Informatiewinst en wederzijdse informatie voor machinaal leren

Laatst bijgewerkt op 10 december 2020

Informatiewinst berekent de vermindering in entropie of verrassing van het transformeren van een dataset op een bepaalde manier.

Het wordt gewoonlijk gebruikt bij de constructie van beslisbomen uit een trainingsdataset, door de informatiewinst voor elke variabele te evalueren, en de variabele te selecteren die de informatiewinst maximaliseert, die op zijn beurt de entropie minimaliseert en de dataset het best in groepen verdeelt voor effectieve classificatie.

Informatiewinst kan ook worden gebruikt voor kenmerkselectie, door de winst van elke variabele te evalueren in de context van de doelvariabele. In dit iets andere gebruik wordt de berekening wederzijdse informatie tussen de twee willekeurige variabelen genoemd.

In dit bericht ontdekt u informatiewinst en wederzijdse informatie in machinaal leren.

Na het lezen van deze post, zul je weten:

• Informatiewinst is de vermindering van entropie of verrassing door het transformeren van een dataset en wordt vaak gebruikt bij het trainen van beslisbomen.
• Informatiewinst wordt berekend door de entropie van de dataset vóór en na een transformatie te vergelijken.
• Mutual information berekent de statistische afhankelijkheid tussen twee variabelen en is de naam die wordt gegeven aan informatiewinst wanneer deze wordt toegepast op variabelenselectie.

Kick-start je project met mijn nieuwe boek Probability for Machine Learning, inclusief stap-voor-stap tutorials en de Python-broncodebestanden voor alle voorbeelden.

Let’s get started.

• Update Nov/2019: Verbeterde beschrijving van info/entropie-basics (bedankt HR).
• Update Aug/2020: Ontbrekende haakjes toegevoegd aan vergelijking (bedankt David)

Overzicht

Deze tutorial is onderverdeeld in vijf delen; deze zijn:

1. Wat is informatiewinst?
2. Werkvoorbeeld van berekening van informatiewinst
3. Voorbeelden van informatiewinst bij Machine Learning
4. Wat is wederzijdse informatie?
5. Hoe zijn informatiewinst en wederzijdse informatie verwant?

Wat is informatiewinst?

Informatiewinst, of kortweg IG, meet de vermindering in entropie of verrassing door het splitsen van een dataset volgens een gegeven waarde van een willekeurige variabele.

Een grotere informatiewinst suggereert een groep of groepen monsters met een lagere entropie, en dus minder verrassing.

Je herinnert je wellicht dat informatie kwantificeert hoe verrassend een gebeurtenis is in bits. Gebeurtenissen met een lagere waarschijnlijkheid hebben meer informatie, gebeurtenissen met een hogere waarschijnlijkheid hebben minder informatie. Entropie kwantificeert hoeveel informatie er in een willekeurige variabele zit, of meer bepaald in de waarschijnlijkheidsverdeling ervan. Een scheve verdeling heeft een lage entropie, terwijl een verdeling waarbij gebeurtenissen een gelijke waarschijnlijkheid hebben een grotere entropie heeft.

In de informatietheorie beschrijven we graag de “verrassing” van een gebeurtenis. Gebeurtenissen met een lage waarschijnlijkheid zijn verrassender en hebben daarom een grotere hoeveelheid informatie. Terwijl waarschijnlijkheidsverdelingen waarbij de gebeurtenissen even waarschijnlijk zijn, verrassender zijn en een grotere entropie hebben.

• Scheve waarschijnlijkheidsverdeling (niet verrassend): Lage entropie.
• Evenwichtige kansverdeling (verrassend): hoge entropie.

Voor meer over de grondbeginselen van informatie en entropie, zie de tutorial:

• Een voorzichtige inleiding tot informatie-entropie

Nu, laten we eens kijken naar de entropie van een dataset.

We kunnen de entropie van een gegevensreeks beschouwen als de kansverdeling van waarnemingen in de gegevensreeks die tot een bepaalde klasse behoren, bijvoorbeeld twee klassen in het geval van een binaire classificatiegegevensreeks.

Eén interpretatie van entropie uit de informatietheorie is dat zij het minimumaantal bits informatie aangeeft dat nodig is om de classificatie van een willekeurig lid van S te coderen (d.w.z, een willekeurig met uniforme waarschijnlijkheid getrokken lid van S.

– Page 58, Machine Learning, 1997.

Bijvoorbeeld, in een binair classificatieprobleem (twee klassen), kunnen we de entropie van het gegevensmonster als volgt berekenen:

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

Een dataset met een 50/50-verdeling van monsters voor de twee klassen zou een maximale entropie (maximale verrassing) van 1 bit hebben, terwijl een onevenwichtige dataset met een verdeling van 10/90 een kleinere entropie zou hebben omdat er minder verrassing zou zijn voor een willekeurig getrokken voorbeeld uit de dataset.

We kunnen dit demonstreren met een voorbeeld van de berekening van de entropie voor deze onevenwichtige dataset in Python. Het volledige voorbeeld staat hieronder.

Het uitvoeren van het voorbeeld, kunnen we zien dat de entropie van de dataset voor binaire classificatie minder dan 1 bit is. Dat wil zeggen dat er minder dan één bit aan informatie nodig is om het klasselabel voor een willekeurig voorbeeld uit de dataset te coderen.

Op deze manier kan entropie worden gebruikt als een berekening van de zuiverheid van een dataset, bijv.

Een entropie van 0 bits wijst op een dataset die één klasse bevat; een entropie van 1 of meer bits wijst op de maximale entropie voor een evenwichtige dataset (afhankelijk van het aantal klassen), met waarden daartussen die niveaus tussen deze uitersten aangeven.

Informatiewinst biedt een manier om entropie te gebruiken om te berekenen hoe een verandering in de dataset de zuiverheid van de dataset, bv. de verdeling van de klassen, beïnvloedt. Een kleinere entropie suggereert meer zuiverheid of minder verrassing.

… informatiewinst, is eenvoudigweg de verwachte vermindering in entropie veroorzaakt door het verdelen van de voorbeelden volgens dit attribuut.

– Page 57, Machine Learning, 1997.

Het is bijvoorbeeld mogelijk dat we de invloed op de zuiverheid willen evalueren door een dataset S te verdelen door middel van een willekeurige variabele met een bereik van waarden.

Dit kan als volgt worden berekend:

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

Waarbij IG(S, a) de informatie voor de dataset S voor de variabele a voor een willekeurige variabele is, H(S) de entropie voor de dataset vóór elke verandering (hierboven beschreven) en H(S | a) de voorwaardelijke entropie voor de dataset gegeven de variabele a.

Deze berekening beschrijft de winst in de dataset S voor de variabele a. Het is het aantal bits dat wordt bespaard bij de transformatie van de dataset.

De voorwaardelijke entropie kan worden berekend door de dataset op te splitsen in groepen voor elke waargenomen waarde van a en de som te berekenen van de verhouding van de voorbeelden in elke groep uit de gehele dataset, vermenigvuldigd met de entropie van elke groep.

• H(S | a) = som v in a Sa(v)/S * H(Sa(v))

Waarbij Sa(v)/S de verhouding is van het aantal voorbeelden in de dataset waarbij variabele a de waarde v heeft, en H(Sa(v)) de entropie is van de groep voorbeelden waarbij variabele a de waarde v heeft.

Dit klinkt misschien een beetje verwarrend.

We kunnen de berekening van de informatiewinst concreet maken met een uitgewerkt voorbeeld.

Wil je Kansberekening leren voor Machine Learning

Doe nu mee aan mijn gratis 7-daagse spoedcursus per e-mail (met voorbeeldcode).

Klik om je aan te melden en ontvang ook een gratis PDF Ebook versie van de cursus.

Download Je GRATIS Mini-Cursus

Werkvoorbeeld van het berekenen van informatiewinst

In dit deel zullen we de berekening van informatiewinst concreet maken met een uitgewerkt voorbeeld.

We kunnen een functie definiëren om de entropie van een groep monsters te berekenen op basis van de verhouding van monsters die tot klasse 0 en klasse 1 behoren.

Nu, beschouw een dataset met 20 voorbeelden, 13 voor klasse 0 en 7 voor klasse 1. We kunnen de entropie voor deze dataset berekenen, die minder dan 1 bit zal hebben.

Neem nu in overweging dat een van de variabelen in de dataset twee unieke waarden heeft, zeg “waarde1” en “waarde2.” We zijn geïnteresseerd in het berekenen van de informatiewinst van deze variabele.

Laten we aannemen dat als we de dataset splitsen op waarde1, we een groep van acht monsters hebben, zeven voor klasse 0 en één voor klasse 1. We kunnen dan de entropie van deze groep monsters berekenen.

Nemen we nu aan dat we de dataset splitsen op waarde2; dan hebben we een groep van 12 monsters met zes in elke groep. We zouden verwachten dat deze groep een entropie van 1 heeft.

Tot slot kunnen we de informatiewinst voor deze variabele berekenen op basis van de groepen die zijn gemaakt voor elke waarde van de variabele en de berekende entropie.

De eerste variabele resulteerde in een groep van acht voorbeelden uit de dataset, en de tweede groep had de resterende 12 monsters in de dataset. We hebben dus alles wat we nodig hebben om de informatiewinst te berekenen.

In dit geval kan de informatiewinst worden berekend als:

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

Of:

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

Of in code:

Hierna volgt het volledige voorbeeld.

Eerst wordt de entropie van de dataset berekend op iets minder dan 1 bit. Vervolgens wordt de entropie voor de eerste en de tweede groep berekend op respectievelijk ongeveer 0,5 en 1 bit.

Tot slot wordt de informatiewinst voor de variabele berekend op 0,117 bit. Dat wil zeggen dat de winst voor de dataset door deze via de gekozen variabele te splitsen 0,117 bits bedraagt.

Voorbeelden van Information Gain in Machine Learning

Het meest populaire gebruik van information gain in machine learning is misschien wel in beslisbomen.

Een voorbeeld is het Iterative Dichotomiser 3 algoritme, kortweg ID3, dat wordt gebruikt om een beslisboom te construeren.

Informatiewinst is precies de maatstaf die door ID3 wordt gebruikt om bij elke stap in de groei van de boom het beste attribuut te selecteren.

– Page 58, Machine Learning, 1997.

De informatiewinst wordt berekend voor elke variabele in de dataset. De variabele met de grootste informatiewinst wordt geselecteerd om de dataset op te splitsen. Over het algemeen duidt een grotere winst op een kleinere entropie of minder verrassing.

Merk op dat het minimaliseren van de entropie gelijkstaat aan het maximaliseren van de informatiewinst …

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

Het proces wordt vervolgens herhaald op elke gecreëerde groep, met uitsluiting van de variabele die al was gekozen. Dit stopt zodra een gewenste diepte van de beslisboom is bereikt of geen splitsingen meer mogelijk zijn.

Het proces van het selecteren van een nieuw attribuut en het partitioneren van de trainingsvoorbeelden wordt nu herhaald voor elk niet-terminale afgeleide knooppunt, waarbij dit keer alleen de trainingsvoorbeelden worden gebruikt die aan dat knooppunt zijn gekoppeld. Attributen die hoger in de boom zijn opgenomen, worden uitgesloten, zodat elk gegeven attribuut maximaal één keer kan voorkomen langs elk pad door de boom.

– Page 60, Machine Learning, 1997.

Informatiewinst kan worden gebruikt als een splitsingscriterium in de meeste moderne implementaties van beslisbomen, zoals de implementatie van het Classification and Regression Tree (CART)-algoritme in de scikit-learn Python-bibliotheek voor machinaal leren in de klasse DecisionTreeClassifier voor classificatie.

Dit kan worden bereikt door het criteriumargument in te stellen op “entropie” bij het configureren van het model; bijvoorbeeld:

Informatiewinst kan ook worden gebruikt voor kenmerkselectie voorafgaand aan modellering.

Het houdt in dat de informatiewinst tussen de doelvariabele en elke invoervariabele in de trainingsdataset wordt berekend. De Weka machine learning workbench biedt een implementatie van informatiewinst voor feature selectie via de InfoGainAttributeEval klasse.

In deze context van feature selectie, kan informatiewinst worden aangeduid als “wederzijdse informatie” en berekent de statistische afhankelijkheid tussen twee variabelen. Een voorbeeld van het gebruik van informatiewinst (wederzijdse informatie) voor feature selectie is de mutual_info_classif() scikit-learn functie.

Wat is wederzijdse informatie?

Wederzijdse informatie wordt berekend tussen twee variabelen en meet de vermindering van de onzekerheid voor een variabele gegeven een bekende waarde van de andere variabele.

Een grootheid die wederzijdse informatie wordt genoemd, meet de hoeveelheid informatie die kan worden verkregen uit een willekeurige variabele gegeven een andere.

– Bladzijde 310, Data Mining: Practical Machine Learning Tools and Techniques, 4e editie, 2016.

De wederzijdse informatie tussen twee willekeurige variabelen X en Y kan formeel als volgt worden weergegeven:

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

Waarbij I(X ; Y) de wederzijdse informatie voor X en Y is, H(X) de entropie voor X en H(X | Y) de conditionele entropie voor X gegeven Y. Het resultaat heeft de eenheid bits.

Wederzijdse informatie is een maat voor de afhankelijkheid of “wederzijdse afhankelijkheid” tussen twee willekeurige variabelen. Als zodanig is de maat symmetrisch, hetgeen betekent dat I(X ; Y) = I(Y ; X).

Zij meet de gemiddelde vermindering van de onzekerheid over x die het gevolg is van het leren van de waarde van y; of omgekeerd, de gemiddelde hoeveelheid informatie die x over y verschaft.

– Bladzijde 139, Information Theory, Inference, and Learning Algorithms, 2003.

Kullback-Leibler, of KL, divergentie is een maat die het verschil tussen twee kansverdelingen berekent.

De wederzijdse informatie kan ook worden berekend als de KL divergentie tussen de gezamenlijke kansverdeling en het product van de marginale kansen voor elke variabele.

Als de variabelen niet onafhankelijk zijn, kunnen we een idee krijgen of ze “bijna” onafhankelijk zijn door te kijken naar de Kullback-Leibler divergentie tussen de gezamenlijke verdeling en het product van de marginalen, wat de wederzijdse informatie tussen de variabelen wordt genoemd

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

Dit kan formeel als volgt worden gesteld:

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

Wederzijdse informatie is altijd groter dan of gelijk aan nul, waarbij geldt dat hoe groter de waarde is, des te groter de relatie tussen de twee variabelen. Als het berekende resultaat nul is, dan zijn de variabelen onafhankelijk.

Mutuele informatie wordt vaak gebruikt als een algemene vorm van een correlatiecoëfficiënt, bijvoorbeeld een maat voor de afhankelijkheid tussen willekeurige variabelen.

Het wordt ook gebruikt als een aspect in sommige algoritmen voor machinaal leren. Een veelvoorkomend voorbeeld is de Independent Component Analysis, kortweg ICA, die een projectie oplevert van statistisch onafhankelijke componenten van een dataset.

Hoe zijn Information Gain en Mutual Information aan elkaar gerelateerd?

Mutual Information en Information Gain zijn hetzelfde, hoewel de context of het gebruik van de maat vaak aanleiding geeft tot de verschillende benamingen.

Bijvoorbeeld:

• Effect van transformaties op een dataset (beslisbomen): Information Gain.
• Afhankelijkheid tussen variabelen (feature selection): Wederzijdse Informatie.

Merk de overeenkomst op in de manier waarop de wederzijdse informatie wordt berekend en de manier waarop de informatiewinst wordt berekend; ze zijn equivalent:

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

en

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

Zo wordt wederzijdse informatie soms gebruikt als synoniem voor informatiewinst. Technisch gezien berekenen zij dezelfde grootheid indien toegepast op dezelfde gegevens.

We kunnen het verband tussen de twee opvatten als hoe groter het verschil in de gezamenlijke en de marginale kansverdelingen (wederzijdse informatie), hoe groter de informatiewinst (informatiewinst).

Verder lezen

In dit gedeelte vindt u meer bronnen over dit onderwerp als u dieper op het onderwerp wilt ingaan.

Boeken

• 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, 4e editie, 2016.

API

• scipy.stats.entropy API

Artikels

• Entropie (informatietheorie), Wikipedia.
• Informatiewinst in beslisbomen, Wikipedia.
• ID3 algoritme, Wikipedia.
• Informatiewinstverhouding, Wikipedia.
• Wederzijdse informatie, Wikipedia.

Samenvatting

In dit bericht ontdekte u informatiewinst en wederzijdse informatie in machine learning.

Specifiek leerde u:

• Informatiewinst is de vermindering van entropie of verrassing door een dataset te transformeren en wordt vaak gebruikt bij het trainen van beslisbomen.
• Informatiewinst wordt berekend door de entropie van de dataset voor en na een transformatie te vergelijken.
• Mutual information berekent de statistische afhankelijkheid tussen twee variabelen en is de naam die wordt gegeven aan informatiewinst wanneer deze wordt toegepast op variabelenselectie.

Heeft u nog vragen?
Stel uw vragen in de reacties hieronder en ik zal mijn best doen om ze te beantwoorden.