Search

Finding hidden temporal structures from event sequences is a difficult task, particularly when events occur irregularly over time and temporal dependencies may exist in a long time horizon. The tasks involved are not only to find event patterns represented in the form of temporal orders, but more importantly to find patterns that are described with precise time conditions and rules that can be applied to predict when a future event will occur. Recent study has shown that a new approach based on learning temporal regions is a good solution for this problem. This paper investigates this approach in a greater depth and makes several improvements. It introduces multiple rule selection methods to better uncover hidden relations. It also introduces heuristic rule pruning methods to speed up search to solve large-scale problems. Experimental results are presented which show the effectiveness of the new methods. [ABSTRACT FROM AUTHOR]

Data clustering and association rules discovery are two related problems in data mining. In this paper, we propose to integrate these two techniques using the frequent concept lattice data structure — a formal conceptual model that can be used to identify similarities among a set of objects based on their frequent attributes (frequent items). Experimental results show that clusterings and association rules are generated efficiently from the frequent concept lattice, since response time after lattice construction is measured almost in seconds. [ABSTRACT FROM AUTHOR]

This paper presents a new method that deals with a supervised learning task usually known as multivariate regression. The main distinguishing feature of this new technique is the use of a clustering method to obtain sub-sets of the training data before the learning phase. After this "resampling" process a different regression model is fitted to each found cluster. We call the resulting method clustered partial linear regression. Predictions using this technique are preceded by a cluster membership query for each test case. The cluster membership probability of a test case is used as a weight in an averaging process that calculates the final prediction. This averaging process involves the predictions of the regression models associated to the clusters for which the test case may belong. We have tested this general multi-strategy approach using several regression techniques and we have observed significant accuracy gains in several data sets. We have also compared our method to bagging that also uses an averaging process to obtain predictions. This experiment showed that the two methods are significantly different. Finally, we present a comparison of our method with several state-of-the-art regression methods. [ABSTRACT FROM AUTHOR]

MetaCost is a recently proposed procedure that converts an error-based learning algorithm into a cost-sensitive algorithm. This paper investigates two important issues centered on the procedure which were ignored in the paper proposing MetaCost. First, no comparison was made between MetaCost's final model and the internal cost-sensitive classifier on which MetaCost depends. It is credible that the internal cost-sensitive classifier may outperform the final model without the additional computation required to derive the final model. Second, MetaCost assumes its internal cost-sensitive classifier is obtained by applying a minimum expected cost criterion. It is unclear whether violation of the assumption has an impact on MetaCost's performance. We study these issues using two boosting procedures, and compare with the performance of the original form of MetaCost which employs bagging. [ABSTRACT FROM AUTHOR]

Feature selection has received a lot of attention in the machine learning community, but mainly under the supervised paradigm. In this work we study the potential benefits of feature selection in hierarchical clustering tasks. Particularly we address this problem in the context of incremental clustering, following the basic ideas of Gennari [8]. By using a simple implementation, we show that a feature selection scheme running in parallel with the learning process can improve the clustering task under the dimensions of accuracy, efficiency in learning, efficiency in prediction and comprehensibility. [ABSTRACT FROM AUTHOR]

Boosting is a powerful method for improving the predictive accuracy of classifiers. The AdaBoost algorithm of Freund and Schapire has been successfully applied to many domains [2, 10, 12] and the combination of AdaBoost with the C4.5 decision tree algorithm has been called the best off-the-shelf learning algorithm in practice. Unfortunately, in some applications, the number of decision trees required by AdaBoost to achieve a reasonable accuracy is enormously large and hence is very space consuming. This problem was first studied by Margineantu and Dietterich [7], where they proposed an empirical method called Kappa pruning to prune the boosting ensemble of decision trees. The Kappa method did this without sacrificing too much accuracy. In this work-in-progress we propose a potential improvement to the Kappa pruning method and also study the boosting pruning problem from a theoretical perspective. We point out that the boosting pruning problem is intractable even to approximate. Finally, we suggest a margin-based theoretical heuristic for this problem. [ABSTRACT FROM AUTHOR]

In behavioural cloning of the human operator's skill, a controller is usually induced directly as a classifier from system's states into actions. Experience shows that this often results in brittle controllers. In this paper we explore a decomposition of the cloning problem into two learning problems: the learning of operator's control trajectories and the learning of the system's dynamics separately. We analyse advantages of such indirect controllers. We give characterization of the learner's error that is plausible explanation of why this decomposition approach has empirically proved to be usually superior to direct cloning. [ABSTRACT FROM AUTHOR]

This paper presents layered learning, a hierarchical machine learning paradigm. Layered learning applies to tasks for which learning a direct mapping from inputs to outputs is intractable with existing learning algorithms. Given a hierarchical task decomposition into subtasks, layered learning seamlessly integrates separate learning at each subtask layer. The learning of each subtask directly facilitates the learning of the next higher subtask layer by determining at least one of three of its components: (i) the set of training examples; (ii) the input representation; and/or (iii) the output representation. We introduce layered learning in its domain-independent general form. We then present a full implementation in a complex domain, namely simulated robotic soccer. [ABSTRACT FROM AUTHOR]

Case-based reasoning systems solve new problems by reusing previous problem solving experience stored as cases in a case-base. In recent years the maintenance problem has become an increasingly important research issue for the case-based reasoning community. In short, the goal is to develop strategies for effectively maintaining the efficiency and competence of case-based reasoning systems as they evolve. Our research has focused on the development of a model of competence for case-based reasoning systems, a model that measures the contributions of individual cases to overall system competence, and which forms the computational basis for a variety of maintenance strategies. However, while this model offers many potential advantages its upkeep adds an additional cost to the CBR cycle. In this paper we evaluate a new method for more efficiently updating the model at run-time. [ABSTRACT FROM AUTHOR]

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]