Information Retrieval und Vektoriteration - in.tum.de · 2 Vergleich zweier Dokumente auf...

1

Information Retrieval und Vektoriteration: Vektorraummodell für ‚Data Mining‘

Liste von Dokumenten D1 , ... , Dn , z.B. WWW-Seiten Liste von Suchtermen T1 , ... , Tm , z.B. alphabetisch geordnet: Aachen, ABC, Auto, Bar, ... , Zug

Jeder Suchbegriff erscheint in jedem Dokument mit einem Bestimmten Gewicht, z.B. Gewicht ∼ Häufigkeit.

Sammle diese Gewichte in der sog. Term-Dokument-Matrix (dünnbesetzte Matrix). j-ter Spaltenvektor dieser Matrix listet für das j-te Dokument Dj die darin enthaltenen Suchworte ! Vektor dj . k-ter Zeilenvektor tk listet für den k-ten Suchbegriff die relevanten Dokumente auf.

2

Vergleich zweier Dokumente auf Ähnlichkeit: Dokument Di repräsentiert durch Vektor der darin enthaltenen Suchbegriffe di , entsprechend dj .

D1 D2 D3 . . . .T1 . . T2 . .

nahe bei 1.

Vektoren ähnlich (kollinear), wenn Winkel zwischen ihnen sehr klein, d.h.

