読者です 読者をやめる 読者になる 読者になる

パーセプトロンアルゴリズムの実装をした気がする

最近読み始めたSVMの参考書

サポートベクターマシン入門

サポートベクターマシン入門

の中でパーセプトロンアルゴリズムが紹介されているので実装してみる(うまくいっているかはよくわからん)

ちなみに僕がそのままわかるはずもなく

こちらを参考にしています
http://labs.cybozu.co.jp/blog/nakatani/2009/04/perceptron_1.html:Perceptron を手で計算して理解してみる
http://d.hatena.ne.jp/aidiary/20100429/1272504218:パーセプトロン

詳細も僕が書くより上記の記事をみたほうが明らかによいです。

とりあえず学習データは同じものを用意してみました。なお、各ベクトルは都合上全て転置しています。
また、ベクトルが太字になっていません(ばかす

x_{0} = (0,0),t_{0} = -1
x_{1} = (1,0),t_{1} = -1
x_{2} = (0,1),t_{2} = -1
x_{3} = (1,1),t_{3} = +1

続いて特徴ベクトルを
\phi(x_{0}) = (1,0,0)
\phi(x_{1}) = (1,1,0)
\phi(x_{2}) = (1,0,1)
\phi(x_{3}) = (1,1,1)
とします。

そして初期の重みベクトルを
w_{0} = (0,0,0)
とします。

あとは
各学習データに対して
w^T\phi(x_{n})t_{n} > 0
を満たすかどうかを調べ、満たすならばそのまま、満たさないときには
w_{\tau+1} = w_{\tau} + w^T\phi(x_{n})t_{n}
で重みベクトルを更新します。

これをすべての学習データで上の式を満たすまで繰り返します。
学習データが線形分離可能だとわかっていれば、このアルゴリズムは有限回の繰り返しで厳密解に収束することが知られています。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<unistd.h>
#include<sys/times.h>

int Dm,Dc,Dv,*VecA,*VecB,*VecC,**MatD,**MatA,**MatB;

void    readValue(char *fn1)
{
  FILE *fp;
  int i, j, k;
  double v;
  if((fp = fopen(fn1, "r")) == NULL){
    printf("Unknown File = %s\n", fn1); exit(1);}
  fscanf(fp, "%d %d",&Dm,&Dc);
  MatA = (int **) malloc(sizeof(int *)*Dm);
  VecA = (int *) malloc(sizeof(int )*Dm);
  for(i = 0; i < Dm; i++){
    MatA[i] = (int *) malloc(sizeof(int)*Dc);
    for(j = 0; j < Dc; j++){
      fscanf(fp, "%d", &k);
      MatA[i][j] = k;
      }
    fscanf(fp, "%d",&VecA[i]);
  }
  fclose(fp);
}

void initValue()
{
  int i,j,k;
  VecB = (int *) malloc(sizeof(int)*Dc+1); 
  for(i=0;i<Dc+1;i++) VecB[i] = 0;
  MatB = (int **) malloc(sizeof(int *)*Dm);
   for(i=0;i<Dm;i++){
    MatB[i] = (int *) malloc(sizeof(int )*Dc+1);
    MatB[i][0] = 1;
    for(j=1;j<Dc+1;j++){
      MatB[i][j] = MatA[i][j-1];
    }
  }
}

void calValue()
{
  int sum=0,i,j,k=0,sum2,update=0;
  while(sum<Dm){
    for(i=0; i<Dm; i++){
      for(sum2=j=0;j<Dc+1;j++){
        sum2 += VecB[j]*(MatB[i][j]*VecA[i]);
        printf("%d\n",sum2);
      }
      sum2*VecA[i];
      if(sum2 > 0) {
        sum++;
      }
      else{
        for(j=0;j<Dc+1;j++) VecB[j] = VecB[j]+MatB[i][j]*VecA[i];
        update++;
        printf("%d ",update);
        for(j=0;j<Dc+1;j++) printf("%d ",VecB[j]);
        printf("\n");
      }
    }
  }
}

main(int argc ,char **argv)
{
  int i,j,k,l;
  readValue(argv[1]);
  initValue();
  calValue();
}
実行結果

1 -1 0 0
2 0 1 1
3 -1 1 1
4 -2 0 1
5 -1 1 2
6 -2 0 2
7 -3 0 1
8 -2 1 2

8回の反復で終了し、
{ w_{8}} = (-2,1,2)
だという結果。合っているのか…汗
少なくとも参考記事と同じ結果になっていないのでどこかミスしているかもしれません…とりあえずかくのが重要と思い書いてみました!

追記:学習率\etaという概念が全くと言っていいほど理解できてません…