Оценка количества необходимых примеров

Для того чтобы перевести эти предположения на практическую почву, необходимо ввести некоторые описанные ниже обозначения.
• Обозначим символом х множество всех возможных примеров.
• Обозначим символом D распределение, из которого извлекаются примеры.
• Обозначим символом Н множество возможных гипотез.
• Обозначим символом iV количество примеров в обучающем множестве.
Первоначально будем предполагать, что истинная функция f является элементом множества н. Теперь можно определить ошибку гипотезы h применительно к истинной функции f, если дано распределение вероятностей D по примерам, описывающее вероятность того, что гипотеза h отлична от функции f на некотором примере:
error(h) = P(h(х)Ф?(х)|х извлечен из D)
Это — такое же количество, которое измерялось экспериментально с помощью кривых обучения, описанных выше в данной главе.
Гипотеза h называется приблизительно правильной, если error (h) <е, где е — небольшая константа. Примем к действию план решения этой проблемы, который состоит в том, чтобы доказать, что после просмотра iV примеров все совместимые гипотезы с высокой вероятностью станут приблизительно правильными. Приблизительно правильная гипотеза может рассматриваться как "близкая" к истинной функции в пространстве гипотез: она находится внутри так называемого е-шара, который окружает истинную функцию f. На рис. 18.9 показано множество всех гипотез Н, которое подразделяется на е-шар, окружающий функцию f, и все остальные гипотезы, принадлежащие к множеству, которое мы будем называть Hbad.
Вероятность того, что гипотеза hbGHbad, содержащая "серьезную ошибку", будет согласована с первыми N примерами, можно вычислить следующим образом. Известно, что error (hb) >е. В таком случае вероятность того, что эта гипотеза согласуется с заданным примером, равна по меньшей мере 1-е. Граничное значение этой вероятности для N примеров равно:
Р(пъ согласует - с N примерами) < (l-e)N
Вероятность того, что множество Hbad содержит по меньшей мере одну совместимую гипотезу, ограничивается суммой отдельных вероятностей:
?P(Hbad содержит совместимую гипотезу) < |Hbad| (1-е)N < |н| (1-Ј)N
где учитывался тот факт, что | Hbad | < | н |. Желательно уменьшить вероятность этого события так, чтобы она не превышала некоторого небольшого числа 8:
|Н|(1-8)N < 5
С учетом того, что 1-е<е"е, такой цели можно добиться, предоставив алгоритму возможность обработать следующее количество примеров:
N > -(In - + In |Н|) (18.1)
Таким образом, если обучающий алгоритм возвратит гипотезу, совместимую с этим или большим количеством примеров, то с вероятностью, по меньшей мере равной 1-8, он будет иметь, самое большее, ошибку е. Иными словами, полученная гипотеза будет по всей вероятности приблизительно правильной. Количество требуемых примеров, зависящее от е и 8, называется выборочной сложностью (sample complexity) пространства гипотез.
Поэтому создается впечатление, что основной вопрос сводится к определению размера пространства гипотез. Как было показано выше, если н — множество всех булевых функций от п атрибутов, то |н|=22 . Таким образом, выборочная сложность пространства растет в зависимости от 2П. Поскольку количество возможных примеров также равно 2П, на этом основании можно утверждать, что любой обучающий алгоритм для пространства всех булевых функций не может функционировать лучше, чем поисковая таблица, если он просто возвращает гипотезу, совместимую со всеми известными примерами. Еще один способ убедиться в справедливости этого утверждения может быть основан на том наблюдении, что для любого не встречавшегося ранее примера пространство гипотез будет содержать столько же совместимых гипотез, которые предсказывают положительный результат, сколько имеется гипотез, предсказывающих отрицательный результат.
Поэтому дилемма, с которой мы сталкиваемся, состоит в следующем: если пространство функций, которые могут рассматриваться алгоритмом, останется неограниченным, то алгоритм не будет способен к обучению, но, с другой стороны, ограничение пространства может привести к полному удалению истинной функции. Существуют два способа "разрешения" этой дилеммы. Первый способ состоит в соблюдении требования, чтобы алгоритм возвращал не просто любую совместимую гипотезу, а преимущественно наиболее простую гипотезу (что и предусмотрено в обучении деревьев решений). Теоретический анализ подобных алгоритмов выходит за рамки данной книги, но в тех случаях, когда задача поиска простых совместимых гипотез является легко разрешимой, результаты определения выборочной сложности обычно бывают лучше по сравнению с результатами анализа, основанными только на определении совместимости. Второй способ разрешения дилеммы, который рассматривается ниже, состоит в том, что нужно сосредоточиться на тех подмножествах всего множества булевых функций, которые доступны для обучения. Идея этого способа состоит в том, что в большинстве случаев не требуется полная выразительная мощь булевых функций и можно ограничиться использованием более простых языков. В следующем разделе один из таких ограниченных языков рассматривается более подробно.







Материалы

Яндекс.Метрика