Nejmenší absolutní odchylky (LAD), také známé jako Nejmenší absolutní chyby (LAE), Nejmenší absolutní hodnota (LAV) nebo L1 normový problém, je matematická optimalizační technika podobná populární technice nejmenších čtverců, která se pokouší najít funkci, která přibližuje soubor dat. V jednoduchém případě množiny (x,y) dat je aproximační funkce jednoduchá „trendová čára“ ve dvourozměrných karteziánských souřadnicích. Metoda minimalizuje součet absolutních chyb (SAE) (součet absolutních hodnot svislých „zbytků“ mezi body generovanými funkcí a odpovídajícími body v datech). Odhad nejmenších absolutních odchylek také vzniká jako odhad maximální pravděpodobnosti, pokud chyby mají Laplaceovo rozdělení.
Formulace problému
Předpokládejme, že soubor dat se skládá z bodů (xi, yi) s i = 1, 2, …, n. Chceme najít funkci f taková, že
Abychom tohoto cíle dosáhli, předpokládáme, že funkce f je určité formy obsahující některé parametry, které je třeba určit. Například nejjednodušší forma by byla lineární: f(x) = bx + c, kde b a c parametry, jejichž hodnoty nejsou známy, ale které bychom chtěli odhadnout. Méně jednoduše, předpokládejme, že f(x) je kvadratická, což znamená, že f(x) = ax2 + bx + c, kde a, b a c ještě nejsou známy. (Obecněji, mohlo by existovat nejen jedno vysvětlení x, ale spíše více vysvětlení, všechna by se jevila jako argumenty funkce f.)
Nyní hledáme odhadované hodnoty neznámých parametrů, které minimalizují součet absolutních hodnot reziduí:
Kontrast nejmenších čtverců s nejmenšími absolutními odchylkami
Následující tabulka kontrastuje některé vlastnosti metody nejmenších absolutních odchylek s těmi z metody nejmenších čtverců (pro non-singulární problémy).
Metoda nejmenších absolutních odchylek nachází uplatnění v mnoha oblastech díky své robustnosti ve srovnání s metodou nejmenších čtverců. Nejmenší absolutní odchylky jsou robustní v tom, že jsou odolné vůči odlehlým hodnotám v datech. To může být užitečné ve studiích, kde odlehlé hodnoty mohou být bezpečně a efektivně ignorovány. Pokud je důležité věnovat pozornost jakýmkoli odlehlým hodnotám, je metoda nejmenších čtverců lepší volbou.
Vlastnost nestability metody nejmenších absolutních odchylek znamená, že při malé vodorovné úpravě datumu může regresní přímka přeskočit velké množství. Metoda má spojitá řešení pro některé datové konfigurace; nicméně při posunutí datumu o malé množství by se dalo „přeskočit“ konfiguraci, která má více řešení, která pokrývají oblast. Po průchodu touto oblastí řešení má přímka nejmenších absolutních odchylek sklon, který se může značně lišit od sklonu předchozí přímky. Naproti tomu řešení nejmenších čtverců je stabilní v tom, že při každé malé úpravě datového bodu se regresní přímka bude pohybovat vždy jen mírně; to znamená, že regresní parametry jsou spojité funkce dat.
A konečně, pro daný datový soubor může metoda nejmenších absolutních odchylek přinést více řešení, zatímco metoda nejmenších čtverců vždy přinese pouze jedno řešení (regresní přímka je jedinečná).
Existují i jiné unikátní vlastnosti přímky nejmenších absolutních odchylek. V případě množiny (x,y) dat bude přímka nejmenších absolutních odchylek procházet vždy alespoň dvěma datovými body, pokud neexistuje více řešení. Pokud existuje více řešení, pak oblast platných řešení nejmenších absolutních odchylek bude ohraničena alespoň dvěma přímkami, z nichž každá projde alespoň dvěma datovými body. Obecněji řečeno, pokud existuje k regresorů (včetně konstanty), pak alespoň jedna optimální regresní plocha projde k datových bodů.:s.936
Toto „přichycení“ linky k datovým bodům může pomoci pochopit vlastnost „nestabilita“: pokud se linka vždy přichytí k alespoň dvěma bodům, pak bude linka skákat mezi různými množinami bodů při změně datových bodů. „Přichycení“ také pomáhá pochopit vlastnost „robustnost“: pokud existuje odlehlá hodnota a linie nejmenších absolutních odchylek se musí přichytit ke dvěma datovým bodům, odlehlá hodnota s největší pravděpodobností nebude jedním z těchto dvou bodů, protože to ve většině případů nebude minimalizovat součet absolutních odchylek.
Jedním známým případem, kdy existuje více řešení, je množina bodů symetrických k vodorovné přímce, jak je znázorněno na obrázku A níže.
Obrázek A: Sada datových bodů s reflexní symetrií a několika řešeními nejmenších absolutních odchylek. „Oblast řešení“ je zobrazena zeleně. Svislé modré čáry představují absolutní chyby od růžové čáry ke každému datovému bodu. Růžová čára je jedním z nekonečně mnoha řešení v rámci zelené plochy.
Abychom pochopili, proč existuje více řešení v případě uvedeném na obrázku A, zamysleme se nad růžovou přímkou v zelené oblasti. Její součet absolutních chyb je nějaká hodnota S. Pokud bychom přímku mírně naklonili nahoru a přitom ji stále drželi v zelené oblasti, součet chyb by byl stále S. Nezměnilo by se to, protože vzdálenost od každého bodu k přímce roste na jedné straně přímky, zatímco vzdálenost ke každému bodu na opačné straně přímky se zmenšuje přesně o stejnou hodnotu. Součet absolutních chyb tedy zůstává stejný. Protože lze přímku naklánět v nekonečně malých krocích, ukazuje to také, že pokud existuje více než jedno řešení, existuje nekonečně mnoho řešení.
Variace, rozšíření, specializace
Problém nejmenší absolutní odchylky může být rozšířen o omezení a regularizaci, např. lineární model s lineárními omezeními:
Regularizaci s LASSO lze také kombinovat s LAD.
I když je myšlenka regrese nejmenších absolutních odchylek stejně přímočará jako u regrese nejmenších čtverců, přímka nejmenších absolutních odchylek není tak jednoduchá na efektivní výpočet. Na rozdíl od regrese nejmenších čtverců nemá regrese nejmenších absolutních odchylek analytickou metodu řešení. Proto je nutný iterační přístup. Následuje výčet některých metod řešení nejmenších absolutních odchylek.
Metody založené na Simplexu jsou „preferovaným“ způsobem řešení problému nejmenších absolutních odchylek. Metoda Simplex je metoda pro řešení problému v lineárním programování. Nejoblíbenějším algoritmem je Barrodale-Robertsův modifikovaný Simplexův algoritmus. Algoritmy pro IRLS, Wesolowského metodu a Liho metodu lze najít v Příloze A tohoto dokumentu,
mezi jinými metodami. Kontrola všech kombinací čar procházejících libovolné dva (x,y) datové body je další metodou hledání nejmenší absolutní odchylky přímky. Protože je známo, že alespoň jedna absolutní odchylka přímky prochází alespoň dvěma datovými body, tato metoda najde přímku porovnáním SAE každé přímky a výběrem přímky s nejmenším SAE. Navíc, pokud má více přímek stejné, nejmenší SAE, pak přímky nastiňují oblast více řešení. I když je tato metoda jednoduchá, je neefektivní pro velké soubory dat.
Řešení pomocí lineárního programování
Problém může být vyřešen libovolnou technikou lineárního programování podle následující specifikace problému. Přejeme si
s ohledem na volbu hodnot parametrů , kde yi je hodnota ith pozorování závislé proměnné, a xij je hodnota ith pozorování jth nezávislé proměnné (j = 1,…,k). Přepíšeme tento problém z hlediska umělých proměnných ui jako
Tato omezení mají za následek, že každé z nich je po minimalizaci rovno, takže objektivní funkce je ekvivalentní původní objektivní funkci. Protože tato verze problémového příkazu neobsahuje operátor absolutní hodnoty, je ve formátu, který lze vyřešit libovolným lineárním programovacím balíčkem.