Пользователь
0,0
рейтинг
1 декабря 2014 в 11:08

Разработка → Вероятностное программирование из песочницы

Вступление


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

Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.

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

«Обычное» программирование


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



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



А теперь вероятностное программирование


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

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



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

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

Существует более 15 языков вероятностного программирования, перечень с кратким описанием каждого из них можно найти здесь. В данной публикации приведен пример кода на вероятностных языках Venture/Anglican, который имеют очень схожий синтаксис и которые берут свое начало от вероятностного языка Church. Church в свою очередь основан на языке «обычного» программирования Lisp и Scheme. Заинтересованному читателю крайне рекомендуется ознакомиться с книгой «Структура и интерпретация компьютерных программ», являющейся одним из лучших способов начать знакомство с языком «обычного» программирования Scheme.

Пример Байесовской линейной регрессии


Рассмотрим задание простой вероятностной модели Байесовской линейной регрессии на языке вероятностного программирования Venture/Anglican в виде вероятностной программы:

01: [ASSUME t1 (normal 0 1)]
02: [ASSUME t2 (normal 0 1)]
03: [ASSUME noise 0.01]
04: [ASSUME noisy_x (lambda (time) (normal (+ t1 (* t2 time)) noise))]
05: [OBSERVE (noisy_x 1.0) 10.3]
06: [OBSERVE (noisy_x 2.0) 11.1]
07: [OBSERVE (noisy_x 3.0) 11.9]
08: [PREDICT t1]
09: [PREDICT t2]
10: [PREDICT (noisy_x 4.0)]

Скрытые искомые параметры — значения коэффициентов t1 и t2 линейной функции x = t1 + t2 * time. У нас есть априорные предположения о данных коэффициентах, а именно мы предполагаем, что они распределены по закону нормального распределения Normal(0, 1) со средним 0 и стандартным отклонением 1. Таким образом, мы определили в первых двух строках вероятностной программы априорную вероятность на скрытые переменные, P(T). Инструкцию [ASSUME name expression] можно рассматривать как определение случайной величины с именем 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 — тело процедуры, состоящее из выражений. В общем случае составная процедура является стохастической (недетерминированной) составной процедурой, так как ее тело может содержать вызовы вероятностных процедур.

Вернемся к исходному коду на языке программирования Venture/Anglican. После первых двух строк мы хотим задать условную вероятность P(X | T), то есть условную вероятность наблюдаемых переменных x1, x2, x3 при заданных значениях скрытых переменных t1, t2 и параметра time.

Перед вводом непосредственно самих наблюдений с помощью выражения [OBSERVE ...] мы определяем общий закон для наблюдаемых переменных xi в рамках нашей модели, а именно мы предполагаем, что данные наблюдаемые случайные величины при заданных t1, t2 и заданном уровне шума noise распределены по закону нормального распределения Normal(t1 + t2 * time, sqrt(noise)) со средним t1 + t2 * time и стандартным отклонением noise. Данная условная вероятность определена на строках 3 и 4 данной вероятностной программы. noisy_x определена как функция, принимающая параметр time и возвращающая случайное значение, определенное с помощью вычисления выражение (normal (+ t1 (* t2 time)) noise) и обусловленное значениями случайных величин t1 и t2 и переменной noise. Отметим, что выражение (normal (+ t1 (* t2 time)) noise) содержит в себе неопределенность, поэтому каждый раз при его вычислении мы будем получать в общем случае разное значение.

На строках 5—7 мы непосредственно вводим известные значения x1 = 10.3, x2 = 11.1, x3 = 11.9. Инструкция вида [OBSERVE expression value] фиксирует наблюдение о том, что случайная величина, принимающая значение согласно выполнению выражения expression, приняла значение value.

Повторим на данном этапе всё, что мы сделали. На строках 1—4 с помощью инструкций вида [ASSUME ...] мы задали непосредственно саму вероятностную модель: P(T) и P(X | T). На строках 5—7 мы непосредственно задали известные нам значения наблюдаемых случайных величин X с помощью инструкций вида [OBSERVE ...].

На строках 8—9 мы запрашиваем у системы вероятностного программирования апостериорное распределение P(T | X) скрытых случайных величин t1 и t2. Как уже было сказано, при большом объеме данных и достаточно сложных моделях получить точное аналитическое представление невозможно, поэтому инструкции вида [PREDICT ...] генерируют выборку значений случайных величин из апостериорного распределения P(T | X) или его приближения. Инструкция вида [PREDICT expression] в общем случае генерирует один элемент выборки из значений случайной величины, принимающей значение согласно выполнению выражения expression. Если перед инструкциями вида [PREDICT ...] расположены инструкции вида [OBSERVE ...], то выборка будет из апостериорного распределения (говоря точнее, конечно, из приближения апостериорного распределения), обусловленного перечисленными ранее введенными наблюдениями.

Отметим, что в завершении мы можем также предсказать значение функции x(time) в другой точке, например, при time = 4.0. Под предсказанием в данном случае понимается генерация выборки из апостериорного распределения новой случайной величины при значениях скрытых случайных величин t1, t2 и параметре time = 4.0.

Для генерации выборки из апостериорного распределения P(T | X) в языке программирования Venture в качестве основного используется алгоритм Метрополиса-Гастингса, который относится к методам Монте-Карло по схеме Марковских цепей. Под обобщенным выводом в данном случае понимается то, что алгоритм может быть применен к любым вероятностным программам, написанным на данном вероятностном языке программирования.

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


(На видео показан пример, основанный на языке вероятностного программирования Venture.)

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

На этом мы закончим первую часть данного вступления в вероятностное программирование.

Материалы


Ниже я приведу рекомендуемые ссылки для тех, кто хочет прямо сейчас узнать больше о вероятностном программировании:
  1. Сайт вероятностного языка программирования Anglican, который является собратом Venture и потомком Church.
  2. Обучающий курс по вероятностному языку программирования Anglican.
  3. Курс по вероятностному программированию, прочитанный на одной из школ по машинному обучению: часть 1, часть 2 и часть 3.
  4. Курс «Проектирование и реализация вероятностных языков программирования».
  5. Курс «Вероятностные порождающие модели познания (одна из сфер применения вероятностного программирования)».

Данная публикация основана на моей бакалаврской научной работе, которая была защищена летом этого года в Институте математики и фундаментальной информатики Сибирского федерального университета. Заинтересованный читатель найдет в ней более подробное и формальное введение в вероятностное программирование. В работе в конце также есть вся полная библиография, на основе которой написана и данная публикация.
Юра Перов @YuraPerov
карма
15,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (40)

  • 0
    По вашему мнению, вероятностное программирование эволюционное продолжение теории машинного обучения?
    • +2
      Я субъективно считаю, что вероятностное программирование на текущий момент — это лишь прикладное направлении машинного обучения.

      Вероятностное программирование не вносит ничего фундаментально нового само по себе. Оно лишь позволяет компактно и композионно записывать вероятностные модели и также «снабжает» нас автоматическими универсальными методами статистического вывода.

      Я и мои коллеги любим проводить следующую параллель. Сейчас большая часть работы в машинном обучении — это как написание кода на Ассемблере. Например, чтобы написать алгоритм статистического вывода по Гиббсу или вариационный вывод для конкретной модели, нужно потратить достаточно много времени. Если же использовать языки вероятностного программирования, то запись модели — дело нескольких десятков минут, а статистический вывод производится автоматически; и это можно сравнить с использованием Python вместе Ассемблера: разрабатывать и изменять намного быстрее, но работает намного медленнее.

      Вероятностное программирование дает простоту в записи модели и возможность сразу же попробовать на ней статистический вывод.
  • 0
    Интересно, есть ли математика для индетерминизма, которая пытается работать так же, как байес-формулы в вероятностном программирование, т.е. в предиктивном плане?

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

    Вместе с тем, никто не запрещает упрощать причины. Мы даже можем ввести в описание априорного события всего две причины: исследуемую и любую другую как совокупность, и тогда для описания элемента нам потребуется байт и два указателя, это совсем немного.
    • 0
      По поводу «математики для индетерминизма»

      Если я правильно понимаю, одним из примеров подобного научного направления является индуктивное логическое программирование (англ.).

      По поводу задания ущербности априорной вероятности

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

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

      [ASSUME hyper (gamma 1 1)]
      [ASSUME mean (0.0 hyper)]
      [OBSERVE (normal mean 1) 5.0]
      

      Здесь неизвестная случайная величина mean «вызывается» гипер-параметром hyper, который также неизвестен.

      ***

      Прошу прощения, но про энтропийный барьер и про упрощение причин не понял. Прошу привести пример.
      • 0
        О, благодарю, реализация индуктивной логики в прологе — это еще одно «не», от которого можно оттолкнуться. Смешивание фактов и предположений в одну конструкцию (точнее, то, что предполагается, программист будет их смешивать и реализовывать именно такую логику) — это описание гипотезы, лишенное главной цели гипотезы — получить в итоге теорию. Оно не будет эффективно работать на практике, потому что в нем (явно! хаха!) заложен энтропийный барьер.

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

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

        Благодаря энтропийному барьеру возможно новое знание, новая информация вроде изобретений и интерпретаций законов природы.
        Но я пока не видел, чтобы его реализовали в математике и программировании:
        — вероятностный, байесовский подход вроде как способен создать новое знание, но оно принципиально неформализуемо (энтропийный барьер не исчезает, система «вязнет» в нем)
        — логика пролога — просто ходячая демонстрация ЭБ.
        — совместить их нельзя. Или можно? К примеру, чтобы апостериорные вероятности считались истинными причинами и в таком виде формировали условное множество для догматически заданного правила. Да, это не сможет создать нового знания, но и не надо прыгать через голову.
        • 0
          Я надеюсь, что мои краткие ответы ниже не покажутся агрессивными, по крайней мере в них совсем нет попытки оскорбить. Это просто мои мысли в ответ на Ваши мысли.

          >>> «Смешивание фактов и предположений в одну конструкцию...»

          Я не знаю способов отличить факты от предположений. Для меня философски любой факт о мире — это предположение. Любая теория для меня — это предположение и предположение неточное.

          >>> Вот мы к нему и подошли. Смотрите, NP-полнота требует вычисления всех предикатов, которые растут экспоненциально. К примеру, если делать медицинскую диагностику на такой логике (1000 болезней, 3000 симптомов в среднем по 10 в каждой), на вычисление уйдут ресурсы, сопоставимые с вечностью. А это не самая сложная задача…

          А нужно ли вычислять все предикаты? Можно ли вычислить только часть предикатов и таким образом получить удовлетворительный, пусть и не самый лучший ответ? Ведь любой самый лучший врач, например, никогда не сможет постоянно давать самые лучшие ответы и будет иногда ошибаться, к сожалению. Я не совсем понимаю, в рамках какой модели мы говорим о 3000 симптомах и какой алгоритм для диагностики болезней предлагается использовать. Но что я пытаюсь спросить, а можем ли мы всегда рассчитывать на самый лучший ответ? Что вообще такое самый лучший ответ? Я не знаю ответа на этот вопрос…

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

          Я в этой статье и в комментариях к ней пытаюсь мыслить конкретно о том, необходимо ли вероятностное программирование как приложение методов машинного обучения, которые уже используются? Да, мне кажется, что необходимо, так как оно позволяет проще работать с порождающими «Байесовскими» вероятностными моделями, которые уже используются в машинном обучении. То есть какой-то хороший результат это нам даст и сделает прикладное машинное обучение немного проще.

          Решит ли вероятностное программирование проблему «сильного» искусственного интеллекта? Скорее всего нет, по крайней мере само по себе не решит.

          Я прошу прощения, что я не отвечаю на Ваш вопрос, и честно признаюсь, что я не знаю на него ответа. На сегодня я удовлетворен приблизительным решением проблем машинного обучения и необходимостью указывать априорные вероятности. Как обойтись без этого и/или решать проблемы точно? Я не знаю :).
          • 0
            Не переживайте по поводу агрессивности, мы же не демагогией занимаемся, а истину ищем)
            > Я не знаю способов отличить факты от предположений.
            Тогда я поправлюсь: смешивание догм и предположений. Догма как раз не должна проверяться, пример догмы — неравенство натуральных чисел.

            > А нужно ли вычислять все предикаты? Можно ли вычислить только часть предикатов и таким образом получить удовлетворительный, пусть и не самый лучший ответ?
            Edward H. Shortliffe тоже так думал, и он ошибся. Такая редукция уменьшает качество результата быстрее, чем падает объем вычислений.

            >Статистический вывод и другие методы машинного обучения дают хорошие ответы: мы пользуемся поиском Гугла, наша почта фильтруется на спам, распознаются номера на машинах, чтобы водители не превышали скорость, и так далее.
            В основном это заслуга величайших умов, создавших правильные точные алгоритмы. Где-то в их глубине встроено немного машинного обучения. Говорить о победе МО в этом случае — некорректно. (взять то же распознавание изображений — сначала идет алгоритмическое разложение по фильтрам, затем алгоритмическая (с допустимым шумом) сверка паттернов, а байес-сеть управляет только порядком перебора этих паттернов, увеличивая скорость).
            Не хочу дальше об этом спорить, мы всё это пробовали, и сейчас для логического вывода у нас не используется ни один из способов манипуляции с предиктивной вероятностью.

            > Решит ли вероятностное программирование проблему «сильного» искусственного интеллекта?
            Сильный ИИ — это просто абстракция, объединяющая как свойства, недоступные уже реализованным версиям ИИ, так и мыслимые категории из разных направлений философии. Сильный ИИ — это не какая-то определенная штука.

            P.S. Можно не продолжать, я уже получил необходимые ответы, благодарю Вас.
    • 0
      в самом деле, описывать возможное, мыслимое макрособытие как определяемое единственным числом (его вероятностью) в то время, как оно вызывается причинами — как-то глупо
      Почему глупо? А описывать его десятью числами лучше? А 101000000 числами?

      Если Вы вдруг считаете, что чем больше чисел, тем лучше, то спешу напомнить о том, что счётное объединение счётных множеств счётно, т.е. 101000 чисел имеют ту же выразительную мощность, что и одно число.
      Конечно, всё хорошо в мире математики, где есть бесконечности и даже континуум, но с модельной точки зрения Ваш аргумент неубедителен.
      • 0
        Вот я и думаю, что описывать причинно-следственные отношения, при которых для одного и того же следствия возможны разные причины, нельзя только счетными множествами.
        • 0
          Так то же самое справедливо и для континуальных множеств. Или Вы за трансфиниты?
  • +5
    На мой взгляд, статья написана слишком сложным языком.
    Начинается прекрасно — пример с мальчиком отлично иллюстрирует задачу! Но затем очень резко переходим к «Байесовской линейной регрессии», и аудитория понимающих резко сокращается. Почему не продолжить пример с мальчиком и окнами? Я способен нагуглить и разобраться, что это за байесовская регрессия, но зачем заставлять читателя это делать?

    По крупицам вроде бы сложилось понимание — на вероятностном языке различными способами задаются ограничения входных параметров — то есть из всех окон выбираем только те, которые со стороны футбольного поля, ограничиваем скорость ветра и силу удара адекватными значениями, затем задаём наблюдения — такие-то окна разбиты столько-то раз. А далее уже система за нас ищет наиболее вероятные входные параметры, удовлетворяющие огрничениям и выходным данным.
    • –6
      Соглашусь с высказыванием.
      Сильно бесит этот дебильный стиль «дипломной работы». В любом случае, не совсем тухлая херня как предыдущий пост о вероятностном программировании.
      • +2
        Стоп-стоп… В таком случае, где ваша статья, которая не является «тухлой херней» и написана прекрасным языком а не «дебильным стилем дипломной работы»?
        • –1
          Ох… Как наличие (или отсутствие) у меня прекрасной статьи влияет на
          • качество этой статьи
          • моё право высказывать мнение по этой статье

          ? Никак.
          Ей-богу, думал к 30 годам такие «школьные защитники» уже должны были вырасти.
          • +2
            Наличие или отсутствие статьи у вас — никак не влияет. Я просто был удивлен, листая комментарии, когда увидел термины «тухлая херня» и «дебильный». Ей-богу, я просто отвык от того, что на хабре встречаются люди, способные считать конструктивной критикой собственные каменты вида «школота-стайл».

            Почему этот человек вправе так писать, подумал я? Может он эксперт в этой области, может он действительно устал от плохих статей и поэтому сорвался на грубость и неуважительные обороты речи? Но тогда у него, я, наверняка, найду материалы по этой же теме и поучусь уму-разуму, подумал я. Не нашел. Странно, отчего же автор тогда ведет себя, как банальная школота? Может он и есть школота? Да нет, вроде 24 года, должен бы вырасти уже. Пожалуй, надо бы задать этот вопрос самому автору, подумал я, и написал тот комментарий, мол, а чего вы, уважаемый кипятитесь, может вы эксперт в этой области? Но если так, где тогда ваше разумное-доброе-вечное? Его нет т.к. вам лень публиковаться? Или его нет, т.к. вы неспособны даже сделать чего-то подобного?

            Это и был, собственно, смысл моего предыдущего комментария.
    • 0
      Спасибо за комментарий! В следующей публикации разберу пример с Васей и окнами на примере вероятностной программы и соответствующего статистического вывода.
      • +1
        Может лучше обновить уже существующую? Плавно переходя от мальчика с окнами к регрессии.
        • 0
          Я планирую, что это будет отдельная, новая, немаленькая статья. Я аккуратно добавлю ссылку на нее в нужное место в этой статье, чтобы заинтересованные читатели могли сразу же найти ее.
  • 0
    А где в первой кодине t1 используется?
    • 0
      В четвертой строчке: noisy_x = function (time) { Normal(t1 + t2 * time, noise); }
  • +2
    Я, если честно, ничего не понял. Слышал про вероятностное программирование, но когда слышал, тоже ничего не понял. :)

    Понятно, что MCMC работает почти везде, и, наверное, можно написать единую реализацию, которая делает MCMC на широком классе моделей; это само по себе интересно и применимо, конечно. Верно ли я понял, что «вероятностное программирование» — это именно такая реализация?

    Если да, то применять MCMC к линейной регрессии — это очень странная идея, разве нет? Там есть замкнутые формулы; для логистической не совсем замкнутые, но всё равно на порядки быстрее MCMC должно быть, по идее.

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

    Сорри, что такую ретроградскую позицию занял. :) Вероятно, я чего-то недопонял насчёт того, что на самом деле делают эти языки под капотом. В частности, я действительно не совсем понял, как он понимает, как надо делать вывод. Например, на простом фактор-графе без циклов будет ли он делать всё-таки message passing, как было бы логично? И если да, то как он поймёт, надо ли делать expectation propagation и если надо, то чем приближать?..

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

    А что было бы супер-полезно — это хорошая стандартная библиотека базовых алгоритмов машобуча, как lapack/blas для линейной алгебры. То есть всё уже написано, конечно, но есть пока что ситуация «14 competing standards» в каком-то смысле, особенно если на разных языках посмотреть; а базовая библиотека должна быть единой и над ней уже должны быть обёртки для языков, как над lapack'ом.
    • 0
      Здравствуйте! Спасибо Вам большое за комментарий и вопросы!

      >>> Верно ли я понял, что «вероятностное программирование» — это именно такая реализация?

      Грубо говоря, да. Вместо MCMC также используется SMC, например, и другие методы вывода. Но в основном обычно речь идет об MCMC.

      >>> Если да, то применять MCMC к линейной регрессии — это очень странная идея, разве нет?

      Я согласен, что это странная это идея с точки зрения эффективности. Зачем копать землю ложкой, если есть лопата, которой копать быстрее? Но с другой стороны, почему так много людей используют Python, если он значительно медленее, чем C++?

      Пример линейной регрессии — это просто чтобы показать то, что можно делать, на самом простом возможном примере.

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

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

      Согласен, но ведь всегда вопрос (1) в степени понимания (например, все ли программисты понимают, как именно работает процессор? Мешает ли это им решать задачи?), (2) в том, как система помогает пониманию (например, можно разработать удобные и информативные методы отладки статистического вывода).

      >>> Например, на простом фактор-графе без циклов будет ли он делать всё-таки message passing, как было бы логично? И если да, то как он поймёт, надо ли делать expectation propagation и если надо, то чем приближать?..

      Venture/Anglican/Church в основном делают сейчас MCMC/SMC. Infer.Net позволяет работать с менее широким классом моделей, но при этом как раз реализует чаще более эффективные алгоритмы, как раз включая expectation propagation и message passing.

      >>> Но если это всё, то не надо, наверное, таких громких слов про «новое программирование». :)

      Название «вероятностное программирование» — это спорное название. Можно назвать направление «вероятностным моделированием с автоматически универсальным выводом», например. «Вероятностное программирование» — это не новое «программирование». Это просто игра слов, которую можно логически обосновать :).

      >>> А что было бы супер-полезно — это хорошая стандартная библиотека базовых алгоритмов машобуча, как lapack/blas для линейной алгебры. То есть всё уже написано, конечно, но есть пока что ситуация «14 competing standards» в каком-то смысле, особенно если на разных языках посмотреть; а базовая библиотека должна быть единой и над ней уже должны быть обёртки для языков, как над lapack'ом.

      Подскажите, пожалуйста, что Вы имеет в виду под уже написанными?
      • 0
        (2) — именно! чтобы понять, что сломалось, надо понимать, как оно работает; я всеми руками за то, чтобы больше инкапсулировать в библиотеки, но в данном случае всё-таки надо понимать, как работает, потому что пользователь не просто пользуется готовым, а, по замыслу, создаёт новые модели.

        Infer.Net я когда-то как раз пробовал; честно говоря, мне не очень понравилось. :) То есть модель закодировалась и даже как-то работала, но ужасно медленно и не то чтобы суперинтуитивно, хотя мы делали как раз в точности то, для чего Infer.Net предназначен — расширение рейтинг-системы TrueSkill. Правда, это было лет пять назад уже, плюс накладывались проблемы с Mono/.NET — опять то, о чём я говорю: хорошая библиотека должна быть написана на си, компилироваться под конкретную архитектуру и дальше давать уже обёртки в разные языки; библиотека под .NET не имеет шансов. :)

        Люди используют python вместо C++ потому, что время на разработку сильно сокращается. Вот в моём примере выше с Infer.Net мы пробовали-пробовали, как-то оно всё то работало, то не работало, то работало очень медленно. Так прошли несколько недель… а потом мы плюнули, посидели денёк, вывели формулы для сообщений и закодировали их сами. Этот опыт дал нам большой плюс к пониманию того, как работает наша модель — и этот бонус тут же пригодился, потому что там были кое-какие экстремальные случаи, на которых Infer.Net ломался, и было непонятно, почему. Время разработки на этом только сэкономилось.

        Плюс неверно было бы говорить, что мы бы один раз «освоили Infer.Net», а потом всё время «за час долетали»:
        (1) понимать, как работает, всё равно было бы необходимо, иначе даже error messages не поймёшь;
        (2) поскольку нет единой стандартной библиотеки, с большой вероятностью в следующий раз лучше было бы использовать не Infer.Net, а что-нибудь другое, и всё началось бы сначала.

        Уже написанные — ну, например, на python есть фактически стандартные библиотеки scikit-learn и statsmodels. На C++ уже сложнее, есть mlpack, работающий с armadillo, а больше я и не знаю. Понятно, что на R есть всё, но это отдельное удовольствие. И есть стандартные библиотеки для отдельных алгоритмов вроде libsvm, которые как раз работают как я сказал — есть одна библиотека и к ней обёртки для разных языков. Но всё как-то не очень унифицировано пока, а для более сложных моделей так и вовсе ничего стандартного нету.
        • 0
          (3) я всё время работаю в области машинного обучения, и за эти пять лет ни разу пока не встретил другого проекта с большим графом без циклов, но с expectation propagation… :) вот логистическую регрессию да, часто делаю, а такие сложные модели встречаются штучно, и к каждой новый подход всё равно нужен получается…
          • 0
            Прошу прощения за поздний ответ.

            Вы правы, особенно с позиции человека, который профессионально занимается машинным обучением. Ничто не заменит собственное понимание, и чем оно больше, тем лучше результат.

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

            Мы рассчитываем, что для решения части задач в конечном счете будет быстрее использовать их, чем писать вывод самому, по крайней мере на первом этапе тестирования модели или при умеренном количестве наблюдений. Например, для приложений в бизнесе.
            • 0
              Было бы хорошо увидеть конкретные примеры…

              Хотя, конечно, даже стандартных библиотек очень не хватает. Я вот недавно столкнулся: нужна была самая обычная логистическая регрессия, но так, чтобы можно было в response variable давать не 0/1, а любую целевую вероятность от 0 до 1; т.е. функция правдоподобия та же самая, просто степени в ней теперь дробные. И нигде в питоне не нашёл! :) Ни sklearn.linear_model.LogisticRegression, ни sklearn.linear_model.SGDClassifier с loss='log' такого не умеют. До сих пор, кстати, не знаю, что делать, пока что чешу левой рукой за правым ухом, запуская glmnet в R через pyper…
              • 0
                Несколько примеров есть здесь:
                1. www.robots.ox.ac.uk/~fwood/anglican/examples/index.html
                2. www.robots.ox.ac.uk/~fwood/anglican/teaching/mlss2014/index.html
                3. probmods.org/


                Но пока они по скорости (и часто асимптотически) уступают вручную написанному статистическому выводу.

                По поводу вопроса про логистическую регрессию: извините, к сожалению, не знаю хорошего решения.
                • 0
                  Я имел в виду примеры «для приложений в бизнесе»; по первой ссылке очень интересный пример про процессы Дирихле. Кстати, меня во всех примерах очень смущает код вроде
                  ; observe draws from the DP mixture
                  [observe (normal (get-mean (get-class 1)) (get-std (get-class 1))) 10]
                  [observe (normal (get-mean (get-class 2)) (get-std (get-class 2))) 11]
                  [observe (normal (get-mean (get-class 3)) (get-std (get-class 3))) 12]

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

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

                    Есть публикации, где используют вероятностные языки программирования, но это пока больше научные вещи, например:
                    1. www.mrc-bsu.cam.ac.uk/software/bugs/the-bugs-project-bugs-resources-online/
                    2. research.microsoft.com/en-us/um/cambridge/projects/infernet/papers.aspx

                    Приложения в бизнесе это пока план, а не полученный результат :).

                    ***

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

                    Да, например, есть OBSERVE-CSV: www.robots.ox.ac.uk/~fwood/anglican/language/

                    Реализовать что-то подобное для других форматов — дело нескольких часов.

                    Для Venture ввод данных можно осуществлять с помощью Python, подгружая Venture как модуль Python.
              • 0
                А почему бы для такой хитрой логистической регрессии просто вектор признаков на соответствующую константу (зависящую от target'а) не домножнить?
                • 0
                  И что будет?..
                  • 0
                    Известную мне логистическую регрессию, где модельная вероятность задаётся как image, можно расширить на вероятностный случай заменив yi на 2 p(yi=1) — 1

                    Тогда
                    image

                    Тогда пары (zi, sign(2 p(yi=1) — 1)) дадут датасет, готовый к применению в обычной логистической регрессии.

                    UPD: Правда, тут не учитываются негативные эффекты от регуляризации, без которой результат вообще был бы идентичен дискретному случаю y = ±1.
                    • 0
                      Мда, что за бред я несу… Регуляризация тут ни при чём.
                    • 0
                      Простите, что я медленный, но можете дать ссылку?
                      Я совершенно не против, просто не понял пока что — мне нужно, чтобы

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

                        Есть 2 (эквивалентных) способа определить функционал максимального правдоподобия для логистической регрессии (правда, ни в EoSL, ни в PRML второй не упоминается, а в MLAPP только мельком). В одном случае таргеты можно интерпретировать как огрублённые вероятности класса 1 (т.е. y ∈ {0, 1}), а в другом — как метки класса (y ∈ {-1, +1}). В первом MLE приводит нас к настойщей кросс-энтропии в качестве функции потерь, а второй — к той, о которой я писал выше (она же, видимо, используется в статье, на которой основан алгоритм из sklearn).

                        Так что да, использовать sklearn никак не получится.
                        • 0
                          Честно говоря, всё равно не понял — заменить 0 на -1 я, конечно, совершенно не возражаю, если будет нужно. :) Просто мне кажется, что из того, что у меня для каких-то α и , не следует, что (разумная функция от y и α), как ни определяй.

                          Ну да ладно.
  • 0
    Спасибо за публикацию. Не уточните, пожалуйста, некоторые детали.

    1. Любопытно посмотреть на эффективность работы в сравнении с другими языками. В этой публикации дается обзор по времени работы в разных «обычных» языках программирования сэмплирования по Гиббсу для некого двумерного распределения: здесь. Если несложно, сообщите, что будет в Venture/Anglican?

    2. Как обстоят дела с набором заданных в языке распределений. Например, truncated multivariate normal distribution из коробки есть?

    3. Интересно посмотреть на код генерации случ. величин из truncated mv normal distribution, оценить, если получится, сложность реализации. Не могли бы Вы указать ссылку на источник?
    • 0
      Здравствуйте! Благодарю Вас за интересные вопросы.

      1) Я грубо предполагаю, что в Venture/Anglican это будет в 50-500 раз медленнее, чем в C.

      Probabilistic-C, скорее всего, по выводу может быть в 3-10 раз медленее, чем C.

      Спасибо за эту статью, записал себе в план протестировать, чтобы были точные результаты. В целом можно отметить, что сейчас движки вероятностных языков программирования очень значительно медленнее, чем вручную написанный вывод на C / Python. Мы надеемся, что с помощью различных оптимизаций (в том числе оптимизаций подобных оптимизациям при компиляции) мы нам удастся уменьшить различия в скорости в разы.

      2) Пока заданных распределений очень мало. Но так как движки этих вероятностных языков программирования реализованы на обычных языках программирования (Clojure ("=>" Java), C++, Python), то добавить новое распределение — дело нескольких десятков минут или по крайней мере нескольких часов.

      3) Это будет просто код на C++ / Python / Clojure. Вот, например, реализация нормального распределения; всего 17 строчек. Нужно указать функцию генерации элемента выборки и функцию плотности распределения.

      Надеюсь, мои ответы немного полезны. Буду рад ответить более подробно или на другие вопросы.
  • 0
    Здравствуйте! Спасибо за ответы.

    2-3. Извините, не точно выразился. Понятно, что можно использовать готовую реализацию распределения на обычном языке.
    Поскольку Anglican ориентирован на MCMC, интересно, как элегантно именно в нем можно задать новое распределение. Возможно, с сэмплированием я перегнул, обычный язык для этих целей вполне приемлем.
    Если исполнение в вероятностном языке будет еще и эффективно по времени, то это было бы замечательно.
  • 0
    Прошу прощения за поздний ответ.

    В Anglican основан на Scheme (хотя и без set!), и в нем можно задать любую функцию. Например, если бы не было геометрического распределения, его можно было бы очень просто задать функций

    (define geom
      (lambda (weight) (if (= (bernoulli weight) 1) 1 (+ 1 (geom weight)))))
    

    То есть практически любое распределение можно задать через его генератор.

    Что же касается скорости, то скорость в общем случае будет ниже. Однако, например, Probabilistic C компилирует вероятностные программы, поэтому там скорость будет сравнима с обычной скоростью любого генератора, который можно написать на C/C++.

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