Optimal Margin Distribution Machine for Multi-Instance Learning

1 Introduction

Multi-instance learning (MIL) is a celebrated learning framework [Foulds and Frank, 2010; Amores, 2013; Herrera et al., 2016] where each example is represented as a collection (bag) of feature vectors (instances). A bag is negative if it has no positive instances, and vice versa if at least one positive instance is contained. The learner can only access the bag labels, while the instance labels are not available. Compared to the classical supervised learning where each bag just consists of one instance, MIL provides a much more natural representation and is well suited for many complicated problems. For example in drug discovery and development [Dietterich et al., 1997], one molecule (bag) could have many low-energy shapes (instances), and the model should predict whether a new molecule is qualified to make a special drug or not by learning from a set of known molecules. In content-based image retrieval (CBIR) [Zhou et al., 2005], the image (bag) is decompose into several regions (instances), and the system should retrieve all the images that are relevant to the concept queried by users. Besides the prediction of bag labels, detecting the key instance which triggers the positive bag label is a more difficult task. For the former, it is to determine which low-energy shapes are responsible for the observed biological activity. For the latter, it is to identify which regions in the image make users have interest in it.

In the past decades, various MIL algorithms have been proposed, e.g., the diverse density (DD) algorithm [Maron and Ratan, 1998] and EM-DD [Zhang and Goldman, 2001], citation-kNN and its variant [Zhou et al., 2005], MISVM [Andrews et al., 2003] and its variants [Bi et al., 2005; Li et al., 2009], among which, the large margin based methods have always been popular. More specifically, MI-SVM starts with a SVM using some multi-instance kernel [G¨artner et al., 2002] and identifies the key instances according to the decision values, after that retrains the SVM model based on the new key instance assignments (bag labels). The convergence of this procedure can be easily guaranteed once it is viewed as a specialization of the constrained concave-convex programming (CCCP) method. Although in each iteration, MI-SVM only solves a SVM-like convex optimization, the whole problem is still non-convex and thus it may get stuck in the local minima. On the other hand, the KI-SVM overcomes this difficulty by relaxing the mixed-integer programming as a convex optimization by minimax saddle point theory. It applies the cutting-plane method for optimization by generating a violated key instance assignment (kernel) to the constraint set in each iteration.

Aforementioned methods are based on the large margin principle, i.e., maximizing the minimal distance from the instances to the decision hyperplane. Recently, the studies on margin theory [Gao and Zhou, 2013] show that margin distribution is of more importance to generalization ability than minimal margin, which gives rise to the optimal margin distribution learning ([Zhang and Zhou, 2019]). Due to the superiority to the traditional large margin based methods, this new learning paradigm has quickly attracted a lot of attentions and been extended to many learning settings ([Zhang and Zhou, 2018a; Zhang and Zhou, 2018b; Tan et al., 2020]). These great successes suggest that the existing large margin based MIL algorithms still have enough room for enhancement.

Based on this recognition, we propose the multi-instance optimal margin distribution machine (MI-ODM). It can identify the key instance via explicitly optimizing the margin distribution. Specifically, we characterize the margin distribution by its first- and second-order statistics, i.e., the margin mean and margin variance. As suggested in [Gao and Zhou, 2013], we maximize the former and minimize the latter simultaneously. To solve the resultant minimax saddle point problem, we extend a stochastic accelerated mirror prox method which enjoys the optimal convergence rate. Extensive experiments verify the superiority of the proposed method.

The rest of the paper is organized as follows. We first introduce some preliminaries, and then present the proposed MI-ODM. After that we detail the optimization techniques, followed by the experimental results and empirical observations. Finally we conclude the paper with future work.

2 Preliminaries

For convenience, we first make some notation conventions. Throughout the paper, we denote scalars with lower case letters (e.g., y), and vectors with bold face letters (e.g., x). Sets are designated by upper case letters with mathcal font (e.g., S). Let X ⊆ Rn and Y = {1,-1} denote the input and output spaces, respectively. For any m ≥ 1, the set of integers {1, . . . ,m} is denoted by [m]. The feature mapping associated to some positive definite kernel κ is denoted by φ : X ↦→H.

2.1 ODM

