Prediction Games: Robust, Parallel Machine Learning Algorithms
Final Report Abstract
Das Forschungsgebiet maschinelles Lernen umfasst Probleme der Modellbildung aus Daten und der Vorhersage zukünftigen Verhaltens der in den Daten reflektierten Systeme. Ein Großteil der Ergebnisse des Gebietes basiert auf der Annahme, dass verfügbare Daten und zukünftiges Verhalten des Systems derselben Wahrscheinlichkeitsverteilung folgen. Diese Annahme stellt eine unangemessene Vereinfachung dar, wenn ein aktiver Gegner Einfluss auf das zukünftige Verhalten des Systems nehmen kann. Dies ist beispielsweise bei der Erkennung von Phishing- Angriffen und Kreditkartenbetrug der Fall. Im Projekt „Prädiktionsspiele“ haben wir derartige Lernprobleme mit Hilfe spieltheoretischer Paradigmen modelliert; wir bezeichnen diese Probleme als Prädiktionsspiele. Wir konnten Bedingungen identifizieren, unter denen statische Nicht-Nullsummen-Prädiktionsspiele eindeutige Gleichgewichtspunkte besitzen; diese stellen optimale Lösungen dar, wenn Lerner und Gegner die Minimierung ihrer jeweiligen Kosten anstreben. Wir haben primale und duale Lernalgorithmen für statische Prädiktionsspiele hergeleitet, bei denen Lernverfahren und Gegner gleichzeitig, ohne Kenntnis der Aktion ihres jeweiligen Gegenspielers agieren müssen. Wir haben dabei Klassifikations- und Regressionsprobleme analysiert. Ebenso haben wir Verfahren für Lernprobleme hergeleitet, bei denen das Lernverfahren zuerst agiert und der Gegner auf das Modell des Lernverfahrens reagieren. Neben Lernproblemen, bei denen beide Spieler über die Kostenfunktion ihres jeweiligen Gegners informiert sind haben wir Lernprobleme mit Unsicherheit über die Kostenfunktion des Gegners untersucht, Lernverfahren für Bayes’sche Prädiktionsspiele hergeleitet und untersucht. Im Kontext der Spam-Filterung zeigt sich empirisch, dass spieltheoretische Lernverfahren robuster gegenüber Angriffen sind als Lernverfahren, die keinen aktiven Gegner berücksichtigen. Es zeigt sich jedoch auch, dass spieltheoretische Lernverfahren zu komplexen Optimierungsproblemen führen, die für große Datensätze in der Praxis nicht unmittelbar handhabbar sind. Wir haben zwei parallelisierbare Ansätze zur Lösung des Optimierungsproblems entwickelt und untersucht: einen auf inexact line search basierenden Ansatz und einen auf der Arrow-Hurwicz-Uzawa-Methode basierenden Ansatz zum bestimmen des Sattelpunktes der Nikaido-Isoda-Funktion. Beide Ansätze können Batch-parallel implementiert werden und eignen sich für eine Umsetzung innerhalb des Map-Reduce-Paradigmas. Aus praktischer Sicht stellt es sich als besser heraus, unter der IID- Annahme Batch-parallel trainierte Modelle zu aggregieren, sobald die Rechenzeit und nicht die Verfügbarkeit von Daten zum limitierenden Faktor wird. Wir haben alle entwickelten Verfahren im Hinblick auf die Erkennung von Email-Spam evaluiert. Zusätzlich haben wir die Erkennung von DDoS-Angriffen untersucht und dafür ein Online- Stochastic-Policy-Gradient-Verfahren für das Decoding eines strukturierten Vorhersageproblems entwickelt.
Publications
-
(2011). Stackelberg Games for Adversarial Prediction Problems. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Brückner, M., und Scheffer, T.
-
(2012). Prediction Games: Machine Learning in the Presence of an Adversary. Dissertation, Universität Potsdam
Brückner, M.
-
(2012). Static Prediction Games for Adversarial Learning Problems. In Journal of Machine Learning Research, Volume 12, 2617-2654
Brückner, M., Kanzow, C., & Scheffer, T.
-
(2013). Bayesian Games for Adversarial Regression Problems. In Proceedings of the 30th International Conference on Machine Learning
Großhans, M., Sawade, C., Brückner, M., & Scheffer, T.
-
(2015) Solving prediction games with parallel batch gradient descent. Proceedings of the European Conference on Machine Learning
Großhans, M. Scheffer, T.
-
(2016) Learning to control a structured-prediction decoder for detection of HTTP-layer DDoS Attacks. Machine Learning 106 (2-3): 385-410
Dick, U. and Scheffer, T.
