jmlr jmlr2012 jmlr2012-75 knowledge-graph by maker-knowledge-mining

75 jmlr-2012-NIMFA : A Python Library for Nonnegative Matrix Factorization

Source: pdf

Author: Marinka Žitnik, Blaž Zupan

Abstract: NIMFA is an open-source Python library that provides a uniﬁed interface to nonnegative matrix factorization algorithms. It includes implementations of state-of-the-art factorization methods, initialization approaches, and quality scoring. It supports both dense and sparse matrix representation. NIMFA’s component-based implementation and hierarchical design should help the users to employ already implemented techniques or design and code new strategies for matrix factorization tasks. Keywords: nonnegative matrix factorization, initialization methods, quality measures, scripting, Python

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 SI Faculty of Computer and Information Science University of Ljubljana SI-1000 Ljubljana, Trˇ aˇka 25, Slovenia z s Editor: Mikio Braun Abstract NIMFA is an open-source Python library that provides a uniﬁed interface to nonnegative matrix factorization algorithms. [sent-7, score-0.604]

2 It includes implementations of state-of-the-art factorization methods, initialization approaches, and quality scoring. [sent-8, score-0.535]

3 NIMFA’s component-based implementation and hierarchical design should help the users to employ already implemented techniques or design and code new strategies for matrix factorization tasks. [sent-10, score-0.432]

4 Keywords: nonnegative matrix factorization, initialization methods, quality measures, scripting, Python 1. [sent-11, score-0.332]

5 Introduction As a method to learn parts-based representation, a nonnegative matrix factorization (NMF) has become a popular approach for gaining new insights about complex latent relationships in highdimensional data through feature construction, selection and clustering. [sent-12, score-0.564]

6 NMF’s distinguishing feature is imposition of nonnegativity constraints, where only non-subtractive combinations of vectors in original space are allowed (Lee and Seung, 1999, 2001). [sent-15, score-0.047]

7 We have developed a Python-based NMF library called NIMFA which implements a wide variety of useful NMF operations and its components at a granular level. [sent-17, score-0.107]

8 Our aim was both to provide access to already published variants of NMF and ease the innovative use of its components in crafting new algorithms. [sent-18, score-0.025]

