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

5.5. Анализ оптимального качества и обобщение на случай нескольких классов

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

С практической точки зрения величина может выбираться произвольно (как это было в примере, приведенном в § 5.4). Однако всякий выбор вообще говоря, влияет на структуру классификатора, а также на его качество. Поэтому желательно проанализировать качество системы путем вывода приближенного соотношения между параметром в альтернативах Лемана и средним числом измерений, требуемых для принятия окончательного решения. Как будет кратко показано, этот вывод позволяет отыскать подходящий способ выбора значения при котором достигается более эффективное построение без существенного увеличения сложности системы.

Для удобства определим следующий эквивалент п. к. о. в., переписав (5.10). Для четных положим

Процесс формирования продолжается до тех пор, пока выполняется условие

или

Гипотеза принимается, как только и отвергается, как только где останавливающие границы (пороги), определяемые согласно (1.48). Положим и определим

Тогда после логарифмирования можно записать (5.14) в виде

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

получим

и

Аналогично совместные вероятности

где Используя эти вероятности, нетрудно подсчитать дисперсию

Заметим, что убывает по мере роста Разлагая в ряд около среднего значения получим

где отлично от нуля. Взяв среднее от из (5.23) получаем

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

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

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

Подставляя (5.25), (5.27) и (5.28) в (5.26), получим

Если выбрано очень малым, ею "С 1, то (5.29) можно переписать следующим образом:

что дает приближенную связь между средним числом измерений и параметром при заданных ею и Рассмотрим случай, когда Ясно, что знаменатель в (5.30) возрастает с уменьшением Поскольку величина постоянна при заданных ею и соответственно стремится уменьшаться. С другой стороны, когда знаменатель возрастает с увеличением что в свою очередь приводит к уменьшению Отсюда можно заключить, что как при так и при среднее число измерений уменьшается по мере удаления от единицы. Количественная зависимость от определяемая соотношением (5.30), показана на рис. 5.2.

Рис. 5.2. График уравнения (5.30), показывающий связь между средним числом наблюдений и параметром в альтернативах Лемана.

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

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

против альтернативы

Рассмотрим последовательные замеры векторов объединенных выборок

где Соответствующие векторы последовательных рангов имеют вид

где При измерении векторов объединенных выборок вычисляются последовательные отношения вероятностей

где или являются вероятностями векторов последовательных рангов в предположении справедливости гипотезы о том, что принадлежит к классу или альтернативы о том, что не принадлежит Согласно (5.8) для четных из (5.31) получаем

где

Применяя принцип о.п.к.о.в., исключаем из дальнейшего рассмотрения класс образов со на шаге, если

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

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

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