Oblast důvěry: říct to nahlas

Tohle je statická kopie kapitoly pro vyhledávače. Interaktivní verze má animované obrázky, kontrolní otázky a tlačítka, která příklad načtou do kalkulačky.

Levenberg-Marquardt vyjadřuje důvěru v model nepřímo, hodnotou μ. Kolik to je v milimetrech kroku, se z μ na první pohled nepozná. Metoda oblasti důvěry to řekne rovnou:

min m(h) za podmínky ‖h‖ ≤ ΔΔ je poloměr, ve kterém modelu věříme

Powellův „dog leg" je chytrá a levná náhrada přesného řešení téhle úlohy. Má k dispozici dva body: Gauss-Newtonův krok a Cauchyho bod, což je nejnižší místo podél nejstrmějšího spádu:

α = ‖g‖² / ‖Jg‖², a = −α gCauchyho bod — minimum modelu podél spádu

A pak tři možnosti, podle toho, jak velké Δ je:

situace	krok
Gauss-Newton se vejde do Δ	vezmi ho celý
ani Cauchyho bod se nevejde	ořízni spád na délku Δ
mezi tím	jdi z Cauchyho bodu k GN, dokud nenarazíš na hranici

Z tohoto počátečního Δ: 24 kroků, skončil v minimu
z toho větví: Gauss-Newton 3 · spád 0 · psí noha 21
Poloměr není nastavení, které by se ladilo — algoritmus si ho po každém kroku sám zvětší nebo zmenší podle toho, jak dobře model předpověděl skutečný pokles.

Táhni poloměrem. Kroužek je oblast důvěry, tečkovaná lomená čára je „psí noha", zelená šipka je vybraný krok.

Ta třetí větev je ta, po které se metoda jmenuje — lomená dráha z golfu. Hledá se β tak, aby délka kroku byla přesně Δ, a to vede na kvadratickou rovnici. Řešit se musí opatrně, protože jeden z tvarů vzorce se pro malé Δ numericky ruší:

β = (Δ² − ‖a‖²) / ( c + √(c² + ‖b−a‖²(Δ² − ‖a‖²)) ), c = aᵀ(b−a) > 0tvar bez odečítání blízkých čísel

Jak se Δ mění

Stejným poměrem zisku jako u LM, jen se řídí poloměr místo tlumení:

ϱ > 0,75: Δ ← max{Δ, 3‖h‖}model byl dobrý — věř mu víc

ϱ < 0,25: Δ ← Δ/2model byl špatný — věř mu míň

Poloměr není parametr k ladění. Zadá se počáteční hodnota a algoritmus si ho dál řídí sám podle toho, jak se model osvědčuje. Kdo Δ ladí ručně, dělá práci, kterou má dělat metoda.

Který si tedy vybrat

V praxi jsou obě metody srovnatelné a obě jsou spolehlivé. Levenberg-Marquardt je rozšířenější a je to ten, který má KineLab a VisionLab pod kapotou. Dog-leg se lépe vysvětluje a lépe se z něj vychází k pokročilejším metodám, protože „poloměr, ve kterém věřím modelu" je pojem, který má smysl i mimo nejmenší čtverce.