text:
1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Many complex control problems require sophisticated solutions that are not amenable to traditional controller design. Not only is it difficult to model real world systems, but often it is unclear what kind of behavior is required to solve the task. Reinforcement learning (RL) approaches have made progress by using direct interaction with the task environment, but have so far not scaled well to large state spaces and environments that are not fully observable. In recent years, neuroevolution, the artificial evolution of neural networks, has had remarkable success in tasks that exhibit these two properties. In this paper, we compare a neuroevolution method called Cooperative Synapse Neuroevolution (CoSyNE), that uses cooperative coevolution at the level of individual synaptic weights, to a broad range of reinforcement learning algorithms on very difficult versions of the pole balancing problem that involve large (continuous) state spaces and hidden state. CoSyNE is shown to be significantly more efficient and powerful than the other methods on these tasks.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {937–965},
numpages = {29}
}

@article{10.5555/1390681.1390711,
author = {Christmann, Andreas and Messem, Arnout Van},
title = {Bouligand Derivatives and Robustness of Support Vector Machines for Regression},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We investigate robustness properties for a broad class of support vector machines with non-smooth loss functions. These kernel methods are inspired by convex risk minimization in infinite dimensional Hilbert spaces. Leading examples are the support vector machine based on the <u>ε</u>-insensitive loss function, and kernel based quantile regression based on the pinball loss function. Firstly, we propose with the Bouligand influence function (BIF) a modification of F.R. Hampel's influence function. The BIF has the advantage of being positive homogeneous which is in general not true for Hampel's influence function. Secondly, we show that many support vector machines based on a Lipschitz continuous loss function and a bounded kernel have a bounded BIF and are thus robust in the sense of robust statistics based on influence functions.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {915–936},
numpages = {22}
}

@article{10.5555/1390681.1390710,
author = {Drton, Mathias and Richardson, Thomas S.},
title = {Graphical Methods for Efficient Likelihood Inference in Gaussian Covariance Models},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In graphical modelling, a bi-directed graph encodes marginal independences among random variables that are identified with the vertices of the graph. We show how to transform a bi-directed graph into a maximal ancestral graph that (i) represents the same independence structure as the original bi-directed graph, and (ii) minimizes the number of arrowheads among all ancestral graphs satisfying (i). Here the number of arrowheads of an ancestral graph is the number of directed edges plus twice the number of bi-directed edges. In Gaussian models, this construction can be used for more efficient iterative maximization of the likelihood function and to determine when maximum likelihood estimates are equal to empirical counterparts.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {893–914},
numpages = {22}
}

@article{10.5555/1390681.1390709,
author = {Bax, Eric and Callejas, Augusto},
title = {An Error Bound Based on a Worst Likely Assignment},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {This paper introduces a new PAC transductive error bound for classification. The method uses information from the training examples and inputs of working examples to develop a set of likely assignments to outputs of the working examples. A likely assignment with maximum error determines the bound. The method is very effective for small data sets.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {859–891},
numpages = {33}
}

@article{10.5555/1390681.1390708,
author = {Munos, R\'{e}mi and Szepesv\'{a}ri, Csaba},
title = {Finite-Time Bounds for Fitted Value Iteration},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In this paper we develop a theoretical analysis of the performance of sampling-based fitted value iteration (FVI) to solve infinite state-space, discounted-reward Markovian decision processes (MDPs) under the assumption that a generative model of the environment is available. Our main results come in the form of finite-time bounds on the performance of two versions of sampling-based FVI. The convergence rate results obtained allow us to show that both versions of FVI are well behaving in the sense that by using a sufficiently large number of samples for a large class of MDPs, arbitrary good performance can be achieved with high probability. An important feature of our proof technique is that it permits the study of weighted Lp-norm performance bounds. As a result, our technique applies to a large class of function-approximation methods (e.g., neural networks, adaptive regression trees, kernel machines, locally weighted learning), and our bounds scale well with the effective horizon of the MDP. The bounds show a dependence on the stochastic stability properties of the MDP: they scale with the discounted-average concentrability of the future-state distributions. They also depend on a new measure of the approximation power of the function space, the inherent Bellman residual, which reflects how well the function space is "aligned" with the dynamics and rewards of the MDP. The conditions of the main result, as well as the concepts introduced in the analysis, are extensively discussed and compared to previous theoretical results. Numerical experiments are used to substantiate the theoretical findings.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {815–857},
numpages = {43}
}

@article{10.5555/1390681.1390707,
author = {Seeger, Matthias W.},
title = {Bayesian Inference and Optimal Design for the Sparse Linear Model},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The linear model with sparsity-favouring prior on the coefficients has important applications in many different domains. In machine learning, most methods to date search for maximum a posteriori sparse solutions and neglect to represent posterior uncertainties. In this paper, we address problems of Bayesian optimal design (or experiment planning), for which accurate estimates of uncertainty are essential. To this end, we employ expectation propagation approximate inference for the linear model with Laplace prior, giving new insight into numerical stability properties and proposing a robust algorithm. We also show how to estimate model hyperparameters by empirical Bayesian maximisation of the marginal likelihood, and propose ideas in order to scale up the method to very large underdetermined problems.We demonstrate the versatility of our framework on the application of gene regulatory network identification from micro-array expression data, where both the Laplace prior and the active experimental design approach are shown to result in significant improvements. We also address the problem of sparse coding of natural images, and show how our framework can be used for compressive sensing tasks.Part of this work appeared in Seeger et al. (2007b). The gene network identification application appears in Steinke et al. (2007).},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {759–813},
numpages = {55}
}

@article{10.5555/1390681.1390706,
author = {Ye, Jieping and Ji, Shuiwang and Chen, Jianhui},
title = {Multi-Class Discriminant Kernel Learning via Convex Programming},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Regularized kernel discriminant analysis (RKDA) performs linear discriminant analysis in the feature space via the kernel trick. Its performance depends on the selection of kernels. In this paper, we consider the problem of multiple kernel learning (MKL) for RKDA, in which the optimal kernel matrix is obtained as a linear combination of pre-specified kernel matrices. We show that the kernel learning problem in RKDA can be formulated as convex programs. First, we show that this problem can be formulated as a semidefinite program (SDP). Based on the equivalence relationship between RKDA and least square problems in the binary-class case, we propose a convex quadratically constrained quadratic programming (QCQP) formulation for kernel learning in RKDA. A semi-infinite linear programming (SILP) formulation is derived to further improve the efficiency. We extend these formulations to the multi-class case based on a key result established in this paper. That is, the multi-class RKDA kernel learning problem can be decomposed into a set of binary-class kernel learning problems which are constrained to share a common kernel. Based on this decomposition property, SDP formulations are proposed for the multi-class case. Furthermore, it leads naturally to QCQP and SILP formulations. As the performance of RKDA depends on the regularization parameter, we show that this parameter can also be optimized in a joint framework with the kernel. Extensive experiments have been conducted and analyzed, and connections to other algorithms are discussed.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {719–758},
numpages = {40}
}

@article{10.5555/1390681.1390705,
author = {Yoon, Sungwook and Fern, Alan and Givan, Robert},
title = {Learning Control Knowledge for Forward Search Planning},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {A number of today's state-of-the-art planners are based on forward state-space search. The impressive performance can be attributed to progress in computing domain independent heuristics that perform well across many domains. However, it is easy to find domains where such heuristics provide poor guidance, leading to planning failure. Motivated by such failures, the focus of this paper is to investigate mechanisms for learning domain-specific knowledge to better control forward search in a given domain. While there has been a large body of work on inductive learning of control knowledge for AI planning, there is a void of work aimed at forward-state-space search. One reason for this may be that it is challenging to specify a knowledge representation for compactly representing important concepts across a wide range of domains. One of the main contributions of this work is to introduce a novel feature space for representing such control knowledge. The key idea is to define features in terms of information computed via relaxed plan extraction, which has been a major source of success for non-learning planners. This gives a new way of leveraging relaxed planning techniques in the context of learning. Using this feature space, we describe three forms of control knowledge---reactive policies (decision list rules and measures of progress) and linear heuristics---and show how to learn them and incorporate them into forward state-space search. Our empirical results show that our approaches are able to surpass state-of-the-art non-learning planners across a wide range of planning competition domains.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {683–718},
numpages = {36}
}

@article{10.5555/1390681.1390704,
author = {Chen, Shann-Ching and Gordon, Geoffrey J. and Murphy, Robert F.},
title = {Graphical Models for Structured Classification, with an Application to Interpreting Images of Protein Subcellular Location Patterns},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In structured classification problems, there is a direct conflict between expressive models and efficient inference: while graphical models such as Markov random fields or factor graphs can represent arbitrary dependences among instance labels, the cost of inference via belief propagation in these models grows rapidly as the graph structure becomes more complicated. One important source of complexity in belief propagation is the need to marginalize large factors to compute messages. This operation takes time exponential in the number of variables in the factor, and can limit the expressiveness of the models we can use. In this paper, we study a new class of potential functions, which we call decomposable k-way potentials, and provide efficient algorithms for computing messages from these potentials during belief propagation. We believe these new potentials provide a good balance between expressive power and efficient inference in practical structured classification problems. We discuss three instances of decomposable potentials: the associative Markov network potential, the nested junction tree, and a new type of potential which we call the voting potential. We use these potentials to classify images of protein subcellular location patterns in groups of cells. Classifying subcellular location patterns can help us answer many important questions in computational biology, including questions about how various treatments affect the synthesis and behavior of proteins and networks of proteins within a cell. Our new representation and algorithm lead to substantial improvements in both inference speed and classification accuracy.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {651–682},
numpages = {32}
}

@article{10.5555/1390681.1390703,
author = {Lin, Chih-Jen and Weng, Ruby C. and Keerthi, S. Sathiya},
title = {Trust Region Newton Method for Logistic Regression},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Large-scale logistic regression arises in many applications such as document classification and natural language processing. In this paper, we apply a trust region Newton method to maximize the log-likelihood of the logistic regression model. The proposed method uses only approximate Newton steps in the beginning, but achieves fast convergence in the end. Experiments show that it is faster than the commonly used quasi Newton approach for logistic regression. We also extend the proposed method to large-scale L2-loss linear support vector machines (SVM).},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {627–650},
numpages = {24}
}

@article{10.5555/1390681.1390702,
author = {Klanke, Stefan and Vijayakumar, Sethu and Schaal, Stefan},
title = {A Library for Locally Weighted Projection Regression},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In this paper we introduce an improved implementation of locally weighted projection regression (LWPR), a supervised learning algorithm that is capable of handling high-dimensional input data. As the key features, our code supports multi-threading, is available for multiple platforms, and provides wrappers for several programming languages.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {623–626},
numpages = {4}
}

@article{10.5555/1390681.1390701,
author = {Corani, Giorgio and Zaffalon, Marco},
title = {Learning Reliable Classifiers From Small or Incomplete Data Sets: The Naive Credal Classifier 2},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In this paper, the naive credal classifier, which is a set-valued counterpart of naive Bayes, is extended to a general and flexible treatment of incomplete data, yielding a new classifier called naive credal classifier 2 (NCC2). The new classifier delivers classifications that are reliable even in the presence of small sample sizes and missing values. Extensive empirical evaluations show that, by issuing set-valued classifications, NCC2 is able to isolate and properly deal with instances that are hard to classify (on which naive Bayes accuracy drops considerably), and to perform as well as naive Bayes on the other instances. The experiments point to a general problem: they show that with missing values, empirical evaluations may not reliably estimate the accuracy of a traditional classifier, such as naive Bayes. This phenomenon adds even more value to the robust approach to classification implemented by NCC2.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {581–621},
numpages = {41}
}

@article{10.5555/1390681.1390700,
author = {Garriga, Gemma C. and Kralj, Petra and Lavra\v{c}, Nada},
title = {Closed Sets for Labeled Data},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Closed sets have been proven successful in the context of compacted data representation for association rule learning. However, their use is mainly descriptive, dealing only with unlabeled data. This paper shows that when considering labeled data, closed sets can be adapted for classification and discrimination purposes by conveniently contrasting covering properties on positive and negative examples. We formally prove that these sets characterize the space of relevant combinations of features for discriminating the target class. In practice, identifying relevant/irrelevant combinations of features through closed sets is useful in many applications: to compact emerging patterns of typical descriptive mining applications, to reduce the number of essential rules in classification, and to efficiently learn subgroup descriptions, as demonstrated in real-life subgroup discovery experiments on a high dimensional microarray data set.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {559–580},
numpages = {22}
}

@article{10.5555/1390681.1390699,
author = {Claeskens, Gerda and Croux, Christophe and Van Kerckhoven, Johan},
title = {An Information Criterion for Variable Selection in Support Vector Machines},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Support vector machines for classification have the advantage that the curse of dimensionality is circumvented. It has been shown that a reduction of the dimension of the input space leads to even better results. For this purpose, we propose two information criteria which can be computed directly from the definition of the support vector machine. We assess the predictive performance of the models selected by our new criteria and compare them to existing variable selection techniques in a simulation study. The simulation results show that the new criteria are competitive in terms of generalization error rate while being much easier to compute. We arrive at the same findings for comparison on some real-world benchmark data sets.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {541–558},
numpages = {18}
}

@article{10.5555/1390681.1390698,
author = {Jiang, Bo and Zhang, Xuegong and Cai, Tianxi},
title = {Estimating the Confidence Interval for Prediction Errors of Support Vector Machine Classifiers},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Support vector machine (SVM) is one of the most popular and promising classification algorithms. After a classification rule is constructed via the SVM, it is essential to evaluate its prediction accuracy. In this paper, we develop procedures for obtaining both point and interval estimators for the prediction error. Under mild regularity conditions, we derive the consistency and asymptotic normality of the prediction error estimators for SVM with finite-dimensional kernels. A perturbation-resampling procedure is proposed to obtain interval estimates for the prediction error in practice. With numerical studies on simulated data and a benchmark repository, we recommend the use of interval estimates centered at the cross-validated point estimates for the prediction error. Further applications of the proposed procedure in model evaluation and feature selection are illustrated with two examples.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {521–540},
numpages = {20}
}

@article{10.5555/1390681.1390697,
author = {Ye, Jieping},
title = {Comments on the Complete Characterization of a Family of Solutions to a Generalized <i>Fisher</i> Criterion},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Loog (2007) provided a complete characterization of the family of solutions to a generalized Fisher criterion. We show that this characterization is essentially equivalent to the original characterization proposed in Ye (2005). The computational advantage of the original characterization over the new one is discussed, which justifies its practical use.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {517–519},
numpages = {3}
}

@article{10.5555/1390681.1390696,
author = {Banerjee, Onureena and El Ghaoui, Laurent and d'Aspremont, Alexandre},
title = {Model Selection Through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We consider the problem of estimating the parameters of a Gaussian or binary distribution in such a way that the resulting undirected graphical model is sparse. Our approach is to solve a maximum likelihood problem with an added l1-norm penalty term. The problem as formulated is convex but the memory requirements and complexity of existing interior point methods are prohibitive for problems with more than tens of nodes. We present two new algorithms for solving problems with at least a thousand nodes in the Gaussian case. Our first algorithm uses block coordinate descent, and can be interpreted as recursive l1-norm penalized regression. Our second algorithm, based on Nesterov's first order method, yields a complexity estimate with a better dependence on problem size than existing interior point methods. Using a log determinant relaxation of the log partition function (Wainwright and Jordan, 2006), we show that these same algorithms can be used to solve an approximate sparse maximum likelihood problem for the binary case. We test our algorithms on synthetic data, as well as on gene expression and senate voting records data.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {485–516},
numpages = {32}
}

@article{10.5555/1390681.1390695,
author = {Xie, Xianchao and Geng, Zhi},
title = {A Recursive Method for Structural Learning of Directed Acyclic Graphs},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In this paper, we propose a recursive method for structural learning of directed acyclic graphs (DAGs), in which a problem of structural learning for a large DAG is first decomposed into two problems of structural learning for two small vertex subsets, each of which is then decomposed recursively into two problems of smaller subsets until none subset can be decomposed further. In our approach, search for separators of a pair of variables in a large DAG is localized to small subsets, and thus the approach can improve the efficiency of searches and the power of statistical tests for structural learning. We show how the recent advances in the learning of undirected graphical models can be employed to facilitate the decomposition. Simulations are given to demonstrate the performance of the proposed method.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {459–483},
numpages = {25}
}

@article{10.5555/1390681.1390694,
author = {Panait, Liviu and Tuyls, Karl and Luke, Sean},
title = {Theoretical Advantages of Lenient Learners: An Evolutionary Game Theoretic Perspective},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {This paper presents the dynamics of multiple learning agents from an evolutionary game theoretic perspective. We provide replicator dynamics models for cooperative coevolutionary algorithms and for traditional multiagent Q-learning, and we extend these differential equations to account for lenient learners: agents that forgive possible mismatched teammate actions that resulted in low rewards. We use these extended formal models to study the convergence guarantees for these algorithms, and also to visualize the basins of attraction to optimal and suboptimal solutions in two benchmark coordination problems. The paper demonstrates that lenience provides learners with more accurate information about the benefits of performing their actions, resulting in higher likelihood of convergence to the globally optimal solution. In addition, the analysis indicates that the choice of learning algorithm has an insignificant impact on the overall performance of multiagent learning algorithms; rather, the performance of these algorithms depends primarily on the level of lenience that the agents exhibit to one another. Finally, the research herein supports the strength and generality of evolutionary game theory as a backbone for multiagent learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {423–457},
numpages = {35}
}

@article{10.5555/1390681.1390693,
author = {Shafer, Glenn and Vovk, Vladimir},
title = {A Tutorial on Conformal Prediction},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Conformal prediction uses past experience to determine precise levels of confidence in new predictions. Given an error probability ε, together with a method that makes a prediction undefined of a label y, it produces a set of labels, typically containing undefined, that also contains y with probability 1 – ε. Conformal prediction can be applied to any method for producing undefined: a nearest-neighbor method, a support-vector machine, ridge regression, etc.Conformal prediction is designed for an on-line setting in which labels are predicted successively, each one being revealed before the next is predicted. The most novel and valuable feature of conformal prediction is that if the successive examples are sampled independently from the same distribution, then the successive predictions will be right 1 – ε of the time, even though they are based on an accumulating data set rather than on independent data sets.In addition to the model under which successive examples are sampled independently, other on-line compression models can also use conformal prediction. The widely used Gaussian linear model is one of these.This tutorial presents a self-contained account of the theory of conformal prediction and works through several numerical examples. A more comprehensive treatment of the topic is provided in Algorithmic Learning in a Random World, by Vladimir Vovk, Alex Gammerman, and Glenn Shafer (Springer, 2005).},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {371–421},
numpages = {51}
}

@article{10.5555/1390681.1390692,
author = {Krupka, Eyal and Tishby, Naftali},
title = {Generalization from Observed to Unobserved Features by Clustering},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We argue that when objects are characterized by many attributes, clustering them on the basis of a random subset of these attributes can capture information on the unobserved attributes as well. Moreover, we show that under mild technical conditions, clustering the objects on the basis of such a random subset performs almost as well as clustering with the full attribute set. We prove finite sample generalization theorems for this novel learning scheme that extends analogous results from the supervised learning setting. We use our framework to analyze generalization to unobserved features of two well-known clustering algorithms: k-means and the maximum likelihood multinomial mixture model. The scheme is demonstrated for collaborative filtering of users with movie ratings as attributes and document clustering with words as attributes.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {339–370},
numpages = {32}
}

@article{10.5555/1390681.1390691,
author = {Balakrishnan, Suhrid and Madigan, David},
title = {Algorithms for Sparse Linear Classifiers in the Massive Data Setting},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Classifiers favoring sparse solutions, such as support vector machines, relevance vector machines, LASSO-regression based classifiers, etc., provide competitive methods for classification problems in high dimensions. However, current algorithms for training sparse classifiers typically scale quite unfavorably with respect to the number of training examples. This paper proposes online and multi-pass algorithms for training sparse linear classifiers for high dimensional data. These algorithms have computational complexity and memory requirements that make learning on massive data sets feasible. The central idea that makes this possible is a straightforward quadratic approximation to the likelihood function.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {313–337},
numpages = {25}
}

@article{10.5555/1390681.1390690,
author = {Lin, Hsuan-Tien and Li, Ling},
title = {Support Vector Machinery for Infinite Ensemble Learning},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Ensemble learning algorithms such as boosting can achieve better performance by averaging over the predictions of some base hypotheses. Nevertheless, most existing algorithms are limited to combining only a finite number of hypotheses, and the generated ensemble is usually sparse. Thus, it is not clear whether we should construct an ensemble classifier with a larger or even an infinite number of hypotheses. In addition, constructing an infinite ensemble itself is a challenging task. In this paper, we formulate an infinite ensemble learning framework based on the support vector machine (SVM). The framework can output an infinite and nonsparse ensemble through embedding infinitely many hypotheses into an SVM kernel. We use the framework to derive two novel kernels, the stump kernel and the perceptron kernel. The stump kernel embodies infinitely many decision stumps, and the perceptron kernel embodies infinitely many perceptrons. We also show that the Laplacian radial basis function kernel embodies infinitely many decision trees, and can thus be explained through infinite ensemble learning. Experimental results show that SVM with these kernels is superior to boosting with the same base hypothesis set. In addition, SVM with the stump kernel or the perceptron kernel performs similarly to SVM with the Gaussian radial basis function kernel, but enjoys the benefit of faster parameter selection. These properties make the novel kernels favorable choices in practice.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {285–312},
numpages = {28}
}

@article{10.5555/1390681.1390689,
author = {Krause, Andreas and Singh, Ajit and Guestrin, Carlos},
title = {Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {When monitoring spatial phenomena, which can often be modeled as Gaussian processes (GPs), choosing sensor locations is a fundamental task. There are several common strategies to address this task, for example, geometry or disk models, placing sensors at the points of highest entropy (variance) in the GP model, and A-, D-, or E-optimal design. In this paper, we tackle the combinatorial optimization problem of maximizing the mutual information between the chosen locations and the locations which are not selected. We prove that the problem of finding the configuration that maximizes mutual information is NP-complete. To address this issue, we describe a polynomial-time approximation that is within (1-1/e) of the optimum by exploiting the submodularity of mutual information. We also show how submodularity can be used to obtain online bounds, and design branch and bound search procedures. We then extend our algorithm to exploit lazy evaluations and local structure in the GP, yielding significant speedups. We also extend our approach to find placements which are robust against node failures and uncertainties in the model. These extensions are again associated with rigorous theoretical approximation guarantees, exploiting the submodularity of the objective function. We demonstrate the advantages of our approach towards optimizing mutual information in a very extensive empirical study on two real-world data sets.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {235–284},
numpages = {50}
}

@article{10.5555/1390681.1390688,
author = {Chapelle, Olivier and Sindhwani, Vikas and Keerthi, Sathiya S.},
title = {Optimization Techniques for Semi-Supervised Support Vector Machines},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Due to its wide applicability, the problem of semi-supervised classification is attracting increasing attention in machine learning. Semi-Supervised Support Vector Machines (S3VMs) are based on applying the margin maximization principle to both labeled and unlabeled examples. Unlike SVMs, their formulation leads to a non-convex optimization problem. A suite of algorithms have recently been proposed for solving S3VMs. This paper reviews key ideas in this literature. The performance and behavior of various S3VMs algorithms is studied together, under a common experimental setting.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {203–233},
numpages = {31}
}

@article{10.5555/1390681.1390687,
author = {Mease, David and Wyner, Abraham},
title = {Evidence Contrary to the Statistical View of Boosting},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The statistical perspective on boosting algorithms focuses on optimization, drawing parallels with maximum likelihood estimation for logistic regression. In this paper we present empirical evidence that raises questions about this view. Although the statistical perspective provides a theoretical framework within which it is possible to derive theorems and create new algorithms in general contexts, we show that there remain many unanswered important questions. Furthermore, we provide examples that reveal crucial flaws in the many practical suggestions and new methods that are derived from the statistical view. We perform carefully designed experiments using simple simulation models to illustrate some of these flaws and their practical consequences.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {131–156},
numpages = {26}
}

@article{10.5555/1390681.1390686,
author = {Henrich, Falk-Florian and Obermayer, Klaus},
title = {Active Learning by Spherical Subdivision},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We introduce a computationally feasible, "constructive" active learning method for binary classification. The learning algorithm is initially formulated for separable classification problems, for a hyperspherical data space with constant data density, and for great spheres as classifiers. In order to reduce computational complexity the version space is restricted to spherical simplices and learning procedes by subdividing the edges of maximal length. We show that this procedure optimally reduces a tight upper bound on the generalization error. The method is then extended to other separable classification problems using products of spheres as data spaces and isometries induced by charts of the sphere. An upper bound is provided for the probability of disagreement between classifiers (hence the generalization error) for non-constant data densities on the sphere. The emphasis of this work lies on providing mathematically exact performance estimates for active learning strategies.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {105–130},
numpages = {26}
}

@article{10.5555/1390681.1390685,
author = {Franc, Vojt\v{e}ch and Savchynskyy, Bogdan},
title = {Discriminative Learning of Max-Sum Classifiers},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The max-sum classifier predicts n-tuple of labels from n-tuple of observable variables by maximizing a sum of quality functions defined over neighbouring pairs of labels and observable variables. Predicting labels as MAP assignments of a Random Markov Field is a particular example of the max-sum classifier. Learning parameters of the max-sum classifier is a challenging problem because even computing the response of such classifier is NP-complete in general. Estimating parameters using the Maximum Likelihood approach is feasible only for a subclass of max-sum classifiers with an acyclic structure of neighbouring pairs. Recently, the discriminative methods represented by the perceptron and the Support Vector Machines, originally designed for binary linear classifiers, have been extended for learning some subclasses of the max-sum classifier. Besides the max-sum classifiers with the acyclic neighbouring structure, it has been shown that the discriminative learning is possible even with arbitrary neighbouring structure provided the quality functions fulfill some additional constraints. In this article, we extend the discriminative approach to other three classes of max-sum classifiers with an arbitrary neighbourhood structure. We derive learning algorithms for two subclasses of max-sum classifiers whose response can be computed in polynomial time: (i) the max-sum classifiers with supermodular quality functions and (ii) the max-sum classifiers whose response can be computed exactly by a linear programming relaxation. Moreover, we show that the learning problem can be approximately solved even for a general max-sum classifier.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {67–104},
numpages = {38}
}

@article{10.5555/1390681.1390684,
author = {Camps-Valls, Gustavo and Guti\'{e}rrez, Juan and G\'{o}mez-P\'{e}rez, Gabriel and Malo, Jes\'{u}s},
title = {On the Suitable Domain for SVM Training in Image Coding},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Conventional SVM-based image coding methods are founded on independently restricting the distortion in every image coefficient at some particular image representation. Geometrically, this implies allowing arbitrary signal distortions in an n-dimensional rectangle defined by the ε-insensitivity zone in each dimension of the selected image representation domain. Unfortunately, not every image representation domain is well-suited for such a simple, scalar-wise, approach because statistical and/or perceptual interactions between the coefficients may exist. These interactions imply that scalar approaches may induce distortions that do not follow the image statistics and/or are perceptually annoying. Taking into account these relations would imply using non-rectangular ε-insensitivity regions (allowing coupled distortions in different coefficients), which is beyond the conventional SVM formulation.In this paper, we report a condition on the suitable domain for developing efficient SVM image coding schemes. We analytically demonstrate that no linear domain fulfills this condition because of the statistical and perceptual inter-coefficient relations that exist in these domains. This theoretical result is experimentally confirmed by comparing SVM learning in previously reported linear domains and in a recently proposed non-linear perceptual domain that simultaneously reduces the statistical and perceptual relations (so it is closer to fulfilling the proposed condition). These results highlight the relevance of an appropriate choice of the image representation before SVM learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {49–66},
numpages = {18}
}

@article{10.5555/1390681.1390683,
author = {Rieck, Konrad and Laskov, Pavel},
title = {Linear-Time Computation of Similarity Measures for Sequential Data},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Efficient and expressive comparison of sequences is an essential procedure for learning with sequential data. In this article we propose a generic framework for computation of similarity measures for sequences, covering various kernel, distance and non-metric similarity functions. The basis for comparison is embedding of sequences using a formal language, such as a set of natural words, k-grams or all contiguous subsequences. As realizations of the framework we provide linear-time algorithms of different complexity and capabilities using sorted arrays, tries and suffix trees as underlying data structures.Experiments on data sets from bioinformatics, text processing and computer security illustrate the efficiency of the proposed algorithms---enabling peak performances of up to 106 pairwise comparisons per second. The utility of distances and non-metric similarity measures for sequences as alternatives to string kernels is demonstrated in applications of text categorization, network intrusion detection and transcription site recognition in DNA.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {23–48},
numpages = {26}
}

@article{10.5555/1390681.1390682,
author = {Chechik, Gal and Heitz, Geremy and Elidan, Gal and Abbeel, Pieter and Koller, Daphne},
title = {Max-Margin Classification of Data with Absent Features},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We consider the problem of learning classifiers in structured domains, where some objects have a subset of features that are inherently absent due to complex relationships between the features. Unlike the case where a feature exists but its value is not observed, here we focus on the case where a feature may not even exist (structurally absent) for some of the samples. The common approach for handling missing features in discriminative models is to first complete their unknown values, and then use a standard classification procedure over the completed data. This paper focuses on features that are known to be non-existing, rather than have an unknown value. We show how incomplete data can be classified directly without any completion of the missing features using a max-margin learning framework. We formulate an objective function, based on the geometric interpretation of the margin, that aims to maximize the margin of each sample in its own relevant subspace. In this formulation, the linearly separable case can be transformed into a binary search over a series of second order cone programs (SOCP), a convex problem that can be solved efficiently. We also describe two approaches for optimizing the general case: an approximation that can be solved as a standard quadratic program (QP) and an iterative approach for solving the exact problem. By avoiding the pre-processing phase in which the data is completed, both of these approaches could offer considerable computational savings. More importantly, we show that the elegant handling of missing values by our approach allows it to both outperform other methods when the missing values have non-trivial structure, and be competitive with other methods when the values are missing at random. We demonstrate our results on several standard benchmarks and two real-world problems: edge prediction in metabolic pathways, and automobile detection in natural images.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1–21},
numpages = {21}
}

@article{10.5555/1314498.1390333,
author = {Kolter, J. Zico and Maloof, Marcus A.},
title = {Dynamic Weighted Majority: An Ensemble Method for Drifting Concepts},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We present an ensemble method for concept drift that dynamically creates and removes weighted experts in response to changes in performance. The method, dynamic weighted majority (*DWM*), uses four mechanisms to cope with concept drift: It trains online learners of the ensemble, it weights those learners based on their performance, it removes them, also based on their performance, and it adds new experts based on the global performance of the ensemble. After an extensive evaluation---consisting of five experiments, eight learners, and thirty data sets that varied in type of target concept, size, presence of noise, and the like---we concluded that *DWM* outperformed other learners that only incrementally learn concept descriptions, that maintain and use previously encountered examples, and that employ an unweighted, fixed-size ensemble of experts.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2755–2790},
numpages = {36}
}

@article{10.5555/1314498.1390332,
author = {Hue, Carine and Boull\'{e}, Marc},
title = {A New Probabilistic Approach in Rank Regression with Optimal Bayesian Partitioning},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In this paper, we consider the supervised learning task which consists in predicting the normalized rank of a numerical variable. We introduce a novel probabilistic approach to estimate the posterior distribution of the target rank conditionally to the predictors. We turn this learning task into a model selection problem. For that, we define a 2D partitioning family obtained by discretizing numerical variables and grouping categorical ones and we derive an analytical criterion to select the partition with the highest posterior probability. We show how these partitions can be used to build univariate predictors and multivariate ones under a naive Bayes assumption.We also propose a new evaluation criterion for probabilistic rank estimators. Based on the logarithmic score, we show that such criterion presents the advantage to be minored, which is not the case of the logarithmic score computed for probabilistic value estimator.A first set of experimentations on synthetic data shows the good properties of the proposed criterion and of our partitioning approach. A second set of experimentations on real data shows competitive performance of the univariate and selective naive Bayes rank estimators projected on the value range compared to methods submitted to a recent challenge on probabilistic metric regression tasks.Our approach is applicable for all regression problems with categorical or numerical predictors. It is particularly interesting for those with a high number of predictors as it automatically detects the variables which contain predictive information. It builds pertinent predictors of the normalized rank of the numerical target from one or several predictors. As the criteria selection is regularized by the presence of a prior and a posterior term, it does not suffer from overfitting.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2727–2754},
numpages = {28}
}

@article{10.5555/1314498.1390331,
author = {Zhao, Peng and Yu, Bin},
title = {Stagewise Lasso},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Many statistical machine learning algorithms minimize either an empirical loss function as in AdaBoost, or a penalized empirical loss as in Lasso or SVM. A single regularization tuning parameter controls the trade-off between fidelity to the data and generalizability, or equivalently between bias and variance. When this tuning parameter changes, a regularization "path" of solutions to the minimization problem is generated, and the whole path is needed to select a tuning parameter to optimize the prediction or interpretation performance. Algorithms such as homotopy-Lasso or LARS-Lasso and Forward Stagewise Fitting (FSF) (aka e-Boosting) are of great interest because of their resulted sparse models for interpretation in addition to prediction.In this paper, we propose the BLasso algorithm that ties the FSF (e-Boosting) algorithm with the Lasso method that minimizes the L1 penalized L2 loss. BLasso is derived as a coordinate descent method with a fixed stepsize applied to the general Lasso loss function (L1 penalized convex loss). It consists of both a forward step and a backward step. The forward step is similar to e-Boosting or FSF, but the backward step is new and revises the FSF (or e-Boosting) path to approximate the Lasso path. In the cases of a finite number of base learners and a bounded Hessian of the loss function, the BLasso path is shown to converge to the Lasso path when the stepsize goes to zero. For cases with a larger number of base learners than the sample size and when the true model is sparse, our simulations indicate that the BLasso model estimates are sparser than those from FSF with comparable or slightly better prediction performance, and that the the discrete stepsize of BLasso and FSF has an additional regularization effect in terms of prediction and sparsity. Moreover, we introduce the Generalized BLasso algorithm to minimize a general convex loss penalized by a general convex function. Since the (Generalized) BLasso relies only on differences not derivatives, we conclude that it provides a class of simple and easy-to-implement algorithms for tracing the regularization or solution paths of penalized minimization problems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2701–2726},
numpages = {26}
}

@article{10.5555/1314498.1390330,
author = {Cl\'{e}men\c{c}on, St\'{e}phan and Vayatis, Nicolas},
title = {Ranking the Best Instances},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We formulate a local form of the bipartite ranking problem where the goal is to focus on the best instances. We propose a methodology based on the construction of real-valued scoring functions. We study empirical risk minimization of dedicated statistics which involve empirical quantiles of the scores. We first state the problem of finding the best instances which can be cast as a classification problem with mass constraint. Next, we develop special performance measures for the local ranking problem which extend the Area Under an ROC Curve (AUC) criterion and describe the optimal elements of these new criteria. We also highlight the fact that the goal of ranking the best instances cannot be achieved in a stage-wise manner where first, the best instances would be tentatively identified and then a standard AUC criterion could be applied. Eventually, we state preliminary statistical results for the local ranking problem.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2671–2699},
numpages = {29}
}

@article{10.5555/1314498.1390329,
author = {Ghavamzadeh, Mohammad and Mahadevan, Sridhar},
title = {Hierarchical Average Reward Reinforcement Learning},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Hierarchical reinforcement learning (HRL) is a general framework for scaling reinforcement learning (RL) to problems with large state and action spaces by using the task (or action) structure to restrict the space of policies. Prior work in HRL including HAMs, options, MAXQ, and PHAMs has been limited to the discrete-time discounted reward semi-Markov decision process (SMDP) model. The average reward optimality criterion has been recognized to be more appropriate for a wide class of continuing tasks than the discounted framework. Although average reward RL has been studied for decades, prior work has been largely limited to flat policy representations.In this paper, we develop a framework for HRL based on the average reward optimality criterion. We investigate two formulations of HRL based on the average reward SMDP model, both for discrete-time and continuous-time. These formulations correspond to two notions of optimality that have been previously explored in HRL: hierarchical optimality and recursive optimality. We present algorithms that learn to find hierarchically and recursively optimal average reward policies under discrete-time and continuous-time average reward SMDP models.We use two automated guided vehicle (AGV) scheduling tasks as experimental testbeds to study the empirical performance of the proposed algorithms. The first problem is a relatively simple AGV scheduling task, in which the hierarchically and recursively optimal policies are different. We compare the proposed algorithms with three other HRL methods, including a hierarchically optimal discounted reward algorithm and a recursively optimal discounted reward algorithm on this problem. The second problem is a larger AGV scheduling task. We model this problem using both discrete-time and continuous-time models. We use a hierarchical task decomposition in which the hierarchically and recursively optimal policies are the same for this problem. We compare the performance of the proposed algorithms with a hierarchically optimal discounted reward algorithm and a recursively optimal discounted reward algorithm, as well as a non-hierarchical average reward algorithm. The results show that the proposed hierarchical average reward algorithms converge to the same performance as their discounted reward counterparts.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2629–2669},
numpages = {41}
}

@article{10.5555/1314498.1390328,
author = {N\'{u}\~{n}ez, Marlon and Fidalgo, Ra\'{u}l and Morales, Rafael},
title = {Learning in Environments with Unknown Dynamics: Towards More Robust Concept Learners},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In the process of concept learning, target concepts may have portions with short-term changes, other portions may support long-term changes, and yet others may not change at all. For this reason several local windows need to be handled. We suggest facing this problem, which naturally exists in the field of concept learning, by allocating windows which can adapt their size to portions of the target concept. We propose an incremental decision tree that is updated with incoming examples. Each leaf of the decision tree holds a time window and a local performance measure as the main parameter to be controlled. When the performance of a leaf decreases, the size of its local window is reduced. This learning algorithm, called OnlineTree2, automatically adjusts its internal parameters in order to face the current dynamics of the data stream. Results show that it is comparable to other batch algorithms when facing problems with no concept change, and it is better than evaluated methods in its ability to deal with concept drift when dealing with problems in which: concept change occurs at different speeds, noise may be present and, examples may arrive from different areas of the problem domain (virtual drift).},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2595–2628},
numpages = {34}
}

@article{10.5555/1314498.1390327,
author = {Guermeur, Yann},
title = {VC Theory of Large Margin Multi-Category Classifiers},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In the context of discriminant analysis, Vapnik's statistical learning theory has mainly been developed in three directions: the computation of dichotomies with binary-valued functions, the computation of dichotomies with real-valued functions, and the computation of polytomies with functions taking their values in finite sets, typically the set of categories itself. The case of classes of vector-valued functions used to compute polytomies has seldom been considered independently, which is unsatisfactory, for three main reasons. First, this case encompasses the other ones. Second, it cannot be treated appropriately through a na\"{\i}ve extension of the results devoted to the computation of dichotomies. Third, most of the classification problems met in practice involve multiple categories.In this paper, a VC theory of large margin multi-category classifiers is introduced. Central in this theory are generalized VC dimensions called the γ-Ψ-dimensions. First, a uniform convergence bound on the risk of the classifiers of interest is derived. The capacity measure involved in this bound is a covering number. This covering number can be upper bounded in terms of the γ-Ψ-dimensions thanks to generalizations of Sauer's lemma, as is illustrated in the specific case of the scale-sensitive Natarajan dimension. A bound on this latter dimension is then computed for the class of functions on which multi-class SVMs are based. This makes it possible to apply the structural risk minimization inductive principle to those machines.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2551–2594},
numpages = {44}
}

