Lineare Trennbarkeit (Linear Separability)

Das Konzept der linearen Trennbarkeit kann man am besten an einem einfachen Beispiel, dem bekannten XOR-Problem, demonstrieren. Man betrachte hierzu ein einstufiges Perzeptron-Netzwerk mit einem Ausgabeneuron j in Ebene 1 und zwei Neuronen in Ebene 0. Die Ausgabe des Neurons j soll 0 sein, falls seine binären Eingaben gleich sind (o1=o2) sonst soll sie 1 sein. Das heißt, damit oj=1 ist, muss gelten:

Für w2j>0 ist dies äquivalent zu folgender Ungleichung:

Für einen konstanten Schwellenwert Θj ergibt sich also eine Gerade in der durch o1 und o2 gebildeten Ebene (siehe Abb. 1, links). Alle Punkte oberhalb dieser Geraden stellen bei positivem w2j Kombinationen von o1 und o2 dar, für die das Neuron feuert. Bei negativem w2j sind alle Punkte unterhalb der Geraden Punkte, für die das Neuron feuert. Man beachte, dass diese Herleitung allgemein für reelle Aktivierungen gilt, bei binären Aktivierungen sind nur die mit A0, A1, B0 und B1 gekennzeichneten Eckpunkte des Einheitsquadrats möglich.

Abb.1Lineare Separierbarkeit und das XOR-Problem

Abb.2einschichtiges binäres Perzeptron

Klicken Sie das Ausgangsneuron an, um Schieberegler für Gewichte anzuzeigen. Die grüne Fläche rechts bezeichnet vom Perzeptron akzeptiertes Gebiet. In dem Applet wird nicht der Schwellenwert, sondern ein verstecktes ON-Neuron benutzt.

Ein neuronales Netz, welches das XOR-Problem lösen will, muss die Punkte A0 und A1 der einen Klasse A zuordnen, die Punkte B0 und B1 der Klasse B. Es ist offensichtlich, dass dies durch Verschiebung und Drehung einer einzigen Geraden, die den Eingaberaum linear separiert, nicht möglich ist. Es gilt also:

Die Mengen A=A0A1 und B=B0B1 des XOR-Problems sind nicht linear separierbar, d.h. es gibt keine Wertekombination von w1j, w2j und j, für die netj<j für alle Punkte in A und zugleich netj⋅j für alle Punkte in B ist.

Bei n Neuronen, die Eingaben in ein Neuron liefern, kann man den Raum der Eingaben als n-dimensionalen Würfel darstellen (sofern die Eingabe auf 01 beschränkt ist, sonst ist es der n-dimensionale Raum). Das Neuron separiert diesen Eingaberaum durch eine n−1-dimensionale Hyperebene. Für n=3 ist dies in Abb. 1 rechts dargestellt. Allgemein gilt:

Ein einstufiges Perzeptron (d.h. ein Perzeptron mit nur einer Stufe modifizierbarer Gewichte) kann nur linear separierbare Mengen, d.h. Mengen, die durch eine Hyperebene trennbar sind, klassifizieren.

Für praktische Anwendungen stellt sich damit die Frage, wie häufig reale Probleme linear separierbar sind. Da dies vom Problem und der gewählten Codierung abhängt, kann man diese Frage nicht allgemein beantworten. Von sehr vielen Problemen weiß man aber oder vermutet man, dass sie nicht linear separierbar sind. Es gibt auch eine theoretische Untersuchung von Widner, der die Anzahl der linear separierbaren Funktionen unter allen möglichen binären Funktionen von n Eingabeneuronen untersucht hat. Er hat festgestellt, dass ihr Prozentsatz mit wachsendem n sehr schnell abnimmt.