Informaatiovoitto ja keskinäinen informaatio koneoppimisessa

Viimeisin päivitetty 10.12.2020

Informaatiovoitto laskee entropian tai yllätyksellisyyden vähenemisen, joka aiheutuu siitä, että tietokokonaisuutta muutetaan jollakin tavalla.

Sitä käytetään yleisesti päätöspuiden rakentamisessa harjoitusaineistosta arvioimalla kunkin muuttujan informaatiovoittoa ja valitsemalla muuttuja, joka maksimoi informaatiovoiton, mikä puolestaan minimoi entropian ja jakaa aineiston parhaiten ryhmiin tehokasta luokittelua varten.

Informaatiovoittoa voidaan käyttää myös ominaisuuksien valintaan arvioimalla kunkin muuttujan voittoa kohdemuuttujan yhteydessä. Tässä hieman erilaisessa käytössä laskentaa kutsutaan kahden satunnaismuuttujan keskinäiseksi informaatioksi.

Tässä postauksessa tutustut informaatiovoittoon ja keskinäiseen informaatioon koneoppimisessa.

Lukemalla tämän postauksen tiedät:

• Informaatiovoitto on entropian tai yllätyksellisyyden vähenemistä aineistoa muunnettaessa, ja sitä käytetään usein päätöspuiden harjoittelussa.
• Informaatiovoitto lasketaan vertailemalla aineiston entropiaa ennen ja jälkeen muunnoksen.
• Mutual information laskee kahden muuttujan välisen tilastollisen riippuvuuden ja on nimitys informaatiovoitolle, kun sitä sovelletaan muuttujien valintaan.

Käynnistä projektisi uudella kirjallani Probability for Machine Learning, joka sisältää vaiheittaiset opetusohjelmat ja Python-lähdekooditiedostot kaikille esimerkeille.

Aloitetaan.

• Päivitys marraskuu/2019: Parannettu infon/entropian perusteiden kuvausta (kiitos HR:lle).
• Päivitys elokuu/2020: Lisätty puuttuvat sulkeet yhtälöön (kiitos David)

Yleiskatsaus

Tämä opetusohjelma on jaettu viiteen osaan; ne ovat:

1. Mitä on informaatiovoitto?
2. Työskentelyesimerkki informaatiovoiton laskemisesta
3. Esimerkkejä informaatiovoiton laskemisesta koneoppimisessa
4. Mitä on keskinäinen informaatio?
5. Miten informaatiovoitto ja keskinäinen informaatio liittyvät toisiinsa?

Mitä on informaatiovoitto?

Informaatiovoitto, lyhyesti IG, mittaa entropian tai yllätyksellisyyden vähenemistä jakamalla tietokokonaisuus tietyn satunnaismuuttujan arvon mukaan.

Suurempi informaatiovoitto viittaa pienempään entropiaryhmään tai -ryhmiin ja siten pienempään yllätyksellisyyteen.

Voi ehkä muistaa, että informaatio kvantifioi sitä, kuinka yllättävä tapahtuma on bitteinä. Pienemmän todennäköisyyden tapahtumilla on enemmän informaatiota, suuremman todennäköisyyden tapahtumilla on vähemmän informaatiota. Entropia kvantifioi, kuinka paljon informaatiota satunnaismuuttujassa, tai tarkemmin sanottuna sen todennäköisyysjakaumassa, on. Vinolla jakaumalla on pieni entropia, kun taas jakaumalla, jossa tapahtumilla on yhtä suuri todennäköisyys, on suurempi entropia.

Informaatioteoriassa kuvataan mielellään tapahtuman ”yllätyksellisyyttä”. Pienellä todennäköisyydellä tapahtumat ovat yllättävämpiä, joten niillä on suurempi määrä informaatiota. Kun taas todennäköisyysjakaumat, joissa tapahtumat ovat yhtä todennäköisiä, ovat yllättävämpiä ja niillä on suurempi entropia.

• Vino todennäköisyysjakauma (ei yllättävä): Pieni entropia.
• Tasapainoinen todennäköisyysjakauma (yllättävä): Suuri entropia.

Lisätietoa informaation ja entropian perusteista löydät opetusohjelmasta:

• Varovainen johdatus informaatioentropiaan

Tarkastellaan nyt erään tietokokonaisuuden entropiaa.

Voidaan ajatella tietokokonaisuuden entropiaa todennäköisyysjakaumana, jolla tietokokonaisuuden havainnot kuuluvat johonkin luokkaan, esim. kahteen luokkaan binäärisen luokittelutietokokonaisuuden tapauksessa.

Yksi tulkinta entropiasta informaatioteorian näkökulmasta on se, että se määrittelee sen, mikä on se informaatiobittien vähimmäismäärä, joka tarvitaan, jotta voidaan koodata luokittelun mielivaltaisen S:n jäsenen luokittelua (ts, tasaisella todennäköisyydellä satunnaisesti arvottu S:n jäsen).

– Page 58, Machine Learning, 1997.

Voidaan esimerkiksi binäärisessä luokitusongelmassa (kaksi luokkaa) laskea datanäytteen entropia seuraavasti:

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

Aineistokokonaisuuden, jossa näytteet jakautuvat 50/50 kahteen luokkaan, suurin entropia (suurin yllätys) olisi 1 bitti, kun taas epätasapainoisella aineistokokonaisuudella, jossa jakauma on 10/90, olisi pienempi entropia, koska satunnaisesti poimitun esimerkin yllättävyys aineistokokonaisuudesta olisi pienempi.

Voidaan havainnollistaa tämä esimerkillä, jossa lasketaan entropia tälle epätasapainoiselle aineistokokonaisuudelle Pythonilla. Täydellinen esimerkki on lueteltu alla.

Suorittamalla esimerkin näemme, että tietokokonaisuuden entropia binääriluokittelua varten on alle 1 bitti. Toisin sanoen alle yksi bitti tietoa tarvitaan koodaamaan luokkamerkintä mielivaltaiselle esimerkille tietokokonaisuudesta.

Siten entropiaa voidaan käyttää laskelmana aineiston puhtaudesta, esim.esim. kuinka tasapainoinen luokkien jakauma sattuu olemaan.

Nolla bittiä oleva entropia viittaa tietokokonaisuuteen, joka sisältää yhden luokan; yhden tai useamman bitin entropia viittaa tasapainoisen tietokokonaisuuden maksimaaliseen entropiaan (luokkien lukumäärästä riippuen), ja siltä väliltä olevat arvot ilmaisevat näiden ääripäiden välisiä tasoja.

Informaatiovahvistus tarjoaa tavan, jonka avulla voidaan laskea entropian avulla, miten tietokokonaisuuteen tehty muutos vaikuttaa tietokokonaisuuden puhtauteen, esim. luokkien jakauman puhtauteen. Pienempi entropia viittaa suurempaan puhtauteen tai pienempään yllätyksellisyyteen.

… informaatiovoitto, on yksinkertaisesti odotettavissa oleva entropian pieneneminen, joka aiheutuu esimerkkien jakamisesta tämän ominaisuuden mukaan.

– Sivu 57, Koneellinen oppiminen, 1997.

Voidaan esimerkiksi halutessamme arvioida, millainen vaikutus puhtauteen on sillä, että jaamme tietokokonaisuutta S satunnaismuuttujan, jolla on arvoalue.

Tämä voidaan laskea seuraavasti:

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

Jossa IG(S, a) on datajoukon S informaatio muuttujan a satunnaismuuttujan osalta, H(S) on datajoukon entropia ennen muutosta (kuvattu edellä) ja H(S | a) on datajoukon ehdollinen entropia muuttujan a suhteen.

Tämä laskutoimitus kuvaa datasetin S voittoa muuttujalle a. Se on bittien määrä, joka säästyy datasetin muunnoksen yhteydessä.

Konditionaalinen entropia voidaan laskea jakamalla datasetti ryhmiin jokaiselle havaitulle a:n arvolle ja laskemalla kuhunkin ryhmään kuuluvien esimerkkien suhdeluvun summa koko datasetistä kerrottuna kunkin ryhmän entropialla.

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

Jossa Sa(v)/S on niiden esimerkkien lukumäärän suhde aineistossa, joissa muuttuja a:lla on arvo v, ja H(Sa(v)) on niiden esimerkkiryhmien entropia, joissa muuttujalla a on arvo v.

Tämä saattaa kuulostaa hieman hämmentävältä.

Voidaan konkretisoida informaatiovoiton laskemista työstetyn esimerkin avulla.

Tahdotko oppia todennäköisyyttä koneoppimista varten

Tule mukaan maksuttomalle 7-päiväiselle sähköpostitse lähetettävälle pikakurssilleni nyt (esimerkkikoodin kanssa).

Klikkaa ilmoittautuaksesi ja saat myös ilmaisen PDF-kirjaversion kurssista.

Lataa ILMAINEN minikurssisi

Työskentelyesimerkki informaatiovoiton laskemisesta

Tässä osiossa konkretisoimme informaatiovoiton laskemisen työstetyn esimerkin avulla.

Voidaan määritellä funktio, jolla voidaan laskea näytteiden ryhmän entropia perustuen luokkaan 0 ja luokkaan 1 kuuluvien näytteiden suhteeseen.

Harkitaan nyt aineistoa, jossa on 20 esimerkkiä, joista 13 kuuluu luokkaan 0 ja 7 luokkaan 1. Voimme laskea tälle tietokokonaisuudelle entropian, joka on alle 1 bitti.

Asettele nyt, että yhdellä tietokokonaisuuden muuttujista on kaksi yksilöllistä arvoa, vaikkapa ”arvo1” ja ”arvo2”. Olemme kiinnostuneita laskemaan tämän muuttujan informaatiovoiton.

Asettakaamme, että jos jaamme aineiston arvon1 mukaan, meillä on kahdeksan näytteen ryhmä, joista seitsemän kuuluu luokkaan 0 ja yksi luokkaan 1. Voimme tällöin laskea tämän näyteryhmän entropian.

Esitellään nyt, että jaamme aineiston arvon2 mukaan; meillä on 12 näytteen ryhmä, jossa kussakin ryhmässä on kuusi näytettä. Odottaisimme, että tämän ryhmän entropia olisi 1.

Viimeiseksi voimme laskea tämän muuttujan informaatiovoiton perustuen muuttujan kullekin arvolle luotuihin ryhmiin ja laskettuun entropiaan.

Ensimmäisen muuttujan tuloksena saatiin ryhmä, jossa oli kahdeksan esimerkkiä tietokokonaisuudesta, ja toisessa ryhmässä oli loput 12 näytettä tietokokonaisuudesta. Meillä on siis kaikki, mitä tarvitsemme informaatiovoiton laskemiseen.

Tässä tapauksessa informaatiovoitto voidaan laskea seuraavasti:

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

Or:

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

Or koodissa:

Tämän kaiken yhteen nivominen, täydellinen esimerkki on lueteltu alla.

Ensiksi datasetin entropia lasketaan vajaan 1 bitin suuruiseksi. Sitten lasketaan ensimmäisen ja toisen ryhmän entropia, jotka ovat noin 0,5 ja 1 bittiä.

Viimeiseksi lasketaan muuttujan informaatiovoitto, joka on 0,117 bittiä. Toisin sanoen datajoukon voitto jakamalla se valitun muuttujan avulla on 0,117 bittiä.

Esimerkkejä informaatiovoitosta koneoppimisessa

Periaatteessa suosituin informaatiovoiton käyttö koneoppimisessa on päätöksentekopuissa.

Esimerkkinä voidaan mainita päätöksentekopuiden konstruoimiseen käytetty Iterative Dichotomiser 3 -algoritmi, lyhyesti ID3.

Informaatiovoitto on juuri se mittari, jota ID3 käyttää valitessaan parhaan attribuutin jokaisessa päätöksentekopuun kasvattamisen vaiheessa.

– Sivu 58, Koneoppiminen, 1997.

Informaatiovoitto lasketaan kullekin muuttujalle aineistossa. Muuttuja, jolla on suurin informaatiovoitto, valitaan jaettavaksi aineistosta. Yleensä suurempi informaatiovoitto merkitsee pienempää entropiaa tai vähemmän yllätyksellisyyttä.

Huomaa, että entropian minimointi vastaa informaatiovoiton maksimointia …

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

Prosessi toistetaan sitten jokaiselle luodulle ryhmälle, jolloin jo valittu muuttuja jätetään pois. Tämä lopetetaan, kun päätöspuun haluttu syvyys on saavutettu tai jakaminen ei ole enää mahdollista.

Prosessi, jossa valitaan uusi attribuutti ja osioidaan harjoitusesimerkit, toistetaan nyt jokaiselle ei-päätteiselle jälkeläissolmulle, tällä kertaa käyttäen vain kyseiseen solmuun liittyviä harjoitusesimerkkejä. Attribuutit, jotka on sisällytetty puuhun ylempänä, jätetään pois, joten mikä tahansa attribuutti voi esiintyä korkeintaan kerran millä tahansa polulla puun läpi.

– Sivu 60, Machine Learning, 1997.

Informaatiohyötyä voidaan käyttää jakokriteerinä useimmissa nykyaikaisissa päätöspuutoteutuksissa, kuten scikit-learnin Python-koneoppimiskirjastossa olevan luokitus- ja regressiopuualgoritmin (Classification and Regression Tree (CART) algorithmiin (luokitus ja regressiopuualgoritmi) toteutuksessa luokittelua varten luokkaan DecisionTreeClassifier.

Tämä voidaan saavuttaa asettamalla kriteeriargumentiksi ”entropia” mallia konfiguroitaessa; esim:

Informaatiovoittoa voidaan käyttää myös ominaisuuksien valintaan ennen mallintamista.

Siinä lasketaan informaatiovoitto kohdemuuttujan ja jokaisen harjoitusaineiston syötemuuttujan välillä. Weka-koneoppimisen työpöytä tarjoaa informaatiovahvistuksen toteutuksen ominaisuuksien valintaa varten InfoGainAttributeEval-luokan kautta.

Tässä ominaisuuksien valinnan yhteydessä informaatiovahvistus voidaan nimittää ”keskinäiseksi informaatioksi”, ja se laskee kahden muuttujan välisen tilastollisen riippuvuuden. Esimerkki informaatiovoiton (mutual information) käyttämisestä ominaisuuksien valinnassa on mutual_info_classif() scikit-learn-funktio.

Mitä on mutual information?

Mutual information lasketaan kahden muuttujan välille ja se mittaa epävarmuuden vähenemistä yhden muuttujan osalta, kun toisen muuttujan arvo tunnetaan.

Kummanväliseksi informaatioksi kutsuttu suure mittaa sitä, kuinka paljon informaatiota voidaan saada yhdestä satunnaismuuttujasta, kun otetaan huomioon toinen satunnaismuuttuja.

– Sivu 310, Data Mining: Practical Machine Learning Tools and Techniques, 4. painos, 2016.

Kahden satunnaismuuttujan X ja Y keskinäinen informaatio voidaan esittää muodollisesti seuraavasti:

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

Jossa I(X ; Y) on X:n ja Y:n keskinäinen informaatio, H(X) on X:n entropia ja H(X | Y) on X:n ehdollinen entropia annettuna Y:lle. Tuloksen yksikköinä ovat bitit.

Keskinäinen informaatio on kahden satunnaismuuttujan välisen riippuvuuden tai ”keskinäisen riippuvuuden” mitta. Sinänsä mitta on symmetrinen eli I(X ; Y) = I(Y ; X).

Se mittaa keskimääräistä epävarmuuden vähenemistä x:n suhteen, joka johtuu siitä, että oppii y:n arvon; tai päinvastoin, keskimääräistä informaation määrää, jonka x välittää y:stä.

– Sivu 139, Informaatioteoria, päättely, ja oppimisalgoritmit, 2003.

Kullback-Leiblerin eli KL-divergenssi on mitta, joka laskee kahden todennäköisyysjakauman välisen eron.

Vuorovaikutteinen informaatio voidaan laskea myös yhteisen todennäköisyysjakauman ja kunkin muuttujan marginaalitodennäköisyyksien tulon välisenä KL-divergenssinä.

Jos muuttujat eivät ole riippumattomia, voimme saada jonkinlaisen käsityksen siitä, ovatko ne ”lähellä” riippumattomuutta tarkastelemalla yhteisen jakauman ja marginaalitodennäköisyyksien tulon välistä Kullback-Leibler-divergenssia, jota kutsutaan muuttujien keskinäiseksi informaatioksi

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

Tämä voidaan esittää muodollisesti seuraavasti:

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

Mutual information (keskinäinen informaatio)

on aina suurempi tai yhtä suuri kuin nolla, jolloin mitä suurempi arvo on, sitä suuremmasta suhteesta kahden muuttujan välillä on kyse. Jos laskettu tulos on nolla, muuttujat ovat riippumattomia.

Mutuaali-informaatiota käytetään usein korrelaatiokertoimen yleisenä muotona, esim. satunnaismuuttujien välisen riippuvuuden mittana.

Sitä käytetään myös eräänä näkökohtana joissakin koneoppimisalgoritmeissa. Yleinen esimerkki on riippumaton komponenttianalyysi, lyhyesti ICA, joka antaa projisointia tilastollisesti riippumattomista komponenteista aineistosta.

Miten informaatiovoitto ja keskinäinen informaatio liittyvät toisiinsa?

Mutual Information ja Information Gain ovat sama asia, vaikka mittarin konteksti tai käyttö antaa usein aihetta erilaisiin nimityksiin.

Esimerkkinä esimerkiksi:

• Transformaatioiden vaikutus aineistokokonaisuuksiin (päätöksenteko-puut): Information Gain.
• Dependence Between Variables (feature selection): Mutual Information.

Huomaa samankaltaisuus tavassa, jolla keskinäinen informaatio lasketaan, ja tavassa, jolla informaatiovoitto lasketaan; ne vastaavat toisiaan:

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

ja

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

Niinpä vastavuoroista informaatiota käytetään joskus informaatiovoiton synonyyminä. Teknisesti ne laskevat saman suureen, jos niitä sovelletaan samoihin aineistoihin.

Voidaan ymmärtää näiden kahden välinen suhde siten, että mitä suurempi ero yhteis- ja ääritodennäköisyysjakaumissa on (mutual information), sitä suurempi on informaatiovoitto (information gain).

Lisälukemista

Tässä osiossa on lisää lähteitä aiheesta, jos haluat syventyä aiheeseen.

Kirjat

• Informaatioteoria, päättely ja oppimisalgoritmit, 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. painos, 2016.

API

• scipy.stats.entropy API

Artikkelit

• Entropia (tietoteoria), Wikipedia.
• Informaatiovoitto päätöspuissa, Wikipedia.
• ID3-algoritmi, Wikipedia.
• Informaatiovoiton suhde, Wikipedia.
• Keskinäinen informaatio, Wikipedia.

Yhteenveto

Tässä postauksessa tutustuit informaatiovoittoon ja keskinäiseen informaatioon koneoppimisessa.

Kohtaisesti opit:

• Informaatiovoitto on entropian tai yllätyksellisyyden pieneneminen muunnoksella, ja sitä käytetään usein päätöspuiden harjoittelussa.
• Informaatiovoitto saadaan laskettua vertailemalla tietokokonaisuuksien entropiatieto ennen muunnosta ja muunnoksen jälkeen.
• Mutual information laskee kahden muuttujan välisen tilastollisen riippuvuuden ja on nimitys informaatiovoitolle, kun sitä sovelletaan muuttujien valintaan.

Onko sinulla kysyttävää?
Kysy kysymyksesi alla olevissa kommenteissa ja teen parhaani vastatakseni.