簡單易學(xué)的機器學(xué)習(xí)算法—Rosenblatt感知機的對偶解法

一、Rosenblatt感知機回顧
    在博文“簡單易學(xué)的機器學(xué)習(xí)算法——Rosenblatt感知機”中介紹了Rosenblatt感知機的基本概念。Rosenblatt感知機是針對線性可分問題的二分類算法。通過構(gòu)造分離超平面將正類和負類區(qū)分開。構(gòu)造了如下的輸入空間到輸出空間的函數(shù)：

其中，w為權(quán)重，b為偏置。為符號函數(shù)：

求解這個函數(shù)的重點就是求解函數(shù)中的參數(shù)：和。Rosenblatt感知機通過構(gòu)造損失函數(shù)，并求得使得這樣的損失函數(shù)達到最小時的w和b。
    其中，為：

這里的為所有誤分類的點的集合。我們的目標是求得損失函數(shù)的最小值：。
    通過梯度下降法(詳細請見“簡單易學(xué)的機器學(xué)習(xí)算法——Rosenblatt感知機”)，我們得到了w和b的更新公式：


其中，為學(xué)習(xí)率。
二、Rosenblatt感知機的對偶形式
    對偶形式的基本想法是，將w和b表示為實例的線性組合的形式，通過求解其系數(shù)而求得。
    通過上面的的更新公式，我們發(fā)現(xiàn)，是一個累加的過程。如果令，則可以表示為：
其中，。
    此時的感知機模型就變?yōu)椋?img src="/uploadfile/image/20170321/20170321210647_36238.png" alt="" />
三、算法流程
初始化，
選擇誤分類數(shù)據(jù)點，即，更新a和b

直到?jīng)]有誤分類的點，否則重復(fù)步驟2
計算出
四、實驗的仿真
    利用博文“簡單易學(xué)的機器學(xué)習(xí)算法——Rosenblatt感知機”中的數(shù)據(jù)集，原始數(shù)據(jù)集如下圖所示：

(原始數(shù)據(jù)點)

MATLAB代碼
[plain] view plain copy 在CODE上查看代碼片派生到我的代碼片
%% Rosenblatt感知機的對偶解法  
clear all;  
clc;  
 
%讀入數(shù)據(jù)  
x=[3,3;4,3;1,1];  
y=[1;1;-1];  
[m,n] = size(x);%取得數(shù)據(jù)集的大小  
 
%% 畫出原始的點  
hold on  
axis([0 5 0 5]);%axis一般用來設(shè)置axes的樣式，包括坐標軸范圍，可讀比例等  
for i = 1:m  
    plot(x(i,1),x(i,2),'.');  
end  
 
%% 初始化  
alpha = zeros(1,m);  
b = 0;  
yita = 1;%學(xué)習(xí)率  
gram = zeros(m,m);  
 
%% 計算Gram矩陣  
for i = 1:m  
    for j = 1:m  
        gram(i,j)=x(i,:)*x(j,:)';  
    end  
end  
 
%% 更新  
for i = 1:m  
    tmp = 0;  
    for j = 1:m  
        tmp = tmp + alpha(j)*y(j)*gram(i,j);  
    end  
    tmp = tmp + b;  
    tmp = y(i)*tmp;  
    if tmp <= 0  
        alpha(i) = alpha(i)+yita;  
        b = b + y(i);  
    end  
end  
% 要使得數(shù)據(jù)集中沒有誤分類的點  
flag = 0;%標志位，用于標記有沒有誤分類的點  
i = 1;  
while flag~=1  
    while i <= 3  
        tmp = 0;  
        for j = 1:m  
            tmp = tmp + alpha(j)*y(j)*gram(i,j);  
        end  
        tmp = tmp + b;  
        tmp = y(i)*tmp;  
        if tmp <= 0  
            alpha(i) = alpha(i)+yita;  
            b = b + y(i);  
            i = 1;%重置i  
            break;  
        else  
            i = i+1;  
        end  
        if i == 4  
            flag = 1;  
        end  
    end  
end  
 
%% 重新計算w和b  
for i = 1:m  
    x_new(i,:) = x(i,:) * y(i);  
end  
w = alpha * x_new;  
 
%% 畫出分隔線  
x_1 = (0:3);  
y_1 = (-b-w(1,1)*x_1)./w(1,2);  
plot(x_1,y_1);  

最終的分離超平面：

(最終分離超平面)