简介
50年代末 F.Rosenblatt提出感知器算法。线性分类器的设计就是利用训练样本来计算线性函数的权向量
问题
设有两类问题的判别函数
g(X)=w1x1+w2x2+w3=0<script type="math/tex" id="MathJax-Element-1">g(X)=w_1x_1+w_2x_2+w_3=0</script>
训练样本XA,XB∈ω1, XC,XD∈ω2则
g(XA)>0,g(XB)>0<script type="math/tex" id="MathJax-Element-2">g(XA)>0, g(XB)>0</script>
g(XC)<0,g(XD)<0<script type="math/tex" id="MathJax-Element-3">g(XC)<0 ,g(XD)<0</script>
即:
WX>0<script type="math/tex" id="MathJax-Element-4"> W X > 0</script>
其中:
权向量
各样本特征向量的增1矩阵
该线性联立不等式只对线性可分问题有解,且是多解,因而只有按不同条件取最优解
赏-罚训练算法是一个迭代过程:
1)取权向量W(1)为任一初始值;
2)用训练集X对W进行迭代,在第k步
3)如Xk∈ ω1 且 Wt(k)X(k) ≤ 0
如Xk∈ ω2 且 Wt(k)X(k) ≥ 0。则惩罚:
W(k+1)=W(k)+f(X)
直之无惩罚
#即要设计一个f(X)随着迭代达到最小
确定f(X)的感知器算法的梯度法,是使得f(X)越迭代越小最后收敛为“0”(梯度下降法)
设f(X)是向量X=(x1,x2…xn)<script type="math/tex" id="MathJax-Element-5">X=(x_1,x_2…x_n)</script>的函数,其梯度向量为
它的方向指向自变量(x1,x2…xn)增大时函数f(X)最大增大率方向,反之,负梯度指向f的最陡下降方向。
F.Rosenblett 提出的准则函数
J(W,X)=C1(|WtX|?WtX)<script type="math/tex" id="MathJax-Element-6">J(W,X)=C_1(|W_t X|-W_t X)</script>
W(k+1)=W(k)?C2▽J<script type="math/tex" id="MathJax-Element-7">W(k+1)=W(k)-C_2▽ J </script> C2为有助收敛的校正系数<script type="math/tex" id="MathJax-Element-8">C_2为有助收敛的校正系数</script>
这样把求线性不等式组转化为一个使函数J极小化,也就是使▽J=0<script type="math/tex" id="MathJax-Element-9">▽J=0</script>。
其中
公式表示:
注意
原不等式是对第二类样本的特征向量引如符号后得到的,如不引入负号,则算法为:
如 Xk∈ω1且Wt(k)X(k)>0或<script type="math/tex" id="MathJax-Element-10">X_k∈ω_1 且 W_t(k)X(k) > 0 或</script>
Xk∈ω2且Wt(k)X(k)<0<script type="math/tex" id="MathJax-Element-11">X_k∈ω_2 且 W_t(k)X(k) < 0 </script>
则不需要修正 反之,须予以“惩罚”:
若 Xk∈ω1且Wt(k)X(k)<=0<script type="math/tex" id="MathJax-Element-12">X_k∈ω_1 且 W_t(k)X(k) <= 0 </script>
则 W(k+1)=W(k)+CX(k)<script type="math/tex" id="MathJax-Element-13">W(k+1)=W(k)+CX(k)</script>
若 Xk∈ω2且Wt(k)X(k)>=0<script type="math/tex" id="MathJax-Element-14">X_k∈ω_2 且 W_t(k)X(k) >= 0 </script>
则 W(k+1)=W(k)?CX(k)<script type="math/tex" id="MathJax-Element-15">W(k+1)=W(k)-CX(k)</script>
例子
例:有4个训练样本如下:
ω1类: (0,0),(0,1)
ω1类: (1,0),(1,1)
试用感知器算法求其判别函数。
解:特征向量的增1矩阵
X(1)=(001)t,X(2)=(011)t<script type="math/tex" id="MathJax-Element-16">X(1)=(0 0 1)^t, X(2)=(0 1 1)^t</script>
X(3)=(101)t,X(4)=(111)t<script type="math/tex" id="MathJax-Element-17"> X(3)=(1 0 1)^t, X(4)=(1 1 1)^t</script>
取 C=1,Wt(1)=(000)<script type="math/tex" id="MathJax-Element-18">C=1, W^t(1)=(0 0 0)</script>
第一次迭代
输入样本1
因W(1)∈ω1<script type="math/tex" id="MathJax-Element-19">W(1)∈ω_1</script>类, Wt(1)X(1)≯0<script type="math/tex" id="MathJax-Element-20">W^t(1)X(1)≯0</script>,要受惩罚
输入样本2
因W(2)∈ω1<script type="math/tex" id="MathJax-Element-21">W(2)∈ω_1</script>类, W^t(1)X(1)>0,不惩罚
输入样本3
因W(3)∈ω2类,Wt(3)X(3)?0<script type="math/tex" id="MathJax-Element-22">因W(3)∈ω_2类, W^t(3)X(3)〉0</script>,要受惩罚
输入样本4
因W(4)∈ω2类,Wt(4)X(4)?0,不惩罚<script type="math/tex" id="MathJax-Element-23">因W(4)∈ω_2类, W^t(4)X(4)〈0,不惩罚</script>
由于W(1),W(2),W(3),W(4)未能收敛,继续迭代,这时
X(5)=X(1);X(6)=X(2)<script type="math/tex" id="MathJax-Element-24">X(5)=X(1); X(6)=X(2)</script>
X(7)=X(3);X(7)=X(4)<script type="math/tex" id="MathJax-Element-25"> X(7)=X(3); X(7)=X(4)</script>
再输入4个样本进行计算
Wt(5)X(5)=0,惩罚,W(6)=W(5)+X(5)=(?101)t<script type="math/tex" id="MathJax-Element-26">W^t(5)X(5)=0, 惩罚,W(6)=W(5)+X(5)=(-1 0 1^)t</script>
Wt(6)X(6)=1, W(7)=W(6)=(?101)t<script type="math/tex" id="MathJax-Element-27">W^t(6)X(6)=1, W(7)=W(6)=(-1 0 1)^t</script>
Wt(7)X(7)=0,惩罚,W(8)=W(7)?X(7)=(?200)t<script type="math/tex" id="MathJax-Element-28">W^t(7)X(7)=0, 惩罚,W(8)=W(7)-X(7)=(-2 0 0)^t</script>
Wt(8)X(8)=?2, W(9)=W(8)=(?200)t<script type="math/tex" id="MathJax-Element-29">W^t(8)X(8)=-2, W(9)=W(8)=(-2 0 0)^t</script>
仍未收敛,再用4个原始样本进行迭代,这时
X(9)=X(1),X(10)=X(2),X(11)=X(3),X(12)=X(4)<script type="math/tex" id="MathJax-Element-30">X(9)=X(1),X(10)=X(2),X(11)=X(3),X(12)=X(4)</script>
迭代结果:
Wt(9)X(9)=0 惩罚 W(10)=W(9)+X(9)=(?201)t<script type="math/tex" id="MathJax-Element-31">Wt(9)X(9)=0 惩罚 W(10)=W(9)+X(9)=(-2 0 1)t</script>
Wt(10)X(10)=1 W(11)=W(10)=(?201)t<script type="math/tex" id="MathJax-Element-32">Wt(10)X(10)=1 W(11)=W(10)=(-2 0 1)t</script>
Wt(11)X(11)=?1 W(12)=W(11)=(?201)t<script type="math/tex" id="MathJax-Element-33">Wt(11)X(11)=-1 W(12)=W(11)=(-2 0 1)t</script>
Wt(12)X(12)=?1 W(13)=W(12)=(?201)t<script type="math/tex" id="MathJax-Element-34">Wt(12)X(12)=-1 W(13)=W(12)=(-2 0 1)t</script>
此时X(2),X(3),X(4)分类全部正确,再检查一下X(1)的分类
收敛,结束
g(X)=?2x1+1=0<script type="math/tex" id="MathJax-Element-35">g(X)=-2x_1+1=0</script>
作业
以下述两类模式为样本,用matlab实现感知器算法求判别函数:ω1:(000)t,(100)t,(101)t,(110)t;ω2:(001)t,(011)t,(010)t,(111)t.且令W(1)=(?1–2–20)t,C=1.<script type="math/tex" id="MathJax-Element-36">ω_1:{(0 0 0)^t,(1 0 0)^t,(1 0 1)^t,(1 1 0)^t}; ω_2:{(0 0 1)^t,(0 1 1)^t,(0 1 0)^t,(1 1 1)^t}.且令W(1)=(-1 –2 –2 0)^t, C=1.</script>
clc
clear
X = [ 0 0 0 1;
1 0 0 1;
1 0 1 1;
1 1 0 1;
0 0 -1 -1;
0 -1 -1 -1;
0 -1 0 -1;
-1 -1 -1 -1;
];
W = [-1 -2 -2 0];
C = 1;
[n m] = size(X);
while (1)
j = 0;
for i = 1:n
g = X(i,:)*W‘;
if g <= 0
j = 1;
disp(‘惩罚‘);
W = W + C*X(i,:);
end
end
if j == 0
break;
else
j = 0;
end
end
color = [‘r‘, ‘b‘];
for i = 1:n
scatter3(X(i,1)*X(i,4), X(i,2)*X(i,4) ,X(i,3)*X(i,4), 16, color(floor((X(i,4)+3)/2)));
hold on;
end
t=0:0.1:1;
[x,y]=meshgrid(t);
z = -W(1)/W(3)*x-W(2)/W(3)*y-W(4)/W(3);
mesh(x,y,z)
结果:W = [3 -2 -3 1]
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