perceptron 2 4 2008

Information about perceptron 2 4 2008

Published on April 30, 2008

Author: Belly

Source: authorstream.com

Content

Perceptrons and Linear Classifiers:  Perceptrons and Linear Classifiers William Cohen 2-4-2008 Slide2:  Announcement: no office hours for William this Friday 2/8 Slide3:  Dave Touretzky’s Gallery of CSS Descramblers Linear Classifiers:  Linear Classifiers Let’s simplify life by assuming: Every instance is a vector of real numbers, x=(x1,…,xn). (Notation: boldface x is a vector.) There are only two classes, y=(+1) and y=(-1) A linear classifier is vector w of the same dimension as x that is used to make this prediction: Slide5:  w -W Visually, x · w is the distance you get if you “project x onto w” X1 X1 . w X2 . w The line perpendicular to w divides the vectors classified as positive from the vectors classified as negative. In 3d: lineplane In 4d: planehyperplane … Slide6:  Wolfram MathWorld Mediaboost.com Geocities.com/bharatvarsha1947 Slide7:  Notice that the separating hyperplane goes through the origin…if we don’t want this we can preprocess our examples: What have we given up?:  What have we given up? -1 +1 Outlook overcast Humidity normal What have we given up?:  What have we given up? Not much! Practically, it’s a little harder to understand a particular example (or classifier) Practically, it’s a little harder to debug You can still express the same information You can analyze things mathematically much more easily Naïve Bayes as a Linear Classifier:  Naïve Bayes as a Linear Classifier Consider Naïve Bayes with two classes (+1, -1) and binary features (0,1). Naïve Bayes as a Linear Classifier:  Naïve Bayes as a Linear Classifier Naïve Bayes as a Linear Classifier:  Naïve Bayes as a Linear Classifier “log odds” Naïve Bayes as a Linear Classifier:  Naïve Bayes as a Linear Classifier pi qi Naïve Bayes as a Linear Classifier:  Naïve Bayes as a Linear Classifier Naïve Bayes as a Linear Classifier:  Naïve Bayes as a Linear Classifier Summary: NB is linear classifier Weights wi have a closed form which is fairly simple, expressed in log-odds An Even Older Linear Classifier:  An Even Older Linear Classifier 1957: The perceptron algorithm: Rosenblatt WP: “A handsome bachelor, he drove a classic MGA sports car and was often seen with his cat named Tobermory. He enjoyed mixing with undergraduates, and for several years taught an interdisciplinary undergraduate honors course entitled "Theory of Brain Mechanisms" that drew students equally from Cornell's Engineering and Liberal Arts colleges…this course was a melange of ideas .. experimental brain surgery on epileptic patients while conscious, experiments on .. the visual cortex of cats, ... analog and digital electronic circuits that modeled various details of neuronal behavior (i.e. the perceptron itself, as a machine).” Built on work of Hebbs (1949); also developed by Widrow-Hoff (1960) 1960: Perceptron Mark 1 Computer – hardware implementation Slide17:  Bell Labs TM 59-1142-11– Datamation 1961 – April 1 1984 Special Edition of CACM An Even Older Linear Classifier:  An Even Older Linear Classifier 1957: The perceptron algorithm: Rosenblatt WP: “A handsome bachelor, he drove a classic MGA sports car and was often seen with his cat named Tobermory. He enjoyed mixing with undergraduates, and for several years taught an interdisciplinary undergraduate honors course entitled "Theory of Brain Mechanisms" that drew students equally from Cornell's Engineering and Liberal Arts colleges…this course was a melange of ideas .. experimental brain surgery on epileptic patients while conscious, experiments on .. the visual cortex of cats, ... analog and digital electronic circuits that modeled various details of neuronal behavior (i.e. the perceptron itself, as a machine).” Built on work of Hebbs (1949); also developed by Widrow-Hoff (1960) 1960: Perceptron Mark 1 Computer – hardware implementation 1969: Minksky & Papert book shows perceptrons limited to linearly separable data, and Rosenblatt dies in boating accident 1970’s: learning methods for two-layer neural networks Mid-late 1980’s (Littlestone & Warmuth): mistake-bounded learning & analysis of Winnow method; early-mid 1990’s, analyses of perceptron/Widrow-Hoff Slide19:  Experimental evaluation of Perceptron vs WH and Experts (Winnow-like methods) in SIGIR-1996 (Lewis, Schapire, Callan, Papka), and (Cohen & Singer) Freund & Schapire, 1998-1999 showed “kernel trick” and averaging/voting worked The voted perceptron:  The voted perceptron A B instance xi Slide21:  (1) A target u (2) The guess v1 after one positive example. Slide22:  u -u 2γ u -u 2γ v1 +x2 +x1 v1 -x2 v2 (3a) The guess v2 after the two positive examples: v2=v1+x2 (3b) The guess v2 after the one positive and one negative example: v2=v1-x2 I want to show two things: The v’s get closer and closer to u: v.u increases with each mistake The v’s do not get too large: v.v grows slowly Slide23:  u -u 2γ u -u 2γ v1 +x2 +x1 v1 -x2 v2 (3a) The guess v2 after the two positive examples: v2=v1+x2 (3b) The guess v2 after the one positive and one negative example: v2=v1-x2 > γ Slide24:  u -u 2γ u -u 2γ v1 +x2 +x1 v1 -x2 v2 On-line to batch learning:  On-line to batch learning Pick a vk at random according to mk/m, the fraction of examples it was used for. Predict using the vk you just picked. (Actually, use some sort of deterministic approximation to this). The voted perceptron:  The voted perceptron Some more comments:  Some more comments Perceptrons are like support vector machines (SVMs) SVMs search for something that looks like u: i.e., a vector w where ||w|| is small and the margin for every example is large You can use “the kernel trick” with perceptrons Replace x.w with (x.w+1)d Experimental Results:  Experimental Results Slide30:  Task: classifying hand-written digits for the post office More Experimental Results (Linear kernel, one pass over the data):  More Experimental Results (Linear kernel, one pass over the data)

Related presentations


Other presentations created by Belly

Capital budgeting
28. 04. 2008
0 views

Capital budgeting

Nice pics slides
17. 09. 2007
0 views

Nice pics slides

pham07
18. 04. 2008
0 views

pham07

FC STONE GREAT WALL1
17. 04. 2008
0 views

FC STONE GREAT WALL1

Sauter Nuts Bolt ETFs
16. 04. 2008
0 views

Sauter Nuts Bolt ETFs

UnivOfGuelphNov26th
14. 04. 2008
0 views

UnivOfGuelphNov26th

fujiwara
13. 04. 2008
0 views

fujiwara

Week 08 Finance
10. 04. 2008
0 views

Week 08 Finance

Lct1
09. 04. 2008
0 views

Lct1

outlook
19. 06. 2007
0 views

outlook

Microsoft Windows Vista
19. 06. 2007
0 views

Microsoft Windows Vista

2004 presentation
13. 09. 2007
0 views

2004 presentation

Australian
13. 09. 2007
0 views

Australian

NBB
13. 09. 2007
0 views

NBB

Thilo Ewald ppt
13. 09. 2007
0 views

Thilo Ewald ppt

20031216 NASANIH presentation
05. 10. 2007
0 views

20031216 NASANIH presentation

mna presentation
17. 10. 2007
0 views

mna presentation

lect29 groupwords
18. 10. 2007
0 views

lect29 groupwords

Essential Q Imperialism 2
22. 10. 2007
0 views

Essential Q Imperialism 2

p puska
07. 09. 2007
0 views

p puska

Productivity
07. 09. 2007
0 views

Productivity

honeyPots
13. 09. 2007
0 views

honeyPots

NDB Bensouda
23. 10. 2007
0 views

NDB Bensouda

181105
24. 10. 2007
0 views

181105

METO200Lect19 20
05. 10. 2007
0 views

METO200Lect19 20

oksupercompsymp2006 talk matrow
17. 10. 2007
0 views

oksupercompsymp2006 talk matrow

mareyes
25. 10. 2007
0 views

mareyes

2 01 3
29. 10. 2007
0 views

2 01 3

Online Class Evaluations 8
30. 10. 2007
0 views

Online Class Evaluations 8

1 3Grand father Journey
02. 11. 2007
0 views

1 3Grand father Journey

TuijaKuisma
07. 09. 2007
0 views

TuijaKuisma

Metallsektor
14. 11. 2007
0 views

Metallsektor

insects in out
13. 09. 2007
0 views

insects in out

oasen
16. 11. 2007
0 views

oasen

Unit 10 Scent Theory
17. 11. 2007
0 views

Unit 10 Scent Theory

SPEAR 2004
21. 11. 2007
0 views

SPEAR 2004

danse macabre
22. 11. 2007
0 views

danse macabre

kmutt
13. 09. 2007
0 views

kmutt

NCUR SDT 4 19 05
04. 01. 2008
0 views

NCUR SDT 4 19 05

gerber colloq UICtop feb2002
15. 10. 2007
0 views

gerber colloq UICtop feb2002

Lioi Altered Version
07. 01. 2008
0 views

Lioi Altered Version

Five Halloween Pumpkins audacity
02. 11. 2007
0 views

Five Halloween Pumpkins audacity

smime
07. 10. 2007
0 views

smime

CdF BEC
20. 11. 2007
0 views

CdF BEC

WEB C Schumacher
23. 10. 2007
0 views

WEB C Schumacher

bsb
13. 09. 2007
0 views

bsb

2006052213550876705
03. 01. 2008
0 views

2006052213550876705

1 11
19. 02. 2008
0 views

1 11

Ukraine
20. 02. 2008
0 views

Ukraine

truck tmp1002
27. 02. 2008
0 views

truck tmp1002

ace program plan
29. 02. 2008
0 views

ace program plan

takala
07. 09. 2007
0 views

takala

464 TM12
14. 12. 2007
0 views

464 TM12

ICEBP presentation for ANZCP A
10. 03. 2008
0 views

ICEBP presentation for ANZCP A

aionescu cmc dec06
30. 10. 2007
0 views

aionescu cmc dec06

creationtalk
11. 03. 2008
0 views

creationtalk

Data Mining 2
12. 03. 2008
0 views

Data Mining 2

Omaha Pres for NAP web2
29. 12. 2007
0 views

Omaha Pres for NAP web2

sustainable development part1
26. 03. 2008
0 views

sustainable development part1

Schrage
31. 08. 2007
0 views

Schrage

IHYJP Kickoff Poster
09. 10. 2007
0 views

IHYJP Kickoff Poster

020703 DHCAL
31. 08. 2007
0 views

020703 DHCAL

Vimpel Com
31. 08. 2007
0 views

Vimpel Com

Overland vista uib itforum
19. 06. 2007
0 views

Overland vista uib itforum

OS Notes
19. 06. 2007
0 views

OS Notes

NVIDIA OpenGL on Vista
19. 06. 2007
0 views

NVIDIA OpenGL on Vista

NonAdmin Pilot
19. 06. 2007
0 views

NonAdmin Pilot

New Mexico NETUG WPF
19. 06. 2007
0 views

New Mexico NETUG WPF

nercomp SIG
19. 06. 2007
0 views

nercomp SIG

MSAM Launch Vista Final Updated
19. 06. 2007
0 views

MSAM Launch Vista Final Updated

MOSS WF Talk
19. 06. 2007
0 views

MOSS WF Talk

More Online Games
19. 06. 2007
0 views

More Online Games

MHay Wireless
19. 06. 2007
0 views

MHay Wireless

Marl WSUS3
19. 06. 2007
0 views

Marl WSUS3

mail list news
19. 06. 2007
0 views

mail list news

Lenovo UofU
19. 06. 2007
0 views

Lenovo UofU

Lecture II
19. 06. 2007
0 views

Lecture II

Smith F09
13. 10. 2007
0 views

Smith F09

35508
26. 02. 2008
0 views

35508

pinar
19. 06. 2007
0 views

pinar

pgp
19. 06. 2007
0 views

pgp

pessner
19. 06. 2007
0 views

pessner

Overview Presentation
19. 06. 2007
0 views

Overview Presentation

North Dakota Annuity Deck
19. 06. 2007
0 views

North Dakota Annuity Deck

Rutland Presentation plenary4
31. 08. 2007
0 views

Rutland Presentation plenary4

NAMI NC 112707
07. 01. 2008
0 views

NAMI NC 112707

finland poster
07. 09. 2007
0 views

finland poster

sample
27. 09. 2007
0 views

sample

dtk
13. 09. 2007
0 views

dtk

Phenotyping Oxford
17. 10. 2007
0 views

Phenotyping Oxford

dog breeding
19. 11. 2007
0 views

dog breeding

5th trondhiem
29. 11. 2007
0 views

5th trondhiem

policies regs
28. 12. 2007
0 views

policies regs

GetuHailu
13. 09. 2007
0 views

GetuHailu

genealogy
01. 10. 2007
0 views

genealogy

net info 050928
19. 06. 2007
0 views

net info 050928

chap7
15. 10. 2007
0 views

chap7

Rafael Guillen CCAD SIAM mar06
22. 10. 2007
0 views

Rafael Guillen CCAD SIAM mar06

na3 Russia
31. 08. 2007
0 views

na3 Russia

Sois Global Programs3 12 04
31. 08. 2007
0 views

Sois Global Programs3 12 04

sacha
31. 08. 2007
0 views

sacha

amm pres valdez lacnic
22. 10. 2007
0 views

amm pres valdez lacnic

nwnt
19. 06. 2007
0 views

nwnt

STAR shielding 2
13. 11. 2007
0 views

STAR shielding 2

voiceline overview
17. 10. 2007
0 views

voiceline overview

gross PPT
07. 04. 2008
0 views

gross PPT

WP1a
15. 10. 2007
0 views

WP1a

Microarray Data Standard
07. 11. 2007
0 views

Microarray Data Standard

Lim Badejo Dell Presentation 1
19. 06. 2007
0 views

Lim Badejo Dell Presentation 1

HongKong Punkka Salo
07. 09. 2007
0 views

HongKong Punkka Salo

Dvoretsky
31. 08. 2007
0 views

Dvoretsky

qm1 web
03. 01. 2008
0 views

qm1 web

IAPS
07. 09. 2007
0 views

IAPS

yalestudy
28. 09. 2007
0 views

yalestudy

digvlsideslec1
12. 10. 2007
0 views

digvlsideslec1

mead
13. 09. 2007
0 views

mead

bashmakov
31. 08. 2007
0 views

bashmakov