CiteULike: sdvillal's library [848 articles]

An information-theoretic perspective of tf-idf measures

Akiko Aizawa — 2006-01-10T19:08:43-00:00

Information Processing & Management, Vol. 39, No. 1. (January 2003), pp. 45-65.

Modeling word burstiness using the Dirichlet distribution

Rasmus Madsen — 2008-06-11T15:02:47-00:00

(2005), pp. 545-552.

Clustering documents with an exponential-family approximation of the Dirichlet compound multinomial distribution

Charles Elkan — 2008-06-11T15:01:53-00:00

(2006), pp. 289-296.

Building Text Classifiers Using Positive and Unlabeled Examples

Bing Liu — 2008-06-09T09:17:14-00:00

(2003)

Addressing the curse of imbalanced training sets: one-sided selection

Miroslav Kubat — 2008-03-13T12:23:40-00:00

(1997), pp. 179-186.

Adding examples of the majority class to the training set can have a detrimental effect on the learner's behavior: noisy or otherwise unreliable examples from the majority class can overwhelm the minority class. The paper discusses criteria to evaluate the utility of classifiers induced from such imbalanced training sets, gives explanation of the poor behavior of some learners under these circumstances, and suggests as a solution a simple technique called one-sided selection of...

A practical method for the software fault-prediction

Zhan Li — 2008-06-03T05:41:52-00:00

Information Reuse and Integration, 2007. IRI 2007. IEEE International Conference on (2007), pp. 659-666.

In the paper, a novel machine learning method, SimBoost, is proposed to handle the software fault-prediction problem when highly skewed datasets are used. Although the method, proved by empirical results, can make the datasets much more balanced, the accuracy of the prediction is still not satisfactory. Therefore, a fuzzy-based representation of the software module fault state has been presented instead of the original faulty/non-faulty one. Several experiments were conducted using datasets from NASA Metrics Data Program. The discussion of the results of experiments is provided.

Generalization from Observed to Unobserved Features by Clustering

Eyal Krupka — 2008-03-25T20:06:19-00:00

Journal of Machine Learning Research, Vol. 9 (March 2008), pp. 339-370.

We argue that when objects are characterized by many attributes, clustering them on the basis of a random subset of these attributes can capture information on the unobserved attributes as well. Moreover, we show that under mild technical conditions, clustering the objects on the basis of such a random subset performs almost as well as clustering with the full attribute set. We prove finite sample generalization theorems for this novel learning scheme that extends analogous results from the supervised learning setting. We use our framework to analyze generalization to unobserved features of two well-known clustering algorithms: k-means and the maximum likelihood multinomial mixture model. The scheme is demonstrated for collaborative filtering of users with movie ratings as attributes and document clustering with words as attributes.

Max-margin Classification of Data with Absent Features

Gal Chechik — 2008-06-02T09:30:24-00:00

Journal of Machine Learning Research, Vol. 9 (January 2008), pp. 1-21.

We consider the problem of learning classifiers in structured domains, where some objects have a subset of features that are inherently absent due to complex relationships between the features. Unlike the case where a feature exists but its value is not observed, here we focus on the case where a feature may not even exist (structurally absent) for some of the samples. The common approach for handling missing features in discriminative models is to first complete their unknown values, and then use a standard classification procedure over the completed data. This paper focuses on features that are known to be non-existing, rather than have an unknown value. We show how incomplete data can be classified directly without any completion of the missing features using a max-margin learning framework. We formulate an objective function, based on the geometric interpretation of the margin, that aims to maximize the margin of each sample in its own relevant subspace. In this formulation, the linearly separable case can be transformed into a binary search over a series of second order cone programs (SOCP), a convex problem that can be solved efficiently. We also describe two approaches for optimizing the general case: an approximation that can be solved as a standard quadratic program (QP) and an iterative approach for solving the exact problem. By avoiding the pre-processing phase in which the data is completed, both of these approaches could offer considerable computational savings. More importantly, we show that the elegant handling of missing values by our approach allows it to both outperform other methods when the missing values have non-trivial structure, and be competitive with other methods when the values are missing at random. We demonstrate our results on several standard benchmarks and two real-world problems: edge prediction in metabolic pathways, and automobile detection in natural images.

Computational Methods of Feature Selection (Chapman & Hall/Crc Data Mining and Knowledge Discovery Series)

2008-05-21T16:00:30-00:00

(29 October 2007)

Due to increasing demands for dimensionality reduction, research on feature selection has deeply and widely expanded into many fields, including computational statistics, pattern recognition, machine learning, data mining, and knowledge discovery. Highlighting current research issues, **Computational Methods of Feature Selection** introduces the basic concepts and principles, state-of-the-art algorithms, and novel applications of this tool. The book begins by exploring unsupervised, randomized, and causal feature selection. It then reports on some recent results of empowering feature selection, including active feature selection, decision-border estimate, the use of ensembles with independent probes, and incremental feature selection. This is followed by discussions of weighting and local methods, such as the ReliefF family, _k_-means clustering, local feature relevance, and a new interpretation of Relief. The book subsequently covers text classification, a new feature selection score, and both constraint-guided and aggressive feature selection. The final section examines applications of feature selection in bioinformatics, including feature construction as well as redundancy-, ensemble-, and penalty-based feature selection. Through a clear, concise, and coherent presentation of topics, this volume systematically covers the key concepts, underlying principles, and inventive applications of feature selection, illustrating how this powerful tool can efficiently harness massive, high-dimensional data and turn it into valuable, reliable information.

The Pyramid Match Kernel: Efficient Learning with Sets of Features

Kristen Grauman — 2008-05-21T11:49:49-00:00

Journal of Machine Learning Research, Vol. 8 (April 2007), pp. 725-760.

In numerous domains it is useful to represent a single example by the set of the local features or parts that comprise it. However, this representation poses a challenge to many conventional machine learning techniques, since sets may vary in cardinality and elements lack a meaningful ordering. Kernel methods can learn complex functions, but a kernel over unordered set inputs must somehow solve for correspondences---generally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function called the pyramid match that measures partial match similarity in time linear in the number of features. The pyramid match maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in order to find implicit correspondences based on the finest resolution histogram cell where a matched pair first appears. We show the pyramid match yields a Mercer kernel, and we prove bounds on its error relative to the optimal partial matching cost. We demonstrate our algorithm on both classification and regression tasks, including object recognition, 3-D human pose inference, and time of publication estimation for documents, and we show that the proposed method is accurate and significantly more efficient than current approaches.

Feature selection for text categorization on imbalanced data

Zhaohui Zheng — 2008-05-21T09:15:20-00:00

SIGKDD Explor. Newsl., Vol. 6, No. 1. (June 2004), pp. 80-89.

An Extensive Empirical Study of Feature Selection Metrics for Text Classification

George Forman — 2007-11-14T20:42:55-00:00

Journal of Machine Learning Research, Vol. 3 (March 2003), pp. 1289-1305.

Machine learning for text classification is the cornerstone of document categorization, news filtering, document routing, and personalization. In text domains, effective feature selection is essential to make the learning task efficient and more accurate. This paper presents an empirical comparison of twelve feature selection methods (e.g. Information Gain) evaluated on a benchmark of 229 text classification problem instances that were gathered from Reuters, TREC, OHSUMED, etc. The results are analyzed from multiple goal perspectives-accuracy, F-measure, precision, and recall-since each is appropriate in different situations. The results reveal that a new feature selection metric we call 'Bi-Normal Separation' (BNS), outperformed the others by a substantial margin in most situations. This margin widened in tasks with high class skew, which is rampant in text classification problems and is particularly challenging for induction algorithms. A new evaluation methodology is offered that focuses on the needs of the data mining practitioner faced with a single dataset who seeks to choose one (or a pair of) metrics that are most likely to yield the best performance. From this perspective, BNS was the top single choice for all goals except precision, for which Information Gain yielded the best result most often. This analysis also revealed, for example, that Information Gain and Chi-Squared have correlated failures, and so they work poorly together. When choosing optimal pairs of metrics for each of the four performance goals, BNS is consistently a member of the pair---e.g., for greatest recall, the pair BNS + F1-measure yielded the best performance on the greatest number of tasks by a considerable margin.

Phase transitions and the search problem

Tad Hogg — 2008-05-14T13:39:17-00:00

Artificial Intelligence, Vol. 81, No. 1-2. (March 1996), pp. 1-15.

We describe how techniques that were originally developed in statistical mechanics can be applied to search problems that arise commonly in artificial intelligence. This approach is useful for understanding the typical behavior of classes of problems. In particular, these techniques predict that abrupt changes in computational cost, analogous to physical phase transitions, should occur universally, as heuristic effectiveness or search space topology is varied. We also present a number of open questions raised by these studies.

The Design and Analysis of an Algorithm Portfolio for SAT

Lin Xu — 2008-05-13T08:11:57-00:00

Principles and Practice of Constraint Programming – CP 2007 (2007), pp. 712-727.

It has been widely observed that there is no “dominant” SAT solver; instead, different solvers perform best on different instances. Rather than following the traditional approach of choosing the best solver for a given class of instances, we advocate making this decision online on a per-instance basis. Building on previous work, we describe a per-instance solver portfolio for SAT, SATzilla-07, which uses so-called empirical hardness models to choose among its constituent solvers. We leverage new model-building techniques such as censored sampling and hierarchical hardness models, and demonstrate the effectiveness of our techniques by building a portfolio of state-of-the-art SAT solvers and evaluating it on several widely-studied SAT data sets. Overall, we show that our portfolio significantly outperforms its constituent algorithms on every data set. Our approach has also proven itself to be effective in practice: in the 2007 SAT competition, SATzilla-07 won three gold medals, one silver, and one bronze; it is available online at http://www.cs.ubc.ca/labs/beta/Projects/SATzilla .

Off-the-peg and bespoke classifiers for fraud detection

Piotr Juszczak — 2008-05-12T07:36:53-00:00

Computational Statistics & Data Analysis, Vol. 52, No. 9. (15 May 2008), pp. 4521-4532.

Detecting fraudulent plastic card transactions is an important and challenging problem. The challenges arise from a number of factors including the sheer volume of transactions financial institutions have to process, the asynchronous and heterogeneous nature of transactions, and the adaptive behaviour of fraudsters. In this fraud detection problem the performance of a supervised two-class classification approach is compared with performance of an unsupervised one-class classification approach. Attention is focussed primarily on one-class classification approaches. Useful representations of transaction records, and ways of combining different one-class classifiers are described. Assessment of performance for such problems is complicated by the need for timely decision making. Performance assessment measures are discussed, and the performance of a number of one- and two-class classification methods is assessed using two large, real world personal banking data sets.

Variational Extensions to EM and Multinomial PCA

Wray Buntine — 2008-05-07T10:01:17-00:00

(2002), pp. 23-34.

Scale-sensitive dimensions, uniform convergence, and learnability

Noga Alon — 2008-04-30T12:29:38-00:00

J. ACM, Vol. 44, No. 4. (July 1997), pp. 615-631.

Reliable Reasoning: Induction and Statistical Learning Theory (Jean Nicod Lectures)

Gilbert Harman — 2008-04-30T11:55:19-00:00

(01 May 2007)

In Reliable Reasoning, Gilbert Harman and Sanjeev Kulkarni--a philosopher and an engineer--argue that philosophy and cognitive science can benefit from statistical learning theory (SLT), the theory that lies behind recent advances in machine learning. The philosophical problem of induction, for example, is in part about the reliability of inductive reasoning, where the reliability of a method is measured by its statistically expected percentage of errors--a central topic in SLT. After discussing philosophical attempts to evade the problem of induction, Harman and Kulkarni provide an admirably clear account of the basic framework of SLT and its implications for inductive reasoning. They explain the Vapnik-Chervonenkis (VC) dimension of a set of hypotheses and distinguish two kinds of inductive reasoning, describing fundamental results about the power and limits of those methods in terms of the VC-dimension of the hypotheses being considered. The VC-dimension is found to be superior to a related measure proposed by Karl Popper, and shown not to correspond exactly to ordinary notions of simplicity. The authors discuss various topics in machine learning, including nearest-neighbor methods, neural networks, and support vector machines. Finally, they describe transductive reasoning and suggest possible new models of human reasoning suggested by developments in SLT.

Tutorial on Practical Prediction Theory for Classification

John Langford — 2008-04-24T11:35:10-00:00

Journal of Machine Learning Research, Vol. 6 (March 2005), pp. 273-306.

We discuss basic prediction theory and its impact on classification success evaluation, implications for learning algorithm design, and uses in learning algorithm execution. This tutorial is meant to be a comprehensive compilation of results which are both theoretically rigorous and quantitatively useful.

Learning over Sets using Kernel Principal Angles

Lior Wolf — 2008-04-23T10:12:18-00:00

Journal of Machine Learning Research, Vol. 4 (October 2003), pp. 913-931.

Abduction and Induction: Essays on their Relation and Integration (Applied Logic Series)

