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

240
Гл. 5. Приобретение знаний и машинное обучение
— интерконструирование
(
a : −v, b, c a : −w, b, c
)
⇒







a : −u, b, c u : −v u : −w







;
— интраконструирование
(
a : −v, b, c a : −w, b, c
)
⇒







a : −v, u a : −w, u u : −b, c







Все эти операторы могут быть выведены методом резолюции, опи- санным во второй главе книги. Напомним, что метод резолюции поз- воляет из истинных дизъюнктов (C
1
∨ l) и (C
2
∨ ¬l) вывести дизъюнкт
(C
1
∨ C
2
), разумеется, также истинный.
Для применения здесь метода резолюций его схему следует ин- вертировать. Если известна резольвента и одна из исходных строк,
можно построить вторую исходную строку. В зависимости от того,
содержит ли имеющаяся клауза утвердительную или отрицательную форму литерала l, мы будем говорить, соответственно, что имеет ме- сто идентификация или поглощение. Вся схема вывода для обоих операторов показана на рис. 5.9. Поясним только получение оператора идентификации, вывод оператора поглощения строится аналогично.
Предположим, даны две клаузы, a : −b, x и a : −b, c, d. Пусть первая называется «оригинал», а вторая — «резольвента». Задача заключается в нахождении неизвестной клаузы, которая вместе с оригиналом дала бы нам резольвенту. Для простоты рассматриваем пропозициональный случай.
Зная, что формулу A : −B можно записать в виде A ∨ ¬B, пре- вращаем наши клаузы в a ∨ ¬b ∨ ¬x и a ∨ ¬b ∨ ¬c ∨ ¬d. В обе клаузы входит подстрока a ∨ ¬b. Кроме того, в резольвенту входит еще и подстрока ¬c ∨ ¬d, которая могла бы быть унаследована из неизвестной клаузы. Оригинал, в свою очередь, содержит также предикат ¬x, и,
следовательно, его отрицание x должно входить в неизвестную клаузу.
После конкатенации резольвенты и оригинала мы получим строку
¬c ∨ ¬d ∨ x. Будучи преобразована обратно в клаузу Хорна, эта строка превратится в x : −c, d.
К сожалению, на практике эта задача усложняется. Так, в случае обратной резолюции обучающаяся система должна найти правильные подстановки аргументов в предикаты l и ¬l для того, чтобы они были совместимы. Например, предикаты p
1
= родитель (джон, билл) и p
2
=

5.3. Приобретение знаний из примеров
241
Рис. 5.9. Вывод операторов идентификации (а) и поглощения (б)
родитель (X, ева) совместимы только при подстановках θ
1
= {джон/X,
билл/Y } в первый предикат и θ
2
= {ева/Y } во второй предикат.
Для вывода операторов интерконструирования и интраконструиро- вания требуются несколько более сложные процедуры, которые мы здесь опустим.
Ревизия теорий. Иногда в распоряжении обучающейся системы имеется некоторый набор базовых знаний, который может управлять процессом обучения. Проиллюстрируем это на примере: предположим,
что базовые знания содержат частичную информацию о родственных отношениях, как на рис. 5.8, а дополнительная информация относи- тельно пола этих индивидов представлена в терминах предикатов муж-

242
Гл. 5. Приобретение знаний и машинное обучение
чина и женщина. После того, как обучающейся системе сообщили, что
Джек — отец Билла, она должна вывести определение предиката отец,
который до того не входил в базовые знания. Подход, в общих чертах описанный здесь, опирается на алгоритм, лежащий в основе системы
CLINT.
Обучающаяся система начинает свою работу с некоторого языка с очень сильными ограничениями — например, начальное ограничение требует, чтобы тело клаузы содержало в качестве аргументов только те константы и переменные, которые входят также и в голову, как в p(X, Y ) : −q(X, Y ), r(X). В случае клаузы отец(джек, билл) это озна- чает, что система ищет все литералы, которые не содержат никаких аргументов, кроме джек и билл. Обнаружив такие литералы, система связывает их конъюнкциями.
Предположим для примера, что базовые знания системы содержат,
среди прочего, следующие предикаты:
родитель (джек, билл).
родитель (том, джек).
родитель (том, ева).
родитель (ева, билл).
мужчина (том).
мужчина (джек).
мужчина (билл).
женщина (ева).
художник (билл).
певец (джек).
Если никаких других предикатов, содержащих джек или билл в качестве аргументов, нет, то попытка построить (искомый) концепт в терминах описанного выше простого языка завершится следующим описанием:
отец (джек, билл) : −родитель (джек, билл), мужчина (джек),
мужчина (билл), художник (билл), певец (джек).
Найдя эту конкретную клаузу, система обобщит ее, заменив константы переменными, и получит, таким образом, то, что называется начальной
клаузой:
отец (X, Y ) : − родитель (X, Y ), мужчина (X), мужчина (Y ),
художник (Y ), певец (X).
Ясно, что при таком методе построение клауз неизбежно происхо- дит вслепую, и даже поверхностный взгляд на эту «сфабрикованную»
клаузу обнаружит, что с ней что-то не так: тот факт, что джек —
отец билла, никак не связан с тем, что билл — мужчина, и уж, тем

5.3. Приобретение знаний из примеров
243
более, с его профессией. Чтобы справиться с этой проблемой, авторы системы CLINT вооружили обучающуюся систему способностью уточ- нять начальное описание концепта посредством несложного диалога с пользователем.
В процессе диалога система рассматривает по очереди каждую ато- марную формулу и проверяет ее необходимость: система строит новые примеры и просит пользователя их классифицировать. К примеру, на вопрос:
Правда ли, что отец (том, джек)?
пользователь ответит утвердительно, и это свидетельствует о том, что литерал художник(Y) не является необходимым (джек — певец, а том,
тем не менее, его отец).
Следующий вопрос должен прояснить, обязательно ли Y быть мужчиной. Зная, что ева — женщина, система отыскивает в базовых знаниях литерал родитель(том,ева) и задает пользователю вопрос:
Правда ли, что отец(том, ева)?
Утвердительный ответ говорит о том, что атомарная формула мужчи- на(Y) тоже не является обязательной. С другой стороны, на вопрос:
Правда ли, что отец (ева, билл)?
пользователь ответит отрицательно, а это означает, что атомарную формулу мужчина (X) нельзя удалить из клаузы.
Очевидно, что во время такой верификации первоначальная кла- уза может полностью измениться — возможно даже, что из ее тела будут удалены все литералы. Возможен и другой вариант: начальную клаузу найти не удастся. В обоих случаях система продолжит работу и поступит следующим образом: она ослабит некоторые ограничения,
например, ограничение на аргументы предикатов. Тогда предикатам из тела будет разрешено иметь один и только один аргумент, который не входит в голову, как в случае с клаузой:
grandparent(X, Y ) : − родитель (X, Z), родитель (Z, Y ).
Таким путем система обобщает описание концепта для того, чтобы оно охватило и те положительные экземпляры (построенные системой и предложенные пользователю), которые не подпадали под предыдущее описание.
Разумеется, описание может стать слишком общим — в том смысле,
что будет удовлетворять и отрицательным примерам. Чтобы исправить это положение, нужно принять соответствующие меры. В CLINT ис- пользуется следующее решение: для отрицательного примера строится дерево объяснения, которое находит ту самую преступную клаузу c,
из-за которой под описание подпадает отрицательный пример; клауза c удаляется из базы знаний, а полученная в результате структура зна-

244
Гл. 5. Приобретение знаний и машинное обучение
ний вновь обобщается, для того чтобы все положительные примеры,
которые описывались клаузой c, снова оказались «охвачены».

5.4. Искусственные нейронные сети и их обучение
245
Активационная функция может быть
• линейной: F (NET) = k · NET, k = const;
• пороговой: F (NET) =
(
1 ⇔ NET > T ,
0 ⇔ NET 6 T ,
T = const, порог актива- ции нейрона;
• иной функцией, более точно моделирующей процессы, происхо- дящие в биологическом нейроне.
Если ∀NET ∃a, b : (a < b, a 6 F (NET) 6 b), функция F носит на- звание сжимающей. Часто в качестве сжимающей функции исполь- зуется логистическая (сигмоидальная) функция OUT
i
= F (NET
i
) =
=
1 1 + e
−NET
i
∈ (0.0, 1.0). Такого рода активационную функцию можно рассматривать как нелинейную усилительную характеристику искус- ственного нейрона. Исследования Гроссберга показали, что использо- вание подобной активационной функции снимает проблему шумового насыщения и качество выхода нейрона практически не зависит от уровня входного сигнала [118].
Такая модель искусственного нейрона лишена многих свойств био- логического нейрона: отсутствует учет временных задержек: входной сигнал «немедленно» порождает выходной — система лишена дина- мики.
Совокупность нейронов (как правило, одинаковой размерности)
образует слой нейронной сети. Слои могут комбинироваться таким образом, что выходы нейронов предыдущих слоев являются входами нейронов следующих слоев (для простых сетей без обратных связей),
образуя искусственную нейронную сеть.
Входной вектор сети и выход последнего нейрона считаются внеш- ними слоями, остальные слои рассматриваются как внутренние или скрытые.
В некоторых источниках векторы, являющиеся выходами скрытых слоев нейронов, также именуются слоями.
Вычисления, выполняемые сетью без обратных связей, записыва- ются следующим рекуррентным матричным уравнением: OUT
i+1
=
= F
i
(W
i
· OU T
i
)
∗
, где OUT
i
— выход i-го слоя нейронов, W
i
∈
∈ Mat n×m
R — матрица весов нейронов i-го слоя, n — число нейронов в слое, m — размерность нейрона, F
i
— покомпонентная пороговая функция i-го слоя нейронов,
∗
— оператор транспонирования векто- ра. Для первого скрытого слоя входной вектор соответствует входно- му вектору OUT
0
= X = (x
1
, x
2
, ... , x k
). Размерность выхода каждого предыдущего слоя нейронов равна размерности входа последующего слоя.
Между слоями нейронов могут существовать обратные связи, т. е.
выходы нейронов в свою очередь являются входами нейронов предыду- щих слоев. В этих случаях сеть не имеет простой линейной конфигу-

246
Гл. 5. Приобретение знаний и машинное обучение
рации и описывается более сложными системами дифференциальных уравнений.
Под процедурой обучения сети (автоматической или контролиру- емой) понимается итерационный процесс подстройки весов нейронов таким образом, чтобы группе входных сигналов, принадлежащих к од- ному классу, соответствовал идентичный выходной сигнал. Под кол- лапсом сети в процессе обучения подразумевается ситуация, когда никакая подстройка весов не ведет к получению приемлемого резуль- тата обучения (процесс обучения не сходится, либо сходится крайне медленно, а потому может считаться бесконечным).
5.4.2. Достоинства и недостатки искусственных нейронных се-
тей.
Искусственные нейронные сети имеют как достоинства, так и недостатки [113, 119].
Общие недостатки искусственных нейронных сетей:
• относительно большой объем вычислений, связанных с получени- ем выхода сети, особенно в сравнении с системами, работающими с деревьями решений;
• размер структуры, необходимой для хранения данных одного уровня нейронной сети линейно зависит от размерности входного вектора (размерность нейрона) и количества классов, к кото- рым могут принадлежать входные объекты (количество нейронов в слое);
• теоретически, вход и выход искусственной нейронной сети яв- ляются синхронными (одновременно с подачей входного сигнала сеть должна генерировать выходной сигнал), на практике этого достичь невозможно;
• в случаях неконтролируемого обучения возможны ситуации кол- лапса сети. Неверный подбор количества нейронов может приве- сти либо к коллапсу сети (количество нейронов меньше количе- ства распознаваемых классов), либо к потере общности.
К достоинствам искусственных нейронных сетей можно отнести следующие:
• относительная простота производимых вычислений и используе- мых структур данных, легкость аппаратной реализации;
• способность к самоорганизации: алгоритмы обучения нейрон- ных сетей построены таким образом, что наиболее характерным признакам (компонентам) входного вектора в процессе обуче- ния автоматически приписываются б´ольшие веса. Искусственные нейронные сети можно использовать для выделения наиболее характерных особенностей входного сигнала;
• возможность построения дерева решения (decision tree) по обу- ченной нейронной сети.