Hauptinhalt

Probabilistische Programmierung (Seminar)

Seminar WS 19/20 (2 SWS, Nr. 041402)

Probabilistische Programmierung

 

Veranstalter: Peter Buchholz (Tel.: (0231) 755 4746),

Email: peter.buchholz@cs.tu-dortmund.de

Sprechstunde: Donnerstag 10:00-11.30 und n.V.

Übersicht

Inhalt

Probabilistische Modelle werden heute in vielen Bereichen der Informatik und darüber hinaus eingesetzt. Anwendungsgebiete sind unter anderem maschinelles Lernen, KI, Robotik, Neurowissenschaften, Zuverlässigkeits- und Sicherheitsanalysen oder auch randomisierte Algorithmen. Viele Modelle werden graphisch oder mit einer Mischung aus graphischen und textuellen Komponenten spezifiziert, oft sind die Darstellungen nur semi-formal.

Probabilistische Programmiersprachen sind ein Ansatz, Programmiersprachen, mit einer wohldefinierten Semantik und Syntax, um Zufallsaspekte anzureichern. Die Ausführung eines Programms kann also durch "das Werfen einer (unter Umständen unfairen) Münze" beeinflusst werden, so dass auch bei vorgegebenen Eingabedaten mehrere Programmabläufe möglich sind. Dies erschwert natürlich erst einmal die Programmanalyse, ein Programm liefert nicht ein Ergebnis, sondern eine Menge von Resultaten, die mit unterschiedlichen Wahrscheinlichkeiten auftreten können. Ein solches Verhalten entspricht aber oft der Realität, die sich deterministisch nicht beschreiben lässt. Auf algorithmischer Ebene sind für manche Problemstellungen randomisierte Algorithmen eine gute Alternative zu deterministischen Algorithmen.

Ansätze zur probabilistischen Programmierung gibt es seit vielen Jahren in unterschiedlichen Varianten. Lange haben die Ideen aber eher ein Nischendasein geführt und wurden nur selten in reale Systeme umgesetzt oder zur Systemanalyse oder -optimierung eingesetzt. Mit der Verfügbarkeit immer größerer Datenmenge und den zugehörigen Entwicklungen im Bereich der Auswertung und Interpretation dieser Daten, z.B. mit Hilfe von KI-Methoden, zeigt sich aber, dass probabilistische Modelle und Ansätze notwendig sind, um die in den Daten vorhandenen Informationen wirklich zu nutzen. Dadurch bedingt haben das Interesse an probabilistischer Programmierung und die Forschung in diesem Bereich in den letzten Jahren deutlich zugenommen.

Wir wollen im Rahmen des Seminars einen Überblick über die probabilistische Programmierung gewinnen. Es sollen sowohl unterschiedliche probabilistische Programmiersprachen, als auch theoretische und anwendungsorientierte Aspekte der probabilistischen Programmierung sowie die Analyse probabilistischer Programme betrachtet werden.

Literatur zur Einführung

Zahlreiche Referenzen findet man auf der Web-Seite http://probabilistic-programming.org.

Ein kurzer Einführungsartikel ist
Brian Hayes: Programs and Probability. American Scientist 103 (5), 2015.

Eine gute Einführung bietet das Buch
Noah D. Goodman, Andreas Stuhlmüller: The Design and Implementation of Probabilistic Programming Languages (online verfügbar).

Eine neuere Übersicht liefert [22].

Wesentlich formaler ist
Dirk Draheim: Semantics of the Probabilistic Typed Lambda Calculus, Springer 2017 (in der TU-Bib als ebook verfügbar).

Einzelne Kapitel der Bücher werden auch für Seminarthemen genutzt.

Themen

Die Themen werden jeweils in Blöcke zusammengefasst. Ein Block umfasst mehrere Seminarthemen. Teilnehmerinnen und Teilnehmer sollten sich zuerst für einen Themenblock entscheiden, sich dort einarbeiten und anschließend ein konkretes Thema festlegen und bearbeiten.  Die angegebene Literatur dient zum Einstieg in das jeweilige Themengebiet. Das Weitersuchen  von Literatur und das Lesen weiterer Artikel ist erwünscht und meistens auch notwendig.

Grundlagen probabilistischer Programmierung

  1. Grundlagen probabilistischer Berechnungen
    Literatur [1], Kapitel „Exploring the executions of a random computation“ aus [2], Kapitel „Probabilistic programming in a nutshell“ und „The three rules of probabilistic inference“ aus [3], Kapitel „Generative Models“ aus [4]
  2. Konditionierung in der probabilistischen Programmierung
    Kapitel „Conditioning“ aus [4], [5], [8]
  3. Probabilistische Modelle probabilistischer Programme
    Kapitel „Probabilistic models and probabilistic programs“ und „Modeling dependencies with Bayesian and Markov networks“ aus [3], [23]
  4. Objektorientierte und hierarchische Modelle probabilistischer Programme
    Kapitel „Object-oriented probabilistic modeling“ aus [3], Kapitel „Hierarchical models“ aus [4]
  5. Die Auswertung probabilistischer Programme
    Kapitel „Exploring the executions of a random computation“, „Early, incremental evidence “ und „Particle Filtering“ aus [2], Kapitel “Factored inference algorithms” aus [3]
  6. Markov Monte Carlo Methoden für probabilistische Programme
    Kapitel „Markov Chain Monte Carlo“ aus [2], Kapitel „Sampling Algorithms“ aus [3], [6]
  7. Berechnung zusammengesetzter Wahrscheinlichkeiten und der wahrscheinlichsten Ursachen einer Beobachtung
    Kapitel „Solving other inference tasks“ aus [3], [10]
  8. Methoden zum Lernen der Parameter stochastischer Modelle
    Kapitel „Dynamic reasoning and parameter learning“ aus [3], Kapitel „Learning as conditional inference“ aus [4]
  9. Terminierung probabilistischer Programme
    Kapitel 4 aus [18], [7], [9].

Probabilistische Programmiersprachen und –systeme

  1. FIGARO
    diverse Kapitel aus [3],[24]
  2. WebPPL
    Kapitel „The WebPPL language“ und „WebPPL“ aus [2], [11]
  3. Probabilistische Programmierung mit Python
    [25],[26]

Anwendungen

  1.  Bewertung der Fähigkeiten von Spielern in online-Spielen
    [12], [13],[32]
  2. Probabilistische Programmierung im Sicherheitsbereich
    [14], [15]
  3. Anwendungen im Maschinellen Lernen
    [16], [17]
  4. Probabilistische Programmierung im Affective Computing
    [27]
  5. Bayes'sche Optimierung mit probabilistischer Porgrammierung
    [28],[29]

Weiterführende Themen

  1. Nicht terminierende probabilistische Programme
    [19]
  2. Datenparallele Ausführung probabilistischer Programme
    [20], [21]
  3. Deep Probabilistic Programming
    [30],[31]

Literatur zu den Seminarthemen

[1]    Noah D. Goodman: The Principles and Practice of Probabilistic Programming. In: ACM SIGPLAN notices, Vol. 48, 2013, Heft 1, S. 399.

[2]    N. D. Goodman and A. Stuhlmüller (electronic). The Design and Implementation of Probabilistic Programming Languages. Retrieved 2019-9-5 from http://dippl.org.

[3]    Avi Pfeffer: Practical Probabilistic Programming. Manning Publications 2016.

[4]    N. D. Goodman and J. B. Tenenbaum (2016). Probabilistic Models of Cognition (2nd ed.). Retrieved 2019-9-5 from https://probmods.org/

[5]    Andreas Stuhlmüller and Noah D. Goodman. Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs. Cognitive Systems Research, 28:80–99, 2014.

[6]    Chung-Kil Hur, Aditya V. Nori, Sriram K. Rajamani, Selva Samuel: A Provably Correct Sampler for Probabilistic Programs. FSTTCS 2015: 475-488

[7]    Benjamin Lucien Kaminski & Joost-Pieter Katoen. On the Hardness of Almost-Sure Termination. MFCS 2015

[8]    Kaminski, Benjamin ; Mciver, Annabelle ; Jansen, Nils ; Gretz, Friedrich ; Olmedo, Federico ; Katoen, Joost-Pieter: Conditioning in Probabilistic Programming. In: ACM Transactions on Programming Languages and Systems (TOPLAS), 40.2018, Heft 1, S. 1 – 50.

[9]    Luis María Ferrer Fioriti and Holger Hermanns. Probabilistic termination: Soundness, completeness, and compositionality. In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '15, pages 489–501, New York, NY, USA, 2015. ACM.

[10] Johan Kwisthout: Most Probable Explanations in Bayesian Networks: complexity and tractability. International Journal of Approximate Reasoning 52 (9), 2011, 1452-1469.

[11] WebPPL Documentation
https://webppl.readthedocs.io/en/master/

[12] Ralf Herbrich, Tom Minka, Thore Graepel: TrueSkill - A Bayesian Skill Rating System. In: Advances in Neural Information Processing Systems (NIPS), 19:569, 2007.

[13] Tom Minka, Ryan Cleven, Yordan Zaykov: TrueSkill 2: An improved Bayesian skill rating system.
https://www.microsoft.com/en-us/research/publication/trueskill-2-improved-bayesian-skill-rating-system/

[14] Piotr Mardziel, Mário S. Alvim, Michael Hicks, Michael R. Clarkson: Quantifying Information Flow for Dynamic Secrets. In: Proceedings of the IEEE Symposium on Security and Privacy (S&P), 2014.

[15] B Ruttenberg, L Kellogg, A Pfeffer: Probabilistic Programming for Malware Analysis. arXiv:1603.08379, 2016 - arxiv.org.

[16] Brenden M. Lake, Ruslan Salakhutdinov, Joshua B. Tenenbaum: Human-level concept learning through probabilistic program induction. Science, vol. 350, no. 6266, pp. 1332–1338, 2015.

[17] Gaunt,  Alexander  L.,  Brockschmidt,  Marc,  Singh, Rishabh,  Kushman,  Nate,  Kohli,  Pushmeet,  Taylor,  Jonathan,  and Tarlow,  Daniel.    Terpret:  A probabilistic programming language for program induction. arXiv:1608.04428, 2016 – arxiv.org

[18] Dirk Draheim: Semantics of the Probabilistic Typed Lambda Calculus. Springer 2017.

[19] Thomas Icard.  Beyond almost-sure termination.  In Proc. 39th CogSci, 2017.

[20] Tristan, J.-B., Huang, D., Tassarotti, J., Pocock, A. C., Green, S., Steele, G. L. Augur: Data-Parallel Probabilistic Modeling. In Advances in Neural Information Processing Systems 28 (2014), Neural Information Processing Systems Foundation, pp. 2600–2608.

[21] Daniel Huang, Jean-Baptiste Tristan, Greg Morrisett: Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling. ACM SIGPLAN Notices - PLDI '17, Volume 52 Issue 6, June 2017, Pages 111-125.

[22] Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, Frank Wood. An Introduction to Probabilistic Programming. arXiv: 1809.10756v1, Sept. 2018.

[23] Adnan Darwiche. Bayesian Networks. Comm. of the ACM 53 (2): 80-90, 2010.

[24] Figaro Web-Seite https://www.cra.com/work/case-studies/figaro

[25] John Salvatier, Thomas V Wiecki, Christopher Fonnesbeck. Probabilistic programming in Python using PyMC3. PeerJ Computer Science 2:e55. https://doi.org/10.7717/peerj-cs.55

[26] PyMC3 Web-Seite https://github.com/pymc-devs/pymc3

[27] Desmond C. Ong, Harold Soh, Jamil Zaki, and Noah D. Goodman. Applying Probabilistic Programming to Affective Computing. Accepted for IEEE Trans. on Affective Computing.

[28] Tom Rainforth, Tuan-Anh Le, Jan-Willem van de Mennt, Michael A. Osborne, Frank Wood. Bayesian optimization for probabilistic programs. In Advances in Neural Information Processing Systems. 280-288, 2016.

[29] Willie Neiswanger, Kirthevasan Kandasamy, Barnabás Póczos, Jeff Schneider, and Eric P. Xing. ProBO: Versatile Bayesian Optimization Using Any Probabilistic Programming Language. arXiv 1901.11515v2, July 2019.

[30]Dustin Tran, Matthew D. Hoffman, Dave Moore, Christopher Suter. Simple, Distributed, and Accelerated Probabilistic Programming.In Proc. 32nd Conference on Neural Information Processing Systems (NeurIPS 2018).

[31] Guillaume Baudart, Martin Hirzel, Louis Mandel. Deep Probabilistic Programming Languages: A Qualitative Study. arXiv 1804.06458v1, July 2018.

[32] Catherine Olsson, Surya Bhupatiraju, Tom Brown, Augustus Odena, Ian Goodfellow. Skill Rating for Generative Models. arXiv 1808.04888v1, August 2018.

            Organisatorisches

            Das Seminar findet als Kompaktseminar im Februar 2020 (voraussichtlich in der Woche vom 3.-7. Februar 2020) statt.

            Ein erstes Treffen zur Themenvergabe findet voraussichtlich Mitte November 2019 statt.

            Anmeldungen (mit Namen + Mat.Nr.) werden per E-Mail (an peter.buchholz@cs.tu-dortmund.de) angenommen.

            Da die Teilnehmerinnen-/Teilnehmerzahl ist auf 20 beschränkt ist, erfolgt die Platzvergabe nach Eingang der Anmeldungen.

            Für eine erfolgreiche Teilnahme am Seminar ist die Anwesenheit bei allen Vorträgen zwingend notwendig. Ferner muss ein ca. 45minütiger Vortrag über ein Thema gehalten werden, die Diskussion zum Vortrag muss vorbereitet und geleitet werden und eine Ausarbeitung zum Thema im Umfang von ca. 10-15 Seiten ist zu erstellen. Ausarbeitungen sollen mit LaTeX unter Nutzung des llncs Stils erstellt werden und müssen mit pdflatex erzeugt werden können. Die Ausarbeitung muss in einer ersten Version vor dem Seminartermin vorliegen!

            Last not least einige Tipps zum Erstellen und Halten von Semiarvorträgen:

            1. Der perfekte Seminarvortrag, A. Zeller, Universität des Saarlandes, Saarbrücken
            2. How to give a good research talk, S. Peyton Jones, Microsoft Research, Cambridge

            Termine

            VoraussichtlicheTermine, die sich noch ändern können

            • Anmeldung: ab Anfang September bis Mitte November bzw. bis alle Plätze vergeben sind (Vergabe nach First Come First Served)
              Anmedlung per E-Mail an peter.buchholz@cs.tu-dortmund.de
            • Erstes Treffen: Mitte November
            • Skizze und Gliederung: Anfang Januar 2020
            • Erste Version Ausarbeitung: Anfang Februar
            • Seminar: voraussichtlich in der  Woche vom 3.-7.  Februar 2020
            • Abgabe endgültige Version Ausarbeitung: Ende März 2020