Понимание вероятностных графических моделей: начните с основных понятий и оценки параметров

искусственный интеллект

от статбота

Автор: Прасун Гоял

Сборник "Сердце машины"

Участие: Панда

Вероятностная графическая модель является основным направлением исследований в области искусственного интеллекта. Недавно команда Statsbot пригласила исследователя данных Прасуна Гояла опубликовать в своем блоге базовое введение в вероятностные графические модели, состоящее из двух частей. Статья начинается с основных понятий и добавляет основные примеры приложений, чтобы помочь новичкам понять практическую ценность вероятностных графических моделей. The Heart of the Machine составил и представил эту статью.


Часть 1: Основная терминология и постановка задачи

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

Оказывается, многие проблемы выходят за рамки вышеизложенного. Например, для предложения «Мне нравится машинное обучение» укажите часть речи каждого слова (существительное, местоимение, глагол, прилагательное и т. д.). Как показывает этот простой пример: мы не можем решить эту задачу, рассматривая каждое слово по отдельности — «обучение» может быть как существительным, так и глаголом в зависимости от контекста. Эта задача важна для многих более сложных задач с текстом, таких как перевод с одного языка на другой, преобразование текста в речь и т. д.

Не существует очевидного способа решения этих проблем с использованием стандартных моделей классификации. Вероятностная графическая модель (PGM/вероятностная графическая модель) является мощной основой для изучения этих моделей с зависимостями. Этот пост представляет собой руководство по фреймворку, для написания которого команда Statsbot пригласила специалиста по данным Прасуна Гояла.

Прежде чем исследовать, как использовать вероятностные графические модели для задач машинного обучения, нам нужно понять структуру PGM. Вероятностные графические модели (или просто графические модели) формально состоят из графовых структур. Каждый узел графа связан со случайной величиной, а ребра графа используются для кодирования связи между этими случайными величинами.

В зависимости от того, является ли граф ориентированным или неориентированным, мы можем разделить шаблоны графа на две широкие категории —  байесовские сети и марковские сети.


Байесовские сети: модели ориентированного графа

Типичным примером байесовской сети является так называемая «студенческая сеть», которая выглядит так:

На этой диаграмме показана установка студента, поступающего на университетский курс. На этом графике 5 случайных величин:

  • Сложность прохождения (Difficulty): может принимать два значения, 0 означает низкую сложность, 1 означает высокую сложность

  • Уровень интеллекта ученика (Intelligence): может принимать два значения, 0 означает не умный, 1 означает умный

  • Оценка студента (Grade): может принимать три значения, 1 означает плохо, 2 означает удовлетворительно, 3 означает отлично

  • Студенческий балл SAT (SAT): принимает два значения: 0 для низкого балла и 1 для высокого балла.

  • Качество (Письмо) рекомендательного письма, которое студент получает от профессора после прохождения курса: Возможны два значения, 0 означает, что рекомендательное письмо не является хорошим, 1 означает, что рекомендательное письмо является хорошим

Ребра в этом графе кодируют зависимости между этими переменными.

  • Оценка студента зависит от сложности курса и интеллекта студента;

  • А оценка, в свою очередь, определяет, сможет ли студент получить хорошее письмо от профессора;

  • Кроме того, интеллект учащихся влияет на их баллы SAT в дополнение к их оценкам.

Обратите внимание, что направление стрелок указывает на причину и следствие — Интеллект влияет на баллы SAT, но SAT не влияет на Интеллект.

Наконец, давайте посмотрим на таблицы, связанные с каждым узлом, их официальное название — CPD/условное распределение вероятностей.


1. Условное распределение вероятностей

CPD Сложности и Интеллекта очень прост, потому что эти переменные не зависят ни от каких других переменных. По сути, эти две таблицы кодируют вероятности этих двух переменных, принимающих значения 0 и 1. Вы могли заметить, что значения в каждой таблице должны в сумме равняться 1.

