Matrix Multiplikation Rückwärts

  • Moin,


    Jeder Kennt die Matrixmultiplikation A * B = C, man kennt A und B und sucht C. Einfache Sache.


    Was passiert aber, wenn man A * B = C hat und B und C kennt und A sucht?


    Ich bin leider kein Meister der linearen Gleichungssysteme und habe jetzt einige Zeit probiert dazu eine anständige (analytische) Lösung zu programmieren, einige Erkenntnisse liste ich hier auf, vllt hilft das jemandem weiter. Ansich suche ich aber jemanden der zu viel Freizeit, oder bereits eine Lösung für dieses Problem parat hat.


    Wofür brauche ich das?

    Ich habe in der letzten Zeit versucht eine Art "Texterkennung" zu basteln die auch mit Pixelfehlern usw. klarkommt. Dabei sind die Inputpixel (Schwarz oder Weiß, 0 oder 1) jeweils eine Spalte in der Matrix B. Jede Zeile steht für die Erkennungspixel eines einzelnen Zeichens, (vereinfacht (als 3x3 Pixel "Bit"map) 010 010 010 = "I", 111 101 111 = "O", usw usw). In C stehen jetzt die zugeordneten Zeichen als Zeile, z.B. kommt soetwas heraus wie [0.123, 0.013, -1.5, 1], dann weiß man, dass die untersuchte Bitmap wahrscheinlich das Zeichen Nummer 4 ist (die Zuordnung welches Zeichen welche Nummer hat passiert woanders). Der Knackpunkt ist die Matrix A die quasi die "Gewichtung" der einzelnen Pixel für die einzelnen Zeichen beinhaltet. Vereinfacht: Ist der obere Linke Pixel = Schwarz, so ziehe ich vom Buchstaben O etwas ab da er unwahrscheinlich ist und Addiere bei W, T, P usw etwas dazu, weil diese Buchstaben wahrscheinlicher sind. Nachdem man also die Volle Multiplikation von A = Gewichtungsmatrix * B = "Bit"map durchgeführt hat weiß man welches Zeichen in der Bitmap steht. Vorteil bei der Geschichte ist folgendes: Selbst wenn ein paar Pixel falsch sind (weil z.B. die Kantensuche bei unterschiedlichen Farben für unterschiedliche Ergebnisse beim gleichen Buchstaben sorgt) haben die restlichen Pixel immernoch genug Informationen um den Buchstaben anständig zuzuordnen. Durch die Gewichtung ist diese Methode auch einem direkten Vergleich mit einer Testbitmap überlegen (außerdem müsste man dann alle theoretisch möglichen Zeichen 1x vergleichen und das mit der niedrigsten Abweichung ist dann das richtige, das ist zwar mathematisch einfacher, aber unnötig Rechenaufwändig und niemand will ein paar hundert Bitmaps haben).


    Problemstellung: A * B = C

    - A - Unbekannt <- Soll berechnet werden

    - B - Bekannt (Mögliche Werte sind 0, 1)

    - C - Bekannt (Mögliche Werte sind -1, 0, 1. Das -1 kommt vom OffsetVektor für ein komplett leeres B, da A * 0 = 0 ist, ein leeres B aber z.B. für ein Leerzeichen stehen kann, also muss C <> 0 sein)


    Erkenntnisse:

    - Die Lösung wäre Trivial, wenn A quadratisch wäre sodass man A invertieren kann. Da A aber beliebige Maße haben können muss ist das nicht möglich.

    - B[n][m] und C[k][m] bedeutet A[k][n] -> also ist A automatisch A[UBound(C, 1)][UBound(B, 1)]

    - Es gibt nicht immer eine Lösung (vorallem bei kleinen Matrizen die in meinem Anwendungsfall nicht vorkommen werden, genauso wie ein Inputvektor mit nur Nullen, oder ein Outputvektor mit nur Nullen, jede Matrix Zeile/Spalte hat immer mindestens einen von 0 verschiedenen Wert)

    - Es gibt, wenn es eine Lösung gibt (fast immer) unendlich viele Lösungen, da das Gleichungssystem (fast immer) überbestimmt ist, bzw. Werte voneinander abhängen (wenn man an beiden dreht bleibt das Ergebnis gleich). A enthält viel mehr Werte als es Gleichungen gibt. Für eine optimale Nutzung wäre natürlich eine Art "Durchschnittslösung" die best mögliche Lösung. Man kann also nicht einfach alle "überflüssigen" Werte aus A = 0 setzen und mit dem Rest das System lösen, das ruiniert die Fehlerkorrektur, weil es den Einfluss einzelner Pixel (einzelner Elemente aus B) auf das Ergebnis maximiert un der soll ja gerade minimiert werden.


    Beispielskript:

    Das Skript macht folgendes:

    1. Fülle A mit Zufallszahlen

    2. Suche ein Zufälliges Element aus A heraus, speichere dessen Wert und Addiere eine kleine Zufallszahl

    3. Berechne Abweichung(A * B, C)

    4. Schaue ob die Abweichung kleiner geworden ist:

    wenn ja -> Weiter zuSchritt 2.

    wenn nein -> Mache die Änderung des Elements rückgängig und dann weiter zu Schritt 2.

    5. Ist die Abweichung kleiner als irgendein Epsilon -> Höre auf

    6. Wird die Abweichung nie kleiner als ein Epsilon > 0, dann gibt es keine exakte Lösung. In dem Fall wird "eine" Approximation der Lösung generiert (die aber bei kleinen Matrizen meistens Müll ist, bei großen ist sie aber ziemlich gut).


    So das wars von mir. Wenn jemand Ideen, Skripte oder anderweitiges hat um A * B = C nach A aufzulösen, her damit!


    Edit: 12.2.19:

    Teile Des Systems sind unabhängig lösbar. Also es reicht eigentlich ein u * B = v zu lösen, wobei u,v = Vektoren sind.

    Dabei treten die Fälle auf:

    1. Es gibt mehr Gleichungen als Variablen -> Best Match gesucht (also ein u finden, sodass v möglichst gut quadratisch approximiert wird), hier gibt es ggf. ein Verfahren von Gauß (wie für alles in der Welt) in das ich mich noch einlesen muss.

    2. Es gibt gleich viele Gleichungen wie Variablen -> Trivial (Andys Gleichungssystemlöser freut sich)

    3. Es gibt mehr Variablen als Gleichungen -> "Durchschnittslösung" gesucht (für kleine Systeme habe ich hier eine Lösung, z.B. a + b = 1, die "Durchschnittslösung" ist hier a = b = 0.5. Da man hier immer Variablen paarweise gleichsetzt hat man aber eine Fakultät in der Anzahl Terme die man berechnen muss, für z.B. 20 variablen und 10 Gleichungen wären das 20!/10 = 2.4e17 Terme, was schon nicht mehr praktikabel ist...)



    lg

    M