Learning from Observations Chapter 18 Section 1 4 Outline Learning agents Inductive learning Nearest Neighbors
Learning agents Sometimes we want to invest time and effort to observe the feedback from our environment to our actions in order to improve these actions so we can more effectively optimize our utility in the future. Learning element
Design of a learning element is affected by Which components of the performance element are to be learned (e.g. learn to stop for traffic light) What feedback is available to learn these components (e.g. visual feedback form camera) What representation is used for the components (e.g. logic, probabilistic descriptions, attributes,...)
Type of feedback: Supervised learning: correct answers for each example (label). Unsupervised learning: correct answers not given. Reinforcement learning: occasional rewards Two Examples of Learning Object Categories. Here is your training set (2 classes):
Here is your test set: Does it belong to one of the above classes? Learning from 1 Example Copied from P. Perona talk slides.
S. Savarese, 2003 P. Buegel, 1562 Inductive learning Simplest form: learn a function from examples f is the target function
An example is a pair (x, f(x)) Problem: find a hypothesis h such that h f given a training set of examples Inductive learning method
Construct/adjust h to agree with f on training set (h is consistent if it agrees with f on all examples) E.g., curve fitting: Inductive learning method Construct/adjust h to agree with f on training set (h is consistent if it agrees with f on all examples) E.g., curve fitting:
Inductive learning method Inductive learning method Inductive learning method which curve is best?
Inductive learning method Ockhams razor: prefer the simplest hypothesis consistent with data Supervised Learning I Example: Imagine you want to classify
versus Data: 100 monkey images and 200 human images with labels what is what. {xi ,yi 0}, i 1,...,100 {x j ,yj 1}, j 1,...,200
where x represents the greyscale of the image pixels and y=0 means monkey while y=1 means human. Task: Here is a new image: monkey or human? 1 nearest neighbors
(your first ML algorithm!) Idea: 1. Find the picture in the database which is closest to your query image. 2. Check its label. 3. Declare the class of your query image to be the same as that of the closest picture. query
closest image 1NN Decision Surface decision curve Distance Metric
How do we measure what it means to be close? Depending on the problem we should choose an appropriate distance metric (or more generally, a (dis)similarity measure)
Hamming distance: D(xn , xm) | xn xm | Scaled Euclidean Distance:
D(xn , xm) (xn xm)T A (xn x m) {x discrete};
{x cont .}; -Demo: http://www.comp.lancs.ac.uk/~kristof/research/notes/nearb/cluster.html -Matlab Demo. Remarks on NN methods We only need to construct a classifier that works locally for each query. Hence: We dont need to construct a classifier everywhere in space.
Classifying is done at query time. This can be computationally taxing at a time where you might want to be fast. Memory inefficient. Curse of dimensionality: imagine many features are irrelevant / noisy distances are always large. Very flexible, not many prior assumptions. k-NN variants robust against bad examples.
Summary Learning agent = performance element + learning element For supervised learning, the aim is to find a simple hypothesis approximately consistent with training examples Decision tree learning + boosting Learning performance = prediction accuracy measured on test set