nips nips2010 nips2010-211 knowledge-graph by maker-knowledge-mining

211 nips-2010-Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression

Source: pdf

Author: Ling Huang, Jinzhu Jia, Bin Yu, Byung-gon Chun, Petros Maniatis, Mayur Naik

Abstract: Predicting the execution time of computer programs is an important but challenging problem in the community of computer systems. Existing methods require experts to perform detailed analysis of program code in order to construct predictors or select important features. We recently developed a new system to automatically extract a large number of features from program execution on sample inputs, on which prediction models can be constructed without expert knowledge. In this paper we study the construction of predictive models for this problem. We propose the SPORE (Sparse POlynomial REgression) methodology to build accurate prediction models of program performance using feature data collected from program execution on sample inputs. Our two SPORE algorithms are able to build relationships between responses (e.g., the execution time of a computer program) and features, and select a few from hundreds of the retrieved features to construct an explicitly sparse and non-linear model to predict the response variable. The compact and explicitly polynomial form of the estimated model could reveal important insights into the computer program (e.g., features and their non-linear combinations that dominate the execution time), enabling a better understanding of the program’s behavior. Our evaluation on three widely used computer programs shows that SPORE methods can give accurate prediction with relative error less than 7% by using a moderate number of training data samples. In addition, we compare SPORE algorithms to state-of-the-art sparse regression algorithms, and show that SPORE methods, motivated by real applications, outperform the other methods in terms of both interpretability and prediction accuracy.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract Predicting the execution time of computer programs is an important but challenging problem in the community of computer systems. [sent-13, score-0.607]

2 Existing methods require experts to perform detailed analysis of program code in order to construct predictors or select important features. [sent-14, score-0.437]

3 We recently developed a new system to automatically extract a large number of features from program execution on sample inputs, on which prediction models can be constructed without expert knowledge. [sent-15, score-1.067]

4 We propose the SPORE (Sparse POlynomial REgression) methodology to build accurate prediction models of program performance using feature data collected from program execution on sample inputs. [sent-17, score-1.288]

5 , the execution time of a computer program) and features, and select a few from hundreds of the retrieved features to construct an explicitly sparse and non-linear model to predict the response variable. [sent-20, score-0.823]

6 The compact and explicitly polynomial form of the estimated model could reveal important insights into the computer program (e. [sent-21, score-0.542]

7 , features and their non-linear combinations that dominate the execution time), enabling a better understanding of the program’s behavior. [sent-23, score-0.51]

8 Our evaluation on three widely used computer programs shows that SPORE methods can give accurate prediction with relative error less than 7% by using a moderate number of training data samples. [sent-24, score-0.305]

9 In addition, we compare SPORE algorithms to state-of-the-art sparse regression algorithms, and show that SPORE methods, motivated by real applications, outperform the other methods in terms of both interpretability and prediction accuracy. [sent-25, score-0.338]

