Листинг 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_condI 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