ДСМ-метод

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

ДСМ-метод – это метод автоматического порождения гипотез. Формализует схему правдоподобного и достоверного вывода, называемую ДСМ-рассуждением.

ДСМ-рассуждение является синтезом познавательных процедур: индукции, аналогии и абдукции. ДСМ-метод был создан как средство автоматизированного построения формализации знаний о предметной области средствами так называемых квазиаксиоматических теорий (КАТ).

История

ДСМ-метод автоматического порождения гипотез был предложен В. К. Финном в конце семидесятых годов. Название метода составляют инициалы известного английского философа, логика и экономиста Джона Стюарта Милля, чьи “методы здравомыслящего естествоиспытателя” частично формализованы в ДСМ-методе.

Исторически, первым примером задач, для решения которых применялись ДСМ-системы, является выявление причинно-следственных закономерностей вида структура-активность в фармакологии. В 1997-1998 годах был проведен ряд компьютерных экспериментов, целью которых являлась оценка возможности создания интеллектуальной системы, которая позволяла бы определить степень риска возникновения у больного рецидива аденомы гипофиза после её удаления. На основе количественного ДСМ-метода была разработана экспериментальная система прогнозирования рецидива аденомы гипофиза, которая носит рабочее название HTRD (Hypophisis tumor relapse diagnostics). Кроме этого, ДСМ-системы успешно применялись в задачах технической диагностики и в исследовании детерминант социологического поведения.

В настоящее время разработками ДСМ-систем занимаются в ВИНИТИ РАН и на кафедре математики, логики и интеллектуальных систем РГГУ под руководством В. К. Финна.

Описание метода

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

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

Пример:

Объект – лист растения.

Свойство объекта – зелёный цвет.

Причина свойства – хлорофилл.

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

• объекты, про которые известно, что они обладают данным признаком,

• объекты, про которые известно, что они не обладают данным признаком,

• объекты, для которых существуют аргументы как за, так и против того, что они обладают данным признаком,

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

Результатом применения ДСМ-метода являются гипотезы двух типов:

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

Шаг ДСМ-метода

Рассмотрим один шаг ДСМ-метода в его самом простом варианте.

• O — множество объектов,
• P — множество свойств объектов (целевых признаков),
• C — множество возможных причин свойств объектов (элементы структуры объектов),
• V — множество оценок. V = {+1, –1, 0, $\tau$}.

Имеется функция P: O→$2^C$, которая сопоставляет каждому объекту о подмножество фрагментов (элементов структуры), встречающихся в объекте о.

Введём функцию F: O×P→V, представляющую начальную ситуацию.

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

Функция F может быть представлена в виде матрицы:

$\begin{bmatrix} f_{11} & \cdots & f_{1j} \\ \vdots & \ddots & \vdots \\ f_{i1} & \cdots & f_{ij}\end{bmatrix}$

Если f_ij = $\tau$, то говорят, что для пары (o_i, p_j) функция F(o_i, p_j) недоопределена. Задача ДСМ-метода состоит в том, чтобы с помощью формирования гипотез доопределить исходную матрицу.

Правила первого рода

Сформируем гипотезы о возможных причинах свойств. В результате получим функцию H: C×P→V.

• H(c, p) = +1 — c является возможной причиной наличия свойства p или (+)-гипотезой;

• H(c, p) = –1 — c является возможной причиной отсутствия свойства p или (-)-гипотезой;

• H(c, p) = 0 — есть аргументы как за то, что c является причиной наличия свойства p, так и за то, что c есть причина отсутствия этого свойства или (+)-гипотезой (противоречивой гипотезой);

• H(c, p) = $\tau$ — неизвестно, является ли c причиной наличия p или причиной отсутствия этого свойства.

Значения функции H для каждой пары (c, p) находятся с помощью правил правдоподобного вывода. Эти правила называются правилами первого рода. Сокращенное обозначение — PIR₁ (от Plausible Inference Rules). Правила первого рода можно рассматривать как функцию, использующую матрицу F для получения матрицы H, т.е.
H = PIR₁(F).

Пусть p — некоторое свойство.
Объект o является:

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

Через F ⁺[p], F ^-[p], F ⁰[p] будем обозначать множество всех положительных, отрицательных и противоречивых примеров для p относительно F, соответственно.

В качестве возможных причин наличия/отсутствия свойств объектов рассматриваются подмножества набора фрагментов С^[1]. Множество С' ⊆ C удовлетворяет (+)-условию для p относительно F, если существует Ω ⊆ F⁺[p] такое, что:

1. $C'=\bigcap_{o\in\Omega} P(o)$, т.е. каждый объект из Ω содержит все фрагменты из множества C', и не существует дополнительных фрагментов, принадлежащих $P(o)$ для всех $o\in\Omega$;
2. Ω содержит по крайней мере два элемента.

(–)- и (0)-условия - аналогично.

Через M⁺(F, c, p) будем обозначать тот факт, что c удовлетворяет (+)-условию для p относительно F .
Через M^-(F, c, p) - тот факт, что c удовлетворяет (-)-условию для p относительно F .
Через M⁰(F, c, p) - тот факт, что c удовлетворяет (0)-условию для p относительно F .

Теперь определим функцию H^[2]. Положим:

$H(c, p) = \begin{cases}+1, & \text{если}M^+(F, c, p)\And \lnot M^-(F, c, p)\And \lnot M^0 (F, c, p),\\-1, & \text{если}M^-(F, c, p) \And \lnot M^+(F, c, p)\And \lnot M^0(F, c, p), \\ \quad 0, & \text{если}(M^+(F, c, p) \And M^-(F, c, p)) \lor M^0(F, c, p), \\ \quad \tau,& \text{если}\lnot M^+(F, c, p)\And \lnot M^-(F, c, p) \And \lnot M^0(F, c, p).\end{cases}$

Иначе говоря, множество фрагментов C_i⊆C, доопределяется как

• возможная причина наличия свойства p, если оно вкладывается в два и более (+)-примера, не более чем в один (-)-пример) и неболее чем в один (0)-пример;
• возможная причина отсутствия свойства p, если оно вкладывается в два и более (-)-примера, не более чем в один (+)-пример и не более чем в один (0)-пример.

Правила второго рода

Используя матрицу гипотез о возможных причинах, можно сформировать гипотезы о наличии или отсутствии свойства p у тех объектов из O, для которых изначально не было известно, обладают они этим свойством или нет, т.е. для тех o$\in$O, для которых F(o, p) = $\tau$.

В результате мы получим функцию F’: O×P→V. F’(o, p) = F(o, p), если F(o, p) ≠ $\tau$. Если же F(o, p) = $\tau$, то F’(o, p) может принимать любое значение из V:

• F’(o, p) = +1 - o возможно обладает свойством p,
• F’(o, p) = -1 - o возможно не обладает свойством p,
• F’(o, p) = 0 - есть аргументы как за, так и против того, что объект o обладает свойством p,
• F’(o, p) = $\tau$ - доопределить ячейку исходной матрицы F не удалось.

Значения функции F' находятся с помощью правил правдоподобного вывода. Эти правила называются правилами второго рода. Сокращенное обозначение — PIR₂. Правила второго рода можно рассматривать как функцию, использующую матрицы F и Н для получения матрицы F', т.е. F' = PIR₂(F, H).

Пусть o — объект, p — свойство. Будем говорить, что объект o удовлетворяет

• (+)-условию для p относительно H (т.е. возможно обладает свойством p), если существует такое c$\in$C, что c⊆o и H(c, p) = +1.
• (-)-условию для p относительно H (т.е. возможно не обладает свойством p), если существует такое c$\in$C, что c⊆o и H(c, p) = -1.
• (0)-условию для p относительно H (т.е. есть аргументы как за, так и против того, что о обладает свойством p), если существует такое c$\in$C, что c⊆o и H(c, p) = 0.

Через $\Pi$⁺(H, o, p), $\Pi$^-(H, o, p), $\Pi$⁰(H, o, p) будем обозначать тот факт, что объект o для свойства p относительно H удовлетворяет (+)-условию, (–)-условию и 0-условию, соответственно. Положим: F'(o, p) = F(o, p), если F(o, p) ≠ $\tau$; в противном случае

$F'(o, p) = \begin{cases}+1, & \text{если}\Pi^+(H, o, p)\And \lnot \Pi^-(H, o, p)\And \lnot \Pi^0 (H, o, p),\\-1, & \text{если}\Pi^-(H, o, p) \And \lnot \Pi^+(H, o, p)\And \lnot \Pi^0((H, o, p), \\ \quad 0, & \text{если}(\Pi^+(H, o, p) \And \Pi^-(H, o, p)) \lor \Pi^0(H, o, p), \\ \quad \tau,& \text{если}\lnot \Pi^+(H, o, p)\And \lnot \Pi^-(H, o, p) \And \lnot \Pi^0(H, o, p).\end{cases}$

---

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

Проверка условия каузальной полноты

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

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

Пример

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

Рассмотрим следующий набор объектов предметной области:

• o₁ - квадрат,
• o₂ - прямоугольник,
• o₃ - ромб,
• o₄ - параллелограмм,
• o₅ - равнобокая трапеция,
• o₆ - дельтоид,
• o₇ - прямоугольный дельтоид.

Для этих объектов выберем следующий набор структурных фрагментов C:

• c₁ - есть центр симметрии,
• c₂ - есть ось симметрии,
• c₃ - есть ось симметрии, которая является диагональю,
• c₄ -есть ось симметрии, не являющаяся диагональю,
• c₅ - ровно один поворот на 180⁰ переводит фигуру в себя,
• c₆ -порядок группы симметрий равен двум,
• c₇ -есть пара противолежащих прямых углов,
• c₈ - нет прямого угла,
• c₉ - нет оси симметрии или любая ось симметрии является диагональю.

множество целевых признаков в данном случае состоит всего из одного признака:

• p - можно описать окружность.

Представим исходные данные в виде таблицы:

	p	c1	c2	c3	c4	c5	c6	c7	c8	c9
o1 (квадрат)	+	+	+	+	+	-	-	+	-	-
o2 (прямоугольник)	$\tau$	+	+	-	+	+	-	+	-	-
o3 (ромб)	-	+	+	+	-	+	-	-	+	+
o4 (параллелограмм)	-	+	-	-	-	+	+	-	+	+
o5 (равнобокая трапеция)	+	-	+	-	+	-	+	-	+	-
o6 (дельтоид)	-	-	+	+	-	-	+	-	+	+
o7 (прямоугольный дельтоид)	+	-	+	+	-	-	+	+	-	+

Представим каждый из объектов набором структурных компонентов, которыми этот объект обладает:

• о₁ (квадрат) {с₁, с₂, с₃, с₄, с₇};
• o₂ (прямоугольник) {с₁, с₂, с₄, с₅, с₇};
• o₃ (ромб) {с₁, с₂, с₃, с₅, с₈, с₉};
• o₄ (параллелограмм) {с₁, с₅, с₆, с₈, с₉};
• o₅ (равнобокая трапеция) {с₂, с₄, с₆, с₈};
• о₆ (дельтоид) {с₂, с₃, с₆, с₈, с₉};
• о₇ (прямоугольный дельтоид) {с₂, с₃, с₆, с₇, с₉}.

В нашем случае положительными примерами для целевого свойства p являются объекты о₁, о₅ и о₇, отрицательными - о₃, о₄ и о₆. Также имеется один ($\tau$)-пример - o₂.

Наша задача состоит в том, чтобы, используя правдоподобные рассуждения, выяснить, обладают ($\tau$)-примеры целевым свойством p или нет.

Применение правил первого рода

Здесь в качестве возможных причин наличия/отсутствия свойства p у объектов будем рассматривать некоторые непустые подмножества множества структурных фрагментов C. (+)-условию удовлетворяют множества:

• C₁ = {с₂, с₄}: Ω = {o₁, o₅};
• C₂ = {с₂, с₃, с₇}: Ω = {o₁, o₇};
• C₃ = {с₂}: Ω = {o₁, o₅, o₇};
• C₄ = {с₂, с₆}: Ω = {o₅, o₇}.

(-)-условию удовлетворяют множества:

• C₅ = {с₁, с₅, с₈, с₉}: Ω = {o₃, o₄};
• C₆ = {с₂, с₃, с₈, с₉}: Ω = {o₃, o₆};
• C₇ = {с₈, с₉}: Ω = {o₃, o₄, o₆};
• C₈ = {с₆, с₈, с₉}: Ω = {o₄, o₆};

Теперь необходимо выяснить, являются ли найденные множества возможными причинами наличия или отсутствия целевого свойства p у объектов, то есть определить функцию H для данного шага. Как говорилось ранее, правила определения данной функции могут иметь различный вид в зависимости от выбранной стратегии - с запретом (или без запрета) на контр-примеры.

Множество C_i$\subseteq$C будем доопределять как

• возможную причину наличия свойства p, если C_i удовлетворяет (+)-условию для p, то есть вкладывается как подмножество в два и более (+)-примера и при этом не вкладывается ни в один (вкладывается не более чем в один) (-)-пример;
• возможную причину отсутствия свойства p, C_i удовлетворяет (-)-условию для p, то есть вкладывается как подмножество в два и более (-)-примера и при этом не вкладывается ни в один (вкладывается не более чем в один) (+)-пример;
• противоречивую гипотезу, если существуют как (+)-пример, так и (-)-пример, в который вкладывается C_i.

Анализируя наши данные, мы получаем две возможные причины наличия свойства p:

• C₁ = {с₂, с₄} и
• C₂ = {с₂, с₃, с₇}.

Множество фрагментов C₄ = {с₂, с₆} становится (+)-гипотезой или противоречивой гипотезой в зависимости от стратегии.

Все множества, удовлетворяющие (-)-условию для p, доопределяются как возможные причины отсутствия свойства p.

То есть,

• H (C₁, p) = +1,
• H (C₂, p) = +1,
• H (C₅, p) = -1,
• H (C₆, p) = -1,
• H (C₇, p) = -1,
• H (C₈, p) = -1,
• H (C₄, p) = +1' или H (C₄, p) = 0 в зависимости от выбранной стратегии.

Применение правил второго рода

Используем полученные на предыдущем шаге (+)- и (-)-гипотезы для определения $\tau$-примеров. В нашем случае такой пример всего один: o₂ {с₁, с₂, с₄, с₅, с₇}.

В него вкладывается одна возможная причина наличия свойства p (C₁ = {с₂, с₄}) и не вкладывается ни одной возможной причины отсутствия свойства p, поэтому в стратегии с запретом на контр-примеры мы доопределяем o₁ как (+)-пример^[3].

К полученному на n-м шаге набору примеров опять применяются правила первого, а затем второго рода. Этот процесс продолжается до тех пор, пока не будут доопределены все $\tau$-примеры.

Проверка каузальной полноты

Проверка каузальной полноты осуществляется, как говорилось ранее, при помощи абдуктивных рассуждений. Условие каузальной полноты выполняется, если в каждый исходный (+)-пример вкладывается хотя бы одна возможная причина наличия целевого свойства p, а в каждый (-)-пример - хотя бы одна возможная причина его отсутствия.

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

Итог

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

1. имеется ось симметрии, которая не является диагональю,
2. имеется ось симметрии диагональ, и при этом имеется пара противолежащих прямых углов.

Примечания

1. ↑ В этом случае, для того, чтобы определить множества, удовлетворяющие (+)-, (-) и (0)-условиям, требуется найти всевозможные непустые пересечения фрагментов для набора (+)-, (-)- и (0)-примеров. Поиск всех пересечений (сходств) заданного наборя является отдельной комбинаторной задачей, для решения которой известен ряд алгоритмов, наиболее эффективным из которых является алгоритм Норриса.
2. ↑ Функция H может быть определена по другому в зависимости от стратегии (с запретом или без запрета на контр-примеры).
3. ↑ В более осторожной стратегии без запрета на контр-примеры мы отмечаем, что помимо этого, в него вкладывается одна противоречивая гипотеза, и поэтому доопределяем o₁ как (0)-пример.

Литература

1. Автоматическое порождение гипотез в интеллектуальных системах. Сост. Е.С.Панкратова, В.К.Финн. - М.: ЛИБРОКОМ, 2009. - 528 с.
2. ДСМ-метод автоматического порождения гипотез: логические и эпистемологические основания. Сост. О.М.Аншаков, Е.Ф.Фабрикантова. - М.: ЛИБРОКОМ, 2009. - 432 с.
3. Финн В. К. О возможности формализации правдоподобных рассуждений средствами многозначных логик // Всесоюзн. симп. по логике и методологии науки. – Киев: Наукова думка, 1976. – С. 82-83.
4. Финн В. К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф. Бэкона – Д. С. Милля // Семиотика и информатика. – 1983. – Вып. 20. – С. 35-101.
5. Anshakov O.M., Finn V.K., Skvortsov D.P. On axiomatization of many-valued logics associated with formalization of plausible reasoning // Studia Logica. 1989. Vol. 48. N 4. P. 423—447.
6. Аншаков О.М., Скворцов Д.П., Финн В.К. О дедуктивной имитации некоторых вариантов ДСМ-метода автоматического порождения гипотез // Семиотика и ин-форматика.— 1993.— Вып. 33.— С. 164–233.
7. Финн В. К. Об особенностях ДСМ-метода как средства интеллекту-ального анализа данных // НТИ. Сер. 2. – 2001. – №5. – С. 1-4.
8. Виноградов Д. В. Несимметричный ДСМ-метод с учетом контекста // Пятая национальная конференция с международным участием .Искусственный интеллект-96. – Казань: 1996. – КИИ-96: Сб. науч. тр.: В 3 т. – Казань : Ассоц. искусств. интеллекта, 1996.
9. Аншаков О.М., Скворцов Д.П., Финн В.К. О логической конструкции ДСМ-метода автоматического порождения гипотез // Докл. АН СССР, Том 320, № 6.— 1991.— С. 1331–1334.
10. Кузнецов С.О. Предикаты ДСМ-метода на языке соответствий Галуа // Научно-техническая информация (НТИ), Сер. 2, 2006, № 12, С. 12-16.
11. Кузнецов С.О. ДСМ-метод как система автоматического обучения // Итоги науки и техники, Сер. Информатика, 1991, Т. 15, С.17-54.

См. также

• Интеллектуальная информационная система
• Экспертная система
• Автоматизированная информационная система
• Гибридная интеллектуальная система
• Интеллектуальные системы в гуманитарной сфере (институт лингвистики РГГУ) - кафедра, занимающаяся разработкой ДСМ-метода

Ссылки

Добрынин Д.А. Динамический ДСМ-метод в задаче управления интеллектуальным роботом
Добрынин Д.А. Применение ДСМ-метода в задачах адаптивного поведения роботов
Михеенкова М.А., Финн В.К. Интеллектуальные системы для анализа социологических данных: задачи, логика, архитектура
Кожунова О.С. Применение правдоподобных рассуждений ДСМ-метода для пополнения семантического словаря
Труды XI Национальной конференции по искусственному интеллекту с международным участием
Открытый ДСМ-решатель на C++