Machine Learning I - Content

1. What is Machine Learning?
2. Types of Learning
3. Design of a Learning System
4. Concept Learning
5. Version Space
6. Applications

ML - Introduction

• Predicting the future
  • How much will you like a movie that you haven’t seen?
    • We base on other movies you have seen
    • Informed predictions
  • What does learning mean?
    • How do we determine success or failure of the task?

ML - Introduction

• Predicting the future
  • Example
    • When we learn in a course
    • We evaluate learning with a test
    • How should we design the test questions?
      • Should correspond to the topics covered in class
      • Only exercises seen in class?
      • Actually, new questions but related to the topics seen in class
  • GENERALIZATION

ML - Generalization

• One of the most important concepts in Machine Learning
  • Learning, not memorizing
    • Memorizing: We can only answer what we were thought (equally) but not related problems
    • Learning: Allows solving problems related to those we have previously learned, not necessarily the same

ML - Learning Definitions

• “acquiring knowledge or understanding or skill by means of study, instruction or experience”
• “change of a tendency in behavior through experience”
• Learning in Machines
  • Parallel lines between learning in machines and animals
  • Learning techniques based in animal and human learning models

ML - Learning Definitions

• A point of view
  • “… a machine learns when it changes its structure, program or data (based in the inputs or output to external information) in such a way that its expected future precision increases” (Nilson)
• Usually in tasks related to Artificial Intelligence
  • Recognition, Diagnosis, Planning, Robot control, Prediction
• Changes can be
  • Enhancements in known activities
  • Learning new tasks

ML - Learning Definitions

ML - Why should machines learn?

• Some tasks can only be defined through examples
  • We can specify inputs & outpus
  • Can’t specify concise relations between those inputs & outputs
  • Machines adjust their internal structure to produce the right output
    • A large number of samples \(\rightarrow\) function that approximates the implicit relation in the examples
• Extract important relations and correlations from data
  • Data Mining

ML - Why should machines learn?

• For applications in which:
  • We don’t know all the environment characteristics
    • At design time
    • Use of ML to enhance existing applications
  • Ammount of available knowledge too large
    • To be coded by humans
    • Machines learn this knowledge
  • Environments change through time
    • Machines adapt to these changes in the environment
    • Reduce need for constant re-design
  • New knowledge about tasks is constantly discovered
    • Implies redesign of AI systems, impractical
    • ML deals with this new knowledge

ML - Areas involved in ML

• Statistics
  • Use of samples taken with unknown probability distributions
  • From which probability distribution did we take this sample?
  • How can we estimate the value of an unknown function in a new point given the values of that function for a set of sample points?

ML - Areas involved in ML

• Brain Models
  • Model the way in which the human brain works
  • This work is also known as
    • Connectionism
    • Brain-style computation
    • Sub-symbolic processing
  • Neural networks

ML - Areas involved in ML

• Adaptive control theory
  • Study the problem of processes control with unknown parameters that are estimated on the process
  • Parameters may chance during the process
  • Instances of: control a robot based on sensor inputs

ML - Areas involved in ML

• Phycological Models
  • Study the effectiveness of humans in several learning tasks
  • Phycological studies inspired
    • Decision trees
    • Semantic networks
  • Stimuli-reward experiments to influence behavior for goal finding in animals inspired
    • Reinforcement learning

ML - Areas involved in ML

• Artificial Intelligence
  • Program learns parameters of a function to evaluate board in checkers
    • Samuel, 1959
  • Learning analogies
    • Carbonell, 1983
  • How actions and future decisions can be based on previous example cases
    • Kolodner, 1993
  • Rule discovery for expert systems using decision trees
    • Quinlan, 1990
  • Inductive logic programming
    • Muggleton, 1991
    • Lavrac & Dzeroski, 1994
  • Problem solving using explanation based learning
    • DeJong & Mooney, 1986
    • Laird et al., 1986
    • Minton, 1988
    • Etzioni, 1993

ML - Areas involved in ML

• Evolutive Models
  • Model biological evolution
  • Proposed as learning methods to enhance the efficiency of computer programs
  • Genetic algorithms
    • Holland, 1975
  • Genetic programming
    • Koza, 1992, 1994

ML - Varieties of ML

• Different computational structures
  • Functions
  • Logic programs and sets of rules
  • Finite state machine
  • Grammars
  • Problem resolution problems

ML - Types of Learning

• Supervised
• Unsupervised

ML - Tasks

• Associations
• Classification
• Clustering
• Regression
• Reinforcement learning
• Summarization
• Outliers detection

ML - Steps to design of a ML system

1. Data collection
   • Depends on the domain
   • What type of data?
   • From a database?
   • Select a sub-set of data?
   • Too much data?
   • Small amount of data?
     • Sampling?

ML - Steps to design of a ML system

2. Prepare the input data
   • Data cleaning
   • Format data for specific algorithm
     • Table
     • Logical predicates
     • Graphs

ML - Steps to design of a ML system

3. Analyze the input data (preview)
   • Missing values
   • Identify noise
   • Identify outliers

ML - Steps to design of a ML system

4. Training an algorithm
   • Which algorithm?
   • Would this be the best algorithm for the task?
   • Try only one algorithm or more?

ML - Steps to design of a ML system

5. Evaluate the algorithm
   • How do we evaluate?
   • 10-FCV
   • Confusion matriz
   • Which metrics should we use?
     • Accuracy
     • Precision / recall
     • F-Measure
     • ROC or AUC

ML - Steps to design of a ML system

6. Use the algorithm or model

Inductive Learning (IL)- DEFINITION

• We say that a computational program LEARNS from EXPERIENCE E with respect to a class of TASKS T and PRECISION P, if its precision with respect to task T, and measure P, improves with experience E. (Tom Mitchell)

• Think again about the Design of a learning system

IL - Concept Learning

• Infer a function with boolean values from training examples of its input and output
• We learn symbolic models of the concepts

IL - Notation

• Domain: The theme of our data (i.e. stars and galaxies, leukemia cells, radiographies, other)
• Attributes: Characteristics of the domain that we use to describe it (i.e. color, size, etc.)
• Class: The characteristic that tells us how to classify an specific example (i.e. whether it is a star or a galaxy)
• Hypothesis: A possible model tha we could use to classify/predict (only a proposal that we will evaluate)
• Hypothesis language: The language used to describe the domain. Can be a table format, decision trees, classification rules, logic predicates, graphs, etc.

IL - Notation

• Objective Concept: The concept that we learn (i.e. Star, Enjoy-sport)
• Examples: An example is an attributes-class pair (\(x\), \(f(x)\)). \(x\) is the input (usually a vector of attribute-values) and \(f(x)\) is the output (or assigned class).
• Inference Process (Induction): Given a collection of examples of \(f\), return a function \(h\) (hypothesis) such that \(h\) approximates \(f\).
• Hypothesis Space: The set of possibilities to choose \(h\) from.
• Bias: Any preference for choosing a hypothesis.

IL - The Problem of Inductive Learning

• Five elements to specify to characterize the inductive inference problem (Angluin & Smith)
  • Class of rules
  • Hypothesis space
  • Set of examples and its presentation
  • Class of inference method
  • Success criterion

IL - The Problem of Inductive Learning

• Class of rules
  • The class of functions or language under consideration
    • i.e. all regular expressions over an specific alphabet
    • Context free languages
    • Recursively ennumerated functions
    • Prolog programs
    • etc.

IL - The Problem of Inductive Learning

• Hypothesis space
  • We assume that the language described by the hypothesis space (hypothesis language) is the same of the class of rules
  • Hypothesis language: Syntax used for hypothesis construction
  • Hypothesis space: Set of all possible hypotheses for the hypothesis language

IL - The Problem of Inductive Learning

• Hypothesis space
  • Hypothesis language determines the hypothesis space
  • Inference method selects rules from the hypothesis space
  • Language imposes restrictions or preferences
    • About what can be learnt
    • About the reasoning strategies allowed
  • Hypothesis language \(\rightarrow\) depends on the application
  • Language selection \(\rightarrow\) CONSIDER:
    • What we want the system to do?
    • What information will we provide to the system (input)?
      • To try to solve the problem
      • Will the problem be solved on time?
  • Balance between Expressiveness and Efficiency

Machine Learning as a Search Problem

• Systematically search the hypothesis space (strategy)
  • Find the right hypothesis

ML Example (Tom Mitchell 1997)

ML Example (Tom Mitchell 1997)

• Representation
  • Each hypothesis consists on a conjunction of restrictions about the attributes of the instances
  • Vector with 6 restrictions - specify the values of the 6 attributes
  • Possible values
    • ? \(\rightarrow\) any value is acceptable for this attribute
    • \(\emptyset \rightarrow\) no value is acceptable
    • \(warm\) or other \(\rightarrow\) especifies a unique value for the attribute
  • If an instance \(x\) satisfies the restrictions of hypothesis \(h\), then \(h\) classifies \(x\) as a positive example
    • \(h(x) = 1\)
    • \(\{?, Cold, High, ?, ?, ?\}\)

