Ймовірнісний програмування - ключ до штучного інтелекту?

Трохи води

Вже більше півтора років тому пройшла новина про те, що «DARPA має намір здійснити революцію в машинному навчанні». Звичайно, DARPA лише виділила гроші на дослідницьку програму, пов'язану з імовірнісним програмуванням. Саме ж ймовірнісний програмування існує і розвивається без DARPA досить давно, причому дослідження ведуться, як у провідних університетах, таких як MIT, так і у великих корпораціях, таких як Microsoft. І зовсім не даремно DARPA, Microsoft, MIT і т. д. звертають пильну увагу на цю ділянку, адже вона по-справжньому перспективна для машинного навчання, а, може, і для штучного інтелекту в цілому. Кажуть, що ймовірнісний програмування для машинного навчання буде грати ту ж роль, що і високорівневі мови для звичайного програмування. Ми б привели іншу паралель — з роллю Прологу, яку він зіграв для старого доброго ІІ. Ось тільки в Рунеті по даній темі досі можна знайти лише поодинокі посилання, і то в основному містять лише опису загальних принципів. Можливо, це пов'язано з тим, що потенціал імовірнісного програмування ще тільки почав розкриватися і воно не стало основним трендом. Однак на що ж здатні або будуть здатні імовірнісні мови?

Можна виділити два основних класу імовірнісних мов програмування — це мови, які допускають завдання генеративних моделей тільки у формі Байєсівських мереж (або інших графічних імовірнісних моделей), або Тьюринг-повні мови.

Типовим представником перших є Infer.NET, що розробляється Microsoft. У ньому завдяки використанню в якості генеративних моделей Байесовких мереж виявляється можливим застосовувати відомі для них ефективні методи виведення. Природно, використання добре відомого класу моделей з відомими методами виведення не призводить до можливості вирішення якихось принципово нових завдань (і навіть такі генеративні моделі, як мережі глибокого навчання на основі обмежених машинах Больцмана виявляються не представимы в таких мовах), але дає цілком практичний інструмент. Як кажуть розробники, з використанням цього інструмента можна за пару годин реалізувати нетривіальну імовірнісну модель, таку як повна Байєсова версія аналізу головних компонент, яка буде займати всього кілька десятків рядків коду і для якої окрема реалізація ефективної процедури виведення на звичайному мові зажадала б помітно більшого обсягу знань та кількох тижнів роботи. Таким чином, за рахунок імовірнісного програмування використання графічних моделей стає набагато більш простим і доступним.

Набагато більшим потенціалом, однак, мають Тьюринг-повні імовірнісні мови. Вони дозволяють вийти за рамки того класу задач, що існуючі методи машинного навчання вже вміють вирішувати. Природно, в таких мовах виникає проблема ефективності виведення, яка поки далека від вирішення, що призводить до поганої масштабованості на завдання реального світу. Однак цей напрямок активно розвивається, існує ряд робіт, що показують як в імовірнісних мови загального призначення досягти ефективного виводу для цікавих практичних завдань. Можна сподіватися, що в найближчому майбутньому ці рішення стануть доступними для використання в конкретних мовах. Крім того, Тьюринг-повні імовірнісні мови вже зараз виявляються досить корисними в дослідженнях, пов'язаних з когнітивним моделюванням і загальним штучним інтелектом. З цих причин ми і розглянемо основні принципи імовірнісного програмування саме на прикладі Тьюринг-повних мов, з яких ми вибрали Черч (Church), що є розширенням мови Лисп (конкретніше, його діалекту — Scheme). Зручність цієї мови (принаймні, в цілях початкового знайомства з ним) полягає в існуванні для нього web-реалізації (web-church), з якої можна експериментувати без установки додаткового програмного забезпечення.

Отже, до справи

Програма на імовірнісному мовою може, на перший погляд, нічим не відрізнятися від програми на звичайній мові. Саме так зроблено в Черче. Як і в звичайному Ліспі, в цій мові можуть бути визначені змінні, функції, виконані детерміновані обчислення. Наприклад, наступна програма задає функцію від одного аргументу, яка підраховує факторіал за рекурсивну формулою n!=n*(n-1)!, і викликає цю функцію для n=10

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


Також в цій мові можуть бути звернення до (псевдо)випадковим функцій. Наприклад, при виконанні виклику (flip 0.3) з ймовірністю 0.3 буде повернуто значення #t, а з імовірністю 0.7 — #f. Така функція елементарно реалізується і в Ліспі
(define (flip p) (< (random) p))
Черч, як і інші імовірнісні мови, містить багато вбудованих функцій, які повертають випадкові значення у відповідності з тим чи іншим розподілом. Наприклад, (gaussian x0 s) повертає речову випадкову величину, розподілену за гауссиане з заданими параметрами. В якості інших реалізованих розподілів ймовірностей зазвичай присутні рівномірний, мультиномиальное, Діріхле, бета, гамма. Всі ці розподілу не так складно реалізувати вручну в звичайній мові, і тут поки що немає принципової відмінності між Черчем і Лиспом.

Однак крім звичайної семантики програма на Черче має ймовірнісної семантикою, в рамках якої вважається, що програма, що містить виклики випадкових функцій, не просто при своєму запуску породжує якісь конкретні значення випадкових величин, але задає розподіл ймовірностей над ними. Так, (gaussian x0 s) — це не просто функція, що повертає деяке конкретне значення випадкової величини, розподіленої за гауссиане, але саме саме гаусівських розподілу розподіл.

Але як отримувати ці розподілу ймовірностей, що задаються програмою? Уявімо, наприклад, програму
(if (flip 0.4) (flip 0.1) (flip 0.6))
тобто з імовірністю 0.4 значення цього виразу — це P(#t)=0.1 і P(#f)=0.9, а з імовірністю 0.6 — P(#t)=0.6 і P(#f)=0.4. Звідки візьметься підсумкове розподіл, що задається цим виразом: P(#t)=0.4 і P(#f)=0.6? Ця імовірнісна семантика найчастіше реалізується через процес семплювання: ми можемо просто багато разів запустити програму і побудувати вибірку результатів її виконання. Таку процедуру, звичайно, також нескладно реалізувати на звичайному мові (і, дійсно, ще Симула-67 таким способом регулярно використовувалася для моделювання стохастичних процесів).

Однак сучасні імовірнісні мови йдуть далі і додають в процес семплювання умова, що накладається на результати виконання програми. Ця ідея веде до найпростішого сэмплированию з відмовами, яка в Черче реалізується функцією rejection-query. Ця функція на вхід приймає імовірнісну програму (як сукупність define), передостаннє вираз в якій обчислює значення, що повертається, а останнє вираз — умова (предикат), який в процесі виконання повинен виявитися істинним. Розглянемо програму

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


rejection-query виконує подану їй програму до тих пір, поки не буде виконано остання умова — тут (or A B) — і повертає (один раз) значення передостаннього вираження — тут B. Щоб отримати вибірку значень, можна скористатися функцією repeat. Також Черч має вбудовані функції для побудови гістограм. Розглянемо дещо розширену програму:

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


При запуску програми ми отримаємо наступний результат: #f — 21%, #t — 79% (цифри від запуску до запуску можуть трохи змінюватися). Цей результат означає, що значення B одно #t з імовірністю трохи менше 0.8. Звідки взялася ця ймовірність, якщо в програмі B — це бінарна випадкова величина, для якої P(#t)=0.6? Очевидно, справа в накладенні умови: (or A B). В процесі семплювання ми приймаємо такі значення B, що вірно або A, або B Фактично, ми вважаємо апостериорную ймовірність P(B|A+B). Можна було б скористатися правилом Байєса для того, щоб обчислити цю ймовірність вручну:

P(B|A+B) = P(A+B|B)P(B)/P(A+B) =
=(P(A|B)+P(B|B)-P(A|B)P(B|B))P(B)/(P(A)+P(B)-P(A)P(B))=
=(P(A)+1-P(A)P(B)/(P(A)+P(B)-P(A)P(B))=0.6/(0.4+0.6-0.4*0.6)=0.789.

Проте вже для такої елементарної програми ручне застосування правила Байєса вимагає деякого часу, а для нетривіальних програм аналітично обчислити значення може і зовсім не вийти.

Отже, семплірування дозволяє нам обчислювати апостеріорні ймовірності цікавлять нас випадкових величин при накладенні тих чи інших умов. Воно замінює правило Байєса, широко використовуване в машинному навчанні для вибору моделей або виконання прогнозів. При цьому запис програми на імовірнісному мовою для багатьох людей може виявитися набагато зрозуміліше, ніж застосування правила Байєса. Звичайно, саме режекторное семплірування досить просто можна реалізувати на звичайному мові програмування, але імовірнісні мови цим не обмежуються.
У Черче, зокрема, реалізована інша функція семплювання — enumeration-query. Запустимо програму

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


На виході ми отримаємо: ((#t #f) (0.7894736842105263 0.2105263157894737)). Тут виведені точні значення (звичайно, зі знижкою на кінцеву розрядну сітку) ймовірностей P(B|A+B). enumeration-query вже не просто запускає багато разів програму, але аналізує шляхи її виконання і перебирає всі можливі значення випадкових величин з урахуванням їх ймовірностей. Звичайно, таке «семплірування» буде працювати, тільки коли безліч можливих комбінацій значень випадкових змінних не надто велике.

Є в Черче і більш просунута заміна режекторному сэмплированию на основі MCMC (Monte Carlo Markov Chains), а саме Metropolis Hastings алгоритм, звідки і назва процедури — mh-query. Ця процедура запиту відразу формує заданий число семплів (а також отримує на вхід один додатковий параметр — лад). Ця процедура також нетривіальна в реалізації, так що використання готового імовірнісного мови (а не власна реалізація простих процедур семплування на звичайному мові) набуває сенс.

Однак головне, що дає імовірнісне програмування, — це стиль мислення.

Від азів до застосування

Різні розробники знаходять різні застосування імовірнісному програмування. Багато застосовують його безпосередньо для рішення завдань машинного навчання. Автори мови Черч, Noah D. Goodman and Joshua B. Tenenbaum, у своїй web-книзі «Probabilistic Models of Cognition» показують застосування імовірнісного програмування для когнітивного моделювання. Також відомо, як рішення задач планування зручно представляти у термінах виведення в імовірнісних мовами. Воно також виявляється придатним для представлення знань і виведення над ними, а також для завдань машинного сприйняття (в тому числі, розпізнавання зображень). Всі ці програми поки що більш або менш розрізнені, але наявність загального фреймворку для всіх них свідчить про те, що ймовірнісний програмування може стати «теорією великого об'єднання» для ІІ. Подивимося на найпростіші приклади можливого використання.

Одним з найбільш класичних прикладів застосування експертних систем є медична діагностика. Зокрема, система MYCIN була побудована на системі правил виду:

Rule 52:
If
  1. THE SITE OF THE CULTURE IS BLOOD
  2. THE GRAM OF THE ORGANISM I S NEG
  3. THE MORPHOLOGY OF THE ORGANISM IS ROD
  4. THE BURN OF THE PATIENT IS SERIOUS
Then there is weakly suggestive evidence (0.4) that
  1. THE IDENTITY OF THE ORGANISM IS PSEUDOMONAS


Очевидно, правила такого виду добре описуються на мові типу Черч. При цьому немає необхідності ще й реалізовувати процедуру виведення — достатньо просто записати систему правил. Наведемо приклад зі згаданої книги «Probabilistic Models of Cognition»:

(define samples
(mh-query 1000 100
(define lung-cancer (flip 0.01))
(define TB (flip 0.005))
(define cold (flip 0.2))
(define stomach-flu (flip 0.1))
(define other (flip 0.1))

(define cough (or (and cold (flip 0.5)) (and lung-cancer (flip 0.3)) (and TB (flip 0.7)) (and other (flip 0.01))))
(define fever (or (and cold (flip 0.3)) (stomach and-flu (flip 0.5)) (and TB (flip 0.2)) (and other (flip 0.01))))
(define chest-pain (or (and lung-cancer (flip 0.4)) (and TB (flip 0.5)) (and other( flip 0.01))))
(define shortness-of-breath (or (and lung-cancer (flip 0.4)) (and TB (flip 0.5)) (and other (flip 0.01))))

(list lung-cancer TB)
(and cough fever chest-pain shortness-of-breath)))
(hist samples "Joint inferences for lung cancer and TB")


У цій програмі визначаються апріорні ймовірності появи у хворого раку легень, туберкульозу, застуди і т. д. Далі визначаються ймовірності спостереження кашлю, спека, болі в грудях і туги дихання при тих чи інших захворюваннях. Повертається величина — це пара бульових значень, чи є у пацієнта рак та/або туберкульоз. І, нарешті, умова — це сукупність спостережуваних симптомів (тобто семплірування проводиться за умови, що значення всіх змінних — cough fever chest-pain shortness-of-breath — #t).

Результат виконання програми буде мати наступний вигляд: (#f #f) — 4%, (#f #t) — 58%, (#t #f) — 37%, (#t #t) — 1%.
Нескладно зробити, щоб samples була функцією, в яку подається перелік симптомів, який далі в mh-query використовується для семплювання, що дасть можливість ставити діагнози різних пацієнтам. Звичайно, цей приклад сильно спрощений, але видно, що в стилі імовірнісного програмування цілком можна представляти знання та робити висновок над ними.

Природно, можна вирішувати і задачі машинного навчання. Їх відмінність буде лише в тому, що невідомими величинами будуть параметри самої моделі, а в якості умови для семплювання буде виступати генерація цією моделлю навчальної вибірки. Наприклад, в наведеній вище програмі ми б числа в рядках виду (define lung-cancer (flip 0.01)) могли б замінити на змінні, які самі б задавалися як випадкові, наприклад (define p-lung-cancer (uniform 0 1)), а далі для кожного пацієнта з навчальної вибірки значення lung-cancer вже визначалося б з імовірністю p-lung-cancer.

Розглянемо цю можливість на простому прикладі оцінювання параметрів многочлена з набору точок. У наступній програмі функція calc-poly обчислює значення многочлена з параметрами ws в точці x. Функція generate застосовує calc-poly до кожного значення із заданого списку xs і повертає список відповідних ординат. Процедура noisy-equals? «приблизно» порівнює два заданих значень (якщо ці значення рівні, то функція повертає #t з ймовірністю 1; якщо ж вони не рівні, то чим більше вони відрізняються, тим з меншою ймовірністю вона поверне #t).

(define (calc-poly x ws)
(if (null? ws) 0
(+ (car ws) (* x (calc-poly x (cdr ws))))))

(define (generate xs ws)
(map (lambda (x) (calc-poly x ws)) xs))

(define (noisy-equals? x y)
(flip (exp (* -3 (expt (- x y) 2)))))

(define (samples xs ys)
(mh-query 1 100
(define n-coef 4)
(define ws (repeat n-coef (lambda () (gaussian 0 3))))
ws
(all (map noisy-equals? (generate xs ws) ys))))
(samples'(0 1 2 3 4) '(0.01 1.95 6.03 12.01 20.00))


Всередині виклику mh-query параметр n-coef визначає число коефіцієнтів в многочлене (тобто ступінь мінус один); ws — це список, що складається з випадкових величин, згенерованих у відповідності з нормальним розподілом. Значення, що повертається — список параметрів многочлена. Умова для семплювання — «наближений» рівність всіх заданих значень ys всім ординатам, породженим многочленом при даних ws. Тут ми запитуємо всього одну реалізацію, яка проходить за умовою (оскільки будувати гістограму для вектора параметрів не дуже зручно). Результатом цього запиту може бути, наприклад, список (2.69 1.36 0.53 -0.10), який визначає многочлен 2.69+1.36 x+0.53 x^2-0.10 x^3.

Взагалі, висновок на моделях з речовими параметрами — не найсильніша сторона мови Черч (але не варто вважати глобальним недоліком імовірнісного програмування взагалі). Тим не менш, на цьому прикладі mh-query-сяк працює. Щоб переконатися в цьому, замість визначення значень параметрів в запиті можна попросити повертати передбачення в деякій точці. Перепишемо останній фрагмент коду:

(define (samples xs ys)
(mh-query 100 100
(define n-coef 4)
(define ws (repeat n-coef (lambda () (gaussian 0 3))))
(calc-poly 5 ws)
(all (map noisy-equals? (generate xs ws) ys))))
(hist (samples'(0 1 2 3 4) '(0.01 1.95 6.03 12.01 20.00)))


Тобто ми запитуємо найбільш вірогідне (при наявних даних) значення в точці x=5. При різних запусках максимум гістограми, на жаль, буде припадати на кілька окремі значення (метод MCMC, теоретично, гарантує сходження до істинного розподілу, але лише в межі), але зазвичай ці значення будуть досить вразумительными. Варто помітити, що тут ми «безкоштовно» (заміною однієї строчки) отримали повне байесовское передбачення: замість вибору кращої моделі і передбачення лише по ній, ми отримали апостеріорне розподіл значень в точці x=5, усереднене відразу з безлічі моделей з урахуванням їх власних ймовірностей.
Але і це ще не все. Знову ж таки, заміною однієї строчки — (define n-coef 4) -> (define n-coef (random-integer 5)) ми можемо зробити автоматичний вибір між моделями з різним числом параметрів. Причому семплірування величини n-coef показує (хоча і не дуже стабільно), що найбільш ймовірним значенням є n-coef=3 (тобто парабола, яка закладена в заданий набір точок). При такій модифікації стає більш стабільним і передбачення. Іншими словами, не виникає ефекту перенавчання! Чому ж не вибираються многочлени більш високого ступеня, адже вони можуть точніше проходити до заданих точках? Справа в тому, що при сэмплировании «вгадати» відповідні значення параметрів многочлена меншою мірою простіше, ніж многочлена більш високого ступеня, тому ймовірність породити такі параметри, які пройдуть перевірку, для многочлена другого степеня вище, ніж для третьої. У той же час, многочлен першого ступеня буде давати великі відхилення, для яких ймовірність спрацьовування noisy-equals? буде сильно знижуватися.

Подивимося ще на одне застосування, яке в рамках імовірнісного програмування може здатися несподіваним. Це рішення «дедуктивних» завдань. Візьмемо наведену на початку функцію обчислення факторіала, але замість виклику її з фіксованим значенням будемо вважати, що аргумент — випадкова змінна, але саме значення факторіала накладено обмеження:

(define (f n)
(if (= n 0) 1 (* n (f (- n 1)))))
(enumeration-query
(define n (random-integer 20))
n
(equal? (f n) 120))


В якості відповіді ми побачимо n=5 з ймовірністю 1. Якщо ж ми замість 120 задамо 100, то програма не зациклиться (на відміну від випадку використання rejection-query або mh-query, що можна вважати їх недоліком), а просто поверне порожня множина. Можна поставити в якості умови і не тотожність, а якесь інше обмеження.

Таким же чином можна вирішувати і більш складні завдання. Припустимо, ми хочемо вирішити задачу про суму підмножин: в ній треба з заданої множини чисел знайти таке підмножина, сума в якому дорівнює заданому числу (зазвичай в якості цього числа береться 0 і потрібно, щоб підмножина було не порожнім; але щоб позбутися від перевірки на нетривіальність рішення, ми візьмемо ненульову суму). Здавалося б, причому тут ймовірнісний програмування? Але випадкові величини — це просто невідомі величини (для яких задані апріорні ймовірності). У будь-яких завданнях нам потрібно знайти щось невідоме, в тому числі і в задачі про суму підмножин. Подивимося на наступну елементарну програму (її можна було б навіть ще спростити, записавши summ через fold).

(define (solution xs v)
(rejection-query
(define ws (repeat (length xs) flip))
(define (summ xs ws)
(if (null? xs) 0
(+ (if (car ws) (car xs) 0) (summ (cdr xs) (cdr ws)))))
ws
(equal? (summ xs ws) v)))
(solution'(-1 3 7 5 -9 -1) 1)


Тут ws — список випадкових булевих значень. Процедура summ обчислює суму елементів списку xs, для яких відповідні елементи списку ws істинні. Далі запитується значення ws, для яких виконується умова рівності отриманої суми заданому числу v. Запустивши цю програму, можна отримати такий результат: (#f #t #t #f #t #f), який, звичайно, є правильним (так як 3+7-9=1).

Природно, Черч не робить дива і при підвищенні розмірності цієї задачі він з нею не впорається. Однак не може не дивувати те, що настільки різні завдання ІЇ можуть бути хоча б поставлені (і частково вирішено) з використанням одного і того ж мови. Ну, а проблема ефективного виведення як була, так і залишається. В імовірнісних мовах вона хоча б виділяється в чистому вигляді.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.