text:
@article{10.5555/2567709.2567762,
author = {Salleb-Aouissi, Ansaf and Vrain, Christel and Nortet, Cyril and Kong, Xiangrong and Rathod, Vivek and Cassard, Daniel},
title = {QuantMiner for Mining Quantitative Association Rules},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we propose QUANTMINER, a mining quantitative association rules system. This system is based on a genetic algorithm that dynamically discovers "good" intervals in association rules by optimizing both the support and the confidence. The experiments on real and artificial databases have shown the usefulness of QUANTMINER as an interactive, exploratory data mining tool.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3153–3157},
numpages = {5},
keywords = {unsupervised discretization, numerical and categorical attributes, simulated annealing, association rules, genetic algorithm}
}

@article{10.5555/2567709.2567761,
author = {Talwalkar, Ameet and Kumar, Sanjiv and Mohri, Mehryar and Rowley, Henry},
title = {Large-Scale SVD and Manifold Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This paper examines the efficacy of sampling-based low-rank approximation techniques when applied to large dense kernel matrices. We analyze two common approximate singular value decomposition techniques, namely the Nystr\"{o}m and Column sampling methods. We present a theoretical comparison between these two methods, provide novel insights regarding their suitability for various tasks and present experimental results that support our theory. Our results illustrate the relative strengths of each method. We next examine the performance of these two techniques on the large-scale task of extracting low-dimensional manifold structure given millions of high-dimensional face images. We address the computational challenges of non-linear dimensionality reduction via Isomap and Laplacian Eigenmaps, using a graph containing about 18 million nodes and 65 million edges. We present extensive experiments on learning low-dimensional embeddings for two large face data sets: CMU-PIE (35 thousand faces) and a web data set (18 million faces). Our comparisons show that the Nystr\"{o}m approximation is superior to the Column sampling method for this task. Furthermore, approximate Isomap tends to perform better than Laplacian Eigenmaps on both clustering and classification with the labeled CMU-PIE data set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3129–3152},
numpages = {24},
keywords = {large-scale matrix factorization, manifold learning, low-rank approximation}
}

@article{10.5555/2567709.2567760,
author = {Long, Philip M. and Servedio, Rocco A.},
title = {Algorithms and Hardness Results for Parallel Large Margin Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of learning an unknown large-margin halfspace in the context of parallel computation, giving both positive and negative results.As our main positive result, we give a parallel algorithm for learning a large-margin half-space, based on an algorithm of Nesterov's that performs gradient descent with a momentum term. We show that this algorithm can learn an unknown γ-margin halfspace over n dimensions using n undefined poly(1/γ) processors and running in time \~{O}(1/γ)+O(log n). In contrast, naive parallel algorithms that learn a γ-margin halfspace in time that depends polylogarithmically on n have an inverse quadratic running time dependence on the margin parameter γ.Our negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We prove that in the original PAC framework, in which a weak learning algorithm is provided as an oracle that is called by the booster, boosting cannot be parallelized. More precisely, we show that, if the algorithm is allowed to call the weak learner multiple times in parallel within a single boosting stage, this ability does not reduce the overall number of successive stages of boosting needed for learning by even a single stage. Our proof is information-theoretic and does not rely on unproven assumptions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3105–3128},
numpages = {24},
keywords = {halfspace learning, linear classifiers, PAC learning, parallel learning algorithms}
}

@article{10.5555/2567709.2567759,
author = {He, Yuejia and She, Yiyuan and Wu, Dapeng},
title = {Stationary-Sparse Causality Network Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Recently, researchers have proposed penalized maximum likelihood to identify network topology underlying a dynamical system modeled by multivariate time series. The time series of interest are assumed to be stationary, but this restriction is never taken into consideration by existing estimation methods. Moreover, practical problems of interest may have ultra-high dimensionality and obvious node collinearity. In addition, none of the available algorithms provides a probabilistic measure of the uncertainty for the obtained network topology which is informative in reliable network identification. The main purpose of this paper is to tackle these challenging issues. We propose the S2 learning framework, which stands for stationary-sparse network learning. We propose a novel algorithm referred to as the Berhu iterative sparsity pursuit with stationarity (BISPS), where the Berhu regularization can improve the Lasso in detection and estimation. The algorithm is extremely easy to implement, efficient in computation and has a theoretical guarantee to converge to a global optimum. We also incorporate a screening technique into BISPS to tackle ultra-high dimensional problems and enhance computational efficiency. Furthermore, a stationary bootstrap technique is applied to provide connection occurring frequency for reliable topology learning. Experiments show that our method can achieve stationary and sparse causality network learning and is scalable for high-dimensional problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3073–3104},
numpages = {32},
keywords = {stationarity, sparsity, bootstrap, screening, Berhu}
}

@article{10.5555/2567709.2567758,
author = {Hyttinen, Antti and Eberhardt, Frederick and Hoyer, Patrik O.},
title = {Experiment Selection for Causal Discovery},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Randomized controlled experiments are often described as the most reliable tool available to scientists for discovering causal relationships among quantities of interest. However, it is often unclear how many and which different experiments are needed to identify the full (possibly cyclic) causal structure among some given (possibly causally insufficient) set of variables. Recent results in the causal discovery literature have explored various identifiability criteria that depend on the assumptions one is able to make about the underlying causal process, but these criteria are not directly constructive for selecting the optimal set of experiments. Fortunately, many of the needed constructions already exist in the combinatorics literature, albeit under terminology which is unfamiliar to most of the causal discovery community. In this paper we translate the theoretical results and apply them to the concrete problem of experiment selection. For a variety of settings we give explicit constructions of the optimal set of experiments and adapt some of the general combinatorics results to answer questions relating to the problem of experiment selection.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3041–3071},
numpages = {31},
keywords = {experiment selection, randomized experiments, cut-coverings, causality, completely separating systems, separating systems}
}

@article{10.5555/2567709.2567757,
author = {Tong, Xin},
title = {A Plug-in Approach to Neyman-Pearson Classification},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The Neyman-Pearson (NP) paradigm in binary classification treats type I and type II errors with different priorities. It seeks classifiers that minimize type II error, subject to a type I error constraint under a user specified level α. In this paper, plug-in classifiers are developed under the NP paradigm. Based on the fundamental Neyman-Pearson Lemma, we propose two related plug-in classifiers which amount to thresholding respectively the class conditional density ratio and the regression function. These two classifiers handle different sampling schemes. This work focuses on theoretical properties of the proposed classifiers; in particular, we derive oracle inequalities that can be viewed as finite sample versions of risk bounds. NP classification can be used to address anomaly detection problems, where asymmetry in errors is an intrinsic property. As opposed to a common practice in anomaly detection that consists of thresholding normal class density, our approach does not assume a specific form for anomaly distributions. Such consideration is particularly necessary when the anomaly class density is far from uniformly distributed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3011–3040},
numpages = {30},
keywords = {Neyman-Pearson paradigm, plug-in approach, oracle inequality, anomaly detection, nonparametric statistics}
}

@article{10.5555/2567709.2567756,
author = {Gong, Pinghua and Ye, Jieping and Zhang, Changshui},
title = {Multi-Stage Multi-Task Feature Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Multi-task sparse feature learning aims to improve the generalization performance by exploiting the shared features among tasks. It has been successfully applied to many applications including computer vision and biomedical informatics. Most of the existing multi-task sparse feature learning algorithms are formulated as a convex sparse regularization problem, which is usually suboptimal, due to its looseness for approximating an l0-type regularizer. In this paper, we propose a non-convex formulation for multi-task sparse feature learning based on a novel nonconvex regularizer. To solve the non-convex optimization problem, we propose a Multi-Stage Multi-Task Feature Learning (MSMTFL) algorithm; we also provide intuitive interpretations, detailed convergence and reproducibility analysis for the proposed algorithm. Moreover, we present a detailed theoretical analysis showing that MSMTFL achieves a better parameter estimation error bound than the convex formulation. Empirical studies on both synthetic and real-world data sets demonstrate the effectiveness of MSMTFL in comparison with the state of the art multi-task sparse feature learning algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2979–3010},
numpages = {32},
keywords = {non-convex, sparse learning, multi-stage, multi-task learning}
}

@article{10.5555/2567709.2567755,
author = {Lin, Binbin and He, Xiaofei and Zhang, Chiyuan and Ji, Ming},
title = {Parallel Vector Field Embedding},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel local isometry based dimensionality reduction method from the perspective of vector fields, which is called parallel vector field embedding (PFE). We first give a discussion on local isometry and global isometry to show the intrinsic connection between parallel vector fields and isometry. The problem of finding an isometry turns out to be equivalent to finding orthonormal parallel vector fields on the data manifold. Therefore, we first find orthonormal parallel vector fields by solving a variational problem on the manifold. Then each embedding function can be obtained by requiring its gradient field to be as close to the corresponding parallel vector field as possible. Theoretical results show that our method can precisely recover the manifold if it is isometric to a connected open subset of Euclidean space. Both synthetic and real data examples demonstrate the effectiveness of our method even if there is heavy noise and high curvature.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2945–2977},
numpages = {33},
keywords = {covariant derivative, manifold learning, isometry, out-of-sample extension, vector field}
}

@article{10.5555/2567709.2567754,
author = {Chaudhuri, Kamalika and Sarwate, Anand D. and Sinha, Kaushik},
title = {A Near-Optimal Algorithm for Differentially-Private Principal Components},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The principal components analysis (PCA) algorithm is a standard tool for identifying good low-dimensional approximations to high-dimensional data. Many data sets of interest contain private or sensitive information about individuals. Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs. Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs. In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output. We show that the sample complexity of the proposed method differs from the existing procedure in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling. We furthermore illustrate our results, showing that on real data there is a large performance gap between the existing method and our method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2905–2943},
numpages = {39},
keywords = {dimension reduction, differential privacy, principal components analysis}
}

@article{10.5555/2567709.2567753,
author = {Wang, Niya and Meng, Fan and Chen, Li and Madhavan, Subha and Clarke, Robert and Hoffman, Eric P. and Xuan, Jianhua and Wang, Yue},
title = {The CAM Software for Nonnegative Blind Source Separation in R-Java},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We describe a R-Java CAM (convex analysis of mixtures) package that provides comprehensive analytic functions and a graphic user interface (GUI) for blindly separating mixed nonnegative sources. This open-source multiplatform software implements recent and classic algorithms in the literature including Chan et al. (2008), Wang et al. (2010), Chen et al. (2011a) and Chen et al. (2011b). The CAM package offers several attractive features: (1) instead of using proprietary MATLAB, its analytic functions are written in R, which makes the codes more portable and easier to modify; (2) besides producing and plotting results in R, it also provides a Java GUI for automatic progress update and convenient visual monitoring; (3) multi-thread interactions between the R and Java modules are driven and integrated by a Java GUI, assuring that the whole CAM software runs responsively; (4) the package offers a simple mechanism to allow others to plug-in additional R-functions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2899–2903},
numpages = {5},
keywords = {information-based model selection, affinity propagation clustering, convex analysis of mixtures, compartment modeling, blind source separation}
}

@article{10.5555/2567709.2567752,
author = {Opper, Manfred and Paquet, Ulrich and Winther, Ole},
title = {Perturbative Corrections for Approximate Inference in Gaussian Latent Variable Models},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Expectation Propagation (EP) provides a framework for approximate inference. When the model under consideration is over a latent Gaussian field, with the approximation being Gaussian, we show how these approximations can systematically be corrected. A perturbative expansion is made of the exact but intractable correction, and can be applied to the model's partition function and other moments of interest. The correction is expressed over the higher-order cumulants which are neglected by EP's local matching of moments. Through the expansion, we see that EP is correct to first order. By considering higher orders, corrections of increasing polynomial complexity can be applied to the approximation. The second order provides a correction in quadratic time, which we apply to an array of Gaussian process and Ising models. The corrections generalize to arbitrarily complex approximating families, which we illustrate on tree-structured Ising model approximations. Furthermore, they provide a polynomial-time assessment of the approximation error. We also provide both theoretical and practical insights on the exactness of the EP solution.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2857–2898},
numpages = {42},
keywords = {expectation consistent inference, Wick expansions, perturbation correction, expectation propagation, Gaussian process, Ising model}
}

@article{10.5555/2567709.2567751,
author = {Ryabko, Daniil and Mary, J\'{e}r\'{e}mie},
title = {A Binary-Classification-Based Metric between Time-Series Distributions and Its Use in Statistical and Learning Problems},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {A metric between time-series distributions is proposed that can be evaluated using binary classification methods, which were originally developed to work on i.i.d. data. It is shown how this metric can be used for solving statistical problems that are seemingly unrelated to classification and concern highly dependent time series. Specifically, the problems of time-series clustering, homogeneity testing and the three-sample problem are addressed. Universal consistency of the resulting algorithms is proven under most general assumptions. The theoretical results are illustrated with experiments on synthetic and real-world data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2837–2856},
numpages = {20},
keywords = {stationary ergodic, clustering, time series, reductions, metrics between probability distributions}
}

@article{10.5555/2567709.2567750,
author = {Noorshams, Nima and Wainwright, Martin J.},
title = {Belief Propagation for Continuous State Spaces: Stochastic Message-Passing with Quantitative Guarantees},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The sum-product or belief propagation (BP) algorithm is a widely used message-passing technique for computing approximate marginals in graphical models. We introduce a new technique, called stochastic orthogonal series message-passing (SOSMP), for computing the BP fixed point in models with continuous random variables. It is based on a deterministic approximation of the messages via orthogonal series basis expansion, and a stochastic estimation of the basis coefficients via Monte Carlo techniques and damped updates. We prove that the SOSMP iterates converge to a δ-neighborhood of the unique BP fixed point for any tree-structured graph, and for any graphs with cycles in which the BP updates satisfy a contractivity condition. In addition, we demonstrate how to choose the number of basis coefficients as a function of the desired approximation accuracy δ and smoothness of the compatibility functions. We illustrate our theory with both simulated examples and in application to optical flow estimation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2799–2835},
numpages = {37},
keywords = {graphical models, stochastic approximation, sum-product for continuous state spaces, low-complexity belief propagation, Monte Carlo methods, orthogonal basis expansion}
}

@article{10.5555/2567709.2567749,
author = {Brakel, Phil\'{e}mon and Stroobandt, Dirk and Schrauwen, Benjamin},
title = {Training Energy-Based Models for Time-Series Imputation},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Imputing missing values in high dimensional time-series is a difficult problem. This paper presents a strategy for training energy-based graphical models for imputation directly, bypassing difficulties probabilistic approaches would face. The training strategy is inspired by recent work on optimization-based learning (Domke, 2012) and allows complex neural models with convolutional and recurrent structures to be trained for imputation tasks. In this work, we use this training strategy to derive learning rules for three substantially different neural architectures. Inference in these models is done by either truncated gradient descent or variational mean-field iterations. In our experiments, we found that the training methods outperform the Contrastive Divergence learning algorithm. Moreover, the training methods can easily handle missing values in the training data itself during learning. We demonstrate the performance of this learning scheme and the three models we introduce on one artificial and two real-world data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2771–2797},
numpages = {27},
keywords = {energy-based models, time-series, neural networks, optimization, missing values}
}

@article{10.5555/2567709.2567748,
author = {Wang, Shusen and Zhang, Zhihua},
title = {Improving CUR Matrix Decomposition and the Nystr\"{o}m Approximation via Adaptive Sampling},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The CUR matrix decomposition and the Nystr\"{o}m approximation are two important low-rank matrix approximation techniques. The Nystr\"{o}m method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nystr\"{o}m approximation.In this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nystr\"{o}m algorithms with expected relative-error bounds. The proposed CUR and Nystr\"{o}m algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nystr\"{o}m method and the ensemble Nystr\"{o}m method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2729–2769},
numpages = {41},
keywords = {randomized algorithms, the Nystr\"{o}m method, adaptive sampling, CUR matrix decomposition, large-scale matrix computation}
}

@article{10.5555/2567709.2567747,
author = {Aravkin, Aleksandr Y. and Burke, James V. and Pillonetto, Gianluigi},
title = {Sparse/Robust Estimation and Kalman Smoothing with Nonsmooth Log-Concave Densities: Modeling, Computation, and Theory},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We introduce a new class of quadratic support (QS) functions, many of which already play a crucial role in a variety of applications, including machine learning, robust statistical inference, sparsity promotion, and inverse problems such as Kalman smoothing. Well known examples of QS penalties include the l2, Huber, l1 and Vapnik losses. We build on a dual representation for QS functions, using it to characterize conditions necessary to interpret these functions as negative logs of true probability densities. This interpretation establishes the foundation for statistical modeling with both known and new QS loss functions, and enables construction of non-smooth multivariate distributions with specified means and variances from simple scalar building blocks.The main contribution of this paper is a flexible statistical modeling framework for a variety of learning applications, together with a toolbox of efficient numerical methods for estimation. In particular, a broad subclass of QS loss functions known as piecewise linear quadratic (PLQ) penalties has a dual representation that can be exploited to design interior point (IP) methods. IP methods solve nonsmooth optimization problems by working directly with smooth systems of equations characterizing their optimality. We provide several numerical examples, along with a code that can be used to solve general PLQ problems.The efficiency of the IP approach depends on the structure of particular applications. We consider the class of dynamic inverse problems using Kalman smoothing. This class comprises a wide variety of applications, where the aim is to reconstruct the state of a dynamical system with known process and measurement models starting from noisy output samples. In the classical case, Gaussian errors are assumed both in the process and measurement models for such problems. We show that the extended framework allows arbitrary PLQ densities to be used, and that the proposed IP approach solves the generalized Kalman smoothing problem while maintaining the linear complexity in the size of the time series, just as in the Gaussian case. This extends the computational efficiency of the Mayne-Fraser and Rauch-Tung-Striebel algorithms to a much broader nonsmooth setting, and includes many recently proposed robust and sparse smoothers as special cases.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2689–2728},
numpages = {40},
keywords = {nonsmooth optimization, interior point methods, Kalman smoothing, convex analysis, statistical modeling, robust inference, sparsity optimization}
}

@article{10.5555/2567709.2567746,
author = {Niu, Gang and Dai, Bo and Shang, Lin and Sugiyama, Masashi},
title = {Maximum Volume Clustering: A New Discriminative Clustering Approach},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The large volume principle proposed by Vladimir Vapnik, which advocates that hypotheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a new discriminative clustering model based on the large volume principle called maximum volume clustering (MVC), and then propose two approximation schemes to solve this MVC model: A soft-label MVC method using sequential quadratic programming and a hard-label MVC method using semi-definite programming, respectively. The proposed MVC is theoretically advantageous for three reasons. The optimization involved in hard-label MVC is convex, and under mild conditions, the optimization involved in soft-label MVC is akin to a convex one in terms of the resulting clusters. Secondly, the soft-label MVC method possesses a clustering error bound. Thirdly, MVC includes the optimization problems of a spectral clustering, two relaxed k-means clustering and an information-maximization clustering as special limit cases when its regularization parameter goes to infinity. Experiments on several artificial and benchmark data sets demonstrate that the proposed MVC compares favorably with state-of-the-art clustering methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2641–2687},
numpages = {47},
keywords = {discriminative clustering, finite sample stability, semi-definite programming, clustering error bound, large volume principle, sequential quadratic programming}
}

@article{10.5555/2567709.2567745,
author = {Fanello, Sean Ryan and Gori, Ilaria and Metta, Giorgio and Odone, Francesca},
title = {Keep It Simple and Sparse: Real-Time Action Recognition},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Sparsity has been showed to be one of the most important properties for visual recognition purposes. In this paper we show that sparse representation plays a fundamental role in achieving one-shot learning and real-time recognition of actions. We start off from RGBD images, combine motion and appearance cues and extract state-of-the-art features in a computationally efficient way. The proposed method relies on descriptors based on 3D Histograms of Scene Flow (3DHOFs) and Global Histograms of Oriented Gradient (GHOGs); adaptive sparse coding is applied to capture high-level patterns from data. We then propose a simultaneous on-line video segmentation and recognition of actions using linear SVMs. The main contribution of the paper is an effective real-time system for one-shot action modeling and recognition; the paper highlights the effectiveness of sparse coding techniques to represent 3D actions. We obtain very good results on three different data sets: a benchmark data set for one-shot action learning (the ChaLearn Gesture Data Set), an in-house data set acquired by a Kinect sensor including complex actions and gestures differing by small details, and a data set created for human-robot interaction purposes. Finally we demonstrate that our system is effective also in a human-robot interaction setting and propose a memory game, "All Gestures You Can", to be played against a humanoid robot.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2617–2640},
numpages = {24},
keywords = {one-shot action learning, human robot interaction, real-time action recognition, sparse representation}
}

@article{10.5555/2567709.2567744,
author = {Gonen, Alon and Sabato, Sivan and Shalev-Shwartz, Shai},
title = {Efficient Active Learning of Halfspaces: An Aggressive Approach},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches. Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2583–2615},
numpages = {33},
keywords = {active learning, adaptive sub-modularity, linear classifiers, margin}
}

@article{10.5555/2567709.2567743,
author = {Wan, Jun and Ruan, Qiuqi and Li, Wei and Deng, Shuang},
title = {One-Shot Learning Gesture Recognition from RGB-D Data Using Bag of Features},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {For one-shot learning gesture recognition, two important challenges are: how to extract distinctive features and how to learn a discriminative model from only one training sample per gesture class. For feature extraction, a new spatio-temporal feature representation called 3D enhanced motion scale-invariant feature transform (3D EMoSIFT) is proposed, which fuses RGB-D data. Compared with other features, the new feature set is invariant to scale and rotation, and has more compact and richer visual representations. For learning a discriminative model, all features extracted from training samples are clustered with the k-means algorithm to learn a visual codebook. Then, unlike the traditional bag of feature (BoF) models using vector quantization (VQ) to map each feature into a certain visual codeword, a sparse coding method named simulation orthogonal matching pursuit (SOMP) is applied and thus each feature can be represented by some linear combination of a small number of codewords. Compared with VQ, SOMP leads to a much lower reconstruction error and achieves better performance. The proposed approach has been evaluated on ChaLearn gesture database and the result has been ranked amongst the top best performing techniques on ChaLearn gesture challenge (round 2).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2549–2582},
numpages = {34},
keywords = {one-shot learning, 3D enhanced motion scale invariant feature transform (3D EMoSIFT), gesture recognition, simulation orthogonal matching pursuit (SOMP), bag of features (BoF) model}
}

@article{10.5555/2567709.2567742,
author = {Wu, Wei and Lu, Zhengdong and Li, Hang},
title = {Learning Bilinear Model for Matching Queries and Documents},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The task of matching data from two heterogeneous domains naturally arises in various areas such as web search, collaborative filtering, and drug design. In web search, existing work has designed relevance models to match queries and documents by exploiting either user clicks or content of queries and documents. To the best of our knowledge, however, there has been little work on principled approaches to leveraging both clicks and content to learn a matching model for search. In this paper, we propose a framework for learning to match heterogeneous objects. The framework learns two linear mappings for two objects respectively, and matches them via the dot product of their images after mapping. Moreover, when different regularizations are enforced, the framework renders a rich family of matching models. With orthonormal constraints on mapping functions, the framework subsumes Partial Least Squares (PLS) as a special case. Alternatively, with a l1+l2 regularization, we obtain a new model called Regularized Mapping to Latent Structures (RMLS). RMLS enjoys many advantages over PLS, including lower time complexity and easy parallelization. To further understand the matching framework, we conduct generalization analysis and apply the result to both PLS and RMLS. We apply the framework to web search and implement both PLS and RMLS using a click-through bipartite with metadata representing features of queries and documents. We test the efficacy and scalability of RMLS and PLS on large scale web search problems. The results show that both PLS and RMLS can significantly outperform baseline methods, while RMLS substantially speeds up the learning process.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2519–2548},
numpages = {30},
keywords = {generalization analysis, partial least squares, regularized mapping to latent structures, web search}
}

