Модель суміші процесу Діріхле

• 23 Червня, 2014.
• Василіс Врініотис
• . 2 коментарі

Ця публікація в блозі є четвертою частиною серії Кластеризація з моделями сумішей процесу Діріхле. У попередніх статтях ми обговорювали кінцеві моделі суміші Діріхле і взяли межу їх моделі для нескінченних k кластерів, що привело нас до впровадження процесів Діріхле. Як ми бачили, наша мета — побудувати модель суміші, яка не вимагає від нас вказувати кількість k кластерів/компонентів з самого початку. Після представлення різних уявлень процесів Діріхле, тепер настав час фактично використовувати DP для побудови моделі нескінченної суміші, яка дозволить нам виконувати кластеризацію. Метою цієї статті є визначення моделей сумішей процесу Діріхле та обговорення використання китайського ресторанного процесу та відбору проб Гіббса. Якщо ви не читали попередні дописи, настійно рекомендуємо це зробити, оскільки тема є трохи теоретичною і вимагає хорошого розуміння побудови моделі.

Оновлення: Система машинного навчання Datumbox тепер є відкритою та безкоштовною скачати. Перевірте пакет com.datumbox.framework.machinelearning.clustering, щоб побачити реалізацію моделей суміші процесів Діріхле на Java.

1. Визначення моделі суміші процесу Діріхле

Використання процесів Діріхле дозволяє нам мати змішану модель з нескінченними компонентами, яку можна вважати таким, що виводить межу скінченної моделі для k до нескінченності. Припустимо, що у нас є така модель:

Рівняння 1: Модель суміші процесу Діріхле

Де G визначається як та використовується як короткий позначення для яка є дельта-функцією, яка приймає 1 якщо і 0 в інших місцях. θ_i є параметрами кластера, які відбираються з G. Генеративний розподіл F налаштовується параметрами кластера θ_i і використовується для створення x_i спостереження. Нарешті, ми можемо визначити розподіл щільності який є нашим розподілом суміші (зліченна нескінченна суміш) із пропорціями змішування і змішування компонентів .

Малюнок 1: Графічна модель моделі суміші процесу Діріхле

Вище ми бачимо еквівалентну графічну модель DPMM. Г₀ є базовим розподілом DP, і його зазвичай вибирають спряженим перед нашим генеративним розподілом F, щоб спростити обчислення та використати привабливі математичні властивості. α є скалярним гіперпараметром процесу Діріхле і впливає на кількість кластерів, які ми отримаємо. Чим більше значення α, тим більше кластерів; чим менше α, тим менше кластерів. Слід зазначити, що значення α виражає сила віри в Г₀. Велике значення вказує на те, що більшість зразків будуть відрізнятися і мати значення, зосереджені на G₀. G — це випадковий розподіл у просторі параметрів Θ, відібраний із DP, який призначає ймовірності параметрам. θ_i є вектором параметрів, який витягується з G-розподілу і містить параметри кластера, F-розподіл параметризований θ_i та x_i - це точка даних, створена генеративним розподілом F.

Важливо відзначити, що θ_i є елементами простору параметрів Θ і вони «налаштовують» наші кластери. Їх також можна розглядати як приховані змінні на x_i які говорять нам, з якого компонента/кластеру x_i звідки і які параметри цього компонента. Таким чином, для кожного х_i що ми спостерігаємо, малюємо θ_i з розподілу G. З кожним розіграшем розподіл змінюється залежно від попередніх виборів. Як ми бачили в схемі урн Блеквелла-Маккуїна, розподіл G можна інтегрувати, а наші майбутні вибори θ_i залежить тільки від Г₀: . Оцінити параметри θi з попередньої формули не завжди можливо, оскільки багато реалізацій (наприклад, китайський ресторанний процес) передбачають перерахування за допомогою експоненціально зростаючий k компонент. Таким чином, використовуються наближені обчислювальні методи, такі як вибірка Гіббса. Нарешті, ми повинні зазначити, що незважаючи на нескінченність k кластерів, кількість активних кластерів є . Таким чином, θ_i буде повторюватися і проявляти ефект кластеризації.

2. Використання китайського ресторанного процесу для визначення моделі нескінченної суміші

Модель, визначена в попередньому сегменті, є математично твердою, проте вона має серйозний недолік: для кожного нового x_i що ми спостерігаємо, ми повинні випробувати новий θ_i з урахуванням попередніх значень θ. Проблема в тому, що в багатьох випадках вибірка цих параметрів може бути складною і дорогою з точки зору обчислень.

Альтернативним підходом є використання китайського ресторанного процесу для моделювання прихованих змінних z_i кластерних завдань. Таким чином замість використання θ_i щоб позначити як параметри кластера, так і призначення кластера, ми використовуємо приховану змінну z_i щоб вказати ідентифікатор кластера, а потім використовувати це значення для призначення параметрів кластера. Як наслідок, нам більше не потрібно робити вибірку θ щоразу, коли ми отримуємо нове спостереження, але замість цього ми отримуємо кластерне призначення шляхом вибірки z_i від CRP. За допомогою цієї схеми новий θ відбирається лише тоді, коли нам потрібно створити новий кластер. Нижче ми представляємо модель цього підходу:

Рівняння 2: Модель суміші з CRP

Вище наведена генеративна модель, яка описує, як дані x_i і створюються кластери. Для виконання кластерного аналізу ми повинні використовувати спостереження x_i і оцінити кластерні призначення z_i.

3. Виведення моделі суміші та вибірка Гіббса

На жаль, оскільки процеси Діріхле непараметричні, ми не можна використовувати EM-алгоритм щоб оцінити приховані змінні, які зберігають кластерні призначення. Для оцінки завдань скористаємося Згорнута вибірка Гіббса.

Згорнута вибірка Гіббса — це простий алгоритм Монте-Карло ланцюга Маркова (MCMC). Це швидко і дозволяє нам інтегрувати деякі змінні під час вибірки іншої змінної. Проте цей алгоритм вимагає від нас вибрати G₀ який є спряженим попереднім генеративного розподілу F, щоб мати можливість аналітично розв’язувати рівняння та мати можливість вибірки безпосередньо з .

Нижче наведено кроки згорнутої вибірки Гіббса, які ми будемо використовувати для оцінки призначень кластерів:

• Ініціалізуйте z_i кластерні призначення випадковим чином
• Повторюйте до зближення
• Виберіть випадковим чином сокиру_i
  
• Залиште іншу z_j фіксується для кожного j≠i:
• Призначте нове значення z_i шляхом розрахунку «ймовірності CRP», яка залежить від z_j та x_j з усіх j≠i:

У наступній статті ми зосередимося на тому, як виконати кластерний аналіз за допомогою моделей суміші процесу Діріхле. Ми визначимо дві різні моделі суміші процесу Діріхле, які використовують китайський ресторанний процес і згорнуту вибірку Гіббса для виконання кластеризації безперервних наборів даних і документів.