«Витяев Е.Е. ИЗВЛЕЧЕНИЕ ЗНАНИЙ ИЗ ДАННЫХ КОМПЬЮТЕРНОЕ ПОЗНАНИЕ МОДЕЛИ КОГНИТИВНЫХ ПРОЦЕССОВ Монография Новосибирск, 2006 1 УДК 681.3:004.8 ББК з-813 В 546 Витяев Е.Е. Извлечение знаний из данных. Компьютерное познание. ...»

ISBN 5-94356-439-Х

Витяев Е.Е.

ИЗВЛЕЧЕНИЕ ЗНАНИЙ ИЗ ДАННЫХ

КОМПЬЮТЕРНОЕ ПОЗНАНИЕ

МОДЕЛИ КОГНИТИВНЫХ ПРОЦЕССОВ

Монография

Новосибирск, 2006

1

УДК 681.3:004.8

ББК з-813

В 546

Витяев Е.Е. Извлечение знаний из данных. Компьютерное познание.

Модели когнитивных процессов: Моногр. / Новосиб. гос. ун-т. Новосибирск, 2006, 293 с.

ISBN 5-94356-439-Х В работе излагается подход к компьютерному познанию, разработанный за последние 35 лет в Институте математики им. С. Л. Соболева. За основу подхода взята теория измерений, разработанная под руководством известного ученого и философа Patrick Suppes (Stanford university), в которой излагается аксиоматический подход к исследованию предметных областей. Нами разработаны необходимые теоретические и компьютерные методы реализующие этот процесс познания. Излагается решение некоторых сложных проблем работы со знаниями. В частности, описываются методы достаточно полного извлечения знаний из данных.

Наш подход к компьютерному познанию является междисциплинарным и основан на различных областях знания: логике и методологии науки, искусственном интеллекте, анализе данных, когнитивных науках и в том числе на психологии и физиологии работы мозга.

Автор придерживался многослойности изложения: 1) идеи изложены отдельно от технических результатов, потому что сами идеи имеют самостоятельную ценность и могут формализовываться различным образом, уточняться и развиваться самостоятельно; 2) для технических результатов приводится объяснение их смысла (что формализуется) и связи с основными идеями, поэтому читать текст можно пропуская технические детали.

Монография предназначена всем интересующимся проблемами познания, мышления и работы мозга, ученым, аспирантам и студентам.

Работы, представленные в монографии, выполнены при финансовой поддержке гранта РФФИ 05-07-90185в, Интеграционного проекта СО РАН №1, и программы президента Российской Федерации поддержки научных школ 4413.2006. © Витяев Е. Е., © Новосибирский государственный университет,

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ

ПРЕДИСЛОВИЕ

ВВЕДЕНИЕ

§ 1. Методология познания, вытекающая из теории измерений............ § 2. Процесс познания, основанный на теории измерений

§ 3. Логический путь познания предметной области

§ 4. Проблемы извлечения знаний и теорий

§ 5. Реляционный подход к извлечению знаний – реализация логического пути познания

§ 6. Применения реляционного подхода к извлечению знаний из данных в финансовом прогнозировании, медицине и биоинформатике

ГЛАВА 1. ЛОГИЧЕСКИЙ АНАЛИЗ ДАННЫХ И ЗАКОНОВ................... § 7. Основные понятия и проблемы теории измерений

§ 8. Эмпирические аксиоматические теории и теория измерений....... § 9. Представление известных типов данных в эмпирических аксиоматических теориях

§ 10. Критический анализ методов анализа данных

§ 11. Представление законов в теории измерений

§ 12. Теория физических структур

§ 13. Соотношение между физической структурой ранга (2,2) и аддитивной соединительной структурой

§ 14. Алгебраическое и конструктивное представления физической структуры ранга (2,2)

§ 15. Конструктивные числовые представления величин

§ 16. Взаимосвязь конструктивного и числового представлений........... § 17. Примеры конструктивных представлений величин

§ 18. Конструктивное числовое представление процедур шкалирования для экстенсивных величин

ГЛАВА 2. ПРОЦЕСС ПОЗНАНИЯ, ОСНОВАННЫЙ НА ТЕОРИИ

ИЗМЕРЕНИЙ.

§ 19. Универсальная аксиоматизируемость экспериментальной зависимости

§ 20. Общая формулировка метода обнаружения экспериментальной зависимости.

§ 21. Что такое закон

§ 22. Понятие эксперимента. Определение закона на множестве экспериментов

§ 23. События и вероятности событий

§ 24. Определение вероятностного закона на Exp

§ 25. Обобщение понятия вероятностного закона и эксперимента на случай данных с шумами

§ 26. Тестирование систем аксиом в условиях шумов

§ 27. Сохраняющий двоичный шум

ГЛАВА 3. ЛОГИЧЕСКИЙ ПУТЬ ПОЗНАНИЯ. ПРОБЛЕМА

ПРЕДСКАЗАНИЯ.

§ 28. Знание и познание

§ 29. Индуктивно-статистический вывод

§ 30. Семантический вероятностный вывод.

§ 31. Требование максимальной специфичности

§ 32. Решение проблемы статистической двусмысленности.................. § 33. Проблема логического вывода

§ 34. Эрбрановы модели. Вероятностная модель данных.

§ 35. Логические программы

§ 36. Оценки вероятностей и условных вероятностей запросов........... § 37. Вероятностные оценки запросов

§ 38. Детерминированные закономерности.

§ 39. Вероятностные закономерности.

§ 40. Предсказание и индуктивный синтез логических программ....... § 41. Вероятностный семантический вывод

§ 42. Взаимосвязь вероятностного и логического выводов..................

ГЛАВА 4. РЕЛЯЦИОННЫЙ ПОДХОД К ИЗВЛЕЧЕНИЮ

ЗНАНИЙ ИЗ ДАННЫХ

§ 43. Логический анализ методов извлечения знаний

§ 44. Реляционный подход к извлечению знаний

§ 45. Программная система извлечения знаний «Discovery»................ § 46. Метод обнаружения вероятностных законов

ГЛАВА 5. ПРИЛОЖЕНИЯ РЕЛЯЦИОННОГО ПОДХОДА

В ФИНАНСАХ

§ 47. Применение реляционного подхода в финансовом прогнозировании

§ 48. Преобразование числовых данных в отношения

§ 49. Гипотезы и вероятностные законы

§ 50. Марковские цепи как «вероятностные законы» в финансах........ § 51. Процедура обучения

§ 52. Метод прогноза

§ 53. Эксперимент 1

§ 54. Качество предсказания для конкретной закономерности............ § 55. Эксперимент 2

§ 56. Сравнение качества системы Discovery с другими методами...... § 57. Сравнение со стратегией buy-and-hold

§ 58. Результаты сравнения с другими методами

§ 59. Выводы из финансовых приложений

ГЛАВА 6. ПРИЛОЖЕНИЯ РЕЛЯЦИОННОГО ПОДХОДА

В МЕДИЦИНЕ.

§ 60. Диагностика рака груди. Постановка задачи

§ 61. Метод извлечения диагностических правил из эксперта............. § 62. Свойство монотонности

§ 63. Обнаружение диагностических правил на данных

§ 64. Правила, извлеченные из эксперта

§ 65. Извлечение правил используя монотонные Булевы функции..... § 66. Сравнение экспертных и извлеченных из данных правил........... § 67. Обсуждение и заключение

ГЛАВА 7. ПРИЛОЖЕНИЯ РЕЛЯЦИОННОГО ПОДХОДА

В БИОИНФОРМАТИКЕ.

§ 68. Задача анализа регуляторных районов ДНК

§ 69. Gene Discovery как технология извлечения знаний из ДНК........ § 70. Комплексные сигналы как олигонуклеотидные паттерны........... § 71. Подготовка данных и предварительный отбор сигналов............. § 72. Анализ найденных комплексных сигналов

§ 73. Распознавание на основе комплексных сигналов

§ 74. Обсуждение

ГЛАВА 8. ЕСТЕСТВЕННЫЕ КЛАССИФИКАЦИИ

И ОНТОЛОГИИ КАК ЗАКОНЫ ПРИРОДЫ

§ 75. Что такое естественная классификация

§ 76. Онтологии и описание предметной области

§ 77. Формальное определение «естественной» классификации и систематики

§ 78. Пример построения систематики

§ 79. Применение в биоинформатике

ГЛАВА 9. ПРИНЦИПЫ РАБОТЫ МОЗГА И МОДЕЛИ

КОГНИТИВНЫХ ПРОЦЕССОВ

§ 80. Принципы и основания естественно-научных теорий.................. § 81. Понятия задачи, цели и результата

§ 82. Теория функциональных систем работы мозга.

§ 83. Целенаправленная деятельность в ТФС и парадокс цели............ § 84. Информационная теория эмоций П. В. Симонова.

§ 85. Потребности и парадокс цели. Синтез принципов целеполагания, вероятностного прогнозирования и предсказания

§ 86. Формальный анализ главного принципа работы мозга................ § 87. Критика гипотезы суммации возбуждений на единичном нейроне. Новая формальная модель нейрона.

§ 88. Формальная модель работы мозга, основанная на принципе предсказания.

§ 89. Объяснение теории функциональных систем.

§ 90. Модель теории функциональных систем П. К. Анохина............. БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРЕДИСЛОВИЕ

Данная монография посвящена результатам исследований, которые проводились в институте математики СО РАН последние 35 лет начиная с организации в 1971 г. направления исследований под названием «Машинные методы обнаружения закономерностей» (МОЗ). Тогда была создана логико-методологическая группа под руководством Н. Г. Загоруйко и К. Ф. Самохвалова, целью которой была разработка алгоритмов обнаружения законов природы. За рубежом такое направление исследований называется Scientific Discovery. В рамках направления МОЗ было проведено несколько конференций. В последнее время работа, в частности, проводилась в рамках международных грантов.

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

В частности, разработан оригинальный подход – Relational Data Mining – к интенсивно развиваемому за рубежом направлению исследований – извлечению знаний из данных (Knowledge Discovery in Data Bases and Data Mining (KDD&DM)). Разработанный нами подход лишен ограничений, присущих другим методам и способен решать задачу «полного» извлечения знаний из данных. Этот подход опубликован в монографии: Kovalerchuk B., Vityaev E. Data Mining in Finance: Advances in Relational and Hybrid methods. Kluwer Academic Publishers, 2000, а также в ряде глав других монографий.

Проблема компьютерного познания является по существу междисциплинарной и требует хорошего знания одновременно многих областей знания: философии, логики и методологии науки, искусственного интеллекта, анализа данных, анализа человеческого процесса познания – когнитивных наук (cognitive science, neuroscience) и др. Поэтому в книге анализируются различные области знаний и устанавливается взаимосвязь между различными направлениями исследований. Без таких взаимосвязей невозможно найти правильное решение сложных вопросов организации процесса познания.

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

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

Наибольший вклад внес бывший участник логико-методологической группы в ИМ СО РАН и ныне prof. computer science Central Washington University Б. Ковалерчук. Главы 5, 6 выполнены нами совместно в процессе работы в Lousisana State University над разработкой диагностической системой рака груди и в Central Washington University в процессе работы над системами финансового прогнозирования. При работе над диагностической системой нам неоценимую помощь оказал радиолог James Ruiz из Baton Rouge (Louisiana) Women Hospital.

Следует отметить, что в первые годы работы группы идеологом направления был К. Ф. Самохвалов, ныне д-р филос. наук, основные идеи которого, изложенные в монографии Загоруйко Н. Г., Самохвалов К. Ф., Свириденко Д. И. «Логика эмпирических исследований» (Новосибирск, 1978), были приняты нами на вооружение.

Организатором и вдохновителем являлся Н. Г. Загоруйко, в лаборатории которого в Институте математики была организована работа.

Важный вклад в разработанное направление внёс выдающийся физик Ю. И. Кулаков и американский физик William Q. Sumner. С ними мы занимались теорией физических структур (см. главу 1).

Логическое представление психофизических экспериментов, изложенное в главе 2, явилось результатом совместной работы с проф. А. Логвиненко (School of Psychology, Queen's University of Belfast, UK) по гранту английского королевского общества (Royal Sosiety, Belfast, 1993–1994).

В содержание книги внесли существенный вклад В. С. Костин, с которым была разрабатана «естественная» классификация; Ю. Л. Орлов, Т. И. Шипилов, И. В. Хомичева, К. А. Лапардин, совместно с которыми были получены результаты по биоинформатике; А. В. Демин (ему принадлежит эксперимент по моделированию анимата); Е. В. Михиенко (с ним разрабатывалась архитектура функциональных систем работы мозга.

Автор выражает благодарность Л. Ковтонюк за помощь в переводе некоторых статей и глав и К. Денисовой за дизайн обложки.

ВВЕДЕНИЕ

§ 1. Методология познания, вытекающая из теории измерений В настоящее время интенсивно развивается направление Knowledge Discovery in Databases and Data Mining (KDD&DM), основанное на методах Machine Learning, Artificial Intelligence и Data Analysis. Давно назрела потребность проанализировать эти методы с точки зрения их связи с процессом познания. В результате анализа мы естественным образом придем к компьютерному познанию, основанному на теории измерений.

1. Аппроксимационный подход к решению задач анализа данных.

В методах Machine Learning неизвестная зависимость аппроксимируется некоторым заданным априори классом функций, моделями, решающими правилами и т. д. В нейронных сетях это кусочно-линейные правила, в деревьях – логические решающие функции, в регрессионном анализе – линейная или нелинейная регрессия, в дискриминантном анализе – дискриминантная функция, в распознавании образов – решающее правило, в методах классификации – форма кластеров. Какова в некотором смысле «истинная» зависимость? Этот вопрос не ставится и не может быть поставлен.

Аппроксимируя неизвестную зависимость с требуемой степенью точности и надежности, методы Machine Learning решают, по существу, задачу предсказания. Найденная аппроксимация практически ничего не говорит об «истинной» зависимости.

Процесс аппроксимации начинается с переноса способов измерения из точных наук в другие области. Рассмотрим, например, такую физическую величину, как температура. Шкалы температуры в нефизических областях, например при измерении температуры тела больного в медицине, температуры почвы в сельском хозяйстве, температуры воздуха в духовке в кулинарии и т. д., должны быть разные, хотя измеряться они могут одним и тем же прибором – термометром. Далеко не всеми понимается тот факт, что шкала – это не только риски делений на приборе, это набор операций и отношений, которые имеет смысл производить с числовыми значениями величин с точки зрения рассматриваемой предметной области (точнее, операции и отношения, интерпретируемые в системе понятий соответствующей предметной области). Можно возразить, что термометр не может измерять ничего, кроме температуры. Он действительно во всех случаях измеряет физическую температуру. Но резонно спросить: а зачем, собственно, мы измеряем температуру? Ведь не затем, чтобы согласно законам физики узнать, сколько в больном содержится тепла и сколько он в состоянии растопить льда, если его положить на лед, и не затем, чтобы определить среднюю кинетическую энергию молекул почвы или курицы в духовке. Температура, как и любой другой прибор, нужна для получения выводов в системе понятий той предметной области, к которой он относится.

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

Следует понимать, что физическая величина температуры является косвенным измерением другой величины, интерпретируемой в системе понятий предметной области, которую мы именно и хотим измерить. Физическая температура больного, например, есть косвенное измерение медицинской величины – уровня обмена веществ, температура почвы измеряет состояние биохимических процессов в растениях и микроорганизмах, температура воздуха в духовке измеряет течение процесса свертывания белка и т. д. Какие отношения и операции над числовыми значениями температуры имеют смысл для всех этих величин – определяется уже этими интерпретациями. Поэтому числовые значения величин нельзя автоматически переносить из одной области знаний в другую. После такого переноса необходимо заново определять шкалу. Например, для температуры больного интерпретируемы выделенные значения 36.7°, 42° и отношение линейного порядка 0) и (A0 /A1&... &Ak) = 1;

b) условная вероятность (A0 /A1&... &Ak) правила строго больше условных вероятностей каждого из его подправил.

Доказательство. 1. Предположим, что правило C является законом на M. Докажем, что тогда правила определены. Если правило C является законом на M, то подправило (A2&... &Ak ¬A1) не всегда истинно на M.

Значит, есть эксперименты, являющиеся исключениями из этого правила, т. е. эксперименты на которых высказывание (A2&... &Ak &A1) истинно.

Тогда {Exp(I(M), s) | (Exp(I(M), s)) E(A2&... &Ak &A1)} и, значит, в силу свойства 2 (определение 13), (E(A2&... &Ak &A1)) 0 и (A2&... &Ak&A1) 0. Отсюда получаем, что (A2&... &Ak &A1) = (A1&A2&... &Ak) > 0 и, значит, условная вероятность правила C определена. Отсюда следует, что и условные вероятности всех подправил определены, так как из {Ai1,..., Aih} {A1,..., Ak}, следует, что (Ai1&... &Aih) (A1&... &Ak) > 0.

2. Докажем теперь, что (A0 /A1&... &Ak) = 1 тогда и только тогдп, когда правило C истинно на Exp. Докажем, что из (A0 /A1&... &Ak) = 1 следует истинность правила C на Exp. Предположим противное, что оно не истинно на Exp. Это означает, что существуют эксперименты, на которых высказывание A1&... &Ak&¬A0 истинно, и, значит, множество экспериментов {Exp(s) ¦ (Exp(s)) E(A1&... &Ak&¬A0)} не пусто. Отсюда, вследствие свойства 2 (определение 13), следует, что (A1&... &Ak &¬A0) 0. Но это противоречит условию (A0 /A1&... &Ak) = 1, так как (A0 /A1&... &Ak) / ((A0&A1&... &Ak) + (¬A0&A1&... & Ak)) и поскольку мы доказали, что (¬A0&A1&... &Ak) 0, то (A0 /A1&... &Ak) < 1. Обратное доказательство, что из истинности правила C на Exp следует, что (A0 /A1 &... &Ak) = 1, проводится теми же рассуждениями, проведенными в обратном порядке.

3. Из пп. 1, 2 следует, что условие 1 теоремы влечет условие 2а. Из п. 1.

следует определенность правил, а из п. 2 следует, что условная вероятность равна 1.

4. Докажем, что из условия 1 теоремы следует условие 2b. Любое подправило Ai1&... &Aih L правила C ложно на M, где L – литера вида ¬A, для правил вида 1 (теорема 4), либо вида A, для правил вида 2. Ложность имеет место тогда и только тогда, когда {Exp(s) ¦ (Exp(s)) E(Ai1&... &Aih&¬L)}, что в силу свойства 2 (определение 13), эквивалентно условиям (Ai1&... &Aih&¬L) > 0 и (Ai1&... &Aih&¬L) > 0. Из последнего неравенства следует (L /Ai1&... &Aih) = (Ai1&... &Aih&L) / (Ai1&... &Aih) = (Ai1&... &Aih&L) / ((Ai1&... &Aih&¬L) + (Ai1&... & Aih&L)) < 1.

Но поскольку в силу п. 2 условная вероятность правила C равна 1, то ложность любого подправила на M эквивалентна неравенствам (L /Ai1&... &Aih) < 1 = (A0 /A1&... &Ak).

5. Таким образом, мы доказали, что из условия 1 теоремы следуют условия 2a и 2b, что доказывает теорему в одну сторону.

6. Докажем, что из условий 2a и 2b следует условие 1 теоремы. Если для правила C условная вероятность определена, то в силу пункта (1) будут определены и условные вероятности всех его подправил. Так как условная вероятность правила C, в силу условия 2a равна 1, то в силу п. правило C будет истинным на Exp. Для доказательства того, что правило C будет законом необходимо доказать, что каждое подправило этого правила ложно. Это можно сделать проводя те же рассуждения, что и в п. 4, только в обратном порядке Данная теорема дает нам эквивалентное определение закона на Exp в терминах вероятностей.

Определение 15. Вероятностным законом на Exp в детерминированном случае (см. определение 13 вероятности) будем называть правило C = (A1&... &Ak A0) вида (1), удовлетворяющее условиям:

a) условная вероятность (A0 /A1&... &Ak) правила определена (т. е.

(A1&... &Ak) > 0) и (A0 /A1&... &Ak) = 1;

b) условная вероятность (A0 /A1&... &Ak) правила строго больше условных вероятностей каждого из его подправил.

Следствие 2. Вероятностный закон на Exp в детерминированном случае является законом эмпирической системы M.

Доказательство. Следует из теоремы 6 и 7.

§ 25. Обобщение понятия вероятностного закона и эксперимента на случай данных с шумами Определение эксперимента Exp(s), как некоторого «фрагмента», эмпирической системы не включает в себя всех видов случайностей, которые могут быть в эксперименте и не отражает реальность проведения экспериментов как она есть. Определение 13 вероятности исключает возможность искажения значений истинности предикатов (лемма 7). Чтобы обобщить понятие эксперимента на случай, когда возможны ошибки измерения, шумы или ошибки в ответах испытуемого, необходимо ввести все эти случайные искажения в понятие эксперимента.

Известно [108], что в языке первого порядка можно ввести несколько типов случайностей:

случайности, связанные со случайным выбором стимулов из генеральной совокупности (случайность на области [Там же]);

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

В случаях 1 и 2 вероятность может вводиться, вообще говоря, различным образом [Там же] как вероятность на «области» или как вероятность на множестве «возможных миров»… Определение 13 вероятности является примером вероятности на «области», так как, в силу свойства 2, определено для экспериментов являющимися «фрагментами» эмпирических систем и, следовательно, не содержащими случайностей вида 2. Чтобы учесть оба типа случайностей необходимо одновременно обобщить определение вероятности и эксперимента.

Определение 16. Вероятностью на E назовем отображение : E [0, 1], удовлетворяющее условию Для «детерминированных» экспериментов, должно быть выполнено также условие 2) () = 0 {Exp(s) | (Exp(s)) = } =.

Эксперимент определим как набор где F : E E – случайное отображение. В случае, когда F – тождественное отображение будем говорить, что мы имеем «детерминированный» эксперимент, для которого должно быть выполнено условие 2.

