автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Логико-математические основания ДСМ-метода автоматического порождения гипотез

Введение.

Глава I. Неформальное введение в ДСМ-метод.

1. Объекты, свойства, характеристики.

2. Правила первого рода (правила поиска причин).

3. Правила второго рода (правила доопределения исходных данных).

4. Итерация применения правил.

5. Итерация применения правил (номер шага как мера правдоподобия гипотез).

Глава II. Логики с J-операторами, связанные с формализацией правдоподобных рассуждений.

1. Многозначные логики и J-операторы.

2. J-определимые и J-компактные логики.

3. Исчисление для J-определимых и J-компактных логик.

Глава III. Алгебры, соответствующие J-определимым Jкомпактным логикам.

1. L-степени булевых алгебр.

2. L-алгебры.

Глава IV. Каузальные модели предметных областей.

1. Каузоидные структуры.

2. Каузальные структуры.

3. Описание закономерностей, связанных с поиском возможных причин.

4. Обобщенные каузоидные и каузальные структуры.

ДСМ-метод (78М-метод) автоматического порождения гипотез был предложен В.К.Финном в конце 1970-х — начале 1980-х годов [41 — 43]. Название «ДСМ-метод» образовано от инициалов Джона Стюарта Милля. Правила индуктивных рассуждений Д.С.Милля [32] послужили отправной точкой для разработки ДСМ-метода. ДСМ-метод сочетает три разновидности правдоподобных рассуждений:

• индуктивные (в стиле Д.С.Милля [32]),

• рассуждения по аналогии, использующие результаты проделанных ранее индуктивных рассуждений,

• абдуктивные рассуждения в стиле Ч.Пирса [73], дающие критерий достаточного основания всей процедуре ДСМ-метода.

Индуктивные рассуждения определяют некоторый способ обучения на примерах и позволяют сформировать гипотезы о возможных причинах рассматриваемых свойств объектов предметной области. С помощью рассуждений по аналогии формируются гипотезы о наличии или отсутствии интересующего нас набора свойств у тех объектов предметной области, для которых информация (о наличии у них этих свойств) неполна или противоречива. Процедуры ДСМ-метода обрабатывают некоторое множество исходных данных (фактов или примеров). В результате исполнения процедур, соответствующих индуктивным рассуждениям и рассуждениям по аналогии, формируется некоторое множество гипотез. Затем наступает этап абдукции. Абдукция основана на применении следующего правила: если каждый факт (пример) может быть объяснен с помощью имеющихся гипотез, то ги-потзы принимаются, т.е. предполагается, что они сформированы на достаточном основании. В том случае, когда посылка правила абдукции ложна, делается вывод о необходимости расширения исходного набора фактов с помощью внешних источников.

Заметим, что компьютерные реализации ДСМ-метода успешно применяются в различных предметных областях, например, в химии и социологии ([29], [33], [35 — 37], [39]).

В настоящее время в исследованиях по ДСМ-методу наступил такой момент, когда большой объем накопленного фактического материала требует обобщения и систематизации. Изучение логико-математических оснований ДСМ-метода позволяет существенно продвинуться в решении данных задач. Этим и обусловлена актуальность темы диссертации.

В том случае, когда система правдоподобных рассуждений погружается в некоторую формальную теорию, говорят о дедуктивной имитации этой системы [5]. Для дедуктивной имитации может быть использован нестандартный логический аппарат: бесконечнозначные логики [55], языки с кванторами по кортежам [40], обобщенные кванторы [17]. Цель данного диссертационного исследования — изучение логико-математического аппарата, применяемого для дедуктивной имитации ДСМ-метода.

Предмет исследования — это логические исчисления, формальные теории, связанные с дедуктивной имитацией ДСМ-метода, и их модели.

Что касается методов исследования, то в работе использовалась различная логико-математическая техника, как стандарная (построение моделей из констант в стиле Генкина) так и оригинальная, например, аппарат ¿-степеней, введенный автором работы.

Основные результаты работы:

1. Предложен общий эффективный способ аксиоматизации широкого класса многозначных логик с .[-операторами. Логики из этого класса названы .[-определимыми и .[-компактными. (Одна из .[-определимых .[-компактных логик используется как базис для дедуктивной имитации ДСМ-метода).

2. Описан общий эффективный способ аксиоматизации классов алгебр, соответствующих .[-определимым .[-компактным логикам. Доказана теорема о полноте соответствующих исчислений относительно этих классов алгебр. Доказаны два варианта теоремы о представлении алгебр из данных классов.

3. Определены два класса многосортных алгебраических систем, пригодных для формализации каузальных свойств предметных областей (т.е. таких свойств, которые имеют отношение к причинно-следственным зависимостям). Первый из этих классов соответствует простому, а второй — обобщенному ДСМ-методу автоматического порождения гипотез. Приведены примеры алгебраических систем из упомянутых классов, построенные с помощью фильтров булевых алгебр.

4. Определено исчисление предикатов с обобщенными кванторами, которое может служить логическим базисом теории, описывающей характер причинно-следственных связей в предметных областях. Доказана теорема о полноте этого исчисления относительно естественной семантики.

Научная новизна работы обусловлена следующими моментами:

• впервые в виде аксиом для некоторых классов многосортных структур описана система требований к характеру причинно-следственных связей в предметной области в целом',

• впервые исследованы классы алгебр, соответствующих многозначным, в том числе бесконечнозначным, логикам из пшрокого класса логик с J-операторами, причем в этом исследовании применена оригинальная техника (¿-степени);

• работа основана на новых научных результатах, большинство из которых получено в течении последних пяти лет.

Теоретическая значимость работы обусловлена достаточно общим характером полученных результатов. Например, предлагаемые в работе системы аксиом для описания причинно-следственных связей позволяют в рамках одного класса структур рассматривать модели предметных областей, имеющих как статистистический, так и детерминистский характер причинно-следственных зависимостей.

Кроме того, следует отметить, что результаты работы позволяют поставить ряд интересных проблем, что открывает новое поле деятельности для исследований в этой области.

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

Все результаты работы либо получены лично автором (результаты из всех глав, кроме второй), либо при его непосредственном участии (вторая глава).

Апробация работы. Результаты работы докладывались: на 8 международном конгрессе по логике, методологии и философии науки LMPS'87 (1987), на 10 международном симпозиуме по интеллектуальному управлению (10th IEEE International Symposiumon Intelligent Control, 1995), на международной конференции по интеллектуальным системам и семиотике (1997 International Conference on Intelligent Systems and Semiotics: A Laerning Perspective, JSAS'97), на международной конференции «Смирновские чтения» (1997, 1999), на национальной конференции по искусственному интеллекту КИИ'92 (1992) и

КИИ'98 (1998), на международных конференциях НТИ-97 и НТИ-99 и опубликованы в ряде статей [3 — 17, 54 — 58]

Диссертация состоит из введения, пяти глав, заключения и списка литературы.

Заключение

По мнению автора, в настоящее время в исследованиях по ДСМ-методу наступил такой момент, когда обобщение и систематизация накопленного фактического материала и новые результаты позволяют поставить ряд интересных проблем, в том числе и проблем чисто математических, имеющих отношение к аппарату ДСМ-метода. Очень краткое заключение будет посвящено формулировке тех проблем, которые связаны с материалом данной диссертации.

На мой взгляд, интересно было бы исследовать категорные свойства классов алгебр, соответствующих .[-определимым и ^компактным логикам. Аналогичные проблемы можно поставить для классов каузоидных (обобщенных каузоидных) и каузальных (обобщенных каузальных) структур, а также для гиперструктур.

В связи с каузальными (обобщенными каузальными) структурами встает также проблема поиска их стандартного представления и доказательства соответствующей теоремы о представлении. Также необходимо найти новые примеры этих структур, в том числе имеющие отношение к конкретным предметным областям. Важной проблемой является также построение примеров (обобщенных) каузальных структур, удовлетворяющих аксиоме аргументированной индукции со статистическим кванторами. Автор предполагает, что для статистических кванторов могут возникнуть проблемы с совместностью аксиомы аргументированной индукции и аксиомы каузальной полноты. Возможно, придется отказаться от аксиомы каузальной полноты или ослабить ее.

Одна из проблем, связанных с исчислением ТвО из последней главы — это определение для гиперструктур и ТСО аналогов обыч

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

Другой круг проблем, связанных с гиперструктурами и ТвО — это проблемы абстрактного описания понятия мощности, т.е. описания понятия мощности без использования аппарата аксиоматической теории множеств, более скромными, преимущественно алгебраическими средствами.

Интересная, но, по-видимому, несложная задача — это обобщение ТОО до формализма, в котором шаблоны (а значит и соответствующие им кванторы), задаются при помощи произвольных функций, определенных на степени предметного универсума.

Завершим обзор проблем формулировкой следующей задачи: построить формальную теорию (обобщенных) каузальных структур на базе ТвО или другого формализма, допускающего обобщенные кванторы.

1. Аншаков О.М., Рынков C.B. О многозначных логических исчислениях // Докл. АН СССР. 1982. Т. 264. №2. С. 267-270.

2. Аншаков О.М., Рынков C.B. Об аксиоматизации конечнознач-ных логических исчислений//Матем. сб. 1984. №4. С. 71—89.

3. Аншаков О.М., Скворцов Д.П., Финн В.К. Логические средства экспертных систем типа ДСМ // Семиотика и информатика.— 1986,—Вып. 28,—С. 65-101.

4. Аншаков О.М., Скворцов Д.П., Финн В.К. О логической конструкции ДСМ-метода автоматического порождения гипотез // Докл. АН СССР, Том 320, № 6,— 1991,— С. 1331-1334.

5. Аншаков О.М., Скворцов Д.П., Финн В.К. О дедуктивной имитации некоторых вариантов ДСМ-метода автоматического порождения гипотез // Семиотика и информатика.— 1993.— Вып. 33,—С. 164-233.

6. Аншаков О.М., Скворцов Д.П., Финн В.К. Об аксиоматизируемости многозначных логик, связанных с формализацией правдоподобных рассуждений // Логические исследования. Вып. 1.— М.: Наука.— 1993,— С. 222-248.

7. Аншаков О.М. О решетке данных для ДСМ-метода автоматического порождения гипотез // НТИ. Сер. 2.— 1996.— № 5-6.— С. 33-36.

8. Аншаков О.М., Скворцов Д.П., Финн В.К. О некоторой формализации правдоподобных рассуждений средствами многознаяной логики с J-операторами // Международная конференция «Смирновские чтения». М.: 1997.— С. 9-10.

9. Аншаков О.М. Многозначные логики с J-операторами и соответствующие им классы алгебр // Международная конференция «Смирновские чтения». М.: 1997.— С. 7-9.

10. Атиаков О.М. J-логики и соответствующие им классы алгебр // 3 международная конференция "Информационные ресурсы, интеграция, технологии" (НТИ-97), Материалы конференции (вторая часть), М., 1997,-С. 6.

11. Аншаков О.М. ДСМ-метод на неформальном языке // КИИ-98. Шестая национальная конференция с международным участием. Сборник научных трудов в трех томах. Том II.— Пущино, 1998,—С. 575-579.

12. Аншаков О.М. J-логики и соответствующие им классы алгебр // Логические исследования. Вып. 5.— М.: Наука.— 1998.— С. 2552.

13. Аншаков О.М. Об одной интерпретации ДСМ-метода автоматического порождения гипотез // НТИ. Сер. 2.— 1999.— № 1-2.— С. 45-53.

14. Аншаков О.М. О статистических и детерминистских интерпретациях правил индуктивной логики Д.С.Милля // 2 Международная конференция «Смирновские чтения». М.: 1999.— С. 2730.

15. Аншаков ОМ. Каузальные модели предметных областей // НТИ. Сер. 2,— 2000,—№3.

16. Артамонов В.А., Салий В.Н., Скорняков Л.А., Шеврин Л.Н., Шульгейфер Е.Г. Общая алгебра, Т. 2.— М.: Наука, 1991.— 480 с.

17. Барвайс Дж. Введение в логику первого порядка // Справочная книга по математической логике: В 4-х частях / Под ред. Дж. Барвайса.— Ч. I. Теория моделей.— М.: Наука, 1982, С. 13-54.

18. Борщев В. Б. О постулатах ДСМ-метода // Новости искусственного интеллекта. Спец. вып. К 60-летию В.К.Финна.— М.: 1993.—С. 16-26.

19. Бочвар Д.А. Об одном трехзначном исчислении и его применении к анализу парадоксов классического расширенного функционального исчисления // Матем. Сборник. 1938. Т. 4. №2. С. 287—303.

20. Виноградов Д.В. Алгебраическая модель связанных свойств ДСМ-метода // НТИ-97. Информационные ресурсы. Интеграция. Технологии. Материалы конференции.— М.: ВИНИТИ, 1997, С. 59.

21. Виноградов Д.В. Логические программы для квазиаксиоматических теорий // НТИ. Сер. 2,— 1999.— № 1-2.— С. 61-64.

22. Гаек П, Гавранек Т. Автоматическое образование гипотез.— М.: Наука, 1984.—280 с.

23. Григолия Р.Ш., Финн В.К. Алгебры Бочвара и соответствующиеим пропозициональные исчисления // Исследования по неклассическим логикам и теории множеств. М., Наука, 1979. С. 345— 371.

24. Григорьев П.А. Об одном методе автоматического порождения гипотез, схожем с ДСМ-методом: применение статистических соображении // НТИ. Сер. 2,— 1996.— № 5-6,— С. 52-55.

25. Григорьев П.А. Sword-системы или ДСМ-системы для цепочек, использующие статистические соображения // НТИ. Сер. 2.— 1996.— № 5-6.— С. 45-51.

26. Григорьев П.А. О перспективах компьютерного прогнозирования рецидива аденомы гипофиза // НТИ. Сер. 2.— 1999.— № 1-2.—С. 83-88.

27. Гусакова С.М., Панкратова Е.С. Принципы построения интеллектуальной системы типа ДСМ для прогнозирования канцерогенности химических веществ // НТИ. Сер. 2.— 1996.— №3,—С. 16-20.

28. Кузнецов С.О. Введение в ДСМ-метод // Семиотика и информатика,— 1990,—Вып. 31,— С. 5-40.

29. Кузнецов С.О. ДСМ-метод как система автоматизированного обучения // Итоги науки и техники. Сер. «Информатика». Т. 15,—М: ВИНИТИ, 1991,— 17-53.

30. МилльД.С. Система логики силлогистической и индуктивной.— М.: Книжное дело, 1900.— 781 с.

31. Михеенкова М.А. ДСМ-метод правдоподобного рассуждения как средство анализа социального поведения // Известия РАН. Сер. «Теория и системы управления».— 1997.—№ 5.— С. 62-70.

32. Мостовский А. Конструктивные множества и их приложения.— М.: Мир, 1973.—256 с.

33. Панкратова Е.С., Ивашко В.Г., Авидон В.В., Блинова В.Г., Бодя-гин Д.А. Экспериментальная проверка новой версии ДСМ-метода автоматического порождения гипотез // НТИ. Сер. 2.— 1988,—№2.—С. 18-21.

34. Панкратова Е.С., Блинова В.Г., Финн В.К. О возможности применения ДСМ-метода в задаче распознавания химического канцерогенеза // Экпертные системы: состояние и перспективы / Под ред. Д.А.Поспелова.—М.: Наука, 1989,—С. 131-138.

35. ПойаД. Математика и правдоподобные рассуждения.— М.: Наука, 1975.

36. Путрин А.С., Панкратова Е.С. Программная реализация интелектуальной системы типа ДСМ для распознавания химической канцерогенности 7/ НТИ: Сер. 2.— 1997.— Лг2 3.— С. 8-11.

37. СкворцовД.П. О некоторых способах построения логических языков с кванторами по кортежам // Семиотика и информатика,— 1983,— Вып. 20.—С. 102-126.

38. Финн В.К. О возможностях формализации правдоподобных рассуждений средствами многозначных логик // Всесоюз. симпозиум по логике и методологии науки.— Киев: Наукова думка, 1976.— С. 82-83.

39. Финн В.К. Базы данных с неполной информацией и новый метод автоматического порождения гипотез // Диалоговые и фактографические системы информационного обеспечения.— М., 1981,—С. 153-156.

40. Финн В.К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф.Бэкона — Д.С.Милля // Семиотика и информатика.—1983.— Вып. 20.— С. 35-101.

41. Финн В.К Правдоподобные выводы и правдоподобные рассуждения // Итоги науки и техники. Сер. «Теория вероятностей. Ма-тем. статистика. Теоретическая кибернетика». Т. 28.— М: ВИНИТИ, 1988.—С. 3-84.

42. Финн В.К. Об обобщенном методе автоматического порождения гипотез // Семиотика и информатика.— 1989.— Вып. 29.— С. 93-123.

43. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ // Итоги науки и техники. Сер. «Информатика». Т. 15.—М.: ВИНИТИ, 1991.-54-101.

44. Финн В.К. Об интеллектуальных системах автоматизированной поддержки научных исследований // НТИ. Сер. 2.— 1996.— № 5-6.—С. 1-2.

45. Финн В.К. Об одном варианте логики аргументации // НТИ. Сер. 2,— 1996,—№ 5-6,—С. 3-19.

46. Яблонский С.В. Функциональные построения в k-значной логике // Труды МИАН СССР им. В.А.Стеклова. М., 1958. Т.51.

47. Alechina N., Lambalgen van М. Correspondence and completeness for generalized quantifiers // Bulletin of the Interest Group in Pure and Applied Logic, 3, 1995, P. 167-190.

48. Alechina N. Modal quantifiers / ILLC Dissertation series 1995-20.— Amsterdam, 126 p.

49. Anshakov O.M., Finn V.K., Skvortsov D.P. On axiomatization of many-valued logics associated with formalization of plausible reasoning 11 Studia Logica. 1989. Vol. 48. N 4. P. 423—447.

50. Anshakov O., Rychkov S. On finite-valued propositional logical calculi // Notre Dame Journal of Formal Logic. 1994. Vol. 36. N 4. P. 606—629.

51. O.M.Anshakov, V.K.Finn, D.P.Skvortsov. Plausible reasoning and its logics 11 Proceedings of the 1997 International Conference on Intelligent Systems and Semiotics: A Laerning Perspective, JSAS'97/ 1997,—P. 87-99

52. Astesiano E., Cerioli M. Free objects and equational deduction for partial conditional specifications // Theoretical Computer Science,

53. Vol 152, N 1, 11, 1995,—P. 91-138

54. Model-theoretic logics / Ed. Barwise J., Feferman S.— N.Y.: Springer Verlag, 1985.

55. Benthem van J., Alechina N. Modal quantification over structured domains // Advances in Intensional logic / Ed. Rijke de M., Dordrecht, Kluwer, 1993.

56. Burakowska E. Subalgebras of many sorted algebra. Lattice of subal-gebras // Journal of Formalized Mathematics, 6, 1994.— http://mizar.org/JFM/Vol6/msualg2.html

57. Ebbinghaus H.-D. Über eine Pradikatenlogik mit partiel definierten Pradikaten und Funktionen // Arch. Math. Logik Grundlagenforsch. 1969. Bd. 12. S. 39—53.

58. Finn V.K., Anshakov O.M., Grigolia R.Sh., Zabezhailo M.I. Many-valued logics as fragments of formalized semantics // Acta Philoso-phicaFennica. 1982. Vol. 35. P. 239—272.

59. Finn V.K., Grigolia R. Nonsense logics and their algebraic properties //Theoria. 1993. Vol. 59. P. 207—273.

60. Hallden S. The logic of nonsense. Uppsala: 1949.

61. Keisler H.J. Probability quantifiers // Model-Theoretic Logics / Ed. Barwise J., Feferman S.— N.Y.: Springer-Verlag, 1985.

62. Korolkiewicz M. Homomorphisms of many sorted algebras // Journal of Formalized Mathematics, 6, 1994.—http ://mizar.org/JFM/V ol6/msualg3 .html

63. Korolkiewicz M. Many sorted quotient algebra // Journal of Formalized Mathematics, 6, 1994.— http://mizar.org/JFM/Vol6/msualg4.html

64. Lukasiewicz J., Tarski A. Investigations into the sentential calculus // Tarski A. Logic, Semantics, Metamathematics / Chapter IV. Oxford:1. Clarendon Press. 1956.

65. Madras B. Products of many sorted algebras // Journal of Formalised Mathematics, 6, 1994,— http://mizar.org/JFM/Vol6/pralg 2.html

66. Mostowski A. On a generalization of quantifiers // Fundamenta mathematical 44, 1957,—P. 12-36.

67. PeirceC.S. Philosophical writings / Ed. J.Buchler.— N.Y.: Dover Publ. Co., 1955.

68. Post E. Introduction to a general theory of elementary propositions I I American Journal of Mathematics. 1921. Vol. 43. P. 63—185.

69. RosserJ.B., Turquette A.R. Many-valued logics. Amsterdam: North-Holland. 1951.

70. Segerberg K. A contribution to nonsense logic // Theoria. 1965. Vol. 31, P. 199—217.

71. Trybulec A. Many-sorted sets // Journal of Formalized Mathematics, 5, 1993,— http://mizar.org/JFM/Vol5/pboole.html

72. Trybulec A. Many sorted algebras 11 Journal of Formalized Mathematics, 6, 1994.— http://mizar.org/JFM/Vol6/msualgl.html1. Указатель обозначений1. Глава I

73. О, D, Р, С, V 13 Т 30 Sim 16 Sst 20 type 30 PIR, 21 PIR2 22 CSR 21 DDR 22 F(o,p) 16 F'(o,p) 22 H(c, p) 21 H'(c,p) 32 m 35 +1,-1,0 16 x 161. Глава II1.361. VL 361. DL 36oL 36s) 30 {s, nj 311,/|),(-1,/|),(0,/|) 31,32

74. F+PIF~¡PIF°\P. 18,19 ]Vr(F,c,/?) 20 M ~(F,c,p) 20 M°(F,c,p) 201. Tl+(H,o,p) 221.(H,o,p) 221. П°(Н,о,р) 22 -<,< 15n 161. Fz 361. JOL 391. ChL 391. JFL 401. Глава IV92