Tsutomu Sasao
Springer Nature,
July 2023.
Amazon.com
Contents 1 Introduction 1 1.1 Aim of this Book . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Organization of the Book . . . . . . . . . . . . . . . . . . . . 1 2 Definitions and Basic Properties 5 2.1 Two-Class Function . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Classification Function . . . . . . . . . . . . . . . . . . . . . 8 2.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Minimization of Variables: Exact Method 13 3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Exact Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4 Minimization of Variables: Heuristic Method 19 4.1 Impurity Measure . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Heuristic Algorithm . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5 Two-Class Functions 29 5.1 Statistical Analysis . . . . . . . . . . . . . . . . . . . . 29 5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 34 5.2.1 Random 6-variable functions with k0 = k1 = 4 . . . . 34 5.2.2 Number functions that require no variables, for n = 16,20,24,28 and k0 = k1 = 64. . . . . . . . . . . . . 34 5.2.3 Random 24-variable Functions with k0 = k1 . . . . . 36 5.2.4 Random 24-variable Functions with 5.2.5 Random 60-Variable Function . . . . . . . . . . . . . 36 5.2.6 Non-Random Functions . . . . . . . . . . . . . . . . 37 5.2.7 MNIST Handwritten Character Recognition Circuit . . 38 5.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6 Linear Decomposition 43 6.1 Algorithm for Linear Decomposition . . . . . . . . . . . . . . 43 6.2 Number of Variables to Represent Non-Linear Function . . . . 48 6.3 Examples of Reductions . . . . . . . . . . . . . . . . . . . . 49 6.4 Experimental Results for Larger Problems . . . . . . . . . . . 52 6.4.1 Benchmark Functions and Computer Environment . . 52 6.4.2 Reduction of Primitive Variables . . . . . . . . . . . . 52 6.4.3 Reduction of Compound Variables . . . . . . . . . . . 53 6.4.4 MNIST Character Recognition Circuit (45-unit real- ization) . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.4.5 Fashion MNIST (45-unit realization) . . . . . . . . . 54 6.4.6 Single-Unit Realization of MNIST . . . . . . . . . . . 55 6.4.7 MNIST Two-Class Problem . . . . . . . . . . . . . . 56 6.4.8 Spam E-Mail Filter (two-class function) . . . . . . . . 57 6.5 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7 Data Mining and Machine Learning 61 7.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.2 Comparison with a Tree-based Classifier . . . . . . . . . . . . 65 7.3 Performance Measures . . . . . . . . . . . . . . . . . . . . 68 7.4 Evaluation Methods . . . . . . . . . . . . . . . . . . . . . . . 69 7.5 Accuracy for MNIST . . . . . . . . . . . . . . . . . . . . . . 69 7.6 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 8 Functions with Multi-Valued Inputs 75 8.1 SOP with Multi-valued Inputs . . . . . . . . . . . . . . . . 75 8.2 Minimization of Multi-valued Variables . . . . . . . . . . . . 78 8.3 SOP Minimization and Generalization Ability . . . . . . . . . 79 8.4 Experiments with UCI Data Sets . . . . . . . . . . . . . . . . 82 8.4.1 Breast Cancer . . . . . . . . . . . . . . . . . . . . . . 82 8.4.2 Chess3196 . . . . . . . . . . . . . . . . . . . . . . . 82 8.4.3 Connect-4 . . . . . . . . . . . . . . . . . . . . . . . . 82 8.4.4 Dermatology . . . . . . . . . . . . . . . . . . . . . . 83 8.4.5 Letter Recognition . . . . . . . . . . . . . . . . . . . 83 8.4.6 Monks . . . . . . . . . . . . . . . . . . . . . . . . . 83 8.4.7 Mushroom . . . . . . . . . . . . . . . . . . . . . . . 83 8.4.8 Promoter . . . . . . . . . . . . . . . . . . . . . . . . 84 8.4.9 Splice . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.4.10 Teaching Assistant Evaluation . . . . . . . . . . . . . 84 8.4.11 Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . . 84 8.4.12 Vote . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 8.4.13 Zoo . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 8.5 Experiments with Imbalanced Data Set . . . . . . . . . . . . . 86 8.5.1 Hepatitis . . . . . . . . . . . . . . . . . . . . . . . . 86 8.5.2 Thoracic . . . . . . . . . . . . . . . . . . . . . . . . 87 8.6 Observations . . . . . . . . . . . . . . . . . . . . . . . . 88 8.6.1 Analysis of Table 8.4.1 . . . . . . . . . . . . . . . . . 88 8.6.2 Analysis of Table 8.4.2 . . . . . . . . . . . . . . . . . 88 8.7 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 8.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 9 Easily Reconstructable Functions 91 9.1 Reconstruction of Functions by SOP minimization . . . . . . 91 9.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 9.2.1 SOP Minimizer for Machine Learning . . . . . . . . . 95 9.2.2 Achilles Heel Functions . . . . . . . . . . . . . . . . 96 9.2.3 Other Monotone Increasing Functions . . . . . . . . . 96 9.2.4 Functions Generated by Random SOPs . . . . . . . . 98 9.3 Evaluation of Methods . . . . . . . . . . . . . . . . . . . 98 9.4 Comparison with Other Classifiers 100 9.4.1 Performance of the Proposed Method 100 9.4.2 Performance of Other Methods 100 9.5 Extension to Multi-Valued Input Functions 102 9.6 Remarks 103 9.7 Exercises 104 10 Functions with Continuous Variables 107 10.1 Generation of Rules from Examples 107 10.2 Algorithms and Examples 109 10.2.1 Discretization 109 10.2.2 Domain Reduction 111 10.2.3 Multi-Valued Input SOP Minimization 111 10.3 Experimental Results 114 10.4 Remarks 118 10.5 Exercises 118 11 References 121 11.1 Reduction of Variables 121 11.2 Analysis 122 11.3 Architecture 122 11.4 Applications 122 11.5 Survey 122 11.6 Miscellaneous 123 12 Conclusions 127 12.1 Summary of the Book 127 12.2 Remaining Problems 128 Appendix: Solutions to the Exercises 129