Метаматематические исследования правдоподобных рассуждений типа ДСМ тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Виноградов, Дмитрий Вячеславович

• Виноградов, Дмитрий Вячеславович
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Виноградов, Дмитрий Вячеславович

Введение.

Глава 1.

Логические проблемы формализации правдоподобных рассуждений

§ 1. Логика первого порядка.

§2. Кванторы по конечным множествам.

§3. Стратифицированные логические программы.

§4. Несимметричная стратегия правдоподобных рассуждений.

Глава 2.

Алгебраические структуры свойств

§ 1. Стратегии для связанных активностей.

§2. Общие структуры свойств.

§3. Пример: социологические модели.

§4. Напоминание: условия дистрибутивности.

Глава 3.

Рандомизированные алгоритмы правдоподобных рассуждений

§1. Графы для поиска сходств.

§2. Основной алгоритм.

§3. Анализ алгоритма.

Введение диссертации (часть автореферата) на тему «Метаматематические исследования правдоподобных рассуждений типа ДСМ»

Уже в начале 1970-х голов стало очевидно, что рассуждения эксперта не могут быть описаны исключительно в дедуктивных терминах. Дж. МакКарти [5], Р. Рейтер [7] и их ученики [6] развили подходы к «рассуждениям здравого смысла» на основе различных систем немонотонных логик. П. Гарденфорс [4] и др. исследовали математические основы пересмотра теорий. Однако, несмотря на известное изящество предложенных конструкций, все эти теории так и не привели к прикладным системам, осуществляющим автоматизированные рассуждения в конкретных предметных областях.

В конце 1970-х годов группа исследователей под руководством профессора В.К. Финна [18], [19] существенно продвинулась в формализации средствами многозначных логик, расширении и обобщении процедур индукции (названных в честь Д.С. Милля — создателя концепции индуктивных методов [14] — ДСМ-методом автоматического порождения гипотез). Правдоподобные рассуждения типа ДСМ соединили в себе индукцию на эмпирических данных, рассуждения по аналогии, конструктивную абдукцию и дедуктивные выводы. На основе предложенной теории были созданы прикладные интеллектуальные системы в помощь исследователям-фармакологам при компьютерном конструировании лекарств, ученым-социологам при исследовании индивидуальных поведенческих готовностей и другие.

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

Для описания причинно-следственных зависимостей (без учета структурных запретов) необходимо рассматривать элементы сорта «объект» (переменные X с индексами), сорта подобъею» (переменные Z и V с индексами) и сорта «(под)множество свойств» (переменные У, и и \5(7 с индексами). Основные отношения «объект X обладает множеством свойством У» и «подобъект V является причиной наличия множества свойств представляются бинарными предикатами X =>1 У, V =>2 W. Однако, для формального представления правдоподобных рассуждений необходимо было расширение классической многосортной логики предикатов первого порядка в двух направлениях: многозначность и кванторы по конечным множествам (или кортежам переменной длины).

Так как исходная база данных содержит неполную информацию о свойствах изучаемых объектов, то приходится вводить дополнительные истинностные значения. В итоге, получаем следующие внутренние (расщепляемые в случае итерации) истинностные значения: (+1) — фактическая истина, (-1) — фактическая ложь, (0) — фактическое противоречие, (т) — неопределенность. Кроме того, имеются стандартные внешние истинностные значения I (логическая истина — выделенное значение) и £ (логическая ложь).

Для каждого внутреннего истинностного значения вводятся соответствующие 1-операторы Россера-Тьюкетга: = 1:, если X = v, и = £, если А, Ф v. Формулы вида 1У(Ф), где Ф — произвольная формула, а v — внутреннее истинностное значение, назовем 1-формулами. .[-формулы вида 1У(Ф), где Ф — атомарная формула, назовем Д-атомарными. Формулы, построенные из 1-формул с помощью обычных логических связок логики первого порядка, назовем внешними. Внешние формулы, содержащие только 1-атомарные .[-формулы, назовем нормальными.

На внутренних истинностных значениях можно определить связки и кванторы. Нужно только позаботиться о том, чтобы для любой внешней формулы существовала эквивалентная ей нормальная формула. Такие многозначные логики называются .[-определимыми. Критерий 1-опр е делимо сти и теорема об аксиоматизируемости многозначных (бесконечнозначных с конечным числом типов истинностных значений) логик были установлены О. М. Аншаковым, Д. П. Скворцовым и Б. К. Финном [8], [9],

Но гораздо более радикальным расширением было введение кванторов по конечным множествам. Они использовались для записи условия глобальности сходства как необходимого признака причины множества свойств. Глобальное сходство примеров [11] определяется через сходство такого множества примеров, которое не может быть расширено без уменьшения сходства. Это условие апеллирует к конечному, но заранее не фиксированному числу примеров.

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

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

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

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

Результаты работы докладывались на национальных конференциях по искусственному интеллекту, международных конференциях «Intégration, Information Technologies and Telecommunications» 97 и 99, общемосковском семинаре по искусственному интеллекту под руководством проф. В.Н. Вагина, проф. О.П. Кузнецова и проф. В.К. Финна, научно-исследовательском семинаре сектора интеллектуальных систем ВИНИТИ.

Тяава 1

Логические проблемы формализации правдоподобных рассуждений

Список литературы диссертационного исследования кандидат физико-математических наук Виноградов, Дмитрий Вячеславович, 2000 год

1. Anshakov О.М., Finn V.K., Skvottsov D.P. On axiomatizarion of many-valued logics associated with fomialization of plausible reasoning / / Stadia Lógica. - 1989. - Vol. 48, № 4. - P. 423-447.

2. Börger E. Decision Problems in Predicate Logic / / Logic CoIloquiuin'82.Amsterdam: North - HoUand, 1984. - P. 263-301.

3. Chandra A., HarelD. Horn clause queries and generalizations / / Journalof Logic Programming, -1985. - Vol. 2, № 1 - P. 1-15.

4. Gardenfors P. Conditionals and Changes of Belief / / Acta PhilosophicaFennica. - 1978. - Vol, 30. - P. 381-404

5. McCarthy}. Application of Circumscription to FormalizingCommonsense ICnowledge / / Artificial InteHigeace J, - 1986. - Vol, 28. - P . 89-116.

6. McDermott D., Doyle J, Non-monotonic Logic I / / Artificial IntelligenceJ. - 1980. - Vol. 13. - P, 41-72.

7. Reiter R. A Logic for Default Reasoning / / Artificial Intelligence J.1980.-Vol 13.-P, 81-132,

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

9. Аншаков О.М., Скворцов ДП., Финн В.К, Аогические средстваДСМ-метода автоматического порождения гипотез / / Научнотехническая информация, — Сер. 2 — 1987. — № 9. — 9—17.

11. Кемени Дж., Снелл Дж, Конечньге цепи Маркова, М.: Наука, 1970.

12. Кузнецов С О . Быстрый алгоритм построения всех пересеченийобъектов из конечной полурешетки / / Научно-техническая информация, - Сер. 2 - 1993. - № 9. - С, 11-21.

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

14. Михеенкова М.А. Развитие ДСМ-метода автоматическогопорождения гипотез для его применения при анализе социологических данных типа «субъект поведение» / / Автореф. дисс. канд. техн. наук. М.: ВИНИТИ. - 1998 - 28 с,

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

16. Трахтенброт Б.А. О рекурсивной отделимости / / Доклады АНСССР. - 1953. - Т. 88 - 953-955.

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

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

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

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

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

22. ФиннВ.К. ДСМ-метод автоматического порождения гипотез сотношением порядка / / Семиотика и информатика. - 1990. — Вып. 31- 69-103.

23. Финн В.К, Михеенкова М.А. Некоторые проблемы обобщенногоДСМ-метода автоматического поро>едения гипотез / / Семиотика и информатика. - 1993. - Вып. 33 - 136-163.