Learning to rank arises in many data mining applications, ranging from web search engine, online advertising to recommendation system. In learning to rank, the performance of a ranking model is strongly affected by the number of labeled examples in the training set; on the other hand, obtaining labeled examples for training data is very expensive and time-consuming. This presents a great need for the active learning approaches to select most informative examples for ranking learning; however, in the literature there is still very limited work to address active learning for ranking. In this paper, we propose a general active learning framework, expected loss optimization (ELO), for ranking. The ELO framework is applicable to a wide range of ranking functions. Under this framework, we derive a novel algorithm, expected discounted cumulative gain (DCG) loss optimization (ELO-DCG), to select most informative examples. Then, we investigate both query and document level active learning for raking and propose a two-stage ELO-DCG algorithm which incorporate both query and document selection into active learning. Furthermore, we show that it is flexible for the algorithm to deal with the skewed grade distribution problem with the modification of the loss function. Extensive experiments on real-world web search data sets have demonstrated great potential and effectiveness of the proposed framework and algorithms.

In performance display advertising a key metric of a campaign effectiveness is its conversion rate -- the proportion of users who take a predefined action on the advertiser website, such as a purchase. Predicting this conversion rate is thus essential for estimating the value of an impression and can be achieved via machine learning. One difficulty however is that the conversions can take place long after the impression -- up to a month -- and this delayed feedback hinders the conversion modeling. We tackle this issue by introducing an additional model that captures the conversion delay. Intuitively, this probabilistic model helps determining whether a user that has not converted should be treated as a negative sample -- when the elapsed time is larger than the predicted delay -- or should be discarded from the training set -- when it is too early to tell. We provide experimental results on real traffic logs that demonstrate the effectiveness of the proposed model.

Clickthrough and conversation rates estimation are two core predictions tasks in display advertising. We present in this article a machine learning framework based on logistic regression that is specifically designed to tackle the specifics of display advertising. The resulting system has the following characteristics: It is easy to implement and deploy, it is highly scalable (we have trained it on terabytes of data), and it provides models with state-of-the-art accuracy.

We consider the task of suggesting related queries to users after they issue their initial query to a web search engine. We propose a machine learning approach to learn the probability that a user may find a follow-up query both useful and relevant, given his initial query. Our approach is based on a machine learning model which enables us to generalize to queries that have never occurred in the logs as well. The model is trained on co-occurrences mined from the search logs, with novel utility and relevance models, and the machine learning step is done without any labeled data by human judges. The learning step allows us to generalize from the past observations and generate query suggestions that are beyond the past co-occurred queries. This brings significant gains in coverage while yielding modest gains in relevance. Both offline (based on human judges) and online (based on millions of user interactions) evaluations demonstrate that our approach significantly outperforms strong baselines.

Interleaving is an increasingly popular technique for evaluating information retrieval systems based on implicit user feedback. While a number of isolated studies have analyzed how this technique agrees with conventional offline evaluation approaches and other online techniques, a complete picture of its efficiency and effectiveness is still lacking. In this paper we extend and combine the body of empirical evidence regarding interleaving, and provide a comprehensive analysis of interleaving using data from two major commercial search engines and a retrieval system for scientific literature. In particular, we analyze the agreement of interleaving with manual relevance judgments and observational implicit feedback measures, estimate the statistical efficiency of interleaving, and explore the relative performance of different interleaving variants. We also show how to learn improved credit-assignment functions for clicks that further increase the sensitivity of interleaving.

Thompson sampling is one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly not very popular in the literature. We present here some empirical results using Thompson sampling on simulated and real data, and show that it is highly competitive. And since this heuristic is very easy to implement, we argue that it should be part of the standard baselines to compare against.

In this paper we propose a novel algorithm for multi-task learning with boosted decision trees. We learn several different learning tasks with a joint model, explicitly addressing the specifics of each learning task with task-specific parameters and the commonalities between them through shared parameters. This enables implicit data sharing and regularization. We evaluate our learning method on web-search ranking data sets from several countries. Here, multitask learning is particularly helpful as data sets from different countries vary largely in size because of the cost of editorial judgments. Our experiments validate that learning various tasks jointly can lead to significant improvements in performance with surprising reliability.

Learning to rank arises in many information retrieval applications, ranging from Web search engine, online advertising to recommendation system. In learning to rank, the performance of a ranking model is strongly affected by the number of labeled examples in the training set; on the other hand, obtaining labeled examples for training data is very expensive and time-consuming. This presents a great need for the active learning approaches to select most informative examples for ranking learning; however, in the literature there is still very limited work to address active learning for ranking. In this paper, we propose a general active learning framework, Expected Loss Optimization (ELO), for ranking. The ELO framework is applicable to a wide range of ranking functions. Under this framework, we derive a novel algorithm, Expected DCG Loss Optimization (ELO-DCG), to select most informative examples. Furthermore, we investigate both query and document level active learning for raking and propose a two-stage ELO-DCG algorithm which incorporate both query and document selection into active learning. Extensive experiments on real-world Web search data sets have demonstrated great potential and effective-ness of the proposed framework and algorithms.

