научная статья по теме О ПРИЛОЖЕНИИ ВЫПУКЛОЙ ОПТИМИЗАЦИИ К ПОСЛЕДОВАТЕЛЬНОМУ РАЗЛИЧЕНИЮ ГИПОТЕЗ Автоматика. Вычислительная техника

Текст научной статьи на тему «О ПРИЛОЖЕНИИ ВЫПУКЛОЙ ОПТИМИЗАЦИИ К ПОСЛЕДОВАТЕЛЬНОМУ РАЗЛИЧЕНИЮ ГИПОТЕЗ»

Автоматика и телемеханика, № 5, 2015

© 2015 г. А.Б. ЮДИЦКИЙ, канд. техн. наук (anatoli.juditsky@imag.fr) (Университет Гренобль - Альпы, Франция), А.С. НЕМИРОВСКИЙ, д-р физ.-мат. наук (nemirovs@isye.gatech.edu) (Технологический институт Джорджии, Атланта, США)

О ПРИЛОЖЕНИИ ВЫПУКЛОЙ ОПТИМИЗАЦИИ К ПОСЛЕДОВАТЕЛЬНОМУ РАЗЛИЧЕНИЮ ГИПОТЕЗ1

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

1. Введение

Имеется пространство наблюдений Q, снабженное мерой P. Наблюдается последовательность шк = (ш\, ... ,Шк) независимых одинаково распределенных (н.о.р.) реализаций Шг € П случайной величины с плотностью распределения (взятой по мере P) из заданного параметрического семейства {рД-) : ц € M}. Требуется различать гипотезы Нг, 1 ^ i ^ I, порожденные I заданными попарно непересекающимися подмножествами Хг параметрического пространства M; согласно гипотезе Нг параметр ц наблюдаемого распределения принадлежит множеству Xг. Соответствующие решающие правила (тесты) представляются измеримыми функциями Тк(шк) на пространстве Пк со значениями в множестве {0,1,...,I}; соотношение TK(шк) = i интерпретируется как принятие тестом, примененным к наблюдению шк, гипотезы Нг (при i > 0) или отказ от принятия какой бы то ни было гипотезы (при i = 0). Качество теста Тк(■) характеризуется его риском - максимальной (по всем разрешенным гипотезами распределениям наблюдений) вероятностью отвергнуть правильную гипотезу:

(1) Risk(Tк) = max sup Pм к{шк : Тк(шк) = i},

где P ^ к - вероятность, соответствующая распределению шк, индуцированному плотностью рД-). В рассматриваемой ситуации типичная статистическая задача - это построение теста с заданным риском и минимальным (или "почти

1 Работа выполнена при финансовой поддержке: CNRS-Mastodons проект GARGANTUA, LabEx PERSYVAL-Lab (грант № ANR-11-LABX-0025), NSF (грант №CMMI-1232623, грант №CMMI-1262063, грант №CCF-1415498).

минимальным") при этом требовании временем наблюдения К. Во многих ситуациях такой чисто минимаксный подход оказывается слишком консервативным, и предпочтение отдается последовательным тестам. Последовательный тест обрабатывает индивидуальные наблюдения одно за другим и в каждый момент Ь ^ К использует накопленное наблюдение Ш = (ш1,..., ш^), чтобы либо принять одну из гипотез и остановиться, либо отложить решение и перейти к следующему наблюдению (при Ь < К), либо остановиться, не приняв ни одной гипотезы (при Ь = К). Синтезируя последовательный тест, хотелось бы обеспечить заданный риск е при возможно меньшем значении К («оптимальное гарантированное поведение») и добиться по возможности ранней остановки в ситуации, когда истинное значение параметра ц наблюдаемого распределения находится «глубоко внутри» своего множества Xг и тем самым «хорошо отделяется» от ложных гипотез. Такой подход, берущий свое начало в классических работах Барнарда [1] и Вальда [2, 3], представляет собой хорошо развитую область статистической теории (см. [4-6] или недавний обзор [7]). Обычно последовательный тест основывается на статистике обобщенного правдоподобия или смешанного правдоподобия, и его качество оценивается дескриптивно, по явно выписываемому асимптотическому поведению при е — +0 и К — то. Подход, развиваемый в данной статье и берущий свое начало в [8, 9], по своему роду операционный, а не дескриптивный. Он опирается на вычислительно эффективную конструкцию, основанную на выпуклом программировании, которая дает возможность при соответствующих предположениях построить почти оптимальный «простой тест», позволяющий различить по наблюдению шк две сложные гипотезы Н1 : ^ € X и Н2 : ^ € У о параметре наблюдаемого распределения; здесь X и У - выпуклые компактные подмножества М. Эта конструкция применима в нескольких важных ситуациях, а именно, когда: а) р^ - плотность нормального распределения на Мп с математическим ожиданием ^ и фиксированной ковариационной матрицей, б) р^ - распределение вектора в Мт с независимыми пуассоновскими компонентами с параметрами в) распределение дискретной случайной величины, принимающей значения {1 ,...,т}, где ц € М^ - вектор вероятностей соответствующего распределения, г) семейство плотностей р^ образовано из семейств типа а)-в) с помощью взятия естественно определенного прямого произведения.2 В качестве компенсации за довольно жесткие предположения о семействах плотностей р^, обсуждаемая конструкция работает в очень широких предположениях о структуре областей: все, что требуется (помимо компактности и выпуклости), - это возможность эффективного описания X и У. Следует подчеркнуть, что указанная конструкция, как и развивающие ее результаты данной статьи, не дает априорной аналитической информации о качестве результирующих тестов (что вряд ли возможно при широких предположениях о «геометрии» рассматриваемых гипотез); в то же время детальная количественная информация о качестве полученных здесь (доказуемо почти оптимальных) тестов вполне доступна и получается в результате эффективных вычислений.

2 Следует отметить, что некоторые частные случаи "простых тестов" рассматривались и ранее, а именно в работах [10-12], посвященных случаю а), и в работах [13-18], покрывающих до известной степени случай в).

Цель настоящей статьи - применение подхода из [9] к синтезу последовательных тестов. Организация статьи такова: в разделе 2 приведены результаты из [9], используемые в последующих построениях. Раздел 3 содержит формулировку задачи последовательного различения гипотез, предлагаемую общую схему последовательного теста и анализ этой схемы. В разделе 4 детально описывается представляющаяся наиболее естественной реализация последовательного теста и приводится численная иллюстрация. В целях экономии места опускаем некоторые доказательства; читатель может найти их в подробной версии статьи [19].

2. Предварительные замечания

В этой части статьи кратко излагается подход [8] применительно к задаче проверки гипотез; подробное описание конструкций и результатов данного раздела, а также соответствующие доказательства см. в [9].

2.1. Простые схемы наблюдения

Начнем с описания простых схем наблюдения, с которыми будем работать. Напомним, что будем анализировать случайные наблюдения ш, принимающие значения в заданном пространстве наблюдений О; предполагается, что распределение наблюдений имеет плотность по заданной мере Р на О и эта плотность принадлежит заданному параметрическому семейству плотностей {рД-} : ^ € М}. Предполагаем, что:

1) Мс Мт - выпуклое множество, совпадающее со своей относительной внутренностью;

2) О - польское (т.е. сепарабельное полное метрическое) пространство с борелевской ст-аддитивной ст-конечной мерой Р, 8ирр(Р} = О, и

• рДш) положительна и непрерывна по ^ € М, ш € О;

• плотности р^(-} «локально равномерно суммируемы»: для всякого компакта М сМ существует борелевская функция рм(■} на О, такая что /п рм(ш)Р(^ш) < то и рДш) ^ рм(ш) для всех ^ € М, ш € О;

3) дано конечномерное линейное пространство Т непрерывных функций на О, содержащее константы, такое что 1п(рД-)/р^(■}} € Т при

V € М (таким образом, плотности рД-) принадлежат экспоненциальному семейству);

4) для всякого ф € Т функция ^ф(^) = 1п (/п ехр{ф(ш)}рм(ш)Р(^ш)) конечна в каждой точке М и вогнута по ц € М.

В только что описанной ситуации при соблюдении предположений 1-4 назовем тройку О = ((О,Р), {рм(■) : ^ € М}, Т) простой схемой наблюдений (с.н.).3

Примеры. Приведем основные примеры простых с.н.

3 Здесь и далее сокращение «с.н.» означает "схема наблюдений".

Гауссовская с.н. Здесь О = Мт, Р - мера Лебега на О, М = Мт и рДш) = = N/т) - гауссовская плотность со средним ц и единичной матрицей ко-вариации.4 Пространство Т образовано всеми аффинными функциями на О = Мт. Ввиду

гауссовская с.н. проста.

Пуассоновская с.н. Здесь О = Z+m - дискретное множество т-мерных векторов с неотрицательными целыми компонентами, Р - «считающая» мера на О (масса каждой точки равна 1), М = Мт+ - множество положительных т-мерных векторов и рД-), ^ = ...; 1лт] > 0, - распределение вероятности случайного вектора ш = [ш1;...; шт] с независимыми пуассоновскими компонентами; вектор р образован параметрами соответствующих пуассоновских распределений. Пространство Т образовано всеми аффинными функциями на О. Функция

вогнута по р, так что пуассоновская с.н. проста.

Дискретная с.н. Здесь О = {1,...,т} - конечное множество, Р - считающая мера на О, М образовано всеми положительными плотностями вероятностей, взятых относительно Р (иными словами, М состоит из положительных т-мерных векторов р = [^1;...; рт] > 0 с единичной суммой компонент), и случайная величина ш с плотностью рД-) принимает значения ш € О с вероятностями . Пространство Т образовано всеми вещественнозначными функциями на О = {1,... ,т}. Таким образом, для ф € Т функция

вогнута по р € М, так что дискретная с.н. проста.

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

Прямые произведения простых с.н. Пусть 0 = ((О^,Р^), {р^, ¿(-) : €

€ М^}, Т^), 1 ^ £ ^ К, - простые с.н. Можно связать с этими с.н. их прямое произведение - новую с.н. с кратными наблюдениями шк = (ш1,..., шк), где Ш1,..., шк генерируются независимо друг от друга соответствующими с.н. Формально прямое произведение исходных с.н. определяется как схема на-

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

блюдений

Ок = | (Ок, Рк) = ^ Ц О4, Рк = Р1

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком