Главная arrow книги arrow Копия Глава 18. Обучение на основе наблюдений arrow Оценка количества необходимых примеров
Оценка количества необходимых примеров

Вероятность того, что множествосодержит по меньшей мере одну совместимую гипотезу, ограничивается суммой отдельных вероятностей:

где учитывался тот факт, что. Желательно уменьшить вероятность этого события так, чтобы она не превышала некоторого небольшого числа δ:

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

(18.1)

Таким образом, если обучающий алгоритм возвратит гипотезу, совместимую с этим или большим количеством примеров, то с вероятностью, по меньшей мере равной l-δ, он будет иметь, самое большее, ошибку ε. Иными словами, полученная гипотеза будет по всей вероятности приблизительно правильной. Количество требуемых примеров, зависящее от ε и δ, называется выборочной сложностью (sample complexity) пространства гипотез.

Поэтому создается впечатление, что основной вопрос сводится к определению размера пространства гипотез. Как было показано выше, если Η — множество всех булевых функций от η атрибутов, то. Таким образом, выборочная сложность пространства растет в зависимости от. Поскольку количество возможных примеров также равно, на этом основании можно утверждать, что любой обучающий алгоритм для пространства всех булевых функций не может функционировать лучше, чем поисковая таблица, если он просто возвращает гипотезу, совместимую со всеми известными примерами. Еще один способ убедиться в справедливости этого утверждения может быть основан на том наблюдении, что для любого не встречавшегося ранее примера пространство гипотез будет содержать столько же совместимых гипотез, которые предсказывают положительный результат, сколько имеется гипотез, предсказывающих отрицательный результат.

Поэтому дилемма, с которой мы сталкиваемся, состоит в следующем: если пространство функций, которые могут рассматриваться алгоритмом, останется неограниченным, то алгоритм не будет способен к обучению, но, с другой стороны, ограничение пространства может привести к полному удалению истинной функции. Существуют два способа "разрешения" этой дилеммы. Первый способ состоит в соблюдении требования, чтобы алгоритм возвращал не просто любую совместимую гипотезу, а преимущественно наиболее простую гипотезу (что и предусмотрено в обучении деревьев решений). Теоретический анализ подобных алгоритмов выходит за рамки данной книги, но в тех случаях, когда задача поиска простых совместимых гипотез является легко разрешимой, результаты определения выборочной сложности обычно бывают лучше по сравнению с результатами анализа, основанными только на определении совместимости. Второй способ разрешения дилеммы, который рассматривается ниже, состоит в том, что нужно сосредоточиться на тех подмножествах всего множества булевых функций, которые доступны для обучения. Идея этого способа состоит в том, что в большинстве случаев не требуется полная выразительная мощь булевых функций и можно ограничиться использованием более простых языков. В следующем разделе один из таких ограниченных языков рассматривается более подробно.