PureBoard

Hallo,

Ich wüsste gerne wie die bei PAM250 bei A, A (Alanin mutiert zu Alanin) auf 13 kommen:
http://de.wikipedia.org/wiki/Substitutionsmatrix

PAM250 ergibt sich aus PAM1^250.

Kann mir das jemand erklären?

Die PAM1 ist mit Faktor 10000 skaliert. Ohne diese Skalierung sieht sie so aus (also PAM1 / 10000) =
Setze PAM1* := PAM1/10000

Jetzt potenzieren wir PAM250* := PAM1*^250 und erhalten:
Diese ist nun in Wikipedia anscheinend mit Faktor 100 skaliert und dann normal gerundet: Das ist allerdings nirgendwo vermerkt.

Bei mir kommt immernoch 0.0351788... raus für Alanin - Alanin.

0.98670^250 ist bei mir nicht 0.1331935.

Das ist mein Problem.

Es kann ja wohl kaum sein, dass man da echte Matrizenmultiplikation anwendet, da das ja Prozentwerte sind wie eine Aminosäure zu einer anderen Mutiert in 10 * x Mio. Jahren. Die Mutationen können voneinander ja schlecht abhängen. Das wär ein großer Zufall, dass das exakt mit der Matrixmultiplikation übereinstimmt.

Von den Hintergründen habe ich absolut keine Ahnung, allerdings halte ich die Verwendung einer ganz normalen Matrizenmultiplikation für sehr wahrscheinlich: Denn diese PAM1-Matrix gibt ja sowas wie Übergangswahrscheinlichkeiten an (analog wie bei Markov-Ketten). Die resultierenden Gesamtwahrscheinlichkeiten nach 250-facher Anwendung stets derselben einzelnen und voneinander unabhängigen Übergangswahrscheinlichkeiten ist aber eben die 250ste Potenz der Matrix (bzgl. Matrizenmultiplikation). Nur so wird auch berücksichtigt, dass Alanin auch über Umwege wieder zu Alanin werden kann, auch hat man nur so sichergestellt, dass PAM250 wieder eine Übergangswahrscheinlichkeitsmatrix ist (also mit Zeilensumme=1 jeder Zeile).

(Anm: Könnte sein, dass bei PAM die Rolle von Zeilen und Spalten gegenüber normalen Übergangsmatrizen wie bei denen bei Markov-Ketten vertauscht ist, was aber nichts grundsätzliches ändert)

EDIT: Mini-Anmerkung: Matrizenmultiplikation ist nichts 'komisch konstruiertes', sondern etwas absolut natürliches, dass in unzähligen verschiedenen Situtation angewandt werden kann. Z.B. habe die Matrix P als Eintrag (i,j) die Wahrscheinlichkeit, dass Objekt i zu Objekt j mutiert (oder in einem Graphen mit dieser Wahrscheinlichkeit von Knoten i nach Knoten j gegangen wird). Dann ist nach quadrieren der Eintrag in P^2(i,j) = Summe_k P(i,k) * P(k,j). Das ist aber eben gleich der Wahrscheinlichkeit, dass von i in zwei Schritten nach j gegangen wird entweder über 1 mit Wahrscheinlichkeit P(i,1)*P(1,j) ODER über 2 mit Wahrscheinlichkeit P(i,2)*P(2,j) usw. Die Multiplikation ist wegen der Unabhängigkeit der Ereignisse erlaubt und das ODER führt aufgrund der Disjunktheit zur Gleichheit. => Ergo: Das Matrizenquadrat ist genau die Übergangswahrscheinlichkeit von i nach j in genau 2 Schritten.

Froggerprogger hat geschrieben:Von den Hintergründen habe ich absolut keine Ahnung, allerdings halte ich die Verwendung einer ganz normalen Matrizenmultiplikation für sehr wahrscheinlich: Denn diese PAM1-Matrix gibt ja sowas wie Übergangswahrscheinlichkeiten an (analog wie bei Markov-Ketten). Die resultierenden Gesamtwahrscheinlichkeiten nach 250-facher Anwendung stets derselben einzelnen und voneinander unabhängigen Übergangswahrscheinlichkeiten ist aber eben die 250ste Potenz der Matrix (bzgl. Matrizenmultiplikation). Nur so wird auch berücksichtigt, dass Alanin auch über Umwege wieder zu Alanin werden kann, auch hat man nur so sichergestellt, dass PAM250 wieder eine Übergangswahrscheinlichkeitsmatrix ist (also mit Zeilensumme=1 jeder Zeile).

(Anm: Könnte sein, dass bei PAM die Rolle von Zeilen und Spalten gegenüber normalen Übergangsmatrizen wie bei denen bei Markov-Ketten vertauscht ist, was aber nichts grundsätzliches ändert)

EDIT: Mini-Anmerkung: Matrizenmultiplikation ist nichts 'komisch konstruiertes', sondern etwas absolut natürliches, dass in unzähligen verschiedenen Situtation angewandt werden kann.

Okay . Danke jedenfalls.
Meine Generation hat echt Pech. Ich warte schon die ganze Zeit auf Lineare Algebra, seit der Realschule. Im Gymnasium war nichts, weils nur wenig mit Informatik zu tun hat?! An der Universität ist es ein neuer Dozent in diesem Fach, der es nicht soweit schafft und jetzt weiß ich langsam nichtmehr weiter wo man das Zeug noch lernen könnte. Ich wills nicht privat lernen sondern auf offiziellem Wege. Gibt es da wirklich nirgendwo die Möglichkeit für meine Generation? Das ganze privat zu lernen ist schwammig und ich habe auch keine Motivation mehr dafür. Das hätte man früher alles in mich reinstecken können jetzt aber nichtmehr.

[Habe zeitgleich mein obiges EDIT mit einem Beispiel angereichert, s.o....]

