logo-IBA logo-MU © Institut biostatistiky a analýz INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc. logo-IBA logo-MU © Institut biostatistiky a analýz IV. LINEÁRNÍ KLASIFIKACE – pokračování — levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ þAlgoritmus podpůrných vektorů (Support vector machines - SVM) je metoda strojového učení. SVM hledá nadrovinu, která v prostoru příznaků optimálně rozděluje trénovací data. þOptimální nadrovina je taková, že body leží v opačných poloprostorech a hodnota minima vzdáleností bodů od roviny je co největší. Jinými slovy, okolo nadroviny je na obě strany co nejširší pruh bez bodů. þNa popis nadroviny stačí pouze nejbližší body, kterých je obvykle málo - tyto body se nazývají podpůrné vektory (angl. support vectors) a odtud název metody. Tato metoda je ze své přirozenosti binární, tedy rozděluje data do dvou množin. Rozdělující nadrovina je lineární funkcí v prostoru příznaků. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ (SUPPORT VECTOR MACHINE – SVM) þSEPARABILNÍ TŘÍDY þmějme v učební množině obrazy xi, i=1,2,…,n, ze dvou lineárně separabilních klasifikačních tříd ω1 a ω2 þcílem je určení parametrů definující hranici þy(x) = wTx + w0 = 0, þjejíž pomocí klasifikátor správně zařadí všechny obrazy z učební množiny skenování0001.jpg levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ SEPARABILNÍ TŘÍDY þpřipomenutí: þvzdálenost jakéhokoliv bodu od klasifikační hranice je skenování0001.jpg levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þurčeme hodnoty váhového vektoru w a w0 tak, aby hodnota y(x) v nejbližším bodě třídy ω1 byla rovna 1 a pro ω2 rovna -1 ALGORITMUS PODPŮRNÝCH VEKTORŮ SEPARABILNÍ TŘÍDY skenování0002.jpg levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ SEPARABILNÍ TŘÍDY þmáme „ochranné“ klasifikační pásmo o šířce þ þ þ a chceme þ þ nebo také - chceme najít minimální þ þ þza předpokladu, že þ þkde ti =+1 pro ω1 a ti =-1 pro ω2 þ(minimalizace normy maximalizuje klasifikační pásmo) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þnelineární kvadratická optimalizační úloha se soustavou podmínek formulovaných pomocí lineárních nerovností þKarushovy-Kuhnovy-Tuckerovy podmínky praví, že pro to musí být splněno þ þ þ þ þ þ kde λ je vektor Langrangových součinitelů a L(w,w0, λ) je Lagrangova funkce definována vztahem ALGORITMUS PODPŮRNÝCH VEKTORŮ SEPARABILNÍ TŘÍDY levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þkdyž se všechny vztahy z předcházející strany dají dohromady dostaneme ALGORITMUS PODPŮRNÝCH VEKTORŮ SEPARABILNÍ TŘÍDY podpůrné vektory levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ NESEPARABILNÍ TŘÍDY þstále ale platí, že klasifikační „ochranné“ pásmo je definováno dvěma paralelními „nadrovinami“ definovanými þwTx + w0 = ± 1 þobrazy z trénovací množiny patří do následujících tří kategorií: èobraz leží vně pásma a je správně klasifikován [platí podmínka ti(wTx+w0)³1 i=1,2,…,n]; skenování0003.jpg èobraz leží uvnitř pásma a je správně klasifikován (čtverečky) [platí pro ně 0£ ti(wTx+w0)<1]; èobraz je chybně klasifikován (kolečka) [platí pro něj ti(wTx+w0)<0] levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þvšechny tři kategorie obrazů mohou být řešeny na základě pro daný typ specifických podmínek þ ti(wTx+w0)³1-ξi þ pomocí nově zavedených proměnných ξi (tzv. volné proměnné - slack variables). þ První kategorie je pro ξi=0, druhá 0<ξi£1 a třetí pro ξi>1. þCílem návrhu v tomto případě je vytvořit co nejširší „ochranné“ pásmo, ale současně minimalizovat počet obrazů s ξi>0, což vyjadřuje kritérium se ztrátovou funkcí þ þ þ kde ξ je vektor parametrů ξi a ALGORITMUS PODPŮRNÝCH VEKTORŮ NESEPARABILNÍ TŘÍDY C je kladná korekční konstanta, která váhuje vliv obou členů v uvedeném vztahu. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þoptimalizace je obtížná, protože ztrátová funkce je nespojitá (díky funkci I(•)). V takových případech se proto používá náhradní ztrátová funkce þ þa cílem návrhu je minimalizovat J(w,w0,ξ) za podmínek, že þ ti(wTx+w0)³1-ξi a ξi ³0, i=1,2,…,n. þProblém lze opět řešit pomocí Langrangeovy funkce þ ALGORITMUS PODPŮRNÝCH VEKTORŮ NESEPARABILNÍ TŘÍDY levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þpříslušné Karushovy-Kuhnovy-Tuckerovy podmínky jsou þ ALGORITMUS PODPŮRNÝCH VEKTORŮ NESEPARABILNÍ TŘÍDY levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þz čehož platí požadavek na maximalizaci L(w,w0,λ,ξ,μ) za podmínek þ ALGORITMUS PODPŮRNÝCH VEKTORŮ NESEPARABILNÍ TŘÍDY levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ þDůležitou součástí techniky Support vector machines je jádrová transformace (angl. kernel transformation) prostoru příznaků dat do prostoru transformovaných příznaků typicky vyšší dimenze. Tato jádrová transformace umožňuje převést původně lineárně neseparovatelnou úlohu na úlohu lineárně separovatelnou, na kterou lze dále aplikovat optimalizační algoritmus pro nalezení rozdělující nadroviny. þPoužívají se různé jádrové transformace. Intuitivně, vyjadřují podobnost dat, tj. svých dvou vstupních argumentů. þVýhodou této metody (a jiných metod založených na jádrové transformaci) je, že transformace se dá definovat pro různé typy objektů, nejen body v Rn. Např. pro grafy, stromy, posloupnosti DNA ... þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS PODPŮRNÝCH VEKTORŮ skenování0002.jpg skenování0003.jpg dvourozměrný prostor s oddělovací hranicí ve tvaru x12 + x22 ≤ 1 tatáž situace zobrazená do trojrozměrného prostoru (x12, x22, Ö2x1x2) – kruhová hranice se stane lineární levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þpřímé rozšíření řešení případu dichotomického problému podle schématu è„jedna versus zbytek“ – M dichotomických úloh; è každý klasifikátor je trénován podle schématu s hraniční funkcí yi(x)>0 pro obrazy z ωi a yi(x)<0 pro všechny ostatní; è„jedna versus jedna“ – M(M-1)/2 binárních klasifikátorů èklasifikační schéma používající K binárních klasifikátorů, přičemž jednotlivé shluky obrazů z jednotlivých tříd jsou stanoveny navrhovatelem a jsou kódovány vektory o délce K, jehož hodnoty jsou +1 nebo -1. è např. pro M=4 a K=6 může být taková matice è ALGORITMUS PODPŮRNÝCH VEKTORŮ VÍCE KLASIFIKAČNÍCH TŘÍD levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þPříprava nových učebních materiálů þpro obor Matematická biologie þje podporována projektem ESF þč. CZ.1.07/2.2.00/07.0318 þ„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“ INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU