WIXLIB

1KERNEL-BASEDLEARNINGWM&R a.a. 2013/14R. Basili, (A. Moschitti)Università di Roma “Tor Vergata”basili@info.uniroma2.it

2Outline Metodi Kernel Motivazioni Esempio Kernel standard Polynomial kernel String Kernel Introduzione a metodi Kernel avanzati (Tree kernels) Lexical semantic kernels

3La funzione Kernel Il learning dipende solo dal prodotto scalare dei vettori diesempio Quindi dipende dalla Gram-matrix. In generale si definiscekernel la funzione: K ( z , x) ( z ) ( x) La funzione kernel produce il risultato a partire dagli oggettiiniziali Quando la mappatura è l’identità abbiamo l’usuale prodottoscalare. Gli esempi compaiono nell’algoritmo di learning (ad es. ilpercettrone) solo attraverso i loro contributi al kernel

4Primo Vantaggio:rendere linearmente separabili gli esempi Mappare i dati in uno Spazio di Feature dove sono linearmente separabili x (x )(i.e. attributi feature) oox (x) (x)ox (o)x (x) (o)oxo (o) (o) (x) (o)

5Esempio di una funzione di mappaturaDue masse m1 e m2 , una vincolataApplico una forza fa alla massa m1EsperimentiFeatures m1 , m2 e faSupponiamo di volere apprendere quando m1 si allontana da m2Considerando la legge gravitazionale di Newtonm1m2f (m1 , m2 , r ) C 2rDobbiamo determinare se f(m1 , m2 , r) fa

6Esempio di una funzione di mappatura x ( x1 ,., xn ) ( x ) ( 1 ( x ),., n ( x ))Non esprimibile linearmente, quindi cambio spazio( f a , m1 , m2 , r ) (k , x, y, z ) (ln f a , ln m1 , ln m2 , ln r )Poichéln f (m1 , m2 , r ) ln C ln m1 ln m2 2 ln r c x y 2 zAllora l’iperpiano è la funzione richiestaln f a ln m1 ln m2 2 ln r ln C 0(1,1,-2,-1) (ln m1,ln m2,ln r, ln fa) ln C 0, posso decideresenza errore se le masse si avvicinano o si allontanano

7Feature Spaces and Kernels Feature Space Lo spazio di input è mappato in unnuovo spazio dotato di prodotto scalareF (detto feature space) attraverso unatrasformazione (non lineare) Kernel RN F La valutazione della funzione didecisione richiede il prodotto scalare mamai i pattern rimappati in formaesplicita (x) Il prodotto scalare viene calcolatoattraverso la funzione kernelk ( x, y) ( ( x) ( y))

8Funzione di classificazione: forma duale sgn( w x b) sgn j y j x j x b j 1. Notare che i dati appaiono solo nel prodotto scalareLa matrice G xi x j li , j 1è chiamata Gram matrix

9Algoritmo duale del Percettrone e le funzioni KernelPossiamo riscrivere la funzione di decisione: h( x) sgn(w ( x ) b) sgn( j y j ( x j ) ( x ) b) sgn( j y j k ( x j , x ) b)j 1. i 1. e nel processo di aggiornamento yi ( j y j ( x j )) ( xi ) b j 1. j yi y j k ( x j , xi ) bj 1.

10Kernels in Support Vector Machines Nel problema Soft Margin SVMs si deve massimizzare:Usando le funzioni kernel possiamo riscrivere il problemacome:

11Definizione delle Funzioni Kernel Le funzioni kernel esprimono mappature implicite diquesto tipo x n , ( x ) ( 1 ( x ), 2 ( x ),., m ( x )) m

12Validità delle funzioni kernel (1)

13Validità delle funzioni kernel (2) L’idea principale di questa proposizione è chese la Gram matrix è semidefinita positiva allora esiste ilmapping che realizza la funzione kernel, cioè unospazio F in cui la separabilità è espressa in modo migliore

14Feature Spaces and Kernels Esempio di Kernel Polynomial kernel Se d 2 ek ( x, y) ( x y) dx, y R 2 x12 y12 x1 y1 2( x y ) 2 x1 x2 2 y1 y 2 2 x2 y 2 x 2 y 2 2 ( ( x) ( y )) k ( x, y )2

15Polynomial Kernel (n dimensions)

16General Polynomial Kernel (n dimensions)

17Polynomial kernel andthe conjunction of features The initial vectors can be mapped into a higher dimensionalspace (c 1) ( x1 , x2 ) ( x12 , x22 , 2 x1 x2 , 2 x1 , 2 x2 ,1) More expressive, as( x1 x2 ) encodesstock market vs. downtown market features We can smartly compute the scalar product as ( x ) ( z ) ( x12 , x22 , 2 x1 x2 , 2 x1 , 2 x2 ,1) ( z12 , z 22 , 2 z1 z 2 , 2 z1 , 2 z 2 ,1) x12 z12 x22 z 22 2 x1 x2 z1 z 2 2 x1 z1 2 x2 z 2 1 ( x1 z1 x2 z 2 1) 2 ( x z 1) 2 K p2 ( x , z )

18Architettura di una SVM Classificatore non lineare (basato su kernel) La funzionedi decisione èlf ( x) sgn( vi ( ( x) ( xi )) b)i 1l sgn( vi k ( x, xi ) b)i 1 ( xi ) sostituisc e ogniesempio di training xivi i y ivi sono calcolate attraverso la soluzionedel problema di ottimizzazione

19String Kernel Given two strings, the number of matches between theirsubstrings is computed E.g. Bank and Rank B, a, n, k, Ba, Ban, Bank, an, ank, nk R, a , n , k, Ra, Ran, Rank, an, ank, nk String kernel over sentences and texts Huge space but there are efficient algorithms

20Formal DefinitionSottosequenza di indici ordinati enon contigui di (1, s ), substring of s defined by I, con1, con

21Kernel tra Bank e Rank Common substrings:– a, n, k, an, ank, nk, ak Notice how these are the same subsequences asbetween Schrianak and Rank

22An example of string kernel computation

23Tree Kernels Cio’ che è stato mostrato per la gestione di sequenze(stringhe) nell’apprendimento di una SVM non dipendestrettamente dalla nozione di sequenza, ma si applica astrutture piu’ complesse Alberi, che sono caratterizzati da un molteplicità sottosequenze, checorrispondono ai cammini radice-foglie Grafi, che sono caratterizzati da piu’ alberi, quindi da una maggioremolteplicità di sottosequenze

24Tree kernels Applications are related to text processing taskssuch as Syntactic parsing, when SVM classification is useful toselect the best parse tree among multiple legalgrammatical interpretations Question Classification, where SVM classification isapplied to the recognition of the target of a question (e.g.a person such as in “Who is the inventor of the light?” vs.a place as in “Where is Taji Mahal?”or to pattern recognition (e.g. in bioinformatics theclassification of protein structures)

25Tree kernels Details are in a separated lesson’s slides

26Kernel Lessicale Semantico I sistemi di Text Classification agiscono sulle rappresentazionivettoriali d dei documenti d Dato un documento d posso tentare di rappresentarlo in unospazio dei concetti (cioe’ sensi secondo Wordnet) invece chenello spazio di parole (VSM tradizionale) Questo genera una immagine (complessa) dei sensi delleparole di d che chiameremo (d ) Per apprendere da esempi d1 e d2 si può utilizzare unafunzione della similitudine tra tutti i termini di d1 e quelli di d2,con un kernel (semantico lessicale) che calcola quindiSK (d1 , d 2 ) (d1 ) (d 2 )

27Kernel Lessicale Semantico (2) La similarità tra due documenti, d1 e d2, è data dalkernel semantico SK seguente:SK (d1 , d 2 ) dove s (w , w )w1 d1 ,w2 d 212s è una funzione della similarità semantica inWordnet tra due parole Una possibile scelta di s è data dalla conceptualdensity in Wordnet (vedi lezioni su WSD)

28Similarità tra documenti e conceptual densitysu coppie di paroleDoc 2Doc 1industrys (industry , company )companys (.,.)s (.,.)telephones (telephone, product )products (.,.)markets (market, product )OSS: in un VSM tradizionale la similarità tra i due documentisarebbe 0 perche’ non ci sono parole comuni tra Doc1 e Doc2!!

29Is it a valid kernel? It may not be a kernel so we can use M M

30Summary La forma duale del problema di ottimizzazione di una SVMdipende solo dal prodotto scalare degli esempi diadddestramento e NON dalla loro esplicita rappresentazionevettoriale (come nel percettrone) Questo suggerisce di sfruttare questa proprietà per Definire funzioni capaci di calcolare in modo il prodotto scalare a partiredalla rappresentazione originale Utilizzando quindi rappresentazioni (cioe’ spazi di feature) piu’complesse(i) in modo implicito Tale ricerca di spazi linearmente separabili Mantiene le proprietà matematiche che garantiscono la minimizzazionedell’errore atteso Contiene la complessità del processo di training e di classificazione

31Summary (2) Affinchè una funzione K(.,.) sia un kernel la gram matrixcorrrispondente deve essere semi-definita positiva Possono essere fornite anche semplici prove empiriche di taleproprietà sui data set di addestramento Sono state discusse: Funzioni kernel di base (per esempio I kernel polinomiali di grado 2) Funzioni kernel dipendenti dalla struttura del task String (Sequence) kernels Semantic kernel

32References Kernel Methods for Pattern Analysis, John Shawe-Taylor & Nello Cristianini- Cambridge University Press, 2004 Haussler, D. (1999). Convolution kernels on discrete structures. TechnicalReport UCSC-CRL-99-10, UC Santa Cruz Lodhi, Huma; Saunders, Craig; Shawe-Taylor, John; Cristianini, Nello;Watkins, Chris (2002). "Text classification using string kernels". Journal ofMachine Learning Research: 419–444. Roberto Basili, Marco Cammisa and Alessandro Moschitti, Effective use ofwordnet semantics via kernel-based learning. In Proceedings of the 9thConference on Computational Natural Language Learning (CoNLL 2005),Ann Arbor(MI), USA, 2005 Building Semantic Kernels for Text Classification using Wikipedia, Pu Wangand Carlotta Domeniconi, Department of Computer Science, George MasonUniversity

La funzione Kernel Il learning dipende solo dal prodotto scalare dei vettori di esempio Quindi dipende dalla Gram-matrix.In generale si definisce kernel la funzione: La funzione kernel produce il risultato a partire dagli oggetti iniziali Quando la mappatura è l'identità abbiamo l'usuale prodotto scalare. Gli esempi compaiono nell'algoritmo di learning (ad es. il