Apprendimento automatico (machine learning)

Machine learning

Pagani Davide

22 settembre 2016

Indice

• Introduzione 2
• Inductive learning 3
• Concept learning 5
• Find-S e Candidate elimination 6
• Alberi di decisione 9
• Elementi per la costruzione dell'albero 10
• Parametri per guidare la costruzione dell'albero 11
• Vantaggi e svantaggi 12
• PAC 15
• Vapnik-Chervonenkis Dimension 17
• Mistake Bound Model 17
• Mistake Bound Model per find-S 18
• Mistake Bound per Halving 18
• Optimal Mistake Bound 18
• Weighted majority algorithm (WM) 19
• Reti neurali 20
• Percettrone 23
• Apprendimento del percettrone 24
• Teorema di Minsky-Papert e discesa del gradiente 24
• Teorema di convergenza 25
• Reti neurali multistrato e retropropagazione 25
• Apprendimento statistico 27
• Il classificatore Naive Bayes 29
• Support Vector Machines (metodi kernel) 31
• Reinforcement Learning 33
• Processo di decisione di Markov 34
• Apprendimento non supervisionato (Clustering) 37
• Tipi di dati nel Clustering 38
• I metodi di partizionamento 38
• Il metodo di partizionamento k-Means 39

Introduzione

L’idea alla base dell’apprendimento è che le percezioni non dovrebbero essere usate solo per decidere quale azione intraprendere, ma anche per migliorare la capacità futura dell’agente. Migliorare rispetto a una data misura di capacità di esecuzione di un certo compito, attraverso l’esperienza.

Un agente in grado di apprendere contiene un elemento:

• Esecutivo decide quali azioni intraprendere.
• Di apprendimento modifica quello esecutivo in modo che prenda decisioni migliori.

Per descrivere il problema in generale, iniziamo con 3 attributi:

• Task (T) il compito da apprendere (identificare un volto all’interno di un database).
• Performance (P) una misura di bontà su come apprendiamo.
• Experience (E) faccio esperienza.

Posso distinguere tra:

• Learner colui che impara da esempi in modo automatico che può essere un algoritmo o un programma.
• Trainer un modulo che fornisce l’esperienza al learner.

Ricolleghiamoci a task, diversi sono i compiti da apprendere. Solitamente questo fattore è il più importante per determinare la natura del problema di apprendimento affrontato dall’agente.

Possiamo osservare 3 casi:

• Apprendimento supervisionato richiede che si apprenda una funzione partendo da esempi di input e output. Esempio: clustering problem o classification problem se l’outcome è qualitativo mentre regression problem se l’outcome è quantitativo.
• Apprendimento non supervisionato richiede di imparare a riconoscere pattern o schemi nell’input senza alcuna specificazione di valori in uscita.
• Apprendimento per rinforzo è la categoria più generale, in cui l’agente deve apprendere basandosi sul rinforzo.

Un ulteriore fattore fondamentale è la conoscenza pregressa.

Inductive learning

Un algoritmo per l’apprendimento deterministico supervisionato riceve in ingresso il valore corretto di una funzione sconosciuta in alcuni punti e deve cercare di ricostruirla nel modo più fedele possibile. Un esempio è la coppia (x, f(x)) in cui x è l’input e f(x) l’output della funzione applicata a x. Data una collezione di esempi di f, restituire una inferenza induttiva funzione h che approssima f. Con h che prende il nome di ipotesi. Non è facile stabilire se una particolare h è una buona approssimazione di f. Una buona ipotesi si potrà generalizzare bene, il che significa che potrà predire correttamente esempi che non ha incontrato (problema dell’induzione).

Considerando lo spazio delle ipotesi H, che corrisponde a tutte le ipotesi considerate. Graficamente analizziamo una retta che passa per tutti i punti di un polinomio qualsiasi (retta consistente perché si accorda con tutti i dati osservati). Il problema sta nella scelta tra più ipotesi che risultano essere tutte consistenti. Rasoio di Occam preferisco l’ipotesi più semplice (ragionevolmente un polinomio di grado 1 è più semplice rispetto ad un polinomio di grado 12).

Un problema di apprendimento automatico si basa su:

• Formulazione del concetto da apprendere.
• Formulazione della performance.
• Formulazione dell’esperienza.

Vado a collegarmi al capitolo 1 in cui si parlava della performance P, che corrispondeva al secondo attributo dopo task. Performance corrisponde ad una misura che valuta il successo del learner: Il sistema ha appreso oppure sta apprendendo?

Parliamo adesso dell’esperienza E:

• Da cosa impara il sistema? Da osservazioni, da esempi?
• È importante la scelta dell’esperienza, la quale può influire significativamente sul successo dell’apprendimento. L’esperienza è rappresentativa per il compito che il sistema deve svolgere?
• Controllo dell’esperienza da parte del learner: può essere fornita al learner senza che esso possa interagire oppure, il learner può fare domande su esempi che non risultano chiari.

