Transductive Optimization of Top k Precision

1 Introduction

In the Transductive Precision@k problem, the training set and the unlabeled test set are given, and the task is to predict exactly k test instances as positives. The precision of these selected instances-the fraction of correct positive predictions-is the only measure of importance. Our work is motivated by the problem of designing conservation reserves for an endangered species. Suppose a geographical region is divided into equal-sized cells of land. The species is present in positive cells and absent in negative cells. To protect the species, we seek to purchase some cells ("a conservation reserve"), and we want as many of those as possible to be positive cells. Suppose we have conducted a field survey of publicly-owned land to collect a training set of cells. With a fixed budget sufficient to purchase k cells, we want to decide which k privately-owned (and un-surveyed) cells to buy. In this paper, we assume that all cells have the same price. This is an instance of the Transductive Precision@k problem. Other instances arise in information retrieval and digital advertising.

⇤Nan Li is now working at Alibaba Group, Hangzhou China.

The standard approach to this problem is to first train a classifier or ranker on the training data and then threshold the predicted test scores to obtain the k top-ranked test instances. Any model that outputs continuous scores (e.g., an SVM) can be employed in this two-step process. Better results can often be obtained by bipartite ranking algorithms [Burges et al., 2005; Rudin, 2009; Usunier et al., 2009; Agarwal, 2011; Rakotomamonjy, 2012; Li et al., 2014; Kar et al., 2015], which seek to minimize a ranking loss. Recent work focuses even more tightly on the top-ranked instances. The MPG algorithm [Wang et al., 2015] formulates the ranking problem as an adversarial game and can optimize several ranking measures. The Accuracy At The Top (AATP) algorithm [Boyd et al., 2012] seeks to optimize the ranking quality for a specified top quantile of the training data. Maximizing accuracy on the top quantile is intractable, so AATP optimizes a relaxation of the original objective. However, none of the algorithms above explicitly considers the constraint of choosing k test instances in model training.

Unlike the ranking problems discussed so far, our problem is transductive, because we have the unlabeled test examples available. There is a substantial body of research on transductive classification [Joachims, 1999; Sindhwani and Keerthi, 2006; Pechyony, 2008; Li et al., 2013]. Most transductive classification algorithms are inspired by either the large margin principle or the clustering principle. The goal of these algorithms is to develop classifiers that will perform well on the entire test set. Some transductive classifiers [Joachims, 1999; Li et al., 2013] have a parameter to specify the desired ratio of positive predictions. However, such parameter is mainly used for training a stable classifier, and the ratio not strongly enforced on the test set.

In this paper, we claim that the knowledge of k helps to learn a better model in terms of the measure of top-k precision and that the trained model should be constrained to output a selection of k test instances as positive. We call this constraint the k-constraint. The benefit of incorporating k into the learning process can be understood in three ways. First, the k-constraint greatly reduces the hypothesis space and thus reduces the structural risk of the trained model. Second, the algorithm can take advantage of the knowledge of k to jointly optimize the scoring model and the score threshold with respect to the k-constraint. As a comparison, a two-step method trains a ranker that is optimal by some standard, but the ranker together with the threshold may not be optimal for the selection task. Third, the selection of k test points is directly obtained through model training, instead of learning a general classifier or ranker as an intermediate step. Vapnik's principle [Vapnik, 1998] dictates that we should not solve a more difficult problem on the way to solving the problem of interest.

In this paper, we jointly train the model and determine the threshold to obtain exactly k test instances as positive. We seek a decision boundary that predicts exactly k positives and has high precision on the training data. The paper proceeds as follows. We start by identifying a deterministic relation between the precision@k measure and the accuracy of any classifier that satisfies the k-constraint. This suggests that the learning objective should maximize classifier accuracy subject to the k-constraint. We adopt the space of linear decision boundaries and introduce an algorithm we call Transductive optimization of Top k precision (TTK). In the TTK optimization problem, the objective is to minimize the hinge loss on the training set subject to the k-constraint. This optimization problem is very challenging since it is highly non-convex. We first formulate this problem into an equivalent Mixed Integer Programming (MIP) problem and solve it with an off-theshelf MIP solver. This method works for small problems. To solve larger problems, we also design a feasible direction algorithm, which we find experimentally to converge very rapidly. Finally, our theoretical analysis of the transductive precision@k problem shows that one should train different scoring functions for different values of k. As a byproduct of the work, We also find a problem in the optimization algorithm used in AATP, which solves a problem similar to ours.

