Research activity in 1998
In 1998, the group continued to be active on several topics: the integration of numerical and symbolic learning techniques in First Order Logic, which led to the development of the system FONN, was expanded and a new, more powerful system, RTN, was built up. Also the work on Genetic Algorithms continued and the system G-NET has been improved and tested on several datasets.
An interesting new line of research was initiated: the study of Phase Transitions in Matching and Learning. In fact, one of the major limitations in applying relational learning is due to the complexity of verifying the inductive hypotheses, which in principle is exponential in the number of variables. Borrowed from Statistical Physics, the term «phase transition» denotes the appearance of an abrupt change in some order parameter describing a system. Recent investigations have uncovered that several classes of computationally difficult problems show a phase transition with respect to their probability of being solvable, coupled with a peak in computational complexity. This is typically true for search problems, and the phenomenon seems to be largely independent from the specific search algorithm used.
The location of the phase transition divides the problem space in three regions: One in which the probability of the existence of a solution is almost zero, and then it is «easy» to prove unsolvability. Another one, where many alternative solutions exist, and then it is «easy» to find one, and, finally, one where the probability of solution changes abruptly from almost 1 to almost 0, potentially making very difficult to find one of the existing solutions or to prove unsolvability.
Recent results described in the literature have shown that most constraint satisfaction problems (CSP) are characterized by the presence of a narrow phase transition peak, with respect to some order parameter, where the complexity rises up exponentially while remains affordable elsewhere. By means of an extensive experimental analysis, we have shown that clause verification exhibits a typical phase transition with respect to the number of binary (or greater arity) predicates, and with respect to the ratio between the number of constants in the concept instances and the cardinality of the relations. Nevertheless, also clauses laying in the phase transition region may be tractable, depending upon their structure and on the structure of the concept instances. Then, there is hope of discovering good inductive hypotheses capturing complex structural relations but verifiable within bounded computational resources. Unfortunately this property cannot be predicted on the basis of the static analysis of an order parameter but needs to go through the matching process. To this aim we have propose a method derived from the Monte Carlo algorithm theory, and based on a stochastic theorem prover, for estimating on line if a given hypotheses can be verified (or falsified) within the limits of the granted computational resources.
As concern the national projects, a subgroup has been involved in a collaboration with CSELT (the research labs of Telecom Italia) aimed at developing a tool for building an interactive module for introducing a priori knowledge in a clustering system.
1998 Publications
Anglano C., Giordana A., Lo Bello G., and Saitta L. (1998). "An Experimental Evaluation of Coevolutive Concept Learning". In Proc. 15th Int. Conference on Machine Learning (Madison, WI), pp. 19-27.
C. Anglano, A. Giordana, G. Lo Bello, and L. Saitta (1998). "Coevolutionary, Distributed Search for Inducing Concept Descriptions". In Proc.10th European Conference on Machine Learning (Chemnitz, Germany), Lecture Notes in Artificial Intelligence, Vol. 1398, 322-333.
M. Baldoni, C. Baroglio, D. Cavagnino (1998) "XFF: A simple method to eXtract Fractal Features for 2D object recognition", Proc.of the 7th International Workshop on Structural and Syntactic Pattern Recognition (SSPR-98, Sydney, Australia), Lecture Notes in Computer Science, Vol. 1451, pp. 382-389.
M. Baldoni, C. Baroglio, D. Cavagnino, L. Egidi (1998) "Learning to Classify Images by means of Iterated Function Systems", Proc.of Fractal98 (Malta), pp. 173-182.
M. Baldoni, C. Baroglio, D. Cavagnino, L. Saitta (1998) "Towards an Automatic Fractal Feature Extraction for Image Recognition", in H. Liu and H. Motoda (Eds.). "Feature Extraction, Construction and Selection", Kluwer Academic Publisher, 1998.
M. Baldoni, C. Baroglio, D. Cavagnino and L. Saitta (1998) "IFS-based feature extraction for learning to classify objects", Proc. of IAPRVA98, (Ferrara, Italy, april 1998).
M. Botta, R. Piola (1998) "Refining Numerical Terms in Structured FOL Theories", Proc. of the 4th International Workshop on Multistrategy Learning (Desenzano del Garda, Italy, 1998), pp 47-52.
M. Botta, A. Giordana, R. Piola (1998) "An Integrated Framework for Learning Numerical Terms in FOL", Proc. of the 13th European Conference on Artificial Intelligence (ECAI-98, Brighton, UK), pp. 415-419.
F. Esposito, R. Michalski and L. Saitta (Eds.) (1998). Proc. 4th Int. Workshop on Multistrategy Learning. (Desenzano del Garda, Italy, 1998).
A. Giordana, L. Saitta (1998). "Phase Transition in Learning with FOL Languages", TR 97-25, Dipartimento di Informatica, Università di Torino.
A. Giordana (1998). "A Stochastic Approach to Concept Induction". Invited Paper in F. Esposito, R. Michalski and L. Saitta (Eds.), Proc. of the 4th International Workshop on Multistrategy Learning, pag. 1, (Desenzano del Garda, Italy, 1998).
G. Lo Bello (1998) "A Coevolutionary Distributed Approach to Learning Classification Programs", PhD thesis, Universita` di Torino, Italy.
F. Neri (1998) "The Role of Explanation in Understanding Children Learning Elementary Heat Transfer Phenomena", Proc. of the 4th International Workshop on Multistrategy Learning (Desenzano del Garda, Italy, 1998), pp 116-124.
F. Neri (1998). "Simulating Children Learning and Explaining Elementary Heat Transfer Phenomena: A Multistrategy System at Work". 10th European Conference on Machine Learning, Lecture Notes in Artificial Intelligence, Vol. 1398, 67-76.
R. Piola (1998). Refinement of Knowledge Bases in First Order Logics by Means of Neural Networks, Ph.D. Thesis, Università di Torino, Italy.
M. Rossotto, L. Saitta, M. Botta (1998) "S3 (Segmentation Support System): Scelte Ingegneristiche e Architetturali per la Realizzazione del Prototipo." Documenti CSELT DLR 98.03130.
L. Saitta and J. D. Zucker (1998). "Semantic Abstraction for Concept Representation and Learning". In Proc. Int. Symposium on Abstraction, Reformulation and Approximation (Asilomar, CA), pp.103-120.
L. Saitta and F. Neri (1998). "Learning in the "Real-World"", Machine Learning, 30, 133-164.
