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

Категорійний
Параметри	${\displaystyle k>0}$ кількість категорій (ціле число) ${\displaystyle p_{1},\ldots ,p_{k}}$ ймовірності подій (${\displaystyle \Sigma p_{i}=1}$)
Носій функції	${\displaystyle x\in \{1,\dots ,k\}}$
Розподіл імовірностей	(1) ${\displaystyle p(x=i)=p_{i}}$ (2) ${\displaystyle p(x)=p_{1}^{[x=1]}\cdots p_{k}^{[x=k]}}$ (3) ${\displaystyle p(x)=[x=1]\cdot p_{1}\,+\dots +\,[x=k]\cdot p_{k}}$ ${\displaystyle [x=i]}$ є дужками Айверсона
Функція розподілу ймовірностей (cdf)	${\displaystyle {\begin{cases}0&{\text{для }}x<1\\\sum _{j=1}^{i}p_{j}&{\text{для }}x\in [i,i+1)\\1&{\text{для }}x\geq k\end{cases}}}$
Середнє	${\displaystyle \operatorname {E} ([x=i])=p_{i}}$, це є середнім значенням дужок Айверсона ${\displaystyle [x=i]}$, а не середнім значенням ${\displaystyle x}$
Медіана	${\displaystyle i}$ таке що ${\displaystyle \sum _{j=1}^{i-1}p_{j}\leq 0.5}$ та ${\displaystyle \sum _{j=1}^{i}p_{j}\geq 0.5}$
Мода	${\displaystyle i}$ таке що ${\displaystyle p_{i}=\max(p_{1},\ldots ,p_{k})}$
Дисперсія	${\displaystyle \textstyle {\mathrm {Var} }([x=i])=p_{i}(1-p_{i})}$ ${\displaystyle \textstyle {\mathrm {Cov} }([x=i],[x=j])=-p_{i}p_{j}~~(i\neq j)}$
Твірна функція моментів (mgf)	${\displaystyle \sum _{i=1}^{k}p_{i}e^{t_{i}}}$
Характеристична функція	${\displaystyle \sum _{j=1}^{k}p_{j}e^{it_{j}}}$ де ${\displaystyle i^{2}=-1}$
Генератриса (pgf)	${\displaystyle \sum _{i=1}^{k}p_{i}z_{i}}$ для ${\displaystyle (z_{1},\ldots ,z_{k})\in \mathbb {C} ^{k}}$

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

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

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

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

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

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

Введення

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

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

${\displaystyle f(x=i|{\boldsymbol {p}})=p_{i},}$

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

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

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

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

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

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

${\displaystyle f(\mathbf {x} |{\boldsymbol {p}})=\prod _{i=1}^{k}p_{i}^{x_{i}},}$

де ${\displaystyle p_{i}}$ представляє ймовірність побачити елемент ${\displaystyle i}$, а ${\displaystyle \textstyle {\sum _{i}p_{i}=1}}$. Це є формулюванням, прийнятим Бішопом^[en].[4][прим. 1]

Властивості

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

• Цей розподіл повністю задається ймовірностями, пов'язаними з кожним із чисел i: ${\displaystyle p_{i}=P(X=i)}$, i = 1,...,k, де ${\displaystyle \textstyle {\sum _{i}p_{i}=1}}$. Ці можливі ймовірності в точності є стандартним ${\displaystyle (k-1)}$-вимірним симплексом; для k = 2 це вироджується до можливих імовірностей розподілу Бернуллі, що є 1-симплексом, ${\displaystyle p_{1}+p_{2}=1,0\leq p_{1},p_{2}\leq 1.}$
• Цей розподіл є окремим випадком «багатовимірного розподілу Бернуллі»,[5] в якому в точності одна з k змінних 0-1 набуває значення одиниці.
• ${\displaystyle \mathbb {E} \left[\mathbf {x} \right]={\boldsymbol {p}}}$
• Нехай ${\displaystyle {\boldsymbol {X}}}$ буде реалізацією з категоричного розподілу. Визначмо випадковий вектор Y як складений з елементів

${\displaystyle Y_{i}=I({\boldsymbol {X}}=i),}$

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

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

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

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

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

${\displaystyle {\begin{array}{lclcl}{\boldsymbol {\alpha }}&=&(\alpha _{1},\ldots ,\alpha _{K})&=&{\text{гіперпараметр концентрації}}\\\mathbf {p} \mid {\boldsymbol {\alpha }}&=&(p_{1},\ldots ,p_{K})&\sim &\operatorname {Dir} (K,{\boldsymbol {\alpha }})\\\mathbb {X} \mid \mathbf {p} &=&(x_{1},\ldots ,x_{K})&\sim &\operatorname {Cat} (K,\mathbf {p} )\end{array}}}$

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

${\displaystyle {\begin{array}{lclcl}\mathbf {c} &=&(c_{1},\ldots ,c_{K})&=&{\text{кількість випадків категорії }}i=\sum _{j=1}^{N}[x_{j}=i]\\\mathbf {p} \mid \mathbb {X} ,{\boldsymbol {\alpha }}&\sim &\operatorname {Dir} (K,\mathbf {c} +{\boldsymbol {\alpha }})&=&\operatorname {Dir} (K,c_{1}+\alpha _{1},\ldots ,c_{K}+\alpha _{K})\end{array}}}$

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

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

