# Article

Full entry | PDF   (2.5 MB)
Keywords:
knowledge extraction from data; artificial neural networks; fuzzy logic; Lukasiewicz logic; disjunctive normal form
Summary:
The extraction of logical rules from data has been, for nearly fifteen years, a key application of artificial neural networks in data mining. Although Boolean rules have been extracted in the majority of cases, also methods for the extraction of fuzzy logic rules have been studied increasingly often. In the paper, those methods are discussed within a five-dimensional classification scheme for neural-networks based rule extraction, and it is pointed out that all of them share the feature of being based on some specialized neural network, constructed directly for the rule extraction task. As an important representative, a method for the extraction of rules in a general fuzzy disjunctive normal form is described in detail and illustrated on real-world applications. Finally, the paper proposes an algorithm demonstrating a principal possibility to extract fuzzy logic rules from multilayer perceptrons with continuous activation functions, i. e., from the kind of neural networks most universally used in applications. However, complexity analysis of the individual steps of that algorithm reveals that it involves computations with doubly-exponential complexity, due to which it can not without simplifications serve as a practically applicable alternative to methods based on specialized neural networks.
References:
[1] Adamo J. M.: Data Mining for Association Rules and Sequential Patterns: Sequential and Parallel Algorithms. Springer–Verlag, Berlin 2001 Zbl 0998.68228
[2] Aguzzoli S., Mundici D.: Weierstrass approximations by Lukasiewicz formulas with one quantified variable. In: 31st IEEE Internat. Symposium on Multiple-Valued Logic, 2001
[3] Alexander J. A., Mozer M. C.: Template-based procedures for neural network interpretation. Neural Networks 12 (1999), 479–498 DOI 10.1016/S0893-6080(99)00009-X
[4] Amato P., Nola, A. Di, Gerla B.: Neural networks and rational Lukasiewicz logic. J. Multiple-Valued Logic and Soft Computing (accepted for publication)
[5] Amato P., Porto M.: An algorithm for the automatic generation of logical formula representing a control law. Neural Network World 10 (2000), 777–786
[6] Andrews R., Diederich, J., Tickle A. B.: Survey and critique of techniques for extracting rules from trained artificical neural networks. Knowledge-based Systems 8 (1995), 378–389 DOI 10.1016/0950-7051(96)81920-4
[7] Bern M., Chew L. P., Eppstein, D., Ruppert J.: Dihedral bounds for mesh generation in high dimensions. In: Proc. Sixth ACM-SIAM Symposium on Discrete Algorithms, ACM, San Francisco 1995, pp. 189–196 MR 1321850 | Zbl 0849.68116
[8] Berthold M., Hand D., editors: Intelligent Data Analysis. An Introduction. Springer–Verlag, Berlin 1999 DOI 10.1007/978-3-662-03969-4 | MR 1723394
[9] Chen J., Liu J.: Using mixture principal component analysis networks to extract fuzzy rules from data. Indust. Engrg. Chemistry Research 39 (2000), 2355–2367 DOI 10.1021/ie9905613
[10] Cignoli L. O., D’Ottaviano I. M. L., Mundici D.: Algebraic Foundations of Many-valued Reasoning. Kluwer Academic Publishers, Dordrecht 2000 MR 1786097 | Zbl 0937.06009
[11] Garcez A. S. d’Avila, Broda, K., Gabbay D. M.: Symbolic knowledge extraction from artificial neural networks: A sound approach. Artificial Intelligence 125 (2001), 155–207 DOI 10.1016/S0004-3702(00)00077-1 | MR 1805645
[12] Daňková M., Perfilieva I.: Logical approximation II. Soft Computing 7 (2003), 228–233 DOI 10.1007/s00500-002-0209-3 | Zbl 1029.03503
[13] Raedt L. De: Interactive Theory Revision: An Inductive Logic Programming Approach. Academic Press, London 1992
[14] Duch W., Adamczak, R., Grabczewski K.: Extraction of logical rules from neural networks. Neural Processing Lett. 7 (1998), 211–219 DOI 10.1023/A:1009670302979
[15] Duch W., Adamczak, R., Grabczewski K.: A new methodology of extraction, optimization and application of crisp and fuzzy logical rules. IEEE Trans. Neural Networks 11 (2000), 277–306
[16] Dzeroski S., Lavrac N.: Relational Data Mining. Springer–Verlag, Berlin 2001 Zbl 1003.68039
[17] Edelsbrunner H.: Algorithms in Combinatorial Geometry. Springer–Verlag, Heidelberg 1987 MR 0904271 | Zbl 0634.52001
[18] Esteva F., Godo, L., Montagna F.: The L$\Pi$ and L$\Pi \frac{1}{2}$ logics: Two complete fuzzy systems joining Lukasiewicz and product logic. Arch. Math. Logic 40 (2001), 39–67 DOI 10.1007/s001530050173 | MR 1816606
[19] Faber J., Novák M., Svoboda, P., Tatarinov V.: Electrical brain wave analysis during hypnagogium. Neural Network World 13 (2003), 41–54
[20] Finn G. D.: Learning fuzzy rules from data. Neural Computing Appl. 8 (1999), 9–24 DOI 10.1007/s005210050003
[21] Freitas A. A.: Data Mining and Knowledge Discovery with Evolutionary Algorithms. Springer–Verlag, Berlin 2002 Zbl 1013.68075
[22] Gehrke M., Walker C. L., Walker E. A.: Normal forms and truth tables for fuzzy logics. Fuzzy Sets and Systems 138 (2003), 25–51 MR 2012239 | Zbl 1027.03023
[23] Hájek P.: Metamathematics of Fuzzy Logic. Kluwer Academic Publishers, Dordrecht 1998 MR 1900263 | Zbl 1007.03022
[24] Hájek P., Havránek T.: Mechanizing Hypothesis Formation. Springer–Verlag, Berlin 1978 MR 0501342 | Zbl 0371.02002
[25] Healy M. J., Caudell T. P.: Acquiring rule sets as a product of learning in a logical neural architecture. IEEE Trans. Neural Networks 8 (1997), 461–474 DOI 10.1109/72.572088
[26] Holeňa M.: Extraction of logical rules from data by means of piecewise-linear neural networks. In: Proc. 5th Internat. Conference on Discovery Science, Springer–Verlag, Berlin 2002, pp. 192–205 Zbl 1024.68560
[27] Holeňa M., Baerns M.: Artificial neural networks in catalyst development. In: Experimental Design for Combinatorial and High Throughput Materials Development (J. N. Cawse, ed.), Wiley, Hoboken 2003, pp. 163–202
[28] Holeňa M., Baerns M.: Feedforward neural networks in catalysis. A tool for the approximation of the dependency of yield on catalyst composition, and for knowledge extraction. Catalysis Today 81 (2003), 485–494
[29] Horčík R., Cintula P.: Product Lukasiewicz logic. Arch. Math. Logic 43 (2004), 477–503 DOI 10.1007/s00153-004-0214-6 | MR 2060396 | Zbl 1059.03011
[30] Ishikawa M.: Rule extraction by successive regularization. Neural Networks 13 (2000), 1171–1183 DOI 10.1016/S0893-6080(00)00072-1
[31] Lu H., Setiono, R., Liu H.: Effective data mining using neural networks. IEEE Trans. Knowledge and Data Engrg. 8 (1996), 957–961 DOI 10.1109/69.553163
[32] Maire F.: Rule-extraction by backpropagation of polyhedra. Neural Networks 12 (1999), 717–725 DOI 10.1016/S0893-6080(99)00013-1
[33] McNaughton R.: A theorem about infinite-valued sentential logic. J. Symbolic Logic 16 (1951), 1–13 DOI 10.2307/2268660 | MR 0041799 | Zbl 0043.00901
[34] Mitra S., De R. K., Pal S. K.: Knowledge-based fuzzy MLP for classification and rule generation. IEEE Trans. Neural Networks 8 (1997), 1338–1350 DOI 10.1109/72.641457
[35] Mitra S., Hayashi Y.: Neuro-fuzzy rule generation: Survey in soft computing framework. IEEE Trans. Neural Networks 11 (2000), 748–768 DOI 10.1109/72.846746
[36] Muggleton S.: Inductive Logic Programming. Academic Press, London 1992 Zbl 1132.68007
[37] Mundici D.: A constructive proof of McNaughton’s theorem in infinite-valued logic. J. Symbolic Logic 59 (1994), 596–602 DOI 10.2307/2275410 | MR 1276635 | Zbl 0807.03012
[38] Narazaki H., Watanabe, T., Yamamoto M.: Reorganizing knowledge in neural networks: An exploratory mechanism for neural networks in data classification problems. IEEE Trans. Systems Man Cybernet. 26 (1996), 107–117 DOI 10.1109/3477.484442
[39] Nauck D., Nauck, U., Kruse R.: Generating classification rules with the neuro-fuzzy system NEFCLASS. In: Proc. Biennial Conference of the North American Fuzzy Information Processing Society NAFIPS’96, 1996, pp. 466–470
[40] Novák V., Perfilieva I.: Some consequences of herbrand and McNaughton theorems in fuzzy logic. In: Discovering World with Fuzzy Logic: Perspectives and Approaches to Formalization of Human-Consistent Logical Systems (V. Novák and I. Perfilieva, eds.), Springer–Verlag, Heidelberg 1999, pp. 271–295 MR 1858104
[41] Novák V., Perfilieva, I., Močkoř J.: Mathematical Principles of Fuzzy Logic. Kluwer Academic Publishers, Dordrecht 1999 MR 1733839 | Zbl 0940.03028
[42] Perfilieva I.: Neural nets and normal forms from fuzzy logic point of view. Technical Report, Institute for Research and Applications of Fuzzy Modelling, 2001
[43] Perfilieva I.: Normal forms for fuzzy logic functions and their approximation ability. Fuzzy Sets and Systems 124 (2001), 371–384 MR 1860857 | Zbl 0994.03019
[44] Perfilieva I.: Logical approximaion. Soft Computing 7 (2003), 73–78 DOI 10.1007/s00500-002-0173-y
[45] Perfilieva I.: Normal forms in BL-algerbra and their contribution fo universal approximation of functions. Fuzzy Sets and Systems 143 (2004), 111–127 DOI 10.1016/j.fss.2003.06.009 | MR 2060276
[46] Perfilieva I.: Normal forms in BL and L$\Pi$ algebras of functions. Soft Computing 8 (2004), 291–298 DOI 10.1007/s00500-003-0274-2 | Zbl 1077.03047
[47] Perfilieva I., Kreinovich V.: A new universal approximation result for fuzzy systems, which reflects CNF-DNF duality. Internat. J. Intelligent Systems 17 (2002), 1121–1130 DOI 10.1002/int.10063 | Zbl 1028.68169
[48] Polkowski L.: Rough Sets. Mathematical Foundations. Physica–Verlag, Heidelberg 2002 MR 1967129 | Zbl 1166.68307
[49] Quinlan J.: C4. 5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Francisco 1992 Zbl 0900.68112
[50] Setiono R.: Extracting rules from neural networks by pruning and hidden unit splitting. Neural Computation 9 (1997), 05–225 DOI 10.1162/neco.1997.9.1.205 | Zbl 0872.68155
[51] Tickle A. B., Andrews R., Golea, M., Diederich J.: The truth will come to light: Directions and challenges in extracting rules from trained artificial neural networks. IEEE Trans. Neural Networks 9 (1998), 1057–1068 DOI 10.1109/72.728352
[52] Towell G. G., Shavlik J. W.: Extracting refined rules from knowledge-based neural networks. Mach. Learning 13 (1993), 71–101 DOI 10.1007/BF00993103
[53] Triantaphyllou E., (eds.) G. Felici: Data Mining and Knowledge Discovery Approaches Based on Rule Induction Techniques. Kluwer Academic Publishers, Dordrecht 2003 Zbl 1117.68028
[54] Tsukimoto H.: Extracting rules from trained neural networks. IEEE Trans. Neural Networks 11 (2000), 333–389 DOI 10.1109/72.839008
[55] Wong M. L., Leung K. S.: Data Mining Using Grammar Based Genetic Programming and Applications. Kluwer Academic Publishers, Dordrecht 2000 Zbl 0944.68172
[56] Zhang C., Zhang, S., Heymer B. E.: Association Rule Mining: Models and Algoritms. Springer–Verlag, Berlin 2002

Partner of