Interleaving experiments are an attractive methodology for evaluating \nretrieval functions through implicit feedback. Designed as \na blind and unbiased test for eliciting a preference between two \nretrieval functions, an interleaved ranking of the results of two retrieval \nfunctions is presented to the users. It is then observed whether \nthe users click more on results from one retrieval function or the \nother. While it was shown that such interleaving experiments reliably \nidentify the better of the two retrieval functions, the naive \napproach of counting all clicks equally leads to a suboptimal test. \nWe present new methods for learning how to score different types \nof clicks so that the resulting test statistic optimizes the statistical \npower of the experiment. This can lead to substantial savings in \nthe amount of data required for reaching a target confidence level. \nOur methods are evaluated on an operational search engine over a \ncollection of scientific articles.

Some commercial web search engines rely on sophisticated machine learning systems for ranking web documents. Due to very large collection sizes and tight constraints on query response times, online efficiency of these learning systems forms a bottleneck. An important problem in such systems is to speedup the ranking process without sacrificing much from the quality of results. In this paper, we propose optimization strategies that allow short-circuiting score computations in additive learning systems. The strategies are evaluated over a state-of-the-art machine learning system and a large, real-life query log, obtained from Yahoo!. By the proposed strategies, we are able to speedup the score computations by more than four times with almost no loss in result quality.

We present an algorithm, witch , that learns to detect spam hosts or pages on the Web. Unlike most other approaches, it simultaneously exploits the structure of the Web graph as well as page contents and features. The method is efficient, scalable, and provides state-of-the-art accuracy on a standard Web spam benchmark.

In this article we propose Supervised Semantic Indexing (SSI), an algorithm that is trained on (query, document) pairs of text documents to predict the quality of their match. Like Latent Semantic Indexing (LSI), our models take account of correlations between words (synonymy, polysemy). However, unlike LSI our models are trained with a supervised signal directly on the ranking task of interest, which we argue is the reason for our superior results. As the query and target texts are modeled separately, our approach is easily generalized to different retrieval tasks, such as online advertising placement. Dealing with models on all pairs of words features is computationally challenging. We propose several improvements to our basic model for addressing this issue, including low rank (but diagonal preserving) representations, and correlated feature hashing (CFH). We provide an empirical study of all these methods on retrieval tasks based on Wikipedia documents as well as an Internet advertisement task. We obtain state-of-the-art performance while providing realistically scalable methods.

While numerous metrics for information retrieval are available in the case of binary relevance, there is only one commonly used metric for graded relevance, namely the Discounted Cumulative Gain (DCG). A drawback of DCG is its additive nature and the underlying independence assumption: a document in a given position has always the same gain and discount independently of the documents shown above it. Inspired by the "cascade" user model, we present a new editorial metric for graded relevance which overcomes this difficulty and implicitly discounts documents which are shown below very relevant documents. More precisely, this new metric is defined as the expected reciprocal length of time that the user will take to find a relevant document. This can be seen as an extension of the classical reciprocal rank to the graded relevance case and we call this metric Expected Reciprocal Rank (ERR). We conduct an extensive evaluation on the query logs of a commercial search engine and show that ERR correlates better with clicks metrics than other editorial metrics.

It is now widely recognized that user interactions with search results can provide substantial relevance information on the documents displayed in the search results. In this paper, we focus on extracting relevance information from one source of user interactions, i.e., user click data, which records the sequence of documents being clicked and not clicked in the result set during a user search session. We formulate the problem as a global ranking problem, emphasizing the importance of the sequential nature of user clicks, with the goal to predict the relevance labels of all the documents in a search session. This is distinct from conventional learning to rank methods that usually design a ranking model defined on a single document; in contrast, in our model the relational information among the documents as manifested by an aggregation of user clicks is exploited to rank all the documents jointly. In particular, we adapt several sequential supervised learning algorithms, including the conditional random field (CRF), the sliding window method and the recurrent sliding window method, to the global ranking problem. Experiments on the click data collected from a commercial search engine demonstrate that our methods can outperform the baseline models for search results re-ranking.

As with any application of machine learning, web search ranking requires labeled data. The labels usually come in the form of relevance assessments made by editors. Click logs can also provide an important source of implicit feedback and can be used as a cheap proxy for editorial labels. The main difficulty however comes from the so called position bias - urls appearing in lower positions are less likely to be clicked even if they are relevant. In this paper, we propose a Dynamic Bayesian Network which aims at providing us with unbiased estimation of the relevance from the click logs. Experiments show that the proposed click model outperforms other existing click models in predicting both click-through rate and relevance.

