5 Learning

5.1 Learning from Examples/Observation

5.2 Knowledge in Learning
5.3 Learning Probabilistic Models
5.4 Neural Networks

Faizur Rashid (PhD)

1
 5.1. Learning

• An agent is learning if it improves its performance on future

tasks after making observations about the world.
• Learning can range from the trivial, as exhibited by jotting
down a phone number, to the profound, as exhibited by
Albert Einstein, who inferred a new theory of the universe.
• actually has vast applicability: from a collection of input–
output pairs, learn a function that predicts the output for new
inputs.
• This includes all kinds of informal and formal learning via any
combination of experience, education, and training.

2
 5.1. Learning

• Example
• what should students be learning about solving
problem?
• should they be learning to compete with computers or
work cooperatively with computers?
• Understanding of one's acquired knowledge and skills.
• Active use of one's acquired knowledge and skills.
(Transfer of learning).
• Ability to apply one's learning to new settings. Ability to
analyze and solve novel problems.)
3
 5.1. Learning
• Why would we want an agent to learn?
• If the design of the agent can be improved, why wouldn’t
the designers just program in that improvement to begin
with?
• There are three main reasons.
• First, the designers cannot anticipate all possible
situations that the agent might find itself in.
• For example, a robot designed to navigate mazes must
learn the layout of each new maze it encounters.
• Second, the designers cannot anticipate all changes over
time; a program designed to predict tomorrow’s stock
market prices must learn to adapt when conditions
change from boom to bust. 4
 5.1. Learning

• Third, sometimes human programmers have no idea how

to program a solution themselves.
• For example, most people are good at recognizing the
faces of family members, but even the best programmers
are unable to program a computer to accomplish that
task, except by using learning algorithms.

5
 5.2. Learning Examples
Form of Learning
• Any component of an agent can be improved by learning
from data.
• The improvements, and the techniques used to make them,
depend on four major factors:
• Which component is to be improved
• What prior knowledge the agent already has?
• What representation is used for the data and the
component?
• What feedback is available to learn from?

6
 5.2. Learning Examples
Components to be learned
The components of these agents include:
1. A direct mapping from conditions on the current state to
actions.
2. A means to infer relevant properties of the world from the
percept sequence.
3. Information about the way the world evolves and about the
results of possible actions the agent can take.
4. Utility information indicating the desirability of world states.
5. Action-value information indicating the desirability of actions.
6. Goals that describe classes of states whose achievement
maximizes the agent’s utility. 7
 5.2. Learning Examples
Components to be learned
• Each of these components can be learned. Consider, for
example, an agent training to become a taxi driver.
• Every time the instructor shouts “Brake!” the agent
might learn a condition– action rule for when to brake
(component 1);
• the agent also learns every time the instructor does not
shout. By seeing many camera images that it is told
contain buses, it can learn to recognize them (2).
• By trying actions and observing the results—for
example, braking hard on a wet road—it can learn the
effects of its actions (3).

8
 5.2. Learning Examples
Representation and prior knowledge
• Effective learning algorithms have been devised for all
of these representations.
• most of current machine learning research covers inputs
that form a factored representation
• a vector of attribute values and outputs that can be either
a continuous numerical value or a discrete value.
• There is another way to look at the various types of
learning:
• learning a (possibly incorrect) general function or rule
from specific input–output pairs is called inductive
learning.
9
 5.2. Learning Examples
Representation and prior knowledge
• analytical or deductive learning: going from a known general
rule to a new rule that is logically entailed, but is DEDUCTIVE
LEARNING useful because it allows more efficient
processing.
Feedback to learn from
• There are three types of feedback that determine the
three main types of learning:
UNSUPERVISED LEARNING
• In unsupervised learning the agent learns patterns in the
input even though no explicit feedback is supplied. The
most common unsupervised learning task is clustering:
10
 5.2. Learning Examples