«Детерминированный» эксперимент совпадает со старым определением эксперимента. Данное определение эксперимента Exp(s) представляет собой случайно искаженный функцией F «фрагмент» эмпирической системы. Характеристики функции F как случайного отображения полностью определяются вероятностью. Определение вероятности остается прежним.

Для экспериментов, определенных в определении 16 с различными типами случайностей уже нельзя требовать истинности аксиом на Exp. Поэтому определение закона на Exp теряет свой смысл. Эквивалентное определение вероятностного закона, для которого должно быть выполнено условие (A0 /A1&... &Ak) = 1, так же теряет смысл, в силу того, что условная вероятность не может быть равна 1 в экспериментах с шумами. Поэтому необходимо ввести обобщение этого определения путем удаления условия, которое не может быть выполнено.

Определение 17. Вероятностным законом на Exp будем называть правило C = (A1&... &Ak A0) вида (1), удовлетворяющее следующему условию: условная вероятность (A0 /A1&... &Ak) правила определена и строго больше условных вероятностей каждого из его подправил.

Обозначим через LP множество всех вероятностных законов.

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

Предложение 3. L СВЗ LP.

Покажем, что в результате удаления условия (A0 /A1&... &Ak) = 1 из определения вероятностного закона для детерминированного случая (определение 15) мы ничего не потеряли из существа определения закона.

Вспомним, что именно свойство неупрощаемости позволило нам сформулировать определение вероятностного закона в детерминированном случае. Посмотрим на результат предыдущей теоремы (теорема 7) с точки зрения неупрощаемости закона. В вероятностных терминах свойство неупрощаемости закона звучит уже несколько иначе: для правила, истинного на M, для которого условная вероятность равна 1, неупрощаемость правила означает, что, если мы возьмем любое логически более сильное его подправило, то его условная вероятность строго уменьшится и станет строго меньше 1, т. е. вероятностный закон на Exp в детерминированном случае нельзя упростить, не уменьшив существенно его условную вероятность. Поэтому два эквивалентных определения закона, сформулированные в теореме могут быть переформулированы в терминах неупрощаемости закона, только одно из них для значения истинности, а другое для условной вероятности. Из этой переформулировки видно, что для понятия закона важны не сама истинность или то, что условная вероятность равна 1, а невозможность его упрощения с сохранением этих оценок (истинности, вероятности и т. д.). Это дает возможность дать более общее определение закона для правил вида (1), охватывающее как детерминированный так и вероятностный случаи.

Определение 19. Законом является такое правило C вида (1), характеризуемое некоторой оценкой, что его нельзя «упростить» (логически усилить – теорема 4) не уменьшив существенно этой оценки.

Эквивалентность двух различных определений закона с точки зрения данного определения закона для двух различных видов оценок – оценки истинности и оценки условной вероятности, равной 1, доказана (теорема 7). При переходе от вероятностного закона в детерминированном случае (определение 15) к вероятностному закону (определение 17) мы заменили оценку закона с условной вероятности равной 1 на просто оценку условной вероятности, оставаясь в рамках закона (определение 19).

Условная вероятность, используемая нами (теорема 7, определение 15, определение 17) как оценка закона, интересна не только тем, что это вероятность, но еще и тем, что она является оценкой предсказательной силы закона, являющейся наиболее важной характеристикой законов вообще.

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

Теорема 7 в этом случае означает, что для детерминированного случая, который характеризует возможность предсказания в случае отсутствия шумов, определения закона через истинность и условную вероятность совпадают. Но если мы имеем стохастический случай, когда правила не истинны на M, определение закона через истинность теряет свой смысл, а определение закона, основанное на условных вероятностях и предсказании, сохраняет свой смысл.

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

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

Множество вероятностных законов шире множества законов (см.

предложение 3), поэтому, обнаруживая вероятностные законы, мы будем обнаруживать как аксиомы теории так и просто вероятностные законы.

Чтобы выделить среди вероятностных законов аксиомы из есть два пути.

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

§ 26. Тестирование систем аксиом в условиях шумов Процесс получения результатов эксперимента (см. определение 16) можно разделить на два этапа: получение результатов эксперимента в «чистом» виде, как «фрагмента» некоторой эмпирической системы, а затем получение результатов реального эксперимента «добавлением» шумов. Выделить эти два этапа можно, введя две вероятностных меры для значений экспериментов: вероятностную меру в детерминированном и стохастическом случаях. Первая их них D будет удовлетворять дополнительному требованию 2 (определение 16) для вероятностей в детерминированном случае, а вторая S будет вероятностной мерой в общем случае.

Введение двух вероятностных мер позволит нам ввести вероятностную модель шумов. Вернемся к определению эксперимента (определение 16) Стохастический эксперимент Exp(s) получается в два этапа: сначала получается результат детерминированного эксперимента в соответствии с вероятностной мерой D, а затем применяется случайное преобразование F, отражающее влияние на результаты детерминированного эксперимента шумов, ошибок, неточности приборов и т. д. в соответствии с вероятностной мерой S. Приведем соответствующие определения.

Определим переход от значений детерминированного эксперимента, представленного некоторыми наборами в двоичном кубе E, к значению стохастического эксперимента как действие случайной функции F : E E.

Отображение F есть некоторое случайное взаимнооднозначное отображение. Вероятностные характеристики этого отображения и соответственно модель шумов задаются соотношением двух вероятностей D и S. При этом вероятность S – есть вероятность реальных экспериментов, а D – вероятность гипотетического «идеального» эксперимента на эмпирической системе.

Устойчивость понятия вероятностной закономерности относительно некоторого типа шумов означает, что если некоторое множество правил {Ci} является множеством вероятностных законов в детерминированном случае, то то же самое множество правил будет множеством вероятностных законов и в стохастическом случае.

Эта формулировка ставит следующую проблему: определить какие вероятности и модели шумов сохраняют множество вероятностных законов.

Определение 20. Назовем сохраняющими моделями шумов такие пары вероятностей S, D, для которых множество вероятностных законов LP для вероятности S и множество законов L для вероятности D совпадают.

Если мы ограничим себя рассмотрением только сохраняющих моделей шумов, то задача 6 решается так же, как задача 7.

Поэтому данная работа ставит проблему: определить множество сохраняющих моделей шумов. Но как определить является ли модель шумов сохраняющей или нет. Это можно сделать либо аналитически, либо машинным моделированием. Пример аналитического доказательства приведен в следующем параграфе.

§ 27. Сохраняющий двоичный шум Предположим, что у нас есть эксперимент Exp(s) = a1,..., am, I(M)I(X())s и вероятность для детерминированного случая D. Определим шумы, задающие случайное преобразование F : E E. Предположим, что каждое атомарное высказывание, значение которого получается в эксперименте, подвергается воздействию независимой и одинаково распределенной двузначной случайной величины, принимающей значение 1 с вероятностью > 0.5 и 0 с вероятностью 1-. Если значения эксперимента представить как двоичный вектор 1, 1, 0,..., 0, 1, где 1 – истина, а 0 – ложь, то преобразование F : E E примет вид:

где 1, 2,..., n – различные независимые случайные величины с распределением. Эксперимент с преобразованными значениями атомарных высказываний обозначим через FExp(s). Пусть S – вероятность (определение 16) для случайно преобразованного эксперимента.

Теорема 8. Множества вероятностных законов для эксперимента Exp(s) с вероятностью D и эксперимента FExp(s) с вероятностью S равны.

Доказательство. Нужно доказать, что правило C = (A1&... &Ak A0) является вероятностным законом для эксперимента Exp(s) тогда и только тогда, когда оно является вероятностным законом для эксперимента FExp(s). В стохастическом эксперименте FExp(s) правило *C примет вид (1*A1&... &k*Ak 0*A0), где 1*,..., k*, 0* – случайные величины вида 1 2,..., n, если литера A1,..., Ak, A0 не содержит отрицания, или случайные величины вида 1 - 1, 1 - 2,..., 1 - n, если литера содержит отрицание.

Надо доказать, что правила C = (A1&... &Ak A0) и *C = (1*A1&... &k*Ak 0*A0) одновременно либо являются, либо не являются вероятностными законами. Докажем это последовательностью эквивалентных преобразований. Пусть правило *C является вероятностным законом. Тогда (0*A0 / 1*A1&... & k*Ak) > (0*A0 / 2*A2&... & k*Ak), (22) для подправила вида 2 (теорема 4) (2*A2&... &k*Ak 0*A0).

Распишем это неравенство:

(0*A0&1*A1&... & k*Ak) / (1*A1&... & k*Ak) > (0*A0&2*A2&... & k*Ak) / (2*A2&... & k*Ak).

Рассматривая значения литер A0, A1,..., Ak, как точку в двоичном кубе, мы можем заменить операцию конъюнкции на умножение. Тогда получим следующее эквивалентное неравенство:

Это неравенство легко преобразуется эквивалентным образом в силу независимости случайных величин как между собой так и относительно литер A1,..., Ak, A0:

Если два события A, B независимы, то (A&B) = (A)(B). Так как операция • является конъюнкцией, то (A • B) = (A)(B). Отсюда получаем следующее эквивалентное преобразование неравенства:

(A0 • A1 •…• Ak) / (A1 •…• Ak) > (A0 • A2 •…• Ak) / (A2 •…• Ak) Но последнее неравенство и есть то, что нам требуется доказать, а именно вероятностное неравенство, аналогичное неравенству (22), но только относительно правила C, а не правила *C. Так как последнее неравенство было получено эквивалентными преобразованиями, то обратное так же верно, т. е. если неравенство (22) выполнено для правила C, то оно будет выполнено и для правила *C. Справедливость аналогичного неравенства относительно других подправил вида 2 (теорема 4) доказывается аналогично. Таким образом справедливость теоремы относительно подправил вида 2 доказана.

Для завершения доказательства теоремы необходимо доказать аналогичное неравенство для подправил вида 1 (теорема 4).

Рассмотрим неравенство (0*A0 /1*A1&... & k*Ak) > (¬1*A1 / 2*A2&... & k*Ak) Распишем его аналогичным образом. Отрицание ¬1*A1 равно (1A1. Но поскольку сама случайная функция 1* есть либо 1, либо 1-1 в зависимости от наличия либо отсутствия отрицания у атома A1, то обозначение случайной величины ¬1* можно оставить тем же самым, а именно 1*. Поэтому мы получим неравенства Заменим операцию конъюнкции на операцию умножения.

Проведем серию эквивалентных преобразований.

(0* • 1* •…• k* • A0 • A1 •…• Ak) / (1* •…• k* • A1 •…• Ak) > (1* • 2* •…• k* • A1 • A2 •…• Ak) / (2* •…• k* • A2 •…• Ak).

Отсюда получаем следующие эквивалентные преобразования.

0* • 1* •…• k* (A0 • A1 •…• Ak) / 1* •…• k* (A1 •…• Ak)> 1* • 2* •…• k* (A1 • A2 •…• Ak) / 2* •…• k* (A2 •…• Ak) Так как 0* = 1* =, то мы получаем требуемое неравенство, так как последнее неравенство и есть то, что нам требуется доказать. Аналогичное доказательство проводится для остальных подправил вида 1 (теорема 4).

ГЛАВА 3. ЛОГИЧЕСКИЙ ПУТЬ ПОЗНАНИЯ.

ПРОБЛЕМА ПРЕДСКАЗАНИЯ.

§ 28. Знание и познание В предыдущей главе был рассмотрен процесс познания, основанный на теории измерений. Он состоял в разработке метода обнаружения эмпирической аксиоматической теории предметной области, включающей системы аксиом, представленной некоторой эмпирической системой.

Рассмотрим более общую задачу.

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

Знания – это высказывания, имеющие некоторую степень вероятности, нечеткости, достоверности и т. д.

Рассмотрение знаний сталкивается со следующими принципиальными и нерешенными проблемами:

1) знания логически противоречивы и не образуют теорию;

