Microsoft Word - L. Aslanyan_9.doc Mathematical Problems of Computer Science 34, 2010. 28 Pattern Recognition with Mathematical Logic and Discrete Analysis Levon Aslanyan Institute for Informatics and Automation Problems Information Society Technologies Center Joint Laboratory of Computational Biology Institute for Information Theories and Applications 1, P.Sevak, 0014 Yerevan, lasl@sci.am Pattern recognition undergoes an important development for many years. As a research area this is not uni-modular like classic mathematical sciences, there are a number of sub disciplines inside such as – feature selection, object and feature ranking, analogy measuring, supervised and unsupervised classification, etc. The same time pattern recognition is indeed an integrated theory studying object descriptions and their diverse classification models. This is a collection of mathematical, statistical, heuristic and inductive techniques of fundamental role in executing the intellectual tasks, typical for a human being, – but on computers. Many applied problems with multidimensional experimental data use the object description that is often non-classical, that is, - not exclusively in terms of only numerical or only categorical features, but simultaneously by both kinds of values. Sometimes, the missing or unreliable value is introduced so that finally we deal with mixed and incomplete descriptions of objects as elements of Cartesian product of feature values, without any algebraic, logical or topological properties assumed in applied area. How then, do we select in these cases the most informative features, classify a new object given a (training) sample or find the relationships between all objects based on a certain measure of similarity? Logic Combinatorial Pattern Recognition (LCPR) is a research area formed since 70’s that uses a mix of discrete descriptors with similarities, separation, frequencies, integration, corrections, and optimization, and solves the whole spectrum of pattern recognition tasks. This approach is originated by the work [Dmitriev et al, 1966] that transfers the engineering domain technique of tests for electrical schemes [Chegis, Yablonskii, 1958] to the feature selection and object classification area. The applied task of [Dmitriev et al, 1966] address prognosis of mineral resources. Testor theory [Dmitriev et al, 1966] is based on a restriction of feature sets - with preservation of the basic learning set property. A feature subset },,{ kiii xxxT  21  is called a testor (or test) of L , if prjection of L on T keeps the classes nonintersecting (learning set property). Irreducible is the testor where no one ji x may be eliminated with conservation of the learning set property. Further a feature ranking is made taking into consideration the frequency of belonging ji x to the testors (irreducible testors). Testor based supervised classification algorithms are constructed by use of frequency similarity measures. Which is the structural property used from the learning 29 set? This is the pair wise difference of learning set elements from different classes (learning set property). We may suppose that this is a consequence of the well accepted compactness hypothesis. On formal basis testor technology is well visible on binary tables. Now it is known that constructing all irreducible testors is an NP hard problem. Approximations are studied as well. There is a high similarity with association rule mining models, especially in learning the monotone set structures – be it with frequent itemsets in associative rule mining or irreducible tests and testors in this theory. KORA and Logic Separation. [Vaintsvaig, 1973] introduced one of the basic concept in LCPR – the KORA algorithm. KORA is constructing elementary conjunctions C that intersect with only one class iC of learning set L . It is easy to imagine the corresponding interval C of n - dimensional binary cube nE . C does not contain contradictory knowledge of learning the set L . Contrary, [Aslanyan, 1975] considers all irreducible conjunction forms that intersect with only one class iC of the learning set L . This is not the generating idea of this work but is the consequence of the Logic Separation (LS) Principle. The work, factually for the first time, is considering learning set elements in a non-disjoint manner. The potential function concept is used that an element spreads its similarity, reducing by the distance measure, which interrupts facing the different class object. An extension may consider not only pairs of learning set elements – one spreading the similarity measure and the second interrupting that - but also arbitrary subsets/fragments of learning set. Several comments: logically, it is evident that the best learning algorithm is also best suited to the learning set (at least the learning set is reconstructable by the information used by the algorithm). This also may use the recognition hypothesis when available. The same learning set fragments play a crucial role in determining the best suited recognition algorithm to the given learning data set. After the methodological discussion it is worth to mention further developments with the voting algorithm, algorithmic correction procedure and other approaches of advanced logic- combinatorial pattern recognition [Zhuravlev, 1998] . References [ChegisYablonskii, 1958] Chegis I. A. and Yablonskii S. V., Logical Methods for controlling electrical systems, Proceedings of Mathematical Institute after V. A. Steklov, 51: 270-360, Moscow (In Russian), 1958. [Dmitriev et al, 1966] Dmitriev A. N., Zhuravlev Yu. I. and Krendelev F.P. On mathematical principles of object and phenomena classification, Discrete Analysis, 7: 3-15, Novosibirsk (In Russian), 1966. [Bongard, 1967] Bongard M.M. The problem of cognition, Moscow, 1967. [Vaintsvaig, 1973] Vaintsvaig M.N. Pattern Recognition Learning Algorithm KORA, Pattern recognition learning algorithms, Moscow, Sovetskoe Radio, 1973, pp.110-116. [Yablonskii, 1958] Yablonskii S. V., Functional constructions in k-valued logic, Proceedings of Mathematical Institute after V. A. Steklov, 51: 5-142, Moscow (In Russian), 1958. [Zhuravlev, 1958] Zhuravlev Yu. I., On separating subsets of vertices of n-dimensional unit cube, Proceedings of Mathematical Institute after V. A. Steklov, 51: 143-157, 1958. [Baskakova, Zhuravlev, 1981] Baskakova L.V., Zhuravlev Yu.I. Model of recognition algorithms with representative and support sets, Journal of Comp. Math. and Math. Phys., 1981, Vol. 21, No.5, pp. 1264-1275. [Zhuravlev, 1978] Zhuravlev Yu.I. On an algebraic approach to the problems of pattern recognition and classification, Problemy Kybernetiki, Vol. 33, 1978, pp.5-68. 30 [Zhuravlev, Nikiforov, 1971] Zhuravlev Yu.I., Nikiforov V.V. Recognition algorithms based on calculation of estimates. Cybernetics, Vol. 3, 1971, pp.1-11. [Aslanyan, 1975] Aslanyan L. H. On a pattern recognition method based on the separation by the disjunctive normal forms. Kibernetika, 5, (1975), 103 -110. [Zhuravlev, 1977] Zhuravlev Yu.I. Correct algebras over the sets of incorrect (heuristical) algorithms: I, Cybernetics, No.4, 1977, pp.5-17., II, Cybernetics, No.6, 1977., III, Cybernetics, No.2, 1978. [Aslanyan, Zhuravlev, 2001] Aslanyan L., Zhuravlev Yu,.Logic Separation Principle, Computer Science & Information Technologies Conference, Yerevan, September 17-20, 2001, 151-156. [Zhuravlev, 1998] Zhuravlev Yu. I., Selected Scientific Works (in russian), Magistr, Moscow, 1998, 417 p. [Aslanyan, Castellanos, 2006] Aslanyan L. and Castellanos J., Logic based pattern recognition – ontology content (1), iTECH-06, 20-25 June 2006, Varna, Bulgaria, Proceedings, pp. 61-66. [Aslanyan, Ryazanov, 2008] Aslanyan L. and Ryazanov V., Logic Based Pattern Recognition - Ontology Content (2), information Theories and Applications, ISSN 1310-0513, 2008, Volume 15, Number 4, pp. 314-318. [Aslanyan, 1975] Aslanyan L. H. On a pattern recognition method based on the separation by the disjunctive normal forms. Kibernetika, 5: 103-110, 1975. [Aslanyan, 1979] Aslanyan L. H. The Discrete Isoperimetry Problem and Related Extremal Problems for Discrete Spaces, Problemy Kibernetiki, 36: 85-128, 1979. [Aslanyan, Sahakyan, 2009] L. Aslanyan, H. Sahakyan, Chain Split and Computations in Practical Rule Mining, Intenational Book Series, Information Science and Computing, Book 8, Classification, forecasting, Data Mining, pp. 132-135, 2009. [Aslanyan, Sahakyan, 2010] L. Aslanyan, H. Sahakyan, Composite block optimized classification data structures, Classification, forecasting, Data Mining conference, Varna, 22- 24 June, 2010.