Для того чтобы перевести эти предположения на практическую почву, необходимо ввести некоторые описанные ниже обозначения.

•    Обозначим символом х множество всех возможных примеров.

•    Обозначим символом D распределение, из которого извлекаются примеры.

•    Обозначим символом Η множество возможных гипотез.

•    Обозначим символом N количество примеров в обучающем множестве.

Первоначально будем предполагать, что истинная функция f является элементом множества н. Теперь можно определить ошибку гипотезы h применительно к истинной функции f, если дано распределение вероятностей D по примерам, описывающее вероятность того, что гипотеза h отлична от функции f на некотором примере:

Это — такое же количество, которое измерялось экспериментально с помощью кривых обучения, описанных выше в данной главе.

Гипотеза h называется приблизительно правильной, если error (h) <ε, где ε — небольшая константа. Примем к действию план решения этой проблемы, который состоит в том, чтобы доказать, что после просмотра N примеров все совместимые гипотезы с высокой вероятностью станут приблизительно правильными. Приблизительно правильная гипотеза может рассматриваться как "близкая" к истинной функции в пространстве гипотез: она находится внутри так называемого ε-шара, который окружает истинную функцию f. На рис. 18.9 показано множество всех гипотез Н, которое подразделяется на ε-шар, окружающий функцию f, и все остальные гипотезы, принадлежащие к множеству, которое мы будем называть

Вероятность того, что гипотеза, содержащая "серьезную ошибку", будет согласована с первыми N примерами, можно вычислить следующим образом. Известно, что. В таком случае вероятность того, что эта гипотеза согласуется с заданным примером, равна по меньшей мере l-ε. Граничное значение этой вероятности для N примеров равно:

Рис. 18.9. Схематическое изображение пространства гипотез, на котором показан ε-шар, окружающий истинную функцию f