Extreme Regression for Dynamic Search Advertising

2020·Arxiv

ABSTRACT

ABSTRACT

This paper introduces a new learning paradigm called eXtreme Regression (XR) whose objective is to accurately predict the numerical degrees of relevance of an extremely large number of labels to a data point. XR can provide elegant solutions to many large-scale ranking and recommendation applications including Dynamic Search Advertising (DSA). XR can learn more accurate models than the recently popular extreme classifiers which incorrectly assume strictly binary-valued label relevances. Traditional regression metrics which sum the errors over all the labels are unsuitable for XR problems since they could give extremely loose bounds for the label ranking quality. Also, the existing regression algorithms won’t efficiently scale to millions of labels. This paper addresses these limitations through: (1) new evaluation metrics for XR which sum only the k largest regression errors; (2) a new algorithm called XReg which decomposes XR task into a hierarchy of much smaller regression problems thus leading to highly effi-cient training and prediction. This paper also introduces a (3) new labelwise prediction algorithm in XReg useful for DSA and other recommendation tasks.

Experiments on benchmark datasets demonstrated that XReg can outperform the state-of-the-art extreme classifiers as well as large-scale regressors and rankers by up to 50% reduction in the new XR error metric, and up to 2% and 2.4% improvements in terms of the propensity-scored precision metric used in extreme classifi-cation and the click-through rate metric used in DSA respectively. Deployment of XReg on DSA in Bing resulted in a relative gain of 27% in query coverage. XReg’s source code can be downloaded from [1]

CCS CONCEPTS

Computing methodologies → Machine Learning; Supervised learning by regression.

Microsoft Research India †Indian Institute of Technology Delhi ‡University of Washington §Work done during Research Fellowship at Microsoft Research India

KEYWORDS

Extreme classification, dynamic search advertising, regression

ACM Reference Format:

Yashoteja Prabhu, Aditya Kusupati, Nilesh Gupta, and Manik Varma. 2020. Extreme Regression for Dynamic Search Advertising. In The Thirteenth

February 3–7, 2020, Houston, TX, USA. ACM, New York, NY, USA, 15 pages. https://doi.org/10.1145/3336191.3371768

1 INTRODUCTION

Objective: This paper introduces a new learning paradigm called eXtreme Regression (XR) which can provide elegant solutions to many large-scale ranking and recommendation applications including Dynamic Search Advertising (DSA). To effectively solve XR problems, this paper also develops new evaluation metrics and a new highly scalable and accurate algorithm called XReg.

eXtreme Regression: The objective of eXtreme Regression is to learn to accurately predict the numerical degrees of relevance of an extremely large number of labels with respect to a data point. Many large-scale ranking and recommendation applications can naturally be reformulated as XR problems. For example, the tasks of DSA, movie recommendation and document tagging can be posed as the problems of predicting the search queries’ click probabilities for an ad, the users’ ratings for a movie and the informativeness of tags while describing a web document, respectively. These qualify as XR problems since the total number of queries, users and tags can potentially be in millions in these applications. The predicted relevance estimates could then be used to recommend the most relevant labels to a data point which is the desired end goal of recommendation systems. Alternatively, the recommendations can also be further refined by filtering off less relevant ones or by re-ranking them to improve their relevance, and the relevance estimates provide principled ways of achieving these. To successfully solve an XR problem, new algorithms which could train and predict efficiently over millions of labels as well as millions of data points while also maintaining high prediction accuracy are required. Furthermore, the definition of accuracy, or equivalently regression error, needs to be redefined for XR settings where both the relevant labels and the desired label recommendations are extremely small in number compared to the complete label set whose most labels have no influence on final recommendations. This paper addresses these challenges by developing new evaluation metrics and algorithms.

DSA: DSA is a format of search advertising where the ads to be shown against a search query, along with the associated ad-copy, ad-title, bid-phrases etc., are algorithmically obtained by leveraging the content from the ad landing pages. This saves considerable efforts for advertisers, results in faster deployment of new ad campaigns and enables more accurate user targeting. The ads shown by DSA algorithms need to be highly relevant and generate user clicks for the given query in order to earn revenue for the search engine and satisfy the users and advertisers. In addition, these algorithms need to train and predict very efficiently in order to scale to billions of ads and millions of search queries across multiple markets and maintain milliseconds’ prediction latencies. This paper solves DSA as an XR task of estimating the click probabilities for the query, ad pairs by using the new XReg algorithm. Note that different ads can have different click probabilities for same query owing to multiple query intents. For example the query "throne" on Bing refers to an online strategy war game, an online tv series and a furniture product with click probabilities of 0.2, 0.06 and 0.004 respectively. Based on the predicted click probabilities, the less clickable ads are filtered off, the remaining ads are re-ranked to promote those of high quality and high advertiser bids, and a small number of top ranked ads are finally shown for the given query.

Extreme Classification: Extreme classifiers annotate a data point with the most relevant subset of labels from an extremely large label set. Owing to their high scalability and accuracy in label subset selection scenarios, extreme classifiers are increasingly being used for DSA [46] and other large-scale recommendation problems. Unfortunately, they make a fundamentally incorrect assumption that a label is either fully relevant or fully irrelevant to a data point which hurts their model accuracy. When applied to DSA, they approximate all click-through rates to either 0 or 1 during training and thus end up predicting less clickable ads. In turn, this also undermines further filtering and re-ranking steps due to the lack of reliable click probability estimates. Also, the ranking at the top metrics used for evaluating extreme classifiers ignore the errors in estimating the relevances and are hence not suitable for XR.

Regression and ranking: Multivariate regressors predict multiple numerical outcome variables as functions of the features of a data point. Although such regressors could reliably estimate the label relevances in XR, most existing regressors are designed for small number of outcome variables and do not scale to millions of labels in XR. Moreover, the standard regression metrics such as Mean Absolute Deviation (MAD) which sum the regression errors over all the labels are unsuitable for XR problems because the quality of recommended labels, both before and after the filter-ing and re-ranking steps, depend only on the accurate estimation of a small number of label relevances. The pairwise ranking approaches, which ensure that a more relevant item is ranked ahead of a less relevant one for each pair of items, have been extensively used for moderate-sized ranking and recommendation tasks. However, their complexity scales quadratically in number of labels and therefore don’t scale to million labels.

eXtreme Regression metrics: This paper proposes new regression metrics for XR which serve as good proxies for the ranking accuracy and for the qualities of the subsequent label filtering and re-ranking steps. These metrics average of the largest few regression errors which are usually caused by highly underestimating or highly overestimating the relevances of the most or the least relevant labels which in turn degrade the ranking quality. The new XMAD@k metric can give up to 69x tighter bounds over ranking regret than MAD. These new metrics can guide the crucial steps in XR such as training, performance evaluation, hyper-parameter tuning, model selection etc.

eXtreme Regressor algorithm: This paper also develops a new eXtreme Regressor (XReg) algorithm which can efficiently regress on to millions of label relevance weights in only logarithmic time. XReg hierarchically clusters the labels into a balanced tree and learns approximate regressors in each tree node which are common to all the labels in the node. Due to high label sparsity, each data point only participates in a logarithmic number of tree nodes which can lead to a significant speed up during both training and prediction by using appropriate algorithms. XReg essentially extends the state-of-the-art Parabel extreme classifier to the regression setting. XReg consistently outperforms extreme classi-fiers, large-scale regressors and rankers in terms of ranking accuracy. On a DSA dataset with 5M ads & 1M queries, XReg can train within just 20 hours using 1 core, predict in just 3 ms per query and give up to 27% lift in query coverage when deployed online.

Labelwise inference: The standard prediction scenario involves recommending the most relevant labels for a test point, referred here as pointwise prediction, but applications such as DSA and movie recommendation can more naturally be posed in the reverse manner of predicting the most relevant ads or movies (i.e. test points) for each query or user (i.e. each label), referred here as labelwise prediction. On these tasks, pointwise prediction might recommend a small set of highly popular labels that are relevant to all test points resulting in low label coverage. This paper develops an efficient labelwise prediction algorithm in XReg, which significantly improves the query coverage in DSA. Note that the XReg training is agnostic to the choice of the prediction setting and the same learnt model works well for both types of predictions.

Contributions: This paper: (a) introduces a new learning paradigm called eXtreme Regression (XR) and reformulates tagging, movie recommendation and DSA applications as XR problems; (b) develops new evaluation metrics and a highly scalable and accurate algorithm called XReg to effectively tackle XR problems; and (c) demonstrates that XReg can significantly improve query coverage on Bing DSA when deployed in production. XReg’s source code can be downloaded from [1].

2 RELATED WORK

Extreme Classification: Much progress has recently been made in developing extreme multi-label classifiers based on trees [4, 26, 28, 45, 47, 52], embeddings [9, 11, 14, 19, 22, 37, 41, 54, 58, 61] and 1-vs-all approaches [5, 6, 25, 34, 38, 42, 46, 59, 62, 63, 66]. Among these, 1-vs-all approaches like DiSMEC [5], ProXML [6], Parabel [46] and Slice [25] achieve state-of-the-art results on Precision@k, nDCG@k and their propensity-scored counterparts, but train only from binary labels and are hence not apt for DSA. In terms of efficiency, Parabel is many orders faster to train and predict than DiSMEC and ProXML, hence XReg algorithm builds on top of Parabel. Slice only works on low-dimensional embeddings and does not scale to high-dimensional bag-of-words features used in this paper. Some

extreme classifiers like PfastreXML [26] and LEML [67] can be easily adapted to learn from any relevance weights, but they tend to be inaccurate and inefficient since they train a large ensemble of weak trees and inaccurate low-dimensional projections with linear reconstruction time, respectively. Performance of extreme classifiers has traditionally been measured in terms of Precision@k and nDCG@k [9, 47]. Recently, propensity-scored metrics were introduced in [26] which give higher importance to more useful and informative tail labels. However, all these metrics ignore the regression error in the predicted relevance estimates when applied to XR. Regression & ranking: Most of the conventional regression approaches [7, 17, 53, 56, 67] learn a separate regressor for each outcome variable and hence do not scale to millions of labels. This problem is mitigated to some extent in the multi-objective decision tree based approaches [4, 26, 32] which scale sublinearly in the number on outcome variables. However, these approaches suffer from low accuracy issues despite learning a large ensemble of weak trees. As seen from experiments, XReg can be significantly more scalable and accurate than the naive 1-vs-all least squares regressor [56], the more efficient LEML regressor with low-rank assumption on the parameter space [67] and the decision tree based PfastreXML [26]. The performance accuracy in regression have traditionally been measured by error metrics such as Mean Absolute Deviation (MAD) and Root Mean Square Error (RMSE) [10], but these are not appropriate for XR. Learning to rank methods [12, 16, 23, 35, 36, 43, 48, 50, 60, 65] have been widely used in the recommendation and ranking literatures, primarily to re-rank a small shortlist of items which has been generated by simple heuristics like tf-idf scoring or by more scalable approaches like extreme classifiers or XReg. These rankers usually have super-linear dependence on the number of labels and hence do not scale to XR. Although negative label sampling could potentially be used to make these approaches more scalable, their ranking performance suffers significantly as demonstrated in Section 5 for the popular RankSVM [21, 35] and the more recent eXtreme Learning to Rank (XLR) [12] approaches. A plethora of accuracy metrics have been proposed in the ranking literature [9, 27, 31, 36, 47, 55, 69], but none of these measure the regression performance. Dynamic search advertising: Various approaches have been proposed for DSA in the organic search literature including information retrieval based methods [29], probabilistic methods and topic models [57] and deep learning [24, 51]; however these do not work well for pithy ad-landing pages. Techniques based on landing page summarization [13], translation and query language models [49, 64] and keyword suggestion based on Wikipedia concepts [68] have also been proposed for sponsored search; but these suffer from low coverage problem. Extreme classifiers such as Parabel have also been used in DSA to improve accuracy and ad coverage; but they still suffer from low query coverage due to pointwise predictions. As demonstrated in Section 5, XReg significantly improves query coverage when included in the Bing DSA ensemble comprising all the above alternatives.

3 EXTREME REGRESSION METRICS

Notation: Let an XR dataset comprise N data points where dimensional feature vector and is a ground truth relevance weight vector for point i. The weight measures the true degree of relevance of label l to point i, with higher values indicating higher relevance. Similarly, let ˆdenote the predicted relevance weight vector for point i. The function S(v,k) indicates the ordered index set of the k highest scoring labels in a score vector