Затем посмотрите на CPD для SAT. Каждая строка соответствует значению, которое может принимать его родительский узел (Intelligence), а каждый столбец соответствует значению, которое может принимать SAT. Каждая ячейка имеет условную вероятность p(SAT=s|Интеллект=i), то есть: учитывая значение интеллекта i, это вероятность того, что значение SAT равно s.

Например, мы можем видеть, что p(SAT=s¹|Intelligence=i¹) равно 0,8. То есть, если у студента высокий уровень интеллекта, существует вероятность 0,8, что он также имеет высокий балл по SAT. А p(SAT=s⁰|Интеллект=i¹) означает, что если уровень интеллекта учащегося высок, то вероятность низкого балла SAT составляет 0,2.

Обратите внимание, что значения в каждой строке в сумме равны 1. Это, конечно, потому что, когда Интеллект=i¹, SAT может быть только одним из s⁰ и s¹, поэтому сумма двух вероятностей должна быть равна 1. Точно так же CPD Леттера кодирует условную вероятность p (Letter = l | Grade = g). Поскольку Grade может принимать 3 значения, в этой таблице 3 строки.

Обладая вышеуказанными знаниями, CPD Grade легко понять. Поскольку у него два родителя, его условная вероятность имеет вид: p(Оценка=g|Сложность=d,SAT=s), что является вероятностью того, что Уровень равен g, когда Сложность равна d, а SAT равна s. Каждая строка этой таблицы соответствует паре значений Сложности и Интеллекта. Опять же, сумма значений в каждой строке равна 1.

Основное требование байесовских сетей состоит в том, что граф должен быть ориентированным ациклическим графом (DAG/направленный ациклический граф).


Сети Маркова: модели неориентированных графов

Простой пример сети Маркова:

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


1. Возможное использование

Так же, как в байесовских сетях есть CPD, в марковских сетях есть таблицы, которые объединяют отношения между узлами. Однако между этими формами и CPD есть два ключевых различия.

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

Полученная таблица называется «фактором» или «потенциальной функцией» и обозначается греческой буквой φ. Например, мы можем использовать следующую потенциальную функцию для описания взаимосвязи между переменными A, B и C, где C — «мягкое» исключающее ИЛИ (XOR) для A и B, то есть: если A и B не то же самое, то C, вероятно, будет равно 1; если A и B одинаковы, то C, вероятно, будет равно 0:

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

Структура графика и таблица могут кратко представлять совместное распределение вероятностей по этим случайным переменным.

Теперь у вас может возникнуть вопрос: зачем нужны ориентированные графы, а также неориентированные графы? Причина в том, что для некоторых задач более естественно использовать ориентированный граф, например, упомянутую выше студенческую сеть. Ориентированный граф может легко описать причинно-следственную связь между переменными — уровень интеллекта учащегося будет влиять на результат SAT, но SAT баллов не будет.Уровень интеллекта (хотя он может отражать уровень интеллекта учащегося).

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


постановка проблемы

Мы говорили о графиках, случайных величинах и таблицах, и вам может быть интересно, в чем смысл всего этого? Что именно мы пытаемся сделать? Есть ли здесь машинное обучение? Где данные, обучение, прогнозы? Этот раздел даст вам ответ.

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

Кроме того, у нас есть данные о каждом студенте каждого курса — об их уровне интеллекта, результатах SAT, оценках, которые они получили, и о том, получали ли они хорошие рекомендации от профессоров. По этим данным можно оценить параметры ЦПД. Например, данные могут показать, что учащиеся с высоким интеллектом, как правило, имеют хорошие результаты SAT, и тогда мы можем узнать, что p(SAT=s¹|Интеллект=i¹) является высоким. Это фаза обучения. Позже мы покажем, как мы можем выполнять такую ​​оценку параметров в байесовских и марковских сетях.

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

Хотя у нас нет CPD, который может напрямую информировать нас, мы можем видеть, что учащийся с высоким баллом SAT указывает на то, что учащийся также, вероятно, имеет высокий уровень интеллекта; таким образом, если сложность курса низкая, учащийся получает хорошую оценку. Вероятность оценки также будет выше, как показано красной стрелкой на изображении выше. Мы также можем захотеть оценить вероятность нескольких переменных одновременно, например, вероятность того, что студент получит хорошую оценку и хорошее рекомендательное письмо одновременно?

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

Ответ на эти вопросы аналогичен другим областям машинного обучения — в графических моделях этот процесс называется «вывод».

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


условная независимость

Структура графа, которую мы только что исследовали, на самом деле несет важную информацию об этих переменных. В частности, они определяют набор условных зависимостей между этими переменными, утверждение вида — «Если наблюдается А, то В не зависит от С».

Допустим, в студенческой сети вы видите студентку с очень высоким баллом SAT. Что вы думаете о ее рейтинге? Как мы видели ранее, высокий балл SAT указывает на высокий уровень интеллекта, поэтому вы можете рассчитывать на хорошую оценку. Что делать, если у студента низкий балл SAT? В этом случае можно ожидать, что рейтинг будет не очень высоким.

Теперь давайте предположим, что вы не только знаете, что у этой ученицы высокий балл по SAT, но и что у нее высокий уровень интеллекта. Если балл SAT высокий, то вы можете прогнозировать ее оценку как отличную. Но что, если балл SAT ниже? Вы по-прежнему можете рассчитывать на отличную оценку, потому что ученица очень умна, и вы можете предположить, что она недостаточно хорошо справляется с SAT. Таким образом, знание этого балла SAT ничего не говорит нам об уровне интеллекта этого студента. Чтобы сформулировать это с точки зрения условной независимости, можно было бы сказать: «Если наблюдается Интеллект, то САТ и Степень независимы».

Мы получаем эту информацию об условной независимости на основе того, как эти узлы связаны в графе. Если эти узлы соединены по-разному, то мы также получаем разную независимую от условий информацию.

Давайте посмотрим на другой пример.

Предположим, вы знаете, что у этого ученика высокий уровень интеллекта. Что вы можете сказать мне о сложности этого курса? Ничего не знаешь, да? А что, если я скажу вам, что этот студент получил плохую оценку по этому курсу? Это показывает, что курс сложен, потому что мы знаем, что способный ученик получает плохого. Таким образом, мы можем написать наше условное утверждение независимости: «Если Степень не соблюдается, то Интеллект и Сложность не зависят друг от друга».

Поскольку все эти операторы выражают независимость между двумя узлами при определенных условиях, они называются условной независимостью. Обратите внимание, что эти два примера имеют противоположную семантику: в первом примере независимость сохраняется, если наблюдаются связанные узлы, во втором — независимость сохраняется, если не наблюдаются связанные узлы. Эта разница вызвана способом соединения узлов (то есть направлением стрелок).

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

В марковских сетях мы можем использовать аналогичную интуицию, но поскольку нет направленных ребер (стрелок), утверждение условной независимости относительно простое — если нет пути между узлами A и B, такого, что все узлы наблюдаются, то A и В не зависят друг от друга. Другими словами: A и B не являются независимыми друг от друга, если все промежуточные узлы хотя бы на одном пути между A и B не наблюдаются.

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


Применение: Трехдверная задача

Вы, должно быть, видели какую-то версию этого вопроса в какой-нибудь телевизионной игре:

Ведущий покажет вам три закрытые двери, за одной машина, а за другими что-то никчемное. Вы можете выбрать дверь. Затем ведущий откроет одну из двух оставшихся дверей без машины. Теперь вы можете выбрать, заменить ли дверь по вашему выбору: оставить дверь, которую вы выбрали ранее, или выбрать закрытую дверь, оставленную хозяином. ты его заменишь?

Интуитивно казалось, что ведущий не раскрыл никакой информации. Оказывается, эта интуиция не совсем верна. Давайте разберемся в этой проблеме, используя наш новый инструмент «Графическая модель».

Давайте сначала определим некоторые переменные:

  • D: За машиной есть дверь.

  • Ф: Ваш первый выбор

  • H: Дверь, открытая хозяином

  • Я: Фа Д?

