Artikel
02/01/2017

Juli 2016

Band 31, Nummer 7

Dieser Artikel wurde maschinell übersetzt.

Testlauf – Matrixinversion mit C#

James McCaffrey Eine der grundlegendsten Techniken in Machine learning-Systeme (ML) ist die matrixinversion. Aus Gründen, die habe ich nicht Microsoft .NET Framework ist anscheinend eine Matrix Inversion-Methode verfügen oder wenn eine solche Methode vorhanden ist, ist es sehr gut ausgeblendet. In diesem Artikel ich darstellen und beschreiben den Code für eine Matrix-Inversion-Methode, die einen Algorithmus Namens Crouts LU Zerlegung verwendet.

Lassen Sie mich werden das erste, matrixinversion zugeben ist ein sehr auffälligen Thema nicht. Aber wenn Sie ML Systeme ohne Rückgriff auf externe Bibliotheken erstellen möchten, müssen eine Matrix Inversion-Methode ist wichtig, da matrixinversion von Dutzenden von wichtigen ML-Algorithmen verwendet wird.

Ich empfehle Ihnen, sich das Demoprogramm in Abbildung 1 anzusehen. Dort erfahren Sie, um was es bei diesem Artikel geht.

Matrix-Inversion-Demo
Abbildung 1 Matrix Inversion Demo

Das Demoprogramm einrichten und die Anzeige einer 4 x 4 (4 Zeilen, 4 Spalten) Matrix m:

3.0  7.0  2.0  5.0
1.0  8.0  4.0  2.0
2.0  1.0  9.0  3.0
5.0  4.0  7.0  1.0

Anschließend berechnet die Inverse der Matrix mit einer im Programm definierte Methode und das Ergebnis wird angezeigt:

0.097   -0.183   -0.115    0.224
 -0.019    0.146   -0.068    0.010
 -0.087    0.064    0.103   -0.002
  0.204   -0.120    0.123   -0.147

Das ist so ziemlich alles. Doch wie Sie gleich sehen werden, ist matrixinversion gar nicht so einfach. Als Nächstes überprüft die Demo, dass die berechnete Inverse durch Multiplizieren der ursprünglichen Matrix Zeiten das Gegenteil richtig ist:

1.0  0.0  0.0  0.0
0.0  1.0  0.0  0.0
0.0  0.0  1.0  0.0
0.0  0.0  0.0  1.0

Das Ergebnis der Multiplikation ist die Identitätsmatrix (1.0-Werten auf die diagonale, 0,0 Werte an anderer Stelle), der das inverse Ergebnis richtig ist.

Im Hintergrund verwendet die Matrix-Inversion-Methode eine Technik namens matrixuntergliederung. Zerlegung Faktoren eine Matrix in zwei Matrizen, L (untere) und U (oben), aufgerufen, die beim zusammen mit die ursprüngliche Matrix geben, jedoch mit einigen Zeilen neu angeordnet. Die Demo zeigt die Aufgliederung:

5.000    4.000    7.000    1.000
0.200    7.200    2.600    1.800
0.400   -0.083    6.417    2.750
0.600    0.639   -0.602    4.905

Die Zerlegung enthält sowohl die U die L-Matrizen. Die Matrix L bestehen aus den Werten in der unteren linken Teil der kombinierten LU Matrix mit dummy-1.0-Werten auf der diagonalen und 0.0 Werte im oberen Teil:

1.000    0.000    0.000    0.000
0.200    1.000    0.000    0.000
0.400   -0.083    1.000    0.000
0.600    0.639   -0.602    1.000

Die U-Matrix besteht aus den Werten in der oberen rechten Ecke und die diagonale des kombinierten LU Matrix:

5.000    4.000    7.000    1.000
0.000    7.200    2.600    1.800
0.000    0.000    6.417    2.750
0.000    0.000    0.000    4.905

Die Demo stellt sicher, dass es sich bei die Zerlegung LU korrekt ist, indem der Multiplikation der Matrizen L, U und zeigt das Ergebnis:

5.0  4.0  7.0  1.0
1.0  8.0  4.0  2.0
2.0  1.0  9.0  3.0
3.0  7.0  2.0  5.0

Wenn Sie mit der ursprünglichen Matrix m L * U vergleichen, sehen Sie, dass L * U m, aber die Zeilen der L fast identisch ist * Sie haben wurde zurück permutiert wurden (angeordnet). Die Zeile Permutation sind:

3  1  2  0

Dies bedeutet, dass die Zeile [0] m in Zeile [3] L * u; Zeile [1] m ist in Zeile [1] L * u. Zeile [2] von m ist in Zeile [2] L * u. und Zeile [3] m Zeile [0] L * u.

Grundlegendes zu Matrixinversion

Im normalen arithmetischen ist die Umkehrung einer Anzahl Z eine Zahl, die beim Multiplizieren mit Z 1 gibt. Angenommen, wenn Z = 3, das Inverse Z ist 1/3 = 0.33, da 3 * (1/3) = 1.

Matrixinversion erweitert diese Idee. Die Inverse Matrix m ist ein mit Nxn ("quadratische Matrix" bezeichnet, da die Anzahl der Zeilen die Anzahl von Spalten entspricht) eine Matrix mi z. B. m * mi = I, in dem ich die Identitätsmatrix ist (auf der diagonalen 0.0s an anderer Stelle 1.0s).

Nicht alle Matrizen haben eine Inverse. Wie sich herausstellt, ist es einen Skalarwert bezeichnet die Determinante einer Matrix. Wenn die Determinante einer Matrix 0 (null) ist, müssen die Matrix doen't eine Inverse an.

Beachten Sie, dass zum matrixinversion vollständig zu verstehen, Sie Matrixmultiplikation wissen müssen. Matrixmultiplikation wird am besten anhand eines Beispiels erläutert. Betrachten Sie das Beispiel in Abbildung 2. Der Wert in Zelle [R] [c] der Ergebnismatrix ist das Produkt der Werte in der Zeile der ersten Matrix R und die Werte in Spalte c der zweiten Matrix.

Abbildung 2 Matrixmultiplikation

Bei der Suche nach die Inverse einer Matrix, funktionieren nur mit quadratischen Matrizen allerdings Matrixmultiplikation Matrizen mit unterschiedlichen Formen angewendet werden kann. In diesen Fällen muss die Matrizen was conformable aufgerufen wird. Wenn Matrix A hat die Form Axn Matrix B hat die Form Nxb, hat das Ergebnis der Multiplikation Axb Form. Die Anzahl der Spalten in der ersten Matrix muss die Anzahl der Zeilen in der zweiten Matrix gleich.

Das Demoprogramm Matrixmultiplikation mit der Methode "matrixproduct" und die Hilfsmethoden MatrixCreate, implementiert, siehe Abbildung 3. Das Demoprogramm verwendet einen brute-Force-Ansatz, aber da die Berechnung der einzelnen Zellen in der Ergebnismatrix unabhängig ist, konnte Matrixmultiplikation parallel mit die Parallel.For-Methode von der .NET Task Parallel Library ausgeführt werden.

Abbildung 3 Matrixmultiplikation

static double[][] MatrixCreate(int rows, int cols)
{
  double[][] result = new double[rows][];
  for (int i = 0; i < rows; ++i)
    result[i] = new double[cols];
  return result;
}
static double[][] MatrixProduct(double[][] matrixA,
  double[][] matrixB)
{
  int aRows = matrixA.Length;
  int aCols = matrixA[0].Length;
  int bRows = matrixB.Length;
  int bCols = matrixB[0].Length;
  if (aCols != bRows)
    throw new Exception("Non-conformable matrices");
  double[][] result = MatrixCreate(aRows, bCols);
  for (int i = 0; i < aRows; ++i)
    for (int j = 0; j < bCols; ++j)
      for (int k = 0; k < aCols; ++k)
        result[i][j] += matrixA[i][k] *
          matrixB[k][j];
  return result;
}

