Перебор с возвратами возникает из-за того, что в подходе, предусматривающем поиск текущей наилучшей гипотезы, приходится выбирать конкретную гипотезу как наилучшее текущее предположение, даже несмотря на то, что еще отсутствует достаточный объем данных, позволяющий убедиться в правильности этого выбора. Вместо этого можно было бы просто "держать под рукой" те и только те гипотезы, которые являются совместимыми со всеми поступившими до сих пор данными. В таком случае каждый новый экземпляр данных либо не оказывает никакого влияния на состав гипотез, либо позволяет избавиться от некоторых гипотез. Напомним, что первоначальное пространство гипотез может рассматриваться как следующее дизъюнктивное высказывание:

По мере обнаружения того, что различные гипотезы являются несовместимыми с примерами, эта дизъюнкция сужается и остаются только те гипотезы, которые еще не исключены. Это означает, что при условии, что первоначальное пространство гипотез действительно содержит правильный ответ, этот правильный ответ должен также содержаться в сокращенной дизъюнкции, поскольку были удалены только неправильные гипотезы. Множество оставшихся гипотез называется пространством версий, а соответствующий алгоритм обучения (приведенный в листинге 19.2) называется алгоритмом обучения в пространстве версий (а также алгоритмом удаления потенциальных гипотез).

Листинг 19.2. Алгоритм обучения в пространстве версий. Он находит подмножество гипотез V, совместимое с примерами examples

Одним важным свойством этого алгоритма является то, что он инкрементный, — при его использовании никогда не приходится возвращаться и повторно исследовать старые примеры, поскольку в любом случае гарантируется, что оставшиеся гипотезы остаются совместимыми с ними. Этот алгоритм также представляет собой алгоритм поиска с наименьшим вкладом, поскольку в нем не используются произвольные варианты выбора (сравните его с алгоритмом планирования с частичным упорядочением, который приведен в главе 11). Но при использовании этого алгоритма возникает одна очевидная проблема. Как уже было сказано, пространство гипотез часто имеет огромные размеры; как же в таком случае можно записать соответствующую ему огромную дизъюнкцию?