Machine learning for sequential data: A review <s> Feature Selection and Long-Distance Interactions <s> Inspired by the information theoretic idea of minimum description length, we add a term to the back propagation cost function that penalizes network complexity. We give the details of the procedure, called weight-elimination, describe its dynamics, and clarify the meaning of the parameters involved. From a Bayesian perspective, the complexity term can be usefully interpreted as an assumption about prior distribution of the weights. We use this procedure to predict the sunspot time series and the notoriously noisy series of currency exchange rates. <s> BIB001 </s> Machine learning for sequential data: A review <s> Feature Selection and Long-Distance Interactions <s> From the Publisher: ::: Classifier systems play a major role in machine learning and knowledge-based systems, and Ross Quinlan's work on ID3 and C4.5 is widely acknowledged to have made some of the most significant contributions to their development. This book is a complete guide to the C4.5 system as implemented in C for the UNIX environment. It contains a comprehensive guide to the system's use , the source code (about 8,800 lines), and implementation notes. The source code and sample datasets are also available on a 3.5-inch floppy diskette for a Sun workstation. ::: ::: C4.5 starts with large sets of cases belonging to known classes. The cases, described by any mixture of nominal and numeric properties, are scrutinized for patterns that allow the classes to be reliably discriminated. These patterns are then expressed as models, in the form of decision trees or sets of if-then rules, that can be used to classify new cases, with emphasis on making the models understandable as well as accurate. The system has been applied successfully to tasks involving tens of thousands of cases described by hundreds of properties. The book starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting. Advantages and disadvantages of the C4.5 approach are discussed and illustrated with several case studies. ::: ::: This book and software should be of interest to developers of classification-based intelligent systems and to students in machine learning and expert systems courses. <s> BIB002 </s> Machine learning for sequential data: A review <s> Feature Selection and Long-Distance Interactions <s> Selecting a good model of a set of input points by cross validation is a computationally intensive process, especially if the number of possible models or the number of training points is high. Techniques such as gradient descent are helpful in searching through the space of models, but problems such as local minima, and more importantly, lack of a distance metric between various models reduce the applicability of these search methods. Hoeffding Races is a technique for finding a good model for the data by quickly discarding bad models, and concentrating the computational effort at differentiating between the better ones. This paper focuses on the special case of leave-one-out cross validation applied to memory-based learning algorithms, but we also argue that it is applicable to any class of model selection problems. <s> BIB003 </s> Machine learning for sequential data: A review <s> Feature Selection and Long-Distance Interactions <s> In this paper, we examine a method for feature subset selection based on Information Theory. Initially, a framework for defining the theoretically optimal, but computationally intractable, method for feature subset selection is presented. We show that our goal should be to eliminate a feature if it gives us little or no additional information beyond that subsumed by the remaining features. In particular, this will be the case for both irrelevant and redundant features. We then give an efficient algorithm for feature selection which computes an approximation to the optimal feature selection criterion. The conditions under which the approximate algorithm is successful are examined. Empirical results are given on a number of data sets, showing that the algorithm effectively handles datasets with a very large number of features. <s> BIB004 </s> Machine learning for sequential data: A review <s> Feature Selection and Long-Distance Interactions <s> Abstract In the feature subset selection problem, a learning algorithm is faced with the problem of selecting a relevant subset of features upon which to focus its attention, while ignoring the rest. To achieve the best possible performance with a particular learning algorithm on a particular training set, a feature subset selection method should consider how the algorithm and the training set interact. We explore the relation between optimal feature subset selection and relevance. Our wrapper method searches for an optimal feature subset tailored to a particular algorithm and a domain. We study the strengths and weaknesses of the wrapper approach and show a series of improved designs. We compare the wrapper approach to induction without feature subset selection and to Relief, a filter approach to feature subset selection. Significant improvement in accuracy is achieved for some datasets for the two families of induction algorithms used: decision trees and Naive-Bayes. <s> BIB005 </s> Machine learning for sequential data: A review <s> Feature Selection and Long-Distance Interactions <s> This book is the first comprehensive introduction to Support Vector Machines (SVMs), a new generation learning system based on recent advances in statistical learning theory. The book also introduces Bayesian analysis of learning and relates SVMs to Gaussian Processes and other kernel based learning methods. SVMs deliver state-of-the-art performance in real-world applications such as text categorisation, hand-written character recognition, image classification, biosequences analysis, etc. Their first introduction in the early 1990s lead to a recent explosion of applications and deepening theoretical analysis, that has now established Support Vector Machines along with neural networks as one of the standard tools for machine learning and data mining. Students will find the book both stimulating and accessible, while practitioners will be guided smoothly through the material required for a good grasp of the theory and application of these techniques. The concepts are introduced gradually in accessible and self-contained stages, though in each stage the presentation is rigorous and thorough. Pointers to relevant literature and web sites containing software ensure that it forms an ideal starting point for further study. Equally the book will equip the practitioner to apply the techniques and an associated web site will provide pointers to updated literature, new applications, and on-line software. <s> BIB006
Any method for sequential supervised learning must employ some form of divideand-conquer to break the overall problem of predicting y i given x i into subproblems of predicting individual output labels y i,t given some subset of information from x i (and perhaps other predicted values y i,u ). One of the central problems of sequential supervised learning is to identify the relevant information subset for making accurate predictions. In standard supervised learning, this is known as the feature selection problem, and there are four primary strategies for solving it. The first strategy, known as the wrapper approach BIB005 , is to generate various subsets of features and evaluate them by running the learning algorithm and measuring the accuracy of the resulting classifier (e.g., via cross-validation or by applying the Akaiki Information Criterion). The feature subsets are typically generated by forward selection (starting with single features and progressively adding one feature at a time) or backward elimination (starting with all of the features and progressively removing one feature at a time). For some learning algorithms, such as linear regression, this can be implemented very efficiently. The second strategy is to include all possible features in the model, but to place a penalty on the values of parameters in the fitted model. This causes the parameters associated with useless features to become very small (perhaps even zero). Examples of this approach include ridge regression  , neural network weight elimination BIB001 , and L 1 -norm support vector machines (SVMs; BIB006 ). The third strategy is to compute some measure of feature relevance and remove low-scoring features. One of the simplest measures is the mutual information between a feature and the class. This (or similar measures) forms the basis of recursive-partioning algorithms for growing classification and regression trees. These methods incorporate the choice of relevant features into the treegrowing process  BIB002 . Unfortunately, this measure does not capture interactions between features. Several methods have been developed that identify such interactions including RELIEFF  , Markov blankets BIB004 , and feature racing BIB003 . The fourth strategy is to first fit a simple model and then analyze the fitted model to identify the relevant features. For example, Chow and Liu  describe an efficient algorithm for fitting a tree-structured Bayesian network to a data set. This network can then be analyzed to remove features that have low influence on the class. Kristin Bennett (personal communication, 2001) fits L 1 -norm SVMs to drug binding data to remove irrelevant features prior to fitting a more complex SVM regression model. In sequential supervised learning, most authors have assumed that a fixedsized neighborhood of features is relevant for predicting each output value. For example, suppose we assume a neighborhood of size 3. Then we will employ x i,t−1 , x i,t , and x i,t+1 to predict y i,t . However, this has two drawbacks. First, not all of the features in each feature vector {x i,u } t+1 u=t−1 are necessarily relevant. Second, there may be longer-range interactions that are missed. For example, consider the problem of predicting the pronunciation of English words from their spelling. The only difference between the words "thought" and "though" is the final "t", yet this influences the pronunciation of the initial "th" (changing it from unvoiced to voiced). An even more extreme case is the pair "photograph" and "photography" in which the final "y" changes the pronunciation of every vowel in the word. Of the four feature-selection strategies discussed above, it is unlikely that the first two are feasible for sequential supervised learning. There are so many potential features to consider in a long sequence, that a direct search of possible feature subsets becomes completely intractable (even with greedy algorithms). The third and fourth approaches are more promising, but with long sequences, they still raise the possibility of overfitting. Hence, any successful methodology for feature selection (and for handling long distance interactions) will probably need to combine human expertise with statistical techniques rather than applying statistical techniques alone.