The Bayesian Case Model: A Generative Approach for Case-Based Reasoning and Prototype Classification
Been Kim
Cynthia Rudin and Julie Shah
Massachusetts Institute of Technology
Cambridge
Massachusetts 02139
\{beenkim
rudin
julie\_a\_shah\
We present the Bayesian Case Model (BCM), a general framework for Bayesian case-based reasoning (CBR) and prototype classification and clustering. BCM brings the intuitive power of CBR to a Bayesian generative framework. The BCM learns prototypes, the ``quintessential" observations that best represent clusters in a dataset, by performing joint inference on cluster labels, prototypes and important features. Simultaneously, BCM pursues sparsity by learning subspaces, the sets of features that play important roles in the characterization of the prototypes. The prototype and subspace representation provides quantitative benefits in interpretability while preserving classification accuracy. Human subject experiments verify statistically significant improvements to participants' understanding when using explanations produced by BCM, compared to those given by prior art.
nips2014CameraReady.tex
\documentclass{article} % For LaTeX2e
\usepackage{nips14submit_e,times}
\usepackage{hyperref}
\usepackage{url}
%\documentstyle[nips13submit_09,times,art10]{article} % For LaTeX 2.09
\nipsfinalcopy
\usepackage{amssymb}
%\usepackag{geometry}                % See geometry.pdf to learn the layout options. There are lots.
%\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx}
%\usepackage{epstopdf}
\usepackage[]{algorithmic}
\usepackage[]{algorithm}
\usepackage{tikz}
\usetikzlibrary{fit,positioning}
\usepackage{array}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{caption}
\usepackage{subcaption}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{adjustbox}
\usepackage{xcolor}
\usepackage{soul}
\usepackage{dsfont}
%  \newcommand{\changeB}[2][blue]{\setulcolor{#1}\ul{#2}\setulcolor{blue}}
\newcommand{\changeB}[1]{\textcolor{blue}{#1}}

\title{The Bayesian Case Model: A Generative Approach for 
Case-Based Reasoning and Prototype Classification}


\author{
Been Kim, Cynthia Rudin and Julie Shah\\
Massachusetts Institute of Technology\\
Cambridge, Massachusetts 02139\\
\texttt{\{beenkim, rudin, julie\_a\_shah\}@csail.mit.edu} \\
%\And
%Cynthia Rudin \\
%Massachusetts Institute of Technology\\
%Cambridge, Massachusetts 02139\\
%\texttt{rudin@mit.edu} \\
%\And
%Julie Shah \\
%Massachusetts Institute of Technology\\
%Cambridge, Massachusetts 02139\\
%\texttt{julie\_a\_shah@csail.mit.edu} \\
}

% The \author macro works with any number of authors. There are two commands
% used to separate the names and addresses of multiple authors: \And and \AND.
%
% Using \And between authors leaves it to \LaTeX{} to determine where to break
% the lines. Using \AND forces a linebreak at that point. So, if \LaTeX{}
% puts 3 of 4 authors names on the first line, and the last on the second
% line, try using \AND instead of \And before the third author name.

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}
\newcommand{\commentB}[1]{\textcolor{blue}{\textbf{Been Comment: #1}}}
%\nipsfinalcopy % Uncomment for camera-ready version

\begin{document}

\newcommand{\cfbox}[2]{%
    \colorlet{currentcolor}{.}%
    {\color{#1}%
    \fbox{\color{currentcolor}#2}}%
}
\maketitle

\begin{abstract}
We present the Bayesian Case Model (BCM), a general framework for Bayesian case-based reasoning (CBR) and prototype classification and clustering. BCM brings the intuitive power of CBR to a Bayesian generative framework.
The BCM learns \textit{prototypes}, the ``quintessential" observations that best represent clusters in a dataset, by performing joint inference on cluster labels, prototypes and important features. Simultaneously, BCM pursues sparsity by learning \textit{subspaces}, the sets of features that play important roles in the characterization of the prototypes. 
The prototype and subspace representation provides quantitative benefits in interpretability while preserving classification accuracy. Human subject experiments verify statistically significant improvements to participants' understanding when using explanations produced by BCM, compared to those given by prior art.
\end{abstract}

 

 %%%%%%%%%%%%%%%%%%%%%%%% INTRO %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

People like to look at examples. Through advertising, marketers present examples of people we might want to emulate in order to lure us into making a purchase. We might ignore recommendations made by Amazon.com and look instead at an Amazon customer's Listmania to find an example of a customer like us. We might ignore medical guidelines computed from a large number of patients in favor of medical blogs where we can get examples of individual patients' experiences. 

Numerous studies have demonstrated that exemplar-based reasoning, involving various forms of matching and prototyping, is fundamental to our most effective strategies for tactical decision-making (\cite{newell1972human, cohen1996metarecognition, klein1989decision}). For example, naturalistic studies have shown that skilled decision makers in the fire service use \textit{recognition-primed decision making}, in which new situations are matched to typical cases where certain actions are appropriate and usually successful ~\cite{klein1989decision}.  
To assist humans in leveraging large data sources to make better decisions, we desire that machine learning algorithms provide output in forms that are easily incorporated into the human decision-making process. 


Studies of human decision-making and cognition provided the key inspiration for artificial intelligence Case-Based Reasoning (CBR) approaches~\cite{aamodt1994case,slade1991case}. CBR relies on the idea that a new situation can be well-represented by the summarized experience of previously solved problems~\cite{slade1991case}. CBR has been used in important real-world applications~\cite{li2008ranking, bichindaritz2006case}, but is fundamentally limited, 
in that it does not learn the underlying complex structure of data in an unsupervised fashion and may not scale to datasets with high-dimensional feature spaces (as discussed in \cite{sormo2005explanation}).

In this work, we introduce a new Bayesian model, called the Bayesian Case Model (BCM), for prototype clustering and subspace learning. In this model, the prototype is the exemplar that is most representative of the cluster. The subspace representation is a powerful output of the model because we neither need nor want the best exemplar to be similar to the current situation in all possible ways: for instance, a moviegoer who likes the same horror films as we do might be useful for identifying good horror films, regardless of their cartoon preferences.
We model the underlying data using a mixture model, and infer sets of features that are important within each cluster (i.e., subspace). This type of model can help to bridge the gap between machine learning methods and humans, who use examples as a fundamental part of their decision-making strategies. 


We show that BCM produces prediction accuracy comparable to or better than prior art for standard datasets. We also verify through human subject experiments that the prototypes and subspaces present as meaningful feedback for the characterization of important aspects of a dataset. In these experiments, the exemplar-based output of BCM resulted in statistically significant improvements to participants' performance of a task requiring an understanding of clusters within a dataset, as compared to outputs produced by prior art.

 %%%%%%%%%%%%%%%%%%%%%%%% BG %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Background and Related Work\label{sec:relatedWork}}


People organize and interpret information through exemplar-based reasoning, particularly when they are solving problems
(\cite{newell1972human, carroll1980analyzing, cohen1996metarecognition, klein1989decision}). AI Cased-Based Reasoning approaches are motivated by this insight, and provide example cases along with the machine-learned solution. Studies show that example cases significantly improve user confidence in the resulting solutions, as compared to providing the solution alone or by also displaying a rule that was
used to find the solution~\cite{cunningham2003evaluation}. 
However, CBR requires solutions (i.e. labels) for previous cases, and does not learn the underlying structure of the data in an unsupervised fashion. Maintaining transparency in complex situations also remains a challenge  ~\cite{sormo2005explanation}. CBR models designed explicitly to produce explanations~\cite{aamodt1991knowledge}
%\textcolor{blue}{}~\cite{aamodt1991knowledge} 
rely on the backward chaining of the causal relation from a solution, which does not scale as complexity increases. The cognitive load of the user also increases with the complexity of the similarity measure used for comparing cases~\cite{freitas2014comprehensible}. Other CBR models for explanations require the model to be manually crafted in advance by experts ~\cite{murdock2003assessing}. 

Alternatively, the mixture model is a powerful tool for discovering cluster distributions in an unsupervised fashion. However, this approach does not provide intuitive explanations for the learned clusters (as pointed out in~\cite{chang2009reading}). 
Sparse topic models are designed to improve interpretability by reducing the number of words per topic~\cite{williamson2010ibp, eisenstein2011sparse}. 
However, using the number of features as a proxy for interpretability is problematic, as sparsity is often not a good or complete measure of interpretability
%this metric is independent of the contents of the model or the data 
~\cite{freitas2014comprehensible}.
Explanations produced by mixture models are typically presented as distributions over features. Even users with technical expertise in machine learning may have a difficult time interpreting such output, especially when the cluster is distributed over a large number of features~\cite{freitas2014comprehensible}. 

Our approach, the Bayesian Case Model (BCM), simultaneously performs unsupervised clustering and learns both the most representative cases (i.e., prototypes) and important features (i.e., subspaces). 
BCM preserves the power of CBR in generating interpretable output, where  interpretability comes not only from sparsity but from the prototype exemplars.

In our view, there are at least three widely known types of interpretable models: sparse linear classifiers (\cite{tibshirani1996regression,chang2009reading,UstunRu14}); discretization methods, such as decision trees and decision lists (e.g., \cite{de2000classification, williamson2010ibp, eisenstein2011sparse,LethamRuMcMa14,GohRu14}); and prototype- or case-based classifiers (e.g., nearest neighbors~\cite{cover1967nearest} or a supervised optimization-based method~\cite{bien2011prototype}). 
(See \cite{freitas2014comprehensible} for a review of interpretable classification.)
%Extensive review on interpretable classification methods is found from \cite{freitas2014comprehensible}.
%BCM aims at the third type, but through unsupervised generative mechanisms for explaining clusters, rather than supervised optimization-based approaches or by focusing on local points in the data space~\cite{baehrens2010explain}.
BCM is intended as the third model type, but uses unsupervised generative mechanisms to explain clusters, rather than supervised approaches~\cite{graf2009prototype} or by focusing myopically on neighboring points~\cite{baehrens2010explain}.





 %%%%%%%%%%%%%%%%%%%%%%%% BCM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{The Bayesian Case Model\label{sec:BCM}}
%We formally describe the BCM in this section. 
Intuitively, BCM generates each observation using the important pieces of related prototypes. The model might generate a movie profile made of the horror movies from a quintessential horror movie watcher, and action movies from a quintessential action moviegoer.
% and cartoons from a cartoon connoisseur.%when given someone else's example.)

\begin{figure}
\centering

\resizebox{2in}{1.5in}{
\begin{tikzpicture}
\tikzstyle{main}=[circle, minimum size = 5mm, thick, draw =black!80, node distance = 8mm]
\tikzstyle{hyper}=[node distance = 10mm]
\tikzstyle{connect}=[-latex, thick]
\tikzstyle{box}=[rectangle, draw=black!100]

  \node[hyper] (N)  {$N$};
    \node[hyper, fill = white!100] (q) [right=of N] {$q$};
  \node[main, fill = white!100] (p) [below=of N] { $p_{s}$};
  \node[main, fill = white!100] (phi) [below=of p] { $\phi_{s}$};
  \node[main, fill = white!100] (omega) [below=of q] {$\omega_s$ };
  \node[hyper, fill = white!100] (lambda) [left=of p] {$\lambda$, $c$};
  \node[main, fill = black!10] (x) [below=of phi ] { $x_{ij}$};
  \node[main] (z_s) [left=of x] {$z_{ij}$};
    \node[main] (theta_s) [left=of z_s] {$\pi_i$};
  \node[hyper, fill = white!100] (alpha_s) [left=of theta_s] {$\alpha$};
   
  \path (alpha_s) edge [connect] (theta_s)
         (theta_s) edge [connect] (z_s)
         (z_s) edge [connect] (x)
         (N) edge [connect] (p)
        (p) edge [connect] (phi)
        (lambda) edge[connect] (phi)
        (q) edge[connect](omega)
        (omega) edge [connect] (phi)
        (phi) edge [connect] (x);  
  \node[rectangle, inner sep=0mm, fit= (z_s)  (x) (theta_s) ,label=below right:N, xshift=17.5mm, yshift=-1mm] {};
  \node[rectangle, inner sep=5.8mm, draw=black!100, fit =   (z_s) (x) (theta_s)] {};
     
  \node[rectangle, inner sep=0mm, fit= (z_s)  (x)   ,label=below right:F, xshift=6.5mm, yshift=3mm] {};
  \node[rectangle, inner sep=2.4mm, draw=black!100, fit =   (z_s) (x) ] {};

 
      \node[rectangle, inner sep=0mm, fit= (omega) (phi) (p),label=below right:S, yshift=3mm, xshift=-3mm] {};
  \node[rectangle, inner sep=1mm, draw=black!100, fit = (omega) (phi) (p)] {};
  
\end{tikzpicture}
}
\caption{Graphical model for the Bayesian Case Model\label{fig:graphicalModel}}
\end{figure}
BCM begins with a standard discrete mixture model ~\cite{hofmann1999probabilistic,blei2003latent} to represent the underlying structure of the observations.
It augments the standard mixture model with \textit{prototypes} and \textit{subspace feature indicators} that characterize the clusters. We show in Section~\ref{subsec:exp} that prototypes and subspace feature indicators improve human interpretability as compared to the standard mixture model output. The graphical model for BCM is depicted in Figure~\ref{fig:graphicalModel}. 

We start with $N$ observations, denoted by $\mathbf{x} = \{ x_1, x_2, \dots, x_N\}$, with each $x_i$ represented as a random mixture over clusters. 
There are $S$ clusters, where $S$ is assumed to be known in advance. (This assumption can easily be relaxed through extension to a non-parametric mixture model.) 
Vector $\pi_i$ are the mixture weights over these clusters for the $i^{th}$ observation $x_i$, $\pi_i\in \mathbb{R}_+^S$.
Each observation has $P$ features, and we denote the $j^{th}$ feature of the $i^{th}$ observation as $x_{ij}$.
Each feature $j$ of the observation $x_{i}$ comes from one of the clusters, the index of the cluster for $x_{ij}$ 
is denoted by $z_{ij}$ and the full set of cluster assignments for observation-feature pairs is denoted by $\mathbf{z}$.
Each $z_{ij}$ takes on the value of a cluster index between 1 and $S$. 
Hyperparameters $ q, \lambda, c,$ and $\alpha$ are assumed to be fixed.


The explanatory power of BCM results from how the clusters are characterized.  
While a standard mixture model assumes that each cluster take the form of a predefined parametric distribution (e.g., normal), BCM characterizes each cluster by a \textit{prototype}, $p_s$, and a \textit{subspace feature indicator}, $\omega_s$.  
Intuitively, the \textit{subspace feature indicator} selects only a few features that play an important role in identifying the cluster and prototype 
(hence, BCM clusters are \textit{subspace clusters}). We intuitively define these latent variables below.

\textit{Prototype, $p_s$}:
The prototype $p_s$  for cluster $s$  is defined as one observation in $\mathbf{x}$ that maximizes 
$p(p_s|\omega_s, \mathbf{z},\mathbf{x})$, 
with the probability density and $\omega_s$ as defined below.
%Our notation for element $j$ of $p_s$ is $p_{sj}$. Since $p_s$ is a prototype, it is equal to one of the observations, such that $p_{sj}=x_{ij}$ for some $i$.
%\changeB{Replace: 
Our notation for element $j$ of $p_s$ is $p_{sj}$. Since $p_s$ is a prototype, it is equal to one of the observations, so $p_{sj}=x_{ij}$ for some $i$.
%}
Note that more than one maximum may exist per cluster; in this case, one prototype is arbitrarily chosen.
Intuitively, the prototype is the ``quintessential" observation that best represents the cluster.

\textit{Subspace feature indicator $\omega_s$}: Intuitively, $\omega_s$ `turns on' the features
that are important for characterizing cluster $s$ and selecting the prototype, $p_s$.
Here, $\omega_s\in \{0,1\}^P$ is an indicator variable that is 1 on the subset of features 
that maximizes  $p(\omega_s|p_s, \mathbf{z},\mathbf{x})$, with the probability for $\omega_s$ as defined below.
Here, $\omega_s$ is a binary vector of size $P$, where
each element is an indicator of whether or not feature $j$ belongs to subspace $s$.



The generative process for BCM is as follows:
First, we generate the subspace clusters. A subspace cluster can be fully described by three components: 1) a prototype, $p_s$, generated by sampling uniformly over all observations, $1\dots N$;  2) a feature indicator vector, $\omega_s$, that indicates important features for that subspace cluster, where each element of the feature indicator ($\omega_{sj}$) is generated according to a Bernoulli distribution with hyperparameter $q$; and 3) the distribution of feature outcomes for each feature, $\phi_s$, for subspace $s$, which we now describe.


\textit{Distribution of feature outcomes $\phi_s$ for cluster $s$}: 
Here, $\phi_s$ is a data structure wherein each ``row" $\phi_{sj}$ is a discrete probability distribution of possible outcomes for feature $j$. Explicitly,
$\phi_{sj}$  is a vector of length $V_j$, where $V_j$ is the number of possible outcomes of feature $j$.
Let us define $\Theta$ as a vector of the possible outcomes of feature $j$ (e.g., for feature `color', $\Theta = [ \text{red}, \text{blue},\text{yellow} ]$), where
$\Theta_v$ represents a particular outcome for that feature (e.g., $\Theta_v =\text{blue}$). We will generate $\phi_s$ so that it mostly takes outcomes from the prototype $p_s$ for the important dimensions of the cluster. We do this by considering the vector $g$, indexed by possible outcomes $v$, as follows:
\begin{equation*}
g_{p_{sj}, \omega_{sj}, \lambda}(v) = \lambda ( 1 + c \mathds{1}_{[w_{sj} = 1 \text{  and  }	 p_{sj} = \Theta_v]}) ,
\end{equation*}
where $c$ and $\lambda$ are constant hyperparameters that indicate how much we will copy the prototype in order to generate the observations.
The distribution of feature outcomes will be determined by $g$ through $\phi_{sj} \sim \text{Dirichlet}( g_{p_{sj}, \omega_{sj}, \lambda} )$. 
To explain at an intuitive level: First, consider the irrelevant dimensions $j$ in subspace $s$, which have $w_{sj}=0$. In that case, $\phi_{sj}$ will look like a uniform distribution over all possible outcomes for features $j$; the feature values for the unimportant dimensions are generated arbitrarily according to the prior. Next, consider relevant dimensions where $w_{sj}=1$. In this case, $\phi_{sj}$ will generally take on a larger value $\lambda+c$ for the feature value that prototype $p_s$ has on feature $j$, which is called $\Theta_v$. All of the other possible outcomes are taken with lower probability $\lambda$. As a result, we will be more likely to select the outcome $\Theta_v$ that agrees with the prototype $p_s$.
In the extreme case where $c$ is very large, we can copy the cluster's prototype directly within the cluster's relevant subspace and assign the rest of the feature values randomly.

An observation is then a mix of different prototypes, wherein we take the most important pieces of each prototype.
%Specifically, we generate the observations as follows: For element $j$ of observation $i$, we select a cluster according to its
%subspace cluster distribution $\pi_i$. Here, 
To do this, mixture weights $\pi_i$ are generated according to a Dirichlet distribution, parameterized by hyperparameter $\alpha$.
From there, to select a cluster and obtain the cluster index $z_{ij}$ for each $x_{ij}$, we sample from a multinomial distribution with parameters $\pi_i$. 
Finally, each feature for an observation, $x_{ij}$, is sampled
from the feature distribution of the assigned subspace cluster ($\phi_{z_{ij}}$).
(Note that 
%this part of our model is the standard mixture model formulation. 
Latent Dirichlet Allocation (LDA)~\cite{blei2003latent} also begins with a standard mixture model, though our feature values exist in a discrete set that is not necessarily binary.) 
Here is the full model, with hyperparameters $c$, $\lambda$, $q$, and $\alpha$:
\begin{align*}
	\omega_{sj}&\sim \text{Bernoulli}(q) \;\;\forall s,j\qquad\qquad
	p_s \sim \text{Uniform}(1,N) \;\;\forall s\qquad\qquad
	\\\nonumber \phi_{sj} &\sim \text{Dirichlet}( g_{p_{sj}, \omega_{sj}, \lambda} ) \;\;\forall s,j
	%\\ \nonumber
	%\lefteqn{
	\qquad\textrm{ where } g_{p_{sj}, \omega_{sj}, \lambda}(v) = \lambda ( 1 + c \mathds{1}_{[w_{sj} = 1 \text{  and  }	 p_{sj} = \Theta_v]}) \\\nonumber
	\pi_i &\sim \text{Dirichlet}(\alpha) \;\;\forall i \qquad\qquad
	z_{ij} \sim \text{Multinomial}(\pi_i) \;\;\forall i,j\qquad
	x_{ij} \sim \text{Multinomial}(\phi_{z_{ij}j} ) \;\;\forall i,j.
\end{align*}
Our model can be readily extended to different similarity measures,
such as standard kernel methods or domain specific similarity measures, by modifying
the function $g$.  For example, we can use the least squares loss i.e., for fixed threshold $\epsilon$,
$g_{p_{sj}, \omega_{sj}, \lambda}(v) = \lambda ( 1 + c \mathds{1}_{[w_{sj} = 1 \text{  and  }	 (p_{sj}  -\Theta_v )^2 \leq \epsilon  ]})$; or, more generally, $g_{p_{sj}, \omega_{sj}, \lambda}(v) = \lambda ( 1 + c \mathds{1}_{[w_{sj} = 1 \text{  and  }	 \ell(p_{sj},\Theta_v ) \leq \epsilon  ]})$.


In terms of setting hyperparameters, there are natural settings for $\alpha$ (all entries being 1). This means that there are three real-valued parameters to set, which can be done through cross-validation, another layer of hierarchy with more diffuse hyperparameters, or plain intuition. To use BCM for classification, vector $\pi_i$ is used as $S$ features for a classifier, such as SVM.

\subsection{Motivating example}

This section provides an illustrative example for prototypes, subspace feature indicators and subspace clusters, using a dataset composed of a mixture of smiley faces. 
The feature set for a smiley face is composed of types, shapes and colors of eyes and mouths. For the purpose of this example, assume that the ground truth is that there are three clusters, each of which has two features that are important for defining that cluster. In Table~\ref{tab:smileresults}, we show the first cluster, with a subspace defined by the color (green) and shape (square) of the face; the rest of the features are not important for defining the cluster. For the second cluster, color (orange) and eye shape define the subspace. We generated 240 smiley faces from  BCM's prior with $\alpha=0.1$ for all entries, and $q=0.5, \lambda=1$ and $c = 50$.
\begin{table}[h!]
\centering
\resizebox{.76\columnwidth}{!}{
\begin{tabular}{|p{.1cm}|p{7cm} || p{4.3cm}||p{2.8cm}|p{4.7cm}|}
\hline
 &\centering \multirow{2}{*}{Data in assigned to cluster}
 &\centering LDA & \multicolumn{2}{c|}{BCM}  \\ 
 \cline{3-5}
 && Top 3 words and probabilities & \centering Prototype &  \hspace{0.2in} Subspaces\\
\hline
1&
  \begin{minipage}{1\textwidth}
      \vspace{.2cm}
    \includegraphics[scale=.2]{data_in_subspace0}
    \end{minipage}
    &
  \begin{minipage}{1\textwidth}
   \includegraphics[scale=.2]{color0}   \hspace{.2in}
   \includegraphics[scale=.1]{shape0} \hspace{.1in}
      \includegraphics[scale=.2]{eyenew1}
      \end{minipage}
        &   
          \begin{minipage}{1\textwidth}
            \vspace{.2cm}
   \includegraphics[scale=.3]{prototype0}
   \end{minipage}
  & color (\includegraphics[scale=.2]{color0})   and 
  shape ( \includegraphics[scale=.07]{shape0} ) are important.
\\ 
&&
\hspace{.2in}0.26 \hspace{.25in}0.23 \hspace{.3in}0.12
& &
\\ \hline 
2&
    \begin{minipage}{1\textwidth}
        \vspace{.2cm}
%  \caption{Prototype 2\\ Subspace:\\color and eye} 
   \includegraphics[scale=.2]{data_in_subspace1}
   \end{minipage}
   &
  \begin{minipage}{1\textwidth}
   \includegraphics[scale=.18]{color1}
  \hspace{.15in}
         \includegraphics[scale=.2]{eyenew1}   
         \hspace{.1in}
   \includegraphics[scale=.1]{shape0}
%  \caption{Topic 2: 0.26, 0.24, 0.16}
\end{minipage}
&
  \begin{minipage}{1\textwidth}
  \vspace{.2cm}
   \includegraphics[scale=.3]{prototype1}
   \end{minipage}
      &
    color (\includegraphics[scale=.2]{color1}) and eye (\includegraphics[scale=.18]{eyenew1}) are important.
\\  
&&
\hspace{.2in}0.26\hspace{.25in}0.24\hspace{.35in}0.16
&&
\\ \hline
3&  
   \begin{minipage}{1\textwidth}
       \vspace{.2cm}
   \includegraphics[scale=.2]{data_in_subspace2}
   \end{minipage}
   &
  \begin{minipage}{1\textwidth}
   \includegraphics[scale=.15]{eyenew2}\hspace{.2in}
   \includegraphics[scale=.2]{smilenew2}\hspace{.2in}
      \includegraphics[scale=.1]{shape2}
  %\caption{Topic 3: 0.35, 0.27, 0.15}
  \end{minipage}
&
  \begin{minipage}{1\textwidth}
    \vspace{.2cm}
   \includegraphics[scale=.3]{prototype2}
   \end{minipage}
 % \caption{Prototype 3\\ Subspace:\\eye and mouth}
   &
  eye (\includegraphics[scale=.18]{eyenew2}) and mouth (\includegraphics[scale=.18]{smilenew2}) are important.
   \\
   &&
\hspace{.1in}0.35\hspace{.33in} 0.27\hspace{.33in} 0.15
&&
 \\  \hline
   
\end{tabular}
}
\caption{The mixture of smiley faces for LDA and BCM\label{tab:smileresults}}
\end{table}


BCM works differently to Latent Dirichlet Allocation (LDA)~\cite{blei2003latent}, which presents its output in a very different form. Table~\ref{tab:smileresults} depicts the representation of clusters in both LDA (middle column) and BCM (right column). This dataset is particularly simple, and we chose this comparison because the two most important features that both LDA and  BCM learn are identical for each cluster. However, LDA does not learn prototypes, and represents information differently. To convey cluster information using LDA (i.e., to define a topic), we must record several probability distributions -- one for each feature. 
For BCM, we need only to record a prototype (e.g., the green face depicted in the top row, right column of the figure), and state which features were important for that cluster's subspace (e.g., shape and color). For this reason, BCM is more succinct than LDA with regard to what information must be recorded in order to define the clusters. One could define a ``special" constrained version of LDA with topics having uniform weights over a subset of features, and with ``word" distributions centered around a particular value. This would require a similar amount of memory; however, it loses information, with respect to the fact that BCM carries a full prototype within it for each cluster.


A major benefit of BCM over LDA is that the ``words" in each topic (the choice of feature values) are coupled and not assumed to be independent -- correlations can be controlled depending on the choice of parameters. The independence assumption of LDA can be very strong, and this may be crippling for its use in many important applications. Given our example of images, one could easily generate an image with eyes and a nose that cannot physically occur on a single person (perhaps overlapping). BCM can also generate this image, but it would be unlikely, as the model would generally prefer to copy the important features from a prototype.



BCM performs joint inference on prototypes, subspace feature indicators and cluster labels for observations. This encourages the inference step to achieve solutions where clusters are better represented by prototypes. We will show that this is beneficial in terms of predictive accuracy in Section~\ref{subsec:results_prediction}. We will also show through an experiment involving human subjects that BCM's succinct representation is very effective for communicating the characteristics of clusters in Section \ref{subsec:exp}.



\subsection{Inference: collapsed Gibbs sampling}

We use collapsed Gibbs sampling to perform inference, as this has been observed to converge quickly, particularly in %LDA
mixture models~\cite{griffiths2004finding}.
We sample $\omega_{sj}$, $z_{ij}$, and $p_s$, where $\phi$ and $\pi$ are integrated out. Note that we can recover $\phi$ by simply counting the number of feature values assigned to each subspace. Integrating out $\phi$ and $\pi$ results in the following expression for sampling $z_{ij}$:
\begin{equation}
p(z_{ij} =s| z_{i\neg j}, \mathbf{x}, p, \omega, \alpha, \lambda) 
\propto \dfrac{ \alpha/S + n_{(s,i,\neg j,\cdot)}  }{ \alpha + n } \times \dfrac{ g(p_{sj}, \omega_{sj}, \lambda)+ n_{(s,\cdot,j,x_{ij})}  }{  \sum_s g(p_{sj}, \omega_{sj}, \lambda) + n_{(s,\cdot,j,\cdot)}  },
\end{equation}
where $n_{(s,i,j,v)} = \mathds{1}(z_{ij}=s, x_{ij}=v)$. 
In other words, if $x_{ij}$ takes 
feature value $v$ for feature $j$ and is assigned to cluster $s$, then $n_{(s,i,j,v)} =1$, or 0 otherwise. Notation
$n_{(s,\cdot,j, v)}$ is the number of times that the $j^{th}$ feature
of an observation takes feature value $v$ and that observation is assigned to subspace cluster $s$ (i.e., $n_{(s,\cdot,j, v)} = \sum_i \mathds{1}(z_{ij}=s, x_{ij}=v)$). Notation  $n_{(s,\cdot,j,\cdot)}$ means sum over $i$ and $v$.
We use $n_{(s,i,\neg j,v)}$ to denote a count that does not include the feature $j$. %The derivation follows the standard collapsed Gibbs sampling for LDA mixture models~\cite{griffiths2004finding}.
%\changeB{Replace: 
The derivation is similar to the standard collapsed Gibbs sampling for LDA mixture models~\cite{griffiths2004finding}.
%}

Similarly, integrating out $\phi$ results in the following expression for sampling $\omega_{sj}$:
\begin{equation}
p(\omega_{sj} = b | q, p_{sj}, \lambda, \phi, \mathbf{x}, \mathbf{z}, \alpha) 
\propto   \begin{cases}
q \times \dfrac{ \mathbf{B}(g(p_{sj}, 1, \lambda)  + n_{(s,\cdot, j, \cdot)})}{\mathbf{B}(g(p_{sj}, 1, \lambda))}   & \text{b = 1} \\
1- q \times \dfrac{ \mathbf{B}(g(p_{sj}, 0, \lambda)  + n_{(s,\cdot, j, \cdot)})}{\mathbf{B}(g(p_{sj}, 0, \lambda))} & \text{b = 0},
    \end{cases} 
\end{equation}
where $\mathbf{B}$ is the Beta function and comes from integrating out $\phi$ variables, which are sampled from Dirichlet distributions.


 %%%%%%%%%%%%%%%%%%%%%%%% RESULTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Results\label{sec:results}} 
In this section, we show that BCM produces prediction accuracy comparable to or better than LDA for standard datasets. We also verify the interpretability of BCM through human subject experiments involving a task that requires an understanding of clusters within a dataset. 
We show statistically significant improvements in objective measures of task performance using prototypes produced by BCM, compared to output of LDA.
Finally, we visually illustrate that the learned prototypes and subspaces present as 
meaningful feedback for the characterization of important aspects of the dataset.

 \subsection{BCM maintains prediction accuracy.\label{subsec:results_prediction}}
 \begin{figure}[]
 \begin{subfigure}[]{.33\textwidth}
 \centering
   \includegraphics[scale=.21]{handacc}
      \includegraphics[scale=.21]{newsacc}
  \caption{Accuracy and standard deviation with SVM \label{subfig:handsvm}}
 \end{subfigure}
% \hfill
% \begin{subfigure}[]{.33\textwidth}
% \centering
%   \includegraphics[scale=.18]{newsacc}
%  \caption{Accuracy and Std. with SVM (News)\label{subfig:newssvm}}
% \end{subfigure} 
 \hfill
  \begin{subfigure}[]{.24\textwidth}
 \centering
\includegraphics[scale=.21]{acc_hand_ndata200unsuper} 
      \includegraphics[scale=.21]{acc_news_ndata1200unsuper} 
  \caption{Unsupervised accuracy for  BCM\label{subfig:handunsuper}}
 \end{subfigure}
 \hfill  
 \begin{subfigure}[]{.33\textwidth}
 \centering
    \begin{minipage}{.5\textwidth}
\includegraphics[scale=.14]{lambda}  
\includegraphics[scale=.14]{peaksize}   
\includegraphics[scale=.14]{q}  
\end{minipage}
%  \caption{Unsupervised accuracy (News)\label{subfig:newsunsuper}}
    \caption{Sensitivity analysis for BCM\label{subfig:sensitivity}}
 \end{subfigure} 
\caption{
% Prediction accuracy reported for the \textit{Handwritten Digit}~\cite{hull1994database} and \textit{20 Newsgroups} datasets~\cite{Lang95} . (a) and (b) apply SVM for both LDA and BCM. (c) presents the unsupervised accuracy for BCM and (d) presents the sensitivity analysis for hyperparameters. 
%Datasets were produced by randomly sampling 10 to 70 observations of each digit for the \textit{Handwritten Digit} dataset, and 100 - 450 documents per document class for the \textit{20 Newsgroups} dataset.  The \textit{Handwritten Digit} pixel values (range from 0 to 255) were rescaled into 7 bins (range from 0 to 6).
%Each 16 by 16 pixel picture was represented as a 1D vector of pixels values with length 256.
%Both BCM and LDA were randomly initialized with the same seed (half the labels were incorrect and randomly mixed),
%Number of iterations  was set at 1000. $S=4$ for \textit{20 Newsgroups} and $S=10$ for \textit{Handwritten Digit}. $\alpha = 0.01, \lambda = 2, c = 50, q = 0.8$. \label{fig:results} \\
%\changeB{Replace: 
Prediction test accuracy reported for the \textit{Handwritten Digit}~\cite{hull1994database} and \textit{20 Newsgroups} datasets~\cite{Lang95}. (a) applies SVM for both LDA and BCM, (b) presents the unsupervised accuracy of BCM for \textit{Handwritten Digit} (top) and \textit{20 Newsgroups} (bottom) and (c) depicts the sensitivity analysis conducted for hyperparameters for \textit{Handwritten Digit} dataset. 
Datasets were produced by randomly sampling 10 to 70 observations of each digit for the \textit{Handwritten Digit} dataset, and 100-450 documents per document class for the \textit{20 Newsgroups} dataset. The \textit{Handwritten Digit} pixel values (range from 0 to 255) were rescaled into seven bins (range from 0 to 6).
Each 16-by-16 pixel picture was represented as a 1D vector of pixel values, with a length of 256.
Both BCM and LDA were randomly initialized with the same seed (one half of the labels were incorrect and randomly mixed),
The number of iterations was set at 1,000. $S=4$ for \textit{20 Newsgroups} and $S=10$ for \textit{Handwritten Digit}. $\alpha = 0.01, \lambda = 1, c = 50, q = 0.8$. \label{fig:results}
%}
}
 \end{figure}
We show that BCM output produces prediction accuracy comparable to or better than LDA, which uses the same mixture model (Section~\ref{sec:BCM}) to learn the underlying structure but does not learn explanations (i.e., prototypes and subspaces). 
We validate this through use of two standard datasets: \textit{Handwritten Digit}~\cite{hull1994database} and \textit{20 Newsgroups}~\cite{Lang95}. 
We use the implementation of LDA available from \cite{phan2013gibbslda}, which incorporates Gibbs sampling, the same inference technique used for  BCM.


Figure~\ref{subfig:handsvm} depicts the ratio of correctly assigned cluster labels for BCM and LDA. 
In order to compare the prediction accuracy with LDA, the learned cluster labels are provided as features to a support vector machine (SVM) with linear kernel, as is often done in the LDA literature on clustering~\cite{blei2003latent}.
The improved accuracy of BCM over LDA, as depicted in the figures, is explained in part by the ability of  BCM to capture dependencies among
features via prototypes, as described in Section~\ref{sec:BCM}.
We also note that prediction accuracy when using the full \textit{20 Newsgroups} dataset acquired by LDA (accuracy: 0.68$\pm$ 0.01) matches that reported previously for this dataset when using a combined LDA and SVM approach~\cite{zhu2012medlda}. Also, %The precision and recall matche with the reported accuracy from~\cite{salakhutdinov2009replicated}.
LDA accuracy for the full \textit{Handwritten Digit} dataset (accuracy: 0.76 $\pm$ 0.017) is comparable to that produced by BCM using the subsampled dataset (70 samples per digit, accuracy: 0.77 $\pm$ 0.03). 

 
As indicated by Figure~\ref{subfig:handunsuper}, BCM achieves high unsupervised clustering accuracy as a function of iterations. We can compute this measure for BCM because each cluster is characterized by a prototype -- a particular data point with a label in the given datasets. (Note that this is not possible for LDA.) We set $\alpha$ to prefer each $\pi_i$ to be sparse, so only one prototype generates each observation, and we use that prototype's label for the observation.
Sensitivity analysis in Figure \ref{subfig:sensitivity} indicates that the additional parameters introduced to learn prototypes and subspaces (i.e., $q, \lambda$ and $c$) 
are not too sensitive within the range of reasonable choices. 

 
 

 
 	
 \subsection{Verifying the interpretability of BCM\label{subsec:exp}}

We verified the interpretability of  BCM by performing human subject experiments that incorporated a task requiring an understanding of clusters within a dataset. This task required each participant to assign 16 recipes, described only by a set of required ingredients (recipe names and instructions were withheld), to one cluster representation out of a set of four to six. (This approach is similar to those used in prior work to measure comprehensibility~\cite{huysmans2011empirical}.) We chose a recipe dataset\footnote{Computer Cooking Contest: \texttt{http://liris.cnrs.fr/ccc/ccc2014/}} for this task because such a dataset requires clusters to be well-explained in order for subjects to be able to perform classification, but does not require special expertise or training. 

Our experiment incorporated a within-subjects design, which allowed for more powerful statistical testing and mitigated the effects of inter-participant variability. To account for possible learning effects, we blocked the BCM and LDA questions and balanced the assignment of participants into the two ordering groups: Half of the subjects were presented with all eight BCM questions first, while the other half first saw the eight LDA questions. Twenty-four participants (10 females, 14 males, average age 27 years) performed the task, answering a total of 384 questions. Subjects were encouraged to answer the questions as quickly and accurately as possible, but were instructed to take a 5-second break every four questions in order to mitigate the potential effects of fatigue.

 \begin{figure}
 \begin{center}
\includegraphics[scale=.2]{exp_bigger_notitle}
 \caption{Web-interface for the human subject experiment\label{fig:exp}}
 \end{center}
 \end{figure}
Cluster representations (i.e., explanations) from LDA were presented as the set of top ingredients for each recipe topic cluster. 
%For BCM, we simply presented the prototype for each cluster. 
For BCM we presented the ingredients of the prototype without the name of the recipe and without subspaces. The number of top ingredients shown for LDA was set as the number of ingredients from the corresponding BCM prototype
and ran Gibbs sampling for LDA with different initializations until the ground truth clusters were visually identifiable. 

Using explanations from BCM, the average classification accuracy was 85.9\%, which was statistically significantly higher ($c^2(1, N = 24) = 12.15, p \ll 0.001 $) than that of LDA, (71.3\%). 
For both LDA and BCM, each ground truth label was manually coded by two domain experts: the first author and one independent analyst (kappa coefficient: 1). These manually-produced ground truth labels were identical to those that LDA and BCM predicted for each recipe.
There was no statistically significant difference between BCM and LDA in the amount of time spent on each question ($t(24) = 0.89, p= 0.37$); the overall average was 32 seconds per question, with 3\% more time spent on BCM than on LDA.
Subjective evaluation using Likert-style questionnaires produced no statistically significant differences between reported preferences for LDA versus BCM. Interestingly, this suggests that participants did not have insight into their superior performance using output from BCM versus that from LDA. 



Overall, the experiment demonstrated substantial improvement to participants' classification accuracy when using BCM compared with LDA, with no degradation to other objective or subjective measures of task performance. 




 \subsection{Learning subspaces\label{subsec:results_subspace}}
 

\begin{figure}
 \begin{subfigure}[]{.3\textwidth}
 \centering
\includegraphics[scale=.19]{handsubspace}  
  \caption{\textit{Handwritten Digit} dataset\label{fig:handsubspace}}
 \end{subfigure} 
 \hfill
  \begin{subfigure}[]{.65\textwidth}
  \begin{minipage}{1\textwidth} \hfill 
  \centering
  \resizebox{.88\textwidth}{!}{
\begin{tabular}{|p{3.8cm}| p{5cm}|}
\hline
Prototype (Recipe names) &  Ingredients (\fcolorbox{red}{white}{Subspaces}) \\ \hline
 \textit{Herbs and Tomato in Pasta}
 & basil, garlic, Italian seasoning, \fcolorbox{red}{white}{oil} \fcolorbox{red}{white}{pasta}\fcolorbox{red}{white}{pepper} salt,   \fcolorbox{red}{white}{tomato} \\
% basil garlic italian oil pasta pepper salt seasoning tomato
\hline
\textit{Generic chili recipe}
 & \fcolorbox{red}{white}{beer} \fcolorbox{red}{white}{chili powder} cumin, garlic, meat, oil, onion, pepper, salt, \fcolorbox{red}{white}{tomato}\\
% beer chili cumin garlic meat oil onion pepper salt tomato
\hline
\textit{Microwave brownies}
 & \fcolorbox{red}{white}{baking powder} sugar, butter, 
 \fcolorbox{red}{white}{chocolate} chopped pecans, eggs,   flour, salt, vanilla\\
% baking brown butter chocolate chopped eggs flour salt vanilla
\hline
\textit{Spiced-punch}
& 
cinnamon stick,
\fcolorbox{red}{white}{lemon juice}
\fcolorbox{red}{white}{orange juice}
\fcolorbox{red}{white}{pineapple juice} sugar, water,   whole cloves \\
%cinnamon lemon orange pineapple sugar water whole
\hline
\end{tabular}
}
    \end{minipage}
      \caption{\textit{Recipe} dataset\label{fig:recipesubspace}}
     \end{subfigure} 
 \caption{Learned prototypes and subspaces for the \textit{Handwritten Digit} and \textit{Recipe} datasets. 
 \label{fig:subspace}}
 \end{figure}
Figure~\ref{fig:handsubspace} illustrates the learned prototypes and subspaces
as a function of sampling iterations for the \textit{Handwritten Digit} dataset. For the later iterations, shown on the right of the figure, the BCM output effectively characterizes the important aspects of the data. In particular, the subspaces learned by BCM are pixels that define the digit for the cluster's prototype. 

Interestingly, the subspace highlights the \textit{absence} of writing in certain areas. This makes sense: For example, one can define a `7' by showing the absence of pixels on the left of the image where the loop of a `9' might otherwise appear. The pixels located where there is variability among digits of the same cluster 
are not part of the defining subspace for the cluster.

Because we initialized randomly, in early iterations, the subspaces tend to identify features common to the observations that were randomly initialized to the cluster. This is because $\omega_s$ assigns higher likelihood to features with the most similar values across observations within a given cluster. For example, most digits `agree' (i.e., have the same zero pixel value) near the borders; thus, these are the first areas that are refined, as shown in Figure~\ref{fig:handsubspace}. Over iterations, the third row of Figure~\ref{fig:handsubspace} shows how  BCM learns to separate the digits ``3" and ``5," which tend to share many pixel values in similar locations. Note that the sparsity of the subspaces can be customized by hyperparameter $q$.






Next, we show results for BCM using 
%the recipe dataset %  
the Computer Cooking Contest dataset 
in Figure~\ref{fig:recipesubspace}. 
Each prototype consists of a set of ingredients for a recipe, and the subspace is a set of important ingredients that define that cluster, highlighted in red boxes. For instance, BCM found a ``chili" cluster defined by the subspace ``beer," ``chili powder," and ``tomato." A recipe called ``Generic Chili Recipe" was chosen as the prototype for the cluster. %\footnote{
(Note that beer is indeed a typical ingredient in chili recipes.)

 

 %%%%%%%%%%%%%%%%%%%%%%%% CONCLUSION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Conclusion}
The Bayesian Case Model provides a generative framework for case-based reasoning and prototype-based modeling. Its clusters come with natural explanations; namely, a prototype (a quintessential exemplar for the cluster) and a set of defining features for that cluster. We showed the quantitative advantages in prediction quality and interpretability resulting from the use of BCM. Exemplar-based modeling (nearest-neighbors, case-based reasoning) has historical roots dating back to the beginning of artificial intelligence; this method offers a fresh perspective on this topic, and a new way of thinking about the balance of accuracy and interpretability in predictive modeling.

 
 

\newpage
\small\textcolor{blue}{}
%\subsubsection*{References}
\vskip 0.2in
\bibliography{reference}
\bibliographystyle{plain}


















\end{document}

nips2014CameraReady.bbl
\begin{thebibliography}{10}

\bibitem{aamodt1991knowledge}
A.~Aamodt.
\newblock A knowledge-intensive, integrated approach to problem solving and
  sustained learning.
\newblock {\em Knowledge Engineering and Image Processing Group. University of
  Trondheim}, pages 27--85, 1991.

\bibitem{aamodt1994case}
A.~Aamodt and E.~Plaza.
\newblock Case-based reasoning: Foundational issues, methodological variations,
  and system approaches.
\newblock {\em AI communications}, 1994.

\bibitem{baehrens2010explain}
D.~Baehrens, T.~Schroeter, S.~Harmeling, M.~Kawanabe, K.~Hansen, and K.R.
  M{\"u}ller.
\newblock How to explain individual classification decisions.
\newblock {\em JMLR}, 2010.

\bibitem{bichindaritz2006case}
I.~Bichindaritz and C.~Marling.
\newblock Case-based reasoning in the health sciences: What's next?
\newblock {\em AI in medicine}, 2006.

\bibitem{bien2011prototype}
J.~Bien, R.~Tibshirani, et~al.
\newblock Prototype selection for interpretable classification.
\newblock {\em AOAS}, 2011.

\bibitem{blei2003latent}
D.M. Blei, A.Y. Ng, and M.I. Jordan.
\newblock Latent dirichlet allocation.
\newblock {\em JMLR}, 2003.

\bibitem{carroll1980analyzing}
J.S. Carroll.
\newblock Analyzing decision behavior: The magician's audience.
\newblock {\em Cognitive processes in choice and decision behavior}, 1980.

\bibitem{chang2009reading}
J.~Chang, J.L. Boyd-Graber, S.~Gerrish, C.~Wang, and D.M. Blei.
\newblock Reading tea leaves: How humans interpret topic models.
\newblock In {\em NIPS}, 2009.

\bibitem{cohen1996metarecognition}
M.S. Cohen, J.T. Freeman, and S.~Wolf.
\newblock Metarecognition in time-stressed decision making: Recognizing,
  critiquing, and correcting.
\newblock {\em Human Factors}, 1996.

\bibitem{cover1967nearest}
T.~Cover and P.~Hart.
\newblock Nearest neighbor pattern classification.
\newblock {\em Information Theory}, 1967.

\bibitem{cunningham2003evaluation}
P.~Cunningham, D.~Doyle, and J.~Loughrey.
\newblock An evaluation of the usefulness of case-based explanation.
\newblock In {\em CBRRD}. Springer, 2003.

\bibitem{de2000classification}
G.~De'ath and K.E. Fabricius.
\newblock Classification and regression trees: a powerful yet simple technique
  for ecological data analysis.
\newblock {\em Ecology}, 2000.

\bibitem{eisenstein2011sparse}
J.~Eisenstein, A.~Ahmed, and E.~Xing.
\newblock Sparse additive generative models of text.
\newblock In {\em ICML}, 2011.

\bibitem{freitas2014comprehensible}
A.~Freitas.
\newblock Comprehensible classification models: a position paper.
\newblock {\em ACM SIGKDD Explorations}, 2014.

\bibitem{GohRu14}
S.~Goh and C.~Rudin.
\newblock Box drawings for learning with imbalanced data.
\newblock In {\em KDD}, 2014.

\bibitem{graf2009prototype}
A.~Graf, O.~Bousquet, G.~R{\"a}tsch, and B.~Sch{\"o}lkopf.
\newblock Prototype classification: Insights from machine learning.
\newblock {\em Neural computation}, 2009.

\bibitem{griffiths2004finding}
T.L. Griffiths and M.~Steyvers.
\newblock Finding scientific topics.
\newblock {\em PNAS}, 2004.

\bibitem{hofmann1999probabilistic}
T.~Hofmann.
\newblock Probabilistic latent semantic indexing.
\newblock In {\em ACM SIGIR}, 1999.

\bibitem{hull1994database}
J.J. Hull.
\newblock A database for handwritten text recognition research.
\newblock {\em TPAMI}, 1994.

\bibitem{huysmans2011empirical}
J.~Huysmans, K.~Dejaeger, C.~Mues, J.~Vanthienen, and B.~Baesens.
\newblock An empirical evaluation of the comprehensibility of decision table,
  tree and rule based predictive models.
\newblock {\em DSS}, 2011.

\bibitem{klein1989decision}
G.A. Klein.
\newblock Do decision biases explain too much.
\newblock {\em HFES}, 1989.

\bibitem{Lang95}
K.~Lang.
\newblock Newsweeder: Learning to filter netnews.
\newblock In {\em ICML}, 1995.

\bibitem{LethamRuMcMa14}
B.~Letham, C.~Rudin, T.~McCormick, and D.~Madigan.
\newblock Interpretable classifiers using rules and {B}ayesian analysis.
\newblock Technical report, University of Washington, 2014.

\bibitem{li2008ranking}
H.~Li and J.~Sun.
\newblock Ranking-order case-based reasoning for financial distress prediction.
\newblock {\em KBSI}, 2008.

\bibitem{murdock2003assessing}
J.W. Murdock, D.W. Aha, and L.A. Breslow.
\newblock Assessing elaborated hypotheses: An interpretive case-based reasoning
  approach.
\newblock In {\em ICCBR}. Springer, 2003.

\bibitem{newell1972human}
A.~Newell and H.A. Simon.
\newblock {\em Human problem solving}.
\newblock Prentice-Hall Englewood Cliffs, 1972.

\bibitem{phan2013gibbslda}
X.~Phan and C.~Nguyen.
\newblock Gibbs{LDA}++, {AC/C}++ implementation of latent dirichlet allocation
  using gibbs sampling for parameter estimation and inference, 2013.

\bibitem{slade1991case}
S.~Slade.
\newblock Case-based reasoning: A research paradigm.
\newblock {\em AI magazine}, 1991.

\bibitem{sormo2005explanation}
F.~S{\o}rmo, J.~Cassens, and A.~Aamodt.
\newblock Explanation in case-based reasoning--perspectives and goals.
\newblock {\em AI Review}, 2005.

\bibitem{tibshirani1996regression}
R.~Tibshirani.
\newblock Regression shrinkage and selection via the lasso.
\newblock {\em JRSS}, 1996.

\bibitem{UstunRu14}
B.~Ustun and C.~Rudin.
\newblock Methods and models for interpretable linear classification.
\newblock {\em ArXiv}, 2014.

\bibitem{williamson2010ibp}
S.~Williamson, C.~Wang, K.~Heller, and D.~Blei.
\newblock The {IBP} compound dirichlet process and its application to focused
  topic modeling.
\newblock 2010.

\bibitem{zhu2012medlda}
J.~Zhu, A.~Ahmed, and E.P. Xing.
\newblock Med{LDA}: maximum margin supervised topic models.
\newblock {\em JMLR}, 2012.

\end{thebibliography}
