nips nips2008 nips2008-73 knowledge-graph by maker-knowledge-mining

73 nips-2008-Estimating Robust Query Models with Convex Optimization

Source: pdf

Author: Kevyn Collins-thompson

Abstract: Query expansion is a long-studied approach for improving retrieval effectiveness by enhancing the user’s original query with additional related words. Current algorithms for automatic query expansion can often improve retrieval accuracy on average, but are not robust: that is, they are highly unstable and have poor worst-case performance for individual queries. To address this problem, we introduce a novel formulation of query expansion as a convex optimization problem over a word graph. The model combines initial weights from a baseline feedback algorithm with edge weights based on word similarity, and integrates simple constraints to enforce set-based criteria such as aspect balance, aspect coverage, and term centrality. Results across multiple standard test collections show consistent and signiﬁcant reductions in the number and magnitude of expansion failures, while retaining the strong positive gains of the baseline algorithm. Our approach does not assume a particular retrieval model, making it applicable to a broad class of existing expansion algorithms. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract Query expansion is a long-studied approach for improving retrieval effectiveness by enhancing the user’s original query with additional related words. [sent-5, score-1.086]

2 Current algorithms for automatic query expansion can often improve retrieval accuracy on average, but are not robust: that is, they are highly unstable and have poor worst-case performance for individual queries. [sent-6, score-1.122]

3 To address this problem, we introduce a novel formulation of query expansion as a convex optimization problem over a word graph. [sent-7, score-1.12]

4 The model combines initial weights from a baseline feedback algorithm with edge weights based on word similarity, and integrates simple constraints to enforce set-based criteria such as aspect balance, aspect coverage, and term centrality. [sent-8, score-0.965]

5 Results across multiple standard test collections show consistent and signiﬁcant reductions in the number and magnitude of expansion failures, while retaining the strong positive gains of the baseline algorithm. [sent-9, score-0.495]

6 Our approach does not assume a particular retrieval model, making it applicable to a broad class of existing expansion algorithms. [sent-10, score-0.437]

7 1 Introduction A major goal of current information retrieval research is to develop algorithms that can improve retrieval effectiveness by inferring a more complete picture of the user’s information need, beyond that provided by the user’s query text. [sent-11, score-0.894]

8 A query model captures a richer representation of the context and goals of a particular information need. [sent-12, score-0.649]

9 For example, in the language modeling approach to retrieval [9], a simple query model may be a unigram language model, with higher probability given to terms related to the query text. [sent-13, score-1.553]

10 Once estimated, a query model may be used for such tasks as query expansion, suggesting alternate query terms to the user, or personalizing search results [11]. [sent-14, score-2.047]

11 In this paper, we focus on the problem of automatically inferring a query model from the top-ranked documents obtained from an initial query. [sent-15, score-0.742]

12 This task is known as pseudo-relevance feedback or blind feedback, because we do not assume any direct input from the user other than the initial query text. [sent-16, score-0.839]

13 Despite decades of research, even state-of-the-art methods for inferring query models – and in particular, pseudo-relevance feedback – still suffer from some serious drawbacks. [sent-17, score-0.78]

14 First, when term risk is ignored, the result will be less reliable algorithms for query models, as we show in Section 3. [sent-24, score-0.922]

15 Second, selection of expansion terms is typically done in a greedy fashion by rank or score, which ignores the properties of the terms as a set and leads to the problem of aspect imbalance, a major source of retrieval failures [2]. [sent-25, score-0.797]

16 Third, few existing expansion algorithms can operate selectively; that is, automatically detect when a query is risky to expand, and then avoid or reduce expansion in such cases. [sent-26, score-1.375]

17 Finally, for a given task there may be additional factors that must be constrained, such as the computational cost of sending many expansion terms to the search engine. [sent-28, score-0.409]

18 To our knowledge such situations are not handled by any current query model estimation methods in a principled way. [sent-29, score-0.679]

19 Our solution is to develop a novel formulation of query model estimation as a convex optimization problem [1], by casting the problem in terms of constrained graph labeling. [sent-31, score-0.937]

20 Informally, we seek query models that use a set of terms with high expected relevance but low expected risk. [sent-32, score-0.961]

21 Instead, we specify a (convex) objective function and a set of constraints that a good query model should satisfy, letting the solver do the work of searching the space of feasible query models. [sent-35, score-1.452]

22 ore generally, it gives a very ﬂexible framework for integrating different criteria for expansion as optimization constraints or objectives. [sent-37, score-0.491]

23 Term risk in turn has two subcomponents: the individual risk of a term, and the conditional risk of choosing one term given we have already chosen another. [sent-40, score-0.615]

24 These constraints are chosen to address traditional reasons for query drift. [sent-42, score-0.717]

25 With these two parts, we obtain a simple convex program for solving for the relative term weights in a query model. [sent-43, score-0.916]

26 2 Theoretical model Our aim in this section is to develop a constrained optimization program to ﬁnd stable, effective query models. [sent-44, score-0.763]

27 Typically, our optimization will embody a basic tradeoff between wanting to use evidence that has strong expected relevance, such as expansion terms with high relevance model weights, and the risk or conﬁdence in using that evidence. [sent-45, score-0.849]

28 We begin by describing the objectives and constraints over term sets that might be of interest for estimating query models. [sent-46, score-0.926]

29 We then describe a set of (sometimes competing) constraints whose feasible set reﬂects query models that are likely to be effective and reliable. [sent-47, score-0.799]

30 1 Query model estimation as graph labeling We can gain some insight into the problem of query model estimation by viewing the process of building a query as a two-class labeling problem over terms. [sent-50, score-1.58]

31 Given a vocabulary V , for each term t ∈ V we decide to either add term t to the query (assign label ‘1’ to the term), or to leave it out (assign label ‘0’). [sent-51, score-1.028]

32 The initial query terms are given a label of ‘1’. [sent-52, score-0.797]

33 The terms are typically related, so that the pairwise similarity σ(i, j) between any two terms wi , wj is represented by the weight of the edge connecting wi and wj in the undirected graph G = (V, E), where E is the set of all edges. [sent-54, score-0.597]

34 The square nodes X, Y, and Z represent query terms, and circular nodes represent potential expansion terms. [sent-57, score-0.975]

35 Additional constraints can select sets of terms having desirable properties for stable expansion, such as a bias toward relevant labels related to multiple query terms (right). [sent-59, score-0.87]

36 Our method obtains its initial assignment costs cs;j from a baseline feedback method, given an observed query and corresponding set of query-ranked documents. [sent-71, score-0.868]

37 For our baseline expansion method, we use the strong default feedback algorithm included in Indri 2. [sent-72, score-0.574]

38 In the next section, we discuss how to specify values for cs;j and σs,j;t,k that make sense for query model estimation. [sent-75, score-0.649]

39 , xK ) where each xi corresponds to the weight in the ﬁnal query model of term wi and thus is the relative value of each word in the expanded query. [sent-80, score-0.963]

40 The graph labeling formulation may be interpreted as combining two natural objectives: the ﬁrst maximizes the expected relevance of the selected terms, and the second minimizes the risk associated with the selection. [sent-81, score-0.49]

41 We now describe each of these in more detail, followed by a description of additional set-based constraints that are useful for query expansion. [sent-82, score-0.717]

42 2 Relevance objectives Given an initial set of term weights from a baseline expansion method c = (c1 , . [sent-84, score-0.692]

43 The initial assignment costs (label values) c can be set using a number of methods depending on how scores from the baseline expansion model are normalized. [sent-91, score-0.437]

44 We can also estimate a non-relevance model p(w|N ) using the collection to approximate non-relevant documents, or using the lowest-ranked k documents out of the top 1000 retrieved by the initial query Q. [sent-93, score-0.719]

46 3 Risk objectives Optimizing for expected term relevance only considers one dimension of the problem. [sent-101, score-0.435]

47 We adapt an informal deﬁnition of risk here in which the variance of the expected relevance is a proxy for uncertainty, encoded in the matrix Σ with entries σij . [sent-103, score-0.379]

48 Using a betting analogy, the weights x = {xi } represent wagers on the utility of the query model terms. [sent-104, score-0.695]

49 A risky strategy would place all bets on the single term with highest relevance score. [sent-105, score-0.429]

50 First, we consider the conditional risk σij between pairs of terms wi and wj . [sent-108, score-0.432]

51 We say that a term related to multiple query terms exhibits term centrality. [sent-115, score-0.947]

52 Previous work has shown that central terms are more likely to be more effective for expansion than terms related to few query terms [3] [12]. [sent-116, score-1.172]

53 We use term centrality to quantify a term’s individual risk, and deﬁne it for a term wi in terms of the vector di of all similarities of wi with all query terms. [sent-117, score-1.287]

54 (5) Y Bad Y Good (a) Aspect balance Y Low Y High (b) Aspect coverage Y Variable Y Centered (c) Term centering Figure 2: Three complementary criteria for expansion term weighting on a graph of candidate terms, and two query terms X and Y . [sent-119, score-1.515]

55 The aspect balance constraint (left) prefers sets of expansion terms that balance the representation of X and Y . [sent-120, score-0.811]

56 The aspect coverage constraint (center) increases recall by allowing more expansion candidates within a distance threshold of each term. [sent-121, score-0.669]

57 We can now combine relevance and risk into a single objective, and control the tradeoff with a single parameter κ, by minimizing the function κ (6) L(x) = −cT x + xT Σx. [sent-126, score-0.377]

58 2 If Σ is estimated from term co-occurrence data in the top-retrieved documents, then the condition to minimize xT Σx also encodes the fact that we want to select expansion terms that are not all in the same co-occurrence cluster. [sent-127, score-0.504]

59 Rather, we prefer a set of expansion terms that are more diverse, covering a larger range of potential topics. [sent-128, score-0.415]

60 4 Set-based constraints One limitation of current query model estimation methods is that they typically make greedy termby-term decisions using a threshold, without considering the qualities of the set of terms as a whole. [sent-130, score-0.805]

61 A one-dimensional greedy selection by term score, especially for a small number of terms, has the risk of emphasizing terms related to one aspect and not others. [sent-131, score-0.52]

62 This in turn increases the risk of query drift after expansion. [sent-132, score-0.802]

63 We now deﬁne several useful constraints on query model terms: aspect balance, aspect coverage, and query term support. [sent-133, score-1.864]

64 Figure 2 gives graphical examples of aspect balance, aspect coverage, and the term centrality objective. [sent-134, score-0.59]

65 We create the matrix A from the vectors φk (wi ) for each query term qk , by setting Aki = φk (wi ) = σik . [sent-137, score-0.769]

66 In effect, Ax gives the projection of the solution model x on each query term’s feature vector φk . [sent-138, score-0.673]

67 Another important constraint is that the set of initial query terms Q be predicted by the solution labeling. [sent-144, score-0.771]

68 We express this mathematically by requiring that the the weights for the ‘relevant’ label on the query terms xi:1 lie in a range li ≤ xi ≤ ui and in particular be above the threshold li for xi ∈ Q. [sent-145, score-0.998]

69 95 for all query terms, and zero for all other terms. [sent-147, score-0.649]

70 Term-speciﬁc values for li may also be desirable to reﬂect the rarity or ambiguity of individual query terms. [sent-150, score-0.74]

71 minimize κ T x Σx 2 µ + ζµ − cT x + subject to Ax T Relevance, term centrality & risk Aspect balance wi ∈ Q li ≤ xi ≤ ui , i = 1, . [sent-151, score-0.662]

72 , K (10) Aspect coverage gi x ≥ ζi , (9) (11) Query term support, positivity (12) Figure 3: The basic constrained quadratic program QMOD used for query model estimation. [sent-154, score-1.042]

73 One of the strengths of query expansion is its potential for solving the vocabulary mismatch problem by ﬁnding different words to express the same information need. [sent-156, score-1.008]

74 That is, we may require more than just that terms are balanced evenly among all query terms: we may care about the absolute level of support that exists. [sent-158, score-0.707]

75 Assuming no conﬂicting constraints such as maximum query length, we may prefer the second weighting because it increases the chance we ﬁnd the right alternate words for the query, potentially improving recall. [sent-162, score-0.786]

76 We denote the set of distances to neighboring words of query term qi by the vector gi . [sent-163, score-0.868]

77 The projection gi T x gives us the aspect coverage, or how well the words selected by the solution x ‘cover’ term qi . [sent-164, score-0.432]

78 The more expansion terms near qi that are given higher weights, the larger this value becomes. [sent-165, score-0.415]

79 When only the query term is covered, the value of gi T x = σii . [sent-166, score-0.837]

80 We want the aspect coverage for each of the vectors gi to exceed a threshold ζi , and this is expressed by the constraint gi T x ≥ ζi . [sent-167, score-0.479]

81 (8) Putting together the relevance and risk objectives, and constraining by the set properties, results in the following complete quadratic program for query model estimation, which we call QMOD and is shown in Figure 3. [sent-168, score-1.043]

82 3 Evaluation In this section we summarize the effectiveness of using the QMOD convex programs to estimate query models and examine how well the QMOD feasible set is calibrated to the empirical risk of expansion. [sent-170, score-0.919]

83 The best risk-reward tradeoff is generally obtained with a strong query support constraint (li near 1. [sent-172, score-0.726]

84 95 for query terms and li = 0 for non-query terms. [sent-180, score-0.762]

85 1 Robustness of Model Estimation In this section we evaluate the robustness of the query models estimated using the convex program in Fig. [sent-182, score-0.787]

86 The number of queries helped or hurt by expansion is shown, binned by the loss or gain in average precision by using feedback. [sent-187, score-0.738]

87 Yet considering the expansion failures whose loss in average precision is more than 10%, the robust version hurts more than 60% fewer queries. [sent-193, score-0.492]

88 The dark bars show robust expansion performance using the QMOD convex program with default control parameters. [sent-197, score-0.494]

89 The light bars show baseline expansion performance using term relevance weights only. [sent-198, score-0.764]

90 2 Calibration of Feasible Set If the constraints of a convex program are well-designed for stable query expansion, the odds of an infeasible solution should be much greater than 50% for queries that are risky. [sent-201, score-1.059]

91 Conversely, the odds of ﬁnding a feasible query model should ideally increase for thoese queries that are more amenable to expansion. [sent-203, score-0.926]

92 We binned these queries according to the actual gain or loss that would have been achieved with the baseline expansion, normalized by the original number of queries appearing in each bin when the (non-selective) baseline expansion is used. [sent-205, score-0.903]

93 This gives the log-odds of reverting to the original query for any given gain/loss level. [sent-206, score-0.736]

94 At this point, such high-reward queries are considered high risk by the algorithm, and the likelihood of reverting to the original query increases dramatically again. [sent-210, score-1.023]

95 This analysis makes clear that the selective expansion behavior of the convex algorithm is well-calibrated to the true expansion beneﬁt. [sent-211, score-0.753]

96 4 Conclusions We have presented a new research approach to query model estimation, showing how to adapt convex optimization methods to the problem by casting it as constrained graph labeling. [sent-212, score-0.849]

97 By integrating relevance and risk objectives with additional constraints to selectively reduce expansion for the most risky queries, our approach is able to signiﬁcantly reduce the downside risk of a strong baseline algorithm while retaining its strong gains in average precision. [sent-213, score-1.26]

98 In addition, sensitivity analysis of the constraints is likely provide useful information for active learning: interesting extensions to semi-supervised learning are possible to incorporate additional observations such as relevance feedback from the user. [sent-216, score-0.397]

99 Finally, there are a number of Figure 5: The log-odds of reverting to the original query as a result of selective expansion. [sent-217, score-0.755]

100 Queries are binned by the percent change in average precision if baseline expansion were used. [sent-218, score-0.548]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('query', 0.649), ('expansion', 0.326), ('relevance', 0.198), ('aspect', 0.189), ('queries', 0.158), ('risk', 0.153), ('qmod', 0.127), ('coverage', 0.127), ('term', 0.12), ('wi', 0.118), ('retrieval', 0.111), ('feedback', 0.108), ('wj', 0.103), ('balance', 0.091), ('objectives', 0.089), ('sigir', 0.086), ('cs', 0.081), ('trec', 0.079), ('binned', 0.074), ('risky', 0.074), ('baseline', 0.074), ('labeling', 0.072), ('constraints', 0.068), ('gi', 0.068), ('portfolio', 0.068), ('centrality', 0.068), ('indri', 0.063), ('reverting', 0.063), ('odds', 0.06), ('hurt', 0.06), ('feasible', 0.059), ('terms', 0.058), ('convex', 0.058), ('xs', 0.057), ('li', 0.055), ('failures', 0.055), ('label', 0.053), ('ax', 0.053), ('word', 0.051), ('precision', 0.049), ('weights', 0.046), ('user', 0.045), ('selectively', 0.045), ('language', 0.043), ('selective', 0.043), ('program', 0.043), ('personalizing', 0.042), ('default', 0.042), ('collections', 0.039), ('gain', 0.039), ('graph', 0.039), ('weighting', 0.038), ('initial', 0.037), ('robustness', 0.037), ('criteria', 0.037), ('hurts', 0.037), ('bets', 0.037), ('labels', 0.037), ('optimization', 0.036), ('individual', 0.036), ('constrained', 0.035), ('dumais', 0.034), ('wq', 0.034), ('documents', 0.033), ('vocabulary', 0.033), ('ui', 0.032), ('gains', 0.032), ('casting', 0.032), ('helped', 0.032), ('histogram', 0.032), ('acm', 0.031), ('qi', 0.031), ('prefer', 0.031), ('development', 0.031), ('estimation', 0.03), ('ws', 0.03), ('centering', 0.03), ('annual', 0.03), ('prefers', 0.029), ('expected', 0.028), ('budget', 0.027), ('objective', 0.027), ('constraint', 0.027), ('engines', 0.026), ('tradeoff', 0.026), ('ravikumar', 0.025), ('xi', 0.025), ('cost', 0.025), ('percent', 0.025), ('redundancy', 0.025), ('robust', 0.025), ('gives', 0.024), ('metric', 0.024), ('strong', 0.024), ('international', 0.024), ('inferring', 0.023), ('relaxations', 0.023), ('infeasible', 0.023), ('expand', 0.023), ('likely', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999952 73 nips-2008-Estimating Robust Query Models with Convex Optimization

Author: Kevyn Collins-thompson

2 0.29905236 184 nips-2008-Predictive Indexing for Fast Search

Author: Sharad Goel, John Langford, Alexander L. Strehl

Abstract: We tackle the computational problem of query-conditioned search. Given a machine-learned scoring rule and a query distribution, we build a predictive index by precomputing lists of potential results sorted based on an expected score of the result over future queries. The predictive index datastructure supports an anytime algorithm for approximate retrieval of the top elements. The general approach is applicable to webpage ranking, internet advertisement, and approximate nearest neighbor search. It is particularly effective in settings where standard techniques (e.g., inverted indices) are intractable. We experimentally ﬁnd substantial improvement over existing methods for internet advertisement and approximate nearest neighbors. 1

3 0.16844137 93 nips-2008-Global Ranking Using Continuous Conditional Random Fields

Author: Tao Qin, Tie-yan Liu, Xu-dong Zhang, De-sheng Wang, Hang Li

Abstract: This paper studies global ranking problem by learning to rank methods. Conventional learning to rank methods are usually designed for ‘local ranking’, in the sense that the ranking model is deﬁned on a single object, for example, a document in information retrieval. For many applications, this is a very loose approximation. Relations always exist between objects and it is better to deﬁne the ranking model as a function on all the objects to be ranked (i.e., the relations are also included). This paper refers to the problem as global ranking and proposes employing a Continuous Conditional Random Fields (CRF) for conducting the learning task. The Continuous CRF model is deﬁned as a conditional probability distribution over ranking scores of objects conditioned on the objects. It can naturally represent the content information of objects as well as the relation information between objects, necessary for global ranking. Taking two speciﬁc information retrieval tasks as examples, the paper shows how the Continuous CRF method can perform global ranking better than baselines.

4 0.16557804 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions

Author: Giovanni Cavallanti, Nicolò Cesa-bianchi, Claudio Gentile

Abstract: We provide a new analysis of an efﬁcient margin-based algorithm for selective sampling in classiﬁcation problems. Using the so-called Tsybakov low noise condition to parametrize the instance distribution, we show bounds on the convergence rate to the Bayes risk of both the fully supervised and the selective sampling versions of the basic algorithm. Our analysis reveals that, excluding logarithmic factors, the average risk of the selective sampler converges to the Bayes risk at rate N −(1+α)(2+α)/2(3+α) where N denotes the number of √ queried labels, and α > 0 is the exponent in the low noise condition. For all α > 3 − 1 ≈ 0.73 this convergence rate is asymptotically faster than the rate N −(1+α)/(2+α) achieved by the fully supervised version of the same classiﬁer, which queries all labels, and for α → ∞ the two rates exhibit an exponential gap. Experiments on textual data reveal that simple variants of the proposed selective sampler perform much better than popular and similarly efﬁcient competitors. 1

5 0.14742792 83 nips-2008-Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method

Author: Dongryeol Lee, Alexander G. Gray

Abstract: We propose a new fast Gaussian summation algorithm for high-dimensional datasets with high accuracy. First, we extend the original fast multipole-type methods to use approximation schemes with both hard and probabilistic error. Second, we utilize a new data structure called subspace tree which maps each data point in the node to its lower dimensional mapping as determined by any linear dimension reduction method such as PCA. This new data structure is suitable for reducing the cost of each pairwise distance computation, the most dominant cost in many kernel methods. Our algorithm guarantees probabilistic relative error on each kernel sum, and can be applied to high-dimensional Gaussian summations which are ubiquitous inside many kernel methods as the key computational bottleneck. We provide empirical speedup results on low to high-dimensional datasets up to 89 dimensions. 1 Fast Gaussian Kernel Summation In this paper, we propose new computational techniques for efﬁciently approximating the following sum for each query point qi ∈ Q: Φ(qi , R) = e−||qi −rj || 2 /(2h2 ) (1) rj ∈R where R is the reference set; each reference point is associated with a Gaussian function with a smoothing parameter h (the ’bandwidth’). This form of summation is ubiquitous in many statistical learning methods, including kernel density estimation, kernel regression, Gaussian process regression, radial basis function networks, spectral clustering, support vector machines, and kernel PCA [1, 4]. Cross-validation in all of these methods require evaluating Equation 1 for multiple values of h. Kernel density estimation, for example, requires |R| density estimate based on |R| − 1 points, yielding a brute-force computational cost scaling quadratically (that is O(|R| 2 )). Error bounds. Due to its expensive computational cost, many algorithms approximate the Gaussian kernel sums at the expense of reduced precision. Therefore, it is natural to discuss error bound criteria which measure the quality of the approximations with respect to their corresponding true values. The following error bound criteria are common in literature: Deﬁnition 1.1. An algorithm guarantees absolute error bound, if for each exact value Φ(q i , R) for qi ∈ Q, it computes Φ(qi , R) such that Φ(qi , R) − Φ(qi , R) ≤ . Deﬁnition 1.2. An algorithm guarantees relative error bound, if for each exact value Φ(q i , R) for qi ∈ Q, it computes Φ(qi , R) ∈ R such that Φ(qi , R) − Φ(qi , R) ≤ |Φ(qi , R)|. 1 Bounding the relative error (e.g., the percentage deviation) is much harder because the error bound criterion is in terms of the initially unknown exact quantity. As a result, many previous methods [7] have focused on bounding the absolute error. The relative error bound criterion is preferred to the absolute error bound criterion in statistical applications in which high accuracy is desired. Our new algorithm will enforce the following “relaxed” form of the relative error bound criterion, whose motivation will be discussed shortly. Deﬁnition 1.3. An algorithm guarantees (1 − α) probabilistic relative error bound, if for each exact value Φ(qi , R) for qi ∈ Q, it computes Φ(qi , R) ∈ R, such that with at least probability 0 < 1 − α < 1, Φ(qi , R) − Φ(qi , R) ≤ |Φ(qi , R)|. Previous work. The most successful class of acceleration methods employ “higher-order divide and conquer” or generalized N -body algorithms (GNA) [4]. This approach can use any spatial partioning tree such as kd-trees or ball-trees for both the query set Q and reference data R and performs a simulataneous recursive descent on both trees. GNA with relative error bounds (Deﬁnition 1.2) [5, 6, 11, 10] utilized bounding boxes and additional cached-sufﬁcient statistics such as higher-order moments needed for series-expansion. [5, 6] utilized bounding-box based error bounds which tend to be very loose, which resulted in slow empirical performance around suboptimally small and large bandwidths. [11, 10] extended GNA-based Gaussian summations with series-expansion which provided tighter bounds; it showed enormous performance improvements, but only up to low dimensional settings (up to D = 5) since the number of required terms in series expansion increases exponentially with respect to D. [9] introduces an iterative sampling based GNA for accelerating the computation of nested sums (a related easier problem). Its speedup is achieved by replacing pessimistic error bounds provided by bounding boxes with normal-based conﬁdence interval from Monte Carlo sampling. [9] demonstrates the speedup many orders of magnitude faster than the previous state of the art in the context of computing aggregates over the queries (such as the LSCV score for selecting the optimal bandwidth). However, the authors did not discuss the sampling-based approach for computations that require per-query estimates, such as those required for kernel density estimation. None of the previous approaches for kernel summations addresses the issue of reducing the computational cost of each distance computation which incurs O(D) cost. However, the intrinsic dimensionality d of most high-dimensional datasets is much smaller than the explicit dimension D (that is, d << D). [12] proposed tree structures using a global dimension reduction method, such as random projection, as a preprocessing step for efﬁcient (1 + ) approximate nearest neighbor search. Similarly, we develop a new data structure for kernel summations; our new data structure is constructed in a top-down fashion to perform the initial spatial partitioning in the original input space R D and performs a local dimension reduction to a localized subset of the data in a bottom-up fashion. This paper. We propose a new fast Gaussian summation algorithm that enables speedup in higher dimensions. Our approach utilizes: 1) probabilistic relative error bounds (Deﬁnition 1.3) on kernel sums provided by Monte Carlo estimates 2) a new tree structure called subspace tree for reducing the computational cost of each distance computation. The former can be seen as relaxing the strict requirement of guaranteeing hard relative bound on very small quantities, as done in [5, 6, 11, 10]. The latter was mentioned as a possible way of ameliorating the effects of the curse of dimensionality in [14], a pioneering paper in this area. Notations. Each query point and reference point (a D-dimensional vector) is indexed by natural numbers i, j ∈ N, and denoted qi and rj respectively. For any set S, |S| denotes the number of elements in S. The entities related to the left and the right child are denoted with superscripts L and R; an internal node N has the child nodes N L and N R . 2 Gaussian Summation by Monte Carlo Sampling Here we describe the extension needed for probabilistic computation of kernel summation satisfying Deﬁnition 1.3. The main routine for the probabilistic kernel summation is shown in Algorithm 1. The function MCMM takes the query node Q and the reference node R (each initially called with the roots of the query tree and the reference tree, Qroot and Rroot ) and β (initially called with α value which controls the probability guarantee that each kernel sum is within relative error). 2 Algorithm 1 The core dual-tree routine for probabilistic Gaussian kernel summation. MCMM(Q, R, β) if C AN S UMMARIZE E XACT(Q, R, ) then S UMMARIZE E XACT(Q, R) else if C AN S UMMARIZE MC(Q, R, , β) then 5: S UMMARIZE MC(Q, R, , β) else if Q is a leaf node then if R is a leaf node then MCMMBASE(Q, R) 10: else MCMM Q, RL , β , MCMM Q, RR , β 2 2 else if R is a leaf node then MCMM(QL , R, β), MCMM(QR , R, β) 15: else MCMM QL , RL , β , MCMM QL , RR , β 2 2 MCMM QR , RL , β , MCMM QR , RR , β 2 2 The idea of Monte Carlo sampling used in the new algorithm is similar to the one in [9], except the sampling is done per query and we use approximations that provide hard error bounds as well (i.e. ﬁnite difference, exhaustive base case: MCMMBASE). This means that the approximation has less variance than a pure Monte Carlo approach used in [9]. Algorithm 1 ﬁrst attempts approximations with hard error bounds, which are computationally cheaper than sampling-based approximations. For example, ﬁnite-difference scheme [5, 6] can be used for the C AN S UMMARIZE E XACT and S UMMARIZE E XACT functions in any general dimension. The C AN S UMMARIZE MC function takes two parameters that specify the accuracy: the relative error and its probability guarantee and decides whether to use Monte Carlo sampling for the given pair of nodes. If the reference node R contains too few points, it may be more efﬁcient to process it using exact methods that use error bounds based on bounding primitives on the node pair or exhaustive pair-wise evaluations, which is determined by the condition: τ · minitial ≤ |R| where τ > 1 controls the minimum number of reference points needed for Monte Carlo sampling to proceed. If the reference node does contain enough points, then for each query point q ∈ Q, the S AMPLE routine samples minitial terms over the terms in the summation Φ(q, R) = Kh (||q − rjn ||) rjn ∈R where Φ(q, R) denotes the exact contribution of R to q’s kernel sum. Basically, we are interested in estimating Φ(q, R) by Φ(q, R) = |R|µS , where µS is the sample mean of S. From the Central 2 Limit Theorem, given enough m samples, µS N (µ, σS /m) where Φ(q, R) = |R|µ (i.e. µ is the average of the kernel value between q and any reference point r ∈ R); this implies that √ |µS − µ| ≤ zβ/2 σS / m with probability 1 − β. The pruning rule we have to enforce for each query point for the contribution of R is: σS Φ(q, R) zβ/2 √ ≤ |R| m where σS the sample standard deviation of S. Since Φ(q, R) is one of the unknown quanities we want to compute, we instead enforce the following: σS zβ/2 √ ≤ m Φl (q, R) + |R| µS − |R| zβ/2 σS √ m (2) where Φl (q, R) is the currently running lower bound on the sum computed using exact methods z σ √ and |R| µS − β/2 S is the probabilistic component contributed by R. Denoting Φl,new (q, R) = m zβ/2 σ Φl (q, R) + |R| µS − √ S , the minimum number of samples for q needed to achieve the |S| 3 target error the right side of the inequality in Equation 2 with at least probability of 1 − β is: 2 2 m ≥ zβ/2 σS (|R| + |R|)2 2 (Φl (q, R) + |R|µ )2 S If the given query node and reference node pair cannot be pruned using either nonprobabilistic/probabilistic approximations, then we recurse on a smaller subsets of two sets. In particular, when dividing over the reference node R, we recurse with half of the β value 1 . We now state the probablistic error guarantee of our algorithm as a theorem. Theorem 2.1. After calling MCMM with Q = Qroot , R = Rroot , and β = α, Algorithm 1 approximates each Φ(q, R) with Φ(q, R) such that Deﬁnition 1.3 holds. Proof. For a query/reference (Q, R) pair and 0 < β < 1, MCMMBASE and S UMMARIZE E XACT compute estimates for q ∈ Q such that Φ(q, R) − Φ(q, R) < Φ(q,R)|R| with probability at |R| least 1 > 1 − β. By Equation 2, S UMMARIZE MC computes estimates for q ∈ Q such that Φ(q, R) − Φ(q, R) < Φ(q,R)|R| with probability 1 − β. |R| We now induct on |Q ∪ R|. Line 11 of Algorithm 1 divides over the reference whose subcalls compute estimates that satisfy Φ(q, RL ) − Φ(q, RL ) ≤ Φ(q,R)|RR | |R| L each with at least 1 − β 2 Φ(q,R)|RL | |R| and Φ(q, RR ) − Φ(q, RR ) ≤ probability by induction hypothesis. For q ∈ Q, Φ(q, R) = Φ(q, R )+ Φ(q, R ) which means |Φ(q, R)−Φ(q, R)| ≤ Φ(q,R)|R| with probability at least 1−β. |R| Line 14 divides over the query and each subcall computes estimates that hold with at least probability 1 − β for q ∈ QL and q ∈ QR . Line 16 and 17 divides both over the query and the reference, and the correctness can be proven similarly. Therefore, M CM M (Qroot , Rroot , α) computes estimates satisfying Deﬁnition 1.3. R “Reclaiming” probability. We note that the assigned probability β for the query/reference pair computed with exact bounds (S UMMARIZE E XACT and MCMMBASE) is not used. This portion of the probability can be “reclaimed” in a similar fashion as done in [10] and re-used to prune more aggressively in the later stages of the algorithm. All experiments presented in this paper were beneﬁted by this simple modiﬁcation. 3 Subspace Tree A subspace tree is basically a space-partitioning tree with a set of orthogonal bases associated with each node N : N.Ω = (µ, U, Λ, d) where µ is the mean, U is a D×d matrix whose columns consist of d eigenvectors, and Λ the corresponding eigenvalues. The orthogonal basis set is constructed using a linear dimension reduction method such as PCA. It is constructed in the top-down manner using the PARTITION S ET function dividing the given set of points into two (where the PARTITION S ET function divides along the dimension with the highest variance in case of a kd-tree for example), with the subspace in each node formed in the bottom-up manner. Algorithm 3 shows a PCA tree (a subspace tree using PCA as a dimension reduction) for a 3-D dataset. The subspace of each leaf node is computed using P CA BASE which can use the exact PCA [3] or a stochastic one [2]. For an internal node, the subspaces of the child nodes, N L .Ω = (µL , U L , ΛL , dL ) and N R .Ω = (µR , U R , ΛR , dR ), are approximately merged using the M ERGE S UBSPACES function which involves solving an (d L + dR + 1) × (dL + dR + 1) eigenvalue problem [8], which runs in O((dL + dR + 1)3 ) << O(D 3 ) given that the dataset is sparse. In addition, each data point x in each node N is mapped to its new lower-dimensional coordinate using the orthogonal basis set of N : xproj = U T (x − µ). The L2 norm reconstruction error is given by: ||xrecon − x||2 = ||(U xproj + µ) − x||2 . 2 2 Monte Carlo sampling using a subspace tree. Consider C AN S UMMARIZE MC function in Algorithm 2. The “outer-loop” over this algorithm is over the query set Q, and it would make sense to project each query point q ∈ Q to the subspace owned by the reference node R. Let U and µ be the orthogonal basis system for R consisting of d basis. For each q ∈ Q, consider the squared distance 1 We could also divide β such that the node that may be harder to approximate gets a lower value. 4 Algorithm 2 Monte Carlo sampling based approximation routines. C AN S UMMARIZE MC(Q, R, , α) S AMPLE(q, R, , α, S, m) return τ · minitial ≤ |R| for k = 1 to m do r ← random point in R S UMMARIZE MC(Q, R, , α) S ← S ∪ {Kh (||q − r||)} 2 for qi ∈ Q do µS ← M EAN(S), σS ← VARIANCE(S) S ← ∅, m ← minitial zα/2 σS Φl,new (q, R) ← Φl (q, R) + |R| µS − √ repeat |S| 2 S AMPLE(qi , R, , α, S, m) 2 2 mthresh ← zα/2 σS 2 (Φ(|R|+ |R|) S )2 l (q,R)+|R|µ until m ≤ 0 m ← mthresh − |S| Φ(qi , R) ← Φ(qi , R) + |R| · M EAN(S) ||(q − µ) − rproj ||2 (where (q − µ) is q’s coordinates expressed in terms of the coordinate system of R) as shown in Figure 1. For the Gaussian kernel, each pairwise kernel value is approximated as: e−||q−r|| 2 /(2h2 ) ≈ e−||q−qrecon || 2 (3) /(2h2 ) −||qproj −rproj ||2 /(2h2 ) e where qrecon = U qproj +µ and qproj = U (q−µ). For a ﬁxed query point q, e can be precomputed (which takes d dot products between two D-dimensional vectors) and re-used for every distance computation between q and any reference point r ∈ R whose cost is now O(d) << O(D). Therefore, we can take more samples efﬁciently. For a total of sufﬁciently large m samples, the computational cost is O(d(D + m)) << O(D · m) for each query point. −||q−qrecon ||2 /(2h2 ) T Increased variance comes at the cost of inexact distance computations, however. Each distance computation incurs at most squared L2 norm of ||rrecon − r||2 error. That is, 2 ||q − rrecon ||2 − ||q − r||2 ≤ ||rrecon − r||2 . Neverhteless, the sample variance for each query 2 2 2 point plus the inexactness due to dimension reduction τS can be shown to be bounded for the Gaus2 2 sian kernel as: (where each s = e−||q−rrecon || /(2h ) ): 1 m−1 ≤ 1 m−1 s∈S s2 − m · µ 2 S s2 + τS 2 min 1, max e||rrecon −r||2 /h s∈S r∈R 2 2 − m µS min e−||rrecon −r||2 /(2h 2 2 ) r∈R Exhaustive computations using a subspace tree. Now suppose we have built subspace trees for the query and the reference sets. We can project either each query point onto the reference subspace, or each reference point onto the query subspace, depending on which subspace has a smaller dimension and the number of points in each node. The subspaces formed in the leaf nodes usually are highly numerically accurate since it contains very few points compared to the extrinsic dimensionality D. 4 Experimental Results We empirically evaluated the runtime performance of our algorithm on seven real-world datasets, scaled to ﬁt in [0, 1]D hypercube, for approximating the Gaussian sum at every query point with a range of bandwidths. This experiment is motivated by many kernel methods that require computing the Gaussian sum at different bandwidth values (according to the standard least-sqares crossvalidation scores [15]). Nevertheless, we emphasize that the acceleration results are applicable to other kernel methods that require efﬁcient Gaussian summation. In this paper, the reference set equals the query set. All datasets have 50K points so that the exact exhaustive method can be tractably computed. All times are in seconds and include the time needed to build the trees. Codes are in C/C++ and run on a dual Intel Xeon 3GHz with 8 Gb of main memory. The measurements in second to eigth columns are obtained by running the algorithms at the bandwidth kh∗ where 10−3 ≤ k ≤ 103 is the constant in the corresponding column header. The last columns denote the total time needed to run on all seven bandwidth values. Each table has results for ﬁve algorithms: the naive algorithm and four algorithms. The algorithms with p = 1 denote the previous state-of-the-art (ﬁnite-difference with error redistribution) [10], 5 Algorithm 3 PCA tree building routine. B UILD P CAT REE(P) if C AN PARTITION(P) then {P L , P R } ← PARTITION S ET(P) N ← empty node N L ← B UILD P CAT REE(P L ) N R ← B UILD P CAT REE(P R ) N.S ← M ERGE S UBSPACES(N L .S, N R .S) else N ← B UILD P CAT REE BASE(P) N.S ← P CA BASE(P) N.Pproj ← P ROJECT(P, N.S) return N while those with p < 1 denote our probabilistic version. Each entry has the running time and the percentage of the query points that did not satisfy the relative error . Analysis. Readers should focus on the last columns containing the total time needed for evaluating Gaussian sum at all points for seven different bandwidth values. This is indicated by boldfaced numbers for our probabilistic algorithm. As expected, On low-dimensional datasets (below 6 dimensions), the algorithm using series-expansion based bounds gives two to three times speedup compared to our approach that uses Monte Carlo sampling. Multipole moments are an effective form of compression in low dimensions with analytical error bounds that can be evaluated; our Monte Carlo-based method has an asymptotic error bound which must be “learned” through sampling. As we go from 7 dimensions and beyond, series-expansion cannot be done efﬁciently because of its slow convergence. Our probabilistic algorithm (p = 0.9) using Monte Carlo consistently performs better than the algorithm using exact bounds (p = 1) by at least a factor of two. Compared to naive, it achieves the maximum speedup of about nine times on an 16-dimensional dataset; on an 89-dimensional dataset, it is at least three times as fast as the naive. Note that all the datasets contain only 50K points, and the speedup will be more dramatic as we increase the number of points. 5 Conclusion We presented an extension to fast multipole methods to use approximation methods with both hard and probabilistic bounds. Our experimental results show speedup over the previous state-of-the-art on high-dimensional datasets. Our future work will include possible improvements inspired by a recent work done in the FMM community using a matrix-factorization formulation [13]. Figure 1: Left: A PCA-tree for a 3-D dataset. Right: The squared Euclidean distance between a given query point and a reference point projected onto a subspace can be decomposed into two components: the orthogonal component and the component in the subspace. 6 Algorithm \ scale 0.001 0.01 0.1 1 10 100 1000 Σ mockgalaxy-D-1M-rnd (cosmology: positions), D = 3, N = 50000, h ∗ = 0.000768201 Naive 182 182 182 182 182 182 182 1274 MCMM 3 3 5 10 26 48 2 97 ( = 0.1, p = 0.9) 1% 1% 1% 1% 1% 1% 5% DFGT 2 2 2 2 6 19 3 36 ( = 0.1, p = 1) 0% 0% 0% 0% 0% 0% 0% MCMM 3 3 4 11 27 58 21 127 ( = 0.01, p = 0.9) 0 % 0% 1% 1% 1% 1% 7% DFGT 2 2 2 2 7 30 5 50 ( = 0.01, p = 1) 0% 0% 0% 0% 0% 0% 0% Algorithm \ scale 0.001 0.01 0.1 1 10 100 1000 Σ bio5-rnd (biology: drug activity), D = 5, N = 50000, h∗ = 0.000567161 Naive 214 214 214 214 214 214 214 1498 MCMM 4 4 6 144 149 65 1 373 ( = 0.1, p = 0.9) 0% 0% 0% 0% 1% 0% 1% DFGT 4 4 5 24 96 65 2 200 ( = 0.1, p = 1) 0% 0% 0% 0% 0% 0% 0% MCMM 4 4 6 148 165 126 1 454 ( = 0.01, p = 0.9) 0 % 0% 0% 0% 1% 0% 1% DFGT 4 4 5 25 139 126 4 307 ( = 0.01, p = 1) 0% 0% 0% 0% 0% 0% 0% Algorithm \ scale 0.001 0.01 0.1 1 10 100 1000 Σ pall7 − rnd , D = 7, N = 50000, h∗ = 0.00131865 Naive 327 327 327 327 327 327 327 2289 MCMM 3 3 3 3 63 224 <1 300 ( = 0.1, p = 0.9) 0% 0% 0% 1% 1% 12 % 0% DFGT 10 10 11 14 84 263 223 615 ( = 0.1, p = 1) 0% 0% 0% 0% 0% 0% 0% MCMM 3 3 3 3 70 265 5 352 ( = 0.01, p = 0.9) 0 % 0% 0% 1% 2% 1% 8% DFGT 10 10 11 14 85 299 374 803 ( = 0.01, p = 1) 0% 0% 0% 0% 0% 0% 0% Algorithm \ scale 0.001 0.01 0.1 1 10 100 1000 Σ covtype − rnd , D = 10, N = 50000, h∗ = 0.0154758 Naive 380 380 380 380 380 380 380 2660 MCMM 11 11 13 39 318 <1 <1 381 ( = 0.1, p = 0.9) 0% 0% 0% 1% 0% 0% 0% DFGT 26 27 38 177 390 244 <1 903 ( = 0.1, p = 1) 0% 0% 0% 0% 0% 0% 0% MCMM 11 11 13 77 362 2 <1 477 ( = 0.01, p = 0.9) 0 % 0% 0% 1% 1% 10 % 0% DFGT 26 27 38 180 427 416 <1 1115 ( = 0.01, p = 1) 0% 0% 0% 0% 0% 0% 0% Algorithm \ scale 0.001 0.01 0.1 1 10 100 1000 Σ CoocTexture − rnd , D = 16, N = 50000, h∗ = 0.0263958 Naive 472 472 472 472 472 472 472 3304 MCMM 10 11 22 189 109 <1 <1 343 ( = 0.1, p = 0.9) 0% 0% 0% 1% 8% 0% 0% DFGT 22 26 82 240 452 66 <1 889 ( = 0.1, p = 1) 0% 0% 0% 0% 0% 0% 0% MCMM 10 11 22 204 285 <1 <1 534 ( = 0.01, p = 0.9) 0 % 0% 1% 1% 10 % 4% 0% DFGT 22 26 83 254 543 230 <1 1159 ( = 0.01, p = 1) 0% 0% 0% 0% 0% 0% 0% 7 Algorithm \ scale 0.001 0.01 0.1 1 10 100 1000 LayoutHistogram − rnd , D = 32, N = 50000, h∗ = 0.0609892 Naive 757 757 757 757 757 757 757 MCMM 32 32 54 168 583 8 8 ( = 0.1, p = 0.9) 0% 0% 1% 1% 1% 0% 0% DFGT 153 159 221 492 849 212 <1 ( = 0.1, p = 1) 0% 0% 0% 0% 0% 0% 0% MCMM 32 45 60 183 858 8 8 ( = 0.01, p = 0.9) 0 % 0% 1% 6% 1% 0% 0% DFGT 153 159 222 503 888 659 <1 ( = 0.01, p = 1) 0% 0% 0% 0% 0% 0% 0% Algorithm \ scale 0.001 0.01 0.1 1 10 100 1000 CorelCombined − rnd , D = 89, N = 50000, h∗ = 0.0512583 Naive 1716 1716 1716 1716 1716 1716 1716 MCMM 384 418 575 428 1679 17 17 ( = 0.1, p = 0.9) 0% 0% 0% 1% 10 % 0% 0% DFGT 659 677 864 1397 1772 836 17 ( = 0.1, p = 1) 0% 0% 0% 0% 0% 0% 0% MCMM 401 419 575 437 1905 17 17 ( = 0.01, p = 0.9) 0 % 0% 0% 1% 2% 0% 0% DFGT 659 677 865 1425 1794 1649 17 ( = 0.01, p = 1) 0% 0% 0% 0% 0% 0% 0% Σ 5299 885 2087 1246 2585 Σ 12012 3518 6205 3771 7086 References [1] Nando de Freitas, Yang Wang, Maryam Mahdaviani, and Dustin Lang. Fast krylov methods for n-body learning. In Y. Weiss, B. Sch¨ lkopf, and J. Platt, editors, Advances in Neural Information Processing o Systems 18, pages 251–258. MIT Press, Cambridge, MA, 2006. [2] P. Drineas, R. Kannan, and M. Mahoney. Fast monte carlo algorithms for matrices iii: Computing a compressed approximate matrix decomposition, 2004. [3] G. Golub. Matrix Computations, Third Edition. The Johns Hopkins University Press, 1996. [4] A. Gray and A. W. Moore. N-Body Problems in Statistical Learning. In Todd K. Leen, Thomas G. Dietterich, and Volker Tresp, editors, Advances in Neural Information Processing Systems 13 (December 2000). MIT Press, 2001. [5] Alexander G. Gray and Andrew W. Moore. Nonparametric Density Estimation: Toward Computational Tractability. In SIAM International Conference on Data Mining 2003, 2003. [6] Alexander G. Gray and Andrew W. Moore. Very Fast Multivariate Kernel Density Estimation via Computational Geometry. In Joint Statistical Meeting 2003, 2003. to be submitted to JASA. [7] L. Greengard and J. Strain. The Fast Gauss Transform. SIAM Journal of Scientiﬁc and Statistical Computing, 12(1):79–94, 1991. [8] Peter Hall, David Marshall, and Ralph Martin. Merging and splitting eigenspace models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(9):1042–1049, 2000. [9] Michael Holmes, Alexander Gray, and Charles Isbell. Ultrafast monte carlo for statistical summations. In J.C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 673–680. MIT Press, Cambridge, MA, 2008. [10] Dongryeol Lee and Alexander Gray. Faster gaussian summation: Theory and experiment. In Proceedings of the Twenty-second Conference on Uncertainty in Artiﬁcial Intelligence. 2006. [11] Dongryeol Lee, Alexander Gray, and Andrew Moore. Dual-tree fast gauss transforms. In Y. Weiss, B. Sch¨ lkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, pages 747– o 754. MIT Press, Cambridge, MA, 2006. [12] Ting Liu, Andrew W. Moore, and Alexander Gray. Efﬁcient exact k-nn and nonparametric classiﬁcation ¨ in high dimensions. In Sebastian Thrun, Lawrence Saul, and Bernhard Sch olkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004. [13] P. G. Martinsson and Vladimir Rokhlin. An accelerated kernel-independent fast multipole method in one dimension. SIAM J. Scientiﬁc Computing, 29(3):1160–1178, 2007. [14] A. W. Moore, J. Schneider, and K. Deng. Efﬁcient locally weighted polynomial regression predictions. In D. Fisher, editor, Proceedings of the Fourteenth International Conference on Machine Learning, pages 196–204, San Francisco, 1997. Morgan Kaufmann. [15] B. W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall/CRC, 1986. 8

6 0.086619101 116 nips-2008-Learning Hybrid Models for Image Annotation with Partially Labeled Data

7 0.085402325 214 nips-2008-Sparse Online Learning via Truncated Gradient

8 0.080895349 142 nips-2008-Multi-Level Active Prediction of Useful Image Annotations for Recognition

9 0.077996708 101 nips-2008-Human Active Learning

10 0.07534188 125 nips-2008-Local Gaussian Process Regression for Real Time Online Model Learning

11 0.074474715 246 nips-2008-Unsupervised Learning of Visual Sense Models for Polysemous Words

12 0.074237362 136 nips-2008-Model selection and velocity estimation using novel priors for motion patterns

13 0.06609498 201 nips-2008-Robust Near-Isometric Matching via Structured Learning of Graphical Models

14 0.063079543 4 nips-2008-A Scalable Hierarchical Distributed Language Model

15 0.062123481 145 nips-2008-Multi-stage Convex Relaxation for Learning with Sparse Regularization

16 0.062031932 32 nips-2008-Bayesian Kernel Shaping for Learning Control

17 0.061982226 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions

18 0.061504252 194 nips-2008-Regularized Learning with Networks of Features

19 0.060685195 224 nips-2008-Structured ranking learning using cumulative distribution networks

20 0.060518634 96 nips-2008-Hebbian Learning of Bayes Optimal Decisions

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.203), (1, -0.054), (2, -0.056), (3, -0.057), (4, -0.074), (5, -0.012), (6, 0.102), (7, -0.004), (8, 0.034), (9, 0.029), (10, -0.153), (11, 0.042), (12, -0.077), (13, 0.106), (14, 0.209), (15, -0.103), (16, 0.023), (17, 0.058), (18, 0.303), (19, 0.052), (20, 0.16), (21, 0.07), (22, 0.032), (23, -0.077), (24, 0.043), (25, -0.031), (26, 0.219), (27, -0.068), (28, -0.002), (29, -0.014), (30, 0.006), (31, 0.089), (32, -0.013), (33, -0.127), (34, -0.04), (35, 0.034), (36, -0.011), (37, -0.107), (38, 0.087), (39, -0.014), (40, 0.162), (41, 0.031), (42, 0.04), (43, -0.011), (44, 0.082), (45, 0.022), (46, -0.021), (47, 0.006), (48, -0.043), (49, -0.045)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9801206 73 nips-2008-Estimating Robust Query Models with Convex Optimization