In the experiment section, we first present a small synthetic dataset to show how the TTK algorithm improves the SVM decision boundary. Then, we show that our feasible direction method can find solutions nearly optimal as global optimal solutions. In the third part, we compare the TTK algorithm with five other algorithms on ten datasets. The results show that the TTK algorithm matches or exceeds the performance of these state-of-the-art algorithms on almost all of these datasets.

2 The TTKmodel

Let the distribution of the data be D with support in X ⇥Y. In this work, we assume X = Rd and only consider the binary classification problem with Y = ¶-1↪ 1♦. By sampling from D independently, a training set (x↪ y) = (xi↪ yi)ni=1 and a test set (ˆx↪ ˆy) = (ˆxj↪ ˆ yj)mj=1 are obtained, but the labeling ˆy of the test set is unknown. The problem is to train a classifier and maximize the precision at k on the test set. The hypothesis space is H ⇢ Y X (functions mapping from X to Y). The hypothesis h 2 H is evaluated by the measure precision@k.

When we seek the best classifier from H for selecting k instances from the test set ˆx, we only consider classifiers satisfying the k-constraint, that is, these classifiers must be in the hypothesis space Hk(ˆx) = ¶h 2 H♣ Pmj=1 I[h(ˆxj) = 1] = k♦, where I[·] is 1 if its argument is true and 0 otherwise. All classifiers not predicting k positives on the test set are excluded from Hk. Note that any two-step method essentially reaches a classifier in Hk(ˆx) by setting a threshold in the second step to select k test instances. With these methods, the model optimized at the first step may be optimal in the original task, however, the classifier obtained by thresholding is often not optimal within Hk.

To maximize the precision of h 2 Hk(ˆx) on the test set, we essentially need to maximize the classification accuracy of h. This can be seen by the following relation. Let m- be the number of negative test instances, and let mtp, mfp and mtn denote the number of true positives, false positives, and true negatives (respectively) on the test set as determined by h. Then the precision@k of h can be expressed as

Since the number of negative test instances m- is unknown but fixed, there is a deterministic relationship between the accuracy (mtp +mtn)◁m and the precision@k on the test set. Hence, increasing classification accuracy directly increases the precision. This motivates us to maximize the accuracy of the classifier on the test set while respecting the k-constraint.

In this section, we develop a learning algorithm for linear classifiers and thus H = ¶h : X 7! Y↪ h(x;w↪ b) = sign(w>x + b)♦. Our learning objective is to minimize the (regularized) hinge loss on the training set, which is a convex upper bound of the zero-one loss. Together with the kconstraint, the optimization problem is

where [·]+ = max(·↪ 0) calculates the hinge loss on each instance. Due to the piece-wise constant function in the constraint, the problem is very hard to solve.

We relax the equality constraint to an inequality constraint and get the following optimization problem.

This relaxation generally does not change the solution to the optimization problem. If we neglect the constraint, then the solution that minimizes the objective will be an SVM. In our applications, there are typically significantly more than k positive test points, so the SVM will usually predict more than k positives. In that case, the inequality constraint will be active, and the relaxed optimization problem will give the same solution as the original problem 1 .

Even with the relaxed constraint, the problem is still hard, because the feasible region is non-convex. We first express the problem as a Mixed Integer Program (MIP). Let G be a large constant and ⌘ be a binary vector of length m. Then we can write the optimization problem as

Theorem 1 Optimization problems (3) and (4) are equivalent.

Proof: Since the two problems have the same objective that involves (w↪ b) only, we just need to show that the two constraint sets of the two problems are equivalent in terms of (w↪ b). Suppose (w1 ↪ b1 ) is a solution of (3), then at most k instances have positive scores. Let ⌘1 be a binary vector with length m. Set ⌘1 j = 1 if instance j has positive score, and set other entries of ⌘1 to get Pj ⌘1 j = k. Then (w1 ↪ b1 ↪ ⌘1 ) is a solution of (4). If (w2 ↪ b2 ↪ ⌘2 ) is a solution of (4), then at most k test instances get positive scores, and then (w2 ↪ b2 ) is a solution of (3). ⇤

For this MIP, a globally optimal solution can be found for small problem instances via the branch-and-bound method with an off-the-shelf package. We used Gurobi[Gurobi Optimization, 2015].

For large problem instances, finding the global optimum of the MIP is impractical. We propose to employ a feasible direction algorithm [Bazaraa et al., 2006], which is an iterative algorithm designed for constrained optimization. In each iteration, it first finds a descending direction in the feasible direction cone and then calculates a step size to make a descending step that leads to an improved feasible solution. The feasible direction algorithm fits this problem well. Because the constraint is a polyhedron, a step in any direction within the feasible direction cone will generate a feasible solution provided that the step length is sufficiently small. Since our objective is convex but the constraint is highly non-convex, we want to avoid making descending steps along the constraint boundary in order to avoid local minima.

In each iteration, we first need to find a descending direction. The subgradient (rw↪rb) of the objective with respect to (w↪ b) is calculated as follows. Let ⇠i = 1-yi (w>xi +b) be the hinge loss on instance i. Then

1 In the extreme case that many data points are nearly identical, the original problem may not have a solution while the relaxed problem always has one.

We need to project the negative subgradient (-rw↪-rb) to a feasible direction to get a feasible descending direction. Let L, E, and R be the sets of test instances predicted to be positive, predicted to be exactly on the decision boundary, and predicted to be negative:

With the constraint in (3), there can be at most k instances in L.

When (w↪ b) changes in a descending direction, no instance can move directly from L to R or from R to L without going though set E due to the continuity of its score. A feasible direction only allows (w↪ b) to moves no more than k - ♣L♣ from E to L. Therefore, the feasible direction cone is

To avoid that the descending direction moves exessive instances from E to L, we project the direction into the null space of a set B ✓ E of test instances, then the instances in B will stay in E. We also need to guarantee that no more than k - ♣L♣ instances in E ∩ B moves from E to L. Now the problem is how to find the set B.

We first sort the instances in E in descending order according to the value of -ˆx>j rw-rb. Let j 0 : 1  j 0  ♣E♣ re-index the instances in this order. To construct the set B, we start with B = ; and the initial direction (dw↪ db) = -(rw↪rb). The starting index is j0 = 1 if ♣L♣ = k, and j0 = 2 if ♣L♣ < k. Then with index j 0 starting from j0 and increasing, we consecutively put instance j 0 into B and project (dw↪ db) into the null space of ¶(ˆxj ◦ ↪ 1) : j ◦ 2 B♦. We stop at j 0 = j1 when the direction (dw↪ db) decreases the scores of all the remaining instances in E. The final projected direction is denoted by (d?w ↪ d?b ). The direction (d?w ↪ d?b ) has non-positive inner product with all instances with indices from j 0 = j0 to j 0 = ♣E♣, so these instances will not move into the set L when (w↪ b) moves in that direction. Only when ♣L♣ < k, is the first instance allowed to move from E to L. It is easy to check that the final projected direction (d?w ↪ d?b ) is in the feasible cone F and that it is a descending direction. This subgradient projection algorithm is summarized in Algorithm 1.

In this design, we have the following considerations. When ♣L♣ < k, the instance in E that has the largest inner product with the negative subgradient is allowed to enter set L. We allow at most one instance to move from E to L to reduce the chance that (w↪ b) hits the boundary. In the projecting iterations, instances with large inner products are selected first to reduce the number of projections.

Once a descending direction is chosen, we perform a line search to determine the step size. We first find the maximum step size ↵ that guarantees the feasibility of the descending step. That is, no points in R will cross the decision boundary and enter L with the step length ↵.

Algorithm 1 Find a descending feasible direction

Input: subgradient (rw↪rb), instance set ¶ˆxj : j 2 E♦,

size ♣L♣, k Output: descending feasible direction (d?w ↪ d?b ) Sort instances in E in descending order according to -ˆx>j rw - rb Initialize (dw↪ db) = -(rw↪ rb) Initialize B = ; j0 = min(k - ♣L♣↪ 1) + 1 for j 0 = j0 to ♣E♣ do if 9j 00 : j 0  j 00  ♣E♣↪ ˆx>j 00dw +db > 0 then B = B [ ¶j 0 ♦ project (dw↪ db) into the null space of (ˆxB↪ 1) else break end if end for d?w = dw, d?b = db

Then we do a line search in [0↪ 0▷5↵] to find the best step length ↵? . Note that the objective function is a convex piecewise quadratic function, so we only need to check these elbow points plus a minimum between two elbow points to find the best step length. We omit the details. The shrinkage 0▷5 of ↵ reduces the chance of (w↪ b) hitting the boundary.

We initialize w by training a standard linear SVM (although any linear model can be used) and then initialize b to satisfy the k-positive constraint. This gives us a pair (w↪ b) that is a feasible solution to (3). Then (w↪ b) is updated in each iteration according to (w↪ b) := (w↪ b) +↵? (d?w ↪ d?b ) until convergence.

We set the maximum number of iterations, T, to 500; the algorithm typically requires only 200-300 iterations to converge. In each iteration, the two most expensive calculations are computing the subgradient and projecting the negative subgradient. The first calculation requires O(nd) operations, and the second one takes at most O(ud2 ) operations, where u is the largest size of E. The overall running time is the time of training an initial model plus O(T (nd + ud2 )).

Though the problem is highly non-convex, the proposed projected subgradient method is very effective in practice, which is indicated by the comparison between solutions obtained by this method and optimal solutions obtained by Gurobi in the experiment section.

The AATP algorithm [Boyd et al., 2012] faces an optimization problem similar to (3) and uses a different relaxation to find an appoximate solution. Here we show that their relaxation is very loose. The AATP objective is equivalent to ours, and the difference is that the constraint is posed on the training set. Their constraint is that the top q quantile of training instances must receive positive scores and all others, negative scores. The AATP authors assume that the optimal decision boundary must go though a single training instance, so their relaxation of the optimization problem is constrained to require one instance to be on the decision boundary. However, their assumption is incorrect, since the optimal solution would put multiple instances on the boundary. So their relaxation is very loose, and their solutions classify much more than quantile q of the instances as positive. Our analysis is verified by the experiment results, which will be shown in the experiment section.

3 Analysis

Before presenting experiments, we first argue that different values of k require us, in general, to train different models. We work with the population distribution D instead of with samples, and we assume linear models. Suppose the distributions of positive instances and negative instances have probability measures θ+ and θ- defined on Rd . The total distribution is a mixture of the two distributions, and it has measure θ = λθ+ + (1 - λ)θ- with λ 2 (0↪ 1). The classifier (w↪ b) defines a positive region Rw↪b = ¶x 2 Rd ↪ w>x + b > 0♦. Assume θ+(Rw↪b) and θ-(Rw↪b) are both differentiable with respect to (w↪ b). If we consider classifiers that classify fraction q of the instances as positive, then θ(Rw↪b) = q. The precision of the classifier will be λθ+(Rw↪b) ◁ q. The optimal classifier is therefore

If we change q, we might hope that we do not need to modify w? but instead can just change b? . However, this is unlikely to work.

Theorem 2 If (w? ↪ b1) and (w? ↪ b2) are two optimal solutions for (8) with two different quantile values q1 and q2, then 9s1↪ t1↪ s2↪ t2↪ 2 R,

The proof follows directly from the KKT conditions. Note that (9) and (10) are two vector equations. When b1 is changed into be b2, the vectors of partial derivatives, @θ+(Rw? ↪b1 )◁@(w? ↪ b1) and @θ-(Rw? ↪b1 )◁@(w? ↪ b1) must change their directions in the same way to maintain optimality. This will only be possible for very special choices of θ+ and θ-. This suggests that (w? ↪ b? ) should be optimized jointly to achieve each target quantile value q.

4 Experimental Tests

4.1 An illustrative synthetic dataset

We begin with a simple synthetic example to provide some intuition for how the TTK algorithm improves the SVM decision boundary, see Figure 1. The dataset consists of 40 training and 40 test instances. The training and testing sets each contain 22 positive and 18 negative instances. Our goal is to select k = 4 positive test instances. The bold line is the decision boundary of the SVM. It is an optimal linear classifier both for overall accuracy and for precision@k for k = 24. However, when we threshold the SVM score to select 4 test instances, this translates the decision boundary to the dashed line, which gives very poor precision of 0.5. This dashed line is the starting point of the TTK algorithm. After making feasible direction descent steps, TTK finds the solution shown by the dot-dash-dot line. The k test instances selected by this boundary are all positive. Notice that if k = 24, then the SVM decision boundary gives the optimal solution. This provides additional intuition for why the TTK algorithm should be rerun whenever we change the desired value of k.

4.2 Effectiveness of Optimization

One way to compare different algorithms is to see how well they optimize the training and test surrogate loss functions. We trained standard SVM, AATP, and TTK on three UCI [Lichman, 2013] datasets: diabetes, ionosphere and sonar. The proposed TTK objective is solved by the MIP solver and the feasible direction method (denoted by TTKMIP and TTKFD ). We set k to select 5% of the test instances. For the SVM and AATP methods, we fit them to the training data and then obtain a top-k prediction by adjusting the intercept term b. We compare the regularized hinge loss on the training set and the hinge loss on the test set of each model after adjusting b, since the model with b adjusted is the true classifier used in the task. The hyper-parameter C is set to 1 for all methods. The results in Table 1 show that TTK with either solver obtains much lower losses than the competing methods. The small difference between the third (MIP) and the fourth (feasible direction) columns indicates that the feasible direction method finds near-optimal solutions.

The results also show that the AATP method does not minimize the objective very well. Due to its loose relaxation of the objective, the original AATP solution often predicts many more positives than the target quantile of 5% of the test instances. This requires to change the intercept term b to satisfy the k-constraint.

To further understand and compare the behavior of AATP and TTK, we performed a non-transductive experiment (by making the training and test sets identical). We measured the number of training instances that fall on the decision boundary and the fraction of training instances classified as positive (see Table 2). The optimal solution given by the MIP solver always puts multiple instances on the decision boundary, whereas the AATP method always puts a single instance on the boundary. The MIP always exactly achieves the de-

Table 1: Training and test loss attained by different methods. The symbol "+badj" indicates that the bias term is adjusted to satisfy the k-constraint

216 ◦ 22 213 ◦ 30 103 ◦ 19 105 ◦ 24

sired k, whereas AATP always classifies many more than k instances as positive. This shows that the AATP assumption that the decision boundary should pass through exactly one training instance is wrong.

4.3 Precision evaluation on real-world datasets

In this subsection, we evaluate our TTK method on ten datasets. Seven datasets, ¶diabetes, ionosphere, sonar, spambase, splice♦ from UCI repository and ¶german-numer, svmguide3♦ from the LIBSVM web site, are widely studied binary classification datasets. The other three datasets, NY16, NY18 and NY88, are three species distribution datasets extracted from a large eBird dataset [Sullivan et al., 2009]; each of them has 634 instances and 38 features. The eBird dataset contains a large number of checklists of bird counts reported from birders around the world. Each checklist is associated with the position of the observation and a set of 38 features describing the habitat. We chose a subset of the data consisting of checklists of three species from New York state in June of 2012. To correct for spatial sampling bias, we formed spatial cells by imposing a grid over New York and combining all checklists reported within each grid cell. This gives 634 cells (instances). Each instance is labeled with whether a species was present or absent in the corresponding cell.

We compare the proposed TTK algorithm with 5 other algorithms 2 . The SVM algorithm [Sch¨olkopf and Smola, 2002] is the baseline. The Transductive SVM (TSVM) [Joachims, 1999] compared here uses the UniverSVM [Sinz and Roffilli, 2012] implementation, which optimizes its objective with the convex-concave procedure. SVMperf [Joachims, 2005] can optimize multiple ranking measures and is parameterized here to optimize precision@k. Two algorithms, Accuracy At The Top (AATP) [Boyd et al., 2012] and TopPush [Li et al., 2014], are specially designed for top precision optimization. Each algorithm is run 10 times on 10 random splits of each dataset. Each of these algorithms requires setting the regularization parameter C. This was done by performing five 2-fold internal cross-validation runs within each training set and selecting the value of C from the set ¶0▷01↪ 0▷1↪ 1↪ 10↪ 100♦ that maximized precision on the top 5% of the (cross-validation) test points. With the chosen value of C, the algorithm was then run on the full training set (and unlabeled test set) and the precision on the top 5% was measured. The achieved precision values were then averaged across the 10 independent runs.

2 One reviewer suggests comparing our algorithm with the MPG algorithm [Wang et al., 2015]. We will provide the result of the comparison separately.

Table 3 shows the performance of the algorithms. For datasets with more than 1000 instances, the AATP and TTKMIP algorithms do not finish within a practical amount of time, so results are not reported for these algorithms on those datasets. This is indicated in the table by "NA". The results for each pair of algorithms are compared by a paireddifferences t-test at the p < 0▷05 significance level. If one algorithm is not significantly worse than any of the other algorithms, then it is regarded as one the best and its performance is shown in bold face. Wins, ties and losses of of TTKMIP and TTKFD with respect to all other algorithms are reported in the last two rows of Table 3.

On each of the six small datasets, the performance of TTKMIP matches or exceeds that of the other algorithms. The TTKFD method does almost as well-it is among the best algorithms on 8 of the 10 datasets. It loses once to SVMperf (on svmguide3) and once to AATP (on ionosphere). None of the other methods performs as well. By comparing TTKFD with SVM, we see that the performance is improved on almost all datasets, so the TTKFDmethod can be viewed as a safe treatment of the SVM solution. As expected, the transductive SVM does not gain much advantage from the availability of the testing instances, because it seeks to optimize accuracy rather than precision@k. The TopPush algorithm is good at optimizing the precision of the very top instance. But when more positive instances are needed, the TopPush algorithm does not perform as well as TTK.

5 Summary

This paper introduced and studied the transductive precision@k problem, which is to train a model on a labeled training set and an unlabeled test set and then select a fixed number k of positive instances from the testing set. Most existing methods first train a scoring function and then adjust a threshold to select the top k test instances. We show that by learning the scoring function and the threshold together, we are able to achieve better results.

We presented the TTK method. The TTK objective is the same as the SVM objective, but TTK imposes the constraint that the learned model must select exactly k positive instances from the testing set. This constraint guarantees that the final classifier is optimized for its target task. The optimization problem is very challenging. We formulated it as a mixed integer program and solved it exactly via an MIP solver. We also designed a feasible direction algorithm for large problems. We compared both TTK algorithms to several state-ofthe-art methods on ten datasets. The results indicate that the performance of the TTK methods matches or exceeds all of the other algorithms on most of these datasets.

Our analysis and experimental results show that the TTK objective is a step in the right direction. We believe that the performance can be further improved if we can minimize a tighter (possibly non-convex) bound on the zero-one loss.

Acknowledgments

This work has been supported primarily by CyberSEES: NSF Grant NSF 1331932. This work has also been partially supported by NSFC (61333014) and the Collaborative Innovation Center of Novel Software Technology and Industrialization of Nanjing University. Thank all reviewers for their comments and suggestions.