Informační zisk a vzájemná informace pro strojové učení

Poslední aktualizace 10. prosince 2020

Informační zisk vypočítává snížení entropie nebo překvapení z určité transformace souboru dat.

Běžně se používá při konstrukci rozhodovacích stromů z trénovacího souboru dat tak, že se vyhodnotí informační zisk pro každou proměnnou a vybere se proměnná, která maximalizuje informační zisk, což zase minimalizuje entropii a nejlépe rozdělí soubor dat do skupin pro efektivní klasifikaci.

Informační zisk lze také použít pro výběr příznaků tak, že se vyhodnotí zisk každé proměnné v kontextu cílové proměnné. V tomto trochu odlišném použití se výpočet označuje jako vzájemná informace mezi dvěma náhodnými proměnnými.

V tomto příspěvku se seznámíte s informačním ziskem a vzájemnou informací ve strojovém učení.

Po přečtení tohoto příspěvku budete vědět:

• Informační zisk je snížení entropie nebo překvapení transformací souboru dat a často se používá při trénování rozhodovacích stromů.
• Informační zisk se vypočítá porovnáním entropie souboru dat před transformací a po ní.
• Společná informace vypočítává statistickou závislost mezi dvěma proměnnými a je to název pro informační zisk, který se používá při výběru proměnných.

Začněte svůj projekt s mou novou knihou Pravděpodobnost pro strojové učení, která obsahuje návody krok za krokem a zdrojové soubory jazyka Python pro všechny příklady.

Začněme.

• Aktualizace listopad/2019: Vylepšen popis základů informace/entropie (díky HR).
• Aktualizace srpen/2020: Doplněny chybějící závorky do rovnice (díky Davidovi)

Přehled

Tento výukový kurz je rozdělen do pěti částí; jsou to:

1. Co je informační zisk
2. Pracovní příklad výpočtu informačního zisku
3. Příklady informačního zisku ve strojovém učení
4. Co je vzájemná informace?
5. Jak spolu souvisí informační zisk a vzájemná informace?

Co je informační zisk?

Informační zisk, zkráceně IG, měří snížení entropie nebo překvapení rozdělením souboru dat podle dané hodnoty náhodné proměnné.

Větší informační zisk naznačuje nižší entropii skupiny nebo skupin vzorků, a tedy menší překvapení.

Možná si vzpomenete, že informace kvantifikuje, jak překvapivá je událost v bitech. Události s nižší pravděpodobností mají větší informaci, události s vyšší pravděpodobností mají menší informaci. Entropie kvantifikuje, kolik informace je v náhodné veličině, přesněji v jejím pravděpodobnostním rozdělení. Šikmé rozdělení má nízkou entropii, zatímco rozdělení, kde mají události stejnou pravděpodobnost, má entropii větší.

V teorii informace rádi popisujeme „překvapivost“ události. Události s nízkou pravděpodobností jsou překvapivější, proto mají větší množství informace. Zatímco rozdělení pravděpodobnosti, kde jsou události stejně pravděpodobné, jsou překvapivější a mají větší entropii.

• Šikmé rozdělení pravděpodobnosti (nepřekvapivé):
• Vyvážené pravděpodobnostní rozdělení (překvapivé): vysoká entropie.

Další informace o základech informace a entropie naleznete ve výukovém programu:

• Šetrný úvod do informační entropie

Podívejme se nyní na entropii souboru dat.

O entropii souboru dat můžeme uvažovat ve smyslu pravděpodobnostního rozdělení pozorování v souboru dat patřících do jedné nebo druhé třídy, např. dvou tříd v případě binárního klasifikačního souboru dat.

Jednou z interpretací entropie z teorie informace je, že udává minimální počet bitů informace potřebných k zakódování klasifikace libovolného člena S (tj, člen S náhodně vybraný s rovnoměrnou pravděpodobností).

– Strana 58, Strojové učení, 1997.

Příklad v binárním klasifikačním problému (dvě třídy) můžeme vypočítat entropii vzorku dat takto:

• Entropie = -(p(0) * log(P(0)). + p(1) * log(P(1)))

Soubor dat s rozdělením vzorků pro obě třídy 50/50 by měl maximální entropii (maximální překvapení) 1 bit, zatímco nevyvážený soubor dat s rozdělením 10/90 by měl menší entropii, protože by bylo menší překvapení pro náhodně vybraný příklad ze souboru dat.

To můžeme demonstrovat na příkladu výpočtu entropie pro tento nevyvážený soubor dat v jazyce Python. Kompletní příklad je uveden níže.

Při spuštění příkladu vidíme, že entropie souboru dat pro binární klasifikaci je menší než 1 bit. To znamená, že k zakódování označení třídy pro libovolný příklad ze souboru dat je zapotřebí méně než jeden bit informace.

Takto lze entropii použít jako výpočet čistoty souboru dat, např.např. jak vyvážené je rozložení tříd.

Entropie 0 bitů označuje soubor dat obsahující jednu třídu; entropie 1 nebo více bitů naznačuje maximální entropii pro vyvážený soubor dat (v závislosti na počtu tříd), přičemž hodnoty mezi nimi označují úrovně mezi těmito extrémy.

Zisk informací poskytuje způsob, jak použít entropii k výpočtu, jak změna souboru dat ovlivní čistotu souboru dat, např. rozložení tříd. Menší entropie naznačuje větší čistotu nebo menší překvapení.

… informační zisk, je jednoduše očekávané snížení entropie způsobené rozdělením příkladů podle tohoto atributu.

– Strana 57, Strojové učení, 1997.

Například můžeme chtít vyhodnotit dopad na čistotu rozdělením souboru dat S pomocí náhodné proměnné s rozsahem hodnot.

To lze vypočítat takto:

• IG(S, a) = H(S) – H(S | a)

Kde IG(S, a) je informace pro soubor dat S pro náhodnou proměnnou a, H(S) je entropie pro soubor dat před jakoukoli změnou (popsanou výše) a H(S | a) je podmíněná entropie pro soubor dat vzhledem k proměnné a.

Tento výpočet popisuje zisk v souboru dat S pro proměnnou a. Je to počet bitů ušetřených při transformaci souboru dat.

Podmíněnou entropii lze vypočítat rozdělením souboru dat do skupin pro každou pozorovanou hodnotu proměnné a a výpočtem součtu poměru příkladů v každé skupině z celého souboru dat vynásobeného entropií každé skupiny.

• H(S | a) = součet v v a Sa(v)/S * H(Sa(v))

Kde Sa(v)/S je poměr počtu příkladů v souboru dat s proměnnou a s hodnotou v a H(Sa(v)) je entropie skupiny vzorků, kde proměnná a má hodnotu v.

To může znít trochu zmateně.

Výpočet informačního zisku si můžeme konkretizovat na příkladu z praxe.

Chcete se naučit pravděpodobnost pro strojové učení

Podstupte nyní můj bezplatný 7denní e-mailový rychlokurz (s ukázkovým kódem).

Klikněte pro registraci a získejte také bezplatnou elektronickou verzi kurzu ve formátu PDF.

Stáhněte si svůj minikurz ZDARMA

Pracovní příklad výpočtu informačního zisku

V této části si výpočet informačního zisku konkretizujeme na pracovním příkladu.

Můžeme definovat funkci pro výpočet entropie skupiny vzorků na základě poměru vzorků, které patří do třídy 0 a třídy 1.

Nyní uvažujme datovou sadu s 20 příklady, z nichž 13 patří do třídy 0 a 7 do třídy 1. Pro tento soubor dat můžeme vypočítat entropii, která bude mít méně než 1 bit.

Nyní uvažujme, že jedna z proměnných v souboru dat má dvě jedinečné hodnoty, řekněme „hodnota1“ a „hodnota2“. Zajímá nás výpočet informačního zisku této proměnné.

Předpokládejme, že pokud soubor dat rozdělíme podle hodnoty1, budeme mít skupinu osmi vzorků, sedm pro třídu 0 a jeden pro třídu 1.

Předpokládejme, že pokud soubor dat rozdělíme podle hodnoty2, budeme mít skupinu osmi vzorků. Můžeme tedy vypočítat entropii této skupiny vzorků.

Nyní předpokládejme, že soubor dat rozdělíme podle hodnoty2; máme skupinu 12 vzorků, v každé skupině je šest vzorků. Očekávali bychom, že tato skupina bude mít entropii 1.

Nakonec můžeme vypočítat informační zisk pro tuto proměnnou na základě skupin vytvořených pro každou hodnotu proměnné a vypočtené entropie.

První proměnná vedla ke skupině osmi vzorků ze souboru dat a druhá skupina měla zbývajících 12 vzorků v souboru dat. Máme tedy vše, co potřebujeme k výpočtu informačního zisku.

V tomto případě lze informační zisk vypočítat jako:

• Entropie(Dataset) – (Count(Group1) / Count(Dataset) * Entropie(Group1) + Count(Group2) / Count(Dataset) * Entropie(Group2))

nebo:

• Entropie(13/20, 7/20) – (8/20 * Entropie(7/8, 1/8) + 12/20 * Entropie(6/12, 6/12))

Nebo v kódu:

Kompletní příklad je uveden níže.

Nejprve se vypočítá entropie souboru dat na úrovni necelého 1 bitu. Poté se vypočítá entropie pro první a druhou skupinu na přibližně 0,5, resp. 1 bit.

Nakonec se vypočítá informační zisk proměnné na 0,117 bitu. To znamená, že zisk souboru dat jeho rozdělením prostřednictvím zvolené proměnné je 0,117 bitu.

Příklady informačního zisku ve strojovém učení

Snad nejpopulárnější využití informačního zisku ve strojovém učení je v rozhodovacích stromech.

Příkladem je algoritmus Iterative Dichotomiser 3, zkráceně ID3, používaný ke konstrukci rozhodovacího stromu.

Informační zisk je právě míra, kterou ID3 používá k výběru nejlepšího atributu v každém kroku růstu stromu.

– Strana 58, Strojové učení, 1997.

Informační zisk se počítá pro každou proměnnou v souboru dat. Proměnná, která má největší informační zisk, je vybrána pro rozdělení souboru dat. Obecně platí, že větší zisk znamená menší entropii nebo menší překvapení.

Všimněte si, že minimalizace entropie je ekvivalentní maximalizaci informačního zisku …

– Strana 547, Machine Learning: A Probabilistic Perspective, 2012.

Postup se pak opakuje na každé vytvořené skupině s vyloučením již vybrané proměnné. Tento postup se zastaví, jakmile je dosaženo požadované hloubky rozhodovacího stromu nebo není možné žádné další rozdělení.

Proces výběru nového atributu a rozdělení trénovacích příkladů se nyní opakuje pro každý nekoncový potomní uzel, tentokrát se použijí pouze trénovací příklady spojené s tímto uzlem. Atributy, které byly začleněny výše ve stromu, jsou vyloučeny, takže každý daný atribut se může na libovolné cestě stromem objevit nejvýše jednou.

– Strana 60, Strojové učení, 1997.

Informační zisk lze použít jako kritérium rozdělení ve většině moderních implementací rozhodovacích stromů, jako je například implementace algoritmu CART (Classification and Regression Tree) v knihovně strojového učení scikit-learn Python ve třídě DecisionTreeClassifier pro klasifikaci.

Toho lze dosáhnout nastavením argumentu kritéria na hodnotu „entropie“ při konfiguraci modelu; např:

Informační zisk lze také použít pro výběr příznaků před modelováním.

Spočívá ve výpočtu informačního zisku mezi cílovou proměnnou a každou vstupní proměnnou v trénovací množině dat. Pracovní prostředí pro strojové učení Weka poskytuje implementaci informačního zisku pro výběr příznaků prostřednictvím třídy InfoGainAttributeEval.

V tomto kontextu výběru příznaků lze informační zisk označit jako „vzájemnou informaci“ a vypočítat statistickou závislost mezi dvěma proměnnými. Příkladem použití informačního zisku (vzájemné informace) pro výběr příznaků je funkce mutual_info_classif() scikit-learn.

Co je to vzájemná informace?

Vzájemná informace se počítá mezi dvěma proměnnými a měří snížení nejistoty pro jednu proměnnou při známé hodnotě druhé proměnné.

Veličina zvaná vzájemná informace měří množství informace, kterou lze získat z jedné náhodné proměnné vzhledem k druhé.

– Strana 310, Data Mining: Praktické nástroje a techniky strojového učení, 4. vydání, 2016.

Vzájemnou informaci mezi dvěma náhodnými veličinami X a Y lze formálně vyjádřit takto:

• I(X ; Y) = H(X) – H(X | Y)

Kde I(X ; Y) je vzájemná informace pro X a Y, H(X) je entropie pro X a H(X | Y) je podmíněná entropie pro X vzhledem k Y. Výsledek má jednotky bitů.

Vzájemná informace je míra závislosti neboli „vzájemná závislost“ mezi dvěma náhodnými veličinami. Jako taková je tato míra symetrická, což znamená, že I(X ; Y) = I(Y ; X).

Měří průměrné snížení nejistoty o x, které vyplývá z poznání hodnoty y; nebo naopak průměrné množství informace, kterou x předává o y.

– Strana 139, Teorie informace, odvozování a algoritmy učení, 2003.

Kullback-Leiblerova neboli KL divergence je míra, která počítá rozdíl mezi dvěma rozděleními pravděpodobnosti.

Vzájemnou informaci lze také vypočítat jako KL divergenci mezi společným rozdělením pravděpodobnosti a součinem mezních pravděpodobností pro každou proměnnou.

Jestliže proměnné nejsou nezávislé, můžeme získat určitou představu o tom, zda jsou „blízko“ tomu, aby byly nezávislé, uvažováním Kullback-Leiblerovy divergence mezi společným rozdělením a součinem marginálních pravděpodobností, která se nazývá vzájemná informace mezi proměnnými

– Page 57, Pattern Recognition and Machine Learning, 2006.

Tu lze formálně vyjádřit takto:

• I(X ; Y) = KL(p(X, Y) || p(X) * p(Y))

Vzájemná informace je vždy větší nebo rovna nule, přičemž čím větší hodnota, tím větší je vztah mezi oběma proměnnými. Pokud je vypočtený výsledek roven nule, pak jsou proměnné nezávislé.

Vzájemná informace se často používá jako obecná forma korelačního koeficientu, např. míra závislosti mezi náhodnými proměnnými.

Používá se také jako aspekt v některých algoritmech strojového učení. Běžným příkladem je analýza nezávislých komponent, zkráceně ICA, která poskytuje projekci statisticky nezávislých komponent souboru dat.

Jak spolu souvisí informační zisk a vzájemná informace?

Vzájemná informace a informační zisk jsou totéž, ačkoli kontext nebo použití míry často vede k rozdílným názvům.

Například:

• Vliv transformací na soubor dat (rozhodovací stromy):
• Závislost mezi proměnnými (výběr příznaků): Vzájemná informace.

Všimněte si podobnosti způsobu výpočtu vzájemné informace a způsobu výpočtu informačního zisku; jsou rovnocenné:

• I(X ; Y) = H(X) – H(X | Y)

a

• IG(S, a) = H(S) – H(S | a)

Proto se vzájemná informace někdy používá jako synonymum pro informační zisk. Technicky vzato počítají stejnou veličinu, pokud jsou aplikovány na stejná data.

Vztah mezi nimi můžeme chápat tak, že čím větší je rozdíl ve společném a mezním rozdělení pravděpodobnosti (vzájemná informace), tím větší je zisk informace (informační zisk).

Další literatura

Tato část obsahuje další zdroje k tématu, pokud chcete jít hlouběji.

Knihy

• Information Theory, Inference, and Learning Algorithms, 2003.
• Machine Learning: A Probabilistic Perspective, 2012.
• Pattern Recognition and Machine Learning, 2006.
• Machine Learning, 1997.
• Data Mining: Practical Machine Learning Tools and Techniques, 4. vydání, 2016.

API

• scipy.stats.entropy API

Articles

• Entropie (teorie informace), Wikipedia.
• Informační zisk v rozhodovacích stromech, Wikipedia.
• Algoritmus ID3, Wikipedia.
• Poměr informačního zisku, Wikipedia.
• Vzájemná informace, Wikipedia.

Shrnutí

V tomto příspěvku jste objevili informační zisk a vzájemnou informaci ve strojovém učení.

Konkrétně jste se dozvěděli:

• Informační zisk je snížení entropie nebo překvapení transformací souboru dat a často se používá při trénování rozhodovacích stromů.
• Informační zisk se vypočítá porovnáním entropie souboru dat před transformací a po ní.
• Mutální informace vypočítává statistickou závislost mezi dvěma proměnnými a je to název pro informační zisk, který se používá při výběru proměnných.

Máte nějaké otázky?
Pokládejte své dotazy v komentářích níže a já se budu snažit odpovědět.

.