Машинное обучение - графическая модель

Одно из основных различий между машинным обучением (ML) и глубоким обучением (DL) - это объем знаний в предметной области, необходимых для решения проблемы. Алгоритмы машинного обучения регулярно используют знания предметной области. Однако решение может быть необъективным, если знания неполны. Однако, если все будет сделано правильно, мы сможем решать проблемы более эффективно.

Графическая модель (GM) - это ветвь ML, которая использует граф для представления проблемы предметной области. Многие алгоритмы ML и DL, включая алгоритм наивного Байеса, скрытую марковскую модель, ограниченную машину Больцмана и нейронные сети, принадлежат GM. Изучение этого позволяет нам взглянуть на многие алгоритмы машинного обучения с высоты птичьего полета. В этой статье мы сосредоточимся на основных принципах представления проблемы с помощью графической модели. Позже в этой серии мы обсудим, как делается вывод и как обучается модель.

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

В GM мы моделируем задачу предметной области с набором случайных величин (X₁,..., Xn) как совместное распределение p (X₁,... ., Xn). Модель представлена ​​графиком. Каждый узел на графике представляет собой переменную, причем каждое ребро представляет зависимость или корреляцию между двумя переменными.

Например, описанная выше проблема спринклера моделируется тремя переменными:

1. включен ли дождеватель автоматически или выключен,
2. идет ли дождь, и
3. мокрая ли трава.

И моделируем задачу с совместной вероятностью

Сила совместной вероятности сейчас может не быть очевидной. Но он отвечает на широкий спектр запросов (вывод), включая

• Вероятность наблюдений P (E) - вероятность результатов лабораторных исследований (Evidence E).
• Предельная вероятность P (X₁), P (X₁, X₃) и т. Д. - шанс заболеть Альцгеймером в 70 лет.
• Условная вероятность (или апостериорное убеждение, основанное на доказательствах), P (Y | E) - вероятность того, что у вашего родителя будет болезнь Альцгеймера.
• Максимум заднего (MAP), arg max P (X, E) - наиболее вероятное заболевание по результатам лабораторных исследований.

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

Резюме

В GM мы выбираем граф для представления информации и их взаимосвязей в плотной форме. Мы делаем выводы в форме предельной вероятности P (x₁) , P (x₁, x₂ ), условная вероятность P (x | e) , или MAP arg max P ( x, e). И мы строим модель, максимизируя вероятность собранной нами выборки. В сочетании с теоремой Байеса он формирует базовую основу для определения неопределенности в реальном мире с помощью теории вероятностей. Прежде чем привести пример GM, давайте сначала посмотрим, как мы моделируем совместное распределение.

Совместная вероятность

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

Для L.H.S. распределение, мы можем расширить его, используя цепное правило.

Предположим, что после дальнейшего анализа проблемы предметной области мы обнаруживаем следующие утверждения о независимости. Например, первое утверждение - это переменная i, не зависящая от d.

Следовательно, мы можем упростить R.H.S. выражение как:

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

Эти параметры модели представлены в виде записей в таблице ниже.

Так в чем же сложность этих моделей? p (d, i, g, s, l) имеют 5 переменных с возможными комбинациями 32 (2⁵). Чтобы смоделировать p, мы выбираем данные для 32 возможных вариантов. Напротив, на графике выше 4 таблицы всего с 26 параметрами.

Не стоит недооценивать проклятие экспоненты. 64 переменные будут иметь комбинацию

то есть простое изображение в оттенках серого 8 × 8 будет содержать достаточно переменных (пикселей), которые сделают задачу ML слишком сложной для решения. В ML важно обнаружить независимость, чтобы разрушить проклятие этой экспоненциальной сложности, например, наивный байесовский классификатор, скрытая марковская модель, оценка максимального правдоподобия с iid и т. Д. Распределение переменной может быть вычислено с учетом всех ее соседей. знать. В ML отсутствует оригинальный грандиозный дизайн. Мы видим глобальное понимание с помощью локализованных результатов.

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

Давайте кратко рассмотрим вероятностную модель. Это будет нашей основой для дальнейшего обсуждения.

1. Смоделируйте проблему предметной области как совместное распределение.

2. Изучите параметры модели по данным с оценкой максимального правдоподобия MLE или максимальной апостериорной оценкой MAP.

3. Заключение. Типичные выводы в ML:

• Предельная вероятность p (X) путем суммирования по другим переменным.

