5.4.3. Метод разбиения выборки.

Для того чтобы разбить имеющиеся объекты на обучающую и экзаменационную выборки изучим, как это разбиение влияет на дисперсию оценки вероятности ошибки.

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

где — истинная вероятность ошибки класса (см. выражение (5.131)).

С другой стороны, если имеется объектов для синтеза классификатора и бесконечное число экзаменационных объектов, то оценка вероятности ошибки выражается следующим образом:

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

Дисперсию оценки для плотности вероятности генеральной совокупности вычислить сложно. Однако в случае нормальных распределений объектов в классах с равными ковариационными матрицами интегралы в (5.142) можно преобразовать к одномерным интегралам

где определяются условными математическими ожиданиями:

Это преобразование основано на том, что для нормальных распределений с равными ковариационными матрицами байесовский классификатор — линейный, а распределение отношения правдоподобия также является нормальным распределением. Подобные выражения встречались в формулах (3.35) — (3.38).

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

где число объектов класса используемых для синтеза классификатора.

Математическое ожидание оценки было определено в работе [Окомото, 1963]. Так как выражение для этого математического ожидания достаточно громоздкое, то здесь приводится

наипростейший случай, когда

где — расстояние между двумя векторами математических ожиданий, определяемое по формуле

Величина является минимальной вероятностью ошибки байесовского классификатора. Так как — минимальное значение оценки то распределение для является причинным. Поэтому можно определить оценку дисперсии величины , основанную на ее математическом ожидании. Предположим, что плотность вероятности Де является плотностью вероятности гамма-распределения, которое включает в себя широкий класс причин распределений. Тогда

Математическое ожидание и дисперсия плотности (5.151) равны:

Исключая с, получим верхнюю границу дисперсии , т. е.

Таким образом, степень влияния числа обучающих объектов на оценку вероятности ошибки в случае нормальных распределений с равными ковариационными матрицами и равными риорными вероятностями равна

Величину из (5.155) следует сравнить с величиной которая характеризует влияние числа объектов в экзаменациовной выборке на оценку вероятности ошибки. Значение получается

подстановкой в формулу (5.141) значений

Величины из выражения (5.149) и из выражения (5.156) связаны однозначно. Поэтому можно установить зависимость между величиной в (5.155) с величиной в (5.156). Эта зависимость показана на рис. 5.3.

Из рис. 5.3 видно, что в значительной степени зависит размерности и степени разделимости классов, измеряемой расстоянием

Рис. 5.3. (см. скан) в зависимости от величины

Для любых фиксированных значений и числа объектов в обучающей и экзаменационной выборках можно оценить величины и с помощью формул (5.155), (5.156) и

рис. 5.3, Поскольку с ростом величина уменьшается не быстрее чем уменьшается не быстрее чем то для многих случаев большее число объектов должно быть использовано для экзамена, а не для проектирования классификатора.

Пример 5.7. Для распространения вышеприведенного результата на случай нормальных распределений с неравными ковариационными матрицами были проведены эксперименты для стандартных данных Размер обучающей выборки для каждого класса выбирался равным 12, 50, 100, 200 и 400 объектам Четыреста объектов каждого класса, которые генерировались независимо от объектов обучающей выборки, использовались для проверки качества классификатора. Для каждой выборки эксперимент повторялся 40 раз. По данным 40 экспериментов вычислялись выборочное среднее и среднеквадратичное отклонения оценки вероятности ошибки. Результаты приведены в табл. 5.1. Заметим, что эти результаты не противоречат

Таблица 5.1. Выборочный эксперимент для вычисления смещения и среднеквадратичного отклонения, обусловленных построением классификатора

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

Хайлиман показал, что если задача состоит в синтезе классификатора, обеспечивающего минимум дисперсии несмещенной оценки для ее решения требуется обучающая выборка относительно небольшого объема по сравнению с экзаменационной [Хайлиман, 1962]. Его метод годится для любых плотностей вероятности, но при весьма жестких ограничениях на вид оценки вероятности ошибки.

Исключение задания класса для объектов экзаменационной выборки.

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

Рассмотрим метод оценки вероятности ошибки, не требующий информации о принадлежности объектов экзаменационной выборки к конкретному классу [Чоу, 1970]. Применение этого метода наиболее эффективно в случае, когда при оптимальном разбиении выборки на обучающую и экзаменационную, число объектов в экзаменационной выборке больше, чем в обучающей.

Введем критическую область для задач классификации М классов:

где - плотность вероятности смеси, критический у ровень, Условие (5.157) устанавливает, что если для данного объекта X значения вычисленные для каждого класса М, не превышают величины то объект X не классифицируют вообще; в противном случае объект X классифицируют и относят его к классу. Таким образом, вся область значений X делится на критическую область и допустимую область причем размеры обеих областей являются функциями критического уровня

При таком решающем правиле вероятность ошибки коэффициент отклонения и коэффициент правильного распознавания будут равны

и

Предположим, что область отклонения увеличивается на за счет изменения значения на Тогда те X, которые раньше распознавались правильно, теперь отклоняются:

Интегрируя (5.161) в пределах области получим

где — приращения вызванные изменением формулы (5.160) следует, что неравенство (5.162) можно переписать следующим образом:

Суммируя по всем дискретным значениям от 0 до , получим

Полагая получаем интеграл Стилтьеса

Уравнение (5.165) показывает, что вероятность ошибки может быть вычислена после того, как известна зависимость между значениями и Из решающего правила (5.157) следует, что при область отклонения отсутствует, так что байесовская ошибка Кроме того, из формулы (5.165) можно установить взаимосвязь между вероятностью ошибки и коэффициентом отклонения, так как изменение вероятности ошибки можно вычислить как функцию от изменения коэффициента отклонения.

Рис. 5.4. Приращение областей отклонения.

Воспользуемся выражением (5.165) для исключения задания класса объектов экзаменационной выборки. Для этого поступим следующим образом.

1. Для определения при где — дискретный шаг переменной будем использовать относительно дорогостоящие классифицируемые объекты. Это показано на рис. 5.4.

2. Подсчитаем число неклассифицированных объектов экзаменационной выборки, которые попали в область разделим это число на общее число объектов и обозначим полученное отношение через

3. Тогда из выражения (5.165) следует, что оценка вероятности ошибки

В описанной процедуре использовалось то, что коэффициент отклонения является функцией от плотности вероятности смеси, а не от плотностей вероятности отдельных классов. Поэтому после того, как по классифицированным объектам найдены расширенные области отклонения, в дальнейшем для оценивания и вероятности ошибки нет необходимости использовать классифицированные объекты.