|
длина обучающей выборки I. Совокупную погрешность Е условно можно разбить на две составляющие: ошибку оценки (Я0Ц€нки) из-за конечного числа параметров классификатора и ошибку выборки (^выборки)» вызванную ее конечным размером. Погрешность классификатора Оценки зависит, как и следует ожидать, от аппроксимируемой функции и модели классификатора. При достаточно общих предположениях было доказано [23], что погрешность аппроксимации убывает как (АО, где ^ это «степень гладкости» аппроксимируемой функции, а й размерность вектора признаков, то есть количество признаков. Феномен замедления убывания погрешности при увеличении числа параметров при больших размерностях пространства признаков получил название «проклятия размерности» («сигзе о/ (НтепйопаШу»). Погрешность выборки ^выборки уменьшается при увеличении размеров выборки, но увеличивается с ростом сложности аппроксимируемой функции [24, 25]. Таким образом, при решении задачи распознавания приходится иметь дело с двумя противодействующими факторами погрешностью выборки и погрешностью классификатора. Правильный их баланс необходим для достижения минимальной погрешности аппроксимации при заданном размере обучающей выборки. Численные оценки этой проблемы показали [26], что в большинстве реальных ситуаций, когда размерность пространства признаков достаточно велика, имеет место ситуация существенной нехватки обучающих данных, т. е. приходится искать решение в условиях недостатка информации. На практике выбор оптимального количества параметров делается опытным путем, с помощью тестовой выборки. Классификатор, основанный на формуле Байеса Задачу распознавания можно сформулировать в общем виде как задачу выбора решающего правила, обеспечивающего минимальный риск. Задавшись совместным распределением Р{у»ь у) вектора признаков V и возможных классов изображения и>А, риск можно определить как математическое ожидание штрафа, связанного с данным решением: 32 |
информации для аппроксимации обычно используется обучающая выборка множество изображений, для которых известен правильный класс. «Обучением» классификатора называется процедура выбора параметров классификатора на основании обучающей выборки таким образом, чтобы впоследствии минимизировать риск неправильного решения. «Тестированием» классификатора называется проверка работы классификатора на «тестовой» выборке изображений. Необходимость в раздельных обучающей и тестовой выборках связана с эффектом, который называется в литературе «переобученностью» [20]. Задача классификатора состоит в аппроксимации апостериорной вероятности с минимальной погрешностью. При заданной модели классификатора имеется два параметра, влияющие на погрешность аппроксимации: число параметров классификатора М и длина обучающей выборки Ь. Совокупную погрешность Е можно (по крайней мере, гсоретически) разбить на две составляющие: ошибку выборки (Евыборки), вызванную ее конечным размером, и ошибку оценки (Еоцснки) из-за конечного числа параметров классификатора. Погрешность классификатора Еоцснки зависит, как и следует ожидать, от аппроксимируемой функции и модели классификатора. При достаточно общих предположениях было доказано [21], что погрешность аппроксимации убывает как (М 5,4*), где 5 это «степень гладкости» аппроксимируемой функции, а б размерность вектора признаков. Феномен замедления убывания погрешности при увеличении числа параметров при больших размерностях пространства признаков получил название «проклятия размерности» («сипе о/сИтегиюпаНгу»). Погрешность выборки Евыборки уменьшается при увеличении размеров выборки, но увеличивается с ростом сложности аппроксимируемой функции [22, 23]. Таким образом, при решении задачи распознавания приходится иметь дело с двумя противодействующими факторами погрешностью выборки и погрешностью классификатора; правильный их банане необходим для достижения минимальной погрешности аппроксимации при заданном размере обучающей выборки. Численные оценки этой проблемы показали [24], что в большинстве реальных ситуаций, когда размерность пространства признаков достаточно велика, имеет место ситуация существенной нехватки обучающих данных, т. е. приходится искать решение в условиях 16 недостаточной информации. На практике выбор оптимального количества параметров делается опытным путем, с помощью тестовой выборки. Классификатор, основанный на формуле Байеса Задачу распознавания можно сформулировать в общем виде как задачу выбора решающего правила, обеспечивающего минимальный риск. Задавшись совместным распределением Р(\ук, V) вектора признаков V и возможных классов изображения \ук, риск можно определить как математическое ожидание штрафа, связанного с данным решением: Я = Еу 2к С(\ук, д(у)) Р(\ук, у), (2.1) где матрица штрафов С(\ук, 6(у)) характеризует штраф при принятии решения б(у), если вектор признаков у на самом деле принадлежит классу \ук. В частном (но очень распространенном) случае оценкой качества работы классификатора является общее число совершенных ошибок. В этом случае матрица штрафов принимает упрощенный вид: С(\ук, 6(у)) = 0, в случае правильного решения, =1, в случае неправильного решения (2.2) Учитывая это, а также используя правило условной вероятности Р(х, у) = Р(ху) Р(у), уравнение (2.1) можно переписать следующим образом: К = Р(у) Ек С(чук, с!(у)) Р(%уку) = 1уР(у)[(1к [Р(луку)])-РЫу)] = ^Р(у )[1-РЫу )] (2.3) Из уравнения (3.3) следует, что для минимизации риска принятия неверного решения Я классификатор должен выбирать класс \\ц, который имеет максимальную апостериорную вероятность Р(^у). Это интуитивно понятное решение принято называть Байесовским классификатором (по имени хорошо известной формулы Байеса из теории вероятностей). Он фактически минимизирует среднее число ошибок, используя в качестве дискриминационной функции апостериорные вероятности классов. При всей привлекательности и простоте этого классификатора воспользоваться им на практике можно, к сожалению, только в простейших задачах, так как в подавляющем большинстве 17 |