jmlr jmlr2013 jmlr2013-46 knowledge-graph by maker-knowledge-mining

46 jmlr-2013-GURLS: A Least Squares Library for Supervised Learning

Source: pdf

Author: Andrea Tacchetti, Pavan K. Mallapragada, Matteo Santoro, Lorenzo Rosasco

Abstract: We present GURLS, a least squares, modular, easy-to-extend software library for efﬁcient supervised learning. GURLS is targeted to machine learning practitioners, as well as non-specialists. It offers a number state-of-the-art training strategies for medium and large-scale learning, and routines for efﬁcient model selection. The library is particularly well suited for multi-output problems (multi-category/multi-label). GURLS is currently available in two independent implementations: Matlab and C++. It takes advantage of the favorable properties of regularized least squares algorithm to exploit advanced tools in linear algebra. Routines to handle computations with very large matrices by means of memory-mapped storage and distributed task execution are available. The package is distributed under the BSD license and is available for download at https://github.com/LCSL/GURLS. Keywords: regularized least squares, big data, linear algebra 1. Introduction and Design Supervised learning has become a fundamental tool for the design of intelligent systems and the analysis of high dimensional data. Key to this success has been the availability of efﬁcient, easy-touse software packages. New data collection technologies make it easy to gather high dimensional, multi-output data sets of increasing size. This trend calls for new software solutions for the automatic training, tuning and testing of supervised learning methods. These observations motivated the design of GURLS (Grand Uniﬁed Regularized Least Squares). The package was developed to pursue the following goals: Speed: Fast training/testing procedures for learning problems with potentially large/huge number of points, features and especially outputs (e.g., classes). Memory: Flexible data management to work with large data sets by means of memory-mapped storage. Performance: ∗. Also in the Laboratory for Computational and Statistical Learning, Istituto Italiano di Tecnologia and Massachusetts Institute of Technology c 2013 Andrea Tacchetti, Pavan K. Mallapragada, Matteo Santoro and Lorenzo Rosasco. TACCHETTI , M ALLAPRAGADA , S ANTORO AND ROSASCO State of the art results in high-dimensional multi-output problems. Usability and modularity: Easy to use and to expand. GURLS is based on Regularized Least Squares (RLS) and takes advantage of all the favorable properties of these methods (Rifkin et al., 2003). Since the algorithm reduces to solving a linear system, GURLS is set up to exploit the powerful tools, and recent advances, of linear algebra (including randomized solver, ﬁrst order methods, etc.). Second, it makes use of RLS properties which are particularly suited for high dimensional learning. For example: (1) RLS has natural primal and dual formulation (hence having complexity which is the smallest between number of examples and features); (2) efﬁcient parameter selection (closed form expression of the leave one out error and efﬁcient computations of regularization path); (3) natural and efﬁcient extension to multiple outputs. Speciﬁc attention has been devoted to handle large high dimensional data sets. We rely on data structures that can be serialized using memory-mapped ﬁles, and on a distributed task manager to perform a number of key steps (such as matrix multiplication) without loading the whole data set in memory. Efforts were devoted to to provide a lean API and an exhaustive documentation. GURLS has been deployed and tested successfully on Linux, MacOS and Windows. The library is distributed under the simpliﬁed BSD license, and can be downloaded from https://github.com/LCSL/GURLS. 2. Description of the Library The library comprises four main modules. GURLS and bGURLS—both implemented in Matlab— are aimed at solving learning problems with small/medium and large-scale data sets respectively. GURLS++ and bGURLS++ are their C++ counterparts. The Matlab and C++ versions share the same design, but the C++ modules have signiﬁcant improvements, which make them faster and more ﬂexible. The speciﬁcation of the desired machine learning experiment in the library is straightforward. Basically, it is a formal description of a pipeline, that is, an ordered sequence of steps. Each step identiﬁes an actual learning task, and belongs to a predeﬁned category. The core of the library is a method (a class in the C++ implementation) called GURLScore, which is responsible for processing the sequence of tasks in the proper order and for linking the output of the former task to the input of the subsequent one. A key role is played by the additional “options” structure, referred to as OPT. OPT is used to store all conﬁguration parameters required to customize the behavior of individual tasks in the pipeline. Tasks receive conﬁguration parameters from OPT in read-only mode and—upon termination—the results are appended to the structure by GURLScore in order to make them available to subsequent tasks. This allows the user to skip the execution of some tasks in a pipeline, by simply inserting the desired results directly into the options structure. Currently, we identify six different task categories: data set splitting, kernel computation, model selection, training, evaluation and testing and performance assessment and analysis. Tasks belonging to the same category may be interchanged with each other. 2.1 Learning From Large Data Sets Two modules in GURLS have been speciﬁcally designed to deal with big data scenarios. The approach we adopted is mainly based on a memory-mapped abstraction of matrix and vector data structures, and on a distributed computation of a number of standard problems in linear algebra. For learning on big data, we decided to focus speciﬁcally on those situations where one seeks a linear model on a large set of (possibly non linear) features. A more accurate speciﬁcation of what “large” means in GURLS is related to the number of features d and the number of training 3202 GURLS: A L EAST S QUARES L IBRARY FOR S UPERVISED L EARNING data set optdigit landast pendigit letter isolet # of samples 3800 4400 7400 10000 6200 # of classes 10 6 10 26 26 # of variables 64 36 16 16 600 Table 1: Data sets description. examples n: we require it must be possible to store a min(d, n) × min(d, n) matrix in memory. In practice, this roughly means we can train models with up-to 25k features on machines with 8Gb of RAM, and up-to 50k features on machines with 36Gb of RAM. We do not require the data matrix itself to be stored in memory: within GURLS it is possible to manage an arbitrarily large set of training examples. We distinguish two different scenarios. Data sets that can fully reside in RAM without any memory mapping techniques—such as swapping—are considered to be small/medium. Larger data sets are considered to be “big” and learning must be performed using either bGURLS or bGURLS++ . These two modules include all the design patterns described above, and have been complemented with additional big data and distributed computation capabilities. Big data support is obtained using a data structure called bigarray, which allows to handle data matrices as large as the space available on the hard drive: we store the entire data set on disk and load only small chunks in memory when required. There are some differences between the Matlab and C++ implementations. bGURLS relies on a simple, ad hoc interface, called GURLS Distributed Manager (GDM), to distribute matrix-matrix multiplications, thus allowing users to perform the important task of kernel matrix computation on a distributed network of computing nodes. After this step, the subsequent tasks behave as in GURLS. bGURLS++ (currently in active development) offers more interesting features because it is based on the MPI libraries. Therefore, it allows for a full distribution within every single task of the pipeline. All the processes read the input data from a shared ﬁlesystem over the network and then start executing the same pipeline. During execution, each process’ task communicates with the corresponding ones. Every process maintains its local copy of the options. Once the same task is completed by all processes, the local copies of the options are synchronized. This architecture allows for the creation of hybrid pipelines comprising serial one-process-based tasks from GURLS++ . 3. Experiments We decided to focus the experimental analysis in the paper to the assessment of GURLS’ performance both in terms of accuracy and time. In our experiments we considered 5 popular data sets, brieﬂy described in Table 1. Experiments were run on a Intel Xeon 5140 @ 2.33GHz processor with 8GB of RAM, and running Ubuntu 8.10 Server (64 bit). optdigit accuracy (%) GURLS (linear primal) GURLS (linear dual) LS-SVM linear GURLS (500 random features) GURLS (1000 random features) GURLS (Gaussian kernel) LS-SVM (Gaussian kernel) time (s) landsat accuracy (%) time (s) pendigit accuracy (%) time (s) 92.3 92.3 92.3 96.8 97.5 98.3 98.3 0.49 726 7190 25.6 207 13500 26100 63.68 66.3 64.6 63.5 63.5 90.4 90.51 0.22 1148 6526 28.0 187 20796 18430 82.24 82.46 82.3 96.7 95.8 98.4 98.36 0.23 5590 46240 31.6 199 100600 120170 Table 2: Comparison between GURLS and LS-SVM. 3203 TACCHETTI , M ALLAPRAGADA , S ANTORO AND ROSASCO Performance (%) 1 0.95 0.9 0.85 isolet(∇) letter(×) 0.8 pendigit(∆) 0.75 landsat(♦) optdigit(◦) 0.7 LIBSVM:rbf 0.65 GURLS++:rbf GURLS:randomfeatures-1000 0.6 GURLS:randomfeatures-500 0.55 0.5 0 10 GURLS:rbf 1 10 2 10 3 10 4 Time (s) 10 Figure 1: Prediction accuracy vs. computing time. The color represents the training method and the library used. In blue: the Matlab implementation of RLS with RBF kernel, in red: its C++ counterpart. In dark red: results of LIBSVM with RBF kernel. In yellow and green: results obtained using a linear kernel on 500 and 1000 random features respectively. We set up different pipelines and compared the performance to SVM, for which we used the python modular interface to LIBSVM (Chang and Lin, 2011). Automatic selection of the optimal regularization parameter is implemented identically in all experiments: (i) split the data; (ii) deﬁne a set of regularization parameter on a regular grid; (iii) perform hold-out validation. The variance of the Gaussian kernel has been ﬁxed by looking at the statistics of the pairwise distances among training examples. The prediction accuracy of GURLS and GURLS++ is identical—as expected—but the implementation in C++ is signiﬁcantly faster. The prediction accuracy of standard RLS-based methods is in many cases higher than SVM. Exploiting the primal formulation of RLS, we further ran experiments with the random features approximation (Rahimi and Recht, 2008). As show in Figure 1, the performance of this method is comparable to that of SVM at a much lower computational cost in the majority of the tested data sets. We further compared GURLS with another available least squares based toolbox: the LS-SVM toolbox (Suykens et al., 2001), which includes routines for parameter selection such as coupled simulated annealing and line/grid search. The goal of this experiment is to benchmark the performance of the parameter selection with random data splitting included in GURLS. For a fair comparison, we considered only the Matlab implementation of GURLS. Results are reported in Table 2. As expected, using the linear kernel with the primal formulation—not available in LS-SVM—is the fastest approach since it leverages the lower dimensionality of the input space. When the Gaussian kernel is used, GURLS and LS-SVM have comparable computing time and classiﬁcation performance. Note, however, that in GURLS the number of parameter in the grid search is ﬁxed to 400, while in LS-SVM it may vary and is limited to 70. The interesting results obtained with the random features implementation in GURLS, make it an interesting choice in many applications. Finally, all GURLS pipelines, in their Matlab implementation, are faster than LS-SVM and further improvements can be achieved with GURLS++ . Acknowledgments We thank Tomaso Poggio, Zak Stone, Nicolas Pinto, Hristo S. Paskov and CBCL for comments and insights. 3204 GURLS: A L EAST S QUARES L IBRARY FOR S UPERVISED L EARNING References C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011. Software available at http://www. csie.ntu.edu.tw/˜cjlin/libsvm. A. Rahimi and B. Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In Advances in Neural Information Processing Systems, volume 21, pages 1313–1320, 2008. R. Rifkin, G. Yeo, and T. Poggio. Regularized least-squares classiﬁcation. Nato Science Series Sub Series III Computer and Systems Sciences, 190:131–154, 2003. J. Suykens, T. V. Gestel, J. D. Brabanter, B. D. Moor, and J. Vandewalle. Least Squares Support Vector Machines. World Scientiﬁc, 2001. ISBN 981-238-151-1. 3205

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 IT Laboratory for Computational and Statistical Learning, Istituto Italiano di Tecnologia Via Morego, 30 16163 Genova, Italy Lorenzo Rosasco∗ LROSASCO @ MIT. [sent-7, score-0.019]

2 EDU DIBRIS, Universit` degli Studi di Genova a via Dodecaneso, 35 16146 Genova, Italy Editor: Geoff Holmes Abstract We present GURLS, a least squares, modular, easy-to-extend software library for efﬁcient supervised learning. [sent-8, score-0.16]

3 It offers a number state-of-the-art training strategies for medium and large-scale learning, and routines for efﬁcient model selection. [sent-10, score-0.042]

4 The library is particularly well suited for multi-output problems (multi-category/multi-label). [sent-11, score-0.097]

5 GURLS is currently available in two independent implementations: Matlab and C++. [sent-12, score-0.022]

6 It takes advantage of the favorable properties of regularized least squares algorithm to exploit advanced tools in linear algebra. [sent-13, score-0.098]

7 Routines to handle computations with very large matrices by means of memory-mapped storage and distributed task execution are available. [sent-14, score-0.089]

8 The package is distributed under the BSD license and is available for download at https://github. [sent-15, score-0.083]

9 Keywords: regularized least squares, big data, linear algebra 1. [sent-17, score-0.097]

10 Key to this success has been the availability of efﬁcient, easy-touse software packages. [sent-19, score-0.023]

11 This trend calls for new software solutions for the automatic training, tuning and testing of supervised learning methods. [sent-21, score-0.045]

12 The package was developed to pursue the following goals: Speed: Fast training/testing procedures for learning problems with potentially large/huge number of points, features and especially outputs (e. [sent-23, score-0.04]

13 Also in the Laboratory for Computational and Statistical Learning, Istituto Italiano di Tecnologia and Massachusetts Institute of Technology c 2013 Andrea Tacchetti, Pavan K. [sent-28, score-0.019]

14 GURLS is based on Regularized Least Squares (RLS) and takes advantage of all the favorable properties of these methods (Rifkin et al. [sent-32, score-0.024]

15 Second, it makes use of RLS properties which are particularly suited for high dimensional learning. [sent-36, score-0.02]

16 We rely on data structures that can be serialized using memory-mapped ﬁles, and on a distributed task manager to perform a number of key steps (such as matrix multiplication) without loading the whole data set in memory. [sent-39, score-0.1]

17 The library is distributed under the simpliﬁed BSD license, and can be downloaded from https://github. [sent-42, score-0.101]

18 Description of the Library The library comprises four main modules. [sent-45, score-0.077]

19 The Matlab and C++ versions share the same design, but the C++ modules have signiﬁcant improvements, which make them faster and more ﬂexible. [sent-48, score-0.053]

20 The speciﬁcation of the desired machine learning experiment in the library is straightforward. [sent-49, score-0.077]

21 The core of the library is a method (a class in the C++ implementation) called GURLScore, which is responsible for processing the sequence of tasks in the proper order and for linking the output of the former task to the input of the subsequent one. [sent-52, score-0.174]

22 OPT is used to store all conﬁguration parameters required to customize the behavior of individual tasks in the pipeline. [sent-54, score-0.071]

23 Tasks receive conﬁguration parameters from OPT in read-only mode and—upon termination—the results are appended to the structure by GURLScore in order to make them available to subsequent tasks. [sent-55, score-0.043]

24 This allows the user to skip the execution of some tasks in a pipeline, by simply inserting the desired results directly into the options structure. [sent-56, score-0.108]

25 Currently, we identify six different task categories: data set splitting, kernel computation, model selection, training, evaluation and testing and performance assessment and analysis. [sent-57, score-0.086]

26 Tasks belonging to the same category may be interchanged with each other. [sent-58, score-0.021]

27 1 Learning From Large Data Sets Two modules in GURLS have been speciﬁcally designed to deal with big data scenarios. [sent-60, score-0.122]

28 The approach we adopted is mainly based on a memory-mapped abstraction of matrix and vector data structures, and on a distributed computation of a number of standard problems in linear algebra. [sent-61, score-0.024]

29 For learning on big data, we decided to focus speciﬁcally on those situations where one seeks a linear model on a large set of (possibly non linear) features. [sent-62, score-0.097]

30 examples n: we require it must be possible to store a min(d, n) × min(d, n) matrix in memory. [sent-64, score-0.03]

31 In practice, this roughly means we can train models with up-to 25k features on machines with 8Gb of RAM, and up-to 50k features on machines with 36Gb of RAM. [sent-65, score-0.08]

32 Data sets that can fully reside in RAM without any memory mapping techniques—such as swapping—are considered to be small/medium. [sent-68, score-0.031]

33 These two modules include all the design patterns described above, and have been complemented with additional big data and distributed computation capabilities. [sent-70, score-0.146]

34 Big data support is obtained using a data structure called bigarray, which allows to handle data matrices as large as the space available on the hard drive: we store the entire data set on disk and load only small chunks in memory when required. [sent-71, score-0.08]

35 bGURLS relies on a simple, ad hoc interface, called GURLS Distributed Manager (GDM), to distribute matrix-matrix multiplications, thus allowing users to perform the important task of kernel matrix computation on a distributed network of computing nodes. [sent-73, score-0.087]

36 After this step, the subsequent tasks behave as in GURLS. [sent-74, score-0.063]

37 bGURLS++ (currently in active development) offers more interesting features because it is based on the MPI libraries. [sent-75, score-0.04]

38 Therefore, it allows for a full distribution within every single task of the pipeline. [sent-76, score-0.034]

39 All the processes read the input data from a shared ﬁlesystem over the network and then start executing the same pipeline. [sent-77, score-0.019]

40 During execution, each process’ task communicates with the corresponding ones. [sent-78, score-0.034]

41 Once the same task is completed by all processes, the local copies of the options are synchronized. [sent-80, score-0.07]

42 This architecture allows for the creation of hybrid pipelines comprising serial one-process-based tasks from GURLS++ . [sent-81, score-0.115]

43 Experiments We decided to focus the experimental analysis in the paper to the assessment of GURLS’ performance both in terms of accuracy and time. [sent-83, score-0.073]

44 optdigit accuracy (%) GURLS (linear primal) GURLS (linear dual) LS-SVM linear GURLS (500 random features) GURLS (1000 random features) GURLS (Gaussian kernel) LS-SVM (Gaussian kernel) time (s) landsat accuracy (%) time (s) pendigit accuracy (%) time (s) 92. [sent-88, score-0.263]

45 5 0 10 GURLS:rbf 1 10 2 10 3 10 4 Time (s) 10 Figure 1: Prediction accuracy vs. [sent-126, score-0.022]

46 The color represents the training method and the library used. [sent-128, score-0.077]

47 In yellow and green: results obtained using a linear kernel on 500 and 1000 random features respectively. [sent-131, score-0.069]

48 We set up different pipelines and compared the performance to SVM, for which we used the python modular interface to LIBSVM (Chang and Lin, 2011). [sent-132, score-0.119]

49 The variance of the Gaussian kernel has been ﬁxed by looking at the statistics of the pairwise distances among training examples. [sent-134, score-0.029]

50 The prediction accuracy of GURLS and GURLS++ is identical—as expected—but the implementation in C++ is signiﬁcantly faster. [sent-135, score-0.022]

51 The prediction accuracy of standard RLS-based methods is in many cases higher than SVM. [sent-136, score-0.022]

52 Exploiting the primal formulation of RLS, we further ran experiments with the random features approximation (Rahimi and Recht, 2008). [sent-137, score-0.086]

53 We further compared GURLS with another available least squares based toolbox: the LS-SVM toolbox (Suykens et al. [sent-139, score-0.07]

54 , 2001), which includes routines for parameter selection such as coupled simulated annealing and line/grid search. [sent-140, score-0.042]

55 The goal of this experiment is to benchmark the performance of the parameter selection with random data splitting included in GURLS. [sent-141, score-0.02]

56 As expected, using the linear kernel with the primal formulation—not available in LS-SVM—is the fastest approach since it leverages the lower dimensionality of the input space. [sent-144, score-0.075]

57 When the Gaussian kernel is used, GURLS and LS-SVM have comparable computing time and classiﬁcation performance. [sent-145, score-0.029]

58 The interesting results obtained with the random features implementation in GURLS, make it an interesting choice in many applications. [sent-147, score-0.04]

59 Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. [sent-166, score-0.021]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('gurls', 0.888), ('bgurls', 0.148), ('rls', 0.106), ('tacchetti', 0.099), ('library', 0.077), ('optdigit', 0.074), ('pavan', 0.074), ('pendigit', 0.074), ('pipelines', 0.074), ('big', 0.069), ('rbf', 0.067), ('matteo', 0.063), ('santoro', 0.063), ('genova', 0.057), ('rosasco', 0.057), ('matlab', 0.057), ('modules', 0.053), ('allapragada', 0.049), ('gurlscore', 0.049), ('landsat', 0.049), ('mallapragada', 0.049), ('rifkin', 0.049), ('primal', 0.046), ('squares', 0.046), ('libsvm', 0.044), ('quares', 0.042), ('antoro', 0.042), ('bsd', 0.042), ('manager', 0.042), ('rahimi', 0.042), ('routines', 0.042), ('tasks', 0.041), ('features', 0.04), ('ram', 0.038), ('east', 0.038), ('suykens', 0.038), ('ibrary', 0.038), ('istituto', 0.038), ('italiano', 0.038), ('license', 0.038), ('lorenzo', 0.038), ('tecnologia', 0.038), ('options', 0.036), ('andrea', 0.035), ('upervised', 0.035), ('task', 0.034), ('isolet', 0.033), ('pipeline', 0.033), ('execution', 0.031), ('opt', 0.031), ('https', 0.031), ('italy', 0.031), ('memory', 0.031), ('store', 0.03), ('kernel', 0.029), ('regularized', 0.028), ('decided', 0.028), ('letter', 0.026), ('modular', 0.026), ('toolbox', 0.024), ('favorable', 0.024), ('distributed', 0.024), ('assessment', 0.023), ('guration', 0.023), ('software', 0.023), ('subsequent', 0.022), ('accuracy', 0.022), ('supervised', 0.022), ('currently', 0.022), ('massachusetts', 0.021), ('geoff', 0.021), ('appended', 0.021), ('dibris', 0.021), ('download', 0.021), ('grand', 0.021), ('holmes', 0.021), ('interchanged', 0.021), ('kitchen', 0.021), ('lrosasco', 0.021), ('mcgovern', 0.021), ('mpi', 0.021), ('pinto', 0.021), ('server', 0.021), ('tomaso', 0.021), ('suited', 0.02), ('splitting', 0.02), ('laboratory', 0.02), ('di', 0.019), ('interface', 0.019), ('executing', 0.019), ('sinks', 0.019), ('moor', 0.019), ('chunks', 0.019), ('brabanter', 0.019), ('modularity', 0.019), ('degli', 0.019), ('dodecaneso', 0.019), ('morego', 0.019), ('studi', 0.019), ('ubuntu', 0.019)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999976 46 jmlr-2013-GURLS: A Least Squares Library for Supervised Learning

Author: Andrea Tacchetti, Pavan K. Mallapragada, Matteo Santoro, Lorenzo Rosasco

2 0.063111492 76 jmlr-2013-Nonparametric Sparsity and Regularization

Author: Lorenzo Rosasco, Silvia Villa, Sofia Mosci, Matteo Santoro, Alessandro Verri

Abstract: In this work we are interested in the problems of supervised learning and variable selection when the input-output dependence is described by a nonlinear function depending on a few variables. Our goal is to consider a sparse nonparametric model, hence avoiding linear or additive models. The key idea is to measure the importance of each variable in the model by making use of partial derivatives. Based on this intuition we propose a new notion of nonparametric sparsity and a corresponding least squares regularization scheme. Using concepts and results from the theory of reproducing kernel Hilbert spaces and proximal methods, we show that the proposed learning algorithm corresponds to a minimization problem which can be provably solved by an iterative procedure. The consistency properties of the obtained estimator are studied both in terms of prediction and selection performance. An extensive empirical analysis shows that the proposed method performs favorably with respect to the state-of-the-art methods. Keywords: sparsity, nonparametric, variable selection, regularization, proximal methods, RKHS ∗. Also at Istituto Italiano di Tecnologia, Via Morego 30, 16163 Genova, Italy and Massachusetts Institute of Technology, Bldg. 46-5155, 77 Massachusetts Avenue, Cambridge, MA 02139, USA. c 2013 Lorenzo Rosasco, Silvia Villa, Soﬁa Mosci, Matteo Santoro and Alessandro Verri. ROSASCO , V ILLA , M OSCI , S ANTORO AND V ERRI

3 0.042339582 54 jmlr-2013-JKernelMachines: A Simple Framework for Kernel Machines

Author: David Picard, Nicolas Thome, Matthieu Cord

Abstract: JKernelMachines is a Java library for learning with kernels. It is primarily designed to deal with custom kernels that are not easily found in standard libraries, such as kernels on structured data. These types of kernels are often used in computer vision or bioinformatics applications. We provide several kernels leading to state of the art classiﬁcation performances in computer vision, as well as various kernels on sets. The main focus of the library is to be easily extended with new kernels. Standard SVM optimization algorithms are available, but also more sophisticated learning-based kernel combination methods such as Multiple Kernel Learning (MKL), and a recently published algorithm to learn powered products of similarities (Product Kernel Learning). Keywords: classiﬁcation, support vector machines, kernel, computer vision

4 0.039423574 112 jmlr-2013-Tapkee: An Efficient Dimension Reduction Library

Author: Sergey Lisitsyn, Christian Widmer, Fernando J. Iglesias Garcia

Abstract: We present Tapkee, a C++ template library that provides efﬁcient implementations of more than 20 widely used dimensionality reduction techniques ranging from Locally Linear Embedding (Roweis and Saul, 2000) and Isomap (de Silva and Tenenbaum, 2002) to the recently introduced BarnesHut-SNE (van der Maaten, 2013). Our library was designed with a focus on performance and ﬂexibility. For performance, we combine efﬁcient multi-core algorithms, modern data structures and state-of-the-art low-level libraries. To achieve ﬂexibility, we designed a clean interface for applying methods to user data and provide a callback API that facilitates integration with the library. The library is freely available as open-source software and is distributed under the permissive BSD 3-clause license. We encourage the integration of Tapkee into other open-source toolboxes and libraries. For example, Tapkee has been integrated into the codebase of the Shogun toolbox (Sonnenburg et al., 2010), giving us access to a rich set of kernels, distance measures and bindings to common programming languages including Python, Octave, Matlab, R, Java, C#, Ruby, Perl and Lua. Source code, examples and documentation are available at http://tapkee.lisitsyn.me. Keywords: dimensionality reduction, machine learning, C++, open source software

5 0.037604619 19 jmlr-2013-BudgetedSVM: A Toolbox for Scalable SVM Approximations

Author: Nemanja Djuric, Liang Lan, Slobodan Vucetic, Zhuang Wang

Abstract: We present BudgetedSVM, an open-source C++ toolbox comprising highly-optimized implementations of recently proposed algorithms for scalable training of Support Vector Machine (SVM) approximators: Adaptive Multi-hyperplane Machines, Low-rank Linearization SVM, and Budgeted Stochastic Gradient Descent. BudgetedSVM trains models with accuracy comparable to LibSVM in time comparable to LibLinear, solving non-linear problems with millions of high-dimensional examples within minutes on a regular computer. We provide command-line and Matlab interfaces to BudgetedSVM, an efﬁcient API for handling large-scale, high-dimensional data sets, as well as detailed documentation to help developers use and further extend the toolbox. Keywords: non-linear classiﬁcation, large-scale learning, SVM, machine learning toolbox

6 0.027510282 67 jmlr-2013-MLPACK: A Scalable C++ Machine Learning Library

7 0.020331204 83 jmlr-2013-Orange: Data Mining Toolbox in Python

8 0.019469606 113 jmlr-2013-The CAM Software for Nonnegative Blind Source Separation in R-Java

9 0.017113866 56 jmlr-2013-Keep It Simple And Sparse: Real-Time Action Recognition

10 0.014935683 7 jmlr-2013-A Risk Comparison of Ordinary Least Squares vs Ridge Regression

11 0.014786636 29 jmlr-2013-Convex and Scalable Weakly Labeled SVMs

12 0.014500931 82 jmlr-2013-Optimally Fuzzy Temporal Memory

13 0.014183113 1 jmlr-2013-AC++Template-Based Reinforcement Learning Library: Fitting the Code to the Mathematics

14 0.014175267 109 jmlr-2013-Stress Functions for Nonlinear Dimension Reduction, Proximity Analysis, and Graph Drawing

15 0.013456589 70 jmlr-2013-Maximum Volume Clustering: A New Discriminative Clustering Approach

16 0.013387848 28 jmlr-2013-Construction of Approximation Spaces for Reinforcement Learning

17 0.01322744 72 jmlr-2013-Multi-Stage Multi-Task Feature Learning

18 0.012773145 111 jmlr-2013-Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows

19 0.012655729 52 jmlr-2013-How to Solve Classification and Regression Problems on High-Dimensional Data with a Supervised Extension of Slow Feature Analysis

20 0.01228919 99 jmlr-2013-Semi-Supervised Learning Using Greedy Max-Cut

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.066), (1, 0.01), (2, -0.041), (3, -0.02), (4, 0.029), (5, 0.02), (6, -0.029), (7, 0.012), (8, -0.014), (9, -0.114), (10, 0.081), (11, -0.123), (12, 0.07), (13, -0.008), (14, 0.048), (15, -0.146), (16, 0.047), (17, -0.031), (18, 0.109), (19, 0.049), (20, 0.067), (21, -0.118), (22, 0.037), (23, 0.083), (24, 0.039), (25, 0.056), (26, 0.01), (27, -0.081), (28, 0.068), (29, 0.2), (30, -0.017), (31, -0.098), (32, -0.046), (33, -0.012), (34, 0.088), (35, 0.074), (36, 0.099), (37, 0.096), (38, 0.022), (39, -0.179), (40, -0.095), (41, -0.208), (42, -0.195), (43, 0.238), (44, 0.082), (45, 0.079), (46, -0.054), (47, 0.07), (48, -0.186), (49, -0.14)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9523741 46 jmlr-2013-GURLS: A Least Squares Library for Supervised Learning

Author: Andrea Tacchetti, Pavan K. Mallapragada, Matteo Santoro, Lorenzo Rosasco

2 0.50102717 76 jmlr-2013-Nonparametric Sparsity and Regularization

Author: Lorenzo Rosasco, Silvia Villa, Sofia Mosci, Matteo Santoro, Alessandro Verri

3 0.35074294 112 jmlr-2013-Tapkee: An Efficient Dimension Reduction Library

Author: Sergey Lisitsyn, Christian Widmer, Fernando J. Iglesias Garcia

4 0.33830762 67 jmlr-2013-MLPACK: A Scalable C++ Machine Learning Library

Author: Ryan R. Curtin, James R. Cline, N. P. Slagle, William B. March, Parikshit Ram, Nishant A. Mehta, Alexander G. Gray

Abstract: MLPACK is a state-of-the-art, scalable, multi-platform C++ machine learning library released in late 2011 offering both a simple, consistent API accessible to novice users and high performance and ﬂexibility to expert users by leveraging modern features of C++. MLPACK provides cutting-edge algorithms whose benchmarks exhibit far better performance than other leading machine learning libraries. MLPACK version 1.0.3, licensed under the LGPL, is available at http://www.mlpack.org. Keywords: C++, dual-tree algorithms, machine learning software, open source software, largescale learning 1. Introduction and Goals Though several machine learning libraries are freely available online, few, if any, offer efﬁcient algorithms to the average user. For instance, the popular Weka toolkit (Hall et al., 2009) emphasizes ease of use but scales poorly; the distributed Apache Mahout library offers scalability at a cost of higher overhead (such as clusters and powerful servers often unavailable to the average user). Also, few libraries offer breadth; for instance, libsvm (Chang and Lin, 2011) and the Tilburg MemoryBased Learner (TiMBL) are highly scalable and accessible yet each offer only a single method. MLPACK, intended to be the machine learning analog to the general-purpose LAPACK linear algebra library, aims to combine efﬁciency and accessibility. Written in C++, MLPACK uses the highly efﬁcient Armadillo matrix library (Sanderson, 2010) and is freely available under the GNU Lesser General Public License (LGPL). Through the use of C++ templates, MLPACK both eliminates unnecessary copying of data sets and performs expression optimizations unavailable in other languages. Also, MLPACK is, to our knowledge, unique among existing libraries in using generic programming features of C++ to allow customization of the available machine learning methods without incurring performance penalties. c 2013 Ryan R. Curtin, James R. Cline, N. P. Slagle, William B. March, Parikshit Ram, Nishant A. Mehta and Alexander G. Gray. C URTIN , C LINE , S LAGLE , M ARCH , R AM , M EHTA AND G RAY In addition, users ranging from students to experts should ﬁnd the consistent, intuitive interface of MLPACK to be highly accessible. Finally, the source code provides references and comprehensive documentation. Four major goals of the development team of MLPACK are • • • • to implement scalable, fast machine learning algorithms, to design an intuitive, consistent, and simple API for non-expert users, to implement a variety of machine learning methods, and to provide cutting-edge machine learning algorithms unavailable elsewhere. This paper offers both an introduction to the simple and extensible API and a glimpse of the superior performance of the library. 2. Package Overview Each algorithm available in MLPACK features both a set of C++ library functions and a standalone command-line executable. Version 1.0.3 includes the following methods: • • • • • • • • • • • • • • nearest/furthest neighbor search with cover trees or kd-trees (k-nearest-neighbors) range search with cover trees or kd-trees Gaussian mixture models (GMMs) hidden Markov models (HMMs) LARS / Lasso regression k-means clustering fast hierarchical clustering (Euclidean MST calculation)1 (March et al., 2010) kernel PCA (and regular PCA) local coordinate coding1 (Yu et al., 2009) sparse coding using dictionary learning RADICAL (Robust, Accurate, Direct ICA aLgorithm) (Learned-Miller and Fisher, 2003) maximum variance unfolding (MVU) via LRSDP1 (Burer and Monteiro, 2003) the naive Bayes classiﬁer density estimation trees1 (Ram and Gray, 2011) The development team manages MLPACK with Subversion and the Trac bug reporting system, allowing easy downloads and simple bug reporting. The entire development process is transparent, so any interested user can easily contribute to the library. MLPACK can compile from source on Linux, Mac OS, and Windows; currently, different Linux distributions are reviewing MLPACK for inclusion in their package managers, which will allow users to install MLPACK without needing to compile from source. 3. A Consistent, Simple API MLPACK features a highly accessible API, both in style (such as consistent naming schemes and coding conventions) and ease of use (such as templated defaults), as well as stringent documentation standards. Consequently, a new user can execute algorithms out-of-the-box often with little or no adjustment to parameters, while the seasoned expert can expect extreme ﬂexibility in algorithmic 1. This algorithm is not available in any other comparable software package. 802 MLPACK: A S CALABLE C++ M ACHINE L EARNING L IBRARY Data Set wine cloud wine-qual isolet miniboone yp-msd corel covtype mnist randu MLPACK 0.0003 0.0069 0.0290 13.0197 20.2045 5430.0478 4.9716 14.3449 2719.8087 1020.9142 Weka 0.0621 0.1174 0.8868 213.4735 216.1469 >9000.0000 14.4264 45.9912 >9000.0000 2665.0921 Shogun 0.0277 0.5000 4.3617 37.6190 2351.4637 >9000.0000 555.9600 >9000.0000 3536.4477 >9000.0000 MATLAB 0.0021 0.0210 0.6465 46.9518 1088.1127 >9000.0000 60.8496 >9000.0000 4838.6747 1679.2893 mlpy 0.0025 0.3520 4.0431 52.0437 3219.2696 >9000.0000 209.5056 >9000.0000 5192.3586 >9000.0000 sklearn 0.0008 0.0192 0.1668 46.8016 714.2385 >9000.0000 160.4597 651.6259 5363.9650 8780.0176 Table 1: k-NN benchmarks (in seconds). Data Set UCI Name Size wine Wine 178x13 cloud Cloud 2048x10 wine-qual Wine Quality 6497x11 isolet ISOLET 7797x617 miniboone MiniBooNE 130064x50 Data Set UCI Name Size yp-msd YearPredictionMSD 515345x90 corel Corel 37749x32 covtype Covertype 581082x54 mnist N/A 70000x784 randu N/A 1000000x10 Table 2: Benchmark data set sizes. tuning. For example, the following line initializes an object which will perform the standard kmeans clustering in Euclidean space: KMeans

5 0.33256668 3 jmlr-2013-A Framework for Evaluating Approximation Methods for Gaussian Process Regression

Author: Krzysztof Chalupka, Christopher K. I. Williams, Iain Murray

Abstract: Gaussian process (GP) predictors are an important component of many Bayesian approaches to machine learning. However, even a straightforward implementation of Gaussian process regression (GPR) requires O(n2 ) space and O(n3 ) time for a data set of n examples. Several approximation methods have been proposed, but there is a lack of understanding of the relative merits of the different approximations, and in what situations they are most useful. We recommend assessing the quality of the predictions obtained as a function of the compute time taken, and comparing to standard baselines (e.g., Subset of Data and FITC). We empirically investigate four different approximation algorithms on four different prediction problems, and make our code available to encourage future comparisons. Keywords: Gaussian process regression, subset of data, FITC, local GP

6 0.30601394 19 jmlr-2013-BudgetedSVM: A Toolbox for Scalable SVM Approximations

7 0.28424361 54 jmlr-2013-JKernelMachines: A Simple Framework for Kernel Machines

8 0.2489599 109 jmlr-2013-Stress Functions for Nonlinear Dimension Reduction, Proximity Analysis, and Graph Drawing

9 0.20723163 115 jmlr-2013-Training Energy-Based Models for Time-Series Imputation

10 0.17944764 51 jmlr-2013-Greedy Sparsity-Constrained Optimization

11 0.17167306 40 jmlr-2013-Efficient Program Synthesis Using Constraint Satisfaction in Inductive Logic Programming

12 0.15307489 110 jmlr-2013-Sub-Local Constraint-Based Learning of Bayesian Networks Using A Joint Dependence Criterion

13 0.13463113 33 jmlr-2013-Dimension Independent Similarity Computation

14 0.13287154 14 jmlr-2013-Asymptotic Results on Adaptive False Discovery Rate Controlling Procedures Based on Kernel Estimators

15 0.12481412 82 jmlr-2013-Optimally Fuzzy Temporal Memory

16 0.12010875 7 jmlr-2013-A Risk Comparison of Ordinary Least Squares vs Ridge Regression

17 0.11500935 25 jmlr-2013-Communication-Efficient Algorithms for Statistical Optimization

18 0.11044743 52 jmlr-2013-How to Solve Classification and Regression Problems on High-Dimensional Data with a Supervised Extension of Slow Feature Analysis

19 0.10906926 44 jmlr-2013-Finding Optimal Bayesian Networks Using Precedence Constraints

20 0.10453913 30 jmlr-2013-Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.024), (5, 0.11), (6, 0.02), (10, 0.067), (20, 0.023), (23, 0.042), (35, 0.343), (44, 0.032), (68, 0.018), (70, 0.014), (75, 0.043), (85, 0.014), (87, 0.079), (93, 0.043)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.69945925 46 jmlr-2013-GURLS: A Least Squares Library for Supervised Learning

Author: Andrea Tacchetti, Pavan K. Mallapragada, Matteo Santoro, Lorenzo Rosasco

2 0.41958612 116 jmlr-2013-Truncated Power Method for Sparse Eigenvalue Problems

Author: Xiao-Tong Yuan, Tong Zhang

Abstract: This paper considers the sparse eigenvalue problem, which is to extract dominant (largest) sparse eigenvectors with at most k non-zero components. We propose a simple yet effective solution called truncated power method that can approximately solve the underlying nonconvex optimization problem. A strong sparse recovery result is proved for the truncated power method, and this theory is our key motivation for developing the new algorithm. The proposed method is tested on applications such as sparse principal component analysis and the densest k-subgraph problem. Extensive experiments on several synthetic and real-world data sets demonstrate the competitive empirical performance of our method. Keywords: sparse eigenvalue, power method, sparse principal component analysis, densest k-subgraph

3 0.40638006 76 jmlr-2013-Nonparametric Sparsity and Regularization

Author: Lorenzo Rosasco, Silvia Villa, Sofia Mosci, Matteo Santoro, Alessandro Verri

4 0.39209548 121 jmlr-2013-Variational Inference in Nonconjugate Models

Author: Chong Wang, David M. Blei

Abstract: Mean-ﬁeld variational methods are widely used for approximate posterior inference in many probabilistic models. In a typical application, mean-ﬁeld methods approximately compute the posterior with a coordinate-ascent optimization algorithm. When the model is conditionally conjugate, the coordinate updates are easily derived and in closed form. However, many models of interest—like the correlated topic model and Bayesian logistic regression—are nonconjugate. In these models, mean-ﬁeld methods cannot be directly applied and practitioners have had to develop variational algorithms on a case-by-case basis. In this paper, we develop two generic methods for nonconjugate models, Laplace variational inference and delta method variational inference. Our methods have several advantages: they allow for easily derived variational algorithms with a wide class of nonconjugate models; they extend and unify some of the existing algorithms that have been derived for speciﬁc models; and they work well on real-world data sets. We studied our methods on the correlated topic model, Bayesian logistic regression, and hierarchical Bayesian logistic regression. Keywords: variational inference, nonconjugate models, Laplace approximations, the multivariate delta method

5 0.39160362 59 jmlr-2013-Large-scale SVD and Manifold Learning

Author: Ameet Talwalkar, Sanjiv Kumar, Mehryar Mohri, Henry Rowley

Abstract: This paper examines the efﬁcacy of sampling-based low-rank approximation techniques when applied to large dense kernel matrices. We analyze two common approximate singular value decomposition techniques, namely the Nystr¨ m and Column sampling methods. We present a theoretical o comparison between these two methods, provide novel insights regarding their suitability for various tasks and present experimental results that support our theory. Our results illustrate the relative strengths of each method. We next examine the performance of these two techniques on the largescale task of extracting low-dimensional manifold structure given millions of high-dimensional face images. We address the computational challenges of non-linear dimensionality reduction via Isomap and Laplacian Eigenmaps, using a graph containing about 18 million nodes and 65 million edges. We present extensive experiments on learning low-dimensional embeddings for two large face data sets: CMU-PIE (35 thousand faces) and a web data set (18 million faces). Our comparisons show that the Nystr¨ m approximation is superior to the Column sampling method for this o task. Furthermore, approximate Isomap tends to perform better than Laplacian Eigenmaps on both clustering and classiﬁcation with the labeled CMU-PIE data set. Keywords: low-rank approximation, manifold learning, large-scale matrix factorization

6 0.39046073 52 jmlr-2013-How to Solve Classification and Regression Problems on High-Dimensional Data with a Supervised Extension of Slow Feature Analysis

7 0.38799027 25 jmlr-2013-Communication-Efficient Algorithms for Statistical Optimization

8 0.38639027 48 jmlr-2013-Generalized Spike-and-Slab Priors for Bayesian Group Feature Selection Using Expectation Propagation

9 0.38421527 50 jmlr-2013-Greedy Feature Selection for Subspace Clustering

10 0.38237333 47 jmlr-2013-Gaussian Kullback-Leibler Approximate Inference

11 0.38108975 28 jmlr-2013-Construction of Approximation Spaces for Reinforcement Learning

12 0.38074484 105 jmlr-2013-Sparsity Regret Bounds for Individual Sequences in Online Linear Regression

13 0.37939259 86 jmlr-2013-Parallel Vector Field Embedding

14 0.37664673 72 jmlr-2013-Multi-Stage Multi-Task Feature Learning

15 0.37654501 5 jmlr-2013-A Near-Optimal Algorithm for Differentially-Private Principal Components

16 0.37613863 4 jmlr-2013-A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion

17 0.37411085 43 jmlr-2013-Fast MCMC Sampling for Markov Jump Processes and Extensions

18 0.37387675 73 jmlr-2013-Multicategory Large-Margin Unified Machines

19 0.37288064 102 jmlr-2013-Sparse Matrix Inversion with Scaled Lasso

20 0.3728174 3 jmlr-2013-A Framework for Evaluating Approximation Methods for Gaussian Process Regression