Логический вывод правил на основании примеров

Теперь рассмотрим, каким образом могут формулироваться правила на основании множества примеров. В отличие от задачи распознавания арок, приведенной в пре­дыдущем разделе, описание класса не формируется путем последовательной обработ­ки отдельных примеров. Вместо этого все примеры обрабатываются одновременно. Поэтому такой процесс называют также пакетным обучением (batch learning) в от­личие от постепенного, инкрементного обучения (incremental learning).

В данном случае основное требование к процедуре обучения состоит в том, чтобы сформированное описание класса точно соответствовало примерам, относящимся к этому классу. Иными словами, это описание должно соответствовать всем положи­тельным примерами данного класса, но ни одному отрицательному примеру.

Если объект соответствует описанию, считается, что описание охватывает дан­ный объект. Поэтому необходимо сформировать такое описание для определенного класса, которое охватывает все экземпляры этого класса, но не охватывает ни одного постороннего экземпляра. Такое описание принято называть полным и достоверным: оно является полным, поскольку охватывает асе положительные примеры, и досто­верным, поскольку не охватывает ни одного отрицательного примера.

Для формирования непротиворечивой гипотезы в виде множества правил вывода широко используется алгоритм охвата (covering algorithm), программа которого приведена в листинге 18.2. Он носит такое название, поскольку постепенно охваты­вает все положительные примеры изучаемого понятия. Алгоритм охвата начинает свою работу с пустого множества правил, затем обеспечивает итерационный логиче­ский вывод одного правила за другим. Ни одно правило не может охватывать какой-либо отрицательный пример, но должно распространяться на некоторые положи­тельные примеры. После логического вывода нового правила это правило добавляет­ся к формулировке гипотезы и из множества примеров удаляются охваченные им положительные примеры. На основании этого нового сокращенного множества при­меров осуществляется логический вывод следующего правила, и такая работа про­должается до тех пор, пока не будут охвачены все положительные примеры.

Листинг 18,2. Алгоритм охвата; процедура indviceOjieRule(E) вырабатывает правило, которое охватывает некоторые положительные примеры и ни одного отрицательного

Чтобы логическим путем вывести список правил RULELIST для множества S

классифицированных примеров, выполнить следующее:

RULELIST := empty; E:=S;

while E содержит положительные примеры do begin

RULE := InduceOneRulefE);

Добавить правило RULE к списку правил RULELIST; Удалить из множества Е все примера, охваченные правилом RULE end

Алгоритм охвата (см. листинг 18.2) допускает введение только непротиворечивых правил. Правила, полученные с помощью логического вывода, должны охватывать все положительные примеры и ни одного отрицательного. На практике используются также менее строгие варианты этого алгоритма охвата, особенно если для обучения применяются зашумленные данные. При использовании таких вариантов работа ал­горитма может оканчиваться до того, как будут охвачены все положительные приме­ры. Кроме того, может быть предусмотрена возможность охватывать в процедуре InduceOneRule некоторые отрицательные примеры, кроме положительных, при ус­ловии, что охваченные положительные примеры в достаточной степени превышают по количеству отрицательные.

Реализация этого алгоритма охвата приведена в листинге 18.3. Процедура learn) Examples, Class, Description)



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


этой программы формирует непротиворечивое описание Description для класса Class и примеров Examples . Ее работу можно описать примерно так, как показано ниже .

Для охвата всех примеров класса Class,приведенных с помощью списка

примеров Examples,необходимо выполнить следующее:

если ни один из примеров списка Examplesне относится к классу Class,то

Description= [](охвачены все положительные примеры) ;

в противном случае Description = [ConjI Conjs],где Conjи Conjs

формируются таким образом.

1. Собрать список Conjзначений атрибутов, который охватывает хотя бы один
положительный пример класса Classи не охватывает ни одного примера

из любого другого класса.

2. Удалить из списка Examplesвсе примеры, охваченные списком Conj, затем
распространить описание Conjsна все оставшиеся и не охваченные объекты.