Author: Kevyn Collins-thompson

2 0.89212316 184 nips-2008-Predictive Indexing for Fast Search

Author: Sharad Goel, John Langford, Alexander L. Strehl

3 0.62018609 83 nips-2008-Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method

Author: Dongryeol Lee, Alexander G. Gray

4 0.45693749 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions

Author: Giovanni Cavallanti, Nicolò Cesa-bianchi, Claudio Gentile

5 0.45234191 169 nips-2008-Online Models for Content Optimization

Author: Deepak Agarwal, Bee-chung Chen, Pradheep Elango, Nitin Motgi, Seung-taek Park, Raghu Ramakrishnan, Scott Roy, Joe Zachariah

Abstract: We describe a new content publishing system that selects articles to serve to a user, choosing from an editorially programmed pool that is frequently refreshed. It is now deployed on a major Yahoo! portal, and selects articles to serve to hundreds of millions of user visits per day, signiﬁcantly increasing the number of user clicks over the original manual approach, in which editors periodically selected articles to display. Some of the challenges we face include a dynamic content pool, short article lifetimes, non-stationary click-through rates, and extremely high trafﬁc volumes. The fundamental problem we must solve is to quickly identify which items are popular (perhaps within different user segments), and to exploit them while they remain current. We must also explore the underlying pool constantly to identify promising alternatives, quickly discarding poor performers. Our approach is based on tracking per article performance in near real time through online models. We describe the characteristics and constraints of our application setting, discuss our design choices, and show the importance and effectiveness of coupling online models with a randomization procedure. We discuss the challenges encountered in a production online content-publishing environment and highlight issues that deserve careful attention. Our analysis of this application also suggests a number of future research avenues. 1

