Перплексивність

У теорії інформації, перплексивність (складність) — це міра того, наскільки добре розподіл імовірності або статистична модель прогнозує вибірку. Її можна використовувати для порівняння ймовірнісних моделей. Низька перплексивність означає, що розподіл ймовірності добре передбачає вибірку.

Перплексивність розподілу ймовірностей

Перплексивність PP дискретного розподілу ймовірностей p визначається як

${\displaystyle {\mathit {PP}}(p):=2^{H(p)}=2^{-\sum _{x}p(x)\log _{2}p(x)}=\prod _{x}p(x)^{-p(x)}}$

де H(p) — ентропія (у бітах) розподілу, a x — діапазон подій. (Основа логарифма не обов'язково має бути 2: перплексивність не залежить від основи за умови, що ентропія та показникова функція використовують ту саму основу.) Цей показник також відомий у деяких областях як міра різноманітності.

Перплексивність випадкової величини X може бути визначена як перплексивність розподілу її можливих значень x.

В окремому випадку, коли p моделює k-сторонній гральний кубик (рівномірний розподіл по k дискретним подіям), її перплексивність дорівнює k. Випадкова величина з перплексивністю k має таку ж невизначеність, як і k-сторонній гральний кубик. Тоді кажуть, що кубик «k-перплексивний» щодо значення випадкової величини. (Якщо це не k-сторонній кубик, можливо більше ніж k значень, однак загальна невизначеність не є вищою, тому що деякі з цих значень матимуть ймовірність більше 1/k, зменшуючи загальне значення під час підсумовування.)

Поняття перплексивності іноді використовується у значенні міри складності проблеми передбачення. Однак, це не завжди точно. Якщо у вас є два результати, один з яких має можливість 0,9, то при використанні оптимальної стратегії ваші шанси на правильне вгадування становлять 90 відсотків. Перплексивність становить 2 ^{−0,9 log ₂ 0,9 — 0,1 log ₂ 0,1} = 1,38. Обернена величина до неї (яка у випадку з k-стороннім кубиком є ймовірністю правильного вгадування) дорівнює 1/1.38 = 0.72, а не 0,9.

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

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

Перплексивність імовірнісної моделі

Модель з невідомим розподілом ймовірності величини p може бути створеною на основі навчальної вибірки, взятої з p.

Враховуючи запропоновану модель ймовірності q, можна оцінити q, зʼясувавши, наскільки добре вона передбачає окрему тестову вибірку x₁, x₂, …, x_N, також отриману з p. Складність моделі q визначається як

${\displaystyle b^{-{\frac {1}{N}}\sum _{i=1}^{N}\log _{b}q(x_{i})},}$

де ${\displaystyle b}$ зазвичай становить 2.

Кращі моделі q невідомого розподілу p мають тенденцію визначати вищі ймовірності q(x_i) для тестових подій. Таким чином, вони мають нижчу перплексивність, тобто менше дивуються тестовому зразку.

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

Експоненту можна також розглядати як перехресну ентропію,

${\displaystyle H({\tilde {p}},q)=-\sum _{x}{\tilde {p}}(x)\log _{2}q(x),}$

де ${\displaystyle {\tilde {p}}}$ позначає емпіричний розподіл тестової вибірки (тобто, ${\displaystyle {\tilde {p}}(x)=n/N}$, якщо x з'явилося n разів у тестовій вибірці розміру N).

Перплексивність на слово

В обробці природної мови перплексивність є способом оцінки мовних моделей. Мовна модель — це розподіл ймовірностей на цілі речення або тексти.

Використовуючи визначення перплексивності для імовірнісної моделі, можна було б знайти, наприклад, що середнє речення x_i у тестовій вибірці може бути закодовано в 190 біт (тобто, тестові речення мали середню логарифмічну ймовірність -190). Для моделі це означає величезне значення перплексивності 2¹⁹⁰ на речення. Однак, частіше заведено нормалізувати довжину речення і враховувати лише кількість бітів на слово. Таким чином, якщо усі речення тестового зразка містили в цілому 1000 слів і їх можна було закодувати, використовуючи 7,95 біт на слово, то можна було б сказати, що перплексивність моделі ${\displaystyle 2^{7{,}95}\approx 247}$ на одне слово. Іншими словами, модель настільки заплутана в тестових даних, ніби їй доводилося вибирати рівномірно і незалежно з 247 можливостей для кожного слова.

Найменша перплексивність, яка була опублікована в Браунівському корпусі (містить 1 мільйон слів американської англійської різних тем і жанрів) станом на 1992 рік, дійсно становить близько 247 на слово, що відповідає перехресній ентропії ${\displaystyle \log _{2}247\approx 7{,}95}$ біт на слово або 1,75 біт на букву, якщо скористатися триграмною моделлю. Зазвичай можна досягти меншої перплексивність на спеціалізованих корпусах текстів, оскільки вони більш передбачувані.

Загалом, просте передбачення про те, що наступним словом у корпусі Брауна є слово «the», буде мати точність 7 відсотків, а не 1/247 = 0,4 відсотки. Вказане припущення засновано на статистиці уніграмм корпусу Брауна, а не на статистиці триграми, яка дала слову «the» перплексивність 247. Як бачимо, використання триграмної моделі підвищило б шанси на правильні припущення.

Примітки

• Затверджування статистичної моделі

Посилання

1. Brown, Peter F. та ін. (March 1992). An Estimate of an Upper Bound for the Entropy of English (PDF). Computational Linguistics. 18 (1). Процитовано 7 лютого 2007.