Взаємна інформація

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Діаграма Венна різних мір інформації, пов'язаних із корельованими величинами X та Y. Область, яка міститься в обох колах, є спільною ентропією Η(X,Y). Коло ліворуч (червоний і фіолетовий) є особистою ентропією Η(X), в якому червоне є умовною ентропією Η(X|Y). Коло праворуч (синій та фіолетовий) є Η(Y), а синє в ньому є Η(Y|X). Фіолетове є взаємною інформацією I(X;Y).

У теорії ймовірностей та теорії інформації взає́мна інформа́ція (англ. mutual information, MI) двох випадкових величин — це міра взаємної залежності між цими двома величинами. Конкретніше, вона визначає «кількість інформації» (в таких одиницях, як біти), отримуваної про одну випадкову величину через іншу випадкову величину. Поняття взаємної інформації нерозривно пов'язане з ентропією випадкової величини, фундаментальним поняттям теорії інформації, яке визначає «кількість інформації», яка міститься у випадковій величині.

Не обмежуючись дійснозначними випадковими величинами, такими як коефіцієнт кореляції, взаємна інформація є загальнішою, і визначає, наскільки подібним є спільний розподіл p(X,Y) до добутків розкладених відособлених розподілів p(X)p(Y). Взаємна інформація — це математичне сподівання поточкової взаємної інформації[en] (англ. pointwise mutual information, PMI). Найпоширенішою одиницею вимірювання взаємної інформації є біт.

Визначення взаємної інформації[ред.ред. код]

Формально взаємну інформацію двох дискретних випадкових величин X та Y може бути визначено як

де p(x,y) є функцією спільного розподілу ймовірностей X та Y, а  та  є функціями відособлених розподілів імовірності X та Y відповідно.

У випадку неперервних випадкових величин підсумовування замінюється визначеним подвійним інтегралом:

де p(x,y) тепер є функцією густини спільної ймовірності X та Y, а та  є функціями густини відособлених імовірностей X та Y відповідно.

Якщо застосовується логарифм за основою 2, то одиницею вимірювання взаємної інформації є біт.

Інтуїтивно, взаємна інформація вимірює інформацію, яку поділяють X та Y: вона вимірює, наскільки знання однієї з цих величин зменшує невизначеність щодо іншої. Наприклад, якщо X та Y є незалежними, то знання X не дає жодної інформації про Y, і навпаки, тому їхня взаємна інформація дорівнює нулеві. З іншого боку, якщо X є детермінованою функцією від Y, і Y є детермінованою функцією від X, то вся інформація, яка передається X, є спільною з Y: знання X визначає значення Y, і навпаки. В результаті, в цьому випадку взаємна інформація є тим же, що й невизначеність, яка міститься окремо в Y (або X), а саме, ентропією Y (або X). Крім того, ця взаємна інформація є такою ж, як і ентропія X та як ентропія Y. (Дуже особливим випадком цього є такий, коли X та Y є однією й тією ж випадковою величиною.)

Взаємна інформація є мірою притаманної залежності, вираженої в спільному розподілі X та Y, по відношенню до спільного розподілу X та Y за припущення незалежності. Взаємна інформація відтак вимірює залежність у наступному сенсі: I(X; Y) = 0, якщо і лише якщо X та Y є незалежними випадковими величинами. Це легко побачити в одному напрямку: якщо X та Y є незалежними, то p(x,y) = p(x) p(y), і тому

Крім того, взаємна інформація є невід'ємною (тобто, I(X;Y) ≥ 0; див. нижче) і симетричною[en] (тобто, I(X;Y) = I(Y;X)).

Відношення до інших величин[ред.ред. код]

Взаємну інформацію може бути рівнозначно виражено як

де та  є відособленими ентропіями, Η(X|Y) та Η(Y|X) є умовними ентропіями, а Η(X,Y) є спільною ентропією X та Y. Зверніть увагу на аналогію з об'єднанням, різницею та перетином двох множин, яку показано в діаграмі Венна.

Застосовуючи нерівність Єнсена до визначення взаємної інформації, можна показати, що I(X;Y) є невід'ємною, отже, . Тут ми наводимо докладне виведення I(X;Y) = Η(Y) – Η(Y|X):

Доведення інших наведених вище тотожностей є схожими на це.

Інтуїтивно, якщо ентропія Η(Y) розглядається як міра невизначеності випадкової величини, то Η(Y|X) є мірою того, що X не каже стосовно Y. Це є «кількістю невизначеності Y, яка залишається після того, як стала відомою X», і, отже, праву частину першого з цих рівнянь можна читати як «кількість невизначеності Y за вирахуванням кількості невизначеності Y, яка залишається після того, як стала відомою , що рівнозначно «кількість невизначеності Y, яка усувається, коли стає відомою X». Це підтримує інтуїтивне значення взаємної інформації як кількості інформації (тобто, зниження невизначеності), яке знання однієї з величин забезпечує стосовно іншої.

Зауважте, що в дискретному випадку Η(X|X) = 0 і, отже, Η(X) = I(X;X). Таким чином, I(X;X) ≥ I(X;Y), і можна сформулювати основний принцип, що величина містить про себе щонайменше стільки ж інформації, скільки могла би забезпечити будь-яка інша величина.

Взаємну інформацію також може бути виражено як відстань Кульбака — Лейблера добутку p(x) × p(y) відособлених розподілів двох випадкових величин x та y від спільного розподілу цих випадкових величин p(x,y):

Крім того, нехай p(x|y) = p(x, y) / p(y). Тоді

Зауважте, що тут відстань Кульбака — Лейблера передбачає інтегрування лише за випадковою величиною X, і вираз тепер є випадковою величиною в Y. Таким чином, взаємну інформацію можна також розуміти як математичне сподівання відстані Кульбака — Лейблера одновимірного розподілу[en] p(X) величини X від умовного розподілу p(x|y) величини X відносно Y: що більш відмінними в середньому є розподіли p(x|y) та p(x), то більшим є приріст інформації.

Варіації взаємної інформації[ред.ред. код]

Для задоволення різних потреб було запропоновано кілька варіацій взаємної інформації. Серед них є нормалізовані варіанти та узагальнення до понад двох величин.

Метрика[ред.ред. код]

Багато застосувань вимагають метрики[en], тобто міри відстань між парами точок. Величина

