Каковы основные теоремы в машинном (глубоком) обучении?

45

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

Когда он сказал это, я начал искать основные теоремы для ML, но не смог найти хорошую ссылку, в которой были бы понятны основные результаты. Итак, вот мой вопрос: каковы текущие основные математические теоремы (теория) в ML / DL и что они доказывают? Я предполагаю, что работа Вапника пойдет куда-нибудь сюда. В качестве дополнения, каковы основные теоретические открытые проблемы?

statslearner
источник
3
@Tim Эта меха похожа на stats.stackexchange.com/questions/2379/… («Какие большие проблемы в статистике?»).
whuber
2
Это немного широко. Можете ли вы хотя бы указать подмножество машинного обучения? Если мы ограничимся глубоким обучением или, по крайней мере, контролируемым обучением, можно попытаться ответить. Но если вы настаиваете на чем-то вроде «Математика машинного обучения», то для написания ответа понадобятся годы.
DeltaIV
3
В свете примера аналога @ whuber, я склонен сказать, что он должен оставаться открытым как CW, особенно если это может быть ограничено определенным подмножеством ML, таким как контролируемое обучение , как запросы DeltaV.
gung - Восстановить Монику
3
@DeltaIV Обратите внимание, что "Deep" в названии.
говорит амеба, восстанови Монику
4
Понимание этого вопроса было темой недавней серии лекций, организованных Дэвидом Донохо: см. Stats385.github.io .
user795305

Ответы:

43

Как я писал в комментариях, этот вопрос мне кажется слишком широким, но я попытаюсь ответить на него. Чтобы установить некоторые границы, я начну с небольшой математики, которая лежит в основе большей части ML, а затем сконцентрируюсь на последних результатах для DL.


Диагонально-дисперсии Компромисс упоминается в бесчисленных книгах, курсах, MOOCs, блоги, твиты и т.д. на ML, поэтому мы не можем начать без упоминания о нем:

E[(Yf^(X))2|X=x0]=σϵ2+(Ef^(x0)f(x0))2+E[(f^(x0)Ef^(x0))2]=Irreducible error + Bias2 + Variance

Доказательство здесь: https://web.stanford.edu/~hastie/ElemStatLearn/


Теорема Гаусса-Маркова (да, линейная регрессия останется важной частью машинного обучения, несмотря ни на что: разберитесь с ней) разъясняет, что, когда линейная модель верна и некоторые предположения относительно члена ошибки верны, OLS имеет минимум среднеквадратическая ошибка (которая в вышеприведенном выражении является просто Bias2 + Variance ) только среди несмещенных линейных оценок линейной модели. Таким образом, вполне могут существовать линейные оценки со смещением (или нелинейные оценки), которые имеют лучшую среднеквадратичную ошибку и, следовательно, лучшую ожидаемую ошибку предсказания, чем OLS. И это открывает путь ко всему арсеналу регуляризации (регрессия гребня, LASSO, снижение веса и т. Д.), Который является рабочей лошадкой ML. Доказательство дается здесь (и в бесчисленных других книгах): https://www.amazon.com/Linear-Statistical-Models-James-Stapleton/dp/0470231467

Вероятно, более значимым для взрыва подходов к регуляризации, как отметил Карлос Синелли в комментариях, и, безусловно, более интересно узнать, является теорема Джеймса-Стейна . Рассмотрим n независимых одинаковых дисперсий, но не одинаковых средних гауссовских случайных величин:

Xi|μiN(θi,σ2),i=1,,n

Другими словами, мы имеем n компоненты гауссовский случайный вектор . У нас есть один образец из и мы хотим оценить . MLE (а также UMVUE) - это, очевидно, . Рассмотрим оценку Джеймса-СтейнаXN(θ,σ2I)xXθthetas ; М л Е = хθ^MLE=x

θ^JS=(1(n2)σ2||x||2)x

Ясно, что если , сокращает оценку MLE до нуля. Теорема Джеймса-Стейна гласит, что для , строго доминирует в , т. Имеет более низкое значение MSE . Удивительно, но даже если мы сжимаемся к любой другой константе , прежнему доминирует . Так как(n2)σ2||x||2thetas ; J S п 4 & thetas ; J S & thetas ; M L E ∀ & thetas ; с 0 & thetas ; J S & thetas М Л Е Х яθ^JS n4θ^JS θ^MLE θc0θ^JSθ^MLEXiнезависимы, может показаться странным, что попытка оценить рост трех не связанных между собой людей, включая выборку из числа яблок, произведенных в Испании, может улучшить нашу оценку в среднем . Ключевым моментом здесь является «в среднем»: среднеквадратичная ошибка для одновременной оценки всех компонентов вектора параметров меньше, но квадратная ошибка для одного или нескольких компонентов может быть значительно больше, и это действительно так, когда у вас есть "экстремальные" наблюдения.

Обнаружение того, что MLE, который действительно был «оптимальной» оценкой для случая одномерного оценивания, было свергнуто для многовариантной оценки, было довольно шокирующим в то время и привело к большому интересу к усадке, более известной как регуляризация на языке ML. Можно отметить некоторые сходства со смешанными моделями и понятием «сила заимствования»: здесь действительно есть какая-то связь, как обсуждалось здесь

Единый взгляд на усадку: какова связь (если таковая имеется) между парадоксом Штейна, регрессией гребня и случайными эффектами в смешанных моделях?

Ссылка: Джеймс В., Стейн К. Оценка с квадратичной потерей . Материалы четвертого симпозиума в Беркли по математической статистике и вероятности, том 1: вклад в теорию статистики, 361–379, издательство Калифорнийского университета, Беркли, Калифорния, 1961


Анализ главных компонентов является ключом к важной теме сокращения размерности и основан на разложении по сингулярным значениям : для каждой действительной матрицы (хотя теорема легко обобщается на сложные матрицы) мы можем написатьN×pX

X=UDVT

где размера ортогонально, является диагональной матрицей с неотрицательными диагональными элементами, а размера снова ортогонально. Доказательства и алгоритмы о том, как его вычислить, см .: Голуб Г., и Ван Лоан, С. (1983), Матричные вычисления , издательство Университета Джона Хопкинса, Балтимор.UN×pDp×pUp×p


Теорема Мерсера является основой для множества различных методов ML: сплайны на тонких пластинах, машины опорных векторов, оценка Кригинга гауссовского случайного процесса и т. Д. По сути, это одна из двух теорем, лежащих в основе так называемого трюка ядра . Пусть - симметрическая непрерывная функция или ядро. если является положительным полуопределенным, то он допускает орторнормальный базис собственных функций, соответствующих неотрицательным собственным значениям:K(x,y):[a,b]×[a,b]RK

K(x,y)=i=1γiϕi(x)ϕi(y)

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

Ссылка: Дж. Мерсер, Функции положительного и отрицательного типа и их связь с теорией интегральных уравнений. Философские труды Лондонского королевского общества. Серия А, содержащие документы математического или физического характера, 209: 415-446, 1909

Существует также более простое изложение в Конраде Йоргенсе, Линейные интегральные операторы , Питман, Бостон, 1982.


Другая теорема, которая вместе с теоремой Мерсера излагает теоретическую основу трюка ядра, является теоремой о представителе . Предположим, у вас есть пробное пространство и симметричное положительное полуопределенное ядро . Кроме того, пусть быть RKHS , связанные с . Наконец, пусть будет обучающей выборкой. Теорема говорит, что среди всех функций , которые все допускают бесконечное представление в терминах собственных функцийXK:X×XRHKKS={xi,yi}i=1nfHKKиз-за теоремы Мерсера тот, который минимизирует регуляризованный риск, всегда имеет конечное представление в базисе, образованном ядром, оцененным в обучающих точках, т.е.n

minfHKi=1nL(yi,f(xi))+λ||f||HK2=min{cj}1i=1nL(yi,jcjϕj(xi))+λjcj2γj=i=1nαiK(x,xi)

(теорема является последним равенством). Список литературы: Wahba, G. 1990, Сплайн-модели для данных наблюдений , SIAM, Филадельфия.


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

  • это не дает никакой корреляции между размером скрытого слоя и некоторой мерой сложности целевой функции , такой как, например, Total Variation. Если и необходимое для фиксированной ошибки растет экспоненциально с , тогда один скрытый слой нейронный сети были бы бесполезны.Nf(x)f(x)=sin(ωx):[0,2π][1,1]Nϵω
  • он не говорит , если сеть является изучаемым . Другими словами, предположим, что с учетом и мы знаем, что размер NN будет приближаться к с требуемым допуском в гиперкубе. Затем, используя тренировочные наборы размера и процедуру обучения, такую ​​как, например, back-prop, можем ли мы гарантировать, что, увеличив мы сможем восстановить ?F(x)fϵNfMMF
  • наконец, что еще хуже, ничего не говорится об ошибке предсказания нейронных сетей. То , что мы действительно заинтересованы в том , оценке ошибки предсказания, по крайней мере , усредненное по всех учебных наборов размера . Теорема не помогает в этом отношении.M

Меньшая проблема в версии этой теоремы Горника состоит в том, что она не справедлива для функций активации ReLU. Однако с тех пор Бартлетт доказал расширенную версию, которая покрывает этот пробел.


До сих пор, я думаю, все теоремы, которые я рассматривал, были известны всем. Итак, теперь пришло время для забавных вещей :-) Давайте посмотрим несколько теорем глубокого обучения :

Предположения:

  • глубокая нейронная сеть (для фиксированного , - это функция, которая связывает входы нейронной сети с ее выходами) и потери регуляризации являются суммами положительно однородные функции той же степениΦ(X,W)WΦW(X)Θ(W)
  • функция потерь выпукла и однажды дифференцируема в в компактном множествеL(Y,Φ(X,W)XS

Затем:

  • любой локальный минимум для такой, что подсеть имеет нулевые веса, является глобальным минимумом ( теорема 1 )L(Y,Φ(X,W))+λΘ(W)Φ(X,W)
  • выше критического размера сети локальное снижение всегда будет сходиться к глобальному минимуму при любой инициализации ( теорема 2 ).

Это очень интересно: CNN, состоящие только из сверточных слоев, ReLU, max-pool, полностью подключенных ReLU и линейных слоев являются положительно однородными функциями, в то время как если мы включим функции активации сигмоида, это уже не так, что может частично объяснить превосходство производительность в некоторых приложениях пула ReLU + max по отношению к сигмоидам. Более того, теоремы верны только в том случае, если также положительно однородно в той же степени, что и . факт заключается в том, что или , хотя и является положительно однородной, не имеет одинаковую степень (степеньΘWΦl1l2ΦΦв простом случае CNN, упомянутом ранее, увеличивается с увеличением числа слоев). Вместо этого, более современные методы регуляризации, такие как пакетная нормализация и Path-SGD, действительно соответствуют положительно однородной функции регуляризации той же степени, что и , и выпадение, хотя и не вписывается в эту структуру точно, имеет сильные сходства с ней. Это может объяснить, почему для получения высокой точности с регуляризации и недостаточно, но нам необходимо использовать все виды дьявольских приемов, таких как выпадение и нормализация партии! Насколько я знаю, это самое близкое к объяснению эффективности нормализации партии, которая в остальном очень неясна, как правильно отметил Аль Рахими в своем выступлении.Φl1l2

Другое наблюдение, которое делают некоторые люди, основываясь на теореме 1 , состоит в том, что оно может объяснить, почему ReLU работает хорошо, даже с проблемой мертвых нейронов . Согласно этой интуиции, тот факт, что во время обучения некоторые нейроны ReLU «умирают» (переходят в нулевую активацию и затем никогда не восстанавливаются после этого, поскольку при градиент ReLU равен нулю), это «особенность, а не ошибка». «потому что если мы достигли минимума и полная подсеть умерла, то мы достигли доказанного глобального минимума (согласно условиям теоремы 1»).x<0). Я могу что-то упустить, но я думаю, что эта интерпретация надуманна. Прежде всего, во время обучения ReLU могут «умереть» задолго до того, как мы достигнем местного минимума. Во-вторых, необходимо доказать, что, когда блоки ReLU «умирают», они всегда делают это по всей подсети: единственный случай, когда это тривиально верно, - это когда у вас есть только один скрытый слой, и в этом случае, конечно, каждый отдельный нейрон подсеть. Но в целом я был бы очень осторожен, рассматривая «мертвые нейроны» как хорошую вещь.

Рекомендации:

Б. Хаффеле и Р. Видал, Глобальная оптимальность в обучении нейронных сетей , на конференции IEEE по компьютерному зрению и распознаванию образов, 2017.

Б. Хаффеле и Р. Видаль. Глобальная оптимальность в тензорной факторизации, глубоком обучении и за ее пределами , arXiv, abs / 1506.07540, 2015.


Классификация изображений требует изучения представлений, которые являются инвариантными (или, по крайней мере, устойчивыми, то есть очень слабо чувствительными) к различным преобразованиям, таким как местоположение, поза, точка зрения, освещение, выражение и т. Д., Которые обычно присутствуют в естественных изображениях, но не содержат информацию для задачи классификации. То же самое для распознавания речи: изменения высоты, громкости, темпа, акцента. и т. д. не должно приводить к изменению классификации слова. Такие операции, как свертка, максимальный пул, средний пул и т. Д., Используемые в CNN, имеют именно эту цель, поэтому мы интуитивно ожидаем, что они будут работать для этих приложений. Но есть ли у нас теоремы, подтверждающие эту интуицию? Существует теорема о вертикальной трансляционной инвариантности, который, несмотря на название, не имеет ничего общего с переводом в вертикальном направлении, но в основном это результат, который говорит о том, что функции, изученные в следующих слоях, становятся все более и более инвариантными с ростом количества слоев. Это противоречит более старой теореме о горизонтальной трансляционной инвариантности, которая, однако, верна для рассеивающих сетей, но не для CNN. Теорема очень техническая, однако:

  • предположим, что (ваше входное изображение) является квадратично интегрируемымf
  • Предположим, ваш фильтр коммутирует с оператором перевода , который отображает входное изображение в переведенную копию самого себя . Изученное ядро ​​свертки (фильтр) удовлетворяет этой гипотезе.TtfTtf
  • Предположим, что все фильтры, нелинейности и пулы в вашей сети удовлетворяют так называемому условию слабой допустимости , которое в основном является своего рода условиями слабой регулярности и ограниченности. Этим условиям удовлетворяют изученное ядро ​​свертки (при условии, что на каждом уровне выполняется некоторая операция нормализации), ReLU, сигмоид, танх и т. Д., Нелинейности и средний пул, но не максимальный пул. Таким образом, он охватывает некоторые (не все) архитектуры реального мира CNN.
  • Наконец, предположим, что каждый уровень имеет коэффициент объединения , то есть объединение применяется на каждом уровне и эффективно отбрасывает информацию. Условие также будет достаточно для более слабой версии теоремы.nSn>1Sn1

Укажите с помощью выход слоя из CNN, когда вход - . Тогда наконец:Φn(f)nf

limn|||Φn(Tff)Φn(f)|||=0

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

Ссылка: Т. Wiatowski и H. Bolcskei, Математическая теория глубоких сверточных нейронных сетей для извлечения признаков, arXiv: 1512.06293v3 .


В заключение, многочисленные оценки для ошибки обобщения глубокой нейронной сети, основанной на ее измерении Vapnik-Chervonkensis или сложности Rademacher, растут с увеличением количества параметров (некоторые даже экспоненциально), что означает, что они не могут объяснить, почему DNN работают так хорошо на практике даже тогда, когда количество параметров значительно превышает количество обучающих выборок. На самом деле, теория VC не очень полезна в Deep Learning.

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

GE2log2NyNγm+2log(1/δ)m

где:

  • GE - это ошибка обобщения, определяемая как разница между ожидаемой потерей (средняя потеря изученного классификатора по всем возможным контрольным точкам) и эмпирической потерей (просто ошибка хорошего набора обучения)
  • Ny - количество классов
  • m - размер тренировочного набора
  • Nγ - это число покрытия данных, количество, связанное со структурой входного пространства и минимальным разделением между точками разных классов в обучающем наборе. Ссылка:

Дж. Соколич, Р. Гириес, Г. Сапиро и М. Родригес. Ошибка обобщения инвариантных классификаторов . В АИСТАХ, 2017

DeltaIV
источник
2
+1. Отличный ответ, последняя часть очень интригующая. В первой части теорема Мерсера выглядит так же, как SVD, которую вы представили чуть выше.
говорит амеба, восстанови Монику
1
@amoeba, вы правы, но 1) не все читатели настолько же разбираются в математике, как вы, что они сразу распознали бы сходство между SVD, расширением Кархунена-Лоэва и теоремой Мерсера. Также 2) другую теорему из Функционального анализа, которая «питает» уловку ядра, и которую я решил не включать, объяснить сложнее, чем теорему Мерсера, и я уже сломал свою субботу :-) Может быть, я добавлю ее завтра!
DeltaIV
1
Гаусс Марков кажется неуместным, никогда не видел, чтобы кто-то заботился о СИНЕМ в сообществе ОД.
Карлос Синелли
2
Я согласен, что, как правило, оригинальная (архаичная) ссылка обычно имеет утомительное обозначение. Тем не менее, статья Мерсера на самом деле удивительно современна в этом аспекте, и я добавил ее именно из-за этого. :) (Первоначально я сказал, что это очень хороший ответ, это просто комментарий после возражения)
usεr11852 говорит восстановить Monic
2
Мне нравится теорема Мерсера здесь, не удаляйте ее. А почему бы не иметь обе ссылки? Просто добавьте что-нибудь, как See [here] for a modern exposition, или наоборот, "для оригинальной статьи".
говорит амеба, восстанови монику
11

Я думаю, что следующая теорема, на которую вы ссылаетесь, считается довольно фундаментальной в статистическом обучении.

Теорема (Вапник, Червоненкис, 1971). Пусть - класс гипотез функций из области в а функция потерь - потеря. Тогда следующие условия эквивалентны:HX{0,1}01

  1. H обладает свойством равномерной сходимости.
  2. H является PAC обучаемым.
  3. H имеет конечную VC-размерность.

Проверено в количественной версии здесь:

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

Сформулированная выше версия вместе с хорошим изложением других результатов теории обучения доступна здесь :

Шалев-Шварц, Шай и Шай Бен-Давид. Понимание машинного обучения: от теории к алгоритмам. Издательство Кембриджского университета, 2014.

Машина эпсилон
источник
6

Уловка ядра - это общая идея, которая используется во многих местах и ​​основана на множестве абстрактных математических представлений о пространствах Гильберта. Слишком много теории для меня, чтобы напечатать (скопировать ...) в ответ здесь, но если вы просмотрите это, вы сможете получить представление о его строгих основах:

http://www.stats.ox.ac.uk/~sejdinov/teaching/atml14/Theory_2014.pdf

Теймур
источник
4

Мой любимый - это неравенство Крафта.

Теорема: для любого метода описания для конечного алфавита длины кодовых слов должны удовлетворять неравенству .CA={1,,m}LC(1),,LC(2)xA2LC(x)1

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

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

bayerj
источник
4

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

Теорема: Пусть - непостоянная и монотонно возрастающая непрерывная функция. Для любой непрерывной функции и любого существуют целое число и многослойный персептрон с одним скрытым слоем, содержащим нейронов, в качестве активации которого используется функционировать так, чтобыσf:[0,1]mRϵ>0NFNσ

|F(x)f(x)|ϵ
для всех .x[0,1]m

Конечно, поскольку это утверждение о существовании , его влияние на практиков незначительно.

Доказательство можно найти в Hornik, Аппроксимационные возможности многослойных сетей прямого распространения, Нейронные сети 4 (2), 1991,

Тобиас Виндиш
источник
5
Эта теорема немного неинтересна, поскольку она не относится к нейронным сетям. Многие другие классы функций имеют сходные (а иногда и более сильные) свойства аппроксимации. См., Например, теорему Стоуна-Вейерштрасса. Более интересным результатом была бы последовательность регрессии нейронной сети в общих рамках. Кроме того, должны быть известны границы средней ошибки обобщения с точки зрения сложности сети и размера обучающей выборки.
Оливье
1
@ Оливье: Я полностью согласен. Но хотя эта теорема не посвящена исключительно нейронным сетям, я все же нахожу ее утверждение, ее строгое доказательство и ее последствия интересными. Например, в нем говорится, что до тех пор, пока вы используете функцию активации, которая имеет свойства, указанные выше, примерные возможности сети одинаковы (грубо говоря). Или это говорит о том, что нейронные сети подвержены переоснащению, так как вы можете многому научиться уже с одним скрытым слоем.
Тобиас Виндиш
1
Это точно не говорит об этом. Он говорит только о том, что существует нейронная сеть с одним скрытым слоем, который может представлять собой , но он ничего не говорит вам о том, как растет с , например, или с некоторой степенью сложности (например, ее полная вариация ). Он не говорит вам, можете ли вы вес вашей сети, учитывая данные. Вы увидите , что во многих интересных случаях является экспоненциально больше для одного скрытых сетей слоя , чем для многослойных (глубоких) сетей. Вот почему никто не использует один скрытый слой сетей для ImageNet или Kaggle. fNmflearnN
DeltaIV
@DeltaIV: в последнем предложении моего предыдущего комментария есть опечатка: слово «выучить» на самом деле должно быть «приблизительным» (иначе мое утверждение о «переоснащении» не имело бы смысла). Спасибо за подсказку!
Тобиас Виндиш
Да, я интерпретировал это в смысле «приближения». Я хочу сказать, что даже если вы знаете, что теоретически вы можете аппроксимировать любую функцию (в ограниченном гиперкубе) одним скрытым слоем NN, на практике это бесполезно во многих случаях. Другой пример: процессы Гаусса с квадратом экспоненциального ядра обладают свойством универсальной аппроксимации, но они не исключили все другие методы регрессии, в том числе из-за того, что для некоторых задач количество выборок, необходимых для точной аппроксимации, растет экспоненциально.
DeltaIV
2

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

https://medium.com/mlreview/modern-theory-of-deep-learning-why-does-it-works-so-well-9ee1f7fb2808

Это дает доступное резюме основных появляющихся теорем для способности глубоких нейронных сетей обобщать так хорошо.

Тоби Коллинз
источник