Автоматика и телемеханика, № 12, 2014
© 2014 г. А.В. НАЗИН, д-р физ.-мат. наук (nazine@ipu.ru) (Институт проблем управления им. В.А. Трапезникова РАН, Москва), С. ЖИРАР, д-р наук (stephane.girard@inria.fr) (ИНРИА Рона-Альпы, Гренобль, Франция)
Li-ОПТИМАЛЬНОЕ ОЦЕНИВАНИЕ МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ПЕРИОДИЧЕСКИХ ГРАНИЧНЫХ ФУНКЦИЙ С ГЕЛЬДЕРОВСКОЙ ПРОИЗВОДНОЙ1
Предложен новый способ оценивания гладкой границы по выборке точек на плоскости, основанный на методе линейного программирования. Производная граничной функции предполагается непрерывной по Гель-деру. Оценка определяется как линейная комбинация ядерных функций, являющихся достаточно регулярными, покрывающая все точки и доставляющая наименьшую площадь ассоциированного носителя. Коэффициенты линейной комбинации вычисляются посредством решения задачи линейного программирования. Показано, что Li-ошибка между полученной оценкой и истинной граничной функцией почти наверное сходится к нулю, а скорость сходимости оптимальна.
1. Введение
В литературе имеется немало работ по оцениванию множества S на плоскости по конечному набору случайных внутренних точек. Здесь внимание сосредоточено на случае, когда неизвестный носитель может быть записан в виде S = {(ж, у) : 0 ^ ж ^ 1 ; 0 ^ y ^ f (ж)}, где f — неизвестная функция. Исходная задача сводится к оцениванию f, называемой граничной функцией, или границей, по случайным парам (X, Y), содержащимся внутри S.
При условии монотонности границу можно также интерпретировать как совокупность конечных точек Y при данном X ^ ж. В этом контексте были разработаны специфические методы оценивания, см., например, [1—3]. Также сошлемся на статьи [4-6], где даны определения робастных оценок.
В общем случае, когда нет предположений монотонности, в [7] была предложена оценка, основанная на ядерной регрессии степенного преобразования наблюдений с большим показателем. В частности, когда Y при данном X = x равномерно распределен, доказано, что эта оценка является асимптотически гауссовской с минимаксной скоростью сходимости для липшицевых границ. (Говоря неформально, под скоростью сходимости будем понимать бесконечно малую положительную числовую последовательность, характеризующую сходимость к нулю той или иной нормы ошибки оценивания, при размере выборки N ^ то.) По сравнению с оцениванием экстремальных значений [8-14], с проекционными [15] или полиномиальными оценками [16-20] эта оценка не
1 Данное исследование А.В. Назина проводилось во время пребывания в проекте MISTIS, ИНРИА Рона-Альпы, с июня по октябрь 2013 г.; частично поддержано ПреМо-Лаб/МФТИ, грант Правительства РФ № 11.G34.31.0073.
требует разбиения носителя Когда условное распределение У при данном X не является равномерным, эта оценка все же сходится (см. [7], теорема 1), но может быть подвержена сильному смещению (см. [7], табл. 1). Модификация этой оценки была предложена в [21, 22] с целью решения ситуации, в которой функция условного распределения У при данном X = х убывает с полиномиальной скоростью к нулю в окрестности граничной функции / (х). Установлена как асимптотическая нормальность, так и сильная состоятельность оценки.
Предложенный в [23] оцениватель множества 5 сохраняет некоторые общие характерные особенности с оценкой из [7]. Предполагается, что У при данном X = х является равномерно распределенным, но не требует разделения носителя. Кроме того, оцениватель определен как ядерная оценка, полученная сглаживанием некоторых избранных точек выборки. Эти точки являются, однако, выбранными автоматически посредством решения задачи линейного программирования, чтобы полученная оценка носителя покрывала все точки выборки, имея наименьшую площадь. С теоретической точки зрения, как было показано, эта оценка состоятельна в Ь\ норме. В [24] было предложено улучшение этого оценивателя для липшицевых границ с целью достижения оптимальной минимаксной скорости сходимости в Ь\ (с точностью до логарифмического множителя).
В настоящей статье предлагается адаптация этих методов для оценивания гладких границ: предполагается, что первая производная граничной функции гельдерова. В результате доказывается, что полученный оцениватель достигает минимаксно оптимальную скорость сходимости в Ь\ (с точностью до логарифмического множителя). Статья организована следующим образом. Метод оценивания определен в разделе 2. Предположения и предварительные результаты представлены в разделе 3, а основной результат сформулирован в разделе 4. В последнем разделе 5 дано заключение, все доказательства отнесены в Приложения 1-4.
2. Постановка задачи и оценка границы
Пусть все рассматриваемые случайные величины определены на общем полном вероятностном пространстве (О, Т, Р). Рассмотрим задачу оценивания неизвестной 1-периодической функции / : М — (0, то), т.е. /(х + 1) = /(х) для любых х € М, по наблюдениям (Х^, У )г=1,...,м с независимыми (в совокупности) парами (Хг,У;), равномерно распределенными на множестве
5 4 {(х,у) : 0 < х < 1, 0 < у < /(х)}.
Так как функция / 1-периодична, для дальнейшего удобно ввести расширенный индексированный набор данных, образующийся из исходных данных (Хг,Уг), г = 1, Л^, путем периодического продолжения функции /(ж) по оси х. Следовательно, полагаем (Xг-г,Уг) = — для г = 1 — N,0
и (Хг, Гг) = (Хг_м + 1, Уг_м) для г = ЛГ + 1,2ЛГ.
Замечание 1. Пример граничной 2п-периодической функции возникает при описании границы выпуклого плоского множества в полярных коорди-
натах с центром внутри множества. Нормировка полярного угла позволяет прийти к 1-периодической функции.
Замечание 2. Отметим, что условие периодичности граничной функции является, с одной стороны, существенным предположением, выделяющим специальный класс задач, а с другой стороны, техническим условием, позволяющим (вместе с условиями на ядерную функцию, см. ниже) избежать "трудности на границах" интервала [0,1], упростить выкладки при анализе ошибки оценивания и прийти к оптимальной скорости сходимости.
Положим
(1)
1
Cf=! / («)
Величины Хг распределены на интервале [0,1] с плотностью вероятности /О/С/, поскольку Уг имеет равномерное условное распределение вероятности относительно Хг в интервале [0, /(Хг)]. В дальнейшем будем предполагать, что / € Е(1, в, ¿в), 1 < в ^ 2, т.е. функция / : М — (0, то) 1-периодична, непрерывно дифференцируема с непрерывной по Гельдеру производной /' степени в — 1 и верхней границей ¿в для константы Гельдера:
|/'(х) — /'(и)| < Ьв|ж — и|в-1 Vж, и € М.
Рассмотрим семейство ядерных оценок /у : [0,1] — [0, то) граничной функции:
N
(2) /у (ж) = ^ а К^(ж,Хг), а > 0, г = 1,...,^,
г=1
где ядерная функция
(3) = +
0, 1 Тг
К
1«
х — I — 1 Тг
х -г+ 1
Тг
если Н < £ < 1 — Н, если 0 ^ £ ^ Н,
если 1 — Н ^ £ ^ 1,
определена для всех (ж,£) € [0,1]2 и Н € (0,1/2), а достаточно гладкая базисная ядерная функция К : М - [0, то) интегрируема к единице, имеет в качестве носителя интервал [—1, 1] и нулевой первый момент (см. предположение В2, раздел 3); параметр ширины окна Н зависит от N так, что Н — 0 при N — то.
Замечание 3. Оценка (2) не обязана быть периодической.
Замечание 4. Можно убедиться, что ядро (3) как функция от £ непрерывно во всех точках, включая £ = Н и £ = 1 — Н (при условии Н € (0,1/2)),
поскольку носители различных членов в (3) не пересекаются, и ядро может быть записано как
(4) Кн{х,1) = £ 1к(^±1) , ОМ) € [ОД]2-
j=-l
Выражение (4) показывает ту же степень гладкости, что и функция К(■). Например, всегда имеются границы сверху ядра К^(х,Ь) ^ Ктах/Л и к-х производных если К(■) имеет ограниченные к-е производные.
Замечание 5. В определении оценки (2) ядро (3) введено для х € [0,1]. Однако удобно ввести более широкий интервал [—Л, 1+Л], а для переменных х и Ь в ядерной функции (3) определить дополнительные точки Хо € [—Л, 0] и ХN+1 € [1,1 + Л] почти наверное (п.н.), см. ниже (17).
Замечание 6. Оптимальный выбор ширины окна Л осуществляется здесь в духе работы [24]. Также см. ниже замечание 7 в конце раздела П.3.
Как показано ниже в лемме 2, площадь оцениваемого носителя
(5) = {(х, у) : 0 < х < 1, 0 < у < /м(х)} выражается как
1 - м
(6) ¡м(х) ^х =
0 ^=1
Это приводит к определению оценки через вектор-параметр а = (а1,... ,ам)т, являющийся решением задачи оптимизации
(7) ГР 4 тш£
а ^—*
N
аг
г=1
при ограничениях: для всякого г = 1,Ж,
(8) /м(Хг) + (Xj - Хг) /м(Хг) ^ Yj, V; : |Xj - Хг| < Л,
(9)
м
аг
г=1
(11) 0 < аг,
(10) аг 1{(«г - 1)/«г/г < Хг < т/гпк} ^ Са1г, т = 1, тн,
где = |_1/Л1 (т.е. целая часть числа 1/Л),
// д2 К (х,и) = —т Кь{х, и), (х,и) € [0,1]2, дх2
!(•} — индикаторная функция (равная 1, если аргументное условие выполнено, и 0 в противном случае). Положительный параметр Са, присутствующий в ограничениях (10), будет выписан позднее в разделе 4. Очевидно, эта задача минимизации может быть переписана в виде задачи линейного программирования (ЛП), и определенную таким образом оценку граничной функции будем называть ЛП-оценкой (7)—(11).
3. Основные предположения и предварительные результаты
Основные предположения относительно неизвестной граничной функции / : М — (0, +го) таковы:
А1. /(ж) = /(ж + 1) и 0 < /т1п ^ /(ж) ^ /тах < го для всех ж € М. А2. функция /(•) непрерывно дифференцируемая, имеющая гельдеров-скую степень в — 1 по отношению к производной /', т.е.
1/'(ж) — /'(у)| < ^ |ж — у|в-1 V ж, у € [0,1], где константы Ьр < го и в € (1, 2] предполагаются заданными. Вводятся следующие предположения на ядро К(•):
В1. К : М —> [0, +го) имеет компактный носитель: виррК(¿) = [—1,1];
1 1
В2. У К(¿) ^ = 1, J * К(¿) ^ = 0; -1 -1
В3. Ядро К(•) четырежды непрерывно дифференцируемое.
Лемма 1. Пусть / — 1-периодическая функция на М. Тогда предположения В1 и В2 обеспечивают равенство 1 1
(12) у / (и)К^(ж,и) ^и ^У /(ж — Ли)К(и) ¿и V ж € [0,1]. 0 -1
В частности, для / (ж) = 1 получаем
1
(13)
0
Кроме того,
I
У К^(ж,и) ^и = 1 Vж € [0,1].
(14)
(15)
(16)
1
У (и — ж)К^(ж,и) ^и = 0 V ж € [Л,, 1 — Л,], 0
1
У К^(ж,и) ^ж = 1 Vи € [0,1], 0
1
У (ж — и)К^(ж, и) ^ж = 0 V и € [0,1].
Приведем ряд предварительных результатов о
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.