This work proved that EXORCISM performs well as a machine learning program on functions with a small and a medium percentage of don't cares. The data support the conclusion that EXORCISM compares favorably to Espresso in general and fills in some of its weaknesses. While EXORCISM in its present form does not minimize partial functions well, we outlined some proposed changes and have further developed the algorithm in [16]. We can then conclude that EXORCISM has potential as a viable ML method that would especially complement existing ML techniques.
Our goal is the creation of a practical ``machine learning'' algorithm, which means at the minimum, 30 binary input variables but more likely, about 100 multiple-valued variables. As presented above, in machine learning, with the increase in the number of input variables there is only a small increase in the number of both positive and negative samples, but a dramatic increase in the number of don't cares. For instance, it is reasonable to expect that for a function of 100 variables there will not be more than 10,000 cares.
The program must be robust across various classes of data from the learning benchmarks. Combining SOP and ESOP minimizers, like Espresso and EXORCISM, into a single program will create a program that would be superior to both of them. We believe that this analysis pinpoints strengths and weaknesses of all analyzed approaches: AFD is clearly superior on small functions but it is not yet tractable on larger ones; Espresso has trouble with ``counting'' type of dependencies such as parity and arithmetic circuits but handles don't cares relatively well; EXORCISM is superior to Espresso and C4.5 on some functions, in spite of the uncorrected problem of very strongly unspecified functions. C4.5, the defacto standard machine learning tool, can handle more special cases of data, such as noise and missing input values.
The observation that functions in Machine Learning are very strongly unspecified and thus none of the known approaches work well, makes the requirements on the minimization programs in circuit design and machine learning very different, a point that has not yet been sufficiently observed and appreciated. This fact calls for the development of totally new approaches to synthesis, and is a very positive opportunity for people working in the area of ``Reed-Muller logic.'' Instead of adapting the algorithms created for circuit design, new algorithms should be created from scratch, and from the very beginning they should take into account the problem specifics. Moreover, since these algorithms run only in software, EXOR gates are as good as any other and there is no problem of its realization or speed.
Missing values, and especially noise, are still not adequately part of the circuit design world but are a reality in KDD and ML. It will be necessary to find solutions to these issues if we are to use logic synthesis tools in these fields.
We believe that machine learning will become a new and fruitful area for logic synthesis research, and an application territory for logic minimizers. There exist big challenges, but also great wins for successful programs. The first research results that appreciate this synergy and try to link the two worlds of the ``machine learning community'' and the ``design automation community'' already start to appear: new decision-diagram approaches were presented in 1994 by Ron Kohavi [10, 11], and Arlindo Oliveira [15]. It is our hope that the participants of this Workshop will also partake in this challenge, develop new theories and software, and will test them on the machine learning benchmarks. It is quite possible, that problems with an unusually high percent of don't cares will also occur in circuit design, when more sophisticated VHDL compilers start to appear.