2) предсказание для знаний плохо определено – вероятностные оценки знаний резко падают в процессе логического вывода;

3) предсказания, получаемые из знаний, статистически двусмысленны.

Эти проблемы известны и обсуждаются, например, в широко цитируемой работе L. De Raedt and K. Kersting. «Probabilistic logic learning» [141].

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

Проблемы 1–3 являются следствием более глубокой проблемы:

4) в настоящее время не существует адекватного синтеза логики и вероятности.

Этой проблеме в 2002 г. был посвящен workshop «Combining Probability and Logic” (King's College London 4th–6th November 2002). В аннотации к workshop говорится: «Artificial intelligence is one key discipline in which probability theory competes with other logics for application. It is becoming vitally important to evaluate and integrate systems that are based on very different approaches to reasoning, and there is strong demand for theoretical understanding of the relationships between these approaches».

Во введении к спецвыпуску «Journal of Applied Logic» 1 (2003), Special issue on Combining Probability and Logic, посвященному этому workshop, Jon Williamson, Dov Gabbay писали: «One approach is to argue that probability is logic, which requires showing that probability is a determinate relation between statements. Kyburg, Howson and Paris and Vencovsk appeal to the concepts of frequency, consistency and entropy respectively to determine this relation. Alternatively one can explore other formalisms which interface between probability and logic: argumentation in the case of Fox and Kohlas; default reasoning in the case of Bourne and Weydert».

Однако настоящего синтеза логики и вероятности в этих работах не сделано.

Нам удалось разрешить проблемы 1–4 и осуществить синтез логики и вероятности для понятия предсказания [154; 157–158]. Предсказание является одним из важнейших понятий в науке, однако до сих пор адекватного, с нашей точки зрения, определения этого понятия не существует. Мы покажем, что это связано с нерешенностью проблемы 4. Решение проблемы как и других проблем связано с радикальным изменением парадигмы в логике: предсказание нельзя вывести, его можно только вычислить. Такой процесс вычисления нами разработан на основе семантического вероятностного вывода, который следует идее семантического подхода к программированию выдвинутого Ю. Л. Ершовым, С. С. Гончаровым и Д. И. Свириденко. Идея семантического программирования состоит в том, чтобы процесс вычисления рассматривать как проверку истинности утверждений (включая возможное использование логического вывода) на некоторой модели (моделью могут быть данные, представленные некоторой многосортной системой; некоторая специальная модель теории или абстрактного типа данных и т. д.). При таком взгляде на процесс вычисления, процедуру логического вывода можно обобщить, рассматривая более разнообразные взаимоотношения высказываний и модели – рассмотреть процесс вычисления как, например, определение наиболее вероятных, подтвержденных или нечетких высказываний на модели. Такой обобщенный вывод будем называть семантическим.

В настоящее время определение понятия предсказания для индуктивных теорий, содержащих знания, осуществляется Индуктивностатистическим I–S (Inductive–Statistical) выводом. Гемпелем было замечено, что предсказания получаемые I–S-выводом статистически двусмысленны. Что бы избежать такой двусмысленности он ввел для законов, используемых в I–S-выводе, требование максимальной специфичности RMS (Requirement of Maximum Specificity). Он не дал формального определения этому требованию, но дал достаточно четкую формулировку. Различные формализации этой формулировки показали, что они также не решают проблемы статистической двусмысленности. Из-за этой проблемы считается, что предсказание для индуктивных теорий не поддается адекватной формализации.

В этой главе мы рассмотрим проблему формализации понятия предсказания для индуктивных теорий. Мы введем своё определение множества всех максимально специфических правил MSR и докажем, что, во-первых, оно непротиворечиво, а во-вторых, для него не возникает проблемы статистической двусмысленности. Тем самым такие правила могут использоваться в I–S-выводе без противоречий. Мы определим семантический вероятностный вывод, который позволяет вывести все четыре множества законов L, LP и MSR.

§ 29. Индуктивно-статистический вывод Индуктивно-статистический вывод Гемпеля по выводу некоторого факта G имеет вид:

Он удовлетворяет следующим условиям:

i) L1, …, Lm, C1, …, Cn G;

ii) множество L1, …, Lm, C1, …, Cn непротиворечиво;

iii)L1, …, Lm G, C1, …, Cn G;

iv) множество L1, …, Lm содержит статистические законы. Множество фактов C1, …, Cn не имеет кванторов;

v) RMS: все законы L1, …, Lm максимально специфичны.

По Гемпелю [111], требование максимальной специфичности RMS (Requirement of Maximal Specificity) определяется следующим образом.

I–S-вывод вида:

является приемлемым I–S-предсказанием при состоянии знания K, если следующее требование RMS выполнено. Для каждого класса H, для которого оба следующих высказывания принадлежат K:

Существует статистический закон p(G; H) = r’ в K такой, что r = r’. Основная идея RMS состоит в том, что если F и H оба содержат объект a, и H является подмножеством F, то H обладает более специфической информацией об объекте a чем F и следовательно закон p(G; H) должен предпочитаться закону p(G; F).

§ 30. Семантический вероятностный вывод.

Определение 21. Под семантическим вероятностным выводом (СВВ) некоторого сильнейшего вероятностного закона (СВЗ, см. определение 18) мы понимаем такую последовательность вероятностных законов C1 C... Cn, что C1, C2,..., Cn LP, Ci = (A1 &...& A iki G), i = 1, 2,..., n, n 1, правило Ci является подправилом правила Ci+1, Предложение 4. Любой вероятностный закон принадлежит некоторому СВВ-выводу.

Предложение 5. Для любого СВЗ-закона существует СВВ-вывод этого правила.

Следствие 3. Для любого закона из L существует СВВ-вывод этого закона.

Рассмотрим множество всех СВВ-выводов некоторого факта G. Это множество можно представить как семантическое вероятностное Дерево выводов (СВДВ-дерево) факта G (рис 7).

Определение 22. Максимально специфическим законом вывода факта G ( МСЗ(G) ) мы определим сильнейший вероятностный закон СВДВдерева вывода факта G, имеющий максимальное значение условной вероA3k1+1&...&A3k3& ятности среди всех других сильнейших вероятностных законов СВДВдерева вывода факта G.

Множество всех максимально специфических законов обозначим через МСЗ.

Предложение 6. L МСЗ СВЗ LP.

§ 31. Требование максимальной специфичности Определим требование максимальной специфичности (ТМС). Будем предполагать, что класс H объектов в (23) определён некоторым предложением H () языка L. В том случае требование ТМС говорит о том, что должно быть выполнено равенство p(G; H) = p(G; F) = r. В терминах вероятности это означает, что (G / H) = (G / F) = r для любого H (), удовлетворяющего (23).

Определение 23. Требование максимальной специфичности (ТМС):

a) если мы добавим предложение H () к посылке правила C = (F G) (то предложение (1) x(F(x)&H(x) F(x)) истинно);

b) и будет выполнено условие F(a)&H(a) (тогда (F&H) > 0), то должно выполняться равенство (G / F&H) = (G / F) = r.

Другими словами, ТМС означает, что не существует утверждения H (), которое увеличивает (или уменьшает, см. нижеследующую лемму) условную вероятность (G / F) = r путем добавления его в посылку правила.

Лемма 8. Если утверждение H () уменьшает условную вероятность (G / F&H) < (G / F), то утверждение ¬H увеличивает ее и (G / F&¬H) > (G / F).

Доказательство. Введем обозначения a = (G&F&H’), b = (F&H’), c = (G&F&¬H’), d = (F&¬H’). Тогда неравенство (G / F&H’) < (G / F) моно заменить на неравенство a / b < (a + c) / (b + d). Из неравенства a / b < (a + c) / (b + d) следует, что Лемма 9. Для любого правила C = (B1&... &Bt A0), (B1&... &Bt) > вида (1) существует вероятностный закон C’ = (A1&... &Ak A0) на M, являющийся подправилом правила C и (C’) (C) Теорема 9. Любое МСЗ(G) правило удовлетворяет требованию ТМС.

Доказательство. Нам надо доказать, что для любого предложения H () равенство (G / F&H) = (G / F) = r имеет место для любого МСП(G) правила C = (F G).

Из условия b (определение 23) следует, что (F&H) > 0 и, следовательно, условная вероятность определена.

Рассмотрим случай, когда предложение H является некоторым атомом B или отрицанием атома ¬B и (G / F&H) r. Тогда одно из правил (F&B G) или (F&¬B G) (лемма 8) имеет большее, чем r значение условной вероятности (F&B G) > r (F&¬B G) > r. Тогда существует вероятностный закон (лемма 9) C’, являющийся подправилом правила C, такой что (C’) (C) > r. Правило C’ принадлежит СВДВ-дереву и имеет большее значение условной вероятности, что противоречит предположению о том, что правило C является МСЗ(G)-правилом.

Рассмотрим случай, когда предложение H является конъюнкцией двух атомов B1&B2, для которых теорема доказана. Если одно из неравенств (G / F&B1&B2 ) > r, (G / F&¬B1&B2 ) > r, (G / F&B1&¬B2 ) > r, (G / F&¬B1&¬B2 ) > r выполнено, то существует вероятностный закон (лемма 9) C’ СВДВ-дереву, являющийся подправилом правила C, такой, что (C’) (C) > r. Но это невозможно, так как правило C является МСЗ(G)-правилом. Следовательно, для всех этих неравенств мы имеем только равенство = или неравенство <. Последний случай невозможен изза следующего равенства Случай, когда предложение H является конъюнкцией нескольких атомов или их отрицаний доказывается индукцией.

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

Для завершения доказательства нам достаточно рассмотреть случай, когда предложение H является дизъюнкцией двух непересекающихся предложений DE, (D&E) = 0, для которых теорема уже доказана и (G / F&D) = (G / F&E) = (G / F) = r. Оно следует из следующего равенства:

Случай дизъюнкции большего числа непересекающихся предложений следует по индукции из случая двух непересекающихся предложений Лемма 10. Любой закон из L удовлетворяет требованию ТМС.

§ 32. Решение проблемы статистической двусмысленности Проблема статистической двусмысленности. В отличие от дедуктивного вывода, в индуктивном выводе мы можем вывести противоречивые выводы из непротиворечивых посылок.

Предположим, что в теории J есть следующие утверждения:

