Απόκλιση Kullback–Leibler

Στην θεωρία πληροφορίας, η απόκλιση Kullback-Leibler (KL) (ή σχετική εντροπία) μεταξύ δύο κατανομών πιθανότητας $p$ και $q$ ορίζεται ως

$D_{\mathrm {KL} }(p\Vert q):=\operatorname {E} _{X\sim p}[-\log q(x)+\log p(X)].$

Για διακριτές τυχαίες μεταβλητές με πεδίο ορισμού ${\mathcal {X}}$, αυτή η ποσότητα είναι ίση με

$D_{\mathrm {KL} }(p\Vert q)=\sum _{x\in {\mathcal {X}}}p(x)\log \left({\frac {p(x)}{q(x)}}\right),$

και για συνεχείς τυχαίες μεταβλητές είναι ίση με

$D_{\mathrm {KL} }(p\Vert q)=\int _{x\in {\mathcal {X}}}p(x)\log \left({\frac {p(x)}{q(x)}}\right)\,\mathrm {d} x.$

Η ποσότητα αυτή μπορεί να ερμηνευτεί ως η αναμενόμενη τιμή της έξτρα πληροφορίας που χρειάζεται για να κωδικοποιήσουμε την τυχαία μεταβλητή $X$ με κατανομή $p$ υποθέτοντας ότι στην πραγματικότητα έχει κατανομή $q$.

Η συνάρτηση είναι απόκλιση και όχι μετρική απόσταση καθώς δεν ικανοποιεί την τριγωνική ανισότητα ούτε είναι συμμετρική.

Παράδειγμα

Οι κατανομές πιθανότητας $p$ και $q$.

Για τις κατανομές $p={\big (}{\tfrac {1}{3}},{\tfrac {1}{3}},{\tfrac {1}{3}}{\big )}$ και $q=(0.2,0.5,0.3)$, η απόκλιση KL δίνεται από

${\begin{aligned}D_{\mathrm {KL} }(p\Vert q)&=p_{1}\log _{2}(p_{1}/q_{1})+p_{2}\log _{2}(p_{2}/q_{2})+p_{3}\log _{2}(p_{3}/q_{3})\\&={\frac {1}{3}}\cdot \log _{2}\left({\frac {1/3}{0.2}}\right)+{\frac {1}{3}}\cdot \log _{2}\left({\frac {1/3}{0.5}}\right)+{\frac {1}{3}}\cdot \log _{2}\left({\frac {1/3}{0.3}}\right)\\&\approx 0.1013,\end{aligned}}$

και

${\begin{aligned}D_{\mathrm {KL} }(p\Vert q)&=q_{1}\log _{2}(q_{1}/p_{1})+q_{2}\log _{2}(q_{2}/p_{2})+q_{3}\log _{2}(q_{3}/p_{3})\\&=0.2\cdot \log _{2}\left({\frac {0.2}{1/3}}\right)+0.5\cdot \log _{2}\left({\frac {0.5}{1/3}}\right)+0.3\cdot \log _{2}\left({\frac {0.3}{1/3}}\right)\\&\approx 0.0994.\end{aligned}}$

Από αυτό το παράδειγμα φαίνεται ότι η απόκλιση δεν είναι συμμετρική.

Ιδιότητες

• (Μη-μηδενικότητα) Για οποιεσδήποτε δύο κατανομές $p$ και $q$, ισχύει ότι

$D_{\mathrm {KL} }(p\Vert q)\geq 0.$

Απόδειξη  

Από την ανισότητα λογαρίθμου-αθροίσματος έχουμε ότι

$D_{\mathrm {KL} }(p\Vert q)=\sum _{x\in {\mathcal {X}}}p(x)\log \left({\frac {p(x)}{q(x)}}\right)\geq \left(\sum _{x\in {\mathcal {X}}}p(x)\right)\log \left({\frac {\sum _{x\in {\mathcal {X}}}p(x)}{\sum _{x\in {\mathcal {X}}}q(x)}}\right)=1\cdot \log \left({\frac {1}{1}}\right)=0.$

• (Κυρτότητα) Η απόκλιση Kullback-Leibler είναι κυρτή συνάρτηση στα ζεύγη των κατανομών $(p,q)$, δηλαδή για κάθε ζεύγη κατανομών $(p_{1},q_{1})$ και $(p_{2},q_{2})$ και για κάθε πραγματικό αριθμό $0<\lambda <1$, ισχύει ότι

$D_{\mathrm {KL} }(\lambda \cdot p_{1}+(1-\lambda )\cdot p_{2}\Vert \lambda \cdot q_{1}+(1-\lambda )\cdot q_{2})\leq \lambda \cdot D_{\mathrm {KL} }(p_{1}\Vert q_{1})+(1-\lambda )\cdot D_{\mathrm {KL} }(p_{2}\Vert q_{2}).$

• (Ανεξάρτητες μεταβλητές) Η απόκλιση Kullback-Leibler είναι αθροιστική για τις ανεξάρτητες τυχαίες μεταβλητές $X$ και $Y$, δηλαδή με $p_{(X,Y)}(x,y)=p_{1}(x)p_{2}(y)$ και $q_{(X,Y)}(x,y)=q_{1}(x)q_{2}(y)$,

$D_{\mathrm {KL} }(p\Vert q)=D_{\mathrm {KL} }(p_{1}\Vert q_{1})+D_{\mathrm {KL} }(p_{2}\Vert q_{2}).$

Απόδειξη  

Ξεκινώντας από τον ορισμό για την απόκλιση $D_{\mathrm {KL} }(p\Vert q)$,

${\begin{aligned}D_{\mathrm {KL} }(p\Vert q)&=\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{(X,Y)}(x,y)\log _{2}\left({\frac {p_{(X,Y)}(x,y)}{q_{(X,Y)}(x,y)}}\right)\\&=\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{(X,Y)}(x,y)\log _{2}p_{(X,Y)}(x,y)-\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{(X,Y)}(x,y)\log _{2}q_{(X,Y)}(x,y)\\&=\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{1}(x)p_{2}(y)\log _{2}(p_{1}(x)p_{2}(y))-\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{1}(x)p_{2}(y)\log _{2}(q_{1}(x)q_{2}(y))\\&=\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{1}(x)p_{2}(y)\log _{2}p_{1}(x)+\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{1}(x)p_{2}(y)\log _{2}p_{2}(y)\\&\qquad \qquad -\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{1}(x)p_{2}(y)\log _{2}q_{1}(x)-\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p_{1}(x)p_{2}(y)\log _{2}q_{2}(y)\\&=\sum _{x\in {\mathcal {X}}}p_{1}(x)\log _{2}p_{1}(x)\left(\sum _{y\in {\mathcal {Y}}}p_{2}(y)\right)+\sum _{y\in {\mathcal {Y}}}p_{2}(y)\log _{2}p_{2}(y)\left(\sum _{x\in {\mathcal {X}}}p_{2}(x)\right)\\&\qquad \qquad -\sum _{x\in {\mathcal {X}}}p_{1}(x)\log _{2}q_{1}(x)\left(\sum _{y\in {\mathcal {Y}}}q_{2}(y)\right)-\sum _{y\in {\mathcal {Y}}}q_{1}(y)\log _{2}q_{2}(y)\left(\sum _{x\in {\mathcal {X}}}q_{2}(x)\right)\\&=\sum _{x\in {\mathcal {X}}}p_{1}(x)\log _{2}\left({\frac {p_{1}(x)}{p_{2}(x)}}\right)-\sum _{x\in {\mathcal {X}}}q_{1}(x)\log _{2}\left({\frac {q_{1}(x)}{q_{2}(x)}}\right)\\&=D_{\mathrm {KL} }(p_{1}\Vert q_{1})+D_{\mathrm {KL} }(p_{2}\Vert q_{2}).\end{aligned}}$

Δείτε επίσης

• Εντροπία πληροφοριών
• Ανισότητα Γκιμπς
• Ανισότητα Γένσεν