text:
under certain differentiability assumptions, \^{a}n converges to a* with rate n-1/3, and also present the asymptotic distribution of the renormalized estimator.For example, let V0 denote the set of x on which, given X=x, the label Y=1 is more likely (than the label Y=-1). If X is one-dimensional, the set V0 is the union of disjoint intervals. The problem is then to estimate the thresholds of the intervals. We obtain the asymptotic distribution of the empirical risk minimizer when the classifiers have K thresholds, where K is fixed. We furthermore consider an extension to higher-dimensional X, assuming basically that V0 has a smooth boundary in some given parametric class.We also discuss various rates of convergence when the differentiability conditions are possibly violated. Here, we again restrict ourselves to one-dimensional X. We show that the rate is n-1 in certain cases, and then also obtain the asymptotic distribution for the empirical prediction error.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2027–2047},
numpages = {21}
}

@article{10.5555/1046920.1194911,
author = {Zoeter, Onno and Heskes, Tom},
title = {Change Point Problems in Linear Dynamical Systems},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We study the problem of learning two regimes (we have a normal and a prefault regime in mind) based on a train set of non-Markovian observation sequences. Key to the model is that we assume that once the system switches from the normal to the prefault regime it cannot restore and will eventually result in a fault. We refer to the particular setting as semi-supervised since we assume the only information given to the learner is whether a particular sequence ended with a stop (implying that the sequence was generated by the normal regime) or with a fault (implying that there was a switch from the normal to the fault regime). In the latter case the particular time point at which a switch occurred is not known.The underlying model used is a switching linear dynamical system (SLDS). The constraints in the regime transition probabilities result in an exact inference procedure that scales quadratically with the length of a sequence. Maximum aposteriori (MAP) parameter estimates can be found using an expectation maximization (EM) algorithm with this inference algorithm in the E-step. For long sequences this will not be practically feasible and an approximate inference and an approximate EM procedure is called for. We describe a flexible class of approximations corresponding to different choices of clusters in a Kikuchi free energy with weak consistency constraints.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1999–2026},
numpages = {28}
}

@article{10.5555/1046920.1194910,
author = {Wong, Weng-Keen and Moore, Andrew and Cooper, Gregory and Wagner, Michael},
title = {What's Strange About Recent Events (WSARE): An Algorithm for the Early Detection of Disease Outbreaks},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Traditional biosurveillance algorithms detect disease outbreaks by looking for peaks in a univariate time series of health-care data. Current health-care surveillance data, however, are no longer simply univariate data streams. Instead, a wealth of spatial, temporal, demographic and symptomatic information is available. We present an early disease outbreak detection algorithm called What's Strange About Recent Events (WSARE), which uses a multivariate approach to improve its timeliness of detection. WSARE employs a rule-based technique that compares recent health-care data against data from a baseline distribution and finds subgroups of the recent data whose proportions have changed the most from the baseline data. In addition, health-care data also pose difficulties for surveillance algorithms because of inherent temporal trends such as seasonal effects and day of week variations. WSARE approaches this problem using a Bayesian network to produce a baseline distribution that accounts for these temporal trends. The algorithm itself incorporates a wide range of ideas, including association rules, Bayesian networks, hypothesis testing and permutation tests to produce a detection algorithm that is careful to evaluate the significance of the alarms that it raises.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1961–1998},
numpages = {38}
}

@article{10.5555/1046920.1194909,
author = {Qui\~{n}onero-Candela, Joaquin and Rasmussen, Carl Edward},
title = {A Unifying View of Sparse Approximate Gaussian Process Regression},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We provide a new unifying view, including all existing proper probabilistic sparse approximations for Gaussian process regression. Our approach relies on expressing the effective prior which the methods are using. This allows new insights to be gained, and highlights the relationship between existing methods. It also allows for a clear theoretically justified ranking of the closeness of the known approximations to the corresponding full GPs. Finally we point directly to designs of new better sparse approximations, combining the best of the existing strategies, within attractive computational constraints.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1939–1959},
numpages = {21}
}

@article{10.5555/1046920.1194908,
author = {Goldsmith, Judy and Sloan, Robert H.},
title = {New Horn Revision Algorithms},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the measured resource) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give efficient revision algorithms in the model of learning with equivalence and membership queries. The algorithms work in a general revision model where both deletion and addition revision operators are allowed. In this model one of the main open problems is the efficient revision of Horn formulas. Two revision algorithms are presented for special cases of this problem: for depth-1 acyclic Horn formulas, and for definite Horn formulas with unique heads.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1919–1938},
numpages = {20}
}

@article{10.5555/1046920.1194907,
author = {Fan, Rong-En and Chen, Pai-Hsuen and Lin, Chih-Jen},
title = {Working Set Selection Using Second Order Information for Training Support Vector Machines},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Working set selection is an important step in decomposition methods for training support vector machines (SVMs). This paper develops a new technique for working set selection in SMO-type decomposition methods. It uses second order information to achieve fast convergence. Theoretical properties such as linear convergence are established. Experiments demonstrate that the proposed method is faster than existing selection methods using first order information.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1889–1918},
numpages = {30}
}

@article{10.5555/1046920.1194906,
author = {Wolf, Lior and Shashua, Amnon},
title = {Feature Selection for Unsupervised and Supervised Inference: The Emergence of Sparsity in a Weight-Based Approach},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {The problem of selecting a subset of relevant features in a potentially overwhelming quantity of data is classic and found in many branches of science. Examples in computer vision, text processing and more recently bio-informatics are abundant. In text classification tasks, for example, it is not uncommon to have 104 to 107 features of the size of the vocabulary containing word frequency counts, with the expectation that only a small fraction of them are relevant. Typical examples include the automatic sorting of URLs into a web directory and the detection of spam email.In this work we present a definition of "relevancy" based on spectral properties of the Laplacian of the features' measurement matrix. The feature selection process is then based on a continuous ranking of the features defined by a least-squares optimization process. A remarkable property of the feature relevance function is that sparse solutions for the ranking values naturally emerge as a result of a "biased non-negativity" of a key matrix in the process. As a result, a simple least-squares optimization process converges onto a sparse solution, i.e., a selection of a subset of features which form a local maximum over the relevance function. The feature selection algorithm can be embedded in both unsupervised and supervised inference problems and empirical evidence show that the feature selections typically achieve high accuracy even when only a small fraction of the features are relevant.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1855–1887},
numpages = {33}
}

@article{10.5555/1046920.1194905,
author = {Ando, Rie Kubota and Zhang, Tong},
title = {A Framework for Learning Predictive Structures from Multiple Tasks and Unlabeled Data},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {One of the most important issues in machine learning is whether one can improve the performance of a supervised learning algorithm by including unlabeled data. Methods that use both labeled and unlabeled data are generally referred to as semi-supervised learning. Although a number of such methods are proposed, at the current stage, we still don't have a complete understanding of their effectiveness. This paper investigates a closely related problem, which leads to a novel approach to semi-supervised learning. Specifically we consider learning predictive structures on hypothesis spaces (that is, what kind of classifiers have good predictive power) from multiple learning tasks. We present a general framework in which the structural learning problem can be formulated and analyzed theoretically, and relate it to learning with unlabeled data. Under this framework, algorithms for structural learning will be proposed, and computational issues will be investigated. Experiments will be given to demonstrate the effectiveness of the proposed algorithms in the semi-supervised learning setting.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1817–1853},
numpages = {37}
}

@article{10.5555/1046920.1194904,
author = {Lawrence, Neil},
title = {Probabilistic Non-Linear Principal Component Analysis with Gaussian Process Latent Variable Models},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Summarising a high dimensional data set with a low dimensional embedding is a standard approach for exploring its structure. In this paper we provide an overview of some existing techniques for discovering such embeddings. We then introduce a novel probabilistic interpretation of principal component analysis (PCA) that we term dual probabilistic PCA (DPPCA). The DPPCA model has the additional advantage that the linear mappings from the embedded space can easily be non-linearised through Gaussian processes. We refer to this model as a Gaussian process latent variable model (GP-LVM). Through analysis of the GP-LVM objective function, we relate the model to popular spectral techniques such as kernel PCA and multidimensional scaling. We then review a practical algorithm for GP-LVMs in the context of large data sets and develop it to also handle discrete valued data and missing attributes. We demonstrate the model on a range of real-world and artificially generated data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1783–1816},
numpages = {34}
}

@article{10.5555/1046920.1194903,
author = {Sigletos, Georgios and Paliouras, Georgios and Spyropoulos, Constantine D. and Hatzopoulos, Michalis},
title = {Combining Information Extraction Systems Using Voting and Stacked Generalization},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This article investigates the effectiveness of voting and stacked generalization -also known as stacking- in the context of information extraction (IE). A new stacking framework is proposed that accommodates well-known approaches for IE. The key idea is to perform cross-validation on the base-level data set, which consists of text documents annotated with relevant information, in order to create a meta-level data set that consists of feature vectors. A classifier is then trained using the new vectors. Therefore, base-level IE systems are combined with a common classifier at the meta-level. Various voting schemes are presented for comparing against stacking in various IE domains. Well known IE systems are employed at the base-level, together with a variety of classifiers at the meta-level. Results show that both voting and stacking work better when relying on probabilistic estimates by the base-level systems. Voting proved to be effective in most domains in the experiments. Stacking, on the other hand, proved to be consistently effective over all domains, doing comparably or better than voting and always better than the best base-level systems. Particular emphasis is also given to explaining the results obtained by voting and stacking at the meta-level, with respect to the varying degree of similarity in the output of the base-level systems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1751–1782},
numpages = {32}
}

@article{10.5555/1046920.1194902,
author = {Banerjee, Arindam and Merugu, Srujana and Dhillon, Inderjit S. and Ghosh, Joydeep},
title = {Clustering with Bregman Divergences},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A wide variety of distortion functions, such as squared Euclidean distance, Mahalanobis distance, Itakura-Saito distance and relative entropy, have been used for clustering. In this paper, we propose and analyze parametric hard and soft clustering algorithms based on a large class of distortion functions known as Bregman divergences. The proposed algorithms unify centroid-based parametric clustering approaches, such as classical <tt>kmeans</tt>, the Linde-Buzo-Gray (LBG) algorithm and information-theoretic clustering, which arise by special choices of the Bregman divergence. The algorithms maintain the simplicity and scalability of the classical <tt>kmeans</tt> algorithm, while generalizing the method to a large class of clustering loss functions. This is achieved by first posing the hard clustering problem in terms of minimizing the loss in Bregman information, a quantity motivated by rate distortion theory, and then deriving an iterative algorithm that monotonically decreases this loss. In addition, we show that there is a bijection between regular exponential families and a large class of Bregman divergences, that we call regular Bregman divergences. This result enables the development of an alternative interpretation of an efficient EM scheme for learning mixtures of exponential family distributions, and leads to a simple soft clustering algorithm for regular Bregman divergences. Finally, we discuss the connection between rate distortion theory and Bregman clustering and present an information theoretic analysis of Bregman clustering algorithms in terms of a trade-off between compression and loss in Bregman information.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1705–1749},
numpages = {45}
}

@article{10.5555/1046920.1194901,
author = {Kuss, Malte and Rasmussen, Carl Edward},
title = {Assessing Approximate Inference for Binary Gaussian Process Classification},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Gaussian process priors can be used to define flexible, probabilistic classification models. Unfortunately exact Bayesian inference is analytically intractable and various approximation techniques have been proposed. In this work we review and compare Laplace's method and Expectation Propagation for approximate Bayesian inference in the binary Gaussian process classification model. We present a comprehensive comparison of the approximations, their predictive performance and marginal likelihood estimates to results obtained by MCMC sampling. We explain theoretically and corroborate empirically the advantages of Expectation Propagation compared to Laplace's method.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1679–1704},
numpages = {26}
}

@article{10.5555/1046920.1194900,
author = {Bongard, Josh and Lipson, Hod},
title = {Active Coevolutionary Learning of Deterministic Finite Automata},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This paper describes an active learning approach to the problem of grammatical inference, specifically the inference of deterministic finite automata (DFAs). We refer to the algorithm as the estimation-exploration algorithm (EEA). This approach differs from previous passive and active learning approaches to grammatical inference in that training data is actively proposed by the algorithm, rather than passively receiving training data from some external teacher. Here we show that this algorithm outperforms one version of the most powerful set of algorithms for grammatical inference, evidence driven state merging (EDSM), on randomly-generated DFAs. The performance increase is due to the fact that the EDSM algorithm only works well for DFAs with specific balances (percentage of positive labelings), while the EEA is more consistent over a wider range of balances. Based on this finding we propose a more general method for generating DFAs to be used in the development of future grammatical inference algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1651–1678},
numpages = {28}
}

@article{10.5555/1046920.1194899,
author = {Brown, Gavin and Wyatt, Jeremy L. and Ti\v{n}o, Peter},
title = {Managing Diversity in Regression Ensembles},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Ensembles are a widely used and effective technique in machine learning---their success is commonly attributed to the degree of disagreement, or 'diversity', within the ensemble. For ensembles where the individual estimators output crisp class labels, this 'diversity' is not well understood and remains an open research issue. For ensembles of regression estimators, the diversity can be exactly formulated in terms of the covariance between individual estimator outputs, and the optimum level is expressed in terms of a bias-variance-covariance trade-off. Despite this, most approaches to learning ensembles use heuristics to encourage the right degree of diversity. In this work we show how to explicitly control diversity through the error function. The first contribution of this paper is to show that by taking the combination mechanism for the ensemble into account we can derive an error function for each individual that balances ensemble diversity with individual accuracy. We show the relationship between this error function and an existing algorithm called negative correlation learning, which uses a heuristic penalty term added to the mean squared error function. It is demonstrated that these methods control the bias-variance-covariance trade-off systematically, and can be utilised with any estimator capable of minimising a quadratic error function, for example MLPs, or RBF networks. As a second contribution, we derive a strict upper bound on the coefficient of the penalty term, which holds for any estimator that can be cast in a generalised linear regression framework, with mild assumptions on the basis functions. Finally we present the results of an empirical study, showing significant improvements over simple ensemble learning, and finding that this technique is competitive with a variety of methods, including boosting, bagging, mixtures of experts, and Gaussian processes, on a number of tasks.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1621–1650},
numpages = {30}
}

@article{10.5555/1046920.1194898,
author = {Bordes, Antoine and Ertekin, Seyda and Weston, Jason and Bottou, L\'{e}on},
title = {Fast Kernel Classifiers with Online and Active Learning},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Very high dimensional learning systems become theoretically possible when training examples are abundant. The computing cost then becomes the limiting factor. Any efficient learning algorithm should at least take a brief look at each example. But should all examples be given equal attention?This contribution proposes an empirical answer. We first present an online SVM algorithm based on this premise. LASVM yields competitive misclassification rates after a single pass over the training examples, outspeeding state-of-the-art SVM solvers. Then we show how active example selection can yield faster training, higher accuracies, and simpler models, using only a fraction of the training example labels.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1579–1619},
numpages = {41}
}

@article{10.5555/1046920.1194897,
author = {III, Hal Daum\'{e} and Marcu, Daniel},
title = {A Bayesian Model for Supervised Clustering with the Dirichlet Process Prior},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We develop a Bayesian framework for tackling the supervised clustering problem, the generic problem encountered in tasks such as reference matching, coreference resolution, identity uncertainty and record linkage. Our clustering model is based on the Dirichlet process prior, which enables us to define distributions over the countably infinite sets that naturally arise in this problem. We add supervision to our model by positing the existence of a set of unobserved random variables (we call these "reference types") that are generic across all clusters. Inference in our framework, which requires integrating over infinitely many parameters, is solved using Markov chain Monte Carlo techniques. We present algorithms for both conjugate and non-conjugate priors. We present a simple---but general---parameterization of our model based on a Gaussian assumption. We evaluate this model on one artificial task and three real-world tasks, comparing it against both unsupervised and state-of-the-art supervised algorithms. Our results show that our model is able to outperform other models across a variety of tasks and performance metrics.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1551–1577},
numpages = {27}
}

@article{10.5555/1046920.1194896,
author = {Cowell, Robert G.},
title = {Local Propagation in Conditional Gaussian Bayesian Networks},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This paper describes a scheme for local computation in conditional Gaussian Bayesian networks that combines the approach of Lauritzen and Jensen (2001) with some elements of Shachter and Kenley (1989). Message passing takes place on an elimination tree structure rather than the more compact (and usual) junction tree of cliques. This yields a local computation scheme in which all calculations involving the continuous variables are performed by manipulating univariate regressions, and hence matrix operations are avoided.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1517–1550},
numpages = {34}
}

@article{10.5555/1046920.1194895,
author = {Rakotomamonjy, Alain and Canu, St\'{e}phane},
title = {Frames, Reproducing Kernels, Regularization and Learning},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This work deals with a method for building a reproducing kernel Hilbert space (RKHS) from a Hilbert space with frame elements having special properties. Conditions on existence and a method of construction are given. Then, these RKHS are used within the framework of regularization theory for function approximation. Implications on semiparametric estimation are discussed and a multiscale scheme of regularization is also proposed. Results on toy and real-world approximation problems illustrate the effectiveness of such methods.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1485–1515},
numpages = {31}
}

@article{10.5555/1046920.1088722,
author = {Tsochantaridis, Ioannis and Joachims, Thorsten and Hofmann, Thomas and Altun, Yasemin},
title = {Large Margin Methods for Structured and Interdependent Output Variables},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Learning general functional dependencies between arbitrary input and output spaces is one of the key challenges in computational intelligence. While recent progress in machine learning has mainly focused on designing flexible and powerful input representations, this paper addresses the complementary issue of designing classification algorithms that can deal with more complex outputs, such as trees, sequences, or sets. More generally, we consider problems involving multiple dependent output variables, structured output spaces, and classification problems with class attributes. In order to accomplish this, we propose to appropriately generalize the well-known notion of a separation margin and derive a corresponding maximum-margin formulation. While this leads to a quadratic program with a potentially prohibitive, i.e. exponential, number of constraints, we present a cutting plane algorithm that solves the optimization problem in polynomial time for a large class of problems. The proposed method has important applications in areas such as computational biology, natural language processing, information retrieval/extraction, and optical character recognition. Experiments from various domains involving different types of output spaces emphasize the breadth and generality of our approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1453–1484},
numpages = {32}
}

@article{10.5555/1046920.1088721,
author = {Boull\'{e}, Marc},
title = {A Bayes Optimal Approach for Partitioning the Values of Categorical Attributes},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {In supervised machine learning, the partitioning of the values (also called grouping) of a categorical attribute aims at constructing a new synthetic attribute which keeps the information of the initial attribute and reduces the number of its values. In this paper, we propose a new grouping method MODL founded on a Bayesian approach. The method relies on a model space of grouping models and on a prior distribution defined on this model space. This results in an evaluation criterion of grouping, which is minimal for the most probable grouping given the data, i.e. the Bayes optimal grouping. We propose new super-linear optimization heuristics that yields near-optimal groupings. Extensive comparative experiments demonstrate that the MODL grouping method builds high quality groupings in terms of predictive quality, robustness and small number of groups.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1431–1452},
numpages = {22}
}

@article{10.5555/1046920.1088720,
author = {Khardon, Roni and Servedio, Rocco A.},
title = {Maximum Margin Algorithms with Boolean Kernels},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Recent work has introduced Boolean kernels with which one can learn linear threshold functions over a feature space containing all conjunctions of length up to k (for any 1 ≤ k ≤ n) over the original n Boolean features in the input space. This motivates the question of whether maximum margin algorithms such as Support Vector Machines can learn Disjunctive Normal Form expressions in the Probably Approximately Correct (PAC) learning model by using this kernel. We study this question, as well as a variant in which structural risk minimization (SRM) is performed where the class hierarchy is taken over the length of conjunctions.We show that maximum margin algorithms using the Boolean kernels do not PAC learn t(n)-term DNF for any t(n) = ω(1), even when used with such a SRM scheme. We also consider PAC learning under the uniform distribution and show that if the kernel uses conjunctions of length ˜ω(√n) then the maximum margin hypothesis will fail on the uniform distribution as well. Our results concretely illustrate that margin based algorithms may overfit when learning simple target functions with natural kernels.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1405–1429},
numpages = {25}
}

@article{10.5555/1046920.1088719,
author = {Nakamura, Atsuyoshi and Schmitt, Michael and Schmitt, Niels and Simon, Hans Ulrich},
title = {Inner Product Spaces for Bayesian Networks},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Bayesian networks have become one of the major models used for statistical inference. We study the question whether the decisions computed by a Bayesian network can be represented within a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. As main results we establish upper and lower bounds on the dimension of the inner product space for Bayesian networks with an explicitly given (full or reduced) parameter collection. In particular, these bounds are tight up to a factor of 2. For some nontrivial cases of Bayesian networks we even determine the exact values of this dimension. We further consider logistic autoregressive Bayesian networks and show that every sufficiently expressive inner product space must have dimension at least Ω(n2), where n is the number of network nodes. We also derive the bound 2Ω(n) for an artificial variant of this network, thereby demonstrating the limits of our approach and raising an interesting open question. As a major technical contribution, this work reveals combinatorial and algebraic structures within Bayesian networks such that known methods for the derivation of lower bounds on the dimension of inner product spaces can be brought into play.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1383–1403},
numpages = {21}
}

@article{10.5555/1046920.1088718,
author = {Banerjee, Arindam and Dhillon, Inderjit S. and Ghosh, Joydeep and Sra, Suvrit},
title = {Clustering on the Unit Hypersphere Using von Mises-Fisher Distributions},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Several large scale data mining applications, such as text categorization and gene expression analysis, involve high-dimensional data that is also inherently directional in nature. Often such data is L2 normalized so that it lies on the surface of a unit hypersphere. Popular models such as (mixtures of) multi-variate Gaussians are inadequate for characterizing such data. This paper proposes a generative mixture-model approach to clustering directional data based on the von Mises-Fisher (vMF) distribution, which arises naturally for data distributed on the unit hypersphere. In particular, we derive and analyze two variants of the Expectation Maximization (EM) framework for estimating the mean and concentration parameters of this mixture. Numerical estimation of the concentration parameters is non-trivial in high dimensions since it involves functional inversion of ratios of Bessel functions. We also formulate two clustering algorithms corresponding to the variants of EM that we derive. Our approach provides a theoretical basis for the use of cosine similarity that has been widely employed by the information retrieval community, and obtains the spherical kmeans algorithm (kmeans with cosine similarity) as a special case of both variants. Empirical results on clustering of high-dimensional text and gene-expression data based on a mixture of vMF distributions show that the ability to estimate the concentration parameter for each vMF component, which is not present in existing approaches, yields superior results, especially for difficult clustering tasks in high-dimensional spaces.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1345–1382},
numpages = {38}
}

@article{10.5555/1046920.1088717,
author = {Rousu, Juho and Shawe-Taylor, John},
title = {Efficient Computation of Gapped Substring Kernels on Large Alphabets},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We present a sparse dynamic programming algorithm that, given two strings s and t , a gap penalty λ, and an integer p, computes the value of the gap-weighted length-p subsequences kernel. The algorithm works in time O(p |M| log |t|), where M = {(i,j) | si = tj} is the set of matches of characters in the two sequences. The algorithm is easily adapted to handle bounded length subsequences and different gap-penalty schemes, including penalizing by the total length of gaps and the number of gaps as well as incorporating character-specific match/gap penalties.The new algorithm is empirically evaluated against a full dynamic programming approach and a trie-based algorithm both on synthetic and newswire article data. Based on the experiments, the full dynamic programming approach is the fastest on short strings, and on long strings if the alphabet is small. On large alphabets, the new sparse dynamic programming algorithm is the most efficient. On medium-sized alphabets the trie-based approach is best if the maximum number of allowed gaps is strongly restricted.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1323–1344},
numpages = {22}
}

@article{10.5555/1046920.1088716,
author = {Binev, Peter and Cohen, Albert and Dahmen, Wolfgang and DeVore, Ronald and Temlyakov, Vladimir},
title = {Universal Algorithms for Learning Theory Part I : Piecewise Constant Functions},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This paper is concerned with the construction and analysis of a universal estimator for the regression problem in supervised learning. Universal means that the estimator does not depend on any a priori assumptions about the regression function to be estimated. The universal estimator studied in this paper consists of a least-square fitting procedure using piecewise constant functions on a partition which depends adaptively on the data. The partition is generated by a splitting procedure which differs from those used in CART algorithms. It is proven that this estimator performs at the optimal convergence rate for a wide class of priors on the regression function. Namely, as will be made precise in the text, if the regression function is in any one of a certain class of approximation spaces (or smoothness spaces of order not exceeding one -- a limitation resulting because the estimator uses piecewise constants) measured relative to the marginal measure, then the estimator converges to the regression function (in the least squares sense) with an optimal rate of convergence in terms of the number of samples. The estimator is also numerically feasible and can be implemented on-line.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1297–1321},
numpages = {25}
}

@article{10.5555/1046920.1088715,
author = {Shani, Guy and Heckerman, David and Brafman, Ronen I.},
title = {An MDP-Based Recommender System},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Typical recommender systems adopt a static view of the recommendation process and treat it as a prediction problem. We argue that it is more appropriate to view the problem of generating recommendations as a sequential optimization problem and, consequently, that Markov decision processes (MDPs) provide a more appropriate model for recommender systems. MDPs introduce two benefits: they take into account the long-term effects of each recommendation and the expected value of each recommendation. To succeed in practice, an MDP-based recommender system must employ a strong initial model, must be solvable quickly, and should not consume too much memory. In this paper, we describe our particular MDP model, its initialization using a predictive model, the solution and update algorithm, and its actual performance on a commercial site. We also describe the particular predictive model we used which outperforms previous models. Our system is one of a small number of commercially deployed recommender systems. As far as we know, it is the first to report experimental analysis conducted on a real commercial site. These results validate the commercial value of recommender systems, and in particular, of our MDP-based approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1265–1295},
numpages = {31}
}

@article{10.5555/1046920.1088714,
author = {Drukh, Evgeny and Mansour, Yishay},
title = {Concentration Bounds for Unigram Language Models},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We show several high-probability concentration bounds for learning unigram language models. One interesting quantity is the probability of all words appearing exactly k times in a sample of size m. A standard estimator for this quantity is the Good-Turing estimator. The existing analysis on its error shows a high-probability bound of approximately O(k / m1/2). We improve its dependency on k to O(k1/4 / m1/2 + k / m). We also analyze the empirical frequencies estimator, showing that with high probability its error is bounded by approximately O( 1 / k + k1/2 / m). We derive a combined estimator, which has an error of approximately O(m-2/5), for any k.A standard measure for the quality of a learning algorithm is its expected per-word log-loss. The leave-one-out method can be used for estimating the log-loss of the unigram model. We show that its error has a high-probability bound of approximately O(1 / m1/2), for any underlying distribution.We also bound the log-loss a priori, as a function of various parameters of the distribution.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1231–1264},
numpages = {34}
}

@article{10.5555/1046920.1088713,
author = {Almeida, Lu\'{\i}s B.},
title = {Separating a Real-Life Nonlinear Image Mixture},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {When acquiring an image of a paper document, the image printed on the back page sometimes shows through. The mixture of the front- and back-page images thus obtained is markedly nonlinear, and thus constitutes a good real-life test case for nonlinear blind source separation.This paper addresses a difficult version of this problem, corresponding to the use of "onion skin" paper, which results in a relatively strong nonlinearity of the mixture, which becomes close to singular in the lighter regions of the images. The separation is achieved through the MISEP technique, which is an extension of the well known INFOMAX method. The separation results are assessed with objective quality measures. They show an improvement over the results obtained with linear separation, but have room for further improvement.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1199–1229},
numpages = {31}
}

@article{10.5555/1046920.1088712,
author = {Cuturi, Marco and Fukumizu, Kenji and Vert, Jean-Philippe},
title = {Semigroup Kernels on Measures},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We present a family of positive definite kernels on measures, characterized by the fact that the value of the kernel between two measures is a function of their sum. These kernels can be used to derive kernels on structured objects, such as images and texts, by representing these objects as sets of components, such as pixels or words, or more generally as measures on the space of components. Several kernels studied in this work make use of common quantities defined on measures such as entropy or generalized variance to detect similarities. Given an a priori kernel on the space of components itself, the approach is further extended by restating the previous results in a more efficient and flexible framework using the "kernel trick". Finally, a constructive approach to such positive definite kernels through an integral representation theorem is proved, before presenting experimental results on a benchmark experiment of handwritten digits classification to illustrate the validity of the approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1169–1198},
numpages = {30}
}

@article{10.5555/1046920.1088711,
author = {Markatou, Marianthi and Tian, Hong and Biswas, Shameek and Hripcsak, George},
title = {Analysis of Variance of Cross-Validation Estimators of the Generalization Error},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This paper brings together methods from two different disciplines: statistics and machine learning. We address the problem of estimating the variance of cross-validation (CV) estimators of the generalization error. In particular, we approach the problem of variance estimation of the CV estimators of generalization error as a problem in approximating the moments of a statistic. The approximation illustrates the role of training and test sets in the performance of the algorithm. It provides a unifying approach to evaluation of various methods used in obtaining training and test sets and it takes into account the variability due to different training and test sets. For the simple problem of predicting the sample mean and in the case of smooth loss functions, we show that the variance of the CV estimator of the generalization error is a function of the moments of the random variables Y=Card(Sj ∩ Sj') and Y*=Card(Sjc ∩ Sj'c), where Sj, Sj' are two training sets, and Sjc, Sj'c are the corresponding test sets. We prove that the distribution of Y and Y* is hypergeometric and we compare our estimator with the one proposed by Nadeau and Bengio (2003). We extend these results in the regression case and the case of absolute error loss, and indicate how the methods can be extended to the classification case. We illustrate the results through simulation.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1127–1168},
numpages = {42}
}

@article{10.5555/1046920.1088710,
author = {Micchelli, Charles A. and Pontil, Massimiliano},
title = {Learning the Kernel Function via Regularization},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We study the problem of finding an optimal kernel from a prescribed convex set of kernels K for learning a real-valued function by regularization. We establish for a wide variety of regularization functionals that this leads to a convex optimization problem and, for square loss regularization, we characterize the solution of this problem. We show that, although K may be an uncountable set, the optimal kernel is always obtained as a convex combination of at most m+2 basic kernels, where m is the number of data examples. In particular, our results apply to learning the optimal radial kernel or the optimal dot product kernel.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1099–1125},
numpages = {27}
}

@article{10.5555/1046920.1088709,
author = {Murphy, Susan A.},
title = {A Generalization Error for Q-Learning},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Planning problems that involve learning a policy from a single training set of finite horizon trajectories arise in both social science and medical fields. We consider Q-learning with function approximation for this setting and derive an upper bound on the generalization error. This upper bound is in terms of quantities minimized by a Q-learning algorithm, the complexity of the approximation space and an approximation term due to the mismatch between Q-learning and the goal of learning a policy that maximizes the value function.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1073–1097},
numpages = {25}
}

@article{10.5555/1046920.1088708,
author = {Ong, Cheng Soon and Smola, Alexander J. and Williamson, Robert C.},
title = {Learning the Kernel with Hyperkernels},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This paper addresses the problem of choosing a kernel suitable for estimation with a support vector machine, hence further automating machine learning. This goal is achieved by defining a reproducing kernel Hilbert space on the space of kernels itself. Such a formulation leads to a statistical estimation problem similar to the problem of minimizing a regularized risk functional.We state the equivalent representer theorem for the choice of kernels and present a semidefinite programming formulation of the resulting optimization problem. Several recipes for constructing hyperkernels are provided, as well as the details of common machine learning problems. Experimental results for classification, regression and novelty detection on UCI data show the feasibility of our approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1043–1071},
numpages = {29}
}

@article{10.5555/1046920.1088707,
author = {Chu, Wei and Ghahramani, Zoubin},
title = {Gaussian Processes for Ordinal Regression},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We present a probabilistic kernel approach to ordinal regression based on Gaussian processes. A threshold model that generalizes the probit function is used as the likelihood function for ordinal variables. Two inference techniques, based on the Laplace approximation and the expectation propagation algorithm respectively, are derived for hyperparameter learning and model selection. We compare these two Gaussian process approaches with a previous ordinal regression method based on support vector machines on some benchmark and real-world data sets, including applications of ordinal regression to collaborative filtering and gene expression analysis. Experimental results on these data sets verify the usefulness of our approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1019–1041},
numpages = {23}
}

@article{10.5555/1046920.1088706,
author = {Tsuda, Koji and R\"{a}tsch, Gunnar and Warmuth, Manfred K.},
title = {Matrix Exponentiated Gradient Updates for On-Line Learning and Bregman Projection},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We address the problem of learning a symmetric positive definite matrix. The central issue is to design parameter updates that preserve positive definiteness. Our updates are motivated with the von Neumann divergence. Rather than treating the most general case, we focus on two key applications that exemplify our methods: on-line learning with a simple square loss, and finding a symmetric positive definite matrix subject to linear constraints. The updates generalize the exponentiated gradient (EG) update and AdaBoost, respectively: the parameter is now a symmetric positive definite matrix of trace one instead of a probability vector (which in this context is a diagonal positive definite matrix with trace one). The generalized updates use matrix logarithms and exponentials to preserve positive definiteness. Most importantly, we show how the derivation and the analyses of the original EG update and AdaBoost generalize to the non-diagonal case. We apply the resulting matrix exponentiated gradient (MEG) update and DefiniteBoost to the problem of learning a kernel matrix from distance measurements.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {995–1018},
numpages = {24}
}

@article{10.5555/1046920.1088705,
author = {Maurer, Andreas},
title = {Algorithmic Stability and Meta-Learning},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A mechnism of transfer learning is analysed, where samples drawn from different learning tasks of an environment are used to improve the learners performance on a new task. We give a general method to prove generalisation error bounds for such meta-algorithms. The method can be applied to the bias learning model of J. Baxter and to derive novel generalisation bounds for meta-algorithms searching spaces of uniformly stable algorithms. We also present an application to regularized least squares regression.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {967–994},
numpages = {28}
}

@article{10.5555/1046920.1088704,
author = {Bar-Hillel, Aharon and Hertz, Tomer and Shental, Noam and Weinshall, Daphna},
title = {Learning a Mahalanobis Metric from Equivalence Constraints},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Many learning algorithms use a metric defined over the input space as a principal tool, and their performance critically depends on the quality of this metric. We address the problem of learning metrics using side-information in the form of equivalence constraints. Unlike labels, we demonstrate that this type of side-information can sometimes be automatically obtained without the need of human intervention. We show how such side-information can be used to modify the representation of the data, leading to improved clustering and classification.Specifically, we present the Relevant Component Analysis (RCA) algorithm, which is a simple and efficient algorithm for learning a Mahalanobis metric. We show that RCA is the solution of an interesting optimization problem, founded on an information theoretic basis. If dimensionality reduction is allowed within RCA, we show that it is optimally accomplished by a version of Fisher's linear discriminant that uses constraints. Moreover, under certain Gaussian assumptions, RCA can be viewed as a Maximum Likelihood estimation of the within class covariance matrix. We conclude with extensive empirical evaluations of RCA, showing its advantage over alternative methods.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {937–965},
numpages = {29}
}

@article{10.5555/1046920.1088703,
author = {Ihler, Alexander T. and Fischer III, John W. and Willsky, Alan S.},
title = {Loopy Belief Propagation: Convergence and Effects of Message Errors},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Belief propagation (BP) is an increasingly popular method of performing approximate inference on arbitrary graphical models. At times, even further approximations are required, whether due to quantization of the messages or model parameters, from other simplified message or model representations, or from stochastic approximation methods. The introduction of such errors into the BP message computations has the potential to affect the solution obtained adversely. We analyze the effect resulting from message approximation under two particular measures of error, and show bounds on the accumulation of errors in the system. This analysis leads to convergence conditions for traditional BP message passing, and both strict bounds and estimates of the resulting error in systems of approximate BP message passing.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {905–936},
numpages = {32}
}

@article{10.5555/1046920.1088702,
author = {Vito, Ernesto De and Rosasco, Lorenzo and Caponnetto, Andrea and Giovannini, Umberto De and Odone, Francesca},
title = {Learning from Examples as an Inverse Problem},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Many works related learning from examples to regularization techniques for inverse problems, emphasizing the strong algorithmic and conceptual analogy of certain learning algorithms with regularization algorithms. In particular it is well known that regularization schemes such as Tikhonov regularization can be effectively used in the context of learning and are closely related to algorithms such as support vector machines. Nevertheless the connection with inverse problem was considered only for the discrete (finite sample) problem and the probabilistic aspects of learning from examples were not taken into account. In this paper we provide a natural extension of such analysis to the continuous (population) case and study the interplay between the discrete and continuous problems. From a theoretical point of view, this allows to draw a clear connection between the consistency approach in learning theory and the stability convergence property in ill-posed inverse problems. The main mathematical result of the paper is a new probabilistic bound for the regularized least-squares algorithm. By means of standard results on the approximation term, the consistency of the algorithm easily follows.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {883–904},
numpages = {22}
}

@article{10.5555/1046920.1088701,
author = {Wingate, David and Seppi, Kevin D.},
title = {Prioritization Methods for Accelerating MDP Solvers},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {The performance of value and policy iteration can be dramatically improved by eliminating redundant or useless backups, and by backing up states in the right order. We study several methods designed to accelerate these iterative solvers, including prioritization, partitioning, and variable reordering. We generate a family of algorithms by combining several of the methods discussed, and present extensive empirical evidence demonstrating that performance can improve by several orders of magnitude for many problems, while preserving accuracy and convergence guarantees.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {851–881},
numpages = {31}
}

@article{10.5555/1046920.1088700,
author = {Aiolli, Fabio and Sperduti, Alessandro},
title = {Multiclass Classification with Multi-Prototype Support Vector Machines},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Winner-take-all multiclass classifiers are built on the top of a set of prototypes each representing one of the available classes. A pattern is then classified with the label associated to the most 'similar' prototype. Recent proposal of SVM extensions to multiclass can be considered instances of the same strategy with one prototype per class.The multi-prototype SVM proposed in this paper extends multiclass SVM to multiple prototypes per class. It allows to combine several vectors in a principled way to obtain large margin decision functions. For this problem, we give a compact constrained quadratic formulation and we propose a greedy optimization algorithm able to find locally optimal solutions for the non convex objective function.This algorithm proceeds by reducing the overall problem into a series of simpler convex problems. For the solution of these reduced problems an efficient optimization algorithm is proposed. A number of pattern selection strategies are then discussed to speed-up the optimization process. In addition, given the combinatorial nature of the overall problem, stochastic search strategies are suggested to escape from local minima which are not globally optimal.Finally, we report experiments on a number of datasets. The performance obtained using few simple linear prototypes is comparable to that obtained by state-of-the-art kernel-based methods but with a significant reduction (of one or two orders) in response time.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {817–850},
numpages = {34}
}

@article{10.5555/1046920.1088699,
author = {Murray, Joseph F. and Hughes, Gordon F. and Kreutz-Delgado, Kenneth},
title = {Machine Learning Methods for Predicting Failures in Hard Drives: A Multiple-Instance Application},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We compare machine learning methods applied to a difficult real-world problem: predicting computer hard-drive failure using attributes monitored internally by individual drives. The problem is one of detecting rare events in a time series of noisy and nonparametrically-distributed data. We develop a new algorithm based on the multiple-instance learning framework and the naive Bayesian classifier (mi-NB) which is specifically designed for the low false-alarm case, and is shown to have promising performance. Other methods compared are support vector machines (SVMs), unsupervised clustering, and non-parametric statistical tests (rank-sum and reverse arrangements). The failure-prediction performance of the SVM, rank-sum and mi-NB algorithm is considerably better than the threshold method currently implemented in drives, while maintaining low false alarm rates. Our results suggest that nonparametric statistical tests should be considered for learning problems involving detecting rare events in time series data. An appendix details the calculation of rank-sum significance probabilities in the case of discrete, tied observations, and we give new recommendations about when the exact calculation should be used instead of the commonly-used normal approximation. These normal approximations may be particularly inaccurate for rare event problems like hard drive failures.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {783–816},
numpages = {34}
}

@article{10.5555/1046920.1088698,
author = {Fiori, Simone},
title = {Quasi-Geodesic Neural Learning Algorithms Over the Orthogonal Group: A Tutorial},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {The aim of this contribution is to present a tutorial on learning algorithms for a single neural layer whose connection matrix belongs to the orthogonal group. The algorithms exploit geodesics appropriately connected as piece-wise approximate integrals of the exact differential learning equation. The considered learning equations essentially arise from the Riemannian-gradient-based optimization theory with deterministic and diffusion-type gradient. The paper aims specifically at reviewing the relevant mathematics (and at presenting it in as much transparent way as possible in order to make it accessible to readers that do not possess a background in differential geometry), at bringing together modern optimization methods on manifolds and at comparing the different algorithms on a common machine learning problem. As a numerical case-study, we consider an application to non-negative independent component analysis, although it should be recognized that Riemannian gradient methods give rise to general-purpose algorithms, by no means limited to ICA-related applications.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {743–781},
numpages = {39}
}

@article{10.5555/1046920.1088697,
author = {Dekel, Ofer and Shalev-Shwartz, Shai and Singer, Yoram},
title = {Smooth ε-Insensitive Regression by Loss Symmetrization},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We describe new loss functions for regression problems along with an accompanying algorithmic framework which utilizes these functions. These loss functions are derived by symmetrization of margin-based losses commonly used in boosting algorithms, namely, the logistic loss and the exponential loss. The resulting symmetric logistic loss can be viewed as a smooth approximation to the ε-insensitive hinge loss used in support vector regression. We describe and analyze two parametric families of batch learning algorithms for minimizing these symmetric losses. The first family employs an iterative log-additive update which can be viewed as a regression counterpart to recent boosting algorithms. The second family utilizes an iterative additive update step. We also describe and analyze online gradient descent (GD) and exponentiated gradient (EG) algorithms for the symmetric logistic loss. A byproduct of our work is a new simple form of regularization for boosting-based classification and regression algorithms. Our regression framework also has implications on classification algorithms, namely, a new additive update boosting algorithm for classification. We demonstrate the merits of our algorithms in a series of experiments.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {711–741},
numpages = {31}
}

@article{10.5555/1046920.1088696,
author = {Hyv\"{a}rinen, Aapo},
title = {Estimation of Non-Normalized Statistical Models by Score Matching},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {One often wants to estimate statistical models where the probability density function is known only up to a multiplicative normalization constant. Typically, one then has to resort to Markov Chain Monte Carlo methods, or approximations of the normalization constant. Here, we propose that such models can be estimated by minimizing the expected squared distance between the gradient of the log-density given by the model and the gradient of the log-density of the observed data. While the estimation of the gradient of log-density function is, in principle, a very difficult non-parametric problem, we prove a surprising result that gives a simple formula for this objective function. The density function of the observed data does not appear in this formula, which simplifies to a sample average of a sum of some derivatives of the log-density given by the model. The validity of the method is demonstrated on multivariate Gaussian and independent component analysis models, and by estimating an overcomplete filter set for natural image data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {695–709},
numpages = {15}
}

@article{10.5555/1046920.1088695,
author = {Winn, John and Bishop, Christopher M.},
title = {Variational Message Passing},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Bayesian inference is now widely established as one of the principal foundations for machine learning. In practice, exact inference is rarely possible, and so a variety of approximation techniques have been developed, one of the most widely used being a deterministic framework called variational inference. In this paper we introduce Variational Message Passing (VMP), a general purpose algorithm for applying variational inference to Bayesian Networks. Like belief propagation, VMP proceeds by sending messages between nodes in the network and updating posterior beliefs using local operations at each node. Each such update increases a lower bound on the log evidence (unless already at a local maximum). In contrast to belief propagation, VMP can be applied to a very general class of conjugate-exponential models because it uses a factorised variational approximation. Furthermore, by introducing additional variational parameters, VMP can be applied to models containing non-conjugate distributions. The VMP framework also allows the lower bound to be evaluated, and this can be used both for model comparison and for detection of convergence. Variational message passing has been implemented in the form of a general purpose inference engine called VIBES ('Variational Inference for BayEsian networkS') which allows models to be specified graphically and then solved variationally without recourse to coding.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {661–694},
numpages = {34}
}

@article{10.5555/1046920.1088694,
author = {Hutter, Marcus and Poland, Jan},
title = {Adaptive Online Prediction by Following the Perturbed Leader},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {When applying aggregating strategies to Prediction with Expert Advice (PEA), the learning rate must be adaptively tuned. The natural choice of sqrt(complexity/current loss) renders the analysis of Weighted Majority (WM) derivatives quite complicated. In particular, for arbitrary weights there have been no results proven so far. The analysis of the alternative Follow the Perturbed Leader (FPL) algorithm from Kalai and Vempala (2003) based on Hannan's algorithm is easier. We derive loss bounds for adaptive learning rate and both finite expert classes with uniform weights and countable expert classes with arbitrary weights. For the former setup, our loss bounds match the best known results so far, while for the latter our results are new.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {639–660},
numpages = {22}
}

@article{10.5555/1046920.1088693,
author = {Evgeniou, Theodoros and Micchelli, Charles A. and Pontil, Massimiliano},
title = {Learning Multiple Tasks with Kernel Methods},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We study the problem of learning many related tasks simultaneously using kernel methods and regularization. The standard single-task kernel methods, such as support vector machines and regularization networks, are extended to the case of multi-task learning. Our analysis shows that the problem of estimating many task functions with regularization can be cast as a single task learning problem if a family of multi-task kernel functions we define is used. These kernels model relations among the tasks and are derived from a novel form of regularizers. Specific kernels that can be used for multi-task learning are provided and experimentally tested on two real data sets. In agreement with past empirical work on multi-task learning, the experiments show that learning multiple related tasks simultaneously using the proposed approach can significantly outperform standard single-task learning particularly when there are many related tasks but few data per task.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {615–637},
numpages = {23}
}

@article{10.5555/1046920.1088692,
author = {Luo, Tong and Kramer, Kurt and Goldgof, Dmitry B. and Hall, Lawrence O. and Samson, Scott and Remsen, Andrew and Hopkins, Thomas},
title = {Active Learning to Recognize Multiple Types of Plankton},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This paper presents an active learning method which reduces the labeling effort of domain experts in multi-class classification problems. Active learning is applied in conjunction with support vector machines to recognize underwater zooplankton from higher-resolution, new generation SIPPER II images. Most previous work on active learning with support vector machines only deals with two class problems. In this paper, we propose an active learning approach "breaking ties" for multi-class support vector machines using the one-vs-one approach with a probability approximation. Experimental results indicate that our approach often requires significantly less labeled images to reach a given accuracy than the approach of labeling the least certain test example and random sampling. It can also be applied in batch mode resulting in an accuracy comparable to labeling one image at a time and retraining.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {589–613},
numpages = {25}
}

@article{10.5555/1046920.1088691,
author = {Segal, Eran and Pe'er, Dana and Regev, Aviv and Koller, Daphne and Friedman, Nir},
title = {Learning Module Networks},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Methods for learning Bayesian networks can discover dependency structure between observed variables. Although these methods are useful in many applications, they run into computational and statistical problems in domains that involve a large number of variables. In this paper, we consider a solution that is applicable when many variables have similar behavior. We introduce a new class of models, module networks, that explicitly partition the variables into modules, so that the variables in each module share the same parents in the network and the same conditional probability distribution. We define the semantics of module networks, and describe an algorithm that learns the modules' composition and their dependency structure from data. Evaluation on real data in the domains of gene expression and the stock market shows that module networks generalize better than Bayesian networks, and that the learned module network structure reveals regularities that are obscured in learned Bayesian networks.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {557–588},
numpages = {32}
}

@article{10.5555/1046920.1088690,
author = {Ernst, Damien and Geurts, Pierre and Wehenkel, Louis},
title = {Tree-Based Batch Mode Reinforcement Learning},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Reinforcement learning aims to determine an optimal control policy from interaction with a system or from observations gathered from a system. In batch mode, it can be achieved by approximating the so-called Q-function based on a set of four-tuples (xt, ut , rt, xt+1) where xt denotes the system state at time t, ut the control action taken, rt the instantaneous reward obtained and xt+1 the successor state of the system, and by determining the control policy from this Q-function. The Q-function approximation may be obtained from the limit of a sequence of (batch mode) supervised learning problems. Within this framework we describe the use of several classical tree-based supervised learning methods (CART, Kd-tree, tree bagging) and two newly proposed ensemble algorithms, namely extremely and totally randomized trees. We study their performances on several examples and find that the ensemble methods based on regression trees perform well in extracting relevant information about the optimal control policy from sets of four-tuples. In particular, the totally randomized trees give good results while ensuring the convergence of the sequence, whereas by relaxing the convergence constraint even better accuracy results are provided by the extremely randomized trees.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {503–556},
numpages = {54}
}

@article{10.5555/1046920.1088689,
author = {Ye, Jieping},
title = {Characterization of a Family of Algorithms for Generalized Discriminant Analysis on Undersampled Problems},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A generalized discriminant analysis based on a new optimization criterion is presented. The criterion extends the optimization criteria of the classical Linear Discriminant Analysis (LDA) when the scatter matrices are singular. An efficient algorithm for the new optimization problem is presented.The solutions to the proposed criterion form a family of algorithms for generalized LDA, which can be characterized in a closed form. We study two specific algorithms, namely Uncorrelated LDA (ULDA) and Orthogonal LDA (OLDA). ULDA was previously proposed for feature extraction and dimension reduction, whereas OLDA is a novel algorithm proposed in this paper. The features in the reduced space of ULDA are uncorrelated, while the discriminant vectors of OLDA are orthogonal to each other. We have conducted a comparative study on a variety of real-world data sets to evaluate ULDA and OLDA in terms of classification accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {483–502},
numpages = {20}
}

@article{10.5555/1046920.1088687,
author = {Marchand, Mario and Sokolova, Marina},
title = {Learning with Decision Lists of Data-Dependent Features},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We present a learning algorithm for decision lists which allows features that are constructed from the data and allows a trade-off between accuracy and complexity. We provide bounds on the generalization error of this learning algorithm in terms of the number of errors and the size of the classifier it finds on the training data. We also compare its performance on some natural data sets with the set covering machine and the support vector machine. Furthermore, we show that the proposed bounds on the generalization error provide effective guides for model selection.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {427–451},
numpages = {25}
}

@article{10.5555/1046920.1088686,
author = {Agarwal, Shivani and Graepel, Thore and Herbrich, Ralf and Har-Peled, Sariel and Roth, Dan},
title = {Generalization Bounds for the Area Under the ROC Curve},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We study generalization properties of the area under the ROC curve (AUC), a quantity that has been advocated as an evaluation criterion for the bipartite ranking problem.The AUC is a different term than the error rate used for evaluation in classification problems; consequently, existing generalization bounds for the classification error rate cannot be used to draw conclusions about the AUC.In this paper, we define the expected accuracy of a ranking function (analogous to the expected error rate of a classification function), and derive distribution-free probabilistic bounds on the deviation of the empirical AUC of a ranking function (observed on a finite data sequence) from its expected accuracy.We derive both a large deviation bound, which serves to bound the expected accuracy of a ranking function in terms of its empirical AUC on a test sequence, and a uniform convergence bound, which serves to bound the expected accuracy of a learned ranking function in terms of its empirical AUC on a training sequence.Our uniform convergence bound is expressed in terms of a new set of combinatorial parameters that we term the bipartite rank-shatter coefficients; these play the same role in our result as do the standard VC-dimension related shatter coefficients (also known as the growth function) in uniform convergence results for the classification error rate. A comparison of our result with a recent uniform convergence result derived by Freund et al. (2003) for a quantity closely related to the AUC shows that the bound provided by our result can be considerably tighter.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {393–425},
numpages = {33}
}

@article{10.5555/1046920.1088684,
author = {Keerthi, S. Sathiya and DeCoste, Dennis},
title = {A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {This paper develops a fast method for solving linear SVMs with L2 loss function that is suited for large scale data mining tasks such as text classification. This is done by modifying the finite Newton method of Mangasarian in several ways. Experiments indicate that the method is much faster than decomposition methods such as SVMlight, SMO and BSVM (e.g., 4-100 fold), especially when the number of examples is large. The paper also suggests ways of extending the method to other loss functions such as the modified Huber's loss function and the L1 loss function, and also for solving ordinal regression.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {341–361},
numpages = {21}
}

@article{10.5555/1046920.1088683,
author = {Jaeger, Savina Andonova},
title = {Generalization Bounds and Complexities Based on Sparsity and Clustering for Convex Combinations of Functions from Random Classes},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A unified approach is taken for deriving new generalization data dependent bounds for several classes of algorithms explored in the existing literature by different approaches. This unified approach is based on an extension of Vapnik's inequality for VC classes of sets to random classes of sets - that is, classes depending on the random data, invariant under permutation of the data and possessing the increasing property.Generalization bounds are derived for convex combinations of functions from random classes with certain properties. Algorithms, such as SVMs (support vector machines), boosting with decision stumps, radial basis function networks, some hierarchies of kernel machines or convex combinations of indicator functions over sets with finite VC dimension, generate classifier functions that fall into the above category. We also explore the individual complexities of the classifiers, such as sparsity of weights and weighted variance over clusters from the convex combination introduced by Koltchinskii and Panchenko (2004), and show sparsity-type and cluster-variance-type generalization bounds for random classes.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {307–340},
numpages = {34}
}

@article{10.5555/1046920.1088679,
author = {Eibl, G\"{u}nther and Pfeiffer, Karl-Peter},
title = {Multiclass Boosting for Weak Classifiers},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {AdaBoost.M2 is a boosting algorithm designed for multiclass problems with weak base classifiers. The algorithm is designed to minimize a very loose bound on the training error. We propose two alternative boosting algorithms which also minimize bounds on performance measures. These performance measures are not as strongly connected to the expected error as the training error, but the derived bounds are tighter than the bound on the training error of AdaBoost.M2. In experiments the methods have roughly the same performance in minimizing the training and test error rates. The new algorithms have the advantage that the base classifier should minimize the confidence-rated error, whereas for AdaBoost.M2 the base classifier should minimize the pseudo-loss. This makes them more easily applicable to already existing base classifiers. The new algorithms also tend to converge faster than AdaBoost.M2.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {189–210},
numpages = {22}
}

@article{10.5555/1046920.1058117,
author = {Kawanabe, Motoaki and M\"{u}ller, Klaus-Robert},
title = {Estimating Functions for Blind Separation When Sources Have Variance Dependencies},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A blind separation problem where the sources are not independent, but have variance dependencies is discussed. For this scenario Hyv\"{a}rinen and Hurri (2004) proposed an algorithm which requires no assumption on distributions of sources and no parametric model of dependencies between components. In this paper, we extend the semiparametric approach of Amari and Cardoso (1997) to variance dependencies and study estimating functions for blind separation of such dependent sources. In particular, we show that many ICA algorithms are applicable to the variance-dependent model as well under mild conditions, although they should in principle not. Our results indicate that separation can be done based only on normalized sources which are adjusted to have stationary variances and is not affected by the dependent activity levels. We also study the asymptotic distribution of the quasi maximum likelihood method and the stability of the natural gradient learning in detail. Simulation results of artificial and realistic examples match well with our theoretical findings.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {453–482},
numpages = {30}
}

@article{10.5555/1046920.1058114,
author = {Tsang, Ivor W. and Kwok, James T. and Cheung, Pak-Ming},
title = {Core Vector Machines: Fast SVM Training on Very Large Data Sets},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Standard SVM training has O(m3) time and O(m2) space complexities, where m is the training set size. It is thus computationally infeasible on very large data sets. By observing that practical SVM implementations only approximate the optimal solution by an iterative strategy, we scale up kernel methods by exploiting such "approximateness" in this paper. We first show that many kernel methods can be equivalently formulated as minimum enclosing ball (MEB) problems in computational geometry. Then, by adopting an efficient approximate MEB algorithm, we obtain provably approximately optimal solutions with the idea of core sets. Our proposed Core Vector Machine (CVM) algorithm can be used with nonlinear kernels and has a time complexity that is linear in m and a space complexity that is independent of m. Experiments on large toy and real-world data sets demonstrate that the CVM is as accurate as existing SVM implementations, but is much faster and can handle much larger data sets than existing scale-up methods. For example, CVM with the Gaussian kernel produces superior results on the KDDCUP-99 intrusion detection data, which has about five million training patterns, in only 1.4 seconds on a 3.2GHz Pentium--4 PC.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {363–392},
numpages = {30}
}

@article{10.5555/1046920.1058111,
author = {Langford, John},
title = {Tutorial on Practical Prediction Theory for Classification},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We discuss basic prediction theory and its impact on classification success evaluation, implications for learning algorithm design, and uses in learning algorithm execution. This tutorial is meant to be a comprehensive compilation of results which are both theoretically rigorous and quantitatively useful.There are two important implications of the results presented here. The first is that common practices for reporting results in classification should change to use the test set bound. The second is that train set bounds can sometimes be used to directly motivate learning algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {273–306},
numpages = {34}
}

@article{10.5555/1046920.1058110,
author = {S\"{a}rel\"{a}, Jaakko and Valpola, Harri},
title = {Denoising Source Separation},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A new algorithmic framework called denoising source separation (DSS) is introduced. The main benefit of this framework is that it allows for the easy development of new source separation algorithms which can be optimised for specific problems. In this framework, source separation algorithms are constructed around denoising procedures. The resulting algorithms can range from almost blind to highly specialised source separation algorithms. Both simple linear and more complex nonlinear or adaptive denoising schemes are considered. Some existing independent component analysis algorithms are reinterpreted within the DSS framework and new, robust blind source separation algorithms are suggested. The framework is derived as a one-unit equivalent to an EM algorithm for source separation. However, in the DSS framework it is easy to utilise various kinds of denoising procedures which need not be based on generative models.In the experimental section, various DSS schemes are applied extensively to artificial data, to real magnetoencephalograms and to simulated CDMA mobile network signals. Finally, various extensions to the proposed DSS algorithms are considered. These include nonlinear observation mappings, hierarchical models and over-complete, nonorthogonal feature spaces. With these extensions, DSS appears to have relevance to many existing models of neural information processing.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {233–272},
numpages = {40}
}

@article{10.5555/1046920.1058109,
author = {Steinwart, Ingo and Hush, Don and Scovel, Clint},
title = {A Classification Framework for Anomaly Detection},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {One way to describe anomalies is by saying that anomalies are not concentrated. This leads to the problem of finding level sets for the data generating density. We interpret this learning problem as a binary classification problem and compare the corresponding classification risk with the standard performance measure for the density level problem. In particular it turns out that the empirical classification risk can serve as an empirical performance measure for the anomaly detection problem. This allows us to compare different anomaly detection algorithms empirically, i.e. with the help of a test set. Furthermore, by the above interpretation we can give a strong justification for the well-known heuristic of artificially sampling "labeled" samples, provided that the sampling plan is well chosen. In particular this enables us to propose a support vector machine (SVM) for anomaly detection for which we can easily establish universal consistency. Finally, we report some experiments which compare our SVM to other commonly used methods including the standard one-class SVM.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {211–232},
numpages = {22}
}

@article{10.5555/1046920.1046926,
author = {Chechik, Gal and Globerson, Amir and Tishby, Naftali and Weiss, Yair},
title = {Information Bottleneck for Gaussian Variables},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {The problem of extracting the relevant aspects of data was previously addressed through the  information bottleneck  (IB) method, through (soft) clustering one variable while preserving information about another -  relevance  - variable. The current work extends these ideas to obtain continuous representations that preserve relevant information, rather than discrete clusters, for the special case of multivariate Gaussian variables. While the general continuous IB problem is difficult to solve, we provide an analytic solution for the optimal representation and tradeoff between compression and relevance for the this important case. The obtained optimal representation is a noisy linear projection to eigenvectors of the normalized regression matrix Σx|yΣx-1, which is also the basis obtained in canonical correlation analysis. However, in Gaussian IB, the compression tradeoff parameter uniquely determines the dimension, as well as the scale of each eigenvector, through a cascade of structural phase transitions. This introduces a novel interpretation where solutions of different ranks lie on a continuum parametrized by the compression level. Our analysis also provides a complete analytic expression of the preserved information as a function of the compression (the "information-curve"), in terms of the eigenvalue spectrum of the data. As in the discrete case, the information curve is concave and smooth, though it is made of different analytic segments for each optimal dimension. Finally, we show how the algorithmic theory developed in the IB framework provides an iterative algorithm for obtaining the optimal Gaussian projections.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {165–188},
numpages = {24}
}

@article{10.5555/1046920.1046925,
author = {Lafferty, John and Lebanon, Guy},
title = {Diffusion Kernels on Statistical Manifolds},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A family of kernels for statistical learning is introduced that exploits the geometric structure of statistical models. The kernels are based on the heat equation on the Riemannian manifold defined by the Fisher information metric associated with a statistical family, and generalize the Gaussian kernel of Euclidean space. As an important special case, kernels based on the geometry of multinomial families are derived, leading to kernel-based learning algorithms that apply naturally to discrete data. Bounds on covering numbers and Rademacher averages for the kernels are proved using bounds on the eigenvalues of the Laplacian on Riemannian manifolds. Experimental results are presented for document classification, for which the use of multinomial geometry is natural and well motivated, and improvements are obtained over the standard use of Gaussian or linear kernels, which have been the standard for text classification.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {129–163},
numpages = {35}
}

@article{10.5555/1046920.1046924,
author = {Elidan, Gal and Friedman, Nir},
title = {Learning Hidden Variable Networks: The Information Bottleneck Approach},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {A central challenge in learning probabilistic graphical models is dealing with domains that involve hidden variables. The common approach for learning model parameters in such domains is the expectation maximization (EM) algorithm. This algorithm, however, can easily get trapped in sub-optimal local maxima. Learning the model structure is even more challenging. The structural EM algorithm can adapt the structure in the presence of hidden variables, but usually performs poorly without prior knowledge about the cardinality and location of the hidden variables. In this work, we present a general approach for learning Bayesian networks with hidden variables that overcomes these problems. The approach builds on the information bottleneck framework of Tishby et al. (1999). We start by proving formal correspondence between the information bottleneck objective and the standard parametric EM functional. We then use this correspondence to construct a learning algorithm that combines an information-theoretic smoothing term with a continuation procedure. Intuitively, the algorithm bypasses local maxima and achieves superior solutions by following a continuous path from a solution of, an easy and smooth, target function, to a solution of the desired likelihood function. As we show, our algorithmic framework allows learning of the parameters as well as the structure of a network. In addition, it also allows us to introduce new hidden variables during model selection and learn their cardinality. We demonstrate the performance of our procedure on several challenging real-life data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {81–127},
numpages = {47}
}

@article{10.5555/1046920.1046923,
author = {Elisseeff, Andre and Evgeniou, Theodoros and Pontil, Massimiliano},
title = {Stability of Randomized Learning Algorithms},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We extend existing theory on stability, namely how much changes in the training data influence the estimated models, and generalization performance of deterministic learning algorithms to the case of randomized algorithms. We give formal definitions of stability for randomized algorithms and prove non-asymptotic bounds on the difference between the empirical and expected error as well as the leave-one-out and expected error of such algorithms that depend on their random stability. The setup we develop for this purpose can be also used for generally studying randomized learning algorithms. We then use these general results to study the effects of bagging on the stability of a learning method and to prove non-asymptotic bounds on the predictive performance of bagging which have not been possible to prove with the existing theory of stability for deterministic learning algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {55–79},
numpages = {25}
}

@article{10.5555/1046920.1046922,
author = {Kim, Hyunsoo and Howland, Peg and Park, Haesun},
title = {Dimension Reduction in Text Classification with Support Vector Machines},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {Support vector machines (SVMs) have been recognized as one of the most successful classification methods for many applications including text classification. Even though the learning ability and computational complexity of training in support vector machines may be independent of the dimension of the feature space, reducing computational complexity is an essential issue to efficiently handle a large number of terms in practical applications of text classification. In this paper, we adopt novel dimension reduction methods to reduce the dimension of the document vectors dramatically. We also introduce decision functions for the centroid-based classification algorithm and support vector classifiers to handle the classification problem where a document may belong to multiple classes. Our substantial experimental results show that with several dimension reduction methods that are designed particularly for clustered data, higher efficiency for both training and testing can be achieved without sacrificing prediction accuracy of text classification even when the dimension of the input space is significantly reduced.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {37–53},
numpages = {17}
}

@article{10.5555/1046920.1046921,
author = {Rusakov, Dmitry and Geiger, Dan},
title = {Asymptotic Model Selection for Naive Bayesian Networks},
year = {2005},
issue_date = {12/1/2005},
publisher = {JMLR.org},
volume = {6},
issn = {1532-4435},
abstract = {We develop a closed form asymptotic formula to compute the marginal likelihood of data given a naive Bayesian network model with two hidden states and binary features. This formula deviates from the standard BIC score. Our work provides a concrete example that the BIC score is generally incorrect for statistical models that belong to stratified exponential families. This claim stands in contrast to linear and curved exponential families, where the BIC score has been proven to provide a correct asymptotic approximation for the marginal likelihood.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1–35},
numpages = {35}
}

@article{10.5555/1005332.1044712,
author = {Rudin, Cynthia and Daubechies, Ingrid and Schapire, Robert E.},
title = {The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach allows us to understand AdaBoost's convergence properties completely in certain cases; for these cases we find stable cycles, allowing us to explicitly solve for AdaBoost's output.Using this unusual technique, we are able to show that AdaBoost does not always converge to a maximum margin combined classifier, answering an open question. In addition, we show that "non-optimal" AdaBoost (where the weak learning algorithm does not necessarily choose the best weak classifier at each iteration) may fail to converge to a maximum margin classifier, even if "optimal" AdaBoost produces a maximum margin. Also, we show that if AdaBoost cycles, it cycles among "support vectors", i.e., examples that achieve the same smallest margin.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1557–1595},
numpages = {39}
}

@article{10.5555/1005332.1044711,
author = {Fleuret, Fran\c{c}ois},
title = {Fast Binary Feature Selection with Conditional Mutual Information},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {We propose in this paper a very fast feature selection technique based on conditional mutual information. By picking features which maximize their mutual information with the class to predict conditional to any feature already picked, it ensures the selection of features which are both individually informative and two-by-two weakly dependant. We show that this feature selection method outperforms other classical algorithms, and that a naive Bayesian classifier built with features selected that way achieves error rates similar to those of state-of-the-art methods such as boosting or SVMs. The implementation we propose selects 50 features among 40,000, based on a training set of 500 examples in a tenth of a second on a standard 1Ghz PC.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1531–1555},
numpages = {25}
}

@article{10.5555/1005332.1044710,
author = {Greensmith, Evan and Bartlett, Peter L. and Baxter, Jonathan},
title = {Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Policy gradient methods for reinforcement learning avoid some of the undesirable properties of the value function approaches, such as policy degradation (Baxter and Bartlett, 2001). However, the variance of the performance gradient estimates obtained from the simulation is sometimes excessive. In this paper, we consider variance reduction methods that were developed for Monte Carlo estimates of integrals. We study two commonly used policy gradient techniques, the baseline and actor-critic methods, from this perspective. Both can be interpreted as additive control variate variance reduction methods. We consider the expected average reward performance measure, and we focus on the GPOMDP algorithm for estimating performance gradients in partially observable Markov decision processes controlled by stochastic reactive policies. We give bounds for the estimation error of the gradient estimates for both baseline and actor-critic algorithms, in terms of the sample size and mixing properties of the controlled system. For the baseline technique, we compute the optimal baseline, and show that the popular approach of using the average reward to define the baseline can be suboptimal. For actor-critic algorithms, we show that using the true value function as the critic can be suboptimal. We also discuss algorithms for estimating the optimal baseline and approximate value function.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1471–1530},
numpages = {60}
}

@article{10.5555/1005332.1044709,
author = {Hoyer, Patrik O.},
title = {Non-Negative Matrix Factorization with Sparseness Constraints},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Non-negative matrix factorization (NMF) is a recently developed technique for finding parts-based, linear representations of non-negative data. Although it has successfully been applied in several applications, it does not always result in parts-based representations. In this paper, we show how explicitly incorporating the notion of 'sparseness' improves the found decompositions. Additionally, we provide complete MATLAB code both for standard NMF and for our extension. Our hope is that this will further the application of these methods to solving novel data-analysis problems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1457–1469},
numpages = {13}
}

@article{10.5555/1005332.1044708,
author = {Leslie, Christina and Kuang, Rui},
title = {Fast String Kernels Using Inexact Matching for Protein Sequences},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {We describe several families of k-mer based string kernels related to the recently presented mismatch kernel and designed for use with support vector machines (SVMs) for classification of protein sequence data. These new kernels -- restricted gappy kernels, substitution kernels, and wildcard kernels -- are based on feature spaces indexed by k-length subsequences ("k-mers") from the string alphabet Σ. However, for all kernels we define here, the kernel value K(x,y) can be computed in O(cK(|x|+|y|)) time, where the constant cK depends on the parameters of the kernel but is independent of the size |Σ| of the alphabet. Thus the computation of these kernels is linear in the length of the sequences, like the mismatch kernel, but we improve upon the parameter-dependent constant cK = km+1|Σ|m of the (k,m)-mismatch kernel. We compute the kernels efficiently using a trie data structure and relate our new kernels to the recently described transducer formalism. In protein classification experiments on two benchmark SCOP data sets, we show that our new faster kernels achieve SVM classification performance comparable to the mismatch kernel and the Fisher kernel derived from profile hidden Markov models, and we investigate the dependence of the kernels on parameter choice.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1435–1455},
numpages = {21}
}

@article{10.5555/1005332.1044707,
author = {Bhattacharyya, Chiranjib},
title = {Second Order Cone Programming Formulations for Feature Selection},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {This paper addresses the issue of feature selection for linear classifiers given the moments of the class conditional densities. The problem is posed as finding a minimal set of features such that the resulting classifier has a low misclassification error. Using a bound on the misclassification error involving the mean and covariance of class conditional densities and minimizing an L1 norm as an approximate criterion for feature selection, a second order programming formulation is derived. To handle errors in estimation of mean and covariances, a tractable robust formulation is also discussed. In a slightly different setting the Fisher discriminant is derived. Feature selection for Fisher discriminant is also discussed. Experimental results on synthetic data sets and on real life microarray data show that the proposed formulations are competitive with the state of the art linear programming formulation.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1417–1433},
numpages = {17}
}

@article{10.5555/1005332.1044706,
author = {Hastie, Trevor and Rosset, Saharon and Tibshirani, Robert and Zhu, Ji},
title = {The Entire Regularization Path for the Support Vector Machine},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {The support vector machine (SVM) is a widely used tool for classification. Many efficient implementations exist for fitting a two-class SVM model. The user has to supply values for the tuning parameters: the regularization cost parameter, and the kernel parameters. It seems a common practice is to use a default value for the cost parameter, often leading to the least restrictive model. In this paper we argue that the choice of the cost parameter can be critical. We then derive an algorithm that can fit the entire path of SVM solutions for every value of the cost parameter, with essentially the same computational cost as fitting one SVM model. We illustrate our algorithm on some examples, and use our representation to give further insight into the range of SVM solutions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1391–1415},
numpages = {25}
}

@article{10.5555/1005332.1044705,
author = {De Vito, Ernesto and Rosasco, Lorenzo and Caponnetto, Andrea and Piana, Michele and Verri, Alessandro},
title = {Some Properties of Regularized Kernel Methods},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {In regularized kernel methods, the solution of a learning problem is found by minimizing functionals consisting of the sum of a data and a complexity term. In this paper we investigate some properties of a more general form of the above functionals in which the data term corresponds to the expected risk. First, we prove a quantitative version of the representer theorem holding for both regression and classification, for both differentiable and non-differentiable loss functions, and for arbitrary offset terms. Second, we show that the case in which the offset space is non trivial corresponds to solving a standard problem of regularization in a Reproducing Kernel Hilbert Space in which the penalty term is given by a seminorm. Finally, we discuss the issues of existence and uniqueness of the solution. From the specialization of our analysis to the discrete setting it is immediate to establish a connection between the solution properties of sparsity and coefficient boundedness and some properties of the loss function. For the case of Support Vector Machines for classification, we also obtain a complete characterization of the whole method in terms of the Khun-Tucker conditions with no need to introduce the dual formulation.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1363–1390},
numpages = {28}
}

@article{10.5555/1005332.1044704,
author = {Stracuzzi, David J. and Utgoff, Paul E.},
title = {Randomized Variable Elimination},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Variable selection, the process of identifying input variables that are relevant to a particular learning problem, has received much attention in the learning community. Methods that employ a learning algorithm as a part of the selection process (wrappers) have been shown to outperform methods that select variables independently from the learning algorithm (filters), but only at great computational expense. We present a randomized wrapper algorithm whose computational requirements are within a constant factor of simply learning in the presence of all input variables, provided that the number of relevant variables is small and known in advance. We then show how to remove the latter assumption, and demonstrate performance on several problems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1331–1362},
numpages = {32}
}

@article{10.5555/1005332.1044703,
author = {Chickering, David Maxwell and Heckerman, David and Meek, Christopher},
title = {Large-Sample Learning of Bayesian Networks is NP-Hard},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {In this paper, we provide new complexity results for algorithms that learn discrete-variable Bayesian networks from data. Our results apply whenever the learning algorithm uses a scoring criterion that favors the simplest structure for which the model is able to represent the generative distribution exactly. Our results therefore hold whenever the learning algorithm uses a consistent scoring criterion and is applied to a sufficiently large dataset. We show that identifying high-scoring structures is NP-hard, even when any combination of one or more of the following hold: the generative distribution is perfect with respect to some DAG containing hidden variables; we are given an independence oracle; we are given an inference oracle; we are given an information oracle; we restrict potential solutions to structures in which each node has at most k parents, for all k>=3.Our proof relies on a new technical result that we establish in the appendices. In particular, we provide a method for constructing the local distributions in a Bayesian network such that the resulting joint distribution is provably perfect with respect to the structure of the network.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1287–1330},
numpages = {44}
}

@article{10.5555/1005332.1044702,
author = {Huang, Kaizhu and Yang, Haiqin and King, Irwin and Lyu, Michael R. and Chan, Laiwan},
title = {The Minimum Error Minimax Probability Machine},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {We construct a distribution-free Bayes optimal classifier called the Minimum Error Minimax Probability Machine (MEMPM) in a worst-case setting, i.e., under all possible choices of class-conditional densities with a given mean and covariance matrix. By assuming no specific distributions for the data, our model is thus distinguished from traditional Bayes optimal approaches, where an assumption on the data distribution is a must. This model is extended from the Minimax Probability Machine (MPM), a recently-proposed novel classifier, and is demonstrated to be the general case of MPM. Moreover, it includes another special case named the Biased Minimax Probability Machine, which is appropriate for handling biased classification. One appealing feature of MEMPM is that it contains an explicit performance indicator, i.e., a lower bound on the worst-case accuracy, which is shown to be tighter than that of MPM. We provide conditions under which the worst-case Bayes optimal classifier converges to the Bayes optimal classifier. We demonstrate how to apply a more general statistical framework to estimate model input parameters robustly. We also show how to extend our model to nonlinear classification by exploiting kernelization techniques. A series of experiments on both synthetic data sets and real world benchmark data sets validates our proposition and demonstrates the effectiveness of our model.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1253–1286},
numpages = {34}
}

@article{10.5555/1005332.1044701,
author = {Zhang, Tong},
title = {Statistical Analysis of Some Multi-Category Large Margin Classification Methods},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {The purpose of this paper is to investigate statistical properties of risk minimization based multi-category classification methods. These methods can be considered as natural extensions of binary large margin classification. We establish conditions that guarantee the consistency of classifiers obtained in the risk minimization framework with respect to the classification error. Examples are provided for four specific forms of the general formulation, which extend a number of known methods. Using these examples, we show that some risk minimization formulations can also be used to obtain conditional probability estimates for the underlying problem. Such conditional probability information can be useful for statistical inferencing tasks beyond classification.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1225–1251},
numpages = {27}
}

@article{10.5555/1005332.1044700,
author = {Yu, Lei and Liu, Huan},
title = {Efficient Feature Selection via Analysis of Relevance and Redundancy},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Feature selection is applied to reduce the number of features in many applications where data has hundreds or thousands of features. Existing feature selection methods mainly focus on finding relevant features. In this paper, we show that feature relevance alone is insufficient for efficient feature selection of high-dimensional data. We define feature redundancy and propose to perform explicit redundancy analysis in feature selection. A new framework is introduced that decouples relevance analysis and redundancy analysis. We develop a correlation-based method for relevance and redundancy analysis, and conduct an empirical study of its efficiency and effectiveness comparing with representative methods.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1205–1224},
numpages = {20}
}

@article{10.5555/1005332.1044699,
author = {Dash, Denver and Cooper, Gregory F.},
title = {Model Averaging for Prediction with Discrete Bayesian Networks},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {In this paper we consider the problem of performing Bayesian model-averaging over a class of discrete Bayesian network structures consistent with a partial ordering and with bounded in-degree k. We show that for N nodes this class contains in the worst-case at least <img src="dash04a-omega.jpeg" alt="omega eq" align="middle"> distinct network structures, and yet model averaging over these structures can be performed using <img src="dash04a-bigo.jpeg" alt="bigo eq" align="middle"> operations. Furthermore we show that there exists a single Bayesian network that defines a joint distribution over the variables that is equivalent to model averaging over these structures. Although constructing this network is computationally prohibitive, we show that it can be approximated by a tractable network, allowing approximate model-averaged probability calculations to be performed in O(N) time. Our result also leads to an exact and linear-time solution to the problem of averaging over the 2N possible feature sets in a naive Bayes model, providing an exact Bayesian solution to the troublesome feature-selection problem for naive Bayes classifiers. We demonstrate the utility of these techniques in the context of supervised classification, showing empirically that model averaging consistently beats other generative Bayesian-network-based models, even when the generating model is not guaranteed to be a member of the class being averaged over. We characterize the performance over several parameters on simulated and real-world data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1177–1203},
numpages = {27}
}

@article{10.5555/1005332.1044698,
author = {Chen, Di-Rong and Wu, Qiang and Ying, Yiming and Zhou, Ding-Xuan},
title = {Support Vector Machine Soft Margin Classifiers: Error Analysis},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {The purpose of this paper is to provide a PAC error analysis for the q-norm soft margin classifier, a support vector machine classification algorithm. It consists of two parts: regularization error and sample error. While many techniques are available for treating the sample error, much less is known for the regularization error and the corresponding approximation error for reproducing kernel Hilbert spaces. We are mainly concerned about the regularization error. It is estimated for general distributions by a K-functional in weighted Lq spaces. For weakly separable distributions (i.e., the margin may be zero) satisfactory convergence rates are provided by means of separating functions. A projection operator is introduced, which leads to better sample error estimates especially for small complexity kernels. The misclassification error is bounded by the V-risk associated with a general class of loss functions V. The difficulty of bounding the offset is overcome. Polynomial kernels and Gaussian kernels are used to demonstrate the main results. The choice of the regularization parameter plays an important role in our analysis.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1143–1175},
numpages = {33}
}

@article{10.5555/1005332.1044697,
author = {Mangasarian, Olvi L. and Shavlik, Jude W. and Wild, Edward W.},
title = {Knowledge-Based Kernel Approximation},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Prior knowledge, in the form of linear inequalities that need to be satisfied over multiple polyhedral sets, is incorporated into a function approximation generated by a linear combination of linear or nonlinear kernels. In addition, the approximation needs to satisfy conventional conditions such as having given exact or inexact function values at certain points. Determining such an approximation leads to a linear programming formulation. By using nonlinear kernels and mapping the prior polyhedral knowledge in the input space to one defined by the kernels, the prior knowledge translates into nonlinear inequalities in the original input space. Through a number of computational examples, including a real world breast cancer prognosis dataset, it is shown that prior knowledge can significantly improve function approximation.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1127–1141},
numpages = {15}
}

@article{10.5555/1005332.1044696,
author = {K\"{a}\"{a}ri\"{a}inen, Matti and Malinen, Tuomo and Elomaa, Tapio},
title = {Selective Rademacher Penalization and Reduced Error Pruning of Decision Trees},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Rademacher penalization is a modern technique for obtaining data-dependent bounds on the generalization error of classifiers. It appears to be limited to relatively simple hypothesis classes because of computational complexity issues. In this paper we, nevertheless, apply Rademacher penalization to the in practice important hypothesis class of unrestricted decision trees by considering the prunings of a given decision tree rather than the tree growing phase. This study constitutes the first application of Rademacher penalization to hypothesis classes that have practical significance. We present two variations of the approach, one in which the hypothesis class consists of all prunings of the initial tree and another in which only the prunings that are accurate on growing data are taken into account. Moreover, we generalize the error-bounding approach from binary classification to multi-class situations. Our empirical experiments indicate that the proposed new bounds outperform distribution-independent bounds for decision tree prunings and provide non-trivial error estimates on real-world data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1107–1126},
numpages = {20}
}

@article{10.5555/1005332.1044695,
author = {Bengio, Yoshua and Grandvalet, Yves},
title = {No Unbiased Estimator of the Variance of K-Fold Cross-Validation},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Most machine learning researchers perform quantitative experiments to estimate generalization error and compare the performance of different algorithms (in particular, their proposed algorithm). In order to be able to draw statistically convincing conclusions, it is important to estimate the uncertainty of such estimates. This paper studies the very commonly used K-fold cross-validation estimator of generalization performance. The main theorem shows that there exists no universal (valid under all distributions) unbiased estimator of the variance of K-fold cross-validation. The analysis that accompanies this result is based on the eigen-decomposition of the covariance matrix of errors, which has only three different eigenvalues corresponding to three degrees of freedom of the matrix and three components of the total variance. This analysis helps to better understand the nature of the problem and how it can make naive estimators (that don't take into account the error correlations due to the overlap between training and test sets) grossly underestimate variance. This is confirmed by numerical experiments in which the three components of the variance are compared when the difficulty of the learning problem and the number of folds are varied.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1089–1105},
numpages = {17}
}

@article{10.5555/1005332.1016794,
author = {Sallans, Brian and Hinton, Geoffrey E.},
title = {Reinforcement Learning with Factored States and Actions},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {A novel approximation method is presented for approximating the value function and selecting good actions for Markov decision processes with large state and action spaces. The method approximates state-action values as negative free energies in an undirected graphical model called a product of experts. The model parameters can be learned efficiently because values and derivatives can be efficiently computed for a product of experts. Actions can be found even in large factored action spaces by the use of Markov chain Monte Carlo sampling. Simulation results show that the product of experts approximation can be used to solve large problems. In one simulation it is used to find actions in action spaces of size 240.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1063–1088},
numpages = {26}
}

@article{10.5555/1005332.1016793,
author = {Cortes, Corinna and Haffner, Patrick and Mohri, Mehryar},
title = {Rational Kernels: Theory and Algorithms},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Many classification algorithms were originally designed for fixed-size vectors. Recent applications in text and speech processing and computational biology require however the analysis of variable-length sequences and more generally weighted automata. An approach widely used in statistical learning techniques such as Support Vector Machines (SVMs) is that of kernel methods, due to their computational efficiency in high-dimensional feature spaces. We introduce a general family of kernels based on weighted transducers or rational relations,  rational kernels , that extend kernel methods to the analysis of variable-length sequences or more generally weighted automata. We show that rational kernels can be computed efficiently using a general algorithm of composition of weighted transducers and a general single-source shortest-distance algorithm. Not all rational kernels are  positive definite and symmetric  (PDS), or equivalently verify the Mercer condition, a condition that guarantees the convergence of training for discriminant classification algorithms such as SVMs. We present several theoretical results related to PDS rational kernels. We show that under some general conditions these kernels are closed under sum, product, or Kleene-closure and give a general method for constructing a PDS rational kernel from an arbitrary transducer defined on some non-idempotent semirings. We give the proof of several characterization results that can be used to guide the design of PDS rational kernels. We also show that some commonly used string kernels or similarity measures such as the edit-distance, the convolution kernels of Haussler, and some string kernels used in the context of computational biology are specific instances of rational kernels. Our results include the proof that the edit-distance over a non-trivial alphabet is not negative definite, which, to the best of our knowledge, was never stated or proved before. Rational kernels can be combined with SVMs to form efficient and powerful techniques for a variety of classification tasks in text and speech processing, or computational biology. We describe examples of general families of PDS rational kernels that are useful in many of these applications and report the result of our experiments illustrating the use of rational kernels in several difficult large-vocabulary spoken-dialog classification tasks based on deployed spoken-dialog systems. Our results show that rational kernels are easy to design and implement and lead to substantial improvements of the classification accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1035–1062},
numpages = {28}
}

@article{10.5555/1005332.1016792,
author = {Christmann, Andreas and Steinwart, Ingo},
title = {On Robustness Properties of Convex Risk Minimization Methods for Pattern Recognition},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {The paper brings together methods from two disciplines: machine learning theory and robust statistics. We argue that robustness is an important aspect and we show that many existing machine learning methods based on the convex risk minimization principle have - besides other good properties - also the advantage of being robust. Robustness properties of machine learning methods based on convex risk minimization are investigated for the problem of pattern recognition. Assumptions are given for the existence of the influence function of the classifiers and for bounds on the influence function. Kernel logistic regression, support vector machines, least squares and the AdaBoost loss function are treated as special cases. Some results on the robustness of such methods are also obtained for the sensitivity curve and the maxbias, which are two other robustness criteria. A sensitivity analysis of the support vector machine is given.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1007–1034},
numpages = {28}
}

@article{10.5555/1005332.1016791,
author = {Wu, Ting-Fan and Lin, Chih-Jen and Weng, Ruby C.},
title = {Probability Estimates for Multi-Class Classification by Pairwise Coupling},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Pairwise coupling is a popular multi-class classification method that combines all comparisons for each pair of classes. This paper presents two approaches for obtaining class probabilities. Both methods can be reduced to linear systems and are easy to implement. We show conceptually and experimentally that the proposed approaches are more stable than the two existing popular methods: voting and the method by Hastie and Tibshirani (1998)},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {975–1005},
numpages = {31}
}

@article{10.5555/1005332.1016790,
author = {Rosset, Saharon and Zhu, Ji and Hastie, Trevor},
title = {Boosting as a Regularized Path to a Maximum Margin Classifier},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {In this paper we study boosting methods from a new perspective. We build on recent work by Efron et al. to show that boosting approximately (and in some cases exactly) minimizes its loss criterion with an l1 constraint on the coefficient vector. This helps understand the success of boosting with early stopping as regularized fitting of the loss criterion. For the two most commonly used criteria (exponential and binomial log-likelihood), we further show that as the constraint is relaxed---or equivalently as the boosting iterations proceed---the solution converges (in the separable case) to an "l1-optimal" separating hyper-plane. We prove that this l1-optimal separating hyper-plane has the property of maximizing the minimal l1-margin of the training data, as defined in the boosting literature. An interesting fundamental similarity between boosting and kernel support vector machines emerges, as both can be described as methods for regularized optimization in high-dimensional predictor space, using a computational trick to make the calculation practical, and converging to margin-maximizing solutions. While this statement describes SVMs exactly, it applies to boosting only approximately.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {941–973},
numpages = {33}
}

@article{10.5555/1005332.1016789,
author = {Chen, Yixin and Wang, James Z.},
title = {Image Categorization by Learning and Reasoning with Regions},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {Designing computer programs to automatically categorize images using low-level features is a challenging research topic in computer vision. In this paper, we present a new learning technique, which extends Multiple-Instance Learning (MIL), and its application to the problem of region-based image categorization. Images are viewed as bags, each of which contains a number of instances corresponding to regions obtained from image segmentation. The standard MIL problem assumes that a bag is labeled positive if at least one of its instances is positive; otherwise, the bag is negative. In the proposed MIL framework, DD-SVM, a bag label is determined by some number of instances satisfying various properties. DD-SVM first learns a collection of  instance prototypes according to a Diverse Density (DD) function. Each instance prototype represents a class of instances that is more likely to appear in bags with the specific label than in the other bags. A nonlinear mapping is then defined using the instance prototypes and maps every bag to a point in a new feature space, named the  bag feature space. Finally, standard support vector machines are trained in the bag feature space. We provide experimental results on an image categorization problem and a drug activity prediction problem.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {913–939},
numpages = {27}
}

@article{10.5555/1005332.1016788,
author = {Schmitt, Michael},
title = {Some Dichotomy Theorems for Neural Learning Problems},
year = {2004},
issue_date = {12/1/2004},
publisher = {JMLR.org},
volume = {5},
issn = {1532-4435},
abstract = {The computational complexity of learning from binary examples is investigated for linear threshold neurons. We introduce combinatorial measures that create classes of infinitely many learning problems with sample restrictions. We analyze how the complexity of these problems depends on the values for the measures. The results are established as dichotomy theorems showing that each problem is either NP-complete or solvable in polynomial time. In particular, we consider consistency and maximum consistency problems for neurons with binary weights, and maximum consistency problems for neurons with arbitrary weights. We determine for each problem class the dividing line between the NP-complete and polynomial-time solvable problems. Moreover, all efficiently solvable problems are shown to have constructive algorithms that require no more than linear time on a random access machine model. Similar dichotomies are exhibited for neurons with bounded threshold.

license_type: permissive

branch_name: refs/heads/main

extension: bib