Выделение наибольшей общей подформулы предикатных формул для решения ряда задач искусственного интеллекта

Татьяна Матвеевна Косовская; Дмитрий Андреевич Петров

doi:10.21638/11701/spbu10.2017.303

Authors

Татьяна Матвеевна Косовская St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation
Дмитрий Андреевич Петров St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation

DOI:

https://doi.org/10.21638/11701/spbu10.2017.303

Abstract

If an investigated object in an Artificial Intelligence problem is regarded as a set of its elements and is characterized by properties of these elements and relations between them, then a predicate calculus language is an adequate one for the description of an object and classes of objects. Such a way formalized problems are NP-complete or NP-hard. Example of such an NP-hard problem is the problem of the analysis of a complex object presented as a set of its elements and described by a set of atomic formulas with the predicates setting properties of these elements and relation between them. To solve such a problem, a problem of extraction of a maximal common up to the names of variables sub-formula of two elementary conjunctions of atomic predicate formulas is under consideration in the paper. Extraction of these subformulas allows us to reduce a recognition problem to a series of analogous problems with the less input data length by means of construction a level description of classes, which essentially decreases an exponent in the exponential upper bound for a number of solution algorithm steps for NP-hard problem of checking whether an object belongs to this class. An algorithm of extraction of a maximal common up to the names of variables sub-formula of two elementary conjunctions of atomic predicate formulas is presented in the paper. Bounds on number of the algorithm run number of steps are proved. The time of its implementation in dependence on the input data structure is analyzed. The analysis of the number of algorithm steps shows that the proposed algorithm may be successfully implemented in order to decrease computational complexity of many Artificial Intelligence problems which are formalized by means of predicate calculus. The results of numerical experiments show the influence of input data structure on the algorithm run time. For example, the increasing of amount of predicate arguments involves essential decreasing of the algorithm run time, which is a consequence of the recursion depth decreasing. The number of different predicate symbols occurred in the formula notation also essentially influences on the algorithm run time. At larger input data the effectiveness of the offered algorithm, cutting obviously unsuccessful “brunches”, is especially noticeable. The strong impact on the algorithm run time is exerted by distribution of variables as arguments of predicates. Results show its considerable decreasing at a nonuniform distribution of variables. During the described algorithm run a problem of checking the coincidence up to the names of variables (isomorphism) of two elementary conjunctions appears. This problem has the greatest computational complexity among the other problems arising on other steps of the algorithm. A polynomial algorithm of checking whether two elementary conjunctions of atomic predicate formulas coincide up to the names of variables (are isomorphic) is offered. The algorithm is not a precise one. The correctness of this algorithm implementation exceeds 99,5 %. It is proved that if the algorithm gives a negative answer then the formulas are not isomorphic. If the algorithm gives a positive answer then the results of numerical experiments show that 99,5 % pairs of formulas are isomorphic. Refs 14. Tables 2.

Keywords:

Artificial Intelligence, predicate calculus, algorithmic complexity, isomorphism of predicate formulas

Downloads

Download data is not yet available.

References

Литература

Нильсон Н. Искусственный интеллект. Методы поиска решений / пер. с англ. В. Л. Стефанюка; под ред. С. В. Фомина. М.: Мир, 1973. 270 с. (Nilson Nils J. Problem-solving methods in artificial intelligence.)

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / пер. с англ. Е. В. Левнера, М. А. Фрумкина; под ред. А. А. Фридмана. М.: Мир, 1982. 416 с. (Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness.)

Косовская Т. М. Некоторые задачи искусственного интеллекта, допускающие формализацию на языке исчисления предикатов, и оценки числа шагов их решения // Труды СПИИРАН. 2010. Вып. 14. С. 58–75.

Косовская Т. М. Распознавание объектов из классов, замкнутых относительно группы преобразований // Вестн. С.-Петерб. ун-та. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2009. Вып. 3. С. 45–55.

Журавлев Ю. И. Об алгоритмах распознавания с представительными наборами (о логических алгоритмах) // Журн. вычисл. математики и матем. физики. 2002. Т. 42, № 9. С. 1425–1435.

Косовская Т. М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестн. С.-Петерб. ун-та. Сер. 1. Математика. Механика. Астрономия. 2007. Вып. 4. С. 82–90.

Рассел С., Норвиг П. Искусственный интеллект: современный подход. 2-е изд. / пер. с англ. К. Птицына. М.: Издат. дом «Вильямс», 2006. 1408 с. (Russel S. J., Norvig P. Artificial Intelligence. A Modern Approach.)

Косовская Т. М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов // Вестн. С.-Петерб. ун-та. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2008. Вып. 1. С. 64–72.

Косовская Т. М. Подход к решению задачи построения многоуровневого описания классов на языке исчисления предикатов // Труды СПИИРАН. 2014. № 3 (34). С. 204–217.

Клини С. Математическая логика / пер. с англ. Ю. А. Гастева; под ред. Г. Е. Минца. М.: Мир, 1973. 480 с. (Kleene S. C. Mathematical logic.)

Косовская Т. М. Частичная выводимость предикатных формул как средство распознавания объектов с неполной информацией // Вестн. С.-Петерб. ун-та. Сер. 10. Прикладная математика. Информатика. Процессы управления. 2009. Вып. 1. С. 74–84.

Рыбалов А. Н. Об одном генерическом отношении рекурсивно перечислимых множеств // Алгебра и логика. 2016. Т. 55, № 5. С. 587–596.

Kosovskaya T. Distance between objects described by predicate formulas // Intern. Book Series. Information Science and Computing. Book 25. Mathematics of Distances and Applications / eds: M. Deza, M. Petitjean, K. Markov. Sofia, Bulgaria, ITHEA Publ., 2012. P. 153–159.

Косовская Т. М. Самообучающаяся сеть с ячейками, реализующими предикатные формулы // Труды СПИИРАН. 2015. № 6 (43). С. 94–113.

References

Nilson Nils J. Problem-solving methods in artificial intelligence. New York, McGRAW-HILL BOOK COMPANY Press, 1971, 280 p. (Russ. ed.: Nilson N. Iskusstvennyi intellekt. Metody poisra reshenii. Moscow, Mir Publ., 1973, 270 p.)

Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, Freeman Press, 1979, 340 p. (Russ. ed.: Garey M. R., Johnson D. S. Vychislitelnye mashiny i trudnoreshaemye zadachi. Moscow, Mir Publ., 1982, 416 p.)

Kosovskaya T. M. Nekotorye zadachi iskusstvennogo intellekta, dopuskaiushchie formalizatsiiu na iazyke ischisleniia predikatov, i otsenki chisla shagov ikh resheniia [Some artificial intelligence problems permitting formalization by means of predicate calculus language and upper bounds of their solution steps]. SPIIRAS Proceedings, 2010, no. 14, pp. 58–75. (In Russian)

Kossovskaya T. M. Raspoznavanie ob"ektov iz klassov, zamknutykh otnositel’no gruppy preobrazovanii [Partial deduction of predicate formula as an instrument for recognition of an object with incomplete description]. Vestnik of Saint-Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes, 2009, iss. 3, pp. 45–55. (In Russian)

Zhuravlev Yu. I. Ob algoritmah raspoznavaniya s predstavitelnymi naborami (o logichskih algoritmah) [Recognition algorithms with representative sets (logical algorithms)]. Zhurnal vychislitelnoi matamatiki i matematicheskoi fiziki [Computational Mathematics and Mathematical Physics], 2002, vol. 2, no. 9, pp. 1425–1435. (In Russian)

Kossovskaya T. M. Dokazatel’stva otsenok chisla shagov resheniia nekotorykh zadach raspoznavaniia obrazov, imeiushchikh logicheskie opisaniia [Proofs of the number of steps bounds for solving of some pattern recognition problems with logical description]. Vestnik of Saint Petersburg University. Series 1. Mathematics. Mechanics. Astronomy, 2007, no. 4, pp. 82–90. (In Russian)

Russel S. J., Norvig P. Artificial Intelligence. A Modern Approach. Pearson Education, Inc., 2003, 1412 p. (Russ. ed.: Russel S. J., Norvig P. Iskusstvennyi intellekt: sovremennyi podhod. Moscow, “Viliams” Publ., 2006, 1408 p.)

Kossovskaya T. M. Mnogourovnevye opisaniia klassov dlia umen’sheniia chisla shagov resheniia zadach raspoznavaniia obrazov, opisyvaemykh formulami ischisleniia predikatov [Level descriptions of classes for decreasing step number of pattern recognition problem solving described by predicate calculus formulas]. Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes, 2008, iss. 1, pp. 64–72. (In Russian)

Kosovskaya T. M. Podkhod k resheniiu zadachi postroeniia mnogourovnevogo opisaniia klassov na iazyke ischisleniia predikatov [An approach to the construction of a level description of classes by means of a predicate calculus language]. SPIIRAS Proceedings, 2014, no. 3(34), pp. 204–217. (In Russian)

Kleene S. C. Mathematical logic. New York, Wiley, Dover Publ., 1967. 398 p. (Russ. ed.: Kleene S. Matematicheskaia logika. Moscow, Mir Publ., 1973, 480 p.)

Kossovskaya T. M. Chastichnaia vyvodimost’ predikatnykh formul kak sredstvo raspoznavaniia ob"ektov s nepolnoi informatsiei [Partial deduction of predicate formula as an instrument for recognition of an object with incomplete description]. Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes, 2009, iss. 1, pp. 74–84. (In Russian)

Rybalov A. N. Ob odnom genericheskom otnoshenii rekursivno perechislimykh mnozhestv [A Generic relation on Recursively Enumerable Sets]. Algebra and Logic, 2016, vol. 55, no. 5, pp. 587–596. (In Russian)

Kosovskaya T. Distance between objects described by predicate formulas. International Book Series. Information Science and Computing. Book 25. Mathematics of Distances and Applications. Sofia, Bulgaria, ITHEA Publ., 2012, pp. 153–159.

Kosovskaya T. M. Samoobuchaiushchaiasia set’ s iacheikami, realizuiushchimi predikatnye formuly [Self-training network with the nells implementing predicate formulas]. SPIIRAS Proceedings, 2015, no. 6(43), pp. 94–113. (In Russian)