Inl. Adaptieve Systemen

Inl. Adaptieve Systemen

Het leren van regels

Inl. Adaptieve Systemen Het leren van regels Gerard Vreeswijk Leerstoelgroep Intelligente Systemen, Departement Informatica en Informatiekunde, Faculteit Bètawetenschappen, Universiteit Utrecht.

Gerard Vreeswijk. Laatst gewijzigd op 15 juni 2011 om 10:54 uur

Slide 1



Inhoud 1. Concepten uit machinaal leren. 2. • Uitputtend algoritme voor het leren van één regel: EGS.

• Heuristisch algoritme voor het leren van één regel: HGS. 3. • Het leren van meerdere regels voor één conclusie.

• Het leren van meerdere regels zonder een vooraf bepaalde doelconclusie: ongesuperviseerd leren.


Slide 2



Motivatie Het leren van regels is o.a. nuttig voor: 1. Sensemaking (ietwat modieuze term). Ongeveer: Het herkennen van regels en patronen in het op het eerste gezicht onoverzichtelijke “berg” gegevens. 2. Het automatisch “vullen” van de rulebase (kennisbank) van zg. (a) Expert systems (ook wel bekend als “rule-based systems”). (b) Argumentatiesystemen. Dit zijn systemen waarmee computers kwalitatief kunnen redeneren op basis van onzekere en/of onvolledige kennis (“ROOK”). http://people.cs.uu.nl/gv/code/AS/index.cgi. 3. Ter vergelijking van Holland’s zg. learning classifier systems (LCS, XCS, ZCS). Gerard Vreeswijk. Laatst gewijzigd op 15 juni 2011 om 10:54 uur

Slide 3



Destilleren van regels uit situatiebeschrijvingen Voorbeeld van een set van situatiebeschrijvingen: Jaar .. .

Gebeurtenissen .. .

2006:

¬New president, DeNiro Movie, Eclipse

2007:

Tour de France, Olympic Games, European Championship Football, New president, DeNiro Movie

2008:

Tour de France, DeNiro Movie

2009:

Tour de France, World Championship Football, DeNiro Movie

2010:

Tour de France, DeNiro Movie

2011:

Olympic Games, Tour de France, European Championship Football, DeNiro Movie .. .

.. .


Slide 4



Abstracte situatiebeschrijvingen Jaar .. .

Gebeurtenissen .. .

2006:

¬ a, b, ¬d, g, ¬ j, ¬k, m

2007:

b, ¬c, d, ¬e, f , h, ¬i, j

2008:

a, c, ¬d, ¬e, f , ¬k, l, ¬m

2009:

a, b, d, ¬ g, h, j, k, ¬m

2010:

¬b, c, e, ¬ f , g, ¬i, ¬ j, n

2011: .. .

a, ¬c, e, ¬ f , ¬k, l, ¬m .. .


Slide 5



Situatiebeschrijvingen in regelformaat Jaar .. .

Gebeurtenissen .. .

2006:

¬ a, b, ¬d, g, ¬ j, ¬k, m

2007:

b, ¬c, d, ¬e, h, ¬i, j >− f

2008:

a, c, ¬d, ¬e, ¬k, l, ¬m >− f

2009:

a, b, d, ¬ g, h, j, k, ¬m

2010:

¬b, c, e, g, ¬i, ¬ j, n >− ¬ f

2011: .. .

a, ¬c, e, ¬k, l, ¬m >− ¬ f .. .


Slide 6



Basisconcepten Machinaal Leren


Slide 7



Basisconcepten machinaal leren Regels leren ⊆ machinaal leren. Beschouw: 1. Instanties: punten in {0, 1, 2, . . . , 100}2 . 2. Mogelijke classificaties: positief (+), negatief (−), of ongedefinieerd. 3. Dataset: deelverzameling van instantieverzameling:

(22, 25) → + (37, 37) → + (85, 78) → −

(76, 54) → − (25, 80) → − (22, 38) → +

(37, 23) → + (34, 75) → − (90, 10) → −

4. Gezocht: criterium om toekomstige instanties te classificeren.


Slide 8



Concepten uit machinaal leren 100

100

−−

75 50

+ + + +

25

− −

−

50

0 25

+ + + +

25

− 0

−−

75

50

75 100

− −

−

−

0 0


25

50

75 100

Slide 9



Concepten uit machinaal leren (II) 100

−−

75 50

+ + + +

25

− −

• Positieve instanties

−

• Negatieve instanties

−

0 0

25

50

Belangrijke concepten: • Dataverzameling (= alle bekende instanties)

75 100

• Instantieruimte (= alle mogelijk denkbare instanties) • Hypothese (hier: gesloten rechthoek) • Hypotheseruimte (= alle mogelijke hypothesen) • Classificatie (hier: + of −)


Slide 10



Concepten uit machinaal leren (III) Belangrijke concepten: • Match van H:

100

−−

75 50

−

+ + + + +

25 0 0

25

−

50

−

correcte classificaties 9 = data-instanties 11

• H is consistent: match = 1

− 75 100

• Bereik van H = mogelijk denkbare instanties gedekt door H ≈ 20 ∗ 30 = 600 punten • Overdekking van H: data in het in het bereik van H (5 punten) • Accuratesse van H: ratio correct geclassificeerde data op bereik van H = 4/5


Slide 11



Netlogo Machine Learning “Lab”


Slide 12



Regels leren


Slide 13



Het leren van één regel: algoritme EGS EGS = exhaustive general-to-specific. Voorbeeld: we willen een regel leren voor d op basis van de volgende vijf casussen: 1.

a, c, b, d

4.

¬ a, ¬b

2.

b, a, d

5.

a, ¬d

3.

b, c, ¬d

i. Positieve instanties: 1 en 2. ii. Negatieve instanties: 3 en 5. iii. Neutrale instantie: 4.

Meest algemene regel voor d: “ → d ”.


Slide 14



Het leren van één regel: specialisatie, stap één 1.

a, c, b, d

4.

¬ a, ¬b

2.

b, a, d

5.

a, ¬d

3.

b, c, ¬d

Specialisatie

Prestatie

Actie

a→d

dekt negatieve instantie nr. 5

specialiseer verder

b→d

dekt negatieve instantie nr. 3

specialiseer verder

c→d

mist positieve instantie nr. 2

verwijder regel

¬a → d


verwijder regel

¬b → d


verwijder regel


Slide 15



Het leren van één regel: specialisatie, stap twee 1.

a, c, b, d

4.

¬ a, ¬b

2.

b, a, d

5.

a, ¬d

3.

b, c, ¬d

Specialisatie a, b → d a, c → d a, ¬b → d

Prestatie perfecte match mist positieve instantie nr. 2 mist positieve instantie nr. 1

Actie behoud regel verwijder regel verwijder regel

Regel “ a, b → d ” is algemeen genoeg gebleven om 1 en 2 af te dekken, maar specifiek genoeg geworden om 3, 4 en 5 te missen. EGS is volledig: het vindt alle meest-algemene hypothesen die consistent zijn met de data. Gerard Vreeswijk. Laatst gewijzigd op 15 juni 2011 om 10:54 uur

Slide 16



Inconsistentie en ruis Diagram 1: inconsistente data.

Diagram 2: ruis (zie element rechtsboven).

100

100

75

75

+ +++ +++++ +++++ +++−+ +++++

50 25 0 0

25

50

+ + +++ +++++ +++++ +++++ +++++

50 25 0 75 100

0


25

50

75 100

Slide 17



Problemen met exhaustive general-to-specific (EGS) 1. Exploreert alle mogelijke specialisaties van regel-antecedenten → combinatorische explosie zoekruimte. 2. Data met ruis → oversized hypothesen. 3. Inconsistente data → helemaal geen hypothesen. 4. Produceert alle consistente hypothesen → meestal willen we alleen de beste(n) . . . . . . of ze nu consistent met de data zijn of niet.


Slide 18



Heuristic general-to-specific (HGS) 1. Uitputtend zoeken is . . . te uitputtend. Alternatief: ga op elk moment verder met de b beste regels. Dit wordt beam-search genoemd, b is de beam-grootte (of wijdte). Collectie van open hypothesen bestaat nu altijd uit b regels. 2. Consistentie als kwaliteitsmaat is te zwart-wit: alleen 0 (inconsistent) of 1 (consistent). Alternatief: pas reëelwaardige kwaliteitsmaat (score) toe, bijvoorbeeld score( H ) =Def match( H ).


Slide 19



→z 0.40 ¬a → z 0.53 ¬ a, b → z 0.57 ...

¬ a, c → z 0.59 ¬ a, c, b → z 0.53 (< 0.59)

...

...

b→z 0.47

STOP

...

c→z 0.71

¬ a, c, ¬b → z 0.57 (< 0.59)

...

Getallen geven regelscore aan. Regelscore kan de match zijn, de accuratesse, of een combinatie van deze twee factoren.

c, a → z 0.83

...

c, a, b → z 0.85

...

...

...

...

c, a, b, ¬e, g → z 0.94 ...


...

c, a, b, ¬e → z 0.89

...

...

c, b → z 0.76

...

Slide 20



Waarom meer dan één regel leren? Best scorende individuele regel. 100

−−−− +++ − +++ − +++ − ++ − +++ − +++ − +++ −−−−

75 50 25 0 0

25

50

75 100

Best scorende regelverzameling. 100

−−−− +++ − +++ − +++ − ++ − +++ − +++ − +++ −−−−

75 50 25 0 0


25

50

75 100

Slide 21



Het leren van regelverzamelingen Pas relatieve kwaliteitsmaat toe, toegespitst op accuratesse: score( H ) =Def accuracy( H ). Probleem: overfitting. Voorbeeld: 1. Gegeven: Onderwijzer tekent aantal punten, ongeveer in rechte lijn. 2. Algemene achterliggende concept: Een rechte lijn. 3. Overfitting: Leerling interpoleert punten met polygoon. Ander voorbeeld: a. Gegeven: Ouder toont drie rode objecten aan 2-jarig kind. b. Algemene achterliggende concept: Rood. c. Overfitting: Kind verwerpt alle andere rode dingen als rood, omdat het denkt dat alleen drie getoonde voorwerpen de eigenschap “roodheid” bezitten. Gerard Vreeswijk. Laatst gewijzigd op 15 juni 2011 om 10:54 uur

Slide 22



Meerdere regels: afweging tussen eenvoud en accuratesse Nauwkeurige maar complexe afdekking.

Eenvoudige maar onnauwkeurige afdekking.


Slide 23



Sequentieel afdekken (sequential covering) Input: P, a list of positive instances Input: N, a list of negative instances Input: SCORE, a subroutine that computes the performance of an elementary hypothesis Input: l, a lower bound for what is acceptable as a score 1: - R := [ ]; 2: while P has elements do 3: - let r be the rule that is produced with HGS with parameters SCORE, P and N 4: - leave the while-loop if accuracy(r ) > l; 5: - put r in R; 6: - remove all members of P that are covered by r; 7: return ( R, P); # P contains all instances not covered by R Met veel scores kan bewezen worden dat P op ’t eind leeg is. Gerard Vreeswijk. Laatst gewijzigd op 15 juni 2011 om 10:54 uur

Slide 24



Parametrizeerbare scorefunctie score( H ) = a ∗ accuracy( H ) + b ∗ range( H ) + c ∗ coverage( H ) a groot

b klein

c klein

klein

groot

klein

klein

klein

groot

geproduceerde regelset overfitting; veel regels met lange antecedenten; veel toekomstige instanties negatief weinig regels; korte regel-antecedenten; veel positieve data niet gedekt weinig regels; groot gedeelte van de data is gedekt


Slide 25



Geloofwaardigheid (DOB) en implicatiesterkte (strength) Notatie: DOB( “x, y −(0.91)→ z” ) = 0.45 Geloofwaardigheid (DOB, hier 0.45) en implicatiesterkte (hier 0.91) worden aangeleverd door geleerde waarden: 1. Geloofwaardigheid door (relatieve) coverage: welk percentage van het bereik van de regel (gegeven door de regel-antecedent) is reeds bekend (is data)? 2. Implicatiesterkte door accuratesse: op welk percentage aan data classificeert regel correct? Tabel: Geloofwaardigheid (DOB) coverage( R)/range( R)

implicatiesterkte accuracy( R)


Slide 26



Ongesuperviseerd leren Ongesuperviseerd leren: het leren van regels zonder dat je vooraf aangeeft naar welke conclusies je zoekt. Input: A, a (high ∼ 0.98) lower bound for rule accuracy 1: - set Rall to [ ]; 2: for each literal L that occurs in the data do 3: - set P, the list of positive instances, for L 4: - set N, the list of negative instances, for L 5: - augment, trough sequential covering, Rall with all rules learned for L, as accurate as A; 6: return Rall ; # all rules are as accurate as A


Slide 27



Andere manieren om regels te leren 1. Batch vs. real-time verwerken van instanties. Ook bekend als off-line vs. on-line, of als incrementeel vs. non-incrementeel verwerken van instanties. Er werd besproken: batch. 2. General-to-specific vs. specific-to-general ontwikkeling van hypothesen. Er werd besproken: {E|H}GS. Een combinatie van beiden (GS + SG) kan ook (vgl. zg. “versieruimten” in machinaal leren). 3. Sequentieel afdekken vs. uitzondering-op-uitzondering. Er werd besproken: sequentieel afdekken. Uitzondering-op-uitzondering: 1e regel is ruwe benadering; 2e regel is correctie op 1e regel; 3e regel is correctie op 2e regel, enzovoort.


Slide 28

Inl. Adaptieve Systemen

Recommend Documents