Аппроксимативные свойства функциональных классов и их приложения к задачам регрессии тема автореферата и диссертации по математике, 01.01.01 ВАК РФ

Математический институт им. В.А. Стеклова Российская академия наук

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

004609323

Малыхин Юрий Вячеславович

Аппроксимативные свойства функциональных классов и их приложения к задачам регрессии

Специальность 01.01.01 — математический анализ

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

3 0 СЕН ?щ

Москва - 2010

004609323

Работа выполнена в отделе теории функций Математического института им. В.А. Стеклова РАН.

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

профессор Конягин Сергей Владимирович

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

профессор Магарил-Ильяев Георгий Георгиевич

кандидат физико-математических наук, старший научный сотрудник Червоненкис Алексей Яковлевич

Ведущая организация: Институт математики и механики

Уральского отделения РАН

Защита диссертации состоится 14 октября 2010 г. в 14 часов на заседании диссертационного совета Д.002.022.01 при МИАН по адресу: 119991, Москва, ул. Губкина, д.8 (9 этаж).

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

Автореферат разослан У МяТ.Я^гЯ, 2010 г.

Ученый секретарь диссертационного совета Д.002.022.01 при МИАН доктор физико-математических наук, профессор Ватутин В.А.

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

Актуальность темы. В настоящее время многие методы и идеи теории приближений используются в математической статистике. С середины 20-го века в математической статистике начался переход от классической, "параметрической" парадигмы, в которой оцениваемый параметр принадлежит конечномерному евклидовому пространству, к современной "иепа-раметрической", в которой это уже не так. Возникла необходимость работы с существенно бесконечномерными объектами, такими как, скажем, множество функций плотности, удовлетворяющих определенному условию гладкости. Это привело статистиков к активному использованию общих понятий из функционального анализа и теории функций, а позже — из теории приближений.

Так, в задаче оценивания функции регрессии f(x) — Е(у|х = х) по выборке (xi,yi),..., (хп, уп) часто предполагается, что / принадлежит известному функциональному классу Т. В этом случае как методы построения оценок функции регрессии, так и наилучшая возможная точность оценивания определяются аппроксимативными свойствами Т.

Важнейшими аппроксимативными свойствами функциональных классов являются е-энтропия и колмогоровские поперечники. Использование этих характеристик в математической статистике восходит к Л. Jle Каму, H.H. Ченцову, И.А. Ибрагимову и Р.З. Хасьминскому, В.Н. Вапнику и А.Я. Червопенкису, J1. Бирже и относится к концу 1970-х — началу 1980-х годов: [1, 2, 3, 4]. В настоящее время применение теории приближений в математической статистике вызывает всё больший интерес. Отметим работу С. Смейла и Ф. Кукера [5] 2001 года, где явно указывается на фундаментальную роль теории приближений в теории машинного обучения. Эта работа привлекла внимание к статистическим проблемам многих специалистов по теории аппроксимации: Р. ДеВора, В.Н. Темлякова, C.B. Конягина, и других.

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

Ярким примером является псевдоразмерностъ, возникшая как обобщение VC-размерности на случай R-значных функций. Изначально VC-размерность была введена Вапником и Червоненкисом [6] как комбинаторная характеристика семейств множеств, нужная для обоснования сходимости некоторых статистических методов оценивания. Многие важные классы функций имеют конечную псевдоразмерность: линейное пространство функций размерности п, множество рациональных дробей вида P/Q,

с^ Р < п, с^ < т, множество кусочно-полиномиальных функций степени пстп нефиксированными узлами, множество малочленов из не более чем <1 мономов. Вычислениями псевдоразмерности различных функциональных классов занимались ряд авторов: П. Ассуа, А Андрианов, М. Карпинский, А. Макинтайр и другие. Около 10 лет назад появились работы В. Майорова и Дж. Ратсаби, где исследовались порядки приближения множеств классами конечной псевдоразмерности.

Другим примером является локальная энтропия. Многие результаты, связывающие точность оценивания с метрической энтропией пространства параметров, оказывались верны не в полной общности, а лишь при определенных ограничениях па поведение е-эптропии. Ещё у Ле Кама в работе [1] 1973 года на е-сети накладывались некоторые ограничения "локального" характера. В своей книге [2] Ле Кам ввёл так называемую размерность I), являющуюся локальным аналогом е-энтропии. Позже это понятие в несколько измененном виде переоткрывалось разными авторами и успешно применялось для характеризации сложности статистических задач [7, 8]. Однако, несмотря на свою важность, локальная энтропия сама по себе практически пе изучалась.

Ещё одной разновидностью энтропии, пришедшей из математической статистики, является так называемая скобочная энтропия, являющаяся в некотором смысле средним между энтропией в Ь\ и Ь^. Скобочная энтропия берет начало из работ Дж. Блюма [9] и Дж. Дехардта [10], в которых авторы обобщали классическую теорему Гливенко-Кантелли. В настоящее время скобочная энтропия активно используется в математической статистике наравне с УС-размерностью. Схожие конструкции имеются в теории приближения в связи с односторонними приближениями, однако взаимосвязь не вполне изучена.

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

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

Методы исследований. Используются стандартные методы действительного анализа и теории функций, оригинальные комбинаторные конструкции, а также современные методы теории вероятностей.

Научная новизна. Результаты диссертации являются новыми и состоят в следующем:

1. Построены примеры классов со сколь угодно большим отношением поперечников рп и sm при т, немного меньшем, чем п.

2. Вычислены асимптотики локальной энтропии некоторых функциональных классов.

3. Получен критерий конечности скобочной энтропии для классов, инвариантных относительно сдвига.

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

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

Апробация работы. Результаты настоящей диссертации докладывались на научном семинаре по теории функций под руководством д.ф.-м.н. профессора Б.С. Кашина, д.ф.-м.н. профессора C.B. Конягина в 2006-2009 г., на научном семинаре по теории функций под руководством д.ф.-м.н. профессора С.А. Теляковского в 2007-2010 г., на Саратовской зимней школе "Современные проблемы теории функций и их приложения" в 2008 г., на международной конференции по математической статистике в г. Марсель, Франция, 2009 г.

Публикации. Результаты диссертации опубликованы в 5 работах автора, список которых приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы, содержащего 58 наименований. Объем диссертации составляет 63 страницы.

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

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

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

Дадим необходимые определения. Пусть I — некоторое множество. Обозначим через В{1) пространство ограниченных функций /: I —> К, снабженное нормой |[/|| = вир |/(д;)|. Рассмотрим непустое множество \¥ С

хе1

В(1).

Определение. Псевдоразмериостыо с11тр(И/) множества XV называется максимальное число п, такое что существуют точки ..., хп 6 I и числа 1/1,...,уп £ К, удовлетворяющие условию: для любого набора знаков <Т1,..., ап 6 {—1,1} найдется функция / € IV, такая что

«■¿(/(^г) - Уг) > о, г = 1,..., п.

Определение. Псевдоразмерностиым поперечником множества называется величина

р„(Ж):= т {¿^Б), где точная нижняя грань берется по множествам 5 псевдоразмерности ^ п,

«5) := 8щ>ЫШ-Ц.

Определение. Раздробляющим поперечником зп{\¥) множества У/ называется точная верхняя грань таких е ^ 0, что существуют точки хо, • • •, хп е I и числа уо,...,уп £ К, удовлетворяющие условию: для любого набора знаков сто,..., ап 6 {—1,1} найдется функция / такая что

- Уг) ^ е, г = 0,...,п.

Поперечник рп(ТУ), введенный Майоровым и Ратсаби [11], дает оценку снизу на величину приближения IV множествами псевдоразмерности п. Нетрудно проверить, что рп(№) ^ зп{у/)\ как правило, оценка рп снизу проводилась с помощью этого неравенства. Возникает вопрос о том, насколько это неравенство точное.

Верно ли, что существует абсолютная константа С, такая что рп{У^) ^ С-зп(V/) для всех ? Верно ли, что для каждого п существует число С(п), такое что рп(№) ^ С(п) • ¿„(Ж)? Ответ в обоих случаях отрицательный, как показывает следующая теорема.

Теорема 1.1. Для любого n^2u любого С > О найдутся множества I и W С В(1), такие что pn(W) > С • s„(W).

Следствие 1.1. Существуют множества I и W С В(1) такие, что lim pn{W)/sn{W) = оо.

п—юо

Доказательство носит комбинаторный характер; множество W явно строится. Используя те же идеи, но значительно более громоздкие конструкции, этот результат удается усилить (при больших п).

Теорема 1.2. Для достаточно большого п и любого С > 0 найдутся множества I и W С В{1), такие что pgn(W) > С ■ Sgn(jy).

Вторая глава состоит из трех разделов.

Раздел 2.1 посвящен локальной энтропии. Нами доказываются простейшие свойства локальной энтропии и приводится ряд примеров. В частности, достаточно точно вычисляется локальная энтропия класса кусочно-полиномиальных функций.

Дадим необходимые определения. Пусть (X, d) — метрическое пространство, В(х, г) — замкнутый шар радиуса г с центром в х, А С X, е > 0.

Определение. Минимальное количество элементов в е-сети для А в X назовем энтропийным числом А в X и обозначим Ne(A,X). Логарифм этого числа называется е-эптропией А.

Определение. Упаковочным числом множества А называется максимальное количество точек в А с попарными расстояниями не меньше е. Обозначение: Р£{А).

Теперь определим локальные аналоги Ne и Р£. Для этого зафиксируем параметр с > 1.

Определение. Локальным энтропийным числом множества А в X называется величина

N£(c, А, X) = sup Ne(A П В{х, се), X). хех

Логарифм этого числа назовем локальной е-эптропией А.

Определение. Локальным упаковочным числом множества А называется величина

Ре(с, А) = sup{n: 3xi,.. .,хп е А: Vz < j е < d(xi: Xj) ^ се}.

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

Соотношение / > д для функций /,д. (0,ео) —> (0,+со) означает, что

Üm f(z)/9(e) > 1, а f~g — что lim f{e)lg{e) = 1. £->+0

Пусть Sm,n — множество функций /: [0,1] —> R, таких что существует разбиение отрезка [0,1] на т ^ 3 частей, на каждой из которых / является многочленом степени меньше п. Обозначим Lp := Lp[0,1] и Uq :=

{/: ll/IU, ^ 1}.

Теорема 2.1. Пусть 1 ^ р < q ^ +оо, т' := I/t^J- Имеют место следующие соотношения:

log Ре(с J Sjn,n n Uq, Lp) qp ( ,

_ log(l/e) ~д-Лт +

log SmtTl П Uq, Ьр) ^ qp ,

2m'

-m,

log(l/e)

logNe(Sm¡nD Uq,Lp) jmn + p(m — 1), если п^Щ^,

logíl/e) I SE-rrí + {m~ m')n + (~1Г+1р, иначе.

(Если q = oo, мы полагаем = p.)

В случае p ^ q, как легко показать, энтропийные числа бесконечны. Раздел 2.2 носит вспомогательный характер; приведенные там результаты используются в третьей главе.

В разделе 2.3 рассматривается скобочная энтропия. Исследуется, когда класс функций является скобочно-компактным, то есть имеет конечную скобочную е-энтропию для любого е > 0. Дадим соответствующие определения.

Нам будет удобно считать, что функции заданы на окружности Т = R/Z с мерой Лебега ц. Мы будем рассматривать измеримые функции Т —>■ К, для которых конечен интеграл

И/Их := (\f(x)\dx. J т

Для двух таких функций Р, Q введем обозначение

[P,Q]:={f:Vxe Т Р(х) ^ f(x) < Q(x)}.

Определение. Скобочной е-энтропией класса Т называется минимальное число N, такое что существуют функции Pi,..., Pjv и Qi,. ■. ,Qn, такие что

N

-РсЦP»Qi\ и WPi-QiW^s, i = l,2,...,N. ¿=i

Класс T называется скобочно-компактным, если его скобочная е-энтропия конечна для любого е > 0.

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

Определение. Пусть / — ограниченная измеримая функция Т -> К. Усредненным модулем непрерывности функции / порядка 8 > 0 называется величина

r(f,5)= [( sup f(x)~ inf f(x)]dt.

Отметим, что т(/, J) —> 0 при S —> 0 тогда и только тогда, когда / интегрируема по Риману. Модуль т был введен Б. Сендовым и В. Поповым [12].

Теорема 2.3. Класс J7, инвариантный относительно сдвигов, является скобочно-компактным, если и только если выполнены следующие условия:

• Г равномерно ограничен: sup |/(х)| < оо;

/ еТ,хвТ

• усредненные модули непрерывности функций из Т равномерно стремятся к нулю:

limsupr(/, 5) = 0. o/eF

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

Пример 3.1. Пусть Л — семейство сдвигов на Т характеристической функции множества [0,1) П Q. Тогда А имеет псевдоразмерность 1, но не является скобочно-компактным (по лебеговой мере).

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

Пусть X = К^, У = [—М, М], (х, у) Е ХхУ — случайный вектор с неизвестным нам распределением р. Требуется по выборке ъ = ((ж,-, Уг))2=1 независимых векторов, распределенных в соответствии с р, построить функцию /2, аппроксимирующую функцию регрессии

/Дх) = Е(у\х).

Отображение называется оценкой функции регрессии.

Отметим, что функция регрессии /р минимизирует ошибку

£(/) := Е((/(х) - у)2).

Более того, имеет место равенство

од-ед) = и/-/рии*)>

где рх — проекция распределения р на X. В силу этого равенства, погрешность приближения Д — /р естественно измерять в норме пространства £2 (рх).

В приведенной выше постановке задачи необходимо как-то ограничить класс возможных распределений р. Мы будем налагать условия лишь на функцию и меру рх■ Относительно функции /р предположим, что она принадлежит известному функциональному классу Т. Мера рх будет, в зависимости от ситуации, либо фиксированной и известной нам, как в разделе 3.3, либо произвольной, как в разделе 3.2.

Теорема 3.1. Для любого е Е (0,1) существует оценка /ъ такая, что для любой меры р, для которой /р Е Т, выполняется неравенство

~ 1р\\ь2(рх) ^ с1£) ^ с2 ехр(с3 • ус(7", С4б) \og{A:/е) — с5те ),

где = Сг{М).

Теорема опирается на известные оценки близости ¿2-норм по эмпирической и обычной мерам, а также на современные оценки энтропии через комбинаторную размерность.

Рассмотрим случай фиксированной меры рх = Р- Пусть

Р{е):=Р£( 20,Т,Ь2(р)).

Имеет место следующая теорема.

Теорема 3.2. Пусть

Ve > О Р(е)^(р(е),

причем невозрастает. Существует оценка fz, такая что для любой меры р с рх = ß и fp € Т, и любого е > О выполняется неравенство

Pm{z: ||/z - fP|| > £} ^ ci^(e/16)exp(-c2m£2),

где Ci = Ci (M).

Этот результат дополняет следующую теорему, дающую нижнюю оценку минимаксной погрешности.

Теорема G (Р. ДеВор, Ж. Керкичирян, Д. Пикар, В. Темляков [8]). Пусть Y = [—1,1]. Предположим, что при некотором г) > 0 функции {/¿}, i = 1,..., Р{2г]) из определения Р удовлетворяют условию ||/г||с(;г) ^ Тогда для любой оценки fz найдется г 6 {1,..., Р(2г?)} такой, что

Wh-fiWbM min(l/2, (Р(2г})-1)^2е-^т^е), m = 1,2,...

В заключение приношу глубокую благодарность моему научному руководителю, доктору физико-математических паук, профессору Конягииу Сергею Владимировичу за постановку задач и постоянное внимание к работе, а также Рютину Константину Сергеевичу за многочисленные плодотворные обсуждения.

Цитированная литература

[1] L. Le Cam, "Convergence of estimates under dimensionality restrictions", Anna/s of Statistics, 1:1 (1973), 768-774.

[2] L. Le Cam, Asymptotic Methode in Statistical Decision Theory, SpringerVerlag, 1986.

[3] И.А. Ибрагимов, Р.З. Хасьминский, Асимптотическая теория оценивания, М.: Наука. Физматлит, 1979.

[4] В.Н. Вапник, А.Я. Червоиенкис, "Необходимые и достаточные условия равномерной сходимости средних к математическим ожиданиям", Теор. вер. и применения, 26:3 (1981), 543-563.

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

[6] B.H. Вапник, А.Я. Червоненкис, "О равномерной сходимости частот появления событий к их вероятностям", ДАН СССР, 181:4 (1968), 781-783.

[7] Y. Yang, A. Barron, "Information-theoretic determination of minimax rates of convergence", Annals of Statistics, 27:5 (1999), 1564-1599.

[8] R. DeVore, G. Kerkyacharian, D. Picard, V. Temlyakov, "Mathematical methods for supervised learning", J. Foundations of Computational Mathematu 6 (2006), 3-58.

[9] J. Blum, "On the convergence of empiric distribution function", Annals of Math. Statistics, 26:3 (1955), 527-529.

[10] J. Dehardt, "Generalizations of the Glivenko-Cantelli theorem", Annals of Math. Statistics, 42:6 (1971), 2050-2055.

[11] V. Maiorov, J. Ratsaby, "The degree of approximation of sets in Euclidean space using sets with bounded Vapnik-Chcrvonenkis dimension", Discrete Applied Mathematics, 86:1 (1998), 81-93.

[12] Б. Сендов, В. Попов, Усредненные модули гладкости, М.: Мир, 1988.

Работы автора по теме диссертации

[1] Ю.В. Малыхин, "Поперечники, связанные с псевдоразмерностью", Изв. РАН. Сер. матем., 73:2 (2009), 109-122.

[2] Yu.V. Malykhin, "Tight packing numbers: examples and basic properties", East J. on Approximations, 13:2 (2007), 135-152.

[3] Ю.В. Малыхин, "Усредненный модуль непрерывности и скобочная компактность" Матем. заметки, 87:3 (2010), 468-471.

[4] Ю.В. Малыхин, "Верхние оценки погрешности оценщиков в задаче непараметрической регрессии: адаптивный случай и случай неизвестной меры рх \ Матем. заметки, 86:5 (2009), 725-732.

[5] Ю.В. Малыхин, "Локальная энтропия в теории обучения", Матем. заметки, 80:6 (2006), 946-949.

Введение

Исторический обзор понятий, исследуемых в диссертации

Структура и основные результаты работы

1 Псевдоразмерность и связанные с ней поперечники

1.1 Определения и примеры.

1.2 Сравнение рп и зп

1.3 Сравнение рп и зт, т < п.

2 Энтропия

2.1 Локальная энтропия.

2.2 Связь энтропии и комбинаторной размерности.

2.3 Скобочная энтропия.

3 Оценки погрешности в задаче непараметрической регрессии

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

3.2 Случай неизвестной меры рх.

3.3 Случай известной меры рх.

В настоящее время многие методы и идеи теории приближений используются в математической статистике. С середины 20-го века в математической статистике начался переход от классической, "параметрической" парадигмы, в которой оцениваемый параметр принадлежит конечномерному евклидовому пространству, к современной "непараметрической", в которой это уже не так. Возникла необходимость работы с существенно бесконечномерными объектами, такими как, скажем, множество функций плотности, удовлетворяющих определенному условию гладкости. Это привело статистиков к активному использованию общих понятий из функционального анализа и теории функций, а позже — из теории приближений.

Проиллюстрируем сказанное на примере задачи регрессии. Задача регрессии состоит в аппроксимации функциональной зависимости среднего значения одной случайной величины от другой или нескольких других. Пусть, скажем, мы наблюдаем п значений (x\,yi), . . ., (хп,уп) случайных величин х и у с неизвестным нам распределением. Требуется оценить функцию регрессии f(x) = Е(у|х = х). Обычно предполагается, что / принадлежит известному функциональному классу Т. В этом случае, как методы построения оценок функции регрессии, так и наилучшая возможная точность оценивания определяются аппроксимативными свойствами Т. Отметим также, что в отсутствии шума (у = /(х) почти наверное) имеем Уг — i — I, и задача переходит в классическую для теории приближений задачу интерполяции.

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

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

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

Исторический обзор понятий, исследуемых в диссертации

Одной из важнейших аппроксимативных характеристик функциональных классов является е-энтропия. Её определение дается в случае произвольного метрического пространства. Пусть (X, d) — метрическое пространство. Обозначим через В(х:г) замкнутый шар радиуса г с центром в х.

Определение. Пусть А С X и е > 0. Минимальное количество элементов в е-сети для А в X назовем энтропийным числом А в X и обозначим N£(A,X). Логарифм этого числа называется е-энтропией А (в X).

Впервые идея о возможности характеризовать "массивность" компактов в метрических пространствах скоростью роста мощности их минимальных е-покрытий была высказана в 1932 году JI.C. Понтрягиным и Л.Г. Шни-рельманом в работе [42] (перевод см. в конце книги [6]). Оценки подобных величин позволили А.Г. Витушкину [7] доказать теорему о неизбежности понижения гладкости при представлении функции через суперпозицию функций с меньшим числом переменных. В обзорной статье 1960 года

A.Н. Колмогоров и В.М. Тихомиров [10] систематизировали полученные ими и другими математиками результаты, касающиеся е-энтропии множеств.

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

Использование энтропии в статистике восходит к Л. Ле Каму [31], H.H. Ченцову [12], И.А. Ибрагимову и Р.З. Хасьминскому [8, 9], а также

B.Н. Вапнику и А.Я. Червоненкису [2, 5|, о работах которых мы расскажем позже. Л. Бирже [17, 18] развил идеи Ле Кама и получил достаточно общие результаты о минимаксной погрешности оценивания в терминах метрической энтропии пространства параметров. Среди большого количества последовавших работ отметим [53, 50, 52] и особо выделим работу Я. Янга и А. Бэррона [52], которые значительно уточнили и придали более завершенный вид результатам Бирже. Не вдаваясь в технические детали, поясним их результат в части регрессии. Янг и Баррон показали, что при оценивании функции регрессии / £ Т по выборке (х\, у\),., (хп, уп) погрешность определяется энтропией класса F в метрике d пространства Ь2{рх), где рх — распределение переменной X. Пусть fn обозначает оценку регрессии, тогда infsup d2{fnJ)^e2n, (1) fn f<=F где en определяется из условия logN£n{F,d) xn4

Важно, что результат Янга и Бэррона имеет место не в полной общности, а лишь при определенных ограничениях на поведение ^-энтропии. Ещё у Jle Кама в работе 1973 года на е-сети накладывались некоторые ограничения "локального" характера.

В книге [32] Jle Кам ввёл определение размерности, в терминах которой получил верхние оценки погрешности в задаче оценивания плотности. Для множества А в метрическом пространстве его размерность по Ле Каму D{e) определяется как минимальное число D, такое что любое подмножество А диаметра 25 ^ 2е может быть покрыто не более чем 2D множествами диаметра 5.

Янг и Бэррон, в упомянутой выше работе [52J, по-видимому, переоткрыли это понятие, применив его, в свою очередь, для нижних оценок. Их определение, впрочем, несколько другое: М1ос(е) есть максимально возможное количество точек множества А с попарными расстояниями больше е/2, содержащимися в некотором шаре радиуса е.

В работе [23] Р. ДеВором, Ж. Керкичиряном, Д. Пикар и В. Темляко-вым было дано определение "локальной энтропии" в несколько более общем виде — вместо постоянной "2" авторы вводят параметр с > 1. Приведем здесь их определение.

Определение. Локальным упаковочным числом множества А называется величина

Ре(с,А) = sup{n: 3xi,. ,хп 6 А: Уг < j е < d(xi1xJ) < се.}

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

В.Н. Вапник и А.Я. Червоненкис, при исследовании равномерного закона больших чисел, столкнулись, по существу, с несколько другим видом энтропии. Классический закон больших чисел утверждает, что для любого события А частота его появления в п независимых испытаниях Рп(А) сходится к его вероятности: Рп(А) —> Р(А) при п —> со (где сходимость понимается по вероятности или почти наверное). Вапником и Червоиенкисом был исследован вопрос о том, когда имеет место сходимость одновременно для целого класса событий А: lim sup IР(А) - Рп{А)I 0 пл.

В этом случае будем говорить, что выполнен равномерный закон больших чисел (РЗБЧ). Отметим, что первым примером РЗБЧ является классическая теорема Гливенко-Кантелли (1933) о равномерной сходимости эмпирической функции распределения к истинной.

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

Определение. Пусть А — семейство подмножеств некоторого множества X. Для точек . ,xr G X обозначим через Aa(xi, . ,хг) количество различных множеств вида АС\{Х\,., A G А. Функцией роста семейства А называется функция тА(г) — max ÄA(xi,., xr). x\,.,xr£X

Размерностью Ваппика-Червоненкиса dimyc(w4) называется максимальное число d такое, что mA(d) = 2d.

РЗБЧ для множеств конечной VC-размерности d следует [2] из неравенства

P(sup IР(А) - Pn(А)I > е) ^ бтл{2п) ехр(-^2(п - 1)) (2) АеД 4 и полиномиальной оценки функции роста к=о 4 7

Относительно (3) нужно отметить, что в оригинальных работах Вапника и Червоненкиса доказывалась чуть более слабая оценка. Одновременно и независимо (3) была получена в комбинаторной работе Н. Сойера [44], а также С. Шеллахом и Перлесом [46].

Обобщение (2, 3) на случай семейств функций содержится у Вапника и Червоненкиса [3, 4, 5]. В этом случае РЗБЧ означает следующее:

Нт эир гг->оо ^ яО-ЕДя) г=1

О П.Н.

Функцию роста заменяет так называемая УС-энтропия, являющаяся средним значением г-энтропии в пространстве Ь2 со случайной (эмпирической мерой). Комбинаторные величины типа УС-размерности позволяют оценивать энтропию в 1/2 (/-О сразу для всех мер /х, что позволяет получить РЗБЧ для функций. Оценки Вапника и Червоненкиса были в этом случае несколько завышенными; наиболее подходящим обобщением УС-размерности на классы М-значных функций оказалась псевдоразмерност,ъ, введенная Д. Хаусслером [27] и основанная на рассмотрениях Д. Поллар-да [41].

Определение. Пусть Т — семейство функций X —> М. Псевдоразмерно-стъю Т называется УС-размерность семейства подграфиков функций из сШМЛ - <Итус({{(я,г/) ах!:^ /(х)}: / € Т"}).

Приведем важные примеры множеств конечной псевдоразмерности.

• Линейное пространство функций размерности п имеет псевдоразмерность п.

• Множество рациональных дробей

Яп = {Р/д: с(3{х) Ф 0 при X <Е [0,1]} С В[0,1] имеет псевдоразмерность порядка п. Точнее, п ^ сНт-р Ип ^ 2п — 1. Более того, порядковая оценка псевдоразмерности справедлива и для обобщенных дробей, когда числитель и знаменатель берутся из линейных пространств размерности п.

• Множество кусочно-полиномиальных функций степени пет нефиксированными узлами имеет псевдоразмерность порядка тп.

• Множество малочленов {^Ук=1акх(1к} С -В(М) имеет псевдоразмерность сНтр £ [Зп, 4п — 1]. (Эти нетривиальные оценки получены в [28].)

В 90-е годы было понято, что псевдоразмерность даёт завышенные оценки в скорости сходимости в РЗБЧ. Действительно, даже очень маленькие колебания могут дать большую размерность. В работе [30] было предложено учитывать только "существенные" колебания. Соответствующая величина называлась разными авторами по-разному: "e-shattering" в [30], "Р7"-dimension в [13], "fat-shattering" в [16], "combinatorial dimension" в [43]. В данной работе выбрано последнее название.

Определение. Комбинаторной размерностью vc(Jr, е) класса Т порядка е > 0 называется максимальное п, такое что существуют точки xi,. ,хп и числа yi,-.-,yn со следующим свойством: для любого набора знаков G {-1,1} существует функция / £ J7, для которой

ViUixi) -Уг) > г = 1, . ,77,

Связь комбинаторной размерности и энтропии, лежащая в основе РЗБЧ, исследовалась далее в работах [13, 39, 43].

Работы Вапника и Червоненкиса были мотивированы обоснованием определенного статистического метода. Наличие именно VC-размерности (а не, скажем, линейной размерности) в оценках скорости сходимости в РЗБЧ привело многих статистиков к выводу, что сложность используемых классов функций (моделей) можно контролировать его VC размерностью. Было написано множество работ, в которых вычислялись подобные характеристики, в частности, [15, 14, 28, 29]. Приведем, однако цитату из обзора 3. Мендельсона [38]:

Unfortunately, the VC dimension and the fat-shattering dimension have become the central issue in machine learning literature. One must remember that the combinatorial parameters were introduced as a way to estimate the uniform entropy numbers. In fact, they seem to be the wrong parameters to measure the complexity of learning problems. Ironically, they have a considerable geometric significance as many results indicate."

Интерес к псевдоразмерности проявился также и в теории приближений. Г. Шапиро в работе [45] 1964 года использовал конструкции, аналогичные VC-размерности, для оценки снизу погрешности приближения классов функций классом обобщенных рациональных дробей. Позже Г.Е. Вор-рен [51] развил этот метод для оценки снизу погрешности приближения классом полиномов от многих переменных. В обеих работах авторы имели дело с приближающими множествами конечной псевдоразмерности. Впервые задачу о приближении множествами ограниченной псевдоразмерности в общем виде поставили В. Майоров и Дж. Ратсаби [35]. Ими был введен псевдоразмерностный поперечник рп, определяемый аналогично Колмого-ровскому, но с заменой линейной размерности на псевдоразмерность.

Определение. Пусть (X, || • ||) — банахово пространство вещественно-значных функций. Псевдоразмерностпым поперечником множества W называется величина

Pn(W):= mîd{W,S), О где inf берется по множествам S псевдоразмерности ^ п, d(W, S) := sup inf ||/ — h\\. f€Wh^S

Определение pn, впрочем, было мотивировано именно теми соображениями, что множества конечной псевдоразмерности удовлетворяют РЗБЧ и поэтому важны с точки зрения статистики. В ряде последовавших работ [35, 36, 33] вычисляются псевдоразмерностные поперечники для многих классических классов функций.

В случае равномерной метрики оценки Шапиро, Воррена и других авторов вытекают, по существу, из следующего простого утверждения: если vc(H/', е) > п, то pn(W) ^ е. Величину sup{e: vc(W,s) > п} C.B. Конягип предложил назвать раздробляющим поперечником и обозначить через sn; так это утверждение принимает вид

Pn(W) > 8n{W).

1. В.Н. Вапник, А.Я. Червоненкис, "О равномерной сходимости частот появления событий к их вероятностям", ДАН СССР, 181:4 (1968), 781-783.

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

3. В.Н. Вапник, А.Я. Червоненкис, "Теория равномерной сходимости частот появления событий к их вероятностям и задача поиска оптимального решения по эмпирическим данным", Автоматика и телемеханика, 2 (1971), 42-53.

4. В.Н. Вапник, А.Я. Червоненкис, "О методе упорядоченной минимизации риска", Автоматика и телемеханика, 8 (1974), 21-30.

5. В.Н. Вапник, А.Я. Червоненкис, "Необходимые и достаточные условия равномерной сходимости средних к математическим ожиданиям", Теор. вер. и применения, 26:3 (1981), 543-563.

6. Г. Волмен, В. Гуревич, Теория размерности, М.: Изд-во иностр. лит., 1948.

7. А.Г. Витушкии, "К тринадцатой проблеме Гильберта", ДАН СССР, 95:4 (1955), 701-704.

8. И.А. Ибрагимов, Р.З. Хасьминский, "Об оценке бесконечномерного параметра в гауссовом белом шуме", ДАН СССР, 236:5 (1977), 1053-1055.

9. И.А. Ибрагимов, Р.З. Хасьминский, Асимптотическая теория оценивания, М.: Наука. Физматлит, 1979.

10. А.H. Колмогоров, В.M. Тихомиров, "^-энтропия и е-емкость множеств в функциональных пространствах", УМЕ, 14:2(86) (1959), 3-86.

11. Б. Сендов, В. Попов, Усредненные модули гладкости, М.: Мир, 1988.

12. H.H. Ченцов, Стастистические решающие правила и оптимальные выводы, М.: Наука, 1972.

13. N. Alon, S. Ben-David, N. Cesa-Bianchi, D. Haussler, "Scale-sensitive dimensions, Uniform Convergence, and Learnability", J. of the ACM, 44:4 (1997), 615-631.

14. A. Andrianov "On pseudo-dimension of certain sets of functions" East J. on Approximations, 5:4 (1999).

15. P. Assouad, "Density and dimension (the Vapriik-Chervoncnkis class of subsets)", Ann. Inst. Fourier, 33:3 (1983), 233-282.

16. P. Bartlett, P. Long, R. Williamson, "Fat-shattering and the learnability of real-valued functions.", J. Comput. Syst. Sei., 52:3 (1996), 434-452.

17. L. Birge, "Approximation dans les espaces métriques et théorie de l'estimation", Z. Wahrscheinlichkeitstheorie verw. Gebiete, 65:2 (1983), 181-237.

18. L. Birge, "On estimating a Density using Hellinger Distance and Some Other Strange Facts", Prob. Theory and Related Fields, 71 (1986), 271-291.

19. L. Birge, P. Massart, "Rates of convergence for minimum contrast estimators", Prob, theory and related fields, 97 (1993), 113-150.

20. J. Blum, "On the convergence of empiric distribution function", Annals of Math. Statistics, 26:3 (1955), 527-529.

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

22. J. Dehardt, "Generalizations of the Glivenko-Cantelli theorem", Annals of Math. Statistics, 42:6 (1971), 2050-2055.

23. R. DeVore, G. Kerkyacharian, D. Picard, V. Temlyakov, "Mathematical methods for supervised learning",' J. Foundations of Computational Mathematics, 6 (2006), 3-58.

24. R.M. Dudley, A course on empirical processes, Springer Berlin, 1984.

25. F. Gao, J.A. Wellner, "Entropy Estimate For High Dimensional Monotonic Functions", J. Mult. Anal., 98 (2007), 1751-1764.

26. L. Gyorfi, M. Kohlcr, A. Krzyzak, W. Harro, "A Distribution-Free Theory of Nonparametric Regression", Springer Series in Statistics.

27. D. Haussler, "Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications", Inform,ation and Comput., 100 (1992), 78-150.

28. M. Karpinski, T. Wertner, "VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions", SI AM J. Comput. 22:6 (1993), 1276-1285.

29. M. Karpinski, A. Macintyre, "Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks", Annual acm symposium on theory of computing, 27 (1995), 200-208.

30. M.J. Kearns, R.E. Schapire, "Efficient Distribution-Free Learning of Probabilistic Concepts" J. of computer and system sciences, 48:3 (1994), 464-??.

31. L. Le Cam, "Convergence of estimates under dimensionality restrictions", Annals of Statistics, 1:1 (1973), 768-774.

32. L. Le Cam, Asymptotic Methods in Statistical Decision Theory, Springer-Verlag, 1986.

33. V. Maiorov, "Optimal non-linear approximation using sets of finite pseudodimension", East J. on Approximations, 11:1 (2005), 1-19.

34. V. Maiorov, J. Ratsaby, "On the Value of Partial Information for Learning from Examples", J. of Complexity, 13:4 (1997), 509-543.

35. V. Maiorov, J. Ratsaby, "The degree of approximation of sets in Euclidean space using sets with bounded Vapnik-Chervonenkis dimension", Discrete Applied Mathematics, 86:1 (1998), 81-93.

36. V. Maiorov, J. Ratsaby, "On the Degree of Approximation by Manifolds of Finite Pseudo-Dimension", Constructive Approximation, 15:2 (1999), 291-300.

37. P. Massart, E. Nedelec, "Risk bounds for statistical learning", Annals of Statistics, 34:5 (2006), 2326-2366.

38. S. Mendelson, "A few notes on Statistical Learning Theory", Lecture Notes in Computer Science, 2600 (2003), 1-40.

39. S. Mendelson, R. Vershynin, "Entropy and the combinatorial dimension", Inventiones Mathematicae, 152 (2003), 37-55.

40. R. Nickl, B. M. Potscherl "Bracketing Metric Entropy Rates and Empirical Central Limit Theorems for Function Classes of Besov- and Sobolev-Type", J. of Theoretical Probability, 20:2 (2007), 177-199.

41. D. Pollard, Convergence of stochastic processes, Springer-Verlag, 1984.

42. L.S. Pontrjagin, L. Schnirelman, "Sur une propiete metrique de la dimension", Annals of Mathematics, 33 (1932), 156-162.

43. M. Rudelson, R. Vershynin, "Combinatorics of random processes and sections of convex bodies", Annals of Mathematics, 164 (2006), 603— 648. '

44. N. Sauer, "On the Density of Families of Sets", J. of Combinatorial theory, 13:1 (1972), 145-147.

45. H.S. Shapiro, "Some negative theorems of approximation theory", Michigan Math J., 11:3 (1964), 211-217.

46. S. Shelah, "A combinatorial problem; Stability and order for models and theoies in infinitary languages", Pacific J. of Mathematics, 41:1 (1972), 247-261.

47. V. Temlyakov, "Optimal estimators in learning theory", Banach Center Publications, 72 (2006), 341-366.

48. V. Temlyakov, "Approximation in Learning Theory", Constructive Approximation, 27 (2008), 33-74.

49. A.B. Tsybakov, "Optimal Aggregation of Classifiers in Statistical Learning", The Annals of Statistics 32:1 (2004), 135-166.

50. S. van de Geer, "Estimating a regression function", Annals of Statistics, 18:2 (1990), 907-924.

51. H.E. Warren, "Lower bounds for approximation by non-linear manifolds", Trans. AMS, 133:1 (1968), 167-178.

52. Y. Yang, A. Barron, "Information-theoretic determination of minimax rates of convergence", Annals of Statistics, 27:5 (1999), 1564-1599.

53. Y.G. Yatracos, "Rates of Convergence of minimum distance estimators and Kolmogorov's entropy", Annals of Statistics, 13:2 (1985), 768-774.

54. Ю.В. Малыхин, "Поперечники, связанные с псевдоразмерностью", Изв. РАН. Сер. матем., 73:2 (2009), 109-122.

55. Yu.V. Malykhin, "Tight packing numbers: examples and basic properties", East J. on Approximations, 13:2 (2007), 135-152.

56. Ю.В. Малыхин, "Усредненный модуль непрерывности и скобочная компактность" Матем. заметки, 87:3 (2010), 468-471.

57. Ю.В. Малыхин, "Верхние оценки погрешности оценщиков в задаче непараметрической регрессии: адаптивный случай и случай неизвестной меры рх\ Матем. заметки, 86:5 (2009), 725-732.

58. Ю.В. Малыхин, "Локальная энтропия в теории обучения", Матем. замет,ки, 80:6 (2006), 946-949.