• Условная вероятность, решаемая с помощью теоремы Байеса и предельных вероятностей.

• MAP-вывод (максимум апостериорный). Например, используйте теорему Байеса, чтобы найти наиболее вероятные значения для набора переменных с учетом наблюдений.

Второй вывод выше (условная вероятность) - это просто расширение предельной вероятности. Итак, пока мы сосредоточимся на предельном выводе и MAP выводе.

В практических задачах трудно вычислить предельные вероятности. Суммирование или интегрирование по всем другим переменным обычно NP-сложно. Это серьезная проблема при работе с вероятностными моделями, если мы не сможем обнаружить (или предположить) достаточную независимость, как в наивном байесовском алгоритме или скрытой марковской модели, чтобы уменьшить сложность до полиномиальной.

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

Далее мы подробно рассмотрим представление проблемы предметной области с помощью графа.

Байесовская сеть (BN)

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

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

Начнем с совместной вероятности и расширим ее с помощью цепного правила.

С помощью байесовской сети (BN) мы можем еще больше упростить условную вероятность. Например, P (S | R, W) становится P (S | R), потому что S не зависит от W. Общий вид условной вероятности в каждом узле принимает следующий вид:

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

Сделаем несколько прогнозов. Условную вероятность P (R | W) дождя с учетом влажной травы можно рассчитать по теореме Байеса, за которой следуют соответствующие предельные вероятности.

Совместная вероятность в R.H.S. будут расширены с помощью условных вероятностей, определенных в GM, и решены с помощью исключения переменных или некоторых методов приближения, которые будут обсуждаться в следующих статьях.

Вот еще один BN и совместная вероятность.

Согласно графику, совместная вероятность p может быть разложена на множители как

Например, совместное распределение в этом примере факторизуется как

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

Генеративная сеть

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

По этому же принципу GAN (Generative Adversary Network) генерирует необработанное изображение путем первой случайной выборки скрытой переменной.

Резюме

BN - это график, в котором каждый узел представляет переменную с одной условной вероятностью p (x | x_parent) - вероятность x с учетом его родителей. Затем мы можем факторизовать совместную вероятность в соответствии с этим GM.

Независимость

3 + 4 равно 5 + 2. То есть даже формулы разные, они идентичны. Имея два графика, они могут моделировать одну и ту же проблему, даже если они выглядят по-разному. Когда p факторизуется в соответствии с зависимостью в байесовской сети G), мы говорим, что p факторизуется по G. Но G не обязательно является самой простой моделью для нашей проблемы предметной области. Мы можем упустить некоторую возможную независимость. Однако мы просто усложняем модель, но решение остается верным.

Следовательно, мы можем использовать независимость при определении того, дадут ли две графические модели одинаковый результат. Давайте еще немного осмыслим идею независимости.

Если переменные X и Y независимы (X ⊥ Y), то p (X, Y) = p (X) p (Y). Во-первых, давайте введем следующие обозначения для обозначения такой независимости.

Если две переменные A и B независимы, знание A не дает нам никакой информации о B или наоборот.

Для первой диаграммы выше, если мы знаем A, тогда распределение вероятностей для B и C будет известно и не будет зависеть от какой-либо переменной. Следовательно, B и C не зависят друг от друга при условии A (B ⊥ C | A ∈ I (p)).

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

Но если A неизвестен, знание B может дать нам информацию от C до A. Следовательно,

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

Рассмотрим второй случай (v-структура).

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

Путь на графике считается активным, если он несет информацию. В третьем случае ниже (Каскад), если мы знаем A, тогда C не зависит от B. Нам больше не нужно B, чтобы вычислять C.

Знание B не дает нам дополнительной информации о C, и, следовательно, путь неактивен. Но если A неизвестен, путь активен. B и C разделены d (разделены зависимостями или разделены направленно), если все пути, которые их соединяют, неактивны. Итак, в зависимости от того, что наблюдалось, мы можем проверить, разделены ли две переменные d. Обрести независимость без сложной математики будет намного проще. Фактически, анализ можно провести, разделив граф на подграфы с одной из трех структур ниже.

Например, L не зависит от {I, D, S} заданного G.

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

Вот еще один анализ переменной D, когда наблюдается C. D и A разделяются d, если соблюдается C. С другой стороны, все красные узлы имеют активный путь с D, если наблюдается C, т.е. они не разделены d. (График анализируется этой программой.)

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

I-карта (карта независимости)

Условные независимости позволяют сравнивать BN. Пусть I (G) - все условные независимости, подразумеваемые DAG G и I (p) - все условные независимости выполняются для совместного распределения p. G - это I-карта распределения p, если I (G) ⊆ I (p). G - это минимальная I-карта для p, если удаление одного края делает ее не I-картой. Если I (G) = I (p), G - идеальный карта. Найти идеальную карту может быть непросто, но нам нужно как минимум I (G) ⊆ I (p ).

Короче говоря, если I (G) является I-картой для p, I (p ) содержит все зависимости I (G), то есть все независимости I (G ) не будет нарушать правила в I (p). Так что способ разложения p над G будет правильным. Но G не обязательно самый простой. Мы можем не открыть для себя всю независимость. Это может быть сложнее, чем могло бы быть.

I-карта не уникальна. Я (p) могу иметь много I-map. Для полносвязного графа G (каждый узел соединен друг с другом) его множество независимости будет пустым. Следовательно, полностью связанный G всегда является I-картой для любого распределения p, поскольку I (G) = ∅ ⊆ I (p).

Без доказательств, давайте сделаем несколько утверждений.

• Найти идеальную карту в BN не всегда возможно.
• Совершенная карта не может быть уникальной.
• Две графики имеют одинаковый скелет, если они одинаковы, если игнорировать стрелку в зависимости.

Чтобы карты были идеальными, G и G 'должны иметь одинаковый скелет и одинаковые v-структуры.

Оба BN, представленные ниже, имеют одинаковый скелет и v-образную структуру и, следовательно, одинаковы.

Примеры BN

Посмотрим еще примеры BN. Мы можем использовать BN, чтобы связать заболевания d и лабораторные данные f. Однако условная вероятность p (fᵢ | dⱼ) может оставаться слишком сложной, поскольку многие результаты могут быть вызваны множеством различных заболеваний. Мы можем дополнительно упростить совместную вероятность, используя параметризацию зашумленного или приведенного ниже.

Вот примеры BN по скрытой марковской модели и модели гауссовой смеси.

Ограничения BN

BN - ориентированный ациклический граф . Направленный характер ребра и неациклическое поведение графа делают невозможным совместное моделирование некоторых предположений о независимости. Некоторые независимые предположения не могут сосуществовать в BN. Например, обе приведенные ниже BN могут выполнять A ⊥ C | {B, D}, но не B ⊥ D | {A, C}. Если мы хотим независимости вместе, это непросто.

Это часто случается, когда связь между двумя переменными является двунаправленной. Например, друзья могут голосовать аналогичным образом. Влияние двунаправленное (не направленное). Одно из решений - ввести в график дополнительные переменные, но это увеличит сложность модели.

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

Марковские случайные поля

Есть два основных варианта графической модели. Б.Н. - один из них. Второй - это марковские случайные поля (MRF). MRF моделируют проблему с помощью неориентированного графа.

Он моделирует корреляцию между переменными, а не зависимость.

где 𝜙 - факторная функция для оценки корреляций между ее параметрами. Это заменяет условную вероятность в BN. 𝜙 может быть любой настраиваемой функцией подсчета очков. Однако p должно быть вероятностным распределением. Поэтому мы перенормировали результат на Z, который называется функцией разбиения . Вы часто будете слышать этот термин в ML, который ведет себя как фактор нормализации, суммируя все оценки для всех возможных комбинаций переменных.

Мы обсудим 𝜙 и Z позже. Здесь мы просто вводим абстрактную концепцию моделирования корреляций между переменными. В нашем примере выше p (A, B, C, D, E) будет высоким, если (A, B), ( B, C), (C, D) и (D, A) сильно коррелированы соответственно. При сравнении MRF с BN мы меняем край на ненаправленный и используем факторные функции вместо условных вероятностей.

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

Вот уточненное определение MRF. Граф разбит на клики. Каждая клика может оценить корреляцию между своими узлами. В этом расширенном определении коэффициент 𝜙 может принимать любое ненулевое количество параметров и может быть различным для каждой клики.

p (X) называется распределением Гиббса по MRF G, если p можно разложить на множители с помощью кликов в G. Наше определение MRF не диктует, какие клики будут использоваться при факторизации, если они являются кликами, узлы которых полностью связаны. Действительно, разный выбор клик приводит к разной факторизации. Это остается на усмотрение дизайнера модели. Все три приведенные ниже факторизации действительны для этого MRF. Первые два используют попарную клику, а последний - максимальную клику. Все могут создать одно и то же решение. Для второй может потребоваться пять двумерных таблиц, а для третьей - две трехмерные таблицы для представления совместной вероятности.

Вот еще один пример:

Учтите, что никакие два соседних дома в Чинкве-Терре не будут окрашены в один цвет. Вот модель MRF, которую мы можем построить для четырех соседних домов и соответствующих факторов.

Есть и другие варианты расчета факторов 𝜙. Допустим, у нас есть только 3 цвета краски, мы можем разработать факторы как

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

Теорема Хаммерсли – Клиффорда

Без доказательства теорема Хаммерсли – Клиффорда утверждает, что если p (X) ›0 для всех X и G является I-картой для p (X) (условная независимость G является подмножеством условных зависимостей p : I (G) ⊆ I (p) ), тогда p (x) - это распределение Гиббса, которое факторизуется по G.

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

Энергетическая модель

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

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

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

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

Для особо любопытных читателей ниже приводится ограниченная машина Больцмана (RBM) и то, как рассчитывается функция энергии. vᵢ и hᵢ (скрытая единица / скрытый фактор) равны 0 или 1. W ᵢⱼ учитывает корреляции между vᵢ и hⱼ. В RBM мы хотим тренировать a, b, W так, чтобы у нас была самая низкая свободная энергия для обучающего набора данных.

BN - это частный случай MRF, в котором в качестве фактора используется условная вероятность и Z = 1. Но, как и BN, MRF может быть не самой простой моделью для p. Но он предоставляет альтернативу, которую мы можем попробовать проверить, может ли он лучше смоделировать проблему.

Модель Изинга

Как упоминалось ранее, графическая модель широко используется в физике. Рассмотрим решетку атомов. В соответствии с квантовой механикой спин каждого атома либо вверх, либо вниз.

Распределение спиновой конфигурации для этой решетки:

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

Морализация

BN можно преобразовать в MRF, изменив край на ненаправленный и соединив вместе родительские элементы v-структуры.

Морализация превращает BN в неориентированную графическую модель, но не обязательно сохраняет всю условную независимость. Например, A ⊥ B теряется, в то время как A не является независимым от B при введении C.

Недостатки MRF

Вот недостатки MRF:

• Вычисление статистической суммы Z в целом NP-сложно, обычно требуется использование аппроксимации.
• Это не генеративная модель. Мы не можем легко сгенерировать данные / выборку из этой модели.

В общем, MRF может быть более сложным, но требовательным к вычислениям. Мы можем сначала использовать BN для простоты, если он не отвечает за независимость моделирования.

Марковское одеяло

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

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

Если наблюдаются B, D, A и C графически разделены и независимы. Если соблюдены A, C, A и C независимы. Таким образом, мы достигаем независимости, которую BN не может достичь без добавления дополнительных узлов.

Мы можем доказать, что A и C независимы при условии B с помощью теории вероятностей.

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

Разделение графов равносильно условной независимости. Это гораздо более простой инструмент для обретения независимости.

Условные случайные поля

Ранее мы строили GM для моделирования совместного распределения для p (x₁, x₂, x₃,…). Как только это построено, мы делаем все возможные запросы, используя эту совместную вероятность. Тем не менее, во многих задачах машинного обучения нас интересуют только определенные типы запросов. Например, при обучении с учителем тип запроса обычно имеет форму условной вероятности p (y | x), где y - метка, а x - наблюдение. Как обсуждалось ранее, учитывая, что наблюдаются некоторые переменные, мы можем дополнительно сократить график, чтобы упростить модель.

В качестве альтернативы, мы можем спроектировать GM с самого начала, исходя из того, что доказательства известны. Компромисс в том, что он может отвечать только на определенный тип запроса. Условные случайные поля (CRF) - это неориентированные графические модели, которые непосредственно моделируют условные распределения p (y | x). CRF - это частный случай MRF. После построения графической структуры вся факторизация, обучение модели и логический вывод будут такими же, как и в MRF. Ниже приведен один из возможных вариантов CRF, в котором наблюдение xᵢ связано только с yᵢ, а yᵢ также связано с y в соседнем шаге. В самом деле, это скрытая марковская модель (HMM).