Large-margin structured estimation methods work by minimizing a convex upper bound of loss functions. While they allow for efficient optimization algorithms, these convex formulations are not tight and sacrifice the ability to accurately model the true loss. We present tighter non-convex bounds based on generalizing the notion of a ramp loss from binary classification to structured estimation. We show that a small modification of existing optimization algorithms suffices to solve this modified problem. On structured prediction tasks such as protein sequence alignment and web page ranking, our algorithm leads to improved accuracy.

Applications of multi-class classification, such as document categorization, often appear in cost-sensitive settings. Recent work has significantly improved the state of the art by moving beyond ``flat'' classification through incorporation of class hierarchies [Cai and Hoffman 04]. We present a novel algorithm that goes beyond hierarchical classification and estimates the latent semantic space that underlies the class hierarchy. In this space, each class is represented by a prototype and classification is done with the simple nearest neighbor rule. The optimization of the semantic space incorporates large margin constraints that ensure that for each instance the correct class prototype is closer than any other. We show that our optimization is convex and can be solved efficiently for large data sets. Experiments on the OHSUMED medical journal data base yield state-of-the-art results on topic categorization.

We study a pattern classification algorithm which has recently been proposed by Vapnik and coworkers. It builds on a new inductive principle which assumes that in addition to positive and negative data, a third class of data is available, termed the Universum. We assay the behavior of the algorithm by establishing links with Fisher discriminant analysis and oriented PCA, as well as with an SVM in a pro- jected subspace (or, equivalently, with a data-dependent reduced kernel). We also provide experimental results.

This paper considers kernels invariant to translation, rotation and dilation. We show that no non-trivial positive definite (p.d.) kernels exist which are radial and dilation invariant, only conditionally positive definite (c.p.d.) ones. Accordingly, we discuss the c.p.d. case and provide some novel analysis, including an elemen- tary derivation of a c.p.d. representer theorem. On the practical side, we give a support vector machine (s.v.m.) algorithm for arbitrary c.p.d. kernels. For the thin- plate kernel this leads to a classifier with only one parameter (the amount of regu- larisation), which we demonstrate to be as effective as an s.v.m. with the Gaussian kernel, even though the Gaussian involves a second parameter (the length scale).

We present a general boosting method extending functional gradient boosting to optimize complex loss functions that are encountered in many machine learning problems. Our approach is based on optimization of quadratic upper bounds of the loss functions which allows us to present a rigorous convergence analysis of the algorithm. More importantly, this general framework enables us to use a standard regression base learner such as decision trees for fitting any loss function. We illustrate an application of the proposed method in learning ranking functions for Web search by combining both preference data and labeled data for training. We present experimental results for Web search using data from a commercial search engine that show significant improvements of our proposed methods over some existing methods.

Most literature on support vector machines (SVMs) concentrates on the dual optimization problem. In this letter, we point out that the primal problem can also be solved efficiently for both linear and nonlinear SVMs and that there is no reason for ignoring this possibility. On the contrary, from the primal point of view, new families of algorithms for large-scale SVM training can be investigated.

Semi-Supervised Support Vector Machines (S3VMs) are an appealing method for using unlabeled data in classification: their objective function favors decision boundaries which do not cut clusters. However their main problem is that the optimization problem is non-convex and has many local minima, which often results in suboptimal performances. In this paper we propose to use a global optimization technique known as continuation to alleviate this problem. Compared to other algorithms minimizing the same objective function, our continuation method often leads to lower test errors.

An intuitive approach to utilizing unlabeled data in kernel-based classification algorithms is to simply treat unknown labels as additional optimization variables. For margin-based loss functions, one can view this approach as attempting to learn low-density separators. However, this is a hard optimization problem to solve in typical semi-supervised settings where unlabeled data is abundant. The popular Transductive SVM algorithm is a label-switching-retraining procedure that is known to be susceptible to local minima. In this paper, we present a global optimization framework for semi-supervised Kernel machines where an easier problem is parametrically deformed to the original hard problem and minimizers are smoothly tracked. Our approach is motivated from deterministic annealing techniques and involves a sequence of convex optimization problems that are exactly and efficiently solved. We present empirical results on several synthetic and real world datasets that demonstrate the effectiveness of our approach.

Semi-supervised SVMs (S3 VM) attempt to learn low-density separators by maximizing the margin over labeled and unlabeled examples. The associated optimization problem is non-convex. To examine the full potential of S3 VMs modulo local minima problems in current implementations, we apply branch and bound techniques for obtaining exact, global ly optimal solutions. Empirical evidence suggests that the globally optimal solution can return excellent generalization performance in situations where other implementations fail completely. While our current implementation is only applicable to small datasets, we discuss variants that can potentially lead to practically useful algorithms.

