Вероятностное программирование на Scala

Сегодня мы публикуем внеочередной перевод — это будет обзорная статья блистательного Ноэля Уэлша о принципах вероятностного программирования. Статья публикуется по заявкам читателей, которые задают нашему блогу все более высокую планку — и это, безусловно, здорово!

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

Вероятностные модели и логический вывод

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

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

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

1. Выбрать несколько тем и присвоить им весовые категории;
2. Для каждой темы характерно свое распределение слов;
3. Исходя из такого распределения слов, выбираем конкретные слова, прочитанные на странице, пропорционально весовым категориям, присвоенным тем или иным темам.

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

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

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

Когда мы создали вероятностную модель (и вдоволь поприкалывались с липовыми данными), эту модель можно использовать для логического вывода. Логический вывод – это процесс «обратной перемотки модели». Мы смотрим на реальные данные, которые удалось наблюдать, и пытаемся догадаться, как могла бы выглядеть ситуация, недоступная для наблюдения. Например, можно воспользоваться текстом документа и попытаться выяснить, какой теме он посвящен, либо собрать астрономические данные и попытаться определить, какие звездные системы с наибольшей вероятностью пригодны для жизни. Поскольку мы не можем с уверенностью судить о состоянии этих ненаблюдаемых элементов нашей модели, можно построить вероятностное распределение всех возможностей. Создание такого распределения как раз и отличает байесовский вывод от альтернатив – например, от метода максимального правдоподобия, позволяющего выявить всего одно состояние ненаблюдаемых свойств.

Зачем нужно вероятностное программирование

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

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

Как было бы здорово, если бы можно было сделать алгоритм логического вывода, исходя лишь из описания модели. Ситуацию можно сравнить с программированием на ассемблере и на высокоуровневом языке. Пользуясь ассемблером, мы все оптимизируем вручную, реализуем собственные и управляющие структуры и т.д., в контексте конкретной проблемы, стоящей перед нами. То же самое происходит при создании специального алгоритма логического вывода для конкретной генеративной модели. При программировании на высокоуровневом языке мы пользуемся готовыми конструкциями, которые компилятор сам переводит на ассемблер. Продуктивность работы значительно повышается ценой небольшого снижения машинной производительности (чего мы зачастую даже не замечаем). Цель вероятностного программирования – точно такая.

Конечно же это монада!

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

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

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

Можно аннотировать эту модель типами, чтобы показать, как может решаться проблема. При помощи Distribution[A] представим распределение по типу A. Теперь документ генерируется так:

• выбираем некоторые темы — так можем получить Distribution[Seq[Topic]] (или просто Distribution[Topic] для более простой модели).
• из каждой темы получаем распределение по словам — это функция Topic => Distribution[Words].
• из этих распределений по словам выбираем конкретные слова, которые читаем на странице – извлечение делается из Distribution[Words].

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

Основная часть этой модели заключается в соединении Distribution[Topic] и Topic => Distribution[Words] для создания Distribution[Words], из которого можно построить документ. Кстати, чем нужно заменить ???, чтобы следующее тождество соблюдалось?

Distribution[Topic] ??? Topic => Distribution[Words] = Distribution[Words]

Ответ — flatMap, то есть, у нас есть монада. (Можете сами убедиться, что и законы монад тоже соблюдаются, однако, в данном случае нам нужно определить семантику flatMap. См. ниже.)

Если вы когда-либо работали со ScalaCheck или подобными системами – то, значит, пользовались монадой безопасности.

Построение алгоритмов логического вывода

Существует много способов реализовать монаду вероятности. Если мы имеем дело лишь с дискретными доменами, то можно все представить внутри предметной области как List[(A, Probability)] (где Probability может быть псевдонимом типа Double) и в точности вычислять результаты. В реальных приложениях польза от такого подхода невелика, поскольку нам, скорее всего, придется иметь дело со сплошными доменами, либо дискретными, но все равно крупными. Тогда размер представления в каждом flatMap будет расти экспоненциально. Пример реализации показан здесь.

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

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

Заключение и дальнейшая работа

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

Кроме того, вероятностное программирование изрядно пересекается с моими интересами в сфере машинного обучения и языков программирования. Если вы заинтересовались – вот доклад, слайды, код.

Источник: habrahabr.ru

Комментарии: