Seminar Spieltheorie im maschinellen Lernen

Seminar im Sommersemester 2013. Michael Großhans, Ph.D. Blaine Nelson, Prof. Tobias Scheffer.


Termine

Die Veranstaltung umfasst 2 SWS (3 LP). Das Seminar findet als Blockveranstaltung statt.


Inhalte

Das Seminar beschäftigt sich mit der Verwendung spieltheoretischer Konzepte im Kontext des Maschinellen Lernens.

Viele Algorithmen des maschinellen Lernens setzen voraus, dass Trainings- und Testdaten die gleiche Verteilung zugrunde liegt. Diese Annahme spiegelt nicht immer die Realität in geeignetem Maße wider. Durch zufällige Störungen der Daten oder gezieltes Beeinflussen dieser durch einen Gegenspieler können die Testdaten zur Anwendungszeit stark von denen abweichen, die zur Trainingszeit verfügbar waren. Dies kann die Qualität des gelernten Modelles erheblich beeinträchtigen.

Während sich ein Großteil der vorgestellten Algorithmen wie Invar-SVM und Minimax Probability Machine auf die Modellierung eines Nullsummenspieles und der damit verbundenen Minimax-Lösung stützen, werden auch Algorithmen vorgestellt, die auf komplexeren Lösungsmodellen wie Stackelberg- oder Nashgleichgewichten basieren.




Zusatzliteratur


Vorraussichtliche Themen

Nr Thema Literatur
1 Lernen mit Invarianzen

Beim Lernen mit Invarianzen besteht das Ziel darin, Modelle zu lernen, welche auch dann noch eine hohe Qualität besitzen, wenn bestimmte Transformationen auf die Daten angewandt werden. Ein möglicher Anwendungsfall ist beim Lernen aus Bilddaten gegeben. Hier verändern Transformationen wie Rotation, Skalierung und Verschiebung oftmals nicht den Inhalt des Bildes, jedoch die Features, welche zum Lernen benutzt werden.		 [1], [2]
2 Zufällige Störung der Features zur Testzeit

Ein Spezialfall des Lernens mit Invarianzen ist gegeben, wenn angenommen wird, dass einige der Feature welche zum Lernen benutzt werden, durch Rauschen gestört werden oder zur Testzeit sogar komplett ausfallen. Modelle die sich auf hauptsächlich gestörte Features stützen verlieren somit zur Testzeit stark an Qualität und es werden zusätzliche Mechanismen benötigt um Robustheit bezüglich des Unterschiedes zwischen Trainings- und Testdaten zu erreichen. 		[3], [4]
3 Minimax Probability Machine

Ziel der Minimax Probability Machine ist es, die Wahrscheinlichkeit einer Fehlklassifikation zu minimieren. Mit Hilfe eines Nullsummenspieles, bei dem ein zweiter Spieler die Verteilung der Daten unter gewissen Einschränkungen wählen kann, werden explizite Verteilungsannahmen an die Daten vermieden und die Generalität des Modells erhöht. 		[5], [6]
4 Robuste Regression

Ähnlich zur robusten Klassifikation wird bei der robusten Regression angenommen, dass einige der Features, welche zum Lernen benutzt werden, durch Rauschen gestört werden. Die Einschränkung auf eine quadratische Verlustfunktion und bietet hier die Möglichkeit effiziente und robuste Lösungsalgorithmen zu entwickeln. 		[7], [8]
5 Online Learning

Das sogenannte “Online Learning” oder “Learning from Experts” besitzt einige wesentliche Gemeinsamkeiten mit dem Lösen von Nullsummenspielen. Mit Hilfe der verwendeten Algorithmen ist es möglich durch wiederholtes Spielen Gleichgewichte in endlichen Spielen mit gemischten Strategien approximativ zu berechnen. 		[9], [10], [11]
6 Vorhersagespiele nach Nash

Bei Vorhersagenspielen ist die Modellierung als Nullsummenspielen in vielen Fällen zu pessimistisch. Das Ziel des Gegenspielers besteht hierbei nicht darin, das gelernte Modell so schlecht wie möglich zu machen. Vielmehr besitzt der Gegenspieler eigene Zielvorstellungen und Kosten die beachtet werden müssen. Die Existenz und Eindeutigkeit eines Gleichgewichtes nach Nash für gegebene Daten und Kostenfunktionen sind hierbei wesentlicher Bestandteil der Untersuchung. 		[12], [13]
7 Vorhersagespiele nach Stackelberg

Kann der Gegenspieler die Möglichkeit die Daten nach seinen Vorstellungen und in Reaktion auf das gelernte Modell zu verändern sollte ein Gleichgewicht nach Stackelberg aus Sicht des Lerners angestrebt werden. Durch das Ausnutzen des asymmetrischen Informationsflusses kann eine höhere Qualität des gelernten Models erreicht werden. 		[14], [15]


Literatur

[1] DeCoste, D. and Schölkopf, B. "Training invariant support vector machines". Machine Learning, 46:161–190, 2002.
[2] Teo, C. H., Globerson, A., Roweis, S. T. and Smola, A. J. "Convex learning with invariances". In Advances in Neural Information Processing Systems, 2008.
[3] El Ghaoui L., Lanckriet G. R. G. and Natsoulis, G. "Robust classification with interval data". Technical Report UCB/CSD-03-1279, EECS Department, University of California, Berkeley, 2003.
[4] Globerson, A. and Roweis, S. "Nightmare at test time: Robust learning by feature deletion". International Conference on Machine Learning, 2006.
[5] Lanckriet G. R. G., El Ghaoui L., Bhattacharyya, C. and Jordan, M. I. "A robust minimax approach to classification". The Journal of Machine Learning Research 3:555-582
[6] Huang, K., Yang, H., King, I., Lyu, M. R., & Chan, L. (2005). "The minimum error minimax probability machine". Journal of Machine Learning Research, 5(2), 1253.
[7] El Ghaoui, L. and Lebret, H. "Robust solutions to least-square problems with uncertain data". Siam Journal Matrix Analysis and Applications, 18(4):1035-1064, 1997
[8] Sayed, A. H. and Chen, H. "A uniqueness result concerning a robust regularized least-squares solution". Systems and Control Letters, 46(5):361-369, 2002.
[9] Blum, A. and Monsour, Y. "Learning, Regret Minimization and Equilibria". Chapter in Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani, eds, Cambridge University Press, 2007.
[10] Freund, Y. and Schapire, R. "Adaptive game playing using multiplicative weights". Games and Economic Behaviour, 29:79-103, 1999
[11] Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. "Regret minimization in games with incomplete information". Advances in Neural Information Processing Systems 20, pp905-912, 2008.
[12] Brückner, M., Kanzow, C. and Scheffer, T. "Static Prediction Games for Adversarial Learning Problems". In Journal of Machine Learning Research (JMLR), 12: 2617-2654, 2012.
[13] Dalvi, N. , Domingos, P. , Sumit, M. , and Verma, S.D. "Adversarial classification". Proceedings of the Tenth International Conference on Knowledge Discovery and Data Mining, 2004.
[14] Brückner M. and Scheffer, T. "Stackelberg Games for Adversarial Prediction Problems". Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2011.
[15] Liu, W. and Chawla, S. "A game theoretical model for adversarial learning". In ICDM Workshops, pages 25–30. IEEE Computer Society, 2009.