Three Linear Models

寫本文的目的主要是通過看他人的筆記加深印象以及理解難點(diǎn)。需要跟課堂看筆記的同學(xué)建議移步這里弄唧，課后習(xí)題的Python實(shí)現(xiàn)在這里候引。

注意點(diǎn)

PLA中分割線垂直于 $W$
Linear regression中向量求導(dǎo)
logistic regression中最大（極大）似然估計(jì)的概念<概率書p141>以及對(duì)分量求導(dǎo)澄干。

Three Linear Models

一柠傍、PLA/Pocket

感知機(jī)模型惧笛，就是當(dāng)特征加權(quán)和與閾值的差大于或等于0，則輸出h(x)=1拜效；當(dāng)特征加權(quán)和與閾值的差小于0，則輸出h(x)=-1侮腹，而我們的目的就是計(jì)算出權(quán)值w和閾值threshold使全部分類正確稻励。

題目：銀行貸款問題望抽，訓(xùn)練數(shù)據(jù)是客戶的n維資料和貸款與否

1. PLA

Hypothesis公式

公式

公式中 $x_{i}$ 表示每個(gè)貸款申請人的個(gè)人特征煤篙， $w_{i}$ 表示相對(duì)應(yīng)的個(gè)人信息的權(quán)重， $threshold$ 表示闕值苛茂。

sign函數(shù)

即當(dāng)特征加權(quán)和比threshold大時(shí)妓羊，h(x)為正（發(fā)放貸款）躁绸。
調(diào)整權(quán)重W

調(diào)整權(quán)重W

某次學(xué)習(xí)錯(cuò)誤將原本結(jié)果該為+1的 $y_n(t)$ 誤判成-1净刮，這代表 $w$ 與 $x$ 之間的角度太大硅则，所以我們透過 $w_t+1←w_t+(+1)x_{n}(t)$ 來將夾角減小抢埋，使未來學(xué)習(xí)到這點(diǎn)時(shí)能正確的判斷成+1。如此逐個(gè)檢查所有點(diǎn)穷吮，直到不存在判斷錯(cuò)誤的點(diǎn)為止饥努。

為什么分割線總是垂直與 $W$
$w?x =||w||?||x||?cos(θ)$ 當(dāng) $w$ 與 $x$ 的夾角 $θ$ 小于90°時(shí)結(jié)果為正（圖中的圈圈）酷愧，大于90°時(shí)結(jié)果為負(fù)（圖中的叉叉）。因此與夾角垂直的線自然就成了正與負(fù)的分水嶺乍迄。

核心代碼

    W=np.zeros(5)
    while True:
        iscompleted=True
        #arr為訓(xùn)練集
        for i in range(0,len(arr)):
            #所有的特徵值乘上相對(duì)的權(quán)重加起來大於某個(gè)設(shè)定的門檻時(shí)，就會(huì)回傳是褥伴，反之則否
            #將門檻值threshold轉(zhuǎn)換為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存在一個(gè)缺點(diǎn)重慢，那就是當(dāng) $X$ 不是線性可分的（例如存在噪音）似踱，PLA將不會(huì)停止稽煤。如下圖，PLA找不到一條線使所有點(diǎn)都正確狞洋。

非線性可分

這時(shí)就需要使用Pocket算法，即在調(diào)整過程中記錄犯更少錯(cuò)誤的庐橙，當(dāng)?shù)螖?shù)達(dá)到要求時(shí)，選取犯錯(cuò)個(gè)數(shù)最少的直線對(duì)應(yīng)的转培，即為我們最終想要得到的權(quán)重值浸须。

    while True:
        for i in range(0,len(arr)):
            #所有的特徵值乘上相對(duì)的權(quán)重加起來大於某個(gè)設(shè)定的門檻時(shí)邦泄，就會(huì)回傳是，反之則否
            #將門檻值threshold轉(zhuǎn)換為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:#調(diào)整達(dá)50次后結(jié)束
                break
        if count==50:
            break

二肌索、linear regression

題目：銀行貸款問題诚亚，訓(xùn)練數(shù)據(jù)是客戶的n維資料和貸款與否

1. 公式

Hypothesis

誤差衡量為平方差，損失函數(shù)：

損失函數(shù)

目標(biāo)求解使損失函數(shù)最小的闸准。

2. 求解

將損失函數(shù)轉(zhuǎn)換成矩陣運(yùn)算形式：

轉(zhuǎn)換過程

當(dāng) $X$ 為一維空間時(shí)夷家，損失函數(shù)如下圖：

函數(shù)圖

可以發(fā)現(xiàn)損失函數(shù)最小值位于“谷底”瘾英，即求解? $E_in=0$ (導(dǎo)函數(shù)為0)缺谴。
求? $E_{in}$ 耳鸯。

求導(dǎo)
求解 $w$
令? $E_{in}=0$ 县爬，解得 $w$ ，即為最終解： $w=(x^Tx)^{-1}x^Ty$
其中 $(x^Tx)^{-1}x^T$ 叫做矩陣X的偽逆（pseudo-inverse）察迟。注意此處輸入矩陣X在很少的情況下才是方陣（N=d+1時(shí)）耳高，這種偽逆矩陣的形式和方陣中的逆矩陣具有很多相似的性質(zhì)泌枪。

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隨機(jī)生成一個(gè)實(shí)數(shù)，它在 [x,y] 范圍內(nèi)
    #round返回浮點(diǎn)數(shù)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

題目：輸入訓(xùn)練集是病人的信息修壕，標(biāo)記是得病與否，要求目標(biāo)函數(shù)判斷得病的概率

1. 梯度下降

1.目標(biāo)函數(shù)

目標(biāo)函數(shù)

2.Logistic Hypothesis
風(fēng)險(xiǎn)分?jǐn)?shù)：

risk score

利用sigmoid函數(shù)將分?jǐn)?shù)轉(zhuǎn)化為0-1：

sigmoid

logistic regression:

損失函數(shù)
目標(biāo)函數(shù) $f(x)$ 形式轉(zhuǎn)換：

轉(zhuǎn)換
minimize $E_{in}(w)$
$E_{in}(w)$ 函數(shù)為連續(xù)、可微像棘、凹函數(shù)，因此其最小值在梯度為零時(shí)取得截歉。

對(duì)權(quán)值向量w的各個(gè)分量求解偏微分：

使 $?E_{in}(w)=0$ 有兩種情況：
①所有的 $θ(·) =0$ 瘪松，這就要求 $y_nw^tx_n$ 遠(yuǎn)大于0宵睦，即所有的 $y_n$ 和 $w^tx_n$ （score）都是同號(hào)墅诡，代表所有的 $w^t$ 都是好的，那么訓(xùn)練集D就是線性可分的烟馅，所以不適用于非線性可分的問題然磷。
②累加和為0。所以接下來是調(diào)整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. 隨機(jī)梯度下降

計(jì)算梯度過程中悦穿，每次的梯度計(jì)算包含一個(gè)連加业踢，是一個(gè)o(N)的時(shí)間復(fù)雜度知举，如果樣本量過大太伊，幾乎是一個(gè)不可完成過程。如果是在線學(xué)習(xí)锰提，訓(xùn)練樣本無法一次給清，同樣無法代入上面公式边坤。我們把1/N的連加換成一個(gè)隨機(jī)選擇點(diǎn)的過程谅年，隨機(jī)梯度值可以看做真實(shí)的梯度值加上一個(gè)噪音，使用隨機(jī)梯度取代真實(shí)梯度做梯度下降的算法稱作隨機(jī)梯度下降（stochastic gradient descent）旺订，簡稱SGD超燃。這種替代的理論基礎(chǔ)是在迭代次數(shù)足夠多的情況下，平均的隨機(jī)梯度和平均的真實(shí)梯度相差不大樱调。

SDG中的 $x_n$ 為隨機(jī)選擇的一個(gè)點(diǎn)洽瞬。
SGD是大錯(cuò)大更新，小錯(cuò)小更新（0~1之間的值）菩颖；PLA是有錯(cuò)就更新为障，無錯(cuò)不更新；兩者其實(shí)是類似的呻右。關(guān)于迭代次數(shù)和步長（學(xué)習(xí)速率）的選擇：因?yàn)闊o法真正確定梯度為0的地方鞋喇，所以確定一個(gè)t很困難，通常做法是選擇一個(gè)足夠大的迭代次數(shù)t落塑；步長的經(jīng)驗(yàn)算法是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