The margin γ(x, y) of a labeled instance (x, y) is defined as the signed decision value, i.e., γ(x, y) = yw⊤φ(x). 1 This value can be viewed as the confidence (or safety) of the prediction. The larger the margin, the more confidence we have on the predicted label, and (x, y) is misclassified if and only if it produces a negative margin.

It is well known that SVMs employ the large margin principle to pick the decision boundary [Cristianini and ShaweTaylor, 2000]. As a result, the obtained separating hyperplane just consists of a small amount of instances, a.k.a. the support vectors (SVs), and the rest instances are totally ignored. When noisy instances exist, the learner may be misled and produce a suboptimal decision boundary [Zhou, 2014].

As a counterpart, optimizing the margin distribution is a more robust strategy by exploiting the whole data set and preventing from being cheated by the noisy instances. As for how to characterize the margin distribution, a straightforward way is through the first- and second- statistics, i.e., the margin mean and variance. Moreover, as suggested in [Gao and Zhou, 2013], maximizing the former and minimizing the latter simultaneously can yield a tighter generalization bound, the optimal margin distribution machine (ODM) is initially formulated as:

where η and λ are the parameters for trading-off the regularization, and ¯ γ is the margin mean. Note that ξi and ϵi are deviations of γ(xi, yi) from the margin mean, thus the last term ∑i∈[m] (ξ 2 i + ϵ2i )/m is exactly the margin variance.

1 Often an offset term b is included, but as this can be implemented by augmenting each x with an additional element whose value is always one, we do not explicitly include it here.

To make the model more clean and powerful, ODM further introduces three modifications to Eqn. (1). First is simplifying the formulation by fixing the margin mean as one. 2 Second is assigning different weights to different deviations respectively. Third is tolerating the deviation smaller than the given threshold θ to achieve a sparse solution. Therefore, the final formulation of ODM is:

where ν is the weight for trading-off different deviations, and (1 - θ)2 is to scale the second term as a surrogate loss.

3 The ProposedMethod

Given a training set of m bags S = {Bi, yi}i∈[m] where Bi = {xi,1, . . . , xi,mi } is the i-th bag, yi ∈ {±1} is the label and mi is the number of instances in bag Bi, we assume the first p bags are positive and the rest q = m- p bags are negative without loss of generality, i.e., all bags are ordered such that

The prediction of a bag is determined by the largest decision value of its instances, i.e., f(Bi) = maxj∈[mi] w⊤φ(xi,j). Substituting into Eqn. (2), we get

where λ1, λ2 are the parameters for trading-off empirical losses on positive and negative bags, respectively.

For each positive bag Bi, we introduce a binary vector

to indicate the key instance with the largest decision value. Following the traditional MIL setting, we assume that each positive bag has only one key instance, 3 and hence we have e⊤ai = 1, where e is an all-one column vector. In the following, let c = [a1; . . . ; ap] and C be its domain, then the constraints yi maxj∈[mi] w⊤φ(xi,j) ≥ 1-θ-ξi corresponding to positive bags in Eqn. (3) can be equivalently rewritten as maxai ∑j∈[mi] ai,jw⊤φ(xi,j ) ≥ 1 - θ - ξi.

2 Note that scaling w does not affect the prediction.

3 Sometimes one may want the positive bag has more than one key instances. The proposed method can be simply extended to this case by setting e⊤ai = k.

For each negative bag Bi whose instances are all negative, the corresponding constraints Eqn. (3) can be replaced by

Moreover, to make the model more relaxable, we allow the bags have different slack variables, i.e.,

where index s(i, j) = Ji-1 -Jp +j +p ranges from p+1 to Jm - Jp + p and Ji = ∑it=1 mt (J0 is set to 0). Combining all these together, Eqn. (3) turns into

As kernel methods, the inner minimization of Eqn. (4) is usually processed via the dual form due to the underlying infinite dimensional feature mapping. Introduce the dual variables u = [u1; . . . ; u2(Jm-Jp+p)] ⪰ 0, the Lagrangian of Eqn. (4) leads to

where U is the non-negative quadrant and Ki,j = Ψ⊤i Ψj ∈ Rq×q is the kernel matrix with

