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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-achim16, title = {Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference}, author = {Achim, Tudor and Sabharwal, Ashish and Ermon, Stefano}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2254--2262}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, 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 = {https://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.} }
Endnote
%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 %P 2254--2262 %U https://proceedings.mlr.press/v48/achim16.html %V 48 %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.
RIS
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 DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-achim16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2254 EP - 2262 L1 - http://proceedings.mlr.press/v48/achim16.pdf UR - https://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 -
APA
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 Proceedings of Machine Learning Research 48:2254-2262 Available from https://proceedings.mlr.press/v48/achim16.html.

Related Material