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

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

doi:10.21638/11701/spbu10.2017.303

Авторы

Татьяна Матвеевна Косовская Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7–9
Дмитрий Андреевич Петров Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7–9

DOI:

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

Аннотация

В задачах искусственного ителлекта, в которых объект представлен как множество составляющих его элементов и характеризуется свойствами этих элементов и отношениями междуними, язык исчисления предикатов является адекватным для описания объектов и классов объектов. Так формализованные задачи оказываются NP-полными или NP-трудными. Примером такой NP-трудной задачи является задача анализа сложного объекта, представленного как множество его элементов и описываемого набором атомарных формул с предикатами, задающими свойства этих элементов и отношения между ними. Для решения данных задач рассматривается задача выделения наибольшей общей с точностью до имен переменных подформулы двух элементарных конъюнкций атомарных предикатных формул. Выделение таких подформул позволяет свести задачу распознавания объекта к серии аналогичных задач с меньшей длиной исходных данных за счeт построения многоуровневого описания классов, существенно уменьшающего показатель степени в экспоненциальной оценке числа шагов решения NP-трудной задачи проверки принадлежности объекта этомуклассу . Приводится алгоритм выделения наибольшей общей с точностью до имен переменных подформулы двух элементарных конъюнкций. Доказываются оценки числа шагов его работы. Анализируется время применения его реализации в зависимости от структуры исходных данных. Анализ числа шагов работы алгоритма показывает, что предложенный алгоритм может быть успешно применен для уменьшения вычислительной сложности многих задач искусственного интеллекта, формализуемых средствами исчисления предикатов. Приводятся результаты численных экспериментов, показывающих влияние структуры исходных данных на время работы алгоритма. Так, например, при увеличении количества аргументов у предикатов значительно снижается время работы за счeт уменьшения глубины рекурсии. Также существенное влияние оказывает количество различных предикатных символов, участвующих в записи формулы. При больших исходных данных особенно заметна эффективность предложенного алгоритма, отсекающего «ветви», заведомо не приводящие к успеху. Сильное влияние на время работы алгоритма оказывает распределение переменных в качестве аргументов предикатов. Результаты показывают значительное снижение числа шагов работы алгоритма при неравномерном распределении переменных. В процессе работы описанного алгоритма возникает задача проверки совпадения с точностью до имен переменных (изоморфизма) двух элементарных конъюнкций. Решение этой задачи имеет наибольшую вычислительную сложность среди прочих шагов алгоритма. Предложен полиномиальный алгоритм проверки изоморфизма предикатных формул, правильность работы которого превышает 99,5 %. Алгоритм не является абсолютно точным. Доказано, что если он даeт отрицательный ответ, то формулы не изоморфны. Если алгоритм дает положительный ответ, то результаты численных экспериментов в 99,5 % случаев показали изоморфность формул. Библиогр. 14 назв. Табл. 2.

Ключевые слова:

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

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

Литература

Нильсон Н. Искусственный интеллект. Методы поиска решений / пер. с англ. В. Л. Стефанюка; под ред. С. В. Фомина. М.: Мир, 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)