cos('(di, d j)) =dT

i d j

kdik2 · kd jk2

3

Eine Suchanfrage ist ein Spaltenvektor d und entspricht quasi einem Dokument, das mit anderen Dokumenten auf Ähnlichkeit verglichen werden soll. Berechne Vektor t = dT*D = (dT*D1 dT*D2 ..) . Große Komponenten tj entsprechen Dokumenten Dj , die mit der Suchanfrage am besten übereinstimmen.

di

dj ϕ

Matrix D enthält sehr viel ‚Rauschen’, (zufälliges Auftreten von Suchtermen in Dokumenten, Wortwahl, ...) Modellreduktion: Ersetze D durch System, das die wesentlichen Eigenschaften repräsentiert:

4

!!"

#$$%

&=

22

1211

0 RRR

R

Verbesserung durch Pivotsuche: D*P=Q*R mit allgemeiner QR-Zerlegung incl. Permutation liefert und neues tTTPRQD ⋅⋅= ~:~

Berechne QR-Zerlegung von D : D=QR Partitioniere R in der Form

dabei sei R22 gleich Null oder mit kleinen Einträgen. Dann repräsentieren die Zeilen von R22 ‚linear abhängige’ Such- begriffe, die eigentlich überflüssig sind.

Ddt TT ~⋅= DdT ⋅

( ) ( )121111211

211211

0000:~ RRQ

RRQQ

RRQD ⋅=""

#

$%%&

'=""

#

$%%&

'=

und untersuche anstatt

Ersetze D durch die Approximation kleinen Ranges:

5

Andere Methode des ‚Denoising’ mittels Eigenwerten: Betrachte Singulärwertzerlegung von A: A = U D V, dabei sind U und V Eigenvektormatrizen von ATA und AAT, und D ist eine rechteckige Diagonalmatrix, deren Diagonaleinträge >= 0 sind:

mit Singulärwerten σj >0, Rang(A)=k.

A = U

0BBBBBBBBBBBBB@

�1 0 · · · 0 · · · 0

0. . .

. . ..........

.... . . �k 0 · · · 0

1CCCCCCCCCCCCCA

V

6

D~Ersetze D durch , indem kleine σj durch 0 ersetzt werden.

Ergibt neue Matrix (Term-Dokument-Tabelle)

VDUA ~~ = mit kleinerem Rang:

Diese neue Matrix enthält wieder die wesentliche Information von A . A = UDV heißt Singulärwertzerlegung von A. Und ergibt sich aus der Eigenwert-Zerlegung von ATA, bzw. AAT .

Zusammenfassung

• Newton-Verfahren zur Nullstellenbestimmung / Minimierung • Nichtlineare Ausgleichsrechung • iterative Methoden zum Lösen von lin. Gleichungssystemen • Jacobi- und Gauß-Seidel-Verfahren • Gradientenabstieg und Conjugate Gradient • Vektoriteration • Anwendung: neuronale Netze

7

VII. Numerische Behandlung von Differentialgleichungen

Gewöhnliche Diff’gleichungen (erster Ordnung)

Diff’gleichungsproblem allgemein: Aus Beziehungen zwischen den Änderungen (Ableitungen) und den Funktionswerten soll eine gesuchte Funktion bestimmt werden!

),( xyy ϕ="

Aufgabe: Funktion y(x) nur implizit gegeben durch Bedingungen an die Ableitung y’ ! y ??

! y(x) ?

Ableitung von y(x) nach x in jedem möglichen Punkt (x,y) ist gegeben durch Funktion ϕ(x,y).

Frage: Warum Differentialgleichungen?

9

Beispiel: Freier Fall

Kugel wird aus Höhe h0 losgelassen zum Zeitpunkt t0 = 0 mit Anfangsgeschwindigkeit v0 = 0, Erdbeschleunigung g.

v(t) = s(t) =dsdt,

�g = v(t) =dvdt= s(t) =

d2sdt2 .

Diff’gleichung für v(t): v(t) = '1(v, t) = �g (= ¨s(t))

Integration ! v(t) =Z t

0v(⌧)d⌧ =

Z t

0(�g)d⌧ = �gt

10

Diff’gleichung für s(t):

Aus Anfangswerten t0 = 0 und h0, und aus der Bedingung für die Ableitung wird die Funktion selbst bestimmt.

In dieser einfachen Form explizit lösbar durch Quadratur!

Im Allgemeinen ist das Integral nicht direkt lösbar, oder Diff’gleichung kann nicht auf Integral zurückgeführt werden.

s(t) = '2(s, 1) = v(t) = �gt

Integration ! s(t) = h0 +

Z t

0(�g⌧)d⌧ = h0 �

12

gt2

11

Definition: Anfangswertproblem (AWP)

Aus Anfangswert y(x0 ) = y0 und Differentialgleichung y’(x) = ϕ(y,x) soll die Funktion y(x) für x > x0 bestimmt werden.

Dabei ist die Diff’gleichung hier in expliziter Form gegeben, d.h. in der Form: y’(x) = ...

Impliziter Fall: ϕ(y’,y,x) = 0 ! y ??? ( Beispiel implizit: y’*exp(y’) = y+x )

12

00 )(),()( yxyundyxyxy ===! αϕ

dtydy

dxydy

ydxdy

x

x

xy

xy ∫∫ =

⋅=⇔=

00

)(

)(α

αα

Beispiel für explizit lösbare Diff’gleichung:

Lösung durch Integration (“Separation”, ohne Beweis)

)())(ln())(ln( 00 xxxyxy −=− α

)(0

0)( xxeyxy −= αund daher

13

Geometrische Problemstellung:

Von einer Funktion sind alle möglichen Ableitungswerte an allen möglichen Stellen (x,y) bekannt (also an allen potentiellen Funktionswerten) Dies entspricht einem Vektorfeld von Tangentenrichtungen

Weiterhin bekannt ist der Funktionswert an einer Stelle x0 .

Gesucht: Kurve, deren Tangenten in allen Punkten dem vorgegebenen Vektorfeld entspricht!

14

Die Lösungskurve ist dann die Gerade mit Steigung -g durch den Nullpunkt, also v(t) = -gt .

Im Beispiel ‚Freier Fall’ ist dieses Vektorfeld trivial:

In der (t,v)-Ebene ist jede Tangentenrichtung durch den Vektor (1,v’)T gegeben, also hier durch den Vektor (1,-g)T .

v’=0: Tangentenvektor (1,0)T

Kurve (t,v)"!v(t)

Tangentenvektor (t,v)‘ = (1,v‘)

v(t) = �g, v(t0) = 0

15

00 )(),()( yxyundxyxy ==! ϕ

Das Eulerverfahren:

Gegeben AWP Anfangswertproblem

Gesucht: y(x) für x ≥ x0

),())(()()( 0000100111 xyhyxxxyyxgyxy ϕ⋅+=−$+==≈

Dadurch erhält man den Näherungswert

Wir wollen y(x) bei x0 lokal als lineare Funktion g(x) betrachten, und einen kleinen Schritt der Länge h zu x1 = x0 + h entlang dieser linearen Näherung gehen.

16

),(;);( 1100 kkkkkk xyhyyhxxxyy ϕ⋅+=+== ++

Ersetze wieder Funktion lokal durch Tangentengerade!

Dies ergibt die Iterationsvorschrift des Eulerverfahrens (Vorwärts-Euler):

Der Einfachheit halber wählen wir die Schrittweite h konstant (muss aber nicht sein).

für k=0,1,...

17

] ).,()()),(()()( 0001011

0

1

0

1

0xyxxdxxxydxxyxyyy x

xxx

xx ϕϕ ⋅−≈∫=∫ &==−

Euler aus Integration:

Betrachte die Diff’gleichung zwischen den Stellen x0 und x1 :

aus Rechteckregel, indem die Fläche unter der Kurve ϕ(y(x),x) angenähert wird durch die Fläche des Rechtecks mit den Ecken (x0,0), (x1,0), und (x1,ϕ(y0,x0)), (x0,ϕ(y0,x0)).

18

)(2

)()()()( 0

2

0001 zyh

xyhxyhxyxy !!+!+=+=

Eulerverfahren aus Taylorentwicklung :

Bekannt sind y(x0) = y0, y’(x0) = ϕ(y0,x0), mit Zwischenstelle z0. Der h2-Term ist klein und wird vernachlässigt ! Eulerverfahren.

hyy

xxyy

dxdy

yxyx

01

01

01000

0

),( −=

−

−≈#$

%=&=ϕ

ergibt wieder das Eulerverfahren!

Euler aus der Diskretisierung des Differentialquotienten:

19

hyy

xxyy

dxdyyxy

x

01

01

01111

1

),( −=

−−

≈#$

%=&=ϕ

Verbesserte Verfahren:

Rückwärts-Euler:

Der Diff’quotient kann natürlich mit derselben Berechtigung angenähert werden durch

),( 111 +++ ⋅+= kkkk xyhyy ϕDies führt zu der Vorschrift

Im Unterschied zum einfachen Euler taucht hier die Unbekannte yk+1 auch noch in der Funktion ϕ auf; das macht die Sache komplizierter.

20

0),()(!

1 =−⋅−= + kk yxzhzzf ϕ

Die berechnete Nullstelle z ist dann die nächste Näherung

)( 11 ++ ≈= kk xyyz

Um yk+1 zu erhalten, ist die Nullstelle einer Funktion zu bestimmen, nämlich von

Solche Verfahren heißen implizite Verfahren, im Gegensatz zum einfachen Eulerverfahren, das ein explizites Verfahren ist. Zur Bestimmung von yk+1 kann man iterative Verfahren wie z.B. das Newtonverfahren verwenden.

Explizites Euler als „Predictor“ liefert Startwert für implizites Euler / Newtonverfahren als „Corrector“

21

)(6

)(2

)()()()( 0

3

0

2

0001 zyhxyhxyhxyhxyxy !!!+!!+!+=+=

Weitere Taylorpolynom-Verfahren:

Berücksichtigung höherer Terme in der Taylorentwicklung:

xy

xyxdx

dyxy

yxxy

dxd

dxyd

xy

∂

∂+

∂

∂=

=∂

∂+⋅

∂

∂==

#=##

ϕϕ

ϕ

ϕϕϕ ),(),()),(()(

Hier taucht aber die unbekannte Ableitung y’’(x0) auf. Sie kann berechnet werden aus

Benötigt: Partielle Ableitungen, Nachdifferenzieren (Kettenregel)

mit Zwischenstelle z0.

22

] ] ),(00),(0 0000),(),(),()( xyxy xy

xxyxy

yxy ϕϕϕ

∂

∂+⋅

∂

∂=$$

!!"

#$$%

&

∂

∂+⋅

∂

∂++=+ ),(),(),(2

),(2

1 kkkkkkkkkk xyx

xyxyy

hxyhyy

ϕϕ

ϕϕ

Also

und damit

Auf diese Art können beliebig hohe Ableitungen der Lösungs- funktion y an einer Stelle (yk , xk) auf Ableitungen der Funktion ϕ zurückgeführt werden. Die nächste Iterierte erhält man aus dem Anfang der Taylorentwicklung an der letzten Stelle xk. Man spricht hier auch von Einschrittverfahren da stets yk!yk+1

23

Beispiel:

;0)0(;),()('

=

==

yyxxyxy ϕ

( ) ( )

( ) );1(')),((

;),(;),(

2 +=+=∂

∂+⋅

∂

∂=

=∂

∂=

∂

∂=

∂

∂=

∂

∂

xyyyxxx

yy

xxydxd

yyxx

xyx

xyxy

xyy

ϕϕϕ

ϕϕ

( )( ) ;22

112

),(),(),(2

),(

222

22

2

1

!!"

#$$%

&+++=+++=

=!!"

#$$%

&

∂

∂+⋅

∂

∂++=+

kkkkkkkk

kkkkkkkkkk

xhh

hxyxyh

xhyy

xyx

xyxyy

hxyhyy

ϕϕ

ϕϕ

Lösung:

;2

exp)()(

2))(ln())(ln(

20

2

0

2

0

0

!!"

#$$%

& −=⇒

)*

+=−⇒⋅=

xxxyxy

xxyxydxx

ydy

x

x

24

Mehrschrittverfahren

Hier wird aus mehreren schon berechneten Iterierten das nächste yk+1 gewonnen, also yk+1-m , … , yk-1 , yk ! yk+1 .

),(211 kkkk xyhyy ϕ+= −+Also

]

),()(

)),((

)()()()(

11

11

1

1

1

1

1

1

kkkk

x

x

x

x

xxkk

xyxx

dxxxy

dxxyxyxyxy

k

k

k

k

k

k

ϕ

ϕ

⋅−≈

≈=

=%==−

−+

−+

∫

∫+

−

+

−

+

−

Solche Verfahren können sehr einfach aus Quadraturregeln hergeleitet werden, z.B.

25

AWP für Diff’gleichungen erster Ordnung im Rn:

Also

mit vorgegebenem Startvektor

Sei y(x) = (y1(x) . . . y

n

(x))T

y

0(x) = (y01(x) . . . y0n

(x))T = '(y, x) =

= ('1(y1, . . . , yn

, x), . . . ,'n

(y1, . . . , yn

, x))T

y(x0) = (y1(x0) . . . yn

(x0))T

Lösung genauso durch Euler:

y

k+1 =

0BBBBBBBBBB@

y

k+11...

y

k+1n

1CCCCCCCCCCA=

0BBBBBBBBBB@

y

k

1...

y

k

n

1CCCCCCCCCCA+ h ·

0BBBBBBBBBB@

'1(yk

1, . . . , yk

n

, xk

)...

