{"id":4750,"date":"2022-07-12T06:35:06","date_gmt":"2022-07-12T06:35:06","guid":{"rendered":"https:\/\/lamarr-institute.org\/blog\/sum-product-networks\/"},"modified":"2025-11-12T14:54:46","modified_gmt":"2025-11-12T14:54:46","slug":"sum-product-networks","status":"publish","type":"blog","link":"https:\/\/lamarr-institute.org\/de\/blog\/sum-product-networks\/","title":{"rendered":"Sum-Product Networks \u2013 Eine neue tiefe Architektur des Maschinellen Lernens"},"content":{"rendered":"\n

Sum-Product Networks (SPNs) sind eine Art von probabilistischen graphischen Modellen (PGMs). Sie bestehen also aus Knoten, die durch Kanten miteinander verbunden sind, und repr\u00e4sentieren Verteilungsfunktionen. So weit unterscheiden sie sich also nicht weiter von anderen PGMs wie beispielsweise Bayes- oder Markov-Netzen. Der wesentliche Unterschied besteht in der Semantik der einzelnen Knoten. Ein SPN ist ein sogenannter tripartiter Graph. Das bedeutet, dass es drei verschiedene Typen von Knoten gibt. Als Blattknoten<\/strong> werden alle Knoten in einem SPN bezeichnet, die keine ausgehenden Kanten besitzen. Diese repr\u00e4sentieren univariate Verteilungsfunktionen, also Verteilungen, die genau \u00fcber eine Variable definiert sind. Alle inneren Knoten eines SPNs sind entweder Summen- oder Produktknoten. Daher auch der Name Sum-Product Networks. Summenknoten<\/strong> repr\u00e4sentieren Mischverteilungen, die sich als gewichtete Summe der Verteilungen ergeben, die durch die direkt folgenden Knoten, Kindknoten genannt, dargestellt werden. Produktknoten<\/strong> repr\u00e4sentieren Faktorisierungen, die sich analog zu den Summenknoten als Produkt der durch die Kindknoten dargestellten Verteilungen ergeben.<\/p>\n\n\n\n

Durch die Kombination von univariaten Verteilungen, Faktorisierungen und Mischverteilungen lassen sich schlie\u00dflich beliebig komplexe Verteilungsfunktionen darstellen. Diese lassen sich f\u00fcr die verschiedensten Aufgaben, wie beispielsweise Bildsegmentierung, die Verarbeitung nat\u00fcrlicher Sprache oder sogar in der Robotik verwenden.<\/p>\n\n\n\n

\"-
\u00a9 ML2R
Abbildung 1: Darstellung der drei Knotentypen. Die beiden Abbildungen links stellen Blattknoten dar. Hierbei unterscheidet man zwischen Blattknoten f\u00fcr kategorische und kontinuierliche Variablen. <\/figcaption><\/figure>\n\n\n\n

Wie trainiert man ein SPN?<\/h2>\n\n\n\n

Das Training eines SPNs folgt einem einfachen, aber effektivem Schema namens \u201eLearnSPN\u201c, das sowohl die Modellstruktur als auch dessen Parameter lernt. LearnSPN erstellt die Modellstruktur rekursiv, in dem f\u00fcr die Erstellung eines jeden Knoten aus f\u00fcnf Operationen gew\u00e4hlt werden kann: SplitData, SplitVariables, SplitUninformativeVariables, NaiveFactorization und CreateLeaf.<\/p>\n\n\n\n

SplitData<\/strong> erstellt einen Summenknoten und partitioniert den Datensatz unter Verwendung eines Clustering-Algorithmus wie zum Beispiel $k$-Means. F\u00fcr jede so entstandene Partitionsmenge wird rekursiv ein sub-SPN trainiert. Diese sub-SPNs bilden dann die Kindknoten des erstellten Summenknotens. Die Kantengewichte werden proportional zur Anzahl der Daten in den Partitionsmengen gew\u00e4hlt, sodass sie in der Summe 1 ergeben.<\/p>\n\n\n\n

SplitVariables<\/strong> erstellt einen Produktknoten und partitioniert die Variablen mithilfe einer Unabh\u00e4ngigkeitsanalyse, sodass alle Variablen in einer Partitionsmenge abh\u00e4ngig voneinander und gleichzeitig m\u00f6glichst unabh\u00e4ngig zu denen der anderen Partitionsmengen sind. F\u00fcr jede der Partitionsmengen wird dann erneut ein sub-SPN trainiert. Hierbei werden jeweils nur die Daten in Bezug auf die Variablen der jeweiligen Partitionsmenge betrachtet.<\/p>\n\n\n\n

Durch das Aufteilen der Daten und Variablen kann es vorkommen, dass Variablen ihren informativen Mehrwert verlieren und \u201euninformativ\u201c werden, sprich, alle Datenpunkte nehmen f\u00fcr bestimmte Variablen denselben Wert an. In solchen F\u00e4llen sorgt die Operation SplitUninformativeVariables <\/strong>f\u00fcr die Abspaltung dieser Variablen. Dazu wird ein Produktknoten erstellt, der f\u00fcr jede dieser Variable einen Blattknoten als Kind erh\u00e4lt. Die \u00fcbrigen informativen Variablen werden dann in einem sub-SPN f\u00fcr das weitere Training verwendet.<\/p>\n\n\n\n

Ein Spezialfall von SplitUninformativeVariables stellt die naive Faktorisierung dar, genannt NaiveFactorization<\/strong>. Hierbei wird ein Produktknoten erstellt, der f\u00fcr jede Variable einen Blattknoten erh\u00e4lt.<\/p>\n\n\n\n

Zu guter Letzt dient die Operation CreateLeaf<\/strong> dazu, einen Blattknoten f\u00fcr eine Variable zu erstellen und anhand der gegebenen Datenpunkte eine univariate Verteilung zu sch\u00e4tzen. Die Art der Verteilung ist abh\u00e4ngig von der Variablen selbst.<\/p>\n\n\n\n

Der Entscheidungsprozess, der bestimmt, welche Operation gew\u00e4hlt wird, ist in Abbildung 2 graphisch dargestellt. Ausschlaggebend sind dabei die Anzahl der Variablen $|V|$, die Existenz von Variablen ohne gro\u00dfen informativen Mehrwert, Clustern und Unabh\u00e4ngigkeiten sowie die Anzahl der Datenpunkte $|X|$, die einen gewissen Grenzwert $t$ nicht unterschreiten sollte. Sobald dieser Grenzwert unterschritten wird, werden keine weiteren Aufteilungen der Daten oder Variablen (nur SplitVariables) vorgenommen. Dadurch wird sichergestellt, dass die Anzahl der Datenpunkte in den Bl\u00e4ttern ausreichend f\u00fcr eine sinnvolle Sch\u00e4tzung der Verteilungen ist.<\/p>\n\n\n\n

\"-
\u00a9 ML2R
Abbildung 2: Links ist der Entscheidungsprozess w\u00e4hrend des Trainings mit LearnSPN und rechts der Trainingsdatensatz bestehenden aus zwei Clustern und ein darauf trainiertes SPN dargestellt.<\/figcaption><\/figure>\n\n\n\n

Am Wurzelknoten werden zun\u00e4chst die beiden Datencluster (blau und orange) getrennt. Anschlie\u00dfend werden f\u00fcr beide Cluster die Klassenzugeh\u00f6rigkeitsvariable $C$ abgespalten, da diese unter Betrachtung eines einzelnen Clusters ohne informativen Mehrwert ist. Da $C$ eine kategorische Variable ist, stellen die korrespondierenden Bl\u00e4tter Indikatoren der jeweiligen Klasse dar. Zum Schluss werden die beiden Koordinaten $X$ und $Y$ faktorisiert und aus den Daten Normalverteilungen gesch\u00e4tzt.<\/p>\n\n\n\n

Inferenzen: Das trainierte KI-Modell in die Anwendung bringen<\/h2>\n\n\n\n

Nach dem Training eines SPNs soll dieses nat\u00fcrlich auch zur Vorhersage von bestimmten Zielgr\u00f6\u00dfen, verwendet werden, welche f\u00fcr gew\u00f6hnlich als Inferenz bezeichnet wird. In der Anwendung von SPNs werden in der Regel drei Arten von Inferenzen unterschieden: Maximum a-posteriori (MAP), most probable explanation (MPE) und maximum likelihood (MAX).<\/p>\n\n\n\n

Der grundlegende Unterschied zwischen den verschiedenen Inferenzarten liegt in der Unterteilung der Variablen in beobachtete Variablen, versteckte Variablen und Zielvariablen. Die beobachteten Variablen sind, wie der Name es bereits vermuten l\u00e4sst, diejenigen Variablen, die wir beobachten k\u00f6nnen, beziehungsweise als Evidenz verwenden wollen, um schlie\u00dflich die Zielvariablen vorherzusagen. Alle \u00fcbrigen Variablen in unserem SPN bezeichnen wir als versteckte Variablen.<\/p>\n\n\n\n

Die MAP-Inferenz<\/strong> sucht nach der wahrscheinlichsten Belegung unserer Zielvariablen, gegeben der beobachteten Variablen (Evidenz).<\/p>\n\n\n\n

Existieren keine versteckten Variablen, sprich, alle nicht beobachteten Variablen sind Zielvariablen, so spricht man von einer MPE-Inferenz<\/strong>. Diese stellt also lediglich einen Spezialfall der MAP-Inferenz dar. Diese Art der Inferenz kann beispielsweise f\u00fcr klassische Klassifikationen verwendet werden.<\/p>\n\n\n\n

Die MAX-Inferenz<\/strong> sucht nach der wahrscheinlichsten Belegung aller Variablen. Hierbei wird nicht weiter zwischen den Variablenarten unterschieden.<\/p>\n\n\n\n

Betrachten wir im Folgenden ein Beispiel zur MPE-Inferenz:<\/p>\n\n\n\n