Approximative Verfahren zur Evaluation von Bedingungen

[mrapp-ke]

Ziel ist es, approximative Verfahren zur Evaluation der Bedingungen, die zu einer Regel hinzugefügt werden können, verwenden zu können. Dabei werden statt jeder möglichen Bedingung nur eine bestimmte Untermenge dieser Bedingungen getestet. Die Auswahl der relevanten Bedingungen, bzw. der Thresholds, die diese verwenden, resultiert von einer Einteilung der Trainingsbeispiele in sogenannte "Bins". Die Statistiken (z.B. Gradienten und Hessians) der Trainingsbeispiele innerhalb jedes Bins werden jeweils aggregiert um ein sogenanntes Histogramm zu erhalten. Die Einteilung der Beispiele in die Bins kann mit Hilfe eines der folgenden Binning-Verfahren erfolgen.

Unsupervised:

Methoden, die keine Informationen über die Ground-Truth Labels, bzw. übeer die aktuellen Vorhersagen des Modells für die diese Labels, berücksichtigen. Da die zu verwendenden Thresholds lediglich von den Feature-Werten der Trainingsbeispiele abhängen, bleiben die möglichen Bedingungen während des kompletten Trainings die selben.

• Equal-Width
• Equal-Frequency

Supervised:

Methoden, die Informationen über die Ground-Truth-Labels, bzw. über die aktuellen Vorhersagen für diese Labels, berücksichtigen. Da die Vorhersagen sich ändern sobald eine neue Regel zum Modell hinzugefügt wurde, ändern sich auch die möglichen Bedingungen in jeder Trainingsiteration.

• Weighted Quantile Sketch

Um die Unterstützung solcher approximativer Verfahren vollständig umzusetzen, müssen eine Reihe von Voraussetzungen geschaffen werden. Es bietet sich an, die Implementierung schrittweise umzusetzen.

Das korrekte Zusammenspiel der approximativen Verfahren mit einigen der bestehenden Funktionen des Algorithmus erfordern außerdem zusätzlichen Aufwand. Um diesen anfangs zu vermeiden sollte der Algorithmus so konfiguriert werden, dass die Verwendung von sparsen Feature-Matrizen und das Sampling von Trainingsbeispielen deaktiviert wird. Das ist über die folgenden Konfigurationsparameter möglich:

--instance-sub-sampling
None
--feature-format
dense