D, F и H могут принимать значения 1, 2 или 3, я могу принимать значения 0 или 1. D и I не наблюдаются, а F наблюдается. H остается незамеченным, пока модератор не откроет одну из дверей. Поэтому мы используем байесовскую сеть для решения нашей задачи:

Обратите внимание на направление стрелок — D и F не зависят друг от друга, I очевидно зависит от D и F, и дверь, выбранная модератором, также зависит от D и F. Вы ничего не знаете о D в данный момент. (Это похоже на структуру студенческих сетей, где знание уровня интеллекта учащегося не дает вам никакой информации о сложности курса.)

Теперь ведущий выбирает дверь H и открывает ее. Итак, теперь H наблюдается.

Наблюдение за H не дает нам никакой информации об I, т. е. не указывает, правильно ли мы выбрали ворота. Наша интуиция так думает. Но это дает нам некоторую информацию о D! (Аналогичным образом, по аналогии со студенческими сетями, если вы знаете, что у студентов высокий интеллект и низкие оценки, вы можете кое-что узнать о сложности курса.)

Давайте посмотрим, используя цифры. Таблица CPD для этих переменных выглядит так (это когда никаких переменных не наблюдается):

Таблицы для D и F просты — дверь с автомобилем за ней может быть любой из этих дверей с равной вероятностью, и вероятность того, что мы выберем одну из них, одинакова. В таблице I указано, что I=1, когда D и F одинаковы, и I=0, когда D и F разные. Таблица H говорит, что если D и F одинаковы, то модератор имеет одинаковую вероятность выбрать одну из двух других дверей, если D и F разные, то модератор выбирает третью дверь.

Теперь предположим, что мы выбрали дверь. То есть F теперь наблюдается, если предположить, что F=1. Так какова условная вероятность I и D при заданном F?

Используя эти уравнения, мы можем получить следующие вероятности:

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

Теперь хост открывает еще одну дверь за F, так что мы наблюдаем H. Предположим, что Н=2. Давайте снова вычислим условные вероятности I и D при заданных F и H.

Используя эти уравнения, мы можем получить следующие вероятности:

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

Таким образом, если мы поменяемся местами, то у нас будет две трети шансов получить машину; если мы не поменяемся, у нас будет одна треть шансов получить машину.

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


в заключении

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

Во второй части этого блога мы представим некоторые алгоритмы оценки и вывода параметров, а также другое приложение.


Часть II: Оценка параметров и алгоритмы логического вывода

В первой части этого руководства по вероятностным графическим моделям команда Statsbot представила два типа графических моделей: байесовские сети и сети Маркова. Кроме того, обсуждаются постановка задачи, условная независимость и применение графической модели к задаче о трех дверях. Эта часть познакомит вас с оценкой параметров и выводом, а также исследует другое приложение.


Оценка параметра


1. Байесовские сети

Оценить значения в таблице CPD байесовской сети так же просто, как подсчитать количество вхождений события в обучающих данных. То есть, если мы хотим оценить p(SAT=s1|Интеллект=i1), нам нужно только рассчитать долю точек данных с SAT=s1 и Интеллектом = i1 в общем количестве точек данных с Интеллектом = i1. Хотя такой подход может показаться специфичным для данной задачи, оказывается, что полученные таким образом параметры максимизируют правдоподобие наблюдаемых данных.


2. Марковская сеть

Вышеупомянутый метод подсчета не имеет статистической поддержки для сетей Маркова (и, таким образом, приводит к субоптимальным параметрам). Поэтому нам нужно использовать более сложные методы. Основная идея этих методов — градиентный спуск — мы определяем некоторые параметры, которые описывают его распределение вероятностей, а затем используем градиентный спуск, чтобы найти значения параметров, которые максимизируют вероятность наблюдаемых данных.

Наконец, у нас есть параметры нашей модели, и мы хотим использовать их на новых данных, т.е. сделать вывод!


рассуждение

Литература, посвященная вероятностным графическим моделям вывода, огромна по двум причинам:

1. Рассуждения — вот почему мы построили всю эту структуру — чтобы делать прогнозы на основе того, что мы уже знаем.

2. Рассуждения вычислительно сложны! Мы можем достаточно эффективно выполнять вывод на определенных типах графов, но графы в целом сложны в вычислительном отношении. Поэтому нам нужно использовать алгоритмы аппроксимации, чтобы найти компромисс между точностью и эффективностью.

Мы можем использовать рассуждения, чтобы ответить на некоторые вопросы:

  • Предельный вывод: нахождение распределения вероятностей конкретной переменной. Например, по графу с переменными A, B, C и D, где A принимает значения 1, 2 и 3, найдите p(A=1), p(A=2) и p(A =3).

  • Апостериорный вывод: если задана некоторая явная переменная v_E (E обозначает доказательство) и ее значение равно e, найдите апостериорное распределение p(v_H|v_E=e) некоторой скрытой переменной v_H.

  • Максимальный апостериорный вывод (MAP) (максимальный апостериорный вывод): учитывая некоторые явные переменные v_E, значение которых равно e, найдите конфигурацию, при которой другие переменные v_H имеют наибольшую вероятность.

Ответы на эти вопросы могут быть полезны сами по себе или использоваться как часть более крупной миссии.

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


устранение переменной

Используя определение условной вероятности, мы можем записать апостериорное распределение как:

Как мы можем вычислить числитель и знаменатель в приведенном выше уравнении? Проиллюстрируем на простом примере. Рассмотрим сеть с тремя переменными, совместное распределение которых определяется следующим образом:

Предположим, мы хотим вычислить p(A|B=1). Обратите внимание, что это означает, что мы хотим вычислить p(A=0|B=1) и p(A=1|B=1), которые в сумме должны быть равны 1. Используя приведенное выше уравнение, мы можем написать:

Числитель — это вероятность того, что A=0 и B=1. Нас не волнует значение C . Итак, мы сложим все значения C. (Это связано с тем, что базовые вероятности p(A=0, B=1, C=0) и p(A=0, B=1, C=1) являются взаимоисключающими событиями, поэтому их совместная вероятность p(A=0 , B=1) — сумма вероятностей.)

Таким образом, мы складываем строки 3 и 4, чтобы получить p(A=0, B=1)=0,15. Аналогично, сложение строк 7 и 8 дает p(A=1, B=1)=0,40. В качестве альтернативы мы можем вычислить знаменатель, просуммировав все строки, содержащие B=1, то есть строки 3, 4, 7, 8, в результате чего p(B=1)=0,55. Таким образом мы можем получить:


p(A=0|B=1) = 0.15 / 0.55 = 0.27

p(A=1|B=1) = 0.40 / 0.55 = 0.73


Если вы внимательно посмотрите на приведенные выше вычисления, то увидите, что мы сделали некоторое дублирование вычислений — дважды добавили строки 3 и 4 и строки 7 и 8. Более эффективным способом вычисления p(B=1) является непосредственное сложение значений p(A=0, B=1) и p(A=1, B=1) . Это основная идея исключения переменных.

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

Поскольку мы суммируем одну переменную за раз, тем самым исключая эту переменную, процесс суммирования нескольких переменных эквивалентен исключению переменных по одной. Поэтому мы называем этот процесс «устранением переменных».

Мы также можем довольно просто применить описанную выше процедуру к решению задач маргинального вывода или вывода MAP. Точно так же приведенные выше идеи можно легко обобщить и на марковские сети.

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


Распространение убеждений

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

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

Затем каждая пара соседних узлов отправляет друг другу «сообщения», и эти сообщения содержат свое локальное распределение. Теперь каждый узел проверяет полученные сообщения и объединяет их для обновления распределения вероятностей переменной.

На приведенной выше диаграмме C собирает информацию от соседних узлов A и B, а затем отправляет сообщение D. Затем D объединяет это сообщение с информацией от E и F.

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


приблизительное рассуждение

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


1. Приблизительный вывод на основе выборки

