机器学习基石 作业三

机器学习基石 作业三

线性回归得到的映射函数HHH的性质问题。显然映射多次与映射一次效果一样。其它的可以根据HHH的性质，秩为d+1，显然不可逆。特征值的部分不是非常清楚，大概是根据I−HI-HI−H的迹等于N−(d+1)N-(d+1)N−(d+1)得到的。

3. PLA的error的上限。计算一下就知道结果。

4. 可微，显然。

5. 使用SGD法能够得到PLA的error。SGD法更新公式wt+1=wt−error的梯度w_{t+1} = w_{t}-error的梯度wt+1​=wt​−error的梯度。可以算出其中一个能够得出wt+1=wt+[[y!=wx]]yxw_{t+1} = w_{t}+[[y!=wx]]yxwt+1​=wt​+[[y!=wx]]yx的更新结果。做的时候思路不是很清晰，error与error的梯度有点混。

7. 6-10除了第9题之外都是编程题，代码如下：

import numpy as np def E(u,v):return np.exp(u)+np.exp(2*v)+np.exp(u*v)+u*u-2*u*v+2*v*v-3*u-2*v def gradU(func,u,v):return (func(u+0.0001,v)-func(u-0.0001,v))/0.0002def gradV(func,u,v):return (func(u,v+0.0001)-func(u,v-0.0001))/0.0002def update(N):u,v = 0,0for i in range(N):gu = gradU(E,u,v)gv = gradV(E,u,v)u = u-0.01*guv = v-0.01*gvreturn u,vdef newtonUpdate(N):u,v = 0,0for i in range(N):gu = gradU(E,u,v)gv = gradV(E,u,v)guu = gradU(lambda u,v:gradU(E,u,v),u,v)guv = gradU(lambda u,v:gradV(E,u,v),u,v)gvu = gradV(lambda u,v:gradU(E,u,v),u,v)gvv = gradV(lambda u,v:gradV(E,u,v),u,v)hession = np.mat([[guu,guv],[guv,gvv]])grad = np.array([[gu],[gv]])delta = hession.I * graddelta = delta.tolist()u = u-delta[0][0]v = v-delta[1][0]return u,vdef main6():gu = gradU(E,0,0)gv = gradV(E,0,0)print(gu,gv)def main7():u,v = update(5)print(E(u,v))def main8():u = 0v = 0b = E(u,v)gu = gradU(E,u,v)gv = gradV(E,u,v)guu = gradU(lambda u,v:gradU(E,u,v),u,v)guv = gradU(lambda u,v:gradV(E,u,v),u,v)gvu = gradV(lambda u,v:gradU(E,u,v),u,v)gvv = gradV(lambda u,v:gradV(E,u,v),u,v)print(guu/2,gvv/2,guv,gu,gv,b)def main10():u,v = 0,0u,v = newtonUpdate(5)print(E(u,v))if __name__ == '__main__':main6()main7()main8()main10()

这题需要注意，对应的系数不是直接等于求导的结果，二次项有一个0.5的系数，而uv有两项，加起来是1。emm这题卡了好久，怀疑人生。

9. 牛顿法的下降方向，不太懂，不过貌似是个基础问题，找了个链接。梯度下降法、牛顿法和拟牛顿法

10.

11. 有两个变量，它的2阶非线性映射之后的VC维是1+C42=71+C_{4}^{2}=71+C42​=7，因此对于6个点的情况是可以shatter的。不过稍微有点疑问，VC维是指最多可能shatter的点的数量，虽然是7但是不知道如何证明能够shatter这6个给定的点。线性的好说可以眼看，二次的不太明白怎么证明。

12. 这题比较有意思。把训练集映射到一个N维的0/1向量。也就是one-hot的形式。因此对于训练集之外的点映射后的x都是全0的向量，于是结果都是1，又因为实际的分布中有30%的结果是1，因此Eout=0.7E_{out}=0.7Eout​=0.7是没问题的。其他的选项，N个数据就映射了N维，很显然线性可分（每一维的系数等于对应结果+1或-1即可），因此其它选项都明白了。

13. 编程求解。直接使用numpy里的伪逆方法。代码如下：

