# A Visual Mining Approach to Improved Multiple-Instance Learning
## 4 Visual Multiple-Instance Learning
### Creating a Multiple-Instance Tree (MILTree)
Algorithm 3 contains the complete procedure to build the MILTree, which starts by grouping the matrix data \(D\) in bags \(B_{i}\) (first for loop), where \(i\) denotes the index of bags. We iterate over the instances in the matrix \(D\), each line \(D_{m}\) representing the distance from instance \(m\) to all other instances. In each iteration, a new bag \(B_{i}\) is created, and all its instances \(B_{ij}\) are added to \(B_{i}\), where \(j\) denote the index of instances belonging to some bag \(B_{i}\). Afterwards, we compute \(B_{i,protoProj}\) and \(B_{i,protoClass}\) for each \(B_{i}\) using either MILTree-SI or MILTree-Med (second for loop). Remember that \(B_{i,protoProj}\) is used in MILTree and \(B_{i,protoClass}\) in the classification process. Every \(B_{i,protoProj}\) is included in a set \(P\), which will be used later to create a bag distance matrix in the NJ tree procedure. Finally, \(B_{i}\forall i\) are processed by the MILTree using \(P\), creating the bag space projection. Instance projection: Since our MILTree has two levels, when a user interacts with a bag \(i\), the instances \(B_{ij}\) will form an instance space projection \(B_{i}.tree\). To create \(B_{i}.tree\), the NJ-Tree algorithm takes as input the instances of \(B_{i}\) and the prototype \(B_{i,protoProj}\). Figure 1: Layouts of Bag and Instance Spaces for the Corel-1000 subset (with instance prototypes highlighted) in the MILTree, with a total of 200 bags and 824 instances. ### Instance Prototype Selection Methods

We propose two new prototype selection methods, MILTree-SI and MILTree-Med, based on those proposed by [16], as described in Section 3.2. Both the SI and Med approaches compute two prototypes per bag: \(B_{ix}\) and \(B_{iy}\). The first, \(B_{ix}\), is used both in the visualization and to build the classification model, while \(B_{iy}\) is an alternative prototype that can be used to update the classification model. Computing \(B_{iy}\) offers an option to automatically change the bags' prototypes that are poorly represented by \(B_{ix}\), for example, those that are misclassified in the training set, improving the multiple-instance classification model. In contrast with the original method [16], we assume that not only positive bags but also negative bags could have both positive and negative instances. This is true for more complex data such as images and text. Consider, for example, the problem of discriminating between photos of flowers (positive) and photos of the classes person and animals (negative) in which each image is a bag and its instances are disjoint regions of the image. If we use the classic definition of a positive bag, all those images (bag) containing a flower in at least one region (instance) are considered positive; to be considered negative, the image must not contain any flower. However, in this application, we are often interested in the main object in the scene. A photo whose main subject is an animal may contain a region with a flower, for example, in the background or a person may carry a flower in a photo, although the person itself is the main object. Similar examples apply to contexts such as text, video and speech classification. Therefore, we compute both optimal positive and negative prototypes. #### 4.3.1 MILTree-SI

The optimal negative instance is defined as the one most distant from all the true positive instances of \(B^{+}\) obtained by the original Salient Instance Selection Method: \(Sal(B_{ij}^{-})\) is computed using Equation (1), then a true negative instance is obtained for each negative bag according to Equation (3). Equations (1) and (3) are reproduced again below for clarity:

\[Sal(B_{ij})=\sum_{B_{ix}\in B_{i}\backslash\left\{B_{ij}\right\}}d(B_{ij},B_{ ik})\]\[D(B_{ij},B^{-})=\min_{B_{tt}\in B^{-}}d(B_{ij},B_{tt}).\]

From all true negative instances, the optimal negative instance will be the one furthest from the set \(B^{+}\).