N. V. Findler Some Techniques of Reducing the Dangers of Combinatorial Explosion in Automatic Knowledge Acquisition Le danger d'explosion combinatoire reste probablement le plus sérieux inconvénient pour utiliser des systèmes à base de con­ naissances 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 con­ naissances, 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 com­ posantes 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 vari­ ables 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 fonction­ nelles de variables cachées (les variables cachées peuvent-être observées et mesurées seulement de façon intermitente à des in­ tervalles 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 proba­ bilistes, potentiellement causales, entre les valeurs connues des variables cachées et certaines propriétés mathématiques des dis­ tributions 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 dan­ ger d'explosion combinatoire dans l'acquisition des connais­ sances. Finalement, remarquons que les décideurs humains parais­ sent 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. The danger of getting into a combinatorial explosion has re­ mained 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 realis­ tic and manageable size - without jeopardizing the success of finding satisfactory solutions. This paper describes some tech­ niques 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 de­ cision 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 combina­ torial explosion with the QO include selecting the most indepen­ dent (near-orthogonal) decision variables, chunking conceptually coherent decision variables, eliminating statistical outlier val­ ues, and using dynamically evolving experimental designs to re­ sult 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 vari­ ables can be observed and measured only intermittently and at ir­ regular points of time and space - in contrast with open vari­ ables whose values can be identified at any time and location.) The estimation is based on generalized production rules express­ ing stochastic and potentially causal relations between known values of hidden variables and certain mathematical properties of the open variable distribution. A multi-dimensional learning pro­ cess 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 knowl­ edge 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.