6 0.44069001 93 nips-2008-Global Ranking Using Continuous Conditional Random Fields

7 0.40015876 101 nips-2008-Human Active Learning

8 0.39817643 168 nips-2008-Online Metric Learning and Fast Similarity Search

9 0.36883005 125 nips-2008-Local Gaussian Process Regression for Real Time Online Model Learning

10 0.36128405 29 nips-2008-Automatic online tuning for fast Gaussian summation

11 0.35308596 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions

12 0.32107913 142 nips-2008-Multi-Level Active Prediction of Useful Image Annotations for Recognition

13 0.31400603 190 nips-2008-Reconciling Real Scores with Binary Comparisons: A New Logistic Based Model for Ranking

14 0.30988455 41 nips-2008-Breaking Audio CAPTCHAs

15 0.30717534 246 nips-2008-Unsupervised Learning of Visual Sense Models for Polysemous Words

16 0.3033466 176 nips-2008-Partially Observed Maximum Entropy Discrimination Markov Networks

17 0.29859808 156 nips-2008-Nonparametric sparse hierarchical models describe V1 fMRI responses to natural images

18 0.29399404 214 nips-2008-Sparse Online Learning via Truncated Gradient

19 0.28982189 224 nips-2008-Structured ranking learning using cumulative distribution networks

20 0.28693375 201 nips-2008-Robust Near-Isometric Matching via Structured Learning of Graphical Models

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(4, 0.011), (6, 0.082), (7, 0.055), (12, 0.049), (16, 0.023), (28, 0.159), (35, 0.246), (57, 0.06), (59, 0.025), (63, 0.033), (71, 0.032), (77, 0.034), (78, 0.011), (83, 0.076)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.82428223 73 nips-2008-Estimating Robust Query Models with Convex Optimization

Author: Kevyn Collins-thompson

2 0.82313025 42 nips-2008-Cascaded Classification Models: Combining Models for Holistic Scene Understanding

Author: Geremy Heitz, Stephen Gould, Ashutosh Saxena, Daphne Koller

Abstract: One of the original goals of computer vision was to fully understand a natural scene. This requires solving several sub-problems simultaneously, including object detection, region labeling, and geometric reasoning. The last few decades have seen great progress in tackling each of these problems in isolation. Only recently have researchers returned to the difﬁcult task of considering them jointly. In this work, we consider learning a set of related models in such that they both solve their own problem and help each other. We develop a framework called Cascaded Classiﬁcation Models (CCM), where repeated instantiations of these classiﬁers are coupled by their input/output variables in a cascade that improves performance at each level. Our method requires only a limited “black box” interface with the models, allowing us to use very sophisticated, state-of-the-art classiﬁers without having to look under the hood. We demonstrate the effectiveness of our method on a large set of natural images by combining the subtasks of scene categorization, object detection, multiclass image segmentation, and 3d reconstruction. 1

3 0.65528238 14 nips-2008-Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models

Author: Tong Zhang

Abstract: Consider linear prediction models where the target function is a sparse linear combination of a set of basis functions. We are interested in the problem of identifying those basis functions with non-zero coefﬁcients and reconstructing the target function from noisy observations. Two heuristics that are widely used in practice are forward and backward greedy algorithms. First, we show that neither idea is adequate. Second, we propose a novel combination that is based on the forward greedy algorithm but takes backward steps adaptively whenever beneﬁcial. We prove strong theoretical results showing that this procedure is effective in learning sparse representations. Experimental results support our theory. 1

4 0.65424693 245 nips-2008-Unlabeled data: Now it helps, now it doesn't

Author: Aarti Singh, Robert Nowak, Xiaojin Zhu

Abstract: Empirical evidence shows that in favorable situations semi-supervised learning (SSL) algorithms can capitalize on the abundance of unlabeled training data to improve the performance of a learning task, in the sense that fewer labeled training data are needed to achieve a target error bound. However, in other situations unlabeled data do not seem to help. Recent attempts at theoretically characterizing SSL gains only provide a partial and sometimes apparently conﬂicting explanations of whether, and to what extent, unlabeled data can help. In this paper, we attempt to bridge the gap between the practice and theory of semi-supervised learning. We develop a ﬁnite sample analysis that characterizes the value of unlabeled data and quantiﬁes the performance improvement of SSL compared to supervised learning. We show that there are large classes of problems for which SSL can signiﬁcantly outperform supervised learning, in ﬁnite sample regimes and sometimes also in terms of error convergence rates.

5 0.65324259 202 nips-2008-Robust Regression and Lasso

Author: Huan Xu, Constantine Caramanis, Shie Mannor

Abstract: We consider robust least-squares regression with feature-wise disturbance. We show that this formulation leads to tractable convex optimization problems, and we exhibit a particular uncertainty set for which the robust problem is equivalent to 1 regularized regression (Lasso). This provides an interpretation of Lasso from a robust optimization perspective. We generalize this robust formulation to consider more general uncertainty sets, which all lead to tractable convex optimization problems. Therefore, we provide a new methodology for designing regression algorithms, which generalize known formulations. The advantage is that robustness to disturbance is a physical property that can be exploited: in addition to obtaining new formulations, we use it directly to show sparsity properties of Lasso, as well as to prove a general consistency result for robust regression problems, including Lasso, from a uniﬁed robustness perspective. 1

6 0.65233243 205 nips-2008-Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization

7 0.6522615 79 nips-2008-Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

8 0.65082061 194 nips-2008-Regularized Learning with Networks of Features

9 0.64909089 62 nips-2008-Differentiable Sparse Coding

10 0.64765871 173 nips-2008-Optimization on a Budget: A Reinforcement Learning Approach

11 0.64691919 196 nips-2008-Relative Margin Machines

12 0.64637733 75 nips-2008-Estimating vector fields using sparse basis field expansions

13 0.64625639 91 nips-2008-Generative and Discriminative Learning with Unknown Labeling Bias

14 0.6457932 116 nips-2008-Learning Hybrid Models for Image Annotation with Partially Labeled Data

15 0.64496595 142 nips-2008-Multi-Level Active Prediction of Useful Image Annotations for Recognition

16 0.64463615 130 nips-2008-MCBoost: Multiple Classifier Boosting for Perceptual Co-clustering of Images and Visual Features

17 0.64451456 179 nips-2008-Phase transitions for high-dimensional joint support recovery

18 0.64403135 145 nips-2008-Multi-stage Convex Relaxation for Learning with Sparse Regularization

19 0.64365804 176 nips-2008-Partially Observed Maximum Entropy Discrimination Markov Networks

20 0.6436373 143 nips-2008-Multi-label Multiple Kernel Learning