'n

(yk

1, . . . , yk

n

, xk

)

1CCCCCCCCCCA

26

AWP für Diff’gleichungen höherer Ordnung:

Gegeben eine Bedingung für die j-te Ableitung der Funktion y(x)

mit Anfangswerten0BBBBBBBBBB@

y

( j�1)(x0)...

y(x0)

1CCCCCCCCCCA=

0BBBBBBBBBBB@

y

( j�1)0...

y0

1CCCCCCCCCCCA

d

j

dx

j

y(x) = y

( j)(x) = (y( j�1), . . . , y, x)

27

Umformulieren in Diff’gleichung erster Ordnung im Rj :

Definiere dazu Vektorfunktion u(x) = ( u1(x), ... , uj(x) )T und setze u1(x) := y(x) , u2(x) := y’(x) , … uj(x) := y(j-1)(x) .

Damit erhalten wir für u(x)

u

0(x) =

0BBBBBBBBBBBBBBBB@

u

01(x)...

u

0j�1(x)u

0j

(x)

1CCCCCCCCCCCCCCCCA=

0BBBBBBBBBBBBBBB@

u2(x)...

u

j

(x) (u

j

, . . . , u1, x)

1CCCCCCCCCCCCCCCA= '(u, x)

28

),(1k

kkk xuhuu ϕ⋅+=+

mit Anfangsbedingungen

Insgesamt kann man nun wieder das Vektor-Euler-verfahren anwenden:

u(x0) =

0BBBBBBBBBB@

u1(x0)...

u

j

(x0)

1CCCCCCCCCCA=

0BBBBBBBBBB@

y(x0)...

y

( j�1)(x0)

1CCCCCCCCCCA=

0BBBBBBBBBBB@

y0...

y

( j�1)0

1CCCCCCCCCCCA

29

Fehleranalyse: Start bei a = x0 , Gesuchter Wert b = xn ,

Bei äquidistanter Einteilung ist Schrittweite h := (b-a)/n Damit xj = x0 + jh, j=0,1,...,n

Also der Fehler, der in einem Schritt von (y(xk), xk) nach (yk+1,xk+1) entsteht.

y(xk) ist dabei der exakte Wert einer Lösung, nicht yk!

kkk exyy =− ++ )( 11

Definition lokaler Diskretisierungsfehler:

An der Stelle xk ist der lokale Diskret.-Fehler gegeben durch

30

nnnn gxyybyy =−=− )()(

Definition globaler Diskretisierungsfehler:

Für das AWP zur Bestimmung der Lösung an der Stelle b ist der globale Diskret.-Fehler gegeben durch

)(lim,0

byynnh

=∞→→

Definition der Konvergenz:

Die durch unser Lösungsverfahren erzeugte Folge heißt konvergent, wenn gilt

31

Wenn also in exakter Arithmetik bei immer feineren Unterteilungen der Näherungswert gegen den exakten Wert konvergiert.

Das bedeutet natürlich auch, dass der globale Fehler gegen 0 gehen muss!

Lokaler Diskretisierungsfehler

a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8

h

y(x1)

y1

Lokaler Diskretisierungsfehler

a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8

h h

y(x2)

y2

Lokaler Diskretisierungsfehler

a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8

h h h

y(x3)

y3

Lokaler Diskretisierungsfehler

globaler Diskreti- sierungs- Fehler

a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8

h h h

y(b)

y8

36

An jeder Stelle xk treten neue lokale Fehler auf und addieren sich zum globalen Fehler. Um insgesamt Konvergenz zu erhalten, muss also das Verfahren so sein, dass - lokal ein genügend kleiner Fehler entsteht (Konsistenz) und - sich diese lokalen Fehler nur zu einem kleinen globalen Fehler aufsummieren (Stabilität).

Nur so ist für den globalen Fehler O(h2)n = O(h) erreichbar!

)()( 211 hOxyy =−

Definition Konsistenz:

Ein Verfahren heißt konsistent, wenn der lokale Diskretisierungsfehler mindestens von der Ordnung h2 ist, also

Ist mit p≥1 ,

so heißt das Verfahren von der Ordnung p.

Offensichtlich ist das Eulerverfahren konsistent von Ordnung 1, da gilt

37

)()( 111

+=− phOxyy

)(21),()()( 2

000111 zyhxyhyxyyxy !!=−−=− ϕ

mit einer Zwischenstelle z.

Zur Untersuchung der Stabilität beschränken wir uns auf den ‚linearen’ Spezialfall y’ = ϕ(y,x) = λy mit Lösung y(x)=y0exp(λx)

Stabilität bei Diff’gleichungen im Rn:

38

.)1()1(

,)1()1(

,)1(),(

01

02

1112

00001

yhyhy

yhyhyhyy

yhxyhyy

kkk λλ

λλλ

λϕ

+=+=

+=+=+=

+=+=

−

Für |1+hλ|>1 wird daher die Näherungslösung yk immer größer.

mit Lösung :

00 )(),()( yxyundyxyxy ===! λϕ

)(0

0)( xxeyxy −= λ

Für die berechneten Näherungslösungen gilt beim Eulerver. auf

Problem: Divergenz bei zu großer Schrittweite h! Wie groß kann man h wählen?

39

Kritisch ist der Fall λ < 0 :

Die exakte Lösung geht gegen 0,

die Näherungslösung aber nur dann, wenn |1+hλ| < 1 gilt,

d.h. nur wenn h < 2 / |λ|

Für |1+hλ|<1 geht die Näherungslösung yk gegen 0. Stimmt dieses Verhalten mit der tatsächlichen Lösung überein?

Im Fall λ > 0 zeigen also exakte und Näherungslösung dasselbe Verhalten.

0)(:0

)(:0

limlim

=⇒<

∞=⇒>

∞→

∞→

xy

xy

x

x

λ

λ

Für die tatsächliche Lösung y(x) = y0 exp(λx) gilt

40

Dies ist die Stabilitätsbedingung, die garantiert, dass eine beschränkte exakte Lösung auch durch eine beschränkte Näherungslösung approximiert wird, und der globale Fehler nicht zu stark anwachsen kann.

kk hyy)1(

0

λ−=

Führen wir dieselbe Untersuchung für das implizite (Rückwärts) – Euler –Verfahren durch, so erhält man die Näherungslösungen von der Form

Also ist für λ < 0 das Eulerverfahren nur konvergent, wenn die Schrittweite h so klein gewählt ist, dass h < 2 / |λ| gilt !

41

Im kritischen Fall λ < 0 gilt hier unabhängig von h

0)1(

0limlim =−

=∞→∞→

kk

kk h

yyλ

Das implizite Eulerverfahren erfüllt für alle h die Stabililtätsbedingung, nämlich dass exakte und Näherungs-lösung für λ < 0 beschränkt bleiben!

42

Anwendungsbeispiel:

Räuber-Beute-Modell

Einfaches Modell, das die Populationsänderung in einem ‚Primitiv-Ökosystem’, bestehend aus genau einer Räuberspezies und einer Beutespezies, beschreibt.

Viele Räuber ! Beute nimmt ab Wenig Räuber ! Beute nimmt zu

Viel Beute ! Räuber nehmen zu Wenig Beute ! Räuber nehmen ab

43

Änderung der Anzahl Beutetiere x(t) ist zum einen durch die Geburtenrate a proportional der Anzahl Beutetiere, und zum anderen führt eine Begegnung eines Beutetiers mit einem Räuber (y(t)) zu einer Verringerung (mit Sterberate b):

Man erhält also zur Beschreibung der zeitlichen Änderung der Population von Räuber und Beute ein DGL-System:

x(t) = ax � byx

Andererseits erhöht sich die Räuber-Geburtenrate durch viele Beutetiere, während die Abnahme der Räuber von ihrer Sterberate d abhängt:

y(t) = cxy � dy

44

0000 )()( ytyundxtx ==mit Startwerten

Fixpunkte dieser Vektoriteration: (x,y)=( d/c, a/b )

iiiii

iiiii

dyycxyy

ybxaxxx

−=−

−=−

+

+

τ

τ1

1

Eulerverfahren mit Schrittweite τ liefert dafür die Formel:

oder( )( )iiiii

iiiii

dyycxyyybxaxxx

−+=

−+=

+

+

τ

τ

1

1

y(t) = cx(t)y(t) � dy(t)

x(t) = ax(t) � bx(t)y(t)fur t0 t tn

45

Beute

Räuber

Populationsverlauf: Parameter: a=.3, b=.025, c=.0015, d=.2

http://www.leinweb.com/snackbar/wator/

Fixpunkt

Fixpunkt