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

Теория распределенного обучения или изучение распределения вероятностей является основой в теория вычислительного обучения. Он был предложен Майклом Кирнсом, Дана Рон, Рониттом Рубинфельдом, Робертом Шапайром, а в 1994 году он был вдохновлен PAC-framework, представленный Leslie Valiant.

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

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

• 1 Определения
• 2 Первые результаты
• 3 $ϵ\; -\; \{\backslash \; displaystyle\; \backslash \; textstyle\; \backslash \; epsilon\; -\}$Covers
• 4 Обучающие суммы случайных величин
  • 4.1 Обучение Биномиальные распределения Пуассона
  • 4.2 Изучение сумм независимых целочисленных случайных переменных
• 5 Изучение смесей гауссианов
• 6 Ссылки

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

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

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

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

Пусть $CX\; \{\backslash \; displaystyle\; \backslash \; textstyle\; C\_\; \{X\}\}$класс распределения по X, то есть $CX\; \{\backslash \; displaystyle\; \backslash \; textstyle\; C\_\; \{X\}\}$- это такой набор, что каждый $D\; \in \; CX\; \{\backslash \; displaystyle\; \backslash \; textstyle\; D\; \backslash \; in\; C\_\; \{X\}\}$является распределением вероятностей с поддержкой $X\; \{\backslash \; displaystyle\; \backslash \; textstyle\; X\}$. $C\; X\; \{\backslash \; displaystyle\; \backslash \; textstyle\; C\_\; \{X\}\}$для простоты также может быть записан как $C\; \{\backslash \; displaystyle\; \backslash \; textstyle\; C\}$.

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

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

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

$KL\; -\; distance\; (D,\; D\; \prime )\; \ge \; TV\; -\; distance\; (D,\; D\; \prime )\; \ge \; К\; олмогорова\; -\; расстояние\; (D,\; D\; \prime )\; \{\backslash \; displaystyle\; KL-distance\; (D,\; D\; \text{'})\; \backslash \; geq\; TV-distance\; (D,\; D\text{'})\; \backslash \; geq\; Kolmogorov-distance\; (D,\; D\; \text{'})\}$

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

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

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

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

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

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

$Pr\; [d\; (D,\; D\text{'})\; \le \; ϵ]\; \ge \; 1\; -\; \delta \; \{\backslash \; displaystyle\; \backslash \; Pr\; [d\; (D,\; D\; \text{'})\; \backslash \; leq\; \backslash \; epsilon]\; \backslash \; geq\; 1-\; \backslash \; delta\}$

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

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

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

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

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

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

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

Определение

Набор $C\; ϵ\; \{\backslash \; displaystyle\; \backslash \; textstyle\; C\; \_\; \{\backslash \; epsilon\}\}$называется $ϵ\; \{\backslash \; displaystyle\; \backslash \; textstyle\; \backslash \; epsilon\}$- обложка $C\; \{\backslash \; displaystyle\; \backslash \; te\; xtstyle\; C\}$если для каждого $D\; \in \; C\; \{\backslash \; displaystyle\; \backslash \; textstyle\; D\; \backslash \; in\; C\}$существует $D\; \prime \; \in \; C\; ϵ\; \{\backslash \; displaystyle\; \backslash \; textstyle\; D\; \text{'}\backslash \; в\; C\; \_\; \{\backslash \; epsilon\}\}$так, что $d\; (D,\; D\text{'})\; \le \; ϵ\; \{\backslash \; displaystyle\; \backslash \; textstyle\; d\; (D,\; D\; \text{'})\; \backslash \; leq\; \backslash \; epsilon\}$. Обложка $ϵ\; -\; \{\backslash \; displaystyle\; \backslash \; textstyle\; \backslash \; epsilon\; -\}$мала, если она имеет полиномиальный размер относительно параметров, описывающих $D\; \{\backslash \; displaystyle\; \backslash \; textstyle\; D\}$.

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

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

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

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

Рассмотрим $n\; \{\backslash \; displaystyle\; \backslash \; textstyle\; n\}$независимые случайные величины Бернулли $X\; 1,\dots ,\; X\; n\; \{\backslash \; displaystyle\; \backslash \; textstyle\; X\_\; \{1\},\; \backslash \; dots,\; X\_\; \{n\}\}$с вероятностями успеха $p\; 1,\dots ,\; pn\; \{\backslash \; displaystyle\; \backslash \; textstyle\; p\_\; \{1\},\; \backslash \; dots,\; p\_\; \{\; n\}\}$. Биномиальное распределение Пуассона порядка $n\; \{\backslash \; displaystyle\; \backslash \; textstyle\; n\}$- это распределение суммы $X\; =\; \sum \; i\; X\; i\; \{\backslash \; displaystyle\; \backslash \; textstyle\; X\; =\; \backslash \; sum\; \_\; \{i\; \}\; X\_\; \{i\}\}$. Для изучения класса $PBD\; =\; \{D:\; D\; -\; биномиальное\; распределение\; Пуассона\}\; \{\backslash \; displaystyle\; \backslash \; textstyle\; PBD\; =\; \backslash \; \{D:\; D\; ~\; \{\backslash \; text\; \{-\; биномиальное\; распределение\; Пуассона\}\}\; \backslash \}\}$. Первый из следующих результатов касается случая неправильного обучения $PBD\; \{\backslash \; displaystyle\; \backslash \; textstyle\; PBD\}$, а второй - правильного изучения $PBD\; \{\backslash \; displaystyle\; \backslash \; textstyle\; PBD\}.$.

Теорема

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

Теорема

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

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

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

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

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

$k\; -\; SIIRV\; =\; \{D:\; D\; представляет\; собой\; k-сумму\; независимых\; целочисленных\; случайных\; величин\}\; \{\backslash \; displaystyle\; \backslash \; textstyle\; k-SIIRV\; =\; \backslash \; \{D:\; D\; \{\backslash \; text\; \{представляет\; собой\; k-сумму\; независимая\; целочисленная\; случайная\; величина\}\}\; \backslash \}\}$

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

Теорема

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

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

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

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

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

Теорема

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

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

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

Теорема

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

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

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