Intelligent Systems Lecture Notes

4 November 2011 • Supervised Learning

---

Outline

A Problem

• Here are some numbers

  10 35 81 61 77 67 29 35 98 82 14

• What's the next number?
• You could guess.

  42. That's always a good number.

  But that leaves information on the table.

  How can you do better?

Do the Math

• If the numbers are truly random, guessing is the best you can do.
• If they're not random, what can you exploit to do better than guessing?
• They're numbers; do arithmetic on them.
  • mean: 53.5
  • median: 61
  • mode: 35

How'd You Do?

• Given a guess, how good is it?
• Measure the difference (the error) between your guess g and the numbers.

  		mean		median		mode
  \(\sum\) (vi - g)2		10442.5		11463		13229
  \(\sum\) |vi - g|		314.6		305		309
  max |vi - g|		46.6		50		64

Learning

• Learning improves behavior through experience.
  • Learning new behaviors.
  • Learn how to do old behaviors better.
    • Faster and more accurately.

Components

• A learning problem has the following parts:
  • The behavior being improved: the task.
    • Handwriting recognition.
  • The experiences from which learning draws on.
    • Handwriting samples.
  • Performance criteria.
    • Faster recognition, or greater accuracy, or recognize script.

The Learning Task

Learning Architecture

Representation Choice

• Rich representations are
  • more useful for problem solving
  • more difficult to set-up.

Learning Tasks

Supervised classification

Unsupervised learning

Reinforcement learning

Analytic learning

Inductive logic programming

Statistical relational learning

Classification Data Example

• 		Action		Author		Thread
  Training examples:
  e1		skips		known		new
  e2		reads		unknown		new
  e3		skips		unknown		old
  e4		skips		known		old
  e5		reads		known		new
  e6		skips		known		old
  New examples:
  e7		?		known		new
  e8		?		unknown		new

Feedback

• Learning tasks can be characterized by learner feedback:
  • Supervised learning: What has to be learned is specified for each example.
  • Unsupervised learning: No classifications, the learner discover categories and data regularities.
  • Reinforcement learning: Feedback occurs after an action sequence.

Measuring Success

• How well does the agent perform on new examples?
• Consider the agents
  • P claims negative examples are the only negative examples.
  • N claims the positive examples seen are the only positive examples.
• Both agents correctly classify every training example, but disagree on every other example.

Bias

• Bias prefers one hypothesis over another.
• Hypothesis ranking isn't done by the data.
• Bias allows a inductive process to make predictions.
• Useful biases are determined empirically.

Learning as Search

• Representation and bias reduce learning to search.
• Search through representations looking for a data good fit given the bias.
• Search-space size is usually huge, leading to incomplete searches.
• Learning involves a search space, an evaluation function, and a search method.

Noise

• Data isn't perfect: attributes may be given bad values, or there may not be enough of them.
• Overfitting discovers patterns in the training data that don't exist.
  • Due to data-set correlations.

Learning Characterizations

• Find the best representation for the given data.
• Find a class of representations consistent with the given data.
• Find probability distributions for representations given the data.

Supervised Learning

• Given
  • A set of input features I₁, …, I_n.
  • A set of target features T₁, …, T_n.
  • A set of training examples assigning input- and target-feature values.
  • a new example assigning input-feature values.
• predict target-feature values for the new examples.

Data-Representation Examples.

• A travel agent wants to predict the trip length, between 1 to 6 days (no input features).
• Represent the data two ways:
  • Random value T is the trip length.
  • Each indicator value Y_i is 1 if the trip length is i, 0 otherwise.

Data-Representation Examples..

Example T e1 1 e2 6 e3 6 e4 2 e5 1

Example T1 T2 T3 T4 T5 T6 e1 1 0 0 0 0 0 e2 0 0 0 0 0 1 e3 0 0 0 0 0 1 e4 0 1 0 0 0 0 e5 1 0 0 0 0 0

• What is a prediction?

Evaluating Prediction

• Suppose F is a feature and e is an example:
  • val(e, F) is the value of feature F in example e.
  • pval(e, F) is the predicted value of feature F in example e.
  • The prediction error is the difference between val() and pval().
  • There are many ways of finding the difference.

Error Measures.

• E is an example set; F is a target-feature set.
• The absolute error is

  

• The sum of squares error is

  

• The worst-case error is

  

• A cost-based error accounts for error costs.

Error Measures..

• When the target features are binary, use likelihood of the data

  

• Entropy

  

Information Theory

• A bit is a binary digit.
• A bit distinguishes two items.
• k bits can distinguish 2^k items.
• n items can be distinguished using log₂ n bits.
• Can you do better?

Information and Probability

• Design a code to distinguish elements of { a, b, c, d } with

  Pr(a) = 0.5, Pr(b) = 0.25, Pr(c) = Pr(d) = 0.125

• Consider the code:

  a 0, b 10, c 110, d 111

• The code sometimes uses 1 bit and sometimes uses 3 bits. On average, it uses

  Pr(a) + 2Pr(b) + 3Pr(c) + 3(d)
  = 1/2 + 2/4 + 3/8 + 3/8 = 1.75 bits

• The string aacabbda has code 00110010101110.

Information Content

• To identify x, you need - log₂ P(x) bits.
• Given a distribution over a set,

  

• is the distribution entropy.

Summary

References

• Learning in IS (Chapter 16) in Intelligent Systems by Robert Schalkoff, Jones and Bartlett, 2011.
• Learning from Examples (Chapter 18) in Artifical Intelligence, third edition, by Stuart Russell and Peter Norvig, Prentice Hall, 2010.

---

This page last modified on 2011 October 9.