Ztrátové funkce: co přesně model minimalizuje

Nechť 𝒳 je množina možných vstupů, 𝒴 množina možných skutečných hodnot (např. 𝒴 = ℝ u regrese, 𝒴 = {−1, +1} u dvou tříd) a 𝒵 množina možných předpovědí (např. ℝ). Ztrátová funkce je funkce

ℓ : 𝒴 × 𝒵 → [0, ∞),   (y, ŷ) ↦ ℓ(y, ŷ);

číslo ℓ(y, ŷ) je cena předpovědi ŷ ∈ 𝒵, když skutečná hodnota je y ∈ 𝒴.

Nechť dále n ∈ ℕ, n ≥ 1, (x₁, y₁), …, (x_n, y_n) ∈ 𝒳 × 𝒴 jsou trénovací data a f : 𝒳 → 𝒵 je model. Empirické riziko modelu f je číslo

R̂(f) = 1/n ∑_i=1ⁿ ℓ(y_i, f(x_i)),

tedy průměrná cena chyb modelu na trénovacích datech; učení hledá model (v praxi parametry θ modelu f_θ), pro který je R̂ co nejmenší.

Metrika je předpis M, který modelu f a (obvykle testovacím) datům přiřadí reálné číslo hodnotící kvalitu jeho předpovědí — např. přesnost, F1 nebo RMSE z dílu o vyhodnocení modelu. Metrika nemusí být průměrem ztráty přes body (F1 není) a obecně se od empirického rizika liší.

Nechť (X, Y) je náhodný vektor s hodnotami v 𝒳 × 𝒴 a s rozdělením P (z něj pocházejí trénovací i nová data), ℓ : 𝒴 × 𝒵 → [0, ∞) je ztrátová funkce a f : 𝒳 → 𝒵 model. Riziko modelu f je střední hodnota ztráty

R(f) = E_{(X, Y) ∼ P}[ ℓ(Y, f(X)) ]

(pokud existuje), tedy průměrná cena chyby na nových datech. Rozdělení P neznáme, proto ho nahradíme trénovacími daty a riziko průměrem — empirickým rizikem. Podle zákona velkých čísel se pro pevné f empirické riziko s rostoucím n blíží skutečnému; pro model vybraný právě podle trénovacích dat to už neplatí automaticky (přeučení).

Nechť y ∈ ℝ je skutečná hodnota, ŷ ∈ ℝ předpověď a r = y − ŷ ∈ ℝ reziduum. Regresní ztráty zapisujeme jako funkce rezidua ℝ → [0, ∞):

1. kvadratická ztráta: ℓ₂(r) = r²;
2. absolutní ztráta: ℓ₁(r) = |r|;
3. Huberova ztráta s parametrem δ > 0: H_δ(r) = ½r²   pro |r| ≤ δ,    H_δ(r) = δ(|r| − ½δ)   pro |r| > δ.

Huberova ztráta je tedy pro malá rezidua kvadratická, pro velká lineární a v bodech |r| = δ, kde se obě části potkávají, má spojitou derivaci (je hladká).

Nechť ℓ : ℝ → [0, ∞) je konvexní regresní ztráta zapsaná jako funkce rezidua r = y − f_θ(x). Číslo g ∈ ℝ je subgradient ℓ v bodě r₀, právě když ℓ(r) ≥ ℓ(r₀) + g · (r − r₀) pro všechna r ∈ ℝ; je-li ℓ v r₀ diferencovatelná, je jediným subgradientem ℓ′(r₀). Tah (funkce vlivu) ztráty ℓ je funkce ψ : ℝ → ℝ,

ψ(r) = ℓ′(r)   v bodech, kde ℓ má derivaci,

a v ostatních bodech je ψ(r) některý subgradient ℓ v r. Tah říká, jak silně a kterým směrem bod s reziduem r táhne za model. Pro naše tři ztráty:

1. kvadratická: ψ(r) = 2r;
2. absolutní: ψ(r) = sign r pro r ≠ 0 a ψ(0) ∈ [−1, 1] (subgradienty |r| v nule tvoří celý interval [−1, 1]);
3. Huberova: ψ(r) = r pro |r| ≤ δ a ψ(r) = δ · sign r pro |r| > δ.

Nechť n ∈ ℕ, n ≥ 1, a y₁, …, y_n ∈ ℝ. Označme ȳ = 1/n ∑_i=1ⁿ y_i jejich průměr. Číslo m ∈ ℝ je medián hodnot y₁, …, y_n, právě když

|{i : y_i < m}| ≤ n/2   ∧   |{i : y_i > m}| ≤ n/2,

tj. pod ani nad m neleží víc než polovina hodnot (pro liché n je medián jediný — prostřední hodnota; pro sudé n je mediánem každé číslo mezi dvěma prostředními hodnotami). Pak platí:

1. funkce Q(c) = ∑_i=1ⁿ (y_i − c)² nabývá na ℝ minima právě v bodě c = ȳ;
2. funkce A(c) = ∑_i=1ⁿ |y_i − c| nabývá na ℝ minima právě v mediánech.

Jediné číslo, které nejlépe zastupuje všechny hodnoty, je tedy pro kvadratickou ztrátu průměr a pro absolutní medián.

Důkaz. Obě funkce jsou konvexní, takže minimum je právě tam, kde je součet tahů nulový (nebo kde nulu obsahuje subgradient). Kvadratická: Q′(c) = −∑ 2(y_i − c) = 0 ⇔ c = 1/n ∑ y_i = ȳ. Absolutní: ∑ sign(y_i − c) = (počet bodů nad c) − (počet bodů pod c), a to je nula (nebo nulu obsahuje subgradient), právě když nad i pod c leží nejvýš polovina bodů — to je medián. ∎

Příklad. Pět měření 20, 21, 22, 24 a 33 °C, poslední vadné. Průměr je 120/5 = 24 °C, medián 22 °C. Huberova ztráta s δ = 2 dá c = 22⅓ °C: rezidua jsou −2⅓, −1⅓, −⅓, 1⅔ a 10⅔, tahy −2, −1⅓, −⅓, 1⅔ a 2 (u krajních bodů oříznuté na ±δ) a jejich součet je 0. Vadný bod odtáhl průměr o 2 °C nad medián, Huberovo řešení jen o třetinu stupně.

Vadné měření s reziduem r = 7 °C a dobré s r = 0,4 °C (zhruba velikost šumu):

U kvadratické ztráty táhne osm vadných měření zhruba tak silně jako 8 · 17,5 = 140 dobrých s typickou chybou — a dobrých je jen 52.

Nechť n ≥ 1 a Y₁, …, Y_n jsou nezávislé náhodné veličiny se stejným normálním rozdělením N(μ, σ²), kde μ ∈ ℝ a σ > 0 (měření μ s normálním šumem). Nechť Ȳ_n = 1/n ∑_i=1ⁿ Y_i je výběrový průměr a M_n výběrový medián. Pak

1. var Ȳ_n = σ²/n pro každé n;
2. pro n → ∞ je rozptyl mediánu přibližně var M_n ≈ πσ²/2n ≈ 1,57 · σ²/n (přesně: √n (M_n − μ) konverguje v distribuci k N(0, πσ²/2)).

Bod 2 je případ klasického asymptotického výsledku (viz např. A. W. van der Vaart, Asymptotic Statistics, 1998, kap. 21): má-li rozdělení hustotu φ spojitou a kladnou v mediánu m, je var M_n ≈ 1/4n φ(m)². Pro normální rozdělení je m = μ a φ(m) = 1/σ√2π, takže 1/4n φ(m)² = 2πσ²/4n = πσ²/2n. Medián tedy potřebuje o 57 % víc dat, aby byl stejně přesný jako průměr. Jakmile ale data obsahují odlehlé body, poměr se obrátí.

Nechť τ ∈ (0, 1) a r = y − ŷ ∈ ℝ je reziduum. Kvantilová (pinball) ztráta pro kvantil τ je funkce ρ_τ : ℝ → [0, ∞),

ρ_τ(r) = τ · r   pro r ≥ 0,    ρ_τ(r) = (τ − 1) · r   pro r < 0.

Nechť Y je náhodná veličina s distribuční funkcí F(y) = P(Y ≤ y). Její τ-kvantil je číslo

q_τ = min {y ∈ ℝ : F(y) ≥ τ},

tedy nejmenší hodnota, pod kterou (včetně ní) leží aspoň podíl τ případů. Je-li E|Y| < ∞, nabývá funkce c ↦ E[ρ_τ(Y − c)] minima v c = q_τ; se vstupem x jde o podmíněný kvantil rozdělení Y při X = x. Pro τ = ½ je ρ_½(r) = ½|r|, polovina absolutní ztráty, a optimem je medián.

Nechť τ ∈ (0, 1), n ≥ 1 a y₁, …, y_n ∈ ℝ. Pro c ∈ ℝ označme S(c) = ∑_i=1ⁿ ρ_τ(y_i − c). Pak S nabývá na ℝ minima právě v těch c, pro která

|{i : y_i < c}| ≤ τn ≤ |{i : y_i ≤ c}|,

a aspoň jedno takové c existuje (je jím ⌈τn⌉-tá nejmenší z hodnot). Takovým c se říká výběrový τ-kvantil: pod c leží nejvýš podíl τ hodnot a pod c včetně c aspoň podíl τ.

Důkaz. Posuneme-li c o malé ε > 0 nahoru, ztráta každého bodu nad c klesne o τε a každého bodu pod c (či na c) vzroste o (1 − τ)ε. Je-li takových bodů k z n, změní se součet o ε · [(1 − τ)k − τ(n − k)] = ε · (k − τn). Dokud k/n < τ, posun nahoru se vyplatí, jakmile k/n > τ, vyplatí se posun dolů. S je konvexní, minimum je tedy tam, kde k/n přejde přes τ — to je přesně podmínka výše. Pro τ = ½ je to medián. ∎

U přímky a + b · km dává stejný argument pro posun a stejnou podmínku: v optimu leží pod přímkou podíl τ trénovacích jízd (až na body ležící přesně na ní). Rozpětí mezi 10% a 90% přímkou proto slibuje 90 − 10 = 80 % jízd.

Nechť f : 𝒳 → ℝ je model, který příkladu x ∈ 𝒳 přiřadí skóre z = f(x) a předpovídá třídu sign z, a nechť y ∈ {−1, +1} je skutečná třída příkladu x. Marže příkladu je číslo

m = y · z ∈ ℝ.

Platí m > 0, právě když sign z = y (příklad je zařazený správně), a čím je m větší, tím dál od hranice z = 0 na správné straně příklad leží. Klasifikační ztráty zapisujeme jako funkce marže ℝ → [0, ∞):

1. 0–1: ℓ₀₁(m) = 1 pro m ≤ 0 a ℓ₀₁(m) = 0 pro m > 0 (počet chyb — to, co chceme, ale nedá se učit);
2. logistická (křížová entropie): ℓ_log(m) = log₂(1 + e^−m);
3. hinge: ℓ_hinge(m) = max(0, 1 − m);
4. exponenciální: ℓ_exp(m) = e^−m.

Ztráty 2–4 se nazývají náhradní: jsou konvexní a pro každé m ∈ ℝ platí ℓ(m) ≥ ℓ₀₁(m), tj. 0–1 ztrátu shora omezují (důkaz ve větě níže).

Nechť x ∈ 𝒳, y ∈ {−1, +1}, z = f(x) ∈ ℝ a m = yz. Nechť model (logistická regrese) předpovídá pravděpodobnost

P(y = +1 | x) = σ(z) = 1/1 + e^−z,   P(y = −1 | x) = 1 − σ(z).

Pak platí:

1. křížová entropie této předpovědi (v bitech) je rovna ℓ_log(m);
2. pro ℓ ∈ {ℓ_log, ℓ_hinge, ℓ_exp} a každé m ∈ ℝ je ℓ(m) ≥ ℓ₀₁(m); proto pro data (x₁, y₁), …, (x_n, y_n) je podíl chyb 1/n ∑_i ℓ₀₁(y_if(x_i)) nejvýš roven průměrné náhradní ztrátě 1/n ∑_i ℓ(y_if(x_i)).

Důkaz. 1. Křížová entropie (v bitech) pro y = +1 je −log₂ σ(z) = log₂(1 + e^−z) a pro y = −1 je −log₂(1 − σ(z)) = −log₂ σ(−z) = log₂(1 + e^z). V obou případech je to log₂(1 + e^−yz) = ℓ_log(m).

2. Pro m ≤ 0 je e^−m ≥ 1, takže logistická ztráta ≥ log₂ 2 = 1, exponenciální ≥ 1 a hinge 1 − m ≥ 1 = ℓ₀₁(m); pro m > 0 je 0–1 ztráta nulová a všechny tři jsou nezáporné. Nerovnost platí v každém bodě, a tedy i pro průměry. ∎

Například logistická ztráta pro m = −2 (barvy podle vzorce výše): ℓ_log(−2) = log₂(1 + e²) ≈ log₂(1 + 7,389) = log₂ 8,389 ≈ 3,07; pro m = 1: ℓ_log(1) = log₂(1 + e⁻¹) ≈ log₂(1 + 0,368) ≈ 0,45.

Nechť (X, Y) je náhodný vektor s hodnotami v 𝒳 × 𝒴, ℓ : 𝒴 × 𝒵 → [0, ∞) ztrátová funkce a předpokládejme, že model může být libovolná (měřitelná) funkce f : 𝒳 → 𝒵 („má dost volnosti“). Nechť pro každé x ∈ 𝒳 existuje

f*(x) = argmin_{c ∈ 𝒵} E[ ℓ(Y, c) | X = x ].

Pak R(f*) ≤ R(f) pro každý model f — riziko se minimalizuje v každém bodě x zvlášť, protože R(f) = E[ E[ℓ(Y, f(X)) | X] ]. Podle vět výše (a jejich verzí pro rozdělení místo konečného výběru) tak vychází:

Pro logistickou ztrátu: při daném x minimalizujeme p · log₂(1 + e^−z) + (1 − p) · log₂(1 + e^z); derivace podle z je úměrná −p(1 − σ(z)) + (1 − p)σ(z) = σ(z) − p, takže σ(z*) = p. Proto z logistické regrese pravděpodobnost dostaneme a ze SVM ne.