什么是H-K算法

什么是H-K算法

其实HK算法思想很朴实,就是在最小均方误差准则下求得权矢量.
他相对于感知器算法的优点在于,他适用于线性可分和非线性可分得情况,对于线性可分的情况,给出最优权矢量,对于非线性可分得情况,能够判别出来,以退出迭代过程.
2.在程序编制过程中,我所受的最大困扰是：关于收敛条件的判决.
对于误差矢量：e=x*w-b
若e>0 则继续迭代
若e=0 则停止迭代,得到权矢量
若e〈0 则停止迭代,样本是非线性可分得,
若e有的分量大于0,有的分量小于0 ,则在各分量都变成零,或者停止由负值转变成正值时,停机.
3.在程序编制中的注意点：
1）关于0的判断,由于计算机的精度原因,严格等于零是很不容易的,而且在很多情况下也没有必要,则只要在0的一个可以接受的delta域内就可接受为零
2）关于判断,迭代前后,变量是否发生变化
在判断时,显然也不能直接判断a(i)==a(i+1)
而应该|a(i)-a(i+1)|〈err
4.HK详细代码如下：
unction [w,flag]=HK(data)
Iteration=20;
flag=0;
% [n,p]=size(data);
n=size(data,1);
b=ones(n,1)./10;
c=0.6;
xx=inv(data'*data)*data';
w=xx*b;
e=data*w-b;
t=0;
while (1)
temp=min(e);
temp1=max(e);
if temp>-1e-4 && temp1e-3
deltab=e+abs(e);
b=b+c.*deltab;
w=w+c.*xx*deltab;
e=data*w-b;
else
if temp>=0 && temp1

H-K算法是求解Xw=b，式中b=( b1, b2, …, bn)T，b的所有分量都是正值。这里要同时计算w和b，我们已知X不是N*N的方阵，通常是行多于列的N*(n+1)阶的长方阵，属于超定方程，因此一般情况下，Xw=b没有唯一确定解，但可求其线性最小二乘解。
设Xw=b的线性最小二乘解为w*，即使||Xw*-b||=极小 采用梯度法，定义准则函数：
)bXw()bXw(2
1bXw21)bxw(21)b,x,w(JT2
n1i2iiT
当Xw=b的条件满足时，J达到最小值。由于上式中包括的
n
1
i2iiT
)bxw
(项为两个数量方差的和，且我们将使其最小化，因此也
称之为最小均方误差算法。
使函数J同时对变量w和b求最小。对于w的梯度为：
)bXw(Xw
J
T 使0w
J
，得XT(Xw-b)=0，从而XTXw=XTb。因为XTX为(n+1)*(n+1)阶方阵，因此可求得解：
w = (XTX)-1XTb = X#b
这里X#= (XTX)-1XT称为X的伪逆，X是N*(n+1)阶的长方阵。
由上式可知，只要求出b即可求得w。利用梯度法可求得b的迭代公式为：
)
k(bbbJC)k(b)1k(b

根据上述约束条件，在每次迭代中，b(k)的全部分量只能是正值。由J的准则函数式，J也是正值，因此，当取校正增量C为正值时，为保证每次迭代中的b(k)都是正值，应使)
k(bbbJ

为非正值。在此条件下，准则函数J的微分为：
|bXw|)bXw(bJ2)
k(bb

该式满足以下条件：
若[Xw(k) – b(k)] > 0，则)k(b)k(XwbJ)
k(bb

 若[Xw(k) – b(k)] < 0，则0bJ)
k(bb 由b的迭代式和微分，有：
b(k+1) = b(k) +δb(k)
δb(k) = C[Xw(k) – b(k) + | Xw(k) – b(k)|]
将此式代入w=X#b，有：
w(k+1) = X#b(k+1) = X#[b(k) +δb(k)] = w(k) + X#δb(k)
为简化起见，令e(k) = Xw(k) – b(k)，可得H-K算法的迭代式。
设初值为b(1)，其每一分量均为正值，则：
w(1) = X#b(1) e(k) = Xw(k) – b(k)
w(k+1) = w(k) + X#{C[Xw(k) – b(k) + |Xw(k) – b(k)|]}
= w(k) + CX#[e(k) + |e(k)|]
由于
X#e(k) = X#[Xw(k) – b(k)] = (XTX)-1XT[Xw(k) – b(k)]

= w(k) –X#b(k) = 0
因此
w(k+1) = w(k) + CX#|e(k)|
b(k+1) = b(k) + C[Xw(k) – b(k) + |Xw(k) – b(k)|]
= b(k) + C[e(k) + |e(k)|]