@article{10.5555/2567709.2567741,
author = {Dyer, Eva L. and Sankaranarayanan, Aswin C. and Baraniuk, Richard G.},
title = {Greedy Feature Selection for Subspace Clustering},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Unions of subspaces provide a powerful generalization of single subspace models for collections of high-dimensional data; however, learning multiple subspaces from data is challenging due to the fact that segmentation--the identification of points that live in the same subspace--and subspace estimation must be performed simultaneously. Recently, sparse recovery methods were shown to provide a provable and robust strategy for exact feature selection (EFS)--recovering subsets of points from the ensemble that live in the same subspace. In parallel with recent studies of EFS with l1-minimization, in this paper, we develop sufficient conditions for EFS with a greedy method for sparse signal recovery known as orthogonal matching pursuit (OMP). Following our analysis, we provide an empirical study of feature selection strategies for signals living on unions of subspaces and characterize the gap between sparse recovery methods and nearest neighbor (NN)-based approaches. In particular, we demonstrate that sparse recovery methods provide significant advantages over NN methods and that the gap between the two approaches is particularly pronounced when the sampling of subspaces in the data set is sparse. Our results suggest that OMP may be employed to reliably recover exact feature sets in a number of regimes where NN approaches fail to reveal the subspace membership of points in the ensemble.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2487–2517},
numpages = {31},
keywords = {nearest neighbors, hybrid linear models, low-rank approximation, structured sparsity, subspace clustering, unions of subspaces, sparse approximation}
}

@article{10.5555/2567709.2567740,
author = {Mairal, Julien and Yu, Bin},
title = {Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider supervised learning problems where the features are embedded in a graph, such as gene expressions in a gene network. In this context, it is of much interest to automatically select a subgraph with few connected components; by exploiting prior knowledge, one can indeed improve the prediction performance or obtain results that are easier to interpret. Regularization or penalty functions for selecting features in graphs have recently been proposed, but they raise new algorithmic challenges. For example, they typically require solving a combinatorially hard selection problem among all connected subgraphs. In this paper, we propose computationally feasible strategies to select a sparse and well-connected subset of features sitting on a directed acyclic graph (DAG). We introduce structured sparsity penalties over paths on a DAG called "path coding" penalties. Unlike existing regularization functions that model long-range interactions between features in a graph, path coding penalties are tractable. The penalties and their proximal operators involve path selection problems, which we efficiently solve by leveraging network flow optimization. We experimentally show on synthetic, image, and genomic data that our approach is scalable and leads to more connected subgraphs than other regularization functions for graphs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2449–2485},
numpages = {37},
keywords = {convex and non-convex optimization, network flow optimization, graph sparsity}
}

@article{10.5555/2567709.2567739,
author = {Verma, Nakul},
title = {Distance Preserving Embeddings for General N-Dimensional Manifolds},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Low dimensional embeddings of manifold data have gained popularity in the last decade. However, a systematic finite sample analysis of manifold embedding algorithms largely eludes researchers. Here we present two algorithms that embed a general n-dimensionalmanifold into Rd (where d only depends on some key manifold properties such as its intrinsic dimension, volume and curvature) that guarantee to approximately preserve all interpoint geodesic distances.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2415–2448},
numpages = {34},
keywords = {non-linear dimensionality reduction, Nash's embedding theorem, isometric embeddings, manifold learning}
}

@article{10.5555/2567709.2567738,
author = {Guyader, Arnaud and Hengartner, Nick},
title = {On the Mutual Nearest Neighbors Estimate in Regression},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Motivated by promising experimental results, this paper investigates the theoretical properties of a recently proposed nonparametric estimator, called the Mutual Nearest Neighbors rule, which estimates the regression function m(x) = E[Y|X = x] as follows: first identify the k nearest neighbors of x in the sample Dn, then keep only those for which x is itself one of the k nearest neighbors, and finally take the average over the corresponding response variables. We prove that this estimator is consistent and that its rate of convergence is optimal. Since the estimate with the optimal rate of convergence depends on the unknown distribution of the observations, we also present adaptation results by data-splitting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2361–2376},
numpages = {16},
keywords = {nonparametric estimation, nearest neighbor methods, mathematical statistics}
}

@article{10.5555/2567709.2567737,
author = {Lisitsyn, Sergey and Widmer, Christian and Garcia, Fernando J. Iglesias},
title = {Tapkee: An Efficient Dimension Reduction Library},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present Tapkee, a C++ template library that provides efficient implementations of more than 20 widely used dimensionality reduction techniques ranging from Locally Linear Embedding (Roweis and Saul, 2000) and Isomap (de Silva and Tenenbaum, 2002) to the recently introduced Barnes-Hut-SNE (van der Maaten, 2013). Our library was designed with a focus on performance and flexibility. For performance, we combine efficient multi-core algorithms, modern data structures and state-of-the-art low-level libraries. To achieve flexibility, we designed a clean interface for applying methods to user data and provide a callback API that facilitates integration with the library. The library is freely available as open-source software and is distributed under the permissive BSD 3-clause license. We encourage the integration of Tapkee into other open-source toolboxes and libraries. For example, Tapkee has been integrated into the codebase of the Shogun toolbox (Sonnenburg et al., 2010), giving us access to a rich set of kernels, distance measures and bindings to common programming languages including Python, Octave, Matlab, R, Java, C#, Ruby, Perl and Lua. Source code, examples and documentation are available at http://tapkee.lisitsyn.me.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2355–2359},
numpages = {5},
keywords = {dimensionality reduction, C++, machine learning, open source software}
}

@article{10.5555/2567709.2567736,
author = {Dem\v{s}ar, Janez and Curk, Toma\v{z} and Erjavec, Ale\v{s} and Gorup, \v{C}rt and Ho\v{c}evar, Toma\v{z} and Milutinovi\v{c}, Mitar and Mo\v{z}ina, Martin and Polajnar, Matija and Toplak, Marko and Stari\v{c}, An\v{z}e and \v{S}tajdohar, Miha and Umek, Lan and \v{Z}agar, Lan and \v{Z}bontar, Jure and \v{Z}itnik, Marinka and Zupan, Bla\v{z}},
title = {Orange: Data Mining Toolbox in Python},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Orange is a machine learning and data mining suite for data analysis through Python scripting and visual programming. Here we report on the scripting part, which features interactive data analysis and component-based assembly of data mining procedures. In the selection and design of components, we focus on the flexibility of their reuse: our principal intention is to let the user write simple and clear scripts in Python, which build upon C++ implementations of computationally-intensive tasks. Orange is intended both for experienced users and programmers, as well as for students of data mining.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2349–2353},
numpages = {5},
keywords = {machine learning, data mining, scripting, toolbox, python}
}

@article{10.5555/2567709.2567735,
author = {Mukherjee, Indraneel and Rudin, Cynthia and Schapire, Robert E.},
title = {The Rate of Convergence of AdaBoost},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The AdaBoost algorithm was designed to combine many "weak" hypotheses that perform slightly better than random guessing into a "strong" hypothesis that has very low error. We study the rate at which AdaBoost iteratively converges to the minimum of the "exponential loss." Unlike previous work, our proofs do not require a weak-learning assumption, nor do they require that minimizers of the exponential loss are finite. Our first result shows that the exponential loss of AdaBoost's computed parameter vector will be at most e more than that of any parameter vector of l1-norm bounded by B in a number of rounds that is at most a polynomial in B and 1/ε. We also provide lower bounds showing that a polynomial dependence is necessary. Our second result is that within C/ε iterations, AdaBoost achieves a value of the exponential loss that is at most e more than the best possible value, where C depends on the data set. We show that this dependence of the rate on ε is optimal up to constant factors, that is, at least Ω(1/ε) rounds are necessary to achieve within ε of the optimal exponential loss.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2315–2347},
numpages = {33},
keywords = {optimization, coordinate descent, convergence rate, AdaBoost}
}

@article{10.5555/2567709.2567734,
author = {Ruozzi, Nicholas and Tatikonda, Sekhar},
title = {Message-Passing Algorithms for Quadratic Minimization},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Gaussian belief propagation (GaBP) is an iterative algorithm for computing the mean (and variances) of a multivariate Gaussian distribution, or equivalently, the minimum of a multivariate positive definite quadratic function. Sufficient conditions, such as walk-summability, that guarantee the convergence and correctness of GaBP are known, but GaBP may fail to converge to the correct solution given an arbitrary positive definite covariance matrix. As was observed by Malioutov et al. (2006), the GaBP algorithm fails to converge if the computation trees produced by the algorithm are not positive definite. In this work, we will show that the failure modes of the GaBP algorithm can be understood via graph covers, and we prove that a parameterized generalization of the min-sum algorithm can be used to ensure that the computation trees remain positive definite whenever the input matrix is positive definite. We demonstrate that the resulting algorithm is closely related to other iterative schemes for quadratic minimization such as the Gauss-Seidel and Jacobi algorithms. Finally, we observe, empirically, that there always exists a choice of parameters such that the above generalization of the GaBP algorithm converges.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2287–2314},
numpages = {28},
keywords = {belief propagation, graph covers, Gaussian graphical models}
}

@article{10.5555/2567709.2567733,
author = {Challis, Edward and Barber, David},
title = {Gaussian Kullback-Leibler Approximate Inference},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We investigate Gaussian Kullback-Leibler (G-KL) variational approximate inference techniques for Bayesian generalised linear models and various extensions. In particular we make the following novel contributions: sufficient conditions for which the G-KL objective is differentiable and convex are described; constrained parameterisations of Gaussian covariance that make G-KL methods fast and scalable are provided; the lower bound to the normalisation constant provided by G-KL methods is proven to dominate those provided by local lower bounding methods; complexity and model applicability issues of G-KL versus other Gaussian approximate inference methods are discussed. Numerical results comparing G-KL and other deterministic Gaussian approximate inference methods are presented for: robust Gaussian process regression models with either Student-t or Laplace likelihoods, large scale Bayesian binary logistic regression models, and Bayesian sparse linear models for sequential experimental design.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2239–2286},
numpages = {48},
keywords = {Gaussian processes, variational approximate inference, generalised linear models, experimental design, large scale inference, latent linear models, sparse learning, active learning}
}

@article{10.5555/2567709.2567732,
author = {Stowell, Dan and Plumbley, Mark D.},
title = {Segregating Event Streams and Noise with a Markov Renewal Process Model},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We describe an inference task in which a set of timestamped event observations must be clustered into an unknown number of temporal sequences with independent and varying rates of observations. Various existing approaches to multi-object tracking assume a fixed number of sources and/or a fixed observation rate; we develop an approach to inferring structure in timestamped data produced by a mixture of an unknown and varying number of similar Markov renewal processes, plus independent clutter noise. The inference simultaneously distinguishes signal from noise as well as clustering signal observations into separate source streams. We illustrate the technique via synthetic experiments as well as an experiment to track a mixture of singing birds. Source code is available.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2213–2238},
numpages = {26},
keywords = {sound, multi-target tracking, flow network, point processes, clustering}
}

@article{10.5555/2567709.2567731,
author = {Malgireddy, Manavender R. and Nwogu, Ifeoma and Govindaraju, Venu},
title = {Language-Motivated Approaches to Action Recognition},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present language-motivated approaches to detecting, localizing and classifying activities and gestures in videos. In order to obtain statistical insight into the underlying patterns of motions in activities, we develop a dynamic, hierarchical Bayesian model which connects low-level visual features in videos with poses, motion patterns and classes of activities. This process is somewhat analogous to the method of detecting topics or categories from documents based on the word content of the documents, except that our documents are dynamic. The proposed generative model harnesses both the temporal ordering power of dynamic Bayesian networks such as hidden Markov models (HMMs) and the automatic clustering power of hierarchical Bayesian models such as the latent Dirichlet allocation (LDA) model. We also introduce a probabilistic framework for detecting and localizing pre-specified activities (or gestures) in a video sequence, analogous to the use of filler models for keyword detection in speech processing. We demonstrate the robustness of our classification model and our spotting framework by recognizing activities in unconstrained real-life video sequences and by spotting gestures via a one-shot-learning approach.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2189–2212},
numpages = {24},
keywords = {topic models, activity recognition, generative models, dynamic hierarchical Bayesian networks, gesture spotting}
}

@article{10.5555/2567709.2567730,
author = {Li, Yu-Feng and Tsang, Ivor W. and Kwok, James T. and Zhou, Zhi-Hua},
title = {Convex and Scalable Weakly Labeled SVMs},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we study the problem of learning from weakly labeled data, where labels of the training examples are incomplete. This includes, for example, (i) semi-supervised learning where labels are partially known; (ii) multi-instance learning where labels are implicitly known; and (iii) clustering where labels are completely unknown. Unlike supervised learning, learning with weak labels involves a difficult Mixed-Integer Programming (MIP) problem. Therefore, it can suffer from poor scalability and may also get stuck in local minimum. In this paper, we focus on SVMs and propose the WELLSVM via a novel label generation strategy. This leads to a convex relaxation of the original MIP, which is at least as tight as existing convex Semi-Definite Programming (SDP) relaxations. Moreover, the WELLSVM can be solved via a sequence of SVM subproblems that are much more scalable than previous convex SDP relaxations. Experiments on three weakly labeled learning tasks, namely, (i) semi-supervised learning; (ii) multi-instance learning for locating regions of interest in content-based information retrieval; and (iii) clustering, clearly demonstrate improved performance, and WELLSVM is also readily applicable on large data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2151–2188},
numpages = {38},
keywords = {convex relaxation, cutting plane, weakly labeled data, clustering, multi-instance learning, semi-supervised learning}
}

@article{10.5555/2567709.2567729,
author = {Sabato, Sivan and Srebro, Nathan and Tishby, Naftali},
title = {Distribution-Dependent Sample Complexity of Large Margin Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on the sample complexity, both governed by the margin-adapted dimension of the data distribution. The upper bounds are universal, and the lower bounds hold for the rich family of sub-Gaussian distributions with independent features. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. To prove the lower bound, we develop several new tools of independent interest. These include new connections between shattering and hardness of learning, new properties of shattering with linear classifiers, and a new lower bound on the smallest eigenvalue of a random Gram matrix generated by sub-Gaussian variables. Our results can be used to quantitatively compare large margin learning to other learning rules, and to improve the effectiveness of methods that use sample complexity bounds, such as active learning.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2119–2149},
numpages = {31},
keywords = {sample complexity, supervised learning, linear classifiers, distribution-dependence}
}

@article{10.5555/2567709.2567728,
author = {B\"{o}hmer, Wendelin and Gr\"{u}new\"{a}lder, Steffen and Shen, Yun and Musial, Marek and Obermayer, Klaus},
title = {Construction of Approximation Spaces for Reinforcement Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Linear reinforcement learning (RL) algorithms like least-squares temporal difference learning (LSTD) require basis functions that span approximation spaces of potential value functions. This article investigates methods to construct these bases from samples. We hypothesize that an ideal approximation spaces should encode diffusion distances and that slow feature analysis (SFA) constructs such spaces. To validate our hypothesis we provide theoretical statements about the LSTD value approximation error and induced metric of approximation spaces constructed by SFA and the state-of-the-art methods Krylov bases and proto-value functions (PVF). In particular, we prove that SFA minimizes the average (over all tasks in the same environment) bound on the above approximation error. Compared to other methods, SFA is very sensitive to sampling and can sometimes fail to encode the whole state space. We derive a novel importance sampling modification to compensate for this effect. Finally, the LSTD and least squares policy iteration (LSPI) performance of approximation spaces constructed by Krylov bases, PVF, SFA and PCA is compared in benchmark tasks and a visual robot navigation experiment (both in a realistic simulation and with a robot). The results support our hypothesis and suggest that (i) SFA provides subspace-invariant features for MDPs with self-adjoint transition operators, which allows strong guarantees on the approximation error, (ii) the modified SFA algorithm is best suited for LSPI in both discrete and continuous state spaces and (iii) approximation spaces encoding diffusion distances facilitate LSPI performance.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2067–2118},
numpages = {52},
keywords = {visual robot navigation, diffusion distance, reinforcement learning, proto value functions, slow feature analysis, least-squares policy iteration}
}

@article{10.5555/2567709.2567727,
author = {Chertkov, Michael and Yedidia, Adam B.},
title = {Approximating the Permanent with Fractional Belief Propagation},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the belief propagation (BP) approach and its fractional belief propagation (FBP) generalization for computing the permanent of a non-negative matrix. Known bounds and Conjectures are verified in experiments, and some new theoretical relations, bounds and Conjectures are proposed. The fractional free energy (FFE) function is parameterized by a scalar parameter γ ∈ [-1;1], where γ = -1 corresponds to the BP limit and γ = 1 corresponds to the exclusion principle (but ignoring perfect matching constraints) mean-field (MF) limit. FFE shows monotonicity and continuity with respect to γ. For every non-negative matrix, we define its special value γ* ∈ [-1;0] to be the γ for which the minimum of the γ-parameterized FFE function is equal to the permanent of the matrix, where the lower and upper bounds of the γ-interval corresponds to respective bounds for the permanent. Our experimental analysis suggests that the distribution of γ* varies for different ensembles but γ* always lies within the [-1;-1/2] interval. Moreover, for all ensembles considered, the behavior of γ* is highly distinctive, offering an empirical practical guidance for estimating permanents of non-negative matrices via the FFE approach.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2029–2066},
numpages = {38},
keywords = {permanent, exact and approximate algorithms, belief propagation, learning flows, graphical models}
}

@article{10.5555/2567709.2567726,
author = {Tulabandhula, Theja and Rudin, Cynthia},
title = {Machine Learning with Operational Costs},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This work proposes a way to align statistical modeling with decision making. We provide a method that propagates the uncertainty in predictive modeling to the uncertainty in operational cost, where operational cost is the amount spent by the practitioner in solving the problem. The method allows us to explore the range of operational costs associated with the set of reasonable statistical models, so as to provide a useful way for practitioners to understand uncertainty. To do this, the operational cost is cast as a regularization term in a learning algorithm's objective function, allowing either an optimistic or pessimistic view of possible costs, depending on the regularization parameter. From another perspective, if we have prior knowledge about the operational cost, for instance that it should be low, this knowledge can help to restrict the hypothesis space, and can help with generalization. We provide a theoretical generalization bound for this scenario. We also show that learning with operational costs is related to robust optimization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1989–2028},
numpages = {40},
keywords = {decision theory, covering numbers, optimization, statistical learning theory}
}

@article{10.5555/2567709.2567725,
author = {Zaidi, Nayyar A. and Cerquides, Jes\'{u}s and Carman, Mark J. and Webb, Geoffrey I.},
title = {Alleviating Naive Bayes Attribute Independence Assumption by Attribute Weighting},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Despite the simplicity of the Naive Bayes classifier, it has continued to perform well against more sophisticated newcomers and has remained, therefore, of great interest to the machine learning community. Of numerous approaches to refining the naive Bayes classifier, attribute weighting has received less attention than it warrants. Most approaches, perhaps influenced by attribute weighting in other machine learning algorithms, use weighting to place more emphasis on highly predictive attributes than those that are less predictive. In this paper, we argue that for naive Bayes attribute weighting should instead be used to alleviate the conditional independence assumption. Based on this premise, we propose a weighted naive Bayes algorithm, called WANBIA, that selects weights to minimize either the negative conditional log likelihood or the mean squared error objective functions. We perform extensive evaluations and find that WANBIA is a competitive alternative to state of the art classifiers like Random Forest, Logistic Regression and A1DE.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1947–1988},
numpages = {42},
keywords = {classification, weighted naive bayes classification, naive bayes, attribute independence assumption}
}

@article{10.5555/2567709.2567724,
author = {Hern\'{a}ndez-Lobato, Daniel and Hern\'{a}ndez-Lobato, Jos\'{e} Miguel and Dupont, Pierre},
title = {Generalized Spike-and-Slab Priors for Bayesian Group Feature Selection Using Expectation Propagation},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We describe a Bayesian method for group feature selection in linear regression problems. The method is based on a generalized version of the standard spike-and-slab prior distribution which is often used for individual feature selection. Exact Bayesian inference under the prior considered is infeasible for typical regression problems. However, approximate inference can be carried out efficiently using Expectation Propagation (EP). A detailed analysis of the generalized spike-and-slab prior shows that it is well suited for regression problems that are sparse at the group level. Furthermore, this prior can be used to introduce prior knowledge about specific groups of features that are a priori believed to be more relevant. An experimental evaluation compares the performance of the proposed method with those of group LASSO, Bayesian group LASSO, automatic relevance determination and additional variants used for group feature selection. The results of these experiments show that a model based on the generalized spike-and-slab prior and the EP algorithm has state-of-the-art prediction performance in the problems analyzed. Furthermore, this model is also very useful to carry out sequential experimental design (also known as active learning), where the data instances that are most informative are iteratively included in the training set, reducing the number of instances needed to obtain a particular level of prediction accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1891–1945},
numpages = {55},
keywords = {approximate inference, expectation propagation, sequential experimental design, generalized spike-and-slab priors, sparse linear model, signal reconstruction, group feature selection}
}

@article{10.5555/2567709.2567723,
author = {Pan, Wei and Shen, Xiaotong and Liu, Binghui},
title = {Cluster Analysis: Unsupervised Learning via Supervised Learning with a Non-Convex Penalty},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Clustering analysis is widely used in many fields. Traditionally clustering is regarded as unsupervised learning for its lack of a class label or a quantitative response variable, which in contrast is present in supervised learning such as classification and regression. Here we formulate clustering as penalized regression with grouping pursuit. In addition to the novel use of a non-convex group penalty and its associated unique operating characteristics in the proposed clustering method, a main advantage of this formulation is its allowing borrowing some well established results in classification and regression, such as model selection criteria to select the number of clusters, a difficult problem in clustering analysis. In particular, we propose using the generalized cross-validation (GCV) based on generalized degrees of freedom (GDF) to select the number of clusters. We use a few simple numerical examples to compare our proposed method with some existing approaches, demonstrating our method's promising performance.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1865–1889},
numpages = {25},
keywords = {K-means clustering, Lasso, grouping, truncated Lasso penalty (TLP), penalized regression, generalized degrees of freedom}
}

@article{10.5555/2567709.2567722,
author = {Cai, Tony and Fan, Jianqing and Jiang, Tiefeng},
title = {Distributions of Angles in Random Packing on Spheres},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This paper studies the asymptotic behaviors of the pairwise angles among n randomly and uniformly distributed unit vectors in Rp as the number of points n → ∞, while the dimension p is either fixed or growing with n. For both settings, we derive the limiting empirical distribution of the random angles and the limiting distributions of the extreme angles. The results reveal interesting differences in the two settings and provide a precise characterization of the folklore that "all high-dimensional random vectors are almost always nearly orthogonal to each other". Applications to statistics and machine learning and connections with some open problems in physics and mathematics are also discussed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1837–1864},
numpages = {28},
keywords = {uniform distribution on sphere, empirical law, extreme-value distribution, maximum of random variables, minimum of random variables, packing on sphere, random angle}
}

@article{10.5555/2567709.2567721,
author = {Urry, Matthew J. and Sollich, Peter},
title = {Random Walk Kernels and Learning Curves for Gaussian Process Regression on Random Graphs},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider learning on graphs, guided by kernels that encode similarity between vertices. Our focus is on random walk kernels, the analogues of squared exponential kernels in Euclidean spaces. We show that on large, locally treelike graphs these have some counter-intuitive properties, specifically in the limit of large kernel lengthscales. We consider using these kernels as covariance functions of Gaussian processes. In this situation one typically scales the prior globally to normalise the average of the prior variance across vertices. We demonstrate that, in contrast to the Euclidean case, this generically leads to significant variation in the prior variance across vertices, which is undesirable from a probabilistic modelling point of view. We suggest the random walk kernel should be normalised locally, so that each vertex has the same prior variance, and analyse the consequences of this by studying learning curves for Gaussian process regression. Numerical calculations as well as novel theoretical predictions for the learning curves using belief propagation show that one obtains distinctly different probabilistic models depending on the choice of normalisation. Our method for predicting the learning curves using belief propagation is significantly more accurate than previous approximations and should become exact in the limit of large random graphs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1801–1835},
numpages = {35},
keywords = {Gaussian process, generalisation error, random walk kernel, cavity method, learning curve, belief propagation, graph}
}

@article{10.5555/2567709.2567720,
author = {Joseph, Antony},
title = {Variable Selection in High-Dimension with Random Designs and Orthogonal Matching Pursuit},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The performance of orthogonal matching pursuit (OMP) for variable selection is analyzed for random designs. When contrasted with the deterministic case, since the performance is here measured after averaging over the distribution of the design matrix, one can have far less stringent sparsity constraints on the coefficient vector. We demonstrate that for exact sparse vectors, the performance of the OMP is similar to known results on the Lasso algorithm (Wainwright, 2009). Moreover, variable selection under a more relaxed sparsity assumption on the coefficient vector, whereby one has only control on the l1 norm of the smaller coefficients, is also analyzed. As consequence of these results, we also show that the coefficient estimate satisfies strong oracle type inequalities.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1771–1800},
numpages = {30},
keywords = {high dimensional regression, greedy algorithms, compressed sensing, lasso}
}

@article{10.5555/2567709.2567719,
author = {Arias-Castro, Ery and Pelletier, Bruno},
title = {On the Convergence of Maximum Variance Unfolding},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Maximum Variance Unfolding is one of the main methods for (nonlinear) dimensionality reduction. We study its large sample limit, providing specific rates of convergence under standard assumptions. We find that it is consistent when the underlying submanifold is isometric to a convex subset, and we provide some simple examples where it fails to be consistent.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1747–1770},
numpages = {24},
keywords = {maximum variance unfolding, empirical processes, proximity graphs, U-processes, isometric embedding}
}

@article{10.5555/2567709.2567718,
author = {Arora, Raman and Gupta, Maya R. and Kapila, Amol and Fazel, Maryam},
title = {Similarity-Based Clustering by Left-Stochastic Matrix Factorization},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {For similarity-based clustering, we propose modeling the entries of a given similarity matrix as the inner products of the unknown cluster probabilities. To estimate the cluster probabilities from the given similarity matrix, we introduce a left-stochastic non-negative matrix factorization problem. A rotation-based algorithm is proposed for the matrix factorization. Conditions for unique matrix factorizations and clusterings are given, and an error bound is provided. The algorithm is particularly efficient for the case of two clusters, which motivates a hierarchical variant for cases where the number of desired clusters is large. Experiments show that the proposed left-stochastic decomposition clustering model produces relatively high within-cluster similarity on most data sets and can match given class labels, and that the efficient hierarchical variant performs surprisingly well.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1715–1746},
numpages = {32},
keywords = {clustering, completely positive, non-negative matrix factorization, similarity, indefinite kernel, rotation}
}

@article{10.5555/2567709.2567717,
author = {Rosasco, Lorenzo and Villa, Silvia and Mosci, Sofia and Santoro, Matteo and Verri, Alessandro},
title = {Nonparametric Sparsity and Regularization},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {In this work we are interested in the problems of supervised learning and variable selection when the input-output dependence is described by a nonlinear function depending on a few variables. Our goal is to consider a sparse nonparametric model, hence avoiding linear or additive models. The key idea is to measure the importance of each variable in the model by making use of partial derivatives. Based on this intuition we propose a new notion of nonparametric sparsity and a corresponding least squares regularization scheme. Using concepts and results from the theory of reproducing kernel Hilbert spaces and proximal methods, we show that the proposed learning algorithm corresponds to a minimization problem which can be provably solved by an iterative procedure. The consistency properties of the obtained estimator are studied both in terms of prediction and selection performance. An extensive empirical analysis shows that the proposed method performs favorably with respect to the state-of-the-art methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1665–1714},
numpages = {50},
keywords = {variable selection, sparsity, RKHS, nonparametric, regularization, proximal methods}
}

@article{10.5555/2567709.2567716,
author = {Roussos, Anastasios and Theodorakis, Stavros and Pitsikalis, Vassilis and Maragos, Petros},
title = {Dynamic Affine-Invariant Shape-Appearance Handshape Features and Classification in Sign Language Videos},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We propose the novel approach of dynamic affine-invariant shape-appearance model (Aff-SAM) and employ it for handshape classification and sign recognition in sign language (SL) videos. Aff-SAM offers a compact and descriptive representation of hand configurations as well as regularized model-fitting, assisting hand tracking and extracting handshape features. We construct SA images representing the hand's shape and appearance without landmark points. We model the variation of the images by linear combinations of eigenimages followed by affine transformations, accounting for 3D hand pose changes and improving model's compactness. We also incorporate static and dynamic handshape priors, offering robustness in occlusions, which occur often in signing. The approach includes an affine signer adaptation component at the visual level, without requiring training from scratch a new singer-specific model. We rather employ a short development data set to adapt the models for a new signer. Experiments on the Boston-University-400 continuous SL corpus demonstrate improvements on handshape classification when compared to other feature extraction approaches. Supplementary evaluations of sign recognition experiments, are conducted on a multi-signer, 100-sign data set, from the Greek sign language lemmas corpus. These explore the fusion with movement cues as well as signer adaptation of Aff-SAM to multiple signers providing promising results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1627–1663},
numpages = {37},
keywords = {static and dynamic priors, affine-invariant shape-appearance model, feature extraction, handshape classification, landmarks-free shape representation}
}

@article{10.5555/2567709.2567715,
author = {Zadeh, Reza Bosagh and Goel, Ashish},
title = {Dimension Independent Similarity Computation},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present a suite of algorithms for Dimension Independent Similarity Computation (DISCO) to compute all pairwise similarities between very high-dimensional sparse vectors. All of our results are provably independent of dimension, meaning that apart from the initial cost of trivially reading in the data, all subsequent operations are independent of the dimension; thus the dimension can be very large. We study Cosine, Dice, Overlap, and the Jaccard similarity measures. For Jaccard similarity we include an improved version of MinHash. Our results are geared toward the MapReduce framework. We empirically validate our theorems with large scale experiments using data from the social networking site Twitter. At time of writing, our algorithms are live in production at twitter.com.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1605–1626},
numpages = {22},
keywords = {cosine, jaccard, similarity, dimension independent, overlap, dice, mapreduce}
}

@article{10.5555/2567709.2567714,
author = {Mahdi, Rami and Mezey, Jason},
title = {Sub-Local Constraint-Based Learning of Bayesian Networks Using a Joint Dependence Criterion},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Constraint-based learning of Bayesian networks (BN) from limited data can lead to multiple testing problems when recovering dense areas of the skeleton and to conflicting results in the orientation of edges. In this paper, we present a new constraint-based algorithm, light mutual min (LMM) for improved accuracy of BN learning from small sample data. LMM improves the assessment of candidate edges by using a ranking criterion that considers conditional independence on neighboring variables at both sides of an edge simultaneously. The algorithm also employs an adaptive relaxation of constraints that, selectively, allows some nodes not to condition on some neighbors. This relaxation aims at reducing the incorrect rejection of true edges connecting high degree nodes due to multiple testing. LMM additionally incorporates a new criterion for ranking v-structures that is used to recover the completed partially directed acyclic graph (CPDAG) and to resolve conflicting v-structures, a common problem in small sample constraint-based learning. Using simulated data, each of these components of LMM is shown to significantly improve network inference compared to commonly applied methods when learning from limited data, including more accurate recovery of skeletons and CPDAGs compared to the PC, MaxMin, and MaxMin hill climbing algorithms. A proof of asymptotic correctness is also provided for LMM for recovering the correct skeleton and CPDAG.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1563–1603},
numpages = {41},
keywords = {constraint-based learning, skeleton, mutual min, Bayesian networks}
}

@article{10.5555/2567709.2567713,
author = {McFowland, Edward and Speakman, Skyler and Neill, Daniel B.},
title = {Fast Generalized Subset Scan for Anomalous Pattern Detection},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We propose Fast Generalized Subset Scan (FGSS), a new method for detecting anomalous patterns in general categorical data sets. We frame the pattern detection problem as a search over subsets of data records and attributes, maximizing a nonparametric scan statistic over all such subsets. We prove that the nonparametric scan statistics possess a novel property that allows for efficient optimization over the exponentially many subsets of the data without an exhaustive search, enabling FGSS to scale to massive and high-dimensional data sets. We evaluate the performance of FGSS in three real-world application domains (customs monitoring, disease surveillance, and network intrusion detection), and demonstrate that FGSS can successfully detect and characterize relevant patterns in each domain. As compared to three other recently proposed detection algorithms, FGSS substantially decreased run time and improved detection power for massive multivariate data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1533–1561},
numpages = {29},
keywords = {scan statistics, Bayesian networks, anomaly detection, pattern detection, knowledge discovery}
}

@article{10.5555/2567709.2567712,
author = {Angluin, Dana and Aspnes, James and Eisenstat, Sarah and Kontorovich, Aryeh},
title = {On the Learnability of Shuffle Ideals},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {PAC learning of unrestricted regular languages is long known to be a difficult problem. The class of shuffle ideals is a very restricted subclass of regular languages, where the shuffle ideal generated by a string u is the collection of all strings containing u as a subsequence. This fundamental language family is of theoretical interest in its own right and provides the building blocks for other important language families. Despite its apparent simplicity, the class of shuffle ideals appears quite difficult to learn. In particular, just as for unrestricted regular languages, the class is not properly PAC learnable in polynomial time if RP ≠ NP, and PAC learning the class improperly in polynomial time would imply polynomial time algorithms for certain fundamental problems in cryptography. In the positive direction, we give an efficient algorithm for properly learning shuffle ideals in the statistical query (and therefore also PAC) model under the uniform distribution.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1513–1531},
numpages = {19},
keywords = {regular languages, shuffle ideals, subsequences, deterministic finite automata, PAC learning, statistical queries}
}

@article{10.5555/2567709.2567711,
author = {Dhillon, Paramveer S. and Foster, Dean P. and Kakade, Sham M. and Ungar, Lyle H.},
title = {A Risk Comparison of Ordinary Least Squares vs Ridge Regression},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We compare the risk of ridge regression to a simple variant of ordinary least squares, in which one simply projects the data onto a finite dimensional subspace (as specified by a principal component analysis) and then performs an ordinary (un-regularized) least squares regression in this subspace. This note shows that the risk of this ordinary least squares method (PCA-OLS) is within a constant factor (namely 4) of the risk of ridge regression (RR).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1505–1511},
numpages = {7},
keywords = {ridge regression, pca, risk inflation}
}

