Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Some inductive learning systems enable structural descriptions of examples, based on elementary entities whose value can be either symbolic or numerical. This paper studies such systems, especially the ones that use a similarity measure defined between elementary entities. As it is the case in our system [12], [13], in a learning process, the matching step leads to a generalization of the training set. The main benefit of a similarity based matching step is to enable symbolic as well as numeric values processing. Given a pair of examples, learning algorithms using a similarity measure begin with computing this measure for all entities pairs taken in both examples. When it comes to choosing which entities are to be associated, a greedy method is used: entities are associated by pairs in decreasing similarity order. This paper proposes an alternative to this greedy choice based on a network flow algorithm providing an optimal result, according to the given similarity function. Furthermore, we study a generalization of this approach and we show the general case to be NP-complete. After a discussion on theoretical and practical use of the optimal method, we give some directions for further works.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Mustafa Akgül, A genuinely polynomial primal simplex algorithm for the assignment problem, Discrete Applied Mathematics, v.45 n.2, p.93-115, Aug. 17, 1993 [doi>10.1016/0166-218X(93)90054-R]
• 3: J.P Barthelemy and A Cobstein, "Complexité algorithmique et problèmes de communication", Masson/CNET-ENST, 1992.
• 4: C Berge, "Théorie des graphes et ses applications", Dunod, 1963.
• 5: G Bisson, "Une mesure de similarite pour apprender en LPO", Proceedings of RFIA 91, 1991.
• 6: G Bisson, "Learning in FOL with a similarity measure", Proceedings of AAAI, 1992.
• 7: M Botta and A Giordana, "SMART+ : A multistartegy learning tool", proceedings of 13th International Joint Conference on Artificial Intelligence (IJCAI), 1993.
• 8: E Diday, "Knowledge representation and symbolic data analysis", proceedings of 2nd international workshop in data expert knowledge and decision, 1989.
• 9: Floriana Esposito , Donato Malerba , Giovanni Semeraro, Classification in Noisy Environments Using a Distance Measure Between Structural Symbolic Descriptions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.3, p.390-402, March 1992 [doi>10.1109/34.120333]
• 10: J.G Ganascia, "Agape et Charade: Deux techniques d'apprentissage symbolique appliquees a la construction de bases de connaissances", Phd Universite de Paris-Sud, 1987.
• 11: M Gondran and M Minoux, "Graphes et Algorithmes", Eyrolles, 1990.
• 12: M Liquière and J Sallantin, "INNE (INduction in NEtworks) A structural learning algorithm for noisy examples", Proceedings of the 4th European Working Session on Learning (EWSL), Morgan Kaufmann, 1989, pp. 111--123.
• 13: M Liquière, "Graphs and structural similarities", Proceedings of IFCS'93, New approaches in Classification and Data Analysis, Studies in Classification, Data Analysis and Knowledge Acquisition, Springer Verlag, 1993.
• 14: M Minoux, "Programmation mathématique, théorie et algorithmes", Dunod, volume 1, 1983.
• 15: B Roy, "Algebre moderne et theorie des graphes", Dunod, volume 1:2, 1970.
• 16: J. F. Sowa, Conceptual structures: information processing in mind and machine, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 17: Christel Vrain, OGUST: a system that learns using domain properties expressed as the theorems, Machine learning: an artificial intelligence approach volume III, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990