Regression & ranking metrics: The regression metrics such as MAD and RMSE; the ranking metrics such as relevance-weighted Precision and nDCG at k (WP@k, WN@k) and Kendall’s Tau at k (Tau@k) [31]; and WP@k-regret which is the difference between the optimal and the attained WP@k are pertinant for this paper. Their formulae are provided in the supplementary. The WP@k metric reduces to PSP@k, CTR@k suitable for DSA, or Rating@k based on whether are set to inverse propensity-scored relevances, ad click-through rates, or user ratings respectively. Rating@k is the undiscounted version of the familiar rating-based nDCG@k metric used in recommender systems [27].

be the vector of regression errors where . The new XR metrics, eXtreme Mean AbsoluteDeviation atk (XMAD@k) and eXtreme Root Mean Square Error at k (XRMSE@k) are defined as follows:

For ease of discussion, this paper mainly focusses on the XMAD metric, although most of the observations and results also apply to XRMSE. XMAD@k averages the k maximum regression errors but is minimized when all the L label relevances are predicted exactly right. The following lemma shows that XMAD serves as a good proxy for the ranking error. This is based on an intuition that the ranking errors at the top occur mainly due to either highly underestimating or highly overestimating the relevances of the most or the least relevant labels respectively leading to high regression errors on such labels.

Lemma 3.1. For any true and predicted relevance vectors WP-regret@holds true.

In addition, 0WP-regret@usually holds empirically (see Section 5) thus making XMAD error a close bound for the ranking error.

Although the top ranked labels with the highest predicted relevances could directly be recommended to a test point, it usually helps to further improve the recommendations by either filtering or re-ranking. The objective of filtering step is to maximize both precision and recall by removing as many irrelevant labels across as many test points as possible. This is crucial in DSA where there are system limitations against online hosting of too many relevant query, ad pairs. The following lemma shows that when the estimated label relevances are almost accurate in terms of the XMAD metric, almost ideal precision-recall trade-offs could be obtained by directly using a global threshold on the predicted relevances.

Lemma 3.2. Given a test set where the true and predicted relevance vectors of ith point are XMAD@k) holds true where are the attained and ideal areas under the micro-averaged precision-recall curves plotted using a global threshold.

The lemma assumes that the number of retained labels per each test point is less than k for the evaluated region of the curve. It is reasonable to set k = log(L) since only a small number of labels need to be recommended to each point.

Re-ranking the relevance estimates could significantly improve the final ranking quality, especially when the XMAD errors are small. An example of re-ranking is to combine these estimates with the scores from tail classifiers (see [26]) to improve the recommendation accuracies over rare labels. It is worth noting that bad relevance estimates, despite inducing a good initial ranking, could hurt the subsequent filtering or re-ranking performance. Unlike XMAD, the traditional MAD metric is sensitive to the sparsity in the ˆy vector which does not directly affect the ranking performance in any way. For example, MAD error becomes huge for a dense estimator like 1-vs-All least squares regressor since small regression errors could accrue over million labels into a large value. Results from Section 5 corroborate these observations.

Labelwise metrics: To evaluate performance in the labelwise prediction scenario, all the above ranking and regression metrics, defined for pointwise predictions, need to be redefined appropriately. The formulae for labelwise metrics are provided in the supplementary. Most discussions and results in this paper, while presented primarily for pointwise prediction case, also hold for labelwise prediction setting after interchanging the roles of data points and labels. To promote clarity, all pointwise and labelwise metrics will be used with suffixes "-p" and "-l" respectively.

Note that proofs for the lemmas in this section are available in the supplementary.

4 XREG: EXTREME REGRESSOR

This section describes XReg’s key components including the label tree construction, the probabilistic regression model and the pointwise and labelwise prediction algorithms using the same model.

4.1 Label Tree Construction

XReg learns a small ensemble of up to 3 label trees quite similarly to Parabel. Each tree is grown by recursively partitioning the labels into two balanced groups. Label partitioning is achieved by a balanced spherical k = 2-means algorithm [46] is which takes as input the feature vectors for all those labels in the current node and outputs 2 label clusters, efficiently, in time where ˆD is the number of non-zero features per data point. The feature vector for a label is represented by the unit vector that points along the average of the training points which are relevant to the label:

This is based on the intuition that two labels are similar if they are active in similar training points. In DSA, two queries (labels) are similar according to the proposed representation if they lead to clicks on similar ads (training points). As a result, the k-means algorithm ensures that the labels relevant for a data point end up in the same leaf. Note that, unlike Parabel, XReg uses non-binary relevance-weighted average leading to more informative label feature representations.

4.2 A Probabilistic Regression Model

XReg is a regression method which takes a probabilistic approach to estimating the label relevance weights. Firstly, all the relevance weights are normalized to lie between 0 and 1 by dividing by its maximum value, thus allowing them to be treated as probability values. Note that while click-through rates in DSA are already valid probabilities, the inverse propensities and the user rating could exceed 1. Also, note that the predicted estimates can be easily scaled back since no information is lost due to this normalization.

XReg treats the normalized relevance weights for each label as the marginal probability of its relevance to a data point, which is, in fact, the case in DSA. This allows XReg to minimize the KLdivergence between the true and the predicted marginal probability for each label with respect to each data point. KL-divergence [33] measures how close 2 distributions are and is minimized when the 2 are identical, thus justifying its use while regressing on to probability values.

A naive 1-vs-All approach, which learns a separate regressor minimizing KL-divergences for each label, would be extremely costly to train when labels are in millions. To reduce this complexity, XReg leverages the previously trained label tree. XReg expresses the marginal probability of a label as the probability that a data point traverses the tree path starting from the root to the label. Let the path from root to label l consist of nodes H is tree height, is the root and is the leaf node containing solely label denote the probability that a data point x visits the node after it has already visited the parent Then the true marginal probability that the label l is relevant to x is equivalent to . Similar equality holds for pre- dicted marginal probability: ˆ. XReg then learns to minimize an upper bound on the KL-divergence between the two according to the following theorem.

Proof. Proof is provided in the supplementary.

The unvisited node assumption formalizes the observation that the children of an unvisited internal node will never be traversed and that the labels in an unvisited leaf node will never be visited by a data point [46]. Due to the above theorem, XReg can separately minimize the KL-divergence over the true and predicted probabilities that a data point takes a particular edge in the tree, and still end up minimizing the KL-divergences over each of the individual marginal label probabilities. The true probability value of edge traversal is essentially the probability that the data point visits any of the labels in the subtree rooted at the node indexed lh. We instantiate it to be equal to the largest marginal probability of any label in the subtree, by assuming the worst-case scenario that labels in each subtree are fully correlated, which promotes model robustness.

