text:
3048.1953065,
author = {Aflalo, Jonathan and Ben-Tal, Aharon and Bhattacharyya, Chiranjib and Nath, Jagarlapudi Saketha and Raman, Sankaran},
title = {Variable Sparsity Kernel Learning},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {This paper presents novel algorithms and applications for a particular class of mixed-norm regularization based Multiple Kernel Learning (MKL) formulations. The formulations assume that the given kernels are grouped and employ l1 norm regularization for promoting sparsity within RKHS norms of each group and ls, s≥2 norm regularization for promoting non-sparse combinations across groups. Various sparsity levels in combining the kernels can be achieved by varying the grouping of kernels---hence we name the formulations as Variable Sparsity Kernel Learning (VSKL) formulations. While previous attempts have a non-convex formulation, here we present a convex formulation which admits efficient Mirror-Descent (MD) based solving techniques. The proposed MD based algorithm optimizes over product of simplices and has a computational complexity of O(m2ntot log nmax/ε2) where m is no. training data points, nmax,ntot are the maximum no. kernels in any group, total no. kernels respectively and ε is the error in approximating the objective. A detailed proof of convergence of the algorithm is also presented. Experimental results show that the VSKL formulations are well-suited for multi-modal learning tasks like object categorization. Results also show that the MD based algorithm outperforms state-of-the-art MKL solvers in terms of computational efficiency.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {565–592},
numpages = {28}
}

@article{10.5555/1953048.1953064,
author = {Dhillon, Paramveer S. and Foster, Dean and Ungar, Lyle H.},
title = {Minimum Description Length Penalization for Group and Multi-Task Sparse Learning},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {We propose a framework MIC (Multiple Inclusion Criterion) for learning sparse models based on the information theoretic Minimum Description Length (MDL) principle. MIC provides an elegant way of incorporating arbitrary sparsity patterns in the feature space by using two-part MDL coding schemes. We present MIC based models for the problems of grouped feature selection (MIC-GROUP) and multi-task feature selection (MIC-MULTI). MIC-GROUP assumes that the features are divided into groups and induces two level sparsity, selecting a subset of the feature groups, and also selecting features within each selected group. MIC-MULTI applies when there are multiple related tasks that share the same set of potentially predictive features. It also induces two level sparsity, selecting a subset of the features, and then selecting which of the tasks each feature should be added to. Lastly, we propose a model, TRANSFEAT, that can be used to transfer knowledge from a set of previously learned tasks to a new task that is expected to share similar features. All three methods are designed for selecting a small set of predictive features from a large pool of candidate features. We demonstrate the effectiveness of our approach with experimental results on data from genomics and from word sense disambiguation problems.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {525–564},
numpages = {40}
}

@article{10.5555/1953048.1953063,
author = {McFee, Brian and Lanckriet, Gert},
title = {Learning Multi-Modal Similarity},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {In many applications involving multi-media data, the definition of similarity between items is integral to several key tasks, including nearest-neighbor retrieval, classification, and recommendation. Data in such regimes typically exhibits multiple modalities, such as acoustic and visual content of video. Integrating such heterogeneous data to form a holistic similarity space is therefore a key challenge to be overcome in many real-world applications. We present a novel multiple kernel learning technique for integrating heterogeneous data into a single, unified similarity space. Our algorithm learns an optimal ensemble of kernel transformations which conform to measurements of human perceptual similarity, as expressed by relative comparisons. To cope with the ubiquitous problems of subjectivity and inconsistency in multi-media similarity, we develop graph-based techniques to filter similarity measurements, resulting in a simplified and robust training procedure.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {491–523},
numpages = {33}
}

@article{10.5555/1953048.1953062,
author = {Gillenwater, Jennifer and Ganchev, Kuzman and Gra\c{c}a, Jo\~{a}o and Pereira, Fernando and Taskar, Ben},
title = {Posterior Sparsity in Unsupervised Dependency Parsing},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {A strong inductive bias is essential in unsupervised grammar induction. In this paper, we explore a particular sparsity bias in dependency grammars that encourages a small number of unique dependency types. We use part-of-speech (POS) tags to group dependencies by parent-child types and investigate sparsity-inducing penalties on the posterior distributions of parent-child POS tag pairs in the posterior regularization (PR) framework of Gra\c{c}a et al. (2007). In experiments with 12 different languages, we achieve significant gains in directed attachment accuracy over the standard expectation maximization (EM) baseline, with an average accuracy improvement of 6.5%, outperforming EM by at least 1% for 9 out of 12 languages. Furthermore, the new method outperforms models based on standard Bayesian sparsity-inducing parameter priors with an average improvement of 5% and positive gains of at least 1% for 9 out of 12 languages. On English text in particular, we show that our approach improves performance over other state-of-the-art techniques.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {455–490},
numpages = {36}
}

@article{10.5555/1953048.1953061,
author = {Cseke, Botond and Heskes, Tom},
title = {Approximate Marginals in Latent Gaussian Models},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {We consider the problem of improving the Gaussian approximate posterior marginals computed by expectation propagation and the Laplace method in latent Gaussian models and propose methods that are similar in spirit to the Laplace approximation of Tierney and Kadane (1986). We show that in the case of sparse Gaussian models, the computational complexity of expectation propagation can be made comparable to that of the Laplace method by using a parallel updating scheme. In some cases, expectation propagation gives excellent estimates where the Laplace approximation fails. Inspired by bounds on the correct marginals, we arrive at factorized approximations, which can be applied on top of both expectation propagation and the Laplace method. The factorized approximations can give nearly indistinguishable results from the non-factorized approximations and their computational complexity scales linearly with the number of variables. We experienced that the expectation propagation based marginal approximations we introduce are typically more accurate than the methods of similar complexity proposed by Rue et al. (2009).},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {417–454},
numpages = {38}
}

@article{10.5555/1953048.1953060,
author = {Pelletier, Bruno and Pudlo, Pierre},
title = {Operator Norm Convergence of Spectral Clustering on Level Sets},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {Following Hartigan (1975), a cluster is defined as a connected component of the t-level set of the underlying density, that is, the set of points for which the density is greater than t. A clustering algorithm which combines a density estimate with spectral clustering techniques is proposed. Our algorithm is composed of two steps. First, a nonparametric density estimate is used to extract the data points for which the estimated density takes a value greater than t. Next, the extracted points are clustered based on the eigenvectors of a graph Laplacian matrix. Under mild assumptions, we prove the almost sure convergence in operator norm of the empirical graph Laplacian operator associated with the algorithm. Furthermore, we give the typical behavior of the representation of the data set into the feature space, which establishes the strong consistency of our proposed algorithm.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {385–416},
numpages = {32}
}

@article{10.5555/1953048.1953059,
author = {Zilles, Sandra and Lange, Steffen and Holte, Robert and Zinkevich, Martin},
title = {Models of Cooperative Teaching and Learning},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {While most supervised machine learning models assume that training examples are sampled at random or adversarially, this article is concerned with models of learning from a cooperative teacher that selects "helpful" training examples. The number of training examples a learner needs for identifying a concept in a given class C of possible target concepts (sample complexity of C) is lower in models assuming such teachers, that is, "helpful" examples can speed up the learning process. The problem of how a teacher and a learner can cooperate in order to reduce the sample complexity, yet without using "coding tricks", has been widely addressed. Nevertheless, the resulting teaching and learning protocols do not seem to make the teacher select intuitively "helpful" examples. The two models introduced in this paper are built on what we call subset teaching sets and recursive teaching sets. They extend previous models of teaching by letting both the teacher and the learner exploit knowing that the partner is cooperative. For this purpose, we introduce a new notion of "coding trick"/"collusion". We show how both resulting sample complexity measures (the subset teaching dimension and the recursive teaching dimension) can be arbitrarily lower than the classic teaching dimension and known variants thereof, without using coding tricks. For instance, monomials can be taught with only two examples independent of the number of variables. The subset teaching dimension turns out to be nonmonotonic with respect to subclasses of concept classes. We discuss why this nonmonotonicity might be inherent in many interesting cooperative teaching and learning scenarios.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {349–384},
numpages = {36}
}

@article{10.5555/1953048.1953058,
author = {Huang, Jim C. and Frey, Brendan J.},
title = {Cumulative Distribution Networks and the Derivative-Sum-Product Algorithm: Models and Inference for Cumulative Distribution Functions on Graphs},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {We present a class of graphical models for directly representing the joint cumulative distribution function (CDF) of many random variables, called cumulative distribution networks (CDNs). Unlike graphs for probability density and mass functions, for CDFs the marginal probabilities for any subset of variables are obtained by computing limits of functions in the model, and conditional probabilities correspond to computing mixed derivatives. We will show that the conditional independence properties in a CDN are distinct from the conditional independence properties of directed, undirected and factor graphs, but include the conditional independence properties of bi-directed graphs. In order to perform inference in such models, we describe the `derivative-sum-product' (DSP) message-passing algorithm in which messages correspond to derivatives of the joint CDF. We will then apply CDNs to the problem of learning to rank players in multiplayer team-based games and suggest several future directions for research.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {301–348},
numpages = {48}
}

@article{10.5555/1953048.1953057,
author = {Weng, Ruby C. and Lin, Chih-Jen},
title = {A Bayesian Approximation Method for Online Ranking},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {This paper describes a Bayesian approximation method to obtain online ranking algorithms for games with multiple teams and multiple players. Recently for Internet games large online ranking systems are much needed. We consider game models in which a k-team game is treated as several two-team games. By approximating the expectation of teams' (or players') performances, we derive simple analytic update rules. These update rules, without numerical integrations, are very easy to interpret and implement. Experiments on game data show that the accuracy of our approach is competitive with state of the art systems such as TrueSkill, but the running time as well as the code is much shorter.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {267–300},
numpages = {34}
}

@article{10.5555/1953048.1953056,
author = {V'yugin, Vladimir V.},
title = {Online Learning in Case of Unbounded Losses Using Follow the Perturbed Leader Algorithm},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {In this paper the sequential prediction problem with expert advice is considered for the case where losses of experts suffered at each step cannot be bounded in advance. We present some modification of Kalai and Vempala algorithm of following the perturbed leader where weights depend on past losses of the experts. New notions of a volume and a scaled fluctuation of a game are introduced. We present a probabilistic algorithm protected from unrestrictedly large one-step losses. This algorithm has the optimal performance in the case when the scaled fluctuations of one-step losses of experts of the pool tend to zero.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {241–266},
numpages = {26}
}

@article{10.5555/1953048.1953055,
author = {Ren, Lu and Du, Lan and Carin, Lawrence and Dunson, David},
title = {Logistic Stick-Breaking Process},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {A logistic stick-breaking process (LSBP) is proposed for non-parametric clustering of general spatially- or temporally-dependent data, imposing the belief that proximate data are more likely to be clustered together. The sticks in the LSBP are realized via multiple logistic regression functions, with shrinkage priors employed to favor contiguous and spatially localized segments. The LSBP is also extended for the simultaneous processing of multiple data sets, yielding a hierarchical logistic stick-breaking process (H-LSBP). The model parameters (atoms) within the H-LSBP are shared across the multiple learning tasks. Efficient variational Bayesian inference is derived, and comparisons are made to related techniques in the literature. Experimental analysis is performed for audio waveforms and images, and it is demonstrated that for segmentation applications the LSBP yields generally homogeneous segments with sharp boundaries.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {203–239},
numpages = {37}
}

@article{10.5555/1953048.1953054,
author = {Steinwart, Ingo and Hush, Don and Scovel, Clint},
title = {Training SVMs Without Offset},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {We develop, analyze, and test a training algorithm for support vector machine classifiers without offset. Key features of this algorithm are a new, statistically motivated stopping criterion, new warm start options, and a set of inexpensive working set selection strategies that significantly reduce the number of iterations. For these working set strategies, we establish convergence rates that, not surprisingly, coincide with the best known rates for SVMs with offset. We further conduct various experiments that investigate both the run time behavior and the performed iterations of the new training algorithm. It turns out, that the new algorithm needs significantly less iterations and also runs substantially faster than standard training algorithms for SVMs with offset.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {141–202},
numpages = {62}
}

@article{10.5555/1953048.1953053,
author = {Zhang, Zhihua and Dai, Guang and Jordan, Michael I.},
title = {Bayesian Generalized Kernel Mixed Models},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {We propose a fully Bayesian methodology for generalized kernel mixed models (GKMMs), which are extensions of generalized linear mixed models in the feature space induced by a reproducing kernel. We place a mixture of a point-mass distribution and Silverman's g-prior on the regression vector of a generalized kernel model (GKM). This mixture prior allows a fraction of the components of the regression vector to be zero. Thus, it serves for sparse modeling and is useful for Bayesian computation. In particular, we exploit data augmentation methodology to develop a Markov chain Monte Carlo (MCMC) algorithm in which the reversible jump method is used for model selection and a Bayesian model averaging method is used for posterior prediction. When the feature basis expansion in the reproducing kernel Hilbert space is treated as a stochastic process, this approach can be related to the Karhunen-Lo\`{e}ve expansion of a Gaussian process (GP). Thus, our sparse modeling framework leads to a flexible approximation method for GPs.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {111–139},
numpages = {29}
}

@article{10.5555/1953048.1953052,
author = {Jebara, Tony},
title = {Multitask Sparsity via Maximum Entropy Discrimination},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {A multitask learning framework is developed for discriminative classification and regression where multiple large-margin linear classifiers are estimated for different prediction problems. These classifiers operate in a common input space but are coupled as they recover an unknown shared representation. A maximum entropy discrimination (MED) framework is used to derive the multitask algorithm which involves only convex optimization problems that are straightforward to implement. Three multitask scenarios are described. The first multitask method produces multiple support vector machines that learn a shared sparse feature selection over the input space. The second multitask method produces multiple support vector machines that learn a shared conic kernel combination. The third multitask method produces a pooled classifier as well as adaptively specialized individual classifiers. Furthermore, extensions to regression, graphical model structure estimation and other sparse methods are discussed. The maximum entropy optimization problems are implemented via a sequential quadratic programming method which leverages recent progress in fast SVM solvers. Fast monotonic convergence bounds are provided by bounding the MED sparsifying cost function with a quadratic function and ensuring only a constant factor runtime increase above standard independent SVM solvers. Results are shown on multitask data sets and favor multitask learning over single-task or tabula rasa methods.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {75–110},
numpages = {36}
}

@article{10.5555/1953048.1953051,
author = {Melnykov, Volodymyr and Maitra, Ranjan},
title = {CARP: Software for Fishing Out Good Clustering Algorithms},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {This paper presents the CLUSTERING ALGORITHMS' REFEREE PACKAGE or CARP, an open source GNU GPL-licensed C package for evaluating clustering algorithms. Calibrating performance of such algorithms is important and CARP addresses this need by generating datasets of different clustering complexity and by assessing the performance of the concerned algorithm in terms of its ability to classify each dataset relative to the true grouping. This paper briefly describes the software and its capabilities.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {69–73},
numpages = {5}
}

@article{10.5555/1953048.1953050,
author = {Kumar, M. Pawan and Veksler, Olga and Torr, Philip H.S.},
title = {Improved Moves for Truncated Convex Models},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {We consider the problem of obtaining an approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose two st-MINCUT based move making algorithms that we call Range Swap and Range Expansion. Our algorithms can be thought of as extensions of αβ-Swap and α-Expansion respectively that fully exploit the form of the pairwise potentials. Specifically, instead of dealing with one or two labels at each iteration, our methods explore a large search space by considering a range of labels (that is, an interval of consecutive labels). Furthermore, we show that Range Expansion provides the same multiplicative bounds as the standard linear programming (LP) relaxation in polynomial time. Compared to previous approaches based on the LP relaxation, for example interior-point algorithms or tree-reweighted message passing (TRW), our methods are faster as they use only the efficient st-MINCUT algorithm in their design. We demonstrate the usefulness of the proposed approaches on both synthetic and standard real data problems.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {31–67},
numpages = {37}
}

@article{10.5555/1953048.1953049,
author = {Ni, Yizhao and Saunders, Craig and Szedmak, Sandor and Niranjan, Mahesan},
title = {Exploitation of Machine Learning Techniques in Modelling Phrase Movements for Machine Translation},
year = {2011},
issue_date = {2/1/2011},
publisher = {JMLR.org},
volume = {12},
number = {null},
issn = {1532-4435},
abstract = {We propose a distance phrase reordering model (DPR) for statistical machine translation (SMT), where the aim is to learn the grammatical rules and context dependent changes using a phrase reordering classification framework. We consider a variety of machine learning techniques, including state-of-the-art structured prediction methods. Techniques are compared and evaluated on a Chinese-English corpus, a language pair known for the high reordering characteristics which cannot be adequately captured with current models. In the reordering classification task, the method significantly outperforms the baseline against which it was tested, and further, when integrated as a component of the state-of-the-art machine translation system, MOSES, it achieves improvement in translation results.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {1–30},
numpages = {30}
}

@article{10.5555/1756006.1953047,
author = {Robinson, Joshua W. and Hartemink, Alexander J.},
title = {Learning Non-Stationary Dynamic Bayesian Networks},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Learning dynamic Bayesian network structures provides a principled mechanism for identifying conditional dependencies in time-series data. An important assumption of traditional DBN structure learning is that the data are generated by a stationary process, an assumption that is not true in many important settings. In this paper, we introduce a new class of graphical model called a non-stationary dynamic Bayesian network, in which the conditional dependence structure of the underlying data-generation process is permitted to change over time. Non-stationary dynamic Bayesian networks represent a new framework for studying problems in which the structure of a network is evolving over time. Some examples of evolving networks are transcriptional regulatory networks during an organism's development, neural pathways during learning, and traffic patterns during the day. We define the non-stationary DBN model, present an MCMC sampling algorithm for learning the structure of the model from time-series data under different assumptions, and demonstrate the effectiveness of the algorithm on both simulated and biological data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3647–3680},
numpages = {34}
}

@article{10.5555/1756006.1953046,
author = {Seldin, Yevgeny and Tishby, Naftali},
title = {PAC-Bayesian Analysis of Co-Clustering and Beyond},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We derive PAC-Bayesian generalization bounds for supervised and unsupervised learning models based on clustering, such as co-clustering, matrix tri-factorization, graphical models, graph clustering, and pairwise clustering. We begin with the analysis of co-clustering, which is a widely used approach to the analysis of data matrices. We distinguish among two tasks in matrix data analysis: discriminative prediction of the missing entries in data matrices and estimation of the joint probability distribution of row and column variables in co-occurrence matrices. We derive PAC-Bayesian generalization bounds for the expected out-of-sample performance of co-clustering-based solutions for these two tasks. The analysis yields regularization terms that were absent in the previous formulations of co-clustering. The bounds suggest that the expected performance of co-clustering is governed by a trade-off between its empirical performance and the mutual information preserved by the cluster variables on row and column IDs. We derive an iterative projection algorithm for finding a local optimum of this trade-off for discriminative prediction tasks. This algorithm achieved state-of-the-art performance in the MovieLens collaborative filtering task. Our co-clustering model can also be seen as matrix tri-factorization and the results provide generalization bounds, regularization terms, and new algorithms for this form of matrix factorization. The analysis of co-clustering is extended to tree-shaped graphical models, which can be used to analyze high dimensional tensors. According to the bounds, the generalization abilities of tree-shaped graphical models depend on a trade-off between their empirical data fit and the mutual information that is propagated up the tree levels. We also formulate weighted graph clustering as a prediction problem: given a subset of edge weights we analyze the ability of graph clustering to predict the remaining edge weights. The analysis of co-clustering easily extends to this problem and suggests that graph clustering should optimize the trade-off between empirical data fit and the mutual information that clusters preserve on graph nodes.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3595–3646},
numpages = {52}
}

@article{10.5555/1756006.1953045,
author = {Watanabe, Sumio},
title = {Asymptotic Equivalence of Bayes Cross Validation and Widely Applicable Information Criterion in Singular Learning Theory},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In regular statistical models, the leave-one-out cross-validation is asymptotically equivalent to the Akaike information criterion. However, since many learning machines are singular statistical models, the asymptotic behavior of the cross-validation remains unknown. In previous studies, we established the singular learning theory and proposed a widely applicable information criterion, the expectation value of which is asymptotically equal to the average Bayes generalization loss. In the present paper, we theoretically compare the Bayes cross-validation loss and the widely applicable information criterion and prove two theorems. First, the Bayes cross-validation loss is asymptotically equivalent to the widely applicable information criterion as a random variable. Therefore, model selection and hyperparameter optimization using these two values are asymptotically equivalent. Second, the sum of the Bayes generalization error and the Bayes cross-validation error is asymptotically equal to 2λ/n, where λ is the real log canonical threshold and n is the number of training samples. Therefore the relation between the cross-validation error and the generalization error is determined by the algebraic geometrical structure of a learning machine. We also clarify that the deviance information criteria are different from the Bayes cross-validation and the widely applicable information criterion.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3571–3594},
numpages = {24}
}

@article{10.5555/1756006.1953044,
author = {Henderson, James and Titov, Ivan},
title = {Incremental Sigmoid Belief Networks for Grammar Learning},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We propose a class of Bayesian networks appropriate for structured prediction problems where the Bayesian network's model structure is a function of the predicted output structure. These incremental sigmoid belief networks (ISBNs) make decoding possible because inference with partial output structures does not require summing over the unboundedly many compatible model structures, due to their directed edges and incrementally specified model structure. ISBNs are specifically targeted at challenging structured prediction problems such as natural language parsing, where learning the domain's complex statistical dependencies benefits from large numbers of latent variables. While exact inference in ISBNs with large numbers of latent variables is not tractable, we propose two efficient approximations. First, we demonstrate that a previous neural network parsing model can be viewed as a coarse mean-field approximation to inference with ISBNs. We then derive a more accurate but still tractable variational approximation, which proves effective in artificial experiments. We compare the effectiveness of these models on a benchmark natural language parsing task, where they achieve accuracy competitive with the state-of-the-art. The model which is a closer approximation to an ISBN has better parsing accuracy, suggesting that ISBNs are an appropriate abstract model of natural language grammar learning.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3541–3570},
numpages = {30}
}

@article{10.5555/1756006.1953043,
author = {Ye, Fei and Zhang, Cun-Hui},
title = {Rate Minimaxity of the Lasso and Dantzig Selector for the <i>l<sub>q</sub></i> Loss in <i>l<sub>r</sub></i> Balls},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We consider the estimation of regression coefficients in a high-dimensional linear model. For regression coefficients in lr balls, we provide lower bounds for the minimax lq risk and minimax quantiles of the lq loss for all design matrices. Under an l0 sparsity condition on a target coefficient vector, we sharpen and unify existing oracle inequalities for the Lasso and Dantzig selector. We derive oracle inequalities for target coefficient vectors with many small elements and smaller threshold levels than the universal threshold. These oracle inequalities provide sufficient conditions on the design matrix for the rate minimaxity of the Lasso and Dantzig selector for the lq risk and loss in lr balls, 0≤ r≤ 1≤ q≤ ∞. By allowing q=∞, our risk bounds imply the variable selection consistency of threshold Lasso and Dantzig selectors.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3519–3540},
numpages = {22}
}

@article{10.5555/1756006.1953042,
author = {Meil\u{a}, Marina and Bao, Le},
title = {An Exponential Model for Infinite Rankings},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {This paper presents a statistical model for expressing preferences through rankings, when the number of alternatives (items to rank) is large. A human ranker will then typically rank only the most preferred items, and may not even examine the whole set of items, or know how many they are. Similarly, a user presented with the ranked output of a search engine, will only consider the highest ranked items. We model such situations by introducing a stagewise ranking model that operates with finite ordered lists called top-t orderings over an infinite space of items. We give algorithms to estimate this model from data, and demonstrate that it has sufficient statistics, being thus an exponential family model with continuous and discrete parameters. We describe its conjugate prior and other statistical properties. Then, we extend the estimation problem to multimodal data by introducing an Exponential-Blurring-Mean-Shift nonparametric clustering algorithm. The experiments highlight the properties of our model and demonstrate that infinite models over permutations can be simple, elegant and practical.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3481–3518},
numpages = {38}
}

@article{10.5555/1756006.1953041,
author = {Bouckaert, Remco and Hemmecke, Raymond and Lindner, Silvia and Studen\'{y}, Milan},
title = {Efficient Algorithms for Conditional Independence Inference},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The topic of the paper is computer testing of (probabilistic) conditional independence (CI) implications by an algebraic method of structural imsets. The basic idea is to transform (sets of) CI statements into certain integral vectors and to verify by a computer the corresponding algebraic relation between the vectors, called the independence implication. We interpret the previous methods for computer testing of this implication from the point of view of polyhedral geometry. However, the main contribution of the paper is a new method, based on linear programming (LP). The new method overcomes the limitation of former methods to the number of involved variables. We recall/describe the theoretical basis for all four methods involved in our computational experiments, whose aim was to compare the efficiency of the algorithms. The experiments show that the LP method is clearly the fastest one. As an example of possible application of such algorithms we show that testing inclusion of Bayesian network structures or whether a CI statement is encoded in an acyclic directed graph can be done by the algebraic method.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3453–3479},
numpages = {27}
}

@article{10.5555/1756006.1953040,
author = {Sinz, Fabian and Bethge, Matthias},
title = {<i>L<sub>p</sub></i>-Nested Symmetric Distributions},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper, we introduce a new family of probability densities called Lp-nested symmetric distributions. The common property, shared by all members of the new class, is the same functional form ρ(x) = ~ρ(f(x)), where f is a nested cascade of Lp-norms ||x||p = (∑ |xi|p)1/p. Lp-nested symmetric distributions thereby are a special case of ν-spherical distributions for which f is only required to be positively homogeneous of degree one. While both, ν-spherical and Lp-nested symmetric distributions, contain many widely used families of probability models such as the Gaussian, spherically and elliptically symmetric distributions, Lp-spherically symmetric distributions, and certain types of independent component analysis (ICA) and independent subspace analysis (ISA) models, ν-spherical distributions are usually computationally intractable. Here we demonstrate that Lp-nested symmetric distributions are still computationally feasible by deriving an analytic expression for its normalization constant, gradients for maximum likelihood estimation, analytic expressions for certain types of marginals, as well as an exact and efficient sampling algorithm. We discuss the tight links of Lp-nested symmetric distributions to well known machine learning methods such as ICA, ISA and mixed norm regularizers, and introduce the nested radial factorization algorithm (NRF), which is a form of non-linear ICA that transforms any linearly mixed, non-factorial Lp-nested symmetric source into statistically independent signals. As a corollary, we also introduce the uniform distribution on the Lp-nested unit sphere.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3409–3451},
numpages = {43}
}

@article{10.5555/1756006.1953039,
author = {Vincent, Pascal and Larochelle, Hugo and Lajoie, Isabelle and Bengio, Yoshua and Manzagol, Pierre-Antoine},
title = {Stacked Denoising Autoencoders: Learning Useful Representations in a Deep Network with a Local Denoising Criterion},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We explore an original strategy for building deep networks, based on stacking layers of denoising autoencoders which are trained locally to denoise corrupted versions of their inputs. The resulting algorithm is a straightforward variation on the stacking of ordinary autoencoders. It is however shown on a benchmark of classification problems to yield significantly lower classification error, thus bridging the performance gap with deep belief networks (DBN), and in several cases surpassing it. Higher level representations learnt in this purely unsupervised fashion also help boost the performance of subsequent SVM classifiers. Qualitative experiments show that, contrary to ordinary autoencoders, denoising autoencoders are able to learn Gabor-like edge detectors from natural image patches and larger stroke detectors from digit images. This work clearly establishes the value of using a denoising criterion as a tractable unsupervised objective to guide the learning of useful higher level representations.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3371–3408},
numpages = {38}
}

@article{10.5555/1756006.1953038,
author = {Visweswaran, Shyam and Cooper, Gregory F.},
title = {Learning Instance-Specific Predictive Models},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {This paper introduces a Bayesian algorithm for constructing predictive models from data that are optimized to predict a target variable well for a particular instance. This algorithm learns Markov blanket models, carries out Bayesian model averaging over a set of models to predict a target variable of the instance at hand, and employs an instance-specific heuristic to locate a set of suitable models to average over. We call this method the instance-specific Markov blanket (ISMB) algorithm. The ISMB algorithm was evaluated on 21 UCI data sets using five different performance measures and its performance was compared to that of several commonly used predictive algorithms, including naive Bayes, C4.5 decision tree, logistic regression, neural networks, k-Nearest Neighbor, Lazy Bayesian Rules, and AdaBoost. Over all the data sets, the ISMB algorithm performed better on average on all performance measures against all the comparison algorithms.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3333–3369},
numpages = {37}
}

@article{10.5555/1756006.1953037,
author = {Dmochowski, Jacek P. and Sajda, Paul and Parra, Lucas C.},
title = {Maximum Likelihood in Cost-Sensitive Learning: Model Specification, Approximations, and Upper Bounds},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The presence of asymmetry in the misclassification costs or class prevalences is a common occurrence in the pattern classification domain. While much interest has been devoted to the study of cost-sensitive learning techniques, the relationship between cost-sensitive learning and the specification of the model set in a parametric estimation framework remains somewhat unclear. To that end, we differentiate between the case of the model including the true posterior, and that in which the model is misspecified. In the former case, it is shown that thresholding the maximum likelihood (ML) estimate is an asymptotically optimal solution to the risk minimization problem. On the other hand, under model misspecification, it is demonstrated that thresholded ML is suboptimal and that the risk-minimizing solution varies with the misclassification cost ratio. Moreover, we analytically show that the negative weighted log likelihood (Elkan, 2001) is a tight, convex upper bound of the empirical loss. Coupled with empirical results on several real-world data sets, we argue that weighted ML is the preferred cost-sensitive technique.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3313–3332},
numpages = {20}
}

@article{10.5555/1756006.1953036,
author = {Wang, Chunping and Liao, Xuejun and Carin, Lawrence and Dunson, David B.},
title = {Classification with Incomplete Data Using Dirichlet Process Priors},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A non-parametric hierarchical Bayesian framework is developed for designing a classifier, based on a mixture of simple (linear) classifiers. Each simple classifier is termed a local "expert", and the number of experts and their construction are manifested via a Dirichlet process formulation. The simple form of the "experts" allows analytical handling of incomplete data. The model is extended to allow simultaneous design of classifiers on multiple data sets, termed multi-task learning, with this also performed non-parametrically via the Dirichlet process. Fast inference is performed using variational Bayesian (VB) analysis, and example results are presented for several data sets. We also perform inference via Gibbs sampling, to which we compare the VB results.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3269–3311},
numpages = {43}
}

@article{10.5555/1756006.1953035,
author = {Honkela, Antti and Raiko, Tapani and Kuusela, Mikael and Tornio, Matti and Karhunen, Juha},
title = {Approximate Riemannian Conjugate Gradient Learning for Fixed-Form Variational Bayes},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Variational Bayesian (VB) methods are typically only applied to models in the conjugate-exponential family using the variational Bayesian expectation maximisation (VB EM) algorithm or one of its variants. In this paper we present an efficient algorithm for applying VB to more general models. The method is based on specifying the functional form of the approximation, such as multivariate Gaussian. The parameters of the approximation are optimised using a conjugate gradient algorithm that utilises the Riemannian geometry of the space of the approximations. This leads to a very efficient algorithm for suitably structured approximations. It is shown empirically that the proposed method is comparable or superior in efficiency to the VB EM in a case where both are applicable. We also apply the algorithm to learning a nonlinear state-space model and a nonlinear factor analysis model for which the VB EM is not applicable. For these models, the proposed algorithm outperforms alternative gradient-based methods by a significant margin.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3235–3268},
numpages = {34}
}

@article{10.5555/1756006.1953034,
author = {Yuan, Guo-Xun and Chang, Kai-Wei and Hsieh, Cho-Jui and Lin, Chih-Jen},
title = {A Comparison of Optimization Methods and Software for Large-Scale L1-Regularized Linear Classification},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Large-scale linear classification is widely used in many areas. The L1-regularized form can be applied for feature selection; however, its non-differentiability causes more difficulties in training. Although various optimization methods have been proposed in recent years, these have not yet been compared suitably. In this paper, we first broadly review existing methods. Then, we discuss state-of-the-art software packages in detail and propose two efficient implementations. Extensive comparisons indicate that carefully implemented coordinate descent methods are very suitable for training large document data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3183–3234},
numpages = {52}
}

@article{10.5555/1756006.1953033,
author = {Theodorou, Evangelos and Buchli, Jonas and Schaal, Stefan},
title = {A Generalized Path Integral Control Approach to Reinforcement Learning},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {With the goal to generate more scalable algorithms with higher efficiency and fewer open parameters, reinforcement learning (RL) has recently moved towards combining classical techniques from optimal control and dynamic programming with modern learning techniques from statistical estimation theory. In this vein, this paper suggests to use the framework of stochastic optimal control with path integrals to derive a novel approach to RL with parameterized policies. While solidly grounded in value function estimation and optimal control based on the stochastic Hamilton-Jacobi-Bellman (HJB) equations, policy improvements can be transformed into an approximation problem of a path integral which has no open algorithmic parameters other than the exploration noise. The resulting algorithm can be conceived of as model-based, semi-model-based, or even model free, depending on how the learning problem is structured. The update equations have no danger of numerical instabilities as neither matrix inversions nor gradient learning rates are required. Our new algorithm demonstrates interesting similarities with previous RL research in the framework of probability matching and provides intuition why the slightly heuristically motivated probability matching approach can actually perform well. Empirical evaluations demonstrate significant performance improvements over gradient-based policy learning and scalability to high-dimensional control problems. Finally, a learning experiment on a simulated 12 degree-of-freedom robot dog illustrates the functionality of our algorithm in a complex robot learning scenario. We believe that Policy Improvement with Path Integrals (PI2) offers currently one of the most efficient, numerically robust, and easy to implement algorithms for RL based on trajectory roll-outs.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3137–3181},
numpages = {45}
}

@article{10.5555/1756006.1953032,
author = {Gupta, Rahul and Sarawagi, Sunita and Diwan, Ajit A.},
title = {Collective Inference for Extraction MRFs Coupled with Symmetric Clique Potentials},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Many structured information extraction tasks employ collective graphical models that capture inter-instance associativity by coupling them with various clique potentials. We propose tractable families of such potentials that are invariant under permutations of their arguments, and call them symmetric clique potentials. We present three families of symmetric potentials---MAX, SUM, and MAJORITY. We propose cluster message passing for collective inference with symmetric clique potentials, and present message computation algorithms tailored to such potentials. Our first message computation algorithm, called α-pass, is sub-quadratic in the clique size, outputs exact messages for MAX, and computes 13/15-approximate messages for Potts, a popular member of the SUM family. Empirically, it is upto two orders of magnitude faster than existing algorithms based on graph-cuts or belief propagation. Our second algorithm, based on Lagrangian relaxation, operates on MAJORITY potentials and provides close to exact solutions while being two orders of magnitude faster. We show that the cluster message passing framework is more principled, accurate and converges faster than competing approaches. We extend our collective inference framework to exploit associativity of more general intra-domain properties of instance labelings, which opens up interesting applications in domain adaptation. Our approach leads to significant error reduction on unseen domains without incurring any overhead of model retraining.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3097–3135},
numpages = {39}
}

@article{10.5555/1756006.1953031,
author = {Cohn, Trevor and Blunsom, Phil and Goldwater, Sharon},
title = {Inducing Tree-Substitution Grammars},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Inducing a grammar from text has proven to be a notoriously challenging learning task despite decades of research. The primary reason for its difficulty is that in order to induce plausible grammars, the underlying model must be capable of representing the intricacies of language while also ensuring that it can be readily learned from data. The majority of existing work on grammar induction has favoured model simplicity (and thus learnability) over representational capacity by using context free grammars and first order dependency grammars, which are not sufficiently expressive to model many common linguistic constructions. We propose a novel compromise by inferring a probabilistic tree substitution grammar, a formalism which allows for arbitrarily large tree fragments and thereby better represent complex linguistic structures. To limit the model's complexity we employ a Bayesian non-parametric prior which biases the model towards a sparse grammar with shallow productions. We demonstrate the model's efficacy on supervised phrase-structure parsing, where we induce a latent segmentation of the training treebank, and on unsupervised dependency grammar induction. In both cases the model uncovers interesting latent linguistic structures while producing competitive results.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3053–3096},
numpages = {44}
}

@article{10.5555/1756006.1953030,
author = {Cohen, Shay B. and Smith, Noah A.},
title = {Covariance in Unsupervised Learning of Probabilistic Grammars},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Probabilistic grammars offer great flexibility in modeling discrete sequential data like natural language text. Their symbolic component is amenable to inspection by humans, while their probabilistic component helps resolve ambiguity. They also permit the use of well-understood, general-purpose learning algorithms. There has been an increased interest in using probabilistic grammars in the Bayesian setting. To date, most of the literature has focused on using a Dirichlet prior. The Dirichlet prior has several limitations, including that it cannot directly model covariance between the probabilistic grammar's parameters. Yet, various grammar parameters are expected to be correlated because the elements in language they represent share linguistic properties. In this paper, we suggest an alternative to the Dirichlet prior, a family of logistic normal distributions. We derive an inference algorithm for this family of distributions and experiment with the task of dependency grammar induction, demonstrating performance improvements with our priors on a set of six treebanks in different natural languages. Our covariance framework permits soft parameter tying within grammars and across grammars for text in different languages, and we show empirical gains in a novel learning setting using bilingual, non-parallel data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3017–3051},
numpages = {35}
}

@article{10.5555/1756006.1953029,
author = {Rasmussen, Carl Edward and Nickisch, Hannes},
title = {Gaussian Processes for Machine Learning (GPML) Toolbox},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The GPML toolbox provides a wide range of functionality for Gaussian process (GP) inference and prediction. GPs are specified by mean and covariance functions; we offer a library of simple mean and covariance functions and mechanisms to compose more complex ones. Several likelihood functions are supported including Gaussian and heavy-tailed for regression as well as others suitable for classification. Finally, a range of inference methods is provided, including exact and variational inference, Expectation Propagation, and Laplace's method dealing with non-Gaussian likelihoods and FITC for dealing with large regression tasks.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3011–3015},
numpages = {5}
}

@article{10.5555/1756006.1953028,
author = {Blanchard, Gilles and Lee, Gyemin and Scott, Clayton},
title = {Semi-Supervised Novelty Detection},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A common setting for novelty detection assumes that labeled examples from the nominal class are available, but that labeled examples of novelties are unavailable. The standard (inductive) approach is to declare novelties where the nominal density is low, which reduces the problem to density level set estimation. In this paper, we consider the setting where an unlabeled and possibly contaminated sample is also available at learning time. We argue that novelty detection in this semi-supervised setting is naturally solved by a general reduction to a binary classification problem. In particular, a detector with a desired false positive rate can be achieved through a reduction to Neyman-Pearson classification. Unlike the inductive approach, semi-supervised novelty detection (SSND) yields detectors that are optimal (e.g., statistically consistent) regardless of the distribution on novelties. Therefore, in novelty detection, unlabeled data have a substantial impact on the theoretical properties of the decision rule. We validate the practical utility of SSND with an extensive experimental study. We also show that SSND provides distribution-free, learning-theoretic solutions to two well known problems in hypothesis testing. First, our results provide a general solution to the general two-sample problem, that is, the problem of determining whether two random samples arise from the same distribution. Second, a specialization of SSND coincides with the standard p-value approach to multiple testing under the so-called random effects model. Unlike standard rejection regions based on thresholded p-values, the general SSND framework allows for adaptation to arbitrary alternative distributions in multiple dimensions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2973–3009},
numpages = {37}
}

@article{10.5555/1756006.1953027,
author = {Chang, Fu and Guo, Chien-Yang and Lin, Xiao-Rong and Lu, Chi-Jen},
title = {Tree Decomposition for Large-Scale SVM Problems},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {To handle problems created by large data sets, we propose a method that uses a decision tree to decompose a given data space and train SVMs on the decomposed regions. Although there are other means of decomposing a data space, we show that the decision tree has several merits for large-scale SVM training. First, it can classify some data points by its own means, thereby reducing the cost of SVM training for the remaining data points. Second, it is efficient in determining the parameter values that maximize the validation accuracy, which helps maintain good test accuracy. Third, the tree decomposition method can derive a generalization error bound for the classifier. For data sets whose size can be handled by current non-linear, or kernel-based, SVM training techniques, the proposed method can speed up the training by a factor of thousands, and still achieve comparable test accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2935–2972},
numpages = {38}
}

@article{10.5555/1756006.1953026,
author = {Cavallanti, Giovanni and Cesa-Bianchi, Nicol\`{o} and Gentile, Claudio},
title = {Linear Algorithms for Online Multitask Classification},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We introduce new Perceptron-based algorithms for the online multitask binary classification problem. Under suitable regularity conditions, our algorithms are shown to improve on their baselines by a factor proportional to the number of tasks. We achieve these improvements using various types of regularization that bias our algorithms towards specific notions of task relatedness. More specifically, similarity among tasks is either measured in terms of the geometric closeness of the task reference vectors or as a function of the dimension of their spanned subspace. In addition to adapting to the online setting a mix of known techniques, such as the multitask kernels of Evgeniou et al., our analysis also introduces a matrix-based multitask extension of the p-norm Perceptron, which is used to implement spectral co-regularization. Experiments on real-world data sets complement and support our theoretical findings.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2901–2934},
numpages = {34}
}

@article{10.5555/1756006.1953025,
author = {L\"{u}cke, J\"{o}rg and Eggert, Julian},
title = {Expectation Truncation and the Benefits of Preselection In Training Generative Models},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We show how a preselection of hidden variables can be used to efficiently train generative models with binary hidden variables. The approach is based on Expectation Maximization (EM) and uses an efficiently computable approximation to the sufficient statistics of a given model. The computational cost to compute the sufficient statistics is strongly reduced by selecting, for each data point, the relevant hidden causes. The approximation is applicable to a wide range of generative models and provides an interpretation of the benefits of preselection in terms of a variational EM approximation. To empirically show that the method maximizes the data likelihood, it is applied to different types of generative models including: a version of non-negative matrix factorization (NMF), a model for non-linear component extraction (MCA), and a linear generative model similar to sparse coding. The derived algorithms are applied to both artificial and realistic data, and are compared to other models in the literature. We find that the training scheme can reduce computational costs by orders of magnitude and allows for a reliable extraction of hidden causes.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2855–2900},
numpages = {46}
}

@article{10.5555/1756006.1953024,
author = {Vinh, Nguyen Xuan and Epps, Julien and Bailey, James},
title = {Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Information theoretic measures form a fundamental class of measures for comparing clusterings, and have recently received increasing interest. Nevertheless, a number of questions concerning their properties and inter-relationships remain unresolved. In this paper, we perform an organized study of information theoretic measures for clustering comparison, including several existing popular measures in the literature, as well as some newly proposed ones. We discuss and prove their important properties, such as the metric property and the normalization property. We then highlight to the clustering community the importance of correcting information theoretic measures for chance, especially when the data size is small compared to the number of clusters present therein. Of the available information theoretic based measures, we advocate the normalized information distance (NID) as a general measure of choice, for it possesses concurrently several important properties, such as being both a metric and a normalized measure, admitting an exact analytical adjusted-for-chance form, and using the nominal [0,1] range better than other normalized variants.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2837–2854},
numpages = {18}
}

@article{10.5555/1756006.1953023,
author = {Audibert, Jean-Yves and Bubeck, S\'{e}bastien},
title = {Regret Bounds and Minimax Policies under Partial Monitoring},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {This work deals with four classical prediction settings, namely full information, bandit, label efficient and bandit label efficient as well as four different notions of regret: pseudo-regret, expected regret, high probability regret and tracking the best expert regret. We introduce a new forecaster, INF (Implicitly Normalized Forecaster) based on an arbitrary function ψ for which we propose a unified analysis of its pseudo-regret in the four games we consider. In particular, for ψ(x)=exp(η x) + γ/K, INF reduces to the classical exponentially weighted average forecaster and our analysis of the pseudo-regret recovers known results while for the expected regret we slightly tighten the bounds. On the other hand with ψ(x)=(η/-x)q + γ/K, which defines a new forecaster, we are able to remove the extraneous logarithmic factor in the pseudo-regret bounds for bandits games, and thus fill in a long open gap in the characterization of the minimax rate for the pseudo-regret in the bandit game. We also provide high probability bounds depending on the cumulative reward of the optimal action. Finally, we consider the stochastic bandit game, and prove that an appropriate modification of the upper confidence bound policy UCB1 (Auer et al., 2002a) achieves the distribution-free optimal rate while still having a distribution-dependent rate logarithmic in the number of plays.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2785–2836},
numpages = {52}
}

@article{10.5555/1756006.1953022,
author = {Cohn, Ido and El-Hay, Tal and Friedman, Nir and Kupferman, Raz},
title = {Mean Field Variational Approximation for Continuous-Time Bayesian Networks},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Continuous-time Bayesian networks is a natural structured representation language for multi-component stochastic processes that evolve continuously over time. Despite the compact representation provided by this language, inference in such models is intractable even in relatively simple structured networks. We introduce a mean field variational approximation in which we use a product of inhomogeneous Markov processes to approximate a joint distribution over trajectories. This variational approach leads to a globally consistent distribution, which can be efficiently queried. Additionally, it provides a lower bound on the probability of observations, thus making it attractive for learning tasks. Here we describe the theoretical foundations for the approximation, an efficient implementation that exploits the wide range of highly optimized ordinary differential equations (ODE) solvers, experimentally explore characterizations of processes for which this approximation is suitable, and show applications to a large-scale real-world inference problem.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2745–2783},
numpages = {39}
}

@article{10.5555/1756006.1953021,
author = {Clark, Alexander and Eyraud, R\'{e}mi and Habrard, Amaury},
title = {Using Contextual Representations to Efficiently Learn Context-Free Languages},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We present a polynomial update time algorithm for the inductive inference of a large class of context-free languages using the paradigm of positive data and a membership oracle. We achieve this result by moving to a novel representation, called Contextual Binary Feature Grammars (CBFGs), which are capable of representing richly structured context-free languages as well as some context sensitive languages. These representations explicitly model the lattice structure of the distribution of a set of substrings and can be inferred using a generalisation of distributional learning. This formalism is an attempt to bridge the gap between simple learnable classes and the sorts of highly expressive representations necessary for linguistic representation: it allows the learnability of a large class of context-free languages, that includes all regular languages and those context-free languages that satisfy two simple constraints. The formalism and the algorithm seem well suited to natural language and in particular to the modeling of first language acquisition. Preliminary experimental results confirm the effectiveness of this approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2707–2744},
numpages = {38}
}

@article{10.5555/1756006.1953020,
author = {Songsiri, Jitkomut and Vandenberghe, Lieven},
title = {Topology Selection in Graphical Models of Autoregressive Processes},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {An algorithm is presented for topology selection in graphical models of autoregressive Gaussian time series. The graph topology of the model represents the sparsity pattern of the inverse spectrum of the time series and characterizes conditional independence relations between the variables. The method proposed in the paper is based on an l1-type nonsmooth regularization of the conditional maximum likelihood estimation problem. We show that this reduces to a convex optimization problem and describe a large-scale algorithm that solves the dual problem via the gradient projection method. Results of experiments with randomly generated and real data sets are also included.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2671–2705},
numpages = {35}
}

@article{10.5555/1756006.1953019,
author = {Shalev-Shwartz, Shai and Shamir, Ohad and Srebro, Nathan and Sridharan, Karthik},
title = {Learnability, Stability and Uniform Convergence},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The problem of characterizing learnability is the most basic question of statistical learning theory. A fundamental and long-standing answer, at least for the case of supervised classification and regression, is that learnability is equivalent to uniform convergence of the empirical risk to the population risk, and that if a problem is learnable, it is learnable via empirical risk minimization. In this paper, we consider the General Learning Setting (introduced by Vapnik), which includes most statistical learning problems as special cases. We show that in this setting, there are non-trivial learning problems where uniform convergence does not hold, empirical risk minimization fails, and yet they are learnable using alternative mechanisms. Instead of uniform convergence, we identify stability as the key necessary and sufficient condition for learnability. Moreover, we show that the conditions for learnability in the general setting are significantly more complex than in supervised classification and regression.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2635–2670},
numpages = {36}
}

@article{10.5555/1756006.1953018,
author = {Dillon, Joshua V. and Lebanon, Guy},
title = {Stochastic Composite Likelihood},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Maximum likelihood estimators are often of limited practical use due to the intensive computation they require. We propose a family of alternative estimators that maximize a stochastic variation of the composite likelihood function. Each of the estimators resolve the computation-accuracy tradeoff differently, and taken together they span a continuous spectrum of computation-accuracy tradeoff resolutions. We prove the consistency of the estimators, provide formulas for their asymptotic variance, statistical robustness, and computational complexity. We discuss experimental results in the context of Boltzmann machines and conditional random fields. The theoretical and experimental studies demonstrate the effectiveness of the estimators when the computational resources are insufficient. They also demonstrate that in some cases reduced computational complexity is associated with robustness thereby increasing statistical accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2597–2633},
numpages = {37}
}

@article{10.5555/1756006.1953017,
author = {Xiao, Lin},
title = {Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We consider regularized stochastic learning and online optimization problems, where the objective function is the sum of two convex terms: one is the loss function of the learning task, and the other is a simple regularization term such as l1-norm for promoting sparsity. We develop extensions of Nesterov's dual averaging method, that can exploit the regularization structure in an online setting. At each iteration of these methods, the learning variables are adjusted by solving a simple minimization problem that involves the running average of all past subgradients of the loss function and the whole regularization term, not just its subgradient. In the case of l1-regularization, our method is particularly effective in obtaining sparse solutions. We show that these methods achieve the optimal convergence rates or regret bounds that are standard in the literature on stochastic and online convex optimization. For stochastic learning problems in which the loss functions have Lipschitz continuous gradients, we also present an accelerated version of the dual averaging method.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2543–2596},
numpages = {54}
}

@article{10.5555/1756006.1953016,
author = {Bouckaert, Remco R. and Frank, Eibe and Hall, Mark A. and Holmes, Geoffrey and Pfahringer, Bernhard and Reutemann, Peter and Witten, Ian H.},
title = {WEKA---Experiences with a Java Open-Source Project},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {WEKA is a popular machine learning workbench with a development life of nearly two decades. This article provides an overview of the factors that we believe to be important to its success. Rather than focussing on the software's functionality, we review aspects of project management and historical development decisions that likely had an impact on the uptake of the project.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2533–2541},
numpages = {9}
}

@article{10.5555/1756006.1953015,
author = {Radovanovi\'{c}, Milo\v{s} and Nanopoulos, Alexandros and Ivanovi\'{c}, Mirjana},
title = {Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Different aspects of the curse of dimensionality are known to present serious challenges to various machine-learning methods and tasks. This paper explores a new aspect of the dimensionality curse, referred to as hubness, that affects the distribution of k-occurrences: the number of times a point appears among the k nearest neighbors of other points in a data set. Through theoretical and empirical analysis involving synthetic and real data sets we show that under commonly used assumptions this distribution becomes considerably skewed as dimensionality increases, causing the emergence of hubs, that is, points with very high k-occurrences which effectively represent "popular" nearest neighbors. We examine the origins of this phenomenon, showing that it is an inherent property of data distributions in high-dimensional vector space, discuss its interaction with dimensionality reduction, and explore its influence on a wide range of machine-learning tasks directly or indirectly based on measuring distances, belonging to supervised, semi-supervised, and unsupervised learning families.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2487–2531},
numpages = {45}
}

@article{10.5555/1756006.1953014,
author = {Koltchinskii, Vladimir},
title = {Rademacher Complexities and Bounding the Excess Risk in Active Learning},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Sequential algorithms of active learning based on the estimation of the level sets of the empirical risk are discussed in the paper. Localized Rademacher complexities are used in the algorithms to estimate the sample sizes needed to achieve the required accuracy of learning in an adaptive way. Probabilistic bounds on the number of active examples have been proved and several applications to binary classification problems are considered.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2457–2485},
numpages = {29}
}

@article{10.5555/1756006.1953013,
author = {Sun, Shiliang and Shawe-Taylor, John},
title = {Sparse Semi-Supervised Learning Using Conjugate Functions},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {In this paper, we propose a general framework for sparse semi-supervised learning, which concerns using a small portion of unlabeled data and a few labeled data to represent target functions and thus has the merit of accelerating function evaluations when predicting the output of a new example. This framework makes use of Fenchel-Legendre conjugates to rewrite a convex insensitive loss involving a regularization with unlabeled data, and is applicable to a family of semi-supervised learning methods such as multi-view co-regularized least squares and single-view Laplacian support vector machines (SVMs). As an instantiation of this framework, we propose sparse multi-view SVMs which use a squared ε-insensitive loss. The resultant optimization is an inf-sup problem and the optimal solutions have arguably saddle-point properties. We present a globally optimal iterative algorithm to optimize the problem. We give the margin bound on the generalization error of the sparse multi-view SVMs, and derive the empirical Rademacher complexity for the induced function class. Experiments on artificial and real-world data show their effectiveness. We further give a sequential training approach to show their possibility and potential for uses in large-scale problems and provide encouraging experimental results indicating the efficacy of the margin bound and empirical Rademacher complexity on characterizing the roles of unlabeled data for semi-supervised learning.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2423–2455},
numpages = {33}
}

@article{10.5555/1756006.1953012,
author = {Reid, Mark D. and Williamson, Robert C.},
title = {Composite Binary Losses},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We study losses for binary classification and class probability estimation and extend the understanding of them from margin losses to general composite losses which are the composition of a proper loss with a link function. We characterise when margin losses can be proper composite losses, explicitly show how to determine a symmetric loss in full from half of one of its partial losses, introduce an intrinsic parametrisation of composite binary losses and give a complete characterisation of the relationship between proper losses and "classification calibrated" losses. We also consider the question of the "best" surrogate binary loss. We introduce a precise notion of "best" and show there exist situations where two convex surrogate losses are incommensurable. We provide a complete explicit characterisation of the convexity of composite binary losses in terms of the link function and the weight function associated with the proper loss which make up the composite loss. This characterisation suggests new ways of "surrogate tuning" as well as providing an explicit characterisation of when Bregman divergences on the unit interval are convex in their second argument. Finally, in an appendix we present some new algorithm-independent results on the relationship between properness, convexity and robustness to misclassification noise for binary losses and show that all convex proper losses are non-robust to misclassification noise.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2387–2422},
numpages = {36}
}

@article{10.5555/1756006.1859933,
author = {Omidiran, Dapo and Wainwright, Martin J.},
title = {High-Dimensional Variable Selection with Sparse Random Projections: Measurement Sparsity and Statistical Efficiency},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We consider the problem of high-dimensional variable selection: given n noisy observations of a k-sparse vector β* ∈ Rp, estimate the subset of non-zero entries of β*. A significant body of work has studied behavior of l1-relaxations when applied to random measurement matrices that are dense (e.g., Gaussian, Bernoulli). In this paper, we analyze sparsified measurement ensembles, and consider the trade-off between measurement sparsity, as measured by the fraction γ of non-zero entries, and the statistical efficiency, as measured by the minimal number of observations n required for correct variable selection with probability converging to one. Our main result is to prove that it is possible to let the fraction on non-zero entries γ → 0 at some rate, yielding measurement matrices with a vanishing fraction of non-zeros per row, while retaining the same statistical efficiency as dense ensembles. A variety of simulation results confirm the sharpness of our theoretical predictions.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2361–2386},
numpages = {26}
}

@article{10.5555/1756006.1859932,
author = {Pernkopf, Franz and Bilmes, Jeff A.},
title = {Efficient Heuristics for Discriminative Structure Learning of Bayesian Network Classifiers},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We introduce a simple order-based greedy heuristic for learning discriminative structure within generative Bayesian network classifiers. We propose two methods for establishing an order of N features. They are based on the conditional mutual information and classification rate (i.e., risk), respectively. Given an ordering, we can find a discriminative structure with O(Nk+1) score evaluations (where constant k is the tree-width of the sub-graph over the attributes). We present results on 25 data sets from the UCI repository, for phonetic classification using the TIMIT database, for a visual surface inspection task, and for two handwritten digit recognition tasks. We provide classification performance for both discriminative and generative parameter learning on both discriminatively and generatively structured networks. The discriminative structure found by our new procedures significantly outperforms generatively produced structures, and achieves a classification accuracy on par with the best discriminative (greedy) Bayesian network learning approach, but does so with a factor of ~10-40 speedup. We also show that the advantages of generative discriminatively structured Bayesian network classifiers still hold in the case of missing features, a case where generative classifiers have an advantage over discriminative classifiers.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2323–2360},
numpages = {38}
}

@article{10.5555/1756006.1859931,
author = {Mazumder, Rahul and Hastie, Trevor and Tibshirani, Robert},
title = {Spectral Regularization Algorithms for Learning Large Incomplete Matrices},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We use convex relaxation techniques to provide a sequence of regularized low-rank solutions for large-scale matrix completion problems. Using the nuclear norm as a regularizer, we provide a simple and very efficient convex algorithm for minimizing the reconstruction error subject to a bound on the nuclear norm. Our algorithm SOFT-IMPUTE iteratively replaces the missing elements with those obtained from a soft-thresholded SVD. With warm starts this allows us to efficiently compute an entire regularization path of solutions on a grid of values of the regularization parameter. The computationally intensive part of our algorithm is in computing a low-rank SVD of a dense matrix. Exploiting the problem structure, we show that the task can be performed with a complexity of order linear in the matrix dimensions. Our semidefinite-programming algorithm is readily scalable to large matrices; for example SOFT-IMPUTE takes a few hours to compute low-rank approximations of a 106 X 106 incomplete matrix with 107 observed entries, and fits a rank-95 approximation to the full Netflix training set in 3.3 hours. Our methods achieve good training and test errors and exhibit superior timings when compared to other competitive state-of-the-art techniques.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2287–2322},
numpages = {36}
}

@article{10.5555/1756006.1859930,
author = {Yuan, Ming},
title = {High Dimensional Inverse Covariance Matrix Estimation via Linear Programming},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {This paper considers the problem of estimating a high dimensional inverse covariance matrix that can be well approximated by "sparse" matrices. Taking advantage of the connection between multivariate linear regression and entries of the inverse covariance matrix, we propose an estimating procedure that can effectively exploit such "sparsity". The proposed method can be computed using linear programming and therefore has the potential to be used in very high dimensional problems. Oracle inequalities are established for the estimation error in terms of several operator norms, showing that the method is adaptive to different types of sparsity of the problem.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2261–2286},
numpages = {26}
}

@article{10.5555/1756006.1859929,
author = {Raskutti, Garvesh and Wainwright, Martin J. and Yu, Bin},
title = {Restricted Eigenvalue Properties for Correlated Gaussian Designs},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Methods based on l1-relaxation, such as basis pursuit and the Lasso, are very popular for sparse regression in high dimensions. The conditions for success of these methods are now well-understood: (1) exact recovery in the noiseless setting is possible if and only if the design matrix X satisfies the restricted nullspace property, and (2) the squared l2-error of a Lasso estimate decays at the minimax optimal rate k log p / n, where k is the sparsity of the p-dimensional regression problem with additive Gaussian noise, whenever the design satisfies a restricted eigenvalue condition. The key issue is thus to determine when the design matrix X satisfies these desirable properties. Thus far, there have been numerous results showing that the restricted isometry property, which implies both the restricted nullspace and eigenvalue conditions, is satisfied when all entries of X are independent and identically distributed (i.i.d.), or the rows are unitary. This paper proves directly that the restricted nullspace and eigenvalue conditions hold with high probability for quite general classes of Gaussian matrices for which the predictors may be highly dependent, and hence restricted isometry conditions can be violated with high probability. In this way, our results extend the attractive theoretical guarantees on l1-relaxations to a much broader class of problems than the case of completely independent or unitary designs.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2241–2259},
numpages = {19}
}

@article{10.5555/1756006.1859928,
author = {Bordes, Antoine and Bottou, L\'{e}on and Gallinari, Patrick and Chang, Jonathan and Smith, S. Alex},
title = {Erratum: SGDQN is Less Careful than Expected},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The SGD-QN algorithm described in Bordes et al. (2009) contains a subtle flaw that prevents it from reaching its design goals. Yet the flawed SGD-QN algorithm has worked well enough to be a winner of the first Pascal Large Scale Learning Challenge (Sonnenburg et al., 2008). This document clarifies the situation, proposes a corrected algorithm, and evaluates its performance.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2229–2240},
numpages = {12}
}

@article{10.5555/1756006.1859927,
author = {Zhang, Zhihua and Dai, Guang and Xu, Congfu and Jordan, Michael I.},
title = {Regularized Discriminant Analysis, Ridge Regression and Beyond},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Fisher linear discriminant analysis (FDA) and its kernel extension--kernel discriminant analysis (KDA)--are well known methods that consider dimensionality reduction and classification jointly. While widely deployed in practical problems, there are still unresolved issues surrounding their efficient implementation and their relationship with least mean squares procedures. In this paper we address these issues within the framework of regularized estimation. Our approach leads to a flexible and efficient implementation of FDA as well as KDA. We also uncover a general relationship between regularized discriminant analysis and ridge regression. This relationship yields variations on conventional FDA based on the pseudoinverse and a direct equivalence to an ordinary least squares estimator.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2199–2228},
numpages = {30}
}

@article{10.5555/1756006.1859926,
author = {Wu, Qiang and Guinney, Justin and Maggioni, Mauro and Mukherjee, Sayan},
title = {Learning Gradients: Predictive Models That Infer Geometry and Statistical Dependence},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The problems of dimension reduction and inference of statistical dependence are addressed by the modeling framework of learning gradients. The models we propose hold for Euclidean spaces as well as the manifold setting. The central quantity in this approach is an estimate of the gradient of the regression or classification function. Two quadratic forms are constructed from gradient estimates: the gradient outer product and gradient based diffusion maps. The first quantity can be used for supervised dimension reduction on manifolds as well as inference of a graphical model encoding dependencies that are predictive of a response variable. The second quantity can be used for nonlinear projections that incorporate both the geometric structure of the manifold as well as variation of the response variable on the manifold. We relate the gradient outer product to standard statistical quantities such as covariances and provide a simple and precise comparison of a variety of supervised dimensionality reduction methods. We provide rates of convergence for both inference of informative directions as well as inference of a graphical model of variable dependencies.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2175–2198},
numpages = {24}
}

@article{10.5555/1756006.1859925,
author = {Mooij, Joris M.},
title = {LibDAI: A Free and Open Source C++ Library for Discrete Approximate Inference in Graphical Models},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {This paper describes the software package libDAI, a free & open source C++ library that provides implementations of various exact and approximate inference methods for graphical models with discrete-valued variables. libDAI supports directed graphical models (Bayesian networks) as well as undirected ones (Markov random fields and factor graphs). It offers various approximations of the partition sum, marginal probability distributions and maximum probability states. Parameter learning is also supported. A feature comparison with other open source software packages for approximate inference is given. libDAI is licensed under the GPL v2+ license and is available at http://www.libdai.org.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2169–2173},
numpages = {5}
}

@article{10.5555/1756006.1859924,
author = {Yu, Guoqiang and Feng, Yuanjian and Miller, David J. and Xuan, Jianhua and Hoffman, Eric P. and Clarke, Robert and Davidson, Ben and Shih, Ie-Ming and Wang, Yue},
title = {Matched Gene Selection and Committee Classifier for Molecular Classification of Heterogeneous Diseases},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Microarray gene expressions provide new opportunities for molecular classification of heterogeneous diseases. Although various reported classification schemes show impressive performance, most existing gene selection methods are suboptimal and are not well-matched to the unique characteristics of the multicategory classification problem. Matched design of the gene selection method and a committee classifier is needed for identifying a small set of gene markers that achieve accurate multicategory classification while being both statistically reproducible and biologically plausible. We report a simpler and yet more accurate strategy than previous works for multicategory classification of heterogeneous diseases. Our method selects the union of one-versus-everyone (OVE) phenotypic up-regulated genes (PUGs) and matches this gene selection with a one-versus-rest support vector machine (OVRSVM). Our approach provides even-handed gene resources for discriminating both neighboring and well-separated classes. Consistent with the OVRSVM structure, we evaluated the fold changes of OVE gene expressions and found that only a small number of high-ranked genes were required to achieve superior accuracy for multicategory classification. We tested the proposed PUG-OVRSVM method on six real microarray gene expression data sets (five public benchmarks and one in-house data set) and two simulation data sets, observing significantly improved performance with lower error rates, fewer marker genes, and higher performance sustainability, as compared to several widely-adopted gene selection and classification methods. The MATLAB toolbox, experiment data and supplement files are available at http://www.cbil.ece.vt.edu/software.htm.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2141–2167},
numpages = {27}
}

@article{10.5555/1756006.1859923,
author = {Fan, Yu and Xu, Jing and Shelton, Christian R.},
title = {Importance Sampling for Continuous Time Bayesian Networks},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A continuous time Bayesian network (CTBN) uses a structured representation to describe a dynamic system with a finite number of states which evolves in continuous time. Exact inference in a CTBN is often intractable as the state space of the dynamic system grows exponentially with the number of variables. In this paper, we first present an approximate inference algorithm based on importance sampling. We then extend it to continuous-time particle filtering and smoothing algorithms. These three algorithms can estimate the expectation of any function of a trajectory, conditioned on any evidence set constraining the values of subsets of the variables over subsets of the time line. We present experimental results on both synthetic networks and a network learned from a real data set on people's life history events. We show the accuracy as well as the time efficiency of our algorithms, and compare them to other approximate algorithms: expectation propagation and Gibbs sampling.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2115–2140},
numpages = {26}
}

@article{10.5555/1756006.1859922,
author = {Hothorn, Torsten and B\"{u}hlmann, Peter and Kneib, Thomas and Schmid, Matthias and Hofner, Benjamin},
title = {Model-Based Boosting 2.0},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We describe version 2.0 of the R add-on package mboost. The package implements boosting for optimizing general risk functions using component-wise (penalized) least squares estimates or regression trees as base-learners for fitting generalized linear, additive and interaction models to potentially high-dimensional data.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2109–2113},
numpages = {5}
}

@article{10.5555/1756006.1859921,
author = {Cawley, Gavin C. and Talbot, Nicola L.C.},
title = {On Over-Fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Model selection strategies for machine learning algorithms typically involve the numerical optimisation of an appropriate model selection criterion, often based on an estimator of generalisation performance, such as k-fold cross-validation. The error of such an estimator can be broken down into bias and variance components. While unbiasedness is often cited as a beneficial quality of a model selection criterion, we demonstrate that a low variance is at least as important, as a non-negligible variance introduces the potential for over-fitting in model selection as well as in training the model. While this observation is in hindsight perhaps rather obvious, the degradation in performance due to over-fitting the model selection criterion can be surprisingly large, an observation that appears to have received little attention in the machine learning literature to date. In this paper, we show that the effects of this form of over-fitting are often of comparable magnitude to differences in performance between learning algorithms, and thus cannot be ignored in empirical evaluation. Furthermore, we show that some common performance evaluation practices are susceptible to a form of selection bias as a result of this form of over-fitting and hence are unreliable. We discuss methods to avoid over-fitting in model selection and subsequent selection bias in performance evaluation, which we hope will be incorporated into best practice. While this study concentrates on cross-validation based model selection, the findings are quite general and apply to any model selection practice involving the optimisation of a model selection criterion evaluated over a finite sample of data, including maximisation of the Bayesian evidence and optimisation of performance bounds.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2079–2107},
numpages = {29}
}

@article{10.5555/1756006.1859920,
author = {Keshavan, Raghunandan H. and Montanari, Andrea and Oh, Sewoong},
title = {Matrix Completion from Noisy Entries},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the 'Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced by Keshavan, Montanari, and Oh (2010), based on a combination of spectral techniques and manifold optimization, that we call here OPTSPACE. We prove performance guarantees that are order-optimal in a number of circumstances.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2057–2078},
numpages = {22}
}

@article{10.5555/1756006.1859919,
author = {Gorissen, Dirk and Couckuyt, Ivo and Demeester, Piet and Dhaene, Tom and Crombecq, Karel},
title = {A Surrogate Modeling and Adaptive Sampling Toolbox for Computer Based Design},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {An exceedingly large number of scientific and engineering fields are confronted with the need for computer simulations to study complex, real world phenomena or solve challenging design problems. However, due to the computational cost of these high fidelity simulations, the use of neural networks, kernel methods, and other surrogate modeling techniques have become indispensable. Surrogate models are compact and cheap to evaluate, and have proven very useful for tasks such as optimization, design space exploration, prototyping, and sensitivity analysis. Consequently, in many fields there is great interest in tools and techniques that facilitate the construction of such regression models, while minimizing the computational cost and maximizing model accuracy. This paper presents a mature, flexible, and adaptive machine learning toolkit for regression modeling and active learning to tackle these issues. The toolkit brings together algorithms for data fitting, model selection, sample selection (active learning), hyperparameter optimization, and distributed computing in order to empower a domain expert to efficiently generate an accurate model for the problem or data at hand.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2051–2055},
numpages = {5}
}

@article{10.5555/1756006.1859918,
author = {Ganchev, Kuzman and Gra\c{c}a, Jo\~{a}o and Gillenwater, Jennifer and Taskar, Ben},
title = {Posterior Regularization for Structured Latent Variable Models},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We present posterior regularization, a probabilistic framework for structured, weakly supervised learning. Our framework efficiently incorporates indirect supervision via constraints on posterior distributions of probabilistic models with latent variables. Posterior regularization separates model complexity from the complexity of structural constraints it is desired to satisfy. By directly imposing decomposable regularization on the posterior moments of latent variables during learning, we retain the computational efficiency of the unconstrained model while ensuring desired constraints hold in expectation. We present an efficient algorithm for learning with posterior regularization and illustrate its versatility on a diverse set of structural constraints such as bijectivity, symmetry and group sparsity in several large scale experiments, including multi-view learning, cross-lingual dependency grammar induction, unsupervised part-of-speech induction, and bitext word alignment.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {2001–2049},
numpages = {49}
}

@article{10.5555/1756006.1859917,
author = {Ilin, Alexander and Raiko, Tapani},
title = {Practical Approaches to Principal Component Analysis in the Presence of Missing Values},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Principal component analysis (PCA) is a classical data analysis technique that finds linear transformations of data that retain the maximal amount of variance. We study a case where some of the data values are missing, and show that this problem has many features which are usually associated with nonlinear models, such as overfitting and bad locally optimal solutions. A probabilistic formulation of PCA provides a good foundation for handling missing values, and we provide formulas for doing that. In case of high dimensional and very sparse data, overfitting becomes a severe problem and traditional algorithms for PCA are very slow. We introduce a novel fast algorithm and extend it to variational Bayesian learning. Different versions of PCA are compared in artificial experiments, demonstrating the effects of regularization and modeling of posterior variance. The scalability of the proposed algorithm is demonstrated by applying it to the Netflix problem.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1957–2000},
numpages = {44}
}

@article{10.5555/1756006.1859916,
author = {Ralaivola, Liva and Szafranski, Marie and Stempfel, Guillaume},
title = {Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary β-Mixing Processes},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {PAC-Bayes bounds are among the most accurate generalization bounds for classifiers learned from independently and identically distributed (IID) data, and it is particularly so for margin classifiers: there have been recent contributions showing how practical these bounds can be either to perform model selection (Ambroladze et al., 2007) or even to directly guide the learning of linear classifiers (Germain et al., 2009). However, there are many practical situations where the training data show some dependencies and where the traditional IID assumption does not hold. Stating generalization bounds for such frameworks is therefore of the utmost interest, both from theoretical and practical standpoints. In this work, we propose the first--to the best of our knowledge--PAC-Bayes generalization bounds for classifiers trained on data exhibiting interdependencies. The approach undertaken to establish our results is based on the decomposition of a so-called dependency graph that encodes the dependencies within the data, in sets of independent data, thanks to graph fractional covers. Our bounds are very general, since being able to find an upper bound on the fractional chromatic number of the dependency graph is sufficient to get new PAC-Bayes bounds for specific settings. We show how our results can be used to derive bounds for ranking statistics (such as AUC) and classifiers trained on data distributed according to a stationary β-mixing process. In the way, we show how our approach seamlessly allows us to deal with U-processes. As a side note, we also provide a PAC-Bayes generalization bound for classifiers learned on data from stationary φ-mixing distributions.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1927–1956},
numpages = {30}
}

@article{10.5555/1756006.1859915,
author = {Segata, Nicola and Blanzieri, Enrico},
title = {Fast and Scalable Local Kernel Machines},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A computationally efficient approach to local learning with kernel methods is presented. The Fast Local Kernel Support Vector Machine (FaLK-SVM) trains a set of local SVMs on redundant neighbourhoods in the training set and an appropriate model for each query point is selected at testing time according to a proximity strategy. Supported by a recent result by Zakai and Ritov (2009) relating consistency and localizability, our approach achieves high classification accuracies by dividing the separation function in local optimisation problems that can be handled very efficiently from the computational viewpoint. The introduction of a fast local model selection further speeds-up the learning process. Learning and complexity bounds are derived for FaLK-SVM, and the empirical evaluation of the approach (with data sets up to 3 million points) showed that it is much faster and more accurate and scalable than state-of-the-art accurate and approximated SVM solvers at least for non high-dimensional data sets. More generally, we show that locality can be an important factor to sensibly speed-up learning approaches and kernel methods, differently from other recent techniques that tend to dismiss local information in order to improve scalability.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1883–1926},
numpages = {44}
}

@article{10.5555/1756006.1859914,
author = {L\'{a}zaro-Gredilla, Miguel and Qui\~{n}onero-Candela, Joaquin and Rasmussen, Carl Edward and Figueiras-Vidal, An\'{\i}bal R.},
title = {Sparse Spectrum Gaussian Process Regression},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We present a new sparse Gaussian Process (GP) model for regression. The key novel idea is to sparsify the spectral representation of the GP. This leads to a simple, practical algorithm for regression tasks. We compare the achievable trade-offs between predictive accuracy and computational requirements, and show that these are typically superior to existing state-of-the-art sparse approximations. We discuss both the weight space and function space representations, and note that the new construction implies priors over functions which are always stationary, and can approximate any covariance function in this class.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1865–1881},
numpages = {17}
}

@article{10.5555/1756006.1859913,
author = {Ojala, Markus and Garriga, Gemma C.},
title = {Permutation Tests for Studying Classifier Performance},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We explore the framework of permutation-based p-values for assessing the performance of classifiers. In this paper we study two simple permutation tests. The first test assess whether the classifier has found a real class structure in the data; the corresponding null distribution is estimated by permuting the labels in the data. This test has been used extensively in classification problems in computational biology. The second test studies whether the classifier is exploiting the dependency between the features in classification; the corresponding null distribution is estimated by permuting the features within classes, inspired by restricted randomization techniques traditionally used in statistics. This new test can serve to identify descriptive features which can be valuable information in improving the classifier performance. We study the properties of these tests and present an extensive empirical evaluation on real and synthetic data. Our analysis shows that studying the classifier performance via permutation tests is effective. In particular, the restricted permutation test clearly reveals whether the classifier exploits the interdependency between the features in the data.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1833–1863},
numpages = {31}
}

@article{10.5555/1756006.1859912,
author = {Baehrens, David and Schroeter, Timon and Harmeling, Stefan and Kawanabe, Motoaki and Hansen, Katja and M\"{u}ller, Klaus-Robert},
title = {How to Explain Individual Classification Decisions},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {After building a classifier with modern tools of machine learning we typically have a black box at hand that is able to predict well for unseen data. Thus, we get an answer to the question what is the most likely label of a given unseen data point. However, most methods will provide no answer why the model predicted a particular label for a single instance and what features were most influential for that particular instance. The only method that is currently able to provide such explanations are decision trees. This paper proposes a procedure which (based on a set of assumptions) allows to explain the decisions of any classification method.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1803–1831},
numpages = {29}
}

@article{10.5555/1756006.1859911,
author = {Sonnenburg, S\"{o}ren and R\"{a}tsch, Gunnar and Henschel, Sebastian and Widmer, Christian and Behr, Jonas and Zien, Alexander and Bona, Fabio de and Binder, Alexander and Gehl, Christian and Franc, Vojt\v{e}ch},
title = {The SHOGUN Machine Learning Toolbox},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We have developed a machine learning toolbox, called SHOGUN, which is designed for unified large-scale learning for a broad range of feature types and learning settings. It offers a considerable number of machine learning models such as support vector machines, hidden Markov models, multiple kernel learning, linear discriminant analysis, and more. Most of the specific algorithms are able to deal with several different data classes. We have used this toolbox in several applications from computational biology, some of them coming with no less than 50 million training examples and others with 7 billion test examples. With more than a thousand installations worldwide, SHOGUN is already widely adopted in the machine learning community and beyond.SHOGUN is implemented in C++ and interfaces to MATLABTM, R, Octave, Python, and has a stand-alone command line interface. The source code is freely available under the GNU General Public License, Version 3 at http://www.shogun-toolbox.org.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1799–1802},
numpages = {4}
}

@article{10.5555/1756006.1859910,
author = {Yoshida, Ryo and West, Mike},
title = {Bayesian Learning in Sparse Graphical Factor Models via Variational Mean-Field Annealing},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We describe a class of sparse latent factor models, called graphical factor models (GFMs), and relevant sparse learning algorithms for posterior mode estimation. Linear, Gaussian GFMs have sparse, orthogonal factor loadings matrices, that, in addition to sparsity of the implied covariance matrices, also induce conditional independence structures via zeros in the implied precision matrices. We describe the models and their use for robust estimation of sparse latent factor structure and data/signal reconstruction. We develop computational algorithms for model exploration and posterior mode search, addressing the hard combinatorial optimization involved in the search over a huge space of potential sparse configurations. A mean-field variational technique coupled with annealing is developed to successively generate "artificial" posterior distributions that, at the limiting temperature in the annealing schedule, define required posterior modes in the GFM parameter space. Several detailed empirical studies and comparisons to related approaches are discussed, including analyses of handwritten digit image and cancer gene expression data.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1771–1798},
numpages = {28}
}

@article{10.5555/1756006.1859909,
author = {Verbancsics, Phillip and Stanley, Kenneth O.},
title = {Evolving Static Representations for Task Transfer},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {An important goal for machine learning is to transfer knowledge between tasks. For example, learning to play RoboCup Keepaway should contribute to learning the full game of RoboCup soccer. Previous approaches to transfer in Keepaway have focused on transforming the original representation to fit the new task. In contrast, this paper explores the idea that transfer is most effective if the representation is designed to be the same even across different tasks. To demonstrate this point, a bird's eye view (BEV) representation is introduced that can represent different tasks on the same two-dimensional map. For example, both the 3 vs. 2 and 4 vs. 3 Keepaway tasks can be represented on the same BEV. Yet the problem is that a raw two-dimensional map is high-dimensional and unstructured. This paper shows how this problem is addressed naturally by an idea from evolutionary computation called indirect encoding, which compresses the representation by exploiting its geometry. The result is that the BEV learns a Keepaway policy that transfers without further learning or manipulation. It also facilitates transferring knowledge learned in a different domain, Knight Joust, into Keepaway. Finally, the indirect encoding of the BEV means that its geometry can be changed without altering the solution. Thus static representations facilitate several kinds of transfer.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1737–1769},
numpages = {33}
}

@article{10.5555/1756006.1859908,
author = {Jaimovich, Ariel and Meshi, Ofer and McGraw, Ian and Elidan, Gal},
title = {FastInf: An Efficient Approximate Inference Library},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The FastInf C++ library is designed to perform memory and time efficient approximate inference in large-scale discrete undirected graphical models. The focus of the library is propagation based approximate inference methods, ranging from the basic loopy belief propagation algorithm to propagation based on convex free energies. Various message scheduling schemes that improve on the standard synchronous or asynchronous approaches are included. Also implemented are a clique tree based exact inference, Gibbs sampling, and the mean field algorithm. In addition to inference, FastInf provides parameter estimation capabilities as well as representation and learning of shared parameters. It offers a rich interface that facilitates extension of the basic classes to other inference and learning methods.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1733–1736},
numpages = {4}
}

@article{10.5555/1756006.1859907,
author = {Hyv\"{a}rinen, Aapo and Zhang, Kun and Shimizu, Shohei and Hoyer, Patrik O.},
title = {Estimation of a Structural Vector Autoregression Model Using Non-Gaussianity},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Analysis of causal effects between continuous-valued variables typically uses either autoregressive models or structural equation models with instantaneous effects. Estimation of Gaussian, linear structural equation models poses serious identifiability problems, which is why it was recently proposed to use non-Gaussian models. Here, we show how to combine the non-Gaussian instantaneous model with autoregressive models. This is effectively what is called a structural vector autoregression (SVAR) model, and thus our work contributes to the long-standing problem of how to estimate SVAR's. We show that such a non-Gaussian model is identifiable without prior knowledge of network structure. We propose computationally efficient methods for estimating the model, as well as methods to assess the significance of the causal influences. The model is successfully applied on financial and brain imaging data.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1709–1731},
numpages = {23}
}

@article{10.5555/1756006.1859906,
author = {Forero, Pedro A. and Cano, Alfonso and Giannakis, Georgios B.},
title = {Consensus-Based Distributed Support Vector Machines},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {This paper develops algorithms to train support vector machines when training data are distributed across different nodes, and their communication to a centralized processing unit is prohibited due to, for example, communication complexity, scalability, or privacy reasons. To accomplish this goal, the centralized linear SVM problem is cast as a set of decentralized convex optimization sub-problems (one per node) with consensus constraints on the wanted classifier parameters. Using the alternating direction method of multipliers, fully distributed training algorithms are obtained without exchanging training data among nodes. Different from existing incremental approaches, the overhead associated with inter-node communications is fixed and solely dependent on the network topology rather than the size of the training sets available per node. Important generalizations to train nonlinear SVMs in a distributed fashion are also developed along with sequential variants capable of online processing. Simulated tests illustrate the performance of the novel algorithms.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1663–1707},
numpages = {45}
}

@article{10.5555/1756006.1859905,
author = {Spirtes, Peter},
title = {Introduction to Causal Inference},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {The goal of many sciences is to understand the mechanisms by which variables came to take on the values they have (that is, to find a generative model), and to predict what the values of those variables would be if the naturally occurring mechanisms were subject to outside manipulations. The past 30 years has seen a number of conceptual developments that are partial solutions to the problem of causal inference from observational sample data or a mixture of observational sample and experimental data, particularly in the area of graphical causal modeling. However, in many domains, problems such as the large numbers of variables, small samples sizes, and possible presence of unmeasured causes, remain serious impediments to practical applications of these developments. The articles in the Special Topic on Causality address these and other problems in applying graphical causal modeling algorithms. This introduction to the Special Topic on Causality provides a brief introduction to graphical causal modeling, places the articles in a broader context, and describes the differences between causal inference and ordinary machine learning classification and prediction problems.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1643–1662},
numpages = {20}
}

@article{10.5555/1756006.1859904,
author = {El-Yaniv, Ran and Wiener, Yair},
title = {On the Foundations of Noise-Free Selective Classification},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We consider selective classification, a term we adopt here to refer to 'classification with a reject option.' The essence in selective classification is to trade-off classifier coverage for higher accuracy. We term this trade-off the risk-coverage (RC) trade-off. Our main objective is to characterize this trade-off and to construct algorithms that can optimally or near optimally achieve the best possible trade-offs in a controlled manner. For noise-free models we present in this paper a thorough analysis of selective classification including characterizations of RC trade-offs in various interesting settings.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1605–1641},
numpages = {37}
}

@article{10.5555/1756006.1859903,
author = {Bifet, Albert and Holmes, Geoff and Kirkby, Richard and Pfahringer, Bernhard},
title = {MOA: Massive Online Analysis},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Massive Online Analysis (MOA) is a software environment for implementing algorithms and running experiments for online learning from evolving data streams. MOA includes a collection of offline and online methods as well as tools for evaluation. In particular, it implements boosting, bagging, and Hoeffding Trees, all with and without Na\"{\i}ve Bayes classifiers at the leaves. MOA supports bi-directional interaction with WEKA, the Waikato Environment for Knowledge Analysis, and is released under the GNU GPL license.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1601–1604},
numpages = {4}
}

@article{10.5555/1756006.1859902,
author = {Jaksch, Thomas and Ortner, Ronald and Auer, Peter},
title = {Near-Optimal Regret Bounds for Reinforcement Learning},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {For undiscounted reinforcement learning in Markov decision processes (MDPs) we consider the total regret of a learning algorithm with respect to an optimal policy. In order to describe the transition structure of an MDP we propose a new parameter: An MDP has diameter D if for any pair of states s,s' there is a policy which moves from s to s' in at most D steps (on average). We present a reinforcement learning algorithm with total regret \~{O}(DS√AT) after T steps for any unknown MDP with S states, A actions per state, and diameter D. A corresponding lower bound of Ω(√DSAT) on the total regret of any learning algorithm is given as well.These results are complemented by a sample complexity bound on the number of suboptimal steps taken by our algorithm. This bound can be used to achieve a (gap-dependent) regret bound that is logarithmic in T.Finally, we also consider a setting where the MDP is allowed to change a fixed number of l times. We present a modification of our algorithm that is able to deal with this setting and show a regret bound of \~{O}(l1/3T2/3DS√A).},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1563–1600},
numpages = {38}
}

@article{10.5555/1756006.1859901,
author = {Sriperumbudur, Bharath K. and Gretton, Arthur and Fukumizu, Kenji and Sch\"{o}lkopf, Bernhard and Lanckriet, Gert R.G.},
title = {Hilbert Space Embeddings and Metrics on Probability Measures},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {A Hilbert space embedding for probability measures has recently been proposed, with applications including dimensionality reduction, homogeneity testing, and independence testing. This embedding represents any probability measure as a mean element in a reproducing kernel Hilbert space (RKHS). A pseudometric on the space of probability measures can be defined as the distance between distribution embeddings: we denote this as γk, indexed by the kernel function k that defines the inner product in the RKHS.We present three theoretical properties of γk. First, we consider the question of determining the conditions on the kernel k for which γk is a metric: such k are denoted characteristic kernels. Unlike pseudometrics, a metric is zero only when two distributions coincide, thus ensuring the RKHS embedding maps all distributions uniquely (i.e., the embedding is injective). While previously published conditions may apply only in restricted circumstances (e.g., on compact domains), and are difficult to check, our conditions are straightforward and intuitive: integrally strictly positive definite kernels are characteristic. Alternatively, if a bounded continuous kernel is translation-invariant on ℜd, then it is characteristic if and only if the support of its Fourier transform is the entire ℜd. Second, we show that the distance between distributions under γk results from an interplay between the properties of the kernel and the distributions, by demonstrating that distributions are close in the embedding space when their differences occur at higher frequencies. Third, to understand the nature of the topology induced by γk, we relate γk to other popular metrics on probability measures, and present conditions on the kernel k under which γk metrizes the weak topology.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1517–1561},
numpages = {45}
}

@article{10.5555/1756006.1859900,
author = {Rodriguez-Lujan, Irene and Huerta, Ramon and Elkan, Charles and Cruz, Carlos Santa},
title = {Quadratic Programming Feature Selection},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Identifying a subset of features that preserves classification accuracy is a problem of growing importance, because of the increasing size and dimensionality of real-world data sets. We propose a new feature selection method, named Quadratic Programming Feature Selection (QPFS), that reduces the task to a quadratic optimization problem. In order to limit the computational complexity of solving the optimization problem, QPFS uses the Nystr\"{o}m method for approximate matrix diagonalization. QPFS is thus capable of dealing with very large data sets, for which the use of other methods is computationally expensive. In experiments with small and medium data sets, the QPFS method leads to classification accuracy similar to that of other successful techniques. For large data sets, QPFS is superior in terms of computational efficiency.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1491–1516},
numpages = {26}
}

@article{10.5555/1756006.1859899,
author = {Chang, Yin-Wen and Hsieh, Cho-Jui and Chang, Kai-Wei and Ringgaard, Michael and Lin, Chih-Jen},
title = {Training and Testing Low-Degree Polynomial Data Mappings via Linear SVM},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Kernel techniques have long been used in SVM to handle linearly inseparable problems by transforming data to a high dimensional space, but training and testing large data sets is often time consuming. In contrast, we can efficiently train and test much larger data sets using linear SVM without kernels. In this work, we apply fast linear-SVM methods to the explicit form of polynomially mapped data and investigate implementation issues. The approach enjoys fast training and testing, but may sometimes achieve accuracy close to that of using highly nonlinear kernels. Empirical experiments show that the proposed method is useful for certain large-scale data sets. We successfully apply the proposed method to a natural language processing (NLP) application by improving the testing accuracy under some training/testing speed requirements.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1471–1490},
numpages = {20}
}

@article{10.5555/1756006.1859898,
author = {Carlsson, Gunnar and M\'{e}moli, Facundo},
title = {Characterization, Stability and Convergence of Hierarchical Clustering Methods},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {We study hierarchical clustering schemes under an axiomatic view. We show that within this framework, one can prove a theorem analogous to one of Kleinberg (2002), in which one obtains an existence and uniqueness theorem instead of a non-existence result. We explore further properties of this unique scheme: stability and convergence are established. We represent dendrograms as ultrametric spaces and use tools from metric geometry, namely the Gromov-Hausdorff distance, to quantify the degree to which perturbations in the input metric space affect the result of hierarchical methods.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1425–1470},
numpages = {46}
}

@article{10.5555/1756006.1859897,
author = {Gretton, Arthur and Gy\"{o}rfi, L\'{a}szl\'{o}},
title = {Consistent Nonparametric Tests of Independence},
year = {2010},
issue_date = {3/1/2010},
publisher = {JMLR.org},
volume = {11},
issn = {1532-4435},
abstract = {Three simple and explicit procedures for testing the independence of two multi-dimensional random variables are described. Two of the associated test statistics (L1, log-likelihood) are defined when the empirical distribution of the variables is restricted to finite partitions. A third test statistic is defined as a kernel-based independence measure. Two kinds of tests are provided. Distribution-free strong consistent tests are derived on the basis of large deviation bounds on the test statistics: these tests make almost surely no Type I or Type II error after a random sample size. Asymptotically α-level tests are obtained from the limiting distribution of the test statistics. For the latter tests, the Type I error converges to a fixed non-zero value α, and the Type II error drops to zero, for increasing sample size. All tests reject the null hypothesis of independence if the test statistics become large. The performance of the tests is evaluated experimentally on benchmark data.},
journal = {J. Mach. Learn. Res.},
month = aug,
pages = {1391–1423},
numpages = {33}
}

@article{10.5555/1756006.1859896,
author = {Ghiasi-Shirazi, Kamaledin and Safabakhsh, Reza and Shamsi, Mostafa},
title = {Learning Translation Invariant Kernels for Classification},
year

license_type: permissive

branch_name: refs/heads/main

extension: bib