To overcome the difficulty caused by the mixed-integer programming, some convex relaxation methods should be applied, e.g., the semi-definite programming relaxation [Xu et al., 2004], and the minimax relaxation [Li et al., 2009]. Since the latter is proven to be tighter than the former, we also employ minimax relaxation in this paper. Interchanging the order of maxu∈U and minc∈C, we have

where D(u, c) denotes the objective function of Eqn. (5). Moreover, with an equivalent rewriting for the inner optimization, the above formulation turns to

Again introduce the dual variables v = [v1; . . . ; v|C|] ⪰ 0 for the inner optimization, the Lagrangian of Eqn. (6) leads to

Setting the derivative of d to zero, we have ∑k:ck∈C vk = 1 and the dual problem turns to

where V = {v ∈ R|C| + | e⊤v = 1} is the simplex in R|C| . For simplicity, denote ∑k:ck∈C vkD(u, ck) as G(u, v), and substitute Eqn. (7) into Eqn. (6), we have

Note that G(u, v) is a convex combination of negative definite quadratic functions, thus it is convex in v and concave in u, and according to Siont's minimax theorem [Sion, 1958], there exists a saddle point (u⋆ , v⋆ ) ∈ U × V such that

Combining with the minimax inequality

all the inequalities in Eqn. (8) hold as equations, thus the MIODM finally can be formulated as

and the optimal solution is the saddle point (u⋆ , v⋆ ).

4 Optimization

In this section, we first give a simple introduction to the minimax problem. After that, we detail the stochastic accelerated mirror prox method which can quickly find the optimal solution.

4.1 Minimax Problem

Note that G(u, ·) and -G(·, v) are both convex functions, according to the first order inequality of convexity, for any pair (ˆu, ˆ v) ∈ U × V, we have

Adding the above two inequalities together and augmenting u and v, we have

where w = [u; v] and g( ˆw) = [-∂uG( ˆw); ∂vG( ˆw)]. Compared to the general convex optimization, it can be found that g( ˆw) plays a similar role as "gradient". Since Eqn. (10) holds for any u and v, particularly we have

The LHS of Eqn. (11) can be further decomposed as two gaps between current point (ˆu, ˆ v) and saddle point (u⋆ , v⋆ ):

Since the two gaps are both non-negative, and the smaller the two gaps, the closer to the saddle point, the LHS of Eqn. (11) can be viewed as the "duality gap" in the general convex optimization and serves as a stopping criteria for the algorithm design.

4.2 Stochastic AcceleratedMirror Prox

The feasible field of u and v are box and simplex respectively. To exploit this structural information, we resort to the mirror descent method [Beck and Teboulle, 2003]. Specifically, for variable u, the common Euclidean distance mirror map ψU(u) = ‖u‖22 /2 can work well, while for variable v, the negative entropy mirror map ψV(v) = ∑k vk log vk is most suitable, since it can make the time complexity only have a logarithmic dependence on the dimension.

The mirror descent style methods perform gradient descent in the dual space induced by the mirror maps. To make the minimax structure more easily handled like the general optimization problem, we introduce the joint mirror map ψ(w) = aψU (u)+bψV (v) , where a = √2/τ √Jm - Jp + p and b = 1/√log |C|, respectively. It can be shown that ∇ψU(u) = u and ∇ψV(v) = logv + e. Combining the two components together we have ∇ψ(w) = [au; b log v + be].

As shown in Figure 1, at the t-th iteration, we first map the current point wt = [ut; vt] into the dual space ∇ψ(wt) = [aut; b log vt + be] and perform one step of gradient descent

where η is the step size, then map the ∇ψ( ˆwt) back to primal space, i.e., to find ˆwt = [ˆut; ˆ vt] such that

which implies that ˆut = ut + η∂uG(ut, vt)/a and ˆ vt = vt exp(-η∂vG(ut, vt)/b). Finally, we project [ˆut; ˆ vt] back to U × V based on the Bregman distance induced by the mirror maps. To be specific, the Euclidean distance mirror map induces the common Euclidean distance, while the negative entropy mirror map induces the Kullback-Leibler divergence. This can be formulated as the following two optimization sub-problems:

Fortunately, both two problems have a closed-form solution. The former is to project ˆut onto the non-negative quadrant, thus ut+1 = max{ˆut, 0}. For the latter, we introduce the dual variable z, and the Lagrangian leads to

Setting the derivative of v to zero, we have log(v/ˆ vt) + e + ze = 0, which implies that vt+1 = ˆ vt exp(-1 - z). Note that vt+1 belongs to a simplex, hence

Substituting with exp(-1-z) = 1/‖ˆ vt‖1, we get the closedform solution vt+1 = ˆ vt/‖ˆ vt‖1.

Once we have yt+1 ≜ [ut+1; vt+1], repeat the above procedure fromwt one more time, except that when performing gradient descent in the dual space, we use the gradient at yt+1 rather than wt. In other words, a two-step mirror descent is carried out in each iteration, which starts from the same point but the gradient used in the second time is evaluated at the ending point of the first time. This is exactly the mirror prox method [Nemirovski, 2005], which has been proved enjoying better convergence rate. Figure 2 illustrates one iteration of this method.

The mirror prox method can be further accelerated via the Nesterov accelerated technique [Nesterov, 2003]. The intuition is that besides {wt} and {yt}, we also maintain another two sequences {wt } and {wt}, which are the convex combination of {wt} and {yt}. Specifically, at the t-th iteration, first update wt = (1-γt)wt+γtyt, where γt is the Nesterov accelerated coefficient, usually set as 2/(t + 1). After that, perform two-step mirror descent based on wt to get yt+1 and wt+1. Finally, update update wt+1 = (1 - γt)wt + γtwt+1.

Moreover, to make the method scale well for big data, we also extend a stochastic version of our method, and the key problem turns to finding the unbiased noisy gradient ∂u ˜G(ut, vt) and ∂v ˜G(ut, vt). Note that G(u, v) = ∑k:ck∈C vkD(u, ck), we have

Randomly sampling an index it according to the distribution vt on {1, 2, . . . , |C|}, we can obtain ∂u ˜G(ut, vt, it) = ∂uD(ut, cit ). On the other hand, uniformly sampling an index jt from {1, 2, . . . , |C|}, we can obtain ∂v ˜G(ut, vt, jt) = [0, . . . , |C|D(ut, cjt ) . . . , 0]. Thus it can be shown that

and ˜ g(wt) = [-∂u ˜G(ut, vt, it); ∂v ˜G(ut, vt, jt)] is the targeted unbiased estimation of g(wt).

Putting the above all together, we come up with the stochastic accelerated mirror prox method for MI-ODM. Algorithm 1 summarizes the pseudo-code.

4.3 Discussion

Resorting to the monotone stochastic variational inequality technique [Juditsky et al., 2011; Chen et al., 2017], we can prove the time complexity is O(1/√ϵ + 1/ϵ + 1/ϵ2 ), where the dominated term 1/ϵ2 comes from the noise introduced by the stochastic optimization. On the other hand, the stateof-the-art cutting-plane based algorithms have the same time complexity O(1/ϵ2 ) [Zhao et al., 2008]. Further note that in each iteration, cutting-plane based algorithms need to find the most violated key instance assignment and retrain a SVM model, while our method just preforms some random samplings and two steps of gradient descent followed by a projection with closed-form solutions, therefore our method is much more efficient.

5 Empirical Studies

We empirically study our method on CBIR image data sets in Sec. 5.1 and benchmark data sets in Sec. 5.2, respectively.

5.1 Experiments on Image Data

The data set contains 500 images (bags) with resolution 160 × 160 from five categories: castle, firework, mountain,

Algorithm 1 MI-ODM