import numpy as np import randomdef sign(v):if v > 0:return +1else:return -1def targetFunc(x1,x2):r = x1*x1+x2*x2-0.6return sign(r)def genData(N):xs = []ys = []for i in range(N):x1 = random.uniform(-1,1)x2 = random.uniform(-1,1)y = targetFunc(x1,x2)prob = random.uniform(0,1)if prob < 0.1:y = -yxs.append([1,x1,x2])ys.append([y])return np.mat(xs), np.array(ys)def trainLR(x,y):pseu_inv = np.linalg.pinv(x)w = pseu_inv*yreturn np.array(w)def errorRate(w,x,y):yHat = np.array(x*w)yHat = list(map(sign,yHat))y = list(map(lambda x: x[0],y))errorNum = np.sum(np.array(yHat) != np.array(y))return errorNum/len(y)def main():N = 1000errorSum = 0for i in range(N):x,y = genData(1000)w = trainLR(x,y)errorSum += errorRate(w,x,y)print("error in sample is",errorSum/N)if __name__ == '__main__':main()

先算出使用线性回归的结果，然后将题目中的系数代入数据集进行验证错误率最接近的即可。代码如下（代码是平均了线性回归结果的系数肉眼看最接近的，不严谨）：

import numpy as np import randomdef sign(v):if v > 0:return +1else:return -1def targetFunc(x1,x2):r = x1*x1+x2*x2-0.6return sign(r)def genData(N):xs = []ys = []for i in range(N):x1 = random.uniform(-1,1)x2 = random.uniform(-1,1)y = targetFunc(x1,x2)prob = random.uniform(0,1)if prob < 0.1:y = -yxs.append([1,x1,x2,x1*x2,x1*x1,x2*x2])ys.append([y])return np.mat(xs), np.array(ys)def trainLR(x,y):pseu_inv = np.linalg.pinv(x)w = pseu_inv*yreturn np.array(w)def errorRate(w,x,y):yHat = np.array(x*w)yHat = list(map(sign,yHat))y = list(map(lambda x: x[0],y))errorNum = np.sum(np.array(yHat) != np.array(y))return errorNum/len(y)def main():N = 1000# errorSum = 0# wsum = None# for i in range(N):#x,y = genData(1000)#w = trainLR(x,y)#if wsum is None:# wsum = w#else:# wsum += w#errorSum += errorRate(w,x,y)#if i%100 == 0:# print("iteration:",i+1)# print("error in sample is",errorSum/N)# print(wsum/N)errorSum = 0w = np.array([[-1],[-0.05],[0.08],[0.13],[1.5],[1.5]])print(w.shape)for i in range(N):x,y = genData(1000)errorSum += errorRate(w,x,y)if i%100 == 0:print("iteration:",i+1)print("error out of sample is",errorSum/N)if __name__ == '__main__':main()

代码也在上面，代入检验即可。

跟ppt一样，写下来假设函数产生数据集的联合概率，然后取ln加负号。

17. 上题结果求导即可。

18. 实现逻辑回归算法然后使用测试集进行检测即可。主要是numpy的使用，代码如下（代码已经是SGD的算法，对应更新的地方改一下就行）：

import numpy as npimport requestsimport randomdef getData(url):content = requests.get(url).contentcontent = content.decode('utf-8')x = []y = []content = content.split('\n')for line in content[:-1]:data = line.split(' ')y.append(int(data[-1]))x1 = data[1:-1]for i in range(len(x1)):x1[i] = float(x1[i])x.append([1]+x1)x = np.mat(x)y = np.array(y)return x,ydef sigmoid(s):return 1/(1+np.exp(-s))def hypo(w,x):return sigmoid(x*w)def gradientOne(w,x,y,i):res = hypo(w,-y[i]*x[i]).item()*(-y[i]*x[i].T)return np.array(res.tolist())def gradient(w,x,y):N = len(y)gSum = Nonefor i in range(N):if gSum is None:gSum = gradientOne(w,x,y,i)else:gSum += gradientOne(w,x,y,i)return gSum/N def logisticRegression(w,x,y):T = 2000eta = 0.001for i in range(T):#for index in range(len(x)):g = gradientOne(w,x,y,i%len(y))w = w - eta*gif i%100 == 0:print("iteration",i)return wdef sign(v):if v >= 0.5:return 1else:return -1def errorRate(w,x,y):yHat = hypo(w,x).tolist()yHat = list(map(lambda x:sign(x[0]),yHat))errorNum = np.sum(np.array(yHat) != np.array(y))return errorNum/len(y)def main():trainUrl = 'https://www.csie.ntu.edu.tw/~htlin/mooc/datasets/mlfound_algo/hw3_train.dat'testUrl = 'https://www.csie.ntu.edu.tw/~htlin/mooc/datasets/mlfound_algo/hw3_test.dat'trainX,trainY = getData(trainUrl)testX,testY = getData(testUrl)w0 = np.array([0]*trainX[0].size)w0 = w0.reshape(-1,1)w = logisticRegression(w0,trainX,trainY)print(w)errR = errorRate(w,testX,testY)print("out of sample error rate is",errR)if __name__ == '__main__':main()

运行即可。

20.