ML - Notation

• Notation
  • Most general hypothesis: \(\{?, ?, ?, ?, ?, ?\}\)
  • Most specific hypothesis: \(\{\emptyset, \emptyset, \emptyset, \emptyset, \emptyset, \emptyset\}\)

ML - Learning Algorithm

• Learning algorithm
  • What should the learning algorithm do for the “Enjoy-Sport” domain?

ML - Learning Algorithm

• Learning algorithm
  • Input: Experience in the form of examples with a class assigned
  • Algorithm: Find a hypothesis that generalizes the knowledge
  • Output: A model to classify new instances

ML - Inductive Learning Hypothesis

• The learning task consists on fining a hypothesis h identical to the objective concept c from the set of instances X.

• We only have information about c from the training examples
  • We don’t have all the possible instances of X

• Inductive learning algorithms can only guarantee that h adjusts to c over for the training data

• If we don’t have more information, we assume that the best hypothesis for unseen instances, is that hypothesis that best adjusts to the observed data in the training set

ML - Design of a ML system

• Any hypothesis found that accurately approximates the objective function over a large enough set of training examples will also accurately approximate the objective function over other unseen examples

ML - Concept Learning as Search

• We can see concept learning as a search task
  • Search over the hypothesis space
    • Defined space over the hypothesis representation
• Find the hypothesis that best adjusts to the training examples

ML- Computing the Hypothesis Space

• In the “EnjoySport” example
• Possible values for each attribute:
  • Sky has 3
  • AirTemp has 2
  • Humidity has 2
  • Wind has 2
  • Water has 2
  • Forecast has 2
• Possible distinct instances: \(3 \times 2 \times 2 \times 2 \times 2 \times 2 = 96\)
• Synctactically different instances: \(5 \times 4 \times 4 \times 4 \times 4 \times 4 = 5,120\)
  • Considering ? and \(\emptyset\)
  • Any hypothesis with \(\emptyset\) represents an empty set, then it classifies the instance as negative
• Instances synctactically distinct: \(1 + 4 \times 3 \times 3 \times 3 \times 3 \times 3 = 973\)
  • This is a finite hypothesis space, small

ML- Ordering the Hypothesis Space: General to Specific

• Organize the hypothesis space for searching in it
• General to specific order
  • Relation more-general-than
• Design exhaustive search algorithm
  • Search in finite spaces
  • Without explicitly ennumerating all hypotheses

ML- Ordering the Hypothesis Space: General to Specific

• \(h_j\) more-general-than \(h_k\) (\(h_j >_g h_k\))
• Applied to our example:

ML - The Find-S Algorithm

• Uses the more-general-than relation to organize the search for a hypothesis consistent with the training examples
  • Start with the most specific possible hypothesis in \(H\)
  • Generalize this hypothesis when it fails in covering a positive example
    • Most specific hypothesis: \(h_0 \leftarrow \{\emptyset, \emptyset, \emptyset, \emptyset, \emptyset, \emptyset \}\)
  • Generalize \(h_0\) with the first example: \(\{Sunny, Warm, Normal, Strong, Warm, Same\}\)
    • \(h_1 \leftarrow \{Sunny, Warm, Normal, Strong, Warm, Same\}\)
  • \(h_1\) is still very specific, we generalize with the following example: \(\{Sunny, Warm, High, Strong, Same\}\)
  • Negative example, it doesn’t modify \(h_2\)
  • For the 4\(th\) example: \(\{Sunny, Warm, High, Strong, Cool, Change\}\), \(h_2\) is very specific and we generalize \(h_2\)
    • \(h_3 \leftarrow \{Sunny, Warm, ?, Strong, ?, ?\}\)

ML - The Find-S Algorithm

ML - The Find-S Algorithm

Finding a most specific hypothesis

1. Initialize \(h\) to the most specific hypothesis in \(H\)
2. For each positive training instance \(x\)
   • For each attribute constraint \(a_i\) in \(h\)
     • If the constraint \(a_i\) in \(h\) is satisfied by \(x\)
       • Then do nothing
       • Else replace \(a_i\) in \(h\) by the next more general constraint that is satisfied by \(x\)
3. Output hypothesis \(h\)

ML - The Find-S Algorithm

