3.8.4. УРОВЕНЬ ОШИБКИ, УСРЕДНЕННЫЙ ПО ЗАДАЧАМ

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

Чтобы исследовать это теоретически, требуется выполнить следующие действия:

1)   произвести оценку неизвестных параметров по выборкам;

2)   применить эти оценки для определения классификатора;

3)   вычислить уровень ошибки полученного классификатора.

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

Рассмотрим случай с двумя классами, предполагаемыми равновероятными. Предположим, что пространство признаков мы разбили на некоторое число т отдельных ячеек . . ., Если в пределах каждой из ячеек условные плотности р(х|(Оі) и p(x|(Og) заметно не изменяются, то вместо того, чтобы отыскивать точное значение X, потребуется лишь определить, в какую из ячеек попадает X. Это упрощает задачу, сводя ее к дискретной. Пусть Рі~Р{х£^і\<Лі) и 9і = Р(х€ Тогда, поскольку мы предположили, что Р((Оі) = =Р((0а)==1/2, векторы р= (рі, . . pj* и q= (qi, . . ., определят вероятностную структуру задачи. Если х попадает в if,-, то байесовское решающее правило выразится в принятии решения (Лі, если Рі>ді. Получаемый байесовский уровень ошибки определится выражением

Если параметры р и q неизвестны и должны быть оценены по множеству выборок, то получаем уровень ошибки, больший, чем байесовский. Точный ответ будет зависеть от взятого множества выборок и способа построения по ним классификатора. Допустим, что одна половина выборок помечена Юі, а другая Og, причем titj представляет число выборок с пометкой ю;, попавших в ячейку Допустим далее, что мы строим классификатор, пользуясь оценками по максимуму правдоподобия Рі=2пц/п и ді=2пцІп, как если бы они и были истинными значениями. Тогда новый вектор признаков, попадающий в будет отнесен к Фі, если щощг- Со всеми этими предположениями вероятность ошибки для получаемого классификатора определится выражением

Чтобы оценить вероятность ошибки, надо знать истинные значения условных вероятностей р и q и множество выборок или по меньшей мере числа ntj. Различные множества из п случайных выборок приведут к различным значениям Р(е|р, q, SC).

Для усреднения п случайных выборок по всем возможным множествам и получения средней вероятности ошибки Р(е|р, q, Ж) можно использовать тот факт, что числа ntj распределены по полиномиальному закону. Грубо говоря, это даст типичный уровень ошибки, который можно ожидать для п выборок. Однако оценка этого среднего уровня потребует еще решения второстепенной задачи — оценки величин р и q. Если р и q различаются сильно, то средний уровень ошибки будет близок к нулю; при сходных р и q он приближается к 1/2.

Радикальным путем устранения этой зависимости решения от задачи будет усреднение результатов решения всех возможных задач. Для этого следует выбрать некоторое априорное распределение неизвестных параметров р и q, а затем усреднить Р(е|р, q, п) в соответствии с этими р и q. Получаемая усредненная по задачам вероятность ошибки Р(е\т, п) будет зависеть только от числа т ячеек, числа п выборок и вида априорного распределения.

Выбор априорного распределения является, несомненно, тонким моментом. Стараясь облегчить задачу, мы можем принять величину Р близкой к 0, а стараясь ее усложнить — близкой к 1/2. Априорное распределение следовало бы выбирать соответствующим тому классу задач, с которым мы обычно встречаемся, однако не ясно, как это сделать. Можно просто предположить эти задачи «равномерно распределенными», т. е. предположить, что векторы р и q

т

распределены равномерно на симплексах рі^0, 2рг=1,

т    і=1

^)<7*=1. Г. Ф. Хугсом, предположившим такой подход, проведены необходимые вычисления, результаты которых представлены графиками рис. 3.5. Рассмотрим некоторые приложения его результатов.

Заметим сначала, что эти кривые представляют Р как функцию числа ячеек для постоянного числа выборок. Если число выборок бесконечно, то становятся верны оценки по максимуму правдоподобия, и Р для любой задачи будет средним значением байесовского уровня ошибки. Кривая, соответствующая Р(е\т, оо), быстро убывает от 0,5 при т= 1 до асимптотического значения 0,25 при стремлении т к бесконечности. Не удивительно, что Р=0,5 при т= 1, так как в случае всего лишь одного элемента решение должно основываться только на априорных вероятностях. Эффектно и то, что Р стремится к 0,25 при стремлении т. к бесконечности, так как эта величина находится как раз посередине между предельными значе

ниями 0,0 и 0,5. Столь большое значение уровня ошибки свидетельствует лишь о том, что в этой средней величине отражено множество безнадежно трудных задач, связанных с классификацией. И конечно, не следует считать, что «типичная» задача распознавания образов может иметь такой уровень ошибки.

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

излишнее количество признаков, то качество работы ухудшится. Почему это так, в данном случае ясно. Во-первых, увеличение числа ячеек позволяет легче различать р(х|соі) и р(х|со2) (представляемые векторами р и q), тем самым способствуя улучшению качества работы. Если, однако, число ячеек становится слишком большим, то не хватит выборок, чтобы их заполнить. В конечном счете число выборок в большинстве ячеек окажется равным нулю, и для классификации придется вернуться к неэффективным априорньш вероятностям. Таким образом, при любом конечном п величина Р{е\т,п) должна стремиться к 0,5 при стремлении т к бесконечности.

Значение т, для которого Р (е,\ т, п) достигает минимума, чрезвычайно мало. При числе выборок п=500 эта величина лежит где-то около /п=20 ячеек. Допустим, что мы сформировали ячейки посредством разбиения каждой оси на I интервалов. Тогда для d признаков получим т—І^ ячеек. Это будет означать, что при 1=2, т. е.

предельно грубом квантовании, использование более четырех-пяти бинарных признаков ухудшит, а не улучшит качество работы. Такой результат весьма пессимистичен, но не более чем утверждение о том, что средний уровень ошибки равен 0,25. Приведенные численные значения получены в соответствии с априорным распределением, выбранным для конкретной задачи, и могут не иметь отношения к частным задачам, с которыми можно еще столкнуться. Основной замысел проведенного анализа состоит в том, чтобы усвоить, что качество работы классификатора безусловно зависит от числа конструктивных выборок и что при заданном числе выборок увеличение числа признаков сверх определенного может оказаться вредным.