2008-04-20T19:18:41-00:00

(30 April 2000)

From the very beginning of their investigation of human reasoning, philosophers have identified two other forms of reasoning, besides deduction, which we now call abduction and induction. Deduction is now fairly well understood, but abduction and induction have eluded a similar level of understanding. The papers collected here address the relationship between abduction and induction and their possible integration. The approach is sometimes philosophical, sometimes that of pure logic, and some papers adopt the more task-oriented approach of AI. The book will command the attention of philosophers, logicians, AI researchers and computer scientists in general.

Smart Inductive Generalizations are Abductions

J Josephson — 2008-04-20T19:05:03-00:00

This paper describes abduction as `inference to the best explanation' and argues that "smart" inductive generalizations are a special case of abductions. Along the way it argues that some good explanations are not proofs and some proofs are not explanations, concluding that explanations are not deductive proofs in any particularly interesting sense. An attractive alternative is that explanations are assignments of causal responsibility. Smart inductive generalizations can then be seen to be...

Integrating abduction and induction in machine learning

R Mooney — 2008-04-20T19:02:30-00:00

(1997)

This paper discusses the integration of traditional abductive and inductive reasoning methods in the development of machine learning systems. In particular, the paper discusses our recent work in two areas: 1) The use of traditional abductive methods to propose revisions during theory refinement, where an existing knowledge base is modified to make it consistent with a set of empirical data; and 2) The use of inductive learning methods to automatically acquire from examples a diagnostic...

Combining Labeled and Unlabeled Data with Co-training

Avrim Blum — 2005-03-25T18:29:37-00:00

(1998)

We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a problem setting motivated by the task of learning to classify web pages, in which the description of each example can be partitioned into two distinct views. For example, the description of a web page can be partitioned into the words occurring on that page, and the words occurring in hyperlinks that point to...

Latent Dirichlet Allocation

David Blei — 2007-11-19T20:26:58-00:00

Journal of Machine Learning Research, Vol. 3 (January 2003), pp. 993-1022.

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.

A selective sampling approach to active feature selection

Huan Liu — 2008-03-28T15:57:09-00:00

Artif. Intell., Vol. 159, No. 1-2. (2004), pp. 49-74.

Ensembles of nested dichotomies for multi-class problems

Eibe Frank — 2008-04-16T11:45:32-00:00

(2004)

Semisupervised learning using feature selection based on maximum density subgraphs

Yoshiyuki Nakatani — 2008-04-16T09:01:11-00:00

Systems and Computers in Japan, Vol. 38, No. 9. (2007), pp. 32-43.

In machine learning tasks on large-scale datasets, the labeled data essential to the classification are not always sufficient, which degrades the learning accuracy. Meanwhile, unlabeled data are always abundant. Hence, semisupervised learning which uses both unlabeled and labeled data to improve the learning accuracy is currently of great interest. In this paper, we use a graph to represent the underlying distribution of both labeled and unlabeled data and split it by using multiway cut to classify unlabeled data. Additionally, we propose a graph-based feature selection algorithm to improve the learning accuracy of our graph-based semisupervised learning algorithm. In our algorithm, we first propose an evaluation criterion for the attribute relevance using the graph density. Then, we extract the relevant attribute subset by finding the clique on the graph where each vertex stands for the attribute and each edge stands for the relevance of a feature pair. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(9): 32-43, 2007; Published online in Wiley InterScience (). DOI 10.1002/scj.20757

Less is More: Compact Matrix Decomposition for Large Sparse Graphs

Jimeng Sun — 2008-04-16T08:22:34-00:00

(2007)

Masquerader Detection Using OCLEP: One-Class Classification Using Length Statistics of Emerging Patterns

Lijun Chen — 2008-04-15T10:24:41-00:00

Web-Age Information Management Workshops, 2006. WAIM '06. Seventh International Conference on (2006), pp. 5-5.

We introduce a new method for masquerader detection that only uses a user¿s own data for training, called Oneclass Classification using Length statistics of Emerging Patterns (OCLEP). Emerging patterns (EPs) are patterns whose support increases from one dataset/class to another with a big ratio, and have been very useful in earlier studies. OCLEP classifies a case T as self or masquerader by using the average length of EPs obtained by contrasting T against sets of samples of a user¿s normal data. It is based on the observation that one needs long EPs to differentiate instances from a common class, but needs short EPs to differentiate instances from different classes. OCLEP has two novel features: for training it uses EPs mined from just the self class; for classification it uses the length statistics instead of the EPs themselves. Experiments show that OCLEP can achieve very good accuracy while keeping the false positive rate low, it achieves slightly better area-under-ROC-curve than SVM, and it can achieve good results when other approaches can not. OCLEP requires little effort in choosing parameters; the SVM requires significant tuning and it is hard to reach the theoretical optimal result. These features imply that OCLEP is a good complementary component for a robust masquerader detection system, even though its average performance in false positive rate is not as good as SVM¿s.

Matrix Computations (Johns Hopkins Studies in Mathematical Sciences)

Gene Golub — 2005-07-12T18:58:24-00:00

(15 October 1996)

Revised and updated, the third edition of Golub and Van Loan's classic text in computer science provides essential information about the mathematical background and algorithmic skills required for the production of numerical software. This new edition includes thoroughly revised chapters on matrix multiplication problems and parallel matrix computations, expanded treatment of CS decomposition, an updated overview of floating point arithmetic, a more accurate rendition of the modified Gram-Schmidt process, and new material devoted to GMRES, QMR, and other methods designed to handle the sparse unsymmetric linear system problem.

Numerical Recipes with Source Code CD-ROM 3rd Edition: The Art of Scientific Computing

William Press — 2008-02-15T17:43:05-00:00

(01 September 2007)

This book/CD bundle of the greatly expanded third edition of Numerical Recipes now has wider coverage than ever before, many new, expanded and updated sections, and two completely new chapters. Co-authored by four leading scientists from academia and industry, Numerical Recipes starts with basic mathematics and computer science and proceeds to complete, working routines. The informal, easy-to-read style that made earlier editions so popular is kept throughout. Highlights of the new material include: a new chapter on classification and inference, Gaussian mixture models, HMMs, hierarchical clustering, and SVMs; a new chapter on computational geometry, covering KD trees, quad- and octrees, Delaunay triangulation, and algorithms for lines, polygons, triangles, and spheres; interior point methods for linear programming; MCMC; an expanded treatment of ODEs with completely new routines; and many new statistical distributions.

Learning a Maximum Margin Subspace for Image Retrieval

Xiaofei He — 2008-04-06T10:16:43-00:00

IEEE Trans. on Knowl. and Data Eng., Vol. 20, No. 2. (February 2008), pp. 189-201.

Geodesic entropic graphs for dimension and entropy estimation in manifold learning

JA Costa — 2008-04-01T14:04:25-00:00

Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], Vol. 52, No. 8. (2004), pp. 2210-2221.

In the manifold learning problem, one seeks to discover a smooth low dimensional surface, i.e., a manifold embedded in a higher dimensional linear vector space, based on a set of measured sample points on the surface. In this paper, we consider the closely related problem of estimating the manifold's intrinsic dimension and the intrinsic entropy of the sample points. Specifically, we view the sample points as realizations of an unknown multivariate density supported on an unknown smooth manifold. We introduce a novel geometric approach based on entropic graph methods. Although the theory presented applies to this general class of graphs, we focus on the geodesic-minimal-spanning-tree (GMST) to obtaining asymptotically consistent estimates of the manifold dimension and the Re/spl acute/nyi /spl alpha/-entropy of the sample density on the manifold. The GMST approach is striking in its simplicity and does not require reconstruction of the manifold or estimation of the multivariate density of the samples. The GMST method simply constructs a minimal spanning tree (MST) sequence using a geodesic edge matrix and uses the overall lengths of the MSTs to simultaneously estimate manifold dimension and entropy. We illustrate the GMST approach on standard synthetic manifolds as well as on real data sets consisting of images of faces.

Feature Extraction: Foundations and Applications (Studies in Fuzziness and Soft Computing)

2008-03-31T23:22:48-00:00

(29 August 2006)

This book is both a reference for engineers and scientists and a teaching resource, featuring tutorial chapters and research papers on feature extraction. Its CD-ROM includes the data of the NIPS 2003 Feature Selection Challenge and sample Matlab® code. "This book compiles some very promising techniques, coming from an extremely smart collection of researchers, delivering their best ideas in a competitive environment." Trevor Hastie, Stanford University "Feature selection is a key technology for making sense of the high dimensional data. Isabelle Guyon et al. have done a splendid job in designing a challenging competition, and collecting the lessons learned." Bernhard Schoelkopf, Max Planck Institute "There has been until now insufficient consideration of feature selection algorithms, no unified presentation of leading methods, and no systematic comparisons. This volume is noteworthy for the breadth of methods covered, the clarity of presentations, the unity in notation and the helpful statistical appendices." David G. Stork, Ricoh Innovations "Feature extraction finds application in biotechnology, industrial inspection, the Internet, radar, sonar, and speech recognition. This book will make a difference to the literature on machine learning." Simon Haykin, Mc Master University "This book sets a high standard as the public record of an interesting and effective competition." Peter Norvig, Google Inc.

Convexity, Classification, and Risk Bounds

Peter Bartlett — 2006-02-18T14:36:37-00:00

Journal of the American Statistical Association, Vol. 101, No. 473. (March 2006), pp. 138-156.

On divergences, surrogate loss functions, and decentralized detection

Xuanlong Nguyen — 2008-01-08T00:17:15-00:00

(25 Oct 2005)

We develop a general correspondence between a family of loss functions that act as surrogates to 0-1 loss, and the class of Ali-Silvey or $f$-divergence functionals. This correspondence provides the basis for choosing and evaluating various surrogate losses frequently used in statistical learning (e.g., hinge loss, exponential loss, logistic loss); conversely, it provides a decision-theoretic framework for the choice of divergences in signal processing and quantization theory. We exploit this correspondence to characterize the statistical behavior of a nonparametric decentralized hypothesis testing algorithms that operate by minimizing convex surrogate loss functions. In particular, we specify the family of loss functions that are equivalent to 0-1 loss in the sense of producing the same quantization rules and discriminant functions.

One-class classifiers : a review and analysis of suitability in the context of mobile-masquerader detection

Oleksiy Mazhelis — 2008-03-31T13:10:59-00:00

South African Computer Journal, Vol. 36 (2006), pp. 29-48.

Application of LVQ to novelty detection using outlier training data

Hyoung-Joo Lee — 2008-03-31T13:07:04-00:00

Pattern Recognition Letters, Vol. 27, No. 13. (1 October 2006), pp. 1572-1579.

We propose to use learning vector quantization (LVQ) in novelty detection where a few outliers exist in training data. The codebook update of original LVQ is modified and the scheme to determine a threshold for each codebook is proposed. Experimental results on artificial and real-world problems are quite promising.

The many faces of sequence alignment.

S Batzoglou — 2006-03-01T16:58:55-00:00

Brief Bioinform, Vol. 6, No. 1. (March 2005), pp. 6-22.

Starting with the sequencing of the mouse genome in 2002, we have entered a period where the main focus of genomics will be to compare multiple genomes in order to learn about human biology and evolution at the DNA level. Alignment methods are the main computational component of this endeavour. This short review aims to summarise the current status of research in alignments, emphasising large-scale genomic comparisons and suggesting possible directions that will be explored in the near future.

The complexity of theorem-proving procedures

Stephen Cook — 2006-02-06T08:39:41-00:00

(1971), pp. 151-158.

Active Learning with Feedback on Features and Instances

Hema Raghavan — 2008-03-28T15:53:39-00:00

Journal of Machine Learning Research, Vol. 7 (August 2006), pp. 1655-1686.

We extend the traditional active learning framework to include feedback on features in addition to labeling instances, and we execute a careful study of the effects of feature selection and human feedback on features in the setting of text categorization. Our experiments on a variety of categorization tasks indicate that there is significant potential in improving classifier performance by feature re-weighting, beyond that achieved via membership queries alone (traditional active learning) if we have access to an oracle that can point to the important (most predictive) features. Our experiments on human subjects indicate that human feedback on feature relevance can identify a sufficient proportion of the most relevant features (over 50% in our experiments). We find that on average, labeling a feature takes much less time than labeling a document. We devise an algorithm that interleaves labeling features and documents which significantly accelerates standard active learning in our simulation experiments. Feature feedback can complement traditional active learning in applications such as news filtering, e-mail classification, and personalization, where the human teacher can have significant knowledge on the relevance of features.

Alternative Measures of Computational Complexity with Applications to Agnostic Learning

Shai Ben-David — 2008-03-28T10:27:57-00:00

Theory and Applications of Models of Computation (2006), pp. 231-235.

We address a fundamental problem of complexity theory - the inadequacy of worst-case complexity for the task of evaluating the computational resources required for real life problems. While being the best known measure and enjoying the support of a rich and elegant theory, worst-case complexity seems gives rise to over-pessimistic complexity values. Many standard task, that are being carried out routinely in machine learning applications, are NP-hard, that is, infeasible from the worst-case-complexity perspective. In this work we offer an alternative measure of complexity for approximations-optimization tasks. Our approach is to define a hierarchy on the set of inputs to a learning task, so that natural (’real data’) inputs occupy only bounded levels of this hierarchy and that there are algorithms that handle in polynomial time each such bounded level.

Random Forests

Leo Breiman — 2007-02-25T22:54:41-00:00

Machine Learning, Vol. V45, No. 1. (1 October 2001), pp. 5-32.

Novelty detection with constructive probabilistic neural networks

Adriano Oliveira — 2008-03-25T12:05:39-00:00

Neurocomputing, Vol. 71, No. 4-6. (January 2008), pp. 1046-1053.

This paper investigates the use of probabilistic neural networks trained with the dynamic decay adjustment algorithm (PNN-DDA) for novelty detection tasks. PNN-DDA is a fast, constructive neural model originally developed and investigated for standard classification tasks. The training algorithm is controlled by two parameters, [theta]+ and [theta]-. Simulations employing four data sets from the UCI machine learning repository are reported. The results show that parameter [theta]- considerably influences the performance of PNN-DDA for novelty detection, and furthermore, that PNN-DDA achieves performance comparable to NNDD with the advantage of producing much smaller classifiers.

Weighted support vector machine for data classification

Xulei Yang — 2008-03-25T12:04:19-00:00

Neural Networks, 2005. IJCNN '05. Proceedings. 2005 IEEE International Joint Conference on, Vol. 2 (2005), pp. 859-864 vol. 2.

This paper presents a weighted support vector machine (WSVM) to improve the outlier sensitivity problem of standard support vector machine (SVM) for two-class data classification. The basic idea is to assign different weights to different data points such that the WSVM training algorithm learns the decision surface according to the relative importance of data points in the training data set. The weights used in WSVM are generated by kernel-based possibilistic c-means (KPCM) algorithm, whose partition generates relative high values for important data points but low values for outliers. Experimental results indicate that the proposed method reduces the affect of outliers and yields higher classification rate than standard SVM does when outliers exist in the training data set.

A Unified Subspace Outlier Ensemble Framework for Outlier Detection in High Dimensional Spaces

Zengyou He — 2008-03-25T12:00:22-00:00

(24 May 2005)

The task of outlier detection is to find small groups of data objects that are exceptional when compared with rest large amount of data. Detection of such outliers is important for many applications such as fraud detection and customer migration. Most such applications are high dimensional domains in which the data may contain hundreds of dimensions. However, the outlier detection problem itself is not well defined and none of the existing definitions are widely accepted, especially in high dimensional space. In this paper, our first contribution is to propose a unified framework for outlier detection in high dimensional spaces from an ensemble-learning viewpoint. In our new framework, the outlying-ness of each data object is measured by fusing outlier factors in different subspaces using a combination function. Accordingly, we show that all existing researches on outlier detection can be regarded as special cases in the unified framework with respect to the set of subspaces considered and the type of combination function used. In addition, to demonstrate the usefulness of the ensemble-learning based outlier detection framework, we developed a very simple and fast algorithm, namely SOE1 (Subspace Outlier Ensemble using 1-dimensional Subspaces) in which only subspaces with one dimension is used for mining outliers from large categorical datasets. The SOE1 algorithm needs only two scans over the dataset and hence is very appealing in real data mining applications. Experimental results on real datasets and large synthetic datasets show that: (1) SOE1 has comparable performance with respect to those state-of-art outlier detection algorithms on identifying true outliers and (2) SOE1 can be an order of magnitude faster than one of the fastest outlier detection algorithms known so far.

Modified support vector novelty detector using training data with outliers

Li Cao — 2008-03-25T11:53:18-00:00

Pattern Recogn. Lett., Vol. 24, No. 14. (October 2003), pp. 2479-2487.

Performance Measures for Neyman-Pearson Classification

Clayton Scott — 2008-03-24T14:45:45-00:00

IEEE Transactions on Information Theory, Vol. 53, No. 8. (2007), pp. 2852-2863.

Local learning projections

Mingrui Wu — 2008-03-21T23:48:47-00:00

(2007), pp. 1039-1046.