@article{10.5555/1314498.1390326,
author = {Hussain, Zakria and Laviolette, Fran\c{c}ois and Marchand, Mario and Shawe-Taylor, John and Brubaker, Spencer Charles and Mullin, Matthew D.},
title = {Revised Loss Bounds for the Set Covering Machine and Sample-Compression Loss Bounds for Imbalanced Data},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Marchand and Shawe-Taylor (2002) have proposed a loss bound for the set covering machine that has the property to depend on the observed fraction of positive examples and on what the classifier achieves on the positive training examples. We show that this loss bound is incorrect. We then propose a loss bound, valid for any sample-compression learning algorithm (including the set covering machine), that depends on the observed fraction of positive examples and on what the classifier achieves on them. We also compare numerically the loss bound proposed in this paper with the incorrect bound, the original SCM bound and a recently proposed loss bound of Marchand and Sokolova (2005) (which does not depend on the observed fraction of positive examples) and show that the latter loss bounds can be substantially larger than the new bound in the presence of imbalanced misclassifications.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2533–2549},
numpages = {17}
}

@article{10.5555/1314498.1390325,
author = {Tewari, Ambuj and Bartlett, Peter L.},
title = {On the Consistency of Multiclass Classification Methods},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Binary classification is a well studied special case of the classification problem. Statistical properties of binary classifiers, such as consistency, have been investigated in a variety of settings. Binary classification methods can be generalized in many ways to handle multiple classes. It turns out that one can lose consistency in generalizing a binary classification method to deal with multiple classes. We study a rich family of multiclass methods and provide a necessary and sufficient condition for their consistency. We illustrate our approach by applying it to some multiclass methods proposed in the literature.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1007–1025},
numpages = {19}
}

