机器学习基石 作业三
机器学习基石 作业三
- 代入计算
- 线性回归得到的映射函数的性质问题。显然映射多次与映射一次效果一样。其它的可以根据的性质,秩为d+1,显然不可逆。特征值的部分不是非常清楚,大概是根据的迹等于得到的。
3. PLA的error的上限。计算一下就知道结果。
4. 可微,显然。
5. 使用SGD法能够得到PLA的error。SGD法更新公式。可以算出其中一个能够得出的更新结果。做的时候思路不是很清晰,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.0002
def gradV(func,u,v):
return (func(u,v+0.0001)-func(u,v-0.0001))/0.0002
def update(N):
u,v = 0,0
for i in range(N):
gu = gradU(E,u,v)
gv = gradV(E,u,v)
u = u-0.01*gu
v = v-0.01*gv
return u,v
def newtonUpdate(N):
u,v = 0,0
for 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 * grad
delta = delta.tolist()
u = u-delta[0][0]
v = v-delta[1][0]
return u,v
def 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 = 0
v = 0
b = 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,0
u,v = newtonUpdate(5)
print(E(u,v))
if __name__ == '__main__':
main6()
main7()
main8()
main10()
- 这题需要注意,对应的系数不是直接等于求导的结果,二次项有一个0.5的系数,而uv有两项,加起来是1。emm这题卡了好久,怀疑人生。
9. 牛顿法的下降方向,不太懂,不过貌似是个基础问题,找了个链接。梯度下降法、牛顿法和拟牛顿法
10.
11. 有两个变量,它的2阶非线性映射之后的VC维是,因此对于6个点的情况是可以shatter的。不过稍微有点疑问,VC维是指最多可能shatter的点的数量,虽然是7但是不知道如何证明能够shatter这6个给定的点。线性的好说可以眼看,二次的不太明白怎么证明。
12. 这题比较有意思。把训练集映射到一个N维的0/1向量。也就是one-hot的形式。因此对于训练集之外的点映射后的x都是全0的向量,于是结果都是1,又因为实际的分布中有30%的结果是1,因此是没问题的。其他的选项,N个数据就映射了N维,很显然线性可分(每一维的系数等于对应结果+1或-1即可),因此其它选项都明白了。
13. 编程求解。直接使用numpy里的伪逆方法。代码如下:
import numpy as np
import random
def sign(v):
if v > 0:
return +1
else:
return -1
def targetFunc(x1,x2):
r = x1*x1+x2*x2-0.6
return 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 = -y
xs.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*y
return 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
for 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 random
def sign(v):
if v > 0:
return +1
else:
return -1
def targetFunc(x1,x2):
r = x1*x1+x2*x2-0.6
return 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 = -y
xs.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*y
return 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 = 0
w = 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 np
import requests
import random
def getData(url):
content = requests.get(url).content
content = 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,y
def 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 = None
for 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 = 2000
eta = 0.001
for i in range(T):
#for index in range(len(x)):
g = gradientOne(w,x,y,i%len(y))
w = w - eta*g
if i%100 == 0:
print("iteration",i)
return w
def sign(v):
if v >= 0.5:
return 1
else:
return -1
def 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.