Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f PLIN037 Sémantika a počítače OP VK Mezi bohemistikou a informatikou www. proj e kt- i n ova. cz Zuzana Nevěřilová xpopelkOf i.muni.cz Centrum zpracování přirozeného jazyka, B203 Fakulta informatiky, Masarykova univerzita 7. dubna 2016 Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami Podobnost Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Klasifikace parafrází ■ obtížný úkol, se kterým se každý vyrovná po svém (—>► nízká mezianotátorská shoda) ■ anotační manuál (který buď nezachytí všechny případy, nebo ho nikdo nebude číst) ■ řešení neshody (třetí anotátor) ■ řešení náhodné shody? (výpočet Cohen k nebo Fleiss k) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Klasifikace parafrází ■ obtížný úkol, se kterým se každý vyrovná po svém (—>► nízká mezianotátorská shoda) ■ anotační manuál (který buď nezachytí všechny případy, nebo ho nikdo nebude číst) ■ řešení neshody (třetí anotátor) ■ řešení náhodné shody? (výpočet Cohen k nebo Fleiss k) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti Lehký úvod do strojového učení učení = změna stavu na základě vnějších podnětů strojové učení: 1) máme program (který se už nebude měnit), 2) máme vstupní (trénovací) data výsledek: 3) program se z trénovacích dat naučí klasifikovat libovolná další data Aby bylo strojové učení užitečné, musí mít vysokou přesnost: ■ velké množství trénovacích dat ■ velká rozmanitost trénovacích dat ■ vhodně definovaná klasifikační úloha ■ vhodný algoritmus strojového učení (podle povahy dat) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Lehký úvod do strojového učení Velmi důležité je znát data: ■ velikost datového souboru ■ způsob pořízení dat (kvůli možných chybám) ■ původce dat ■ distribuce sledovaného jevu (tady se opravdu hodí statistika) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Lehký úvod do strojového učení známe-li data, můžeme se pustit do strojového učení Základní techniky: ■ rozhodovací stromy, rozhodovací seznamy ■ vzdálenosti ■ naivní Bayesovský klasifikátor ■ k-NN (nearest neighbors), klastrování ■ neuronové sítě Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Vzdálenost (distance) a metrika (metric) Vzdálenost D je funkce definovaná na kartézském součinu X x X s nezápornými hodnotami. D : X x X -+n Vx,y : D(x,y) >0 Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mez Vzdálenost (distance) a metrika (metric) Vzdálenost D je funkce definovaná na kartézském součinu X x X s nezápornými hodnotami. D.XxX^K Vx,y : D(x,y)>0 Vzdálenost je metrika, pokud: ■ D(x, y) = 0 x = y (identita) ■ D(x,y) + D(y,z) > D(x,y) (trojúhelníková nerovnost) ■ D(x,y) = D(y,x) (symetrie) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mez Vzdálenost (distance) a metrika (metric) Vzdálenost D je funkce definovaná na kartézském součinu X x X s nezápornými hodnotami. D.XxX^K Vx,y : D(x,y)>0 Vzdálenost je metrika, pokud: ■ D(x, y) = 0 x = y (identita) ■ D(x,y) + D(y,z) > D(x,y) (trojúhelníková nerovnost) ■ D(x,y) = D(y,x) (symetrie) Množinu X nazýváme metrický prostor. Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Vzdálenost mezi body Triviální diskrétní metrika: - D(x,y) = 0 ^ x = y ■ D(x,y) = l^x^y Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Vzdálenost mezi body Euklidovská vzdálenost: ■ D(x,y) = J(x — y)2 - jednorozměrná ■ D{p, q) = yj(pi - qi)2 + (p2 - (72)2, p = (pi, P2), q = (q±, 172) - dvourozměrná ■ D{p, q) = yj(pi - (71)2 + (P2 - qi)2 + (P3 - qz)2, P = (pi, P2, P3), <7 = (<7i, 92, ťfó) - trojrozměrná ■ D(p, q) = A/(pi-(7i)2 + --- + (Pn-í7n)2, p = (pi,..., pn), (7 = (qri, • • •, qn) ~ n-rozměrná Čtverec euklidovské vzdálenosti: D2(x,y) = (x — y)2 Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálen Vzdálenost mezi body Euklidovská vzdálenost: ■ D(x,y) = J(x — y)2 - jednorozměrná ■ D{p, q) = yj(pi - qi)2 + (p2 - (72)2, p = (pi, P2), q = (q±, 172) - dvourozměrná ■ D{p, q) = yj(pi - (71)2 + (P2 - qi)2 + (P3 - <73)2, P = (pi, P2, P3), <7 = (<7i, 92, qz) ~ trojrozměrná ■ D(p, q) = A/(pi-(7i)2 + --- + (Pn-í7n)2, p = (pi,..., p„), q = (q1,...,qn)- n-rozměrná Čtverec euklidovské vzdálenosti: D2(x,y) = (x — y)2 Manhattanská vzdálenost D(p, q) = |pi - qi\ + |P2 - <721, P = {Pi.,Pi),q = (fli,*) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Vzdálenost mezi vektory Kosinová vzdálenost: cos(9) = AB A B Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Vzdálenost mezi vektory Kosinová vzdálenost: cos(e)= AB A B A = (aua2),B=(b1,b2) cos(0) = □ Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Vzdálenosti mezi řetězci Levenshteinova vzdálenost a její varianty (nejmenší) počet operací (transpozic, transposition), které řetězec si převedou na řetězec S2 Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mez Vzdálenosti mezi řetězci Levenshteinova vzdálenost a její varianty (nejmenší) počet operací (transpozic, transposition), které řetězec si převedou na řetězec S2 Hammingova vzdálenost počet pozic, které jsou mezi dvěma řetězci rozdílné (non-matching characters) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mez Vzdálenosti mezi řetězci Levenshteinova vzdálenost a její varianty (nejmenší) počet operací (transpozic, transposition), které řetězec si převedou na řetězec S2 Hammingova vzdálenost počet pozic, které jsou mezi dvěma řetězci rozdílné (non-matching characters) Jaro-Winkler, Soundex (založen na hláskové podobnosti) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami f Vzdálenosti mezi množinami Jaccardův koeficient: Q = 2l^nfíl AU B S0rensenův-Diceův koeficient: Q = 2 AílB A + B Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Editační vzdálenost stromů (tree edit distance) operace (podobné jako u L. vzdálenosti) ■ přidat uzel u ■ smazat uzel u (a připojit jeho potomky k rodiči u) ■ přejmenovat uzel Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami F Editační vzdálenost stromů (tree edit distance) operace (podobné jako u L. vzdálenosti) ■ přidat uzel u ■ smazat uzel u (a připojit jeho potomky k rodiči u) ■ přejmenovat uzel řádově těžší úloha (použití rekurze) Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami F Podobnost Podobnost je (nějakým způsobem) převrácená hodnota vzdálenosti. Lehký úvod do strojového učení Vzdálenost a metrika Vzdálenosti mezi body Vzdálenosti mezi řetězci Vzdálenosti mezi množinami F