9 The library intentionally focuses on nonnegative variant of matrix factorization, and in terms of variety of different approaches compares favourably to several popular matrix factorization packages that are broader in scope (PyMF, (http://code. [sent-19, score-0.682]

10 Symbol + denotes full support, (+) partial support and symbol − no support. [sent-30, score-0.03]

11 Supported Factorization Methods and Approaches In a standard model of NMF (Lee and Seung, 2001), a data matrix V is factorized to V ≡ W H by solving a related optimization problem. [sent-33, score-0.083]

12 Nonnegative matrices W and H are commonly referred to as basis and mixture matrix, respectively. [sent-34, score-0.029]

13 NIMFA implements an originally proposed optimization (Lee and Seung, 2001; Brunet et al. [sent-35, score-0.039]

14 , 2004) with Euclidean or Kullback-Leibler cost function, along with Frobenius, divergence or connectivity costs. [sent-36, score-0.029]

15 It also supports alternative optimization algorithms including Bayesian NMF Gibbs sampler (Schmidt et al. [sent-37, score-0.03]

16 , 2008) and alternating least squares NMF using projected gradient method for subproblems (Lin, 2007). [sent-40, score-0.151]

17 Sparse matrix factorization is provided either through probabilistic (Dueck and Frey, 2004) or alternating nonnegativityconstrained least squares factorization (Kim and Park, 2007). [sent-41, score-0.851]

18 These comprise nonsmooth factorization V ≡ W S(θ) H (Pascual-Montano et al. [sent-48, score-0.39]

19 , 2006) and multiple model factorization for simultaneous treatment of several input matrices and their factorization with the same basis matrix W (Zhang et al. [sent-49, score-0.816]

20 All mentioned optimizations are incremental and start with initial approximation of matrices W and H. [sent-51, score-0.029]

21 Appropriate choice of initialization can greatly speed-up the convergence and increase the overall quality of the factorization results. [sent-52, score-0.51]

22 NIMFA contains implementations of popular initialization methods such as nonnegative double singular value decomposition (Boutsidis and Gallopoulos, 2007), random C and random Vcol algorithms (Albright et al. [sent-53, score-0.288]

23 User can also completely 850 NIMFA : A P YTHON L IBRARY FOR N ONNEGATIVE M ATRIX FACTORIZATION specify initial factorization by passing ﬁxed factors or choose any inexpensive method of randomly populated factors. [sent-55, score-0.386]

24 Factorization rank, choice of optimization method, and method-speciﬁc parameters jointly deﬁne the quality of approximation of input matrix V with the factorized system. [sent-56, score-0.13]

25 NIMFA provides a number of quality measures ranging from standard ones (e. [sent-57, score-0.047]

26 , Euclidean distance, Kullback-Leibler divergence, and sparseness) to those more speciﬁc like feature scoring representing speciﬁcity to basis vectors (Kim and Park, 2007). [sent-59, score-0.027]

27 Design and Implementation NIMFA has hierarchical, modular, and scalable structure which allows uniform treatment of numerous factorization models, their corresponding factorization algorithms and initialization methods. [sent-61, score-0.82]

28 The library enables easy integration into user’s code and arbitrary combinations of its factorization algorithms and their components. [sent-62, score-0.425]

29 seeding), supporting models for factorization, ﬁtted results, tracking and computation of quality and performance measures (nimfa. [sent-67, score-0.115]

30 models), and linear algebra helper routines for sparse and dense matrices (nimfa. [sent-68, score-0.077]

31 The library provides access to a set of standard data sets (nimfa. [sent-70, score-0.068]

32 examples stores scripts that demonstrate factorization-based analysis of these data sets and provide examples for various analytic approaches like factorization of sparse matrices, multiple factorization runs, and others. [sent-73, score-0.737]

33 Every block of the algorithms, like data preprocessing, initialization of matrix factors, overall optimization, stopping criteria and quality scoring may be selected from the library or deﬁned in a user-script, thus seamlessly enabling experimentation and construction of new approaches. [sent-75, score-0.323]

34 Optimization process may be monitored, tracking residuals across iterations or tracking ﬁtted factorization model. [sent-76, score-0.534]

35 NIMFA uses a popular Python matrix computation package NumPy for data management and representation. [sent-77, score-0.109]

36 A drawback of the library is that is holds matrix factors and ﬁtted model in main memory, raising an issue with very large data sets. [sent-78, score-0.172]

37 To address this, NIMFA fully supports computations with sparse matrices as implemented in SciPy. [sent-79, score-0.082]

38 An Example Script The sample script below demonstrates factorization of medulloblastoma gene expression data using alternating least squares NMF with projected gradient method for subproblems (Lin, 2007) and Random Vcol (Albright et al. [sent-81, score-0.627]

39 mf run is ﬁtted factorization model through which user can access matrix factors and estimate quality measures. [sent-84, score-0.483]

40 mf (V , seed = ’ random_vcol ’, method = ’ lsnmf ’, rank =40 , max_iter =65) fctr_res = nimfa . [sent-89, score-0.692]

41 evar ()) 851 ˇ Z ITNIK AND Z UPAN print ’K -L divergence : %5. [sent-96, score-0.19]

42 distance ( metric = ’kl ’) print ’ Sparseness , W: %5. [sent-98, score-0.074]

43 sparseness () Running this script produces the following output, where slight differences in reported scores across different runs can be attributed to randomness of the Random Vcol initialization method. [sent-102, score-0.232]

44 Availability and Requirements NIMFA is a Python-based package requiring SciPy version 0. [sent-109, score-0.031]

45 The latest version with documentation and working examples can be found at http://nimfa. [sent-113, score-0.027]

46 Algorithms, initializations, and convergence for the nonnegative matrix factorization. [sent-120, score-0.179]

47 SVD-based initialization: A head start for nonnegative matrix factorization. [sent-123, score-0.179]

48 Sparse non-negative matrix factorizations via alternating nonnegativity-constrained least squares for microarray data analysis. [sent-139, score-0.173]

49 Learning the parts of objects by non-negative matrix factorization. [sent-152, score-0.05]

50 A novel computational framework for simultaneous integration of multiple types of genomic data to identify microRNA-gene regulatory modules. [sent-184, score-0.023]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('nimfa', 0.692), ('factorization', 0.357), ('nmf', 0.333), ('nonnegative', 0.129), ('python', 0.108), ('initialization', 0.106), ('albright', 0.087), ('evar', 0.087), ('marinka', 0.087), ('pymf', 0.087), ('rss', 0.087), ('vcol', 0.087), ('zitnik', 0.087), ('print', 0.074), ('tracking', 0.068), ('library', 0.068), ('fit', 0.067), ('tted', 0.065), ('sparseness', 0.065), ('script', 0.061), ('bionmf', 0.058), ('brunet', 0.058), ('dueck', 0.058), ('fctr', 0.058), ('ibrary', 0.058), ('itnik', 0.058), ('medulloblastoma', 0.058), ('onnegative', 0.058), ('upan', 0.058), ('alternating', 0.055), ('seung', 0.051), ('matrix', 0.05), ('bla', 0.049), ('cichocki', 0.049), ('laurberg', 0.049), ('ython', 0.049), ('schmidt', 0.049), ('quality', 0.047), ('lars', 0.044), ('ljubljana', 0.044), ('zupan', 0.044), ('lj', 0.044), ('bioinformatics', 0.044), ('lee', 0.042), ('residuals', 0.041), ('boutsidis', 0.041), ('implements', 0.039), ('toronto', 0.038), ('subproblems', 0.036), ('factorizations', 0.036), ('atrix', 0.034), ('factorized', 0.033), ('nonsmooth', 0.033), ('park', 0.033), ('kim', 0.032), ('squares', 0.032), ('package', 0.031), ('sebastian', 0.03), ('symbol', 0.03), ('supports', 0.03), ('divergence', 0.029), ('factors', 0.029), ('zhang', 0.029), ('matrices', 0.029), ('projected', 0.028), ('popular', 0.028), ('fisher', 0.027), ('scoring', 0.027), ('documentation', 0.027), ('hierarchical', 0.025), ('implementations', 0.025), ('omaha', 0.025), ('huo', 0.025), ('lehmann', 0.025), ('imposition', 0.025), ('ka', 0.025), ('partsbased', 0.025), ('raising', 0.025), ('client', 0.025), ('scripting', 0.025), ('ltd', 0.025), ('andrzej', 0.025), ('slovenian', 0.025), ('christos', 0.025), ('crafting', 0.025), ('gallopoulos', 0.025), ('genomics', 0.025), ('helper', 0.025), ('kauai', 0.025), ('php', 0.025), ('plumbley', 0.025), ('seamlessly', 0.025), ('zdunek', 0.025), ('li', 0.025), ('sparse', 0.023), ('simultaneous', 0.023), ('uni', 0.023), ('nonnegativity', 0.022), ('jia', 0.022), ('crisp', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 75 jmlr-2012-NIMFA : A Python Library for Nonnegative Matrix Factorization

Author: Marinka Žitnik, Blaž Zupan

2 0.27084213 108 jmlr-2012-Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing

Author: Nicolas Gillis

Abstract: Nonnegative matrix factorization (NMF) has become a very popular technique in machine learning because it automatically extracts meaningful features through a sparse and part-based representation. However, NMF has the drawback of being highly ill-posed, that is, there typically exist many different but equivalent factorizations. In this paper, we introduce a completely new way to obtaining more well-posed NMF problems whose solutions are sparser. Our technique is based on the preprocessing of the nonnegative input data matrix, and relies on the theory of M-matrices and the geometric interpretation of NMF. This approach provably leads to optimal and sparse solutions under the separability assumption of Donoho and Stodden (2003), and, for rank-three matrices, makes the number of exact factorizations ﬁnite. We illustrate the effectiveness of our technique on several image data sets. Keywords: nonnegative matrix factorization, data preprocessing, uniqueness, sparsity, inversepositive matrices

3 0.059609868 88 jmlr-2012-PREA: Personalized Recommendation Algorithms Toolkit

Author: Joonseok Lee, Mingxuan Sun, Guy Lebanon

Abstract: Recommendation systems are important business applications with signiﬁcant economic impact. In recent years, a large number of algorithms have been proposed for recommendation systems. In this paper, we describe an open-source toolkit implementing many recommendation algorithms as well as popular evaluation metrics. In contrast to other packages, our toolkit implements recent state-of-the-art algorithms as well as most classic algorithms. Keywords: recommender systems, collaborative ﬁltering, evaluation metrics

4 0.057863012 90 jmlr-2012-Pattern for Python

Author: Tom De Smedt, Walter Daelemans

Abstract: Pattern is a package for Python 2.4+ with functionality for web mining (Google + Twitter + Wikipedia, web spider, HTML DOM parser), natural language processing (tagger/chunker, n-gram search, sentiment analysis, WordNet), machine learning (vector space model, k-means clustering, Naive Bayes + k-NN + SVM classiﬁers) and network analysis (graph centrality and visualization). It is well documented and bundled with 30+ examples and 350+ unit tests. The source code is licensed under BSD and available from http://www.clips.ua.ac.be/pages/pattern. Keywords: Python, data mining, natural language processing, machine learning, graph networks

5 0.048862521 101 jmlr-2012-SVDFeature: A Toolkit for Feature-based Collaborative Filtering

Author: Tianqi Chen, Weinan Zhang, Qiuxia Lu, Kailong Chen, Zhao Zheng, Yong Yu

Abstract: In this paper we introduce SVDFeature, a machine learning toolkit for feature-based collaborative ﬁltering. SVDFeature is designed to efﬁciently solve the feature-based matrix factorization. The feature-based setting allows us to build factorization models incorporating side information such as temporal dynamics, neighborhood relationship, and hierarchical information. The toolkit is capable of both rate prediction and collaborative ranking, and is carefully designed for efﬁcient training on large-scale data set. Using this toolkit, we built solutions to win KDD Cup for two consecutive years. Keywords: large-scale collaborative ﬁltering, context-aware recommendation, ranking

6 0.035063129 30 jmlr-2012-DARWIN: A Framework for Machine Learning and Computer Vision Research and Development

7 0.02992022 31 jmlr-2012-DEAP: Evolutionary Algorithms Made Easy

8 0.028078718 50 jmlr-2012-Human Gesture Recognition on Product Manifolds

9 0.027264062 61 jmlr-2012-ML-Flex: A Flexible Toolbox for Performing Classification Analyses In Parallel

10 0.025452057 47 jmlr-2012-GPLP: A Local and Parallel Computation Toolbox for Gaussian Process Regression

11 0.025162289 43 jmlr-2012-Fast Approximation of Matrix Coherence and Statistical Leverage

12 0.024947813 33 jmlr-2012-Distance Metric Learning with Eigenvalue Optimization

13 0.024822213 83 jmlr-2012-Online Learning in the Embedded Manifold of Low-rank Matrices

14 0.024583677 106 jmlr-2012-Sign Language Recognition using Sub-Units

15 0.02305562 119 jmlr-2012-glm-ie: Generalised Linear Models Inference & Estimation Toolbox

16 0.022648063 11 jmlr-2012-A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models

17 0.020621095 99 jmlr-2012-Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise

18 0.020558449 79 jmlr-2012-Oger: Modular Learning Architectures For Large-Scale Sequential Processing

19 0.019066229 113 jmlr-2012-The huge Package for High-dimensional Undirected Graph Estimation in R

20 0.018152708 32 jmlr-2012-Discriminative Hierarchical Part-based Models for Human Parsing and Action Recognition

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.086), (1, 0.04), (2, 0.164), (3, -0.023), (4, -0.036), (5, 0.067), (6, 0.079), (7, -0.12), (8, 0.038), (9, -0.376), (10, -0.254), (11, -0.256), (12, 0.228), (13, -0.027), (14, 0.049), (15, -0.006), (16, -0.229), (17, 0.119), (18, 0.021), (19, 0.351), (20, 0.068), (21, -0.048), (22, -0.011), (23, -0.038), (24, -0.024), (25, -0.142), (26, -0.063), (27, 0.097), (28, 0.018), (29, 0.034), (30, 0.013), (31, 0.003), (32, -0.028), (33, 0.048), (34, 0.012), (35, -0.018), (36, -0.042), (37, -0.039), (38, -0.005), (39, -0.033), (40, 0.018), (41, 0.007), (42, 0.023), (43, -0.004), (44, 0.003), (45, -0.007), (46, 0.014), (47, 0.038), (48, 0.012), (49, -0.043)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97256529 75 jmlr-2012-NIMFA : A Python Library for Nonnegative Matrix Factorization

Author: Marinka Žitnik, Blaž Zupan

2 0.86244208 108 jmlr-2012-Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing

Author: Nicolas Gillis

3 0.23704465 88 jmlr-2012-PREA: Personalized Recommendation Algorithms Toolkit

Author: Joonseok Lee, Mingxuan Sun, Guy Lebanon

4 0.21691608 90 jmlr-2012-Pattern for Python

Author: Tom De Smedt, Walter Daelemans

5 0.18554527 83 jmlr-2012-Online Learning in the Embedded Manifold of Low-rank Matrices

Author: Uri Shalit, Daphna Weinshall, Gal Chechik

Abstract: When learning models that are represented in matrix forms, enforcing a low-rank constraint can dramatically improve the memory and run time complexity, while providing a natural regularization of the model. However, naive approaches to minimizing functions over the set of low-rank matrices are either prohibitively time consuming (repeated singular value decomposition of the matrix) or numerically unstable (optimizing a factored representation of the low-rank matrix). We build on recent advances in optimization over manifolds, and describe an iterative online learning procedure, consisting of a gradient step, followed by a second-order retraction back to the manifold. While the ideal retraction is costly to compute, and so is the projection operator that approximates it, we describe another retraction that can be computed efﬁciently. It has run time and memory complexity of O ((n + m)k) for a rank-k matrix of dimension m × n, when using an online procedure with rank-one gradients. We use this algorithm, L ORETA, to learn a matrix-form similarity measure over pairs of documents represented as high dimensional vectors. L ORETA improves the mean average precision over a passive-aggressive approach in a factorized model, and also improves over a full model trained on pre-selected features using the same memory requirements. We further adapt L ORETA to learn positive semi-deﬁnite low-rank matrices, providing an online algorithm for low-rank metric learning. L ORETA also shows consistent improvement over standard weakly supervised methods in a large (1600 classes and 1 million images, using ImageNet) multi-label image classiﬁcation task. Keywords: low rank, Riemannian manifolds, metric learning, retractions, multitask learning, online learning

6 0.14326672 30 jmlr-2012-DARWIN: A Framework for Machine Learning and Computer Vision Research and Development

7 0.14173588 101 jmlr-2012-SVDFeature: A Toolkit for Feature-based Collaborative Filtering

8 0.13403702 31 jmlr-2012-DEAP: Evolutionary Algorithms Made Easy

9 0.12214772 43 jmlr-2012-Fast Approximation of Matrix Coherence and Statistical Leverage

10 0.11259547 119 jmlr-2012-glm-ie: Generalised Linear Models Inference & Estimation Toolbox

11 0.11209602 52 jmlr-2012-Iterative Reweighted Algorithms for Matrix Rank Minimization

12 0.10926753 11 jmlr-2012-A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models

13 0.10691706 70 jmlr-2012-Multi-Assignment Clustering for Boolean Data

14 0.10406281 47 jmlr-2012-GPLP: A Local and Parallel Computation Toolbox for Gaussian Process Regression

15 0.095218092 102 jmlr-2012-Sally: A Tool for Embedding Strings in Vector Spaces

16 0.09500806 50 jmlr-2012-Human Gesture Recognition on Product Manifolds

17 0.087425254 112 jmlr-2012-Structured Sparsity via Alternating Direction Methods

18 0.08730153 79 jmlr-2012-Oger: Modular Learning Architectures For Large-Scale Sequential Processing

19 0.084538035 61 jmlr-2012-ML-Flex: A Flexible Toolbox for Performing Classification Analyses In Parallel

20 0.080895886 33 jmlr-2012-Distance Metric Learning with Eigenvalue Optimization

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.02), (8, 0.457), (21, 0.034), (26, 0.046), (27, 0.04), (29, 0.02), (49, 0.021), (56, 0.055), (57, 0.016), (69, 0.045), (75, 0.03), (92, 0.035), (96, 0.067)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.77519745 75 jmlr-2012-NIMFA : A Python Library for Nonnegative Matrix Factorization

Author: Marinka Žitnik, Blaž Zupan

2 0.2289108 98 jmlr-2012-Regularized Bundle Methods for Convex and Non-Convex Risks

Author: Trinh Minh Tri Do, Thierry Artières

Abstract: Machine learning is most often cast as an optimization problem. Ideally, one expects a convex objective function to rely on efﬁcient convex optimizers with nice guarantees such as no local optima. Yet, non-convexity is very frequent in practice and it may sometimes be inappropriate to look for convexity at any price. Alternatively one can decide not to limit a priori the modeling expressivity to models whose learning may be solved by convex optimization and rely on non-convex optimization algorithms. The main motivation of this work is to provide efﬁcient and scalable algorithms for non-convex optimization. We focus on regularized unconstrained optimization problems which cover a large number of modern machine learning problems such as logistic regression, conditional random ﬁelds, large margin estimation, etc. We propose a novel algorithm for minimizing a regularized objective that is able to handle convex and non-convex, smooth and non-smooth risks. The algorithm is based on the cutting plane technique and on the idea of exploiting the regularization term in the objective function. It may be thought as a limited memory extension of convex regularized bundle methods for dealing with convex and non convex risks. In case the risk is convex the algorithm is proved to converge to a stationary solution with accuracy ε with a rate O(1/λε) where λ is the regularization parameter of the objective function under the assumption of a Lipschitz empirical risk. In case the risk is not convex getting such a proof is more difﬁcult and requires a stronger and more disputable assumption. Yet we provide experimental results on artiﬁcial test problems, and on ﬁve standard and difﬁcult machine learning problems that are cast as convex and non-convex optimization problems that show how our algorithm compares well in practice with state of the art optimization algorithms. Keywords: optimization, non-convex, non-smooth, cutting plane, bundle method, regularized risk

3 0.21869186 43 jmlr-2012-Fast Approximation of Matrix Coherence and Statistical Leverage

Author: Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff

Abstract: The statistical leverage scores of a matrix A are the squared row-norms of the matrix containing its (top) left singular vectors and the coherence is the largest leverage score. These quantities are of interest in recently-popular problems such as matrix completion and Nystr¨ m-based low-rank o matrix approximation as well as in large-scale statistical data analysis applications more generally; moreover, they are of interest since they deﬁne the key structural nonuniformity that must be dealt with in developing fast randomized matrix algorithms. Our main result is a randomized algorithm that takes as input an arbitrary n × d matrix A, with n ≫ d, and that returns as output relative-error approximations to all n of the statistical leverage scores. The proposed algorithm runs (under assumptions on the precise values of n and d) in O(nd log n) time, as opposed to the O(nd 2 ) time required by the na¨ve algorithm that involves computing an orthogonal basis for the ı range of A. Our analysis may be viewed in terms of computing a relative-error approximation to an underconstrained least-squares approximation problem, or, relatedly, it may be viewed as an application of Johnson-Lindenstrauss type ideas. Several practically-important extensions of our basic result are also described, including the approximation of so-called cross-leverage scores, the extension of these ideas to matrices with n ≈ d, and the extension to streaming environments. Keywords: matrix coherence, statistical leverage, randomized algorithm

4 0.21718197 92 jmlr-2012-Positive Semidefinite Metric Learning Using Boosting-like Algorithms

Author: Chunhua Shen, Junae Kim, Lei Wang, Anton van den Hengel

Abstract: The success of many machine learning and pattern recognition methods relies heavily upon the identiﬁcation of an appropriate distance metric on the input data. It is often beneﬁcial to learn such a metric from the input training data, instead of using a default one such as the Euclidean distance. In this work, we propose a boosting-based technique, termed B OOST M ETRIC, for learning a quadratic Mahalanobis distance metric. Learning a valid Mahalanobis distance metric requires enforcing the constraint that the matrix parameter to the metric remains positive semideﬁnite. Semideﬁnite programming is often used to enforce this constraint, but does not scale well and is not easy to implement. B OOST M ETRIC is instead based on the observation that any positive semideﬁnite matrix can be decomposed into a linear combination of trace-one rank-one matrices. B OOST M ETRIC thus uses rank-one positive semideﬁnite matrices as weak learners within an efﬁcient and scalable boosting-based learning process. The resulting methods are easy to implement, efﬁcient, and can accommodate various types of constraints. We extend traditional boosting algorithms in that its weak learner is a positive semideﬁnite matrix with trace and rank being one rather than a classiﬁer or regressor. Experiments on various data sets demonstrate that the proposed algorithms compare favorably to those state-of-the-art methods in terms of classiﬁcation accuracy and running time. Keywords: Mahalanobis distance, semideﬁnite programming, column generation, boosting, Lagrange duality, large margin nearest neighbor

5 0.21304764 88 jmlr-2012-PREA: Personalized Recommendation Algorithms Toolkit

Author: Joonseok Lee, Mingxuan Sun, Guy Lebanon

6 0.21143633 85 jmlr-2012-Optimal Distributed Online Prediction Using Mini-Batches

7 0.21138385 103 jmlr-2012-Sampling Methods for the Nyström Method

8 0.21018201 11 jmlr-2012-A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models

9 0.20880002 65 jmlr-2012-MedLDA: Maximum Margin Supervised Topic Models

10 0.20792034 106 jmlr-2012-Sign Language Recognition using Sub-Units

11 0.20731449 50 jmlr-2012-Human Gesture Recognition on Product Manifolds

12 0.20508474 72 jmlr-2012-Multi-Target Regression with Rule Ensembles

13 0.20463583 77 jmlr-2012-Non-Sparse Multiple Kernel Fisher Discriminant Analysis

14 0.20378858 6 jmlr-2012-A Model of the Perception of Facial Expressions of Emotion by Humans: Research Overview and Perspectives

15 0.20330182 64 jmlr-2012-Manifold Identification in Dual Averaging for Regularized Stochastic Online Learning

16 0.20261961 66 jmlr-2012-Metric and Kernel Learning Using a Linear Transformation

17 0.20243454 45 jmlr-2012-Finding Recurrent Patterns from Continuous Sign Language Sentences for Automated Extraction of Signs

18 0.20239499 115 jmlr-2012-Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints

19 0.20201799 18 jmlr-2012-An Improved GLMNET for L1-regularized Logistic Regression

20 0.20176807 112 jmlr-2012-Structured Sparsity via Alternating Direction Methods