Normal/Classic Search

Search ALGOS: (most examples are in traversing a maze)

• Frontier:
  • Depth-First Search (uses a stack) DFS
  • Breadth-First Search (uses a queue) BFS

Informed search: search startegy that uses problem-specific knowledge to find solutions more efficiently

Greedy Best-First search: search algo that expands the node is closest to the goal, esitmated by a heuristic function h(n)

A* Search: search algo that expands the node with lowest value of g(n) + h(n)

g(n) = cost to reach node

h(n) = estimated cost to goal

this algo is the optimal under these conditions:

• h(n) is admissible (never overestimates the true cost) and
• h(n) is consistent (for every node n and successor n’ with step cost c, h(n) <= h(n’) + c)

Adversarial Search:

like playing a game against opponent (tic tac toe, )

Minimax:

• MAX: (X) aims to maximize score
• MIN: (O) aims to minimize score

S0: init state

Player/s: returns which player to move in state s

ACTIONS(s) returns the set of actions that can be executed in state s

RESULT(s, a) returns the state resulting from performing action a in state s

TERMINAL(s): checks if state s is a terminal state (game over)

UTILITY(s): final numerical value for the terminal state s (score of the state)

The algo process: Given a state s:

• MAX picks action a in ACTIONS(s) that produces the highest value of MIN-VALUE(RESULT(s, a))
• MIN picks action a in ACTIONS(s) that produces the lowest value of MAX-VALUE(RESULT(s, a))

1
function MAX-VALUE(state):
2
  if TERMINAL(state):
3
    return UTILITY(state)
4
  v = -∞
5
  for action in ACTIONS(state):
6
    v = MAX(v, MIN-VALUE(RESULT(state, action)))
7
  return v

1
function MIN-VALUE(state):
2
  if TERMINAL(state):
3
    return UTILITY(state)
4
  v = ∞
5
  for action in ACTIONS(state):
6
    v = MIN(v, MAX-VALUE(RESULT(state, action)))
7
  return v

Alpha-Beta Pruning: I can ignore the rest of the nodes of already there is a choice for the other player that is less than we have already to optimize the minimax algo

Depth-Limited Minimax: after certain number of moves I won’t consider extra ones, this algo is important for complex games like Chess that got billions of possibilites that cannot be calculated in a reasonable time

evaluation function: function that estimates the expected utility of the game from a given state (the better this function is in estimating, the more intelligent the AI is)

Inference rules:

Modus Ponens, De Morgan’s Law, And elimination, implication elimination, Double Negation elimination, bi-conditional elimination, Distributive Property

Theorem Proving

works a bit like search problems

State: config of the agent and its knowledge base

Actions: inference rules

ACTIONS(s) returns the set of actions that can be executed in state s

transition model: new knowledge base after inference

RESULT(s, a) returns the state resulting from performing action a in state s

state space: the set of all states reachable from the inital state by any sequence of actions (sometimes we use a Graph to represent the state space)

goal test: way to determine whether a given state is a goal state (check statement we are trying to prove)

path cost: number of steps in proof

Theorem Proving: init state, actions, transition model, goal test, path cost function

Conversion To CNF (Conjuctive Normal Form)

disjunction: literals connected with $\lor$ conjunction: literals connected with $\land$

clause: a disjunction of literals

Conjuctive Normal Form: logical sentence that is a conjuction of clauses e.g. $(A \lor B \lor C) \land (D \lor \neg E) \land (F \lor G)$

Steps to Convert to CNF

• Eliminate biconditonals
  • turn $(\alpha \leftrightarrow \beta)$ into $(\alpha \rightarrow \beta) \land (\beta \rightarrow \alpha)$
• Eliminate implications
  • turn $(\alpha \rightarrow \beta)$ into $\neg \alpha \lor \beta$
• Move $\neg$ inwards using De Morgan’s Laws
  • e.g. turn $\neg(\alpha \land \beta)$ into $\neg \alpha \lor \neg \beta$
• Use distributive law to distribute $\lor$ wherever possible

First-Order Logic

Constant Symbols (Names, Objects, etc), Predicate Symbols (Classes) (Person, House, BelongsTo)

Universal Quantification: $\forall x$ Existential Quantification: $\exists x$ and so on of Quantifications

unconditional probability

degree of belief in a proposition in the absence of any other evidence.

conditional probability

degree of belief in a proposition given some evidence that has already been revealed

the probability of “a” given “b” $P(a|b)$

to know the probability of a given b, we take the probability of both and divide it by the probability of the second (b) to get rid of its own probability that happens when (a) doesn’t

random variable

a variable in probability theory with a domain of possible values it can take on can be encoded as an array to distribute the probabilities

Probability Distribution

$P(Flight = on time) = 0.6$

$P(Flight = delayed) = 0.3$

$P(Flight = cancelled) = 0.1$

or as a vector/array

$P(Flight) = <0.6, 0.3, 0.1>$

independence

the knowledge that one event occurs doesn’t affect the probability of the other event

then $P(b|a) = P(b)$ because (b) is independent of (a) anyways

dependence

the knowledge that one event occurs affects the probability of the other event

Bayes’ Rule

Note

$\because$ $P(a \land b) = P(b)P(a|b)$

$P(a \land b) = P(a)P(b|a)$

$\therefore$ $P(b)P(a|b) = P(a)P(b|a)$

$\therefore$

$P(b|a) = \frac{P(b) P(a | b)}{P(a)}$

knowing P(a | b) we can calculate P(b | a)

knowing P(visible effect | unknown cause) we can calculate P(unknown cause | visible effect)

knowing P(medical test result | disease) we can calculate P(disease | medical test result)

Probability Rules

Probability Models