Das Demoprogramm

Ich habe das Demoprogramm mit c# codiert, aber Sie haben keine Probleme beim Portieren von Code in eine andere Sprache, z. B. Visual Basic oder Python, falls gewünscht. Der Democode ist zu lang und in seiner Gesamtheit vorhanden, aber der vollständige Code ist im Download, der diesen Artikel begleitet. Der Code ist auch unter quaetrix.com/Matrix/code.html (die URL wird beachtet).

Um das Demoprogramm zu erstellen, wenn ich Visual Studio gestartet und erstellt eine neue C#-Konsolenanwendungsprojekt mit dem Namen "matrixinverse". Das Demoprogramm hat keine nennenswerten .NET Framework-Abhängigkeiten, sodass jede Version von Visual Studio funktionieren sollte. Nachdem der Vorlagencode geladen, im Projektmappen-Explorer Fenster ich mit der rechten Maustaste auf die Datei Program.cs und diese zu den aussagekräftigeren MatrixInverseProgram.cs und Visual Studio dann automatisch die Programmklasse umbenannt für mich.

Am oberen Rand des Editorfensters habe ich gelöscht alle using-Anweisungen, die unnötige Namespaces verwiesen wird, nur die einen Verweis auf den Namespace der obersten Ebene System verlassen.

Die Main-Methode beginnt mit dem Einrichten einer Matrix zum Umkehren:

Console.WriteLine("Begin matrix inverse demo");
double[][] m = MatrixCreate(4, 4);
m[0][0] = 3; m[0][1] = 7; m[0][2] = 2; m[0][3] = 5;
m[1][0] = 1; m[1][1] = 8; m[1][2] = 4; m[1][3] = 2;
m[2][0] = 2; m[2][1] = 1; m[2][2] = 9; m[2][3] = 3;
m[3][0] = 5; m[3][1] = 4; m[3][2] = 7; m[3][3] = 1;

In vielen Fällen werden Ihre Daten in einer Textdatei gespeichert werden, und Sie eine Hilfsmethode zum Laden einer Matrix aus der Datei zu schreiben müssen. Das Demoprogramm verwendet eine Array von Arrays Style-Matrix. Im Gegensatz zu den meisten Programmiersprachen c# unterstützt ein true n-dimensionalen Matrix bevorzuge das Standardverfahren Array von Arrays.

Als Nächstes Main zeigt die Matrix m, und klicken Sie dann berechnet und zeigt das Gegenteil:

Console.WriteLine("Original matrix m is ");
Console.WriteLine(MatrixAsString(m));
double[][] inv = MatrixInverse(m);
Console.WriteLine("Inverse matrix inv is ");
Console.WriteLine(MatrixAsString(inv));

Die gesamte Arbeit wird von der Methode "matrixinverse" ausgeführt. Hilfsmethode MatrixAsString gibt eine Zeichenfolgendarstellung einer Matrix zurück:

static string MatrixAsString(double[][] matrix)
{
  string s = "";
  for (int i = 0; i < matrix.Length; ++i) {
    for (int j = 0; j < matrix[i].Length; ++j)
      s += matrix[i][j].ToString("F3").PadLeft(8) + " ";
    s += Environment.NewLine;
  }
  return s;
}

Die Anzahl der Dezimalstellen (3) und Wert Breite (8) wird hier der Einfachheit halber hartcodiert sind. Ein allgemeiner Ansatz würde diese Werte als Eingabeparameter übergeben. Als Nächstes multipliziert Demo der ursprünglichen Matrix und die inverse einer Matrix, um sicherzustellen, dass das Ergebnis die Identitätsmatrix ist:

double[][] prod = MatrixProduct(m, inv);
Console.WriteLine("The product of m * inv is ");
Console.WriteLine(MatrixAsString(prod));

In dieser Version müssen Sie visuell überprüfen, ob das Ergebnis die Identitätsmatrix ist. Eine anspruchsvollere Vorgehensweise wäre eine Methode schreiben, akzeptiert eine Matrix, und true zurückgibt, wenn die Matrix eine Identitätsmatrix unterliegen einige kleine Unterschied ist (1, 0E-5 wird in der Regel) in die Werte der Zellen.

Als Nächstes veranschaulicht die Demo Teil der im Hintergrund Arbeit Zerlegen der ursprünglichen Matrix:

double[][] lum;
int[] perm;
int toggle = MatrixDecompose(m, out lum, out perm);
Console.WriteLine("The decomposition is");
Console.WriteLine(MatrixAsString(lum));

Die aufrufende Signatur der Methode "matrixdecompose" möglicherweise ein wenig ungewöhnlich angezeigt. Die explizite Rückgabewert ist + 1 oder-1 abhängig von der Anzahl der Zeile Permutationen sind (gerade oder ungerade ist, bzw.). Die Umschaltfläche zurück Wert wird nicht mit der Demo verwendet, jedoch ist erforderlich, wenn Sie die Determinante der Matrix, der Sie darüber informiert, wenn die Inverse einer Matrix vorhanden ist, wie ich gleich erläutern werde, berechnen möchten.

Die Lum out-Parameter ist der Zerlegung der kombinierten LU (untere oben). Die permanent out-Parameter ist ein Array von ganzzahligen Werten, die codiert werden wie die Zeilen zurück, permutiert wurden wurde haben.

Als Nächstes die Demo extrahiert die oberen und unteren Matrizen aus der kombinierten LU und angezeigt:

double[][] lower = ExtractLower(lum);
double[][] upper = ExtractUpper(lum);
Console.WriteLine("The lower part of LUM is");
Console.WriteLine(MatrixAsString(lower));
Console.WriteLine("The upper part of LUM is");
Console.WriteLine(MatrixAsString(upper));

Hilfsmethoden ExtractLower und ExtractUpper wirklich nicht benötigt, um matrixinversion auszuführen, jedoch werden verwendet, um zu veranschaulichen, wie die matrixuntergliederung funktioniert.

Das Demoprogramm endet die Permutation-Informationen, indem die oberen und unteren Zerlegung Matrizen multiplizieren, und zeigt das Ergebnis:

Console.WriteLine("The perm[] array is");
ShowVector(perm);
double[][] lowTimesUp = MatrixProduct(lower, upper);
Console.WriteLine("The product of lower * upper is ");
Console.WriteLine(MatrixAsString(lowTimesUp));
Console.WriteLine("End matrix inverse demo");

Programm definierten Hilfsmethode ShowVector ist lediglich eine Vereinfachung für die Main-Methode zu halten. Wie bereits erwähnt, wird das Ergebnis des unteren * Großbuchstaben ist der ursprünglichen Matrix mit der Ausnahme, dass die Zeilen des Resultsets zurück permutiert entsprechend den Informationen in das Array Perm wurden sind.

Methode "matrixinverse"

Die Definition der Methode "matrixinverse" beginnt mit:

static double[][] MatrixInverse(double[][] matrix)
{
  int n = matrix.Length;
  double[][] result = MatrixCreate(n, n);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      result[i][j] = matrix[i][j];
...

Die Methode wird davon ausgegangen, dass als Eingabeparameter in der Tat eine Matrix verfügt. Dies bedeutet, dass Sie vor dem Aufruf, ungefähr folgendermaßen überprüfen soll:

int d = MatrixDeterminant(m);
if (d == 0.0)
  Console.WriteLine("No inverse");
else
  double[][] mi = MatrixInverse(m);

Eine Alternative ist an diesem Fehlerprüfcode in der Methode "matrixinverse", die eine Kopie der Eingabe Matrix erstellt. Sie können auch matrixinversion, durchzuführen spart Speicherplatz, aber die ursprüngliche Matrix zerstört.

Als Nächstes zerlegt "matrixinverse" die Kopie der Eingabe Matrix:

double[][] lum; // Combined lower & upper
int[] perm;
int toggle;
toggle = MatrixDecompose(matrix, out lum, out perm);

Es mag seltsam an überhaupt Zerlegen einer Matrix um berechnet die Inverse, aber mir vertrauen, dieser Ansatz ist viel einfacher, eine Matrix direkt umkehren.

Die Demo berechnet als Nächstes das Gegenteil noch eine Hilfsmethode namens Hilfsprogramm verwenden:

double[] b = new double[n];
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j)
    if (i == perm[j]) b[j] = 1.0;
    else  b[j] = 0.0;
  double[] x = Helper(lum, b); //
  for (int j = 0; j < n; ++j)
    result[j][i] = x[j];
}

