Title: Artificial Intelligence: A Modern Approach
Tags: addimg

Front: What things specify a task environment?
Back: PEAS: performance measure, environment, actuators, sensors

Front: What are the dimensions along which to categorize environments?
Back: fully vs. partially observable/single vs. multi-agent/deterministic vs. stochastic/episodic vs. sequential/static vs. dynamic/discrete vs. continuous/known vs. unknown

Front: Define fully vs. partially observable
Back: Environment is fully observable if the sensors detect all aspects that are relevant to the choice of action, partially observable if not all

Front: Define unobservable in the context of environments
Back: If the agent has no sensors at all.

Front: Define single-agent vs. multi-agent
Back: Environment is multi-agent when all other things in the environment are best modeled as agents, single-agent if not

Front: Define deterministic vs. stochastic
Back: An environment is deterministic if the next state of it is completely determined by the current state and the action executed by the agent

Front: Define uncertain for an environment
Back: An environment is uncertain if it not fully observable or not deterministic.

Front: Define episodic vs. sequential
Back: An environment is episodic if the next episode of percepts is not dependent on the action taken in previous episodes

Front: Define static vs. dynamic
Back: An environment is dynamic if it can change while the agent is deliberating, static if not

Front: Define semidynamic
Back: The environment doesn't change during deliberation, but the performance score does

Front: Define discrete vs. continuous for environments
Back: Discrete if the environment has a finite number of distinct states, continuous if not (applies to environment states, time, percepts & actions)

Front: Define known vs. unknown
Back: An environment is unknown if the agent does not have complete knowledge about the “laws of physics” in the environment

Front: What, in combination, are the hardest types of environments?
Back: Partially observable & multiagent & stochastic & sequential & dynamic & continous & unknown

Front: What is the composition of an agent?
Back: agent=architecture + program

Front: What are the four basic kinds of agents?
Back: • Simple reflex agents
• Model-based reflex agents
• Goal-based agents
• Utility-based agents

Front: Define a simple reflex agent
Back: Selects actions on the basis of the current percept, ignoring the rest of the percept history

Front: What is the schematic of a simple reflex agent?

Front: Define a model-based reflex agent
Back: A reflex agent with a model of the world (i.e. an internal state that gives predictions about the effects of the agent's actions)

Front: What is the schematic of a model-based reflex agent?

Front: Define a goal-based agent.
Back: A goal-based agent is a model-based agent where instead of choosing the next action based on fixed rules, available actions are evaluated using a goal criterion.

Front: What is the schematic of a goal-based agent?

Front: Define a utility-based agent
Back: A utility-based agent is a goal-based agent where states are evaluated using a utility function (an internalization of the performance measure)

Front: What can a utility-based agent do that a goal-based agent can't?
Back: Make trade-offs between different, conflicting goals; reason based on expected value

Front: What is the schematic of a utility-based agent?

Front: What is the schematic of a general learning agent?

Front: What are the parts of a general learning agent?
Back: Critic, learning element, problem generator, performance element (which usually contains a utility-based agent)

Front: What are the rough categories of environment representation?
Back: Atomic, Factored, Structured

Front: Define atomic environment representation
Back: In an atomic representation, each state of the world is indivisible

Front: Define factored environment representation
Back: A factored representation splits up each state into a fixed set of variables or attributes, each of which can have a value

Front: Define structured environment representation
Back: Structured representations contain objects and their relationships to each other

Front: Drawbacks of problem-solving and logical agents
Back: • Combinatorial explosion due to considering every possible explanation for observations
• Contingent plans can grow arbitrarily large
• No plan available, yet agent must act

Front: State the principle of maximum expected utility
Back: An agent is rational if and only if it chooses the action that yields the highest expected utility, averaged over all possible outcomes of the action

Front: What are the conditions that have to be satisfied in a probability model \(\Omega\)?
Back: \(0 \le P(\omega) \le 1 \hbox{ for every } \omega \hbox{ and } \sum_{\omega \in \Omega} P(\omega)=1\)

Front: \(P(\text{cavity}|\text{toothache})=0.6\) does not mean “Whenever toothache is true, conclude that cavity is true with probability 0.6”. What does it mean instead?
Back: “Whenever toothache is true and we have no further information, conclude that cavity is true with probability 0.6.”

Front: State Bayes Theorem in the case of two variables
Back: \(P(A|B)=\frac{P(B|A) P(A)}{P(B)}\)

Front: State the product rule for two variables.
Back: \(P(a \land b)=P(a|b)P(b)\)

Front: Define a probability density function
Back: A probability density function is a function that returns the value of a probability distribution on a continuous domain.

Front: How does one obtain the probability density of a random variable \(X\) at \(x\)?
Back: \(P(x)=\underset{dx \rightarrow 0}{\lim} \frac{P(x \le X \le x+dx)}{dx}\)

Front: Define a full joint probability distribution.
Back: A full joint probability distribution is the probability distribution over all possible combinations of values for random variables (that is, the cartesian product of those variables).

Front: State the inclusion-exclusion principle.
Back: \(P(a \lor b)=P(a)+P(b)-P(a \land b)\)

Front: What is the frequentist stance on the question “Where do probabilities come from?"?
Back: Probabilities can come only from experiments, probabilities are fractions that would be observed in the limit of infinitely many samples.

Front: What is the objectivist stance on the question “Where do probabilities come from?"?
Back: The objectivists believe that probabilities are real aspects of the universe (of the objects in it to behave in certain ways), and not just descriptions of an observer's degree of belief.

Front: What is the subjectivist stance on the question “Where do probabilities come from?"?
Back: Probabilities are ways of characterizing an agent's beliefs.

Front: What is the subjectivist Bayesian stance on the question “Where do probabilities come from?"?
Back: Probabilities are degrees of belief for agents (initially priors), and are then updated using Bayes' rule.

Front: State the formula for the sum rule for two sets.
Back: \(P(Y)=\sum_{z \in Z} P(Y, z)\)

Front: State the formula for conditioning/summing out for two sets of conditional probabilities.
Back: \(P(Y)=\sum_{z \in Z} P(Y|z)P(z)\)

Front: Define normalization in the context of probability theory.
Back: Multiplying a random variable joined with another random variable by a constant to obtain the conditional distribution.

Front: Given a single random variable \(X\), a set of evidences \(e\), and a set of remaining unobserved variables \(Y\), state the general inference procedure of \(X\).
Back: \(P(X|e)=αP(X,e)=α\sum_{y} P(X,e,y)\)

Front: How well does bayesian inference scale?
Back: Not very well, in requires an input table of size \(O(2^n)\) and taken \(O(2^n)\) time to process.

Front: When are two random variables \(A\) and \(B\) independent?
Back: If \(P(A|B)=P(A)\) or \(P(B|A)=P(B)\) or \(P(A, B)=P(A)P(B)\)

Front: State Bayes theorem for two variables and additional evidence.
Back: \(P(X|Y,e)=\frac{P(Y|X,e)P(X|e)}{P(Y|e)}\)

Front: State the general form of Bayes' rule with normalization.
Back: \(P(A|B)=αP(B|A)P(A)\)

Front: State the intuition behind conditional independence.
Back: When we have observed one variable (e.g. that someone has a cavity), then two other variables who were previously dependent can become independent (e.g. whether the cavity is caught and whether there is a toothache).

Front: State the formula that holds iff \(X\) and \(Y\) are conditionally independent given \(Z\).
Back: \(P(X,Y|Z)=P(X|Z)P(Y|Z)\) or alternatively \(P(X|Y, Z)=P(X|Z)\) or \(P(Y|Z)=0\).

Front: What does Cox's theorem state?
Back: That any consistent system for uncertain reasoning that meets a set of assumptions (e.g. can't be dutch-booked, no contradictions, correspondence with propositional logic, different degrees of belief as numbers) is equivalent to standard probability theory.

Front: Give the specification of a Bayesian network
Back: 1. Each node corresponds to a random variable, which may be discrete or continuous
2. A set of directed links connects pairs of nodes. If there is any arrow from node X to node Y, X is said to be a parent of Y. The graph has no cycles.
3. Each node \(X_{i}\) has a conditional probability distribution \(P(X_{i}|Parents(X_{i}))\) that quantifies the effects of the parents on the node.

Front: Whas is a conditional probability table?
Back: It's a table in a Bayesian network attached to a random variable, which gives probabilities for the variable conditional on its parents having certain values.

Front: What are the two ways in which the semantics of Bayesian networks can be understood?
Back: 1. A representation of the joint probability distribution
2. An encoding of a collection of conditional independence statements

Front: How does one compute the joint probability on an entry \(P(x_1, \dots, x_n)\) in a Bayes network?
Back: \(P(x_1, \dots, x_n)=\prod_{i=1}^{n} P(x_i|parents(X_i))\)

Front: State the chain rule for a joint probability \(P(x_1, \dots, x_n)\).
Back: \(P(x_1, \dots, x_n)=\prod_{i=1}^{n}P(x_i|x_{i-1},\dots,x_1)\)

Front: When is a Bayesian network a correct representation of the domain?
Back: Only if each node is conditionally independent of its other predecessors in the node ordering, given its parents.

Front: Which two facts about independence do topological semantics specify for Bayesian networks?
Back: 1. That each variable is conditionally independent of its non-descendants, given its parents.
2. That each variable is conditionally independent of every other node given its Markov blanket.

Front: What is the Markov blanket of a node in a Bayesian network?
Back: Its parents ∪ its children ∪ its children's parents.

Front: What is the size of a Bayesian network with n nodes, given that the maximum number of parents is k?
Back: \(O(n \cdot 2^k)\)

Front: In a Bayesian network, what is a deterministic node?
Back: A deterministic node has its value specified exactly by the values of its parents, with no uncertainty.

Front: What is a noisy-OR node in a Bayesian network?
Back: It's a node that is true whenever any of its parents is true.

Front: What is a nonparametric representation of a node in a Bayesian network?
Back: Representing a conditional probability distribution implicitely with a collection of instances, each containing specific values for of the parent and child variables.

Front: What's a hybrid Bayesian network?
Back: A network that can contain both discrete and continous random variables.

Front: What is a probit-distribution?
Back: It's using the integral of the standard normal distribution as a conditioning random variable (\(P(x|Y=y)=\Phi((-y+\mu)/\sigma\)). probit=probability unit

Front: What is a logit-distribution?
Back: It's using the logistic function as a conditioning random variable \(P(x|Y=y)=\frac{1}{1+exp(-2\frac{-y+\mu}{\sigma})}\).

Front: What are the relative benefits of logit and probit distributions?
Back: A logit distribution has longer tails & is easier to deal with mathematically, while probit is often better for real situations.

Front: What is the time complexity for Bayesian inference in a network with \(n\) Boolean variables?
Back: \(O(n2^n)\)

Front: What is the ENUMERATION-ASK algorithm used for?
Back: It performs inference in Bayesian networks.

Front: What are the time and space complexity of the ENUMERATION-ASK algorithm?
Back: \(O(n2^n)\), \(O(2^n)\)

Front: In Markov processes, what does \(X_{a:b}\) stand for?
Back: The variables from \(X_a\) to \(X_b\), inclusive.

Front: State the Markov assumption.
Back: The current state depends on only a finite fixed number of previous states.

Front: What is a first-order Markov process?
Back: A Markov process in which the current state depends only on the previous state and not on any earlier states (i.e. \(P(X_t | X_{0:t−1}) = P(X_t | X_{t−1})\) .

Front: How do Markov models deal with the fact that there are infinitely many possible values of \(t,\)and therefore infinitely many distributions for those variables?
Back: It assumes that every change in the world state is caused by a stationary process, a process of change that is governed by unchanging laws.

Front: State the sensor Markov assumption for evidence variables \(E_t\) and state variables \(X_t\).
Back: \(P(E_t|X_{0:t}, E_{0:t-1})=P(E_t|X_t)\)

Front: State the formula for computing the complete joint distribution over all variables in first-order Markov models.
Back: \(P(X_{0:t}, E_{1:t})=P(X_0)\prod_{i=1}^{t}P(X_i|X_{i-1})P(E_i|X_i)\)

Front: In first-order Markov models, give the formulas for the
1. Initial state model
2. Transition model
3. Sensor model
Back: 1. \(P(X_0)\)
2. \(P(X_i|X_{i-1})\)
3. \(P(E_i|X_i)\)

Front: What are the basic inference tasks for Markov models?
Back: Filtering/state estimation, Prediction, Smoothing, Most likely explanation, Learning

Front: Define the task of filtering/state estimation for Markov models
Back: Computing the belief state–the posterior distribution over the most recent state–given all evidence to date: \(P(X_t|e_{1:t})\)

Front: Define the task of prediction for Markov models
Back: Computing the posterior distribution over the future state given all evidence to date: \(P(X_{t+k}|e_{1:t})\) for some \(k>0\)

Front: Define the task of smoothing for Markov models
Back: Computing the posterior distribution over a past state, given all evidence up to the presence: \(P(X_k|e_{1:t})\) for some \(k\) so that \(0 \le k<t\)

Front: Define the task of finding the most likely explanation for Markov models
Back: Given a sequence of observations, find the sequence of states that is most likely to have generated those observations: \(\hbox{argmax}_{X_{1:t}}P(x_{1:t}|e_{1:t})\)

Front: Define the task of learning for Markov models
Back: The transition and sensor models can be learned from observations as a by-product of inference–inference provides an estimate of what transitions actually occurred and which states generated the sensor readings.

Front: Motivate and describe an algorithm for filtering in a Markov model.
Back: We can think of the filtered estimate \(P(X_t|e_{1:t})\) as a “message” \(f_{1:t}\) that is propagated forward along the sequence:
\(f_{1:t+1}=α\hbox{FORWARD}(f_{1:t}, e_{t+1})\), where \(\text{FORWARD}\) begins with \(f_{1:0}=P(X_0)\).

Front: What is the time and space complexity of forward filtering in Markov models?
Back: When all the state variables are discrete, the time and space for each update are constant, which makes the whole algorithm linear \(O(t)\) in time, and constant in space

Front: Give the recursive formula for prediction in Markov models
Back: \(P(X_{t+k+1}|e_{1:t})=\sum_{X_{t+k}}P(X_{t+k+1}|x_{t+k})P(x_{t+k}|e_{1:t})\)

Front: Give the formula for computing the likelihood of the evidence sequence \(P(e_{1:t})\)
Back: The likelihood is computed using the following formula:
\(L_{1:t}=P(e_{1:t})=\sum_{x_t}\ell_{1:t}(x_t)\)
For this, compute the likelihood message \(\ell_{1:t}(X_t)=P(X_t,e_{1:t})\) using the recursive
\(\ell_{1:t+1}=\hbox{FORWARD}(\ell_{1:t}, e_{t+1})\)

Front: Give the formula for smoothing in Markov models and motivate the structure.
Back: We need to compute \(P(X_k|e_{1:t})\). For that, we split the evidence into two parts: the evidence up to \(X_k\) (\(f_{1:k}\)), and the evidence after \(X_k\) (\(b_{k+1:t}\)). Then \(P(X_k|e_{1:t})=αf_{1:k} \times b_{k+1:t}\) (pointwise multiplication of the vectors).
We can compute \(b_{k+1:t}=\hbox{BACKWARD}(b_{k+2:t}, e_{k+1})\), and FORWARD is implemented just as in filtering, with \(f_{1:k}=α\hbox{FORWARD}(f_{1:k-1}, e_{k})\), where FORWARD begins with \(f_{1:0}=P(X_0)\).

Front: Describe the forward-backward algorithm.
Back: First, compute the filtering over the whole sequence. Then, run backward recursion from \(t\) down to 1, and compute the smoothed estimate for each step \(k\) from the computed backward message \(b_{k+1:t}\) and the stored forward message \(f_{1:k}\).

Front: Give the recursive formula for the probability of the most likely explanation of the observations (the Viterbi algorithm).
Back: \(\underset{x_1, \dots, x_t}{\hbox{max}}P(x_1, \dots, x_t, X_{t+1} | e_{1:t+1})=αP(e_{t+1}|X_{t+1})\underset{x_t}{\hbox{max}}(P(X_{t+1}|x_t) \underset{x_1, \dots x_{t-1}}{\hbox{max}} P(x_1, \dots, x_{t-1}, x_t|e_{1:t}))\)
The algorithm for computing the most likely sequence is similar to filtering: it runs forward along the sequence, computing the m message at each time step.

Front: What is the space and time complexity of the Viterbi algorithm?
Back: Time and space are linear in \(t\), the length of the evidence sequence.

Front: Define a hidden Markov model (HMM).
Back: An HMM is a temporal probabilistic model in which the state of the process is described by a single discrete random variable, the possible values of the variable being the possible states of the world (e.g. a tuple containing the values).

Front: Give the formula for the \(BACKWARD\) algorithm
Back: \(P(e_{k+1:t}|X_k)=\sum_{x_{k+1}}P(e_{k+1}|x_{k+1})P(x_{k+1}|X_k)P(e_{k+2:t}|x_{k+1})\)

Front: Give the formula for the FORWARD algorithm
Back: \(P(X_{t+1}|e_{1:t+1})=αP(e_{t+1}|X_{t+1})\sum_{x_t}P(X_{t+1}|x_t)P(x_t|e_{1:t})\)

Front: In Hidden Markov models, what does \(T\) stand for?
Back: \(T\) is a matrix so that \(T_{ij}\) is the transition probability from state \(i\) to state \(j\).

Front: In Hidden Markov models, what does \(O_t\) stand for?
Back: \(O_t\) is a matrix so that \(O_{t_{ii}}=P(e_t|X_t=i)\)

Front: In matrix algorithms for HMMs, how does one compute the forward equation?
Back: \(f_{1:t+1}=αO_{t+1}T^{\top} f_{1:t}\)

Front: In matrix algorithms for HMMs, how does one compute the backward equation?
Back: \(b_{k+1:t}=TO_{k+1}b_{k+2:t}\)

Front: State the function that calculates the expected utility of executing action \(a\) given evidence \(e\).
Back: \(EU(a|e)=\sum_{s'}P(\hbox{RESULT}(a)=s'|a,e)U(s')\)

Front: What does the principle of maximum expected utility state?
Back: A rational agent should choose the action that maximizes the agent's expected utility:
\(\text{action}=\underset{a}{\hbox{argmax }} EU(a|e)\)

Front: What is a lottery in the context of decision theory?
Back: A lottery \(L\) is a distribution of probabilities over possible outcomes. With possible outcomes \(S_1, \dots, S_n\) that occur with probabilities \(p_1, \dots p_n\) it is written \(L=[p_1, S_1; p_2, S_2; \dots p_n, S_n]\)

Front: Name the six axioms of utility theory.
Back: Orderability, transitivity, continuity, substitutability, monotonicity, decomposability. (SCOT M. D.)

Front: Define orderability for preference relations.
Back: For any two things, one is preferable to the other, or both are equally valuable: \(A \succ B\) or \(B \succ A\) or \(A \sim B\).

Front: Define transitivity for preference relations.
Back: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C: \((A \succ B) \land (B \succ A) \Rightarrow (A \succ C)\).

Front: Define continuity in the context of preference relations.
Back: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1-p:
\(A \succ B \succ C \Rightarrow \exists p: [p, A; 1-p, C] \sim B\)

Front: Define substitutability in the context of preference relations.
Back: If an agent is indifferent between two lotteries \(A\) and \(B\), then the agent is indifferent between two more complex lotteries that are the same except that \(B\) is substituted for \(A\) in one of them: \(A \sim B \Rightarrow [p, A; 1-p, C] \sim [p, B; 1-p, C]\)

Front: Define monotonicity in the context of preference relations.
Back: If an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A: \(A \succ B \Rightarrow (p>q \Leftrightarrow [p, A; 1-p, B] \succ [q, A; 1-q, B])\)

Front: Define decomposability in the context of preference relations.
Back: Compound lotteries can be reduced to simpler ones using the laws of probability:
\([p, A; 1-p, [q, B; 1-q, C]] \sim [p, A; (1-p)q, B; (1-p)(1-q), C]\)

Front: Define preference ilicitation.
Back: Preference ilicitation is the process of presenting an agent with choices and using observed preferences to pin down the underlying utility function.

Front: Define normalized utilities.
Back: Normalized utilities are utility for which the best possible prize \(e_{\top}\) is set to \(U(e_{\top})=1\) and the worst possible catastrophe \(e_{\bot}\) is set to \(U(e_{\bot})=0\)

Front: Define insurance premium.
Back: The difference between the expected monetary value of a lottery and its certainty equivalent.

Front: When is an estimate of expected utility unbiased?
Back: When the expected value of the error is 0: \(\mathbb{E}[\hat{EU}(a|e)-EU(a|e)]=0\).

Front: What is the optimizer's curse?
Back: The tendency for the expected utility of the best choices to be too high, resulting in a bias towards optimism.

Front: How can one avoid the optimizers curse?
Back: Use an explicit probability model \(P(\hat{EU}|EU)\) of the error in the utility estimates. Given this model and a prior \(P(EU)\) on what we might reasonably expect the utilities to be, we treat the utility estimate, once obtained as evidence and compute the posterior distribution for the true utility using Bayes' rule.

Front: Define the certainty effect.
Back: People are irrationally strongly attracted to gains that are certain.

Front: What is multiattribute utility theory?
Back: Utility theory that deals with outcomes that are characterized by vectors of two or more attributes \(x=\langle x_1, \dots, x_n \rangle\), where each \(x_i\) is either a numeric value or a discrete value with an assumed ordering on values (without combining the attributes into a single value).

Front: Define strict dominance in multiattribute utility theory.
Back: If an option \(s_1\) is better on all attributes than some other option \(s_2\), \(s_1\) strictly dominates \(s_2\) (better can be both lower or higher, depending on the nature of the attribute).

Front: Define stochastic dominance in multiattribute utility theory.
Back: An option \(s_1\) stochastically dominates another option \(s_2\) if the cumulative distribution for \(s_1\) is always to the right of the cumulative distribution for \(s_2\).
More formally:
\(\forall x \int_{- \inf}^{x} p_1(x')dx' \le \int_{- \inf}^{x}p_2(x')dx'\)

Front: When are two attributes \(x_1, x_2\) of a multiattribute preference preferentially independent of a third attribute \(x_3\)?
Back: If the preference between outcomes \(\langle x_1, x_2, x_3 \rangle\) and \(\langle x_{1}', x_{2}', x_3 \rangle\) does not depend on the value of \(x_3\):
\(\forall x_1, x_2, x_3: \langle x_1, x_2, x_3 \rangle \bullet \langle x_{1}', x_{2}', x_3 \rangle \Leftrightarrow \langle x_1, x_2, x_{3}' \rangle \bullet \langle x_{1}', x_{2}', x_{3}' \rangle\) for \(\bullet \in \{\succ, \sim, \prec\}\)

Front: Define and explain mutual preferential independence.
Back: If two variables \(x_1, x_2\) are preferentially independent to each other, they are mutually preferentially independent. Wherease each attribute may be important, it does not affect the way in which one trades off the other attributes against each other.

Front: Define utility independence.
Back: The notion of utility independence extends preference independence to cover lotteries:
A set of attributes \(X\) is utility independent of a set of attributes \(Y\) if preferences between lotteries on the attributes in \(X\) are independent of the particular values of the attributes in \(Y\).

Front: When is a set of attributes mutually utility independent?
Back: If each of its subsets is utility-independent of the remaining attributes.

Front: Give the formula for a multiplicative utility function with \(n\) attributes, given \(U_i=U_i(x_i)\) the utility functions for the \(n\) different mutually utility independent attributes.
Back: Given \(U_i=U_i(x_i)\), and \(k_i\) always a constant:
\(U=\sum_{I \subset \{ 1\dots n \}}\prod_{i \in I} k_i U_i\)

Front: In a decision network, what is a chance node and what symbol represents it?
Back: A chance node represents a random variable, and is represented by an oval.

Front: In a decision network, what is a decision node and what represents it?
Back: A decision node is a point where the decision maker has a choice of action, and it is represented by a rectangle.

Front: In a decision network, what is a utility node and what symbol represents it?
Back: A utility node is the agent's utility function. It is represented by a diamond symbol.

Front: What is an action-utility network?
Back: It's a decision network in which all non-evidence nodes are omitted.

Front: State the algorithm for evaluating decision networks in natural language.
Back: 1. Set the evidence variables for the current state.
2. For each possible value of the decision node:
    (a) Set the decision node to that value.
    (b) Calculate the posterior probabilities for the parent nodes of the utility node, using a standard probabilistic inference algorithm.
    (c) Calculate the resulting utility for the action.
3. Return the action with the highest utility.

Front: Assuming that exact evidence can be obtained about the value of some random variable \(E_j\), with initial evidence \(e\) and the current best action \(α\), give the general formula for the value of information for \(E_j\).
Back: \(VPI_e(E_j)=(\sum_{k} \text{EU} (α_{e_{jk}}|e, E_j=e_{jk}) P(E_j=e_{jk}|e))-\text{EU}(α|e)\).

Front: Is VPI additive?
Back: No.

Front: What is order independence for VPI?
Back: The order of evidence is irrelevant.
Mathematically: \(\text{VPI}_e(E_j, E_k)=\text{VPI}_e(E_j)+\text{VPI}_{e, e_j}(E_k)=\text{VPI}_e(E_k)+\text{VPI}_{e, e_k}(E_j)\)

Front: State the algorithm for a shortsighted information gathering agent.

Front: When is an agent myopic?
Back: When it uses the VPI formula shortsightedly, calculating the value of information as if only a single evidence variable will be acquired, as opposed to formulating a plan to acquire conditional evidence.

Front: Define Markov decision process.
Back: A Markov decision process is a sequential decision process for a fully observable, stochastic environment with a Markovian transition model and additive rewards.

Front: What are the components of a Markov decision process?
Back: It consists of a set of states (with an initial state \(s_0\)); a set \(ACTIONS(s)\) of actions in each state, a transition model \(P(s'|s,a)\); and a reward function \(R(s)\).

Front: What is a policy?
Back: A policy is a function (usually written \(π\)) that recommends an action for every state.

Front: Define optimal policy.
Back: An optimal policy (usually denoted by \(\pi^*\)) is a policy that yields the highest expected utility.

Front: What is the difference between a finite horizon and an infinite horizon in decision making?
Back: A finite horizon means that there is a fixed time N after which nothing matters: \(U_h([s_0, s_1, \dots, s_{N+k}])=U_h([s_0, s_1, \dots, s_N])\).
An infinite horizon means the converse.

Front: What is an optimal policy for a finite horizon called?
Back: Nonstationary.

Front: When is a policy stationary?
Back: When it is optimal for an infinite horizon.

Front: When are the preferences between state sequences stationary?
Back: If \(s_0=s_{0}'\), then
\([s_0, s_1, s_2, \dots] \bullet [s_{0}', s_{1}', s_{2}', \dots] \Rightarrow [s_1, s_2, \dots] \bullet [s_{1}', s_{2}', \dots]\) for \(\bullet \in \{\succ, \sim, \prec\}\).
"If you prefer one future to another starting tomorrow, then you should still prefer that future if it were to start today".

Front: What are the two possible possible coherent ways to assign utilities to sequences under stationarity?
Back: 1. Additive rewards: The utility of a state sequence is
\(U_h([s_0, s_1, s_2, \dots])=R(s_0)+R(s_1)+R(s_2)+\dots\)
2. Discounted rewards: The utility of a state sequence is
\(U_h([s_0, s_1, s_2, \dots])=R(s_0)+γR(s_1)+γ^2 R(s_2)+\dots\) with \(0<γ<1\).

Front: What is the cool fact about discount factors and interest rates?
Back: A discount factor of \(γ\) is equivalent to an interest rate of \(\frac{1}{γ}-1\).

Front: What are the three solutions for possibly infinite rewards in MDPs with infinite horizons?
Back: Discounting, guaranteed reaching terminal states, average reward obtained per time step.

Front: Give the formula for the expected reward of executing the policy \(π\) starting in the state \(s\) (\(S_t\) being the state reached at time t when executing \(π\), as a random variable).
Back: \(U^π(s)=E[\sum_{t=0}^{\infty}γ^t R(S_t)]\)

Front: Give the formula for \(π^*(s)\) given the state s.
Back: \(π^*(s)=\underset{a \in A(s)}{\hbox{argmax}}\sum_{s'}P(s'|s,a)U(s')\)

Front: State the Bellman equation.
Back: \(U(s)=R(s)+γ \underset{a \in A(s)}{\hbox{ argmax }}\sum_{s'}P(s'|s,a)U(s')\), where \(s'\) are the neighbours of s.

Front: State the formula for a Bellman update.
Back: \(U_{i+1}(s) \leftarrow R(s) + γ \underset{a \in A(s)}{\hbox{max}} \sum_{s'} P(s'|s, a) U_s(s')\), where \(s'\) are the neighbours of s.

Front: Motivate and explain the value iteration algorithm.
Back: We want to solve an MDP (that is, assign utilities to every state). But we can't just do that using the Bellman equation, since they are nonlinear–we can't just solve the \(n\) unknowns.
Therefore, one uses an iterative approach, using the Bellman update on a set of arbitrary initial values that are updated until they reach an equilibrium.

Front: Informally, which steps does the policy iteration algorithm execute?
Back: Given an initial policy \(π_0\):
• Policy evaluation: Given a policy \(π_i\), calculate \(U_i=U^{π_i}\), the utility of each state if \(π_i\) were to be executed.
• Policy improvement: Calculate a new MEU policy \(π_{i+1}\), using one-step look-ahead based on \(U_i\): \(π_{i+1}[s] \leftarrow \underset{a \in A(s)}{\hbox{argmax}} \sum_{s'} P(s'|s,a) U_i[s']\)
Do this until a fixed point is reached (the policy evaluation shows that \(U_i-U^{π_i}<ε\)).

Front: Why is policy iteration easier than value iteration?
Back: Because the policy iteration algorithm can be simplified to a system of linear equations, since the neighbor Bellman equation is linear.

Front: State the simplified neighbor Bellman equation.
Back: \(U_i(s)=R(s)+γ\sum_{s'}P(s'|s, π_i(s))U_i(s')\)

Front: State the simplified neighbor Bellman update.
Back: \(U_{i+1}(s) \leftarrow R(s)+γ\sum_{s'}P(s'|s, π_i(s))U_i(s')\)

Front: Motivate and explain the modified policy iteration algorithm.
Back: Instead of updating the utilities, we update the policy until it doesn't change anymore.

Front: What is asynchronous policy iteration?
Back: It's the general algorithm of updating any subset of states and applying either policy improvement or simplified value iteration to that subset.

Front: What is a POMDP?
Back: A POMDP is an MDP with an only partially observable world: the agent does not necessarily know which state it is in.
It has the following components: a transition model \(P(s'|s,a)\), a set of actions \(A(s)\) for every state, a reward function \(R(s)\), and a sensor model \(P(e|s)\) that specifies the probability of perceiving evidence \(e\) in state \(s\) (usually called \(b(s)\)).

Front: Give the formula for calculating the belief state in a POMDP for a state \(s\), given evidence \(e\) and a previous action \(a\) (Hint: it's like the formula for filtering in Markov models).
Back: \(b(s)=αP(e|s)\sum_{s'} P(s|s',a)b(s')\)
(or, short, \(b=FORWARD(b,a,e)\))

Front: State the three steps of the decision cycle of a POMDP.
Back: 1. Given the current belief state b, execute the action \(a=π^{*}(b)\).
2. Receive percept e.
3. Set the current belief state to \(FORWARD(b,a,e)\) and repeat.

Front: Let \(p\) be a depth-\(d\) conditional plan whose initial action is \(a\) and whose depth-\(d-1\) subplan for percept \(e\) is \(p.e\).
Give the formula for the utility vector of the state \(s\) conditional on plan \(p\).
Back: \(α_p(s)=R(s)+γ(\sum_{s'}P(s'|s,a)\sum_{e} P(e|s')α_{p.e}(s'))\)

Front: Roughly describe the POMDP-VALUE-ITERATION algorithm.
Back: Here, equation (17.13) is simply assigning utility to states conditional on a plan \(p\), based on the likelihood of the next states.

Front: How many plans does POMDP-VALUE-ITERATION generate, given \(|A|\) actions and \(|E|\) possible observations, at planning depth d?
Back: \(|A|^{O(|E|^{d-1})}\)

Front: What is the function that empirically describes the utility of money for humans?
Back: \(U(s_n)=-263+22 \cdot \log(n+150000)\)

Front: What are the four factors that learning in agents depends on?
Back: • Which component is to be improved
• What prior knowledge the agent already has
• What representation is used for the data and the component
• What feedback is available to learn from

Front: Define inductive learning.
Back: Learning a general function or rule from specific input-output pairs.

Front: Define deductive learning.
Back: Going from a know general rule to a new rule that is logically entailed.

Front: Define unsupervised learning.
Back: The agent learns patterns in the input even though no explicit feedback is supplied.

Front: Define reinforcement learning.
Back: The agent learns from rewards or punishments, and decides which actions prior to the reinforcement were responsible for it.

Front: Define supervised learning.
Back: The agent observes input-output pairs and learns a function that maps input to output.

Front: Define semi-supervised learning.
Back: Learning with a few labeled examples (possibly with noise) and many unlabeled examples.

Front: What is a regression?
Back: A regression is a classification problem with numbers.

Front: When is a hypothesis in learning consistent?
Back: If it predicts the data perfectly.

Front: When is a learning problem realizable?
Back: If the hypothesis space contains the true function.

Front: Define a decision tree.
Back: A decision tree represents a function that takes as input a vector of attribute values and returns a “decision” – a single output value.
This function works by performing a sequence of tests, arranged in a tree, with each leaf node in the tree specifying a value to be returned by the function.

Front: Define information theoretic entropy, first in normal language and then give the formula.
Back: Entropy is the measure of the uncertainty of a random variable; acquisition of information corresponds to a reduction in entropy.
\(H(V)=-\sum_k P(v_k) log_2 P(v_k)\)

Front: Give the formula for the entropy of a Boolean random variable that is true with probability \(q\).
Back: \(B(q)=-(q \log_2 q+(1-q) \log_2 (1-q))\)

Front: Given: An attribute \(A\) with \(d\) distinct values divides the training set \(E\) into subsets \(E_1, \dots, E_d\). Each subset \(E_k\) has \(p_k\) positive examples and \(n_k\) negative examples.
What is the expected entropy remaining after testing attribute \(A\)?
Back: For every subset \(E_k\), the binary entropy of the subset, weighted by how many elements the subset contains relative to all elements in the training set. The sum is the remaining entropy.
\(\text{Remainder}(A)=\sum_{k=1}^{d}\frac{p_k+n_k}{p+n} B(\frac{p_k}{p_k+n_k})\)
(It simply is the expected entropy over all classes!)

Front: What is the formula for the information gain from the attribute \(A\), given \(p\) positive and \(n\) negative examples in the training set?
Back: \(\text{Gain}(A)=B(\frac{p}{p+n})-\text{Remainder}(A)\)

Front: How does the importance function in learning decision trees work?
Back: Choose the attribute A that maximizes the \(Gain(A)\) of entropy explained by the variable.

Front: How does on combat overfitting in decision trees?
Back: 1. Start with a full tree.
2. Look at test node that has only leaf nodes as descendants.
3. If the test detects only noise (information gain is close to zero), replace the test with a leaf node.
4. Repeat.

Front: In pruning decision trees, how do we assess that a node given close to zero information?
Back: By performing a statistical test, usually a \(\chi^2\) test.

Front: In decision trees, what do we do when we have continuous or integer-valued input attributes?
Back: Find the split point (i.e. a value to divide the dataset at) that gives the highest information gain.

Front: What is the method for finding a split point while creating a decision tree?
Back: 1. Sort the values of the attribute
2. Consider split points that are between two examples in sorted order that have different classifications
3. Maximize the running totals of positive & negative examples on each side of the split point

Front: What is a regression tree?
Back: A regression tree is a tree that has at each leaf a linear function of some subset of numerical attributes, rather than a single value.
Regression trees are used mainly for continuous-value output attributes.

Front: What does a Q-learning agent do?
Back: It learns an action-utility function or Q-function, giving the expected utility of taking a given action in a given state.

Front: What is passive learning?
Back: Passive learning is learning with a fixed policy, the task is to learn the utilities of states or state-action pairs.

Front: What is active learning?
Back: Active learning encompasses both learning a policy and learning the utilities of states.

Front: What is direct utility estimation and how does it work?
Back: Direct utility estimation tries to estimate the utility of states.
It does so by taking all sequences in which the state occurs, and calculates the average of the total rewards in those sequences. It then assigns those values to the state.

Front: What does an adaptive dynamic programming agent do?
Back: It tries to learn the transition model of the environment and solve the corresponding MDP.
It does so by combining the transition model and the observed rewards using the Bellman equations to calculate the utilities of states.

Front: What is an uninformed search algorithm?
Back: An algorithm with no information about the problem other than its definition (also called blind search).
All they can do is distinguish goal states from non-goal states.

Front: What is an open-loop agent?
Back: An agent that does not take into account the percepts from its environment for decision-making.

Front: What components does a search problem have?
Back: An initial state, a set of actions, a transition model (a function \(f: S \times A \rightarrow S\)), a goal test (a function \(t: S \rightarrow \{\text{True}, \text{False}\}\) which gives \(\text{True}\) if the given state is the goal state), and a transition cost (\(c: S \times S \times A \rightarrow \mathbb{R}^+\) – the cost of transitioning from one state into the other using a specific action).

Front: Give a high-level overview of the simple problem solving agent.
Back: The agent first formulates a goal and a problem, then searches for the sequence of actions that solve the problem, and then executes the first action in the sequence.

Front: In the context of searching problems, what is an optimal solution?
Back: It's the solution that has the lowest path cost among all solutions.

Front: Define incremental formulations in the context of search problems.
Back: Start with an empty state, then search by adding to the state description.

Front: Define complete-state formulation in the context of search problems.
Back: Start with a complete state description, then change it while searching.

Front: What is the touring problem?
Back: Visit every node in a graph at least once, ending at the starting node.

Front: State the traveling salesperson problem (TSP).
Back: The TSP is the problem of finding the shortest tour that visits every node in a graph exactly once.

Front: What is the set of all leaf nodes available for expansion called?
Back: The frontier.

Front: In the context of tree search, what is a redundant path?
Back: It's a path for which there exists another path that ends in the same state (possibly shorter or less costly).

Front: Roughly describe the generalized tree search algorithm.

Front: Roughly describe the general graph search algorithm.

Front: What are the possible operations on a queue?
Back: • \(Empty?(queue)\) – is the queue empty?
• \(Pop(queue)\) – remove the first element
• \(Insert(element, queue)\) – insert an element

Front: What is the defining characteristic of a FIFO queue?
Back: Pops the oldest element of the queue.

Front: What is the defining characteristic of a LIFO queue?
Back: Pops the newest element of the queue.

Front: What are the criteria by which to evaluate search algorithms?
Back: • Completeness: Does the algorithm guaranteedly find the solution if it exists?
• Optimality: Does the strategy find the optimal solution?
• Time complexity: How long does it take to find a solution?
• Space complexity: How much memory is needed to perform the search.

Front: In search problems, how is the complexity of the problem expressed?
Back: In three factors:
• b, the branching factor (the maximum number of successors of any node)
• d, the depth of the shallowest goal node
• m, the maximum length of any path in the state space

Front: Define the total cost in the context of search problems.
Back: The sum of the search cost (time/space complexity) and the path cost of the solution.

Front: What is informed search?
Back: Search algorithms that know whether one non-goal state is “more promising” than another.

Front: Roughly describe breadth-first search.
Back: All nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded–the shallowest unexpanded node is chosen for expansion.

Front: What is the data structure that is useful in breadth-first search?
Back: A FIFO queue, since new & deeper nodes go to the back of the queue.

Front: How does breadth-first search rank according to the four criteria for search algorithms?
Back: • Complete ✔
• Optimal ✘ (shallowest goal not necessarily the best)
• Time complexity \(\mathcal{O}(b^d)\)
• Space complexity \(\mathcal{O}(b^d)\)

Front: What is the biggest problem with breadth-first search?
Back: The memory requirement, closely followed by the time complexity.

Front: What is the central idea behind uniform-cost search?
Back: The next node expanded is the node n with the lowest path cost \(g(n)\). This is done by storing the frontier as a priority queue ordered by \(g\).

Front: Roughly state the algorithm for uniform-cost-search.
Back: Nodes are checked for being the goal only once they get expanded, and the algorithm replaces nodes in the frontier with better alternatives if they're found.

Front: What is the basic idea of depth-first search?
Back: Expand the deepest node in the current frontier of the search tree. For this, use a LIFO queue.

Front: What is backtracking search?
Back: Only one successor node is generated at a time (rather than all successors); each partially expanded node remembers which successor to generate next.

Front: What are the time and space complexity of depth-limited search?
Back: Time: \(\mathcal{O}(b^\ell)\), space: \(\mathcal{O}(b\ell)\), given a limit \(\ell\).

Front: What is iterative deepening search?
Back: It's limited depth-first search where the limit is increased until a goal is found.

Front: What is bidirectional search and why is it useful?
Back: Bidirectional search runs two simultaneous searches–one forward from the initial state and the other backward from the goal, with the objective of the two searches meeting.
This is useful because \(b^{d/2}+b^{d/2}<<b^d\).

Front: In informed search, what is the evaluation function?
Back: The evaluation function is a function that returns a cost estimate for nodes.

Front: What is best-first search?
Back: It's a tree searching algorithm that expands the node with the lowest value for the evaluation function \(f(n)\).

Front: What is a heuristic function?
Back: The heuristic function \(h(n)\) returns the estimated cost of the cheapest path from the state at the node \(n\) to a goal state.

Front: What is greedy best-first search?
Back: It's the search algorithm that uses the heuristic function is the evaluation function \(f(n)=h(n)\), expanding the node with the lowest heuristic first.

Front: How does A* search work?
Back: A* search combines the cost to reach a node with its heuristic value (its estimated cost to reach the goal) to create the evaluation function: \(f(n)=g(n)+h(n)\), and then executes best-first search with that function.

Front: When is a heuristic \(h(n)\) admissible?
Back: An admissible heuristic is one that never overestimates the cost to reach the goal.

Front: When is a heuristic \(h(n)\) consistent?
Back: If it, for every node \(n\) and every successor \(n'\) of \(n\) generated by any action \(a\) with the cost \(c(n, a, n')\):
\(h(n) \le c(n,a,n')+h(n')\)
The estimated cost of reaching the goal from \(n\) is no greater than the step cost of getting to \(n'\) plus the estimated cost of reaching the goal from \(n'\).

Front: When is a search algorithm optimally efficient?
Back: No algorithm is guaranteed to expand fewer nodes than that algorithm.

Front: What are absolute and relative error in relation evaluating heuristics?
Back: Given the actual cost from the root to the goal \(h^*\), the absolute error is \(Δ \equiv h^*-h\), and the relative error is \(ε \equiv \frac{h^*-h}{h^*}\)

Front: What are the time and space complexity of A*?
Back: Time & space complexity:
    • \(\mathcal{O}(b^Δ)\) (if single goal & reversible actions, absolute heuristic error Δ)
    • \(\mathcal{O}(b^{εd})\) (for constant step cost >ε & solution depth d)

Front: What kind of environment representation do constraint satisfaction problems rely on?
Back: At least factored state representation.

Front: Give the components of a constraint satisfaction problem.
Back: A constraint satisfaction problem has three components: a set of variables \(X=\{X_1, \dots, X_n\}\), a set of domains \(D=\{D_1, \dots, D_n\}\) (one for each variable), and a set of constraints \(C\) that specifies allowed combinations of variables.

Front: What mathematical structure does a constraint \(C_i\) have in a constraint satisfaction problem?
Back: Each constraint \(C_i\) consists of a pair \(\langle \text{scope}, \text{rel} \rangle\) where \(\text{scope}\) is a tuple of variables that participate in the constraint and \(\text{rel}\) is a relation that defines the values that those variables can take on.

Front: In CSPs, what is a global constraint?
Back: A constraint that involves an arbitrary number of variables.

Front: What are the two possible steps in constraint satisfaction solving?
Back: 1. Searching for correct assignments
2. Propagating or inferring stricter constraints

Front: When is a variable in a CSP network node consistent?
Back: If the values in its domain satisfy all the variable's unary constraints.

Front: When is a variable in a CSP arc-consistent?
Back: If, for all variables in relation to it, each of its admissible values is consistent with some admissible value of the second variable.

Front: What is the space complexity of backtracking search?
Back: \(\mathcal{O}(m)\)

Front: How does iterative-deepening A* work?
Back: It is an iterated version of the A* algorithm, using the f-cost \(g(n)+h(n)\) as a cutoff value. Specifically, "at each iteration, the cutoff value is the smallest f-cost of any node that exceeded the cutoff on the previous iteration".

Front: Roughly, how does the AC-3 algorithm work?
Back: If we change the domain of a variables in an arc \((X_i, X_j)\), for example the domain \(D_i\), then we next consider all arcs \((X_i, X_k)\) where \(X_k\) is a neighbor of \(X_i\) and \(k \not = j\).
If we end up with an empty domain, we know the CSP is unsatisfiable.

Front: What is the worst-case runtime complexity of AC-3?
Back: \(\mathcal{O}(cd^3)\), where \(d\) is the maximal domain size and \(c\) is the number of binary constraints.

Front: When are two variables \(\{X_i, X_j\}\) path consistent?
Back: If, with respect to a fixed third variable \(X_m\), for every assignment \(\{X_i=a, X_j=b\}\) consistent with existing constraints, there is an assignment to \(X_m\) that satisfies the constraints on \(\{X_i, X_m\}\) and \(\{X_m, X_j\}\).

Front: What is the PC-3 algorithm?
Back: It's an algorithm that reduces domains in CSPs to achieve path consistency, in a way that is practically identical to the AC-3 algorithm.

Front: When is a CSP k-consistent?
Back: If, for any set of \(k-1\) variables and for any consistent assignment to those variables, a consistent value can always be assigned to the \(k\)th variable.

Front: Which \(k\)-consistencies are arc-consistency, path-consistency, and node-consistency equivalent to?
Back: • arc-consistency: 2-consistency
• node-consistency: 1-consistency
• path-consistency: 3-consistency

Front: When is a CSP strongly k-consistent?
Back: If it is \(k\)-consistent, \(k-1\)-consistent, … all the way down to 1-consistent.

Front: Roughly, how does backtracking search work in CSPs?
Back: Iterate through possible assignments, then infer, then recurse.

Front: In CSPs, what are useful ways to choose the next variable?
Back: Choose the variable with the fewest “legal” values–the minimum-remaining-values (MRV) heuristic.
If there is a tie for MRV, use the degree heuristic: select the variable that is involved in the largest number of constraints on other unassigned variables.

Front: In CSPs, what is a good way to order values during inference?
Back: Using the least-constraining-value heuristic. Choose the value that rules out the fewest choices for the neighboring variables in the constraint graph.

Front: When solving CSPs, what is forward checking?
Back: Whenever a variable \(X\) is assigned, we establish arc consistency for it.

Front: What does the MAC algorithm do?
Back: The MAC (Maintaining Arc Consistency) algorithm preserves arc consistency during search.
After a variable \(X_i\) is assigned a value, the INFERENCE procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs \((X_j, X_i)\) for all \(X_j\) that are unassigned neighbors of \(X_i\).

Front: In CSPs, what is chronological backtracking?
Back: When a branch of the search fails, back up to the preceding variable and try a different value for it.

Front: In CSPs, what is the conflict set of a variable?
Back: If the variable \(X\) can't have a consistent assignment, the conflict set is the set of assignments to neighboring variables that delete values from \(X\)'s domain.

Front: In CSPs, what is backjumping?
Back: It's a method that backtracks to the most recent assignment in the conflict set of a variable.

Front: How does conflict-directed backjumping work?
Back: Let \(X_j\) be the current variable, and let \(conf(X_j)\) be its conflict set. If every possible value for \(X_j\) fails, then backjump to the most recent variable \(X_i\) in \(conf(X_j)\), and set
\(conf(X_i) \leftarrow conf(X_i) \cup conf(X_j) \backslash \{X_i\}\)
Repeat this as often neccessary (or to the first assignment).

Front: What is constraint learning?
Back: Finding a minimum set of variables from the conflict set that causes the problem, the so-called no-good set.

Front: Using a complete-state formulation, what is a good heuristic for choosing a value to re-assign to variables in CSP search?
Back: The min-conflict heuristic: select the value that results in the minimum number of conflicts with other variables.

Front: What is tabu search?
Back: Tabu search keeps a small list of recently visited states and forbids the algorithm from returning to those states.

Front: How does constraint weighting work?
Back: Each constraint is given a numeric weight, initially 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints.
The weights are then adjusted by incrementing the weight of each constraint violated by the current assignment.

Front: In CSPs, what is an independent subproblem?
Back: It's a set of variables that only has constraints among itself.

Front: Why are independent subproblems important in CSPs?
Back: Because they can be solved independently from the rest of the problem, and the solution is simply the union of the assignments.
This also means that the two problems can be parallelized.

Front: What is the advantage for the computational complexity of independent subproblems for CSPs?
Back: Given subproblems with at most \(c\) variables out of \(n\), with a maximum domain size \(d\). Then the total work is \(\mathcal{O}(\frac{d^c n}{c})\), which is linear in \(n\).
Without the decomposition, the total work is \(\mathcal{O}(d^n)\).

Front: What is a knowledge base?
Back: A set of sentences.

Front: What are the three steps a logical agent program performs when it is called?
Back: 1. It TELLs the knowledge base what is perceives.
2. It ASKs the knowledge base what action it should perform.
3. It TELLs the knowledge base which action was chosen, and executes the action.

Front: What are the two basic operations for interacting with a knowledge base in propositional logic?
Back: \(ASK\) (query what is known) and \(TELL\) (add new sentences to the knowledge base).

Front: What is the difference between the declarative and the procedural approach to system building?
Back: Declarative: Starting with an empty knowledge base, the agent designer TELLs the system sentences one by one until the agent knows how to operate in its environment.
Procedural: Encode desired behaviors directly as program code.

Front: What are the semantics of a logic?
Back: It defines the truth of each sentence with respect to each possible world.

Front: What is a model in logic?
Back: It's an assignment to the variables used in a sentence (similar to the term “possible world”).

Front: What is the syntax of a representation language?
Back: The standard which defines which sentences are well formed.

Front: What does the notation \(M(α)\) mean in logic?
Back: It's the set of all models of α, all models under which α is true.

Front: What does \(α \models β\) mean?
Back: That \(β\) follows logically from \(α\); \(α\) entails \(β\).
\(α \models β\) iff every model of \(α\) is also a model of \(β\):
\(α \models β\) iff \(M(α) \subseteq M(β)\)

Front: What is model checking?
Back: It's an inference algorithm for logic that enumerates all possible models to check that \(α\) is true in all models in which KB is true \(M(KB) \subseteq M(α)\).

Front: What does the notation \(KB \vdash_i α\) mean?
Back: That the inference algorithm \(i\) can derive \(α\) from \(KB\).

Front: When is an inference algorithm sound?
Back: If it derives only entailed sentences.

Front: When is an inference algorithm complete?
Back: When it can derive any sentence that is entailed by the knowledge base.

Front: What is the operator precendence in propositional logic (from highest to lowest)?
Back: \(\lnot, \land, \lor, \Rightarrow, \Leftrightarrow\)

Front: What does the TT-ENTAILS? algorithm do?
Back: It performs a recursive enumeration of a finite space of assignments to symbols to discover whether the propositional knowledge base entails a sentence.

Front: State implication elimination in propositional logic.
Back: \(α \Rightarrow β \equiv \lnot α \lor β\)

Front: State contraposition in propositional logic.
Back: \(α \Rightarrow β \equiv \lnot α \Rightarrow \lnot β\)

Front: When are two sentences logically equivalent?
Back: If the have the same set of models:
\(α \equiv β\) iff \(α \models β\) and \(β \models α\).

Front: When is a sentence valid?
Back: If it is true in all models. Valid sentences are also known as "tautologies".

Front: State the deduction theorem.
Back: For any sentences \(α\) and \(β\), \(α \models β\) iff the sentence \(α \Rightarrow β\) is valid.

Front: When is a sentence satisfiable?
Back: If it is true in at least one model.

Front: How are validity and satisfiability connected?
Back: \(α\) is valid iff \(\lnot α\) is unsatisfiable, \(α\) is satisfiable iff \(\lnot α\) is not valid.

Front: State the mathematical formulation of the reductio ad absurdum.
Back: \(α \models β\) iff the sentence \(α \land \lnot β\) is unsatisfiable.

Front: State the mathematical formulation of the modus ponens.
Back: \(\frac{α \Rightarrow β, α}{β}\)

Front: State and-elimination.
Back: \(\frac{α \land β}{α}\)

Front: State the property of monotonicity in propositional logic.
Back: If \(KB \models α\) then \(KB \land β \models α\) for any sentences α and β.

Front: State the unit resolution inference rule.
Back: \(\frac{\ell_1 \dots \ell_k, m}{\ell_1 \lor \dots \ell_{i-1} \lor \ell_{i+1} \lor \dots \lor \ell_k}\)
where each \(\ell\) is a literal and \(\ell_i \equiv \lnot m\).

Front: State the full resolution inference rule.

Front: What normal form of sentences in propositional logic is resolution used for?
Back: Conjunctive normal form.

Front: How, on a very high level, does resolution do inference?
Back: To show that \(KB \models α\), it shows that \(KB \land \lnot α\) is unsatisfiable.
The resolution rule is applied repeatedly until:
• there are no new clauses that can be added, in which case KB does not entail \(α\); or
• two clauses resolve to yield the empty clause, in which case KB entails \(α\)

Front: Broadly state the algorithm for resolution.

Front: State the ground resolution theorem.
Back: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.

Front: How does resolution fare in regards to completeness and soundness?
Back: • Completeness: ✔
• Soundness: ✔

Front: What is a definite clause?
Back: A disjunction of literals of which exactly one is positive.

Front: What is a Horn clause?
Back: A disjunction of literals of which at most one is positive, which is equivalent to a conjunction of literals that implies a single literal.

Front: What is a Horn clause with no positive literals called?
Back: A goal clause.

Front: How does the forward-chaining algorithm \(\text{PL-FC-Entails}?(\text{KB}, q)\) work?
Back: It starts with known facts and Horn clauses. If all the premises of an implication are known, then its conclusion is added to the set of known facts.
This process continues until the query \(q\) is added or no further inferences can be made.

Front: Is forward chaining sound/complete?
Back: • Soundness: ✔
• Completeness: ✔

Front: Roughly, how does the backward chaining inference algorithm work?
Back: If the query \(q\) is known to be true, no work is needed.
Otherwise, the algorithm finds those implications in the knowledge base whose conclusion is \(q\). If all the premises of one of those implications can be proved true (by backward chaining), then \(q\) is true.

Front: When can an agent's behavior be described using a multiplicative utility function?
Back: If the attributes of its utility function are mutually utility independent.

Front: What kinds of things does first-order logic deal with?
Back: Objects, functions and relations.

Front: What is the operator precedence in first-order logic?
Back: \(\lnot, =, \land, \lor, \Rightarrow, \Leftrightarrow\)

Front: In first-order logic, what is an atomic sentence?
Back: It's a predicate symbol optionally followed by a parenthesized list of terms, such as
\(\text{Brother}(\text{Richard}, \text{John})\)

Front: When writing out general rules with universal quantifiers, which connective is used best?
Back: Implication, not conjunction.

Front: What is the natural connective to use with an existential quantifier?
Back: Conjunction.

Front: In logic, what does \(\{x/y\}\) mean?
Back: Replacing \(y\) with \(x\), a substitution or binding list.

Front: When is a logical sentence a theorem?
Back: When it is entailed by the axioms.

Front: What is the fundamental idea for inference in first-order logic?
Back: Reduce the knowledge base in first-order logic to propositional logic, perform inference on that.

Front: What is the rule of universal instantiation?
Back: The rule of universal instantiation says that we can infer any sentence obtained by substituting a ground term (a term without variables) for the variable.
\(\frac{\forall v, α}{SUBST(\{v/g\},α)}\)
for any variable \(v\) and ground term \(g\), where \(SUBST(θ,α)\) denotes the result of applying the substitution \(θ\) to the sentence \(α\).

Front: What does the rule of existential instantiation state?
Back: The rule of existential instantiation says that we can replace a variable inside an existential quantifier with a single new constant symbol.
\(\frac{\exists v: α}{SUBST(\{v/k\},α)}\)
for any variable v, sentence α and constant symbol k, where \(SUBST(θ,α)\) denotes the result of applying the substitution θ to the sentence α.

Front: What is the constant used in the rule of existential instantiation called?
Back: The Skolem constant.

Front: How does propositionalization work for knowledge bases in first-order logic?
Back: Existential instantiation is applied to all sentences, then Universal instantion is applied using all possible ground-term substitutions from the vocabulary of the knowledge base.

Front: What is the computational complexity of entailment in first-order logic?
Back: It's semidecidable: algorithms exist that say yes to every entailed sentence, but no algorithm exists that also says no to every nonentailed sentence.

Front: State the generalized modus ponens.
Back: For atomic sentences \(p_i, p_i'\), and \(q\), where there is a substitution \(θ\) such that \(SUBST(θ, p_i')=SUBST(θ, p_i)\) for all \(i\),
\(\frac{p_1', p_2', \dots, p_n', (p_1 \land p_2 \land \dots \land p_n \Rightarrow q)}{SUBST(θ, q)}\)

Front: What is unification in first-order logic and how does it work?
Back: The \(UNIFY\) algorithm takes two sentences and returns a unifier for them if one exists, so that:
\(UNIFY(p,q)=θ\) where \(SUBST(θ, p)=SUBST(θ, q)\)

Front: In first-order logic, what is the most general unifier?
Back: It's the unifier that sets the fewest variables to ground terms that is unique up to renaming and substitution of variables.

Front: What do the functions \(STORE\) and \(FETCH\) do?
Back: \(STORE\) stores a sentence \(s\) into the knowledge base, \(FETCH(q)\) returns all unifiers such that the query \(q\) unifies with some sentence in the knowledge base.

Front: Roughly, how does the unification algorithm work?
Back: It recurses until it deals with single variables, then deals with every single variable separately.

Front: What characterizes a Datalog knowledge base?
Back: A knowledge base that contains no function symbols.

Front: How does forward chaining work in first-order logic?
Back: Starting from the known facts, the forward-chaining algorithm triggers all the rules whose premises are satisfied, adding their conclusions to the known facts.
The process repeats until the query is answered or no new facts are added.

Front: Is first-order forward chaining complete/sound?
Back: Yes/yes.

Front: What is the conjunct ordering problem? What does it have in common with constraint satisfaction solving?
Back: While performing forward checking in first-order logic, finding an ordering of conjuncts to solve find substitutions of the premise so that the total cost is minimized while searching.

Front: What is the rule of incremental forward chaining?
Back: Every new fact inferred on iteration \(t\) must be derived from at least one new fact inferred on iteration \(t-1\).
This is true because any inference that does not require a new fact on iteration \(t-1\) could have been done at iteration \(t-1\) already.

Front: Describe, roughly, how the backward-chaining algorithm for first-order knowledge bases works.
Back: The algorithm alternates between unifying the right-hand side of each known fact and the goal, and the each part of the left hand side of the known fact with the knowledge base.
It can return multiple results.

Front: What is Skolemization and how does it work?
Back: Skolemization is the process of removing existential quantifiers.
This is done either by introducing Skolem constants or Skolem functions, which take the original variable as an argument.

Front: State the resolution inference rule for first-order logic.

Front: When does one use Skolem functions instead of Skolem constants?
Back: When the existential quantifier is not at the beginning of the proposition, but inside another universal quantifier.

Front: What are the arguments of a Skolem function?
Back: The variables in the universal quantifiers around it.

Front: Roughly, how does recursive best-first search work?
Back: For each node, save f-value of the best alternative path available.
When backtracking, the f-value of the current node is propagated upwards and assigned to the newly chosen node.

Front: How does SMA* (simplified memory-bounded A*) work, roughly?
Back: SMA* proceeds just like A*, expanding the best leaf until the memory is full.
SMA* then drops the worst leaf node, the one with the highest f-value, while backing up the value of the forgotten node to its parent.
That way, the ancestor of a forgotten subtree knows the quality of the best path in that subtree.

Front: What is a good heuristic for choosing the next precondition in the conjunct ordering problem?
Back: A good heuristic for this is, as in CSPs, the minimum-remaining-values heuristic.

Front: How well does depth-first search fare with regard to optimality?
Back: ✘, it is not optimal (solution paths on the "left" are preferred to better ones on the "right")

Front: How well does depth-first search fare with regard to completeness?
Back: ✘, infinite expansion possible if tree-search or infinite search spaces

Front: What is the time complexity of depth-first search?
Back: \(\mathcal{O}(b^m)\)

Front: What is the space complexity of depth-first search?
Back: \(\mathcal{O}(bm)\)

Front: How does iterative deepening depth-first search rank according to completeness?
Back: ✔, if the branching factor finite and path cost always \(>ε\)

Front: How does iterative deepening depth-first search rank according to optimality?
Back: ✔, if step costs are identical, otherwise ✘

Front: How does iterative deepening depth-first search rank according to space complexity?
Back: \(\mathcal{O}(bd)\)

Front: How does iterative deepening depth-first search rank according to time complexity?
Back: \(\mathcal{O}(b^d)\)

Front: How does greedy best-first search fare in terms of optimality?
Back: ✘

Front: How does greedy best-first search fare in terms of completeness?
Back: ✘

Front: How does greedy best-first search fare in terms of space complexity?
Back: \(\mathcal{O}(b^m)\)

Front: How does greedy best-first search fare in terms of time complexity?
Back: \(\mathcal{O}(b^m)\)

Front: How does uniform-cost search fare with regard to optimality?
Back: ✔

Front: How does uniform-cost search fare with regard to completeness?
Back: ✔ if costs are >\(ε\) (\(ε\) constant)

Front: How does uniform-cost search fare with regard to time complexity?
Back: \(\mathcal{O}(b^{1+\lfloor \frac{C^*}{ε} \rfloor})\) (\(C^*\) being the cost of the optimal solution)

Front: How does uniform-cost search fare with regard to space complexity?
Back: \(\mathcal{O}(b^{1+\lfloor \frac{C^*}{ε} \rfloor})\) (\(C^*\) being the cost of the optimal solution)

Front: How does A* search rank on optimality?
Back: • tree-search version of A* optimal if \(h(n)\) is admissible
• graph-search version is optimal if \(h(n)\) is consistent

Front: How does A* search rank on completeness?
Back: ✔ (if step costs exceed finite \(ε, b\) is finite)

The DECISION-TREE-LEARNING algorithm works as follows:
Start with the most important attribute (the one that makes the most difference to the classification of an example).
Then:
1. If the remaining examples are all positive (or all negative), then we are done.
2. If there are some positive and some negative examples, choose the most important attribute, use it to classify.
3. If there are no examples left, return a default value (plurality classification for the node's parent).
4. If there are no attributes left, but both positive & negative examples, there has been error or noise. Return plurality classification.

Front: How does Recursive Best-First Search fare on completeness?
Back: ✔

Front: How does Recursive Best-First Search fare on optimality?
Back: ✔, if \(h(n)\) is admissible

Front: How does Recursive Best-First Search fare on space complexity?
Back: \(\mathcal{O}(m)\)

Front: How does Recursive Best-First Search fare on time complexity?
Back: Difficult to characterize

The steps for creating a decision network are:
• Create a causal model
• Simplifiy to a qualitative decision model
• Assign probabilities
• Assign utilities
• Verify and refine the model
• Perform sensitivity analysis

The steps involved in creating a decision network are:
• Create a causal model
• Simplifiy to a qualitative decision model
• Assign probabilities
• Assign utilities
• Verify and refine the model
• Perform sensitivity analysis

Q: Database semantics are established by the following conditions:
• [...]
• [...]
• [...]
A: Unique-names assumption: Every constant symbol refers to a distinct object; Closed-world assumption: Atomic sentences not known to be true are in fact false; Domain closure: Each model contains no more domain elements than those named by the constant symbols

To convert a sentence in first-order logic to conjunctive normal form, one follows these steps:
• Eliminate implications
• Move \(\lnot\) inwards
• Standardize variables (rename variables that occur twice or more)
• Skolemize
• Drop universal quantifiers (just leave them out)
• Distribute \(\lor\) over \(\land\)

Q: [...] states that [...].
A: Debreu's theorem for mutual independence; if attributes \(X_1, \dots, X_n\) in a multiattribute utility function are mutually preferentially independent, then the agent's preference behavior can be described as maximizing the function
\(V(x_1, \dots, x_n)=\sum_{i} V_i(x_i)\)

Q: In Markovian models, the time complexity for smoothing the whole sequence is [...], the space complexity for smoothing the sequence is [...].
A: \(O(t^2)\), (O(t)\) using dynamic programming; \(O(|f|t)\) (\(|f|\) being the size of the forward message)

Front: How does bidirectional search fare under the criterion of completeness?
Back: ✔ (if b finite and breadth-first in both directions)

Front: How does bidirectional search fare under the criterion of optimality?
Back: ✔ (if b finite & breadth-first & step costs are identical)

Front: How does bidirectional search fare under the criterion of time complexity?
Back: \(\mathcal{O}(b^{d/2})\)

Front: How does bidirectional search fare under the criterion of space complexity?
Back: \(\mathcal{O}(b^{d/2})\)

Front: How does SMA* fare on completeness?
Back: ✔ (if d (the sum of node sizes) is less than the memory size)

Front: How does SMA* fare on optimality?
Back: ✔ (if goal is reachable)

Q: [...] states that [...].
A: Debreu's theorem for mutual independence; If attributes \(X_1, \dots, X_n\) are mutually preferentially independent, then the agent's preference behavior can be described as maximizing the function:
\(V(x_1, \dots, x_n)=\sum_{i} V_i(x_i)\)

The knowledge-engineering process in logic has the following steps:
1. Identify the task
2. Assemble the relevant knowledge
3. Decide on a vocabulary of predicates, functions, and constants
4. Encode general knowledge about the domain
5. Encode a description of the specific problem instance
6. Pose queries to infer procedure and get answers
7. Debug the knowledge base

Q: The three important considerations when solving CSPs through backtracking are:
1. [...]
2. [...]
3. [...]
A: Which variables should be assigned next? In what order should values be tried?; What inferences should be performed at each step in the search?; When a search finds an assignment that violates a constraint, can we avoid repeating that assignment?