Hodnocení SVM - Ranking SVM
v strojové učení, a Hodnocení SVM je varianta podporovat vektorový stroj algoritmus, který se používá k řešení určitých hodnocení problémy (přes naučit se hodnotit ). Algoritmus žebříčku SVM publikoval Thorsten Joachims v roce 2002.[1] Původním účelem algoritmu bylo zlepšit výkon souboru internetový vyhledávač. Bylo však zjištěno, že Ranking SVM lze použít také k řešení dalších problémů, jako je Pořadí SIFT.[2]
Popis
Algoritmus Ranking SVM je funkce načítání učení, která využívá párové metody hodnocení k adaptivnímu třídění výsledků podle toho, jak „relevantní“ jsou pro konkrétní dotaz. Funkce Ranking SVM používá mapovací funkci k popisu shody mezi vyhledávacím dotazem a vlastnostmi každého z možných výsledků. Tato funkce mapování promítá každý datový pár (například vyhledávací dotaz a kliknutou webovou stránku) na prostor funkcí. Tyto funkce jsou kombinovány s odpovídajícími údaji o prokliku (které mohou fungovat jako proxy pro to, jak relevantní je stránka pro konkrétní dotaz), a poté je lze použít jako tréninková data pro algoritmus Ranking SVM.
Ranking SVM obecně zahrnuje tři kroky v tréninkovém období:
- Mapuje podobnosti mezi dotazy a kliknutými stránkami na určitý prostor funkcí.
- Vypočítá vzdálenosti mezi libovolnými dvěma vektory získanými v kroku 1.
- Vytváří optimalizační problém, který je podobný standardní klasifikaci SVM a tento problém řeší běžným řešičem SVM.
Pozadí
Způsob hodnocení
Předpokládat je datová sada obsahující elementy . je hodnocení metoda aplikována na . Pak v lze reprezentovat jako a podle asymetrická binární matice. Pokud je hodnost je vyšší než hodnost , tj. , je odpovídající poloha této matice nastavena na hodnotu "1". Jinak bude prvek na této pozici nastaven jako hodnota „0“.
Kendall's Tau [3][4]
Kendall's Tau také odkazuje Kendall tau rank korelační koeficient, který se běžně používá k porovnání dvou metod hodnocení pro stejnou sadu dat.
Předpokládat a jsou dvě metody hodnocení aplikované na soubor dat , mezi Kendallovým Tau a lze reprezentovat následovně:
kde je počet shodných párů a je počet nesouhlasných párů (inverzí). Pár a je shodný, pokud obojí a dohodněte se, jak si objednají a . Je nesouhlasné, pokud nesouhlasí.
Kvalita načítání informací [5][6][7]
Získávání informací kvalita se obvykle hodnotí pomocí následujících tří měření:
- Přesnost
- Odvolání
- Průměrná přesnost
Pro konkrétní dotaz do databáze, let být souborem příslušných informačních prvků v databázi a být množinou načtených informačních prvků. Poté lze výše uvedená tři měření znázornit takto:
kde je z .
Nechat a být očekávanou a navrhovanou metodou hodnocení databáze, dolní mez průměrné přesnosti metody lze reprezentovat následovně:
kde je počet různých prvků v horních trojúhelníkových částech matic a a je počet příslušných prvků v souboru dat.
Klasifikátor SVM [8]
Předpokládat je prvek souboru tréninkových dat, kde je vektor funkcí a je štítek (který klasifikuje kategorii ). Typický klasifikátor SVM pro takový soubor dat lze definovat jako řešení následujícího optimalizačního problému.
Řešení výše uvedeného optimalizačního problému lze představit jako a lineární kombinace vektorů prvků s.
kde je koeficient, který má být určen.
Algoritmus hodnocení SVM
Funkce ztráty
Nechat být Kendallovým tau mezi očekávanou metodou hodnocení a navrhovaná metoda , lze dokázat, že maximalizovat pomáhá minimalizovat spodní hranici průměrné přesnosti .
- Funkce očekávané ztráty [9]
Negativní lze vybrat jako funkce ztráty minimalizovat spodní hranici průměrné přesnosti
kde je statistické rozdělení na určitý dotaz .
- Funkce empirické ztráty
Protože funkce očekávané ztráty není použitelná, je pro tréninková data v praxi vybrána následující empirická funkce ztráty.
Sběr tréninkových dat
i.i.d. dotazy se aplikují na databázi a každý dotaz odpovídá metodě hodnocení. Soubor tréninkových dat má elementy. Každý prvek obsahuje dotaz a odpovídající metodu hodnocení.
Prostor funkcí

Funkce mapování [10][11] je nutné k mapování každého dotazu a prvku databáze na prostor funkcí. Poté je každý bod v prostoru funkcí označen určitým hodnocením podle metody hodnocení.
Problém s optimalizací
Body generované tréninkovými daty jsou v prostoru funkcí, které také nesou informace o hodnosti (štítky). Tyto označené body lze použít k nalezení hranice (klasifikátoru), která určuje jejich pořadí. V lineárním případě je taková hranice (klasifikátor) vektor.
Předpokládat a jsou dva prvky v databázi a označují pokud je hodnost je vyšší než v určité metodě hodnocení . Nechť vektor být kandidátem lineárního klasifikátoru v prostoru funkcí. Poté lze problém s hodnocením přeložit na následující problém s klasifikací SVM. Jedna metoda hodnocení odpovídá jednomu dotazu.
Výše uvedený problém s optimalizací je totožný s klasickým problémem klasifikace SVM, což je důvod, proč se tento algoritmus nazývá Ranking-SVM.


Funkce načítání
Optimální vektor získané tréninkovým vzorkem je
Funkce načítání by tedy mohla být vytvořena na základě takového optimálního klasifikátoru.
Pro nový dotaz , funkce načítání nejprve promítne všechny prvky databáze do prostoru funkcí. Potom seřadí tyto rysové body podle hodnot jejich vnitřních produktů s optimálním vektorem. Pozice každého funkčního bodu je hodností odpovídajícího prvku databáze pro dotaz .
Aplikace Ranking SVM
Hodnocení SVM lze použít k hodnocení stránek podle dotazu. Algoritmus lze trénovat pomocí dat z prokliku, kde se skládá z následujících tří částí:
- Dotaz.
- Aktuální hodnocení výsledků vyhledávání
- Výsledky vyhledávání, na které uživatel klikl
Kombinace 2 a 3 nemůže poskytnout úplné pořadí tréninkových dat, které je nutné k použití celého algoritmu SVM. Místo toho poskytuje část informací o hodnocení tréninkových dat. Algoritmus lze tedy mírně revidovat následovně.
Metoda neposkytuje informace o hodnocení celé datové sady, je to podmnožina metody úplného hodnocení. Stav optimalizačního problému se tedy ve srovnání s původním Ranking-SVM uvolní.
Reference
- ^ Joachims, T. (2002), „Optimizing Search Engines using Clickthrough Data“, Sborník z konference ACM o zjišťování znalostí a dolování dat
- ^ Bing Li; Rong Xiao; Zhiwei Li; Rui Cai; Bao-Liang Lu; Lei Zhang; „Rank-SIFT: Learning to Rank Repeatable Local Interest Points“, Počítačové vidění a rozpoznávání vzorů (CVPR), 2011
- ^ M.Kemeny. Rank Correlation Methods, Hafner, 1955
- ^ A. Mood, F. Graybill a D. Boes. Úvod do teorie statistiky. McGraw-Hill, 3. vydání, 1974
- ^ J. Kemeny a L. Snell. Matematické modely ve společenských vědách. Ginn & Co. 1962
- ^ Y. Yao. Měření efektivity vyhledávání na základě preferencí uživatelů dokumentů. Journal of the American Society for Information Science, 46 (2): 133-145, 1995.
- ^ R.Baeza-Yates a B. Ribeiro-Neto. Moderní vyhledávání informací. Addison- Wesley-Longman, Harlow, Velká Británie, květen 1999
- ^ C. Cortes a V.N Vapnik. Podporované vektorové sítě. Machine Learning Journal, 20: 273-297,1995
- ^ V.Vapnik. Statistická teorie učení. WILEY, Chichester, GB, 1998
- ^ N.Fuhr. Optimální funkce načítání polynomů založené na principu hodnocení pravděpodobnosti. ACM TRANSACTIONS on Information Systems, 7 (3): 183-204
- ^ N.Fuhr, S. Hartmann, G. Lustig, M. Schwantner, K. Tzeras a G. Knorz. Air / x - vícestupňový indexovací systém založený na pravidlech pro velká předmětová pole. In RIAO, 1991