@article{10.5555/1314498.1390324,
author = {Sugiyama, Masashi and Krauledat, Matthias and M\"{u}ller, Klaus-Robert},
title = {Covariate Shift Adaptation by Importance Weighted Cross Validation},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {A common assumption in supervised learning is that the input points in the training set follow the same probability distribution as the input points that will be given in the future test phase. However, this assumption is not satisfied, for example, when the outside of the training region is extrapolated. The situation where the training input points and test input points follow different distributions while the conditional distribution of output values given input points is unchanged is called the covariate shift. Under the covariate shift, standard model selection techniques such as cross validation do not work as desired since its unbiasedness is no longer maintained. In this paper, we propose a new method called importance weighted cross validation (IWCV), for which we prove its unbiasedness even under the covariate shift. The IWCV procedure is the only one that can be applied for unbiased classification under covariate shift, whereas alternatives to IWCV exist for regression. The usefulness of our proposed method is illustrated by simulations, and furthermore demonstrated in the brain-computer interface, where strong non-stationarity effects can be seen between training and test sessions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {985–1005},
numpages = {21}
}

@article{10.5555/1314498.1314579,
author = {Li, Ping and Hastie, Trevor J. and Church, Kenneth W.},
title = {Nonlinear Estimators and Tail Bounds for Dimension Reduction in <i>l</i><sub>1</sub> Using Cauchy Random Projections},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {For dimension reduction in the l1 norm, the method of Cauchy random projections multiplies the original data matrix A ∈ ℝn\texttimes{}D with a random matrix R ∈ ℝD\texttimes{}k (k≪D) whose entries are i.i.d. samples of the standard Cauchy C(0,1). Because of the impossibility result, one can not hope to recover the pairwise l1 distances in A from B=A\texttimes{}R∈ ℝn\texttimes{}k, using linear estimators without incurring large errors. However, nonlinear estimators are still useful for certain applications in data stream computations, information retrieval, learning, and data mining.We study three types of nonlinear estimators: the sample median estimators, the geometric mean estimators, and the maximum likelihood estimators (MLE). We derive tail bounds for the geometric mean estimators and establish that k = O(log n / ε2) suffices with the constants explicitly given. Asymptotically (as k→∞), both the sample median and the geometric mean estimators are about 80% efficient compared to the MLE. We analyze the moments of the MLE and propose approximating its distribution of by an inverse Gaussian.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2497–2532},
numpages = {36}
}

@article{10.5555/1314498.1314578,
author = {Dinuzzo, Francesco and Neve, Marta and Nicolao, Giuseppe De and Gianazza, Ugo Pietro},
title = {On the Representer Theorem and Equivalent Degrees of Freedom of SVR},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Support Vector Regression (SVR) for discrete data is considered. An alternative formulation of the representer theorem is derived. This result is based on the newly introduced notion of pseudoresidual and the use of subdifferential calculus. The representer theorem is exploited to analyze the sensitivity properties of ε-insensitive SVR and introduce the notion of approximate degrees of freedom. The degrees of freedom are shown to play a key role in the evaluation of the optimism, that is the difference between the expected in-sample error and the expected empirical risk. In this way, it is possible to define a Cp-like statistic that can be used for tuning the parameters of SVR. The proposed tuning procedure is tested on a simulated benchmark problem and on a real world problem (Boston Housing data set).},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2467–2495},
numpages = {29}
}

@article{10.5555/1314498.1314577,
author = {Sonnenburg, S\"{o}ren and Braun, Mikio L. and Ong, Cheng Soon and Bengio, Samy and Bottou, Leon and Holmes, Geoffrey and LeCun, Yann and M\"{u}ller, Klaus-Robert and Pereira, Fernando and Rasmussen, Carl Edward and R\"{a}tsch, Gunnar and Sch\"{o}lkopf, Bernhard and Smola, Alexander and Vincent, Pascal and Weston, Jason and Williamson, Robert},
title = {The Need for Open Source Software in Machine Learning},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Open source tools have recently reached a level of maturity which makes them suitable for building large-scale real-world systems. At the same time, the field of machine learning has developed a large body of powerful learning algorithms for diverse applications. However, the true potential of these methods is not used, since existing implementations are not openly shared, resulting in software with low usability, and weak interoperability. We argue that this situation can be significantly improved by increasing incentives for researchers to publish their software under an open source model. Additionally, we outline the problems authors are faced with when trying to publish algorithmic implementations of machine learning methods. We believe that a resource of peer reviewed software accompanied by short articles would be highly valuable to both the machine learning and the general scientific community.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2443–2466},
numpages = {24}
}

@article{10.5555/1314498.1314576,
author = {Lebanon, Guy and Mao, Yi and Dillon, Joshua},
title = {The Locally Weighted Bag of Words Framework for Document Representation},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The popular bag of words assumption represents a document as a histogram of word occurrences. While computationally efficient, such a representation is unable to maintain any sequential information. We present an effective sequential document representation that goes beyond the bag of words representation and its n-gram extensions. This representation uses local smoothing to embed documents as smooth curves in the multinomial simplex thereby preserving valuable sequential information. In contrast to bag of words or n-grams, the new representation is able to robustly capture medium and long range sequential trends in the document. We discuss the representation and its geometric properties and demonstrate its applicability for various text processing tasks.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2405–2441},
numpages = {37}
}

@article{10.5555/1314498.1314575,
author = {Gy\"{o}rgy, Andr\'{a}s and Linder, Tam\'{a}s and Lugosi, G\'{a}bor and Ottucs\'{a}k, Gy\"{o}rgy},
title = {The On-Line Shortest Path Problem Under Partial Monitoring},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defined as the sum of the weights of its composing edges) be as small as possible. In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the weights of those edges that belong to the chosen path. For this problem, an algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire sequence of the edge weights, by a quantity that is proportional to 1/√n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with complexity that is linear in the number of rounds n (i.e., the average complexity per round is constant) and in the number of edges. An extension to the so-called label efficient setting is also given, in which the decision maker is informed about the weights of the edges corresponding to the chosen path at a total of m ≪ n time instances. Another extension is shown where the decision maker competes against a time-varying path, a generalization of the problem of tracking the best expert. A version of the multi-armed bandit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results are also presented.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2369–2403},
numpages = {35}
}

@article{10.5555/1314498.1314574,
author = {Bartlett, Peter L. and Traskin, Mikhail},
title = {AdaBoost is Consistent},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The risk, or probability of error, of the classifier produced by the AdaBoost algorithm is investigated. In particular, we consider the stopping strategy to be used in AdaBoost to achieve universal consistency. We show that provided AdaBoost is stopped after n1-ε iterations---for sample size n and ε ∈ (0,1)---the sequence of risks of the classifiers it produces approaches the Bayes risk.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2347–2368},
numpages = {22}
}

@article{10.5555/1314498.1314573,
author = {Gabrilovich, Evgeniy and Markovitch, Shaul},
title = {Harnessing the Expertise of 70,000 Human Editors: Knowledge-Based Feature Generation for Text Categorization},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Most existing methods for text categorization employ induction algorithms that use the words appearing in the training documents as features. While they perform well in many categorization tasks, these methods are inherently limited when faced with more complicated tasks where external knowledge is essential. Recently, there have been efforts to augment these basic features with external knowledge, including semi-supervised learning and transfer learning. In this work, we present a new framework for automatic acquisition of world knowledge and methods for incorporating it into the text categorization process. Our approach enhances machine learning algorithms with features generated from domain-specific and common-sense knowledge. This knowledge is represented by ontologies that contain hundreds of thousands of concepts, further enriched through controlled Web crawling. Prior to text categorization, a feature generator analyzes the documents and maps them onto appropriate ontology concepts that augment the bag of words used in simple supervised learning. Feature generation is accomplished through contextual analysis of document text, thus implicitly performing word sense disambiguation. Coupled with the ability to generalize concepts using the ontology, this approach addresses two significant problems in natural language processing---synonymy and polysemy. Categorizing documents with the aid of knowledge-based features leverages information that cannot be deduced from the training documents alone. We applied our methodology using the Open Directory Project, the largest existing Web directory built by over 70,000 human editors. Experimental results over a range of data sets confirm improved performance compared to the bag of words document representation.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2297–2345},
numpages = {49}
}

@article{10.5555/1314498.1314572,
author = {Globerson, Amir and Chechik, Gal and Pereira, Fernando and Tishby, Naftali},
title = {Euclidean Embedding of Co-Occurrence Data},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Embedding algorithms search for a low dimensional continuous representation of data, but most algorithms only handle objects of a single type for which pairwise distances are specified. This paper describes a method for embedding objects of different types, such as images and text, into a single common Euclidean space, based on their co-occurrence statistics. The joint distributions are modeled as exponentials of Euclidean distances in the low-dimensional embedding space, which links the problem to convex optimization over positive semidefinite matrices. The local structure of the embedding corresponds to the statistical correlations via random walks in the Euclidean space. We quantify the performance of our method on two text data sets, and show that it consistently and significantly outperforms standard methods of statistical correspondence modeling, such as multidimensional scaling, IsoMap and correspondence analysis.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2265–2295},
numpages = {31}
}

@article{10.5555/1314498.1314571,
author = {Dekel, Ofer and Long, Philip M. and Singer, Yoram},
title = {Online Learning of Multiple Tasks with a Shared Loss},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We study the problem of learning multiple tasks in parallel within the online learning framework. On each online round, the algorithm receives an instance for each of the parallel tasks and responds by predicting the label of each instance. We consider the case where the predictions made on each round all contribute toward a common goal. The relationship between the various tasks is defined by a global loss function, which evaluates the overall quality of the multiple predictions made on each round. Specifically, each individual prediction is associated with its own loss value, and then these multiple loss values are combined into a single number using the global loss function. We focus on the case where the global loss function belongs to the family of absolute norms, and present several online learning algorithms for the induced problem. We prove worst-case relative loss bounds for all of our algorithms, and demonstrate the effectiveness of our approach on a large-scale multiclass-multilabel text categorization problem.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2233–2264},
numpages = {32}
}

@article{10.5555/1314498.1314570,
author = {Mahadevan, Sridhar and Maggioni, Mauro},
title = {Proto-Value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {This paper introduces a novel spectral framework for solving Markov decision processes (MDPs) by jointly learning representations and optimal policies. The major components of the framework described in this paper include: (i) A general scheme for constructing representations or basis functions by diagonalizing symmetric diffusion operators (ii) A specific instantiation of this approach where global basis functions called proto-value functions (PVFs) are formed using the eigenvectors of the graph Laplacian on an undirected graph formed from state transitions induced by the MDP (iii) A three-phased procedure called representation policy iteration comprising of a sample collection phase, a representation learning phase that constructs basis functions from samples, and a final parameter estimation phase that determines an (approximately) optimal policy within the (linear) subspace spanned by the (current) basis functions. (iv) A specific instantiation of the RPI framework using least-squares policy iteration (LSPI) as the parameter estimation method (v) Several strategies for scaling the proposed approach to large discrete and continuous state spaces, including the Nystr\"{o}m extension for out-of-sample interpolation of eigenfunctions, and the use of Kronecker sum factorization to construct compact eigenfunctions in product spaces such as factored MDPs (vi) Finally, a series of illustrative discrete and continuous control tasks, which both illustrate the concepts and provide a benchmark for evaluating the proposed approach. Many challenges remain to be addressed in scaling the proposed framework to large MDPs, and several elaboration of the proposed framework are briefly summarized at the end.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2169–2231},
numpages = {63}
}

@article{10.5555/1314498.1314569,
author = {Taylor, Matthew E. and Stone, Peter and Liu, Yaxin},
title = {Transfer Learning via Inter-Task Mappings for Temporal Difference Learning},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Temporal difference (TD) learning (Sutton and Barto, 1998) has become a popular reinforcement learning technique in recent years. TD methods, relying on function approximators to generalize learning to novel situations, have had some experimental successes and have been shown to exhibit some desirable properties in theory, but the most basic algorithms have often been found slow in practice. This empirical result has motivated the development of many methods that speed up reinforcement learning by modifying a task for the learner or helping the learner better generalize to novel situations. This article focuses on generalizing across tasks, thereby speeding up learning, via a novel form of transfer using handcoded task relationships. We compare learning on a complex task with three function approximators, a cerebellar model arithmetic computer (CMAC), an artificial neural network (ANN), and a radial basis function (RBF), and empirically demonstrate that directly transferring the action-value function can lead to a dramatic speedup in learning with all three. Using transfer via inter-task mapping (TVITM), agents are able to learn one task and then markedly reduce the time it takes to learn a more complex task. Our algorithms are fully implemented and tested in the RoboCup soccer Keepaway domain.This article contains and extends material published in two conference papers (Taylor and Stone, 2005; Taylor et al., 2005).},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2125–2167},
numpages = {43}
}

@article{10.5555/1314498.1314568,
author = {Loog, Marco},
title = {A Complete Characterization of a Family of Solutions to a Generalized Fisher Criterion},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Recently, Ye (2005) suggested yet another optimization criterion for discriminant analysis and proposed a characterization of the family of solutions to this objective. The characterization, however, merely describes a part of the full solution set, that is, it is not complete and therefore not at all a characterization. This correspondence first gives the correct characterization and afterwards compares it to Ye's.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2121–2123},
numpages = {3}
}

@article{10.5555/1314498.1314567,
author = {Xu, Yuesheng and Zhang, Haizhang},
title = {Refinable Kernels},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Motivated by mathematical learning from training data, we introduce the notion of refinable kernels. Various characterizations of refinable kernels are presented. The concept of refinable kernels leads to the introduction of wavelet-like reproducing kernels. We also investigate a refinable kernel that forms a Riesz basis. In particular, we characterize refinable translation invariant kernels, and refinable kernels defined by refinable functions. This study leads to multiresolution analysis of reproducing kernel Hilbert spaces.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2083–2120},
numpages = {38}
}

@article{10.5555/1314498.1314566,
author = {Kuzmin, Dima and Warmuth, Manfred K.},
title = {Unlabeled Compression Schemes for Maximum Classes},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Maximum concept classes of VC dimension d over n domain points have size n C ≤d, and this is an upper bound on the size of any concept class of VC dimension d over n points. We give a compression scheme for any maximum class that represents each concept by a subset of up to d unlabeled domain points and has the property that for any sample of a concept in the class, the representative of exactly one of the concepts consistent with the sample is a subset of the domain of the sample. This allows us to compress any sample of a concept in the class to a subset of up to d unlabeled sample points such that this subset represents a concept consistent with the entire original sample. Unlike the previously known compression scheme for maximum classes (Floyd and Warmuth, 1995) which compresses to labeled subsets of the sample of size equal d, our new scheme is tight in the sense that the number of possible unlabeled compression sets of size at most d equals the number of concepts in the class.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2047–2081},
numpages = {35}
}

@article{10.5555/1314498.1314565,
author = {Chariatis, Aggelos},
title = {Very Fast Online Learning of Highly Non Linear Problems},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The experimental investigation on the efficient learning of highly non-linear problems by online training, using ordinary feed forward neural networks and stochastic gradient descent on the errors computed by back-propagation, gives evidence that the most crucial factors for efficient training are the hidden units' differentiation, the attenuation of the hidden units' interference and the selective attention on the parts of the problems where the approximation error remains high. In this report, we present global and local selective attention techniques and a new hybrid activation function that enables the hidden units to acquire individual receptive fields which may be global or local depending on the problem's local complexities. The presented techniques enable very efficient training on complex classification problems with embedded subproblems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2017–2045},
numpages = {29}
}

@article{10.5555/1314498.1314564,
author = {G\'{o}mez, Vicen\c{c} and Mooij, Joris M. and Kappen, Hilbert J.},
title = {Truncating the Loop Series Expansion for Belief Propagation},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Recently, Chertkov and Chernyak (2006b) derived an exact expression for the partition sum (normalization constant) corresponding to a graphical model, which is an expansion around the belief propagation (BP) solution. By adding correction terms to the BP free energy, one for each "generalized loop" in the factor graph, the exact partition sum is obtained. However, the usually enormous number of generalized loops generally prohibits summation over all correction terms. In this article we introduce truncated loop series BP (TLSBP), a particular way of truncating the loop series of Chertkov & Chernyak by considering generalized loops as compositions of simple loops. We analyze the performance of TLSBP in different scenarios, including the Ising model on square grids and regular random graphs, and on PROMEDAS, a large probabilistic medical diagnostic system. We show that TLSBP often improves upon the accuracy of the BP solution, at the expense of increased computation time. We also show that the performance of TLSBP strongly depends on the degree of interaction between the variables. For weak interactions, truncating the series leads to significant improvements, whereas for strong interactions it can be ineffective, even if a high number of terms is considered.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1987–2016},
numpages = {30}
}

@article{10.5555/1314498.1314563,
author = {Banerjee, Arindam and Dhillon, Inderjit and Ghosh, Joydeep and Merugu, Srujana and Modha, Dharmendra S.},
title = {A Generalized Maximum Entropy Approach to Bregman Co-Clustering and Matrix Approximation},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Co-clustering, or simultaneous clustering of rows and columns of a two-dimensional data matrix, is rapidly becoming a powerful data analysis technique. Co-clustering has enjoyed wide success in varied application domains such as text clustering, gene-microarray analysis, natural language processing and image, speech and video analysis. In this paper, we introduce a partitional co-clustering formulation that is driven by the search for a good matrix approximation---every co-clustering is associated with an approximation of the original data matrix and the quality of co-clustering is determined by the approximation error. We allow the approximation error to be measured using a large class of loss functions called Bregman divergences that include squared Euclidean distance and KL-divergence as special cases. In addition, we permit multiple structurally different co-clustering schemes that preserve various linear statistics of the original data matrix. To accomplish the above tasks, we introduce a new minimum Bregman information (MBI) principle that simultaneously generalizes the maximum entropy and standard least squares principles, and leads to a matrix approximation that is optimal among all generalized additive models in a certain natural parameter space. Analysis based on this principle yields an elegant meta algorithm, special cases of which include most previously known alternate minimization based clustering algorithms such as kmeans and co-clustering algorithms such as information theoretic (Dhillon et al., 2003b) and minimum sum-squared residue co-clustering (Cho et al., 2004). To demonstrate the generality and flexibility of our co-clustering framework, we provide examples and empirical evidence on a variety of problem domains and also describe novel co-clustering applications such as missing value prediction and compression of categorical data matrices.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1919–1986},
numpages = {68}
}

@article{10.5555/1314498.1314562,
author = {G\"{u}nter, Simon and Schraudolph, Nicol N. and Vishwanathan, S. V. N.},
title = {Fast Iterative Kernel Principal Component Analysis},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We develop gain adaptation methods that improve convergence of the kernel Hebbian algorithm (KHA) for iterative kernel PCA (Kim et al., 2005). KHA has a scalar gain parameter which is either held constant or decreased according to a predetermined annealing schedule, leading to slow convergence. We accelerate it by incorporating the reciprocal of the current estimated eigenvalues as part of a gain vector. An additional normalization term then allows us to eliminate a tuning parameter in the annealing schedule. Finally we derive and apply stochastic meta-descent (SMD) gain vector adaptation (Schraudolph, 1999, 2002) in reproducing kernel Hilbert space to further speed up convergence. Experimental results on kernel PCA and spectral clustering of USPS digits, motion capture and image denoising, and image super-resolution tasks confirm that our methods converge substantially faster than conventional KHA. To demonstrate scalability, we perform kernel PCA on the entire MNIST data set.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1893–1918},
numpages = {26}
}

@article{10.5555/1314498.1314561,
author = {Wang, Junhui and Shen, Xiaotong},
title = {Large Margin Semi-Supervised Learning},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In classification, semi-supervised learning occurs when a large amount of unlabeled data is available with only a small number of labeled data. In such a situation, how to enhance predictability of classification through unlabeled data is the focus. In this article, we introduce a novel large margin semi-supervised learning methodology, using grouping information from unlabeled data, together with the concept of margins, in a form of regularization controlling the interplay between labeled and unlabeled data. Based on this methodology, we develop two specific machines involving support vector machines and ψ-learning, denoted as SSVM and SPSI, through difference convex programming. In addition, we estimate the generalization error using both labeled and unlabeled data, for tuning regularizers. Finally, our theoretical and numerical analyses indicate that the proposed methodology achieves the desired objective of delivering high performance in generalization, particularly against some strong performers.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1867–1891},
numpages = {25}
}

@article{10.5555/1314498.1314560,
author = {Chhabra, Manu and Jacobs, Robert A. and \v{S}tefankovi\v{c}, Daniel},
title = {Behavioral Shaping for Geometric Concepts},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In a search problem, an agent uses the membership oracle of a target concept to find a positive example of the concept. In a shaped search problem the agent is aided by a sequence of increasingly restrictive concepts leading to the target concept (analogous to behavioral shaping). The concepts are given by membership oracles, and the agent has to find a positive example of the target concept while minimizing the total number of oracle queries. We show that for the concept class of intervals on the real line an agent using a bounded number of queries per oracle exists. In contrast, for the concept class of unions of two intervals on the real line no agent with a bounded number of queries per oracle exists. We then investigate the (amortized) number of queries per oracle needed for the shaped search problem over other concept classes. We explore the following methods to obtain efficient agents. For axis-parallel rectangles we use a bootstrapping technique to obtain gradually better approximations of the target concept. We show that given rectangles R ⊆ A ⊆ ℝd one can obtain a rectangle A' ⊇ R with vol(A') / vol(R) ≤ 2, using only O(d ⋅ vol(A) / vol(R)) random samples from A. For ellipsoids of bounded eccentricity in ℝd we analyze a deterministic ray-shooting process which uses a sequence of rays to get close to the centroid. Finally, we use algorithms for generating random points in convex bodies (Dyer et al., 1991; Kannan et al., 1997) to give a randomized agent for the concept class of convex bodies. In the final section, we explore connections between our bootstrapping method and active learning. Specifically, we use the bootstrapping technique for axis-parallel rectangles to active learn axis-parallel rectangles under the uniform distribution in O(d ln(1/ε)) labeled samples.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1835–1865},
numpages = {31}
}

@article{10.5555/1314498.1314559,
author = {Elidan, Gal and Nachman, Iftach and Friedman, Nir},
title = {"Ideal Parent" Structure Learning for Continuous Variable Bayesian Networks},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Bayesian networks in general, and continuous variable networks in particular, have become increasingly popular in recent years, largely due to advances in methods that facilitate automatic learning from data. Yet, despite these advances, the key task of learning the structure of such models remains a computationally intensive procedure, which limits most applications to parameter learning. This problem is even more acute when learning networks in the presence of missing values or hidden variables, a scenario that is part of many real-life problems. In this work we present a general method for speeding structure search for continuous variable networks with common parametric distributions. We efficiently evaluate the approximate merit of candidate structure modifications and apply time consuming (exact) computations only to the most promising ones, thereby achieving significant improvement in the running time of the search algorithm. Our method also naturally and efficiently facilitates the addition of useful new hidden variables into the network structure, a task that is typically considered both conceptually difficult and computationally prohibitive. We demonstrate our method on synthetic and real-life data sets, both for learning structure on fully and partially observable data, and for introducing new hidden variables during structure search.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1799–1833},
numpages = {35}
}

@article{10.5555/1314498.1314558,
author = {Pillai, Natesh S. and Wu, Qiang and Liang, Feng and Mukherjee, Sayan and Wolpert, Robert L.},
title = {Characterizing the Function Space for Bayesian Kernel Models},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Kernel methods have been very popular in the machine learning literature in the last ten years, mainly in the context of Tikhonov regularization algorithms. In this paper we study a coherent Bayesian kernel model based on an integral operator defined as the convolution of a kernel with a signed measure. Priors on the random signed measures correspond to prior distributions on the functions mapped by the integral operator. We study several classes of signed measures and their image mapped by the integral operator. In particular, we identify a general class of measures whose image is dense in the reproducing kernel Hilbert space (RKHS) induced by the kernel. A consequence of this result is a function theoretic foundation for using non-parametric prior specifications in Bayesian modeling, such as Gaussian process and Dirichlet process prior distributions. We discuss the construction of priors on spaces of signed measures using Gaussian and L\'{e}vy processes, with the Dirichlet processes being a special case the latter. Computational issues involved with sampling from the posterior distribution are outlined for a univariate regression and a high dimensional classification problem.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1769–1797},
numpages = {29}
}

@article{10.5555/1314498.1314557,
author = {Hickey, Ray J.},
title = {Structure and Majority Classes in Decision Tree Learning},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {To provide good classification accuracy on unseen examples, a decision tree, learned by an algorithm such as ID3, must have sufficient structure and also identify the correct majority class in each of its leaves. If there are inadequacies in respect of either of these, the tree will have a percentage classification rate below that of the maximum possible for the domain, namely (100 - Bayes error rate). An error decomposition is introduced which enables the relative contributions of deficiencies in structure and in incorrect determination of majority class to be isolated and quantified. A sub-decomposition of majority class error permits separation of the sampling error at the leaves from the possible bias introduced by the attribute selection method of the induction algorithm. It is shown that sampling error can extend to 25% when there are more than two classes. Decompositions are obtained from experiments on several data sets. For ID3, the effect of selection bias is shown to vary from being statistically non-significant to being quite substantial, with the latter appearing to be associated with a simple underlying model.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1747–1768},
numpages = {22}
}

