IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,VOL.X,NO.X,XXX 200X 5 many existing supervised and semi-supervised learning methods can be easily adapted for MIL applications. 2 RELATED WORK Over the past few years,many applications have been formulated as MIL problems.These include drug activity prediction [1],[13],[14],[15],image classification [4],[11],[16],[17],[18],text classification [2],[7],stock selection [7],[10],protein family modeling [19],computer aided diagnosis [20],[21],and security applications [22].To solve these problems,many MIL methods have been proposed.The first MIL method is APR [1],which represents the target concept by an axis-parallel rectangle (or hyper-rectangle)in the feature space.The rectangle includes at least one instance from each positive bag but excludes all instances from the negative bags.[10] proposed a measure called DD(diverse density),which essentially measures how many different positive bags have instances near a point in the feature space and how far the negative instances are from that point.A DD-based method tries to find the point with the highest DD value as the target concept.EM-DD [23],[24]combines expectation-maximization (EM)[25]with the DD formulation by using EM to search for the most likely concept. Several other methods try to modify standard single-instance learning methods for MIL by introducing constraints derived from the MIL formulation.[7]proposed two methods based on SVM,one(mi-SVM)for instance-level classification and the other (MI-SVM)for bag-level clas- sification.Both methods are formulated as mixed integer quadratic programming problems.[26] applied deterministic annealing to the SVM formulation to find better local mimima compared to the heuristic methods.[6]proposed a kernel function directly for bags.With this multi-instance (MI)kernel,in principle any kernel-based classifier can be trained for classifying the bags.[27] extended this work by proposing a marginalized MI kernel to convert the MIL problem from an incomplete data problem to a complete data problem.[28]proposed an SVM-based method for sparse positive bags by directly enforcing the desired constraint that at least one of the instances in a positive bag is positive.[9]proposed to apply transductive SVM for solving MIL problems. Recently,some methods try to convert MIL into a standard single-instance problem and then solve it with conventional methods by representing the bags as feature vectors.[4]proposed the DD-SVM method through a feature mapping defined on some instance prototypes learned by DD.[11]proposed another method,called MILES (Multiple Instance Learning via Embedded March 1,2009 DRAFTIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. X, NO. X, XXX 200X 5 many existing supervised and semi-supervised learning methods can be easily adapted for MIL applications. 2 RELATED WORK Over the past few years, many applications have been formulated as MIL problems. These include drug activity prediction [1], [13], [14], [15], image classification [4], [11], [16], [17], [18], text classification [2], [7], stock selection [7], [10], protein family modeling [19], computer aided diagnosis [20], [21], and security applications [22]. To solve these problems, many MIL methods have been proposed. The first MIL method is APR [1], which represents the target concept by an axis-parallel rectangle (or hyper-rectangle) in the feature space. The rectangle includes at least one instance from each positive bag but excludes all instances from the negative bags. [10] proposed a measure called DD (diverse density), which essentially measures how many different positive bags have instances near a point in the feature space and how far the negative instances are from that point. A DD-based method tries to find the point with the highest DD value as the target concept. EM-DD [23], [24] combines expectation-maximization (EM) [25] with the DD formulation by using EM to search for the most likely concept. Several other methods try to modify standard single-instance learning methods for MIL by introducing constraints derived from the MIL formulation. [7] proposed two methods based on SVM, one (mi-SVM) for instance-level classification and the other (MI-SVM) for bag-level clas￾sification. Both methods are formulated as mixed integer quadratic programming problems. [26] applied deterministic annealing to the SVM formulation to find better local mimima compared to the heuristic methods. [6] proposed a kernel function directly for bags. With this multi-instance (MI) kernel, in principle any kernel-based classifier can be trained for classifying the bags. [27] extended this work by proposing a marginalized MI kernel to convert the MIL problem from an incomplete data problem to a complete data problem. [28] proposed an SVM-based method for sparse positive bags by directly enforcing the desired constraint that at least one of the instances in a positive bag is positive. [9] proposed to apply transductive SVM for solving MIL problems. Recently, some methods try to convert MIL into a standard single-instance problem and then solve it with conventional methods by representing the bags as feature vectors. [4] proposed the DD-SVM method through a feature mapping defined on some instance prototypes learned by DD. [11] proposed another method, called MILES (Multiple Instance Learning via Embedded March 1, 2009 DRAFT