Machine Learning – ページ 25

Perceptron (Rosenblatt, 1958) を1年半前に書いてから, だいぶ時間が経ってしまいましたが, 今回はその続きで Go で PA, PA-I, PA-II, CW, AROW, SCW-I, SCW-II を書いてみたのでメモリます。

PA, CW, AROW, SCWの総まとめ的な論文 Exact Soft Confidence-Weighted Learning にアルゴリズムがまとまっています。

PA (Passive-Aggressive)

PA (Crammer et al., 2006) [1] は, 損失関数にSVMでも使われているヒンジ損失を用いる。

$\begin{eqnarray*} {\ell}_{hinge} = max(0, 1-y\omega^{T}x) \end{eqnarray*}$

最適化問題は, ヒンジ損失が 0 となる制約の元でこれまでに得られている重みに近い重みを選択する。ただし, ヒンジ損失が 0 となる制約は強く, 急に重みが変動してしまうので, PA-Iでは罰則項を線形に加え, PA-IIでは罰則項を2乗で加える。

PA, PA-I, PA-IIのそれぞれで最適化問題をラグランジュの未定乗数法を用いて解くと閉じた形式の更新式が得られる。

実装はシンプルとなる。

func calc_tau(method string, l float64, x *mat64.Dense, c float64) float64 {
	switch method {
	case PA:
		return l / mat64.Dot(x, x) // hingeloss / ||x||^2
	case PA1:
		return util.Min(c, l/mat64.Dot(x, x)) // min(c, hingeloss / ||x||^2)
	case PA2:
		return l / (mat64.Dot(x, x) + 1/(2*c)) // hingeloss / (||x||^2 + 1/2c)
	default:
		return l / mat64.Dot(x, x) // default case : PA
	}
}

func (self *Model) UpdatePA(label float64, feats *mat64.Dense, C float64) (float64, float64) {
	// Hinge loss
	l := util.Max(0, 1.0-label*mat64.Dot(feats, self.Param.W))

	// set updating strategy
	tau := calc_tau(self.Env.Method, l, feats, C)

	for i, x := range util.RawColViewer(feats, 0) {
		w := self.Param.W.At(0, i)
		// Aggressive : Update the weights
		self.Param.W.Set(0, i, w+tau*label*x)
	}

	return label, util.Sign(mat64.Dot(feats, self.Param.W))
}

CW (Confidence Weighted)

CW (Dredze et al., 2008) [2] では, 重みベクトル ω が正規分布 N(μ, Z) から生成されていると考える。従って, パラメータは点から分布に変わり平均に加えて, 分散共分散行列がパラメータとして加わっている。

PAでこれまでに得られている重みに近い重みを探したように, CW でもこれまでと近い分布を KLダイバージェンス (Kullback–Leibler divergence) で探す。

正規分布を決めるパラメータを更新する最適化問題は, 以下の閉じた形で表される。

更新時に各特徴ごとの確信度によって更新幅を変えるため, 計算量はPAと比較して大きくなる。

func (self *Model) UpdateCW(label float64, feats *mat64.Dense) (float64, float64) {

	phi := math.Pow(util.Cdf(self.Param.Eta), -1) // cdf(eta)^-1
	psi := 1.0 + math.Pow(phi, 2)/2
	zeta := 1.0 + math.Pow(phi, 2)

	// Weight distribution is updated by minimizing Kullback-Leibler divergence
	v_part := util.Dot(self.Param.Cov, mat64.DenseCopyOf(feats.T()))
	v := util.Dot(feats, v_part).At(0, 0)                     // x・Cov・x_T, to float64
	m := label * mat64.Sum(util.MulElem(self.Param.W, feats)) // y * (mu・x)
	if v < 0 {                                                // TODO
		self.Err = errors.New("Error occurred : v is under zero.")
		return 0.0, 0.0
	}

	// updating coefficients
	alpha := util.Max(0.0, 1.0/(v*zeta)*(-m*psi+
		math.Sqrt((math.Pow(m, 2))*(math.Pow(phi, 4))/4.0+v*math.Pow(phi, 2)*zeta)))
	u := 0.25 * math.Pow(-alpha*v*phi+math.Sqrt(math.Pow(alpha*v*phi, 2)+4.0*v), 2)
	beta := alpha * phi / (math.Sqrt(u) + v*alpha*phi)

	// updating parameters
	w_part := util.Mul(util.Mul(util.Dot(self.Param.Cov, feats), label), alpha) // α・y・Cov・x
	self.Param.W = util.Add(self.Param.W, w_part)                               // mu + α・y・Cov・x

	s_part := util.MulElem(util.Dot(self.Param.Cov, feats), feats) // Cov・x_T * x
	s := util.Mul(util.MulElem2(s_part, self.Param.Cov), beta)     // Β * Cov・x_T・x * Cov
	self.Param.Cov = util.Sub(self.Param.Cov, s)                   // Cov - Β * Cov・x_T・x * Cov

	return label, util.Sign(mat64.Dot(self.Param.W, feats))
}

CW ではノイズが入っていても η の確率で分類できるようにパラメータを更新してしまう。η を下げるとノイズに多少強くなりそうだが, その分収束までの時間がかかってしまう。

AROW (Adaptive Regularization of Weight Vectors)

AROW (Crammer et al., 2009b) [3]はこれまでの分布は保持し, 収束速度を保ちつつも CW でノイズが混ざっている時に over-fit しやすい問題に対して, 名前にもあるように正則化パラメータ γを導入することで頑健性も持っている。

CWの目的関数に 2つ目の項で損失関数を追加し, 3つ目の項で学習が進むにつれて共分散を小さくするように追加した形になっている

更新則は CWと同様の形となり, 最終的なアルゴリズム自体は CW と似ている。α と β は下記となる。

α は二乗ヒンジ損失の方で実装した。

func (self *Model) UpdateAROW(label float64, feats *mat64.Dense, gamma float64) (float64, float64) {

	v_part := util.Dot(self.Param.Cov, mat64.DenseCopyOf(feats.T()))
	v := util.Dot(feats, v_part).At(0, 0) // confidence : x・Cov・x_T, to float64
	m := mat64.Dot(feats, self.Param.W)   // margin : mu・x

	if m*label < 1.0 {
		// Updating coefficients
		beta := 1 / (v + gamma)                  // 1 / conf + γ
		alpha := util.Max(0, 1-(label*m)) * beta // max(0, 1 - y・m) * β

		covx := util.Dot(self.Param.Cov, feats)
		// Updating parameters
		w_part := util.Mul(util.Mul(covx, label), alpha)
		self.Param.W = util.Add(self.Param.W, w_part) // mu

		s_part := util.Mul(util.MulElem(covx, covx), beta)
		self.Param.Cov = util.Sub(self.Param.Cov, s_part) // Cov
	}

	return label, util.Sign(mat64.Dot(self.Param.W, feats))
}

SCW (Soft Confidence-Weighted Learning)

SCW (J Wang et al., ‎2012) [4]は CW と AROW の特徴を備えたアルゴリズム。
ソフトマージン SVMの最適化問題と似ており, パラメータ C を用いて, 正規分布が急激に変化するのを抑制する。

更新則の α と β は Proposition1 (SCW-I), Proposition2 (SCW-II)で異なり, どちらも CWと同様に閉じた形で更新式が表される。

SCW-I と SCW-II で β は共通なので, α の計算だけ切り出している。

func calc_alpha(method string, v, m, phi, psi, zeta, C float64) float64 {
	switch method {
	case SCW1:
		j := math.Pow(m, 2) * 0.25 * math.Pow(phi, 4)
		k := v * zeta * math.Pow(phi, 2)

		alpha := util.Min(C, util.Max(0.0, (-m*psi+math.Sqrt(j+k))/(v*zeta)))
		return alpha

	case SCW2:
		n := v + 1/(2*C)
		j := math.Pow(phi*m*v, 2)
		k := 4.0 * n * v * (n + v*math.Pow(phi, 2))
		gamma := phi * math.Sqrt(j+k)

		alpha := util.Max(0.0, (-(2.0*m*n+math.Pow(phi, 2)*m*v)+gamma)/
			(2.0*(math.Pow(n, 2)+n*v*math.Pow(phi, 2))))
		return alpha

	default:
		return 0.0
	}
}

func (self *Model) UpdateSCW(label float64, feats *mat64.Dense, C float64) (float64, float64) {

	phi := math.Pow(util.Cdf(self.Param.Eta), -1) // cdf(eta)^-1
	psi := 1.0 + math.Pow(phi, 2)/2
	zeta := 1.0 + math.Pow(phi, 2)

	// Weight distribution is updated by minimizing Kullback-Leibler divergence
	v_part := util.Dot(self.Param.Cov, mat64.DenseCopyOf(feats.T()))
	v := util.Dot(feats, v_part).At(0, 0)                     // x・Cov・x_T, to float64
	m := label * mat64.Sum(util.MulElem(self.Param.W, feats)) // y * (mu・x)
	if v < 0 {                                                // TODO
		self.Err = errors.New("Error occurred : v is under zero.")
		return 0.0, 0.0
	}

	if calc_loss(feats, self.Param.W, label) > 0.0 {
		// updating coefficients
		alpha := calc_alpha(self.Env.Method, v, m, phi, psi, zeta, C)
		u := 0.25 * math.Pow(-alpha*v*phi+math.Sqrt(math.Pow(alpha*v*phi, 2)+4.0*v), 2)
		beta := (alpha * phi) / (math.Sqrt(u) + v*alpha*phi)

		// updating parameters
		w_part := util.Mul(util.Mul(util.Dot(self.Param.Cov, feats), label), alpha) // α・y・Cov・x
		self.Param.W = util.Add(self.Param.W, w_part)                               // mu + α・y・Cov・x

		s_part := util.MulElem(util.Dot(self.Param.Cov, feats), feats) // Cov・x_T * x
		s := util.Mul(util.MulElem2(s_part, self.Param.Cov), beta)     // Β * Cov・x_T・x * Cov
		self.Param.Cov = util.Sub(self.Param.Cov, s)                   // Cov - Β * Cov・x_T・x * Cov
	}

	return label, util.Sign(mat64.Dot(self.Param.W, feats))
}

おわりに

今回は PA, PA-I, PA-II, CW, AROW, SCW-I, SCW-II を(汚いですが) Go で書きました。
上記のcodeの CW, SCW で vt の計算が問題によっては負となり α の更新則の中の math.Sqrt() で NaNになってしまうのは宿題にします…

次は Pegasos (Primal Estimated sub-GrAdient SOlver for SVM) [5] も書いてみたいです。numpyほど gonum/mat64 が使いやすくない所があり辛い面もありましたが, せっかく Go で書いたこともり, まとめて package にして GitHub で公開したいです。

参考書籍は『オンライン機械学習 (機械学習プロフェッショナルシリーズ)』です。

[1] Online Passive-Aggressive Algorithms
[2] Confidence-Weighted Linear Classification
[3] Adaptive Regularization of Weight Vectors
[4] Exact Soft Confidence-Weighted Learning
[5] Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
[6] オンライン凸最適化と線形識別モデル学習の最前線
[7] 機械学習勉強会 2010/07/01

タグ: Machine Learning

【オンライン機械学習】 Go で PA, CW, AROW, SCW を書いてみた

PA (Passive-Aggressive)

CW (Confidence Weighted)

AROW (Adaptive Regularization of Weight Vectors)

SCW (Soft Confidence-Weighted Learning)

おわりに