Zysk informacyjny i informacja wzajemna dla uczenia maszynowego

Ostatnio aktualizowane 10 grudnia 2020

Zysk informacyjny oblicza redukcję entropii lub zaskoczenia z przekształcenia zbioru danych w jakiś sposób.

Jest on powszechnie stosowany w konstrukcji drzew decyzyjnych ze zbioru danych szkoleniowych, poprzez ocenę przyrostu informacji dla każdej zmiennej i wybór zmiennej, która maksymalizuje przyrost informacji, co z kolei minimalizuje entropię i najlepiej dzieli zbiór danych na grupy dla skutecznej klasyfikacji.

Przyrost informacji może być również stosowany do wyboru cech, poprzez ocenę przyrostu każdej zmiennej w kontekście zmiennej docelowej. W tym nieco innym zastosowaniu, obliczenie jest określane jako informacja wzajemna pomiędzy dwoma zmiennymi losowymi.

W tym poście, poznasz zysk informacyjny i informację wzajemną w uczeniu maszynowym.

Po przeczytaniu tego postu, będziesz wiedział:

• Przyrost informacji jest redukcją entropii lub zaskoczenia przez przekształcenie zbioru danych i jest często używany w szkoleniu drzew decyzyjnych.
• Przyrost informacji jest obliczany przez porównanie entropii zbioru danych przed i po przekształceniu.
• Wspólna informacja oblicza statystyczną zależność między dwiema zmiennymi i jest nazwą nadaną przyrostowi informacji, gdy jest stosowany do wyboru zmiennych.

Kick-startuj swój projekt z moją nową książką Probability for Machine Learning, zawierającą samouczki krok po kroku i pliki kodu źródłowego Pythona dla wszystkich przykładów.

Zacznijmy.

• Aktualizacja Nov/2019: Poprawiono opis podstaw info/entropii (dzięki HR).
• Aktualizacja Aug/2020: Dodano brakujące nawiasy do równania (dzięki David)

Przegląd

Tutorial ten podzielony jest na pięć części; są to:

1. Co to jest zysk informacyjny?
2. Pracowy przykład obliczania zysku informacyjnego
3. Przykłady zysku informacyjnego w uczeniu maszynowym
4. Co to jest informacja wzajemna?
5. How Are Information Gain and Mutual Information Related?

What Is Information Gain?

Information Gain, or IG for short, measures the reduction in entropy or surprise by split a dataset according to a given value of a random variable.

Większy zysk informacyjny sugeruje niższą entropię grupy lub grup próbek, a tym samym mniejszą niespodziankę.

Możesz sobie przypomnieć, że informacja określa jak zaskakujące jest zdarzenie w bitach. Zdarzenia o niższym prawdopodobieństwie mają więcej informacji, zdarzenia o wyższym prawdopodobieństwie mają mniej informacji. Entropia określa jak dużo informacji jest w zmiennej losowej, a dokładniej w jej rozkładzie prawdopodobieństwa. Rozkład skośny ma niską entropię, podczas gdy rozkład, w którym zdarzenia mają równe prawdopodobieństwo, ma większą entropię.

W teorii informacji lubimy opisywać „niespodziankę” zdarzenia. Zdarzenia o niskim prawdopodobieństwie są bardziej zaskakujące, dlatego mają większą ilość informacji. Natomiast rozkłady prawdopodobieństwa, w których zdarzenia są równie prawdopodobne są bardziej zaskakujące i mają większą entropię.

• Skośny rozkład prawdopodobieństwa (mało zaskakujący): Niska entropia.
• Zrównoważony rozkład prawdopodobieństwa (zaskakujący): Wysoka entropia.

Więcej na temat podstaw informacji i entropii można znaleźć w samouczku:

• Łagodne wprowadzenie do entropii informacji

Teraz rozważmy entropię zbioru danych.

Możemy myśleć o entropii zbioru danych w kategoriach rozkładu prawdopodobieństwa obserwacji w zbiorze danych należących do jednej lub drugiej klasy, np. dwóch klas w przypadku zbioru danych klasyfikacji binarnej.

Jedną z interpretacji entropii z teorii informacji jest to, że określa ona minimalną liczbę bitów informacji potrzebnych do zakodowania klasyfikacji arbitralnego członka S (tj, członka S losowanego z jednolitym prawdopodobieństwem).

– Strona 58, Machine Learning, 1997.

