Kullback-Leibler divergens

I sannsynlighetsteori og informasjonsteori er Kullback-Leibler (eller KL-divergens , eller relativ entropi ) et mål på ulikhet mellom to fordelinger av sannsynligheter. Det skylder navnet sitt til Solomon Kullback og Richard Leibler , to amerikanske kryptanalytikere. I følge NSA , var det i løpet av 1950-tallet, mens de jobbet for dette byrået, at Kullback og Leibler oppfant dette tiltaket. Det ville også ha tjent NSA i sitt kryptanalysearbeid for Venona-prosjektet .

Introduksjon og bakgrunn

Tenk på to sannsynlighetsfordelinger P og Q. Vanligvis representerer P data, observasjoner eller en nøyaktig beregnet sannsynlighetsfordeling. Fordeling Q representerer typisk en teori, en modell, en beskrivelse eller en tilnærming til P . Kullback-Leibler-divergensen tolkes som den gjennomsnittlige forskjellen i antall biter som trengs for å kode eksempler på P ved hjelp av en kode optimalisert for Q i stedet for koden optimalisert for P .

Definisjon

Det er flere definisjoner avhengig av antakelsene om sannsynlighetsfordelingene.

Første definisjoner

For to diskrete sannsynlighetsfordelinger P og Q er Kullback-Leibler-divergensen av P med hensyn til Q definert av

D _ {{{\ mathrm {KL}}}} (P \ | Q) = \ sum _ {i} P (i) \ log {\ frac {P (i)} {Q (i)}} \!

For kontinuerlige P- og Q- fordelinger bruker vi en integral

D _ {{{\ mathrm {KL}}}} (P \ | Q) = \ int _ {{- \ infty}} ^ {{\ infty}} p (x) \ log {\ frac {p (x )} {q (x)}} \; dx \!

hvor p og q er de respektive tettheter av P og Q .

Med andre ord er Kullback-Leibler-divergensen forventningen om forskjellen mellom logaritmene til P og Q, og tar sannsynligheten P for å beregne forventningen.

Generelle definisjoner

Vi kan generalisere de to spesifikke tilfellene ovenfor ved å vurdere P og Q to mål definert på et sett X , absolutt kontinuerlig med hensyn til et mål : Radon-Nikodym-Lebesgue-setningen sikrer eksistensen av tetthetene p og q med og vi deretter spørre $\ mu$ $dP = pd \ mu$ $dQ = qd \ mu$

D _ {{{\ mathrm {KL}}}} (P \ | Q) = \ int _ {X} p \ log {\ frac {p} {q}} \; d \ mu \!

forutsatt at riktig mengde eksisterer. Hvis P er absolutt kontinuerlig med hensyn til Q , (som er nødvendig hvis det er endelig), er da Radon-Nikodym-derivatet av P med hensyn til Q, og vi får $D _ {{{\ mathrm {KL}}}} (P \ | Q)$ ${\ frac {p} {q}} = {\ frac {dP} {dQ}}$

D _ {{{\ mathrm {KL}}}} (P \ | Q) = \ int _ {X} \ log {\ frac {dP} {dQ}} \; dP = \ int _ {X} {\ frac {dP} {dQ}} \ log {\ frac {dP} {dQ}} \; dQ \, \!

hvor man erkjenner entropien av P med hensyn til Q .

Tilsvarende, hvis Q er absolutt kontinuerlig med hensyn til P , har vi det

D _ {{{\ mathrm {KL}}}} (P \ | Q) = - \ int _ {X} \ log {\ frac {dQ} {dP}} \; dP \!

I begge tilfeller ser vi at Kullback-Leibler-avviket ikke avhenger av tiltaket $\ mu$

Når logaritmene til disse formlene er tatt i base 2, blir informasjonen målt i bits ; når basen er null , er enheten nat .

Eksempel

Kullback gir følgende eksempel (tabell 2.1, eksempel 2.1). La P og Q være fordelingen gitt i tabellen og figuren. P er fordelingen på venstre side av figuren, det er en binomialfordeling med N = 2 og p = 0,4. Q er fordelingen av høyre side av figuren, en diskret uniform fordeling med tre verdier x = 0, 1 eller 2, hver med sannsynlighet p = 1/3.

	0	1	2
Fordeling P	0,36	0,48	0,16
Q-fordeling	0,333	0,333	0,333

KL-avviket beregnes som følger. Vi bruker den naturlige logaritmen.

{\ displaystyle {\ begin {align} D _ {\ text {KL}} (Q \ parallell P) & = \ sum _ {i} Q (i) \ ln \ venstre ({\ frac {Q (i)} {P (i)}} \ høyre) \\ [6pt] & = 0,333 \ ln \ venstre ({\ frac {0,333} {0,36}} \ høyre) +0,333 \ ln \ venstre ({\ frac {0,333} { 0.48}} \ høyre) +0.333 \ ln \ venstre ({\ frac {0.333} {0.16}} \ høyre) \\ [6pt] & = - 0.02596 + (- 0.12176) +0.24408 \\ [6pt] & = 0.09637 \ end {align}}}

Eiendommer

$D _ {{{\ mathrm {KL}}}} (P \ | Q) \ geq 0$
${\ displaystyle P \; {\ stackrel {ps} {=}} \; Q}$ hvis $D _ {{{\ mathrm {KL}}}} (P \ | Q) = 0$

Bevis (diskret sak)

D _ {{{\ mathrm {KL}}}} (P \ | Q) = \ sum _ {i} P (i) \ log {\ frac {P (i)} {Q (i)}} = - \ sum _ {i} P (i) \ log {\ frac {Q (i)} {P (i)}} \!

Nå er logaritmen strengt konkav, og bruker Jensens ulikhet :

\ sum _ {i} P (i) \ log {\ frac {Q (i)} {P (i)}} \ leq \ log \ left (\ sum _ {i} P (i) {\ frac {Q (i)} {P (i)}} \ høyre) = \ log \ sum _ {i} Q (i) = \ log (1) = 0 \!

Med likhet er iff konstant nesten overalt . (på grunn av den strenge konkaviteten) I dette tilfellet kan konstanten bare være lik 1 siden de to funksjonene P og Q er sannsynligheter. Derav egenskapene. ${\ frac {Q (i)} {P (i)}}$

Tilsetningsevne. La to skillbare distribusjoner og $P _ {{12}} (x_ {1}, x_ {2}) = P_ {1} (x_ {1}). P_ {2} (x_ {2})$ $Q _ {{12}} (x_ {1}, x_ {2}) = Q_ {1} (x_ {1}). Q_ {2} (x_ {2})$

D (P _ {{12}} \ | Q _ {{12}}) = D (P_ {1} \ | Q_ {1}) + D (P_ {2} \ | Q_ {2})

I informasjonsgeometriformalismen utviklet av S. Amari, er Kullback-Leibler-divergensen divergensen assosiert med to grunnleggende doble affineforbindelser : m-forbindelsen (blanding, additiv kombinasjon av distribusjoner) og e-forbindelsen (eksponentiell, multiplikativ kombinasjon av distribusjoner) . Kullback-Leibler-avviket adlyder lokalt Fisher-beregningen og tilsvarer integrasjonen av avstanden mellom to punkter (fordelinger) langs en geodesikk av typen e eller m (avhengig av om man vurderer en retning eller l 'annen: eller ). $D (P \ | Q)$ $D (Q \ | P)$
Den symmetriske avstanden (indusert av Levi-Civita-forbindelsen , autoduale) assosiert med Fisher-metriske er Hellinger-avstanden $D_ {H} (P \ | Q) = 2 \ sum _ {i} \ left ({\ sqrt {P_ {i}}} - {\ sqrt {Q_ {i}}} \ right) ^ {2}.$

Diskusjon

Selv om den ofte oppfattes som en avstand , oppfyller den ikke betingelsene: den er ikke symmetrisk og respekterer ikke den trekantede ulikheten.

Kullback-Leibler-avviket faller inn i den større kategorien av f- avvik, introdusert uavhengig av Csiszár i 1967 og av Ali og Silvey i 1966. Ved å tilhøre denne familien respekterer den egenskapene til bevaring av informasjon: invarians, monotonisitet.

Utfyllende er Kullback-Leibler-divergensen også en Bregman-divergens , assosiert med den potensielle funksjonen . Konsekvensen er at dette avvik ved Legendre transformasjon av er forbundet med en dobbelt dreiemoment koordinatsystem for å representere fordelinger av den eksponentielle familien . $\ psi (x) = x \ log xx$ $\ psi$ $(x, \ log x)$

Merknader og referanser

Kullback og Leibler 1951 .
Kullback 1959 .
S. Kullback , informasjonsteori og statistikk , John Wiley & Sons ,1959. Gjenutgitt av Dover Publications i 1968; omtrykket i 1978: ( ISBN 0-8446-5625-9 ) .
Amari og Nagaoka 2000 .
Csiszár 1967 .
Ali og Silvey 1967 .
Amari 2010 .
Bregman 1967 .

Vedlegg

Bibliografi

[Ali og Silvey 1967] (en) MS Ali og D. Silvey, " En generell klasse av koeffisienter for avvik fra en distribusjon fra en annen " , Journal of the Royal Statistical Society , Ser. B , vol. 28,1967, s. 131-140.
[Amari og Nagaoka 2000] (en) Sunichi Amari og Hiroshi Nagaoka , Methods of information geometry , vol. 191, American Mathematical Society,2000.
[Amari 2010] (en) Sunichi Amari, “ Informasjonsgeometri i optimalisering, maskinlæring og statistisk inferens ” , Frontiers of Electrical and Electronic Engineering in China , SP Higher Education Press, vol. 5, n o 3,september 2010, s. 241–260 ( DOI 10.1007 / s11460-010-0101-3 ).
[Bregman 1967] (en) L. Bregman, “ Relaxasjonsmetoden for å finne det felles punktet for konvekse sett og dets anvendelse på løsningen av problemer i konveks programmering ” , USSR Computational Mathematics and Mathematical Physics , vol. 7, n o 3,1967, s. 200–217 ( DOI 10.1016 / 0041-5553 (67) 90040-7 ).
[Csiszár] (en) I. Csiszár, “ Informasjonstype mål på forskjell mellom sannsynlighetsfordelinger og indirekte observasjon ” , Studia Sci. Matte. Hungar. , vol. 2,1967, s. 229-318.
[Kullback og Leibler 1951] (in) S. og R. Kullback Leibler, " er informasjon og tilstrekkelig " , Annals of Mathematical Statistics , Vol. 22,1951, s. 79-86.
[Kullback 1959] (no) S. Kullback, Informasjonsteori og statistikk , New York, John Wiley og Sons,1959.

Se også