Ai

Front 1

Define simple reflex agent

Back 1

An agent which memorises all possible state action parings and can choose the best action for any given state with a simple look up table and no 'thinking'

Front 2

+ - simple reflex agent

Back 2

+ Very fast execution, no computation required

- Cannot adapt to new circumstances

- Can take up lots of memory, many scenarios have too man ypossible states.

Front 3

Define agent function/policy

Back 3

The mapping from observed states to action. f(si) -> aj

Front 4

Define fully observable state

Back 4

A state which provides all the information required to select an action.

Front 5

Define partially observable state

Back 5

A state which doesn't provide all the information required to select an action. You may need to know past states etc. I.e. a ball flying through the air. The state it is in at any one time is not enough to tell you where it will land, you need past states in order to calculate it.

Front 6

How do you calculate an action in a fully observable environment?

Back 6

f(Si) -> Aj

Front 7

How to calculate an action in a partially observable environment?

Back 7

f(S1, s2, s3, s4, s5....., Si) -> Aj

Front 8

What might make an environment partially observable?

Back 8

Inadequate sensing

Noisy sensing

Sensing or computing is too slow

Environment is too complex to model

Multiple agents

Front 9

Define deterministic environment

Back 9

The next state is completely determined by the current state

Front 10

Define stochastic environment

Back 10

The next state is not completely determined by the current state, from the point of view of the AI

Front 11

Define discrete environment

Back 11

An environment with a finite number of possible states (chess)

Front 12

Define continuous environment

Back 12

An environment with an infinite number of possible states (medical diagnosis)

Front 13

Define completeness

Back 13

An algorithm is complete if it is guaranteed to find the goal node (providing there is one)

Front 14

Define optimality

Back 14

An algorithm is optimal if it is guaranteed to fine the optimal solution. The optimal solution is the one with the lowest possible cost. Cost is dependent on the agents performance measure, i.e. not always the shortest path.

Front 15

Define time complexity

Back 15

The worst case length of time an algorithm will take to find a solution.

Front 16

Define space complexity

Back 16

The worst case amount of space an algorithm will use to find a solution.

Front 17

What does BFS use to store nodes to expand?

Back 17

A queue. Because queues are broad ||||||

Front 18

In BFS what do you expand?

Back 18

The first element of the queue. |||||| <---

Front 19

What path does BFS choose?

Back 19

The one with the least number of steps.

Front 20

Is BFS complete and or optimal

Back 20

It is complete. It will always find a solution.

It is not necessarily optimal, for example of each step costs a different amount. It will simply find the path with the shortest number of steps to the node, not necessarily the cheapest.

Front 21

What is the time and space complexity of BFS

Back 21

O(b^d) for both. All nodes and all edges need to be expanded in the worst case.

Front 22

What does DFS use to store nodes to expand?

Back 22

A stack. A stack is deep, not broad.

Front 23

Define branching factor

Back 23

The maximum number of edges on any one branch in the tree.

Front 24

Is DFS complete and or optimal

Back 24

It is generally not complete, it must explicitly not allow for repeated nodes or it will get stuck in a loop.

It is not optimal either, as it generally finds very long solution paths.

Front 25

What is the time and space complexity of DFS

Back 25

Time = O(b^m)

Space = O(bm)

m = max depth of the tree

Front 26

How does iterative deepening search work?

Back 26

It performs DFS but limits the depth to one. If the solution is not found it clears the whole tree and resets the limit to two. It repeats until the solution is found.

Front 27

When is IDDFS useful?

Back 27

When you think the goal node is not too deep but when the tree may be very deep.

Also if the branch factor is very high and you don't want to use up all the memory with breadth first search.

Front 28

What is the time and space complexity of IDDFS?

Back 28

Time = O(b^d)

Space = (d)

Front 29

How does UCS work?

Back 29

It is like BFS but with a priority queue. (you can add a node to the queue multiple times if you find a cheaper path)

The priority queue holds the currently expandable nodes and their distance cost total from the start.

At each point expand the cheapest node in the PQ which ensures optimality

Front 30

Is UCS complete and or optimal?

Back 30

It is complete unless the graph is infinite.

It is optimal because you always expand the cheapest node. So whenever a node is expanded we know we have found the cheapest possible path to that node.

Front 31

What is the time and space complexity of UCS?

Back 31

O(b^1+c*/e)

Essentially O(b^d)

c* is optimal cost

e is the cost of the cheapest action

+1 because you expand the goal node too.

Front 32

Define greedy search

Back 32

Greedy search prefers the node with the most short term gain without considering long term consequences.

Front 33

How does A* search work?

Back 33

It combines UCS with a heuristic. Heuristic = the cost of each node + a penalty for not going towards the goal node. f(p) = path cost(p) + heurustic (p)

which is the total estimated cost from the start to the goal = the actual cost from the start to node p + the estimated cost from p to the goal using the heuristic

Front 34

What makes a good heuristic

Back 34

One than doesn't overestimate the distance form the node to the goal = its admissible.

Also one that is efficiently compute-able so that it doesn't take up too much time or resources.

Front 35

Is A* optimal and efficient?

Back 35

A* is optimally efficient so long s the heuristic is admissible. It is complete and it is optimal.

Front 36

What is the time and space complexity of A*?

Back 36

The same as for UCS in the worst case where the heuristic is uninformative. O(b^c*/e+1)

Front 37

What is the time and space complexity of MinMax?

Back 37

time = O(b^m)

space = O(bm)

Front 38

How does MinMax work?

Back 38

You expand possible nodes and at each stage if its your move you choose the maximum posssible outcome and if its the opponents move you shooce the minimum possible option. So you evaluate the nodes and it will tell you which action to take that will minimise the opponents move. You assume they will always choose the action which benefits them the most.

Front 39

What is alpha beta pruning?

Back 39

Alpha beta pruning is used in conjunction with minmax to stop you having to explore nodes when you know the move will not be taken anyway. I.e. if you have already evaluated a node you can stop evaluating the next node as soon as it is worse for you than the previous node. This saves time and memory.

Front 40

What is the time and space complexity of alpha beta pruning?

Back 40

Worst case is still O(b^m) if none of the nodes can be pruned but in reality only 3% of the nodes need evaluation. O(b^3m/4)

Front 41

Outline expectminmax

Back 41

This is for cases which need to include probability such as dice rolls.

Front 42

What is the time complexity of expectminmax

Back 42

O(b^m n^m) where n = distinct outcomes of chance.

Front 43

When is monte carlo tree search applicable?

Back 43

When the complexity of games is too great to apply other algorithms, i.e Go where there are far too many permutations to applyalgorithms which work out the best possible move.

Front 44

What are the 4 steps in monte carlo tree search

Back 44

1 SELECTION: select the node you wish to expand using minmax to a certain depth with alpha beta pruning if possible

2: EXPANSION: select a new child node for expansion.

3: SIMULATION: Simulate a game from that child with random moves.

4: BACK PROPAGATION: Update the root with the result of the random playout.

Front 45

What are the three benefits of MCTS? AAA

Back 45

AHEURISTIC: No prior knowledge of the game required

ASYMMETRIC: Focuses on searching the most promising parts of the tree/is good for trees with a large branching factor.

ANYTIME: It can be stopped at any time and return the current best estimate = flexible.

Front 46

What are the three types of machine learning?

Back 46

Supervised = using labelled data

Unsupervised = using unlabelled data and looks for patterns

Reinforcement learning = an agents action are rewarded/punished, must learn to maximise reward.

Front 47

What are you trying to determine with training data?

Back 47

To determine the function which maps input data to a label. You are trying to use the machine to find out a function f(x).

Front 48

Define bias

Back 48

error from modelling assumptions

Front 49

Define variance

Back 49

Error from sensitivity to small fluctuations in training data

Front 50

Define interpolation

Back 50

find a point of data WITHIN a given data set range ----x----

Front 51

Define extrapolation

Back 51

look at a data set and predict a value outside of it ---- x

= risky

Front 52

Define overfitting

Back 52

When you are too sensetive to noise when trying to find a curve in a data set

Front 53

Define exploration

Back 53

Trying to look for new things beyond what you know = risky but could be high reward

Front 54

Define exploitation

Back 54

Exploiting what you currently know to continue reaping reward = safe but may not be as high reward as exploration

Front 55

What can a neural net with one hidden layer represent?

Back 55

Any continuous function

Front 56

What can a neural net with two hidden layers represent

Back 56

Any function

Front 57

Whats the number of neuron tradeoff?

Back 57

The more neurons you have the more complex the function you can represent, yet the risk of overfitting increases.

Front 58

What can cause uncertainty?

Back 58

Sensors, actuators or the environment may be noisy.

Front 59

When would an agent treat an environment as stochastic?

Back 59

If it is partially observable it may be beneficial to create a belief state and choose the action with the highest expected utility.