Эти алгоритмы используют выборку для оценки желаемых вероятностей. Возьмем простой пример. Рассмотрим такой сценарий: учитывая монету, как определить вероятность того, что она выпадет решкой? Самый простой способ сделать это — подбросить монету, скажем, 100 раз и посмотреть, сколько орла выпадет.

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

Для задач со многими переменными сложно генерировать качественные независимые выборки, поэтому мы генерируем выборки с зависимостями, то есть каждая новая выборка является случайной, но смежной с предыдущей выборкой. Этот алгоритм называется методом Монте-Карло с цепями Маркова (MCMC), поскольку выборки образуют цепь Маркова. Получив образец, мы можем использовать его для решения различных логических задач.


2. Вариационно-приближенное рассуждение.

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

Часто эти выражения содержат суммы или интегралы, точное вычисление которых требует чрезвычайно больших вычислительных ресурсов. Хороший способ аппроксимации этих выражений состоит в том, чтобы решить суррогатное выражение и сделать так, чтобы суррогатное выражение каким-то образом аппроксимировало оригинал. Это основная идея вариационных методов.

Когда мы пытаемся оценить сложное распределение вероятностей p_complex, мы определяем другой набор распределений вероятностей P_simple, которыми легче манипулировать, а затем получаем распределение вероятностей p_приблизительно, наиболее близкое к p_complex, на основе P_simple.


Применение: Шумоподавление изображения

Теперь давайте применим некоторые из идей, которые только что обсуждались, к реальной проблеме. Предположим, у вас есть следующее изображение:

Теперь предположим, что это изображение загрязнено случайным шумом и становится зашумленным изображением:

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

Первый шаг — подумать о том, какие переменные наблюдаются, а какие нет, и как мы можем соединить их, чтобы сформировать график. Давайте определим каждый пиксель зашумленного изображения как наблюдаемую случайную величину, а каждый пиксель исходного изображения — как ненаблюдаемую переменную. Таким образом, если размер изображения MxN, то имеется MN каждой из наблюдаемых и ненаблюдаемых переменных. Обозначим наблюдаемые переменные как X_ij, а ненаблюдаемые переменные как Y_ij. Каждая переменная может принимать значение +1 или -1 (для черных и белых пикселей соответственно). Учитывая наблюдаемую переменную, мы хотим найти наиболее вероятное значение ненаблюдаемой переменной. Это соответствует выводу MAP.

Теперь давайте построим структуру графа, используя некоторые знания предметной области. Понятно, что переменная, наблюдаемая в позиции (i,j) зашумленного изображения, зависит от переменной, не наблюдаемой в позиции (i,j) эталонного изображения. Причина в том, что большую часть времени они равны.

Какую дополнительную информацию мы можем получить? Для эталонного изображения соседние пиксели обычно имеют одинаковое значение — не на границах изменения цвета, а в пределах каждой одноцветной области. Итак, если Y_ij и Y_kl являются соседними пикселями, мы объединяем их.

Отсюда получаем структуру графа:

Среди них белые узлы представляют ненаблюдаемую переменную Y_ij, а серые узлы представляют наблюдаемую переменную X_ij. Каждый X_ij связан с соответствующим Y_ij, а каждый Y_ij связан со своими соседями.

Обратите внимание, что это сеть Маркова, потому что между пикселями изображения нет причинно-следственной связи, поэтому стрелки направления в байесовской сети здесь не подходят.

Наша задача рассуждения MAP может быть записана математически следующим образом:

Здесь мы используем некоторые стандартные методы упрощения, обычно используемые в расчетах максимального логарифмического правдоподобия. Мы будем использовать X и Y (без индексов) для обозначения набора всех значений X_ij и всех значений Y_ij соответственно.

