text:
40,
author = {Greenshtein, Eitan and Park, Junyong},
title = {Application of Non Parametric Empirical Bayes Estimation to High Dimensional Classification},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We consider the problem of classification using high dimensional features' space. In a paper by Bickel and Levina (2004), it is recommended to use naive-Bayes classifiers, that is, to treat the features as if they are statistically independent.Consider now a sparse setup, where only a few of the features are informative for classification. Fan and Fan (2008), suggested a variable selection and classification method, called FAIR. The FAIR method improves the design of naive-Bayes classifiers in sparse setups. The improvement is due to reducing the noise in estimating the features' means. This reduction is since that only the means of a few selected variables should be estimated.We also consider the design of naive Bayes classifiers. We show that a good alternative to variable selection is estimation of the means through a certain non parametric empirical Bayes procedure. In sparse setups the empirical Bayes implicitly performs an efficient variable selection. It also adapts very well to non sparse setups, and has the advantage of making use of the information from many "weakly informative" variables, which variable selection type of classification procedures give up on using.We compare our method with FAIR and other classification methods in simulation for sparse and non sparse setups, and in real data examples involving classification of normal versus malignant tissues based on microarray data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1687–1704},
numpages = {18}
}

@article{10.5555/1577069.1755839,
author = {Taylor, Matthew E. and Stone, Peter},
title = {Transfer Learning for Reinforcement Learning Domains: A Survey},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The reinforcement learning paradigm is a popular way to address problems that have only limited environmental feedback, rather than correctly labeled examples, as is common in other machine learning contexts. While significant progress has been made to improve learning in a single task, the idea of transfer learning has only recently been applied to reinforcement learning tasks. The core idea of transfer is that experience gained in learning to perform one task can help improve learning performance in a related, but different, task. In this article we present a framework that classifies transfer learning methods in terms of their capabilities and goals, and then use it to survey the existing literature, as well as to suggest future directions for transfer learning work.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1633–1685},
numpages = {53}
}

@article{10.5555/1577069.1755838,
author = {Lin, Shaowei and Sturmfels, Bernd and Xu, Zhiqiang},
title = {Marginal Likelihood Integrals for Mixtures of Independence Models},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Inference in Bayesian statistics involves the evaluation of marginal likelihood integrals. We present algebraic algorithms for computing such integrals exactly for discrete data of small sample size. Our methods apply to both uniform priors and Dirichlet priors. The underlying statistical models are mixtures of independent distributions, or, in geometric language, secant varieties of Segre-Veronese varieties.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1611–1631},
numpages = {21}
}

@article{10.5555/1577069.1755837,
author = {Xu, Yuehua and Fern, Alan and Yoon, Sungwook},
title = {Learning Linear Ranking Functions for Beam Search with Application to Planning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Beam search is commonly used to help maintain tractability in large search spaces at the expense of completeness and optimality. Here we study supervised learning of linear ranking functions for controlling beam search. The goal is to learn ranking functions that allow for beam search to perform nearly as well as unconstrained search, and hence gain computational efficiency without seriously sacrificing optimality. In this paper, we develop theoretical aspects of this learning problem and investigate the application of this framework to learning in the context of automated planning. We first study the computational complexity of the learning problem, showing that even for exponentially large search spaces the general consistency problem is in NP. We also identify tractable and intractable subclasses of the learning problem, giving insight into the problem structure. Next, we analyze the convergence of recently proposed and modified online learning algorithms, where we introduce several notions of problem margin that imply convergence for the various algorithms. Finally, we present empirical results in automated planning, where ranking functions are learned to guide beam search in a number of benchmark planning domains. The results show that our approach is often able to outperform an existing state-of-the-art planning heuristic as well as a recent approach to learning such heuristics.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1571–1610},
numpages = {40}
}

@article{10.5555/1577069.1755836,
author = {Yehezkel, Raanan and Lerner, Boaz},
title = {Bayesian Network Structure Learning by Recursive Autonomy Identification},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We propose the recursive autonomy identification (RAI) algorithm for constraint-based (CB) Bayesian network structure learning. The RAI algorithm learns the structure by sequential application of conditional independence (CI) tests, edge direction and structure decomposition into autonomous sub-structures. The sequence of operations is performed recursively for each autonomous sub-structure while simultaneously increasing the order of the CI test. While other CB algorithms d-separate structures and then direct the resulted undirected graph, the RAI algorithm combines the two processes from the outset and along the procedure. By this means and due to structure decomposition, learning a structure using RAI requires a smaller number of CI tests of high orders. This reduces the complexity and run-time of the algorithm and increases the accuracy by diminishing the curse-of-dimensionality. When the RAI algorithm learned structures from databases representing synthetic problems, known networks and natural problems, it demonstrated superiority with respect to computational complexity, run-time, structural correctness and classification accuracy over the PC, Three Phase Dependency Analysis, Optimal Reinsertion, greedy search, Greedy Equivalence Search, Sparse Candidate, and Max-Min Hill-Climbing algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1527–1570},
numpages = {44}
}

@article{10.5555/1577069.1755835,
author = {Slobodianik, Nikolai and Zaporozhets, Dmitry and Madras, Neal},
title = {Strong Limit Theorems for the Bayesian Scoring Criterion in Bayesian Networks},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In the machine learning community, the Bayesian scoring criterion is widely used for model selection problems. One of the fundamental theoretical properties justifying the usage of the Bayesian scoring criterion is its consistency. In this paper we refine this property for the case of binomial Bayesian network models. As a by-product of our derivations we establish strong consistency and obtain the law of iterated logarithm for the Bayesian scoring criterion.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1511–1526},
numpages = {16}
}

@article{10.5555/1577069.1755834,
author = {Xu, Huan and Caramanis, Constantine and Mannor, Shie},
title = {Robustness and Regularization of Support Vector Machines},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We consider regularized support vector machines (SVMs) and show that they are precisely equivalent to a new robust optimization formulation. We show that this equivalence of robust optimization and regularization has implications for both algorithms, and analysis. In terms of algorithms, the equivalence suggests more general SVM-like algorithms for classification that explicitly build in protection to noise, and at the same time control overfitting. On the analysis front, the equivalence of robustness and regularization provides a robust optimization interpretation for the success of regularized SVMs. We use this new robustness interpretation of SVMs to give a new proof of consistency of (kernelized) SVMs, thus establishing robustness as the reason regularized SVMs generalize well.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1485–1510},
numpages = {26}
}

@article{10.5555/1577069.1755833,
author = {Hausser, Jean and Strimmer, Korbinian},
title = {Entropy Inference and the James-Stein Estimator, with Application to Nonlinear Gene Association Networks},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We present a procedure for effective estimation of entropy and mutual information from small-sample data, and apply it to the problem of inferring high-dimensional gene association networks. Specifically, we develop a James-Stein-type shrinkage estimator, resulting in a procedure that is highly efficient statistically as well as computationally. Despite its simplicity, we show that it outperforms eight other entropy estimation procedures across a diverse range of sampling scenarios and data-generating models, even in cases of severe undersampling. We illustrate the approach by analyzing E. coli gene expression data and computing an entropy-based gene-association network from gene expression data. A computer program is available that implements the proposed shrinkage estimator.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1469–1484},
numpages = {16}
}

@article{10.5555/1577069.1755832,
author = {Xiang, Dao-Hong and Zhou, Ding-Xuan},
title = {Classification with Gaussians and Convex Loss},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {This paper considers binary classification algorithms generated from Tikhonov regularization schemes associated with general convex loss functions and varying Gaussian kernels. Our main goal is to provide fast convergence rates for the excess misclassification error. Allowing varying Gaussian kernels in the algorithms improves learning rates measured by regularization error and sample error. Special structures of Gaussian kernels enable us to construct, by a nice approximation scheme with a Fourier analysis technique, uniformly bounded regularizing functions achieving polynomial decays of the regularization error under a Sobolev smoothness condition. The sample error is estimated by using a projection operator and a tight bound for the covering numbers of reproducing kernel Hilbert spaces generated by Gaussian kernels. The convexity of the general loss function plays a very important role in our analysis.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1447–1468},
numpages = {22}
}

@article{10.5555/1577069.1755831,
author = {Kanamori, Takafumi and Hido, Shohei and Sugiyama, Masashi},
title = {A Least-Squares Approach to Direct Importance Estimation},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We address the problem of estimating the ratio of two probability density functions, which is often referred to as the importance. The importance values can be used for various succeeding tasks such as covariate shift adaptation or outlier detection. In this paper, we propose a new importance estimation method that has a closed-form solution; the leave-one-out cross-validation score can also be computed analytically. Therefore, the proposed method is computationally highly efficient and simple to implement. We also elucidate theoretical properties of the proposed method such as the convergence rate and approximation error bounds. Numerical experiments show that the proposed method is comparable to the best existing method in accuracy, while it is computationally more efficient than competing approaches.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1391–1445},
numpages = {55}
}

@article{10.5555/1577069.1755830,
author = {Raeder, Troy and Chawla, Nitesh V.},
title = {Model Monitor (M2): Evaluating, Comparing, and Monitoring Models},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {This paper presents Model Monitor (M2), a Java toolkit for robustly evaluating machine learning algorithms in the presence of changing data distributions. M2 provides a simple and intuitive framework in which users can evaluate classifiers under hypothesized shifts in distribution and therefore determine the best model (or models) for their data under a number of potential scenarios. Additionally, M2 is fully integrated with the WEKA machine learning environment, so that a variety of commodity classifiers can be used if desired.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1387–1390},
numpages = {4}
}

@article{10.5555/1577069.1755829,
author = {Boull\'{e}, Marc},
title = {A Parameter-Free Classification Method for Large Scale Learning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {With the rapid growth of computer storage capacities, available data and demand for scoring models both follow an increasing trend, sharper than that of the processing power. However, the main limitation to a wide spread of data mining solutions is the non-increasing availability of skilled data analysts, which play a key role in data preparation and model selection.In this paper, we present a parameter-free scalable classification method, which is a step towards fully automatic data mining. The method is based on Bayes optimal univariate conditional density estimators, naive Bayes classification enhanced with a Bayesian variable selection scheme, and averaging of models using a logarithmic smoothing of the posterior distribution. We focus on the complexity of the algorithms and show how they can cope with data sets that are far larger than the available central memory. We finally report results on the Large Scale Learning challenge, where our method obtains state of the art performance within practicable computation time.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1367–1385},
numpages = {19}
}

@article{10.5555/1577069.1755828,
author = {Tuv, Eugene and Borisov, Alexander and Runger, George and Torkkola, Kari},
title = {Feature Selection with Ensembles, Artificial Variables, and Redundancy Elimination},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Predictive models benefit from a compact, non-redundant subset of features that improves interpretability and generalization. Modern data sets are wide, dirty, mixed with both numerical and categorical predictors, and may contain interactive effects that require complex models. This is a challenge for filters, wrappers, and embedded feature selection methods. We describe details of an algorithm using tree-based ensembles to generate a compact subset of non-redundant features. Parallel and serial ensembles of trees are combined into a mixed method that can uncover masking and detect features of secondary effect. Simulated and actual examples illustrate the effectiveness of the approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1341–1366},
numpages = {26}
}

@article{10.5555/1577069.1577113,
author = {Goedertier, Stijn and Martens, David and Vanthienen, Jan and Baesens, Bart},
title = {Robust Process Discovery with Artificial Negative Events},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Process discovery is the automated construction of structured process models from information system event logs. Such event logs often contain positive examples only. Without negative examples, it is a challenge to strike the right balance between recall and specificity, and to deal with problems such as expressiveness, noise, incomplete event logs, or the inclusion of prior knowledge. In this paper, we present a configurable technique that deals with these challenges by representing process discovery as a multi-relational classification problem on event logs supplemented with Artificially Generated Negative Events (AGNEs). This problem formulation allows using learning algorithms and evaluation techniques that are well-know in the machine learning community. Moreover, it allows users to have a declarative control over the inductive bias and language bias.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1305–1340},
numpages = {36}
}

@article{10.5555/1577069.1577112,
author = {Paquet, Ulrich and Winther, Ole and Opper, Manfred},
title = {Perturbation Corrections in Approximate Inference: Mixture Modelling Applications},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Bayesian inference is intractable for many interesting models, making deterministic algorithms for approximate inference highly desirable. Unlike stochastic methods, which are exact in the limit, the accuracy of these approaches cannot be reasonably judged. In this paper we show how low order perturbation corrections to an expectation-consistent (EC) approximation can provide the necessary tools to ameliorate inference accuracy, and to give an indication of the quality of approximation without having to resort to Monte Carlo methods. Further comparisons are given with variational Bayes and parallel tempering (PT) combined with thermodynamic integration on a Gaussian mixture model. To obtain practical results we further generalize PT to temper from arbitrary distributions rather than a prior in Bayesian inference.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1263–1304},
numpages = {42}
}

@article{10.5555/1577069.1577111,
author = {Dugas, Charles and Bengio, Yoshua and B\'{e}lisle, Fran\c{c}ois and Nadeau, Claude and Garcia, Ren\'{e}},
title = {Incorporating Functional Knowledge in Neural Networks},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Incorporating prior knowledge of a particular task into the architecture of a learning algorithm can greatly improve generalization performance. We study here a case where we know that the function to be learned is non-decreasing in its two arguments and convex in one of them. For this purpose we propose a class of functions similar to multi-layer neural networks but (1) that has those properties, (2) is a universal approximator of Lipschitz functions with these and other properties. We apply this new class of functions to the task of modelling the price of call options. Experiments show improvements on regressing the price of call options using the new types of function classes that incorporate the a priori constraints.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1239–1262},
numpages = {24}
}

@article{10.5555/1577069.1577110,
author = {Silva, Ricardo and Ghahramani, Zoubin},
title = {The Hidden Life of Latent Variables: Bayesian Learning with Mixed Graph Models},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Directed acyclic graphs (DAGs) have been widely used as a representation of conditional independence in machine learning and statistics. Moreover, hidden or latent variables are often an important component of graphical models. However, DAG models suffer from an important limitation: the family of DAGs is not closed under marginalization of hidden variables. This means that in general we cannot use a DAG to represent the independencies over a subset of variables in a larger DAG. Directed mixed graphs (DMGs) are a representation that includes DAGs as a special case, and overcomes this limitation. This paper introduces algorithms for performing Bayesian inference in Gaussian and probit DMG models. An important requirement for inference is the specification of the distribution over parameters of the models. We introduce a new distribution for covariance matrices of Gaussian DMGs. We discuss and illustrate how several Bayesian machine learning tasks can benefit from the principle presented here: the power to model dependencies that are generated from hidden variables, but without necessarily modeling such variables explicitly.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1187–1238},
numpages = {52}
}

@article{10.5555/1577069.1577109,
author = {Li, Hui and Liao, Xuejun and Carin, Lawrence},
title = {Multi-Task Reinforcement Learning in Partially Observable Stochastic Environments},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We consider the problem of multi-task reinforcement learning (MTRL) in multiple partially observable stochastic environments. We introduce the regionalized policy representation (RPR) to characterize the agent's behavior in each environment. The RPR is a parametric model of the conditional distribution over current actions given the history of past actions and observations; the agent's choice of actions is directly based on this conditional distribution, without an intervening model to characterize the environment itself. We propose off-policy batch algorithms to learn the parameters of the RPRs, using episodic data collected when following a behavior policy, and show their linkage to policy iteration. We employ the Dirichlet process as a nonparametric prior over the RPRs across multiple environments. The intrinsic clustering property of the Dirichlet process imposes sharing of episodes among similar environments, which effectively reduces the number of episodes required for learning a good policy in each environment, when data sharing is appropriate. The number of distinct RPRs and the associated clusters (the sharing patterns) are automatically discovered by exploiting the episodic data as well as the nonparametric nature of the Dirichlet process. We demonstrate the effectiveness of the proposed RPR as well as the RPR-based MTRL framework on various problems, including grid-world navigation and multi-aspect target classification. The experimental results show that the RPR is a competitive reinforcement learning algorithm in partially observable domains, and the MTRL consistently achieves better performance than single task reinforcement learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1131–1186},
numpages = {56}
}

@article{10.5555/1577069.1577108,
author = {Kontorovich, Leonid (Aryeh) and Nadler, Boaz},
title = {Universal Kernel-Based Learning with Applications to Regular Languages},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We propose a novel framework for supervised learning of discrete concepts. Since the 1970's, the standard computational primitive has been to find the most consistent hypothesis in a given complexity class. In contrast, in this paper we propose a new basic operation: for each pair of input instances, count how many concepts of bounded complexity contain both of them.Our approach maps instances to a Hilbert space, whose metric is induced by a universal kernel coinciding with our computational primitive, and identifies concepts with half-spaces. We prove that all concepts are linearly separable under this mapping. Hence, given a labeled sample and an oracle for evaluating the universal kernel, we can efficiently compute a linear classifier (via SVM, for example) and use margin bounds to control its generalization error. Even though exact evaluation of the universal kernel may be infeasible, in various natural situations it is efficiently approximable.Though our approach is general, our main application is to regular languages. Our approach presents a substantial departure from current learning paradigms and in particular yields a novel method for learning this fundamental concept class. Unlike existing techniques, we make no structural assumptions on the corresponding unknown automata, the string distribution or the completeness of the training set. Instead, given a labeled sample our algorithm outputs a classifier with guaranteed distribution-free generalization bounds; to our knowledge, the proposed framework is the only one capable of achieving the latter. Along the way, we touch upon several fundamental questions in complexity, automata, and machine learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1095–1129},
numpages = {35}
}

@article{10.5555/1577069.1577107,
author = {Pe\~{n}a, Jose M. and Nilsson, Roland and Bj\"{o}rkegren, Johan and Tegn\'{e}r, Jesper},
title = {An Algorithm for Reading Dependencies from the Minimal Undirected Independence Map of a Graphoid That Satisfies Weak Transitivity},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We present a sound and complete graphical criterion for reading dependencies from the minimal undirected independence map G of a graphoid M that satisfies weak transitivity. Here, complete means that it is able to read all the dependencies in M that can be derived by applying the graphoid properties and weak transitivity to the dependencies used in the construction of G and the independencies obtained from G by vertex separation. We argue that assuming weak transitivity is not too restrictive. As an intermediate step in the derivation of the graphical criterion, we prove that for any undirected graph G there exists a strictly positive discrete probability distribution with the prescribed sample spaces that is faithful to G. We also report an algorithm that implements the graphical criterion and whose running time is considered to be at most O(n2(e+n)) for n nodes and e edges. Finally, we illustrate how the graphical criterion can be used within bioinformatics to identify biologically meaningful gene dependencies.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1071–1094},
numpages = {24}
}

@article{10.5555/1577069.1577106,
author = {Huang, Jonathan and Guestrin, Carlos and Guibas, Leonidas},
title = {Fourier Theoretic Probabilistic Inference over Permutations},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Permutations are ubiquitous in many real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations is challenging, since there are n! possibilities, and typical compact and factorized probability distribution representations, such as graphical models, cannot capture the mutual exclusivity constraints associated with permutations. In this paper, we use the "low-frequency" terms of a Fourier decomposition to represent distributions over permutations compactly. We present Kronecker conditioning, a novel approach for maintaining and updating these distributions directly in the Fourier domain, allowing for polynomial time bandlimited approximations. Low order Fourier-based approximations, however, may lead to functions that do not correspond to valid distributions. To address this problem, we present a quadratic program defined directly in the Fourier domain for projecting the approximation onto a relaxation of the polytope of legal marginal distributions. We demonstrate the effectiveness of our approach on a real camera-based multi-person tracking scenario.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {997–1070},
numpages = {74}
}

@article{10.5555/1577069.1577105,
author = {Jiang, Wenxin},
title = {On Uniform Deviations of General Empirical Risks with Unboundedness, Dependence, and High Dimensionality},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The statistical learning theory of risk minimization depends heavily on probability bounds for uniform deviations of the empirical risks. Classical probability bounds using Hoeffding's inequality cannot accommodate more general situations with unbounded loss and dependent data. The current paper introduces an inequality that extends Hoeffding's inequality to handle these more general situations. We will apply this inequality to provide probability bounds for uniform deviations in a very general framework, which can involve discrete decision rules, unbounded loss, and a dependence structure that can be more general than either martingale or strong mixing. We will consider two examples with high dimensional predictors: autoregression (AR) with l1-loss, and ARX model with variable selection for sign classification, which uses both lagged responses and exogenous predictors.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {977–996},
numpages = {20}
}

@article{10.5555/1577069.1577104,
author = {Martins, Andr\'{e} F. T. and Smith, Noah A. and Xing, Eric P. and Aguiar, Pedro M. Q. and Figueiredo, M\'{a}rio A. T.},
title = {Nonextensive Information Theoretic Kernels on Measures},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Positive definite kernels on probability measures have been recently applied to classification problems involving text, images, and other types of structured data. Some of these kernels are related to classic information theoretic quantities, such as (Shannon's) mutual information and the Jensen-Shannon (JS) divergence. Meanwhile, there have been recent advances in nonextensive generalizations of Shannon's information theory. This paper bridges these two trends by introducing nonextensive information theoretic kernels on probability measures, based on new JS-type divergences. These new divergences result from extending the the two building blocks of the classical JS divergence: convexity and Shannon's entropy. The notion of convexity is extended to the wider concept of q-convexity, for which we prove a Jensen q-inequality. Based on this inequality, we introduce Jensen-Tsallis (JT) q-differences, a nonextensive generalization of the JS divergence, and define a k-th order JT q-difference between stochastic processes. We then define a new family of nonextensive mutual information kernels, which allow weights to be assigned to their arguments, and which includes the Boolean, JS, and linear kernels as particular cases. Nonextensive string kernels are also defined that generalize the p-spectrum kernel. We illustrate the performance of these kernels on text categorization tasks, in which documents are modeled both as bags of words and as sequences of characters.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {935–975},
numpages = {41}
}

@article{10.5555/1577069.1577103,
author = {Abeel, Thomas and Van de Peer, Yves and Saeys, Yvan},
title = {Java-ML: A Machine Learning Library},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Java-ML is a collection of machine learning and data mining algorithms, which aims to be a readily usable and easily extensible API for both software developers and research scientists. The interfaces for each type of algorithm are kept simple and algorithms strictly follow their respective interface. Comparing different classifiers or clustering algorithms is therefore straightforward, and implementing new algorithms is also easy. The implementations of the algorithms are clearly written, properly documented and can thus be used as a reference. The library is written in Java and is available from http://java-ml.sourceforge.net/ under the GNU GPL license.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {931–934},
numpages = {4}
}

@article{10.5555/1577069.1577102,
author = {Ramon, Jan and Nijssen, Siegfried},
title = {Polynomial-Delay Enumeration of Monotonic Graph Classes},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Algorithms that list graphs such that no two listed graphs are isomorphic, are important building blocks of systems for mining and learning in graphs. Algorithms are already known that solve this problem efficiently for many classes of graphs of restricted topology, such as trees. In this article we introduce the concept of a dense augmentation schema, and introduce an algorithm that can be used to enumerate any class of graphs with polynomial delay, as long as the class of graphs can be described using a monotonic predicate operating on a dense augmentation schema. In practice this means that this is the first enumeration algorithm that can be applied theoretically efficiently in any frequent subgraph mining algorithm, and that this algorithm generalizes to situations beyond the standard frequent subgraph mining setting.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {907–929},
numpages = {23}
}

@article{10.5555/1577069.1577101,
author = {H\"{o}fling, Holger and Tibshirani, Robert},
title = {Estimation of Sparse Binary Pairwise Markov Networks Using Pseudo-Likelihoods},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We consider the problems of estimating the parameters as well as the structure of binary-valued Markov networks. For maximizing the penalized log-likelihood, we implement an approximate procedure based on the pseudo-likelihood of Besag (1975) and generalize it to a fast exact algorithm. The exact algorithm starts with the pseudo-likelihood solution and then adjusts the pseudo-likelihood criterion so that each additional iterations moves it closer to the exact solution. Our results show that this procedure is faster than the competing exact method proposed by Lee, Ganapathi, and Koller (2006a). However, we also find that the approximate pseudo-likelihood as well as the approaches of Wainwright et al. (2006), when implemented using the coordinate descent procedure of Friedman, Hastie, and Tibshirani (2008b), are much faster than the exact methods, and only slightly less accurate.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {883–906},
numpages = {24}
}

@article{10.5555/1577069.1577100,
author = {Foster, Leslie and Waagen, Alex and Aijaz, Nabeela and Hurley, Michael and Luis, Apolonio and Rinsky, Joel and Satyavolu, Chandrika and Way, Michael J. and Gazis, Paul and Srivastava, Ashok},
title = {Stable and Efficient Gaussian Process Calculations},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The use of Gaussian processes can be an effective approach to prediction in a supervised learning environment. For large data sets, the standard Gaussian process approach requires solving very large systems of linear equations and approximations are required for the calculations to be practical. We will focus on the subset of regressors approximation technique. We will demonstrate that there can be numerical instabilities in a well known implementation of the technique. We discuss alternate implementations that have better numerical stability properties and can lead to better predictions. Our results will be illustrated by looking at an application involving prediction of galaxy redshift from broadband spectrum data.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {857–882},
numpages = {26}
}

@article{10.5555/1577069.1577099,
author = {Zakai, Alon and Ritov, Ya'acov},
title = {Consistency and Localizability},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We show that all consistent learning methods---that is, that asymptotically achieve the lowest possible expected loss for any distribution on (X,Y)---are necessarily localizable, by which we mean that they do not significantly change their response at a particular point when we show them only the part of the training set that is close to that point. This is true in particular for methods that appear to be defined in a non-local manner, such as support vector machines in classification and least-squares estimators in regression. Aside from showing that consistency implies a specific form of localizability, we also show that consistency is logically equivalent to the combination of two properties: (1) a form of localizability, and (2) that the method's global mean (over the entire X distribution) correctly estimates the true mean. Consistency can therefore be seen as comprised of two aspects, one local and one global.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {827–856},
numpages = {30}
}

@article{10.5555/1577069.1577098,
author = {Abernethy, Jacob and Bach, Francis and Evgeniou, Theodoros and Vert, Jean-Philippe},
title = {A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We present a general approach for collaborative filtering (CF) using spectral regularization to learn linear operators mapping a set of "users" to a set of possibly desired "objects". In particular, several recent low-rank type matrix-completion methods for CF are shown to be special cases of our proposed framework. Unlike existing regularization-based CF, our approach can be used to incorporate additional information such as attributes of the users/objects---a feature currently lacking in existing regularization-based CF approaches---using popular and well-known kernel methods. We provide novel representer theorems that we use to develop new estimation methods. We then provide learning algorithms based on low-rank decompositions and test them on a standard CF data set. The experiments indicate the advantages of generalizing the existing regularization-based CF methods to incorporate related information about users and objects. Finally, we show that certain multi-task learning methods can be also seen as special cases of our proposed approach.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {803–826},
numpages = {24}
}

@article{10.5555/1577069.1577097,
author = {Langford, John and Li, Lihong and Zhang, Tong},
title = {Sparse Online Learning via Truncated Gradient},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We propose a general method called truncated gradient to induce sparsity in the weights of online-learning algorithms with convex loss functions. This method has several essential properties: (1) The degree of sparsity is continuous---a parameter controls the rate of sparsification from no sparsification to total sparsification. (2) The approach is theoretically motivated, and an instance of it can be regarded as an online counterpart of the popular L1-regularization method in the batch setting. We prove that small rates of sparsification result in only small additional regret with respect to typical online-learning guarantees. (3) The approach works well empirically. We apply the approach to several data sets and find for data sets with large numbers of features, substantial sparsity is discoverable.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {777–801},
numpages = {25}
}

@article{10.5555/1577069.1577096,
author = {Chen, Yihua and Garcia, Eric K. and Gupta, Maya R. and Rahimi, Ali and Cazzanti, Luca},
title = {Similarity-Based Classification: Concepts and Algorithms},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {This paper reviews and extends the field of similarity-based classification, presenting new analyses, algorithms, data sets, and a comprehensive set of experimental results for a rich collection of classification problems. Specifically, the generalizability of using similarities as features is analyzed, design goals and methods for weighting nearest-neighbors for similarity-based learning are proposed, and different methods for consistently converting similarities into kernels are compared. Experiments on eight real data sets compare eight approaches and their variants to similarity-based learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {747–776},
numpages = {30}
}

@article{10.5555/1577069.1577095,
author = {Maes, Francis},
title = {Nieme: Large-Scale Energy-Based Models},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In this paper we introduce NIEME, a machine learning library for large-scale classification, regression and ranking. NIEME, relies on the framework of energy-based models (LeCun et al., 2006) which unifies several learning algorithms ranging from simple perceptrons to recent models such as the pegasos support vector machine or l1-regularized maximum entropy models. This framework also unifies batch and stochastic learning which are both seen as energy minimization problems. NIEME, can hence be used in a wide range of situations, but is particularly interesting for large-scale learning tasks where both the examples and the features are processed incrementally. Being able to deal with new incoming features at any time within the learning process is another original feature of the NIEME, toolbox. NIEME, is released under the GPL license. It is efficiently implemented in C++, it works on Linux, Mac OS X and Windows and provides interfaces for C++, Java and Python.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {743–746},
numpages = {4}
}

@article{10.5555/1577069.1577094,
author = {Wang, Junhui and Shen, Xiaotong and Pan, Wei},
title = {On Efficient Large Margin Semisupervised Learning: Method and Theory},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In classification, semisupervised learning usually involves a large amount of unlabeled data with only a small number of labeled data. This imposes a great challenge in that it is difficult to achieve good classification performance through labeled data alone. To leverage unlabeled data for enhancing classification, this article introduces a large margin semisupervised learning method within the framework of regularization, based on an efficient margin loss for unlabeled data, which seeks efficient extraction of the information from unlabeled data for estimating the Bayes decision boundary for classification. For implementation, an iterative scheme is derived through conditional expectations. Finally, theoretical and numerical analyses are conducted, in addition to an application to gene function prediction. They suggest that the proposed method enables to recover the performance of its supervised counterpart based on complete data in rates of convergence, when possible.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {719–742},
numpages = {24}
}

@article{10.5555/1577069.1577093,
author = {VanderWeele, Tyler J. and Robins, James M.},
title = {Properties of Monotonic Effects on Directed Acyclic Graphs},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Various relationships are shown hold between monotonic effects and weak monotonic effects and the monotonicity of certain conditional expectations. Counterexamples are provided to show that the results do not hold under less restrictive conditions. Monotonic effects are furthermore used to relate signed edges on a causal directed acyclic graph to qualitative effect modification. The theory is applied to an example concerning the direct effect of smoking on cardiovascular disease controlling for hypercholesterolemia. Monotonicity assumptions are used to construct a test for whether there is a variable that confounds the relationship between the mediator, hypercholesterolemia, and the outcome, cardiovascular disease.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {699–718},
numpages = {20}
}

@article{10.5555/1577069.1577092,
author = {Bubeck, S\'{e}bastien and Luxburg, Ulrike von},
title = {Nearest Neighbor Clustering: A Baseline Method for Consistent Clustering with Arbitrary Objective Functions},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Clustering is often formulated as a discrete optimization problem. The objective is to find, among all partitions of the data set, the best one according to some quality measure. However, in the statistical setting where we assume that the finite data set has been sampled from some underlying space, the goal is not to find the best partition of the given sample, but to approximate the true partition of the underlying space. We argue that the discrete optimization approach usually does not achieve this goal, and instead can lead to inconsistency. We construct examples which provably have this behavior. As in the case of supervised learning, the cure is to restrict the size of the function classes under consideration. For appropriate "small" function classes we can prove very general consistency theorems for clustering optimization schemes. As one particular algorithm for clustering with a restricted function space we introduce "nearest neighbor clustering". Similar to the k-nearest neighbor classifier in supervised learning, this algorithm can be seen as a general baseline algorithm to minimize arbitrary clustering objective functions. We prove that it is statistically consistent for all commonly used clustering objective functions.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {657–698},
numpages = {42}
}

@article{10.5555/1577069.1577091,
author = {Tak\'{a}cs, G\'{a}bor and Pil\'{a}szy, Istv\'{a}n and N\'{e}meth, Botty\'{a}n and Tikk, Domonkos},
title = {Scalable Collaborative Filtering Approaches for Large Recommender Systems},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The collaborative filtering (CF) using known user ratings of items has proved to be effective for predicting user preferences in item selection. This thriving subfield of machine learning became popular in the late 1990s with the spread of online services that use recommender systems, such as Amazon, Yahoo! Music, and Netflix. CF approaches are usually designed to work on very large data sets. Therefore the scalability of the methods is crucial. In this work, we propose various scalable solutions that are validated against the Netflix Prize data set, currently the largest publicly available collection. First, we propose various matrix factorization (MF) based techniques. Second, a neighbor correction method for MF is outlined, which alloys the global perspective of MF and the localized property of neighbor based approaches efficiently. In the experimentation section, we first report on some implementation issues, and we suggest on how parameter optimization can be performed efficiently for MFs. We then show that the proposed scalable approaches compare favorably with existing ones in terms of prediction accuracy and/or required training time. Finally, we report on some experiments performed on MovieLens and Jester data sets.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {623–656},
numpages = {34}
}

@article{10.5555/1577069.1577090,
author = {Ghanty, Pradip and Paul, Samrat and Pal, Nikhil R.},
title = {NEUROSVM: An Architecture to Reduce the Effect of the Choice of Kernel on the Performance of SVM},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In this paper we propose a new multilayer classifier architecture. The proposed hybrid architecture has two cascaded modules: feature extraction module and classification module. In the feature extraction module we use the multilayered perceptron (MLP) neural networks, although other tools such as radial basis function (RBF) networks can be used. In the classification module we use support vector machines (SVMs)---here also other tool such as MLP or RBF can be used. The feature extraction module has several sub-modules each of which is expected to extract features capturing the discriminating characteristics of different areas of the input space. The classification module classifies the data based on the extracted features. The resultant architecture with MLP in feature extraction module and SVM in classification module is called NEUROSVM. The NEUROSVM is tested on twelve benchmark data sets and the performance of the NEUROSVM is found to be better than both MLP and SVM. We also compare the performance of proposed architecture with that of two ensemble methods: majority voting and averaging. Here also the NEUROSVM is found to perform better than these two ensemble methods. Further we explore the use of MLP and RBF in the classification module of the proposed architecture. The most attractive feature of NEUROSVM is that it practically eliminates the severe dependency of SVM on the choice of kernel. This has been verified with respect to both linear and non-linear kernels. We have also demonstrated that for the feature extraction module, the full training of MLPs is not needed.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {591–622},
numpages = {32}
}

@article{10.5555/1577069.1577089,
author = {Mannor, Shie and Tsitsiklis, John N. and Yu, Jia Yuan},
title = {Online Learning with Sample Path Constraints},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We study online learning where a decision maker interacts with Nature with the objective of maximizing her long-term average reward subject to some sample path average constraints. We define the reward-in-hindsight as the highest reward the decision maker could have achieved, while satisfying the constraints, had she known Nature's choices in advance. We show that in general the reward-in-hindsight is not attainable. The convex hull of the reward-in-hindsight function is, however, attainable. For the important case of a single constraint, the convex hull turns out to be the highest attainable function. Using a calibrated forecasting rule, we provide an explicit strategy that attains this convex hull. We also measure the performance of heuristic methods based on non-calibrated forecasters in experiments involving a CPU power management problem.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {569–590},
numpages = {22}
}

@article{10.5555/1577069.1577088,
author = {Zhang, Tong},
title = {On the Consistency of Feature Selection Using Greedy Least Squares Regression},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {This paper studies the feature selection problem using a greedy least squares regression algorithm. We show that under a certain irrepresentable condition on the design matrix (but independent of the sparse target), the greedy algorithm can select features consistently when the sample size approaches infinity. The condition is identical to a corresponding condition for Lasso.Moreover, under a sparse eigenvalue condition, the greedy algorithm can reliably identify features as long as each nonzero coefficient is larger than a constant times the noise level. In comparison, Lasso may require the coefficients to be larger than O(√s) times the noise level in the worst case, where s is the number of nonzero coefficients.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {555–568},
numpages = {14}
}

@article{10.5555/1577069.1577087,
author = {P\'{o}czos, Barnab\'{a}s and L\H{o}rincz, Andr\'{a}s},
title = {Identification of Recurrent Neural Networks by Bayesian Interrogation Techniques},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We introduce novel online Bayesian methods for the identification of a family of noisy recurrent neural networks (RNNs). We present Bayesian active learning techniques for stimulus selection given past experiences. In particular, we consider the unknown parameters as stochastic variables and use A-optimality and D-optimality principles to choose optimal stimuli. We derive myopic cost functions in order to maximize the information gain concerning network parameters at each time step. We also derive the A-optimal and D-optimal estimations of the additive noise that perturbs the dynamical system of the RNN. Here we investigate myopic as well as non-myopic estimations, and study the problem of simultaneous estimation of both the system parameters and the noise. Employing conjugate priors our derivations remain approximation-free and give rise to simple update rules for the online learning of the parameters. The efficiency of our method is demonstrated for a number of selected cases, including the task of controlled independent component analysis.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {515–554},
numpages = {40}
}

@article{10.5555/1577069.1577086,
author = {Li, Junning and Wang, Z. Jane},
title = {Controlling the False Discovery Rate of the Association/Causality Structure Learned with the PC Algorithm},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In real world applications, graphical statistical models are not only a tool for operations such as classification or prediction, but usually the network structures of the models themselves are also of great interest (e.g., in modeling brain connectivity). The false discovery rate (FDR), the expected ratio of falsely claimed connections to all those claimed, is often a reasonable error-rate criterion in these applications. However, current learning algorithms for graphical models have not been adequately adapted to the concerns of the FDR. The traditional practice of controlling the type I error rate and the type II error rate under a conventional level does not necessarily keep the FDR low, especially in the case of sparse networks. In this paper, we propose embedding an FDR-control procedure into the PC algorithm to curb the FDR of the skeleton of the learned graph. We prove that the proposed method can control the FDR under a user-specified level at the limit of large sample sizes. In the cases of moderate sample size (about several hundred), empirical experiments show that the method is still able to control the FDR under the user-specified level, and a heuristic modification of the method is able to control the FDR more accurately around the user-specified level. The proposed method is applicable to any models for which statistical tests of conditional independence are available, such as discrete models and Gaussian models.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {475–514},
numpages = {40}
}

@article{10.5555/1577069.1577085,
author = {Agarwal, Shivani and Niyogi, Partha},
title = {Generalization Bounds for Ranking Algorithms via Algorithmic Stability},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The problem of ranking, in which the goal is to learn a real-valued ranking function that induces a ranking or ordering over an instance space, has recently gained much attention in machine learning. We study generalization properties of ranking algorithms using the notion of algorithmic stability; in particular, we derive generalization bounds for ranking algorithms that have good stability properties. We show that kernel-based ranking algorithms that perform regularization in a reproducing kernel Hilbert space have such stability properties, and therefore our bounds can be applied to these algorithms; this is in contrast with generalization bounds based on uniform convergence, which in many cases cannot be applied to these algorithms. Our results generalize earlier results that were derived in the special setting of bipartite ranking (Agarwal and Niyogi, 2005) to a more general setting of the ranking problem that arises frequently in applications.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {441–474},
numpages = {34}
}

@article{10.5555/1577069.1577084,
author = {Escalante, Hugo Jair and Montes, Manuel and Sucar, Luis Enrique},
title = {Particle Swarm Model Selection},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {This paper proposes the application of particle swarm optimization (PSO) to the problem of full model selection, FMS, for classification tasks. FMS is defined as follows: given a pool of preprocessing methods, feature selection and learning algorithms, to select the combination of these that obtains the lowest classification error for a given data set; the task also includes the selection of hyperparameters for the considered methods. This problem generates a vast search space to be explored, well suited for stochastic optimization techniques. FMS can be applied to any classification domain as it does not require domain knowledge. Different model types and a variety of algorithms can be considered under this formulation. Furthermore, competitive yet simple models can be obtained with FMS. We adopt PSO for the search because of its proven performance in different problems and because of its simplicity, since neither expensive computations nor complicated operations are needed. Interestingly, the way the search is guided allows PSO to avoid overfitting to some extend. Experimental results on benchmark data sets give evidence that the proposed approach is very effective, despite its simplicity. Furthermore, results obtained in the framework of a model selection challenge show the competitiveness of the models selected with PSO, compared to models selected with other techniques that focus on a single algorithm and that use domain knowledge.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {405–440},
numpages = {36}
}

@article{10.5555/1577069.1577083,
author = {Novak, Petra Kralj and Lavra\v{c}, Nada and Webb, Geoffrey I.},
title = {Supervised Descriptive Rule Discovery: A Unifying Survey of Contrast Set, Emerging Pattern and Subgroup Mining},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {This paper gives a survey of contrast set mining (CSM), emerging pattern mining (EPM), and subgroup discovery (SD) in a unifying framework named supervised descriptive rule discovery. While all these research areas aim at discovering patterns in the form of rules induced from labeled data, they use different terminology and task definitions, claim to have different goals, claim to use different rule learning heuristics, and use different means for selecting subsets of induced patterns. This paper contributes a novel understanding of these subareas of data mining by presenting a unified terminology, by explaining the apparent differences between the learning tasks as variants of a unique supervised descriptive rule discovery task and by exploring the apparent differences between the approaches. It also shows that various rule learning heuristics used in CSM, EPM and SD algorithms all aim at optimizing a trade off between rule coverage and precision. The commonalities (and differences) between the approaches are showcased on a selection of best known variants of CSM, EPM and SD algorithms. The paper also provides a critical survey of existing supervised descriptive rule discovery visualization methods.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {377–403},
numpages = {27}
}

@article{10.5555/1577069.1577082,
author = {Kulis, Brian and Sustik, M\'{a}ty\'{a}s A. and Dhillon, Inderjit S.},
title = {Low-Rank Kernel Learning with Bregman Matrix Divergences},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In this paper, we study low-rank matrix nearness problems, with a focus on learning low-rank positive semidefinite (kernel) matrices for machine learning applications. We propose efficient algorithms that scale linearly in the number of data points and quadratically in the rank of the input matrix. Existing algorithms for learning kernel matrices often scale poorly, with running times that are cubic in the number of data points. We employ Bregman matrix divergences as the measures of nearness---these divergences are natural for learning low-rank kernels since they preserve rank as well as positive semidefiniteness. Special cases of our framework yield faster algorithms for various existing learning problems, and experimental results demonstrate that our algorithms can effectively learn both low-rank and full-rank kernel matrices.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {341–376},
numpages = {36}
}

@article{10.5555/1577069.1577081,
author = {Bromberg, Facundo and Margaritis, Dimitris},
title = {Improving the Reliability of Causal Discovery from Small Data Sets Using Argumentation},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We address the problem of improving the reliability of independence-based causal discovery algorithms that results from the execution of statistical independence tests on small data sets, which typically have low reliability. We model the problem as a knowledge base containing a set of independence facts that are related through Pearl's well-known axioms. Statistical tests on finite data sets may result in errors in these tests and inconsistencies in the knowledge base. We resolve these inconsistencies through the use of an instance of the class of defeasible logics called argumentation, augmented with a preference function, that is used to reason about and possibly correct errors in these tests. This results in a more robust conditional independence test, called an argumentative independence test. Our experimental evaluation shows clear positive improvements in the accuracy of argumentative over purely statistical tests. We also demonstrate significant improvements on the accuracy of causal structure discovery from the outcomes of independence tests both on sampled data from randomly generated causal models and on real-world data sets.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {301–340},
numpages = {40}
}

@article{10.5555/1577069.1577080,
author = {Dasgupta, Sanjoy and Kalai, Adam Tauman and Monteleoni, Claire},
title = {Analysis of Perceptron-Based Active Learning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We start by showing that in an active learning setting, the Perceptron algorithm needs Ω(1/ε2) labels to learn linear separators within generalization error ε. We then present a simple active learning algorithm for this problem, which combines a modification of the Perceptron update with an adaptive filtering rule for deciding which points to query. For data distributed uniformly over the unit sphere, we show that our algorithm reaches generalization error ε after asking for just \~{O}(d log 1/ε) labels. This exponential improvement over the usual sample complexity of supervised learning had previously been demonstrated only for the computationally more complex query-by-committee algorithm.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {281–299},
numpages = {19}
}

@article{10.5555/1577069.1577079,
author = {Arlot, Sylvain and Massart, Pascal},
title = {Data-Driven Calibration of Penalties for Least-Squares Regression},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Penalization procedures often suffer from their dependence on multiplying factors, whose optimal values are either unknown or hard to estimate from data. We propose a completely data-driven calibration algorithm for these parameters in the least-squares regression framework, without assuming a particular shape for the penalty. Our algorithm relies on the concept of minimal penalty, recently introduced by Birg\'{e} and Massart (2007) in the context of penalized least squares for Gaussian homoscedastic regression. On the positive side, the minimal penalty can be evaluated from the data themselves, leading to a data-driven estimation of an optimal penalty which can be used in practice; on the negative side, their approach heavily relies on the homoscedastic Gaussian nature of their stochastic framework.The purpose of this paper is twofold: stating a more general heuristics for designing a data-driven penalty (the slope heuristics) and proving that it works for penalized least-squares regression with a random design, even for heteroscedastic non-Gaussian data. For technical reasons, some exact mathematical results will be proved only for regressogram bin-width selection. This is at least a first step towards further results, since the approach and the method that we use are indeed general.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {245–279},
numpages = {35}
}

@article{10.5555/1577069.1577078,
author = {Weinberger, Kilian Q. and Saul, Lawrence K.},
title = {Distance Metric Learning for Large Margin Nearest Neighbor Classification},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The accuracy of k-nearest neighbor (kNN) classification depends significantly on the metric used to compute distances between different examples. In this paper, we show how to learn a Mahalanobis distance metric for kNN classification from labeled examples. The Mahalanobis metric can equivalently be viewed as a global linear transformation of the input space that precedes kNN classification using Euclidean distances. In our approach, the metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. As in support vector machines (SVMs), the margin criterion leads to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our approach requires no modification or extension for problems in multiway (as opposed to binary) classification. In our framework, the Mahalanobis distance metric is obtained as the solution to a semidefinite program. On several data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification. Sometimes these results can be further improved by clustering the training examples and learning an individual metric within each cluster. We show how to learn and combine these local metrics in a globally integrated manner.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {207–244},
numpages = {38}
}

@article{10.5555/1577069.1577077,
author = {Vural, Volkan and Fung, Glenn and Krishnapuram, Balaji and Dy, Jennifer G. and Rao, Bharat},
title = {Using Local Dependencies within Batches to Improve Large Margin Classifiers},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Most classification methods assume that the samples are drawn independently and identically from an unknown data generating distribution, yet this assumption is violated in several real life problems. In order to relax this assumption, we consider the case where batches or groups of samples may have internal correlations, whereas the samples from different batches may be considered to be uncorrelated. This paper introduces three algorithms for classifying all the samples in a batch jointly: one based on a probabilistic formulation, and two based on mathematical programming analysis. Experiments on three real-life computer aided diagnosis (CAD) problems demonstrate that the proposed algorithms are significantly more accurate than a naive support vector machine which ignores the correlations among the samples.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {183–206},
numpages = {24}
}

@article{10.5555/1577069.1577076,
author = {Feldman, Vitaly},
title = {On The Power of Membership Queries in Agnostic Learning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We study the properties of the agnostic learning framework of Haussler (1992) and Kearns, Schapire, and Sellie (1994). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?Our results show that the answer is negative for distribution-independent agnostic learning and positive for agnostic learning with respect to a specific marginal distribution. Namely, we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries. This resolves an open problem posed by Kearns et al. (1994). For agnostic learning with respect to the uniform distribution over {0,1}n we show a concept class that is learnable with membership queries but computationally hard to learn from random examples alone (assuming that one-way functions exist).},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {163–182},
numpages = {20}
}

@article{10.5555/1577069.1577075,
author = {Shah, Abhik and Woolf, Peter},
title = {Python Environment for Bayesian Learning: Inferring the Structure of Bayesian Networks from Knowledge and Data},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {In this paper, we introduce PEBL, a Python library and application for learning Bayesian network structure from data and prior knowledge that provides features unmatched by alternative software packages: the ability to use interventional data, flexible specification of structural priors, modeling with hidden variables and exploitation of parallel processing.PEBL is released under the MIT open-source license, can be installed from the Python Package Index and is available at http://pebl-project.googlecode.com.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {159–162},
numpages = {4}
}

@article{10.5555/1577069.1577074,
author = {Su, Xiaogang and Tsai, Chih-Ling and Wang, Hansheng and Nickerson, David M. and Li, Bogong},
title = {Subgroup Analysis via Recursive Partitioning},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Subgroup analysis is an integral part of comparative analysis where assessing the treatment effect on a response is of central interest. Its goal is to determine the heterogeneity of the treatment effect across subpopulations. In this paper, we adapt the idea of recursive partitioning and introduce an interaction tree (IT) procedure to conduct subgroup analysis. The IT procedure automatically facilitates a number of objectively defined subgroups, in some of which the treatment effect is found prominent while in others the treatment has a negligible or even negative effect. The standard CART (Breiman et al., 1984) methodology is inherited to construct the tree structure. Also, in order to extract factors that contribute to the heterogeneity of the treatment effect, variable importance measure is made available via random forests of the interaction trees. Both simulated experiments and analysis of census wage data are presented for illustration.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {141–158},
numpages = {18}
}

@article{10.5555/1577069.1577073,
author = {Xu, Yuesheng and Zhang, Haizhang},
title = {Refinement of Reproducing Kernels},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {We continue our recent study on constructing a refinement kernel for a given kernel so that the reproducing kernel Hilbert space associated with the refinement kernel contains that with the original kernel as a subspace. To motivate this study, we first develop a refinement kernel method for learning, which gives an efficient algorithm for updating a learning predictor. Several characterizations of refinement kernels are then presented. It is shown that a nontrivial refinement kernel for a given kernel always exists if the input space has an infinite cardinal number. Refinement kernels for translation invariant kernels and Hilbert-Schmidt kernels are investigated. Various concrete examples are provided.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {107–140},
numpages = {34}
}

@article{10.5555/1577069.1577072,
author = {Kumar, M. Pawan and Kolmogorov, Vladimir and Torr, Philip H. S.},
title = {An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {The problem of obtaining the maximum a posteriori estimate of a general discrete Markov random field (i.e., a Markov random field defined using a discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximation algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger (1976) for a special case and independently in Chekuri et al. (2001), Koster et al. (1998), and Wainwright et al. (2005) for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation of Ravikumar and Lafferty (2006); and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki (2003) for two label problems and later extended by Kumar et al. (2006) for a general label set.We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e., provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which define constraints using random variables that form cycles or cliques in the graphical model representation of the random field. Using some examples we show that the new SOCP relaxations strictly dominate the previous approaches.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {71–106},
numpages = {36}
}

@article{10.5555/1577069.1577071,
author = {Kang, Changsung and Tian, Jin},
title = {Markov Properties for Linear Causal Models with Correlated Errors},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {A linear causal model with correlated errors, represented by a DAG with bi-directed edges, can be tested by the set of conditional independence relations implied by the model. A global Markov property specifies, by the d-separation criterion, the set of all conditional independence relations holding in any model associated with a graph. A local Markov property specifies a much smaller set of conditional independence relations which will imply all other conditional independence relations which hold under the global Markov property. For DAGs with bi-directed edges associated with arbitrary probability distributions, a local Markov property is given in Richardson (2003) which may invoke an exponential number of conditional independencies. In this paper, we show that for a class of linear structural equation models with correlated errors, there is a local Markov property which will invoke only a linear number of conditional independence relations. For general linear models, we provide a local Markov property that often invokes far fewer conditional independencies than that in Richardson (2003). The results have applications in testing linear structural equation models with correlated errors.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {41–70},
numpages = {30}
}

@article{10.5555/1577069.1577070,
author = {Larochelle, Hugo and Bengio, Yoshua and Louradour, J\'{e}r\^{o}me and Lamblin, Pascal},
title = {Exploring Strategies for Training Deep Neural Networks},
year = {2009},
issue_date = {12/1/2009},
publisher = {JMLR.org},
volume = {10},
issn = {1532-4435},
abstract = {Deep multi-layer neural networks have many levels of non-linearities allowing them to compactly represent highly non-linear and highly-varying functions. However, until recently it was not clear how to train such deep networks, since gradient-based optimization starting from random initialization often appears to get stuck in poor solutions. Hinton et al. recently proposed a greedy layer-wise unsupervised learning procedure relying on the training algorithm of restricted Boltzmann machines (RBM) to initialize the parameters of a deep belief network (DBN), a generative model with many layers of hidden causal variables. This was followed by the proposal of another greedy layer-wise procedure, relying on the usage of autoassociator networks. In the context of the above optimization problem, we study these algorithms empirically to better understand their success. Our experiments confirm the hypothesis that the greedy layer-wise unsupervised training strategy helps the optimization by initializing weights in a region near a good local minimum, but also implicitly acts as a sort of regularization that brings better generalization and encourages internal distributed representations that are high-level abstractions of the input. We also present a series of experiments aimed at evaluating the link between the performance of deep neural networks and practical aspects of their topology, for example, demonstrating cases where the addition of more depth helps. Finally, we empirically explore simple variants of these training algorithms, such as the use of different RBM input unit distributions, a simple way of combining gradient estimators to improve performance, as well as on-line versions of those algorithms.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1–40},
numpages = {40}
}

@article{10.5555/1390681.1442799,
author = {Biau, G\'{e}rard and Devroye, Luc and Lugosi, G\'{a}bor},
title = {Consistency of Random Forests and Other Averaging Classifiers},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In the last years of his life, Leo Breiman promoted random forests for use in classification. He suggested using averaging as a means of obtaining good discrimination rules. The base classifiers used for averaging are simple and randomized, often based on random samples from the data. He left a few questions unanswered regarding the consistency of such rules. In this paper, we give a number of theorems that establish the universal consistency of averaging rules. We also show that some popular classifiers, including one suggested by Breiman, are not universally consistent.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {2015–2033},
numpages = {19}
}

@article{10.5555/1390681.1442798,
author = {Airoldi, Edoardo M. and Blei, David M. and Fienberg, Stephen E. and Xing, Eric P.},
title = {Mixed Membership Stochastic Blockmodels},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Consider data consisting of pairwise measurements, such as presence or absence of links between pairs of objects. These data arise, for instance, in the analysis of protein interactions and gene regulatory networks, collections of author-recipient email, and social networks. Analyzing pairwise measurements with probabilistic models requires special assumptions, since the usual independence or exchangeability assumptions no longer hold. Here we introduce a class of variance allocation models for pairwise measurements: mixed membership stochastic blockmodels. These models combine global parameters that instantiate dense patches of connectivity (blockmodel) with local parameters that instantiate node-specific variability in the connections (mixed membership). We develop a general variational inference algorithm for fast approximate posterior inference. We demonstrate the advantages of mixed membership stochastic blockmodels with applications to social networks and protein interaction networks.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1981–2014},
numpages = {34}
}

@article{10.5555/1390681.1442797,
author = {Shpitser, Ilya and Pearl, Judea},
title = {Complete Identification Methods for the Causal Hierarchy},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We consider a hierarchy of queries about causal relationships in graphical models, where each level in the hierarchy requires more detailed information than the one below. The hierarchy consists of three levels: associative relationships, derived from a joint distribution over the observable variables; cause-effect relationships, derived from distributions resulting from external interventions; and counterfactuals, derived from distributions that span multiple "parallel worlds" and resulting from simultaneous, possibly conflicting observations and interventions. We completely characterize cases where a given causal query can be computed from information lower in the hierarchy, and provide algorithms that accomplish this computation. Specifically, we show when effects of interventions can be computed from observational studies, and when probabilities of counterfactuals can be computed from experimental studies. We also provide a graphical characterization of those queries which cannot be computed (by any method) from queries at a lower layer of the hierarchy.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1941–1979},
numpages = {39}
}

@article{10.5555/1390681.1442796,
author = {Goldberg, Yair and Zakai, Alon and Kushnir, Dan and Ritov, Ya'acov},
title = {Manifold Learning: The Price of Normalization},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We analyze the performance of a class of manifold-learning algorithms that find their output by minimizing a quadratic form under some normalization constraints. This class consists of Locally Linear Embedding (LLE), Laplacian Eigenmap, Local Tangent Space Alignment (LTSA), Hessian Eigenmaps (HLLE), and Diffusion maps. We present and prove conditions on the manifold that are necessary for the success of the algorithms. Both the finite sample case and the limit case are analyzed. We show that there are simple manifolds in which the necessary conditions are violated, and hence the algorithms cannot recover the underlying manifolds. Finally, we present numerical results that demonstrate our claims.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1909–1939},
numpages = {31}
}

@article{10.5555/1390681.1442795,
author = {Braun, Mikio L. and Buhmann, Joachim M. and M\"{u}ller, Klaus-Robert},
title = {On Relevant Dimensions in Kernel Feature Spaces},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We show that the relevant information of a supervised learning problem is contained up to negligible error in a finite number of leading kernel PCA components if the kernel matches the underlying learning problem in the sense that it can asymptotically represent the function to be learned and is sufficiently smooth. Thus, kernels do not only transform data sets such that good generalization can be achieved using only linear discriminant functions, but this transformation is also performed in a manner which makes economical use of feature space dimensions. In the best case, kernels provide efficient implicit representations of the data for supervised learning problems. Practically, we propose an algorithm which enables us to recover the number of leading kernel PCA components relevant for good classification. Our algorithm can therefore be applied (1) to analyze the interplay of data set and kernel in a geometric fashion, (2) to aid in model selection, and (3) to denoise in feature space in order to yield better classification results.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1875–1908},
numpages = {34}
}

@article{10.5555/1390681.1442794,
author = {Fan, Rong-En and Chang, Kai-Wei and Hsieh, Cho-Jui and Wang, Xiang-Rui and Lin, Chih-Jen},
title = {LIBLINEAR: A Library for Large Linear Classification},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {LIBLINEAR is an open source library for large-scale linear classification. It supports logistic regression and linear support vector machines. We provide easy-to-use command-line tools and library calls for users and developers. Comprehensive documents are available for both beginners and advanced users. Experiments demonstrate that LIBLINEAR is very efficient on large sparse data sets.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1871–1874},
numpages = {4}
}

@article{10.5555/1390681.1442793,
author = {Becerra-Bonache, Leonor and de la Higuera, Colin and Janodet, Jean-Christophe and Tantini, Fr\'{e}d\'{e}ric},
title = {Learning Balls of Strings from Edit Corrections},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {When facing the question of learning languages in realistic settings, one has to tackle several problems that do not admit simple solutions. On the one hand, languages are usually defined by complex grammatical mechanisms for which the learning results are predominantly negative, as the few algorithms are not really able to cope with noise. On the other hand, the learning settings themselves rely either on too simple information (text) or on unattainable one (query systems that do not exist in practice, nor can be simulated). We consider simple but sound classes of languages defined via the widely used edit distance: the balls of strings. We propose to learn them with the help of a new sort of queries, called the correction queries: when a string is submitted to the Oracle, either she accepts it if it belongs to the target language, or she proposes a correction, that is, a string of the language close to the query with respect to the edit distance. We show that even if the good balls are not learnable in Angluin's MAT model, they can be learned from a polynomial number of correction queries. Moreover, experimental evidence simulating a human Expert shows that this algorithm is resistant to approximate answers.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1841–1870},
numpages = {30}
}

@article{10.5555/1390681.1442792,
author = {Bartlett, Peter L. and Wegkamp, Marten H.},
title = {Classification with a Reject Option Using a Hinge Loss},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We consider the problem of binary classification where the classifier can, for a particular cost, choose not to classify an observation. Just as in the conventional classification problem, minimization of the sample average of the cost is a difficult optimization problem. As an alternative, we propose the optimization of a certain convex loss function φ, analogous to the hinge loss used in support vector machines (SVMs). Its convexity ensures that the sample average of this surrogate loss can be efficiently minimized. We study its statistical properties. We show that minimizing the expected surrogate loss—the φ-risk—also minimizes the risk. We also study the rate at which the φ-risk approaches its minimum value. We show that fast rates are possible when the conditional probability P(Y=1|X) is unlikely to be close to certain critical values.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1823–1840},
numpages = {18}
}

@article{10.5555/1390681.1442791,
author = {Collins, Michael and Globerson, Amir and Koo, Terry and Carreras, Xavier and Bartlett, Peter L.},
title = {Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Log-linear and maximum-margin models are two commonly-used methods in supervised machine learning, and are frequently used in structured prediction problems. Efficient learning of parameters in these models is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes exponentiated gradient (EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function; the dual in both the log-linear and max-margin cases corresponds to minimizing a convex function with simplex constraints. We study both batch and online variants of the algorithm, and provide rates of convergence for both cases. In the max-margin case, O(1/ε) EG updates are required to reach a given accuracy ε in the dual; in contrast, for log-linear models only O(log(1/ε)) updates are required. For both the max-margin and log-linear cases, our bounds suggest that the online EG algorithm requires a factor of n less computation to reach a desired accuracy than the batch EG algorithm, where n is the number of training examples. Our experiments confirm that the online algorithms are much faster than the batch algorithms in practice. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models. The algorithms are applied to a multi-class problem as well as to a more complex large-scale parsing task. In all these settings, the EG algorithms presented here outperform the other methods.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1775–1822},
numpages = {48}
}

@article{10.5555/1390681.1442790,
author = {Crammer, Koby and Kearns, Michael and Wortman, Jennifer},
title = {Learning from Multiple Sources},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We consider the problem of learning accurate models from multiple sources of "nearby" data. Given distinct samples from multiple data sources and estimates of the dissimilarities between these sources, we provide a general theory of which samples should be used to learn models for each source. This theory is applicable in a broad decision-theoretic learning framework, and yields general results for classification and regression. A key component of our approach is the development of approximate triangle inequalities for expected loss, which may be of independent interest. We discuss the related problem of learning parameters of a distribution from multiple data sources. Finally, we illustrate our theory through a series of synthetic simulations.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1757–1774},
numpages = {18}
}

@article{10.5555/1390681.1442789,
author = {Bax, Eric},
title = {Nearly Uniform Validation Improves Compression-Based Error Bounds},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {This paper develops bounds on out-of-sample error rates for support vector machines (SVMs). The bounds are based on the numbers of support vectors in the SVMs rather than on VC dimension. The bounds developed here improve on support vector counting bounds derived using Littlestone and Warmuth's compression-based bounding technique.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1741–1755},
numpages = {15}
}

@article{10.5555/1390681.1442788,
author = {Szlam, Arthur D. and Maggioni, Mauro and Coifman, Ronald R.},
title = {Regularization on Graphs with Function-Adapted Diffusion Processes},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Harmonic analysis and diffusion on discrete data has been shown to lead to state-of-the-art algorithms for machine learning tasks, especially in the context of semi-supervised and transductive learning. The success of these algorithms rests on the assumption that the function(s) to be studied (learned, interpolated, etc.) are smooth with respect to the geometry of the data. In this paper we present a method for modifying the given geometry so the function(s) to be studied are smoother with respect to the modified geometry, and thus more amenable to treatment using harmonic analysis methods. Among the many possible applications, we consider the problems of image denoising and transductive classification. In both settings, our approach improves on standard diffusion based methods.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1711–1739},
numpages = {29}
}

@article{10.5555/1390681.1442787,
author = {Cs\'{a}ji, Bal\'{a}zs Csan\'{a}d and Monostori, L\'{a}szl\'{o}},
title = {Value Function Based Reinforcement Learning in Changing Markovian Environments},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The paper investigates the possibility of applying value function based reinforcement learning (RL) methods in cases when the environment may change over time. First, theorems are presented which show that the optimal value function of a discounted Markov decision process (MDP) Lipschitz continuously depends on the immediate-cost function and the transition-probability function. Dependence on the discount factor is also analyzed and shown to be non-Lipschitz. Afterwards, the concept of (ε,δ)-MDPs is introduced, which is a generalization of MDPs and ε-MDPs. In this model the environment may change over time, more precisely, the transition function and the cost function may vary from time to time, but the changes must be bounded in the limit. Then, learning algorithms in changing environments are analyzed. A general relaxed convergence theorem for stochastic iterative algorithms is presented. We also demonstrate the results through three classical RL methods: asynchronous value iteration, Q-learning and temporal difference learning. Finally, some numerical experiments concerning changing environments are presented.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1679–1709},
numpages = {31}
}

@article{10.5555/1390681.1442786,
author = {Dalalyan, Arnak S. and Juditsky, Anatoly and Spokoiny, Vladimir},
title = {A New Algorithm for Estimating the Effective Dimension-Reduction Subspace},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The statistical problem of estimating the effective dimension-reduction (EDR) subspace in the multi-index regression model with deterministic design and additive noise is considered. A new procedure for recovering the directions of the EDR subspace is proposed. Many methods for estimating the EDR subspace perform principal component analysis on a family of vectors, say β1,...,βL, nearly lying in the EDR subspace. This is in particular the case for the structure-adaptive approach proposed by Hristache et al. (2001a). In the present work, we propose to estimate the projector onto the EDR subspace by the solution to the optimization problemminimize maxl=1,...,L βlT (I-A)βl    subject to A ∈ Amwhere Am is the set of all symmetric matrices with eigenvalues in [0,1] and trace less than or equal to m, with m being the true structural dimension. Under mild assumptions, √n-consistency of the proposed procedure is proved (up to a logarithmic factor) in the case when the structural dimension is not larger than 4. Moreover, the stochastic error of the estimator of the projector onto the EDR subspace is shown to depend on L logarithmically. This enables us to use a large number of vectors βl for estimating the EDR subspace. The empirical behavior of the algorithm is studied through numerical simulations.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1647–1678},
numpages = {32}
}

@article{10.5555/1390681.1442785,
author = {Caponnetto, Andrea and Micchelli, Charles A. and Pontil, Massimiliano and Ying, Yiming},
title = {Universal Multi-Task Kernels},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In this paper we are concerned with reproducing kernel Hilbert spaces HK of functions from an input space into a Hilbert space Y, an environment appropriate for multi-task learning. The reproducing kernel K associated to HK has its values as operators on Y. Our primary goal here is to derive conditions which ensure that the kernel K is universal. This means that on every compact subset of the input space, every continuous function with values in Y can be uniformly approximated by sections of the kernel. We provide various characterizations of universal kernels and highlight them with several concrete examples of some practical importance. Our analysis uses basic principles of functional analysis and especially the useful notion of vector measures which we describe in sufficient detail to clarify our results.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1615–1646},
numpages = {32}
}

@article{10.5555/1390681.1442784,
author = {Zhu, Jun and Nie, Zaiqing and Zhang, Bo and Wen, Ji-Rong},
title = {Dynamic Hierarchical Markov Random Fields for Integrated Web Data Extraction},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Existing template-independent web data extraction approaches adopt highly ineffective decoupled strategies---attempting to do data record detection and attribute labeling in two separate phases. In this paper, we propose an integrated web data extraction paradigm with hierarchical models. The proposed model is called Dynamic Hierarchical Markov Random Fields (DHMRFs). DHMRFs take structural uncertainty into consideration and define a joint distribution of both model structure and class labels. The joint distribution is an exponential family distribution. As a conditional model, DHMRFs relax the independence assumption as made in directed models. Since exact inference is intractable, a variational method is developed to learn the model's parameters and to find the MAP model structure and label assignments. We apply DHMRFs to a real-world web data extraction task. Experimental results show that: (1) integrated web data extraction models can achieve significant improvements on both record detection and attribute labeling compared to decoupled models; (2) in diverse web data extraction DHMRFs can potentially address the blocky artifact issue which is suffered by fixed-structured hierarchical models.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1583–1614},
numpages = {32}
}

@article{10.5555/1390681.1442783,
author = {Loustau, S\'{e}bastien},
title = {Aggregation of SVM Classifiers Using Sobolev Spaces},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {This paper investigates statistical performances of Support Vector Machines (SVM) and considers the problem of adaptation to the margin parameter and to complexity. In particular we provide a classifier with no tuning parameter. It is a combination of SVM classifiers.Our contribution is two-fold: (1) we propose learning rates for SVM using Sobolev spaces and build a numerically realizable aggregate that converges with same rate; (2) we present practical experiments of this method of aggregation for SVM using both Sobolev spaces and Gaussian kernels.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1559–1582},
numpages = {24}
}

@article{10.5555/1390681.1442782,
author = {Chhabra, Manu and Jacobs, Robert A.},
title = {Learning to Combine Motor Primitives Via Greedy Additive Regression},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The computational complexities arising in motor control can be ameliorated through the use of a library of motor synergies. We present a new model, referred to as the Greedy Additive Regression (GAR) model, for learning a library of torque sequences, and for learning the coefficients of a linear combination of sequences minimizing a cost function. From the perspective of numerical optimization, the GAR model is interesting because it creates a library of "local features"---each sequence in the library is a solution to a single training task---and learns to combine these sequences using a local optimization procedure, namely, additive regression. We speculate that learners with local representational primitives and local optimization procedures will show good performance on nonlinear tasks. The GAR model is also interesting from the perspective of motor control because it outperforms several competing models. Results using a simulated two-joint arm suggest that the GAR model consistently shows excellent performance in the sense that it rapidly learns to perform novel, complex motor tasks. Moreover, its library is overcomplete and sparse, meaning that only a small fraction of the stored torque sequences are used when learning a new movement. The library is also robust in the sense that, after an initial training period, nearly all novel movements can be learned as additive combinations of sequences in the library, and in the sense that it shows good generalization when an arm's dynamics are altered between training and test conditions, such as when a payload is added to the arm. Lastly, the GAR model works well regardless of whether motor tasks are specified in joint space or Cartesian space. We conclude that learning techniques using local primitives and optimization procedures are viable and potentially important methods for motor control and possibly other domains, and that these techniques deserve further examination by the artificial intelligence and cognitive science communities.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1535–1558},
numpages = {24}
}

@article{10.5555/1390681.1442781,
author = {Srinivasan, Ashwin and King, Ross D.},
title = {Incremental Identification of Qualitative Models of Biological Systems Using Inductive Logic Programming},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The use of computational models is increasingly expected to play an important role in predicting the behaviour of biological systems. Models are being sought at different scales of biological organisation namely: sub-cellular, cellular, tissue, organ, organism and ecosystem; with a view of identifying how different components are connected together, how they are controlled and how they behave when functioning as a system. Except for very simple biological processes, system identification from first principles can be extremely difficult. This has brought into focus automated techniques for constructing models using data of system behaviour. Such techniques face three principal issues: (1) The model representation language must be rich enough to capture system behaviour; (2) The system identification technique must be powerful enough to identify substantially complex models; and (3) There may not be sufficient data to obtain both the model's structure and precise estimates of all of its parameters. In this paper, we address these issues in the following ways: (1) Models are represented in an expressive subset of first-order logic. Specifically, they are expressed as logic programs; (2) System identification is done using techniques developed in Inductive Logic Programming (ILP). This allows the identification of first-order logic models from data. Specifically, we employ an incremental approach in which increasingly complex models are constructed from simpler ones using snapshots of system behaviour; and (3) We restrict ourselves to "qualitative" models. These are non-parametric: thus, usually less data are required than for identifying parametric quantitative models. A further advantage is that the data need not be precise numerical observations (instead, they are abstractions like positive, negative, zero, increasing, decreasing and so on). We describe incremental construction of qualitative models using a simple physical system and demonstrate its application to identification of models at four scales of biological organisation, namely: (a) a predator-prey model at the ecosystem level; (b) a model for the human lung at the organ level; (c) a model for regulation of glucose by insulin in the human body at the extra-cellular level; and (d) a model for the glycolysis metabolic pathway at the cellular level.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1475–1533},
numpages = {59}
}

@article{10.5555/1390681.1442780,
author = {Zhang, Jiji},
title = {Causal Reasoning with Ancestral Graphs},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Causal reasoning is primarily concerned with what would happen to a system under external interventions. In particular, we are often interested in predicting the probability distribution of some random variables that would result if some other variables were forced to take certain values. One prominent approach to tackling this problem is based on causal Bayesian networks, using directed acyclic graphs as causal diagrams to relate post-intervention probabilities to pre-intervention probabilities that are estimable from observational data. However, such causal diagrams are seldom fully testable given observational data. In consequence, many causal discovery algorithms based on data-mining can only output an equivalence class of causal diagrams (rather than a single one). This paper is concerned with causal reasoning given an equivalence class of causal diagrams, represented by a (partial) ancestral graph. We present two main results. The first result extends Pearl (1995)'s celebrated do-calculus to the context of ancestral graphs. In the second result, we focus on a key component of Pearl's calculus---the property of invariance under interventions, and give stronger graphical conditions for this property than those implied by the first result. The second result also improves the earlier, similar results due to Spirtes et al. (1993).},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1437–1474},
numpages = {38}
}

@article{10.5555/1390681.1442779,
author = {Amit, Yonatan and Shalev-Shwartz, Shai and Singer, Yoram},
title = {Online Learning of Complex Prediction Problems Using Simultaneous Projections},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We describe and analyze an algorithmic framework for online classification where each online trial consists of multiple prediction tasks that are tied together. We tackle the problem of updating the online predictor by defining a projection problem in which each prediction task corresponds to a single linear constraint. These constraints are tied together through a single slack parameter. We then introduce a general method for approximately solving the problem by projecting simultaneously and independently on each constraint which corresponds to a prediction sub-problem, and then averaging the individual solutions. We show that this approach constitutes a feasible, albeit not necessarily optimal, solution of the original projection problem. We derive concrete simultaneous projection schemes and analyze them in the mistake bound model. We demonstrate the power of the proposed algorithm in experiments with synthetic data and with multiclass text categorization tasks.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1399–1435},
numpages = {37}
}

@article{10.5555/1390681.1442778,
author = {Chang, Kai-Wei and Hsieh, Cho-Jui and Lin, Chih-Jen},
title = {Coordinate Descent Method for Large-Scale L2-Loss Linear Support Vector Machines},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Linear support vector machines (SVM) are useful for classifying large-scale sparse data. Problems with sparse features are common in applications such as document classification and natural language processing. In this paper, we propose a novel coordinate descent algorithm for training linear SVM with the L2-loss function. At each step, the proposed method minimizes a one-variable sub-problem while fixing other variables. The sub-problem is solved by Newton steps with the line search technique. The procedure globally converges at the linear rate. As each sub-problem involves only values of a corresponding feature, the proposed approach is suitable when accessing a feature is more convenient than accessing an instance. Experiments show that our method is more efficient and stable than state of the art methods such as Pegasos and TRON.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1369–1398},
numpages = {30}
}

@article{10.5555/1390681.1442777,
author = {Koo, Ja-Yong and Lee, Yoonkyung and Kim, Yuwon and Park, Changyi},
title = {A Bahadur Representation of the Linear Support Vector Machine},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {The support vector machine has been successful in a variety of applications. Also on the theoretical front, statistical properties of the support vector machine have been studied quite extensively with a particular attention to its Bayes risk consistency under some conditions. In this paper, we study somewhat basic statistical properties of the support vector machine yet to be investigated, namely the asymptotic behavior of the coefficients of the linear support vector machine. A Bahadur type representation of the coefficients is established under appropriate conditions, and their asymptotic normality and statistical variability are derived on the basis of the representation. These asymptotic results do not only help further our understanding of the support vector machine, but also they can be useful for related statistical inferences.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1343–1368},
numpages = {26}
}

@article{10.5555/1390681.1442776,
author = {Pellet, Jean-Philippe and Elisseeff, Andr\'{e}},
title = {Using Markov Blankets for Causal Structure Learning},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We show how a generic feature-selection algorithm returning strongly relevant variables can be turned into a causal structure-learning algorithm. We prove this under the Faithfulness assumption for the data distribution. In a causal graph, the strongly relevant variables for a node X are its parents, children, and children's parents (or spouses), also known as the Markov blanket of X. Identifying the spouses leads to the detection of the V-structure patterns and thus to causal orientations. Repeating the task for all variables yields a valid partially oriented causal graph. We first show an efficient way to identify the spouse links. We then perform several experiments in the continuous domain using the Recursive Feature Elimination feature-selection algorithm with Support Vector Regression and empirically verify the intuition of this direct (but computationally expensive) approach. Within the same framework, we then devise a fast and consistent algorithm, Total Conditioning (TC), and a variant, TCbw, with an explicit backward feature-selection heuristics, for Gaussian data. After running a series of comparative experiments on five artificial networks, we argue that Markov blanket algorithms such as TC/TCbw or Grow-Shrink scale better than the reference PC algorithm and provides higher structural accuracy.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1295–1342},
numpages = {48}
}

@article{10.5555/1390681.1442775,
author = {d'Aspremont, Alexandre and Bach, Francis and Ghaoui, Laurent El},
title = {Optimal Solutions for Sparse Principal Component Analysis},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Given a sample covariance matrix, we examine the problem of maximizing the variance explained by a linear combination of the input variables while constraining the number of nonzero coefficients in this combination. This is known as sparse principal component analysis and has a wide array of applications in machine learning and engineering. We formulate a new semidefinite relaxation to this problem and derive a greedy algorithm that computes a full set of good solutions for all target numbers of non zero coefficients, with total complexity O(n3), where n is the number of variables. We then use the same relaxation to derive sufficient conditions for global optimality of a solution, which can be tested in O(n3), per pattern. We discuss applications in subset selection and sparse recovery and show on artificial examples and biological data that our algorithm does provide globally optimal solutions in many cases.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1269–1294},
numpages = {26}
}

@article{10.5555/1390681.1390722,
author = {L\"{u}cke, J\"{o}rg and Sahani, Maneesh},
title = {Maximal Causes for Non-Linear Component Extraction},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We study a generative model in which hidden causes combine competitively to produce observations. Multiple active causes combine to determine the value of an observed variable through a max function, in the place where algorithms such as sparse coding, independent component analysis, or non-negative matrix factorization would use a sum. This max rule can represent a more realistic model of non-linear interaction between basic components in many settings, including acoustic and image data. While exact maximum-likelihood learning of the parameters of this model proves to be intractable, we show that efficient approximations to expectation-maximization (EM) can be found in the case of sparsely active hidden causes. One of these approximations can be formulated as a neural network model with a generalized softmax activation function and Hebbian learning. Thus, we show that learning in recent softmax-like neural networks may be interpreted as approximate maximization of a data likelihood. We use the bars benchmark test to numerically verify our analytical results and to demonstrate the competitiveness of the resulting algorithms. Finally, we show results of learning model parameters to fit acoustic and visual data sets in which max-like component combinations arise naturally.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1227–1267},
numpages = {41}
}

@article{10.5555/1390681.1390721,
author = {Bach, Francis R.},
title = {Consistency of the Group Lasso and Multiple Kernel Learning},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We consider the least-square regression problem with regularization by a block l1-norm, that is, a sum of Euclidean norms over spaces of dimensions larger than one. This problem, referred to as the group Lasso, extends the usual regularization by the l1-norm where all spaces have dimension one, where it is commonly referred to as the Lasso. In this paper, we study the asymptotic group selection consistency of the group Lasso. We derive necessary and sufficient conditions for the consistency of group Lasso under practical assumptions, such as model mis specification. When the linear predictors and Euclidean norms are replaced by functions and reproducing kernel Hilbert norms, the problem is usually referred to as multiple kernel learning and is commonly used for learning from heterogeneous data sources and for non linear variable selection. Using tools from functional analysis, and in particular covar iance operators, we extend the consistency results to this infinite dimensional case and also propose an adaptive scheme to obtain a consistent model estimate, even when the necessary condition required for the non adaptive scheme is not satisfied.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1179–1225},
numpages = {47}
}

@article{10.5555/1390681.1390720,
author = {Seeger, Matthias W.},
title = {Cross-Validation Optimization for Large Scale Structured Classification Kernel Methods},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {We propose a highly efficient framework for penalized likelihood kernel methods applied to multi-class models with a large, structured set of classes. As opposed to many previous approaches which try to decompose the fitting problem into many smaller ones, we focus on a Newton optimization of the complete model, making use of model structure and linear conjugate gradients in order to approximate Newton search directions. Crucially, our learning method is based entirely on matrix-vector multiplication primitives with the kernel matrices and their derivatives, allowing straightforward specialization to new kernels, and focusing code optimization efforts to these primitives only.Kernel parameters are learned automatically, by maximizing the cross-validation log likelihood in a gradient-based way, and predictive probabilities are estimated. We demonstrate our approach on large scale text classification tasks with hierarchical structure on thousands of classes, achieving state-of-the-art results in an order of magnitude less time than previous work.Parts of this work appeared in the conference paper Seeger (2007).},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1147–1178},
numpages = {32}
}

@article{10.5555/1390681.1390719,
author = {Jorgensen, Zach and Zhou, Yan and Inge, Meador},
title = {A Multiple Instance Learning Strategy for Combating Good Word Attacks on Spam Filters},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Statistical spam filters are known to be vulnerable to adversarial attacks. One of the more common adversarial attacks, known as the good word attack, thwarts spam filters by appending to spam messages sets of "good" words, which are words that are common in legitimate email but rare in spam. We present a counterattack strategy that attempts to differentiate spam from legitimate email in the input space by transforming each email into a bag of multiple segments, and subsequently applying multiple instance logistic regression on the bags. We treat each segment in the bag as an instance. An email is classified as spam if at least one instance in the corresponding bag is spam, and as legitimate if all the instances in it are legitimate. We show that a classifier using our multiple instance counterattack strategy is more robust to good word attacks than its single instance counterpart and other single instance learners commonly used in the spam filtering domain.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1115–1146},
numpages = {32}
}

@article{10.5555/1390681.1390718,
author = {Sabato, Sivan and Shalev-Shwartz, Shai},
title = {Ranking Categorical Features Using Generalization Properties},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Feature ranking is a fundamental machine learning task with various applications, including feature selection and decision tree learning. We describe and analyze a new feature ranking method that supports categorical features with a large number of possible values. We show that existing ranking criteria rank a feature according to the training error of a predictor based on the feature. This approach can fail when ranking categorical features with many values. We propose the Ginger ranking criterion, that estimates the generalization error of the predictor associated with the Gini index. We show that for almost all training sets, the Ginger criterion produces an accurate estimation of the true generalization error, regardless of the number of values in a categorical feature. We also address the question of finding the optimal predictor that is based on a single categorical feature. It is shown that the predictor associated with the misclassification error criterion has the minimal expected generalization error. We bound the bias of this predictor with respect to the generalization error of the Bayes optimal predictor, and analyze its concentration properties. We demonstrate the efficiency of our approach for feature selection and for learning decision trees in a series of experiments with synthetic and natural data sets.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1083–1114},
numpages = {32}
}

@article{10.5555/1390681.1390717,
author = {Maurer, Andreas},
title = {Learning Similarity with Operator-Valued Large-Margin Classifiers},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {A method is introduced to learn and represent similarity with linear operators in kernel induced Hilbert spaces. Transferring error bounds for vector valued large-margin classifiers to the setting of Hilbert-Schmidt operators leads to dimension free bounds on a risk functional for linear representations and motivates a regularized objective functional. Minimization of this objective is effected by a simple technique of stochastic gradient descent. The resulting representations are tested on transfer problems in image processing, involving plane and spatial geometric invariants, handwritten characters and face recognition.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1049–1082},
numpages = {34}
}

@article{10.5555/1390681.1390716,
author = {Bach, Francis R.},
title = {Consistency of Trace Norm Minimization},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Regularization by the sum of singular values, also referred to as the trace norm, is a popular technique for estimating low rank rectangular matrices. In this paper, we extend some of the consistency results of the Lasso to provide necessary and sufficient conditions for rank consistency of trace norm minimization with the square loss. We also provide an adaptive version that is rank consistent even when the necessary condition for the non adaptive version is not fulfilled.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {1019–1048},
numpages = {30}
}

@article{10.5555/1390681.1390715,
author = {Marchiori, Elena},
title = {Hit Miss Networks with Applications to Instance Selection},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {In supervised learning, a training set consisting of labeled instances is used by a learning algorithm for generating a model (classifier) that is subsequently employed for deciding the class label of new instances (for generalization). Characteristics of the training set, such as presence of noisy instances and size, influence the learning algorithm and affect generalization performance. This paper introduces a new network-based representation of a training set, called hit miss network (HMN), which provides a compact description of the nearest neighbor relation over pairs of instances from each pair of classes. We show that structural properties of HMN's correspond to properties of training points related to the one nearest neighbor (1-NN) decision rule, such as being border or central point. This motivates us to use HMN's for improving the performance of a 1-NN, classifier by removing instances from the training set (instance selection). We introduce three new HMN-based algorithms for instance selection. HMN-C, which removes instances without affecting accuracy of 1-NN on the original training set, HMN-E, based on a more aggressive storage reduction, and HMN-EI, which applies iteratively HMN-E. Their performance is assessed on 22 data sets with different characteristics, such as input dimension, cardinality, class balance, number of classes, noise content, and presence of redundant variables. Results of experiments on these data sets show that accuracy of 1-NN classifier increases significantly when HMN-EI is applied. Comparison with state-of-the-art editing algorithms for instance selection on these data sets indicates best generalization performance of HMN-EI and no significant difference in storage requirements. In general, these results indicate that HMN's provide a powerful graph-based representation of a training set, which can be successfully applied for performing noise and redundance reduction in instance-based learning.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {997–1017},
numpages = {21}
}

@article{10.5555/1390681.1390714,
author = {Igel, Christian and Heidrich-Meisner, Verena and Glasmachers, Tobias},
title = {Shark},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {SHARK is an object-oriented library for the design of adaptive systems. It comprises methods for single- and multi-objective optimization (e.g., evolutionary and gradient-based algorithms) as well as kernel-based methods, neural networks, and other machine learning techniques.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {993–996},
numpages = {4}
}

@article{10.5555/1390681.1390713,
author = {Chu, Tianjiao and Glymour, Clark},
title = {Search for Additive Nonlinear Time Series Causal Models},
year = {2008},
issue_date = {6/1/2008},
publisher = {JMLR.org},
volume = {9},
issn = {1532-4435},
abstract = {Pointwise consistent, feasible procedures for estimating contemporaneous linear causal structure from time series data have been developed using multiple conditional independence tests, but no such procedures are available for non-linear systems. We describe a feasible procedure for learning a class of non-linear time series structures, which we call additive non-linear time series. We show that for data generated from stationary models of this type, two classes of conditional independence relations among time series variables and their lags can be tested efficiently and consistently using tests based on additive model regression. Combining results of statistical tests for these two classes of conditional independence relations and the temporal structure of time series data, a new consistent model specification procedure is able to extract relatively detailed causal information. We investigate the finite sample behavior of the procedure through simulation, and illustrate the application of this method through analysis of the possible causal connections among four ocean indices. Several variants of the procedure are also discussed.},
journal = {J. Mach. Learn. Res.},
month = jun,
pages = {967–991},
numpages = {25}
}

@article{10.5555/1390681.1390712,
author = {Gomez, Faustino and Schmidhuber, J\"{u}rgen and Miikkulainen, Risto},
title = {Accelerated Neural Evolution through Cooperatively Coevolved Synapses},
year = {2008},
issue_date = {6/

license_type: permissive

branch_name: refs/heads/main

extension: bib