Informationsgevinst og gensidig information til maskinlæring

Sidst opdateret den 10. december 2020

Informationsgevinst beregner reduktionen i entropi eller overraskelse ved at transformere et datasæt på en eller anden måde.

Det bruges almindeligvis i konstruktionen af beslutningstræer fra et træningsdatasæt ved at evaluere informationsgevinsten for hver variabel og vælge den variabel, der maksimerer informationsgevinsten, hvilket igen minimerer entropien og bedst opdeler datasættet i grupper til effektiv klassificering.

Informationsgevinsten kan også bruges til valg af funktioner ved at evaluere gevinsten for hver variabel i forbindelse med målvariablen. I denne lidt anderledes anvendelse betegnes beregningen som gensidig information mellem de to tilfældige variabler.

I dette indlæg vil du opdage informationsforøgelse og gensidig information i maskinlæring.

Når du har læst dette indlæg, vil du vide:

• Informationsgevinst er reduktionen i entropi eller overraskelse ved at transformere et datasæt og bruges ofte til træning af beslutningstræer.
• Informationsgevinst beregnes ved at sammenligne entropien af datasættet før og efter en transformation.
• Mutual information beregner den statistiske afhængighed mellem to variabler og er betegnelsen for informationsgevinst, når den anvendes til valg af variabler.

Kick-start dit projekt med min nye bog Probability for Machine Learning, herunder trinvise vejledninger og Python-kildekodefilerne til alle eksempler.

Lad os komme i gang.

• Opdatering nov/2019: Forbedret beskrivelsen af info/entropi grundprincipper (tak HR).
• Opdatering aug/2020: Tilføjet manglende parenteser til ligningen (tak David)

Overblik

Denne vejledning er opdelt i fem dele; de er:

1. Hvad er informationsgevinst?
2. Arbejdet eksempel på beregning af informationsgevinst
3. Eksempler på informationsgevinst i maskinlæring
4. Hvad er gensidig information?
5. Hvordan er informationsgevinst og gensidig information relateret?

Hvad er informationsgevinst?

Informationsgevinst, eller forkortet IG, måler reduktionen i entropi eller overraskelse ved at opdele et datasæt i henhold til en given værdi af en tilfældig variabel.

En større informationsgevinst tyder på en gruppe eller grupper af prøver med lavere entropi og dermed mindre overraskelse.

Du husker måske, at information kvantificerer, hvor overraskende en begivenhed er i bits. Begivenheder med lavere sandsynlighed har mere information, begivenheder med højere sandsynlighed har mindre information. Entropi kvantificerer, hvor meget information der er i en tilfældig variabel, eller mere specifikt dens sandsynlighedsfordeling. En skæv fordeling har en lav entropi, mens en fordeling, hvor begivenhederne har samme sandsynlighed, har en større entropi.

I informationsteorien kan vi godt lide at beskrive “overraskelsen” ved en begivenhed. Begivenheder med lav sandsynlighed er mere overraskende og har derfor en større mængde information. Hvorimod sandsynlighedsfordelinger, hvor begivenhederne er lige sandsynlige, er mere overraskende og har større entropi.

• Skæv sandsynlighedsfordeling (uoverraskende): Lav entropi.
• Balanceret sandsynlighedsfordeling (overraskende): Høj entropi.

For mere om de grundlæggende principper for information og entropi, se vejledningen:

• En blid introduktion til informationsentropi

Nu skal vi se på entropien for et datasæt.

Vi kan tænke på entropien af et datasæt i form af sandsynlighedsfordelingen af observationer i datasættet, der tilhører den ene eller den anden klasse, f.eks. to klasser i tilfælde af et binært klassifikationsdatasæt.

En fortolkning af entropi fra informationsteorien er, at den angiver det mindste antal bits information, der er nødvendigt for at kode klassifikationen af et vilkårligt medlem af S (dvs, et medlem af S, der trækkes tilfældigt med ensartet sandsynlighed).

– Side 58, Machine Learning, 1997.

For eksempel kan vi i et binært klassifikationsproblem (to klasser) beregne entropien for dataprøven som følger:

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

Et datasæt med en 50/50-opdeling af prøverne for de to klasser ville have en maksimal entropi (maksimal overraskelse) på 1 bit, hvorimod et ubalanceret datasæt med en opdeling på 10/90 ville have en mindre entropi, da der ville være mindre overraskelse for et tilfældigt udtrukket eksempel fra datasættet.

Vi kan demonstrere dette med et eksempel på beregning af entropien for dette ubalancerede datasæt i Python. Det komplette eksempel er anført nedenfor.

Ved udførelse af eksemplet kan vi se, at entropien for datasættet til binær klassifikation er mindre end 1 bit. Det vil sige, at der kræves mindre end én bit information for at kode klasseetiketten for et vilkårligt eksempel fra datasættet.

På denne måde kan entropi bruges som en beregning af renheden af et datasæt, e.f.eks. hvor afbalanceret fordelingen af klasser tilfældigvis er.

En entropi på 0 bit angiver et datasæt, der indeholder én klasse; en entropi på 1 eller flere bit antyder maksimal entropi for et afbalanceret datasæt (afhængigt af antallet af klasser), med værdier derimellem, der angiver niveauer mellem disse ekstremer.

Informationsgevinst giver en måde at bruge entropi til at beregne, hvordan en ændring af datasættet påvirker datasættets renhed, f.eks. fordelingen af klasser. En mindre entropi tyder på mere renhed eller mindre overraskelse.

… informationsgevinst, er simpelthen den forventede reduktion i entropi forårsaget af at opdele eksemplerne i henhold til denne egenskab.

– Side 57, Machine Learning, 1997.

For eksempel kan vi ønske at evaluere virkningen på renheden ved at opdele et datasæt S med en tilfældig variabel med et interval af værdier.

Dette kan beregnes som følger:

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

Hvor IG(S, a) er informationen for datasættet S for variablen a for en tilfældig variabel, H(S) er entropien for datasættet før enhver ændring (beskrevet ovenfor), og H(S | a) er den betingede entropi for datasættet givet variablen a.

Denne beregning beskriver gevinsten i datasættet S for variablen a. Det er det antal bits, der spares ved transformation af datasættet.

Den betingede entropi kan beregnes ved at opdele datasættet i grupper for hver observeret værdi af a og beregne summen af forholdet mellem eksemplerne i hver gruppe ud af hele datasættet multipliceret med entropien for hver gruppe.

• H(S | a) = sum v i a Sa(v)/S * H(Sa(v))

Hvor Sa(v)/S er forholdet mellem antallet af eksempler i datasættet med variablen a har værdien v, og H(Sa(v)) er entropien for gruppen af prøver, hvor variablen a har værdien v.

Dette lyder måske lidt forvirrende.

Vi kan gøre beregningen af informationsgevinst konkret med et gennemarbejdet eksempel.

Vil du lære sandsynlighed til maskinlæring

Tag mit gratis 7-dages e-mail crashkursus nu (med prøvekode).

Klik for at tilmelde dig og få også en gratis PDF Ebook-version af kurset.

Download dit GRATIS minikursus

Arbejdet eksempel på beregning af informationsgevinst

I dette afsnit vil vi gøre beregningen af informationsgevinst konkret med et arbejdseksempel.

Vi kan definere en funktion til at beregne entropien for en gruppe af prøver baseret på forholdet mellem prøver, der tilhører klasse 0 og klasse 1.

Nu betragter vi et datasæt med 20 eksempler, 13 for klasse 0 og 7 for klasse 1. Vi kan beregne entropien for dette datasæt, som vil have mindre end 1 bit.

Tænk nu på, at en af variablerne i datasættet har to unikke værdier, lad os sige “value1” og “value2”. Vi er interesseret i at beregne informationsgevinsten for denne variabel.

Lad os antage, at hvis vi opdeler datasættet efter værdi1, har vi en gruppe på otte prøver, syv for klasse 0 og en for klasse 1. Vi kan så beregne entropien for denne gruppe af prøver.

Lad os nu antage, at vi opdeler datasættet efter værdi2; vi har en gruppe på 12 prøver med seks i hver gruppe. Vi ville forvente, at denne gruppe ville have en entropi på 1.

Endeligt kan vi beregne informationsgevinsten for denne variabel på baggrund af de grupper, der er oprettet for hver værdi af variablen, og den beregnede entropi.

Den første variabel resulterede i en gruppe med otte eksempler fra datasættet, og den anden gruppe havde de resterende 12 prøver i datasættet. Vi har derfor alt, hvad vi har brug for til at beregne informationsgevinsten.

I dette tilfælde kan informationsgevinsten beregnes som:

• Entropi(Datasæt) – (Count(Group1) / Count(Datasæt) * Entropi(Group1) + Count(Group2) / Count(Datasæt) * Entropi(Group2))

Og:

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

Og i kode:

Og i kode: (8/20 * Entropi(7/8, 1/8) + 12/20 * Entropi(6/12, 6/12))

Det komplette eksempel, der binder det hele sammen, er anført nedenfor.

Først beregnes datasættets entropi til lige under 1 bit. Derefter beregnes entropien for den første og anden gruppe til henholdsvis ca. 0,5 og 1 bit.

Slutteligt beregnes informationsgevinsten for variablen til 0,117 bit. Det vil sige, at gevinsten for datasættet ved at opdele det via den valgte variabel er 0,117 bit.

Eksempler på informationsgevinst i maskinlæring

Den måske mest populære anvendelse af informationsgevinst i maskinlæring er i beslutningstræer.

Et eksempel er algoritmen Iterative Dichotomiser 3, eller ID3 forkortet, der bruges til at konstruere et beslutningstræ.

Informationsgevinst er netop det mål, som ID3 bruger til at vælge den bedste attribut ved hvert trin i træets vækst.

– Side 58, Machine Learning, 1997.

Informationsgevinsten beregnes for hver variabel i datasættet. Den variabel, der har den største informationsgevinst, vælges til at opdele datasættet. Generelt indikerer en større gevinst en mindre entropi eller mindre overraskelse.

Bemærk, at en minimering af entropien svarer til en maksimering af informationsgevinsten …

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

Processen gentages derefter på hver oprettet gruppe, idet den variabel, der allerede var valgt, udelukkes. Dette stopper, når en ønsket dybde på beslutningstræet er nået, eller når der ikke er mulighed for flere opdelinger.

Processen med at vælge en ny attribut og opdele træningseksemplerne gentages nu for hver ikke-terminal nedstammet knude, denne gang kun ved hjælp af de træningseksempler, der er knyttet til den pågældende knude. Attributter, der er blevet indarbejdet højere oppe i træet, udelukkes, således at en given attribut højst kan optræde én gang langs enhver vej gennem træet.

– Side 60, Machine Learning, 1997.

Informationsgevinst kan anvendes som et opdelingskriterium i de fleste moderne implementeringer af beslutningstræer, såsom implementeringen af algoritmen Classification and Regression Tree (CART) i scikit-learn Python-maskinlæringsbiblioteket scikit-learn Python i klassen DecisionTreeClassifier til klassifikation.

Dette kan opnås ved at indstille kriterieargumentet til “entropi” ved konfigurationen af modellen; f.eks:

Informationsgevinst kan også bruges til udvælgelse af funktioner forud for modellering.

Det indebærer beregning af informationsgevinsten mellem målvariablen og hver indgangsvariabel i træningsdatasættet. Weka machine learning workbench indeholder en implementering af informationsforøgelse til funktionsudvælgelse via klassen InfoGainAttributeEval.

I denne sammenhæng med funktionsudvælgelse kan informationsforøgelse omtales som “gensidig information” og beregne den statistiske afhængighed mellem to variabler. Et eksempel på anvendelse af informationsforøgelse (gensidig information) til funktionsudvælgelse er funktionen mutual_info_classif() scikit-learn.

Hvad er gensidig information?

Mutuel information beregnes mellem to variabler og måler reduktionen i usikkerheden for den ene variabel givet en kendt værdi af den anden variabel.

En størrelse kaldet gensidig information måler den mængde information, man kan få fra en tilfældig variabel givet en anden.

– Side 310, Data Mining: Practical Machine Learning Tools and Techniques, 4. udgave, 2016.

Den gensidige information mellem to tilfældige variabler X og Y kan formelt angives som følger:

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

Hvor I(X ; Y) er den gensidige information for X og Y, H(X) er entropien for X, og H(X | Y) er den betingede entropi for X, givet Y. Resultatet har enheden bits.

Mutuel information er et mål for afhængighed eller “gensidig afhængighed” mellem to tilfældige variabler. Som sådan er målet symmetrisk, hvilket betyder, at I(X ; Y) = I(Y ; X).

Det måler den gennemsnitlige reduktion i usikkerheden om x, der følger af at lære værdien af y; eller omvendt, den gennemsnitlige mængde information, som x formidler om y.

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

Kullback-Leibler- eller KL-divergens er et mål, der beregner forskellen mellem to sandsynlighedsfordelinger.

Den gensidige information kan også beregnes som KL-divergens mellem den fælles sandsynlighedsfordeling og produktet af de marginale sandsynligheder for hver variabel.

Hvis variablerne ikke er uafhængige, kan vi få en idé om, hvorvidt de er “tæt på” at være uafhængige, ved at betragte Kullback-Leibler-divergens mellem den fælles fordeling og produktet af marginalfordelingerne, som kaldes den gensidige information mellem variablerne

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

Dette kan formelt angives således:

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

Den gensidige information er altid større end eller lig med nul, hvor jo større værdien er, jo større er forholdet mellem de to variabler. Hvis det beregnede resultat er nul, er variablerne uafhængige.

Mutual information bruges ofte som en generel form for en korrelationskoefficient, f.eks. et mål for afhængigheden mellem tilfældige variabler.

Det bruges også som et aspekt i nogle algoritmer til maskinindlæring. Et almindeligt eksempel er Independent Component Analysis, forkortet ICA, der giver en projektion af statistisk uafhængige komponenter i et datasæt.

Hvordan er informationsgevinst og gensidig information relateret?

Mutual Information og informationsgevinst er det samme, selv om konteksten eller brugen af målet ofte giver anledning til de forskellige navne.

For eksempel:

• Effekt af transformationer til et datasæt (beslutningstræer): Informationsgevinst.
• Afhængighed mellem variabler (valg af funktioner): Gensidig information.

Bemærk ligheden i den måde, hvorpå den gensidige information beregnes, og den måde, hvorpå informationsgevinsten beregnes; de er ækvivalente:

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

og

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

Som sådan bruges gensidig information undertiden som et synonym for informationsgevinst. Teknisk set beregner de den samme størrelse, hvis de anvendes på de samme data.

Vi kan forstå forholdet mellem de to som, at jo større forskellen er på den fælles og den marginale sandsynlighedsfordeling (gensidig information), jo større er informationsgevinsten (informationsgevinst).

videre læsning

Dette afsnit indeholder flere ressourcer om emnet, hvis du ønsker at gå i dybden.

Bøger

• 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. udgave, 2016.

API

• scipy.stats.entropy API

Artikler

• Entropi (informationsteori), Wikipedia.
• Informationsgevinst i beslutningstræer, Wikipedia.
• ID3-algoritme, Wikipedia.
• Informationsgevinstforhold, Wikipedia.
• Gensidig information, Wikipedia.

Summary

I dette indlæg opdagede du informationsgevinst og gensidig information i maskinlæring.

Specifikt lærte du:

• Informationsgevinst er reduktionen i entropi eller overraskelse ved at transformere et datasæt og bruges ofte til træning af beslutningstræer.
• Informationsgevinst beregnes ved at sammenligne entropien af datasættet før og efter en transformation.
• Mutual information beregner den statistiske afhængighed mellem to variabler og er betegnelsen for informationsgevinst, når den anvendes til valg af variabler.

Har du spørgsmål?
Sæt dine spørgsmål i kommentarerne nedenfor, og jeg vil gøre mit bedste for at svare.