Алгоритм исключения кандидатов находит все гипотезы, соответствующие всем заданным обучающим примерам. В отличие от алгоритма Find-S и алгоритма List-then-Eliminate, он анализирует как отрицательные, так и положительные примеры, исключая любую несовместимую гипотезу.

Давайте теперь посмотрим на некоторую терминологию, которую мы будем использовать позже.

? -› принимает все

Ø -› отвергает все

Рассмотрим гипотезу с 6 ограничениями

h1 = ‹правда, ?, ложь,?,?,?›

h2 = ‹правда,?,?,?,?,?›

Здесь h2 более общий, чем h1. т. е. h1 специфичнее, чем h2. Так как h2 принимает все примеры с истинным в первой позиции, а h1 будет принимать только примеры с первым истинным и третьим ложным. все примеры, удовлетворяющие h1, будут верны для h2, но не наоборот, поэтому h1 является конкретной гипотезой для h2.

как правило, наиболее конкретной гипотезой будет ‹ Ø, Ø, Ø, Ø, Ø, Ø›, а наиболее общей гипотезой будет ‹ ?, ?, ?, ?, ?, ?›, поскольку первая отклонит все, а вторая будет принимать все образцы.

АЛГОРИТМ:

Шаг 1. Инициализируйте G максимально общейгипотезой в H. (G = ‹ ?, ?, ?, ?, ?, ?›)

Шаг 2. Инициализируйте S максимально конкретной гипотезой в H. (S = ‹ Ø, Ø, Ø, Ø, Ø, Ø›)

Шаг 3: Для каждой обучающей выборки «d» выполните:

→if d is +ve:

  • удалить из G любую гипотезу, несовместимую с d.
  • для каждой гипотезы «s» из S, которая не согласуется с d:

— — — Удалить s из S

— — — Добавьте к S все минимальные обобщения h s такие, что: h совместимо с d, и некоторый член G более общий, чем h

— — — удалить из S любую гипотезу, которая является более общей, чем другая гипотеза в S.

→if d is -ve:

  • удалить из S любую гипотезу, несовместимую с d.
  • для каждой гипотезы «g» в G, несовместимой с d:

— — — Удалить g из G

— — — Добавьте к G все минимальные специализации h группы g такие, что: h согласуется с d, а некоторый член S более специфичен, чем h

— — — удалить из G любую гипотезу, которая является менее общей, чем другая гипотеза в G.

Чтобы лучше понять, давайте рассмотрим пример:

Этот пример имеет двоичное значение, каждое значение позиции будет содержать только два значения.

  1. ‹солнечно, тепло, нормально, сильно, тепло, одинаково› = да(+ve)
  2. ‹солнечный, теплый, высокий, сильный, теплый, такой же› = yes(+ve)
  3. ‹дождливый, холодный, высокий, сильный, теплый, переменный› = no(-ve)
  4. ‹солнечный, теплый, высокий, сильный, прохладный, переменный› = yes(+ve)

Первоначально S0=‹ Ø, Ø, Ø, Ø, Ø, Ø› G0=‹?, ?, ?, ?, ?, ?›

после 1-го образца: ‹солнечно, тепло, нормально, сильно, тепло, то же› = да(+ve)

S1 = ‹солнечно, тепло, нормально, сильно, тепло, одинаково› (S0 отвергает все, но здесь у нас есть гипотеза, которая принимает определенный пример, поэтому измените S0)

G1 = G0 (в G0 нет противоречивой гипотезы, поэтому она остается прежней)

после 2-го образца: ‹солнечно, тепло, высоко, сильно, тепло, то же› = да(+ve)

S2 = ‹солнечно, тепло, ?, сильно, тепло, то же самое›(третье значение отличается в гипотезе и текущей выборке, поэтому измените его на какое-то общее значение, т.е. будет результат будет да. так что измените его, чтобы принять все)

G2 = G1 (без изменений)

после 3-го образца: ‹дождь, холод, высокая, сильная, теплая, перемена› = нет(-ve)

S3 = S2 (без изменений, поскольку выборка отрицательна и в S2 не обнаружено противоречивых данных)

G3 = ‹солнечно,?,?,?,?,?› ‹?,тепло,?,?,?,?›‹?,?,?,?,?,то же› ‹солнечно,тепло,? ,?,?,?› ‹солнечный,?,?,?,?,тот же› ‹солнечный, теплый, ?, сильный,?,?› ‹солнечный, ?,?,сильный,?,?› ‹?,теплый ,?,strong,?,?› (G3 принимает все, поэтому теперь он принимает и отрицательную выборку, которая несовместима. Итак, теперь мы удаляем существующую гипотезу и заменяем ее более общей гипотезой, которая не образует несоответствия с актуальный образец)

после 4-го образца: ‹солнечно, тепло, высоко, сильно, прохладно, перемена› = да(+ve)

S4 = ‹солнечно, тепло, ?, сильно,?,?› (замените 5-е и 6-е значения на acceptAll, поскольку не имеет значения, какое значение находится в этих позициях)

G4 = ‹солнечно,?,?,?,?,?› ‹?,тепло,?,?,?,?› ‹солнечно,тепло,?,?,?,?› ‹солнечно,?,? ,сильный,?,?› ‹?,теплый,?,сильный,?,?››(поскольку значение изменилось для 6-й позиции, мы удаляем гипотезу, которая содержит «то же самое» на 6-й позиции И гипотезу ‹солнечный , теплый, ?, сильный,?,?› такой же, как S4, поэтому мы удаляем и эту гипотезу)

Последняя, ​​приемлемая гипотеза — это объединение гипотез S4 и G4.

Теперь давайте узнаем результат для данных образцов на основе приведенных выше гипотез:

A. ‹солнечный, теплый, нормальный, сильный, прохладный, переменный›

B. ‹Дождь, холодно, нормально, светло, тепло, то же самое›

C. ‹солнечно, тепло, нормально, светло, тепло, то же›

D. ‹солнечный, холодный, нормальный, сильный, теплый, такой же›

A. ДА (положительный пример)

B. НЕТ (отрицательный экземпляр)

К. не может решить. так как 3 гипотезы верны, а 3 гипотезы нет. нам нужно больше образцов, чтобы сказать, является ли это положительным или отрицательным экземпляром.

D. больше склоняется к отрицательному, но все еще не может сказать, так как 4 говорят отрицательно, а 2 говорят иначе.

Спасибо, удачного обучения!

Ссылки: Том М. Митчелл, Машинное обучение,Mc Graw Hill, 1997 г.