Cheat sheet

\documentclass[landscape]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[T1]{fontenc}
\usepackage{multicol}
\usepackage[margin=1cm]{geometry}
\usepackage[margin=1cm]{geometry}
\usepackage{soul}
\setlength{\parindent}{0in}
\begin{document}
\thispagestyle{empty}
\pagestyle{empty}
\begin{multicols}{3}

{\bf State space}: all possible configurations of the domain of interest\\
{\bf A start state}: $s_0 \in S$\\
{\bf Goal States}: The set of end states\\
{\bf Operators A}: Actions available , defined in terms of a mapping from a state to its successor\\
{\bf Path}: a sequence of states and operators\\
{\bf Path cost}: number associated with each path\\
{\bf Solution}: a path from $s_0$ to a goal state\\
{\bf Optimal solutions}: a solution with minimum cost\\
{\bf Search node}: a state, the parent state and the operator used to generate it, the cost of the path, the depth of the node\\
{\bf Candidate nodes}: a set of nodes to be expanded\\
{\bf Expanding a node}: Applying all legal operators to the state in the node and generating all successor states\\
{\bf Uninformed (Blind) search}: when we don't know how far a state is to the goal. Has exponential worst case complexity\\
{\bf Informed (heuristic) search}: a heuristic is used to guess how far the state is to the goal\\
{\bf Breadth-first search}: all nodes at level i get expanded before all nodes at level i+1, complete, $O(b^d)$ time and space complexity\\
{\bf Branching factor}: how many operators at most can be applied to a state\\
{\bf Solution depth}: how long is the path to the shallowest solution\\
{\bf Uniform cost search}: When you enqueue the nodes in a priority queue, ordered by increasing cost of the path. Guaranteed to find an optimal solution\\
{\bf Depth-first search}: Nodes at the deepest level get searched first, $O(bd)$ space comp, $O(b^d)$ time comp, not optimal, not complete.
{\bf Depth-limited search}: DFS, but cut off at a max depth. It always terminates, but still may not complete.\\
{\bf Iterative Deepening}: It's like depth-limited search but you increase the depth successively. It is complete, and has linear space requirements.\\
{\bf Heuristic}: Intuition about the distance from a state to the goal.\\
{\bf Best-First Search}: Nodes are enqueued in the order of most promising to least promising. $O(b^d)$ time complexity, not complete or optimal, greedy.
{\bf Heuristic Search Algorithm}: Enqueue nodes by the cost of the path and heuristic estimate of the node. \\
{\bf Admissible Heuristic}: if $h*(n)$ is the cost of the shortest path from $n$ to any goal, then $h(n)$ is admissible iff $h(n) \leq h*(n)$ \\
{\bf A* search}: Heuristic search with an admissible heuristic, it is complete and optimal\\
{\bf Consistent}: An admissible heuristic is consistent if $h(s) \leq cost(s,s') + h(s')$ for every state $s$ and its successors $s'$\\
{\bf Iterative Deepening A*}: Basically DFS, instead of max depth, we use max $f$ ($h + c$), we expand all nodes up to $f$, then we increase $f$. Uses less memory than A*.\\
{\bf Real-Time search}: instead of looking for a path to the goal, we just move in the direction of the best path.\\
{\bf Real-Time A*}: Do A* but with the g function equal to cost from current state rather than from the start\\
{\bf $\alpha$-pruning}: Maintain a value $\alpha$ that has the lowest f-value of any node in the current search horizon, and a node costing more than $\alpha$ will never be expanded.\\
{\bf Optimization Problems}: described by a set of states and an evaluation function, we are only interested in the best solution, and not the path.\\
{\bf Types of search methods}:
\begin{itemize}
    \item {\bf Constructive}: start from scratch, build a solution
    \item {\bf Iterative improvement/repair}: start with a suboptimal solution, and improve it
    \item {\bf Global search}: start from multiple states far apart, and go around the serch space
\end{itemize}
{\bf Hill climbing}: greedy local search. Start at a configuration, go to its best successor, repeat until the best successor is worst than the current state. Can get stuck in local extrema, can get stuck on a plateau.\\
{\bf Simulated annealing}: if a new value $E_i$ is better than old value $E$, move to $X_i$, if it's worse, move to $X_i$ with probability $e^{-\frac{E-E_i}{T}}$. T decreases with time. When T is high it's in exploratory phase, when T is low it's in exploitation phase. Simulated annealing is a randomized search or Monte Carlo search.\\
{\bf Genetic algorithms}: A solution is called an individual, each individual has a fitness, a set of individuals is a population. Populations change over generations by selection/mutation/crossover.\
{\bf Ways of selection}:
\begin{itemize}
    \item {\bf Fitness proportionate selection}: $Pr(i)=Fitness(i)/\sum_{j=1}^{p}Fitness(j)$
    \item {\bf Tournament selection}: pick 2 random individuals, compare them, the superior one is picked.
    \item {\bf Rank selection}: sort hypothesis by fitness, probability is proportional to rank
    \item {\bf Boltzman selection}: $Pr(i) = \frac{exp(Fitness(i)/T)}{\sum_{j=1}^p exp(Fitness(j)/T)}$
\end{itemize}
{\bf Elitism}: Best solution ever encountered in hill climbing/simulated annealing/genetic algorithms are saved.
{\bf Constraint satisfaction problem}: a solution that satisfies a set of contraints, basically a cost function with minimum value at the solution, and max value somewhere else. It is defined by:
\begin{itemize}
    \item A set of variables that can take values from a domain
    \item A set of constraints specifying what combination of values are allowed, they can be explicit ($A \neg 3$) or implicit ($A \neg B$)
    \item A CSP solution is an assignment of values to the variables such that all constraints are satisfied.
\end{itemize}
{\bf Binary CSP}: each constraint relates at most two variables\\
{\bf Constraint Graph}: Nodes are variables, arcs are constraints\\
{\bf Preferences(Soft constraints)}: represented using costs, lead to constrained optimization problems\\
{\bf Backtracking search}: Basically like DFS.\\
{\bf Forward checking}: Assign value to X, look at each unassigned Y connected to X and delete from Y's domain those values which are inconsistent with X's assignment\\
{\bf Complexity of CSP}:
\begin{itemize}
    \item Worst-case is $O(d^n)$, $d$ is number of possible values and $n$ is the number of variables
    \item Tree constraint graphs are $O(nd^2)$
    \item Nearly-tree structured graphs are $O(d^c(n-c)d^2)$ where $c$ is the number of variables which when removed turns the graph into a tree.
\end{itemize}
{\bf Iterative improvement algorithm}: Start with a broken assignment, reassign conflicted variables until less conflicts occur\\
{\bf Min-conflicts heuristic}: choose value that violates the fewest constraints. It solves CSP in almost linear time except for a very small subset of problems\\
{\bf Minimax search}: Expand a complete search tree, then go back up picking the worst value at min levels and best value at max levels. Complete if game tree is finite, optimal against optimal opponent. Time complexity $O(b^m)$, space complexity $O(bm)$. Cope with resource limitation by cutting off, and use heuristic to estimate values at cutoff.\\
{\bf $\alpha-\beta$ pruning}: We keep the best possible value for max as $\alpha$ and the best possible value for min as $\beta$ and if any node is lower we don't expand it. It does not affect the final result.\\
{\bf Monte Carlo tree search}: Play the game randomly according to some random policy for each player, then the value of each node is the average of the evaluations after the simulation. usually you have a minimax proportion and a monte carlo portion.\\
{\bf Rapid Action-Value Estimate}: Assume the value of the move is the same no matter when it is played.\\
{\bf Plan}: A collection of actions for performing some task with forms of knowledge representation to describe sets of states.
{\bf Declarative approach}: Build agents with two parts. A knowledge base which contains a set of facts expressed in formal/standard lang. An inference engine with general rules for deducing new facts\\
{\bf Logic}: Formal language for representing information. Syntax defines sentences in the language, semantics define the ``meaning'' of sentences\\
{\bf Ontological Commitment}: What exists in the language: facts/objects/relations/time\\
{\bf Epistemological Commitment}: What states of knowledge are in the language: true/false/etc\\
{\bf Interpretation}: A way of matching objects in the world with symbols in the sentence: a truth assignment: A sentence is valid if it's true in 1 interpretation, satisfiable if in all, unsatisfiable if in none.\\
{\bf Entailment(KB $\vDash \alpha$)}: KB entails $\alpha$ iff $\alpha$ is true in all worlds where KB is true.
{\bf Inference(KB $\vdash_i \alpha$)}: $\alpha$ can be derived from KB by inference procedure $i$. $i$ is sound if when KB $\vdash_i \alpha$, KB $\vDash \alpha$. $i$ is complete if when KB $\vDash \alpha$, KB $\vdash_i \alpha$.\
{\bf Model checking}: an inference proof method by enumerating a truth table.\\
{\bf Conjunctive normal form}: conjunction of disjunction of literals: OR clauses connected by ANDs\\
{\bf Disjunctive normal form}: disjunction of conjunction of literals: And clauses connected by ORs\\
{\bf Horn form}: Clauses with $\leq$ 1 positive literal, implications connected by ANDs\\
{\bf Resolution (for CNF)}: $\frac{\alpha \lor \beta, \neg \beta \lor \gamma}{\alpha \lor \gamma}$\\
{\bf Modus Ponens (Horn form)}: $\frac{\alpha_1,\ldots,\alpha_n, \alpha_1\lor\ldots\lor\alpha_n\rightarrow\beta}{\beta}$\\
{\bf Forward chaining}: when a new sentence is added to KB, resolution happens, new sentences are added to KB. Data driven, eager.\\
{\bf Backward chaining}: when query q is asked, if q is in KB, return true, else resolve q with other sentences in KB and continue. Goal driven, lazy\\
{\bf Implication elimination}: $\frac{\alpha \rightarrow \beta}{\neg \alpha \lor \beta}$\\
{\bf Planning graph}: Proposition and Action nodes arranged in levels in which they alternate. Lines between levels indicate pre/post conditions, lines within levels indicate mutual exclusions.
{\bf Predicates}: used to describe objects, properties, and relationships between objects.\\
{\bf Quantifier}: $\forall$ or $\exists$\\
{\bf Atomic sentences}: predicate($term_1,\ldots,term_n$) or $term_1 = term_2$, Term = function($term_1,\ldots,term_n$) or constant or variable\\
{\bf Complex sentences}: made from atomic sentences using connectives\\
{\bf Universal quantification}: $\forall x Taking(x,AI) \rightarrow Smart(x)$, {\bf Existential quantification}: $\exists x Taking(x,AI) \hat Smart(x)$
{\bf Quantifier properties}: $\forall x\forall y \leftrightarrow \forall y \forall x$, $\exists x\exists y \leftrightarrow \exists y \exists x$,  $\forall x\exists y \nleftrightarrow \exists y \forall x$
$\forall x f(x) \leftrightarrow \neg \exists x \neg f(x)$, same with exists.\\
{\bf Proofs}: Modus Ponens $\frac{\alpha, \alpha \rightarrow \beta}{\beta}$, And Introduction $\frac{\alpha \, \beta}{\alpha \hat \beta}$, Universal elimination $\frac{\forall x\alpha}{\alpha\{x/\tau\}}$, Resolution $\frac{\alpha \lor \beta, \neg \beta \lor \gamma}{\alpha \lor gamma}$\\
{\bf Skolemization}: $\exists f(x) = Rich(G1)$, if $\exists$ is inside $\forall$: $\forall x f(x) \leftarrow \exists y g(y) = \forall x f(x) \leftarrow g(H(x))$. $H(x)$ is a skolem function.\\
{\bf STRIPS}: Domain: a set of typed objects, states: first-order predicates over objects in conjunction, operators/actions defined in terms of preconditions and effects, goals: conjunction of literals.\\
{\bf STRIPS Operator}: preconditions are conjunctions of positive literals, postconditions are in terms of an Add-list and a Delete-list.\\
{\bf State-space planning}: finding a plan by looking through state space looking for a path from start to goal. Progression planners start from start, regression planners start from goal.\\
{\bf Progression (Forward) Planning}: Determine all applicable operators in the start state, apply operator, determine new content of knowledge base, repeat until goal is reached.\\
{\bf Goal Regression}: Pick action that satisfy (some of) the goal's propositions, make a new goal by removing conditions satisfied by this condition, adding the preconditions of this action, repeat until goal state is satisfied by the start state.\\
{\bf Variations of Goal Regression}: linear planning is a stack of goals, not complete. non-linear (set of goals) is complete but expensive.\\
{\bf Total vs Partial Order}: total: plan is always a strict sequence of actions, partial: plan steps may be unordered\\
{\bf Bayes rule}: P(H|e) = P(e|H)P(H)/P(e), P(e) = P (e|H)P (H) + P (e|$\neg$H)P($\neg$H). P(H|e) is posterior probability, P(H) is prior probability, P(e|H) is likelihood, P(e) is normalizing constant.\\
{\bf Conditional Independence}: $P(x | y,z) = P(x | z), \forall x,y,z$, Knowing the value of y does not change the probability of x if z is known. If $C$ and $F$ are conditionally independent, $P(C,F,B)$ decomposes to $P(C|B)P(F|B)P(B)$
\end{multicols}
\end{document}