Feedback to learn from
• detecting potentially useful clusters of input examples.
• For example, a taxi agent might gradually develop a
concept of “good traffic days” and “bad traffic days”
without ever being given labeled examples of each by a
teacher.
REINFORCEMENT LEARNING
• In reinforcement learning the agent learns from a series of
reinforcements rewards or punishments.
• For example, the lack of a tip at the end of the journey gives
the taxi agent an indication that it did something wrong.

11
 5.2. Learning Examples
REINFORCEMENT LEARNING
• The two points for a win at the end of a chess game tells the
agent it did something right. It is up to the agent to decide
which of the actions prior to the reinforcement were most
responsible for it
SUPERVISED LEARNING
• In supervised learning the agent observes some example
input–output pairs and learns a function that maps from input
to output.
• In component 1 above, the inputs are percepts and the
output are provided by a teacher who says “Brake!” or “Turn
left.”
• In component 2, the inputs are camera images and the 12
outputs again come from a teacher who says “that’s a bus.”
 5.2. Learning Examples
SUPERVISED LEARNING
• In Component 3, the theory of braking is a function from
states and braking actions to stopping distance in feet.
• In this case the output value is available directly from the
agent’s percepts (after the fact); the environment is the
teacher.
• The purpose of the supervised learning algorithm is to create
a prediction function using the training data that will
generalize for unseen training vectors to classify them
correctly.
• decision-tree learning is explored to construct a decision
tree from observed behavior.

13
 5.2. Learning Examples
SUPERVISED LEARNING
• Learning with Decision Trees
Example1
• One of the most intuitive and practical methods for
supervised learning is the decision tree. A decision tree is the
result of a classification process in which the source data is
reduced into a predictor tree that represents a set of
if/then/else rules.

14
 5.2. Learning Examples
SUPERVISED LEARNING
• Learning with Decision Trees

15
 5.2. Learning Examples
SUPERVISED LEARNING
• Learning with Decision Trees

• Conditional expression resulting from the simple decision tree.

• this player has three predictor variables.

• This condition expression (representing the decision tree)
defines that if the player has a gun with full ammo, it will fight.
• If the player has a knife and full health, it will fight.

16
 5.2. Learning Examples
SUPERVISED LEARNING
• Learning with Decision Trees
• Decision-tree learning is a common technique used in data
mining.
• Data mining is a larger field that studies the extraction of
useful information from data sets.
• Data mining is a popular technique in financial analysis and
also finds use in identifying fraud.

17
 5.2. Learning Examples
SUPERVISED LEARNING
• Expressiveness of Decision Trees
• if and only if the input attributes satisfy one of the paths
leading to a leaf with value true.
• Writing this out in propositional logic, we have

• Goal ⇔ (Path1 ∨ Path2 ∨···) ,

• For example, the majority function, which returns true if and
only if more than half of the inputs are true, requires an
exponentially large decision tree.

18
 5.2. Learning Examples
SUPERVISED LEARNING
• Expressiveness of Decision Trees
• Is there any kind of representation that is efficient for all kinds
of functions? Unfortunately, the answer is no.
• We can show this in a general way. Consider the set of all
Boolean functions on n attributes.
• How many different functions are in this set?
• This is just the number of different truth tables that we can
write down, because the function is defined by its truth table.
• A truth table over n attributes has 2n rows, one for each
combination of values of the attributes.
• Overall, decision tree help to classify and evaluate the idea.19
 5.2. Learning Examples
UnSUPERVISED LEARNING
• Unsupervised learning differs in that no target variable exists.
• All variables are treated as inputs, and therefore
unsupervised learning is used to find patterns in the data.
• This allows the data to be reduced and segmented into its
representative classes.
• Markov Models
• A Markov chain is a kind of probabilistic state machine that
can be easily trained given a set of training data.
• Each state can probabilistically lead to other states, but prior
states have no relevance to subsequent state transitions
(only the current state).
20
 5.2. Learning Examples
UnSUPERVISED LEARNING
• Markov Models
• What makes Markov chains interesting is that they can be
very easily created from observations.
• for example, the idea of the smart home. The home monitors
the actions of the occupant during the time that the occupant
is home.
• Every evening, the occupant sets the alarm for 6 am (Sunday
through Thursday).
• At 6 am, after the alarm sounds, the monitor notices that the
bathroom light is turned on.

