Post on 05-Apr-2015
transcript
23.10.2002 FB Mathematik, Universität Bielefeld 1
Strukturverarbeitende Neuronale Netze
Barbara Hammer,
AG LNM, Universität Osnabrück
23.10.2002 FB Mathematik, Universität Bielefeld 2
Überblick
1. Einige Probleme aus der Bioinformatik
2. Lösungsansätze mithilfe neuronaler Netze
3. Mathematische Fragen beim Training
4. Lernbarkeit rekursiver Netzarchitekturen
5. Generell …
23.10.2002 FB Mathematik, Universität Bielefeld 3
Einige Probleme aus der Bioinformatik …
23.10.2002 FB Mathematik, Universität Bielefeld 4
Mehl
WasserZucker
Backhefe
??
23.10.2002 FB Mathematik, Universität Bielefeld 5
…TCGACTCCGTATTCGAC…
ACGCCUAGU…CUAGUCUU
DNA
RNA-Polymerase
… bindet an Promoter.Transkription: die DNA wird komplementär kopiert, …
…Introns werden abgespalten…
…und die mRNA verläßt den Zellkern.
23.10.2002 FB Mathematik, Universität Bielefeld 6
Translation: Ribosomen bilden Codons auf Aminosäuren ab, ...
…UCACAGAGAGGUUUCCCUCACAGAGGGUUU…
Ser Gln Arg Gly Phe Pro His Arg Gly Cys...das Protein faltet sich zu einer 3D Struktur…
.. und steuert komplexe Prozesse.
23.10.2002 FB Mathematik, Universität Bielefeld 7
Einige Probleme
… S.Cerevisiae ist seit 4/96 sequenziert (http://genome-www.stanford.edu/Saccharomyces)
Welche Abschnitte der DNA kodieren? Promoter, Exon/Intron
Wie falten sich die Aminosäuren? Sekundärstruktur, 3D-Struktur der Proteine
23.10.2002 FB Mathematik, Universität Bielefeld 8
Lösungsansätze mithilfe neuronaler Netze …
23.10.2002 FB Mathematik, Universität Bielefeld 9
Ein Neuron
w1
w2
wn
…θ
x1
x2
xn
σ(wtx - θ)
σ(t) = sgd(t) = (1+e-t)-1
σ(t) = H(t) mit
H(t) = 0 für t≤0 H(t) = 1 für t>0
23.10.2002 FB Mathematik, Universität Bielefeld 10
Vorwärtsgerichtete neuronale Netze (FNN)…
fw :ℝn ℝo
x y
23.10.2002 FB Mathematik, Universität Bielefeld 11
… und deren Training …
Ziel: unbekanntes f:ℝn ℝo ist zu lernen
Beispiele f(x1),…,f(xm) sind verfügbar
Training:
1. Auswahl einer Netzarchitektur { fw | wℝW }
2. Optimieren der Gewichte w durch Minimieren des Fehlers ∑ (f(xi) - fw(xi)) 2 auf den Trainingsdaten
3. Bewerten des Ergebnis durch den Fehler auf einer nicht zum Training benutzten Validierungsmenge
fw ≈ f
23.10.2002 FB Mathematik, Universität Bielefeld 12
… zum Erkennen von Spleißstellen
… …Exon ExonIntron… G U … … A G …
(0,0,0,1;0,0,1,0 ;0,1,0,0 ;0,0,0,1)
1 0
0 0aus [Pertea,Lin,Salzberg,Nucleid Acid Research 29(5):1185-1190, 2001]
Beispielergebnisse (missed Pos/false Pos in %):
NetGene2: 6.4/4.6, 6.0/2.5 [Brunak et al.]0 1
(1,0)
d.h. f: ℝ4k ℝ2 ist zu lernen
23.10.2002 FB Mathematik, Universität Bielefeld 13
Partiell rekurrente Netze (RNN)…
Eingab
eK
ontext
Ausgabe
f:ℝn+cℝc
g:ℝcℝo
mit frec:(ℝn)*ℝc alsfrec([ ])=0frec([x|a])=f(x,frec(a))
g◦frec:(ℝn)*ℝo
Sequenzen über ℝn
23.10.2002 FB Mathematik, Universität Bielefeld 14
… und deren Training …
Ziel: unbekanntes f:(ℝn)*ℝo ist zu lernen Beispiele f(x1),…,f(xm) sind verfügbar
Training:1. Auswahl einer Netzarchitektur
2. Optimieren der Gewichte durch Minimieren des Fehlers auf den Trainingsdaten
3. Bewerten des Ergebnis durch den Fehler auf einer nicht zum Training benutzten Validierungsmenge
23.10.2002 FB Mathematik, Universität Bielefeld 15
… zur Prognose der Sekundärstruktur von Proteinen
…SerGlnArgGlyPheProHisArgGlyCys…
α-helix
β-sheet
γ-coil
…α α β β β β β β β γ…
00000010..
01000000..
00010000..
…
010
d.h. f: Aminosäuren* {α,β,γ} ist zu lernen
23.10.2002 FB Mathematik, Universität Bielefeld 16
… zur Prognose der Sekundärstruktur von Proteinen
…SerGlnArgGlyPheProHisArgGlyCys…
PDBx1 x2 x3 x4 x5 x6 x7 x8 x9 x10
EVA(3/3/2001)-Daten: 77.67% [Pollastri,Przybylski,Rost,Baldi,PROTEINS 47:228-235,2002]
vgl.: PROF1 76.8%, PHDpsi 74.7%
23.10.2002 FB Mathematik, Universität Bielefeld 17
Rekursive Netze (RekNN)…
Ein
.K
ont.
Ausgabe
Kont
.
f:ℝn+2cℝc
g:ℝcℝo
mit frec:(ℝn)2*ℝc als
frec(ξ) = 0frec(a(l,r)) = f(a,frec(l),frec(r))
g◦frec:(ℝn)2*ℝo
gerichtete azyklische Graphen
über ℝn mit einem Startknoten
und fan-out ≤ 2
23.10.2002 FB Mathematik, Universität Bielefeld 18
… und deren Training …
Ziel: unbekanntes f:(ℝn)2*ℝo ist zu lernen Beispiele f(x1),…,f(xm) sind verfügbar Training:1. Auswahl einer Netzarchitektur2. Optimieren der Gewichte durch Minimieren des
Fehlers auf den Trainingsdaten3. Bewerten des Ergebnis durch den Fehler auf einer
nicht zum Training benutzten Validierungsmenge ... nebenbei: rekursive Netze unterscheiden nicht
zwischen Bäumen und Graphen
23.10.2002 FB Mathematik, Universität Bielefeld 19
… zur Prognose von Kontakten
x1x2x3x4x5x6x7x8x9x10…
x1x
2x3x
4x5x
6x7x
8x9x
10…
(x2,x3)
0
1 0 0 0 0 0 0 0 0 0 …0 1 0 0 0 0 0 0 1 1 …0 0 1 0 0 0 0 0 1 0 …0 0 0 1 0 0 0 0 0 0 …0 0 0 0 1 1 0 0 0 0 …0 0 0 0 1 1 1 0 0 0 …0 0 0 0 0 1 1 1 0 0 …0 0 0 0 0 0 1 1 1 0 …0 1 1 0 0 0 0 1 1 1 …0 1 0 0 0 0 0 0 1 1 …
x1x
2x3x
4x5x
6x7x
8x9x
10…
x1x2x3x4x5x6x7x8x9x10…
(x2,x2)
(x1,x1)
(x1,x2)
(x1,x3)(x2,x1)
d.h. f: (Aminosäuren2)2* {0,1} ist zu lernen
23.10.2002 FB Mathematik, Universität Bielefeld 20
… zur Prognose von Kontaktenx1x2x3x4x5x6x7x8x9x10…
PDB
SSProX1X2X3…
X1X
2X3
……
[Pollastri,Baldi,Vullo,Frasconi, NIPS2002]
PDBselect:(Ct,nCt,dist.truePos)
6Ǻ: 0.71,0.998,0.59
12Ǻ: 0.43,0.987,0.55
23.10.2002 FB Mathematik, Universität Bielefeld 21
Mathematische Fragen beim Training …
23.10.2002 FB Mathematik, Universität Bielefeld 22
Training - Architekturauswahl
f: Xℝo ist zu lernen, gegeben f(x1),…,f(xm)
1. Architekturauswahl f ≫ ε
z.z. Approximationsvollständigkeit: Für jede (sinnvolle) Funktion f und jedes ε>0 gibt es ein Netz, daß f bis auf ε (in geeigneter Norm) approximiert
23.10.2002 FB Mathematik, Universität Bielefeld 23
Approximationsergebnisse
FNNs/RNNs [Hornik,Stinchcombe,White; Funahashi,Nakamura]: … können jede stetige Funktion beliebig gut auf Kompakta und
endlichem Zeithorizont bzgl. L1 approximieren (σ:squashing)
RekNNs für Baumstrukturen [Hammer]: … können jede stetige Funktion beliebig gut auf Kompakta und
begrenzter Höhe bzgl. L1 approximieren (σ:squashing)
… können jede endliche Menge {f(x1),…,f(xm)} mit O(m2) Neuronen exakt interpolieren (σ:squashing, C2 in Umgebung von x mit σ‘‘(x)≠0)
... können nicht jede Funktion f:{1}2*{0,1} approximieren (bei realistischer Aktivierungsfunktion)
23.10.2002 FB Mathematik, Universität Bielefeld 24
Training - Fehlerminimierung
f:Xℝo ist zu lernen, gegeben f(x1),…,f(xm)
1. Architekturauswahl
2. Fehlerminimierung
Komplexität des Trainings: gegeben eine Architektur {fw|w} und eine Trainingsmenge, finde Parameter w so daß fw(xi) möglichst gut mit f(xi) übereinstimmt
E(w)w
23.10.2002 FB Mathematik, Universität Bielefeld 25
Komplexitätsergebnisse
Für feste Architektur mit Aktivierungsfunktion H: … Training ist polynomiell
Für variable FNN-Architekturen mit Aktivierungsfunktion H:
… optimale Parameter zu finden ist NP-hart [Judd]
… sogar für Architekturen {(n,2,1)|nℕ} [Blum,Rivest]
… sogar für Architekturen {(n,n1>1,n2,…,1)|nℕ} [Hammer]
… sogar für logistische Aktivierungsfunktion statt H [Jones;Vu;Hammer]
… sogar, wenn man nur approximative Lösungen sucht [Bartlett,Ben-
David;DasGupta,Hammer]
23.10.2002 FB Mathematik, Universität Bielefeld 26
Training - Validierung
f:Xℝo ist zu lernen, gegeben f(x1),…,f(xm)
1. Architekturauswahl
2. Fehlerminimierung
3. Validierung
TATATATATATATATATATATATATATATATA
Trainingsfehler = Validierungsfehler
TATATATATATATATA CTACCACAGATATATSCCHRIII 12335ff
<<
T
?
23.10.2002 FB Mathematik, Universität Bielefeld 27
Lernbarkeit rekursiver Netzarchitekturen …
23.10.2002 FB Mathematik, Universität Bielefeld 28
Lernszenario
unbekannte Funktion f ℱ sei zu lernen (alles sei meßbar)
Funktionenklasse ℱ = { g:(ℝn)2* {0,1} | g } sei fest gewählt
P℘ unbekannte Verteilung auf (ℝn)2* für die Daten
(x,f) = ((x1,f(x1)),…,(xm,f(xm))) mit x1,…,xm i.i.d. gemäß P
h: Um((ℝn)2*x {0,1})m ℱ, (x,f) hm(x,f)
hm(x,f) ≈ f für genügend große m
Lernalgorithmus:
23.10.2002 FB Mathematik, Universität Bielefeld 29
Lernszenario
dP(f,g) = |f(x)-g(x)| dP(x) dm(f,g,x) = i |f(xi)-g(xi)| / m
• h ist PAC (probably approximately correct):⇔
∀ℇ>0 supf ℱ Pm(x | dP(f,hm(x,f)) > ) ℇ 0 (m∞) „h generalisiert mit von der zu lernenden Funktion unabhängigen Schranken“
• ℱ ist UCED (uniform convergence of empirical distances):⇔
∀ℇ>0 Pm(x | f,g∃ |dℱ P(f,g)-dm(f,g,x)| > ) ℇ 0 (m∞)
„genau die Algorithmen mit kleinem Trainingsfehler sind gut“
• ℱ ist PAC lernbar :⇔ h: ∃ h PAC „es gibt einen guten Algorithmus“
23.10.2002 FB Mathematik, Universität Bielefeld 30
Lernszenario
• h ist verteilungsunabhängig PAC :⇔
∀ℇ>0 supp℘supfℱPm(x|dP(f,hm(x,f))> ) ℇ 0 (m∞)
• ℱ ist verteilungsunabhängig UCED:⇔
∀ℇ>0 supp℘Pm(x| f,g∃ |dℱ P(f,g)-dm(f,g,x)|> ) ℇ 0 (m∞)
• ℱ ist verteilungsunabhängig PAC lernbar :⇔
∃h: h verteilungsunabhängig PAC
23.10.2002 FB Mathematik, Universität Bielefeld 31
ℱ PAC
ℱ vert.unabh. PAC
ℱ vert.unabh. UCED
ℱ UCED
VC( ) < ℱ ∞
~VC(ℱ) Beispiele
VC(ℱ) := max mℕ{∞} x∃ 1,…,xm d:{x∀ 1,…,xm} {0,1} ∃f : f|{xℱ 1,…,xm} = d
„maximale Anzahl von Punkten, auf denen jede mögliche Abbildung durch ℱ realisiert werden kann“
23.10.2002 FB Mathematik, Universität Bielefeld 32
VC(ℱ|Xt) = O(W·N+W·ln W+W·t) σ=H
O(W2N222t) σ=sgd
Ω(W·ln W+W·t) σ=H
Ω(W·t2+W·ln W) σ=sgd
VC Dimension rekursiver Architekturen
ℱ rekursive Netzarchitektur mit W Gewichten, N Neuronen
Xt (⊂ ℝn)2* Bäume der Maximalhöhe t
23.10.2002 FB Mathematik, Universität Bielefeld 33
ℱ PAC
ℱ vert.unabh. PAC
ℱ vert.unabh. UCED
ℱ UCED
„für allgemeine rekursive Netzarchitekturen kann es keine von der Verteilung unabhängigen a priori Schranken für den Generalisierungsfehler geben“
Überdeckungszahl N( ,X,d)ℇ := minimale Anzahl Punkte, um X bis auf bzgl. ℇd zu überdecken
limm∞Ex(log N( , |ℇ ℱ x,dm))/m0
Fehlerwahrsch.UCED ≤ Ex(N( /16, |ℇ ℱ x,d2m)2)
exp(-mℇ2/32)
23.10.2002 FB Mathematik, Universität Bielefeld 34
UCED für rekursive Architekturen
Sei pt:=P(Xt). Seien ,ℇ δ>0. Gelte pT≥1- /8. Dann istℇ
Pm(x | f,g∃ ℱ |dP(f,g)-dm(f,g,x)| > ) ℇ ≤ δ
für m = O(ℇ-2δ-1 + VC( |Xℱ T)·ℇ-2ln(ℇ-1ln ℇ-1))
23.10.2002 FB Mathematik, Universität Bielefeld 35
ℱ PAC
ℱ vert.unabh. PAC
ℱ vert.unabh. UCED
ℱ UCED
~VC( |Xℱ T) für pT≥1- /8ℇ
polynomiell, falls für ein β>0, c>0 gilt 1-pt<c·t-β, σ=H bzw.1-pt<c·2-2βt, σ=sgd
„jeder Algorithmus mit kleinem Fehler generalisiert, die Schranken hängen von der Verteilung ab“
Aber: es gibt Beispiele, wo jeder Algorithmus für gute Generalisierung exponentiell viele Trainingsmuster benötigt.
23.10.2002 FB Mathematik, Universität Bielefeld 36
Lernbarkeit rekursiver Architekturen
… die VC Dimension hängt von den Eingaben ab, der Validierungsfehler kann nicht a priori unabhängig von der Verteilung abgeschätzt werden.
… jeder Algorithmus mit kleinem Trainingsfehler generalisiert, die Schranken hängen von der Verteilung ab.
... a posteriori Schranken für beliebigen Lernalgorithmus h:
inff Pm(x| |dm(f,hm(x,f),x)-dP(f,hm(x,f))| < (ℇ x)) >1-δ für
ℇ2(x) = O(m-1log δ-1log m + d·m-1log(m·log m)), d=VC(ℱ|XT), T
max.Höhe in x
… bzw. (ℇ x) = O(β + (β·log β-1+ log m(m-1log δ-1)0.5 + d·m-1log(m/β·log m/β))0.5), d=VC(ℱ|XT), T max.Höhe von Anteil (1-β) von x
… analoge Ergebnisse gelten für Funktionenklassen und allgemeinere (z.B. Lipschitz-stetige) Fehlerfunktionen
… verteilungsunabhängig UCED kann in speziellen Situationen gelten, z.B. für rekurrente Netze mit Kontraktion
… man kann nach dem Training den Fehler abschätzen, wenn man die Maximalhöhe in der Trainingsmenge kennt
… sogar mit Schranken, die wirklich gegen Null gehen
… auch für die wirklich relevanten Szenarien geht‘s …
[Hammer] bzw. [Hammer,Tino]
23.10.2002 FB Mathematik, Universität Bielefeld 37
Generell …
23.10.2002 FB Mathematik, Universität Bielefeld 38
Backpropagation-Netze für StrukturdatenAnwendungen – z.B.Bioinformatik, Simulation biologischer Prozesse
Selbst-organisierende Verfahren
Theorie – z.B.Lernbarkeit, Komplexität, Approximation
TODO: Verbesserte Trainingsalgorithmen mit Gütegarantien
TODO: Theoretische Unter- suchung und Qualitäts-kriterien, Verbesserung und Anwendungen
Kooperationen: USA, Indien,
England
Kooperationen: England, Bielefeld
GRLVQ für technische Sys-teme, Bildverarbeitung, … SOMs mit Rekurrenz
Kooperationen: USA, Leipzig,Prognost,Italien
Theorie – uniforme Formulierung, Kostenfunktion, induzierte Metrik, Topologieerhaltung
Kooperationen: Leipzig, Italien
SV
M, R
ein
forcem
en
tlearn
ing, Le
rne
n von
He
uristiken z.B
. für O
R
23.10.2002 FB Mathematik, Universität Bielefeld 39
ENDE!
23.10.2002 FB Mathematik, Universität Bielefeld 40
23.10.2002 FB Mathematik, Universität Bielefeld 41
VC Dimension rekursiver ArchitekturenVC(ℱ|Xt) = Ω(W·ln W+W·t) für σ=H
00001111
00110011
01010101
t-1
si+(2,4,6,…,2t)
frek mit f(x,c1,c2)=
(c1 c∨ 2 x∨ [0.5+2j,1.5+2j])
fw(m,x,c1,c2)=
(f(x,c1,c2) (m=w))∧
w
FNN für W·ln W
∨
…
Bew:
23.10.2002 FB Mathematik, Universität Bielefeld 42
UCED für rekursive Architekturen
Sei pt:=P(Xt). Seien ,ℇ δ>0. Gelte pT≥1- /8. Dann istℇ
Pm(x | f,g∃ ℱ |dP(f,g)-dm(f,g,x)| > ) ℇ ≤ δ
für m = O(ℇ-2δ-1 + VC( |Xℱ T)·ℇ-2ln(ℇ-1ln ℇ-1))
Bew: Pm(x | f,g∃ ℱ |dP(f,g)-dm(f,g,x)| > )ℇ
≤ Pm(x | <m‘ Punkte aus x in XT)) m‘:=m(1- /4)ℇ+ P‘m‘(x‘ | f,g∃ |Xℱ T |dP‘(f,g)-dm‘(f,g,x‘)| > /4ℇ ))
P‘:=P|XTℇ/4 ℇ/2
≤ pt(1-pt)/(m‘ℇ2) + 2Ex‘(2N( /64, |ℇ ℱ x‘,d2m‘)2)exp(-m‘ℇ2/512)
≤ pt(1-pt)/(m‘ℇ2) + 4(256 e/ℇ·ln(256 e/ ))ℇ dexp(-m‘ℇ2/512)
d=VC( |Xℱ T)