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

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

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

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

Пусть будет носителем интересующих распределений. Как и в оригинальной работе Кернса и др. ^[1], если конечно, то можно предположить без потери общности, что где — число битов, которое необходимо использовать для представления любого . Мы фокусируемся на вероятностных распределениях над .${\displaystyle \textstyle X}$${\displaystyle \textstyle X}$${\displaystyle \textstyle X=\{0,1\}^{n}}$${\displaystyle \textstyle н}$${\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}$

Пусть класс распределения над X, то есть множество такое, что каждое является распределением вероятностей с носителем . Для простоты его можно также записать как .${\displaystyle \textstyle C_{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 {\text{KL-distance}}(D,D')\geq {\text{TV-distance}}(D,D')\geq {\text{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}$

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

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

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

Одним из самых распространенных методов поиска алгоритма обучения для класса распределений является поиск сначала небольшого покрытия .${\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 }$${\displaystyle \textstyle \epsilon -}$${\displaystyle \textstyle D}$

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

Проблема в том, что, учитывая, что нетривиально, как мы можем сравнивать и для того, чтобы решить, какой из них ближе всего к , поскольку неизвестно. Следовательно, для выполнения этих сравнений должны использоваться образцы из . Очевидно, что результат сравнения всегда имеет вероятность ошибки. Поэтому задача похожа на нахождение минимума в наборе элементов с использованием шумных сравнений. Существует множество классических алгоритмов для достижения этой цели. Самый последний, который достигает наилучших гарантий, был предложен Даскалакисом и Каматом ^[4]. Этот алгоритм устанавливает быстрый турнир между элементами , где победителем этого турнира становится элемент, который близок к (т.е. ) с вероятностью не менее . Для этого их алгоритм использует образцы из и работает за время, где .${\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}$${\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 }|}$

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

Рассмотрим независимые случайные величины Бернулли с вероятностями успеха . Биномиальное распределение Пуассона порядка — это распределение суммы . Для обучения класса . Первый из следующих результатов касается случая неправильного обучения , а второй — правильного обучения . ^[5]${\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}$

Теорема

Пусть тогда существует алгоритм, который при заданных , и доступе к находит такой, что . Сложность этого алгоритма равна , а время выполнения равно .${\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})}$

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

Рассмотрим независимые случайные величины, каждая из которых следует произвольному распределению с носителем . Сумма независимых целочисленных случайных величин порядка есть распределение суммы . Для изучения класса${\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 )}$

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

Пусть случайные величины и . Определим случайную величину , которая принимает то же значение, что и с вероятностью , и то же значение, что и с вероятностью . Тогда если есть плотность и есть плотность плотности есть . В этом случае говорят, что следует смеси гауссианов. Пирсон ^[8] был первым, кто ввел понятие смесей гауссианов в своей попытке объяснить распределение вероятностей, из которого он получил те же данные, которые он хотел проанализировать. Поэтому, выполнив множество вычислений вручную, он, наконец, подогнал свои данные к смеси гауссианов. Задача обучения в этом случае состоит в определении параметров смеси .${\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}$${\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)}$

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

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

Теорема ^[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}))}$

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