Artificial Intelligence

Question 1

What is a Search Problem?

Answer 1

The task of getting from an initial state to a specified goal state by means of executing a sequence of actions available to and chosen by the agent.

Question 2

Attributes of a Search Problem

Answer 2

State space, Initial state, Goal state, Actions (a function of current state), Transition model (a function of current state and performed action), Action cost function (optional).

Question 3

Define Uninformed Search

Answer 3

No prior information except that in the state space graph of the problem; solution based on the information in the state space only, including action costs.

Question 4

Define Informed Search

Answer 4

Algorithms that make use of a heuristic function ℎ.

Question 5

What is a heuristic ℎ?

Answer 5

An estimate of the lowest cost from the current state 𝒏 to the goal state. The estimate must be optimistic (not overestimate).

Question 6

BFS (Breadth-First Search) Properties

Answer 6

Complete: Yes, Optimal: Yes, Time Complexity: 𝑏^d, Space Complexity: 𝑏^d.

Question 7

DFS (Depth-First Search) Properties

Answer 7

Complete: Yes, Optimal: No, Time Complexity: 𝑏^m, Space Complexity: 𝑏*m.

Question 8

IDS (Iterative Deepening Search) Main Idea

Answer 8

Combining BFS and DFS by limiting the depth of search (limit l), exploring to the limit in a DFS manner, and then progressing to the next sequential limit + 1 if no goal state is found.

Question 9

IDS (Iterative Deepening Search) Properties

Answer 9

Complete: Yes, Optimal: Yes, Time Complexity: 𝑏^d, Space Complexity: 𝑏*d. Very memory efficient.

Question 10

UCS (Uniform-Cost Search) Main Idea

Answer 10

Utilises action costs to make decisions; the lowest g(n) node generated is chosen for expansion. Goal state tested upon node expansion.

Question 11

Why is UCS uninformed?

Answer 11

Action costs (e.g., road distances) are not directly indicative of which path brings one closer to the destination.

Question 12

Greedy (Best-First) Search Main Idea

Answer 12

Choosing the nodes with the lowest heuristic value ℎ(n), meaning closest to the goal state.

Question 13

Greedy Search Properties

Answer 13

Quick with a good heuristic function. Not optimal as it cannot backtrack after generating the goal state.

Question 14

A* Search Main Idea

Answer 14

Uses both the action costs accumulated in the path cost function g(n) and heuristic ℎ(n) (‘backward’ and ‘forward’ costs).

Question 15

When is A* search optimal?

Answer 15

If heuristic ℎ(n) is admissible.

Question 16

Define an admissible heuristic

Answer 16

A heuristic is admissible if it never overestimates the cost (e.g., straight-line distance).

Question 17

Define a consistent heuristic

Answer 17

A heuristic is consistent if it satisfies the triangle inequality. Every consistent heuristic is admissible.

Question 18

Characteristics of Local Search algorithms

Answer 18

Very memory efficient, not systematic (may leave parts of search space unexplored), highly initialisation dependent.

Question 19

When are Local Search algorithms useful?

Answer 19

For finding reasonable/good solutions in infinite search spaces, which are unsuitable for systematic search.

Question 20

Hill Climbing Algorithm

Answer 20

Initialise state randomly; consider all neighbours and choose the one with the highest objective function value; continue until no better neighbour found.

Question 21

Problems with Hill Climbing

Answer 21

Local maxima and plateaus. Solution: iterative (random-restart) hill climbing.

Question 22

What is a Constraint Satisfaction Problem (CSP)?

Answer 22

State representation is factored into a set of variables, each with its own domain.

Question 23

Components of a CSP

Answer 23

Variables {𝑋1, …, 𝑋𝑛}, Domains {𝐷1, …, 𝐷𝑛} specifying possible values for each variable, Constraints (C) rules that apply to variables and are used to update domains.

Question 24

Define a consistent assignment in CSP

Answer 24

If all constraints are satisfied.

Question 25

Define a complete assignment in CSP

Answer 25

If all variables are assigned.

Question 26

What is a solution to a CSP?

Answer 26

A complete and consistent assignment.

Question 27

Constraint Propagation in CSP

Answer 27

Eliminating parts of the search space through constraints, enforcing local consistency. Making a choice limits the domain (search space) of other variables.

Question 28

Backtracking Search for CSPs Main Idea

Answer 28

A recursive mechanism to handle 'dead end' scenarios (empty domains). Solution gradually developed by trying options at different tree levels.

Question 29

Local Search Paradigm for CSPs

Answer 29

Initialise an assignment of all variables randomly; address resulting constraint violations by adjusting one variable at a time.

Question 30

What is Machine Learning?

Answer 30

Builds a model (a simplified mathematical representation of a phenomenon). Learning is the process of training a model type using data.

Question 31

Types of machine learning based on feedback?

Answer 31

Supervised, Unsupervised, and Reinforcement learning.

Question 32

What is Supervised Learning?

Answer 32

Learning based on observation (𝑋) – label (𝑌) pairs. Output 𝑌 is known for training data.

Question 33

Classification vs. Regression

Answer 33

Classification: output 𝑌 takes a finite set of values (class labels). Regression: output 𝑌 can be any number on a continuous spectrum.

Question 34

Generative vs. Discriminative Models

Answer 34

Generative models explicitly model the distribution of classes and features (e.g., Naive Bayes). Discriminative models implicitly model the decision boundary.

Question 35

Parametric vs. Non-parametric Models

Answer 35

Parametric: model represented by a fixed number of parameters. Non-parametric: model represented by training samples (e.g., K-Nearest-Neighbour).

Question 36

What is Overfitting?

Answer 36

When a model has too much expressive ability (parameters) and models the training data too closely, including noise, causing it to not generalise well on unseen data.

Question 37

What is Generalisation?

Answer 37

The ability of the model to perform well on unseen data (test data) after training.

Question 38

What is the Bias-variance trade-off?

Answer 38

Tension between models that describe training data well (low bias, more complex) and models robust to change with data fluctuations (low variance, simpler).

Question 39

What is the Naïve Bayes Model?

Answer 39

A probabilistic model for classification. Properties: classification, generative, parametric.

Question 40

Key assumption of Naïve Bayes

Answer 40

Conditional independence of features (𝑋1, ..., 𝑋𝑛) given the class Y.

Question 41

Training Data Limitation in Naïve Bayes?

Answer 41

If training data lacks a sample of a certain class with a specific feature value, the conditional probability can be zero, affecting inference.

Question 42

What is Laplace smoothing?

Answer 42

A technique to address Naïve Bayes training data limitations by adding a constant (e.g., 1) to counts of feature values to avoid zero probabilities.

Question 43

What is a Decision Tree?

Answer 43

A representation of a function that solves Boolean classification problems. Can be learnt using a greedy (best-first) approach with the information-gain heuristic.

Question 44

How are Decision Trees learnt?

Answer 44

Using a greedy divide-and-conquer strategy, choosing the most discriminative attribute first to maximise separation of samples.

Question 45

Decision Tree limitations?

Answer 45

Can be prone to overfitting (techniques like pruning are used to mitigate).

Question 46

What is Entropy (Information Theory)?

Answer 46

Measure of uncertainty (in bits) of a variable. H(X) = − Σ P(xk)log2P(xk).

Question 47

What is Information Gain?

Answer 47

The reduction in entropy after splitting on an attribute. We want the attribute that reduces entropy the most.

Question 48

What is the Perceptron?

Answer 48

The simple unit of neural networks. It is a binary (two-class) linear classifier.

Question 49

What do Neural Networks approximate?

Answer 49

Universal approximators of arbitrary continuous functions.

Question 50

Adversarial Search characteristics?

Answer 50

2 competing players take turns, discreet states/moves, clear/quantifiable outcomes, zero-sum property, uses terminal test and utilities of game over states.

Question 51

What is a Utility Function (in games)?

Answer 51

A function that assigns values to final states of a game.

Question 52

What is Minimax?

Answer 52

An algorithm for 2-player, zero-sum games assuming one player minimizes utility and the other maximizes. Finds an optimal move at every position.

Question 53

What is Alpha-beta pruning?

Answer 53

An optimisation for Minimax that explores the game tree to give upper and lower bounds to the optimal score possible, allowing branches that are not worth exploring to be 'pruned'.

Question 54

Why use Evaluation Functions in games?

Answer 54

To give values to states without calculating the full minimax tree, used when minimax is not feasible.

Question 55

What is Propositional Logic?

Answer 55

Builds up sentences from atomic sentences using logical connectives.

Question 56

What is an Atomic Sentence?

Answer 56

Logically irreducible statements which can be either true or false.

Question 57

Logical Connectives in Propositional Logic

Answer 57

Unary: ¬ (not); Binary: ∧ (and), ∨ (or), → (implies), ↔ (if and only if).

Question 58

What is a Model (in Logic)?

Answer 58

A full assignment of truth values to atomic sentences.

Question 59

Define Entailment (α ⊨ β)

Answer 59

In every model in which α is true, β is also true.

Question 60

What is a Knowledge Base (KB)?

Answer 60

A set of sentences that summarizes the information known about the world.

Question 61

What is Model Checking?

Answer 61

An algorithm to determine if KB ⊨ α by checking all possible worlds where KB is true; if α is true in all of them, then KB ⊨ α.

Question 62

Model Checking properties

Answer 62

It is both sound and complete, but its complexity is exponential (2^n models for n atomic sentences).

Question 63

What is a Proof System?

Answer 63

A faster way than model checking using a set of inference rules to derive true sentences from a knowledge base.

Question 64

Define algorithm soundness

Answer 64

An algorithm i is sound if deriving α from KB (KB ⊢_i α) always means that KB ⊨ α.

Question 65

Define algorithm completeness

Answer 65

An algorithm i is complete if KB ⊨ α always means that KB ⊢_i α.

Question 66

What is Resolution (in Logic)?

Answer 66

A common proof system using a single inference rule. To prove α from KB, show no model exists where KB and ¬α both hold.

Question 67

Resolution properties (with CNF)

Answer 67

Sound and complete if all sentences are converted to Conjunctive Normal Form (CNF).

Question 68

Define a Sample Space (Probability)

Answer 68

The set of all possible outcomes for an experiment.

Question 69

Define an Event (Probability)

Answer 69

A subset of the sample space that we are interested in.

Question 70

Define Conditional Probability

Answer 70

The probability of one event happening given that another event has happened. P(A|B) = P(A ∩ B) / P(B).

Question 71

What is Bayes Theorem?

Answer 71

P(Y|X) = P(X|Y)P(Y) / P(X). Used to infer a cause (Y) from an effect (X).

Question 72

What is a Bayesian Network?

Answer 72

A graphical model that concisely displays relations of dependence, independence, and conditional independence between variables.

Question 73

What is the Markov Property?

Answer 73

A property of probabilistic systems indicating they are 'memoryless'; the transition probability to the next state depends only on the current state and action, not the history.

Question 74

What is a Markov Decision Process (MDP)?

Answer 74

A model defined using the Markov Property, consisting of a set of states, actions from each state, transition probabilities, and a reward for each transition.

Question 75

How are standard Search Problems related to MDPs?

Answer 75

Standard search problems can be thought of as a special case of MDPs where the transition probability to one specific next state is 1 for a given state and action.

Question 76

What is Discounted Return in MDPs?

Answer 76

A way to evaluate sequences of states and actions to maximise long-term reward, using a discount rate (gamma).

Question 77

What is Expected Value (Expectation)?

Answer 77

The average score or outcome likely to be achieved from a probabilistic experiment or random variable.

Question 78

Value Iteration Algorithm (Bellman)

Answer 78

An algorithm to calculate the optimal policy in an MDP by iteratively updating the value of each state based on the maximum expected value over all possible actions from that state.