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

В настоящее время многие методы и идеи теории приближений используются в математической статистике. С середины 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 AA (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 со случайной (эмпирической мерой). Комбинаторные величины типа УС-размерности позволяют оценивать энтропию в ½ (/-О сразу для всех мер /х, что позволяет получить РЗБЧ для функций. Оценки Вапника и Червоненкиса были в этом случае несколько завышенныминаиболее подходящим обобщением УС-размерности на классы М-значных функций оказалась псевдоразмерност, ъ, введенная Д. Хаусслером [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):= mid{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 metriques et theorie 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 Besovand 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 problemStability 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.