Dieser Code ist sehr subtil. Glücklicherweise müssen Sie immer diesen Teil des Codes ändern.

Methode "matrixinverse" wird beendet, indem das Gegenteil zurückgeben:

...
  return result;
}

Es sollte klar sein, dass die Methode "matrixinverse" ist im Wesentlichen ein Wrapper für die Methoden "matrixdecompose" und Helfer, die meisten Aufgaben ausführen. Der Code für diese beiden Methoden sind im Download, der diesen Artikel begleitet.

Die Determinante einer Matrix

Wenn die Determinante einer Matrix 0 (null) ist, keine die Matrix eine Inverse. Angenommen Sie, eine 3 x 3-Matrix ist:

1.0  4.0  0.0
3.0  2.0  5.0
7.0  8.0  6.0

Die Determinante der Matrix ist:

+1.0 * [(2.0)(6.0) - (5.0)(8.0)]
-4.0 * [(3.0)(6.0) - (5.0)(7.0)]
+0.0 * [(3.0)(8.0) - (2.0)(7.0)]
= +1.0 * (-28.0) -4.0 * (-17.0) = -28.0 + 68.0 = 40.0

Jedes Quadrat weist eine Determinante. Für Matrizen mit Formen, die größer als 3 x 3 ist es erstaunlich schwierig, berechnet die Determinante. Wie sich herausstellt, wenn Sie eine Matrix zerlegen können Sie unteren oberen daraus jedoch die Determinante leicht zu berechnen, Multiplizieren Sie die diagonale Elemente das Ergebnis. Das Demoprogramm definiert eine Methode MatrixDeterminant als:

static double MatrixDeterminant(double[][] matrix)
{
  double[][] lum;
  int[] perm;
  int toggle = MatrixDecompose(matrix, out lum,
    out perm);
  double result = toggle;
  for (int i = 0; i < lum.Length; ++i)
    result *= lum[i][i];
  return result;
}

Nachbereitung

Der Schlüssel zum effizienten matrixinversion ist matrixuntergliederung. Es gibt verschiedene Algorithmen, die eine Matrix zerlegt. Der Code der Demo verwendet ein Verfahren namens Crout Algorithmus. Eine häufige Alternative ist Doolittle-Algorithmus. Ich verwendete Doolittle-Algorithmus bevorzugt, da ist es etwas einfacher, als Crouts, aber ich jetzt Crouts Algorithmus bevorzugen, da sie weniger Stellen Fehler hat.

Ich habe immer gefragt, warum .NET Framework eine Methode besitzt, die berechnet die Inverse einer Matrix. Um sicherzugehen, ist die matrixinversion überaus knifflige Angelegenheit. Ich habe den Code in diesem Artikel vorgestellten 100 Millionen quadratischen Matrizen mit Formen zwischen 2 x 2 und 50 x 50 zufällig generiert und berechnen die Gegenstücke programmgesteuert überprüfen, ob das Produkt der inversen getestet und die ursprüngliche Matrix die Identitätsmatrix von geeigneter Größe wurde.

Dr. James McCaffrey arbeitet für Microsoft Research in Redmond, Washington. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.

Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Chris Lee und Kirk Olynyk