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

ПРИЛОЖЕНИЕ А. ВВЕДЕНИЕ В ПОСЛЕДОВАТЕЛЬНЫЙ АНАЛИЗ

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

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

1. Последовательный критерий отношения вероятностей

Наиболее важным результатом в последовательном анализе является последовательный критерий отношения вероятностей (п. к. о. в.) Вальда [1]. Этот критерий

построен для решения о выборе между двумя простыми гипотезами.

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

Для (непоследовательного) критерия с постоянным объемом выборки оптимальное решение этой задачи дали Нейман и Пирсон [2]. Они показали, что при данном числе наблюдений критерий, обеспечивающий наименьшее (т. е. наиболее мощный критерий), определяется отношением правдоподобия имеющим вид

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

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

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

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

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

Это указывает на окончательное решение о принятии Из и

что эквивалентно равенству

Оба интеграла берутся по области, содержащей все замеры, приводящие к принятию Согласно определению Дает

Аналогично когда

то

Решая и получим

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

ошибок обоих родов. Тем не менее в общем случае

Следует также заметить, что при доказательстве и нигде не предполагалась независимость замеров.

Из и вновь пренебрегая превышением порогов, получаем

Пусть есть условное среднее при условии, что истинна, и пусть

Отсюда непосредственно следует, что

Определим

Тогда является, очевидно, функцией только и не зависит от следовательно, не зависит от Рассмотрим сумму

Взяв среднее, получим

Поэтому из среднее число наблюдений, когда истинно, равно

Аналогично из

Можно показать, что п. к. о. в. завершается с вероятностью единица как для Ни так и для [1, 13]. Вальд и Вольфовиц [3] показали, что для заданных вероятностей ошибок в. дает минимум среднего числа наблюдений Следует заметить, что процедура п. к. о. в. по существу не зависит от априорных вероятностей хотя вероятность ошибок, понятно, зависит от априорных данных.

Несколько авторов распространили п. к. о. в. на более общие случаи. Кокс [4] дал интересный пример п. к. о. в. с зависимыми между собой замерами, который характеризуется большим средним числом наблюдений как для так и для Для сложных гипотез критерий был развит Вальдом [1] и Коксом [4, 5]. Вальд предложил применить весовые функции, позволяющие свести задачу, относящуюся к сложным гипотезам, к задачам с простыми гипотезами. К сожалению, отсутствует общий метод для выбора весовых функций с подходящими свойствами. Метод весовых функций, предложенный Вальдом, можно трактовать как построение модифицированных гипотез, в которых путем интегрирования исключены мешающие параметры.

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

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

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

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

П. к. о. в. был также распространен на случай испытания трех гипотез Армитэйджем [7], а также Собелем и Вальдом [8]. Армитэйдж предложил применить одновременно все три возможных последовательных критерия, а Собель и Вальд предложили применять два из трех в.

Для большого числа гипотез [9] предложил обобщенный последовательный критерий отношения вероятностей . Предположим, что имеется гипотез. На шаге обобщенные последовательные отношения вероятностей для каждой гипотезы определяются следующим образом:

Решающее правило состоит в следующем. Отношение сравнивается с останавливающей границей для гипотезы Гипотеза исключается из рассмотрения, если

Останавливающая граница определяется соотношением

где вероятность принятия когда в действительности истинна

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

При в. эквивалентен п. к. о. в. и сохраняет его свойство оптимальности. Для доказательство оптимальности пока отсутствует.

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