@article{10.5555/1314498.1314556,
author = {Clark, Alexander and Eyraud, R\'{e}mi},
title = {Polynomial Identification in the Limit of Substitutable Context-Free Languages},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {This paper formalises the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free languages. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. It transpires that it is not necessary to identify constituents in order to learn a context-free language—it is sufficient to identify the syntactic congruence, and the operations of the syntactic monoid can be converted into a context-free grammar. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin's notion of reversibility for regular languages. We also demonstrate that an implementation of this algorithm is capable of learning a classic example of structure dependent syntax in English: this constitutes a refutation of an argument that has been used in support of nativist theories of language.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1725–1745},
numpages = {21}
}

@article{10.5555/1314498.1314555,
author = {Li, Jia and Ray, Surajit and Lindsay, Bruce G.},
title = {A Nonparametric Statistical Approach to Clustering via Mode Identification},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {A new clustering approach based on mode identification is developed by applying new optimization techniques to a nonparametric density estimator. A cluster is formed by those sample points that ascend to the same local maximum (mode) of the density function. The path from a point to its associated mode is efficiently solved by an EM-style algorithm, namely, the Modal EM (MEM). This method is then extended for hierarchical clustering by recursively locating modes of kernel density estimators with increasing bandwidths. Without model fitting, the mode-based clustering yields a density description for every cluster, a major advantage of mixture-model-based clustering. Moreover, it ensures that every cluster corresponds to a bump of the density. The issue of diagnosing clustering results is also investigated. Specifically, a pairwise separability measure for clusters is defined using the ridgeline between the density bumps of two clusters. The ridgeline is solved for by the Ridgeline EM (REM) algorithm, an extension of MEM. Based upon this new measure, a cluster merging procedure is created to enforce strong separation. Experiments on simulated and real data demonstrate that the mode-based clustering approach tends to combine the strengths of linkage and mixture-model-based clustering. In addition, the approach is robust in high dimensions and when clusters deviate substantially from Gaussian distributions. Both of these cases pose difficulty for parametric mixture modeling. A C package on the new algorithms is developed for public access at http://www.stat.psu.edu/∼jiali/hmac.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1687–1723},
numpages = {37}
}

@article{10.5555/1314498.1314554,
author = {Boull\'{e}, Marc},
title = {Compression-Based Averaging of Selective Naive Bayes Classifiers},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The naive Bayes classifier has proved to be very effective on many real data applications. Its performance usually benefits from an accurate estimation of univariate conditional probabilities and from variable selection. However, although variable selection is a desirable feature, it is prone to overfitting. In this paper, we introduce a Bayesian regularization technique to select the most probable subset of variables compliant with the naive Bayes assumption. We also study the limits of Bayesian model averaging in the case of the naive Bayes assumption and introduce a new weighting scheme based on the ability of the models to conditionally compress the class labels. The weighting scheme on the models reduces to a weighting scheme on the variables, and finally results in a naive Bayes classifier with "soft variable selection". Extensive experiments show that the compression-based averaged classifier outperforms the Bayesian model averaging scheme.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1659–1685},
numpages = {27}
}

@article{10.5555/1314498.1314553,
author = {Saar-Tsechansky, Maytal and Provost, Foster},
title = {Handling Missing Values When Applying Classification Models},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Much work has studied the effect of different treatments of missing values on model induction, but little work has analyzed treatments for the common case of missing values at prediction time. This paper first compares several different methods---predictive value imputation, the distribution-based imputation used by C4.5, and using reduced models---for applying classification trees to instances with missing values (and also shows evidence that the results generalize to bagged trees and to logistic regression). The results show that for the two most popular treatments, each is preferable under different conditions. Strikingly the reduced-models approach, seldom mentioned or used, consistently outperforms the other two methods, sometimes by a large margin. The lack of attention to reduced modeling may be due in part to its (perceived) expense in terms of computation or storage. Therefore, we then introduce and evaluate alternative, hybrid approaches that allow users to balance between more accurate but computationally expensive reduced modeling and the other, less accurate but less computationally expensive treatments. The results show that the hybrid methods can scale gracefully to the amount of investment in computation/storage, and that they outperform imputation even for small investments.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1623–1657},
numpages = {35}
}

@article{10.5555/1314498.1314552,
author = {Hamsici, Onur C. and Martinez, Aleix M.},
title = {Spherical-Homoscedastic Distributions: The Equivalency of Spherical and Normal Distributions in Classification},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Many feature representations, as in genomics, describe directional data where all feature vectors share a common norm. In other cases, as in computer vision, a norm or variance normalization step, where all feature vectors are normalized to a common length, is generally used. These representations and pre-processing step map the original data from ℜp to the surface of a hypersphere Sp-1. Such representations should then be modeled using spherical distributions. However, the difficulty associated with such spherical representations has prompted researchers to model their spherical data using Gaussian distributions instead---as if the data were represented in ℜp rather than Sp-1. This opens the question to whether the classification results calculated with the Gaussian approximation are the same as those obtained when using the original spherical distributions. In this paper, we show that in some particular cases (which we named spherical-homoscedastic) the answer to this question is positive. In the more general case however, the answer is negative. For this reason, we further investigate the additional error added by the Gaussian modeling. We conclude that the more the data deviates from spherical-homoscedastic, the less advisable it is to employ the Gaussian approximation. We then show how our derivations can be used to define optimal classifiers for spherical-homoscedastic distributions. By using a kernel which maps the original space into one where the data adapts to the spherical-homoscedastic model, we can derive non-linear classifiers with potential applications in a large number of problems. We conclude this paper by demonstrating the uses of spherical-homoscedasticity in the classification of images of objects, gene expression sequences, and text data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1583–1623},
numpages = {41}
}

@article{10.5555/1314498.1314551,
author = {Melvin, Iain and Ie, Eugene and Weston, Jason and Noble, William Stafford and Leslie, Christina},
title = {Multi-Class Protein Classification Using Adaptive Codes},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Predicting a protein's structural class from its amino acid sequence is a fundamental problem in computational biology. Recent machine learning work in this domain has focused on developing new input space representations for protein sequences, that is, string kernels, some of which give state-of-the-art performance for the binary prediction task of discriminating between one class and all the others. However, the underlying protein classification problem is in fact a huge multi-class problem, with over 1000 protein folds and even more structural subcategories organized into a hierarchy. To handle this challenging many-class problem while taking advantage of progress on the binary problem, we introduce an adaptive code approach in the output space of one-vs-the-rest prediction scores. Specifically, we use a ranking perceptron algorithm to learn a weighting of binary classifiers that improves multi-class prediction with respect to a fixed set of output codes. We use a cross-validation set-up to generate output vectors for training, and we define codes that capture information about the protein structural hierarchy. Our code weighting approach significantly improves on the standard one-vs-all method for two difficult multi-class protein classification problems: remote homology detection and fold recognition. Our algorithm also outperforms a previous code learning approach due to Crammer and Singer, trained here using a perceptron, when the dimension of the code vectors is high and the number of classes is large. Finally, we compare against PSI-BLAST, one of the most widely used methods in protein sequence analysis, and find that our method strongly outperforms it on every structure classification problem that we consider. Supplementary data and source code are available at <tt><a href="http://www.cs.columbia.edu/compbio/adaptive">http://www.cs.columbia.edu/compbio/adaptive</a></tt>.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1557–1581},
numpages = {25}
}

@article{10.5555/1314498.1314550,
author = {Koh, Kwangmoo and Kim, Seung-Jean and Boyd, Stephen},
title = {An Interior-Point Method for Large-Scale <i>l</i><sub>1</sub>-Regularized Logistic Regression},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Logistic regression with l1 regularization has been proposed as a promising method for feature selection in classification problems. In this paper we describe an efficient interior-point method for solving large-scale l1-regularized logistic regression problems. Small problems with up to a thousand or so features and examples can be solved in seconds on a PC; medium sized problems, with tens of thousands of features and examples, can be solved in tens of seconds (assuming some sparsity in the data). A variation on the basic method, that uses a preconditioned conjugate gradient method to compute the search step, can solve very large problems, with a million features and examples (e.g., the 20 Newsgroups data set), in a few minutes, on a PC. Using warm-start techniques, a good approximation of the entire regularization path can be computed much more efficiently than by solving a family of problems independently.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1519–1555},
numpages = {37}
}

@article{10.5555/1314498.1314549,
author = {Johnson, Rie and Zhang, Tong},
title = {On the Effectiveness of Laplacian Normalization for Graph Semi-Supervised Learning},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {This paper investigates the effect of Laplacian normalization in graph-based semi-supervised learning. To this end, we consider multi-class transductive learning on graphs with Laplacian regularization. Generalization bounds are derived using geometric properties of the graph. Specifically, by introducing a definition of graph cut from learning theory, we obtain generalization bounds that depend on the Laplacian regularizer. We then use this analysis to better understand the role of graph Laplacian matrix normalization. Under assumptions that the cut is small, we derive near-optimal normalization factors by approximately minimizing the generalization bounds. The analysis reveals the limitations of the standard degree-based normalization method in that the resulting normalization factors can vary significantly within each connected component with the same class label, which may cause inferior generalization performance. Our theory also suggests a remedy that does not suffer from this problem. Experiments confirm the superiority of the normalization scheme motivated by learning theory on artificial and real-world data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1489–1517},
numpages = {29}
}

@article{10.5555/1314498.1314548,
author = {Laviolette, Fran\c{c}ois and Marchand, Mario},
title = {PAC-Bayes Risk Bounds for Stochastic Averages and Majority Votes of Sample-Compressed Classifiers},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We propose a PAC-Bayes theorem for the sample-compression setting where each classifier is described by a compression subset of the training data and a message string of additional information. This setting, which is the appropriate one to describe many learning algorithms, strictly generalizes the usual data-independent setting where classifiers are represented only by data-independent message strings (or parameters taken from a continuous set). The proposed PAC-Bayes theorem for the sample-compression setting reduces to the PAC-Bayes theorem of Seeger (2002) and Langford (2005) when the compression subset of each classifier vanishes. For posteriors having all their weights on a single sample-compressed classifier, the general risk bound reduces to a bound similar to the tight sample-compression bound proposed in Laviolette et al. (2005). Finally, we extend our results to the case where each sample-compressed classifier of a data-dependent ensemble may abstain of predicting a class label.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1461–1487},
numpages = {27}
}

@article{10.5555/1314498.1314547,
author = {Feldman, Vitaly},
title = {Attribute-Efficient and Non-Adaptive Learning of Parities and DNF Expressions},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over {0,1}n. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem in coding theory. This is the first evidence that attribute-efficient learning of a natural PAC learnable concept class can be computationally hard.An algorithm is said to use membership queries (MQs) non-adaptively if the points at which the algorithm asks MQs do not depend on the target concept. Using a simple non-adaptive parity learning algorithm and a modification of Levin's algorithm for locating a weakly-correlated parity due to Bshouty et al. (1999), we give the first non-adaptive and attribute-efficient algorithm for learning DNF with respect to the uniform distribution. Our algorithm runs in time \~{O}(ns4/ε) and uses \~{O}(s4 · log2n/ε) non-adaptive MQs, where s is the number of terms in the shortest DNF representation of the target concept. The algorithm improves on the best previous algorithm for learning DNF (of Bshouty et al., 1999) and can also be easily modified to tolerate random persistent classification noise in MQs.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1431–1460},
numpages = {30}
}

@article{10.5555/1314498.1314546,
author = {Cardoso, Jaime S. and Pinto da Costa, Joaquim F.},
title = {Learning to Classify Ordinal Data: The Data Replication Method},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Classification of ordinal data is one of the most important tasks of relation learning. This paper introduces a new machine learning paradigm specifically intended for classification problems where the classes have a natural order. The technique reduces the problem of classifying ordered classes to the standard two-class problem. The introduced method is then mapped into support vector machines and neural networks. Generalization bounds of the proposed ordinal classifier are also provided. An experimental study with artificial and real data sets, including an application to gene expression analysis, verifies the usefulness of the proposed approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1393–1429},
numpages = {37}
}

