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

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.