AlphaGo от Google DeepMind побеждает чемпионов GO по умной выборке. Человек постоянно решает проблемы с отбором проб. В отличие от многих алгоритмов машинного обучения (ML), мы не останавливаемся, чтобы сначала разобраться в математике. Например, мы следим за тем, чтобы не разговаривать с родителями в плохие времена, что исходит из нашего опыта. Профессиональные игроки подсчитывают карты, присваивая значение каждой карте, и ведут текущий подсчет просмотренных карт. Они меняют свои ставки в зависимости от числа счета, чтобы увеличить шансы на выигрыш. Отбор проб осуществляется легко и просто. Это привлекательно. В этой статье мы рассмотрим Марковскую цепь Монте-Карло, выборку по важности, алгоритм Метрополиса и выборку Гиббса, которые обычно используются в машинном обучении.
Задача
Успех этих примеров зависит от нескольких критических факторов. Во-первых, как мы можем создать плотное представление уже изученных данных? Даже с терабайтом памяти он все равно не соответствует комбинациям возможных сценариев. В AlphaGo используется глубокая сеть, и игроки создают текущую сумму для представления информации, необходимой им, чтобы обыграть казино. В машинном обучении ML мы можем моделировать данные с распределением Гаусса, содержащим средние значения и ковариацию, гораздо более плотное представление информации, которая нам небезразлична. Счетчики карт используют текущую сумму, потому что модель проста и легко управляема. Это важный принцип машинного обучения. Выбирайте модель с умом.
Но когда проблемы становятся сложными, простого отбора проб недостаточно. В противном случае каждый может стать мастером GO. Эффективность выборки критически важна для большого пространства поиска. Пространство поиска огромно. Небольшие отклонения от оптимального решения могут превратить нас из победителя в полного проигравшего. Многие собранные образцы не дают практически никакой дополнительной информации. Однако баланс исследования и эксплуатации - это искусство. Мы хотим получать самую лучшую информацию с наименьшими усилиями. Однако лучшая информация не обязательно означает жадное стремление к достижению цели. Иногда нам нужно чем-то пожертвовать ради долгосрочной выгоды. Успех AlphaGo способствует его эффективности сэмплирования, он сэмплирует движется разумно и адаптивно.
При выводе на основе выборки мы делаем выводы на основе выборочных данных. Например, из приведенной ниже выборки предельная вероятность p (Пол = мужской, Возраст = 24) = 2/18 может быть вычислена как:
Такие образцы могут быть собраны с помощью интервью по случайным телефонным звонкам. Но в ML мы можем предположить, что сжатая вероятностная модель p уже смоделирована и обучена с использованием экспертных знаний и данных обучения.
Как только модель известна, мы можем взять образцы из этого распределения p, чтобы сделать выводы. Однако в целом это непросто. Мы предлагаем вам сделать паузу на минуту и подумать о том, как отбирать данные из распределения так же просто, как стандартное нормальное распределение. Кумулятивное распределение ниже представлено не в замкнутой форме, которая может быть вычислена с помощью конечных операций.
К счастью, выборку можно выполнить с помощью преобразования Бокса-Мюллера. Если переменные U₁ и U₂ распределены равномерно, выбранные ниже Z ₀ и Z₁ будут иметь стандартное нормальное распределение.
Однако, если распределение не в какой-то особой форме, выборка в целом не проста. Например, многие модели машинного обучения построены с использованием байесовского вывода. Даже если мы можем моделировать априорность и вероятность с помощью хорошо известных распределений, их продукт, как правило, не в той форме, из которой легко произвести выборку.
Вывод
Давайте на мгновение изменим обсуждение. Как было показано раньше, с учетом вероятностной модели для p (x₁, x₂, x₃,…, xn) выводы можно разделить на следующие категории:
И их можно решить с помощью предельной вероятности.
и / или MAP (максимум апостериорный) вывод.
Однако сложность модели экспоненциально растет с увеличением количества переменных. Если мы не сможем найти достаточно независимости, чтобы упростить графическую модель, найти точное решение невозможно. В ML есть два основных метода аппроксимации: выборочный вывод и вариационный вывод. В этой статье мы рассмотрим первую.
Давайте продолжим математику для непрерывных переменных.
Как снова показано, многие вычисления сводились к вычислению предельных вероятностей. Во многих задачах машинного обучения или обучении с подкреплением нас также интересует вычисление математического ожидания f (x) с x, взятым из распределения p. Например, мы хотим знать средние награды за выполнение определенной последовательности действий. Фактически, маргинализацию и ожидания можно обсуждать вместе в одном контексте, поскольку маргинализацию можно легко выразить как ожидание.
При выводе выборки мы собираем выборку данных
для оценки предельной вероятности p (x₁,…) при вычислении:
Это делает выборку привлекательной, потому что ее легко сделать и понять. Настоящая проблема при выводе выборки - это ее эффективность. Если нам нужно собрать экспоненциальный объем данных, чтобы найти достаточно выборок, соответствующих предельной вероятности, решение не удастся.
Резюме
Подведем итоги. Для многомерного пространства большинство моделей не могут быть настолько упрощены, чтобы их можно было точно решить. Для вывода на основе выборки обычно требуется огромное количество точек выборки для необходимой точности. Чтобы он был успешным, нам нужно знать:
- как представить информацию в плотной модели,
- как выбрать данные из этой модели, и
- как эффективно отбирать образцы.
В этой статье мы частично рассмотрим два последних вопроса.
Метод Монте-Карло
В Монте-Карло, где собираются игроки, правят вероятность, статистика и психология. Метод Монте-Карло - это причудливое название для анализа случайного процесса с помощью повторной выборки. Меня всегда недоумевает, почему это называется методом Монте-Карло. Оказывается, Станислав Улам, математик и физик, участвовал в Манхэттенском проекте во время Второй мировой войны. Метод Монте-Карло был разработан Уламом в рамках секретного проекта под кодовым названием Монте-Карло, названного в честь казино Монте-Карло. Одно из приложений того времени - моделировать цепную реакцию водородной бомбы. Ученые хотят контролировать процесс. В противном случае моделирование такого случайного процесса было бы слишком сложным.
Оценка Монте-Карло
Давайте посмотрим, как вычислить математическое ожидание с помощью выборки. Для ожидания
Его можно оценить, нарисовав N i.i.d. точки данных из стр. Ожидаемое значение - это среднее значение f (x) с x, взятым из p.
Это просто. Расчетное ожидание будет несмещенным с дисперсией, обратно пропорциональной N. Согласно Закону большого числа, когда N увеличивается, дисперсия уменьшается, и оценка приближается к значению генеральной совокупности.
Генеративная модель
Многие вероятностные модели, такие как сеть Байеса, являются генеративной моделью. Короче говоря, мы можем брать образцы из этой модели, чтобы делать выводы.
В прямой выборке мы начинаем с узлов, которые не имеют зависимости, и спускаемся по дереву при выборке данных, используя условную вероятность для каждого узла. После многих итераций мы можем использовать собранные образцы для ответа на запросы.
Ненормализованное распределение
Прежде чем двигаться дальше, давайте сначала введем простую терминологию. В некоторых моделях, например в графической, мы вычисляем коэффициенты, а затем нормализовали результат с коэффициентом нормализации Z, чтобы преобразовать его в распределение вероятностей p. Для байесовской сети объединенные коэффициенты уже являются распределением и Z = 1. Для марковского случайного поля мы суммируем факторы для всех возможных x для вычисления Z.
Мы добавляем символ шляпы на p (x), чтобы указать, что это ненормализованное распределение. Поскольку Z суммирует все факторы по всем переменным, его сложно вычислить. Ненормализованное распределение часто предпочтительнее нормализованного распределения при разработке алгоритма машинного обучения, поскольку нам не нужно вычислять Z.
Выборка отклонения
Концепция отбраковочной выборки проста. Давайте объясним это для случаев, когда p (x) легко вычислить, но сначала сложно выполнить выборку из p. Мы разрабатываем простое для выборки распределение q. Мы делаем выборку из него и говорим, что выборочное значение равно xᵢ. Мы принимаем xᵢ в качестве выборки с вероятностью p (x) / q (x ). Интуитивно понятно, что принятая выборка будет пропорциональна p. Действительно, с доказательством позже, наши принятые образцы будут иметь распределение, подобное p.
Далее мы рассмотрим детали с общим сценарием, когда трудно выбрать данные из ненормализованного или нормализованного p.
Чтобы решить эту проблему, мы можем выбрать суррогатное распределение q, которое легко выбрать. Однако нам нужно еще три условия, чтобы это сработало. Во-первых, q будет генерировать образцы везде, где p. Математически, если p (x) ›0, q (x)› также 0. Во-вторых, мы выбираем наименьшее k, которое kq (x) больше ненормализованного p (x ) для всех x. Это непросто, особенно для многомерного пространства. Но можно расслабиться и найти наименьшее k, которое мы можем знать или найти, пока kq (x) является верхней границей . Это не повредит нашему решению, просто сделает его менее эффективным. В-третьих, мы принимаем данные из q с вероятностью, пропорциональной ненормализованному распределению, указанному ниже.
Интуитивно понятно, что мы принимаем данные с большей частотой, если ненормализованное значение p близко к верхней границе. Скажем, у выборочных данных есть распределение s. Приведенные ниже уравнения доказывают, что выборочные данные имеют распределение p. (Пока kq (x) является верхней границей ненормализованного p (x), вероятность принятия не будет обрезана при отклонении выборка.)
Но какова эффективность выборки? Сколько данных отклоняется во время выборки? Оказывается, эффективность выборки для многомерного пространства чрезвычайно мала, даже kq (x) очень близко к q (x ). Большинство образцов выбрасываются, поэтому этот метод не пользуется популярностью. Но это открывает возможности для других алгоритмов.
Выборка по важности
В выборке отклонения мы находим k такое, что kq (x) является верхней границей для ненормализованного p ( x). Наша цель - найти только хорошую верхнюю границу. Но что, если мы воспользуемся преимуществом вычисления нормализованного p (x), что это даст? Ожидание можно переписать как
Он оценивает f (x) с x выборкой из распределения q вместо p . Интуитивно, уравнение просто повторно взвешивает ожидаемое значение, чтобы отразить изменение частоты выборки между p и q.
Это называется выборкой ненормализованной важности. Если q легче выбрать, мы выиграем, если знаем, как вычислить соответствующее p (x). Если f (x) уже вычислено в предыдущих итерациях с распределением q, мы снова выигрываем, что происходит в некоторых методах обучения с подкреплением.
Чтобы получить наименьшую дисперсию ожидания, мы выбираем
То есть мы хотим q * ∝ | f (x) | p (x), т.е. мы хотим, чтобы q * отражал области с высокой вероятностью x, которые имеют | f (x) | ценность (доказательство). Низкая дисперсия позволяет нам брать меньше образцов.
В байесовской модели p легко вычислить. Но как мы можем распространить его на другие модели, включая MRF, которое легко вычислить только ненормализованным распределением? Давайте переформулируем уравнение на основе ненормализованного p.
Мы вычисляем rᵐ с ненормализованным распределением, а затем использовали общую сумму rᵐ для нормализации распределения. Это позволяет избежать вычисления обычного коэффициента нормализации Z. Это называется нормализованной выборкой по важности.
Но этот подход имеет свою цену. Выборка ненормализованной важности беспристрастна, в то время как нормализованная важность смещена. Однако нормализованная выборка по важности, вероятно, имеет меньшую дисперсию.
Взвешивание правдоподобия
Стратегия выборки до сих пор решает любые запросы, которые нам могут понадобиться. Иногда это похоже на приготовление полноценного ужина, когда мы просто хотим немного перекусить. Что, если мы просто хотим запросить p (x | e) только для некоторого наблюдаемого e, например, p (Gender = male | zipcode = 94232). Должны ли мы сгенерировать все возможные образцы или просто сгенерировать их с совпадающим e (с почтовым индексом, равным 94232)? Если существует много возможных значений для e, наши данные выборки будут содержать много точек выборки, которые не имеют отношения к делу. Наша эффективность выборки будет очень низкой.
Давайте повторим это упражнение для наблюдений с опытом всего 2 года и почтовым индексом 94222. Мы можем использовать выделенные ниже данные для вычисления P (Пол | год опыта = 2, почтовый индекс = 94222) . Результат показывает, что 94222 в основном составляют женское население. (Да, я сфабриковал этот результат, чтобы позже продемонстрировать важный момент.)
Теперь давайте сформулируем стратегию создания выборок с использованием прямой выборки. Но всякий раз, когда мы попадаем в узел с известными наблюдениями, мы заставляем переменную быть наблюдаемым значением вместо того, чтобы делать выборку с условной вероятностью узла. Предположим, g наблюдается со значением g³ ниже . Для d мы, как обычно, выбираем значения из условной вероятности. Но для g мы принудительно устанавливаем g³.
Ниже приведен один из возможных примеров, который мы можем сгенерировать. Почтовый индекс и год опыта будут точно соответствовать наблюдениям.
Однако есть серьезная проблема. Сгенерированные данные включают половину мужчин и половину женщин, что отражает генеральную совокупность в прямой выборке. Эти сгенерированные значения не генерируются на основе почтового индекса 94222. В этом почтовом индексе 6 из 7 должны быть женщинами. Чтобы решить эту проблему, мы присваиваем вес для каждой выборки данных. Это произведение всех условных вероятностей каждого наблюдаемого значения (почтовый индекс и опыт) с учетом родительских значений в выборке данных. В нашем примере наблюдаемые события - это почтовый индекс и год опыта. Вес будет
Например, предположим, что почтовый индекс зависит от пола, а опыт зависит от лет образования и возраста. w будет рассчитываться как:
Наконец, запрос для p (Gender | e) будет рассчитан как взвешенная пропорция: добавление весов для строк, соответствующих запросу, разделенных на добавленные веса для всех строк.
Передискретизация важности выборки (SIR)
Как мы помним, мы хотим, чтобы q было как можно ближе к p. q ниже будет часто выполнять выборку в областях, не имеющих значения для p. Даже предполагаемый результат имеет низкую дисперсию, но он не будет точным.
Поскольку проектирование q может быть непростым делом, можем ли мы разработать алгоритм, который может выполнять адаптивную выборку? Начнем с некоторого случайного распределения q, например, равномерного распределения. Но для нашей иллюстрации мы будем использовать гауссиан. Зеленые точки - это образцы, созданные q.
Затем мы вычисляем вес на основе выборки важности (p (x) / q (x)) . Таким образом, зеленые точки внутри p с имеют больший вес.
Затем вместо использования q для генерации выборок мы используем вес для определения следующего распределения выборки. Следовательно, данные выборки не будут сдвигаться в сторону p.
И для будущих итераций мы продолжаем использовать веса для генерации выборок для следующего раунда. Концептуально мы можем визуализировать зеленые точки как частицы. Мы повторно взвешиваем его размер в зависимости от весового коэффициента важности выборки. В следующих итерациях каждая частица порождает новые частицы в зависимости от ее взвешенного размера. Для получения дополнительной информации вы можете прочитать фильтр частиц здесь, который используется в технологии беспилотных автомобилей.
Проблема для вывода выборки
Многие выводы о выборке предполагают, что p трудно выбрать, поэтому вместо этого мы используем гибкое распределение q. Пока что модель q близка к p. Например, если p подобен Гауссу, q будет гауссовым. В большинстве проблем машинного обучения отсутствует генеральный план для этих глобальных структур. А человек не умеет многомерно мыслить или визуализировать. Таким образом, мы не понимаем p в глобальном масштабе и поэтому не можем получить q.
Возможно, для некоторых проблем машинного обучения нам следует использовать подход снизу вверх, а не подход сверху вниз. Действительно, многие проблемы машинного обучения пытаются найти местные знания, чтобы получить глобальное понимание. Как упоминалось ранее, мы часто знаем, как вычислить p (x), плотность вероятности в каждой точке. Мы можем начать решение проблемы с этой локальной информацией. Фактически, SIR в последнем разделе - хороший пример.
Чтобы продемонстрировать этот восходящий подход, давайте рассмотрим случайных покупателей из других городов в Сан-Франциско. На каждом углу улицы они смотрят вперед, чтобы увидеть, какое направление кажется более интересным. Через некоторое время все они должны оказаться в торговых районах - простой, но эффективный способ определить, где находятся самые популярные магазины.
Однако вместо того, чтобы использовать детерминированную политику на каждом углу, мы используем вероятностную модель. Это дает нам возможность исследовать, даже если иногда это кажется менее многообещающим. В частности, эта схема позволяет нам переходить из области высокой вероятности в другую, пересекая область низкой вероятности, только мы не будем тратить на это слишком много времени.
Далее мы опишем, как генерировать выборку адаптивно на основе последних данных выборки.
Процесс цепей Маркова
В процессе цепочки Маркова каждый узел ниже представляет собой состояние, например, мы находимся в магазине Apple. Стрелка представляет собой шанс перехода к следующему состоянию на следующем временном шаге. Например, 0,5 шанса, что мы останемся, и 0,2 шанса, что мы пойдем в Zara.
Такие переходы могут быть представлены в виде матрицы переходов A со следующим состоянием, вычисленным как:
Мы можем начать с начального состояния, скажем, мы находимся в магазине яблок, то есть [1, 0, 0,…]. Если выполняются некоторые условия, uk сходится к стационарному распределению π, а π (xᵢ) будет вероятностью находиться в состоянии xᵢ в стационарном распределении.
т.е. значения в матрице состояний u не изменятся.
Фактически стационарное распределение не зависит от начального состояния. Подробные математические рассуждения можно найти здесь. Но это может быть легче понять с точки зрения супруга. Независимо от того, куда вы высадите супруга за покупками, вы должны иметь разумную оценку его / ее возможного местонахождения позже. Не стоит недооценивать силу процесса цепей Маркова, помимо поиска супруга. Google начал свой алгоритм ранжирования веб-страниц (PageRank) с решения точной задачи, просто с довольно большой матрицы A для покрытия страниц в Интернете.
Итак, когда может существовать стационарное распределение. Двумя достаточными условиями являются
- Несводимость: вы можете перейти из одного состояния в другое. Приведенная ниже диаграмма не является неприводимой. Мы не можем достичь B из A и наоборот. Если вы начнете с C, у вас может быть два очень разных дистрибутива для вашего штата. Несводимость запрещает нам навсегда оставаться в ловушке подмножества состояний.
- Апериодичность: начиная с любого состояния, вы можете достичь того же состояния на любом временном шаге после некоторой разминки. Следующее - не апериодичность. Если мы начнем с A, мы сможем вернуться к A только с четным временным шагом. Технически апериодичность означает, что у вас период один. В противном случае распределение состояний для следующего временного шага не будет равно текущему распределению.
Еще одно достаточное условие, называемое детальным балансом, для стационарного распределения:
Если мы сможем найти π, удовлетворяющее вышеуказанному условию, π будет стационарным распределением, как показано ниже.
Для Google PageRank A содержит вероятность перехода с одной веб-страницы на другую для Интернета. Его содержание взвешивается по количеству гиперссылок, ведущих на страницу. Google решает эту проблему, продолжая умножать эту огромную разреженную матрицу A до тех пор, пока u не сойдется. (по крайней мере, это делается при основании компании.) Как перемножить две большие разреженные матрицы - это один вопрос на собеседовании по кодированию, который я услышал в Google. Хотя это хорошая проблема масштабируемости, ее тоже можно решить с помощью выборки. Мы используем вероятность перехода для выборки следующего состояния. После некоторой разминки собранные состояния будут хорошо представлять распределение π. Но опять же, мы предполагаем, что с p легко получить выборку. Давайте расширим идею без этого предположения.
Цепь Маркова Монте-Карло
В цепях Маркова Монте-Карло (MCMC) мы применяем концепцию цепей Маркова для выборки следующего состояния (также известного как выборка) на основе текущего состояния. Но мы обобщаем эту концепцию, вводя гибкое распределение предложений g при определении того, какое состояние выбрать следующим. Поэтому нам не требуется, чтобы p легко отбирать. Однако мы проверим, принимать ли новый образец, на основе некоторых приемочных испытаний, связанных с p. В случае отказа мы снова отбираем образец из последней точки отбора проб. Но приемочные испытания не являются обязательными. Если g связан с p, такой приемочный тест может не понадобиться. MCMC - это общая концепция, не диктующая, что такое рассылка предложения или дополнительный приемочный тест. Поэтому, чтобы понять это, будет лучше подробно описать некоторые из его конкретных методов.
Алгоритм Метрополиса-Гастингса
Алгоритм Метрополиса-Гастингса - один из самых популярных методов MCMC. Во-первых, давайте выберем распределение предложения g, которое определяет, какое состояние исследовать дальше. Одна из возможностей - нормальное распределение. т.е. мы выбираем соседа, у которого шансы экспоненциально уменьшаются по мере удаления от текущего состояния. Это просто и использует возможности того, что мы уже можем оказаться в области высокой плотности вероятности p после некоторой разминки. Можно использовать и другие варианты, но для демонстрации мы будем придерживаться нормального распределения.
Затем мы устанавливаем вероятность принятия A, относящуюся к p. Он определяет, выберем ли мы состояние кандидата для выборки или снова выберем другого соседа. Здесь мы примем новый образец x ’с вероятностью A, указанной ниже.
P (x ') / g (x' | x) похож на вес важности для x 'в SIR, в то время как P (x) / g (x | x ') подобен весу важности для x. Итак, A оценивает вероятность включения x ’ в выборку p. Нормальное распределение является симметричным, то есть g (x | x ’) = g (x’ | x). Таким образом, вероятность принятия A упадет ниже 1, если новое состояние x ' менее вероятно, чем текущее состояние x согласно p . Если g не является симметричным, мы даем больше шансов переходам, которые можно отменить проще, g (x '| x) ‹g (x | x' ).
Давайте проверим, можем ли мы использовать нормальное распределение в качестве распределения предложения для достижения стационарного распределения. Напомним, что достаточным условием является то, что мы можем перейти в одно состояние из другого, а период перехода равен единице. Для нормального распределения мы всегда можем достичь одного состояния из другого с ненулевой вероятностью. Чтобы удовлетворить второму условию, если текущее состояние - xᵢ, мы можем убедиться, что возможен переход от xᵢ к xᵢ в следующем шаг времени. Это верно для нормального распределения. Как показано ниже, если количество точек выборки увеличивается, распределение выборки будет напоминать распределение p. Таким образом, мы можем использовать собранную выборку для расчета математического ожидания или приблизительного значения p.
В нашем примере мы используем симметричное распределение предложений, и это будет называться алгоритмом Метрополиса (вместо алгоритма Метрополиса-Гастингса). Интуитивно понятно, что выборка xᵢ из xⱼ будет иметь такой же шанс в противоположном направлении. Вероятность принятия A будет упрощена до
Выборка Гиббса
Разработка распределения предложения может быть сложной задачей. Выборка Гиббса - еще один метод MCMC без специально разработанного предложения. Предположим, каждая точка данных состоит из D переменных. Предположим, что трудно сделать выборку из совместной вероятности p
но это не сложно, если мы исправим все, кроме одной переменной,
то есть условные распределения, приведенные выше, легко поддаются выборке. Затем вместо одновременной выборки всех значений D в выборке данных мы просто выбираем только один компонент. Для следующей выборки данных мы отбираем другой компонент. Таким образом, следующая точка данных отличается от предыдущей только на один компонент.
Следовательно, нам не нужно создавать распространение предложения независимо от p. Алгоритм будет:
Вот еще одна немного другая реализация.
Сэмплер Гиббса - это особый случай алгоритма Метрополиса-Гастингса. Приемочный тест нам не нужен, потому что его упростят до одного.
На левой диаграмме ниже мы наносим точки выборки для первых 50 итераций. Этот пример находится в двухмерном пространстве (D = 2). На каждой итерации мы меняем только одно измерение. Поэтому он движется по вертикали и горизонтали только на каждом чередующемся шаге. В примере выполняется выборка 1000 точек из исходного распределения данных p и 1000 точек выборки из выборки Гиббса. Как и ожидалось, оба графика похожи.
Недостаток
Методы, основанные на выборке, могут иметь несколько проблем. Поскольку это не метод оптимизации, целевой функции нет. Ключевым недостатком является то, что мы не можем оценить прогресс или то, насколько мы далеки от решения. Кроме того, многие методы выборки требуют распределения предложений, которое может быть нелегко разработать.
Следующий
Теперь мы рассмотрим логический вывод выборки. Вариационный вывод - еще одно важное приближение. Более подробную информацию можно найти в этой статье.
Для тех, кто интересуется AlphaGo Zero:
