More Test1 Review

Question 1

What are the 4 categories of AI?

Answer 1

• Thinking humanly
• Thinking rationally
• Acting humanly
• Acting rationally

Question 2

What is the definition of AI?

Answer 2

Intelligence demonstrated by machines, in contrast to natural intelligence displayed by humans/animals.

Question 3

What is “thinking humanly?”

Answer 3

Trying to make a computer program which mimics the human brain (cognitive modeling).

Question 4

What is “acting rationally?”

Answer 4

An rational agent which acts so as to achieve the best outcome or, whenever there is uncertainty, the best expected outcome. Also described as “doing the right thing.” (rational agent approach)

Question 5

What is “acting humanly?”

Answer 5

Mimicking human behavior. The Turing test is an example. It’s an “operational” definition of intelligence (blink reflex, Turing test).

Question 6

What is “thinking rationally?”

Answer 6

The attempt to build machines which are based on logical rules (syllogisms) that govern beliefs/behavior. (laws of thought).

Question 7

Machine learning.

Answer 7

The science of getting computers to act without being explicitly programmed.

Question 8

Nested hierarchy of AI, machine learning, representation learning, and deep learning.

Answer 8

Outermost to innermost: AI, machine learning, representation learning, deep learning.

Question 9

2 factors that deterred AI.

Answer 9

Lack of enough data & lack of sufficient computing power

Question 10

Definition of rationality.

Answer 10

Rational agents select an action that is expected to maximize its performance measure, given evidence provided by the percept sequence and built-in knowledge.

Question 11

PEAS

Answer 11

Performance, Environment, Actuator, Sensor.

Question 12

Performance (PEAS) definition

Answer 12

The performance measure that defines the criteria of success.

Question 13

Environment (PEAS) definition

Answer 13

The agent’s prior knowledge of the environment

Question 14

Actuator (PEAS) definition

Answer 14

The actions that the agent can perform

Question 15

Sensor (PEAS) definition

Answer 15

The agent’s percept sequence to date

Question 16

5 structures of intelligent agent

Answer 16

Simple reflex agents, model-based reflex agents, goal-based agents, utility-based agents, learning agents.

Question 17

Simple reflex agent definition.

Answer 17

Select actions on the basis of the current percept, ignoring the rest of the percept history.

Question 18

Model-based reflex agent definition.

Answer 18

The agent uses a “model” of the world to guide its actions. A model is knowledge about how the agent’s world works.

Question 19

Goal-based agent definition.

Answer 19

The agent has information about a goal it is supposed to achieve. It uses this goal and information about the results of possible actions in order to choose actions which achieve that goal.

Question 20

Utility-based agent definition.

Answer 20

Agent uses a utility function which maps a state or sequence of states onto a real number, which describes the associated degree of “happiness” from performing the action.

Question 21

Learning agent definition.

Answer 21

Starts with some basic knowledge and is then able to act and adapt autonomously, through learning, to improve its own performance.

Question 22

Goal vs utility

Answer 22

Goal: may seek to get from point A to point B, and succeeds when it gets there. Utility: get from point A to point B with additional specified criteria with trade-offs (shortest time, minimum fuel expenditure, etc).

Question 23

BFS completeness, time & space complexity, and optimality.

Answer 23

Time: b^(d+1)
Space: b^(d+1)
Complete? Yes (if b is finite)
Optimal? Yes if all steps have the same cost, but not optimal in general

Question 24

Uniform-cost search completeness, time & space complexity, and optimality.

Answer 24

Time: b^[C/e]
Space: b^[C/e]
Complete? Yes if step cost > e
Optimal? Yes

Question 25

DFS completeness, time & space complexity, and optimality.

Answer 25

Time: b^m
Space: bm
Complete? No
Optimal? No

Question 26

Depth-limited search completeness, time & space complexity, and optimality.

Answer 26

Time: b^l
Space: bl
Complete? Yes if l >= d
Optimal? No

Question 27

Iterative deepening DFS completeness, time & space complexity, and optimality.

Answer 27

Time: b^d
Space: bd
Complete? Yes
Optimal? Yes

Question 28

Bidirectional search time & space complexity

Answer 28

O((bd)/2)

Question 29

A* search completeness, time & space complexity, and optimality.

Answer 29

Time: n^2
Space: Keeps all nodes in memory
Complete? Yes unless there are infinitely many nodes
Optimal? Yes

Question 30

BFS uses a ____ and DFS uses a ____

Answer 30

Queue, stack

Question 31

Greedy search completeness, time & space complexity, and optimality.

Answer 31

Time: b^m
Space: b^m
Complete? No, but complete in finite space with repeated state checking.
Optimal? No

Question 32

A search problem consists of

Answer 32

Initial state, set of actions, goal test, path cost

Question 33

graph search vs tree search

Answer 33

graph search = infinite # of nodes without a circle. Tree search = finite nodes without a circle.

Question 34

Naive solution for TSP

Answer 34

Start & end at city 1, generate all (n-1)! permutations of cities, calculate the cost of every permutation & keep track of the minimum cost permutation, return the permutation with the minimum cost.