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

Московский государственный университет имени М.В. Ломоносова Механико-математический факультет

003054040

На правах рукописи УДК 519.21, 519.234

Рафиков Евгений Геннадьевич

ЭФФЕКТ КОНЦЕНТРАЦИИ МЕРЫ В СТАТИСТИЧЕСКИХ ЗАДАЧАХ НЕПАРАМЕТРИЧЕСКОГО ОЦЕНИВАНИЯ.

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва 2007

003054040

Работа выполнена на кафедре теории вероятностей Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор Ю. Н. Тюрин

Официальные оппоненты: доктор физико-математических наук,

доцент В. В. Ульянов

кандидат физико-математических наук, доцент С. А. Пирогов

Ведущая организация: Математический институт Стеклова РАН

Защита диссертации состоится 16 марта 2007 года в 16 часов 15 минут на заседании диссертационного совета Д.501.001.85 в Московском государственном университете имени М.В. Ломоносова по адресу: 119992, ГСП-2, г. Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета (Главное здание, 14 этаж).

Автореферат разослан 16 февраля 2007 года.

Учёный секретарь диссертационного совета Д.501.001.85 в МГУ, доктор физико-математических наук, профессор

Общая характеристика работы

Актуальность темы.

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

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

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

00

Prfsup |Fm(x) - F(x)I > t/^г) 2 V(-l^V2^, при тп-> со.

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

Prisup |Fm(a;) - F(x)| > 1} < С ■ e~2т'г,

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

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

Prjsup |Fm(x) - F{x) I >t\<K- e-(2-Q>'mi2.

Эмпирический процесс, который фигурирует в указанных выше результатах, является частным случаем более общего объекта:

sup |РшИ) - Р(Л)|, (1)

ЛеЛ

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

'И.Санов, О вероятностях больших уклонении случайных величин, Мат. сборник, 42 (1957), р.11-44. JA.Dembo, O.Zeitouni, Large Deviations Techniques and Applications, Springer (1998).

посвящена изучению этой задачи при определённых условиях на вероятностную меру Р(-) и набор множеств А3'4,5 Для фиксированного множества А и вероятностной меры Р(-) по закону больших чисел имеет место сходимость почти наверное Pm(yl) — Р(А) —> 0 при m —► оо. Более того, известное неравенство Хёфдинга даёт следующую (неасимптотическую) оценку на скорость сходимости :

Pr{| Рт(А) - Р(Л)| >t}< 2e~2mt\

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

Prisup | Рт{А) - Р(А)| >t}< 2\А\ ■ е~2т4\

АеА

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

Часть результатов в этой области посвящена тому, что на неизвестную меру Р(-) накладываются дополнительные естественные условия. Так, важным является случай, когда мера Р(-) и семейство А таковы, что множество значений мер {Р(А), А £ .4} отделено от некоторой окрестности 1/2. Улучшению оценок на поведение вероятностных хвостов для (1) в этом случае посвящена первая часть нашей диссертации. В качестве числовой характеристики такой отделимости мы используем разновидность информации Кулъбака-Лейблера, играющую важную роль в теории информации.6,г Близкие характеристики, такие как расстояние Кулъбака-Лейблера, используются для решения задачи оценивания плотности8, а также в асимптотической теории оценивания.9

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

3В.Валник, А.Червоненкис, Теория распознавания образов, Наука (1974).

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

5L.Devroye, L.Gyorfi, G.Lugosi, Л Probabüistic Theory of Pattern Récognition, Springer (1996).

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

7T.Cover, J.Thomas, Éléments of Information Theory, Wiley (1991).

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

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

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

Вторая часть диссертации посвящена современным проблемам регрессионного анализа. Пусть IgR11 and У 6 К — некоторые Борелевские множества. В зависимости от предположений о характере неизвестной зависимости между а: б .X" и у &Y известен ряд классических постановок задачи обучения по конечной выборке.

Так в теории приближений считается, что имеется детерминированная неизвестная зависимость на произведении X xY. Точнее, предполагается, что для точек из известного конечного набора z = {(ii,yi),. ■., (хт,ут), X{ 6 X,yi € У} верно соотношение yi = f(xi),i = 1,... ,т, где / принадлежит некоторому заранее известному функциональному классу 7i. Задача состоит в нахождении наилучшего приближения к / внутри класса "Н. Ошибка приближения обычно измеряется в Lp-норме по отношению к мере Лебега на X, где 1 < р < оо.

В случае, когда допускается какая-то случайность на характер зависимости между rr-ами и у-ами, говорят о теории оценивания функции регрессии. Рассматривается класс моделей вида у = f(x) + e, где / G "Н, а е — случайная величина. Например, считается, что для множества z = {(^1,1/1)1 • • •. (хт,Ут)> xi € X, yi еУ} выполняются равенства yi = f(x() + где xi,..., хт фиксированы, а б, — независимые одинаково распределённые случайные величины с Ее, = 0. Задача, как и выше, состоит в том, чтобы построить некоторое приближение fz для / (или оценку /), оптимальное в смысле Е(||/—/2||2) в одной из стандартных норм. Также рассматривается постановка задачи, когда "входы" xi,...,xm сами случайны и как-то распределены в соответствии с неизвестным вероятностным законом на X.10

В своей работе мы имеем дело с задачей, когда считается, что произведение Z = X х Y снабжено некоторой вероятностной Борелевской мерой р, а обучающие примеры z — суть случайная р-выборка длины т. Задача заключается в оценивании функции регрессии у-ов по х-ам, /Дх) = E{j/|a;}. Пусть рх —

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

это проекция меры р на X. Для описания качества оценивания мы используем общепринятую характеристику скорости убывания вероятностных хвостов

Pr{||/,-/.|U,(«>><}. (2)

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

В ряде случаев, когда известно поведение классических в теории приближений характеристик класса "Н, таких как энтропийные числа и Колмогоровские поперечники, нами получены экспоненциальные оценки убывания (2) при согласованном поведении mat. Они являются обобщением результатов, полученных в ряде недавних работ, основные из которых приведены в конце страницы.11,12

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

Цель работы.

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

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

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

Научная новизна.

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

1. Получена новая (неасимптотическая) оценка скорости сходимости эмпирических частот к вероятностям в терминах функции информации и размерности Вапника-Червоненкиса, обобщающая результаты Колмогорова, Смирнова, Кифера, Хёфдинга, Чернова, Вапника, Червоненкиса и Девроя.

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

3. Получен ряд оценок на поведение вероятностных хвостов отклонения функции-оценщика от функции регрессии в случае, когда класс гипотез задаётся в терминах энтропийных чисел и Колмогоровских поперечников.

4. Построен класс универсальных оценщиков функции регрессии и приведены оценки вероятностных хвостов их отклонения.

Методы исследования.

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

Теоретическая и практическая ценность.

Диссертация носит теоретический характер. Её методы и результаты могут найти применение в вероятностной теории распознавания образов и в теории оценивания функции регрессии.

Апробация работы.

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

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

Публикации.

Результаты диссертации опубликованы в 6 работал, список которых приведён в конце автореферата, см. [1-6].

Структура диссертации.

Диссертация состоит из введения, двух глав (разбитых на разделы), заключения и списка литературы, насчитывающего 34 наименования. Общий объём диссертации — 73 страницы.

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

Во введении приведён краткий исторический обзор по тематике работы, изложены цели и методы исследования, а также структура диссертации.

Пусть Xj,... ,Хт — независимые одинаково распределённые в сответствии с некторой вероятностной мерой Р(-) случайные величины в Евклидовом про-

странстве Обозначим через т длину выборки, а через РП1(-) — соответствующую эмпирическую меру. Первая глава посвящена изучению поведения вероятностных хвостов эмпирического процесса

8ир|рт(л)-р(л)|,

А&А

для случая, когда А — семейство Борелевских множеств в Rd с конечной размерностью Вапника-Червоненкиса V — В предположении, что множество значений мер (Р(Л), А £ А} отделено от некоторой окрестности 1/2, мы улучшаем ряд известных классических оценок. Введём необходимые определения.

Определение. Наибольшее целое число V, для которого существует набор из У точек х\,.. .,ху, удовлетворяющих свойству

#|{хь...,ху} П А : А е = 2У,

называется размерностью Вапника- Червоненкиса семейства А.

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

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

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

р+ = inf Р (Л), р- = sup Р(Л).

АеА,Р(А)>1/2 АеА,Р(А)<1/2

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

Теорема 1. Пусть рА — критическое значение для семейства множеств А с конечной размерностью Вапника- Червоненкиса У. Тогда для некоторых положительных констант М = М(рА, У), К = К(У) и to — toÍPA> У) nPU тп-t2 > М ut <to выполняется оценка

Рг{зир|Рт(Л)-Р(Л)| >t}< K-(mt2)2V+i-exp{-m-mm(H(pA+t>PA),H(pA-t,pA))}. АеА

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

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

А = {{х :< w, х > +w0 > 0} : w € Rd, w0 € R} имеем V(A) - d + 1,

для семейства отрицательных ортантов

А — {(—оо, xi] х • - • х (—00, xd] : (xi,..., xd) e Rd} верно V(A) = d.

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

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

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

Prjsup | Рт(Л) - Р(Л)| > i} < 4(^У ■ е-т<2/8.

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

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

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

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

Pr{sup |Рт(Л) - Р(А)| > i} < K(t, V) ■ (mt2)v ■ е~т-фМ, когда mt2 > С, (3) АеЛ

Здесь С — некоторая константа, не зависящая от t, v — функция от V, a = 712, где 7 € (0,2].

Нескольким авторам удалось улучшить константы из первых оценок Вапника и Червоненкиса. Отметим здесь лишь, что Деврой (L.Devroye)15 получил оптимальный множитель е-2"1'', а Талагранд (М. Talagrand)16 — также и неулуч-шаемый показатель v = V — 1/2. Наше предположение о том, что множество |Р(А) А е А} отделено от некоторой окрестности 1/2, позволяет улучшить экспоненциальный множитель в оценках вида (3) и взять в качестве (¡>{t) выражение

<j>{t) = mт(Н{рл + t,pA),H(pA - t,pA)). (4)

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

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

Pr{(Pm(A) - Р(Л)) >t}< exp{-m • Я (Р(Л) +t), P(i))}, VA G A.

Талагранд выдвинул гипотезу о том, что наряду с ф(t) из выражения (4) в оценке (3) может быть сохранён оптимальный полиномиальный множитель (m£2)v~1/'2. Таким образом, Теорема 1 может рассматриваться как частичное решение гипотезы Талагранда. Условия отделимости (Р(А), А £ Л} от 1/2

I5L. Devroye, Bounds ¡or the Uniform Deviation of Empirical Measures, Journal of Multivariate Analysis, 12 (1982), p. 72-79.

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

означает, что рд ф 1/2. А значит для некоторого ¿о > 0 множества {рд + {рл — С ^ < ¿о не пересекаются с некоторой окрестностью 1/2. Из свойств расходимости Кульбака-Лейблера следует, что для таких £ экспоненциальный показатель в Теореме 1 улучшен по сравнению с оптимальным в случае предположения свободы от распределения.

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

Теорема (Талагранд16). Пусть А. — ограниченное семейство измеримых множеств в К** с конечной V = У{Л). Пусть также Р(-) — некоторая Борелев-ская вероятностная мера на ар,4 — критическое значение для Л и Р(-). Тогда если рл ф 1/2, то для любого р £ (0,1) существуют положительные числа К{у) и Ц{(3,Ра,У), такие что при т ■ Ь2 > М(/?,р, V) и

Ь < Ьо((3,р,У) верно неравенство:

РгЬир I Рт(А) - Р(Л)| > *} < К (У) ■

АеА

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

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

Естественный подход при выборе оптимального / : M.d —* {0,1}, / € ТС состоит в минимизации эмпирической ошибки, определяемой как

1 т

0=1

Обозначим функцию, или как ещё говорят, "распознаватель", на которой достигается этот минимум, как fz. Ошибкой правила f &Н назовём Р-меру множества всех таких пар (х, у) £ Rrf х {0,1}, для которых f(x) ф у. Возникает естественный вопрос о том, насколько ошибка такого "распознавателя" fz близка к минимально возможной ошибке внутри класса 7i. Пусть Рт(-) — соответствующее выборке z эмпирическое рапределение. Тогда можно показать, что модуль интересующей нас разности оценивается сверху как

2 • sup |Рт(>1) — Р(Л)|, АеЛ

где семейство А представляет из себя следующий набор множеств:

{{х : f(x) = 1} х {0}} [j{{x : f(x) = 0} х {1}}, / е П.

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

Рг{|Рт(Л) - Р(А)| > i} < 2e~2mt\

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

Pr{sup |Рт(Л) - Р(Л)| > i} < 2\Л\ ■ е-2т4\

Ае.Д

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

Вторая часть диссертации посвящена задаче оценивания функции регрессии. Пусть Хсй^иУс! - Борелевские множества, и на их произведении Z — X У. Y определена Борелевская вероятностная мера р. Обозначим через /р : X —» Y функцию регрессии у на х, т.е. fp(x) = E{i/|a;}.

Мы изучаем задачу оценивания функции /р(х) по конечной р-выборке г = {^1,...,гт} : — (х{,у;),г = 1 ,...,т. Иногда эту задачу называют обучением функции регрессии.

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

Рг{||Л-/р||^рх)>е}. (5)

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

3 Си С2 > 0, такие что V* > 0 : р{\у\ > *} < Сх ■ ехр{-С2 ■ *2}, (6) /р(х) € Н, где Л — компактное подмножество в пространстве С(Х). (7) Свойство убывания вероятностных хвостов (б) также известно как равномерная сабгауссовостъ по у. Для функции / : X —» У, / € Ь2(Х,рх) её ошибкой назовём выражение

£{!) = ¡Ш-у?-¿р.

Известно, что минимум ошибки достигается на функции регрессии /р{х): £(/,) - , М £(/), при этом для / б Ь2(Х,Рх) : £(/)-£(/„) = \иЧР\\2Ых,Рх),

а значит для любого оценщика £ Ь2(X, рх) вероятностные хвосты (5) можно записать как

Рг{||/. - 1Л1лх,РХ) > 4 = РгЩ/.) - £Ш > с}-

Определим эмпирическую ошибку £х(/) как

1 m т i—'

»=i

и обозначим через fn,7. минимум эмпирической ошибки для пространства ТС:

hur = argmin£z(/). fe-н

Обозначим также через Л^Н, е) мощность е-сети для 7i в пространстве С(Х).

