Tensoren und ihre Zerlegungen

Matrizen sind bereits seit mehreren Jahrhunderten wichtige Werkzeuge, mit denen man effizient lineare Gleichungssysteme lösen kann. Dabei werden die Koeffizienten des Gleichungssystems mit zwei Indizes versehen, die festlegen, in welcher Zeile und in welcher Spalte der Matrix der Koeffizient einzutragen ist.

Eine Matrix mit mehr als zwei Indizes heißt Tensor. Einen Tensor des Formats 3x3x3 kann man sich wie einen Rubik-Würfel vorstellen, bei dem jeder der 27 kleinen Würfel mit einer Zahl gefüllt ist. Tensoren sind Datenstrukturen, die in vielen Bereichen der Naturwissenschaften auftauchen. Außerdem lassen sich große Datenmengen, die unter dem Schlagwort „Big Data“ Grundstein vieler moderner Anwendungen sind, oft auf natürliche Weise in Tensoren speichern.

Ärzte in Mathlandia

Der Begriff Tensorzerlegung soll an einem fiktiven Beispiel erläutert werden. In Mathlandia gibt es zwei Krankheiten. Beide können – müssen aber nicht – drei verschiedene Symptome hervorrufen, nämlich Fieber, Kopfschmerz und Übelkeit. Ob bei einer Person ein Symptom auftritt oder nicht ist unabhängig davon, ob die anderen Symptome auftreten. Die Ärzte von Mathlandia haben für jede der beiden Krankheiten eine Arznei, die aber nicht gemeinsam mit der anderen Arznei verabreicht werden darf, und die bei der jeweils anderen Krankheit wirkungslos bleibt. Außerdem können die Ärzte feststellen, ob ein Patient an einer der beiden Krankheiten leidet, aber nicht an welcher davon. Auf den ersten Blick können die Ärzte also nur zufällig eine der beiden Arzneien verabreichen und mit einer 50:50-Chance dem Patienten helfen. Glücklicherweise kennen sich jedoch einige Ärzte mit Tensoren aus! Bei der Untersuchung von 400 erkrankten Patienten ermitteln sie, welche Symptome auftreten und stellen das Ergebnis in einem Tensor dar (siehe Abb. 1).

In diesem Tensor ist beispielsweise kodiert, dass 39 der 400 kranken Patienten an Übelkeit und Fieber ohne gleichzeitigen Kopfschmerz leiden. Die anderen Einträge geben entsprechend die Anzahl anderer Kombinationen von Symptomen an. Kann dieser Tensor nun den Ärzten helfen, die geeignete Arznei zu verschreiben, wenn sie die spezifischen Symptome eines Patienten kennen? Wie verhält es sich, wenn sie die Symptome nicht kennen? Überraschenderweise ist die Antwort in beiden Fällen ja.

Angenommen, die Patienten würden alle an derselben Krankheit leiden. Dann gäbe es eine Wahrscheinlichkeit für das Auftreten von Fieber, die von den anderen Symptomen unabhängig ist. Die Wahrscheinlichkeit einer Kombination von Symptomen ist nur das Produkt der einzelnen Wahrscheinlichkeiten. Ein Tensor mit dieser multiplikativen Struktur heißt Tensor vom Rang 1. Da das in unserem Beispiel nicht der Fall ist, muss es zwei Krankheiten geben. Die Ärzte versuchen sich also an Tensorzerlegung und schreiben den Tensor als Summe von zwei Tensoren vom Rang 1 (siehe Abb. 2).

Solch eine Zerlegung lässt vermuten, dass 300 der 400 Patienten an der ersten Krankheit leiden und nur 100 an der zweiten. Wenn es nun also gilt, einen Patienten zu behandeln, ohne dessen Symptome zu kennen, sollten die Ärzte auf die erste Krankheit tippen, da diese viel häufiger vorkommt, mit einer Chance von 3:1. Sollte ein Patient zu behandeln sein, der an Übelkeit ohne Kopfschmerz und ohne Fieber leidet, finden die Ärzte in der Tabelle 31 solcher Patienten, aber nur 300*0,01=3 von diesen leiden an der ersten Krankheit. Die Ärzte sind also gut beraten, die Arznei gegen die zweite Krankheit zu verschreiben. Außerdem kann der Zerlegung für jede der beiden Krankheiten die Wahrscheinlichkeit des Auftretens eines bestimmten Symptoms abgelesen werden. So tritt Fieber (Kopfschmerz, Übelkeit) bei 90 Prozent (80 Prozent, 50 Prozent) aller Patienten, die an der ersten Krankheit leiden, auf.

Die Theorie dahinter

Tensoren mit nichtnegativen Einträgen, die sich zu 1 summieren, repräsentieren gemeinsame Zufallsverteilungen mehrerer diskreter Zufallsvariablen. Wenn der Tensor Rang 1 hat, dann ist die Verteilung unabhängig. Ein Tensor hat Rang r, wenn er sich als Summe von r Tensoren von Rang 1 schreiben lässt, nicht aber mit weniger. Dieses Konzept des Rangs eines Tensors ist sehr bedeutend: Der Rang kann als Anzahl der Zustände einer versteckten Zufallsvariable interpretiert werden, die die vorliegenden Daten erklärt. In obigem Beispiel gab es drei Zufallsvariablen, die zwei Werte annehmen – nämlich die Symptome. Der Rang r=2 enthüllt die Anzahl der zugrundeliegenden Krankheiten.

In vielen Anwendungen haben Tensoren bestimmte Zusatzeigenschaften, sie sind beispielsweise symmetrisch oder haben nur nichtnegative Einträge. In diesen Situationen hofft man, diese Eigenschaften in den einzelnen Summanden der Zerlegung zu erhalten. Daraus ergeben sich interessante geometrische Einschränkungen. Geometrie von Tensorzerlegungen und Statistik sind aktive Forschungsrichtungen am Max-Planck Institut für Mathematik in den Naturwissenschaften. So wurden Methoden dort zur exakten Zerlegung symmetrischer Tensoren entwickelt und die Charakterisierung von Tensoren mit kleinem, nichtnegativem Rang initiiert [1,3]. Der Rang eines spezifischen Tensors beschreibt – mittels einer tiefen Verbindung zur Informatik – die Komplexität der Matrixmultiplikation. Die aktuell beste untere Schranke hierfür wird in [2] gegeben.

Ausblick

Vor zwei Jahrzenten stellte Pierre Comon die Vermutung auf, dass der Rang eines symmetrischen Tensors immer auch seinem symmetrischen Rang entspricht. Der Versuch, Comons Vermutung zu beweisen, hat die Entwicklung auf dem Gebiet über viele Jahre vorangetrieben. Im Mai 2017 gelang es jedoch Yaroslav Shitov, ein Gegenbeispiel vorzulegen: einen 800x800x800 Tensor vom Rang 903, dessen symmetrischer Rang höher ist. Zusammen mit Shitov haben wir dieses Beispiel studiert und seine Bedeutung für die Geometrie der Tensoren diskutiert. Dieser Durchbruch öffnet zahlreiche neue Forschungsperspektiven, die die jetzt durch Experten für numerische und stochastische Aspekte (P. Breiding, M. Pfeffer, A. Uschmajew) verstärkte Arbeitsgruppe weiter verfolgt.

Literaturhinweise