Teoria Informației

Universul este plin de informație. Informația oferă un limbaj comun peste rupturile disciplinare: de la Sonetul lui Shakespeare la lucrarea cercetătorilor pe Cornell ArXiv, de la pictura Noapte Înstelată a lui Van Gogh la Simfonia a 5-a a lui Beethoven, de la primul limbaj de programare Plankalkül la algoritmii de învățare automată de ultimă generație. Totul trebuie să urmeze regulile teoriei informației, indiferent de format. Cu teoria informației, putem măsura și compara câtă informație este prezentă în diferite semnale. În această secțiune, vom investiga conceptele fundamentale ale teoriei informației și aplicațiile teoriei informației în învățarea automată.

Înainte de a începe, să schițăm relația dintre învățarea automată și teoria informației. Învățarea automată urmărește să extragă semnale interesante din date și să facă predicții critice. Pe de altă parte, teoria informației studiază codificarea, decodificarea, transmiterea și manipularea informației. Ca rezultat, teoria informației oferă un limbaj fundamental pentru a discuta despre procesarea informației în sistemele de învățare automată. De exemplu, multe aplicații de învățare automată folosesc pierderea de entropie încrucișată (cross-entropy loss), așa cum este descris în . Această pierdere poate fi derivată direct din considerente de teoria informației.

Să începem cu „sufletul” teoriei informației: informația. Informația poate fi codificată în orice cu o secvență particulară de unul sau mai multe formate de codificare. Presupuneți că ne propunem să definim o noțiune de informație. Care ar putea fi punctul nostru de plecare?

Considerați următorul experiment de gândire. Avem un prieten cu un pachet de cărți. Acesta va amesteca pachetul, va întoarce câteva cărți și ne va spune afirmații despre cărți. Vom încerca să evaluăm conținutul informațional al fiecărei afirmații.

Mai întâi, ei întorc o carte și ne spun: „Văd o carte”. Acest lucru nu ne oferă nicio informație deloc. Eram deja siguri că acesta era cazul, așa că sperăm ca informația să fie zero.

Apoi, ei întorc o carte și spun: „Văd o inimă roșie”. Acest lucru ne oferă ceva informații, dar în realitate există doar $4$ culori diferite care erau posibile, fiecare egal probabilă, așa că nu suntem surprinși de acest rezultat. Sperăm că oricare ar fi măsura informației, acest eveniment ar trebui să aibă un conținut informațional scăzut.

Apoi, ei întorc o carte și spun: „Acesta este $3$ de pică”. Aceasta este mai multă informație. Într-adevăr erau $52$ de rezultate posibile egal probabile, și prietenul nostru ne-a spus care a fost. Aceasta ar trebui să fie o cantitate medie de informație.

Să ducem asta la extrema logică. Presupuneți că în cele din urmă ei întorc fiecare carte din pachet și citesc întreaga secvență a pachetului amestecat. Există $52!$ ordine diferite ale pachetului, din nou toate egal probabile, deci avem nevoie de multă informație pentru a ști care este.

Orice noțiune de informație pe care o dezvoltăm trebuie să se conformeze acestei intuiții. Într-adevăr, în secțiunile următoare vom învăța cum să calculăm că aceste evenimente au $0\textrm{ biți}$, $2\textrm{ biți}$, $~5.7\textrm{ biți}$, și respectiv $~225.6\textrm{ biți}$ de informație.

Dacă citim prin aceste experimente de gândire, vedem o idee naturală. Ca punct de plecare, mai degrabă decât să ne pese de cunoaștere, putem construi pe ideea că informația reprezintă gradul de surpriză sau posibilitatea abstractă a evenimentului. De exemplu, dacă vrem să descriem un eveniment neobișnuit, avem nevoie de multă informație. Pentru un eveniment comun, s-ar putea să nu avem nevoie de multă informație.

În 1948, Claude E. Shannon a publicat A Mathematical Theory of Communication ¹⁾ stabilind teoria informației. În articolul său, Shannon a introdus conceptul de entropie informațională pentru prima dată. Ne vom începe călătoria aici.

Deoarece informația întruchipează posibilitatea abstractă a unui eveniment, cum mapăm posibilitatea la numărul de biți? Shannon a introdus terminologia bit ca unitate de informație, care a fost creată inițial de John Tukey. Deci ce este un „bit” și de ce îl folosim pentru a măsura informația? Istoric, un transmițător antic poate trimite sau primi doar două tipuri de cod: $0$ și $1$. Într-adevăr, codificarea binară este încă în uz comun pe toate computerele digitale moderne. În acest fel, orice informație este codificată de o serie de $0$ și $1$. Și prin urmare, o serie de cifre binare de lungime $n$ conține $n$ biți de informație.

Acum, presupuneți că pentru orice serie de coduri, fiecare $0$ sau $1$ apare cu o probabilitate de $\frac{1}{2}$. Prin urmare, un eveniment $X$ cu o serie de coduri de lungime $n$, apare cu o probabilitate de $\frac{1}{2^n}$. În același timp, așa cum am menționat înainte, această serie conține $n$ biți de informație. Deci, putem generaliza la o funcție matematică care poate transfera probabilitatea $p$ la numărul de biți? Shannon a dat răspunsul definind auto-informația

$$I(X) = - \log_2 (p),$$

ca biții de informație pe care i-am primit pentru acest eveniment $X$. Rețineți că vom folosi întotdeauna logaritmi în baza-2 în această secțiune. De dragul simplității, restul acestei secțiuni va omite indicele 2 în notația logaritmului, adică, $\log(.)$ se referă întotdeauna la $\log_2(.)$. De exemplu, codul „0010” are o auto-informație

$$I(\textrm{"0010"}) = - \log (p(\textrm{"0010"})) = - \log \left( \frac{1}{2^4} \right) = 4 \textrm{ biți}.$$

Putem calcula auto-informația așa cum este arătat mai jos. Înainte de asta, să importăm mai întâi toate pachetele necesare în această secțiune.

#@tab pytorch
import torch
from torch.nn import NLLLoss
 
def nansum(x):
    # Define nansum, as pytorch does not offer it inbuilt.
    return x[~torch.isnan(x)].sum()
 
def self_information(p):
    return -torch.log2(torch.tensor(p)).item()
 
self_information(1 / 64)

Deoarece auto-informația măsoară doar informația unui singur eveniment discret, avem nevoie de o măsură mai generalizată pentru orice variabilă aleatoare de distribuție discretă sau continuă.

Să încercăm să fim specifici despre ceea ce vrem. Aceasta va fi o afirmație informală a ceea ce sunt cunoscute ca axiomele entropiei Shannon. Se va dovedi că următoarea colecție de afirmații de bun simț ne forțează la o definiție unică a informației. O versiune formală a acestor axiome, împreună cu alte câteva, poate fi găsită în ²⁾.

1. Informația pe care o câștigăm observând o variabilă aleatoare nu depinde de cum numim elementele, sau de prezența elementelor adiționale care au probabilitate zero.
2. Informația pe care o câștigăm observând două variabile aleatoare nu este mai mare decât suma informației pe care o câștigăm observându-le separat. Dacă sunt independente, atunci este exact suma.
3. Informația câștigată când observăm evenimente (aproape) sigure este (aproape) zero.

Deși demonstrarea acestui fapt este dincolo de scopul textului nostru, este important să știm că acest lucru determină unic forma pe care trebuie s-o ia entropia. Singura ambiguitate pe care acestea o permit este în alegerea unităților fundamentale, care este cel mai adesea normalizată făcând alegerea pe care am văzut-o înainte că informația oferită de o singură aruncare a unei monede corecte este un bit.

Pentru orice variabilă aleatoare $X$ care urmează o distribuție de probabilitate $P$ cu o funcție de densitate a probabilității (p.d.f.) sau o funcție de masă a probabilității (p.m.f.) $p(x)$, măsurăm cantitatea așteptată de informație prin entropie (sau entropie Shannon)

$$H(X) = - E_{x \sim P} [\log p(x)].$$

Pentru a fi specifici, dacă $X$ este discretă, $$H(X) = - \sum_i p_i \log p_i \textrm{, unde } p_i = P(X_i).$$

Altfel, dacă $X$ este continuă, ne referim la entropie și ca entropie diferențială

$$H(X) = - \int_x p(x) \log p(x) \; dx.$$

Putem defini entropia ca mai jos.

#@tab pytorch
def entropy(p):
    entropy = - p * torch.log2(p)
    # Operator `nansum` will sum up the non-nan number
    out = nansum(entropy)
    return out
 
entropy(torch.tensor([0.1, 0.5, 0.1, 0.3]))

Ați putea fi curioși: în definiția entropiei :eqref:eq_ent_def, de ce folosim o așteptare a unui logaritm negativ? Iată câteva intuiții.

Mai întâi, de ce folosim o funcție logaritm $\log$? Presupuneți că $p(x) = f_1(x) f_2(x) \ldots, f_n(x)$, unde fiecare funcție componentă $f_i(x)$ este independentă una de cealaltă. Aceasta înseamnă că fiecare $f_i(x)$ contribuie independent la informația totală obținută din $p(x)$. Așa cum s-a discutat mai sus, vrem ca formula entropiei să fie aditivă peste variabilele aleatoare independente. Din fericire, $\log$ poate transforma natural un produs de distribuții de probabilitate într-o sumă a termenilor individuali.

Apoi, de ce folosim un $\log$ negativ? Intuitiv, evenimentele mai frecvente ar trebui să conțină mai puțină informație decât evenimentele mai puțin comune, deoarece adesea câștigăm mai multă informație dintr-un caz neobișnuit decât dintr-unul obișnuit. Totuși, $\log$ este crescător monoton cu probabilitățile, și într-adevăr negativ pentru toate valorile în $[0, 1]$. Trebuie să construim o relație descrescătoare monotonă între probabilitatea evenimentelor și entropia lor, care va fi ideal întotdeauna pozitivă (căci nimic din ce observăm nu ar trebui să ne forțeze să uităm ce am știut). Prin urmare, adăugăm un semn negativ în fața funcției $\log$.

În cele din urmă, de unde vine funcția așteptare (valoare așteptată)? Considerați o variabilă aleatoare $X$. Putem interpreta auto-informația ($-\log(p)$) ca și cantitatea de surpriză pe care o avem la vederea unui rezultat particular. Într-adevăr, pe măsură ce probabilitatea se apropie de zero, surpriza devine infinită. Similar, putem interpreta entropia ca și cantitatea medie de surpriză din observarea lui $X$. De exemplu, imaginați-vă că un sistem de mașini slot emite statistic independent simboluri ${s_1, \ldots, s_k}$ cu probabilitățile ${p_1, \ldots, p_k}$ respectiv. Atunci entropia acestui sistem este egală cu auto-informația medie din observarea fiecărei ieșiri, adică,

$$H(S) = \sum_i {p_i \cdot I(s_i)} = - \sum_i {p_i \cdot \log p_i}.$$

Prin exemplele și interpretările de mai sus, putem deriva următoarele proprietăți ale entropiei :eqref:eq_ent_def. Aici, ne referim la $X$ ca un eveniment și $P$ ca distribuția de probabilitate a lui $X$.

• $H(X) \geq 0$ pentru tot $X$ discret (entropia poate fi negativă pentru $X$ continuu).
• Dacă $X \sim P$ cu o p.d.f. sau o p.m.f. $p(x)$, și încercăm să estimăm $P$ printr-o nouă distribuție de probabilitate $Q$ cu o p.d.f. sau o p.m.f. $q(x)$, atunci $$H(X) = - E_{x \sim P} [\log p(x)] \leq - E_{x \sim P} [\log q(x)], \textrm{ cu egalitate dacă și numai dacă } P = Q.$$ Alternativ, $H(X)$ dă o margine inferioară a numărului mediu de biți necesari pentru a codifica simboluri trase din $P$.
• Dacă $X \sim P$, atunci $x$ transmite cantitatea maximă de informație dacă se răspândește uniform printre toate rezultatele posibile. Specific, dacă distribuția de probabilitate $P$ este discretă cu $k$-clase $\{p_1, \ldots, p_k \}$, atunci $$H(X) \leq \log(k), \textrm{ cu egalitate dacă și numai dacă } p_i = \frac{1}{k}, \forall i.$$ Dacă $P$ este o variabilă aleatoare continuă, atunci povestea devine mult mai complicată. Totuși, dacă impunem adițional ca $P$ să fie suportată pe un interval finit (cu toate valorile între $0$ și $1$), atunci $P$ are cea mai mare entropie dacă este distribuția uniformă pe acel interval.

Precedent am definit entropia unei singure variabile aleatoare $X$, cum rămâne cu entropia unei perechi de variabile aleatoare $(X, Y)$? Ne putem gândi la aceste tehnici ca încercând să răspundă la următorul tip de întrebare, „Ce informație este conținută în $X$ și $Y$ împreună comparativ cu fiecare separat? Există informație redundantă, sau este totul unic?”

Pentru următoarea discuție, folosim întotdeauna $(X, Y)$ ca o pereche de variabile aleatoare care urmează o distribuție de probabilitate comună $P$ cu o p.d.f. sau o p.m.f. $p_{X, Y}(x, y)$, în timp ce $X$ și $Y$ urmează distribuția de probabilitate $p_X(x)$ și respectiv $p_Y(y)$.

Similar cu entropia unei singure variabile aleatoare :eqref:eq_ent_def, definim entropia comună $H(X, Y)$ a unei perechi de variabile aleatoare $(X, Y)$ ca

$$H(X, Y) = -E_{(x, y) \sim P} [\log p_{X, Y}(x, y)]. $$

Precis, pe de o parte, dacă $(X, Y)$ este o pereche de variabile aleatoare discrete, atunci

$$H(X, Y) = - \sum_{x} \sum_{y} p_{X, Y}(x, y) \log p_{X, Y}(x, y).$$

Pe de altă parte, dacă $(X, Y)$ este o pereche de variabile aleatoare continue, atunci definim entropia diferențială comună ca

$$H(X, Y) = - \int_{x, y} p_{X, Y}(x, y) \ \log p_{X, Y}(x, y) \;dx \;dy.$$

Ne putem gândi la :eqref:eq_joint_ent_def ca spunându-ne aleatorismul total în perechea de variabile aleatoare. Ca o pereche de extreme, dacă $X = Y$ sunt două variabile aleatoare identice, atunci informația din pereche este exact informația din una și avem $H(X, Y) = H(X) = H(Y)$. La cealaltă extremă, dacă $X$ și $Y$ sunt independente atunci $H(X, Y) = H(X) + H(Y)$. Într-adevăr vom avea întotdeauna că informația conținută într-o pereche de variabile aleatoare nu este mai mică decât entropia oricărei variabile aleatoare și nu mai mult decât suma ambelor.

$$ H(X), H(Y) \le H(X, Y) \le H(X) + H(Y). $$

Să implementăm entropia comună de la zero.

#@tab pytorch
def joint_entropy(p_xy):
    joint_ent = -p_xy * torch.log2(p_xy)
    # Operator `nansum` will sum up the non-nan number
    out = nansum(joint_ent)
    return out
 
joint_entropy(torch.tensor([[0.1, 0.5], [0.1, 0.3]]))

Observați că acesta este același cod ca înainte, dar acum îl interpretăm diferit ca lucrând pe distribuția comună a celor două variabile aleatoare.

Entropia comună definită mai sus cantitatea de informație conținută într-o pereche de variabile aleatoare. Acest lucru este util, dar adesea nu este ceea ce ne pasă. Considerați cadrul învățării automate. Să luăm $X$ să fie variabila aleatoare (sau vectorul de variabile aleatoare) care descrie valorile pixelilor unei imagini, și $Y$ să fie variabila aleatoare care este eticheta clasei. $X$ ar trebui să conțină informație substanțială—o imagine naturală este un lucru complex. Totuși, informația conținută în $Y$ odată ce imaginea a fost arătată ar trebui să fie scăzută. Într-adevăr, imaginea unei cifre ar trebui să conțină deja informația despre ce cifră este, cu excepția cazului în care cifra este ilizibilă. Astfel, pentru a continua să ne extindem vocabularul teoriei informației, trebuie să fim capabili să raționăm despre conținutul informațional într-o variabilă aleatoare condiționată de alta.

În teoria probabilității, am văzut definiția probabilității condiționate pentru a măsura relația dintre variabile. Acum vrem să definim analog entropia condiționată $H(Y \mid X)$. Putem scrie asta ca

$$ H(Y \mid X) = - E_{(x, y) \sim P} [\log p(y \mid x)],$$

unde $p(y \mid x) = \frac{p_{X, Y}(x, y)}{p_X(x)}$ este probabilitatea condiționată. Specific, dacă $(X, Y)$ este o pereche de variabile aleatoare discrete, atunci

$$H(Y \mid X) = - \sum_{x} \sum_{y} p(x, y) \log p(y \mid x).$$

Dacă $(X, Y)$ este o pereche de variabile aleatoare continue, atunci entropia diferențială condiționată este similar definită ca

$$H(Y \mid X) = - \int_x \int_y p(x, y) \ \log p(y \mid x) \;dx \;dy.$$

Este acum natural să întrebăm, cum se relaționează entropia condiționată $H(Y \mid X)$ cu entropia $H(X)$ și entropia comună $H(X, Y)$? Folosind definițiile de mai sus, putem exprima acest lucru clar:

$$H(Y \mid X) = H(X, Y) - H(X).$$

Aceasta are o interpretare intuitivă: informația în $Y$ dată fiind $X$ ($H(Y \mid X)$) este aceeași cu informația în ambele $X$ și $Y$ împreună ($H(X, Y)$) minus informația deja conținută în $X$. Aceasta ne dă informația în $Y$ care nu este reprezentată și în $X$.

Acum, să implementăm entropia condiționată :eqref:eq_cond_ent_def de la zero.

#@tab pytorch
def conditional_entropy(p_xy, p_x):
    p_y_given_x = p_xy/p_x
    cond_ent = -p_xy * torch.log2(p_y_given_x)
    # Operator `nansum` will sum up the non-nan number
    out = nansum(cond_ent)
    return out
 
conditional_entropy(torch.tensor([[0.1, 0.5], [0.2, 0.3]]),
                    torch.tensor([0.2, 0.8]))

Dată fiind setarea anterioară a variabilelor aleatoare $(X, Y)$, v-ați putea întreba: „Acum că știm câtă informație este conținută în $Y$ dar nu în $X$, putem cere similar câtă informație este împărtășită între $X$ și $Y$?” Răspunsul va fi informația mutuală a $(X, Y)$, pe care o vom scrie ca $I(X, Y)$.

Mai degrabă decât să ne scufundăm direct în definiția formală, să ne exersăm intuiția încercând mai întâi să derivăm o expresie pentru informația mutuală bazată în întregime pe termeni pe care i-am construit înainte. Dorim să găsim informația împărtășită între două variabile aleatoare. Un mod în care am putea încerca să facem acest lucru este să începem cu toată informația conținută în ambele $X$ și $Y$ împreună, și apoi scoatem părțile care nu sunt împărtășite. Informația conținută în ambele $X$ și $Y$ împreună este scrisă ca $H(X, Y)$. Vrem să scădem din aceasta informația conținută în $X$ dar nu în $Y$, și informația conținută în $Y$ dar nu în $X$. Așa cum am văzut în secțiunea anterioară, aceasta este dată de $H(X \mid Y)$ și respectiv $H(Y \mid X)$. Astfel, avem că informația mutuală ar trebui să fie

$$ I(X, Y) = H(X, Y) - H(Y \mid X) - H(X \mid Y). $$

Într-adevăr, aceasta este o definiție validă pentru informația mutuală. Dacă extindem definițiile acestor termeni și îi combinăm, puțină algebră arată că aceasta este la fel cu

$$I(X, Y) = E_{x} E_{y} \left\{ p_{X, Y}(x, y) \log\frac{p_{X, Y}(x, y)}{p_X(x) p_Y(y)} \right\}. $$

Putem rezuma toate aceste relații în imaginea . Este un test excelent de intuiție pentru a vedea de ce următoarele afirmații sunt de asemenea echivalente cu $I(X, Y)$.

• $H(X) - H(X \mid Y)$
• $H(Y) - H(Y \mid X)$
• $H(X) + H(Y) - H(X, Y)$

În multe feluri ne putem gândi la informația mutuală :eqref:eq_mut_ent_def ca o extensie principială a coeficientului de corelație pe care l-am văzut în . Aceasta ne permite să cerem nu doar relații liniare între variabile, ci și informația maximă împărtășită între cele două variabile aleatoare de orice fel.

Acum, să implementăm informația mutuală de la zero.

#@tab pytorch
def mutual_information(p_xy, p_x, p_y):
    p = p_xy / (p_x * p_y)
    mutual = p_xy * torch.log2(p)
    # Operator `nansum` will sum up the non-nan number
    out = nansum(mutual)
    return out
 
mutual_information(torch.tensor([[0.1, 0.5], [0.1, 0.3]]),
                   torch.tensor([0.2, 0.8]), torch.tensor([[0.75, 0.25]]))

Mai degrabă decât să memorați definiția informației mutuale :eqref:eq_mut_ent_def, trebuie doar să țineți minte proprietățile sale notabile:

• Informația mutuală este simetrică, adică, $I(X, Y) = I(Y, X)$.
• Informația mutuală este non-negativă, adică, $I(X, Y) \geq 0$.
• $I(X, Y) = 0$ dacă și numai dacă $X$ și $Y$ sunt independente. De exemplu, dacă $X$ și $Y$ sunt independente, atunci cunoașterea lui $Y$ nu oferă nicio informație despre $X$ și viceversa, deci informația lor mutuală este zero.
• Alternativ, dacă $X$ este o funcție inversabilă a lui $Y$, atunci $Y$ și $X$ împărtășesc toată informația și $$I(X, Y) = H(Y) = H(X).$$

Când am lucrat cu entropia la începutul acestui capitol, am putut oferi o interpretare a $-\log(p_X(x))$ ca și cât de surprinși am fost de rezultatul particular. Putem da o interpretare similară termenului logaritmic din informația mutuală, care este adesea referit ca informația mutuală punctuală:

$$\textrm{pmi}(x, y) = \log\frac{p_{X, Y}(x, y)}{p_X(x) p_Y(y)}.$$

Ne putem gândi la :eqref:eq_pmi_def ca măsurând cât de mult mai probabilă sau mai puțin probabilă este combinația specifică de rezultate $x$ și $y$ comparativ cu cea la care ne-am aștepta pentru rezultate aleatoare independente. Dacă este mare și pozitivă, atunci aceste două rezultate specifice apar mult mai frecvent decât ar face-o comparativ cu șansa aleatoare (notă: numitorul este $p_X(x) p_Y(y)$ care este probabilitatea ca cele două rezultate să fie independente), în timp ce dacă este mare și negativă reprezintă cele două rezultate întâmplându-se mult mai puțin decât ne-am aștepta prin șansă aleatoare.

Acest lucru ne permite să interpretăm informația mutuală :eqref:eq_mut_ent_def ca și cantitatea medie cu care am fost surprinși să vedem două rezultate apărând împreună comparativ cu ceea ce ne-am aștepta dacă ar fi independente.

Informația mutuală poate fi puțin abstractă în definiția ei pură, deci cum se relaționează cu învățarea automată? În procesarea limbajului natural, una dintre cele mai dificile probleme este rezolvarea ambiguității, sau problema sensului unui cuvânt fiind neclar din context. De exemplu, recent un titlu din știri a raportat că „Amazon is on fire” („Amazon este în flăcări”). V-ați putea întreba dacă compania Amazon are o clădire în flăcări, sau pădurea Amazoniană este în flăcări.

În acest caz, informația mutuală ne poate ajuta să rezolvăm această ambiguitate. Găsim mai întâi grupul de cuvinte care au fiecare o informație mutuală relativ mare cu compania Amazon, cum ar fi e-commerce, tehnologie, și online. În al doilea rând, găsim un alt grup de cuvinte care au fiecare o informație mutuală relativ mare cu pădurea Amazoniană, cum ar fi ploaie, pădure, și tropical. Când trebuie să dezambiguizăm „Amazon”, putem compara care grup are mai multă apariție în contextul cuvântului Amazon. În acest caz articolul ar continua să descrie pădurea, și să facă contextul clar.

Așa cum am discutat în , putem folosi norme pentru a măsura distanța dintre două puncte în spațiu de orice dimensionalitate. Am dori să putem face o sarcină similară cu distribuțiile de probabilitate. Există multe căi de a aborda acest lucru, dar teoria informației oferă una dintre cele mai drăguțe. Explorăm acum Divergența Kullback–Leibler (KL), care oferă o cale de a măsura dacă două distribuții sunt apropiate sau nu.

Dată fiind o variabilă aleatoare $X$ care urmează distribuția de probabilitate $P$ cu o p.d.f. sau o p.m.f. $p(x)$, și estimăm $P$ printr-o altă distribuție de probabilitate $Q$ cu o p.d.f. sau o p.m.f. $q(x)$. Atunci Divergența Kullback–Leibler (KL) (sau entropia relativă) dintre $P$ și $Q$ este

$$D_{\textrm{KL}}(P\|Q) = E_{x \sim P} \left[ \log \frac{p(x)}{q(x)} \right].$$

Ca și cu informația mutuală punctuală :eqref:eq_pmi_def, putem oferi din nou o interpretare a termenului logaritmic: $-\log \frac{q(x)}{p(x)} = -\log(q(x)) - (-\log(p(x)))$ va fi mare și pozitiv dacă vedem $x$ mult mai des sub $P$ decât ne-am aștepta pentru $Q$, și mare și negativ dacă vedem rezultatul mult mai puțin decât așteptat. În acest fel, îl putem interpreta ca surpriza noastră relativă la observarea rezultatului comparativ cu cât de surprinși am fi observându-l din distribuția noastră de referință.

Să implementăm divergența KL de la zero.

#@tab pytorch
def kl_divergence(p, q):
    kl = p * torch.log2(p / q)
    out = nansum(kl)
    return out.abs().item()

Să aruncăm o privire la unele proprietăți ale divergenței KL :eqref:eq_kl_def.

• Divergența KL este ne-simetrică, adică, există $P,Q$ astfel încât $$D_{\textrm{KL}}(P\|Q) \neq D_{\textrm{KL}}(Q\|P).$$
• Divergența KL este non-negativă, adică, $$D_{\textrm{KL}}(P\|Q) \geq 0.$$ Rețineți că egalitatea are loc doar când $P = Q$.
• Dacă există un $x$ astfel încât $p(x) > 0$ și $q(x) = 0$, atunci $D_{\textrm{KL}}(P\|Q) = \infty$.
• <WRAP>

Există o relație strânsă între divergența KL și informația mutuală. Pe lângă relația arătată în , $I(X, Y)$ este de asemenea echivalent numeric cu următorii termeni:

1. $D_{\textrm{KL}}(P(X, Y) \ \| \ P(X)P(Y))$;
2. $E_Y \{ D_{\textrm{KL}}(P(X \mid Y) \ \| \ P(X)) \}$;
3. $E_X \{ D_{\textrm{KL}}(P(Y \mid X) \ \| \ P(Y)) \}$.

Pentru primul termen, interpretăm informația mutuală ca divergența KL dintre $P(X, Y)$ și produsul lui $P(X)$ și $P(Y)$, și astfel este o măsură a cât de diferită este distribuția comună față de distribuție dacă ar fi independente. Pentru al doilea termen, informația mutuală ne spune reducerea medie în incertitudinea despre $Y$ care rezultă din învățarea valorii distribuției lui $X$. Similar pentru al treilea termen. </WRAP>

Să trecem printr-un exemplu de jucărie pentru a vedea ne-simetria explicit.

Mai întâi, să generăm și să sortăm trei tensori de lungime $10,000$: un tensor obiectiv $p$ care urmează o distribuție normală $N(0, 1)$, și doi tensori candidați $q_1$ și $q_2$ care urmează distribuții normale $N(-1, 1)$ și respectiv $N(1, 1)$.

#@tab pytorch
torch.manual_seed(1)
 
tensor_len = 10000
p = torch.normal(0, 1, (tensor_len, ))
q1 = torch.normal(-1, 1, (tensor_len, ))
q2 = torch.normal(1, 1, (tensor_len, ))
 
p = torch.sort(p)[0]
q1 = torch.sort(q1)[0]
q2 = torch.sort(q2)[0]

Deoarece $q_1$ și $q_2$ sunt simetrice în raport cu axa y (adică, $x=0$), ne așteptăm la o valoare similară a divergenței KL între $D_{\textrm{KL}}(p\|q_1)$ și $D_{\textrm{KL}}(p\|q_2)$. Așa cum puteți vedea mai jos, există doar o diferență de mai puțin de 3% între $D_{\textrm{KL}}(p\|q_1)$ și $D_{\textrm{KL}}(p\|q_2)$.

#@tab all
kl_pq1 = kl_divergence(p, q1)
kl_pq2 = kl_divergence(p, q2)
similar_percentage = abs(kl_pq1 - kl_pq2) / ((kl_pq1 + kl_pq2) / 2) * 100
 
kl_pq1, kl_pq2, similar_percentage

În contrast, veți găsi că $D_{\textrm{KL}}(q_2 \|p)$ și $D_{\textrm{KL}}(p \| q_2)$ sunt foarte diferite, cu o diferență de aproximativ 40% așa cum este arătat mai jos.

#@tab all
kl_q2p = kl_divergence(q2, p)
differ_percentage = abs(kl_q2p - kl_pq2) / ((kl_q2p + kl_pq2) / 2) * 100
 
kl_q2p, differ_percentage

Dacă sunteți curioși despre aplicațiile teoriei informației în învățarea profundă, iată un exemplu rapid. Definim distribuția adevărată $P$ cu distribuția de probabilitate $p(x)$, și distribuția estimată $Q$ cu distribuția de probabilitate $q(x)$, și le vom folosi în restul acestei secțiuni.

Spuneți că trebuie să rezolvăm o problemă de clasificare binară bazată pe $n$ exemple de date date {$x_1, \ldots, x_n$}. Presupuneți că codificăm $1$ și $0$ ca eticheta de clasă pozitivă și respectiv negativă $y_i$, și rețeaua noastră neuronală este parametrizată de $\theta$. Dacă urmărim să găsim cel mai bun $\theta$ astfel încât $\hat{y}_i= p_{\theta}(y_i \mid x_i)$, este natural să aplicăm abordarea log-verosimilității maxime așa cum a fost văzut în . Pentru a fi specifici, pentru etichetele adevărate $y_i$ și predicțiile $\hat{y}_i= p_{\theta}(y_i \mid x_i)$, probabilitatea de a fi clasificat ca pozitiv este $\pi_i= p_{\theta}(y_i = 1 \mid x_i)$. Prin urmare, funcția log-verosimilitate ar fi

$$ \begin{aligned} l(\theta) &= \log L(\theta) \\ &= \log \prod_{i=1}^n \pi_i^{y_i} (1 - \pi_i)^{1 - y_i} \\ &= \sum_{i=1}^n y_i \log(\pi_i) + (1 - y_i) \log (1 - \pi_i). \\ \end{aligned} $$

Maximizarea funcției log-verosimilitate $l(\theta)$ este identică cu minimizarea $- l(\theta)$, și prin urmare putem găsi cel mai bun $\theta$ de aici. Pentru a generaliza pierderea de mai sus la orice distribuții, am numit de asemenea $-l(\theta)$ pierderea de entropie încrucișată $\textrm{CE}(y, \hat{y})$, unde $y$ urmează distribuția adevărată $P$ și $\hat{y}$ urmează distribuția estimată $Q$.

Toate acestea au fost derivate lucrând din punctul de vedere al verosimilității maxime. Totuși, dacă privim îndeaproape putem vedea că termeni precum $\log(\pi_i)$ au intrat în calculul nostru ceea ce este un indiciu solid că putem înțelege expresia dintr-un punct de vedere al teoriei informației.

Ca și divergența KL, pentru o variabilă aleatoare $X$, putem măsura divergența dintre distribuția estimată $Q$ și distribuția adevărată $P$ via entropie încrucișată,

$$\textrm{CE}(P, Q) = - E_{x \sim P} [\log(q(x))].$$

Folosind proprietățile entropiei discutate mai sus, o putem interpreta de asemenea ca suma entropiei $H(P)$ și divergenței KL dintre $P$ și $Q$, adică,

$$\textrm{CE} (P, Q) = H(P) + D_{\textrm{KL}}(P\|Q).$$

Putem implementa pierderea de entropie încrucișată ca mai jos.

#@tab pytorch
def cross_entropy(y_hat, y):
    ce = -torch.log(y_hat[range(len(y_hat)), y])
    return ce.mean()

Acum definiți doi tensori pentru etichete și predicții, și calculați pierderea de entropie încrucișată a lor.

#@tab pytorch
labels = torch.tensor([0, 2])
preds = torch.tensor([[0.3, 0.6, 0.1], [0.2, 0.3, 0.5]])
 
cross_entropy(preds, labels)

Așa cum s-a aluzionat la începutul acestei secțiuni, entropia încrucișată :eqref:eq_ce_def poate fi folosită pentru a defini o funcție de pierdere în problema de optimizare. Se dovedește că următoarele sunt echivalente:

1. Maximizarea probabilității predictive a lui $Q$ pentru distribuția $P$, (adică, $E_{x

\sim P} [\log (q(x))]$);

1. Minimizarea entropiei încrucișate $\textrm{CE} (P, Q)$;
2. Minimizarea divergenței KL $D_{\textrm{KL}}(P\|Q)$.

Definiția entropiei încrucișată demonstrează indirect relația echivalentă dintre obiectivul 2 și obiectivul 3, atâta timp cât entropia datelor adevărate $H(P)$ este constantă.

Dacă ne scufundăm adânc în funcția obiectiv de clasificare cu pierdere de entropie încrucișată $\textrm{CE}$, vom găsi că minimizarea $\textrm{CE}$ este echivalentă cu maximizarea funcției log-verosimilitate $L$.

Pentru a începe, presupuneți că ni se dă un set de date cu $n$ exemple, și poate fi clasificat în $k$-clase. Pentru fiecare exemplu de date $i$, reprezentăm orice etichetă de $k$-clasă $\mathbf{y}_i = (y_{i1}, \ldots, y_{ik})$ prin codificare one-hot. Pentru a fi specifici, dacă exemplul $i$ aparține clasei $j$, atunci setăm a $j$-a intrare la $1$, și toate celelalte componente la $0$, adică,

$$ y_{ij} = \begin{cases}1 & j \in J; \\ 0 &\textrm{altfel.}\end{cases}$$

De exemplu, dacă o problemă de clasificare multi-clasă conține trei clase $A$, $B$, și $C$, atunci etichetele $\mathbf{y}_i$ pot fi codificate în {$A: (1, 0, 0); B: (0, 1, 0); C: (0, 0, 1)$}.

Presupuneți că rețeaua noastră neuronală este parametrizată de $\theta$. Pentru vectorii de etichete adevărate $\mathbf{y}_i$ și predicțiile $$\hat{\mathbf{y}}_i= p_{\theta}(\mathbf{y}_i \mid \mathbf{x}_i) = \sum_{j=1}^k y_{ij} p_{\theta} (y_{ij} \mid \mathbf{x}_i).$$

Prin urmare, pierderea de entropie încrucișată ar fi

$$ \textrm{CE}(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{i=1}^n \mathbf{y}_i \log \hat{\mathbf{y}}_i = - \sum_{i=1}^n \sum_{j=1}^k y_{ij} \log{p_{\theta} (y_{ij} \mid \mathbf{x}_i)}.\\ $$

Pe de altă parte, putem de asemenea aborda problema prin estimarea verosimilității maxime. Pentru a începe, să introducem rapid o distribuție multinoulli cu $k$-clase. Este o extensie a distribuției Bernoulli de la clasa binară la multi-clasă. Dacă o variabilă aleatoare $\mathbf{z} = (z_{1}, \ldots, z_{k})$ urmează o distribuție multinoulli cu $k$-clase cu probabilitățile $\mathbf{p} =$ ($p_{1}, \ldots, p_{k}$), adică, $$p(\mathbf{z}) = p(z_1, \ldots, z_k) = \textrm{Multi} (p_1, \ldots, p_k), \textrm{ unde } \sum_{i=1}^k p_i = 1,$$ atunci funcția de masă a probabilității (p.m.f.) comună a lui $\mathbf{z}$ este $$\mathbf{p}^\mathbf{z} = \prod_{j=1}^k p_{j}^{z_{j}}.$$

Se poate vedea că eticheta fiecărui exemplu de date, $\mathbf{y}_i$, urmează o distribuție multinoulli cu $k$-clase cu probabilitățile $\boldsymbol{\pi} =$ ($\pi_{1}, \ldots, \pi_{k}$). Prin urmare, p.m.f. comună a fiecărui exemplu de date $\mathbf{y}_i$ este $\mathbf{\pi}^{\mathbf{y}_i} = \prod_{j=1}^k \pi_{j}^{y_{ij}}.$ Prin urmare, funcția log-verosimilitate ar fi

$$ \begin{aligned} l(\theta) = \log L(\theta) = \log \prod_{i=1}^n \boldsymbol{\pi}^{\mathbf{y}_i} = \log \prod_{i=1}^n \prod_{j=1}^k \pi_{j}^{y_{ij}} = \sum_{i=1}^n \sum_{j=1}^k y_{ij} \log{\pi_{j}}.\\ \end{aligned} $$

Deoarece în estimarea verosimilității maxime, maximizăm funcția obiectiv $l(\theta)$ având $\pi_{j} = p_{\theta} (y_{ij} \mid \mathbf{x}_i)$. Prin urmare, pentru orice clasificare multi-clasă, maximizarea funcției log-verosimilitate de mai sus $l(\theta)$ este echivalentă cu minimizarea pierderii CE $\textrm{CE}(y, \hat{y})$.

Pentru a testa demonstrația de mai sus, să aplicăm măsura încorporată NegativeLogLikelihood. Folosind aceleași labels și preds ca în exemplul anterior, vom obține aceeași pierdere numerică ca exemplul anterior până la a 5-a zecimală.

#@tab pytorch
# Implementation of cross-entropy loss in PyTorch combines `nn.LogSoftmax()`
# and `nn.NLLLoss()`
nll_loss = NLLLoss()
loss = nll_loss(torch.log(preds), labels)
loss

• Teoria informației este un domeniu de studiu despre codificarea, decodificarea, transmiterea și manipularea informației.
• Entropia este unitatea pentru a măsura câtă informație este prezentată în diferite semnale.
• Divergența KL poate măsura de asemenea divergența dintre două distribuții.
• Entropia încrucișată poate fi privită ca o funcție obiectiv a clasificării multi-clasă. Minimizarea pierderii de entropie încrucișată este echivalentă cu maximizarea funcției log-verosimilitate.

1. Verificați că exemplele cu cărți din prima secțiune au într-adevăr entropia revendicată.
2. Arătați că divergența KL $D(p\|q)$ este non-negativă pentru toate distribuțiile $p$ și $q$. Sugestie: folosiți inegalitatea lui Jensen, adică, folosiți faptul că $-\log x$ este o funcție convexă.
3. Să calculăm entropia din câteva surse de date:
   • Presupuneți că urmăriți ieșirea generată de o maimuță la o mașină de scris. Maimuța apasă oricare dintre cele $44$ de taste ale mașinii de scris la întâmplare (puteți presupune că nu a descoperit încă nicio tastă specială sau tasta shift). Câți biți de aleatorism pe caracter observați?
   • Fiind nemulțumit de maimuță, ați înlocuit-o cu un tipograf beat. Este capabil să genereze cuvinte, deși nu coerent. În schimb, alege un cuvânt aleatoriu dintr-un vocabular de $2,000$ de cuvinte. Să presupunem că lungimea medie a unui cuvânt este de $4.5$ litere în engleză. Câți biți de aleatorism pe caracter observați acum?
   • Fiind încă nemulțumit de rezultat, înlocuiți tipograful cu un model de limbaj de înaltă calitate. Modelul de limbaj poate obține în prezent o perplexitate de până la $15$ puncte pe cuvânt. Perplexitatea caracterului unui model de limbaj este definită ca inversul mediei geometrice a unui set de probabilități, fiecare probabilitate corespunzând unui caracter din cuvânt. Specific, dacă lungimea unui cuvânt dat este $l$, atunci $\textrm{PPL}(\textrm{word}) = \left[\prod_i p(\textrm{character}_i)\right]^{ -\frac{1}{l}} = \exp \left[ - \frac{1}{l} \sum_i{\log p(\textrm{character}_i)} \right].$ Presupuneți că cuvântul de test are 4.5 litere, câți biți de aleatorism pe caracter observați acum?
4. Explicați intuitiv de ce $I(X, Y) = H(X) - H(X \mid Y)$. Apoi, arătați că acest lucru este adevărat exprimând ambele părți ca o așteptare cu privire la distribuția comună.
5. Care este Divergența KL dintre cele două distribuții Gaussiene $\mathcal{N}(\mu_1, \sigma_1^2)$ și $\mathcal{N}(\mu_2, \sigma_2^2)$?

Discuții