10 At the heart of such systems are management components that decide how to schedule the execution of different programs over time (e. [sent-29, score-0.545]

11 , to ensure high system utilization or efﬁcient energy use [11, 15]), how to allocate to each program resources such as memory, storage and networking (e. [sent-31, score-0.303]

12 These management components typically must make guesses about how a program will perform under given hypothetical inputs, so as to decide how best to plan for the future. [sent-36, score-0.278]

13 For example, consider a simple scenario in a data center with two computers, fast computer A and slow computer B, and a program waiting to run on a large ﬁle f stored in computer B. [sent-37, score-0.371]

14 A scheduler is often faced 1 with the decision of whether to run the program at B, potentially taking longer to execute, but avoiding any transmission costs for the ﬁle; or moving the ﬁle from B to A but potentially executing the program at A much faster. [sent-38, score-0.591]

15 If the scheduler can predict accurately how long the program would take to execute on input f at computer A or B, he/she can make an optimal decision, returning results faster, possibly minimizing energy use, etc. [sent-39, score-0.492]

16 Existing approaches either create analytical models for the programs based on simplistic assumptions [12], or treat the program as a black box and create a mapping function between certain properties of input data (e. [sent-41, score-0.397]

17 The success of such methods is highly dependent on human experts who are able to select important predictors before a statistical modeling step can take place. [sent-44, score-0.193]

18 Even when an expert is available, program performance is often dependent not on externally visible features such as command-line parameters and input ﬁles, but on the internal semantics of the program (e. [sent-48, score-0.774]

19 To address this problem (lack of expert and inherent semantics), we recently developed a new system [7] to automatically extract a large number of features from the intermediate execution steps of a program (e. [sent-51, score-0.946]

20 , internal variables, loops, and branches) on sample inputs; then prediction models can be built from those features without the need for a human expert. [sent-53, score-0.238]

21 In this paper, we propose two Sparse POlynomial REgression (SPORE) algorithms that use the automatically extracted features to predict a computer program’s performance. [sent-54, score-0.295]

22 Our algorithms are in fact new general methods motivated by the computer performance prediction problem. [sent-56, score-0.186]

23 , the execution time of a computer program given an input) and the generated features, and select a few from hundreds of features to construct an explicit polynomial form to predict the response. [sent-59, score-1.2]

24 The compact and explicit polynomial form reveals important insights in the program semantics (e. [sent-60, score-0.552]

25 , the internal program loop that affects program execution time the most). [sent-62, score-1.008]

26 We evaluate our algorithms experimentally on three popular computer programs from web search and image processing. [sent-64, score-0.215]

27 In prior attempts to predict program execution time, Gupta et al. [sent-67, score-0.738]

28 [13] use a variant of decision trees to predict execution time ranges for database queries. [sent-68, score-0.493]

29 [11] use KCCA to predict time and resource consumption for database queries using statistics on query texts and execution plans. [sent-70, score-0.56]

30 To measure the empirical computational complexity of a program, Trendprof [12] constructs linear or power-law models that predict program execution counts. [sent-71, score-0.738]

31 The drawbacks of such approaches include their need for expert knowledge about the program to identify good features, or their requirement for simple input-size to execution time correlations. [sent-72, score-0.79]

32 Seshia and Rakhlin [22, 23] propose a game-theoretic estimator of quantitative program properties, such as worst-case execution time, for embedded systems. [sent-73, score-0.671]

33 These properties depend heavily on the target hardware environment in which the program is executed. [sent-74, score-0.362]

34 As a result, they formulate the problem as a game between their algorithm (player) and the program’s environment (adversary), where the player seeks to accurately predict the property of interest while the adversary sets environment states and parameters. [sent-76, score-0.268]

35 Since expert resource is limited and costly, it is desirable to automatically extract features from program codes. [sent-77, score-0.569]

36 Then machine learning techniques can be used to select the most important features to build a model. [sent-78, score-0.216]

37 The drawback of applying the SpAM method in our execution time prediction problem is that SpAM outputs an additive model and cannot use the interaction information between features. [sent-83, score-0.601]

38 But it is well-known that features of computer programs interact to determine the execution time [12]. [sent-84, score-0.693]

39 However, the resulting non-parametric models are not easy to interpret and hence are not desirable for our execution time prediction problem. [sent-86, score-0.547]

40 Our goal is to predict how a given program will perform (e. [sent-91, score-0.345]

41 Second, the proﬁling step executes the instrumented program with sample input data to collect values for all created program features and the program’s execution times. [sent-98, score-1.1]

42 Third, the slicing step analyzes each automatically identiﬁed feature to determine the smallest subset of the actual program that can compute the value of that feature, i. [sent-100, score-0.533]

43 Finally, the modeling step uses the feature values collected during proﬁling along with the feature costs computed during slicing to build a predictive model on a small subset of generated features. [sent-104, score-0.341]

44 To obtain a model consisting of low-cost features, we iterate over the modeling and slicing steps, evaluating the cost of selected features and rejecting expensive ones, until only low-cost features are selected to construct the prediction model. [sent-105, score-0.485]

45 At runtime, given a new input, the selected features are computed using the corresponding slices, and the model is used to predict execution time from the feature values. [sent-106, score-0.707]

46 The above description is minimal by necessity due to space constraints, and omits details on the rationale, such as why we chose the kinds of features we chose or how program slicing works. [sent-107, score-0.455]

47 We therefore assume that execution times observed during training will be consistent with system behavior on-line. [sent-110, score-0.418]

48 Our approach can adapt to modest change in execution environment by retraining on different environments. [sent-111, score-0.453]

49 In our future research, we plan to incorporate candidate features of both hardware (e. [sent-112, score-0.183]

50 3 Sparse Polynomial Regression Model Our basic premise for predictive program analysis is that a small but relevant set of features may explain the execution time well. [sent-117, score-0.851]

51 In other words, we seek a compact model—an explicit form function of a small number of features—that accurately estimates the execution time of the program. [sent-118, score-0.485]

52 3 To make the problem tractable, we constrain our models to the multivariate polynomial family, for at least three reasons. [sent-119, score-0.206]

53 First, a “good program” is usually expected to have polynomial execution time in some (combination of) features. [sent-120, score-0.632]

54 Second, a polynomial model up to certain degree can approximate well many nonlinear models (due to Taylor expansion). [sent-121, score-0.255]

55 Finally, a compact polynomial model can provide an easy-to-understand explanation of what determines the execution time of a program, providing program developers with intuitive feedback and a solid basis for analysis. [sent-122, score-0.937]

56 For each computer program, our feature instrumentation procedure outputs a data set with n samples as tuples of {yi , xi }n , where yi ∈ R denotes the ith observation of execution time, and xi denotes i=1 the ith observation of the vector of p features. [sent-123, score-0.539]

57 (1) 2 β 2 j LASSO effectively enforces many βj ’s to be 0, and selects a small subset of features (indexed by non-zero βj ’s) to build the model, which is usually sparse and has better prediction accuracy than models created by ordinary least square regression [14] when p is large. [sent-134, score-0.423]

58 , using polynomial basis functions up to degree d of all p features). [sent-145, score-0.255]

59 We give two alternatives to ﬁt the sparse polynomial regression model next. [sent-147, score-0.368]

60 2 SPORE Methodology and Two Algorithms Our methodology captures non-linear effects of features—as well as non-linear interactions among features—by using polynomial basis functions over those features (we use terms to denote the polynomial basis functions subsequently). [sent-149, score-0.618]

61 xk }, k ≤ p to all the terms in the expansion of the degree-d polynomial (1 + x1 + . [sent-153, score-0.291]

62 + xk )d , and use the terms to construct a multivariate polynomial function f (x, β) for the regression. [sent-156, score-0.232]

63 We deﬁne expan(X, d) as the mapping from the original data matrix X to a new matrix with the polynomial expansion terms up to degree d as the columns. [sent-157, score-0.34]

64 1 2 Complete expansion on all p features is not necessary, because many of them have little contribution to the execution time. [sent-159, score-0.569]

65 Motivated by this execution time application, we propose a general methodology called SPORE which is a sparse polynomial regression technique. [sent-160, score-0.828]

66 1 SPORE-LASSO: A Two-Step Method For a sparse polynomial model with only a few features, if we can preselect a small number of features, applying the LASSO on the polynomial expansion of those preselected features will still be efﬁcient, because we do not have too many polynomial terms. [sent-164, score-0.861]

67 Here is the idea: Step 1: Use the linear LASSO algorithm to select a small number of features and ﬁlter out (often many) features that hardly have contributions to the execution time. [sent-165, score-0.674]

68 Step 2: Use the adaptive-LASSO method on the expanded polynomial terms of the selected features (from Step 1) to construct the sparse polynomial model. [sent-166, score-0.708]

69 Adaptive-LASSO is used in Step 2 because of the collinearity of the expanded polynomial features. [sent-167, score-0.257]

70 Algorithm 1 SPORE-LASSO Input: response Y , feature data X, maximum degree d, λ1 , λ2 ˆ Output: Feature index S, term index St , weights β for d-degree polynomial basis. [sent-170, score-0.357]

71 , xp ], we ﬁrst get the selected feature vector X(S), then obtain the polynomial terms Xnew = expan(X(S), d), and ﬁnally we compute ˆ ˆ the prediction: Y = Xnew × β. [sent-176, score-0.354]

72 The AIC is deﬁned as n log( Y − Y 2 )+ 2 ˆ is the ﬁtted Y and s is the number of polynomial terms selected in the model. [sent-180, score-0.267]

73 On the solution path, for each ﬁxed λ1 , we compute a solution path with varied λ2 for Step 5 of Algorithm 1 to select the polynomial terms. [sent-182, score-0.297]

74 Under the following conditions, we show that Step 1 of SPORE-LASSO, the linear LASSO, selects the relevant features even if the response Y depends on predictors X(S) nonlinearly: 5 1. [sent-202, score-0.237]

75 2 Adaptive Forward-Backward: SPORE-FoBa Using all of the polynomial expansions of a feature subset is not ﬂexible. [sent-222, score-0.268]

76 , Xp , the maximum degree d Output: polynomial terms and the weights 1: Let T = ∅ 2: while true do 3: for j = 1, . [sent-235, score-0.281]

77 , p do 4: Let C be the candidate set that contains non-linear and interaction terms from Equation (3) 5: Use Linear FoBa to select terms from C to form the new active set T . [sent-238, score-0.179]

78 We collected a data set with n = 3840 samples, each of which consists of an execution time and a total of p = 126 automatically generated features. [sent-280, score-0.513]

79 For the Find Maxima program within the ImageJ framework, we collected n = 3045 samples (from an equal number of distinct, diverse images obtained from three vision corpora [1, 2, 5]), and a total of p = 182 features. [sent-285, score-0.345]

80 Finally, from the Segmentation program within the same ImageJ framework on the same image set, we collected again n = 3045 samples, and a total of p = 816 features for each. [sent-290, score-0.467]

81 In all the experiments, we ﬁx degree d = 3 for polynomial expansion, and normalized each column of feature data into range [0, 1]. [sent-295, score-0.317]

82 The accuracy measure we use is the ˆ −y 1 relative prediction error deﬁned as nt | yiyi i |, where nt is the size of the test data set, and yi ’s ˆ and yi ’s are the predicted and actual responses of test data, respectively. [sent-298, score-0.203]

83 We randomly split every data set into a training set and a test set for a given training-set fraction, train the algorithms and measure their prediction error on the test data. [sent-299, score-0.189]

84 Speciﬁcally, both of our algorithms can achieve less than 7% prediction error on both Lucene and Find Maxima datasets; on the segmentation dataset, SPORE-FoBa achieves less than 8% prediction error, and SPORE-LASSO achieves around 10% prediction error on average. [sent-302, score-0.491]

85 Since FoBa and SPORE-FoBa naturally produce a path by adding or deleting features (or terms), we record the prediction error at each step. [sent-307, score-0.348]

86 When two steps have the same sparsity level, we report the smallest prediction error. [sent-308, score-0.193]

87 We believe this is because execution time of a computer program often depends on non-linear combinations of different features, which is usually not well-handled by either linear methods or the additive non-parametric methods. [sent-312, score-0.789]

88 Instead, both of our algorithms can select 2-3 high-quality features and build models with non-linear combinations of them to predict execution time with high accuracy. [sent-313, score-0.743]

89 1 2 3 4 Sparsity 5 (b) Find Maxima 6 7 0 1 2 3 4 Sparsity 5 6 7 (c) Segmentation Figure 2: Performance of the algorithms: relative prediction error versus sparsity level. [sent-329, score-0.198]

90 We see that with different training set fractions and with different sparsity conﬁgurations, SPORE-FoBa can always select two high-quality features from hundreds of automatically generated ones. [sent-333, score-0.281]

91 By consulting with experts of the Find Maxima program, we ﬁnd that the two selected features correspond to the width (w) and height (h) of the region of interest in the image, which may in practice differ from the actual image width and height. [sent-334, score-0.215]

92 Those are indeed the most important factors for determining the execution time of the particular algorithm used. [sent-335, score-0.426]

93 , wh, wh2 ) to predict the execution time accurately (around 5. [sent-344, score-0.525]

94 On the contrary, as observed in our experiments, neither the linear nor the additive sparse methods handle well such nonlinear terms, and result in inferior prediction performance. [sent-347, score-0.242]

95 5 Conclusion In this paper, we proposed the SPORE (Sparse POlynomial REgression) methodology to build the relationship between execution time of computer programs and features of the programs. [sent-349, score-0.808]

96 We introduced two algorithms to learn a SPORE model, and showed that both algorithms can predict execution time with more than 93% accuracy for the applications we tested. [sent-350, score-0.561]

97 For the three test cases, these results present a signiﬁcant improvement (a 40% or more reduction in prediction error) over other sparse modeling techniques in the literature when applied to this problem. [sent-351, score-0.188]

98 Moreover, the SPORE methodology is a general methodology that can be used to model computer program performance metrics other than execution time and solve problems from other areas of science and engineering. [sent-353, score-0.861]

99 Mantis: Predicting system performance through program analysis and modeling. [sent-396, score-0.303]

100 PQR: Predicting query execution times for autonomous workload management. [sent-439, score-0.393]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('spore', 0.509), ('execution', 0.393), ('foba', 0.3), ('program', 0.278), ('lasso', 0.216), ('polynomial', 0.206), ('xnew', 0.14), ('xs', 0.125), ('prediction', 0.121), ('programs', 0.119), ('features', 0.117), ('lucene', 0.1), ('predictors', 0.08), ('afr', 0.08), ('expan', 0.08), ('maxima', 0.077), ('find', 0.07), ('predict', 0.067), ('sparse', 0.067), ('regression', 0.066), ('methodology', 0.063), ('feature', 0.062), ('expert', 0.06), ('slicing', 0.06), ('imagej', 0.06), ('seshia', 0.06), ('environment', 0.06), ('expansion', 0.059), ('additive', 0.054), ('spam', 0.053), ('build', 0.052), ('expanded', 0.051), ('labs', 0.051), ('execute', 0.049), ('degree', 0.049), ('rss', 0.048), ('select', 0.047), ('berkeley', 0.046), ('automatically', 0.046), ('ling', 0.045), ('path', 0.044), ('sparsity', 0.043), ('aic', 0.043), ('candidate', 0.042), ('intel', 0.042), ('semantics', 0.041), ('resource', 0.041), ('collected', 0.041), ('response', 0.04), ('glmnet', 0.04), ('maniatis', 0.04), ('wj', 0.039), ('active', 0.038), ('residuals', 0.037), ('predicting', 0.036), ('selected', 0.035), ('sought', 0.035), ('chun', 0.035), ('scheduler', 0.035), ('step', 0.034), ('algorithms', 0.034), ('error', 0.034), ('time', 0.033), ('deleting', 0.032), ('accurately', 0.032), ('experts', 0.032), ('les', 0.031), ('image', 0.031), ('computer', 0.031), ('xj', 0.03), ('executed', 0.03), ('predictive', 0.03), ('alternatives', 0.029), ('smallest', 0.029), ('ganapathi', 0.029), ('instrumentation', 0.029), ('hundreds', 0.028), ('le', 0.028), ('compact', 0.027), ('extract', 0.027), ('terms', 0.026), ('segmentation', 0.026), ('drawbacks', 0.026), ('corpora', 0.026), ('loop', 0.026), ('queries', 0.026), ('etc', 0.025), ('delete', 0.025), ('xp', 0.025), ('adversary', 0.025), ('system', 0.025), ('indexed', 0.025), ('player', 0.024), ('dl', 0.024), ('yi', 0.024), ('percentage', 0.024), ('inputs', 0.024), ('hardware', 0.024), ('interpretability', 0.024), ('analyzes', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 211 nips-2010-Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression

Author: Ling Huang, Jinzhu Jia, Bin Yu, Byung-gon Chun, Petros Maniatis, Mayur Naik

2 0.12151306 260 nips-2010-Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework

Author: Hongbo Zhou, Qiang Cheng

Abstract: Regularization technique has become a principled tool for statistics and machine learning research and practice. However, in most situations, these regularization terms are not well interpreted, especially on how they are related to the loss function and data. In this paper, we propose a robust minimax framework to interpret the relationship between data and regularization terms for a large class of loss functions. We show that various regularization terms are essentially corresponding to different distortions to the original data matrix. This minimax framework includes ridge regression, lasso, elastic net, fused lasso, group lasso, local coordinate coding, multiple kernel learning, etc., as special cases. Within this minimax framework, we further give mathematically exact deﬁnition for a novel representation called sparse grouping representation (SGR), and prove a set of sufﬁcient conditions for generating such group level sparsity. Under these sufﬁcient conditions, a large set of consistent regularization terms can be designed. This SGR is essentially different from group lasso in the way of using class or group information, and it outperforms group lasso when there appears group label noise. We also provide some generalization bounds in a classiﬁcation setting. 1

3 0.10687352 5 nips-2010-A Dirty Model for Multi-task Learning

Author: Ali Jalali, Sujay Sanghavi, Chao Ruan, Pradeep K. Ravikumar

Abstract: We consider multi-task learning in the setting of multiple linear regression, and where some relevant features could be shared across the tasks. Recent research has studied the use of ℓ1 /ℓq norm block-regularizations with q > 1 for such blocksparse structured problems, establishing strong guarantees on recovery even under high-dimensional scaling where the number of features scale with the number of observations. However, these papers also caution that the performance of such block-regularized methods are very dependent on the extent to which the features are shared across tasks. Indeed they show [8] that if the extent of overlap is less than a threshold, or even if parameter values in the shared features are highly uneven, then block ℓ1 /ℓq regularization could actually perform worse than simple separate elementwise ℓ1 regularization. Since these caveats depend on the unknown true parameters, we might not know when and which method to apply. Even otherwise, we are far away from a realistic multi-task setting: not only do the set of relevant features have to be exactly the same across tasks, but their values have to as well. Here, we ask the question: can we leverage parameter overlap when it exists, but not pay a penalty when it does not ? Indeed, this falls under a more general question of whether we can model such dirty data which may not fall into a single neat structural bracket (all block-sparse, or all low-rank and so on). With the explosion of such dirty high-dimensional data in modern settings, it is vital to develop tools – dirty models – to perform biased statistical estimation tailored to such data. Here, we take a ﬁrst step, focusing on developing a dirty model for the multiple regression problem. Our method uses a very simple idea: we estimate a superposition of two sets of parameters and regularize them differently. We show both theoretically and empirically, our method strictly and noticeably outperforms both ℓ1 or ℓ1 /ℓq methods, under high-dimensional scaling and over the entire range of possible overlaps (except at boundary cases, where we match the best method). 1 Introduction: Motivation and Setup High-dimensional scaling. In ﬁelds across science and engineering, we are increasingly faced with problems where the number of variables or features p is larger than the number of observations n. Under such high-dimensional scaling, for any hope of statistically consistent estimation, it becomes vital to leverage any potential structure in the problem such as sparsity (e.g. in compressed sensing [3] and LASSO [14]), low-rank structure [13, 9], or sparse graphical model structure [12]. It is in such high-dimensional contexts in particular that multi-task learning [4] could be most useful. Here, 1 multiple tasks share some common structure such as sparsity, and estimating these tasks jointly by leveraging this common structure could be more statistically efﬁcient. Block-sparse Multiple Regression. A common multiple task learning setting, and which is the focus of this paper, is that of multiple regression, where we have r > 1 response variables, and a common set of p features or covariates. The r tasks could share certain aspects of their underlying distributions, such as common variance, but the setting we focus on in this paper is where the response variables have simultaneously sparse structure: the index set of relevant features for each task is sparse; and there is a large overlap of these relevant features across the different regression problems. Such “simultaneous sparsity” arises in a variety of contexts [15]; indeed, most applications of sparse signal recovery in contexts ranging from graphical model learning, kernel learning, and function estimation have natural extensions to the simultaneous-sparse setting [12, 2, 11]. It is useful to represent the multiple regression parameters via a matrix, where each column corresponds to a task, and each row to a feature. Having simultaneous sparse structure then corresponds to the matrix being largely “block-sparse” – where each row is either all zero or mostly non-zero, and the number of non-zero rows is small. A lot of recent research in this setting has focused on ℓ1 /ℓq norm regularizations, for q > 1, that encourage the parameter matrix to have such blocksparse structure. Particular examples include results using the ℓ1 /ℓ∞ norm [16, 5, 8], and the ℓ1 /ℓ2 norm [7, 10]. Dirty Models. Block-regularization is “heavy-handed” in two ways. By strictly encouraging sharedsparsity, it assumes that all relevant features are shared, and hence suffers under settings, arguably more realistic, where each task depends on features speciﬁc to itself in addition to the ones that are common. The second concern with such block-sparse regularizers is that the ℓ1 /ℓq norms can be shown to encourage the entries in the non-sparse rows taking nearly identical values. Thus we are far away from the original goal of multitask learning: not only do the set of relevant features have to be exactly the same, but their values have to as well. Indeed recent research into such regularized methods [8, 10] caution against the use of block-regularization in regimes where the supports and values of the parameters for each task can vary widely. Since the true parameter values are unknown, that would be a worrisome caveat. We thus ask the question: can we learn multiple regression models by leveraging whatever overlap of features there exist, and without requiring the parameter values to be near identical? Indeed this is an instance of a more general question on whether we can estimate statistical models where the data may not fall cleanly into any one structural bracket (sparse, block-sparse and so on). With the explosion of dirty high-dimensional data in modern settings, it is vital to investigate estimation of corresponding dirty models, which might require new approaches to biased high-dimensional estimation. In this paper we take a ﬁrst step, focusing on such dirty models for a speciﬁc problem: simultaneously sparse multiple regression. Our approach uses a simple idea: while any one structure might not capture the data, a superposition of structural classes might. Our method thus searches for a parameter matrix that can be decomposed into a row-sparse matrix (corresponding to the overlapping or shared features) and an elementwise sparse matrix (corresponding to the non-shared features). As we show both theoretically and empirically, with this simple ﬁx we are able to leverage any extent of shared features, while allowing disparities in support and values of the parameters, so that we are always better than both the Lasso or block-sparse regularizers (at times remarkably so). The rest of the paper is organized as follows: In Sec 2. basic deﬁnitions and setup of the problem are presented. Main results of the paper is discussed in sec 3. Experimental results and simulations are demonstrated in Sec 4. Notation: For any matrix M , we denote its j th row as Mj , and its k-th column as M (k) . The set of all non-zero rows (i.e. all rows with at least one non-zero element) is denoted by RowSupp(M ) (k) and its support by Supp(M ). Also, for any matrix M , let M 1,1 := j,k |Mj |, i.e. the sums of absolute values of the elements, and M 1,∞ := j 2 Mj ∞ where, Mj ∞ (k) := maxk |Mj |. 2 Problem Set-up and Our Method Multiple regression. We consider the following standard multiple linear regression model: ¯ y (k) = X (k) θ(k) + w(k) , k = 1, . . . , r, where y (k) ∈ Rn is the response for the k-th task, regressed on the design matrix X (k) ∈ Rn×p (possibly different across tasks), while w(k) ∈ Rn is the noise vector. We assume each w(k) is drawn independently from N (0, σ 2 ). The total number of tasks or target variables is r, the number of features is p, while the number of samples we have for each task is n. For notational convenience, ¯ we collate these quantities into matrices Y ∈ Rn×r for the responses, Θ ∈ Rp×r for the regression n×r parameters and W ∈ R for the noise. ¯ Dirty Model. In this paper we are interested in estimating the true parameter Θ from data by lever¯ aging any (unknown) extent of simultaneous-sparsity. In particular, certain rows of Θ would have many non-zero entries, corresponding to features shared by several tasks (“shared” rows), while certain rows would be elementwise sparse, corresponding to those features which are relevant for some tasks but not all (“non-shared rows”), while certain rows would have all zero entries, corresponding to those features that are not relevant to any task. We are interested in estimators Θ that automatically adapt to different levels of sharedness, and yet enjoy the following guarantees: Support recovery: We say an estimator Θ successfully recovers the true signed support if ¯ sign(Supp(Θ)) = sign(Supp(Θ)). We are interested in deriving sufﬁcient conditions under which ¯ the estimator succeeds. We note that this is stronger than merely recovering the row-support of Θ, which is union of its supports for the different tasks. In particular, denoting Uk for the support of the ¯ k-th column of Θ, and U = k Uk . Error bounds: We are also interested in providing bounds on the elementwise ℓ∞ norm error of the estimator Θ, ¯ Θ−Θ 2.1 ∞ = max max j=1,...,p k=1,...,r (k) Θj (k) ¯ − Θj . Our Method Our method explicitly models the dirty block-sparse structure. We estimate a sum of two parameter matrices B and S with different regularizations for each: encouraging block-structured row-sparsity in B and elementwise sparsity in S. The corresponding “clean” models would either just use blocksparse regularizations [8, 10] or just elementwise sparsity regularizations [14, 18], so that either method would perform better in certain suited regimes. Interestingly, as we will see in the main results, by explicitly allowing to have both block-sparse and elementwise sparse component, we are ¯ able to outperform both classes of these “clean models”, for all regimes Θ. Algorithm 1 Dirty Block Sparse Solve the following convex optimization problem: (S, B) ∈ arg min S,B 1 2n r k=1 y (k) − X (k) S (k) + B (k) 2 2 + λs S 1,1 + λb B 1,∞ . (1) Then output Θ = B + S. 3 Main Results and Their Consequences We now provide precise statements of our main results. A number of recent results have shown that the Lasso [14, 18] and ℓ1 /ℓ∞ block-regularization [8] methods succeed in recovering signed supports with controlled error bounds under high-dimensional scaling regimes. Our ﬁrst two theorems extend these results to our dirty model setting. In Theorem 1, we consider the case of deterministic design matrices X (k) , and provide sufﬁcient conditions guaranteeing signed support recovery, and elementwise ℓ∞ norm error bounds. In Theorem 2, we specialize this theorem to the case where the 3 rows of the design matrices are random from a general zero mean Gaussian distribution: this allows us to provide scaling on the number of observations required in order to guarantee signed support recovery and bounded elementwise ℓ∞ norm error. Our third result is the most interesting in that it explicitly quantiﬁes the performance gains of our method vis-a-vis Lasso and the ℓ1 /ℓ∞ block-regularization method. Since this entailed ﬁnding the precise constants underlying earlier theorems, and a correspondingly more delicate analysis, we follow Negahban and Wainwright [8] and focus on the case where there are two-tasks (i.e. r = 2), and where we have standard Gaussian design matrices as in Theorem 2. Further, while each of two tasks depends on s features, only a fraction α of these are common. It is then interesting to see how the behaviors of the different regularization methods vary with the extent of overlap α. Comparisons. Negahban and Wainwright [8] show that there is actually a “phase transition” in the scaling of the probability of successful signed support-recovery with the number of observations. n Denote a particular rescaling of the sample-size θLasso (n, p, α) = s log(p−s) . Then as Wainwright [18] show, when the rescaled number of samples scales as θLasso > 2 + δ for any δ > 0, Lasso succeeds in recovering the signed support of all columns with probability converging to one. But when the sample size scales as θLasso < 2−δ for any δ > 0, Lasso fails with probability converging to one. For the ℓ1 /ℓ∞ -reguralized multiple linear regression, deﬁne a similar rescaled sample size n θ1,∞ (n, p, α) = s log(p−(2−α)s) . Then as Negahban and Wainwright [8] show there is again a transition in probability of success from near zero to near one, at the rescaled sample size of θ1,∞ = (4 − 3α). Thus, for α < 2/3 (“less sharing”) Lasso would perform better since its transition is at a smaller sample size, while for α > 2/3 (“more sharing”) the ℓ1 /ℓ∞ regularized method would perform better. As we show in our third theorem, the phase transition for our method occurs at the rescaled sample size of θ1,∞ = (2 − α), which is strictly before either the Lasso or the ℓ1 /ℓ∞ regularized method except for the boundary cases: α = 0, i.e. the case of no sharing, where we match Lasso, and for α = 1, i.e. full sharing, where we match ℓ1 /ℓ∞ . Everywhere else, we strictly outperform both methods. Figure 3 shows the empirical performance of each of the three methods; as can be seen, they agree very well with the theoretical analysis. (Further details in the experiments Section 4). 3.1 Sufﬁcient Conditions for Deterministic Designs We ﬁrst consider the case where the design matrices X (k) for k = 1, · · ·, r are deterministic, and start by specifying the assumptions we impose on the model. We note that similar sufﬁcient conditions for the deterministic X (k) ’s case were imposed in papers analyzing Lasso [18] and block-regularization methods [8, 10]. (k) A0 Column Normalization Xj 2 ≤ √ 2n for all j = 1, . . . , p, k = 1, . . . , r. ¯ Let Uk denote the support of the k-th column of Θ, and U = supports for each task. Then we require that k r A1 Incoherence Condition γb := 1 − max c j∈U (k) (k) Xj , XUk (k) (k) XUk , XUk Uk denote the union of −1 c We will also ﬁnd it useful to deﬁne γs := 1−max1≤k≤r maxj∈Uk (k) > 0. 1 k=1 (k) Xj , XUk Note that by the incoherence condition A1, we have γs > 0. A2 Eigenvalue Condition Cmin := min λmin 1≤k≤r A3 Boundedness Condition Dmax := max 1≤k≤r 1 (k) (k) XUk , XUk n 1 (k) (k) XUk , XUk n (k) (k) XUk , XUk −1 . 1 > 0. −1 ∞,1 < ∞. Further, we require the regularization penalties be set as λs > 2(2 − γs )σ log(pr) √ γs n and 4 λb > 2(2 − γb )σ log(pr) √ . γb n (2) 1 0.9 0.8 0.8 Dirty Model L1/Linf Reguralizer Probability of Success Probability of Success 1 0.9 0.7 0.6 0.5 0.4 LASSO 0.3 0.2 0 0.5 1 1.5 1.7 2 2.5 Control Parameter θ 3 3.1 3.5 0.6 0.5 0.4 L1/Linf Reguralizer 0.3 LASSO 0.2 p=128 p=256 p=512 0.1 Dirty Model 0.7 p=128 p=256 p=512 0.1 0 0.5 4 1 1.333 (a) α = 0.3 1.5 2 Control Parameter θ (b) α = 2.5 3 2 3 1 0.9 Dirty Model Probability of Success 0.8 0.7 L1/Linf Reguralizer 0.6 0.5 LASSO 0.4 0.3 0.2 p=128 p=256 p=512 0.1 0 0.5 1 1.2 1.5 1.6 2 Control Parameter θ 2.5 (c) α = 0.8 Figure 1: Probability of success in recovering the true signed support using dirty model, Lasso and ℓ1 /ℓ∞ regularizer. For a 2-task problem, the probability of success for different values of feature-overlap fraction α is plotted. As we can see in the regimes that Lasso is better than, as good as and worse than ℓ1 /ℓ∞ regularizer ((a), (b) and (c) respectively), the dirty model outperforms both of the methods, i.e., it requires less number of observations for successful recovery of the true signed support compared to Lasso and ℓ1 /ℓ∞ regularizer. Here p s = ⌊ 10 ⌋ always. Theorem 1. Suppose A0-A3 hold, and that we obtain estimate Θ from our algorithm with regularization parameters chosen according to (2). Then, with probability at least 1 − c1 exp(−c2 n) → 1, we are guaranteed that the convex program (1) has a unique optimum and (a) The estimate Θ has no false inclusions, and has bounded ℓ∞ norm error so that ¯ Supp(Θ) ⊆ Supp(Θ), and ¯ Θ−Θ ∞,∞ 4σ 2 log (pr) + λs Dmax . n Cmin ≤ bmin ¯ (b) sign(Supp(Θ)) = sign Supp(Θ) provided that min ¯ (j,k)∈Supp(Θ) ¯(k) θj > bmin . Here the positive constants c1 , c2 depend only on γs , γb , λs , λb and σ, but are otherwise independent of n, p, r, the problem dimensions of interest. Remark: Condition (a) guarantees that the estimate will have no false inclusions; i.e. all included features will be relevant. If in addition, we require that it have no false exclusions and that recover the support exactly, we need to impose the assumption in (b) that the non-zero elements are large enough to be detectable above the noise. 3.2 General Gaussian Designs Often the design matrices consist of samples from a Gaussian ensemble. Suppose that for each task (k) k = 1, . . . , r the design matrix X (k) ∈ Rn×p is such that each row Xi ∈ Rp is a zero-mean Gaussian random vector with covariance matrix Σ(k) ∈ Rp×p , and is independent of every other (k) row. Let ΣV,U ∈ R|V|×|U | be the submatrix of Σ(k) with rows corresponding to V and columns to U . We require these covariance matrices to satisfy the following conditions: r C1 Incoherence Condition γb := 1 − max c j∈U (k) (k) Σj,Uk , ΣUk ,Uk k=1 5 −1 >0 1 C2 Eigenvalue Condition Cmin := min λmin Σ(k),Uk Uk > 0 so that the minimum eigenvalue 1≤k≤r is bounded away from zero. C3 Boundedness Condition Dmax := (k) ΣUk ,Uk −1 ∞,1 < ∞. These conditions are analogues of the conditions for deterministic designs; they are now imposed on the covariance matrix of the (randomly generated) rows of the design matrix. Further, deﬁning s := maxk |Uk |, we require the regularization penalties be set as 1/2 λs > 1/2 4σ 2 Cmin log(pr) √ γs nCmin − 2s log(pr) and λb > 4σ 2 Cmin r(r log(2) + log(p)) . √ γb nCmin − 2sr(r log(2) + log(p)) (3) Theorem 2. Suppose assumptions C1-C3 hold, and that the number of samples scale as n > max 2s log(pr) 2sr r log(2)+log(p) 2 2 Cmin γs , Cmin γb . Suppose we obtain estimate Θ from algorithm (3). Then, with probability at least 1 − c1 exp (−c2 (r log(2) + log(p))) − c3 exp(−c4 log(rs)) → 1 for some positive numbers c1 − c4 , we are guaranteed that the algorithm estimate Θ is unique and satisﬁes the following conditions: (a) the estimate Θ has no false inclusions, and has bounded ℓ∞ norm error so that ¯ Supp(Θ) ⊆ Supp(Θ), and ¯ Θ−Θ ∞,∞ ≤ 50σ 2 log(rs) + λs nCmin 4s √ + Dmax . Cmin n gmin ¯ (b) sign(Supp(Θ)) = sign Supp(Θ) provided that 3.3 min ¯ (j,k)∈Supp(Θ) ¯(k) θj > gmin . Sharp Transition for 2-Task Gaussian Designs This is one of the most important results of this paper. Here, we perform a more delicate and ﬁner analysis to establish precise quantitative gains of our method. We focus on the special case where r = 2 and the design matrix has rows generated from the standard Gaussian distribution N (0, In×n ), so that C1 − C3 hold, with Cmin = Dmax = 1. As we will see both analytically and experimentally, our method strictly outperforms both Lasso and ℓ1 /ℓ∞ -block-regularization over for all cases, except at the extreme endpoints of no support sharing (where it matches that of Lasso) and full support sharing (where it matches that of ℓ1 /ℓ∞ ). We now present our analytical results; the empirical comparisons are presented next in Section 4. The results will be in terms of a particular rescaling of the sample size n as θ(n, p, s, α) := n . (2 − α)s log (p − (2 − α)s) We will also require the assumptions that 4σ 2 (1 − F1 λs > F2 λb > s/n)(log(r) + log(p − (2 − α)s)) 1/2 (n)1/2 − (s)1/2 − ((2 − α) s (log(r) + log(p − (2 − α)s)))1/2 4σ 2 (1 − s/n)r(r log(2) + log(p − (2 − α)s)) , 1/2 (n)1/2 − (s)1/2 − ((1 − α/2) sr (r log(2) + log(p − (2 − α)s)))1/2 . Theorem 3. Consider a 2-task regression problem (n, p, s, α), where the design matrix has rows generated from the standard Gaussian distribution N (0, In×n ). 6 Suppose maxj∈B∗ ∗(1) Θj − ∗(2) Θj = o(λs ), where B ∗ is the submatrix of Θ∗ with rows where both entries are non-zero. Then the estimate Θ of the problem (1) satisﬁes the following: (Success) Suppose the regularization coefﬁcients satisfy F1 − F2. Further, assume that the number of samples scales as θ(n, p, s, α) > 1. Then, with probability at least 1 − c1 exp(−c2 n) for some positive numbers c1 and c2 , we are guaranteed that Θ satisﬁes the support-recovery and ℓ∞ error bound conditions (a-b) in Theorem 2. ˆ ˆ (Failure) If θ(n, p, s, α) < 1 there is no solution (B, S) for any choices of λs and λb such that ¯ sign Supp(Θ) = sign Supp(Θ) . We note that we require the gap ∗(1) Θj ∗(2) − Θj to be small only on rows where both entries are non-zero. As we show in a more general theorem in the appendix, even in the case where the gap is large, the dependence of the sample scaling on the gap is quite weak. 4 Empirical Results In this section, we investigate the performance of our dirty block sparse estimator on synthetic and real-world data. The synthetic experiments explore the accuracy of Theorem 3, and compare our estimator with LASSO and the ℓ1 /ℓ∞ regularizer. We see that Theorem 3 is very accurate indeed. Next, we apply our method to a real world datasets containing hand-written digits for classiﬁcation. Again we compare against LASSO and the ℓ1 /ℓ∞ . (a multi-task regression dataset) with r = 2 tasks. In both of this real world dataset, we show that dirty model outperforms both LASSO and ℓ1 /ℓ∞ practically. For each method, the parameters are chosen via cross-validation; see supplemental material for more details. 4.1 Synthetic Data Simulation We consider a r = 2-task regression problem as discussed in Theorem 3, for a range of parameters (n, p, s, α). The design matrices X have each entry being i.i.d. Gaussian with mean 0 and variance 1. For each ﬁxed set of (n, s, p, α), we generate 100 instances of the problem. In each instance, ¯ given p, s, α, the locations of the non-zero entries of the true Θ are chosen at randomly; each nonzero entry is then chosen to be i.i.d. Gaussian with mean 0 and variance 1. n samples are then generated from this. We then attempt to estimate using three methods: our dirty model, ℓ1 /ℓ∞ regularizer and LASSO. In each case, and for each instance, the penalty regularizer coefﬁcients are found by cross validation. After solving the three problems, we compare the signed support of the solution with the true signed support and decide whether or not the program was successful in signed support recovery. We describe these process in more details in this section. Performance Analysis: We ran the algorithm for ﬁve different values of the overlap ratio α ∈ 2 {0.3, 3 , 0.8} with three different number of features p ∈ {128, 256, 512}. For any instance of the ˆ ¯ problem (n, p, s, α), if the recovered matrix Θ has the same sign support as the true Θ, then we count it as success, otherwise failure (even if one element has different sign, we count it as failure). As Theorem 3 predicts and Fig 3 shows, the right scaling for the number of oservations is n s log(p−(2−α)s) , where all curves stack on the top of each other at 2 − α. Also, the number of observations required by dirty model for true signed support recovery is always less than both LASSO and ℓ1 /ℓ∞ regularizer. Fig 1(a) shows the probability of success for the case α = 0.3 (when LASSO is better than ℓ1 /ℓ∞ regularizer) and that dirty model outperforms both methods. When α = 2 3 (see Fig 1(b)), LASSO and ℓ1 /ℓ∞ regularizer performs the same; but dirty model require almost 33% less observations for the same performance. As α grows toward 1, e.g. α = 0.8 as shown in Fig 1(c), ℓ1 /ℓ∞ performs better than LASSO. Still, dirty model performs better than both methods in this case as well. 7 4 p=128 p=256 p=512 Phase Transition Threshold 3.5 L1/Linf Regularizer 3 2.5 LASSO 2 Dirty Model 1.5 1 0 0.1 0.2 0.3 0.4 0.5 0.6 Shared Support Parameter α 0.7 0.8 0.9 1 Figure 2: Veriﬁcation of the result of the Theorem 3 on the behavior of phase transition threshold by changing the parameter α in a 2-task (n, p, s, α) problem for dirty model, LASSO and ℓ1 /ℓ∞ regularizer. The y-axis p n is s log(p−(2−α)s) , where n is the number of samples at which threshold was observed. Here s = ⌊ 10 ⌋. Our dirty model method shows a gain in sample complexity over the entire range of sharing α. The pre-constant in Theorem 3 is also validated. n 10 20 40 Average Classiﬁcation Error Variance of Error Average Row Support Size Average Support Size Average Classiﬁcation Error Variance of Error Average Row Support Size Average Support Size Average Classiﬁcation Error Variance of Error Average Row Support Size Average Support Size Our Model 8.6% 0.53% B:165 B + S:171 S:18 B + S:1651 3.0% 0.56% B:211 B + S:226 S:34 B + S:2118 2.2% 0.57% B:270 B + S:299 S:67 B + S:2761 ℓ1 /ℓ∞ 9.9% 0.64% 170 1700 3.5% 0.62% 217 2165 3.2% 0.68% 368 3669 LASSO 10.8% 0.51% 123 539 4.1% 0.68% 173 821 2.8% 0.85% 354 2053 Table 1: Handwriting Classiﬁcation Results for our model, ℓ1 /ℓ∞ and LASSO Scaling Veriﬁcation: To verify that the phase transition threshold changes linearly with α as predicted by Theorem 3, we plot the phase transition threshold versus α. For ﬁve different values of 2 α ∈ {0.05, 0.3, 3 , 0.8, 0.95} and three different values of p ∈ {128, 256, 512}, we ﬁnd the phase transition threshold for dirty model, LASSO and ℓ1 /ℓ∞ regularizer. We consider the point where the probability of success in recovery of signed support exceeds 50% as the phase transition threshold. We ﬁnd this point by interpolation on the closest two points. Fig 2 shows that phase transition threshold for dirty model is always lower than the phase transition for LASSO and ℓ1 /ℓ∞ regularizer. 4.2 Handwritten Digits Dataset We use the handwritten digit dataset [1], containing features of handwritten numerals (0-9) extracted from a collection of Dutch utility maps. This dataset has been used by a number of papers [17, 6] as a reliable dataset for handwritten recognition algorithms. There are thus r = 10 tasks, and each handwritten sample consists of p = 649 features. Table 1 shows the results of our analysis for different sizes n of the training set . We measure the classiﬁcation error for each digit to get the 10-vector of errors. Then, we ﬁnd the average error and the variance of the error vector to show how the error is distributed over all tasks. We compare our method with ℓ1 /ℓ∞ reguralizer method and LASSO. Again, in all methods, parameters are chosen via cross-validation. For our method we separate out the B and S matrices that our method ﬁnds, so as to illustrate how many features it identiﬁes as “shared” and how many as “non-shared”. For the other methods we just report the straight row and support numbers, since they do not make such a separation. Acknowledgements We acknowledge support from NSF grant IIS-101842, and NSF CAREER program, Grant 0954059. 8 References [1] A. Asuncion and D.J. Newman. UCI Machine Learning Repository, http://www.ics.uci.edu/ mlearn/MLRepository.html. University of California, School of Information and Computer Science, Irvine, CA, 2007. [2] F. Bach. Consistency of the group lasso and multiple kernel learning. Journal of Machine Learning Research, 9:1179–1225, 2008. [3] R. Baraniuk. Compressive sensing. IEEE Signal Processing Magazine, 24(4):118–121, 2007. [4] R. Caruana. Multitask learning. Machine Learning, 28:41–75, 1997. [5] C.Zhang and J.Huang. Model selection consistency of the lasso selection in high-dimensional linear regression. Annals of Statistics, 36:1567–1594, 2008. [6] X. He and P. Niyogi. Locality preserving projections. In NIPS, 2003. [7] K. Lounici, A. B. Tsybakov, M. Pontil, and S. A. van de Geer. Taking advantage of sparsity in multi-task learning. In 22nd Conference On Learning Theory (COLT), 2009. [8] S. Negahban and M. J. Wainwright. Joint support recovery under high-dimensional scaling: Beneﬁts and perils of ℓ1,∞ -regularization. In Advances in Neural Information Processing Systems (NIPS), 2008. [9] S. Negahban and M. J. Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. In ICML, 2010. [10] G. Obozinski, M. J. Wainwright, and M. I. Jordan. Support union recovery in high-dimensional multivariate regression. Annals of Statistics, 2010. [11] P. Ravikumar, H. Liu, J. Lafferty, and L. Wasserman. Sparse additive models. Journal of the Royal Statistical Society, Series B. [12] P. Ravikumar, M. J. Wainwright, and J. Lafferty. High-dimensional ising model selection using ℓ1 -regularized logistic regression. Annals of Statistics, 2009. [13] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. In Allerton Conference, Allerton House, Illinois, 2007. [14] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58(1):267–288, 1996. [15] J. A. Tropp, A. C. Gilbert, and M. J. Strauss. Algorithms for simultaneous sparse approximation. Signal Processing, Special issue on “Sparse approximations in signal and image processing”, 86:572–602, 2006. [16] B. Turlach, W.N. Venables, and S.J. Wright. Simultaneous variable selection. Techno- metrics, 27:349–363, 2005. [17] M. van Breukelen, R.P.W. Duin, D.M.J. Tax, and J.E. den Hartog. Handwritten digit recognition by combined classiﬁers. Kybernetika, 34(4):381–386, 1998. [18] M. J. Wainwright. Sharp thresholds for noisy and high-dimensional recovery of sparsity using ℓ1 -constrained quadratic programming (lasso). IEEE Transactions on Information Theory, 55: 2183–2202, 2009. 9

4 0.10442613 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

Author: Jean Morales, Charles A. Micchelli, Massimiliano Pontil

Abstract: We study the problem of learning a sparse linear regression vector under additional conditions on the structure of its sparsity pattern. We present a family of convex penalty functions, which encode this prior knowledge by means of a set of constraints on the absolute values of the regression coefﬁcients. This family subsumes the ℓ1 norm and is ﬂexible enough to include different models of sparsity patterns, which are of practical and theoretical importance. We establish some important properties of these functions and discuss some examples where they can be computed explicitly. Moreover, we present a convergent optimization algorithm for solving regularized least squares with these penalty functions. Numerical simulations highlight the beneﬁt of structured sparsity and the advantage offered by our approach over the Lasso and other related methods.

5 0.10106235 26 nips-2010-Adaptive Multi-Task Lasso: with Application to eQTL Detection

Author: Seunghak Lee, Jun Zhu, Eric P. Xing

Abstract: To understand the relationship between genomic variations among population and complex diseases, it is essential to detect eQTLs which are associated with phenotypic effects. However, detecting eQTLs remains a challenge due to complex underlying mechanisms and the very large number of genetic loci involved compared to the number of samples. Thus, to address the problem, it is desirable to take advantage of the structure of the data and prior information about genomic locations such as conservation scores and transcription factor binding sites. In this paper, we propose a novel regularized regression approach for detecting eQTLs which takes into account related traits simultaneously while incorporating many regulatory features. We ﬁrst present a Bayesian network for a multi-task learning problem that includes priors on SNPs, making it possible to estimate the signiﬁcance of each covariate adaptively. Then we ﬁnd the maximum a posteriori (MAP) estimation of regression coefﬁcients and estimate weights of covariates jointly. This optimization procedure is efﬁcient since it can be achieved by using a projected gradient descent and a coordinate descent procedure iteratively. Experimental results on simulated and real yeast datasets conﬁrm that our model outperforms previous methods for ﬁnding eQTLs.

6 0.098212086 265 nips-2010-The LASSO risk: asymptotic results and real world examples

7 0.089096658 12 nips-2010-A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups

8 0.076554999 170 nips-2010-Moreau-Yosida Regularization for Grouped Tree Structure Learning

9 0.074475721 274 nips-2010-Trading off Mistakes and Don't-Know Predictions

10 0.072981156 94 nips-2010-Feature Set Embedding for Incomplete Data

11 0.067716308 13 nips-2010-A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction

12 0.066211641 172 nips-2010-Multi-Stage Dantzig Selector

13 0.066097654 159 nips-2010-Lifted Inference Seen from the Other Side : The Tractable Features

14 0.064083979 91 nips-2010-Fast detection of multiple change-points shared by many signals using group LARS

15 0.063565314 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery

16 0.062310703 148 nips-2010-Learning Networks of Stochastic Differential Equations

17 0.056406241 178 nips-2010-Multivariate Dyadic Regression Trees for Sparse Learning Problems

18 0.056340478 217 nips-2010-Probabilistic Multi-Task Feature Selection

19 0.055621333 255 nips-2010-Static Analysis of Binary Executables Using Structural SVMs

20 0.055608362 139 nips-2010-Latent Variable Models for Predicting File Dependencies in Large-Scale Software Development

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.19), (1, 0.028), (2, 0.033), (3, 0.035), (4, 0.025), (5, -0.105), (6, -0.033), (7, 0.084), (8, -0.061), (9, -0.041), (10, 0.003), (11, 0.13), (12, -0.073), (13, 0.03), (14, 0.025), (15, -0.061), (16, -0.042), (17, 0.072), (18, 0.021), (19, -0.03), (20, -0.027), (21, 0.096), (22, 0.066), (23, 0.035), (24, 0.013), (25, -0.062), (26, -0.035), (27, -0.003), (28, -0.031), (29, 0.004), (30, 0.021), (31, -0.094), (32, -0.049), (33, -0.004), (34, -0.024), (35, 0.005), (36, 0.048), (37, 0.089), (38, 0.216), (39, -0.036), (40, 0.023), (41, 0.01), (42, -0.055), (43, 0.036), (44, -0.014), (45, -0.039), (46, 0.054), (47, -0.022), (48, -0.067), (49, 0.059)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94202322 211 nips-2010-Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression

Author: Ling Huang, Jinzhu Jia, Bin Yu, Byung-gon Chun, Petros Maniatis, Mayur Naik

2 0.75797814 5 nips-2010-A Dirty Model for Multi-task Learning

Author: Ali Jalali, Sujay Sanghavi, Chao Ruan, Pradeep K. Ravikumar

3 0.74272072 172 nips-2010-Multi-Stage Dantzig Selector

Author: Ji Liu, Peter Wonka, Jieping Ye

Abstract: We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X ∈ Rn×m (m n) and a noisy observation vector y ∈ Rn satisfying y = Xβ ∗ + where is the noise vector following a Gaussian distribution N (0, σ 2 I), how to recover the signal (or parameter vector) β ∗ when the signal is sparse? The Dantzig selector has been proposed for sparse signal recovery with strong theoretical guarantees. In this paper, we propose a multi-stage Dantzig selector method, which iteratively reﬁnes the target signal β ∗ . We show that if X obeys a certain condition, then with a large probability the difference between the solution ˆ β estimated by the proposed method and the true solution β ∗ measured in terms of the lp norm (p ≥ 1) is bounded as ˆ β − β∗ p ≤ C(s − N )1/p log m + ∆ σ, where C is a constant, s is the number of nonzero entries in β ∗ , ∆ is independent of m and is much smaller than the ﬁrst term, and N is the number of entries of √ β ∗ larger than a certain value in the order of O(σ log m). The proposed method improves the estimation bound of the standard Dantzig selector approximately √ √ from Cs1/p log mσ to C(s − N )1/p log mσ where the value N depends on the number of large entries in β ∗ . When N = s, the proposed algorithm achieves the oracle solution with a high probability. In addition, with a large probability, the proposed method can select the same number of correct features under a milder condition than the Dantzig selector. 1

4 0.73705649 26 nips-2010-Adaptive Multi-Task Lasso: with Application to eQTL Detection

Author: Seunghak Lee, Jun Zhu, Eric P. Xing

5 0.70766115 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

Author: Jean Morales, Charles A. Micchelli, Massimiliano Pontil

6 0.69956934 260 nips-2010-Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework

7 0.56419206 12 nips-2010-A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups

8 0.55469906 265 nips-2010-The LASSO risk: asymptotic results and real world examples

9 0.51504368 159 nips-2010-Lifted Inference Seen from the Other Side : The Tractable Features

10 0.51295424 148 nips-2010-Learning Networks of Stochastic Differential Equations

11 0.49178067 45 nips-2010-CUR from a Sparse Optimization Viewpoint

12 0.4848817 73 nips-2010-Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization

13 0.4773542 94 nips-2010-Feature Set Embedding for Incomplete Data

14 0.47372901 212 nips-2010-Predictive State Temporal Difference Learning

15 0.47255397 154 nips-2010-Learning sparse dynamic linear systems using stable spline kernels and exponential hyperpriors

16 0.47146398 274 nips-2010-Trading off Mistakes and Don't-Know Predictions

17 0.45110366 170 nips-2010-Moreau-Yosida Regularization for Grouped Tree Structure Learning

18 0.44451806 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery

19 0.43187052 93 nips-2010-Feature Construction for Inverse Reinforcement Learning

20 0.42959884 91 nips-2010-Fast detection of multiple change-points shared by many signals using group LARS

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.044), (17, 0.016), (18, 0.205), (27, 0.067), (30, 0.082), (35, 0.043), (45, 0.224), (50, 0.064), (52, 0.025), (60, 0.029), (77, 0.057), (78, 0.024), (90, 0.04)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.89126045 267 nips-2010-The Multidimensional Wisdom of Crowds

Author: Peter Welinder, Steve Branson, Pietro Perona, Serge J. Belongie

Abstract: Distributing labeling tasks among hundreds or thousands of annotators is an increasingly important method for annotating large datasets. We present a method for estimating the underlying value (e.g. the class) of each image from (noisy) annotations provided by multiple annotators. Our method is based on a model of the image formation and annotation process. Each image has different characteristics that are represented in an abstract Euclidean space. Each annotator is modeled as a multidimensional entity with variables representing competence, expertise and bias. This allows the model to discover and represent groups of annotators that have different sets of skills and knowledge, as well as groups of images that differ qualitatively. We ﬁnd that our model predicts ground truth labels on both synthetic and real data more accurately than state of the art methods. Experiments also show that our model, starting from a set of binary labels, may discover rich information, such as different “schools of thought” amongst the annotators, and can group together images belonging to separate categories. 1

same-paper 2 0.8354097 211 nips-2010-Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression

Author: Ling Huang, Jinzhu Jia, Bin Yu, Byung-gon Chun, Petros Maniatis, Mayur Naik

3 0.82611859 144 nips-2010-Learning Efficient Markov Networks

Author: Vibhav Gogate, William Webb, Pedro Domingos

Abstract: We present an algorithm for learning high-treewidth Markov networks where inference is still tractable. This is made possible by exploiting context-speciﬁc independence and determinism in the domain. The class of models our algorithm can learn has the same desirable properties as thin junction trees: polynomial inference, closed-form weight learning, etc., but is much broader. Our algorithm searches for a feature that divides the state space into subspaces where the remaining variables decompose into independent subsets (conditioned on the feature and its negation) and recurses on each subspace/subset of variables until no useful new features can be found. We provide probabilistic performance guarantees for our algorithm under the assumption that the maximum feature length is bounded by a constant k (the treewidth can be much larger) and dependences are of bounded strength. We also propose a greedy version of the algorithm that, while forgoing these guarantees, is much more efﬁcient. Experiments on a variety of domains show that our approach outperforms many state-of-the-art Markov network structure learners. 1

4 0.81113005 52 nips-2010-Convex Multiple-Instance Learning by Estimating Likelihood Ratio

Author: Fuxin Li, Cristian Sminchisescu

Abstract: We propose an approach to multiple-instance learning that reformulates the problem as a convex optimization on the likelihood ratio between the positive and the negative class for each training instance. This is casted as joint estimation of both a likelihood ratio predictor and the target (likelihood ratio variable) for instances. Theoretically, we prove a quantitative relationship between the risk estimated under the 0-1 classiﬁcation loss, and under a loss function for likelihood ratio. It is shown that likelihood ratio estimation is generally a good surrogate for the 0-1 loss, and separates positive and negative instances well. The likelihood ratio estimates provide a ranking of instances within a bag and are used as input features to learn a linear classiﬁer on bags of instances. Instance-level classiﬁcation is achieved from the bag-level predictions and the individual likelihood ratios. Experiments on synthetic and real datasets demonstrate the competitiveness of the approach.

5 0.78310937 155 nips-2010-Learning the context of a category

Author: Dan Navarro

Abstract: This paper outlines a hierarchical Bayesian model for human category learning that learns both the organization of objects into categories, and the context in which this knowledge should be applied. The model is ﬁt to multiple data sets, and provides a parsimonious method for describing how humans learn context speciﬁc conceptual representations.

6 0.78146857 63 nips-2010-Distributed Dual Averaging In Networks

7 0.77953023 51 nips-2010-Construction of Dependent Dirichlet Processes based on Poisson Processes

8 0.77899212 260 nips-2010-Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework

9 0.77887481 117 nips-2010-Identifying graph-structured activation patterns in networks

10 0.77863902 148 nips-2010-Learning Networks of Stochastic Differential Equations

11 0.77800149 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

12 0.77778977 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior

13 0.77671146 49 nips-2010-Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning

14 0.77634585 238 nips-2010-Short-term memory in neuronal networks through dynamical compressed sensing

15 0.77538139 12 nips-2010-A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups

16 0.77461475 158 nips-2010-Learning via Gaussian Herding

17 0.77416801 282 nips-2010-Variable margin losses for classifier design

18 0.77409375 243 nips-2010-Smoothness, Low Noise and Fast Rates

19 0.77397227 13 nips-2010-A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction

20 0.77397025 7 nips-2010-A Family of Penalty Functions for Structured Sparsity