LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 1 - The Learning Problem (http://book.caltech.edu/bookforum/forumdisplay.php?f=108)
-   -   Chapter 1 - Problem 1.3 (http://book.caltech.edu/bookforum/showthread.php?t=4413)

meixingdg 09-11-2013 02:14 PM

Chapter 1 - Problem 1.3
 
I am a bit stuck on part b. I am not sure how to start. Could anyone give a nudge in the right direction?

magdon 09-11-2013 06:22 PM

Re: Chapter 1 - Problem 1.3
 
Quote:

Originally Posted by meixingdg (Post 11481)
I am a bit stuck on part b. I am not sure how to start. Could anyone give a nudge in the right direction?

The first part is following from the weight update rule for PLA. The second part follows from the first part using a standard induction proof.

mxcnrawker 01-14-2015 12:23 AM

Re: Chapter 1 - Problem 1.3
 
Can you please do the proof for this problem, I can answer the question conceptually but mathematically I'm having a little trouble starting my argument for both part a and part b please :bow:

htlin 01-17-2015 07:20 AM

Re: Chapter 1 - Problem 1.3
 
Quote:

Originally Posted by mxcnrawker (Post 11902)
Can you please do the proof for this problem, I can answer the question conceptually but mathematically I'm having a little trouble starting my argument for both part a and part b please :bow:

Part a and the first half of part b can almost be found on p14 here:

http://www.csie.ntu.edu.tw/~htlin/co...02_handout.pdf

yongxien 07-20-2015 02:11 AM

Re: Chapter 1 - Problem 1.3
 
Hi I can solve the problem but I cannot understand how does this show that the perceptron algorithm will converge. Can somone explains to me what does the proof shows? I mean what does each step of the problems mean? Thanks

htlin 07-22-2015 06:57 AM

Re: Chapter 1 - Problem 1.3
 
Quote:

Originally Posted by yongxien (Post 11983)
Hi I can solve the problem but I cannot understand how does this show that the perceptron algorithm will converge. Can somone explains to me what does the proof shows? I mean what does each step of the problems mean? Thanks

The proof essentially shows that the (normalized) inner product between \mathbf{w}_t and the separating weights will be larger and larger in each iteration. But the normalized inner product is upper bounded by 1 and cannot be arbitrarily large. Hence PLA will converge.

elyakim 08-18-2015 03:07 AM

Re: Chapter 1 - Problem 1.3
 
Despite the slides I still have difficulty reading the equations.

In my PLA program weights are updated by "the difference between the 'target function line' and x2" for a misclassified example from a 2-dimensional space.

Example target function line: 2 + 3x. If x1 = 3 en x2 = 9, y = 9- (2+3*3) = -2
If misclassified the weights would be updated like: wt+1 = wt + x1 * -2
The method above maybe omits advantages of vector computation(?) as seen in the slides, but I was happy the simulation worked at all:)

The theoretic approach of this course seems more useful in the long term than 'simply learning to type methods', but for me is new and challenging.

So my questions are:
- is p a random symbol? I can't find it in the overview.
- does min1 < n < N stand for the sum of function (x) in range N?
- is yn the positive or negative difference between the target line and coordinate x2 (staying with the 2-dimensional graphical model)?
- I understand a little simple linear algebra for linear regression. Are vector computations making the understanding of this PLA equation easier?

Thanks in advance!

ntvy95 03-23-2016 01:21 AM

Re: Chapter 1 - Problem 1.3
 
3 Attachment(s)
Hi, I am stuck at the part (e). I have two questions:

1 - Is R' a typo? If R' is R then:

2 - Refer to (b), I observe that:

http://book.caltech.edu/bookforum/at...1&d=1458721054

Refer to (c), I observe that:

http://book.caltech.edu/bookforum/at...1&d=1458720991

But I think that http://book.caltech.edu/bookforum/at...1&d=1458721179 happens only when t <= 1? Am I mistaken somewhere?

MaciekLeks 03-23-2016 04:17 AM

Re: Chapter 1 - Problem 1.3
 
Quote:

Originally Posted by ntvy95 (Post 12300)
Hi, I am stuck at the part (e). I have two questions:

1 - Is R' a typo? If R' is R then:

2 - Refer to (b), I observe that:

http://book.caltech.edu/bookforum/at...1&d=1458721054

Refer to (c), I observe that:

http://book.caltech.edu/bookforum/at...1&d=1458720991

But I think that http://book.caltech.edu/bookforum/at...1&d=1458721179 happens only when t <= 1? Am I mistaken somewhere?

1. I assumed while performing a proof that ',' is just a comma char, not a typo
2. (c) works well for t>=0. Do not refer from (b) to (c). Try to refer to the previously proven inequality (so, from (c) to (b)).

ntvy95 03-23-2016 05:04 AM

Re: Chapter 1 - Problem 1.3
 
Quote:

Originally Posted by MaciekLeks (Post 12303)
1. I assumed while performing a proof that ',' is just a comma char, not a typo
2. (c) works well for t>=0. Do not refer from (b) to (c). Try to refer to the previously proven inequality (so, from (c) to (b)).

Aha! I see the point now! Thank you very much!!!


All times are GMT -7. The time now is 01:45 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.