Learning Optimal Subsets with Implicit User Preferences

1 Introduction

Many interesting problems can be abstracted as finding an optimal subset of items that maximizes the utility induced by a preference function defined over individual items or sets of items, given a larger ground set. Examples range from real-world scenarios, such as recommending movies from a list of titles or buying the weekly groceries from a supermarket among aisles of alternatives, to the more general binary knapsack and set covering problems. We note that selecting a subset of items from a larger ground set based on a preference function is different from ranking the items and selecting the top items to include in the subset, since choices may interact with each other. For example, when selecting what to take on a backpacking trip, a bottle of water can be most essential (thus ranked highest), but two bottles of water may be less preferred than a bottle of water and an apple. This example is also known as the portfolio effect. In addition, because items in the optimal subset are normally equally preferred, learning a total ranking of items may not be possible. The problems of preference representation have been studied in the literature [Brafman et al., 2006a; desJardins and Wagstaff, 2005; Freund et al., 2003; Domshlak and Joachims, 2005]. The problem of computing the optimal subset, assuming a completely known preference function, has also been studied [Binshtok et al., 2007; Price and Messinger, 2005]. Recent work has also shown how, given a pre-defined parameterized preference function, the parameters can be automatically learned from historical data. A heuristic greedy method is then used to select an item subset from a larger ground set, trying to maximize the utility associated with the pre-defined (with learned parameters) preference function [desJardins et al., 2006].

In our work we assume that for each ground set of items, a single most preferred optimal subset exists according to some (unknown) preference function, and we want to build a model that can predict the subset as close as possible to the optimal one. Given the wide range of (unknown) preference functions, it is difficult to define a priori the right parameterized family of functions. In order to circumvent this intermediate step, we discriminatively learn to predict the optimal subsets from historical datasets, using structural machine learning, without explicitly assuming a pre-defined parameterized preference function over sets of items. As no explicit preference function is assumed during learning, our performance evaluation is based on a set similarity measure. To the best of our knowledge, our approach is the first one to formulate this problem as the task of learning to predict an optimal subset that maximizes a set similarity measure, without an explicit preference representation. We solve the structural learning for the optimal subset selection problem using Structural Support Vector Machines, for which we guarantee that learning is performed in polynomial time and testing inference is exact, even with an exponential number of candidate subsets. Our experiments are conducted using both a synthetic dataset and a real-world face image dataset. A total of 8 subset selection tasks are used for the evaluation. Our method outperforms the previous approach significantly in all tasks in terms of several set similarity measures.

2 Optimal Subset Learning

2.1 Problem Formulation

Let X denote the space of possible ground sets, and S(x) the space of subsets given a ground set x ∈ X. We assume all possible subsets are legitimate so |S(x)| = 2|x| . In addition, let S(X ) = ⋃x∈X S(x). An example instance is illustrated in Figure 1,where the ground set consists of six face images and the two optimal subsets correspond to two very different kinds of preferences on the same ground set.

The learning problem can be formulated as follows: we Ground Set The two subsets correspond to two user preferences: S1-all face images that can be used as passport photos (looking straight and no sunglasses); S2-if there are more angry faces than happy faces, choose all angry faces, otherwise all happy faces that are with sunglasses or looking up.

are given n supervised training sets (xi,yi), where xi is the ith ground set of items and yi is the optimal subset computed from some implicit user preferences according to the ground set xi with yi ⊆ xi; each item I ∈ xi is represented as a real valued feature vector; the goal is to learn a function F: X → S(X ) which, given a new unseen ground set x, predicts the subset ̂ y of x that minimizes the expected value of a set similarity loss Δ(y, ̂ y), where y is the optimal subset computed from x if we knew the underlying implicit user preferences. As the distribution of instances in X is largely unknown, we instead construct the function f: X →S(X ) that minimizes the empirical risk

where Δ : S(X ) × S(X ) → R is the loss function that penalizes predicting f (xi) as the optimal subset yi.

2.2 The Loss Function Δ

We define the loss function Δ(̂ y, yi) = 1 - σ(̂ y, yi) with σ(y1, y2)= |y1∩y2| max(|y1|,|y2|) , assuming max(|y1|, |y2|)>0. σ(y1, y2) is our measure for set similarity which we refer to as set accuracy. Note that σ(y1, y2) is the minimum of the precision and recall scores given sets y1 and y2. Averaged over multiple instances, set accuracy is upper bounded by the average precision and recall scores. This similarity measure differs from two other often used set similarity measures, namely the Jaccard Index defined as J (y1, y2) = |y1∩y2| |y1∪y2| , and the Dice's coefficient D(y1, y2) = 2×|y1∩y2| |y1|+|y2| , which can be shown to be equal to the F1-score in our problem setting.

The differences of the loss functions are illustrated in Figure 2, where the true optimal subset size is 20, and the size of the overlap of the optimal and predicted subsets is a constant 10. Both Jaccard and F1 loss increases as the predicted size increases, while the set loss is indifferent until the size of the predicted subset reaches that of the optimal subset. We prefer set loss in our problem setting because it encourages the model to aggressively select more items into the subset to achieve a larger overlap between the predicted set and the optimal one when the sizes of two sets do not differ significantly. For example, consider the instance where the true optimal subset is {1,2,3} for a much larger ground set, and the two predicted subsets are ̂ y1 = {1} and ̂ y2 = {1, 2, 4, 5, 6}. Intuitively we prefer ̂ y2 over ̂ y1 as it contains more information included in the optimal set. The Jaccard loss and F1-loss will have the same penalty on both predicted subsets, while set loss penalizes ̂ y1 more. Nevertheless, we will also include the Jaccard Index and the F1-score as performance evaluation metrics in the experiment section.

2.3 Structural Learning Formulation

The optimal subset learning problem naturally falls into the structured learning regime, as the input and output are sets of objects that can interact with other objects in the ground set. We propose to solve it using structural SVM for optimal subset learning (SVMOS), formulated as follows:

OPTIMIZATION PROBLEM SVMOS

φ(x, y) in (3) is the feature map jointly defined by a ground set and a candidate subset. It is a well-known result in the multiclass setting that for any feasible solution w and ξ, ∑ni=1 ξi is an upper bound on the training loss, independent of the prediction function f. The same result holds for our structural learning setting, as we can use simple arithmetic to show that

After the weight vector w is optimized in the above quadratic formulation, the linear discriminant score for predicting subset y as the optimal subset for ground set x is T (x, y; w) = w⊤φ(x, y), and the function f we use to predict subsets for an arbitrary ground set is:

2.4 Optimizing for SVMOS

There are an exponential number of constraints (∑ni=1 2|xi| ) in (3), which is the main difficulty in solving SVMOS optimally. We use Algorithm 1, a cutting plane algorithm proposed in [Tsochantaridis et al., 2005] to solve SVMOS within a tolerance ε from optimality. Algorithm 1 iteratively adds the most violated constraint to the initially empty working set of constraints to be optimized.

Theoretically, given R = maxi,y‖φ(xi, yi) - φ(xi , y)‖, Δ = maxi,y Δ(yi, y) and a fixed ε, Algorithm 1 stops after adding at most max{ 2nΔ ε , 8CΔR2 ε2 } constraints, with the solution ε-close to optimality. The proof can be found in [Tsochantaridis et al., 2005].

1: Input: (x1, y1), . . . , (xn, yn), C, ϵ 2: Pi ← ∅ for all i = 1, . . . , n 3: Initialize w 4: repeat 5: for i = 1,. . .,n do 6: H (y) ≡ Δ(y, yi) + T (x, y; w) - T (x, yi; w) 7: compute ̂ y = arg maxy∈S(xi) H (y) 8: compute ξi = max{0, maxy∈Pi H (y)} 9: if H (̂ y) > ξi + ε then 10: Pi ← Pi ∪ {̂ y} 11: w ← optimize the dual of SVMOS over P = ∪iPi 12: end if 13: end for 14: until no Pi has changed in the current iteration

Consequently, the polynomial runtime of Algorithm 1 is ensured if the "most violated" constraint, among the exponential number of constraints, i.e.,

can be computed in polynomial time.

In our problem setting, each item I is represented as a real valued vector υ(I ) ∈ Rk . We define the feature map to be:

If item I is selected in subset y, it contributes w⊤υ(I ) to T (x, y; w), otherwise its contribution is -w⊤υ(I ). For a given training set (x,y) and arbitrary ̂ y ∈ S(X ), we define a = |y ∩ ̂ y|, the size of overlap between subset y and ̂ y; and b = |y ∩ ̂ y|, the size of overlap of complement of y and ̂ y in x; and n = |x|, the size of the ground set. We can show:

and solve (6) optimally in polynomial time O(|x|2 ) using Algorithm 2 in [Joachims, 2005] as follows: since both a and b can only take values in {0,. . .,n}, Δ(̂ y, y) can have at most O(n2 ) different values. In addition, if a and b are fixed, we can construct ̂ y to maximize T (x, ̂ y ; w) in (6) easily: we rank all items in x according to the score w⊤υ(I ). Select a highest scored items in y to include in ̂ y, and do not select any of the b lowest scored items in x - y in ̂ y. For the rest n - a - b items, choose to include the item in ̂ y if and only if it is not in y. By iterating through legitimate values of a and b, we can find the most violated constraint in O(n2 ) time with efficient implementation. During the testing phase, the optimal subset that maximizes equation (5) is {I∈ x: w⊤υ(I ) > 0}.

3 Preference Formalism

So far we have concentrated on the structural learning algorithm, while being vague about the definition of preferences. Naturally, a preference p : X → S(X ) is a function that maps any ground set in X to its optimal subset in S(X ). Without loss of generality, we also assume that given a subset y ∈ S(x), it is easy to test if y = p(x). In fact, we will show that the decision version of computing the optimal subset given the preference p and a ground set x is NP-complete in the following.

Definition. SUBSET COMPUTATION PROBLEM (SCP) Input: ground set x, preference p, an item I∈ x Decision Question: Is I∈ p(x)?

Lemma. SCP is NP-complete.

Proof. This can be shown by reducing the binary knapsack problem to SCP. The details are omitted due to space constraints.

Therefore, for the experiment dataset construction, we further restrict that given preference p and ground set x, the optimal subset can be efficiently computed, for example in low order polynomial time. This restriction on the preference is for computational purposes of the experiment dataset, but it is not a limitation of our learning algorithm. If an oracle exists to produce the optimal subset given ground set x and unrestricted preference p, SVMOS is able to learn to predict the optimal subset.

4 RelatedWork

[Domshlak and Joachims, 2005] learns a linear discriminant ordinal utility function from a set of qualitative preference statements by a non-parametric model similar to hard margin SVM ordinal regression. The obtained utility function essentially specifies an item-wise preference partial ordering. In addition to the fact that our model is based on structural learning, their focus is not on learning an optimal subset.

[Brafman et al., 2006a] proposed a general way to specify preferences over sets of items. It first defines item properties from the attribute values of an item. The set properties are defined based on item properties and the set preferences are specified over set property values using TCP-nets [Brafman et al., 2006b] that yield a partial ordering. While the emphasis of [Brafman et al., 2006a] is the representation of set preferences, in our study we emphasize not the exact representation of set preferences, but the discriminative model in order to learn the most preferred set of items to maximize a set similarity measure, as we assume preferences are implicit and can take various forms.

[Binshtok et al., 2007] extends the work of [Brafman et al., 2006a]. They concentrate on the computational aspect of the NP-hard optimal subset selection after the set preferences are given in the formalism of [Brafman et al., 2006a]. They showed that they can improve the heuristic search over the property value method first pursued in [Brafman et al., 2006a], by carefully designed pruning mechanisms that efficiently rid many sub-optimal property combinations. They also proposed a new search over sets heuristic that deals with more general preference models. Their work clearly differs from ours, as no learning is involved and the preference model is pre-defined.

[Yue and Joachims, 2008] learns to predict a subset of documents that is as diversified as possible using structured SVM. The diversity measure is defined as a linear function using a structured feature space that encodes the benefit of covering individual words. In our paper we deal with a more general problem by optimizing the set accuracy metric, as diversity can be defined as a particular preference.

[desJardins and Wagstaff, 2005] represents the preference over sets of items by "depth" preferences and "diversity" preferences. The objective value of a given preference and a subset of items is a linear combination of its "depth" value and "diversity" value. While "depth" can be decomposed into a weighted sum of functions on item features, "diversity" is measured with a combination of item features and subset features. They also proposed several greedy methods to find optimal subsets with known preferences, and compared the objective value of subsets found by greedy and exhaustive search methods which showed that the greedy methods can find near optimal subsets much more efficiently than the exhaustive search. The preference representation is considered more specific than [Brafman et al., 2006a] by [Binshtok et al., 2007].

[desJardins et al., 2006] extends [desJardins and Wagstaff, 2005], in which a preference learning mechanism (denoted DDpref) is introduced to learn the preference parameters for the model proposed in [desJardins and Wagstaff, 2005]. DDpref learns depth preferences through kernel density estimation (KDE) [Parzen, 1962] and diversity preferences by maximum a posteriori estimation. The experiments showed how DDpref improves the objective value of learned preferences as training set size increases. To our knowledge DDpref is the only existing method that learns user preferences from sets of objects and can predict optimal subsets for new ground sets of items. Therefore, we will compare our experimental results with DDpref's.

5 Experiment

5.1 Dataset Description

The main experiments are based on the CMU face image dataset we obtained through [Asuncion and Newman, 2007]. This data set contains face images of 20 different people with various poses (straight, left, right or up); expressions (neutral, happy, sad or angry), and eyes (open or with sunglasses). Each person has 28 to 32 quality face images. Each greyscale image contains 32*30 pixels and a pixel is represented using its integer intensity in the range [0,255]. To construct the experiment dataset for optimal subset learning, we separate the 20 people into two disjoint groups of size 12 and 8 to construct the training and testing sets. In order to generate one training example, we randomly sample 100 images of the 12 people, and compute the optimal subset using the preferences we will describe soon. The test set is generated in the same manner on the other 8 peoples' images. 200 training sets and 100 test sets, each with one ground set and an optimal subset, are generated for every preference task 1-5. A total of 2 ∗ 104 images (with repetitions) are used to construct the training set for each task.

The synthetic dataset was first used in [desJardins et al., 2006]. This dataset concerns learning optimal subsets of toy blocks. Each toy block is described using 4 integer values to represent its size, number of sides, color and bins. For task 68, we obtained 100 training sets and 100 testing sets using the block generator from [desJardins et al., 2006]. Each training and test set contains 100 blocks as the ground set, and the size of the optimal subsets are fixed at 20 due to the requirement of DDpref. The scale of the blocks dataset exceeds that used in [desJardins et al., 2006].

Table 1 gives the summary of the experiment dataset size of a single preference learning task in terms of the number of training sets (n), the number of test sets (m), the number of items in each train/test set (card.), the size of optimal subsets (k) and the number of features to describe an item in the set (f ea.).

The different underlying preferences to generate the dataset following our preference formalism in section 3 are listed below, with the first 5 preferences on the face images dataset and the last 3 on the toy blocks dataset:

1. (Independent of ground set) Choose all images that are open, straight, and happy or neutral.
2. (Dependent) If the ground set hasmore imageswith people wearing sunglasses than open face, choose all left, otherwise choose all right.
3. (Dependent) If the ground set has fewer happy faces than sad ones, chose happy images; otherwise choose sad faces.

1. (Dependent, reverse of task 2) If the ground set hasmore left than right images, choose all open, otherwise choose all sunglasses
2. (ComplexDependent) If open and happy images consist of more than 30% of ground set, and sad and sunglass images are fewer than open and happy, choose all sad, otherwise all angry images.
3. (Blocks Child) Want to choose a variety of multicolored, medium-sized blocks with few sides for a child to grasp.
4. (Blocks Mosaic) Want to create a mosaic with blocks of various shapes, with emphasis on simple, small blocks.
5. (Blocks Tower) Want to build a uniform tower with large, similar-sided blocks of the same color.

5.2 Set Accuracy Result

The results are summarized in Figure 3. All performance measures are averaged over the 100 test sets for each task. For the first five tasks on face images, SVMOS reports the best set accuracy results by varying the C parameter from 10-6 to 104. We also included the results where the C parameter is chosen from 5-fold cross validation on the training set (denoted by SVMCV ). For DDpref, we report the best results obtained from extensively tuning the α and K parameters, where α is the tradeoff constant between diversity and depth preferences and K is the required size of predicted subsets. The difference in performance between SVMOS and DDpref for all tasks except task 3 is significant at the 0.01 level with a signed rank test. Difference in task 3 is significant at the 0.1 level. SVMOS outperforms DDpref in all five tasks, while SVMCV outperforms DDpref other than task 3, in which the cross validation happens to find a substantially suboptimal C setting. For other tasks, the cross validation on the training set often finds the best parameter.

For the three toy block tasks, we supplied DDpref with the true optimal subset size K=20 as it is a constant for the generation of the dataset. Thus, DDpref will always predict a subset with the same cardinality as the true optimal subset. All performance differences are significant at the 0.01 level.

Again, both SVMOS and SVMCV predicted better subsets than DDpref in terms of the set accuracy measure.

5.3 More Evaluation Metrics

Results on Precision, Recall, F1 Score and Jaccard Index

Other than the proposed set accuracy measure, we also evaluated the experiment performance of SVMOS and DDpref using the other metrics discussed in section 2.2 to provide a more complete view, namely the precision and recall accuracy, the F1-score and Jacaard Index. All performance measures are calculated using the optimal subset and the predicted one from each test set, and are averaged over 100 test sets. Tables 2 and 3 present the results when the best set accuracy is achieved for both SVMOS and DDpref.

We can conclude from Table 2 that SVMOS outperforms DDpref in all four metrics. The only exception is task 3, where DDpref achieves better recall and F1-score.

In Table 3 the precision, recall and F1 scores for DDpref are exactly the same in each task, as DDpref always predicts the subset with the same cardinality as the optimal subset for a fixed K=20. SVMOS achieves higher scores for all metrics in the three tasks.

We note that both DDpref and SVMOS also learn a preference ranking order over items. In this paper, we focus on the performance of predicting the optimal subset and therefore do not compare the ranking performance, which can be defined separately.

Scalability Comparison

We study the scalability behavior by comparing the training time for both SVMOS and DDpref. Apart from the fact that SVMOS is implemented in C++ and DDpref in Java, we observed that SVMOS is orders of magnitude faster than DDpref during training. Although the training time depends on the particular parameter settings, in general SVMOS usually requires less than 10 minutes to train while the training time required by DDpref can be more than 10 hours on a machine with a 3.8GHz Intel CPU and 8GB memory. Figure 4 shows the detailed training time against different training set sizes for task 5, where the parameters are set to provide the best set accuracy. Both methods appeared to scale linearly in our experiments. During the testing phase, SVMOS has a runtime linear in the number of test cases, and DDpref uses a greedy method to select the optimal subset from the learned preferences. Both SVMOS and DDpref are efficient in the testing phase in terms of runtime.

6 Conclusion

In this paper we propose a new approach for the optimal subset selection problem. We model the problem as a structural learning problem that maximizes set similarity between the predicted subsets and the optimal ones. While previous work requires an explicit preference representation, our discriminative learning model SVMOS only assumes the existence of implicit user preferences. Our model therefore does not need the intermediate step of learning the parameters of a pre-defined preference function. Experiment results on a variety of the subset selection tasks have shown that SVMOS provides high quality testing results compared with a recent learning model.

Acknowledgments

We thank Thorsten Joachims for the discussions on structured learning methods. We also thank the reviewers for their comments and suggestions. This research was supported by AFOSR grant FA9950-08-1-0196, NSF grant 0713499, and NSF grant 0832782.