Lineární klasifikátor - Linear classifier
V oblasti strojové učení cíl statistická klasifikace je použít vlastnosti objektu k identifikaci, do které třídy (nebo skupiny) patří. A lineární klasifikátor toho dosáhne rozhodnutím o klasifikaci na základě hodnoty a lineární kombinace charakteristik. Vlastnosti objektu jsou také známé jako hodnoty funkcí a jsou typicky prezentovány stroji ve vektoru zvaném a vektor funkcí. Takové klasifikátory fungují dobře pro praktické problémy, jako je klasifikace dokumentů a obecněji pro problémy s mnoha proměnnými (funkce ), dosahující úrovně přesnosti srovnatelné s nelineárními klasifikátory, přičemž trénink a používání trvá méně času.[1]
Definice

Pokud je vektorem vstupního prvku do klasifikátoru a nemovitý vektor , pak je výstupní skóre
kde je skutečný vektor vah a F je funkce, která převádí Tečkovaný produkt dvou vektorů do požadovaného výstupu. (Jinými slovy, je jeden formulář nebo lineární funkční mapování na R.) Váhový vektor se učí ze sady označených tréninkových vzorků. Často F je prahová funkce, který mapuje všechny hodnoty nad určitou prahovou hodnotu do první třídy a všechny ostatní hodnoty do druhé třídy; např.,
Složitější F může dát pravděpodobnost, že položka patří do určité třídy.
U problému s klasifikací dvou tříd lze vizualizovat provoz lineárního klasifikátoru jako rozdělení vysoce dimenzionální vstupní prostor s a nadrovina: všechny body na jedné straně nadroviny jsou klasifikovány jako „ano“, zatímco ostatní jsou klasifikovány jako „ne“.
Lineární klasifikátor se často používá v situacích, kdy je problém s rychlostí klasifikace, protože je často nejrychlejším klasifikátorem, zvláště když je řídký. Lineární klasifikátory také často fungují velmi dobře, když je počet dimenzí v je velký, jako v klasifikace dokumentů, kde každý prvek v je obvykle počet výskytů slova v dokumentu (viz matice pojmu dokument ). V takových případech by měl být klasifikátor dobřelegalizovaný.
Generativní modely vs. diskriminační modely
Existují dvě široké třídy metod pro určování parametrů lineárního klasifikátoru . Oni mohou být generativní a diskriminační modely.[2][3] Metody modelu první třídy funkce podmíněné hustoty . Mezi příklady takových algoritmů patří:
- Lineární diskriminační analýza (LDA) - kostýmy Gaussian modely podmíněné hustoty
- Naivní Bayesův klasifikátor s multinomiálními nebo vícerozměrnými modely událostí Bernoulli.
Druhá sada metod zahrnuje diskriminační modely, které se snaží maximalizovat kvalitu výstupu na a tréninková sada. Další pojmy ve funkci nákladů na školení lze snadno provést regulace finálního modelu. Mezi příklady diskriminačního tréninku lineárních klasifikátorů patří:
- Logistická regrese —Maximální odhad pravděpodobnosti za předpokladu, že pozorovaná tréninková množina byla vygenerována binomickým modelem, který závisí na výstupu klasifikátoru.
- Perceptron —Algoritmus, který se pokouší opravit všechny chyby, které se vyskytly v tréninkové sadě
- Fisherova lineární diskriminační analýza - algoritmus (odlišný od „LDA“), který bez dalších předpokladů maximalizuje poměr rozptylu mezi třídami a rozptylu ve třídě. Je to v podstatě metoda redukce dimenze pro binární klasifikaci. [4]
- Podporujte vektorový stroj —Algoritmus, který maximalizuje okraj mezi rozhodovací nadrovinou a příklady ve výcvikové sadě.
Poznámka: Přes své jméno LDA v této taxonomii nepatří do třídy diskriminačních modelů. Jeho název však dává smysl, když porovnáváme LDA s druhou hlavní lineární snížení rozměrů algoritmus: analýza hlavních komponent (PCA). LDA je a učení pod dohledem algoritmus, který využívá popisky dat, zatímco PCA je neřízené učení algoritmus, který ignoruje štítky. Abychom to shrnuli, název je historický artefakt.[5]:117
Diskriminační trénink často přináší vyšší přesnost než modelování funkcí podmíněné hustoty[Citace je zapotřebí ]. Nakládání s chybějícími daty je však u modelů s podmíněnou hustotou často snazší[Citace je zapotřebí ].
Všechny výše uvedené algoritmy lineárního klasifikátoru lze převést na nelineární algoritmy pracující na jiném vstupním prostoru , za použití trik s jádrem.
Diskriminační trénink
Diskriminační trénink lineárních klasifikátorů obvykle probíhá v a pod dohledem způsobem, pomocí optimalizační algoritmus který dostane tréninkovou sadu s požadovanými výstupy a funkce ztráty který měří nesoulad mezi výstupy klasifikátoru a požadovanými výstupy. Učební algoritmus tedy řeší optimalizační problém formuláře[1]
kde
- w je vektor parametrů klasifikátoru,
- L(yi, wTXi) je funkce ztráty, která měří rozdíl mezi predikcí klasifikátoru a skutečným výstupem yi pro ipříklad školení,
- R(w) je regulace funkce, která brání tomu, aby se parametry příliš zvětšily (způsobily nadměrné vybavení ), a
- C je skalární konstanta (nastavená uživatelem algoritmu učení), která řídí rovnováhu mezi funkcí regularizace a ztráty.
Mezi oblíbené ztrátové funkce patří ztráta závěsu (pro lineární SVM) a ztráta protokolu (pro lineární logistickou regresi). Pokud je funkce regularizace R je konvexní, pak výše uvedené je a konvexní problém.[1] Pro řešení těchto problémů existuje mnoho algoritmů; populární pro lineární klasifikaci zahrnují (stochastický ) klesání, L-BFGS, sestup souřadnic a Newtonovy metody.
Viz také
- Zpětná propagace
- Lineární regrese
- Perceptron
- Kvadratický klasifikátor
- Podporujte vektorové stroje
- Winnow (algoritmus)
Poznámky
- ^ A b C Guo-Xun Yuan; Chia-Hua Ho; Chih-Jen Lin (2012). „Nedávné pokroky ve velkém měřítku lineární klasifikace“ (PDF). Proc. IEEE. 100 (9).
- ^ T. Mitchell, Generativní a diskriminační klasifikátory: Naivní Bayes a logistická regrese. Předloha, 2005
- ^ A. Y. Ng a M. I. Jordan. Diskriminační vs. generativní klasifikátory: Porovnání logistické regrese a Naive Bayes. v NIPS 14, 2002.
- ^ R.O. Duda, P.E. Hart, D.G. Stork, "Klasifikace vzorů", Wiley, (2001). ISBN 0-471-05669-3
- ^ R.O. Duda, P.E. Hart, D.G. Stork, "Pattern Classification", Wiley, (2001). ISBN 0-471-05669-3
Další čtení
- Y. Yang, X. Liu, „Přezkoumání kategorizace textu“, Proc. Konference ACM SIGIR, s. 42–49, (1999). paper @ citeseer
- R. Herbrich, "Learning Kernel Classifiers: Theory and Algorithms", MIT Press, (2001). ISBN 0-262-08306-X