• Find-S
  • Works for hypothesis spaces described by conjunctions of attributes
    • Guarantees finding the most specific hypothesis from \(H\) being consistent with the positive examples
    • The final hypothesis is also consistent with negative examples when the right objective concept is contained in \(H\) and the training examples are correct
      • We assume no noise

ML - The Find-S Algorithm

• Activity
• If we have positive and negative examples as coordinates in the cartesian plane
• How can we use Find-S to find the most specific hypothesis consistent with the positive examples?

ML - The Find-S Algorithm - Questions

• Does Find-S converge to the correct objective concept?
  • It doesn’t tell when it finds a solution
• Why would we prefer a more specific hypothesis?
  • There can be more than one solution
• Are the training examples consistent?
  • There might be noise or errors in the data
• What happens if there exist several consistent hypotheses that are more specific?
  • Which of them should we choose?

ML - Version Spaces and the Candidate-elimination Algorithm

• Find-S finds one hypothesis consistent with the training examples
• The Candidate-Elimination algorithm
  • Finds a description of the set of all the hypotheses consistent with the training examples
  • Does not ennumerate (explicitly) all members of this set
  • Uses the partial order more-general-than

ML - Version Spaces - Definitions - Consistent Hypothesis

• A hypothesis \(h\) is consistent with a set of training examples \(D\) iff \(h(x) = c(x)\) for each example \(\langle x, c(x) \rangle\) in \(D\).

\[Consistent(h, D) = (\forall \langle x, c(x) \rangle \in D) \; h(x) = c(x)\]

ML - Version Spaces - Definitions - Version Space

• The set of all hypotheses consistent with the training set is known as the version space with respect to hypotheses \(H\) and training examples \(D\)

\[VS_{H,D} = \{h \in H | Consistent(h, D)\}\]

ML - Version Spaces - Definitions

• True Positive
  • Class: +, Prediction: +
• True Negative
  • Class: -, Prediction: -
• False Positive
  • Class: -, Prediction: +
• False Negative
  • Class: +, Prediction: -

ML - Version Space - List-Then-Eliminate Algorithm

• List all hypotheses in \(H\)
• Eliminates hypotheses not consistent with any training example
  • The set of hypotheses is reduced
  • Ideally we end with only one consistent hypothesis
    • We presume this is the objective concept
  • The training set might not be enough to reduce the version space to only one hypothesis
    • The output might be a set of hypotheses
• Applies when the hypothesis space \(H\) is finite
  • Advantage: Guarantees finding all hypotheses consistent with the dataset
  • Disadvantage: Requires an exhaustive ennumeration of the hypotheses in \(H\)
    • Only feasible for trivial hypothesis spaces

ML - Version Space - List-Then-Eliminate Algorithm

1. \(VersionSpace \leftarrow\) a list containing every hypothesis in \(H\)
2. For each training example, \(\langle x, c(x) \rangle\)
   • remove from \(VersionSpace\) any hypothesis \(h\) for which \(h(x) \neq c(x)\)
3. Output the list of hypotheses in \(VersionSpace\)

ML - Version Space - Candidate-Elimination Algorithm

• Uses the same principle of List-Then-Eliminate
• Uses a more compact representation of the version space
  • Delimits the boundaries of the verison space
  • Instance of the most general boundary: G
  • Instance of the least general boundary: S

ML - Version Space - Candidate-Elimination Algorithm

• In the “Enjoy-Sport” example
  • We have 6 hypotheses consistent with \(H\) from the training set
  • Find-S could find only 1 of them
  • The 6 hypotheses are represented with:
    • \(S\): \(\langle Sunny, Warm, ?, Strong, ?, ? \rangle\)
    • \(G\): \(\{ \langle Suny, ?, ?, ?, ?, ? \rangle, \langle ?, Warm, ?, ?, ?, ? \rangle\}\)

ML - Version Space - Candidate-Elimination Algorithm

ML - Version Space - Candidate-Elimination Algorithm - Definitions

• The General boundary G, with respect to hypothesis space \(H\) and training data \(D\), is the set of general members of \(H\) consistent with \(D\).
  • \(G \equiv \{g \in H | Consistent(g, D) \land (\neg \exists g' \in H) [(g' >_g g) \land Consistent(g', D)]\}\)
• The specific boundary S, with respect to hypothesis space \(H\) and training data \(D\), is the set of least general (most specific) members of \(H\) consistent with \(D\).
  • \(S \equiv \{s \in H | Consistent(s, D) \land (\neg \exists s' \in H) [(s >_g s') \land Consistent(s', D)]\}\)

ML - Version Space - Candidate-Elimination Algorithm - Definitions

• The general boundary \(G\) of \(VS_{H,D}\) is the set of its most general members
• The specific boundary \(S\) of \(VS_{H,D}\) is the sef of its most specific members
• Each member of the version space falls in these boundaries
• \(VS_{H,D} = \{ h \in H \; | \; (\exists s \in S) \; (\exists g \in G) \; (g \geq h \geq s)\}\)
  • \(x \geq y \rightarrow x\) is more general or equal than \(y\)

ML - Version Space - Candidate-Elimination Algorithm

• Initialize \(G\) to the set of maximally general hypotheses in \(H\)
• Initialize \(S\) to the set of maximally specific hypotheses in \(H\)
• For each training example \(d\), do
  • If \(d\) is a positive example
    • Remove from \(G\) any hypothesis inconsistent with \(d\)
    • For each hypothesis \(s\) in \(S\) that is not consistent with \(d\)
      • Remove \(s\) from \(S\)
      • Add to \(S\) all minimal generalizations \(h\) of \(s\) such that
        • \(H\) is consistent with \(d\), and some member of \(G\) is more general than \(h\)
      • Remove from \(S\) any hypothesis that is more general than another hypothesis in \(S\)
  • If \(d\) is a negative example
    • Remove from \(S\) any hypothesis inconsistent with \(d\)
    • For each hypothesis \(g\) in \(G\) that is not consistent with \(d\)
      • Remove \(g\) from \(G\)
      • Add to \(G\) all minimal specializations \(h\) of \(g\) such that
        • \(H\) is consistent with \(d\), and some member of \(S\) is more specific than \(h\)
      • Remove from \(G\) any hypothesis that is less general than another hypothesis in \(G\)

ML - Version Space - Candidate-Elimination Algorithm

• We start with:

ML - Version Space - Candidate-Elimination Algorithm

• We add the first example (positive: \(\{\langle Sunny, Warm, Normal, Strong, Warm, Same \rangle \}\))
  • \(S_0\) doesn’t cover it
  • We move the most specific boundary to the minimum most general hypothesis that covers the new example and get \(S_1\)
  • We don’t modify \(G_0\) because it does cover the example

ML - Version Space - Candidate-Elimination Algorithm

• We add the second example (positive: \(\{\langle Sunny, Warm, High, Strong, Warm, Same \rangle \}\))
  • \(S_1\) doesn’t cover it
  • Generalize \(S_1\) to \(S_2\) to cover the new example
  • \(G_0\) doesn’t change, again
• Similar to the process of Find-S
• This happens because
  • Positive examples make that boundary \(S\) gets more general
  • Negative examples make that boundary \(G\) gets more specific

ML - Version Space - Candidate-Elimination Algorithm

• We add the third example (negative: \(\{\langle Rainy, Cold, High, Strong, Warm, Change \rangle \}\))
  • Boundary \(G\) is very general and covers the negative example, It predict this example as positive
  • Make \(G\) more specific so that it doesn’t cover the negative example

ML - Version Space - Candidate-Elimination Algorithm

ML - Version Space - Candidate-Elimination Algorithm

• The boundary \(S\) of the version space forms a summary of the positive examples previously seen
  • Any hypothesis more general than \(S\), by definition, will cover any example that \(S\) covers. It will cover any previous positive example
• Boundary \(G\) forms a summary of the negative examples previously seen
  • Any more specific hypothesis than \(G\) ensures being consistent with the previous negative examples. By definition, none of these hypotheses may cover examples that \(G\) doen’t cover

ML - Version Space - Candidate-Elimination Algorithm

• We add the fourth example (positive: \(\{\langle Sunny, Warm, High, Strong, Cool, Change \rangle \}\))
  • Generalize boundary \(S\) of the version space
  • We eliminate a member of boundary \(G\)
    • Because it doesn’t cover the new positive example

ML - Version Space - Candidate-Elimination Algorithm

ML - Version Space - Candidate-Elimination Algorithm

• The final version space for Enjoy-Sport

ML - Version Space - Candidate-Elimination

• Candidate-Elimination will converge to the hypothesis that correctly describes the objective concept given that
  • There are no errors in the training dataset
  • There exists a hypothesis in \(H\) that correctly describes the objective concept
• What happens if there are errors in the data?
  • i.e., the second examples is presented as negative
  • The version space will end empty
  • Can also end empty if the hypotheses language doesn’t have the capability to describe the objective concept
• Which training example should we choose next?