Теория распределенного обучения - Distribution learning theory

В теория распределенного обучения или же изучение распределения вероятностей это основа в теория вычислительного обучения. Это было предложено Майкл Кернс, Ишай Мансур, Дана Рон, Ронитт Рубинфельд, Роберт Шапир и Линда Селли в 1994 ^[1] и он был вдохновлен PAC-фреймворк представлен Лесли Валиант.^[2]

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

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

Определения

Позволять ${\displaystyle \textstyle X}$ быть опорой интересующих распределений. Как и в оригинальной работе Kearns et al.^[1] если ${\displaystyle \textstyle X}$ конечно, без ограничения общности можно считать, что ${\displaystyle \textstyle X=\{0,1\}^{n}}$ куда ${\displaystyle \textstyle n}$ это количество битов, которые должны быть использованы для представления любого ${\displaystyle \textstyle y\in X}$. Мы фокусируемся на распределении вероятностей по ${\displaystyle \textstyle X}$.

Есть два возможных представления распределения вероятностей ${\displaystyle \textstyle D}$ над ${\displaystyle \textstyle X}$.

• функция распределения вероятностей (или оценщик) оценщик ${\displaystyle \textstyle E_{D}}$ за ${\displaystyle \textstyle D}$ принимает на вход любые ${\displaystyle \textstyle y\in X}$ и выводит действительное число ${\displaystyle \textstyle E_{D}[y]}$ что означает вероятность того, что ${\displaystyle \textstyle y}$ в соответствии с ${\displaystyle \textstyle D}$, т.е. ${\displaystyle \textstyle E_{D}[y]=\Pr[Y=y]}$ если ${\displaystyle \textstyle Y\sim D}$.
• генератор генератор ${\displaystyle \textstyle G_{D}}$ за ${\displaystyle \textstyle D}$ принимает на вход строку действительно случайных битов ${\displaystyle \textstyle y}$ и выходы ${\displaystyle \textstyle G_{D}[y]\in X}$ согласно распределению ${\displaystyle \textstyle D}$. Генератор можно интерпретировать как процедуру, имитирующую выборку из распределения. ${\displaystyle \textstyle D}$ учитывая последовательность справедливых подбрасываний монеты.

Распределение ${\displaystyle \textstyle D}$ вызывается, чтобы иметь полиномиальный генератор (соответственно оценщик), если его генератор (соответственно оценщик) существует и может быть вычислен за полиномиальное время.

Позволять ${\displaystyle \textstyle C_{X}}$ класс распределения над X, т. е. ${\displaystyle \textstyle C_{X}}$ такое множество, что каждый ${\displaystyle \textstyle D\in C_{X}}$ - распределение вероятностей с поддержкой ${\displaystyle \textstyle X}$. В ${\displaystyle \textstyle C_{X}}$ также можно записать как ${\displaystyle \textstyle C}$ для простоты.

Перед определением обучаемости необходимо определить хорошие приближения распределения. ${\displaystyle \textstyle D}$. Есть несколько способов измерить расстояние между двумя распределениями. Еще три общие возможности:

• Расхождение Кульбака-Лейблера
• Общее расстояние вариации вероятностных мер
• Расстояние Колмогорова

Самым сильным из этих расстояний является Расхождение Кульбака-Лейблера а самый слабый - это Расстояние Колмогорова. Это означает, что для любой пары распределений ${\displaystyle \textstyle D}$, ${\displaystyle \textstyle D'}$ :

${\displaystyle KL-distance(D,D')\geq TV-distance(D,D')\geq Kolmogorov-distance(D,D')}$

Поэтому, например, если ${\displaystyle \textstyle D}$ и ${\displaystyle \textstyle D'}$ близки по отношению к Расхождение Кульбака-Лейблера то они также близки по отношению ко всем остальным расстояниям.

Следующие определения верны для всех расстояний, поэтому символ ${\displaystyle \textstyle d(D,D')}$ обозначает расстояние между распределениями ${\displaystyle \textstyle D}$ и распределение ${\displaystyle \textstyle D'}$ используя одно из расстояний, которые мы описали выше. Хотя обучаемость класса распределений может быть определена с использованием любого из этих расстояний, приложения относятся к определенному расстоянию.

Базовый ввод, который мы используем для изучения распределения, - это количество выборок, взятых этим распределением. С вычислительной точки зрения предполагается, что такая выборка дается за постоянный промежуток времени. Это похоже на доступ к оракулу ${\displaystyle \textstyle GEN(D)}$ который возвращает образец из распределения ${\displaystyle \textstyle D}$. Иногда интерес, помимо измерения временной сложности, состоит в том, чтобы измерить количество выборок, которые необходимо использовать, чтобы изучить конкретное распределение. ${\displaystyle \textstyle D}$ в классе раздач ${\displaystyle \textstyle C}$. Эта величина называется сложность образца алгоритма обучения.

Чтобы проблема распределенного обучения была более ясной, рассмотрим проблему контролируемого обучения, как определено в.^[3] В рамках этого теория статистического обучения тренировочный набор ${\displaystyle \textstyle S=\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$ и цель - найти целевую функцию ${\displaystyle \textstyle f:X\rightarrow Y}$ который минимизирует некоторую функцию потерь, например квадратная функция потерь. Более формально ${\displaystyle f=\arg \min _{g}\int V(y,g(x))d\rho (x,y)}$, куда ${\displaystyle V(\cdot ,\cdot )}$ функция потерь, например ${\displaystyle V(y,z)=(y-z)^{2}}$ и ${\displaystyle \rho (x,y)}$ распределение вероятностей, согласно которому отбираются элементы обучающей выборки. Если условное распределение вероятностей ${\displaystyle \rho _{x}(y)}$ известно, то целевая функция имеет замкнутый вид ${\displaystyle f(x)=\int _{y}yd\rho _{x}(y)}$. Итак, набор ${\displaystyle S}$ представляет собой набор образцов из распределение вероятностей ${\displaystyle \rho (x,y)}$. Теперь цель теории распределенного обучения - найти ${\displaystyle \rho }$ данный ${\displaystyle S}$ который можно использовать для нахождения целевой функции ${\displaystyle f}$.

Определение обучаемости

Класс распределений ${\displaystyle \textstyle C}$ называется эффективно обучаемый если для каждого ${\displaystyle \textstyle \epsilon >0}$ и ${\displaystyle \textstyle 0<\delta \leq 1}$ предоставлен доступ к ${\displaystyle \textstyle GEN(D)}$ для неизвестного распределения ${\displaystyle \textstyle D\in C}$, существует алгоритм с полиномиальным временем ${\displaystyle \textstyle A}$, называемый алгоритмом обучения ${\displaystyle \textstyle C}$, который выводит генератор или оценщик распределения ${\displaystyle \textstyle D'}$ такой, что

${\displaystyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta }$

Если мы это знаем ${\displaystyle \textstyle D'\in C}$ тогда ${\displaystyle \textstyle A}$ называется правильный алгоритм обучения, иначе называется неправильный алгоритм обучения.

В некоторых настройках класс раздач ${\displaystyle \textstyle C}$ - это класс с хорошо известными распределениями, которые можно описать набором параметров. Например ${\displaystyle \textstyle C}$ может быть классом всех гауссовских распределений ${\displaystyle \textstyle N(\mu ,\sigma ^{2})}$. В этом случае алгоритм ${\displaystyle \textstyle A}$ должен уметь оценивать параметры ${\displaystyle \textstyle \mu ,\sigma }$. В этом случае ${\displaystyle \textstyle A}$ называется алгоритм обучения параметрам.

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

Первые результаты

В своей основополагающей работе Kearns et al. иметь дело со случаем, когда ${\displaystyle \textstyle A}$ описывается в терминах схемы конечного полиномиального размера, и они доказали следующее для некоторых конкретных классов распределения.^[1]

• ${\displaystyle \textstyle OR}$ распределение ворот для этого типа распределений нет вычислителя полиномиального размера, если только ${\displaystyle \textstyle \#P\subseteq P/{\text{poly}}}$. С другой стороны, этот класс можно эффективно изучить с помощью генератора.
• Распределения ворот четности этот класс можно эффективно изучить как с помощью генератора, так и с помощью вычислителя.
• Смеси мячей Хэмминга этот класс можно эффективно изучить как с помощью генератора, так и с помощью вычислителя.
• Вероятностные конечные автоматы этот класс не может быть эффективно изучен с помощью оценщика в соответствии с допущением о шумовой четности, которое является невозможным предположением в среде обучения PAC.

${\displaystyle \textstyle \epsilon -}$Охватывает

Один очень распространенный метод поиска алгоритма обучения для класса распределений ${\displaystyle \textstyle C}$ сначала найти небольшой ${\displaystyle \textstyle \epsilon -}$обложка ${\displaystyle \textstyle C}$.

Определение

Множество ${\displaystyle \textstyle C_{\epsilon }}$ называется ${\displaystyle \textstyle \epsilon }$-обложка ${\displaystyle \textstyle C}$ если для каждого ${\displaystyle \textstyle D\in C}$ Существует ${\displaystyle \textstyle D'\in C_{\epsilon }}$ такой, что ${\displaystyle \textstyle d(D,D')\leq \epsilon }$. An ${\displaystyle \textstyle \epsilon -}$ крышка мала, если она имеет полиномиальный размер относительно параметров, описывающих ${\displaystyle \textstyle D}$.

Когда-то существует эффективная процедура, которая для каждого ${\displaystyle \textstyle \epsilon >0}$ находит небольшой ${\displaystyle \textstyle \epsilon -}$крышка ${\displaystyle \textstyle C_{\epsilon }}$ of C, то единственная оставшаяся задача - выбрать из ${\displaystyle \textstyle C_{\epsilon }}$ распространение ${\displaystyle \textstyle D'\in C_{\epsilon }}$ что ближе к раздаче ${\displaystyle \textstyle D\in C}$ этому нужно научиться.

Проблема в том, что данный ${\displaystyle \textstyle D',D''\in C_{\epsilon }}$ нетривиально, как мы можем сравнивать ${\displaystyle \textstyle d(D,D')}$ и ${\displaystyle \textstyle d(D,D'')}$ чтобы решить, какой из них ближе всего к ${\displaystyle \textstyle D}$, потому что ${\displaystyle \textstyle D}$ неизвестно. Таким образом, образцы из ${\displaystyle \textstyle D}$ должны использоваться для этих сравнений. Очевидно, что результат сравнения всегда имеет вероятность ошибки. Таким образом, задача аналогична поиску минимума в наборе элементов с использованием зашумленных сравнений. Для достижения этой цели существует множество классических алгоритмов. Самая последняя версия, обеспечивающая наилучшие гарантии, была предложена Даскалакис и Камат ^[4] Этот алгоритм устанавливает быстрый турнир между элементами ${\displaystyle \textstyle C_{\epsilon }}$ где победитель ${\displaystyle \textstyle D^{*}}$ этого турнира элемент, который ${\displaystyle \textstyle \epsilon -}$рядом с ${\displaystyle \textstyle D}$ (т.е. ${\displaystyle \textstyle d(D^{*},D)\leq \epsilon }$) с вероятностью не менее ${\displaystyle \textstyle 1-\delta }$. Для этого их алгоритм использует ${\displaystyle \textstyle O(\log N/\epsilon ^{2})}$ образцы из ${\displaystyle \textstyle D}$ и бежит в ${\displaystyle \textstyle O(N\log N/\epsilon ^{2})}$ время, где ${\displaystyle \textstyle N=|C_{\epsilon }|}$.

Суммы обучения случайных величин

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

Изучение биномиальных распределений Пуассона

Учитывать ${\displaystyle \textstyle n}$ независимые случайные величины Бернулли ${\displaystyle \textstyle X_{1},\dots ,X_{n}}$ с вероятностью успеха ${\displaystyle \textstyle p_{1},\dots ,p_{n}}$. Биномиальное распределение Пуассона порядка. ${\displaystyle \textstyle n}$ является распределением суммы ${\displaystyle \textstyle X=\sum _{i}X_{i}}$. Для изучения класса ${\displaystyle \textstyle PBD=\{D:D~{\text{ is a Poisson binomial distribution}}\}}$. Первый из следующих результатов касается случая неправильного обучения ${\displaystyle \textstyle PBD}$ а второй при правильном изучении ${\displaystyle \textstyle PBD}$. ^[5]

Теорема

Позволять ${\displaystyle \textstyle D\in PBD}$ то есть алгоритм, который дает ${\displaystyle \textstyle n}$, ${\displaystyle \textstyle \epsilon >0}$, ${\displaystyle \textstyle 0<\delta \leq 1}$ и доступ к ${\displaystyle \textstyle GEN(D)}$ находит ${\displaystyle \textstyle D'}$ такой, что ${\displaystyle \textstyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta }$. Примерная сложность этого алгоритма составляет ${\displaystyle \textstyle {\tilde {O}}((1/\epsilon ^{3})\log(1/\delta ))}$ и время работы ${\displaystyle \textstyle {\tilde {O}}((1/\epsilon ^{3})\log n\log ^{2}(1/\delta ))}$.

Теорема

Позволять ${\displaystyle \textstyle D\in PBD}$ то есть алгоритм, который дает ${\displaystyle \textstyle n}$, ${\displaystyle \textstyle \epsilon >0}$, ${\displaystyle \textstyle 0<\delta \leq 1}$ и доступ к ${\displaystyle \textstyle GEN(D)}$ находит ${\displaystyle \textstyle D'\in PBD}$ такой, что ${\displaystyle \textstyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta }$. Примерная сложность этого алгоритма составляет ${\displaystyle \textstyle {\tilde {O}}((1/\epsilon ^{2}))\log(1/\delta )}$ и время работы ${\displaystyle \textstyle (1/\epsilon )^{O(\log ^{2}(1/\epsilon ))}{\tilde {O}}(\log n\log(1/\delta ))}$.

Одна часть приведенных выше результатов заключается в том, что сложность выборки алгоритма обучения не зависит от ${\displaystyle \textstyle n}$, хотя описание ${\displaystyle \textstyle D}$ линейно по ${\displaystyle \textstyle n}$. Также второй результат является почти оптимальным с точки зрения сложности выборки, потому что также существует нижняя граница ${\displaystyle \textstyle O(1/\epsilon ^{2})}$.

В доказательстве используется небольшой ${\displaystyle \textstyle \epsilon -}$обложка ${\displaystyle \textstyle PBD}$ который был произведен Даскалакисом и Пападимитриу,^[6] чтобы получить этот алгоритм.

Изучение сумм независимых целочисленных случайных величин

Учитывать ${\displaystyle \textstyle n}$ независимые случайные величины ${\displaystyle \textstyle X_{1},\dots ,X_{n}}$ каждый из которых следует произвольному распределению с поддержкой ${\displaystyle \textstyle \{0,1,\dots ,k-1\}}$. А ${\displaystyle \textstyle k-}$сумма независимых целочисленных случайных величин порядка ${\displaystyle \textstyle n}$ является распределением суммы ${\displaystyle \textstyle X=\sum _{i}X_{i}}$. Для изучения класса

${\displaystyle \textstyle k-SIIRV=\{D:D{\text{is a k-sum of independent integer random variable }}\}}$

есть следующий результат

Теорема

Позволять ${\displaystyle \textstyle D\in k-SIIRV}$ то есть алгоритм, который дает ${\displaystyle \textstyle n}$, ${\displaystyle \textstyle \epsilon >0}$ и доступ к ${\displaystyle \textstyle GEN(D)}$ находит ${\displaystyle \textstyle D'}$ такой, что ${\displaystyle \textstyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta }$. Примерная сложность этого алгоритма составляет ${\displaystyle \textstyle {\text{poly}}(k/\epsilon )}$ и время работы также ${\displaystyle \textstyle {\text{poly}}(k/\epsilon )}$.

Другая часть заключается в том, что выборка и временная сложность не зависят от ${\displaystyle \textstyle n}$. Можно заключить эту независимость для предыдущего раздела, если мы положим ${\displaystyle \textstyle k=2}$.^[7]

Обучающие смеси гауссианов

Пусть случайные величины ${\displaystyle \textstyle X\sim N(\mu _{1},\Sigma _{1})}$ и ${\displaystyle \textstyle Y\sim N(\mu _{2},\Sigma _{2})}$. Определите случайную величину ${\displaystyle \textstyle Z}$ который принимает то же значение, что и ${\displaystyle \textstyle X}$ с вероятностью ${\displaystyle \textstyle w_{1}}$ и то же значение, что и ${\displaystyle \textstyle Y}$ с вероятностью ${\displaystyle \textstyle w_{2}=1-w_{1}}$. Тогда если ${\displaystyle \textstyle F_{1}}$ это плотность ${\displaystyle \textstyle X}$ и ${\displaystyle \textstyle F_{2}}$ это плотность ${\displaystyle \textstyle Y}$ плотность ${\displaystyle \textstyle Z}$ является ${\displaystyle \textstyle F=w_{1}F_{1}+w_{2}F_{2}}$. В этом случае ${\displaystyle \textstyle Z}$ как говорят, следует за смесью гауссианцев. Пирсон ^[8] был первым, кто ввел понятие смеси гауссианов в своей попытке объяснить распределение вероятностей, из которого он получил те же данные, которые он хотел проанализировать. Поэтому, выполнив множество вычислений вручную, он наконец приспособил свои данные к смеси гауссиан. Задачей обучения в этом случае является определение параметров смеси ${\displaystyle \textstyle w_{1},w_{2},\mu _{1},\mu _{2},\Sigma _{1},\Sigma _{2}}$.

Первая попытка решить эту проблему была от Дасгупта.^[9] В этой работе Дасгупта предполагает, что два средних значения гауссианцев достаточно далеко друг от друга. Это означает, что существует нижняя граница расстояния ${\displaystyle \textstyle ||\mu _{1}-\mu _{2}||}$. Используя это предположение, Дасгупта и многие ученые после него смогли узнать параметры смеси. Процедура обучения начинается с кластеризация образцы в два разных кластера, минимизируя некоторую метрику. Используя предположение, что средние значения гауссианов находятся далеко друг от друга, с высокой вероятностью выборки в первом кластере соответствуют выборкам из первого гауссиана, а выборки во втором кластере - выборкам из второго. Теперь, когда образцы разделены, ${\displaystyle \textstyle \mu _{i},\Sigma _{i}}$ могут быть вычислены с помощью простых статистических оценок и ${\displaystyle \textstyle w_{i}}$ сравнивая величину кластеров.

Если ${\displaystyle \textstyle GM}$ является набором всех смесей двух гауссианов, используя приведенную выше процедуру, можно доказать следующие теоремы.

Теорема ^[9]

Позволять ${\displaystyle \textstyle D\in GM}$ с ${\displaystyle \textstyle ||\mu _{1}-\mu _{2}||\geq c{\sqrt {n\max(\lambda _{max}(\Sigma _{1}),\lambda _{max}(\Sigma _{2}))}}}$, куда ${\displaystyle \textstyle c>1/2}$ и ${\displaystyle \textstyle \lambda _{max}(A)}$ наибольшее собственное значение ${\displaystyle \textstyle A}$, то есть алгоритм, который задан ${\displaystyle \textstyle \epsilon >0}$, ${\displaystyle \textstyle 0<\delta \leq 1}$ и доступ к ${\displaystyle \textstyle GEN(D)}$ находит приближение ${\displaystyle \textstyle w'_{i},\mu '_{i},\Sigma '_{i}}$ таких параметров, что ${\displaystyle \textstyle \Pr[||w_{i}-w'_{i}||\leq \epsilon ]\geq 1-\delta }$ (соответственно для ${\displaystyle \textstyle \mu _{i}}$ и ${\displaystyle \textstyle \Sigma _{i}}$. Примерная сложность этого алгоритма составляет ${\displaystyle \textstyle M=2^{O(\log ^{2}(1/(\epsilon \delta )))}}$ и время работы ${\displaystyle \textstyle O(M^{2}d+Mdn)}$.

Приведенный выше результат также можно обобщить в ${\displaystyle \textstyle k-}$смесь гауссианцев.^[9]

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

Теорема ^[10]

Позволять ${\displaystyle \textstyle F\in GM}$ то есть алгоритм, который дает ${\displaystyle \textstyle \epsilon >0}$, ${\displaystyle \textstyle 0<\delta \leq 1}$ и доступ к ${\displaystyle \textstyle GEN(D)}$ находит ${\displaystyle \textstyle w'_{i},\mu '_{i},\Sigma '_{i}}$ так что если ${\displaystyle \textstyle F'=w'_{1}F'_{1}+w'_{2}F'_{2}}$, куда ${\displaystyle \textstyle F'_{i}=N(\mu '_{i},\Sigma '_{i})}$ тогда ${\displaystyle \textstyle \Pr[d(F,F')\leq \epsilon ]\geq 1-\delta }$. Сложность выборки и время работы этого алгоритма ${\displaystyle \textstyle {\text{poly}}(n,1/\epsilon ,1/\delta ,1/w_{1},1/w_{2},1/d(F_{1},F_{2}))}$.

Расстояние между ${\displaystyle \textstyle F_{1}}$ и ${\displaystyle \textstyle F_{2}}$ влияет не на качество результата алгоритма, а только на сложность выборки и время выполнения.^[9][10]

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

1. М. Кернс, Ю. Мансур, Д. Рон, Р. Рубинфельд, Р. Шапайр, Л. Селли Об обучаемости дискретных распределений. Симпозиум ACM по теории вычислений, 1994 г. [1]
2. Л. Валиант Теория обучаемого. Сообщения ACM, 1984 г.
3. Лоренцо Росаско, Томазо Поджио, Рукопись «Регуляризационный тур по машинному обучению - MIT-9.520 Лекции», декабрь 2014 г. [2]
4. К. Даскалакис, Г. Камат Более быстрые и примерные почти оптимальные алгоритмы для правильного обучения смесей гауссианов. Ежегодная конференция по теории обучения, 2014 г. [3]
5. К. Даскалакис, И. Диакониколас, Р. Серведио Изучение биномиальных распределений Пуассона. Симпозиум ACM по теории вычислений, 2012 г. [4]
6. К. Даскалакис, К. Пападимитриу Редкие обложки для сумм индикаторов. Теория вероятностей и смежные области, 2014 г. [5]
7. К. Даскалакис, И. Диакониколас, Р. О’Доннелл, Р. Серведио, Л. Тан Изучение сумм независимых целочисленных случайных величин. Симпозиум IEEE по основам компьютерных наук, 2013 г. [6]
8. К. Пирсон Вклад в математическую теорию эволюции. Философские труды Королевского общества в Лондоне, 1894 г. [7]
9. С. Дасгупта Изучение смесей гауссианов. Симпозиум IEEE по основам компьютерных наук, 1999 г. [8]
10. А. Калаи, А. Моитра, Г. Валиант Эффективно обучающиеся смеси двух гауссианов Симпозиум ACM по теории вычислений, 2010 г. [9]