Является Ли Вероятностное Программирование Ключом К Искусственному Интеллекту?

Немного воды Полтора года назад появилась новость о том, что «DARPA намерено произвести революцию в машинном обучении» .

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

Само вероятностное программирование существует и развивается без DARPA довольно долгое время, а исследования проводятся как в ведущих университетах, таких как MIT, так и в крупных корпорациях, таких как Microsoft. И не зря DARPA, Microsoft, MIT и др.

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

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

Мы бы провели еще одну параллель — с ролью Пролога, которую он сыграл за старый добрый ИИ.

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

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

Однако на что способны или будут способны вероятностные языки? Можно выделить два основных класса вероятностных языков программирования: языки, позволяющие задавать генеративные модели только в виде байесовских сетей (или других графических вероятностных моделей), или тьюринг-полные языки.

Типичным представителем первого является Infer.NET, разработанный Microsoft. В ней благодаря использованию байесовских сетей в качестве генеративных моделей становится возможным использовать известные для них эффективные методы вывода.

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

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

Однако тьюринг-полные вероятностные языки имеют гораздо больший потенциал.

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

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

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

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

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

По этим причинам мы рассмотрим основные принципы вероятностного программирования на примере Тьюринг-полных языков, из которых мы выбрали Чёрча, который является расширением языка Лисп (точнее, его диалекта — Scheme).

Удобство этого языка (по крайней мере, для целей первоначального знакомства с ним) заключается в наличии для него веб-реализации (веб-церкви), с которой можно экспериментировать без установки дополнительного программного обеспечения.

Итак, приступим к делу

Именно это и делается в Церкви.

Как и в обычном Лиспе, на этом языке можно определять переменные и функции, а также выполнять детерминированные вычисления.

Например, следующая программа определяет функцию с одним аргументом, которая вычисляет факториал по рекурсивной формуле n!=n*(n–1)!, и вызывает эту функцию для n=10.

 
         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.
 

Например, при вызове (переворот 0,3) существует вероятность 0,3, что будет возвращено значение #t, и вероятность 0,7, что будет возвращено значение #f. Эту функцию можно легко реализовать в Лиспе как

(define (f n) (if (= n 0) 1 (* n (f (– n 1))))) (f 10)

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

Например, (gaussian x0 s) возвращает реальную случайную величину, распределенную по гауссу с заданными параметрами.

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

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

Над ними.

Таким образом, (Gaussian x0 s) — это не просто функция, возвращающая какое-то конкретное значение случайной величины, распределенной по гауссу, но именно само распределение Гаусса.

Но как получить эти распределения вероятностей, заданные программой? Представим себе, например, программу

(define (flip p) (< (random) p))

То есть с вероятностью 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? Эта вероятностная семантика часто реализуется посредством процесса выборки: мы можем просто запустить программу много раз и построить выборку результатов ее выполнения.

Такую процедуру, конечно, легко реализовать и на обычном языке (и действительно, Simula-67 регулярно использовалась таким образом для моделирования случайных процессов).

Однако современные вероятностные языки идут дальше и добавляют в процесс выборки условие, которое накладывается на результаты выполнения программы.

Эта идея приводит к простейшей выборке с отклонениями, которая в Чёрче реализована функцией запроса-отклонения.

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

Давайте посмотрим на программу

(if (flip 0.4) (flip 0.1) (flip 0.6))

Rejection-query выполняет заданную ему программу до тех пор, пока не будет выполнено последнее условие — здесь (или A B) — и возвращает (один раз) значение предпоследнего выражения — здесь B. Чтобы получить выборку значений, можно использовать функцию повтора .

Черч также имеет встроенные функции для построения гистограмм.

Давайте посмотрим на немного расширенную программу:

(rejection-query (define A (flip 0.4)) (define B (flip 0.6)) B (or A B))

При запуске мы получим следующий результат: #f — 21%, #t — 79% (цифры могут немного меняться от запуска к запуску).

Этот результат означает, что значение B равно #t с вероятностью чуть меньше 0,8. Откуда взялась эта вероятность, если в программе Б это двоичная случайная величина, для которой P(#t)=0,6? Очевидно, речь идет о наложении условия: (или A B).

В процессе выборки мы принимаем только такие значения B, которые либо A, либо B сами по себе являются истинными.

Фактически мы рассматриваем апостериорную вероятность P(B|A+B).

Можно использовать правило Байеса, чтобы вычислить эту вероятность вручную:

(define (get-sample) (rejection-query (define A (flip 0.4)) (define B (flip 0.6)) B (or A B))) (hist (repeat 1000 get-sample))

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

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

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

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

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

В Чёрче, в частности, реализована ещё одна функция выборки — 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 (Цепи Монте-Карло Маркова), а именно алгоритм Metropolis Hastings, отсюда и название процедуры — mh-query. Эта процедура запроса сразу генерирует заданное количество выборок (а также получает на вход один дополнительный параметр — лаг).

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

Однако главное, что дает вероятностное программирование, — это стиль мышления.

От основ к применению

Многие люди используют его непосредственно для решения задач машинного обучения.

Авторы церковного языка Ной Д.

Гудман и Джошуа Б.

Тененбаум в своей веб-книге «Вероятностные модели познания» показывают использование вероятностного программирования для когнитивного моделирования.

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

Он также оказывается применимым для представления знаний и вывода, а также для задач машинного восприятия (включая распознавание изображений).

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

Давайте рассмотрим простейшие примеры возможного использования.

Одним из наиболее классических примеров использования экспертных систем является медицинская диагностика.

В частности, система MYCIN была построена на системе правил вида: Правило 52: Если

1. САЙТ КУЛЬТУРЫ – КРОВЬ
2. ГРАММ ОРГАНИЗМА ОТР.

3. МОРФОЛОГИЯ ОРГАНИЗМА ПАЛОЧКА
4. ОЖОГ ПАЦИЕНТА СЕРЬЕЗНЫЙ

1. ИДЕНТИЧНОСТЬ ОРГАНИЗМА – PSEUDOMONAS

В этом случае нет необходимости реализовывать процедуру вывода — достаточно просто записать систему правил.

Приведем пример из упомянутой книги «Вероятностные модели познания»:

(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")

Эта программа определяет априорные вероятности развития у пациента рака легких, туберкулеза, простуды и т. д. Далее определяются вероятности наблюдения кашля, лихорадки, боли в груди и одышки при определенных заболеваниях.

Возвращаемое значение — это пара логических значений, указывающих, есть ли у пациента рак и/или туберкулез.

И, наконец, состояние представляет собой набор наблюдаемых симптомов (то есть выборка производится при условии, что значение всех переменных равно кашлю, лихорадке, боли в груди, одышке - #t).

Результат выполнения программы будет следующим: (#f#f) - 4%, (#f#t) - 58%, (#t#f) - 37%, (#t#t) - 1% .

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

Конечно, этот пример сильно упрощен, но понятно, что в стиле вероятностного программирования вполне возможно представить знания и сделать на их основе выводы.

Естественно, проблемы машинного обучения также могут быть решены.

Единственная разница между ними будет заключаться в том, что неизвестными величинами будут параметры самой модели, а условием выборки будет построение этой моделью обучающей выборки.

Например, в программе, представленной выше, мы могли бы заменить числа в строках типа (определить рак легких (перевернуть 0,01)) на переменные, которые сами по себе будут установлены как случайные, например (определить p-рак легких (единообразный 0 1 )) , а затем для каждого пациента из обучающей выборки будет определяться значение рака легких с вероятностью p-рак легких.

Рассмотрим эту возможность на простом примере оценки параметров полинома по набору точек.

В следующей программе функция Calc-poly вычисляет значение многочлена с параметрами ws в точке x. Функция генерации применяет Calc-Poly к каждому значению в заданном списке xs и возвращает список соответствующих ординат. Процедура шумно-равно? «приблизительно» сравнивает два заданных значения (если эти значения равны, то функция возвращает #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) '(0.01 1.95 6.03 12.01 20.00))

Внутри вызова mh-запроса параметр 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-коэффициента показывает (хотя и не очень стабильно), что наиболее вероятным значением является n-коэф = 3 (то есть парабола, вложенная в заданный набор точек).

Благодаря этой модификации прогноз также становится более стабильным.

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

В то же время полином первой степени будет давать большие отклонения, для которых вероятность срабатывания шумно-равна? сильно уменьшится.

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

Это решение «дедуктивных» задач.

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

(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 и требуется что подмножество не пусто; но чтобы избавиться от проверки на нетривиальность решения, возьмем ненулевую сумму).

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

В любой задаче нам нужно найти что-то неизвестное, в том числе и в задаче о сумме подмножеств.

Давайте посмотрим на следующую элементарную программу (ее можно даже упростить, написав сумму через складку).

(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 — список случайных логических значений.

Процедура sum вычисляет сумму элементов списка xs, для которых соответствующие элементы списка ws истинны.

Далее запрашиваются значения ws, для которых выполнено условие равенства полученной суммы заданному числу v. Запустив эту программу, можно получить следующий результат: (#f #t #t #f #t #f), что, конечно, правильно (поскольку 3+7-9=1).

Естественно, Черч не совершает чуда, и если масштабность этой задачи увеличится, он не сможет с ней справиться.

Однако удивительно, что такие разные проблемы ИИ могут быть сформулированы (и частично решены) на одном и том же языке.

Ну а проблема эффективного производства всегда была и остаётся.

В вероятностных языках оно хотя бы выделяется в чистом виде.

Теги: #вероятностное программирование #машинное обучение #представление знаний #решение задач #программирование

• Новости Партнеров Dynamics Gp: Аспекты Международной Установки

  19 Oct, 24

• Как Писать Как Профессионал: Защитите Свои Навыки Написания Электронных Писем

  19 Oct, 24

• Дрон-Рыбак. Размышления По Теме

  19 Oct, 24

• Акционеры Dream Industries И Создатели Rutube Запустили Систему Аудиорекламы Instreamatic

  19 Oct, 24

• Звук По Сети

  19 Oct, 24

• Первые Шаги В Китай

  19 Oct, 24

• Развитие Инфраструктуры Высокоавтономного Вождения (Had)

  19 Oct, 24

• Еще Один «Урок» По Extjs. Шаблоны Элементов

  19 Oct, 24

• Лауреатов Премии Рунета Объявят 29 Ноября.

  19 Oct, 24

• Опыт Решения Задачи По Созданию Olap-Куба С Использованием C#.

  19 Oct, 24