Kullback-Leibler divergens

I sandsynlighedsteori og informationsteori er Kullback-Leibler (eller KL-divergens eller relativ entropi ) et mål for ulighed mellem to fordelinger af sandsynligheder. Det skylder sit navn Solomon Kullback og Richard Leibler , to amerikanske kryptanalytikere. Ifølge NSA , var det i 1950'erne, mens de arbejdede for dette agentur, at Kullback og Leibler opfandt denne foranstaltning. Det ville også have tjent NSA i sin kryptanalyseindsats for Venona-projektet .

Introduktion og baggrund

Overvej to sandsynlighedsfordelinger P og Q. Typisk repræsenterer P data, observationer eller en nøjagtigt beregnet sandsynlighedsfordeling. Distribution Q betegner typisk en teori, en model, en beskrivelse eller en tilnærmelse af P . Kullback-Leibler-divergensen fortolkes som den gennemsnitlige forskel i antallet af bits, der er nødvendige for at kode for prøver af P ved hjælp af en kode optimeret til Q i stedet for den kode, der er optimeret til P .

Definition

Der er flere definitioner afhængigt af antagelserne om sandsynlighedsfordelingerne.

Første definitioner

For to diskrete sandsynlighedsfordelinger P og Q defineres Kullback-Leibler-divergensen af P med hensyn til Q ved

DKL(P‖Q)=∑jegP(jeg)log⁡P(jeg)Q(jeg){\ displaystyle D _ {\ mathrm {KL}} (P \ | Q) = \ sum _ {i} P (i) \ log {\ frac {P (i)} {Q (i)}} \!}.

Til kontinuerlige P- og Q- distributioner bruger vi en integral

DKL(P‖Q)=∫-∞∞s(x)log⁡s(x)q(x)dx{\ displaystyle D _ {\ mathrm {KL}} (P \ | Q) = \ int _ {- \ infty} ^ {\ infty} p (x) \ log {\ frac {p (x)} {q ( x)}} \; dx \!}

hvor p og q er de respektive densiteter af P og Q .

Med andre ord er Kullback-Leibler-divergensen forventningen om forskellen mellem logaritmerne P og Q, idet sandsynligheden P tages for at beregne forventningen.

Generelle definitioner

Vi kan generalisere de to særlige tilfælde ovenfor ved at overveje P og Q to mål defineret på et sæt X , absolut kontinuerligt i forhold til et mål  : Radon-Nikodym-Lebesgue-sætningen sikrer eksistensen af ​​tæthederne p og q med og vi derefter spørge μ{\ displaystyle \ mu}dP=sdμ{\ displaystyle dP = pd \ mu}dQ=qdμ{\ displaystyle dQ = qd \ mu}

DKL(P‖Q)=∫xslog⁡sqdμ{\ displaystyle D _ {\ mathrm {KL}} (P \ | Q) = \ int _ {X} p \ log {\ frac {p} {q}} \; d \ mu \!}

forudsat at den rigtige mængde findes. Hvis P er absolut kontinuerlig i forhold til Q , (hvilket er nødvendigt, hvis det er endeligt), så er Radon-Nikodym-derivatet af P med hensyn til Q, og vi får DKL(P‖Q){\ displaystyle D _ {\ mathrm {KL}} (P \ | Q)}sq=dPdQ{\ displaystyle {\ frac {p} {q}} = {\ frac {dP} {dQ}}}

DKL(P‖Q)=∫xlog⁡dPdQdP=∫xdPdQlog⁡dPdQdQ{\ displaystyle D _ {\ mathrm {KL}} (P \ | Q) = \ int _ {X} \ log {\ frac {dP} {dQ}} \; dP = \ int _ {X} {\ frac {dP} {dQ}} \ log {\ frac {dP} {dQ}} \; dQ \, \!},

hvor man anerkender entropien af P med hensyn til Q .

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

DKL(P‖Q)=-∫xlog⁡dQdPdP{\ displaystyle D _ {\ mathrm {KL}} (P \ | Q) = - \ int _ {X} \ log {\ frac {dQ} {dP}} \; dP \!}

I begge tilfælde ser vi, at Kullback-Leibler-divergensen ikke afhænger af foranstaltningen μ{\ displaystyle \ mu}

Når logaritmerne med disse formler tages i base 2, måles informationen i bits ; når basen er nul , er enheden nat .

Eksempel

Kullback giver følgende eksempel (tabel 2.1, eksempel 2.1). Lad P og Q være fordelingen i tabellen og figuren. P er fordelingen på venstre side af figuren, det er en binomial fordeling med N = 2 og p = 0,4. Q er fordelingen af ​​højre side af figuren, en diskret ensartet fordeling med tre værdier x = 0, 1 eller 2, hver med sandsynlighed p = 1/3.

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

KL-afvigelsen beregnes som følger. Vi bruger den naturlige logaritme.

DKL(Q∥P)=∑jegQ(jeg)ln⁡(Q(jeg)P(jeg))=0,333ln⁡(0,3330,36)+0,333ln⁡(0,3330,48)+0,333ln⁡(0,3330,16)=-0,02596+(-0.12176)+0,24408=0,09637{\ displaystyle {\ begin {align} D _ {\ text {KL}} (Q \ parallel P) & = \ sum _ {i} Q (i) \ ln \ left ({\ frac {Q (i)} {P (i)}} \ højre) \\ [6pt] & = 0,333 \ ln \ venstre ({\ frac {0,333} {0,36}} \ højre) +0,333 \ ln venstre ({\ frac {0,333} { 0,48}} \ højre) +0,333 \ ln \ venstre ({\ frac {0,333} {0,16}} \ højre) \\ [6pt] & = - 0,02596 + (- 0,122176) +0,24408 \\ [6pt] & = 0,09637 \ end {justeret}}}

Ejendomme

• DKL(P‖Q)≥0{\ displaystyle D _ {\ mathrm {KL}} (P \ | Q) \ geq 0}
• P=s.s.Q{\ displaystyle P \; {\ stackrel {ps} {=}} \; Q} hvis DKL(P‖Q)=0{\ displaystyle D _ {\ mathrm {KL}} (P \ | Q) = 0}

Bevis (diskret sag) DKL(P‖Q)=∑jegP(jeg)log⁡P(jeg)Q(jeg)=-∑jegP(jeg)log⁡Q(jeg)P(jeg){\ displaystyle 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)}} \!}

Nu er logaritmen strengt konkav og bruger derfor Jensens ulighed :

∑jegP(jeg)log⁡Q(jeg)P(jeg)≤log⁡(∑jegP(jeg)Q(jeg)P(jeg))=log⁡∑jegQ(jeg)=log⁡(1)=0{\ displaystyle \ sum _ {i} P (i) \ log {\ frac {Q (i)} {P (i)}} \ leq \ log \ left (\ sum _ {i} P (i) {\ frac {Q (i)} {P (i)}} \ højre) = \ log \ sum _ {i} Q (i) = \ log (1) = 0 \!}

Med lighed er iff konstant næsten overalt . (på grund af den strenge konkavitet) I dette tilfælde kan konstanten kun være lig med 1, da de to funktioner P og Q er sandsynligheder. Derfor egenskaberne. Q(jeg)P(jeg){\ displaystyle {\ frac {Q (i)} {P (i)}}}

• Additivitet. Lad to adskillelige distributioner ogP12(x1,x2)=P1(x1).P2(x2){\ displaystyle P_ {12} (x_ {1}, x_ {2}) = P_ {1} (x_ {1}). P_ {2} (x_ {2})}Q12(x1,x2)=Q1(x1).Q2(x2){\ displaystyle Q_ {12} (x_ {1}, x_ {2}) = Q_ {1} (x_ {1}). Q_ {2} (x_ {2})}

D(P12‖Q12)=D(P1‖Q1)+D(P2‖Q2){\ displaystyle D (P_ {12} \ | Q_ {12}) = D (P_ {1} \ | Q_ {1}) + D (P_ {2} \ | Q_ {2})}

• I informationsgeometriformalismen udviklet af S. Amari er Kullback-Leibler-divergensen den divergens, der er forbundet med to grundlæggende dobbelte affineforbindelser : m-forbindelsen (blanding, additiv kombination af distributioner) og e-forbindelsen (eksponentiel, multiplikativ kombination af distributioner) . Kullback-Leibler-divergensen adlyder lokalt Fisher-metricen og svarer til integrationen af ​​afstanden mellem to punkter (fordelinger) langs en geodesik af typen e eller m (afhængigt af om man betragter en retning eller l 'anden: eller ).D(P‖Q){\ displaystyle D (P \ | Q)}D(Q‖P){\ displaystyle D (Q \ | P)}
• Den symmetriske afstand (induceret af Levi-Civita-forbindelsen , autoduale) forbundet med Fisher-metricen er Hellinger-afstanden DH(P‖Q)=2∑jeg(Pjeg-Qjeg)2.{\ displaystyle D_ {H} (P \ | Q) = 2 \ sum _ {i} \ left ({\ sqrt {P_ {i}}} - {\ sqrt {Q_ {i}}} \ right) ^ { 2}.}

Diskussion

Selvom den ofte opfattes som en afstand , opfylder den ikke betingelserne: den er ikke symmetrisk og respekterer ikke den trekantede ulighed.

Kullback-Leibler-afvigelsen falder ind i den større kategori af f- forskelle, der blev introduceret uafhængigt af Csiszár i 1967 og af Ali og Silvey i 1966. Ved at tilhøre denne familie respekterer den egenskaberne ved bevarelse af information: invarians, monotonicitet.

Supplerende er Kullback-Leibler-divergensen også en Bregman-divergens , der er forbundet med den potentielle funktion . Konsekvensen er, at denne divergens ved Legendre transformation af er forbundet med en dobbelt moment koordinatsystem for at repræsentere de fordelinger af den eksponentielle familie . ψ(x)=xlog⁡x-x{\ displaystyle \ psi (x) = x \ log xx}ψ{\ displaystyle \ psi}(x,log⁡x){\ displaystyle (x, \ log x)}

Noter og referencer

1. Kullback og Leibler 1951 .
2. Kullback 1959 .
3. S. Kullback , Informationsteori og statistik , John Wiley & Sons ,1959. Genudgivet af Dover Publications i 1968; genoptrykt i 1978: ( ISBN  0-8446-5625-9 ) .
4. Amari og Nagaoka 2000 .
5. Csiszár 1967 .
6. Ali og Silvey 1967 .
7. Amari 2010 .
8. Bregman 1967 .

Tillæg

Bibliografi

• [Ali og Silvey 1967] (da) MS Ali og D. Silvey, "  En generel klasse af koefficienter for divergens mellem fordeling fra en anden  " , Journal of the Royal Statistical Society , Ser. B , bind.  28,1967, s.  131-140.
• [Amari og Nagaoka 2000] (da) Sunichi Amari og Hiroshi Nagaoka , Metoder til informationsgeometri , bind.  191, American Mathematical Society,2000.
• [Amari 2010] (da) Sunichi Amari, "  Informationsgeometri i optimering, maskinindlæ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] (da) L. Bregman, "  Afslapningsmetoden til at finde det fælles punkt for konvekse sæt og dets anvendelse til løsning af problemer i konveks programmering  " , USSR Computational Mathematics and Mathematical Physics , bind.  7, n o  3,1967, s.  200–217 ( DOI  10.1016 / 0041-5553 (67) 90040-7 ).
• [Csiszár] (en) I. Csiszár, "  Informationstype målinger af forskel på sandsynlighedsfordelinger og indirekte observation  " , Studia Sci. Matematik. Hungar. , Vol.  2,1967, s.  229-318.
• [Kullback og Leibler 1951] (in) S. og R. Kullback Leibler, "  er information og tilstrækkelighed  " , Annals of Mathematical Statistics , Vol.  22,1951, s.  79-86.
• [Kullback 1959] (da) S. Kullback, Informationsteori og statistik , New York, John Wiley og Sons,1959.

Se også

• Afstand i total variation (sandsynligheder)
• Hellinger afstand
• Afstand fra Bhattacharyya

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">