WMR 22 - Kernel Methods II

Lecture Info

In questa lezione abbiamo trattato i metodi kernel, andando in particolare a vedere come è possibile definire delle funzioni kernel a partire da spazi di input discreti, come nel caso delle string kernel.

1 Conjuction of Features

Accoppiando a due a due le proprietà di ingresso siamo in grado di aumentare il numero di feature per ogni istanza, in modo da rendere il training set più espressivo.

Ad esempio possiamo considerare il seguente mapping

\[\Phi(\langle x_1, x_2 \rangle) = (x_1^2, x_2^2, \sqrt{2} x_1 x_2, \sqrt{2} x_1, \sqrt{2} x_2, 1)\]

Da questo è poi possibile calcolare il prodotto scalare nel seguente modo

\[\Phi(\overline{x}) \cdot \Phi(\overline{z}) = ... = (x_1z_1 + x_2z_2 + 1)^2 = (\overline{x} \cdot \overline{z} + 1)^2 = K_{p^2}(\overline{x}, \overline{z})\]

2 String Kernel

Fino adesso abbiamo solamente trattato di kernel che agiscono su spazi vettoriali e che quindi eseguono trasformazioni tra spazi continui in spazi continui. Detto questo, è anche possibile definire delle funzioni kernel che partono da insiemi di elementi discreti, e che tramite procedure algoritmiche mappano questi ultimi in spazi continui.

Consideriamo ad esempio la rappresentazione delle stringhe. Uno string kernel dovrebbe fornirci un metodo per mappare parole simili in vettori di numeri simili. Per fare questo l'idea è quella di utilizzare le sottostringhe. In particolare, date due stringhe, più queste stringhe condividono sottostringhe uguali, e più sono "simili" nello spazio delle features su cui vengono mappate.

Uno string kernel deve quindi prendere in input due stringhe \(s\) e \(t\) e deve essere in grado di calcolare il numero reale \(k(s, t)\) tale che:

  • Esistono due vettori \(\overline{s}, \overline{t}\).

  • I vettori \(\overline{s}\) e \(\overline{t}\) sono unici fissati \(s\) e \(t\).

  • \(k(s, t) = \overline{s} \cdot \overline{t}\).

Per poter definire \(k(s, t)\) devo poter essere in grado di enumerare tutte le sottostringhe di lunghezza arbitraria. In altre parole sto enumerando degli elementi nello spazio \(\mathbb{R}^{\infty}\). L'idea infatti è proprio quella di definire uno spazio in cui ogni sottostringa rappresenta una dimensione.

Esempio: Consideriamo ad esempio le parole \(\text{Bank}\) e \(\text{Rank}\), ed analizziamo tutte le sottostringhe possibili di queste stringhe

\[\begin{split} \text{B}, \text{a}, \text{n}, \text{k}, \text{Ba}, \text{Ban}, \text{Bank}, \text{an}, \text{ank}, \text{nk} \\ \\ \text{R}, \text{a}, \text{n}, \text{k}, \text{Ra}, \text{Ran}, \text{Rank}, \text{an}, \text{ank}, \text{nk} \\ \end{split}\]

Mattiamo quindi queste stringhe nello spazio menzionato prima per ottenere

Notiamo che per calcolare il prodotto scalare tra queste due stringhe non dobbiamo esplorare l'intero spazio delle features, in quanto abbiamo infinite dimensioni con valore \(0\).

2.1 Formal Definition

Consideriamo una stringa \(s = s_1,\ldots,s_{|s|}\), e consideriamo una sua generica sottostringa definita da una sequenza di indici ordinati ed eventuali non contigui \(\overline{I} = (i_1,\ldots,i_{|u|})\) di \((1, \ldots, |s|)\). Indichiamo con \(u = s[\overline{I}]\) la relativa sottostringa.

Alla sottostringa \(u\) di \(s\) associo il seguente numero reale

\[\phi_u(s) = \sum\limits_{\overline{I}: u = s[\overline{I}]} \lambda^{l(\overline{I})}\]

con \(l(\overline{I}) = i_{|u|} - i_1 + 1\). Con questa definizione abbiamo che più grande è la sottostringa, e minore sarà il suo contributo.

A questo punto è possibile definire il kernel nel seguente modo

\[\begin{split} K(s, t) = \sum\limits_{u \in \Sigma^*} \phi_u(s) \cdot \phi_u(t) &= \sum\limits_{u \in \Sigma^*} \sum\limits_{\overline{I}: u = s[\overline{I}]} \lambda^{l(\overline{I})} \sum\limits_{\overline{J}: u = t[\overline{J}]} \lambda^{l(\overline{J})} \\ &= \sum\limits_{u \in \Sigma^*} \sum\limits_{\overline{I}: u = s[\overline{I}]} \sum\limits_{\overline{J}: u = t[\overline{J}]} \lambda^{l(\overline{I}) + l(\overline{J})} \end{split}\]

Notiamo ora che la sommatoria esterna fatta sull'insieme \(\Sigma^* = \sum_{n = 0}^{\infty} \Sigma^n\) è superflua.

2.2 Exercise

Esercizio: Scrivere un kernel che, dato un insieme di parole, stipula la simularità tra due insiemi come component-wise matching di tutti i loro sottoinsiemi. Voglio quindi ottenere un kernel \(k\) che mi dice quando due documenti sono simili sulla base di quanti sottoinsieme di parole i due documenti condividono tra loro.

3 Tree Kernels

Un albero non è nient'altro che la composizione di tutti i suoi sotto-alberi. È dunque possibile definire in modo analogo a quanto fatto prima un kernel che calcola la similarità tra due alberi enumerando i sotto-alberi dei due alberi.