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