Křížová entropie

Křížová entropie mezi dvěma rozděleními pravděpodobnosti p a q se stejnou podkladovou množinou událostí míry je v teorii informace průměrný počet bitů potřebných pro identifikaci události vybrané z množiny, jestliže kódovací schéma používané pro množinu je optimalizované pro odhadnuté rozdělení pravděpodobnosti q místo skutečného rozdělení p.

Definice

Křížová entropie rozdělení q vůči rozdělení p na dané množině je definovaná takto:

:H(p, q) = -\operatorname{E}_p[\log q].

Jiná definice používá Kullbackovu-Leiblerovu divergenci D_{\mathrm{KL}}(p \| q) rozdělení p z q (neboli relativní entropie rozdělení q vzhledem k p):

:H(p, q) = H(p) + D_{\mathrm{KL}}(p \| q),

kde H(p) je entropie rozdělení p.

Pro diskrétní pravděpodobnostní distribuce p a q se stejným nosičem \mathcal{X} to znamená

:H(p,q) = -\sum_{x\in\mathcal{X}} p(x)\, \log q(x) (rovnice 1)

Pro spojité distribuce je situace analogická. Musíme předpokládat, že p a q jsou absolutně spojité vzhledem k nějaké referenční míře r (obvykle je r Lebesgueova míra na Borelovské σ-algebře). +more Nechť P a Q jsou hustoty pravděpodobností rozdělení p a q vzhledem k r. Pak.

:-\int_\mathcal{X} P(x)\, \log Q(x)\, dr(x) = \operatorname{E}_p[-\log Q]

a tedy

:H(p,q) = -\int_\mathcal{X} P(x)\, \log Q(x)\, dr(x) (rovnice 2)

Poznámka: Notace H(p,q) se používá také pro jinou veličinu, sdruženou entropii rozdělení p a q.

Motivace

Kraftova-McMillanova věta v teorii informace říká, že jakékoli přímo dekódovatelné kódovací schéma pro kódování zprávy identifikující jednu hodnotu x_i ze sady možností \{x_1,. ,x_n\} můžeme považovat za reprezentaci implicitního rozdělení pravděpodobnosti q(x_i) = \left(\frac{1}{2}\right)^{l_i} pro \{x_1,. +more,x_n\}, kde l_i je délka kódu pro x_i v bitech. Proto lze křížovou entropii interpretovat jako očekávanou délku zprávy pro zakódování jedné položky, když předpokládáme nějaké rozdělení q, zatímco data mají ve skutečnosti rozdělení p. To znamená, že očekávané hodnoty se berou ze skutečného rozdělení pravděpodobnosti p místo z q. Očekávaná délka zprávy při skutečném rozdělení p je.

: \operatorname{E}_p[l] = - \operatorname{E}_p\left[\frac{\ln{q(x)}}{\ln(2)}\right] = - \operatorname{E}_p\left[\log_2 {q(x)}\right] = - \sum_{x_i} p(x_i)\, \log_2 {q(x_i)} = -\sum_x p(x)\, \log_2 q(x) = H(p, q)

Odhad

Je mnoho situací, kdy by bylo třeba měřit křížovou entropii, ale rozdělení p je neznámé. Příkladem je jazykové modelování, kde model je vytvořen na trénovací množině T a jeho křížová entropie je pak měřena na testovací množině pro zhodnocení, jak je model přesný v predikci testovacích dat. +more V tomto příkladě je p skutečné rozdělení slov v nějakém korpusu a q je rozdělení slov predikované modelem. Protože skutečné rozdělení je neznámé, nelze křížovou entropii přímo spočítat. V takovém případě se odhad křížové entropie počítá pomocí vzorce:.

:H(T,q) = -\sum_{i=1}^N \frac{1}{N} \log_2 q(x_i)

kde N je velikost testovací množiny a q(x) je pravděpodobnost události x odhadnuté z trénovací množiny. Suma se počítá přes N. +more Toto je pravděpodobnostní (Monte Carlo) odhad skutečné křížové entropie, při kterém testovací množinu považujeme za vzorek z p(x).

Vztah k logaritmické věrohodnosti

U klasifikačních problémů chceme odhadnout pravděpodobnost jednotlivých výsledků. Pokud odhadnutá pravděpodobnost výsledku i je q_i, zatímco frekvence (empirická pravděpodobnost) výsledku i v trénovací množině je p_i a v trénovací množině je N vzorků, pak věrohodnost trénovací množiny je

:\prod_i q_i^{N p_i}

a logaritmická věrohodnost vydělená N je

:\frac{1}{N} \log \prod_i q_i^{N p_i} = \sum_i p_i \log q_i = -H(p, q)

takže maximalizace věrohodnosti je totéž jako minimalizace křížové entropie.

Minimalizace křížové entropie

Minimalizace křížové entropie se často používá při optimalizaci a odhadu pravděpodobnosti řídkých událostí; viz metoda křížové entropie.

Při porovnávání rozdělení q s pevným referenčním rozdělením p jsou křížová entropie a KL divergence identické až na aditivní konstantu (protože p je pevné): obě nabývají pro p = q své minimální hodnoty, která je 0 pro KL divergenci a \mathrm{H}(p) pro křížovou entropii. V inženýrské literatuře se postup minimalizace KL divergence (Kullbackův "Princip minimální diskriminace informace") často nazývá Princip minimální křížové entropie (MCE, z anglického ) nebo Minxent.

Jak je však diskutováno v článku Kullbackova-Leiblerova divergence, někdy je rozdělení q fixováno před referenčním rozdělením a rozdělení p je optimalizováno, aby bylo co nejbližší k q, při platnosti určitých omezení. V takovém případě obě minimalizace nejsou ekvivalentní. +more To vedlo k určité nejednoznačnosti v literatuře, protože někteří autoři usilovali vyřešit nekonzistenci tím, že termínem křížová entropie označují D_{\mathrm{KL}}(p \| q) místo H(p, q).

Nákladová funkce křížové entropie a logistická regrese

Křížovou entropii lze použít pro definování nákladové funkce při strojovém učení a optimalizaci. Skutečná pravděpodobnost p_i je skutečný popisek a dané rozdělení q_i je predikovanou hodnotou současného modelu.

Konkrétněji uvažujme logistickou regresi, kterou lze (mimo jiné) použít pro klasifikaci pozorování do dvou možných tříd (často značených 0 a 1). Výstup modelu pro určité pozorování dané vektorem vstupních vlastností x lze interpretovat jako pravděpodobnost, což slouží jako základ pro klasifikaci pozorování. +more Pravděpodobnost je znázorněna pomocí logistické funkce g(z)=1/(1+e^{-z}) kde z je nějaká funkce vstupního vektoru x, obvykle pouze lineární funkce. Pravděpodobnost výstupu y=1 je : q_{y=1}\ =\ \hat{y}\ \equiv\ g(\mathbf{w}\cdot\mathbf{x})\ = 1/(1+e^{-\mathbf{w}\cdot\mathbf{x}}), kde vektor vah \mathbf{w} je optimalizován pomocí nějakého vhodného algoritmu, jako například metodou gradientního spádu. Podobně komplementární pravděpodobnost hledání výstup y=0 je : q_{y=0}\ =\ 1-\hat{y}.

Při použití notace p\in\{y,1-y\} a q\in\{\hat{y},1-\hat{y}\} můžeme používat křížovou entropii pro získání míry odlišnosti mezi p a q: : H(p,q)\ =\ -\sum_ip_i\log q_i\ =\ -y\log\hat{y} - (1-y)\log(1-\hat{y})

Typická nákladová funkce, kterou používáme v logistické regresi, se počítá jako průměr všech křížových entropií ve vzorku. Pokud například máme N vzorků indexovaných n=1,\dots,N, bude nákladová funkce

: \begin{align} J(\mathbf{w})\ &=\ \frac1N\sum_{n=1}^N H(p_n,q_n)\ =\ -\frac1N\sum_{n=1}^N\ \bigg[y_n \log \hat y_n + (1 - y_n) \log (1 - \hat y_n)\bigg]\, \end{align}

kde \hat{y}_n\equiv g(\mathbf{w}\cdot\mathbf{x}_n) = 1/(1+e^{-\mathbf{w}\cdot\mathbf{x}_n}) a g(z) je logistická funkce stejně jako výše.

Logistická ztráta se někdy nazývá ztráta křížové entropie nebo logaritmická ztráta (V tomto případě se třídy zpravidla označují hodnotami {-1,+1}).

Odkazy

Reference

Související články

Metoda křížové entropie * Logistická regrese * Podmíněná entropie * Metoda maximální věrohodnosti * Vzájemná informace

Externí odkazy

[url=http://www.cse.unsw.edu.au/~billw/cs9444/crossentropy.html]What is cross-entropy, and why use it?[/url] * [url=http://heliosphan.org/cross-entropy.html]Cross Entropy[/url]

Kategorie:Entropie a informace Kategorie:Nákladové funkce Kategorie:Kříže ve vědě a technice