text:
high-dimensional data analysis. Fisher discriminant analysis (FDA) is a traditional technique for supervised dimensionality reduction, but it tends to give undesired results if samples in a class are multimodal. An unsupervised dimensionality reduction method called locality-preserving projection (LPP) can work well with multimodal data due to its locality preserving property. However, since LPP does not take the label information into account, it is not necessarily useful in supervised learning scenarios. In this paper, we propose a new linear supervised dimensionality reduction method called local Fisher discriminant analysis (LFDA), which effectively combines the ideas of FDA and LPP. LFDA has an analytic form of the embedding transformation and the solution can be easily computed just by solving a generalized eigenvalue problem. We demonstrate the practical usefulness and high scalability of the LFDA method in data visualization and classification tasks through extensive simulation studies. We also show that LFDA can be extended to non-linear dimensionality reduction scenarios by applying the kernel trick.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1027–1061},
numpages = {35}
}

@article{10.5555/1314498.1314532,
author = {Macskassy, Sofus A. and Provost, Foster},
title = {Classification in Networked Data: A Toolkit and a Univariate Case Study},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {This paper is about classifying entities that are interlinked with entities for which the class is known. After surveying prior work, we present NetKit, a modular toolkit for classification in networked data, and a case-study of its application to networked data used in prior machine learning research. NetKit is based on a node-centric framework in which classifiers comprise a local classifier, a relational classifier, and a collective inference procedure. Various existing node-centric relational learning algorithms can be instantiated with appropriate choices for these components, and new combinations of components realize new algorithms. The case study focuses on univariate network classification, for which the only information used is the structure of class linkage in the network (i.e., only links and some class labels). To our knowledge, no work previously has evaluated systematically the power of class-linkage alone for classification in machine learning benchmark data sets. The results demonstrate that very simple network-classification models perform quite well---well enough that they should be used regularly as baseline classifiers for studies of learning with networked data. The simplest method (which performs remarkably well) highlights the close correspondence between several existing methods introduced for different purposes---that is, Gaussian-field classifiers, Hopfield networks, and relational-neighbor classifiers. The case study also shows that there are two sets of techniques that are preferable in different situations, namely when few versus many labels are known initially. We also demonstrate that link selection plays an important role similar to traditional feature selection.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {935–983},
numpages = {49}
}

@article{10.5555/1314498.1314531,
author = {Esmeir, Saher and Markovitch, Shaul},
title = {Anytime Learning of Decision Trees},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The majority of existing algorithms for learning decision trees are greedy---a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Even the few non-greedy learners cannot learn good trees when the concept is difficult. Furthermore, they require a fixed amount of time and are not able to generate a better tree if additional time is available. We introduce a framework for anytime induction of decision trees that overcomes these problems by trading computation speed for better tree quality. Our proposed family of algorithms employs a novel strategy for evaluating candidate splits. A biased sampling of the space of consistent trees rooted at an attribute is used to estimate the size of the minimal tree under that attribute, and an attribute with the smallest expected tree is selected. We present two types of anytime induction algorithms: a contract algorithm that determines the sample size on the basis of a pre-given allocation of time, and an interruptible algorithm that starts with a greedy tree and continuously improves subtrees by additional sampling. Experimental results indicate that, for several hard concepts, our proposed approach exhibits good anytime behavior and yields significantly better decision trees when more time is available.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {891–933},
numpages = {43}
}

@article{10.5555/1314498.1314530,
author = {Audibert, Jean-Yves and Bousquet, Olivier},
title = {Combining PAC-Bayesian and Generic Chaining Bounds},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {There exist many different generalization error bounds in statistical learning theory. Each of these bounds contains an improvement over the others for certain situations or algorithms. Our goal is, first, to underline the links between these bounds, and second, to combine the different improvements into a single bound. In particular we combine the PAC-Bayes approach introduced by McAllester (1998), which is interesting for randomized predictions, with the optimal union bound provided by the generic chaining technique developed by Fernique and Talagrand (see Talagrand, 1996), in a way that also takes into account the variance of the combined functions. We also show how this connects to Rademacher based bounds.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {863–889},
numpages = {27}
}

@article{10.5555/1314498.1314529,
author = {Cawley, Gavin C. and Talbot, Nicola L. C.},
title = {Preventing Over-Fitting during Model Selection via Bayesian Regularisation of the Hyper-Parameters},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {While the model parameters of a kernel machine are typically given by the solution of a convex optimisation problem, with a single global optimum, the selection of good values for the regularisation and kernel parameters is much less straightforward. Fortunately the leave-one-out cross-validation procedure can be performed or a least approximated very efficiently in closed form for a wide variety of kernel learning methods, providing a convenient means for model selection. Leave-one-out cross-validation based estimates of performance, however, generally exhibit a relatively high variance and are therefore prone to over-fitting. In this paper, we investigate the novel use of Bayesian regularisation at the second level of inference, adding a regularisation term to the model selection criterion corresponding to a prior over the hyper-parameter values, where the additional regularisation parameters are integrated out analytically. Results obtained on a suite of thirteen real-world and synthetic benchmark data sets clearly demonstrate the benefit of this approach.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {841–861},
numpages = {21}
}

@article{10.5555/1314498.1314528,
author = {Chakrabartty, Shantanu and Cauwenberghs, Gert},
title = {<i>Gini</i> Support Vector Machine: Quadratic Entropy Based Robust Multi-Class Probability Regression},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Many classification tasks require estimation of output class probabilities for use as confidence scores or for inference integrated with other models. Probability estimates derived from large margin classifiers such as support vector machines (SVMs) are often unreliable. We extend SVM large margin classification to GiniSVM maximum entropy multi-class probability regression. GiniSVM combines a quadratic (Gini-Simpson) entropy based agnostic model with a kernel based similarity model. A form of Huber loss in the GiniSVM primal formulation elucidates a connection to robust estimation, further corroborated by the impulsive noise filtering property of the reverse water-filling procedure to arrive at normalized classification margins. The GiniSVM normalized classification margins directly provide estimates of class conditional probabilities, approximating kernel logistic regression (KLR) but at reduced computational cost. As with other SVMs, GiniSVM produces a sparse kernel expansion and is trained by solving a quadratic program under linear constraints. GiniSVM training is efficiently implemented by sequential minimum optimization or by growth transformation on probability functions. Results on synthetic and benchmark data, including speaker verification and face detection data, show improved classification performance and increased tolerance to imprecision over soft-margin SVM and KLR.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {813–839},
numpages = {27}
}

@article{10.5555/1314498.1314527,
author = {Melnik, Ofer and Vardi, Yehuda and Zhang, Cun-Hui},
title = {Concave Learners for Rankboost},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Rankboost has been shown to be an effective algorithm for combining ranks. However, its ability to generalize well and not overfit is directly related to the choice of weak learner, in the sense that regularization of the rank function is due to the regularization properties of its weak learners. We present a regularization property called consistency in preference and confidence that mathematically translates into monotonic concavity, and describe a new weak ranking learner (MWGR) that generates ranking functions with this property. In experiments combining ranks from multiple face recognition algorithms and an experiment combining text information retrieval systems, rank functions using MWGR proved superior to binary weak learners.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {791–812},
numpages = {22}
}

@article{10.5555/1314498.1314526,
author = {Bartlett, Peter L. and Tewari, Ambuj},
title = {Sparseness vs Estimating Conditional Probabilities: Some Asymptotic Results},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {One of the nice properties of kernel classifiers such as SVMs is that they often produce sparse solutions. However, the decision functions of these classifiers cannot always be used to estimate the conditional probability of the class label. We investigate the relationship between these two properties and show that these are intimately related: sparseness does not occur when the conditional probabilities can be unambiguously estimated. We consider a family of convex loss functions and derive sharp asymptotic results for the fraction of data that becomes support vectors. This enables us to characterize the exact trade-off between sparseness and the ability to estimate conditional probabilities for these loss functions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {775–790},
numpages = {16}
}

@article{10.5555/1314498.1314525,
author = {Owen, Art B.},
title = {Infinitely Imbalanced Logistic Regression},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In binary classification problems it is common for the two classes to be imbalanced: one case is very rare compared to the other. In this paper we consider the infinitely imbalanced case where one class has a finite sample size and the other class's sample size grows without bound. For logistic regression, the infinitely imbalanced case often has a useful solution. Under mild conditions, the intercept diverges as expected, but the rest of the coefficient vector approaches a non trivial and useful limit. That limit can be expressed in terms of exponential tilting and is the minimum of a convex objective function. The limiting form of logistic regression suggests a computational shortcut for fraud detection problems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {761–773},
numpages = {13}
}

@article{10.5555/1314498.1314524,
author = {Grauman, Kristen and Darrell, Trevor},
title = {The Pyramid Match Kernel: Efficient Learning with Sets of Features},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In numerous domains it is useful to represent a single example by the set of the local features or parts that comprise it. However, this representation poses a challenge to many conventional machine learning techniques, since sets may vary in cardinality and elements lack a meaningful ordering. Kernel methods can learn complex functions, but a kernel over unordered set inputs must somehow solve for correspondences---generally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function called the pyramid match that measures partial match similarity in time linear in the number of features. The pyramid match maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in order to find implicit correspondences based on the finest resolution histogram cell where a matched pair first appears. We show the pyramid match yields a Mercer kernel, and we prove bounds on its error relative to the optimal partial matching cost. We demonstrate our algorithm on both classification and regression tasks, including object recognition, 3-D human pose inference, and time of publication estimation for documents, and we show that the proposed method is accurate and significantly more efficient than current approaches.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {725–760},
numpages = {36}
}

@article{10.5555/1314498.1314523,
author = {Sutton, Charles and McCallum, Andrew and Rohanimanesh, Khashayar},
title = {Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In sequence modeling, we often wish to represent complex interaction between labels, such as when performing multiple, cascaded labeling tasks on the same sequence, or when long-range dependencies exist. We present dynamic conditional random fields (DCRFs), a generalization of linear-chain conditional random fields (CRFs) in which each time slice contains a set of state variables and edges---a distributed state representation as in dynamic Bayesian networks (DBNs)---and parameters are tied across slices. Since exact inference can be intractable in such models, we perform approximate inference using several schedules for belief propagation, including tree-based reparameterization (TRP). On a natural-language chunking task, we show that a DCRF performs better than a series of linear-chain CRFs, achieving comparable performance using only half the training data. In addition to maximum conditional likelihood, we present two alternative approaches for training DCRFs: marginal likelihood training, for when we are primarily interested in predicting only a subset of the variables, and cascaded training, for when we have a distinct data set for each state variable, as in transfer learning. We evaluate marginal training and cascaded training on both synthetic data and real-world text data, finding that marginal training can improve accuracy when uncertainty exists over the latent variables, and that for transfer learning, a DCRF trained in a cascaded fashion performs better than a linear-chain CRF that predicts the final task directly.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {693–723},
numpages = {31}
}

@article{10.5555/1314498.1314522,
author = {Neville, Jennifer and Jensen, David},
title = {Relational Dependency Networks},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Recent work on graphical models for relational data has demonstrated significant improvements in classification and inference when models represent the dependencies among instances. Despite its use in conventional statistical models, the assumption of instance independence is contradicted by most relational data sets. For example, in citation data there are dependencies among the topics of a paper's references, and in genomic data there are dependencies among the functions of interacting proteins. In this paper, we present relational dependency networks (RDNs), graphical models that are capable of expressing and reasoning with such dependencies in a relational setting. We discuss RDNs in the context of relational Bayes networks and relational Markov networks and outline the relative strengths of RDNs---namely, the ability to represent cyclic dependencies, simple methods for parameter estimation, and efficient structure learning techniques. The strengths of RDNs are due to the use of pseudolikelihood learning techniques, which estimate an efficient approximation of the full joint distribution. We present learned RDNs for a number of real-world data sets and evaluate the models in a prediction context, showing that RDNs identify and exploit cyclic relational dependencies to achieve significant performance gains over conventional conditional models. In addition, we use synthetic data to explore model performance under various relational data characteristics, showing that RDN learning and inference techniques are accurate over a wide range of conditions.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {653–692},
numpages = {40}
}

@article{10.5555/1314498.1314521,
author = {Tibshirani, Robert and Hastie, Trevor},
title = {Margin Trees for High-Dimensional Classification},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We propose a method for the classification of more than two classes, from high-dimensional features. Our approach is to build a binary decision tree in a top-down manner, using the optimal margin classifier at each split. We implement an exact greedy algorithm for this task, and compare its performance to less greedy procedures based on clustering of the matrix of pairwise margins. We compare the performance of the "margin tree" to the closely related "all-pairs" (one versus one) support vector machine, and nearest centroids on a number of cancer microarray data sets. We also develop a simple method for feature selection. We find that the margin tree has accuracy that is competitive with other methods and offers additional interpretability in its putative grouping of the classes.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {637–652},
numpages = {16}
}

@article{10.5555/1314498.1314520,
author = {Kalisch, Markus and B\"{u}hlmann, Peter},
title = {Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We consider the PC-algorithm (Spirtes et al., 2000) for estimating the skeleton and equivalence class of a very high-dimensional directed acyclic graph (DAG) with corresponding Gaussian distribution. The PC-algorithm is computationally feasible and often very fast for sparse problems with many nodes (variables), and it has the attractive property to automatically achieve high computational efficiency as a function of sparseness of the true underlying DAG. We prove uniform consistency of the algorithm for very high-dimensional, sparse DAGs where the number of nodes is allowed to quickly grow with sample size n, as fast as O(na) for any 0 < a < ∞. The sparseness assumption is rather minimal requiring only that the neighborhoods in the DAG are of lower order than sample size n. We also demonstrate the PC-algorithm for simulated data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {613–636},
numpages = {24}
}

@article{10.5555/1314498.1314519,
author = {Nilsson, Roland and Pe\~{n}a, Jos\'{e} M. and Bj\"{o}rkegren, Johan and Tegn\'{e}r, Jesper},
title = {Consistent Feature Selection for Pattern Recognition in Polynomial Time},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We analyze two different feature selection problems: finding a minimal feature set optimal for classification (MINIMAL-OPTIMAL) vs. finding all features relevant to the target variable (ALL-RELEVANT). The latter problem is motivated by recent applications within bioinformatics, particularly gene expression analysis. For both problems, we identify classes of data distributions for which there exist consistent, polynomial-time algorithms. We also prove that ALL-RELEVANT is much harder than MINIMAL-OPTIMAL and propose two consistent, polynomial-time algorithms. We argue that the distribution classes considered are reasonable in many practical cases, so that our results simplify feature selection in a wide range of machine learning tasks.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {589–612},
numpages = {24}
}

@article{10.5555/1314498.1314518,
author = {Arias, Marta and Khardon, Roni and Maloberti, J\'{e}r\^{o}me},
title = {Learning Horn Expressions with LOGAN-H},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The paper introduces LOGAN-H — a system for learning first-order function-free Horn expressions from interpretations. The system is based on an algorithm that learns by asking questions and that was proved correct in previous work. The current paper shows how the algorithm can be implemented in a practical system, and introduces a new algorithm based on it that avoids interaction and learns from examples only. The LOGAN-H system implements these algorithms and adds several facilities and optimizations that allow efficient applications in a wide range of problems. As one of the important ingredients, the system includes several fast procedures for solving the subsumption problem, an NP-complete problem that needs to be solved many times during the learning process. We describe qualitative and quantitative experiments in several domains. The experiments demonstrate that the system can deal with varied problems, large amounts of data, and that it achieves good classification accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {549–587},
numpages = {39}
}

@article{10.5555/1314498.1314517,
author = {Gadat, S\'{e}bastien and Younes, Laurent},
title = {A Stochastic Algorithm for Feature Selection in Pattern Recognition},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We introduce a new model addressing feature selection from a large dictionary of variables that can be computed from a signal or an image. Features are extracted according to an efficiency criterion, on the basis of specified classification or recognition tasks. This is done by estimating a probability distribution P on the complete dictionary, which distributes its mass over the more efficient, or informative, components. We implement a stochastic gradient descent algorithm, using the probability as a state variable and optimizing a multi-task goodness of fit criterion for classifiers based on variable randomly chosen according to P. We then generate classifiers from the optimal distribution of weights learned on the training set. The method is first tested on several pattern recognition problems including face detection, handwritten digit recognition, spam classification and micro-array analysis. We then compare our approach with other step-wise algorithms like random forests or recursive feature elimination.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {509–547},
numpages = {39}
}

@article{10.5555/1314498.1314516,
author = {Landwehr, Niels and Kersting, Kristian and Raedt, Luc De},
title = {Integrating Na\"{\i}ve Bayes and FOIL},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {A novel relational learning approach that tightly integrates the na\"{\i}ve Bayes learning scheme with the inductive logic programming rule-learner FOIL is presented. In contrast to previous combinations that have employed na\"{\i}ve Bayes only for post-processing the rule sets, the presented approach employs the na\"{\i}ve Bayes criterion to guide its search directly. The proposed technique is implemented in the <small>NFOIL and <small>TFOIL systems, which employ standard na\"{\i}ve Bayes and tree augmented na\"{\i}ve Bayes models respectively. We show that these integrated approaches to probabilistic model and rule learning outp erform post-processing approaches. They also yield significantly more accurate models than si mple rule learning and are competitive with more sophisticated ILP systems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {481–507},
numpages = {27}
}

@article{10.5555/1314498.1314515,
author = {Rifkin, Ryan M. and Lippert, Ross A.},
title = {Value Regularization and Fenchel Duality},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Regularization is an approach to function learning that balances fit and smoothness. In practice, we search for a function f with a finite representation f = Σi ci φi(·). In most treatments, the ci are the primary objects of study. We consider  value regularization, constructing optimization problems in which the predicted values at the training points are the primary variables, and therefore the central objects of study. Although this is a simple change, it has profound consequences. From convex conjugacy and the theory of Fenchel duality, we derive separate optimality conditions for the regularization and loss portions of the learning problem; this technique yields clean and short derivations of standard algorithms. This framework is ideally suited to studying many other phenomena at the intersection of learning theory and optimization. We obtain a value-based variant of the representer theorem, which underscores the transductive nature of regularization in reproducing kernel Hilbert spaces. We unify and extend previous results on learning kernel functions, with very simple proofs. We analyze the use of unregularized bias terms in optimization problems, and low-rank approximations to kernel matrices, obtaining new results in these areas. In summary, the combination of value regularization and Fenchel duality are valuable tools for studying the optimization problems in machine learning.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {441–479},
numpages = {39}
}

@article{10.5555/1314498.1314514,
author = {Mease, David and Wyner, Abraham J. and Buja, Andreas},
title = {Boosted Classification Trees and Class Probability/Quantile Estimation},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The standard by which binary classifiers are usually judged, misclassification error, assumes equal costs of misclassifying the two classes or, equivalently, classifying at the 1/2 quantile of the conditional class probability function P[y=1|x]. Boosted classification trees are known to perform quite well for such problems. In this article we consider the use of standard, off-the-shelf boosting for two more general problems: 1) classification with unequal costs or, equivalently, classification at quantiles other than 1/2, and 2) estimation of the conditional class probability function P[y=1|x]. We first examine whether the latter problem, estimation of P[y=1|x], can be solved with LogitBoost, and with AdaBoost when combined with a natural link function. The answer is negative: both approaches are often ineffective because they overfit P[y=1|x] even though they perform well as classifiers. A major negative point of the present article is the disconnect between class probability estimation and classification.Next we consider the practice of over/under-sampling of the two classes. We present an algorithm that uses AdaBoost in conjunction with Over/Under-Sampling and Jittering of the data "JOUS-Boost". This algorithm is simple, yet successful, and it preserves the advantage of relative protection against overfitting, but for arbitrary misclassification costs and, equivalently, arbitrary quantile boundaries. We then use collections of classifiers obtained from a grid of quantiles to form estimators of class probabilities. The estimates of the class probabilities compare favorably to those obtained by a variety of methods across both simulated and real data sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {409–439},
numpages = {31}
}

@article{10.5555/1314498.1314513,
author = {Reisert, Marco and Burkhardt, Hans},
title = {Learning Equivariant Functions with Matrix Valued Kernels},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {This paper presents a new class of matrix valued kernels that are ideally suited to learn vector valued equivariant functions. Matrix valued kernels are a natural generalization of the common notion of a kernel. We set the theoretical foundations of so called equivariant matrix valued kernels. We work out several properties of equivariant kernels, we give an interpretation of their behavior and show relations to scalar kernels. The notion of (ir)reducibility of group representations is transferred into the framework of matrix valued kernels. At the end to two exemplary applications are demonstrated. We design a non-linear rotation and translation equivariant filter for 2D-images and propose an invariant object detector based on the generalized Hough transform.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {385–408},
numpages = {24}
}

@article{10.5555/1314498.1314512,
author = {Fukumizu, Kenji and Bach, Francis R. and Gretton, Arthur},
title = {Statistical Consistency of Kernel Canonical Correlation Analysis},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {While kernel canonical correlation analysis (CCA) has been applied in many contexts, the convergence of finite sample estimates of the associated functions to their population counterparts has not yet been established. This paper gives a mathematical proof of the statistical convergence of kernel CCA, providing a theoretical justification for the method. The proof uses covariance operators defined on reproducing kernel Hilbert spaces, and analyzes the convergence of their empirical estimates of finite rank to their population counterparts, which can have infinite rank. The result also gives a sufficient condition for convergence on the regularization coefficient involved in kernel CCA: this should decrease as n-1/3, where n is the number of data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {361–383},
numpages = {23}
}

@article{10.5555/1314498.1314511,
author = {Biehl, Michael and Ghosh, Anarta and Hammer, Barbara},
title = {Dynamics and Generalization Ability of LVQ Algorithms},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Learning vector quantization (LVQ) schemes constitute intuitive, powerful classification heuristics with numerous successful applications but, so far, limited theoretical background. We study LVQ rigorously within a simplifying model situation: two competing prototypes are trained from a sequence of examples drawn from a mixture of Gaussians. Concepts from statistical physics and the theory of on-line learning allow for an exact description of the training dynamics in high-dimensional feature space. The analysis yields typical learning curves, convergence properties, and achievable generalization abilities. This is also possible for heuristic training schemes which do not relate to a cost function. We compare the performance of several algorithms, including Kohonen's LVQ1 and LVQ+/-, a limiting case of LVQ2.1. The former shows close to optimal performance, while LVQ+/- displays divergent behavior. We investigate how early stopping can overcome this difficulty. Furthermore, we study a crisp version of robust soft LVQ, which was recently derived from a statistical formulation. Surprisingly, it exhibits relatively poor generalization. Performance improves if a window for the selection of data is introduced; the resulting algorithm corresponds to cost function based LVQ2. The dependence of these results on the model parameters, for example, prior class probabilities, is investigated systematically, simulations confirm our analytical findings.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {323–360},
numpages = {38}
}

@article{10.5555/1314498.1314510,
author = {List, Nikolas and Simon, Hans Ulrich},
title = {General Polynomial Time Decomposition Algorithms},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We present a general decomposition algorithm that is uniformly applicable to every (suitably normalized) instance of Convex Quadratic Optimization and efficiently approaches an optimal solution. The number of iterations required to be within ε of optimality grows linearly with 1/ε and quadratically with the number m of variables. The working set selection can be performed in polynomial time. If we restrict our considerations to instances of Convex Quadratic Optimization with at most k0 equality constraints for some fixed constant k0 plus some so-called box-constraints (conditions that hold for most variants of SVM-optimization), the working set is found in linear time. Our analysis builds on a generalization of the concept of rate certifying pairs that was introduced by Hush and Scovel. In order to extend their results to arbitrary instances of Convex Quadratic Optimization, we introduce the general notion of a rate certifying q-set. We improve on the results by Hush and Scovel (2003) in several ways. First our result holds for Convex Quadratic Optimization whereas the results by Hush and Scovel are specialized to SVM-optimization. Second, we achieve a higher rate of convergence even for the special case of SVM-optimization (despite the generality of our approach). Third, our analysis is technically simpler.We prove furthermore that the strategy for working set selection which is based on rate certifying sets coincides with a strategy which is based on a so-called "sparse witness of sub-optimality". Viewed from this perspective, our main result improves on convergence results by List and Simon (2004) and Simon (2004) by providing convergence rates (and by holding under more general conditions).},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {303–321},
numpages = {19}
}

@article{10.5555/1314498.1314509,
author = {Loosli, Ga\"{e}lle and Canu, St\'{e}phane},
title = {Comments on the "Core Vector Machines: Fast SVM Training on Very Large Data Sets"},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In a recently published paper in JMLR, Tsang et al. (2005) present an algorithm for SVM called Core Vector Machines (CVM) and illustrate its performances through comparisons with other SVM solvers. After reading the CVM paper we were surprised by some of the reported results. In order to clarify the matter, we decided to reproduce some of the experiments. It turns out that to some extent, our results contradict those reported. Reasons of these different behaviors are given through the analysis of the stopping criterion.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {291–301},
numpages = {11}
}

@article{10.5555/1314498.1314508,
author = {Elbaz, Ariel and Lee, Homin K. and Servedio, Rocco A. and Wan, Andrew},
title = {Separating Models of Learning from Correlated and Uncorrelated Data},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible examples. A recent paper by Bshouty et al. (2003) shows that the class of polynomial-size DNF formulas is efficiently learnable in this random walk model; this result suggests that the Random Walk model is more powerful than comparable standard models of learning from independent examples, in which similarly efficient DNF learning algorithms are not known. We give strong evidence that the Random Walk model is indeed more powerful than the standard model, by showing that if any cryptographic one-way function exists (a universally held belief in cryptography), then there is a class of functions that can be learned efficiently in the Random Walk setting but not in the standard setting where all examples are independent.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {277–290},
numpages = {14}
}

@article{10.5555/1314498.1314507,
author = {Ying, Yiming and Zhou, Ding-Xuan},
title = {Learnability of Gaussians with Flexible Variances},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Gaussian kernels with flexible variances provide a rich family of Mercer kernels for learning algorithms. We show that the union of the unit balls of reproducing kernel Hilbert spaces generated by Gaussian kernels with flexible variances is a uniform Glivenko-Cantelli (uGC) class. This result confirms a conjecture concerning learnability of Gaussian kernels and verifies the uniform convergence of many learning algorithms involving Gaussians with changing variances. Rademacher averages and empirical covering numbers are used to estimate sample errors of multi-kernel regularization schemes associated with general loss functions. It is then shown that the regularization error associated with the least square loss and the Gaussian kernels can be greatly improved when flexible variances are allowed. Finally, for regularization schemes generated by Gaussian kernels with flexible variances we present explicit learning rates for regression with least square loss and classification with hinge loss.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {249–276},
numpages = {28}
}

@article{10.5555/1314498.1314506,
author = {Khardon, Roni and Wachman, Gabriel},
title = {Noise Tolerant Variants of the Perceptron Algorithm},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {A large number of variants of the Perceptron algorithm have been proposed and partially evaluated in recent work. One type of algorithm aims for noise tolerance by replacing the last hypothesis of the perceptron with another hypothesis or a vote among hypotheses. Another type simply adds a margin term to the perceptron in order to increase robustness and accuracy, as done in support vector machines. A third type borrows further from support vector machines and constrains the update function of the perceptron in ways that mimic soft-margin techniques. The performance of these algorithms, and the potential for combining different techniques, has not been studied in depth. This paper provides such an experimental study and reveals some interesting facts about the algorithms. In particular the perceptron with margin is an effective method for tolerating noise and stabilizing the algorithm. This is surprising since the margin in itself is not designed or used for noise tolerance, and there are no known guarantees for such performance. In most cases, similar performance is obtained by the voted-perceptron which has the advantage that it does not require parameter selection. Techniques using soft margin ideas are run-time intensive and do not give additional performance benefits. The results also highlight the difficulty with automatic parameter selection which is required with some of these variants.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {227–248},
numpages = {22}
}

@article{10.5555/1314498.1314505,
author = {Dasgupta, Sanjoy and Schulman, Leonard},
title = {A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We show that, given data from a mixture of k well-separated spherical Gaussians in ℜd, a simple two-round variant of EM will, with high probability, learn the parameters of the Gaussians to near-optimal precision, if the dimension is high (d >> ln k). We relate this to previous theoretical and empirical work on the EM algorithm.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {203–226},
numpages = {24}
}

@article{10.5555/1314498.1314504,
author = {Raiko, Tapani and Valpola, Harri and Harva, Markus and Karhunen, Juha},
title = {Building Blocks for Variational Bayesian Learning of Latent Variable Models},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We introduce standardised building blocks designed to be used with variational Bayesian learning. The blocks include Gaussian variables, summation, multiplication, nonlinearity, and delay. A large variety of latent variable models can be constructed from these blocks, including nonlinear and variance models, which are lacking from most existing variational systems. The introduced blocks are designed to fit together and to yield efficient update rules. Practical implementation of various models is easy thanks to an associated software package which derives the learning formulas automatically once a specific model structure has been fixed. Variational Bayesian learning provides a cost function which is used both for updating the variables of the model and for optimising the model structure. All the computations can be carried out locally, resulting in linear computational complexity. We present experimental results on several structures, including a new hierarchical nonlinear model for variances and means. The test results demonstrate the good performance and usefulness of the introduced method.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {155–201},
numpages = {47}
}

@article{10.5555/1314498.1314503,
author = {Tatti, Nikolaj},
title = {Distances between Data Sets Based on Summary Statistics},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The concepts of similarity and distance are crucial in data mining. We consider the problem of defining the distance between two data sets by comparing summary statistics computed from the data sets. The initial definition of our distance is based on geometrical notions of certain sets of distributions. We show that this distance can be computed in cubic time and that it has several intuitive properties. We also show that this distance is the unique Mahalanobis distance satisfying certain assumptions. We also demonstrate that if we are dealing with binary data sets, then the distance can be represented naturally by certain parity functions, and that it can be evaluated in linear time. Our empirical tests with real world data show that the distance works well.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {131–154},
numpages = {24}
}

@article{10.5555/1314498.1314502,
author = {Alaiz-Rodr\'{\i}guez, Roc\'{\i}o and Guerrero-Curieses, Alicia and Cid-Sueiro, Jes\'{u}s},
title = {Minimax Regret Classifier for Imprecise Class Distributions},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The design of a minimum risk classifier based on data usually stems from the stationarity assumption that the conditions during training and test are the same: the misclassification costs assumed during training must be in agreement with real costs, and the same statistical process must have generated both training and test data. Unfortunately, in real world applications, these assumptions may not hold. This paper deals with the problem of training a classifier when prior probabilities cannot be reliably induced from training data. Some strategies based on optimizing the worst possible case (conventional minimax) have been proposed previously in the literature, but they may achieve a robust classification at the expense of a severe performance degradation. In this paper we propose a minimax regret (minimax deviation) approach, that seeks to minimize the maximum deviation from the performance of the optimal risk classifier. A neural-based minimax regret classifier for general multi-class decision problems is presented. Experimental results show its robustness and the advantages in relation to other approaches.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {103–130},
numpages = {28}
}

@article{10.5555/1314498.1314501,
author = {Teboulle, Marc},
title = {A Unified Continuous Optimization Framework for Center-Based Clustering Methods},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Center-based partitioning clustering algorithms rely on minimizing an appropriately formulated objective function, and different formulations suggest different possible algorithms. In this paper, we start with the standard nonconvex and nonsmooth formulation of the partitioning clustering problem. We demonstrate that within this elementary formulation, convex analysis tools and optimization theory provide a unifying language and framework to design, analyze and extend hard and soft center-based clustering algorithms, through a generic algorithm which retains the computational simplicity of the popular k-means scheme. We show that several well known and more recent center-based clustering algorithms, which have been derived either heuristically, or/and have emerged from intuitive analogies in physics, statistical techniques and information theoretic perspectives can be recovered as special cases of the proposed analysis and we streamline their relationships.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {65–102},
numpages = {38}
}

@article{10.5555/1314498.1314500,
author = {Xue, Ya and Liao, Xuejun and Carin, Lawrence and Krishnapuram, Balaji},
title = {Multi-Task Learning for Classification with Dirichlet Process Priors},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Consider the problem of learning logistic-regression models for multiple classification tasks, where the training data set for each task is not drawn from the same statistical distribution. In such a multi-task learning (MTL) scenario, it is necessary to identify groups of similar tasks that should be learned jointly. Relying on a Dirichlet process (DP) based statistical model to learn the extent of similarity between classification tasks, we develop computationally efficient algorithms for two different forms of the MTL problem. First, we consider a symmetric multi-task learning (SMTL) situation in which classifiers for multiple tasks are learned jointly using a variational Bayesian (VB) algorithm. Second, we consider an asymmetric multi-task learning (AMTL) formulation in which the posterior density function from the SMTL model parameters (from previous tasks) is used as a prior for a new task: this approach has the significant advantage of not requiring storage and use of all previous data from prior tasks. The AMTL formulation is solved with a simple Markov Chain Monte Carlo (MCMC) construction. Experimental results on two real life MTL problems indicate that the proposed algorithms: (a) automatically identify subgroups of related tasks whose training data appear to be drawn from similar distributions; and (b) are more accurate than simpler approaches such as single-task learning, pooling of data across all tasks, and simplified approximations to DP.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {35–63},
numpages = {29}
}

@article{10.5555/1314498.1314499,
author = {Garc\'{\i}a-Pedrajas, Nicol\'{a}s and Garc\'{\i}a-Osorio, C\'{e}sar and Fyfe, Colin},
title = {Nonlinear Boosting Projections for Ensemble Construction},
year = {2007},
issue_date = {12/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = { In this paper we propose a novel approach for ensemble construction based on the use of nonlinear projections to achieve both accuracy and diversity of individual classifiers. The proposed approach combines the philosophy of boosting, putting more effort on difficult instances, with the basis of the random subspace method. Our main contribution is that instead of using a random subspace, we construct a projection taking into account the instances which have posed most difficulties to previous classifiers. In this way, consecutive nonlinear projections are created by a neural network trained using only incorrectly classified instances. The feature subspace induced by the hidden layer of this network is used as the input space to a new classifier. The method is compared with bagging and boosting techniques, showing an improved performance on a large set of 44 problems from the UCI Machine Learning Repository. An additional study showed that the proposed approach is less sensitive to noise in the data than boosting methods.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1–33},
numpages = {33}
}

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

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

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

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

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

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

@article{10.5555/1248659.1248694,
author = {Sugiyama, Masashi},
title = {Dimensionality Reduction of Multimodal Labeled Data by Local Fisher Discriminant Analysis},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Reducing the dimensionality of data without losing intrinsic information is an important preprocessing step in high-dimensional data analysis. Fisher discriminant analysis (FDA) is a traditional technique for supervised dimensionality reduction, but it tends to give undesired results if samples in a class are multimodal. An unsupervised dimensionality reduction method called locality-preserving projection (LPP) can work well with multimodal data due to its locality preserving property. However, since LPP does not take the label information into account, it is not necessarily useful in supervised learning scenarios. In this paper, we propose a new linear supervised dimensionality reduction method called local Fisher discriminant analysis (LFDA), which effectively combines the ideas of FDA and LPP. LFDA has an analytic form of the embedding transformation and the solution can be easily computed just by solving a generalized eigenvalue problem. We demonstrate the practical usefulness and high scalability of the LFDA method in data visualization and classification tasks through extensive simulation studies. We also show that LFDA can be extended to non-linear dimensionality reduction scenarios by applying the kernel trick.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1027–1061},
numpages = {35}
}

@article{10.5555/1248659.1248693,
author = {Macskassy, Sofus A. and Provost, Foster},
title = {Classification in Networked Data: A Toolkit and a Univariate Case Study},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {This paper is about classifying entities that are interlinked with entities for which the class is known. After surveying prior work, we present NetKit, a modular toolkit for classification in networked data, and a case-study of its application to networked data used in prior machine learning research. NetKit is based on a node-centric framework in which classifiers comprise a local classifier, a relational classifier, and a collective inference procedure. Various existing node-centric relational learning algorithms can be instantiated with appropriate choices for these components, and new combinations of components realize new algorithms. The case study focuses on univariate network classification, for which the only information used is the structure of class linkage in the network (i.e., only links and some class labels). To our knowledge, no work previously has evaluated systematically the power of class-linkage alone for classification in machine learning benchmark data sets. The results demonstrate that very simple network-classification models perform quite well---well enough that they should be used regularly as baseline classifiers for studies of learning with networked data. The simplest method (which performs remarkably well) highlights the close correspondence between several existing methods introduced for different purposes---that is, Gaussian-field classifiers, Hopfield networks, and relational-neighbor classifiers. The case study also shows that there are two sets of techniques that are preferable in different situations, namely when few versus many labels are known initially. We also demonstrate that link selection plays an important role similar to traditional feature selection.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {935–983},
numpages = {49}
}

@article{10.5555/1248659.1248692,
author = {Esmeir, Saher and Markovitch, Shaul},
title = {Anytime Learning of Decision Trees},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The majority of existing algorithms for learning decision trees are greedy---a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Even the few non-greedy learners cannot learn good trees when the concept is difficult. Furthermore, they require a fixed amount of time and are not able to generate a better tree if additional time is available. We introduce a framework for anytime induction of decision trees that overcomes these problems by trading computation speed for better tree quality. Our proposed family of algorithms employs a novel strategy for evaluating candidate splits. A biased sampling of the space of consistent trees rooted at an attribute is used to estimate the size of the minimal tree under that attribute, and an attribute with the smallest expected tree is selected. We present two types of anytime induction algorithms: a contract algorithm that determines the sample size on the basis of a pre-given allocation of time, and an interruptible algorithm that starts with a greedy tree and continuously improves subtrees by additional sampling. Experimental results indicate that, for several hard concepts, our proposed approach exhibits good anytime behavior and yields significantly better decision trees when more time is available.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {891–933},
numpages = {43}
}

@article{10.5555/1248659.1248691,
author = {Audibert, Jean-Yves and Bousquet, Olivier},
title = {Combining PAC-Bayesian and Generic Chaining Bounds},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {There exist many different generalization error bounds in statistical learning theory. Each of these bounds contains an improvement over the others for certain situations or algorithms. Our goal is, first, to underline the links between these bounds, and second, to combine the different improvements into a single bound. In particular we combine the PAC-Bayes approach introduced by McAllester (1998), which is interesting for randomized predictions, with the optimal union bound provided by the generic chaining technique developed by Fernique and Talagrand (see Talagrand, 1996), in a way that also takes into account the variance of the combined functions. We also show how this connects to Rademacher based bounds.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {863–889},
numpages = {27}
}

@article{10.5555/1248659.1248690,
author = {Cawley, Gavin C. and Talbot, Nicola L. C.},
title = {Preventing Over-Fitting during Model Selection via Bayesian Regularisation of the Hyper-Parameters},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {While the model parameters of a kernel machine are typically given by the solution of a convex optimisation problem, with a single global optimum, the selection of good values for the regularisation and kernel parameters is much less straightforward. Fortunately the leave-one-out cross-validation procedure can be performed or a least approximated very efficiently in closed form for a wide variety of kernel learning methods, providing a convenient means for model selection. Leave-one-out cross-validation based estimates of performance, however, generally exhibit a relatively high variance and are therefore prone to over-fitting. In this paper, we investigate the novel use of Bayesian regularisation at the second level of inference, adding a regularisation term to the model selection criterion corresponding to a prior over the hyper-parameter values, where the additional regularisation parameters are integrated out analytically. Results obtained on a suite of thirteen real-world and synthetic benchmark data sets clearly demonstrate the benefit of this approach.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {841–861},
numpages = {21}
}

@article{10.5555/1248659.1248689,
author = {Chakrabartty, Shantanu and Cauwenberghs, Gert},
title = {<i>Gini</i> Support Vector Machine: Quadratic Entropy Based Robust Multi-Class Probability Regression},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Many classification tasks require estimation of output class probabilities for use as confidence scores or for inference integrated with other models. Probability estimates derived from large margin classifiers such as support vector machines (SVMs) are often unreliable. We extend SVM large margin classification to GiniSVM maximum entropy multi-class probability regression. GiniSVM combines a quadratic (Gini-Simpson) entropy based agnostic model with a kernel based similarity model. A form of Huber loss in the GiniSVM primal formulation elucidates a connection to robust estimation, further corroborated by the impulsive noise filtering property of the reverse water-filling procedure to arrive at normalized classification margins. The GiniSVM normalized classification margins directly provide estimates of class conditional probabilities, approximating kernel logistic regression (KLR) but at reduced computational cost. As with other SVMs, GiniSVM produces a sparse kernel expansion and is trained by solving a quadratic program under linear constraints. GiniSVM training is efficiently implemented by sequential minimum optimization or by growth transformation on probability functions. Results on synthetic and benchmark data, including speaker verification and face detection data, show improved classification performance and increased tolerance to imprecision over soft-margin SVM and KLR.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {813–839},
numpages = {27}
}

@article{10.5555/1248659.1248688,
author = {Melnik, Ofer and Vardi, Yehuda and Zhang, Cun-Hui},
title = {Concave Learners for Rankboost},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Rankboost has been shown to be an effective algorithm for combining ranks. However, its ability to generalize well and not overfit is directly related to the choice of weak learner, in the sense that regularization of the rank function is due to the regularization properties of its weak learners. We present a regularization property called consistency in preference and confidence that mathematically translates into monotonic concavity, and describe a new weak ranking learner (MWGR) that generates ranking functions with this property. In experiments combining ranks from multiple face recognition algorithms and an experiment combining text information retrieval systems, rank functions using MWGR proved superior to binary weak learners.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {791–812},
numpages = {22}
}

@article{10.5555/1248659.1248687,
author = {Bartlett, Peter L. and Tewari, Ambuj},
title = {Sparseness vs Estimating Conditional Probabilities: Some Asymptotic Results},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {One of the nice properties of kernel classifiers such as SVMs is that they often produce sparse solutions. However, the decision functions of these classifiers cannot always be used to estimate the conditional probability of the class label. We investigate the relationship between these two properties and show that these are intimately related: sparseness does not occur when the conditional probabilities can be unambiguously estimated. We consider a family of convex loss functions and derive sharp asymptotic results for the fraction of data that becomes support vectors. This enables us to characterize the exact trade-off between sparseness and the ability to estimate conditional probabilities for these loss functions.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {775–790},
numpages = {16}
}

@article{10.5555/1248659.1248686,
author = {Owen, Art B.},
title = {Infinitely Imbalanced Logistic Regression},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In binary classification problems it is common for the two classes to be imbalanced: one case is very rare compared to the other. In this paper we consider the infinitely imbalanced case where one class has a finite sample size and the other class's sample size grows without bound. For logistic regression, the infinitely imbalanced case often has a useful solution. Under mild conditions, the intercept diverges as expected, but the rest of the coefficient vector approaches a non trivial and useful limit. That limit can be expressed in terms of exponential tilting and is the minimum of a convex objective function. The limiting form of logistic regression suggests a computational shortcut for fraud detection problems.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {761–773},
numpages = {13}
}

@article{10.5555/1248659.1248685,
author = {Grauman, Kristen and Darrell, Trevor},
title = {The Pyramid Match Kernel: Efficient Learning with Sets of Features},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In numerous domains it is useful to represent a single example by the set of the local features or parts that comprise it. However, this representation poses a challenge to many conventional machine learning techniques, since sets may vary in cardinality and elements lack a meaningful ordering. Kernel methods can learn complex functions, but a kernel over unordered set inputs must somehow solve for correspondences---generally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function called the pyramid match that measures partial match similarity in time linear in the number of features. The pyramid match maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in order to find implicit correspondences based on the finest resolution histogram cell where a matched pair first appears. We show the pyramid match yields a Mercer kernel, and we prove bounds on its error relative to the optimal partial matching cost. We demonstrate our algorithm on both classification and regression tasks, including object recognition, 3-D human pose inference, and time of publication estimation for documents, and we show that the proposed method is accurate and significantly more efficient than current approaches.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {725–760},
numpages = {36}
}

@article{10.5555/1248659.1248684,
author = {Sutton, Charles and McCallum, Andrew and Rohanimanesh, Khashayar},
title = {Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In sequence modeling, we often wish to represent complex interaction between labels, such as when performing multiple, cascaded labeling tasks on the same sequence, or when long-range dependencies exist. We present dynamic conditional random fields (DCRFs), a generalization of linear-chain conditional random fields (CRFs) in which each time slice contains a set of state variables and edges---a distributed state representation as in dynamic Bayesian networks (DBNs)---and parameters are tied across slices. Since exact inference can be intractable in such models, we perform approximate inference using several schedules for belief propagation, including tree-based reparameterization (TRP). On a natural-language chunking task, we show that a DCRF performs better than a series of linear-chain CRFs, achieving comparable performance using only half the training data. In addition to maximum conditional likelihood, we present two alternative approaches for training DCRFs: marginal likelihood training, for when we are primarily interested in predicting only a subset of the variables, and cascaded training, for when we have a distinct data set for each state variable, as in transfer learning. We evaluate marginal training and cascaded training on both synthetic data and real-world text data, finding that marginal training can improve accuracy when uncertainty exists over the latent variables, and that for transfer learning, a DCRF trained in a cascaded fashion performs better than a linear-chain CRF that predicts the final task directly.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {693–723},
numpages = {31}
}

@article{10.5555/1248659.1248683,
author = {Neville, Jennifer and Jensen, David},
title = {Relational Dependency Networks},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Recent work on graphical models for relational data has demonstrated significant improvements in classification and inference when models represent the dependencies among instances. Despite its use in conventional statistical models, the assumption of instance independence is contradicted by most relational data sets. For example, in citation data there are dependencies among the topics of a paper's references, and in genomic data there are dependencies among the functions of interacting proteins. In this paper, we present relational dependency networks (RDNs), graphical models that are capable of expressing and reasoning with such dependencies in a relational setting. We discuss RDNs in the context of relational Bayes networks and relational Markov networks and outline the relative strengths of RDNs---namely, the ability to represent cyclic dependencies, simple methods for parameter estimation, and efficient structure learning techniques. The strengths of RDNs are due to the use of pseudolikelihood learning techniques, which estimate an efficient approximation of the full joint distribution. We present learned RDNs for a number of real-world data sets and evaluate the models in a prediction context, showing that RDNs identify and exploit cyclic relational dependencies to achieve significant performance gains over conventional conditional models. In addition, we use synthetic data to explore model performance under various relational data characteristics, showing that RDN learning and inference techniques are accurate over a wide range of conditions.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {653–692},
numpages = {40}
}

@article{10.5555/1248659.1248682,
author = {Tibshirani, Robert and Hastie, Trevor},
title = {Margin Trees for High-Dimensional Classification},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We propose a method for the classification of more than two classes, from high-dimensional features. Our approach is to build a binary decision tree in a top-down manner, using the optimal margin classifier at each split. We implement an exact greedy algorithm for this task, and compare its performance to less greedy procedures based on clustering of the matrix of pairwise margins. We compare the performance of the "margin tree" to the closely related "all-pairs" (one versus one) support vector machine, and nearest centroids on a number of cancer microarray data sets. We also develop a simple method for feature selection. We find that the margin tree has accuracy that is competitive with other methods and offers additional interpretability in its putative grouping of the classes.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {637–652},
numpages = {16}
}

@article{10.5555/1248659.1248681,
author = {Kalisch, Markus and B\"{u}hlmann, Peter},
title = {Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We consider the PC-algorithm (Spirtes et al., 2000) for estimating the skeleton and equivalence class of a very high-dimensional directed acyclic graph (DAG) with corresponding Gaussian distribution. The PC-algorithm is computationally feasible and often very fast for sparse problems with many nodes (variables), and it has the attractive property to automatically achieve high computational efficiency as a function of sparseness of the true underlying DAG. We prove uniform consistency of the algorithm for very high-dimensional, sparse DAGs where the number of nodes is allowed to quickly grow with sample size n, as fast as O(na) for any 0 < a < ∞. The sparseness assumption is rather minimal requiring only that the neighborhoods in the DAG are of lower order than sample size n. We also demonstrate the PC-algorithm for simulated data.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {613–636},
numpages = {24}
}

@article{10.5555/1248659.1248680,
author = {Nilsson, Roland and Pe\~{n}a, Jos\'{e} M. and Bj\"{o}rkegren, Johan and Tegn\'{e}r, Jesper},
title = {Consistent Feature Selection for Pattern Recognition in Polynomial Time},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We analyze two different feature selection problems: finding a minimal feature set optimal for classification (MINIMAL-OPTIMAL) vs. finding all features relevant to the target variable (ALL-RELEVANT). The latter problem is motivated by recent applications within bioinformatics, particularly gene expression analysis. For both problems, we identify classes of data distributions for which there exist consistent, polynomial-time algorithms. We also prove that ALL-RELEVANT is much harder than MINIMAL-OPTIMAL and propose two consistent, polynomial-time algorithms. We argue that the distribution classes considered are reasonable in many practical cases, so that our results simplify feature selection in a wide range of machine learning tasks.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {589–612},
numpages = {24}
}

@article{10.5555/1248659.1248679,
author = {Arias, Marta and Khardon, Roni and Maloberti, J\'{e}r\^{o}me},
title = {Learning Horn Expressions with LOGAN-H},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The paper introduces LOGAN-H — a system for learning first-order function-free Horn expressions from interpretations. The system is based on an algorithm that learns by asking questions and that was proved correct in previous work. The current paper shows how the algorithm can be implemented in a practical system, and introduces a new algorithm based on it that avoids interaction and learns from examples only. The LOGAN-H system implements these algorithms and adds several facilities and optimizations that allow efficient applications in a wide range of problems. As one of the important ingredients, the system includes several fast procedures for solving the subsumption problem, an NP-complete problem that needs to be solved many times during the learning process. We describe qualitative and quantitative experiments in several domains. The experiments demonstrate that the system can deal with varied problems, large amounts of data, and that it achieves good classification accuracy.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {549–587},
numpages = {39}
}

@article{10.5555/1248659.1248678,
author = {Gadat, S\'{e}bastien and Younes, Laurent},
title = {A Stochastic Algorithm for Feature Selection in Pattern Recognition},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We introduce a new model addressing feature selection from a large dictionary of variables that can be computed from a signal or an image. Features are extracted according to an efficiency criterion, on the basis of specified classification or recognition tasks. This is done by estimating a probability distribution P on the complete dictionary, which distributes its mass over the more efficient, or informative, components. We implement a stochastic gradient descent algorithm, using the probability as a state variable and optimizing a multi-task goodness of fit criterion for classifiers based on variable randomly chosen according to P. We then generate classifiers from the optimal distribution of weights learned on the training set. The method is first tested on several pattern recognition problems including face detection, handwritten digit recognition, spam classification and micro-array analysis. We then compare our approach with other step-wise algorithms like random forests or recursive feature elimination.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {509–547},
numpages = {39}
}

@article{10.5555/1248659.1248677,
author = {Landwehr, Niels and Kersting, Kristian and Raedt, Luc De},
title = {Integrating Na\"{\i}ve Bayes and FOIL},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {A novel relational learning approach that tightly integrates the na\"{\i}ve Bayes learning scheme with the inductive logic programming rule-learner FOIL is presented. In contrast to previous combinations that have employed na\"{\i}ve Bayes only for post-processing the rule sets, the presented approach employs the na\"{\i}ve Bayes criterion to guide its search directly. The proposed technique is implemented in the NFOIL and TFOIL systems, which employ standard na\"{\i}ve Bayes and tree augmented na\"{\i}ve Bayes models respectively. We show that these integrated approaches to probabilistic model and rule learning outp erform post-processing approaches. They also yield significantly more accurate models than si mple rule learning and are competitive with more sophisticated ILP systems.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {481–507},
numpages = {27}
}

@article{10.5555/1248659.1248676,
author = {Rifkin, Ryan M. and Lippert, Ross A.},
title = {Value Regularization and Fenchel Duality},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Regularization is an approach to function learning that balances fit and smoothness. In practice, we search for a function f with a finite representation f = Σi ci φi(·). In most treatments, the ci are the primary objects of study. We consider  value regularization, constructing optimization problems in which the predicted values at the training points are the primary variables, and therefore the central objects of study. Although this is a simple change, it has profound consequences. From convex conjugacy and the theory of Fenchel duality, we derive separate optimality conditions for the regularization and loss portions of the learning problem; this technique yields clean and short derivations of standard algorithms. This framework is ideally suited to studying many other phenomena at the intersection of learning theory and optimization. We obtain a value-based variant of the representer theorem, which underscores the transductive nature of regularization in reproducing kernel Hilbert spaces. We unify and extend previous results on learning kernel functions, with very simple proofs. We analyze the use of unregularized bias terms in optimization problems, and low-rank approximations to kernel matrices, obtaining new results in these areas. In summary, the combination of value regularization and Fenchel duality are valuable tools for studying the optimization problems in machine learning.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {441–479},
numpages = {39}
}

@article{10.5555/1248659.1248675,
author = {Mease, David and Wyner, Abraham J. and Buja, Andreas},
title = {Boosted Classification Trees and Class Probability/Quantile Estimation},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The standard by which binary classifiers are usually judged, misclassification error, assumes equal costs of misclassifying the two classes or, equivalently, classifying at the 1/2 quantile of the conditional class probability function P[y=1|x]. Boosted classification trees are known to perform quite well for such problems. In this article we consider the use of standard, off-the-shelf boosting for two more general problems: 1) classification with unequal costs or, equivalently, classification at quantiles other than 1/2, and 2) estimation of the conditional class probability function P[y=1|x]. We first examine whether the latter problem, estimation of P[y=1|x], can be solved with LogitBoost, and with AdaBoost when combined with a natural link function. The answer is negative: both approaches are often ineffective because they overfit P[y=1|x] even though they perform well as classifiers. A major negative point of the present article is the disconnect between class probability estimation and classification.Next we consider the practice of over/under-sampling of the two classes. We present an algorithm that uses AdaBoost in conjunction with Over/Under-Sampling and Jittering of the data "JOUS-Boost". This algorithm is simple, yet successful, and it preserves the advantage of relative protection against overfitting, but for arbitrary misclassification costs and, equivalently, arbitrary quantile boundaries. We then use collections of classifiers obtained from a grid of quantiles to form estimators of class probabilities. The estimates of the class probabilities compare favorably to those obtained by a variety of methods across both simulated and real data sets.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {409–439},
numpages = {31}
}

@article{10.5555/1248659.1248674,
author = {Reisert, Marco and Burkhardt, Hans},
title = {Learning Equivariant Functions with Matrix Valued Kernels},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {This paper presents a new class of matrix valued kernels that are ideally suited to learn vector valued equivariant functions. Matrix valued kernels are a natural generalization of the common notion of a kernel. We set the theoretical foundations of so called equivariant matrix valued kernels. We work out several properties of equivariant kernels, we give an interpretation of their behavior and show relations to scalar kernels. The notion of (ir)reducibility of group representations is transferred into the framework of matrix valued kernels. At the end to two exemplary applications are demonstrated. We design a non-linear rotation and translation equivariant filter for 2D-images and propose an invariant object detector based on the generalized Hough transform.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {385–408},
numpages = {24}
}

@article{10.5555/1248659.1248673,
author = {Fukumizu, Kenji and Bach, Francis R. and Gretton, Arthur},
title = {Statistical Consistency of Kernel Canonical Correlation Analysis},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {While kernel canonical correlation analysis (CCA) has been applied in many contexts, the convergence of finite sample estimates of the associated functions to their population counterparts has not yet been established. This paper gives a mathematical proof of the statistical convergence of kernel CCA, providing a theoretical justification for the method. The proof uses covariance operators defined on reproducing kernel Hilbert spaces, and analyzes the convergence of their empirical estimates of finite rank to their population counterparts, which can have infinite rank. The result also gives a sufficient condition for convergence on the regularization coefficient involved in kernel CCA: this should decrease as n-1/3, where n is the number of data.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {361–383},
numpages = {23}
}

@article{10.5555/1248659.1248672,
author = {Biehl, Michael and Ghosh, Anarta and Hammer, Barbara},
title = {Dynamics and Generalization Ability of LVQ Algorithms},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Learning vector quantization (LVQ) schemes constitute intuitive, powerful classification heuristics with numerous successful applications but, so far, limited theoretical background. We study LVQ rigorously within a simplifying model situation: two competing prototypes are trained from a sequence of examples drawn from a mixture of Gaussians. Concepts from statistical physics and the theory of on-line learning allow for an exact description of the training dynamics in high-dimensional feature space. The analysis yields typical learning curves, convergence properties, and achievable generalization abilities. This is also possible for heuristic training schemes which do not relate to a cost function. We compare the performance of several algorithms, including Kohonen's LVQ1 and LVQ+/-, a limiting case of LVQ2.1. The former shows close to optimal performance, while LVQ+/- displays divergent behavior. We investigate how early stopping can overcome this difficulty. Furthermore, we study a crisp version of robust soft LVQ, which was recently derived from a statistical formulation. Surprisingly, it exhibits relatively poor generalization. Performance improves if a window for the selection of data is introduced; the resulting algorithm corresponds to cost function based LVQ2. The dependence of these results on the model parameters, for example, prior class probabilities, is investigated systematically, simulations confirm our analytical findings.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {323–360},
numpages = {38}
}

@article{10.5555/1248659.1248671,
author = {List, Nikolas and Simon, Hans Ulrich},
title = {General Polynomial Time Decomposition Algorithms},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We present a general decomposition algorithm that is uniformly applicable to every (suitably normalized) instance of Convex Quadratic Optimization and efficiently approaches an optimal solution. The number of iterations required to be within ε of optimality grows linearly with 1/ε and quadratically with the number m of variables. The working set selection can be performed in polynomial time. If we restrict our considerations to instances of Convex Quadratic Optimization with at most k0 equality constraints for some fixed constant k0 plus some so-called box-constraints (conditions that hold for most variants of SVM-optimization), the working set is found in linear time. Our analysis builds on a generalization of the concept of rate certifying pairs that was introduced by Hush and Scovel. In order to extend their results to arbitrary instances of Convex Quadratic Optimization, we introduce the general notion of a rate certifying q-set. We improve on the results by Hush and Scovel (2003) in several ways. First our result holds for Convex Quadratic Optimization whereas the results by Hush and Scovel are specialized to SVM-optimization. Second, we achieve a higher rate of convergence even for the special case of SVM-optimization (despite the generality of our approach). Third, our analysis is technically simpler.We prove furthermore that the strategy for working set selection which is based on rate certifying sets coincides with a strategy which is based on a so-called "sparse witness of sub-optimality". Viewed from this perspective, our main result improves on convergence results by List and Simon (2004) and Simon (2004) by providing convergence rates (and by holding under more general conditions).},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {303–321},
numpages = {19}
}

@article{10.5555/1248659.1248670,
author = {Loosli, Ga\"{e}lle and Canu, St\'{e}phane},
title = {Comments on the "Core Vector Machines: Fast SVM Training on Very Large Data Sets"},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In a recently published paper in JMLR, Tsang et al. (2005) present an algorithm for SVM called Core Vector Machines (CVM) and illustrate its performances through comparisons with other SVM solvers. After reading the CVM paper we were surprised by some of the reported results. In order to clarify the matter, we decided to reproduce some of the experiments. It turns out that to some extent, our results contradict those reported. Reasons of these different behaviors are given through the analysis of the stopping criterion.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {291–301},
numpages = {11}
}

@article{10.5555/1248659.1248669,
author = {Elbaz, Ariel and Lee, Homin K. and Servedio, Rocco A. and Wan, Andrew},
title = {Separating Models of Learning from Correlated and Uncorrelated Data},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible examples. A recent paper by Bshouty et al. (2003) shows that the class of polynomial-size DNF formulas is efficiently learnable in this random walk model; this result suggests that the Random Walk model is more powerful than comparable standard models of learning from independent examples, in which similarly efficient DNF learning algorithms are not known. We give strong evidence that the Random Walk model is indeed more powerful than the standard model, by showing that if any cryptographic one-way function exists (a universally held belief in cryptography), then there is a class of functions that can be learned efficiently in the Random Walk setting but not in the standard setting where all examples are independent.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {277–290},
numpages = {14}
}

@article{10.5555/1248659.1248668,
author = {Ying, Yiming and Zhou, Ding-Xuan},
title = {Learnability of Gaussians with Flexible Variances},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Gaussian kernels with flexible variances provide a rich family of Mercer kernels for learning algorithms. We show that the union of the unit balls of reproducing kernel Hilbert spaces generated by Gaussian kernels with flexible variances is a uniform Glivenko-Cantelli (uGC) class. This result confirms a conjecture concerning learnability of Gaussian kernels and verifies the uniform convergence of many learning algorithms involving Gaussians with changing variances. Rademacher averages and empirical covering numbers are used to estimate sample errors of multi-kernel regularization schemes associated with general loss functions. It is then shown that the regularization error associated with the least square loss and the Gaussian kernels can be greatly improved when flexible variances are allowed. Finally, for regularization schemes generated by Gaussian kernels with flexible variances we present explicit learning rates for regression with least square loss and classification with hinge loss.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {249–276},
numpages = {28}
}

@article{10.5555/1248659.1248667,
author = {Khardon, Roni and Wachman, Gabriel},
title = {Noise Tolerant Variants of the Perceptron Algorithm},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {A large number of variants of the Perceptron algorithm have been proposed and partially evaluated in recent work. One type of algorithm aims for noise tolerance by replacing the last hypothesis of the perceptron with another hypothesis or a vote among hypotheses. Another type simply adds a margin term to the perceptron in order to increase robustness and accuracy, as done in support vector machines. A third type borrows further from support vector machines and constrains the update function of the perceptron in ways that mimic soft-margin techniques. The performance of these algorithms, and the potential for combining different techniques, has not been studied in depth. This paper provides such an experimental study and reveals some interesting facts about the algorithms. In particular the perceptron with margin is an effective method for tolerating noise and stabilizing the algorithm. This is surprising since the margin in itself is not designed or used for noise tolerance, and there are no known guarantees for such performance. In most cases, similar performance is obtained by the voted-perceptron which has the advantage that it does not require parameter selection. Techniques using soft margin ideas are run-time intensive and do not give additional performance benefits. The results also highlight the difficulty with automatic parameter selection which is required with some of these variants.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {227–248},
numpages = {22}
}

@article{10.5555/1248659.1248666,
author = {Dasgupta, Sanjoy and Schulman, Leonard},
title = {A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We show that, given data from a mixture of k well-separated spherical Gaussians in ℜd, a simple two-round variant of EM will, with high probability, learn the parameters of the Gaussians to near-optimal precision, if the dimension is high (d >> ln k). We relate this to previous theoretical and empirical work on the EM algorithm.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {203–226},
numpages = {24}
}

@article{10.5555/1248659.1248665,
author = {Raiko, Tapani and Valpola, Harri and Harva, Markus and Karhunen, Juha},
title = {Building Blocks for Variational Bayesian Learning of Latent Variable Models},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {We introduce standardised building blocks designed to be used with variational Bayesian learning. The blocks include Gaussian variables, summation, multiplication, nonlinearity, and delay. A large variety of latent variable models can be constructed from these blocks, including nonlinear and variance models, which are lacking from most existing variational systems. The introduced blocks are designed to fit together and to yield efficient update rules. Practical implementation of various models is easy thanks to an associated software package which derives the learning formulas automatically once a specific model structure has been fixed. Variational Bayesian learning provides a cost function which is used both for updating the variables of the model and for optimising the model structure. All the computations can be carried out locally, resulting in linear computational complexity. We present experimental results on several structures, including a new hierarchical nonlinear model for variances and means. The test results demonstrate the good performance and usefulness of the introduced method.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {155–201},
numpages = {47}
}

@article{10.5555/1248659.1248664,
author = {Tatti, Nikolaj},
title = {Distances between Data Sets Based on Summary Statistics},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The concepts of similarity and distance are crucial in data mining. We consider the problem of defining the distance between two data sets by comparing summary statistics computed from the data sets. The initial definition of our distance is based on geometrical notions of certain sets of distributions. We show that this distance can be computed in cubic time and that it has several intuitive properties. We also show that this distance is the unique Mahalanobis distance satisfying certain assumptions. We also demonstrate that if we are dealing with binary data sets, then the distance can be represented naturally by certain parity functions, and that it can be evaluated in linear time. Our empirical tests with real world data show that the distance works well.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {131–154},
numpages = {24}
}

@article{10.5555/1248659.1248663,
author = {Alaiz-Rodr\'{\i}guez, Roc\'{\i}o and Guerrero-Curieses, Alicia and Cid-Sueiro, Jes\'{u}s},
title = {Minimax Regret Classifier for Imprecise Class Distributions},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {The design of a minimum risk classifier based on data usually stems from the stationarity assumption that the conditions during training and test are the same: the misclassification costs assumed during training must be in agreement with real costs, and the same statistical process must have generated both training and test data. Unfortunately, in real world applications, these assumptions may not hold. This paper deals with the problem of training a classifier when prior probabilities cannot be reliably induced from training data. Some strategies based on optimizing the worst possible case (conventional minimax) have been proposed previously in the literature, but they may achieve a robust classification at the expense of a severe performance degradation. In this paper we propose a minimax regret (minimax deviation) approach, that seeks to minimize the maximum deviation from the performance of the optimal risk classifier. A neural-based minimax regret classifier for general multi-class decision problems is presented. Experimental results show its robustness and the advantages in relation to other approaches.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {103–130},
numpages = {28}
}

@article{10.5555/1248659.1248662,
author = {Teboulle, Marc},
title = {A Unified Continuous Optimization Framework for Center-Based Clustering Methods},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Center-based partitioning clustering algorithms rely on minimizing an appropriately formulated objective function, and different formulations suggest different possible algorithms. In this paper, we start with the standard nonconvex and nonsmooth formulation of the partitioning clustering problem. We demonstrate that within this elementary formulation, convex analysis tools and optimization theory provide a unifying language and framework to design, analyze and extend hard and soft center-based clustering algorithms, through a generic algorithm which retains the computational simplicity of the popular k-means scheme. We show that several well known and more recent center-based clustering algorithms, which have been derived either heuristically, or/and have emerged from intuitive analogies in physics, statistical techniques and information theoretic perspectives can be recovered as special cases of the proposed analysis and we streamline their relationships.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {65–102},
numpages = {38}
}

@article{10.5555/1248659.1248661,
author = {Xue, Ya and Liao, Xuejun and Carin, Lawrence and Krishnapuram, Balaji},
title = {Multi-Task Learning for Classification with Dirichlet Process Priors},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {Consider the problem of learning logistic-regression models for multiple classification tasks, where the training data set for each task is not drawn from the same statistical distribution. In such a multi-task learning (MTL) scenario, it is necessary to identify groups of similar tasks that should be learned jointly. Relying on a Dirichlet process (DP) based statistical model to learn the extent of similarity between classification tasks, we develop computationally efficient algorithms for two different forms of the MTL problem. First, we consider a symmetric multi-task learning (SMTL) situation in which classifiers for multiple tasks are learned jointly using a variational Bayesian (VB) algorithm. Second, we consider an asymmetric multi-task learning (AMTL) formulation in which the posterior density function from the SMTL model parameters (from previous tasks) is used as a prior for a new task: this approach has the significant advantage of not requiring storage and use of all previous data from prior tasks. The AMTL formulation is solved with a simple Markov Chain Monte Carlo (MCMC) construction. Experimental results on two real life MTL problems indicate that the proposed algorithms: (a) automatically identify subgroups of related tasks whose training data appear to be drawn from similar distributions; and (b) are more accurate than simpler approaches such as single-task learning, pooling of data across all tasks, and simplified approximations to DP.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {35–63},
numpages = {29}
}

@article{10.5555/1248659.1248660,
author = {Garc\'{\i}a-Pedrajas, Nicol\'{a}s and Garc\'{\i}a-Osorio, C\'{e}sar and Fyfe, Colin},
title = {Nonlinear Boosting Projections for Ensemble Construction},
year = {2007},
issue_date = {5/1/2007},
publisher = {JMLR.org},
volume = {8},
issn = {1532-4435},
abstract = {In this paper we propose a novel approach for ensemble construction based on the use of nonlinear projections to achieve both accuracy and diversity of individual classifiers. The proposed approach combines the philosophy of boosting, putting more effort on difficult instances, with the basis of the random subspace method. Our main contribution is that instead of using a random subspace, we construct a projection taking into account the instances which have posed most difficulties to previous classifiers. In this way, consecutive nonlinear projections are created by a neural network trained using only incorrectly classified instances. The feature subspace induced by the hidden layer of this network is used as the input space to a new classifier. The method is compared with bagging and boosting techniques, showing an improved performance on a large set of 44 problems from the UCI Machine Learning Repository. An additional study showed that the proposed approach is less sensitive to noise in the data than boosting methods.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1–33},
numpages = {33}
}

@article{10.5555/1248547.1248647,
author = {Wright, Charles V. and Monrose, Fabian and Masson, Gerald M.},
title = {On Inferring Application Protocol Behaviors in Encrypted Network Traffic},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Several fundamental security mechanisms for restricting access to network resources rely on the ability of a reference monitor to inspect the contents of traffic as it traverses the network. However, with the increasing popularity of cryptographic protocols, the traditional means of inspecting packet contents to enforce security policies is no longer a viable approach as message contents are concealed by encryption. In this paper, we investigate the extent to which common application protocols can be identified using only the features that remain intact after encryption---namely packet size, timing, and direction. We first present what we believe to be the first exploratory look at protocol identification in encrypted tunnels which carry traffic from many TCP connections simultaneously, using only post-encryption observable features. We then explore the problem of protocol identification in individual encrypted TCP connections, using much less data than in other recent approaches. The results of our evaluation show that our classifiers achieve accuracy greater than 90% for several protocols in aggregate traffic, and, for most protocols, greater than 80% when making fine-grained classifications on single connections. Moreover, perhaps most surprisingly, we show that one can even estimate the number of live connections in certain classes of encrypted tunnels to within, on average, better than 20%.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2745–2769},
numpages = {25}
}

@article{10.5555/1248547.1248646,
author = {Kolter, J. Zico and Maloof, Marcus A.},
title = {Learning to Detect and Classify Malicious Executables in the Wild},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We describe the use of machine learning and data mining to detect and classify malicious executables as they appear in the wild. We gathered 1,971 benign and 1,651 malicious executables and encoded each as a training example using n-grams of byte codes as features. Such processing resulted in more than 255 million distinct n-grams. After selecting the most relevant n-grams for prediction, we evaluated a variety of inductive methods, including naive Bayes, decision trees, support vector machines, and boosting. Ultimately, boosted decision trees outperformed other methods with an area under the ROC curve of 0.996. Results suggest that our methodology will scale to larger collections of executables. We also evaluated how well the methods classified executables based on the function of their payload, such as opening a backdoor and mass-mailing. Areas under the ROC curve for detecting payload function were in the neighborhood of 0.9, which were smaller than those for the detection task. However, we attribute this drop in performance to fewer training examples and to the challenge of obtaining properly labeled examples, rather than to a failing of the methodology or to some inherent difficulty of the classification task. Finally, we applied detectors to 291 malicious executables discovered after we gathered our original collection, and boosted decision trees achieved a true-positive rate of 0.98 for a desired false-positive rate of 0.05. This result is particularly important, for it suggests that our methodology could be used as the basis for an operational system for detecting previously undiscovered malicious executables.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2721–2744},
numpages = {24}
}

@article{10.5555/1248547.1248645,
author = {Fumera, Giorgio and Pillai, Ignazio and Roli, Fabio},
title = {Spam Filtering Based On The Analysis Of Text Information Embedded Into Images},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In recent years anti-spam filters have become necessary tools for Internet service providers to face up to the continuously growing spam phenomenon. Current server-side anti-spam filters are made up of several modules aimed at detecting different features of spam e-mails. In particular, text categorisation techniques have been investigated by researchers for the design of modules for the analysis of the semantic content of e-mails, due to their potentially higher generalisation capability with respect to manually derived classification rules used in current server-side filters. However, very recently spammers introduced a new trick consisting of embedding the spam message into attached images, which can make all current techniques based on the analysis of digital text in the subject and body fields of e-mails ineffective. In this paper we propose an approach to anti-spam filtering which exploits the text information embedded into images sent as attachments. Our approach is based on the application of state-of-the-art text categorisation techniques to the analysis of text extracted by OCR tools from images attached to e-mails. The effectiveness of the proposed approach is experimentally evaluated on two large corpora of spam e-mails.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2699–2720},
numpages = {22}
}

@article{10.5555/1248547.1248644,
author = {Bratko, Andrej and Filipi\v{c}, Bogdan and Cormack, Gordon V. and Lynam, Thomas R. and Zupan, Bla\v{z}},
title = {Spam Filtering Using Statistical Data Compression Models},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Spam filtering poses a special problem in text categorization, of which the defining characteristic is that filters face an active adversary, which constantly attempts to evade filtering. Since spam evolves continuously and most practical applications are based on online user feedback, the task calls for fast, incremental and robust learning algorithms. In this paper, we investigate a novel approach to spam filtering based on adaptive statistical data compression models. The nature of these models allows them to be employed as probabilistic text classifiers based on character-level or binary sequences. By modeling messages as sequences, tokenization and other error-prone preprocessing steps are omitted altogether, resulting in a method that is very robust. The models are also fast to construct and incrementally updateable. We evaluate the filtering performance of two different compression algorithms; dynamic Markov compression and prediction by partial matching. The results of our empirical evaluation indicate that compression models outperform currently established spam filters, as well as a number of methods proposed in previous studies.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2673–2698},
numpages = {26}
}

@article{10.5555/1248547.1248643,
author = {Chan, Philip K. and Lippmann, Richard P.},
title = {Machine Learning for Computer Security},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The prevalent use of computers and internet has enhanced the quality of life for many people, but it has also attracted undesired attempts to undermine these systems. This special topic contains several research studies on how machine learning algorithms can help improve the security of computer systems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2669–2672},
numpages = {4}
}

@article{10.5555/1248547.1248642,
author = {Micchelli, Charles A. and Xu, Yuesheng and Zhang, Haizhang},
title = {Universal Kernels},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In this paper we investigate conditions on the features of a continuous kernel so that it may approximate an arbitrary continuous target function uniformly on any compact subset of the input space. A number of concrete examples are given of kernels with this universal approximating property.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2651–2667},
numpages = {17}
}

@article{10.5555/1248547.1248641,
author = {Castelo, Robert and Roverato, Alberto},
title = {A Robust Procedure For Gaussian Graphical Model Search From Microarray Data With <i>p</i> Larger Than <i>n</i>},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Learning of large-scale networks of interactions from microarray data is an important and challenging problem in bioinformatics. A widely used approach is to assume that the available data constitute a random sample from a multivariate distribution belonging to a Gaussian graphical model. As a consequence, the prime objects of inference are full-order partial correlations which are partial correlations between two variables given the remaining ones. In the context of microarray data the number of variables exceed the sample size and this precludes the application of traditional structure learning procedures because a sampling version of full-order partial correlations does not exist. In this paper we consider limited-order partial correlations, these are partial correlations computed on marginal distributions of manageable size, and provide a set of rules that allow one to assess the usefulness of these quantities to derive the independence structure of the underlying Gaussian graphical model. Furthermore, we introduce a novel structure learning procedure based on a quantity, obtained from limited-order partial correlations, that we call the non-rejection rate. The applicability and usefulness of the procedure are demonstrated by both simulated and real data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2621–2650},
numpages = {30}
}

@article{10.5555/1248547.1248640,
author = {Moser, Bernhard},
title = {On Representing and Generating Kernels by Fuzzy Equivalence Relations},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Kernels are two-placed functions that can be interpreted as inner products in some Hilbert space. It is this property which makes kernels predestinated to carry linear models of learning, optimization or classification strategies over to non-linear variants. Following this idea, various kernel-based methods like support vector machines or kernel principal component analysis have been conceived which prove to be successful for machine learning, data mining and computer vision applications. When applying a kernel-based method a central question is the choice and the design of the kernel function. This paper provides a novel view on kernels based on fuzzy-logical concepts which allows to incorporate prior knowledge in the design process. It is demonstrated that kernels mapping to the unit interval with constant one in its diagonal can be represented by a commonly used fuzzy-logical formula for representing fuzzy rule bases. This means that a great class of kernels can be represented by fuzzy-logical concepts. Apart from this result, which only guarantees the existence of such a representation, constructive examples are presented and the relation to unlabeled learning is pointed out.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2603–2620},
numpages = {18}
}

@article{10.5555/1248547.1248639,
author = {Olsson, Rasmus Kongsgaard and Hansen, Lars Kai},
title = {Linear State-Space Models for Blind Source Separation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We apply a type of generative modelling to the problem of blind source separation in which prior knowledge about the latent source signals, such as time-varying auto-correlation and quasi-periodicity, are incorporated into a linear state-space model. In simulations, we show that in terms of signal-to-error ratio, the sources are inferred more accurately as a result of the inclusion of strong prior knowledge. We explore different schemes of maximum-likelihood optimization for the purpose of learning the model parameters. The Expectation Maximization algorithm, which is often considered the standard optimization method in this context, results in slow convergence when the noise variance is small. In such scenarios, quasi-Newton optimization yields substantial improvements in a range of signal to noise ratios. We analyze the performance of the methods on convolutive mixtures of speech signals.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2585–2602},
numpages = {18}
}

@article{10.5555/1248547.1248638,
author = {Caponnetto, Andrea and Rakhlin, Alexander},
title = {Stability Properties of Empirical Risk Minimization over Donsker Classes},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We study some stability properties of algorithms which minimize (or almost-minimize) empirical error over Donsker classes of functions. We show that, as the number n of samples grows, the L2-diameter of the set of almost-minimizers of empirical error with tolerance ξ(n)=o(n-1/2) converges to zero in probability. Hence, even in the case of multiple minimizers of expected error, as n increases it becomes less and less likely that adding a sample (or a number of samples) to the training set will result in a large jump to a new hypothesis. Moreover, under some assumptions on the entropy of the class, along with an assumption of Komlos-Major-Tusnady type, we derive a power rate of decay for the diameter of almost-minimizers. This rate, through an application of a uniform ratio limit inequality, is shown to govern the closeness of the expected errors of the almost-minimizers. In fact, under the above assumptions, the expected errors of almost-minimizers become closer with a rate strictly faster than n-1/2.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2565–2583},
numpages = {19}
}

@article{10.5555/1248547.1248637,
author = {Zhao, Peng and Yu, Bin},
title = {On Model Selection Consistency of Lasso},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {Sparsity or parsimony of statistical models is crucial for their proper interpretations, as in sciences and social sciences. Model selection is a commonly used method to find such models, but usually involves a computationally heavy combinatorial search. Lasso (Tibshirani, 1996) is now being used as a computationally feasible alternative to model selection. Therefore it is important to study Lasso for model selection purposes.In this paper, we prove that a single condition, which we call the Irrepresentable Condition, is almost necessary and sufficient for Lasso to select the true model both in the classical fixed p setting and in the large p setting as the sample size n gets large. Based on these results, sufficient conditions that are verifiable in practice are given to relate to previous works and help applications of Lasso for feature selection and sparse representation.This Irrepresentable Condition, which depends mainly on the covariance of the predictor variables, states that Lasso selects the true model consistently if and (almost) only if the predictors that are not in the true model are "irrepresentable" (in a sense to be clarified) by predictors that are in the true model. Furthermore, simulations are carried out to provide insights and understanding of this result.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2541–2563},
numpages = {23}
}

@article{10.5555/1248547.1248636,
author = {Barber, David},
title = {Expectation Correction for Smoothed Inference in Switching Linear Dynamical Systems},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We introduce a method for approximate smoothed inference in a class of switching linear dynamical systems, based on a novel form of Gaussian Sum smoother. This class includes the switching Kalman 'Filter' and the more general case of switch transitions dependent on the continuous latent state. The method improves on the standard Kim smoothing approach by dispensing with one of the key approximations, thus making fuller use of the available future information.Whilst the central assumption required is projection to a mixture of Gaussians, we show that an additional conditional independence assumption results in a simpler but accurate alternative. Our method consists of a single Forward and Backward Pass and is reminiscent of the standard smoothing 'correction' recursions in the simpler linear dynamical system. The method is numerically stable and compares favourably against alternative approximations, both in cases where a single mixture component provides a good posterior approximation, and where a multimodal approximation is required.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2515–2540},
numpages = {26}
}

@article{10.5555/1248547.1248635,
author = {Mukherjee, Sayan and Wu, Qiang},
title = {Estimation of Gradients and Coordinate Covariation in Classification},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We introduce an algorithm that simultaneously estimates a classification function as well as its gradient in the supervised learning framework. The motivation for the algorithm is to find salient variables and estimate how they covary. An efficient implementation with respect to both memory and time is given. The utility of the algorithm is illustrated on simulated data as well as a gene expression data set. An error analysis is given for the convergence of the estimate of the classification function and its gradient to the true classification function and true gradient.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2481–2514},
numpages = {34}
}

@article{10.5555/1248547.1248634,
author = {Ekdahl, Magnus and Koski, Timo},
title = {Bounds for the Loss in Probability of Correct Classification Under Model Based Approximation},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {In many pattern recognition/classification problem the true class conditional model and class probabilities are approximated for reasons of reducing complexity and/or of statistical estimation. The approximated classifier is expected to have worse performance, here measured by the probability of correct classification. We present an analysis valid in general, and easily computable formulas for estimating the degradation in probability of correct classification when compared to the optimal classifier. An example of an approximation is the Na\"{\i}ve Bayes classifier. We show that the performance of the Na\"{\i}ve Bayes depends on the degree of functional dependence between the features and labels. We provide a sufficient condition for zero loss of performance, too.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2449–2480},
numpages = {32}
}

@article{10.5555/1248547.1248633,
author = {Chen, Di-Rong and Sun, Tao},
title = {Consistency of Multiclass Empirical Risk Minimization Methods Based on Convex Loss},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {The consistency of classification algorithm plays a central role in statistical learning theory. A consistent algorithm guarantees us that taking more samples essentially suffices to roughly reconstruct the unknown distribution. We consider the consistency of ERM scheme over classes of combinations of very simple rules (base classifiers) in multiclass classification. Our approach is, under some mild conditions, to establish a quantitative relationship between classification errors and convex risks. In comparison with the related previous work, the feature of our result is that the conditions are mainly expressed in terms of the differences between some values of the convex function.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2435–2447},
numpages = {13}
}

@article{10.5555/1248547.1248632,
author = {Belkin, Mikhail and Niyogi, Partha and Sindhwani, Vikas},
title = {Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples},
year = {2006},
issue_date = {12/1/2006},
publisher = {JMLR.org},
volume = {7},
issn = {1532-4435},
abstract = {We propose a family of learning algorithms based on a new form of regularization that allows us to exploit the geometry of the marginal distribution. We focus on a semi-supervised framework that incorporates labeled and unlabeled data in a general-purpose learner. Some transductive graph learning algorithms and standard methods including support vector machines and regularized least squares can be obtained as special cases. We use properties of reproducing kernel Hilbert spaces to prove new Representer theorems that provide theoretical basis for the algorithms. As a result (in contrast to purely graph-based approaches) we obtain a natural out-of-sample extension to novel examples and so are able to handle both transductive and truly semi-supervised settings. We present experimental evidence suggesting that our semi-supervised algorithms are able to use unlabeled data effectively. Finally we have a brief discussion of unsupervised and fully supervised learning within our general framework.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {2399–2434},
numpages = {36}
}

@article{10.5555/1248547.1248631,
author = {Ross, David A. and Zemel, Richard S.},
title =

license_type: permissive

branch_name: refs/heads/main

extension: bib