ITRI 616 – Artificial Intelligence
Notes in preparation for the 2014 examination. The subject material is based on:
AI - Russell, S. & Norvig, P. 2014. Artificial intelligence: a modern approach. 3rd ed. Pearson
education limited: Essex.
NDD - Hagan, M. T., Demuth, H. B. & Beale, M. H. 1996. Neural network design. Boston: Pws Pub.
Table of Contents
1. Introduction to artificial intelligence (AI Chapter 1) 2
2. Intelligent Agents (AI Chapter 2) 3
3. Solving problems by searching (AI Chapter 3) 7
4. Introduction to neural network design (NDD Chapter 1) 12
5. Network architectures (NDD Chapter 2) 12
6. An illustrative example (NDD Chapter 3) 16
7. Examination 2012 17
8. Examination 2013 25
,Stuvia.co.za GeekyS
1. Introduction to artificial intelligence (AI Chapter 1)
The field of Artificial Intelligence (AI) attempts to understand and build intelligent entities.
Categories of AI definitions
Systems that think Systems that think
Rationality
as metric
as metric
Humans
like humans rationally
Systems that act like Systems that act
humans rationally
(a) Systems that think humanly. We need to get inside the actual workings of human minds.
There are two ways to do this: through introspection – trying to catch our own thoughts as
they go by – and through psychological experiments. Once we have a sufficiently precise
theory of the mind, it becomes possible to express the theory as a computer program.
(b) Systems that think rationally. The Greek philosopher Aristotle was one of the first to attempt
to codify “right thinking,” that is, irrefutable reasoning processes. His syllogisms provided
patterns for argument structures that always yielded correct conclusions when given correct
premises. These laws of thought were supposed to govern the operation of the mind; their
study initiated the field called logic.
(c) Systems that act humanly. The Turing Test, proposed by Alan Turing (1950), was designed to
provide a satisfactory operational definition of intelligence. Rather than proposing a long and
perhaps controversial list of qualifications required for intelligence, he suggested a test based
on indistinguishability from undeniably intelligent entities – human beings. The computer
passes the test if a human interrogator, after posing some written questions, cannot tell
whether the written responses came from a person or not.
(d) Systems that act rationally. An agent is something that acts. But computer agents are
expected to have other attributes that distinguish them from mere “programs,” such as
operating under autonomous control, perceiving their environment, persisting over a
prolonged time period, adapting to change, and being capable of taking on another’s goals. A
rational agent is one that acts so as to achieve the best outcome or, when there is
uncertainty, the best expected outcome.
AI definitions per category
“The exciting new effort to make computers “The study of mental faculties, through the use of
think… machines with minds, in the full and literal computational models.”
sense.”
“The study of the computations that make it
“[The automation of] activities that we associate possible to perceive, reason, and act.”
with human thinking, activities such as decision-
making, problem solving, learning…”
“The art of creating machines which perform “Computational Intelligence is the study of the
functions that requires intelligence when design of intelligent agents.”
performed by people.”
“AI … is concerned with intelligent behaviour in
The study how to make computers do things at artifacts.”
which, at the moment, people are better.”
2
,Stuvia.co.za GeekyS
History of AI: The birth (1956):
Princeton was home to another influential figure in AI, John McCarthy. After graduation, McCarthy
moved to Dartmouth College, which was to become the official birthplace of the field. McCarthy
convinced Minsky, Claude Shannon, and Nathaniel Rochester to help him bring together U.S.
researchers interested in automata theory, neural nets, and the study of intelligence. They organized
a two-month workshop at Dartmouth in the summer of 1956. There were 10 attendees in all, including
Trenchard More from Princeton, Arthur Samuel from IBM, and Ray Solomonoff and Oliver Selfridge
from MIT. Two researchers from Carnegie Tech,13 Allen Newell and Herbert Simon, rather stole the
show. Although the others had ideas and in some cases programs for particular applications such as
checkers, Newel1 and Simon already had a reasoning program, the Logic Theorist (LT), about which
Simon claimed, "We have invented a computer program capable of thinking non-numerically, and
thereby solved the venerable mind-body problem."14 Soon after the workshop, the program was able
to prove most of the theorems in Chapter 2 of Russell and Whitehead's Principia Mathernatica.
Russell was reportedly delighted when Simon showed him that the program had come up with a proof
for one theorem that was shorter than the one in Principia. The editors of the Journal of Symbolic
Logic were less impressed; they rejected a paper coauthored by Newell, Simon, and Logic Theorist.
Discuss the early enthusiasm and great expectations period of Artificial Intelligence (1952-1969):
The early years of AI were full of successes-in a limited way. Given the primitive computers and
programming tools of the time, and the fact that only a few years earlier computers were seen as
things that could do arithmetic and no more, it was astonishing whenever a computer did anything
remotely clever. The intellectual establishment, by and large, preferred to believe that "a machine can
never do X." AI researchers naturally responded by demonstrating one X after another. John
McCarthy referred to this period as the "Look, Ma, no hands!" era.
Applications (sub-fields) of AI: Machine translation, Speech recognition, Spam filtering, Robotics &
Game playing.
2. Intelligent Agents (AI Chapter 2)
An agent: An agent is anything that can be viewed as perceiving its environment through sensors and
acting upon that environment through actuators.
Percept: A percept refers to the agent’s perceptual inputs at any given instant.
Percept sequence: is the complete history of everything the agent has ever perceived. In general an
agent’s choice of action at any given instant can depend on the entire percept sequence observed to
date.
Agent function: An agent function maps any given percept sequence to an action.
Agent program: Internally, the agent function for an artificial agent will be implemented by an agent
program.
Tasks an agent must perform: Measure success, describe environment, sense/perceive (using
sensors), act (through actuators).
Rationality depends on:
Performance measure which defines the criterion of success.
Agent’s prior knowledge of the environment.
Actions that the agent can perform.
The agent’s percept sequence to date.
3
,Stuvia.co.za GeekyS
Definition of a Rational Agent: For each possible percept sequence, a rational agent should select an
action that is expected to maximize its performance measure, given the evidence provided by the
percept sequence and whatever built-in knowledge the agent has. (An Omniscient agent: knows the
actual outcome of its actions and can act accordingly)
Properties of Task Environments
Fully observable: if the sensors detect all Partially observable: only some aspects are
aspects that are relevant to the choice of detected.
action.
Unobservable: An agent has no sensors at all.
Single agent: only one agent active in the Multi-agent: more than one agent active in the
environment, ex. program solving crossword environment, ex two programs playing chess
puzzle. against each other.
Competitive: By maximising the performance Cooperative: agents work together to
of one agent the performance of an opposing maximise performance.
agent is minimised.
Deterministic: The next state of the Stochastic: Non deterministic environment.
environment is fully determined by the current
Nondeterministic: one in which actions are
state and the action performed by the agent.
characterised by their possible outcomes but
Strategic: an environment which is no probabilities are attached to them.
deterministic except for the actions of other
Uncertain: environment which is not fully
agents.
observable or not deterministic.
Episodic: agent’s experience is divided into Sequential: The current decision affects all
atomic episodes. In each episode an agent future decisions.
receives a percept and then performs a single
action. The next episode does not depend on
the actions taken in the previous one.
Static: no changes in the environment over Dynamic: the environment can change while
time. the agent is deliberating.
Semi-dynamic: The environment does not
change over time but the agent’s performance
score does.
Discrete: Applies to the state of the Continuous: Events are continuous.
environment and the way time is handled;
distinct states exists.
Known: Refers to the agent’s state of Unknown: Agents will have to learn
knowledge about the laws of physics of the environment, outcomes of actions are not
environment. All possible outcomes for all known.
possible actions are known.
4
,Stuvia.co.za GeekyS
Structure of agents: Agent = Architecture + Program
Types of agent programs:
Table-drive agent program:
A rather trivial agent program keeps track of the percept sequence and then uses it to index into a
table of actions to decide what to do. The table represents explicitly the agent function that the agent
program embodies. To build a rational agent in this way, we as designers must construct a table that
contains the appropriate action for every possible percept sequence. It is instructive to consider why
the table-driven approach to agent construction is doomed to failure.
(a) no physical agent in this universe will have the space to store the table,
(b) the designer would not have time to create the table,
(c) no agent could ever learn all the right table entries from its experience, and
(d) even if the environment is simple enough to yield a feasible table size, the designer still has no
guidance about how to fill in the table entries.
Despite all this, the TABLE-DRIVEN-AGENT does do what we want: it implements the desired agent
function. The key challenge for AI is to find out how to write programs that, to the extent possible,
produce rational behaviour from a smallish program rather than from a vast table.
Simple reflex agent:
Actions based on current precepts.
Simple with limited intelligence
Infinite loop occur frequently (can use randomised actions).
Model-based reflex agents:
Handles partial observability by keeping track of the world which is not observable.
Maintains an internal state that depends on the precept sequence.
Updates the internal state with knowledge of: how the world develops independent of the
agent and how the agent’s actions influence the world.
Goal-based agents:
Knowing something about the current state of the environment is not always enough to decide what to
do. For example at a road junction, the taxi can turn left, turn right, or go straight on. The correct
decision depends on where the taxi is trying to get to. In other words, as well as a current state
description, the agent needs some sort of goal information that describes situations that are
desirable—for example, being at the passenger's destination. The agent program can combine this
with the model (the same information as was used in the model-based reflex agent) to choose actions
that achieve the goal. The picture below shows the goal-based agent's structure. Sometimes goal-
based action selection is straightforward—for example, when goal satisfaction results immediately
from a single action. Sometimes it will be trickier; for example, when the agent has to consider long
5
,Stuvia.co.za GeekyS
sequences of twists and turns in order to find a way to achieve the goal. Search and planning are the
subfields of Al devoted to finding action sequences that achieve the agent's goals.
Utility-based agents:
Goals are not enough to generate high-quality behaviour is most environments; use utility.
Utility function is an internalisation of the performance measure.
If utility function and external performance measure are in agreement; rational actions are
chosen.
Learning agents:
Start operating initially in unknown environment and gets more competent.
Example: Give the Performance, Environment, Actuators and Sensors (PEAS) description of the task
environment of a taxi driver agent for an automated taxi for a metropolitan city.
Explain why you would not use a Simple Reflex agent to implement the taxi agent: Simple reflex
agents need a fully observable environment, or else it will go into an infinite loop.
6
,Stuvia.co.za GeekyS
3. Solving problems by searching (AI Chapter 3)
A problem can be defined formally by five components:
(a) The initial state that the agent starts in. For example, the initial state for our agent in Romania
might be described as In(Arad).
(b) A description of the possible actions available to the agent. The most common formulation
uses a successor function. Given a particular state x, SUCCESSOR-FN(x) returns a set of
<action, successor> ordered pairs, where each action is one of the legal actions in state x and
each successor is a state that can be reached from x by applying the action. Together, the
initial state and successor function implicitly define the state space of the graph in which the
nodes are states and the arcs between nodes are actions.
(c) A description of what each action does; the formal name for this is the transition model,
specified by a function RESULTS(s, a) that returns the state that results from doing action a in
state s. We also use the term successor to refer to any state reachable from a given state by
a single action.
(d) The goal test, which determines whether a given state is a goal state. Sometimes there is an
explicit set of possible goal states, and the test simply checks whether the given state is one
of them. Sometimes the goal is specified by an abstract property rather than an explicitly
enumerated set of states.
(e) A path cost function that assigns a numeric cost to each path. The problem-solving agent
chooses a cost function that reflects its own performance measure.
Measuring problem-solving performance:
Completeness: Is the algorithm guaranteed to find a solution when there is one?
Optimality: Does the strategy find the optimal solution? (Does it find the best/shortest solution)
Time complexity: How long does it take to find a solution? (Number of nodes generated
during search)
Space complexity: How much memory is needed to perform the search? (Maximum number
of nodes stored in memory)
Complexity (time & space) is measured by:
Branching factor (b): maximum number of successors of any node.
The depth of the shallowest goal node (d).
The maximum length of any path in the state space (m).
Uninformed search strategies:
1. Breadth-first
2. Depth-first
3. Depth-limited
4. Iterative deepening depth-first
5. Bidirectional
[S] = start [G] = goal
7
, Stuvia.co.za GeekyS
1. Breadth-first
Goal test is done when node is generated. Nodes already contained in open list is not added
again.
1.1 [Visit]=S [Open]={A,D} [Closed]={}
1.2 [Visit]=A [Open]={D,B} [Closed]={S}
1.3 [Visit]=D [Open]={B,E} [Closed]={S,A}
1.4 [Visit]=B [Open]={E,C} [Closed]={S,A,D}
1.5 [Visit]=E [Open]={C,F} [Closed]={S,A,D,B}
1.6 [Visit]=C [Open]={F} [Closed]={S,A,D,B,E}
1.7 [Visit]=F [Open]={G} [Closed]={S,A,D,B,E,C}
Goal state reached path = {S, D, E, F}.
2. Depth-first
2.1 [Visit]=S [Open]={A,D} [Closed]={}
2.2 [Visit]=A [Open]={B,D} [Closed]={S}
2.3 [Visit]=B [Open]={C,D} [Closed]={S,A}
2.4 [Visit]=C [Open]={D} [Closed]={S,A,B}
2.5 [Visit]=D [Open]={E} [Closed]={S,A,B,C}
2.6 [Visit]=E [Open]={F} [Closed]={S,A,B,C,D}
2.7 [Visit]=F [Open]={G} [Closed]={S,A,B,C,D,E}
Goal state reached path = {S, D, E, F}.
3. Depth-limited
l = 2.
3.1 [Visit]=S [Open]={A,D} [Closed]={}
3.2 [Visit]=A [Open]={B,D} [Closed]={S}
3.3 [Visit]=B [Open]={D} [Closed]={S,A} l = 2 reached
3.4 [Visit]=D [Open]={E} [Closed]={S,A,B}
3.5 [Visit]=E [Open]={} [Closed]={S,A,B,D} l = 2 reached
Goal state not reached.
8
