Текущий поиск лучшей гипотезы

Идея текущего поиска наилучшей гипотезы состоит в том, чтобы поддерживать одну гипотезу и корректировать ее по мере появления нового примера, чтобы сохранить согласованность.

Пространство гипотез H представляет собой набор гипотез, которые алгоритм обучения предназначен для рассмотрения. Алгоритм обучения считает, что одна гипотеза верна, то есть верит предложению:

h1 V h2  V h3 V.... V hn

Гипотеза, не согласующаяся с примером, может быть исключена.

Есть два возможных способа быть несовместимым с примером:

1. Ложноотрицательный: в этой гипотезе пример должен быть отрицательным, но на самом деле он положительный.
2. Ложноположительный: в этом типе гипотезы пример должен быть положительным, но на самом деле он отрицательный.

если пример согласуется с гипотезой, то не меняйте его. Если пример ложноотрицательный, обобщите гипотезу, а если пример ложноположительный, то конкретизируйте гипотезу.

function CURRENT-BEST-LEARNING(examples) return a hypothesis
H<- any hypothesis consistent with the first example in examples
for each remaining example in examples do 
    if e is a false positive for H then
        H<- choose a specialization of H is consistent with examples
    else if e is a false negative for H then
        H<- choose a generalization of H is consistent with examples
    if no consistent specialization/generalization can be found 
    then fail
    return H

Текущий алгоритм обучения наилучшей гипотезы ищет непротиворечивую гипотезу и отменяет алгоритм, когда решение не найдено.

Обратите внимание, что каждый раз, когда мы думаем об обобщении или конкретизации гипотезы, мы должны проверять ее на согласованность с другими примерами, потому что произвольное увеличение или уменьшение расширения может включать или исключать ранее увиденные отрицательные или положительные примеры.

Обобщение и специализация определяются как операции, изменяющие расширение гипотезы.

Текущий алгоритм наилучшей гипотезы и его варианты использовались во многих обучающих системах.

Недостатки:

1. проверка всех предыдущих экземпляров заново для каждой модификации очень затратна.
2. процесс поиска может включать в себя большое количество возвратов. Пространство гипотез может быть вдвойне экспоненциально большим местом.

Отношения «более общее чем» и «более конкретное чем» между гипотезами обеспечивают логическую структуру в пространстве гипотез, что делает возможным эффективный поиск.