10.12.2003Antrittsvorlesung1 Neuronale Netze für strukturierte Daten Antrittsvorlesung zur Habilation, Barbara Hammer, AG LNM, Universität Osnabrück

10.12.2003 Antrittsvorlesung 1

Neuronale Netze für strukturierte Daten

Antrittsvorlesung zur Habilation,Barbara Hammer,

AG LNM, Universität Osnabrück


Vekto

r


Übersicht

1. Lernende Vektorquantisierung und Relevanzlernen

LVQ RLVQ Anwendungen Large margin

2. Weitere Ansätze


Lernende Vektorquantisierung und Relevanzlernen …


LVQ …


Lernende Vektorquantisierung und Relevanzlernen - LVQ

Kohonen



Lernende Vektorquantisierung (LVQ) [Kohonen]:

überwachtes selbstorganisierendes Klassifikationsverfahren

Netz gegeben durch Prototypen (wi,c(wi)) ∈ ℝn x {1,…,m}

Hebbsches Lernen anhand von Beispieldaten (xi,c(xi))

Klassifikation ℝn x ∋ c(wj) {1..m} ∈mit |x-wj| minimal

i.e.ziehe xi und adaptiere den Gewinner wj:

wj := wj ± η·(xi-wj)



Beispiel: unterscheide Äpfel von Birnen

Repräsentation als Vektor ( Øx/Øy , Härte ) in ℝ2

x1

x2



Problem: LVQ basiert auf der Euklidischen Metrik. Probleme bei vielen und unterschiedlich relevanten Dimensionen



Dramatisches Beispiel dieses Problems:



Dieses tritt insbesondere bei als Vektor kodierten komplexen Strukturen auf.

(mittlere Anzahl Nachbarn,

minimale Anzahl Nachbarn,

maximal Anzahl Nachbarn,

Anzahl von gegebenen Subgraphen,

topologische Indizes,

...

Farbe der Knoten)



Kohonen, wenn er diesen Vortrag hören würde…


RLVQ …


Relevanzlernen: ersetze die Euklidische Metrik durch eine Metrik mit adaptiven Relevanzfaktoren

adaptiere die Relevanzfaktoren durch Hebbsches Lernen:

Lernende Vektorquantisierung und Relevanzlernen - RLVQ

n

l lll

n

l ll xwxw 1

2

1

2

10 ll,

sonst

korrektfalls

xwxwlll

lll

l 2

2

Relevanz LVQ

normiere l


Generalisiertes RLVQ – adaptive Relevanzfaktoren in GLVQ, Adaptation als stochastischer Gradientenabstieg


iii

ii

xdxd

xdxdsgd

minimiere

gewichteter quadratischer Abstand zum nächsten korrekten/falschen Prototypen

wxsgdw

i

xdxd

xdii

i

2'

wxsgdwi

xdxd

xdii

i

2'

xdxd

wxxd

xdxd

wxxdii

i

l

i

ii

i

l

i

lll

sgd

22

22

'



Wir bzw. Kohonen, wenn er‘s wüßte …


Anwendungen …


Lernende Vektorquantisierung und Relevanzlernen - Anwendungen

Erkennung von Fehlzuständen bei KolbenmaschinenPROGNOSTPROGNOST



Detektion aufgrund hochdimensionaler und heterogener Daten:

Sensoren liefern zeitabhängige Daten:

Druck, Oszillation, ...

Prozeß Charakteristika,

Merkmale des pV Diagramms,

…

Sensorik



Typische Datenlage: 30 Zeitreihen mit je 36 Einträgen 20 Analysewerte über ein Zeitintervall 40 globale Merkmale15 Klassen, 100 Trainingsmuster

Maschine LVQ Experten-LVQ GRLVQ

1, Train

Test

69.6 (64.8-71.9)

66.7 (65.3-69.8)

91.6 (89.1-92.4)

81.6 (75.2-83.4)

98.2 (96.3-100)

97.2 (93.5-100)

2, Train

Test

72.3 (68.4-74.3)

65.3 (62.5-67.2)

92.1 (88.3-97.2)

84.5 (74.2-86.3)

99.1 (98.4-100)

97.7 (97.6-100)



… Prognost


Prognose von Splice-Stellen:


branch site

A64G73G100T100G62A68G84T63

18-40 bp pyrimidines, i.e. T,C

C65A100G100

Kopie der DNA

donor acceptor

nein ja

ATCGATCGATCGATCGATCGATCGATCGAGTCAATGACC

reading frames


IPsplice (UCI): menschliche DNA, 3 Klassen, ca.3200 Punkte, Fenstergröße 60, alt

C.elegans (Sonneburg et al.): nur acceptor/decoys, 1000/10000 Trainingspunkte, 10000 Testpunkte, Fenstergröße 50, decoys liegen nahe an acceptors

GRLVQ mit wenigen Prototypen (8 / 5 pro Klasse) geänderte Metrik: LIK


i

llj jijiji yxyxd

2,

lokale Korrelationen



GRLVQ HMM SVM-LIK SVM-TOP SVM-FK BRAIN BP LIN ID3

96.5 94 96.3 94.6 94.7 87 78.3 62.3 66.6

IPsplice:





GRLVQ HMM SVM-LIK SVM-TOP SVM-FK

1000 95.2 97.2 94.8 95.4 96.5

10000 95.7 97.4 96.1 97.7 97.5

C.elegans:

... GRLVQ erlaubt kom-pakte Modelle, Aufwand linear in Bezug auf die Trainingsdaten



… die Biologen


Large margin …


Lernende Vektorquantisierung und Relevanzlernen – large margin

F := durch GRLVQ mit p Prototypen berechnete binäre Klassifikationen

(xi,yi)i=1..m Trainingsdaten, i.i.d. gemäß Pm f in F

Ziel: EP(f) := P(y≠f(x)) soll klein sein

Lernalgo.


Ziel: EP(f) := P(y≠f(x)) soll klein sein

Lerntheorie: EP(f) ≤ |{ i | yi≠f(xi)}| + strukturelles Risiko

Für GRLVQ gilt:

EP(f) ≤ |{ i | yi ≠ f(xi)}| + Ʃ0<Mf(xi)<ρ(1-Mf(xi)/ρ) + O(p2(B3+(ln 1/δ)1/2)/(ρm1/2))

wobei Mf(xi) := - dλ+(xi) + dλ

-(xi) der margin ist (= Sicherheit)

dimensionsunabhängige large-margin Schranke!

GRLVQ optimiert den margin:


empirischer Fehler wird im Training optimiertwie sicher legen m Trainingsdaten die Funktion fest

Trainingsfehler Punkte mit zu kleinem marginSchranke in Abhängigkeit von

m = Anzahl Daten

p = Anzahl Prototypen, B = Träger,

δ = Konfidenz

ρ = margin

iii

ii

xdxd

xdxdsgd



Wir


Weitere Ansätze …


Weitere Ansätze

Rekursive Verarbeitung von beliebig langen Sequenzen reeller Vektoren

…GC

TA


Weitere Ansätze

Rekursive Verarbeitung von Bäumen und DPAGs: gerichtete positionierte azyklische Graphen mit beschränkter Anzahl Nachfolger/Vorgänger und einem Wurzelknoten

a

b e

ha

d


Weitere Ansätze

Ich


Weitere Ansätze


Weitere Ansätze GRLVQ +Schriftzeichenerkennung

Satellitendaten

Zeitreihenprognose

Kernelisierung

Neural Gas

Regelextraktion

Rekurrente Netze

SVM

Rekursive Netze

Komplexität Lernbarkeit

SOM, Datamining

.. und weitere Nullmengen


os

Marc Strickert

Kai Gersmann

OR-Gruppe

Theo.Inf.

BieleLeipzig

Rheine

Thorsten Bojer

Prognost

BirminghamPeter Tino

Thomas VillmannHouston

Padua

Hyderabad

Pisa

Alessio MicheliAlessandro Sperduti Matukumalli

Vidyasagar

Berlin

Illinois

Erzsebeth

Merenyi

Bhaskar

DasGupta

Gatersleben

Brijnesh Jain

Jochen Steil

Helge Ritter

Tina

Udo Seiffert


Documents

10.12.2003Antrittsvorlesung1 Neuronale Netze für strukturierte Daten Antrittsvorlesung zur Habilation, Barbara Hammer, AG LNM, Universität Osnabrück