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)
-   -   Problem 1.3 c (http://book.caltech.edu/bookforum/showthread.php?t=4648)

henry2015 12-18-2015 04:26 AM

Problem 1.3 c
 
||w(t)||^2
= ||w(t-1) + y(t-1)x(t-1)||^2 <--- this is from the PLA iteration
<=(||w(t-1)|| + ||y(t-1)x(t-1)||)^2 <--- a property: ||a + b|| <= ||a|| + ||b||
= ||w(t-1)||^2 + 2y(t-1)||w(t-1)||||x(t-1)|| + y(t-1)^2||x(t-1)||^2
= ||w(t-1)||^2 + 2y(t-1)||w(t-1)||||x(t-1)|| + ||x(t-1)||^2

Now, it seems like 2y(t-1)||w(t-1)||||x(t-1)|| is somehow <= 0.

||w(t-1)||||x(t-1)|| is >= 0 tho.

hence, it seems like 2y(t-1) is somehow <= 0.

It seems like I am on the wrong track as I am not using the hint mentioned in the question at all.

Any pointer?

Thanks!

htlin 12-19-2015 08:18 AM

Re: Problem 1.3 c
 
This inequality ||a + b|| <= ||a|| + ||b|| is quite loose in general and you may want to consider not using it. Hope this helps.

henry2015 06-10-2016 03:19 AM

Re: Problem 1.3 c
 
Hi,

I just revisited this problem again.

If I substitute w(t-1) with
\begin{bmatrix}w{_0}\\w{_1}\\w{_2}\end{bmatrix}

x(t-1) with
\begin{bmatrix}1\\x{_1}\\x{_2}\end{bmatrix}

I could get
||w(t)||{^2}
= ||w(t-1) + y(t-1)x(t-1)||{^2}
= ||w(t-1)||{^2} + y(t-1){^2}||x(t-1)||{^2} + 2y(t-1)w{^T}(t-1)x(t-1)

and then use the hint to get the answer.

However, the dimension of x and w can be more than 3. I just wonder whether there is a more generic proof.

Thanks in advance.


All times are GMT -7. The time now is 08:00 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, 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.