Une nouvelle approche basée sur le treillis de Galois, pour l'apprentissage de concepts

Mephu Nguifo, Engelbert

Mathématiques informatique et sciences humaines, Tome 124 (1993), pp. 19-38.

L'apprentissage automatique à partir d'exemples consiste généralement à caractériser un ensemble d'objets dénotant un concept. Nous avons développé deux méthodes d'apprentissage symbolique, LEGAL et LEGAL-E, qui s'appuient sur le même modèle d'apprentissage, et utilisent une technique de généralisation descendante, basée sur la logique des propositions et sur la structure de treillis de Galois, pour produire un ensemble de descriptions structurées et ordonnées. Elles diffèrent dans leur approche de production de connaissances. Pour des raisons de complexité, seules deux variantes de LEGAL-E sont évaluées sur le problème de la prédiction de sites de jonctions introns-exons. Une comparaison à d'autres méthodes montrent que nos résultats sont meilleurs que ceux obtenus avec des méthodes symboliques, et sont relativement comparables à ceux des meilleures méthodes neuronales. Nous montrons enfin que LEGAL-E peut être vu comme un réseau de neurones multi-couches, simple et dynamique.

The main goal of machine learning systems is to characterise a concept denoted by a set of examples. We have designed and implemented a symbolic-based method, LEGAL, which uses a top-down generalisation mecanism based on propositional logic and Galois lattice structure, to build a set of ordered and structured descriptions. Its major drawback relies on its time and space complexity when building learned knowledge. Our goal in this paper is to present a new learning method LEGAL-E which uses a different approach allowing to reduce this drawback. Two variants of this method are tested onto the problem of splice junction sites prediction on primate genetic sequences. A comparison to others machine learning systems shows that our results are far better than those obtained with symbolic representation, and are as good as the best neural networks-based ones. We finally show that LEGAL-E can be assimilated to a simple and dynamic multi-layer neural network method.

Barbut M., Monjardet B., Ordre et Classification, Algèbre et Combinatoire, T.1, Chap.4: "Fermetures, Correspondances de Galois, Treillis d'une corresp.", Paris, Hachette 1970. | Zbl

Bordat J.P., "Calcul pratique du treillis de Galois d'une correspondance", Math. Sci. Hum., 24ème année, n° 96, 1986, pp 31-47. | Numdam | MR | Zbl

Duquenne V., Guigues J.-L. "Familles minimales d'implications informatives resultant d'un tableau de données binaires", Math. Sci. Hum., n°95, 1986, pp.5-18. | Numdam | MR

Ganascia J.G., "CHARADE : une sémantique cognitive pour les heuristiques d'apprentissage ", Proc. of the 8th international conf. of Experts Systems and their Applications, Avignon, 1988, pp.567-586.

Godin R., "Complexité de Structures de Treillis", Ann. Sci. Math., Québec, vol.13, n°1, 1989, pp.19-38. | MR | Zbl

Godin R., Missaoui R., Alaoui H., "Learning Algorithms using a Galois Lattice Structure", Proc. of the 1991 IEEE Int. Conf. on Tools for AI, San José, CA, November 1991, pp.22-29.

Guénoche A., "Construction du treillis de Galois d'une relation binaire", Math. Inf. Sci. Hum., n°109, 1991, pp.5-47. | Numdam | Zbl

Kodratoff Y., "Recent Advances in Machine Learning", The Intl. Journal of Pattern Recognition and Artificial Intelligence, vol.7, 1993, pp.469-511.

Lagrange M.S., Renaud M., Mephu Nguifo E., Sallantin J., "Apprentissage automatique et typologie. PLATA: une expérience d'acquisition de connaissances dans le domaine de la céramique archéologique", Rapport de recherche LIRMM, n°93-103, Décembre 1993.

Liquiere M., Mephu Nguifo E., "LEGAL : LEarning with GAlois Lattice", 5th JFA Proceedings, 1990, pp.93-113.

Mephu Nguifo E., "Improvement and Control of Similarity-Based Decision for Knowledge Acquisition", Proceedings of the first African Conference on Research in Computer Science, Yaoundé (Cameroun), October 14-20 1992, pp.173-184, Ed. M. Tchuenté, INRIA.

Mephu Nguifo E., "Concevoir une abstraction à partir de ressemblances", Thèse de Doctorat, Université de Montpellier II (USTL), 11 Mai 1993.

Mephu Nguifo E., Sallantin J., "Prediction of primate splice junction gene sequences with a cooperative knowledge acquisition system", Proc. of the 1st International Conference on Intelligent Systems for Molecular Biology, Washington DC, July 7-9 1993, Eds. L. Hunter, D. Searls, and J. Shavlik, AAAI/MIT Press, Menlo Park CA.

Michalski R.S., Kodratoff Y., "Research in Machine Learning.: Recent progress, classification of methods, and future directions", Machine Learning: an AI approach, Kodratoff & Michalski eds, M.Kaufman, 1990, pp.1-30.

Noordewier M.O., Towell G.G., Shavlik J.W., "Training Knowledge-Based Neural Networks to Recognize Genes in DNA sequences", Advances in Neural Informat° Processing Systems, vol.3, 1991, M. Kaufmann.

Quinlan J.R., "Induction of Decisions Trees", Machine Learning, Mitchell & al. Eds, vol.1, 1986, pp.81-106.

Quinqueton J., Sallantin J., "CALM: Constestation for Argumentative Learning Machine", Machine Learning, a Guide to current Research, T.M.Mitchell & al. Eds, 1986, pp.247-253.

Towell G.G., Shavlik J.W., "Interpretation of Artificial Neural Networks : Mapping Knowledge-based Neural Networks into Rules", Advances in Neural Informat° Processing Systems, vol.4, 1992, M Kaufman.

Wille R., "Restructuring Lattice Theory : an Approach Based on Hierarchies of Concepts",, in Ordered Sets (ed. I. Rival), D. Reidel, Dordrecht, 1982, pp.445-470. | MR | Zbl

Wille R., "Concept Lattices & Conceptual Knowledge Systems", Comp. Math. App., vol.23, n°6-9, 1992, pp.493-515. | Zbl