text:
= {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Appropriate selection of the kernel function, which implicitly defines the feature space of an algorithm, has a crucial role in the success of kernel methods. In this paper, we consider the problem of optimizing a kernel function over the class of translation invariant kernels for the task of binary classification. The learning capacity of this class is invariant with respect to rotation and scaling of the features and it encompasses the set of radial kernels. We show that how translation invariant kernel functions can be embedded in a nested set of sub-classes and consider the kernel learning problem over one of these sub-classes. This allows the choice of an appropriate sub-class based on the problem at hand. We use the criterion proposed by Lanckriet et al. (2004) to obtain a functional formulation for the problem. It will be proven that the optimal kernel is a finite mixture of cosine functions. The kernel learning problem is then formulated as a semi-infinite programming (SIP) problem which is solved by a sequence of quadratically constrained quadratic programming (QCQP) sub-problems. Using the fact that the cosine kernel is of rank two, we propose a formulation of a QCQP sub-problem which does not require the kernel matrices to be loaded into memory, making the method applicable to large-scale problems. We also address the issue of including other classes of kernels, such as individual kernels and isotropic Gaussian kernels, in the learning process. Another interesting feature of the proposed method is that the optimal classifier has an expansion in terms of the number of cosine kernels, instead of support vectors, leading to a remarkable speedup at run-time. As a by-product, we also generalize the kernel trick to complex-valued kernel functions. Our experiments on artificial and real-world benchmark data sets, including the USPS and the MNIST digit recognition data sets, show the usefulness of the proposed method.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1353–1390},
numpages = {38}
}

@article{10.5555/1756006.1859895,
author = {Donmez, Pinar and Lebanon, Guy and Balasubramanian, Krishnakumar},
title = {Unsupervised Supervised Learning I: Estimating Classification and Regression Errors without Labels},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Estimating the error rates of classifiers or regression models is a fundamental task in machine learning which has thus far been studied exclusively using supervised learning techniques. We propose a novel unsupervised framework for estimating these error rates using only unlabeled data and mild assumptions. We prove consistency results for the framework and demonstrate its practical applicability on both synthetic and real world data.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1323–1351},
numpages = {29}
}

@article{10.5555/1756006.1859894,
author = {Raykar, Vikas C. and Yu, Shipeng and Zhao, Linda H. and Valadez, Gerardo Hermosillo and Florin, Charles and Bogoni, Luca and Moy, Linda},
title = {Learning From Crowds},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {For many supervised learning tasks it may be infeasible (or very expensive) to obtain objective and reliable labels. Instead, we can collect subjective (possibly noisy) labels from multiple experts or annotators. In practice, there is a substantial amount of disagreement among the annotators, and hence it is of great practical interest to address conventional supervised learning problems in this scenario. In this paper we describe a probabilistic approach for supervised learning when we have multiple annotators providing (possibly noisy) labels but no absolute gold standard. The proposed algorithm evaluates the different experts and also gives an estimate of the actual hidden labels. Experimental results indicate that the proposed method is superior to the commonly used majority voting baseline.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1297–1322},
numpages = {26}
}

@article{10.5555/1756006.1859893,
author = {G\'{o}mez, Vicen\c{c} and Kappen, Hilbert J. and Chertkov, Michael},
title = {Approximate Inference on Planar Graphs Using Loop Calculus and Belief Propagation},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006a) allows to express the exact partition function of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in Chertkov et al. (2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze the performance of the algorithm for models with binary variables and pairwise interactions on grids and other planar graphs. We study in detail both the loop series and the equivalent Pfaffian series and show that the first term of the Pfaffian series for the general, intractable planar model, can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state of the art methods for approximate inference.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1273–1296},
numpages = {24}
}

@article{10.5555/1756006.1859892,
author = {Aoyagi, Miki},
title = {Stochastic Complexity and Generalization Error of a Restricted Boltzmann Machine in Bayesian Estimation},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper, we consider the asymptotic form of the generalization error for the restricted Boltzmann machine in Bayesian estimation. It has been shown that obtaining the maximum pole of zeta functions is related to the asymptotic form of the generalization error for hierarchical learning models (Watanabe, 2001a,b). The zeta function is defined by using a Kullback function. We use two methods to obtain the maximum pole: a new eigenvalue analysis method and a recursive blowing up process. We show that these methods are effective for obtaining the asymptotic form of the generalization error of hierarchical learning models.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1243–1272},
numpages = {30}
}

@article{10.5555/1756006.1859891,
author = {Vishwanathan, S. V. N. and Schraudolph, Nicol N. and Kondor, Risi and Borgwardt, Karsten M.},
title = {Graph Kernels},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We present a unified framework to study graph kernels, special cases of which include the random walk (G\"{a}rtner et al., 2003; Borgwardt et al., 2005) and marginalized (Kashima et al., 2003, 2004; Mah\'{e}t al., 2004) graph kernels. Through reduction to a Sylvester equation we improve the time complexity of kernel computation between unlabeled graphs with n vertices from O(n6) to O(n3). We find a spectral decomposition approach even more efficient when computing entire kernel matrices. For labeled graphs we develop conjugate gradient and fixed-point methods that take O(dn3) time per iteration, where d is the size of the label set. By extending the necessary linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) we obtain the same result for d-dimensional edge kernels, and O(n4) in the infinite-dimensional case; on sparse graphs these algorithms only take O(n2) time per iteration in all cases. Experiments on graphs from bioinformatics and other application domains show that these techniques can speed up computation of the kernel by an order of magnitude or more. We also show that certain rational kernels (Cortes et al., 2002, 2003, 2004) when specialized to graphs reduce to our random walk graph kernel. Finally, we relate our framework to R-convolution kernels (Haussler, 1999) and provide a kernel that is close to the optimal assignment kernel of kernel of Fr\"{o}hlich et al. (2006) yet provably positive semi-definite.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1201–1242},
numpages = {42}
}

@article{10.5555/1756006.1756045,
author = {Yu, Jin and Vishwanathan, S.V.N. and G\"{u}nter, Simon and Schraudolph, Nicol N.},
title = {A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We extend the well-known BFGS quasi-Newton method and its memory-limited variant LBFGS to the optimization of nonsmooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: the local quadratic model, the identification of a descent direction, and the Wolfe line search conditions. We prove that under some technical conditions, the resulting subBFGS algorithm is globally convergent in objective function value. We apply its memory-limited variant (subLBFGS) to L2-regularized risk minimization with the binary hinge loss. To extend our algorithm to the multiclass and multilabel settings, we develop a new, efficient, exact line search algorithm. We prove its worst-case time complexity bounds, and show that our line search can also be used to extend a recently developed bundle method to the multiclass and multilabel settings. We also apply the direction-finding component of our algorithm to L1-regularized risk minimization with logistic loss. In all these contexts our methods perform comparable to or better than specialized state-of-the-art solvers on a number of publicly available data sets. An open source implementation of our algorithms is freely available.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1145–1200},
numpages = {56}
}

@article{10.5555/1756006.1756044,
author = {Krause, Andreas},
title = {SFO: A Toolbox for Submodular Function Optimization},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In recent years, a fundamental problem structure has emerged as very useful in a variety of machine learning applications: Submodularity is an intuitive diminishing returns property, stating that adding an element to a smaller set helps more than adding it to a larger set. Similarly to convexity, submodularity allows one to efficiently find provably (near-) optimal solutions for large problems. We present SFO, a toolbox for use in MATLAB or Octave that implements algorithms for minimization and maximization of submodular functions. A tutorial script illustrates the application of submodularity to machine learning and AI problems such as feature selection, clustering, inference and optimized information gathering.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1141–1144},
numpages = {4}
}

@article{10.5555/1756006.1756043,
author = {Shelton, Christian R. and Fan, Yu and Lam, William and Lee, Joon and Xu, Jing},
title = {Continuous Time Bayesian Network Reasoning and Learning Engine},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We present a continuous time Bayesian network reasoning and learning engine (CTBN-RLE). A continuous time Bayesian network (CTBN) provides a compact (factored) description of a continuous-time Markov process. This software provides libraries and programs for most of the algorithms developed for CTBNs. For learning, CTBN-RLE implements structure and parameter learning for both complete and partial data. For inference, it implements exact inference and Gibbs and importance sampling approximate inference for any type of evidence pattern. Additionally, the library supplies visualization methods for graphically displaying CTBNs or trajectories of evidence.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1137–1140},
numpages = {4}
}

@article{10.5555/1756006.1756042,
author = {Chechik, Gal and Sharma, Varun and Shalit, Uri and Bengio, Samy},
title = {Large Scale Online Learning of Image Similarity Through Ranking},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Learning a measure of similarity between pairs of objects is an important generic problem in machine learning. It is particularly useful in large scale applications like searching for an image that is similar to a given image or finding videos that are relevant to a given video. In these tasks, users look for objects that are not only visually similar but also semantically related to a given object. Unfortunately, the approaches that exist today for learning such semantic similarity do not scale to large data sets. This is both because typically their CPU and storage requirements grow quadratically with the sample size, and because many methods impose complex positivity constraints on the space of learned similarity functions.The current paper presents OASIS, an Online Algorithm for Scalable Image Similarity learning that learns a bilinear similarity measure over sparse representations. OASIS is an online dual approach using the passive-aggressive family of learning algorithms with a large margin criterion and an efficient hinge loss cost. Our experiments show that OASIS is both fast and accurate at a wide range of scales: for a data set with thousands of images, it achieves better results than existing state-of-the-art methods, while being an order of magnitude faster. For large, web scale, data sets, OASIS can be trained on more than two million images from 150K text queries within 3 days on a single CPU. On this large scale data set, human evaluations showed that 35% of the ten nearest neighbors of a given test image, as found by OASIS, were semantically relevant to that image. This suggests that query independent similarity could be accurately learned even for large scale data sets that could not be handled before.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1109–1135},
numpages = {27}
}

@article{10.5555/1756006.1756041,
author = {Zhang, Tong},
title = {Analysis of Multi-Stage Convex Relaxation for Sparse Regularization},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We consider learning formulations with non-convex objective functions that often occur in practical applications. There are two approaches to this problem: Heuristic methods such as gradient descent that only find a local minimum. A drawback of this approach is the lack of theoretical guarantee showing that the local minimum gives a good solution.  Convex relaxation such as L1-regularization that solves the problem under some conditions. However it often leads to a sub-optimal solution in reality. This paper tries to remedy the above gap between theory and practice. In particular, we present a multi-stage convex relaxation scheme for solving problems with non-convex objective functions. For learning formulations with sparse regularization, we analyze the behavior of a specific multi-stage relaxation scheme. Under appropriate conditions, we show that the local solution obtained by this procedure is superior to the global solution of the standard L1 convex relaxation for learning sparse targets.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1081–1107},
numpages = {27}
}