${\displaystyle \mathbb {E} [p_{i}\mid \mathbb {X} ,{\boldsymbol {\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), або багато інших близьких можливостей. Ступінь вплутаної тут невизначеності визначається дисперсією апостеріорного, яка контролюється загальним числом спостережень — що більше даних ми спостерігаємо, то менше невизначеності про істинний параметр.)

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

Оцінка МАІ

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

${\displaystyle \arg \max _{\mathbf {p} }p(\mathbf {p} |\mathbb {X} )={\frac {\alpha _{i}+c_{i}-1}{\sum _{i}(\alpha _{i}+c_{i}-1)}},\qquad \forall i\;\alpha _{i}+c_{i}>1}$

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

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

У наведеній вище моделі відособлена правдоподібність спостережень (тобто спільний розподіл спостережень зі знеособленим апріорним параметром) є поліноміальним розподілом Діріхле^[en]:[2]

${\displaystyle {\begin{aligned}p(\mathbb {X} \mid {\boldsymbol {\alpha }})&=\int _{\mathbf {p} }p(\mathbb {X} \mid \mathbf {p} )p(\mathbf {p} \mid {\boldsymbol {\alpha }}){\textrm {d}}\mathbf {p} \\&={\frac {\Gamma \left(\sum _{k}\alpha _{k}\right)}{\Gamma \left(N+\sum _{k}\alpha _{k}\right)}}\prod _{k=1}^{K}{\frac {\Gamma (c_{k}+\alpha _{k})}{\Gamma (\alpha _{k})}}\end{aligned}}}$

Цей розподіл відіграє важливу роль в ієрархічних баєсових моделях, оскільки при виконанні висновування над такими моделями із застосуванням таких методів, як вибірка за Ґіббсом^[en] або варіаційні баєсові методи^[en], апріорні розподіли Діріхле часто знеособлюються. Докладніше див. у статті про цей розподіл^[en].

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

Передбачуваним апостеріорним розподілом^[en] нового спостереження в наведеній вище моделі є розподіл, який матиме нове спостереження ${\displaystyle {\tilde {x}}}$ при заданому наборі ${\displaystyle \mathbb {X} }$ з N категорійних спостережень. Як показано в статті про поліноміальний розподіл Діріхле^[en], він має дуже простий вигляд:[2]

${\displaystyle {\begin{aligned}p({\tilde {x}}=i\mid \mathbb {X} ,{\boldsymbol {\alpha }})&=\int _{\mathbf {p} }p({\tilde {x}}=i\mid \mathbf {p} )\,p(\mathbf {p} \mid \mathbb {X} ,{\boldsymbol {\alpha }})\,{\textrm {d}}\mathbf {p} \\&=\,{\frac {c_{i}+\alpha _{i}}{N+\sum _{k}\alpha _{k}}}\\&=\,\mathbb {E} [p_{i}\mid \mathbb {X} ,{\boldsymbol {\alpha }}]\\&\propto \,c_{i}+\alpha _{i}.\\\end{aligned}}}$

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

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

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

${\displaystyle {\begin{aligned}p({\tilde {x}}=i\mid \mathbb {X} ,{\boldsymbol {\alpha }})&=\int _{\mathbf {p} }p({\tilde {x}}=i\mid \mathbf {p} )\,p(\mathbf {p} \mid \mathbb {X} ,{\boldsymbol {\alpha }})\,{\textrm {d}}\mathbf {p} \\&=\,\mathbb {E} _{\mathbf {p} \mid \mathbb {X} ,{\boldsymbol {\alpha }}}\left[p({\tilde {x}}=i\mid \mathbf {p} )\right]\\&=\,\mathbb {E} _{\mathbf {p} \mid \mathbb {X} ,{\boldsymbol {\alpha }}}\left[p_{i}\right]\\&=\,\mathbb {E} [p_{i}\mid \mathbb {X} ,{\boldsymbol {\alpha }}].\\\end{aligned}}}$

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

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

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

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

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

${\displaystyle {\begin{aligned}p(x_{n}=i\mid \mathbb {X} ^{(-n)},{\boldsymbol {\alpha }})&=\,{\frac {c_{i}^{(-n)}+\alpha _{i}}{N-1+\sum _{i}\alpha _{i}}}&\propto \,c_{i}^{(-n)}+\alpha _{i}\\\end{aligned}}}$

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

Вибірка

Найпоширеніший спосіб вибірки з категорійного розподілу використовує один з типів вибірки оберненим перетворенням^[en]:

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

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

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

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

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

функція вибрати_категорійно(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

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

В машинному навчанні є типовим параметризувати категорійний розподіл ${\displaystyle p_{1},\ldots ,p_{k}}$ через необмежене представлення в ${\displaystyle \mathbb {R} ^{k}}$, складові якого задаються як

${\displaystyle \gamma _{i}=\log p_{i}+\alpha }$

де ${\displaystyle \alpha }$ є будь-якою дійсною сталою. Маючи це представлення, ${\displaystyle p_{1},\ldots ,p_{k}}$ можна відтворити із застосуванням нормованої експоненційної функції, з чого потім можна робити вибірку за описаних вище методик. Проте існує пряміший метод вибірки, який використовує вибірку з розподілу Гумбеля^[en].[7] Нехай ${\displaystyle g_{1},\ldots ,g_{k}}$ будуть k незалежними виборами зі стандартного розподілу Гумбеля, тоді

${\displaystyle c=\arg \max _{i}\gamma _{i}+g_{i}}$

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

Див. також

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

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

• Розподіл Діріхле
• Поліноміальний розподіл
• Розподіл Бернуллі
• Поліноміальний розподіл Діріхле^[en]

Примітки

1. Проте Бішоп не використовує явно термін «категорійний розподіл».

Виноски

1. Murphy, K. P. (2012). Machine learning: a probabilistic perspective, p. 35. MIT press. ISBN 0262018020. (англ.)
2. Minka, T. (2003) Bayesian inference, entropy and the multinomial distribution [Архівовано 4 березня 2016 у Wayback Machine.]. Technical report Microsoft Research. (англ.)
3. Minka, T. (2003), op. cit. Minka uses the Kronecker delta function, similar to but less general than the Iverson bracket. (англ.)
4. Bishop, C.^[en] (2006) Pattern Recognition and Machine Learning, Springer. ISBN 0-387-31073-8 (англ.)
5. Johnson, N.L., Kotz, S., Balakrishnan, N. (1997) Discrete Multivariate Distributions, Wiley. ISBN 0-471-12844-9 (p.105) (англ.)
6. Agresti, A., An Introduction to Categorical Data Analysis, Wiley-Interscience, 2007, ISBN 978-0-471-22618-5, pp. 25 (англ.)
7. Adams, Ryan. The Gumbel-Max Trick for Discrete Distributions. Архів оригіналу за 6 березня 2016. Процитовано 3 квітня 2016. (англ.)