The KL-divergence minimization is mathematically equivalent to training a logistic regressor for estimating values for each tree edge where every data point is duplicated with weights and 1

where n is used to index the node instead of only include those points which reach the node n. The problem in (Eq. 5) is strongly convex and was optimized using the modified CDDual algorithm available from Liblinear package [18]. To summarize, each internal node in XReg contains 2 1-vs-All regressors which give the probability that a data point traverses to each of its children, each leaf node contains M 1-vs-All regressors which gives the conditional probability of each label being relevant given the data point reaches its leaf.

We make a mild assumption that each data point has at most O(logL) positive labels is made which is often valid on extreme learning datasets. As a result, each data point traverses at most tree edges, which directly leads to a huge reduction in training complexity thus resulting in average number of non-zero features per data point. The following lemma describes how XReg’s training objective is related to the XMAD@k metric proposed earlier:

Lemma 4.2. XReg’s overall training objective minimizes an upper bound over XMAD@k for all k, with the bound being tighter for smaller k values.

Proof. The proof is provided in the supplementary.

4.3 Pointwise Inference

The pointwise inference algorithm in XReg utilizes the same beam search prediction technique proposed in Parabel where only the top ranked relevant labels are recommended based on a greedy, breadth-first tree traversal strategy. The following theorem proves that such traversal mechanism is not only asymptotically optimal for both WP@k and XMAD@k but also strongly generalizable with sample complexity. This uses the assumption that each data point has at most O(logL) positive labels. Also the theorem assumes that each individual regressor in well-generalizable and achieves zero-regret with infinite data samples.

Theorem 4.3. When each data point has at most O(logL) positive labels, the expected WP@k regret and XMAD@k error suffered by XReg’s pointwise inference algorithm are bounded by:

with probability at least 1 is the total training points, L is the number of labels, W is the maximum norm across all node classifier vectors and p is the minimum probability density of x distribution that any tree node receives.

Proof is available in the supplementary. Therefore the errors go to 0 as dependence arises because each data point visits at most log2 L nodes in a tree.

4.4 Labelwise Inference

The XReg model also allows efficient labelwise inference. The core idea here is to estimate from training data the fraction of points with non-zero relevance that visit each node of the tree and allot a factor F times the same fraction of top ranking test points to respective nodes. On large scale datasets with enough training and test points, the ratio of non-zero relevance points in each tree node remain almost the same over training and test points. The factor accounts for any small deviations. This strategy is adopted to ensure that all non-zero relevance points for a label end up reaching the label’s leaf node. Finally, the topmost scoring test points that visit a label’s leaf node are ranked at the top for that label, where the scores are marginal relevance probabilities, the average test time complexity is per test point. Pseudocode for labelwise inference is provided in the supplementary.

5 EXPERIMENTS

Datasets: Experiments were carried out on several medium and large scale benchmark datasets with up to 4.9M training points, 1.8M features and 1.4M labels (see Table 1 for dataset statistics). These datasets cover diverse applications such as document tagging (BibTeX [47], EURLex-4K [40], Wiki10-31K [8] & WikiLSHTC-325K [9, 44]), content-based movie recommendation (YahooMovie-8K [3] & MovieLens-138K [2, 20]), item-to-item recommendation of Amazon products (Amazon-670K [9, 39]), sponsored search advertising (SSA-130K) and dynamic search advertising (DSA-130K, DSA-1M). For ease of discussion, the label size suffixes are dropped from dataset names hereafter except for DSA. The document tagging, item-to-item recommendation, and SSA datasets require pointwise inference whereas the movie recommendation and DSA datasets require labelwise inference. YahooMovie and MovieLens use normalized (between 0 and 1) user-provided movie ratings as relevance weights and movie meta-data like summary, genres, and tags as features. For all the datasets, bag-of-words feature representation derived from text descriptions are used. SSA and DSA are proprietary datasets that were created by mining the Bing logs. Rest of the datasets are available from [1].

Baselines: XReg was compared to leading extreme classifiers such as PfastreXML [26], Parabel [46], DiSMEC [5] and ProXML [6], traditional multivariate regressors such as one-vs-all least-squares regression (1-vs-all-LS) and LEML [67], and a popular pairwise

Table 1: Dataset statistics

Table 2: XReg achieves the best or close to the best ranking and regression performance in both pointwise ("-p") and labelwise ("-l") prediction settings. Re-ranking with tail classifiers (XReg-t) further improves the performance in many cases. More results are in the supplementary.

ranker, RankSVM [21, 35]. XReg was also compared to the recent eXtreme Learning to Rank (XLR) [12] approach. ProXML is the current state-of-the-art over propensity scored precision@k (PSPp@k) during pointwise inference. Results for DiSMEC and ProXML, which required 1000s of cores, could not be replicated on large datasets and hence the numbers from the corresponding papers have been reporteddirectly. RankSVM was unable to scale to datasets larger than SSA-130K and hence required down-sampling of negatives up to 0.1% on these larger datasets. XLR, which specifically addresses the labelwise recommendation task, has only been applied to labelwise datasets. For the other baselines, results have been reported for only those datasets up to which the implementations scale. Since many of these large-scale datasets have a preponderance of tail labels, results for a variant of XReg where predicted labels have been reranked with tail classifier scores have also been

reported with a "-t" suffix. The tail classifiers are generative clas-sifiers which are tailored for accurate predictions on labels with < 5 training point samples [26]. For extreme classifiers which train on binary labels (Parabel, DiSMEC, and ProXML), all positive relevance weights were approximated to be fully relevant (value 1). Remaining baselines, including the PfastreXML and LEML, were trained on relevance weighted labels for a fair comparison.

Hyperparameters: XReg has 5 hyperparameters: (a) number of label trees in the ensemble (T); (b) number of tree paths explored by a test point during pointwise prediction (P); (c) maximum ratio of test to train points that traverse to each node during labelwise prediction (F); (d) maximum number of labels in a leaf node of XReg tree (M); and (e) regularization parameter common to logistic regressors in all the internal and leaf node classifiers (C). On medium-sized datasets, the XReg’s hyperparameters were set by fine-grained tuning over a 10% validation dataset. On larger datasets where tuning was not feasible, the default hyperparameter setting of T = 3, P = 10, F = 4, M = 100 and C = 10 was used. Results in table 8 of the supplementary demonstrates that the above default values of T, P, M achieve the best trade-off between accuracy and scalability across multiple datasets and increasing any of them further leads to minimal gains in accuracy while linearly increasing the training or prediction cost. The value of adjusts the influence of tail classifiers in XReg-t, was also tuned on the validation data. The hyperparameters for baseline algorithms were also set by tuning on medium datasets and set to defaults suggested in the respective papers/codebases on larger datasets.

Metrics and hardware: Performances were evaluated using accuracy metrics such as WP@k variants, Tau@k and XMAD@k (see Section 3) as well as efficiency metrics such as training time, test time per data point and model size. Among WP@k variants, for tagging (BibTeX, EURLex, Wiki10, WikiLSHTC) and Amazon datasets PSP@k are reported; for SSA and DSA which are ads datasets CTR@k is reported; and for movie recommendation datasets (YahooMovie and MovieLens) Rating@k is reported. All accuracy metrics are suffixed with "-p" or "-l" depending on whether the prediction scenario is pointwise or labelwise. All experiments were run on an Intel Xeon 2.5 GHz processor with 256 GB RAM.

Results on benchmark datasets: Table 2 compares XReg’s performance to diverse baselines on datasets belonging to tagging, recommendation and DSA applications. In terms of prediction accuracy, XReg consistently achieves close to best performance in terms of WP@5, Tau@5 as well as XMAD@5 metrics. In particular, XReg can be up to 2.4%, 3.89% and 2x better than all baselines in WP@5, Tau@5 and XMAD@5 respectively.

On most tagging datasets, XReg scores within 2% of the state-of-the-art ProXML in terms of the popular PSP@5 metric but can be up to 1000x faster during both training and prediction.

XReg consistently outperforms extreme classifiers like Parabel and DiSMEC which train only on binary labels. In particular, XReg can be up to 9% and 45% better than Parabel over pointwise and labelwise datasets in terms of WP@5. The larger gains on labelwise datasets are due to pointwise prediction in Parabel which can lead to low label coverage, especially on datasets like MovieLens with only 8K test points but around 140K labels. Owing to similar clas-sifier architectures, XReg can be highly efficient just like Parabel. XReg is at most 3.75x and 4.8x slower during training and prediction and has at most 2.15x the model size as Parabel.

Owing to their high scalability, both Parabel and XReg scale to the largest DSA-1M dataset where none of the other approaches scale. On this dataset, XReg has 50% smaller XMAD@5 than Parabel.

XReg-t denotes the re-ranked XReg where the predicted relevance estimates are combined with tail classifier scores to improve ranking performance over more informative tail labels. XReg-t consistently improves performance over XReg since most XR datasets are dominated by tail labels. XReg-t can be up to 5.66% and 5.58% better than XReg in terms of PSP@5 and Tau@5. However, XReg-t often increases XMAD@5 over XReg since tail classifiers are not regressors but are good generative classifiers which and therefore increase regression errors. Since the tail classifiers are extremely efficient to train and the re-ranking step is only applied to a small number (100s) of labels with high relevance estimates from XReg, XReg-t can be very efficient with 1.1, 1.96 and 2.8 times the training time, prediction time and model size as XReg in worst case.

Additional results for WP@k, Tau@k where k=1,3, nDCG@5 and XRMSE@5 are available in the supplementary.

Filtering and re-ranking: The accurate relevance weight estimates that XReg produces can be used for many downstream tasks such as filtering and re-ranking as discussed in Sections 1 and 3. Table 3 reports (1) AUPRC which measures the quality of filter-ing and (2) WP-rerank@5 which measures the quality of reranking with tail classifiers by using the relevance estimates generated by (a) Parabel, (b) XReg and (c) XReg-zero which corrupts XReg’s estimates by setting all relevances to almost 0 while maintaining the same rankings. As can be seen, XReg consistently outperforms Parabel and XReg-zero, both of which have higher regression errors as measured by XMAD@5, during both filtering and re-ranking. XReg-zero’s results demonstrate that just accurate ranking, as measured by the WP@5 column, is not enough for good filtering and re-ranking performance and that low regression errors are also necessary. Furthermore, regression errors measured in terms of traditional MAD are not reliable since MAD is sensitive to the sparsity in relevances and can in fact be lower for corrupted relevances such as in XReg-zero. Figures showing the AUPRC plots can be found in supplementary.

presents the relationship between XMAD & MAD to the ranking error (WP-regret@k). Table 4 shows that, across all the baselines, 2*XMAD@2k is a much better upper bound for WP-regret@k compared to the traditional MAD. Particularly, on regression and classi-fication techniques, 2*XMAD@2k is 1.35-5.84 times the WP-regret@k while MAD can be up to 69x larger than 2*XMAD@2k. In general, ranking baselines (RankSVM, XLR) do not produce good regression values making the ratio of 2*XMAD@2k and MAD to WPregret@k much higher. Lastly, for the dense score prediction algorithms like 1-vs-all-LS, MAD is significantly high since it sums up the errors across all labels.

Ablation Studies: To test the effectiveness of the proposedXReg along with its novel labelwise prediction algorithm, experiments were done to show the boost due to each of the factors. First, the extension of Parabel-logloss to utilize label weights lead to pointwise XReg which improved the ranking metrics up to 1.5% over Parabel across the 3 labelwise datasets showing that XReg can learn better from relevance weights. Further, when XReg was coupled with the novel labelwise prediction algorithm, the gains were up to 16%, 1.1% and 45% on YahooMovie-8K, DSA-130K, and MovieLens-138K respectively due to higher label coverage. Lastly, the use of tail classifiers with XReg (XReg-t) further increased the ranking performance by up to 0.7% over labelwise XReg.

DSA Results: Table 2 shows the offline evaluation on DSA-130K and DSA-1M while Table 6 showcases the results of the live deployment of labelwise XReg in Bing DSA pipeline. Even though few of the extreme classification techniques could scale to DSA-130K, the live deployment requires the techniques to scale to tens of millions of labels (queries) and data points (ads). In the actual deployment only PfastreXML, Parabel, and XReg were able to scale.

Table 6 compares XReg’s performance to the existing DSA ensemble, consisting of BM25 information retrieval based algorithm [29]

Table 3: XMAD@k is a better indicator of the filtering and re-ranking qualities than purely ranking metrics like WP@k or traditional regression metrics like MAD.

Table 4: Ranking regret at k is up to 69x more closely bounded by 2*XMAD@2k compared to the traditional MAD as proposed in Section 3. k = 5, "-p": pointwise, "-l": labelwise and "-t": use of tail classifiers. Please refer to the text for details.

Table 5: The ablation study of Parabel leading to per-label XReg-t which clearly outperforms its predecessors on ranking metrics.

Table 6: XReg significantly improves query coverage over the exist- ing ensemble for DSA on Bing. Note: Cov: Query Coverage, CY: Click Yield, IY: Impression Yield, BR: Bounce Rate

and PfastreXML when deployed on Bing. Both pointwise and labelwise XReg were deployed and evaluated. Pointwise XReg increased

RPM, CY, and IY by 5% while maintaining the CTR and BR. Finally, the labelwise XReg improves query coverage by 27% along with a 48% and 50% increase in click yield and impression yields at a cost of only 2% reduction in CTR.

6 CONCLUSIONS

This paper proposed a new learning paradigm called eXtreme Regression (XR) which provides a scalable solution to many real-world recommendation and ranking problems such as tagging, recommendation, DSA etc. XR involves learning to accurately predict the numerical relevance weights of an extremely large number of labels with respect to a data point. These weights not only induce an accurate ranking but are also useful for subsequent filtering and re-ranking steps. To effectively solve XR problems, this paper also develops a new evaluation metric called XMAD@k and a new algorithm called XReg. XReg consistently outperforms the state-of-the-art extreme classifiers as well as large-scale regressors and rankers in terms of ranking accuracies and efficiently scales to datasets with millions of data points and labels. Deployment of XReg on DSA in Bing resulted in a relative gain of 27% in query coverage.

7 ACKNOWLEDGEMENTS

We are grateful to Kunal Dahiya, Prateek Jain, Nagarajan Natarajan, Deepak Saini and Harsha Vardhan Simhadri for helpful discussions, feedback and computing resources.

REFERENCES

[1] [n. d.]. Code and datasets for XReg. http://manikvarma.org/code/XReg/download.html

[2] [n. d.]. MovieLens 20M Dataset. https://grouplens.org/datasets/movielens/20m/.

[3] [n. d.]. Yahoo! Movies User Ratings and Descriptive Content Information, v.1.0. https://webscope.sandbox.yahoo.com/catalog.php?datatype=r.

[4] R. Agrawal, A. Gupta, Y. Prabhu, and M. Varma. 2013. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In WWW.

[5] R. Babbar and B. Schölkopf. 2017. Dismec: Distributed sparse machines for ex- treme multi-label classification. In WSDM.

[6] R. Babbar and B. Schölkopf. 2018. AdversarialExtreme Multi-label Classification. arXiv preprint arXiv:1803.01570 (2018).

[7] R. Bekkerman, M. Bilenko, and J. Langford. 2011. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press.

[8] K. Bhatia, K. Dahiya, H. Jain, Y. Prabhu, and M. Varma. 2019. The Extreme Classification Repository: Multi-label Datasets & Code. http://manikvarma.org/downloads/XC/XMLRepository.html

[9] K. Bhatia, H. Jain, P. Kar, M. Varma, and P. Jain. 2015. Sparse Local Embeddings for Extreme Multi-label Classification. In NeurIPS.

[10] T. Chai and R. R. Draxler. 2014. Root mean square error (RMSE) or mean absolute error (MAE).

[11] Y. Chen and H. Lin. 2012. Feature-aware label space dimension reduction for multi-label classification. In NeurIPS.

[12] Minhao Cheng, Ian Davidson, and Cho-Jui Hsieh. 2018. Extreme Learning to Rank via Low Rank Assumption. In ICML.

[13] Y. Choi, M. Fontoura, E. Gabrilovich, V. Josifovski, M. R. Mediano, and B. Pang. 2010. Using landing pages for sponsored search ad selection. In WWW.

[14] M. Cissé, N. Usunier, T. Artières, and P. Gallinari. 2013. Robust Bloom Filters for Large MultiLabel Classification Tasks. In NeurIPS.

[15] K. Dembczyński, W. Kotłowski, W. Waegeman, R. Busa-Fekete, and E. Hüller- meier. 2016. Consistency of Probabilistic Classifier Trees. In Machine Learning and Knowledge Discovery in Databases.

[16] C. Dhanjal, R. Gaudel, and S. Clémençon. 2015. Collaborative filtering with lo- calised ranking. In AAAI.

[17] J Engel. 1988. Polytomous logistic regression. Statistica Neerlandica (1988).

[18] R. E. Fan, K. W. Chang, C. J. Hsieh, X. R. Wang, and C. J. Lin. 2008. LIBLINEAR: A library for large linear classification. JMLR (2008).

[19] C. Guo, A. Mousavi, X. Wu, D. N. Holtmann-Rice, S. Kale, S. Reddi, and S. Ku- mar. 2019. Breaking the Glass Ceiling for Embedding-Based Classifiers for Large Output Spaces. In NeurIPS.

[20] F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens Datasets: His- tory and Context. ACM Trans. Interact. Intell. Syst. (2015), 19:1–19:19.

[21] R. Herbrich, T. Graepel, and K. Obermayer. 1999. Support vector learning for ordinal regression. (1999).

[22] D. Hsu, S. Kakade, J. Langford, and T. Zhang. 2009. Multi-Label Prediction via Compressed Sensing. In NeurIPS.

[23] J. Hu and P. Li. 2018. Collaborative Multi-objective Ranking. In PCIKM.

[24] P. S. Huang, X. He, J. Gao, L. Deng, A. Acero, and L. P. Heck. 2013. Learning deep structured semantic models for web search using clickthrough data. In CIKM.

[25] H. Jain, V. Balasubramanian, B. Chunduri, and M. Varma. 2019. Slice: Scalable Linear Extreme Classifiers trained on 100 Million Labels for Related Searches. In WSDM.

[26] H. Jain, Y. Prabhu, and M. Varma. 2016. Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking and Other Missing Label Applications. In KDD.

[27] K. Järvelin and J. Kekäläinen. 2002. Cumulated gain-based evaluation of IR tech- niques. ACM Transactions on Information Systems (TOIS) 20, 4 (2002).

[28] K. Jasinska, K. Dembczynski, R. Busa-Fekete, K. Pfannschmidt, T. Klerx, and E. Hüllermeier. 2016. Extreme F-measure Maximization Using Sparse Probability Estimates. In ICML.

[29] K. S. Jones, S. Walker, and S. E. Robertson. 2000. A probabilisticmodel of informa- tion retrieval: development and comparative experiments. Inf. Process. Manage. (2000).

