CSCE 420 Lecture 28

« previous | Friday, April 26, 2013 | next »

End Exam 2 content

Honors Lecture

Machine Learning

"Learning from experience" (in true light of "intelligence")

→ Adapt and Improve performance

Knowledge Base Repair: correct errors in KB rules
Neural Networks: graph of sensor inputs through node "network" to output

Supervised learning

Labeled examples:

Labels: finite set of classes/categories; usually small, maybe only positive and negative classes
Examples: described as feature vectors; maps state of features to an action

Driving Example

Labels:

c₁ = accelerate
c₂ = do nothing
c₃ = brake

Features:

F₁ = light (red, green, yellow)
F₂ = pedestrians
F₃ = distance to car in front
F₃ = surface wet?

Training Examples:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle \text{red}, \mathbf{F}, 120, \mathbf{F} = c_3 \right\rangle}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle \text{green}, \textbf{T}, 100, \mathbf{T} c_3 \right\rangle}

Unsupervised learning

Unlabeled Examples

Seems much more abstract...

Reinforcement learning

Indirect feedback

Credit assignment

Analyzing Learning

Usually plotted on learning curve graphs:

X axis → number of examples
Y axis → accuracy
Usually plateaus before reaching 100% accuracy

Decision Trees

Each node represents a feature, and branches represent that feature's values:

F₁
|-- True: F₂
|   |-- True:  (+)
|   `-- False: (-)
`-- False: (+)

How does one construct a decision tree?

ID3 Algorithm

For each node, What feature gains the most information?

ID3(example) returns Tree
  if example is pure, make leaf
  else
    for each feature f
      divide examples into 2 subsets A and B
      calculate information gain IG = H_ex - sum(weight[b] * entropy[b], b in branch)
      for F_i that maximizes IG
        return Tree(ID3(A), ID3(B))

Entropy minimization

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H = -\sum_i Pr[X=i] \, \log_2{(Pr[X=i])}}

Over a domain of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} classes, if we were to plot entropy (Y axis) based on how many of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} classes were positive, we would get a parabola with roots 0 and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} and maximum at (n/2, 1)

Perceptrons: Linear Classifiers

Labeled examples of binary classes (positive or negative)

If these are plotted as points on a graph, how would we find a line (discriminant function, hyperplane) to divide the positives and negatives into groups.

In other words, if our examples have values Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x} = \left\langle x_1, x_2, \ldots, x_n \right\rangle} and our target classes are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{y} = \left\langle +, -, +, +, \ldots \right\rangle} , we can write our learned rule as a weighted linear combination compared to a threshhold:

if x₁ w₁ + x₂ w₂ >= c
    return +
else
    return -
end if

we want to find the weight vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w} = \left\langle w_1, w_2, \ldots, w_n \right\rangle} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x} \cdot \vec{w} \ge 0} and the mean squared error Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E = \frac{1}{2} \sum \left( x_i \, w_i - y_i \right)^2} is minimized.

Gradient Descent

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta w_i \propto -\nabla E = -\left( \frac{\partial E}{\partial w_i} \right)}

Delta Training Rule: for each example update:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w}_i \gets \vec{w_1} + \eta \, \vec{x}_i \cdot (y_i - \vec{w}_i \cdot \vec{x}_i)} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta} is a small learning rate (e.g. 0.001

This eventually causes a random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w}} assignment to migrate toward the best position

This has application in neural networks, where each node is "trained" to understand its threshhold for executing.

Summary

Machine learning boils down to improving a function or a model (hypothesis):

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h : X \mapsto C}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is instance space
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is a discrete output space
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \in H} is a hypothesis from Hypothesis Space
- for ID3, $H$ is the space of all decision tree
- for Perceptrons, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^{n+1}} for instance space dimension of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} (don't forget the threshhold is a weight on the constant term!)