Na przykład, w binarnym problemie klasyfikacji (dwie klasy), możemy obliczyć entropię próbki danych w następujący sposób:

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

Zbiór danych z podziałem próbek dla dwóch klas 50/50 miałby maksymalną entropię (maksymalne zaskoczenie) 1 bit, podczas gdy niezrównoważony zbiór danych z podziałem 10/90 miałby mniejszą entropię, ponieważ byłoby mniej zaskoczenia dla losowo wylosowanego przykładu ze zbioru danych.

Możemy to zademonstrować na przykładzie obliczania entropii dla tego niezrównoważonego zbioru danych w Pythonie. Kompletny przykład znajduje się poniżej.

Running the example, możemy zobaczyć, że entropia zbioru danych dla klasyfikacji binarnej jest mniejsza niż 1 bit. Oznacza to, że mniej niż jeden bit informacji jest wymagany do zakodowania etykiety klasy dla dowolnego przykładu z zestawu danych.

W ten sposób entropia może być użyta jako obliczenie czystości zbioru danych, np.jak zrównoważony jest rozkład klas.

An entropia 0 bitów wskazuje na zbiór danych zawierający jedną klasę; entropia 1 lub więcej bitów sugeruje maksymalną entropię dla zrównoważonego zbioru danych (w zależności od liczby klas), z wartościami pomiędzy wskazującymi poziomy pomiędzy tymi ekstremami.

Zysk informacji zapewnia sposób na wykorzystanie entropii do obliczenia, jak zmiana w zbiorze danych wpływa na czystość zbioru danych, np. rozkład klas. Mniejsza entropia sugeruje większą czystość lub mniejszą niespodziankę.

… zysk informacyjny, jest po prostu oczekiwanym zmniejszeniem entropii spowodowanym przez podział przykładów według tego atrybutu.

– Strona 57, Machine Learning, 1997.

Na przykład, możemy chcieć ocenić wpływ na czystość przez podział zbioru danych S przez zmienną losową o zakresie wartości.

Można to obliczyć w następujący sposób:

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

Gdzie IG(S, a) jest informacją dla zbioru danych S dla zmiennej losowej a, H(S) jest entropią dla zbioru danych przed jakąkolwiek zmianą (opisaną powyżej), a H(S | a) jest entropią warunkową dla zbioru danych biorąc pod uwagę zmienną a.

To obliczenie opisuje przyrost w zbiorze danych S dla zmiennej a. Jest to liczba bitów zaoszczędzonych podczas przekształcania zbioru danych.

Enterropię warunkową można obliczyć dzieląc zbiór danych na grupy dla każdej zaobserwowanej wartości a i obliczając sumę stosunku przykładów w każdej grupie z całego zbioru danych pomnożoną przez entropię każdej grupy.

• H(S | a) = suma v w a Sa(v)/S * H(Sa(v))

Gdzie Sa(v)/S jest stosunkiem liczby przykładów w zbiorze danych, w których zmienna a ma wartość v, a H(Sa(v)) jest entropią grupy próbek, w których zmienna a ma wartość v.

To może brzmieć trochę zagmatwanie.

Możemy skonkretyzować obliczanie przyrostu informacji za pomocą działającego przykładu.

Want to Learn Probability for Machine Learning

Take my free 7-day email crash course now (with sample code).

Kliknij, aby się zapisać, a także otrzymać darmowy PDF Ebook w wersji kursu.

Download Your FREE Mini-Course

Worked Example of Calculating Information Gain

W tej sekcji skonkretyzujemy obliczanie zysku informacyjnego za pomocą działającego przykładu.

Możemy zdefiniować funkcję obliczającą entropię grupy próbek na podstawie stosunku próbek, które należą do klasy 0 i klasy 1.

Rozważmy teraz zbiór danych z 20 przykładami, 13 dla klasy 0 i 7 dla klasy 1. Możemy obliczyć entropię dla tego zbioru danych, która będzie miała mniej niż 1 bit.

Teraz rozważmy, że jedna ze zmiennych w zbiorze danych ma dwie unikalne wartości, powiedzmy „wartość1” i „wartość2”. Interesuje nas obliczenie przyrostu informacji tej zmiennej.

Załóżmy, że jeśli podzielimy zbiór danych według wartości1, mamy grupę ośmiu próbek, siedem dla klasy 0 i jedną dla klasy 1. Następnie możemy obliczyć entropię tej grupy próbek.

Załóżmy teraz, że podzieliliśmy zbiór danych według wartości2; mamy grupę 12 próbek z sześcioma w każdej grupie. Spodziewalibyśmy się, że ta grupa będzie miała entropię 1.

Wreszcie, możemy obliczyć zysk informacyjny dla tej zmiennej w oparciu o grupy utworzone dla każdej wartości zmiennej i obliczonej entropii.

Pierwsza zmienna spowodowała powstanie grupy ośmiu przykładów ze zbioru danych, a druga grupa miała pozostałe 12 próbek w zbiorze danych. Mamy zatem wszystko, czego potrzebujemy do obliczenia przyrostu informacji.

W tym przypadku zysk informacyjny można obliczyć jako:

• 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 w kodzie:

Łącząc to wszystko razem, kompletny przykład jest podany poniżej.

Najpierw entropia zbioru danych jest obliczana na poziomie nieco poniżej 1 bitu. Następnie entropia dla pierwszej i drugiej grupy są obliczane na około 0,5 i 1 bit odpowiednio.

Finally, zysk informacji dla zmiennej jest obliczana jako 0,117 bitów. Oznacza to, że zysk dla zbioru danych poprzez jego podział za pomocą wybranej zmiennej wynosi 0,117 bitów.

Przykłady zysku informacyjnego w uczeniu maszynowym

Prawdopodobnie najpopularniejszym zastosowaniem zysku informacyjnego w uczeniu maszynowym są drzewa decyzyjne.

Przykładem jest algorytm Iterative Dichotomiser 3, w skrócie ID3, używany do konstruowania drzewa decyzyjnego.

Zysk informacji jest właśnie miarą używaną przez ID3 do wyboru najlepszego atrybutu na każdym etapie wzrostu drzewa.

– Strona 58, Machine Learning, 1997.

Zysk informacji jest obliczany dla każdej zmiennej w zbiorze danych. Zmienna, która ma największy przyrost informacji jest wybierana do podziału zbioru danych. Ogólnie rzecz biorąc, większy zysk wskazuje na mniejszą entropię lub mniejsze zaskoczenie.

Zauważ, że minimalizacja entropii jest równoważna maksymalizacji zysku informacyjnego …

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

Proces ten jest następnie powtarzany na każdej utworzonej grupie, z wyłączeniem zmiennej, która została już wybrana. Proces ten zatrzymuje się po osiągnięciu pożądanej głębokości drzewa decyzyjnego lub gdy nie ma już możliwości podziału.

Proces wyboru nowego atrybutu i podziału przykładów szkoleniowych jest teraz powtarzany dla każdego niekończącego się węzła potomnego, tym razem z wykorzystaniem tylko przykładów szkoleniowych związanych z tym węzłem. Atrybuty, które zostały włączone wyżej w drzewie są wykluczone, tak że każdy dany atrybut może pojawić się co najwyżej raz wzdłuż dowolnej ścieżki przez drzewo.

– Strona 60, Machine Learning, 1997.

Zysk informacji może być użyty jako kryterium podziału w większości nowoczesnych implementacji drzew decyzyjnych, takich jak implementacja algorytmu Classification and Regression Tree (CART) w bibliotece uczenia maszynowego scikit-learn Python w klasie DecisionTreeClassifier dla klasyfikacji.

Można to osiągnąć, ustawiając argument kryterium na „entropię” podczas konfigurowania modelu; na przykład:

Zysk informacyjny może być również wykorzystany do selekcji cech przed modelowaniem.

Polega on na obliczeniu zysku informacyjnego pomiędzy zmienną docelową a każdą zmienną wejściową w zestawie danych treningowych. Weka machine learning workbench dostarcza implementację wzmocnienia informacyjnego dla selekcji cech poprzez klasę InfoGainAttributeEval.

W tym kontekście selekcji cech, wzmocnienie informacyjne może być określane jako „wzajemna informacja” i oblicza statystyczną zależność pomiędzy dwoma zmiennymi. Przykładem wykorzystania przyrostu informacji (informacji wzajemnej) do selekcji cech jest funkcja mutual_info_classif() scikit-learn.

What Is Mutual Information?

Mutual information is calculated between two variables and measures the reduction in uncertainty for one variable given a known value of the other variable.

Wielkość zwana informacją wzajemną mierzy ilość informacji, którą można uzyskać z jednej zmiennej losowej biorąc pod uwagę inną.

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

Informacja wzajemna między dwiema zmiennymi losowymi X i Y może być formalnie określona w następujący sposób:

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

Gdzie I(X ; Y) jest informacją wzajemną dla X i Y, H(X) jest entropią dla X, a H(X | Y) jest entropią warunkową dla X biorąc pod uwagę Y. Wynik ma jednostki bitowe. Wynik ma jednostki w bitach.

Informacja wzajemna jest miarą zależności lub „wzajemnej zależności” między dwiema zmiennymi losowymi. Jako taka, miara ta jest symetryczna, co oznacza, że I(X ; Y) = I(Y ; X).

Mierzy średnią redukcję niepewności o x, która wynika z poznania wartości y; lub odwrotnie, średnią ilość informacji, którą x przekazuje o y.

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

Różnica Kullbacka-Leiblera, lub KL, jest miarą, która oblicza różnicę pomiędzy dwoma rozkładami prawdopodobieństwa.

Informację wzajemną można również obliczyć jako rozbieżność KL pomiędzy wspólnym rozkładem prawdopodobieństwa a iloczynem prawdopodobieństw krańcowych dla każdej zmiennej.

Jeśli zmienne nie są niezależne, możemy uzyskać pewne pojęcie o tym, czy są „bliskie” bycia niezależnymi, rozważając dywergencję Kullbacka-Leiblera między wspólnym rozkładem a iloczynem prawdopodobieństw marginalnych, która jest nazywana informacją wzajemną między zmiennymi

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

Można to stwierdzić formalnie w następujący sposób:

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

Informacja wzajemna jest zawsze większa lub równa zeru, gdzie im większa wartość, tym większy związek między dwiema zmiennymi. Jeśli obliczony wynik wynosi zero, wówczas zmienne są niezależne.

Informacja wzajemna jest często stosowana jako ogólna forma współczynnika korelacji, np. miara zależności między zmiennymi losowymi.

Jest również stosowana jako aspekt w niektórych algorytmach uczenia maszynowego. Popularnym przykładem jest analiza niezależnych składowych, w skrócie ICA, która zapewnia projekcję statystycznie niezależnych składowych zbioru danych.

How Are Information Gain and Mutual Information Related?

Mutual Information i Information Gain są tym samym, chociaż kontekst lub użycie miary często powoduje powstanie różnych nazw.

Na przykład:

• Effect of Transforms to a Dataset (decision trees): Information Gain.
• Dependence Between Variables (feature selection): Mutual Information.

Zauważ podobieństwo w sposobie obliczania informacji wzajemnej i sposobie obliczania zysku informacyjnego; są one równoważne:

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

oraz

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

W związku z tym informacja wzajemna jest czasem używana jako synonim zysku informacyjnego. Z technicznego punktu widzenia obliczają one tę samą wielkość, jeśli są stosowane do tych samych danych.

Zależność między nimi możemy rozumieć w ten sposób, że im większa różnica w łącznych i krańcowych rozkładach prawdopodobieństwa (informacja wzajemna), tym większy przyrost informacji (zysk informacyjny).

Dalsza lektura

Ta sekcja dostarcza więcej zasobów na ten temat, jeśli szukasz pogłębienia.

Książki

• 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

Artykuły

• Entropia (teoria informacji), Wikipedia.
• Zysk informacyjny w drzewach decyzyjnych, Wikipedia.
• Algorytm ID3, Wikipedia.
• Współczynnik zysku informacyjnego, Wikipedia.
• Informacja wzajemna, Wikipedia.

Podsumowanie

W tym poście odkryłeś zysk informacyjny i wzajemną informację w uczeniu maszynowym.

Konkretnie, nauczyłeś się:

• Zysk informacyjny jest redukcją entropii lub zaskoczenia przez przekształcenie zbioru danych i jest często używany w szkoleniu drzew decyzyjnych.
• Zysk informacyjny jest obliczany przez porównanie entropii zbioru danych przed i po przekształceniu.
• Wspólna informacja oblicza statystyczną zależność między dwiema zmiennymi i jest nazwą nadaną zyskowi informacji, gdy jest stosowana do selekcji zmiennych.

Czy masz jakieś pytania?
Zadawaj pytania w komentarzach poniżej, a ja dołożę wszelkich starań, aby odpowiedzieć.

.