Linear concepts and hidden variables

Adam J. Grove, Dan Roth

Research output: Contribution to journalArticlepeer-review


We study a learning problem which allows for a `fair' comparison between unsupervised learning methods - probabilistic model construction, and more traditional algorithms that directly learn a classification. The merits of each approach are intuitively clear: inducing a model is more expensive computationally, but may support a wider range of predictions. Its performance, however, will depend on how well the postulated probabilistic model fits that data. To compare the paradigms we consider a model which postulates a single binary-valued hidden variable on which all other attributes depend. In this model, finding the most likely value of any one variable (given known values for the others) reduces to testing a linear function of the observed values. We learn the model with two techniques: the standard EM algorithm, and a new algorithm we develop based on covariances. We compare these, in a controlled fashion, against an algorithm (a version of Winnow) that attempts to find a good linear classifier directly. Our conclusions help delimit the fragility of using a model that is even `slightly' simpler than the distribution actually generating the data, vs. the relative robustness of directly searching for a good predictor.

Original languageEnglish (US)
Pages (from-to)123-141
Number of pages19
JournalMachine Learning
Issue number1-2
StatePublished - 2001

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Linear concepts and hidden variables'. Together they form a unique fingerprint.

Cite this