Riconoscimento e recupero dell’informazione per bioinformatica · Data una persona da...

Riconoscimento e recupero dell’informazione per

bioinformatica

Classificazione

Manuele Bicego

Corso di Laurea in Bioinformatica

Dipartimento di Informatica - Università di Verona

2

Sistema di classificazione

Insieme di addestramento

x1,y1

x2,y2

...

xN,yN

Addestramento: modellare (separare) le due classi

altezza

lunghezza

Feature space

spigola

oratayi etichette

3

Sistema di classificazione

x1 = [3, 12]

feature extraction

dati pre-processati

oggetto sconosciuto

Altezza

lunghezza

Modelli

testing

categoria: spigola

4

Sistema di classificazione Il fuoco è sul sistema di decisione:

un sistema che ci permette di dire, dato un oggetto in ingresso, a quale classe l’oggetto appartiene

un sistema che “classifica” l’oggetto: un classificatore

Dato un oggetto x, un classificatore è una funzione f che ritorna un valore y discreto (una delle possibili categorie/classi)

Differente dalla regressione (y continuo)

y=f x

5

Sistema di classificazioneGoal: stimare la funzione f

Requisito: si vuole trovare una funzione f che “sbagli” il meno possibile (ridurre gli errori che può fare un sistema di decisione)nel senso dell’errore di generalizzazione

Errore: un oggetto appartiene alla classe 1 e viene classificato come appartenente alla classe 2

6

Sistema di classificazioneTeorie della decisione: come costruire il classificatore

Ce ne sono diverse, caratterizzate da:come vengono espresse/caratterizzate le entità in gioco

come viene determinata la regola di decisione

come possono essere interpretate le soluzioni

Esempi:Teoria di Bayes: approccio probabilistico

Statistical Learning Theory: approccio geometrico

Non c’è una chiara separazione tra le teorie

Teoria della decisione di Bayes

8

La teoria della decisione di Bayes

Rev. Thomas Bayes, F.R.S (1702-1761)

9

IntroduzioneApproccio probabilistico di classificazione di pattern

Molto utilizzato

Molti i risultati teorici dimostrati

Ipotesi: Il problema di decisione è posto in termini probabilistici;

Tutte le probabilità rilevanti sono conosciute;

Goal:Discriminare tra le diverse classi (determinare le regole di

decisione) usando tali probabilità

10

IntroduzioneDEFINIZIONE: Sia ω la categoria o la classe (“lo stato di

natura”) da descrivere probabilisticamente;

ω assume un valore diverso per ogni classeω=ω1 --> prima classe,

ω=ω2 --> seconda classe,

ω=ω3 --> terza classe

...

La regola di classificazione (o regola di decisione) mi permette di rispondere alla seguente domanda:

“Dato un oggetto x, lo assegno a ω1, a ω2 oppure a ω3?” In altre parole: “A quale classe deve essere assegnato?”

Introduzione

Teoria della decisione di Bayes: il problema di decisione è posto in termini probabilistici

Ci sono diverse probabilità che si possono utilizzare per costruire la regola di decisioneOgnuna porta ad una regola di decisione diversa

In particolare:Probabilità a priori: regola della probabilità a priori

Probabilità condizionale: regola Maximum Likelihood

Probabilità a posteriori: regola di Bayes

Vediamole con un esempio...

12

Esempio

ESEMPIO guida: Discriminare tra un calciatore professionista e il resto del mondo sulla base dello stipendiox = stipendio (pattern da classificare)

ω1 = calciatore professionista (classe 1)

ω2 = resto del mondo (classe 2)

13

Probabilità a prioriPrima possibilità: utilizzare solo l'eventuale informazione

a priori che si ha sul problema:“la probabilità che una persona sia un calciatore professionista è

molto bassa (1%)”

Regola di decisione:

Data una persona x da classificare: sapendo che il 99% delle persone sono “non calciatori”, la classifico come

“non calciatore”

Viene utilizzata la “Probabilità a PRIORI”

14

Probabilità a prioriProbabilità a priori:

probabilità P(ω): rappresenta la probabilità dello stato nota a priori (senza aver osservato nulla del sistema)

Probabilità derivanti da conoscenze “esterne”

Esempio calciatore: P(ω= ω1) = 0.01, P(ω= ω2) = 0.99

Regola di decisione della Probabilità a PRIORI:

decidi ω1 se P(ω1) > P(ω2); altrimenti decidi ω2

Ovviamente è un sistema limitato: Non tiene minimamente conto delle osservazioni (indipendente da x)

Esempio calciatore:Ogni pattern x (stipendio) è sempre classificato come “resto del mondo”

15

Probabilità condizionaleSeconda possibilità: utilizzare dei modelli per gli stipendi

delle persone all'interno delle due classiE' presente un training set con cui si costruisce un modello per gli

stipendi dei calciatori

Si ripete la stessa operazione sugli stipendi dei “non calciatori”

Regola di decisione:

Data una persona da classificare: se il suo stipendio x è spiegato meglio dal modello della classe “non

calciatore”allora lo assegno alla classe “non calciatore”, altrimenti il contrario

Modello per x in una classe → PROBABILITA' CONDIZIONALE

16

Probabilità condizionalesia x una misurazione del sistema

x è una variabile aleatoria dipendente da ωj

La probabilità condizionale (o likelihood) è definita come P(x|ωj)misura la probabilità di avere la misurazione x sapendo che lo

stato di natura (la classe) è ωj

17

Regola basata sulla probabilità condizionale

La regola si basa sulla seguente osservazione ragionevole: fissata la misurazione x, più è alta p(x|ωj) più è probabile che ωj sia la classe giusta

Regola di decisione (maximum likelihood):

dato x, decidi ω1 se p(x|ω1) > p(x|ω2), ω2 altrimenti

Migliore della regola basata sulla probabilità a priori perché qui si considera l'osservazione

E' vero che è sicuramente migliore della regola della probabilità a priori … MA si basa solo sull'osservazione!!

Esempio calciatore: non si tiene in conto del fatto che pochissime persone sono calciatori professionisti

SOLUZIONE: Regola di Bayes: utilizza la probabilità a posteriori, che

mette assieme probabilità a priori e probabilità condizionale

Regola di decisione di Bayes IDEA: Prendere la decisione su una persona tenendo

conto sia del fatto che ci sono pochi calciatori (probabilità a priori) sia guardando quanto il suo stipendio x è spiegato dal modello delle classi (probabilità condizionale)

Si utilizza la PROBABILITA' A POSTERIORIProbabilità che mette assieme probabilità a priori e probabilità

condizionale

La probabilità a posteriori si ricava dalle probabilità precedenti attraverso il teorema di bayes:

Teorema di Bayes:

Probabilità a posteriori

Probabilità a piori

Probabilità condizionale

Evidenza: fattore di scala che garantisce che

21

Regola di decisione di Bayes

Regola di decisione di Bayes:

dato x, decidi ω1 se p(ω1|x) > p(ω2|x), ω2 altrimenti

NOTA IMPORTANTE: Si può dimostrare che la regola di decisione di Bayes minimizza la probabilità di errore

Pω j∣x =p x∣ω j P ω j

p x posterior=

likelihood×priorevidence

22

Regola di decisione di Bayes

Regola di decisione equivalente:

l’evidenza rappresenta un fattore di scala che descrive quanto frequentemente si osserva un pattern x

non dipende da ω1 o da ω2, quindi è ininfluente per la regola di

decisione

regola di decisione equivalente:

Regola di decisione di Bayes (versione 2):

Decidi ω1 se p(x|ω1)P(ω1)> p(x|ω2)P(ω2), ω2 altrimenti

23

In pratica?

Problema principale: le probabilità non sono note, come si fa a costruire il classificatore?

Soluzione: apprendimento da esempi

Si utilizza un training set per effettuare una “stima” delle probabilitàDate le probabilità si può fare “classificazione” con la regola di

Bayes

Stima delle probabilitàDiversi approcci:

Stime parametriche: si conosce la forma della pdf, se ne vogliono stimare i parametri esempio gaussiana, stimo la media

Stime non parametriche: non si assume nota la forma, la pdf è stimata direttamente dai datiesempio istogramma

Stime semi-parametriche: ibrido tra le due – i parametri possono cambiare la forma della funzioneesempio Neural Networks

Estensione della teoria di decisione di Bayes

Regola base

Può essere estesa a diversi casi...

Regola di decisione di Bayes:dato x, decidi ω1 se p(ω1|x) > p(ω2|x), ω2 altrimenti

Caso 1: Il pattern è composto da più features

Le probabilità sono definite su spazi multidimensionaliEsempio: due features, gaussiana con media a 2 dimensioni


Caso 2: Ci sono più di due classi

Per ogni classe si può calcolare la probabilità a posteriori

La regola di decisione non cambia e dice di assegnare un oggetto alla classe la cui probabilità a posteriori è massima

Pω j∣x =p x∣ω j P ω j

p x

class x =arg max j Pω j∣x


Caso 3: Si può anche rigettare la classificazioneUn pattern x non viene classificato (non c'è abbastanza

confidenza nella risposta)

Chow's rule: rigettare una classificazione se

ovviamente la scelta di T è cruciale

max j Pω j∣x T


Approcci alla classificazione

30

Per rappresentare un classificatore spesso si utilizza un

insieme di funzioni discriminanti gi(x), i=1...c

Il classificatore assegna l'oggetto x alla classe i se

gi(x) > gj(x) per ogni j i

Questo insieme di funzioni suddivide lo spazio delle features in Regioni, separate tra di loro da Confini di

decisione (decision boundaries)

Funzioni discriminanti e superfici di separazione

Regione R1 (tutti i punti che

verrebbero classificati come appartenenti alla classe 1)

Punti x per cui g1(x) > g

2(x)

Regione R2 (tutti i punti che

verrebbero classificati come appartenenti alla classe 2)

punti x per cui g2(x) > g

1(x)

Confine di decisionePunti x per cui g

1(x) = g

2(x)

32

Un classificatore che utilizza la regola di decisione di Bayes si presta facilmente a questa rappresentazione:

Assegnare x alla classe la cui g(x) è massima equivale ad assegnare x alla classe la cui posterior è massima (REGOLA DI DECISIONE DI BAYES)


g j(x )=P(ω j∣x )=p( x∣ω j)P(ω j)

p ( x )

33


Nota: le posterior non sono note, occorre stimarle!!

Per stimare le posterior si possono o non si possono utilizzare la likelihood e il prior

Approcci:Approcci generativi: si calcolano likelihood e priorApprocci discriminativi: si calcola direttamente le

posterior

Nota: si potrebbe anche evitare di calcolare direttamente le posterior, stimando direttamente il confine di decisione!!


Esempio: nel caso a due categorie ho due funzioni discriminanti, g1(x),g2(x) per cui assegno x a 1 se

g1(x) > g2(x)

Posso anche definire una sola funzione discriminante g(x) = g1(x)-g2(x), e classificare quando g(x) > 0

(g1(x)-g2(x)>0, o g1(x)>g2(x))

L’obiettivo diventa quindi quello di stimare direttamente g(x), la funzione che mi permette di separare le due classiPosso cioè stimare direttamente il confine di decisione!

35

Approcci alla classificazioneRIASSUNTO:

Per la classificazione, la regola che minimizza la probabilità di errore è quella di Bayes (assegnare un oggetto alla classe la cui posterior è maggiore)

La regola utilizza le posterior (che non sono note)

Per stimare le posterior si possono o non si possono utilizzare la likelihood e il prior

Approcci:Approcci generativi: si calcolano likelihood e prior

Approcci discriminativi: si calcola direttamente le posterior e il corrispondente confine di decisione

si può anche stimare direttamente il confine di decisione

36


y=argmax y P y∣x

Generativi: un modello per ogni classe

Discriminativi: modellano direttamente il confine

y=sign w⋅xb

37


Gli approcci discriminativi mirano a risolvere direttamente il problema di classificazione (quindi spesso sono più efficaci)

Gli approcci generativi mirano a modellare tutte le classi del problema (quindi spesso sono più descrittivi)

38

Approcci generativi

Parentesi: la densità normale

40

La densità normaleUna delle più importanti densità

è la densità normale o Gaussiana multivariata; infatti:è analiticamente trattabile;

più importante, fornisce la migliore modellazione di problemi sia teorici che pratici

il teorema del Limite Centrale asserisce che “sotto varie condizioni, la distribuzione della somma di d variabili aleatorie indipendenti tende ad un limite particolare conosciuto

come distribuzione normale”.

41

La densità normale univariata

Completamente specificata da due parametri, media μ e varianza σ2,

si indica con N(μ, σ2) e si presenta nella forma

p x =1

2π σexp {−1

2 x−μσ 2

}

μ=E [ x ]=∫−∞

∞

xp x dx

σ 2=E [ x−μ 2 ]=∫

−∞

∞

x−μ 2 p x dx

42

Densità normale multivariataLa generica densità normale multivariata a d dimensioni

si presenta nella forma

p x =1

2π d /2∣Σ∣1/2exp {−1

2 x−μ T Σ−1 x−μ }

d=1 d=2

43

Densità normale multivariata

Parametri della densità:

vettore di media a d componenti

matrice d x d di covarianza, dove

|| = determinante della matrice

-1 = matrice inversa

σ ij=Ε[ x i−μi x j−μ j ]

Σ=Ε[ x−μ x−μ t ]=∫ x−μ x−μ t p x dx

44

Densità normale multivariataCaratteristiche della matrice di covarianzaSimmetricaSemidefinita positiva (|| 0) ii= varianza di xi ( = i2 ) ij= covarianza tra xi e xj

se xi e xj sono statisticamente indipendenti ij= 0p(x) è il prodotto della densità univariata per x

componente per componente.

45

Densità normale multivariataLa forma della matrice di covarianza porta a diverse

distribuzioni normali

1>2 2>2

46

Approccio generativo

Si stimano le probabilità a priori e le probabilità condizionali

Si combinano a formare le probabilità a posteriori

Si classifica con la regola di Bayes

47

Stima delle probabilitàProblema: le probabilità sono sconosciute, occorre stimarle

dal training set!

Stime parametriche: si conosce la forma della pdf, se ne vogliono stimare i parametri esempio gaussiana, stimo la media

Stime non parametriche: non si assume nessuna forma per la pdf, ma viene stimata direttamente dai datiesempio istogramma

48

Stima parametricaPer costruire un classificatore bayesiano con stima parametrica si procede in questo modo:

Si stima dal training set la probabilità a priori per ogni classe

Per la probabilità condizionale:Si decide (o si stima) la forma per ogni classe (ad esempio gaussiana)

Si stimano i parametri a partire dai dati di training (un insieme di parametri per ogni classe)

Si usano le stime risultanti come se fossero i valori veri e si utilizza la teoria di decisione Bayesiana per costruire il classificatore

49

Stima dei parametri – Probabilità a priori

Stima della probabilità a priori: più facile

Si ha a disposizione il training set: un insieme di n dati di training in cui ad ogni pattern xj è assegnata un’etichetta

Allora si può stimare p(i) come

dove ni è il numero di campioni con etichetta i

Pωi =n in

50

La stima della prob. condizionale rappresenta il vero problema!!

L'obiettivo è stimare i parametri sconosciuti della funzione conosciuta p(x|ωj)

Per es., stimare il vettore sapendo che

Esiste anche un caso più difficile: si vuole stimare sia la forma che i parametri della funzione sconosciuta p(x|ωj)

p x∣ω j ≈N μ j , Σ j

θ j=μ j , Σ j

Stima della probabilità condizionale

51

Stima dei parametri – Probabilità condizionale

Il training set T può essere diviso in sottoinsiemi

T1,T2,...,TC (uno per ogni classe)

Assunzioni che si fanno

Tj contiene campioni generati dalla probabilità p(x|j)

I campioni appartenenti al set Ti non danno informazioni relative

ai parametri di p(x|j) se ij.

52

Stima dei parametri – Due approcci

Essendo i diversi Tj indipendenti, basta trovare la soluzione al seguente problema (da applicare poi a tutti i Tj)

Dato un set di dati di training D={x1, x2, ...., xn} (estratti indipendentemente), si vuole stimare il parametro (che determina in maniera univoca p(x|)) a partire da D

è un vettore che rappresenta i parametri necessari a descrivere in modo univoco p(x|)

p.e., se

Esistono due approcci (non vediamo I dettagli) Stima Maximum-likelihood (ML) Stima di Bayes

θ=μ ,Σ p x∣ω ≈N μ , Σ

53

Stima non parametricaProblema della stima parametrica: si assume che la forma

delle densità di probabilità sia nota, ma questa assunzione non può essere fatta in molti problemi di riconoscimento.

In particolare, se la scelta della forma parametrica è sbagliata, la stima sarà molto poveraEsempio: distribuzione multimodale che viene assunta essere

Gaussiana

Soluzione: metodi non parametrici: fanno poche assunzioni (nessuna) sulla forma della pdf da stimare

54

Stima non parametrica Idea: stimare la pdf andando ad analizzare le singole

regioni dello spazio

Se bisogna stimare p(x=x0), si va a considerare la regione attorno ad x0 e si effettua la stima a partire da quella regione

Si può ripetere per tutti i punti dello spazio (o per tutti i punti di interesse)

55

Stima non parametrica

56

Teorema generale della stima non parametrica

Obiettivo: stimare la probabilità p(x) in una regione R dati N punti campionati da p(x)

Si fa in due passi: 1. Calcolare la probabilità che un punto appartenga alla regione R2. Legare questa probabilità alla dimensione di R

57

PASSO 1.

Sia x0 un punto generato con la probabilità p(x)

Si definisce P come la probabilità che il punto x0 appartenga alla regione.

Teorema: Dati N punti generati con la probabilità p(x), sia K il numero di punti che cadono in R. Allora K/N è uno stimatore corretto e consistente di P.

il valor medio dello stimatore è proprio P (“in media si fa giusto”)

Al crescere di N l'incertezza sulla stima diventa 0

58

PASSO 2.

Se i) p(x) è continua e ii) p(x) non varia molto all'interno della regione R, allora possiamo scrivere

Dove V è il volume della regione R e x0 è un qualsiasi punto interno alla regione

Mettendo assieme:

59

Stima non parametricaDue possibilità per determinare p(x) per ogni possibile x

1. (più intuitiva): si fissa la regione R centrata in x (in particolare si fissa il suo volume V), si calcola K dai dati e si stima p(x) più punti ci sono nel volume fissato V, più alta la probabilità

Esempio: Parzen Windows

2. (meno intuitiva): si fissa K, si sceglie R in modo tale che contenga K punti attorno ad x, si determina V e si stima p(x) più grande è la regione che devo considerare per trovare K

punti, più bassa è la probabilità

60

Classificatore che utilizza il secondo metodo per stimare

non parametricamente p(x0)

si fissa K, si sceglie R in modo tale che contenga K punti

attorno ad x0, si determina V e si stima p(x0)

il classificatore K-Nearest Neighbor stima le probabilità condizionali con questo sistema non parametrico e applica la regola di decisione di Bayes

p x ≈KNV

Il classificatore K-Nearest Neighbor

61

Il classificatore K-Nearest Neighbor

Il classificatore K-NN funziona nel seguente modo: sia X un insieme di esempi etichettati (il training set, ogni punto

ha la sua classe)

dato un punto x0 da classificare, si calcola l’insieme U dei K punti

dell’insieme X più vicini ad x0 secondo una determinata metrica

Si calcola la classe Cj più frequente all’interno dell’insieme U

Si assegna x0 a Cj

Nota importante: il K-nearest neighbor rappresenta un classificatore che implementa la regola di decisione di Bayes dove le probabilità a posteriori sono stimate in modo generativo (likelihood e prior) e in modo non parametrico!

62

K-Nearest NeighborVANTAGGI

tecnica semplice e flessibile

tecnica intuitiva (assume che punti della stessa classe abbiano probabilmente caratteristiche simili, cioè una distanza bassa)

tecnica che funziona anche per dati non vettoriali (basta avere una misura di distanza appropriata)

ragionevolmente accurata (il confine di separazione è comunque non lineare)

ci sono pochi parametri da aggiustare

sono stati dimostrati molti risultati teorici su questa tecnica (asintoticità del comportamento, bounds)

63

Confine di decisione di1-Nearest Neighbor

Problema di classificazione difficile!

64

K-Nearest NeighborSVANTAGGI

Tutti i punti del training set devono essere mantenuti in memoria

vengono utilizzati solo pochi punti dello spazio per prendere la decisione (solo K punti)

dipendentemente dalla metrica utilizzata, occorre pre-processare lo spazio

Serve una misura di distanza buona

La scelta di K spesso è cruciale (K = 1 Nearest Neighbor rule)

scelta tipica Nk

65

K-Nearest Neighbor: note finali

Determinazione di K troppo piccolo si hanno stime troppo rumorose

troppo grande si hanno stime troppo grezze

Metodo per stimare K:crossvalidation sul training set (o su un altro insieme chiamato

Validation Set)

si provano diversi valori e si tiene quello che funziona meglio

Metodi locali: si decide guardando la regione dove si sta operando (ad esempio guardando il K che funziona meglio

localmente)

66


Condensing/Editing: metodi per ridurre la dimensionalità del training set (che deve essere mantenuto in memoria)

Condensing: rimuovere dal training set tutti quei punti che non hanno effetto sul confine di decisione

67


Editing: rimuovere dal training set tutti i punti che non vengono classificati correttamente dall’algoritmo

PROBLEMA DI QUESTI DUE METODI:

così facendo non siamo sicuri di aver eliminano tutti gli errori (i punti eliminati potrebbero essere cruciali per la classificazione

di altri punti non presenti nel training set)

Riconoscimento e recupero dell’informazione per bioinformatica · Data una persona da...

Documents

Transcript of Riconoscimento e recupero dell’informazione per bioinformatica · Data una persona da...