В основе метода поиска текущей наилучшей гипотезы лежит подход, предусматривающий сопровождение единственной гипотезы и ее корректировку по мере поступления новых примеров в целях поддержки совместимости. Основной алгоритм этого метода был впервые описан Джоном Стюартом Миллом [1049], но вполне мог быть изобретен еще раньше.

Предположим, что в нашем распоряжении имеется определенная гипотеза, скажем, которая нас полностью устраивает. До тех пор пока каждый новый пример остается с ней совместимым, не нужно ничего делать. Наконец, вслед за ними поступает ложно отрицательный пример,. Что теперь следует делать? На рис. 19.1, а гипотезапоказана схематически в виде области; все, что находится внутри прямоугольника, входит в состав расширения. Примеры, которые фактически встретились до сих пор, показаны как " + " или "-", и рисунок наглядно демонстрирует, что гипотезаправильно классифицирует все примеры как положительные или отрицательные примеры предиката willWait. Показанный на рис. 19.1, б новый пример (обозначенный кружком) является ложно отрицательным — в гипотезе утверждается, что он должен быть отрицательным, но фактически этот пример положителен. Расширение гипотезы должно быть увеличено с целью его включения. Такая операция называется обобщением; одно из возможных обобщений показано на рис. 19.1, в. После этого на рис. 19.1, г показан ложно положительный пример — в гипотезе утверждается, что новый пример (обозначенный кружком) должен быть положительным, но фактически этот пример отрицателен. Расширение гипотезы должно быть уменьшено в целях исключения данного примера. Такая операция называется уточнением; на рис. 19.1, д показано одно из возможных уточнений данной гипотезы. Отношения "более общий чем" и "более конкретный чем" между гипотезами позволяют создать пространство гипотез с такой логической структурой, которая дает возможность осуществлять эффективный поиск.

Рис. 19.1. Операции уточнения и обобщения: совместимая гипотеза (а); ложно отрицательный пример (б); гипотеза обобщена (в); ложно положительный пример (г); гипотеза уточнена (д)