ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА АВТОМАТИЧЕСКОГО ПОРОЖДЕНИЯ ГИПОТЕЗ (ДСМ-МЕТОД)

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

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

Одной из главных идей самого ДСМ-метода АПГ является формализация взаимодействия трех познавательных процедур – индукции, аналогии, абдукции [1].

ДСМ-метод в своей работе оперирует следующими сущностями:

• объекты;
• свойства объектов;
• структурные компоненты.

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

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

Перед началом работы ДСМ-метода полагаем, что уже есть некая база знаний. База знаний содержит [2]:

• O – множество объектов;
• P – множество свойств объектов (целевых признаков);
• C – множество элементов структуры (возможных причин свойств);
• V – множество значений свойств. В нашем случае это: {1, -1, 0, -};
• функцию P: O => 2^C, которая определяет наличие у объектов подмножества целевых признаков;
• функцию F: O*P => V, которая определяет начальное значение свойств объектов.

Значения функции F из области V можно описать следующим образом [2]:

• F(o, p) = 1 – объект o обладает свойством p;
• F(o, p) = -1 – объект o не обладает свойством p;
• F(o, p) = 0 – есть противоречивые аргументы относительно наличия свойства p у объекта o;
• F(o, p) = - – заранее не известно о наличии свойства p у объекта o.

Задача ДСМ-метода состоит в том, чтобы доопределить все значения функции F содержащей значение {-} до одного из значений {1, -1, 0}. Происходит это путем формирования гипотез:

• о связи подмножества структурных признаков со значением свойства. Это гипотезы о возможных причинах свойств;
• о значении свойства для объектов, изначально имевших значение
• {-} (путем применения гипотез о возможных причинах свойств).

Гипотезы о возможных причинах свойств обозначим функцией H: C*P => V. Значения этой функции можно описать следующим образом [2]:

H(c, p) = 1 – подмножество структурных признаков c является возможной причиной наличия свойства p;

• H(c, p) = -1 – подмножество структурных признаков c является возможной причиной отсутствия свойства p;
• H(c, p) = 0 – есть аргументы как за, так и против того, что подмножество структурных признаков c является причиной свойства p;
• H(c, p) = - – нет информации о связи подмножества структурных признаков c со свойством p.

Итак, ДСМ-метод заключается в последовательном применении познавательных процедур [1]:

• индукции – правила вывода первого рода, для получения гипотез о возможных причинах свойств (функция H);
• аналогии – правила вывода второго рода, для получения гипотез о наличии свойств у объектов (доопределение функции F);
• абдукции – для проверки каузальной полноты.

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

Абдукция применяется только после того, как завершено применение правил первого и второго рода.

Правило первого рода – это некоторая функция, использующая базу знаний для получения функции H. Определим правило первого рода как H = PIR1(F). Далее опишем алгоритм работы правил первого рода.

Можно поделить все объекты o в базе, на:

• положительные примеры, для свойства p, относительно матрицы F, если F(o, p) = 1;
• отрицательные примеры, для свойства p, относительно матрицы F, если F(o, p) = -1;
• противоречивые примеры, для свойства p, относительно матрицы F, если F(o, p) = 0.

Объекты, для которых справедливо: F(o, p) = - не рассматриваются, так как они не участвуют в формировании функции H.

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

• M+(F, c, p) – набор структурных признаков c вкладывается хотя бы в один объект, являющийся положительным примером относительно F для свойства p;
• M-(F, c, p) – набор структурных признаков c вкладывается хотя бы в один объект, являющийся отрицательным примером относительно F для свойства p;
• M0(F, c, p) – набор структурных признаков c вкладывается хотя бы в один объект, являющийся противоречивым примером относительно F для свойства p.

Теперь, можно определить функцию H(c, p) следующими значениями [2]:

• 1, если M+(F, c, p) ∧ ¬M-(F, c, p) ∧ ¬M0(F, c, p)
• -1, если M-(F, c, p) ∧ ¬M+(F, c, p) ∧ ¬M0(F, c, p)
• 0, если (M+(F, c, p) ∧ M-(F, c, p)) ∨ M0(F, c, p)
• -, если ¬M+(F, c, p) ∧ ¬M-(F, c, p) ∧ ¬M0(F, c, p)

На этом действие индукции завершено, гипотезы сформированы.

Правила вывода второго рода преобразуют функцию F, доопределяя некоторые её значения. Обозначим новую функцию F1, как доопределенную в результате применения аналогии функцию F. Тогда функция F1(o, p) будет принимать значения исходной функции F, если F(o, p) = {1, -1, 0}. Остальные значения определяются применением правил второго рода, используя матрицу H: F1 = PIR2(F, H).

Аналогично правилам первого рода введем новые обозначения:

K+(H, o, p) – в объект o вкладывается хотя бы одна гипотеза из H о наличии свойства p,

K-(H, o, p) – в объект o вкладывается хотя бы одна гипотеза из H об отсутствии свойства p,

K0(H, o, p) – в объект o вкладывается хотя бы одна противоречивая гипотеза из H.

Тогда, доопределим функцию F1 следующими значениями:

• 1, если K+(H, o,p) ∧ ¬K-(H, o,p) ∧ ¬K0(H, o,p)
• -1, если K-(H, o,p) ∧ ¬K+(H, o,p) ∧ ¬K0(H, o,p)
• 0, если (K+(H, o,p) ∧ K-(H, o,p)) ∨ K0(H, o,p)
• -, если ¬K+(H, o,p) ∧ ¬K-(H, o,p) ∧ ¬K0(H, o,p)

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

Для этого, для всех объектов в функции F(o, p) значения для которых были известны изначально, необходимо проверить что имеется хотя бы одна гипотеза из H(c, p), которая объясняла бы это значение [2]. Если объяснения начальных значений найдены, то проверка каузальной полноты считается пройденной, и результаты ДСМ-метода можно применять. В противном случае рекомендуется расширить базу фактов, пересмотреть набор структурных признаков, или способ кодирования структурных признаков.

Результат

Здесь рассмотрим веб-приложение со стороны веб-интерфейса.

На всех рисунках будет показана работа с известным примером ДСМ-метода: можно ли описать окружность вокруг прямоугольника. (Рис. 1).

Рисунок 1. Страница настроек свойств задачи

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

Рисунок 2. Таблица редактирования структурных свойств

Рисунок 3. Страница редактирования объектов задачи

Далее обратим внимание на страницу редактирования объектов. Тут в таблице первый столбец – это название объекта, со второго до предпоследнего – по очереди сначала все свойства, потом все структурные признаки, последний столбец занимает кнопка для удаления элемента. Значения структурных свойств могут быть true, или false (во время редактирования появляется галочка). Значения свойств в соответствии с ДСМ-методом: 1, -1, 0, либо не иметь значения. Отсутствие значения означает что его необходимо найти. (Рис. 3).

Теперь, когда данные добавлены в систему, можно переходить к вычислениям. На странице результатов вычислений есть таблица с конечным состоянием объектов, обратите внимание, что свойство у прямоугольника определено как значение один, что совпадает с рассматриваемым примером (Рис. 4).

Рисунок 4. Таблица с конечным состоянием объектов

Как и в рассмотренном примере эта задача решается за один шаг ДСМ-метода. Сгенерированные гипотезы совпадают, и причина свойства прямоугольника тоже: можно описать окружность, так как есть ось симметрии, не являющаяся диагональю. Таким образом было продемонстрировано поведение системы со стороны пользователя, сгенерированы гипотезы на основе базы фактов, и найдены значения свойств для всех объектов.