Multi-instance learning (MIL) is a sub-area of machine learning in which training and testing data are organized in sets called bags. What makes MIL challenging is that labels associated with these data are frequently provided at the baglevel, but not the instance-level. This is also known as weakly supervised learning in the literature. Algorithms that adhere to this type of weakly supervised learning paradigm are naturally suited to a wide variety of real world problems that contain limited labeled data. For example, images can be represented
Positive Instances
Positive Bags
Fig. 1. An illustrative comparison of the single instance and multi-instance learning paradigms. Algorithms that operate on multi-instance data must contend with the fact that instances are rarely individually-labeled. Instead, labels are generally provided at the bag-level. Thus, the goal of a multiinstance learning algorithm is to learn to identify instances, within a given bag, that indicate a particular class membership.
by a bag of patches, documents can be organized into sentences, patients can be represented by a collection of medical records, to name a few. However, since each bag can have an arbitrary number of instances, standard machine learning approaches that rely on fixed-length vector representations cannot be applied to the data directly. Significant research efforts have been made to design algorithms that can handle this type of data.
In the past twenty years, a large number of MIL algorithms [1]- [8] have been proposed. These approaches have been applied to many different topics ranging from drug activity prediction [9], content-based image retrieval [10], medical image analysis [11], document classification [12], among many other application areas [13]. Recently, deep learning-based MIL methods [14]- [16] have also been proposed to handle multi-instance data. While these methods have demonstrated their effectiveness in solving a variety of real-world problems by multi-instance learning, their limitations have also been discussed in literature [17], [18]. For example, a recent survey paper [18] notes that current state-of-the-art MIL approaches are sensitive to the construction of instances within a bag. Specifically, they determine that the performance of MIL methods are sensitive to witness rate, e.g., the proportion of positive instances in positive bags, as well as whether the algorithm operates on the instance or bag level. This has also been observed in older MIL survey papers [17] and requires that new algorithms be tested on a range of different datasets and applications. In addition to dataset-specific performance, the authors of these survey papers highlight that performance improvements in the training time of MIL algorithms, especially those that rely on instance-level information, are necessary for further adoption.
In this work, we focus specifically on scaling SVM-based MIL algorithms, as they have shown consistent performance and can be further extended to non-linear decision boundaries via the kernel trick. Popular SVM-based MIL approaches such as miSVM/MISVM [1], NSK [19], and sMIL/sbMIL [2] have been proposed to handle multi-instance data and have demonstrated promising performance, even when compared against modern MIL deep-learning architectures such as miNet/MINet [20]. While these approaches have performed well, and can be extended to solve a variety of real-world problems, they are not widely used in practice as they do not scale well to large datasets. Furthermore, many of these approaches are not equipped with capabilities to interpret the results of their predictions. These two shortcomings, speed of model training and model interpretability of multi-instance learning methods, are the focus of this work.
For the remainder of this manuscript we present a novel method that extends a multi-instance SVM to large scale data. Our approach uses the multi-block alternating direction method of multipliers (ADMM) to avoid iteratively solving the quadratic programming problems that arise from standard SVM-based MIL approaches. The scientific contributions of this work are as follows: -A novel MIL algorithm derivation, named the Primal-Dual Multi-Instance SVM (pdMISVM) method, and an associated implementation that scales linearly as the number of bags increases. -An inexact variation of our approach, based on the optimal line search method, that scales linearly as the number of features increases. -Experimental results showcasing the promising predictive performance, scalability, and interpretability of our approach on baseline multi-instance data and real-world image data compared against other MIL algorithms. -An extension of our approach that allows for the inclusion of an arbitrary kernel function and a proof-of-concept experiment on synthetic data verifying our derivation.
In this section we begin with a sketch for the steps required for the standard multi-instance SVM (MISVM) derivation initially presented by Andrews et al. [1]. Then, following the multi-block ADMM framework [21]- [23], we construct the augmented Lagrangian which will be used to derive the solution to the proposed pdMISVM method; this is followed by a step-by-step derivation to optimize the proposed objective. Finally, we extend our approach to handle a large number of features through an application of the optimal line search method [24].
In this manuscript we represent matrices as M, vectors as m, and scalars as m. The i-th row and j-th column of M are m i and m j , respectively. Similarly, m i j is the scalar value indexed by the i-th row and j-th column of M. The matrix M p corresponds to the p-th column-block of M. Given a K × N matrix M, {m, i} = arg max m ,i (M) gives the rowby-column coordinates for the maximum element in M. The row and column indices are given by arg max m ,i (M) m and arg max m ,i (M) i , respectively.
In the binary multi-instance classification problem, the MIL algorithm is presented with a collection of bags and labels represented by the set {X i , y i } : i ∈ 1, . . . , N where y i ∈ {-1, 1}, X i ∈ R d×ni designates a bag containing n i instances, and {x 1 , . . . , x ni } ∈ X i represent each instance within the i-th bag. Following the instance-centric approach advocated by Andrew's et al. [1] MISVM model, where a single "witness" instance determines the class of a bag, we define the decision function for a multi-instance binary classifier as
where w, b are the hyperplane and intercept for the MISVM.
The MISVM objective devised by Andrews et al. is
where C is a hyperparameter that determines the level of regularization on the learned hyperplane and ξ i are slack variables. The constraints in Eq. ( 2) are incorporated via a Lagrangian function
and is solved with respect to the dual variables (α i ) using off-the-shelf quadratic programming solvers or heuristic algorithms like sequential minimal optimization [25] which takes advantage of a limited number of support vectors. Although the MISVM formulation from Andrews et al. is widely used in MIL literature, it is generally limited to binary classification problems.
In order to design a method suitable for multi-class multiinstance classification, we extend the decision function presented in Eq. (1) to K-classes via ŷi = arg max m ,i
where W ∈ R d×K , b ∈ R K , ŷi ∈ {1, . . . , K} represents the hyperplanes, intercepts, and labels for K classes. Motivated by the results of [26] where it is argued that all-in-one formulations for K-class SVMs provide superior predictive performance, when compared to one-vs-all approaches, we construct the following Weston & Watkins [27] MISVM extension to Eq. ( 2)
where w y , b y is the hyperplane-intercept pair associated with the i-th bag's class label, (•) + = max(0, •) is the hinge loss function, and y m i ∈ {-1, 1} indicates if the i-th bag belongs to the m-th class. Similar to Eq. ( 2), the K-class formulation above can be transformed into a quadratic programming problem and solved. Although, this approach is known [26] not to scale well as the number of bags increases. To address this issue we propose a novel primal-dual algorithm based on the multi-block ADMM [23] to optimize Eq. (5).
Incorporating the constraints of Eq. ( 5) into the objective gives the unconstrained optimization
which is difficult to solve given the coupling across w k , b m , and the max(•) operations. Following the multi-block ADMM approach we introduce the following constraints, inspired by [24], [28], and rewrite Eq. ( 6) as
to decouple the primal variables. Then, the augmented Lagrangian function of Eq. ( 7) is
where W, b, E, Q, T, R, U are the primal variables, Λ, Σ, Θ, Ω, Ξ are the dual variables, and μ > 0 is a tuning parameter. Equation ( 8) is then differentiated with respect to each primal variable to derive Algorithm 1. The primal-dual updates terminate when the total difference between the constraints incorporated via the augmented Lagrangian terms are less than a predefined tolerance.
W & b update. Removing all terms from Eq. ( 8) that do not include W and decoupling across columns of W gives the following K problems
where i indicates the column blocks in X (and the corresponding columns of U and Ξ) that belong to the m-th class and N is the total number of bags belonging to the m-th class. Taking the derivative of Eq. ( 9) with respect to w m and setting the result equal to zero gives the closed form solution
which can be calculated via a least-squares solver to avoid an inverse calculation. Similarly, differentiating Eq. ( 9) elementwise with respect to b m , setting the result equal to zero, gives the update
E update. Dropping terms from Eq. ( 8), that do not contain E and decoupling element-wise gives K × N problems
where 12) can be differentiated with respect to e m i via the sub-gradient method, and solved in three cases
Q & R update. Keeping only terms with Q in Eq. ( 8) and decoupling element-wise gives K × N problems
Taking the derivative of Eq. ( 14) with respect to q m i , setting the result equal to zero, and solving for q m i gives the update
Following the same steps for each r m i ∈ R we derive the element-wise updates
T & U update. Keeping terms in Eq. ( 8) containing T and decoupling across K and N gives the following
which can be further decoupled element-wise for each
Taking the derivative of Eq. ( 18) with respect to t m i,j , setting the result equal to zero, and solving for t m i,j , gives the updates
This same strategy is applied to derive the element-wise updates of U, giving
where
The associated dual variable updates are provided in Algorithm 1.
Although the updates derived in Section II-C provide a suitable algorithm as the number of bags increase, the leastsquares solver used to update W in Eq. ( 10) has computational complexity 2 and scales quadratically as the number of features increase; this limits the scalability of our approach to bags only. Additionally, since μ is updated every iteration, the least-squares solver must be invoked at every iteration. To handle this issue, we propose an alternative optimal line search method [24] to update W instead. W Update, inexact. The partial derivative of Eq. ( 9) with respect to w k gives
which can be used to create the minimization
in terms of s m instead of w m . Differentiating Eq. ( 22) with respect to s m , setting the result equal to zero, and solving for s m gives
Recognizing that the denominator of Eq. ( 23) is equivalent to
allows for Eq. ( 23) to be calculated efficiently in
Combining, Eq. ( 21) and Eq. ( 23) can then be used to update w m via
This "inexact" update option avoids solving the least squares problem present in Eq. (10) and is provided as an option on Line 6 of Algorithm 1 to extend our method to handle a large number of features.
In this section we explore the performance of our exact and inexact pdMISVM implementations. We first test our method against an array of standard MIL benchmarks to explore how our implementations compare against other MIL methods. Algorithm 1 The pdMISVM method to optimize Eq. ( 8) Update wm ∈ W by Eq. ( 10), or Eq. ( 25) inexact Update e m p ∈ E by Eq. (
Update q m p ∈ Q by Eq. ( 15)
12:
Update r m p ∈ R by Eq. ( 16)
13:
for j ∈ np do 14:
Update t m p,j ∈ T by Eq. (
Update u m p,j ∈ U by Eq. (
end for 17:
y Xi + 1by)).
end for
Update μ = ρμ 20: end while 21: return (wm, . . . , wK ) ∈ W and (b1, . . . , bK ) ∈ b.
We follow the baseline experiments with an investigation into increasingly complex natural scene data to determine the performance characteristics of our approach. Then, we conduct experiments with synthetic data to illustrate the scalability of our approach and experimentally verify the expected computational complexity/performance characteristics of our approach compared to others. We follow with a discussion of the interpretability of our method on three multi-instance datasets derived from two well-known baseline datasets. Finally, we present an extension of our primal-dual derivation to handle arbitrary kernel functions. We experimentally verify this extended derivation on synthetic data and identify a limitation of our approach to be addressed in future work.
We compare our method against eight MIL learning algorithms: (1) a single-instance learning (SIL) approach that assigns the bags' labels to all instances during training and returns the maximum response for each bag/class-pair at test time for the testing bags' instances; (2) the miSVM and (3) MISVM algorithms [1] that assume that at least one instance per bag is positive to classify a bag as positive; (4) the NSK algorithm [19], a bag-based method, that maps the entire bag to a single-instance by way of a kernel function; (5) the sMIL and ( 6) sbMIL [2] algorithms which expect that only a small number of instances within a bag are classified as positive and combine instance-level and bag-level relationships to make a prediction. We also compare our approach against two end-toend MIL algorithms, (7) miNet and ( 8) MINet [20], based on deep neural-network (DNN) architectures.
These methods are compared against the proposed pdMISVM (Ours) method, and the inexact variation, described in Algorithm 1. The grid search and performance calculations for each method-dataset pair are conducted using the MLJ library [29] and are included with our code. 1 All experiments were run on an Intel Xeon processor running at 2.20GHz using 126GB of RAM, running Ubuntu 18.04.4 LTS. The competing SVM-based methods are implemented using a libraryfoot_1 written by Doran et al. [30] while the DNN methods are implemented using the codefoot_2 provided as a companion to the paper by Wang et al. [20]. Methods that take longer than one-thousand seconds to train during a single cross-validation are considered "timed-out" (T/O) and their performance metrics are not provided.
Each method is compared against a synthetic dataset and ten multi-instance datasets that are normalized to have zero mean and unit variance. The synthetic dataset contains 10 to 1,000 bags with three to five instances per bag and 10 to 1,000 features per instance. The first instance per bag is constructed from two normally-distributed clusters with a standard deviation of one; the second to fifth instances per bag contain uniform random noise.
The MUSK-2 [9], Elephant, Fox, and Tiger [1] datasets are standard small scale MIL evaluation datasets and are widely cited in the MIL literature. The MUSK-2 dataset is designed to classify chemical compounds as either "musk" or "non- musk" which describes the chemical properties of a given compound; bags within this dataset are representative of the possible conformations of the labeled compound. The MUSK-2 dataset contains 39 positive and 63 negative bags with 166 features per instance. The Elephant, Fox and Tiger datasets are derived from the Corel image dataset [31] and each contain 100 positive and 100 negative bags with 143 non-zero features per instance.
The MNIST-bags [15] dataset contains 100 positive and 100 negative bags where a bag is made up of a random number of 28 × 28 greyscale images taken from the MNIST dataset. A bag is given a positive label if it contains a '9' and negative label if it does not. For our experiments the average number of bags is ten, thus the witness rate for positive bags is 10%, on average. This low witness rate makes this a challenging dataset for the chosen MIL algorithms.
The SIVAL dataset was specifically designed for contentbased image retrieval (CBIR) and contains natural scene images consisting of 25 categories with 60 images per category Fig. 3. Confusion matrix of the inexact pdMISVM approach tested on the SIVAL-25-deep dataset created from the patch-wise application of a convolutional neural network as a pre-processing step. Results are derived from a six-fold cross-validation experiment across all 1,463 bags.
for a total of 1,500 bags. In this work we use the processed dataset provided in the initial work of Rahmani et al. [32] and create a novel dataset derived from the raw SIVAL images. In the original processed SIVAL dataset, the images are segmented into 30 or 31 instances, depending on the picture, consisting of 30 features each. In total there are 47,414 instances across the entire SIVAL dataset. In order to explore the prediction and runtime performance of the compared methods, we construct a few subsets of this dataset containing a predetermined number of classes. Specifically, we construct the SIVAL-3, SIVAL-5, SIVAL-10, and SIVAL-25 datasets each containing three, five, ten, and twenty-five classes from the SIVAL dataset, respectively.
In addition, we construct the "SIVAL-25-deep" dataset, which is inspired by the "hybrid" approach detailed by Zheng et al. [33] which investigates the ongoing shift from SIFT-based descriptors [34] to convolutional neural networks for generating image descriptors. To create this multi-instance dataset we extract patches from the raw Fig. 4. Time to train our method and other MIL methods on synthetic multiinstance data where the number of bags increase. Both the exact and inexact end up training faster than the competing methods once the number of synthetic bags is greater than eight-hundred.
SIVAL images using the proposal generator (eta=0.2, minScore=0.04, maxBoxes=200) provided in the OpenCV library. 4 These patches are fed a pre-trained AlexNet [36] convolutional neural network where the second to last fully-connected layer (F10) is used to represent each instance by 4,096 features. We note that more complex/newer deep neural architectures, and other proposal generators, could be used to create this patch-level embedding but leave this to future work. This process is repeated for every image (where object proposals are detected by EdgeBox) and results in 1,463 bags for a total of 80,561 instances. The SIVAL-25-deep dataset is our attempt at a modernization of the standard SIVAL dataset; the pipeline used to generate this benchmark is provided with our code.
In Tables I and II we provide the classification performance of our approach compared against the other MIL algorithms. Our goal is to verify that our approach matches the performance of the other MIL algorithms. For each datasetmethod pair we report the accuracy (ACC) and balanced accuracy (BACC) results across ten six-fold cross validation experiments. We can see from Table I that our method gives comparable performance on the MUSK-2, Elephant, and Tiger datasets; this applies for both the exact and inexact implementations. Interestingly, the inexact implementation of our approach outperforms all other methods on both the Fox and MNIST-Bags datasets. In Table II the exact method only slightly outperforms the next best performing method on the SIVAL-3 dataset; this impressive performance result does not hold for the inexact version. Although, the inexact method performs better (in comparison) when the number of classes/bags increase. The inexact method shows surprisingly impressive results on SIVAL-25-deep dataset which are recorded just within the time-budget; this significant performance improvement can be seen very clearly in the comparison between the Fig. 5. Elapsed time to train the exact and inexact methods on synthetic multi-instance data as the number of features is varied. As expected, the exact approach performs poorly as the number of features increases but the inexact method continues to scale linearly. confusion matrices in Figures 2 and3. It's clear from these results that both the exact and inexact methods are capable of providing competitive performance results on a variety of multi-instance datasets.
The key contribution of this work is that the derived algorithms described in Section II-C and Section II-D scale to large datasets. This can clearly be seen in the SIVAL-25 column of Table II where our methods are the only ones that are able to fit a model within one-thousand seconds. In order to further validate this finding, in Figure 4 we report training time results on a synthetic multi-instance dataset where we increase the number of bags as described in Section III-A. Our approach scales well with respect to the number of bags which illustrates the importance of our primal-dual derivation. This conclusion is especially clear when our method is compared against SVM-based MIL methods which rely on repeatedly solving quadratic programming problems.
Although the initial pdMISVM derivation scales well with respect to bags, it does not scale to the number of features when it is large. This is due to the fact that the update for each w k in Eq. ( 10) requires solving a least squares problem which scales quadratically as the number of features increase. To address this limitation, we proposed an optimal line search method to improve the scalability of our approach in Eq. ( 25). We conduct a timing experiment between the exact and inexact methods using synthetic data where the number of features are increased to see if our inexact variation provides improved runtime performance. We can see in Figure 5 that the proposed inexact method significantly reduces the training time of our approach as the number of features increase.
In addition to the promising predictive performance and scalability of our method, we note that instance-based methods such as ours come with an additional benefit: interpretability. Instance-based methods such as miSVM, MISVM, and the Fig. 6. Learned class-specific hyperplanes of the pdMISVM method on the MNIST-bags dataset plotted in a 28 × 28 grid. Left: Learned coefficients for predicting whether a bag contains the MNIST handwritten digit '9'. Right: The learned coefficients for predicting whether a bag does not contain the MNIST digit '9'. Fig. 7. Instance identification results on the first five testing bags of our method on the MNIST-bags dataset with the detectors in Figure 6. Our approach correctly classifies the first, second and third bags. Although the first bag is classified correctly the "9"s are not properly identified.
proposed pdMISVM method, identify an explicit instance within a bag that is responsible for the predicted label. We use this phenomenon to explore the limitations of our method on the MNIST-bags dataset and showcase patches identified during the SIVAL experiment across a number of different classes.
For the MNIST-bags dataset we plot the learned positive and negative class coefficients associated with the two learned hyperplanes in Figure 6 (e.g. w 1 and w 2 ). In addition, we plot four randomly chosen testing bags and what instance was chosen by the multi-instance decision function for the positive class hyperplane in Figure 7. On the left-hand side of Figure 6, we can see that our method can roughly detect the loop at the top of the '9' although it is clear from this interpretation that the our approach will not be able to handle even moderate translation or rotation if it is only provided with raw-pixel values. Additionally, even though our method correctly classifies the first bag, it incorrectly identifies the '4' as the witness instance; we can see that a '4' appears to be contaminating the learned coefficients displayed in Figure 6. In order to solve this problem it is likely that additional preprocessing will be required to extract more descriptive features from instances within the MNIST-bags dataset beyond raw pixels for our method to be effective.
In order to illustrate how effective feature extraction can aid in the interpretability of our method, we extend our discussion to the SIVAL-25 and SIVAL-25-deep datasets. In Figure 8, we provide image patches identified by our approach on images chosen from the SIVAL-25 dataset. We can see that our method identifies distinctive visual characteristics in each of the classes. For example, the bag representing a "Banana" is identified by a distinctive patch along the length of the fruit while in the "Apple" image our approach identifies the round patch on top of the fruit. Similarly, in Figure 9 we present the neural-network embedded patches extracted via the EdgeBox detection algorithm and the identified patches. We can clearly see in Figure 9 that our approach is able to accurately localize the most distinctive parts of the object, at the patch-level, within the image. For example, the medal is recognized by the "gold" part while the "bowl" of the spoon is recognized.
Remarkably, the results in Figures 8 and9 show that when our method is given a set of sufficiently descriptive object proposals/patches, paired with a bag-level label, our method can accurately locate objects within an image. This is one of the significant advantages of instance-based MIL methods over traditional single-instance learning methods that require all instances to be labeled. We anticipate that this framework could be extended to investigate and interpret the effectiveness of pre-trained neural networks on an assortment of datasets that can be formulated as MIL problems. We plan to further investigate different aspects of our approach under different Fig. 9. Instance identification on the SIVAL-25-deep dataset across different classes. In each set of three pictures the leftmost is the original image, the middle shows the bag of patches extracted by the EdgeBox detector [35], and the final image highlights the patch identified by our approach for classifying the image. object proposal methods [37], [38], neural architectures [39], and applications [12], [13], [40].
Although the proposed pdMISVM formulation and implementations are shown to work well on a variety of MIL datasets, they are limited to classifying data that is linearly separable. In order for our method to be able to handle nonlinear decision boundaries, it requires the addition of a kernel. To this end, we briefly sketch out a kernel extension to the W variable update proposed in Section II-C. We verify this addition in an experiment with synthetic data that can only be correctly classified by a nonlinear method. W update (with kernel) Starting with Eq. ( 9) and replacing all columns of X i with feature vectors calculated by an arbitrary kernel function φ(X i ) = Φ i , taking its derivative with respect to w m , and solving for w m gives Since the kernel function applied to each X i may return feature vectors that are infinitely long, it may be impossible to calculate the inverse required to express w m in Eq. (27). In order to solve this issue we use the following trick [41] (P -1 + m T R -1 m) -1 m T R -1 = Pm T (mPm T + R) -1 to rewrite w T m equivalently, as
The updated w m in Eq. ( 28) can then be used to update w T m φ(X i ) and w m 2 2 = tr w T m w m directly, as the kernel function occurs as an inner product in both cases and can be computed. We implement the kernel version of the pdMISVM method and compare it against the linear version in Figure 10; we can see this extension successfully extends our approach to correctly classify data that is not linearly separable. Unfortunately, the update in Eq. ( 28) is computationally expensive as it requires a least squares calculation that scales quadratically with respect to the total number of bags in the training dataset. We plan to address this limitation in our future work.
In this work we propose a Primal-Dual Multi-Instance SVM method that is able to scale to large multi-instance datasets. Our SVM-based approach is able to handle data that grows in terms of bags as well as features since it avoids solving a quadratic programming problem that limits the adoption of traditional SVM-based MIL techniques. Throughout the manuscript, we provide detailed derivations, implementations, and experimental results which illustrate the utility of our approach on both synthetic and real-world datasets. In addition, we provide analyses that investigate the interpretability of our method on benchmark multi-instance datasets and develop an extension to the SIVAL dataset as part of this study. Finally, using the same primal-dual framework, we derive and implement a kernel extension of our approach that is able to learn non-linear decision boundaries on synthetic multiinstance data and identify areas for future work.
https://github.com/minds-mines/pdMISVM.jl
https://github.com/garydoranjr/misvm
https://github.com/yanyongluan/MINNs
https://github.com/opencv/opencv