text:
{Learning Parts-Based Representations of Data},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Many perceptual models and theories hinge on treating objects as a collection of constituent parts. When applying these approaches to data, a fundamental problem arises: how can we determine what are the parts? We attack this problem using learning, proposing a form of generative latent factor model, in which each data dimension is allowed to select a different factor or part as its explanation. This approach permits a range of variations that posit different models for the appearance of a part. Here we provide the details for two such models: a discrete and a continuous one. Further, we show that this latent factor model can be extended hierarchically to account for correlations between the appearances of different parts. This permits modelling of data consisting of multiple categories, and learning these categories simultaneously with the parts when they are unobserved. Experiments demonstrate the ability to learn parts-based representations, and categories, of facial images and user-preference data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2369–2397},
numpages = {29}
}

@article{10.5555/1248547.1248630,
author = {Porta, Josep M. and Vlassis, Nikos and Spaan, Matthijs T.J. and Poupart, Pascal},
title = {Point-Based Value Iteration for Continuous POMDPs},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We propose a novel approach to optimize Partially Observable Markov Decisions Processes (POMDPs) defined on continuous spaces. To date, most algorithms for model-based POMDPs are restricted to discrete states, actions, and observations, but many real-world problems such as, for instance, robot navigation, are naturally defined on continuous spaces. In this work, we demonstrate that the value function for continuous POMDPs is convex in the beliefs over continuous state spaces, and piecewise-linear convex for the particular case of discrete observations and actions but still continuous states. We also demonstrate that continuous Bellman backups are contracting and isotonic ensuring the monotonic convergence of value-iteration algorithms. Relying on those properties, we extend the algorithm, originally developed for discrete POMDPs, to work in continuous state spaces by representing the observation, transition, and reward models using Gaussian mixtures, and the beliefs using Gaussian mixtures or particle sets. With these representations, the integrals that appear in the Bellman backup can be computed in closed form and, therefore, the algorithm is computationally feasible. Finally, we further extend to deal with continuous action and observation sets by designing effective sampling approaches.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2329–2367},
numpages = {39}
}

@article{10.5555/1248547.1248629,
author = {Braun, Mikio L.},
title = {Accurate Error Bounds for the Eigenvalues of the Kernel Matrix},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The eigenvalues of the kernel matrix play an important role in a number of kernel methods, in particular, in kernel principal component analysis. It is well known that the eigenvalues of the kernel matrix converge as the number of samples tends to infinity. We derive probabilistic finite sample size bounds on the approximation error of individual eigenvalues which have the important property that the bounds scale with the eigenvalue under consideration, reflecting the actual behavior of the approximation errors as predicted by asymptotic results and observed in numerical simulations. Such scaling bounds have so far only been known for tail sums of eigenvalues. Asymptotically, the bounds presented here have a slower than stochastic rate, but the number of sample points necessary to make this disadvantage noticeable is often unrealistically large. Therefore, under practical conditions, and for all but the largest few eigenvalues, the bounds presented here form a significant improvement over existing non-scaling bounds.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2303–2328},
numpages = {26}
}

@article{10.5555/1248547.1248628,
author = {Jonsson, Anders and Barto, Andrew},
title = {Causal Graph Based Decomposition of Factored MDPs},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We present Variable Influence Structure Analysis, or VISA, an algorithm that performs hierarchical decomposition of factored Markov decision processes. VISA uses a dynamic Bayesian network model of actions, and constructs a causal graph that captures relationships between state variables. In tasks with sparse causal graphs VISA exploits structure by introducing activities that cause the values of state variables to change. The result is a hierarchy of activities that together represent a solution to the original task. VISA performs state abstraction for each activity by ignoring irrelevant state variables and lower-level activities. In addition, we describe an algorithm for constructing compact models of the activities introduced. State abstraction and compact activity models enable VISA to apply efficient algorithms to solve the stand-alone subtask associated with each activity. Experimental results show that the decomposition introduced by VISA can significantly accelerate construction of an optimal, or near-optimal, policy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2259–2301},
numpages = {43}
}

@article{10.5555/1248547.1248627,
author = {Scheinberg, Katya},
title = {An Efficient Implementation of an Active Set Method for SVMs},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We propose an active set algorithm to solve the convex quadratic programming (QP) problem which is the core of the support vector machine (SVM) training. The underlying method is not new and is based on the extensive practice of the Simplex method and its variants for convex quadratic problems. However, its application to large-scale SVM problems is new. Until recently the traditional active set methods were considered impractical for large SVM problems. By adapting the methods to the special structure of SVM problems we were able to produce an efficient implementation. We conduct an extensive study of the behavior of our method and its variations on SVM problems. We present computational results comparing our method with Joachims' SVMlight (see Joachims, 1999). The results show that our method has overall better performance on many SVM problems. It seems to have a particularly strong advantage on more difficult problems. In addition this algorithm has better theoretical properties and it naturally extends to the incremental mode. Since the proposed method solves the standard SVM formulation, as does SVMlight, the generalization properties of these two approaches are identical and we do not discuss them in the paper.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2237–2257},
numpages = {21}
}

@article{10.5555/1248547.1248626,
author = {Angluin, Dana and Chen, Jiang},
title = {Learning a Hidden Hypergraph},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We consider the problem of learning a hypergraph using edge-detecting queries. In this model, the learner may query whether a set of vertices induces an edge of the hidden hypergraph or not. We show that an r-uniform hypergraph with m edges and n vertices is learnable with O(24rm · poly(r,logn)) queries with high probability. The queries can be made in O(min(2r (log m+r)2, (log m+r)3)) rounds. We also give an algorithm that learns an almost uniform hypergraph of dimension r using O(2O((1+Δ/2)r) · m1+Δ/2 · poly(log n)) queries with high probability, where Δ is the difference between the maximum and the minimum edge sizes. This upper bound matches our lower bound of Ω((m/(1+Δ/2))1+Δ/2) for this class of hypergraphs in terms of dependence on m. The queries can also be made in O((1+Δ) · min(2r (log m+r)2, (log m+r)3)) rounds.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2215–2236},
numpages = {22}
}

@article{10.5555/1248547.1248625,
author = {\v{S}ingliar, Tom\'{a}\v{s} and Hauskrecht, Milo\v{s}},
title = {Noisy-OR Component Analysis and Its Application to Link Analysis},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We develop a new component analysis framework, the Noisy-Or Component Analyzer (NOCA), that targets high-dimensional binary data. NOCA is a probabilistic latent variable model that assumes the expression of observed high-dimensional binary data is driven by a small number of hidden binary sources combined via noisy-or units. The component analysis procedure is equivalent to learning of NOCA parameters. Since the classical EM formulation of the NOCA learning problem is intractable, we develop its variational approximation. We test the NOCA framework on two problems: (1) a synthetic image-decomposition problem and (2) a co-citation data analysis problem for thousands of CiteSeer documents. We demonstrate good performance of the new model on both problems. In addition, we contrast the model to two mixture-based latent-factor models: the probabilistic latent semantic analysis (PLSA) and latent Dirichlet allocation (LDA). Differing assumptions underlying these models cause them to discover different types of structure in co-citation data, thus illustrating the benefit of NOCA in building our understanding of high-dimensional data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2189–2213},
numpages = {25}
}

@article{10.5555/1248547.1248624,
author = {de Campos, Luis M.},
title = {A Scoring Function for Learning Bayesian Networks Based on Mutual Information and Conditional Independence Tests},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We propose a new scoring function for learning Bayesian networks from data using score+search algorithms. This is based on the concept of mutual information and exploits some well-known properties of this measure in a novel way. Essentially, a statistical independence test based on the chi-square distribution, associated with the mutual information measure, together with a property of additive decomposition of this measure, are combined in order to measure the degree of interaction between each variable and its parent variables in the network. The result is a non-Bayesian scoring function called MIT (mutual information tests) which belongs to the family of scores based on information theory. The MIT score also represents a penalization of the Kullback-Leibler divergence between the joint probability distributions associated with a candidate network and with the available data set. Detailed results of a complete experimental evaluation of the proposed scoring function and its comparison with the well-known K2, BDeu and BIC/MDL scores are also presented.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2149–2187},
numpages = {39}
}

@article{10.5555/1248547.1248623,
author = {Chang, Fu and Lin, Chin-Chin and Lu, Chi-Jen},
title = {Adaptive Prototype Learning Algorithms: Theoretical and Experimental Studies},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In this paper, we propose a number of adaptive prototype learning (APL) algorithms. They employ the same algorithmic scheme to determine the number and location of prototypes, but differ in the use of samples or the weighted averages of samples as prototypes, and also in the assumption of distance measures. To understand these algorithms from a theoretical viewpoint, we address their convergence properties, as well as their consistency under certain conditions. We also present a soft version of APL, in which a non-zero training error is allowed in order to enhance the generalization power of the resultant classifier. Applying the proposed algorithms to twelve UCI benchmark data sets, we demonstrate that they outperform many instance-based learning algorithms, the k-nearest neighbor rule, and support vector machines in terms of average test accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2125–2148},
numpages = {24}
}

@article{10.5555/1248547.1248622,
author = {Sahbi, Hichem and Geman, Donald},
title = {A Hierarchy of Support Vector Machines for Pattern Detection},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We introduce a computational design for pattern detection based on a tree-structured network of support vector machines (SVMs). An SVM is associated with each cell in a recursive partitioning of the space of patterns (hypotheses) into increasingly finer subsets. The hierarchy is traversed coarse-to-fine and each chain of positive responses from the root to a leaf constitutes a detection. Our objective is to design and build a network which balances overall error and computation.Initially, SVMs are constructed for each cell with no constraints. This "free network" is then perturbed, cell by cell, into another network, which is "graded" in two ways: first, the number of support vectors of each SVM is reduced (by clustering) in order to adjust to a pre-determined, increasing function of cell depth; second, the decision boundaries are shifted to preserve all positive responses from the original set of training data. The limits on the numbers of clusters (virtual support vectors) result from minimizing the mean computational cost of collecting all detections subject to a bound on the expected number of false positives.When applied to detecting faces in cluttered scenes, the patterns correspond to poses and the free network is already faster and more accurate than applying a single pose-specific SVM many times. The graded network promotes very rapid processing of background regions while maintaining the discriminatory power of the free network.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2087–2123},
numpages = {37}
}

@article{10.5555/1248547.1248621,
author = {K\"{a}mpke, Thomas},
title = {Distance Patterns in Structural Similarity},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Similarity of edge labeled graphs is considered in the sense of minimum squared distance between corresponding values. Vertex correspondences are established by isomorphisms if both graphs are of equal size and by subisomorphisms if one graph has fewer vertices than the other. Best fit isomorphisms and subisomorphisms amount to solutions of quadratic assignment problems and are computed exactly as well as approximately by minimum cost flow, linear assignment relaxations and related graph algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2065–2086},
numpages = {22}
}

@article{10.5555/1248547.1248620,
author = {Malioutov, Dmitry M. and Johnson, Jason K. and Willsky, Alan S.},
title = {Walk-Sums and Belief Propagation in Gaussian Graphical Models},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We present a new framework based on walks in a graph for analysis and inference in Gaussian graphical models. The key idea is to decompose the correlation between each pair of variables as a sum over all walks between those variables in the graph. The weight of each walk is given by a product of edgewise partial correlation coefficients. This representation holds for a large class of Gaussian graphical models which we call walk-summable. We give a precise characterization of this class of models, and relate it to other classes including diagonally dominant, attractive, non-frustrated, and pairwise-normalizable. We provide a walk-sum interpretation of Gaussian belief propagation in trees and of the approximate method of loopy belief propagation in graphs with cycles. The walk-sum perspective leads to a better understanding of Gaussian belief propagation and to stronger results for its convergence in loopy graphs.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2031–2064},
numpages = {34}
}

@article{10.5555/1248547.1248619,
author = {Shimizu, Shohei and Hoyer, Patrik O. and Hyv\"{a}rinen, Aapo and Kerminen, Antti},
title = {A Linear Non-Gaussian Acyclic Model for Causal Discovery},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In recent years, several methods have been proposed for the discovery of causal structure from non-experimental data. Such methods make various assumptions on the data generating process to facilitate its identification from purely observational data. Continuing this line of research, we show how to discover the complete causal structure of continuous-valued data, under the assumptions that (a) the data generating process is linear, (b) there are no unobserved confounders, and (c) disturbance variables have non-Gaussian distributions of non-zero variances. The solution relies on the use of the statistical method known as independent component analysis, and does not require any pre-specified time-ordering of the variables. We provide a complete Matlab package for performing this LiNGAM analysis (short for Linear Non-Gaussian Acyclic Model), and demonstrate the effectiveness of the method using artificially generated data and real-world data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2003–2030},
numpages = {28}
}

@article{10.5555/1248547.1248618,
author = {Bach, Francis R. and Jordan, Michael I.},
title = {Learning Spectral Clustering, With Application To Speech Separation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters, with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive new cost functions for spectral clustering based on measures of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing these cost functions with respect to the partition leads to new spectral clustering algorithms. Minimizing with respect to the similarity matrix leads to algorithms for learning the similarity matrix from fully labelled data sets. We apply our learning algorithm to the blind one-microphone speech separation problem, casting the problem as one of segmentation of the spectrogram.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1963–2001},
numpages = {39}
}

@article{10.5555/1248547.1248617,
author = {Bhatnagar, Shalabh and Borkar, Vivek S. and Akarapu, Madhukar},
title = {A Simulation-Based Algorithm for Ergodic Control of Markov Chains Conditioned on Rare Events},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We study the problem of long-run average cost control of Markov chains conditioned on a rare event. In a related recent work, a simulation based algorithm for estimating performance measures associated with a Markov chain conditioned on a rare event has been developed. We extend ideas from this work and develop an adaptive algorithm for obtaining, online, optimal control policies conditioned on a rare event. Our algorithm uses three timescales or step-size schedules. On the slowest timescale, a gradient search algorithm for policy updates that is based on one-simulation simultaneous perturbation stochastic approximation (SPSA) type estimates is used. Deterministic perturbation sequences obtained from appropriate normalized Hadamard matrices are used here. The fast timescale recursions compute the conditional transition probabilities of an associated chain by obtaining solutions to the multiplicative Poisson equation (for a given policy estimate). Further, the risk parameter associated with the value function for a given policy estimate is updated on a timescale that lies in between the two scales above. We briefly sketch the convergence analysis of our algorithm and present a numerical application in the setting of routing multiple flows in communication networks.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1937–1962},
numpages = {26}
}

@article{10.5555/1248547.1248616,
author = {Laskov, Pavel and Gehl, Christian and Kr\"{u}ger, Stefan and M\"{u}ller, Klaus-Robert},
title = {Incremental Support Vector Learning: Analysis, Implementation and Applications},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Incremental Support Vector Machines (SVM) are instrumental in practical applications of online learning. This work focuses on the design and analysis of efficient incremental SVM learning, with the aim of providing a fast, numerically stable and robust implementation. A detailed analysis of convergence and of algorithmic complexity of incremental SVM learning is carried out. Based on this analysis, a new design of storage and numerical operations is proposed, which speeds up the training of an incremental SVM by a factor of 5 to 20. The performance of the new algorithm is demonstrated in two scenarios: learning with limited resources and active learning. Various applications of the algorithm, such as in drug discovery, online monitoring of industrial devices and and surveillance of network traffic, can be foreseen.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1909–1936},
numpages = {28}
}

@article{10.5555/1248547.1248615,
author = {Yanover, Chen and Meltzer, Talya and Weiss, Yair},
title = {Linear Programming Relaxations and Belief Propagation -- An Empirical Study},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The problem of finding the most probable (MAP) configuration in graphical models comes up in a wide range of applications. In a general graphical model this problem is NP hard, but various approximate algorithms have been developed. Linear programming (LP) relaxations are a standard method in computer science for approximating combinatorial problems and have been used for finding the most probable assignment in small graphical models. However, applying this powerful method to real-world problems is extremely challenging due to the large numbers of variables and constraints in the linear program. Tree-Reweighted Belief Propagation is a promising recent algorithm for solving LP relaxations, but little is known about its running time on large problems.In this paper we compare tree-reweighted belief propagation (TRBP) and powerful general-purpose LP solvers (CPLEX) on relaxations of real-world graphical models from the fields of computer vision and computational biology. We find that TRBP almost always finds the solution significantly faster than all the solvers in CPLEX and more importantly, TRBP can be applied to large scale problems for which the solvers in CPLEX cannot be applied. Using TRBP we can find the MAP configurations in a matter of minutes for a large range of real world problems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1887–1907},
numpages = {21}
}

@article{10.5555/1248547.1248614,
author = {Zhou, Jing and Foster, Dean P. and Stine, Robert A. and Ungar, Lyle H.},
title = {Streamwise Feature Selection},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In streamwise feature selection, new features are sequentially considered for addition to a predictive model. When the space of potential features is large, streamwise feature selection offers many advantages over traditional feature selection methods, which assume that all features are known in advance. Features can be generated dynamically, focusing the search for new features on promising subspaces, and overfitting can be controlled by dynamically adjusting the threshold for adding features to the model. In contrast to traditional forward feature selection algorithms such as stepwise regression in which at each step all possible features are evaluated and the best one is selected, streamwise feature selection only evaluates each feature once when it is generated. We describe information-investing and α-investing, two adaptive complexity penalty methods for streamwise feature selection which dynamically adjust the threshold on the error reduction required for adding a new feature. These two methods give false discovery rate style guarantees against overfitting. They differ from standard penalty methods such as AIC, BIC and RIC, which always drastically over- or under-fit in the limit of infinite numbers of non-predictive features. Empirical results show that streamwise regression is competitive with (on small data sets) and superior to (on large data sets) much more compute-intensive feature selection methods such as stepwise regression, and allows feature selection on problems with millions of potential features.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1861–1885},
numpages = {25}
}

@article{10.5555/1248547.1248613,
author = {Wainwright, Martin J.},
title = {Estimating the "Wrong" Graphical Model: Benefits in the Computation-Limited Setting},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Consider the problem of joint parameter estimation and prediction in a Markov random field: that is, the model parameters are estimated on the basis of an initial set of data, and then the fitted model is used to perform prediction (e.g., smoothing, denoising, interpolation) on a new noisy observation. Working under the restriction of limited computation, we analyze a joint method in which the same convex variational relaxation is used to construct an M-estimator for fitting parameters, and to perform approximate marginalization for the prediction step. The key result of this paper is that in the computation-limited setting, using an inconsistent parameter estimator (i.e., an estimator that returns the "wrong" model even in the infinite data limit) is provably beneficial, since the resulting errors can partially compensate for errors made by using an approximate prediction technique. En route to this result, we analyze the asymptotic properties of M-estimators based on convex variational relaxations, and establish a Lipschitz stability property that holds for a broad class of convex variational methods. This stability result provides additional incentive, apart from the obvious benefit of unique global optima, for using message-passing methods based on convex variational relaxations. We show that joint estimation/prediction based on the reweighted sum-product algorithm substantially outperforms a commonly used heuristic based on ordinary sum-product.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1829–1859},
numpages = {31}
}

@article{10.5555/1248547.1248612,
author = {Kok, Jelle R. and Vlassis, Nikos},
title = {Collaborative Multiagent Reinforcement Learning by Payoff Propagation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In this article we describe a set of scalable techniques for learning the behavior of a group of agents in a collaborative multiagent setting. As a basis we use the framework of coordination graphs of Guestrin, Koller, and Parr (2002a) which exploits the dependencies between agents to decompose the global payoff function into a sum of local terms. First, we deal with the single-state case and describe a payoff propagation algorithm that computes the individual actions that approximately maximize the global payoff function. The method can be viewed as the decision-making analogue of belief propagation in Bayesian networks. Second, we focus on learning the behavior of the agents in sequential decision-making tasks. We introduce different model-free reinforcement-learning techniques, unitedly called Sparse Cooperative Q-learning, which approximate the global action-value function based on the topology of a coordination graph, and perform updates using the contribution of the individual agents to the maximal global action value. The combined use of an edge-based decomposition of the action-value function and the payoff propagation algorithm for efficient action selection, result in an approach that scales only linearly in the problem size. We provide experimental evidence that our method outperforms related multiagent reinforcement-learning methods based on temporal differences.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1789–1828},
numpages = {40}
}

@article{10.5555/1248547.1248611,
author = {Abbeel, Pieter and Koller, Daphne and Ng, Andrew Y.},
title = {Learning Factor Graphs in Polynomial Time and Sample Complexity},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We study the computational and sample complexity of parameter and structure learning in graphical models. Our main result shows that the class of factor graphs with bounded degree can be learned in polynomial time and from a polynomial number of training examples, assuming that the data is generated by a network in this class. This result covers both parameter estimation for a known network structure and structure learning. It implies as a corollary that we can learn factor graphs for both Bayesian networks and Markov networks of bounded degree, in polynomial time and sample complexity. Importantly, unlike standard maximum likelihood estimation algorithms, our method does not require inference in the underlying network, and so applies to networks where inference is intractable. We also show that the error of our learned model degrades gracefully when the generating distribution is not a member of the target class of networks. In addition to our main result, we show that the sample complexity of parameter learning in graphical models has an O(1) dependence on the number of variables in the model when using the KL-divergence normalized by the number of variables as the performance criterion.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1743–1788},
numpages = {46}
}

@article{10.5555/1248547.1248610,
author = {Bach, Francis R. and Heckerman, David and Horvitz, Eric},
title = {Considering Cost Asymmetry in Learning Classifiers},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Receiver Operating Characteristic (ROC) curves are a standard way to display the performance of a set of binary classifiers for all feasible ratios of the costs associated with false positives and false negatives. For linear classifiers, the set of classifiers is typically obtained by training once, holding constant the estimated slope and then varying the intercept to obtain a parameterized set of classifiers whose performances can be plotted in the ROC plane. We consider the alternative of varying the asymmetry of the cost function used for training. We show that the ROC curve obtained by varying both the intercept and the asymmetry, and hence the slope, always outperforms the ROC curve obtained by varying only the intercept. In addition, we present a path-following algorithm for the support vector machine (SVM) that can compute efficiently the entire ROC curve, and that has the same computational complexity as training a single classifier. Finally, we provide a theoretical analysis of the relationship between the asymmetric cost model assumed when training a classifier and the cost model assumed in applying the classifier. In particular, we show that the mismatch between the step function used for testing and its convex upper bounds, usually used for training, leads to a provable and quantifiable difference around extreme asymmetries.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1713–1741},
numpages = {29}
}

@article{10.5555/1248547.1248609,
author = {Collobert, Ronan and Sinz, Fabian and Weston, Jason and Bottou, L\'{e}on},
title = {Large Scale Transductive SVMs},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We show how the concave-convex procedure can be applied to transductive SVMs, which traditionally require solving a combinatorial search problem. This provides for the first time a highly scalable algorithm in the nonlinear case. Detailed experiments verify the utility of our approach. Software is available at <tt>http://www.kyb.tuebingen.mpg.de/bs/people/fabee/transduction.html</tt>.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1687–1712},
numpages = {26}
}

@article{10.5555/1248547.1248608,
author = {Raghavan, Hema and Madani, Omid and Jones, Rosie},
title = {Active Learning with Feedback on Features and Instances},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We extend the traditional active learning framework to include feedback on features in addition to labeling instances, and we execute a careful study of the effects of feature selection and human feedback on features in the setting of text categorization. Our experiments on a variety of categorization tasks indicate that there is significant potential in improving classifier performance by feature re-weighting, beyond that achieved via membership queries alone (traditional active learning) if we have access to an oracle that can point to the important (most predictive) features. Our experiments on human subjects indicate that human feedback on feature relevance can identify a sufficient proportion of the most relevant features (over 50% in our experiments). We find that on average, labeling a feature takes much less time than labeling a document. We devise an algorithm that interleaves labeling features and documents which significantly accelerates standard active learning in our simulation experiments. Feature feedback can complement traditional active learning in applications such as news filtering, e-mail classification, and personalization, where the human teacher can have significant knowledge on the relevance of features.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1655–1686},
numpages = {32}
}

@article{10.5555/1248547.1248607,
author = {Taskar, Ben and Lacoste-Julien, Simon and Jordan, Michael I.},
title = {Structured Prediction, Dual Extragradient and Bregman Projections},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We present a simple and scalable algorithm for maximum-margin estimation of structured output models, including an important class of Markov networks and combinatorial models. We formulate the estimation problem as a convex-concave saddle-point problem that allows us to use simple projection methods based on the dual extragradient algorithm (Nesterov, 2003). The projection step can be solved using dynamic programming or combinatorial algorithms for min-cost convex flow, depending on the structure of the problem. We show that this approach provides a memory-efficient alternative to formulations based on reductions to a quadratic program (QP). We analyze the convergence of the method and present experiments on two very different structured prediction tasks: 3D image segmentation and word alignment, illustrating the favorable scaling properties of our algorithm.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1627–1653},
numpages = {27}
}

@article{10.5555/1248547.1248606,
author = {Rousu, Juho and Saunders, Craig and Szedmak, Sandor and Shawe-Taylor, John},
title = {Kernel-Based Learning of Hierarchical Multilabel Classification Models},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We present a kernel-based algorithm for hierarchical text classification where the documents are allowed to belong to more than one category at a time. The classification model is a variant of the Maximum Margin Markov Network framework, where the classification hierarchy is represented as a Markov tree equipped with an exponential family defined on the edges. We present an efficient optimization algorithm based on incremental conditional gradient ascent in single-example subspaces spanned by the marginal dual variables. The optimization is facilitated with a dynamic programming based algorithm that computes best update directions in the feasible set.Experiments show that the algorithm can feasibly optimize training sets of thousands of examples and classification hierarchies consisting of hundreds of nodes. Training of the full hierarchical model is as efficient as training independent SVM-light classifiers for each node. The algorithm's predictive accuracy was found to be competitive with other recently introduced hierarchical multi-category or multilabel classification learning algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1601–1626},
numpages = {26}
}

@article{10.5555/1248547.1248605,
author = {Shalev-Shwartz, Shai and Singer, Yoram},
title = {Efficient Learning of Label Ranking by Soft Projections onto Polyhedra},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We discuss the problem of learning to rank labels from a real valued feedback associated with each label. We cast the feedback as a preferences graph where the nodes of the graph are the labels and edges express preferences over labels. We tackle the learning problem by defining a loss function for comparing a predicted graph with a feedback graph. This loss is materialized by decomposing the feedback graph into bipartite sub-graphs. We then adopt the maximum-margin framework which leads to a quadratic optimization problem with linear constraints. While the size of the problem grows quadratically with the number of the nodes in the feedback graph, we derive a problem of a significantly smaller size and prove that it attains the same minimum. We then describe an efficient algorithm, called SOPOPO, for solving the reduced problem by employing a soft projection onto the polyhedron defined by a reduced set of constraints. We also describe and analyze a wrapper procedure for batch learning when multiple graphs are provided for training. We conclude with a set of experiments which show significant improvements in run time over a state of the art interior-point algorithm.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1567–1599},
numpages = {33}
}

@article{10.5555/1248547.1248604,
author = {Sonnenburg, S\"{o}ren and R\"{a}tsch, Gunnar and Sch\"{a}fer, Christin and Sch\"{o}lkopf, Bernhard},
title = {Large Scale Multiple Kernel Learning},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {While classical kernel-based learning algorithms are based on a single kernel, in practice it is often desirable to use multiple kernels. Lanckriet et al. (2004) considered conic combinations of kernel matrices for classification, leading to a convex quadratically constrained quadratic program. We show that it can be rewritten as a semi-infinite linear program that can be efficiently solved by recycling the standard SVM implementations. Moreover, we generalize the formulation and our method to a larger class of problems, including regression and one-class classification. Experimental results show that the proposed algorithm works for hundred thousands of examples or hundreds of kernels to be combined, and helps for automatic model selection, improving the interpretability of the learning result. In a second part we discuss general speed up mechanism for SVMs, especially when used with sparse feature maps as appear for string kernels, allowing us to train a string kernel SVM on a 10 million real-world splice data set from computational biology. We integrated multiple kernel learning in our machine learning toolbox <tt>SHOGUN</tt> for which the source code is publicly available at <tt>http://www.fml.tuebingen.mpg.de/raetsch/projects/shogun</tt>.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1531–1565},
numpages = {35}
}

@article{10.5555/1248547.1248603,
author = {Mangasarian, Olvi L.},
title = {Exact 1-Norm Support Vector Machines Via Unconstrained Convex Differentiable Minimization},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Support vector machines utilizing the 1-norm, typically set up as linear programs (Mangasarian, 2000; Bradley and Mangasarian, 1998), are formulated here as a completely unconstrained minimization of a convex differentiable piecewise-quadratic objective function in the dual space. The objective function, which has a Lipschitz continuous gradient and contains only one additional finite parameter, can be minimized by a generalized Newton method and leads to an exact solution of the support vector machine problem. The approach here is based on a formulation of a very general linear program as an unconstrained minimization problem and its application to support vector machine classification problems. The present approach which generalizes both (Mangasarian, 2004) and (Fung and Mangasarian, 2004) is also applied to nonlinear approximation where a minimal number of nonlinear kernel functions are utilized to approximate a function from a given number of function values.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1517–1530},
numpages = {14}
}

@article{10.5555/1248547.1248602,
author = {Keerthi, S. Sathiya and Chapelle, Olivier and DeCoste, Dennis},
title = {Building Support Vector Machines with Reduced Classifier Complexity},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Support vector machines (SVMs), though accurate, are not preferred in applications requiring great classification speed, due to the number of support vectors being large. To overcome this problem we devise a primal method with the following properties: (1) it decouples the idea of basis functions from the concept of support vectors; (2) it greedily finds a set of kernel basis functions of a specified maximum size (dmax) to approximate the SVM primal cost function well; (3) it is efficient and roughly scales as O(ndmax2) where n is the number of training examples; and, (4) the number of basis functions it requires to achieve an accuracy close to the SVM accuracy is usually far less than the number of SVM support vectors.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1493–1515},
numpages = {23}
}

@article{10.5555/1248547.1248601,
author = {Zanni, Luca and Serafini, Thomas and Zanghirati, Gaetano},
title = {Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Parallel software for solving the quadratic program arising in training support vector machines for classification problems is introduced. The software implements an iterative decomposition technique and exploits both the storage and the computing resources available on multiprocessor systems, by distributing the heaviest computational tasks of each decomposition iteration. Based on a wide range of recent theoretical advances, relevant decomposition issues, such as the quadratic subproblem solution, the gradient updating, the working set selection, are systematically described and their careful combination to get an effective parallel tool is discussed. A comparison with state-of-the-art packages on benchmark problems demonstrates the good accuracy and the remarkable time saving achieved by the proposed software. Furthermore, challenging experiments on real-world data sets with millions training samples highlight how the software makes large scale standard nonlinear support vector machines effectively tractable on common multiprocessor systems. This feature is not shown by any of the available codes.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1467–1492},
numpages = {26}
}

@article{10.5555/1248547.1248600,
author = {Glasmachers, Tobias and Igel, Christian},
title = {Maximum-Gain Working Set Selection for SVMs},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Support vector machines are trained by solving constrained quadratic optimization problems. This is usually done with an iterative decomposition algorithm operating on a small working set of variables in every iteration. The training time strongly depends on the selection of these variables. We propose the maximum-gain working set selection algorithm for large scale quadratic programming. It is based on the idea to greedily maximize the progress in each single iteration. The algorithm takes second order information from cached kernel matrix entries into account. We prove the convergence to an optimal solution of a variant termed hybrid maximum-gain working set selection. This method is empirically compared to the prominent most violating pair selection and the latest algorithm using second order information. For large training sets our new selection scheme is significantly faster.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1437–1466},
numpages = {30}
}

@article{10.5555/1248547.1248599,
author = {Bie, Tijl De and Cristianini, Nello},
title = {Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The rise of convex programming has changed the face of many research fields in recent years, machine learning being one of the ones that benefitted the most. A very recent developement, the relaxation of combinatorial problems to semi-definite programs (SDP), has gained considerable attention over the last decade (Helmberg, 2000; De Bie and Cristianini, 2004a). Although SDP problems can be solved in polynomial time, for many relaxations the exponent in the polynomial complexity bounds is too high for scaling to large problem sizes. This has hampered their uptake as a powerful new tool in machine learning.In this paper, we present a new and fast SDP relaxation of the normalized graph cut problem, and investigate its usefulness in unsupervised and semi-supervised learning. In particular, this provides a convex algorithm for transduction, as well as approaches to clustering. We further propose a whole cascade of fast relaxations that all hold the middle between older spectral relaxations and the new SDP relaxation, allowing one to trade off computational cost versus relaxation accuracy. Finally, we discuss how the methodology developed in this paper can be applied to other combinatorial problems in machine learning, and we treat the max-cut problem as an example.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1409–1436},
numpages = {28}
}

@article{10.5555/1248547.1248598,
author = {Heiler, Matthias and Schn\"{o}rr, Christoph},
title = {Learning Sparse Representations by Non-Negative Matrix Factorization and Sequential Cone Programming},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We exploit the biconvex nature of the Euclidean non-negative matrix factorization (NMF) optimization problem to derive optimization schemes based on sequential quadratic and second order cone programming. We show that for ordinary NMF, our approach performs as well as existing state-of-the-art algorithms, while for sparsity-constrained NMF, as recently proposed by P. O. Hoyer in JMLR 5 (2004), it outperforms previous methods. In addition, we show how to extend NMF learning within the same optimization framework in order to make use of class membership information in supervised learning problems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1385–1407},
numpages = {23}
}

@article{10.5555/1248547.1248597,
author = {Niculescu, Radu Stefan and Mitchell, Tom M. and Rao, R. Bharat},
title = {Bayesian Network Learning with Parameter Constraints},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The task of learning models for many real-world problems requires incorporating domain knowledge into learning algorithms, to enable accurate learning from a realistic volume of training data. This paper considers a variety of types of domain knowledge for constraining parameter estimates when learning Bayesian networks. In particular, we consider domain knowledge that constrains the values or relationships among subsets of parameters in a Bayesian network with known structure.We incorporate a wide variety of parameter constraints into learning procedures for Bayesian networks, by formulating this task as a constrained optimization problem. The assumptions made in module networks, dynamic Bayes nets and context specific independence models can be viewed as particular cases of such parameter constraints. We present closed form solutions or fast iterative algorithms for estimating parameters subject to several specific classes of parameter constraints, including equalities and inequalities among parameters, constraints on individual parameters, and constraints on sums and ratios of parameters, for discrete and continuous variables. Our methods cover learning from both frequentist and Bayesian points of view, from both complete and incomplete data.We present formal guarantees for our estimators, as well as methods for automatically learning useful parameter constraints from data. To validate our approach, we apply it to the domain of fMRI brain image analysis. Here we demonstrate the ability of our system to first learn useful relationships among parameters, and then to use them to constrain the training of the Bayesian network, resulting in improved cross-validated accuracy of the learned model. Experiments on synthetic data are also presented.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1357–1383},
numpages = {27}
}

@article{10.5555/1248547.1248596,
author = {Bergkvist, Anders and Damaschke, Peter and L\"{u}thi, Marcel},
title = {Linear Programs for Hypotheses Selection in Probabilistic Inference Models},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We consider an optimization problem in probabilistic inference: Given n hypotheses Hj, m possible observations Ok, their conditional probabilities pkj, and a particular Ok, select a possibly small subset of hypotheses excluding the true target only with some error probability ε. After specifying the optimization goal we show that this problem can be solved through a linear program in mn variables that indicate the probabilities to discard a hypothesis given an observation. Moreover, we can compute optimal strategies where only O(m+n) of these variables get fractional values. The manageable size of the linear programs and the mostly deterministic shape of optimal strategies makes the method practicable. We interpret the dual variables as worst-case distributions of hypotheses, and we point out some counterintuitive nonmonotonic behaviour of the variables as a function of the error bound ε. One of the open problems is the existence of a purely combinatorial algorithm that is faster than generic linear programming.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1339–1355},
numpages = {17}
}

@article{10.5555/1248547.1248595,
author = {Zhang, Yi and Burer, Samuel and Street, W. Nick},
title = {Ensemble Pruning Via Semi-Definite Programming},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {An ensemble is a group of learning models that jointly solve a problem. However, the ensembles generated by existing techniques are sometimes unnecessarily large, which can lead to extra memory usage, computational costs, and occasional decreases in effectiveness. The purpose of ensemble pruning is to search for a good subset of ensemble members that performs as well as, or better than, the original ensemble. This subset selection problem is a combinatorial optimization problem and thus finding the exact optimal solution is computationally prohibitive. Various heuristic methods have been developed to obtain an approximate solution. However, most of the existing heuristics use simple greedy search as the optimization method, which lacks either theoretical or empirical quality guarantees. In this paper, the ensemble subset selection problem is formulated as a quadratic integer programming problem. By applying semi-definite programming (SDP) as a solution technique, we are able to get better approximate solutions. Computational experiments show that this SDP-based pruning algorithm outperforms other heuristics in the literature. Its application in a classifier-sharing study also demonstrates the effectiveness of the method.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1315–1338},
numpages = {24}
}

@article{10.5555/1248547.1248594,
author = {Shivaswamy, Pannagadatta K. and Bhattacharyya, Chiranjib and Smola, Alexander J.},
title = {Second Order Cone Programming Approaches for Handling Missing and Uncertain Data},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We propose a novel second order cone programming formulation for designing robust classifiers which can handle uncertainty in observations. Similar formulations are also derived for designing regression functions which are robust to uncertainties in the regression setting. The proposed formulations are independent of the underlying distribution, requiring only the existence of second order moments. These formulations are then specialized to the case of missing values in observations for both classification and regression problems. Experiments show that the proposed formulations outperform imputation.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1283–1314},
numpages = {32}
}

@article{10.5555/1248547.1248593,
author = {Bennett, Kristin P. and Parrado-Hern\'{a}ndez, Emilio},
title = {The Interplay of Optimization and Machine Learning Research},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The fields of machine learning and mathematical programming are increasingly intertwined. Optimization problems lie at the heart of most machine learning approaches. The Special Topic on Machine Learning and Large Scale Optimization examines this interplay. Machine learning researchers have embraced the advances in mathematical programming allowing new types of models to be pursued. The special topic includes models using quadratic, linear, second-order cone, semi-definite, and semi-infinite programs. We observe that the qualities of good optimization algorithms from the machine learning and optimization perspectives can be quite different. Mathematical programming puts a premium on accuracy, speed, and robustness. Since generalization is the bottom line in machine learning and training is normally done off-line, accuracy and small speed improvements are of little concern in machine learning. Machine learning prefers simpler algorithms that work in reasonable computational time for specific classes of problems. Reducing machine learning problems to well-explored mathematical programming classes with robust general purpose optimization codes allows machine learning researchers to rapidly develop new techniques. In turn, machine learning presents new challenges to mathematical programming. The special issue include papers from two primary themes: novel machine learning models and novel optimization approaches for existing models. Many papers blend both themes, making small changes in the underlying core mathematical program that enable the develop of effective new algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1265–1281},
numpages = {17}
}

@article{10.5555/1248547.1248592,
author = {Takeuchi, Ichiro and Le, Quoc V. and Sears, Timothy D. and Smola, Alexander J.},
title = {Nonparametric Quantile Estimation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In regression, the desired estimate of y|x is not always given by a conditional mean, although this is most common. Sometimes one wants to obtain a good estimate that satisfies the property that a proportion, τ, of y|x, will be below the estimate. For τ = 0.5 this is an estimate of the median. What might be called median regression, is subsumed under the term quantile regression. We present a nonparametric version of a quantile estimator, which can be obtained by solving a simple quadratic programming problem and provide uniform convergence statements and bounds on the quantile property of our estimator. Experimental results show the feasibility of the approach and competitiveness of our method with existing ones. We discuss several types of extensions including an approach to solve the quantile crossing problems, as well as a method to incorporate prior qualitative knowledge such as monotonicity constraints.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1231–1264},
numpages = {34}
}

@article{10.5555/1248547.1248591,
author = {Cesa-Bianchi, Nicol\`{o} and Gentile, Claudio and Zaniboni, Luca},
title = {Worst-Case Analysis of Selective Sampling for Linear Classification},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {A selective sampling algorithm is a learning algorithm for classification that, based on the past observed data, decides whether to ask the label of each new instance to be classified. In this paper, we introduce a general technique for turning linear-threshold classification algorithms from the general additive family into randomized selective sampling algorithms. For the most popular algorithms in this family we derive mistake bounds that hold for individual sequences of examples. These bounds show that our semi-supervised algorithms can achieve, on average, the same accuracy as that of their fully supervised counterparts, but using fewer labels. Our theoretical results are corroborated by a number of experiments on real-world textual data. The outcome of these experiments is essentially predicted by our theoretical results: Our selective sampling algorithms tend to perform as well as the algorithms receiving the true label after each classification, while observing in practice substantially fewer labels.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1205–1230},
numpages = {26}
}

@article{10.5555/1248547.1248590,
author = {Ye, Jieping and Xiong, Tao},
title = {Computational and Theoretical Analysis of Null Space and Orthogonal Linear Discriminant Analysis},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Dimensionality reduction is an important pre-processing step in many applications. Linear discriminant analysis (LDA) is a classical statistical approach for supervised dimensionality reduction. It aims to maximize the ratio of the between-class distance to the within-class distance, thus maximizing the class discrimination. It has been used widely in many applications. However, the classical LDA formulation requires the nonsingularity of the scatter matrices involved. For undersampled problems, where the data dimensionality is much larger than the sample size, all scatter matrices are singular and classical LDA fails. Many extensions, including null space LDA (NLDA) and orthogonal LDA (OLDA), have been proposed in the past to overcome this problem. NLDA aims to maximize the between-class distance in the null space of the within-class scatter matrix, while OLDA computes a set of orthogonal discriminant vectors via the simultaneous diagonalization of the scatter matrices. They have been applied successfully in various applications.In this paper, we present a computational and theoretical analysis of NLDA and OLDA. Our main result shows that under a mild condition which holds in many applications involving high-dimensional data, NLDA is equivalent to OLDA. We have performed extensive experiments on various types of data and results are consistent with our theoretical analysis. We further apply the regularization to OLDA. The algorithm is called regularized OLDA (or ROLDA for short). An efficient algorithm is presented to estimate the regularization value in ROLDA. A comparative study on classification shows that ROLDA is very competitive with OLDA. This confirms the effectiveness of the regularization in ROLDA.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1183–1204},
numpages = {22}
}

@article{10.5555/1248547.1248589,
author = {Castillo, Enrique and Guijarro-Berdi\~{n}as, Bertha and Fontenla-Romero, Oscar and Alonso-Betanzos, Amparo},
title = {A Very Fast Learning Method for Neural Networks Based on Sensitivity Analysis},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {This paper introduces a learning method for two-layer feedforward neural networks based on sensitivity analysis, which uses a linear training algorithm for each of the two layers. First, random values are assigned to the outputs of the first layer; later, these initial values are updated based on sensitivity formulas, which use the weights in each of the layers; the process is repeated until convergence. Since these weights are learnt solving a linear system of equations, there is an important saving in computational time. The method also gives the local sensitivities of the least square errors with respect to input and output data, with no extra computational cost, because the necessary information becomes available without extra calculations. This method, called the Sensitivity-Based Linear Learning Method, can also be used to provide an initial set of weights, which significantly improves the behavior of other learning algorithms. The theoretical basis for the method is given and its performance is illustrated by its application to several examples in which it is compared with several learning algorithms and well known data sets. The results have shown a learning speed generally faster than other existing methods. In addition, it can be used as an initialization tool for other well known methods with significant improvements.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1159–1182},
numpages = {24}
}

@article{10.5555/1248547.1248588,
author = {Liu, Ting and Moore, Andrew W. and Gray, Alexander},
title = {New Algorithms for Efficient High-Dimensional Nonparametric Classification},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {This paper is about non-approximate acceleration of high-dimensional nonparametric operations such as k nearest neighbor classifiers. We attempt to exploit the fact that even if we want exact answers to nonparametric queries, we usually do not need to explicitly find the data points close to the query, but merely need to answer questions about the properties of that set of data points. This offers a small amount of computational leeway, and we investigate how much that leeway can be exploited. This is applicable to many algorithms in nonparametric statistics, memory-based learning and kernel-based learning. But for clarity, this paper concentrates on pure k-NN classification. We introduce new ball-tree algorithms that on real-world data sets give accelerations from 2-fold to 100-fold compared against highly optimized traditional ball-tree-based k-NN. These results include data sets with up to 106 dimensions and 105 records, and demonstrate non-trivial speed-ups while giving exact answers.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1135–1158},
numpages = {24}
}

@article{10.5555/1248547.1248587,
author = {Vishwanathan, S. V.N. and Schraudolph, Nicol N. and Smola, Alex J.},
title = {Step Size Adaptation in Reproducing Kernel Hilbert Space},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {This paper presents an online support vector machine (SVM) that uses the stochastic meta-descent (SMD) algorithm to adapt its step size automatically. We formulate the online learning problem as a stochastic gradient descent in reproducing kernel Hilbert space (RKHS) and translate SMD to the nonparametric setting, where its gradient trace parameter is no longer a coefficient vector but an element of the RKHS. We derive efficient updates that allow us to perform the step size adaptation in linear time. We apply the online SVM framework to a variety of loss functions, and in particular show how to handle structured output spaces and achieve efficient online multiclass classification. Experiments show that our algorithm outperforms more primitive methods for setting the gradient step size.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1107–1133},
numpages = {27}
}

@article{10.5555/1248547.1248586,
author = {Even-Dar, Eyal and Mannor, Shie and Mansour, Yishay},
title = {Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We incorporate statistical confidence intervals in both the multi-armed bandit and the reinforcement learning problems. In the bandit problem we show that given n arms, it suffices to pull the arms a total of O((n/ε2)log(1/δ)) times to find an ε-optimal arm with probability of at least 1-δ. This bound matches the lower bound of Mannor and Tsitsiklis (2004) up to constants. We also devise action elimination procedures in reinforcement learning algorithms. We describe a framework that is based on learning the confidence interval around the value function or the Q-function and eliminating actions that are not optimal (with high probability). We provide a model-based and a model-free variants of the elimination method. We further derive stopping conditions guaranteeing that the learned policy is approximately optimal with high probability. Simulations demonstrate a considerable speedup and added robustness over ε-greedy Q-learning.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1079–1105},
numpages = {27}
}

@article{10.5555/1248547.1248585,
author = {Roverato, Alberto and Studen\'{y}, Milan},
title = {A Graphical Representation of Equivalence Classes of AMP Chain Graphs},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {This paper deals with chain graph models under alternative AMP interpretation. A new representative of an AMP Markov equivalence class, called the largest deflagged graph, is proposed. The representative is based on revealed internal structure of the AMP Markov equivalence class. More specifically, the AMP Markov equivalence class decomposes into finer strong equivalence classes and there exists a distinguished strong equivalence class among those forming the AMP Markov equivalence class. The largest deflagged graph is the largest chain graph in that distinguished strong equivalence class. A composed graphical procedure to get the largest deflagged graph on the basis of any AMP Markov equivalent chain graph is presented. In general, the largest deflagged graph differs from the AMP essential graph, which is another representative of the AMP Markov equivalence class.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1045–1078},
numpages = {34}
}

@article{10.5555/1248547.1248584,
author = {Gardner, Andrew B. and Krieger, Abba M. and Vachtsevanos, George and Litt, Brian},
title = {One-Class Novelty Detection for Seizure Analysis from Intracranial EEG},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {This paper describes an application of one-class support vector machine (SVM) novelty detection for detecting seizures in humans. Our technique maps intracranial electroencephalogram (EEG) time series into corresponding novelty sequences by classifying short-time, energy-based statistics computed from one-second windows of data. We train a classifier on epochs of interictal (normal) EEG. During ictal (seizure) epochs of EEG, seizure activity induces distributional changes in feature space that increase the empirical outlier fraction. A hypothesis test determines when the parameter change differs significantly from its nominal value, signaling a seizure detection event. Outputs are gated in a .one-shot. manner using persistence to reduce the false alarm rate of the system. The detector was validated using leave-one-out cross-validation (LOO-CV) on a sample of 41 interictal and 29 ictal epochs, and achieved 97.1% sensitivity, a mean detection latency of -7.58 seconds, and an asymptotic false positive rate (FPR) of 1.56 false positives per hour (Fp/hr). These results are better than those obtained from a novelty detection technique based on Mahalanobis distance outlier detection, and comparable to the performance of a supervised learning technique used in experimental implantable devices (Echauz et al., 2001). The novelty detection paradigm overcomes three significant limitations of competing methods: the need to collect seizure data, precisely mark seizure onset and offset times, and perform patient-specific parameter tuning for detector training.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1025–1044},
numpages = {20}
}

@article{10.5555/1248547.1248583,
author = {B\"{u}hlmann, Peter and Yu, Bin},
title = {Sparse Boosting},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = { We propose Sparse Boosting (the SparseL2Boost algorithm), a variant on boosting with the squared error loss. SparseL2Boost yields sparser solutions than the previously proposed L2Boosting by minimizing some penalized L2-loss functions, the FPE model selection criteria, through small-step gradient descent. Although boosting may give already relatively sparse solutions, for example corresponding to the soft-thresholding estimator in orthogonal linear models, there is sometimes a desire for more sparseness to increase prediction accuracy and ability for better variable selection: such goals can be achieved with SparseL2Boost.We prove an equivalence of SparseL2Boost to Breiman's nonnegative garrote estimator for orthogonal linear models and demonstrate the generic nature of SparseL2Boost for nonparametric interaction modeling. For an automatic selection of the tuning parameter in SparseL2Boost we propose to employ the gMDL model selection criterion which can also be used for early stopping of L2Boosting. Consequently, we can select between SparseL2Boost and L2Boosting by comparing their gMDL scores.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1001–1024},
numpages = {24}
}

@article{10.5555/1248547.1248582,
author = {Meinshausen, Nicolai},
title = {Quantile Regression Forests},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Random forests were introduced as a machine learning tool in Breiman (2001) and have since proven to be very popular and powerful for high-dimensional regression and classification. For regression, random forests give an accurate approximation of the conditional mean of a response variable. It is shown here that random forests provide information about the full conditional distribution of the response variable, not only about the conditional mean. Conditional quantiles can be inferred with quantile regression forests, a generalisation of random forests. Quantile regression forests give a non-parametric and accurate way of estimating conditional quantiles for high-dimensional predictor variables. The algorithm is shown to be consistent. Numerical examples suggest that the algorithm is competitive in terms of predictive power.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {983–999},
numpages = {17}
}

@article{10.5555/1248547.1248581,
author = {Lecu\'{e}, Guillaume},
title = {Lower Bounds and Aggregation in Density Estimation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In this paper we prove the optimality of an aggregation procedure. We prove lower bounds for aggregation of model selection type of M density estimators for the Kullback-Leibler divergence (KL), the Hellinger's distance and the L1-distance. The lower bound, with respect to the KL distance, can be achieved by the on-line type estimate suggested, among others, by Yang (2000a). Combining these results, we state that log M/n is an optimal rate of aggregation in the sense of Tsybakov (2003), where n is the sample size.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {971–981},
numpages = {11}
}

@article{10.5555/1248547.1248580,
author = {Kim, Seyoung and Smyth, Padhraic},
title = {Segmental Hidden Markov Models with Random Effects for Waveform Modeling},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {This paper proposes a general probabilistic framework for shape-based modeling and classification of waveform data. A segmental hidden Markov model (HMM) is used to characterize waveform shape and shape variation is captured by adding random effects to the segmental model. The resulting probabilistic framework provides a basis for learning of waveform models from data as well as parsing and recognition of new waveforms. Expectation-maximization (EM) algorithms are derived and investigated for fitting such models to data. In particular, the "expectation conditional maximization either" (ECME) algorithm is shown to provide significantly faster convergence than a standard EM procedure. Experimental results on two real-world data sets demonstrate that the proposed approach leads to improved accuracy in classification and segmentation when compared to alternatives such as Euclidean distance matching, dynamic time warping, and segmental HMMs without random effects.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {945–969},
numpages = {25}
}

@article{10.5555/1248547.1248579,
author = {Climer, Sharlee and Zhang, Weixiong},
title = {Rearrangement Clustering: Pitfalls, Remedies, and Applications},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Given a matrix of values in which the rows correspond to objects and the columns correspond to features of the objects, rearrangement clustering is the problem of rearranging the rows of the matrix such that the sum of the similarities between adjacent rows is maximized. Referred to by various names and reinvented several times, this clustering technique has been extensively used in many fields over the last three decades. In this paper, we point out two critical pitfalls that have been previously overlooked. The first pitfall is deleterious when rearrangement clustering is applied to objects that form natural clusters. The second concerns a similarity metric that is commonly used. We present an algorithm that overcomes these pitfalls. This algorithm is based on a variation of the Traveling Salesman Problem. It offers an extra benefit as it automatically determines cluster boundaries. Using this algorithm, we optimally solve four benchmark problems and a 2,467-gene expression data clustering problem. As expected, our new algorithm identifies better clusters than those found by previous approaches in all five cases. Overall, our results demonstrate the benefits of rectifying the pitfalls and exemplify the usefulness of this clustering technique. Our code is available at our websites.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {919–943},
numpages = {25}
}

@article{10.5555/1248547.1248578,
author = {Whiteson, Shimon and Stone, Peter},
title = {Evolutionary Function Approximation for Reinforcement Learning},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Temporal difference methods are theoretically grounded and empirically effective methods for addressing reinforcement learning problems. In most real-world reinforcement learning tasks, TD methods require a function approximator to represent the value function. However, using function approximators requires manually making crucial representational decisions. This paper investigates evolutionary function approximation, a novel approach to automatically selecting function approximator representations that enable efficient individual learning. This method evolves individuals that are better able to learn. We present a fully implemented instantiation of evolutionary function approximation which combines NEAT, a neuroevolutionary optimization technique, with Q-learning, a popular TD method. The resulting NEAT+Q algorithm automatically discovers effective representations for neural network function approximators. This paper also presents on-line evolutionary computation, which improves the on-line performance of evolutionary computation by borrowing selection mechanisms used in TD methods to choose individual actions and using them in evolutionary computation to select policies for evaluation. We evaluate these contributions with extended empirical studies in two domains: 1) the mountain car task, a standard reinforcement learning benchmark on which neural network function approximators have previously performed poorly and 2) server job scheduling, a large probabilistic domain drawn from the field of autonomic computing. The results demonstrate that evolutionary function approximation can significantly improve the performance of TD methods and on-line evolutionary computation can significantly improve evolutionary methods. This paper also presents additional tests that offer insight into what factors can make neural network function approximation difficult in practice.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {877–917},
numpages = {41}
}

@article{10.5555/1248547.1248577,
author = {Lippert, Ross A. and Rifkin, Ryan M.},
title = {Infinite-σ Limits For Tikhonov Regularization},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We consider the problem of Tikhonov regularization with a general convex loss function: this formalism includes support vector machines and regularized least squares. For a family of kernels that includes the Gaussian, parameterized by a "bandwidth" parameter σ, we characterize the limiting solution as σ → ∞. In particular, we show that if we set the regularization parameter λ = ~λ σ-2p, the regularization term of the Tikhonov problem tends to an indicator function on polynomials of degree ⌊p⌋ (with residual regularization in the case where p ∈ Z). The proof rests on two key ideas: epi-convergence, a notion of functional convergence under which limits of minimizers converge to minimizers of limits, and a value-based formulation of learning, where we work with regularization on the function output values (y) as opposed to the function expansion coefficients in the RKHS. Our result generalizes and unifies previous results in this area.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {855–876},
numpages = {22}
}

@article{10.5555/1248547.1248576,
author = {Vert, R\'{e}gis and Vert, Jean-Philippe},
title = {Consistency and Convergence Rates of One-Class SVMs and Related Algorithms},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We determine the asymptotic behaviour of the function computed by support vector machines (SVM) and related algorithms that minimize a regularized empirical convex loss function in the reproducing kernel Hilbert space of the Gaussian RBF kernel, in the situation where the number of examples tends to infinity, the bandwidth of the Gaussian kernel tends to 0, and the regularization parameter is held fixed. Non-asymptotic convergence bounds to this limit in the L2 sense are provided, together with upper bounds on the classification error that is shown to converge to the Bayes risk, therefore proving the Bayes-consistency of a variety of methods although the regularization term does not vanish. These results are particularly relevant to the one-class SVM, for which the regularization can not vanish by construction, and which is shown for the first time to be a consistent density level set estimator.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {817–854},
numpages = {38}
}

@article{10.5555/1248547.1248575,
author = {Spratling, Michael W.},
title = {Learning Image Components for Object Recognition},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In order to perform object recognition it is necessary to learn representations of the underlying components of images. Such components correspond to objects, object-parts, or features. Non-negative matrix factorisation is a generative model that has been specifically proposed for finding such meaningful representations of image data, through the use of non-negativity constraints on the factors. This article reports on an empirical investigation of the performance of non-negative matrix factorisation algorithms. It is found that such algorithms need to impose additional constraints on the sparseness of the factors in order to successfully deal with occlusion. However, these constraints can themselves result in these algorithms failing to identify image components under certain conditions. In contrast, a recognition model (a competitive learning neural network algorithm) reliably and accurately learns representations of elementary image features without such constraints.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {793–815},
numpages = {23}
}

@article{10.5555/1248547.1248574,
author = {Munos, R\'{e}mi},
title = {Policy Gradient in Continuous Time},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Policy search is a method for approximately solving an optimal control problem by performing a parametric optimization search in a given class of parameterized policies. In order to process a local optimization technique, such as a gradient method, we wish to evaluate the sensitivity of the performance measure with respect to the policy parameters, the so-called policy gradient. This paper is concerned with the estimation of the policy gradient for continuous-time, deterministic state dynamics, in a reinforcement learning framework, that is, when the decision maker does not have a model of the state dynamics.We show that usual likelihood ratio methods used in discrete-time, fail to proceed the gradient because they are subject to variance explosion when the discretization time-step decreases to 0. We describe an alternative approach based on the approximation of the pathwise derivative, which leads to a policy gradient estimate that converges almost surely to the true gradient when the time-step tends to 0. The underlying idea starts with the derivation of an explicit representation of the policy gradient using pathwise derivation. This derivation makes use of the knowledge of the state dynamics. Then, in order to estimate the gradient from the observable data only, we use a stochastic policy to discretize the continuous deterministic system into a stochastic discrete process, which enables to replace the unknown coefficients by quantities that solely depend on known data. We prove the almost sure convergence of this estimate to the true policy gradient when the discretization time-step goes to zero.The method is illustrated on two target problems, in discrete and continuous control spaces.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {771–791},
numpages = {21}
}

@article{10.5555/1248547.1248573,
author = {Hush, Don and Kelly, Patrick and Scovel, Clint and Steinwart, Ingo},
title = {QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We describe polynomial--time algorithms that produce approximate solutions with guaranteed accuracy for a class of QP problems that are used in the design of support vector machine classifiers. These algorithms employ a two--stage process where the first stage produces an approximate solution to a dual QP problem and the second stage maps this approximate dual solution to an approximate primal solution. For the second stage we describe an O(n log n) algorithm that maps an approximate dual solution with accuracy (2(2Km)1/2+8(λ)1/2)-2 λ εp2 to an approximate primal solution with accuracy εp where n is the number of data samples, Kn is the maximum kernel value over the data and λ > 0 is the SVM regularization parameter. For the first stage we present new results for decomposition algorithms and describe new decomposition algorithms with guaranteed accuracy and run time. In particular, for τ-rate certifying decomposition algorithms we establish the optimality of τ = 1/(n-1). In addition we extend the recent τ = 1/(n-1) algorithm of Simon (2004) to form two new composite algorithms that also achieve the τ = 1/(n-1) iteration bound of List and Simon (2005), but yield faster run times in practice. We also exploit the τ-rate certifying property of these algorithms to produce new stopping rules that are computationally efficient and that guarantee a specified accuracy for the approximate dual solution. Furthermore, for the dual QP problem corresponding to the standard classification problem we describe operational conditions for which the Simon and composite algorithms possess an upper bound of O(n) on the number of iterations. For this same problem we also describe general conditions for which a matching lower bound exists for any decomposition algorithm that uses working sets of size 2. For the Simon and composite algorithms we also establish an O(n2) bound on the overall run time for the first stage. Combining the first and second stages gives an overall run time of O(n2(ck + 1)) where ck is an upper bound on the computation to perform a kernel evaluation. Pseudocode is presented for a complete algorithm that inputs an accuracy εp and produces an approximate solution that satisfies this accuracy in low order polynomial time. Experiments are included to illustrate the new stopping rules and to compare the Simon and composite decomposition algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {733–769},
numpages = {37}
}

@article{10.5555/1248547.1248572,
author = {Bickel, Peter J. and Ritov, Ya'acov and Zakai, Alon},
title = {Some Theory for Generalized Boosting Algorithms},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We give a review of various aspects of boosting, clarifying the issues through a few simple results, and relate our work and that of others to the minimax paradigm of statistics. We consider the population version of the boosting algorithm and prove its convergence to the Bayes classifier as a corollary of a general result about Gauss-Southwell optimization in Hilbert space. We then investigate the algorithmic convergence of the sample version, and give bounds to the time until perfect separation of the sample. We conclude by some results on the statistical optimality of the L2 boosting.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {705–732},
numpages = {28}
}

@article{10.5555/1248547.1248571,
author = {Scott, Clayton D. and Nowak, Robert D.},
title = {Learning Minimum Volume Sets},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Given a probability measure P and a reference measure μ, one is often interested in the minimum μ-measure set with P-measure at least α. Minimum volume sets of this type summarize the regions of greatest probability mass of P, and are useful for detecting anomalies and constructing confidence regions. This paper addresses the problem of estimating minimum volume sets based on independent samples distributed according to P. Other than these samples, no other information is available regarding P, but the reference measure μ is assumed to be known. We introduce rules for estimating minimum volume sets that parallel the empirical risk minimization and structural risk minimization principles in classification. As in classification, we show that the performances of our estimators are controlled by the rate of uniform convergence of empirical to true probabilities over the class from which the estimator is drawn. Thus we obtain finite sample size performance bounds in terms of VC dimension and related quantities. We also demonstrate strong universal consistency, an oracle inequality, and rates of convergence. The proposed estimators are illustrated with histogram and decision tree set estimation rules.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {665–704},
numpages = {40}
}

@article{10.5555/1248547.1248570,
author = {Ryabko, Daniil},
title = {Pattern Recognition for Conditionally Independent Data},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In this work we consider the task of relaxing the i.i.d. assumption in pattern recognition (or classification), aiming to make existing learning algorithms applicable to a wider range of tasks. Pattern recognition is guessing a discrete label of some object based on a set of given examples (pairs of objects and labels). We consider the case of deterministically defined labels. Traditionally, this task is studied under the assumption that examples are independent and identically distributed. However, it turns out that many results of pattern recognition theory carry over a weaker assumption. Namely, under the assumption of conditional independence and identical distribution of objects, while the only assumption on the distribution of labels is that the rate of occurrence of each label should be above some positive threshold.We find a broad class of learning algorithms for which estimations of the probability of the classification error achieved under the classical i.i.d. assumption can be generalized to the similar estimates for case of conditionally i.i.d. examples.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {645–664},
numpages = {20}
}

@article{10.5555/1248547.1248569,
author = {Watanabe, Kazuho and Watanabe, Sumio},
title = {Stochastic Complexities of Gaussian Mixtures in Variational Bayesian Approximation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Bayesian learning has been widely used and proved to be effective in many data modeling problems. However, computations involved in it require huge costs and generally cannot be performed exactly. The variational Bayesian approach, proposed as an approximation of Bayesian learning, has provided computational tractability and good generalization performance in many applications.The properties and capabilities of variational Bayesian learning itself have not been clarified yet. It is still unknown how good approximation the variational Bayesian approach can achieve. In this paper, we discuss variational Bayesian learning of Gaussian mixture models and derive upper and lower bounds of variational stochastic complexities. The variational stochastic complexity, which corresponds to the minimum variational free energy and a lower bound of the Bayesian evidence, not only becomes important in addressing the model selection problem, but also enables us to discuss the accuracy of the variational Bayesian approach as an approximation of true Bayesian learning.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {625–644},
numpages = {20}
}

@article{10.5555/1248547.1248568,
author = {Wu, Mingrui and Sch\"{o}lkopf, Bernhard and Bak\i{}r, G\"{o}khan},
title = {A Direct Method for Building Sparse Kernel Learning Algorithms},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Many kernel learning algorithms, including support vector machines, result in a kernel machine, such as a kernel classifier, whose key component is a weight vector in a feature space implicitly introduced by a positive definite kernel function. This weight vector is usually obtained by solving a convex optimization problem. Based on this fact we present a direct method to build sparse kernel learning algorithms by adding one more constraint to the original convex optimization problem, such that the sparseness of the resulting kernel machine is explicitly controlled while at the same time performance is kept as high as possible. A gradient based approach is provided to solve this modified optimization problem. Applying this method to the support vectom machine results in a concrete algorithm for building sparse large margin classifiers. These classifiers essentially find a discriminating subspace that can be spanned by a small number of vectors, and in this subspace, the different classes of data are linearly well separated. Experimental results over several classification benchmarks demonstrate the effectiveness of our approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {603–624},
numpages = {22}
}

@article{10.5555/1248547.1248567,
author = {Klivans, Adam R. and Servedio, Rocco A.},
title = {Toward Attribute Efficient Learning of Decision Lists and Parities},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We consider two well-studied problems regarding attribute efficient learning: learning decision lists and learning parity functions. First, we give an algorithm for learning decision lists of length k over n variables using 2\~{O}(k1/3) log n examples and time n\~{O}(k1/3). This is the first algorithm for learning decision lists that has both subexponential sample complexity and subexponential running time in the relevant parameters. Our approach is based on a new construction of low degree, low weight polynomial threshold functions for decision lists. For a wide range of parameters our construction matches a lower bound due to Beigel for decision lists and gives an essentially optimal tradeoff between polynomial threshold function degree and weight.Second, we give an algorithm for learning an unknown parity function on k out of n variables using O(n1-1/k) examples in poly(n) time. For k=o(log n) this yields the first polynomial time algorithm for learning parity on a superconstant number of variables with sublinear sample complexity. We also give a simple algorithm for learning an unknown length-k parity using O(k log n) examples in nk/2 time, which improves on the naive nk time bound of exhaustive search.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {587–602},
numpages = {16}
}

@article{10.5555/1248547.1248566,
author = {Crammer, Koby and Dekel, Ofer and Keshet, Joseph and Shalev-Shwartz, Shai and Singer, Yoram},
title = {Online Passive-Aggressive Algorithms},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We present a family of margin based online learning algorithms for various prediction tasks. In particular we derive and analyze algorithms for binary and multiclass categorization, regression, uniclass prediction and sequence prediction. The update steps of our different algorithms are all based on analytical solutions to simple constrained optimization problems. This unified view allows us to prove worst-case loss bounds for the different algorithms and for the various decision problems based on a single lemma. Our bounds on the cumulative loss of the algorithms are relative to the smallest loss that can be attained by any fixed hypothesis, and as such are applicable to both realizable and unrealizable settings. We demonstrate some of the merits of the proposed algorithms in a series of experiments with synthetic and real data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {551–585},
numpages = {35}
}

@article{10.5555/1248547.1248565,
author = {Mukherjee, Sayan and Zhou, Ding-Xuan},
title = {Learning Coordinate Covariances via Gradients},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We introduce an algorithm that learns gradients from samples in the supervised learning framework. An error analysis is given for the convergence of the gradient estimated by the algorithm to the true gradient. The utility of the algorithm for the problem of variable selection as well as determining variable covariance is illustrated on simulated data as well as two gene expression data sets. For square loss we provide a very efficient implementation with respect to both memory and time.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {519–549},
numpages = {31}
}

@article{10.5555/1248547.1248564,
author = {Langley, Pat and Choi, Dongkyu},
title = {Learning Recursive Control Programs from Problem Solving},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In this paper, we propose a new representation for physical control -- teleoreactive logic programs -- along with an interpreter that uses them to achieve goals. In addition, we present a new learning method that acquires recursive forms of these structures from traces of successful problem solving. We report experiments in three different domains that demonstrate the generality of this approach. In closing, we review related work on learning complex skills and discuss directions for future research on this topic.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {493–518},
numpages = {26}
}

@article{10.5555/1248547.1248563,
author = {Centeno, Tonatiuh Pe\~{n}a and Lawrence, Neil D.},
title = {Optimising Kernel Parameters and Regularisation Coefficients for Non-Linear Discriminant Analysis},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In this paper we consider a novel Bayesian interpretation of Fisher's discriminant analysis. We relate Rayleigh's coefficient to a noise model that minimises a cost based on the most probable class centres and that abandons the 'regression to the labels' assumption used by other algorithms. Optimisation of the noise model yields a direction of discrimination equivalent to Fisher's discriminant, and with the incorporation of a prior we can apply Bayes' rule to infer the posterior distribution of the direction of discrimination. Nonetheless, we argue that an additional constraining distribution has to be included if sensible results are to be obtained. Going further, with the use of a Gaussian process prior we show the equivalence of our model to a regularised kernel Fisher's discriminant. A key advantage of our approach is the facility to determine kernel parameters and the regularisation coefficient through the optimisation of the marginal log-likelihood of the data. An added bonus of the new formulation is that it enables us to link the regularisation coefficient with the generalisation error.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {455–491},
numpages = {37}
}

@article{10.5555/1248547.1248562,
author = {Kitzelmann, Emanuel and Schmid, Ute},
title = {Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We describe an approach to the inductive synthesis of recursive equations from input/output-examples which is based on the classical two-step approach to induction of functional Lisp programs of Summers (1977). In a first step, I/O-examples are rewritten to traces which explain the outputs given the respective inputs based on a datatype theory. These traces can be integrated into one conditional expression which represents a non-recursive program. In a second step, this initial program term is generalized into recursive equations by searching for syntactical regularities in the term. Our approach extends the classical work in several aspects. The most important extensions are that we are able to induce a set of recursive equations in one synthesizing step, the equations may contain more than one recursive call, and additionally needed parameters are automatically introduced.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {429–454},
numpages = {26}
}

@article{10.5555/1248547.1248561,
author = {Munos, R\'{e}mi},
title = {Geometric Variance Reduction in Markov Chains: Application to Value Function and Gradient Estimation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We study a variance reduction technique for Monte Carlo estimation of functionals in Markov chains. The method is based on designing sequential control variates using successive approximations of the function of interest V. Regular Monte Carlo estimates have a variance of O(1/N), where N is the number of sample trajectories of the Markov chain. Here, we obtain a geometric variance reduction O(ρN) (with ρ<1) up to a threshold that depends on the approximation error V-AV, where A is an approximation operator linear in the values. Thus, if V belongs to the right approximation space (i.e. AV=V), the variance decreases geometrically to zero.An immediate application is value function estimation in Markov chains, which may be used for policy evaluation in a policy iteration algorithm for solving Markov Decision Processes.Another important domain, for which variance reduction is highly needed, is gradient estimation, that is computing the sensitivity ∂αV of the performance measure V with respect to some parameter α of the transition probabilities. For example, in policy parametric optimization, computing an estimate of the policy gradient is required to perform a gradient optimization method.We show that, using two approximations for the value function and the gradient, a geometric variance reduction is also achieved, up to a threshold that depends on the approximation errors of both of those representations.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {413–427},
numpages = {15}
}

@article{10.5555/1248547.1248560,
author = {Begleiter, Ron and El-Yaniv, Ran},
title = {Superior Guarantees for Sequential Prediction and Lossless Compression via Alphabet Decomposition},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We present worst case bounds for the learning rate of a known prediction method that is based on hierarchical applications of binary context tree weighting (CTW) predictors. A heuristic application of this approach that relies on Huffman's alphabet decomposition is known to achieve state-of-the-art performance in prediction and lossless compression benchmarks. We show that our new bound for this heuristic is tighter than the best known performance guarantees for prediction and lossless compression algorithms in various settings. This result substantiates the efficiency of this hierarchical method and provides a compelling explanation for its practical success. In addition, we present the results of a few experiments that examine other possibilities for improving the multi-alphabet prediction performance of CTW-based algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {379–411},
numpages = {33}
}

@article{10.5555/1248547.1248559,
author = {Hamerly, Greg and Perelman, Erez and Lau, Jeremy and Calder, Brad and Sherwood, Timothy},
title = {Using Machine Learning to Guide Architecture Simulation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {An essential step in designing a new computer architecture is the careful examination of different design options. It is critical that computer architects have efficient means by which they may estimate the impact of various design options on the overall machine. This task is complicated by the fact that different programs, and even different parts of the same program, may have distinct behaviors that interact with the hardware in different ways. Researchers use very detailed simulators to estimate processor performance, which models every cycle of an executing program. Unfortunately, simulating every cycle of a real program can take weeks or months.To address this problem we have created a tool called SimPoint that uses data clustering algorithms from machine learning to automatically find repetitive patterns in a program's execution. By simulating one representative of each repetitive behavior pattern, simulation time can be reduced to minutes instead of weeks for standard benchmark programs, with very little cost in terms of accuracy. We describe this important problem, the data representation and preprocessing methods used by SimPoint, the clustering algorithm at the core of SimPoint, and we evaluate different options for tuning SimPoint.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {343–378},
numpages = {36}
}

@article{10.5555/1248547.1248558,
author = {Passerini, Andrea and Frasconi, Paolo and Raedt, Luc De},
title = {Kernels on Prolog Proof Trees: Statistical Learning in the ILP Setting},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We develop kernels for measuring the similarity between relational instances using background knowledge expressed in first-order logic. The method allows us to bridge the gap between traditional inductive logic programming (ILP) representations and statistical approaches to supervised learning. Logic programs are first used to generate proofs of given visitor programs that use predicates declared in the available background knowledge. A kernel is then defined over pairs of proof trees. The method can be used for supervised learning tasks and is suitable for classification as well as regression. We report positive empirical results on Bongard-like and M-of-N problems that are difficult or impossible to solve with traditional ILP techniques, as well as on real bioinformatics and chemoinformatics data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {307–342},
numpages = {36}
}

@article{10.5555/1248547.1248557,
author = {Goldberg, Paul W.},
title = {Some Discriminant-Based PAC Algorithms},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {A classical approach in multi-class pattern classification is the following. Estimate the probability distributions that generated the observations for each label class, and then label new instances by applying the Bayes classifier to the estimated distributions. That approach provides more useful information than just a class label; it also provides estimates of the conditional distribution of class labels, in situations where there is class overlap.We would like to know whether it is harder to build accurate classifiers via this approach, than by techniques that may process all data with distinct labels together. In this paper we make that question precise by considering it in the context of PAC learnability. We propose two restrictions on the PAC learning framework that are intended to correspond with the above approach, and consider their relationship with standard PAC learning. Our main restriction of interest leads to some interesting algorithms that show that the restriction is not stronger (more restrictive) than various other well-known restrictions on PAC learning. An alternative slightly milder restriction turns out to be almost equivalent to unrestricted PAC learning.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {283–306},
numpages = {24}
}

@article{10.5555/1248547.1248556,
author = {Blanchard, Gilles and Kawanabe, Motoaki and Sugiyama, Masashi and Spokoiny, Vladimir and M\"{u}ller, Klaus-Robert},
title = {In Search of Non-Gaussian Components of a High-Dimensional Distribution},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Finding non-Gaussian components of high-dimensional data is an important preprocessing step for efficient information processing. This article proposes a new linear method to identify the "non-Gaussian subspace" within a very general semi-parametric framework. Our proposed method, called NGCA (non-Gaussian component analysis), is based on a linear operator which, to any arbitrary nonlinear (smooth) function, associates a vector belonging to the low dimensional non-Gaussian target subspace, up to an estimation error. By applying this operator to a family of different nonlinear functions, one obtains a family of different vectors lying in a vicinity of the target space. As a final step, the target space itself is estimated by applying PCA to this family of vectors. We show that this procedure is consistent in the sense that the estimaton error tends to zero at a parametric rate, uniformly over the family, Numerical examples demonstrate the usefulness of our method.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {247–282},
numpages = {36}
}

@article{10.5555/1248547.1248555,
author = {Silva, Ricardo and Scheines, Richard and Glymour, Clark and Spirtes, Peter},
title = {Learning the Structure of Linear Latent Variable Models},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We describe anytime search procedures that (1) find disjoint subsets of recorded variables for which the members of each subset are d-separated by a single common unrecorded cause, if such exists; (2) return information about the causal relations among the latent factors so identified. We prove the procedure is point-wise consistent assuming (a) the causal relations can be represented by a directed acyclic graph (DAG) satisfying the Markov Assumption and the Faithfulness Assumption; (b) unrecorded variables are not caused by recorded variables; and (c) dependencies are linear. We compare the procedure with standard approaches over a variety of simulated structures and sample sizes, and illustrate its practical value with brief studies of social science data sets. Finally, we consider generalizations for non-linear systems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {191–246},
numpages = {56}
}

@article{10.5555/1248547.1248554,
author = {Pe'er, Dana and Tanay, Amos and Regev, Aviv},
title = {MinReg: A Scalable Algorithm for Learning Parsimonious Regulatory Networks in Yeast and Mammals},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In recent years, there has been a growing interest in applying Bayesian networks and their extensions to reconstruct regulatory networks from gene expression data. Since the gene expression domain involves a large number of variables and a limited number of samples, it poses both computational and statistical challenges to Bayesian network learning algorithms. Here we define a constrained family of Bayesian network structures suitable for this domain and devise an efficient search algorithm that utilizes these structural constraints to find high scoring networks from data. Interestingly, under reasonable assumptions on the underlying probability distribution, we can provide performance guarantees on our algorithm. Evaluation on real data from yeast and mouse, demonstrates that our method cannot only reconstruct a high quality model of the yeast regulatory network, but is also the first method to scale to the complexity of mammalian networks and successfully reconstructs a reasonable model over thousands of variables.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {167–189},
numpages = {23}
}

@article{10.5555/1248547.1248553,
author = {Sugiyama, Masashi},
title = {Active Learning in Approximately Linear Regression Based on Conditional Expectation of Generalization Error},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The goal of active learning is to determine the locations of training input points so that the generalization error is minimized. We discuss the problem of active learning in linear regression scenarios. Traditional active learning methods using least-squares learning often assume that the model used for learning is correctly specified. In many practical situations, however, this assumption may not be fulfilled. Recently, active learning methods using "importance"-weighted least-squares learning have been proposed, which are shown to be robust against misspecification of models. In this paper, we propose a new active learning method also using the weighted least-squares learning, which we call ALICE (Active Learning using the Importance-weighted least-squares learning based on Conditional Expectation of the generalization error). An important difference from existing methods is that we predict the conditional expectation of the generalization error given training input points, while existing methods predict the full expectation of the generalization error. Due to this difference, the training input design can be fine-tuned depending on the realization of training input points. Theoretically, we prove that the proposed active learning criterion is a more accurate predictor of the single-trial generalization error than the existing criterion. Numerical studies with toy and benchmark data sets show that the proposed method compares favorably to existing methods.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {141–166},
numpages = {26}
}

@article{10.5555/1248547.1248552,
author = {Maurer, Andreas},
title = {Bounds for Linear Multi-Task Learning},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We give dimension-free and data-dependent bounds for linear multi-task learning where a common linear operator is chosen to preprocess data for a vector of task specific linear-thresholding classifiers. The complexity penalty of multi-task learning is bounded by a simple expression involving the margins of the task-specific classifiers, the Hilbert-Schmidt norm of the selected preprocessor and the Hilbert-Schmidt norm of the covariance operator for the total mixture of all task distributions, or, alternatively, the Frobenius norm of the total Gramian matrix for the data-dependent version. The results can be compared to state-of-the-art results on linear single-task learning.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {117–139},
numpages = {23}
}

@article{10.5555/1248547.1248551,
author = {Huang, Tzu-Kuo and Weng, Ruby C. and Lin, Chih-Jen},
title = {Generalized Bradley-Terry Models and Multi-Class Probability Estimates},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The Bradley-Terry model for obtaining individual skill from paired comparisons has been popular in many areas. In machine learning, this model is related to multi-class probability estimates by coupling all pairwise classification results. Error correcting output codes (ECOC) are a general framework to decompose a multi-class problem to several binary problems. To obtain probability estimates under this framework, this paper introduces a generalized Bradley-Terry model in which paired individual comparisons are extended to paired team comparisons. We propose a simple algorithm with convergence proofs to solve the model and obtain individual skill. Experiments on synthetic and re al data demonstrate that the algorithm is useful for obtaining multi-class probability estimates. Moreover, we discuss four extensions of the proposed model: 1) weighted individual skill, 2) home-field advantage, 3) ties, and 4) comparisons with more than two teams.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {85–115},
numpages = {31}
}

@article{10.5555/1248547.1248550,
author = {Schmitt, Michael and Martignon, Laura},
title = {On the Complexity of Learning Lexicographic Strategies},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Fast and frugal heuristics are well studied models of bounded rationality. Psychological research has proposed the take-the-best heuristic as a successful strategy in decision making with limited resources. Take-the-best searches for a sufficiently good ordering of cues (or features) in a task where objects are to be compared lexicographically. We investigate the computational complexity of finding optimal cue permutations for lexicographic strategies and prove that the problem is NP-complete. It follows that no efficient (that is, polynomial-time) algorithm computes optimal solutions, unless P=NP. We further analyze the complexity of approximating optimal cue permutations for lexicographic strategies. We show that there is no efficient algorithm that approximates the optimum to within any constant factor, unless P=NP.The results have implications for the complexity of learning lexicographic strategies from examples. They show that learning them in polynomial time within the model of agnostic probably approximately correct (PAC) learning is impossible, unless RP=NP. We further consider greedy approaches for building lexicographic strategies and determine upper and lower bounds for the performance ratio of simple algorithms. Moreover, we present a greedy algorithm that performs provably better than take-the-best. Tight bounds on the sample complexity for learning lexicographic strategies are also given in this article.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {55–83},
numpages = {29}
}

@article{10.5555/1248547.1248549,
author = {Cesa-Bianchi, Nicol\`{o} and Gentile, Claudio and Zaniboni, Luca},
title = {Incremental Algorithms for Hierarchical Classification},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We study the problem of classifying data in a given taxonomy when classifications associated with multiple and/or partial paths are allowed. We introduce a new algorithm that incrementally learns a linear-threshold classifier for each node of the taxonomy. A hierarchical classification is obtained by evaluating the trained node classifiers in a top-down fashion. To evaluate classifiers in our multipath framework, we define a new hierarchical loss function, the H-loss, capturing the intuition that whenever a classification mistake is made on a node of the taxonomy, then no loss should be charged for any additional mistake occurring in the subtree of that node.Making no assumptions on the mechanism generating the data instances, and assuming a linear noise model for the labels, we bound the H-loss of our on-line algorithm in terms of the H-loss of a reference classifier knowing the true parameters of the label-generating process.We show that, in expectation, the excess cumulative H-loss grows at most logarithmically in the length of the data sequence. Furthermore, our analysis reveals the precise dependence of the rate of convergence on the eigenstructure of the data each node observes.Our theoretical results are complemented by a number of experiments on texual corpora. In these experiments we show that, after only one epoch of training, our algorithm performs much better than Perceptron-based hierarchical classifiers, and reasonably close to a hierarchical support vector machine.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {31–54},
numpages = {24}
}

@article{10.5555/1248547.1248548,
author = {Dem\v{s}ar, Janez},
title = {Statistical Comparisons of Classifiers over Multiple Data Sets},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {While methods for comparing two learning algorithms on a single data set have been scrutinized for quite some time already, the issue of statistical tests for comparisons of more algorithms on multiple data sets, which is even more essential to typical machine learning studies, has been all but ignored. This article reviews the current practice and then theoretically and empirically examines several suitable tests. Based on that, we recommend a set of simple, yet safe and robust non-parametric tests for statistical comparisons of classifiers: the Wilcoxon signed ranks test for comparison of two classifiers and the Friedman test with the corresponding post-hoc tests for comparison of more classifiers over multiple data sets. Results of the latter can also be neatly presented with the newly introduced CD (critical difference) diagrams.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1–30},
numpages = {30}
}

@article{10.5555/1046920.1194917,
author = {Opper, Manfred and Winther, Ole},
title = {Expectation Consistent Approximate Inference},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We propose a novel framework for approximations to intractable probabilistic models which is based on a free energy formulation. The approximation can be understood as replacing an average over the original intractable distribution with a tractable one. It requires two tractable probability distributions which are made consistent on a set of moments and encode different features of the original intractable distribution. In this way we are able to use Gaussian approximations for models with discrete or bounded variables which allow us to include non-trivial correlations. These are neglected in many other methods. We test the framework on toy benchmark problems for binary variables on fully connected graphs and 2D grids and compare with other methods, such as loopy belief propagation. Good performance is already achieved by using single nodes as tractable substructures. Significant improvements are obtained when a spanning tree is used instead.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2177–2204},
numpages = {28}
}

@article{10.5555/1046920.1194916,
author = {Drineas, Petros and Mahoney, Michael W.},
title = {On the Nystr\"{o}m Method for Approximating a Gram Matrix for Improved Kernel-Based Learning},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A problem for many kernel-based methods is that the amount of computation required to find the solution scales as O(n3), where n is the number of training examples. We develop and analyze an algorithm to compute an easily-interpretable low-rank approximation to an n \texttimes{} n Gram matrix G such that computations of interest may be performed more rapidly. The approximation is of the form ~Gk = CWk+CT, where C is a matrix consisting of a small number c of columns of G and Wk is the best rank-k approximation to W, the matrix formed by the intersection between those c columns of G and the corresponding c rows of G. An important aspect of the algorithm is the probability distribution used to randomly sample the columns; we will use a judiciously-chosen and data-dependent nonuniform probability distribution. Let ||·||2 and ||·||F denote the spectral norm and the Frobenius norm, respectively, of a matrix, and let Gk be the best rank-k approximation to G. We prove that by choosing O(k/ε4) columns||G-CWk+CT||ξ ≤ ||G-Gk||ξ + ε Σi=1n Gii2  ,both in expectation and with high probability, for both ξ = 2, F, and for all k: 0 ≤ k ≤ rank(W). This approximation can be computed using O(n) additional space and time, after making two passes over the data from external storage. The relationships between this algorithm, other related matrix decompositions, and the Nystr\"{o}m method from integral equation theory are discussed.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2153–2175},
numpages = {23}
}

@article{10.5555/1046920.1194915,
author = {R\"{a}tsch, Gunnar and Warmuth, Manfred K.},
title = {Efficient Margin Maximizing with Boosting},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {AdaBoost produces a linear combination of base hypotheses and predicts with the sign of this linear combination. The linear combination may be viewed as a hyperplane in feature space where the base hypotheses form the features. It has been observed that the generalization error of the algorithm continues to improve even after all examples are on the correct side of the current hyperplane. The improvement is attributed to the experimental observation that the distances (margins) of the examples to the separating hyperplane are increasing even after all examples are on the correct side.We introduce a new version of AdaBoost, called AdaBoost*ν, that explicitly maximizes the minimum margin of the examples up to a given precision. The algorithm incorporates a current estimate of the achievable margin into its calculation of the linear coefficients of the base hypotheses. The bound on the number of iterations needed by the new algorithms is the same as the number needed by a known version of AdaBoost that must have an explicit estimate of the achievable margin as a parameter. We also illustrate experimentally that our algorithm requires considerably fewer iterations than other algorithms that aim to maximize the margin.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2131–2152},
numpages = {22}
}

@article{10.5555/1046920.1194914,
author = {Gretton, Arthur and Herbrich, Ralf and Smola, Alexander and Bousquet, Olivier and Sch\"{o}lkopf, Bernhard},
title = {Kernel Methods for Measuring Independence},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We introduce two new functionals, the constrained covariance and the kernel mutual information, to measure the degree of independence of random variables. These quantities are both based on the covariance between functions of the random variables in reproducing kernel Hilbert spaces (RKHSs). We prove that when the RKHSs are universal, both functionals are zero if and only if the random variables are pairwise independent. We also show that the kernel mutual information is an upper bound near independence on the Parzen window estimate of the mutual information. Analogous results apply for two correlation-based dependence functionals introduced earlier: we show the kernel canonical correlation and the kernel generalised variance to be independence measures for universal kernels, and prove the latter to be an upper bound on the mutual information near independence. The performance of the kernel dependence functionals in measuring independence is verified in the context of independent component analysis.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2075–2129},
numpages = {55}
}

@article{10.5555/1046920.1194913,
author = {Gunawardana, Asela and Byrne, William},
title = {Convergence Theorems for Generalized Alternating Minimization Procedures},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {The EM algorithm is widely used to develop iterative parameter estimation procedures for statistical models. In cases where these procedures strictly follow the EM formulation, the convergence properties of the estimation procedures are well understood. In some instances there are practical reasons to develop procedures that do not strictly fall within the EM framework. We study EM variants in which the E-step is not performed exactly, either to obtain improved rates of convergence, or due to approximations needed to compute statistics under a model family over which E-steps cannot be realized. Since these variants are not EM procedures, the standard (G)EM convergence results do not apply to them. We present an information geometric framework for describing such algorithms and analyzing their convergence properties. We apply this framework to analyze the convergence properties of incremental EM and variational EM. For incremental EM, we discuss conditions under these algorithms converge in likelihood. For variational EM, we show how the E-step approximation prevents convergence to local maxima in likelihood.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2049–2073},
numpages = {25}
}

@article{10.5555/1046920.1194912,
author = {Mohammadi, Leila and van de Geer, Sara},
title = {Asymptotics in Empirical Risk Minimization},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {In this paper, we study a two-category classification problem. We indicate the categories by labels Y=1 and Y=-1. We observe a covariate, or feature, X ∈ X ⊂ ℜd. Consider a collection {ha} of classifiers indexed by a finite-dimensional parameter a, and the classifier ha* that minimizes the prediction error over this class. The parameter a* is estimated by the empirical risk minimizer \^{a}n over the class, where the empirical risk is calculated on a training sample of size n. We apply the Kim Pollard Theorem to show that

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr