Теперь рассмотрим, каким образом могут формулироваться правила на основании множества примеров. В отличие от задачи распознавания арок, приведенной в предыдущем разделе, описание класса не формируется путем последовательной обработки отдельных примеров. Вместо этого все примеры обрабатываются одновременно. Поэтому такой процесс называют также пакетным обучением (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 = [Conj I Conjs], где Conj и Conjs
формируются таким образом.
1. Собрать список Conj значений атрибутов, который охватывает хотя бы один
положительный пример класса Class и не охватывает ни одного примера
из любого другого класса.
2. Удалить из списка Examples все примеры, охваченные списком Conj, затем
распространить описание Conjs на все оставшиеся и не охваченные объекты.
