Title: pof

Q: What makes belief revision difficult?
A: When new information is introduced, belief revision can be performed in several different ways.
For example, if we know \(A\), \(B\) and \(A \land B \Rightarrow C\), and we learn \(\lnot C\), we can establish consistency by removing any of the three previously known facts.

Q: What are the two different kinds of belief change?
A: • Belief update: new information is about the situation at present, while the old beliefs refer to the past
• Belief revision: old & new beliefs refer to the same situation, an inconsistency exists

Q: What are the possible actions for belief revision in settings in which all beliefs refer to the same situation?
A: • contraction: removal of a belief
• expansion: addition of a belief without checking consistency
• revision: addition of a belief while maintaining consistency
• extraction: extracting a consistent set of beliefs and/or epistemic entrenchment ordering
• consolidation: restoring consistency of a set of beliefs
• merging: fusion of two or more sets of beliefs while maintaining consistency

Q: What are the AGM postulates?
A: The AGM postulates are properties that an operator that performs belief revision should satisfy in order for that operator to be considered rational.

Q: What are the mathematical objects and their relations considered in belief revision?
A: Given: a deductively closed set of logical formulae \(K\) (the belief set), a new logical formula \(P\), a binary operator \(*: K \times P \rightarrow K\), and a binary operator \(+\) so that \(K+P\) is the deductive closure of \(K \cup \{P\}\).

Q: Who are the AGM postulates named after?
A: Alchourrón, Gärdenfors, and Makinson

Q: How many AGM postulates are there?
A: 6+2=8 (six basic ones, and two additional ones)

Q: In the context of belief revision, what is contraction?
A: Contraction is the operation of removing a belief \(P\) from a knowledge base \(K\); the result of this operation is usually denoted by \(K÷P\).

Q: In the context of belief revision, what are the Levi and Harper identities?
A: The Levi and Harper identities relate belief revision and belief contraction:
\(K*P=(K÷ \lnot P)+P\)
\(K÷P=K\cap (K* \lnot P)\)

Q: State the recovery postulate in the context of belief revision.
A: \(K=(K÷P)+P\)

Q: What is the relation between belief contraction and belief revision?
A: Whatever postulates a revision operator fulfills, the equivalent contraction operator fulfills the equivalent postulates.

Q: What is the Ramsey test?
A: When trying to test whether \(b\) were true if \(a\) were true (also written \(a>b\)), with a given set of beliefs \(K\), the Ramsey test is formalized as:
\(a>b \in K\) iff \(b \in K*a\)

Q: State the Gärdenfors triviality result.
A: There is no non-trivial revision operator that satisfies both the AGM postulates for revision and the condition for the Ramsey test,
unless counterfactual formulae like \(a>b\) (if \(a\) were true, then \(b\) would also be true) can be present in belief sets.

Q: How does one deal with the fact that belief sets can be infinite in size?
A: They are finitely represented, equivalent belief sets are considered equal when revising.
This is called the principle of irrelevance of syntax.

Q: What is the problem with the principle of irrelevance of syntax?
A: Example: \(\{a,b\}* \lnot a \equiv \{\lnot a, b\}\), while
\(\{a \land b\}*\lnot a \equiv \{\lnot a\}\), but \(\{a,b\}\) and \(\{a \land b\}\) are equivalent!
In short, this makes belief revision inconsistent.

Q: What is the foundational approach to belief revision?
A: The basic principle is that retracting a non-derived piece of knowledge should lead to retracting all its consequences that are not otherwise supported.

Q: What is the coherentist approach to belief revision?
A: The coherentist approach is counter to the foundational approach and works with deductively closed belief sets.

Front: What is a privileged group in economics?
Back: A privileged group is a situation in the context of public goods problems in which at least one agent benefits more from a public good than its production cost.

Front: What is the minimal effects hypothesis?
Back: The minimal effects hypothesis states that political campaigns only marginally persuade and convert voters.

Front: When was the minimal effects hypothesis formulated?
Back: Between the 1940s and the 1960s.

Front: What is the empirical state of the minimal effects hypothesis?
Back: When it was developed in the 1940s, it seemed on solid empirical ground, but has been criticized since the 1980s (stating that voters with uncertainties about the positions of candidates switch relatively easily).

Front: When merging two knowledge bases, what are the two cases that need to be distinguished?
Back: • Arbitration: arbitrating two knowledge bases \(K\) and \(T\) entails \(K \lor T\) – as much information as possible is retained.
• Majority: when merging \(K\) and \(T\), the result can be forced to entail \(K\) by adding many knowledge bases similar to \(K\) (similar to majority voting).

Front: What is an example of an arbitration operator?
Back: Classical disjunction \(\lor\).

Front: When is a vector of random variables heteroscedastic?
Back: If the variability of the random disturbance (e.g. the variance) is different across different elements of the vector.

Front: What does humanity do with low-level radioactive waste?
Back: Near-surface disposal for of waste, which is satisfactory.

Front: What does humanity do with high-level radioactive waste?
Back: First it is allowed to decay, ideally for ~50 years. Then we would want to perform deep geological disposal.

Front: What percentage of nuclear waste is low-level waste?
Back: ~90%

Front: What kinds of containers are used for high-level nuclear waste?
Back: Usually a copper container with a steel insert to contain the spent fuel, inside a betonite buffer.

Front: How deep would high-level nuclear waste be stored?
Back: ~400-500m

Front: Why are geological salt environments good for storing nuclear waste?
Back: Very low rate (or even absence) of groundwater flow, excavations are self-healing due to creep of the salt

Front: What is a linear classifier?
Back: It's a classifier that determines the classification based on the linear combination of some features.

Front: What is the formula for a linear classifier?
Back: \(• \text{ if } 0>\mathbf{w}^T \mathbf{x}-β\), \(\circ\) otherwise, where
\(•, \circ\) are the classifications, \(\mathbf{w}\) is a weight vector, \(\mathbf{x}\) is an input vector, and \(β\) is a bias.

Front: For a set of classes \(ω_j\) and a set of measurements \(\mathbf{x}\), what is the optimal decision function (i.e. classification)?
Back: The one that maximizes the probability of the class given the evidence:
\(\underset{j}{\text{argmax }} P(ω_j|\mathbf{x})\)

Front: For a set of \(C\) classes \(ω_j\) and a given set of measurements \(\mathbf{x}\), what is the probability of error for an optimal Bayes classifier?
Back: \(P(E|\mathbf{x})=\text{min}\{P(ω_1|\mathbf{x}), \dots, P(ω_C|\mathbf{x})\}\)

Front: For a set of \(C\) classes \(ω_j\) and a set of measurements \(\mathbf{x}\), give the formula for the expected error of a maximally accurate classifier.
Back: \(P(E)=\int_{x} P(E|\mathbf{x})P(\mathbf{x})d\mathbf{x}\)

Front: Describe the Perceptron Learning Algorithm.
Back: Input: dataset \(\mathbf{x}\), classifications \(\mathbf{y}\), learning rate \(η\).
Output: weights \(\mathbf{w}\).
• Initialize the weights \(\mathbf{w}\) randomly
• While there are misclassified data points
    • Pick a random misclassified datapoint \(\mathbf{x}_m\)
    • Update the weights using the formula \(\mathbf{w}_{\text{new}} \leftarrow \mathbf{w}_{\text{old}} + η \mathbf{x}_m y_m\)
• Stop when there is no misclassified data

Front: State the expected utility theorem.
Back: If a preference relation \(\preceq\) satisfies the axioms of utility theory, then there exists a utility function \(u : O \mapsto [0,1]\) such that \(\ell_1 \preceq \ell_2\) iff \(EU(\ell_1) \le EU(\ell_2)\).
Utility function \(u : O \mapsto ℝ\), lotteries \(\ell \in \mathcal{L}\), and \(EU(\ell)\) the expected utility of \(\ell\).

Front: How do you call the multi-dimensional generalization of effect size?
Back: Mahalanobis distance.

Front: Do canisters for high-level waste contain an option to re-open them & handle the waste again?
Back: No.

Front: What are the three important metrics for storage of radioactive waste?
Back: • Seismic tolerance (measured in Gal)
• Heat load (measured in kW)
• Radioactive absorbtion

Front: What is the unit Gal?
Back: It's the unit used for acceleration. One gal is \(1 \frac{\text{cm}}{s^2}\).

Front: What is the problem with sea disposal of radioactive waste?
Back: Not permitted by international agreements.

Front: What is the problem with the disposal of nuclear waste at subduction zones?
Back: Not permitted by international agreements.

Front: How would nuclear waste disposal through rock melting work?
Back: Very hot nuclear HLW would be place in a deep borehole, melting and diluting itself into the sorrounding rock.

Front: What does "Tenorm" stand for?
Back: "Technologically enhanced naturally occuring radioactive material"

Front: What is the source of the largest Tenorm waste stream?
Back: Coal ash.

Front: How much coal ash is released each year?
Back: 280 megatons.

Front: What radioactive materials does coal ash carry?
Back: Uranium-238 (and its decay products) and thorium-232 (and its progeny).

Front: How do humans deal with radioactive coal-ash?
Back: Bury it.