задовольняє властивості метрики (нерівність трикутника, невід'ємність[en], нерозрізнюваність[en] та симетрію). Ця метрика відстані також відома як різновидність інформації[en].

Якщо  є дискретними випадковими величинами, то всі члени ентропії є невід'ємними, тому  і можна визначити унормовану відстань

Метрика D є універсальною метрикою, в тому сенсі, що якщо будь-яка інша міра відстані розмістить X та Y поруч, то й D також розглядатиме їх як близькі.[1][сумнівно ]

Підключення визначень показує, що

У теоретико-множинній інтерпретації інформації (див. малюнок в умовній ентропії) це є фактично відстанню Жаккара між X та Y.

Нарешті,

також є метрикою.

Умовна взаємна інформація[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Умовна взаємна інформація[en].

Іноді корисно виражати взаємну інформацію двох випадкових величин відносно третьої.

що може бути спрощено як

Обумовлювання третьою випадковою величиною може збільшувати або зменшувати взаємну інформацію, але завжди залишається істинним те, що

для дискретних спільно розподілених випадкових величин X, Y та Z. Цей результат застосовувався як основний будівельний блок для доведення інших нерівностей в теорії інформації[en].

Багатовимірна взаємна інформація[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Багатовимірна взаємна інформація[en].

Було запропоновано декілька узагальнень взаємної інформації для понад двох випадкових величин, такі як повна кореляція[en] та інформація взаємодії[en]. Якщо розглядати ентропію Шеннона як знакову міру[en] в контексті інформаційних діаграм[en], як описано в статті «Теорія інформації та теорія міри[en]», то єдиним визначенням багатовимірної взаємної інформації, яке має сенс,[Джерело?] є наступне:

і для 

де (як вище) ми визначаємо

(Це визначення багатовимірної взаємної інформації є ідентичним визначенню інформації взаємодії[en], за виключенням зміни знаку, коли число випадкових величин є непарним.)

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

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

Одна зі схем багатовимірного узагальнення, яка максимізує взаємну інформацію між спільним розподілом та іншими цільовими величинами, виявилася корисною у виборі ознак.[2]

Взаємна інформація також застосовується в галузі обробки сигналів як міра схожості двох сигналів. Наприклад, метрика взаємної інформації ознак (англ. FMI, feature mutual information)[3] — це міра продуктивності злиття зображень, яка застосовує взаємну інформацію для вимірювання кількості інформації, яку злите зображення містить про первинні зображення. Код MATLAB для цієї метрики можна знайти за адресою [4].

Унормовані варіанти[ред.ред. код]

Унормовані варіанти взаємної інформації забезпечуються коефіцієнтами обмеження,[5] коефіцієнтом невизначеності[en][6] або вправністю (англ. proficiency):[7]

і

Ці два коефіцієнти не обов'язково дорівнюють один одному. В деяких випадках може бути бажаною симетрична міра, така як наступна міра надлишковості (англ. redundancy):[ред.]

яка досягає нульового мінімуму, коли величини є незалежними, і максимального значення

коли одна з величин стає абсолютно надлишковою при знанні іншої. Див. також надлишковість (теорія інформації). Іншою симетричною мірою є симетрична невизначеність (Witten та Frank, 2005), яка задається як

що являє собою зважене усереднення двох коефіцієнтів невизначеності.[6]

Якщо розглядати взаємну інформацію як окремий випадок повної кореляції[en] або двоїстої повної кореляції[en], то унормованими версіями відповідно є

і

Нарешті, існує унормування,[8] яке випливає з першого розгляду взаємної інформації як аналогу коваріації (таким чином ентропії Шеннона є аналогом дисперсії). Потім унормована взаємна інформація розраховується подібно до коефіцієнту кореляції Пірсона,

Зважені варіанти[ред.ред. код]

В традиційному формулюванні взаємної інформації

кожна подія чи об'єкт, вказані як , зважуються відповідною ймовірністю . Це передбачає, що всі об'єкти або події є рівнозначними без врахування ймовірностей їх настання. Проте в деяких застосуваннях може бути так, що певні об'єкти або події є більш значущими, ніж інші, або що деякі шаблони зв'язків є семантично важливішими за інші.

Наприклад, детерміноване відображення може розглядатися як сильніше за детерміноване відображення , хоча ці відношення видадуть однакову взаємну інформацію. Це відбувається тому, що взаємна інформація взагалі не чутлива до жодного природного впорядкування значень величин (Cronbach 1954, Coombs, Dawes & Tversky 1970, Lockhead 1970), і тому взагалі не чутлива до форми відносного відображення між зв'язаними величинами. Якщо бажано, щоби перше відношення — яке показує узгодженість за всіма значеннями величин — оцінювалося вище, ніж друге відношення, то можна використовувати наступну зважену взаємну інформацію (Guiasu, 1977).

яка поміщає вагу  на імовірність кожного збігу значень величин, . Це дозволяє робити так, щоби деякі ймовірності могли нести більше або менше важливості за інші, тим самим дозволяючи кількісно виразити відповідні чинники цілісності (англ. holistic) або виразності (нім. prägnanz). У наведеному вище прикладі застосування більших відносних ваг для , і матиме ефект вищої оцінки інформативності для відношення , ніж для відношення , що може бути бажаним в деяких випадках розпізнавання образів тощо. Ця зважена взаємна інформація є вираженням зваженої відстані Кульбака — Лейблера, яка, як відомо, може набувати від'ємних значень для деяких входів,[9] і є приклади, де зважена взаємна інформація також набуває від'ємних значень.[10]

Скоригована взаємна інформація[ред.ред. код]

Детальніші відомості з цієї теми Ви можете знайти в статті Скоригована взаємна інформація[en].

Розподіл імовірності можна розглядати як розбиття множини. Можна запитати: якщо множину було розбито випадковим чином, яким буде розподіл імовірностей? Яким буде математичне сподівання взаємної інформації? Скоригована взаємна інформація[en] (англ. adjusted mutual information, AMI) віднімає математичне сподівання взаємної інформації таким чином, що вона дорівнює нулеві, коли два різних розподіли носять випадковий характер, і одиниці, коли два розподіли збігаються. Скоригована взаємна інформація визначається за аналогією зі скоригованим індексом Ренда[en] двох різних розбиттів множини.

Абсолютна взаємна інформація[ред.ред. код]

З допомогою ідей колмогоровської складності можна розглядати взаємну інформацію двох послідовностей незалежно від будь-якого розподілу ймовірностей:

Встановлення того, що ця величина є симетричною з точністю до логарифмічного множника (), потребує ланцюгового правила для колмогоровскої складності[en] (Li та Vitányi, 1997). Наближення цієї величини через стиснення може може застосовуватися для визначення міри відстані[en] для виконання ієрархічного кластерування послідовностей без жодного знання про предметну область цих послідовностей (Cilibrasi та Vitányi, 2005).

Взаємна інформація та лінійна кореляція[ред.ред. код]

На відміну від коефіцієнтів кореляції, наприклад, коефіцієнту кореляції моменту добутку, взаємна інформація містить інформацію про всю залежність — лінійну і нелінійну, — а не просто про лінійну залежність, як міри коефіцієнтів кореляції. Тим не менш, у вузькому випадку, в якому відособлені розподіли для X та Y розподілені нормально, і їхній спільний розподіл є двовимірним нормальним розподілом, існує точний взаємозв'язок між I та коефіцієнтом кореляції (Гельфанд та Яглом, 1957).

Взаємна інформація для дискретних даних[ред.ред. код]

Коли X та Y обмежено перебуванням у дискретному числі станів, то дані спостережень підсумовуються до таблиці спряженості[en] зі змінною рядків X (або i) та змінною стовпців Y (або j). Взаємна інформація є однією з мір асоційовності або кореляції між змінними рядків і стовпців. Інші міри асоційовності включають статистики критерію хі-квадрат Пірсона, статистики G-критерію[en] тощо. Фактично, взаємна інформація дорівнює статистиці G-критерію[en], поділеній на 2N, де N є розміром вибірки.

В особливому випадку, коли числом станів для змінних як рядків, так і стовпців є 2 (i,j=1,2), числом ступенів свободи[en] критерію хі-квадрат Пірсона є 1. З чотирьох доданків суми

незалежним є лише один. Це є причиною того, що функція взаємної інформації має точний зв'язок з кореляційною функцією для двійкових послідовностей.[11]

Застосування взаємної інформації[ред.ред. код]

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Kraskov, Alexander; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (2003). «Hierarchical Clustering Based on Mutual Information». arXiv:q-bio/0311039.  (англ.)
  2. Christopher D. Manning; Prabhakar Raghavan; Hinrich Schütze (2008). An Introduction to Information Retrieval. Cambridge University Press. ISBN 0-521-86571-9.  (англ.)
  3. Haghighat, M. B. A.; Aghagolzadeh, A.; Seyedarabi, H. (2011). «A non-reference image fusion metric based on mutual information of image features». Computers & Electrical Engineering 37 (5): 744–756. doi:10.1016/j.compeleceng.2011.07.012.  (англ.)
  4. http://www.mathworks.com/matlabcentral/fileexchange/45926-feature-mutual-information-fmi-image-fusion-metric
  5. Coombs, Dawes та Tversky, 1970
  6. а б Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). Section 14.7.3. Conditional Entropy and Mutual Information. Numerical Recipes: The Art of Scientific Computing (вид. 3rd). New York: Cambridge University Press. ISBN 978-0-521-88068-8.  (англ.)
  7. White, Jim; Steingold, Sam; Fournelle, Connie. Performance Metrics for Group-Detection Algorithms. http://www.interfacesymposia.org/I04/I2004Proceedings/WhiteJim/WhiteJim.paper.pdf.  (англ.)
  8. Strehl, Alexander; Ghosh, Joydeep (2002). Cluster Ensembles – A Knowledge Reuse Framework for Combining Multiple Partitions. The Journal of Machine Learning Research 3 (Dec): 583–617.  (англ.)
  9. Kvålseth, T. O. (1991). «The relative useful information measure: some comments». Information sciences 56 (1): 35–38. doi:10.1016/0020-0255(91)90022-m.  (англ.)
  10. Pocock, A. (2012). Feature Selection Via Joint Likelihood (PDF) (Thesis). (англ.)
  11. Wentian Li (1990). «Mutual information functions versus correlation functions». J. Stat. Phys. 60 (5-6): 823–837. doi:10.1007/BF01025996.  (англ.)
  12. Parsing a Natural Language Using Mutual Information Statistics by David M. Magerman and Mitchell P. Marcus (англ.)
  13. Hugh Everett Theory of the Universal Wavefunction, Thesis, Princeton University, (1956, 1973), pp 1–140 (page 30) (англ.)
  14. Everett, Hugh (1957). «Relative State Formulation of Quantum Mechanics». Reviews of Modern Physics 29: 454–462. doi:10.1103/revmodphys.29.454. http://www.univer.omsk.su/omsk/Sci/Everett/paper1957.html.  (англ.)

Джерела[ред.ред. код]

Література[ред.ред. код]

  • Габидулин, Э. М., Пилипчук, Н. И. Лекции по теории информации. — М.: МФТИ, 2007. — 214 с. — ISBN 5-7417-0197-3 (рос.)