Алгоритм ликвидации кандидата

Рассмотрим следующие обучающие наборы данных.

+-------+-------+----------+-------------+
| Size  | Color | Shape    | Class/Label |
+=======+=======+==========+=============+
| big   | red   | circle   | No          |
| small | red   | triangle | No          |
| small | red   | circle   | Yes         |
| big   | blue  | circle   | No          |
| small | blue  | circle   | Yes         |
+-------+-------+----------+-------------+

Я хотел бы понять, как работает алгоритм, когда он начинается с отрицательного примера и когда два отрицательных примера объединяются.

Это не вопрос заданий, кстати.

Примеры с другими наборами данных также приветствуются! Это нужно понять отрицательную часть алгоритма.

Ответ 1

Для вашего пространства гипотез (H) вы начинаете с своих наборов максимально общих (G) и максимально специфических (S) гипотез:

G0 = {<?, ?, ?>}
S0 = {<0, 0, 0>}

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

Итак, для вашего первого (отрицательного) примера, (big, red, circle), минимальные специализации сделают новое пространство гипотезы

G1 = {<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>}
S1 = S0 = {<0, 0, 0>}

Обратите внимание, что S не изменилось. Для вашего следующего примера (small, red, triangle), который также является отрицательным, вам нужно будет дополнительно специализировать G. Обратите внимание, что вторая гипотеза в G1 не соответствует новому наблюдению, поэтому только первая и третья гипотезы в G1 должны быть специализированными. Это даст

G2 = {<small, blue, ?>, <small, ?, circle>, <?, blue, ?>, <big, ?, triangle>, <?, blue, triangle>}

Однако, поскольку первая и последняя гипотезы в G2 выше являются специализациями средней гипотезы (<?, blue, ?>), мы бросаем эти два, давая

G2 = {<small, ?, circle>, <?, blue, ?>, <big, ?, triangle>}
S2 = S1 = S0 = {<0, 0, 0>}

Для положительного наблюдения (small, red, circle) вы должны обобщить S и удалить что-либо в G, которое является непоследовательным, что дает

G3 = {<small, ?, circle>}
S3 = {<small, red, circle>}

(big, blue, circle) - следующий отрицательный пример. Но поскольку он не согласуется с G, нечего делать

G4 = G3 = {<small, ?, circle>}
S4 = S3 = {<small, red, circle>}

Наконец, у вас есть положительный пример (small, blue, circle), который требует от вас обобщения S, чтобы он соответствовал этому примеру, предоставляя

G5 = {<small, ?, circle>}
S5 = {<small, ?, circle>}

Так как G и S равны, вы поняли понятие "маленькие круги".