Главная > Разное > Последовательные методы в распознавании образов и обучении машин
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.2. Модифицированный последовательный критерий отношения вероятностей — дискретный случай

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

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

и

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

Рис. 3.1. Графическое представление как функций

Рассмотрим модифицированный п. к. о. в., определенный согласно (3.1) и (3.2), где

при Здесь предварительно заданное число измерений признаков, производимых до того, как произойдет усечение и классификатор будет вынужден дать окончательное решение. На рис. 3.1 графически представлены функции

Пусть

Тогда модифицированный п. к. о. в. определяется следующими неравенствами:

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

Как и в § 1.5, интересно рассмотреть изменение решающих границ в случае модифицированного п. к. о. в. Используем тот же пример, который был рассмотрен в § 1.5. Для модифицированного п. к. о. в., определяемого (3.1) и (3.2), формулы (1.56) и (1.57) соответственно принимают вид

и

Заметим, что решающие границы, определяемые формулами (3.7) и (3.8) при знаках равенства, по-прежнему являются двумя параллельными гиперплоскостями в пространстве признаков. Разность между этими границами

уже не является постоянной величиной, как это было в (1.58), а зависит от Если определены формулами (3.3) и (3.4), то при разность между

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

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

можно записать в следующем виде:

Предположим, что измерения признаков независимы и имеют одинаковое распределение. Пусть

Используя хорошо известный результат последовательного анализа [4, 5], а также пренебрегая, как это часто делается, превышением границ, получим (см. приложение А)

Когда первым членом правой части (3.13) можно пренебречь. Тогда (3.12) примет вид

Таким образом,

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

или, что эквивалентно,

Учитывая, что пренебрегая условными моментами и, кроме первого, после разложения в ряд Тэйлора в окрестности и подставляя (3.15) вместо получим

Когда истинно уравнения (3.15) и (3.18) можно применить, заменив а на на на

Рассмотрим теперь обыкновенный п. к. о. в. Вальда с верхней границей (порогом) и нижней границей (порогом) Если очень малы, то Допустим, что т.е. что границы обыкновенного п. к. о. в. Вальда и модифицированного п. к. о. в. начинаются в одних и же точках. Тогда (3.15) и (3.18) можно переписать в следующем виде:

и

Важно рассмотреть следующие соотношения, вытекающие из (3.19) и (3.20):

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

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

Учитывая полученные выше результаты, становится ясным, что при правильном построении зависящих от времени границ (порогов) для последовательного процесса классификации можно достигнуть следующих целей:

(1) процесс классификации всегда заканчивается при заранее определенном максимальном числе измерений признаков;

(2) среднее число измерений признаков можно изменять; обычно оно меньше требуемого для п. к. о. в. Вальда с фиксированными параллельными границами;

(3) путем выбора начальных точек границ можно получить такие же малые вероятности ошибок, как в п. к. о. в. Вальда.

<< Предыдущий параграф Следующий параграф >>
Оглавление