Вредоносное ПО (malware) - это назойливые или опасные программы,...
Вероятностное программирование — тема для меня новая и интересная. Немного , добавил отсюда и предлагаю вам готовый вариант из двух статей. Автор — один и тот же человек, Бо Кронин. Ниже — только его текст.
Недавно DARPA (Агентство передовых оборонных исследовательских проектов США) объявило о новой инициативе, связанной с финансированием исследований в области языков вероятностного программирования. Несмотря на то что в новостях сразу появились сюжеты, в которых под определенным соусом были поданы объяснения, почему же эти исследования так важны, данная область по-прежнему остается новой и довольно неясной для большинства специалистов, работающих в области искусственного интеллекта.
Итак, что же такое «вероятностное программирование» и почему на него стоит обратить внимание? Вот некоторые мои соображения по этому поводу.
Язык вероятностного программирования — это язык, в котором случайные события имеют статус примитивов первого класса. Если реализовать выразительный потенциал реального языка программирования таким образом, что он сможет обращаться со случайными событиями, то разработчик сможет легко кодировать на подобном языке сложнейшие структурированные стохастические процессы. Таким образом, можно создавать вероятностные модели событий, которые могли бы произойти в мире и генерировать заданную коллекцию данных или наблюдений.
Но в том, чтобы выразить вероятностную модель в виде компьютерной программы, нет ничего особенного — эта задача решается на уровне синтаксиса. Истинный же потенциал вероятностного языка программирования заключается в его компиляторе и среде времени исполнения (как и другие языки, вероятностный язык может быть компилируемым либо интерпретируемым). Наряду с решением обычных задач, такой компилятор или такая среда должны понимать, как выполнять в программе операции выведения (inference). Выведение позволяет ответить на вопрос вида: «какие из всех способов, которыми может выполниться программа, содержащая возможности случайного выбора, позволяют наилучшим способом описать имеющиеся данные?»
В чем же заключается автоматическое выведение? Давайте сравним вероятностную программу с классической компьютерной моделью — например с моделью климатических изменений. Нам потребуется написать программу, которая принимает в качестве ввода некий набор исходных условий, например историю температур, оценка энергии, получаемой от Солнца и т. д. Затем обычная модель использует предположения программиста о том, как должны взаимодействовать эти переменные величины. Переменные заключаются в тождествах и коде, который позволяет прогнозировать, как климат будет изменяться в будущем. Модели такого рода фактически однонаправленные: они развиваются от причин к гипотетически выводимым следствиям.
В вероятностной программе все совершенно наоборот. Имея универсум всех возможных взаимодействий между элементами климатической системы, а также набор наблюдаемых данных, мы можем автоматически заключить, какие взаимодействия наиболее полно объясняют наблюдаемые явления — даже если эти взаимодействия довольно сложны. А как это выглядит на практике? В сущности, среда времени исполнения вероятностного языка программирования одновременно выполняет программу и из начала в конец, и из конца в начало — как от данных к эффектам, так и от эффектов к тем данным, которые могли к ним привести. При грамотной реализации программы можно максимально эффективно использовать оба этих направления и находить наиболее вероятные объяснения наблюдаемых явлений.
Где: Simulation — Моделирование
Probabilistic program — Вероятностная программа
Input — Ввод
Output (Data) — Вывод (данные)
Inference — Выведение
Можно сформулировать иначе: в отличие от обычной программы, которая выполняется лишь в «прямом направлении», вероятностная программа может выполняться как в прямом, так и в обратном направлении. При работе в прямом направлении программа рассчитывает все возможные следствия тех предпосылок, которые заложены в нее в виде информации о мире (под миром здесь понимается представленное в ней пространство-модель). Но программа может работать и в обратном направлении, отталкиваясь от имеющихся данных.
Второй способ работы применяется для ограничения набора возможных объяснений. На практике во многих вероятностных программах эти «прямые» и «обратные» операции, очевидно, будут переплетаться, чтобы программа с максимальной эффективностью давала лишь наилучшие объяснения.
В этом и заключается сущность вероятностного программирования. Но почему же оно нас так интересует?
Дело в том, что вероятностное программирование может дать ключ к нарративному описанию данных. Эта возможность давно кажется Святым Граалем бизнес-аналитики и научного подхода к языковым воздействиям. Человек мыслит сюжетными историями. Вот почему примеры из практики так серьезно влияют на принятие решений, независимо от того, насколько обоснованным будет такое решение. Но в рамках имеющейся аналитики сформулировать такие истории обычно не удается. Слишком часто кажется, что цифры взяты откуда-то с потолка. А человек, который взвешивает различные варианты, предпочитает ориентироваться именно на «рабочий» контекст.
Вероятностную программу как раз можно написать «генеративным» образом. Таким образом, в программе можно непосредственно закодировать целое пространство гипотез. Каждая из таких гипотез является вариантом объяснения того, как модель мира породила наблюдаемые данные. Конкретные решения, выбираемые из имеющегося множества, будут конкретными «прикладными» и нарративными объяснениями для данных.
В данном случае было бы идеально скомбинировать наилучшие аспекты эмпирического и статистического обоснования. Так мы сможем одновременно пользоваться и убедительностью «реальных историй», и предсказуемостью (а также широкими обобщениями), обеспечиваемой большими корпусами данных.
Вероятностное программирование позволяет размежевывать моделирование и выведение. Точно как в современных базах данных выполнение запросов абсолютно не связано с индексированием и хранением информации, а в высокоуровневых языках и компиляторах вопросы построения алгоритмов отделены от аппаратной стороны исполнения, в вероятностном программировании мы сможем провести еще одну важнейшую границу, которая пока отсутствует в современных самообучающихся системах.
Моделирование и выведение/обучение довольно давно считаются концептуально разными видами работы, но на практике они тесно связаны. Я имею в виду, что модели, применяемые при решении конкретной проблемы, жестко ограничены необходимостью создания репрезентативных схем выведения информации. А на подготовку и реализацию таких схем уходит масса времени. К тому же для этого требуются очень специфические навыки и опыт. Если же внести в модель даже самые незначительные изменения, то, возможно, потребуется полностью переработать подход к выведению информации. Это не место для импровизаций.
Если вероятностное программирование сможет как следует развиться, то два этих вида деятельности, наконец-то, будут однозначно разделены прочным «барьером абстрагирования»: разработчик пишет программу, которую хочет создать, а компилятор и среда времени исполнения обустраивают механизм выведения (с учетом известных проблем). Таким образом, специалист по вероятностному программированию сможет реализовывать в коде и значительно более эффективно использовать свои знания из конкретной предметной области. В итоге имеем гораздо более взвешенную аргументацию и более качественные решения, принимаемые в контексте всех имеющихся данных.
Вероятностное программирование обеспечивает более универсальные, абстрактные суждения , так как в программах, написанных в соответствии с данной методологией, можно будет непосредственно «зашивать» несколько уровней суждения, а потом осуществлять выведение, опираясь на все эти уровни одновременно. Имеющиеся системы обучения в основном сводятся к изучению тех параметров модели, которые обеспечивают наиболее качественное объяснение данных. Но такие системы не способны «судить» о том, насколько репрезентативным является весь класс моделей, к которому относится данная абстракция.
С другой стороны, вероятностные программы способны и к «сквозным» суждениям, затрагивающим сразу все уровни. Так, программа может изучить параметры модели, либо выбрать наилучшие варианты моделей из конкретного класса, либо, наконец, выбрать один из двух совершенно разных классов моделей. Конечно, нет универсального средства для моделирования случайных отклонений, а также для расчета последствий применения неподходящих моделей. Но уже имеющиеся возможности, несомненно, позволяют значительно более качественно объяснять информацию: не только с количественной, но и с качественной точки зрения.
Наконец, хотелось бы перечислить ряд ключевых проблем, которые можно будет решить при помощи вероятностного программирования.
Создавать компиляторы и среды времени исполнения, которые автоматически генерируют качественные схемы выведения информации для произвольных вероятностных программ, очень сложно.
Если все вышесказанное создает у вас впечатление слишком радужной картины, мало похожей на правду, то это потому, что такую стройную систему еще лишь предстоит создать. У исследователей впереди еще непочатый край работы. Самые успешные из современных вероятностных систем (BUGS, infer.net, factor.ie) при работе целенаправленно ограничивают выразительный потенциал языка, искусственно упрощая проблему выведения.
Все абстракции протекают, и те из них, что расположены между моделированием (написанием вероятностной программы) и выведением, — не исключение . Таким образом, некоторые вероятностные программы выполняют выведение значительно быстрее других, а причины достижения этой скорости могут быть достаточно сложны для понимания. В традиционных высокоуровневых языках программирования подобные проблемы обычно решаются методом профилирования и оптимизации, и в вероятностных системах еще предстоит разработать аналогичный инструментарий, чтобы программист мог изучать и решать проблемы, возникающие в области производительности.
Наконец, вероятностное программирование требует и иной комбинации навыков у разработчика и активного применения машинного обучения или статистических заключений . Думаю, нам останется лишь постыдиться, если такие системы разовьются, но все равно останутся маргинальными и будут применяться лишь небольшими кастами программистов. Такая незавидная судьба сегодня постигла, например, языки Lispи Haskell.
Эти проблемы, конечно же, весьма интересны. Я возлагаю большие надежды на вероятностное программирование и то, чего можно достичь в этой области в ближайшие годы. Подобными проектами уже занимаются некоторые умнейшие люди, с которыми мне когда-либо доводилось общаться, и, я думаю, что прогресс не за горами.
Заинтересовались подробностями? Почитайте о BUGS — это язык для вероятностного программирования, разработанный статистиками уже более 20 лет назад. Конечно, у него есть определенные недостатки, связанные с малой языковой выразительностью и размером множества данных (dataset), но для знакомства с темой этот язык подходит отлично. Кроме того, можете почитать ознакомительный пост Роба Зинкова, где приведены примеры некоторых моделей. Church — один из наиболее многообещающих языков вероятностного программирования. Почитайте руководства по языку , но в любом случае в нем еще предстоит доработать и механизм выведения, и весь инструментарий. Поэтому в краткосрочной перспективе вам может больше понравиться factorie , особенно если вы любитель Scala, либо MicrosoftResearch’sinfer.net , связанный с C# и F#. Отличный обзор вероятностного программирования по состоянию на конец 2012 года дают материалы последнего академического семинара , посвященного этой проблеме.
Примечание: сам я не участвую ни в текущих исследованиях вероятностного программирования, ни в программе DARPA; я просто очень заинтересованный наблюдатель.
Уже более полутора лет назад прошла новость о том, что «DARPA намерено совершить революцию в машинном обучении» . Конечно, DARPA всего лишь выделила деньги на исследовательскую программу, связанную с вероятностным программированием. Само же вероятностное программирование существует и развивается без DARPA достаточно давно, причем исследования ведутся, как в ведущих университетах, таких как MIT, так и в крупных корпорациях, таких как Microsoft. И вовсе не зря DARPA, Microsoft, MIT и т.д. обращают пристальное внимание на эту область, ведь она по-настоящему перспективна для машинного обучения, а, может, и для искусственного интеллекта в целом. Говорят, что вероятностное программирование для машинного обучения будет играть ту же роль, что и высокоуровневые языки для обычного программирования. Мы бы привели другую параллель – с ролью Пролога, которую он сыграл для старого доброго ИИ. Вот только в Рунете по данной теме до сих пор можно найти лишь единичные ссылки, и то в основном содержащие лишь описания общих принципов. Возможно, это связано с тем, что потенциал вероятностного программирования еще только начал раскрываться и оно не стало основным трендом. Однако на что же способны или будут способны вероятностные языки?
Можно выделить два основных класса вероятностных языков программирования – это языки, допускающие задание генеративных моделей только в форме Байесовских сетей (или других графических вероятностных моделей), или Тьюринг-полные языки.
Типичным представителем первых является Infer.NET, разрабатываемый в Microsoft. В нем благодаря использованию в качестве генеративных моделей Байесовких сетей оказывается возможным применять известные для них эффективные методы вывода. Естественно, использование хорошо известного класса моделей с известными методами вывода не приводит к возможности решения каких-то принципиально новых задач (и даже такие генеративные модели, как сети глубокого обучения на основе ограниченных машинах Больцмана оказываются не представимы в таких языках), но дает вполне практичный инструмент. Как говорят разработчики, с использованием этого инструмента можно за пару часов реализовать нетривиальную вероятностную модель, такую как полная Байесовская версия анализа главных компонент, которая будет занимать всего пару десятков строк кода и для которой отдельная реализация эффективной процедуры вывода на обычном языке потребовала бы заметно большего объема знаний и нескольких недель работы. Таким образом, за счет вероятностного программирования использование графических моделей становится гораздо более простым и доступным.
Гораздо большим потенциалом, однако, обладают Тьюринг-полные вероятностные языки. Они позволяют выйти за рамки того класса задач, которые существующие методы машинного обучения уже умеют решать. Естественно, в таких языках возникает проблема эффективности вывода, которая пока далека от решения, что приводит к плохой масштабируемости на задачи реального мира. Однако это направление активно развивается, и существует ряд работ, показывающих как в вероятностных языках общего назначения достичь эффективного вывода для интересных практических задач. Можно надеяться, что в ближайшем будущем эти решения станут доступными для использования в конкретных языках. Кроме того, Тьюринг-полные вероятностные языки уже сейчас оказываются весьма полезными в исследованиях, связанных с когнитивным моделированием и общим искусственным интеллектом. По этим причинам мы и рассмотрим основные принципы вероятностного программирования именно на примере Тьюринг-полных языков, из которых мы выбрали Чёрч (Church), являющийся расширением языка Лисп (конкретнее, его диалекта – Scheme). Удобство этого языка (по крайней мере, в целях начального знакомства с ним) заключается в существовании для него web-реализации (web-church), с которой можно экспериментировать без установки дополнительного программного обеспечения.
Итак, к делу
Программа на вероятностном языке может, на первый взгляд, ничем не отличаться от программы на обычном языке. Именно так сделано в Чёрче. Как и в обычном Лиспе, в этом языке могут быть определены переменные, функции, выполнены детерминированные вычисления. Например, следующая программа задает функцию от одного аргумента, вычисляющую факториал по рекурсивной формуле n!=n*(n–1)!, и вызывает эту функцию для n=10
(define (f n) (if (= n 0 ) 1 (* n (f (– n 1 ) ) ) ) ) (f 10 )Также в этом языке могут быть обращения к (псевдо)случайным функциям. Например, при выполнении вызова (flip 0.3) с вероятностью 0.3 будет возвращено значение #t, а с вероятностью 0.7 – #f. Такая функция элементарно реализуется и в Лиспе как
(define (flip p) (< (random ) p) )
Чёрч, как и другие вероятностные языки, включает много встроенных функций, которые возвращают случайные значения в соответствии с тем или иным распределением. Например, (gaussian x0 s) возвращает вещественную случайную величину, распределенную по гауссиане с заданными параметрами. В качестве других реализованных распределений вероятностей обычно присутствуют равномерное, мультиномиальное, Дирихле, бета, гамма. Все эти распределения не так сложно реализовать вручную в обычном языке, и здесь пока нет принципиального отличия между Чёрчем и Лиспом.
Однако помимо обычной семантики программа на Чёрче обладает вероятностной семантикой, в рамках которой полагается, что программа, содержащая вызовы случайных функций, не просто при своем запуске порождает какие-то конкретные значения случайных величин, но задает распределение вероятностей над ними. Так, (gaussian x0 s) – это не просто функция, возвращающая некоторое конкретное значение случайной величины, распределенной по гауссиане, но именно само Гауссово распределение.
Но как получать эти распределения вероятностей, задаваемые программой? Представим, например, программу
(if (flip 0.4 ) (flip 0.1 ) (flip 0.6 ) )То есть с вероятностью 0.4 значение этого выражения – это P(#t)=0.1 и P(#f)=0.9, а с вероятностью 0.6 – P(#t)=0.6 и P(#f)=0.4. Откуда возьмется итоговое распределение, задаваемое этим выражением: P(#t)=0.4 и P(#f)=0.6? Эта вероятностная семантика зачастую реализуется через процесс сэмплирования: мы можем просто много раз запустить программу и построить выборку результатов ее выполнения. Такую процедуру, конечно, также несложно реализовать на обычном языке (и, действительно, еще Симула-67 таким способом регулярно использовалась для моделирования стохастических процессов).
Однако современные вероятностные языки идут дальше и добавляют в процесс сэмплирования условие, накладываемое на результаты выполнения программы. Эта идея ведет к простейшему сэмплированию с отказами, которая в Чёрче реализуется функцией rejection-query. Эта функция на вход принимает вероятностную программу (как совокупность define), предпоследнее выражение в которой вычисляет возвращаемое значение, а последнее выражение – это условие (предикат), который в процессе выполнения должен оказаться истинным. Рассмотрим программу
(rejection-query (define A (flip 0.4 ) ) (define B (flip 0.6 ) ) B (or A B) )rejection-query выполняет поданную ей программу до тех пор, пока не будет выполнено последнее условие – здесь (or A B) – и возвращает (один раз) значение предпоследнего выражения – здесь B. Чтобы получить выборку значений, можно воспользоваться функцией repeat. Также Чёрч имеет встроенные функции для построения гистограмм. Рассмотрим немного расширенную программу:
(define (get-sample ) (rejection-query (define A (flip 0.4 ) ) (define B (flip 0.6 ) ) B (or A B) ) ) (hist (repeat 1000 get-sample) )При запуске мы получим следующий результат: #f - 21%, #t - 79% (цифры от запуска к запуску могут немного меняться). Этот результат означает, что значение B равно #t с вероятностью чуть меньше 0.8. Откуда взялась эта вероятность, если в программе B – это бинарная случайная величина, для которой P(#t)=0.6? Очевидно, дело в наложении условия: (or A B). В процессе сэмплирования мы принимаем только такие значения B, что верно или A, или само B. Фактически, мы считаем апостериорную вероятность P(B|A+B). Можно было бы воспользоваться правилом Байеса для того, чтобы вычислить эту вероятность вручную:
P(B|A+B) = P(A+B|B)P(B)/P(A+B) = =(P(A|B)+P(B|B)–P(A|B)P(B|B))P(B)/(P(A)+P(B)–P(A)P(B))= =(P(A)+1–P(A))P(B)/(P(A)+P(B)–P(A)P(B))=0.6/(0.4+0.6–0.4*0.6)=0.789.
Однако уже для такой элементарной программы ручное применение правила Байеса требует некоторого времени, а для нетривиальных программ аналитически вычислить значения может и вовсе не получиться.
Итак, сэмплирование позволяет нам вычислять апостериорные вероятности интересующих нас случайных величин при наложении тех или иных условий. Оно заменяет правило Байеса, широко используемое в машинном обучении для выбора моделей или выполнения предсказаний. При этом запись программы на вероятностном языке для многих людей может оказаться гораздо понятнее, чем применение правила Байеса. Конечно, само режекторное сэмплирование весьма просто можно реализовать на обычном языке программирования, но вероятностные языки этим не ограничиваются.
В Чёрче, в частности, реализована другая функция для сэмплирования – enumeration-query. Запустим программу
На выходе мы получим: ((#t #f) (0.7894736842105263 0.2105263157894737)). Здесь выведены точные значения (конечно, со скидкой на конечную разрядную сетку) вероятностей P(B|A+B). enumeration-query уже не просто запускает много раз программу, но анализирует пути ее выполнения и перебирает все возможные значения случайных переменных с учетом их вероятностей. Конечно, такое «сэмплирование» будет работать, только когда множество возможных комбинаций значений случайных переменных не слишком велико.
Есть в Чёрче и более продвинутая замена режекторному сэмплированию на основе MCMC (Monte Carlo Markov Chains), а именно Metropolis Hastings алгоритм, откуда и название у процедуры – mh-query. Эта процедура запроса сразу формирует заданное число сэмплов (а также получает на вход один дополнительный параметр – лаг). Эта процедура также нетривиальна в реализации, так что использование готового вероятностного языка (а не собственная реализация простых процедур сэмплирования на обычном языке) приобретает смысл.
Однако главное, что дает вероятностное программирование, – это стиль мышления.
От азов к применению
Разные разработчики находят разные применения вероятностному программированию. Многие применяют его непосредственно для решения задач машинного обучения. Авторы же языка Чёрч, Noah D. Goodman and Joshua B. Tenenbaum, в своей web-книге «Probabilistic Models of Cognition» показывают применение вероятностного программирования для когнитивного моделирования. Также известно, как решение задач планирования удобно представлять в терминах вывода в вероятностных языках. Оно также оказывается применимым для представления знаний и вывода над ними, а также для задач машинного восприятия (в том числе, распознавания изображений). Все эти приложения пока более или менее разрозненные, но наличие общего фреймворка для всех них свидетельствует о том, что вероятностное программирование может стать «теорией великого объединения» для ИИ. Посмотрим на простейшие примеры возможного использования.
Одним из наиболее классических примеров применения экспертных систем является медицинская диагностика. В частности, система MYCIN была построена на системе правил вида:
- THE SITE OF THE CULTURE IS BLOOD
- THE GRAM OF THE ORGANISM I S NEG
- THE MORPHOLOGY OF THE ORGANISM IS ROD
- THE BURN OF THE PATIENT IS SERIOUS
Then there is weakly suggestive evidence (0.4) that
- THE IDENTITY OF THE ORGANISM IS PSEUDOMONAS
Очевидно, правила такого вида хорошо описываются на языке типа Чёрч. При этом нет необходимости еще и реализовывать процедуру вывода – достаточно просто записать систему правил. Приведем пример из упомянутой книги «Probabilistic Models of Cognition»:
(define samples (mh-query 1000 100 (define lung-cancer (flip 0.01 ) ) (define TB (flip 0.005 ) ) (define cold (flip 0.2 ) ) (define stomach-flu (flip 0.1 ) ) (define other (flip 0.1 ) ) (define cough (or (and cold (flip 0.5 ) ) (and lung-cancer (flip 0.3 ) ) (and TB (flip 0.7 ) ) (and other (flip 0.01 ) ) ) ) (define fever (or (and cold (flip 0.3 ) ) (and stomach-flu (flip 0.5 ) ) (and TB (flip 0.2 ) ) (and other (flip 0.01 ) ) ) ) (define chest-pain (or (and lung-cancer (flip 0.4 ) ) (and TB (flip 0.5 ) ) (and other( flip 0.01 ) ) ) ) (define shortness-of-breath (or (and lung-cancer (flip 0.4 ) ) (and TB (flip 0.5 ) ) (and other (flip 0.01 ) ) ) ) (list lung-cancer TB) (and cough fever chest-pain shortness-of-breath) ) ) (hist samples "Joint inferences for lung cancer and TB" )В этой программе определяются априорные вероятности появления у больного рака легких, туберкулеза, простуды и т.д. Далее определяются вероятности наблюдения кашля, жара, боли в груди и стесненного дыхания при тех или иных заболеваниях. Возвращаемая величина – это пара булевых значений, есть ли у пациента рак и/или туберкулез. И, наконец, условие – это совокупность наблюдаемых симптомов (то есть сэмплирование производится при условии, что значение всех переменных – cough fever chest-pain shortness-of-breath – #t).
Результат выполнения программы будет иметь следующий вид: (#f #f) - 4%, (#f #t) - 58%, (#t #f) - 37%, (#t #t) - 1%.
Несложно сделать, чтобы samples была функцией, в которую подается перечень симптомов, который далее в mh-query используется для сэмплирования, что даст возможность ставить диагнозы разным пациентам. Конечно, этот пример сильно упрощенный, но видно, что в стиле вероятностного программирования вполне можно представлять знания и делать вывод над ними.
Естественно, можно решать и задачи машинного обучения. Их отличие будет лишь в том, что неизвестными величинами будут параметры самой модели, а в качестве условия для сэмплирования будет выступать генерация этой моделью обучающей выборки. К примеру, в представленной выше программе мы бы числа в строках вида (define lung-cancer (flip 0.01)) могли бы заменить на переменные, которые сами бы задавались как случайные, например (define p-lung-cancer (uniform 0 1)), а далее для каждого пациента из обучающей выборки значение lung-cancer уже определялось бы с вероятностью p-lung-cancer.
Рассмотрим эту возможность на простом примере оценивания параметров многочлена по набору точек. В следующей программе функция calc-poly вычисляет значение многочлена с параметрами ws в точке x. Функция generate применяет calc-poly к каждому значению из заданного списка xs и возвращает список соответствующих ординат. Процедура noisy-equals? «приближенно» сравнивает два заданных значения (если эти значения равны, то функция возвращает #t с вероятностью 1; если же они не равны, то чем больше они отличаются, тем с меньшей вероятностью она вернет #t).
(define (calc-poly x ws) (if (null ? ws) 0 (+ (car ws) (* x (calc-poly x (cdr ws) ) ) ) ) ) (define (generate xs ws) (map (lambda (x ) (calc-poly x ws) ) xs) ) (define (noisy-equals ? x y) (flip (exp (* -3 (expt (- x y) 2 ) ) ) ) ) (define (samples xs ys) (mh-query 1 100 (define n-coef 4 ) (define ws (repeat n-coef (lambda () (gaussian 0 3 ) ) ) ) ws (all (map noisy-equals? (generate xs ws) ys) ) ) ) (samples "(0 1 2 3 4 ) "()Внутри вызова mh-query параметр n-coef определяет число коэффициентов в многочлене (то есть его степень плюс один); ws – это список, состоящий из случайных величин, сгенерированных в соответствии с нормальным распределением. Возвращаемое значение – список параметров многочлена. Условие для сэмплирования – «приближенное» равенство всех заданных значений ys всем ординатам, порожденным многочленом при данных ws. Здесь мы запрашиваем всего одну реализацию, которая проходит по условию (поскольку строить гистограмму для вектора параметров не очень удобно). Результатом этого запроса может быть, к примеру, список (2.69 1.36 0.53 -0.10), задающий многочлен 2.69+1.36x+0.53x^2–0.10x^3.
Вообще, вывод на моделях с вещественными параметрами – не самая сильная сторона языка Чёрч (но не стоит это считать глобальным недостатком вероятностного программирования вообще). Тем не менее, на этом примере mh-query кое-как работает. Чтобы в этом убедиться, вместо определения значений параметров в запросе можно попросить возвращать предсказание в некоторой точке. Перепишем последний фрагмент кода так:
(define (samples xs ys) (mh-query 100 100 (define n-coef 4 ) (define ws (repeat n-coef (lambda () (gaussian 0 3 ) ) ) ) (calc-poly 5 ws) (all (map noisy-equals? (generate xs ws) ys) ) ) ) (hist (samples "(0 1 2 3 4 ) "(0.01 1.95 6.03 12.01 20.00 ) ) )То есть мы запрашиваем наиболее вероятное (при имеющихся данных) значение в точке x=5. При разных запусках максимум гистограммы, к сожалению, будет приходиться на несколько различающиеся значения (метод MCMC, теоретически, гарантирует схождение к истинному распределению, но лишь в пределе), но обычно эти значения будут достаточно вразумительными. Стоит заметить, что здесь мы «бесплатно» (заменой одной строчки) получили полное байесовское предсказание: вместо выбора лучшей модели и предсказания лишь по ней, мы получили апостериорное распределение значений в точке x=5, усредненное сразу по множеству моделей с учетом их собственных вероятностей.
Но и это еще не все. Опять же, заменой одной строчки – (define n-coef 4) -> (define n-coef (random-integer 5)) мы можем сделать автоматический выбор между моделями с разным числом параметров. Причем сэмплирование величины n-coef показывает (хотя и не очень стабильно), что наиболее вероятным значением является n-coef=3 (то есть парабола, которая и заложена в заданный набор точек). При такой модификации более стабильным становится и предсказание. Иными словами, не возникает и эффекта переобучения! Почему же не выбираются многочлены более высокой степени, ведь они могут точнее проходить к заданным точкам? Дело в том, что при сэмплировании «угадать» подходящие значения параметров многочлена меньшей степени проще, чем многочлена более высокой степени, поэтому вероятность породить такие параметры, которые пройдут проверку, для многочлена второй степени выше, чем для третьей. В то же время, многочлен первой степени будет давать большие отклонения, для которых вероятность срабатывания noisy-equals? будет сильно понижаться.
Посмотрим еще на одно применение, которое в рамках вероятностного программирования может показаться неожиданным. Это решение «дедуктивных» задач. Возьмем приведенную в начале функцию вычисления факториала, но вместо вызова ее с фиксированным значением будем считать, что аргумент – случайная переменная, но на само значение факториала наложено ограничение:
(define (f n) (if (= n 0 ) 1 (* n (f (- n 1 ) ) ) ) ) (enumeration-query (define n (random-integer 20 ) ) n (equal ? (f n) 120 ) )В качестве ответа мы увидим n=5 с вероятностью 1. Если же мы вместо 120 зададим 100, то программа не зациклится (в отличие от случая использования rejection-query или mh-query, что можно считать их недостатком), а просто вернет пустое множество. Можно поставить в качестве условия и не строгое равенство, а какое-то другое ограничение.
Таким же образом можно решать и более сложные задачи. Допустим, мы хотим решить задачу о сумме подмножеств: в ней надо из заданного множества чисел найти такое подмножество, сумма в котором равна заданному числу (обычно в качестве этого числа берется 0 и требуется, чтобы подмножество было не пустым; но чтобы избавиться от проверки на нетривиальность решения, мы возьмем ненулевую сумму). Казалось бы, причем тут вероятностное программирование? Но случайные величины – это просто неизвестные величины (для которых заданы априорные вероятности). В любых задачах нам нужно найти что-то неизвестное, в том числе и в задаче о сумме подмножеств. Посмотрим на следующую элементарную программу (ее можно было бы даже еще упростить, записав summ через fold).
(define (solution xs v) (rejection-query (define ws (repeat (length xs) flip) ) (define (summ xs ws) (if (null ? xs) 0 (+ (if (car ws) (car xs) 0 ) (summ (cdr xs) (cdr ws) ) ) ) ) ws (equal ? (summ xs ws) v) ) ) (solution "(-1 3 7 5 -9 -1 ) 1 )Здесь ws – список случайных булевых значений. Процедура summ вычисляет сумму элементов списка xs, для которых соответствующие элементы списка ws истинны. Далее запрашивается значения ws, для которых выполняется условие равенства полученной суммы заданному числу v. Запустив эту программу, можно получить такой результат: (#f #t #t #f #t #f), который, конечно, является правильным (так как 3+7-9=1).
Естественно, Чёрч не делает чуда и при повышении размерности этой задачи он с ней не справится. Однако не может не удивлять то, что столь разные задачи ИИ могут быть хотя бы поставлены (и отчасти решены) с использованием одного и того же языка. Ну, а проблема эффективного вывода как была, так и остается. В вероятностных языках она хотя бы выделяется в чистом виде.
Эта публикация является первой частью краткого вступления с иллюстрациями в вероятностное программирование , которое является одним из современных прикладных направлений машинного обучения и искусственного интеллекта. Во время написания этой публикации я с радостью обнаружил, что на Хабрахабре совсем недавно уже была , хотя, к сожалению, в русскоговоряющем Интернете пока мало материалов на эту тему.Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.
Вероятностное программирование я люблю определять как компактный , композиционный способ представления порождающих вероятностных моделей и проведения статистического вывода в них с учетом данных с помощью обобщенных алгоритмов. Хотя вероятностное программирование не вносит много фундаментального нового в теорию машинного обучения, этот подход привлекает своей простотой: «вероятностные порождающие модели в массы!»
«Обычное» программирование
Для знакомства с вероятностным программирование давайте сначала поговорим об «обычном» программировании. В «обычном» программировании основой является алгоритм, обычно детерминированный, который позволяет нам из входных данных получить выходные по четко установленным правилам.Например, если у нас есть мальчик Вася, и мы знаем где он находится, куда он бросает мяч и каковы внешние условия (например, сила ветра), мы узнаем, какое окно он, к сожалению, разобьет в здании школы. Для этого достаточно симулировать простые законы школьной физики, которые легко можно записать в виде алгоритма.
А теперь вероятностное программирование
Однако часто мы знаем только результат, исход, и мы заинтересованы в том, чтобы узнать то, какие неизвестные значения привели именно к этому результату? Чтобы ответить на этот вопрос с помощью теории математического моделирования создается вероятностная модель, часть параметров которой не определены точно.Например, в случае с мальчиком Васей, зная то, какое окно он разбил, и имея априорные знания о том, около какого окна он и его друзья обычно играют в футбол, и зная прогноз погоды на этот день, мы хотим узнать апостериорные распределение местоположения мальчика Васи: откуда же он бросал мяч?
Итак, зная выходные данные, мы заинтересованы в том, чтобы узнать наиболее вероятные значения скрытых, неизвестных параметров.
В рамках машинного обучения рассматриваются в том числе порождающие вероятностные модели. В рамках порождающих вероятностных моделей модель описывается как алгоритм, но вместо точных однозначных значений скрытых параметров и некоторых входных параметров мы используем вероятностные распределениях на них.
Существует более 15 языков вероятностного программирования, перечень с кратким описанием каждого из них можно найти . В данной публикации приведен пример кода на вероятностных языках Venture /Anglican , который имеют очень схожий синтаксис и которые берут свое начало от вероятностного языка Church . Church в свою очередь основан на языке «обычного» программирования Lisp и Scheme. Заинтересованному читателю крайне рекомендуется ознакомиться с книгой , являющейся одним из лучших способов начать знакомство с языком «обычного» программирования Scheme.
Пример Байесовской линейной регрессии
Рассмотрим задание простой вероятностной модели Байесовской линейной регрессии на языке вероятностного программирования Venture/Anglican в виде вероятностной программы:01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
Скрытые искомые параметры — значения коэффициентов t1
и t2
линейной функции x = t1 + t2 * time
. У нас есть априорные предположения о данных коэффициентах, а именно мы предполагаем, что они распределены по закону нормального распределения Normal(0, 1)
со средним 0 и стандартным отклонением 1. Таким образом, мы определили в первых двух строках вероятностной программы априорную вероятность на скрытые переменные, P(T)
. Инструкцию
можно рассматривать как определение случайной величины с именем name
, принимающей значение вычисляемого выражение (программного кода) expression
, которое содержит в себе неопределенность.
Вероятностные языки программирования (имеются в виду конкретно Church, Venture, Anglican), как и Lisp/Scheme, являются функциональными языками программирования, и используют польскую нотацию при записи выражений для вычисления. Это означает, что в выражении вызова функции сначала располагается оператор, а уже только потом аргументы: (+ 1 2) , и вызов функции обрамляется круглыми скобками. На других языках программирования, таких как C++ или Python, это будет эквивалентно коду 1 + 2 .
В вероятностных языках программирования выражение вызова функции принято разделять на три разных вида:
- Вызов детерминированных процедур (primitive-procedure arg1… argN) , которые при одних и тех же аргументах всегда возвращают одно и то же значение. К таким процедурам, например, относятся арифметические операции.
- Вызов вероятностных (стохастических) процедур (stochastic-procedure arg1… argN) , которые при каждом вызове генерируют случайным образом элемент из соответствующего распределения. Такой вызов определяет новую случайную величину . Например, вызов вероятностной процедуры (normal 1 10) определяет случайную величину, распределенную по закону нормального распределения Normal(1, sqrt(10)) , и результатом выполнения каждый раз будет какое-то вещественное число.
- Вызов составных процедур (compound-procedure arg1… argN) , где compound-procedure — введенная пользователем процедура с помощью специального выражения lambda : (lambda (arg1… argN) body) , где body — тело процедуры, состоящее из выражений. В общем случае составная процедура является стохастической (недетерминированной) составной процедурой, так как ее тело может содержать вызовы вероятностных процедур.
Перед вводом непосредственно самих наблюдений с помощью выражения мы определяем общий закон для наблюдаемых переменных xi в рамках нашей модели, а именно мы предполагаем, что данные наблюдаемые случайные величины при заданных t1 , t2 и заданном уровне шума noise распределены по закону нормального распределения Normal(t1 + t2 * time, sqrt(noise)) со средним t1 + t2 * time и стандартным отклонением noise . Данная условная вероятность определена на строках 3 и 4 данной вероятностной программы. noisy_x определена как функция, принимающая параметр time и возвращающая случайное значение, определенное с помощью вычисления выражение и обусловленное значениями случайных величин t1 и t2 и переменной noise . Отметим, что выражение (normal (+ t1 (* t2 time)) noise) содержит в себе неопределенность, поэтому каждый раз при его вычислении мы будем получать в общем случае разное значение.
На строках 5—7 мы непосредственно вводим известные значения x1 = 10.3 , x2 = 11.1 , x3 = 11.9 . Инструкция вида фиксирует наблюдение о том, что случайная величина, принимающая значение согласно выполнению выражения expression , приняла значение value .
Повторим на данном этапе всё, что мы сделали. На строках 1—4 с помощью инструкций вида мы задали непосредственно саму вероятностную модель: P(T) и P(X | T) . На строках 5—7 мы непосредственно задали известные нам значения наблюдаемых случайных величин X с помощью инструкций вида .
На строках 8—9 мы запрашиваем у системы вероятностного программирования апостериорное распределение P(T | X) скрытых случайных величин t1 и t2 . Как уже было сказано, при большом объеме данных и достаточно сложных моделях получить точное аналитическое представление невозможно, поэтому инструкции вида генерируют выборку значений случайных величин из апостериорного распределения P(T | X) или его приближения. Инструкция вида в общем случае генерирует один элемент выборки из значений случайной величины, принимающей значение согласно выполнению выражения expression . Если перед инструкциями вида расположены инструкции вида , то выборка будет из апостериорного распределения (говоря точнее, конечно, из приближения апостериорного распределения), обусловленного перечисленными ранее введенными наблюдениями.
Отметим, что в завершении мы можем также предсказать значение функции x(time) в другой точке, например, при time = 4.0 . Под предсказанием в данном случае понимается генерация выборки из апостериорного распределения новой случайной величины при значениях скрытых случайных величин t1 , t2 и параметре time = 4.0 .
Для генерации выборки из апостериорного распределения P(T | X) в языке программирования Venture в качестве основного используется алгоритм Метрополиса-Гастингса, который относится к методам Монте-Карло по схеме Марковских цепей. Под обобщенным выводом в данном случае понимается то, что алгоритм может быть применен к любым вероятностным программам, написанным на данном вероятностном языке программирования.
В видео, прикрепленном ниже, можно посмотреть на происходящий статистический вывод в данной модели.
В самом начале у нас нет данных, поэтому мы видим априорное распределение прямых. Добавляя точку за точкой (таким образом, элементы данных), мы видим элементы выборки из апостериорного распределения.
На этом мы закончим первую часть данного вступления в вероятностное программирование.
Материалы
Ниже я приведу рекомендуемые ссылки для тех, кто хочет прямо сейчас узнать больше о вероятностном программировании:Можно выделить два основных класса вероятностных языков программирования – это языки, допускающие задание генеративных моделей только в форме Байесовских сетей (или других графических вероятностных моделей), или Тьюринг-полные языки.
Типичным представителем первых является Infer.NET, разрабатываемый в Microsoft. В нем благодаря использованию в качестве генеративных моделей Байесовких сетей оказывается возможным применять известные для них эффективные методы вывода. Естественно, использование хорошо известного класса моделей с известными методами вывода не приводит к возможности решения каких-то принципиально новых задач (и даже такие генеративные модели, как сети глубокого обучения на основе ограниченных машинах Больцмана оказываются не представимы в таких языках), но дает вполне практичный инструмент. Как говорят разработчики, с использованием этого инструмента можно за пару часов реализовать нетривиальную вероятностную модель, такую как полная Байесовская версия анализа главных компонент, которая будет занимать всего пару десятков строк кода и для которой отдельная реализация эффективной процедуры вывода на обычном языке потребовала бы заметно большего объема знаний и нескольких недель работы. Таким образом, за счет вероятностного программирования использование графических моделей становится гораздо более простым и доступным.
Гораздо большим потенциалом, однако, обладают Тьюринг-полные вероятностные языки. Они позволяют выйти за рамки того класса задач, которые существующие методы машинного обучения уже умеют решать. Естественно, в таких языках возникает проблема эффективности вывода, которая пока далека от решения, что приводит к плохой масштабируемости на задачи реального мира. Однако это направление активно развивается, и существует ряд работ, показывающих как в вероятностных языках общего назначения достичь эффективного вывода для интересных практических задач. Можно надеяться, что в ближайшем будущем эти решения станут доступными для использования в конкретных языках. Кроме того, Тьюринг-полные вероятностные языки уже сейчас оказываются весьма полезными в исследованиях, связанных с когнитивным моделированием и общим искусственным интеллектом. По этим причинам мы и рассмотрим основные принципы вероятностного программирования именно на примере Тьюринг-полных языков, из которых мы выбрали Чёрч (Church), являющийся расширением языка Лисп (конкретнее, его диалекта – Scheme). Удобство этого языка (по крайней мере, в целях начального знакомства с ним) заключается в существовании для него web-реализации (web-church), с которой можно экспериментировать без установки дополнительного программного обеспечения.
Итак, к делу
Программа на вероятностном языке может, на первый взгляд, ничем не отличаться от программы на обычном языке. Именно так сделано в Чёрче. Как и в обычном Лиспе, в этом языке могут быть определены переменные, функции, выполнены детерминированные вычисления. Например, следующая программа задает функцию от одного аргумента, вычисляющую факториал по рекурсивной формуле n!=n*(n–1)!, и вызывает эту функцию для n=10
(define (f n)
(if (= n 0) 1 (* n (f (– n 1)))))
(f 10)
Также в этом языке могут быть обращения к (псевдо)случайным функциям. Например, при выполнении вызова (flip 0.3) с вероятностью 0.3 будет возвращено значение #t, а с вероятностью 0.7 – #f. Такая функция элементарно реализуется и в Лиспе как
(define (flip p) (< (random) p))
Чёрч, как и другие вероятностные языки, включает много встроенных функций, которые возвращают случайные значения в соответствии с тем или иным распределением. Например, (gaussian x0 s) возвращает вещественную случайную величину, распределенную по гауссиане с заданными параметрами. В качестве других реализованных распределений вероятностей обычно присутствуют равномерное, мультиномиальное, Дирихле, бета, гамма. Все эти распределения не так сложно реализовать вручную в обычном языке, и здесь пока нет принципиального отличия между Чёрчем и Лиспом.
Однако помимо обычной семантики программа на Чёрче обладает вероятностной семантикой, в рамках которой полагается, что программа, содержащая вызовы случайных функций, не просто при своем запуске порождает какие-то конкретные значения случайных величин, но задает распределение вероятностей над ними. Так, (gaussian x0 s) – это не просто функция, возвращающая некоторое конкретное значение случайной величины, распределенной по гауссиане, но именно само Гауссово распределение.
Но как получать эти распределения вероятностей, задаваемые программой? Представим, например, программу
(if (flip 0.4) (flip 0.1) (flip 0.6))
То есть с вероятностью 0.4 значение этого выражения – это P(#t)=0.1 и P(#f)=0.9, а с вероятностью 0.6 – P(#t)=0.6 и P(#f)=0.4. Откуда возьмется итоговое распределение, задаваемое этим выражением: P(#t)=0.4 и P(#f)=0.6? Эта вероятностная семантика зачастую реализуется через процесс сэмплирования: мы можем просто много раз запустить программу и построить выборку результатов ее выполнения. Такую процедуру, конечно, также несложно реализовать на обычном языке (и, действительно, еще Симула-67 таким способом регулярно использовалась для моделирования стохастических процессов).
Однако современные вероятностные языки идут дальше и добавляют в процесс сэмплирования условие, накладываемое на результаты выполнения программы. Эта идея ведет к простейшему сэмплированию с отказами, которая в Чёрче реализуется функцией rejection-query. Эта функция на вход принимает вероятностную программу (как совокупность define), предпоследнее выражение в которой вычисляет возвращаемое значение, а последнее выражение – это условие (предикат), который в процессе выполнения должен оказаться истинным. Рассмотрим программу
(rejection-query
(define A (flip 0.4))
(define B (flip 0.6))
B
(or A B))
rejection-query выполняет поданную ей программу до тех пор, пока не будет выполнено последнее условие – здесь (or A B) – и возвращает (один раз) значение предпоследнего выражения – здесь B. Чтобы получить выборку значений, можно воспользоваться функцией repeat. Также Чёрч имеет встроенные функции для построения гистограмм. Рассмотрим немного расширенную программу:
(define (get-sample) (rejection-query
(define A (flip 0.4))
(define B (flip 0.6))
B
(or A B)))
(hist (repeat 1000 get-sample))
При запуске мы получим следующий результат: #f — 21%, #t — 79% (цифры от запуска к запуску могут немного меняться). Этот результат означает, что значение B равно #t с вероятностью чуть меньше 0.8. Откуда взялась эта вероятность, если в программе B – это бинарная случайная величина, для которой P(#t)=0.6? Очевидно, дело в наложении условия: (or A B). В процессе сэмплирования мы принимаем только такие значения B, что верно или A, или само B. Фактически, мы считаем апостериорную вероятность P(B|A+B). Можно было бы воспользоваться правилом Байеса для того, чтобы вычислить эту вероятность вручную:
P(B|A+B) = P(A+B|B)P(B)/P(A+B) =
=(P(A|B)+P(B|B)–P(A|B)P(B|B))P(B)/(P(A)+P(B)–P(A)P(B))=
=(P(A)+1–P(A))P(B)/(P(A)+P(B)–P(A)P(B))=0.6/(0.4+0.6–0.4*0.6)=0.789.
Однако уже для такой элементарной программы ручное применение правила Байеса требует некоторого времени, а для нетривиальных программ аналитически вычислить значения может и вовсе не получиться.
Итак, сэмплирование позволяет нам вычислять апостериорные вероятности интересующих нас случайных величин при наложении тех или иных условий. Оно заменяет правило Байеса, широко используемое в машинном обучении для выбора моделей или выполнения предсказаний. При этом запись программы на вероятностном языке для многих людей может оказаться гораздо понятнее, чем применение правила Байеса. Конечно, само режекторное сэмплирование весьма просто можно реализовать на обычном языке программирования, но вероятностные языки этим не ограничиваются.
В Чёрче, в частности, реализована другая функция для сэмплирования – enumeration-query. Запустим программу
(enumeration-query
(define A (flip 0.4))
(define B (flip 0.6))
B
(or A B))
На выходе мы получим: ((#t #f) (0.7894736842105263 0.2105263157894737)). Здесь выведены точные значения (конечно, со скидкой на конечную разрядную сетку) вероятностей P(B|A+B). enumeration-query уже не просто запускает много раз программу, но анализирует пути ее выполнения и перебирает все возможные значения случайных переменных с учетом их вероятностей. Конечно, такое «сэмплирование» будет работать, только когда множество возможных комбинаций значений случайных переменных не слишком велико.
Есть в Чёрче и более продвинутая замена режекторному сэмплированию на основе MCMC (Monte Carlo Markov Chains), а именно Metropolis Hastings алгоритм, откуда и название у процедуры – mh-query. Эта процедура запроса сразу формирует заданное число сэмплов (а также получает на вход один дополнительный параметр – лаг). Эта процедура также нетривиальна в реализации, так что использование готового вероятностного языка (а не собственная реализация простых процедур сэмплирования на обычном языке) приобретает смысл.
Однако главное, что дает вероятностное программирование, – это стиль мышления.
От азов к применению
Разные разработчики находят разные применения вероятностному программированию. Многие применяют его непосредственно для решения задач машинного обучения. Авторы же языка Чёрч, Noah D. Goodman and Joshua B. Tenenbaum, в своей web-книге «Probabilistic Models of Cognition» показывают применение вероятностного программирования для когнитивного моделирования. Также известно, как решение задач планирования удобно представлять в терминах вывода в вероятностных языках. Оно также оказывается применимым для представления знаний и вывода над ними, а также для задач машинного восприятия (в том числе, распознавания изображений). Все эти приложения пока более или менее разрозненные, но наличие общего фреймворка для всех них свидетельствует о том, что вероятностное программирование может стать «теорией великого объединения» для ИИ. Посмотрим на простейшие примеры возможного использования.
Одним из наиболее классических примеров применения экспертных систем является медицинская диагностика. В частности, система MYCIN была построена на системе правил вида:
- THE SITE OF THE CULTURE IS BLOOD
- THE GRAM OF THE ORGANISM I S NEG
- THE MORPHOLOGY OF THE ORGANISM IS ROD
- THE BURN OF THE PATIENT IS SERIOUS
Then there is weakly suggestive evidence (0.4) that
- THE IDENTITY OF THE ORGANISM IS PSEUDOMONAS
Очевидно, правила такого вида хорошо описываются на языке типа Чёрч. При этом нет необходимости еще и реализовывать процедуру вывода – достаточно просто записать систему правил. Приведем пример из упомянутой книги «Probabilistic Models of Cognition»:
(define samples
(mh-query 1000 100
(define lung-cancer (flip 0.01))
(define TB (flip 0.005))
(define cold (flip 0.2))
(define stomach-flu (flip 0.1))
(define other (flip 0.1))
(define cough (or (and cold (flip 0.5)) (and lung-cancer (flip 0.3)) (and TB (flip 0.7)) (and other (flip 0.01))))
(define fever (or (and cold (flip 0.3)) (and stomach-flu (flip 0.5)) (and TB (flip 0.2)) (and other (flip 0.01))))
(define chest-pain (or (and lung-cancer (flip 0.4)) (and TB (flip 0.5)) (and other(flip 0.01))))
(define shortness-of-breath (or (and lung-cancer (flip 0.4)) (and TB (flip 0.5)) (and other (flip 0.01))))
(list lung-cancer TB)
(and cough fever chest-pain shortness-of-breath)))
(hist samples "Joint inferences for lung cancer and TB")
В этой программе определяются априорные вероятности появления у больного рака легких, туберкулеза, простуды и т.д. Далее определяются вероятности наблюдения кашля, жара, боли в груди и стесненного дыхания при тех или иных заболеваниях. Возвращаемая величина – это пара булевых значений, есть ли у пациента рак и/или туберкулез. И, наконец, условие – это совокупность наблюдаемых симптомов (то есть сэмплирование производится при условии, что значение всех переменных – cough fever chest-pain shortness-of-breath – #t).
Результат выполнения программы будет иметь следующий вид: (#f #f) — 4%, (#f #t) — 58%, (#t #f) — 37%, (#t #t) — 1%.
Несложно сделать, чтобы samples была функцией, в которую подается перечень симптомов, который далее в mh-query используется для сэмплирования, что даст возможность ставить диагнозы разным пациентам. Конечно, этот пример сильно упрощенный, но видно, что в стиле вероятностного программирования вполне можно представлять знания и делать вывод над ними.
Естественно, можно решать и задачи машинного обучения. Их отличие будет лишь в том, что неизвестными величинами будут параметры самой модели, а в качестве условия для сэмплирования будет выступать генерация этой моделью обучающей выборки. К примеру, в представленной выше программе мы бы числа в строках вида (define lung-cancer (flip 0.01)) могли бы заменить на переменные, которые сами бы задавались как случайные, например (define p-lung-cancer (uniform 0 1)), а далее для каждого пациента из обучающей выборки значение lung-cancer уже определялось бы с вероятностью p-lung-cancer.
Рассмотрим эту возможность на простом примере оценивания параметров многочлена по набору точек. В следующей программе функция calc-poly вычисляет значение многочлена с параметрами ws в точке x. Функция generate применяет calc-poly к каждому значению из заданного списка xs и возвращает список соответствующих ординат. Процедура noisy-equals? «приближенно» сравнивает два заданных значения (если эти значения равны, то функция возвращает #t с вероятностью 1; если же они не равны, то чем больше они отличаются, тем с меньшей вероятностью она вернет #t).
(define (calc-poly x ws)
(if (null? ws) 0
(+ (car ws) (* x (calc-poly x (cdr ws))))))
(define (generate xs ws)
(map (lambda (x) (calc-poly x ws)) xs))
(define (noisy-equals? x y)
(flip (exp (* -3 (expt (- x y) 2)))))
(define (samples xs ys)
(mh-query 1 100
(define n-coef 4)
ws
(samples "(0 1 2 3 4) "(0.01 1.95 6.03 12.01 20.00))
Внутри вызова mh-query параметр n-coef определяет число коэффициентов в многочлене (то есть его степень минус один); ws – это список, состоящий из случайных величин, сгенерированных в соответствии с нормальным распределением. Возвращаемое значение – список параметров многочлена. Условие для сэмплирования – «приближенное» равенство всех заданных значений ys всем ординатам, порожденным многочленом при данных ws. Здесь мы запрашиваем всего одну реализацию, которая проходит по условию (поскольку строить гистограмму для вектора параметров не очень удобно). Результатом этого запроса может быть, к примеру, список (2.69 1.36 0.53 -0.10), задающий многочлен 2.69+1.36x+0.53x^2–0.10x^3.
Вообще, вывод на моделях с вещественными параметрами – не самая сильная сторона языка Чёрч (но не стоит это считать глобальным недостатком вероятностного программирования вообще). Тем не менее, на этом примере mh-query кое-как работает. Чтобы в этом убедиться, вместо определения значений параметров в запросе можно попросить возвращать предсказание в некоторой точке. Перепишем последний фрагмент кода так:
(define (samples xs ys)
(mh-query 100 100
(define n-coef 4)
(define ws (repeat n-coef (lambda () (gaussian 0 3))))
(calc-poly 5 ws)
(all (map noisy-equals? (generate xs ws) ys))))
(hist (samples "(0 1 2 3 4) "(0.01 1.95 6.03 12.01 20.00)))
То есть мы запрашиваем наиболее вероятное (при имеющихся данных) значение в точке x=5. При разных запусках максимум гистограммы, к сожалению, будет приходиться на несколько различающиеся значения (метод MCMC, теоретически, гарантирует схождение к истинному распределению, но лишь в пределе), но обычно эти значения будут достаточно вразумительными. Стоит заметить, что здесь мы «бесплатно» (заменой одной строчки) получили полное байесовское предсказание: вместо выбора лучшей модели и предсказания лишь по ней, мы получили апостериорное распределение значений в точке x=5, усредненное сразу по множеству моделей с учетом их собственных вероятностей.
Но и это еще не все. Опять же, заменой одной строчки – (define n-coef 4) -> (define n-coef (random-integer 5)) мы можем сделать автоматический выбор между моделями с разным числом параметров. Причем сэмплирование величины n-coef показывает (хотя и не очень стабильно), что наиболее вероятным значением является n-coef=3 (то есть парабола, которая и заложена в заданный набор точек). При такой модификации более стабильным становится и предсказание. Иными словами, не возникает и эффекта переобучения! Почему же не выбираются многочлены более высокой степени, ведь они могут точнее проходить к заданным точкам? Дело в том, что при сэмплировании «угадать» подходящие значения параметров многочлена меньшей степени проще, чем многочлена более высокой степени, поэтому вероятность породить такие параметры, которые пройдут проверку, для многочлена второй степени выше, чем для третьей. В то же время, многочлен первой степени будет давать большие отклонения, для которых вероятность срабатывания noisy-equals? будет сильно понижаться.
Посмотрим еще на одно применение, которое в рамках вероятностного программирования может показаться неожиданным. Это решение «дедуктивных» задач. Возьмем приведенную в начале функцию вычисления факториала, но вместо вызова ее с фиксированным значением будем считать, что аргумент – случайная переменная, но на само значение факториала наложено ограничение:
(define (f n)
(if (= n 0) 1 (* n (f (- n 1)))))
(enumeration-query
(define n (random-integer 20))
n
(equal? (f n) 120))
В качестве ответа мы увидим n=5 с вероятностью 1. Если же мы вместо 120 зададим 100, то программа не зациклится (в отличие от случая использования rejection-query или mh-query, что можно считать их недостатком), а просто вернет пустое множество. Можно поставить в качестве условия и не строгое равенство, а какое-то другое ограничение.
Таким же образом можно решать и более сложные задачи. Допустим, мы хотим решить задачу о сумме подмножеств: в ней надо из заданного множества чисел найти такое подмножество, сумма в котором равна заданному числу (обычно в качестве этого числа берется 0 и требуется, чтобы подмножество было не пустым; но чтобы избавиться от проверки на нетривиальность решения, мы возьмем ненулевую сумму). Казалось бы, причем тут вероятностное программирование? Но случайные величины – это просто неизвестные величины (для которых заданы априорные вероятности). В любых задачах нам нужно найти что-то неизвестное, в том числе и в задаче о сумме подмножеств. Посмотрим на следующую элементарную программу (ее можно было бы даже еще упростить, записав summ через fold).
(define (solution xs v)
(rejection-query
(define ws (repeat (length xs) flip))
(define (summ xs ws)
(if (null? xs) 0
(+ (if (car ws) (car xs) 0) (summ (cdr xs) (cdr ws)))))
ws
(equal? (summ xs ws) v)))
(solution "(-1 3 7 5 -9 -1) 1)
Здесь ws – список случайных булевых значений. Процедура summ вычисляет сумму элементов списка xs, для которых соответствующие элементы списка ws истинны. Далее запрашивается значения ws, для которых выполняется условие равенства полученной суммы заданному числу v. Запустив эту программу, можно получить такой результат: (#f #t #t #f #t #f), который, конечно, является правильным (так как 3+7-9=1).
Естественно, Чёрч не делает чуда и при повышении размерности этой задачи он с ней не справится. Однако не может не удивлять то, что столь разные задачи ИИ могут быть хотя бы поставлены (и отчасти решены) с использованием одного и того же языка. Ну, а проблема эффективного вывода как была, так и остается. В вероятностных языках она хотя бы выделяется в чистом виде.
This entry passed through the Full-Text RSS service - if this is your content and you"re reading it on someone else"s site, please read the FAQ at http://ift.tt/jcXqJW.
Эта публикация является первой частью краткого вступления с иллюстрациями в вероятностное программирование , которое является одним из современных прикладных направлений машинного обучения и искусственного интеллекта. Во время написания этой публикации я с радостью обнаружил, что на Хабрахабре совсем недавно уже была , хотя, к сожалению, в русскоговоряющем Интернете пока мало материалов на эту тему.
Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.
Вероятностное программирование я люблю определять как компактный , композиционный способ представления порождающих вероятностных моделей и проведения статистического вывода в них с учетом данных с помощью обобщенных алгоритмов. Хотя вероятностное программирование не вносит много фундаментального нового в теорию машинного обучения, этот подход привлекает своей простотой: «вероятностные порождающие модели в массы!»
«Обычное» программирование
Для знакомства с вероятностным программирование давайте сначала поговорим об «обычном» программировании. В «обычном» программировании основой является алгоритм, обычно детерминированный, который позволяет нам из входных данных получить выходные по четко установленным правилам.Например, если у нас есть мальчик Вася, и мы знаем где он находится, куда он бросает мяч и каковы внешние условия (например, сила ветра), мы узнаем, какое окно он, к сожалению, разобьет в здании школы. Для этого достаточно симулировать простые законы школьной физики, которые легко можно записать в виде алгоритма.
А теперь вероятностное программирование
Однако часто мы знаем только результат, исход, и мы заинтересованы в том, чтобы узнать то, какие неизвестные значения привели именно к этому результату? Чтобы ответить на этот вопрос с помощью теории математического моделирования создается вероятностная модель, часть параметров которой не определены точно.Например, в случае с мальчиком Васей, зная то, какое окно он разбил, и имея априорные знания о том, около какого окна он и его друзья обычно играют в футбол, и зная прогноз погоды на этот день, мы хотим узнать апостериорные распределение местоположения мальчика Васи: откуда же он бросал мяч?
Итак, зная выходные данные, мы заинтересованы в том, чтобы узнать наиболее вероятные значения скрытых, неизвестных параметров.
В рамках машинного обучения рассматриваются в том числе порождающие вероятностные модели. В рамках порождающих вероятностных моделей модель описывается как алгоритм, но вместо точных однозначных значений скрытых параметров и некоторых входных параметров мы используем вероятностные распределениях на них.
Существует более 15 языков вероятностного программирования, перечень с кратким описанием каждого из них можно найти . В данной публикации приведен пример кода на вероятностных языках Venture /Anglican , который имеют очень схожий синтаксис и которые берут свое начало от вероятностного языка Church . Church в свою очередь основан на языке «обычного» программирования Lisp и Scheme. Заинтересованному читателю крайне рекомендуется ознакомиться с книгой , являющейся одним из лучших способов начать знакомство с языком «обычного» программирования Scheme.
Пример Байесовской линейной регрессии
Рассмотрим задание простой вероятностной модели Байесовской линейной регрессии на языке вероятностного программирования Venture/Anglican в виде вероятностной программы:01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
Скрытые искомые параметры - значения коэффициентов t1
и t2
линейной функции x = t1 + t2 * time
. У нас есть априорные предположения о данных коэффициентах, а именно мы предполагаем, что они распределены по закону нормального распределения Normal(0, 1)
со средним 0 и стандартным отклонением 1. Таким образом, мы определили в первых двух строках вероятностной программы априорную вероятность на скрытые переменные, P(T)
. Инструкцию
можно рассматривать как определение случайной величины с именем name
, принимающей значение вычисляемого выражение (программного кода) expression
, которое содержит в себе неопределенность.
Вероятностные языки программирования (имеются в виду конкретно Church, Venture, Anglican), как и Lisp/Scheme, являются функциональными языками программирования, и используют польскую нотацию при записи выражений для вычисления. Это означает, что в выражении вызова функции сначала располагается оператор, а уже только потом аргументы: (+ 1 2) , и вызов функции обрамляется круглыми скобками. На других языках программирования, таких как C++ или Python, это будет эквивалентно коду 1 + 2 .
В вероятностных языках программирования выражение вызова функции принято разделять на три разных вида:
- Вызов детерминированных процедур (primitive-procedure arg1… argN) , которые при одних и тех же аргументах всегда возвращают одно и то же значение. К таким процедурам, например, относятся арифметические операции.
- Вызов вероятностных (стохастических) процедур (stochastic-procedure arg1… argN) , которые при каждом вызове генерируют случайным образом элемент из соответствующего распределения. Такой вызов определяет новую случайную величину . Например, вызов вероятностной процедуры (normal 1 10) определяет случайную величину, распределенную по закону нормального распределения Normal(1, sqrt(10)) , и результатом выполнения каждый раз будет какое-то вещественное число.
- Вызов составных процедур (compound-procedure arg1… argN) , где compound-procedure - введенная пользователем процедура с помощью специального выражения lambda : (lambda (arg1… argN) body) , где body - тело процедуры, состоящее из выражений. В общем случае составная процедура является стохастической (недетерминированной) составной процедурой, так как ее тело может содержать вызовы вероятностных процедур.
Перед вводом непосредственно самих наблюдений с помощью выражения мы определяем общий закон для наблюдаемых переменных xi в рамках нашей модели, а именно мы предполагаем, что данные наблюдаемые случайные величины при заданных t1 , t2 и заданном уровне шума noise распределены по закону нормального распределения Normal(t1 + t2 * time, sqrt(noise)) со средним t1 + t2 * time и стандартным отклонением noise . Данная условная вероятность определена на строках 3 и 4 данной вероятностной программы. noisy_x определена как функция, принимающая параметр time и возвращающая случайное значение, определенное с помощью вычисления выражение и обусловленное значениями случайных величин t1 и t2 и переменной noise . Отметим, что выражение (normal (+ t1 (* t2 time)) noise) содержит в себе неопределенность, поэтому каждый раз при его вычислении мы будем получать в общем случае разное значение.
На строках 5-7 мы непосредственно вводим известные значения x1 = 10.3 , x2 = 11.1 , x3 = 11.9 . Инструкция вида фиксирует наблюдение о том, что случайная величина, принимающая значение согласно выполнению выражения expression , приняла значение value .
Повторим на данном этапе всё, что мы сделали. На строках 1-4 с помощью инструкций вида мы задали непосредственно саму вероятностную модель: P(T) и P(X | T) . На строках 5-7 мы непосредственно задали известные нам значения наблюдаемых случайных величин X с помощью инструкций вида .
На строках 8-9 мы запрашиваем у системы вероятностного программирования апостериорное распределение P(T | X) скрытых случайных величин t1 и t2 . Как уже было сказано, при большом объеме данных и достаточно сложных моделях получить точное аналитическое представление невозможно, поэтому инструкции вида генерируют выборку значений случайных величин из апостериорного распределения P(T | X) или его приближения. Инструкция вида в общем случае генерирует один элемент выборки из значений случайной величины, принимающей значение согласно выполнению выражения expression . Если перед инструкциями вида расположены инструкции вида , то выборка будет из апостериорного распределения (говоря точнее, конечно, из приближения апостериорного распределения), обусловленного перечисленными ранее введенными наблюдениями.
Отметим, что в завершении мы можем также предсказать значение функции x(time) в другой точке, например, при time = 4.0 . Под предсказанием в данном случае понимается генерация выборки из апостериорного распределения новой случайной величины при значениях скрытых случайных величин t1 , t2 и параметре time = 4.0 .
Для генерации выборки из апостериорного распределения P(T | X) в языке программирования Venture в качестве основного используется алгоритм Метрополиса-Гастингса, который относится к методам Монте-Карло по схеме Марковских цепей. Под обобщенным выводом в данном случае понимается то, что алгоритм может быть применен к любым вероятностным программам, написанным на данном вероятностном языке программирования.
В видео, прикрепленном ниже, можно посмотреть на происходящий статистический вывод в данной модели.
(На видео показан пример, основанный на языке вероятностного программирования Venture.)
В самом начале у нас нет данных, поэтому мы видим априорное распределение прямых. Добавляя точку за точкой (таким образом, элементы данных), мы видим элементы выборки из апостериорного распределения.
На этом мы закончим первую часть данного вступления в вероятностное программирование.
