Artificial Intelligence

Question 1

Branching factor

Answer 1

• Maximum number of successors of any node
• Denoted as b

Question 2

Depth of shallowest goal node

Answer 2

Denoted as d

Question 3

Maximum length of path

Answer 3

Denoted as m

Question 4

Breadth first search

Answer 4

• Expands shallowest node on the frontier
• Complete if d and b are finite
• Optimal only if path cost is a nondecreasing function of a node depth, for example, if all actions have identical cost
• Time complexity: O(b^d)
• Space complexity: O(b^d)

Question 5

Depth first search

Answer 5

• Expands deepest node on the frontier
• Complete if graph-search and finite state space. No if it’s used in a tree search.
• Not optimal
• Time complexity: O(b^m)
• Space complexity: O(bm)

Question 6

Iterative deepening search

Answer 6

• Run depth-first search to a fixed depth z
• Starting at z = 1, if the solution is not found then increment z and rerun the algorithm
• Time complexity: O(b^d)
• Space complexity: O(bd)
• Complete if state space is finite
• Optimal if step costs are all identical

Question 7

Uniform-cost search

Answer 7

• Expand node with lowest path cost
• Complete unless there is a path with an infinite sequence of zero-cost actions
• Optimal
• Time and space complexity: O(b^d) unless there are identical action costs, then it would be O (b^[1+ (C*/ϵ)]) with:
• C* = cost of the optimal solution
• ϵ = minimum action cost

Question 8

Minimax algorithm

Answer 8

• Complete if game tree is finite
• Optimal against an optimal opponent
• Time complexity: O(b^m)
• Space complexity: O(bm) or O(m)

Question 9

Pruning decision trees

Answer 9

• Avoids over fitting to training data
• Reduces test error
• Reduces complexity of the final classifier

Question 10

Greedy decision-tree learning

Answer 10

• Uses information gain to choose attributes to split on
• Does not prune
• Finds the decision tree that minimises error in the training data

Question 11

Admissible heuristic

Answer 11

• Never overestimates the cost to reach the goal
• For example, straight line distance
• If non-negative then 0 ≤ h(I) ≤ action cost

Question 12

Consistent heuristic

Answer 12

• Is also admissible
• h(n) <= c(n, a, nʹ) + h(nʹ)

Question 13

Constraint satisfaction problem

Answer 13

• X = {X₁,…,X_n} = set of variables
• D = {D₁,..,D_n} = set of domains specifying the values each variable can take
• C = set of constraints that specifies values that the variables are allowed to have collectively

Question 14

Q-learning

Answer 14

Formula to find new value: (γ p) + (α (r + (γ * p)))

• γ = discount factor
• p = previous value
• α = learning rate
• r = reward from previous turn

Given classes A and B:

• After transition A, perform action, B, the agent updates the Q value of state A
• After history A, perform action, B, the Q-value of state A changes

Question 15

Greedy best-first search

Answer 15

• Expands the node that appears to be closest to goal.
• Complexity: O(b^m) for both for tree search but a good heuristic can reduce it substantially
• Complete only when performing graph search in finite state set otherwise no (it can get into loops).

Question 16

A* search

Answer 16

• g(n) + h(n)
• g(n) = path cost from start node to node n
• h(n) = estimated cost of the cheapest path from n to goal state
• Complete
• Tree search version is optimal with an admissible heuristic
• Graph search version is optimal with a consistent heuristic.
• No other optimal algorithm is guaranteed to expand fewer nodes than A*
• Expands m nodes

Question 17

Markov Decision Process

Answer 17

• S = set of states
• A(s), s ∈ S = set of actions available from each state
• P(s’ | s,a) = transition model
• R(s, a, s’) = reward function

Question 18

Bellman’s Equation

Answer 18

s = state
a = action
s' = successor state

Question 19

Bellman Optimality Equation

Answer 19

Question 20

Value Iteration Update

Answer 20

Question 21

Deterministic policy in MDP

Answer 21

At a state, one action is selected with total probability 1.

Question 22

Interpretation in propositional logic

Answer 22

• Assignment of a truth value to each symbol (true/false)
• For example, for two symbols P and Q there would be 4 interpretations

Question 23

Meaning in propositional logic

Answer 23

• A set of interpretations

Question 24

Naive Bayes Classifier

Answer 24

• All features are conditionally independent of each other given their parent
• Features are mutually dependent of each other if they have the same parent

Question 25

Bayes net

Answer 25

• Each node is conditionally independent of its non descendants given its parents
• Each node is conditionally independent of all other nodes in the network given its Markov blanket
• A node is not independent of it’s descendants or ancestors

Question 26

Markov Blanket

Answer 26

• Parents, children and children’s parents of selected node
• Each node is independent of all other nodes outside the Markov blanket given it’s Markov blanket

Question 27

Perceptron network

Answer 27

• If a weighted linear combination is less than the threshold, then output is 0 and doesn’t fire, otherwise output is 1 and fired
• Can’t represent xor linearly

Question 28

Holdout cross-validation

Answer 28

• Split the training set in half
• Train classifier on one half and measure the error rate on another half
• Repeat on different splits

Question 29

K-fold cross-validation

Answer 29

• Divide the training set into k equal subsets
• Perform k rounds of learning
• In each round, train the classifier on k-1 subsets then test on the remaining subset
• Use the mean error rate across rounds

Question 30

Leave one out cross-validation

Answer 30

• Extreme version of k-fold cross validation, where k=n, and n is the number of instances in the training set