Entscheidungsbaum-LernenPerzeptron-Lernen
Einfuhrung in die Angewandte InformatikIV: Gedachtnis und Lernen
Ute Schmid
Fakultat WIAI, Otto-Friedrich Universitat Bamberg
Angewandte Informatik/Kognitive Systeme
Letzte Anderung 6. Mai 2014
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Erinnerung: Kognitive Systeme
Intelligente Computer- oder Roboterprogramme
Wissensreprasentation und -verarbeitung basiert auf ahnlichenPrinzipien wie menschliche Kognition
Berucksichtigung psychologischer Theorien und empirischerBefunde
Intelligente Systeme basieren nicht auf einfachenReiz-Reaktions-Schaltungen sondern erlauben flexible undadaptive Informationsverarbeitung
ProblemlosenLernen
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Das Modale Gedachtnis-Modell
(Atkinson & Shiffrin, 1968)
...
Zerfall Vergessen
Arbeitsgedächtnis Langzeitgedächtnis
Input aus der
Umwelt
Output der
Antwort
visuellauditorischhaptisch
Zentrale Exekutive
Subsysteme:
deklaratives Systemepisodisches Wissensemantisches Wissen
perzeptuelles Wissenprozedurales Wissen
Sensorisches Register
phonologische Schleifevisuo−spatiales Systemepisodischer Buffer
Nicht−deklaratives System
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Sensorisches Register
Zerfallszeit ca. 1 sec.
Virtuell unbeschrankte Speicherkapazitat
Keine Organisation von Information (“ikonographischesGedachtnis”)
Sperlings “span of apprehension” Experimente
Demonstration der Existenz eines sensorischen SpeichersBestimmung von dessen EigenschaftenInsbesondere: Beschrankte Menge von Information, die (seriell)in den Arbeitsspeicher ubertragen werden kannNicht ubetragene Information verfallt
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Sperling Experimente
(1) Tachistokopische Darbietung von 12 Buchstaben (3 Zeilena 4)
Bericht, dass 12 Buchstaben gesehen wurdengenannt werden konnten nur 3-4 bevor die Gedachtnisspurverblasste
(2) Zusatzlich Ton, der auf die relevante Zeile verweist (hoch,mittel, tief)
Variation der Zeitspanne zwischen Buchstabendarbietung undHinweisreizBei 0 sec. Verzogerung: alle 4 Buchstaben der Reihe genannt;bei Verzogerung (onset) von 1 sec. verschlechtert sich Recallauf 1-2 Buchstaben
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arbeitsgedachtnis
Fruher auch “Kurzzeitspeicher”; Arbeits-Gedachtnis betontdie aktive, aufgabenbezogene Funktion
Akustische oder visuelle Organisation
Speicherzeit: 20-30 sec.
Durch Wiederholung (phonological loop) kann Information imArbeitsgedachtnis bleiben
Beschrankte SpeicherkapazitatFlaschenhals des Gedachtnisprozesses (Miller: 7 plus/minus 2chunks)
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Langzeitgedachtnis
Ohne neurologische Erkrankung oder Verletzungen: im Prinzippermanente Speicherung
Virtuell unbeschrankte Gedachtniskapazitat
Semantische/chronologische Organisation
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Semantisches Gedachtnis
Allgemeines (generisches) Wissen (kulturabhangig) uber dieBedeutung von Konzepten, ihre Eigenschaften (Attribute) undBeziehungen
Apfel sind rot, Ein Hund ist ein Saugetier, Vogel legen Eier
Im Gegensatz zu episodischem/fallbasierten Wissen uberkonkrete Erfahrungen (mit kontextueller Information: Zeit,Ort)
Mein Hund Lassie ist 7 Jahre alt, Mein Bruder lebt in London
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Hierarchische Gedachtnisorganisation
Der TLC von Collins und Quinlan (1969)
Merkmalsvererbung (Kognitive Okonomie)
Reaktionszeitexperimente: Beurteilung vonEigenschaftszuordnungen
Probleme: Typikalitatseffekte, Ausnahmen
Beispiel fur regelbasierte Ansatze zur Begriffsdefinition
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Intelligente Systeme
Wissensbasierte Systeme
Wissen und Regeln durch Menschen modelliertAllgemeine Mechanismen: Ziehen von Schlussen,Ahnlichkeitsvergleich, ...
Lernende Systeme
Wissen und Regeln werden aus Beispielen erworbenLernalgorithmen
If an expert system – brilliantly designed, engineered andimplemented – cannot learn not to repeat its mistakes, it is not asintelligent as a worm or a sea anemone or a kitten.
(O. Selfridge)
Je flexibler und anpassungsfahiger ein Organismus, desto we-niger verfugt er uber ein fest vorgegebenes Verhaltensinventarund desto mehr muss (lebenslang) gelernt werden!
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens
Auswendiglernen
Vokabeln, geschichtliche/geographische FaktenFrage der guten Gedachtnisorganisation fur effizienten Abruf inverschiedenen Kontexten
Lernen von Klassifikationregeln
Konzepte: “Hund”, “Primzahl”, “Vorbereitung fur gutenPrufungserfolg”Klassen allgemein: Hunderassen, Zustande einer chemischenAnlageIdentifikation relevanter Merkmalskombinationen zurVorhersage der Zugehorigkeit eines Objekts zu einer Klasse
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens
Auswendiglernen
Vokabeln, geschichtliche/geographische Fakten
Frage der guten Gedachtnisorganisation fur effizienten Abruf inverschiedenen Kontexten
Lernen von Klassifikationregeln
Konzepte: “Hund”, “Primzahl”, “Vorbereitung fur gutenPrufungserfolg”Klassen allgemein: Hunderassen, Zustande einer chemischenAnlageIdentifikation relevanter Merkmalskombinationen zurVorhersage der Zugehorigkeit eines Objekts zu einer Klasse
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens
Auswendiglernen
Vokabeln, geschichtliche/geographische FaktenFrage der guten Gedachtnisorganisation fur effizienten Abruf inverschiedenen Kontexten
Lernen von Klassifikationregeln
Konzepte: “Hund”, “Primzahl”, “Vorbereitung fur gutenPrufungserfolg”Klassen allgemein: Hunderassen, Zustande einer chemischenAnlageIdentifikation relevanter Merkmalskombinationen zurVorhersage der Zugehorigkeit eines Objekts zu einer Klasse
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens
Auswendiglernen
Vokabeln, geschichtliche/geographische FaktenFrage der guten Gedachtnisorganisation fur effizienten Abruf inverschiedenen Kontexten
Lernen von Klassifikationregeln
Konzepte: “Hund”, “Primzahl”, “Vorbereitung fur gutenPrufungserfolg”Klassen allgemein: Hunderassen, Zustande einer chemischenAnlageIdentifikation relevanter Merkmalskombinationen zurVorhersage der Zugehorigkeit eines Objekts zu einer Klasse
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens
Auswendiglernen
Vokabeln, geschichtliche/geographische FaktenFrage der guten Gedachtnisorganisation fur effizienten Abruf inverschiedenen Kontexten
Lernen von Klassifikationregeln
Konzepte: “Hund”, “Primzahl”, “Vorbereitung fur gutenPrufungserfolg”
Klassen allgemein: Hunderassen, Zustande einer chemischenAnlageIdentifikation relevanter Merkmalskombinationen zurVorhersage der Zugehorigkeit eines Objekts zu einer Klasse
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens
Auswendiglernen
Vokabeln, geschichtliche/geographische FaktenFrage der guten Gedachtnisorganisation fur effizienten Abruf inverschiedenen Kontexten
Lernen von Klassifikationregeln
Konzepte: “Hund”, “Primzahl”, “Vorbereitung fur gutenPrufungserfolg”Klassen allgemein: Hunderassen, Zustande einer chemischenAnlage
Identifikation relevanter Merkmalskombinationen zurVorhersage der Zugehorigkeit eines Objekts zu einer Klasse
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens
Auswendiglernen
Vokabeln, geschichtliche/geographische FaktenFrage der guten Gedachtnisorganisation fur effizienten Abruf inverschiedenen Kontexten
Lernen von Klassifikationregeln
Konzepte: “Hund”, “Primzahl”, “Vorbereitung fur gutenPrufungserfolg”Klassen allgemein: Hunderassen, Zustande einer chemischenAnlageIdentifikation relevanter Merkmalskombinationen zurVorhersage der Zugehorigkeit eines Objekts zu einer Klasse
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens cont.
Auswendiglernen
Lernen von Klassifikationregeln
Lernen von Steuerregeln/Policies/Programmen
Motorische Steuerung (Stab balancieren, Ruckwarts einparken)Prozess-Steuerung (Klaranlage)Handlungsstrategien (Umformen von Gleichungen, Abfolge vonBeweisschritten, Handlungsfolge zur Installation einesRechners)Identifikation von Aktionsfolgen zur Erreichung eines Ziels
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens cont.
Auswendiglernen
Lernen von Klassifikationregeln
Lernen von Steuerregeln/Policies/Programmen
Motorische Steuerung (Stab balancieren, Ruckwarts einparken)Prozess-Steuerung (Klaranlage)Handlungsstrategien (Umformen von Gleichungen, Abfolge vonBeweisschritten, Handlungsfolge zur Installation einesRechners)Identifikation von Aktionsfolgen zur Erreichung eines Ziels
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens cont.
Auswendiglernen
Lernen von Klassifikationregeln
Lernen von Steuerregeln/Policies/Programmen
Motorische Steuerung (Stab balancieren, Ruckwarts einparken)
Prozess-Steuerung (Klaranlage)Handlungsstrategien (Umformen von Gleichungen, Abfolge vonBeweisschritten, Handlungsfolge zur Installation einesRechners)Identifikation von Aktionsfolgen zur Erreichung eines Ziels
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens cont.
Auswendiglernen
Lernen von Klassifikationregeln
Lernen von Steuerregeln/Policies/Programmen
Motorische Steuerung (Stab balancieren, Ruckwarts einparken)Prozess-Steuerung (Klaranlage)
Handlungsstrategien (Umformen von Gleichungen, Abfolge vonBeweisschritten, Handlungsfolge zur Installation einesRechners)Identifikation von Aktionsfolgen zur Erreichung eines Ziels
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens cont.
Auswendiglernen
Lernen von Klassifikationregeln
Lernen von Steuerregeln/Policies/Programmen
Motorische Steuerung (Stab balancieren, Ruckwarts einparken)Prozess-Steuerung (Klaranlage)Handlungsstrategien (Umformen von Gleichungen, Abfolge vonBeweisschritten, Handlungsfolge zur Installation einesRechners)
Identifikation von Aktionsfolgen zur Erreichung eines Ziels
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Arten des Lernens cont.
Auswendiglernen
Lernen von Klassifikationregeln
Lernen von Steuerregeln/Policies/Programmen
Motorische Steuerung (Stab balancieren, Ruckwarts einparken)Prozess-Steuerung (Klaranlage)Handlungsstrategien (Umformen von Gleichungen, Abfolge vonBeweisschritten, Handlungsfolge zur Installation einesRechners)Identifikation von Aktionsfolgen zur Erreichung eines Ziels
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Klassifikationslernen
Beispiel: Lernen eines Konzepts
Objekte der Welt sind (kulturspezifisch) in Konzepte gruppiert
Extensionale Beschreibung: (unendliche)Menge aller Exemplare �
����
�����
�����
�����
� � � � �� � � � �� � � � �� � � � �
Intensionale Beschreibung: endliche CharakterisierungKonzept Tisch ist die Menge aller Objekte, fur die gilt, dasssie 3 oder 4 Beine und eine Platte haben
Lernen: Konstruktion einer intensionalen Beschreibung aus ei-ner endlichen Teilmenge von Exemplaren (Trainingsbeispiele)
Lernen als Induktion
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Klassifikationslernen
Beispiel: Lernen eines Konzepts
Objekte der Welt sind (kulturspezifisch) in Konzepte gruppiert
Extensionale Beschreibung: (unendliche)Menge aller Exemplare �
����
�����
�����
�����
� � � � �� � � � �� � � � �� � � � �
Intensionale Beschreibung: endliche CharakterisierungKonzept Tisch ist die Menge aller Objekte, fur die gilt, dasssie 3 oder 4 Beine und eine Platte haben
Lernen: Konstruktion einer intensionalen Beschreibung aus ei-ner endlichen Teilmenge von Exemplaren (Trainingsbeispiele)
Lernen als Induktion
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Klassifikationslernen
Beispiel: Lernen eines Konzepts
Objekte der Welt sind (kulturspezifisch) in Konzepte gruppiert
Extensionale Beschreibung: (unendliche)Menge aller Exemplare �
����
�����
�����
�����
� � � � �� � � � �� � � � �� � � � �
Intensionale Beschreibung: endliche CharakterisierungKonzept Tisch ist die Menge aller Objekte, fur die gilt, dasssie 3 oder 4 Beine und eine Platte haben
Lernen: Konstruktion einer intensionalen Beschreibung aus ei-ner endlichen Teilmenge von Exemplaren (Trainingsbeispiele)
Lernen als Induktion
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Klassifikationslernen
Beispiel: Lernen eines Konzepts
Objekte der Welt sind (kulturspezifisch) in Konzepte gruppiert
Extensionale Beschreibung: (unendliche)Menge aller Exemplare �
����
�����
�����
�����
� � � � �� � � � �� � � � �� � � � �
Intensionale Beschreibung: endliche CharakterisierungKonzept Tisch ist die Menge aller Objekte, fur die gilt, dasssie 3 oder 4 Beine und eine Platte haben
Lernen: Konstruktion einer intensionalen Beschreibung aus ei-ner endlichen Teilmenge von Exemplaren (Trainingsbeispiele)
Lernen als Induktion
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Klassifikationslernen
Beispiel: Lernen eines Konzepts
Objekte der Welt sind (kulturspezifisch) in Konzepte gruppiert
Extensionale Beschreibung: (unendliche)Menge aller Exemplare �
����
�����
�����
�����
� � � � �� � � � �� � � � �� � � � �
Intensionale Beschreibung: endliche CharakterisierungKonzept Tisch ist die Menge aller Objekte, fur die gilt, dasssie 3 oder 4 Beine und eine Platte haben
Lernen: Konstruktion einer intensionalen Beschreibung aus ei-ner endlichen Teilmenge von Exemplaren (Trainingsbeispiele)
Lernen als Induktion
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Klassifikationslernen
Beispiel: Lernen eines Konzepts
Objekte der Welt sind (kulturspezifisch) in Konzepte gruppiert
Extensionale Beschreibung: (unendliche)Menge aller Exemplare �
����
�����
�����
�����
� � � � �� � � � �� � � � �� � � � �
Intensionale Beschreibung: endliche CharakterisierungKonzept Tisch ist die Menge aller Objekte, fur die gilt, dasssie 3 oder 4 Beine und eine Platte haben
Lernen: Konstruktion einer intensionalen Beschreibung aus ei-ner endlichen Teilmenge von Exemplaren (Trainingsbeispiele)
Lernen als Induktion
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Induktion versus Deduktion
Deduktion
Axiom Alle Menschen sind sterblich.
Fakt Sokrates ist ein Mensch.
Schluss Sokrates ist sterblich!
“Wissensextraktion”
Anwendung einer korrekten Schlussregelhier: modus ponensresultiert in einer korrekten Folgerung
Deduktion: Schließen von Allgemeinem auf Spezielles
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Induktion versus Deduktion
Induktion
Hintergrundwissen Sokrates ist ein Mensch.
Beobachtung Sokrates ist sterblich.
Generalisierung Alle Menschen sind sterblich!
“Wissensgenerierung”
Aus Beobachtungen/Trainingsbeispielenwird eine allgemeinere Regel erzeugt,die hypothetischen Charakter hat
Induktion: Schließen vom Speziellen auf Allgemeines
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Beispiel
Kontext: Expertensystem fur Fernreisen
Ziel: Aussprechen von Impfempfehlungen
Es sei keine genaue Kenntnis vorhanden, wo Tse-Tse-Fliegen(Malaria) vorkommen
Beschreibung von ausgewahlten Regionen, fur die bekannt ist,ob Tse-Tse-Fliege vorkommt durch Merkmale
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Grundbegriffe
Reprasentation von Trainingsbeispielen als Merkmalsvektorenb1 = (0, 0, 1, 1)
Zuordnung der bekannten Klasse 1↪→ Lernen mit Lehrer (uberwachtes Lernen)
Lernalgorithmus: CAL2, ID3, C4.5, ...
Reprasentation der Hypothesen: Entscheidungsbaum
x1 (vegetation)
NO Tse−Tse Fly
0 1 2
NO Tse−Tse FlyNO Tse−Tse Fly Tse−Tse FlyTse−Tse Fly
0 1far from eq.near eq.
0 10x2 (latitude) x2 (latitude)
A B A B
forrestgrassland
wamp
near eq. far from eq.
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
CAL2
1 Starte mit dem Entscheidungsbaum (*) (Klasse
unbekannt).
2 Solange sich noch (fur mind. ein Bsp derTrainingsmenge) Anderungen ergeben:
1 Wenn das neue Objekt korrekt klassifiziert wird,
andere nichts.
2 Wenn das neue Objekt als (*) klassifiziert wird,
trage die Klasse ein.
3 Wenn das neue Objekt falsch klassifiziert wird,
nimm das nachste Merkmal in den Baum hinzu.
Trage fur die entsprechende Auspragung die
aktuelle Klasse ein und fur alle anderen
Auspragungen (*).
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(0):
*
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(1):
A
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(2):
x1
* *
0 21
B
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(3):
x1
*
0 21
B B
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(4):
x1
*
0 21
B B
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(5):
x1
*
0 21
x2
*
0 1
B
A
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(6):
x1
*
0 21
x2
*
0 1
B
A
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(7):
x1
0 21
x2
*
0 1
A B
A
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(8):
x1
0 21
x2
*
0 1
*
x2
0 1
B
B A
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(1):
x1
0 21
x2
*
0 1
x2
0 1
B
A B A
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(2):
x1
0
0 21
x2
*
0 1
1 0
x20 1
1
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation CAL2
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
(3):
x1
0 21
x2
0 1
x2
0 1
B
A B A B
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Kommentare zu CAL2
Inkrementelles Lernverfahren
Termination: in einem Durchlauf durch alle Beispiele keineAnderungen mehr (fur disjunkte Klassen)
Entscheidungsbaum: Menge von Wenn-Dann RegelnWENN (x1 = 0 UND x2 = 0) ODER (x1 = 2 UND x2 = 0)DANN A SONST B
Funktioniert auch fur allgemeines Klassifikationslernen (mehrals 2 Klassen)
Erweiterungen fur
nicht-disjunkte Klassen (statistische Entscheidung)reelwertige Merkmalsauspragungen (automatischeDiskretisierung)
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
ID3
ID3(beispiele, attribute):
1 Erzeuge Knoten mit beispiele
2 WENN alle beispiele positiv, DANN LIEFERE Knoten mit Klasse ‘‘1’’
3 WENN alle beispiele negativ, DANN LIEFERE Knoten mit Klasse ‘‘0’’
4 WENN attribute leer, DANN LIEFERE Knoten mit dem haufigeren
Klassen-Label
5 SONST
1 Wahle Merkmal A aus attribute
2 Weisse A dem Knoten zu3 Fur jeden moglichen Wert vi von A
1 Fuge neuen Pfad fur A = vi unter Knoten ein
2 Setze beispielevi als die Teilmenge von beispiele
mit Wert vi fur A3 WENN beispielevi leer
DANN erzeuge Blattknoten mit dem haufigeren
Klassen-Label
SONST ID3(beispielevi , attribute \A)6 LIEFERE Entscheidungsbaum
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation ID3
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
1(A) 2(B) 3(B) 4(B)
5(A) 6(B) 7(A) 8(B)
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation ID3
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
x1
10 2
1(A) 2(B) 3(B) 4(B)
5(A) 6(B) 7(A) 8(B)
1(A) 7(A)
8(B)
2(B) 6(B) 4(B) 3(B) 5(A)
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Handsimulation ID3
Nr Vegetation (x1) Latitude (x2) Humidity (x3) Altitude (x4) Tse-Tse (Class)1 swamp (0) near eq. (0) high (1) high (1) occurs (A)2 grassland (1) near eq. high low (0) occurs not (B)3 forest (2) far f. eq. (1) low (0) high occurs not4 grassland far f. eq. high high occurs not5 forest near eq. high low occurs6 grassland near eq. low low occurs not7 swamp near eq. low low occurs8 swamp far f. eq. low low occurs not
x1
10 2
x2 x2
0 1 10
1(A) 2(B) 3(B) 4(B)
5(A) 6(B) 7(A) 8(B)
1(A) 7(A)
8(B)
2(B) 6(B) 4(B) 3(B) 5(A)
B
1(A) 7(A) 8(B)
A B
5(A)
A
3(B)
B
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Kommentare zu ID3
Nicht-Inkrementelles (“Batch”) Lernverfahren
Alle Beispiele werden gemeinsam betrachtet und systematischbezuglich der (relevanten) Merkmale unterteilt.
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Kommentare zu EB-Verfahren
Liefern symbolische (verbale) Regeln
Generalisierung: Nur Kombination relevanter Merkmalenicht: Tabelle der Trainingsbeispiele
EB: Klassifikation noch nie gesehener Objekte
Allgemein bei Lernverfahren: ermittelt werden Trainingsfehlerund Generalisierungsfehler (sollte moglichst gering sein)
Evaluation: Zuruckbehalten einer Teilmenge der Beispiele zumTesten
Lernen basiert auf zwei “inductive biases”
Language Bias: Ich kann nur Lernen, was ich in derHypothesensprache reprasentieren kannSearch Bias: Wie bewege ich mich im Hypothesenraum fort(hier von kleinen zu großeren EBs)
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Verkurzung von EBs
Merkmalsreihenfolge bestimmt Komplexitat des gelerntenBaums
Irrelevante Merkmale in hoheren Ebenen bleiben erhalten
Inkrementelles Lernen: Analyse des gelernten Baumes,Umstrukturierung und Loschen irrelevanter Merkmale(Beschneidung im Nachhinein)
Batch-Lernen: Merkmalsauswahl nachinformationstheoretischem Mass
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Beschneidung von EBs
Regel:
αα
αx i Reduce
Beispiel:
x1
Reduce
x1x
x x
0
0 3
2
31 0
1
1
x
x x
0
0 3
2
31 0
1
1
A B A B A B A B
x30 1x
x x
0
0 3
2
31 0
1
1A B
A B A B
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Umstrukturierung von EBs
Regel:
α11 α1k α αl1 lk
xjxj
xi
α11
switch
α α αlk
xj
xi xi
l1 1k
Beispiel:
xj
x i ix
a11 21a a12 a22
j j
a a21
xi
x x
11a 12 a22
switch
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Information Gain
Informationstheoretisches Maß zur Auswahl des nachstenMerkmals
Welches Merkmal reduziert die Unsicherheit, um welcheKlasse es sich handeln konnte am meisten
Idee: Entropie des Gesamtsystems minus relative Entropieeines Merkmals
Merkmal mit hochstem Wert (mit geringster Entropie)auswahlen
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Entropie
H(S) =n∑
i=1
−pi · log2pi
Entropie H eines Systems S
Summe uber Auftretenswahrscheinlichkeiten (relativeHaufigkeiten) mogliche Ereignisse
Logarithmus zur Basis 2: Einheit Bit (ErwarteteEnkodier-Lange)
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Veranschaulichung Entropie
S: Werfen einer Munze pKopf = pZahl = 0.5
H(Muenze) = [−0.5 · log20.5]︸ ︷︷ ︸Kopf
[−0.5 · log20.5]︸ ︷︷ ︸Zahl
= 1 bit
Kodierung mit 1 Bit: 0 (Kopf), 1 (Zahl)
Manipulierte Munze mit 99% Kopf: H = 0.08 bits
Manipulierte Munze mit 100% Kopf: H = 0 bits
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Entropie als Anzahl von Entscheidungsfragen
Anzahl der Entscheidungsfragen bis zur volligen Sicherheit
Raten einer Kartenfarbe: Kreuz, Pik, Herz, KaroHerz
Karo
Kreuz
Pik
Herz?
Kreuz?
Farbe rot?
H(Karte) = 4× [−0.25 · log20.25] = −log20.25 = 2 bit
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Entropie bei der Tse-Tse-Fliege
H(S) = −5
8· log2
5
8− 3
8· log2
3
8≈ 0.95
Ohne Betrachtung eines Merkmals existiert ein leichter Vorteil, sichfur die haufigere Klasse “Tse-Tse Fliege kommt nicht vor” zuentscheiden
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
BeispielGrundbegriffeZwei EB-AlgorithmenMerkmalsauswahl und Entropie
Information Gain eines Merkmals
Gain(S ,A) = H(S)−v∑
i=1
|Sv ||S |· H(Sv )︸ ︷︷ ︸
“relative” Entropy of A
Merkmal x2 “Latitude”H(x2 = 0) = −3
5 · log235 −
25 · log2
25 ≈
−0.6 · −0.74− 0.4 · −1.32 ≈ 0.972H(x2 = 1) = −0
3 · log203 −
33 · log2
33 = 0 · 1 = 0
(Anmerkung: wir setzen 0 · log 0 = 0)Gewichtung: x2 = 0: 5
8 und x2 = 1: 38
Gain(S , x2) = 0.95− [(0.625 · 0.972) + (0.375 · 0)] ≈ 0.34
In verschiedenen Unterbaumen konnen verschiedene Merkmaleden hochsten Gain liefern
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Neuronale Netze
Alternativer Ansatz zum Konzeptlernen: Perzeptron
Idee: Modell einer Nervenzelle
Neuronale Netze allgemein: Verschaltung vieler einfacher“Neurone”
Methode zum Lernen komplexer Funktionen
Achtung: nur wenige neuronale Netze modellieren tatsachlichbiologisches Lernen!
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Modell eines Neurons
Axon spaltet sich auf underreicht Dendriten andererNeurone (Synapse)
Jedes Neuron hatSynapsen mit 10–100.000anderen Neuronen
Transmitter ubertragen Impulse von Synapsen in Dentritenund verandern das elektrische Potential in der Soma.
Falls eine bestimmte Schwelle erreicht wird, wird das Potentialuber das Axon gesendet. (Erregungsfortpflanzung)
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Perzeptron
x 1
x 2
x n
x 0 = 1
1
2
n
0w
w
w
w
Σxwi i
i=0
n
Σ { 1 if > 0
otherwiseo =
xwi ii=0
n
Σ−1
Merkmale spannen euklidischen Raum auf
Jedes Beispiel: Punkt im Merkmalsraum
Lernen der Gewichte wi
so dass positive und negative Beispiele durch eine Trennebene separiertwerden
Schwellenfunktion (o zur Normierung des Outputs)
Klassen werden als −1 und +1 reprasentiert
funktioniert fur linear separierbare Klassen
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Trenngeradex2
x1
1
1
1 1 1
1 1 1
1
1
−1 −1
−1 −1
−1 −1
−1
−1
(−2−1
)· ~x + 3 = 0
Multiplikativer Faktor:Steigung der Geraden
Additiver Faktor:Verschiedbung vomNullpunkt
Klassifikation: Skalarprodukt von Gewichtsvektor undEingabevektordarauf die Schwellenfunktion anwenden
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Perzeptron-Lernalgorithmus
Erweitern des Vektor ~x um Konstante 1 and Stelle x0:Verschiebungsfaktor mit in Gewichtsvektor ziehen.
1 Initialisiere Gewichtsvektor ~w mit 0en2 Solange bis alle Beispiele korrekt klassifiziert
werden oder bis n Iterationen durchlaufen sind,wiederhole:
1 Nimm das nachste Beispiel ~xi2 Berechne o(~xi ) = sgn(~w · ~xi )3 Wenn o(~xi ) = Klasse k(~xi )
Dann weiterSonst
1 Wenn o(~xi ) > k(~xi )Dann ~w := ~w − ~xi
2 Wenn o(~xi ) < k(~xi )Dann ~w := ~w + ~xi
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
0
00
·
100
= 0
Update:
~w :=
0 + 10 + 00 + 0
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
1
00
·
101
= 1 Update: –
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
1
00
·
110
= 1 Update: –
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
1
00
·
111
= 1
Update:
~w :=
1− 10− 10− 1
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
0
−1−1
·
100
= 0
Update:
~w :=
0 + 1−1 + 0−1 + 0
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
1
−1−1
·
101
= 0
Update:
~w :=
1 + 1−1 + 0−1 + 1
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
2
−10
·
110
= 1 Update: –
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
2
−10
·
111
= 1
Update:
~w :=
2− 1−1− 10− 1
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Beispiel Perzeptron
Klassische Anwendung: Lernen logischer Funktionen
Hier: NAND
x1 x2 k(x)
1 0 0 12 0 1 13 1 0 14 1 1 0
Nach 6 Durchlaufen durch die Trai-ningsmenge werden alle Beispiele kor-rekt klassifiziert mit
~w :=
3−2−1
1
−2−1
·
111
= 1
Update:
~w :=
2− 1−1− 10− 1
Ute Schmid Einfuhrung in die Angewandte Informatik
Entscheidungsbaum-LernenPerzeptron-Lernen
Computer und GehirnPerzeptron ArchitekturPerzeptron Algorithmus
Kommentare Perzeptron
Logische Funktion XOR nicht lernbar (nicht mit einerTrenngerade sparierbar)
Verstandnis des Perzeprons liefert Grundlage fur komplexereNetze
z.B. mehrschichtige feedforward Netze (wie Backpropagation)
Ute Schmid Einfuhrung in die Angewandte Informatik