Теория распределенного обучения - 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 В ( cdot, cdot)}$ функция потерь, например ${ Displaystyle V (y, z) = (y-z) ^ {2}}$ и ${ Displaystyle rho (х, у)}$ распределение вероятностей, согласно которому отбираются элементы обучающей выборки. Если условное распределение вероятностей ${ Displaystyle rho _ {х} (у)}$ известно, то целевая функция имеет замкнутый вид ${ Displaystyle е (х) = int _ {у} ярд ро _ {х} (у)}$. Итак, набор ${ displaystyle S}$ представляет собой набор образцов из распределение вероятностей ${ Displaystyle rho (х, у)}$. Теперь цель теории распределенного обучения - найти ${ displaystyle rho}$ данный ${ displaystyle S}$ который можно использовать для нахождения целевой функции ${ displaystyle f}$.

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

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

${ Displaystyle Pr [д (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 substeq 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 = сумма _ {я} X_ {я}}$. Для изучения класса ${ displaystyle textstyle PBD = {D: D ~ { text {- биномиальное распределение Пуассона}} }}$. Первый из следующих результатов касается случая неправильного обучения ${ displaystyle textstyle PBD}$ а второй при правильном изучении ${ displaystyle textstyle PBD}$. ^[5]

Теорема

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

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

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

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

${ displaystyle textstyle k-SIIRV = {D: D { text {- k-сумма независимых целочисленных случайных величин}} }}$

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

Теорема

Позволять ${ 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 { текст {поли}} (к / эпсилон)}$ и время работы также ${ Displaystyle textstyle { текст {поли}} (к / эпсилон)}$.

Другая часть заключается в том, что выборка и временная сложность не зависят от ${ 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 _ {макс} ( Sigma _ {2}))}}}$, куда ${ displaystyle textstyle c> 1/2}$ и ${ Displaystyle textstyle лямбда _ {макс} (А)}$ наибольшее собственное значение ${ displaystyle textstyle A}$, то есть алгоритм, который задан ${ displaystyle textstyle epsilon> 0}$, ${ Displaystyle textstyle 0 < дельта 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 _ {я}}$ и ${ Displaystyle textstyle Sigma _ {я}}$. Примерная сложность этого алгоритма составляет ${ displaystyle textstyle M = 2 ^ {O ( log ^ {2} (1 / ( epsilon delta)))}}$ и время работы ${ Displaystyle textstyle О (M ^ {2} d + Mdn)}$.

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

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

Теорема ^[10]

Позволять ${ displaystyle textstyle F in GM}$ то есть алгоритм, который дает ${ displaystyle textstyle epsilon> 0}$, ${ Displaystyle textstyle 0 < дельта 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 '_ {я} = N ( mu' _ {я}, Sigma '_ {я})}$ тогда ${ 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]

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