Invatare automata
description
Transcript of Invatare automata
Invatare automata
Universitatea Politehnica BucurestiAnul universitar 2008-2009
Adina Magda Floreahttp://turing.cs.pub.ro/inva_09 si
curs.cs.pub.ro
Curs nr. 1
Continut curs Introducere Invatare inductiva Invatare in spatiul versiunilor Teoria invatarii computationale Invatare prin recopensa Invatare bazata pe FOPL Programare logica inductiva Retele neurale Algoritmi genetici Invatarea in retele Bayesiene
2
Cerinte
Notare Laborator si teme de casa T1-T3 - 30% (10+20) Tema de casa T4 - 20% (se alege tema pana pe 15 martie) Examen final - 50% PlanificareT1 - S2 cu predare in S4T2 - S5 cu predare in S7T3 - S8 cu predare in S10T4 - se publica pe 1 martie, se alege pana pe 15 martie, cu predare in S13
Cerinte pentru promovare Minimum 6 prezente la laborator pentru promovare (in lipsa a 6
prezente cursul si laboratorul se refac in anul universitar urmator) Studentul trebuie sa obtina minim jumatate din punctajul examenului
final pentru promovare
3
1. Definitii
Invatarea este procesul prin care un sistem isi imbunatateste performantele (Herbert Simon).
Invatarea este achizitia cunostintelor explicite;
Invatarea este achizitiaa deprinderilor de rezolvare a problemelor
Invatarea este formare teoriilor, formarea ipotezelor si inferenta inductiva
4
Invatare automata
Machine learning Schimba structura, programul sau BC Schimbarile: imbunatatiri sau de la zero
Perceptie
Model (BC) Rationament
Actiune
5
Invatare automata
De ce sa invete? Taskuri definite prin exemple Relatii / corelatii in cantitati mari de date Mediu in schimbare Date diferite, cu zgomot Cantitate de cunostinte prea mare pentru a fi
reprezentate explicit
6
Invatare automata
Discipline Statistica (esantioane - distributie de
probabilitate) Modele neuronale Teoria controlului (control proces cu
parametrii necunoscuti) Modele psihologice Modele biologice Inteligenta artificiala
7
InvA – Exemple de aAplicatii clasificarea proteinelor corespunzator functiei lor prezice daca pacientul raspunde bine unui
tratament/medicament categorizarea textelor (e.g., filtrare spam) detectia fraudelor OCR detectia fetelor umane in imagini intelegerea limbajului vorbit segmentarea pietii (e.g., daca un client raspunde unei
promotii) descoperirea regulilor de bune practici (tipar) predictia consumului de electricitate sinteza ontologiilor
8
Model simplu – Clasificare 1T = {X1, X2, …, Xm} – multime de invatare
9
x1
x2
.
.xn
hX =
h H
h(X)
f(X) = ?
Invatare supervizata – se cunosc f(X1), …, f(Xm)
Gasim h a.i. h(Xi) = f(Xi), i=1,m h(Xi) = f(Xi), i Invatare ne-supervizata – NU se cunosc f(X1), …, f(Xm)Imparte T in submultimi – claseSe poate vedea tot ca invatarea unei functii – val f = numele
submultimii careia ii apratine Xi
Invatare prin recompensa – Se cunosc recompensele pentru valorile h(X1), …, h(Xm), Nu se cunosc valorle lui f
Denumiri T – vector de intrare, vector sablon, vector de
caracteristici, esantioane, exemple, instante xi- caracteristici, atribute, variabile de intrare,
componente xi - valori reale, valori numerice intregi, valori
simbolice, valori booleene f(Xi)
valori reale: h – functie de esantionare valori simbolice: h – clasificator boolene: 1 – instanta pozitiva, 0 – instanta
negativa
10
Model conceptual – Clasificare 2
Mediul ofera stimuli sau informatie elementului de învatare, care foloseste aceasta informatie pentru a imbunatati cunostintele (explicite) din baza de cunostinte
Aceste cunostinte sunt utilizate de componenta de prelucrare (rezolvare) în rezolvarea problemei
11
12
Sistem de invatare
Element deinvatare
Rezolvare BC
Motor de inferenta Strategie
Evaluareperformante
Rezultate invatare
Rezultate
Mediu
Feed-backProfesor
Feed-back
Date
În functie de diferenta între nivelul informatiei oferite de mediu si cel al informatiei din baza de cunostinte, se pot identifica patru tipuri de invatare invatarea prin memorare invatarea prin instruire invatarea prin inductie (din exemple) invatarea prin analogie
Model conceptual – Clasificare 2
13
Reguli de inferenta utilizate in invatare
La baza procesului de invatare stau o serie de forme inferentiale nevalide: inductia, abductia si analogia
O metoda de învãtare poate folosi una sau mai multe astfel de forme de inferenta, cat si forme de inferenta valide, cum este deductia
14
Inferenta inductiva
O proprietate adevarata pentru o submultime de obiecte dintr-o clasa este adevarata pentru toate obiectele din acea clasa
P(a),P(a ),...,P(a )
( x)P(x)1 2 n
15
Se poate generaliza la sintetizarea unei întregi reguli de deductie pe baza exemplelor
Q(y))(P(x) y)x)((
)Q(b)P(a
)Q(b)P(a
)Q(b)P(a
nn
22
11
Inferenta inductiva
16
Inferenta abductiva
Se utilizeaza cunostinte cauzale pentru a explica sau a justifica o concluzie, posibil invalida
Q(a)( x)(P(x) Q(x))
P(a)
17
Inferenta abductiva
Exemplu Uda(iarba) (x) (PlouaPeste(x) Uda(x)) Se poate infera abductiv ca a plouat Cu toate acestea, abductia nu poate fi aplicata
consistent in oricare caz
18
Inferenta analogica
Situatii sau entitati care tind sa fie asemanatoare sub anumite aspecte sunt asemanatoare în general
Este o combinatie a celorlalte forme de inferenta: abductive, deductive si inductive
(x)Q'(x)P'
Q(x)P(x)r
r
19
Aspecte InvA
Regimuri de invatare: Batch Incremental
Zgomot: zgomot atribute zgomot iesiri (alterare iesiri)
20
Aspecte InvA
Bias (learning bias) Bias = ipoteza de lucru apriori = H se poate
limita apriori la o multime de functii sau ipoteze de invatare
Invatare functie booleana de n intrari: 2n intrari posibile, H este functii boleene
21
n22
BiasT – 6 sabloane de invatare
H – functii liniar separabile
22
x1
x2
x3
1
0
Bias absolut – H este limitat la o multime de functii cunoscute
Bias preferential – H se ordoneaza dupa un anumit criteriu
- se alege h minim
Occam Razor
Principiul lamei lui Occam prefer explicatiile simple celor complexe Wiliam of Occam, 1285 – 1349 (?) filozof englez
"non sunt multiplicanda entia praeter necessitatem"
23
Conditii pentru o invatare "buna"
Problema: identifica caractere "bune" sau "rele" dupa modul in care arata
24
Conditii pentru o invatare "buna"
25
Atribute /
InstanteSex Masca Pelerina Cravata Urechi Lupta Clasa
Set de invatare
Batman Masc Da Da Nu Da Nu Bun
Robin Masc Da Da Nu Nu Nu Bun
Alfred Masc Nu Nu Da Nu Nu Bun
Pinguin Masc Nu Nu Da Nu Da Rau
Catwoman Fem Da Nu Nu Da Nu Rau
Joker Masc Nu Nu Nu Nu Nu Rau
Date de test
Batgirl Fem Da Da Nu Da Nu ??
Fred Masc Da Nu Nu Nu Nu ??
Conditii pentru o invatare "buna"
26
Cravata
Pelerina Lupta
Rau Bun Bun Rau
DaNu
NuNu Da Da
Clasifica datele
Conditii pentru o invatare "buna"
27
Cravata
PelerinaLupta
Bun
Rau
Bun
Rau
DaNu
Nu
NuDa
Da
Masca
Urechi Sex Urechi
Nu
Nu
Nu
Nu
Nu
Da
Da
Da
Pelerina
BunRau
Bun Rau Lupta
Da
Da
Bun Rau
Fem Masc
Clasifica datele dar complexitate prea mare (intuitiv)
Conditii pentru o invatare "buna"
28
Sex
Bun Rau
Masc Fem
Prea simplu, nu clasifica corect
Aleg prima varianta (cf. lamei lui Occam)
Conditii pentru o invatare "buna"
29
Clasificatoarele trebuie sa fie suficient de "expresive" pentru a fi in concordanta cu setul de invatare
Dar clasificatoarele care au o complexitate prea mare pot duce la fenomenul de "overfit" (overfitting) = include zgomot sau sabloane de date nerelevante