Поточкова взаємна інформація

Пото́чкова взає́мна інформа́ція (ПВІ, англ. pointwise mutual information, PMI),^[1] або то́чкова взає́мна інформа́ція (англ. point mutual information) — це міра пов'язаності, що використовується в теорії інформації та статистиці. На відміну від взаємної інформації (ВІ), що будується на ПВІ, вона стосується одиничних подій, тоді як ВІ стосується усереднення всіх можливих подій.

Визначення ред.

ПВІ пари результатів x та y, що належать дискретним випадковим змінним X та Y, дає кількісну оцінку розбіжності між імовірністю їхнього збігу за заданого їхнього спільного розподілу, та їхніми особистими розподілами за умови їхньої незалежності. Математично:

\operatorname {pmi} (x;y)\equiv \log {\frac {p(x,y)}{p(x)p(y)}}=\log {\frac {p(x|y)}{p(x)}}=\log {\frac {p(y|x)}{p(y)}}.

Взаємна інформація (ВІ) випадкових змінних X та Y є математичним сподіванням значення ПВІ над усіма можливими результатами (по відношенню до спільного розподілу $p(x,y)$ ).

Ця міра є симетричною ( $\operatorname {pmi} (x;y)=\operatorname {pmi} (y;x)$ ). Вона може набувати додатних та від'ємних значень, але є нульовою, якщо X та Y є незалежними. Зауважте, що хоча ПВІ й може бути додатною або від'ємною, її математичне сподівання над усіма спільними подіями (ВІ) є додатним. ПВІ досягає максимуму тоді, коли X та Y є цілком пов'язаними (тобто, $p(x|y)$ або $p(y|x)=1$ ), даючи наступні межі:

-\infty \leq \operatorname {pmi} (x;y)\leq \min \left[-\log p(x),-\log p(y)\right].

Нарешті, $\operatorname {pmi} (x;y)$ збільшуватиметься за незмінної $p(x|y)$ , але зменшуваної $p(x)$ .

Ось приклад для ілюстрації:

x	y	p(x, y)
0	0	0.1
0	1	0.7
1	0	0.15
1	1	0.05

Використовуючи цю таблицю, ми можемо здійснити відособлювання, щоби отримати наступну додаткову таблицю для особистих розподілів:

	p(x)	p(y)
0	0.8	0.25
1	0.2	0.75

У цьому прикладі ми можемо обчислити чотири значення $pmi(x;y)$ . Із застосуванням логарифмів за основою 2:

pmi(x=0;y=0)	=	−1
pmi(x=0;y=1)	=	0.222392
pmi(x=1;y=0)	=	1.584963
pmi(x=1;y=1)	=	-1.584963

(Для довідки, взаємною інформацією $\operatorname {I} (X;Y)$ тоді буде 0.2141709)

Схожості зі взаємною інформацією ред.

Поточкова взаємна інформація має багато відношень, однакових зі взаємною інформацією. Зокрема,

${\begin{aligned}\operatorname {pmi} (x;y)&=&h(x)+h(y)-h(x,y)\\&=&h(x)-h(x|y)\\&=&h(y)-h(y|x)\end{aligned}}$

де $h(x)$ є власною інформацією, або $-\log _{2}p(X=x)$ .

Нормалізована поточкова взаємна інформація (НПВІ) ред.

Поточкову взаємну інформацію може бути нормалізовано в проміжку [-1,+1], що дає в результаті -1 (у границі) для спільної появи ніколи, 0 — для незалежності та +1 — для цілковито спільної появи^[en].^[2]

$\operatorname {npmi} (x;y)={\frac {\operatorname {pmi} (x;y)}{h(x,y)}}$

Варіанти ПВІ ред.

На додачу до наведеної вище НПВІ, ПВІ має багато інших цікавих варіантів. Порівняльне дослідження цих варіантів можна знайти в ^[3]

Ланцюгове правило для ПВІ ред.

Як і взаємна інформація,^[4] поточкова взаємна інформація слідує ланцюговому правилу, тобто,

\operatorname {pmi} (x;yz)=\operatorname {pmi} (x;y)+\operatorname {pmi} (x;z|y)

Це може бути легко доведено як

{\begin{aligned}\operatorname {pmi} (x;y)+\operatorname {pmi} (x;z|y)&{}=\log {\frac {p(x,y)}{p(x)p(y)}}+\log {\frac {p(x,z|y)}{p(x|y)p(z|y)}}\\&{}=\log \left[{\frac {p(x,y)}{p(x)p(y)}}{\frac {p(x,z|y)}{p(x|y)p(z|y)}}\right]\\&{}=\log {\frac {p(x|y)p(y)p(x,z|y)}{p(x)p(y)p(x|y)p(z|y)}}\\&{}=\log {\frac {p(x,yz)}{p(x)p(yz)}}\\&{}=\operatorname {pmi} (x;yz)\end{aligned}}

Застосування ред.

В математичній лінгвістиці ПВІ використовували для знаходження сполучень та пов'язаності слів. Наприклад, підрахунок^[en] появ та спільних появ^[en] слів у корпусі текстів можна використовувати для наближення ймовірностей $p(x)$ та $p(x,y)$ відповідно. Наступна таблиця показує кількості пар слів, що отримали найвищі та найнижчі рівні ПВІ у перших 50 мільйонах слів англомовної Вікіпедії (дамп від жовтня 2015 року), відфільтрованих за 1 000 чи більше спільних появ. Частоту кожної з кількостей можна отримати діленням її значення на 50 000 952. (Зауваження: в цьому прикладі для обчислення значень ПВІ використано натуральний логарифм замість логарифму за основою 2)

слово 1	слово 2	кількість слів 1	кількість слів 2	кількість спільних появ	ПВІ
puerto	rico	1938	1311	1159	10.0349081703
hong	kong	2438	2694	2205	9.72831972408
los	angeles	3501	2808	2791	9.56067615065
carbon	dioxide	4265	1353	1032	9.09852946116
prize	laureate	5131	1676	1210	8.85870710982
san	francisco	5237	2477	1779	8.83305176711
nobel	prize	4098	5131	2498	8.68948811416
ice	hockey	5607	3002	1933	8.6555759741
star	trek	8264	1594	1489	8.63974676575
car	driver	5578	2749	1384	8.41470768304
it	the	283891	3293296	3347	-1.72037278119
are	of	234458	1761436	1019	-2.09254205335
this	the	199882	3293296	1211	-2.38612756961
is	of	565679	1761436	1562	-2.54614706831
and	of	1375396	1761436	2949	-2.79911817902
a	and	984442	1375396	1457	-2.92239510038
in	and	1187652	1375396	1537	-3.05660070757
to	and	1025659	1375396	1286	-3.08825363041
to	in	1025659	1187652	1066	-3.12911348956
of	and	1761436	1375396	1190	-3.70663100173

Добре сполучені пари мають високу ПВІ, оскільки ймовірність спільної появи є лише трошки нижчою за ймовірності появи кожного зі слів. З іншого боку, пара слів, ймовірності появи яких є значно вищими за ймовірність їхньої спільної появи, отримує низький рівень ПВІ.

Примітки ред.

↑ Kenneth Ward Church and Patrick Hanks (March 1990). Word association norms, mutual information, and lexicography. Comput. Linguist. 16 (1): 22—29. Архів оригіналу за 28 серпня 2017. Процитовано 28 травня 2017. (англ.)
↑ Bouma, Gerlof (2009). Normalized (Pointwise) Mutual Information in Collocation Extraction (PDF). Proceedings of the Biennial GSCL Conference. Архів оригіналу (PDF) за 30 липня 2016. Процитовано 28 травня 2017. (англ.)
↑ Francois Role, Moahmed Nadif. Handling the Impact of Low frequency Events on Co-occurrence-based Measures of Word Similarity:A Case Study of Pointwise Mutual Information. [Архівовано 7 листопада 2016 у Wayback Machine.] Proceedings of KDIR 2011 : KDIR- International Conference on Knowledge Discovery and Information Retrieval, Paris, October 26-29 2011 (англ.)
↑ Paul L. Williams. INFORMATION DYNAMICS: ITS THEORY AND APPLICATION TO EMBODIED COGNITIVE SYSTEMS (PDF). Архів оригіналу (PDF) за 24 травня 2018. Процитовано 28 травня 2017. (англ.)

Література ред.

Fano, R M (1961). chapter 2. Transmission of Information: A Statistical Theory of Communications. MIT Press, Cambridge, MA. ISBN 978-0262561693. (англ.)

Посилання ред.

Демонстрація на сервері MSR Rensselaer (значення ПВІ нормалізовано, щоби вони були в проміжку між 0 та 1) (англ.)

[Church1990-1] Kenneth Ward Church and Patrick Hanks (March 1990). Word association norms, mutual information, and lexicography. Comput. Linguist. 16 (1): 22—29. Архів оригіналу за 28 серпня 2017. Процитовано 28 травня 2017. (англ.)

[2] Bouma, Gerlof (2009). Normalized (Pointwise) Mutual Information in Collocation Extraction (PDF). Proceedings of the Biennial GSCL Conference. Архів оригіналу (PDF) за 30 липня 2016. Процитовано 28 травня 2017. (англ.)

[3] Francois Role, Moahmed Nadif. Handling the Impact of Low frequency Events on Co-occurrence-based Measures of Word Similarity:A Case Study of Pointwise Mutual Information. [Архівовано 7 листопада 2016 у Wayback Machine.] Proceedings of KDIR 2011 : KDIR- International Conference on Knowledge Discovery and Information Retrieval, Paris, October 26-29 2011 (англ.)

[4] Paul L. Williams. INFORMATION DYNAMICS: ITS THEORY AND APPLICATION TO EMBODIED COGNITIVE SYSTEMS (PDF). Архів оригіналу (PDF) за 24 травня 2018. Процитовано 28 травня 2017. (англ.)

[1]

[2]

[3]

[4]