Machine Learning Foundations 作业二 Question 9 解法
自从发表了台大线上课程，Machine Learning Foundations作业一与作业二的某些题目的解法后，陆续接到许多朋友的要求，希望我提供更多题目的解法。当然，网路上有许可供参考，本人在做题目时，也的确参考了那些解法。只是有些解法对我来说是一步登天，对于问题的彻底了解帮助有限。花了一些时间了解之后，希望能用深入浅出的方式，把问题说清楚，答案讲明白。
这道题目是该课程作业二的第9题，其解答为D+1。接下来为各位朋友说明这道题目的解题过程。
首先，我们撇开sign不看，发现这是一个多项式的式子。我们先看D = 1的情况：
D = 1时，y = c0 + c1 * x ， 代表直线，可以改写成 y = s (x - a1) 。我们从上图可以看出，s和a1，这两个参数可以决定这条直线的样子。所以当D = 1时，VC dimension = 2
我们再来看D = 2：
D = 2时，此多项式为一元二次的曲线，我们把这个曲线改写成 y = s (x - a1) ( x - a2) 。从上图可以看出，s、a1、a2，这三个参数可以决定这条曲线的样子。所以当D = 2时，VC dimension = 3
最后，来看D = 3：
D = 3时，此多项式为一元三次的曲线，此曲线可以改写成 y = s (x - a1) ( x - a2) (x - a3) 。从上图可以看出，s、a1、a2、a3，这四个参数足以决定这条曲线的样子。所以当D =3时，VC dimension = 4。
我们可以检验一下，这种想法是否正确。拿D = 2，也就是若我们的Hypothesis为一元二次的曲线，那么它的VC dimension为多少？下图解释，N = 3代表有3个点要做分类，N = 4代表有4个点要做分类。分类的方法都是指定用一元二次的曲线。
先看N = 3：我们发现，一元二次曲线完全可以对所有情况做分类。共有2^3 = 8种情况。所以对于该hypothesis set H而言，在N = 3的情况下，此set的最大数量为mH(3)。
再看N = 4：有一种情况，想将4个点分为(+, -, +, -)，用一元二次曲线是不可行的，只能交由一元三次曲线做分类。如下图所示。
所以依照VC dimension的定义
dVC(H) = 3, for D = 2
推广之
dVC(H) = D + 1, for degree D
-Count