We consider the task of tuning hyperparameters in SVM models based on minimizing a smooth performance validation function, e.g., smoothed k-fold crossvalidation error, using non-linear optimization techniques. The key computation in this approach is that of the gradient of the validation function with respect to hyperparameters. We show that for large-scale problems involving a wide choice of kernel-based models and validation functions, this computation can be very efficiently done; often within just a fraction of the training time. Empirical results show that a near-optimal set of hyperparameters can be identified by our approach with very few training rounds and gradient computations. .

We consider the problem of constructing a function whose zero set is to represent a surface, given sample points with surface normal vectors. The contributions include a novel means of regularising multi-scale compactly supported basis functions that leads to the desirable properties previously only associated with fully supported bases, and show equivalence to a Gaussian process with modified covariance function. We also provide a regularisation framework for simpler and more direct treatment of surface normals, along with a corresponding generalisation of the representer theorem. We demonstrate the techniques on 3D problems of up to 14 million data points, as well as 4D time series data.

Abstract We consider the problem of constructing a globally smooth analytic function that represents a surface implicitly by way of its zero set, given sample points with surface normal vectors. The contributions of the paper include a novel means of regularising multi‐scale compactly supported basis functions that leads to the desirable interpolation properties previously only associated with fully supported bases. We also provide a regularisation framework for simpler and more direct treatment of surface normals, along with a corresponding generalisation of the representer theorem lying at the core of kernel‐based machine learning methods. We demonstrate the techniques on 3D problems of up to 14 million data points, as well as 4D time series data and four‐dimensional interpolation between three‐dimensional shapes. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Curve, surface, solid, and object representations

Support vector machines (SVMs), though accurate, are not preferred in applications requiring great classification speed, due to the number of support vectors being large. To overcome this problem we devise a primal method with the following properties: (1) it decouples the idea of basis functions from the concept of support vectors; (2) it greedily finds a set of kernel basis functions of a specified maximum size (dmax) to approximate the SVM primal cost function well; (3) it is efficient and roughly scales as O(ndmax2) where n is the number of training examples; and, (4) the number of basis functions it requires to achieve an accuracy close to the SVM accuracy is usually far less than the number of SVM support vectors.

We discuss the problem of fitting an implicit shape model to a set of points sampled from a co-dimension one manifold of arbitrary topology. The method solves a non-convex optimisation problem in the embedding function that defines the implicit by way of its zero level set. By assuming that the solution is a mixture of radial basis functions of varying widths we attain the globally optimal solution by way of an equivalent eigenvalue problem, without using or constructing as an intermediate step the normal vectors of the manifold at each data point. We demonstrate the system on two and three dimensional data, with examples of missing data interpolation and set operations on the resultant shapes.

Choice-based conjoint analysis builds models of consumer preferences over products with answers gathered in questionnaires. Our main goal is to bring tools from the machine learning community to solve this prob- lem more efficiently. Thus, we propose two algorithms to quickly and accurately estimate consumer preferences. 1 Introduction Conjoint analysis (also called trade-off analysis) is one of the most popular marketing re- search technique used to determine which features a new product should have, by conjointly measuring consumers trade-offs between discretized1 attributes. In this paper, we will fo- cus on the choice-based conjoint analysis (CBC) framework [11] since it is both widely used and realistic: at each question in the survey, the consumer is asked to choose one product from several. The preferences of a consumer are modeled via a utility function representing how much a consumer likes a given product. The utility u(x) of a product x is assumed to be the sum of the partial utilities (or partworths) for each attribute, i.e. linear: u(x) = w x. However, instead of observing pairs (xl, yl), the training samples are of the form ({x1, . . . , xp}, y k k k ) indicating that among the p products {x1 , . . . , xp}, the yth was preferred. Without noise, k k k this is expressed mathematically by u(xyk ) u(xb ), b = y k k k . Let us settle down the general framework of a regular conjoint analysis survey. We have a population of n consumers available for the survey. The survey consists of a questionnaire of q questions for each consumer, each asking to choose one product from a basket of p. Each product profile is described through a attributes with l1, ..., la levels each, via a vector of length m = a l s=1 s, with 1 at positions of levels taken by each attribute and 0 elsewhere. Marketing researchers are interested in estimating individual partworths in order to per- form for instance a segmentation of the population afterwards. But traditional conjoint estimation techniques are not reliable for this task since the number of parameters m to be estimated is usually larger than the number of answers q available for each consumer. They estimate instead the partworths on the whole population (aggregated partworths). Here we 1e.g. if the discretized attribute is weight, the levels would be light/heavy. aim to investigate this issue, for which machine learning can provide efficient tools. We also address adaptive questionnaire design with active learning heuristics. 2 Hierarchical Bayes Analysis The main idea of HB2 is to estimate the individual utility functions under the constraint that their variance should not be too small. By doing so, the estimation problem is not ill-posed and the lack of information for a consumer can be completed by the other ones. 2.1 Probabilistic model In this section, we follow [11] for the description of the HB model and its implementation. This method aims at estimating the individual linear utility functions ui(x) = wi x, for 1 i n. The probabilistic model is the following: 1. The individual partworths wi are drawn from a Gaussian distribution with mean (representing the aggregated partworths) and covariance (encoding population's heterogeneity), 2. The covariance matrix has an invert Wishart prior, and has an (improper) flat prior. 3. Given a set of products (x1, . . . xp), the probability that the consumer i chooses the product x is given by exp(wi x) P (x|wi) = p . (1) exp(w b=1 i xb) 2.2 Model estimation We describe now the standard way of estimating , w (w1, . . . , wn) and based on Gibbs sampling and then propose a much faster algorithm that approximates the maximum a posteriori (MAP) solution. Gibbs sampling As far as we know, all implementations of HB rely on a variant of the Gibbs sampling [11]. During one iteration, each of the three sets of variables (, w and ) is drawn in turn from its posterior distribution the two others being fixed. Sampling for and is straightforward, whereas sampling from P (w|, , Y ) P (Y |w). P (w|, ) is achieved with the Metropolis-Hastings algorithm. When convergence is reached, the sampling goes on and finally outputs the empirical ex- pectation of , w and . Although the results of this sampling-based implementation of HB3 are impressive, practitioners complain about its computational burden. Approximate MAP solution So far HB implementations make predictions by evaluating (1) at the empirical mean of the samples, in contrast with the standard bayesian approach, which would average the rhs of (1) over the different samples, given samples w from the posterior. In order to alleviate the computational issues associated with Gibbs sampling, we suggest to consider the maximum of the posterior distribution (maximum a posteriori, MAP) rather than its mean. 2Technical papers of Sawtooth software [11], the world leading company for conjoint analysis softwares, provide very useful and extensive references. 3that we will call HB-Sampled or HB-S in the rest of the paper. To find , w and which maximize P (, w, |Y ), let us use Bayes' rule, P (, w, |Y ) P (Y |, w, ) P (w|, ) P (|) P () P (Y |w) P (w|, ) P () (2) Maximizing (2) with respect to yields MAP = I+Cw , with C n+d w being the "covariance" matrix of the wi centered at : Cw = (wi - )(wi - ) . Putting back this value in (2), we get - log P (, w, MAP|Y ) = - log P (Y |w) + log |I + Cw()| + C, (3) where C is an irrelevant constant. Using the model (1), the first term in the rhs of (3) is convex in w, but not the second term. For this reason, we propose to change log |I + Cw| by trace(Cw) = ||wi - ||2 (this would be a valid approximation if trace(Cw) 1). With this new prior on w, the rhs of (3) becomes n W (, w) = - log P (Yi|wi) + ||wi - ||2. (4) i=1 As in equation (3), this objective function is minimized with respect to when is equal to the empirical mean of the wi. We thus suggest the following iterative scheme to minimize the convex functional (4): 1. For a given , minimize (4) with respect to each of the wi independently. 2. For a given w, set to the empirical mean4 of the w. Thanks to the convexity, this optimization problem can be solved very efficiently. A New- ton approach in step 1, as well as in step 2 to speed-up the global convergence to a fixed point , has been implemented. Only couple of steps in both cases are necessary to reach convergence. Remark The approximation from equation (3) to (4) might be too crude. After all it boils down to setting to the identity matrix. One might instead consider as an hyperparam- eter and optimize it by maximizing the marginalized likelihood [14]. 3 Conjoint Analysis with Support Vector Machines Similarly to what has recently been proposed in [3], we are now investigating the use of Support Vector Machines (SVM) [1, 12] to solve the conjoint estimation problem. 3.1 Soft margin formulation of conjoint estimation Let us recall the learning problem. At the k-th question, the consumer chooses the yth k product from the basket {x1 , . . . , xp}: w xyk w xb , b = y k k k k k . Our goal is to estimate the individual partworths w, with the individual utility function now being u(x) = w x. With a reordering of the products, we can actually suppose that yk = 1. Then the above inequalities can be rewritten as a set of p - 1 constraints: w (x1 - xb ) 0, 2 b p. k k (5) Eq. (5) shows that the conjoint estimation problem can be cast as a classification problem in the product-profiles differences space. From this point of view, it seems quite natural to use state-of-the-art classifiers such as SVMs for this purpose. 4which is consistent with the L2-loss measuring deviations of wi-s from . More specifically, we propose to train a L2-soft margin classifier (see also [3] for a similar approach) with only positive examples and with a hyperplane passing through the origin (no bias), modelling the noise in the answers with slack variables kb: Minimize w2 + C q p 2 k=1 b=2 kb subject to w (x1 - xb ) 1 - k k kb. 3.2 Estimation of individual utilities It was proposed in [3] to train one SVM per consumer to get wi and to compute the individual partworths by regularizing with the aggregated partworths w = 1 n w n i=1 i: w = wi+w . i 2 Instead, to estimate the individual utility partworths wi, we suggest the following opti- mization problem (the set Qi contains the indices j such that the consumer i was asked to choose between products x1 , . . . , xp) : k k ~ Minimize w2 + C p 2 + C p 2 i qi kQi b=2 kb q b=2 kb j=i j k / Qi subject to wi (x1 - xb ) 1 - k k kb, k, b 2 . Here the ratio C determines the trade-off between the individual scale and the aggregated ~ C one.5 For C = 1, the population is modeled as if it were homogeneous, i.e. all partworths ~ C wi are equal. For C 1, the individual partworths are computed independently, without ~ C taking into account aggregated partworths. 4 Related work Ordinal regression Very recently [2] explores the so-called ordinal regression task for ranking, and derive two techniques for hyperparameters learning and model selection in a hierarchical bayesian framework, Laplace approximation and Expectation Propagation respectively. Ordinal regression is similar yet distinct from conjoint estimation since train- ing data are supposed to be rankings or ratings in contrast with conjoint estimation where training data are choice-based. See [4] for more extensive bibliography. Large margin classifiers Casting the preference problem in a classification framework, leading to learning by convex optimization, was known for a long time in the psycho- metrics community. [5] pioneered the use of large margin classifiers for ranking tasks. [3] introduced the kernel methods machinery for conjoint analysis on the individual scale. Very recently [10] proposes an alternate method for dealing with heterogeneity in conjoint analysis, which boils down to a very similar optimization to our HB-MAP approximation objective function, but with large margin regularization and with minimum deviation from the aggregated partworths. Collaborative filtering Collaborative filtering exploits similarity between ratings across a population. The goal is to predict a person's rating on new products given the person's past ratings on similar products and the ratings of other people on all the products. Again collaborative is designed for overlapping training samples for each consumer, and usually rating/ranking training data, whereas conjoint estimation usually deals with different ques- tionnaires for each consumer and choice-based training data. 5C ~ C In this way, directions for which the xj , j Qi contain information are estimated accurately, whereas the others directions are estimated thanks to the answers of the other consumers. 5 Experiments Artificial experiments We tested our algorithms on the same benchmarking artificial ex- perimental setup used in [3, 16]. The simulated product profiles consist of 4 attributes, each of them being discretized through 4 levels. A random design was used for the question- naire. For each question, the consumer was asked to choose one product from a basket of 4. A population of 100 consumers was simulated, each of them having to answer 4 questions. Finally, the results presented below are averaged over 5 trials. The 100 true consumer partworths were generated from a Gaussian distribution with mean (-, -/3, /3, ) (for each attribute) and with a diagonal covariance matrix 2I. Each answer is a choice from the basket of products, sampled from the discrete logit-type distri- bution (1). Hence when (called the magnitude6) is large, the consumer will choose with high probability the product with the highest utility, whereas when is small, the answers will be less reliable. The ratio 2/ controls the heterogeneity7 of the population. Finally, as in [3], the performances are computed using the mean of the L2 distances be- tween the true and estimated individual partworths (also called RMSE). Beforehand the partworths are translated such that the mean on each attribute is 0 and normalized to 1. Real experiments We tested our algorithms on disguised industrial datasets kindly pro- vided by Sawtooth Software Inc., the world leading company in conjoint analysis soft- wares. 11 one-choice-based8 conjoint surveys datasets9 were used for real experiments below. The number of attributes ranged from 3 to 6 (hence total number of levels from 13 to 28), the size of the baskets, to pick one product from at each question, ranged from 2 to 5, and the number of questions ranged from 6 to 15. The numbers of respondents ranged roughly from 50 to 1200. Since here we did not address the issue of no choice options in question answering, we removed10 questions where customers refused to choose a product from the basket and chose the no-choice-option as an answer11. Finally, as in [16], the performances are computed using the hit rate, i.e. the misprediction rate of the preferred product. 5.1 Analysis of HB-MAP We compare in this section our implementation of the HB method described in Section 2, that we call HB-MAP, to HB-S, the standard HB implementation. The average training time for HB-S was 19 minutes (with 12000 iterations as suggested in [11]), whereas our implementation based on the approximation of the MAP solution took in average only 1.8 seconds. So our primary goal, i.e. to alleviate the sampling phase complexity, was achieved since we got a speed-up factor of the order of 1000. The accuracy does not seem to be significantly weakened by this new implementation. Indeed, as shown in both Table 1 and Table 2, the performances achieved by HB-MAP were surprisingly often as good as HB-S's, and sometimes even a bit better. This might be 6as in [3], we tested High Magnitude ( = 3) and Low Magnitude ( = 0.5). 7It was either set to 2 = 3 or 2 = 0.5, respectively High and Low Heterogeneity cases. 8We limited ourselves to datasets in which respondents were asked to choose 1 product among a basket at each question. 9see [4] for more details on the numerical features of the datasets. 10One could use EM-based methods to deal with such missing training choice data. 11When this procedure boiled down to unreasonable number of questions for hold-out evaluation of our algorithms, we simply removed the corresponding individuals. explained by the fact that assuming that the covariance matrix is quasi-diagonal is a reason- able approximation, and that the mode of the posterior distribution is actually roughly close to the mean, for the real datasets considered. Additionally it is likely that HB-S may have demanded much more iterations for convergence to systematically behave more accurately than HB-MAP as one would have normally expected. 5.2 Analysis of SVMs We now turn to the SVM approach presented in section 3.2 that we call Im.SV12. We did not use a non-linear kernel in our experiments. Hence it was possible to minimize (3.2) directly in the primal, instead of using the dual formulation as done usually. This turned out to be faster since the number of constraints was, for our problem, larger than the number of variables. The resulting mean training time was 4.7 seconds. The so-called chapspan, span estimate of leave-one-out prediction error [17], was used to select a suitable value of C13, since it gave a quasi-convex estimation on the regularization path. The performances of Im.SV in Table 2, compared to the HB methods and logistic regression [3] are very satisfactory in case of artificial experiments. In real experiments, Im.SV gives overall quite satisfactory results, but sometimes disappointing ones in Table 2. One reason might be that hyperparameters (C, ~ C) were optimized once for the whole population. This may also be due to the lack of robustness14 of Im.SV to heterogeneity in the number of training samples for each consumer. Table 1: Average RMSE between estimated and true individual partworths Mag Het HB-S HB-MAP Logistic Im.SV L L 0.90 0.83 0.84 0.86 L H 0.95 0.91 1.16 0.90 H L 0.44 0.40 0.43 0.41 H H 0.72 0.68 0.82 0.67 Table 2: Hit rate performances on real datasets. Im.SV HB-MAP HB-S Im.SV HB-MAP HB-S Dat12 0.16 0.16 0.17 Dat15 0.52 0.45 0.48 Dat22 0.15 0.13 0.15 Dat25 0.58 0.47 0.51 Im.SV HB-MAP HB-S Im.SV HB-MAP HB-S Dat13 0.37 0.24 0.25 Dat1 Dat2 4 0.33 0.36 0.35 3 0.34 0.33 0.33 Dat2 Dat3 4 0.33 0.36 0.28 3 0.35 0.28 0.24 Dat3 Dat4 4 0.45 0.40 0.25 3 0.35 0.31 0.28 Legend of Tables 1 and 2 The first two columns indicate the Magnitude and the Heterogeneity (High or Low). p in Datmp is the number of products respondents are asked to choose one from at each question. 12since individual choice data are Immersed in the rest of the population choice data, via the optimization objective 13We observed that the value of the constant ~ C was irrelevant, and that only the ratio C/ ~ C mat- tered. 14Indeed the no-choice data cleaning step might have lead to a strong unbalance to which Im.SV is maybe much more sensitive than HB-MAP or HB-S. 6 Active learning Motivation Traditional experimental designs are built by minimizing the variance of an estimator (e.g. orthogonal designs [6]). However, they are sub-optimal because they do not take into account the previous answers of the consumer. Therefore adaptive conjoint analysis was proposed [11, 16] for adaptively designing questionnaires. The adaptive design concept is often called active learning in machine learning, as the algorithm can actively select questions whose responses are likely to be informative. In the SVM context, a common and intuitive strategy is to select, as the next point to be labeled, the nearest one from the decision boundary (see for instance [15]). Experiments We implemented this heuristic for conjoint analysis by selecting for each question a set of products whose estimated utilities are as close as possible15. To compare the different designs, we used the same artificial simulations as in section 5, but with 16 questions per consumer in order to fairly compare to the orthogonal design. Table 3: Comparison of the RMSE achieved by different designs. Mag Het Random Orthogonal Adaptive L L 0.66 0.61 0.66 L H 0.62 0.56 0.56 H L 0.31 0.29 0.24 H H 0.49 0.45 0.34 Results in Table 3 show that active learning produced an adaptive design which seems efficient, especially in the case of high magnitude, i.e. when the answers are not noisy16.

The problem of feature selection is a difficult combinatorial task in machine learning and of high practical relevance, e.g. in bioinformatics. genetic algorithms (GAs) offer a natural way to solve this problem. In this paper, we present a special genetic algorithm, which especially takes into account the existing bounds on the generalization error for support vector machines (SVMs). This new approach is compared to the traditional method of performing cross-validation and to other existing algorithms for feature selection.

We address in this paper the question of how the knowledge of the marginal distribution P (x) can be incorporated in a learning algorithm. We suggest three theoretical methods for taking into account this distribution for regularization and provide links to existing graph-based semi-supervised learning algorithms. We also propose practical implementations.

Abstract Motivation: In drug discovery a key task is to identify characteristics that separate active (binding) compounds from inactive (non-binding) ones. An automated prediction system can help reduce resources necessary to carry out this task. Results: Two methods for prediction of molecular bioactivity for drug design are introduced and shown to perform well in a data set previously studied as part of the KDD (Knowledge Discovery and Data Mining) Cup 2001. The data is characterized by very few positive examples, a very large number of features (describing three-dimensional properties of the molecules) and rather different distributions between training and test data. Two techniques are introduced specifically to tackle these problems: a feature selection method for unbalanced data and a classifier which adapts to the distribution of the the unlabeled test data (a so-called transductive method). We show both techniques improve identification performance and in conjunction provide an improvement over using only one of the techniques. Our results suggest the importance of taking into account the characteristics in this data which may also be relevant in other problems of a similar type. Availability: Matlab source code is available at http://www.kyb.tuebingen.mpg.de/bs/people/weston/kdd/kdd.html Contact: [email protected] Supplementary information: Supplementary material is available at http://www.kyb.tuebingen.mpg.de/bs/people/weston/kdd/kdd.html. * To whom correspondence should be addressed.

We propose a framework to incorporate unlabeled data in kernel classifier, based on the idea that two points in the same cluster are more likely to have the same label. This is achieved by modifying the eigenspectrum of the kernel matrix. Experimental results assess the validity of this approach.

We consider the learning problem of finding a dependency between a general class of objects and another, possibly different, general class of objects. The objects can be for example: vectors, images, strings, trees or graphs. Such a task is made possible by employing similarity measures in both input and output spaces using ker(cid:173) nel functions, thus embedding the objects into vector spaces. We experimentally validate our approach on several tasks: mapping strings to strings, pattern recognition, and reconstruction from par(cid:173) tial images.

The choice of an SVM kernel corresponds to the choice of a rep(cid:173) resentation of the data in a feature space and, to improve per(cid:173) formance, it should therefore incorporate prior knowledge such as known transformation invariances. We propose a technique which extends earlier work and aims at incorporating invariances in non(cid:173) linear kernels. We show on a digit recognition task that the pro(cid:173) posed approach is superior to the Virtual Support Vector method, which previously had been the method of choice.

The Vicinal Risk Minimization principle establishes a bridge between generative models and methods derived from the Structural Risk Mini(cid:173) mization Principle such as Support Vector Machines or Statistical Reg(cid:173) ularization. We explain how VRM provides a framework which inte(cid:173) grates a number of existing algorithms, such as Parzen windows, Support Vector Machines, Ridge Regression, Constrained Logistic Classifiers and Tangent-Prop. We then show how the approach implies new algorithm(cid:173) s for solving problems usually associated with generative models. New algorithms are described for dealing with pattern recognition problems with very different pattern distributions and dealing with unlabeled data. Preliminary empirical results are presented.

We introduce a method of feature selection for Support Vector Machines. The method is based upon finding those features which minimize bounds on the leave-one-out error. This search can be efficiently performed via gradient descent. The resulting algorithms are shown to be superior to some standard feature selection algorithms on both toy data and real-life problems of face recognition, pedestrian detection and analyzing DNA micro array data.

We introduce the concept of span of support vectors (SV) and show that the generalization ability of support vector machines (SVM) depends on this new geometrical concept. We prove that the value of the span is always smaller (and can be much smaller) than the diameter of the smallest sphere containing the support vectors, used in previous bounds (Vapnik, 1998). We also demonstrate experimentally that the prediction of the test error given by the span is very accurate and has direct application in model selection (choice of the optimal parameters of the SVM).

Traditional classification approaches generalize poorly on image classification tasks, because of the high dimensionality of the feature space. This paper shows that support vector machines (SVM's) can generalize well on difficult image classification problems where the only features are high dimensional histograms. Heavy-tailed RBF kernels of the form K(x, y) = e(-rho)Sigma(i)/xia-yia/b with a < or = 1 and b < or = 2 are evaluated on the classification of images extracted from the Corel stock photo collection and shown to far outperform traditional polynomial or Gaussian radial basis function (RBF) kernels. Moreover, we observed that a simple remapping of the input x(i)-->x(i)(a) improves the performance of linear SVM's to such an extend that it makes them, for this problem, a valid alternative to RBF kernels.