• 1: Input: ODMparameters λ1, λ2, ν, θ, maximum iteration number T , stopping criteria ζ.
• 2: Initialize u0 ← 0, v0 ← [1/|C|, . . . , 1/|C|], t ← 0, [u0; v0] ← [u0; v0], [ˆu0; ˆ v0] ← [u0; v0].
• 3: while t < T do
• 4: γt ← 2/(t +1).
• 5: [ut ; vt ] ← (1 - γt)[ut; vt] + γt[ut; vt].
• 6: Select it from {1, 2, . . . , |C|} according to vt .
• 7: ∂u ˜G← ∂uD(ut , cit ).
• 8: Uniformly select jt from {1, 2, . . . , |C|}.
• 9: ∂v ˜G← [0, . . . , |C|D(ut , cjt ) . . . , 0].
• 10: [ˆut; ˆ vt] ← [ut + η∂u ˜G/a; vt exp(-η∂v ˜G/b)].
• 11: [˜ut+1; ˜ vt+1] ← [max{ˆut, 0}; ˆ vt/‖ˆ vt‖1].
• 12: Select i′t from {1, 2, . . . , |C|} according to ˜ vt+1.
• 13: ∂u ˜G← ∂uD(˜ut+1, ci′t ).
• 14: Uniformly select j ′t from {1, 2, . . . , |C|}.
• 15: ∂v ˜G← [0, . . . , |C|D(˜ut+1, cj ′t ) . . . , 0].
• 16: [ˆut+1; ˆ vt+1] ← [ut + η∂u ˜G/a; vt exp(-η∂v ˜G/b)].
• 17: [ut+1; vt+1] ← [max{ˆut+1, 0}; ˆ vt+1/‖ˆ vt+1‖1].
• 18: [ut+1; vt+1] ← (1 - γt)[ut; vt] + γt[ut+1; vt+1].
• 19: t ← t + 1.
• 20: if duality gap smaller than the stopping criteria ζ then
• 21: Break.
• 22: end if
• 23: end while
• 24: Output: u, v.

sunset and waterfall. Each instance is a region in the image with resolution 20 × 20. Some of the regions are manually labeled as key instances. Table 1 summarizes the statistics of these data sets.

We randomly sample 50 images from each category as training data and the rest are used as test data. The training/test split are repeated for 10 times. The average accuracies as well as the standard deviations are recorded.

The proposed method is compared to the following five large margin based methods: 1) Ins-KI-SVM [Li et al., 2009]; 2) Bag-KI-SVM [Li et al., 2009]; 3) MI-SVM [Andrews et al., 2003]; 4) mi-SVM [Andrews et al., 2003]; 5) MIKernel [G¨artner et al., 2002]. The parameters C1, C2, λ1, λ2 are selected from {1, 10, 100, 1000}, and ν, θ are selected from {0.2, 0.4, 0.6, 0.8}. The RBF kernel is applied for all the methods and the width is selected from the set of {2-4 δ, 2-2 δ, 20 δ, 22 δ, 24 δ}, where δ is the reciprocal of dimension. Three classical non-large margin based methods, i.e., DD [Maron and Ratan, 1998], EM-DD [Zhang and Goldman, 2001] and CkNN-ROI [Zhou et al., 2005], which can locate key instances, are also included as baselines. All the parameters are selected by 5-fold cross validation.

Following the setting in [Li et al., 2009], we evaluate the success rate, i.e., the ratio of the number of successes divided by the total number of relevant images. Table 2 shows the results of al the compared methods. As can be seen, MIODM beats all the large margin based methods. As for the non-margin based methods, MI-ODM is also better than DD, CkNN-ROI, and highly comparable to EM-DD. Specifically, MI-ODM achieves the best performance on four categories, while EM-DD achieves the best performance on the remaining one (mountain).

5.2 Experiments on Benchmark Data

We have also evaluated our method on five benchmark data sets commonly used in the literature of MIL, i.e., Musk1, Musk2, Elephant, Fox and Tiger. Musk1 has 47 positive bags and 45 negative bags. Musk2 consists of 39 positive bags and 63 negative bags. The remaining three data sets all contains 100 positive bags and 100 negative bags. The detail of these data sets can be found in [Dietterich et al., 1997; Andrews et al., 2003].

The setting is the same with the previous experiment. We adopt the 5-fold cross validation to measure the performance. DD could not return results on some data sets in 48 hours because it lacks high efficient packages. As shown in Table 3, our method is always better or comparable, almost never worse than other baselines.

6 Conclusions

Recent studies on margin theory discloses the importance of margin distribution to generalization ability, which gives rise to a promising research direction, i.e., the optimal margin distribution learning. Based on this observation, we propose the MI-ODM, which can identify the key instance via explicitly optimizing the margin distribution. Extensive experimental results verify the superiority of the new learning paradigm. In the future, we will apply the variance reduction technique [Johnson and Zhang, 2013] to further accelerate our method and extend it to other learning settings, e.g., multi-instance multi-label learning [Zhou et al., 2012].