Hauptinhalt

Probabilistische Programmierung (Seminar)

Seminar WS 18/19 (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.

 

Die folgende Web-Seite ist noch nicht vollständig atualisiert und wird im September noch ergänzt, insbesondere bzgl. neuer Literatur. Die unten angegeben Termine sind allerdings aktuell, auch die Litertaur zur Einführung wird sich nicht wesentlich ändern.

Ü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 Nutzung und Interpretation dieser Daten zeigt sich aber, dass probabilistische Modelle und Ansätze notwendig sind, um die 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 Aspekte der probabilistischen Programmierung und 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).

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

Einzelne Kapitel beider 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], Kapitel „Patterns of inference“  und „Models for sequences of observations” aus [4]
  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], [12]
  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 [29], [7], [9]
  10. Berechenbarkeit und Komplexität probabilistischer Programme
    [10], [11]

Probabilistische Programmiersprachen und –systeme

  1. FIGARO
    diverse Kapitel aus [3]
  2. WebPPL
    Kapitel „The WebPPL language“ und „WebPPL“ aus [2], [13]
  3. Church
    [14]
  4. Probabilistic C
    [15], [16]
  5. Tabular
    [17], [18], [19]

Anwendungen

  1.  Bestimmung der Zuverlässigkeit fehlertoleranter Programme auf unzuverlässiger Hardware
    [20],  
  2. Bewertung der Fähigkeiten von Spielern in online-Spielen
    [21], [22]
  3. Probabilistische Programmierung in der Computergraphik: Erzeugung von 3D-Modellen aus 2D-Bildern
     [23], [24]
  4. Probabilistische Programmierung im Sicherheitsbereich
    [25], [26]
  5. Anwendungen im Maschinellen Lernen
    [27], [28]

Weiterführende Themen

  1. Nicht terminierende probabilistische Programme
    [30]
  2. Datenparallele Ausführung probabilistischer Programme
    [31], [32]
  3. Probabilistische Programmierung in SDNs
    [33], [34]
  4. Optimierung probabilistischer Programme
    [35]
  5. Probabilistsiche Programmierung und zeitkontinuierliche Modelle
    [36], [37]

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 2018-8-7 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 2018-8-7 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] Benjamin Lucien Kaminski & Joost-Pieter Katoen. On the Hardness of Almost-Sure Termination. MFCS 2015.

[11] NL Ackerman, CE Freer, DM Roy: On the computability of conditional probability.  arXiv preprint arXiv:1005.3014, 2010 - arxiv.org

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

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

[14] Noah D. Goodman, Vikash K. Mansinghka, Daniel M. Roy, Keith Bonawitz & Joshua B. Tenenbaum: Church: a language for generative models. arXiv:1206.3255, 2012 – arxiv.org

[15] Probabilistic C Webpage
http://www.robots.ox.ac.uk/~brooks/probabilistic-c/

[16] Brooks Paige, Frank Wood: A Compilation Target for Probabilistic Programming Languages. arXiv:1403.0504, 2014 – arxiv.org

[17] Tabular Webpage
https://www.microsoft.com/en-us/research/project/tabular/

[18] Andrew D. Gordon, Thore Graepel, Nicolas Rolland, Claudio Russo, Johannes Borgstrom, John Guiver: Tabular: a schema-driven probabilistic programming language. In: Proceeding POPL '14 Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM SIGPLAN Notices49 (1), 2014, 321-334.

[19] Andrew D. Gordon, Claudio Russo, Marcin Szymczak, Johannes Borgström, Nicolas Rolland, Thore Graepel, Daniel Tarlow: Probabilistic Programs as Spreadsheet Queries. In: Vitek J. (eds) Programming Languages and Systems. ESOP 2015. Lecture Notes in Computer Science, vol 9032. Springer, 1-25.

[20] Michael Carbin, Sasa Misailovic, Martin C. Rinard: Verifying  Quantitative  Reliability  for  Programs That  Execute  on  Unreliable  Hardware. Communications of the ACM CACM, Volume 59 Issue 8, August 2016, Pages 83-91 (Vorversion Proc. OOPSLA, 2013)

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

[22] 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/

[23] Short probabilistic programming machine-learning code replaces complex programs for computer-vision tasks. KurzweilAI. April 13, 2015. http://www.kurzweilai.net/short-probabilistic-programming-machine-learning-code-replaces-complex-programs-for-computer-vision-tasks

[24] T. D. Kulkarni, P. Kohli, J. B. Tenenbaum, and V. Mansinghka. Picture: A probabilistic programming language for scene perception. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4390–4399, 2015.

[25] 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.

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

[27] 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.

[28] 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

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

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

[31] 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.

[32] 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.

[33] Nate Foster, Dexter Kozen, Konstantinos Mamouras, Mark Reitblatt, and Alexandra Silva. Probabilistic NetKAT. In ESOP 2016. 282–309.

[34] Steffen Smolka, David Kahn, Praveen Kumar, and Nate Foster. Deciding probabilistic program equivalence in NetKAT. arXiv:1707.02772v2, 2018 - arxiv.org.

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

[36] Pfeffer, A. (2009). CTPPL: A continuous time probabilistic programming language. In Proceedings of the 21st International Joint Conference on Artical Intelligence, pp. 1943-1950.

[37] A. Georgoulas, J. Hillston, D. Milios, G. Sanguinetti. Probabilistic programming process algebra. In Proc. of QEST: The 1th International Conference on Quantitative Evaluation of Systems, Lecture Notes in Comput. Sci., vol. 8657, Springer (2014), pp. 249-264.

            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 Anfang bis 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 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 Em-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