В моем предыдущем посте я представил мотивацию графовых сетей, описанную в статье DeepMind, которую я читал [1]. Мы рассмотрели идеи реляционной индуктивной предвзятости и комбинаторного обобщения, которые описывают то, как мы, люди, думаем. В документе DeepMind утверждается, что использование графовых сетей для мышления, как люди, может помочь нам решить некоторые ключевые проблемы, такие как (1) сложное понимание языка/сцены, (2) рассуждения о структурированных данных, (3) перенос обучения за пределы условий обучения и (4) ) обучение на небольших объемах данных/опыта [1]. В этом посте я хочу представить базовую структуру графовой сети и некоторые концепции вероятности, благодаря которым они работают. В частности, мы обсудим концепции совместного распределения вероятностей и условной независимости. Давайте начнем.

Основные определения графа

В статье DeepMind вводится формальное определение графа с использованием следующих терминов [1]:

(1) Структура: расположение известных элементов. «Структурированное представление» отображает эту структуру, а «структурированное вычисление» оперирует всеми элементами структуры и структурой в целом.

(2) Сущность: это объект, представленный узлом на графике. У него есть некоторые атрибуты, такие как вес, размер или цвет.

(3) Отношение: это свойство, которое соединяет два объекта или узла вместе. Он также может иметь атрибуты, такие как «А в 10 раз тяжелее, чем Б». Атрибуты отношения также могут зависеть от глобального контекста; например, камень и перо будут иметь разное ускорение в зависимости от того, через какую среду они падают.

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

(5) Реляционное рассуждение: это описывает процесс, который мы используем для работы со структурированным представлением сущностей и отношений, используя набор правил.

Граф — это структура, содержащая объекты и отношения, и ее можно обосновать с помощью правил. В статье DeepMind дается интересная интерпретация этой сети графов с использованием вероятности — они говорят, что графы могут представлять совместные распределения, если явно известны условные независимости между переменными [1]. Но что это значит? Чтобы ответить на этот вопрос, я раскрою термины совместное распределение вероятностей и условная независимость.

Совместные распределения вероятностей и условная независимость

Совместное распределение вероятностей описывает вероятность того, что две или более случайные величины появятся одновременно [2]. Это способ описания отношений между переменными [2]. Совместная функция плотности вероятности будет описывать все возможные комбинации двух случайных величин, предполагая, что они непрерывны [2].

Как насчет условной независимости? Допустим, у нас есть два случайных события, A и B, и третье случайное событие, C [3]. События А и В условно независимы, если для данного С, то А не зависит от В [3]. Другими словами, если мы знаем, что произошло C, то знание того, что произошло A, не скажет нам ничего нового о том, произойдет ли B [3]. А? Давайте рассмотрим пример: Фатима и Хорхе работают в разных частях Питтсбурга, и они оба пытаются вернуться домой в конце дня [3]. Помимо работы в разных частях Питтсбурга, они еще и живут в совершенно разных районах [3]. Мы хотим знать, насколько вероятно, что Фатима и Хорхе вернутся домой вовремя, если в Питтсбурге идет дождь (события A и B) [3]. Мы знаем, что если идет дождь (событие C), то Фатима и Хорхе с большей вероятностью вернутся домой поздно [3]. Но если мы знаем, что Фатима возвращается домой поздно (событие А), говорит ли это нам больше о том, насколько вероятно, что Хорхе опоздает (событие Б)? Нет, это не так, потому что поездка Фатимы на работу полностью не зависит от поездки Хорхе [3]. Мы бы сказали, что соответствующие прибытия Фатимы и Хорхе домой условно независимы, учитывая знание погоды в Питтсбурге [3].

Таким образом, графовые сети способны описывать вероятность возникновения множества различных событий (их совместное распределение вероятностей), явно зная вероятность возникновения каждого события, зная о других событиях (их условную независимость) [1]. Это полезно, потому что возможность фиксировать совместные распределения вероятностей с использованием условной независимости точно «фиксирует разреженную структуру, которая лежит в основе многих реальных генеративных процессов» [1]. Другими словами, размышления о совместном распределении вероятностей и условной независимости отражают то, как на самом деле устроен мир, поэтому этот подход гарантирует, что графовые сети с большей вероятностью смогут точно представлять явления реального мира.

Позвольте мне подробнее остановиться на этом моменте, представив пример модели, которая может представлять совместные распределения вероятностей с использованием условной независимости: скрытая марковская модель [1]. Скрытая марковская модель — это статистическая модель марковского процесса [4]. Я знаю, я знаю, это не поможет. Что ж, статистическая модель — это модель, которая делает предположения о том, как были получены данные в выборке, а также, в более широком смысле, о том, как были созданы данные для большей совокупности, из которой была взята выборка [ 5]. Статистическая модель — это «идеальное представление процесса генерации данных» [5]. А марковский процесс или модель — это случайная модель, представляющая изменяющиеся системы [6]. Что особенного в марковском процессе, так это то, что мы предполагаем, что следующее состояние только зависит от текущего состояния, а не от предыдущих состояний [6]. Это допущение очень мощное и позволяет нам делать с этой моделью много вещей, которые мы не могли бы сделать с моделями, требующими знания истории системы [6].

Итак, скрытая марковская модель (СММ) — это статистическая модель марковского процесса, но как она работает? Мы используем HMM, чтобы узнать о процессе X, наблюдая Y [4]. Это полезно в ситуациях, когда вы не можете наблюдать за состоянием X напрямую, но можете наблюдать за процессом Y, связанным с X [4]. В каждый момент времени условная вероятность Y в этот момент, учитывая историю X, не должна зависеть ни от чего, кроме текущего состояния X [4]. Разве это не похоже на ситуацию с условной независимостью? Мы хотим знать совместную вероятность Y и X, исходя из предположения, что существует некоторая условная зависимость Y от X, учитывая наше знание истории X.

Позвольте мне привести еще один пример с Хорхе и Фатимой. Хорхе и Фатима — друзья, и они разговаривают каждый день [4]. Каждый день Фатима сообщает Хорхе, пошла ли она гулять, ходила по магазинам или убиралась в своей квартире, и ее решение о том, чем заняться, зависит от погоды [4]. Хорхе знает только то, что в целом бывает либо солнечно, либо идет дождь, но он не знает точных погодных условий каждый день [4]. Поскольку он не может наблюдать за погодой напрямую, Хорхе должен угадать, что это за погода, основываясь на том, что он знает о повседневной деятельности Фатимы [4]. Это показано на Рисунке 1 ниже. В этой ситуации мы моделируем совместное распределение вероятностей различных погодных явлений, явно учитывая условную независимость повседневной деятельности Фатимы. Такая модель может быть решена с использованием различных подходов, один из которых называется алгоритмом Витерби [4].*

Рисунок 1 — Источник [7]

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

Сноски:

*Алгоритм Витерби — это алгоритм динамического программирования, который ищет наиболее вероятный набор скрытых состояний, которые привели к последовательности наблюдаемых состояний [8].

Использованная литература:

[1] П. В. Батталья и др., Реляционные индуктивные смещения, глубокое обучение и графовые сети, июнь 2018 г. ArXiv ID: 1806.01261. https://arxiv.org/abs/1806.01261

[2] Стефани. Совместное распределение вероятностей. Статистика Как. https://www.statisticshowto.com/joint-probability-distribution/ Посещено 8 мая 2020 г.

[3] Википедия. Условная независимость. https://en.wikipedia.org/wiki/Conditional_independence Посещено 8 мая 2020 г.

[4] Википедия. Скрытая марковская модель. https://en.wikipedia.org/wiki/Hidden_Markov_model Посещено 8 мая 2020 г.

[5] Википедия. Статистическая модель. https://en.wikipedia.org/wiki/Statistical_model Посещено 8 мая 2020 г.

[6] Википедия. Марковская модель. https://en.wikipedia.org/wiki/Markov_model Посещено 8 мая 2020 г.

[7] Теренсхонлес. Скрытая марковская модель. Википедия. https://commons.wikimedia.org/wiki/File:HMMGraph.svg Посещено 12 мая 2020 г.

[8] Википедия. Алгоритм Витерби. https://en.wikipedia.org/wiki/Viterbi_algorithm#Example Посещено 8 мая 2020 г.

Первоначально опубликовано на https://sassafras13.github.io 12 мая 2020 г.