(G&F) (G&F&B1 & B2 )) + (G&F&¬B1 & B2 )) + (G&F&B1 & ¬B2 )) + (G&F&¬B1 & ¬B2 )) (Л1) – ‘почти все случаи заболевания стрептококком быстро вылечиваются инъекцией пенициллина’;

(Л2) – ‘почти никогда устойчивая к пенициллину стрептококковая инфекция вылечивается после инъекции пенициллина’;

(C1) – ‘Джейн Джонс заболел стрептококковой инфекцией’;

(C2) – ‘Джейн Джонс получил инъекцию пенициллина’;

(C3) – ‘Джейн Джонс имеет устойчивую к пенициллину стрептококковую инфекцию’.

Из этой теории можно вывести два противоречивых утверждения: одно, объясняющее почему Джейн Джонс выздоровеет быстро (E), и другое, объясняющее отрицание первого: почему Джейн Джонс не выздоровеет быстро (¬E).

Условия обоих объяснений не противоречат друг другу, оба могут быть истинны. Тем не менее их выводы противоречат друг другу. Потому набор правил TP может быть противоречив.

Гемпель надеялся решить эту проблему, требуя от статистических законов, чтобы они удовлетворяли требованию максимальной специфичности. Они должны содержать всю относящуюся к рассматриваемому вопросу информацию. В нашем примере условие C3 второго объяснения опровергает условие первого объяснения в силу того, что закон L1 не максимально специфичен по отношению ко всей информации относительно Джонса в теории J. Потому теория J может объяснить только утверждение ¬E, но не E.

Теорема 10. I–S-вывод непротиворечив для любой теории J МСЗ.

Доказательство. Докажем, что для предложений из теории J МСЗ нельзя получить противоречие, когда у нас есть два вывода {A G, B ¬G} J МСЗ, при условии, что (A&B) > 0. Мы докажем, что в этом случае одно из приведенных выше правил имеет большую оценку условной вероятности, чем правила A G, B ¬G:

Тогда существует вероятностный закон (лемма 9), условная вероятность которого выше, чем у правил A G, B ¬G, что противоречит условию J ММСП.

Рассуждая от противного, правила (25) имеют условную вероятность не большую, чем правила A G, B ¬G.

Рассмотрим первое из правил A&B G. По предположению (G / A&B) (G / A). Рассмотрим два случая:

а) (A&¬B) 0. Так как (A&B) > 0, то Если первое неравенство строгое, то и другие неравенства строгие.

Следовательно, из неравенства (G / A&B) < (G / A) следует, что (G / A&¬B) > (G / A). Этим данный случай рассмотрен. Осталось рассмотреть случай (G / A&B) = (G / A);

(б) (A&¬B) = 0. Так как (A&B) > 0, то Оставшийся случай такой же (G / A&B) = (G / A).

Рассмотрим правило A&B ¬G. По предположению мы имеем (¬G / A&B) (¬G / B). Проводя аналогичные рассуждения, получим:

Если неравенство строгое (¬G / A&B) < (¬G / B), то получим неравенство (¬G / ¬A&B) > (¬G / B) и теорема для этого случая доказана.

Осталось рассмотреть случай (¬G / A&B) = (¬G / B).

Рассмотрим случаи 1, 2, когда мы имеем равенство Поскольку правила A G и B ¬G являются вероятностными законами и они удовлетворяют условиям (¬G / B) > (¬G), (G / A) > (G), Итак мы получили противоречие с предположением Проиллюстрируем эту теорему на предыдущем примере. Максимально специфичными правилами для высказываний Е и ¬E будут следующие правила МСЗ(E) и МСЗ(¬E):

(Л1)’ : ‘Во всех случаях заражения стрептококковой инфекцией, которая не устойчива к пенициллину, происходит быстрое выздоровление после инъекции пенициллина’.

(Л2): ‘Почти нет случаев устойчивых к пенициллину стрептококковых инфекций и поэтому выздоровление происходит быстро после инъекции пенициллина.’ Правило (Л1)’ имеет большую условную вероятность, чем исходное правило (Л1) и, следовательно, оно должно быть максимально специфичным МСЗ(E)-правилом для высказывания E. Правила (Л1)’ и (Л2) уже не могут быть выполнены на одних и тех же данных.

Заключение. Если мы сможем обнаружить множество всех максимально специфичных правил ММСП, то мы их без противоречий сможем использовать для предсказаний в I–S-выводах.

§ 33. Проблема логического вывода Методы машинного обучения (Mashine Learning) часто используются в экспертных системах и системах принятия решений для получения новых знаний из данных. Полученные знания используются далее для принятия решений с помощью методов логического вывода, которые абстрагируются от возможной недостоверности знаний и осуществляют вывод, как будто бы мы имели достоверные знания. В результате решения имеют неопределенную степень достоверности и, строго говоря, непонятно в каком смысле являются решениями.

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

Есть работы, в которых степень достоверности рассматривается как значение истинности утверждений, а процесс логического вывода обобщается до так называемой «количественной дедукции» [100–101; 103; 107;

145; 149–151]. В последних работах [100; 149–150] описываются довольно богатые формальные системы, содержащие как частные случаи основные известные «количественные дедукции».

В какой степени разработанные методы оценки достоверности обосновывают и придают смысл решениям ?

Рассмотрим знания, полученные методами машинного обучения на вероятностных данных. Анализ изменения вероятностных оценок утверждений в процессе логического вывода показывает, что они могут значительно уменьшаться. Как следует из работ по вероятностной логике [107; 144; 137], полученные оценки не могут быть улучшены. Даже если ограничиться использованием правил с условной вероятностью не меньшей чем 1-e, как это делается в [87], то это все равно не избавляет нас от существенного уменьшения вероятности в процессе вывода и, кроме того, это не соответствует условиям реально возникающих задач.

Рассмотрим знания, извлекаемые и оцениваемые экспертом. В работах по «количественной дедукции» [100; 149–150] истинностное значение заключения правила вычисляется как функция минимума или наибольшей нижней границы (для значений истинности в решетке) значений истинности атомов посылки. Соответствует ли это экспертным оценкам правила?

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

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

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

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

Невозможность адекватного вычисления оценок решений говорит о неадекватности и самого аксиоматического подхода к построению баз знаний и необходимости его пересмотра. На какой основе это можно сделать?

Рассмотрим процесс вычисления с точки зрения «семантического»

подхода к программированию [20 ;104]. Идея семантического программирования состоит в том, чтобы процесс вычисления рассматривать как проверку истинности утверждений (включая возможное использование логического вывода) на некоторой модели (моделью могут быть данные, представленные некоторой многосортной системой; некоторая специальная модель теории или абстрактного типа данных предметной области и т. д.).

При таком взгляде на процесс вычисления, процедуру логического вывода можно обобщить, рассматривая более разнообразные взаимоотношения высказываний и модели – рассмотреть процесс вычисления как, например, определение вероятности, подтвержденности, достоверности, статистической значимости и т. д. высказываний на модели. Такой обобщенный вывод будем называть семантическим.

В работе семантический подход к базам знаний разрабатывается для случая ПРОЛОГ-программ в языке первого порядка с вероятностной мерой [90; 93–95; 133–136; 147], а так же вероятностных данных (нам извероятностная мера, вестна вероятностная модель данных заданная на множестве всех основных предложений (см. определение 24).

Наиболее важной вероятностной оценкой решений является оценка предсказательной силы высказываний. Высказывание вместе с такой оценкой назовем предсказанием.

Рассмотрим сначала стандартный процесс вычисления ПРОЛОГпрограмм. Предсказанием запроса ПРОЛОГ-программой PR назовем такое вычисление запроса, на котором достигается максимум оценки условной вероятности запроса относительно подставленных в процессе вычисления фактов. Оценки условных вероятностей можно вычислить по вероятностным характеристикам правил и фактов, используя вероятностную логику (см. оценки в п. 4). Оценки не ухудшаются, если в процессе вывода используются правила, имеющие условную вероятность равную единице, и могут значительно ухудшаться, если используются правила с условной вероятностью, строго меньшей 1.

Цель предсказания в общем случае состоит в нахождении таких фактов, из которых решение следовало бы с максимальной условной вероятностью. Предсказание, получаемое ПРОЛОГ-программой, не удовлетворяет этой цели. Во-первых, вероятностные оценки запроса могут существенно снижаться в процессе вычисления, а во-вторых, вычисление не всегда может приводить к фактам, дающим максимальную оценку условной вероятности запроса.

Для получения наилучших предсказаний для любого одноатомного запроса A в работе определяется семантический процесс вычисления – вероятностный вывод, в котором вычисление осуществляется путем движения вдоль «уточняющего» графа [146–147]. В этом графе правила, начиная с A, «уточняются» либо добавлением произвольного атома (или конъюнкции атомов) в посылку, либо применением подстановки. Выбор уточнения, удлиняющего соответствующую ветвь графа, определяется требованием увеличения условной вероятности, определяемой по вероятностной модели данных. Результатом вычисления является результирующая подстановка и достигнутая условная вероятность.

На уточняющие правила в вероятностном выводе можно наложить (без ограничения общности) дополнительное требование: чтобы каждый атом в посылке был «существенным» для предсказания атома A (удаление любого атома из посылки уменьшало бы условную вероятность атома A). Такие правила называются вероятностными закономерностями. Для получения любого вероятностного вывода, таким образом, достаточно иметь множество всех возможных вероятностных закономерностей данной вероятностной модели данных. В работе это множество обозначается через PR( ).

Отметим, что для вероятностного вывода не нужны никакие правила вывода. Процесс вычисления вполне определяется увеличением оценки условной вероятности (определяемой вероятностной моделью данных ).

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

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

Пусть есть данные D(N) из некоторой модели N, случайно выбранной из множества возможных миров G в соответствии с вероятностной моделью данных. Рассмотрим ПРОЛОГ-программу PR(, N) = P( )D(N), где P( ) PR( ) – множество всех вероятностных закономерностей с непустой посылкой. В работе доказывается, что программа PR(, N) предсказывает лучше любой другой ПРОЛОГ-программы Pr, имеющей те же факты D(N). Более того, предсказание любого атома A (данной сигнатуры) осуществляется «лучшим для предсказания атома A правилом»

(см. определение 34) в один шаг, не считая подстановки фактов. «Лучшее для предсказания атома A правило» является вероятностной закономерностью и может быть получено вероятностным выводом.

Таким образом, база знаний PR( ), рассматриваемая как ПРОЛОГ-программа, предсказывает на одних и тех же фактах лучше любой другой ПРОЛОГ-программы.

Почему множеству вероятностных закономерностей удается аппроксимировать по предсказанию значительно более разнообразный и богатый комбинационными возможностями логический вывод? Поясним это на примере шахматной игры. Целью игры является выигрыш, а правила игры можно представить как правила вывода. Опытный игрок никогда не использует чисто комбинационный анализ всех возможных ходов за себя и за противника, т. е. чисто логический вывод. Для достижения выигрыша и проведения глубокого анализа вариантов, игрок использует некоторую оценку позиции, которую он стремится улучшить. Ведущей к цели – выигрышу – становится оценка, а перебор вариантов подчинен требованию улучшения оценки позиции. Логический вывод не должен быть самоцелью. Цель вывода должна определяться независимо от самого вывода, а логический вывод должен быть подчинен поставленной цели.

Точный анализ цели доказательств в математических теориях осуществлен в [45]. Цель доказательств состоит в решении задач: «... мы понимаем задачу только тогда, когда ей сопоставили обоснованное чувство уверенности в том, что всякое состояние нашего сознания мы сумеем убедительным и безошибочным образом распознать как такое, когда решение найдено, или как такое, когда решение задачи не найдено» [45]. Формализация этого требования и его анализ показал, что оно накладывает существенные ограничения на формальные системы, в которых должны ставиться и решаться задачи.

В задачах искусственного интеллекта приведенное требование на осмысленность постановок задач также должно быть выполнено. Задача принятия решений осмысленна только тогда, когда мы не только можем вывести решение, но и всегда определить, является ли оно таковым. В работах [45] показано, что формальные системы для постановок и решения задач должны быть слабыми. Для этого подходит, в частности, логическое программирование. Как отмечается в работе [Там же], «...в рамках новой парадигмы выглядит весьма естественным так называемый «логический подход к программированию»,... согласно которому следует создавать языки спецификаций не только программ, но и задач».

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

В заключении отметим, что множество PR(, N) не является слишком большим. Понятие вероятностной закономерности было ранее введено автором для разработки метода обнаружения закономерностей [9; 10; 32–33] - метода построения всех статистических аппроксимаций вероятностных закономерностей, т. е. метода построения статистической аппроксимации множества PR( ). Этот метод был реализован и успешно применялся для решения ряда практических задач. Опыт решения задач показал, что множество PR( ) практически может быть найдено даже на малых ЭВМ.

§ 34. Эрбрановы модели. Вероятностная модель данных.

Зафиксируем язык первого порядка L с равенством не более чем счетной сигнатуры =, C = {CkK}, K. Обозначим через U множество всех основных термов (не содержащих свободных переменных), X – множество переменных, T – множество термов, F – множество формул, F0 – множество формул без кванторов, S – множество предложений (формул без свободных переменных), = F0S множество всех основных предложений сигнатуры.

Следуя работе [108], определим вероятность на подмножестве F, F предложений, замкнутом относительно логических операций &,, ¬ (равенство не строгое, для строгого равенства необходимы дополнительные аксиомы (см. [Там же]).

Определение 24 [Там же]. Вероятностью на подмножестве F называется отображение : F [0, 1], удовлетворяющее условиям:

Следствие [Там же]. Если, то () = (). Если ¬, то () = Вероятность является конечно-аддитивной мерой на подалгебре { / | F} булевой алгебры Линденбаума–Тарского.

Определение 25. Вероятностной Эрбрановой моделью сигнатуры будем называть пару M =, где – вероятность на. Функциональные символы интерпретируются на U обычным образом [90].

Определение 26. Эрбрановой моделью сигнатуры будем называть вероятностную Эрбранову модель M =, где I : {0, I}.

Рассмотрим множество S всех Эрбрановых моделей M = сигнатуры. Пусть дан некоторый класс Эрбрановых моделей G S (множество возможных миров) и вероятность на некотором подмножестве F формул замкнутом относительно логических операций. Определим булеву подалгебру D подмножеств G() = {M | M G, M }, F множества G. Где обозначает выполнимость утверждения на модели M.

Определение 27. Класс Эрбрановых моделей G будем называть согласованным с вероятностью на множестве формул F, если из G() = 0, F следует () = 0.

Лемма 11. Величина (G()) = (), F является конечноаддитивной мерой на подалгебре D, если класс Эрбрановых моделей G согласован с на множестве формул F #.

Доказательство: Так как D – булева подалгебра подмножеств G является кольцом множеств, то достаточно доказать, что (G(1) G(2)) = (G(1)) + (G(2)), если G(1) G(2) = ; 1, 2. Так как (G(1) G(2)) = (G(1 2)) = (1 2); (G(1)) = (1); (G(2)) = (2); G(1) G(2) = G(1&2), то нам достаточно доказать, что (1 2) = (1) + (2), если G(1&2) =. Из определения меры следует, что (1 2) = (1) + (2) - (1&2). Из условия леммы и определения 2.4 следует, что если G(1&2) =, то (1&2) Если множество формул F совпадает с, то будем говорить, что класс Эрбрановых моделей G согласован с вероятностной Эрбрановой моделью M =, а модель M является вероятностной моделью множества возможных миров G или выборок из некоторой генеральной совокупности.

§ 35. Логические программы.

Обозначим через PR множество всех правил A A1, …, Ak, k 0 сигнатуры, где A, A1, …, Ak – атомы сигнатуры. Если атом A отсутствует, то правило A1, …, Ak называется целью (запросом). Если k = 0, то правило A называется фактом.

Логическая программа Pr есть конечная совокупность правил. Подстановкой называется отображение :X T. Подстановка (x) = x называется тождественной. Обозначим через множество всех подстановок. Подстановки естественным образом распространяются на произвольные выражения. Так для терма t = f(t1,..., tn) и атома A = P(t1,..., tn) их подстановки соответственно равны t = f(t1,..., tn), A = P(t1,..., tn). Правило A A1,..., An называется вариантом правила A A1, …, An если – перестановка множества X.

Зафиксируем правило вычисления R, определяющее в каждом запросе выделенный атом. Пусть N = A1&... &Ai&... &Ak, k 1 запрос, в котором правилом R выделен атом Ai и A B1&... &Bl – вариант некоторого правила программы Pr, в котором все переменные отличны от переменных запроса. Пусть – наиболее общий унификатор атомов Ai и A. Тогда запросы будем называть выводимыми из запроса N по правилу A B1&... &Bl с помощью подстановки и правила вычисления R. Как видно из определения, атом Ai не удаляется из запроса при его унификации с некоторым фактом программы. Такие атомы выделяются жирным шрифтом. Будем предполагать, что правило R не выбирает для очередного шага вывода выделенные атомы.

Пространством вычислений для программы Pr и правила вычисления R называется множество всех возможных запросов сигнатуры с заданным на нем отношением выводимости. SLDF-выводом (Linear resolution with Selection rule for Definite clauses and underlined Facts) цели N в некотором пространстве вычислений, назовем максимальную последовательность запросов N = N0, N1, N2... вместе с последовательностью правил C0, C1,... и унификаций 0, 1,..., такую что запросы Ni+1 выводимы из запросов Ni по правилам Ci с помощью подстановок i и правила R. SLDFвывод – максимальный путь в пространстве вычислений, начинающийся с N. SLDF-вывод, заканчивающийся запросом, в котором все атомы выделены, называется успешным. Конечный SLDF-вывод, не являющийся успешным – тупиковым. Множество всех SLDF-выводов, начинающихся с цели N, обычно представляют в виде дерева (префикс дерева SLDF-выводов) и называют SLDF-деревом вычислений запроса N. SLDF-дерево, содержащее успешный SLDF-вывод, называется успешным.

§ 36. Оценки вероятностей и условных вероятностей запросов.

Пусть M = – вероятностная Эрбранова модель. Рассмотрим успешный SLDF-вывод N, N1,..., Nk запроса N с помощью последовательности правил C0, C1,..., Ck-1 некоторой программы Pr, последовательности унификаций 0, 1,..., k-1; = 01... k-1 и некоторого правила вычислений Последовательность запросов N, N1,..., Nk, = 01... k-1 также будет SLDF-выводом запроса N с помощью последовательности правил C0, C1,..., Ck-1 тождественных подстановок и правила вычислений R.

Будем предполагать, что N, N1,..., Nk. В данном пункте факты A представим правилами A true. Тогда (C) = (A / true) = (A), для фактов C = A, A.

Определим через Ni^ конъюнкцию всех не подчеркнутых атомов запроса Ni. Если все атомы подчеркнуты (как в запросе Nk), то положим Nk^ true. Обозначим через NiF^ конъюнкцию всех подчеркнутых атомов запроса Ni. Тогда NiF^ – конъюнкция всех фактов, использованных в SLDF-выводе запроса N.

Цель данного пункта – оценить вероятности (N^), (N^ / NkF^) по SLDF-выводу запроса N, предполагая, что нам известны только вероятности фактов и правил.

Рассмотрим вывод запросов (1) из запроса N = ( A1&... &Ai&... &Ak), k 1 по правилу (Ai B1,..., Bl). Представим запросы (1) в виде N1 = ( A1,..., Ai-1, B, Ai+1,..., Ak), B = B1,..., Bl и N = ( A1,..., Ai,..., Ak). Конъюнкция N^ является частным случаем конъюнкции N1^, когда B = true. Оценим вероятности (N^), (N^ / N1^) в предположении, что нам известны только вероятности (N1^), (Ai), (B), p = (Ai / B^).

Лемма 12. Если (N1^) > 0 и (B) > 0, то 1) (N^) < (¬B^) + min{(N1^), (A&B^)};

2) (N^) > (N1^) - (1-p)(B^);

Доказательство. 1) (N^) = (N^&B^) + (N^&¬B^) (¬B^) + (N^&B^) (¬B^) + min{(N1^), (A&B^)};

3) (N^ / N1^) = (N^&B^) / (N1^) (A&B^) / (N1^) = p*(B^) / (N1^) = p / (N^ / B^);

2) (N^) (N^&B^) (N^&B^) - (¬N^&¬A^&B^). Выражение из правой части п. 2 утверждения леммы равно этому же выражению: (N1^) - (1-p)(B^) = (N1^) + (A&B^) - (B^) = (N1^&A) + (N1^&¬A) + (A&B^&N^) + (A&B^&¬N^) - (B^) = (B &A&¬N ) - (B ) = (B &N &A) - (B^&¬N^&¬A) = (N^&B^) - (¬N^&¬A&B^);

(1-p)(B )) / (N1 ) = 1 - (1-p) / (N / B ) (см. доказательство п. 2.) Следствие 4. Если (N1^) > 0, (B^) > 0 и p = 1, то:

1) (N1^) (N^) min{1, (¬B^) + (N1^)};

Доказательство. Подставим в предыдущую лемму значение p = 1.

Второе из неравенств 1 следует из того, что величина min{(N1^), (A&B^)} равна либо (N1^), либо (B^). Во втором случае (¬B^) + (B^) = Следствие 5. Если (N1^) > 0 и правило является фактом (A true), то:

1) (N^) min{(N1^), (A)};

2) (N^) (N1^) + (A) - 1;

3) (N^ / N1^) (A) / (N1^);

4) (N^ / N1^) 1 - (1 - (A)) / (N1^).

Доказательство. Следует из предыдущей леммы и равенств p = (A), (N^) = (N1^) Следствие 6. Если (B^) > 0, то:

1) (N^&B^) min{(N1^), (A&B^)};

2) (N^&B^) (N1^) - (1-p)(B^).

Доказательство. Следует из доказательств пп. 1, 2 леммы Рассмотрим SLDF-вывод N, N1,..., Nk запроса N посредством последовательности правил Ci = (A Bi1,..., Bili), i = 0, 1,..., k-1 и пустых унификаций. Положим Bi = (Bi1&... &Bili), pi = (Ci).

Теорема 11. Если (Bi) > 0, i = 0, 1,..., k-1, то:

Доказательство. Используем оценку 2 следствия, примененную к последнему шагу вывода от Nk-1^ к Nk. Получим (Nk-1^&Bk-1) (Nk^) pk-1)(Bk-1), где (Nk^) = (true) = 1, так как все атомы выделены. Рассмотрим вывод запроса Nk-1^&Bk-1 из запроса Nk-2^&Bk-1 посредством правила Ck-2. Снова применим оценку 2 следствия. Получим: (NkBk-1&Bk-2) (Nk-1^&Bk-1) - (1-pk-2)(Bk-2). Рассмотрим вывод запроса Nk-2^&Bk-1&Bk-2 из запроса Nk-3^&Bk-1&Bk-2 посредством правила Ck-3 и т. д. Получим (N^&B0&B1&…&Bk-1) (N1^&BBk-1) - (1 - p0)(B0). Подставляя левые части неравенств в их правые части, получаем оценку Покажем, что если из конъюнкции (N^&B0&B1& … &Bk-1) удалить все константы true, то получим конъюнкцию (N^&A0&A1&…&Ak-1). Заметим, что каждый атом конъюнкции Bi (true – не атом) в процессе вывода обязательно унифицируется с левой частью одного из правил. Следовательно, каждый атом конъюнкции B0&B1& … &Bk-1 содержится в конъюнкции A0&A1&…&Ak-1. С другой стороны, каждый атом Ai, i = 0, 1,..., k-1 содержится либо в N^, либо в правой части одного из правил Ci, i = 0, 1,..., k- Следствие 7. Если (Bi) > 0, i = 0, 1,..., k-1, то:

Доказательство. Следует из (N^) > (N^&A0&... &Ak-1) и теоремы 4. Для каждого успешного SLDF-вывода N = N0, N1,..., Nk существует успешный SLDF’-вывод N = N0, N’1,..., N’i,..., Nk, в котором факты применяются последними и до запроса N’i применяются правила Cj с длиной lj 1; j = 0,..., i-1. Тогда запрос N’i будет иметь вид A1,..., Am, а запрос Nk – вид A1,..., Am. Такой SLDF’ - вывод будем называть нормализованным.

Теорема 12. Если (Bj) > 0, j = 0,1,..., i-1, и (NkF^) > 0, то где pj – условные вероятности, а Bj – условия правил Cj, j = 1,..., i-1.

Доказательство: Проводится аналогично доказательству предыдущей теоремы, но для нормализованного вывода и начинается с запроса i. Первое неравенство имеет вид (Ni-1^ &Bi-1) (Ni^) - (1-pi-1)(Bi-1), где (Ni^) = (NkF^). Далее, рассуждая как в теореме 4.1, получаем неравенстi B0& … &Bi-1) (N^&NkF^), то (N^ / NkF^) = (N^&NkF^) / (NkF^) § 37. Вероятностные оценки запросов Определим вероятностные оценки (N), (N) запросов для пространства вычислений программы Pr по правилу R. Рассмотрим SLDF-дерево некоторого запроса N пространства вычислений. Если SLDF-дерево не успешно, то оценки (N), (N) не определены. Для успешного SLDF-дерева рассмотрим множество {SLDF’1,..., SLDF’m} всех успешных нормализованных SLDF’-выводов целей N1,..., Nm у которых конечные запросы N1k1,..., Nmkm не содержат переменных. Если это множество пусто, то оценки (N), (N) не определены.

Вычислим оценки 1,..., m, равные правой части неравенств следствия 4.4, для вероятностей (N^1) 1,..., (N^m) m запросов N1,..., Nm.

Вычислим также оценки 1,..., m, равные правой части неравенств теоремы 4.2 для условных вероятностей (N^1 / N1k1F^) > 1,..., (N^m / NmkmF^) > m запросов N1,..., Nm. Положим (N) = sup{1,..., m}, (N) = sup{1,..., m}. Выбор операции sup не регламентируется чисто логическими соображениями. В данном случае автор исходит из желания объединить такие понятия как логический вывод (с вероятностными оценками) и предсказание.

Если один из выводов SLDF’1,..., SLDF’m состоит только в применении фактов, то, как следует из теоремы, он будет иметь оценку (N) = 1. Назовем такой SLDF-вывод проверкой истинности запроса N (по аналогии с семантическим программированием [104]). Предсказанием запроса N будем называть такой SLDF-вывод запроса N, на котором достигается оценка (N). Оценкой предсказания запроса N будем называть величину (N). Если предсказание не определено, то оценка предсказания (N) не определена.

Пусть M = – вероятностная Эрбранова модель, согласованная с классом G.

Определение 28. Программа Pr истинна на Эрбрановой модели N, N Pr тогда и только тогда, когда каждое правило истинно на N. Правило истинно на N тогда и только тогда, когда оно истинно на N при любых состояниях (при любых отображениях : X U) [90].

Определение 29. Программа Pr истинна на классе моделей G тогда и только тогда, когда N Pr, N G.

Распространим вероятность на множество формул со свободными переменными F0. Для F0\S положим () = inf {()}, где G – множество всех подстановок основных термов вместо переменных. Для правил C = A B1,..., Bk k 0, определим условную вероятность равенством (C) = (A) / (B1&... &Bk), если правило не содержит переменных, и равенствами если правило содержит переменные. Если ((B1&... &Bk)) = 0 для некоторой подстановки G или (B1&... &Bk) = 0 для B1&... &Bk, то значение (C) не определено. При k = 0 правило C = A рассматривается как правило A true с вероятностью посылки (true) = 1. Далее запись (C) всегда означает, что вероятность (C) определена. Обозначим через PR0, PR0 PR множество всех правил сигнатуры, для которых вероятность определена.

Лемма 13. () > (), F0, – некоторая подстановка Лемма 14. Если программа Pr истинна на классе моделей G, то (C) = 1, C Pr.

Доказательство. Пусть C = A B1,..., Bk; C Pr, k > 0;

Рассмотрим правило C = A (B1,..., Bk), G, и условную вероятность (A / (B1,..., Bk)). Каждая подстановка G однозначно определяет некоторое состояние : X U. Так как программа Pr истинна на G, для любого состояния, то для любой подстановки G будем иметь G(A (B1,..., Bk)) = G. Так как мера согласована с классом моделей G, то из G(1) = G(2) следует (1) = (2) и, следовательно, (A (B1,..., Bk)) = 1, откуда (A / (B1,..., Bk)) = 1. Поэтому (C) = 1, если (C) определена § 38. Детерминированные закономерности.

Определим на множестве PR отношение – «быть более общим».

Обозначим множество всех подстановок не являющихся перестановками через t, (тождественная подстановка принадлежит t).

Определение 30. Отношение C B 1,..., B n’, n, n' 0 имеет место тогда и только тогда, когда существует подстановка t такая, что A = A’, {B1,..., Bn} {B’1,..., B’n’} и либо не тождественная подстановка, либо n < n'.

Лемма 15. Отношение – строгий частичный порядок на PR Обозначим через W(G) PR множество всех правил, истинных на G.

Следствие 8. Если C W(G) и C C’, то C’ W(G) Пусть W’(G), W’(G) W(G) – множество всех максимальных по отношению правил из W(G). Правила из W’(G) нельзя обобщить, сохраняя их истинность на G. Среди правил W’(G) могут быть такие, которые истинны на G только потому, что посылка правила всегда ложна.

Определение 31. Детерминированной закономерностью или Dправилом будем называть такое правило (A B1,..., Bn) W’(G), для которого утверждение x(B1&... &Bn) истинно хотя бы на одной модели из § 39. Вероятностные закономерности.

Определение 32. Отношением вероятностной выводимости назовем отношение C C’ (C C’)&((C) < (C’)).

Определение 33. Вероятностной закономерностью (P-правилом) будем называть правило C PR0, такое, что из C’ C, C’ PR0 следует C’ Если детерминированные закономерности нельзя обобщить, сохраняя их истинность на классе моделей G, то вероятностные закономерности нельзя обобщить, не уменьшая их условную вероятность. Обозначим множество всех P-правил через PR(M).

Лемма 16. Если существует C’, C’ C, (C’) (C), то C PR(M) Лемма 17. Если для правила C W(G)\W’(G), C PR0 существует правило C’ W(G), C’ C, C’ PR0, то C PR(M) Лемма 18. D-правило C, C PR0 является P-правилом, если из C’ C, C’ PR0 следует ({ | G, ¬C’}) > 0.

Доказательство. В силу леммы (C) = 1. Докажем, что из C’ C, C’ PR0 следует (C’) < (C) = 1. По условию ({ | G, ¬C’}) > 0.

Отсюда следует, что (B’&A’) < m(A’) и m(C’) < 1, C’ = B’ A’ § 40. Предсказание и индуктивный синтез логических программ Полный набор фактов для класса моделей G составляет совокупность множеств F(N) = {A | A – atom, N A для любого состояния атома A}, N G. Любую конечную совокупность D конечных подмножеств D(N) F(N), N G будем называть данными. Вероятностную Эрбранову модель M, согласованную с классом G, будем называть вероятностной моделью данных D.

Как следует использовать правила C = A B1,..., Bk, k 1 для предсказания? Если посылка правила (B1&... &Bk) истинна на некоторой случайно выбранной из G в соответствии с мерой модели N (при некоторой подстановке : {B1,..., Bk} F(N)), то заключение A истинно на N с вероятностью (A / (B1&... &Bk)) (A / B1&... &Bk) = (C). Вероятность (C), определенная в параграфе 5 для правил со свободными переменными, дает нам нижнюю границу вероятностей предсказания атома A. Заметим, что предсказание нужно делать по данным D(N) какой-то одной случайно выбранной из G модели N. Обозначим множество всех Pправил с посылкой, содержащей хотя бы один атом, через P(M) PR(M).

Определение 34. Для атома A сигнатуры и некоторых данных D(N) правило C = A’ B1,..., Bl; l 1, C PR0, не содержащее одинаковых переменных с атомом A, будем называть наилучшим для предсказания атома A правилом по данным D(N) в вероятностной модели M, если:

1) существует подстановка G такая, что {B1,..., Bl} D(N), 2) на правиле достигается максимум условной вероятности среди правил, удовлетворяющих условию 1 и сравнимых по условию {B1,..., Bl}(это подмножество должно включаться в подмножества других правил);

3) правило C максимально по отношению среди правил, удовлетворяющих условиям 1, 2.

Теорема 13. Все наилучшие для предсказания какого-либо атома A сигнатуры (по некоторым данным D(N), N G в вероятностной модели данных M) правила являются вероятностными закономерностями с непустой посылкой, т. е. принадлежат множеству P(M).

Доказательство: Пусть правило C = A’ B1,..., Bk; k 1; C PR0 является наилучшим для предсказания атома A по данным D(N), и для некоторой подстановки ’ G выполняются соотношения {B1’,..., Bk’} D(N), A’ = A’’, (C) > (A’’). Предположим противное, что C P(M) и C’ PR0, C’ = A” B’1,..., B’l и подстановка ”, A”” = A’, {B’1”,..., B’l”} {B1,..., Bk}, такие, что (C’) (C) > (A’’) (A’). Так как A”” = A’, то (A’) (A”) и, следовательно, (C’) > (A”). Отсюда следует, что посылка правила C’ не пуста и l > 1. Покажем, что правило C’ лучше правила C для предсказания атома A, что противоречит условию. Включение {B’1”’,..., B’l”’} {B1’,..., Bk’} D(N), равенство A’ = A””’ и неравенство (C’) (C) > (A’’) говорит о выполнении условия 1. Соотношения (C’) > (C), C’ C противоречат выполнению условий 2, 3 для правила C Определение 35. ПРОЛОГ-программой индуктивно синтезированной по данным D и вероятностной модели данных M будем называть множество правил PR(M, N) = P(M) D(N), где D(N) D, N – некоторая модель, случайно выбранная из G в соответствии с вероятностной моделью данных § 41. Вероятностный семантический вывод Определение 36. Семантическим вероятностным выводом (P-выводом) произвольного атома A сигнатуры будем называть максимальную последовательность правил C1 C2...; C1, C2,... P(M); Ci = Ai Bi1,..., Bili, i = 1, 2,... такую, что атом A унифицируем с атомами A1, A2,.... Если такой последовательности не существует, то P-вывод пуст.

2. Каждому P-выводу соответствует последовательность подстановок 1, 2,... определения 6.1 отношения. Подстановку = 12... будем называть результатом вероятностного вывода.

Последнее правило в конечном P-выводе будем называть результирующим.

Лемма 19. D-правило в P-выводе может быть только результирующим.

P-деревом семантического вероятностного вывода атома A будем называть совокупность всех P-выводов (возможно пустую) цели A.

Определение 37. P-предсказанием некоторого атома A сигнатуры программой PR(M, N) = P(M)D(N) будем называть такой P-вывод C C2... Ci...; C1, C2,..., Ci,... P(M) цели A, в котором:

1) существует правило Ci = Ai Bi1,..., Bili и подстановка, такие что {B 1,..., Bili} D(N); A = Ai; (Ai) < (Ci);

2) на правиле Ci достигается максимум условной вероятности (Ci) среди всех правил, удовлетворяющих условию 1, всех P-выводов цели A;

3) если P-дерево вывода цели A пусто или требуемой подстановки не существует, то P-предсказание не определено;

4) результатом P-предсказания будем называть подстановку p = 12...i-1, где 1, 2,..., i-1 – подстановки P-вывода C1 C2... Ci ;

5) оценкой P-предсказания будем называть величину p(A) = (Ci). Если P-предсказание не определено, то оценка p(A) не определена.

Теорема 14. P-предсказание атома A сигнатуры программой PR(M, N) = P(M) D(N) определено тогда и только тогда, когда существует наилучшее для предсказания атома A правило C по данным D(N) в вероятностной модели данных M. Если P-предсказание атома A программой PR(M, N) определено, то оно осуществляется P-выводом, содержащим наилучшее для предсказания атома A правило C. Оценкой P-предсказания является величина p = (C).

Доказательство: Пусть C – наилучшее для предсказания атома A правило C = A’ B1,..., Bl. Тогда, по теореме, C P(M) PR(M, N). В силу свойства 1 (определение 34) атом A унифицируем с атомом A’. Отсюда следует, что существует P-вывод, содержащий правило С. Из свойства (определение 34) следует свойство 1 (определение 37). Следовательно, P-предсказание атома A определено.

Если P-предсказание определено, то существует, по крайней мере, одно правило C = A’ B1,..., Bl, l 1, C PR0 (так как C PR(M, N)) и подстановка такие, что A = A’, {B1,..., Bl} D(N), (C) > (A’). Таким образом, необходимые условия наилучшего для предсказания правила выполнены и, следовательно, наилучшее для предсказания правило существует.

Докажем вторую часть теоремы. Из первой части доказательства следует, что существует P-вывод, содержащий наилучшее для предсказания атома A правило C. В силу свойства 2 (определение 34) на этом правиле достигается максимум условной вероятности среди правил, удовлетворяющих условию 1 (определение 34) Но как показано в первой части доказательства, условию 1 (определение 34) удовлетворяют все правила P-дерева вывода цели A, которые могут использоваться для предсказания (удовлетворяют условию 1 (определение 37)). Отсюда следует свойство (определение 37) P-предсказания § 42. Взаимосвязь вероятностного и логического выводов Пусть Pr – некоторая логическая программа, факты которой содержатся среди фактов D(N) программы PR(M, N) = P(M) D(N).

Теорема 15. Если атом A предсказывается программой Pr c оценкой (A) > (A), для любой подстановки G, то он P-предсказывается программой PR(M, N) с оценкой P-предсказания p(A) > (A).

Доказательство. По условию существует успешный SLDF-вывод A, N1,..., Nk, NkF^ цели A в пространстве вычислений программы Pr такой, что (A / NkF^) (A) > (A), (NkF^) > 0, Nk = B1,..., Bl;

Рассмотрим правило C = A B1,..., Bl. Из условия (A) > (A) 0, следует что l 1. Так как (NkF^) > 0, то C PR0. Кроме того, (C) (A) > (A) и, следовательно, выполнено условие 1 (определение 34) наилучшего для предсказания атома A правила. Отсюда следует, что существует наилучшее для предсказания атома A правило CB и по теореме Pпредсказание атома A определено и p(A) = (CB). Так как правило, C удовлетворяет условию 1 (определение 34), то p(A) = (CB) (C) по условию 2 этого же определения Рассмотрим P-предсказание C1... Ci... цели A программой PR(M, N) = P(M) D(N) по наилучшему для предсказания атома A правилу Ci = Ai Bi1,..., Bili и подстановке, {Bi1,..., Bili} D(N), A = Ai, (Ai) < (Ci). Этому P-предсказанию поставим в соответствие нормализованный SLDF-вывод, который будем обозначать как SLDP(A)-вывод, A; Bi1,..., Bili;... ; Bi1,..., Bili цели A по правилам Ci, Bi1,..., Bili. По теореме 4.2 найдем оценку полученного SLDP(A)-вывода: (A / NkF^) = 1 - (1 - p)(Bi1&... &Bili) / (NkF^) = 1 - (1 - p) = p, где p = (Ci).

Таким образом, (A) = (Ci) = p(A). SLDP(A)-вывод цели A состоит в использовании наилучшего для предсказания атома A правила Ci и фактов D(N) программы.

Теорема 16. Если атом A предсказывается программой PR(M, N) с оценкой (A) > (A), G и P-предсказывается этой же программой с оценкой p(A), то (A) = p(A).

Доказательство. Выше, при введении понятия SLDP(A)-вывода, было доказано, если P-предсказание атома A определено, то существует SLDP(A)-вывод атома A такой, что (A) p(A). Обратное неравенство p(A) (A) следует из теоремы, если в качестве программы Pr взять программу PR(M, N) Теорема 17. Если атом A предсказывается некоторой программой Pr с оценкой (A) > (A), G, то он предсказывается программой PR(M, N) с оценкой '(A), '(A) (A).

Доказательство. В силу теоремы, атом A P-предсказывается программой PR(M, N) с оценкой p(A) (A). Из предыдущих рассуждений следует, что в этом случае существует SLDP(A)-вывод атома A программой PR(M, N) с оценкой = p(A) (A) > (A), G. Отсюда следует, что предсказание атома A программой PR(M, N) определено и для оценки предсказания '(A) имеет место соотношение '(A) = p(A) Процесс организации вычислений запросов A1,..., Ak, k 2 можно охватить, обобщив понятие вероятностной закономерности на утверждения A1&... &Ak B1,..., Bl.

ГЛАВА 4. РЕЛЯЦИОННЫЙ ПОДХОД

К ИЗВЛЕЧЕНИЮ ЗНАНИЙ ИЗ ДАННЫХ

§ 43. Логический анализ методов извлечения знаний В данном параграфе проводится логический анализ методов Machine Learning и KDD&DM. Показывается, что если методы не основаны на теории измерений, то для них возникает проблема адекватности – доказательство инвариантности метода относительно допустимых преобразований шкал. В противном случае метод может давать различные результаты в зависимости от того в каких единицах измерения представлены данные.

Вводится определение инвариантности метода относительно выбора числовых представлений для данных. Выделяется логическая составляющая данных. Показывается, как для любого метода Machine Learning и KDD&DM можно получить его логический аналог, для которого не возникает проблема инвариантности.

В результате проведенного анализа показывается, как для каждого Machine Learning и KDD&DM можно выделить:

- тип данных с которыми работает KDD&DM-метод в виде многосортной эмпирической системы;

- онтологию метода в виде множества отношений и операций, в которых записаны данные и представлены гипотезы метода;

- тип знаний метода как класс правил, которые проверяет метод.

Дадим определение инвариантности метода. Для этого представим числовые методы, как это показано на рис 8 :

- W = {w} – обучающая выборка;

- X(w) = (x1, …, xn) – набор значений из n признаков для каждого объекта обучения;

- Y(w) – целевое значение признака для каждого объекта обучения KDD&DM метод M в результате обучения на обучающей выборке {X(w)}, wW, порождает решающее правило которое предсказывает целевые значения признака Y(w). Например, рассмотрим объект w с неизвестным значением Y(w), но известными значениями признаков X(w), тогда где J(X(w)) является значением сгенерированным правилом J, и ~ приблизительное равенство. Решающее правило J может быть алгебраическим или логическим выражением, решающим деревом, нейронной сетью или гибридным алгоритмом.

Для признаков (x1, …, xn, Y) существуют эмпирические системы A1, …, An, B, имеющие соответствующие группы преобразований g1, …, gn, g. Группа преобразований для всех признаков определяется как Инвариантность KDD&DM-метода M относительно группы преобразований G определяется так, что для любого преобразования gG решающее правило обнаруживаемое методом М должно быть одним и тем же в том смысле, что принимаемые на объектах wW решения совпадают, т.е. решающие правила J = M({X(w), Y(w)}) и Jg = M({gX(w), gY(w)}), полученные методом М по преобразованной {gX(w), gY(w)} и не преобразованной {X(w), Y(w)} выборке должны давать одни и те же решения для любых объектов wW Если метод не инвариантен, то получаемые методом решения зависят от выбора единиц измерения.

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

Генеральная совокупность Присвоение целевых значений {X(w)}={(x 1,x 2...., x n )} Представление обучающих объектов набором признаков:

Эмпирические системы A1, …, An, B признаков, по определению, интерпретируемы в системе понятий предметной области. Методы KDD&DM очевидно инвариантны, если они используют в своей работе только интерпретируемую информацию эмпирических систем A1, …, An, B и обнаруживают решающие правила J, являющиеся логическими выражениями в терминах эмпирических систем.

Покажем, как из любого метода KDD&DM можно извлечь инвариантный метод M : {X(w)} J. Проанализируем метод M с точки зрения ограничений KDD&DM-методов 1–3. Определим многосортную эмпирическую систему A(W) как произведение эмпирических систем A1, …, An, B.