Schritt 1: Unsupervised-Methoden implementieren (siehe #227)

• Abstrakte Basisklasse für alle Methoden hinzufügen
• Equal-Width-Methode implementieren
• Equal-Frequency-Methode implementieren

Schritt 2: Lernen einer einzigen Bedingung

Die Integration in den Regellernalgorithmus erfordert einige Anpassungen des bestehenden Codes. Um diese Anpassungen schrittweise durchführen zu können, sollte es zunächst das Ziel sein eine der oben genannten approximativen Methoden verwenden zu können um eine einzelne Regel mit einer einzelnen Bedingung zu lernen. Um den Algorithmus so zu konfiguren, dass nur die Default-Rule, sowie eine weitere Regel mit exakt einer Bedingung gelernt wird, müssen die folgenden Parameter gesetzt werden:

--max-rules
2
--max-conditions
1

• Erstellen von Histogrammen auf Basis von Statistiken (siehe Erstellen von Histogrammen auf Basis von Statistiken #228)
  • Label-wise
  • Example-wise
• Datenstruktur zur Repräsentation eines Bins, inklusive der Möglichkeit zur Angabe minimaler und maximaler Featurewerte, sowie der Anzahl Beispiele im Bin (siehe Datenstruktur für Repräsentation eines Bins #243)
• Auslagerung des Codes zum Suchen des besten Refinements einer Regel in eigene Klasse
  • Portierung der Klasse HeadRefinement und ihrer Unterklassen nach C++
  • Erstellen einer Basisklasse AbstractRuleRefinement und Portierung des bisherigen Implementierung in neue Unterklasse ExactRuleRefinementImpl (Teil von Abstraktionen um approximative Evaluation von Bedingungen zu ermöglichen #237)
  • Implementierung der Suche nach Refinements auf der Basis von Bins in einer weiteren Unterklasse ApproximateRuleRefinementImpl (siehe Suche nach Refinements auf der Basis von Bins #252)
• Auslagerung des Codes zum Sortieren und Cachen von Beispielindices und Featurewerten in eigene Klasse
  • Portierung der Klasse FeatureMatrix und ihrer Unterklassen nach C++ (siehe Portierung der Klasse FeatureMatrix nach C++ #235)
  • Erstellen einer Basisklasse AbstractThresholds und Portierung der bisherigen Implementierung in neue Unterklasse ExactThresholdsImpl (Teil von Abstraktionen um approximative Evaluation von Bedingungen zu ermöglichen #237)
  • Implementierung für approximative Verfahren in einer weiteren Unterklasse ApproximateThresholdsImpl (siehe Bereitstellung von Thresholds auf der Basis von Bins #256)
• Möglichkeit um Algorithmus so zu konfigurieren dass approximative Verfahren genutzt werden (siehe Konfigurationsparameter für approximative Verfahren #269)

Schritt 3: Lernen einer kompletten Regel

• Funktion zum Filtern der aktuell gecoverten Traininggsbeispiele in Klasse AbstractThresholds auslagern
  • Bisherige Funktionen __filter_current_indices und __filter_any_indices aus rule_induction.pyx in die Klasse ExactThresholdsImpl übernehmen (Teil von Abstraktionen um approximative Evaluation von Bedingungen zu ermöglichen #237)
  • Die Funktionalität zum Filtern der aktuell gecoverten Trainingsbeispiele in KlasseApproximateThresholds::ThresholdsSubset implementieren
    • Die Zuordnung von Bins zu darin enthaltenen Trainingsbeispielen speichern (siehe Zuordnung von Bins zu darin enthaltenen Trainingsbeispielen speichern #290)
    • Die Funktion filterThresholds(Refinement) implementieren (siehe Filterung der von einem Refinement abgedeckten Bins #295)
    • Innerhalb der Funktion Callback::get Bins filtern, falls notwendig (siehe Filterung beliebiger Bins #302)

Schritt 4: Lernen beliebig vieler Regeln

• Funktion zur Anwendung der Vorhersagen einer neuen Regel in Klasse AbstractThresholds aufnehmen
  • In der Klasse ExactThresholdsImpl müssen lediglich die Statistiken aktualisiert werden (Teil von Abstraktionen um approximative Evaluation von Bedingungen zu ermöglichen #237)
  • In der Klasse ApproximateThresholdsImpl müssen die originalen Statistiken und die Histograme aktualisiert werden
    • Innerhalb der Funktion applyPrediction die originalen Statistiken aktualisieren (siehe Statistiken nach Lernen einer Regel mit Hilfe des approximativen Algorithmus aktualisieren #332)
    • Innerhalb der Funktion Callback::get Histogramme neu aufbauen, falls notwendig (siehe Histogramme bei Bedarf neu aufbauen #333)
• Verbleibende Probleme in Offene Probleme bezüglich approximativer Verfahren #341 lösen

Schritt 5: Weighted Quantile Sketch

Out of scope

Weitere offene Punkte

• Anzahl distinkter Featurewerte für die Berechnung der Anzahl Bins verwenden (siehe Möglichkeit um die Anzahl distinkter Werte in einem FeatureVector abzufragen #280)
• Korrektes Zusammenspiel mit dem Sampling von einzelnen Trainingsbeispielen (siehe Unterstützung von Instance-Sampling durch approximativen Algorithmus #340)
• Unterstützung von nominalen Attributen (siehe Unterstützung von nominalen Attributen durch approximative Verfahren #370)
• Unterstützung von sparsen Feature-Matrizen (siehe Unterstützung von sparsen Featurematrizen durch approximative Verfahren #373)
• Unterstützung fehlender Featurewerte (siehe Unterstützung von fehlenden Featurewerten durch approximative Verfahren #416)
• Verwendung der Bins zum Prunen von Regeln (siehe Pruning von Regeln auf Basis von Bins #420)

Weitere optionale Punkte

• Unterstützung der approximativen Verfahren durch SeCo-Algorithmus (siehe Erstellen von Histogrammen auf Basis von Konfusionsmatrizen #253)