LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 3 - The Linear Model (http://book.caltech.edu/bookforum/forumdisplay.php?f=110)
-   -   Exercise 3.15 (http://book.caltech.edu/bookforum/showthread.php?t=4408)

 xuewei4d 09-06-2013 03:16 PM

Exercise 3.15

I have a question about (b)

(a) since all x are mapped onto a line. A perceptron cannot generate all separations for 3 data points. But it works for 2 data points. Therefore d_vc (H_k) = 2.

(b) Suppose N data points have d bits. In order to let one perceptron generates all 2^N separations, we could let every separations shows up in one dimension, i.e. one bit. Since one half of separations equals another half, i.e. the separation where the first data point is separated from others could be represented as 0 1 1 1 ... , or 1 0 0 0 ... . Therefore
[ math ] 2^N/2 \le d [ /math ]
i.e.
[ math ] d_vc \le \log_2d + 1 [/math]

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

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