Поиск текущей наилучшей гипотезы
В основе метода поиска .текущей наилучшей гипотезы лежит подход, предусматривающий сопровождение единственной гипотезы и ее корректировку по мере поступления новых примеров в целях поддержки совместимости. Основной алгоритм этого метода был впервые описан Джоном Стюартом Миллом [1049], но вполне мог быть изобретен еще раньше.
Предположим, что в нашем распоряжении имеется определенная гипотеза, скажем Яг, которая нас полностью устраивает. До тех пор пока каждый новый пример остается с ней совместимым, не нужно ничего делать. Наконец, вслед за ними поступает ложно отрицательный пример, Х13. Что теперь следует делать? На рис. 19.1, « гипотеза яг показана схематически в виде области; все, что находится внутри прямоугольника, входит в состав расширения Яг. Примеры, которые фактически встретились до сих пор, показаны как " + " или "-", и рисунок наглядно демонстрирует, что гипотеза яг правильно классифицирует все примеры как положительные или отрицательные примеры предиката willWai t. Показанный на рис. 19.1, б новый пример (обозначенный кружком) является ложно отрицательным — в гипотезе утверждается, что он должен быть отрицательным, но фактически этот пример положителен. Расширение гипотезы должно быть увеличено с целью его включения. Такая операция называется обобщением; одно из возможных обобщений показано на рис. 19.1,0. После этого на рис. 19.1, г показан ложно положительный пример — в гипотезе утверждается, что новый пример (обозначенный кружком) должен быть положительным, но фактически этот пример отрицателен. Расширение гипотезы должно быть уменьшено в целях исключения данного примера. Такая операция называется уточнением; на рис. 19.1, д показано одно из возможных уточнений данной гипотезы. Отношения "более общий чем" и "более конкретный чем" между гипотезами позволяют создать пространство гипотез с такой логической структурой, которая дает возможность осуществлять эффективный поиск.
Теперь можно определить алгоритм Current-Best-Learning, приведенный в листинге 19.1. Обратите внимание на то, что каждый раз при рассмотрении возможности обобщения или уточнения гипотезы необходимо проверять согласованность этих операций с другими примерами, поскольку произвольное увеличение/уменьшение расширения может привести к включению/исключению рассматривавшихся ранее отрицательных/положительных примеров.
Листинг 19.1. Алгоритм обучения по методу поиска текущей наилучшей гипотезы. Он осуществляет поиск совместимой гипотезы и выполняет возврат, если не удается найти какое-либо совместимое уточнение/обобщение
function Current-Best-Learning(examples) returns гипотеза
Я <— любая гипотеза, совместимая с первым примером в множестве
примеров examples for each из оставшихся примеров в множестве examples do if пример е является ложно положительным применительно к Я then
Я <— выбрать уточнение Я, совместимое с примерами examples else if пример е является ложно положительным применительно к Я then Я <— выбрать обобщение Я, совместимое с примерами examples if не удается найти какое-либо совместимое
уточнение/обобщение then неудачное завершение поиска
return Я
Выше в данном разделе обобщение и уточнение были определены как операции, модифицирующие расширение гипотезы. Теперь необходимо точно определить, как эти операции могут быть реализованы в виде синтаксических операций, которые вносят изменения в потенциальное определение, связанное с гипотезой, чтобы эти операции можно было выполнять с помощью какой-то программы. Прежде чем приступить к решению этой задачи, необходимо отметить, что обобщение и уточнение также представляют собой логические связи между гипотезами. Если гипотеза я2 с определением Ci является обобщением гипотезы н2 с определением с2, то должно иметь место следующее выражение: