象徵性均勻採樣之於互斥或閘電路

Abstract

均勻採樣是統計上一個重要的方法，並被廣泛地運用於模型計數(model counting)、系統驗證與演算法設計等諸多領域。布林空間(Boolean space)中的象徵性採樣(symbolic sampling)是一項於近期提出的技術，其結合了採樣與象徵性的表述來達到有效率的布林論證(Boolean reasoning)。本論文在象徵性採樣的框架下提出一個密實的互斥或閘電路建構方法，在此方法下所產生之電路可於給定的布林空間中進行均勻採樣。 而我們也將此方法進一步的擴展至專注於特定子空間的偏差採樣。 實驗結果顯示了採驗電路生成之效率與其促進布林論證之潛力。

Uniform sampling is an important method in statistics and has various applications in model counting, system verification, algorithm design, among others. Symbolic sampling in a Boolean space is a recently proposed technique that combines sampling and symbolic representation for effective Boolean reasoning. Under the framework of symbolic sampling, we propose a method to construct compact XOR circuits achieving uniform sampling in a given Boolean space. The method is further extended to biased sampling within a focused subspace of interest. Experimental results show the effectiveness of compact sampling circuit generation and its potential to facilitate Boolean reasoning.