matically learn the interest of the user.This can be achieved demonstrate the promising performance of our method through relevance feedback or by inputting a query image with respect to multiple performance metrics,includ- set [12]labeled as positive or negative by the user accord- ing accuracy,efficiency and robustness. ing to whether the images contain the target regions of in- terest.Under this setting,the underlying learning problem It should be emphasized that the focus of this work is on for localized CBIR is essentially an MIL problem where an CBIR rather than image classification.Although the tech- image corresponds to a bag and each region in the image niques for CBIR are also suitable for image classification, corresponds to an instance and vice versa,their application scenarios are somewhat dif- ferent.While for image classification a large number of la- 1.2.Motivation beled images can be provided for training,for CBIR it is unreasonable (or impractical)to require the user to input a Few of the existing MIL methods have designed effective large number of query images. feature representation schemes to describe the bags.mak- ing it difficult to adapt some sophisticated SIL methods for 2.A Feature Representation Scheme for MIL MIL problems.DD-SVM [4]is the first MIL method try- ing to propose a feature representation scheme for the bags 2.1.Notations and Conventions in MIL to convert MIL into SIL.However,the features of DD-SVM are very sensitive to noise and incur very high B denotes a positive bag and B denotes a negative computation cost.MILES [3](Multiple Instance Learning bag.When the label of a bag is irrelevant,we simply de- via Embedded instance Selection)also converts MIL into a note the bag as Bi.B denotes an instance in a positive standard SIL problem via feature mapping,in which each bag B and B is an instance in a negative bag B.Let feature is defined by an instance from the training bags,in- B={Bt,B时，Bt+,B,B,,B元-}denote the cluding both positive and negative bags.Although MILES set of all n positive and n-negative training bags.For is less sensitive to noise and more efficient than DD-SVM. each bag Bi,its bag label is yi E{+1,-1}.All the in- the feature space for representing bags is of very high di- stances are represented as feature vectors of the same di- mensionality because it contains too many irrelevant fea- mensionality.Furthermore,in CBIR,a bag refers to an im- tures.Hence,appropriate classifiers that can make use of age and an instance corresponds to a region in some image the feature representation scheme in MILES are limited to those that can perform both feature selection and classifica- 2.2.Evidence Instance Identification tion simultaneously,such as 1-norm SVM [3].Therefore, According to the MIL problem formulation,a bag is la- the motivation of this work is to design an effective as well beled positive if at least one of its instances is positive;oth- as efficient feature representation scheme for representing erwise,the bag is labeled negative.Because whether or not the bags in MIL there exist positive instances in a bag provides evidence for supporting the bag's label,we call the positive instances ev- 1.3.Main Contributions idence instances.If a bag refers to an image,evidence in- In this paper,we propose a feature representation scheme stances are also referred to as evidence regions. for the bags in MIL to convert MIL into SIL and adapt the sophisticated SIL technique,SVM,to solve MIL problems. 2.2.1 Evidence Instance Identification Algorithm The main contributions are summarized as follows: The evidence confidence EC(Bgh),which is used to repre- We propose an evidence region (or evidence instance) sent the confidence (or likelihood)for the instance Bgh to identification method to identify the evidence regions be an evidence instance,is defined as follows: that support the labels of the images(i.e.,bags). .A very effective feature representation scheme,which EC(Bah)= ΠPr()ΠPr(BhB),(I) is also very computationally efficient and robust to la- beling noise,is proposed to describe the bags based on the identified evidence regions.As a result,the MIL where Pr(Bgh|Bi)is estimated based on the noisy-OR problem is converted into a standard SIL problem and model [8]: an SVM is successfully adapted for localized CBIR. The resulting method is called EC-SVM,which will Pr(Bgh |B) be described in detail later. We compare our method extensively with many state- Pr(Bgh|B) I[1-Pr(BghB】 of-the-art methods on two challenging data sets tomatically learn the interest of the user. This can be achieved through relevance feedback or by inputting a query image set [12] labeled as positive or negative by the user accord￾ing to whether the images contain the target regions of in￾terest. Under this setting, the underlying learning problem for localized CBIR is essentially an MIL problem where an image corresponds to a bag and each region in the image corresponds to an instance. 1.2. Motivation Few of the existing MIL methods have designed effective feature representation schemes to describe the bags, mak￾ing it difficult to adapt some sophisticated SIL methods for MIL problems. DD-SVM [4] is the first MIL method try￾ing to propose a feature representation scheme for the bags in MIL to convert MIL into SIL. However, the features of DD-SVM are very sensitive to noise and incur very high computation cost. MILES [3] (Multiple Instance Learning via Embedded instance Selection) also converts MIL into a standard SIL problem via feature mapping, in which each feature is defined by an instance from the training bags, in￾cluding both positive and negative bags. Although MILES is less sensitive to noise and more efficient than DD-SVM, the feature space for representing bags is of very high di￾mensionality because it contains too many irrelevant fea￾tures. Hence, appropriate classifiers that can make use of the feature representation scheme in MILES are limited to those that can perform both feature selection and classifica￾tion simultaneously, such as 1-norm SVM [3]. Therefore, the motivation of this work is to design an effective as well as efficient feature representation scheme for representing the bags in MIL. 1.3. Main Contributions In this paper, we propose a feature representation scheme for the bags in MIL to convert MIL into SIL and adapt the sophisticated SIL technique, SVM, to solve MIL problems. The main contributions are summarized as follows: • We propose an evidence region (or evidence instance) identification method to identify the evidence regions that support the labels of the images (i.e., bags). • A very effective feature representation scheme, which is also very computationally efficient and robust to la￾beling noise, is proposed to describe the bags based on the identified evidence regions. As a result, the MIL problem is converted into a standard SIL problem and an SVM is successfully adapted for localized CBIR. The resulting method is called EC-SVM, which will be described in detail later. • We compare our method extensively with many state￾of-the-art methods on two challenging data sets to demonstrate the promising performance of our method with respect to multiple performance metrics, includ￾ing accuracy, efficiency and robustness. It should be emphasized that the focus of this work is on CBIR rather than image classification. Although the tech￾niques for CBIR are also suitable for image classification, and vice versa, their application scenarios are somewhat dif￾ferent. While for image classification a large number of la￾beled images can be provided for training, for CBIR it is unreasonable (or impractical) to require the user to input a large number of query images. 2. A Feature Representation Scheme for MIL 2.1. Notations and Conventions B + i denotes a positive bag and B − i denotes a negative bag. When the label of a bag is irrelevant, we simply de￾note the bag as Bi . B + ij denotes an instance in a positive bag B + i and B − ij is an instance in a negative bag B − i . Let B = {B + 1 , B+ 2 , . . . , B+ n+ , B− 1 , B− 2 , . . . , B− n− } denote the set of all n + positive and n − negative training bags. For each bag Bi , its bag label is yi ∈ {+1, −1}. All the in￾stances are represented as feature vectors of the same di￾mensionality. Furthermore, in CBIR, a bag refers to an im￾age and an instance corresponds to a region in some image. 2.2. Evidence Instance Identification According to the MIL problem formulation, a bag is la￾beled positive if at least one of its instances is positive; oth￾erwise, the bag is labeled negative. Because whether or not there exist positive instances in a bag provides evidence for supporting the bag’s label, we call the positive instances ev￾idence instances. If a bag refers to an image, evidence in￾stances are also referred to as evidence regions. 2.2.1 Evidence Instance Identification Algorithm The evidence confidence EC(Bgh), which is used to repre￾sent the confidence (or likelihood) for the instance Bgh to be an evidence instance, is defined as follows: EC(Bgh) = nY+ i=1 Pr(Bgh | B + i ) nY− i=1 Pr(Bgh | B − i ), (1) where Pr(Bgh | Bi) is estimated based on the noisy-OR model [8]: Pr(Bgh | B + i ) ∝    1 − Y j 1 − Pr(Bgh | B + ij )    (2) Pr(Bgh | B − i ) ∝ Y j 1 − Pr(Bgh | B − ij ) . (3)