nips nips2009 nips2009-157 knowledge-graph by maker-knowledge-mining

157 nips-2009-Multi-Label Prediction via Compressed Sensing

Source: pdf

Author: John Langford, Tong Zhang, Daniel J. Hsu, Sham M. Kakade

Abstract: We consider multi-label prediction problems with large output spaces under the assumption of output sparsity – that the target (label) vectors have small support. We develop a general theory for a variant of the popular error correcting output code scheme, using ideas from compressed sensing for exploiting this sparsity. The method can be regarded as a simple reduction from multi-label regression problems to binary regression problems. We show that the number of subproblems need only be logarithmic in the total number of possible labels, making this approach radically more efﬁcient than others. We also state and prove robustness guarantees for this method in the form of regret transform bounds (in general), and also provide a more detailed analysis for the linear prediction setting. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We consider multi-label prediction problems with large output spaces under the assumption of output sparsity – that the target (label) vectors have small support. [sent-9, score-0.665]

2 We develop a general theory for a variant of the popular error correcting output code scheme, using ideas from compressed sensing for exploiting this sparsity. [sent-10, score-0.781]

3 We also state and prove robustness guarantees for this method in the form of regret transform bounds (in general), and also provide a more detailed analysis for the linear prediction setting. [sent-13, score-0.424]

4 A standard approach to this task is to collect a sample of these images x along with corresponding labels y = (y1 , . [sent-15, score-0.175]

5 , yd ) ∈ {0, 1}d , where yi = 1 if and only if person or object i is depicted in image x, and then feed the labeled sample to a multi-label learning algorithm. [sent-18, score-0.102]

6 103 , 104 ), the simple one-against-all approach of learning a single predictor for each entity can become prohibitively expensive, both at training and testing time. [sent-22, score-0.266]

7 Our motivation for the present work comes from the observation that although the output (label) space may be very high dimensional, the actual labels are often sparse. [sent-23, score-0.303]

8 In this work, we consider how this sparsity in the output space, or output sparsity, eases the burden of large-scale multi-label learning. [sent-25, score-0.535]

9 A subtle but critical point that distinguishes output sparsity from more common notions of sparsity (say, in feature or weight vectors) is that we are interested in the sparsity of E[y|x] rather than y. [sent-27, score-0.906]

10 A crucial observation – central to the area of compressed sensing [1] – is that methods exist to recover E[y|x] from just O(k log d) measurements when E[y|x] is k-sparse. [sent-34, score-0.579]

11 We show how to apply algorithms for compressed sensing to the output coding approach [2]. [sent-37, score-0.817]

12 At a high level, the output coding approach creates a collection of subproblems of the form “Is the label in this subset or its complement? [sent-38, score-0.5]

13 The role of compressed sensing in our application is distinct from its more conventional uses in data compression. [sent-40, score-0.538]

14 Although we do employ a sensing matrix to compress training data, we ultimately are not interested in recovering data explicitly compressed this way. [sent-41, score-0.699]

15 Rather, we learn to predict compressed label vectors, and then use sparse reconstruction algorithms to recover uncompressed labels from these predictions. [sent-42, score-1.115]

16 Thus we are interested in reconstruction accuracy of predictions, averaged over the data distribution. [sent-43, score-0.32]

17 A formal application of compressed sensing to prediction problems with output sparsity. [sent-45, score-0.83]

18 An efﬁcient output coding method, in which the number of required predictions is only logarithmic in the number of labels d, making it applicable to very large-scale problems. [sent-47, score-0.426]

19 Robustness guarantees, in the form of regret transform bounds (in general) and a further detailed analysis for the linear prediction setting. [sent-49, score-0.288]

20 The ubiquity of multi-label prediction problems in domains ranging from multiple object recognition in computer vision to automatic keyword tagging for content databases has spurred the development of numerous general methods for the task. [sent-51, score-0.13]

21 Perhaps the most straightforward approach is the well-known one-against-all reduction [3], but this can be too expensive when the number of possible labels is large (especially if applied to the power set of the label space [4]). [sent-52, score-0.336]

22 When structure can be imposed on the label space (e. [sent-53, score-0.147]

23 class hierarchy), efﬁcient learning and prediction methods are often possible [5, 6, 7, 8, 9]. [sent-55, score-0.13]

24 Here, we focus on a different type of structure, namely output sparsity, which is not addressed in previous work. [sent-56, score-0.162]

25 Moreover, our method is general enough to take advantage of structured notions of sparsity (e. [sent-57, score-0.28]

26 Recently, heuristics have been proposed for discovering structure in large output spaces that empirically offer some degree of efﬁciency [11]. [sent-60, score-0.162]

27 As previously mentioned, our work is most closely related to the class of output coding method for multi-class prediction, which was ﬁrst introduced and shown to be useful experimentally in [2]. [sent-61, score-0.236]

28 Relative to this work, we expand the scope of the approach to multi-label prediction and provide bounds on regret and error which guide the design of codes. [sent-62, score-0.292]

29 The loss based decoding approach [12] suggests decoding so as to minimize loss. [sent-63, score-0.152]

30 The output coding approach is inconsistent when classiﬁers are used and the underlying problems being encoded are noisy. [sent-65, score-0.236]

31 This is proved and analyzed in [13], where it is also shown that using a Hadamard code creates a robust consistent predictor when reduced to binary regression. [sent-66, score-0.27]

32 Compared to this method, our approach achieves the same robustness guarantees up to a constant factor, but requires training and evaluating exponentially (in d) fewer predictors. [sent-67, score-0.172]

33 Our algorithms rely on several methods from compressed sensing, which we detail where used. [sent-68, score-0.396]

34 2 Preliminaries Let X be an arbitrary input space and Y ⊂ Rd be a d-dimensional output (label) space. [sent-69, score-0.162]

35 Our goal is to learn a predictor F : X → Y with low expected ℓ2 -error Ex F (x) − E[y|x] 2 (the sum of mean-squared2 2 errors over all labels) using a set of n training data {(xi , yi )}n . [sent-71, score-0.266]

36 i=1 We focus on the regime in which the output space is very high-dimensional (d very large), but for any given x ∈ X , the expected value E[y|x] of the corresponding label y ∈ Y has only a few non-zero entries. [sent-72, score-0.309]

37 1 Learning and Prediction Learning to Predict Compressed Labels Let A : Rd → Rm be a linear compression function, where m ≤ d (but hopefully m ≪ d). [sent-75, score-0.249]

38 reduce the dimension of) the labels Y, and learn a predictor H : X → A(Y) of these compressed labels. [sent-78, score-0.724]

39 Speciﬁcally, given a sample {(xi , yi )}n , we form a compressed sample {(xi , Ayi )}n and then i=1 i=1 learn a predictor H of E[Ay|x] with the objective of minimizing the ℓ2 -error Ex H(x)−E[Ay|x] 2 . [sent-80, score-0.583]

40 2 Predicting Sparse Labels To obtain a predictor F of E[y|x], we compose the predictor H of E[Ay|x] (learned using the compressed sample) with a reconstruction algorithm R : Rm → Rd . [sent-82, score-1.098]

41 The algorithm R maps predictions of compressed labels h ∈ Rm to predictions of labels y ∈ Y in the original output space. [sent-83, score-0.895]

42 These algorithms typically aim to ﬁnd a sparse vector y such that Ay closely approximates h. [sent-84, score-0.108]

43 Recent developments in the area of compressed sensing have produced a spate of reconstruction algorithms with strong performance guarantees when the compression function A satisﬁes certain properties. [sent-85, score-1.147]

44 The function f is the output sparsity of R and the constants C1 and C2 are the regret factors. [sent-89, score-0.485]

45 Informally, if the predicted compressed label H(x) is close to E[Ay|x] = AE[y|x], then the sparse vector y returned by the reconstruction algorithm should be close to E[y|x]; this latter distance y −E[y|x] 2 should degrade gracefully in terms of the accuracy of H(x) and the sparsity of E[y|x]. [sent-90, score-1.149]

46 2 Moreover, the algorithm should be agnostic about the sparsity of E[y|x] (and thus the sparsity error sperr(k, E[y|x])), as well as the “measurement noise” (the prediction error H(x) − E[Ay|x] 2 ). [sent-91, score-0.624]

47 This is a subtle condition and precludes certain reconstruction algorithm (e. [sent-92, score-0.325]

48 However, the condition is needed in our application, as such bounds on the prediction error (for each x) are not generally known beforehand. [sent-95, score-0.221]

49 The minimum number of rows of matrices A ∈ Ak may in general depend on k (as well as the ambient dimension d). [sent-98, score-0.115]

50 The sparsity error sperr(k, y) should measure how poorly y ∈ Rd is approximated by a k-sparse vector. [sent-101, score-0.247]

51 A reasonable output sparsity f (k) for sparsity level k should not be much more than k, e. [sent-103, score-0.584]

52 Concrete examples of valid reconstruction algorithms (along with the associated Ak , sperr, etc. [sent-106, score-0.389]

53 We give some examples of compression functions and reconstruction algorithms in the following subsections. [sent-109, score-0.545]

54 3 Algorithm 1 Training algorithm parameters sparsity level k, compression function A ∈ Ak with m rows, regression learning algorithm L input training data S ⊂ X × Rd for i = 1, . [sent-110, score-0.464]

55 , m do hi ← L({(x, (Ay)i ) : (x, y) ∈ S}) end for output regressors H = [h1 , . [sent-113, score-0.213]

56 , hm ] Algorithm 2 Prediction algorithm parameters sparsity level k, compression function A ∈ Ak with m rows, valid reconstruction algorithm R for Ak input regressors H = [h1 , . [sent-116, score-0.888]

57 , hm ], test point x ∈ X output y = R(k, A, [h1 (x), . [sent-119, score-0.225]

58 , hm (x)]) Figure 1: Training and prediction algorithms. [sent-122, score-0.193]

59 1 Compression Functions Several valid reconstruction algorithms are known for compression matrices that satisfy a restricted isometry property. [sent-124, score-0.657]

60 A striking feature of these constructions is the very mild dependence of m on the ambient dimension d. [sent-140, score-0.115]

61 Some reconstruction algorithms require a stronger guarantee of bounded coherence µ(A) ≤ O(1/k), where µ(A) deﬁned as µ(A) = max |(A⊤ A)i,j |/ 1≤i < d, we potentially incur an extra penalty in sperr(k, E[y|x]), which relates how far E[y|x] is from being k-sparse. [sent-142, score-0.328]

62 This is an oft cited issue with using output codes for multiclass problems. [sent-147, score-0.209]

63 Suppose, for instance, there is a perfect linear predictor of E[y|x], i. [sent-149, score-0.262]

64 Then it is easy to see that H = BA⊤ is a perfect linear predictor of E[Ay|x]: H ⊤ x = AB ⊤ x = AE[y|x] = E[Ay|x]. [sent-152, score-0.262]

65 Theorem 4 implies that the errors of any linear predictor are not magniﬁed much by the compression function. [sent-165, score-0.479]

66 So a good linear predictor for the original problem implies an almost-as-good linear predictor for the induced problem. [sent-166, score-0.524]

67 Using this theorem together with known results about linear prediction [22], it is straightforward to derive sample complexity bounds for achieving a given error relative to that of the best linear predictor in some class. [sent-167, score-0.515]

68 [23, 22]) which are concerned with sparsity in the weight vector, rather than in the output. [sent-171, score-0.211]

69 6 6 Experimental Validation We conducted an empirical assessment of our proposed reduction on two labeled data sets with large label spaces. [sent-172, score-0.195]

70 These experiments demonstrate the feasibility of our method – a sanity check that the reduction does in fact preserve learnability – and compare different compression and reconstruction options. [sent-173, score-0.588]

71 1 The ﬁrst data set was collected by the ESP Game [24], an online game in which players ultimately provide word tags for a diverse set of web images. [sent-176, score-0.19]

72 We retained just the 1000 most frequent labels: the least frequent of these occurs 39 times in the data, and the most frequent occurs about 12000 times. [sent-178, score-0.348]

73 We used half of the data for training and half for testing. [sent-180, score-0.136]

74 Speciﬁcally, we identiﬁed 1024 representative SURF features points [26] from 10 × 10 gray-scale patches chosen randomly from the training images; this partitions the space of image patches (represented with SURF features) into Voronoi cells. [sent-182, score-0.193]

75 us, a social bookmarking service in which users assign descriptive textual tags to web pages. [sent-188, score-0.107]

76 The least frequent label occurs 21 times and the most frequent occurs almost 6500 times. [sent-190, score-0.407]

77 Again, we used half the data for training and half for testing. [sent-192, score-0.136]

78 Each binary label vector (in both data sets) indicates the labels of the corresponding data point. [sent-195, score-0.288]

79 We computed the least-squares linear regressor B ∈ Rp×d on the training data (without any output coding) and predicted the label probabilities p(x) = B ⊤ x on the test data (clipping values to the range [0, 1]). [sent-198, score-0.416]

80 Examining Ex ǫ(k, p(x)) as a function of k, we saw that in both the image and text data, the falloff with k is eventually super-polynomial, but we are interested in the behavior for small k where it appears polynomial k −r for some r. [sent-203, score-0.14]

81 Thus, we expect the reconstruction algorithms will have to contend with the sparsity error of the target. [sent-210, score-0.606]

82 3 Procedure We used least-squares linear regression as our base learning algorithm, with no regularization on the image data and with ℓ2 -regularization with the text data (λ = 0. [sent-212, score-0.137]

83 html 7 The compression functions we used were generated by selecting m random rows of the 1024 × 1024 Hadamard matrix, for m ∈ {100, 200, 300, 400}. [sent-222, score-0.285]

84 We tested the greedy and iterative reconstruction algorithms described earlier (OMP, FoBa, and CoSaMP) as well as a path-following version of Lasso based on LARS [21]. [sent-224, score-0.328]

85 Each algorithm was used to recover a k-sparse label vector y k from the predicted compressed label H(x), for k = 1, . [sent-225, score-0.727]

86 We measured the ℓ2 distance y k − y 2 of the prediction to the true test label y. [sent-229, score-0.277]

87 In 2 2 addition, we measured the precision of the predicted support at various values of k using the 10sparse label prediction. [sent-230, score-0.186]

88 That is, we ordered the coefﬁcients of each 10-sparse label prediction y 10 10 by magnitude, and measured the precision of predicting the ﬁrst k coordinates | supp(y(1:k) ) ∩ 2k 10 supp(y)|/k. [sent-231, score-0.323]

89 We used correlation decoding (CD) as a baseline method, as it is a standard decoding method for ECOC approaches. [sent-233, score-0.152]

90 Note that CD is not a valid reconstruction algorithm when m < d. [sent-236, score-0.346]

91 But when the compression function A is in AK for a sufﬁciently large K, then the squared-error decreases as the output sparsity k increases up to K. [sent-239, score-0.59]

92 All of the reconstruction algorithms at least match or out-performed the baseline on the meansquared-error criterion, except when m = 100. [sent-241, score-0.328]

93 In this case, when choosing k > K columns, it is better to choose correlated columns to avoid over-ﬁtting. [sent-243, score-0.1]

94 Both OMP and FoBa explicitly avoid this and thus do not fare well; but CoSaMP, Lasso, and CD do allow selecting correlated columns and thus perform better in this regime. [sent-244, score-0.1]

95 This is because the extra correlated columns need not correspond to accurate label coordinates. [sent-246, score-0.247]

96 In summary, the experiments demonstrate the feasibility and robustness of our reduction method for two natural multi-label prediction tasks. [sent-247, score-0.288]

97 They show that predictions of relatively few compressed labels are sufﬁcient to recover an accurate sparse label vector, and as our theory suggests, the robustness of the reconstruction algorithms is a key factor in their success. [sent-248, score-1.196]

98 Support vector machine learning for interdependent and structured output spaces. [sent-296, score-0.195]

99 Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements. [sent-344, score-0.285]

100 Stable recovery of sparse overcomplete representations in the presence of noise. [sent-385, score-0.103]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('compressed', 0.353), ('reconstruction', 0.285), ('predictor', 0.23), ('compression', 0.217), ('sperr', 0.216), ('sparsity', 0.211), ('ay', 0.199), ('sensing', 0.185), ('ak', 0.166), ('output', 0.162), ('label', 0.147), ('labels', 0.141), ('prediction', 0.13), ('surf', 0.108), ('frequent', 0.088), ('ex', 0.083), ('sham', 0.081), ('cosamp', 0.081), ('cd', 0.08), ('rp', 0.077), ('ae', 0.077), ('subproblems', 0.077), ('rm', 0.077), ('decoding', 0.076), ('coding', 0.074), ('robustness', 0.072), ('tsoumakas', 0.072), ('regret', 0.071), ('rd', 0.07), ('image', 0.069), ('rows', 0.068), ('constructions', 0.068), ('sparse', 0.065), ('guarantees', 0.064), ('hm', 0.063), ('foba', 0.063), ('web', 0.062), ('valid', 0.061), ('hadamard', 0.06), ('columns', 0.058), ('multilabel', 0.058), ('esp', 0.058), ('bounds', 0.055), ('ba', 0.054), ('danger', 0.054), ('supp', 0.054), ('isometry', 0.051), ('regressors', 0.051), ('compress', 0.051), ('omp', 0.051), ('half', 0.05), ('predictions', 0.049), ('degrade', 0.049), ('reduction', 0.048), ('multiclass', 0.047), ('ambient', 0.047), ('coordinates', 0.046), ('tong', 0.045), ('tags', 0.045), ('correcting', 0.045), ('polynomially', 0.045), ('game', 0.044), ('patches', 0.044), ('algorithms', 0.043), ('correlated', 0.042), ('occurs', 0.042), ('inaccurate', 0.041), ('recover', 0.041), ('constants', 0.041), ('predict', 0.04), ('kakade', 0.04), ('subtle', 0.04), ('langford', 0.04), ('creates', 0.04), ('predicted', 0.039), ('ultimately', 0.039), ('recovery', 0.038), ('feasibility', 0.038), ('entities', 0.038), ('page', 0.037), ('text', 0.036), ('error', 0.036), ('training', 0.036), ('notions', 0.036), ('interested', 0.035), ('images', 0.034), ('structured', 0.033), ('depicted', 0.033), ('linear', 0.032), ('clipping', 0.031), ('djhsu', 0.031), ('karthik', 0.031), ('sridharan', 0.031), ('boutell', 0.031), ('cotter', 0.031), ('rotational', 0.031), ('contend', 0.031), ('luc', 0.031), ('terrence', 0.031), ('allwein', 0.031)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999982 157 nips-2009-Multi-Label Prediction via Compressed Sensing

Author: John Langford, Tong Zhang, Daniel J. Hsu, Sham M. Kakade

2 0.19298208 55 nips-2009-Compressed Least-Squares Regression

Author: Odalric Maillard, Rémi Munos

Abstract: We consider the problem of learning, from K data, a regression function in a linear space of high dimension N using projections onto a random subspace of lower dimension M . From any algorithm minimizing the (possibly penalized) empirical risk, we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We show that solving the problem in the compressed domain instead of the initial domain reduces the estimation error at the price of an increased (but controlled) approximation error. We apply the analysis to Least-Squares (LS) regression and discuss the excess risk and numerical complexity of the resulting “Compressed Least Squares Re√ gression” (CLSR) in terms of N , K, and M . When we choose M = O( K), we √ show that CLSR has an estimation error of order O(log K/ K). 1 Problem setting We consider a regression problem where we observe data DK = ({xk , yk }k≤K ) (where xk ∈ X and yk ∈ R) are assumed to be independently and identically distributed (i.i.d.) from some distribution P , where xk ∼ PX and yk = f ∗ (xk ) + ηk (xk ), where f ∗ is the (unknown) target function, and ηk a centered independent noise of variance σ 2 (xk ). For a given class of functions F, and f ∈ F, we deﬁne the empirical (quadratic) error def LK (f ) = 1 K K [yk − f (xk )]2 , k=1 and the generalization (quadratic) error def L(f ) = E(X,Y )∼P [(Y − f (X))2 ]. Our goal is to return a regression function f ∈ F with lowest possible generalization error L(f ). Notations: In the sequel we will make use of the following notations about norms: for h : X → R, we write ||h||P for the L2 norm of h with respect to (w.r.t.) the measure P , ||h||PK for the L2 norm n 2 1/2 of h w.r.t. the empirical measure PK , and for u ∈ Rn , ||u|| denotes by default . i=1 ui The measurable function minimizing the generalization error is f ∗ , but it may be the case that f ∗ ∈ F. For any regression function f , we deﬁne the excess risk / L(f ) − L(f ∗ ) = ||f − f ∗ ||2 , P which decomposes as the sum of the estimation error L(f ) − inf f ∈F L(f ) and the approximation error inf f ∈F L(f ) − L(f ∗ ) = inf f ∈F ||f − f ∗ ||2 which measures the distance between f ∗ and the P function space F. 1 In this paper we consider a class of linear functions FN deﬁned as the span of a set of N functions def def N {ϕn }1≤n≤N called features. Thus: FN = {fα = n=1 αn ϕn , α ∈ RN }. When the number of data K is larger than the number of features N , the ordinary Least-Squares Regression (LSR) provides the LS solution fα which is the minimizer of the empirical risk LK (f ) b 1 in FN . Note that here LK (fα ) rewrites K ||Φα − Y ||K where Φ is the K × N matrix with elements (ϕn (xk ))1≤n≤N,1≤k≤K and Y the K-vector with components (yk )1≤k≤K . Usual results provide bound on the estimation error as a function of the capacity of the function space and the number of data. In the case of linear approximation, the capacity measures (such as covering numbers [23] or the pseudo-dimension [16]) depend on the number of features (for example the pseudo-dimension is at most N + 1). For example, let fα be a LS estimate (minimizer of LK b in FN ), then (a more precise statement will be stated later in Subsection 3) the expected estimation error is bounded as: N log K E L(fα ) − inf L(f ) ≤ cσ2 , (1) b f ∈FN K def where c is a universal constant, σ = supx∈X σ(x), and the expectation is taken with respect to P . Now, the excess risk is the sum of this estimation error and the approximation error inf f ∈FN ||f − f ∗ ||P of the class FN . Since the later usually decreases when the number of features N increases [13] (e.g. when N FN is dense in L2 (P )), we see the usual tradeoff between small estimation error (low N ) and small approximation error (large N ). In this paper we are interested in the setting when N is large so that the approximation error is small. Whenever N is larger than K we face the overﬁtting problem since there are more parameters than actual data (more variables than constraints), which is illustrated in the bound (1) which provides no information about the generalization ability of any LS estimate. In addition, there are many minimizers (in fact a vector space of same dimension as the null space of ΦT Φ) of the empirical risk. To overcome the problem, several approaches have been proposed in the literature: • LS solution with minimal norm: The solution is the minimizer of the empirical error with minimal (l1 or l2 )-norm: α = arg minΦα=Y ||α||1 or 2 , (or a robust solution arg min||Φα−Y ||2 ≤ε ||α||1 ). The choice of 2 -norm yields the ordinary LS solution. The choice of 1 -norm has been used for generating sparse solutions (e.g. the Basis Pursuit [10]), and assuming that the target function admits a sparse decomposition, the ﬁeld of Compressed Sensing [9, 21] provides sufﬁcient conditions for recovering the exact solution. However, such conditions (e.g. that Φ possesses a Restricted Isometric Property (RIP)) does not hold in general in this regression setting. On another aspect, solving these problems (both for l1 or l2 -norm) when N is large is numerically expensive. • Regularization. The solution is the minimizer of the empirical error plus a penalty term, for example f = arg min LK (f ) + λ||f ||p , for p = 1 or 2. p f ∈FN where λ is a parameter and usual choices for the norm are 2 (ridge-regression [20]) and 1 (LASSO [19]). A close alternative is the Dantzig selector [8, 5] which solves: α = arg min||α||1 ≤λ ||ΦT (Y − Φα)||∞ . The numerical complexity and generalization bounds of those methods depend on the sparsity of the target function decomposition in FN . Now if we possess a sequence of function classes (FN )N ≥1 with increasing capacity, we may perform structural risk minimization [22] by solving in each model the empirical risk penalized by a term that depends on the size of the model: fN = arg minf ∈FN ,N ≥1 LK (f ) + pen(N, K), where the penalty term measures the capacity of the function space. In this paper we follow another approach where instead of searching in the large space FN (where N > K) for a solution that minimizes the empirical error plus a penalty term, we simply search for the empirical error minimizer in a (randomly generated) lower dimensional subspace GM ⊂ FN (where M < K). Our contribution: We consider a set of M random linear combinations of the initial N features and perform our favorite LS regression algorithm (possibly regularized) using those “compressed 2 features”. This is equivalent to projecting the K points {ϕ(xk ) ∈ RN , k = 1..K} from the initial domain (of size N ) onto a random subspace of dimension M , and then performing the regression in the “compressed domain” (i.e. span of the compressed features). This is made possible because random projections approximately preserve inner products between vectors (by a variant of the Johnson-Lindenstrauss Lemma stated in Proposition 1. Our main result is a bound on the excess risk of a linear estimator built in the compressed domain in terms of the excess risk of the linear estimator built in the initial domain (Section 2). We further detail the case of ordinary Least-Squares Regression (Section 3) and discuss, in terms of M , N , K, the different tradeoffs concerning the excess risk (reduced estimation error in the compressed domain versus increased approximation error introduced by the random projection) and the numerical complexity (reduced complexity of solving the LSR in the compressed domain versus the additional load of performing the projection). √ As a consequence, we show that by choosing M = O( K) projections we deﬁne a Compressed Least-Squares Regression which uses O(N K 3/2 ) elementary operations to compute a regression √ function with estimation error (relatively to the initial function space FN ) of order log K/ K up to a multiplicative factor which depends on the best approximation of f ∗ in FN . This is competitive with the best methods, up to our knowledge. Related works: Using dimension reduction and random projections in various learning areas has received considerable interest over the past few years. In [7], the authors use a SVM algorithm in a compressed space for the purpose of classiﬁcation and show that their resulting algorithm has good generalization properties. In [25], the authors consider a notion of compressed linear regression. For data Y = Xβ + ε, where β is the target and ε a standard noise, they use compression of the set of data, thus considering AY = AXβ + Aε, where A has a Restricted Isometric Property. They provide an analysis of the LASSO estimator built from these compressed data, and discuss a property called sparsistency, i.e. the number of random projections needed to recover β (with high probability) when it is sparse. These works differ from our approach in the fact that we do not consider a compressed (input and/or output) data space but a compressed feature space instead. In [11], the authors discuss how compressed measurements may be useful to solve many detection, classiﬁcation and estimation problems without having to reconstruct the signal ever. Interestingly, they make no assumption about the signal being sparse, like in our work. In [6, 17], the authors show how to map a kernel k(x, y) = ϕ(x) · ϕ(y) into a low-dimensional space, while still approximately preserving the inner products. Thus they build a low-dimensional feature space speciﬁc for (translation invariant) kernels. 2 Linear regression in the compressed domain We remind that the initial set of features is {ϕn : X → def N FN = {fα = n=1 αn ϕn , α ∈ components (ϕn (x))n≤N . Let us R, 1 ≤ n ≤ N } and the initial domain R } is the span of those features. We write ϕ(x) the N -vector of N now deﬁne the random projection. Let A be a M × N matrix of i.i.d. elements drawn for some distribution ρ. Examples of distributions are: • Gaussian random variables N (0, 1/M ), √ • ± Bernoulli distributions, i.e. which takes values ±1/ M with equal probability 1/2, • Distribution taking values ± 3/M with probability 1/6 and 0 with probability 2/3. The following result (proof in the supplementary material) states the property that inner-product are approximately preserved through random projections (this is a simple consequence of the JohnsonLindenstrauss Lemma): Proposition 1 Let (uk )1≤k≤K and v be vectors of RN . Let A be a M × N matrix of i.i.d. elements drawn from one of the previously deﬁned distributions. For any ε > 0, δ > 0, for M ≥ ε2 1 ε3 log 4K , we have, with probability at least 1 − δ, for all k ≤ K, δ 4 − 6 |Auk · Av − uk · v| ≤ ε||uk || ||v||. 3 def We now introduce the set of M compressed features (ψm )1≤m≤M such that ψm (x) = N We also write ψ(x) the M -vector of components (ψm (x))m≤M . Thus n=1 Am,n ϕn (x). ψ(x) = Aϕ(x). We deﬁne the compressed domain GM = {gβ = m=1 βm ψm , β ∈ RM } the span of the compressed features (vector space of dimension at most M ). Note that each ψm ∈ FN , thus GM is a subspace of FN . def 2.1 M Approximation error We now compare the approximation error assessed in the compressed domain GM versus in the initial space FN . This applies to the linear algorithms mentioned in the introduction such as ordinary LS regression (analyzed in details in Section 3), but also its penalized versions, e.g. LASSO and ridge regression. Deﬁne α+ = arg minα∈RN L(fα ) − L(f ∗ ) the parameter of the best regression function in FN . Theorem 1 For any δ > 0, any M ≥ 15 log(8K/δ), let A be a random M × N matrix deﬁned like in Proposition 1, and GM be the compressed domain resulting from this choice of A. Then with probability at least 1 − δ, inf ||g−f ∗ ||2 ≤ P g∈GM 8 log(8K/δ) + 2 ||α || M E ||ϕ(X)||2 +2 sup ||ϕ(x)||2 x∈X log 4/δ + inf ||f −f ∗ ||2 . P f ∈FN 2K (2) This theorem shows the tradeoff in terms of estimation and approximation errors for an estimator g obtained in the compressed domain compared to an estimator f obtained in the initial domain: • Bounds on the estimation error of g in GM are usually smaller than that of f in FN when M < N (since the capacity of FN is larger than that of GM ). • Theorem 1 says that the approximation error assessed in GM increases by at most O( log(K/δ) )||α+ ||2 E||ϕ(X)||2 compared to that in FN . M def def Proof: Let us write f + = fα+ = arg minf ∈FN ||f − f ∗ ||P and g + = gAα+ . The approximation error assessed in the compressed domain GM is bounded as inf ||g − f ∗ ||2 P g∈GM ≤ ||g + − f ∗ ||2 = ||g + − f + ||2 + ||f + − f ∗ ||2 , P P P (3) since f + is the orthogonal projection of f ∗ on FN and g + belongs to FN . We now bound ||g + − def def f + ||2 using concentration inequalities. Deﬁne Z(x) = Aα+ · Aϕ(x) − α+ · ϕ(x). Deﬁne ε2 = P log(8K/δ) 8 M log(8K/δ). For M ≥ 15 log(8K/δ) we have ε < 3/4 thus M ≥ ε2 /4−ε3 /6 . Proposition 1 applies and says that on an event E of probability at least 1 − δ/2, we have for all k ≤ K, def |Z(xk )| ≤ ε||α+ || ||ϕ(xk )|| ≤ ε||α+ || sup ||ϕ(x)|| = C (4) x∈X On the event E, we have with probability at least 1 − δ , ||g + − f + ||2 P = ≤ ≤ EX∼PX |Z(X)|2 ≤ ε2 ||α+ ||2 ε2 ||α+ ||2 1 K 1 K K |Z(xk )|2 + C 2 k=1 K ||ϕ(xk )||2 + sup ||ϕ(x)||2 x∈X k=1 E ||ϕ(X)||2 + 2 sup ||ϕ(x)||2 x∈X log(2/δ ) 2K log(2/δ ) 2K log(2/δ ) . 2K where we applied two times Chernoff-Hoeffding’s inequality. Combining with (3), unconditioning, and setting δ = δ/2 then with probability at least (1 − δ/2)(1 − δ ) ≥ 1 − δ we have (2). 4 2.2 Computational issues We now discuss the relative computational costs of a given algorithm applied either in the initial or in the compressed domain. Let us write Cx(DK , FN , P ) the complexity (e.g. number of elementary operations) of an algorithm A to compute the regression function f when provided with the data DK and function space FN . We plot in the table below, both for the initial and the compressed versions of the algorithm A, the order of complexity for (i) the cost for building the feature matrix, (ii) the cost for computing the estimator, (iii) the cost for making one prediction (i.e. computing f (x) for any x): Construction of the feature matrix Computing the regression function Making one prediction Initial domain NK Cx(DK , FN , P ) N Compressed domain N KM Cx(DK , GM , P ) NM Note that the values mentioned for the compressed domain are upper-bounds on the real complexity and do not take into account the possible sparsity of the projection matrix A (which would speed up matrix computations, see e.g. [2, 1]). 3 Compressed Least-Squares Regression We now analyze the speciﬁc case of Least-Squares Regression. 3.1 Excess risk of ordinary Least Squares regression In order to bound the estimation error, we follow the approach of [13] which truncates (up to the level ±L where L is a bound, assumed to be known, on ||f ∗ ||∞ ) the prediction of the LS regression function. The ordinary LS regression provides the regression function fα where b α= argmin α∈argminα ∈ RN ||α||. ||Y −Φα || Note that ΦΦT α = ΦT Y , hence α = Φ† Y ∈ RN where Φ† is the Penrose pseudo-inverse of Φ1 . def Then the truncated predictor is: fL (x) = TL [fα (x)], where b def TL (u) = u if |u| ≤ L, L sign(u) otherwise. Truncation after the computation of the parameter α ∈ RN , which is the solution of an unconstrained optimization problem, is easier than solving an optimization problem under the constraint that ||α|| is small (which is the approach followed in [23]) and allows for consistency results and prediction bounds. Indeed, the excess risk of fL is bounded as 1 + log K E(||f − f ∗ ||2 ) ≤ c max{σ2 , L2 } N + 8 inf ||f − f ∗ ||2 (5) P P f ∈FN K where a bound on c is 9216 (see [13]). We have a simpler bound when we consider the expectation EY conditionally on the input data: N EY (||f − f ∗ ||2 K ) ≤ σ2 + inf ||f − f ∗ ||2 K (6) P P K f ∈F Remark: Note that because we use the quadratic loss function, by following the analysis in [3], or by deriving tight bounds on the Rademacher complexity [14] and following Theorem 5.2 of Koltchinskii’s Saint Flour course, it is actually possible to state assumptions under which we can remove the log K term in (5). We will not further detail such bounds since our motivation here is not to provide the tightest possible bounds, but rather to show how the excess risk bound for LS regression in the initial domain extends to the compressed domain. 1 In the full rank case, Φ† = (ΦT Φ)−1 ΦT when K ≥ N and Φ† = ΦT (ΦΦT )−1 when K ≤ N 5 3.2 Compressed Least-Squares Regression (CLSR) CLSR is deﬁned as the ordinary LSR in the compressed domain. Let β = Ψ† Y ∈ RM , where Ψ is the K × M matrix with elements (ψm (xk ))1≤m≤M,1≤k≤K . The CLSR estimate is deﬁned as def gL (x) = TL [gβ (x)]. From Theorem 1, (5) and (6), we deduce the following excess risk bounds for b the CLSR estimate: √ ||α+ || E||ϕ(X)||2 K log(8K/δ) Corollary 1 For any δ > 0, set M = 8 max(σ,L) c (1+log K) . Then whenever M ≥ 15 log(8K/δ), with probability at least 1 − δ, the expected excess risk of the CLSR estimate is bounded as √ E(||gL − f ∗ ||2 ) ≤ 16 c max{σ, L}||α+ || E||ϕ(X)||2 P × 1+ supx ||ϕ(x)||2 E||ϕ(X)||2 (1 + log K) log(8K/δ) K log 4/δ + 8 inf ||f − f ∗ ||2 . P f ∈FN 2K (7) √ ||α+ || E||ϕ(X)||2 Now set M = 8K log(8K/δ). Assume N > K and that the features (ϕk )1≤k≤K σ are linearly independent. Then whenever M ≥ 15 log(8K/δ), with probability at least 1 − δ, the expected excess risk of the CLSR estimate conditionally on the input samples is upper bounded as 2 log(8K/δ) supx ||ϕ(x)||2 1+ K E||ϕ(X)||2 EY (||gL − f ∗ ||2 K ) ≤ 4σ||α+ || E||ϕ(X)||2 P log 4/δ . 2K Proof: Whenever M ≥ 15 log(8K/δ) we deduce from Theorem 1 and (5) that the excess risk of gL is bounded as E(||gL − f ∗ ||2 ) ≤ c max{σ2 , L2 } P +8 8 log(8K/δ) + 2 ||α || M 1 + log K M K E||ϕ(X)||2 + 2 sup ||ϕ(x)||2 x log 4/δ + inf ||f − f ∗ ||2 . P f ∈FN 2K By optimizing on M , we deduce (7). Similarly, using (6) we deduce the following bound on EY (||gL − f ∗ ||2 K ): P σ2 8 M + log(8K/δ)||α+ ||2 K M E||ϕ(X)||2 + 2 sup ||ϕ(x)||2 x log 4/δ + inf ||f − f ∗ ||2 K . P f ∈FN 2K By optimizing on M and noticing that inf f ∈FN ||f − f ∗ ||2 K = 0 whenever N > K and the features P (ϕk )1≤k≤K are linearly independent, we deduce the second result. Remark 1 Note that the second term in the parenthesis of (7) is negligible whenever K Thus we have the expected excess risk log K/δ + inf ||f − f ∗ ||2 . P f ∈FN K E(||gL − f ∗ ||2 ) = O ||α+ || E||ϕ(X)||2 √ P log 1/δ. (8) The choice of M in the previous corollary depends on ||α+ || and E||ϕ(X)|| which are a priori unknown (since f ∗ and PX are unknown). If we set M independently of ||α+ ||, then an additional multiplicative factor of ||α+ || appears in the bound, and if we replace E||ϕ(X)|| by its bound supx ||ϕ(x)|| (which is known) then this latter factor will appear instead of the former in the bound. Complexity of CLSR: The complexity of LSR for computing the regression function in the compressed domain only depends on M and K, and is (see e.g. [4]) Cx(DK , GM , P ) = O(M K 2 ) which √ is of order O(K 5/2 ) when we choose the optimized number of projections M = O( K). However the leading term when using CLSR is the cost for building the Ψ matrix: O(N K 3/2 ). 6 4 4.1 Discussion The factor ||α+ || E||ϕ(X)||2 In light of Corollary 1, the important factor which will determine whether the CLSR provides low generalization error or not is ||α+ || E||ϕ(X)||2 . This factor indicates that a good set of features (for CLSR) should be such that the norm of those features as well as the norm of the parameter α+ of the projection of f ∗ onto the span of those features should be small. A natural question is whether this product can be made small for appropriate choices of features. We now provide two speciﬁc cases for which this is actually the case: (1) when the features are rescaled orthonormal basis functions, and (2) when the features are speciﬁc wavelet functions. In both cases, we relate the bound to an assumption of regularity on the function f ∗ , and show that the dependency w.r.t. N decreases when the regularity increases, and may even vanish. Rescaled Orthonormal Features: Consider a set of orthonormal functions (ηi )i≥1 w.r.t a measure µ, i.e. ηi , ηj µ = δi,j . In addition we assume that the law of the input data is dominated by µ, i.e. PX ≤ Cµ where C is a constant. For instance, this is the case when the set X is compact, µ is the uniform measure and PX has bounded density. def We deﬁne the set of N features as: ϕi = ci ηi , where ci > 0, for i ∈ {1, . . . , N }. Then any f ∈ FN decomposes as f = 2 we have: ||α|| = ||α+ ||2 E||ϕ||2 ≤ C N bi 2 i=1 ( ci ) N bi 2 i=1 ( ci ) and N i=1 N bi i=1 ci ϕi , where N 2 2 i=1 ci X ηi (x)dPX (x) f, ηi ηi = E||ϕ|| = 2 def bi = f, ηi . Thus ≤ C N 2 i=1 ci . Thus N 2 i=1 ci . Now, linear approximation theory (Jackson-type theorems) tells us that assuming a function f ∗ ∈ L2 (µ) is smooth, it may be decomposed onto the span of the N ﬁrst (ηi )i∈{1,...,N } functions with decreasing coefﬁcients |bi | ≤ i−λ for some λ ≥ 0 that depends on the smoothness of f ∗ . For example the class of functions with bounded total variation may be decomposed with Fourier basis (in dimension 1) with coefﬁcients |bi | ≤ ||f ||V /(2πi). Thus here λ = 1. Other classes (such as Sobolev spaces) lead to larger values of λ related to the order of differentiability. √ N By choosing ci = i−λ/2 , we have ||α+ || E||ϕ||2 ≤ C i=1 i−λ . Thus if λ > 1, then this term is bounded by a constant that does not depend on N . If λ = 1 then it is bounded by O(log N ), and if 0 < λ < 1, then it is bounded by O(N 1−λ ). However any orthonormal basis, even rescaled, would not necessarily yield a small ||α+ || E||ϕ||2 term (this is all the more true when the dimension of X is large). The desired property that the coefﬁcients (α+ )i of the decomposition of f ∗ rapidly decrease to 0 indicates that hierarchical bases, such as wavelets, that would decompose the function at different scales, may be interesting. Wavelets: Consider an inﬁnite family of wavelets in [0, 1]: (ϕ0 ) = (ϕ0 ) (indexed by n ≥ 1 or n h,l equivalently by the scale h ≥ 0 and translation 0 ≤ l ≤ 2h − 1) where ϕ0 (x) = 2h/2 ϕ0 (2h x − l) h,l and ϕ0 is the mother wavelet. Then consider N = 2H features (ϕh,l )1≤h≤H deﬁned as the rescaled def wavelets ϕh,l = ch 2−h/2 ϕ0 , where ch > 0 are some coefﬁcients. Assume the mother wavelet h,l is C p (for p ≥ 1), has at least p vanishing moments, and that for all h ≥ 0, supx l ϕ0 (2h x − l)2 ≤ 1. Then the following result (proof in the supplementary material) provides a bound on supx∈X ||ϕ(x)||2 (thus on E||ϕ(X)||2 ) by a constant independent of N : Proposition 2 Assume that f ∗ is (L, γ)-Lipschitz (i.e. for all v ∈ X there exists a polynomial pv of degree γ such that for all u ∈ X , |f (u) − pv (u)| ≤ L|u − v|γ ) with 1/2 < γ ≤ p. Then setting γ 1 ch = 2h(1−2γ)/4 , we have ||α+ || supx ||ϕ(x)|| ≤ L 1−22 |ϕ0 |, which is independent of N . 1/2−γ 0 Notice that the Haar walevets has p = 1 vanishing moment but is not C 1 , thus the Proposition does not apply directly. However direct computations show that if f ∗ is L-Lipschitz (i.e. γ = 1) then L 0 αh,l ≤ L2−3h/2−2 , and thus ||α+ || supx ||ϕ(x)|| ≤ 4(1−2−1/2 ) with ch = 2−h/4 . 7 4.2 Comparison with other methods In the case when the factor ||α+ || E||ϕ(X)||2 does not depend on N (such as in the previous example), the bound (8) on the excess risk of CLSR states that the estimation error (assessed in √ √ terms of FN ) of CLSR is O(log K/ K). It is clear that whenever N > K (which is the case of interest here), this is better than the ordinary LSR in the initial domain, whose estimation error is O(N log K/K). It is difﬁcult to compare this result with LASSO (or the Dantzig selector that has similar properties [5]) for which an important aspect is to design sparse regression functions or to recover a solution assumed to be sparse. From [12, 15, 24] one deduces that under some assumptions, the estimation error of LASSO is of order S log N where S is the sparsity (number of non-zero coefﬁcients) of the K√ best regressor f + in FN . If S < K then LASSO is more interesting than CLSR in terms of excess risk. Otherwise CLSR may be an interesting alternative although this method does not make any assumption about the sparsity of f + and its goal is not to recover a possible sparse f + but only to make good predictions. However, in some sense our method ﬁnds a sparse solution in the fact that the regression function gL lies in a space GM of small dimension M N and can thus be expressed using only M coefﬁcients. Now in terms of numerical complexity, CLSR requires O(N K 3/2 ) operations to build the matrix and compute the regression function, whereas according to [18], the (heuristical) complexity of the LASSO algorithm is O(N K 2 ) in the best cases (assuming that the number of steps required for convergence is O(K), which is not proved theoretically). Thus CLSR seems to be a good and simple competitor to LASSO. 5 Conclusion We considered the case when the number of features N is larger than the number of data K. The result stated in Theorem 1 enables to analyze the excess risk of any linear regression algorithm (LS or its penalized versions) performed in the compressed domain GM versus in the initial space FN . In the compressed domain the estimation error is reduced but an additional (controlled) approximation error (when compared to the best regressor in FN ) comes into the picture. In the case of LS regression, when the term ||α+ || E||ϕ(X)||2 has a mild dependency on N , then by choosing a √ random subspace of dimension M = O( K), CLSR has an estimation error (assessed in terms of √ FN ) bounded by O(log K/ K) and has numerical complexity O(N K 3/2 ). In short, CLSR provides an alternative to usual penalization techniques where one ﬁrst selects a random subspace of lower dimension and then performs an empirical risk minimizer in this subspace. Further work needs to be done to provide additional settings (when the space X is of dimension > 1) for which the term ||α+ || E||ϕ(X)||2 is small. Acknowledgements: The authors wish to thank Laurent Jacques for numerous comments and Alessandro Lazaric and Mohammad Ghavamzadeh for exciting discussions. This work has been supported by French National Research Agency (ANR) through COSINUS program (project EXPLO-RA, ANR-08-COSI-004). References [1] Dimitris Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671–687, June 2003. [2] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast JohnsonLindenstrauss transform. In STOC ’06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 557–563, New York, NY, USA, 2006. ACM. [3] Jean-Yves Audibert and Olivier Catoni. Risk bounds in linear regression through pac-bayesian truncation. Technical Report HAL : hal-00360268, 2009. [4] David Bau III and Lloyd N. Trefethen. Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics, 1997. 8 [5] Peter J. Bickel, Ya’acov Ritov, and Alexandre B. Tsybakov. Simultaneous analysis of Lasso and Dantzig selector. To appear in Annals of Statistics, 2008. [6] Avrim Blum. Random projection, margins, kernels, and feature-selection. Subspace, Latent Structure and Feature Selection, pages 52–68, 2006. [7] Robert Calderbank, Sina Jafarpour, and Robert Schapire. Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain. Technical Report, 2009. [8] Emmanuel Candes and Terence Tao. The Dantzig selector: Statistical estimation when p is much larger than n. Annals of Statistics, 35:2313, 2007. [9] Emmanuel J. Candes and Justin K. Romberg. Signal recovery from random projections. volume 5674, pages 76–86. SPIE, 2005. [10] S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientiﬁc Computing, 20:33–61, 1998. [11] Mark A. Davenport, Michael B. Wakin, and Richard G. Baraniuk. Detection and estimation with compressive measurements. Technical Report TREE 0610, Department of Electrical and Computer Engineering, Rice University, 2006. [12] E. Greenshtein and Y. Ritov. Persistency in high dimensional linear predictor-selection and the virtue of over-parametrization. Bernoulli, 10:971–988, 2004. [13] L. Gy¨ rﬁ, M. Kohler, A. Krzy˙ ak, and H. Walk. A distribution-free theory of nonparametric o z regression. Springer-Verlag, 2002. [14] Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Leon Bottou, editors, Neural Information Processing Systems, pages 793– 800. MIT Press, 2008. [15] Yuval Nardi and Alessandro Rinaldo. On the asymptotic properties of the group Lasso estimator for linear models. Electron. J. Statist., 2:605–633, 2008. [16] D. Pollard. Convergence of Stochastic Processes. Springer Verlag, New York, 1984. [17] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Neural Information Processing Systems, 2007. [18] Saharon Rosset and Ji Zhu. Piecewise linear regularized solution paths. Annals of Statistics, 35:1012, 2007. [19] Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society, Series B, 58:267–288, 1994. [20] A. N. Tikhonov. Solution of incorrectly formulated problems and the regularization method. Soviet Math Dokl 4, pages 1035–1038, 1963. [21] Yaakov Tsaig and David L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52:1289–1306, 2006. [22] Vladimir N. Vapnik. The nature of statistical learning theory. Springer-Verlag New York, Inc., New York, NY, USA, 1995. [23] Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2:527–550, 2002. [24] Tong Zhang. Some sharp performance bounds for least squares regression with L1 regularization. To appear in Annals of Statistics, 2009. [25] Shuheng Zhou, John D. Lafferty, and Larry A. Wasserman. Compressed regression. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, Neural Information Processing Systems. MIT Press, 2007. 9

3 0.12991114 228 nips-2009-Speeding up Magnetic Resonance Image Acquisition by Bayesian Multi-Slice Adaptive Compressed Sensing

Author: Matthias Seeger

Abstract: We show how to sequentially optimize magnetic resonance imaging measurement designs over stacks of neighbouring image slices, by performing convex variational inference on a large scale non-Gaussian linear dynamical system, tracking dominating directions of posterior covariance without imposing any factorization constraints. Our approach can be scaled up to high-resolution images by reductions to numerical mathematics primitives and parallelization on several levels. In a ﬁrst study, designs are found that improve signiﬁcantly on others chosen independently for each slice or drawn at random. 1

4 0.12656125 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

Author: John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, Yi Ma

Abstract: Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized “robust principal component analysis” problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the corrupted entries E are unknown and the errors can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efﬁciently and exactly recovered from most error sign-and-support patterns by solving a simple convex program, for which we give a fast and provably convergent algorithm. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the ﬁrst proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision. 1

5 0.12635946 185 nips-2009-Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis

Author: Sundeep Rangan, Alyson K. Fletcher

Abstract: A well-known analysis of Tropp and Gilbert shows that orthogonal matching pursuit (OMP) can recover a k-sparse n-dimensional real vector from m = 4k log(n) noise-free linear measurements obtained through a random Gaussian measurement matrix with a probability that approaches one as n → ∞. This work strengthens this result by showing that a lower number of measurements, m = 2k log(n − k), is in fact sufﬁcient for asymptotic recovery. More generally, when the sparsity level satisﬁes kmin ≤ k ≤ kmax but is unknown, m = 2kmax log(n − kmin ) measurements is sufﬁcient. Furthermore, this number of measurements is also sufﬁcient for detection of the sparsity pattern (support) of the vector with measurement errors provided the signal-to-noise ratio (SNR) scales to inﬁnity. The scaling m = 2k log(n − k) exactly matches the number of measurements required by the more complex lasso method for signal recovery in a similar SNR scaling.

6 0.12070522 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

7 0.11692531 245 nips-2009-Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation

8 0.11357724 200 nips-2009-Reconstruction of Sparse Circuits Using Multi-neuronal Excitation (RESCUME)

9 0.10796107 104 nips-2009-Group Sparse Coding

10 0.10026866 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

11 0.091536321 122 nips-2009-Label Selection on Graphs

12 0.091493994 71 nips-2009-Distribution-Calibrated Hierarchical Classification

13 0.090245888 260 nips-2009-Zero-shot Learning with Semantic Output Codes

14 0.088966481 57 nips-2009-Conditional Random Fields with High-Order Features for Sequence Labeling

15 0.08884839 108 nips-2009-Heterogeneous multitask learning with joint sparsity constraints

16 0.087748848 127 nips-2009-Learning Label Embeddings for Nearest-Neighbor Multi-class Classification with an Application to Speech Recognition

17 0.086095616 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models

18 0.08509545 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

19 0.084626064 222 nips-2009-Sparse Estimation Using General Likelihoods and Non-Factorial Priors

20 0.083263546 192 nips-2009-Posterior vs Parameter Sparsity in Latent Variable Models

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.261), (1, 0.048), (2, -0.028), (3, 0.062), (4, -0.01), (5, 0.018), (6, 0.001), (7, -0.117), (8, 0.153), (9, 0.178), (10, -0.041), (11, -0.008), (12, -0.101), (13, 0.001), (14, 0.007), (15, 0.129), (16, 0.05), (17, 0.044), (18, 0.035), (19, -0.019), (20, 0.036), (21, 0.052), (22, 0.068), (23, 0.163), (24, 0.123), (25, 0.068), (26, -0.082), (27, -0.086), (28, -0.041), (29, -0.082), (30, -0.047), (31, -0.013), (32, -0.047), (33, 0.161), (34, 0.007), (35, 0.019), (36, 0.093), (37, 0.062), (38, 0.001), (39, -0.025), (40, -0.064), (41, -0.045), (42, 0.192), (43, -0.027), (44, -0.05), (45, -0.04), (46, 0.112), (47, -0.037), (48, -0.043), (49, 0.001)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95741761 157 nips-2009-Multi-Label Prediction via Compressed Sensing

Author: John Langford, Tong Zhang, Daniel J. Hsu, Sham M. Kakade

2 0.69600123 185 nips-2009-Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis

Author: Sundeep Rangan, Alyson K. Fletcher

3 0.60813046 55 nips-2009-Compressed Least-Squares Regression

Author: Odalric Maillard, Rémi Munos

4 0.60467929 228 nips-2009-Speeding up Magnetic Resonance Image Acquisition by Bayesian Multi-Slice Adaptive Compressed Sensing

Author: Matthias Seeger

5 0.6041134 127 nips-2009-Learning Label Embeddings for Nearest-Neighbor Multi-class Classification with an Application to Speech Recognition

Author: Natasha Singh-miller, Michael Collins

Abstract: We consider the problem of using nearest neighbor methods to provide a conditional probability estimate, P (y|a), when the number of labels y is large and the labels share some underlying structure. We propose a method for learning label embeddings (similar to error-correcting output codes (ECOCs)) to model the similarity between labels within a nearest neighbor framework. The learned ECOCs and nearest neighbor information are used to provide conditional probability estimates. We apply these estimates to the problem of acoustic modeling for speech recognition. We demonstrate signiﬁcant improvements in terms of word error rate (WER) on a lecture recognition task over a state-of-the-art baseline GMM model. 1

6 0.57285732 222 nips-2009-Sparse Estimation Using General Likelihoods and Non-Factorial Priors

7 0.56076682 138 nips-2009-Learning with Compressible Priors

8 0.55862981 108 nips-2009-Heterogeneous multitask learning with joint sparsity constraints

9 0.55506295 258 nips-2009-Whose Vote Should Count More: Optimal Integration of Labels from Labelers of Unknown Expertise

10 0.53773105 36 nips-2009-Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing

11 0.53382522 71 nips-2009-Distribution-Calibrated Hierarchical Classification

12 0.52031058 245 nips-2009-Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation

13 0.49878928 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

14 0.4650895 49 nips-2009-Breaking Boundaries Between Induction Time and Diagnosis Time Active Information Acquisition

15 0.46231237 93 nips-2009-Fast Image Deconvolution using Hyper-Laplacian Priors

16 0.45666131 56 nips-2009-Conditional Neural Fields

17 0.44762668 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

18 0.44275853 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

19 0.438777 122 nips-2009-Label Selection on Graphs

20 0.43193474 7 nips-2009-A Data-Driven Approach to Modeling Choice

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(23, 0.228), (24, 0.08), (25, 0.099), (35, 0.05), (36, 0.123), (39, 0.049), (58, 0.089), (61, 0.012), (71, 0.058), (81, 0.039), (86, 0.08), (91, 0.019)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.84568477 157 nips-2009-Multi-Label Prediction via Compressed Sensing

Author: John Langford, Tong Zhang, Daniel J. Hsu, Sham M. Kakade

2 0.75113451 174 nips-2009-Nonparametric Latent Feature Models for Link Prediction

Author: Kurt Miller, Michael I. Jordan, Thomas L. Griffiths

Abstract: As the availability and importance of relational data—such as the friendships summarized on a social networking website—increases, it becomes increasingly important to have good models for such data. The kinds of latent structure that have been considered for use in predicting links in such networks have been relatively limited. In particular, the machine learning community has focused on latent class models, adapting Bayesian nonparametric methods to jointly infer how many latent classes there are while learning which entities belong to each class. We pursue a similar approach with a richer kind of latent variable—latent features—using a Bayesian nonparametric approach to simultaneously infer the number of features at the same time we learn which entities have each feature. Our model combines these inferred features with known covariates in order to perform link prediction. We demonstrate that the greater expressiveness of this approach allows us to improve performance on three datasets. 1

3 0.70227963 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

Author: Kai Yu, Tong Zhang, Yihong Gong

Abstract: This paper introduces a new method for semi-supervised learning on high dimensional nonlinear manifolds, which includes a phase of unsupervised basis learning and a phase of supervised function learning. The learned bases provide a set of anchor points to form a local coordinate system, such that each data point x on the manifold can be locally approximated by a linear combination of its nearby anchor points, and the linear weights become its local coordinate coding. We show that a high dimensional nonlinear function can be approximated by a global linear function with respect to this coding scheme, and the approximation quality is ensured by the locality of such coding. The method turns a difﬁcult nonlinear learning problem into a simple global linear learning problem, which overcomes some drawbacks of traditional local learning methods. 1

4 0.6978448 97 nips-2009-Free energy score space

Author: Alessandro Perina, Marco Cristani, Umberto Castellani, Vittorio Murino, Nebojsa Jojic

Abstract: A score function induced by a generative model of the data can provide a feature vector of a ﬁxed dimension for each data sample. Data samples themselves may be of differing lengths (e.g., speech segments, or other sequence data), but as a score function is based on the properties of the data generation process, it produces a ﬁxed-length vector in a highly informative space, typically referred to as a “score space”. Discriminative classiﬁers have been shown to achieve higher performance in appropriately chosen score spaces than is achievable by either the corresponding generative likelihood-based classiﬁers, or the discriminative classiﬁers using standard feature extractors. In this paper, we present a novel score space that exploits the free energy associated with a generative model. The resulting free energy score space (FESS) takes into account latent structure of the data at various levels, and can be trivially shown to lead to classiﬁcation performance that at least matches the performance of the free energy classiﬁer based on the same generative model, and the same factorization of the posterior. We also show that in several typical vision and computational biology applications the classiﬁers optimized in FESS outperform the corresponding pure generative approaches, as well as a number of previous approaches to combining discriminating and generative models.

5 0.69485492 129 nips-2009-Learning a Small Mixture of Trees

Author: M. P. Kumar, Daphne Koller

Abstract: The problem of approximating a given probability distribution using a simpler distribution plays an important role in several areas of machine learning, for example variational inference and classiﬁcation. Within this context, we consider the task of learning a mixture of tree distributions. Although mixtures of trees can be learned by minimizing the KL-divergence using an EM algorithm, its success depends heavily on the initialization. We propose an efﬁcient strategy for obtaining a good initial set of trees that attempts to cover the entire observed distribution by minimizing the α-divergence with α = ∞. We formulate the problem using the fractional covering framework and present a convergent sequential algorithm that only relies on solving a convex program at each iteration. Compared to previous methods, our approach results in a signiﬁcantly smaller mixture of trees that provides similar or better accuracies. We demonstrate the usefulness of our approach by learning pictorial structures for face recognition.

6 0.69365931 122 nips-2009-Label Selection on Graphs

7 0.69129562 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

8 0.69046229 132 nips-2009-Learning in Markov Random Fields using Tempered Transitions

9 0.69004214 225 nips-2009-Sparsistent Learning of Varying-coefficient Models with Structural Changes

10 0.68949932 71 nips-2009-Distribution-Calibrated Hierarchical Classification

11 0.68898213 41 nips-2009-Bayesian Source Localization with the Multivariate Laplace Prior

12 0.68725395 59 nips-2009-Construction of Nonparametric Bayesian Models from Parametric Bayes Equations

13 0.68657857 18 nips-2009-A Stochastic approximation method for inference in probabilistic graphical models

14 0.68651092 260 nips-2009-Zero-shot Learning with Semantic Output Codes

15 0.68584841 254 nips-2009-Variational Gaussian-process factor analysis for modeling spatio-temporal data

16 0.68534476 1 nips-2009-$L 1$-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry

17 0.68481344 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA

18 0.68367833 49 nips-2009-Breaking Boundaries Between Induction Time and Diagnosis Time Active Information Acquisition

19 0.68323141 37 nips-2009-Asymptotically Optimal Regularization in Smooth Parametric Models

20 0.68304276 72 nips-2009-Distribution Matching for Transduction