MOTIVATION: Microarray experiments that allow simultaneous expression profiling of thousands of genes in various conditions (tissues, cells or time) generate data whose analysis raises difficult problems. In particular, there is a vast disproportion between the number of attributes (tens of thousands) and the number of examples (several tens). Dimension reduction is therefore a key step before applying classification approaches. Many methods have been proposed to this purpose, but only a few of them considered a direct quantification of transcriptional interactions. We describe and experimentally validate a new dimension reduction and feature construction method, which assesses interactions between expression profiles to improve microarray-based classification accuracy. RESULTS: Our approach relies on a mutual information measure that exposes some elementary constituents of the information contained in a pair of gene expression profiles. We show that their analysis implies a term that represents the information of the interaction between the two genes. The principle of our method, called FeatKNN, is to exploit the information provided by highly synergic gene pairs to improve classification accuracy. First, a heuristic search selects the most informative gene pairs. Then, for each selected pair, a new feature, representing the classification margin of a KNN classifier in the gene pairs space, is constructed. We show experimentally that the interactional information has a degree of significance comparable to that of the gene expression profiles considered separately. Our method has been tested with different classifiers and yielded significant improvements in accuracy on several public microarray databases. Moreover, a synthetic assessment of the biological significance of the concept of synergic gene pairs suggested its ability to uncover relevant mechanisms underlying interactions among various cellular processes.

Properties of ensemble classification can be studied using the framework of Monte Carlo stochastic algorithms. Within this framework it is also possible to define a new ensemble classifier, whose accuracy probability distribution can be computed exactly. This paper has two goals: first, an experimental comparison between the theoretical predictions and experimental results; second, a systematic comparison between bagging and Monte Carlo ensemble classification.

In this paper we extend previous results providing a theoretical analysis of a new Monte Carlo ensemble classifier. The framework allows us to characterize the conditions under which the ensemble approach can be expected to outperform the single hypothesis classifier. Moreover, we provide a closed form expression for the distribution of the true ensemble accuracy, as well as of its mean and variance. We then exploit this result in order to analyze the expected error behavior in a particularly interesting case.

The “universal suffrage” selection operator, designed primarily for concept learning inside the system REGAL, is discussed for both overlapping and nonoverlapping populations. Analysis of its behavior is performed by using the “virtual average population” method, a new tool for investigating asymptotic properties of convergence of macroscopic quantities related to the population of a genetic algorithm.

In this paper we show, in a constructive way, that there are problems for which the use of genetic algorithm based learning systems can be at least as effective as traditional symbolic or connectionist approaches. To this aim, the system REGAL is briefly described, and its application to two classical benchmarks for machine learning is discussed, by comparing the results with the best ones published in the literature.

The computational learning approach shows that the concept descriptions acquired from examples are approximately correct with a degree of probability that grows with the size of the training sample. The same problem has also been widely investigated in the field of pattern recognition under a variety of problem settings. Some of the results obtained in both fields are surveyed and compared, and the limits of their applicability are analyzed. Moreover, new and tighter bounds for the growth function of some classes of Boolean formulas are presented.>

The results of extensive experimentation aimed at assessing the concrete possibilities of automatically building a diagnostic expert system, to be used in-field in an industrial domain, by means of machine learning techniques, are described. The system, ENIGMA, is an incremental version of the ML-SMART system, which acquires a network of first-order logic rules, starting from a set of classified examples and a domain theory. An application is described that consists of discovering malfunctions in electromechanical apparatus. ENIGMA's efficacy in acquiring sophisticated knowledge and handling complex structured examples is largely due to its underlying database management system, which supports the learning operators, defined at the abstract level, with a set of primitives, taken from the field of deductive databases. An expert system, MEPS, devoted to the same task, has also been manually developed. A number of comparisons along different dimensions of the manual and automatic development process have been possible, allowing some practical indications to be suggested.>

A semiautomated methodology for eliciting knowledge from an expert is described. The methodology suggests the use of a manual interview technique and the application of a machine learning program to structure the elicited information. This way the experts are free to express their knowledge in a familiar format. Automated processing helps the knowledge engineer formalize knowledge. This interaction between manual and automatic techniques is particularly useful when the expert meets with difficulties in formulating general rules and prefers, instead, to reason by cases. The application of the methodology to an image interpretation task, namely speech spectrogram reading, is described as a test case.>

A system that performs automated concept acquisition from examples and has been specially designed to work in noisy environments is presented. The learning methodology is aimed at the target problem of finding discriminant descriptions of a given set of concepts and uses both examples and counterexamples. The learned knowledge is expressed in the form of production rules, organized into separate clusters, linked together in a graph structure. Knowledge extraction is guided by a top-down control strategy, through a process of specialization. The system also utilizes a technique of problem reduction to contain the computational complexity. Several criteria are proposed for evaluating the acquired knowledge. The methodology has been tested on a problem in the field of speech recognition and the experimental results obtained are reported and discussed.>

This paper surveys a long term project, aimed at providing a general methodology for building up and maintaining an expert system oriented to Pattern Recognition problems. The methodology makes use of an integrated set of modules, performing different functions but sharing a common knowledge representation scheme. In particular, a learning module allows to acquire the knowledge automatically from a set of examples and another module performs sophisticated reasoning, on the basis of the available knowledge, during the recognition phase.

This paper describes a method for performing knowledge base (re)organization in Expert Systems oriented to classification, interpretation and diagnosis problems. The methodology can be applied either to the input descriptions of a set of samples, giving thus a preliminary characterization of groups of samples, or to a set of intermediate level descriptions, supplied by a human expert or previously automatically learned. An example of application is also given. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The relevance of the Semantics for a Speech Understanding System (SUS) was pointed out by many authors and is by now a classic topic. The present work contains an implementation of a semantic analysis for the SUS of the CENS, in Turin. The semantic knowledge is contained in a graph on which a set of fuzzy relations is defined. The semantic algorithm accepts, as input, a table of alternative weighted words, found in the processed spectrogram at phonological and lexical level. The output is a sentence assumed as the "best" interpretation of the whole spectrogram. The algorithm is implemented in FORTRAN and PL1 on a IBM 370/158 and it utilizes a recursive evaluation function for the concurrent hypotheses. We compare experimentally the efficiency of the algorithm, by varying the number of alternative input words and their weight, the number of vertices and arcs of the semantic graph and the evaluation function. The results show a good performance of this pure semantic analysis.