@article{10.5555/1756006.1756040,
author = {Ravikumar, Pradeep and Agarwal, Alekh and Wainwright, Martin J.},
title = {Message-Passing for Graph-Structured Linear Programs: Proximal Methods and Rounding Schemes},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The problem of computing a maximum a posteriori (MAP) configuration is a central computational challenge associated with Markov random fields. There has been some focus on "tree-based" linear programming (LP) relaxations for the MAP problem. This paper develops a family of super-linearly convergent algorithms for solving these LPs, based on proximal minimization schemes using Bregman divergences. As with standard message-passing on graphs, the algorithms are distributed and exploit the underlying graphical structure, and so scale well to large problems. Our algorithms have a double-loop character, with the outer loop corresponding to the proximal sequence, and an inner loop of cyclic Bregman projections used to compute each proximal update. We establish convergence guarantees for our algorithms, and illustrate their performance via some simulations. We also develop two classes of rounding schemes, deterministic and randomized, for obtaining integral configurations from the LP solutions. Our deterministic rounding schemes use a "re-parameterization" property of our algorithms so that when the LP solution is integral, the MAP solution can be obtained even before the LP-solver converges to the optimum. We also propose graph-structured randomized rounding schemes applicable to iterative LP-solving algorithms in general. We analyze the performance of and report simulations comparing these rounding schemes.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1043–1080},
numpages = {38}
}

@article{10.5555/1756006.1756039,
author = {Leskovec, Jure and Chakrabarti, Deepayan and Kleinberg, Jon and Faloutsos, Christos and Ghahramani, Zoubin},
title = {Kronecker Graphs: An Approach to Modeling Networks},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {How can we generate realistic networks? In addition, how can we do so with a mathematically tractable model that allows for rigorous analysis of network properties? Real networks exhibit a long list of surprising properties: Heavy tails for the in- and out-degree distribution, heavy tails for the eigenvalues and eigenvectors, small diameters, and densification and shrinking diameters over time. Current network models and generators either fail to match several of the above properties, are complicated to analyze mathematically, or both. Here we propose a generative model for networks that is both mathematically tractable and can generate networks that have all the above mentioned structural properties. Our main idea here is to use a non-standard matrix operation, the Kronecker product, to generate graphs which we refer to as "Kronecker graphs".First, we show that Kronecker graphs naturally obey common network properties. In fact, we rigorously prove that they do so. We also provide empirical evidence showing that Kronecker graphs can effectively model the structure of real networks.We then present KRONFIT, a fast and scalable algorithm for fitting the Kronecker graph generation model to large real networks. A naive approach to fitting would take super-exponential time. In contrast, KRONFIT takes linear time, by exploiting the structure of Kronecker matrix multiplication and by using statistical simulation techniques.Experiments on a wide range of large real and synthetic networks show that KRONFIT finds accurate parameters that very well mimic the properties of target networks. In fact, using just four parameters we can accurately model several aspects of global network structure. Once fitted, the model parameters can be used to gain insights about the network structure, and the resulting synthetic graphs can be used for null-models, anonymization, extrapolations, and graph summarization.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {985–1042},
numpages = {58}
}

@article{10.5555/1756006.1756038,
author = {Mann, Gideon S. and McCallum, Andrew},
title = {Generalized Expectation Criteria for Semi-Supervised Learning with Weakly Labeled Data},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper, we present an overview of generalized expectation criteria (GE), a simple, robust, scalable method for semi-supervised training using weakly-labeled data. GE fits model parameters by favoring models that match certain expectation constraints, such as marginal label distributions, on the unlabeled data. This paper shows how to apply generalized expectation criteria to two classes of parametric models: maximum entropy models and conditional random fields. Experimental results demonstrate accuracy improvements over supervised training and a number of other state-of-the-art semi-supervised learning methods for these models.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {955–984},
numpages = {30}
}

@article{10.5555/1756006.1756037,
author = {Argyriou, Andreas and Micchelli, Charles A. and Pontil, Massimiliano},
title = {On Spectral Learning},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper, we study the problem of learning a matrix W from a set of linear measurements. Our formulation consists in solving an optimization problem which involves regularization with a spectral penalty term. That is, the penalty term is a function of the spectrum of the covariance of W. Instances of this problem in machine learning include multi-task learning, collaborative filtering and multi-view learning, among others. Our goal is to elucidate the form of the optimal solution of spectral learning. The theory of spectral learning relies on the von Neumann characterization of orthogonally invariant norms and their association with symmetric gauge functions. Using this tool we formulate a representer theorem for spectral regularization and specify it to several useful example, such as Schatten p-norms, trace norm and spectral norm, which should proved useful in applications.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {935–953},
numpages = {19}
}

@article{10.5555/1756006.1756036,
author = {Rosasco, Lorenzo and Belkin, Mikhail and Vito, Ernesto De},
title = {On Learning with Integral Operators},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A large number of learning algorithms, for example, spectral clustering, kernel Principal Components Analysis and many manifold methods are based on estimating eigenvalues and eigenfunctions of operators defined by a similarity function or a kernel, given empirical data. Thus for the analysis of algorithms, it is an important problem to be able to assess the quality of such approximations. The contribution of our paper is two-fold: 1. We use a technique based on a concentration inequality for Hilbert spaces to provide new much simplified proofs for a number of results in spectral approximation. 2. Using these methods we provide several new results for estimating spectral properties of the graph Laplacian operator extending and strengthening results from von Luxburg et al. (2008).},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {905–934},
numpages = {30}
}

@article{10.5555/1756006.1756035,
author = {Laparra, Valero and Guti\'{e}rrez, Juan and Camps-Valls, Gustavo and Malo, Jes\'{u}s},
title = {Image Denoising with Kernels Based on Natural Image Relations},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A successful class of image denoising methods is based on Bayesian approaches working in wavelet representations. The performance of these methods improves when relations among the local frequency coefficients are explicitly included. However, in these techniques, analytical estimates can be obtained only for particular combinations of analytical models of signal and noise, thus precluding its straightforward extension to deal with other arbitrary noise sources.In this paper, we propose an alternative non-explicit way to take into account the relations among natural image wavelet coefficients for denoising: we use support vector regression (SVR) in the wavelet domain to enforce these relations in the estimated signal. Since relations among the coefficients are specific to the signal, the regularization property of SVR is exploited to remove the noise, which does not share this feature. The specific signal relations are encoded in an anisotropic kernel obtained from mutual information measures computed on a representative image database. In the proposed scheme, training considers minimizing the Kullback-Leibler divergence (KLD) between the estimated and actual probability functions (or histograms) of signal and noise in order to enforce similarity up to the higher (computationally estimable) order. Due to its non-parametric nature, the method can eventually cope with different noise sources without the need of an explicit re-formulation, as it is strictly necessary under parametric Bayesian formalisms.Results under several noise levels and noise sources show that: (1) the proposed method outperforms conventional wavelet methods that assume coefficient independence, (2) it is similar to state-of-the-art methods that do explicitly include these relations when the noise source is Gaussian, and (3) it gives better numerical and visual performance when more complex, realistic noise sources are considered. Therefore, the proposed machine learning approach can be seen as a more flexible (model-free) alternative to the explicit description of wavelet coefficient relations for image denoising.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {873–903},
numpages = {31}
}

@article{10.5555/1756006.1756034,
author = {Ben-Haim, Yael and Tom-Tov, Elad},
title = {A Streaming Parallel Decision Tree Algorithm},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We propose a new algorithm for building decision tree classifiers. The algorithm is executed in a distributed environment and is especially designed for classifying large data sets and streaming data. It is empirically shown to be as accurate as a standard decision tree classifier, while being scalable for processing of streaming data on multiple processors. These findings are supported by a rigorous analysis of the algorithm's accuracy.The essence of the algorithm is to quickly construct histograms at the processors, which compress the data to a fixed amount of memory. A master processor uses this information to find near-optimal split points to terminal tree nodes. Our analysis shows that guarantees on the local accuracy of split points imply guarantees on the overall tree accuracy.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {849–872},
numpages = {24}
}

@article{10.5555/1756006.1756033,
author = {Huang, Fang-Lan and Hsieh, Cho-Jui and Chan, Kai-Wei and Lin, Chih-Jen},
title = {Iterative Scaling and Coordinate Descent Methods for Maximum Entropy Models},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Maximum entropy (Maxent) is useful in natural language processing and many other areas. Iterative scaling (IS) methods are one of the most popular approaches to solve Maxent. With many variants of IS methods, it is difficult to understand them and see the differences. In this paper, we create a general and unified framework for iterative scaling methods. This framework also connects iterative scaling and coordinate descent methods. We prove general convergence results for IS methods and analyze their computational complexity. Based on the proposed framework, we extend a coordinate descent method for linear SVM to Maxent. Results show that it is faster than existing iterative scaling methods.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {815–848},
numpages = {34}
}

@article{10.5555/1756006.1756032,
author = {Mohri, Mehryar and Rostamizadeh, Afshin},
title = {Stability Bounds for Stationary φ-Mixing and β-Mixing Processes},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Most generalization bounds in learning theory are based on some measure of the complexity of the hypothesis class used, independently of any algorithm. In contrast, the notion of algorithmic stability can be used to derive tight generalization bounds that are tailored to specific learning algorithms by exploiting their particular properties. However, as in much of learning theory, existing stability analyses and bounds apply only in the scenario where the samples are independently and identically distributed. In many machine learning applications, however, this assumption does not hold. The observations received by the learning algorithm often have some inherent temporal dependence.This paper studies the scenario where the observations are drawn from a stationary φ-mixing or β-mixing sequence, a widely adopted assumption in the study of non-i.i.d. processes that implies a dependence between observations weakening over time. We prove novel and distinct stability-based generalization bounds for stationary φ-mixing and β-mixing sequences. These bounds strictly generalize the bounds given in the i.i.d. case and apply to all stable learning algorithms, thereby extending the use of stability-bounds to non-i.i.d. scenarios.We also illustrate the application of our φ-mixing generalization bounds to general classes of learning algorithms, including Support Vector Regression, Kernel Ridge Regression, and Support Vector Machines, and many other kernel regularization-based and relative entropy-based regularization algorithms. These novel bounds can thus be viewed as the first theoretical basis for the use of these algorithms in non-i.i.d. scenarios.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {789–814},
numpages = {26}
}

@article{10.5555/1756006.1756031,
author = {Shivaswamy, Pannagadatta K. and Jebara, Tony},
title = {Maximum Relative Margin and Data-Dependent Regularization},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Leading classification methods such as support vector machines (SVMs) and their counterparts achieve strong generalization performance by maximizing the margin of separation between data classes. While the maximum margin approach has achieved promising performance, this article identifies its sensitivity to affine transformations of the data and to directions with large data spread. Maximum margin solutions may be misled by the spread of data and preferentially separate classes along large spread directions. This article corrects these weaknesses by measuring margin not in the absolute sense but rather only relative to the spread of data in any projection direction. Maximum relative margin corresponds to a data-dependent regularization on the classification function while maximum absolute margin corresponds to an l2 norm constraint on the classification function. Interestingly, the proposed improvements only require simple extensions to existing maximum margin formulations and preserve the computational efficiency of SVMs. Through the maximization of relative margin, surprising performance gains are achieved on real-world problems such as digit, text classification and on several other benchmark data sets. In addition, risk bounds are derived for the new formulation based on Rademacher averages.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {747–788},
numpages = {42}
}

@article{10.5555/1756006.1756030,
author = {Schaul, Tom and Bayer, Justin and Wierstra, Daan and Sun, Yi and Felder, Martin and Sehnke, Frank and R\"{u}ckstie\ss{}, Thomas and Schmidhuber, J\"{u}rgen},
title = {PyBrain},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {PyBrain is a versatile machine learning library for Python. Its goal is to provide flexible, easy-to-use yet still powerful algorithms for machine learning tasks, including a variety of predefined environments and benchmarks to test and compare algorithms. Implemented algorithms include Long Short-Term Memory (LSTM), policy gradient methods, (multidimensional) recurrent neural networks and deep belief networks.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {743–746},
numpages = {4}
}

@article{10.5555/1756006.1756029,
author = {Shi, Jianing and Yin, Wotao and Osher, Stanley and Sajda, Paul},
title = {A Fast Hybrid Algorithm for Large-Scale <i>l<sub>1</sub></i>-Regularized Logistic Regression},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {l1-regularized logistic regression, also known as sparse logistic regression, is widely used in machine learning, computer vision, data mining, bioinformatics and neural signal processing. The use of l1 regularization attributes attractive properties to the classifier, such as feature selection, robustness to noise, and as a result, classifier generality in the context of supervised learning. When a sparse logistic regression problem has large-scale data in high dimensions, it is computationally expensive to minimize the non-differentiable l1-norm in the objective function. Motivated by recent work (Koh et al., 2007; Hale et al., 2008), we propose a novel hybrid algorithm based on combining two types of optimization iterations: one being very fast and memory friendly while the other being slower but more accurate. Called hybrid iterative shrinkage (HIS), the resulting algorithm is comprised of a fixed point continuation phase and an interior point phase. The first phase is based completely on memory efficient operations such as matrix-vector multiplications, while the second phase is based on a truncated Newton's method. Furthermore, we show that various optimization techniques, including line search and continuation, can significantly accelerate convergence. The algorithm has global convergence at a geometric rate (a Q-linear rate in optimization terminology). We present a numerical comparison with several existing algorithms, including an analysis using benchmark data from the UCI machine learning repository, and show our algorithm is the most computationally efficient without loss of accuracy.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {713–741},
numpages = {29}
}

@article{10.5555/1756006.1756028,
author = {Biau, G\'{e}rard and C\'{e}rou, Fr\'{e}d\'{e}ric and Guyader, Arnaud},
title = {On the Rate of Convergence of the Bagged Nearest Neighbor Estimate},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Bagging is a simple way to combine estimates in order to improve their performance. This method, suggested by Breiman in 1996, proceeds by resampling from the original data set, constructing a predictor from each subsample, and decide by combining. By bagging an n-sample, the crude nearest neighbor regression estimate is turned into a consistent weighted nearest neighbor regression estimate, which is amenable to statistical analysis. Letting the resampling size kn grows appropriately with n, it is shown that this estimate may achieve optimal rate of convergence, independently from the fact that resampling is done with or without replacement. Since the estimate with the optimal rate of convergence depends on the unknown distribution of the observations, adaptation results by data-splitting are presented.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {687–712},
numpages = {26}
}

@article{10.5555/1756006.1756027,
author = {Christoforou, Christoforos and Haralick, Robert and Sajda, Paul and Parra, Lucas C.},
title = {Second-Order Bilinear Discriminant Analysis},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Traditional analysis methods for single-trial classification of electro-encephalography (EEG) focus on two types of paradigms: phase-locked methods, in which the amplitude of the signal is used as the feature for classification, that is, event related potentials; and second-order methods, in which the feature of interest is the power of the signal, that is, event related (de)synchronization. The process of deciding which paradigm to use is ad hoc and is driven by assumptions regarding the underlying neural generators. Here we propose a method that provides an unified framework for the analysis of EEG, combining first and second-order spatial and temporal features based on a bilinear model. Evaluation of the proposed method on simulated data shows that the technique outperforms state-of-the art techniques for single-trial classification for a broad range of signal-to-noise ratios. Evaluations on human EEG--including one benchmark data set from the Brain Computer Interface (BCI) competition--show statistically significant gains in classification accuracy, with a reduction in overall classification error from 26%-28% to 19%.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {665–685},
numpages = {21}
}

@article{10.5555/1756006.1756026,
author = {Escalera, Sergio and Pujol, Oriol and Radeva, Petia},
title = {Error-Correcting Ouput Codes Library},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper, we present an open source Error-Correcting Output Codes (ECOC) library. The ECOC framework is a powerful tool to deal with multi-class categorization problems. This library contains both state-of-the-art coding (one-versus-one, one-versus-all, dense random, sparse random, DECOC, forest-ECOC, and ECOC-ONE) and decoding designs (hamming, euclidean, inverse hamming, laplacian, β-density, attenuated, loss-based, probabilistic kernel-based, and loss-weighted) with the parameters defined by the authors, as well as the option to include your own coding, decoding, and base classifier.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {661–664},
numpages = {4}
}

@article{10.5555/1756006.1756025,
author = {Erhan, Dumitru and Bengio, Yoshua and Courville, Aaron and Manzagol, Pierre-Antoine and Vincent, Pascal and Bengio, Samy},
title = {Why Does Unsupervised Pre-Training Help Deep Learning?},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Much recent research has been devoted to learning algorithms for deep architectures such as Deep Belief Networks and stacks of auto-encoder variants, with impressive results obtained in several areas, mostly on vision and language data sets. The best results obtained on supervised learning tasks involve an unsupervised learning component, usually in an unsupervised pre-training phase. Even though these new algorithms have enabled training deep models, many questions remain as to the nature of this difficult learning problem. The main question investigated here is the following: how does unsupervised pre-training work? Answering this questions is important if learning in deep architectures is to be further improved. We propose several explanatory hypotheses and test them through extensive simulations. We empirically show the influence of pre-training with respect to architecture depth, model capacity, and number of training examples. The experiments confirm and clarify the advantage of unsupervised pre-training. The results suggest that unsupervised pre-training guides the learning towards basins of attraction of minima that support better generalization from the training data set; the evidence from these results supports a regularization explanation for the effect of pre-training.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {625–660},
numpages = {36}
}

@article{10.5555/1756006.1756024,
author = {Perry, Patrick O. and Owen, Art B.},
title = {A Rotation Test to Verify Latent Structure},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In multivariate regression models we have the opportunity to look for hidden structure unrelated to the observed predictors. However, when one fits a model involving such latent variables it is important to be able to tell if the structure is real, or just an artifact of correlation in the regression errors. We develop a new statistical test based on random rotations for verifying the existence of latent variables. The rotations are carefully constructed to rotate orthogonally to the column space of the regression model. We find that only non-Gaussian latent variables are detectable, a finding that parallels a well known phenomenon in independent components analysis. We base our test on a measure of non-Gaussianity in the histogram of the principal eigenvector components instead of on the eigenvalue. The method finds and verifies some latent dichotomies in the microarray data from the AGEMAP consortium.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {603–624},
numpages = {22}
}

@article{10.5555/1756006.1756023,
author = {Ryabko, Daniil},
title = {On Finding Predictors for Arbitrary Families of Processes},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The problem is sequence prediction in the following setting. A sequence x1,...,xn,... of discrete-valued observations is generated according to some unknown probabilistic law (measure) μ. After observing each outcome, it is required to give the conditional probabilities of the next observation. The measure μ belongs to an arbitrary but known class C of stochastic process measures. We are interested in predictors ρ whose conditional probabilities converge (in some sense) to the "true" μ-conditional probabilities, if any μ∈C is chosen to generate the sequence. The contribution of this work is in characterizing the families C for which such predictors exist, and in providing a specific and simple form in which to look for a solution. We show that if any predictor works, then there exists a Bayesian predictor, whose prior is discrete, and which works too. We also find several sufficient and necessary conditions for the existence of a predictor, in terms of topological characterizations of the family C, as well as in terms of local behaviour of the measures in C, which in some cases lead to procedures for constructing such predictors.It should be emphasized that the framework is completely general: the stochastic processes considered are not required to be i.i.d., stationary, or to belong to any parametric or countable family.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {581–602},
numpages = {22}
}

@article{10.5555/1756006.1756022,
author = {Rieck, Konrad and Krueger, Tammo and Brefeld, Ulf and M\"{u}ller, Klaus-Robert},
title = {Approximate Tree Kernels},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {555–580},
numpages = {26}
}

@article{10.5555/1756006.1756021,
author = {Journ\'{e}e, Michel and Nesterov, Yurii and Richt\'{a}rik, Peter and Sepulchre, Rodolphe},
title = {Generalized Power Method for Sparse Principal Component Analysis},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, and are therefore computationally intractable, we rewrite them into the form of an optimization program involving maximization of a convex function on a compact set. The dimension of the search space is decreased enormously if the data matrix has many more columns (variables) than rows. We then propose and analyze a simple gradient method suited for the task. It appears that our algorithm has best convergence properties in the case when either the objective function or the feasible set are strongly convex, which is the case with our single-unit formulations and can be enforced in the block case. Finally, we demonstrate numerically on a set of random and gene expression test problems that our approach outperforms existing algorithms both in quality of the obtained solution and in computational speed.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {517–553},
numpages = {37}
}

@article{10.5555/1756006.1756020,
author = {Varshney, Kush R. and Willsky, Alan S.},
title = {Classification Using Geometric Level Sets},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A variational level set method is developed for the supervised classification problem. Nonlinear classifier decision boundaries are obtained by minimizing an energy functional that is composed of an empirical risk term with a margin-based loss and a geometric regularization term new to machine learning: the surface area of the decision boundary. This geometric level set classifier is analyzed in terms of consistency and complexity through the calculation of its ε-entropy. For multicategory classification, an efficient scheme is developed using a logarithmic number of decision functions in the number of classes rather than the typical linear number of decision functions. Geometric level set classification yields performance results on benchmark data sets that are competitive with well-established methods.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {491–516},
numpages = {26}
}

@article{10.5555/1756006.1756019,
author = {Venna, Jarkko and Peltonen, Jaakko and Nybo, Kristian and Aidos, Helena and Kaski, Samuel},
title = {Information Retrieval Perspective to Nonlinear Dimensionality Reduction for Data Visualization},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Nonlinear dimensionality reduction methods are often used to visualize high-dimensional data, although the existing methods have been designed for other related tasks such as manifold learning. It has been difficult to assess the quality of visualizations since the task has not been well-defined. We give a rigorous definition for a specific visualization task, resulting in quantifiable goodness measures and new visualization methods. The task is information retrieval given the visualization: to find similar data based on the similarities shown on the display. The fundamental tradeoff between precision and recall of information retrieval can then be quantified in visualizations as well. The user needs to give the relative cost of missing similar points vs. retrieving dissimilar points, after which the total cost can be measured. We then introduce a new method NeRV (neighbor retrieval visualizer) which produces an optimal visualization by minimizing the cost. We further derive a variant for supervised visualization; class information is taken rigorously into account when computing the similarity relationships. We show empirically that the unsupervised version outperforms existing unsupervised dimensionality reduction methods in the visualization task, and the supervised version outperforms existing supervised methods.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {451–490},
numpages = {40}
}

@article{10.5555/1756006.1756018,
author = {Mordohai, Philippos and Medioni, G\'{e}rard},
title = {Dimensionality Estimation, Manifold Learning and Function Approximation Using Tensor Voting},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We address instance-based learning from a perceptual organization standpoint and present methods for dimensionality estimation, manifold learning and function approximation. Under our approach, manifolds in high-dimensional spaces are inferred by estimating geometric relationships among the input instances. Unlike conventional manifold learning, we do not perform dimensionality reduction, but instead perform all operations in the original input space. For this purpose we employ a novel formulation of tensor voting, which allows an N-D implementation. Tensor voting is a perceptual organization framework that has mostly been applied to computer vision problems. Analyzing the estimated local structure at the inputs, we are able to obtain reliable dimensionality estimates at each instance, instead of a global estimate for the entire data set. Moreover, these local dimensionality and structure estimates enable us to measure geodesic distances and perform nonlinear interpolation for data sets with varying density, outliers, perturbation and intersections, that cannot be handled by state-of-the-art methods. Quantitative results on the estimation of local manifold structure using ground truth data are presented. In addition, we compare our approach with several leading methods for manifold learning at the task of measuring geodesic distances. Finally, we show competitive function approximation results on real data.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {411–450},
numpages = {40}
}

@article{10.5555/1756006.1756017,
author = {Castro, Dotan Di and Meir, Ron},
title = {A Convergent Online Single Time Scale Actor Critic Algorithm},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Actor-Critic based approaches were among the first to address reinforcement learning in a general setting. Recently, these algorithms have gained renewed interest due to their generality, good convergence properties, and possible biological relevance. In this paper, we introduce an online temporal difference based actor-critic algorithm which is proved to converge to a neighborhood of a local maximum of the average reward. Linear function approximation is used by the critic in order estimate the value function, and the temporal difference signal, which is passed from the critic to the actor. The main distinguishing feature of the present convergence proof is that both the actor and the critic operate on a similar time scale, while in most current convergence proofs they are required to have very different time scales in order to converge. Moreover, the same temporal difference signal is used to update the parameters of both the actor and the critic. A limitation of the proposed approach, compared to results available for two time scale convergence, is that convergence is guaranteed only to a neighborhood of an optimal value, rather to an optimal value itself. The single time scale and identical temporal difference signal used by the actor and the critic, may provide a step towards constructing more biologically realistic models of reinforcement learning in the brain.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {367–410},
numpages = {44}
}

@article{10.5555/1756006.1756016,
author = {Teo, Choon Hui and Vishwanthan, S.V.N. and Smola, Alex J. and Le, Quoc V.},
title = {Bundle Methods for Regularized Risk Minimization},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A wide variety of machine learning problems can be described as minimizing a regularized risk functional, with different algorithms using different notions of risk and different regularizers. Examples include linear Support Vector Machines (SVMs), Gaussian Processes, Logistic Regression, Conditional Random Fields (CRFs), and Lasso amongst others. This paper describes the theory and implementation of a scalable and modular convex solver which solves all these estimation problems. It can be parallelized on a cluster of workstations, allows for data-locality, and can deal with regularizers such as L1 and L2 penalties. In addition to the unified framework we present tight convergence bounds, which show that our algorithm converges in O(1/ε) steps to ε precision for general convex problems and in O(log (1/ε)) steps for continuously differentiable problems. We demonstrate the performance of our general purpose solver on a variety of publicly available data sets.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {311–365},
numpages = {55}
}

@article{10.5555/1756006.1756015,
author = {Kojima, Kaname and Perrier, Eric and Imoto, Seiya and Miyano, Satoru},
title = {Optimal Search on Clustered Structural Constraint for Learning Bayesian Network Structure},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We study the problem of learning an optimal Bayesian network in a constrained search space; skeletons are compelled to be subgraphs of a given undirected graph called the super-structure. The previously derived constrained optimal search (COS) remains limited even for sparse super-structures. To extend its feasibility, we propose to divide the super-structure into several clusters and perform an optimal search on each of them. Further, to ensure acyclicity, we introduce the concept of ancestral constraints (ACs) and derive an optimal algorithm satisfying a given set of ACs. Finally, we theoretically derive the necessary and sufficient sets of ACs to be considered for finding an optimal constrained graph. Empirical evaluations demonstrate that our algorithm can learn optimal Bayesian networks for some graphs containing several hundreds of vertices, and even for super-structures having a high average degree (up to four), which is a drastic improvement in feasibility over the previous optimal algorithm. Learnt networks are shown to largely outperform state-of-the-art heuristic algorithms both in terms of score and structural hamming distance.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {285–310},
numpages = {26}
}

@article{10.5555/1756006.1756014,
author = {Aliferis, Constantin F. and Statnikov, Alexander and Tsamardinos, Ioannis and Mani, Subramani and Koutsoukos, Xenofon D.},
title = {Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification Part II: Analysis and Extensions},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In part I of this work we introduced and evaluated the Generalized Local Learning (GLL) framework for producing local causal and Markov blanket induction algorithms. In the present second part we analyze the behavior of GLL algorithms and provide extensions to the core methods. Specifically, we investigate the empirical convergence of GLL to the true local neighborhood as a function of sample size. Moreover, we study how predictivity improves with increasing sample size. Then we investigate how sensitive are the algorithms to multiple statistical testing, especially in the presence of many irrelevant features. Next we discuss the role of the algorithm parameters and also show that Markov blanket and causal graph concepts can be used to understand deviations from optimality of state-of-the-art non-causal algorithms. The present paper also introduces the following extensions to the core GLL framework: parallel and distributed versions of GLL algorithms, versions with false discovery rate control, strategies for constructing novel heuristics for specific domains, and divide-and-conquer local-to-global learning (LGL) strategies. We test the generality of the LGL approach by deriving a novel LGL-based algorithm that compares favorably to the state-of-the-art global learning algorithms. In addition, we investigate the use of non-causal feature selection methods to facilitate global learning. Open problems and future research paths related to local and local-to-global causal learning are discussed.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {235–284},
numpages = {50}
}

@article{10.5555/1756006.1756013,
author = {Aliferis, Constantin F. and Statnikov, Alexander and Tsamardinos, Ioannis and Mani, Subramani and Koutsoukos, Xenofon D.},
title = {Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification Part I: Algorithms and Empirical Evaluation},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We present an algorithmic framework for learning local causal structure around target variables of interest in the form of direct causes/effects and Markov blankets applicable to very large data sets with relatively small samples. The selected feature sets can be used for causal discovery and classification. The framework (Generalized Local Learning, or GLL) can be instantiated in numerous ways, giving rise to both existing state-of-the-art as well as novel algorithms. The resulting algorithms are sound under well-defined sufficient conditions. In a first set of experiments we evaluate several algorithms derived from this framework in terms of predictivity and feature set parsimony and compare to other local causal discovery methods and to state-of-the-art non-causal feature selection methods using real data. A second set of experimental evaluations compares the algorithms in terms of ability to induce local causal neighborhoods using simulated and resimulated data and examines the relation of predictivity with causal induction performance.Our experiments demonstrate, consistently with causal feature selection theory, that local causal feature selection methods (under broad assumptions encompassing appropriate family of distributions, types of classifiers, and loss functions) exhibit strong feature set parsimony, high predictivity and local causal interpretability. Although non-causal feature selection methods are often used in practice to shed light on causal relationships, we find that they cannot be interpreted causally even when they achieve excellent predictivity. Therefore we conclude that only local causal techniques should be used when insight into causal structure is sought. In a companion paper we examine in depth the behavior of GLL algorithms, provide extensions, and show how local techniques can be used for scalable and accurate global causal graph learning.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {171–234},
numpages = {64}
}

@article{10.5555/1756006.1756012,
author = {Ding, Yufeng and Simonoff, Jeffrey S.},
title = {An Investigation of Missing Data Methods for Classification Trees Applied to Binary Response Data},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {There are many different methods used by classification tree algorithms when missing data occur in the predictors, but few studies have been done comparing their appropriateness and performance. This paper provides both analytic and Monte Carlo evidence regarding the effectiveness of six popular missing data methods for classification trees applied to binary response data. We show that in the context of classification trees, the relationship between the missingness and the dependent variable, as well as the existence or non-existence of missing values in the testing data, are the most helpful criteria to distinguish different missing data methods. In particular, separate class is clearly the best method to use when the testing set has missing values and the missingness is related to the response variable. A real data set related to modeling bankruptcy of a firm is then analyzed. The paper concludes with discussion of adaptation of these results to logistic regression, and other potential generalizations.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {131–170},
numpages = {40}
}

@article{10.5555/1756006.1756011,
author = {Yuan, Ming and Wegkamp, Marten},
title = {Classification Methods with Reject Option Based on Convex Risk Minimization},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper, we investigate the problem of binary classification with a reject option in which one can withhold the decision of classifying an observation at a cost lower than that of misclassification. Since the natural loss function is non-convex so that empirical risk minimization easily becomes infeasible, the paper proposes minimizing convex risks based on surrogate convex loss functions. A necessary and sufficient condition for infinite sample consistency (both risks share the same minimizer) is provided. Moreover, we show that the excess risk can be bounded through the excess surrogate risk under appropriate conditions. These bounds can be tightened by a generalized margin condition. The impact of the results is illustrated on several commonly used surrogate loss functions.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {111–130},
numpages = {20}
}

@article{10.5555/1756006.1756010,
author = {Gy\"{o}rgy, Andr\'{a}s and Lugosi, G\'{a}bor and Ottucs\`{a}k, Gy\"{o}rgy},
title = {On-Line Sequential Bin Packing},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We consider a sequential version of the classical bin packing problem in which items are received one by one. Before the size of the next item is revealed, the decision maker needs to decide whether the next item is packed in the currently open bin or the bin is closed and a new bin is opened. If the new item does not fit, it is lost. If a bin is closed, the remaining free space in the bin accounts for a loss. The goal of the decision maker is to minimize the loss accumulated over n periods. We present an algorithm that has a cumulative loss not much larger than any strategy in a finite class of reference strategies for any sequence of items. Special attention is payed to reference strategies that use a fixed threshold at each step to decide whether a new bin is opened. Some positive and negative results are presented for this case.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {89–109},
numpages = {21}
}

@article{10.5555/1756006.1756009,
author = {Guyon, Isabelle and Saffari, Amir and Dror, Gideon and Cawley, Gavin},
title = {Model Selection: Beyond the Bayesian/Frequentist Divide},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The principle of parsimony also known as "Ockham's razor" has inspired many theories of model selection. Yet such theories, all making arguments in favor of parsimony, are based on very different premises and have developed distinct methodologies to derive algorithms. We have organized challenges and edited a special issue of JMLR and several conference proceedings around the theme of model selection. In this editorial, we revisit the problem of avoiding overfitting in light of the latest results. We note the remarkable convergence of theories as different as Bayesian theory, Minimum Description Length, bias/variance tradeoff, Structural Risk Minimization, and regularization, in some approaches. We also present new and interesting examples of the complementarity of theories leading to hybrid algorithms, neither frequentist, nor Bayesian, or perhaps both frequentist and Bayesian!},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {61–87},
numpages = {27}
}

@article{10.5555/1756006.1756008,
author = {Mairal, Julien and Bach, Francis and Ponce, Jean and Sapiro, Guillermo},
title = {Online Learning for Matrix Factorization and Sparse Coding},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Sparse coding--that is, modelling data vectors as sparse linear combinations of basis elements--is widely used in machine learning, neuroscience, signal processing, and statistics. This paper focuses on the large-scale matrix factorization problem that consists of learning the basis set in order to adapt it to specific data. Variations of this problem include dictionary learning in signal processing, non-negative matrix factorization and sparse principal component analysis. In this paper, we propose to address these tasks with a new online optimization algorithm, based on stochastic approximations, which scales up gracefully to large data sets with millions of training samples, and extends naturally to various matrix factorization formulations, making it suitable for a wide range of learning problems. A proof of convergence is presented, along with experiments with natural images and genomic data demonstrating that it leads to state-of-the-art performance in terms of speed and optimization for both small and large data sets.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {19–60},
numpages = {42}
}

@article{10.5555/1756006.1756007,
author = {Strumbelj, Erik and Kononenko, Igor},
title = {An Efficient Explanation of Individual Classifications Using Game Theory},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We present a general method for explaining individual predictions of classification models. The method is based on fundamental concepts from coalitional game theory and predictions are explained with contributions of individual feature values. We overcome the method's initial exponential time complexity with a sampling-based approximation. In the experimental part of the paper we use the developed method on models generated by several well-known machine learning algorithms on both synthetic and real-world data sets. The results demonstrate that the method is efficient and that the explanations are intuitive and useful.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1–18},
numpages = {18}
}

@article{10.5555/1577069.1755883,
author = {Gunawardana, Asela and Shani, Guy},
title = {A Survey of Accuracy Evaluation Metrics of Recommendation Tasks},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Recommender systems are now popular both commercially and in the research community, where many algorithms have been suggested for providing recommendations. These algorithms typically perform differently in various domains and tasks. Therefore, it is important from the research perspective, as well as from a practical view, to be able to decide on an algorithm that matches the domain and the task of interest. The standard way to make such decisions is by comparing a number of algorithms offline using some evaluation metric. Indeed, many evaluation metrics have been suggested for comparing recommendation algorithms. The decision on the proper evaluation metric is often critical, as each metric may favor a different algorithm. In this paper we review the proper construction of offline experiments for deciding on the most appropriate algorithm. We discuss three important tasks of recommender systems, and classify a set of appropriate well known evaluation metrics for each task. We demonstrate how using an improper evaluation metric can lead to the selection of an improper algorithm for the task of interest. We also discuss other important considerations when designing offline experiments.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2935–2962},
numpages = {28}
}

@article{10.5555/1577069.1755882,
author = {Duchi, John and Singer, Yoram},
title = {Efficient Online and Batch Learning Using Forward Backward Splitting},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We describe, analyze, and experiment with a framework for empirical loss minimization with regularization. Our algorithmic framework alternates between two phases. On each iteration we first perform an unconstrained gradient descent step. We then cast and solve an instantaneous optimization problem that trades off minimization of a regularization term while keeping close proximity to the result of the first phase. This view yields a simple yet effective algorithm that can be used for batch penalized risk minimization and online learning. Furthermore, the two phase approach enables sparse solutions when used in conjunction with regularization functions that promote sparsity, such as l1. We derive concrete and very simple algorithms for minimization of loss functions with l1, l2, l22, and l∞ regularization. We also show how to construct efficient algorithms for mixed-norm l1/lq regularization. We further extend the algorithms and give efficient implementations for very high-dimensional data with sparsity. We demonstrate the potential of the proposed framework in a series of experiments with synthetic and natural data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2899–2934},
numpages = {36}
}

@article{10.5555/1577069.1755881,
author = {Hu, Ting and Zhou, Ding-Xuan},
title = {Online Learning with Samples Drawn from Non-Identical Distributions},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Learning algorithms are based on samples which are often drawn independently from an identical distribution (i.i.d.). In this paper we consider a different setting with samples drawn according to a non-identical sequence of probability distributions. Each time a sample is drawn from a different distribution. In this setting we investigate a fully online learning algorithm associated with a general convex loss function and a reproducing kernel Hilbert space (RKHS). Error analysis is conducted under the assumption that the sequence of marginal distributions converges polynomially in the dual of a H\"{o}lder space. For regression with least square or insensitive loss, learning rates are given in both the RKHS norm and the L2 norm. For classification with hinge loss and support vector machine q-norm loss, rates are explicitly stated with respect to the excess misclassification error.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2873–2898},
numpages = {26}
}

@article{10.5555/1577069.1755880,
author = {Blanchard, Gilles and Roquain, \'{E}tienne},
title = {Adaptive False Discovery Rate Control under Independence and Dependence},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In the context of multiple hypothesis testing, the proportion π0 of true null hypotheses in the pool of hypotheses to test often plays a crucial role, although it is generally unknown a priori. A testing procedure using an implicit or explicit estimate of this quantity in order to improve its efficency is called adaptive. In this paper, we focus on the issue of false discovery rate (FDR) control and we present new adaptive multiple testing procedures with control of the FDR. In a first part, assuming independence of the p-values, we present two new procedures and give a unified review of other existing adaptive procedures that have provably controlled FDR. We report extensive simulation results comparing these procedures and testing their robustness when the independence assumption is violated. The new proposed procedures appear competitive with existing ones. The overall best, though, is reported to be Storey's estimator, albeit for a specific parameter setting that does not appear to have been considered before. In a second part, we propose adaptive versions of step-up procedures that have provably controlled FDR under positive dependence and unspecified dependence of the p-values, respectively. In the latter case, while simulations only show an improvement over non-adaptive procedures in limited situations, these are to our knowledge among the first theoretically founded adaptive multiple testing procedures that control the FDR when the p-values are not independent.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2837–2871},
numpages = {35}
}

@article{10.5555/1577069.1755879,
author = {McDowell, Luke K. and Gupta, Kalyan Moy and Aha, David W.},
title = {Cautious Collective Classification},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Many collective classification (CC) algorithms have been shown to increase accuracy when instances are interrelated. However, CC algorithms must be carefully applied because their use of estimated labels can in some cases decrease accuracy. In this article, we show that managing this label uncertainty through cautious algorithmic behavior is essential to achieving maximal, robust performance. First, we describe cautious inference and explain how four well-known families of CC algorithms can be parameterized to use varying degrees of such caution. Second, we introduce cautious learning and show how it can be used to improve the performance of almost any CC algorithm, with or without cautious inference. We then evaluate cautious inference and learning for the four collective inference families, with three local classifiers and a range of both synthetic and real-world data. We find that cautious learning and cautious inference typically outperform less cautious approaches. In addition, we identify the data characteristics that predict more substantial performance differences. Our results reveal that the degree of caution used usually has a larger impact on performance than the choice of the underlying inference algorithm. Together, these results identify the most appropriate CC algorithms to use for particular task characteristics and explain multiple conflicting findings from prior CC research.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2777–2836},
numpages = {60}
}

@article{10.5555/1577069.1755878,
author = {Zhang, Haizhang and Xu, Yuesheng and Zhang, Jun},
title = {Reproducing Kernel Banach Spaces for Machine Learning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We introduce the notion of reproducing kernel Banach spaces (RKBS) and study special semi-inner-product RKBS by making use of semi-inner-products and the duality mapping. Properties of an RKBS and its reproducing kernel are investigated. As applications, we develop in the framework of RKBS standard learning schemes including minimal norm interpolation, regularization network, support vector machines, and kernel principal component analysis. In particular, existence, uniqueness and representer theorems are established.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2741–2775},
numpages = {35}
}

@article{10.5555/1577069.1755877,
author = {Klivans, Adam R. and Long, Philip M. and Servedio, Rocco A.},
title = {Learning Halfspaces with Malicious Noise},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We give new algorithms for learning halfspaces in the challenging  malicious noise model, where an adversary may corrupt both the labels and the underlying distribution of examples. Our algorithms can tolerate malicious noise rates exponentially larger than previous work in terms of the dependence on the dimension n, and succeed for the fairly broad class of all isotropic log-concave distributions.We give poly(n, 1/ε)-time algorithms for solving the following problems to accuracy ε: Learning origin-centered halfspaces in Rn with respect to the uniform distribution on the unit ball with malicious noise rate η = Ω(ε2 / log(n/ε)). (The best previous result was Ω(ε / (n log(n/ε))1/4).)  Learning origin-centered halfspaces with respect to any isotropic log-concave distribution on Rn with malicious noise rate η = Ω(ε3 / log2(n/ε)). This is the first efficient algorithm for learning under isotropic log-concave distributions in the presence of malicious noise. We also give a poly(n,1/ε)-time algorithm for learning origin-centered halfspaces under any isotropic log-concave distribution on Rn in the presence of adversarial label noise at rate η = Ω(ε3 / log(1/ε)). In the adversarial label noise setting (or agnostic model), labels can be noisy, but not example points themselves. Previous results could handle η = Ω(ε) but had running time exponential in an unspecified function of 1/ε.Our analysis crucially exploits both concentration and anti-concentration properties of isotropic log-concave distributions. Our algorithms combine an iterative outlier removal procedure using Principal Component Analysis together with "smooth" boosting.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2715–2740},
numpages = {26}
}

@article{10.5555/1577069.1755876,
author = {Jain, Brijnesh J. and Obermayer, Klaus},
title = {Structure Spaces},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Finite structures such as point patterns, strings, trees, and graphs occur as "natural" representations of structured data in different application areas of machine learning. We develop the theory of structure spaces and derive geometrical and analytical concepts such as the angle between structures and the derivative of functions on structures. In particular, we show that the gradient of a differentiable structural function is a well-defined structure pointing in the direction of steepest ascent. Exploiting the properties of structure spaces, it will turn out that a number of problems in structural pattern recognition such as central clustering or learning in structured output spaces can be formulated as optimization problems with cost functions that are locally Lipschitz. Hence, methods from nonsmooth analysis are applicable to optimize those cost functions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2667–2714},
numpages = {48}
}

@article{10.5555/1577069.1755875,
author = {Orabona, Francesco and Keshet, Joseph and Caputo, Barbara},
title = {Bounded Kernel-Based Online Learning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {A common problem of kernel-based online algorithms, such as the kernel-based Perceptron algorithm, is the amount of memory required to store the online hypothesis, which may increase without bound as the algorithm progresses. Furthermore, the computational load of such algorithms grows linearly with the amount of memory used to store the hypothesis. To attack these problems, most previous work has focused on discarding some of the instances, in order to keep the memory bounded. In this paper we present a new algorithm, in which the instances are not discarded, but are instead projected onto the space spanned by the previous online hypothesis. We call this algorithm Projectron. While the memory size of the Projectron solution cannot be predicted before training, we prove that its solution is guaranteed to be bounded. We derive a relative mistake bound for the proposed algorithm, and deduce from it a slightly different algorithm which outperforms the Perceptron. We call this second algorithm Projectron++. We show that this algorithm can be extended to handle the multiclass and the structured output settings, resulting, as far as we know, in the first online bounded algorithm that can learn complex classification tasks. The method of bounding the hypothesis representation can be applied to any conservative online algorithm and to other online algorithms, as it is demonstrated for ALMA2. Experimental results on various data sets show the empirical advantage of our technique compared to various bounded online algorithms, both in terms of memory and accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2643–2666},
numpages = {24}
}

@article{10.5555/1577069.1755874,
author = {Lehmann, Jens},
title = {DL-Learner: Learning Concepts in Description Logics},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In this paper, we introduce DL-Learner, a framework for learning in description logics and OWL. OWL is the official W3C standard ontology language for the Semantic Web. Concepts in this language can be learned for constructing and maintaining OWL ontologies or for solving problems similar to those in Inductive Logic Programming. DL-Learner includes several learning algorithms, support for different OWL formats, reasoner interfaces, and learning problems. It is a cross-platform framework implemented in Java. The framework allows easy programmatic access and provides a command line interface, a graphical interface as well as a WSDL-based web service.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2639–2642},
numpages = {4}
}

@article{10.5555/1577069.1755873,
author = {Shi, Qinfeng and Petterson, James and Dror, Gideon and Langford, John and Smola, Alex and Vishwanathan, S.V.N.},
title = {Hash Kernels for Structured Data},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We propose hashing to facilitate efficient kernels. This generalizes previous work using sampling and we show a principled way to compute the kernel matrix for data streams and sparse feature spaces. Moreover, we give deviation bounds from the exact kernel matrix. This has applications to estimation on strings and graphs.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2615–2637},
numpages = {23}
}

@article{10.5555/1577069.1755872,
author = {Madani, Omid and Connor, Michael and Greiner, Wiley},
title = {Learning When Concepts Abound},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Many learning tasks, such as large-scale text categorization and word prediction, can benefit from efficient training and classification when the number of classes, in addition to instances and features, is large, that is, in the thousands and beyond. We investigate the learning of sparse class indices to address this challenge. An index is a mapping from features to classes. We compare the index-learning methods against other techniques, including one-versus-rest and top-down classification using perceptrons and support vector machines. We find that index learning is highly advantageous for space and time efficiency, at both training and classification times. Moreover, this approach yields similar and at times better accuracies. On problems with hundreds of thousands of instances and thousands of classes, the index is learned in minutes, while other methods can take hours or days.As we explain, the design of the learning update enables conveniently constraining each feature to connect to a small subset of the classes in the index. This constraint is crucial for scalability. Given an instance with l active (positive-valued) features, each feature on average connecting to d classes in the index (in the order of 10s in our experiments), update and classification take O(dl log(dl)).},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2571–2613},
numpages = {43}
}

@article{10.5555/1577069.1755871,
author = {Zhu, Jun and Xing, Eric P.},
title = {Maximum Entropy Discrimination Markov Networks},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The standard maximum margin approach for structured prediction lacks a straightforward probabilistic interpretation of the learning scheme and the prediction rule. Therefore its unique advantages such as dual sparseness and kernel tricks cannot be easily conjoined with the merits of a probabilistic model such as Bayesian regularization, model averaging, and ability to model hidden variables. In this paper, we present a new general framework called maximum entropy discrimination Markov networks (MaxEnDNet, or simply, MEDN), which integrates these two approaches and combines and extends their merits. Major innovations of this approach include: 1) It extends the conventional max-entropy discrimination learning of classification rules to a new structural max-entropy discrimination paradigm of learning a distribution of Markov networks. 2) It generalizes the extant Markov network structured-prediction rule based on a point estimator of model coefficients to an averaging model akin to a Bayesian predictor that integrates over a learned posterior distribution of model coefficients. 3) It admits flexible entropic regularization of the model during learning. By plugging in different prior distributions of the model coefficients, it subsumes the well-known maximum margin Markov networks (M3N) as a special case, and leads to a model similar to an L1-regularized M3N that is simultaneously primal and dual sparse, or other new types of Markov networks. 4) It applies a modular learning algorithm that combines existing variational inference techniques and convex-optimization based M3N solvers as subroutines. Essentially, MEDN can be understood as a jointly maximum likelihood and maximum margin estimate of Markov network. It represents the first successful attempt to combine maximum entropy learning (a dual form of maximum likelihood learning) with maximum margin learning of Markov network for structured input/output problems; and the basic principle can be generalized to learning arbitrary graphical models, such as the generative Bayesian networks or models with structured hidden variables. We discuss a number of theoretical properties of this approach, and show that empirically it outperforms a wide array of competing methods for structured input/output learning on both synthetic and real OCR and web data extraction data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2531–2569},
numpages = {39}
}

@article{10.5555/1577069.1755870,
author = {Argyriou, Andreas and Micchelli, Charles A. and Pontil, Massimiliano},
title = {When Is There a Representer Theorem? Vector Versus Matrix Regularizers},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We consider a general class of regularization methods which learn a vector of parameters on the basis of linear measurements. It is well known that if the regularizer is a nondecreasing function of the L2 norm, then the learned vector is a linear combination of the input data. This result, known as the representer theorem, lies at the basis of kernel-based methods in machine learning. In this paper, we prove the necessity of the above condition, in the case of differentiable regularizers. We further extend our analysis to regularization methods which learn a matrix, a problem which is motivated by the application to multi-task learning. In this context, we study a more general representer theorem, which holds for a larger class of regularizers. We provide a necessary and sufficient condition characterizing this class of matrix regularizers and we highlight some concrete examples of practical importance. Our analysis uses basic principles from matrix theory, especially the useful notion of matrix nondecreasing functions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2507–2529},
numpages = {23}
}

@article{10.5555/1577069.1755869,
author = {Rosset, Saharon},
title = {Bi-Level Path Following for Cross Validated Solution of Kernel Quantile Regression},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We show how to follow the path of cross validated solutions to families of regularized optimization problems, defined by a combination of a parameterized loss function and a regularization term. A primary example is kernel quantile regression, where the parameter of the loss function is the quantile being estimated. Even though the bi-level optimization problem we encounter for every quantile is non-convex, the manner in which the optimal cross-validated solution evolves with the parameter of the loss function allows tracking of this solution. We prove this property, construct the resulting algorithm, and demonstrate it on real and artificial data. This algorithm allows us to efficiently solve the whole family of bi-level problems. We show how it can be extended to cover other modeling problems, like support vector regression, and alternative in-sample model selection approaches.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2473–2505},
numpages = {33}
}

@article{10.5555/1577069.1755868,
author = {Vovk, Vladimir and Zhdanov, Fedor},
title = {Prediction With Expert Advice For The Brier Game},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We show that the Brier game of prediction is mixable and find the optimal learning rate and substitution function for it. The resulting prediction algorithm is applied to predict results of football and tennis matches, with well-known bookmakers playing the role of experts. The theoretical performance guarantee is not excessively loose on the football data set and is rather tight on the tennis data set.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2445–2471},
numpages = {27}
}

@article{10.5555/1577069.1755867,
author = {Strehl, Alexander L. and Li, Lihong and Littman, Michael L.},
title = {Reinforcement Learning in Finite MDPs: PAC Analysis},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We study the problem of learning near-optimal behavior in finite Markov Decision Processes (MDPs) with a polynomial number of samples. These "PAC-MDP" algorithms include the well-known E3 and R-MAX algorithms as well as the more recent Delayed Q-learning algorithm. We summarize the current state-of-the-art by presenting bounds for the problem in a unified theoretical framework. A more refined analysis for upper and lower bounds is presented to yield insight into the differences between the model-free Delayed Q-learning and the model-based R-MAX.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2413–2444},
numpages = {32}
}

@article{10.5555/1577069.1755866,
author = {Hellerstein, Lisa and Rosell, Bernard and Bach, Eric and Ray, Soumya and Page, David},
title = {Exploiting Product Distributions to Identify Relevant Variables of Correlation Immune Functions},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {A Boolean function f is correlation immune if each input variable is independent of the output, under the uniform distribution on inputs. For example, the parity function is correlation immune. We consider the problem of identifying relevant variables of a correlation immune function, in the presence of irrelevant variables. We address this problem in two different contexts. First, we analyze Skewing, a heuristic method that was developed to improve the ability of greedy decision tree algorithms to identify relevant variables of correlation immune Boolean functions, given examples drawn from the uniform distribution (Page and Ray, 2003). We present theoretical results revealing both the capabilities and limitations of skewing. Second, we explore the problem of identifying relevant variables in the Product Distribution Choice (PDC) learning model, a model in which the learner can choose product distributions and obtain examples from them. We prove a lemma establishing a property of Boolean functions that may be of independent interest. Using this lemma, we give two new algorithms for finding relevant variables of correlation immune functions in the PDC model.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2374–2411},
numpages = {38}
}

@article{10.5555/1577069.1755865,
author = {Quadrianto, Novi and Smola, Alex J. and Caetano, Tib\'{e}rio S. and Le, Quoc V.},
title = {Estimating Labels from Label Proportions},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Consider the following problem: given sets of unlabeled observations, each set with known label proportions, predict the labels of another set of observations, possibly with known label proportions. This problem occurs in areas like e-commerce, politics, spam filtering and improper content detection. We present consistent estimators which can reconstruct the correct labels with high probability in a uniform convergence sense. Experiments show that our method works well in practice.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2349–2374},
numpages = {26}
}

@article{10.5555/1577069.1755864,
author = {Drton, Mathias and Eichler, Michael and Richardson, Thomas S.},
title = {Computing Maximum Likelihood Estimates in Recursive Linear Models with Correlated Errors},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In recursive linear models, the multivariate normal joint distribution of all variables exhibits a dependence structure induced by a recursive (or acyclic) system of linear structural equations. These linear models have a long tradition and appear in seemingly unrelated regressions, structural equation modelling, and approaches to causal inference. They are also related to Gaussian graphical models via a classical representation known as a path diagram. Despite the models' long history, a number of problems remain open. In this paper, we address the problem of computing maximum likelihood estimates in the subclass of 'bow-free' recursive linear models. The term 'bow-free' refers to the condition that the errors for variables i and j be uncorrelated if variable i occurs in the structural equation for variable j. We introduce a new algorithm, termed Residual Iterative Conditional Fitting (RICF), that can be implemented using only least squares computations. In contrast to existing algorithms, RICF has clear convergence properties and yields exact maximum likelihood estimates after the first iteration whenever the MLE is available in closed form.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2329–2348},
numpages = {20}
}

@article{10.5555/1577069.1755863,
author = {Liu, Han and Lafferty, John and Wasserman, Larry},
title = {The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Recent methods for estimating sparse undirected graphs for real-valued data in high dimensional problems rely heavily on the assumption of normality. We show how to use a semiparametric Gaussian copula---or "nonparanormal"---for high dimensional inference. Just as additive models extend linear models by replacing linear functions with a set of one-dimensional smooth functions, the nonparanormal extends the normal by transforming the variables by smooth functions. We derive a method for estimating the nonparanormal, study the method's theoretical properties, and show that it works well in many examples.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2295–2328},
numpages = {34}
}

@article{10.5555/1577069.1755862,
author = {Jos\'{e} del Coz, Juan and D\'{\i}ez, Jorge and Bahamonde, Antonio},
title = {Learning Nondeterministic Classifiers},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Nondeterministic classifiers are defined as those allowed to predict more than one class for some entries from an input space. Given that the true class should be included in predictions and the number of classes predicted should be as small as possible, these kind of classifiers can be considered as Information Retrieval (IR) procedures. In this paper, we propose a family of IR loss functions to measure the performance of nondeterministic learners. After discussing such measures, we derive an algorithm for learning optimal nondeterministic hypotheses. Given an entry from the input space, the algorithm requires the posterior probabilities to compute the subset of classes with the lowest expected loss. From a general point of view, nondeterministic classifiers provide an improvement in the proportion of predictions that include the true class compared to their deterministic counterparts; the price to be paid for this increase is usually a tiny proportion of predictions with more than one class. The paper includes an extensive experimental study using three deterministic learners to estimate posterior probabilities: a multiclass Support Vector Machine (SVM), a Logistic Regression, and a Na\"{\i}ve Bayes. The data sets considered comprise both UCI multi-class learning tasks and microarray expressions of different kinds of cancer. We successfully compare nondeterministic classifiers with other alternative approaches. Additionally, we shall see how the quality of posterior probabilities (measured by the Brier score) determines the goodness of nondeterministic predictions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2273–2293},
numpages = {21}
}

@article{10.5555/1577069.1755861,
author = {Rudin, Cynthia},
title = {The P-Norm Push: A Simple Convex Ranking Algorithm That Concentrates at the Top of the List},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We are interested in supervised ranking algorithms that perform especially well near the top of the ranked list, and are only required to perform sufficiently well on the rest of the list. In this work, we provide a general form of convex objective that gives high-scoring examples more importance. This "push" near the top of the list can be chosen arbitrarily large or small, based on the preference of the user. We choose lp-norms to provide a specific type of push; if the user sets p larger, the objective concentrates harder on the top of the list. We derive a generalization bound based on the p-norm objective, working around the natural asymmetry of the problem. We then derive a boosting-style algorithm for the problem of ranking with a push at the top. The usefulness of the algorithm is illustrated through experiments on repository data. We prove that the minimizer of the algorithm's objective is unique in a specific sense. Furthermore, we illustrate how our objective is related to quality measurements for information retrieval.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2233–2271},
numpages = {39}
}

@article{10.5555/1577069.1755860,
author = {Rudin, Cynthia and Schapire, Robert E.},
title = {Margin-Based Ranking and an Equivalence between AdaBoost and RankBoost},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We study boosting algorithms for learning to rank. We give a general margin-based bound for ranking based on covering numbers for the hypothesis space. Our bound suggests that algorithms that maximize the ranking margin will generalize well. We then describe a new algorithm, smooth margin ranking, that precisely converges to a maximum ranking-margin solution. The algorithm is a modification of RankBoost, analogous to "approximate coordinate ascent boosting." Finally, we prove that AdaBoost and RankBoost are equally good for the problems of bipartite ranking and classification in terms of their asymptotic behavior on the training set. Under natural conditions, AdaBoost achieves an area under the ROC curve that is equally as good as RankBoost's; furthermore, RankBoost, when given a specific intercept, achieves a misclassification error that is as good as AdaBoost's. This may help to explain the empirical observations made by Cortes and Mohri, and Caruana and Niculescu-Mizil, about the excellent performance of AdaBoost as a bipartite ranking algorithm, as measured by the area under the ROC curve.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2193–2232},
numpages = {40}
}

@article{10.5555/1577069.1755859,
author = {Franc, Vojt\v{e}ch and Sonnenburg, S\"{o}ren},
title = {Optimized Cutting Plane Algorithm for Large-Scale Risk Minimization},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We have developed an optimized cutting plane algorithm (OCA) for solving large-scale risk minimization problems. We prove that the number of iterations OCA requires to converge to a ε precise solution is approximately linear in the sample size. We also derive OCAS, an OCA-based linear binary Support Vector Machine (SVM) solver, and OCAM, a linear multi-class SVM solver. In an extensive empirical evaluation we show that OCAS outperforms current state-of-the-art SVM solvers like SVMlight, SVMperf and BMRM, achieving speedup factor more than 1,200 over SVMlight on some data sets and speedup factor of 29 over SVMperf, while obtaining the same precise support vector solution. OCAS, even in the early optimization steps, often shows faster convergence than the currently prevailing approximative methods in this domain, SGD and Pegasos. In addition, our proposed linear multi-class SVM solver, OCAM, achieves speedups of factor of up to 10 compared to SVMmulti-class. Finally, we use OCAS and OCAM in two real-world applications, the problem of human acceptor splice site detection and malware detection. Effectively parallelizing OCAS, we achieve state-of-the-art results on an acceptor splice site recognition problem only by being able to learn from all the available 50 million examples in a 12-million-dimensional feature space. Source code, data sets and scripts to reproduce the experiments are available at <tt><a href="http://cmp.felk.cvut.cz/~xfrancv/ocas/html/">http://cmp.felk.cvut.cz/~xfrancv/ocas/html/</a></tt>.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2157–2192},
numpages = {36}
}

@article{10.5555/1577069.1755858,
author = {Bickel, Steffen and Br\"{u}ckner, Michael and Scheffer, Tobias},
title = {Discriminative Learning Under Covariate Shift},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We address classification problems for which the training instances are governed by an input distribution that is allowed to differ arbitrarily from the test distribution---problems also referred to as classification under covariate shift. We derive a solution that is purely discriminative: neither training nor test distribution are modeled explicitly. The problem of learning under covariate shift can be written as an integrated optimization problem. Instantiating the general optimization problem leads to a kernel logistic regression and an exponential model classifier for covariate shift. The optimization problem is convex under certain conditions; our findings also clarify the relationship to the known kernel mean matching procedure. We report on experiments on problems of spam filtering, text classification, and landmine detection.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2137–2155},
numpages = {19}
}

@article{10.5555/1577069.1755857,
author = {Tanner, Brian and White, Adam},
title = {RL-Glue: Language-Independent Software for Reinforcement-Learning Experiments},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {RL-Glue is a standard, language-independent software package for reinforcement-learning experiments. The standardization provided by RL-Glue facilitates code sharing and collaboration. Code sharing reduces the need to re-engineer tasks and experimental apparatus, both common barriers to comparatively evaluating new ideas in the context of the literature. Our software features a minimalist interface and works with several languages and computing platforms. RL-Glue compatibility can be extended to any programming language that supports network socket communication. RL-Glue has been used to teach classes, to run international competitions, and is currently used by several other open-source software and hardware projects.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2133–2136},
numpages = {4}
}

@article{10.5555/1577069.1755856,
author = {Rieger, Christian and Zwicknagl, Barbara},
title = {Deterministic Error Analysis of Support Vector Regression and Related Regularized Kernel Methods},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We introduce a new technique for the analysis of kernel-based regression problems. The basic tools are sampling inequalities which apply to all machine learning problems involving penalty terms induced by kernels related to Sobolev spaces. They lead to explicit deterministic results concerning the worst case behaviour of ε- and ν-SVRs. Using these, we show how to adjust regularization parameters to get best possible approximation orders for regression. The results are illustrated by some numerical examples.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2115–2132},
numpages = {18}
}

@article{10.5555/1577069.1755855,
author = {Ferrer, Luciana and S\"{o}nmez, Kemal and Shriberg, Elizabeth},
title = {An Anticorrelation Kernel for Subsystem Training in Multiple Classifier Systems},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We present a method for training support vector machine (SVM)-based classification systems for combination with other classification systems designed for the same task. Ideally, a new system should be designed such that, when combined with existing systems, the resulting performance is optimized. We present a simple model for this problem and use the understanding gained from this analysis to propose a method to achieve better combination performance when training SVM systems. We include a regularization term in the SVM objective function that aims to reduce the average class-conditional covariance between the resulting scores and the scores produced by the existing systems, introducing a trade-off between such covariance and the system's individual performance. That is, the new system "takes one for the team", falling somewhat short of its best possible performance in order to increase the diversity of the ensemble. We report results on the NIST 2005 and 2006 speaker recognition evaluations (SREs) for a variety of subsystems. We show a gain of 19% on the equal error rate (EER) of a combination of four systems when applying the proposed method with respect to the performance obtained when the four systems are trained independently of each other.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2079–2114},
numpages = {36}
}

@article{10.5555/1577069.1755854,
author = {Gorissen, Dirk and Dhaene, Tom and Turck, Filip De},
title = {Evolutionary Model Type Selection for Global Surrogate Modeling},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Due to the scale and computational complexity of currently used simulation codes, global surrogate (metamodels) models have become indispensable tools for exploring and understanding the design space. Due to their compact formulation they are cheap to evaluate and thus readily facilitate visualization, design space exploration, rapid prototyping, and sensitivity analysis. They can also be used as accurate building blocks in design packages or larger simulation environments. Consequently, there is great interest in techniques that facilitate the construction of such approximation models while minimizing the computational cost and maximizing model accuracy. Many surrogate model types exist (Support Vector Machines, Kriging, Neural Networks, etc.) but no type is optimal in all circumstances. Nor is there any hard theory available that can help make this choice. In this paper we present an automatic approach to the model type selection problem. We describe an adaptive global surrogate modeling environment with adaptive sampling, driven by speciated evolution. Different model types are evolved cooperatively using a Genetic Algorithm (heterogeneous evolution) and compete to approximate the iteratively selected data. In this way the optimal model type and complexity for a given data set or simulation code can be dynamically determined. Its utility and performance is demonstrated on a number of problems where it outperforms traditional sequential execution of each model type.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2039–2078},
numpages = {40}
}

@article{10.5555/1577069.1755853,
author = {Fan, Jianqing and Samworth, Richard and Wu, Yichao},
title = {Ultrahigh Dimensional Feature Selection: Beyond The Linear Model},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Variable selection in high-dimensional space characterizes many contemporary problems in scientific discovery and decision making. Many frequently-used techniques are based on independence screening; examples include correlation ranking (Fan & Lv, 2008) or feature selection using a two-sample t-test in high-dimensional classification (Tibshirani et al., 2003). Within the context of the linear model, Fan & Lv (2008) showed that this simple correlation ranking possesses a sure independence screening property under certain conditions and that its revision, called iteratively sure independent screening (ISIS), is needed when the features are marginally unrelated but jointly related to the response variable. In this paper, we extend ISIS, without explicit definition of residuals, to a general pseudo-likelihood framework, which includes generalized linear models as a special case. Even in the least-squares setting, the new method improves ISIS by allowing feature deletion in the iterative process. Our technique allows us to select important features in high-dimensional classification where the popularly used two-sample t-method fails. A new technique is introduced to reduce the false selection rate in the feature screening stage. Several simulated and two real data examples are presented to illustrate the methodology.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2013–2038},
numpages = {26}
}

@article{10.5555/1577069.1755852,
author = {Chen, Jie and Fang, Haw-ren and Saad, Yousef},
title = {Fast Approximate <i>k</i>NN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Nearest neighbor graphs are widely used in data mining and machine learning. A brute-force method to compute the exact kNN graph takes Θ(dn2) time for n data points in the d dimensional Euclidean space. We propose two divide and conquer methods for computing an approximate kNN graph in Θ(dnt) time for high dimensional data (large d). The exponent t ∈ (1,2) is an increasing function of an internal parameter α which governs the size of the common region in the divide step. Experiments show that a high quality graph can usually be obtained with small overlaps, that is, for small values of t. A few of the practical details of the algorithms are as follows. First, the divide step uses an inexpensive Lanczos procedure to perform recursive spectral bisection. After each conquer step, an additional refinement step is performed to improve the accuracy of the graph. Finally, a hash table is used to avoid repeating distance calculations during the divide and conquer process. The combination of these techniques is shown to yield quite effective algorithms for building kNN graphs.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1989–2012},
numpages = {24}
}

@article{10.5555/1577069.1755851,
author = {Brunskill, Emma and Leffler, Bethany R. and Li, Lihong and Littman, Michael L. and Roy, Nicholas},
title = {Provably Efficient Learning with Typed Parametric Models},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {To quickly achieve good performance, reinforcement-learning algorithms for acting in large continuous-valued domains must use a representation that is both sufficiently powerful to capture important domain characteristics, and yet simultaneously allows generalization, or sharing, among experiences. Our algorithm balances this tradeoff by using a stochastic, switching, parametric dynamics representation. We argue that this model characterizes a number of significant, real-world domains, such as robot navigati on across varying terrain. We prove that this representational assumption allows our algorithm to be probably approximately correct with a sample complexity that scales polynomially with all problem-specific quantities including the state-space dimension. We also explicitly incorporate the error introduced by approximate planning in our sample complexity bounds, in contrast to prior Probably Approximately Correct (PAC) Markov Decision Processes (MDP) approaches, which typically assume the estimated MDP can be solved exactly. Our experimental results on constructing plans for driving to work using real car trajectory data, as well as a small robot experiment on navigating varying terrain, demonstrate that our dynamics representation enables us to capture real-world dynamics in a sufficient manner to produce good performance.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1955–1988},
numpages = {34}
}

@article{10.5555/1577069.1755850,
author = {Woodsend, Kristian and Gondzio, Jacek},
title = {Hybrid MPI/OpenMP Parallel Linear Support Vector Machine Training},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Support vector machines are a powerful machine learning technology, but the training process involves a dense quadratic optimization problem and is computationally challenging. A parallel implementation of linear Support Vector Machine training has been developed, using a combination of MPI and OpenMP. Using an interior point method for the optimization and a reformulation that avoids the dense Hessian matrix, the structure of the augmented system matrix is exploited to partition data and computations amongst parallel processors efficiently. The new implementation has been applied to solve problems from the PASCAL Challenge on Large-scale Learning. We show that our approach is competitive, and is able to solve problems in the Challenge many times faster than other parallel approaches. We also demonstrate that the hybrid version performs more efficiently than the version using pure MPI.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1937–1953},
numpages = {17}
}

@article{10.5555/1577069.1755849,
author = {Syed, Zeeshan and Indyk, Piotr and Guttag, John},
title = {Learning Approximate Sequential Patterns for Classification},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In this paper, we present an automated approach to discover patterns that can distinguish between sequences belonging to different labeled groups. Our method searches for approximately conserved motifs that occur with varying statistical properties in positive and negative training examples. We propose a two-step process to discover such patterns. Using locality sensitive hashing (LSH), we first estimate the frequency of all subsequences and their approximate matches within a given Hamming radius in labeled examples. The discriminative ability of each pattern is then assessed from the estimated frequencies by concordance and rank sum testing. The use of LSH to identify approximate matches for each candidate pattern helps reduce the runtime of our method. Space requirements are reduced by decomposing the search problem into an iterative method that uses a single LSH table in memory. We propose two further optimizations to the search for discriminative patterns. Clustering with redundancy based on a 2-approximate solution of the k-center problem decreases the number of overlapping approximate groups while providing exhaustive coverage of the search space. Sequential statistical methods allow the search process to use data from only as many training examples as are needed to assess significance. We evaluated our algorithm on data sets from different applications to discover sequential patterns for classification. On nucleotide sequences from the Drosophila genome compared with random background sequences, our method was able to discover approximate binding sites that were preserved upstream of genes. We observed a similar result in experiments on ChIP-on-chip data. For cardiovascular data from patients admitted with acute coronary syndromes, our pattern discovery approach identified approximately conserved sequences of morphology variations that were predictive of future death in a test population. Our data showed that the use of LSH, clustering, and sequential statistics improved the running time of the search algorithm by an order of magnitude without any noticeable effect on accuracy. These results suggest that our methods may allow for an unsupervised approach to efficiently learn interesting dissimilarities between positive and negative examples that may have a functional role.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1913–1936},
numpages = {24}
}

@article{10.5555/1577069.1755848,
author = {Angluin, Dana and Aspnes, James and Chen, Jiang and Eisenstat, David and Reyzin, Lev},
title = {Learning Acyclic Probabilistic Circuits Using Test Paths},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We define a model of learning probabilistic acyclic circuits using value injection queries, in which fixed values are assigned to an arbitrary subset of the wires and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm (Angluin et al., 2009) to show that there is a polynomial time algorithm that uses value injection queries to learn acyclic Boolean probabilistic circuits of constant fan-in and log depth. We establish upper and lower bounds on the attenuation factor for general and transitively reduced Boolean probabilistic circuits of test paths versus general experiments. We give computational evidence that a polynomial time learning algorithm using general value injection experiments may not do much better than one using test paths. For probabilistic circuits with alphabets of size three or greater, we show that the test path lemmas (Angluin et al., 2009, 2008b) fail utterly. To overcome this obstacle, we introduce function injection queries, in which the values on a wire may be mapped to other values rather than just to themselves or constants, and prove a generalized test path lemma for this case.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1881–1911},
numpages = {31}
}

@article{10.5555/1577069.1755847,
author = {Esposito, Roberto and Radicioni, Daniele P.},
title = {CarpeDiem: Optimizing the Viterbi Algorithm and Applications to Supervised Sequential Learning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The growth of information available to learning systems and the increasing complexity of learning tasks determine the need for devising algorithms that scale well with respect to all learning parameters. In the context of supervised sequential learning, the Viterbi algorithm plays a fundamental role, by allowing the evaluation of the best (most probable) sequence of labels with a time complexity linear in the number of time events, and quadratic in the number of labels.In this paper we propose CarpeDiem, a novel algorithm allowing the evaluation of the best possible sequence of labels with a sub-quadratic time complexity. We provide theoretical grounding together with solid empirical results supporting two chief facts. CarpeDiem always finds the optimal solution requiring, in most cases, only a small fraction of the time taken by the Viterbi algorithm; meantime, CarpeDiem is never asymptotically worse than the Viterbi algorithm, thus confirming it as a sound replacement.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1851–1880},
numpages = {30}
}

@article{10.5555/1577069.1755846,
author = {Shahbaba, Babak and Neal, Radford},
title = {Nonlinear Models Using Dirichlet Process Mixtures},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We introduce a new nonlinear model for classification, in which we model the joint distribution of response variable, y, and covariates, x, non-parametrically using Dirichlet process mixtures. We keep the relationship between y and x linear within each component of the mixture. The overall relationship becomes nonlinear if the mixture contains more than one component, with different regression coefficients. We use simulated data to compare the performance of this new approach to alternative methods such as multinomial logit (MNL) models, decision trees, and support vector machines. We also evaluate our approach on two classification problems: identifying the folding class of protein sequences and detecting Parkinson's disease. Our model can sometimes improve predictive accuracy. Moreover, by grouping observations into sub-populations (i.e., mixture components), our model can sometimes provide insight into hidden structure in the data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1829–1850},
numpages = {22}
}

@article{10.5555/1577069.1755845,
author = {Newman, David and Asuncion, Arthur and Smyth, Padhraic and Welling, Max},
title = {Distributed Algorithms for Topic Models},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We describe distributed algorithms for two widely-used topic models, namely the Latent Dirichlet Allocation (LDA) model, and the Hierarchical Dirichet Process (HDP) model. In our distributed algorithms the data is partitioned across separate processors and inference is done in a parallel, distributed fashion. We propose two distributed algorithms for LDA. The first algorithm is a straightforward mapping of LDA to a distributed processor setting. In this algorithm processors concurrently perform Gibbs sampling over local data followed by a global update of topic counts. The algorithm is simple to implement and can be viewed as an approximation to Gibbs-sampled LDA. The second version is a model that uses a hierarchical Bayesian extension of LDA to directly account for distributed data. This model has a theoretical guarantee of convergence but is more complex to implement than the first algorithm. Our distributed algorithm for HDP takes the straightforward mapping approach, and merges newly-created topics either by matching or by topic-id. Using five real-world text corpora we show that distributed learning works well in practice. For both LDA and HDP, we show that the converged test-data log probability for distributed learning is indistinguishable from that obtained with single-processor learning. Our extensive experimental results include learning topic models for two multi-million document collections using a 1024-processor parallel computer.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1801–1828},
numpages = {28}
}

@article{10.5555/1577069.1755844,
author = {White, Halbert and Chalak, Karim},
title = {Settable Systems: An Extension of Pearl's Causal Model with Optimization, Equilibrium, and Learning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Judea Pearl's Causal Model is a rich framework that provides deep insight into the nature of causal relations. As yet, however, the Pearl Causal Model (PCM) has had a lesser impact on economics or econometrics than on other disciplines. This may be due in part to the fact that the PCM is not as well suited to analyzing structures that exhibit features of central interest to economists and econometricians: optimization, equilibrium, and learning. We offer the settable systems framework as an extension of the PCM that permits causal discourse in systems embodying optimization, equilibrium, and learning. Because these are common features of physical, natural, or social systems, our framework may prove generally useful for machine learning. Important features distinguishing the settable system framework from the PCM are its countable dimensionality and the use of partitioning and partition-specific response functions to accommodate the behavior of optimizing and interacting agents and to eliminate the requirement of a unique fixed point for the system. Refinements of the PCM include the settable systems treatment of attributes, the causal role of exogenous variables, and the dual role of variables as causes and responses. A series of closely related machine learning examples and examples from game theory and machine learning with feedback demonstrates some limitations of the PCM and motivates the distinguishing features of settable systems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1759–1799},
numpages = {41}
}

@article{10.5555/1577069.1755843,
author = {King, Davis E.},
title = {Dlib-Ml: A Machine Learning Toolkit},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {There are many excellent toolkits which provide support for developing machine learning software in Python, R, Matlab, and similar environments. Dlib-ml is an open source library, targeted at both engineers and research scientists, which aims to provide a similarly rich environment for developing machine learning software in the C++ language. Towards this end, dlib-ml contains an extensible linear algebra toolkit with built in BLAS support. It also houses implementations of algorithms for performing inference in Bayesian networks and kernel-based methods for classification, regression, clustering, anomaly detection, and feature ranking. To enable easy use of these tools, the entire library has been developed with contract programming, which provides complete and precise documentation as well as powerful debugging tools.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1755–1758},
numpages = {4}
}

@article{10.5555/1577069.1755842,
author = {Bordes, Antoine and Bottou, L\'{e}on and Gallinari, Patrick},
title = {SGD-QN: Careful Quasi-Newton Stochastic Gradient Descent},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The SGD-QN algorithm is a stochastic gradient descent algorithm that makes careful use of second-order information and splits the parameter update into independently scheduled components. Thanks to this design, SGD-QN iterates nearly as fast as a first-order stochastic gradient descent but requires less iterations to achieve the same accuracy. This algorithm won the "Wild Track" of the first PASCAL Large Scale Learning Challenge (Sonnenburg et al., 2008).},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1737–1754},
numpages = {18}
}

@article{10.5555/1577069.1755841,
author = {Helmbold, David P. and Warmuth, Manfred K.},
title = {Learning Permutations with Exponential Weights},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We give an algorithm for the on-line learning of permutations. The algorithm maintains its uncertainty about the target permutation as a doubly stochastic weight matrix, and makes predictions using an efficient method for decomposing the weight matrix into a convex combination of permutations. The weight matrix is updated by multiplying the current matrix entries by exponential factors, and an iterative procedure is needed to restore double stochasticity. Even though the result of this procedure does not have a closed form, a new analysis approach allows us to prove an optimal (up to small constant factors) bound on the regret of our algorithm. This regret bound is significantly better than that of either Kalai and Vempala's more efficient Follow the Perturbed Leader algorithm or the computationally expensive method of explicitly representing each permutation as an expert.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1705–1736},
numpages = {32}
}

@article{10.5555/1577069.17558

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr