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

232
Гл. 5. Приобретение знаний и машинное обучение
и СКВ содержит правило интерпретации
«Для применимости правила к примеру по крайней мере 3 условия
из
A
1
...A
n
должны быть выполнены на этом примере».
Очень простым примером двухуровневого подхода может служить метод TRUNC, состоящий из следующих общих шагов:
1. Используя AQ, построить начальное множество правил.
2. Установить «важность» каждого правила. Простой мерой важно- сти может служить число положительных примеров, покрывае- мых правилом. Сохранить в БПК только самые важные правила.
3. Определить СКВ-процедуру для правильного распознавания при- меров, не описываемых точно правилами из БПК.
Когда для сопоставления примера правилу используется СКВ-про- цедура, новому примеру приписывается класс того правила в БПК,
которое дает «наилучшее совпадение» при сопоставлении на основе
СКВ.
5.3.5. Оценка обучающих алгоритмов. Рассмотрим критерии качества алгоритмов машинного обучения. Некоторые из таких крите- риев приведены в табл. 5.15.
Т а б л и ц а 5.15. Оценка алгоритмов МО
Критерий
Комментарии
Точность
Процент правильно распознанных плюсов и минусов
Эффективность
Количество требуемых примеров, вычисли- мость
Устойчивость
В условиях шума, неполноты
Специальные требования
Инкрементность, изменчивость концепта
Сложность концепта
Проблемы представления примеров и базовых знаний
Прозрачность
Понятность для пользователя-человека
Вероятно, самым важным критерием является точность. Посколь- ку идея обучения концептам состоит в правильной идентификации новых экземпляров, то вполне логично измерять успешность обучения процентом правильно классифицированных тестовых примеров. Пред- положим, системе предлагается классифицировать множество из 200
примеров, 100 из которых положительны и 100 отрицательны. Если система правильно расклассифицировала 80 положительных примеров и 60 отрицательных, то точность равна
80 + 60 200
= 0,7, т. е. 70 %.
Иногда важнее знать, сколько раз система классифицировала поло- жительные примеры, при том что распознавание отрицательных менее

5.3. Приобретение знаний из примеров
233
существенно (или наоборот). В таком случае мы различаем два вида ошибок: положительные примеры, распознанные как отрицательные,
и отрицательные примеры, распознанные как положительные. Эти ошибки демонстрируют, что описание либо слишком специализиро- ванно, либо слишком общо. В случае излишне специализированного описания система будет скорее неверно распознавать положительные примеры, чем отрицательные. В случае излишне общего описания система чаще будет ошибочно принимать отрицательные примеры за положительные.
В идеале обучающаяся система должна выдвинуть гипотезу (внут- реннее описание концепта), которая была бы непротиворечива (не удо- влетворяла ни одному отрицательному экземпляру) и полна (охваты- вала бы все положительные экземпляры).
Точность классификации — это только один из критериев оценки алгоритмов машинного обучения. От обучающейся системы требуется еще и эффективность — способность достичь определенного уровня точности при минимальном количестве обучающих примеров. Учи- тель не всегда имеет возможность предоставить много примеров, да и вообще, способность к быстрому обучению — один из признаков интеллекта. Интерес представляют, таким образом, критерии вычис-
лительной сложности: сколько времени требуется компьютеру для построения хорошей гипотезы.
Еще один критерий связан с прозрачностью (объяснимостью) вы- водимого описания концепта. Часто важно, чтобы порождаемое описа- ние было понятным и чтобы пользователь мог из него узнать нечто новое об изучаемой области. Такое описание, будучи непосредственно использовано человеком, могло бы обогатить его знания. Этот критерий используется и в тех случаях, когда выводимые описания предназна- чены для использования в системе, основанной на знаниях, поведение которой должно быть объяснимо. По этому критерию машинное обуче- ние в интеллектуальных системах обычно отделяется от других форм обучения, включая нейронные сети и статистические методы.
Серьезную трудность в обучении представляет шум (ошибки) в при- мерах и/или в метках классов примеров. Измерительные приборы,
которые сообщают значения атрибутов, могут быть неточны или плохо отрегулированы; значения атрибутов, предоставленные учителем, могут страдать субъективизмом; данные могут пострадать от несчастного случая, часть данных может быть потеряна. Множество неприятностей может случиться с примерами, прежде чем они попадут в систему.
Поэтому естественно, что требуется устойчивость к шуму и устой-
чивость к пропускам данных (например, к отсутствию значений ат- рибутов). Насколько важен этот критерий, нужно решать в каждом конкретном случае.

234
Гл. 5. Приобретение знаний и машинное обучение
Вообще, к специфике решаемой задачи нужно относиться весьма серьезно. К примеру, пользователь может потребовать от обучающейся системы, чтобы она приобретала знания в режиме онлайн из потока поочередно поступающих примеров (в противоположность ситуации,
когда все примеры имеются в наличии в самом начале обучения).
Представим, что в тот момент, когда уже сформировано начальное опи- сание концепта, появляется новый пример. В традиционных алгоритмах пакетной обработки это означало бы необходимость заново выполнить процедуру обучения на всех данных. Едва ли такое поведение можно назвать интеллектуальным. Обучающаяся система должна быть спо- собна к уточнению ранее приобретенных знаний, к инкрементному
(пошаговому, поcтепенному) обучению, свойственному человеку.
Инкрементное обучение приобретает особую важность, когда си- стеме приходится иметь дело с изменчивым или эволюционирующим
концептом. В некоторых областях значение того или иного концепта может время от времени меняться. Это видно на примере таких тер- минов, как «модное платье» или «демократия». Обучающаяся система должна уметь учитывать такие изменения.
И, наконец, разработчик должен уделить внимание языкам пред- ставления, т. е. языку, на котором описываются примеры, и языку, ко- торый используется для записи базовых знаний. Читатель уже обратил внимание на то, что различные языки представления отличаются друг от друга по выразительности. Например, алгоритм TDIDT использует язык атрибутивной логики, тогда как более сложные системы способны обучаться концептам на примерах, описанных в языке предикатов первого порядка.

5.3. Приобретение знаний из примеров
235
Рис. 5.8. Отношения родства
Предположим, что, имея это отно- шение в своих базовых знаниях, си- стема хочет обучиться концепту дедуш- ка (X, Y ) ∨ бабушка (X, Y ). Предполо- жим также, что от учителя система по- лучила следующие положительные при- меры концепта:
дедушка (1, 4),
дедушка (1, 5),
дедушка (1, 6),
бабушка (3, 7).
Эти примеры тоже проще записать в виде бинарного отношения:
{(1, 4), (1, 5), (1, 6), (3, 7)},
на котором выполняется концепт дедушка (X, Y ) ∨ бабушка (X, Y ).
Все прочие родственные отношения между лицами 1, ... , 7 счита- ются отрицательными примерами.
Весьма популярным подходом в обучении с использованием ло- гики предикатов первого порядка является индуктивное логическое программирование (ИЛП), активно исследуемое в настоящее время.
Рассмотрим его ниже.
Машинное обучение в языке клауз Хорна. Предположим, тре- буется написать программу, которая сможет обучиться концепту «ба- бушка или дедушка» по примерам отношений родства. Концепт должен быть описан с помощью клауз Хорна.
Стремясь к простоте описания концепта, следует начать с языка,
который допускает в теле клауз лишь те аргументы, которые встреча- ются также и в его голове. Допустим, описание концепта представляет собой множество клауз Хорна следующего вида:
C
1
: −L
11
, L
12
, ... , L
1m
,
C
2
: −L
21
, L
22
, ... , L
2m
,
где предикат C
1
— это голова клаузы, а литералы L
ij составляют тело клаузы. Запятые, разделяющие литералы в теле клаузы, указывают на наличие между ними конъюнкции. Каждый литерал представляет отношение, имеющее n > 0 аргументов. Вспомним метод AQ, где обу- чающаяся система начинала с относительно общего описания с уча- стием одного-единственного атрибута, которое затем становилось все

236
Гл. 5. Приобретение знаний и машинное обучение
более и более специализированным за счет включения новых условий.
Используем здесь тот же принцип.
Добавлением литерала в тело клаузы мы получим эффект, ана- логичный эффекту специализации, который достигается добавлением условия в правило при методе AQ или присоединением дополнительной вершины к какому-либо уровню дерева решений, а потому правильно будет начать с клаузы, состоящей исключительно из головы, и затем специализировать ее путем добавления литералов в тело. Поскольку базовые знания не содержат никаких предикатов, кроме «родитель»,
и поскольку в теле клаузы допускаются только те переменные, которые встречаются в голове, то для определения концепта «бабушка или дедушка» (в дальнейшем будем обозначать его через «grandparent»)
можно использовать следующие клаузы:
grandparent (X, Y ) : − родитель (X, Y ),
grandparent (X, Y ) : − родитель (Y , X),
grandparent (X, Y ) : − родитель (X, X),
grandparent (X, Y ) : − родитель (Y , Y ).
Однако ни одна из этих клауз не покрывает ни один положитель- ный пример. Очевидно, что нужно ослабить ограничение, разрешив использовать в теле клаузы аргумент, который не входит в голову.
Можно построить четыре литерала такого вида: родитель (X, Z), роди- тель (Y , Z), родитель (Z, X) и родитель (Z, Y ). Предположим, система выбирает вариант:
grandparent (X, Y ) : − родитель (X, Z).
Посмотрим теперь, для каких троек (X, Z, Y ), удовлетворяющих данной клаузе, голова клаузы представляет положительный пример,
а для каких — отрицательный:
(+) : (1, 2, 4) (1, 2, 5) (1, 2, 6) (1, 3, 4) (1, 3, 5) (1, 3, 6) (3, 4, 7) (3, 5, 7) (3, 6, 7)
(−) : (1, 2, 1) (1, 2, 2) (1, 2, 3) (1, 2, 7) (1, 3, 1) (1, 3, 2) (1, 3, 3) (1, 3, 7)(3, 4, 1)
(3, 4, 2) (3, 4, 3) (3, 4, 4) (3, 4, 5) (3, 4, 6) (3, 5, 1) (3, 5, 2) (3, 5, 3) (3, 5, 4)
(3, 5, 5) (3, 5, 6) (3, 6, 1) (3, 6, 2) (3, 6, 3) (3, 6, 4) (3, 6, 5) (3, 6, 6) (4, 7, 1)
(4, 7, 2) (4, 7, 3) (4, 7, 4) (4, 7, 5) (4, 7, 6) (4, 7, 7)
При ближайшем рассмотрении видно, что положительные тройки включают все 4 положительных примера: (1, 4) (1, 5) (1, 6) (3, 7), а от- рицательные тройки включают 17 отрицательных примеров: (1, 1) (1, 2)
(1, 3) (1, 7) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) (4, 1)(4, 2) (4, 3) (4, 4)
(4, 5) (4, 6) (4, 7).
Мы можем сказать, что клауза grandparent (X, Y ) : − родитель (X, Z)
противоречива, потому что она удовлетворяет и отрицательным приме- рам. Противоречивость можно уменьшить за счет правильно выбран-

5.3. Приобретение знаний из примеров
237
ной специализации этой клаузы. Сделать это можно путем добавления к ней других разрешенных литералов. Попробуем сделать следующее:
grandparent (X, Y ) : − родитель (X, Z), родитель (Z, Y ).
Эта клауза описывает следующие тройки (X, Z, Y ):
(+) : (1, 3, 4) (1, 3, 5) (1, 3, 6) (3, 4, 7),
(−) : ни одного.
Поскольку охвачены все положительные примеры и ни одного отри- цательного, обучающаяся система удовлетворена этой клаузой и оста- навливается.
А что, если бы вместо родитель (Z, Y ), мы добавили бы какой-то другой литерал? Рассмотрим очередную клаузу:
grandparent (X, Y ) : − родитель (X, Z), родитель (Y , Z).
Несмотря на то, что эта клауза не описывает ни одного отрицатель- ного примера, ее полезность сомнительна, так как она не описывает и ни одного положительного. Очевидно, что нужен подходящий критерий для определения того, какой литерал добавлять в клаузу.
Обратимся к более сложному концепту — допустим, предок. Ис- пользуя известные из рис. 5.8 родственные отношения между семью людьми, можно получить следующие положительные примеры:
предок = {(1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7) (3, 4) (3, 5) (3, 6) (3, 7) (4, 7)}.
Поиск лучшего литерала (с теми же аргументами, что и голова клаузы) приводит к следующему описанию:
предок (X, Y ) : − родитель (X, Y ).
Эта клауза непротиворечива, поэтому специализация не требуется.
Система сохранит ее и — поскольку описание неполно — попытается найти альтернативную клаузу, описывающую те положительные при- меры, которые не попали в поле действия первой клаузы. Результат интерпретируется таким образом, чтобы по крайней мере одна из клауз описывала пример, если он представляет положительный экземпляр концепта. Повторяя процедуру, найдем следующие три клаузы:
предок (X, Y ) : − родитель (X, Y ),
предок (X, Y ) : − родитель (X, Z), родитель (Z, Y ),
предок (X, Y ) : − родитель (X, Z), родитель (Z, W ),
родитель (W , Y ).
Даже если эти клаузы покрывают все обучающие примеры, мы зна- ем, что они неполны, поскольку охватывают только четыре поколения.
Читатель, знакомый с логическим программированием, посоветовал бы прибегнуть к рекурсивному описанию:
предок (X, Y ) : − родитель (X, Y ),
предок (X, Y ) : − родитель (X, Z), предок (Z, Y ).

238
Гл. 5. Приобретение знаний и машинное обучение
Обучающаяся система может найти такое описание, только если ей разрешено определять предикат «предок» в терминах начального пони- мания концепта. В этом состоит принцип рекурсии. В самом начале система использует предикат «родитель». После того как сформули- рована первая клауза, системе следет разрешить использовать также предикат «предок».
Процедура, которую мы только что описали, составляет ядро систе- мы FOIL, разработанной Куинланом. Это соображения можно форма- лизовать в виде следующего алгоритма.
Алгоритм FOIL.
1. Задать клаузу, определив голову, которая представляет имя целе- вого концепта (концепта, которому система должна обучиться);
тело оставить пустым.
2. Если клаузе удовлетворяют отрицательные примеры, выполнять:
Найти «хороший» литерал для добавления в тело клаузы.
3. Удалить все примеры, описываемые клаузой.
4. Добавить клаузу в построенное таким образом определение кон- цепта. Если есть положительные примеры, не покрываемые опре- делением концепта, перейти к 1.
К этому моменту остается одна проблема: как найти «хороший»
литерал, который нужно включить в клаузу на шаге 2 алгоритма. Для этой цели FOIL использует информационный критерий, аналогичный тому, что применяется для построения деревьев решений.
Обозначим через T
+
i число положительных примеров, описываемых конъюнкцией L
1
, L
2
, ..., L
i−1
, и обозначим через T
−
i число отрицатель- ных примеров, описываемых той же конъюнкцией. Тогда информация,
возникающая при выборе положительного примера, равна
I
i
= − log

T
+
i
T
+
i
+ T
−
i

После добавления нового литерала L
i эта информация становится равна
I
i+1
= − log
T
+
i+1
T
+
i+1
+ T
−
i+1
!
Успешность литерала literal L
i измеряется двумя факторами:
1. Количеством информации I
i
− I
i+1
;
2. Числом T
++
i положительных примеров, которым продолжает удо- влетворять клауза после добавления L
i+1
Соответственно, мера успешности алгоритма FOIL определяется как
Gain(L
i
) = T
++
i
× (I
i
− I
i+1
).

5.3. Приобретение знаний из примеров
239
Очень полезно обратить внимание на то, как FOIL сочетает два подхода, описанных в предыдущем разделе. В принципе, программа вы- полняет алгоритм AQ, пытаясь охватить пространство положительных примеров некоторым множеством клауз. Во внутреннем цикле клаузы подвергаются пошаговой специализации при помощи некоторой проце- дуры, которой управляет функция, аналогичная той, что применяется в методе «разделяй и властвуй».
Обратная резолюция. Вернемся к поисковой концепции обуче- ния. Легко видеть, что FOIL использует два поисковых оператора:
оператор обобщения добавить_клаузу и оператор специализации до-
бавить_литерал. Добавив сюда обратные операторы удалить_клаузу
для специализации и удалить_литерал для обобщения, мы получим элементарный репертуар операторов для обучения в логике первого порядка. Работу этих операторов можно показать на примере следую- щих четырех шагов, которые постепенно превращают клаузу x : −a, b в клаузу x : −d, e:
— добавить клаузу x : −a, b ⇒
(
x : −a, b x : −c, d
)
;
— удалить клаузу
(
x : −a, b x : −c, d
)
⇒ x : −c, d;
— добавить литерал x : −c, d ⇒ x : −c, d, e;
— удалить литерал x : −c, d, e ⇒ x : −d, e.
Этот репертуар можно расширить следующими операторами индук- тивного поиска:
— идентификация
(
x : −b, x x : −b, c, d
)
⇒
(
a : −b, x x : −c, d
)
;
— поглощение
(
x : −c, d x : −b, c, d
)
⇒
(
x : −c, d a : −b, x
)
;