Ймовірнісний програмування

Вступ
Ця публікація є першою частиною короткого вступу з ілюстраціями ймовірнісний програмування, яке є одним із сучасних прикладних напрямків машинного навчання і штучного інтелекту. Під час написання цієї публікації я з радістю виявив, що на Хабрахабре зовсім нещодавно вже була стаття про імовірнісному програмуванні з розглядом прикладних прикладів з області теорії пізнання, хоча, на жаль, в русскоговоряющем Інтернеті поки мало матеріалів на цю тему.

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

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

«Звичайне» програмування
Для знайомства з імовірнісним програмування давайте спочатку поговоримо про «звичайному» програмуванні. В «звичайному» програмуванні основою є алгоритм, зазвичай детермінований, який дозволяє нам з вхідних даних отримати вихідні за чітко встановленими правилами.



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



А тепер ймовірнісний програмування
Однак часто ми знаємо тільки результат, і ми зацікавлені в тому, щоб дізнатися, які невідомі значення привели саме до цього результату? Щоб відповісти на це питання за допомогою теорії математичного моделювання створюється імовірнісна модель, частина параметрів якої не визначені точно.

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



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

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

Існує більше 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 (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 в якості основного використовується алгоритм Метрополіса-Гастінгса, який відноситься до методів Монте-Карло за схемою Марковських ланцюгів. Під узагальненим висновком в даному випадку розуміється те, що алгоритм може бути застосований до будь-яких імовірнісним програмам, написаним на даному імовірнісному мовою програмування.

У відео, прикріпленому нижче, можна подивитися на походить статистичний висновок в даній моделі.



На самому початку у нас немає даних, тому ми бачимо апріорне розподіл прямих. Додаючи точку за точкою (таким чином, елементи даних), ми бачимо елементи вибірки з апостериорного розподілу.

На цьому ми закінчимо першу частину цієї вступу в імовірнісну програмування.

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

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

0 коментарів

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