M3IC: Maximum Margin Multiple Instance Clustering

1 Introduction

Multiple instance learning (MIL) can be viewed as a variation of the learning methods for problems with incomplete knowledge on the examples (or instances). In the MIL setting, patterns are given as bags, and each bag consists of some instances. In a binary multiple instance classification problem, the labels are assigned to bags, rather than instances. A typical assumption for this kind of problem is that a bag should be labeled as positive if at least one of its instances is positive; and negative if all of its instances are negative. Then, using MIL methods, we can devise a classifier based on the labeled bags and predict the labels for the unlabeled ones. So far, MIL has been widely used in areas such as text mining [Andrews et al., 2003], drug design [Dietterich et al., 1998], Localized Content Based Image Retrieval (LCBIR) [Rahmani and Goldman, 2006], etc.

∗The work of Dan Zhang and Luo Si is supported by NSF research grant IIS-0746830 and the work of Fei Wang and Tao Li is partially supported by NSF grants IIS-0546280, DMS-0844513 and CCF-0830659.

As another branch of machine learning, clustering [Jain and Dubes, 1988] is one of the most fundamental research topics in both data mining and machine learning. It aims to divide data into groups of similar objects, i.e., clusters. From a machine learning perspective, what clustering does is to learn the hidden patterns of the dataset in an unsupervised way, and these patterns are usually referred to as data concepts. From a practical perspective, clustering plays an outstanding role in data mining applications such as information retrieval, text mining, Web analysis, marketing, computational biology, and many others [Han and Kamber, 2001].

However, so far, almost all of the clustering methods are designed to solve traditional single instance learning problems, while in many cases clustering can be better formulated as MIL problems. For example, in image clustering, there is natural ambiguity that as to what portion of each image contains the common concept, where the concept can be a tiger, an elephant, etc, while most portion of the image may be irrelevant. In this case, we can treat each image as a bag, where each instance in this bag corresponds to a region in this image. Then, this application requires the solution of Multiple Instance Clustering (MIC) to help users to partition these bags. Besides Image Clustering, MIC methods can also be applied to many other applications such as drug molecules clustering [Zhang and Zhou, in press] and text clustering, etc.

Recently, very limited research addresses the task of MIC. In [Zhang and Zhou, in press], the authors regard bags as atomic data items and use some distance metric to measure the distances between bags. Then they adapt the k-medoids algorithm to cluster bags. Their method is efficient in some applications. But, as claimed by [Rahmani and Goldman, 2006], defining distances between bags in an unsupervised way may not reflect their actual content differences. For example, two pictures may share identical background and only differ in that one contains a tiger and the other contains a fox. By using the minimal Hausdorff distance to measure distances between bags [Wang and Zucker, 2000], the distance between these two pictures will be very low even though their actual contents (or concepts) may differ. And the calculation of the distances between bags is quite time consuming, since it always needs to calculate all the distances between instances in different bags.

In this paper, we solve the MIC problem in a different way. We first formulate a novel Maximum Margin Multiple Instance Clustering (M3 IC) problem based on Maximum Margin Clustering (MMC) [Xu et al., 2005]. The new formulation aims at finding desired hyperplanes that maximize the margin differences on at least one instance per bag in a unsupervised way. But the formulation of M3 IC is a nonconvex optimization problem, and we can not solve it directly. Therefore, we relax the original M3 IC problem and propose a method - M3 IC-MBM, which is a combination of Constrained Concave-Convex Procedure (CCCP) and Cutting Plane methods, to solve the relaxed optimization task.

The rest of the paper is organized as follows: Section 2, introduces the MIC problem. Section 3 formulates the novel M3 IC problem and propose an efficient method to solve it. Section 4 presents the experimental results. Section 5 concludes and points some future research directions.

2 Problem Statement

Suppose we are given a set of n bags, {Bi, i = 1, 2, · · · , n}. The instances in the bag Bi are denoted as {Bi1,Bi2, ...,Bini } , where ni is the total number of instances in this bag. The goal is to partition this given dataset into k clusters, such that the concepts in different clusters can be "distinct" from each other. We use a 1 × n vector f to denote the cluster assignment array, with fi being the cluster assignment for bag Bi.

3 The ProposedMethod

3.1 Formulation

First of all, we formulate the M3 IC problem. For each class p ∈ {1, · · · , k}, we define a weight vector wp. Instead of labeling all the samples by running an SVM implicitly over all possible labels as that in MMC [Xu et al., 2005], in M3 IC, we try to find a labeling on bags that results in several large margin classifiers that maximize margins on bags, and it is natural to define the Bag Margin (BM) for a bag Bi as:

where, u∗ij = argmaxp(wT p Bij), and v∗ ij = arg maxp\u∗ij (wT p Bij)1 . It is obvious that BM is determined by the most "discriminative " instance. With this definition, M3 IC can then be formulated as:

1 Throughout this paper, "\" means ruling out. So, this definition can also be written as: v∗ ij = arg maxp̸=u∗ij (wT p Bij )

Here, Iij ∗ equals 1 if j ∗ = argmaxj∈Bi (wT u∗ij Bij - wT v∗ ij Bij), and otherwise 0. l is a parameter that controls the cluster balance to avoid the trivially "optimal" solutions [Xu et al., 2005]. It is clear that, in this formulation, these two constraints are imposed only on the instances that determine the bag margins of their corresponding bags. Once these "witness" instances have been identified, the other instances become irrelevant. If we can obtain results from problem (2), the cluster assignment of a specific bag Bi can be determined by fi = argmaxp ∑j∈Bi IijwT p Bij .

3.2 M3 IC-MBM

However, the optimization problem (2) is difficult to solve. For the first constraint, i.e., maxj∈Bi (wT u∗ij Bij -wT v∗ ij Bij ) ≥ 1 - ξi, the convexity of wT v∗ ij Bij is unknown, which makes the form of the constraint too complicated. For the second constraint, the indication function Iij also makes this constraint non-convex. In this section, we first relax these two constraints, and then propose an efficient method - M3 ICMBM to solve the resulting optimization problem.

Relaxation

To relax the first constraint, we consider introducing the notion of Modified Bag Margin (MBM). For a bag Bi, MBM is defined as:

Here, the "mean" function calculates the average value of the input function with respect to the subscript variable. Replacing BM with MBM, the first constraint in problem (2) turns to: maxj∈Bi (maxuwT u Bij - meanv\u∗ij (wT v Bij)) ≥ 1 - ξi. This is equivalent to k k-1 maxj∈Bi (maxu wT u Bij - meanv (wT v Bij )) ≥ 1 - ξi .

For the second constraint in problem (2), we relax the indication function Iij, and rewrite this constraint as follows:

Without loss of generality, we introduce two concatenated vectors as:

Here, 0 is a 1×d zero vector, where d is the dimension of Bij . In Bij(p), only the (p1)d to pd-th elements are nonzero and equals Bij . Then, we have ˜wT Bij(p) = wT p Bij .

With the relaxation of the two constraints in Eq. (3), Eq. (4), and the introduction of the two concatenated vectors in Eq.(5), problem (2) can be transformed to:

In the following sections, we will propose a method, M3 IC with Modified Bag Margin (M3 IC-MBM), to solve this relaxed problem (6).

CCCP Decomposition

Although the objective function and the second constraint in problem (6) are smooth and convex, the first constraint is not. Fortunately, the constrained concave-convex procedure (CCCP) is just designed to solve the optimization problems with a concave convex objective function with concave convex constraints [Smola et al., 2005]. Next, we will show how to use CCCP to solve the problem (6).

To simplify the notation, let f( ˜w, i) be k k-1 maxj∈Bi g( ˜w, i, j) and g( ˜w, i, j) be maxu ˜wT Bij(u) - meanv ( ˜wT Bij(v)). Then, the first constraint in problem (6) becomes: f( ˜w, i) ≥ 1 - ξi. It is obvious that this constraint is, although not convex, the difference of two convex functions.

Hence, we can solve problem (6) with CCCP. Given an initial point ˜w(0) , CCCP iteratively computes ˜w(t+1) from ˜w(t) 2 by replacing f( ˜w, i) with its first order Taylor expansions at ˜w(t) , and solving the resulting quadratic programming problem, until convergence.

Therefore, in order to use CCCP, we should first calculate the gradient and the first-order Taylor expansion of f( ˜w, i) at ˜w(t) . But f( ˜w, i) is a non-smooth functions w.r.t. ˜w. So, we replace its gradient with its subgradient as follows:

Here,

2 We use the superscript t to denote that the result is obtained from the t-th CCCP iteration. For example, ew(t) is the optimized weight vector from the t-th CCCP iteration step.

and

Then, we can decompose f( ˜w, i) at ˜w(t) as:

Thus, for the t-th CCCP iteration, by replacing f( ˜w, i) with Eq. (10) in problem (6), we obtain the following optimization problem:

Cutting Plane

It is true that, for each CCCP iteration step, we can solve problem (11) directly as a quadratic programming problem. But instead of directly solving this optimization problem, we employ the Cutting Plane method, which has shown its effectiveness and efficiency in solving similar tasks recently [Joachims, 2006]. In problem (11), we have n slack variables ξi. To solve it efficiently, we first derive the 1-slack form of problem (11) as in [Joachims, 2006]. More specifically, we introduce a signle slack variable ξ ≥ 0 and rewrite the problem (11) as:

Algorithm: M3 IC-MBM

Input:

1. bags {B1, ....,Bn}
2. parameters: regularization constant C, CCCP solution precision ϵ1, cutting plane solution precision ϵ2, cluster number k, cluster size balance l

Output:

The cluster assignment f

CCCP Iterations:

˜

1. Construct B = {Bij(r)}
2. Initialize ˜w0 ,t=0,ΔJ = 10-3 , J -1 = 10-3
3. while ΔJ/J t-1 > ϵ1 do
4. Derive problem (17). Set the constraint set Ω = φ,∀1 ≤ i ≤ n, ci=0, s = -1

Cutting Plane Iterations:

1. while Hts is true do
2. s = s +1

˜w(ts) , ξ (ts)

7. Get (

) by solving (17) under Ω

8. Compute the most violated bags, i.e., cts i , by

and update the constraint set Ω by Ω = Ω ⋃ cts .

1. end while
2. t = t +1
3. ˜w(t) = ˜w(t-1)s
4. ΔJ = J t-1 - J t
5. 13.end while
6. 14.Cluster Assignment:

Table 1: Algorithm: M3 IC-MBM

It can be proved that the solution to problem (12) is identical to problem (11) with ξ = 1n ∑ni=1 ξi (similar to [Joachims, 2006]).

Now the problem becomes how to solve problem (12) efficiently, which is convex and has exponential number of constraints because of the large number of feasible c. To solve this problem, we employ an adaption of the cutting plane algorithm [Kelley, 1960], which is intended to find a small subset of constraints Ω from the whole set of constrains {0, 1}n in problem (12) that guarantees a sufficiently accurate solution. Using this algorithm, we can construct a nested sequence of tighter relaxations. Specifically, in this algorithm, the first constraint is replaced by:

Similar to [Joachims, 2006], we can generally find a polynomially sized subset of constraints Ω , with which the solution of the relaxed problem satisfies all the constraints from problem (12) up to a precision ϵ2, i.e., ∀c ∈ {0, 1}n :

This means, the remaining exponential number of constraints will not be violated up to the precision ϵ2. Therefore, we don't need to explicitly add them to Ω.

The algorithm iteratively constructs Ω in Eq.(13). The algorithm starts with an empty set of constraints Ω. Specifically, it starts with the following problem:

After getting the solution ˜w(t0)3 of the above problem, the most violated constraint can be computed as:

Then, this constraint will be added to Ω and the optimization problem turns to:

Please note that, for the current cutting plane step, in Ω, there is only one n-dimensional vector, which is obtained from Eq.(16). From this updated optimization problem, we can get the solution ˜w(t1) . Then, the most violated constraint ct1 i can be computed similarly as in Eq.(16). The only difference is that the weight vector ˜w(t0) is replaced by ˜w(t1) . This procedure is repeated until all the constraints satisfy the requirement in Eq.(14). In this way, a successive strengthening approximation series of the problem (12) can be constructed by the expanding number of cutting planes that cut off the current optimal solution from the feasible set [Kelley, 1960].

The Whole Method

Our method is characterized by an outer iteration, i.e., CCCP iteration and an inner iteration, i.e., Cutting Plane iteration. We use Hts to denote the constraint 1n ( ˜w(ts) )T ∑ni=1 cts i ∂f ( ew,i) ∂ew |ew= ew(t) ≥ 1n ∑ni=1 cts i - (ξ (ts) + ϵ2) and J t = 12 ‖ ˜w(t) ‖2 + Cξ (t) . Then, the whole method is summarized in Table 1.

3 Here, we denote ti as the i-th iteration of the cutting plane algorithm for solving the problem from the t-th iteration of CCCP.

3.3 Discussion

Convergence and Local Minimal

The outer iteration of our method is CCCP. It has already been shown that CCCP decreases the objective function monotonically and converges to a local minimum solution [Smola et al., 2005]. As for the inner iteration - the Cutting Plane iteration, we have the following two theorems:

Theorem 1: Each iteration from step 5 to step 9 in Table 1 takes time O(ekn) for a constant constraint set Ω, where e is the average number of nonzero features of Bij and e = d for non-sparse data.

Theorem 2: The Cutting Plane iteration in Table 1 terminates after at most { 2 ϵ2 , 8CR2 ϵ22 } steps, where R2 = k

The proofs of these two theorems are similar to the proofs in [Joachims, 2006], and therefore are omitted here.

Although the convergence of M3 IC-MBM can be guaranteed, it is true that its outer iteration - CCCP iteration only converges to a local minimum solution. Therefore, we would expect a way to get a better solution. In this paper, we run the M3 IC-MBM algorithm several times, and choose the solution with the minimal J t value. We will show, in the experiments, M3 IC-MBM is pretty fast and with only a few repetition times, we can get good results.

Relationship

In [Zhao et al., 2008a], [Zhao et al., 2008b] and [Zhao et al., 2008c], the authors accelerate the MMC and SemiSupervised SVM for the traditional single instance learning problems. They first divide the original problem into a series of non-convex sub-problems by using Cutting Plane, then solve each non-convex sub-problem using CCCP iteratively. These methods have shown state-of-the-art performances, both in accuracy and efficiency, and they look similar to M3 IC-MBM in this paper. But the main common problem in their methods is that the Cutting Plane approach is designed to solve convex nonsmooth problems, rather than nonconvex problems. Since, they try to solve a non-convex problem by using cutting plane, the convergence and optimality of their methods may not be guaranteed. Different from their method, in M3 IC-MBM, we first apply the CCCP to decompose the original nonconvex problem into a series of convex ones, and then use the Cutting Plane method to solve each of them. In this way, the final solution can be guaranteed to converge to a local optimal value. Therefore, M3 IC-MBM is theoretically more elegant than the previous related methods.

4 Experiments

In this section, we will present a set of experiments to validate the effectiveness and the efficiency of the proposed method. All the experiments are performed with MATLAB r2008a on a 2.5GHZ Intel CoreTM 2 Duo PC running Windows Vista with 2.0GB main memory.

4.1 Datasets

Currently, there is no benchmark dataset for MIC algorithms. Fortunately, we can utilize several available datasets for multiple instance classifications, and make them eligible for the MIC tasks. Although MUSK datasets, i.e., MUSK1 and MUSK2 [Dietterich et al., 1998], are two most popular datasets, we can not use them here, because there is only one potential concept - musk in these two datasets, while we need at least two concepts to measure the clustering performances.

Corel We merge pictures from three categories of the Corel dataset, namely elephant, fox, and tiger. More specifically, we merge the positive bags from the benchmark datasets - elephant, fox, and tiger [Andrews et al., 2003]. The reason why the negative bags in these datasets are not used is that the main objective of clustering task is to discover the hidden concepts/patterns in a dataset. But, in these datasets, the negative bags are just some background pictures, and may contain no common hidden concept/pattern. Then, the detailed description of this combined dataset is summarized in Table 2.

SIVAL There are in total 25 categories in the SIVAL dataset [Rahmani and Goldman, 2006]. For each category, there are 60 images. We randomly partition these 25 categories into 5 groups, with each group containing 5 categories. We name the five groups as SIVAL1,SIVAL2,SIVAL3,SIVAL4, and SIVAL5. The descriptions of these datasets are summarized in Table 2.

4.2 Experimental Setups and Comparisons

We have conducted comprehensive performance evaluations by testing our method and comparing it with BAMIC [Zhang and Zhou, in press].

For BAMIC, we used the three bag distance measurement methods as in [Zhang and Zhou, in press], i.e., minimal Hausdorff distance, maximal Hausdorff distance and average Hausdorff distance. We name the BAMIC methods with these three bag distance measurements as BAMIC1, BAMIC2, and BAMIC3, respectively. For each dataset, we run each of these BAMIC algorithms 10 times independently, and report only the best performance of these 10 independent runs.

For M3 IC-MBM, we set ϵ1 = 0.01, ϵ2 = 0.01, The class imbalance parameter l is set by grid search from the grid [0, 0.001, 0.01, 0.1, 1 : 1 : 5, 10] and The parameter C is search from the exponential grid 2[-4:1:4] . ˜w0 is randomly initialized. To avoid the local minimal problem that we have mentioned in Section 3.3, for each experiment, we run the M3 IC algorithm 5 times independently and report the final result with the minimal J t in Table 1.

In experiments, we set the number of clusters k to the true number of classes for all clustering algorithms. Then, we use the clustering accuracy to evaluate the final clustering performance as in [Valizadegan and Jin, 2006][Xu et al.,

2005][Zhao et al., 2008b][Zhao et al., 2008c]. Specifically, we first take a set of labeled bags, remove the labels of these bags and run the clustering algorithms, then we relabel these bags using the clustering assignments returned by the algorithms. Finally, we measure the percentage of correct classifications by comparing the true labels and the labels given by the clustering algorithms. The average CPU-times for each independent run of these algorithms are also reported here.

4.3 Clustering Results

The clustering accuracies for different algorithms are reported in Table 3, while the average CPU time of all the independent runs for these algorithms is reported in Table 4.

From Table 3, it is easy to tell that M3 IC-MBM works much better than the BAMIC method. From Table 4, it is clear that our method runs much faster than BAMIC. This is because, in our algorithm, the outer iteration-CCCP iteration, as well as the inner iteration-Cutting Plane iteation, converges very fast. But for BAMIC, since it needs to calculate the distances between instances in different bags many times, its speed will be badly affected.

5 Conclusions

In this paper, we formulate a novel M3 IC problem for the multiple instance clustering task. In order to avoid solving a non-convex problem directly, we relax the original problem. Then, a combination of Constrained Concave-Convex Procedure (CCCP) and the Cutting Plane method - M3 IC-MBM is proposed to solve the relaxed problem. After that, we demonstrate some important properties of the proposed method. In the experiment part, we compare our method with the existed method-BAMIC on several real-world datasets. However, it is true that under some special cases, a bag may belong to more than one clusters. But in our algorithm, we can only assign a bag to one cluster. In the future, we will consider how to deal with this problem.