17.01.2020 09:22
SemyonSinchenko 4 3200 Источник

Эта статья является моим вольным пересказом работы Learnability can be undecidable, Shai Ben-David, et al.


Недавно на Хабре вышла статья Машинное обучение столкнулось с нерешенной математической проблемой, которая является переводом одноименного обзора в Nature News статьи Шай Бен-Давида. Однако, из-за особенностей тематики и краткости оригинального обзора мне осталось совершенно непонятно, что же было в статье. Зная Шай Бен-Давида, как автора прекрасной книги "Understanding Machine Learning: From Theory to Algorithms", я заинтересовался этой темой, ознакомился с этой работой и постарался тут изложить основные моменты.


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


Несколько слов об PAC-обучаемости в целом


Первое, что меня смутило в обзоре из Nature News это то, что сама по себе проблема обучаемости была представлена как что-то совершенно новое. На самом деле, это давно и относительно неплохо изученная проблема.


Несколько базовых понятий для тех, кто не знаком с вопросом

Риск — функция от $y, \hat{y}$ — реального и предсказанного значения целевой переменной, которая отражает то, насколько мы ошиблись в нашем предсказании. Меньшее значение отражает меньшую ошибку. Самый простой пример для задачи классификации это индикаторная функция $\mathbb{1}(y \neq \hat{y})$. Для регрессии это будет среднеквадратичное отклонение $\sqrt{y^2 - \hat{y}^2}$. Очевидно, могут быть и более сложные варианты. Другое название этого понятия — функция потерь.


Средний риск — среднее значение риска на всем пространстве входных данных. В силу того, что такое пространство обычно бесконечно (например, для вещественных признаков), либо экспонециально велико (например, пространство изображений размера 1024х1024 и значениями в пикселях от 0 до 255), мы не можем напрямую оценить эту величину. Однако, существуют методы оценки этой величины, в которые мы сейчас не будем вдаваться. Именно этот показатель мы в итоге хотим минимизировать. Иногда этот показатель называют также ошибкой обобщения (generalization error).


Эмпирический риск — среднее значение риска на некотором эмпирическом наборе данных, выбранных из всего пространства входных данных. Обычно именно минимизацией этой величины занимаются наши алгоритмы машинного обучения.


Задача машинного обучения — на основании имеющегося эмпирического набора данных построить решение (функцию), которое давало бы минимальное значение среднего риска.


Существует теория вероятно почти корректного обучения (Probably Approximately Correct Learning, PAC).


Упрощенное определение PAC-обучаемого алгоритма машинного обучения

Алгоритм A строящий по эмпирической выборке X размера n некоторую функцию h, восстанавливающую значение целевой переменной, является PAC-обучаемым, если для любого порога $\epsilon$ и степени уверенности $\delta$ существует такой размер обучающий выборки n, что для выученной на нем функции h выполняется следующее условие: вероятность того, что значение среднего риска превысит $\epsilon$, меньше чем $1 - \delta$.


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


Эта теория относится к 80-м годам прошлого века. Она, однако, не дает какого-либо измеримого показателя, который отражал бы способность того или иного алгоритма к обучению. Но такой ответ дает уже разработанная В. Вапником и А. Червоненкисом теория статистического обучения (VC-теория). В основе этой теории лежит численный показатель VC-размерности. VC-размерность — это комбинаторная оценка того максимального размера данных, которые алгоритм может разделить на две части всеми возможными способами.


Пример

Допустим у нас есть алгоритм, строящий разделительную гиперплоскость в n-мерном пространстве. Рассмотрим одномерное пространство: две точки в таком пространстве всегда можно разделить, а вот три разделить уже не получится, значит, VC=2. Рассмотрим двумерное пространство: три точки разделяются на два класса всегда, а вот четыре точки всеми возможными способами разделить уже не выйдет, значит, VC=3.


На самом деле, строго можно показать, что VC для класса гиперплоскостей в n-мерном пространстве равна $n + 1$.


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


Таким образом, сама по себе проблема обучаемости алгоритмов машинного обучения является относительно неплохо изученной и имеет строгую математическую базу.


О чем же тогда речь в статье в Nature?


Авторы пишут, что проблема PAC-теории, основанной на различных показателях размерности, заключается в том, что она не универсальная.


Различные показатели размерностей из PAC-теории
Задача Размерность
Бинарная классификация VC-размерность
Многоклассовая классификация размерность Натараджана
Регрессия Fat Shattering
... ...

Авторы приводят интересный пример задачи, сама постановка которой выполнена так, что успех не может быть сформулирован как PAC-обучаемость. Авторы пишут:


Представим, что у нас есть интернет сайт, на котором мы показываем рекламу. Определим X, как множество всех потенциальных посетителей этого сайта. Реклама выбирается из некоего пула рекламы. Условно, предположим, что каждое объявление из пула направлено на какую-то категорию пользователей: спортивные объявления любителям спорта и т.д. Задача состоит в том, чтобы разместить именно такую рекламу, которая наиболее релевантная посетителям сайта.


Проблема тут заключается в том, что мы на самом деле не знаем, кто именно посетит сайт в будущем. Если обобщить, постановка такой задачи может быть описана так:


Имея набор функций $F$ над множеством $X$, найти такую функцию $F_{best}$, чтобы ее метрика над неизвестным распределением $P$ была максимальной. Причем найти такую функцию надо, основываясь на ограниченном наборе независимых одинаково распределенных величин из $P$


EMX-обучение


Шай Бен-Давид и его коллеги вводят новое понятие — Estimating the MaXimum (EMX-обучаемости), которое как раз и дает критерии обучаемости для подобных задач максимизации:


Для набора функций $F$, множества входных данных $X$ и неизвестного распределения $P$, для любого числа $d = d(\epsilon, \delta)$, функция $G(S)$ является $(\epsilon, \delta)$-EMX-обучаемой, если для любого распределения $P$:


$Pr_{S \sim P^d}[\mathbb{E}_P(G(S)) \leq \sup_{h \in F} \mathbb{E} (h) - \epsilon] \leq \delta $


Такое определение обучаемости является несомненно более общим, нежели концепция PAC.


Тогда причем тут континуум и "нерешенная проблема математики"?


Авторы доказывают следующую теорему:
EMX-оубчаемость $F$ относительно $P$ не зависит от системы аксиом Цермело — Френкеля с аксиомой выбора (далее ZFC).


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


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


Существует такая константа $c$, что если предположить согласованность ZFC, то не существует такого свойства $A(X, Y)$, что для некоторых $inline$m, M > c$inline$ для любого $X$ и набора функций $F$ выполнялось бы:


  • Если $A(X, Y)$ верно, то $(1/3, 1/3)$-сложность EMX-обучения $F$ не превышает M;
  • Если $A(X, Y)$ ложно, то $(1/3, 1/3)$-сложность EMX-обучения $F$ по меньшей мере m;

Наоборот, это справедливо для, например, VC-размерности, так как для $A(X, Y)$ равном $VC \leq d$ это будет по сути формулировка основной теоремы VC-теории.


Заключение


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


  • Красивая связь EMX-обучения и теорем Гёделя;
  • Принципиальная невозможность создания универсальной характеристики обучаемости (типа VC-размерности) для общего класса задач машинного обучения.

При этом мне лично совершенно не нравится заголовок "Машинное обучение столкнулось с нерешенной математической проблемой", употребленный в переводе обзора этой статьи. На мой взгляд, это абсолютный кликбейт, более того, он просто не соответствует действительности. В оригинальной работе не идет речь о том, что кто-то с чем-то столкнулся. Машинное обучение и PAC-теория как работали, так и продолжают работать. Указано на то, что PAC-теория не может быть обобщена на некоторые, частные постановки задачи машинного обучения, найдены интересные связи с теоремами Гёделя, но ни слова о какой-то нерешенной проблеме, с которой столкнулось машинное обучение.