Esperienza diretta: informazioni utili direttamente dagli esempi. Esperienza indiretta: inferire indirettamente l’informazione necessaria. N.B. Non sempre si hanno a disposizione tutti gli esempi.

Classificazione dei metodi di apprendimento:

• Espressioni simboliche (alberi).
• Funzioni di probabilità (BL).
• Funzioni algebriche (SVM).

Classificazione in base all’informazione a disposizione:

• Supervisionato: vengono forniti al learner a priori esempi di comportamento. {S = (x₁, y₁), ..., (x_n, y_n)} per ogni input x_i l’ipotetico trainer fornisce il risultato corretto di y_i.
• Non supervisionato: esperienza rappresentata da esempi non classificati. {S = (x₁), ..., (x_n)} non c’è il trainer che dà le risposte corrette. Un tipico esempio è: il clustering.
• Per rinforzo: il learner interagisce con l’ambiente e riceve una ricompensa positiva o negativa. Si apprende una strategia di comportamento. Cerco di massimizzare la ricompensa "a lungo termine".

Classificazione in base al controllo che il learner ha dell’esperienza:

• Attivo: l’apprendista può fare domande ed esperimenti.
• Passivo: l’apprendista può apprendere solo dai dati messi a disposizione (E).

Concept learning

Definiamo ora l’apprendimento induttivo per il caso in cui l’ipotesi è rappresentata da un insieme di formule logiche. Esempi e classificazioni saranno costituite da formule logiche, considerando ora come nuovo esempio il classificare deducendo una formula di classificazione dall’ipotesi e dalla sua destinazione. È un processo che permette di costruire una formula incrementale delle ipotesi (consente di sfruttare la conoscenza pregressa). Concept learning inferire una funzione a valori booleani da esempi di formazione del suo input e output.

Gli esempi sono descritti mediante attributi come alternativa. Un esempio è un oggetto descritto da una formula logica. Gli attributi corrispondono alle variabili di un dataset. In riga invece osserviamo le istanze, che ci permettono di riferirci alla descrizione di X_i. L’ipotesi h è una congiunzione di vincoli sugli attributi. Ogni vincolo può essere:

• Un valore specifico.
• Un valore non noto, che non importa.
• Nessun valore consentito.

Lo spazio delle ipotesi H è l’insieme di tutte le ipotesi {H₁, ..., H_n} che l’algoritmo di apprendimento è progettato per considerare. Un esempio può essere: per ipotesi se essa predice che dovrebbe essere negativo - falso negativo ma in effetti è positivo. Falso positivo per ipotesi se essa predice che dovrebbe essere positivo ma in effetti è negativo.

Se ho ipotesi consistenti, cioè H_i che è consistente con l’intero insieme di addestramento, allora è consistente con ogni esempio (stessa estensione). Se non è consistente con un esempio, allora ho falso negativo e positivo. Se è falso negativo o falso positivo, allora l’esempio e l’ipotesi sono logicamente inconsistenti. Dato che l’esempio rappresenta l’osservazione corretta di un fatto, allora l’ipotesi può essere scartata.

Posso quindi caratterizzare l’apprendimento induttivo in ambito logico come un processo di eliminazione graduale delle ipotesi inconsistenti con gli esempi, con una progressiva riduzione delle probabilità.

Find-S e Candidate elimination

Descrivo 2 processi che permettono di trovare ipotesi logicamente consistenti con poca fatica:

1. Ricerca mediante migliore ipotesi corrente o find-S (trova l’ipotesi più specifica che è consistente con l’insieme di apprendimento). Supponendo di avere un’ipotesi H a cui siamo abbastanza affezionati, finché ogni nuovo esempio è consistente, allora non dobbiamo fare nulla. Se ho un falso negativo, allora vuol dire che l’ipotesi dice che è negativo ma in realtà è positivo. L’estensione (è un insieme che predice un certo numero di esempi e precisamente quelli che soddisfano la sua definizione candidata) deve quindi essere allargata per includerlo (generalizzazione). Se ho un falso positivo, l’ipotesi dice che è positivo ma in realtà è negativo. L’estensione delle ipotesi deve quindi essere rispettata per escludere tale esempio (specificazione). Ogni volta che generalizziamo o specifichiamo l’ipotesi, dobbiamo verificare la consistenza della nuova ipotesi con gli altri esempi.
2. Un’alternativa è quella di mantenere in memoria tutte e sole le ipotesi che sono consistenti con i dati raccolti fino a qui. Ogni nuova istanza non avrà alcun effetto. Lo spazio delle ipotesi originale si può vedere come una formula disgiuntiva H₁ ∨ H₂ ∨ ... ∨ H_n che si riduce man mano che si trovano ipotesi inconsistenti con gli esempi. Presumo quindi che le ipotesi originarie contengono la risposta corretta. La riduzione dovrà ugualmente contenerla (dato che rimuovo solo le ipotesi errate). L’insieme che rimane è lo spazio delle versioni e l’algoritmo prende il nome di algoritmo di eliminazione dei candidati.

Proprietà:

• Incrementale (non torno indietro a riesaminare i vecchi esempi).
• Ad impegno minimo (non fa scelte arbitrarie).

Svantaggi:

• Spazio delle ipotesi enorme: soluzione sullo spazio delle ipotesi è definito un ordinamento, imposto dalle relazioni di generalizzazione e specificazione.

Vantaggi:

• Posso rappresentare l’intero spazio delle versioni con 2 sottoinsiemi: più generale (G) tutto ciò che si trova in mezzo è consistente, più specifico (S).

Riepilogo:

• Lo spazio delle versioni corrente è l’insieme delle ipotesi consistenti con tutti gli esempi incontrati. È rappresentato per mezzo dell’insieme S e G, ognuno dei quali è costituito da un insieme di ipotesi.
• Ogni elemento dell’insieme S è consistente con tutte le osservazioni effettuate e non esiste un’ipotesi consistente più specifica.
• G non esiste un’ipotesi consistente più generale.

N.B. lo spazio delle versioni voglio che rappresenti tutte le ipotesi possibili. Pongo quindi: G TRUE (l’ipotesi contiene tutto) S FALSE (l’ipotesi la cui estensione è vuota). Per verificare che vale la rappresentazione dello spazio delle versioni G e S devono valere le seguenti proprietà:

• Nessuna ipotesi consistente è esterna all’intervallo.
• Non ci sono buchi tra gli insiemi limitanti.

Ci occupiamo ora degli elementi S e G degli insiemi S e G. Per ognuno di essi l’istanza può essere un falso positivo o un falso negativo:

• Falso positivo per S_i, vuol dire che S_i è troppo generale e quindi lo eliminiamo.
• Falso negativo per S_i, S_i troppo specifico, lo rimpiazziamo con tutte le sue generalizzazioni.
• Falso positivo per G_i, G_i troppo generale, lo rimpiazziamo con tutte le sue specificazioni.
• Falso negativo per G_i, G_i troppo specifico, lo elimino dall’insieme G_i.

Proseguo queste operazioni finché non sono in:

• Spazio delle versioni rimane il concetto (unica ipotesi).
• Spazio delle versioni collassa un insieme tra S e G diventa vuoto.
• Finiscono gli esempi, rimangono diverse ipotesi nello spazio delle versioni.

Alberi di decisione

L’induzione di alberi di decisione è una delle forme di apprendimento più semplice e di maggior successo. Un albero di decisione prende in input un oggetto o una situazione descritta da un insieme di attributi e restituisce una "decisione" (valore predetto). Gli alberi di decisione rappresentano un metodo supervisionato per la costruzione di un modello che mira alla previsione del valore di una variabile di risposta (target) in funzione di un insieme di variabili indipendenti (input). Il modello è strutturato secondo un diagramma ad albero. A seconda della natura della variabile target, gli alberi di decisione sono definiti:

• Alberi di classificazione: la variabile target è qualitativa.
• Alberi di regressione: la variabile target è quantitativa.
• Le variabili in input possono essere sia quantitative che qualitative.

Che cos’è un diagramma ad albero? Un diagramma ad albero è un insieme di nodi collegati tra loro attraverso dei rami, che formano un grafo orientato in senso discendente che parte da un unico nodo radice e termina in una serie di nodi foglia. Partendo dal nodo radice, le osservazioni vengono attribuite ai nodi successivi sulla base di una regola di ripartizione basata sulle variabili input, con l’obiettivo di determinare nodi progressivamente più omogenei rispetto alla variabile target. Ogni ramo conduce ad un nodo successivo che viene ulteriormente ripartito. L’albero di decisione è dunque costruito attraverso una bipartizione ricorsiva delle osservazioni, che vengono suddivise in sottogruppi via via più omogenei internamente. Il criterio di divisione (split) si basa sulle variabili input, mentre il grado di omogeneità interna ai gruppi è misurato sulla variabile target:

• I nodi terminali (o foglia) degli alberi di classificazione sono etichettati da una modalità della variabile di risposta (target) qualitativa.
• I nodi terminali (o foglia) degli alberi di regressione sono etichettati da un intervallo di valori della variabile di risposta (target) quantitativa.

In ottica esplorativa, un albero di decisione si utilizza per descrivere quali sono i valori delle variabili input che determinano intervalli/categorie della variabile target. In ottica decisionale, un albero decisionale si utilizza per predire il valore della variabile di risposta da attribuire ad una osservazione di cui si conoscono i valori delle variabili in input.

Elementi per la costruzione dell’albero

Quali sono gli elementi per la costruzione di un albero decisionale? Per ciascun nodo, valutare l’insieme dei possibili split. Il numero di possibili split dipende dalla natura delle variabili in questione. Se m è il numero di modalità di una variabile qualitativa, ed N il numero di valori di una variabile quantitativa, allora il numero di split per la variabile sarà m-1.