Recently, there has been an increasing interest in applying methods developed in design automation to other fields (see DAC'94 and Euro-DAC'94 panel discussions). Amazingly, the techniques developed in the last 15 years by the design automation community have been so universal and powerful, that they are also increasingly used in areas outside circuit design. For instance, they are now used in automatic theorem proving, robotics, industrial operations scheduling, stock market prediction, genetics research, and many others. It is then quite probable, that the design automation methods will lead to breakthroughs in these other fields.
One of the sub-areas of design automation that can find numerous external applications is logic synthesis. Unfortunately, the potential of logic synthesis for external applications is still less appreciated (by both the CAD and Machine Learning communities, and the general research and industrial circles) than the potentials of placement, routing, scheduling, simulation, and database techniques of design automation.
Until very recently, the logic synthesis discipline formulated efficient methods and algorithms to minimize and optimize only the hardware of digital computers and other digital circuits. This goal was achieved very successfully, and the logic synthesis techniques developed in universities and industry in the last 15 years became one of the sources of the success of Design Automation in creation of such products as Intel's Pentium microprocessor. In the last few years, however, one can observe some increased trend to apply these methods also in image processing, machine learning, knowledge discovery, knowledge acquisition, data-base optimization, AI, image coding, automatic theorem proving and verification of software and hardware [4, 15, 22, 7, 8, 9].
This paper is related to the use of an ESOP minimizer in Machine Learning (ML) and Knowledge Discovery in Databases (KDD) applications. We will examine the performance of the EXORCISM circuit minimizer on small binary functions comparing the results with Espresso. References will be made to data on these same test functions with C4.5 and function decomposition. The comparison will serve to highlight the strengths and the shortcomings of all approaches. The goal of this paper is not to go too deeply in algorithms, but rather to demonstrate the applicability of logic synthesis, and specifically EXOR-based synthesis, to KDD and ML. All four algorithms share the common goal of a consistent, minimal complexity solution, albeit different measures of complexity. All four differ in their method to find it.
The paper is organized as follows. In section 2 we will present briefly the basic concepts developed by the Pattern Theory Group at Wright Lab (WL). Section 3 concentrates on DFC and its role. Section 4 will discuss specific requirements for logic minimizers in Machine Learning applications. Section 5 outlines the application of EXORCISM-MV-2 ESOP minimizer for machine learning. Section 6 presents numerical results on learning benchmarks. Section 7 briefly characterizes the machine learning benchmarks of WL. Section 8 presents the way to improve EXORCISM on very strongly unspecified functions. Finally, section 9 concludes the paper and outlines future areas of research.