{'fraction_non_alphanumeric': 0.04169506930243127, 'fraction_numerical': 0.014371733696887072, 'mean_word_length': 4.401963792574409, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multiple Instance Dictionary Learning using Functions of Multiple Instances

A multiple instance dictionary learning method using functions of multiple instances (DL-FUMI) is proposed to address target detection and two-class classification problems with inaccurate training labels. Given inaccurate training labels, DL-FUMI learns a set of target dictionary atoms that describe the most distinctive and representative features of the true positive class as well as a set of nontarget dictionary atoms that account for the shared information found in both the positive and negative instances. Experimental results show that the estimated target dictionary atoms found by DL-FUMI are more representative prototypes and identify better discriminative features of the true positive class than existing methods in the literature. DL-FUMI is shown to have significantly better performance on several target detection and classification problems as compared to other multiple instance learning (MIL) dictionary learning algorithms on a variety of MIL problems.


I. INTRODUCTION
Obtaining accurate training label information is often time consuming, expensive, and/or infeasible for large data sets. Furthermore, annotators may be inconsistent during labeling providing inherently imprecise labels. Thus, in many applications, one has access only to inaccurately or weakly labeled training data.
Sparse coding and dictionary learning methods, whose lowrank data representations generally reduce redundancy and improve discrimination ability, have been successfully applied to many applications [1]. DL-FUMI leverages the benefits of discriminative dictionary learning for target detection applications given only inaccurate labels. This is accomplished through the use of a novel model that assumes each target data point is a mixture of both target and background atoms whereas non-target data points are composed of only background atoms. In other words, unlike the majority of discriminative dictionary learning methods, DL-FUMI does not learn a separate dictionary for each class. Instead, DL-FUMI introduces a shared background dictionary that is used in reconstruction of both target and non-target points. The advantage of this model over class-specific dictionaries is that the target atoms only need to account for the unique characteristics of target (and do not need to address any shared background variability) resulting in more discriminative, representative target atoms.
Furthermore, the target atoms estimated by DL-FUMI can be examined to uncover what discriminates target data points. Since most approaches estimate class-specific dictionaries, each dictionary must characterize both the class-specific characteristics and the characteristics shared among all data points. Thus, in these methods, it is often difficult to pin down what is unique about each class without prior insight since the class-specific features are mixed with background features and spread across the atoms. In contrast, DL-FUMI provides that insight by pulling out the unique target characteristics and identifying which atoms contain those characteristics. In summary, DL-FUMI advances discriminative dictionary learning by (1) addressing multiple instance learning problems and (2) using a shared background model resulting in improved target characterization and discrimination.
A. Multiple-instance learning (MIL): MIL [2] is a variation on supervised learning for problems with inaccurate label information. In particular, training data is segmented into positive and negative bags. A bag is defined to be a multi-set of data points. In the case of target detection, the MIL problem requires that a positive bag contains at least one instance from the target class and negative bags are composed of entirely non-target data. Given training data of this form, the overall goal can be to predict either unknown instance-level or bag-level labels on test data. MIL methods are effective for problems where accurately labeled training data is unavailable.
Most MIL approaches focus on learning a classification decision boundary to distinguish between positive and negative instances/bags [3], [4]. Although these decision boundary approaches are effective at training classifiers given inaccurate labels, they do not provide an intuitive description or representative concept that characterizes the salient and discriminative features of the target class. The approaches that estimate target representatives [5], [6], [7] often only find a single target concept and are, thus, unable to account for large variation in the target class. To address this, DL-FUMI learns a set of target atoms (and background atoms) to characterize target variation.

B. Supervised Dictionary Learning:
Sparse coding refers to the task of decomposing a signal into a sparse linear combination of dictionary atoms [8], [9]. Of particular relevance are supervised (i.e., task-driven or discriminative) dictionary learning methods [10], [11]. However, among supervised dictionary learning methods, there are only a few approaches that address the problem given inaccurate MIL labels. These include MMDL [12] that trains many linear SVM classifiers and views the estimated parameters as dictionary atoms and DMIL [13], [14] that learns class-specific (4) dictionaries by maximizing the noisy-OR model in such a way that the all negative instances are poorly represented by the estimated target dictionary. As outlined in Sec I, DL-FUMI is unique from these existing methods through the use of a shared background dictionary.

II. DL-FUMI
Let X = [x 1 , · · · , x N ] ∈ R d×N be training data where d is the dimensionality of an instance, x i , and N is the total number of training instances. The data is grouped into K bags, B = {B 1 , . . . , B K }, with associated binary bag-level labels, L = {L 1 , . . . , L K } where L j ∈ {0, 1} and x ji ∈ B j denotes the i th instance in bag B j . Given training data in this form, DL-FUMI models each instance as a sparse linear combination of target and/or background atoms D, x i ≈ Dα i , where α i is the sparse vector of weights for instance i. Positive bags (i.e., B j with L j = 1, denoted as B + j ) contain at least one instance composed of some target: where ε i is a noise term. However, the number of instances in a positive bag with a target component is unknown.
If B j is a negative bag (i.e., L j = 0, denoted as B − j ), then this indicates that B − j does not contain any target: Given this problem formulation, the goal of DL-FUMI is to estimate the dictionary 1 are the T target atoms and atoms. This is accomplished by minimizing (3) which is proportional to the complete negative data log-likelihood, where α l+ i and α l− i are subsets of α i corresponding to D + and D − , respectively. The first term in (3) computes the squared residual error between each instance and its estimate using the dictionary. In this term, a set of hidden binary latent variables {z i } N i=1 that indicate whether an instance is or is not a target (i.e., z i = 1 when x i contains target) are introduced. For all points in negative bags, z i = 0. For points in positive bags, the value of z i is unknown.
j where ψ is a fixed parameter. This weight helps balance terms when there is a large imbalance between the number of negative and positive instances. The second term is an l 1 regularization term to promote sparse weights. It also includes the latent variables, z i , to account for the uncertain presence of target in positive bags.
The third term is a robust penalty term that promotes discriminative target atoms (and inspired by a term presented in [15]). Instead of using a fixed penalty coefficient, we introduce an adaptive coefficient γ kt defined as: where θ kt is the vector angle between the k th background atom and the t th target atom. Since sign(γ kt ) = sign( d − k , d + t ), this discriminative term is always positive and will add large penalty when d − k and d + t have similar shape. Thus, this term encourages a discriminative dictionary by promoting background atoms that are orthogonal to target atoms. In implementation, γ kt is updated once per iteration using d − k old and d + t old which are the dictionary values from the previous iteration.

III. DL-FUMI OPTIMIZATION
Expectation-Maximization is used to optimize (3) and estimate D. During optimization, the fact that many of the binary latent variables {z i } N i=1 are unknown is addressed by taking the expected value of the log likelihood with respect to z i as shown in (4). In (4) is the set of parameters estimated at iteration l and P (z i |x i , θ (l−1) ) is the probability that each instance is or is not a true target instance. During the E-step of each iteration, P (z i |x i , θ (l−1) ) is computed as: where β is a fixed scaling parameter. If x i is a non-target instance, then it should be characterized by the background atoms well, thus P (z i = 0|x i , θ (l−1) ) ≈ 1. Otherwise, if x i is a true target instance, it will not be characterized well using only the background atoms and P (z i = 1|x i , θ (l−1) ) ≈ 1. The M-step is performed by iteratively optimizing (4) for each of the desired parameters. The dictionary D is updated atom-by-atom using a block coordinate descent scheme [16], [17]. The sparse weights, {α i } N i=1 , are updated using an iterative shrinkage-thresholding algorithm [18], [19]. For readability, the derivation of update equations are described in Sec. VII. The method is summarized in Alg. 1.

IV. CLASSIFICATION USING ESTIMATED DICTIONARY
Given D, a confidence that the i th instance is target can be computed using a ratio of the reconstruction errors given the target and background atoms, D, vs. background atoms, D − : where α − i are the sparse weights for the non-target atoms for the i th instance. If the numerator has a large error and the denominator has a low error, then the target atoms are needed to reconstruct instance i.

V. EXPERIMENTS
DL-FUMI is evaluated on two MIL AR Face data [20], [21] recognition problems and an MIL USPS hand-written digits [22], [23] recognition problem. In all of our experiments, target atoms were initialized by computing mean of T random subsets drawn from the union of all positive bags. K-means was applied to the union of all negative bags and the M cluster centers were set as the initial background atoms.

A. AR Face Recognition
The AR-face data set consists of frontal-pose images with 26 images/person (2 sessions, 13 per session) corresponding to different expressions, illuminations and occlusions. Preprocessed and cropped imagery of 50 male and 50 female subjects provided by Martinez and Kak [21] was used. Each image was down-sampled to 83 × 60 pixels and the raw gray scale values were used as features. For the first AR Face experiment, sun-glasses were the target concept. Specifically, 50 positive training bags of 10 instances each were created. Each positive bag contained only two instances of randomly selected images of people wearing sunglasses; the other eight were randomly chosen from images of people without sun-glasses. 50 negative bags were constructed by randomly selecting 10 instances per bag of images of individuals not wearing sun-glasses. Test data included all imagery that was not used for training.
The parameters for DL-FUMI for this experiment were set to T = 3, M = 8, Γ = 0.001, β = 30 and λ = 0.001. After dictionary estimation, the target confidence was computed for each test instance following Sec. IV. Receiver operating characteristic (ROC) curve analysis was conducted. Fig. 1 shows one of the 10 ROCs obtained by DL-FUMI, DMIL and EM-DD where the TPR vs FPR obtained by mi-SVM and MMDL were also plotted. The average TPRs of DL-FUMI, EM-DD and DMIL over 10 runs are shown in Table I Fig. 2 and Fig. 3 show estimated target and background atoms by DL-FUMI and comparison methods, respectively. To estimate the DMIL background atoms, we flipped the sign of positive and negative bags (i.e., swapped the target and background classes) and re-trained the dictionary. This was done since, as stated in [14], DMIL does not learn a set of background atoms simultaneously. As shown, DL-FUMI target atoms are very discriminative and representative of the target class, e.g., there are male and female sun-glasses atoms and variation in light reflections. Finally, the overall dictionary set estimated by DL-FUMI is qualitatively more smooth which will help to reduce error in classification.
For the second AR Face experiment, Woman No. 10 was selected as the positive target class. Two positive training bags containing 50 instances each were created. The first positive bag contained 6 images from Woman No. 10 set 1 and the second positive bag contained the remaining 7   Table II at FPRs 2.9%, 5% and 12.0%, where 2.9% and 12.0% are average FPRs by two classification algorithms MMDL and mi-SVM, respectively. Table II and Fig. 4 clearly show that DL-FUMI outperforms all the comparison algorithms. In order to further show that the estimated target dictionary by DL-FUMI is effective at characterizing the target class, the subspace adaptive cosine estimator (subACE) target detection algorithm [25] was applied for detection using the target dictionary estimated by DL-FUMI directly. One of the subACE ROCs using the DL-FUMI dictionary shows a 100% TPR with 0% FPR in Fig. 4. Since subACE is a target detection   --69.2 EM-DD [6] 0 0 0 MMDL [12] 31.5 --DMIL [13] 54.5 69.1 78.8 DL-FUMI (using (7)

B. USPS Digit Classification
DL-FUMI is further evaluated on a multi-class classification task given the USPS 2 data set. The USPS data set contains 9298 images of handwritten digits from 0 to 9. Each image is 16 × 16 in size. The raw gray-level pixel values are used as features in this experiment. The training and testing data partitions in this paper mimics the experimental set-up in [14]. Specifically, for each class c, 50 positive training bags were generated. Each bag contains 4 instances in total and only one comes from true c th positive class and the other three instances are randomly chosen from other classes. 50 negatively labeled bags were also constructed by randomly selecting 50 instances per bag from classes other than c. The testing data contains 2000 samples in total, 200 from each class.
In this experiment, the parameters used were T = 4, M = 15, Γ = 0.1, β = 25 and λ = 0.001. For instance level classification, the approach described in Sec. IV was applied given a dictionary estimated given each class as the target class. Then, the final class label, for multi-class classification, was assigned by selecting the class with the largest confidence value computed in (7). The classification results of DL-FUMI and comparison algorithms are listed in Table III, where results for GD-MIL are as reported in [14]. Table III shows that DL-FUMI outperforms two multiple instance dictionary learning methods, GD-MIL and MMDL, and two MIL methods mi-SVM and EM-DD. Fig. 7(a) and 7(b) show the estimated DL-FUMI target and non-target dictionary atoms, in these we can see that DL-FUMI is able to learn a set of discriminative target dictionary as well as characteristic background dictionary (i.e., each target dictionary atom looks like the target digit and the background dictionary atoms look like all the other digits).
To get insight into classification errors, Fig. 8 Fig. 8(a) has a true class label of 0, but was misclassified to 6; the reconstructed image is shown in Fig. 8(e). As can be seen, this data point appears to be very similar to the digit 6 and is even difficult for a human to correctly recognize. Similarly, Fig. 8(b) -8(d) show the other three images and Fig. 8(f) -8(h) show the corresponding reconstructed images, respectively. 2 Database at: http://www-i6.informatik.rwth-aachen.de/∼keysers/usps.html 3 Results as stated in the literature [14].   [14] 83.4 EM-DD [6] 76.55 MMDL [12] 80.8 DL-FUMI 86.5

VI. CONCLUSION
In this paper, a multiple-instance dictionary learning algorithm, DL-FUMI, is proposed. DL-FUMI leverages the shared information between positive and negative classes to improve the discriminative ability of the estimated target atoms. Experimental results show that the estimated DL-FUMI target atoms provide a good representation of the positive class and improves target detection and classification performance over comparison methods.

VII. DERIVATION OF DL-FUMI UPDATE EQUATIONS
This section provides a derivation of DL-FUMI update equations. When updating the dictionary D, the sparse weights Note, P (z i |x i , θ (t−1)) is denoted as P (z i ) for simplicity. When updating the sparse weights, , it should be noted that the sparse weight vector α i for instance x i is not dependent on any other instances.
The gradient with respect to α i without considering the l 1 penalty term is: Then α i at l th iteration can be updated using gradient descent, followed by a soft-thresholding: Following a similar proof to that in [26], when ηi ∈ 0, λmax P (zi = 0) 0 d×T D − T 0 d×T D − + P (zi = 1)D T D −1 , the update of α i using a gradient descent method with step length η i monotonically decreases the value of the objective function, where λ max (A) denotes the maximum eigenvalue of A. For simplicity, η was set as η = 1 λmax(D T D) for all α i , x i ∈ B + j . A similar update can be used for points from negative bags. The resulting update equation for negative points is: The sparse weights corresponding to target dictionary atoms are set to 0 for all points in negative bags.