@article{10.5555/2567709.2567710,
author = {Kanamori, Takafumi and Takeda, Akiko and Suzuki, Taiji},
title = {Conjugate Relation between Loss Functions and Uncertainty Sets in Classification Problems},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {There are two main approaches to binary classification problems: the loss function approach and the uncertainty set approach. The loss function approach is widely used in real-world data analysis. Statistical decision theory has been used to elucidate its properties such as statistical consistency. Conditional probabilities can also be estimated by using the minimum solution of the loss function. In the uncertainty set approach, an uncertainty set is defined for each binary label from training samples. The best separating hyperplane between the two uncertainty sets is used as the decision function. Although the uncertainty set approach provides an intuitive understanding of learning algorithms, its statistical properties have not been sufficiently studied. In this paper, we show that the uncertainty set is deeply connected with the convex conjugate of a loss function. On the basis of the conjugate relation, we propose a way of revising the uncertainty set approach so that it will have good statistical properties such as statistical consistency. We also introduce statistical models corresponding to uncertainty sets in order to estimate conditional probabilities. Finally, we present numerical experiments, verifying that the learning with revised uncertainty sets improves the prediction accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1461–1504},
numpages = {44},
keywords = {convex conjugate, loss function, consistency, uncertainty set}
}

@article{10.5555/2567709.2502590,
author = {De Brabanter, Kris and De Brabanter, Jos and De Moor, Bart and Gijbels, Ir\`{e}ne},
title = {Derivative Estimation with Local Polynomial Fitting},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present a fully automated framework to estimate derivatives nonparametrically without estimating the regression function. Derivative estimation plays an important role in the exploration of structures in curves (jump detection and discontinuities), comparison of regression curves, analysis of human growth data, etc. Hence, the study of estimating derivatives is equally important as regression estimation itself. Via empirical derivatives we approximate the qth order derivative and create a new data set which can be smoothed by any nonparametric regression estimator. We derive L1 and L2 rates and establish consistency of the estimator. The new data sets created by this technique are no longer independent and identically distributed (i.i.d.) random variables anymore. As a consequence, automated model selection criteria (data-driven procedures) break down. Therefore, we propose a simple factor method, based on bimodal kernels, to effectively deal with correlated data in the local polynomial regression framework.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {281–301},
numpages = {21},
keywords = {model selection, empirical derivative, factor rule, nonparametric derivative estimation}
}

@article{10.5555/2567709.2502589,
author = {Alquier, Pierre and Biau, G\'{e}rard},
title = {Sparse Single-Index Model},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Let (X,Y) be a random pair taking values in Rp \texttimes{} R. In the so-called single-index model, one has Y = f*(θ*TX)+W, where f* is an unknown univariate measurable function, θ* is an unknown vector in Rd, and W denotes a random noise satisfying E[W|X] = 0. The single-index model is known to offer a flexible way to model a variety of high-dimensional real-world phenomena. However, despite its relative simplicity, this dimension reduction scheme is faced with severe complications as soon as the underlying dimension becomes larger than the number of observations ("p larger than n" paradigm). To circumvent this difficulty, we consider the single-index model estimation problem from a sparsity perspective using a PAC-Bayesian approach. On the theoretical side, we offer a sharp oracle inequality, which is more powerful than the best known oracle inequalities for other common procedures of single-index recovery. The proposed method is implemented by means of the reversible jump Markov chain Monte Carlo technique and its performance is compared with that of standard procedures.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {243–280},
numpages = {38},
keywords = {single-index model, reversible jump Markov chain Monte Carlo method, PAC-Bayesian, sparsity, regression estimation, oracle inequality}
}

@article{10.5555/2567709.2502588,
author = {Kohlsdorf, Daniel Kyu Hwa and Starner, Thad E.},
title = {MAGIC Summoning: Towards Automatic Suggesting and Testing of Gestures with Low Probability of False Positives during Use},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Gestures for interfaces should be short, pleasing, intuitive, and easily recognized by a computer. However, it is a challenge for interface designers to create gestures easily distinguishable from users' normal movements. Our tool MAGIC Summoning addresses this problem. Given a specific platform and task, we gather a large database of unlabeled sensor data captured in the environments in which the system will be used (an "Everyday Gesture Library" or EGL). The EGL is quantized and indexed via multi-dimensional Symbolic Aggregate approXimation (SAX) to enable quick searching. MAGIC exploits the SAX representation of the EGL to suggest gestures with a low likelihood of false triggering. Suggested gestures are ordered according to brevity and simplicity, freeing the interface designer to focus on the user experience. Once a gesture is selected, MAGIC can output synthetic examples of the gesture to train a chosen classifier (for example, with a hidden Markov model). If the interface designer suggests his own gesture and provides several examples, MAGIC estimates how accurately that gesture can be recognized and estimates its false positive rate by comparing it against the natural movements in the EGL. We demonstrate MAGIC's effectiveness in gesture selection and helpfulness in creating accurate gesture recognizers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {209–242},
numpages = {34},
keywords = {gesture recognition, false positives, gesture spotting, continuous recognition}
}

@article{10.5555/2567709.2502587,
author = {Salomon, Antoine and Audiber, Jean-Yves and El Alaoui, Issam},
title = {Lower Bounds and Selectivity of Weak-Consistent Policies in Stochastic Multi-Armed Bandit Problem},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistency, and exhibit a generalisation of the bound. We also study the existence of logarithmic bounds in general and in the case of Hannan consistency. Moreover, we prove that it is impossible to design an adaptive policy that would select the best of two algorithms by taking advantage of the properties of the environment. To get these results, we study variants of popular Upper Confidence Bounds (UCB) policies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {187–207},
numpages = {21},
keywords = {UCB policies, selectivity, consistency, stochastic bandits, regret lower bounds}
}

@article{10.5555/2567709.2502586,
author = {Hable, Robert},
title = {Universal Consistency of Localized Versions of Regularized Kernel Methods},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {In supervised learning problems, global and local learning algorithms are used. In contrast to global learning algorithms, the prediction of a local learning algorithm in a testing point is only based on training data which are close to the testing point. Every global algorithm such as support vector machines (SVM) can be localized in the following way: in every testing point, the (global) learning algorithm is not applied to the whole training data but only to the k nearest neighbors (kNN) of the testing point. In case of support vector machines, the success of such mixtures of SVM and kNN (called SVM-KNN) has been shown in extensive simulation studies and also for real data sets but only little has been known on theoretical properties so far. In the present article, it is shown how a large class of regularized kernel methods (including SVM) can be localized in order to get a universally consistent learning algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {153–186},
numpages = {34},
keywords = {SVM-KNN, regularized kernel methods, machine learning, k-nearest neighbors, localization, SVM}
}

@article{10.5555/2567709.2502585,
author = {Hyv\"{a}rinen, Aapo and Smith, Stephen M.},
title = {Pairwise Likelihood Ratios for Estimation of Non-Gaussian Structural Equation Models},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present new measures of the causal direction, or direction of effect, between two non-Gaussian random variables. They are based on the likelihood ratio under the linear non-Gaussian acyclic model (LiNGAM). We also develop simple first-order approximations of the likelihood ratio and analyze them based on related cumulant-based measures, which can be shown to find the correct causal directions. We show how to apply these measures to estimate LiNGAM for more than two variables, and even in the case of more variables than observations. We further extend the method to cyclic and nonlinear models. The proposed framework is statistically at least as good as existing ones in the cases of few data points or noisy data, and it is computationally and conceptually very simple. Results on simulated fMRI data indicate that the method may be useful in neuroimaging where the number of time points is typically quite small.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {111–152},
numpages = {42},
keywords = {structural equation model, causality, Bayesian network, non-Gaussianity, independent component analysis}
}

@article{10.5555/2567709.2502584,
author = {Riihim\"{a}ki, Jaakko and Jyl\"{a}nki, Pasi and Vehtari, Aki},
title = {Nested Expectation Propagation for Gaussian Process Classification},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This paper considers probabilistic multinomial probit classification using Gaussian process (GP) priors. Challenges with multiclass GP classification are the integration over the non-Gaussian posterior distribution, and the increase of the number of unknown latent variables as the number of target classes grows. Expectation propagation (EP) has proven to be a very accurate method for approximate inference but the existing EP approaches for the multinomial probit GP classification rely on numerical quadratures, or independence assumptions between the latent values associated with different classes, to facilitate the computations. In this paper we propose a novel nested EP approach which does not require numerical quadratures, and approximates accurately all between-class posterior dependencies of the latent values, but still scales linearly in the number of classes. The predictive accuracy of the nested EP approach is compared to Laplace, variational Bayes, and Markov chain Monte Carlo (MCMC) approximations with various benchmark data sets. In the experiments nested EP was the most consistent method compared to MCMC sampling, but in terms of classification accuracy the differences between all the methods were small from a practical point of view.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {75–109},
numpages = {35},
keywords = {approximate inference, multiclass classification, Gaussian process, expectation propagation, multinomial probit}
}

@article{10.5555/2567709.2502583,
author = {Cl\'{e}men\c{c}on, St\'{e}phan and Depecker, Marine and Vayatis, Nicolas},
title = {Ranking Forests},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The present paper examines how the aggregation and feature randomization principles underlying the algorithm RANDOM FOREST (Breiman, 2001) can be adapted to bipartite ranking. The approach taken here is based on nonparametric scoring and ROC curve optimization in the sense of the AUC criterion. In this problem, aggregation is used to increase the performance of scoring rules produced by ranking trees, as those developed in Cl\'{e}emen\c{c}on and Vayatis (2009c). The present work describes the principles for building median scoring rules based on concepts from rank aggregation. Consistency results are derived for these aggregated scoring rules and an algorithm called RANKING FOREST is presented. Furthermore, various strategies for feature randomization are explored through a series of numerical experiments on artificial data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {39–73},
numpages = {35},
keywords = {ROC optimization, bagging, bipartite ranking, rank aggregation, feature randomization, tree-based ranking rules, bootstrap, classification data, median ranking, nonparametric scoring, AUC criterion}
}

@article{10.5555/2567709.2502582,
author = {Nakajima, Shinichi and Sugiyama, Masashi and Babacan, S. Derin and Tomioka, Ryota},
title = {Global Analytic Solution of Fully-Observed Variational Bayesian Matrix Factorization},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The variational Bayesian (VB) approximation is known to be a promising approach to Bayesian estimation, when the rigorous calculation of the Bayes posterior is intractable. The VB approximation has been successfully applied to matrix factorization (MF), offering automatic dimensionality selection for principal component analysis. Generally, finding the VB solution is a nonconvex problem, and most methods rely on a local search algorithm derived through a standard procedure for the VB approximation. In this paper, we show that a better option is available for fully-observed VBMF--the global solution can be analytically computed. More specifically, the global solution is a reweighted SVD of the observed matrix, and each weight can be obtained by solving a quartic equation with its coefficients being functions of the observed singular value. We further show that the global optimal solution of empirical VBMF (where hyperparameters are also learned from data) can also be analytically computed. We illustrate the usefulness of our results through experiments in multi-variate analysis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–37},
numpages = {37},
keywords = {empirical bayes, matrix factorization, model-induced regularization, variational bayes, probabilistic PCA}
}

@article{10.5555/2503308.2503360,
author = {Lang, Tobias and Toussaint, Marc and Kersting, Kristian},
title = {Exploration in Relational Domains for Model-Based Reinforcement Learning},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {A fundamental problem in reinforcement learning is balancing exploration and exploitation. We address this problem in the context of model-based reinforcement learning in large stochastic relational domains by developing relational extensions of the concepts of the E3 and R-MAX algorithms. Efficient exploration in exponentially large state spaces needs to exploit the generalization of the learned model: what in a propositional setting would be considered a novel situation and worth exploration may in the relational setting be a well-known context in which exploitation is promising. To address this we introduce relational count functions which generalize the classical notion of state and action visitation counts. We provide guarantees on the exploration efficiency of our framework using count functions under the assumption that we had a relational KWIK learner and a near-optimal planner. We propose a concrete exploration algorithm which integrates a practically efficient probabilistic rule learner and a relational planner (for which there are no guarantees, however) and employs the contexts of learned relational rules as features to model the novelty of states and actions. Our results in noisy 3D simulated robot manipulation problems and in domains of the international planning competition demonstrate that our approach is more effective than existing propositional and factored exploration techniques.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3725–3768},
numpages = {44},
keywords = {relational transition models, exploration, robotics, statistical relational learning, reinforcement learning}
}

@article{10.5555/2503308.2503359,
author = {Kloft, Marius and Laskov, Pavel},
title = {Security Analysis of Online Centroid Anomaly Detection},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Security issues are crucial in a number of machine learning applications, especially in scenarios dealing with human activity rather than natural phenomena (e.g., information ranking, spam detection, malware detection, etc.). In such cases, learning algorithms may have to cope with manipulated data aimed at hampering decision making. Although some previous work addressed the issue of handling malicious data in the context of supervised learning, very little is known about the behavior of anomaly detection methods in such scenarios. In this contribution, we analyze the performance of a particular method--online centroid anomaly detection--in the presence of adversarial noise. Our analysis addresses the following security-related issues: formalization of learning and attack processes, derivation of an optimal attack, and analysis of attack efficiency and limitations. We derive bounds on the effectiveness of a poisoning attack against centroid anomaly detection under different conditions: attacker's full or limited control over the traffic and bounded false positive rate. Our bounds show that whereas a poisoning attack can be effectively staged in the unconstrained case, it can be made arbitrarily difficult (a strict upper bound on the attacker's gain) if external constraints are properly used. Our experimental evaluation, carried out on real traces of HTTP and exploit traffic, confirms the tightness of our theoretical bounds and the practicality of our protection mechanisms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3681–3724},
numpages = {44},
keywords = {security analysis, adversarial, network intrusion detection, computer security, anomaly detection, support vector data description}
}

@article{10.5555/2503308.2503358,
author = {Zhang, Xinhua and Saha, Ankan and Vishwanathan, S. V. N.},
title = {Smoothing Multivariate Performance Measures},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Optimizing multivariate performance measure is an important task in Machine Learning. Joachims (2005) introduced a Support Vector Method whose underlying optimization problem is commonly solved by cutting plane methods (CPMs) such as SVM-Perf and BMRM. It can be shown that CPMs converge to an ε accurate solution in O(1/λε) iterations, where λ is the trade-off parameter between the regularizer and the loss function. Motivated by the impressive convergence rate of CPM on a number of practical problems, it was conjectured that these rates can be further improved. We disprove this conjecture in this paper by constructing counter examples. However, surprisingly, we further discover that these problems are not inherently hard, and we develop a novel smoothing strategy, which in conjunction with Nesterov's accelerated gradient method, can find an ε accurate solution in O* (min{1/ε, 1/√λε}) iterations. Computationally, our smoothing technique is also particularly advantageous for optimizing multivariate performance scores such as precision/recall break-even point and ROCArea; the cost per iteration remains the same as that of CPMs. Empirical evaluation on some of the largest publicly available data sets shows that our method converges significantly faster than CPMs without sacrificing generalization ability.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3623–3680},
numpages = {58},
keywords = {multivariate performance measures, max-margin methods, smoothing, support vector machines, non-smooth optimization}
}

@article{10.5555/2503308.2503357,
author = {Chen, Tianqi and Zhang, Weinan and Lu, Qiuxia and Chen, Kailong and Zheng, Zhao and Yu, Yong},
title = {SVDFeature: A Toolkit for Feature-Based Collaborative Filtering},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In this paper we introduce SVDFeature, a machine learning toolkit for feature-based collaborative filtering. SVDFeature is designed to efficiently solve the feature-based matrix factorization. The feature-based setting allows us to build factorization models incorporating side information such as temporal dynamics, neighborhood relationship, and hierarchical information. The toolkit is capable of both rate prediction and collaborative ranking, and is carefully designed for efficient training on large-scale data set. Using this toolkit, we built solutions to win KDD Cup for two consecutive years.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3619–3622},
numpages = {4},
keywords = {ranking, large-scale collaborative filtering, context-aware recommendation}
}

@article{10.5555/2503308.2503356,
author = {Ly, Daniel L. and Lipson, Hod},
title = {Learning Symbolic Representations of Hybrid Dynamical Systems},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {A hybrid dynamical system is a mathematical model suitable for describing an extensive spectrum of multi-modal, time-series behaviors, ranging from bouncing balls to air traffic controllers. This paper describes multi-modal symbolic regression (MMSR): a learning algorithm to construct non-linear symbolic representations of discrete dynamical systems with continuous mappings from unlabeled, time-series data. MMSR consists of two subalgorithms--clustered symbolic regression, a method to simultaneously identify distinct behaviors while formulating their mathematical expressions, and transition modeling, an algorithm to infer symbolic inequalities that describe binary classification boundaries. These subalgorithms are combined to infer hybrid dynamical systems as a collection of apt, mathematical expressions. MMSR is evaluated on a collection of four synthetic data sets and outperforms other multi-modal machine learning approaches in both accuracy and interpretability, even in the presence of noise. Furthermore, the versatility of MMSR is demonstrated by identifying and inferring classical expressions of transistor modes from recorded measurements.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3585–3618},
numpages = {34},
keywords = {symbolic piecewise functions, hybrid dynamical systems, evolutionary computation, symbolic binary classification}
}

@article{10.5555/2503308.2503355,
author = {Do, Trinh-Minh-Tri and Arti\`{e}res, Thierry},
title = {Regularized Bundle Methods for Convex and Non-Convex Risks},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Machine learning is most often cast as an optimization problem. Ideally, one expects a convex objective function to rely on efficient convex optimizers with nice guarantees such as no local optima. Yet, non-convexity is very frequent in practice and it may sometimes be inappropriate to look for convexity at any price. Alternatively one can decide not to limit a priori the modeling expressivity to models whose learning may be solved by convex optimization and rely on non-convex optimization algorithms. The main motivation of this work is to provide efficient and scalable algorithms for non-convex optimization. We focus on regularized unconstrained optimization problems which cover a large number of modern machine learning problems such as logistic regression, conditional random fields, large margin estimation, etc. We propose a novel algorithm for minimizing a regularized objective that is able to handle convex and non-convex, smooth and non-smooth risks. The algorithm is based on the cutting plane technique and on the idea of exploiting the regularization term in the objective function. It may be thought as a limited memory extension of convex regularized bundle methods for dealing with convex and non convex risks. In case the risk is convex the algorithm is proved to converge to a stationary solution with accuracy e with a rate O(1/λε) where λ is the regularization parameter of the objective function under the assumption of a Lipschitz empirical risk. In case the risk is not convex getting such a proof is more difficult and requires a stronger and more disputable assumption. Yet we provide experimental results on artificial test problems, and on five standard and difficult machine learning problems that are cast as convex and non-convex optimization problems that show how our algorithm compares well in practice with state of the art optimization algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3539–3583},
numpages = {45},
keywords = {optimization, non-convex, regularized risk, non-smooth, cutting plane, bundle method}
}

@article{10.5555/2503308.2503354,
author = {Gould, Stephen},
title = {DARWIN: A Framework for Machine Learning and Computer Vision Research and Development},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present an open-source platform-independent C++ framework for machine learning and computer vision research. The framework includes a wide range of standard machine learning and graphical models algorithms as well as reference implementations for many machine learning and computer vision applications. The framework contains Matlab wrappers for core components of the library and an experimental graphical user interface for developing and visualizing machine learning data flows.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3533–3537},
numpages = {5},
keywords = {open-source software, graphical models, machine learning, computer vision}
}

@article{10.5555/2503308.2503353,
author = {Parrado-Hern\'{a}ndez, Emilio and Ambroladze, Amiran and Shawe-Taylor, John and Sun, Shiliang},
title = {PAC-Bayes Bounds with Data Dependent Priors},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {This paper presents the prior PAC-Bayes bound and explores its capabilities as a tool to provide tight predictions of SVMs' generalization. The computation of the bound involves estimating a prior of the distribution of classifiers from the available data, and then manipulating this prior in the usual PAC-Bayes generalization bound. We explore two alternatives: to learn the prior from a separate data set, or to consider an expectation prior that does not need this separate data set. The prior PAC-Bayes bound motivates two SVM-like classification algorithms, prior SVM and ν-prior SVM, whose regularization term pushes towards the minimization of the prior PAC-Bayes bound. The experimental work illustrates that the new bounds can be significantly tighter than the original PAC-Bayes bound when applied to SVMs, and among them the combination of the prior PAC-Bayes bound and the prior SVM algorithm gives the tightest bound.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3507–3531},
numpages = {25},
keywords = {PAC-Bayes bound, classification, generalization capability prediction, support vector machine}
}

@article{10.5555/2503308.2503352,
author = {Drineas, Petros and Magdon-Ismail, Malik and Mahoney, Michael W. and Woodruff, David P.},
title = {Fast Approximation of Matrix Coherence and Statistical Leverage},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The statistical leverage scores of a matrix A are the squared row-norms of the matrix containing its (top) left singular vectors and the coherence is the largest leverage score. These quantities are of interest in recently-popular problems such as matrix completion and Nystr\"{o}m-based low-rank matrix approximation as well as in large-scale statistical data analysis applications more generally; moreover, they are of interest since they define the key structural nonuniformity that must be dealt with in developing fast randomized matrix algorithms. Our main result is a randomized algorithm that takes as input an arbitrary n \texttimes{} d matrix A, with n ≫ d, and that returns as output relative-error approximations to all n of the statistical leverage scores. The proposed algorithm runs (under assumptions on the precise values of n and d) in O(nd logn) time, as opposed to the O(nd2) time required by the na\"{\i}ve algorithm that involves computing an orthogonal basis for the range of A. Our analysis may be viewed in terms of computing a relative-error approximation to an underconstrained least-squares approximation problem, or, relatedly, it may be viewed as an application of Johnson-Lindenstrauss type ideas. Several practically-important extensions of our basic result are also described, including the approximation of so-called cross-leverage scores, the extension of these ideas to matrices with n ≈ d, and the extension to streaming environments.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3475–3506},
numpages = {32},
keywords = {randomized algorithm, matrix coherence, statistical leverage}
}

@article{10.5555/2503308.2503351,
author = {Mohan, Karthik and Fazel, Maryam},
title = {Iterative Reweighted Algorithms for Matrix Rank Minimization},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {The problem of minimizing the rank of a matrix subject to affine constraints has applications in several areas including machine learning, and is known to be NP-hard. A tractable relaxation for this problem is nuclear norm (or trace norm) minimization, which is guaranteed to find the minimum rank matrix under suitable assumptions. In this paper, we propose a family of Iterative Reweighted Least Squares algorithms IRLS-p (with 0 ≤ p ≤ 1), as a computationally efficient way to improve over the performance of nuclear norm minimization. The algorithms can be viewed as (locally) minimizing certain smooth approximations to the rank function. When p = 1, we give theoretical guarantees similar to those for nuclear norm minimization, that is, recovery of low-rank matrices under certain assumptions on the operator defining the constraints. For p < 1, IRLS-p  shows better empirical performance in terms of recovering low-rank matrices than nuclear norm minimization. We provide an efficient implementation for IRLS-p, and also present a related family of algorithms, sIRLS-p. These algorithms exhibit competitive run times and improved recovery when compared to existing algorithms for random instances of the matrix completion problem, as well as on the MovieLens movie recommendation data set.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3441–3473},
numpages = {33},
keywords = {null-space property, matrix completion, matrix rankminimization, iterative algorithms}
}

@article{10.5555/2503308.2503350,
author = {Hyttinen, Antti and Eberhardt, Frederick and Hoyer, Patrik O.},
title = {Learning Linear Cyclic Causal Models with Latent Variables},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Identifying cause-effect relationships between variables of interest is a central problem in science. Given a set of experiments we describe a procedure that identifies linear models that may contain cycles and latent variables. We provide a detailed description of the model family, full proofs of the necessary and sufficient conditions for identifiability, a search algorithm that is complete, and a discussion of what can be done when the identifiability conditions are not satisfied. The algorithm is comprehensively tested in simulations, comparing it to competing algorithms in the literature. Furthermore, we adapt the procedure to the problem of cellular network inference, applying it to the biologically realistic data of the DREAMchallenges. The paper provides a full theoretical foundation for the causal discovery procedure first presented by Eberhardt et al. (2010) and Hyttinen et al. (2010).},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3387–3439},
numpages = {53},
keywords = {randomized experiments, causality, graphical models, latent variables, cycles, latent confounders, structural equation models}
}

@article{10.5555/2503308.2503349,
author = {Gillis, Nicolas},
title = {Sparse and Unique Nonnegative Matrix Factorization through Data Preprocessing},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Nonnegative matrix factorization (NMF) has become a very popular technique in machine learning because it automatically extracts meaningful features through a sparse and part-based representation. However, NMF has the drawback of being highly ill-posed, that is, there typically exist many different but equivalent factorizations. In this paper, we introduce a completely new way to obtaining more well-posed NMF problems whose solutions are sparser. Our technique is based on the preprocessing of the nonnegative input data matrix, and relies on the theory of M-matrices and the geometric interpretation of NMF. This approach provably leads to optimal and sparse solutions under the separability assumption of Donoho and Stodden (2003), and, for rank-three matrices, makes the number of exact factorizations finite. We illustrate the effectiveness of our technique on several image data sets.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3349–3386},
numpages = {38},
keywords = {inversepositive matrices, uniqueness, sparsity, nonnegative matrix factorization, data preprocessing}
}

@article{10.5555/2503308.2503348,
author = {Ho, Chia-Hua and Lin, Chih-Jen},
title = {Large-Scale Linear Support Vector Regression},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Support vector regression (SVR) and support vector classification (SVC) are popular learning techniques, but their use with kernels is often time consuming. Recently, linear SVC without kernels has been shown to give competitive accuracy for some applications, but enjoys much faster training/ testing. However, few studies have focused on linear SVR. In this paper, we extend state-of-theart training methods for linear SVC to linear SVR. We show that the extension is straightforward for some methods, but is not trivial for some others. Our experiments demonstrate that for some problems, the proposed linear-SVR training methods can very efficiently produce models that are as good as kernel SVR.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3323–3348},
numpages = {26},
keywords = {coordinate descent methods, Newton methods, support vector regression}
}

@article{10.5555/2503308.2503347,
author = {Lui, Yui Man},
title = {Human Gesture Recognition on Product Manifolds},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Action videos are multidimensional data and can be naturally represented as data tensors. While tensor computing is widely used in computer vision, the geometry of tensor space is often ignored. The aim of this paper is to demonstrate the importance of the intrinsic geometry of tensor space which yields a very discriminating structure for action recognition. We characterize data tensors as points on a product manifold and model it statistically using least squares regression. To this aim, we factorize a data tensor relating to each order of the tensor using Higher Order Singular Value Decomposition (HOSVD) and then impose each factorized element on a Grassmann manifold. Furthermore, we account for underlying geometry on manifolds and formulate least squares regression as a composite function. This gives a natural extension from Euclidean space to manifolds. Consequently, classification is performed using geodesic distance on a product manifold where each factor manifold is Grassmannian. Our method exploits appearance and motion without explicitly modeling the shapes and dynamics. We assess the proposed method using three gesture databases, namely the Cambridge hand-gesture, the UMD Keck body-gesture, and the CHALEARN gesture challenge data sets. Experimental results reveal that not only does the proposed method perform well on the standard benchmark data sets, but also it generalizes well on the one-shot-learning gesture challenge. Furthermore, it is based on a simple statistical model and the intrinsic geometry of tensor space.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3297–3321},
numpages = {25},
keywords = {one-shot-learning, kinect data, gesture recognition, Grassmann manifolds, product manifolds, action recognition}
}

@article{10.5555/2503308.2503346,
author = {Lizotte, Daniel J. and Bowling, Michael and Murphy, Susan A.},
title = {Linear Fitted-Q Iteration with Multiple Reward Functions},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We present a general and detailed development of an algorithm for finite-horizon fitted-Q iteration with an arbitrary number of reward signals and linear value function approximation using an arbitrary number of state features. This includes a detailed treatment of the 3-reward function case using triangulation primitives from computational geometry and a method for identifying globally dominated actions. We also present an example of how our methods can be used to construct a realworld decision aid by considering symptom reduction, weight gain, and quality of life in sequential treatments for schizophrenia. Finally, we discuss future directions in which to take this work that will further enable our methods to make a positive impact on the field of evidence-based clinical decision support.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3253–3295},
numpages = {43},
keywords = {decision making, preference elicitation, linear regression, reinforcement learning, dynamic programming}
}

@article{10.5555/2503308.2503345,
author = {Rieck, Konrad and Wressnegger, Christian and Bikadorov, Alexander},
title = {Sally: A Tool for Embedding Strings in Vector Spaces},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Strings and sequences are ubiquitous in many areas of data analysis. However, only few learning methods can be directly applied to this form of data. We present Sally, a tool for embedding strings in vector spaces that allows for applying a wide range of learning methods to string data. Sally implements a generalized form of the bag-of-words model, where strings are mapped to a vector space that is spanned by a set of string features, such as words or n-grams of words. The implementation of Sally builds on efficient string algorithms and enables processing millions of strings and features. The tool supports several data formats and is capable of interfacing with common learning environments, such as Weka, Shogun, Matlab, or Pylab. Sally has been successfully applied for learning with natural language text, DNA sequences and monitored program behavior.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3247–3251},
numpages = {5},
keywords = {learning with sequential data, bag-of-words models, string embedding}
}

@article{10.5555/2503308.2503344,
author = {Azar, Mohammad Gheshlaghi and G\'{o}mez, Vicen\c{c} and Kappen, Hilbert J.},
title = {Dynamic Policy Programming},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we propose a novel policy iteration method, called dynamic policy programming (DPP), to estimate the optimal policy in the infinite-horizon Markov decision processes. DPP is an incremental algorithm that forces a gradual change in policy update. This allows us to prove finite-iteration and asymptotic l∞-norm performance-loss bounds in the presence of approximation/ estimation error which depend on the average accumulated error as opposed to the standard bounds which are expressed in terms of the supremum of the errors. The dependency on the average error is important in problems with limited number of samples per iteration, for which the average of the errors can be significantly smaller in size than the supremum of the errors. Based on these theoretical results, we prove that a sampling-based variant of DPP (DPP-RL) asymptotically converges to the optimal policy. Finally, we illustrate numerically the applicability of these results on some benchmark problems and compare the performance of the approximate variants of DPP with some existing reinforcement learning (RL) methods.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3207–3245},
numpages = {39},
keywords = {Markov decision processes, approximate dynamic programming, Monte-Carlo methods, reinforcement learning, function approximation}
}

@article{10.5555/2503308.2503343,
author = {Salman, Tamer and Baram, Yoram},
title = {Quantum Set Intersection and Its Application to Associative Memory},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {We describe a quantum algorithm for computing the intersection of two sets and its application to associative memory. The algorithm is based on a modification of Grover's quantum search algorithm (Grover, 1996). We present algorithms for pattern retrieval, pattern completion, and pattern correction. We show that the quantum associative memory can store an exponential number of memories and retrieve them in sub-exponential time. We prove that this model has advantages over known classical associative memories as well as previously proposed quantum models.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3177–3206},
numpages = {30},
keywords = {quantum computation, associative memory, quantum search, pattern completion, pattern correction}
}

@article{10.5555/2503308.2503342,
author = {Brodersen, Kay H. and Mathys, Christoph and Chumbley, Justin R. and Daunizeau, Jean and Ong, Cheng Soon and Buhmann, Joachim M. and Stephan, Klaas E.},
title = {Bayesian Mixed-Effects Inference on Classification Performance in Hierarchical Data Sets},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Classification algorithms are frequently used on data with a natural hierarchical structure. For instance, classifiers are often trained and tested on trial-wise measurements, separately for each subject within a group. One important question is how classification outcomes observed in individual subjects can be generalized to the population from which the group was sampled. To address this question, this paper introduces novel statistical models that are guided by three desiderata. First, all models explicitly respect the hierarchical nature of the data, that is, they are mixed-effects models that simultaneously account for within-subjects (fixed-effects) and across-subjects (random-effects) variance components. Second, maximum-likelihood estimation is replaced by full Bayesian inference in order to enable natural regularization of the estimation problem and to afford conclusions in terms of posterior probability statements. Third, inference on classification accuracy is complemented by inference on the balanced accuracy, which avoids inflated accuracy estimates for imbalanced data sets. We introduce hierarchical models that satisfy these criteria and demonstrate their advantages over conventional methods usingMCMC implementations for model inversion and model selection on both synthetic and empirical data. We envisage that our approach will improve the sensitivity and validity of statistical inference in future hierarchical classification studies.},
journal = {J. Mach. Learn. Res.},
month = nov,
pages = {3133–3176},
numpages = {44},
keywords = {beta-binomial, group studies, normal-binomial, balanced accuracy, Bayesian inference}
}

@article{10.5555/2503308.2503341,
author = {Wang, Zhuang and Crammer, Koby and Vucetic, Slobodan},
title = {Breaking the Curse of Kernelization: Budgeted Stochastic Gradient Descent for Large-Scale SVM Training},
year = {2012},
issue_date = {January 2012},
publisher = {JMLR.org},
volume = {13},
number = {1},
issn = {1532-4435},
abstract = {Online algorithms that process one example at a time are advantageous when dealing with very large data or with data streams. Stochastic Gradient Descent (SGD) is such an algorithm and it is an attractive choice for online Support Vector Machine (SVM) training due to its simplicity and effectiveness. When equipped with kernel functions, similarly to other SVM learning algorithms, SGD is susceptible to the curse of kernelization that causes unbounded linear growth in model size and update time with data size. This may render SGD inapplicable to large data sets. We address this issue by presenting a class of Budgeted SGD (BSGD) algorithms for large-scale kernel SVM training which have constant space and constant time complexity per update. Specifically, BSGD keeps the number of support vectors bounded during training through several budget maintenance strategies. We treat the budget maintenance as a source of the gradient error, and show that the gap between the BSGD and the optimal SVM solutions depends on the model degradation due to budget maintenance. To minimize the gap, we study greedy budget maintenance methods based on removal, projection, and merging of support vectors. We propose budgeted versions of several popular online SVM algorithms that belong to the SGD family. We further derive BSGD algorithms for multi-class SVM training. Comprehensive empirical results show that BSGD achieves higher accuracy than the state-of-the-art budgeted online algorithms and comparable to non-budget algorithms, while achieving impressive computational efficiency both in time and space during training and prediction.},
journal = {J. Mach. Learn. Res.},
month = oct,
pages = {3103–3131},
numpages = {29},
keywords = {SVM, stochastic gradient descent, online

license_type: permissive

branch_name: refs/heads/main

extension: bib