Категорійний розподіл

В теорії ймовірностей та статистиці категорі́йний розпо́діл (Шаблон:Lang-en, що також називають «узагальненим розподілом Бернуллі», Шаблон:Lang-en або, менш точно, «дискретним розподілом») — це розподіл імовірності, що описує можливі результати випадкової події, яка може мати один із K можливих наслідків, із окремим зазначенням ймовірності кожного з наслідків. Не обов'язково мається на увазі існування якогось впорядкування цих результатів, але для зручності опису цього розподілу часто додають числові мітки (наприклад, від 1 до K). Зауважте, що K-вимірний категорійний розподіл є найзагальнішим розподілом над подією з K можливими наслідками; будь-який інший дискретний розподіл над простором елементарних подій розміру K є окремим випадком. Параметри, що вказують імовірності кожного з можливих наслідків, обмежено лише тим, що кожен з них мусить бути в діапазоні від 0 до 1, і всі вони в сумі мусять давати 1.

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

Термінологія

Часом для позначення категорійного розподілу використовують термін «дискретний розподіл». Проте, по-правильному, він позначує не одне певне сімейство розподілів, а загальний клас розподілів.

Зауважте, що в деяких галузях, таких як машинне навчання та обробка природної мови, категорійний та поліноміальний розподіли зливаються, і є звичним говорити про «поліноміальний розподіл», коли в дійсності мається на увазі категорійний. Це неточне використання походить з того факту, що іноді зручніше описувати наслідок категорійного розподілу як вектор «один із K» (вектор, один з елементів якого містить 1, а всі інші елементи містять 0), аніж як ціле число на проміжку від 1 до K; у цьому вигляді категорійний розподіл є рівнозначним поліноміальному розподілові з єдиним спостереженням (див. нижче).

Проте злиття категорійного та поліноміального розподілів може призводити до проблем. Наприклад, у Шаблон:Нп, який зазвичай з'являється в моделях обробки природної мови (хоча й не завжди під цією назвою) як результат Шаблон:Нп, де розподіли Діріхле спадають в ієрархічній баєсовій моделі, дуже важливо відрізняти категорійний від поліноміального. Спільний розподіл одних і тих же змінних з одним і тим же поліноміальним розподілом Діріхле має два різні вигляди в залежності від того, чи він характеризується як розподіл, область визначення якого є над окремими категорійними вузлами, чи над кількостями вузлів поліноміального стилю в кожній конкретній категорії (подібно до розрізнення між набором вузлів з розподілами Бернуллі та єдиним вузлом із біноміальним розподілом). Обидва вигляди мають дуже схожі функції маси ймовірності (ФМІ, Шаблон:Lang-en), що обидві посилаються на кількості вузлів поліноміального стилю в категорії. Проте ФМІ поліноміального стилю має додатковий поліноміальний коефіцієнт, який у ФМІ категорійного стилю є сталою, яка дорівнює 1. Змішування цих двох може легко привести до неправильних результатів в умовах, у яких цей додатковий коефіцієнт не є сталим по відношенню до досліджуваних розподілів. Цей коефіцієнт часто є сталим у повних умовних виразах, які застосовуються у вибірці Ґіббса та оптимальних розподілах у варіаційних методах.

Введення

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

В одному з формулювань цього розподілу як простір елементарних подій береться скінченна послідовність цілих чисел. Конкретні цілі числа, що використовуються як мітки, не є важливими; ними можуть бути {0, 1, ..., k-1}, або {1, 2, ..., k}, або будь-який інший довільний набір значень. В наступних описах ми використовуємо для зручності {1, 2, ..., k}, хоча це й розходиться з угодою для розподілу Бернуллі, яка використовує {0, 1}. В цьому випадку функцією маси ймовірності f є

$f(x=i|𝒑)=p_i,$

де $𝒑=(p_1,...,p_k)$, $p_i$ представляє ймовірність побачити елемент $i$, а ${\sum }_{i=1}^k{p}_i=1$.

