Exchangeable variable models

A sequence of random variables is exchangeable if its joint distribution is invariant under variable permutations. We introduce exchangeable vari-able models (EVMs) as a novel class of proba-bilistic models whose basic building blocks are partially exchangeable sequences, a generaliza-tion of exchangeable sequences. We prove that a family of tractable EVMs is optimal under zero-one loss for a large class of functions, includ-ing parity and threshold functions, and strictly subsumes existing tractable independence-based model families. Extensive experiments show that EVMs outperform state of the art classifiers such as SVMs and probabilistic models which are solely based on independence assumptions. 1