Three Linear Models

2019-08-14 本文已影响0人 SwordIng

写本文的目的主要是通过看他人的笔记加深印象以及理解难点。需要跟课堂看笔记的同学建议移步这里，课后习题的Python实现在这里。

注意点

PLA中分割线垂直于 $W$
Linear regression中向量求导
logistic regression中最大（极大）似然估计的概念<概率书p141>以及对分量求导。

Three Linear Models

一、PLA/Pocket

感知机模型，就是当特征加权和与阈值的差大于或等于0，则输出h(x)=1；当特征加权和与阈值的差小于0，则输出h(x)=-1，而我们的目的就是计算出权值w和阈值threshold使全部分类正确。

题目：银行贷款问题，训练数据是客户的n维资料和贷款与否

1. PLA

Hypothesis公式
公式
公式中 $x_{i}$ 表示每个贷款申请人的个人特征， $w_{i}$ 表示相对应的个人信息的权重， $threshold$ 表示阙值。
sign函数即当特征加权和比threshold大时，h(x)为正（发放贷款）。
调整权重W
调整权重W 某次学习错误将原本结果该为+1的 $y_n(t)$ 误判成-1，这代表 $w$ 与 $x$ 之间的角度太大，所以我们透过 $w_t+1←w_t+(+1)x_{n}(t)$ 来将夹角减小，使未来学习到这点时能正确的判断成+1。如此逐个检查所有点，直到不存在判断错误的点为止。

为什么分割线总是垂直与 $W$
$w⋅x =||w||⋅||x||⋅cos(θ)$ 当 $w$ 与 $x$ 的夹角 $θ$ 小于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存在一个缺点，那就是当 $X$ 不是线性可分的（例如存在噪音），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. 求解

将损失函数转换成矩阵运算形式：转换过程
当 $X$ 为一维空间时，损失函数如下图：函数图
可以发现损失函数最小值位于“谷底”，即求解∇ $E_in=0$ (导函数为0)。
求∇ $E_{in}$ 。
求导
求解 $w$
令∇ $E_{in}=0$ ，解得 $w$ ，即为最终解： $w=(x^Tx)^{-1}x^Ty$
其中 $(x^Tx)^{-1}x^T$ 叫做矩阵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:

损失函数
目标函数 $f(x)$ 形式转换：转换
minimize $E_{in}(w)$
$E_{in}(w)$ 函数为连续、可微、凹函数，因此其最小值在梯度为零时取得。对权值向量w的各个分量求解偏微分：使 $∇E_{in}(w)=0$ 有两种情况：
①所有的 $θ(·) =0$ ，这就要求 $y_nw^tx_n$ 远大于0，即所有的 $y_n$ 和 $w^tx_n$ （score）都是同号，代表所有的 $w^t$ 都是好的，那么训练集D就是线性可分的，所以不适用于非线性可分的问题。
②累加和为0。所以接下来是调整w使 $E_{in}$ 变小。
核心代码

# 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中的 $x_n$ 为随机选择的一个点。
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