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

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

Категорійний
Параметри	${\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}}$

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

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

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

Зауважте, що в деяких галузях, таких як машинне навчання та обробка природної мови, категорійний та поліноміальний розподіли зливаються, і є звичним говорити про «поліноміальний розподіл», коли в дійсності мається на увазі категорійний. Це неточне використання походить з того факту, що іноді зручніше описувати наслідок категорійного розподілу як вектор «один із 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}}$.

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

${\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 випадкових векторів 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].

Властивості

Можливі ймовірності категорійного розподілу з ${\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.}$
• Цей розподіл є окремим випадком «багатовимірного розподілу Бернуллі», в якому в точності одна з 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}}}$.

• Спряженим апріорним розподілом категорійного розподілу є розподіл Діріхле. Подальше обговорення див. розділом нижче.
• Достатньою статистикою з 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}}}$

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

${\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 в наведеній вище моделі є просто (модою апостеріорного розподілу Діріхле), тобто,

${\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]:

${\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], він має дуже простий вигляд:

${\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) використовується для вибору значень з біноміального розподілу).

функція вибрати_категорійно(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]. Нехай ${\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. . (англ.)
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. ^[en] (2006) Pattern Recognition and Machine Learning, Springer. (англ.)
5. Johnson, N.L., Kotz, S., Balakrishnan, N. (1997) Discrete Multivariate Distributions, Wiley. (p.105) (англ.)
6. Agresti, A., An Introduction to Categorical Data Analysis, Wiley-Interscience, 2007, , pp. 25 (англ.)
7. Adams, Ryan. . Архів оригіналу за 6 березня 2016. Процитовано 3 квітня 2016. (англ.)