@article{10.5555/1314498.1314545,
author = {Rigollet, Philippe},
title = {Generalization Error Bounds in Semi-Supervised Classification Under the Cluster Assumption},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We consider semi-supervised classification when part of the available data is unlabeled. These unlabeled data can be useful for the classification problem when we make an assumption relating the behavior of the regression function to that of the marginal distribution. Seeger (2000) proposed the well-known cluster assumption as a reasonable one. We propose a mathematical formulation of this assumption and a method based on density level sets estimation that takes advantage of it to achieve fast rates of convergence both in the number of unlabeled examples and the number of labeled examples.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1369–1392},
numpages = {24}
}

@article{10.5555/1314498.1314544,
author = {Hein, Matthias and Audibert, Jean-Yves and Luxburg, Ulrike von},
title = {Graph Laplacians and Their Convergence on Random Neighborhood Graphs},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Given a sample from a probability measure with support on a submanifold in Euclidean space one can construct a neighborhood graph which can be seen as an approximation of the submanifold. The graph Laplacian of such a graph is used in several machine learning methods like semi-supervised learning, dimensionality reduction and clustering. In this paper we determine the pointwise limit of three different graph Laplacians used in the literature as the sample size increases and the neighborhood size approaches zero. We show that for a uniform measure on the submanifold all graph Laplacians have the same limit up to constants. However in the case of a non-uniform measure on the submanifold only the so called random walk graph Laplacian converges to the weighted Laplace-Beltrami operator.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1325–1370},
numpages = {46}
}

@article{10.5555/1314498.1314543,
author = {Blum, Avrim and Mansour, Yishay},
title = {From External to Internal Regret},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an online algorithm to the loss of a modified online algorithm, which consistently replaces one action by another.In this paper we give a simple generic reduction that, given an algorithm for the external regret problem, converts it to an efficient online algorithm for the internal regret problem. We provide methods that work both in the  full information model, in which the loss of every action is observed at each time step, and the  partial information (bandit) model, where at each time step only the loss of the selected action is observed. The importance of internal regret in game theory is due to the fact that in a general game, if each player has sublinear internal regret, then the empirical frequencies converge to a correlated equilibrium.For external regret we also derive a quantitative regret bound for a very general setting of regret, which includes an arbitrary set of modification rules (that possibly modify the online algorithm) and an arbitrary set of time selection functions (each giving different weight to each time step). The regret for a given time selection and modification rule is the difference between the cost of the online algorithm and the cost of the modified online algorithm, where the costs are weighted by the time selection function. This can be viewed as a generalization of the previously-studied sleeping experts setting.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1307–1324},
numpages = {18}
}

@article{10.5555/1314498.1314542,
author = {Srivastava, Santosh and Gupta, Maya R. and Frigyik, B\'{e}la A.},
title = {Bayesian Quadratic Discriminant Analysis},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Quadratic discriminant analysis is a common tool for classification, but estimation of the Gaussian parameters can be ill-posed. This paper contains theoretical and algorithmic contributions to Bayesian estimation for quadratic discriminant analysis. A distribution-based Bayesian classifier is derived using information geometry. Using a calculus of variations approach to define a functional Bregman divergence for distributions, it is shown that the Bayesian distribution-based classifier that minimizes the expected Bregman divergence of each class conditional distribution also minimizes the expected misclassification cost. A series approximation is used to relate regularized discriminant analysis to Bayesian discriminant analysis. A new Bayesian quadratic discriminant analysis classifier is proposed where the prior is defined using a coarse estimate of the covariance based on the training data; this classifier is termed BDA7. Results on benchmark data sets and simulations show that BDA7 performance is competitive with, and in some cases significantly better than, regularized quadratic discriminant analysis and the cross-validated Bayesian quadratic discriminant analysis classifier Quadratic Bayes.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1277–1305},
numpages = {29}
}

@article{10.5555/1314498.1314541,
author = {Koppel, Moshe and Schler, Jonathan and Bonchek-Dokow, Elisheva},
title = {Measuring Differentiability: Unmasking Pseudonymous Authors},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In the authorship verification problem, we are given examples of the writing of a single author and are asked to determine if given long texts were or were not written by this author. We present a new learning-based method for adducing the "depth of difference" between two example sets and offer evidence that this method solves the authorship verification problem with very high accuracy. The underlying idea is to test the rate of degradation of the accuracy of learned models as the best features are iteratively dropped from the learning process.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1261–1276},
numpages = {16}
}

@article{10.5555/1314498.1314540,
author = {Dud\'{\i}k, Miroslav and Phillips, Steven J. and Schapire, Robert E.},
title = {Maximum Entropy Density Estimation with Generalized Regularization and an Application to Species Distribution Modeling},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We present a unified and complete account of maximum entropy density estimation subject to constraints represented by convex potential functions or, alternatively, by convex regularization. We provide fully general performance guarantees and an algorithm with a complete convergence proof. As special cases, we easily derive performance guarantees for many known regularization types, including l1, l2, l22, and l2 + l22 style regularization. We propose an algorithm solving a large and general subclass of generalized maximum entropy problems, including all discussed in the paper, and prove its convergence. Our approach generalizes and unifies techniques based on information geometry and Bregman divergences as well as those based more directly on compactness. Our work is motivated by a novel application of maximum entropy to species distribution modeling, an important problem in conservation biology and ecology. In a set of experiments on real-world data, we demonstrate the utility of maximum entropy in this setting. We explore effects of different feature types, sample sizes, and regularization levels on the performance of maxent, and discuss interpretability of the resulting models.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1217–1260},
numpages = {44}
}

@article{10.5555/1314498.1314539,
author = {Osadchy, Margarita and Cun, Yann Le and Miller, Matthew L.},
title = {Synergistic Face Detection and Pose Estimation with Energy-Based Models},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We describe a novel method for simultaneously detecting faces and estimating their pose in real time. The method employs a convolutional network to map images of faces to points on a low-dimensional manifold parametrized by pose, and images of non-faces to points far away from that manifold. Given an image, detecting a face and estimating its pose is viewed as minimizing an energy function with respect to the face/non-face binary variable and the continuous pose parameters. The system is trained to minimize a loss function that drives correct combinations of labels and pose to be associated with lower energy values than incorrect ones.The system is designed to handle very large range of poses without retraining. The performance of the system was tested on three standard data sets---for frontal views, rotated faces, and profiles---is comparable to previous systems that are designed to handle a single one of these data sets.We show that a system trained simuiltaneously for detection and pose estimation is more accurate on both tasks than similar systems trained for each task separately.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1197–1215},
numpages = {19}
}

@article{10.5555/1314498.1314538,
author = {Liu, Chao-Chun and Dai, Dao-Qing and Yan, Hong},
title = {Local Discriminant Wavelet Packet Coordinates for Face Recognition},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Face recognition is a challenging problem due to variations in pose, illumination, and expression. Techniques that can provide effective feature representation with enhanced discriminability are crucial. Wavelets have played an important role in image processing for its ability to capture localized spatial-frequency information of images. In this paper, we propose a novel local discriminant coordinates method based on wavelet packet for face recognition to compensate for these variations. Traditional wavelet-based methods for face recognition select or operate on the most discriminant subband, and neglect the scattered characteristic of discriminant features. The proposed method selects the most discriminant coordinates uniformly from all spatial frequency subbands to overcome the deficiency of traditional wavelet-based methods. To measure the discriminability of coordinates, a new dilation invariant entropy and a maximum a posterior logistic model are put forward. Moreover, a new triangle square ratio criterion is used to improve classification using the Euclidean distance and the cosine criterion. Experimental results show that the proposed method is robust for face recognition under variations in illumination, pose and expression.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1165–1195},
numpages = {31}
}

@article{10.5555/1314498.1314537,
author = {Pan, Wei and Shen, Xiaotong},
title = {Penalized Model-Based Clustering with Application to Variable Selection},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Variable selection in clustering analysis is both challenging and important. In the context of model-based clustering analysis with a common diagonal covariance matrix, which is especially suitable for "high dimension, low sample size" settings, we propose a penalized likelihood approach with an L1 penalty function, automatically realizing variable selection via thresholding and delivering a sparse solution. We derive an EM algorithm to fit our proposed model, and propose a modified BIC as a model selection criterion to choose the number of components and the penalization parameter. A simulation study and an application to gene function prediction with gene expression profiles demonstrate the utility of our method.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1145–1164},
numpages = {20}
}

@article{10.5555/1314498.1314536,
author = {Mooij, Joris M. and Kappen, Hilbert J.},
title = {Loop Corrections for Approximate Inference on Factor Graphs},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We propose a method to improve approximate inference methods by correcting for the influence of loops in the graphical model. The method is a generalization and alternative implementation of a recent idea from Montanari and Rizzo (2005). It is applicable to arbitrary factor graphs, provided that the size of the Markov blankets is not too large. It consists of two steps: (i) an approximate inference method, for example, belief propagation, is used to approximate cavity distributions for each variable (i.e., probability distributions on the Markov blanket of a variable for a modified graphical model in which the factors involving that variable have been removed); (ii) all cavity distributions are improved by a message-passing algorithm that cancels out approximation errors by imposing certain consistency constraints. This loop correction (LC) method usually gives significantly better results than the original, uncorrected, approximate inference algorithm that is used to estimate the effect of loops. Indeed, we often observe that the loop-corrected error is approximately the square of the error of the uncorrected approximate inference method. In this article, we compare different variants of the loop correction method with other approximate inference methods on a variety of graphical models, including "real world" networks, and conclude that the LC method generally obtains the most accurate results.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1113–1143},
numpages = {31}
}

@article{10.5555/1314498.1314535,
author = {Dyrholm, Mads and Christoforou, Christoforos and Parra, Lucas C.},
title = {Bilinear Discriminant Component Analysis},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Factor analysis and discriminant analysis are often used as complementary approaches to identify linear components in two dimensional data arrays. For three dimensional arrays, which may organize data in dimensions such as space, time, and trials, the opportunity arises to combine these two approaches. A new method, Bilinear Discriminant Component Analysis (BDCA), is derived and demonstrated in the context of functional brain imaging data for which it seems ideally suited. The work suggests to identify a subspace projection which optimally separates classes while ensuring that each dimension in this space captures an independent contribution to the discrimination.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1097–1111},
numpages = {15}
}

@article{10.5555/1314498.1314534,
author = {Szab\'{o}, Zolt\'{a}n and P\'{o}czos, Barnab\'{a}s and L\H{o}rincz, Andr\'{a}s},
title = {Undercomplete Blind Subspace Deconvolution},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We introduce the blind subspace deconvolution (BSSD) problem, which is the extension of both the blind source deconvolution (BSD) and the independent subspace analysis (ISA) tasks. We examine the case of the undercomplete BSSD (uBSSD). Applying temporal concatenation we reduce this problem to ISA. The associated `high dimensional' ISA problem can be handled by a recent technique called joint f-decorrelation (JFD). Similar decorrelation methods have been used previously for kernel independent component analysis (kernel-ICA). More precisely, the kernel canonical correlation (KCCA) technique is a member of this family, and, as is shown in this paper, the kernel generalized variance (KGV) method can also be seen as a decorrelation method in the feature space. These kernel based algorithms will be adapted to the ISA task. In the numerical examples, we (i) examine how efficiently the emerging higher dimensional ISA tasks can be tackled, and (ii) explore the working and advantages of the derived kernel-ISA methods.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1063–1095},
numpages = {33}
}

@article{10.5555/1314498.1314533,
author = {Sugiyama, Masashi},
title = {Dimensionality Reduction of Multimodal Labeled Data by Local Fisher Discriminant Analysis},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Reducing the dimensionality of data without losing intrinsic information is an important preprocessing step in

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr