Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference

Tudor Achim; Ashish Sabharwal; Stefano Ermon

Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference

Tudor Achim, Ashish Sabharwal, Stefano Ermon ;

Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2254-2262, 2016.

Abstract

Random projections have played an important role in scaling up machine learning and data mining algorithms. Recently they have also been applied to probabilistic inference to estimate properties of high-dimensional distributions; however, they all rely on the same class of projections based on universal hashing. We provide a general framework to analyze random projections which relates their statistical properties to their Fourier spectrum, which is a well-studied area of theoretical computer science. Using this framework we introduce two new classes of hash functions for probabilistic inference and model counting that show promising performance on synthetic and real-world benchmarks.

Related Material

@InProceedings{pmlr-v48-achim16, title = {Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference}, author = {Tudor Achim and Ashish Sabharwal and Stefano Ermon}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2254--2262}, year = {2016}, editor = {Maria Florina Balcan and Kilian Q. Weinberger}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/achim16.pdf}, url = {http://proceedings.mlr.press/v48/achim16.html}, abstract = {Random projections have played an important role in scaling up machine learning and data mining algorithms. Recently they have also been applied to probabilistic inference to estimate properties of high-dimensional distributions; however, they all rely on the same class of projections based on universal hashing. We provide a general framework to analyze random projections which relates their statistical properties to their Fourier spectrum, which is a well-studied area of theoretical computer science. Using this framework we introduce two new classes of hash functions for probabilistic inference and model counting that show promising performance on synthetic and real-world benchmarks.} }

%0 Conference Paper %T Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference %A Tudor Achim %A Ashish Sabharwal %A Stefano Ermon %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-achim16 %I PMLR %J Proceedings of Machine Learning Research %P 2254--2262 %U http://proceedings.mlr.press %V 48 %W PMLR %X Random projections have played an important role in scaling up machine learning and data mining algorithms. Recently they have also been applied to probabilistic inference to estimate properties of high-dimensional distributions; however, they all rely on the same class of projections based on universal hashing. We provide a general framework to analyze random projections which relates their statistical properties to their Fourier spectrum, which is a well-studied area of theoretical computer science. Using this framework we introduce two new classes of hash functions for probabilistic inference and model counting that show promising performance on synthetic and real-world benchmarks.

TY - CPAPER TI - Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference AU - Tudor Achim AU - Ashish Sabharwal AU - Stefano Ermon BT - Proceedings of The 33rd International Conference on Machine Learning PY - 2016/06/11 DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-achim16 PB - PMLR SP - 2254 DP - PMLR EP - 2262 L1 - http://proceedings.mlr.press/v48/achim16.pdf UR - http://proceedings.mlr.press/v48/achim16.html AB - Random projections have played an important role in scaling up machine learning and data mining algorithms. Recently they have also been applied to probabilistic inference to estimate properties of high-dimensional distributions; however, they all rely on the same class of projections based on universal hashing. We provide a general framework to analyze random projections which relates their statistical properties to their Fourier spectrum, which is a well-studied area of theoretical computer science. Using this framework we introduce two new classes of hash functions for probabilistic inference and model counting that show promising performance on synthetic and real-world benchmarks. ER -

Achim, T., Sabharwal, A. & Ermon, S.. (2016). Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference. Proceedings of The 33rd International Conference on Machine Learning, in PMLR 48:2254-2262