Multiple instance learning

The standard assumption takes each instance ${\displaystyle x\in {\mathcal {X}}}$ to have an associated label ${\displaystyle y\in \{0,1\}}$ which is hidden to the learner. The pair ${\displaystyle (x,y)}$ is called an "instance-level concept". A bag is now viewed as a multiset of instance-level concepts, and is labeled positive if at least one of its instances has a positive label, and negative if all of its instances have negative labels. Formally, let ${\displaystyle B=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}$ be a bag. The label of ${\displaystyle B}$ is then ${\displaystyle c(B)=1-\prod _{i=1}^{n}(1-y_{i})}$. Standard MI assumption is asymmetric, which means that if the positive and negative labels are reversed, the assumption has a different meaning. Because of that, when we use this assumption, we need to be clear which label should be the positive one.

Standard assumption might be viewed as too strict, and therefore in the recent years, researchers tried to relax that position, which gave rise to other more loose assumptions.[9] Reason for this is the belief that standard MI assumption is appropriate for the Musk dataset, but since MIL can be applied to numerous other problems, some different assumptions could probably be more appropriate. Guided by that idea, Weidmann [10] formulated a hierarchy of generalized instance-based assumptions for MIL. It consists of the standard MI assumption and three types of generalized MI assumptions, each more general than the last, standard ${\displaystyle \subset }$ presence-based ${\displaystyle \subset }$ threshold-based ${\displaystyle \subset }$ count-based, with the count-based assumption being the most general and the standard assumption being the least general. One would expect an algorithm which performs well under one of these assumptions to perform at least as well under the less general assumptions.