In der Schule hatten wir (Abitur '97) zumindest Grundlagen davon durchgenommen, aber weder sinnvolle Anwendungen von Matrizen kennengelernt, noch größere als 3x3-Matrizen behandelt. Aber im Studium war das für die reinen Informatiker eine Erstsemesterveranstaltung und Leute mit Mathe-Nebenfach oder reine Mathestudenten hören in den ersten beiden Semestern zunächst Lineare Algebra I und II, da geht es nach lockerem Start zum Ende richtig ans Eingemachte und man gewinnt erste Einblicke in Anwendungen von Matrizen. Später im Studium *gerade bei der Informatik!!* tauchen immer wieder Matrizen auf, insbesondere in der Graphentheorie (z.B. kürzeste Wege finden, Invarianten in Petri-Netzen oder zig andere Anwendungen), der Codierungstheorie (Reed-Solomon-Codes oder generell lineare Codes), Computergrafik (affine Transformationen, Drehmatrizen, Quaternionen, etc.) oder einfach nur immer wieder das Lösen von Gleichungssystemen zum finden spezieller Lösungen. Es gibt aber noch viel mehr Anwendungsbereiche, das ist irgendwann so normales Handwerkszeug wie Rechnen mit Zahlen. Je nachdem wo und was Du studierst wirst Du also sicherlich noch darauf treffen und hoffentlich einen guten Prof haben, der die Leute zwar bei Null abholt, dann aber gut vorantreibt.

Dass die Matrizen überall auftauchen liegt auch vermutlich eher daran, dass die Matrizen genau sämtliche linearen Abbildungen beschreiben, also jede lineare Abbildung lässt sich in geeigneter Form in eine Matrixschreibweise überführen. Und lineare Zusammenhänge trifft man in allen möglichen Bereichen an.

[EDIT: um nicht zu erschlagen: Solcherart Einsichten wie hier in den paar Worten komprimiert sind natürlich das Ergebnis von jahrelanger Beschäftigung mit dem Thema, das geht nicht von Null auf 100 in 3 Sekunden Also nicht verzagen! Und wenn Du mehr Interesse an einem Thema wie diesem hast, dann solltest Du vielleicht doch noch privat nebenher dazu ein Buch lesen, oder wirklich ein entsprechendes Mathe-Nebenfach belegen, oder einfach nur so mal eine solche Vorlesung (z.B. für Studium Generale) besuchen, oder was anderes oder woanders studieren (letzteres natürlich nur im Worst-Case und nach reiflicher Überlegung ) ]

In der Schule haben wir Matrizenmultiplikation nicht gemacht. Da hatten wir nur lineare Gleichungssysteme dann in Matrizen umgewandelt und dann in Dreiecksform gebracht und gelöst.

Immerhin wurde dann ja schon das Thema Matrizen überhaupt behandelt und das wichtige Verfahren der Gauss-Elimination (das ebenfalls fundamental ist und auch nicht nur in den reellen Zahlen, sondern viel allgemeiner funktioniert). Mit einer leichten Abwandlung kann man so auch den gesamten Lösungsraum bei unterbestimmten Gleichungssystemen erhalten (über Treppenstufenform).

Auch nur mit Matrizen und Vektoren lässt sich ja schon jede Menge anstellen, z.B. im Anschauungsraum: Die Matrizenmultiplikation bedeutet die Hintereinanderausführung von linearen Abbildungen, möchte man bspw. erst eine Drehung D und dann eine Skalierung S auf einen Vektor v durchführen mittels S*D*v, kann man auch erst S*D =: M als Matrizenprodukt berechnen und braucht dann nur noch M*v zu berechnen. OpenGL packt so ja ebenfalls eine ganze Reihe linearer Abbildungen zu einer einzigen zusammen, die dann letztlich auf die Vektoren angewandt wird (zzgl. anschließender Translation, denn eine Translation ist keine lineare Abbildung (!) und lässt sich daher auch nicht als Matrix-Vektorprodukt schreiben.)

Spannend wird es auch bspw. bei Adjazenzmatrizen von Graphen und was man mit denen alles so anstellen kann. Oder eben wie hier bei Übergangswahrscheinlichkeiten in stochastischen Prozessen. Oder was man in der Codierungstheorie für Eigenschaften eines Codes an seiner Paritätsmatrix ablesen kann. Oder in der E-Technik, wo Übertragungswerte eines Geräts in so komischen S-Parametern als Matrizen beschrieben werden und sich dann die Gesamtübertragung mittels einer Matrixmultiplikation dieser S-Parameter-Vekettung ergibt. Oder was für Konvergenzeigenschaften einer Matrixiteration sich aus ihren Eigenwerten ableiten lässt. Ohje, langsam fange ich an zu labern....

Jedenfalls: Eine Matrix ist in der Mathematik spannender als im Kino

Froggerprogger hat geschrieben:Immerhin wurde dann ja schon das Thema Matrizen überhaupt behandelt und das wichtige Verfahren der Gauss-Elimination (das ebenfalls fundamental ist und auch nicht nur in den reellen Zahlen, sondern viel allgemeiner funktioniert). Mit einer leichten Abwandlung kann man so auch den gesamten Lösungsraum bei unterbestimmten Gleichungssystemen erhalten (über Treppenstufenform).

Auch nur mit Matrizen und Vektoren lässt sich ja schon jede Menge anstellen, z.B. im Anschauungsraum: Die Matrizenmultiplikation bedeutet die Hintereinanderausführung von linearen Abbildungen, möchte man bspw. erst eine Drehung D und dann eine Skalierung S auf einen Vektor v durchführen mittels S*D*v, kann man auch erst S*D =: M als Matrizenprodukt berechnen und braucht dann nur noch M*v zu berechnen. OpenGL packt so ja ebenfalls eine ganze Reihe linearer Abbildungen zu einer einzigen zusammen, die dann letztlich auf die Vektoren angewandt wird (zzgl. anschließender Translation, denn eine Translation ist keine lineare Abbildung (!) und lässt sich daher auch nicht als Matrix-Vektorprodukt schreiben.)

Spannend wird es auch bspw. bei Adjazenzmatrizen von Graphen und was man mit denen alles so anstellen kann. Oder eben wie hier bei Übergangswahrscheinlichkeiten in stochastischen Prozessen. Oder was man in der Codierungstheorie für Eigenschaften eines Codes an seiner Paritätsmatrix ablesen kann. Oder in der E-Technik, wo Übertragungswerte eines Geräts in so komischen S-Parametern als Matrizen beschrieben werden und sich dann die Gesamtübertragung mittels einer Matrixmultiplikation dieser S-Parameter-Vekettung ergibt. Oder was für Konvergenzeigenschaften einer Matrixiteration sich aus ihren Eigenwerten ableiten lässt. Ohje, langsam fange ich an zu labern....

Jedenfalls: Eine Matrix ist in der Mathematik spannender als im Kino

Naja, nur das Lösen einer Matrix ist nicht viel und bildet für mich momentan kaum einen Zusammenhang mit dem Rest der Matrixmathematik.

Klar, die Transformationsmatrizen (Rotation, Translation, Skalierung, andere Verzerrungen) verstehe ich ja noch, aber die Multiplikation ist mir im Kopf noch ein Knoten, weil es mir nicht einleuchtet, warum das Ergebnis nunmal so ist wie es sein soll - Ich kann vielleicht einfach nicht soweit denken. Ich wende es einfach an, aber denk nicht drüber nach was es bedeutet. Ich invertiere in meinen Programmen diese Matrizen sogar um z.B. von einem Projezierten Punkt wieder an die Weltkoordinaten zu kommen oder auch in Bone-animation teilweise. Ich verstehe auch, dass die Reihenfolge der Multiplikation eine Rolle spielt (nicht kommutativ).

Adjazenzmatrizen von Graphen haben wir auch schon, aber in einer anderen Vorlesung. Aber dass man die multiplizieren kann ist uns nicht bewusst (Brauchen wir auch nicht?!). Später kommen die sicher nochmal in "Algorithmen und Datenstrukturen".

P.S.: Ich hab den Film über Matrizen noch nie gesehen.

Aber ich weiß auch nicht so recht .. wie soll ich denn PAM1^250 innerhalb von 10 Minuten ohne Hilfe ausrechnen?

wie soll ich denn PAM1^250 innerhalb von 10 Minuten ohne Hilfe ausrechnen?

Antwort: gar nicht

Zwar kann man mittels Square-And-Multiply schneller als naiv potenzieren (also statt bspw. A^22 = A *A * A * ... * A rechne A^22 = ((((A^2))^2*A)^2*A)^2 mit demnach nur 4 Quadrierungen und 2 weiteren Multiplikationen, aber auch das ist natürlich viel zu aufwändig für eine Klausur und solch große Matrizen. Eine solche Aufgabe wird der Prof nicht stellen (sofern er nicht verrückt ist).

Zur Matrixmultiplikation: Wenn man sich Matrizen im Kontext linearer Abbildungen anschaut, dann sieht man, dass die Spalten einer Matrix genau die Bilder der Einheitsvektoren unter dieser Abbildung sind. Matrix-Vektor-Multiplikation ist dann nur ein Zusammensetzen von Vielfachen dieser. Weiterhin gelangt man dann darauf, dass man die Einträge in der Matrix der Hintereinanderausführung genau so wie in den Rechengesetzen vorgegeben berechnen *muss*, damit die Matrix M=A*B eben die Darstellungsmatrix der Hintereinanderausfühung der linearen Abbildungen zu A und B ist.

Eine Anwendung der Adjazenzmatrix A: Die 0 und 1-Einträge bedeuten ja, dass eine Kante zwischen den entsprechenden Knoten ist, bzw. ein Weg genau der Länge Eins. Wenn man nun das Produkt bildet A^2=A*A, dann erhält man als Eintrag A^2(i,j) = sum_k A(i,k)*A(k,j). Was bedeutet das? Für jeden Zwischenknoten k summieren wir auf - und was? A(i,k) ist die Anzahl Wege der Länge 1 von i nach k und A(k,j) die Anzahl Wege der Länge 1 von k nach j, damit ist deren Produkt die Anzahl Wege der Länge 2 von i über k nach j. Damit A'(i,j) die Anzahl Wege der Länge genau 2 von i nach j über irgendeinen Zwischenknoten. So geht es weiter mit A^3 für Wege der Länge 3 und so weiter. A^100 liefert einem also sofort die Anzahl Wege von jedem zu jedem Knoten der Länge genau hundert. Was kann man mit dieser Einsicht noch anstellen? Es gibt Matrizen mit der Eigenschaft nilpotent zu sein, d.h. es existiert für sie ein Exponent n, so dass A^n = Nullmatrix ist (somit auch für alle n' > n). Was bedeutet das für nilpotente Adjanzenzmatrizen? Es existieren ab einem gewissen n keine Wege mehr der Länge größer gleich n im gesamten Graphen, das kann aber nur genau dann der Fall sein, wenn der Graph kreisfrei ist (sobald ein Kreis enthalten ist, gibt es Wege beliebiger Länge). Ergo: Genau die kreisfreien Graphen besitzen nilpotente Adjazenzmatrizen. Unter Wikipedia zu 'Nilpotente Matrix' finden sich zahlreiche notwendige (und äquivalente) Kriterien für Nilpotenz. Wenn man nun sieht, dass die Adjanzenzmatrix eines davon nicht erfüllt, dann ist der Graph kreisfrei. Man braucht also nicht irgendwie zig Kombinationen von Wegen abzulaufen um zu prüfen, ob da ein Kreis drin ist, sondern diese Eigenschaft lässt sich bequem aus der Adjazenzmatrix ablesen, bzw. algorithmisch mittels Matrizenrechnung ermitteln.

Einige solcher Zusammenhänge sollten in einer DuA-Vorlesung anzutreffen sein, andere tauchen immer wieder hier und da mal auf, vorwiegend natürlich in theoretischen Veranstaltungen.