  We present a machine learning algorithm for building classifiers that are
comprised of a small number of disjunctions of conjunctions (or's of and's). An
example of a classifier of this form is as follows: If X satisfies (x1 = 'blue'
AND x3 = 'middle') OR (x1 = 'blue' AND x2 = '<15') OR (x1 = 'yellow'), then we
predict that Y=1, ELSE predict Y=0. An attribute-value pair is called a literal
and a conjunction of literals is called a pattern. Models of this form have the
advantage of being interpretable to human experts, since they produce a set of
conditions that concisely describe a specific class. We present two
probabilistic models for forming a pattern set, one with a Beta-Binomial prior,
and the other with Poisson priors. In both cases, there are prior parameters
that the user can set to encourage the model to have a desired size and shape,
to conform with a domain-specific definition of interpretability. We provide
two scalable MAP inference approaches: a pattern level search, which involves
association rule mining, and a literal level search. We show stronger priors
reduce computation. We apply the Bayesian Or's of And's (BOA) model to predict
user behavior with respect to in-vehicle context-aware personalized recommender
systems.
