Эффект концентрации меры в статистических задачах непараметрического оценивания тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Рафиков, Евгений Геннадьевич

• Рафиков, Евгений Геннадьевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Рафиков, Евгений Геннадьевич

Введение

1 Анализ сходимости эмпирических частот к вероятностям.

1.1 Постановка задачи.

1.2 Вспомогательные утверждения.

1.3 Доказательство основного результата.

1.3.1 Симметризация по перестановкам выборки.

1.3.2 Оценка частичной суммы гипергеометрического распределения.

1.3.3 Продолжение оценки сверху для itm<n(t).

1.3.4 Оценка сверху для r^n(t).

1.3.5 Оценка сверху для rfn n(t).

1.3.6 Оценка интеграла по Ue П Vc.

1.3.7 Оценка интеграла по Uc П Ve.

1.3.8 Завершение доказательства.

1.4 Доказательство основного промежуточного результата.

1.4.1 Разложение sup на max и локальный sup.

1.4.2 Анализ слагаемого шах.

1.4.3 Анализ локального sup слагаемого.'

2 Непараметрическое оценивание функции регрессии.

2.1 Введение и постановка задачи.

2.2 Оцеики сверху в случае неограниченных откликов.

2.3 Оценки сверху в случае, когда класс гипотез задаётся в терминах Колмогоровских поперечников.

2.4 Универсальные оценщики.

2.5 Оценки снизу.

2.6 Оценки снизу для схемы Бернулли.

Введение диссертации (часть автореферата) на тему «Эффект концентрации меры в статистических задачах непараметрического оценивания»

Актуальность работы.

Во многих задачах математической статистики наряду с асимптотическим поведением стохастического объекта важно также знать и его неасимптотическое поведение.

Известно, что если Хь.,Хт — одномерные независимые и одинаково распределённые случайные величины, а Г(х) и Рт{х) — соответствующие им настоящая и эмпирическая функции распределения, то имеет место предельное асимптотическое поведение:

Теорема (Колмогоров).

Из теоремы Колмогорова следует также и неасимптотическая оценка: Утверждение 0.1.

Её аналог в случае распределений в Rd был получен Кифером (Kiefer):

Теорема (Кифер). Для произвольного а > 0 существует полооюительиая константа К = К (а, d), такая что для всех т £ N верно:

Эмпирический процесс, который фигурирует в указанных выше результатах, является частным случаем более общего объекта: k=l k-le-2k42 при m —> oo. sup |Рт(Л) - P(/l)|.

1)

AeA

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

Большая часть статистической теории обучений также посвящена изучению этой задачи при определённых условиях на вероятностную меру Р(-) и набор множеств А, см. [41, 39, 8]. Для фиксированного множества А и вероятностной меры Р(-) по закону больших чисел имеет место сходимость почти наверное Рт(А) - Р(Л) 0 при т -» оо. Более того, известное неравенство Хёфдинга даёт следующую (неасимптотичсскую) оценку на скорость сходимости:

Рг{| Рт(Л) — Р(Л)| > ¿} < 2е-2т*2.

Если набор А конечен, то естественно получаем обобщение предыдущего неравенства:

Рг{8ир|Рт(Л)-Р(Л)| >*} <2|Л|-е"

2;?1-г

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

Часть результатов в этой области посвящена тому, что на неизвестную меру Р(-) накладываются дополнительные естественные условия. Так, важным является случай, когда мера Р(-) и семейство А таковы, что мно'жество значений мер (Р(^4), А £ А\ отделено от некоторой окрестности 1/2. Улучшению оценок на поведение вероятностных хвостов для (1) в этом случае посвящена первая часть нашей диссертации. В качестве числовой характеристики такой отделимости мы используем разновидность информации Кулъбака-Лейблера, играющую важную роль в теории информации, см. [19, 5]. Близкие характеристики, такие как расстояние Кульбака-Лейблера, используются для решения задачи оценивания плотности, см. [7], а также в асимптотической теории оценивания, см. [18].

Для получения экспоненциально быстрых оценок в изучаемом нами случае используется техника из теории эмпирических процессов, что также делает тематику и приёмы, обсуждаемые в диссертации, близкими к таким областям как классическая иепараметрическая статистика, семипарамет-рическая статистика, теория М-оценивания, теория гауссовских процессов и равномерные законы больших чисел и повторного логарифма.

Вторая часть диссертации посвящена современным проблемам регрессионного анализа. Пусть X 6 М^ и У £ М — некоторые борелевские множества.

В зависимости от предположений о характере неизвестной зависимости между х £ X и у Е У известен ряд классических постановок задачи обучения по конечной выборке.

Так, в теории приблиэ/сений считается, что имеется детерминированная неизвестная зависимость па произведении Хх У. Точнее, предполагается, что для точек из известного конечного набора ъ = {(21,7/1),., (хт,ут), Х{ £ Х,уг 6 У} верно соотношение т/г- = = 1 где / принадлежит некоторому заранее известному функциональному классу Н. Задача состоит в нахождении наилучшего приближения к / внутри класса Н. Ошибка приближения обычно измеряется в 1^-норме по отношению к мере Лебега па X, где 1 < р < оо.

В случае, когда допускается какая-то случайность в характере зависимости между х и у, говорят о теории оценивания функции регрессии. Рассматривается класс моделей вида у = /(ж) + е, где / 6 Н, а е — случайная величина. Например, считается, что для множества г = {(21,7/1),., (хт,угп), 2г- £ Х,у1 € У] выполняются равенства 7д = /(х{) + бг-, где 21,. ,хт фиксированы, а бг — независимые одинаково распределённые случайные величины с Ебг = 0. Задача, как и выше, состоит в том, чтобы построить некоторое приближение /2 для / (или оценку /), оптимальное в смысле Е(||/—/2||2) в одной из стандартных норм. Также рассматривается постановка задачи, когда "входы" 21,. ,хт сами случайны и распределены в соответствии с неизвестным вероятностным законом на X, см. монографию [14].

В своей работе мы имеем дело с задачей, когда считается, что произведение Z — X х У снабжено некоторой вероятностной Борелевской мерой р, а обучающие примеры ъ — суть случайная р-выборка длины т. Задача заключается в оценивании функции регрессии т/-ов по гг-ам, /р(х) = Е{у\х}. Пусть рх — это проекция меры р на X. Для описания качества оценивания мы используем общепринятую характеристику скорости убывания вероятностных хвостов -

Рг{||/,-Л|и2(Ы>*}, (2)

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

В ряде случаев, когда известно поведение классических в теории приблиэ/сений характеристик класса Н, таких как энтропийные числа и Колмо-горовские поперечники, нами получены экспоненциальные оценки убывания (2) при согласованном поведении т и Они являются обобщением результатов, полученных в ряде недавних работ, основные из которых приведены в обзорах [4, 33].

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

Краткое содержание диссертации.

Пусть Х\,. ,Хт — независимые одинаково распределённые в сответствии с некторой вероятностной мерой Р(-) случайные величины в Евклидовом пространстве Rd. Обозначим через т длину выборки, а через Рт{') ~ соответствующую эмпирическую меру. Первая глава посвящена изучению поведения вероятностных хвостов эмпирического процесса sup I Рт(Л) - Р(Л)| лед для случая, когда А — семейство Борелевских множеств в Rd с конечной размерностью Вапиика-Червоненкиса V = V(A). В предположении, что множество значений мер (Р(^4), А 6 А} отделено от некоторой окрестности 1/2, мы улучшаем ряд известных классических оценок. Введём необходимые определения.

Определение. Наибольшее целое число V, для которого существует набор из V точек Х\,., ху, удовлетворяющих свойству ху}ПА: AeA] = 2v, называется размерностью Ваппика- Червоненкиса семейства А.

Если не оговаривается противное, везде ниже под V = V(A) мы понимаем конечную размерность Банника- Червоненкиса набора множеств А.

Определение. Для вещественных чисел p,q £ (0,1) расходимостью Кульбака-Лейблера Н(р, q) называют следующее выраоюение:

Определение. Критическим значением р^ для системы множеств А и меры Р(-) назовём блиэ/сайшую к 1/2 из двух величии р+ и р-, где р+ = inf Р(Л), р = sup Р(Л). АеА, Р(Л)>1/2 ЛеДР(Л)<1/2

Неформально можно рассматривать рА как ближайшее к 1/2 значение меры Р(Л) на множествах А € А.

Теорема 1. Пусть рА — критическое значение для семейства множеств А с конечной размерностью Вапника- Червоненкиса V. Тогда для некоторых положительных констант М — М(рА, V), К = K(V) и ¿0 = ¿о(Я4> У) пРи т • t2 > М и t < ¿о выполняется оценка

Pr{sup\Pm(A)-P(A)\>t}<

ЛеЛ К ■ (:mt2)2V+4 • ехр{—77i • min(Н(рЛ + t,pA), Н(рл - t,pA))}.

Прокомментируем наш результат. Размерность Вапника- Червоненкиса V является чисто комбинаторной характеристикой системы борелевских множеств А и не зависит пи от какого распределения вероятностей. Она описывает разнообразие А. Другими словами, V равно наибольшему возможному числу точек в К**, таких что для любого (из 2V) подмножества этих точек найдётся представитель Ае А, пересекающийся с точками в точности по этому подмножеству. Если такое множество из V точек можно найти для любого V 6 N, то размерность Вапника-Червоненкиса считается равной бесконечности. Отметим, что для бесконечной системы множеств А сё размерность V{A) может быть как конечной, так и бесконечной. Рассмотрим несколько важных примеров.

Для набора полупространств в пространстве

А = {{х :< w, х > +-шо > 0} : w G Rd, w0 G Щ имеем V(A) = d+ 1, для семейства отрицательных ортантов

А = {(-оо, х\] х • • • х (-оо, x,i] : (zi,., xd) е M.d} верно V(A) = d.

Семейство всех выпуклых многогранников в (при d > 2) даёт пример набора А с бесконечной размерностью V.

Результат Теоремы 1 обобщает классические неасимптотические оценки Колмогорова, Смирнова и Кифсра (Kiefer) на скорость сходимости эмпирической функции распределения к настоящей, а также ряд результатов Вапника, Червоненкиса и других авторов о равномерной сходимости частот к вероятностям. Вапиик и Червоиенкис первыми доказали экспоненциальные вероятностные оценки для эмпирического процесса sup,^ |Рт(Л) — Р(-А)| в общем случае когда V(A) конечно, см. [39, 40].

Теорема (Вапник-Червоненкис). Пусть А — класс Борелевских множеств в с конечной V — V(A). Тогда для mt2 > 2 верно неравенство:

Pr{sup I РтИ) - Р(Л)| > «} < 4(?P)V • е-"*2/«.

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

Такие оценки принято называть свободными от распределения. Они также известны в литературе как границы Вапника-Червоиенкиса. Все такие результаты и их обобщения в общем виде можно записать так:

Pr{sup |Рт(Л) - Р(Л)| >t}< K(t, V) • {mt2)v - е-,п-ф{1\ когда mt2 > С, (3) АеЛ

Здесь С — некоторая константа, не зависящая от t, v — функция от V, а 4>{t)=1l\ где 7 £ (0,2].

Нескольким авторам удалось улучшить константы из первых оценок Ван-ника и Червонеикиса. Отметим здесь лишь, что Деврой (L.Devroye) в [6] получил оптимальный множитель e~2mt2, а Талагранд (М. Talagrand) в работе [34] — также и неулучшаемый показатель v = V — 1/2. Наше предположение о том, что множество {Р(^4) : А £ А} отделено от некоторой окрестности 1/2, позволяет улучшить экспоненциальный множитель в оценках вида (3) и взять в качестве ф(Ь) выражение = min(Н{рл + t,pA), П{рл ~ t,pA)). (4)

Новый вид оценки обобщает классический результат Чернова (Chernoff) для случая отдельного множества A £ А.

Теорема (Чернов).

Рг{(Рш(А) - Р(4)) >t}< ехр{-т • Н(Р(А) +1), P(i))}, VA е А.

Талагранд выдвинул гипотезу о том, что наряду с ф{Ь) из выражения (4) в оценке (3) может быть сохранён оптимальный полиномиальный мпоо/ситель {тРУ'1!2. Таким образом, Теорема 1 может рассматриваться как частичное решение гипотезы Талаграида. Условия отделимости {Р(у1), А £ А} от 1/2 означает, что Ф 1/2. А значит для некоторого to > 0 множества {pa + {pa — t}, 0 < t < io не пересекаются с некоторой окрестностью 1/2. Из свойств расходимости Кульбака-Лейблера следует, что для таких t экспоненциальный показатель в Теореме 1 улучшен по сравнению с оптимальным в случае предположения свободы от распределения.

Талагранд показал, что выполняется следующая разновидность оценки (3), которую мы приводим для частного случая:

Теорема (Талагранд). Пусть А — ограниченное семейство измеримых миоо/сеств в R^ с конечной V = V(A). Пусть также Р(-) — некоторая

Борелевская вероятностная мера на а ра — критическое значение для А и Р(-). Тогда если рд Ф 1/2, то для любого /3 6 (0,1) существуют поло-'жигпелыше числа М(/3,рV), К(У) и ¿о(/2,Яд> такие что при т • Ь1 > М{(3,Ра-,У) иЬ < ¿о{(3,Ра,У) верно неравенство:

Рг{811р|Рт(Л)-Р(Л)|>^}<

ЛеД К{V) • (mt2^Ve-m(1-P)■1™n(H(PA+t,PA),II{PA-t,PA))

Эта теорема нужна нам как вспомогательная для нашего основного результата. Мы приводим новое простое её доказательство. Отметим, что наибольшую сложность здесь представляет переход от множителя т(1 — (3) в показателе экспоненты просто к га, чтобы получилось прямое обобщение неравенств Чебышева и Чернова.

Поясним иа примере, что объект, который мы оцениваем в Теореме 1, естественным образом возникает в теории обучений. Для этого рассмотрим классическую задачу двухклассового распознавания «¿-мерных объектов. Предположим, что заранее известен класс решающих правил Н, т.е. класс функций / : —> {0,1}, а также обучающая выборка 2 = {(Х1,у1),.,{хт,ут)} длины га. Здесь е М*, а Уу € {0,1}. Будем понимать иод неизвестным законом, в соответствии с которым получены или собраны наблюдения = (а^,^-), некоторое распределение вероятностей Р(-) па произведении М^ х {0,1}. Общая задача состоит в том, чтобы на основе выборки г длины га из семейства ТС выбрать в некотором смысле наилучшее решающее правило /2 £ Н с тем, чтобы использовать его для распознавания любых точек из К0'. Например, выбрать решающее правило /2, которое по входному х-у как можно чаще выдаёт "правильный" у.

Естественный подход при выборе оптимального / : —» {0,1},/ £ Н состоит в минимизации эмпирической ошибки, определяемой как т

Обозначим функцию, или как ещё говорят, "распознаватель", на которой достигается этот минимум, как /2. Ошибкой правила / € Н назовём Р-меру множества всех таких пар (х,у) € М^ х {0,1}, для которых /(х) Ф у. Возникает естественный вопрос о том, насколько ошибка такого "распознавателя" /2 близка к минимально возмоэюной ошибке внутри класса Н. Пусть Рт{-) — соответствующее выборке г эмпирическое рапределение. Тогда можно показать, что модуль интересующей нас разности оценивается сверху как

2-8ир|Рт(Л)-Р(Л)|, лед где семейство Л представляет из себя следующий набор множеств: : f(x) = 1} х {0}} [j{{x : f(x) = 0} х {1}}, f еН.

Для фиксированного множества А и для любой непрерывной меры Р(-) но закону больших чисел имеет место сходимость почти наверное Рт(А) — Р{Л) —> 0 при т —> со. Более того, неравенство Чебышсва и Хёфдинга даёт следующую оценку па скорость сходимости:

Pr{\Pm(A)-P(A)\>t}<2e-2m4\

Если семейство Л конечно, то естественно получаем обобщение предыдущего неравенства:

Pr{snp |Рт(Л) - Р(Л)| >t}< 2\А\ ■ е~2п4\

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

Вторая часть диссертации посвящена задаче оценивания функции регрессии. Пусть X С Rd и У С R — Борелевские множества, и на их произведении Z — X xY определена Борелевская вероятностная мера р. Обозначим через fp-.X—^Y функцию регрессии у на х, т.е. fp(x) — Е{у\х}.

Мы изучаем задачу оценивания функции fp(x) по конечной /^-выборке z = {z\,.,zm} : Zi = (xi,yi),i = 1 ,.,m. Иногда эту задачу называют обучением функции регрессии.

Функцию, построенную по выборке z и оценивающую fp(x), будем обозначать как fz:X->Y и называть её функцией-оценщиком. Пусть рх — проекция меры р на X. Естественной характеристикой качества оценивания функции fp является скорость убывания вероятностных хвостов (при стремлении б 0 и т —> оо)

Рг{\\/г-/р\\Ъ{Х,Рх)>*}' (5)

Здесь и везде ниже под Рг(-) понимается //"-вероятность на произведении Zm, где Z = X х У. На неизвестную меру р мы накладываем следующие условия (6) и (7):

3 Ch С2 > О, такие что Vi > 0 : р{\у\ > t) < Сг • ехр{-С2 • £2}, (6) fp(x) € 7i, где Н — компактное подмножество в пространстве С(Х). (7)

Свойство убывания вероятностных хвостов (6) также известно как равномерная субгауссовость по у. Для функции / : X —> У, / Е Ь2(Х,рх) её ошибкой назовём выражение f) = J у)2-dp. 10

Известно, что минимум ошибки достигается на функции регрессии fp(x): а значит для любого оценщика /2 6 Ь2(Х,рх) вероятностные хвосты (5) можно записать как и обозначим через мгшимум эмпирической ошибки для пространства Н: fn,x = argmin Sz(f). fen

Обозначим также через N(H, е) мощность б-сети для Л в пространстве С(Х) непрерывных функций на X со значениями в R.

Теорема 2. Пусть мера р удовлетворяет условиям (6) и (7). Тогда найдутся полоэ1сителъпые константы C\{7i,p) и такие что для всех б > 0 справедливо неравенство:

Рг[£(Ш ~ ¿Ш > *} < 2N(H,e/C1(H,p)) ■ ехр{-С2(Н,р) • те2}.

Определение. Энтропийным числом еп(Н) порядка п для функционального класса Н в пространстве С(Х) называется следующая характеристика: где и(С(Х)) — единичный шар в пространстве С(Х).

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

Теорема 3. Пусть мера р удовлетворяет условиям (б) и (7) и для некоторых г > О, С > 0 и всех натуральных чисел п € N выполняются неравенства еп(Н) < Сп~г. Тогда существуют полооюительные константы С\(г, р),С2(г, р) > 0, такие что при этом для / G Ь2(Х,рх) : £(/) - £(fp) = ||/ - М\12{х,Рх)

Pr{||/z - fp[[l2ix,Px) >t} = Р'Ш) ~ S(fp) > е}.

Определим эмпирическую ошибку Sz(f) как еп(П) := inf{6 : 3/ь ., /2„ G Ч : Н С uf^fj + eU(C(X)))}

2 т

Pr{£(fn,z) ~ £(fP) > е} < е vmc , как только е • га7^ > С2.

Для доказательства предыдущих теорем мы используем несколько промежуточных результатов. Пусть для меры р выполняются условия (6) и (7). Тогда верпы утверждения:

Лемма 1. Пусть функция / Е Н имеет конечную ошибку £(/). Тогда для некоторой константы С = С(Н,р) > 0 и для всех е > 0 имеет место оценка:

Рг{£(/) - £,(/) > е} < 2ехр{—С • те2}.

Лемма 2. Существуют константы > 0, ^ = 1,2, такие что для б > 0 верно:

Рфир |£(/) - > б} < ЪЩН^С^р)) ■ ехр{-С2(^,р) • шб2}. /еп

Многие авторы изучали вопросы качества и оптимальности оценивания /р в случае, когда на меру р наложены более простые условия ограниченности вида \у\ < М р-п.н. для некоторого фиксированного М > О, см. [4, 10, 14]. Наш основной вклад заключается в перенесении части их результатов па случай неограниченных у-ов.

Определение. Колмогоровским поперечником порядка п для семейства функций % С С(Х) называется число (1п(Н,С(Х)), определяемое как где берётся по всем п-мериым линейными подпространствам в С{Х).

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

1п{Н,С(Х))<С1-п-г, п = 1,2,. (8) следуют неравенства для энтропийных чисел, см. [3]: еп(Ч,С{Х))<С2-пг, п = 1,2,. (9)

Наш следующий результат усиливает оценки Теоремы 3:

Теорема 4. Пусть мера р удовлетворяет условиям (6) и (7). Предполооюим ташее, что существуют такие С,г > 0, что выполняются неравенства: в,п{Н,С(Х)) < С • тГг, п = 1,2,.

Тогда существует такой оценщик ¡х, что для некоторых констант С\(Н, р), выполняются неравенства: г

РгШ/и) - £(/р) >е}< е-с^тс\ как только е ■ т** . I1+2г > С2.

1п т)

Опишем следствие из этой теоремы. Пусть р > 0 действительное число. а р

Определим класс гладких порядка р действительнозначных функций Н'1 на единичном кубе в М следующим образом.

Определение. Представим действительное число р > 0 в виде р = к + (3, где к € М, и 0 < /3 < 1 и определим класс Нр функций / : [О, I}'1 —> М следующими условиями. Скажем, что / £ Нр если и только если у / существуют все частные производные порядка к, все они удолетворяют условию Гёльдера с параметром /3 па мпоэ/сестве [0,1]^, и ||/||с(х) < 1

Известно, что для пространства Н = Нр энтропийные числа и Колмо-горовские поперечники удовлетворяют неравенствам (8) и (9) с показателем г = р/й, см. [36], что даёт нам экспоненциальные оценки для случая, когда пространство гипотез для /р{х) представляет хорошо изученный класс гладких функций Нр. Отметим, что оценщик из Теоремы 4 представляет из себя более сложную конструкцию, чем рассматриваемый ранее па котором достигается минимум эмпирической ошибки для класса Н.

Последняя часть наших результатов касается построения универсальных оценщиков.

Определение. Для подпространства Ь в пространстве непрерывных функций С{Х). определим расстояние до функционального класса Н как с1(Н, Ь) := вир тПЦ-дЦ^. (10)

Пусть С = {Ьп}^=1 — последовательность п-мерных (п = 1,2,.) подпространств в С(Х), и0<а<(3<оо — действительные числа. Пусть также С,Б — некоторые фиксированные положительные константы и г Е [а,(3]. Обозначим через Нг произвольное ограниченное семейство функций в пространстве С(Х), удовлетоворяющее свойствам:

1(Пг, Ьп)<С- пг, п = 1,2,.; 8ир ||/|| С{Х) < Я. епг

Наконец обозначим

Н(а,(3) = {Нг,ге[а,(3}},

Такое условие возникло в работе [10] и является близким к естественным в теории приблилсений условиям на убывание Колмогоровских поперечников. Справедлива

Теорема 5. Предплоэ/сим, что для меры р выполняются условия (6) и (7), где H имеет вид H = Н(а,р) и0<а<(3<оо. Тогда существует универсальный оценщик fz и такие полоэ1сительные константы С\(Н, р,а),С2(Н, р,а), что если fp G Нг С Л(а, (3), для некоторого г G [а,(3], то верпа оценка т

Рг{£(/,) - £(L) >е}< е~Сут(2, как только е ■ mта? . (^ > С2.

МП 771/

Оценка этой теоремы слабее, чем предыдущий результат, однако и пространство H теперь гораздо шире. Существование универсального семейства конечномерных подпространств С = {Ln}, оптимального в смысле расстояния (10) к Колмогоровским поперечникам для всех 7ïr, г G [а, 0\ — непростой вопрос из теории приближений. Однако известно, что для случая d = 1 и пространств Tip в качестве такого семейства С = {Ln} можно взять конечномерные пространства тригонометрических полиномов, см. [36] Отсюда получаем такое следствие:

Следствие. Предположим, что для меры р выполняются условия (6) и (7). Пусть такэ/се 0 < а < (3 < со — фиксированные числа, и H имеет вид H(ot,P) = {H}., а < г < р}. Тогда существует универсальный для всех г оценщик fz и такие полоэ/сительные константы С\(Н,р, a),C2{Ti, р, а), что если fp G то верно неравенство: г

Рr{£(fz) - S{fp) >е}< e-Ci-me\ как только е ■ mш? . ( JÎL) 1+2г > с2.

1п 772/

Известно, что Ti\ С Ti\ при 0 < s < г. Отсюда ясно, что последнее условие на

2 « б и m в предыдущем утверждении можно всегда заменить на такое: е-т1+2<* •

Результаты диссертации в разное время докладывались и обсуждались на следующих семинарах механико-математического факультета МГУ: «Непараметрическая статистика и временные ряды» (руководители - д.ф.-м.и., профессор Ю.Н. Тюрин, д.ф.-м.п., профессор В.Н. Тутубалин, к.ф.-м.н., доцент М.В. Болдин); «Большой Кафедральный Семинар кафедры теории вероятностей»; «Статистическая теория обучений и её применения» (руководитель - д.ф.-м.п., профессор C.B. Конягин); «Теория приближений и приложения» (руководители - д.ф.-м.н., профессор, чл.-корр. РАН Б.С. Кашин, д.ф.-м.н., профессор C.B. Конягин); а также представлялись на ряде международных конференций: «25-я Европейская Конференция по Математической Статистике» (Осло, 2005); «Математические основы теории обучений II» (Париж, 2006); «26-я Европейская

Конференция по Математической Статистике» (Торупь, 2006); Российско-Скандинавский Симпозиум «Теоретическая и Прикладная Теория Вероятностей» (Петрозаводск, 200G). Основные результаты диссертации опубликованы в работах [27, 28, 29].

Автор глубоко благодарен своему научному руководителю профессору Ю.Н. Тюрину за постоянное внимание к работе, а также Е.Д. Лившицу, профессору В.Н. Темлякову и профессору C.B. Конягину за многочисленные полезные и плодотворные обсуждения.

Список литературы диссертационного исследования кандидат физико-математических наук Рафиков, Евгений Геннадьевич, 2007 год

1. A. Barron. Complexity Regularization with Applications to Artificial Neural Networks. Nonparamctric Functional Estimatoin, Kluwer, Dordrecht (1991), p. 561-57G.

2. P. Bartlett. Haussler's Packing Number Bound. Unpublished.

3. B. Carl. Entropy Numbers, s-Numbers, and Eigenvalue Problems. Journal of Functional Analysis, 41 (1981), p. 290-306.

4. F.Cucker, S.Smale, On the mathematical foundations of learning, Bulletin of AMS, 39 (2001), p.1-49.

5. T.Cover, J.Thomas. Elements of Information Theory, Wiley (1991).

6. L. Devroye. Bounds for the Uniform Deviations of Empirical Measures. Journal of Multivariate Analysis, 12 (1982), p. 72-79.

7. Л.Деврой, Л.Дьёрфи. Непараметрическое оценивание плотности. L1-подход. Пер. с англ., Мир (1988).

8. L.Devroye, L.Gyorfi, G.Lugosi. A Probabilistic Theory of Pattern Recognition, Springer (1996).

9. A. Dvoretzky, J. Kiefer, J. Wolfowitz. Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator. Annals of Mathematical Statistics, 27 (1956), p. 642-669.

10. R. DeVore, G. Kerkyacharian, D. Picard, V. Temlyakov, On Mathematical Methods of Learning. IMI Preprints 10 (2004), p.1-24.

11. R. DeVore, G. Kerkyacharian, D. Picard, V. Temlyakov, Mathematical methods for supervised learning, IMI Preprints 22 (2004), p.1-51.

12. R. Dudley. A course on empirical processes. Ecole d'Eté de Probabilités de Saint-Flour XII-1982, 1097, p 1-142, Springer-Verlag, 1982.

13. A. Dembo, О Zetouni. Large Deviation Techniques and Applications. Springer, 1998.

14. L. Gyorfi, M. Kohler, A. Krzyzak, H. Walk. A Distribution-Free Theory of Nonparametric Regression, Springer Series in Statistics (2002).

15. W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58 (1963), p. 13-30.

16. И.Ибрагимов, Р.Хасьминский. Асимптотическая теория оценивания, Наука (1979).

17. А.Колмогоров. Теория информации и теория алгоритмов, Наука (1987).

18. S. Konyagin, V. Temlyakov. The Entropy in the Learning Theory. IMI Preprints 05 (2004), p.1-18.

19. S. Konyagin, V. Temlyakov. The Entropy in the Learning Theory. Error Estimates. IMI Preprints 09 (2004), p. 1-25.

20. G.Lugosi, Pattern Classification and Learning Theory, In Principles of Nonparametric Learning, Springer, Viena (2002), p.5-62.

21. L. Le Cam. Convergence of Estimates Under Dimensionality Restriction. Annals of Statistics, 1 (1973), p. 38-53

22. M. Ledoux, M. Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer Verlag, New York, 1991.

23. G. Pisier. The volume of convex bodies and Banach space geometry. Cambridge University Press, (1989).

24. D. Pollard. Convergence of Stochastic Processes. Springer-Verlag, 1984.

25. E. Рафиков. Оценивание функции регрессии в случае неограниченных откликов. Математические Заметки, 79 (2006), No 6, стр. 231-235.

26. Е.Рафиков. О скорости сходимости частот к вероятностям. Обозрение прикладной и промышленной математики, 13 (2006), No 3, стр. 632-643.

27. Е.Рафиков. Обучение функции регрессии для неограниченных откликов. Депонировано в ВИНИТИ РАН. 2006. N1621-B2006.

28. И.Санов. О вероятностях больших уклонений случайных величии, Мат. сборник, 42 (1957), р.11-44.

29. В. Темляков. Нелинейные Колмогорвские поперечники. Математические Заметки, (63) (1998), стр. 891-902.

30. V. Temlyakov. Optimal Estimators in Learning Theory. IMI Preprints 23 (2004), p.1-29.

31. V. Temlyakov. Approximation in Learning Theory. IMI Preprints 05 (2005), p.1-43.

32. M. Talagrand. Sharper Bounds for Gaussian and Empirical Processes. The Annals of Probability, 22, No. 1 (1994), p. 28-76.

33. M. Talagrand. New Concentration Inequalities in Product Spaces. Invent. Math., 126 (1996), p. 505-563.

34. В.Тихомиров. Теория приблиоюений. Совр. проблемы математики. Фундаментальные направления, 14 (1987), (Итоги науки и техн.), ВИНИТИ АН СССР.

35. В. Вапиик, А.Червоненкис. Восстановление зависимостей по эмпирическим данным. Наука, (1979).

36. V. Vapnik. Statistical Learning Theory. Wiley Interscience, 1998.

37. В. Вапиик, А. Червоненкис. О равномерной сходимости относительных частот событий к их вероятностям. Теория вероятностей и приложения, 16, No. 2 (1971), стр. 264-280.

38. В. Вапник, А. Червоненкис. Необходимые и достаточные условия для равномерной сходимости средних к математическим ожиданиям. Теория вероятностей и приложения, 26, No. 3 (1981), стр. 532-553.

39. В. Вапник. А. Червоненкис Теория распознавания образов. Статистические проблемы обучения. Наука, (1974).

40. S. Van de Geer. Empirical Processes in M-Estimation. Cambridge University Press, New York (2000).