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

Теория распределенного обучения или изучение распределения вероятностей является основой теории вычислительного обучения . Его предложили Майкл Кернс , Ишай Мансур , Дана Рон , Ронитт Рубинфельд , Роберт Шапир и Линда Селли в 1994 году. и он был вдохновлен структурой PAC, представленной Лесли Валиант .

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

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

Определения

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

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

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

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

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

Прежде чем определять обучаемость, необходимо определить хорошие аппроксимации распределения. $\textstyle D$. Существует несколько способов измерения расстояния между двумя распределениями. Три наиболее распространенные возможности:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\textstyle \epsilon -$Обложки

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

Определение

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

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

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

Обучение суммам случайных величин

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

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

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

Теорема

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

Теорема

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

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

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

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

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

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

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

Теорема

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

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

Обучение смесям гауссиан

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

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

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

Теорема

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

Приведенный выше результат также можно обобщить на $\textstyle k-$смесь гауссиан.

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

Теорема

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

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