Эта публикация является первой частью краткого вступления с иллюстрациями в вероятностное программирование , которое является одним из современных прикладных направлений машинного обучения и искусственного интеллекта. Во время написания этой публикации я с радостью обнаружил, что на Хабрахабре совсем недавно уже была , хотя, к сожалению, в русскоговоряющем Интернете пока мало материалов на эту тему.
Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.
Вероятностное программирование я люблю определять как компактный , композиционный способ представления порождающих вероятностных моделей и проведения статистического вывода в них с учетом данных с помощью обобщенных алгоритмов. Хотя вероятностное программирование не вносит много фундаментального нового в теорию машинного обучения, этот подход привлекает своей простотой: «вероятностные порождающие модели в массы!»
Для знакомства с вероятностным программирование давайте сначала поговорим об «обычном» программировании. В «обычном» программировании основой является алгоритм, обычно детерминированный, который позволяет нам из входных данных получить выходные по четко установленным правилам.
Например, если у нас есть мальчик Вася, и мы знаем где он находится, куда он бросает мяч и каковы внешние условия (например, сила ветра), мы узнаем, какое окно он, к сожалению, разобьет в здании школы. Для этого достаточно симулировать простые законы школьной физики, которые легко можно записать в виде алгоритма.
Однако часто мы знаем только результат, исход, и мы заинтересованы в том, чтобы узнать то, какие неизвестные значения привели именно к этому результату? Чтобы ответить на этот вопрос с помощью теории математического моделирования создается вероятностная модель, часть параметров которой не определены точно.
Например, в случае с мальчиком Васей, зная то, какое окно он разбил, и имея априорные знания о том, около какого окна он и его друзья обычно играют в футбол, и зная прогноз погоды на этот день, мы хотим узнать апостериорные распределение местоположения мальчика Васи: откуда же он бросал мяч?
Итак, зная выходные данные, мы заинтересованы в том, чтобы узнать наиболее вероятные значения скрытых, неизвестных параметров.
В рамках машинного обучения рассматриваются в том числе порождающие вероятностные модели. В рамках порождающих вероятностных моделей модель описывается как алгоритм, но вместо точных однозначных значений скрытых параметров и некоторых входных параметров мы используем вероятностные распределениях на них.
Существует более 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 .
В вероятностных языках программирования выражение вызова функции принято разделять на три разных вида:
Вернемся к исходному коду на языке программирования Venture/Anglican. После первых двух строк мы хотим задать условную вероятность P(X | T) , то есть условную вероятность наблюдаемых переменных x1 , x2 , x3 при заданных значениях скрытых переменных t1 , t2 и параметра time .
Перед вводом непосредственно самих наблюдений с помощью выражения мы определяем общий закон для наблюдаемых переменных 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 в качестве основного используется алгоритм Метрополиса-Гастингса, который относится к методам Монте-Карло по схеме Марковских цепей. Под обобщенным выводом в данном случае понимается то, что алгоритм может быть применен к любым вероятностным программам, написанным на данном вероятностном языке программирования.
В видео, прикрепленном ниже, можно посмотреть на происходящий статистический вывод в данной модели.
и Эта публикация является первой частью краткого вступления с иллюстрациями в вероятностное программирование , которое является одним из современных прикладных направлений машинного обучения и искусственного интеллекта. Во время написания этой публикации я с радостью обнаружил, что на Хабрахабре совсем недавно уже была , хотя, к сожалению, в русскоговоряющем Интернете пока мало материалов на эту тему.Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.
Вероятностное программирование я люблю определять как компактный , композиционный способ представления порождающих вероятностных моделей и проведения статистического вывода в них с учетом данных с помощью обобщенных алгоритмов. Хотя вероятностное программирование не вносит много фундаментального нового в теорию машинного обучения, этот подход привлекает своей простотой: «вероятностные порождающие модели в массы!»
Например, если у нас есть мальчик Вася, и мы знаем где он находится, куда он бросает мяч и каковы внешние условия (например, сила ветра), мы узнаем, какое окно он, к сожалению, разобьет в здании школы. Для этого достаточно симулировать простые законы школьной физики, которые легко можно записать в виде алгоритма.
Например, в случае с мальчиком Васей, зная то, какое окно он разбил, и имея априорные знания о том, около какого окна он и его друзья обычно играют в футбол, и зная прогноз погоды на этот день, мы хотим узнать апостериорные распределение местоположения мальчика Васи: откуда же он бросал мяч?
Итак, зная выходные данные, мы заинтересованы в том, чтобы узнать наиболее вероятные значения скрытых, неизвестных параметров.
В рамках машинного обучения рассматриваются в том числе порождающие вероятностные модели. В рамках порождающих вероятностных моделей модель описывается как алгоритм, но вместо точных однозначных значений скрытых параметров и некоторых входных параметров мы используем вероятностные распределениях на них.
Существует более 15 языков вероятностного программирования, перечень с кратким описанием каждого из них можно найти . В данной публикации приведен пример кода на вероятностных языках Venture /Anglican , который имеют очень схожий синтаксис и которые берут свое начало от вероятностного языка Church . Church в свою очередь основан на языке «обычного» программирования Lisp и Scheme. Заинтересованному читателю крайне рекомендуется ознакомиться с книгой , являющейся одним из лучших способов начать знакомство с языком «обычного» программирования Scheme.
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 .
В вероятностных языках программирования выражение вызова функции принято разделять на три разных вида:
Перед вводом непосредственно самих наблюдений с помощью выражения мы определяем общий закон для наблюдаемых переменных 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 в качестве основного используется алгоритм Метрополиса-Гастингса, который относится к методам Монте-Карло по схеме Марковских цепей. Под обобщенным выводом в данном случае понимается то, что алгоритм может быть применен к любым вероятностным программам, написанным на данном вероятностном языке программирования.
В видео, прикрепленном ниже, можно посмотреть на происходящий статистический вывод в данной модели.
В самом начале у нас нет данных, поэтому мы видим априорное распределение прямых. Добавляя точку за точкой (таким образом, элементы данных), мы видим элементы выборки из апостериорного распределения.
На этом мы закончим первую часть данного вступления в вероятностное программирование.
Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.
Вероятностное программирование я люблю определять как компактный , композиционный способ представления порождающих вероятностных моделей и проведения статистического вывода в них с учетом данных с помощью обобщенных алгоритмов. Хотя вероятностное программирование не вносит много фундаментального нового в теорию машинного обучения, этот подход привлекает своей простотой: «вероятностные порождающие модели в массы!»
Например, если у нас есть мальчик Вася, и мы знаем где он находится, куда он бросает мяч и каковы внешние условия (например, сила ветра), мы узнаем, какое окно он, к сожалению, разобьет в здании школы. Для этого достаточно симулировать простые законы школьной физики, которые легко можно записать в виде алгоритма.
Например, в случае с мальчиком Васей, зная то, какое окно он разбил, и имея априорные знания о том, около какого окна он и его друзья обычно играют в футбол, и зная прогноз погоды на этот день, мы хотим узнать апостериорные распределение местоположения мальчика Васи: откуда же он бросал мяч?
Итак, зная выходные данные, мы заинтересованы в том, чтобы узнать наиболее вероятные значения скрытых, неизвестных параметров.
В рамках машинного обучения рассматриваются в том числе порождающие вероятностные модели. В рамках порождающих вероятностных моделей модель описывается как алгоритм, но вместо точных однозначных значений скрытых параметров и некоторых входных параметров мы используем вероятностные распределениях на них.
Существует более 15 языков вероятностного программирования, перечень с кратким описанием каждого из них можно найти . В данной публикации приведен пример кода на вероятностных языках Venture /Anglican , который имеют очень схожий синтаксис и которые берут свое начало от вероятностного языка Church . Church в свою очередь основан на языке «обычного» программирования Lisp и Scheme. Заинтересованному читателю крайне рекомендуется ознакомиться с книгой , являющейся одним из лучших способов начать знакомство с языком «обычного» программирования Scheme.
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 .
В вероятностных языках программирования выражение вызова функции принято разделять на три разных вида:
Перед вводом непосредственно самих наблюдений с помощью выражения мы определяем общий закон для наблюдаемых переменных 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.)
В самом начале у нас нет данных, поэтому мы видим априорное распределение прямых. Добавляя точку за точкой (таким образом, элементы данных), мы видим элементы выборки из апостериорного распределения.
На этом мы закончим первую часть данного вступления в вероятностное программирование.
Сегодня мы публикуем внеочередной перевод — это будет обзорная статья блистательного Ноэля Уэлша о принципах вероятностного программирования. Статья публикуется по заявкам читателей, которые задают нашему блогу все более высокую планку — и это, безусловно, здорово!
Надеюсь, этих кратких примеров достаточно, и вы ухватили идею вероятностных моделей. Можно представить себе и множество других генеративных процессов - например, свойства небесного тела влияют на то, в каком виде мы его наблюдаем, поведение пользователя в онлайне зависит от его интересов, а деятельность НКО влияет на ситуацию со здравоохранением в том регионе, где действует такая организация.
Генеративные модели хорошо работают в случаях, когда у нас есть априорные знания об устройстве мира, и мы можем воспользоваться ими при построении модели. Работать с ними очень весело, поскольку они позволяют создавать фиктивные данные, например, автоматически сгенерированные научные статьи - и тем самым смущать и забавлять наших коллег.
Когда мы создали вероятностную модель (и вдоволь поприкалывались с липовыми данными), эту модель можно использовать для логического вывода. Логический вывод - это процесс «обратной перемотки модели». Мы смотрим на реальные данные, которые удалось наблюдать, и пытаемся догадаться, как могла бы выглядеть ситуация, недоступная для наблюдения. Например, можно воспользоваться текстом документа и попытаться выяснить, какой теме он посвящен, либо собрать астрономические данные и попытаться определить, какие звездные системы с наибольшей вероятностью пригодны для жизни. Поскольку мы не можем с уверенностью судить о состоянии этих ненаблюдаемых элементов нашей модели, можно построить вероятностное распределение всех возможностей. Создание такого распределения как раз и отличает байесовский вывод от альтернатив - например, от метода максимального правдоподобия, позволяющего выявить всего одно состояние ненаблюдаемых свойств.
Зачем нужно вероятностное программирование
Мы вкратце описали генеративные модели и проблему байесовского вывода. Эта область статистики и машинного обучения давно изучается, и со временем исследователи заметили ряд моментов:
Как было бы здорово, если бы можно было сделать алгоритм логического вывода, исходя лишь из описания модели. Ситуацию можно сравнить с программированием на ассемблере и на высокоуровневом языке. Пользуясь ассемблером, мы все оптимизируем вручную, реализуем собственные и управляющие структуры и т.д., в контексте конкретной проблемы, стоящей перед нами. То же самое происходит при создании специального алгоритма логического вывода для конкретной генеративной модели. При программировании на высокоуровневом языке мы пользуемся готовыми конструкциями, которые компилятор сам переводит на ассемблер. Продуктивность работы значительно повышается ценой небольшого снижения машинной производительности (чего мы зачастую даже не замечаем). Цель вероятностного программирования - точно такая.
Конечно же это монада!
Кажется, что цель вероятностного программирования стоящая и благородная, но, чтобы ее достичь, нужно для начала понять, как структурировать наши генеративные модели. Опытного программиста-функциональщика не должно удивлять, что для этого мы воспользуемся монадой. Сейчас объясню, как именно.
Вернемся к примеру с генеративной моделью для создания документа. Чтобы создать документ, нужно:
Можно аннотировать эту модель типами, чтобы показать, как может решаться проблема. При помощи Distribution[A] представим распределение по типу A. Теперь документ генерируется так:
(Здесь мы пытаемся сбалансировать простоту и точность, поэтому наша модель не учитывает грамматику или количество слов, из которых состоит документ. Возможно, у вас получится ее дополнить, но, если запутаетесь - познакомьтесь с моим докладом, где представлен более простой и полный пример.)
Основная часть этой модели заключается в соединении Distribution и Topic => Distribution для создания Distribution , из которого можно построить документ. Кстати, чем нужно заменить??? , чтобы следующее тождество соблюдалось?
Distribution ??? Topic => Distribution = Distribution
Ответ — flatMap , то есть, у нас есть монада. (Можете сами убедиться, что и законы монад тоже соблюдаются, однако, в данном случае нам нужно определить семантику flatMap . См. ниже.)
Если вы когда-либо работали со ScalaCheck или подобными системами - то, значит, пользовались монадой безопасности.
Построение алгоритмов логического вывода
Существует много способов реализовать монаду вероятности. Если мы имеем дело лишь с дискретными доменами, то можно все представить внутри предметной области как List[(A, Probability)] (где Probability может быть псевдонимом типа Double) и в точности вычислять результаты. В реальных приложениях польза от такого подхода невелика, поскольку нам, скорее всего, придется иметь дело со сплошными доменами, либо дискретными, но все равно крупными. Тогда размер представления в каждом flatMap будет расти экспоненциально. Пример реализации показан .
Можно использовать представление, основанное на выборке. Такой подход работает со сплошными доменами, и пользователь может создать столько образцов, сколько заблагорассудится - для достижения желаемой точности. Однако, такой вариант все равно неидеален. Алгоритмы логического вывода исследуются много лет, эта работа напоминает оптимизацию компиляторов, а нам бы хотелось создать такую систему, которая запускала бы вероятностные механизмы для анализа структуры программы и применяла к полученным результатам оптимальный алгоритм логического вывода. Точно как и при работе с компилятором, мы выражаем вероятностную программу в виде абстрактного синтаксического дерева, которым затем могут манипулировать алгоритмы оптимизации.
Теперь можно приступать к построению алгоритмов логического вывода, и именно здесь я самоустраняюсь от объяснений, по двум причинам: во-первых, полагаю, что читатель - не профи в машинном обучении, и обсуждать алгоритмы логического вывода ему будет не слишком интересно, а во-вторых, что, на самом деле, важнее - пока это передний край исследований. В современных системах реализуются обобщенные алгоритмы логического вывода, которые, однако, почти не приспособлены для проблемно-ориентированных оптимизаций. Общий принцип, как и при работе с компиляторами, таков: чем больше информации вы сохраняете, тем больше можете оптимизировать. В то же время, большинство оптимизаций полезны лишь в немногих программах. Во многом остается открытым вопрос, насколько можно полагаться на обобщенные алгоритмы логического вывода и на вычислительную мощность, чтобы такой вывод получался достаточно быстрым, и насколько стоит усердствовать со сложной математикой ради оптимизации конкретных случаев.
Заключение и дальнейшая работа
Я очень воодушевлен вероятностным программированием, поскольку, полагаю, оно позволяет радикально упростить логический вывод, и это пригодится в очень многих сферах - несколько примеров я уже привел выше. В большинстве предметных областей вопрос времени не так критичен, поэтому меня более интересует исследование обобщенных алгоритмов логического вывода и параллельных/распределенных реализаций, нежели сложная математика. Однако, любые вещи я люблю сначала обкатать на практике, и поэтому ищу людей, которым требуется решать реальные задачи.
Кроме того, вероятностное программирование изрядно пересекается с моими интересами в сфере машинного обучения и языков программирования. Если вы заинтересовались - вот
Посмотрело: 446
Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.
Вероятностное программирование я люблю определять как компактный , композиционный способ представления порождающих вероятностных моделей и проведения статистического вывода в них с учетом данных с помощью обобщенных алгоритмов. Хотя вероятностное программирование не вносит много фундаментального нового в теорию машинного обучения, этот подход привлекает своей простотой: «вероятностные порождающие модели в массы!»
Например, если у нас есть мальчик Вася, и мы знаем где он находится, куда он бросает мяч и каковы внешние условия (например, сила ветра), мы узнаем, какое окно он, к сожалению, разобьет в здании школы. Для этого достаточно симулировать простые законы школьной физики, которые легко можно записать в виде алгоритма.
Например, в случае с мальчиком Васей, зная то, какое окно он разбил, и имея априорные знания о том, около какого окна он и его друзья обычно играют в футбол, и зная прогноз погоды на этот день, мы хотим узнать апостериорные распределение местоположения мальчика Васи: откуда же он бросал мяч?
Итак, зная выходные данные, мы заинтересованы в том, чтобы узнать наиболее вероятные значения скрытых, неизвестных параметров.
В рамках машинного обучения рассматриваются в том числе порождающие вероятностные модели. В рамках порождающих вероятностных моделей модель описывается как алгоритм, но вместо точных однозначных значений скрытых параметров и некоторых входных параметров мы используем вероятностные распределениях на них.
Существует более 15 языков вероятностного программирования, перечень с кратким описанием каждого из них можно найти . В данной публикации приведен пример кода на вероятностных языках / , который имеют очень схожий синтаксис и которые берут свое начало от вероятностного языка . Church в свою очередь основан на языке «обычного» программирования Lisp и Scheme. Заинтересованному читателю крайне рекомендуется ознакомиться с книгой , являющейся одним из лучших способов начать знакомство с языком «обычного» программирования Scheme.
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 .
В вероятностных языках программирования выражение вызова функции принято разделять на три разных вида:
Перед вводом непосредственно самих наблюдений с помощью выражения мы определяем общий закон для наблюдаемых переменных 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 в качестве основного используется алгоритм Метрополиса-Гастингса, который относится к методам Монте-Карло по схеме Марковских цепей. Под обобщенным выводом в данном случае понимается то, что алгоритм может быть применен к любым вероятностным программам, написанным на данном вероятностном языке программирования.
В видео, прикрепленном ниже, можно посмотреть на происходящий статистический вывод в данной модели.
В самом начале у нас нет данных, поэтому мы видим априорное распределение прямых. Добавляя точку за точкой (таким образом, элементы данных), мы видим элементы выборки из апостериорного распределения.
На этом мы закончим первую часть данного вступления в вероятностное программирование.
