Algorithmenauswahl und Metalearning

Vorlesungsnotizen: Machine Learning

• Kurs: 194.025: Einführung in maschinelles Lernen
• Dozent: Nysret Musliu
• Gruppe: Datenbanken und Künstliche Intelligenz Gruppe (dbai)
• Thema: Automatisiertes Maschinelles Lernen (AutoML)

Motivation: Algorithmusselektion

• Verschiedene maschinelle Lernalgorithmen stehen zur Verfügung, z.B. k-NN, Entscheidungsbäume, Random Forest, Bayes'sche Netze, Support Vector Machines, Neuronale Netze
• Das No-Free-Lunch-Theorem (NFL) besagt, dass kein Algorithmus für alle Probleme die beste Leistung zeigt. Die optimale Wahl des Algorithmus hängt vom Datensatz ab.

Motivation: Hyperparameter-Optimierung

• Maschinelle Lernalgorithmen haben verschiedene Hyperparameter, z.B. k-NN: Anzahl der Nachbarn, Distanzmetrik; Neuronale Netze: Anzahl der Schichten, Aktivierungsfunktionen; Random Forest: Anzahl der Bäume, Anzahl der Features.
• Die Konfiguration der Parameter hat großen Einfluss auf die Ergebnisse.
• Es gibt einen großen Suchraum möglicher Parameterkonfigurationen.
• Wie wählt man die besten Werte für Hyperparameter aus?

Hyperparameter-Optimierung (formale Definition)

• Formaler Problemdefinition des Problems der Hyperparameter-Optimierung
• Ein maschinelles Lernalgorithmus A
• Parameter: Λ₁, ...,Λ_n
• Hyperparameter-Raum: A = Λ₁ ×... × Λ_n
• A: Algorithmus A verwendet die Hyperparameter-Einstellung Λ
• L(AΛ, Dtrain, Dvalid): Validierungsverlust (z.B. Fehlerrate).
• Optimierungsproblem unter k-facher Kreuzvalidierung ist die Minimierung der folgenden Blackbox-Funktion: f(λ) = 1/k Σ(k_i=1 L(Aλ, D_train⁽ⁱ⁾, D_valid⁽ⁱ⁾)

AutoML-Systeme

• Prozess zur Automatisierung des maschinellen Lernens auf einem Datensatz.
• Automatische Optimierung von Hyperparametern
• Automatische Algorithmusselektion
• Automatische Featureselektion, Preprocessing

Algorithmusselektion in Maschinellem Lernen (Metalearning)

• Lernen über das Lernen
• Metalearning akkumuliert Erfahrungen über die Leistung von Algorithmen in mehreren Anwendungen.
• Dynamisch: Modellauswahl, Methodenkombination

Algorithmusselektion mit Rices Framework

• Problemraum (P) und Performance-Raum (Y)
• Feature-Extraktion (f) aus P
• Algorithmenraum (A)
• Auswahl des Algorithmus (a) in A, um Leistung (y) in Y zu maximieren.
• Auswahl-Abbildung S(f(x))

Algorithmus Auswahl Probleme

• Auswahl des richtigen Algorithmus (f)
• Konstruktion von Trainingsdaten (S)
• Komplexität der Berechnungs-, Aufwand von f und H

AutoML Systeme (Beispiele)

• Auto-Sklearn
• Auto-WEKA
• TPOT
• H2O
• Auto-PyTorch

Parameter-Optimierung (Beispiel: SMAC)

• Für die Optimierung von Parametern für beliebige Algorithmen.
• Basiert auf einer Menge von Instanzen.
• Optimierung von kombinatorischen Problemen.
• Hyperparameter-Optimierung für maschinelle Lernalgorithmen.
• Verwendet Random Forest, um pm(f | λ) zu modellieren.

Feature-Raum

• Auswahl geeigneter Features ist sehr wichtig.
• Features müssen eine gewisse prädiktive Aussagekraft haben.
• Verschiedene Charakterisierungen, z.B. statistischer und informationstheoretischer Natur, modellbasiert, Landmarking

Statistische und informationstheoretische Features

• Extraktion von Features aus dem Datensatz (z.B., Anzahl der Attribute, Anzahl der Klassen, Verhältnis von Beispielen zu Attributen, durchschnittliche Klassenentropie, Korrelationsgrad zwischen Features und Zielkonzept)
• Annahme: Lernalgorithmen sind sensibel für die Struktur des Datensatzes.
• Größe des Datasets hat einen Einfluss.

Modellbasierte Charakterisierung

• Eigenschaften der auf einem bestimmten Problem induzierten Hypothesen als indirekte Form der Charakterisierung.
• Entscheidungsbäume wurden betrachtet: Knoten pro Feature, maximale Baumtiefe, Baum-Unbalanciertheit

Landmarking

• Jeder Lernalgorithmus hat eine Klasse von Aufgaben, auf denen er gut performt (Expertisenbereich).
• Die Leistung eines Algorithmus auf einer Aufgabe sagt etwas über die Natur der Aufgabe aus.
• Der Landmarker (Landmark learner) ist ein Lernmechanismus, dessen Leistung zur Beschreibung einer Aufgabe verwendet wird.
• Lokalisieren der Aufgabe im Expertenraum.
• Expertenkarte (Expertise map): Hauptauskunftquelle im Landmarking

Numerischer Aufwand von f und S

• Die Kosten für die Berechnung von f(x) sollten viel geringer sein als die Berechnung von t(x)
• Induktion des Metamodells.
• Kosten der Vorhersage mit dem Metamodell.
• Im Allgemeinen nicht problematisch.

Auswahl von y

• Vorhersagegenauigkeit ist das Hauptkriterium für die Algorithmusselektion.
• Andere Leistungsmaße: Rechenkomplexität, Kompaktheit, Ausdrucksstärke.
• Eine weitere Möglichkeit ist die Rangfolge der Algorithmen nach abnehmender Performance bei jedem neuen Problem werden die Algorithmen nach absteigender Performance geordnet.

Hyperparameter-Optimierung (Methoden)

• Gittersuche (Grid search): Exhaustive Suche aller Kombinationen im Gitter.
• Randomisierte Suche: Zufällige Auswahl von Konfigurationen im Suchraum.
• Sequentielle modellbasierte bayesianische Optimierung (SMBO): Probabilistisches Modell M zur Modellierung von f(x) und Auswahl vielversprechender Eingabewerte zur nächsten Bewertung von f(x)

Automatisierte Überwachte Lernpipeline

• Automatisierung von überwachten maschinellen Lernpipelines (z.B. T-P-O-T)

Metalearning und Hyperparameter-Optimierung

• Hyperparameter-Optimierung ist ein Spezialfall der Modellauswahl.
• Auswahl eines bestimmten Lernalgorithmus kann als Optimierung eines nominalen Hyperparameters aufgefasst werden.
• Vorverarbeitungsschritte wie Daten-Normalisierung können als nominale Hyperparameter behandelt werden.
• Verwendung von Meta-Features zur Initialisierung der Parameter des einzelnen Datensatzes.

Literatur

• Bücher und Artikel (AutoML, Metalearning, Algorithmusselektion, Hyperparameter-Optimierung)

Bias und Fairness in ML

• ML-Systeme können voreingenommen sein
• Fehlerquoten für weiße und schwarze Angeklagte
• Die Bedeutung von Verzerrungen und Fairness bei der Modelltraining
• Wie lässt sich der Verlust bestimmter Gruppen im Datensatz reduzieren?

Fairness-Definitionen (Beispiel)

• Naive Versuche zur Fairness
• Kalibrierung (Fairness Definition 2)
• Gleichgewichtsrate der Fehlerraten (Fairness Definition 3)
• Kompromisse zwischen Fairness-Definitionen

Implikationen der Unmöglichkeits-Ergebnisse

• Es besteht kein einziger Ansatz oder Algorithmus, der in allen Szenarien gerecht und optimal funktioniert.
• Eine Beeinflussung der Fairness ist in der Regel ein Trade-off zwischen verschiedenen Definitionen.
• Die Zusammenarbeit mit Experten aus anderen Bereichen ist entscheidend, um verschiedene Perspektiven und wichtige Aspekte zu berücksichtigen.
• Verschiedene Arten von Verlusten sind unterschiedlich wichtig und bedürfen einer sorgfältigen Abwägung

Fairness durch Unwissenheit

• Berücksichtigung geschützter Attribute bei der Datenanalyse
• Korrelationen, die geschützte Attribute offenbaren
• Auch wenn man diese Attribute entfernt, finden ML-Algorithmen diese Korrelationen trotzdem.

Fairnessdefinition 4: Individuelle Fairness

• Individuelle Fairness: Personen mit ähnlichen Attributen sollten gleich behandelt werden.
• Distanzmass (d(x,x')).
• Distanz der Risiko-Scores S(x) und S(x') zur Distanz zwischen den Merkmalsvektoren d(x, y').
• Vorteile: Berücksichtigung von Heterogenität innerhalb der Gruppen, anwendbar, wenn geschützte Gruppen unbekannt sind.
• Nachteile: Definition geeigneter Distanzmass ist aufwendig

Einige Worte zum Bias

• Das Lernen aus Datasets erfasst auch Bias in den Datasets.
• ML-Algorithmen reproduzieren den Bias in den trainierten Datasets.
• Die Reduktion des Bias im Datensatz ist nicht ausreichend.
• Verschiedene Kosten von Fehlern (z.B.., Krankheit vs. Betrug)

Transparenz von Klassifiziern

• Verwendung von "Modell-Karten"
• Standardliste von Fragen zur Freigabe trainierter Klassifizierer
• Von Google, OpenAI unterstützt, unterstützt durch Hugging Face

Menschen und Risiko-Scores

• Bewusstsein über Bias in ML-Systemen
• Nicht nur technische Lösungen zur Überwindung von Bias
• Darstellung der Ergebnisse als Information, damit der Mensch die Entscheidung trifft
• Schwierige/unbeabsichtigte Folgen.

KPRA-Beispiel (Kentucky Pretrial Risk Assessment)

• Politikänderung (HB463) in Kentucky (2011). Anwendungsbereich: Entscheidungen über die Freilassung (frühe/späte) von Inhaftierten
• Zwei mögliche Entscheidungen (Geldstrafe/Keine Geldstrafe)
• Risiken der Straftäter wurden als niedrig/mittel/hoch kategorisiert (automatisch).
• Berücksichtigung war optional.

Zusammenfassung: Algorithmusselektion und Hyperparameter Optimierung

• Algorithmenselektion und Hyperparameter-Optimierung in der Praxis.
• Vorteile und Nachteile der beiden Methoden.
• Wichtigkeit der Berücksichtigung der Anwendungsszenarien.
• Automatisierte Pipelines

Zusammenfassung: Automatisiertes Maschinelles Lernen

• Der Prozess der Automatisierung des maschinellen Lernens.
• Automatische Optimierung von Hyperparametern
• Automatische Algorithmus-Auswahl.
• Automatisierte Feature-Selektion und Vorverarbeitung.

Zusammenfassung: Metalearning (und Algorithmusselektion)

• Erfassung von Lernerfahrungen über Leistung von ML-Algorithmen in mehreren Anwendungen.
• Umgang mit unterschiedlichen ML-Techniken. - Dynamische Verfahren wie Modellauswahl, Methodenkombination.
• Framewrok für Algorithmusselektion wie Rice's Framework.

Zusammenfassung: Datensatz Bias

• Datensätze können Bias enthalten.
• Die Qualität der Daten beeinflusst die Genauigkeit und Leistung der ML-Modells.
• Der Bias in den Datasets sollte reduziert werden.

Zusammenfassung: Training von DNNs

• Berechnung der Ausgabe des Modells.
• Verlust (Loss) berechnen.
• Gradienten der Verlustfunktion bzgl. jedes Gewichts berechnen.
• Gewichte mithilfe der Gradienten aktualisieren.