text:
increase to VC dimension, and compression via operating on geometric representations. This paper presents positive results on the latter approach and a first negative result on the former, through a systematic investigation of finite maximum classes. Simple arrangements of hyperplanes in hyperbolic space are shown to represent maximum classes, generalizing the corresponding Euclidean result. We show that sweeping a generic hyperplane across such arrangements forms an unlabeled compression scheme of size VC dimension and corresponds to a special case of peeling the one-inclusion graph, resolving a recent conjecture of Kuzmin & Warmuth. A bijection between finite maximum classes and certain arrangements of piecewise-linear (PL) hyperplanes in either a ball or Euclidean space is established. Finally we show that d-maximum classes corresponding to PL-hyperplane arrangements in Rd have cubical complexes homeomorphic to a d-ball, or equivalently complexes that are manifolds with boundary. A main result is that PL arrangements can be swept by a moving hyperplane to unlabeled d-compress any finite maximum class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary is that some d-maximal classes cannot be embedded into any maximum class of VC-dimension d+k, for any constant k. The construction of the PL sweeping involves Pachner moves on the one-inclusion graph, corresponding to moves of a hyperplane across the intersection of d other hyperplanes. This extends the well known Pachner moves for triangulations to cubical complexes.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1221–1261},
numpages = {41},
keywords = {hyperplane arrangements, one-inclusion graphs, sample compression, hyperbolic and piecewise-linear geometry}
}

@article{10.5555/2503308.2343685,
author = {Liu, Ji and Wonka, Peter and Ye, Jieping},
title = {A Multi-Stage Framework for Dantzig Selector and LASSO},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X ∈ Rn\texttimes{}m (m ≫ n) and a noisy observation vector y ∈ Rn satisfying y = Xβ* + ε where ε is the noise vector following a Gaussian distribution N(0,σ2I), 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 refines 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 β*, the risk of the oracle estimator Δ is independent of m and is much smaller than the first 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 √logmσ to C(s-N)1/p√logmσ 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, where the oracle solution is the projection of the observation vector y onto true features. 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. Finally, we extend this multi-stage procedure to the LASSO case.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1189–1219},
numpages = {31},
keywords = {Dantzig selector, LASSO, sparse signal recovery, multi-stage}
}

@article{10.5555/2503308.2343684,
author = {Chiang, David},
title = {Hope and Fear for Discriminative Training of Statistical Translation Models},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In machine translation, discriminative models have almost entirely supplanted the classical noisy-channel model, but are standardly trained using a method that is reliable only in low-dimensional spaces. Two strands of research have tried to adapt more scalable discriminative training methods to machine translation: the first uses log-linear probability models and either maximum likelihood or minimum risk, and the other uses linear models and large-margin methods. Here, we provide an overview of the latter. We compare several learning algorithms and describe in detail some novel extensions suited to properties of the translation task: no single correct output, a large space of structured outputs, and slow inference. We present experimental results on a large-scale Arabic-English translation task, demonstrating large gains in translation accuracy.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1159–1187},
numpages = {29},
keywords = {machine translation, structured prediction, large-margin methods, online learning, distributed computing}
}

@article{10.5555/2503308.2343683,
author = {Tsamardinos, Ioannis and Triantafillou, Sofia and Lagani, Vincenzo},
title = {Towards Integrative Causal Analysis of Heterogeneous Data Sets and Studies},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present methods able to predict the presence and strength of conditional and unconditional dependencies (correlations) between two variables Y and Z never jointly measured on the same samples, based on multiple data sets measuring a set of common variables. The algorithms are specializations of prior work on learning causal structures from overlapping variable sets. This problem has also been addressed in the field of statistical matching. The proposed methods are applied to a wide range of domains and are shown to accurately predict the presence of thousands of dependencies. Compared against prototypical statistical matching algorithms and within the scope of our experiments, the proposed algorithms make predictions that are better correlated with the sample estimates of the unknown parameters on test data ; this is particularly the case when the number of commonly measured variables is low.The enabling idea behind the methods is to induce one or all causal models that are simultaneously consistent with (fit) all available data sets and prior knowledge and reason with them. This allows constraints stemming from causal assumptions (e.g., Causal Markov Condition, Faithfulness) to propagate. Several methods have been developed based on this idea, for which we propose the unifying name Integrative Causal Analysis (INCA). A contrived example is presented demonstrating the theoretical potential to develop more general methods for co-analyzing heterogeneous data sets. The computational experiments with the novel methods provide evidence that causally-inspired assumptions such as Faithfulness often hold to a good degree of approximation in many real systems and could be exploited for statistical inference. Code, scripts, and data are available at www.mensxmachina.org.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1097–1157},
numpages = {61},
keywords = {statistical matching, causality, data fusion, integrative causal analysis, Bayesian networks, causal discovery, structural equation models, maximal ancestral graphs}
}

@article{10.5555/2503308.2343682,
author = {Biau, G\'{e}rard},
title = {Analysis of a Random Forests Model},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Random forests are a scheme proposed by Leo Breiman in the 2000's for building a predictor ensemble with a set of decision trees that grow in randomly selected subspaces of data. Despite growing interest and practical use, there has been little exploration of the statistical properties of random forests, and little is known about the mathematical forces driving the algorithm. In this paper, we offer an in-depth analysis of a random forests model suggested by Breiman (2004), which is very close to the original algorithm. We show in particular that the procedure is consistent and adapts to sparsity, in the sense that its rate of convergence depends only on the number of strong features and not on how many noise variables are present.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1063–1095},
numpages = {33},
keywords = {sparsity, rate of convergence, randomization, random forests, dimension reduction, consistency}
}

@article{10.5555/2503308.2343681,
author = {Zhao, Tuo and Liu, Han and Roeder, Kathryn and Lafferty, John and Wasserman, Larry},
title = {The Huge Package for High-Dimensional Undirected Graph Estimation in R},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We describe an R package named huge which provides easy-to-use functions for estimating high dimensional undirected graphs from data. This package implements recent results in the literature, including Friedman et al. (2007), Liu et al. (2009, 2012) and Liu et al. (2010). Compared with the existing graph estimation package glasso, the huge package provides extra features: (1) instead of using Fortan, it is written in C, which makes the code more portable and easier to modify; (2) besides fitting Gaussian graphical models, it also provides functions for fitting high dimensional semiparametric Gaussian copula models; (3) more functions like data-dependent model selection, data generation and graph visualization; (4) a minor convergence problem of the graphical lasso algorithm is corrected; (5) the package allows the user to apply both lossless and lossy screening rules to scale up large-scale problems, making a tradeoff between computational and statistical efficiency.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1059–1062},
numpages = {4},
keywords = {lossy screening, glasso, lossless screening, high-dimensional undirected graph estimation, semiparametric graph estimation, huge, data-dependent model selection}
}

@article{10.5555/2503308.2343680,
author = {Kim, Yongdai and Kwon, Sunghoon and Choi, Hosik},
title = {Consistent Model Selection Criteria on High Dimensions},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Asymptotic properties of model selection criteria for high-dimensional regression models are studied where the dimension of covariates is much larger than the sample size. Several sufficient conditions for model selection consistency are provided. Non-Gaussian error distributions are considered and it is shown that the maximal number of covariates for model selection consistency depends on the tail behavior of the error distribution. Also, sufficient conditions for model selection consistency are given when the variance of the noise is neither known nor estimated consistently. Results of simulation studies as well as real data analysis are given to illustrate that finite sample performances of consistent model selection criteria can be quite different.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1037–1057},
numpages = {21},
keywords = {regression, general information criteria, high dimension, model selection consistency}
}

@article{10.5555/2503308.2343679,
author = {Shen, Chunhua and Kim, Junae and Wang, Lei and Van Den Hengel, Anton},
title = {Positive Semidefinite Metric Learning Using Boosting-like Algorithms},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The success of many machine learning and pattern recognition methods relies heavily upon the identification of an appropriate distance metric on the input data. It is often beneficial 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 BOOSTMETRIC, 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 semidefinite. Semidefinite programming is often used to enforce this constraint, but does not scale well and is not easy to implement. BOOSTMETRIC is instead based on the observation that any positive semidefinite matrix can be decomposed into a linear combination of trace-one rank-one matrices. BOOSTMETRIC thus uses rank-one positive semidefinite matrices as weak learners within an efficient and scalable boosting-based learning process. The resulting methods are easy to implement, efficient, and can accommodate various types of constraints. We extend traditional boosting algorithms in that its weak learner is a positive semidefinite matrix with trace and rank being one rather than a classifier or regressor. Experiments on various data sets demonstrate that the proposed algorithms compare favorably to those state-of-the-art methods in terms of classification accuracy and running time.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1007–1036},
numpages = {30},
keywords = {boosting, column generation, Mahalanobis distance, semidefinite programming, Lagrange duality, large margin nearest neighbor}
}

@article{10.5555/2503308.2343678,
author = {Kumar, Sanjiv and Mohri, Mehryar and Talwalkar, Ameet},
title = {Sampling Methods for the Nystr\"{o}m Method},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The Nystr\"{o}m method is an efficient technique to generate low-rank matrix approximations and is used in several large-scale learning applications. A key aspect of this method is the procedure according to which columns are sampled from the original matrix. In this work, we explore the efficacy of a variety of fixed and adaptive sampling schemes. We also propose a family of ensemble-based sampling algorithms for the Nystr\"{o}m method. We report results of extensive experiments that provide a detailed comparison of various fixed and adaptive sampling techniques, and demonstrate the performance improvement associated with the ensemble Nystr\"{o}m method when used in conjunction with either fixed or adaptive sampling schemes. Corroborating these empirical findings, we present a theoretical analysis of the Nystr\"{o}m method, providing novel error bounds guaranteeing a better convergence rate of the ensemble Nystr\"{o}m method in comparison to the standard Nystr\"{o}m method.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {981–1006},
numpages = {26},
keywords = {low-rank approximation, nystr\"{o}m method, large-scale learning, ensemble methods}
}

@article{10.5555/2503308.2343677,
author = {Tahan, Gil and Rokach, Lior and Shahar, Yuval},
title = {Mal-ID: Automatic Malware Detection Using Common Segment Analysis and Meta-Features},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {This paper proposes several novel methods, based on machine learning, to detect malware in executable files without any need for preprocessing, such as unpacking or disassembling. The basic method (Mal-ID) is a new static (form-based) analysis methodology that uses common segment analysis in order to detect malware files. By using common segment analysis, Mal-ID is able to discard malware parts that originate from benign code. In addition, Mal-ID uses a new kind of feature, termed meta-feature, to better capture the properties of the analyzed segments. Rather than using the entire file, as is usually the case with machine learning based techniques, the new approach detects malware on the segment level. This study also introduces two Mal-ID extensions that improve the Mal-ID basic method in various aspects. We rigorously evaluated Mal-ID and its two extensions with more than ten performance measures, and compared them to the highly rated boosted decision tree method under identical settings. The evaluation demonstrated that Mal-ID and the two Mal-ID extensions outperformed the boosted decision tree method in almost all respects. In addition, the results indicated that by extracting meaningful features, it is sufficient to employ one simple detection rule for classifying executable files.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {949–979},
numpages = {31},
keywords = {supervised learning, malware detection, computer security, common segment analysis}
}

@article{10.5555/2188385.2343686,
author = {Rubinstein, Benjamin I. P. and Rubinstein, J. Hyam},
title = {A Geometric Approach to Sample Compression},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for a quarter century. While maximum classes (concept classes meeting Sauer's Lemma with equality) can be compressed, the compression of general concept classes reduces to compressing maximal classes (classes that cannot be expanded without increasing VC dimension). Two promising ways forward are: embedding maximal classes into maximum classes with at most a polynomial increase to VC dimension, and compression via operating on geometric representations. This paper presents positive results on the latter approach and a first negative result on the former, through a systematic investigation of finite maximum classes. Simple arrangements of hyperplanes in hyperbolic space are shown to represent maximum classes, generalizing the corresponding Euclidean result. We show that sweeping a generic hyperplane across such arrangements forms an unlabeled compression scheme of size VC dimension and corresponds to a special case of peeling the one-inclusion graph, resolving a recent conjecture of Kuzmin & Warmuth. A bijection between finite maximum classes and certain arrangements of piecewise-linear (PL) hyperplanes in either a ball or Euclidean space is established. Finally we show that d-maximum classes corresponding to PL-hyperplane arrangements in Rd have cubical complexes homeomorphic to a d-ball, or equivalently complexes that are manifolds with boundary. A main result is that PL arrangements can be swept by a moving hyperplane to unlabeled d-compress any finite maximum class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary is that some d-maximal classes cannot be embedded into any maximum class of VC-dimension d+k, for any constant k. The construction of the PL sweeping involves Pachner moves on the one-inclusion graph, corresponding to moves of a hyperplane across the intersection of d other hyperplanes. This extends the well known Pachner moves for triangulations to cubical complexes.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1221–1261},
numpages = {41},
keywords = {hyperplane arrangements, sample compression, one-inclusion graphs, hyperbolic and piecewise-linear geometry}
}

@article{10.5555/2188385.2343685,
author = {Liu, Ji and Wonka, Peter and Ye, Jieping},
title = {A Multi-Stage Framework for Dantzig Selector and LASSO},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X ∈ Rn\texttimes{}m (m ≫ n) and a noisy observation vector y ∈ Rn satisfying y = Xβ* + ε where ε is the noise vector following a Gaussian distribution N(0,σ2I), 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 refines 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 β*, the risk of the oracle estimator Δ is independent of m and is much smaller than the first 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 √logmσ to C(s-N)1/p√logmσ 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, where the oracle solution is the projection of the observation vector y onto true features. 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. Finally, we extend this multi-stage procedure to the LASSO case.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1189–1219},
numpages = {31},
keywords = {multi-stage, Dantzig selector, sparse signal recovery, LASSO}
}

@article{10.5555/2188385.2343684,
author = {Chiang, David},
title = {Hope and Fear for Discriminative Training of Statistical Translation Models},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {In machine translation, discriminative models have almost entirely supplanted the classical noisy-channel model, but are standardly trained using a method that is reliable only in low-dimensional spaces. Two strands of research have tried to adapt more scalable discriminative training methods to machine translation: the first uses log-linear probability models and either maximum likelihood or minimum risk, and the other uses linear models and large-margin methods. Here, we provide an overview of the latter. We compare several learning algorithms and describe in detail some novel extensions suited to properties of the translation task: no single correct output, a large space of structured outputs, and slow inference. We present experimental results on a large-scale Arabic-English translation task, demonstrating large gains in translation accuracy.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1159–1187},
numpages = {29},
keywords = {distributed computing, online learning, large-margin methods, structured prediction, machine translation}
}

@article{10.5555/2188385.2343683,
author = {Tsamardinos, Ioannis and Triantafillou, Sofia and Lagani, Vincenzo},
title = {Towards Integrative Causal Analysis of Heterogeneous Data Sets and Studies},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We present methods able to predict the presence and strength of conditional and unconditional dependencies (correlations) between two variables Y and Z never jointly measured on the same samples, based on multiple data sets measuring a set of common variables. The algorithms are specializations of prior work on learning causal structures from overlapping variable sets. This problem has also been addressed in the field of statistical matching. The proposed methods are applied to a wide range of domains and are shown to accurately predict the presence of thousands of dependencies. Compared against prototypical statistical matching algorithms and within the scope of our experiments, the proposed algorithms make predictions that are better correlated with the sample estimates of the unknown parameters on test data ; this is particularly the case when the number of commonly measured variables is low.The enabling idea behind the methods is to induce one or all causal models that are simultaneously consistent with (fit) all available data sets and prior knowledge and reason with them. This allows constraints stemming from causal assumptions (e.g., Causal Markov Condition, Faithfulness) to propagate. Several methods have been developed based on this idea, for which we propose the unifying name Integrative Causal Analysis (INCA). A contrived example is presented demonstrating the theoretical potential to develop more general methods for co-analyzing heterogeneous data sets. The computational experiments with the novel methods provide evidence that causally-inspired assumptions such as Faithfulness often hold to a good degree of approximation in many real systems and could be exploited for statistical inference. Code, scripts, and data are available at www.mensxmachina.org.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1097–1157},
numpages = {61},
keywords = {integrative causal analysis, statistical matching, data fusion, Bayesian networks, maximal ancestral graphs, causality, structural equation models, causal discovery}
}

@article{10.5555/2188385.2343682,
author = {Biau, G\'{e}rard},
title = {Analysis of a Random Forests Model},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Random forests are a scheme proposed by Leo Breiman in the 2000's for building a predictor ensemble with a set of decision trees that grow in randomly selected subspaces of data. Despite growing interest and practical use, there has been little exploration of the statistical properties of random forests, and little is known about the mathematical forces driving the algorithm. In this paper, we offer an in-depth analysis of a random forests model suggested by Breiman (2004), which is very close to the original algorithm. We show in particular that the procedure is consistent and adapts to sparsity, in the sense that its rate of convergence depends only on the number of strong features and not on how many noise variables are present.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1063–1095},
numpages = {33},
keywords = {randomization, sparsity, consistency, random forests, rate of convergence, dimension reduction}
}

@article{10.5555/2188385.2343681,
author = {Zhao, Tuo and Liu, Han and Roeder, Kathryn and Lafferty, John and Wasserman, Larry},
title = {The Huge Package for High-Dimensional Undirected Graph Estimation in R},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We describe an R package named huge which provides easy-to-use functions for estimating high dimensional undirected graphs from data. This package implements recent results in the literature, including Friedman et al. (2007), Liu et al. (2009, 2012) and Liu et al. (2010). Compared with the existing graph estimation package glasso, the huge package provides extra features: (1) instead of using Fortan, it is written in C, which makes the code more portable and easier to modify; (2) besides fitting Gaussian graphical models, it also provides functions for fitting high dimensional semiparametric Gaussian copula models; (3) more functions like data-dependent model selection, data generation and graph visualization; (4) a minor convergence problem of the graphical lasso algorithm is corrected; (5) the package allows the user to apply both lossless and lossy screening rules to scale up large-scale problems, making a tradeoff between computational and statistical efficiency.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1059–1062},
numpages = {4},
keywords = {lossless screening, data-dependent model selection, glasso, lossy screening, high-dimensional undirected graph estimation, huge, semiparametric graph estimation}
}

@article{10.5555/2188385.2343680,
author = {Kim, Yongdai and Kwon, Sunghoon and Choi, Hosik},
title = {Consistent Model Selection Criteria on High Dimensions},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Asymptotic properties of model selection criteria for high-dimensional regression models are studied where the dimension of covariates is much larger than the sample size. Several sufficient conditions for model selection consistency are provided. Non-Gaussian error distributions are considered and it is shown that the maximal number of covariates for model selection consistency depends on the tail behavior of the error distribution. Also, sufficient conditions for model selection consistency are given when the variance of the noise is neither known nor estimated consistently. Results of simulation studies as well as real data analysis are given to illustrate that finite sample performances of consistent model selection criteria can be quite different.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1037–1057},
numpages = {21},
keywords = {model selection consistency, general information criteria, regression, high dimension}
}

@article{10.5555/2188385.2343679,
author = {Shen, Chunhua and Kim, Junae and Wang, Lei and Van Den Hengel, Anton},
title = {Positive Semidefinite Metric Learning Using Boosting-like Algorithms},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The success of many machine learning and pattern recognition methods relies heavily upon the identification of an appropriate distance metric on the input data. It is often beneficial 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 BOOSTMETRIC, 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 semidefinite. Semidefinite programming is often used to enforce this constraint, but does not scale well and is not easy to implement. BOOSTMETRIC is instead based on the observation that any positive semidefinite matrix can be decomposed into a linear combination of trace-one rank-one matrices. BOOSTMETRIC thus uses rank-one positive semidefinite matrices as weak learners within an efficient and scalable boosting-based learning process. The resulting methods are easy to implement, efficient, and can accommodate various types of constraints. We extend traditional boosting algorithms in that its weak learner is a positive semidefinite matrix with trace and rank being one rather than a classifier or regressor. Experiments on various data sets demonstrate that the proposed algorithms compare favorably to those state-of-the-art methods in terms of classification accuracy and running time.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1007–1036},
numpages = {30},
keywords = {Mahalanobis distance, Lagrange duality, boosting, column generation, large margin nearest neighbor, semidefinite programming}
}

@article{10.5555/2188385.2343678,
author = {Kumar, Sanjiv and Mohri, Mehryar and Talwalkar, Ameet},
title = {Sampling Methods for the Nystr\"{o}m Method},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The Nystr\"{o}m method is an efficient technique to generate low-rank matrix approximations and is used in several large-scale learning applications. A key aspect of this method is the procedure according to which columns are sampled from the original matrix. In this work, we explore the efficacy of a variety of fixed and adaptive sampling schemes. We also propose a family of ensemble-based sampling algorithms for the Nystr\"{o}m method. We report results of extensive experiments that provide a detailed comparison of various fixed and adaptive sampling techniques, and demonstrate the performance improvement associated with the ensemble Nystr\"{o}m method when used in conjunction with either fixed or adaptive sampling schemes. Corroborating these empirical findings, we present a theoretical analysis of the Nystr\"{o}m method, providing novel error bounds guaranteeing a better convergence rate of the ensemble Nystr\"{o}m method in comparison to the standard Nystr\"{o}m method.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {981–1006},
numpages = {26},
keywords = {ensemble methods, nystr\"{o}m method, low-rank approximation, large-scale learning}
}

@article{10.5555/2188385.2343677,
author = {Tahan, Gil and Rokach, Lior and Shahar, Yuval},
title = {Mal-ID: Automatic Malware Detection Using Common Segment Analysis and Meta-Features},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {This paper proposes several novel methods, based on machine learning, to detect malware in executable files without any need for preprocessing, such as unpacking or disassembling. The basic method (Mal-ID) is a new static (form-based) analysis methodology that uses common segment analysis in order to detect malware files. By using common segment analysis, Mal-ID is able to discard malware parts that originate from benign code. In addition, Mal-ID uses a new kind of feature, termed meta-feature, to better capture the properties of the analyzed segments. Rather than using the entire file, as is usually the case with machine learning based techniques, the new approach detects malware on the segment level. This study also introduces two Mal-ID extensions that improve the Mal-ID basic method in various aspects. We rigorously evaluated Mal-ID and its two extensions with more than ten performance measures, and compared them to the highly rated boosted decision tree method under identical settings. The evaluation demonstrated that Mal-ID and the two Mal-ID extensions outperformed the boosted decision tree method in almost all respects. In addition, the results indicated that by extracting meaningful features, it is sufficient to employ one simple detection rule for classifying executable files.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {949–979},
numpages = {31},
keywords = {common segment analysis, supervised learning, computer security, malware detection}
}

@article{10.5555/2503308.2188416,
author = {Kir\'{a}ly, Franz J. and B\"{u}nau, Paul Von and Meinecke, Frank C. and Blythe, Duncan A. J. and M\"{u}ller, Klaus-Robert},
title = {Algebraic Geometric Comparison of Probability Distributions},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel algebraic algorithmic framework for dealing with probability distributions represented by their cumulants such as the mean and covariance matrix. As an example, we consider the unsupervised learning problem of finding the subspace on which several probability distributions agree. Instead of minimizing an objective function involving the estimated cumulants, we show that by treating the cumulants as elements of the polynomial ring we can directly solve the problem, at a lower computational cost and with higher accuracy. Moreover, the algebraic viewpoint on probability distributions allows us to invoke the theory of algebraic geometry, which we demonstrate in a compact proof for an identifiability criterion.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {855–903},
numpages = {49},
keywords = {unsupervised Learning, approximate algebra, computational algebraic geometry}
}

@article{10.5555/2503308.2188415,
author = {\v{Z}itnik, Marinka and Zupan, Bla\v{z}},
title = {NIMFA: A Python Library for Nonnegative Matrix Factorization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {NIMFA is an open-source Python library that provides a unified 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.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {849–853},
numpages = {5},
keywords = {nonnegative matrix factorization, initialization methods, scripting, quality measures, Python}
}

@article{10.5555/2503308.2188414,
author = {Ramsahai, Roland R.},
title = {Causal Bounds and Observable Constraints for Non-Deterministic Models},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Conditional independence relations involving latent variables do not necessarily imply observable independences. They may imply inequality constraints on observable parameters and causal bounds, which can be used for falsification and identification. The literature on computing such constraints often involve a deterministic underlying data generating process in a counterfactual framework. If an analyst is ignorant of the nature of the underlying mechanisms then they may wish to use a model which allows the underlying mechanisms to be probabilistic. A method of computation for a weaker model without any determinism is given here and demonstrated for the instrumental variable model, though applicable to other models. The approach is based on the analysis of mappings with convex polytopes in a decision theoretic framework and can be implemented in readily available polyhedral computation software. Well known constraints and bounds are replicated in a probabilistic model and novel ones are computed for instrumental variable models without non-deterministic versions of the randomization, exclusion restriction and monotonicity assumptions respectively.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {829–848},
numpages = {20},
keywords = {convex polytope, instrumental variables, directed acyclic graph, causal bounds, latent variables, instrumental inequality}
}

@article{10.5555/2503308.2188413,
author = {Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin},
title = {Algorithms for Learning Kernels Based on Centered Alignment},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {This paper presents new and effective algorithms for learning kernels. In particular, as shown by our empirical results, these algorithms consistently outperform the so-called uniform combination solution that has proven to be difficult to improve upon in the past, as well as other algorithms for learning kernels based on convex combinations of base kernels in both classification and regression. Our algorithms are based on the notion of centered alignment which is used as a similarity measure between kernels or kernel matrices. We present a number of novel algorithmic, theoretical, and empirical results for learning kernels based on our notion of centered alignment. In particular, we describe efficient algorithms for learning a maximum alignment kernel by showing that the problem can be reduced to a simple QP and discuss a one-stage algorithm for learning both a kernel and a hypothesis based on that kernel using an alignment-based regularization. Our theoretical results include a novel concentration bound for centered alignment between kernel matrices, the proof of the existence of effective predictors for kernels with high alignment, both for classification and for regression, and the proof of stability-based generalization bounds for a broad family of algorithms for learning kernels based on centered alignment. We also report the results of experiments with our centered alignment-based algorithms in both classification and regression.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {795–828},
numpages = {34},
keywords = {kernel methods, feature selection, learning kernels}
}

@article{10.5555/2503308.2188412,
author = {Mazumder, Rahul and Hastie, Trevor},
title = {Exact Covariance Thresholding into Connected Components for Large-Scale Graphical Lasso},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider the sparse inverse covariance regularization problem or graphical lasso with regularization parameter λ. Suppose the sample covariance graph formed by thresholding the entries of the sample covariance matrix at λ is decomposed into connected components. We show that the vertex-partition induced by the connected components of the thresholded sample covariance graph (at λ) is exactly equal to that induced by the connected components of the estimated concentration graph, obtained by solving the graphical lasso problem for the same λ. This characterizes a very interesting property of a path of graphical lasso solutions. Furthermore, this simple rule, when used as a wrapper around existing algorithms for the graphical lasso, leads to enormous performance gains. For a range of values of λ, our proposal splits a large graphical lasso problem into smaller tractable problems, making it possible to solve an otherwise infeasible large-scale problem. We illustrate the graceful scalability of our proposal via synthetic and real-life microarray examples.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {781–794},
numpages = {14},
keywords = {sparse inverse covariance selection, concentration graph, graphical lasso, large scale covariance estimation, Gaussian graphical models, graph connected components, sparsity}
}

@article{10.5555/2503308.2188411,
author = {Park, Chiwoo and Huang, Jianhua Z. and Ding, Yu},
title = {GPLP: A Local and Parallel Computation Toolbox for Gaussian Process Regression},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {This paper presents the Getting-started style documentation for the local and parallel computation toolbox for Gaussian process regression (GPLP), an open source software package written in Matlab (but also compatible with Octave). The working environment and the usage of the software package will be presented in this paper.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {775–779},
numpages = {5},
keywords = {Gaussian process regression, partial independent conditional, bagging for Gaussian process, domain decomposition method, local probabilistic regression}
}

@article{10.5555/2503308.2188410,
author = {Gretton, Arthur and Borgwardt, Karsten M. and Rasch, Malte J. and Sch\"{o}lkopf, Bernhard and Smola, Alexander},
title = {A Kernel Two-Sample Test},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We propose a framework for analyzing and comparing distributions, which we use to construct statistical tests to determine if two samples are drawn from different distributions. Our test statistic is the largest difference in expectations over functions in the unit ball of a reproducing kernel Hilbert space (RKHS), and is called the maximum mean discrepancy (MMD).We present two distribution free tests based on large deviation bounds for the MMD, and a third test based on the asymptotic distribution of this statistic. The MMD can be computed in quadratic time, although efficient linear time approximations are available. Our statistic is an instance of an integral probability metric, and various classical metrics on distributions are obtained when alternative function classes are used in place of an RKHS. We apply our two-sample tests to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where they perform strongly. Excellent performance is also obtained when comparing distributions over graphs, for which these are the first such tests.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {723–773},
numpages = {51},
keywords = {hypothesis testing, schema matching, kernel methods, two-sample test, integral probability metric, uniform convergence bounds}
}

@article{10.5555/2503308.2188409,
author = {Skolidis, Grigorios and Sanguinetti, Guido},
title = {A Case Study on Meta-Generalising: A Gaussian Processes Approach},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel model for meta-generalisation, that is, performing prediction on novel tasks based on information from multiple different but related tasks. The model is based on two coupled Gaussian processes with structured covariance function; one model performs predictions by learning a constrained covariance function encapsulating the relations between the various training tasks, while the second model determines the similarity of new tasks to previously seen tasks. We demonstrate empirically on several real and synthetic data sets both the strengths of the approach and its limitations due to the distributional assumptions underpinning it.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {691–721},
numpages = {31},
keywords = {meta-generalising, mixture of experts, multi-task learning, Gaussian processes, transfer learning}
}

@article{10.5555/2503308.2188408,
author = {Maurer, Andreas and Pontil, Massimiliano},
title = {Structured Sparsity and Generalization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present a data dependent generalization bound for a large class of regularized algorithms which implement structured sparsity constraints. The bound can be applied to standard squared-norm regularization, the Lasso, the group Lasso, some versions of the group Lasso with overlapping groups, multiple kernel learning and other regularization schemes. In all these cases competitive results are obtained. A novel feature of our bound is that it can be applied in an infinite dimensional setting such as the Lasso in a separable Hilbert space or multiple kernel learning with a countable number of kernels.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {671–690},
numpages = {20},
keywords = {Rademacher average, sparse estimation, empirical processes}
}

@article{10.5555/2503308.2188407,
author = {Larochelle, Hugo and Mandel, Michael and Pascanu, Razvan and Bengio, Yoshua},
title = {Learning Algorithms for the Classification Restricted Boltzmann Machine},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Recent developments have demonstrated the capacity of restricted Boltzmann machines (RBM) to be powerful generative models, able to extract useful features from input data or construct deep artificial neural networks. In such settings, the RBM only yields a preprocessing or an initialization for some other model, instead of acting as a complete supervised model in its own right. In this paper, we argue that RBMs can provide a self-contained framework for developing competitive classifiers. We study the Classification RBM (ClassRBM), a variant on the RBM adapted to the classification setting. We study different strategies for training the ClassRBM and show that competitive classification performances can be reached when appropriately combining discriminative and generative training objectives. Since training according to the generative objective requires the computation of a generally intractable gradient, we also compare different approaches to estimating this gradient and address the issue of obtaining such a gradient for problems with very high dimensional inputs. Finally, we describe how to adapt the ClassRBM to two special cases of classification problems, namely semi-supervised and multitask learning.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {643–669},
numpages = {27},
keywords = {classification, restricted Boltzmannmachine, generative learning, discriminative learning}
}

@article{10.5555/2503308.2188406,
author = {Yan, Fei and Kittler, Josef and Mikolajczyk, Krystian and Tahir, Atif},
title = {Non-Sparse Multiple Kernel Fisher Discriminant Analysis},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Sparsity-inducing multiple kernel Fisher discriminant analysis (MK-FDA) has been studied in the literature. Building on recent advances in non-sparse multiple kernel learning (MKL), we propose a non-sparse version of MK-FDA, which imposes a general lp norm regularisation on the kernel weights. We formulate the associated optimisation problem as a semi-infinite program (SIP), and adapt an iterative wrapper algorithm to solve it. We then discuss, in light of latest advances in MKL optimisation techniques, several reformulations and optimisation strategies that can potentially lead to significant improvements in the efficiency and scalability of MK-FDA. We carry out extensive experiments on six datasets from various application areas, and compare closely the performance of lp MK-FDA, fixed norm MK-FDA, and several variants of SVM-based MKL (MK-SVM). Our results demonstrate that lp MK-FDA improves upon sparse MK-FDA in many practical situations. The results also show that on image categorisation problems, lp MK-FDA tends to outperform its SVM counterpart. Finally, we also discuss the connection between (MK-)FDA and (MK-)SVM, under the unified framework of regularised kernel machines.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {607–642},
numpages = {36},
keywords = {regularised least squares, kernel fisher discriminant analysis, support vector machines, multiple kernel learning}
}

@article{10.5555/2503308.2188405,
author = {Telgarsky, Matus},
title = {A Primal-Dual Convergence Analysis of Boosting},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Boosting combines weak learners into a predictor with low empirical risk. Its dual constructs a high entropy distribution upon which weak learners and training labels are uncorrelated. This manuscript studies this primal-dual relationship under a broad family of losses, including the exponential loss of AdaBoost and the logistic loss, revealing: • Weak learnability aids the whole loss family: for any ε > 0, O(ln(1/ε)) iterations suffice to produce a predictor with empirical risk ε-close to the infimum; • The circumstances granting the existence of an empirical risk minimizer may be characterized in terms of the primal and dual problems, yielding a new proof of the known rate O(ln(1/ε)); • Arbitrary instances may be decomposed into the above two, granting rate O(1/ε), with a matching lower bound provided for the logistic loss.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {561–606},
numpages = {46},
keywords = {weak learnability, boosting, coordinate descent, convex analysis, maximum entropy}
}

@article{10.5555/2503308.2188404,
author = {Piccolo, Stephen R. and Frey, Lewis J.},
title = {ML-Flex: A Flexible Toolbox for Performing Classification Analyses in Parallel},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Motivated by a need to classify high-dimensional, heterogeneous data from the bioinformatics domain, we developed ML-Flex, a machine-learning toolbox that enables users to perform two-class and multi-class classification analyses in a systematic yet flexible manner. ML-Flex was written in Java but is capable of interfacing with third-party packages written in other programming languages. It can handle multiple input-data formats and supports a variety of customizations. MLFlex provides implementations of various validation strategies, which can be executed in parallel across multiple computing cores, processors, and nodes. Additionally, ML-Flex supports aggregating evidence across multiple algorithms and data sets via ensemble learning. This open-source software package is freely available from http://mlflex.sourceforge.net.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {555–559},
numpages = {5},
keywords = {reproducible research, parallel, toolbox, ensemble, classification}
}

@article{10.5555/2503308.2188403,
author = {Benbouzid, Djalel and Busa-Fekete, R\'{o}bert and Casagrande, Norman and Collin, Fran\c{c}ois-David and K\'{e}gl, Bal\'{a}zs},
title = {MULTIBOOST: A Multi-Purpose Boosting Package},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The MULTIBOOST package provides a fast C++ implementation of multi-class/multi-label/multitask boosting algorithms. It is based on ADABOOST.MH but it also implements popular cascade classifiers and FILTERBOOST. The package contains common multi-class base learners (stumps, trees, products, Haar filters). Further base learners and strong learners following the boosting paradigm can be easily implemented in a flexible framework.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {549–553},
numpages = {5},
keywords = {FILTERBOOST, boosting, cascade classifier, ADABOOST.MH}
}

@article{10.5555/2503308.2188402,
author = {Jain, Prateek and Kulis, Brian and Davis, Jason V. and Dhillon, Inderjit S.},
title = {Metric and Kernel Learning Using a Linear Transformation},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Metric and kernel learning arise in several machine learning applications. However, most existing metric learning algorithms are limited to learning metrics over low-dimensional data, while existing kernel learning algorithms are often limited to the transductive setting and do not generalize to new data points. In this paper, we study the connections between metric learning and kernel learning that arise when studying metric learning as a linear transformation learning problem. In particular, we propose a general optimization framework for learning metrics via linear transformations, and analyze in detail a special case of our framework-that of minimizing the LogDet divergence subject to linear constraints. We then propose a general regularized framework for learning a kernel matrix, and show it to be equivalent to our metric learning framework. Our theoretical connections between metric and kernel learning have two main consequences: 1) the learned kernel matrix parameterizes a linear transformation kernel function and can be applied inductively to new data points, 2) our result yields a constructive method for kernelizing most existing Mahalanobis metric learning formulations. We demonstrate our learning approach by applying it to large-scale real world problems in computer vision, text mining and semi-supervised kernel dimensionality reduction.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {519–547},
numpages = {29},
keywords = {linear transformation, metric learning, kernel learning, matrix divergences, logdet divergence}
}

@article{10.5555/2188385.2188416,
author = {Kir\'{a}ly, Franz J. and B\"{u}nau, Paul Von and Meinecke, Frank C. and Blythe, Duncan A. J. and M\"{u}ller, Klaus-Robert},
title = {Algebraic Geometric Comparison of Probability Distributions},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We propose a novel algebraic algorithmic framework for dealing with probability distributions represented by their cumulants such as the mean and covariance matrix. As an example, we consider the unsupervised learning problem of finding the subspace on which several probability distributions agree. Instead of minimizing an objective function involving the estimated cumulants, we show that by treating the cumulants as elements of the polynomial ring we can directly solve the problem, at a lower computational cost and with higher accuracy. Moreover, the algebraic viewpoint on probability distributions allows us to invoke the theory of algebraic geometry, which we demonstrate in a compact proof for an identifiability criterion.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {855–903},
numpages = {49},
keywords = {unsupervised Learning, computational algebraic geometry, approximate algebra}
}

@article{10.5555/2188385.2188415,
author = {\v{Z}itnik, Marinka and Zupan, Bla\v{z}},
title = {NIMFA: A Python Library for Nonnegative Matrix Factorization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {NIMFA is an open-source Python library that provides a unified 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.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {849–853},
numpages = {5},
keywords = {quality measures, nonnegative matrix factorization, scripting, Python, initialization methods}
}

@article{10.5555/2188385.2188414,
author = {Ramsahai, Roland R.},
title = {Causal Bounds and Observable Constraints for Non-Deterministic Models},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Conditional independence relations involving latent variables do not necessarily imply observable independences. They may imply inequality constraints on observable parameters and causal bounds, which can be used for falsification and identification. The literature on computing such constraints often involve a deterministic underlying data generating process in a counterfactual framework. If an analyst is ignorant of the nature of the underlying mechanisms then they may wish to use a model which allows the underlying mechanisms to be probabilistic. A method of computation for a weaker model without any determinism is given here and demonstrated for the instrumental variable model, though applicable to other models. The approach is based on the analysis of mappings with convex polytopes in a decision theoretic framework and can be implemented in readily available polyhedral computation software. Well known constraints and bounds are replicated in a probabilistic model and novel ones are computed for instrumental variable models without non-deterministic versions of the randomization, exclusion restriction and monotonicity assumptions respectively.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {829–848},
numpages = {20},
keywords = {convex polytope, latent variables, causal bounds, instrumental variables, instrumental inequality, directed acyclic graph}
}

@article{10.5555/2188385.2188413,
author = {Cortes, Corinna and Mohri, Mehryar and Rostamizadeh, Afshin},
title = {Algorithms for Learning Kernels Based on Centered Alignment},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {This paper presents new and effective algorithms for learning kernels. In particular, as shown by our empirical results, these algorithms consistently outperform the so-called uniform combination solution that has proven to be difficult to improve upon in the past, as well as other algorithms for learning kernels based on convex combinations of base kernels in both classification and regression. Our algorithms are based on the notion of centered alignment which is used as a similarity measure between kernels or kernel matrices. We present a number of novel algorithmic, theoretical, and empirical results for learning kernels based on our notion of centered alignment. In particular, we describe efficient algorithms for learning a maximum alignment kernel by showing that the problem can be reduced to a simple QP and discuss a one-stage algorithm for learning both a kernel and a hypothesis based on that kernel using an alignment-based regularization. Our theoretical results include a novel concentration bound for centered alignment between kernel matrices, the proof of the existence of effective predictors for kernels with high alignment, both for classification and for regression, and the proof of stability-based generalization bounds for a broad family of algorithms for learning kernels based on centered alignment. We also report the results of experiments with our centered alignment-based algorithms in both classification and regression.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {795–828},
numpages = {34},
keywords = {kernel methods, learning kernels, feature selection}
}

@article{10.5555/2188385.2188412,
author = {Mazumder, Rahul and Hastie, Trevor},
title = {Exact Covariance Thresholding into Connected Components for Large-Scale Graphical Lasso},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We consider the sparse inverse covariance regularization problem or graphical lasso with regularization parameter λ. Suppose the sample covariance graph formed by thresholding the entries of the sample covariance matrix at λ is decomposed into connected components. We show that the vertex-partition induced by the connected components of the thresholded sample covariance graph (at λ) is exactly equal to that induced by the connected components of the estimated concentration graph, obtained by solving the graphical lasso problem for the same λ. This characterizes a very interesting property of a path of graphical lasso solutions. Furthermore, this simple rule, when used as a wrapper around existing algorithms for the graphical lasso, leads to enormous performance gains. For a range of values of λ, our proposal splits a large graphical lasso problem into smaller tractable problems, making it possible to solve an otherwise infeasible large-scale problem. We illustrate the graceful scalability of our proposal via synthetic and real-life microarray examples.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {781–794},
numpages = {14},
keywords = {concentration graph, graphical lasso, Gaussian graphical models, graph connected components, sparsity, sparse inverse covariance selection, large scale covariance estimation}
}

@article{10.5555/2188385.2188411,
author = {Park, Chiwoo and Huang, Jianhua Z. and Ding, Yu},
title = {GPLP: A Local and Parallel Computation Toolbox for Gaussian Process Regression},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {This paper presents the Getting-started style documentation for the local and parallel computation toolbox for Gaussian process regression (GPLP), an open source software package written in Matlab (but also compatible with Octave). The working environment and the usage of the software package will be presented in this paper.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {775–779},
numpages = {5},
keywords = {bagging for Gaussian process, Gaussian process regression, domain decomposition method, local probabilistic regression, partial independent conditional}
}

@article{10.5555/2188385.2188410,
author = {Gretton, Arthur and Borgwardt, Karsten M. and Rasch, Malte J. and Sch\"{o}lkopf, Bernhard and Smola, Alexander},
title = {A Kernel Two-Sample Test},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We propose a framework for analyzing and comparing distributions, which we use to construct statistical tests to determine if two samples are drawn from different distributions. Our test statistic is the largest difference in expectations over functions in the unit ball of a reproducing kernel Hilbert space (RKHS), and is called the maximum mean discrepancy (MMD).We present two distribution free tests based on large deviation bounds for the MMD, and a third test based on the asymptotic distribution of this statistic. The MMD can be computed in quadratic time, although efficient linear time approximations are available. Our statistic is an instance of an integral probability metric, and various classical metrics on distributions are obtained when alternative function classes are used in place of an RKHS. We apply our two-sample tests to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where they perform strongly. Excellent performance is also obtained when comparing distributions over graphs, for which these are the first such tests.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {723–773},
numpages = {51},
keywords = {two-sample test, uniform convergence bounds, hypothesis testing, kernel methods, integral probability metric, schema matching}
}

@article{10.5555/2188385.2188409,
author = {Skolidis, Grigorios and Sanguinetti, Guido},
title = {A Case Study on Meta-Generalising: A Gaussian Processes Approach},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We propose a novel model for meta-generalisation, that is, performing prediction on novel tasks based on information from multiple different but related tasks. The model is based on two coupled Gaussian processes with structured covariance function; one model performs predictions by learning a constrained covariance function encapsulating the relations between the various training tasks, while the second model determines the similarity of new tasks to previously seen tasks. We demonstrate empirically on several real and synthetic data sets both the strengths of the approach and its limitations due to the distributional assumptions underpinning it.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {691–721},
numpages = {31},
keywords = {mixture of experts, Gaussian processes, transfer learning, meta-generalising, multi-task learning}
}

@article{10.5555/2188385.2188408,
author = {Maurer, Andreas and Pontil, Massimiliano},
title = {Structured Sparsity and Generalization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We present a data dependent generalization bound for a large class of regularized algorithms which implement structured sparsity constraints. The bound can be applied to standard squared-norm regularization, the Lasso, the group Lasso, some versions of the group Lasso with overlapping groups, multiple kernel learning and other regularization schemes. In all these cases competitive results are obtained. A novel feature of our bound is that it can be applied in an infinite dimensional setting such as the Lasso in a separable Hilbert space or multiple kernel learning with a countable number of kernels.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {671–690},
numpages = {20},
keywords = {sparse estimation, Rademacher average, empirical processes}
}

@article{10.5555/2188385.2188407,
author = {Larochelle, Hugo and Mandel, Michael and Pascanu, Razvan and Bengio, Yoshua},
title = {Learning Algorithms for the Classification Restricted Boltzmann Machine},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Recent developments have demonstrated the capacity of restricted Boltzmann machines (RBM) to be powerful generative models, able to extract useful features from input data or construct deep artificial neural networks. In such settings, the RBM only yields a preprocessing or an initialization for some other model, instead of acting as a complete supervised model in its own right. In this paper, we argue that RBMs can provide a self-contained framework for developing competitive classifiers. We study the Classification RBM (ClassRBM), a variant on the RBM adapted to the classification setting. We study different strategies for training the ClassRBM and show that competitive classification performances can be reached when appropriately combining discriminative and generative training objectives. Since training according to the generative objective requires the computation of a generally intractable gradient, we also compare different approaches to estimating this gradient and address the issue of obtaining such a gradient for problems with very high dimensional inputs. Finally, we describe how to adapt the ClassRBM to two special cases of classification problems, namely semi-supervised and multitask learning.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {643–669},
numpages = {27},
keywords = {discriminative learning, generative learning, classification, restricted Boltzmannmachine}
}

@article{10.5555/2188385.2188406,
author = {Yan, Fei and Kittler, Josef and Mikolajczyk, Krystian and Tahir, Atif},
title = {Non-Sparse Multiple Kernel Fisher Discriminant Analysis},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Sparsity-inducing multiple kernel Fisher discriminant analysis (MK-FDA) has been studied in the literature. Building on recent advances in non-sparse multiple kernel learning (MKL), we propose a non-sparse version of MK-FDA, which imposes a general lp norm regularisation on the kernel weights. We formulate the associated optimisation problem as a semi-infinite program (SIP), and adapt an iterative wrapper algorithm to solve it. We then discuss, in light of latest advances in MKL optimisation techniques, several reformulations and optimisation strategies that can potentially lead to significant improvements in the efficiency and scalability of MK-FDA. We carry out extensive experiments on six datasets from various application areas, and compare closely the performance of lp MK-FDA, fixed norm MK-FDA, and several variants of SVM-based MKL (MK-SVM). Our results demonstrate that lp MK-FDA improves upon sparse MK-FDA in many practical situations. The results also show that on image categorisation problems, lp MK-FDA tends to outperform its SVM counterpart. Finally, we also discuss the connection between (MK-)FDA and (MK-)SVM, under the unified framework of regularised kernel machines.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {607–642},
numpages = {36},
keywords = {support vector machines, multiple kernel learning, regularised least squares, kernel fisher discriminant analysis}
}

@article{10.5555/2188385.2188405,
author = {Telgarsky, Matus},
title = {A Primal-Dual Convergence Analysis of Boosting},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Boosting combines weak learners into a predictor with low empirical risk. Its dual constructs a high entropy distribution upon which weak learners and training labels are uncorrelated. This manuscript studies this primal-dual relationship under a broad family of losses, including the exponential loss of AdaBoost and the logistic loss, revealing: • Weak learnability aids the whole loss family: for any ε > 0, O(ln(1/ε)) iterations suffice to produce a predictor with empirical risk ε-close to the infimum; • The circumstances granting the existence of an empirical risk minimizer may be characterized in terms of the primal and dual problems, yielding a new proof of the known rate O(ln(1/ε)); • Arbitrary instances may be decomposed into the above two, granting rate O(1/ε), with a matching lower bound provided for the logistic loss.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {561–606},
numpages = {46},
keywords = {maximum entropy, boosting, weak learnability, coordinate descent, convex analysis}
}

@article{10.5555/2188385.2188404,
author = {Piccolo, Stephen R. and Frey, Lewis J.},
title = {ML-Flex: A Flexible Toolbox for Performing Classification Analyses in Parallel},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Motivated by a need to classify high-dimensional, heterogeneous data from the bioinformatics domain, we developed ML-Flex, a machine-learning toolbox that enables users to perform two-class and multi-class classification analyses in a systematic yet flexible manner. ML-Flex was written in Java but is capable of interfacing with third-party packages written in other programming languages. It can handle multiple input-data formats and supports a variety of customizations. MLFlex provides implementations of various validation strategies, which can be executed in parallel across multiple computing cores, processors, and nodes. Additionally, ML-Flex supports aggregating evidence across multiple algorithms and data sets via ensemble learning. This open-source software package is freely available from http://mlflex.sourceforge.net.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {555–559},
numpages = {5},
keywords = {reproducible research, ensemble, parallel, toolbox, classification}
}

@article{10.5555/2188385.2188403,
author = {Benbouzid, Djalel and Busa-Fekete, R\'{o}bert and Casagrande, Norman and Collin, Fran\c{c}ois-David and K\'{e}gl, Bal\'{a}zs},
title = {MULTIBOOST: A Multi-Purpose Boosting Package},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The MULTIBOOST package provides a fast C++ implementation of multi-class/multi-label/multitask boosting algorithms. It is based on ADABOOST.MH but it also implements popular cascade classifiers and FILTERBOOST. The package contains common multi-class base learners (stumps, trees, products, Haar filters). Further base learners and strong learners following the boosting paradigm can be easily implemented in a flexible framework.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {549–553},
numpages = {5},
keywords = {FILTERBOOST, cascade classifier, boosting, ADABOOST.MH}
}

@article{10.5555/2188385.2188402,
author = {Jain, Prateek and Kulis, Brian and Davis, Jason V. and Dhillon, Inderjit S.},
title = {Metric and Kernel Learning Using a Linear Transformation},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Metric and kernel learning arise in several machine learning applications. However, most existing metric learning algorithms are limited to learning metrics over low-dimensional data, while existing kernel learning algorithms are often limited to the transductive setting and do not generalize to new data points. In this paper, we study the connections between metric learning and kernel learning that arise when studying metric learning as a linear transformation learning problem. In particular, we propose a general optimization framework for learning metrics via linear transformations, and analyze in detail a special case of our framework-that of minimizing the LogDet divergence subject to linear constraints. We then propose a general regularized framework for learning a kernel matrix, and show it to be equivalent to our metric learning framework. Our theoretical connections between metric and kernel learning have two main consequences: 1) the learned kernel matrix parameterizes a linear transformation kernel function and can be applied inductively to new data points, 2) our result yields a constructive method for kernelizing most existing Mahalanobis metric learning formulations. We demonstrate our learning approach by applying it to large-scale real world problems in computer vision, text mining and semi-supervised kernel dimensionality reduction.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {519–547},
numpages = {29},
keywords = {matrix divergences, kernel learning, logdet divergence, metric learning, linear transformation}
}

@article{10.5555/2503308.2188401,
author = {Raykar, Vikas C. and Yu, Shipeng},
title = {Eliminating Spammers and Ranking Annotators for Crowdsourced Labeling Tasks},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {With the advent of crowdsourcing services it has become quite cheap and reasonably effective to get a data set labeled by multiple annotators in a short amount of time. Various methods have been proposed to estimate the consensus labels by correcting for the bias of annotators with different kinds of expertise. Since we do not have control over the quality of the annotators, very often the annotations can be dominated by spammers, defined as annotators who assign labels randomly without actually looking at the instance. Spammers can make the cost of acquiring labels very expensive and can potentially degrade the quality of the final consensus labels. In this paper we propose an empirical Bayesian algorithm called SpEMthat iteratively eliminates the spammers and estimates the consensus labels based only on the good annotators. The algorithm is motivated by defining a spammer score that can be used to rank the annotators. Experiments on simulated and real data show that the proposed approach is better than (or as good as) the earlier approaches in terms of the accuracy and uses a significantly smaller number of annotators.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {491–518},
numpages = {28},
keywords = {spammers, ranking annotators, multiple annotators, crowdsourcing}
}

@article{10.5555/2503308.2188400,
author = {Frank, Mario and Streich, Andreas P. and Basin, David and Buhmann, Joachim M.},
title = {Multi-Assignment Clustering for Boolean Data},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We propose a probabilistic model for clustering Boolean data where an object can be simultaneously assigned to multiple clusters. By explicitly modeling the underlying generative process that combines the individual source emissions, highly structured data are expressed with substantially fewer clusters compared to single-assignment clustering. As a consequence, such a model provides robust parameter estimators even when the number of samples is low. We extend the model with different noise processes and demonstrate that maximum-likelihood estimation with multiple assignments consistently infers source parameters more accurately than single-assignment clustering. Our model is primarily motivated by the task of role mining for role-based access control, where users of a system are assigned one or more roles. In experiments with real-world access-control data, our model exhibits better generalization performance than state-of-the-art approaches.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {459–489},
numpages = {31},
keywords = {Boolean data, clustering, latent feature models, multi-assignments, overlapping clusters, role mining}
}

@article{10.5555/2503308.2188399,
author = {Shalit, Uri and Weinshall, Daphna and Chechik, Gal},
title = {Online Learning in the Embedded Manifold of Low-Rank Matrices},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
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 efficiently. It has run time and memory complexity of O((n+m)k) for a rank-k matrix of dimension m\texttimes{}n, when using an online procedure with rank-one gradients. We use this algorithm, LORETA, to learn a matrix-form similarity measure over pairs of documents represented as high dimensional vectors. LORETA 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 LORETA to learn positive semi-definite low-rank matrices, providing an online algorithm for low-rank metric learning. LORETA also shows consistent improvement over standard weakly supervised methods in a large (1600 classes and 1 million images, using ImageNet) multilabel image classification task.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {429–458},
numpages = {30},
keywords = {low rank, multitask learning, Riemannian manifolds, retractions, metric learning, online learning}
}

@article{10.5555/2503308.2188398,
author = {Raskutti, Garvesh and Wainwright, Martin J. and Yu, Bin},
title = {Minimax-Optimal Rates for Sparse Additive Models over Kernel Classes via Convex Programming},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Sparse additive models are families of d-variate functions with the additive decomposition f* = Σj∈S fj*, where S is an unknown subset of cardinality s < d. In this paper, we consider the case where each univariate component function fj* lies in a reproducing kernel Hilbert space (RKHS), and analyze a method for estimating the unknown function f* based on kernels combined with l1-type convex regularization. Working within a high-dimensional framework that allows both the dimension d and sparsity s to increase with n, we derive convergence rates in the L2(P) and L2(Pn) norms over the class Fd,s,H of sparse additive models with each univariate function fj* in the unit ball of a univariate RKHS with bounded kernel function. We complement our upper bounds by deriving minimax lower bounds on the L2(P) error, thereby showing the optimality of our method. Thus, we obtain optimal minimax rates for many interesting classes of sparse additive models, including polynomials, splines, and Sobolev classes. We also show that if, in contrast to our univariate conditions, the d-variate function class is assumed to be globally bounded, then much faster estimation rates are possible for any sparsity s = Ω(√n), showing that global boundedness is a significant restriction in the high-dimensional setting.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {389–427},
numpages = {39},
keywords = {convex, sparsity, kernel, minimax, non-parametric}
}

@article{10.5555/2503308.2188397,
author = {Huang, Gary B. and Kae, Andrew and Doersch, Carl and Learned-Miller, Erik},
title = {Bounding the Probability of Error for High Precision Optical Character Recognition},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider a model for which it is important, early in processing, to estimate some variables with high precision, but perhaps at relatively low recall. If some variables can be identified with near certainty, they can be conditioned upon, allowing further inference to be done efficiently. Specifically, we consider optical character recognition (OCR) systems that can be bootstrapped by identifying a subset of correctly translated document words with very high precision. This "clean set" is subsequently used as document-specific training data. While OCR systems produce confidence measures for the identity of each letter or word, thresholding these values still produces a significant number of errors.We introduce a novel technique for identifying a set of correct words with very high precision. Rather than estimating posterior probabilities, we bound the probability that any given word is incorrect using an approximate worst case analysis. We give empirical results on a data set of difficult historical newspaper scans, demonstrating that our method for identifying correct words makes only two errors in 56 documents. Using document-specific character models generated from this data, we are able to reduce the error over properly segmented characters by 34.1% from an initial OCR system's translation.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {363–387},
numpages = {25},
keywords = {probability bounding, computer vision, optical character recognition, document-specific modeling}
}

@article{10.5555/2503308.2188396,
author = {Gutmann, Michael U. and Hyv\"{a}rinen, Aapo},
title = {Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We consider the task of estimating, from observed data, a probabilistic model that is parameterized by a finite number of parameters. In particular, we are considering the situation where the model probability density function is unnormalized. That is, the model is only specified up to the partition function. The partition function normalizes a model so that it integrates to one for any choice of the parameters. However, it is often impossible to obtain it in closed form. Gibbs distributions, Markov and multi-layer networks are examples of models where analytical normalization is often impossible. Maximum likelihood estimation can then not be used without resorting to numerical approximations which are often computationally expensive. We propose here a new objective function for the estimation of both normalized and unnormalized models. The basic idea is to perform nonlinear logistic regression to discriminate between the observed data and some artificially generated noise. With this approach, the normalizing partition function can be estimated like any other parameter. We prove that the new estimation method leads to a consistent (convergent) estimator of the parameters. For large noise sample sizes, the new estimator is furthermore shown to behave like the maximum likelihood estimator. In the estimation of unnormalized models, there is a trade-off between statistical and computational performance. We show that the new method strikes a competitive trade-off in comparison to other estimation methods for unnormalized models. As an application to real data, we estimate novel two-layer models of natural image statistics with spline nonlinearities.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {307–361},
numpages = {55},
keywords = {partition function, estimation, computation, unnormalized models, natural image statistics}
}

@article{10.5555/2503308.2188395,
author = {Bergstra, James and Bengio, Yoshua},
title = {Random Search for Hyper-Parameter Optimization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Grid search and manual search are the most widely used strategies for hyper-parameter optimization. This paper shows empirically and theoretically that randomly chosen trials are more efficient for hyper-parameter optimization than trials on a grid. Empirical evidence comes from a comparison with a large previous study that used grid search and manual search to configure neural networks and deep belief networks. Compared with neural networks configured by a pure grid search, we find that random search over the same domain is able to find models that are as good or better within a small fraction of the computation time. Granting random search the same computational budget, random search finds better models by effectively searching a larger, less promising configuration space. Compared with deep belief networks configured by a thoughtful combination of manual search and grid search, purely random search over the same 32-dimensional configuration space found statistically equal performance on four of seven data sets, and superior performance on one of seven. A Gaussian process analysis of the function from hyper-parameters to validation set performance reveals that for most data sets only a few of the hyper-parameters really matter, but that different hyper-parameters are important on different data sets. This phenomenon makes grid search a poor choice for configuring algorithms for new data sets. Our analysis casts some light on why recent "High Throughput" methods achieve surprising success--they appear to search through a large number of hyper-parameters because most hyper-parameters do not matter much. We anticipate that growing interest in large hierarchical models will place an increasing burden on techniques for hyper-parameter optimization; this work shows that random search is a natural baseline against which to judge progress in the development of adaptive (sequential) hyper-parameter optimization algorithms.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {281–305},
numpages = {25},
keywords = {model selection, global optimization, deep learning, response surface modeling, neural networks}
}

@article{10.5555/2503308.2188394,
author = {El-Yaniv, Ran and Wiener, Yair},
title = {Active Learning via Perfect Selective Classification},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We discover a strong relation between two known learning models: stream-based active learning and perfect selective classification (an extreme case of 'classification with a reject option'). For these models, restricted to the realizable case, we show a reduction of active learning to selective classification that preserves fast rates. Applying this reduction to recent results for selective classification, we derive exponential target-independent label complexity speedup for actively learning general (non-homogeneous) linear classifiers when the data distribution is an arbitrary high dimensional mixture of Gaussians. Finally, we study the relation between the proposed technique and existing label complexity measures, including teaching dimension and disagreement coefficient.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {255–279},
numpages = {25},
keywords = {exploration vs. exploitation, classification with a reject option, perfect classification, disagreement coefficient, active learning, teaching dimension, selective sampling, selective classification}
}

@article{10.5555/2503308.2188393,
author = {Orabona, Francesco and Jie, Luo and Caputo, Barbara},
title = {Multi Kernel Learning with Online-Batch Optimization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In recent years there has been a lot of interest in designing principled classification algorithms over multiple cues, based on the intuitive notion that using more features should lead to better performance. In the domain of kernel methods, a principled way to use multiple features is the Multi Kernel Learning (MKL) approach.Here we present a MKL optimization algorithm based on stochastic gradient descent that has a guaranteed convergence rate. We directly solve the MKL problem in the primal formulation. By having a p-norm formulation of MKL, we introduce a parameter that controls the level of sparsity of the solution, while leading to an easier optimization problem. We prove theoretically and experimentally that 1) our algorithm has a faster convergence rate as the number of kernels grows; 2) the training complexity is linear in the number of training examples; 3) very few iterations are sufficient to reach good solutions. Experiments on standard benchmark databases support our claims.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {227–253},
numpages = {27},
keywords = {learning kernels, online optimization, stochastic subgradient descent, multiple kernel learning, large scale, convergence bounds}
}

@article{10.5555/2188385.2188401,
author = {Raykar, Vikas C. and Yu, Shipeng},
title = {Eliminating Spammers and Ranking Annotators for Crowdsourced Labeling Tasks},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {With the advent of crowdsourcing services it has become quite cheap and reasonably effective to get a data set labeled by multiple annotators in a short amount of time. Various methods have been proposed to estimate the consensus labels by correcting for the bias of annotators with different kinds of expertise. Since we do not have control over the quality of the annotators, very often the annotations can be dominated by spammers, defined as annotators who assign labels randomly without actually looking at the instance. Spammers can make the cost of acquiring labels very expensive and can potentially degrade the quality of the final consensus labels. In this paper we propose an empirical Bayesian algorithm called SpEMthat iteratively eliminates the spammers and estimates the consensus labels based only on the good annotators. The algorithm is motivated by defining a spammer score that can be used to rank the annotators. Experiments on simulated and real data show that the proposed approach is better than (or as good as) the earlier approaches in terms of the accuracy and uses a significantly smaller number of annotators.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {491–518},
numpages = {28},
keywords = {ranking annotators, spammers, multiple annotators, crowdsourcing}
}

@article{10.5555/2188385.2188400,
author = {Frank, Mario and Streich, Andreas P. and Basin, David and Buhmann, Joachim M.},
title = {Multi-Assignment Clustering for Boolean Data},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We propose a probabilistic model for clustering Boolean data where an object can be simultaneously assigned to multiple clusters. By explicitly modeling the underlying generative process that combines the individual source emissions, highly structured data are expressed with substantially fewer clusters compared to single-assignment clustering. As a consequence, such a model provides robust parameter estimators even when the number of samples is low. We extend the model with different noise processes and demonstrate that maximum-likelihood estimation with multiple assignments consistently infers source parameters more accurately than single-assignment clustering. Our model is primarily motivated by the task of role mining for role-based access control, where users of a system are assigned one or more roles. In experiments with real-world access-control data, our model exhibits better generalization performance than state-of-the-art approaches.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {459–489},
numpages = {31},
keywords = {latent feature models, clustering, role mining, overlapping clusters, multi-assignments, Boolean data}
}

@article{10.5555/2188385.2188399,
author = {Shalit, Uri and Weinshall, Daphna and Chechik, Gal},
title = {Online Learning in the Embedded Manifold of Low-Rank Matrices},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
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 efficiently. It has run time and memory complexity of O((n+m)k) for a rank-k matrix of dimension m\texttimes{}n, when using an online procedure with rank-one gradients. We use this algorithm, LORETA, to learn a matrix-form similarity measure over pairs of documents represented as high dimensional vectors. LORETA 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 LORETA to learn positive semi-definite low-rank matrices, providing an online algorithm for low-rank metric learning. LORETA also shows consistent improvement over standard weakly supervised methods in a large (1600 classes and 1 million images, using ImageNet) multilabel image classification task.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {429–458},
numpages = {30},
keywords = {low rank, Riemannian manifolds, online learning, metric learning, retractions, multitask learning}
}

@article{10.5555/2188385.2188398,
author = {Raskutti, Garvesh and Wainwright, Martin J. and Yu, Bin},
title = {Minimax-Optimal Rates for Sparse Additive Models over Kernel Classes via Convex Programming},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Sparse additive models are families of d-variate functions with the additive decomposition f* = Σj∈S fj*, where S is an unknown subset of cardinality s < d. In this paper, we consider the case where each univariate component function fj* lies in a reproducing kernel Hilbert space (RKHS), and analyze a method for estimating the unknown function f* based on kernels combined with l1-type convex regularization. Working within a high-dimensional framework that allows both the dimension d and sparsity s to increase with n, we derive convergence rates in the L2(P) and L2(Pn) norms over the class Fd,s,H of sparse additive models with each univariate function fj* in the unit ball of a univariate RKHS with bounded kernel function. We complement our upper bounds by deriving minimax lower bounds on the L2(P) error, thereby showing the optimality of our method. Thus, we obtain optimal minimax rates for many interesting classes of sparse additive models, including polynomials, splines, and Sobolev classes. We also show that if, in contrast to our univariate conditions, the d-variate function class is assumed to be globally bounded, then much faster estimation rates are possible for any sparsity s = Ω(√n), showing that global boundedness is a significant restriction in the high-dimensional setting.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {389–427},
numpages = {39},
keywords = {convex, minimax, non-parametric, sparsity, kernel}
}

@article{10.5555/2188385.2188397,
author = {Huang, Gary B. and Kae, Andrew and Doersch, Carl and Learned-Miller, Erik},
title = {Bounding the Probability of Error for High Precision Optical Character Recognition},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We consider a model for which it is important, early in processing, to estimate some variables with high precision, but perhaps at relatively low recall. If some variables can be identified with near certainty, they can be conditioned upon, allowing further inference to be done efficiently. Specifically, we consider optical character recognition (OCR) systems that can be bootstrapped by identifying a subset of correctly translated document words with very high precision. This "clean set" is subsequently used as document-specific training data. While OCR systems produce confidence measures for the identity of each letter or word, thresholding these values still produces a significant number of errors.We introduce a novel technique for identifying a set of correct words with very high precision. Rather than estimating posterior probabilities, we bound the probability that any given word is incorrect using an approximate worst case analysis. We give empirical results on a data set of difficult historical newspaper scans, demonstrating that our method for identifying correct words makes only two errors in 56 documents. Using document-specific character models generated from this data, we are able to reduce the error over properly segmented characters by 34.1% from an initial OCR system's translation.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {363–387},
numpages = {25},
keywords = {computer vision, probability bounding, document-specific modeling, optical character recognition}
}

@article{10.5555/2188385.2188396,
author = {Gutmann, Michael U. and Hyv\"{a}rinen, Aapo},
title = {Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We consider the task of estimating, from observed data, a probabilistic model that is parameterized by a finite number of parameters. In particular, we are considering the situation where the model probability density function is unnormalized. That is, the model is only specified up to the partition function. The partition function normalizes a model so that it integrates to one for any choice of the parameters. However, it is often impossible to obtain it in closed form. Gibbs distributions, Markov and multi-layer networks are examples of models where analytical normalization is often impossible. Maximum likelihood estimation can then not be used without resorting to numerical approximations which are often computationally expensive. We propose here a new objective function for the estimation of both normalized and unnormalized models. The basic idea is to perform nonlinear logistic regression to discriminate between the observed data and some artificially generated noise. With this approach, the normalizing partition function can be estimated like any other parameter. We prove that the new estimation method leads to a consistent (convergent) estimator of the parameters. For large noise sample sizes, the new estimator is furthermore shown to behave like the maximum likelihood estimator. In the estimation of unnormalized models, there is a trade-off between statistical and computational performance. We show that the new method strikes a competitive trade-off in comparison to other estimation methods for unnormalized models. As an application to real data, we estimate novel two-layer models of natural image statistics with spline nonlinearities.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {307–361},
numpages = {55},
keywords = {natural image statistics, estimation, computation, unnormalized models, partition function}
}

@article{10.5555/2188385.2188395,
author = {Bergstra, James and Bengio, Yoshua},
title = {Random Search for Hyper-Parameter Optimization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Grid search and manual search are the most widely used strategies for hyper-parameter optimization. This paper shows empirically and theoretically that randomly chosen trials are more efficient for hyper-parameter optimization than trials on a grid. Empirical evidence comes from a comparison with a large previous study that used grid search and manual search to configure neural networks and deep belief networks. Compared with neural networks configured by a pure grid search, we find that random search over the same domain is able to find models that are as good or better within a small fraction of the computation time. Granting random search the same computational budget, random search finds better models by effectively searching a larger, less promising configuration space. Compared with deep belief networks configured by a thoughtful combination of manual search and grid search, purely random search over the same 32-dimensional configuration space found statistically equal performance on four of seven data sets, and superior performance on one of seven. A Gaussian process analysis of the function from hyper-parameters to validation set performance reveals that for most data sets only a few of the hyper-parameters really matter, but that different hyper-parameters are important on different data sets. This phenomenon makes grid search a poor choice for configuring algorithms for new data sets. Our analysis casts some light on why recent "High Throughput" methods achieve surprising success--they appear to search through a large number of hyper-parameters because most hyper-parameters do not matter much. We anticipate that growing interest in large hierarchical models will place an increasing burden on techniques for hyper-parameter optimization; this work shows that random search is a natural baseline against which to judge progress in the development of adaptive (sequential) hyper-parameter optimization algorithms.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {281–305},
numpages = {25},
keywords = {deep learning, response surface modeling, neural networks, model selection, global optimization}
}

@article{10.5555/2188385.2188394,
author = {El-Yaniv, Ran and Wiener, Yair},
title = {Active Learning via Perfect Selective Classification},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We discover a strong relation between two known learning models: stream-based active learning and perfect selective classification (an extreme case of 'classification with a reject option'). For these models, restricted to the realizable case, we show a reduction of active learning to selective classification that preserves fast rates. Applying this reduction to recent results for selective classification, we derive exponential target-independent label complexity speedup for actively learning general (non-homogeneous) linear classifiers when the data distribution is an arbitrary high dimensional mixture of Gaussians. Finally, we study the relation between the proposed technique and existing label complexity measures, including teaching dimension and disagreement coefficient.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {255–279},
numpages = {25},
keywords = {perfect classification, selective classification, disagreement coefficient, exploration vs. exploitation, selective sampling, active learning, teaching dimension, classification with a reject option}
}

@article{10.5555/2188385.2188393,
author = {Orabona, Francesco and Jie, Luo and Caputo, Barbara},
title = {Multi Kernel Learning with Online-Batch Optimization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {In recent years there has been a lot of interest in designing principled classification algorithms over multiple cues, based on the intuitive notion that using more features should lead to better performance. In the domain of kernel methods, a principled way to use multiple features is the Multi Kernel Learning (MKL) approach.Here we present a MKL optimization algorithm based on stochastic gradient descent that has a guaranteed convergence rate. We directly solve the MKL problem in the primal formulation. By having a p-norm formulation of MKL, we introduce a parameter that controls the level of sparsity of the solution, while leading to an easier optimization problem. We prove theoretically and experimentally that 1) our algorithm has a faster convergence rate as the number of kernels grows; 2) the training complexity is linear in the number of training examples; 3) very few iterations are sufficient to reach good solutions. Experiments on standard benchmark databases support our claims.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {227–253},
numpages = {27},
keywords = {convergence bounds, online optimization, stochastic subgradient descent, learning kernels, multiple kernel learning, large scale}
}

@article{10.5555/2503308.2188392,
author = {Voevodski, Konstantin and Balcan, Maria-Florina and R\"{o}glin, Heiko and Teng, Shang-Hua and Xia, Yu},
title = {Active Clustering of Biological Sequences},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s ∈ S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. Our algorithm uses an active selection strategy to choose a small set of points that we call landmarks, and considers only the distances between landmarks and other points to produce a clustering. We use our procedure to cluster proteins by sequence similarity. This setting nicely fits our model because we can use a fast sequence database search program to query a sequence against an entire data set. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual classification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {203–225},
numpages = {23},
keywords = {active clustering, clustering, approximation stability, protein sequences, approximation algorithms, clustering accuracy, k-median}
}

@article{10.5555/2503308.2188391,
author = {Dekel, Ofer and Gilad-Bachrach, Ran and Shamir, Ohad and Xiao, Lin},
title = {Optimal Distributed Online Prediction Using Mini-Batches},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Online prediction methods are typically presented as serial algorithms running on a single processor. However, in the age of web-scale prediction problems, it is increasingly common to encounter situations where a single processor cannot keep up with the high rate at which inputs arrive. In this work, we present the distributed mini-batch algorithm, a method of converting many serial gradient-based online prediction algorithms into distributed algorithms. We prove a regret bound for this method that is asymptotically optimal for smooth convex loss functions and stochastic inputs. Moreover, our analysis explicitly takes into account communication latencies between nodes in the distributed environment. We show how our method can be used to solve the closely-related distributed stochastic optimization problem, achieving an asymptotically linear speed-up over multiple processors. Finally, we demonstrate the merits of our approach on a web-scale online prediction problem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {165–202},
numpages = {38},
keywords = {regret bounds, convex optimization, online learning, stochastic optimization, distributed computing}
}

@article{10.5555/2503308.2188390,
author = {Ailon, Nir},
title = {An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Given a set V of n elements we wish to linearly order them given pairwise preference labels which may be non-transitive (due to irrationality or arbitrary noise).The goal is to linearly order the elements while disagreeing with as few pairwise preference labels as possible. Our performance is measured by two parameters: The number of disagreements (loss) and the query complexity (number of pairwise preference labels). Our algorithm adaptively queries at most O(ε-6n log5 n) preference labels for a regret of ε times the optimal loss. As a function of n, this is asymptotically better than standard (non-adaptive) learning bounds achievable for the same problem.Our main result takes us a step closer toward settling an open problem posed by learning-to-rank (from pairwise information) theoreticians and practitioners: What is a provably correct way to sample preference labels? To further show the power and practicality of our solution, we analyze a typical test case in which a large margin linear relaxation is used for efficiently solving the simpler learning problems in our decomposition.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {137–164},
numpages = {28},
keywords = {ranking, active learning, statistical learning theory, pairwise ranking, preferences}
}

@article{10.5555/2503308.2188389,
author = {Zhang, Haizhang and Xu, Yuesheng and Zhang, Qinghui},
title = {Refinement of Operator-Valued Reproducing Kernels},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {This paper studies the construction of a refinement kernel for a given operator-valued reproducing kernel such that the vector-valued reproducing kernel Hilbert space of the refinement kernel contains that of the given kernel as a subspace. The study is motivated from the need of updating the current operator-valued reproducing kernel in multi-task learning when underfitting or overfitting occurs. Numerical simulations confirm that the established refinement kernel method is able to meet this need. Various characterizations are provided based on feature maps and vector-valued integral representations of operator-valued reproducing kernels. Concrete examples of refining translation invariant and finite Hilbert-Schmidt operator-valued reproducing kernels are provided. Other examples include refinement of Hessian of scalar-valued translation-invariant kernels and transformation kernels. Existence and properties of operator-valued reproducing kernels preserved during the refinement process are also investigated.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {91–136},
numpages = {46},
keywords = {embedding, numerical experiments, operator-valued reproducing kernels, refinement, translation invariant kernels, Hessian of Gaussian kernels, vector-valued reproducing kernel Hilbert spaces, Hilbert-Schmidt kernels}
}

@article{10.5555/2503308.2188388,
author = {Minsker, Stanislav},
title = {Plug-in Approach to Active Learning},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present a new active learning algorithm based on nonparametric estimators of the regression function. Our investigation provides probabilistic bounds for the rates of convergence of the generalization error achievable by proposed method over a broad class of underlying distributions. We also prove minimax lower bounds which show that the obtained rates are almost tight.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {67–90},
numpages = {24},
keywords = {model selection, classification, selective sampling, confidence bands, active learning}
}

@article{10.5555/2503308.2188387,
author = {Brown, Gavin and Pocock, Adam and Zhao, Ming-Jie and Luj\'{a}n, Mikel},
title = {Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selection},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present a unifying framework for information theoretic feature selection, bringing almost two decades of research on heuristic filter criteria under a single theoretical interpretation. This is in response to the question: "what are the implicit statistical assumptions of feature selection criteria based on mutual information?". To answer this, we adopt a different strategy than is usual in the feature selection literature--instead of trying to define a criterion, we derive one, directly from a clearly specified objective function: the conditional likelihood of the training labels. While many hand-designed heuristic criteria try to optimize a definition of feature 'relevancy' and 'redundancy', our approach leads to a probabilistic framework which naturally incorporates these concepts. As a result we can unify the numerous criteria published over the last two decades, and show them to be low-order approximations to the exact (but intractable) optimisation problem. The primary contribution is to show that common heuristics for information based feature selection (including Markov Blanket algorithms as a special case) are approximate iterative maximisers of the conditional likelihood. A large empirical study provides strong evidence to favour certain classes of criteria, in particular those that balance the relative size of the relevancy/redundancy terms. Overall we conclude that the JMI criterion (Yang and Moody, 1999; Meyer et al., 2008) provides the best tradeoff in terms of accuracy, stability, and flexibility with small data samples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {27–66},
numpages = {40},
keywords = {conditional likelihood, mutual information, feature selection}
}

@article{10.5555/2503308.2188386,
author = {Ying, Yiming and Li, Peng},
title = {Distance Metric Learning with Eigenvalue Optimization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The main theme of this paper is to develop a novel eigenvalue optimization framework for learning a Mahalanobis metric. Within this context, we introduce a novel metric learning approach called DML-eig which is shown to be equivalent to a well-known eigenvalue optimization problem called minimizing the maximal eigenvalue of a symmetric matrix (Overton, 1988; Lewis and Overton, 1996). Moreover, we formulate LMNN (Weinberger et al., 2005), one of the state-of-the-art metric learning methods, as a similar eigenvalue optimization problem. This novel framework not only provides new insights into metric learning but also opens new avenues to the design of efficient metric learning algorithms. Indeed, first-order algorithms are developed for DML-eig and LMNN which only need the computation of the largest eigenvector of a matrix per iteration. Their convergence characteristics are rigorously established. Various experiments on benchmark data sets show the competitive performance of our new approaches. In addition, we report an encouraging result on a difficult and challenging face verification data set called Labeled Faces in the Wild (LFW).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–26},
numpages = {26},
keywords = {semi-definite programming, matrix factorization, eigenvalue optimization, first-order methods, metric learning, convex optimization, face verification}
}

@article{10.5555/2188385.2188392,
author = {Voevodski, Konstantin and Balcan, Maria-Florina and R\"{o}glin, Heiko and Teng, Shang-Hua and Xia, Yu},
title = {Active Clustering of Biological Sequences},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s ∈ S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. Our algorithm uses an active selection strategy to choose a small set of points that we call landmarks, and considers only the distances between landmarks and other points to produce a clustering. We use our procedure to cluster proteins by sequence similarity. This setting nicely fits our model because we can use a fast sequence database search program to query a sequence against an entire data set. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual classification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {203–225},
numpages = {23},
keywords = {clustering accuracy, clustering, approximation algorithms, k-median, approximation stability, active clustering, protein sequences}
}

@article{10.5555/2188385.2188391,
author = {Dekel, Ofer and Gilad-Bachrach, Ran and Shamir, Ohad and Xiao, Lin},
title = {Optimal Distributed Online Prediction Using Mini-Batches},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Online prediction methods are typically presented as serial algorithms running on a single processor. However, in the age of web-scale prediction problems, it is increasingly common to encounter situations where a single processor cannot keep up with the high rate at which inputs arrive. In this work, we present the distributed mini-batch algorithm, a method of converting many serial gradient-based online prediction algorithms into distributed algorithms. We prove a regret bound for this method that is asymptotically optimal for smooth convex loss functions and stochastic inputs. Moreover, our analysis explicitly takes into account communication latencies between nodes in the distributed environment. We show how our method can be used to solve the closely-related distributed stochastic optimization problem, achieving an asymptotically linear speed-up over multiple processors. Finally, we demonstrate the merits of our approach on a web-scale online prediction problem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {165–202},
numpages = {38},
keywords = {stochastic optimization, distributed computing, online learning, regret bounds, convex optimization}
}

@article{10.5555/2188385.2188390,
author = {Ailon, Nir},
title = {An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {Given a set V of n elements we wish to linearly order them given pairwise preference labels which may be non-transitive (due to irrationality or arbitrary noise).The goal is to linearly order the elements while disagreeing with as few pairwise preference labels as possible. Our performance is measured by two parameters: The number of disagreements (loss) and the query complexity (number of pairwise preference labels). Our algorithm adaptively queries at most O(ε-6n log5 n) preference labels for a regret of ε times the optimal loss. As a function of n, this is asymptotically better than standard (non-adaptive) learning bounds achievable for the same problem.Our main result takes us a step closer toward settling an open problem posed by learning-to-rank (from pairwise information) theoreticians and practitioners: What is a provably correct way to sample preference labels? To further show the power and practicality of our solution, we analyze a typical test case in which a large margin linear relaxation is used for efficiently solving the simpler learning problems in our decomposition.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {137–164},
numpages = {28},
keywords = {active learning, preferences, statistical learning theory, pairwise ranking, ranking}
}

@article{10.5555/2188385.2188389,
author = {Zhang, Haizhang and Xu, Yuesheng and Zhang, Qinghui},
title = {Refinement of Operator-Valued Reproducing Kernels},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {This paper studies the construction of a refinement kernel for a given operator-valued reproducing kernel such that the vector-valued reproducing kernel Hilbert space of the refinement kernel contains that of the given kernel as a subspace. The study is motivated from the need of updating the current operator-valued reproducing kernel in multi-task learning when underfitting or overfitting occurs. Numerical simulations confirm that the established refinement kernel method is able to meet this need. Various characterizations are provided based on feature maps and vector-valued integral representations of operator-valued reproducing kernels. Concrete examples of refining translation invariant and finite Hilbert-Schmidt operator-valued reproducing kernels are provided. Other examples include refinement of Hessian of scalar-valued translation-invariant kernels and transformation kernels. Existence and properties of operator-valued reproducing kernels preserved during the refinement process are also investigated.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {91–136},
numpages = {46},
keywords = {translation invariant kernels, embedding, vector-valued reproducing kernel Hilbert spaces, Hilbert-Schmidt kernels, Hessian of Gaussian kernels, refinement, operator-valued reproducing kernels, numerical experiments}
}

@article{10.5555/2188385.2188388,
author = {Minsker, Stanislav},
title = {Plug-in Approach to Active Learning},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We present a new active learning algorithm based on nonparametric estimators of the regression function. Our investigation provides probabilistic bounds for the rates of convergence of the generalization error achievable by proposed method over a broad class of underlying distributions. We also prove minimax lower bounds which show that the obtained rates are almost tight.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {67–90},
numpages = {24},
keywords = {active learning, selective sampling, model selection, confidence bands, classification}
}

@article{10.5555/2188385.2188387,
author = {Brown, Gavin and Pocock, Adam and Zhao, Ming-Jie and Luj\'{a}n, Mikel},
title = {Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selection},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {We present a unifying framework for information theoretic feature selection, bringing almost two decades of research on heuristic filter criteria under a single theoretical interpretation. This is in response to the question: "what are the implicit statistical assumptions of feature selection criteria based on mutual information?". To answer this, we adopt a different strategy than is usual in the feature selection literature--instead of trying to define a criterion, we derive one, directly from a clearly specified objective function: the conditional likelihood of the training labels. While many hand-designed heuristic criteria try to optimize a definition of feature 'relevancy' and 'redundancy', our approach leads to a probabilistic framework which naturally incorporates these concepts. As a result we can unify the numerous criteria published over the last two decades, and show them to be low-order approximations to the exact (but intractable) optimisation problem. The primary contribution is to show that common heuristics for information based feature selection (including Markov Blanket algorithms as a special case) are approximate iterative maximisers of the conditional likelihood. A large empirical study provides strong evidence to favour certain classes of criteria, in particular those that balance the relative size of the relevancy/redundancy terms. Overall we conclude that the JMI criterion (Yang and Moody, 1999; Meyer et al., 2008) provides the best tradeoff in terms of accuracy, stability, and flexibility with small data samples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {27–66},
numpages = {40},
keywords = {mutual information, feature selection, conditional likelihood}
}

@article{10.5555/2188385.2188386,
author = {Ying, Yiming and Li, Peng},
title = {Distance Metric Learning with Eigenvalue Optimization},
year = {2012},
issue_date = {3/1/2012},
publisher = {JMLR.org},
volume = {13},
number = {null},
issn = {1532-4435},
abstract = {The main theme of this paper is to develop a novel eigenvalue optimization framework for learning a Mahalanobis metric. Within this context, we introduce a novel metric learning approach called DML-eig which is shown to be equivalent to a well-known eigenvalue optimization problem called minimizing the maximal eigenvalue of a symmetric matrix (Overton, 1988; Lewis and Overton, 1996). Moreover, we formulate LMNN (Weinberger et al., 2005), one of the state-of-the-art metric learning methods, as a similar eigenvalue optimization problem. This novel framework not only provides new insights into metric learning but also opens new avenues to the design of efficient metric learning algorithms. Indeed, first-order algorithms are developed for DML-eig and LMNN which only need the computation of the largest eigenvector of a matrix per iteration. Their convergence characteristics are rigorously established. Various experiments on benchmark data sets show the competitive performance of our new approaches. In addition, we report an encouraging result on a difficult and challenging face verification data set called Labeled Faces in the Wild (LFW).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–26},
numpages = {26},
keywords = {face verification, matrix factorization, first-order methods, metric learning, semi-definite programming, convex optimization, eigenvalue optimization}
}

@article{10.5555/1953048.2185804,
author = {Patra, Beno\^{\i}t},
title = {Convergence of Distributed Asynchronous Learning Vector Quantization Algorithms},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {Motivated by the problem of effectively executing clustering algorithms on very large data sets, we address a model for large scale distributed clustering methods. To this end, we briefly recall some standards on the quantization problem and some results on the almost sure convergence of the competitive learning vector quantization (CLVQ) procedure. A general model for linear distributed asynchronous algorithms well adapted to several parallel computing architectures is also discussed. Our approach brings together this scalable model and the CLVQ algorithm, and we call the resulting technique the distributed asynchronous learning vector quantization algorithm (DALVQ). An in-depth analysis of the almost sure convergence of the DALVQ algorithm is performed. A striking result is that we prove that the multiple versions of the quantizers distributed among the processors in the parallel architecture asymptotically reach a consensus almost surely. Furthermore, we also show that these versions converge almost surely towards the

license_type: permissive

branch_name: refs/heads/main

extension: bib