Теперь нам нужно определить наше совместное распределение P(X,Y) в соответствии со структурой нашего графа. Предположим, что P(X,Y) состоит из двух типов факторов — ϕ(X_ij, Y_ij) и ϕ(Y_ij, Y_kl), соответствующих двум типам ребер в графе. Далее мы определяем эти факторы следующим образом:

  • ϕ(X_ij, Y_ij) = exp(w_e X_ij Y_ij), где w_e — параметр больше 0. Этот коэффициент принимает большее значение, когда X_ij и Y_ij равны, и меньшее значение, когда X_ij и Y_ij различны.

  • ϕ(Y_ij, Y_kl) = exp(w_s Y_ij Y_kl), где w_s также является параметром больше 0. Этот коэффициент больше, когда Y_ij и Y_kl равны.

Таким образом, наше совместное распределение может быть дано:

где (i, j) и (k, l) во втором квадрате — соседние пиксели, а Z — нормализующая константа.


Включение этого в наш вывод MAP дает:

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


Значения w_e и w_s получаются с использованием методов оценки параметров на основе эталонного изображения и пары зашумленных изображений. В этом процессе задействовано довольно много математики (хотя в конечном итоге он просто выполняет градиентный спуск для сложных функций), поэтому мы не будем здесь идти дальше. Предположим, у нас есть значения этих двух параметров, w_e=8 и w_s=10.

Этот пример фокусируется на рассуждениях. Имея эти параметры в руках, нам нужно решить вышеупомянутую проблему вывода MAP. Мы могли бы сделать это, используя вариант доверительного распространения, но на самом деле существует гораздо более простой алгоритм для графов этой конкретной структуры, итеративный условный режим (ICM/итеративный условный режим).

Основная идея такова: выбирать узел Y_ij на каждом шаге, затем проверять значение выражения вывода MAP, когда Y_ij=-1 и Y_ij=1, и выбирать узел с более высоким значением. Повторение этого процесса для определенного количества итераций или до сходимости обычно дает достаточно хорошие результаты.

Вы можете сделать это с помощью кода Python здесь:GitHub.com/Лжец Сун О....

Изображение с шумоподавлением, возвращаемое алгоритмом, выглядит следующим образом:

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

С количественной точки зрения, 10% пикселей в зашумленном изображении отличаются от исходного изображения, в то время как изображение, очищенное нашим алгоритмом, отличается от исходного изображения всего на 0,6% пикселей.

Обратите внимание, что граф, который мы используем, довольно большой — размеры этого изображения 440x300, поэтому общее количество узлов близко к 264 000. Следовательно, точный вывод в таких моделях практически невозможен, и результаты, которые мы получаем с помощью большинства алгоритмов (включая ICM), являются локально оптимальными.


обзор

Здесь мы кратко рассмотрим основные концепции, которые мы рассмотрели в этой статье, состоящей из двух частей:

  • Модель графа: модель графа состоит из структуры графа, где узлы представляют собой случайные переменные, а ребра представляют зависимости между переменными.

  • Байесовская сеть: представляет собой модель ориентированного графа, в которой каждый узел имеет связанное с ним условное распределение вероятностей.

  • Сеть Маркова: представляет собой неориентированную графическую модель, каждая клика имеет связанную с ней потенциальную функцию.

  • Условная независимость: в зависимости от того, как соединены узлы в графе, мы можем написать заявление об условной независимости в форме: «Данные Z, X и Y независимы друг от друга».

  • Оценка параметров: заполните таблицу CPD или вычислите потенциальную функцию с учетом некоторых данных и структуры графика.

  • Вывод: учитывая графическую модель, мы хотим ответить на вопросы о ненаблюдаемых переменных, которые обычно относятся к следующим проблемным областям: маргинальный вывод, апостериорный вывод и вывод MAP.

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


Суммировать

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

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

  • Графические модели в двух словах:Love.Stanford.Amount/~KO получил Linger/pap…

  • Учебник по графическим моделям: «Вероятностные графические модели: принципы и методы»

  • Статья «Сердце машины»: Хотите узнать о вероятностных графических моделях? Сначала вы должны понять основные определения и формы теории графов.

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

Оригинальная ссылка:

Часть 1: https://blog.statsbot.co/probabilistic-graphical-models-tutorial-and-solutions-e4f1d72af189

Часть 2:blog.stats bot.co/probabilist…