perceptron 2 4 2008

Information about perceptron 2 4 2008

Published on April 30, 2008

Author: Belly

Source: authorstream.com

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)

28. 04. 2008
0 views

17. 09. 2007
0 views

22. 04. 2008
0 views

18. 04. 2008
0 views

17. 04. 2008
0 views

16. 04. 2008
0 views

14. 04. 2008
0 views

13. 04. 2008
0 views

10. 04. 2008
0 views

09. 04. 2008
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

13. 09. 2007
0 views

13. 09. 2007
0 views

13. 09. 2007
0 views

13. 09. 2007
0 views

05. 10. 2007
0 views

12. 10. 2007
0 views

17. 10. 2007
0 views

18. 10. 2007
0 views

22. 10. 2007
0 views

22. 10. 2007
0 views

07. 09. 2007
0 views

07. 09. 2007
0 views

07. 09. 2007
0 views

13. 09. 2007
0 views

23. 10. 2007
0 views

23. 10. 2007
0 views

24. 10. 2007
0 views

05. 10. 2007
0 views

17. 10. 2007
0 views

31. 08. 2007
0 views

01. 12. 2007
0 views

07. 12. 2007
0 views

25. 10. 2007
0 views

29. 10. 2007
0 views

29. 10. 2007
0 views

30. 10. 2007
0 views

02. 11. 2007
0 views

07. 09. 2007
0 views

22. 10. 2007
0 views

14. 11. 2007
0 views

13. 09. 2007
0 views

16. 11. 2007
0 views

17. 11. 2007
0 views

21. 11. 2007
0 views

22. 11. 2007
0 views

23. 12. 2007
0 views

13. 09. 2007
0 views

02. 01. 2008
0 views

04. 01. 2008
0 views

15. 10. 2007
0 views

06. 11. 2007
0 views

07. 01. 2008
0 views

02. 11. 2007
0 views

07. 10. 2007
0 views

20. 11. 2007
0 views

23. 10. 2007
0 views

13. 09. 2007
0 views

03. 01. 2008
0 views

19. 02. 2008
0 views

20. 02. 2008
0 views

27. 02. 2008
0 views

29. 02. 2008
0 views

07. 09. 2007
0 views

14. 12. 2007
0 views

10. 03. 2008
0 views

30. 10. 2007
0 views

11. 03. 2008
0 views

12. 03. 2008
0 views

29. 12. 2007
0 views

26. 03. 2008
0 views

26. 03. 2008
0 views

31. 08. 2007
0 views

09. 10. 2007
0 views

31. 08. 2007
0 views

31. 08. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

13. 10. 2007
0 views

26. 02. 2008
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

31. 08. 2007
0 views

07. 01. 2008
0 views

07. 09. 2007
0 views

27. 09. 2007
0 views

13. 09. 2007
0 views

17. 10. 2007
0 views

19. 11. 2007
0 views

07. 09. 2007
0 views

29. 11. 2007
0 views

28. 12. 2007
0 views

13. 09. 2007
0 views

31. 08. 2007
0 views

01. 10. 2007
0 views

19. 06. 2007
0 views

15. 10. 2007
0 views

22. 10. 2007
0 views

31. 08. 2007
0 views

31. 08. 2007
0 views

11. 12. 2007
0 views

31. 08. 2007
0 views

19. 06. 2007
0 views

22. 10. 2007
0 views

19. 06. 2007
0 views

13. 11. 2007
0 views

19. 11. 2007
0 views

17. 10. 2007
0 views

07. 04. 2008
0 views

15. 10. 2007
0 views

07. 11. 2007
0 views

19. 06. 2007
0 views

07. 09. 2007
0 views

31. 08. 2007
0 views

03. 01. 2008
0 views

07. 09. 2007
0 views

28. 09. 2007
0 views

12. 10. 2007
0 views

13. 09. 2007
0 views