Search

Many learning algorithms make an implicit assumption that all the attributes present in the data are relevant to a learning task. However, several studies have demonstrated that this assumption rarely holds; for many supervised learning algorithms, the inclusion of irrelevant or redundant attributes can result in a degradation in classification accuracy. While a variety of different methods for dimensionality reduction exist, many of these are only appropriate for datasets which contain a small number of attributes (e.g. < 20). This paper presents an alternative approach to dimensionality reduction, and demonstrates how it can be combined with a Nearest Neighbour learning algorithm. We present an empirical evaluation of this approach, and contrast its performance with two related techniques; a Monte-Carlo wrapper and an Information Gain-based filter approach. [ABSTRACT FROM AUTHOR]

We discuss the problem of choosing the complexity of a decision tree (measured in the number of leaf nodes) that gives us highest generalization performance. We first discuss an analysis of the generalization error of decision trees that gives us a new perspective on the regularization parameter that is inherent to any regularization (e.g., pruning) algorithm. There is an optimal setting of this parameter for every learning problem; a setting that does well for one problem will inevitably do poorly for others. We will see that the optimal setting can in fact be estimated from the sample, without "trying out" various settings on holdout data. This leads us to a nonparametric decision tree regularization algorithm that can, in principle, work well for all learning problems. [ABSTRACT FROM AUTHOR]

The proposed algorithm (BPL) induces behavior patterns from events taking into account characteristics of observed systems and their environment. The main strategy of this method consists on building summaries of the behaviour of a system as events arrive, and take these summaries as training examples. BPL constructs summaries with new features from events, like duration of current event values, repetitions of an event in a period of time, amongst others. This algorithm has been tested in learning faulty behavior of networks with the purpose of continuously predicting alarms. [ABSTRACT FROM AUTHOR]

This paper presents a new method of measuring performance when positives are rare and investigates whether Chomsky-like grammar representations are useful for learning accurate comprehensible predictors of members of biological sequence families. The positive-only learning framework of the Inductive Logic Programming (ILP) system CProgol is used to generate a grammar for recognising a class of proteins known as human neuropeptide precursors (NPPs). Performance is measured using both predictive accuracy and a new cost function, Relative Advantage (RA). The RA results show that searching for NPPs by using our best NPP predictor as a filter is more than 100 times more efficient than randomly selecting proteins for synthesis and testing them for biological activity. Predictive accuracy is not a good measure of performance for this domain because it does not discriminate well between NPP recognition models: despite covering varying numbers of (the rare) positives, all the models are awarded a similar (high) score by predictive accuracy because they all exclude most of the abundant negatives. [ABSTRACT FROM AUTHOR]

The detection of intrusions over computer networks (i.e., network access by non-authorized users)c an be cast to the task of detecting anomalous patterns of network traffic. In this case, models of normal traffic have to be determined and compared against the current network traffic. Data mining systems based on Genetic Algorithms can contribute powerful search techniques for the acquisition of patterns of the network traffic from the large amount of data made available by audit tools. We compare models of network traffic acquired by a system based on a distributed genetic algorithm with the ones acquired by a system based on greedy heuristics. Also we discuss representation change of the network data and its impact over the performances of the traffic models. Network data made available from the Information Exploration Shootout project and the 1998 DARPA Intrusion Detection Evaluation have been chosen as experimental testbed. [ABSTRACT FROM AUTHOR]

Acquisition of patterns for information extraction systems is a common task in Natural Language Processing, mostly based on manual analysis of text corpora. We have developed a system called Prométhée, which incrementally extracts lexico-syntactic patterns for a specific conceptual relation from a technical corpus. However, these patterns are often too general and need to be manually validated. In this paper, we demonstrate how Prométhée has been interfaced with the machine learning system Eagle in order to automatically refine the patterns it produces. The empirical results obtained with this technique show that the refined patterns allows to decrease the need for the human validation. [ABSTRACT FROM AUTHOR]

Two methods to assign discrete values to continuous values from time series, using dynamic information about the series, are proposed. The first method is based on a particular statistic which allows us to select a discrete value for a new continuous value from the series. The second one is based on a concept of significant distance between consecutive values from time series which is defined. This definition is based on qualitative changes in the time series values. In both methods, the conversion process of continuous values into discrete values is dynamic in opposition to static classical methods used in machine learning. Finally, we use the proposed methods in a practical case. We transform the daily clearness index time series into discrete values. The results display that the series with discrete values obtained from the dynamic process captures better the sequential properties of the original continuous series. [ABSTRACT FROM AUTHOR]

Large Bayes (LB) is a recently introduced classifier built from frequent and interesting itemsets. LB uses itemsets to create context-specific probabilistic models of the data and estimate the conditional probability P(ciA) of each class ci given a case A. In this paper we use chi-square tests to address several drawbacks of the originally proposed interestingness metric, namely: (i) the inability to capture certain really interesting patterns, (ii) the need for a user-defined and data dependent interestingness threshold, and (iii) the need to set a minimum support threshold. We also introduce some pruning criteria which allow for a trade-off between complexity and speed on one side and classification accuracy on the other. Our experimental results show that the modified LB outperforms the original LB, Naïve Bayes, C4.5 and TAN. [ABSTRACT FROM AUTHOR]

In the present paper we propose a consistent way to integrate syntactical least general generalizations (lgg's) with semantic evaluation of the hypotheses. For this purpose we use two different relations on the hypothesis space — a constructive one, used to generate lgg's and a semantic one giving the coverage-based evaluation of the lgg. These two relations jointly implement a semantic distance measure. The formal background for this is a height-based definition of a semi-distance in a join semi-lattice. We use some basic results from lattice theory and introduce a family of language independent coverage-based height functions. The theoretical results are illustrated by examples of solving some basic inductive learning tasks. [ABSTRACT FROM AUTHOR]

This paper describes an experiment performed using the Principal Direction Divisive Partitioning algorithm (Boley, 1998) in order to extract linguistic word error regularities from several sets of medical dictation data. For each of six physicians, two hundred finished medical dictations aligned with their corresponding automatic speech recognition output were clustered and the results analyzed for linguistic regularities between and within clusters. Sparsity measures indicated a good fit between the algorithm and the input data. Linguistic analysis of the output clusters showed evidence of systematic word recognition error for short words, function words, words with destressed vowels, and phonological confusion errors due to telephony (recording) bandwidth interference. No qualitatively significant distinctions between clusters could be made by examining word errors alone, but the results confirmed several informally held hypotheses and suggested several avenues of further investigation, such as the examination of word error contexts. [ABSTRACT FROM AUTHOR]

The paper describes a new, context-sensitive discretization algorithm that combines aspects of unsupervised (class-blind) and supervised methods. The algorithm is applicable to a wide range of machine learning and data mining problems where continuous attributes need to be discretized. In this paper, we evaluate its utility in a regression-by-classification setting. Preliminary experimental results indicate that the decision trees induced using this discretization strategy are significantly smaller and thus more comprehensible than those learned with standard discretization methods, while losing only minimally in numerical prediction accuracy. This may be a considerable advantage in machine learning and data mining applications where comprehensibility is an issue. [ABSTRACT FROM AUTHOR]

We present an asymmetric co-evolutionary learning algorithm for imperfect-information zero-sum games. This algorithm is designed so that the fitness of the individual agents is calculated in a way that is compatible with the goal of game-theoretic optimality. This compatibility has been somewhat lacking in previous co-evolutionary approaches, as these have often depended on unwarranted assumptions about the absolute and relative strength of players. Our algorithm design is tested on a game for which the optimal strategy is known, and is seen to work well. [ABSTRACT FROM AUTHOR]

In this paper, a new similarity measure for nearest-neighbor classification is introduced. This measure is an approximation of a theoretical similarity that has some interesting properties. In particular, this latter is a step toward a theory of concepts formation. It renders identical some examples that have distinct representations. Moreover, these examples share some properties relevant for the concept undertaken. Hence, a rule-based representation of the concept can be inferred from the theoretical similarity. Moreover, in this paper, the approximation is validated by some preliminary experiments on non-noisy datasets. [ABSTRACT FROM AUTHOR]

Supervised learning algorithms usually require large amounts of training data to learn reasonably accurate classifiers. Yet, in many text classification tasks, labeled training documents are expensive to obtain, while unlabeled documents are readily available in large quantities. This paper describes a general framework for extending any text learning algorithm to utilize unlabeled documents in addition to labeled document using an Expectation-Maximization-like scheme. Our instantiation of this partially supervised classification framework with a similarity-based single prototype classifier achieves encouraging results on two real-world text datasets. Classification accuracy is reduced by up to 38% when using unlabeled documents in addition to labeled documents. [ABSTRACT FROM AUTHOR]

We examine the role of simplicity in directing the induction of context-free grammars from sample sentences. We present a rational reconstruction of Wolff's SNPR — the Grids system — which incorporates a bias toward grammars that minimize description length. The algorithm alternates between merging existing nonterminal symbols and creating new symbols, using a beam search to move from complex to simpler grammars. Experiments suggest that this approach can induce accurate grammars and that it scales reasonably to more difficult domains. [ABSTRACT FROM AUTHOR]

Induction tree is useful to obtain a proper set of rules for a large amount of examples. However, it has difficulty in obtaining the relation between continuous-valued data points. Many data sets show significant correlations between input variables, and a large amount of useful information is hidden in the data as nonlinearities. It has been shown that neural network is better than direct application of induction tree in modeling nonlinear characteristics of sample data. It is proposed in this paper that we derive a compact set of rules to support data with input variable relations. Those relations as a set of linear classifiers can be obtained from neural network modeling based on back-propagation. This will also solve overgeneralization amd overspecialization problems often seen in induction tree. We have tested this scheme over several data sets to compare with decision tree results. [ABSTRACT FROM AUTHOR]

In this paper an application of the Complexity Approximation Principle to the non-linear regression is suggested. We combine this principle with the approximation of the complexity of a real-valued vector parameter proposed by Rissanen and thus derive a method for the choice of parameters in the non-linear regression. [ABSTRACT FROM AUTHOR]

The elaboration of head-surface registration techniques for auditory potentials evoked from the brainstem (ABR) enabled the construction of objective research and diagnostic methods, which can utilized in the examinations of auditory organs. The aim of the present work was the construction of a method, making use of the neural network techniques, enabling an automated detection of wave V in the ABR signals. The basic problem encountered in any attempts of automated analysis of the auditory potentials is connected with impossibility of a reliable evaluation of a single response evoked by a weak acoustic signal. It has been assumed that considerably better detection results should be obtained, when additional context information will be provided to the network's input. This assumption has been verified using complex, hybrid neural networks. As a result about 90% of correct recognitions has been achieved [ABSTRACT FROM AUTHOR]

There has recently been some interest in applying machine learning techniques to support the acquisition and adaptation of workflow models. The different learning algorithms, that have been proposed, share some restrictions, which may prevent them from being used in practice. Approaches applying techniques from grammatical inference are restricted to sequential workflows. Other algorithms allowing concurrency require unique activity nodes. This contribution shows how the basic principle of our previous approach to sequential workflow induction can be generalized, so that it is able to deal with concurrency. It does not require unique activity nodes. The presented approach uses a log-likelihood guided search in the space of workflow models, that starts with a most general workflow model containing unique activity nodes. Two split operators are available for specialization. [ABSTRACT FROM AUTHOR]

This paper focuses on the variance introduced by the discretization techniques used to handle continuous attributes in decision tree induction. Different discretization procedures are first studied empirically, then means to reduce the discretization variance are proposed. The experiment shows that discretization variance is large and that it is possible to reduce it significantly without notable computational costs. The resulting variance reduction mainly improves interpretability and stability of decision trees, and marginally their accuracy. [ABSTRACT FROM AUTHOR]

Intrusion detection systems (IDSs) need to maximize security while minimizing costs. In this paper, we study the problem of building cost-sensitive intrusion detection models to be used for real-time detection. We briefly discuss the major cost factors in IDS, including consequential and operational costs. We propose a multiple model cost-sensitive machine learning technique to produce models that are optimized for user-defined cost metrics. Empirical experiments in offline analysis show a reduction of approximately 97% in operational cost over a single model approach, and a reduction of approximately 30% in consequential cost over a pure accuracy-based approach. [ABSTRACT FROM AUTHOR]

The acquisition of new accounts is a major task of marketers. It is often carried out rather unsystematically, though. However, by now, one has come to terms that customer acquisition is a matter of quality. An instrument to evaluate prospective accounts is the Customer Lifetime Value (CLV). This paper introduces a Data Mining environment for its calculation and demonstrates its applicability to marketing in the automotive industry. The Car Miner refers to the evaluation of prospects rather than of current customers. This and other restrictions will be discussed along with guidelines for future research. [ABSTRACT FROM AUTHOR]

In this paper Schapire and Singer's AdaBoost.MH boosting algorithm is applied to the Word Sense Disambiguation (WSD) problem. Initial experiments on a set of 15 selected polysemous words show that the boosting approach surpasses Naive Bayes and Exemplar-based approaches, which represent state-of-the-art accuracy on supervised WSD. In order to make boosting practical for a real learning domain of thousands of words, several ways of accelerating the algorithm by reducing the feature space are studied. The best variant, which we call LazyBoosting, is tested on the largest sense-tagged corpus available containing 192,800 examples of the 191 most frequent and ambiguous English words. Again, boosting compares favourably to the other benchmark algorithms. [ABSTRACT FROM AUTHOR]

A minimax version of temporal difference learning (minimax TD-learning) is given, similar to minimax Q-learning. The algorithm is used to train a neural net to play Campaign, a two-player zero-sum game with imperfect information of the Markov game class. Two different evaluation criteria for evaluating game-playing agents are used, and their relation to game theory is shown. Also practical aspects of linear programming and fictitious play used for solving matrix games are discussed. [ABSTRACT FROM AUTHOR]

Feature subset-selection has emerged as a useful technique for creating diversity in ensembles — particularly in classification ensembles. In this paper we argue that this diversity needs to be monitored in the creation of the ensemble. We propose an entropy measure of the outputs of the ensemble members as a useful measure of the ensemble diversity. Further, we show that using the associated conditional entropy as a loss function (error measure) works well and the entropy in the ensemble predicts well the reduction in error due to the ensemble. These measures are evaluated on a medical prediction problem and are shown to predict the performance of the ensemble well. We also show that the entropy measure of diversity has the added advantage that it seems to model the change in diversity with the size of the ensemble. [ABSTRACT FROM AUTHOR]

To facilitate effective search on the World Wide Web, meta search engines have been developed which do not search the Web themselves, but use available search engines to find the required information. By means of wrappers, meta search engines retrieve information from the pages returned by search engines. We present an approach to automatically create such wrappers by means of an incremental grammar induction algorithm. The algorithm uses an adaptation of the string edit distance. Our method performs well; it is quick, can be used for several types of result pages and requires a minimal amount of user interaction. [ABSTRACT FROM AUTHOR]

This paper evaluates complete versus partial classification for the problem of identifying latently dissatisfied customers. Briefly, latently dissatisfied customers are defined as customers reporting overall satisfaction but who possess typical characteristics of dissatisfied customers. Unfortunately, identifying latenty dissatisfied customers, based on patterns of dissatisfaction, is difficult since in customer satisfaction surveys, typically only a small minority of customers reports to be overall dissatisfied and this is exactly the group we want to focus learning on. Therefore, it has been claimed that since traditional (complete) classification techniques have difficulties dealing with highly skewed class distributions, the adoption of partial classification techniques could be more appropriate. We evaluate three different complete and partial classification techniques and compare their performance on a ROC convex hull graph. Results on real world data show that, under the circumstances described abobe, partial classification is indeed a serious competitor for complete classification. Moreover, external validation on holdout data shows that partial classification is able to identify latently dissatisfied customers correctly. [ABSTRACT FROM AUTHOR]

We present a new model, derived from classical Hidden Markov Models (HMMs), to learn sequences of large Boolean vectors. Our model — Hidden Markov Model with Patterns, or HMMP — differs from HMM by the fact that it uses patterns to define the emission probability distributions attached to the states. We also present an efficient state merging algorithm to learn this model from training vector sequences. This model and our algorithm are applied to learn Boolean vector sequences used to test integrated circuits. The learned HMMPs are used as test sequence generators. They achieve very high fault coverage, despite their reduced size, which demonstrates the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

We investigate the problem of using past performance information to select an algorithm for a given classification problem. We present three ranking methods for that purpose: average ranks, success rate ratios and significant wins. We also analyze the problem of evaluating and comparing these methods. The evaluation technique used is based on a leave-one-out procedure. On each iteration, the method generates a ranking using the results obtained by the algorithms on the training datasets. This ranking is then evaluated by calculating its distance from the ideal ranking built using the performance information on the test dataset. The distance measure adopted here, average correlation, is based on Spearman's rank correlation coefficient. To compare ranking methods, a combination of Friedman's test and Dunn's multiple comparison procedure is adopted. When applied to the methods presented here, these tests indicate that the success rate ratios and average ranks methods perform better than significant wins. [ABSTRACT FROM AUTHOR]

Melanoma is the most dangerous skin cancer and early diagnosis is the main factor for its successful treatment. Experienced dermatologists with specific training make the diagnosis by clinical inspection and they reach 80% level of both sensitivity and specificity. In this paper, we present a multi-classifiers system for supporting the early diagnosis of melanoma. The system acquires a digital image of the skin lesion and extracts a set of geometric and colorimetric features. The diagnosis is performed on the vector of features by integrating with a voting schema the diagnostic outputs of three different classifiers: discriminant analysis, k-nearest neighbor and decision tree. The system is build and validated on a set of 152 skin images acquired via D-ELM. The results are comparable or better of the diagnostic response of a group of expert dermatologists. [ABSTRACT FROM AUTHOR]

Using domain knowledge in unsupervised learning has shown to be a useful strategy when the set of examples of a given domain has not an evident structure or presents some level of noise. This background knowledge can be expressed as a set of classification rules and introduced as a semantic bias during the learning process. In this work we present some experiments on the use of partial domain knowledge in conceptual clustering. The domain knowledge (or domain theory) is used to select a set of examples that will be used to start the learning process, this knowledge has not to be complete neither consistent. This bias will increase the quality of the final groups and reduce the effect of the order of the examples. Some measures of stability of classification are used as evaluation method. The improvement of the acquired concepts can be used to improve and correct the domain knowledge. A set of heuristics to revise the original domain theory has been experimented, yielding to some interesting results. [ABSTRACT FROM AUTHOR]

We apply Inductive Logic Programming (ILP) for inducing trading rules formed out of combinations of technical indicators from historical market data. To do this, we first identify ideal trading opportunities in the historical data, and then feed these as examples to an ILP learner, which will try to induce a description of them in terms of a given set of indicators. The main contributions of this paper are twofold. Conceptually, we are learning strategies in a chaotic domain in which learning a predictive model is impossible. Technically, we show a way of dealing with disjunctive positive examples, which create significant problems for most inductive learners. [ABSTRACT FROM AUTHOR]

Support Vector Machines for pattern recognition are addressed to binary classification problems. The problem of multi-class classification is typically solved by the combination of 2-class decision functions using voting scheme methods or decison trees. We present a new multi-class classification SVM for the separable case, called KSVCR. Learning machines operating in a kernel-induced feature space are constructed assigning output +1 or −1 if training patterns belongs to the classes to be separated, and assigning output 0 if patterns have a different label to the formers. This formulation of multi-class classification problem ever assigns a meaningful answer to every input and its architecture is more fault-tolerant than standard methods one. [ABSTRACT FROM AUTHOR]

In this paper, we aim to address a frequent shortcoming of electronic commerce: the lack of customer service. We present an approach to product recommendation using a modified cycle for case-based reasoning in which a new refinement step is introduced. We then use this cycle combined with a heuristic we devised to create a short-term profile of the client. This profile is not stored or reused after the transaction, reducing maintenance. In fact, it allows the client and the system to find an appropriate product to satisfy the client on the basis of available products in a potentially efficient way. [ABSTRACT FROM AUTHOR]

Designing the representation languages for the input, LE, and output, LH, of a learning algorithm is the hardest task within machine learning applications. This paper emphasizes the importance of constructing an appropriate representation LE for knowledge discovery applications using the example of time related phenomena. Given the same raw data — most frequently a database with time-stamped data — rather different representations have to be produced for the learning methods that handle time. In this paper, a set of learning tasks dealing with time is given together with the input required by learning methods which solve the tasks. Transformations from raw data to the desired representation are illustrated by three case studies. [ABSTRACT FROM AUTHOR]

Functional dependencies play an important role in the design of databases. We study the learnability of the class of minimal covers of functional dependencies (MCFD) within the exact learning model via queries. We prove that neither equivalence queries alone nor membership queries alone suffice to learn the class. In contrast, we show that learning becomes feasible if both types of queries are allowed. We also give some properties concerning minimal covers. [ABSTRACT FROM AUTHOR]

We present efficient on-line algorithms for learning unions of a constant number of tree patterns, unions of a constant number of one-variable pattern languages, and unions of a constant number of pattern languages with fixed length substitutions. By fixed length substitutions we mean that each occurrence of variable xi must be substituted by terminal strings of fixed length l(xi). We prove that if an arbitrary unions of pattern languages with fixed length substitutions can be learned efficiently then DNFs are efficiently learnable in the mistake bound model. Since we use a reduction to Winnow, our algorithms are robust against attribute noise. Furthermore, they can be modified to handle concept drift. Also, our approach is quite general and may be applicable to learning other pattern related classes. For example, we could learn a more general pattern language class in which a penalty (i.e. weight) is assigned to each violation of the rule that a terminal symbol cannot be changed or that a pair of variable symbols, of the same variable, must be substituted by the same terminal string. An instance is positive iff the penalty incurred for violating these rules is below a given tolerable threshold. [ABSTRACT FROM AUTHOR]

We design efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees, we implicitly maintain one weight for each of the prunings (exponentially many). The method works for a large class of algorithms that update its weights multiplicatively. It can also be used to design algorithms that predict nearly as well as the best convex combination of prunings. [ABSTRACT FROM AUTHOR]

In this paper we introduce a general method that allows to prove tight linear inequalities between different types of predictive complexity and thus we generalise our previous results. The method relies upon probabilistic considerations and allows to describe (using geometrical terms) the sets of coefficients which correspond to true inequalities. We also apply this method to the square-loss and logarithmic complexity and describe their relations which were not covered by our previous research. [ABSTRACT FROM AUTHOR]

A new research frontier in AI and data mining seeks to develop methods to automatically discover relevant variables among many irrelevant ones. In this paper, we present four algorithms that output such crucial variables in PAC model with membership queries. The first algorithm executes the task under any unknown distribution by measuring the distance between virtual and real targets. The second algorithm exhausts virtual version space under an arbitrary distribution. The third algorithm exhausts universal set under the uniform distribution. The fourth algorithm measures influence of variables under the uniform distribution. Knowing the number r of relevant variables, the first algorithm runs in almost linear time for r. The second and the third ones use less membership queries than the first one, but runs in time exponential for r. The fourth one enumerates highly influential variables in quadratic time for r. [ABSTRACT FROM AUTHOR]

Boolean formulas are known not to be PAC-predictable even with membership queries under some cryptographic assumptions. In this paper, we study the learning complexity of some subclasses of boolean formulas obtained by varying the basis of elementary operations allowed as connectives. This broad family of classes includes, as a particular case, general boolean formulas, by considering the basis given by {AND,OR,NOT}. We completely solve the problem. We prove the following dichotomy theorem: For any set of basic boolean functions, the resulting set of formulas is either polynomially learnable from equivalence queries or membership queries alone or else it is not PAC-predictable even with membership queries under cryptographic assumptions. We identify precisely which sets of basic functions are in which of the two cases. Furthermore, we prove than the learning complexity of formulas over a basis depends only on the absolute expressivity power of the class, ie., the set of functions that can be represented regardless of the size of the representation. In consequence, the same classification holds for the learnability of boolean circuits. [ABSTRACT FROM AUTHOR]

Blum and Blum (1975) showed that a class $$ \mathcal{B} $$ of suitable recursive approximations to the halting problem is reliably EX-learnable. These investigations are carried on by showing that $$ \mathcal{B} $$ is neither in NUM nor robustly EX-learnable. Since the definition of the class $$ \mathcal{B} $$ is quite natural and does not contain any self-referential coding, $$ \mathcal{B} $$ serves as an example that the notion of robustness for learning is quite more restrictive than intended. Moreover, variants of this problem obtained by approximating any given recursively enumerable set A instead of the halting problem K are studied. All corresponding function classes $$ \mathcal{U} $$(A) are still EX-inferable but may fail to be reliably EX-learnable, for example if A is non-high and hypersimple. Additionally, it is proved that $$ \mathcal{U} $$(A) is neither in NUM nor robustly EX-learnable provided A is part of a recursively inseparable pair, A is simple but not hypersimple or A is neither recursive nor high. These results provide more evidence that there is still some need to find an adequate notion for "naturally learnable function classes." [ABSTRACT FROM AUTHOR]

The paper investigates whether it is possible to learn every enumerable classes of recursive functions from "typical" examples. "Typical" means, there is a computable family of finite sets, such that for each function in the class there is one set of examples that can be used in any suitable hypothesis space for this class of functions. As it will turn out, there are enumerable classes of recursive functions that are not learnable from "typical" examples. The learnable classes are characterized. The results are proved within an abstract model of learning from examples, introduced by Freivalds, Kinber and Wiehagen. Finally, the results are interpreted and possible connections of this theoretical work to the situation in real life classrooms are pointed out. [ABSTRACT FROM AUTHOR]

When training Support Vector Machines (SVMs) over nonseparable data sets, one sets the threshold b using any dual cost coefficient that is strictly between the bounds of 0 and C. We show that there exist SVM training problems with dual optimal solutions with all coefficients at bounds, but that all such problems are degenerate in the sense that the "optimal separating hyperplane" is given by w = 0, and the resulting (degenerate) SVM will classify all future points identically (to the class that supplies more training data). We also derive necessary and sufficient conditions on the input data for this to occur. Finally, we show that an SVM training problem can always be made degenerate by the addition of a single data point belonging to a certain unbounded polyhedron, which we characterize in terms of its extreme points and rays. [ABSTRACT FROM AUTHOR]

Recently, Kearns and Singh presented the first provably efficient and near-optimal algorithm for reinforcement learning in general Markov decision processes. One of the key contributions of the algorithm is its explicit treatment of the exploration-exploitation trade off. In this paper, we show how the algorithm can be improved by substituting the exploration phase, that builds a model of the underlying Markov decision process by estimating the transition probabilities, by an adaptive sampling method more suitable for the problem. Our improvement is two-folded. First, our theoretical bound on the worst case time needed to converge to an almost optimal policy is significatively smaller. Second, due to the adaptiveness of the sampling method we use, we discuss how our algorithm might perform better in practice than the previous one. [ABSTRACT FROM AUTHOR]

We provide an algorithm to PAC learn multivariate polynomials with real coefficients. The instance space from which labeled samples are drawn is IRN but the coordinates of such samples are known only approximately. The algorithm is iterative and the main ingredient of its complexity, the number of iterations it performs, is estimated using the condition number of a linear programming problem associated to the sample. To the best of our knowledge, this is the first study of PAC learning concepts parameterized by real numbers from approximate data. [ABSTRACT FROM AUTHOR]

In many learning problems, labeled examples are rare or expensive while numerous unlabeled and positive examples are available. However, most learning algorithms only use labeled examples. Thus we address the problem of learning with the help of positive and unlabeled data given a small number of labeled examples. We present both theoretical and empirical arguments showing that learning algorithms can be improved by the use of both unlabeled and positive data. As an illustrating problem, we consider the learning algorithm from statistics for monotone conjunctions in the presence of classification noise and give empirical evidence of our assumptions. We give theoretical results for the improvement of Statistical Query learning algorithms from positive and unlabeled data. Lastly, we apply these ideas to tree induction algorithms. We modify the code of C4.5 to get an algorithm which takes as input a set LAB of labeled examples, a set POS of positive examples and a set UNL of unlabeled data and which uses these three sets to construct the decision tree. We provide experimental results based on data taken from UCI repository which confirm the relevance of this approach. [ABSTRACT FROM AUTHOR]

We introduce a new model for learning in the presence of noise, which we call the Nasty Noise model. This model generalizes previously considered models of learning with noise. The learning process in this model, which is a variant of the PAC model, proceeds as follows: Suppose that the learning algorithm during its execution asks for m examples. The examples that the algorithm gets are generated by a nasty adversary that works according to the following steps. First, the adversary chooses m examples (independently) according to the fixed (but unknown to the learning algorithm) distribution D as in the PAC-model. Then the powerful adversary, upon seeing the specific m examples that were chosen (and using his knowledge of the target function, the distribution D and the learning algorithm), is allowed to remove a fraction of the examples at its choice, and replace these examples by the same number of arbitrary examples of its choice; the m modified examples are then given to the learning algorithm. The only restriction on the adversary is that the number of examples that the adversary is allowed to modify should be distributed according to a binomial distribution with parameters η (the noise rate) and m. On the negative side, we prove that no algorithm can achieve accuracy of ∈ > 2η in learning any non-trivial class of functions. On the positive side, we show that a polynomial (in the usual parameters, and in ∈ − 2η) number of examples suffice for learning any class of finite VC-dimension with accuracy ∈ > 2η. This algorithm may not be efficient; however, we also show that a fairly wide family of concept classes can be efficiently learned in the presence of nasty noise. [ABSTRACT FROM AUTHOR]

This paper proposes a new framework of knowledge revision, called Similarity-Driven Knowledge Revision. Our revision is invoked based on a similarity observation by users and is intended to match with the observation. Particularly, we are concerned with a revision strategy according to which an inadequate variable typing in describing an object-oriented knowledge base is revised by specializing the typing to more specific one without loss of the original inference power. To realize it, we introduce a notion of extended sorts that can be viewed as a concept not appearing explicitly in the original knowledge base. If a variable typing with some sort is considered over-general, the typing is modified by replacing it with more specific extended sort. Such an extended sort can efficiently be identified by forward reasoning with SOL-deduction from the original knowledge base. Some experimental results show the use of SOL-deduction can drastically improve the computational efficiency. [ABSTRACT FROM AUTHOR]

Some authors have repeatedly pointed out that the use of the accuracy, in particular for comparing classifiers, is not adequate. The main argument discusses the validity of some assumptions underlying the use of this criterion. In this paper, we study the hardness of the accuracy's replacement in various ways, using a framework very sensitive to these assumptions: Inductive Logic Programming. Replacement is investigated in three ways: completion of the accuracy with an additional requirement, replacement of the accuracy by the ROC analysis, recently introduced from signal detection theory, and replacement of the accuracy by a single criterion. We prove strong hardness results for most of the possible replacements. The major point is that allowing arbitrary multiplication of clauses appears to be totally useless. Another point is the equivalence in difficulty of various criteria. In contrast, the accuracy criterion appears to be tractable in this framework. [ABSTRACT FROM AUTHOR]