Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


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





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-10-01; ћы поможем в написании ваших работ!; просмотров: 515 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќадо любить жизнь больше, чем смысл жизни. © ‘едор ƒостоевский
==> читать все изречени€...

1279 - | 1039 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.01 с.