Czytam tę książkę ( NLTK ) i jest ona myląca. Entropia jest zdefiniowana jako :

Entropia jest sumą prawdopodobieństwa każdej etykiety pomnożonej przez prawdopodobieństwo prawdopodobieństwa tej samej etykiety

Jak mogę zastosować entropię i maksymalną entropię w zakresie eksploracji tekstu? Czy ktoś może dać mi prosty, prosty przykład (wizualny)?

Zakładam, że entropia została wspomniana w kontekście budowania drzew decyzyjnych .

Aby to zilustrować, wyobraź sobie zadanie uczenia się klasyfikowania imion w grupach mężczyzn i kobiet. Dostajemy listę nazw oznaczonych albo, malbo fchcemy nauczyć się modelu, który pasuje do danych i może być używany do przewidywania płci nowego, niewidocznego imienia.

name       gender
-----------------        Now we want to predict 
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

Pierwszym krokiem jest podjęcie decyzji, które cechy danych są istotne dla klasy docelowej, którą chcemy przewidzieć. Niektóre przykładowe funkcje to: pierwsza / ostatnia litera, długość, liczba samogłosek, czy kończy się samogłoską itp. Więc po wyodrębnieniu funkcji nasze dane wyglądają następująco:

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

Celem jest zbudowanie drzewa decyzyjnego . Przykładem drzewa byłoby:

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

w zasadzie każdy węzeł reprezentuje test przeprowadzony na jednym atrybucie, a my przechodzimy w lewo lub w prawo w zależności od wyniku testu. Przemierzamy drzewo, aż dotrzemy do węzła liścia zawierającego prognozę klasy ( mlub f)

Więc jeśli uruchomimy nazwę Amro w tym drzewie, zaczniemy od przetestowania „ czy długość <7? ”, A odpowiedź brzmi „ tak” , więc schodzimy w dół tej gałęzi. Po rozgałęzieniu następny test „ jest liczbą samogłosek <3? ” Ponownie ocenia się na prawdę . Prowadzi to do oznaczenia węzła liścia m, a zatem prognoza jest męska ( tak się składa , że drzewo poprawnie przewidziało wynik ).

Drzewo decyzyjne jest zbudowane z góry na dół , ale pytanie brzmi, jak wybrać atrybut do podziału w każdym węźle? Odpowiedź brzmi: znajdź funkcję, która najlepiej dzieli klasę docelową na najczystsze możliwe węzły potomne (tj.: Węzły, które nie zawierają mieszanki zarówno męskiej, jak i żeńskiej, raczej czyste węzły tylko z jedną klasą).

Ta miara czystości nazywana jest informacją . Reprezentuje oczekiwaną ilość informacji, która byłaby potrzebna do określenia, czy nowe wystąpienie (imię) powinno zostać sklasyfikowane jako męskie czy żeńskie, biorąc pod uwagę przykład, który dotarł do węzła. Obliczamy to na podstawie liczby klas męskich i żeńskich w węźle.

Z drugiej strony entropia jest miarą zanieczyszczenia (wręcz przeciwnie). Jest zdefiniowany dla klasy binarnej o wartościacha/bjako:

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

Ta binarna funkcja entropii jest przedstawiona na poniższym rysunku (zmienna losowa może przyjąć jedną z dwóch wartości). Osiąga ona maksimum, gdy prawdopodobieństwo jest p=1/2, co oznacza, że p(X=a)=0.5albo w podobny sposób p(X=b)=0.5o 50% / 50% szans na zarówno alub b(niepewność jest maksymalna). Funkcja entropii jest na poziomie zerowym minimum, gdy prawdopodobieństwo jest p=1lub p=0z całkowitą pewnością ( p(X=a)=1lub p(X=a)=0odpowiednio to drugie implikuje p(X=b)=1).

Oczywiście definicję entropii można uogólnić dla dyskretnej zmiennej losowej X o N wynikach (nie tylko dwóch):

( logwe wzorze jest zwykle brany jako logarytm do podstawy 2 )

Wróćmy do naszego zadania klasyfikacji nazw, spójrzmy na przykład. Wyobraź sobie, że w pewnym momencie procesu konstruowania drzewa rozważaliśmy następujący podział:

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

Jak widać, przed podziałem mieliśmy 9 mężczyzn i 5 kobiet, czyli P(m)=9/14i P(f)=5/14. Zgodnie z definicją entropii:

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

Następnie porównujemy go z entropią obliczoną po rozważeniu podziału, patrząc na dwie gałęzie podrzędne. W lewej gałęzi ends-vowel=1mamy:

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

i odpowiednią gałąź ends-vowel=0, mamy:

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

Łączymy lewą / prawą entropię przy użyciu liczby instancji w dół każdej gałęzi jako współczynnika wagi (7 instancji poszło w lewo, a 7 instancji poszło w prawo) i otrzymujemy ostatnią entropię po podziale:

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

Teraz, porównując entropię przed i po podziale, uzyskujemy miarę przyrostu informacji lub ile informacji uzyskaliśmy dzięki podziałowi przy użyciu tej konkretnej funkcji:

Information_Gain = Entropy_before - Entropy_after = 0.1518

Możesz zinterpretować powyższe obliczenia w następujący sposób: wykonując podział za pomocą end-vowelsfunkcji, byliśmy w stanie zmniejszyć niepewność wyniku prognozy pod-drzewa o niewielką ilość 0,1518 (mierzoną w bitach jako jednostki informacji ).

W każdym węźle drzewa obliczenia są wykonywane dla każdej cechy, a cecha o największym zysku informacji jest wybierana do podziału w zachłanny sposób (faworyzując cechy, które dają czyste podziały z niską niepewnością / entropią). Ten proces jest stosowany rekurencyjnie od węzła głównego do dołu i zatrzymuje się, gdy węzeł liścia zawiera instancje o tej samej klasie (nie trzeba go dalej dzielić).

Zwróć uwagę, że pominąłem niektóre szczegóły, które wykraczają poza zakres tego postu, w tym sposób obsługi funkcji numerycznych , brakujących wartości , nadmiernego dopasowania i przycinania drzew itp.

Na początek najlepiej to zrozumieć the measure of information.

Jak otrzymujemy measureinformacje?

Kiedy dzieje się coś mało prawdopodobnego, mówimy, że to ważna wiadomość. Ponadto, gdy mówimy coś przewidywalnego, nie jest to naprawdę interesujące. Aby więc to oszacować interesting-ness, funkcja powinna spełniać

• jeśli prawdopodobieństwo zdarzenia wynosi 1 (przewidywalne), wówczas funkcja daje 0
• jeśli prawdopodobieństwo zdarzenia jest bliskie 0, funkcja powinna dać wysoką liczbę
• jeśli zdarzy się prawdopodobieństwo 0,5, to daje one bitinformację.

Jednym z naturalnych środków, które spełniają ograniczenia, jest

I(X) = -log_2(p)

gdzie p jest prawdopodobieństwem zdarzenia X. I urządzenie jest bitwłączone, używa tego samego bitowego komputera. 0 lub 1.

Przykład 1

Rzut monetą:

Ile informacji możemy uzyskać od jednego rzutu monetą?

Odpowiedź : -log(p) = -log(1/2) = 1 (bit)

Przykład 2

Jeśli jutro meteor uderzy w Ziemię, p=2^{-22}możemy uzyskać 22 bity informacji.

Jeśli Słońce wstanie jutro, p ~ 1oznacza to 0 bitów informacji.

Entropia

Jeśli więc weźmiemy pod uwagę interesting-nesswydarzenie Y, to jest to entropia. tzn. entropia jest oczekiwaną wartością interesującego zdarzenia.

H(Y) = E[ I(Y)]

Bardziej formalnie, entropia jest oczekiwaną liczbą bitów zdarzenia.

Przykład

Y = 1: zdarzenie X występuje z prawdopodobieństwem p

Y = 0: zdarzenie X nie występuje z prawdopodobieństwem 1-p

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) 
     = - p log p - (1-p) log (1-p)

Baza dziennika 2 dla wszystkich dzienników.

Nie mogę dać ci grafiki, ale może mogę dać jasne wyjaśnienie.

Załóżmy, że mamy kanał informacyjny, taki jak lampka, która miga raz dziennie albo na czerwono, albo na zielono. Ile informacji to przekazuje? Pierwsze przypuszczenie może wynosić jeden bit dziennie. Ale co jeśli dodamy niebieski, aby nadawca miał trzy opcje? Chcielibyśmy mieć miarę informacji, która może obsługiwać rzeczy inne niż potęgi dwóch, ale nadal być addytywna (sposób, w jaki mnożenie liczby możliwych wiadomości przez dwa dodaje jeden bit). Możemy to zrobić, biorąc dziennik ₂ (liczbę możliwych wiadomości), ale okazuje się, że istnieje bardziej ogólny sposób.

Załóżmy, że wróciliśmy do czerwonego / zielonego, ale czerwona żarówka się przepaliła (jest to powszechnie znana), więc lampa musi zawsze migać na zielono. Kanał jest teraz bezużyteczny, wiemy, jaki będzie następny flashwięc błyski nie przekazują żadnych informacji, żadnych wiadomości. Teraz naprawiamy żarówkę, ale wprowadzamy zasadę, że czerwona żarówka nie może błyskać dwa razy z rzędu. Kiedy lampa miga na czerwono, wiemy, jaki będzie następny błysk. Jeśli spróbujesz wysłać strumień bitów przez ten kanał, przekonasz się, że musisz go zakodować z większą ilością błysków niż z bitami (w rzeczywistości o 50% więcej). A jeśli chcesz opisać sekwencję błysków, możesz to zrobić za pomocą mniejszej liczby bitów. To samo dotyczy sytuacji, gdy każdy błysk jest niezależny (bezkontekstowy), ale zielone błyski są częstsze niż czerwone: im bardziej przekrzywione prawdopodobieństwo, tym mniej bitów potrzebujesz do opisania sekwencji i im mniej informacji zawiera, aż do limit całkowitego wypalenia żarówki.

Okazuje się, że istnieje sposób pomiaru ilości informacji w sygnale na podstawie prawdopodobieństwa różnych symboli. Jeśli prawdopodobieństwo otrzymania symbolu x _i wynosi p _i , rozważ wielkość

-log p i

Im mniejsze p _i , tym większa jest ta wartość. Jeśli x _{i stanie} się dwa razy mniej prawdopodobne, wartość ta wzrośnie o ustaloną kwotę (log (2)). To powinno przypominać o dodaniu jednego bitu do wiadomości.

Jeśli nie wiemy, jaki będzie symbol (ale znamy prawdopodobieństwa), możemy obliczyć średnią tej wartości, ile otrzymamy, sumując różne możliwości:

I = -Σ p i log (p i )

To jest zawartość informacyjna w jednym flashu.

Wypalona czerwona żarówka: p czerwona = 0, p zielona = 1, I = - (0 + 0) = 0
Czerwony i zielony sprzęt: p czerwony = 1/2, p zielony = 1/2 , I = - (2 * 1/2 * log (1/2)) = log (2)
Trzy kolory, możliwe do dostosowania: p i = 1/3, I = - (3 * 1/3 * log (1/3)) = log (3)
Zielony i czerwony, zielony dwa razy bardziej prawdopodobny: p czerwony = 1/3 , p zielony = 2/3, I = - (1/3 log (1/3) + 2/3 log (2/3)) = log ( 3) - 2/3 log (2)

Jest to treść informacyjna lub entropia wiadomości. Jest maksymalny, gdy różne symbole są dostępne. Jeśli jesteś fizykiem, korzystasz z naturalnego dziennika, a jeśli jesteś informatykiem, używasz dziennika ₂ i dostajesz kawałki.

Naprawdę polecam przeczytać o teorii informacji, metodach bayesowskich i MaxEnt. Rozpocznij od tej książki Davida Mackaya (dostępnej online):

http://www.inference.phy.cam.ac.uk/mackay/itila/

Te metody wnioskowania są naprawdę znacznie bardziej ogólne niż tylko eksploracja tekstu i nie mogę naprawdę wymyślić, jak można się nauczyć, jak zastosować to do NLP, bez poznania niektórych ogólnych podstaw zawartych w tej książce lub innych książkach wprowadzających na temat uczenia maszynowego i bayesowskiego MaxEnta metody

Związek między entropią i teorią prawdopodobieństwa a przetwarzaniem i przechowywaniem informacji jest naprawdę bardzo głęboki. Aby to zasmakować, istnieje twierdzenie Shannona, które stwierdza, że ​​maksymalna ilość informacji, którą można przekazać bezbłędnie przez głośny kanał komunikacyjny, jest równa entropii procesu szumu. Istnieje również twierdzenie, które łączy, ile można skompresować kawałek danych, aby zajmować minimalną możliwą pamięć w komputerze, do entropii procesu, który wygenerował dane.

Nie sądzę, że naprawdę konieczne jest zapoznanie się z tymi wszystkimi twierdzeniami dotyczącymi teorii komunikacji, ale nie jest możliwe nauczenie się tego bez poznania podstaw tego, czym jest entropia, jak jest obliczana, jaki jest związek z informacjami i wnioskami itp. ...

Kiedy wdrażałem algorytm do obliczania entropii obrazu, znalazłem te linki, patrz tutaj i tutaj .

To pseudo-kod, którego użyłem, musisz go dostosować do pracy z tekstem, a nie obrazami, ale zasady powinny być takie same.

//Loop over image array elements and count occurrences of each possible
//pixel to pixel difference value. Store these values in prob_array
for j = 0, ysize-1 do $
    for i = 0, xsize-2 do begin
       diff = array(i+1,j) - array(i,j)
       if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin
            prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1
       endif
     endfor

//Convert values in prob_array to probabilities and compute entropy
n = total(prob_array)

entrop = 0
for i = 0, array_size-1 do begin
    prob_array(i) = prob_array(i)/n

    //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element
    //here and divide final sum by Ln(2)
    if prob_array(i) ne 0 then begin
        entrop = entrop - prob_array(i)*alog(prob_array(i))
    endif
endfor

entrop = entrop/alog(2)

Skądś mam ten kod, ale nie mogę wykopać linku.

Nieprzepisowo

entropia to dostępność informacji lub wiedzy, brak informacji prowadzi do trudności w przewidywaniu przyszłości, co jest wysoką entropią (przewidywanie następnego słowa w eksploracji tekstu), a dostępność informacji / wiedzy pomoże nam bardziej realistycznie przewidywać przyszłość (niska entropia).

Odpowiednie informacje dowolnego rodzaju zmniejszą entropię i pomogą nam przewidzieć bardziej realistyczną przyszłość, że informacja może być słowem „mięso” występuje w zdaniu lub słowem „mięso” nie występuje. Nazywa się to zdobywaniem informacji

Formalnie

entropia to brak kolejności przewidywalności

Gdy czytasz książkę o NLTK, interesujące byłoby przeczytanie o MaxEnt Classifier Module http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

W przypadku klasyfikacji eksploracji tekstu kroki mogą być następujące: przetwarzanie wstępne (tokenizacja, parowanie, wybór funkcji za pomocą Information Gain ...), transformacja do numerycznej (częstotliwość lub TF-IDF) (myślę, że jest to kluczowy krok do zrozumienia podczas korzystania tekst jako dane wejściowe do algorytmu, który akceptuje tylko wartości liczbowe), a następnie sklasyfikuj za pomocą MaxEnt, z pewnością jest to tylko przykład.