Спикер о вебинаре:
Наиболее точные из известных оценок обобщения с высокой вероятностью для равномерно устойчивых алгоритмов (Фельдман, Вондрак, NeurIPS 2018, COLT, 2019), (Буске, Клочков, Животовский, COLT, 2020) содержат неизбежный член ошибки выборки порядка Θ (1 / √n). Применительно к оценкам избыточного риска это приводит к неоптимальным результатам в нескольких стандартных задачах выпуклой оптимизации. Мы поговорим о том как этого члена можно избежать, если выполняется так называемое условие Бернштейна, и оценки избыточного риска порядка O (1 / n) станут возможны благодаря равномерной устойчивости. Используя этот результат, мы покажем оценки избыточного риска порядка O (log n / n) для сильно выпуклых и липшицевых потерь, действительную для любого эмпирического метода минимизации риска. Это решает вопрос поставленный Шалев-Шварцем, Шамиром, Сребро и Шридхарана (COLT, 2009). Доклад основан на совместной работе с Никитой Животовским и Оливье Буске.
Запись: https://youtu.be/hLfvt6kndTA
Презентация: https://drive.google.com/file/d/1l3zI0mZeBWQQvlAf14iaTmnaQO_J_33j/view?usp=sharing
Статьи:
Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n) https://drive.google.com/drive/u/1/folders/1VH-OjMi3DqsMMOJmX2Beef7TNAszTy-A
Sharper Bounds for Uniformly Stable Algorithms
https://drive.google.com/drive/u/1/folders/15wcTzQrMS6Ki7Ag8buwk89NNqMRIjqaa
(00:00:00) (Начало записи.)
Николай Михайловский: Приветствую всех! Я Николай Михайловский, генеральный директор компании «НТР». И мы приветствуем сегодня Егора Клочкова (университет Кембриджа) на нашем научно-техническом вебинаре с рассказом про избыточный риск устойчивых обучающих алгоритмов. Насколько я понимаю, вся эта история идет из глубин врем от Вапника с Червоненкисом, которые статистическую теорию машинного обучения начинали еще в 1960-е годы развивать. И тогда основная претензия к их теории состояла в том, что, на самом деле, алгоритмы машинного обучения работают быстрее, чем предсказывает статистич… Но в последнее время, похоже, наметился некоторый прорыв в этой области. И Егор – один из людей, которые в этом прорыве участвуют.
Для общения у нас есть Q&A, у нас есть чат.
Егор Клочков: Спасибо большое, что позвали! Делать доклады на русском – это случается в последнее время достаточно редко.
Мы сегодня поговорим про избыточный риск устойчивых обучающих алгоритмов. Это совместная работа с Никитой Животовским (мой хороший друг) и Ове Буске. И доклад основан на двух статьях. Здесь по ссылкам можно посмотреть, если заинтересует.
Начнем с достаточно классической задачи – сильно выпуклая стохастическая оптимизация. У нас есть какой-то параметр W, который живет в каком-то подмножестве Евклидова пространства, или даже Гильбертова, и есть функция потерь, то есть у нас есть какие-то элементы, скажем, какие-то пары ответов признаков, и есть функция потерь параметра на этих элементах. Элементы приходят из какого-то абстрактного множества, а параметры из подмножества (00:03:01) Евклидова или Гильбертова пространства.
И риск-параметры – это матожидание по какому-то распределению на этих элементах, потерь параметра на элементе.
И распределение нам неизвестно. Вместо этого мы наблюдаем какую-то независимую выборку – n независимых Zi, которые приходят с определением P. И наша цель, основываясь на этой независимой выборке – каким-то образом оптимизировать этот риск.
Что предполагается про функцию риска? Для сильно выпуклой оптимизации, мы считаем, что, во-первых, она не отрицательная, во-вторых, сильно выпуклая с параметром λ. То есть для любого фиксированного Z эта функция потерь как функция от параметра w будет сильно выпуклая. Это значит, что если мы вычтем такую регуляризацию, то есть квадратичный член со множеством λ/2, то оставшаяся функция будет выпуклая. Это одно из эквивалентных определений сильной выпуклости, которое наиболее компактно можно записать.
Далее мы еще также предполагаем, что функция будет липшицева с параметром L. Точно также для любого фиксированного Z функция l(z,w) как функция от w будет липшицева.
То есть, если мы берем два разных вектора, разница на произвольном элементе Z функции потерь между параметрами w1, w2 будет ограничена L умножить на расстояние между w1 и w2.
И так как мы говорим о выпуклых функциях, этот домейн W курсив – это должно быть какое-то выпуклое подмножество, и при этом оно еще будет ограничено, просто потому что мы предполагаем сильную выпуклость и липшицовость одновременно, то есть не может быть неограниченное множество.
Что мы хотим сделать? Мы хотим каким-то образом оптимизировать риск. То есть у нас будет какой-то алгоритм оптимизации wn, который отображает множество выборок размера n пространства этих параметров w. То есть какое-то правило, которое по выборке выдает нам параметр.
И стандартный подход – это минимизировать эмпирический риск. Что такое эмпирический риск? Это просто средняя функция потерь параметра w на элементах выборки. То есть каким-то образом это аппроксимация настоящего риска, который мы точно не знаем, но по выборке мы можем как-то с какой-то точностью восстановить.
И минимизатор эмпирического риска – это просто какой-то минимум – не какой-то, а он один в случае сильно выпуклой функции, – минимум этого эмпирического риска.
Также очень часто, так как мы в общем случае численно не можем прямо точно знать, какой параметр минимизирует этот эмпирический риск, иногда используются какие-то приблизительные алгоритмы, например, градиентный спуск, или какой-нибудь стохастический градиентный спуск. Это какой-то алгоритм, который приблизительно выдает нам этот минимизатор эмпирического риска.
И для такого алгоритма мы хотим оценить избыточный риск. То есть чтобы сказать, насколько хорошо мы минимизируем риск, мы просто берем и смотрим на разницу между риском нашего оцененного параметра и минимальным возможным риском. Сам по себе риск не дает информации, насколько качественно мы оценили, а избыточный риск о чем-то говорит. То есть в идеале мы хотим, чтобы эта штука достаточно быстро сходилась к нулю.
И также мы будем очень часто использовать оптимизационную ошибку. То есть если у нас не ERM (минимизатор эмпирического риска), а какой-то градиентный спуск, то там нам тоже будет очень важно узнать, насколько качественно наш алгоритм минимизирует эмпирический риск. То есть такая оптимизационная ошибка. Разница между эмпирическим риском алгоритма и минимально возможным эмпирическим риском. Эта штука тут тоже всегда неотрицательная. И просто оценить, насколько близко мы приближаемся к минимизатору эмпирического риска.
Что про эту задачу известно? Во-первых, известна оценка в среднем. Если мы возьмем матожидание избыточного риска… Здесь w* значит минимизатор настоящего риска, который единственный в случае сильной выпуклости. И эта штука – это просто матожидание избыточного риска. И известно, что матожидание этого избыточного риска ограничено с точностью до константы как L2/nλ. То есть когда я пишу такой значок меньше либо равно с волнистой палочкой (⪅) – это значит, что с точностью до какой-то абсолютной константы.
И получается, что если мы считаем, что константа липшицева и сильная выпуклость, они ведут себя как константы, то порядок сходимости – 1/n – это то, что называется «быстрый порядок сходимости».
При этом это нам не дает особо никакой информации про то, как оценивать избыточный риск с большой вероятностью. То есть по матожиданию – это, конечно, хорошо, но мы еще очень часто хотим знать, что с такой вероятностью избыточный риск ограничен такой-то вещью. И что про это известно? Конечно, мы можем к этому неравенству применить неравенство Маркова, так как эта штука (избыточный риск) неотрицательная. Но тогда будет не очень хорошая зависимость от вероятности.
При этом в этой статье Шалев-Шварц и еще три человека они доказали, что, допустим, у нас есть линейный риск, то это значит, что наши элементы, которые мы наблюдаем, они имеют вид такой пары (x, y): x – это как признаки, y – ответы. Мы можем так воспринимать. И тогда функция потерь – они предполагают, что это просто какая-то функция от скалярного произведения параметра и признаков. И еще от ответа зависит. То есть идея в том, чтобы где-то внутри сидела линейная зависимость от параметра w. И тогда они показывают, что с вероятностью 1–δ, для любого δ избыточный риск ограничен: такой же член, который стоит в матожидании, умножить на log(1/δ). И оценки такого вида, как правило, называются оценками с большой вероятностью. То есть мы можем позволить себе δ очень-очень маленькое, скажем, n в минус какой-то степени, причем в любой степени, и тогда здесь максимум мы заплатим log n. То есть очень хорошая зависимость от этого параметра confidence. И это то, что, скорее всего, должно быть правдой для общего случая, но пока это известно только как раз для линейного риска.
Также есть оценки с медленной сходимостью порядка 1n,. Фельдман и Вондрак, которые доказали свою новую оценку для устойчивых алгоритмов, основываясь на этой оценке, они показали медленную сходимость 1n,. То есть тоже с хорошей зависимостью от log(1/δ). Но при этом это, на самом деле, не очень интересно, потому что такая сходимость может быть, даже если у нас нет сильной выпуклости. То есть если у нас функция просто выпуклая, мы можем всегда добавить регуляризацию порядка 1n,, и это нам не сильно добавит смещение оценки. То есть такая сходимость, на самом деле, не имеет отношения к строго выпуклому случаю. Это в любом выпуклом случае известно. Поэтому не очень интересно.
И такой вопрос, и Шалев-Шварц его поставили: как доказать такую оценку с большой вероятностью в самом общем случае – просто строго выпуклая и липшицева функция.
(00:12:16)
Мы почти полностью на такой вопрос отвечаем в нашей статье 2021 года с Никитой. Пусть у нас есть те самые условия, про которые говорил – сильно выпуклая и липшицева функция. Тогда верна такая оценка с вероятностью 1–δ. То есть по сравнению с линейным случаем мы имеем этот быстрый порядок log(1/δ), но при этом у нас еще дополнительно log возникает. И если его агрегировать (00:12:45), то получится, по сути, быстрый порядок. Эта оценка основана на новой оценке для обобщающей ошибки устойчивых алгоритмов. То есть алгоритм ERM в случае сильно выпуклой оптимизации будет устойчивый, мы об этом чуть подробнее поговорим попозже. И, основываясь на нашей новой оценке, мы просто практически напрямую выводим эту оценку для сильно выпуклой оптимизации.
(00:13:23)
И похожий результат также еще выполняется для приблизительных ERM, то есть для приблизительных минимизаторов риска, если это какой-нибудь градиентный спуск, например. То есть чем ближе мы приближаем себя к ERM, тем ближе мы приближаемся к такой оценке.
Николай Михайловский: Егор, для тех, кто меньше в теме, еще раз можно про физический, так сказать, смысл избыточного риска? Что именно он означает для практической работы? Что эта оценка дает?
Егор Клочков: Это просто один способ показать, насколько мы близко к оптимальному решению.
Николай Михайловский: То есть, когда мы смотрим на инфинум, это у нас инфинум – оптимально подобранная обучающая выборка, скажем так.
Егор Клочков: Ну, да. Бесконечная выборка.
Николай Михайловский: Да. Это бесконечная обучающая выборка для данного алгоритма. Мы взяли некое конечное подмножество и сравниваем теперь, насколько хуже мы можем обучить на конечной выборке, чем на бесконечной выборке. Правильно я понимаю?
Егор Клочков: Да-да, правильно. То есть мы смотрим на этот избыточный риск, просто потому что…
(00:15:01)
Конечно, если мы говорим о какой-нибудь классификации, то эта штука, считается, что она ноль. Но при этом в общем случае она не ноль. И насколько мы хотим какую-то сходимость, и поэтому мы просто вычитаем эту штуку, которая в самом общем случае может быть просто константа. Но для нас важно, чтобы был маленький зазор. Поэтому это просто стандартный способ.
Николай Михайловский: То есть фактически мы ошибку нашего машинного обучения разделяем на два куска. Один кусок связан с конечностью обучающей выборки, а второй кусок – со свойствами алгоритма на бесконечной обучающей выборке.
Егор Клочков: Ну, да. Можно сказать, что это просто шум. Если у нас есть какой-то шум, который мы никак не можем подогнать, мы не хотим этот шум Rw оценивать. Нам нужна именно разница между параметрами.
Николай Михайловский: Для того чтобы я точно был уверен в том, что здесь оценивается, моя интерпретация правильна. Мы разделяем ошибку алгоритма машинного обучения на ошибку обучения на бесконечной выборке и ошибку, связанную с конечностью выборки.
Егор Клочков: Да, можно так сказать.
Николай Михайловский: Спасибо.
Егор Клочков: Причем здесь обобщающая ошибка и что такое обобщающая ошибка? Стандартный подход, чтобы ограничивать этот избыточный риск – это просто такая декомпозиция. Это мы записываем пока для ERM (минимизатора эмпирического риска). В общем случае здесь еще будет участвовать оптимизационная ошибка. Но для простоты давайте рассмотрим. Избыточный риск ограничен суммой вот такого члена. Это разница риска на нашем обучающем алгоритме и эмпирического риска на нашем обучающем алгоритме. И это то, что называется обобщающей ошибкой, то есть насколько хорошо наш алгоритм обобщает из обучающей выборки на всё распределение. То есть, если эта штука маленькая, то значит мы хорошо обобщаем. Если она большая, значит, мы плохо обобщаем.
И плюс вот такой член (00:17:35) – это какая-то такая достаточно простая вещь. Так как это усреднение по выборке (00:17:44) (функция потери), а это ее матожидание (00:17:50), то это сумма независимых случайных величин, с ней очень просто работать. И основной вопрос: как ограничить эту штуку? (00:17:56) И в этом случае есть два подхода, которые используются чаще всего. Один подход – это с помощью эмпирических процессов. То есть мы хотим ограничить разность эмпирического и настоящего риска во всем множестве W. И тогда нас не волнует, что эта наша оценка зависит от элементов выборки. То есть мы просто имеем право поставить сюда этот wn, и он тоже будет маленький, вот эта разница (00:18:34) будет маленькая. И это именно то, как Шалев-Шварц и другие доказывают оценку в линейном случае.
Но при этом в общем случае эта штука даже не сходится к нулю. Нам в принципе-то нужен даже какой-то порядок сходимости, а в общем случае это даже к нулю не сходится, не то, что с каким-то порядком. И они в статье 2010 года показывают пример. Такой подход в самом общем случае не должен работать. Может быть, там можно как-то по-умному брать в каком-то подмножестве супремум, но пока мы про это ничего не знаем. А то, что знаем – это обобщающую ошибку можно ограничивать просто как ошибку устойчивого алгоритма. То есть есть целый класс оценок на обобщающую ошибку для устойчивых алгоритмов. И в нашем сильно выпуклом случае ERM как раз и будет устойчивым алгоритмом. И в частности эта оценка по матожиданию именно так и доказывается. Если мы возьмем матожидание этой штуки, то оно будет ограничено L2/nλ. Но при этом основная проблема в том, что по матожиданию там всё хорошо, а если мы возьмем матожидание модуля, то там уже появится неизбежный член порядка 1n, и, соответственно, мы никаких быстрых порядков не сможем взять напрямую из оценки обобщающей ошибки. И с нашей новой оценкой мы можем этого члена избежать.
(00:20:29)
Теперь давайте подробнее поговорим про устойчивость алгоритмов. И формальное определение устойчивости – просто низкая чувствительность к изменению элементов выборки. И мотивация для этого начинается еще со времен Вапника и Червоненкиса. Когда они придумали, например, метод опорных векторов, идея была в том, что алгоритм зависит от какого-то ограниченного количества векторов выборки. То есть если мы выкинем, допустим, элементы, которые не опорные, то ничего не поменяется. И то есть алгоритм устойчив по отношению к элементам вне этого множества опорных векторов.
И только основываясь на этом факте, в разделимом случае, когда у нас просто есть два линейных класса, которые прямо можно разделить линией, можно легко показать оценку по матожиданию, что риск SVM ограничен d/n, где n – это размерность.
Но чтобы можно было доказывать оценки с большой вероятностью, Буске и Елисеев ввели такое понятие равномерной устойчивости, то есть что не просто там почти все элементы можно выкинуть, но мы говорим, что если мы заменим любой элемент выборки, то функция последней сильно поменяется.
То есть, чтобы подробнее сказать, у нас есть алгоритм, который зависит от выборки (размера n), есть какая-то функция потерь, и теперь она может быть необязательно липшицева или сильно выпуклая, а просто какая-то функция потерь, какой-то алгоритм. Риск алгоритма считается как интеграл по распределению, а эмпирический риск считается как среднее по этой выборке. И алгоритм называется «равномерно устойчивый», если мы для любой выборки и для любого элемента Z возьмем и в нашей выборке поменяем один элемент на какой-то произвольный другой. Тогда разница функции потерь поменяется не больше чем на γ (гамма). И в таком случае алгоритм называется «равномерно устойчивый с параметром γ».
Есть очень много примеров, где есть такая равномерная устойчивость. В частности наша сильно выпуклая оптимизация с параметром γ=2L2/nλ. То есть устойчивость порядка 1/n.
Также есть SVM, но не оригинальная, а которая называется soft margins. Мы не имеем права здесь брать дискретную функцию L, она должна более-менее непрерывно меняться, чтобы была равномерная устойчивость.
И также относительно недавно была такая статья, которая очень много цитируется. Они проверяют равномерную устойчивость для всяких градиентных спусков, всяких вариаций его. И фишка в том там, что для градиентного спуска, в принципе, ничего не нужно знать про выпуклость или сильную выпуклость. Просто нужна какая-то гладкая функция потерь. И если количество шагов градиентного спуска как-то ограничено, то алгоритм получается равномерно устойчивый. И это мотивируется, естественно, тем, что в современных приложениях очень часто нужно оптимизировать какие-то выпуклые функции, не очень хорошие. И эта статья, после нее потом очень много было исследований на эту тему.
Что для таких равномерно устойчивых алгоритмов известно? Допустим, что у нас функция потерь ограничена. И имеется такой гамма равномерно устойчивый алгоритм. Тогда для любого δ с в вероятностью 1–δ вот такая оценка выполняется. То есть обобщающая ошибка. [Мы еще работаем] (00:24:57) с точностью до какой-то константы.
nlog(1/δ) +log(1/δ)n
И эта оценка, на самом деле, не очень хорошо работает для больших γ, потому что в той же самой статье, на самом деле, доказывается оценка в среднеквадратичном. То есть если мы возьмем и вместо оценки с большой вероятностью посмотрим на такой l2 риск, то он будет ограничен γ+1n. То есть этот n, скорее всего, лишний.
(00:25:45)
Также еще известно, и это как раз тот вопрос, который мы изучаем, что этот log(1/δ), если брать матожидание, то он исчезает, то есть там происходит какое-то центрирование. Если мы возьмем матожидание обобщающей ошибки без модуля под матожиданием, то будет очень простая оценка, даже без всяких констант. Просто матожидание от γ. И вопрос: как избавиться от этого n? Во-вторых, как разобраться с этой ошибкой порядка 1n.
Дальше в 2019 году была статья Фельдмана и Вондрака, где они показали, как избавиться от этого n перед членом со стабильностью. То есть они доказали такую оценку, что если те же самые условия, функция потерь ограничена, и имеется γ равномерно устойчивый алгоритм (00:26:49), тогда с вероятностью 1/δ наша обобщающая ошибка ограничена такой штукой (00:26:52). Здесь, получается, этот член пропорционален γ, и появляется дополнительно log n. А этот член (00:27:02), он всегда присутствует. То есть без него в принципе никак, когда мы ограничены с большой вероятностью.
И плюс еще такой, чуть-чуть хуже, чем log n – y(log n)2. И доказательство основано на индукции. Они разделяют выборку пополам, как-то ее потом хитро используют для половинной выборки, и потом склеивают. То есть идея гораздо сложнее, чем то, что сделали Буске и Елисеев. И в общем случае эти слагаемые не знаю, как отделять. Причем оно, чтобы было понятно, что если, допустим, у нас алгоритм – это просто какая-то константа, то разница эмпирического и настоящего риска – это будет просто среднее каких-то центрированных случайных величин. И в самом общем случае они действительно должны такого порядка иметь хвосты. То есть, в принципе, 1n неизбежен.
А мы доказали следующую оценку. Во-первых, мы использовали похожую идею, но у нас более явная конструкция, и за счет нее мы смогли избавиться от этого (log n)2.то есть оценка получилась чуть-чуть точнее. Но при этом, на самом деле – и мы это не сразу поняли, – наше доказательств позволяет выделить такое среднее конкретных случайных независимых величин, что оно отвечает за этот член порядка 1n. то есть если мы вычитаем, вот эти ri явно заданы. ri зависит от xi. Соответственно, они независимые. И если мы их вычтем от обобщающей ошибки, то получится такая оценка с вероятностью 1–δ – просто член, отвечающий за стабильность.
А если мы уж хотим вот этот член получить, то просто можем ограничить эту сумму, у нее будут хвосты порядка log(1/δ)n.
Николай Михайловский: Можно еще раз про сущность ri?
Егор Клочков: У меня нет какой-то интуиции. То, что здесь написано – это следующая вещь… У нас есть этот γ равномерно устойчивый алгоритм, и нам нужно усреднить в какой-то мере функцию потерь на итом [i] элементе по алгоритму. И для этого мы берем просто алгоритм, который не зависит от Xi. То есть просто берем копию его, считаем функцию потерь, на иксы вот этого алгоритма, и затем берем матожидание по этому алгоритму. То есть всё, что остается, оно зависит только от Xi.А вот эта штука – это просто матожидание первого слагаемого. То есть ri центрированы.
(00:30:36)
На самом деле, эта штука, ее можно записать, как, например, l(Xi,wn), матожидание при условии Xi. То есть мы хотим по всему усреднить Xi переменной.
Николай Михайловский: То есть если w – это у нас какие-то веса нейронной сети, условно говоря, то мы по всем возможным нейронным сетям усредняем здесь.
Егор Клочков: У wn’ распределение то же самое, что и у wn, но просто нам нужно вытащить из нее зависимость от Xi, чтобы у нас здесь была сумма независимых переменных, независимых случайных величин.
И немножко технический момент, на чем основывается наше доказательство – мы очень много используем так называемые моментные неравенства. Допустим, у нас есть какая-то случайная величина Z. Тогда моментная норма p случайной величины Z – это просто матожидание E1/pZp . То есть это также еще называется LP normal (00:32:06), потому что если _____ (00:32:07), то значит это функция, и просто интеграл степени p, и потом в степени 1/p. И с этими вещами, на самом деле, достаточно удобно работать, потому что известно, что если для любого p наша случайная величина удовлетворяет такому неравенству с какими-то a и b, то есть ap+bp, то это с точностью до константы эквивалентно тому, что для любого δ с вероятностью 1–δ модуль Z ограничен такой штукой. Там, где был p, у нас будет log(1/δ), а где был p, будет log(1/δ).
И это верно тоже в другую сторону. Если у нас есть такие неравенства (00:32:56), то мы можем получить вот такие неравенства (00:32:59). Но при этом есть очень много неравенств, которые работают именно с моментами. И, на самом деле, очень многие известные неравенства, которые описывают хвосты, их можно записать _____ (00:33:11) моментов, такие как Хёвнин (00:33:13), Берштейн, всякие классические неравенства.
И дальше мы рассматриваем такие функции, которые обладают свойством ограниченных разностей. То есть функция g у нас принимает какие-то элементы выборки, и выдает просто число. И мы говорим, что она обладает свойством ограниченных разностей с параметром β, если мы для какого-то индекса i, если мы эту координату с индексом i заменим на любую другую, то значение функции изменится не больше, чем на . То есть это равномерное условие ограниченных разностей.
И тогда, пользуясь таким определением, мы доказываем следующие неравенства. Допустим, у нас есть какой-то набор независимых случайных величин (Z1,…,Zn), и у нас есть n функций, которые зависят от n таких величин. Каждая функция gi удовлетворяет следующему условию. Во-первых, gi(Z)Zi ограничено. То есть, в принципе, мы могли бы сказать, что просто функция gi ограничена, но самое общее условие вот такое (00:34:43).
(00:34:46)
Вот это условие, оно очень сильное условие. И основная сложность была в том, как его использовать. То есть здесь мы берем условное матожидание по всем кроме итой [i] переменной. Или, грубо говоря, мы просто интегрируем функцию gi(Z) по итой переменной. И независимо от того, какие все остальные переменные, мы всегда получим ноль. Это такое условие, которое я чуть подробнее на следующем слайде расскажу, откуда оно приходит. И основная сложность была в том, чтобы воспользоваться этим условием. Оценка Буске и Елисеева, она это условие вообще не использовала. То есть она исключительно использует ограниченные разности.
И последнее условие, что gi имеет ограниченные по всем переменным кроме итой. И тогда верно такое неравенство, что для любого p≥2 сумма gi(Z) меньше либо равна, чем такая штука. Здесь у нас, получается, какие-то константы. Первое слагаемое пропорционально pnβ c дополнительным алгоритмом, а второе – пропорционально Mpn. И здесь, что тоже достаточно приятно, у нас не очень большие константы. Мне кажется, у Фельдмана и Вондрака были гораздо больше. Они, мне кажется, даже явно не выписывали. Но при этом идея, на самом деле, похожая, что мы разделяем выборку пополам, и вложенно, то есть такая вложенная структура. Но при этом мы эту штуку ограничиваем одной телескопической суммой, у которой и log n слагаемых. То есть мы log n раз берем и делим выборку пополам, отсюда log и появляется.
То есть идею мы действительно взяли от Фельдмана и Вондрака, но мы проще ее воспроизвели. И, на самом деле, доказательство у нас всего на страницу получилось. То есть доказательство получается кратким, если использовать правильные вещи.
Откуда такие функции gi берутся? Это просто такая техническая конструкция. Мы берем наш алгоритм, заменяем в нем итую координату на независимую копию. То есть у нее распределение такое же, как у Zi, но она независима от всех элементов в выборке.
И берем функцию потерь этого алгоритма с запененной координатой на точке Zi, вычитаем риск этого алгоритма, и интегрируем по этой координате-копии. То есть наша цель – пользуясь устойчивостью, просто избавить алгоритм wn от зависимости от Zi, чтобы удобнее работать.
И этот трюк с заменой координаты, он нам максимум дает ошибку 2γ, потому что у нас есть устойчивость. То есть разница между обобщающей ошибкой и средняя этих функций на значениях выборки, она будет не больше, чем 2γ, причем поточечно. То есть не с большой вероятностью, а даже поточечно.
И из нашего неравенства следует такая оценка, что p норма среднего этих функций gi, и если мы еще при этом вычтем условное ⟨Zi]⟩, то среднее этих штук будет по p норме ограничено γ p log n. То есть мы эту штуку сюда подставляем. Среднее вот этих штук – это независимые переменные, ограниченные m, и из них приходит член порядка n. И между этой разностью между средним функции gi и обобщающей ошибкой мы легко получаем оценку на обобщающую ошибку. Но при этом мы явно выделяем эти независимые слагаемые, которые дают член порядка 1n.
Может быть, тут есть какие-то студенты, кого интересует эта задача. Чтобы решать. Наша оценка выглядит таким образом. Этот момент обобщающей ошибки ограничен γ p log n+pn . И остается такой вопрос: а нужен ли вообще этот log? Мы не знаем, как доказывать без логарифма. То есть у нас конструкция, от которой очень сильно доказательство, где этот log неизбежен. Но при этом известно, что если взять p=2, то очень легко показать вот такую оценку (00:40:02). То есть log n для второго момента не должно быть. При этом даже для p=3 это уже неизвестно. То есть даже если сделать оценку для p=3 – это уже будет достаточно интересный результат.
(00:40:20)
А другая открытая задача, и Фельдман и Вондрак тоже об этом упоминают, что это еще нерешенная задача – насколько оптимальна зависимость от p. То есть этот член γ p, он дает как бы субэкспоненциальный хвост. А член-корень из p, он дает субгауссовский хвост. И вопрос: а нужен ли здесь субэкспоненциальный. Может, там что-то гораздо лучше. И нижних оценок для именно оценок с большой вероятностью пока не существует. То есть есть оценки с константной вероятностью. Естественно, это достаточно просто сделать. То есть в этом ничего удивительного нет.
И теперь как нам воспользоваться отделимостью семплирующей ошибки. Семплирующая ошибка – это то, что я говорил про то, что мы отделили член, который отвечает за ошибку порядка 1n. Стандартный подход, то есть обычно в оригинальной статье Фельдмана, или в оригинальной статье, которая у нас была в 2020 году, мы использовали неравенство Хердинга (00:41:37) для среднего и членов, которые мы отделяли. Но если использовать неравенство Бернштейна, можно что-то из этого вытащить.
И стандартное условие для таких оценок – это условие Бернштейна. Это уже технические моменты, но чтобы сформулировать результат – матожидание, разности, функции потерь на произвольном векторе w и на самом лучшем векторе w*, оно ограничено B умножить на разность рисков – B(R(w)– R(w*)). Это можно назвать избыточным риском параметра w. И B – просто какой-то параметр. Условие Бернштейна с параметром B выглядит вот так. И очень много есть всяких задач, где это условие выполняется. В частности в нашей задаче с сильно выпуклой оптимизацией. И мы доказываем следующее неравенство. Что если у нас есть какая-то ограниченная функция потерь и гамма-равномерный устойчивый алгоритм, то здесь уже мы не говорим про какую-то сильную выпуклость. Мы просто говорим, что есть функция потерь, есть равномерный устойчивый алгоритм, тогда выполнена такая оценка на избыточный риск. Избыточный риск ограничен оптимизационной ошибкой, плюс какая-то произвольная константа, сколь угодно близкая к нулю, но она должна быть константой.
Матожидание этой оптимизационной ошибки, что не очень приятная вещь, но мы пока не придумали пока, как от нее избавиться. Плюс константа, умножить на (γ log n+M+Bn)log(1/).
То есть в самом лучшем случае, когда γ порядка 1/n – это автоматически дает быстрый порядок. Если, конечно, оптимизационная ошибка достаточно маленькая. И напрямую из этого следует наша оценка для сильно выпуклой задачи. То есть для сильно выпуклого ERM мы берем B и γ. Я здесь неправильно написал. И B будет 2L2/λ, а γ будет порядка 1/n. Неправильно написал, извиняюсь (00:44:02). И тогда избыточный риск будет ограничен такой штукой. Опять-таки, log n здесь непонятно, насколько важен. Но если игнорировать всякие неприятные логарифмы, то это, по сути, быстрый порядок доказательств.
Также такая оценка должна быть верна для всяких градиентных спусков. В частности для градиентного спуска с постоянным шагом Хардт, Рехт и Сингер доказали, что у него тоже есть такая хорошая устойчивость. То есть та же самая устойчивость, что и у ERM. Но при этом, даже если у нас есть какой-то произвольный вообще алгоритм, и он сколь угодно близко приближается к ERM, мы тоже можем такую оценку сделать. Но в самом общем случае он просто, этот градиентный спуск, потребует больше шагов, чем у Хардта и товарищей.
(00:45:12)
Но еще один момент, который я пока что не упоминал – это то, что мы на самом деле в этом условии можем считать, что у нас даже не один минимум есть.
Условие сильной выпуклости – это очень старая задача. Сейчас в основном люди интересуются оптимизацией невыпуклых функций. И один из способов уйти от этого от условия сильной выпуклости, – это так называемое условие Поляка-Лояшевича. Там у нас вместо одного минимума есть какое-то множество минимумов. И, удаляясь от этого множества, функция растет квадратично. Грубо говоря, такое условие.
И, основываясь на этом условии, например, тоже есть оценки на стабильность ERM. Или на стабильность точнее градиентного спуска.
Но проблема там в том, что если у нас есть сильная выпуклость функции потерь, то мы знаем, что у нас и настоящий риск сильно выпуклый, и эмпирический риск сильно выпуклый. То есть это условие инвариантно к усреднению. А вот условие Поляка-Лояшевича, оно не инвариантно к усреднению. И, допустим, если мы скажем, что у нас пускай и функция риска удовлетворяет этому условию, и функция эмпирического риска точечно по всем выборкам удовлетворяет этому условию, то это какая-то непонятная вещь получается. Поэтому мы явно ничего не выписываем для этого условия. Но при этом какой-то research в этом направлении идет.
Еще как бонус мы показываем такой достаточно приятный результат. Здесь у нас есть матожидание оптимизационной ошибки, что не очень приятная вещь. И один способ – а давайте мы будем не избыточный риск оценивать, а вообще риск. В современных приложениях очень часто у нас получается, что эмпирическая ошибка практически ноль. То есть, допустим, какая-нибудь классификация изображений, например. И у нас избыточный риск – это более техническая вещь. А нас в принципе интересует, насколько маленький риск. То есть если мы обучались, обучались, обучались, получилось, что у нас эмпирическая ошибка ноль – а насколько это обобщает такую маленькую ошибку на всё распределение? И мы доказываем такую оценку, что если у нас просто есть ограниченная функция потерь и какой-то гамма равномерно устойчивый алгоритм, теперь нам никакого неравенства условий Бернштейна не нужно, просто такие простые условия, и тогда связь 1–δ, а настоящий риск ограничен единицей плюс какая-нибудь маленькая константа на эмпирический риск. И плюс такой член, который во всех наших оценках присутствует. То есть если γ порядка 1/n, то это автоматически будет всё примерно порядка 1/n, если мы игнорируем log (00:48:17).
И при этом, если мы знаем, что у нас эмпирический риск ноль, то мы автоматически ограничиваем настоящий риск быстрым порядком.
Но другое дело, что, насколько я понимаю, сейчас считается, что в принципе у нейронных сетей, скорее всего, нет устойчивости. То есть там есть такое понятие меморизации, когда есть какие-то… Если мы обучаем какой-то классификатор изображений, нам можно как можно больше примеров, которые всё покрывают. Там была одна статья, где они рассматривают какое-то распознавание городских мусорок на изображениях. Из-за того, что в разных городах разные мусорки, им нужно покрыть все возможные варианты, чтобы уметь распознавать эти вещи. То есть artificial intelligence, он, на самом деле, не такой уж и intelligence, потому что он просто обучается по примерам. Он не сможет распознать функциональность мусорки. Ему нужен именно конкретный пример, чтобы сделать правильный ответ.
И это понятие меморизации, на самом деле, прямо противоположно понятию устойчивости. Если мы выкидываем какой-то пример из нашей обучающей выборки, то на других картинках вне обучающей выборки ответ становится неправильный.
(00:50:00)
Но зато в этом неравенстве у нас есть один момент, что мы нашли там применение – есть одно очень красивое неравенство само-ограничивающих функций. Всегда приятно, когда находишь такие новые применения для старых вещей. Если интересно, можете почитать.
И чтобы подвести итог. Мы выявили новую обучающую оценку с отделимой ошибкой семплирования для устойчивых алгоритмов. И, основываясь на этом неравенстве, мы доказали, что избыточный риск – порядка 1/n для сильно выпуклой оптимизации.
И также мы рассмотрели некоторые общие оце4нки для избыточного риска устойчивых алгоритмов.
И также мы обсудили некоторые открытые вопросы с лишними логарифмами и нижними оценками для обобщающей ошибки в устойчивых алгоритмах.
В общем-то, всё. Спасибо большое за внимание. Если есть какие-то вопросы, с удовольствием попробую ответить.
Николай Михайловский: Егор, большое спасибо. Коллеги, пожалуйста, вопросы к Егору можно писать в Q&A, можно писать в чат. Пока вы думаете над своими вопросами, у меня к Егору парочка своих вопросов.
Примерно полгода назад в октябре был предпринят ребятами из Google и _____ (00:51:31) (наверное, так эта фамилия читается), и они говорят, что, на самом деле, не так интересно сравнивать эмпирический риск с абсолютным, а важно сравнивать ошибку на тесте, которая была получена при обучении на конечном множестве и на всей выборке. Ничего не слышали, не смотрели в эту сторону?
Егор Клочков: Не знаю… То есть я слышал про это, что, в конечном итоге, всегда важно, какая у нас ошибка hold out, просто потому что…
Николай Михайловский: У них фреймворк такой, что имеются две ограниченных выборки. Не одна как в классике, а две. Одна обучающая, другая тестовая. И мы сравниваем результаты обучения, результаты на тестовой выборке, обучение на обучающей выборке, и обучение на всем распределении. И некая суровая правда в этом есть, потому что в реалиях мы работаем в ситуации, когда у нас есть тестовая выборка, и конечная обучающая выборка. То есть, возможно, там какая-то собака порылась в этом месте. Не смотрели в такую сторону?
Егор Клочков: Нет, не смотрели. Я так понимаю, это вопрос к классической постановке с независимыми наблюдениями. То есть, в принципе, на деле у нас просто есть какой-то конечный набор этих пар признаков ответа, и мы случайно из них получаем какую-то обучающую выборку. Вопрос: как на самом деле семплируется в реальной жизни?
Николай Михайловский: Вопрос не только в том, как семплируется в реальной жизни, а вопрос в том, как результаты обучения… То есть если у нас есть два примера семплирования и некоторые алгоритмы… то есть один пример семплирования – это обучающая выборка, другой пример семплирования – это тестовая выборка. Как то, что у нас получилось при обучении на обучающей выборке, соотносится с тем, что бы получилось при обучении на распределении. То есть вопрос очень близкий к тому, что вы рассматриваете, но не идентичный.
Егор Клочков: Интересно. А как, вы сказали, называется?
Николай Михайловский: Я пришлю вам ссылку.
(00:54:51)
И есть еще одна задачка, которая меня очень занимает, тоже очень близкая. В большинстве случаев мы в реалиях работаем с грязными данными. То есть в большинстве случаев данные, так или иначе, размечены неточно. Есть такой эмпирически наблюдаемый эффект, состоящий в том, что если мы возьмем даже грязные размеченные данные и обучим на них нейронную сетку, то она будет давать правильный ответ, неплохой ответ. Более того, если мы эту выборку грязных данных будем увеличивать, сохраняя качество, то в некий момент мы на этом множестве можем получить качество лучше, чем у обучающей выборки.
Егор Клочков: Это похоже на… Есть такой подход, когда специально загрязняют данные, чтобы получилось что-то вроде регуляризации.
Николай Михайловский: Здесь не специально, здесь суровая правда жизни. Сергей Павлов говорит, это называется аугментацией. Здесь дело даже не в аугментации. Мы можем иметь классификацию на два класса, и мы можем часть лейблов флипнуть, то есть переставить.
У нас любимое приложение – это распознавание речи, например, и мы там работаем с разметкой, которая где-то в 10% случаев ложная. То есть там порядка 10% ошибок. Зачастую 20% ошибок. Тем не менее, результирующие системы, если таких грязных данных много, то мы получаем точность выше, чем точность разметки исходных данных. Соответственно, вероятно, можно получить какие-то оценки на то, как точность классификатора зависит от точности грязных данных и их количества.
Егор Клочков: Интересно.
Николай Михайловский: И, скорее всего, там должны быть какие-то оценки.
Сергей Павлов говорит, что это называется аугментацией. То, что я говорю – это не аугментация, а это именно загрязнение лейблов.
Пожалуйста, коллеги, еще какие-то вопросы к Егору?
Егор, большое спасибо. Я даже что-то стал понимать в том, что вы рассказывали, под конец. Очень интересный рассказ. И ссылку, которую я обещал, я вам вскоре пришлю. И, может быть, еще что-нибудь тоже пришлю.
Егор Клочков: Хорошо. Спасибо большое, что позвали.
Николай Михайловский: Спасибо! До свидания.
Егор Клочков: До свидания.
(00:58:44) (Конец записи.)