Іншим формулюванням, яке видається складнішим, але полегшує математичні перетворення, є наступне, яке застосовує дужки Айверсона:

$f(x|𝒑)=\prod _{i=1}^k{p}_i^{[x=i]},$

де $[x=i]$ обчислюється як 1, якщо $x=i$, а інакше як 0. В цього формулювання є деякі переваги, наприклад:

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

Ще одне формулювання робить явний зв'язок між категорійним та поліноміальним розподілами шляхом розгляду категорійного розподілу як окремого випадку поліноміального розподілу, в якому параметр n поліноміального розподілу (кількість елементів вибірки) зафіксовано на рівні 1. В цьому формулюванні простір елементарних подій може розглядатися як множина закодованих як 1-із-K випадкових векторів x розмірності k, які мають таку властивість, що рівно один елемент кожного з них має значення 1, а всі інші мають значення 0. Конкретний елемент, який має значення 1, вказує, яку категорію було обрано. Функцією маси ймовірності f у цьому формулюванні є

$f(𝐱|𝒑)=\prod _{i=1}^k{p}_i^{x_i},$

де $p_i$ представляє ймовірність побачити елемент $i$, а $\sum _i{p}_i=1$. Це є формулюванням, прийнятим Шаблон:Нп.

Властивості

Можливі ймовірності категорійного розподілу з $k=3$ є 2-симплексом $p_1+p_2+p_3=1$, вкладеним до 3-вимірного простору.

• Цей розподіл повністю задається ймовірностями, пов'язаними з кожним із чисел i: $p_i=P(X=i)$, i = 1,...,k, де $\sum _i{p}_i=1$. Ці можливі ймовірності в точності є стандартним $(k-1)$-вимірним симплексом; для k = 2 це вироджується до можливих імовірностей розподілу Бернуллі, що є 1-симплексом, $p_1+p_2=1,0\le p_1,p_2\le 1.$
• Цей розподіл є окремим випадком «багатовимірного розподілу Бернуллі», в якому в точності одна з k змінних 0-1 набуває значення одиниці.
• $𝔼\left[𝐱\right]=𝒑$
• Нехай $𝑿$ буде реалізацією з категоричного розподілу. Визначмо випадковий вектор Y як складений з елементів

$Y_i=I(𝑿=i),$

де I є індикаторною функцією. Тоді Y має розподіл, який є окремим випадком поліноміального розподілу з параметром $n=1$. Сума $n$ таких незалежних та однаково розподілених змінних Y, побудована з категорійного розподілу з параметром $𝒑$, є поліноміально розподіленою з параметрами $n$ та $𝒑$.

• Спряженим апріорним розподілом категорійного розподілу є розподіл Діріхле. Подальше обговорення див. розділом нижче.
• Достатньою статистикою з n незалежних спостережень є набір кількостей (або, рівнозначно, пропорція) спостережень у кожній категорії, де загальна кількість спроб (=n) є фіксованою.
• Індикаторна функція того, що спостереження матиме значення i, рівнозначна функції дужок Айверсона $[x=i]$ або функції дельти Кронекера ${\delta }_{xi}$, має розподіл Бернуллі з параметром $p_i$.

Зі спряженим апріорним

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

Формально це може бути виражено наступним чином. Якщо задано модель

$\begin{array}{ccccc}\mathit{\alpha }& =& ({\alpha }_1,\dots ,{\alpha }_K)& =& \text{гіперпараметр концентрації}\\ 𝐩\mid \mathit{\alpha }& =& (p_1,\dots ,p_K)& \sim & \mathrm{Dir}(K,\mathit{\alpha })\\ 𝕏\mid 𝐩& =& (x_1,\dots ,x_K)& \sim & \mathrm{Cat}(K,𝐩)\end{array}$

то виконується наступне:

$\begin{array}{ccccc}𝐜& =& (c_1,\dots ,c_K)& =& \text{кількість випадків категорії }i=\sum _{j=1}^N[x_j=i]\\ 𝐩\mid 𝕏,\mathit{\alpha }& \sim & \mathrm{Dir}(K,𝐜+\mathit{\alpha })& =& \mathrm{Dir}(K,c_1+{\alpha }_1,\dots ,c_K+{\alpha }_K)\end{array}$

Це співвідношення використовується в баєсовій статистиці для оцінки параметру p, що лежить в основі категорійного розподілу, при заданій сукупності N зразків. Інтуїтивно зрозуміло, що ми можемо розглядати Шаблон:Нп вектор α як Шаблон:Нп, тобто як представлення кількості спостережень у кожній з категорій, що ми вже бачили. Тоді ми просто додаємо кількості для всіх нових спостережень (вектор c), щоби вивести апостеріорний розподіл.

Подальша інтуїція виходить з математичного сподівання апостеріорного розподілу (див. статтю про розподіл Діріхле):

$𝔼[p_i\mid 𝕏,\mathit{\alpha }]=\frac{c_i+{\alpha }_i}{N+\sum _k{\alpha }_k}$

Це каже, що очікувана ймовірність побачити категорію i серед різних дискретних розподілів, породжених апостеріорним розподілом, просто дорівнює пропорції випадків цієї категорії, в дійсності побачених у даних, включно із псевдолічильниками в апріорному розподілі. Це підсилює інтуїтивний сенс: Якщо, наприклад, є три можливі категорії, й ми бачили категорію 1 у наших спостережених даних 40% часу, то ми також очікуватимемо в середньому бачити категорію 1 40% часу і в апостеріорному розподілі.

(Зауважте, що ця інтуїція ігнорує вплив апріорного розподілу. Крім того, важливо мати на увазі, що апостеріорне є розподілом над розподілами. Слід пам'ятати, що апостеріорний розподіл в цілому говорить нам, що ми знаємо про досліджуваний параметр, і в цьому випадку сам параметр є дискретним розподілом імовірності, тобто справжнім категорійним розподілом, який породив наші дані. Наприклад, якщо ми бачили 3 категорії у співвідношенні 40:5:55 у наших спостережуваних даних, тоді, нехтуючи впливом апріорного розподілу, ми очікуватимемо, що істинний параметр — тобто, істинний розподіл, який лежить в основі наших спостережених даних, які він породив — матиме середнє значення (0.40,0.05,0.55), яке насправді є тим, про що нам говорить апостеріорний розподіл. Проте справжнім розподілом в дійсності міг би бути (0.35,0.07,0.58), або (0.42,0.04,0.54), або багато інших близьких можливостей. Ступінь вплутаної тут невизначеності визначається дисперсією апостеріорного, яка контролюється загальним числом спостережень — що більше даних ми спостерігаємо, то менше невизначеності про істинний параметр.)

(Формально, апріорний параметр ${\alpha }_i$ слід розглядати як такий, що представляє ${\alpha }_i-1$ апріорних спостережень категорії $i$. Тоді уточнений апостеріорний параметр $c_i+{\alpha }_i$ представляє $c_i+{\alpha }_i-1$ апостеріорних спостережень. Це відображає той факт, що розподіл Діріхле з $\mathit{\alpha }=(1,1,\dots )$ має абсолютно пласку форму — по суті, рівномірний розподіл над симплексом можливих значень p. Логічно, що плаский розподіл такого виду представляє повне незнання, що відповідає відсутності спостережень будь-якого виду. Проте математичне уточнення апостеріорного працює добре, якщо ми ігноруємо член $\dots -1$, і просто думаємо про вектор α як такий, що прямо представляє набір псевдолічильників. Крім того, така практика дозволяє уникати проблеми інтерпретування значень ${\alpha }_i$, менших за 1.)

Оцінка МАІ

Оцінка апостеріорного максимуму параметра p в наведеній вище моделі є просто модою апостеріорного розподілу Діріхле, тобто,

$\arg \underset{𝐩}{\max }p(𝐩|𝕏)=\frac{{\alpha }_i+c_i-1}{\sum _i({\alpha }_i+c_i-1)},\mathrm{\forall }i{\alpha }_i+c_i>1$

У багатьох практичних застосуваннях єдиним способом гарантувати умову $\mathrm{\forall }i{\alpha }_i+c_i>1$ є встановити ${\alpha }_i>1$ для всіх i.

Відособлена правдоподібність

У наведеній вище моделі відособлена правдоподібність спостережень (тобто спільний розподіл спостережень зі знеособленим апріорним параметром) є Шаблон:Нп:

$\begin{array}{cc}p(𝕏\mid \mathit{\alpha })& =\underset{𝐩}{\int }p(𝕏\mid 𝐩)p(𝐩\mid \mathit{\alpha })\text{d}𝐩\\ & =\frac{\mathrm{\Gamma }\left(\sum _k{\alpha }_k\right)}{\mathrm{\Gamma }(N+\sum _k{\alpha }_k)}\prod _{k=1}^K\frac{\mathrm{\Gamma }(c_k+{\alpha }_k)}{\mathrm{\Gamma }({\alpha }_k)}\end{array}$

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

Передбачуваний апостеріорний розподіл

Шаблон:Нп нового спостереження в наведеній вище моделі є розподіл, який матиме нове спостереження $\tilde{x}$ при заданому наборі $𝕏$ з N категорійних спостережень. Як показано в статті про Шаблон:Нп, він має дуже простий вигляд:

$\begin{array}{cc}p(\tilde{x}=i\mid 𝕏,\mathit{\alpha })& =\underset{𝐩}{\int }p(\tilde{x}=i\mid 𝐩)p(𝐩\mid 𝕏,\mathit{\alpha })\text{d}𝐩\\ & =\frac{c_i+{\alpha }_i}{N+\sum _k{\alpha }_k}\\ & =𝔼[p_i\mid 𝕏,\mathit{\alpha }]\\ & \propto c_i+{\alpha }_i.\\ \end{array}$

Зверніть увагу на різні взаємозв'язки між цією формулою, та попередніми:

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

Причина рівнозначності між передбачуваною апостеріорною ймовірністю та математичним сподіванням апостеріорного розподілу p стає очевидною, щойно ми переглядаємо наведену вище формулу. Як описано в статті про Шаблон:Нп, формула передбачуваної апостеріорної ймовірності має вигляд математичного сподівання, взятого по відношенню до апостеріорного розподілу:

$\begin{array}{cc}p(\tilde{x}=i\mid 𝕏,\mathit{\alpha })& =\underset{𝐩}{\int }p(\tilde{x}=i\mid 𝐩)p(𝐩\mid 𝕏,\mathit{\alpha })\text{d}𝐩\\ & ={𝔼}_{𝐩\mid 𝕏,\mathit{\alpha }}[p(\tilde{x}=i\mid 𝐩)]\\ & ={𝔼}_{𝐩\mid 𝕏,\mathit{\alpha }}\left[p_i\right]\\ & =𝔼[p_i\mid 𝕏,\mathit{\alpha }].\\ \end{array}$

Вирішальним рядком вище є третій. Другий випливає безпосередньо з визначення математичного сподівання. Третій рядок є особливим для категорійного розподілу, і випливає з того факту що, конкретно в категорійному розподілі, математичне сподівання побачити певне значення i безпосередньо вказується пов'язаним параметром p_i. Четвертий рядок є просто переформулюванням третього в іншому записі, із застосуванням наведеного вище запису математичного сподівання, взятого по відношенню до апостеріорного розподілу параметрів.

Звернімо також увагу, що відбувається у сценарії, в якому ми спостережуємо точки даних одна за одною, і кожного разу розглядаємо їхню передбачувану ймовірність перед спостереженням точки даних та уточненням апостеріорного. Для будь-якої заданої точки даних ймовірність того, що ця точка набуде певної категорії, залежить від кількості точок даних, що вже є в цій категорії. Якщо категорія має високу частоту трапляння, тоді нові точки правдоподібніше приєднаються до цієї категорії — збагачуючи далі ту саму категорію. Цей тип сценарію часто називають моделлю переважного приєднання (або «багатий стає багатшим»). Це моделює багато процесів реального світу, і в таких випадках вибори, зроблені кількома першими точками даних, мають дуже великий вплив на решту точок даних.

Умовний апостеріорний розподіл

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

Тобто, для набору вузлів $𝕏$, якщо ми позначимо вузли під питанням через $x_n$, а решту — через ${𝕏}^{(-n)}$, то

$\begin{array}{ccc}p(x_n=i\mid {𝕏}^{(-n)},\mathit{\alpha })& =\frac{c_i^{(-n)}+{\alpha }_i}{N-1+\sum _i{\alpha }_i}& \propto c_i^{(-n)}+{\alpha }_i\\ \end{array}$

де $c_i^{(-n)}$ є числом вузлів, що мають категорію i, серед інших вузлів, крім вузла n.

Вибірка

Найпоширеніший спосіб вибірки з категорійного розподілу використовує один з типів Шаблон:Нп:

Припустімо, що нам дано розподіл, виражений як «пропорційно до» якогось виразу, з невідомою Шаблон:Нп. Тоді, перш ніж брати якісь зразки, ми готуємо деякі значення в такий спосіб:

1. Обчислити не нормоване значення розподілу для кожної з категорій.
2. Підсумувати їх, і поділити кожне значення на цю суму, щоби Шаблон:Нп їх.
3. Накласти якийсь порядок на категорії (наприклад, індексом, який проходить значення від 1 до k, де k є числом категорій).
4. Перетворити ці значення на кумулятивну функцію розподілу (КФР) заміною кожного значення сумою всіх попередніх значень. Це може бути здійснено за час O(k). Отриманим в результаті значенням для першої категорії буде 0.

Потім, кожного разу, як потрібно вибрати значення:

1. Взяти рівномірно розподілене число між 0 та 1.
2. Визначити найбільше число в КФР, чиє значення є меншим або рівним щойно обраному числу. Це може здійснюватися за час O(log(k)), бінарним пошуком.
3. Повернути категорію, яка відповідає цьому значенню КФР.

Якщо потрібно вибирати багато значень з одного й того ж категорійного розподілу, то ефективнішим може бути наступний підхід. Він вибирає n зразків за час O(n) (за припущення, що наближення O(1) використовується для вибору значень з біноміального розподілу).

функція вибрати_категорійно(n) // де n є числом зразків, які потрібно вибрати з категорійного розподілу
  r = 1
  s = 0
  для i від 1 до k // де k є числом категорій
    v = вибрати з біноміального розподілу (n, p[i] / r) // де p[i] є ймовірністю категорії i
    для j від 1 до v
      z[s++] = i // де z є масивом, у якому зберігаються результати
    n = n - v
    r = r - p[i]
  перемішати (випадково перевпорядкувати) елементи в z
  повернути z

Вибірка через розподіл Гумбеля

В машинному навчанні є типовим параметризувати категорійний розподіл $p_1,\dots ,p_k$ через необмежене представлення в ${ℝ}^k$, складові якого задаються як

${\gamma }_i=\log p_i+\alpha$

де $\alpha$ є будь-якою дійсною сталою. Маючи це представлення, $p_1,\dots ,p_k$ можна відтворити із застосуванням нормованої експоненційної функції, з чого потім можна робити вибірку за описаних вище методик. Проте існує пряміший метод вибірки, який використовує вибірку з Шаблон:Нп. Нехай $g_1,\dots ,g_k$ будуть k незалежними виборами зі стандартного розподілу Гумбеля, тоді

$c=\arg \underset{i}{\max }{\gamma }_i+g_i$

буде вибіркою з бажаного категорійного розподілу. (Якщо $u_i$ є вибіркою зі стандартного рівномірного розподілу, то $g_i=-\log (-\log u_i)$ є вибіркою зі стандартного розподілу Гумбеля.)

Див. також

• Категорійна змінна

Пов'язані розподіли

• Розподіл Діріхле
• Поліноміальний розподіл
• Розподіл Бернуллі
• Шаблон:Нп