Exchangeable Variable Models
This work addresses the limitation of existing probabilistic models that rely solely on independence assumptions, offering a more flexible approach for machine learning practitioners dealing with complex data patterns.
The paper tackles the problem of modeling complex functions like parity and threshold functions by introducing exchangeable variable models (EVMs), a novel class of probabilistic models based on partially exchangeable sequences, and proves they are optimal under zero-one loss for a large class of functions, with experiments showing they outperform state-of-the-art classifiers such as SVMs and independence-based models.
A sequence of random variables is exchangeable if its joint distribution is invariant under variable permutations. We introduce exchangeable variable models (EVMs) as a novel class of probabilistic models whose basic building blocks are partially exchangeable sequences, a generalization of exchangeable sequences. We prove that a family of tractable EVMs is optimal under zero-one loss for a large class of functions, including 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.