fun with hyperplanes fall 2006

Information about fun with hyperplanes fall 2006

Published on December 21, 2007

Author: Jacqueline

Source: authorstream.com

Content

Fun with Hyperplanes: Perceptrons, SVMs, and Friends:  Fun with Hyperplanes: Perceptrons, SVMs, and Friends Ryan Gabbard From CSE 391, Spring 2006 Universal Machine Learning Diagram:  Universal Machine Learning Diagram Generative v. Discriminative Models:  Generative v. Discriminative Models Generative question: “How can we model the joint distribution of the classes and the features?” Why waste energy on stuff we don’t care about? Let’s optimize the job we’re trying to do directly! Discriminative question: “What features distinguish the classes from one another?” Example:  Example Modeling what sort of bizarre distribution produced these training points is hard, but distinguishing the classes is a piece of cake! chart from MIT tech report #507, Tony Jebara Linear Classification:  Linear Classification Representing Lines:  Representing Lines How do we represent a line? In general a hyperplane is defined by Why bother with this weird representation? Projections:  Projections alternate intuition: recall the dot product of two vectors is simply the product of their lengths and the cosine of the angle between them Now classification is easy!:  Now classification is easy! But... how do we learn this mysterious model vector? Perceptron Learning Algorithm :  Perceptron Learning Algorithm Perceptron Update Example I:  Perceptron Update Example I Perceptron Update Example II:  Perceptron Update Example II Properties of the Simple Perceptron:  Properties of the Simple Perceptron You can prove that if it’s possible to separate the data with a hyperplane (i.e. if it’s linearly separable), the algorithm will converge to that hyperplane. But what if it isn’t? Then perceptron is very unstable and bounces all over the place. Voted Perceptron:  Voted Perceptron Works just like a regular perceptron, except you keep track of all the intermediate models you created. When you want to classify something, you let each of the (many, many) models vote on the answer and take the majority. Properties of Voted Perceptron:  Properties of Voted Perceptron Simple! Much better generalization performance than regular perceptron (almost as good as SVMs) Can use the ‘kernel trick’ Training as fast as regular perceptron But run-time is slower. Averaged Perceptron:  Averaged Perceptron Extremely simple! Return as your final model the average of all your intermediate models. Approximation to voted perceptron. Nearly as fast to train and exactly as fast to run as regular perceptron. What’s wrong with these hyperplanes?:  What’s wrong with these hyperplanes? They’re unjustifiably biased!:  They’re unjustifiably biased! A less biased choice:  A less biased choice Margin:  Margin The margin is the distance to closest point in the training data. We tend to get better generalization to unseen data if we choose the separating hyperplane which maximizes the margin. Support Vector Machines:  Support Vector Machines Another learning method which explicitly calculates the maximum margin hyperplane by solving a gigantic quadratic programming problem. Generally considered the highest-performing current machine learning technique. But it’s relatively slow and very complicated. Margin-Infused Relaxed Algorithm (MIRA):  Margin-Infused Relaxed Algorithm (MIRA) Multiclass; each class has a prototype vector Classify an instance by choosing the class whose prototype vector has the greatest dot product with the instance During training, when updating make the ‘smallest’ (in a sense) change to the prototype vectors which guarantees correct classification by a minimum margin Pays attention to the margin directly What if it isn’t separable?:  What if it isn’t separable? Project it to someplace where it is!:  Project it to someplace where it is! Kernel Trick:  If our data isn’t linearly separable, we can define a projection to map it into a much higher dimensional feature space where it is. For some algorithms where everything can be expressed as the dot products of instances (SVM, voted perceptron, MIRA) this can be done efficiently using something called the `kernel trick’ Kernel Trick

Related presentations


Other presentations created by Jacqueline

Bahl Information Divide
02. 11. 2007
0 views

Bahl Information Divide

Chap 5 WW2
13. 11. 2007
0 views

Chap 5 WW2

Lecture8Unification
16. 11. 2007
0 views

Lecture8Unification

chapter14
17. 12. 2007
0 views

chapter14

Air Power Thru the Cold War
24. 12. 2007
0 views

Air Power Thru the Cold War

DaleEnerson
30. 12. 2007
0 views

DaleEnerson

09Feb05 Action NLNR
04. 01. 2008
0 views

09Feb05 Action NLNR

BHallTalk110601Rev3
01. 12. 2007
0 views

BHallTalk110601Rev3

Liang
07. 01. 2008
0 views

Liang

EU Ukr Action Plan
01. 11. 2007
0 views

EU Ukr Action Plan

gpps02
05. 11. 2007
0 views

gpps02

Bulgaria
26. 11. 2007
0 views

Bulgaria

FGMHS Example
27. 12. 2007
0 views

FGMHS Example

subprime
19. 02. 2008
0 views

subprime

John Helmus BEA BISG
24. 02. 2008
0 views

John Helmus BEA BISG

5791
27. 02. 2008
0 views

5791

the american west biographies
29. 02. 2008
0 views

the american west biographies

MYPYRAMIDJEOPARDY
05. 03. 2008
0 views

MYPYRAMIDJEOPARDY

Box02
14. 03. 2008
0 views

Box02

wcit2008 athens04
27. 03. 2008
0 views

wcit2008 athens04

MilDefLecture
30. 03. 2008
0 views

MilDefLecture

semfin
13. 04. 2008
0 views

semfin

AFD 071029 092
05. 11. 2007
0 views

AFD 071029 092

Russell
03. 10. 2007
0 views

Russell

Mann IHY Mag 2005
05. 11. 2007
0 views

Mann IHY Mag 2005

biodiesel safety
08. 11. 2007
0 views

biodiesel safety

map 1
21. 11. 2007
0 views

map 1

BPC Section 3 final
03. 12. 2007
0 views

BPC Section 3 final

nbi03 jim horn
29. 11. 2007
0 views

nbi03 jim horn

AIDAJuneTalk
04. 12. 2007
0 views

AIDAJuneTalk

20 social networking
18. 12. 2007
0 views

20 social networking

housemtg 20071002
02. 11. 2007
0 views

housemtg 20071002

w6Collegative1
04. 01. 2008
0 views

w6Collegative1

DamageTrn Guide
05. 12. 2007
0 views

DamageTrn Guide

HIA
14. 11. 2007
0 views

HIA