Теорема 2. Пусть мера р удовлетворяет условиям (6) и (7). Тогда найдутся положительные константы Ci(Tí,p) и С2{ТС,р), такие что для всех е > О справедливо неравенство:

Рг{£(/«,«) - £(fP) > е} <2N(H,c/C1(H,p)) ■ ехр{-С2(П,р) ■ те2}.

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

£п(Н) ~ ы{£ : 3/ь .. ., /2» € H : H С uJL.ifj + eU(C(X)))},

где U(C(X)) — единичный шар в пространстве С(Х).

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

Теорема 3. Пусть мера р удовлетворяет условиям (6) и (7) и для некоторых г > О, С > 0 и всех натуральных чисел п € N выполняются неравенства (■n{TL) < Сп~г. Тогда существуют положительные константы Ci(r,р),С2(г, р) > О, такие что

Рг{£■(/«,z) - £{fp) > е} < é~Cl'm(2, как только е • га® > С2.

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

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

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

Лемма 5. Существуют константы Cj(Tí,p) > 0, j = 1,2, такие что для е > 0 верно:

Pr{sup I£(/) - £JJ)I > е} < 2N(H,e/Cl{H,p)) ■ ехр{-С2(Н,Р) ■ те2}, fen

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

\у\ < М р-п.н. для некоторого фиксированного М > 0, см.17,18,19. Наш основной вклад заключается в перенесении части их результатов на случай неограниченных у-ов.

Определение. Колмогоровским поперечником порядка п для семейства функций Н С С(Х) называется число dn(7-i,C(X)), определяемое как

dn(H,C(X)) = inf sup inf ||/ - g\\c{x), L•> ¡ен s£L„

где infx,n берётся no всем n-мерным линейными подпространствам в С(Х).

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

dn(H, С(Х)) < Сг • п\ п = 1,2,... (8)

v 2П

следуют неравенства для энтропийных чисел v:

еп(Н,С(Х))<С2-п-г, я = 1,2,... (9)

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

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

dn{li,C(X))<C-n-r, п = 1,2,...

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

Рг{£(/2) - £(fp) >е}< как только е • тгй? ■ (j^) ^ > С2.

"F.Cucker, S.Smale, On the mathematical foundations of learning, Bulletin of AMS, 39 (2001), p.1-49. lsR.DeVore, G.Kerkyacharian, D.Picard, V.Temlyakov, On Mathematical Methods of Learning. IMI Preprints, 10 (2004), p.1-24.

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

20B.Carl, Entropy numbers, s-numbers, and eigenvalue problems, J. Fhnct. Anal., 41 (1981), p.290-306.

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

Определение. Представим действительное число р > 0 в виде р — к + /?, где к E.N, и 0 < Р < 1 и определим класс Tip функций f : [0, l]d —> Ж следующими условиями. Скажем, что f £ Tip если и только если у / существуют все частные производные порядка к, все они удолетворяют условию Гёлъдера с параметром /3 на множестве [0, l]d, и ||/||с(Х) < 1-

Известно, что для пространства Ti = Tip энтропийные числа и Колмогоров-ские поперечники удовлетворяют неравенствам (8) и (9) с показателем г = p/d, см.21, что даёт нам экспоненциальные оценки для случая, когда пространство гипотез для fp(x) представляет хорошо изученный класс гладких функций Tip. Отметим, что оценщик из Теоремы 6 представляет из себя более сложную конструкцию, чем рассматриваемый ранее fn,z, на котором достигается минимум эмпирической ошибки для класса Ti.

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

Определение. Для подпространства L в пространстве непрерывных функций С(Х). определим расстояние до функционального класса Ti как

d(W1L):=supinf||/-s||00. (10)

feHSSL

Пусть £ = {Ln}™=l — последовательность n-мерных (п = 1,2,...) подпространств в С(Х), и0<а</?<оо — действительные числа. Пусть также С, D — некоторые фиксированные положительные константы и г € [а, /?]. Обозначим через Tir произвольное ограниченное семейство функций в пространстве С(Х), удовлетоворяющее свойствам:

d(Tiri Ln) < С ■ n-r, n = 1,2,...; sup ||/||cw < D.

fe-Hr

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

H(a,p) = {HT,r e[a,/3]},

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

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

Теорема 7. Лредпложим, что для меры р выполняются условия (6) и (7), где H имеет вид 7i = 7i(a,j3) и 0 < а < ¡3 < оо. Тогда существует универсальный оценщик fz и такие положительные константы Ci(7i, р, a), С2(Н, р, а), что если fp £ Tir С /?), для некоторого г £ [а,/?], то верна оценка

РЛШг) - £(fP) > е} < е'с' те\ как только е • mïfe • ^ > С2.

Оценка этой теоремы слабее, чем предыдущий результат, однако и пространство Л теперь гораздо шире. Существование универсального семейства конечномерных подпространств L = {Ln}, оптимального в смысле расстояния (10) к Колмогоровским поперечникам для всех TtT, г £ [а, /9] — непростой вопрос из теории приближений. Однако известно, что для случая d, = 1 и пространств Ц}р в качестве такого семейства С = {Ln} можно взять конечномерные пространства тригонометрических полиномов, см.21 Отсюда получаем такое следствие:

Следствие. Предположим, что для меры р выполняются условия (6) и (7). Пусть также 0<а</3<оо — фиксированные числа и TL имеет вид %(а,¡3) = {7il, а < г < /?}. Тогда существует универсальный для всех г оценщик fz и такие положительные константы C\(TÎ, р, а), C2(Tt, р, а), что если fp £ 7ir, то верно неравенство:

Р<-{£(/*) - £(fP) > <0 < e"Ci mf2, как только е ■ mта? • (j~) > С2. Известно, что TLlr С И.\ при 0 < s < г. Отсюда ясно, что последнее условие на

2а

е и m в предыдущем утверждении можно всегда заменить на такое: е ■ ml+2« •

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

Список литературы

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

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

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

[4] Rafikov Е. About Regression Function Estimation in the Case of Unbounded Responses. // Тезисы докладов конференции «26-я Европейская Конференция по Математической Статистике», Торунь, 2006, стр. 345-346.

[5] Rafikov Е., Livshitz Е. About Universal Estimators in Learning Theory. // Тезисы докладов конференции «25-я Европейская Конференция по Математической Статистике», Осло, 2005, стр. 237-238.

[6] Rafikov Е. About Rates of Convergence of Empirical Frequencies to the True Probabilities. // Тезисы докладов Российско-Скандинавский Симпозиума «Теоретическая и Прикладная Теория Вероятностей», Петрозаводск, 2006, стр. 41-43.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать №.02,07

Формат 60 х 90 1/16. Усл. печ. л. £0

Тираж 100 экз. Заказ {{

Введение

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. Конягину за многочисленные полезные и плодотворные обсуждения.

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).