感知机问题学习算法引入:信用卡问题

根据已知数据(不同标准的人的信用评级)训练后得出一个能不能给新客户发放信用卡的评定结果

【机器学习】感知机学习算法(PLA)

解决该问题的核心思想扔为之前所讲到的梯度下降算法,对于更多条件的类似问题,首先选取一个超平面w0,b0,然后用梯度下降算法不断极小化目标函数,使得此过程中随机一个有误分类点的梯度下降。

过程通过随机选取一个分类点,(xi,yi)依据该分类点对w b进行更新。

【机器学习】感知机学习算法(PLA)

得出的这个函数f(x) = sign(w·x+b)就是感知机模型。

它的计目的就是找到一条直线,能够把正向数据与负向数据分开

【机器学习】感知机学习算法(PLA)

那么如图1是一个明确我们所得出的一个比较好的直线,接下来我们需要找到一条更好的直线,将两种结果分开,那么经过多次迭代,就会得出图二中的直线。

算法原始形式如下:

输入:

  训练数据集T = {(x1,y1)……(xn,yn)}

  (xi为向量)

  学习率  η(0,1)

输出:

  w ,b

依据:

  感知机模型f(x) = sign(w·x+b)

感知机算法的执行步骤:

1)选取初值w0,b0

2)在训练集合中任意选取数据(xi,yi),其中yi为评判标准,即yi∈{+1,-1}

3)如果yi(w·xi+b) <= 0 则说明当前结果与目标结果相违背,更新w与b

w = w + ηyixi

b = b + ηyi

4)跳转到步骤(2)直到不存在误分点。

该过程图形化的描述如下:

【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)

 

 

 

 【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)【机器学习】感知机学习算法(PLA)

 

该方法虽然简单,但并非所有情况下都是有解的

【机器学习】感知机学习算法(PLA)

如图2 3的情况下该算法将一直运行,不会得到解。算法对于可分数据集的计算过程用C++语言描述如下:

#include<iostream>
using namespace std;
int main()
{
    bool flag = true;
    int x1[10],x2[10],num;
    int type[10];
    int w1 = 0,w2 = 0,b = 0,times = 0;//times为迭代次数
    cin>>num;
    for(int  i = 0; i < num; i++)
    {
        cin >> x1[i] >> x2[i]>>type[i];
    }
    do
    {
        times++;
        int t = 0;
        for(int i  = 0; i  < num; i++)
        {
            if(type[i]*(w1*x1[i]+w2*x2[i]+b) <= 0)//判断是否被正确分类
            {
                flag = false;//如果没有正确分类,修改标志
                
                w1 += type[i]*x1[i];//更新w
                w2 += type[i]*x2[i];
                b  += type[i];
            }
            else t++;
        }
        if(t == num)
        {
            flag = true;
        }

    }
    while(!flag);
    cout <<"w1:"<< w1 <<" w2:"<<w2<<" b:"<<b<<"times"<<times<<endl;
    return 0;
}

计算过程十分简单,其中说明对于未知的情况,即开始时候,w0 b0都初始化为0,之后将会迭代更新。

经过证明该算法是具有收敛性的,【机器学习】感知机学习算法(PLA)

并且可以得出,对于【机器学习】感知机学习算法(PLA)(R²为最大向量长度,ρ为目标直线的法向量与每个点的內积判断方向yn中的最小的)

可以得出计算次数k <= 【机器学习】感知机学习算法(PLA)

另外需要注意,对于可分训练数据集,选取点的次序不同,得出的解也就不同,但是这些都是感知机学习算法的解。