text:
mechanism for extracting information about stimuli from spike trains. Each test or question corresponds to choosing a neuron and a time interval and checking for a given number of spikes. No assumptions are made about the distribution of spikes or any other aspect of neural encoding. The chosen questions are those which most reduce the uncertainty about the stimulus, as measured by entropy and estimated from stimulus-response data. Our experiments are based on accurate simulations of responses to pure tones in the auditory nerve and are meant to illustrate the ideas rather than investigate the auditory system. The results cohere nicely with well-understood encoding of amplitude and frequency in the auditory nerve, suggesting that adaptive testing might provide a powerful tool for investigating complex and poorly understood neural structures.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {743–754},
numpages = {12}
}

@article{10.1162/153244304773936108,
author = {Mannor, Shie and Meir, Ron and Zhang, Tong},
title = {Greedy Algorithms for Classification—Consistency, Convergence Rates, and Adaptivity},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304773936108},
doi = {10.1162/153244304773936108},
abstract = {Many regression and classification algorithms proposed over the years can be described as greedy procedures for the stagewise minimization of an appropriate cost function. Some examples include additive models, matching pursuit, and boosting. In this work we focus on the classification problem, for which many recent algorithms have been proposed and applied successfully. For a specific regularized form of greedy stagewise optimization, we prove consistency of the approach under rather general conditions. Focusing on specific classes of problems we provide conditions under which our greedy procedure achieves the (nearly) minimax rate of convergence, implying that the procedure cannot be improved in a worst case setting. We also construct a fully adaptive procedure, which, without knowing the smoothness parameter of the decision boundary, converges at the same rate as if the smoothness parameter were known.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {713–741},
numpages = {29}
}

@article{10.1162/153244304773936090,
author = {Clarke, Bertrand},
title = {Comparing Bayes Model Averaging and Stacking When Model Approximation Error Cannot Be Ignored},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304773936090},
doi = {10.1162/153244304773936090},
abstract = {We compare Bayes Model Averaging, BMA, to a non-Bayes form of model averaging called stacking. In stacking, the weights are no longer posterior probabilities of models; they are obtained by a technique based on cross-validation. When the correct data generating model (DGM) is on the list of models under consideration BMA is never worse than stacking and often is demonstrably better, provided that the noise level is of order commensurate with the coefficients and explanatory variables. Here, however, we focus on the case that the correct DGM is not on the model list and may not be well approximated by the elements on the model list. We give a sequence of computed examples by choosing model lists and DGM's to contrast the risk performance of stacking and BMA. In the first examples, the model lists are chosen to reflect geometric principles that should give good performance. In these cases, stacking typically outperforms BMA, sometimes by a wide margin. In the second set of examples we examine how stacking and BMA perform when the model list includes all subsets of a set of potential predictors. When we standardize the size of terms and coefficients in this setting, we find that BMA outperforms stacking when the deviant terms in the DGM 'point' in directions accommodated by the model list but that when the deviant term points outside the model list stacking seems to do better. Overall, our results suggest the stacking has better robustness properties than BMA in the most important settings.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {683–712},
numpages = {30}
}

@article{10.1162/153244304773936081,
author = {Markovitch, Shaul and Shatil, Asaf},
title = {Speedup Learning for Repair-Based Search by Identifying Redundant Steps},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304773936081},
doi = {10.1162/153244304773936081},
abstract = {Repair-based search algorithms start with an initial solution and attempt to improve it by iteratively applying repair operators. Such algorithms can often handle large-scale problems that may be difficult for systematic search algorithms. Nevertheless, the computational cost of solving such problems is still very high. We observed that many of the repair steps applied by such algorithms are redundant in the sense that they do not eventually contribute to finding a solution. Such redundant steps are particularly harmful in repair-based search, where each step carries high cost due to the very high branching factor typically associated with it. Accurately identifying and avoiding such redundant steps would result in faster local search without harming the algorithm's problem-solving ability. In this paper we propose a speedup learning methodology for attaining this goal. It consists of the following steps: defining the concept of a redundant step; acquiring this concept during off-line learning by analyzing solution paths for training problems, tagging all the steps along the paths according to the redundancy definition and using an induction algorithm to infer a classifier based on the tagged examples; and using the acquired classifier to filter out redundant steps while solving unseen problems. Our algorithm was empirically tested on instances of real-world employee timetabling problems (ETP). The problem solver to be improved is based on one of the best methods for solving some large ETP instances. Our results show a significant improvement in speed for test problems that are similar to the given example problems.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {649–682},
numpages = {34}
}

@article{10.1162/153244304773936072,
author = {Servedio, Rocco A.},
title = {Smooth Boosting and Learning with Malicious Noise},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304773936072},
doi = {10.1162/153244304773936072},
abstract = {We describe a new boosting algorithm which generates only smooth distributions which do not assign too much weight to any single example. We show that this new boosting algorithm can be used to construct efficient PAC learning algorithms which tolerate relatively high rates of malicious noise. In particular, we use the new smooth boosting algorithm to construct malicious noise tolerant versions of the PAC-model p-norm linear threshold learning algorithms described by Servedio (2002). The bounds on sample complexity and malicious noise tolerance of these new PAC algorithms closely correspond to known bounds for the online p-norm algorithms of Grove, Littlestone and Schuurmans (1997) and Gentile and Littlestone (1999). As special cases of our new algorithms we obtain linear threshold learning algorithms which match the sample complexity and malicious noise tolerance of the online Perceptron and Winnow algorithms. Our analysis reveals an interesting connection between boosting and noise tolerance in the PAC setting.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {633–648},
numpages = {16}
}

@article{10.1162/153244304773936063,
author = {Cicchello, Orlando and Kremer, Stefan C.},
title = {Inducing Grammars from Sparse Data Sets: A Survey of Algorithms and Results},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304773936063},
doi = {10.1162/153244304773936063},
abstract = {This paper provides a comprehensive survey of the field of grammar induction applied to randomly generated languages using sparse example sets.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {603–632},
numpages = {30}
}

@article{10.1162/153244304773936054,
author = {Baldi, Pierre and Pollastri, Gianluca},
title = {The Principled Design of Large-Scale Recursive Neural Network Architectures--Dag-Rnns and the Protein Structure Prediction Problem},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304773936054},
doi = {10.1162/153244304773936054},
abstract = {We describe a general methodology for the design of large-scale recursive neural network architectures (DAG-RNNs) which comprises three fundamental steps: (1) representation of a given domain using suitable directed acyclic graphs (DAGs) to connect visible and hidden node variables; (2) parameterization of the relationship between each variable and its parent variables by feedforward neural networks; and (3) application of weight-sharing within appropriate subsets of DAG connections to capture stationarity and control model complexity. Here we use these principles to derive several specific classes of DAG-RNN architectures based on lattices, trees, and other structured graphs. These architectures can process a wide range of data structures with variable sizes and dimensions. While the overall resulting models remain probabilistic, the internal deterministic dynamics allows efficient propagation of information, as well as training by gradient descent, in order to tackle large-scale problems. These methods are used here to derive state-of-the-art predictors for protein structural features such as secondary structure (1D) and both fine- and coarse-grained contact maps (2D). Extensions, relationships to graphical models, and implications for the design of neural architectures are briefly discussed. The protein prediction servers are available over the Web at: www.igb.uci.edu/tools.htm.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {575–602},
numpages = {28}
}

@article{10.1162/153244304773936045,
author = {Castelo, Robert and Kocka, Tom\'{a}as},
title = {On Inclusion-Driven Learning of Bayesian Networks},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304773936045},
doi = {10.1162/153244304773936045},
abstract = {Two or more Bayesian network structures are Markov equivalent when the corresponding acyclic digraphs encode the same set of conditional independencies. Therefore, the search space of Bayesian network structures may be organized in equivalence classes, where each of them represents a different set of conditional independencies. The collection of sets of conditional independencies obeys a partial order, the so-called "inclusion order." This paper discusses in depth the role that the inclusion order plays in learning the structure of Bayesian networks. In particular, this role involves the way a learning algorithm traverses the search space. We introduce a condition for traversal operators, the inclusion boundary condition, which, when it is satisfied, guarantees that the search strategy can avoid local maxima. This is proved under the assumptions that the data is sampled from a probability distribution which is faithful to an acyclic digraph, and the length of the sample is unbounded. The previous discussion leads to the design of a new traversal operator and two new learning algorithms in the context of heuristic search and the Markov Chain Monte Carlo method. We carry out a set of experiments with synthetic and real-world data that show empirically the benefit of striving for the inclusion order when learning Bayesian networks from data.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {527–574},
numpages = {48}
}

@article{10.1162/153244304322972694,
author = {Perlich, Claudia and Provost, Foster and Simonoff, Jeffrey S.},
title = {Tree Induction vs. Logistic Regression: A Learning-Curve Analysis},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322972694},
doi = {10.1162/153244304322972694},
abstract = {Tree induction and logistic regression are two standard, off-the-shelf methods for building models for classification. We present a large-scale experimental comparison of logistic regression and tree induction, assessing classification accuracy and the quality of rankings based on class-membership probabilities. We use a learning-curve analysis to examine the relationship of these measures to the size of the training set. The results of the study show several things. (1) Contrary to some prior observations, logistic regression does not generally outperform tree induction. (2) More specifically, and not surprisingly, logistic regression is better for smaller training sets and tree induction for larger data sets. Importantly, this often holds for training sets drawn from the same domain (that is, the learning curves cross), so conclusions about induction-algorithm superiority on a given domain must be based on an analysis of the learning curves. (3) Contrary to conventional wisdom, tree induction is effective at producing probability-based rankings, although apparently comparatively less so for a given training-set size than at making classifications. Finally, (4) the domains on which tree induction and logistic regression are ultimately preferable can be characterized surprisingly well by a simple measure of the separability of signal from noise.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {211–255},
numpages = {45}
}

@article{10.1162/153244304322972685,
author = {Califf, Mary Elaine and Mooney, Raymond J.},
title = {Bottom-up Relational Learning of Pattern Matching Rules for Information Extraction},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322972685},
doi = {10.1162/153244304322972685},
abstract = {Information extraction is a form of shallow text processing that locates a specified set of relevant items in a natural-language document. Systems for this task require significant domain-specific knowledge and are time-consuming and difficult to build by hand, making them a good application for machine learning. We present an algorithm, RAPIER, that uses pairs of sample documents and filled templates to induce pattern-match rules that directly extract fillers for the slots in the template. RAPIER is a bottom-up learning algorithm that incorporates techniques from several inductive logic programming systems. We have implemented the algorithm in a system that allows patterns to have constraints on the words, part-of-speech tags, and semantic classes present in the filler and the surrounding text. We present encouraging experimental results on two domains.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {177–210},
numpages = {34}
}

@article{10.1162/153244304322972676,
author = {Bshouty, Nader H. and Burroughs, Lynn},
title = {On the Proper Learning of Axis-Parallel Concepts},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322972676},
doi = {10.1162/153244304322972676},
abstract = {We study the proper learnability of axis-parallel concept classes in the PAC-learning and exact-learning models. These classes include union of boxes, DNF, decision trees and multivariate polynomials. For constant-dimensional axis-parallel concepts C we show that the following problems have time complexities that are within a polynomial factor of each other.  C is α-properly exactly learnable (with hypotheses of size at most α times the target size) from membership and equivalence queries. C is α-properly PAC learnable (without membership queries) under any product distribution. There is an α-approximation algorithm for the MINEQUIC problem (given a g ∈ C find a minimal size f ∈ C that is logically equivalent to g). In particular, if one has polynomial time complexity, they all do. Using this we give the first proper-learning algorithm of constant-dimensional decision trees and the first negative results in proper learning from membership and equivalence queries for many classes. For axis-parallel concepts over a nonconstant dimension we show that with the equivalence oracle (1) ⇒ (3). We use this to show that (binary) decision trees are not properly learnable in polynomial time (assuming P ≠ NP) and DNF is not sε-properly learnable (ε < 1) in polynomial time even with an NP-oracle (assuming Σ2P ≠ PNP).},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {157–176},
numpages = {20}
}

@article{10.1162/153244304322972667,
author = {Saul, Lawrence K. and Roweis, Sam T.},
title = {Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322972667},
doi = {10.1162/153244304322972667},
abstract = {The problem of dimensionality reduction arises in many fields of information processing, including machine learning, data compression, scientific visualization, pattern recognition, and neural computation. Here we describe locally linear embedding (LLE), an unsupervised learning algorithm that computes low dimensional, neighborhood preserving embeddings of high dimensional data. The data, assumed to be sampled from an underlying manifold, are mapped into a single global coordinate system of lower dimensionality. The mapping is derived from the symmetries of locally linear reconstructions, and the actual computation of the embedding reduces to a sparse eigenvalue problem. Notably, the optimizations in LLE---though capable of generating highly nonlinear embeddings---are simple to implement, and they do not involve local minima. In this paper, we describe the implementation of the algorithm in detail and discuss several extensions that enhance its performance. We present results of the algorithm applied to data sampled from known manifolds, as well as to collections of images of faces, lips, and handwritten digits. These examples are used to provide extensive illustrations of the algorithm's performance---both successes and failures---and to relate the algorithm to previous and ongoing work in nonlinear dimensionality reduction.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {119–155},
numpages = {37}
}

@article{10.1162/153244304322765667,
author = {Gavinsky, Dmitry},
title = {Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322765667},
doi = {10.1162/153244304322765667},
abstract = {We describe a new boosting algorithm that is the first such algorithm to be both smooth and adaptive. These two features make possible performance improvements for many learning tasks whose solutions use a boosting technique. The boosting approach was originally suggested for the standard PAC model; we analyze possible applications of boosting in the context of agnostic learning, which is more realistic than the PAC model. We derive a lower bound for the final error achievable by boosting in the agnostic model and show that our algorithm actually achieves that accuracy (within a constant factor). We note that the idea of applying boosting in the agnostic model was first suggested by Ben-David, Long and Mansour (2001) and the solution they give is improved in the present paper. The accuracy we achieve is exponentially better with respect to the standard agnostic accuracy parameter β. We also describe the construction of a boosting "tandem" whose asymptotic number of iterations is the lowest possible (in both γ and ε and whose smoothness is optimal in terms of \~{O}(·). This allows adaptively solving problems whose solution is based on smooth boosting (like noise tolerant boosting and DNF membership learning), while preserving the original (non-adaptive) solution's complexity.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {101–117},
numpages = {17}
}

@article{10.1162/153244304322765658,
author = {Bakker, Bart and Heskes, Tom},
title = {Task Clustering and Gating for Bayesian Multitask Learning},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322765658},
doi = {10.1162/153244304322765658},
abstract = {Modeling a collection of similar regression or classification tasks can be improved by making the tasks 'learn from each other'. In machine learning, this subject is approached through 'multitask learning', where parallel tasks are modeled as multiple outputs of the same network. In multilevel analysis this is generally implemented through the mixed-effects linear model where a distinction is made between 'fixed effects', which are the same for all tasks, and 'random effects', which may vary between tasks. In the present article we will adopt a Bayesian approach in which some of the model parameters are shared (the same for all tasks) and others more loosely connected through a joint prior distribution that can be learned from the data. We seek in this way to combine the best parts of both the statistical multilevel approach and the neural network machinery. The standard assumption expressed in both approaches is that each task can learn equally well from any other task. In this article we extend the model by allowing more differentiation in the similarities between tasks. One such extension is to make the prior mean depend on higher-level task characteristics. More unsupervised clustering of tasks is obtained if we go from a single Gaussian prior to a mixture of Gaussians. This can be further generalized to a mixture of experts architecture with the gates depending on task characteristics. All three extensions are demonstrated through application both on an artificial data set and on two real-world problems, one a school problem and the other involving single-copy newspaper sales.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {83–99},
numpages = {17}
}

@article{10.1162/153244304322765649,
author = {Tsuda, Koji and Akaho, Shotaro and Asai, Kiyoshi},
title = {The Em Algorithm for Kernel Matrix Completion with Auxiliary Data},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322765649},
doi = {10.1162/153244304322765649},
abstract = {In biological data, it is often the case that observed data are available only for a subset of samples. When a kernel matrix is derived from such data, we have to leave the entries for unavailable samples as missing. In this paper, the missing entries are completed by exploiting an auxiliary kernel matrix derived from another information source. The parametric model of kernel matrices is created as a set of spectral variants of the auxiliary kernel matrix, and the missing entries are estimated by fitting this model to the existing entries. For model fitting, we adopt the em algorithm (distinguished from the EM algorithm of Dempster et al., 1977) based on the information geometry of positive definite matrices. We will report promising results on bacteria clustering experiments using two marker sequences: 16S and gyrB.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {67–81},
numpages = {15}
}

@article{10.1162/153244304322765630,
author = {Christensen, Stefan W. and Sinclair, Ian and Reed, Philippa A. S.},
title = {Designing Committees of Models through Deliberate Weighting of Data Points},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322765630},
doi = {10.1162/153244304322765630},
abstract = {In the adaptive derivation of mathematical models from data, each data point should contribute with a weight reflecting the amount of confidence one has in it. When no additional information for data confidence is available, all the data points should be considered equal, and are also generally given the same weight. In the formation of committees of models, however, this is often not the case and the data points may exercise unequal, even random, influence over the committee formation. In this paper, a principled approach to committee design is presented. The construction of a committee design matrix is detailed through which each data point will contribute to the committee formation with a fixed weight, while contributing with different individual weights to the derivation of the different constituent models, thus encouraging model diversity whilst not biasing the committee inadvertently towards any particular data points. Not distinctly an algorithm, it is instead a framework within which several different committee approaches may be realised. Whereas the focus in the paper lies entirely on regression, the principles discussed extend readily to classification.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {39–66},
numpages = {28}
}

@article{10.1162/153244304322765621,
author = {Petridis, Vassilios and Kaburlasos, Vassilis G.},
title = {Finknn: A Fuzzy Interval Number k-Nearest Neighbor Classifier for Prediction of Sugar Production from Populations of Samples},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322765621},
doi = {10.1162/153244304322765621},
abstract = {This work introduces FINkNN, a k-nearest-neighbor classifier operating over the metric lattice of conventional interval-supported convex fuzzy sets. We show that for problems involving populations of measurements, data can be represented by fuzzy interval numbers (FINs) and we present an algorithm for constructing FINs from such populations. We then present a lattice-theoretic metric distance between FINs with arbitrary-shaped membership functions, which forms the basis for FINkNN's similarity measurements. We apply FINkNN to the task of predicting annual sugar production based on populations of measurements supplied by Hellenic Sugar Industry. We show that FINkNN improves prediction accuracy on this task, and discuss the broader scope and potential utility of these techniques.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {17–37},
numpages = {21}
}

@article{10.1162/153244304322765612,
author = {Klautau, Aldebaro and Jevti\'{c}, Nikola and Orlitsky, Alon},
title = {On Nearest-Neighbor Error-Correcting Output Codes with Application to All-Pairs Multiclass Support Vector Machines},
year = {2003},
issue_date = {12/1/2003},
publisher = {JMLR.org},
volume = {4},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244304322765612},
doi = {10.1162/153244304322765612},
abstract = {A common way of constructing a multiclass classifier is by combining the outputs of several binary ones, according to an error-correcting output code (ECOC) scheme. The combination is typically done via a simple nearest-neighbor rule that finds the class that is closest in some sense to the outputs of the binary classifiers. For these nearest-neighbor ECOCs, we improve existing bounds on the error rate of the multiclass classifier given the average binary distance. The new bounds provide insight into the one-versus-rest and all-pairs matrices, which are compared through experiments with standard datasets. The results also show why elimination (also known as DAGSVM) and Hamming decoding often achieve the same accuracy.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {1–15},
numpages = {15}
}

@article{10.5555/944919.944982,
author = {Weston, Jason and Elisseeff, Andr\'{e} and Sch\"{o}lkopf, Bernhard and Tipping, Mike},
title = {Use of the Zero Norm with Linear Models and Kernel Methods},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We explore the use of the so-called zero-norm of the parameters of linear models in learning. Minimization of such a quantity has many uses in a machine learning context: for variable or feature selection, minimizing training error and ensuring sparsity in solutions. We derive a simple but practical method for achieving these goals and discuss its relationship to existing techniques of minimizing the zero-norm. The method boils down to implementing a simple modification of vanilla SVM, namely via an iterative multiplicative rescaling of the training data. Applications we investigate which aid our discussion include variable and feature selection on biological microarray data, and multicategory classification.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1439–1461},
numpages = {23}
}

@article{10.5555/944919.944963,
author = {Cancedda, Nicola and Gaussier, Eric and Goutte, Cyril and Renders, Jean Michel},
title = {Word Sequence Kernels},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We address the problem of categorising documents using kernel-based methods such as Support Vector Machines. Since the work of Joachims (1998), there is ample experimental evidence that SVM using the standard word frequencies as features yield state-of-the-art performance on a number of benchmark problems. Recently, Lodhi et al. (2002) proposed the use of string kernels, a novel way of computing document similarity based of matching non-consecutive subsequences of characters. In this article, we propose the use of this technique with sequences of words rather than characters. This approach has several advantages, in particular it is more efficient computationally and it ties in closely with standard linguistic pre-processing techniques. We present some extensions to sequence kernels dealing with symbol-dependent and match-dependent decay factors, and present empirical evaluations of these extensions on the Reuters-21578 datasets.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1059–1082},
numpages = {24}
}

@article{10.5555/944919.944962,
author = {Crammer, Koby and Singer, Yoram},
title = {A Family of Additive Online Algorithms for Category Ranking},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We describe a new family of topic-ranking algorithms for multi-labeled documents. The motivation for the algorithms stem from recent advances in online learning algorithms. The algorithms are simple to implement and are also time and memory efficient. We provide a unified analysis of the family of algorithms in the mistake bound model. We then discuss experiments with the proposed family of topic-ranking algorithms on the Reuters-21578 corpus and the new corpus released by Reuters in 2000. On both corpora, the algorithms we present achieve state-of-the-art results and outperforms topic-ranking adaptations of Rocchio's algorithm and of the Perceptron algorithm.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1025–1058},
numpages = {34}
}

@article{10.5555/944919.944961,
author = {Kandola, Jaz and Hofmann, Thomas and Poggio, Tomaso and Taylor, John Shawe},
title = {Introduction to the Special Issue on Machine Learning Methods for Text and Images},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {1023–1024},
numpages = {2}
}

@article{10.5555/944919.944959,
author = {Strens, Malcolm J. A. and Moore, Andrew W.},
title = {Policy Search Using Paired Comparisons},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {Direct policy search is a practical way to solve reinforcement learning (RL) problems involving continuous state and action spaces. The goal becomes finding policy parameters that maximize a noisy objective function. The Pegasus method converts this stochastic optimization problem into a deterministic one, by using fixed start states and fixed random number sequences for comparing policies (Ng and Jordan, 2000). We evaluate Pegasus, and new paired comparison methods, using the mountain car problem, and a difficult pursuer-evader problem. We conclude that: (i) paired tests can improve performance of optimization procedures; (ii) several methods are available to reduce the 'overfitting' effect found with Pegasus; (iii) adapting the number of trials used for each comparison yields faster learning; (iv) pairing also helps stochastic search methods such as differential evolution.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {921–950},
numpages = {30}
}

@article{10.5555/944919.944958,
author = {Singer, Bryan and Veloso, Manuela},
title = {Learning to Construct Fast Signal Processing Implementations},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {A single signal processing algorithm can be represented by many mathematically equivalent formulas. However, when these formulas are implemented in code and run on real machines, they have very different runtimes. Unfortunately, it is extremely difficult to model this broad performance range. Further, the space of formulas for real signal transforms is so large that it is impossible to search it exhaustively for fast implementations. We approach this search question as a control learning problem. We present a new method for learning to generate fast formulas, allowing us to intelligently search through only the most promising formulas. Our approach incorporates signal processing knowledge, hardware features, and formula performance data to learn to construct fast formulas. Our method learns from performance data for a few formulas of one size and then can construct formulas that will have the fastest runtimes possible across many sizes.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {887–919},
numpages = {33}
}

@article{10.5555/944919.944957,
author = {Sebban, Marc and Nock, Richard and Lallich, St\'{e}phane},
title = {Stopping Criterion for Boosting Based Data Reduction Techniques: From Binary to Multiclass Problem},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {So far, boosting has been used to improve the quality of moderately accurate learning algorithms, by weighting and combining many of their weak hypotheses into a final classifier with theoretically high accuracy. In a recent work (Sebban, Nock and Lallich, 2001), we have attempted to adapt boosting properties to data reduction techniques. In this particular context, the objective was not only to improve the success rate, but also to reduce the time and space complexities due to the storage requirements of some costly learning algorithms, such as nearest-neighbor classifiers. In that framework, each weak hypothesis, which is usually built and weighted from the learning set, is replaced by a single learning instance. The weight given by boosting defines in that case the relevance of the instance, and a statistical test allows one to decide whether it can be discarded without damaging further classification tasks. In Sebban, Nock and Lallich (2001), we addressed problems with two classes. It is the aim of the present paper to relax the class constraint, and extend our contribution to multiclass problems. Beyond data reduction, experimental results are also provided on twenty-three datasets, showing the benefits that our boosting-derived weighting rule brings to weighted nearest neighbor classifiers.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {863–885},
numpages = {23}
}

@article{10.5555/944919.944956,
author = {Scheffer, Tobias and Wrobel, Stefan},
title = {Finding the Most Interesting Patterns in a Database Quickly by Using Sequential Sampling},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {Many discovery problems, e.g. subgroup or association rule discovery, can naturally be cast as n-best hypotheses problems where the goal is to find the n hypotheses from a given hypothesis space that score best according to a certain utility function. We present a sampling algorithm that solves this problem by issuing a small number of database queries while guaranteeing precise bounds on the confidence and quality of solutions. Known sampling approaches have treated single hypothesis selection problems, assuming that the utility is the average (over the examples) of some function --- which is not the case for many frequently used utility functions. We show that our algorithm works for all utilities that can be estimated with bounded error. We provide these error bounds and resulting worst-case sample bounds for some of the most frequently used utilities, and prove that there is no sampling algorithm for a popular class of utility functions that cannot be estimated with bounded error. The algorithm is sequential in the sense that it starts to return (or discard) hypotheses that already seem to be particularly good (or bad) after a few examples. Thus, the algorithm is almost always faster than its worst-case bounds.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {833–862},
numpages = {30}
}

@article{10.5555/944919.944955,
author = {Perkins, Theodore J. and Barto, Andrew G.},
title = {Lyapunov Design for Safe Reinforcement Learning},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {Lyapunov design methods are used widely in control engineering to design controllers that achieve qualitative objectives, such as stabilizing a system or maintaining a system's state in a desired operating range. We propose a method for constructing safe, reliable reinforcement learning agents based on Lyapunov design principles. In our approach, an agent learns to control a system by switching among a number of given, base-level controllers. These controllers are designed using Lyapunov domain knowledge so that any switching policy is safe and enjoys basic performance guarantees. Our approach thus ensures qualitatively satisfactory agent behavior for virtually any reinforcement learning algorithm and at all times, including while the agent is learning and taking exploratory actions. We demonstrate the process of designing safe agents for four different control problems. In simulation experiments, we find that our theoretically motivated designs also enjoy a number of practical benefits, including reasonable performance initially and throughout learning, and accelerated learning.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {803–832},
numpages = {30}
}

@article{10.5555/944919.944954,
author = {Nair, Prasanth B. and Choudhury, Arindam and Keane, Andy J.},
title = {Some Greedy Learning Algorithms for Sparse Regression and Classification with Mercer Kernels},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We present greedy learning algorithms for building sparse nonlinear regression and classification models from observational data using Mercer kernels. Our objective is to develop efficient numerical schemes for reducing the training and runtime complexities of kernel-based algorithms applied to large datasets. In the spirit of Natarajan's greedy algorithm (Natarajan, 1995), we iteratively minimize the L2 loss function subject to a specified constraint on the degree of sparsity required of the final model or till a specified stopping criterion is reached. We discuss various greedy criteria for basis selection and numerical schemes for improving the robustness and computational efficiency. Subsequently, algorithms based on residual minimization and thin QR factorization are presented for constructing sparse regression and classification models. During the course of the incremental model construction, the algorithms are terminated using model selection principles such as the minimum descriptive length (MDL) and Akaike's information criterion (AIC). Finally, experimental results on benchmark data are presented to demonstrate the competitiveness of the algorithms developed in this paper.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {781–801},
numpages = {21}
}

@article{10.5555/944919.944953,
author = {Marx, Zvika and Dagan, Ido and Buhmann, Joachim M. and Shamir, Eli},
title = {Coupled Clustering: A Method for Detecting Structural Correspondence},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {This paper proposes a new paradigm and a computational framework for revealing equivalencies (analogies) between sub-structures of distinct composite systems that are initially represented by unstructured data sets. For this purpose, we introduce and investigate a variant of traditional data clustering, termed coupled clustering, which outputs a configuration of corresponding subsets of two such representative sets. We apply our method to synthetic as well as textual data. Its achievements in detecting topical correspondences between textual corpora are evaluated through comparison to performance of human experts.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {747–780},
numpages = {34}
}

@article{10.5555/944919.944952,
author = {Marchand, Mario and Taylor, John Shawe},
title = {The Set Covering Machine},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We extend the classical algorithms of Valiant and Haussler for learning compact conjunctions and disjunctions of Boolean attributes to allow features that are constructed from the data and to allow a trade-off between accuracy and complexity. The result is a general-purpose learning machine, suitable for practical learning tasks, that we call the set covering machine. We present a version of the set covering machine that uses data-dependent balls for its set of features and compare its performance with the support vector machine. By extending a technique pioneered by Littlestone and Warmuth, we bound its generalization error as a function of the amount of data compression it achieves during training. In experiments with real-world learning tasks, the bound is shown to be extremely tight and to provide an effective guide for model selection.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {723–746},
numpages = {24}
}

@article{10.5555/944919.944951,
author = {Ling, Charles X. and Zhang, Huajie},
title = {The Representational Power of Discrete Bayesian Networks},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {One of the most important fundamental properties of Bayesian networks is the representational power, reflecting what kind of functions they can or cannot represent. In this paper, we establish an association between the structural complexity of Bayesian networks and their representational power. We use the maximum number of nodes' parents as the measure for the structural complexity of Bayesian networks, and the maximum XOR contained in a target function as the measure for the function complexity. A representational upper bound is established and proved. Roughly speaking, discrete Bayesian networks with each node having at most k parents cannot represent any function containing (k+1)-XORs. Our theoretical results help us to gain a deeper understanding on the capacities and limitations of Bayesian networks.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {709–721},
numpages = {13}
}

@article{10.5555/944919.944950,
author = {Getoor, Lisa and Friedman, Nir and Koller, Daphne and Taskar, Benjamin},
title = {Learning Probabilistic Models of Link Structure},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {Most real-world data is heterogeneous and richly interconnected. Examples include the Web, hypertext, bibliometric data and social networks. In contrast, most statistical learning methods work with "flat" data representations, forcing us to convert our data into a form that loses much of the link structure. The recently introduced framework of probabilistic relational models (PRMs) embraces the object-relational nature of structured data by capturing probabilistic interactions between attributes of related entities. In this paper, we extend this framework by modeling interactions between the attributes and the link structure itself. An advantage of our approach is a unified generative model for both content and relational structure. We propose two mechanisms for representing a probabilistic distribution over link structures: reference uncertainty and existence uncertainty. We describe the appropriate conditions for using each model and present learning algorithms for each. We present experimental results showing that the learned models can be used to predict link structure and, moreover, the observed link structure can be used to provide better predictions for the attributes in the model.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {679–707},
numpages = {29}
}

@article{10.5555/944919.944949,
author = {Dooly, Daniel R. and Zhang, Qi and Goldman, Sally A. and Amar, Robert A.},
title = {Multiple Instance Learning of Real Valued Data},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {The multiple-instance learning model has received much attention recently with a primary application area being that of drug activity prediction. Most prior work on multiple-instance learning has been for concept learning, yet for drug activity prediction, the label is a real-valued affinity measurement giving the binding strength. We present extensions of k-nearest neighbors (k-NN), Citation-kNN, and the diverse density algorithm for the real-valued setting and study their performance on Boolean and real-valued data. We also provide a method for generating chemically realistic artificial data.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {651–678},
numpages = {28}
}

@article{10.5555/944919.944948,
author = {Blockeel, Hendrik and Struyf, Jan},
title = {Efficient Algorithms for Decision Tree Cross-Validation},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {Cross-validation is a useful and generally applicable technique often employed in machine learning, including decision tree induction. An important disadvantage of straightforward implementation of the technique is its computational overhead. In this paper we show that, for decision trees, the computational overhead of cross-validation can be reduced significantly by integrating the cross-validation with the normal decision tree induction process. We discuss how existing decision tree algorithms can be adapted to this aim, and provide an analysis of the speedups these adaptations may yield. We identify a number of parameters that influence the obtainable speedups, and validate and refine our analysis with experiments on a variety of data sets with two different implementations. Besides cross-validation, we also briefly explore the usefulness of these techniques for bagging. We conclude with some guidelines concerning when these optimizations should be considered.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {621–650},
numpages = {30}
}

@article{10.5555/944919.944947,
author = {Brodley, Carla E. and Danyluk, Andrea P.},
title = {Special Issue on the Eighteenth International Conference on Machine Learning (Icml2001)},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {619},
numpages = {1}
}

@article{10.5555/944919.944945,
author = {Bshouty, Nader H. and Gavinsky, Dmitry},
title = {On Boosting with Polynomially Bounded Distributions},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We construct a framework which allows an algorithm to turn the distributions produced by some boosting algorithms into polynomially smooth distributions (w.r.t. the PAC oracle's distribution), with minimal performance loss.Further, we explore the case of Freund and Schapire's AdaBoost algorithm, bounding its distributions to polynomially smooth. The main advantage of AdaBoost over other boosting techniques is that it is adaptive, i.e., it is able to take advantage of weak hypotheses that are more accurate than it was assumed a priori. We show that the feature of adaptiveness is preserved and improved by our technique.Our scheme allows the execution of AdaBoost in the on-line boosting mode (i.e., to perform boosting "by filtering"). Executed this way (and possessing the quality of smoothness), now AdaBoost may be efficiently applied to a wider range of learning problems than before.In particular, we demonstrate AdaBoost's application to the task of DNF learning using membership queries. This application results in an algorithm that chooses the number of boosting iterations adaptively, and, consequently, adaptively chooses the size of the produced final hypothesis. This answers affirmatively a question posed by Jackson.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {483–506},
numpages = {24}
}

@article{10.5555/944919.944944,
author = {Bartlett, Peter L. and Mendelson, Shahar},
title = {Rademacher and Gaussian Complexities: Risk Bounds and Structural Results},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. We consider function classes that can be expressed as combinations of functions from basis classes and show how the Rademacher and Gaussian complexities of such a function class can be bounded in terms of the complexity of the basis classes. We give examples of the application of these techniques in finding data-dependent risk bounds for decision trees, neural networks and support vector machines.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {463–482},
numpages = {20},
keywords = {error bounds, maximum discrepancy, data-dependent complexity, Rademacher averages}
}

@article{10.5555/944919.944943,
author = {Ben-David, Shai and Eiron, Nadav and Simon, Hans Ulrich},
title = {Limitations of Learning via Embeddings in Euclidean Half Spaces},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {The notion of embedding a class of dichotomies in a class of linear half spaces is central to the support vector machines paradigm. We examine the question of determining the minimal Euclidean dimension and the maximal margin that can be obtained when the embedded class has a finite VC dimension. We show that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in low-dimensional half spaces. (In fact, we show that the Euclidean dimension must be almost as high as the size of the instance space.) We strengthen this result even further by showing that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in half spaces (of arbitrarily high Euclidean dimension) with a large margin. (In fact, the margin cannot be substantially larger than the margin achieved by the trivial embedding.) Furthermore, these bounds are robust in the sense that allowing each image half space to err on a small fraction of the instances does not imply a significant weakening of these dimension and margin bounds. Our results indicate that any universal learning machine, which transforms data into the Euclidean space and then applies linear (or large margin) classification, cannot enjoy any meaningful generalization guarantees that are based on either VC dimension or margins considerations. This failure of generalization bounds applies even to classes for which "straight forward" empirical risk minimization does enjoy meaningful generalization guarantees.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {441–461},
numpages = {21},
keywords = {concept learning, embeddings in half spaces, large margin classification}
}

@article{10.5555/944919.944942,
author = {Kalai, Adam and Vempala, Santosh},
title = {Efficient Algorithms for Universal Portfolios},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {A constant rebalanced portfolio is an investment strategy that keeps the same distribution of wealth among a set of stocks from day to day. There has been much work on Cover's Universal algorithm, which is competitive with the best constant rebalanced portfolio determined in hindsight (Cover, 1991, Helmbold et al, 1998, Blum and Kalai, 1999, Foster and Vohra, 1999, Vovk, 1998, Cover and Ordentlich, 1996a, Cover, 1996c). While this algorithm has good performance guarantees, all known implementations are exponential in the number of stocks, restricting the number of stocks used in experiments (Helmbold et al, 1998, Cover and Ordentlich, 1996a, Ordentlich and Cover, 1996b, Cover, 1996c, Blum and Kalai, 1999). We present an efficient implementation of the Universal algorithm that is based on non-uniform random walks that are rapidly mixing (Applegate and Kannan, 1991, Lovasz and Simonovits, 1992, Frieze and Kannan, 1999). This same implementation also works for non-financial applications of the Universal algorithm, such as data compression (Cover, 1996c) and language modeling (Chen et al, 1999).},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {423–440},
numpages = {18}
}

@article{10.5555/944919.944941,
author = {Auer, Peter},
title = {Using Confidence Bounds for Exploitation-Exploration Trade-Offs},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We show how a standard tool from statistics --- namely confidence bounds --- can be used to elegantly deal with situations which exhibit an exploitation-exploration trade-off. Our technique for designing and analyzing algorithms for such situations is general and can be applied when an algorithm has to make exploitation-versus-exploration decisions based on uncertain information provided by a random process. We apply our technique to two models with such an exploitation-exploration trade-off. For the adversarial bandit problem with shifting our new algorithm suffers only O((ST)1/2) regret with high probability over T trials with S shifts. Such a regret bound was previously known only in expectation. The second model we consider is associative reinforcement learning with linear value functions. For this model our technique improves the regret from O(T3/4) to O(T1/2).},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {397–422},
numpages = {26},
keywords = {exploitation-exploration, online Learning, bandit problem, linear value function, reinforcement learning}
}

@article{10.5555/944919.944940,
author = {Bousquet, Olivier and Warmuth, Manfred K.},
title = {Tracking a Small Set of Experts by Mixing Past Posteriors},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts. Its goal is to predict almost as well as the best sequence of such experts chosen off-line by partitioning the training sequence into k+1 sections and then choosing the best expert for each section. We build on methods developed by Herbster and Warmuth and consider an open problem posed by Freund where the experts in the best partition are from a small pool of size m. Since k >> m, the best expert shifts back and forth between the experts of the small pool. We propose algorithms that solve this open problem by mixing the past posteriors maintained by the master algorithm. We relate the number of bits needed for encoding the best partition to the loss bounds of the algorithms. Instead of paying log n for choosing the best expert in each section we first pay log (n choose m) bits in the bounds for identifying the pool of m experts and then log m bits per new section. In the bounds we also pay twice for encoding the boundaries of the sections.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {363–396},
numpages = {34},
keywords = {on-line learning, share updates, shifting experts, loss bounds}
}

@article{10.5555/944919.944939,
author = {Long, Philip M.},
title = {Introduction to the Special Issue on Computational Learning Theory},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {361–362},
numpages = {2}
}

@article{10.5555/944919.944937,
author = {Blei, David M. and Ng, Andrew Y. and Jordan, Michael I.},
title = {Latent Dirichlet Allocation},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
abstract = {We describe latent Dirichlet allocation (LDA), a generative probabilistic model for collections of discrete data such as text corpora. LDA is a three-level hierarchical Bayesian model, in which each item of a collection is modeled as a finite mixture over an underlying set of topics. Each topic is, in turn, modeled as an infinite mixture over an underlying set of topic probabilities. In the context of text modeling, the topic probabilities provide an explicit representation of a document. We present efficient approximate inference techniques based on variational methods and an EM algorithm for empirical Bayes parameter estimation. We report results in document modeling, text classification, and collaborative filtering, comparing to a mixture of unigrams model and the probabilistic LSI model.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {993–1022},
numpages = {30}
}

@article{10.1162/jmlr.2003.3.4-5.951,
author = {Crammer, Koby and Singer, Yoram},
title = {Ultraconservative Online Algorithms for Multiclass Problems},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/jmlr.2003.3.4-5.951},
doi = {10.1162/jmlr.2003.3.4-5.951},
abstract = {In this paper we study a paradigm to generalize online classification algorithms for binary classification problems to multiclass problems. The particular hypotheses we investigate maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarity-score between each prototype and the input instance and sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this paper we introduce the notion of ultraconservativeness. Ultraconservative algorithms are algorithms that update only the prototypes attaining similarity-scores which are higher than the score of the correct label's prototype. We start by describing a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores. We then discuss a specific online algorithm that seeks a set of prototypes which have a small norm. The resulting algorithm, which we term MIRA (for Margin Infused Relaxed Algorithm) is ultraconservative as well. We derive mistake bounds for all the algorithms and provide further analysis of MIRA using a generalized notion of the margin for multiclass problems. We discuss the form the algorithms take in the binary case and show that all the algorithms from the first family reduce to the Perceptron algorithm while MIRA provides a new Perceptron-like algorithm with a margin-dependent learning rate. We then return to multiclass problems and describe an analogous multiplicative family of algorithms with corresponding mistake bounds. We end the formal part by deriving and analyzing a multiclass version of Li and Long's ROMMA algorithm. We conclude with a discussion of experimental results that demonstrate the merits of our algorithms.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {951–991},
numpages = {41}
}

@article{10.1162/153244303768966148,
author = {Szita, Istv\'{a}n and Tak\'{a}cs, B\'{a}lint and L\"{o}rincz, Andr\'{a}s},
title = {ε-Mdps: Learning in Varying Environments},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244303768966148},
doi = {10.1162/153244303768966148},
abstract = {In this paper ε-MDP-models are introduced and convergence theorems are proven using the generalized MDP framework of Szepesvari and Littman. Using this model family, we show that Q-learning is capable of finding near-optimal policies in varying environments. The potential of this new family of MDP models is illustrated via a reinforcement learning algorithm called event-learning which separates the optimization of decision making from the controller. We show that event-learning augmented by a particular controller, which gives rise to an ε-MDP, enables near optimal performance even if considerable and sudden changes may occur in the environment. Illustrations are provided on the two-segment pendulum problem.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {145–174},
numpages = {30},
keywords = {SDS controller, reinforcement learning, generalized MDP, event-learning, SARSA, convergence, MDP, ε-MDP}
}

@article{10.1162/153244303768966139,
author = {Gers, Felix A. and Schraudolph, Nicol N. and Schmidhuber, J\"{u}rgen},
title = {Learning Precise Timing with Lstm Recurrent Networks},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244303768966139},
doi = {10.1162/153244303768966139},
abstract = {The temporal distance between events conveys information essential for numerous sequential tasks such as motor control and rhythm detection. While Hidden Markov Models tend to ignore this information, recurrent neural networks (RNNs) can in principle learn to make use of it. We focus on Long Short-Term Memory (LSTM) because it has been shown to outperform other RNNs on tasks involving long time lags. We find that LSTM augmented by "peephole connections" from its internal cells to its multiplicative gates can learn the fine distinction between sequences of spikes spaced either 50 or 49 time steps apart without the help of any short training exemplars. Without external resets or teacher forcing, our LSTM variant also learns to generate stable streams of precisely timed spikes and other highly nonlinear periodic patterns. This makes LSTM a promising approach for tasks that require the accurate measurement or generation of time intervals.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {115–143},
numpages = {29},
keywords = {long short-term memory, recurrent neural networks, timing}
}

@article{10.1162/153244303768966120,
author = {Chan, Kwokleung and Lee, Te-Won and Sejnowski, Terrence J.},
title = {Variational Learning of Clusters of Undercomplete Nonsymmetric Independent Components},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244303768966120},
doi = {10.1162/153244303768966120},
abstract = {We apply a variational method to automatically determine the number of mixtures of independent components in high-dimensional datasets, in which the sources may be nonsymmetrically distributed. The data are modeled by clusters where each cluster is described as a linear mixture of independent factors. The variational Bayesian method yields an accurate density model for the observed data without overfitting problems. This allows the dimensionality of the data to be identified for each cluster. The new method was successfully applied to a difficult real-world medical dataset for diagnosing glaucoma.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {99–114},
numpages = {16},
keywords = {ICA, Bayesian learning, mixture models, density estimations}
}

@article{10.1162/153244303768966111,
author = {Antos, Andr\'{a}s and K\'{e}gl, Bal\'{a}zs and Linder, Tam\'{a}s and Lugosi, G\'{a}bor},
title = {Data-Dependent Margin-Based Generalization Bounds for Classification},
year = {2003},
issue_date = {3/1/2003},
publisher = {JMLR.org},
volume = {3},
number = {null},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244303768966111},
doi = {10.1162/153244303768966111},
abstract = {We derive new margin-based inequalities for the probability of error of classifiers. The main feature of these bounds is that they can be calculated using the training data and therefore may be effectively used for model selection purposes. In particular, the bounds involve empirical complexities measured on the training data (such as the empirical fat-shattering dimension) as opposed to their worst-case counterparts traditionally used in such analyses. Also, our bounds appear to be sharper and more general than recent results involving empirical complexity measures. In addition, we develop an alternative data-based bound for the generalization error of classes of convex combinations of classifiers involving an empirical complexity measure that is easier to compute than the empirical covering number or fat-shattering dimension. We also show examples of efficient computation of the new bounds.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {73–98},
numpages = {26},
keywords = {error estimation, fat-shattering dimension, classification, margin-based bounds}
}

@article{10.1162/153244301753683735,
author = {Mahony, Robert E. and Williamson, Robert C.},
title = {Prior Knowledge and Preferential Structures in Gradient Descent Learning Algorithms},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244301753683735},
doi = {10.1162/153244301753683735},
abstract = {A family of gradient descent algorithms for learning linear functions in an online setting is considered. The family includes the classical LMS algorithm as well as new variants such as the Exponentiated Gradient (EG) algorithm due to Kivinen and Warmuth. The algorithms are based on prior distributions defined on the weight space. Techniques from differential geometry are used to develop the algorithms as gradient descent iterations with respect to the natural gradient in the Riemannian structure induced by the prior distribution. The proposed framework subsumes the notion of "link-functions".},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {311–355},
numpages = {45}
}

@article{10.1162/153244301753683726,
author = {Herbster, Mark and Warmuth, Manfred K.},
title = {Tracking the Best Linear Predictor},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244301753683726},
doi = {10.1162/153244301753683726},
abstract = {In most on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best off-line predictor u from a comparison class of predictors. We call such bounds static bounds. The interesting feature of these bounds is that they hold for an arbitrary sequence of examples. Recently some work has been done where the predictor ut at each trial t is allowed to change with time, and the total on-line loss of the algorithm is compared to the sum of the losses of ut at each trial plus the total "cost" for shifting to successive predictors. This is to model situations in which the examples change over time, and different predictors from the comparison class are best for different segments of the sequence of examples. We call such bounds shifting bounds. They hold for arbitrary sequences of examples and arbitrary sequences of predictors.Naturally shifting bounds are much harder to prove. The only known bounds are for the case when the comparison class consists of a sequences of experts or boolean disjunctions. In this paper we develop the methodology for lifting known static bounds to the shifting case. In particular we obtain bounds when the comparison class consists of linear neurons (linear combinations of experts). Our essential technique is to project the hypothesis of the static algorithm at the end of each trial into a suitably chosen convex region. This keeps the hypothesis of the algorithm well-behaved and the static bounds can be converted to shifting bounds.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {281–309},
numpages = {29}
}

@article{10.1162/153244301753683717,
author = {Herbrich, Ralf and Graepel, Thore and Campbell, Colin},
title = {Bayes Point Machines},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244301753683717},
doi = {10.1162/153244301753683717},
abstract = {Kernel-classifiers comprise a powerful class of non-linear decision functions for binary classification. The support vector machine is an example of a learning algorithm for kernel classifiers that singles out the consistent classifier with the largest margin, i.e. minimal real-valued output on the training sample, within the set of consistent hypotheses, the so-called version space. We suggest the Bayes point machine as a well-founded improvement which approximates the Bayes-optimal decision by the centre of mass of version space. We present two algorithms to stochastically approximate the centre of mass of version space: a billiard sampling algorithm and a sampling algorithm based on the well known perceptron algorithm. It is shown how both algorithms can be extended to allow for soft-boundaries in order to admit training errors. Experimentally, we find that - for the zero training error case - Bayes point machines consistently outperform support vector machines on both surrogate data and real-world benchmark data sets. In the soft-boundary/soft-margin case, the improvement over support vector machines is shown to be reduced. Finally, we demonstrate that the real-valued output of single Bayes points on novel test points is a valid confidence measure and leads to a steady decrease in generalisation error when used as a rejection criterion.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {245–279},
numpages = {35}
}

@article{10.1162/153244301753344614,
author = {Heckerman, David and Chickering, David Maxwell and Meek, Christopher and Rounthwaite, Robert and Kadie, Carl},
title = {Dependency Networks for Inference, Collaborative Filtering, and Data Visualization},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244301753344614},
doi = {10.1162/153244301753344614},
abstract = {We describe a graphical model for probabilistic relationships--an alternative to the Bayesian network--called a dependency network. The graph of a dependency network, unlike a Bayesian network, is potentially cyclic. The probability component of a dependency network, like a Bayesian network, is a set of conditional distributions, one for each node given its parents. We identify several basic properties of this representation and describe a computationally efficient procedure for learning the graph and probability components from data. We describe the application of this representation to probabilistic inference, collaborative filtering (the task of predicting preferences), and the visualization of acausal predictive relationships.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {49–75},
numpages = {27}
}

@article{10.1162/153244301753344605,
author = {Meila, Marina and Jordan, Michael I.},
title = {Learning with Mixtures of Trees},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244301753344605},
doi = {10.1162/153244301753344605},
abstract = {This paper describes the mixtures-of-trees model, a probabilistic model for discrete multidimensional domains. Mixtures-of-trees generalize the probabilistic trees of Chow and Liu (1968) in a different and complementary direction to that of Bayesian networks. We present efficient algorithms for learning mixtures-of-trees models in maximum likelihood and Bayesian frameworks. We also discuss additional efficiencies that can be obtained when data are "sparse," and we present data structures and algorithms that exploit such sparseness. Experimental results demonstrate the performance of the model for both density estimation and classification. We also discuss the sense in which tree-based classifiers perform an implicit form of feature selection, and demonstrate a resulting insensitivity to irrelevant attributes.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {1–48},
numpages = {48}
}

@article{10.1162/15324430152748236,
author = {Tipping, Michael E.},
title = {Sparse Bayesian Learning and the Relevance Vector Machine},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/15324430152748236},
doi = {10.1162/15324430152748236},
abstract = {This paper introduces a general Bayesian framework for obtaining sparse solutions to regression and classification tasks utilising models linear in the parameters. Although this framework is fully general, we illustrate our approach with a particular specialisation that we denote the 'relevance vector machine' (RVM), a model of identical functional form to the popular and state-of-the-art 'support vector machine' (SVM). We demonstrate that by exploiting a probabilistic Bayesian learning framework, we can derive accurate prediction models which typically utilise dramatically fewer basis functions than a comparable SVM while offering a number of additional advantages. These include the benefits of probabilistic predictions, automatic estimation of 'nuisance' parameters, and the facility to utilise arbitrary basis functions (e.g. non-'Mercer' kernels). We detail the Bayesian framework and associated learning algorithm for the RVM, and give some illustrative examples of its application along with some comparative benchmarks. We offer some explanation for the exceptional degree of sparsity obtained, and discuss and demonstrate some of the advantageous features, and potential extensions, of Bayesian relevance learning.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {211–244},
numpages = {34}
}

@article{10.1162/15324430152748227,
author = {Smola, Alexander J. and Mika, Sebastian and Sch\"{o}lkopf, Bernhard and Williamson, Robert C.},
title = {Regularized Principal Manifolds},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/15324430152748227},
doi = {10.1162/15324430152748227},
abstract = {Many settings of unsupervised learning can be viewed as quantization problems - the minimization of the expected quantization error subject to some restrictions. This allows the use of tools such as regularization from the theory of (supervised) risk minimization for unsupervised learning. This setting turns out to be closely related to principal curves, the generative topographic map, and robust coding.We explore this connection in two ways: (1) we propose an algorithm for finding principal manifolds that can be regularized in a variety of ways; and (2) we derive uniform convergence bounds and hence bounds on the learning rates of the algorithm. In particular, we give bounds on the covering numbers which allows us to obtain nearly optimal learning rates for certain types of regularization operators. Experimental results demonstrate the feasibility of the approach.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {179–209},
numpages = {31}
}

@article{10.1162/15324430152748218,
author = {Mangasarian, O. L. and Musicant, David R.},
title = {Lagrangian Support Vector Machines},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/15324430152748218},
doi = {10.1162/15324430152748218},
abstract = {An implicit Lagrangian for the dual of a simple reformulation of the standard quadratic program of a linear support vector machine is proposed. This leads to the minimization of an unconstrained differentiable convex function in a space of dimensionality equal to the number of classified points. This problem is solvable by an extremely simple linearly convergent Lagrangian support vector machine (LSVM) algorithm. LSVM requires the inversion at the outset of a single matrix of the order of the much smaller dimensionality of the original input space plus one. The full algorithm is given in this paper in 11 lines of MATLAB code without any special optimization tools such as linear or quadratic programming solvers. This LSVM code can be used "as is" to solve classification problems with millions of points. For example, 2 million points in 10 dimensional input space were classified by a linear surface in 82 minutes on a Pentium III 500 MHz notebook with 384 megabytes of memory (and additional swap space), and in 7 minutes on a 250 MHz UltraSPARC II processor with 2 gigabytes of memory. Other standard classification test problems were also solved. Nonlinear kernel classification can also be solved by LSVM. Although it does not scale up to very large problems, it can handle any positive semidefinite kernel and is guaranteed to converge. A short MATLAB code is also given for nonlinear kernels and tested on a number of problems.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {161–177},
numpages = {17}
}

@article{10.1162/15324430152733142,
author = {Collobert, Ronan and Bengio, Samy},
title = {SVMTorch: Support Vector Machines for Large-Scale Regression Problems},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/15324430152733142},
doi = {10.1162/15324430152733142},
abstract = {Support Vector Machines (SVMs) for regression problems are trained by solving a quadratic optimization problem which needs on the order of l square memory and time resources to solve, where l is the number of training examples. In this paper, we propose a decomposition algorithm, SVMTorch (available at http://www.idiap.ch/learning/SVMTorch.html), which is similar to SVM-Light proposed by Joachims (1999) for classification problems, but adapted to regression problems. With this algorithm, one can now efficiently solve large-scale regression problems (more than 20000 examples). Comparisons with Nodelib, another publicly available SVM algorithm for large-scale regression problems from Flake and Lawrence (2000) yielded significant time improvements. Finally, based on a recent paper from Lin (2000), we show that a convergence proof exists for our algorithm.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {143–160},
numpages = {18}
}

@article{10.1162/15324430152733133,
author = {Allwein, Erin L. and Schapire, Robert E. and Singer, Yoram},
title = {Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/15324430152733133},
doi = {10.1162/15324430152733133},
abstract = {We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning algorithm. The proposed framework unifies some of the most popular approaches in which each class is compared against all others, or in which all pairs of classes are compared to each other, or in which output codes with error-correcting properties are used. We propose a general method for combining the classifiers generated on the binary problems, and we prove a general empirical multiclass loss bound given the empirical loss of the individual binary learning algorithms. The scheme and the corresponding bounds apply to many popular classification learning algorithms including support-vector machines, AdaBoost, regression, logistic regression and decision-tree algorithms. We also give a multiclass generalization error analysis for general output codes with AdaBoost as the binary learner. Experimental results with SVM and AdaBoost show that our scheme provides a viable alternative to the most commonly used multiclass algorithms.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {113–141},
numpages = {29}
}

@article{10.1162/15324430152733124,
author = {Boyan, Justin and Moore, Andrew W.},
title = {Learning Evaluation Functions to Improve Optimization by Local Search},
year = {2001},
issue_date = {9/1/2001},
publisher = {JMLR.org},
volume = {1},
issn = {1532-4435},
url = {https://doi.org/10.1162/15324430152733124},
doi = {10.1162/15324430152733124},
abstract = {This paper describes algorithms that learn to improve search performance on large-scale optimization tasks. The main algorithm, STAGE, works by learning an evaluation function that predicts the outcome of a local search algorithm, such as hillclimbing or Walksat, from features of states visited during search. The learned evaluation function is then used to bias future search trajectories toward better optima on the same problem. Another algorithm, X-STAGE, transfers previously learned evaluation functions to new, similar optimization problems. Empirical results are provided on seven large-scale optimization domains: bin-packing, channel routing, Bayesian network structure-finding, radiotherapy treatment planning, cartogram design, Boolean satisfiability, and Boggle board setup.},
journal = {J. Mach. Learn. Res.},
month = sep,
pages = {77–112},
numpages = {36}
}

@article{10.5555/944790.944823,
author = {Osborne, Miles},
title = {Shallow Parsing Using Noisy and Non-Stationary Training Material},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {Shallow parsers are usually assumed to be trained on noise-free material, drawn from the same distribution as the testing material. However, when either the training set is noisy or else drawn from a different distributions, performance may be degraded. Using the parsed Wall Street Journal, we investigate the performance of four shallow parsers (maximum entropy, memory-based learning, N-grams and ensemble learning) trained using various types of artificially noisy material. Our first set of results show that shallow parsers are surprisingly robust to synthetic noise, with performance gradually decreasing as the rate of noise increases. Further results show that no single shallow parser performs best in all noise situations. Final results show that simple, parser-specific extensions can improve noise-tolerance. Our second set of results addresses the question of whether naturally occurring disfluencies undermines performance more than does a change in distribution. Results using the parsed Switchboard corpus suggest that, although naturally occurring disfluencies might harm performance, differences in distribution between the training set and the testing set are more significant.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {695–719},
numpages = {25}
}

@article{10.5555/944790.944822,
author = {D\'{e}jean, Herv\'{e}},
title = {Learning Rules and Their Exceptions},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {We present in this article a top-down inductive system, ALLiS, for learning linguistic structures. Two difficulties came up during the development of the system: the presence of a significant amount of noise in the data and the presence of exceptions linguistically motivated. It is then a challenge for an inductive system to learn rules from this kind of data. This leads us to add a specific mechanism, refinement, which enables learning rules and their exceptions. In the first part of this article we evaluate the usefulness of this device and show that it improves results when learning linguistic structures.In the second part, we explore how to improve the efficiency of the system by using prior knowledge. Since Natural Language is a strongly structured object, it may be important to investigate whether linguistic knowledge can help to make natural language learning more efficiently and accurately. This article presents some experiments demonstrating that linguistic knowledge improves learning. The system has been applied to the shared task of the CoNLL'00 workshop.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {669–693},
numpages = {25},
keywords = {rule induction, chunking, learning exceptions, natural language processing, symbolic learning}
}

@article{10.5555/944790.944821,
author = {Megyesi, Be\'{a}ta},
title = {Shallow Parsing with Pos Taggers and Linguistic Features},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {Three data-driven publicly available part-of-speech taggers are applied to shallow parsing of Swedish texts. The phrase structure is represented by nine types of phrases in a hierarchical structure containing labels for every constituent type the token belongs to in the parse tree. The encoding is based on the concatenation of the phrase tags on the path from lowest to higher nodes. Various linguistic features are used in learning; the taggers are trained on the basis of lexical information only, part-of-speech only, and a combination of both, to predict the phrase structure of the tokens with or without part-of-speech. Special attention is directed to the taggers' sensitivity to different types of linguistic information included in learning, as well as the taggers' sensitivity to the size and the various types of training data sets. The method can be easily transferred to other languages.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {639–668},
numpages = {30},
keywords = {transformation-based learning, part-of-speech taggers, chunking, shallow parsing, maximum entropy learning, hidden Markov models}
}

@article{10.5555/944790.944820,
author = {Zhang, Tong and Damerau, Fred and Johnson, David},
title = {Text Chunking Based on a Generalization of Winnow},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {This paper describes a text chunking system based on a generalization of the Winnow algorithm. We propose a general statistical model for text chunking which we then convert into a classification problem. We argue that the Winnow family of algorithms is particularly suitable for solving classification problems arising from NLP applications, due to their robustness to irrelevant features. However in theory, Winnow may not converge for linearly non-separable data. To remedy this problem, we employ a generalization of the original Winnow method. An additional advantage of the new algorithm is that it provides reliable confidence estimates for its classification predictions. This property is required in our statistical modeling approach. We show that our system achieves state of the art performance in text chunking with less computational cost then previous systems.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {615–637},
numpages = {23}
}

@article{10.5555/944790.944819,
author = {Molina, Antonio and Pla, Ferran},
title = {Shallow Parsing Using Specialized Hmms},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {We present a unified technique to solve different shallow parsing tasks as a tagging problem using a Hidden Markov Model-based approach (HMM). This technique consists of the incorporation of the relevant information for each task into the models. To do this, the training corpus is transformed to take into account this information. In this way, no change is necessary for either the training or tagging process, so it allows for the use of a standard HMM approach. Taking into account this information, we construct a Specialized HMM which gives more complete contextual models. We have tested our system on chunking and clause identification tasks using different specialization criteria. The results obtained are in line with the results reported for most of the relevant state-of-the-art approaches.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {595–613},
numpages = {19},
keywords = {statistical language modeling, text chunking, shallow parsing, specialized HMMs, clause identification}
}

@article{10.5555/944790.944818,
author = {Sang, Erik F. Tjong Kim},
title = {Memory-Based Shallow Parsing},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {We present memory-based learning approaches to shallow parsing and apply these to five tasks: base noun phrase identification, arbitrary base phrase recognition, clause detection, noun phrase parsing and full parsing. We use feature selection techniques and system combination methods for improving the performance of the memory-based learner. Our approach is evaluated on standard data sets and the results are compared with that of other systems. This reveals that our approach works well for base phrase identification while its application towards recognizing embedded structures leaves some room for improvement.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {559–594},
numpages = {36},
keywords = {system combination, memory-based learning, shallow parsing, feature selection}
}

@article{10.5555/944790.944817,
author = {Hammerton, James and Osborne, Miles and Armstrong, Susan and Daelemans, Walter},
title = {Introduction to Special Issue on Machine Learning Approaches to Shallow Parsing},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {This article introduces the problem of partial or shallow parsing (assigning partial syntactic structure to sentences) and explains why it is an important natural language processing (NLP) task. The complexity of the task makes Machine Learning an attractive option in comparison to the handcrafting of rules. On the other hand, because of the same task complexity, shallow parsing makes an excellent benchmark problem for evaluating machine learning algorithms. We sketch the origins of shallow parsing as a specific task for machine learning of language, and introduce the articles accepted for this special issue, a representative sample of current research in this area. Finally, future directions for machine learning of shallow parsing are suggested.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {551–558},
numpages = {8}
}

@article{10.5555/944790.944815,
author = {Genton, Marc G.},
title = {Classes of Kernels for Machine Learning: A Statistics Perspective},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {In this paper, we present classes of kernels for machine learning from a statistics perspective. Indeed, kernels are positive definite functions and thus also covariances. After discussing key properties of kernels, as well as a new formula to construct kernels, we present several important classes of kernels: anisotropic stationary kernels, isotropic stationary kernels, compactly supported kernels, locally stationary kernels, nonstationary kernels, and separable nonstationary kernels. Compactly supported kernels and separable nonstationary kernels are of prime interest because they provide a computational reduction for kernel-based methods. We describe the spectral representation of the various classes of kernels and conclude with a discussion on the characterization of nonlinear maps that reduce nonstationary kernels to either stationarity or local stationarity.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {299–312},
numpages = {14}
}

@article{10.5555/944790.944814,
author = {Downs, Tom and Gates, Kevin E. and Masters, Annette},
title = {Exact Simplification of Support Vector Solutions},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {This paper demonstrates that standard algorithms for training support vector machines generally produce solutions with a greater number of support vectors than are strictly necessary. An algorithm is presented that allows unnecessary support vectors to be recognized and eliminated while leaving the solution otherwise unchanged. The algorithm is applied to a variety of benchmark data sets (for both classification and regression) and in most cases the procedure leads to a reduction in the number of support vectors. In some cases the reduction is substantial.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {293–297},
numpages = {5}
}

@article{10.5555/944790.944813,
author = {Crammer, Koby and Singer, Yoram},
title = {On the Algorithmic Implementation of Multiclass Kernel-Based Vector Machines},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems. Using this notion we cast multiclass categorization problems as a constrained optimization problem with a quadratic objective function. Unlike most of previous approaches which typically decompose a multiclass problem into multiple independent binary classification tasks, our notion of margin yields a direct method for training multiclass predictors. By using the dual of the optimization problem we are able to incorporate kernels with a compact set of constraints and decompose the dual problem into multiple optimization problems of reduced size. We describe an efficient fixed-point algorithm for solving the reduced optimization problems and prove its convergence. We then discuss technical details that yield significant running time improvements for large datasets. Finally, we describe various experiments with our approach comparing it to previously studied kernel-based methods. Our experiments indicate that for multiclass problems we attain state-of-the-art accuracy.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {265–292},
numpages = {28}
}

@article{10.5555/944790.944812,
author = {Fine, Shai and Scheinberg, Katya},
title = {Efficient Svm Training Using Low-Rank Kernel Representations},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {SVM training is a convex optimization problem which scales with the training set size rather than the feature space dimension. While this is usually considered to be a desired quality, in large scale problems it may cause training to be impractical. The common techniques to handle this difficulty basically build a solution by solving a sequence of small scale subproblems. Our current effort is concentrated on the rank of the kernel matrix as a source for further enhancement of the training procedure. We first show that for a low rank kernel matrix it is possible to design a better interior point method (IPM) in terms of storage requirements as well as computational complexity. We then suggest an efficient use of a known factorization technique to approximate a given kernel matrix by a low rank matrix, which in turn will be used to feed the optimizer. Finally, we derive an upper bound on the change in the objective function value based on the approximation error and the number of active constraints (support vectors). This bound is general in the sense that it holds regardless of the approximation method.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {243–264},
numpages = {22}
}

@article{10.5555/944790.944811,
author = {Gentile, Claudio},
title = {A New Approximate Maximal Margin Classification Algorithm},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm p ≥ 2 for a set of linearly separable data. Our algorithm, called ALMA_p (Approximate Large Margin algorithm w.r.t. norm p), takes O( (p-1) / (α2 γ2 ) ) corrections to separate the data with p-norm margin larger than (1-α)γ, where g is the (normalized) p-norm margin of the data. ALMA_p avoids quadratic (or higher-order) programming methods. It is very easy to implement and is as fast as on-line algorithms, such as Rosenblatt's Perceptron algorithm. We performed extensive experiments on both real-world and artificial datasets. We compared ALMA_2 (i.e., ALMA_p with p = 2) to standard Support vector Machines (SVM) and to two incremental algorithms: the Perceptron algorithm and Li and Long's ROMMA. The accuracy levels achieved by ALMA_2 are superior to those achieved by the Perceptron algorithm and ROMMA, but slightly inferior to SVM's. On the other hand, ALMA_2 is quite faster and easier to implement than standard SVM training algorithms. When learning sparse target vectors, ALMA_p with p > 2 largely outperforms Perceptron-like algorithms, such as ALMA_2.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {213–242},
numpages = {30}
}

@article{10.5555/944790.944810,
author = {Pekalska, Elzbieta and Paclik, Pavel and Duin, Robert P. W.},
title = {A Generalized Kernel Approach to Dissimilarity-Based Classification},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {Usually, objects to be classified are represented by features. In this paper, we discuss an alternative object representation based on dissimilarity values. If such distances separate the classes well, the nearest neighbor method offers a good solution. However, dissimilarities used in practice are usually far from ideal and the performance of the nearest neighbor rule suffers from its sensitivity to noisy examples. We show that other, more global classification techniques are preferable to the nearest neighbor rule, in such cases.For classification purposes, two different ways of using generalized dissimilarity kernels are considered. In the first one, distances are isometrically embedded in a pseudo-Euclidean space and the classification task is performed there. In the second approach, classifiers are built directly on distance kernels. Both approaches are described theoretically and then compared using experiments with different dissimilarity measures and datasets including degraded data simulating the problem of missing values.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {175–211},
numpages = {37}
}

@article{10.5555/944790.944809,
author = {Tax, David M. J. and Duin, Robert P. W.},
title = {Uniform Object Generation for Optimizing One-Class Classifiers},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {In one-class classification, one class of data, called the target class, has to be distinguished from the rest of the feature space. It is assumed that only examples of the target class are available. This classifier has to be constructed such that objects not originating from the target set, by definition outlier objects, are not classified as target objects. In previous research the support vector data description (SVDD) is proposed to solve the problem of one-class classification. It models a hypersphere around the target set, and by the introduction of kernel functions, more flexible descriptions are obtained. In the original optimization of the SVDD, two parameters have to be given beforehand by the user. To automatically optimize the values for these parameters, the error on both the target and outlier data has to be estimated. Because no outlier examples are available, we propose a method for generating artificial outliers, uniformly distributed in a hypersphere. An (relative) efficient estimate for the volume covered by the one-class classifiers is obtained, and so an estimate for the outlier error. Results are shown for artificial data and for real world data.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {155–173},
numpages = {19}
}

@article{10.5555/944790.944808,
author = {Manevitz, Larry M. and Yousef, Malik},
title = {One-Class Svms for Document Classification},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {We implemented versions of the SVM appropriate for one-class classification in the context of information retrieval. The experiments were conducted on the standard Reuters data set. For the SVM implementation we used both a version of Schoelkopf et al. and a somewhat different version of one-class SVM based on identifying "outlier" data as representative of the second-class. We report on experiments with different kernels for both of these implementations and with different representations of the data, including binary vectors, tf-idf representation and a modification called "Hadamard" representation. Then we compared it with one-class versions of the algorithms prototype (Rocchio), nearest neighbor, naive Bayes, and finally a natural one-class neural network classification method based on "bottleneck" compression generated filters.The SVM approach as represented by Schoelkopf was superior to all the methods except the neural network one, where it was, although occasionally worse, essentially comparable. However, the SVM methods turned out to be quite sensitive to the choice of representation and kernel in ways which are not well understood; therefore, for the time being leaving the neural network approach as the most robust.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {139–154},
numpages = {16}
}

@article{10.5555/944790.944807,
author = {Ben-Hur, Asa and Horn, David and Siegelmann, Hava T. and Vapnik, Vladimir},
title = {Support Vector Clustering},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {We present a novel clustering method using the approach of support vector machines. Data points are mapped by means of a Gaussian kernel to a high dimensional feature space, where we search for the minimal enclosing sphere. This sphere, when mapped back to data space, can separate into several components, each enclosing a separate cluster of points. We present a simple algorithm for identifying these clusters. The width of the Gaussian kernel controls the scale at which the data is probed while the soft margin constant helps coping with outliers and overlapping clusters. The structure of a dataset is explored by varying the two parameters, maintaining a minimal number of support vectors to assure smooth cluster boundaries. We demonstrate the performance of our algorithm on several datasets.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {125–137},
numpages = {13}
}

@article{10.5555/944790.944806,
author = {Rosipal, Roman and Trejo, Leonard J.},
title = {Kernel Partial Least Squares Regression in Reproducing Kernel Hilbert Space},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
abstract = {A family of regularized least squares regression models in a Reproducing Kernel Hilbert Space is extended by the kernel partial least squares (PLS) regression model. Similar to principal components regression (PCR), PLS is a method based on the projection of input (explanatory) variables to the latent variables (components). However, in contrast to PCR, PLS creates the components by modeling the relationship between input and output variables while maintaining most of the information in the input variables. PLS is useful in situations where the number of explanatory variables exceeds the number of observations and/or a high level of multicollinearity among those variables is assumed. Motivated by this fact we will provide a kernel PLS algorithm for construction of nonlinear regression models in possibly high-dimensional feature spaces.We give the theoretical description of the kernel PLS algorithm and we experimentally compare the algorithm with the existing kernel PCR and kernel ridge regression techniques. We will demonstrate that on the data sets employed kernel PLS achieves the same results as kernel PCR but uses significantly fewer, qualitatively different components.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {97–123},
numpages = {27}
}

@article{10.5555/944790.944805,
author = {Cristianini, Nello and Shawe-Taylor, John and Williamson, Robert C.},
title = {Introduction to the Special Issue on Kernel Methods},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {95–96},
numpages = {2}
}

@article{10.1162/153244302760200713,
author = {Zhang, Tong},
title = {Covering Number Bounds of Certain Regularized Linear Function Classes},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200713},
doi = {10.1162/153244302760200713},
abstract = {Recently, sample complexity bounds have been derived for problems involving linear functions such as neural networks and support vector machines. In many of these theoretical studies, the concept of covering numbers played an important role. It is thus useful to study covering numbers for linear function classes. In this paper, we investigate two closely related methods to derive upper bounds on these covering numbers. The first method, already employed in some earlier studies, relies on the so-called Maurey's lemma; the second method uses techniques from the mistake bound framework in online learning. We compare results from these two methods, as well as their consequences in some learning formulations.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {527–550},
numpages = {24},
keywords = {covering numbers, sparse approximation, mistake bounds, learning sample complexity}
}

@article{10.1162/153244302760200704,
author = {Bousquet, Olivier and Elisseeff, Andr\'{e}},
title = {Stability and Generalization},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200704},
doi = {10.1162/153244302760200704},
abstract = {We define notions of stability for learning algorithms and show how to use these notions to derive generalization error bounds based on the empirical error and the leave-one-out error. The methods we use can be applied in the regression framework as well as in the classification one when the classifier is obtained by thresholding a real-valued function. We study the stability properties of large classes of learning algorithms such as regularization based algorithms. In particular we focus on Hilbert space regularization and Kullback-Leibler regularization. We demonstrate how to apply the results to SVM for regression and classification.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {499–526},
numpages = {28}
}

@article{10.1162/153244302760200696,
author = {Chickering, David Maxwell},
title = {Learning Equivalence Classes of Bayesian-Network Structures},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200696},
doi = {10.1162/153244302760200696},
abstract = {Two Bayesian-network structures are said to be  equivalent if the set of distributions that can be represented with one of those structures is identical to the set of distributions that can be represented with the other. Many scoring criteria that are used to learn Bayesian-network structures from data are  score equivalent; that is, these criteria do not distinguish among networks that are equivalent. In this paper, we consider using a score equivalent criterion in conjunction with a heuristic search algorithm to perform model selection or model averaging. We argue that it is often appropriate to search among equivalence classes of network structures as opposed to the more common approach of searching among individual Bayesian-network structures. We describe a convenient graphical representation for an equivalence class of structures, and introduce a set of operators that can be applied to that representation by a search algorithm to move among equivalence classes. We show that our equivalence-class operators can be scored locally, and thus share the computational efficiency of traditional operators defined for individual structures. We show experimentally that a greedy model-selection algorithm using our representation yields slightly higher-scoring structures than the traditional approach without any additional time overhead, and we argue that more sophisticated search algorithms are likely to benefit much more.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {445–498},
numpages = {54}
}

@article{10.1162/153244302760200687,
author = {Lodhi, Huma and Saunders, Craig and Shawe-Taylor, John and Cristianini, Nello and Watkins, Chris},
title = {Text Classification Using String Kernels},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200687},
doi = {10.1162/153244302760200687},
abstract = {We propose a novel approach for categorizing text documents based on the use of a special kernel. The kernel is an inner product in the feature space generated by all subsequences of length k. A subsequence is any ordered sequence of k characters occurring in the text though not necessarily contiguously. The subsequences are weighted by an exponentially decaying factor of their full length in the text, hence emphasising those occurrences that are close to contiguous. A direct computation of this feature vector would involve a prohibitive amount of computation even for modest values of k, since the dimension of the feature space grows exponentially with k. The paper describes how despite this fact the inner product can be efficiently evaluated by a dynamic programming technique. Experimental comparisons of the performance of the kernel compared with a standard word feature space kernel (Joachims, 1998) show positive results on modestly sized datasets. The case of contiguous subsequences is also considered for comparison with the subsequences kernel with different decay factors. For larger documents and datasets the paper introduces an approximation technique that is shown to deliver good approximations efficiently for large datasets.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {419–444},
numpages = {26},
keywords = {text classification, kernels and support vector machines, approximating kernels, string subsequence kernel}
}

@article{10.1162/153244302760200678,
author = {Meek, Christopher and Thiesson, Bo and Heckerman, David},
title = {The Learning-Curve Sampling Method Applied to Model-Based Clustering},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200678},
doi = {10.1162/153244302760200678},
abstract = {We examine the learning-curve sampling method, an approach for applying machine-learning algorithms to large data sets. The approach is based on the observation that the computational cost of learning a model increases as a function of the sample size of the training data, whereas the accuracy of a model has diminishing improvements as a function of sample size. Thus, the learning-curve sampling method monitors the increasing costs and performance as larger and larger amounts of data are used for training, and terminates learning when future costs outweigh future benefits. In this paper, we formalize the learning-curve sampling method and its associated cost-benefit tradeoff in terms of decision theory. In addition, we describe the application of the learning-curve sampling method to the task of model-based clustering via the expectation-maximization (EM) algorithm. In experiments on three real data sets, we show that the learning-curve sampling method produces models that are nearly as accurate as those trained on complete data sets, but with dramatically reduced learning times. Finally, we describe an extension of the basic learning-curve approach for model-based clustering that results in an additional speedup. This extension is based on the observation that the shape of the learning curve for a given model and data set is roughly independent of the number of EM iterations used during training. Thus, we run EM for only a few iterations to decide how many cases to use for training, and then run EM to full convergence once the number of cases is selected.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {397–418},
numpages = {22},
keywords = {learning-curve sampling method, sampling, clustering, scalability, decision theory}
}

@article{10.1162/153244302760200669,
author = {Bshouty, Nader H. and Feldman, Vitaly},
title = {On Using Extended Statistical Queries to Avoid Membership Queries},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200669},
doi = {10.1162/153244302760200669},
abstract = {The Kushilevitz-Mansour (KM) algorithm is an algorithm that finds all the "large" Fourier coefficients of a Boolean function. It is the main tool for learning decision trees and DNF expressions in the PAC model with respect to the uniform distribution. The algorithm requires access to the membership query (MQ) oracle. The access is often unavailable in learning applications and thus the KM algorithm cannot be used. We significantly weaken this requirement by producing an analogue of the KM algorithm that uses extended statistical queries (SQ) (SQs in which the expectation is taken with respect to a distribution given by a learning algorithm). We restrict a set of distributions that a learning algorithm may use for its statistical queries to be a set of product distributions with each bit being 1 with probability ρ, 1/2 or 1-ρ for a constant 1/2 > ρ > 0 (we denote the resulting model by SQ-Dρ). Our analogue finds all the "large" Fourier coefficients of degree lower than clog(n) (we call it the Bounded Sieve (BS)). We use BS to learn decision trees and by adapting Freund's boosting technique we give an algorithm that learns DNF in SQ-Dρ. An important property of the model is that its algorithms can be simulated by MQs with persistent noise. With some modifications BS can also be simulated by MQs with product attribute noise (i.e., for a query x oracle changes every bit of x with some constant probability and calculates the value of the target function at the resulting point) and classification noise. This implies learnability of decision trees and weak learnability of DNF with this non-trivial noise. In the second part of this paper we develop a characterization for learnability with these extended statistical queries. We show that our characterization when applied to SQ-Dρ is tight in terms of learning parity functions. We extend the result given by Blum et al. by proving that there is a class learnable in the PAC model with random classification noise and not learnable in SQ-Dρ.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {359–395},
numpages = {37}
}

@article{10.1162/153244302760200650,
author = {Cannon, Adam and Ettinger, J. Mark and Hush, Don and Scovel, Clint},
title = {Machine Learning with Data Dependent Hypothesis Classes},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200650},
doi = {10.1162/153244302760200650},
abstract = {We extend the VC theory of statistical learning to data dependent spaces of classifiers. This theory can be viewed as a decomposition of classifier design into two components; the first component is a restriction to a data dependent hypothesis class and the second is empirical risk minimization within that class. We define a measure of complexity for data dependent hypothesis classes and provide data dependent versions of bounds on error deviance and estimation error. We also provide a structural risk minimization procedure over data dependent hierarchies and prove consistency. We use this theory to provide a framework for studying the trade-offs between performance and computational complexity in classifier design. As a consequence we obtain a new family of classifiers with dimension independent performance bounds and efficient learning procedures.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {335–358},
numpages = {24},
keywords = {computational learning theory, Shatter coefficient, empirical process theory, structural risk minimization, classification}
}

@article{10.1162/153244302760200641,
author = {Zhang, Tong and Iyengar, Vijay S.},
title = {Recommender Systems Using Linear Classifiers},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302760200641},
doi = {10.1162/153244302760200641},
abstract = {Recommender systems use historical data on user preferences and other available data on users (for example, demographics) and items (for example, taxonomy) to predict items a new user might like. Applications of these methods include recommending items for purchase and personalizing the browsing experience on a web-site. Collaborative filtering methods have focused on using just the history of user preferences to make the recommendations. These methods have been categorized as memory-based if they operate over the entire data to make predictions and as model-based if they use the data to build a model which is then used for predictions. In this paper, we propose the use of linear classifiers in a model-based recommender system. We compare our method with another model-based method using decision trees and with memory-based methods using data from various domains. Our experimental results indicate that these linear models are well suited for this application. They outperform a commonly proposed memory-based method in accuracy and also have a better tradeoff between off-line and on-line computational requirements.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {313–334},
numpages = {22},
keywords = {collaborative filtering, decision trees, recommender systems, linear models, unbalanced data}
}

@article{10.1162/153244302760185252,
author = {Steinwart, Ingo},
title = {On the Influence of the Kernel on the Consistency of Support Vector Machines},
year = {2002},
issue_date = {3/1/2002},
publisher = {JMLR.org},
volume = {2},
issn = {1532-4435},
url = {https://doi.org/10.1162/153244302

license_type: permissive

branch_name: refs/heads/main

extension: bib