Some Techniques of Reducing the Dangers of Combinatorial Explosion in Automatic Knowledge Acquisition

N. V. Findler

IBP-Laforia 1995/30: Rapport de Recherche Laforia / Laforia research reports
10 pages - Janvier/January 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Some Techniques of Reducing the Dangers of Combinatorial Explosion in Automatic Knowledge Acquisition

Résumé : Le danger d'explosion combinatoire reste probablement le plus sérieux inconvénient pour utiliser des systèmes à base de connaissances dans des problèmes réels. Des heuristiques raisonnables doivent réduire la taille de l'espace de recherche potentiellement énorme, sans mettre en danger la possibilité de trouver une solution satisfaisante afin d'explorer des espaces réalistes et manipulables. Ce papier décrit quelques techniques qui ont prouvé leur efficacité dans deux systèmes : le quasi-optimiseur (QO) et le système général à règles de production (GPRS).
Le système QO est un outil d'acquisition automatique des connaissances, non dépendant du domaine qui peut obtenir, vérifier, déclencher et optimiser une expertise humaine. Ce système génère des modèles, des théories descriptives, des stratégies humaines de décision et peut aussi choisir et combiner les meilleures composantes de plusieurs modèles de décision dans une seule stratégie qui peut être considérée comme une théorie normative au sens théorique. Dans QO la technique développée pour réduire le danger d'explosion combinatoire comprend la sélection des variables de décision les plus indépendants (presque orthogonaux), l'agrégation des variables de décision conceptuellement cohérentes, l'élimination des variables statistiquement hors champ et l'utilisation de dispositifs évolutifs expérimentaux pour arriver à une distribution presque uniformément fiable de stratégies de réponse.
De son côté, le système GPRS peut évoluer/prévoir les valeurs des variables cachées et peut ainsi servir d'entrée d'un système expert qui nécessiterait des évolutions numériques ou fonctionnelles de variables cachées (les variables cachées peuvent-être observées et mesurées seulement de façon intermitente à des intervalles de temps et d'espaces irréguliers, contrairement aux variables ouvertes dont les valeurs peuvent êtres observées n'importe quand, n'importe où). L'estimation repose sur des règles de production généralisées exprimant des relations probabilistes, potentiellement causales, entre les valeurs connues des variables cachées et certaines propriétés mathématiques des distributions de variables ouvertes. Un processus d'apprentissage multi-dimensionnel consolide et optimise la base de règles généralisées. Le module d'apprentissage progressivement réduit en une seule les règles "suffisamment proches" et élimine celles qui sont fausses et non justifiables. Un tel processus réduit le danger d'explosion combinatoire dans l'acquisition des connaissances. Finalement, remarquons que les décideurs humains paraissent recourir à un processus identique, quoi que de manière moins systématique, quand ils sont confrontés à de trés grands espaces de décision.

Abstract : The danger of getting into a combinatorial explosion has remained probably the most serious impediment to using knowledge-based systems for real-life problems. Justifiable heuristics must cut down the size of potentially huge search spaces to a realistic and manageable size ‹ without jeopardizing the success of finding satisfactory solutions. This paper describes some techniques that have proved to be effective in the operation of two different systems: the Quasi-Optimizer (QO) and the Generalized Production Rule System (GPRS).
The QO is a domain-independent automatic knowledge acquisition tool that can obtain, verify, fuse and optimize human expertise. It generates computer models, descriptive theories, of human decision making strategies, and can also select and combine the best components of several such models into a single strategy which may be considered a normative theory in the statistical sense. The techniques developed to reduce the danger of combinatorial explosion with the QO include selecting the most independent (near-orthogonal) decision variables, chunking conceptually coherent decision variables, eliminating statistical outlier values, and using dynamically evolving experimental designs to result in a near-uniform reliability distribution of the strategy responses.
The GPRS can estimate/predict values of hidden variables and can thus serve as a module of an expert system in need of numerical or functional estimates of hidden variable values. (Hidden variables can be observed and measured only intermittently and at irregular points of time and space ‹ in contrast with open variables whose values can be identified at any time and location.) The estimation is based on generalized production rules expressing stochastic and potentially causal relations between known values of hidden variables and certain mathematical properties of the open variable distribution. A multi-dimensional learning process adds to, consolidates and optimizes the generalized rule base. It gradually merges "similar enough" production rules, and eliminates spurious and statistically not justifiable ones. Such processes reduce the danger of combinatorial explosions in knowledge acquisition.
Finally, we note that human decision makers appear to resort to similar methods, although in a less systematic manner, when they are confronted with very large decision spaces.

Publications internes Laforia 1995 / Laforia research reports 1995