1.感知機模型

1.1感知機定義

假設輸入空間（特征空間）是,輸出空間是,輸入表示實例的特征向量，對應于輸入空間特征空間）的點盒音，輸出表示實例的類別表鳍。由輸入空間到輸出空間的如下函數：

稱為感知機，其中和稱為感知機模型參數祥诽， 叫做權值（weights）或權值向量(weight vector）譬圣，叫做偏置，表示和雄坪。
感知機有如下幾何解釋厘熟，線性方程：

對應于特征空間的一個超平面,其中是超平面的法向量，是超平面的截距。這個超平面將特征空間劃分為兩個部分绳姨，位于兩部分的點就被劃分為正登澜、負兩類，即：
（1）若就缆，則 為正例,
（2）若帖渠，則 為負例,

2.感知機學習策略

2.1 數據集的線性可分性

給定一個數據集,其中 ,,，如果存在某個超平面:

能夠將數據集的正實例點和負實例點完全正確的劃分到超平面的兩側竭宰，即對所有的的實例,有,對所有的的實例空郊，有,則稱數據集為線性可分數據集（linearly separable data set),否則稱為不可分數據集。

2.2感知機的學習策略

損失函數的一個自然選擇是誤分類點的總數切揭，但是這樣的損失函數不是的連續(xù)可導函數狞甚，不容易優(yōu)化。損失函數的另一個選擇是誤分類點到平面的總距離廓旬。
輸入空間中一個點到超平面的距離是：

若某個點被誤分類哼审，即：
（1）為正例，但,
（2）為負例,但孕豹，
綜合考慮涩盾，即：

因此，每個誤分類點到超平面的距離：

假設超平面的誤分類點的集合為励背，那么所有的誤分類點到超平面的總距離為：

由于是常量春霍，不考慮該常量，就可以得到感知機的損失函數：

2.3 感知機學習算法

2.3.1 感知機學習算法的原始形式

目標函數：

求解：梯度下降算法
感知機學習算法是誤分類驅動的叶眉，具體采用梯度下降算法（stochastic gradient descent).首先址儒，任選一個超平面，然后用梯度下降法不斷的極小化目標函數衅疙。極小化的過程不是一次性使用中所有的點莲趣，而是每次只使用一個誤分類點進行梯度下降，當沒有誤分類點時饱溢，即找到想要的超平面.

假設誤分類點的集合是固定的喧伞，那么損失函數的梯度：


當前正遍歷到誤分類點,對進行更新，過程如下：

其中 是步長理朋，在統計學習中又稱為學習率絮识。這樣，通過迭代可以期待損失函數不斷減小嗽上，直到為0.

算法2.1（感知機學習算法的原始形式）###

輸入：數據集,其中 ,,次舌，學習率
輸出：,感知機模型
(1)選取初值
(2)在訓練數據集中，選取數據
(3)如果:


(4)轉至(2)兽愤，直到訓練集中彼念，沒有誤分類點挪圾。

實例（《統計學習方法》例2.1）：
代碼如下：

import numpy as np

# 計算y值
def cacl_y(w, x, b):
    # print(w)
    # print(w.shape)
    # print(x)
    # print(x.shape)
    return np.sign(np.matmul(np.transpose(w), x) + b)

# 感知機計算過程
def perceptron(data_coord, data_label):
    # 0. 初始化參數:w,b, learning_rate
    learning_rate = 1
    w_star = np.zeros(shape=data_coord[0].shape) #zeros
    b_star = 0

    #1.開啟更新w，b的循環(huán):
    # 假設沒有不可分的數據逐沙，當全部數據分類正確時哲思，停止循環(huán)
    while True:
        count = 0;
        for i in range(len(data_coord)):
            # 2.1 對每個數據，查看分類是否錯誤
            x = data_coord[i]
            y_ = data_label[i]
            y = cacl_y(w_star, x, b_star)
            print("y_ = ", y_)
            print("y = ", y)
            print("\n\n")
            # 2.2 若分類錯誤(不大于0)吩案，更新w棚赔，b
            if y * y_ <= 0:  # update w,b
                w_star += learning_rate * y_ * x
                b_star += learning_rate * y_
                print("w_star = ",w_star)
                print("b_star = ",b_star)

            # 2.2 分類正確，對分類正確的數據個數 計數
            else:
                print("count = ", count)
                count += 1
            print("One Circle Again!")
        print("After going through all data, count = ", count)

        # 3.1 對所有數據分類正確徘郭，stop circle
        if count == len(data_label):
            print("\n\n")
            break;
        # 3.2 否則靠益，重啟 遍歷數據過程
        else:
            count = 0;
    # 4.結束：輸出 w b
    print("w_star = ", w_star)
    print("b_star = ", b_star)

# 準備3組測試數據，2個正例残揉， 1個負例
data_coord = np.asarray(((3, 3), (4, 3), (1, 1)))
data_label = np.asarray((1, 1, -1))
# start perceptron
perceptron(data_coord, data_label)

2.3.2 感知機學習算法的對偶形式

對偶形式的基本思想是胧后，將和表示在實例和標記的線性組合的形式，通過求解其系數求得和.不失一般性抱环，在上一個算法中壳快，將和設置為0，對于誤分類點,通過：


逐步修改和,設修改次镇草，則和a關于的增量分別是和,其中,這樣眶痰，經過學習之后，最終學習到的和可以表示如下：


其中梯啤，

算法2.2 （感知機學習算法的對偶形式）

輸入：數據集,其中 ,,凛驮，學習率
輸出：,感知機模型
(1)
(2)訓練集中選取數據
(3)如果：


(4)轉至(2)，直到沒有誤分類的數據条辟。

案例2.2：

import numpy as np

def perceptron_dual(x_input,y_input,gram):
    alpha_star = np.zeros(y_input.shape[0]) # alpha矩陣,x_input為n行矩陣
    b_star     = 0
    learning_rate = 1
    classification_right_count = 0 # 正確分類計數
    while True:
        for i in range(x_input.shape[0]):
            y = y_input[i]
            # 判斷是否滿足條件
            value = (np.sum(gram[i]*(alpha_star*y_input)) + b_star)
            if y*value <= 0:
                alpha_star[i] += learning_rate
                b_star += y
                print("update , alpha =", alpha_star)
                print("update , b_star = ",b_star)
            else:
                classification_right_count += 1
        # 若都已經分類正確，則退出
        if classification_right_count >= y_input.shape[0]: # y_input,行
            print("end, alpha = ",alpha_star)
            print("end, b_star = " , b_star)
            break
        # 否則宏胯，繼續(xù)循環(huán)
        else:
            classification_right_count = 0

# 1.準備數據
data_coord = np.asarray(((3, 3), (4, 3), (1, 1)))
data_label = np.asarray((1, 1, -1))
# 2.計算gram矩陣
x = np.asarray([data_coord[0],data_coord[1],data_coord[2]])
gram = np.matmul(x,x.T)
print("gram = ",gram)
# 3.感知機 對偶形式求解
perceptron_dual(data_coord,data_label,gram)

參考與致謝：
[1]《統計學習方法》
[2]感知機算法原理與實現
[3]WenDesi/lihang_book_algorithm