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

184 nips-2008-Predictive Indexing for Fast Search

Source: pdf

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

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 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. [sent-8, score-1.174]

2 The predictive index datastructure supports an anytime algorithm for approximate retrieval of the top elements. [sent-9, score-0.468]

3 The objective of web search is to quickly return the set of most relevant web pages given a particular query string. [sent-16, score-0.962]

4 Accomplishing this task for a ﬁxed query involves both determining the relevance of potential pages and then searching over the myriad set of all pages for the most relevant ones. [sent-17, score-0.507]

5 The extreme speed constraint, often 100ms or less, and the large number of web pages (N ≈ 1010 ) makes web search a computationally-challenging problem. [sent-26, score-0.566]

6 Even with perfect 1000-way parallelization on modern machines, there is far too little time to directly evaluate against every page when a particular query is submitted. [sent-27, score-0.719]

7 The question addressed here is: “Can we quickly return the highest scoring pages as ranked by complex scoring rules typical of learning algorithms? [sent-29, score-0.509]

8 Taking the empirical probability distribution of queries into account, we pre-compute collections of web pages that have a large expected score conditioned on the query falling into particular sets of related queries {Qi }. [sent-33, score-1.039]

9 For example, we may pre-compute and store the list of web pages that have the highest average score when the query contains the phrase “machine learning”. [sent-34, score-0.843]

10 To yield a practical algorithm, these sets should form meaningful groups of pages with respect to the scoring function and query distribution. [sent-35, score-0.676]

11 Our main contribution is optimizing the search index with respect to the query distribution. [sent-37, score-0.496]

12 The empirical evidence presented shows that predictive indexing is an effective technique, making general machine learning style prediction methods viable for quickly ranking over large numbers of objects. [sent-38, score-0.543]

13 Section 2 describes the predictive indexing algorithm and covers an example and lemma suggesting that predictive indexing has signiﬁcant advantages over existing techniques. [sent-41, score-0.948]

14 We present empirical evaluation of the method in Section 3, using both proprietary web advertising data and public data for nearest neighbor search. [sent-42, score-0.513]

15 1 Feature Representation One concrete way to map web search into the general predictive index framework is to represent both queries and pages as sparse binary feature vectors in a high-dimensional Euclidean space. [sent-44, score-0.737]

16 Speciﬁcally, we associate each word with a coordinate: A query (page) has a value of 1 for that coordinate if it contains the word, and a value of 0 otherwise. [sent-45, score-0.42]

17 We call this the word-based feature representation, because each query and page can be summarized by a list of its features (i. [sent-46, score-0.842]

18 The general predictive framework supports many other possible representations, including those that incorporate the difference between words in the title and words in the body of the web page, the number of times a word occurs, or the IP address of the user entering the query. [sent-49, score-0.467]

19 , 2003) supports the top-k n problem for linear scoring functions of the form f (q, p) = i=1 qi gi (p), where qi ∈ {0, 1} is the th i coordinate of the query q, and gi : W → R are partial scores for pages as determined by the ith feature1 . [sent-58, score-1.003]

20 For each query feature i, construct an ordered list Li containing every web page, sorted in descending order by their partial scores gi (p). [sent-59, score-0.914]

21 Given a query q, we evaluate web pages in the lists Li that correspond to features of q. [sent-61, score-0.844]

22 The lower bound is the score of the k th best page seen so far; the upper bound is the sum of the partial scores (i. [sent-63, score-0.488]

23 , gi (p)) for the next-to-be-scored page in each list. [sent-65, score-0.382]

24 Since the lists are ordered by the partial scores, the upper threshold does in fact bound the score of any page yet to be seen. [sent-66, score-0.69]

25 The threshold algorithm is particularly effective when a query contains a small number of features, facilitating fast convergence of the upper bound. [sent-67, score-0.41]

26 An inverted index is a datastructure that maps every page feature x to a list of pages p that contain x. [sent-71, score-0.855]

27 When a new query arrives, a subset of page features relevant to the query is ﬁrst determined. [sent-72, score-1.128]

28 For instance, when the query contains “dog”, the page feature set might be {“dog”, “canine”, “collar”, . [sent-73, score-0.719]

29 Note that a distinction is made between query features and page features, and in particular, the relevant page features may include many more words than the query itself. [sent-77, score-1.514]

30 Once a set of page features is determined, their respective lists (i. [sent-78, score-0.532]

31 , 2003), use one global order for pages in the lists and walk down the lists synchronously to compute page scores. [sent-83, score-0.708]

32 See (Zobel & Moffat, 2006) for an overview of inverted indices applied to web search. [sent-84, score-0.453]

33 The resulting algorithms are efﬁcient only when it is sufﬁcient to search over a relatively small set of inverted indices for each 1 More general monotone scoring functions (e. [sent-86, score-0.496]

34 They require, for each query q, that there exists a small set2 Xq of page features such that the score of any page against q depends only on its intersection with Xq . [sent-90, score-1.203]

35 In other words, the scoring rule must be extremely sparse, with most words or features in the page having zero contribution to the score for q. [sent-91, score-0.718]

36 1, we consider a machine-learned scoring rule, derived from internet advertising data, with the property that almost all page features have substantial inﬂuence on the score for every query, making any straightforward approach based on inverted indices intractable. [sent-93, score-1.096]

37 Furthermore, algorithms that use inverted indices do not typically optimize the datastructure against the query distribution and our experiments suggest that doing so may be beneﬁcial. [sent-94, score-0.698]

38 ” For each query set, the associated predictive index is an ordered list of web pages sorted by their expected score for random queries drawn from that set. [sent-97, score-1.353]

39 In particular, we expect web pages at the top of the ‘France’ list to be good, on average, for queries containing the word ‘France. [sent-98, score-0.621]

40 ’ In contrast to an inverted index, the pages in the ‘France’ list need not themselves contain the word ‘France’. [sent-99, score-0.392]

41 In the applications we consider, however, we ﬁnd that predictive indexing works well even when applied to naively deﬁned query sets. [sent-104, score-0.845]

42 Furthermore, in our application to approximate nearest neighbor search, we found predictive indexing to be robust to cover sets generated via random projections whose size and shape were varied across experiments. [sent-105, score-0.776]

43 We represent queries and web pages as points in, respectively, Q ⊆ Rn and W ⊆ Rm . [sent-106, score-0.448]

44 This setting is general, but for the experimental application we consider n, m ≈ 106 , with any given page or query having about 102 non-zero entries (see Section 3. [sent-107, score-0.719]

45 Given a scoring function f : Q × W → R, and a query q, we attempt to rapidly ﬁnd the top-k pages p1 , . [sent-111, score-0.647]

46 1 Predictive Indexing for General Scoring Functions Consider a ﬁnite collection Q of sets Qi ⊆ Q that cover the query space (i. [sent-121, score-0.463]

47 The function fi (p) is the expected score of the web page p for the (related) queries in Qi . [sent-125, score-0.831]

48 The hope is that any page p has approximately the same score for any query q ∈ Qi . [sent-126, score-0.817]

49 If, for example, Qi is the set of queries that contain the word “dog”, we may expect every query in Qi to score high against pages about dogs and to score low against those pages not about dogs. [sent-127, score-0.878]

50 At runtime, given a query q, we identify the query sets Qi containing q, and compute the scoring function f only on the restricted set of pages at the beginning of their associated lists Li . [sent-132, score-1.236]

51 One can, however, approximate these scores by sampling from the query distribution D. [sent-135, score-0.446]

52 Algorithm 1 outlines the construction of the sampling-based predictive indexing datastructure. [sent-136, score-0.474]

53 Note that in the special case where we cover Q with a single set, we end up with a global ordering of web pages, independent of the query, which is optimized for the underlying query distribution. [sent-138, score-0.747]

54 3 Algorithm 1 Construct-Predictive-Index(Cover Q, Dataset S) Lj [s] = 0 for all objects s and query sets Qj . [sent-140, score-0.4]

55 2 Discussion We present an elementary example to help develop intuition for why we can sometimes expect predictive indexing to improve upon projective datastructures such as those used in Fagin’s threshold algorithm. [sent-143, score-0.592]

56 Suppose we have: two query features t1 and t2 ; three possible queries q1 = {t1 }, q2 = {t2 } and q3 = {t1 , t2 }; and three web pages p1 , p2 and p3 . [sent-144, score-0.824]

57 That is, pi is the best match for query qi , but p3 does not score highly for either query feature alone. [sent-148, score-1.015]

58 In this case, if we know t1 is in the query, we infer that t2 is likely to be in the query (and vice versa), and construct the predictive index t1 → {p3 , p1 , p2 } t2 → {p3 , p2 , p1 }. [sent-151, score-0.637]

59 On the high probability event, namely query q3 , we see the predictive index outperforms the projective, query independent, index. [sent-152, score-1.008]

60 We expect predictive indices to generally improve on datastructures that are agnostic to the query distribution. [sent-153, score-0.638]

61 , a global web page ordering) and when we wish to optimize the probability of returning the highest-scoring object, Lemma 2. [sent-156, score-0.569]

62 1 shows that a predictive ordering is the best ordering relative to any particular query distribution. [sent-157, score-0.704]

63 Suppose we have a set of points S, a query distribution D, and a function f that scores queries against points in S. [sent-160, score-0.605]

64 Further assume that for each query q, there is a unique highest scoring point Hq . [sent-161, score-0.579]

65 3 Empirical Evaluation We evaluate predictive indexing for two applications: Internet advertising and approximate nearest neighbor. [sent-179, score-0.69]

66 The data are comprised of logs of events, where each event represents a visit by a user to a particular web page p, from a set of web pages Q ⊆ Rn . [sent-183, score-0.858]

67 From a large set of advertisements W ⊆ Rm , the commercial system chooses a smaller, ordered set of ads to display on the page (generally around 4). [sent-184, score-0.575]

68 The training data consist of 5 million events (web page × ad displays). [sent-190, score-0.421]

69 Each page consists of approximately 50 page features, and a total of n ≈ 9 × 105 total page features are observed. [sent-192, score-1.082]

70 1) and trained a linear scoring rule f of the form f (p, a) = i,j wi,j pi aj , to approximately rank the ads by their probability of click. [sent-194, score-0.498]

71 The search algorithms we compare were given the scoring rule f , the training pages, and the ads W for the necessary pre-computations. [sent-196, score-0.458]

72 They were then evaluated by their serving of k = 10 ads, under a time constraint, for each page in the test set. [sent-197, score-0.416]

73 2, two variants of predictive indexing (PI-AVG and PI-DCG), and a fourth method, called best global ordering (BO), which is a degenerate form of PI discussed in Section 2. [sent-205, score-0.542]

74 An inverted index approach is prohibitively expensive since almost all ad features have substantial inﬂuence on the score for every web page (see Section 1. [sent-207, score-1.069]

75 PI-AVG and PI-DCG require a covering of the web page space. [sent-209, score-0.604]

76 We used the natural covering suggested by the binary features—each page feature i corresponds to a cover set consisting of precisely those pages p that contain i. [sent-210, score-0.514]

77 The resulting datastructure is therefore similar to that maintained by the TA algorithm—lists, for each page feature, containing all the ads. [sent-211, score-0.486]

78 However, while TA orders ads by partial score j wi,j pi aj for each ﬁxed page feature i, the predictive methods order by expected score. [sent-212, score-0.863]

79 PI-AVG sorts ad lists by expected score of f , Ep∼Di [f (p, a)] = Ep∼D [f (p, a)|i ∈ p], conditioned on the page containing feature i. [sent-213, score-0.708]

80 BO stores a single list of all ads, sorted by expected DCGf (p, a), while PI-DCG stores a list for each page feature i sorted by Ep∼Di [DCGf (p, a)]. [sent-216, score-0.636]

81 5 × 105 ads for each test page and computing the true top-10 ads. [sent-236, score-0.516]

82 We see that all three methods of predictive indexing are superior to Fagin’s halted threshold algorithm. [sent-238, score-0.596]

83 These latter two predictive indexing methods attain relatively high accuracy even when fully evaluating only 0. [sent-240, score-0.474]

84 0 Probability of Exact Retrieval−1st Result Comparison of Serving Algorithms 200 300 400 500 Number of Full Evaluations (a) (b) Figure 1: Comparison of the ﬁrst and tenth results returned from the four serving algorithms on the web advertisement dataset. [sent-254, score-0.402]

85 Our implementation of the predictive index, and also the halted threshold algorithm, required about 50ms per display event when 500 ad evaluations are allowed. [sent-255, score-0.435]

86 The RAM use for the predictive index is also reasonable, requiring about a factor of 2 more RAM than the ads themselves. [sent-256, score-0.434]

87 2 Approximate Nearest Neighbor Search A special case application of predictive indexing is approximate nearest neighbor search. [sent-258, score-0.684]

88 Given a set of points W in n-dimensional Euclidean space, and a query point x in that same space, the nearest neighbor problem is to quickly return the top-k neighbors of x. [sent-259, score-0.606]

89 In the predictive indexing framework, the nearest neighbor problem corresponds to 6 minimizing a scoring function, f (x, y) = ||x − y||2 , deﬁned by Euclidean distance. [sent-261, score-0.859]

90 We assume query points are generated from a distribution D that can be sampled. [sent-262, score-0.404]

91 Given a query point x, consider the union Ux = {Qi,J ∈Q | x ∈ Qi,J } Qi,J of all cover sets containing x. [sent-284, score-0.506]

92 Standard LSH approaches to the nearest neighbor problem work by scoring points in the set Qx = W ∩ Ux . [sent-285, score-0.418]

93 Predictive indexing, in contrast, maps each cover set Qi,J to an ordered list of points sorted by their probability of being a top-10 nearest point to points in Qi,J . [sent-287, score-0.432]

94 For the query x, we then consider those points in W with large probability hQi,J for at least one of the sets Qi,J that cover x. [sent-289, score-0.496]

95 Figure 2(a) displays the true rank of the ﬁrst point returned by LSH and predictive indexing on the MNIST data set as a function of α, averaged over all points in the test set and over multiple trials. [sent-304, score-0.612]

96 Figure 2(b) displays the performance of LSH and predictive indexing for the tenth point returned, over all four data sets, with values of α varying from 5 to 70, averaged over the test sets, and replicated by multiple runs. [sent-308, score-0.532]

97 4 Conclusion Predictive indexing is the ﬁrst datastructure capable of supporting scalable, rapid ranking based on general purpose machine-learned scoring rules. [sent-314, score-0.624]

98 In the special case of approximate nearest neighbors, predictive indexing offers substantial and consistent improvements over the Locality Sensitive Hashing algorithm. [sent-317, score-0.639]

99 Predictive Indexing on MNIST Data 40 60 qq q q q q q q q q q 80 100 LSH − Rank of 10th Result (a) The y-axis, “Rank of 1st Result” measures the (b) Each point represents the outcome of a single extrue rank of the ﬁrst result returned by each method. [sent-320, score-0.411]

100 Fast query evaluation through document identiﬁer assignment for inverted ﬁle-based information retrieval systems. [sent-347, score-0.606]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('query', 0.371), ('page', 0.348), ('qq', 0.33), ('indexing', 0.277), ('web', 0.221), ('scoring', 0.208), ('lsh', 0.203), ('predictive', 0.197), ('inverted', 0.19), ('ads', 0.168), ('lists', 0.146), ('fagin', 0.127), ('queries', 0.126), ('qi', 0.123), ('nearest', 0.1), ('score', 0.098), ('qqq', 0.097), ('datastructure', 0.095), ('dcgf', 0.095), ('list', 0.085), ('halted', 0.083), ('advertising', 0.083), ('neighbor', 0.077), ('ad', 0.073), ('index', 0.069), ('pages', 0.068), ('ordering', 0.068), ('serving', 0.068), ('cover', 0.063), ('ordered', 0.059), ('ta', 0.059), ('lj', 0.059), ('sorted', 0.059), ('internet', 0.057), ('search', 0.056), ('pi', 0.052), ('projective', 0.051), ('indyk', 0.051), ('word', 0.049), ('hq', 0.047), ('hashing', 0.047), ('bo', 0.047), ('retrieval', 0.045), ('rank', 0.044), ('mnist', 0.044), ('ranking', 0.044), ('containing', 0.043), ('evaluations', 0.043), ('scores', 0.042), ('qqqqqq', 0.042), ('advertisement', 0.042), ('indices', 0.042), ('threshold', 0.039), ('qj', 0.038), ('features', 0.038), ('fi', 0.038), ('france', 0.037), ('returned', 0.037), ('broder', 0.036), ('covering', 0.035), ('gi', 0.034), ('tenth', 0.034), ('partitions', 0.034), ('points', 0.033), ('approximate', 0.033), ('chierichetti', 0.032), ('halting', 0.032), ('moffat', 0.032), ('proprietary', 0.032), ('prq', 0.032), ('rental', 0.032), ('zobel', 0.032), ('substantial', 0.032), ('dog', 0.031), ('ny', 0.03), ('top', 0.029), ('di', 0.029), ('sets', 0.029), ('dcg', 0.028), ('kek', 0.028), ('rvelin', 0.028), ('datastructures', 0.028), ('optdigits', 0.028), ('corel', 0.028), ('ux', 0.028), ('gionis', 0.028), ('pendigits', 0.028), ('goel', 0.028), ('andoni', 0.028), ('yahoo', 0.027), ('rule', 0.026), ('inen', 0.025), ('datar', 0.025), ('ep', 0.025), ('quickly', 0.025), ('rn', 0.025), ('displays', 0.024), ('end', 0.024), ('strehl', 0.024), ('ram', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 184 nips-2008-Predictive Indexing for Fast Search

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

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

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

3 0.29622245 156 nips-2008-Nonparametric sparse hierarchical models describe V1 fMRI responses to natural images

Author: Vincent Q. Vu, Bin Yu, Thomas Naselaris, Kendrick Kay, Jack Gallant, Pradeep K. Ravikumar

Abstract: We propose a novel hierarchical, nonlinear model that predicts brain activity in area V1 evoked by natural images. In the study reported here brain activity was measured by means of functional magnetic resonance imaging (fMRI), a noninvasive technique that provides an indirect measure of neural activity pooled over a small volume (≈ 2mm cube) of brain tissue. Our model, which we call the V-SPAM model, is based on the reasonable assumption that fMRI measurements reﬂect the (possibly nonlinearly) pooled, rectiﬁed output of a large population of simple and complex cells in V1. It has a hierarchical ﬁltering stage that consists of three layers: model simple cells, model complex cells, and a third layer in which the complex cells are linearly pooled (called “pooled-complex” cells). The pooling stage then obtains the measured fMRI signals as a sparse additive model (SpAM) in which a sparse nonparametric (nonlinear) combination of model complex cell and model pooled-complex cell outputs are summed. Our results show that the V-SPAM model predicts fMRI responses evoked by natural images better than a benchmark model that only provides linear pooling of model complex cells. Furthermore, the spatial receptive ﬁelds, frequency tuning and orientation tuning curves of the V-SPAM model estimated for each voxel appears to be consistent with the known properties of V1, and with previous analyses of this data set. A visualization procedure applied to the V-SPAM model shows that most of the nonlinear pooling consists of simple compressive or saturating nonlinearities. 1

4 0.13630131 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.

5 0.11831883 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.10333303 168 nips-2008-Online Metric Learning and Fast Similarity Search

7 0.095987104 246 nips-2008-Unsupervised Learning of Visual Sense Models for Polysemous Words

8 0.094657719 219 nips-2008-Spectral Hashing

9 0.092823841 72 nips-2008-Empirical performance maximization for linear rank statistics

10 0.087627478 176 nips-2008-Partially Observed Maximum Entropy Discrimination Markov Networks

11 0.080451243 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions

12 0.065427914 174 nips-2008-Overlaying classifiers: a practical approach for optimal ranking

13 0.065047771 169 nips-2008-Online Models for Content Optimization

14 0.061911311 140 nips-2008-Mortal Multi-Armed Bandits

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

16 0.05760204 224 nips-2008-Structured ranking learning using cumulative distribution networks

17 0.05666345 82 nips-2008-Fast Computation of Posterior Mode in Multi-Level Hierarchical Models

18 0.055388559 4 nips-2008-A Scalable Hierarchical Distributed Language Model

19 0.054585047 241 nips-2008-Transfer Learning by Distribution Matching for Targeted Advertising

20 0.050387625 214 nips-2008-Sparse Online Learning via Truncated Gradient

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.154), (1, -0.045), (2, -0.023), (3, -0.054), (4, -0.079), (5, -0.048), (6, 0.141), (7, -0.02), (8, 0.079), (9, 0.072), (10, -0.155), (11, 0.023), (12, -0.103), (13, 0.148), (14, 0.152), (15, -0.16), (16, 0.03), (17, 0.026), (18, 0.392), (19, 0.016), (20, 0.179), (21, 0.173), (22, 0.067), (23, -0.168), (24, 0.051), (25, -0.027), (26, 0.27), (27, 0.02), (28, -0.002), (29, 0.042), (30, 0.036), (31, 0.048), (32, -0.013), (33, -0.054), (34, -0.055), (35, 0.004), (36, 0.038), (37, -0.083), (38, -0.1), (39, 0.052), (40, 0.089), (41, 0.018), (42, 0.058), (43, -0.015), (44, 0.002), (45, 0.081), (46, -0.003), (47, 0.096), (48, 0.029), (49, 0.016)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97418737 184 nips-2008-Predictive Indexing for Fast Search

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

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

Author: Kevyn Collins-thompson

3 0.6063289 156 nips-2008-Nonparametric sparse hierarchical models describe V1 fMRI responses to natural images

Author: Vincent Q. Vu, Bin Yu, Thomas Naselaris, Kendrick Kay, Jack Gallant, Pradeep K. Ravikumar

4 0.57490885 83 nips-2008-Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method

Author: Dongryeol Lee, Alexander G. Gray

5 0.38425222 93 nips-2008-Global Ranking Using Continuous Conditional Random Fields

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

6 0.36791199 169 nips-2008-Online Models for Content Optimization

7 0.31339255 168 nips-2008-Online Metric Learning and Fast Similarity Search

8 0.30012232 29 nips-2008-Automatic online tuning for fast Gaussian summation

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

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

11 0.27709034 4 nips-2008-A Scalable Hierarchical Distributed Language Model

12 0.26501408 105 nips-2008-Improving on Expectation Propagation

13 0.25989553 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions

14 0.25206012 188 nips-2008-QUIC-SVD: Fast SVD Using Cosine Trees

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

16 0.2502943 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions

17 0.24486428 219 nips-2008-Spectral Hashing

18 0.22838138 82 nips-2008-Fast Computation of Posterior Mode in Multi-Level Hierarchical Models

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

20 0.22234641 167 nips-2008-One sketch for all: Theory and Application of Conditional Random Sampling

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(6, 0.057), (7, 0.053), (12, 0.046), (16, 0.011), (28, 0.181), (57, 0.044), (59, 0.011), (63, 0.024), (71, 0.019), (73, 0.328), (77, 0.05), (78, 0.018), (83, 0.06)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.77305388 184 nips-2008-Predictive Indexing for Fast Search

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

2 0.55294222 135 nips-2008-Model Selection in Gaussian Graphical Models: High-Dimensional Consistency of \boldmath$\ell 1$-regularized MLE

Author: Garvesh Raskutti, Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar

Abstract: We consider the problem of estimating the graph structure associated with a Gaussian Markov random ﬁeld (GMRF) from i.i.d. samples. We study the performance of study the performance of the ℓ1 -regularized maximum likelihood estimator in the high-dimensional setting, where the number of nodes in the graph p, the number of edges in the graph s and the maximum node degree d, are allowed to grow as a function of the number of samples n. Our main result provides sufﬁcient conditions on (n, p, d) for the ℓ1 -regularized MLE estimator to recover all the edges of the graph with high probability. Under some conditions on the model covariance, we show that model selection can be achieved for sample sizes n = Ω(d2 log(p)), with the error decaying as O(exp(−c log(p))) for some constant c. We illustrate our theoretical results via simulations and show good correspondences between the theoretical predictions and behavior in simulations.

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

Author: Liu Yang, Rong Jin, Rahul Sukthankar

Abstract: The cluster assumption is exploited by most semi-supervised learning (SSL) methods. However, if the unlabeled data is merely weakly related to the target classes, it becomes questionable whether driving the decision boundary to the low density regions of the unlabeled data will help the classiﬁcation. In such case, the cluster assumption may not be valid; and consequently how to leverage this type of unlabeled data to enhance the classiﬁcation accuracy becomes a challenge. We introduce “Semi-supervised Learning with Weakly-Related Unlabeled Data” (SSLW), an inductive method that builds upon the maximum-margin approach, towards a better usage of weakly-related unlabeled information. Although the SSLW could improve a wide range of classiﬁcation tasks, in this paper, we focus on text categorization with a small training pool. The key assumption behind this work is that, even with different topics, the word usage patterns across different corpora tends to be consistent. To this end, SSLW estimates the optimal wordcorrelation matrix that is consistent with both the co-occurrence information derived from the weakly-related unlabeled documents and the labeled documents. For empirical evaluation, we present a direct comparison with a number of stateof-the-art methods for inductive semi-supervised learning and text categorization. We show that SSLW results in a signiﬁcant improvement in categorization accuracy, equipped with a small training set and an unlabeled resource that is weakly related to the test domain.

4 0.5515905 79 nips-2008-Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

Author: Francis R. Bach

Abstract: For supervised and unsupervised learning, positive deﬁnite kernels allow to use large and potentially inﬁnite dimensional feature spaces with a computational cost that only depends on the number of observations. This is usually done through the penalization of predictor functions by Euclidean or Hilbertian norms. In this paper, we explore penalizing by sparsity-inducing norms such as the ℓ1 -norm or the block ℓ1 -norm. We assume that the kernel decomposes into a large sum of individual basis kernels which can be embedded in a directed acyclic graph; we show that it is then possible to perform kernel selection through a hierarchical multiple kernel learning framework, in polynomial time in the number of selected kernels. This framework is naturally applied to non linear variable selection; our extensive simulations on synthetic datasets and datasets from the UCI repository show that efﬁciently exploring the large feature space through sparsity-inducing norms leads to state-of-the-art predictive performance.

5 0.55083352 173 nips-2008-Optimization on a Budget: A Reinforcement Learning Approach

Author: Paul L. Ruvolo, Ian Fasel, Javier R. Movellan

Abstract: Many popular optimization algorithms, like the Levenberg-Marquardt algorithm (LMA), use heuristic-based “controllers” that modulate the behavior of the optimizer during the optimization process. For example, in the LMA a damping parameter λ is dynamically modiﬁed based on a set of rules that were developed using heuristic arguments. Reinforcement learning (RL) is a machine learning approach to learn optimal controllers from examples and thus is an obvious candidate to improve the heuristic-based controllers implicit in the most popular and heavily used optimization algorithms. Improving the performance of off-the-shelf optimizers is particularly important for time-constrained optimization problems. For example the LMA algorithm has become popular for many real-time computer vision problems, including object tracking from video, where only a small amount of time can be allocated to the optimizer on each incoming video frame. Here we show that a popular modern reinforcement learning technique using a very simple state space can dramatically improve the performance of general purpose optimizers, like the LMA. Surprisingly the controllers learned for a particular domain also work well in very different optimization domains. For example we used RL methods to train a new controller for the damping parameter of the LMA. This controller was trained on a collection of classic, relatively small, non-linear regression problems. The modiﬁed LMA performed better than the standard LMA on these problems. This controller also dramatically outperformed the standard LMA on a difﬁcult computer vision problem for which it had not been trained. Thus the controller appeared to have extracted control rules that were not just domain speciﬁc but generalized across a range of optimization domains. 1

6 0.55072242 195 nips-2008-Regularized Policy Iteration

7 0.54985833 231 nips-2008-Temporal Dynamics of Cognitive Control

8 0.54919583 14 nips-2008-Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models

9 0.54871905 196 nips-2008-Relative Margin Machines

10 0.54855996 227 nips-2008-Supervised Exponential Family Principal Component Analysis via Convex Optimization

11 0.54846364 48 nips-2008-Clustering via LP-based Stabilities

12 0.54842407 113 nips-2008-Kernelized Sorting

13 0.54782498 4 nips-2008-A Scalable Hierarchical Distributed Language Model

14 0.54774868 49 nips-2008-Clusters and Coarse Partitions in LP Relaxations

15 0.547095 21 nips-2008-An Homotopy Algorithm for the Lasso with Online Observations

16 0.5470553 245 nips-2008-Unlabeled data: Now it helps, now it doesn't

17 0.5466432 201 nips-2008-Robust Near-Isometric Matching via Structured Learning of Graphical Models

18 0.54625589 176 nips-2008-Partially Observed Maximum Entropy Discrimination Markov Networks

19 0.54569584 50 nips-2008-Continuously-adaptive discretization for message-passing algorithms

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