반환 모델 카운팅 및 샘플링을 위한 세미링 확장

많은 결정 및 최적화 문제는 자연스럽게 카운팅 문제로 확장됩니다. 가장 잘 알려진 예는 불리언 만족성 문제(SAT)로, 여기서 우리는 변수에 대해 진리 값의 만족스럽게 할당을 세고자 하며, 이는 #SAT 문제로 알려져 있습니다. 마찬가지로, 이산 최적화 문제의 경우, 우리는 목적 함수가 최적 값을 달성하는 상태를 세고자 합니다. SAT와 이산 최적화는 모두 선택적 마르지날리제이션 곱 함수(MPF) 쿼리로 공식화할 수 있습니다. 여기서 우리는 일반적인 선택적 MPF 쿼리가 모델 카운팅을 위해 어떻게 확장될 수 있는지를 보여줍니다. MPF 쿼리는 적절한 세미링에서 텐서 하이퍼네트워크로 인코딩되며, 이는 일반적인 텐서 하이퍼네트워크 수축 알고리즘으로 해결할 수 있습니다. 우리의 모델 카운팅 확장은 역시 세미링이 확장된 MPF 쿼리로, 같은 수축 알고리즘으로 해결할 수 있습니다. 모델 카운팅은 균일한 모델 샘플링에 필요합니다. 우리는 카운팅 확장을 또 다른 세미링을 구성하여 모델 샘플링을 위해 어떻게 더 확장할 수 있는지를 보여줍니다. 우리는 모델 카운팅 및 샘플링 확장을 구현했습니다. 실험 결과, 우리의 일반적인 접근법은 모델 카운팅 및 모델 샘플링에서 최신 기술과 경쟁력이 있다는 것을 보여줍니다.