Dual Hashing-Based Algorithms for Discrete Integration
Alexis de Colnet
11 mars 2019 - 14:00Given a boolean formula F and a weight function ρ, the problem of discrete integration seeks to compute the weight of F, defined as the sum of the weights of satisfying assignments. Discrete integration, also known as weighted model counting, is a fundamental problem in computer science with wide variety of applications ranging from machine learning and statistics to physics and infrastructure reliability. Given the intractability of the exact variant, the problem of approximate weighted model counting has been subject to intense theoretical and practical investigations over the years. The purpose of this talk is the detailed study of two algorithms for approximate discrete integration: WISH (Weighted Integration & Sum by Hashing) and SWITCH (Sum of Weights and Integration by Threshold Counting and Hashing). Both algorithms compute (ε,δ)-approximations of the weight of F via usage of universal hash functions, a concept invented by Carter and Wegman. In this talk we will show that these two algorithms are remarkably similar. Specifically we will explain that they arise from the same theoretical framework, share a similar structure, provide the same guarantees on the quality of the estimation and that they are dual to each other in terms of complexity in the sense that their complexities differ only by a permutation of certain parameters.
Etant donné fonction booléenne F à n variables et une fonction de poids ρ sur les assignations de variables, on appelle "intégration discrète" la tâche consistant à calculer le poids de F, défini comme la somme des poids des assignations satisfaisant F. Aussi connu sous le nom "Weighted Model Counting", le calcul d'une intégrale discrète trouve des applications dans des domaines variés allant du machine learning jusqu'à la physique statistique. Le calcul exact du poids de F ayant une complexité exponentiellement croissante avec n, les variantes stochastiques ont fait l'objet d'importants efforts tant sur le plan théorique qu'empirique. Cette présentation s'intéresse en détail à deux algorithmes pour le calcul approché de l'intégral discrète : WISH (Weighted Integration & Sum by Hashing) et SWITCH (Sum of Weights and Integration by Threshold Counting and Hashing). Les deux algorithmes produisent une (ε,δ)-approximation du poids de F en utilisant de fonctions de hachage universelles, telles que définies par Carter et Wegman. Au cours de cette présentation, nous expliciterons les remarquables similarités entre WISH et SWITCH. Notamment on montrera que les deux algorithmes dérivent de la même analyse théorique du problème, qu'ils suivent un structure semblable, et qu'ils apportent des garanties similaires sur la qualité de l'approximation tout en ayant des complexités duales dans le sens où, à une permutation des paramètres près, la complexité de l'un correspond à celle de l'autre.