Constructing fuzzy graphs from examples

Methods to build function approximators from example data have gained considerable interest in the past. Especially methodologies that build models that allow an interpretation have attracted attention. Most existing algorithms, however, are either complicated to use or infeasible for high-dimensional problems. This article presents an efficient and easy to use algorithm to construct fuzzy graphs from example data. The resulting fuzzy graphs are based on locally independent fuzzy rules that operate solely on selected, important attributes. This enables the application of these fuzzy graphs also to problems in high dimensional spaces. Using illustrative examples and a real world data set it is demonstrated how the resulting fuzzy graphs offer quick insights into the structure of the example data, that is, the underlying model. The underlying algorithm is demonstrated using several Java applets, which can be found under ‘Electronic annexes’ on www.elsevier.com/locate/ida.     

Topology constraint free fuzzy gated neural networks for patternrecognition

A novel topology constraint free neural network architecture using a generalized fuzzy gated neuron model is presented for a pattern recognition task. The main feature is that the network does not require weight adaptation at its input and the weights are initialized directly from the training pattern set. The elimination of the need for iterative weight adaptation schemes facilitates quick network set up times which make the fuzzy gated neural networks very attractive. The performance of the proposed network is found to be functionally equivalent to spatio-temporal feature maps under a mild technical condition. The classification performance of the fuzzy gated neural network is demonstrated on a 12-class synthetic three dimensional (3-D) object data set, real-world eight-class texture data set, and real-world 12 class 3-D object data set. The performance results are compared with the classification accuracies obtained from a spatio-temporal feature map, an adaptive subspace self-organizing map, multilayer feedforward neural networks, radial basis function neural networks, and linear discriminant analysis. Despite the network's ability to accurately classify seen data and adequately generalize validation data, its performance is found to be sensitive to noise perturbations due to fine fragmentation of the feature space. This paper also provides partial solutions to the above robustness issue by proposing certain improvements to various modules of the proposed fuzzy gated neural network.     

Adaptive fuzzy leader clustering of complex data sets in patternrecognition

A modular, unsupervised neural network architecture that can be used for clustering and classification of complex data sets is presented. The adaptive fuzzy leader clustering (AFLC) architecture is a hybrid neural-fuzzy system that learns online in a stable and efficient manner. The system used a control structure similar to that found in the adaptive resonance theory (ART-1) network to identify the cluster centers initially. The initial classification of an input takes place in a two-stage process: a simple competitive stage and a distance metric comparison stage. The cluster prototypes are then incrementally updated by relocating the centroid position from fuzzy C-means (FCM) system equations for the centroids and the membership values. The operational characteristics of AFLC and the critical parameters involved in its operation are discussed. The AFLC algorithm is applied to the Anderson iris data and laser-luminescent finger image data. The AFLC algorithm successfully classifies features extracted from real data, discrete or continuous, indicating the potential strength of this new clustering algorithm in analyzing complex data sets.     

Learning production systems from examples

This paper describes a program that learns production systems. The user presents examples consisting of inputs together with the required program output for each. If the productions in their current form would result in the output specified by the user for each input, no learning is needed. Otherwise the program must modify the production system so that it produces the correct output. The productions take arbitrary strings of LISP atoms as input and produce characterizations of them as output. Such a characterization can be as simple as the name of a concept to which the string belongs, but may involve the assertion of many properties and relations describing the input.     

Self-organized fuzzy system generation from training examples

In the synthesis of a fuzzy system two steps are generally employed: the identification of a structure and the optimization of the parameters defining it. The paper presents a methodology to automatically perform these two steps in conjunction using a three-phase approach to construct a fuzzy system from numerical data. Phase 1 outlines the membership functions and system rules for a specific structure, starting from a very simple initial topology. Phase 2 decides a new and more suitable topology with the information received from the previous step; it determines for which variable the number of fuzzy sets used to discretize the domain must be increased and where these new fuzzy sets should be located. This, in turn, decides in a dynamic way in which part of the input space the number of fuzzy rules should be increased. Phase 3 selects from the different structures obtained to construct a fuzzy system the one providing the best compromise between the accuracy of the approximation and the complexity of the rule set. The accuracy and complexity of the fuzzy system derived by the proposed self-organized fuzzy rule generation procedure (SOFRG) are studied for the problem of function approximation. Simulation results are compared with other methodologies such as artificial neural networks, neuro-fuzzy systems, and genetic algorithms     

Learning from positive and unlabeled examples

In many machine learning settings, labeled examples are difficult to collect while unlabeled data are abundant. Also, for some binary classification problems, positive examples which are elements of the target concept are available. Can these additional data be used to improve accuracy of supervised learning algorithms? We investigate in this paper the design of learning algorithms from positive and unlabeled data only. Many machine learning and data mining algorithms, such as decision tree induction algorithms and naive Bayes algorithms, use examples only to evaluate statistical queries (SQ-like algorithms). Kearns designed the statistical query learning model in order to describe these algorithms. Here, we design an algorithm scheme which transforms any SQ-like algorithm into an algorithm based on positive statistical queries (estimate for probabilities over the set of positive instances) and instance statistical queries (estimate for probabilities over the instance space). We prove that any class learnable in the statistical query learning model is learnable from positive statistical queries and instance statistical queries only if a lower bound on the weight of any target concept f can be estimated in polynomial time. Then, we design a decision tree induction algorithm POSC4.5, based on C4.5, that uses only positive and unlabeled examples and we give experimental results for this algorithm. In the case of imbalanced classes in the sense that one of the two classes (say the positive class) is heavily underrepresented compared to the other class, the learning problem remains open. This problem is challenging because it is encountered in many real-world applications.     

Learning recursive languages from good examples

We study learning of indexable families of recursive languages from good examples. We show that this approach can be considerably more powerful than learning from all examples and point out reasons for this additional power. We present several characterizations of types of learning from good examples. We derive similarities as well as differences to learning of recursive functions from good examples. This revised version was published online in June 2006 with corrections to the Cover Date.     

Learning from examples with unspecified attribute values

A challenging problem within machine learning is how to make good inferences from data sets in which pieces of information are missing. While it is valuable to have algorithms that perform well for specific domains, to gain a fundamental understanding of the problem, one needs a “theory” about how to learn with incomplete data. The important contribution of such a theory is not so much the specific algorithmic results, but rather that it provides good ways of thinking about the problem formally. In this paper we introduce the unspecified attribute value (UAV) learning model as a first step towards a theoretical framework for studying the problem of learning from incomplete data in the exact learning framework.In the UAV learning model, an example x is classified positive (resp., negative) if all possible assignments for the unspecified attributes result in a positive (resp., negative) classification. Otherwise the classification given to x is “?” (for unknown). Given an example x in which some attributes are unspecified, the oracle UAV-MQ responds with the classification of x. Given a hypothesis h, the oracle UAV-EQ returns an example x (that could have unspecified attributes) for which h(x) is incorrect.We show that any class of functions learnable in Angluin’s exact model using the MQ and EQ oracles is also learnable in the UAV model using the MQ and UAV-EQ oracles as long as the counterexamples provided by the UAV-EQ oracle have a logarithmic number of unspecified attributes. We also show that any class learnable in the exact model using the MQ and EQ oracles is also learnable in the UAV model using the UAV-MQ and UAV-EQ oracles as well as an oracle to evaluate a given boolean formula on an example with unspecified attributes. (For some hypothesis classes such as decision trees and unate formulas the evaluation can be done in polynomial time without an oracle.) We also study the learnability of a universal class of decision trees under the UAV model and of DNF formulas under a representation-dependent variation of the UAV model.     

Feature extraction from wavelet coefficients for patternrecognition tasks

An efficient feature extraction method based on the fast wavelet transform is presented. The paper especially deals with the assessment of process parameters or states in a given application using the features extracted from the wavelet coefficients of measured process signals. Since the parameter assessment using all wavelet coefficients will often turn out to be tedious or leads to inaccurate results, a preprocessing routine that computes robust features correlated to the process parameters of interest is highly desirable. The method presented divides the matrix of computed wavelet coefficients into clusters equal to row vectors. The rows that represent important frequency ranges (for signal interpretation) have a larger number of clusters than the rows that represent less important frequency ranges. The features of a process signal are eventually calculated by the Euclidean norms of the clusters. The effectiveness of this new method has been verified on a flank wear estimation problem in turning processes and on a problem of recognizing different kinds of lung sounds for diagnosis of pulmonary diseases     

Learning probabilistic logic models from probabilistic examples

We revisit an application developed originally using abductive Inductive Logic Programming (ILP) for modeling inhibition in metabolic networks. The example data was derived from studies of the effects of toxins on rats using Nuclear Magnetic Resonance (NMR) time-trace analysis of their biofluids together with background knowledge representing a subset of the Kyoto Encyclopedia of Genes and Genomes (KEGG). We now apply two Probabilistic ILP (PILP) approaches—abductive Stochastic Logic Programs (SLPs) and PRogramming In Statistical modeling (PRISM) to the application. Both approaches support abductive learning and probability predictions. Abductive SLPs are a PILP framework that provides possible worlds semantics to SLPs through abduction. Instead of learning logic models from non-probabilistic examples as done in ILP, the PILP approach applied in this paper is based on a general technique for introducing probability labels within a standard scientific experimental setting involving control and treated data. Our results demonstrate that the PILP approach provides a way of learning probabilistic logic models from probabilistic examples, and the PILP models learned from probabilistic examples lead to a significant decrease in error accompanied by improved insight from the learned results compared with the PILP models learned from non-probabilistic examples.     

Learning Bayesian classifiers from positive and unlabeled examples

The positive unlabeled learning term refers to the binary classification problem in the absence of negative examples. When only positive and unlabeled instances are available, semi-supervised classification algorithms cannot be directly applied, and thus new algorithms are required. One of these positive unlabeled learning algorithms is the positive naive Bayes (PNB), which is an adaptation of the naive Bayes induction algorithm that does not require negative instances. In this work we propose two ways of enhancing this algorithm. On one hand, we have taken the concept behind PNB one step further, proposing a procedure to build more complex Bayesian classifiers in the absence of negative instances. We present a new algorithm (named positive tree augmented naive Bayes, PTAN) to obtain tree augmented naive Bayes models in the positive unlabeled domain. On the other hand, we propose a new Bayesian approach to deal with the a priori probability of the positive class that models the uncertainty over this parameter by means of a Beta distribution. This approach is applied to both PNB and PTAN, resulting in two new algorithms. The four algorithms are empirically compared in positive unlabeled learning problems based on real and synthetic databases. The results obtained in these comparisons suggest that, when the predicting variables are not conditionally independent given the class, the extension of PNB to more complex networks increases the classification performance. They also show that our Bayesian approach to the a priori probability of the positive class can improve the results obtained by PNB and PTAN.     

Learning rules for graph transformations by induction from examples

The input to the described program, in learning mode, consists of examples of starting graph and result graph pairs. The starting graph is transformable into the result graph by adding or deleting certain edges and vertices. The essential common features of the starting graphs are stored together with specifications of the edges and vertices to be deleted or added. This latter information is obtained by mapping each starting graph onto the corresponding result graph. On subsequent input of similar starting graphs without a result graph, the program, in performance mode, recognizes the characterizing set of features in the starting graph and can perform the proper transformation on the starting graph to obtain the corresponding result graph. The program also adds the production to its source code so that after recompilation it is permanently endowed with the new production. If any feature which lacks the property "ordinary" is discovered in the starting graph and only one example has been given, then there is feedback to the user including a request for more examples to ascertain whether the extraordinary property is a necessary part of the situation.     

Learning rules from incomplete training examples by rough sets

Machine learning can extract desired knowledge from existing training examples and ease the development bottleneck in building expert systems. Most learning approaches derive rules from complete data sets. If some attribute values are unknown in a data set, it is called incomplete. Learning from incomplete data sets is usually more difficult than learning from complete data sets. In the past, the rough-set theory was widely used in dealing with data classification problems. In this paper, we deal with the problem of producing a set of certain and possible rules from incomplete data sets based on rough sets. A new learning algorithm is proposed, which can simultaneously derive rules from incomplete data sets and estimate the missing values in the learning process. Unknown values are first assumed to be any possible values and are gradually refined according to the incomplete lower and upper approximations derived from the given training examples. The examples and the approximations then interact on each other to derive certain and possible rules and to estimate appropriate unknown values. The rules derived can then serve as knowledge concerning the incomplete data set.     

Learning tree languages from positive examples and membership queries

We investigate regular tree languages’ exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [D. Angluin, A note on the number of queries needed to identify regular languages, Information and Control 51 (1981) 76–87] for the case of regular word languages. Neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm.     

Learning fuzzy rules from fuzzy samples based on rough set technique

Although the traditional rough set theory has been a powerful mathematical tool for modeling incompleteness and vagueness, its performance in dealing with initial fuzzy data is usually poor. This paper makes an attempt to improve its performance by extending the traditional rough set approach to the fuzzy environment. The extension is twofold. One is knowledge representation and the other is knowledge reduction. First, we provide new definitions of fuzzy lower and upper approximations by considering the similarity between the two objects. Second, we extend a number of underlying concepts of knowledge reduction (such as the reduct and core) to the fuzzy environment and use these extensions to propose a heuristic algorithm to learn fuzzy rules from initial fuzzy data. Finally, we provide some numerical experiments to demonstrate the feasibility of the proposed algorithm. One of the main contributions of this paper is that the fundamental relationship between the reducts and core of rough sets is still pertinent after the proposed extension.     

Learning text editing tasks from examples: a procedural approach

Reformatting blocks of semi-structured information is a common editing task that typically involves highly repetitive action sequences, but ones where exceptional cases arise constantly and must be dealt with as they arise. This paper describes a procedural programming-by-example approach to repetitive text editing which allows users to construct programs within a standard editing interface and extend them incrementally. Following a brief practice period during which they settle on an editing strategy for the task at hand, users commence editing in the normal way. Once the first block of text has been edited, they inform the learning system which constructs a generalized procedure from the actions that have been recorded. The system then attempts to apply the procedure to the next block of text, by predicting editing actions and displaying them for confirmation. If the user accepts a prediction, the action is carried out (and the program may be generalized accordingly); otherwise the user is asked to intervene and supply additional information, in effect debugging the program on the fly. A pilot implementation is described that operates in a simple interactive point-and-click editor (Macintosh MINI-EDIT), along with its performance on three sample tasks. In one case the procedure was learned correctly from the actions on the first text block, while in the others minor debugging was needed on subsequent text blocks. In each case a much smaller number of both keystrokes and mouse-clicks was required than with normal editing, without the system making any prior assumptions about the stucture of the text except for some general knowledge about lexical patterns. Although a smooth interactive interface has not yet been constructed, the results obtained serve to indicate the potential of this approach for semi-structured editing tasks.     

Learning text editing tasks from examples: a procedural approach

Abstract

Reformatting blocks of semi-structured information is a common editing task that typically involves highly repetitive action sequences, but ones where exceptional cases arise constantly and must be dealt with as they arise. This paper describes a procedural programming-by-example approach to repetitive text editing which allows users to construct programs within a standard editing interface and extend them incrementally. Following a brief practice period during which they settle on an editing strategy for the task at hand, users commence editing in the normal way. Once the first block of text has been edited, they inform the learning system which constructs a generalized procedure from the actions that have been recorded. The system then attempts to apply the procedure to the next block of text, by predicting editing actions and displaying them for confirmation. If the user accepts a prediction, the action is carried out (and the program may be generalized accordingly); otherwise the user is asked to intervene and supply additional information, in effect debugging the program on the fly. A pilot implementation is described that operates in a simple interactive point-and-click editor (Macintosh MINI-EDIT), along with its performance on three sample tasks. In one case the procedure was learned correctly from the actions on the first text block, while in the others minor debugging was needed on subsequent text blocks. In each case a much smaller number of both keystrokes and mouse-clicks was required than with normal editing, without the system making any prior assumptions about the stucture of the text except for some general knowledge about lexical patterns. Although a smooth interactive interface has not yet been constructed, the results obtained serve to indicate the potential of this approach for semi-structured editing tasks.     

Learning naive Bayes classifiers from positive and unlabelled examples with uncertainty

Traditional classification algorithms require a large number of labelled examples from all the predefined classes, which is generally difficult and time-consuming to obtain. Furthermore, data uncertainty is prevalent in many real-world applications, such as sensor network, market analysis and medical diagnosis. In this article, we explore the issue of classification on uncertain data when only positive and unlabelled examples are available. We propose an algorithm to build naive Bayes classifier from positive and unlabelled examples with uncertainty. However, the algorithm requires the prior probability of positive class, and it is generally difficult for the user to provide this parameter in practice. Two approaches are proposed to avoid this user-specified parameter. One approach is to use a validation set to search for an appropriate value for this parameter, and the other is to estimate it directly. Our extensive experiments show that the two approaches can basically achieve satisfactory classification performance on uncertain data. In addition, our algorithm exploiting uncertainty in the dataset can potentially achieve better classification performance comparing to traditional naive Bayes which ignores uncertainty when handling uncertain data.