Informationsvinst och ömsesidig information för maskininlärning

Sist uppdaterad den 10 december 2020

Informationsvinst beräknar minskningen av entropin eller överraskningen av att omvandla en datamängd på något sätt.

Det används vanligen vid konstruktion av beslutsträd från en träningsdatamängd, genom att utvärdera informationsvinsten för varje variabel och välja den variabel som maximerar informationsvinsten, vilket i sin tur minimerar entropin och bäst delar upp datamängden i grupper för effektiv klassificering.

Informationsvinsten kan också användas för val av funktioner, genom att utvärdera vinsten för varje variabel i samband med målvariabeln. I denna något annorlunda användning kallas beräkningen för ömsesidig information mellan de två slumpvariablerna.

I det här inlägget kommer du att upptäcka informationsförstärkning och ömsesidig information inom maskininlärning.

Efter att ha läst det här inlägget kommer du att veta:

• Informationsvinst är minskningen av entropin eller överraskningen genom att omvandla en datamängd och används ofta för att träna beslutsträd.
• Informationsvinst beräknas genom att jämföra datamängdens entropi före och efter en omvandling.
• Mutuell information beräknar det statistiska beroendet mellan två variabler och är det namn som ges till informationsvinst när den tillämpas på val av variabler.

Kicka igång ditt projekt med min nya bok Probability for Machine Learning, inklusive steg-för-steg-handledning och Python-källkodfiler för alla exempel.

Vi sätter igång.

• Uppdatering nov/2019: Förbättrade beskrivningen av grunderna för info/entropi (tack HR).
• Uppdatering aug/2020:

Översikt

Denna handledning är uppdelad i fem delar; de är:

1. Vad är informationsvinst?
2. Arbetsexempel på beräkning av informationsvinst
3. Exempel på informationsvinst i maskininlärning
4. Vad är ömsesidig information?
5. Hur är informationsvinst och ömsesidig information relaterade?

Vad är informationsvinst?

Informationsvinst, eller IG förkortat, mäter minskningen av entropi eller överraskningsmöjlighet genom att dela upp en datamängd i enlighet med ett givet värde på en slumpvariabel.

En större informationsvinst tyder på en grupp eller grupper av prover med lägre entropi och därmed mindre överraskning.

Du kanske minns att information kvantifierar hur överraskande en händelse är i bitar. Händelser med lägre sannolikhet har mer information, händelser med högre sannolikhet har mindre information. Entropi kvantifierar hur mycket information som finns i en slumpvariabel, eller mer specifikt dess sannolikhetsfördelning. En skev fördelning har en låg entropi, medan en fördelning där händelserna har lika stor sannolikhet har en större entropi.

I informationsteorin gillar vi att beskriva ”överraskningen” av en händelse. Händelser med låg sannolikhet är mer överraskande och har därför en större mängd information. Medan sannolikhetsfördelningar där händelserna är lika sannolika är mer överraskande och har större entropi.

• Skevad sannolikhetsfördelning (oöverraskande): Låg entropi.
• Balanserad sannolikhetsfördelning (överraskande): Hög entropi.

För mer information om grunderna för information och entropi, se handledningen:

• En försiktig introduktion till informationsentropi

Nu ska vi betrakta entropin för ett dataset.

Vi kan tänka på entropin hos en datamängd i termer av sannolikhetsfördelningen av observationer i datamängden som tillhör en klass eller en annan, t.ex. två klasser i fallet med en binär klassificeringsdatamängd.

En tolkning av entropin från informationsteorin är att den specificerar det minsta antal bitar information som behövs för att koda klassificeringen av en godtycklig medlem av S (dvs, en medlem av S som dras slumpmässigt med enhetlig sannolikhet).

– Page 58, Machine Learning, 1997.

För ett binärt klassificeringsproblem (två klasser) kan vi till exempel beräkna entropin för dataurvalet på följande sätt:

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

En datamängd med en 50/50-uppdelning av proverna för de två klasserna skulle ha en maximal entropi (maximal överraskning) på 1 bit, medan en obalanserad datamängd med en uppdelning på 10/90 skulle ha en mindre entropi eftersom det skulle vara mindre överraskning för ett slumpmässigt utvalt exempel från datamängden.

Vi kan demonstrera detta med ett exempel på att beräkna entropin för denna obalanserade datamängd i Python. Det fullständiga exemplet finns nedan.

Om vi kör exemplet kan vi se att entropin för datasetet för binär klassificering är mindre än 1 bit. Det innebär att det krävs mindre än en bit information för att koda klassbeteckningen för ett godtyckligt exempel från datasetet.

På detta sätt kan entropin användas som en beräkning av renheten hos en datamängd, t.ex.t.ex. hur balanserad fördelningen av klasser råkar vara.

En entropi på 0 bitar indikerar en datamängd som innehåller en klass; en entropi på 1 eller fler bitar tyder på maximal entropi för en balanserad datamängd (beroende på antalet klasser), med värden däremellan som indikerar nivåer mellan dessa ytterligheter.

Informationsvinst ger ett sätt att använda entropi för att beräkna hur en ändring av datamängden påverkar renheten av datamängden, t.ex. fördelningen av klasser. En mindre entropi tyder på mer renhet eller mindre överraskning.

… informationsvinst, är helt enkelt den förväntade minskningen av entropin som orsakas av att exemplen delas upp enligt detta attribut.

– Sida 57, Maskinininlärning, 1997.

Till exempel kan vi vilja utvärdera hur renheten påverkas av att dela upp en datamängd S med en slumpmässig variabel med ett intervall av värden.

Detta kan beräknas på följande sätt:

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

Varvid IG(S, a) är informationen för datamängden S för variabeln a för en slumpmässig variabel, H(S) är entropin för datamängden före en eventuell förändring (beskrivet ovan) och H(S | a) är den villkorliga entropin för datamängden givet variabeln a.

Denna beräkning beskriver vinsten i datasetet S för variabeln a. Det är antalet bitar som sparas när datasetet omvandlas.

Den betingade entropin kan beräknas genom att dela upp datasetet i grupper för varje observerat värde av a och beräkna summan av förhållandet mellan exemplen i varje grupp av hela datasetet multiplicerat med entropin för varje grupp.

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

Varvid Sa(v)/S är förhållandet mellan antalet exempel i datamängden där variabeln a har värdet v, och H(Sa(v)) är entropin för gruppen av exempel där variabeln a har värdet v.

Detta kan låta lite förvirrande.

Vi kan konkretisera beräkningen av informationsvinst med ett fungerande exempel.

Vill du lära dig sannolikhet för maskininlärning

Ta min kostnadsfria 7-dagars snabbkurs via e-post nu (med exempelkod).

Klicka för att registrera dig och även få en gratis PDF Ebook-version av kursen.

Ladda ner din GRATIS minikurs

Arbetsliknande exempel på beräkning av informationsvinst

I det här avsnittet kommer vi att konkretisera beräkningen av informationsvinst med ett arbetsliknande exempel.

Vi kan definiera en funktion för att beräkna entropin för en grupp av exempel baserat på förhållandet mellan de exempel som tillhör klass 0 och klass 1.

Nu kan vi betrakta ett dataset med 20 exempel, 13 för klass 0 och 7 för klass 1. Vi kan beräkna entropin för detta dataset, som kommer att ha mindre än 1 bit.

Tänk nu på att en av variablerna i datasetet har två unika värden, säg ”värde1” och ”värde2”. Vi är intresserade av att beräkna informationsvinsten för denna variabel.

Vi antar att om vi delar upp datasetet efter värde1 har vi en grupp med åtta prover, sju för klass 0 och ett för klass 1. Vi kan då beräkna entropin för denna grupp av prover.

Nu antar vi att vi delar upp datasetet efter värde2; vi har en grupp med 12 prover med sex i varje grupp. Vi skulle förvänta oss att denna grupp har en entropi på 1.

Slutligt kan vi beräkna informationsvinsten för denna variabel baserat på de grupper som skapats för varje värde av variabeln och den beräknade entropin.

Den första variabeln resulterade i en grupp med åtta exempel från datamängden, och den andra gruppen hade de återstående 12 proverna i datamängden. Därför har vi allt vi behöver för att beräkna informationsvinsten.

I det här fallet kan informationsvinsten beräknas som:

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

Och:

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

Och i kod:

För att knyta ihop allt detta finns det fullständiga exemplet nedan.

För det första beräknas datamängdens entropi till strax under 1 bit. Därefter beräknas entropin för den första och andra gruppen till cirka 0,5 respektive 1 bit.

Slutligt beräknas informationsvinsten för variabeln till 0,117 bit. Det vill säga, vinsten för datasetet genom att dela upp det via den valda variabeln är 0,117 bitar.

Exempel på informationsvinst i maskininlärning

Den kanske mest populära användningen av informationsvinst i maskininlärning är i beslutsträd.

Ett exempel är algoritmen Iterative Dichotomiser 3, eller kort sagt ID3, som används för att konstruera ett beslutsträd.

Informationsvinsten är just det mått som ID3 använder för att välja det bästa attributet vid varje steg i tillväxten av trädet.

– Sida 58, Maskininlärning, 1997.

Informationsvinsten beräknas för varje variabel i datasetet. Den variabel som har den största informationsvinsten väljs ut för att dela upp datasetet. I allmänhet indikerar en större vinst en mindre entropi eller mindre överraskning.

Notera att minimering av entropin är likvärdig med maximering av informationsvinsten …

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

Processen upprepas sedan på varje skapad grupp, med undantag för den variabel som redan valts. Detta upphör när ett önskat djup på beslutsträdet har uppnåtts eller när inga fler uppdelningar är möjliga.

Processen med att välja ett nytt attribut och dela upp träningsexemplen upprepas nu för varje icke terminalt nedstigande nod, den här gången med hjälp av endast träningsexemplen som är associerade med den noden. Attribut som har införlivats högre upp i trädet utesluts, så att varje givet attribut kan förekomma högst en gång längs varje väg genom trädet.

– Sida 60, Maskininlärning, 1997.

Informationsvinst kan användas som ett uppdelningskriterium i de flesta moderna implementeringar av beslutsträd, t.ex. implementeringen av algoritmen för klassificerings- och regressionssträdet (CART) i Python-biblioteket för maskininlärning scikit-learn i klassen DecisionTreeClassifier för klassificering.

Detta kan uppnås genom att ställa in kriterieargumentet till ”entropi” när modellen konfigureras; t.ex:

Informationsvinsten kan också användas för val av funktioner före modellering.

Det innebär att man beräknar informationsvinsten mellan målvariabeln och varje ingående variabel i träningsdatamängden. Weka machine learning workbench tillhandahåller en implementering av informationsvinst för funktionsval via klassen InfoGainAttributeEval.

I detta sammanhang av funktionsval kan informationsvinst kallas ”ömsesidig information” och beräkna det statistiska beroendet mellan två variabler. Ett exempel på användning av informationsvinst (ömsesidig information) för funktionsval är funktionen mutual_info_classif() scikit-learn.

Vad är ömsesidig information?

Muell information beräknas mellan två variabler och mäter minskningen av osäkerheten för den ena variabeln givet ett känt värde för den andra variabeln.

En kvantitet som kallas ömsesidig information mäter hur mycket information man kan få från en slumpmässig variabel givet en annan.

– Sida 310, Data Mining: Practical Machine Learning Tools and Techniques, 4th edition, 2016.

Den ömsesidiga informationen mellan två slumpvariabler X och Y kan formellt anges på följande sätt:

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

Varvid I(X ; Y) är den ömsesidiga informationen för X och Y, H(X) är entropin för X och H(X | Y) är den villkorliga entropin för X givet Y. Resultatet har enheterna bits.

Muell information är ett mått på beroende eller ”ömsesidigt beroende” mellan två slumpvariabler. Som sådant är måttet symmetriskt, vilket innebär att I(X ; Y) = I(Y ; X).

Det mäter den genomsnittliga minskningen av osäkerheten om x som följer av att lära sig värdet av y; eller vice versa, den genomsnittliga mängden information som x förmedlar om y.

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

Kullback-Leibler- eller KL-divergens är ett mått som beräknar skillnaden mellan två sannolikhetsfördelningar.

Den ömsesidiga informationen kan också beräknas som KL-divergens mellan den gemensamma sannolikhetsfördelningen och produkten av de marginella sannolikheterna för varje variabel.

Om variablerna inte är oberoende kan vi få en uppfattning om huruvida de är ”nära” oberoende genom att ta hänsyn till Kullback-Leiblers divergens mellan den gemensamma fördelningen och produkten av marginalerna som kallas den ömsesidiga informationen mellan variablerna

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

Detta kan formellt anges på följande sätt:

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

Den ömsesidiga informationen är alltid större än eller lika med noll, där ju större värdet är desto större är sambandet mellan de två variablerna. Om det beräknade resultatet är noll är variablerna oberoende.

Mutuell information används ofta som en allmän form av en korrelationskoefficient, t.ex. ett mått på beroendet mellan slumpmässiga variabler.

Det används också som en aspekt i vissa algoritmer för maskininlärning. Ett vanligt exempel är Independent Component Analysis, förkortat ICA, som ger en projektion av statistiskt oberoende komponenter i en datamängd.

Hur är informationsvinst och ömsesidig information relaterade?

Mutuell information och informationsvinst är samma sak, även om kontexten eller användningen av måttet ofta ger upphov till de olika namnen.

Till exempel:

• Effekten av omvandlingar av en datamängd (beslutsträd):
• Depende mellan variabler (urval av funktioner): Informationsvinst.
• Depende mellan variabler (urval av funktioner): Ömsesidig information.

Bemärk likheten mellan det sätt på vilket den ömsesidiga informationen beräknas och det sätt på vilket informationsvinsten beräknas; de är likvärdiga:

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

och

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

Därmed används ömsesidig information ibland som en synonym för informationsvinst. Tekniskt sett beräknar de samma kvantitet om de tillämpas på samma data.

Vi kan förstå förhållandet mellan de två som att ju större skillnaden är mellan de gemensamma och marginella sannolikhetsfördelningarna (ömsesidig information), desto större är informationsvinsten (informationsvinst).

Fortsatt läsning

Det här avsnittet innehåller fler resurser om ämnet om du vill fördjupa dig.

Böcker

• 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, 4th edition, 2016.

API

• scipy.stats.entropy API

Articles

• Entropi (informationsteori), Wikipedia.
• Informationsvinst i beslutsträd, Wikipedia.
• ID3-algoritmen, Wikipedia.
• Informationsvinstförhållande, Wikipedia.
• Ömsesidig information, Wikipedia.

Sammanfattning

I det här inlägget upptäckte du informationsvinst och ömsesidig information i maskininlärning.

Specifikt lärde du dig:

• Informationsvinst är minskningen av entropin eller överraskningen genom att omvandla en datamängd, och den används ofta för att träna beslutsträd.
• Informationsvinst beräknas genom att jämföra entropin i datamängden före och efter en omvandling.
• Mutuell information beräknar det statistiska beroendet mellan två variabler och är det namn som ges till informationsvinst när den tillämpas på val av variabler.

Har du några frågor?
Ställ dina frågor i kommentarerna nedan så ska jag göra mitt bästa för att svara.