\documentclass[a4paper]{article} \usepackage{myStyle} \usepackage{amsmath} \usepackage{csquotes} \usepackage[inline]{enumitem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Hier eigene Daten einfügen % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\Studiengang}{Informatik (MA)} \newcommand{\Fach}{Probabilistische Planung} \newcommand{\Pruefungsdatum}{04.08.2016} % DD.MM.YYYY \newcommand{\Pruefer}{Dr. Marco Huber} \newcommand{\Beisitzer}{mir unbekannt} % Nicht zwingend, aber es waere nett, wenn du zumindest die Zahl vor % dem Komma angeben koenntest: \newcommand{\Note}{1,0} \newcommand{\Dauer}{45} % in Minuten %%% WEITER SCROLLEN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \DeclareMathOperator*{\argmin}{arg\,min} \begin{document} \begin{tabular}{p{2cm}p{15cm}} \ifpdf\vspace{-0.8cm}\fi \multirow{2}{2cm}{ \includegraphics[width=20mm]{FS-Eule}} & \Large Fragebogen der Fachschaft zu \\ & \Large {\bfseries mündlichen Prüfungen} \\ & \Large{im Informatikstudium} \\ \end{tabular} \begin{tabular}{p{8cm}p{8cm}} \begin{flushleft}Dieser Fragebogen gibt den Studierenden, die nach Dir die Prüfung ablegen wollen, einen Einblick in Ablauf und Inhalt der Prüfung. Das erleichtert die Vorbereitung. Bitte verwende zum Ausfüllen einen schwarzen Stift. Das erleichtert das Einscannen. \\[0.5cm] %%% HIER GEHTS LOS! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Das Dokument % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Dein Studiengang: \Studiengang \\[0.5cm] \textbf{Prüfungsart:}\\ %% entsprechende \boxempty bitte durch \boxtimes ersetzen. $\boxempty$ Wahlpflichtfach \\ $\boxtimes$ Vertiefungsfach \\ $\boxempty$ Ergänzungsfach \\[0.5cm] %% Namen des Wahl/Vertiefungs/Ergaenzungsfachs hier bitte eintragen. Welches? \Fach %% Jetzt kommt ein Barcode von uns. Einfach weitergehen. ;-) \end{flushleft} & \begin{center} Barcode: \begin{tabular}{p{0.2cm}p{6.8cm}p{0.2cm}} $\ulcorner$ \vskip 2cm $\llcorner$ & & $\urcorner$ \vskip 2cm $\lrcorner$ \\ \end{tabular} \end{center} \vskip 0.5cm %% Hier gehts weiter: \begin{flushright} %% Pruefungsdatum, PrueferIn und BeisitzerIn bitte hier eintragen. Wichtig: Im Allgemeinen kann nur ein Professor der Pruefer gewesen sein. \begin{tabular}{ll} Prüfungsdatum: & \Pruefungsdatum \\[0.5cm] Prüfer/-in: & \Pruefer \\[0.5cm] Beisitzer/-in: & \Beisitzer \\ \end{tabular} \end{flushright} \\ \end{tabular} \begin{tabular}{|p{8.2cm}|p{3cm}|p{1cm}|p{3.5cm}|} \multicolumn{4}{l}{\bfseries Prüfungsfächer und Vorbereitung: } \\[0.2cm] \hline Veranstaltung & Dozent/-in & Jahr & regelmäßig besucht? \\ \hline \hline %% Beispiel: %% Interessante Vorlesung & Toller Prof & 2007 & Ich war immer 5 Minuten vorher da \\ Probabilistische Planung & Dr. Huber & SS 2016 & Ja \\[0.2cm] \hline \end{tabular} \\[0.5cm] \begin{multicols}{2} Note: \Note\\[0.5cm] War diese Note angemessen? %% Hier ist Platz fuer deinen Kommentar Ja \columnbreak %% Bitte Pruefungsdauer eintragen Prüfungsdauer: \Dauer{} Minuten \\[0.5cm] \end{multicols} \textbf{\ding{46}} Wie war der \textbf{Prüfungsstil des Prüfers / der Prüferin?} \\ \begin{footnotesize} (Prüfungsatmosphäre, (un)klare Fragestellungen, Frage nach Einzelheiten oder eher größeren Zusammenhängen, kamen häufiger Zwischenfragen oder ließ er/sie dich erzählen, wurde Dir weitergeholfen, wurde in Wissenslücken gebohrt?)\end{footnotesize} \\ \begin{minipage}[t][10cm]{\linewidth} %% Hier ist Platz fuer deinen Kommentar Die Fragen waren klar gestellt. Die Atmosphäre war angenehm; er hat einen viel erzählen lassen. Ich konnte das meiste in Ruhe aufschreiben (einmal hat er gesagt, dass ich die Formel nicht aufschreiben muss) und er hat auch immer Feedback gegeben, dass ich das erzähle was er hören will. Die Fragen waren eigentlich immer klar; bei einer unklaren Frage habe ich direkt nachgehakt ob er XY meint und er hat es auch direkt bejaht. Super angenehm! \end{minipage} \begin{flushright}$\hookrightarrow$\textbf{Rückseite bitte nicht vergessen!}\end{flushright} \newpage \columnseprule=.4pt \begin{multicols}{2} \ding{46} Hat sich der \textbf{Besuch / Nichtbesuch} der Veranstaltung für dich gelohnt? \\ \begin{minipage}[t][6.8cm]{\linewidth} %% Hier ist Platz fuer deinen Kommentar Ja. Teilweise ist die Schrift schwer zu lesen, aber die Zusammenhänge werden klarer und Dr. Huber geht auch wunderbar auf Fragen ein. \end{minipage} \ding{46} Wie lange und wie hast du dich \textbf{alleine bzw. mit anderen vorbereitet}? \\ \begin{minipage}[t][7cm]{\linewidth} %% Hier ist Platz fuer deinen Kommentar Ich habe die Vorlesung 2 mal gehört, mich ca. 2 Monate immer wieder ein bisschen (ca. 2h/Tag) und ca. 2 Wochen intensiv (5h/Tag) vorbereitet. 3 Treffen à ca. 4h mit einem Lernpartner. \end{minipage} \ding{46} Welche \textbf{Tips zur Vorbereitung} kannst du geben? \begin{footnotesize}(Wichtige / Unwichtige Teile des Stoffes, gute Bücher / Skripten, Lernstil)\end{footnotesize} \\ \begin{minipage}[t][7cm]{\linewidth} %% Hier ist Platz fuer deinen Kommentar Folien lesen und verstehen, Protokolle durchgehen und meinen Blog lesen:\\ \href{https://martin-thoma.com/probabilistische-planung/}{martin-thoma.com/probabilistische-planung/} Insbesondere die Tabelle am Ende, wo MDP / POMDP / RL verglichen werden sollte man auswendig können und aus dem FF beherrschen. \end{minipage} \columnbreak \ding{46} Kannst du ihn/sie \textbf{weiterempfehlen}? %% entsprechende \boxempty bitte durch \boxtimes ersetzen. $\boxtimes$ Ja / $\boxempty$ Nein\newline Warum? \\ \begin{minipage}[t][6.8cm]{\linewidth} %% Hier ist Platz fuer deinen Kommentar Sehr nett, angenehme Athmosphäre. \end{minipage} \ding{46} Fanden vor der Prüfung \textbf{Absprachen} zu Form oder Inhalt statt? Wurden sie \textbf{eingehalten}? \\ \begin{minipage}[t][7cm]{\linewidth} %% Hier ist Platz fuer deinen Kommentar Ja. Es wurde gesagt, dass keine Beweise dran kommen. War auch so. \end{minipage} \ding{46} Kannst du Ratschläge für das \textbf{Verhalten in der Prüfung} geben? \\ \begin{minipage}[t][6.8cm]{\linewidth} %% Hier ist Platz fuer deinen Kommentar Mit den Antworten kann man etwas lenken, was als nächstes gefragt wird. Wenn man kurz Nachdenken muss, kann man das auch einfach sagen. \end{minipage} % \end{multicols} \clearpage \section*{Inhalte der Prüfung:} Gedächtnisprotokoll; ich habe sicherlich ein paar Fragen / Details vergessen. \begin{itemize} \item Welche 3 Themen hatten wir in der Vorlesung \item[$\Rightarrow$] MDP (Markov Decision Processes), POMDP (Partially observable MDPs), RL (Reinforcement Learning). Ich habe auch gleich die Agent-Umwelt-Diagramme gezeichnet und daran die Unterschiede erklärt und habe das Explorationsproblem erwähnt. \item Gut. Zuvor hatten wir die Grundlagen mit Wahrscheinlichkeitstheorie, Optimierungs- und Nutzentheorie. Schreiben sie mir doch mal ein allgemeines Optimierungsproblem auf. \item[$\Rightarrow$] \begin{align} \argmin_{x \in \mathbb{R}^n}& f(x)\\ \text{s.t. } & g_i(x) \leq 0 \quad \text{mit } i = 1, \dots, m\\ & h_j(x) = 0 \quad \text{mit } j = 1, \dots, p \end{align} Siehe auch: \href{https://martin-thoma.com/optimization-basics/}{https://martin-thoma.com/optimization-basics/}.\\ Ich habe auch gleich erklärt warum $=0$ genügt und warum man o.B.d.A. von einem Minimierungsproblem ausgehen kann. \item Ok, und was macht man wenn man Gleichungs-Nebenbedingungen hat? \item[$\Rightarrow$] Lagrange-Ansatz: $$\mathcal{L}(x, \lambda_1, \dots, \lambda_p) = f(x) + \sum_{j=1}^p \lambda_j \cdot h_j(x)$$ wobei das nun die notwendigen Nebenbedingungen für ein Optimum liefert, wenn man den Gradienten nach $x$ und den Gradienten nach $\lambda$ bildet und gleich 0 setzt. \item Was passiert bei den Gradienten nach $\lambda$? \item[$\Rightarrow$] Die Gleichungsnebenbedingungen kommen raus. \item Nun kam noch die Sache mit den Höhenlinien / den Gradienten und dem Winkel. \item Ok, verlassen wir die Optimierungstheorie. Was können sie zum Optimalitätsprinzip sagen? \item[$\Rightarrow$] Wenn man ein Problem mit optimaler Substruktur hat, dann gilt für jede optimale Lösung, dass die Lösungen der enthaltenen Teilprobleme optimal sein müssen. Sehr schön kann man das bei der kürzesten Wegesuche sehen. \item Zeigen sie das mal an einem Beispiel. \item[$\Rightarrow$] Wenn der kürzeste Weg von $A$ nach $E$ über $B, C, D$ führt, dann muss der kürzeste Weg von $B$ nach $D$ auch über $C$ führen. Falls das nicht so wäre --- es also einen kürzesten Weg z.B. direkt von $B$ nach $D$ geben würde, dann wäre auch der Weg von $A$ nach $E$ kürzer wernn man direkt von $B$ nach $D$ gehen würde. \item Was hat das mit MDPs zu tun? \item[$\Rightarrow$] Anwendung findet es im Dynamic Programming (Endliche MDPs mit endlichem Horizont). Dabei geht man Rückwärtsrekursiv vor um die Wertefunktion $J$ aus der Kostenfunktion $g$ zu berechnen: \begin{align} J(x_N) &= g_N(x_N)\\ J(x_k) &= \min_{a_k} \left [ g_k(a_k, x_k) + \mathbb{E}\{J_{k+1}(x_k+1) | x_k, a_k\} \right] \end{align} \item Sehr schön, da haben wir auch gleich die Bellman-Gleichungen. Nun hatten wir noch geschlossen lösbare Spezialfälle. Welche sind das? \item[$\Rightarrow$] \begin{enumerate*}[label=(\roman*)] \item Lineare Probleme (LQR) \item Endliche, deterministische Probleme (Label-Korrektur) \item Endliche Probleme mit unendlichem Horizont (Fixpunktsatz, Werteiteration, Bellman-Operator) \end{enumerate*} \item Dann erklären Sie doch mal den LQR. \item[$\Rightarrow$] Zustandsraummodell ist linear und rauschen ist $r \sim \mathcal{N}(0, \Sigma)$: $$x_{k+1} = A_k x_k + B_k a_k + r$$ Objective function ist: $$\mathbb{E} \left ( \underbrace{x_N^T \cdot Q_N \cdot x_N + \sum_{k=0}^{N-1} x_k^T \cdot Q_k \cdot x_k}_{\text{Zustandsabhängige Kosten}} + \underbrace{\sum_{k=0}^{N-1} a_k^T \cdot R_k \cdot a_k}_{\text{aktionsabhängige Kosten}} \right )$$ Der LQR ist dann einfach $$a_k^* = \underbrace{-{(R_k + B_k^T P_{k+1} B_k)}^{-1} \cdot B_k^T \cdot P_{k+1} \cdot A_k}_{\text{Verstärkungsmatrix } L_k} x_k$$ wobei $P_k$ Rückwärtsrekursiv durch die iterativen Riccati-Gleichungen bestimmt werden kann. (Hier wollte ich die aufschreiben, aber bei $P_N = Q_N$ hat er mich gestoppt.) \item Ok, das ist schon gut so. Nur Qualitativ, was machen die Riccati-Gleichungen? \item[$\Rightarrow$] Strukturell sind sie identisch zum Update der Fehlermatrix im Kalman-Filter duch den Update und Prädiktionsschritt. \item Ok, gut. Kommen wir zu POMDPs. Wie löst man die? \item[$\Rightarrow$] Belief-State MDP und Informationsvektor-MDP erklärt, Approximative Lösungen (Abbildung auf geschlossen lösbare Spezialfälle, Funktionsapproximatoren, Änderung der Optimierung) \item Ok. Warum verwendet man in der Praxis eher nicht das Informationsvektor-MDP? \item[$\Rightarrow$] Weil der Zustand in jedem Zeitschritt wächst. In jedem Zeitschritt $k$ kommt eine weitere Aktion $a_k$ hinzu; ggf. auch noch Beobachtungen $z_k$. Will man alles nutzen wird das Programm immer langsamer. \item Sie haben hinreichende Statistiken erwähnt. Was ist das? \item[$\Rightarrow$] (Definition; vgl. mein Blog-Artikel) \item Welche geschlossenen Spezialfälle gibt es bei POMDPs? \item[$\Rightarrow$] Linear (Kalman-Filter + LQR) und endlich ($\alpha$-Vektoren) \item Was ändert sich beim LQR im POMDP-Fall? \item[$\Rightarrow$] $a_k = L_k \cdot \mathbb{E}(x)$ \item Warum ist der Kalman-Filter toll? \item[$\Rightarrow$] Er erfüllt die BLUE-Eigenschaft (Best linear unbiased estimator). Das bedeutet, unter den erwartungstreuen linearen Schätzern ist er derjenige, welcher die geringste Varianz aufweist. \item Welche Annahmen machen wir beim Kalman-Filter? \item[$\Rightarrow$] Additives, mittelwertfreies normalverteiltes Rauschen und ein linearer Zustandsübergang. \item Was passiert, wenn das Rauschen nicht mehr normalverteilt ist? \item[$\Rightarrow$] Man muss die Kovarianz-Matrix berechnen können. Wenn das geht, dann ist der Kalman-filter immer noch der beste lineare Filter (aber es gibt nicht-lineare Filter die besser sind). \item Welche Bedingung muss der Zustandsschätzer für den LQR erfüllen? \item[$\Rightarrow$] Er muss erwartungstreu sein, was der Kalman-filter ja ist. \item Was bedeutet PWLC? \item[$\Rightarrow$] Piece-wise linear and concave. Da wir in der Vorlesung Minimierungsprobleme hatten, war es concave und nicht konvex. PWLC sind bei endlichen POMDPs die Wertefunktionen $J_k$ (Zeichnung des Belief-State / der Aktionen; vgl. Links in meinem Blog). Ich habe noch Pruning erwähnt. \item Wie kann man einfach Pruning durchführen? \item[$\Rightarrow$] Es handelt sich um einen Simplex. (Beispiel mit nur 2 Zuständen aufgezeichnet.) Ein paarweiser Vergleich ist möglich, indem man nur die Endpunkte betrachtet. Wird eine Aktion echt von einer anderen dominiert, so kann diese Entfernt werden. Wird eine Aktion durch Kombinationen von Aktionen dominiert, so könnte man z.B. Algorithmen zur berechnun der Konvexen Hülle nutzen. \item Wie steigt die komplexität des $\alpha$-Algorithmus in jedem Zeitschritt? \item[$\Rightarrow$] Exponentiell (in jedem Zeitschritt sind alle Aktionen prinzipiell wieder möglich) \item Ok, nun zu RL. Welche 3 Gruppen von Lösungsalgorithmen hatten wir? \item[$\Rightarrow$] Modellbasiert, Wertefunktionsbasiert, Strategiesuche. Modellbasiert kann mittels DP zu Wertefunktionsbasiert reduziert werden. Mit argmax kann man dann eine Strategie berechnen. Modellbasiert gibt es Dyna-Q, Adaptive DP und PILCO. Wertefunktionsbasiert hatten wir die Monte Carlo-Verfahren, Temporal Difference und die Kombination mit Eligibility traces. \item Was ist das Exploitation vs. Exploration-Problem? \item[$\Rightarrow$] Im RL kennen wir das Modell nicht. Wir befinden uns sozusagen im Dunkeln und müssen erst finden wo es Rewards gibt. Am Anfang muss man also Explorieren. (Habe eine Grid-World gezeichet und eine Pfad, wo ein Roboter einen Reward von 100 gefunden hat). Nun könnte man die Strategie so aufbauen, dass immer dieser Pfad (versucht wird) zu nehmen. Allerdings kann man auch darauf hoffen, dass an anderer Stelle (eingezeichnet) ein Reward von z.B. 150 ist. Um das herauszufinden muss man von der aktuell \enquote{optimalen} Strategie abweichen und explorieren. \item Wie macht man das? \item[$\Rightarrow$] Durch probabilistische Strategien. Das einfachste ist, dass man am Anfang $\varepsilon \in \mathbb{N}$ Schritte exploriert und dann deterministisch die Strategie benutzt. Besser sind GLIE-Strategien, die theoretisch unendlich oft alle Zustände besuchen. Nennenswert sind $\varepsilon$-Greedy und Softmax. \item Zeichnen sie die Verteilung mal auf, wenn sie 3 Aktionen haben und Aktion 1 optimal ist, Aktion 2 die zweitbeste und Aktion 3 die schlechteste. \item[$\Rightarrow$] Es ergibt sich, dass bei $\varepsilon$-Greedy die nicht-optimalen Aktionen gleichverteilt sind und bei softmax ist die Verteilung vom aktuell geschätzten Wert der Aktion abhängig. Da gibt es noch eine Temperatur $\tau$, welche mit der Zeit sinkt. Am Anfang ist der $Q$-Wert der Aktionen also nicht so wichtig, aber später mehr. Es gibt noch ausgefeiltere Explorations-Strategien welche berücksichtigen wie viel sich in der Q-Funktion noch ändert. \item Ok, dass hatten wir nicht in der Vorlesung. Damit ist die Zeit auch schon rum. \end{itemize} \end{document}