MACHINE LEARNING e DATA MINING Introduzione

MACHINE LEARNING e
DATA MINING
Introduzione
a.a.2015/16
Jessica Rosati
[email protected]
Apprendimento Automatico(i)
Branca dell’ AI che si occupa di realizzare dispositivi artificiali capaci di emulare le modalità di ragionamento che sono tipiche dell’uomo. Per far ciò, tali dispositivi devono essere in grado di apprendere, ovvero di estrarre una conoscenza generale, attraverso forme di ragionamento induttivo, su di un determinato problema esaminando una serie di esempi ad esso relativo.
Apprendimento Automatico(ii)
• Herbert Simon
“Learning is any process by which a system improves performance from experience.”
• Tom Mitchell
“Machine Learning addresses the question of how to build computer programs that improve their performance at some task through experience.”
Well posed learning problem: A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E. Ragionamento Induttivo(i)
L’ apprendere dagli esempi è un caso particolare di Apprendimento Induttivo.
Dato un insieme di esempi, il modulo di apprendimento induce un modello generale capace di descrivere gli esempi visti.
L’ AI classica si basa su forme di ragionamento deduttivo, dove partendo da assiomi generali si arriva a conclusioni specifiche. L’ apprendimento automatico invece si basa su ragionamento induttivo nel quale partendo da esempi specifici si ottengono descrizioni generali.
Machine Learning
• Machine learning studies computer algorithms for learning to do stuff: learning to complete a task, or to make accurate predictions, or to behave intelligently.
• Enfasi su metodi automatici :apprendere senza ulteriore intervento da parte dell’uomo
Esempi d’utilizzo del ML
• Data mining/Knowledge Discovery in Databases:
scoprire regolarità e patterns in dati multi‐
dimensionali e complessi
– Cartelle cliniche  conoscenza medica
– Dati di vendita  strategie di marketing
– Denuncie dei redditi  politiche di verifica fiscale.
• Applicazioni software difficili da programmare
perchè:
• Non esistono esperti umani (es. Analisi DNA)
• Gli umani sanno eseguire un compito, ma non sanno
come (es. comprensione di immagini, speech recognition, handwriting recognition)
Handwrite Recognition
• Impossibile formalizzare il problema: disponibili solo esempi
• Possibile presenza di rumore e dati ambigui
Esempi d’utilizzo del ML
• Self customizing programs: Ogni utente ha esigenze specifiche (es. filtraggio di notizie dal web)
Amazon, Netflix, GoogleNews
Recommender Systems
Classificazione dei problemi di Apprendimento • Supervisionato
• Non Supervisionato
Apprendimento Supervisionato(i)
Data una serie di esempi (training set), dove ogni singolo esempio (istanza del training set) è caratterizzato da un vettore di features (x) ed un output (y), le tecniche supervisionate (algoritmi di classificazione/regressione) si occupano di costruire un modello h(x)
capace di approssimare l’output y (y=f(x)). Questo modello h(x),
appreso durante una fase di addestramento, è un’approssimazione della funzione non nota f(x) (funzione target) che si vuol apprendere.
Da un punto di vista probabilistico si vuol determinare la probabilità condizionata p(y|x).
output numerico  regressione
output qualitativo (classe)  classificazione/pattern recognition Apprendimento Supervisionato(ii)
Training Set
x11 x12 x13 x14 .. x1N y1 x21 x22 x23 x24 .. x2N y2 ….
….
xM1 xM2 xM3 xM4 .. xMN yM
esempioi: (xi, yi = f(xi))
x
input
y
h(x)
output
Data una collezione di esempi (xi, yi = f(xi)), l’induzione si occupa di
restituire una funzione h che approssima f.
La funzione h prende il nome di ipotesi.
Apprendimento Supervisionato(iii)
Training Set
Algoritmo di Apprendimento
x
vettore di features
Ipotesi
h
y
output
Apprendimento Non Supervisionato
A differenza dell’ apprendimento supervisionato non si hanno informazioni sulle classi di appartenenza degli esempi o in generale sull’output corrispondente ad un certo input.
I dati a disposizione riguardano solamente l’insieme delle features
che descrive ogni esempio.
L’ obiettivo è ottenere un modello che sia capace di scoprire proprietà interessanti. Ad esempio gruppi (cluster) di esempi che hanno caratteristiche simili (clustering). O anche una riduzione della dimensionalità delle features (dimensionality reduction).
Apprendimento Supervisionato vs Non Supervisionato
Supervisionato
100
Weight
1.89
90
Class
90
Male
80
1.75
81
Male
1.55
45
Female
1.65
51
Female
Weight
Height
Classificazione
Male
70
Female
60
50
40
0
1
Height
2
3
Non Supervisionato
Height
Weight
100
Cluster1
1.89
90
1.75
81
1.55
45
Weight
90
80
70
Cluster2
60
50
40
1.65
51
0
0,5
1
1,5
Height
2
2,5
Clustering
Perché Apprendere è difficile?
Dato un numero finito di esempi (dimensione finita del training set) vogliamo apprendere un’ipotesi che ha un dominio potenzialmente infinito (l’insieme di addestramento è solo un campione della popolazione), ne segue che c’è un numero infinito di ipotesi possibili. Quale è la migliore?
Problemi dell’ Induzione
Non è assolutamente facile stabilire se una particolare h sia
una buona approssimazione di f.
Una ipotesi h si può ritenere buona se è capace di generalizzare bene, ossia se è in grado di predire correttamente esempi che non ha ancora incontrato (durante l’ addestramento).
Problemi dell’ Induzione: quale ipotesi scegliere?
Problemi dell’ Induzione: quale ipotesi scegliere?
Scegliamo come spazio delle ipotesi H (insieme di tutte le
ipotesi considerate) l’insieme dei polinomi di grado massimo k.
Come facciamo a scegliere tra più ipotesi, tutte consistenti?
Rasoio di Occam: si deve preferire l’ipotesi più semplice consistente con i dati.
Non possiamo definire esattamente la “semplicità” di una ipotesi, ma è ragionevole affermare che, un polinomio di grado 1 sia più semplice di un polinomio di grado 8.
Modelli Discriminativi e Generativi
Discriminativi
Effettuano direttamente una stima della probabilità condizionata
p(y|x) dal training set.
Questi modelli sono detti discriminativi, perchè, a partire dal training set si deriva una caratterizzazione dell’output in funzione delle features. Questa caratterizzazione permette di discriminare, dato un elemento, il più probabile tra i possibili valori dell’output (la classe più verosimile ad esempio).
Es. Logistic Regression, SVMs, Neural Networks
Modelli Discriminativi e Generativi
Generativi
Effettuano una stima della probabilità congiunta p(x,y) dal training set.
Questo approccio è detto generativo, perché viene derivata una caratterizzazione delle features in funzione dell’output, in modo tale da generare, dato un possibile output, un input che con buona probabilità potrà essere associato a quell’output. Per ogni possibile output viene generato un modello (distribuzione di probabilità) degli input associati a quell’output. Le predizioni p(y|x) vengono calcolate applicando la regola di Bayes.
Es. Naive Bayes, Bayesian Networks, Mixtures of Gaussians