Минимальное количество обучающих примеров для алгоритмов поиска / исключения кандидатов?


Рассмотрим пространство экземпляров, состоящее из целых точек в плоскости x, y, где 0 ≤ x, y ≤ 10, и множество гипотез, состоящее из прямоугольников (т. е. имеющих вид (a ≤ x ≤ b, c ≤ y ≤ d), где 0 ≤ a, b, c, d ≤ 10).

Какое наименьшее число обучающих примеров необходимо предоставить, чтобы алгоритм Find-S идеально изучил конкретную целевую концепцию (например, (2 ≤ x ≤ 4, 6 ≤ y ≤ 9))? Когда мы можем сказать, что целевая концепция точно изучена в случае Алгоритм поиска-S, и какова оптимальная стратегия запроса?

Я также хотел бы знать ответ w.r. T исключение кандидата.

Заранее благодарю.

2   2   2010-05-03 03:26:31

2 ответа:

Вам нужны два положительных примера: (2,6) (2

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

  • г начинается (-инф

Добавьте (3,5) - и мы получим гипотеза:

  • (- Inf

Добавить (3,10) -

  • (- Inf

Добавить (1,7) -

  • (2

Добавить (5,7) -

  • (2

Итак, теперь S=G={(2

Это оптимальный порядок подачи в обучающих примерах. Худший порядок - сначала выполнить набор G, так как вы создадите четыре различных гипотезы-кандидата, которые сольются в три со вторым примером, а затем сольются в один с третьим примером. Полезно проиллюстрировать C-E деревом, как в книге Митчелла, и, возможно, набросать график гипотезы рядом с каждым.

Этот ответ подтверждается здесь: http://ssdi.di.fct.unl.pt/scl/docs/exercises/Clemens%20Dubslaff%20hm4.pdf

Предполагая, что все диапазоны a ≤ x ≤ b и a и b целочисленны...

В 1-мерном случае (только x) было бы 4 образца, (a-1,a,b,b+1), которые доказали бы это.

Если вы расширите это до 2 измерений (x и y), это должно быть 16 образцов, которые являются теми,которые выше как x,и (c-1,c, d, d+1) для y, со всеми возможными комбинациями.

Пожалуйста, поправьте меня, если я не понимаю проблемы.