Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Artificial Intelligence > Module 4 > Flashcards

Module 4 Flashcards

1
Q

What is a local search and it’s pros and cons

A

Operates by searching from start state to neighbouring states

Pros

  • Uses less memory
  • Can find reasonable solutions in large / infinite state spaces

Cons

  • does not keep track of paths or set of reached states
  • not systematic, may never explore a portion where solution exists
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Can local search solve optimization problem

A

Yes, where objective function is utilized

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is hill climbing

A

When aim is to find highest peak/ global maximum

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is gradient descent

A

When aim is to find lowest valley / global minimum

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Describe the hill climbing algorithm idea

A
  • Start wherever
  • move to neighbouring state
  • if no neighbour better than current state then quit
  • does not look beyond direct neighbours of current state
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Local search complexities

A

State space - set of complete configurations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is local maxima, ridge, shoulder and plateau

A

Local maxima - higher than neighbourhood , lower than global maxima

Ridge - sequence of local max , /\/\

Shoulder - flat neighbour’s then ascends

Plateau - No uphill or shoulder , flat

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How to increase hill climbing efficiency

A

Increase sideways moves

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are sideways moves

A

When reaching plateau, restart search from another point. Moves can be limited but is also more expensive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Variations of hill climbing

A

Stochastic - chose randomly among uphill neighbours

First-choice - generate random successors until one is better

Random restart - conducts a series of hill climbing searches

Evolutionary - stores potential solutions and performs random mutations. Keeps mutations that are better states ( ancestor of GA )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is simulated annealing

A

Minimizing algorithm Variation that Allows for bad moves according to temperature. Combines random walk with hill climbing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

When are bad/good moves allowed in simulated annealing

A

High temp - more bad moves

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How does simulated annealing expand

A

Change in energy
E > 0 - move to neighbour
E < 0 - move to neighbour with probability e ^ (-DE/T)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is local beam search

A

K copies of local search are initialized

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does each iteration of local beam search do

A

Generates all successors from k current states and chooses the best k to be current state - searches communicate with each other - evolution hc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is Genetic algorithm

A

Directed search algorithm based on biological evolution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are the components of GA

A
  • Encoding technique ( Gene / chromosome)
  • Initialization procedure ( creation )
  • Evaluation function ( environment )
  • Selection of parents ( reproduction )
  • Genetic operator ( mutation )
  • Parameter settings ( practice )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Flow chart of GA

A

Population initialization -> fitness function -> crossover -> Mutation -> Survivor selection -> terminate + return best

Loops fitness - survivor until termination condition reached

19
Q

What is a fitness calculation

A

Compromises of fitness function which takes solution candidate and measures the solution using fitness score

20
Q

What is a selection process

A

Selects individuals to be parents

Select individuals with probably proptional to fitness score or randomly where (n>p) and select p most fit parents

21
Q

What is GA crossover

A

Recombination procedure , combines different parts of parents to create offspring

  • one with 1P1 and 2P2
  • one with 2P1 and 1P2
22
Q

What is mutation rate

A

How often offspring have random mutations

Every bit in offspring composition is flipped with probability = mutation rate

23
Q

What is elitism

A

Make up of next generation

  • could be offspring or elite parents
  • guarantees overall fitness never decreases
24
Q

What is culling

A

Removing parents below certain thresholds

25
Q

What is a solution and evaluation function for games

A

Solution is strategy - evaluation function is evaluation goodness of game position.

26
Q

What are the environment type for games

A

Fully observable , Multi agent , sequential, discrete

27
Q

What is a game

A

Task env with more than 1 agent

28
Q

List game axes

A 
Determ or stochastic 
Fully observable 
Players
Teams/indiv
Turns/simul
Zero sum
29
Q

Which plan do algorithms help with in game search trees

A

Contingent plan / strategy

30
Q

List different types of games

A

Standard, zero sum, general sum , team

31
Q

List env types of standard games

A

Observable, deterministic, two player, turn taking, zero sum

32
Q

List formulation of standard game

A 
Initial state 
Players
Actions
Transition model  -Results(s,a)
Terminal test  , true when game over
Terminal value, utility for player
33
Q

What is the search objective of standard games

A

Find sequence of players decisions maximizing utility / pay off
Also considers opponent moves/utility

34
Q

List basic idea of zero sum games

A

Agents have opposite utilities , pure competition, one maximizes other minimizes

35
Q

List basic idea of general sum games

A

Agents have independent utilities. Here cooperation, indifference, competition, shifting alliance is possible.

36
Q

List basic idea of team games

A

Common pay off for players in a team

37
Q

Key feature of zero sum

A

Gain or loss is exactly balanced through opponents. Adds to 0

38
Q

How does minmax algorithm traverse and what does it assume

A

Back tracking algorithm with recursion using dfs

Assumes opponent will be rational and optimize, and all future moves are optimal

39
Q

What if minmax doesn’t not play optimally

A

Opponent benefits further

40
Q

What is minmax efficiency

A 
Search O(b^m) 
Space O(bm)
41
Q

What if more than one player / zero sum

A

Terminal nodes are tuples associated with tuple node. Each player maximizes their tuple.

42
Q

What is alpha beta

A

Modified version of mini max , cuts depth to half. Utilizes alpha beta as thresholds.

43
Q

Initial value of beta

A

Positive infinity , min changes

44
Q

Initial value of alpha

A

Negative infinity, max can change

Artificial Intelligence (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions