Листинг 18.3. Программа логического вывода правил вывода

% Обучение на основе простых правил вывода:- ор(300, xfx, <==).

I learn{ Class): собрать учебные примеры в список, сформировать и вывести i описание для класса Class, затем внести в базу данных соответствующее % правило, касающееся класса Class

learnt Class):- bagof(example(ClassX, Obj), example(ClassX, Obj

learnt Examples, Class, Description), nl, write' Class), write(' <== '), nl, writelist(Description), assert (Class <== Description).

Examples), % Собрать % примеры % Сформировать правило % Вывести правило

% Внести правило в базу данных

% learnt Examples, Class, Description):

% описание Description охватывает точно все примеры класса Class

% в списке. Examples

learnt Examples, Class, []):-not member(example! Class,

), Examples).

% Нет примеров, которые нужно % было бы охватить описанием

 

learn(Examples, Class, [Conj I Conjs]): learn_conj (Examples, Class, Conj), remove(Examples, Conj, RestExamples),

learnt RestExamples, Class, Conjs).

% Удалить примеры, которые % соответствуют условию Conj % Охватить описанием % остальные примеры

% learn_conj| Examples, Class, Conj):

% Conj - это список значений атрибутов, которому соответствуют некоторые
% примеры класса Class и не соответствует ни один пример какого-то

% иного класса

learn_conj (Examples, Class, []) not (member! example(ClassX, ClassX \== Class),!.

: -

), Examples), % Нет примеров какого-то % иного класса

 

learn_conj (Examples, Class, [Cond | Conds]) choose_cond(Examples, Class, Cond), filter (Examples, [ Cond], Examplesl), learn_conj(Examplesl, Class, Conds).

: -

% Выбрать значение атрибута

choose_cond I Examples, Class, AttVal):-

findalK AV/Score, score! Examples, Class, AV, Score), AVs),
best! AVs, AttVal). % Атрибут с наилучшей оценкой

Глава 18. Машинное обучение

best( [ AttVal/_], AttVal).

best([ AVO/SC, AV1/S1 I AVSlist], AttVal):-

El > SO,!, % Атрибут AVl имеет лучшую оценку, чем AVO

best{ [AV1/S1 ] AVSlist], AttVal)

best([AVO/SO AVSlist], AttVal).

% filterf Examples, Condition, Examplesl):

Ч список Examplesl содержит элементы списка Examples, которые соответствуют

% условию Condition

filter С Examples, Cond, Examplesl):-findalH example! Class, Obj),

< member С example{ class, Obj), Examples), satisfy(Obj, Cond)),

Examplesl).

i remove(Examples, Conj, Examplesl):

удаление из списка Examples тех примеров, которые охвачены условием Conj, % и получение списка Examplesl

remove ([ ], _, [ ]).

remove [ [example < Class, Obj) I Es], Conj, Esl):-

satisfy(Obj, Conj),!, % Первый пример соответствует условию Conj remove (Es, Conj, Esl). % Удалить его

remove С IE I Es] _r Conj, [E I Esl]):- % Оставить первый пример в списке remove(Es, Conj, Esl),

satisfy{ Object, Conj):-

not (member; Att = Val, Conj),

member ( Att - ValX, Object), ValX \—val).

score(Examples, Class, AttVal, Score):-

candidate С Examples, Class, AttVal), I Подходящее значение атрибута

filter!' Examples, [ AttVal], Examplesl), % Примеры в списке Examplesl

% соответствуют условию Att = Val
length! Examples!, N1), % Длина списка

count_pos[ Examplesl, Class, NPosl), % Количество положительных примеров
NPosl > 0, % По меньшей мере один положительный

% пример соответствует значению AttVal Score is 2 * HPOSl - Ml.

candidate,- Examples, Class, Att -Val):-

attribute! Att, Values), % Атрибут

member; Val, values), % Значение

suitable,- Att = Val, Examples, Class).

suitable(AttVal, Examples, class):-

% По меньшей мере один отрицательный пример не должен соответствовать

% значению AttVal rr.emberf example! ClassX, ObjX), Examples),

ClassX \== Class, Ч Отрицательный пример, который

not satisfy,- ObjX, [ AttVal]),!. % не соответствует значению AttVal

%coimt_pos(Examples, Class, Я):

% H - количество положительных примеров класса Class

ccmnt_pos([], _, 0).

count_pos { [example (ClassX,_) (Examples], Class, И): -count_posi Examples, Class, Ml), (ClassX = Class,!, N is Ni + 1; К = N1).

424 Часть II. Применение языка Prolog в области искусственного интеллекта

writelist t |

writelistt [X | LJ):-tab[ 2), write (X), nl, writelistt L).

Каждый список атрибутов и значений формируется с помощью следующей проце­дуры: learn_con](Examples, Class, Conjunction}

Список атрибутов и значений Conjunction наращивается постепенно, начиная с пустого списка, к которому последовательно добавляются условия в следующей форме: Attribute = value

Обратите внимание на то, что в результате список атрибутов и значений стано­вится все более и более конкретным (охватывает все меньше объектов). Список атри­бутов и значений является наиболее приемлемым, если он стал настолько конкрет­ным, что охватывает только положительные примеры класса Class.

Процесс формирования подобного конъюнктивного выражения характеризуется высокой комбинаторной сложностью. Каждый раз, когда происходит добавление но­вого условия, состоящего из атрибута и значения, приходится рассматривать значи­тельное количество возможных вариантов добавления, которое почти столь же вели­ко, как и количество пар атрибутов и значений. При этом невозможно сразу же оп­ределить, какой из этих вариантов является наилучшим. Как правило, следует стремиться к тому, чтобы все положительные примеры были охвачены с помощью минимально возможного количества правил, а сами правила были наиболее кратки­ми. Такое обучение может рассматриваться как поиск среди возможных описаний с целью максимального уменьшения длины описания понятия. В связи с высокой комбинаторной сложностью этого поиска обычно приходится прибегать к использо­ванию некоторых эвристических функций. Работа программы, приведенной в лис­тинге 18.3, основана на использовании функции эвристической оценки, которая применяется локально. На каждом этапе к списку добавляется только значение ат­рибута с наилучшей оценкой, а все остальные варианты сразу же отбрасываются, Поэтому поиск сводится к детерминированной процедуре без какого-либо перебора с возвратами. Такой поиск называют поглощающим, или жадным (greedy), а также по­иском по принципу "подъема к вершине" (hill-climbing). Он рассматривается как по­глощающий, поскольку всегда предусматривает выбор наиболее перспективной альтер­нативы, не оставляя шансов для других вариантов выбора. Но при такой организации поиска существует риск, что не будет обнаружено кратчайшее описание понятия.

Эвристическая оценка является простой и основана на следующем интуитивном наблюдении: полезное условие, заданное в виде атрибута и значения, должно позво­лять хорошо отличать друг от друга положительные и отрицательные примеры. По­этому оно должно охватывать максимально возможное количество положительных примеров и минимально возможное нрличество отрицательных примеров. На рис. 18.9 проиллюстрированы принципы работы такой эвристической функции оценки. Функция, применяемая в рассматриваемой программе, реализована в виде следующей процедуры: score[ Examples, Class, AttributeValue, Score}

где Score — разница между количеством охваченных положительных и отрицатель­ных примеров.

Программа, приведенная в листинге 18.3, может быть вызвана на выполнение для создания некоторого описания класса для примеров, приведенных в листинге 18.1, с помощью следующего запроса:

?- learnt nut), 1еагп(key), learnf scissors). nut < = =

[ shape = compact, holes = 1] key < = =

Глава 18. Машинное обучение

[ shape - other, size = small] (holes = 1, shape = lor.g] scissors <= [ holes = 2, size = large]

Рис. 18.9. Эвристическая оценка значения атрибута; где 90S — множество положи­тельных примеров изучаемого класса. NEG — множество отрицательных примерна этого класса. Затененная область. ATTVAL, пред­ставляет множество объектов, которые удовлетворяют условию, заданному в еиде атрибутов и значении. Эвристическая оцен­ка значения атрибута определяется как разница между количеством положительных примеров в области ATTVAL и количеством отрицательных примеров в этой области

Кроме того, процедура learn вносит правила, касающиеся соответствующих классов в программе, в базу данных. Эти правила могут использоваться для класси­фикации новых объектов. Соответствующая процедура распознавания, в которой применяются усвоенные описания, приведена ниже, classify[ Object, Class):-

Class <= = Description, % Правило, касающееся класса Class,

1 полученное путем обучения
member! conj, Description), % Конъюнктивное условие
satisfy! Object, conj). % Объект Object удовлетворяет условию Conj