[30] S. M. Kakade, K. Sridharan, and A. Tewari. 2009. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In NeurIPS.

[31] M. G. Kendall. 1938. A new measure of rank correlation. Biometrika 30 (1938).

[32] D. Kocev, C. Vens, J. Struyf, and S. Dzeroski. 2007. Ensembles of multi-objective decision trees. In ECML.

[33] Solomon Kullback and Richard A Leibler. 1951. On information and sufficiency. The annals of mathematical statistics 22, 1 (1951), 79–86.

[34] A. Kusupati, M. Singh, K. Bhatia, A. Kumar, P. Jain, and M. Varma. 2018. Fast- GRNN: A Fast, Accurate, Stable and Tiny Kilobyte Sized Gated Recurrent Neural Network.. In NeurIPS.

[35] C. Lee and C. Lin. 2014. Large-scale linear ranksvm. Neural computation 26, 4 (2014), 781–817.

[36] J. Lee, S. Bengio, S. Kim, G. Lebanon, and Y. Singer. 2014. Local collaborative ranking. In WWW.

[37] Z. Lin, G. Ding, M. Hu, and J. Wang. 2014. Multi-label Classification via Feature- aware Implicit Label Space Encoding. In ICML.

[38] J. Liu, W. Chang, Y. Wu, and Y. Yang. 2017. Deep Learning for Extreme Multi- label Text Classification. In SIGIR.

[39] J. McAuley and J. Leskovec. 2013. Hidden factors and hidden topics: understand- ing rating dimensions with review text. In RecSys.

[40] E. L. Mencia and J. Fürnkranz. 2008. Efficient pairwise multilabel classification for large-scale problems in the legal domain. In ECML.

[41] P. Mineiro and N. Karampatziakis. 2015. Fast Label Embeddings for Extremely Large Output Spaces. In ECML.

[42] A. Niculescu-Mizil and E. Abbasnejad. 2017. Label ‘s for Large Scale Multilabel Classification. In AISTATS.

[43] D. Park, J. Neeman, J. Zhang, S. Sanghavi, and I. S. Dhillon. 2015. Preference com- pletion: Large-scale collaborative ranking from pairwise comparisons. In ICML.

[44] I. Partalas, A. Kosmopoulos, N. Baskiotis, T. Artières, G. Paliouras, É. Gaussier, I. Androutsopoulos, M. R. Amini, and P. Gallinari. 2015. LSHTC: A Benchmark for Large-Scale Text Classification. (2015). http://arxiv.org/abs/1503.08581

[45] Y. Prabhu, A. Kag, S. Gopinath, K. Dahiya, S. Harsola, R. Agrawal, and M. Varma. 2018. Extreme multi-label learning with label features for warm-start tagging, ranking and recommendation. In WSDM.

[46] Y. Prabhu, A. Kag, S. Harsola, R. Agrawal, and M. Varma. 2018. Parabel: Parti- tioned label trees for extreme classification with application to dynamic search advertising. In WWW.

[47] Y. Prabhu and M. Varma. 2014. FastXML: A fast, accurate and stable tree-classifier for extreme multi-label learning. In KDD.

[48] B. Pradel, N. Usunier, and P. Gallinari. 2012. Ranking With Non-Random Miss- ing Ratings: Influence Of Popularity And Positivity on Evaluation Metrics. In RecSys.

[49] S. Ravi, A. Z. Broder, E. Gabrilovich, V. Josifovski, S. Pandey, and B. Pang. 2010. Automatic generation of bid phrases for online advertising. In WSDM.

[50] D. Sculley. 2009. Large scale learning to rank. (2009).

[51] Y. Shen, X. He, J. Gao, L. Deng, and G. Mesnil. 2014. Learning semantic repre- sentations using convolutional neural networks for web search. In WWW.

[52] S. Si, H. Zhang, S. S. Keerthi, D. Mahajan, I. S. Dhillon, and C. J. Hsieh. 2017. Gradient Boosted Decision Trees for High Dimensional Sparse Output. In ICML.

[53] A. J. Smola and B. Schölkopf. 2004. A tutorial on support vector regression. Statistics and computing (2004).

[54] Y. Tagami. 2017. AnnexML: Approximate Nearest Neighbor Search for Extreme Multi-label Classification. In KDD.

[55] Y. Wang, L. Wang, Y. Li, D. He, and T. Liu. 2013. A theoretical analysis of NDCG type ranking measures. In COLT.

[56] G. S. Watson et al. 1967. Linear least squares regression. The Annals of Mathematical Statistics 38, 6 (1967), 1679–1699.

[57] X. Wei and W. B. Croft. 2006. LDA-based document models for ad-hoc retrieval. In SIGIR.

[58] J. Weston, S. Bengio, and N. Usunier. 2011. Wsabie: Scaling Up To Large Vocab- ulary Image Annotation. In IJCAI.

[59] J. Weston, A. Makadia, and H. Yee. 2013. Label Partitioning For Sublinear Rank- ing. In ICML.

[60] L. Wu, C. Hsieh, and J. Sharpnack. 2018. SQL-Rank: A Listwise Approach to Collaborative Ranking. In ICML.

[61] C. Xu, D. Tao, and C. Xu. 2016. Robust Extreme Multi-label Learning. In KDD.

[62] I. E. H. Yen, X. Huang, W. Dai, P. Ravikumar, I. Dhillon, and E. Xing. 2017. PPDsparse: A Parallel Primal-Dual Sparse Method for Extreme Classification. In KDD.

[63] I. E. H. Yen, X. Huang, P. Ravikumar, K. Zhong, and I. S. Dhillon. 2016. PD- Sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification. In ICML.

[64] W. T. Yih, J. Goodman, and V. R. Carvalho. 2006. Finding advertising keywords on web pages. In WWW.

[65] D. Yin, Y. Hu, J. Tang, T. Daly, M. Zhou, Hua Ouyang, Jianhui Chen, Changsung Kang, H. Deng, C. Nobata, et al. 2016. Ranking relevance in yahoo search. In PKDD.

[66] R. You, Z. Zhang, Z. Wang, S. Dai, H. Mamitsuka, and S. Zhu. 2019. AttentionXML: LabelTree-basedAttention-Aware Deep Model for High-Performance Extreme Multi-Label Text Classification. In NeurIPS.

[67] H. F. Yu, P. Jain, P. Kar, and I. S. Dhillon. 2014. Large-scale Multi-label Learning with Missing Labels. In ICML.

[68] W. Zhang, D. Wang, G. Xue, and H. Zha. 2012. Advertising Keywords Recom- mendation for Short-Text Web Pages Using Wikipedia. ACM TIST (2012).

[69] M. Zhu. 2004. Recall, Precision and Average Precision.

A THEOREMS AND PROOFS

Lemma A.1. Given any true and predicted relevance weight vectors , the following inequality hold true:

Table 7: XReg has the best or close to the best ranking and regression performance across all the datasets compared to state-of-the-art extreme classifiers and large-scale regressors and rankers. Re-ranking with tail classifiers (XReg-t) further improves the accuracies. PSP@k, CTR@k and Rating@k are variants of WP@k as discussed in Section 3. "-p": pointwise, "-l": labelwise.

Proof. The ranking and regression errors are defined as follows

Ranking-error@

Regression-error@

Since largest values of, Ranking-error@0 always. Due to summation over only non-negative values, Regressionerror@0 always too, which together establish the inequality 0

Now, let’s prove that . First, we begin by showing that Ranking-error@Without loss of generality, let’s assume that the sets

are non-overlapping. In the contrary case, the same arguments can be applied to another predicted set created by replacing the overlapping labels in with different labels having smaller ˆvalues. Thus bounding ranking error on bound it on

Table 8: Hyperparameter tuning for # trees (T ), Max leaf labels (M), Beam width (P) and points reaching leaf node per label in labelwise prediction of XReg. Note: The hyperparameters in bold face are finally chosen for the default setting.

Figure 1: Precision-Recall curves showing that XReg is consistently better than XReg-Zero and Parabel approaches for precision recall tradeoff.

1

Bounding the regression error is quite straightforward, hence we skip the proof here.

Finally, the XMAD@2follows by using Jensen’s inequality on the square function which is concave.

Proof. We assume that 0 log 01. We also use the unvisited node assumption in Parabel, 0) = 1, which means that a child of an unvisited node is never visited. Let be the probabilistic variable which says whetherlabel l is relevant to a data point in reference, and . Similarly let be the probabilistic variable which says whether the data point visits node not,

Now, since the relevance of label l to a data point is equivalent whether the label path is traversed in the tree by the data point: hold true.Due the fact that is a convex function, it is easy to show that the KL-divergence between 2 marginal distributions is upper bounded by the KL-divergence of the corresponding joint distributions.

The above upper bound is exactly the quantity that XReg minimizes during training by assuming logistic model for probability estimates.

Lemma A.3. XReg’s overall training objective minimizes an upper bound over XMAD@k for all k, with the bound being tighter for smaller k values.

Proof. As presented in the next theorem, XReg minimizes an upperbound on XMAD@1 . Note that XMAD@XMAD@1. Furthermore, ask increases, XMAD@k averages smaller and smaller errors compared the largest errors, therefore the bound is tighter for smaller values of k which are close to

Theorem A.4. When each data point has at most O(logL) positive labels, the expected WP@k regret and XMAD@k error suffered by XReg’s pointwise inference algorithm are bounded by:

with probability at least 1 is the total training points, L is the number of labels, W is the maximum norm across all node classifier vectors and p is the minimum probability density of x distribution that any tree node receives.

Proof. The outline of the proof is as follows. First, we see that the WP@k regret and XMAD@k error for a given data point are bounded, in a straight forward manner, by XReg’s node and label classifier objectives over that data point. For good overall generalization performance, each classifier needs to receive enough training samples as well as learn to generalize well from those samples. We derive probability bounds for those events simultaneously. While these steps together give the regret bounds for the classifier during exact prediction (i.e., calculate the scores for all labels for a given test point), the regret suffered by the greedy, beam-search algorithm might actually be more than that. Therefore, in a followup step, we also give a bound for this approximate algorithm which is only worse by O(logL). This gives us the final sample complexities.

By Lemma (7), both 12WP@k and XMAD@2k are bounded by XRMSE@2k which is in turn bounded by maxNow, using Pinsker’s inequality [15],

For good generalization performance, we need a small expected regret with respect to distribution over data point x:

Now we try to bound the above quantity by relating it to training error.

Let be the expected fraction of the probability density over x that a tree node n receives. This is precisely the density of data points which have at least one label with non-zero relevance in the subtree rooted at node n. Now, let’s compute the probability that the node n receives at least training points where N is the number of total training points and is the expected number of training points that node n would receive. By using chernoff bound, this probability is at least 1 . Now, the probability that all tree nodes n would simultaneously receive at least training points is at least 1 since there are at most L tree nodes and each has x density of at least p.

Now, we use the result in [30]. Since the logistic loss used for modeling probabilities in XReg is lipschitz continuous with constant 1 and logistic regression parameters are bounded by norm W , and x is bounded by norm 1, for any regressor in XReg,

with probability at least 1is the average training error in noden which is 0 as per our assumption.

Combining the above reasonings, along with the fact that there are at most 2L regressors in XReg, we can conclude that with probability of at least 1 node has expected error bounded simultaneously as below:

Now, note that k can be given any value in [0, 1] and the above bounds vary accordingly. We choose to give Then, with probability at least 1 all regressors

In other words, with probability at least 1 over the training samples, for all regressors,

where

for large enough N , the above bound can be approximated to

From (50),

with probability at least 1 over training samples.

The above bound holds for exact prediction where all label probabilities are computed for a given test point. Now we analyse the extra regret due to the greedy, approximate, beam search based, pointwise inference algorithm used by XReg.

During beam-search, a point traverses the tree level-by-level. At each tree level, a small shortlist of around k = 10 most probable nodes, i.e. nodes with most relevant labels their subtrees, are maintained and extended on to next level. If accurate label relevances were available, then beam search would always return the best set of labels, since each node’svariable value matches the most relevant label in its subtree. Unfortunately, due to generalization error, the estimated ˆvalues might not exactly match the values. As a result, the regret accumulates at each tree level whenever a node with lower is maintained in shortlist instead of the highest one. The regret suffered is at most maxset of shortlisted nodes at a tree level. A little more algebra reveals that this quantity is in fact bounded by (50).

which is the bound on the regret suffered by exact prediction algorithm. That is, beam-search can suffer at most the same amount of regret at each tree level that exact prediction suffers as a whole. Now since there are logL tree levels, the regret of beam search algorithm is bounded by