Файл: Методыискусственногоинтеллекта.pdf

2.2. Индуктивные рассуждения
91
фактическую противоречивость, т. е. гипотеза имеет как аргументы
«за», так и аргументы «против». Если f(p, o) = τ, то это значит, что гипотеза не имеет ни одного аргумента «за» и ни одного аргумента
«против», т. е. оценка ее значения — «неопределенность».
Таким образом, функция F задана следующей матрицей:
F =
p
1
p
2
... p n
o
1
F
11
F
12
... F
1n o
2
· · ·
o m
F
m1
F
m2
... F
mn
,
где F
ij
∈ V .
Эту матрицу можно считать базой экспериментальных фактов.
Задача состоит в том, чтобы преобразовать матрицу F в матрицу
F
′
, такую что F
′
ij
= F
ij
, если F
ij
6= τ ; в противном случае следует доопределить матрицу F , заполнив ее клетки значениями, отличными от τ.
Эта задача решается следующим образом:
А) вначале следует найти связи фрагментов объектов со свойствами последних. Эти связи будут представлены в матрице H : C × P →
→ V ,
H =
p
1
p
2
... p n
c
1
H
11
H
12
... H
1n c
2
· · ·
c m
H
m1
H
m2
... H
mn
,
где H
ij
∈ V ;
Б) используем матрицу H для формулирования гипотезы о наличии или отсутствии тех или иных свойств у объектов, для которых
F (o, p) = τ , p ∈ P , o ∈ O. Иначе говоря, если p ∈ P — некоторое свойство, матрицу H мы будем использовать для доопределения функции F и построения таким образом функции F
′
.F
′
: o × p →
→ V .
Теперь опишем шаги А и Б более подробно.
Для этого введем правила 1-го и 2-го рода.
Правила 1-го рода служат для порождения гипотез о причинах свойств объектов.
Пусть o ∈ O, c ∈ C и c является фрагментом o, т. е. c ⊆ o.

92
Гл. 2. Методы автоматизации рассуждений
Обозначим через F
+
[p] множество положительных примеров.
Определение 2.2.2. Пусть p — некоторое свойство o, o ∈ O. Будем называть o отрицательным примером для p относительно F , если
F (o, p) = −1.
Обозначим через F
−
[p] множество отрицательных примеров.
Определение 2.2.3. Пусть p — некоторое свойство o, o ∈ O. Будем называть o неявным примером для p относительно F , если F (o, p)=0.
Обозначим через F
0
[p] множество неявных примеров.
Определение 2.2.4. Пусть p — некоторое свойство, c — неко- торый фрагмент o, т. е. c ⊆ o. Будем говорить, что c удовлетворяет
(+)-условию для p относительно F , если ∃Ω ⊆ F
+
[p], так что
1) c = (
T
Ω
o) 6= ∅;
2) Ω содержит больше одного элемента, т. е. |Ω| > 1.
Обозначение: M
+
(c, p, F ) — c обладает (+)-условием для p относи- тельно F .
Аналогичным образом вводятся определения для (−)-условия и
(0)-условия:
Определение 2.2.5. Пусть p — некоторое свойство, c — некото- рый фрагмент o, т. е. c ⊆ o. Будем говорить, что c удовлетворяет
(−)-условию для p относительно F , если ∃Ω ⊆ F
−
[p], так что
3) c =
T
Ω
o

6= ∅,
Ω содержит больше одного элемента, т. е. |Ω| > 1.
Выражение: M
−
(c, p, F ), означает, что c обладает (−)-условием для p относительно F .
Определение 2.2.6. Пусть p — некоторое свойство, c — некото- рый фрагмент o, т. е. c ⊆ o. Будем говорить, что c удовлетворяет
(0)-условию для p относительно F , если ∃Ω ⊆ F
0
[p], так что
4) c =
T
Ω
o

6= ∅,
Ω содержит больше одного элемента, т. е. |Ω| > 1.
Обозначение: M
0
(c, p, F ) − c обладает (0)-условием для p относи- тельно F .
Построим матрицу H(c, p) — матрицу гипотез — следующим обра- зом:
H(c, p) =









+1, если M
+
(c, p, F ) ∧ ¬M
−
(c, p, F ) ∧ ¬M
0
(c, p, F ),
−1, если _M
−
(c, p, F ) ∧ ¬M
+
(c, p, F ) ∧ ¬M
0
(c, p, F ),
0,
если (M
+
(c, p, F ) ∧ M
−
(c, p, F )) ∨ M
0
(c, p, F ),
τ ,
если ¬M
+
(c, p, F ) ∧ ¬M
−
(c, p, F ) ∧ ¬M
0
(c, p, F ).

2.3. Аргументационные рассуждения
93
По существу, это правило вывода, которое и называется правилом вывода 1-го рода. Это правило позволяет дать оценку степени правдо- подобия гипотезы о том, что c — причина свойства p.
Правила 2-го рода служат для порождения гипотез о наличии свойств у объектов или, иначе говоря, для доопределения матрицы F .
Пусть o — некоторый объект, p — некоторое свойство.
Будем говорить, что объект o удовлетворяет (+)-условию для p относительно H, если ∃c ∈ C : c ⊆ o и H(c, p) = +1, что обозначим через
Q
+
(H, o, p).
Будем говорить, что объект o удовлетворяет (−)-условию для p относительно H, если ∃c ∈ C : c ⊆ o и H(c, p) = −1, что обозначим через
Q
−
(H, o, p).
Будем говорить, что объект o удовлетворяет (0)-условию для p относительно H, если ∃c ∈ C : c ⊆ o и H(c, p) = 0, что обозначим через
Q
0
(H, o, p).
Матрица F
′
определяется следующим образом:
F
′
ij
= F
ij
, если и только если F
ij
# τ, а в противном случае:
F
′
(o, p) =









+1,
Q
+
(H, o, p) ∧ ¬
Q
−
(H, o, p) ∧ ¬
Q
0
(H, o, p),
−1,
Q
−
(H, o, p) ∧ ¬
Q
+
(H, o, p) ∧ ¬
Q
0
(H, o, p),
0,
(
Q
+
(H, o, p) ∧
Q
−
(H, o, p)) ∨
Q
0
(H, o, p),
τ , ¬
Q
+
(H, o, p) ∧ ¬
Q
−
(H, o, p) ∧ ¬
Q
0
(H, o, p).
Эта последняя матрица, собственно, и дает ответ на поставленный в на- чале вопрос. Затем процедура повторяется для следующего свойства и так до вычисления всех неопределенных в F значений. Однако для вычисления некоторых неопределенных значений в исходной матрице,
т. е. в базе фактов, может оказаться недостаточно информации. Тогда матрицу F следует пополнить новыми фактами. Может оказаться,
что при таком пополнении матрицы F значения F
ij
, подсчитанные на предыдущих итерациях, могут измениться. Тогда процесс пополнения и пересчета значений F
ij следует продолжить до стабилизации матри- цы F
′
(если таковая произойдет) или до окончания множества фактов.
2.3. Аргументационные рассуждения
Под аргументацией будем понимать такую процедуру принятия или опровержения некоторого высказывания А, при которой рассматривает- ся некоторое множество аргументов «за» или «против», используемых для приписывания А некоторой оценки (истинности) или для выводи- мости А из этого множества аргументов. Это означает, что аргумента- ция в рассматриваемом здесь смысле имеет два аспекта: семантический и синтаксический.

94
Гл. 2. Методы автоматизации рассуждений
Существует широкий спектр аргументационных систем, различа- ющихся уровнями абстракции и определениями основных понятий
[29, 32].
В основе любой аргументационной системы обычно лежат следую- щие компоненты:
а) логический язык;
б) определение аргумента;
в) определение конфликта между аргументами;
г) определение отвержения аргумента;
д) определение оценки аргумента.
В различных аргументационных теориях понятие аргумента опреде- ляется различным образом: либо аргумент — некоторое примитивное понятие, внутренняя структура которого не рассматривается, либо он является формулой некоторого логического языка. В любом случае для формирования аргументационной структуры необходимы компоненты в), г) и д).
Можно выделить два типа конфликтов:
1. Опровержение — симметричная форма конфликта;
2. Ослабление — несимметричная форма конфликта.
Для описания различных степеней конфликта вводятся бинарные отношения: «конфликтует и не слабее» или «конфликтует и сильнее»
[29]. В первом случае будем говорить, что «аргумент А оспаривает аргумент В», во втором — «аргумент А отвергает аргумент Б».
Пусть на множестве аргументов определено отношение оспарива- ния, тогда можно говорить, что аргументы либо подтверждаются, либо не подтверждаются.
Аргумент подтверждается, если все аргументы, оспаривающие его,
не подтверждаются. Аргумент не подтверждается, если он оспаривает- ся подтвержденным аргументом.
Аргумент А приемлем по отношению к множеству аргументов S
тогда и только тогда, когда каждый аргумент из U, оспаривающий А,
оспаривается аргументом из S. Аргументы из S могут рассматриваться как аргументы, способные к восстановлению статуса А, если А оспа- ривается.
Пусть Arg — множество аргументов, на котором задано бинарное отношение оспаривания. Определим оператор F :
F : 2
Arg
→ 2
Arg
Через F (S) обозначим такое множество аргументов a i
∈ Arg, что каж- дый из них приемлем по отношению к S. Тогда a i
приемлем по отно- шению к любому надмножеству S, иначе говоря, оператор F является

2.3. Аргументационные рассуждения
95
монотонным. Отсюда немедленно следует, что F имеет наименьшую неподвижную точку.
Именно с существованием наименьшей неподвижной точки опера- тора F связано свойство «подтверждаемости» аргумента. А именно,
легко видеть, что аргумент подтверждается тогда и только тогда, когда принадлежит наименьшей неподвижной точке F .
Опишем далее один из алгоритмов моделирования аргументацион- ных рассуждений ARG1, лежащий в основе известной системы MIRAGE
[33]. Алгоритм включает следующие фазы:
— выдвижение гипотез;
— подтверждение или отвержение гипотез;
— редукция множества гипотез.
Для более детального описания следует зафиксировать какой-либо из способов представления знаний, например, неоднородные семанти- ческие сети, описанные в первой главе. Тогда в вершинах сети будут находиться объекты, называемые здесь нами событиями, а ребра сети будут представлять элементы отношений, описанных в той же главе.
Множество событий включает два, вообще говоря, пересекающихся подмножества: аргументов и гипотез. Как к первым, так и ко вторым будут относиться факты и признаки; кроме того, подмножеством мно- жества гипотез являются решения. В качестве исходного множества ар- гументов будем рассматривать «наблюдаемые» факты и признаки, т. е.
некоторые достоверные данные, которые можно увидеть, измерить или получить каким-либо образом, например, в интерактивном режиме. На множестве всех событий определены отношения из п. 1.3.3 главы 1.
Для простоты рассмотрим только отношения R
1
, R
4
и R
5
из гл. 1:
R
1
: «Событие e
1
всегда сопровождается событием
e
2
»;
R
4
: «Событие e
1
иногда может увеличивать возможность появле-
ния
e
2
»;
R
5
: «Событие e
1
исключает событие
e
2
».
Если e
1
таково, что (e
1
, e
2
) ∈ R
1
или (e
1
, e
2
) ∈ R
4
и не существует e такого, что (e, e
1
) ∈ R
5
, будем говорить, что e
1
подтверждает e
2
Если e
1
таково, что (e
1
, e
2
) ∈ R
5
и не существует e 6= e
2
такого, что
(e, e
1
) ∈ R
5
, будем говорить, что e
1
отвергает e
2
Итак, пусть задано множество событий E. Введем одноместные атомарные формулы:
• O(e)
— событие e наблюдаемо;
• ¬O(e) — событие e не имеет места;
• M (e) — событие e возможно;
• H(e)
— событие e является гипотезой;
• ¬H(e) — событие e не является гипотезой;

96
Гл. 2. Методы автоматизации рассуждений
• S(e)
— событие e является решением (подтвержденной гипоте- зой);
• ¬S(e) — событие e не является решением (подтвержденной гипоте- зой).
Введем следующие правила вывода:
П1. (O(e
1
), (e
1
, e
2
) ∈ R
1
) → S(e
2
).
П2. (O(e
1
), (e
1
, e
2
) ∈ R
4
) → H(e
2
).
П3. (H(e
2
), O(e
1
), (e
1
, e
2
) ∈ R
5
) → ¬H(e
2
).
П4. (H(e
1
), (e
1
, e
2
) ∈ R
4
) → M (e
2
).
П5. (H(e
1
), ¬O(e
2
), (e
1
, e
2
) ∈ R
1
) → ¬H(e
1
).
Аксиомы:
Нелогическая аксиома
Т1. S(e) → O(e).
Логические аксиомы (A, B, C — пропозициональные переменные)
Т2. A → (B → A).
Т3. (A → (B → C)) → ((A → B) → (A → C)).
Т4. (¬A → ¬B) → (B → A).
Будем также использовать логические правила вывода, описанные в п. 1.1.2.
В дальнейшем из соображений удобства мы будем прибегать, поми- мо логической, и к теоретико-множественной нотации.
Так, например, будем использовать то обстоятельство, что O =
= {e|O(e)}. Точно так же H = {e|H(e)}, M = {e|M (e)} и S = {e|S(e)}.
Далее, предположим, что имеется некоторая процедура Q, поз- воляющая из M (e) заключать O(e) или ¬O(e). Такой процедурой,
может быть, например, процедура чтения информации из базы данных,
с датчиков или некоторая интерактивная процедура.
Перейдем непосредственно к описанию ARG1.
Шаг 1. Порождение множества гипотез.
Для всех e
1
, таких что для них имеет место O(e
1
) и (e
1
, e
2
) ∈ R
1
,
применить правило П1: (O(e
1
) и (e
1
, e
2
) ∈ R
1
) → S(e
2
); выполнить
H := H ∪ {e
2
}.
Шаг 2. Расширение множества аргументов.
Ко всем e
1
, таким что H(e
1
), (e
1
, e
2
) ∈ R
4
) применить правило П4
и построить множество M := M ∪ {e
2
} всех e
2
, таких что M (e
2
).
Шаг 3. Тестирование аргументов.
Для каждого e, такого что M (e), применяем процедуру Q; если
Q(e) = O(e), то O := O ∪ {e}. Переход к шагу 1.
Шаги 1–3 выполняются до стабилизации множеств O и H, ина- че говоря, до нахождения решения уравнения неподвижной точки
ARG1(X) = X, где X = H ∪ O.

2.4. Рассуждения на основе прецедентов
97
Шаг 4. Редукция множества гипотез по отвергающим аргументам.
Для всех e, таких что имеет место H(e), O(e
1
) и (e
1
, e) ∈ R
5
H := H\{e}.
Шаг 5. Редукция множества гипотез по обусловленным (отсутству- ющим, подтверждающим) аргументам.
Для всех e, таких что H(e), (e, e
1
) ∈ R
1
и выполняется ¬O(e
1
),
в соответствии с правилом П5 заключаем, что ¬H(e). Полагаем
H := H\{e}.
Шаг 6. Если мощность множества гипотез |H| в результате оказалась меньшей или равной единице, полагаем S = H и алгоритм за-
вершает работу.
Шаг 7. Дифференциация множества гипотез.
Если |H| > 1 и в H найдутся две гипотезы h
1
и h
2
, множества аргументов которых Arg(h
1
) и Arg(h
2
) строго вложены одно в другое: Arg(h
1
) ⊂ Arg(h
2
), гипотеза h
1
удаляется из множе- ства гипотез. Эта процедура применяется попарно ко всем таким гипотезам. Результирующее множество гипотез H называется объясняющим множеством.
Шаг 8. Минимизация объясняющего множества.
Если Arg(h) — множество аргументов e гипотезы h
1
, таких что
O(e) и если |H| > 2 и в H найдутся гипотезы h
1
, h
2
, h
3
, ..., h n
,
такие, что Arg(h
1
) ⊂ Arg(h
2
) ∪ Arg(h
3
) ∪ ... ∪ Arg(h n
), то h
1
удаляется из H. Повторяется до исчерпания множества таких гипотез.
Шаг 9. S = H. Завершение работы.
2.4. Рассуждения на основе прецедентов
Как уже было отмечено, основными задачами автоматизации рас- суждений на основе прецедентов являются: а) идентификация текущей проблемы и поиск подходящего прецедента и б) использование найден- ного прецедента для решения текущей проблемы. Эта последняя задача называется иногда задачей адаптации старого решения к текущей си- туации. Рассмотрим обе задачи более подробно.
2.4.1. Метрики на множестве прецедентов. Задача, которую мы будем решать в ближайших параграфах, — поиск подходящего прецедента. Для этого вначале рассмотрим понятие близости преце- дентов. Для уточнения понятия близости обычно используются неко- торые метрики. Рассмотрим некоторые из них [34, 35]. Будем здесь предполагать, что прецедент представлен в виде вектора признаков,
характеризующих некоторое состояние или процесс. Тогда степень близости устанавливается на основании парного сравнения текущего вектора с множеством векторов, например, множеством прецедентов.
4 Г. С. Осипов

98
Гл. 2. Методы автоматизации рассуждений
Поскольку прецедент есть образ в некотором пространстве призна- ков, то в случае, когда рассматривается n признаков, каждый преце- дент есть точка в n-мерном пространстве. Если в некотором n-мерном пространстве заданы 3 точки — A, B, C, то можно определить понятие
метрики. К метрикам предъявляются следующие требования:
d(A, B) > 0 (неотрицательность),
d(A, B) = 0 <=> A ≡ B (тождественность),
d(A, B) = d(B, A) (симметричность),
d(A, B) + d(B, C) > d(A, C) (правило треугольника).
Заметим, что этим требованиям удовлетворяет расстояние в n-мер- ном евклидовом пространстве:
d(X
k
, X
j
) =
q
(x
1k
− x
1j
)
2
+ ... + (x nk
− x nj
)
2
,
где X
k
= (x
1k
, x
2k
, ..., x nk
) и X
j
= (x
1j
, x
2j
, ..., x nj
) — образы (точки в n-мерном евклидовом пространстве).
Если признаки принимают значения либо 1, либо 0 (т. е. являются бинарными величинами), то в качестве метрики используется мера
Хемминга:
d(X
k
, X
j
) =
n
X
i=1
|x ik
− x ij
| или d(X
k
, X
j
) = sup i
|x ik
− x ij
| .
Близость образов можно вычислять с помощью мер близости, опре- деленных несколько иным образом. Условия, которым они должны удовлетворять, таковы:
0 6 γ(A, B) 6 1 (γ(A, B) нормирована),
γ(A, B) = 1 ⇔ A ≡ B,
γ(A, B) = γ(B, A),
γ(A, B) > γ(A, C), если d(A, B) > d(A, C).
В качестве меры близости, в частности, может быть использован классический коэффициент корреляции:
γ(B
1
, B
2
) =
hB
1
, B
2
i kB
1
k · kB
2
k
Иной мерой близости является мера Танимото–Джаккара:
K = n/n
′
,
где n — число совпавших признаков, n
′
— общее число признаков.

2.4. Рассуждения на основе прецедентов
99
В задачах определения близости прецедентов могут быть использо- ваны и иные типы метрик:
• евклидова метрика:
d ik
=
N
X
j=1
(x ij
− x kj
)
2
!
1 2
;
• мера сходства Хемминга:
µ
N
ij
=
n ik
N
,
где n ik
— число совпадающих признаков у образцов X
i и X
k
;
• вероятностная мера сходства:
P
j
= exp



−
N
P
i=1
(w ij
− x i
)
2
σ
2
j


,
где j — номер эталона, X
i
(i = 1, 2, ... , N ) — элемент неизвестного входного образца, w ij
— значение весового коэффициента, соответ- ствующее математическому ожиданию i-го элемента (признака) j-го эталона. Величина среднеквадратичного отклонения σ
j находится в ре- зультате экспериментов для каждого эталона;
• мера сходства Роджерса–Танимото:
µ
R−T
ik
= n ik
(n i
+ n k
− n ik
),
где: n ik
— число совпадающих единичных признаков у образцов X
i и X
k
; n i
, n k
— общее число единичных признаков у образцов X
i и X
k соответственно;
• метрика Махаланобиса:
R
2
M
(x, X) = (x − x)
⊤
C
−
1
(x − x),
где x — выборочное среднее класса H. C
−
1
— матрица, обратная ковариационной для рассматриваемого класса.
Элементы матрицы C
1
вычисляются по формуле c
ij
=
1
n − 1
n
X
β=1
(x
β
1i
− x
1i
)(x
β
1j
− x
1j
),
4*