【線形分類器】Goで Perceptron を書いてみた

工学系出身のため機械学習に関して初心者ですが, 乏しい線形代数の知識をなんとか使って勉強したのでまとめます。今回実装したオンライン学習手法である Perceptronに関しては原理も単純なので機械学習初心者にオススメです。

Rosenblatt-Perceptron Photo by wikipedia(en)

オンライン線形分類器

オンライン学習はデータを逐次的にひとつずつ処理し, その度に重みベクトルを更新していく学習法です。
バッチ学習する場合と比較してリアルタイムに更新できる点が特徴です。オンライン線形分類器は, オンライン学習によって構築される線形分類器です。

今回はオンライン線形分類器の走りである Perceptron を実装しました。

Perceptron

Perceptron [Rosenblatt, 1958] は線形分類器(2値分類器)です。Perceptronの概念の始まりは, 2値出力を行う単純な論理ゲートとして神経細胞を表現した McCulloch-Pitts Neurons [McCulloch Pitts, 1943] が基とも言われています。

Perceptronのアルゴリズムは以下で示されます。単位ステップ関数 (ヘビサイド関数) により2値を分類します。

$\begin{eqnarray*} && f(x) = \begin{cases} 1 \quad ( \sum_{i=0}^m \omega_i x_i + b > 0 )\\ 0 \quad ( otherwise ) \end{cases} \end{eqnarray*}$

超平面は分類するための境界線を指し, 一般に特徴空間は高次元であるため総称して超平面と表現されます。2次元の場合は直線です。

Perceptron は分類に失敗した時に重みベクトルを更新します。問題が線形分離可能で学習率 η が十分小さい場合, 有限回の誤認識に収まり最終的に正しく分類できる超平面が求まります。これを Perceptronの収束定理と言います。

Perceptronの欠点としては低速, 偏り問題, 頻度問題があります。

古くからある Perceptron と同様の単層NNとして ADALINE (Widrow, 1960) に触れておきます。
損失関数とその最小化という概念について初めて述べられたのが, ADALINE のようです。
Perceptronでのステップ関数の代わりに連続値を出力する(微分可能な)活性化関数により重みを更新します。分類予測のために連続値を離散化する量子化器が使われます。

Perceptronの亜種として全てのステップにおける重みの平均を使った平均化Perceptronがあります。

続いて, Perceptron以外の代表的なオンライン学習手法を簡単に紹介します。

Confidence-Weighted Algorithm (CW)

Perceptronの頻度問題に対して, 重みベクトルの分布が正規分布に従うことを仮定して更新するアルゴリズムです。
分散の大きいパラメータは重みベクトルを大きく更新，確信度の高い分散の小さいパラメータは小さく更新するのが Confidence の名前の由来になります。
一方で学習時にノイズがあると急激に性能が落ちる問題があります。

Adaptive Regularization of Weight Vectors (AROW)

AROW [3] は CW がノイズに弱いという問題に対して, 学習データを正しく分類すること, これまでの分布に近い分布を探すこと, 各特徴の確信度を更新する度にあげることの3つを考慮して最適化します。

学習効率は CWと同程度ですが, ノイズが含まれた学習データに対しても頑健です。

Exact Soft Confidence-Weight Learning (SCW)

SCW [4] は CWと AROWの特徴を有する進化版です。上記手法と比較しても高速, ノイズに強い, 高精度という三拍子そろった線形分類器です。

Perceptron を Go で書いてみた

今回実装したのは Perceptronで, wiki(en)のPythonを Go で複製しました。元のコードが以下。

# -*- coding: utf-8 -*-

threshold = 0.5
learning_rate = 0.1
weights = [0, 0, 0]
training_set = [((1, 0, 0), 1), ((1, 0, 1), 1), ((1, 1, 0), 1), ((1, 1, 1), 0)]
 
def dot_product(values, weights):
    return sum(value * weight for value, weight in zip(values, weights))
 
while True:
    print('-' * 60)
    error_count = 0
    for input_vector, desired_output in training_set:
        print(weights)
        result = dot_product(input_vector, weights) > threshold
        error = desired_output - result
        if error != 0:
            error_count += 1
            for index, value in enumerate(input_vector):
                weights[index] += learning_rate * error * value
    if error_count == 0:
        break

Codeは Github にあります。

[2016/06/27追記]
Perceptron からロジスティック回帰, SVM, カーネル主成分分析, Random Forest まで機械学習アルゴリズムとそのPython実装について非常にわかり易く書かれている本を見つけたので載せておきます。注釈も充実していてオススメです。また, 前処理における標準化の重要性と実践的テクニックについて知れたのも良かったです。

[1] 1960: An adaptive “ADALINE” neuron using chemical “memistors”
[2] Adaptive Regularization of Weight Vectors
[3] Exact Soft Confidence-Weighted Learning
[4] オンライン線形分類器とSCW