Front: What is the basic idea of the model-based approach to learning from data?
Back: We assume that the data is generated from a certain distribution, and then try to estimate the parameters of the distribution that best fit the few observations we have.

Front: What is the goal of Maximum Likelihood Estimation?
Back: Let \(\{p(\mathbf{x}|ϕ), ϕ \in Φ\}\), be a set of density functions with \(ϕ\) being the parameter vector (e.g. mean/covariance), and given a dataset \(\mathcal{D}=(\mathbf{x}_1, \dots, \mathbf{x}_N)\) of i.i.d. datapoints generated by \(p\).
Maximum Likelihood Estimation then wants to find the parameter
\(\underset{ϕ}{\text{argmax }} p(\mathcal{D}|ϕ)\)
that best predicts the data.

Front: Where is the maximum of a continuously differentiable and concave multidimensional function \(f(ϕ)\)?
Back: At the point where the gradient is zero.
\(∇_ϕ f(ϕ)=[∂f/∂ϕ_1, ∂f/∂ϕ_2, \dots, ∂f/∂ϕ_h]^T=\mathbf{0}\).

Front: What is the distinction between Maximum Likelihood Parameter Estimation and Bayes Parameter Estimation?
Back: MLE wants to find the parameter that maximizes the probability of the data, BPE wants to compute a probability distribution over parameters given the data.
• MLE: \(θ_o=\underset{θ}{\text{argmax }} p(\mathcal{D}|θ)\)
• BPE: \(p(θ|\mathcal{D})\)

Front: How does one compute a Bayes Parameter Estimation \(p(θ|\mathcal{D})\)?
Back: \(p(θ|\mathcal{D})=\frac{p(\mathcal{D}|θ)p(θ)}{\int_θ p(\mathcal{D}|θ)p(θ)dθ}\)
Simple application of Bayes' theorem.

Front: Given a distribution of parameters given the data (\(P(ω_i|\mathcal{D})\)) and a set of datapoints \(\mathbf{x}\), how does one compute the Bayes classifier of the class \(ω_i\)?

Front: What is a herb that could be helpful against kidney stones?
Back: Chanca Piedra.

Front: What portion of radioactive waste is classified as High-Level Waste?
Back: 0.2%

Front: How much waste does a nuclear reactor produce per year?
Back: 25-30 tonnes

Front: How much less dangerous is radioactive used fuel after being stored for 40 years?
Back: A thousand times

Front: How heavy is a type B cask for transporting nuclear waste?
Back: 125 tons

Front: How long does it take for HLW to return to radioactivity levels of the mined ore?
Back: 1,000 to 10,000 years

Front: What portion of electricity cost from nuclear power comes from disposal costs?
Back: ~10%

Front: What is the background rate of nuclear exposure?
Back: 2-3 millisieverts.

Front: What is the regulatory limit for occupational radiation exposure?
Back: 20 millisieverts per year.

Front: What is the payoff matrix for the prisoner's dilemma?

Front: Give the definition of a Finite Normal-Form Game.
Back: A finite normal-form game is a tuple \((N, A, u)\) where
• \(N\) is the set of players
• \(A=A_1 \times \dots \times A_n\) where \(A_i\) is a finite set of actions available to \(N_i\)
• \(u=(u_1, \dots, u_n)\) where \(u_i: A \mapsto ℝ\) is a utility function for \(N_i\)

Front: In game theory, what is an action profile?
Back: A vector of actions \(a=(a_1, \dots, a_n) ∈ A\) for all players in a normal form game.

Front: How are normal-form games usually represented?
Back: For \(n\) players, the game is represented as an n-dimensional matrix containing the payoffs for corresponding actions for the players.

Front: In game theory, what is a common-payoff game?
Back: A game in which, no matter the outcome, every player receives the same utility.
More formally, a game where for all actions profiles \(a\) and any pair of agents \(i, j \in N\) it is the case that \(u_i(a)=u_j(a)\).

Front: How do you generate correlated data?
Back: Two different options:
• Start with uncorrelated data and apply a linear transformation to the resulting data
• Use a correlated version of the underlying probability distribution

Q: Zero-sum games are strategically equivalent to [...]
A: constant-sum games.

Front: What is the payoff matrix for the game Bach or Stravinsky?

Front: In game theory, what is the support of a mixed strategy?
Back: The set of actions in the strategy with probability >0.
Formally, the support of a mixed strategy \(s_i\) for a player \(i\) is \(\text{supp}(s_i)=\{a \in A_i: s_i(a_i)>0\}\).

Front: In game theory, how does one calculate the expected utility of a strategy profile \(s=(s_1, \dots, s_n)\) for the player \(i\)?
Back: Sum over all utilities, then multiply the probabilities for all possible strategies used.
\(u_i(s)=\sum_{a \in A} u_i(a) \prod_{j=1}^{n} s_j(a_j)\)

Front: In game theory, how is pareto-domination defined?
Back: A strategy profile \(s\) dominates \(s'\) if the utilities for all players for \(s\) are \(\ge\) than for \(s'\), and some player strictly prefers \(s\).

Front: In game theory, define Pareto optimality.
Back: A strategy is Pareto optimal if there is no other strategy that Pareto dominates it.

Front: In game theory, what is the best response for a player \(i\)?
Back: Given a strategy profile \(s_{-i}\) for all other players, the best response is a mixed strategy that maximizes expected utility for the player \(i\).
I.e., the expected utility of the best response is \(\ge\) any other strategy.

Front: In game theory, what does \(s_{-i}\) stand for?
Back: A strategy profile with the strategy for player \(i\) missing.
\(s_{-i}=(s_1, \dots, s_{i-1}, s_{i+1}, \dots, s_n)\)

Front: What is a Nash equilibrium?
Back: A Nash equilibrium is a strategy profile \(s=(s_1, \dots, s_n)\) so that for all players \(i\), \(s_i\) is a best response to \(s_{-i}\).
In a Nash equilibrium, no player wants to change their strategy unilaterally.

Q: Every [...] has at least one Nash equilibrium.
A: normal-form game with a finite number of players and action profiles

Front: In game theory, what is domination?
Back: A strategy \(s_i\) dominates another strategy \(s_i'\) if, for all strategies of the other players, \(s_i\) has a higher utility than \(s_i'\).

Front: In game theory, what is the difference between strict domination, weak domination and very weak domination?
Back: • For strict domination, the expected utility of \(s_i\) must be strictly greater than the expected utility for \(s_i'\) for all strategies of other players
• For weak domination, the expected utility of \(s_i\) must be strictly greater than the expected utility for \(s_i'\) for at least one strategy of the other players
• For very weak domination, the expected utility of \(s_i\) must be greater or equal to the expected utility for \(s_i'\) for all strategies of other players

Front: In game theory, how does Iterated Elimination of Strictly Dominated Actions work?
Back: By removing strictly dominated actions iteratively.

Q: The outcome of Iterated Elimination of Strictly Dominated Actions is [...]
A: independent of the elimination order.

Front: What does Fisher's linear discriminant rule or Fisher's criterion do?
Back: Choose a weight vector so that the ratio of between class variance maximized and within class variance is minimized:
For two classes \(\circ, \bullet\), with \(\mathbf{μ}_{\circ}\) and \(\mathbf{μ}_{\bullet}\) being sample means of the two classes, respectively, and \(\sigma_{\circ}^2\) and \(\sigma_{\bullet}^2\) being sample variances, find a weight vector \(\mathbf{w}\) that maximizes
\(\underset{\mathbf{w}}{\text{argmax}} \frac{(\mathbf{w}\mathbf{μ}_{\circ}-\mathbf{w}\mathbf{μ}_{\bullet})^2}{\mathbf{w}^T (\sigma_{\circ}^2 +\sigma_{\bullet}^2)\mathbf{w}}\)

Front: How does one compute the linear discriminant analysis?
Back: To find the weight vector \(\mathbf{w}\) for two classes \(\circ, \bullet\) with means \(\mathbf{μ}_{\circ}, \mathbf{μ}_{\bullet}\) and variances \(σ_{\circ}^2, σ_{\bullet}^2\), one uses the formula
\(\mathbf{w} \propto (σ_{\circ}^2+σ_{\bullet}^2)^{-1}(\mathbf{μ}_{\circ}-\mathbf{μ}_{\bullet})\)

Front: In machine learning, what is whitening?
Back: It's transforming a dataset so that the covariance is 0 between dimensions (the covariance matrix is the identity matrix).

Q: Linear discriminant analysis is equivalent to [...]
A: whitening the data and the applying nearest centroid classification.

Front: In machine learning, what is the difference between discriminative and generative models?
Back: • Discriminative models find the vector or hyperplane \(\mathbf{w}\) that best discriminates between two classes
• Generative models find out how the data was generated

Front: When is linear discriminant analysis the optimal classifier?
Back: If the data is a Gaussian with equal class covariances.

Q: In game theory, the acronym ISD stands for [...]
A: Iterated Elimination of Strictly Dominated Actions.

Q: The outcome of ISD is [...] of the elimination order.
A: independent

Q: ISD preserves [...]
A: Nash equilibria.
Extra: A Nash equilibrium of the subgame resulting from ISD is also a Nash Equilibrium of the original game.

Front: In game theory, how can one find a dominating strategy for a given action?
Back: By creating a linear program that maximizes the probabilities in the dominating strategy, while satisfying the weak domination criterion.
If the sum of probabilities is less than one, then the found strategy strictly dominates the given action.

Front: In game theory, which of Iterative Elimination of {Strictly, Weakly, Very Weakly} Dominated Actions is order independent/generally in P?
Back: Only Iterative Elimination of Strictly Dominated Actions.

Front: Describe how a principal component analysis can be computed from a dataset using eigenvalues.
Back: Compute the covariance matrix \(\mathbf{Σ}\) of the dataset, then the eigenvectors and corresponding eigenvalues. The eigenvector with the largest eigenvalue is the first principal component, the one with the second largest is the second principal component, and so on.

Front: Describe how a principal component analysis can be computed from a dataset \(\mathbf{x}_1, \dots, \mathbf{x}_N\) by signal maximization?
Back: Pick a vector \(\mathbf{w}\) that maximizes the average dot product between itself and the datapoints.
\(\underset{\mathbf{w}}{\text{argmax}}(\frac{1}{N} \sum_{k=1}^{N} (w^T x_k)^2)\)

Front: Describe how a principal component analysis can be computed from a dataset \(\mathbf{x}_1, \dots, \mathbf{x}_N\) by noise minimization?
Back: Pick a vector \(\mathbf{w}\) that minimizes the distance between itself and the datapoints.
\(\underset{\mathbf{w}}{\text{argmin}}(\frac{1}{N} \sum_{k=1}^{N} ||\mathbf{x}_k-\mathbf{ww}^T \mathbf{x}_k||^2)\)

Front: What are Lagrangians good for?
Back: If you want to maximize a function \(f(θ)\) under a constraction \(g(θ)=0\), you can use a Lagrangian to achieve this.

Front: How does one use a Lagrangian, given a function \(f(θ)\) and a constraint \(g(θ)=0\)?
Back: Construct \(\mathcal{L}(θ,λ)=f(θ)+λg(θ)\) (with \(λ\) being called the "Lagrange multiplier").
Solve \(\nabla \mathcal{L}(θ,λ)=0\). This gives a necessary condition for the solution.

Front: Briefly, which three methods of computing principal components exist?
Back: • Compute using the eigenvalues of the covariance matrix
• Compute using signal maximization
• Compute using noise minimization

Front: What is the south-asian variant of pompoir called?
Back: Kabzah

Q: The dipole repeller is [...]
A: a center of effective repulsion in the large-scale flow of galaxies in the neighborhood of the Milky Way.

Front: How does the dipole repeller look like, schematically?

Front: Is there an active repulsive force acting in the Dipole Repeller?
Back: Currently unknown & disputed.

Front: What is a congestion game?
Back: A congestion game is a game where a finite set of resources needs to be distributed.
Mathematically, it's a tuple \((N, R, A, c)\) where
• \(N\) is a set of \(n\) players
• \(R\) is a finite set of resources
• \(A=A_1 \times \dots \times A_n\), where \(A_i \subseteq 2^R \backslash \{\emptyset\}\) is the set of actions for player \(i\)
• \(c=(c_1, \dots, c_{|R|})\), where \(c_r: ℕ \mapsto ℝ\) is a cost function for resource \(r \in R\)

Front: In a congestion game, what does \(\#(r,a)\) stand for?
Back: The number of players who took any action that involves resource \(r\) under action profile \(a\).

Front: In congestion games, how does one compute the utility function for player \(i\) given an action profile \((a_i, a_{-i})\)?
Back: \(u_i(a)=-\sum_{r \in a_i} c_r(\#(r,a))\)
where \(c_r\) is the cost function for the resource \(r\).

Front: How do you find a Nash equilibrium in a congestion game?
Back: Find the agent who isn't yet playing his best response, change his action profile to the best response, repeat.
Return action profiles if every player is playing their best response.

Front: What is a potential game?
Back: A game where there is a function that can map any action profile to a real number so that the difference in value for the action profiles is the difference in utility to a specific player.
Mathematically, with the function \(P: A \mapsto ℝ\), for all \(i \in N\), \(a_{-i} \in A_{-i}\) and \(a_i, a_i' \in A_i\):
\(u_i(a_i, a_{-i})-u_i(a_i', a_{-i})=P(a_i, a_{-i})-P(a_i', a_{-i})\)

Front: What is the relation between congestion games and potential games?
Back: Every congestion game is a potential game (but not the other way around).

Q: The category-theoretic extension of the Curry-Howard correspondence is called the [...]
A: Curry-Howard-Lambek correspondence.

Front: Given a dataset \(\mathbf{x}\) with labels \(\mathbf{y} \in ℝ^n\), how does one compute a one-dimensional linear regression \(\mathbf{w}\)?
Back: \(\mathbf{w}=\frac{\sum_{i=1}^{n} x_i y_i}{\sum_{i=1}^{n} x_i x_i}\)

Front: Given a multi-dimensional dataset \(X \in ℝ^{d \times n}\) and a feature vector \(y \in ℝ^{1 \times n}\), how does one compute the linear least-square regression \(\mathbf{w}\)?
Back: \(\mathbf{w}=(XX^T)^{-1} Xy^T\)

Front: Given a vector \(\mathbf{w}\) that is the result of a linear regression, for a new datapoint \(z\), how does one predict the label of \(z\)?
Back: \(y_z=\mathbf{w}^T \cdot z\)

Front: How does one compute a ridge regression of a dataset \(X\) with labels \(y\)?
Back: \(\mathbf{w}=(XX^T+λI)^{-1}Xy^T\), where \(λ\) is a hyperparameter and can be found by grid search (or, less likely, is directly specified).

Front: In machine learning, what is grid search?
Back: It's a method for finding the right values for hyperparameters by sweeping through possible assignments.

Front: What is the relation between parallel, serial, concurrent and sequential algorithms?
Back: • Parallel algorithms can execute multiple operations in a physical instant (e.g. with multicore machines)
• Concurrent algorithms can execute computations during overlapping time periods (but not necessarily the same instant, e.g. in time-sharing)
• Serial and sequential algorithms are behaviorally the same
    • Serial is often used as the opposite of parallel, and sequential as the opposite of concurrent

Front: What was the name of the sun goddess in Finnish mythology?
Back: Päivätär

Front: What was the name of the sun goddess in Basque mythology?
Back: Eki

Q: Braess' Paradox states that [...]
A: adding one or more edges to a network can slow down the overall traffic flow through it.

Front: What is the El Farol Bar problem?
Back: It's a problem in game theory where
• if less than 60% of the population go to a bar, they have more fun than if they stay at home
• if more than 60% of the population go to a bar, they'll have less fun than if they stay at home

Front: In congestion games, what is the relation of the cost function and the utility function?
Back: The utility function for an action profile \(a=(a_i, a_{-i})\) is
\(u_i(a)=-\sum_{r \in a_i} c_r(\#(r, a))\).
The cost function is \(c_i(a)=-u_i(a)\).
Every player has the same cost and utility function.

Front: In congestion games, what is the total cost of an action profile \(a\)?
Back: It's the sum of all costs of the action profile for all players:
\(C(a)=\sum_{i \in N} c_i(a)\)

Q: In congestion games, the MyopicBestResponse algorithm [...] terminate.
A: does

Front: Given a minimisation game \(G\) with a cost function \(C\), how does one compute the Price of Anarchy?
Back: Calculate the quotient of the best Nash equilibrium to the best overall strategy.
\(\text{PoA}(G)=\underset{a^{\star} \in \text{pNE}(G)}{\text{max}} \frac{C(a^{\star})}{C(a^{opt})}\)
where pNE is the set of all pure Nash equilibria, and \(a^{opt}\) is the globally optimal strategy (may not be equil).

Front: When is a congestion game \(G\) \((λ \ge 0,μ \ge 0)\)-smooth?
Back: If the sum of the costs for each player to change from any Nash equilibrium to the optimal action is smaller than the costs of the optimal and the current action profile linear combined with \((λ, μ)\).
\(\sum_{i \in N} c_i(a_i^{\text{opt}}, a_{-i}^{\star}) \le λC(a^{\text{opt}})+μC(a^{\star})\)
\(a^{\text{opt}}\) is the optimal action, \(a^{\star}\) is any Nash equilibrium.

Front: In game theory, what is an atomic routing game?
Back: It's a congestion game where
• the set \(R\) of resources is a set of edges
• the set \(A\) of actions is a set \(s_i - t_i\) paths
• the cost function returns the edge delay for a given path

Q: [...] are [...]-smooth.
A: Atomic routing games with non-negative affine cost functions; \((\frac{5}{3}, \frac{1}{3})\)

Front: In a non-atomic routing game, what is a flow?
Back: A flow is a vector \(\{f_p\}_{p \in P_{st}}\) describing the amount of flow on all paths \(p \in P_{st}\), with \(r\) being the total flow.

Front: In non-atomic routing games, how does one compute the amount of flow on an edge \(e\), given a flow \(\{f_p\}\)?
Back: Sum only over the flows that go over \(e\), on any path in \(\{f_p\}\).
\(f_e=\sum_{p \in P_{st}: e \in p} f_p\).

Front: In non-atomic routing games, how does one compute the delay on a path \(p\), given the cost function \(c_e\) for edges and the flows on edges \(f_e\)?
Back: Sum over the individual costs of the edges in \(p\):
\(c_p(f)=\sum_{e \in p} c_e(f_e)\)

Q: The price of anarchy for non-atomic routing games is [...], the price of anarchy for atomic routing games is [...].
A: unbounded; unbounded

Front: In non-atomic routing games, what is a Pigou-like graph?
Back: It's a graph with two nodes \(s, t\), and two edges, one with the cost \(c(r)\) (static cost) and the other with the cost \(c(\cdot)\) (variable cost).

Front: What is the Pigou bound?
Back: It's an upper bound for the price of anarchy on a Pigou-like graph with cost functions in a class of cost functions \(C\).

Front: Conceptually, how does one compute the Pigou bound \(α(C)\)?
Back: Roughly, it is calculated by the supremum of the price of anarchy over all cost functions \(c \in C\), static costs \(r\) and amount of flow \(x\) over the edge with variable cost.
Formally,
\(α(C)=\underset{c \in C}{\text{sup }}\underset{r \ge 0}{\text{sup }}\underset{x \ge 0}{\text{sup}} \{\frac{r \cdot c(r)}{x \cdot c(x) + (r-x) \cdot c(r)}\}\)

Q: For every set of non-negative, continuous and non-decreasing cost functions \(C\) and every non-atomic routing game with cost functions in \(C\), the price of anarchy is upper bounded by [...].
A: the Pigou-bound \(α(C)\)
Extra: This means that you only have to consider Pigou-like graphs in flow networks to compute the price of anarchy.

Front: In a neural network with the output error \(\mathcal{E}\), how does one compute the gradient for a node \(z_i\) using the gradients of the child nodes \(z_j\)? (abstracted from the activation function)
Back: One uses the multivariate chain rule:
\(\frac{∂ \mathcal{E}}{∂ z_i}=\sum_{j} \frac{∂ z_j}{∂ z_i} \frac{∂ \mathcal{E}}{∂ z_j}\)

Front: In a neural network, how does one compute the gradient of the weights \(w_{ij}\) given the gradient of the next layer \(z_j\)?
Back: \(\frac{\partial \mathcal{E}}{\partial w_{ij}}=\frac{\partial z_j}{\partial w_{ij}} \frac{\partial \mathcal{E}}{\partial z_j}\)

Front: Given a neural network with \(N\) output layers \(z_1, \dots, z_N\) and correct classifications \(t_1, \dots, t_N\), how does one compute the error function \(\mathcal{E}(θ)\) of some parameters \(θ\) of the network?
Back: The average error of the misclassification, upper-bounded by \(0\).
\(\mathcal{E}(θ)=\frac{1}{N} \sum_{k=1}^{N} \text{max}(0, -z_k t_k)\)

Front: How old are flowers?
Back: ~130 mio. years

Front: In machine learning, what is a Kernel?
Back: A Kernel function \(k\) is a dot product in a feature space \(\mathcal{F}\).
It is the composed by using the function \(φ\) on the inputs, and then applying the dot product to them.
More mathematically, \(k: \mathcal{X} \times \mathcal{X} \rightarrow ℝ\),
\(k(x_i, x_j)=φ(x_i)^T \cdot φ(x_j)\), with \(φ: \mathcal{X} \rightarrow \mathcal{F}\).

Front: State the Kernel trick.
Back: If we have an algorithm where each input vector \(\mathbf{x}\) only occurs in the form \(\mathbf{x}^T \cdot \mathbf{x'}\), we can replace each scalar product by a kernel
\(k(\mathbf{x}, \mathbf{x'})=ϕ(\mathbf{x})^T \cdot ϕ(\mathbf{x'})\)

Front: State Mercer's theorem.
Back: If a kernel is positive semi-definite symmetric, it can be constructed using the dot-product in a feature space.
More mathematically: If a kernel is positive semi-definite symmetric then it corresponds to \(k(x, x')=ϕ(x)^T \cdot ϕ(x')\) for almost all \(x \in \mathcal{X}\).

Front: State the Representer theorem.
Back: The optimal weights are a linear combination of the training examples in feature space.
More mathematically: Given a feature extraction function \(φ: \mathcal{X} \rightarrow \mathcal{F}\) and a set of \(N\) training examples \(\mathbf{x} \in \mathcal{X}^N\), the optimal weights \(\mathbf{w}\) can be computed by
\(\mathbf{w}=\sum_{i=1}^{N} α_i φ(\mathbf{x}_i)\),
with \(α_i \in ℝ\).

Front: In Kernel Ridge Regression, how does one compute the parameters \(\mathbf{α}\), given a kernel \(K\) and a set of labels \(\mathbf{y}\)?
Back: \(\mathbf{α}=(K+λI)^{-1}\mathbf{y}^T\)

Front: In machine learning, what is the Gram Matrix?
Back: The kernel on the training data, \(K_{\text{Gram}}=K(X_{\text{train}}, X_{\text{train}})\)

Front: In ridge regression in machine learning, how does one predict the the test labels \(y_{\text{test}}\) from a kernel \(K\), a kernel function \(k\), training data \(X_{\text{train}}\), training labels \(y_{\text{train}}\) and test data \(X_{\text{test}}\)?
Back: \(y_{\text{test}}=y_{\text{train}} (K+λI)^{-1} k(X_{\text{train}}, X_{\text{test}})\)
where \(λ\) stands for the ridge parameter.

Front: How does Nested Cross-Validation work?
Back: There are two nested loops both looping through folds of the data, with the inner loop also ignoring the fold of the outer loop.
The inner loop picks the best parameter \(σ_s\) for the model, the outer loop trains the model on \(σ_s\) (ignoring, of course, the outer fold).
It returns the average performance in the outer loop.

Front: In game theory, what is a Principal-Agent model?
Back: A model where there is a Principal who proposes one or more contracts (or set of incentives) in a "take it or leave it" manner, and an Agent, who has private information, who can choose to accept one or zero contracts.

Front: What are the goals in a Principal-Agent model?
Back: The principal wants to bring the agent to maximize the principal's payoff, subject to two contraints:
• The agent will maximize their own payoff (incentive compatibility)
• The agent must be at least as well off as if they hadn't agreed to any contract (participation constraint)

Front: In game theory, what is Adverse Selection?
Back: If there is asymmetric information between buyer and seller (with the seller having more information), better goods leave the market because they can't justify their quality (they are "priced out").

Front: In game theory, what is a Moral Hazard?
Back: A moral hazard occurs when an agent has the incentive to increase its exposure to risk because it does not bear the full costs of that risk.

Front: In machine learning, given a function \(f\) that predicts labels \(y\) from a dataset \(\mathbf{x}\), how does one calculate the risk?
Back: \(R[f]=\int \frac{1}{2} |f(\mathbf{x})-y|^2 d P(\mathbf{x}, y)\)

Front: In machine learning, given a function \(f\) that predicts labels \(y\) from a dataset \(\mathbf{x}\) with \(N\) samples, how does one calculate the empirical risk?
Back: \(R_{\text{emp}}[f]=\frac{1}{N} \sum_{i=1}^{N} \frac{1}{2} |f(\mathbf{x}_i)-y_i|^2\)

Front: What are a shattered set and a shattering class?
Back: A shattering class \(C\) shatters a set \(A\) if for each subset \(a\) of \(A\),
there is some element \(c \in C\) such that \(a=c \cap A\).
That is, \(\mathcal{P}(A)=\{c \cap A | c \in C\}\).

Q: A hyperplane classifier is in canonical form if [...]
A: \(\text{min}_{\mathbf{x}_i \in X} |(\mathbf{w} \cdot \mathbf{x}_i)+b|=1\), i.e. the distance to the the nearest point is exactly 1.

Front: When is a kernel a Mercer Kernel?
Back: Iff for any dataset \(x_1, \dots, x_n \in ℝ^d\) there exist some coefficients \(c_1, \dots, c_n ∈ ℝ\) so that it holds that
\(\sum_{i=1}^n \sum_{j=1}^n c_i c_j k(x_i, x_j) \ge 0\)

Front: What is the spectrum of a matrix?
Back: The bag (multiset) of its eigenvalues.

Front: What is the relation of the determinant and the eigenvalues of a matrix?
Back: The determinant \(d\) is the product of the eigenvalues \(\mathbf{λ}_n\) of the matrix:
\(d=\prod_{i=1}^{n} λ_i\)

Front: What portion of radioactivity does LLW account for?
Back: 1%.

Front: What portion of radioactivity does HLW account for?
Back: 95%.

Front: What portion of radioactivity does ILW account for?
Back: 4%.

Front: In principal-agent models, who has more information and who has less?
Back: The principal has less info, the agent more.

Front: What type of difference in information leads to adverse selection problems?
Back: If one party knows more about the attributes or quality of a good.

Front: What type of difference in information leads to moral hazards?
Back: If one party can take unobservable actions that affect the quality of trade.

Front: How are adverse selection problems solved?
Back: By
• requiring everyone to participate in the market
• making information about goods more accurate

Front: What is a deductible?
Back: In an insurance policy, the deductible is the amount of money paid out of pocket by the policy holder for the insured things before the provider will pay any expenses.

Front: How does on prevent moral hazards from occurring?
Back: By making the insuree pay a deductible.

Front: For HLW, how long does it take for its radioactivity to return to naturally occuring uranium levels?
Back: ~1000 years

Front: What is the disposal volume of the current HLW?
Back: ~22000 m³

Front: In economics, when does one perform signalling or screening?
Back: In the context of asymmetric information (e.g. a prinicipal-agent problem).

Front: In economics, what is the difference between signalling and screening?
Back: Signalling is the search for information performed by the informed party, screening is performed by the uninformed party.

Front: In economics, what is a self-selection constraint and how does it work?
Back: If characteristics of an informed party are unobservable, then the uninformed party can set up the incentives so that only informed parties with a certain characteristic are willing to participate.
Example: Companies who are interested in workers that will stay a long time have rising wage profiles.

Front: In economics, what is a pooling equilibrium?
Back: In a situation with asymmetric information where signalling is available, a pooling equilibrium is a solution where everybody signals because the payoff for signalling is high enough even for low-quality participants.

Front: In economics, what is a separating equilibrium?
Back: In a situation with asymmetric information with signalling, a separating equilibrium is a solution where only high-quality participants signal, because signaling is not worth it for low-quality participants.

Front: In machine learning, what differentiates classification from regression?
Back: Classification is a function \(f: ℝ^d \rightarrow \{-1, 1\}\), regression is a function \(f: ℝ^d \rightarrow ℝ\).

Front: How does one compute the least squares kernel ridge regression for a training set \(\mathbf{x}\) with labels \(\mathbf{t}\), a training set \(X\), a kernel \(K\), a kernel function \(k\) and a ridge parameter \(λ\)?
Back: \(y=k(\mathbf{x}, X)(K+λI)^{-1}\mathbf{t}\)

Front: How one compute Kernel logistic sigmoid classification, given an input \(\mathbf{x}\) and a feature mapping \(ϕ\)?
Back: \(P(y=1|\mathbf{x})=σ(\mathbf{w}^Tϕ(\mathbf{x}))\), where \(\mathbf{w}\) is a weight vector and \(σ\) is the logistic sigmoid function.

Front: Given the set of possible outcomes \(O\), what is a scoring rule?
Back: A function from the probabilities over all outcomes with an actual outcome mapped into the reals.
\(s: Δ(O) \times O \rightarrow ℝ \cup \{-\infty \}\)
where \(Δ(O)\) is the probability simplex over \(O\).

Front: What does the linear scoring rule do?
Back: The linear scoring gives the forecaster a payment equal to the probability they assigned to the correct outcome.

Front: When is a scoring rule proper?
Back: Iff for all true beliefs \(p\), the expected payoff of reporting \(p\) yields higher expected utility than any other belief \(q\).
\(S(p,p)>S(q,p)\) for all \(q \not = p\).

Front: How is the logarithmic scoring rule computed?
Back: \(s_{\text{log}}(q, o_k)=\ln(q_k)\) for a set of reported probabilities \(q\) and an outcome \(o_k\).

Front: What is the name of the algorithm that solves the maximum subarray problem in linear time?
Back: Kadane's algorithm.

Front: What is the name of the Finland nuclear waste disposal site?
Back: Olkiluoto

Front: Which regions are most geologically beneficial for deep geological disposal of nuclear waste?
Back: Australia, southern Africa, Argentina and western China

Front: How is the Vapnik-Chervonenkis dimension of a family of sets \(H\) computed?
Back: It is the largest cardinality of sets shattered by \(H\). If arbitrarily large sets can be shattered, the VC dimension is ∞.

Front: What is the Vapnik-Chervonenkis dimension?
Back: It is a measure of the complexity/expressive power of a set of functions that can be learned by a statistical binary classification algorithm.

Front: What chinese expression is often used to describe the variety of female body types?
Back: huanfei yanshou (環肥燕瘦, literally "plump Huan, slender Fei")

Front: How do you score predictions you don't know the outcome of, if you have predictions from multiple agents?
Back: You reward agents for their predictions insofar as they coincide with the predictions of other agents they can't communicate with.

A peer prediction mechanism receives signal reports \(r_1, r_2\) from agents 1 and 2 and uses a payment rule to reward the agents.

Front: In peer prediction mechanisms, how is the output agreement mechanism defined?
Back: For two reports \(r_1, r_2\), the reward is \(t_i(r_1, r_2)=\mathbf{1}(r_1=r_2)\) for \(i \in \{1,2\}\), where \(\mathbf{1}\) is the indicator function which returns 1 if it receives true, 0 if false.

Front: When is a peer prediction mechanism with a payment rule \(t_1, t_2\) strictly proper?
Back: Iff every agent is incentivized not to change their reported belief (which is also their true belief), given their belief about the reported beliefs of other agents.
Mathematically,
\(\mathbb{E}_{l \sim p(l|j)}[t_1(j, l)]>\mathbb{E}_{l \sim p(l|j)}[t_1(j', l)]\) for all \(j \in [m]\) and all \(j' \in [m]\backslash \{j\}\),
where \(p(l|j)\) is the conditional probability of a signal \(l\) for agent 2 given signal \(j\) for agent 1.

Q: In peer prediction, a signal distribution satisfies signal dependence if [...]
A: there is some correlation between signal, i.e. there is some \(j \in [m]\) and some \(l \in [m]\) for which \(Δ_{j l}>0\).

Front: What is this type of animal called?
Back: Fleckvieh.

Front: What does Fleckvieh look like?

Q: Given two agents, reporting on a set of exclusive options \([m]\) each. A signal distribution satisfies [...] iff mathematically, [...].
In words, [...].
A: the strong-diagonalization property; \(P(X_2=j|X_1=j)>P(X_2=j'|X_1=j)\) for all \(j \in [m]\) and \(j' \in [m] \backslash \{j\}\); any element on the diagonal of the conditional probability matrix is greater than every element in the same row and column
Extra: This signal distribution satisfies the property:
This signal distribution doesn't satisfy the property:

Q: [...] iff [...].
A: The Output Agreement mechanism is strictly proper; the signal distribution satisfies the strong-diagonalization property

Front: What is the payment rule for the 1/Prior mechanism, given two predicting agents?
Back: \(t_i(r_1, r_2)=\frac{1}{P(r_i)} \mathbf{1}(r_1=r_2)\) for \(i \in \{1,2\}\),
where \(P\) is the prior probability over reports.

Q: A signal distribution is self-predicting iff [...].
Mathematically: [...]
By probability matrix: [...]
A: agent 1 believes, for any signal \(j\), that agent 2 is most likely to think the answer is \(j\) when agent 1 believes the answer is \(j\); \(P(X_2=j|X_1=j)>P(X_2=j|X_1=j')\) for all \(j \in [m]\) and all \(j' \in [m] \backslash \{j\}\); The diagonal entries in the conditional probability matrix are strictly greater than every other entry in the same row.

Front: What is the method that implements the scoring rule-based peer prediction mechanism, given two reports \(r_1, r_2\) from agents 1 and 2?
Back: The payment for agent 1 is \(t_1(r_1, r_2)=s(q, r_2)\) where
• \(s\) is any strictly proper scoring rule,
• \(q=P(X_2|X_1=r_1)\), the posterior distribution over the signal of agent 1, given agent \(r_2\)

Q: A signal distribution satisfies stochastic relevance iff [...]
Mathematically, [...]
A: the signal conditional distributions differ on at least one event.; \(P(X_2|X_1=j)\not =P(X_2|X_1=j')\) for all \(j \in [m]\) and all \(j' \in [m] \backslash \{j\}\).

Front: In information elicitation, what is an uninformative equilibrium?
Back: An equilibrium in which the agents report the same outcome, but not the truth.

Front: In information elicitation, what is a bonus-penalty mechanism and how does roughly work?
Back: You have three prediction tasks, and give each of them to each agent. Let \(r_n^{(m)}\) be the signal report from agent \(n\) on task \(m \in [3]\).
The bonus-penalty mechanism is computed by designating one particular task as the bonus task (here task 0). The other tasks are the penalty tasks, which the predictors can't distinguish from the bonus task.
If the agents agree on every task, the payment is zero.
Then the formula for computing the bonus-penalty mechanism is
\(t_i(r_1, r_2)=\mathbf{1}(r_1^{(0)}=r_2^{(0)})-\mathbf{1}(r_1^{(1)}=r_2^{(2)})\)

Q: A peer prediction mechanism is [...] iff [...].
A: informed truthful; no strategy profile provides more payoff in equilibrium than truthful reporting, and that equilibrium is strictly better than any uninformed strategy

Front: What are the horses in this emblem called?
Back: Tulpar

Front: What is a Tulpar?
Back: A winged horse in Turkic mythology.

Front: What is the winged horse in Turkic mythology called?
Back: Tulpar.

Front: Intuitively, what approach do classification decision trees take?
Back: The data space is recursively partitioned into two regions (easy two define), the classification then is e.g. the majority classification in that region.

Front: What is a common minimization criterion used in regression trees?
Back: The sum of squares.

Q: Finding the best binary partition is [...], an alternative approach is to [...]
A: computationally infeasible (NP hard); instead use a greedy approach.

Front: What is Gini impurity?
Back: Gini impurity is a metric for splitting in classification and regression trees, based on the probability of misclassification.

Front: How is Gini impurity computed, for a dataset \(X\), labeled from a set \(C\) of classes, and a given probability distribution \(p(C)\)?
Back: Gin impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset.
Then the Gini impurity is
\(G(X)=\sum_{c \in C} p(c)(1-p(c))\)

Front: Given a regression tree \(T\) with \(|T|\) terminal leaves, the squared loss at terminal leaf \(m\) \(Q_m(T)\), the size of the training data at terminal leaf \(N_m\) and a regularization parameter \(α\), how does one compute the most fitting tree?
Back: Find a subtree that minimizes the total cost versus complexity of the tree.
\(C_α(T)=\sum_{m=1}^{|T|} N_mQ_m(T)+α|T|\)

Front: In decision tree fitting, how is the parameter \(α\) computed?
Back: By cross-validation.

Front: In machine learning, given a finite hypothesis space \(|H|\) and \(m\) i.i.d. samples in the training set, how can one bound the generalization error of a correctly classifying hypothesis \(h \in H\)?
Back: \(P(\text{error}_X(h)>ε)\le |H|e^{-mε}\)

Front: How can the error of a model \(f\) for a dataset \(x,y\) be decomposed?
Back: \(\text{Err}((y-f(x))^2)=\text{Bias}(f(x))^2+\text{Var}(f(x))+σ^2\)
where \(σ^2\) is residual error.

Front: In machine learning, what is Bagging?
Back: Bagging refers to using multiple decision trees trained with subsets of the data whose decision is aggregated (in classification with majority voting, in regression with the average).

Front: In decision tree learning, what is the Random Subspace Method?
Back: It is a method used to de-correlate different estimators by training them on non-overlappingly different features (e.g. dimensions) of the data.

Front: In machine learning, what are Random Forests?
Back: Random forests result from the combination of bootstrap aggregating and the random subspace method, resulting in a set of trees trained on different features of the data.
The random feature selection from the random subspace method occurs either at tree level or at the split level.

Front: Roughly, how does one compute a random forest given a size \(B\) for a dataset of size \(N\)?
Back: For \(b=1\) to \(B\):
    • Draw a random sample without replacement of some size \(K \le N\) from the training data
    • Grow a tree \(T_b\) to the bootstrapped data until the minimum node size is reached:
        • Select \(m\) features at random
        • Pick the best split point among the \(m\)
        • Split the node into two child nodes

Front: What is the basic idea behind boosting?
Back: You have a set of basis functions \(H=\{h_t(\mathbf{x}): t=1, \dots, T\}\) (\(h\) just being some classifier \(h: X \rightarrow Y\)).
Then these hypotheses can be weighted using some weights \(\mathbf{α}=(α_1, \dots, α_T)\) to produce an ensemble output
\(f_{\text{Ens}}\mathbf{x}=\sum_{t=1}^{T} α_t h_t(\mathbf{x})\)

Front: What inputs does the Adaboost algorithm take and which outputs does it produce?
Back: It takes a dataset \(\{(x_1, y_1), \dots (x_N, y_N)\}\) and a constant \(T \in ℕ\) and
produces a set of hypotheses \(H=(h_1, \dots, h_T)\) (\(h_t: \mathbf{x} \rightarrow \{\pm 1\}\)) and a weight vector \(\mathbf{a} \in ℝ^T\).

Front: How, conceptually, does the Adaboost algorithm work?
Back: It starts with uniform weights on all datapoints.
Over \(T\) rounds:
• The base learner \(h\) is trained.
• From the predictions of the base learner, the weighted error \(ε_t\) is computed
• \(ε_t\) is in turn used to compute the hypothesis weight \(α_t\).
• At the end the weights of the datapoints are updated.

Front: Given a hypothesis function \(h\) and a dataset \((\mathbf{x}, \mathbf{y})\), which function \(\mathcal{G}\) is Adaboost minimizing?
Back: It is minimizing
\(\mathcal{G}(\mathbf{a})=\sum_{i=1}^N \exp (-y_i \sum_{t} α_t h_t(x_i))\)

Front: What is the relationship between Adaboost and gradient descent?
Back: Adaboost is a coordinate gradient descent method which minimizes \(\mathcal{G}(\mathbf{α})\) stepwise.

Front: State the theorem for the price of anarchy in generic non-atomic routing games.
Back: For every set of non-negative, continuous and non-decreasing cost functions \(C\) and every every non-atomic routing game with cost functions in \(C\), the PoA is upper-bounded by the Pigou bound \(α(C)\).

Front: What is the Hessian matrix of a function \(f: ℝ^n \rightarrow ℝ\)?
Back: It is the matrix of the second-order partial derivatives of \(f\):
\((H_f)_{i,j}=\frac{\partial^2 f}{\partial x_i \partial x_j}\)

Front: How can one use the Hessian matrix \(H_f\) of a function \(f\) to compute its condition number?
Back: Let \(λ_1, \dots, λn=\text{eigvals}(H_f)\), with \(λ_1\) being the largest eigenvalue and \(λ_n\) being the smallest. Then the condition number of \(f\) is
\(\frac{λ_1}{λ_n}\)

Q: In neural networks, the [...], the [...].
A: higher the ratio between the highest and the lowest eigenvalue of the Hessian matrix of a neural network; slower the convergence

Front: Intuitively, what is the condition number of a function?
Back: It's a positive number (\(\in ℝ_+\)) that measures how much the output value of a function can change for a small change in the input.

Q: In [...], the condition number can be reduced by [...]
A: neural networks with mean squared error; centering the data before training.

Front: In machine learning, how does one center activations in the network in practice?
Back: By choosing an activation function \(g\) that satisfies \(g(0)=0\).

Front: Given a momentum \(μ\), an error function \(\mathcal{E}\), a learning rate \(γ\) and a set of parameters \(θ\), how does one compute stochastic gradient descent with momentum?
Back: It is very similar to stochastic gradient descent, except that the last gradient is added (with a dampening term \(μ\)) to the current update.
\(Δ=μΔ+\frac{\partial \mathcal{E}_k}{\partial θ}\), and
\(θ=θ-γΔ\)
with \(k \sim \{1,\dots, N\}\).

Front: In Stochastic Gradient Descent+Momentum, what is a common value for the momentum parameter?
Back: 0.9

Q: In neural networks, one can introduce a margin to the solution by [...]
A: using the hinge loss \(\mathcal{E}_k(θ)=\max(0, 1-y_kt_k)\) instead of the perceptron loss \(\mathcal{E}_k(θ)=\max(0, -y_kt_k)\). This works because when a classification is barely correct, it will continue to be improved until it is robustly correct. The hinge loss looks like this:

Front: What does it mean to regularize a neural network, and why would one do it?
Back: Regularization is the method of making a network robust to outliers and improve generalization, often by adding a margin.

Q: Some approaches to regularizing a neural network are:
• [...]
• [...]
• [...]
A: Data perturbation, applying random perturbations to the inputs (e.g. Gaussian noise) and randomly flipping some labels; Randomly turning on and off neurons while training; Using Stochastic gradient descent instead of just gradient descent

Front: With a semaphore, which letters are used for the different states and what do they stand for?
Back: \(P\), standing for “procure”, and \(V\), standing for “vacate”.

Q: Given a graph \(G=(V,E)\), a [...] is [...].
A: matching; a subset of edges \(M \subseteq E\) with no vertex appearing more than once

Q: A matching \(M\) is [...] iff [...]
A: pareto optimal; there is no matching \(M'\) so that at least one agent prefers \(M'\) to \(M\) and the rest of all agents is indifferent.

Front: How can one find a Pareto-optimal matching efficiently?
Back: By using the serial dictatorship mechanism.

Front: How does the serial dictatorship mechanism work, given a set \(A=(a_1, \dots, a_n)\) of agents and their preferences \(\mathcal{E}(O)^n\) over a set of objects \(O=(o_1, \dots, o_m)\)?
Back: • Generate a permutation \(σ\) of \(A\)
• \(S:=O\)
• For \(i=0,n\):
    • Give \(σ(i)\) their highest ranked element in \(S\) \(o_h\)
    • Remove \(o_h\) from \(S\)

Q: A matching is [...] iff [...].
A: maximal; there is no unmatched agent \(a \in A\) and no unmatched object \(o \in O\) with \(o \in \succ_a\)

Q: A matching is [...] iff [...].
A: trade-in-free; there is no agent \(a \in A\) and no unmatched object \(o \in O\) so that the unmatched object would be preferred to a matched object (\(h \succ_a M(a)\))

Q: A matching \(M\) is [...] iff [...].
A: coalition-free; there is no sequence of matched agents \(a_1, \dots, a_k\) such that agent \(a_i\) prefers \(M(a_{i+1})\) to \(M(a_i)\)

Q: Theorem: A matching is [...] iff it is [...].
A: Pareto optimal; maximal, trade-in-free, and coalition-free

Q: A matching \(M\) is [...] iff [...].
A: popular; there is no other matching \(M'\) so that more agents prefer their \(M'\) option to their \(M\) option. Mathematically, no \(M'\) satisfies \(|\{a \in A| M'(a) \succ M(a) \}|>|\{a \in A| M(a) \succ M'(a)\}|\)

Q: A matching is [...] iff [...].
A: rank-maximal; it maximizes the number of agents matched to their first choice, then to their second choice, and so on

Q: Theorem: A matching \(M\) between objects \(O\) and agents \(A\) is [...] iff [...]
A: popular; every first choice is matched, and matches only come from first and second choices of the agents.

Front: What problem does on have to solve in a stable bipartite matching?
Back: Given two sets of agents \(U, W\) with preferences \(\prec_u, \prec_w\), find a matching between the two sets.

Q: A bipartite matching between two sets \(U, W\) with preference relation \(\prec\) is [...] iff [...].
A: not stable; there is a \(u \in U\) and a \(w \in W\) which both prefer each other to the elements they have been matched to

Front: How, roughly, does the Gale-Shapley algorithm between two sets \(U, W\) and with a preference relationship \(\prec\) work?
Back: • Each round, every member of \(U\) proposes to the element that ranks highest according to \(\prec\) and that they haven't yet proposed to.
• Each member of \(W\) rejects every proposal that isn't highest on ther preference ranking.
• Repeat until every element is matched.

Front: What is the runtime complexity of the Gale-Shapley algorithm?
Back: \(\mathcal{O}(n^2)\), where \(n\) is the number of elements in each part of the bipartite set.

Front: In neural network interpretability, what is activation maximization with regularization?
Back: It is finding an \(x\) datapoint that maximizes the log-probability of the activation of the network, potentially with some regularization parameter \(λ\):
\(\max_{x \in \mathcal{X}} \log p(ω_c|x)-λ||x||^2\)

Front: What is the distinction between ante-hoc and post-hoc interpretability?
Back: • Ante-hoc interpretability is about choosing & training a model that is inherently interpretable
• Post-hoc interpretability is about interpreting existing models

Front: What is layer-wise relevance propagation?
Back: It is a method for "rolling a neural network up from the back", which shows how much each feature contributes to the classification produced.

Front: In neural network interpretability, what are sensitivity/saliency?
Back: Sensitivity/saliency of input features describes the way a change (increase/decrease) in those features affects classification score

Front: In neural network interpretability, how can one measure the quality of an explanation that gives a score in \(ℝ\) for each feature of the input?
Back: For a specific input \(x\), change the features with the highest scores, and measure how quickly the classification of \(x\) changes.

The 6 basic AGM postulates are
1. Closure: \(K*P\) is a belief set
2. Success: \(P \in K * P\)
3. Inclusion: \(K*P \subseteq K+P\)
4. Vacuity: If \(\lnot P \not \in K\), then \(K*P=K+P\)
5. Consistency: \(K*P\) is consistent if \(P\) is consistent
6. Extensionality: If \(P \equiv Q\), then \(K*P=K*Q\)

The strawberry routine has the following steps:
• Introduction with setting: driving through countryside, fields with strawberries that look delicious.
• Question 1: There is a fence. How tall is it?
• Question 2: After climbing over the fence, how many strawberries do you eat?
• Question 3: When you've finished eating, how do you feel about the farmer whose strawberries you ate?
• Analysis of fence height: barrier to doing crazy things
• Analysis of number of strawberries: how wild she is
• Analysis of thoughts about farmer: feelings of remorse

The rules of the questions game are:
• The questions can't be dull
• You can't ask the same question the other person's already asked
• Each question can have a subquestion
• I go first

A good sequence of escalating questions in the questions game is
1. When did you have your first boyfriend?
2. What turns you on in a guy?
3. What do you like about me?
4. Where's the craziest place you've ever had sex?
5. Tell me one of your fantasies?
6. When did you last have sex?

Front: What is the general setup in the routine The Cube
Back: Driving down a straight road with no distractions, see big cube with horse around it.

In the routine The Cube, the series of questions is
• How big is the cube?
• What color is the cube?
• What's the horse near the cube doing?
The interpretations are
• Size: size of ego
• Color: personality type
• Horse: symbolic of relationships

Front: What are the components of a sealed-bid auction?
Back: • \(N \subset ℕ\) bidders, who hand in sealed bids \(b \in ℝ^N\)
• An assignment function \(x: ℝ^N \mapsto N\)
• A payment function \(p: ℝ^N \times N \mapsto ℝ\), taking the bid vector and the winner and assigning them a payment

Q: A first-price auction works as follows:
1. [...]
2. [...]
3. [...]
A: Bidding: Each bidder \(i \in N\) hands in a sealed bid \(b_i\); Assignment: Give the item to the bidder with the highest bid; Payment: Let the winner \(i^{\star}\) pay their bid \(b_{i^{\star} }\)

Front: What is the problem with first-price auctions?
Back: The are not strategy-free.

Front: What does DSIC stand for in auction theory?
Back: Dominant-strategy incentive compatibility.
It's the property of an auction that it incentivizes truthful bidding (i.e. every bidder reports their value for an item \(b_i=v_i\)).

Q: An auction is [...] iff
• [...]
• [...]
A: strategy-proof; Truthful bidding is a (very weakly) dominant strategy; A truthful bidding never leads to negative utility

Q: A second-price auction works as follows:
1. [...]
2. [...]
3. [...]
A: Bidding: Each bidder \(i \in N\) hands in a sealed bid \(b_i\); Assignment: Give the item to the bidder with the highest bid; Payment: Let the winner \(i^{\star}\) pay the second-highest bid

Front: What advantage does the second-price auction have over the first-price auction?
Back: It is strategy-proof, and maximizes welfare if bids are truthful

Front: What are the two possible sensible objectives for auctions?
Back: • welfare maximization: The item goes to the bidder with the highest valuation
\(\text{max} \sum_{i \in N} v_i x_i\)
• revenue maximization: The auctioneer gets the most money
\(\text{max} \sum_{i \in N} p_i\)

In auction theory, a single-parameter environment has the following components:
• \(N\), a set of bidders
• \(\mathbf{v} \in ℝ^{|N|}\), the valuations of each bidder for one unit of "stuff"
• \(X \subseteq ℝ^N\), the set of feasible allocations
Example:
Single-item auctions have \(X=\{x \in \{0, 1\}^n: \sum_{i \in N} x_i \le 1\}\)

Front: How can one completely define a sealed-bid auction in a single-parameter environment?
Back: By specifying its
• allocation rule \(x: ℝ^N \mapsto X\), and its
• payment rule \(p: ℝ^N \mapsto ℝ^N\)

Q: An allocation rule \(x\) is [...] iff [...].
A: implementable; there is a payment rule \(p\) such that \((x, p)\) is strategy-proof

Q: An allocation rule \(x\) is [...] iff [...].
A: monotone; for every agent \(i\) and bid vector \(b_{-i}\) by the other agents, \(x_i(z, b_{-i})\) is non-decreasing in \(z\) (bidding more cannot give fewer results)

Front: State the non-formula part of Myerson's Lemma.
Back: An allocation rule \(x\) is implementable iff \(x\) is monotone.

Front: State the formula part of Myerson's lemma.
Back: If a single-parameter auction \((x, p)\) is strategy-proof, and \(p_i(b)=0\) whenever \(b_i=0\), then
\(p_i(b)=b_i x_i(b)-\int_0^{b_i} x_i(z, b_{-i})dz\).

Front: What is the connection between Myerson's lemma and single-item auctions?
Back: If one applies Myerson's lemma to the setting of single-item auctions maximizing welfare, it returns the second-price auction.

Front: What is the technique from machine learning called in which neurons are randomly turned off during training?
Back: Dropout or dilution.

Q: The [...] states that [...].
A: Revelation principle; if a social choice function can be implemented by any mechanism, then the same function can be implemented by an incentive-compatible mechanism with the same equilibrium outcome payoffs
Extra: In the context of auctions, this equivalent mechanism is a sealed-bid auction.

Q: Maximising social welfare in auction theory is special because
• [...]
• [...]
A: Every single-parameter environment has a strategy-proof mechanism that maximizes social welfare; There is no mathematical distinction between unknown valuations and known valuations (to the auctioneer)

Front: How does a posted-price auction work in the context of one bidder and one item?
Back: Fix a posted price \(r\), sell the item at price \(r\) iff the bid is above \(b\).

Front: How does a second-price auction with reserve work when maximizing revenue?
Back: Fix a reserve price \(r\). Don't sell if the highest bid is \(<r\), otherwise sell the item at price \(\text{max}\{r, b_2\}\) where \(b_2\) is the second-highest bid.

Front: Given a distribution \(D\) and a valuation \(v \sim D\), how does one compute the virtual valuation of \(v\)?
Back: \(φ(v):=v-\frac{1-F_D(v)}{f_D(v)}\), where
\(F_D\) is the cumulative distribution function of \(D\), and \(f_D\) is the probability distribution function of \(D\).

Front: In a revenue-maximizing auction with \(i \in N\) bidders, valuations \(v_i\) from a distribution \(D_i\),  virtual valuations \(φ_i(v_i)\) and an allocation rule \(x_i\), what is the expected payment of a truthful bidder \(i\) under Myerson's payment rule?
Back: It's the expected value of the virtual valuation multiplied with the allocation:
\(\mathbb{E}_{v \sim D}[p_i(v_i)]=\mathbb{E}_{v \sim D}[φ_i(v_i)x_i(v_i)]\).

Front: What is the expected revenue of a revenue-maximizing auction using Myerson's payment rule, given \(i \in N\) bidders, valuations \(v_i\), an allocation rule \(x\) and virtual valuations \(φ_i\)?
Back: The expected value over the sum of virtual valuations times the corresponding allocations.
\(\mathbb{E}_{v \sim D} [\sum_{i \in N} φ_i(v_i)x_i(v)]\)

Q: How to create a revenue-maximizing strategy-proof auction, given valuations \(v_i\) from a distribution \(D\):
1. [...]
2. [...]
A: Choose an allocation rule that maximizes virtual welfare when bids are truthful: \(\text{max}_{x \in X} \sum_{i \in N} φ_i(b_i)x_i\); Choose the payment rule according to Myerson's lemma

Front: In revenue-maximizing single-item reserve-price auctions, how can one choose the optimal reserve price?
Back: Given a virtual valuation function \(φ\), the optimal reserve price fulfills
\(φ(r)=r-\frac{1-F(r)}{f(r)}=0\),
where \(F, f\) are the cdf and pdf of the distribution \(D\) from which the valuations are pulled.

Front: What are the Myerson payments in revenue-maximizing auctions with \(n\) bidders with different valuations \(v_1 \sim D_1, v_n \sim D_n\)?
Back: • If \(φ_2(b_2) \ge 0\), then the highest virtual bidder pays \(φ_1^{-1}(φ_2(b_2))\)
• If \(φ_2(b_2)<0\), then the highest virtual bidder pays \(φ_1^{-1}(0)\)
where \(b_2\) is the bid with the second-highest virtual valuation, and \(φ_i^{-1}\) is the inverse of the virtual valuation for bidder \(i\).

The steps in the second-price revenue-maximising auction with bidder-specfic reserve are:
1. Choose a \(t\) so that the probability of the maximal virtual valuation being \(\ge t\) is \(\frac{1}{2}\)
2. Set a reserve price of \(φ_i^{-1}(t)\) for each bidder
3. Give the item to the highest bidder that meets the reserve
4. The highest bidder pays the maximum of their reserve price and the second highest bid meeting their own reserve

Q: With a second-price revenue-maximizing bidder-specific reserve auction, the expected revenue is at least [...] of that of the [...]
A: 50%; best revenue-maximizing auction.

The Virtual Threshold Allocation Rule works as follows:
1. Choose a \(t\) so that the probability that the maximal non-negative virtual valuation is greater than \(t\) is \(\frac{1}{2}\), i.e. \(\mathbb{P}_{v \sim D}[\text{max}_{i \in [n]} φ_i(v_i)^+ \ge t]=\frac{1}{2}\), where \(v\) are the valuations distributed over \(D\), and \(φ_i(v_i)^+\) is the virtual valuation of bidder \(i\) (the \(+\) indicating that it's 0 if it is negative).
2. Allocate the item to some bidder with virtual valuation \(\ge t\).
This auction fulfills an optimality criterion: The expected revenue is greater than or equal to \(\frac{1}{2}\) the expected revenue of the best revenue-maximizing auction.

Q: An auction is [...] iff [...].
A: prior-independent; neither the allocation nor the payment rules reference the prior distributions of valuations \(D_1, \dots, D_n\)

The Bulow-Klemperer theorem states that adding a bidder and then executing the second-price auction generates more revenue than holding a revenue-maximizing auction with a known distribution of valuations.
Mathematically, \(\mathbb{E}_{v \sim D^{n+1} } [\sum_{i \in [n+1]} p_i(v)] \ge \mathbb{E}_{v \sim D^n}[\sum_{i \in [n]} p_i^*(v)]\), where the symbols stand for: \(p\): the payment rule of the second price auction with \(n+1\) bidders, \(p^*\) the payment rule of the revenue maximizing auction for \(n\) bidders.

Front: Since revenue-maximizing auctions are complex to set up, what do we do instead?
Back: We use auctions that approximate revenue-maximizing auctions.

Q: A [...] is [...]. It looks like this:
A: serac; a block/column of glacial ice, often larger than a house

Q: In two player zero-sum games, a Nash equilibrium can be found by [...].
A: computing the maximin strategies for both players, which then constitute the Nash equilibrium

Front: What is a maximin strategy?
Back: The maximin strategy for player \(i\) maximizes \(i\)'s worst-case payoff, mathematically
\(\text{arg max}_{s_i}(\text{min}_{s_{-i}} u_i(s_i, s_{-i}))\).

Front: Why do naive attempts at regularizing neural networks fail?
Back: With normal methods, such as using a hinge loss which contains a margin, the training procedure gets around this by just multiplying the weights by a constant factor.

Q: The two additional AGM postulates are
7. [...]
8. [...]
A: Superexpansion: \(K*(P \land Q) \subseteq (K*P)+Q\); Subexpansion: If \(\lnot Q \not \in K*P\), then \((K*P)+Q \subseteq K*(P \land Q)\)

Q: In machine learning, [...] is [...].
Mathematically, it [...].
A: Structural risk minimization; a method of balancing a model's complexity against its success in fitting training data; minimizes the function \(E_{\text{train} }+βH(w)\), where \(E_{\text{train} }\) is the training error, \(H(w)\) is a regularization function of the parameters (where \(w\) with high VC dimension receive high values), and \(β\) is a constant

Q: In machine learning, SRM stands for [...].
A: structural risk minimization

Q: In machine learning, LMC stands for [...].
A: large margin classifier

Front: How does one compute a hyperplane classifier in a feature space defined by a function \(Φ\) for some weight vector \(w\) and bias \(b\)?
Back: \(y=\text{sgn}(w \cdot Φ(x)+b)\)

Front: What is the optimization problem with hyperplane classifiers in a feature space induced by the kernel \(Φ\), weight vector \(w\), bias \(b\), and dataset \(\mathbf{x}, \mathbf{y}\) of size \(N\)?
Back: Minimize \(||w||^2\)
subject to \(y_i \cdot ((w \cdot Φ(x_i))+b) \ge 1\) for \(i=1 \dots N\)

Q: If a primal optimization problem [...], the dual can be used to find [...].
A: is a maximization problem; upper bounds on its optimal value

Front: In the context of support vector machines with kernel \(Φ\), what is the optimization problem of hyperplane classifiers with slack variables \(ξ\), weights \(w\), bias \(b\), and \(N\) datapoints \(\mathbf{x}, \mathbf{y}\)?
Back: Minimize \(||w||^2+C \sum_{i=1}^N ξ_i^p\), where \(C\) is a parameter describing how much slack variables are penalized,
subject to \(y_i \cdot ((w \cdot Φ(x_i))+b) \ge 1-ξ_i\) and \(ξ_i \ge 0\) for \(i=1, \dots, N\).

Q: In machine learning, SMO stands for [...].
A: sequential minimal optimization

In optimization theory, the dual of an optimization problem is:
With an optimization problem \(\underset{θ}{\text{min} } f(θ)\) where \(f\) is convex,
subject to \(\forall_{i=1}^{m} g_i(θ) \le 0\), \(g_i\) convex.
Then the Lagrange dual formulation of the optimization problem is
\(\underset{\mathbf{α} }{\text{max} }(\underset{θ}{\text{min} }(f(θ)+\sum_{i=1}^m α_i g_i(θ)))\),
subject to \(\forall_{i=1}^m α_i \ge 0\).

Front: In the context of support vector machines, what is Slater's condition?
Back: The two classes are linearly separable in the feature space spanned by \(ϕ\).

Q: In neural networks, the [...], the [...].
A: smaller the ratio between the highest and the lowest eigenvalue of the Hessian matrix of a neural network; faster the convergence

Front: How do you center a dataset \(\mathbf{x} \in ℝ^n\)?
Back: For each datapoint \(x_i\), set
\(x_i:=x_i-\frac{1}{N} \sum_{j=1}^n x_j\)

Front: What is the intuitition for what the parameter \(λ\) in rigde regression describes?
Back: The steepness of the regression hyperplane, the smaller \(λ\), the steeper the plane can be.

Q: In the context of support vector machines, the relative advantage of
• the primal optimization problem is [...]
• the dual optimization problem is [...]
A: • when the dimension \(D\) is relatively small, but \(N\) is large
    • the optimization of a vector \((\mathbf{w}, b) \in ℝ^{D+1}\) subject to \(N\) constraints; • when the \(N\) is relatively small, but \(D\) can be large
    • the computation of a kernel matrix \(K \in ℝ^{N \times N}\)

The three edges of Zooko's triangle are
• Human meaningful
• Secure
• Decentralized

Front: What is Zooko's triangle?
Back: It's a trilemma that describes three properties that names in networks should have.

Front: What's the Zooko Wilcox-O'Hearn conjecture?
Back: No single kind of naming mechanism in computer networks can fulfill all of
• Human-meaningful
• Secure
• Decentralized

Q: A [...] is a system that [...].
A: petname system; claims to posses all three properties in Zooko's triangle

Q: A [...] is [...].
A: hypocorism; a name used to show affection for another person or object