The presence-based assumption is a generalization of the standard assumption, wherein a bag must contain one or more instances that belong to a set of required instance-level concepts in order to be labeled positive. Formally, let ${\displaystyle C_{R}\subseteq {\mathcal {X}}\times {\mathcal {Y}}}$ be the set of required instance-level concepts, and let ${\displaystyle \#(B,c_{i})}$ denote the number of times the instance-level concept ${\displaystyle c_{i}}$ occurs in the bag ${\displaystyle B}$. Then ${\displaystyle c(B)=1\Leftrightarrow \#(B,c_{i})\geq 1}$ for all ${\displaystyle c_{i}\in C_{R}}$. Note that, by taking ${\displaystyle C_{R}}$ to contain only one instance-level concept, the presence-based assumption reduces to the standard assumption.

A further generalization comes with the threshold-based assumption, where each required instance-level concept must occur not only once in a bag, but some minimum (threshold) number of times in order for the bag to be labeled positive. With the notation above, to each required instance-level concept ${\displaystyle c_{i}\in C_{R}}$ is associated a threshold ${\displaystyle l_{i}\in \mathbb {N} }$. For a bag ${\displaystyle B}$, ${\displaystyle c(B)=1\Leftrightarrow \#(B,c_{i})\geq l_{i}}$ for all ${\displaystyle c_{i}\in C_{R}}$.

The count-based assumption is a final generalization which enforces both lower and upper bounds for the number of times a required concept can occur in a positively labeled bag. Each required instance-level concept ${\displaystyle c_{i}\in C_{R}}$ has a lower threshold ${\displaystyle l_{i}\in \mathbb {N} }$ and upper threshold ${\displaystyle u_{i}\in \mathbb {N} }$ with ${\displaystyle l_{i}\leq u_{i}}$. A bag ${\displaystyle B}$ is labeled according to ${\displaystyle c(B)=1\Leftrightarrow l_{i}\leq \#(B,c_{i})\leq u_{i}}$ for all ${\displaystyle c_{i}\in C_{R}}$.

Scott, Zhang, and Brown (2005) [11] describe another generalization of the standard model, which they call "generalized multiple instance learning" (GMIL). The GMIL assumption specifies a set of required instances ${\displaystyle Q\subseteq {\mathcal {X}}}$. A bag ${\displaystyle X}$ is labeled positive if it contains instances which are sufficiently close to at least ${\displaystyle r}$ of the required instances ${\displaystyle Q}$.[11] Under only this condition, the GMIL assumption is equivalent to the presence-based assumption.[7] However, Scott et al. describe a further generalization in which there is a set of attraction points ${\displaystyle Q\subseteq {\mathcal {X}}}$ and a set of repulsion points ${\displaystyle {\overline {Q}}\subseteq {\mathcal {X}}}$. A bag is labeled positive if and only if it contains instances which are sufficiently close to at least ${\displaystyle r}$ of the attraction points and are sufficiently close to at most ${\displaystyle s}$ of the repulsion points.[11] This condition is strictly more general than the presence-based, though it does not fall within the above hierarchy.

In contrast to the previous assumptions where the bags were viewed as fixed, the collective assumption views a bag ${\displaystyle B}$ as a distribution ${\displaystyle p(x|B)}$ over instances ${\displaystyle {\mathcal {X}}}$, and similarly view labels as a distribution ${\displaystyle p(y|x)}$ over instances. The goal of an algorithm operating under the collective assumption is then to model the distribution ${\displaystyle p(y|B)=\int _{\mathcal {X}}p(y|x)p(x|B)dx}$.

Since ${\displaystyle p(x|B)}$ is typically considered fixed but unknown, algorithms instead focus on computing the empirical version: ${\displaystyle {\widehat {p}}(y|B)={\frac {1}{n_{B}}}\sum _{i=1}^{n_{B}}p(y|x_{i})}$, where ${\displaystyle n_{B}}$ is the number of instances in bag ${\displaystyle B}$. Since ${\displaystyle p(y|x)}$ is also typically taken to be fixed but unknown, most collective-assumption based methods focus on learning this distribution, as in the single-instance version.[7][9]

While the collective assumption weights every instance with equal importance, Foulds extended the collective assumption to incorporate instance weights. The weighted collective assumption is then that ${\displaystyle {\widehat {p}}(y|B)={\frac {1}{w_{B}}}\sum _{i=1}^{n_{B}}w(x_{i})p(y|x_{i})}$, where ${\displaystyle w:{\mathcal {X}}\rightarrow \mathbb {R} ^{+}}$ is a weight function over instances and ${\displaystyle w_{B}=\sum _{x\in B}w(x)}$.[7]

The earliest proposed MI algorithms were a set of "iterated-discrimination" algorithms developed by Dietterich et al., and Diverse Density developed by Maron and Lozano-Pérez.[3][8] Both of these algorithms operated under the standard assumption.

Broadly, all of the iterated-discrimination algorithms consist of two phases. The first phase is to grow an axis parallel rectangle (APR) which contains at least one instance from each positive bag and no instances from any negative bags. This is done iteratively: starting from a random instance ${\displaystyle x_{1}\in B_{1}}$ in a positive bag, the APR is expanded to the smallest APR covering any instance ${\displaystyle x_{2}}$ in a new positive bag ${\displaystyle B_{2}}$. This process is repeated until the APR covers at least one instance from each positive bag. Then, each instance ${\displaystyle x_{i}}$ contained in the APR is given a "relevance", corresponding to how many negative points it excludes from the APR if removed. The algorithm then selects candidate representative instances in order of decreasing relevance, until no instance contained in a negative bag is also contained in the APR. The algorithm repeats these growth and representative selection steps until convergence, where APR size at each iteration is taken to be only along candidate representatives.

After the first phase, the APR is thought to tightly contain only the representative attributes. The second phase expands this tight APR as follows: a Gaussian distribution is centered at each attribute and a looser APR is drawn such that positive instances will fall outside the tight APR with fixed probability.[4] Though iterated discrimination techniques work well with the standard assumption, they do not generalize well to other MI assumptions.[7]

In its simplest form, Diverse Density (DD) assumes a single representative instance ${\displaystyle t^{*}}$ as the concept. This representative instance must be "dense" in that it is much closer to instances from positive bags than from negative bags, as well as "diverse" in that it is close to at least one instance from each positive bag.

Let ${\displaystyle {\mathcal {B}}^{+}=\{B_{i}^{+}\}_{1}^{m}}$ be the set of positively labeled bags and let ${\displaystyle {\mathcal {B}}^{-}=\{B_{i}^{-}\}_{1}^{n}}$ be the set of negatively labeled bags, then the best candidate for the representative instance is given by ${\displaystyle {\hat {t}}=\arg \max _{t}DD(t)}$, where the diverse density ${\displaystyle DD(t)=Pr\left(t|{\mathcal {B}}^{+},{\mathcal {B}}^{-}\right)=\arg \max _{t}\prod _{i=1}^{m}Pr\left(t|B_{i}^{+}\right)\prod _{i=1}^{n}Pr\left(t|B_{i}^{-}\right)}$ under the assumption that bags are independently distributed given the concept ${\displaystyle t^{*}}$. Letting ${\displaystyle B_{ij}}$ denote the jth instance of bag i, the noisy-or model gives:

${\displaystyle Pr(t|B_{i}^{+})=1-\prod _{j}\left(1-Pr\left(t|B_{ij}^{+}\right)\right)}$

${\displaystyle Pr(t|B_{i}^{-})=\prod _{j}\left(1-Pr\left(t|B_{ij}^{-}\right)\right)}$

${\displaystyle P(t|B_{ij})}$ is taken to be the scaled distance ${\displaystyle P(t|B_{ij})\propto \exp \left(-\sum _{k}s_{k}^{2}\left(x_{k}-(B_{ij})_{k}\right)^{2}\right)}$ where ${\displaystyle s=(s_{k})}$ is the scaling vector. This way, if every positive bag has an instance close to ${\displaystyle t}$, then ${\displaystyle Pr(t|B_{i}^{+})}$ will be high for each ${\displaystyle i}$, but if any negative bag ${\displaystyle B_{i}^{-}}$ has an instance close to ${\displaystyle t}$, ${\displaystyle Pr(t|B_{i}^{-})}$ will be low. Hence, ${\displaystyle DD(t)}$ is high only if every positive bag has an instance close to ${\displaystyle t}$ and no negative bags have an instance close to ${\displaystyle t}$. The candidate concept ${\displaystyle {\hat {t}}}$ can be obtained through gradient methods. Classification of new bags can then be done by evaluating proximity to ${\displaystyle {\hat {t}}}$.[8] Though Diverse Density was originally proposed by Maron et al. in 1998, more recent MIL algorithms use the DD framework, such as EM-DD in 2001 [12] and DD-SVM in 2004,[13] and MILES in 2006 [7]

A number of single-instance algorithms have also been adapted to a multiple-instance context under the standard assumption, including

• Support vector machines[14]
• Artificial neural networks[15]
• Decision trees[16]
• Boosting[17]

Post 2000, there was a movement away from the standard assumption and the development of algorithms designed to tackle the more general assumptions listed above.[9]

• Weidmann [10] proposes a Two-Level Classification (TLC) algorithm to learn concepts under the count-based assumption. The first step tries to learn instance-level concepts by building a decision tree from each instance in each bag of the training set. Each bag is then mapped to a feature vector based on the counts in the decision tree. In the second step, a single-instance algorithm is run on the feature vectors to learn the concept
• Scott et al. [11] proposed an algorithm, GMIL-1, to learn concepts under the GMIL assumption in 2005. GMIL-1 enumerates all axis-parallel rectangles ${\displaystyle \{R_{i}\}_{i\in I}}$ in the original space of instances, and defines a new feature space of Boolean vectors. A bag ${\displaystyle B}$ is mapped to a vector ${\displaystyle \mathbf {b} =(b_{i})_{i\in I}}$ in this new feature space, where ${\displaystyle b_{i}=1}$ if APR ${\displaystyle R_{i}}$ covers ${\displaystyle B}$, and ${\displaystyle b_{i}=0}$ otherwise. A single-instance algorithm can then be applied to learn the concept in this new feature space.

Because of the high dimensionality of the new feature space and the cost of explicitly enumerating all APRs of the original instance space, GMIL-1 is inefficient both in terms of computation and memory. GMIL-2 was developed as a refinement of GMIL-1 in an effort to improve efficiency. GMIL-2 pre-processes the instances to find a set of candidate representative instances. GMIL-2 then maps each bag to a Boolean vector, as in GMIL-1, but only considers APRs corresponding to unique subsets of the candidate representative instances. This significantly reduces the memory and computational requirements.[7]

• Xu (2003) [9] proposed several algorithms based on logistic regression and boosting methods to learn concepts under the collective assumption.

By mapping each bag to a feature vector of metadata, metadata-based algorithms allow the flexibility of using an arbitrary single-instance algorithm to perform the actual classification task. Future bags are simply mapped (embedded) into the feature space of metadata and labeled by the chosen classifier. Therefore, much of the focus for metadata-based algorithms is on what features or what type of embedding leads to effective classification. Note that some of the previously mentioned algorithms, such as TLC and GMIL could be considered metadata-based.

• One approach is to let the metadata for each bag be some set of statistics over the instances in the bag. The SimpleMI algorithm takes this approach, where the metadata of a bag is taken to be a simple summary statistic, such as the average or minimum and maximum of each instance variable taken over all instances in the bag. There are other algorithms which use more complex statistics, but SimpleMI was shown to be surprisingly competitive for a number of datasets, despite its apparent lack of complexity.[7]
• Another common approach is to consider the geometry of the bags themselves as metadata. This is the approach taken by the MIGraph and miGraph algorithms, which represent each bag as a graph whose nodes are the instances in the bag. There is an edge between two nodes if the distance (up to some metric on the instance space) between the corresponding instances is less than some threshold. Classification is done via an SVM with a graph kernel (MIGraph and miGraph only differ in their choice of kernel).[7] Similar approaches are taken by MILES [18] and MInD.[19] MILES represents a bag by its similarities to instances in the training set, while MInD represents a bag by its distances to other bags.
• A modification of k-nearest neighbors (kNN) can also be considered a metadata-based algorithm with geometric metadata, though the mapping between bags and metadata features is not explicit. However, it is necessary to specify the metric used to compute the distance between bags. Wang and Zucker (2000) [20] suggest the (maximum and minimum, respectively) Hausdorff metrics for bags ${\displaystyle A}$ and ${\displaystyle B}$:

${\displaystyle H(A,B)=\max \left\{\max _{A}\min _{B}\|a-b\|,\max _{B}\min _{A}\|a-b\|\right\}}$

${\displaystyle h_{1}(A,B)=\min _{A}\min _{B}\|a-b\|}$

They define two variations of kNN, Bayesian-kNN and citation-kNN, as adaptations of the traditional nearest-neighbor problem to the multiple-instance setting.