ADALINE とは

Adaptive Linear Neuron の略。
分類問題を解くアルゴリズムで、パーセプトロンの改良のようなもの。

問題設定

入力値（特徴量） $x_1, \cdots, x_m$ に対し、分類ラベル $y$ を出力するモデルを作る。

仕組み

基本原理

各入力値に重み $w_1, \cdots, w_m$ をかけて和を取った

$z = \displaystyle \sum_{j=1}^{m} w_j x_j$

を 総入力 と呼び、 $z$ が閾値 $\theta$ 以上か否かで二値分類を行う。
また、閾値 $\theta$ をゼロ番目の重み $w_0 = - \theta$ として総入力に加える（ $x_0 = 1$ ）ことで、ラベル判定の閾値を0にできる。
したがって、問題は重み $w_0, \cdots, w_m$ の最適化問題に帰着する。

ここまではパーセプトロンと同様。

パーセプトロンでは、総入力 $z$ に対する活性化関数を

$\phi(z) = \begin{cases} 1 & (z \ge 0 ) \\ -1 & (z \lt 0 ) \end{cases}$

と定義し、ラベルの正解と予測の一致・不一致の区別のみを行い重みの更新を行った。
ADALINE では、

$\phi(z) = z = \displaystyle \sum_{j=0}^{m} w_j x_j$

という線形活性化関数を導入する。
→ 単純に正解ラベルと一致するかしないかではなく、「どれほど正解ラベルに近いか」という連続値による評価ができる

ADALINE では、全サンプルに対するラベル判定誤差の平方和

$J(\boldsymbol{w}) = \displaystyle \frac{1}{2} \sum_i \left( y^{(i)} - \phi(z^{(i)}) \right)^2 = \displaystyle \frac{1}{2} \sum_i \left( y^{(i)} - \sum_{j=0}^{m} w_j x_j^{(i)} \right)^2$

を目的関数（コスト関数）とし、これが最小になるよう、勾配降下法による学習を進めていく。
式の先頭の $\frac{1}{2}$ は、後述の微分で余計な係数が消えるよう調整するパラメータなので重要ではない。

$J(\boldsymbol{w})$ の勾配 $\nabla J(\boldsymbol{w})$ の各成分は、

$\cfrac{\partial J(\boldsymbol{w})}{\partial w_j} = - \displaystyle \sum_i \left( y^{(i)} - \phi(z^{(i)}) \right) x_j^{(i)}$

よって、重み $\boldsymbol{w}$ の各成分を以下の式で更新するとコスト関数を小さくできる。

$w_j \longleftarrow w_j - \eta \cfrac{\partial J(\boldsymbol{w})}{\partial w_j} = w_j + \eta \displaystyle \sum_i \left( y^{(i)} - \phi(z^{(i)}) \right) x_j^{(i)}$

ここで $\eta (0 \lt \eta \le 1)$ は学習率であり、1度に重みを更新する大きさを表す。

学習規則

重みをゼロ or 値の小さい乱数で初期化
すべての学習サンプル $\boldsymbol{x}^{(i)} = ( x_0^{(i)}, \cdots, x_m^{(i)} )$ を使い、コスト関数 $J(\boldsymbol{w})$ の勾配 $\nabla J(\boldsymbol{w})$ を計算
勾配に沿って、コスト関数が小さくなるように重みを更新
収束するまで2,3を繰り返す

学習率と収束

「学習率が大きい = 1度の重み更新の幅が大きい」
→ 学習率が大きすぎると収束しない

download-4

実装

コード

	import numpy as np

	class Adaline:
	def __init__(self, d, eta=0.001, epoch=100, max_err=10):
	"""
	Parameters
	----------
	d : 次元（変数の数）
	eta : 学習率
	epoch : エポック
	max_err : 許容する判定誤りの最大数
	"""
	self.d = d
	self.eta = eta
	self.epoch = epoch
	self.max_err = max_err
	self.weight = np.zeros(d+1) # 閾値を重みと見做す分、1つ増える

	def predict(self, x):
	"""
	Parameters
	----------
	x : 分類したいデータ（d次元ベクトル）
	"""
	return 1 if np.dot(x, self.weight[:-1]) + self.weight[-1] > 0 else -1

	def fit(self, data, labels):
	"""
	Parameters
	----------
	data :
	labels :
	"""
	self.labels = labels
	self.data = np.append(data, np.array([[1.0] for _ in range(len(data))]), axis=1)
	for t in range(self.epoch):
	cnt_err = self.__cycle()
	if cnt_err <= self.max_err:
	break
	print('Converged in {} cycles.'.format(t+1))

	def __cycle(self):
	cnt_err = 0
	dw = np.zeros(len(self.weight))
	for i in range(len(self.data)):
	z = np.dot(self.data[i], self.weight)
	dw += (self.labels[i] - z) * self.data[i]
	if self.labels[i] < 0 <= z or z < 0 < self.labels[i]:
	cnt_err += 1
	dw *= self.eta
	self.weight += dw
	return cnt_err

view raw adaline.py hosted with ❤ by GitHub

動作確認

点：学習データ
背景：モデルの決定領域

	# 学習データ作成
	N = 1000
	data = np.reshape(np.random.rand(2*N), (N, 2))
	labels = np.array([1 if 2*x[0] - x[1] > 0 else -1 for x in data])

	# 学習
	adaline = Adaline(2, max_err=N//100)
	adaline.fit(data, labels)

view raw ~fit1.py hosted with ❤ by GitHub

download-1

	# 学習データ作成
	N = 1000
	c1 = [1, 1]
	c2 = [2, 3]
	r1 = 1.5*np.random.rand(N//2)
	r2 = 1.0*np.random.rand(N//2)
	theta1 = np.random.rand(N//2) * 2 * np.pi
	theta2 = np.random.rand(N//2) * 2 * np.pi
	data1 = np.array([r1 * np.sin(theta1) + c1[0], r1 * np.cos(theta1) + c1[1]]).T
	data2 = np.array([r2 * np.sin(theta2) + c2[0], r2 * np.cos(theta2) + c2[1]]).T
	data = np.concatenate([data1, data2])
	labels = np.array([1 if i < N//2 else -1 for i in range(N)])

	# 学習
	adaline = Adaline(2, max_err=N//50, eta=1e-4, epoch=500)
	adaline.fit(data, labels)

view raw ~fit2.py hosted with ❤ by GitHub

download-2