Минимальное количество обучающих примеров для алгоритмов поиска Find-S / Candidate? - PullRequest
Новая
       11

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

2 голосов
/ 03 мая 2010

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

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

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

Заранее спасибо.

Ответы [ 2 ]

2 голосов
/ 15 декабря 2014

Вам нужно два положительных примера: (2,6) (2 <= x <= 2, 6 <= y <= 6) а затем (4,9) (2 <= x <= 4, 6 <= y <= 9) То есть набор S сделан, и это конец ответа на обучение / изучение с помощью FIND-S </p>

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

  • G начинается как (-Inf <= x <= Inf, -Inf <= y <= Inf) </li> * +1007 *

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

    • (- Inf <= x <= Inf, 6 <= y <= Inf) </li>

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

    • (- Inf <= x <= Inf, 6 <= y <= 9) </li>

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

    • (2 <= x <= Inf, 6 <= y <= 9) </li>

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

    • (2 <= x <= 4, 6 <= y <= 9) </li>

    Итак, теперь S = G = {(2 <= x <= 4, 6 <= y <= 9)}. Поскольку S = G, он отлично изучил концепцию. Я видел этот вопрос в разных форматах. Замените -Inf на 0, а Inf на 10, если он указывает проблемный домен как таковой. </p>

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

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

0 голосов
/ 04 февраля 2011

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

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

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

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

...