Bernd Thomas
Jul 5 · 7 min read

1.2 Der Transformationstrick ist Fake!

Irgendwie hat man doch ein ungutes Gefühl — insbesondere, wenn man die nichtlineare Kernel Methode auf Erkennen von Vielfachen von z.B. 3 ausdehnen will.

Denn genau genommen haben wir in die Kernel-Funktion bereits (unbeabsichtigt) die Kenntnis (knowledge) von Even / Odd hinein codiert: Die “2” steckt in dem pi/2 der phi-Funktionen, scheinbar unauffällig. D.h. wir haben damit bei der Input-Aufbereitung mittels phi (eine Art Feature-Engineering) bereits die Klassifikation implizit vorweg genommen.

Das fällt sofort auf, wenn man im Fall Vielfache von 3 feststellt, dass die phi-Funktion dann mit pi/3 formuliert werden muß. Dazu mehr in 1.2.2.

Damit ist die Lösung eigentlich unbefriedigend, denn der Kern der Lösung liegt nicht in einem ML Verfahren (hier: SVC) sondern in der Datentransformation, die die Trainings- und Testzahlen bereits nach gerade und ungerade verteilt. Die Machine Learning Lösung ist damit Fake. Genauso, wie in einigen Foren vorschlagen wird, die Zahlen in Binär-Zahlen zu wandeln und auf “lowest digit is 0” zu trainieren.

1.2.1 Den “Kernel-Trick” trainieren ?

Machine Learning heißt im Wesentlichen: Parameter eines Modells zu bestimmen, die die bestmögliche Übereinstimmung zwischen Input und erwartetem Output (Klassifikation) ergeben. Und das allein mit Hilfe von vielen Input-Daten (Training, Training-Set).

Befriedigender wäre es daher, wenn man ein Klassifikationsmodell mit einem oder mehreren Parametern hätte und diese durch Input-Daten und Klassenzuordnung optimal bestimmen könnte (supervised learning).

Ein naheliegender Ansatz ist, an Stelle der 2 in pi/2 den zunächst unbestimmten Paramter w im Ausdruck pi/w in den phi-Funktionen "lernen zu lassen".

D.h. Für die Transformation (und implizite Vor-Klassifikation) der Daten setzen wir:

phi(z) = sin(|z|*pi/w)**2

und versuchen durch Training eines geeigneten Classifiers die Werte für den kontinuierlichen Parameter w von einem Anfangswert w0 zum - uns bekannten - Zielparamter w* = 2 zu führen. Im 2-dim Fall würde man üblicherweise sogar noch die Input-Daten (Summanden) gewichten bevor sie in Phi eingehen. Das, so würde man meinen, gibt dem Verfahren noch mehr Freiheitsgrade.

Viele Stunden später — nach Versuchen mit ML “from scratch” oder Methoden aus der Toolbox sklearn — sieht man ein, was man als Mathematiker eh wusste: das kann nicht klappen! Verschiedene Aktivierungs- und Straffunktionen, Gradienten-Verfahren, stochastische Verfahren — alles nichts.

Zwar bekommt man eine schöne Konvergenz zu w* = 2, wenn der Input (bzw. die Summe der Inputs) die 2 ist und w0 in der Nähe von pi/2 liegt. Wenn wir aber das gesamte Training-Set einbeziehen, komplett oder in Batches oder einzeln zufällig ausgewählt, geht das "Training" von w "kreuz und quer" und konvergiert nicht.

Und das ist nicht verwunderlich: Jedes geradzahlige Vielfache von pi/2 liefert phi = 0. Und mit jedem geradzahligen z, beliebig aus dem Training-Set, ist das Produkt von z*pi/w für (beliebig) viele Werte von w ein geradzahlig Vielfaches von pi/2. Beispiel: z = 12. Der Wert von z*pi/w = 12*pi/w ist geradzahliges Vielfaches von pi/2 für w = 12, 6, 4, 3, 2, 1, 0.5, ... usw. Wo auch immer w im Trainingsprozess steht, wird der Werte für die nächste gerade Zahl z aus dem Training-Set gegen irgendeinen der möglichen Werte konvergieren - wenn er überhaupt konvergiert, was vom Lern-Koeffizienten abhängt (numerische Schrittweitensteuerung). Selbst wenn die 2 im Training-Set auftritt, führt das nicht von z.B. einem w in der Nähe von 0.5 (d.h. pi/0.5 = 2*pi) weg zu w* = 2.

Die analoge Betrachtung gilt für die ungeraden Werte, wodurch bei einem stochastic gradient Verfahren die Werte von w sich völlig erratisch entwickeln.

Auch Straffunktionen “glätten” nicht annähernd genug, um die Oszillationen der Kernel-Funktion auszugleichen.

Fazit: Die ML Classifier-Modelle sind nicht darauf trainierbar, gerade/ungerade zu unterscheiden — es sei denn, man steckt die Kenntnis bereits in die Datenaufbereitung, etwa per nicht-linearer Transformation, die den gesuchten Paramter bereits enthält.

1.2.2 Ergänzung: Erweiterung der Aufgabe auf Vielfache von 3, 4, 5 usw.

Wir wollen uns zumindest noch kurz die “Erweiterung” auf Vielfache von Zahlen größer 2 ansehen, d.h. die Klassifizierung von Input Daten nach “teilbar durch n” und “nicht teilbar durch n”.

Dabei zeigt sich, dass wir auf die gleiche Problematik stoßen:

  • Das Scattergramm zufällig erzeugter und farblich als “teilbar” und “nicht teilbar” gekennzeichneter Training-Sets zeigt die gleiche, nicht linear separierbare Verteilung.
  • Es ist möglich den Transformationstrick mit einer geeigneten Funktion durchzuführen. Diese enthält aber bereits als Paramterwert die Zahl n.
  • Der richtige Parameterweert ist aber nicht trainierbar durch das Training-Set.

Für den Fall n=3 sieht die Transformationsfunktion so aus:

phi(z) = sin(|z|*pi/3)**2

und liefert folgendes 2-dim Bild:

Abb. 1.10: Die sin-square Funktion für n = 3

Die z-Achse ist in 1/10 Einheiten dargestellt. Die dots durchlaufen die Zahlen z von 0 bis 13, wobei die roten dots Vielfache von 3 markieren und die grünen die mit Rest 1 bzw. 2. Man sieht, dass die lineare Klassifikation nach Transformation z.B. durch jede Gerade zwischen 0 und etwa 0.7 möglich ist.

Dass die Transformation mit phi und dem Parameterwert w=2 das nicht leistet, sieht man, wenn wir die Vielfachen von 3 auf die Kurve von phi(z) = sin(|z|*pi/2)**2 abbilden. Vielfache und Nicht-Vielfache von 3 sind nicht linear trennbar. Die richtigen Transformationsparamter sind problemspezifische Vorgaben und werden nicht aus Trainingsdaten gelernt.

Abb. 1.11: Die für n = 3 markierten Punkte auf der phi-Funktion für w = 2

1.2.3 Kurze mathematische Reflexion

Mathmatisch gesehen wird der “Fake” offensichtlich: Im Falle n=2 kann man die Funktion phi(z) = sin(z*pi/2)**2 (z reelle Zahl) als eine stetig differenzierbare Fortsetzung der modulo Funktion m2(z) = z mod 2 (z ganzzahlig) auf die reelen Zahlen ansehen. Das geht so einfach aber nur für n=2.

Für n=3 hat das entsprechende phi(z) = sin(z*pi/3)**2 nicht diese Eigenschaft. Die Funktion kann zwar Vielfache von 3 ( z mod 3 = 0) mit phi(z) = 0 abbilden, aber nicht die anderen Restwerte (1 und 2).

Für größere n gilt das Entsprechende, da mit wachsendem z nach dem höchsten Restwert (i.e. n-1) der Sprung zurück auf 0 (teilbar durch n) folgt. Eine kontinuierliche Erweiterung psi(z) müsste so konstruiert werden, dass sie a) die Restwerte z mod n (0,...,n-1) und b) den "Sprung" von n-1 auf 0 abbildet.

1.3 Ernüchterndes Fazit — und wie es weiter geht

Die Frage, ob ML “lernen” kann, zwischen geraden und ungeraden Zahlen zu unterscheiden, hat uns, bisher, im Kreis geführt.

  • Erst sah es so aus, als wäre es nicht möglich.
  • Dann fanden wir eine Funktion für einen Standardtrick der ML Methoden, mit dem das möglich wurde.
  • Dann stellte sich heraus, dass wir dabei bereits die Lösung vor-implementieren statt ein System zu trainieren.
  • Und schließlich, dass wir diese Lösung nicht durch Training finden können.

Ob es in der wissenschaftlichen Literatur dazu etwas gibt, habe ich nicht abschließend geprüft. Vermutlich ist das Problem an sich zu simpel, als dass es große Aufmerksamkeit verdient. Aber es lässt sich ziemlich schnell zu einer ganzen Problemklasse ausweiten: Lernen, Vielfache von n (statt 2) zu erkennen. Lernen, eine Primzahl (oder Nicht-Primzahl) zu erkennen.

Einige Foren diskutieren die Frage oberflächlich, meist mit dem Hinweis, dass z.B. NN’s sich für solche Aufgaben nicht eignen. Oder machen tatsächlich den Vorschlag, die Zahlen vorher binär zu codieren, d.h. per Teilen durch 2 zu transformieren.

Eine Forum-Quelle diskutiert das Problem allgemeiner: Kann man mit Deep Learning Primzahlen erkennen lassen? D.h. unter anderem die Teilbarkeit durch Ganzzahlen zu lernen. Der Autor gibt an, einem Deep Learning Netztwerk die Teilbarkeit durch 3 antrainiert zu haben, aber für weitere Faktoren war es ihm nicht möglich, ein Netz auf Teilbarkeit zu trainieren.

Fazit bisher also, überspitzt: zu dumm, um gerade und ungerade Zahlen zu unterscheiden!

Andererseits gibt es die universal approximation Sätze (s. z.B. Wikipedia oder in [1]), die besagen, dass es grundsätzlich möglich ist, jede nicht-lineare Funktion durch Neuronale Netze (lokal) zu approximieren. Warum also nicht auch die modulo-Funktionen oder ihre kontinuierlichen Fortsetzungen in Form der sin**2 Funktionen von oben? Wir werden diese Frage in Teil 6 näher untersuchen.

Trotzdem lernt man (nicht das System) einiges darüber, wie man eigentlich gerade/ungerade unterscheidet — und wie man das lernt.

Stellen wir uns Kinder vor, Kindergartenkinder oder auch junge Schüler, die immerhin schon wissen, was Zahlen sind bzw. Zahlen kennen. Wie lernen die, was eine gerade Zahl ist?

Offenbar gibt es zwei wesentlich unterschiedliche Möglichkeiten:

  • die arithmetische: gerade Zahlen lassen sich durch 2 teilen, oder “halbieren”
  • die text-analytische: die geraden Zahlen enden hinten mit einer “2”, “4”, “6”, “8” oder “0” (Ziffer)

Die Erste geht mit elementarem Rechnen (Grundschüler), oder algorithmisch-spielerisch durch Aufteilen einer Menge auf zwei (Bonbons -> Kinder). Die Zweite durch visuelles Erkennen und Memorieren der Basis-Ziffern (“2”, … “0”) — jedenfalls ohne Rechnen.

Was wir in diesem Teil versucht haben und woran wir — bisher — gescheitert sind, ist der arithmetische Ansatz, die Zahlen als numerische Quantitäten zu betrachten, die man z.B. aufteilen kann. Vielleicht führt aber der Ansatz, Zahlen als Zeichenketten zu betrachten, weiter. D.h. diese Art der Formulierung des gleichen Problems könnte für typische ML Verfahren besser geeignet sein.

Wir gehen dem in den nächsten Teilen nach und kommen zu — zumindest für den Verfasser — teilweise überraschenden Erkenntnissen.

[1] “Machine Learning Refined” von Jeremy Watt, Reza Borhani, Aggelos K. Katsaggelos (Cambridge Core, Cambridge University Press)

bernhard.thomas@becketal.com
www.becketal.com

Weiter lesen: 2 Gerade / Ungerade Klassifikation Lernen mit einem statistischen Verfahren

Zurück auf Anfang

Beck et al.

*Arbeiten ist Zusammenarbeiten*. Von Menschen, Daten, Infrastrukturen. Dafür stehen wir.

Bernd Thomas

Written by

Dr. Bernhard Thomas — Mathematics, Theor. Biology, Computational Sciences, AI and advanced Technologies for the Enterprise. Beck et al. Consultant

Beck et al.

*Arbeiten ist Zusammenarbeiten*. Von Menschen, Daten, Infrastrukturen. Dafür stehen wir.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade