Classificazione di testi, entropia e clustering

Classificazione di testi

Per classificare un testo in base al suo contenuto è necessario ottenere un vettore di ingresso.

Prendiamo un vettore con le $𝑛$ parole più significative del ‘dizionario’. Poi per ogni parola trovata nel testo, aumentiamo di 1 la componente corrispondente nel vettore (bag of words).

Note

Ignoriamo per il momento che viene persa l’informazione data dall’ordine delle parole.

Otteniamo un grande vettore di ingresso. Ora dobbiamo capire quali sono le features più significative. Per trovare correlazioni tra coppie di parole possiamo misurarne la dipendenza.

$$\left|\mathbb{P}\left({\text{word}}_1,{\text{word}}_2\right)-\mathbb{P}\left({\text{word}}_1\right)\mathbb{P}\left({\text{word}}_2\right)\right|$$

Se il valore della differenza è alto, allora c’è alta dipendenza tra le variabili.

Test del Chi quadro

Si usa per testare la dipendenza degli output dall’input.

$${\mathrm{{\rm X}}}^2=\sum _{𝑦,𝑥}\frac{{\left({\text{count}}_{𝑦,𝑥}-𝑛\mathbb{P}\left(𝑦\right)\mathbb{P}\left(𝑥\right)\right)}^2}{𝑛\mathbb{P}\left(𝑦\right)\mathbb{P}\left(𝑥\right)}$$

Dove ${\text{count}}_{𝑦,𝑥}$ è il numero di occorrenze del valore $𝑥$ per una data classe $𝑦$ e $𝑛$ è il numero totale di esempi nel dataset.

Le features migliori sono quelle con il ${\mathrm{{\rm X}}}^2$ più grande.

Entropia

Si usa per misurare quanta informazione fornisce una certa feature, maggiore è l’incertezza, maggiore sarà il valore:

$$𝐻\left(𝑌\right)=-\sum _{𝑦\in 𝑌}\mathbb{P}\left(𝑦\right)log\left(\mathbb{P}\left(𝑦\right)\right)\left[\text{bit}\right]$$

Quando conosciamo un valore d’ingresso ${𝑥}_{𝑖}$, otteniamo l’entropia condizionale. Essa sarà minore o uguale a quella iniziale.

$$𝐻\left(𝑌|{𝑋}_{𝑖}\right)=\sum _{{𝑥}_{𝑖}\in {𝑋}_{𝑖}}\mathbb{P}\left({𝑥}_{𝑖}\right)\left(-\sum _{𝑦\in 𝑌}\mathbb{P}\left(𝑦|{𝑥}_{𝑖}\right)log\left(\mathbb{P}\left(𝑦|{𝑥}_{𝑖}\right)\right)\right)\left[\text{bit}\right]$$

L’informazione mutua di ${𝑥}_{𝑖}$ è definita come la differenza tra l’entropia iniziale e quella condizionale.

$$𝐼\left(𝑌,{𝑋}_{𝑖}\right)=𝐻\left(𝑌\right)-𝐻\left(𝑌|{𝑋}_{𝑖}\right)=\sum _{𝑦,{𝑥}_{𝑖}}\mathbb{P}\left(𝑦,{𝑥}_{𝑖}\right)log\left(\mathbb{P}\frac{𝑦,{𝑥}_{𝑖}}{\mathbb{P}}\left(𝑦\right)\mathbb{P}\left({𝑥}_{𝑖}\right)\right)$$

Se $𝑦$ e ${𝑥}_{𝑖}$ sono indipendenti, allora $𝐼\left(𝑌,{𝑋}_{𝑖}\right)=0$ e possiamo scartare la feature.

L’informazione mutua è in grado di catturare dipendenze non lineari arbitrarie tra due variabili, quindi ci dice se otteniamo informazioni anche quando il coefficiente di correlazione è 0.

Clustering

Il clustering è l’operazione di raggruppare nuovi input (in maniera non supervisionata) e assegnare etichette ad essi.

A livello matematico, significa riconoscere delle singole varietà all’interno di spazi altamente dimensionali. Fatto questo, molte features diventeranno ridondanti e quindi potranno essere scartate.

La compressione dell’informazione avviene attraverso i prototipi. Ogni prototipo riassume l’informazione contenuta nel sottoinsieme di casi che rappresenta. In questo caso riassumere significa applicare una funzione $𝑓:{ℝ}^{𝑛}\to {ℝ}^{𝑚}$, dove $𝑛>𝑚$.

Approcci per l’apprendimento non supervisionato

• top-down: si decide il numero di classi e poi si dividono i dati in queste classi.
• bottom-up: si inizia a raggruppare i dati e ci si ferma quando ha senso per la specifica applicazione.