21
 5.2. Learning Examples
UnSUPERVISED LEARNING
• Markov Models
• Through observation, we capture the following over a week’s
training:
• Weekday, 6 am alarm, bathroom-light-on
• Weekend, no alarm, bathroom-light-off
• With this data (five samples of weekday, two samples of
weekend), it’s visible that on weekdays, the alarm results in
the observation that the bathroom light comes on with a
probability of 1.0.
• With this data, the Smart Home could turn on the bathroom
light when it sees the precursor event of the alarm going off.
22
 5.2. Learning Examples
UnSUPERVISED LEARNING
• Markov Models
• This idea can be applied to a large variety of problems in the
domain of prediction, clustering and classification.
• There are various algorithms of clustering and classification.

23
 5.2. Learning Examples
SEMI-SUPERVISED LEARNING
• In semi-supervised learning we are given a few labeled
examples and must make what we can of a large collection of
unlabeled data.
• Even the labels themselves may not be the truths that we
hope for.
• Imagine that you are trying to build a system to guess a
person’s age from a photo.
• You gather some labeled examples by snapping pictures of
people and asking their age.

24
 5.2. Learning Examples
SEMI-SUPERVISED LEARNING
• That’s supervised learning. But in reality some of the people
lied about their age.
• It’s not just that there is random noise in the data; rather the
inaccuracies are systematic, and to uncover them is an
unsupervised learning problem involving images, self-
reported ages, and true
• Thus, both noise and lack of labels create a continuum
between supervised and unsupervised learning.

25
 5.3. Knowledge in Learning
Components to be learned
• Then, when it receives no tip from passengers who have
been thoroughly shaken up during the trip, it can learn a
useful component of its overall utility function.
Representation and prior knowledge
• We have seen several examples of representations for
agent components:
• propositional and first-order logical sentences for the
components in a logical agent;
• Bayesian networks for the inferential components of a
decision-theoretic agent, and so on.

26
 5.3. Knowledge in Learning
Representation and prior knowledge
• when a student is answering an essay test question, he is not
allowed to make use of reference books or a dictionary.
• I say “somewhat similarly” because chess tournaments are
governed by a careful set of rules
• the rules and the tournament are the “real world” of chess
competition.
• However, timed essay tests done without use of reference
materials are relatively far removed from the real world of
writing and making use of one’s knowledge.
• Game is different from writing or making knowledge.

27
 5.3. Knowledge in Learning
Representation and prior knowledge Example
• World Wide Web: A Global Library
• very large and rapidly growing database that we call the
World Wide Web (the Web).
• It can be thought of as a global library designed so that
millions of people can add to the contents of the library.
• It is a library designed for the use of people, by ICT systems,
and by a combination of people and ICT systems.
• Knowledge could be more readily accumulated, moved
around the world, and passed on to future generations.
• Libraries (databases) of data, information, knowledge,
and wisdom could be accumulated.
28
 5.3. Knowledge in Learning
Representation and prior knowledge Example
• World Wide Web: A Global Library
• most important idea in problem solving is building upon
the previous knowledge of yourself and others.
• library is an important component of both informal and
formal education systems.
• The school library has long been an important part of a
school.
• However, money, space, and staff considerably restrict
the size of a school library.
• The Web brings a new dimension to the library.
29
 5.3. Knowledge in Learning
Representation and prior knowledge Example
• World Wide Web: A Global Library
• Some keys to using the Web include:
• 1. learning to make use of search engines
• 2. learning to make relatively rapid and informed decisions on
which individual Websites to explore
• 3. learning to read (with understanding) interactive
hypermedia document.
• 4. learning to separate the “wheat from the chaff.” The Web
differs substantially from an ordinary hardcopy library in that
little of no screening occurs for much of what is published on
the Web.
30
 5.3. Knowledge in Learning
Representation and prior knowledge Example
• Search engines make use of both algorithms and
heuristics.
• Popular heauristic
• 8-Puzzle Heuristic
• Travelling Salesman Problem
• Hill Climbing

31