写本文的目的主要是通过看他人的笔记加深印象以及理解难点。需要跟课堂看笔记的同学建议移步这里，课后习题的Python实现在这里。
注意点
- PLA中分割线垂直于
- Linear regression中向量求导
-
logistic regression中最大（极大）似然估计的概念<概率书p141>以及对分量求导。
Three Linear Models
一、PLA/Pocket
感知机模型，就是当特征加权和与阈值的差大于或等于0，则输出h(x)=1；当特征加权和与阈值的差小于0，则输出h(x)=-1，而我们的目的就是计算出权值w和阈值threshold使全部分类正确。
- 题目：银行贷款问题，训练数据是客户的n维资料和贷款与否
1. PLA
- Hypothesis公式
公式
公式中表示每个贷款申请人的个人特征，
表示相对应的个人信息的权重，
表示阙值。
即当特征加权和比threshold大时，h(x)为正（发放贷款）。sign函数 - 调整权重W
某次学习错误将原本结果该为+1的调整权重W误判成-1，这代表
与
之间的角度太大，所以我们透过
来将夹角减小，使未来学习到这点时能正确的判断成+1。如此逐个检查所有点，直到不存在判断错误的点为止。
- 为什么分割线总是垂直与
当
小于90°时结果为正（图中的圈圈），大于90°时结果为负（图中的叉叉）。因此与夹角垂直的线自然就成了正与负的分水岭。
- 核心代码
W=np.zeros(5)
while True:
iscompleted=True
#arr为训练集
for i in range(0,len(arr)):
#所有的特徵值乘上相對的權重加起來大於某個設定的門檻時，就會回傳是，反之則否
#将门槛值threshold转换为w0*(+1),所以X的第一列多一列1
X=np.ones(5)
X[1:]=arr[i,:-1].copy()
g=arr[i,-1]
Y=np.dot(W,X.reshape(5,1))[0]#matrix multiply
if np.sign(Y)*np.sign(g)==1:
continue
else:
count+=1
iscompleted=False
#print(W,"+",g,"*",X)
W=W+g*X
if iscompleted:
break
2. Pocket
PLA存在一个缺点，那就是当不是线性可分的（例如存在噪音），PLA将不会停止。如下图，PLA找不到一条线使所有点都正确。
非线性可分
这时就需要使用Pocket算法，即在调整过程中记录犯更少错误的，当迭代次数达到要求时，选取犯错个数最少的直线对应的，即为我们最终想要得到的权重值。
while True:
for i in range(0,len(arr)):
#所有的特徵值乘上相對的權重加起來大於某個設定的門檻時，就會回傳是，反之則否
#将门槛值threshold转换为w0*(+1),所以X的第一列多一列1
X=np.ones(5)
X[1:]=arr[i,:-1].copy()
g=arr[i,-1]
Y=np.dot(W,X.reshape(5,1))[0]#matrix multiply
if np.sign(Y)*np.sign(g)!=1:
count+=1
W=W+g*X
err=0
for j in range(0,len(arr)):
XX=np.ones(5)
XX[1:]=arr[j,:-1].copy()
gg=arr[j,-1]
YY=np.dot(W,XX.reshape(5,1))[0]#matrix multiply
if np.sign(YY)*np.sign(gg)!=1:
err+=1
if err<pocket_err:
pocket_err=err
pocket_wei=W.copy()
if count==50:#调整达50次后结束
break
if count==50:
break
二、linear regression
- 题目：银行贷款问题，训练数据是客户的n维资料和贷款与否
1. 公式
Hypothesis
误差衡量为平方差，损失函数：
损失函数
目标求解使损失函数最小的。
2. 求解
- 将损失函数转换成矩阵运算形式：转换过程
当为一维空间时，损失函数如下图：
函数图
可以发现损失函数最小值位于“谷底”，即求解∇(导函数为0)。
- 求∇
。
求导 - 求解
令∇，解得
其中叫做矩阵X的伪逆（pseudo-inverse）。注意此处输入矩阵X在很少的情况下才是方阵（N=d+1时），这种伪逆矩阵的形式和方阵中的逆矩阵具有很多相似的性质。
2. 核心代码
# target function f(x1, x2) = sign(x1^2 + x2^2 - 0.6)
def target_function(x1, x2):
if (x1 * x1 + x2 * x2 - 0.6) >= 0:
return 1
else:
return -1
# create train_set
def training_data_with_random_error(num=1000):
features = np.zeros((num, 3))
labels = np.zeros((num, 1))
#random.uniform随机生成一个实数，它在 [x,y] 范围内
#round返回浮点数x的四舍五入值
points_x1 = np.array([round(random.uniform(-1, 1), 2) for i in range(num)])
points_x2 = np.array([round(random.uniform(-1, 1), 2) for i in range(num)])
for i in range(num):
# create random feature
features[i, 0] = 1
features[i, 1] = points_x1[i]
features[i, 2] = points_x2[i]
labels[i] = target_function(points_x1[i], points_x2[i])
# choose 10% error labels
if i <= num * 0.1:
if labels[i] < 0:
labels[i] = 1
else:
labels[i] = -1
return features, labels
def error_rate(features, labels, w):
wrong = 0
for i in range(len(labels)):
if np.dot(features[i], w) * labels[i, 0] < 0:
wrong += 1
return wrong / (len(labels) * 1.0)
def linear_regression_closed_form(X, Y):
"""
linear regression:
model : g(x) = Wt * X
strategy : squared error
algorithm : close form(matrix)
result : w = (X.T·X)^-1·X.T·Y
林老师上课讲的公式
"""
#np.linalg.inv()：矩阵求逆
return np.linalg.inv(np.dot(X.T, X)).dot(X.T).dot(Y)
if __name__ == '__main__':
# 13
error_rate_array = []
for i in range(1000):
(features, labels) = training_data_with_random_error(1000)
w13 = linear_regression_closed_form(features, labels)
error_rate_array.append(error_rate(features, labels, w13))
三、logistic regression
- 题目：输入训练集是病人的信息，标记是得病与否，要求目标函数判断得病的概率
1. 梯度下降
1.目标函数
目标函数
2.Logistic Hypothesis
风险分数：
risk score
利用sigmoid函数将分数转化为0-1：
sigmoid
logistic regression:
- 损失函数
目标函数形式转换：
转换
- minimize
函数为连续、可微、凹函数，因此其最小值在梯度为零时取得。
对权值向量w的各个分量求解偏微分：使有两种情况：
①所有的，这就要求
远大于0，即所有的
和
（score）都是同号，代表所有的
都是好的，那么训练集D就是线性可分的，所以不适用于非线性可分的问题。
②累加和为0。所以接下来是调整w使 - 核心代码
# gradient descent
def gradient_descent(X, y, w):
# -YnWtXn
tmp = -y * (np.dot(X, w))
# θ(-YnWtXn) = exp(tmp)/1+exp(tmp)
# weight_matrix = np.array([math.exp(_)/(1+math.exp(_)) for _ in tmp]).reshape(len(X), 1)
weight_matrix = np.exp(tmp) / ((1 + np.exp(tmp)) * 1.0)
gradient = 1 / (len(X) * 1.0) * (sum(weight_matrix * -y * X).reshape(len(w), 1))
return gradient
# fit model
def fit(self, X, y, Eta=0.001, max_iteration=2000, sgd=False):
# ∂E/∂w = 1/N * ∑θ(-YnWtXn)(-YnXn)
self.__w = np.zeros((len(X[0]), 1))
for i in range(max_iteration):
self.__w = self.__w - Eta * gradient_descent(X, y, self.__w)
2. 随机梯度下降
- 计算梯度过程中，每次的梯度计算包含一个连加，是一个o(N)的时间复杂度，如果样本量过大，几乎是一个不可完成过程。如果是在线学习，训练样本无法一次给清，同样无法代入上面公式。我们把1/N的连加换成一个随机选择点的过程，随机梯度值可以看做真实的梯度值加上一个噪音，使用随机梯度取代真实梯度做梯度下降的算法称作随机梯度下降（stochastic gradient descent），简称SGD。这种替代的理论基础是在迭代次数足够多的情况下，平均的随机梯度和平均的真实梯度相差不大。
SDG中的为随机选择的一个点。
SGD是大错大更新，小错小更新（0~1之间的值）；PLA是有错就更新，无错不更新；两者其实是类似的。关于迭代次数和步长（学习速率）的选择：因为无法真正确定梯度为0的地方，所以确定一个t很困难，通常做法是选择一个足够大的迭代次数t；步长的经验算法是0.1。
2.核心代码
# gradient descent
def stochastic_gradient_descent(X, y, w):
# -YnWtXn
tmp = -y * (np.dot(X, w))
# θ(-YnWtXn) = exp(tmp)/1+exp(tmp)
# weight = math.exp(tmp[0])/((1+math.exp(tmp[0]))*1.0)
weight = np.exp(tmp) / ((1 + np.exp(tmp)) * 1.0)
gradient = weight * -y * X
return gradient.reshape(len(gradient), 1)
# fit model
def fit(self, X, y, Eta=0.001, max_iteration=2000, sgd=False):
# ∂E/∂w = 1/N * ∑θ(-YnWtXn)(-YnXn)
self.__w = np.zeros((len(X[0]), 1))
index = 0
for i in range(max_iteration):
if (index >= len(X)):
index = 0
self.__w = self.__w - Eta * stochastic_gradient_descent(np.array(X[index]), y[index], self.__w)
index += 1
