COM1005 COM2007 Machines and Intelligence (ACADEMIC YEAR 2016~17)

Question 1

Why write programmes?

Answer 1

Make ideas concrete, evaluate ideas, comparative against alternatives, results can be reproduced.

Question 2

Solving the general problem

Answer 2

Abstraction.

Question 3

State space

Answer 3

All legal problem states (a graph).

Question 4

Arcs

Answer 4

Connect states to each other.

Question 5

Expand function

Answer 5

Takes a state and returns all reachable states in 1 move.

Question 6

Operator

Answer 6

Express legal moves.

Question 7

Combinatorial explosion

Answer 7

Search tree grows rapidly with increasing depth.

Question 8

Calculating # of nodes

Answer 8

Branching factor * depth.

Question 9

Solution to many nodes to search pt1

Answer 9

Stop search before resource run out. Quality v. ease of finding solution.

Question 10

Solution to many nodes to search pt2

Answer 10

Do not include illegal moves in state space. More knowledge.

Question 11

Open nodes

Answer 11

Nodes awaiting development.

Question 12

Closed nodes

Answer 12

Nodes already developed.

Question 13

Does DFS have a solution?

Answer 13

Guaranteed but not admissible.

Question 14

Admissible

Answer 14

If it never overestimates the cost of reaching the goal.

Question 15

How does Depth-bounds search work?

Answer 15

Search completely to n. No solution, increase n.

Question 16

Beam search?

Answer 16

Expands from best (somehow ranked) nodes

Question 17

Branch and bound search?

Answer 17

Move has variable cost e.g map traversal. Min cost.

Question 18

Is Branch and Bound Search admissible?

Answer 18

Goal node from open must be min cost from start.

Question 19

Is Branch and Bound Search efficient?

Answer 19

No, it’s undirected. Explores useless routes not on solution path.

Question 20

Best first search

Answer 20

Nodes with smallest estRemCost. Closest to the goal.

Question 21

Best first search admissible?

Answer 21

Not admissible as bad estimates will ruin.

Question 22

A* algorithm

Answer 22

Mix between best first and branch and bound. Global cost + estRemCost.

Question 23

A* admissible?

Answer 23

Yes if estimates are all underestimates.

Question 24

Dynamic time warping

Answer 24

Spectrogram, energy through time and frequency for spoken words.

Question 25

Best scenario for DTW?

Answer 25

Small words and isolated speakers.

Question 26

Game tree?

Answer 26

Resulting exploration of state-space.

Question 27

Terminal nodes of game tree?

Answer 27

Final game state achieved e.g a win, draw, loss.

Question 28

Deduction

Answer 28

Creating new knowledge from old.

Question 29

Do facts have antecedents?

Answer 29

No

Question 30

Forward chaining from initial facts?

Answer 30

Generate facts from “stereotype” information.