機械学習プロフェッショナルシリーズ 「オンライン機械学習」 読書メモ

サマリー

オンライン学習は，機械学習における学習の枠組みの一つとなる．オンライン学習の枠組みでは，全データを一度に用いること無く，データが一つ（あるいは全データの一部）与えられるたびに，与えられたデータ のみを用いて逐次的にモデルを改良する。このデータ処理方式の性質から，メモリやキャッシュに全データが乗らない規模のデータ解析や永続的にデータが生成される環境下での学習に適用される。

オンライン学習では、逐次的なデータを受け取り、それに合わせてアルゴリズムやデータモデルを変更していく機能が求められる。それらで使われているアルゴリズムとしてはパーセプトロン、ADALINE、ナイーブベイズ、線形回帰、深層学習等がある。

これらは”バンディット問題の理論とアルゴリズム“で述べられた多腕バンディット問題や、”様々な強化学習技術の理論とアルゴリズムとpythonによる実装“で述べられた強化学習技術とも密接に関係している技術となる。

ここではこのオンライン学習に対して「機械学習プロフェッショナルシリーズ オンライン機械学習」をベースに様々なアルゴリズムや応用について述べている。

今回は読書メモについて述べる。

機械学習プロフェッショナルシリーズ 「オンライン機械学習」 読書メモ

「オンライン学習は，機械学習における学習の枠組みの一つである．オンライン学習の枠組みでは，全データを一度に用いること無く，データが一つ（あるいは全データの一部）与えられるたびに，与えられたデータ のみを用いて逐次的にモデルを改良する． そのデータのみを用いて逐次的にモデルを改良する．このデータ処理方式の性質から，メモリやキャッシュに全データが乗らない規模のデータ解析や永続的にデータが生成される環境下での学習が効率化できる．インフラ基盤やセンサー／ネットワーク技術の進歩によるデータの大規模化や機械学習技術を用いた継続的なサービス運用が一般的となるにつれて，オンライン学習分野の研究開発も促進された．機械学習分野の論文ではこれらの枠組みを単にオンライン学習 (Online Learning) と表現する事が多い．しかし，オンライン学習という用語は一般的に，大学講義などの教育系コンテンツをウェブ上で受講できる仕組みを指す．機械学習用語としてのオンライン学習と教育用語としてのオンライン学習を区別するため，機械学習用語の側をオンライン機械学習 (Online Machine Learning) と呼ぶこともある．
オンライン学習は機械学習の枠組みの一つであり，あくまで手段の一つである．また，固有のタスクや目的に特化した枠組みではない．そのため，タスクによって効果的な適用方法が異なり，またオンライン学習以外の代替的な枠組みを適用すべき問題設定も多く存在する．」

第 1 章 序論

1.1 機械学習とは
1.2 オンライン学習とは

はじめに
次々と現れるデータを逐次的に学習を行うこと
データ全体をまとめて学習
バッチ学習
1.2.1 オンライン学習の黎明期
人工知能の誕生とともにオンライン学習は誕生
パーセプトロン
1957
フランク・ローゼンプラット
視覚と脳の機能のモデル化
図形が連結化連結でないかを判定する問題を学習できない
ミンスキーの反論
1.2.2 オンライン学習の再発見
自然言語処理への応用
手法
最大エントロピー法
隠れマルコフモデル
サポートベクトルマシン
適用先
言語モデル
文書分類
品詞推定
構文解析
機械翻訳
サポートベクトルマシンやロジスティック回帰では一層のモデル
深層学習は”深い”モデル

1.3 オンライン学習の特徴

1.3.1 学習データをすぐ捨てられる
1.3.2 学習速度が速い
1.3.3 学習結果がいつでも使える
1.3.4 実装が簡単である
1.3.5 性能解析が容易である

1.4 オンライン学習の短所

学習するデータの順番に学習結果が大きく影響を受ける
データの偏りに影響を受ける
バッチ学習よりノイズに弱い傾向がある

第 2 章 準備

2.1 数式を読む際の心構え

2.2 数式についての約束事

2.2.1 数値の表記方法について
“式の型”を考えることが重要
整数とか、整数のベクトルとか、実数とか
関数は”型ふを考えるのが難しい
2.2.2 ベクトル
ベクトルの内積
x1y1+x2y2+…+xnyn
2.2.3 総和記号
和を取る記号
2.2.4 最小値，最大値，argmin，argmax
それぞれの式の値を最小もしくは最大にする変数
2.2.5 絶対値
絶対値は実数から符号を取り除いた時の大きさ
2.2.6 ノルム
距離を一般化した概念
L1ノルム
∥X∥1 = |x1| + |x2| +…+|xn|
∥W -V∥1 = |w1-v1| + |w2 -v2| +…+|wn-vn|
L2ノルム
∥X∥2 = √x12 + x22 +…+xn2
∥W-V∥2 = √(w1-v1)2 + (w2-v2)2 +…+(wn-vn)2
2.2.7 指数関数
ネイピア数e(2.718..)を低とする指数関数exをexp(x)と書く
2.2.8 偏微分と勾配
偏微分とは、
多変数関数を、注目している変数以外は定数だとみなして微分すること
関数f(x,y)をxで偏微分したもの
例
f(x,y)=2x+xy+y
∂f(x,y)/∂x=2+y
∂f(x,y)/∂y=x+1
関数の勾配とは、
関数を変数で偏微分した結果を並べてベクトルにしたもの
関数f(x)の勾配を∇f(x)と書く
∇f(x)=(∂f(x)/∂x1, ∂f(x)/∂x2, … ,∂f(x)/∂xn)
2.2.9 偏微分に使うテクニック
複雑な関数に対する偏微分のテクニック
関数の積の微分
関数f(x)=g(x)h(x)と積の形にできる場合
∂f(x)/∂x = ∂g(x)/∂x x h(x) + g(x) x ∂h(x)/∂x
合成関数の微分
関数f(x)=h(g(x))と、関数がさらに他の関数の引数になっている場合
∂f(x)/∂x = ∂h(x)/∂g(x) x ∂g(x)/∂x
expとlogの微分
∂ exp(x)/∂x = exp(x)
∂ log(x)/∂x = 1/x
2.2.10 計算量について
O-記法
計算量の記述
O(n):計算量が線形に増加する
O(xn):計算量が指数的に増加する

2.3 凸関数と非凸関数

下に凸である
任意のx,y∈Rmと0≤t≤1を満たす任意のtに対して
f(tx+(1-t)y) ≤ tf(x) + (1-t)f(y)
xが関数fの局所最適点である
ある実数ε>0が存在
任意のX’∈Rmに対して
∥x-x’∥< ε ⇒ f(x) ≤ f(x’)が成り立つ
xの十分近くでは、xが最小になる
xが関数fの大域最適点である
任意のx’∈Rmに対して
f(x)≤f(x’)が成り立つ
εによる制約がない

第 3 章 基礎

3.1 二値分類

入力xに対して実数値を返す関数f(x)を考える
分類器の出力yは2値分類の場合は上式で表される
f(x)の値が0より大きいかどうかで分類
引数の符号の正負に応じて+1,-1の いずれかをガウス関数であるsign()を使うと

3.2 線形分類器

上記のf(x)について
線形分類器(linear classifier)
w∈Rm-1は重みベクトル
b∈Rはバイアス項
計算上省略されることが多い
パラメータw,bを適切な値に調節できれば、二値分類問題が解決
バイアスbは特別扱いして別途最適化したほうが良い
Sgdというソフトでは バイアス項の更新時だけ学習率を1/100とする
バイアス付きPassive-Aggressiveアルゴリズム

3.3 パーセプトロン

最も基本的なオンライン学習アルゴリズム
パーセプトロンにおけるアルゴリズム
T回目に与えられる学習データをx(t)とy(t)の組とする
w(t+1)をt回データを受け取った後のパラメータとする
重みベクトルwと入力xの内積を計算する(wTx)
パラメータ更新の前後でのwTxの変化は
パラメータ更新の前後では内積の値はy(t)x(t)Tx(t)だけ変化する
天下り的に定義

3.4 目的関数と最適化手法

はじめに
目的関数
達成したい目的を表した関数
最適化手法
目的を達成するための方法
目的関数がよく分からなくても、 何かしらのアイデアに基づいた学習アルゴリズムがあれば、 良い性能は達成できる
確率的勾配法
FOBOS, RDA
3.4.1 目的関数の表記
パラメータwで特徴付けられた目的関数L(w)
損失項
正則化項
ℓ(x,y,w)やr(w)の具体的な形は学習アルゴリズムごとに異なる
3.4.2 オンライン学習と収束
分類器を学習することは、 目的関数を最小化するためにパラメータの値を調整することと同等
Incremental Gradient Method
いつになったら収束するのか?

3.5 確率的勾配降下法

はじめに
オンライン学習の最も基礎的な最適化手法
確率的勾配降下法 (Stochastic gradient descent)
3.5.1 勾配法とは
パラメータwを引数としてとる 目的関数L(w)の値を最小化するための手法
最大化したい場合には-1をかければ最小問題に変形できる
目的関数が凸である場合は、下っている方向に降りていけば良い
勾配法におけるポイント
どのタイミングでどの方向にどれだけ移動するか
最小値にたどり着く保証はあるのか
目的関数が凸かどうかが重要
凸関数の場合はどれだけ早く辿り着けるかがポイントになる
非凸関数の場合は、どれだけ良い解に辿り着けるかがポイントになる
3.5.2 勾配降下法
何らかの線形分類器にたいする目的関数L(w)を考える
目的関数は上式に分解できるとする
ℓ(x,y,w)の具体的な計算式はアルゴリズムにより変わる
例:分類に成功したら0、間違えたら分離超平面までの距離の値
勾配降下法では、 目的関数L(w)が収束するまで、 上式を用いてパラメータの更新をする
η(t)は、学習率と呼ばれる値、0以上の適当な値
何らかの正の実数εを設定し、 |L(w(t+1)-L(w(t)|<εとなったら そこで収束したものとする
3.5.3 確率的勾配降下法
通常の勾配法では、 1回のパラメータ更新のために、 全てのデータを使って勾配を計算し直す必要がある
計算コストが高い
一つデータを受け取ったら、そのデータのみを使って勾配を計算し、パラメータを更新する
確率的勾配降下法のアルゴリズム例
w(t+1) = w(t) – η(t)∇ℓ(x(t),y(t),w(t))
L(w)の代わりに、近似としてℓ(x,y,w)を使う
3.5.4 パーセプトロンの目的関数
パーセプトロンの目的関数
パーセプトロン基準
3.5.5 パーセプトロンの学習アルゴリズムの導出
ℓ(x,y,w)=max(-ywTx,0)
xとyは与えられるので学習の時には動かせない
動かせる変数はwのみ
Wの各要素で偏微分
その要素を並べて勾配とする
場合分けして考える
-ywTx>0の場合
式の値はmaxを外して-ywTxと書ける
Wkで偏微分すると
-ywTx<0の場合
関数はずっと0、wkで偏微分しても全て0、勾配は0
-ywTx=0の場合
「滑らかでない点では微分できない」
勾配の値を決めることができない
劣勾配という概念の導入
勾配の代わりに劣勾配を使える
-ywTx=0では、劣勾配として-yxが使える
パーセプトロンの目的関数の(劣)勾配は上式となる
更新式は上式となる

3.6 サポートベクトルマシン

3.6.1 線形分離可能とは
+1と-1のデータの間に分離超平面を引いて 全てのデータを正しく分離できる時
データは線形分離可能であるという
y(n)(wTx(n) + b) ≥ 0 を満たすw,bが存在する時、線形分離可能
線形分離が可能な場合と不可能な場合
3.6.2 ハードマージン SVMの導出
+1クラスと-1クラスを分離する平面を引いた時、 平面から一番近い各クラスのベクトルを「サポートベクトル」と呼ぶ
サポートベクトルから超平面までの距離をマージンと呼ぶ
分離超平面ではf(x)=y(wTx+b)=0となる
サポートベクトルx*と分離超平面f(x)=0の距離は
サポートベクトルから超平面までの距離の変形(マージン)
サポートベクトル以外のサンプルから 分離超平面までの距離は 必ずマージンより大きくなるので
制約
この制約のもとで マージンを最大化するのが ハードマージンSBVM
マージンを2乗しても結果は変わらないので
L2ノルムの2乗∥w∥2を最小化することが目的となる
3.6.3 ソフトマージン SVMの導出
制約の代わりに分類に失敗した場合にはペナルティ𝛏(t)を与える
ペナルティを目的関数に組み込む
Cは適当な正の定数
全ての𝛏(t)は上式の制約を満たす
目的関数から𝜉を消去
𝜉(t) = max(1-y(t)wTx(t), 0)
第一項を損失項
ヒンジ損失
第二項を正則化項
L2正則化
3.6.4 SVMの目的関数の解釈
目的関数はどのような意味を持つか?
損失項はy(t)wTx(t)≥1の時に0になり、 それ以外には0より大きな値となる
y(t)wTx(t)>0で分類には成功しているが、 損失は0にならない場合がある
正則化項は過学習を防ぐためにある
3.6.5 確率的勾配降下法による SVMの学習
SVMでは目的関数が与えられ、 その目的をどのように達成するかは実装者に委ねられる
SVMも、目的関数にmaxが含まれるので、 勾配を計算する際には場合分けが必要
1-y(t)wTx(t)=0という条件を満たす点では微分不可能な為、 劣勾配を導入する
損失項の勾配の計算
場合わけ
ℓ(w)>0
式の値は0を超える為1-ywTxのwに対する勾配が使われる
損失項の勾配の式
正則項の勾配の式
C∥w∥2を数式として展開すると
C∥w∥2=C(w12+w22+…+wk2+…)
Wkで偏微分すると、wkの出ていない項は無視できる
正則項の勾配の式
確率勾配降下法によるSVMのアルゴリズム
Ifの部分が損失項の勾配の処理
最後のw(t+1)を求める部分が正則化項に対する計算

3.7 ロジスティック回帰

はじめに
ロジスティック回帰 (logistic regression)
SVMと並んで非常によく使われるアルゴリズム
特徴
出力値が確率の制約を満たす
出力値は非負
2つのクラスに対する出力の和をとると1になる
入力xに対して 出力yの値が+1もしくは-1となる 確率P(y|x)を考える
P(y=+1|x)=1/(1+exp(-wTx))
P(y=-1|x)=1-p(y=+1|x)=1-1/(1+exp(-wTx))
wTxの値が大きい(確信度が大きい)時はP(y=+1|x)は1に近くなる
wTxの値が小さい時(確信度が小さい時)ハP(y=+1|x)は0に近くなる
Pの標準シグモイド関数を使った表現
P(y=+1|x)=σ(wTx)
P(y=-1|x)=1-σ(wTx)
統合した式
y=+1,-1のどちらでも利用可能になる
ロジスティク回帰の目的関数
尤度もしくは尤度関数
計算を便利にする為対数をとる
対数をとった為、標準シグモイド関数の対数の和となる
対数関数は単勝増加関数なので、尤度最大化と対数尤度最大化は同じ結果になる
3.7.1 ロジスティック回帰のパラメータ推定
パラメータ推定の場合は数値的に不安定になる場合があるので
目的関数にL1正則化もしくはL2正則化を付加したものがよく使われる
対数目的関数に-1をかけて符号を逆転させ、L2正則化項をつけた目的関数
確率的勾配法による最適化
関数ℓ(w)を上式のように定義
ℓ(w)をwのk次元目となるwkで偏微分
正則化項の偏微分は2Cwk
各データ点における勾配
3.7.2 ロジスティック回帰の解釈
SVMではヒンジ損失max(1-y(t)wTx(t),0)
ロジスティック回帰の損失
ヒンジ損失とロジスティック損失の比較
SVMではy(t)wTx(t)がある程度大きくなると損失は0になる ロジスティック回帰では、0にとても近くにはなるが厳密には0にならない
SVMではy(t)wTx(t)=1の部分で微分不可能になる ロジスティック回帰では微分不可能な点がない

3.8 正則化の効果

3.8.1 過学習を防ぐ
損失項と正則化項の和を目的関数として最小化すると、 どうして過学習を防ぐことができるのか?
過学習は、汎化性能が低い状態
学習データに対してパラメータが多いために起きる
学習データ不足か、パラメータが多すぎる時に起こる
y=+1が表で、y=-1が裏に対応したコインを
1回コインを投げたら表が出たので、 このコインは表しか手せないと推定している
パラメータの値が無限大に発散しようとすると、正則項の値も無限大にななり、目的関数を最小化する点が原点に近づく
3.8.2 疎な解を作る正則化
正則化の効果は過学習を防ぐだけではない
正則化項としてL1ノルムなどを使うと、 性能をほとんど下げずに大部分のパラメータが0になる
疎な解
L1ノルムを正則化とした目的関数の式の形
多次元の場合、最適解のいくつかの次元が0となる
損失関数が凸であれば、原点が最適解となり、解は0となる
L2ノルムを正則化とした目的関数の式
疎な解は得られない
3.8.3 正則化と事前分布
損失関数をL,正則化項をrとした時、目的関数を最小化する問題を考える

3.9 二値分類器の性能評価の方法

よく使われる2値分類期のアルゴリズム
分類区の性能を評価する代表的な指標
正解率(accuracy)
正解率の計算方法
例
380件のデータを処理
350件のデータの分類に成功
正解率は350/380×100=92.1%
正解率では性能を測れないケース
スパムをスパムでないとする誤り
スパムでないのにスパムだとする誤り
2つの分類クラスのデータの数に大きな偏りがある場合も、正解率では見ふ山る
真偽の4つのパターン
真陽性(true positive)
偽陽性(false positive)
真陰性(true negative)
偽陰性(false negative)
適合率
適合率の式
スパムだと分類して、本当にスパムだったもの
再現率
再現率の式
分母はスパムの数、分子はスパムであると分類できた数
F値
F値の式
適合率再現率曲線 (precision-recall curve)

3.10 二値分類のまとめ

二値分類アルゴリズムの目的関数

3.11 多クラス分類

3.11.1 どのような考え方があるのか
3.11.2 1対他法
One versus rest
二値分類器の拡張として、最も自然な手法
入力x∈Rmから、出力y∈{1,2,…,K}への分類
各出力ごとに重みベクトルwy∈Rmを用意する
各出力yごとのスコアをS(x,y;w)=wyTxと定義する
入力xに対する分類結果は、スコアが最大となる出力y*=argmaxxyS(x,y;w)
3.11.3 1対1法
One versus one
全体全法
全ての組み合わせに対して分類器を準備する
分類時には全ての分類器で投票を行う
最も票数が多いものを選ぶ
3.11.4 誤り訂正出力符号法
あらかじめ決められた個数の二値分類器補並べ、 分類時にはそれらの出力結果から最終的な分類クラスを決める手法
例4つのクラスと3つの分類器
ハミング距離が最も近いクラスを分類結果とする
ECOCのアルゴリズム
3.11.5 多クラスSVM
Grammerらは 二値分類用のSVMを多クラス分類へと 自然な形で拡張できることを示した
11
多クラスSVMの目的関数
ξ(t)には、 全てのȳ∈{1,2,…,K}について上式のような制約がある
𝜹y(t),ȳはȳ=y(t)の時は1でそれ以外の時は0であるような数
Φは素性関数や特徴関数と呼ばれる関数 xをyに対応する位置にずらす為のもの
例
入力xが2次元、出力yが1,2,3と3通り
x=(1,2)でy=2であれば、Φ(x,y)=(0,0,1,2,0,0)
Yの位置に対する部分にxを入れ、それ以外を0とする
制約なし目的関数の導出
目的関数の式
多クラスSVMのオンライン学習
確率勾配法での最適化アプローチを行う
勾配の式
3.11.6 対数線形モデル
ロジスティック回帰の多クラス分類への自然な拡張
尤度関数の最大化が目的となる
ロジスティック回帰では出力y=1,y=-1の2通りに対する場合に確率を定義
対数モデルではyに対してK通りの値を考える
Kトオリのyに対して確率を定義するために
それぞれのクラスごとにパラメータを用意する
クラスcに対するパラメータをwcと書く
対数線形モデルで真確率の式
この確率を使った対数尤度の最大化が、対数線形モデルの目的
正則化項がついた目的関数
3.11.7 対数線形モデルの学習
確率勾配法を用いた最適化アプローチを行う
Wkで偏微分した結果の式
偏微分の並べた勾配の式

3.12 自然言語処理への応用例

3.12.1 文書分類
教師あり分類問題
文書データの特徴化
Bag of words(BOW)
単語の集合
単語の語順を考慮しない
全ての問題がBOWで解決するものではない
タスクに応じて工夫することが必要
ストップワードを排除する
出現頻度が高く分類に寄与しない単語を削除する
語形変化を戻す
語形を単一の表現に直す
stemming
隣接単語を利用する
隣接する単語を特徴として利用する
N個の隣接する単語
単語Nグラム
次元数が増える為過学習のリスクが高まる
出現品座の低すぎるNグラムは利用しない
3.12.2 単語分割
分類器を使った複雑な構造の推定
例
単語分割
文が文字列が与えられた時に、単語の列を返すタスク
単語の境界線を見つける
長さbの文字列の配列{t1,…,tn}で
ti∈{0,1}の2つに分ける
文字xiとxi+1の間に単語境界があればti=1,なければ0
SVMやロジスティック回帰で十分な精度で解析できる
27
瀕死情報と文法を使って解く方法もある
それぞれの変数を独立に解くのではなく同時確率を推定する方法もある

第 4 章 発展

4.1 高精度なオンライン学習

はじめに
M次元の入力x∈Rmから、二値の出力y∈{-1,+1}を推定する学習問題
二値分類の中でも、線形分類器について考える
入力と同じm次元のモデルパラメータw∈Rmで特徴付けられる
入力x∈Rmが与えられた時
sign(wTx)で推定する
各入力の重みつきの多数決を取り、 その結果が正であれば出力を+1、負であれば出力を-1とする
学習の目的は正しい出力を推定する重みベクトルを得ること
オンライン学習の共通のアルゴリズム
α,Eはα>0、E≥0を満たす実数
A ∈Rmxmは半正定値行列
任意のx∈Rmに対し
xTA≥0を満たすような行列
入力次元数が大きい場合は、 半正定値行列の代わりに対角行列を近似として使う
z=Axの場合は
Aのk番目の対角成分をakとすると
xk=akxkで求められる
アルゴリズムの意味
一行目で、 重みを0と初期化
どのような入力がやってきても出力は常に0と推定する
何も学習していない状態
三行目で、 現在の分類器が与えられた学習データを 正しく推定できているかを調べる
正解の出力yと推定結果wTxの符号が一致すれば正
正しく分類できていれば正
一致しなければ負
誤っていれば負
|wTx|が0に近ければ分類器に自信がない場合に相当
ywTxが小さければ、大きく間違っている
重みを大きく変更する必要がある
四行目では、 (勾配降下法とよく似た形) αは全部のパラメータに共通の更新幅 Aは各特徴ごとの更新幅
更新式の持つ意味
T番目の時の重みをw(t)、学習データを(x,y)
更新が行われてw(t+1)になったとする
yW(t+1)Tx = y(W(t) + yαAx)Tx = yW(t)Tx + y2α(Ax)Tx =yw(t)Tx + αxTAx ≥ yw(t)Tx
yW(t+1)Tx ≥ yW(t)Tx
更新後に大きくなる
間違い度合いが小さくなる
4.1.1 パーセプトロン
現在の分類器が学習データと違う推定をした場合、 上式のように重みベクトルを更新する
一般的なアルゴリズムの中で
E=0としたもの
α=1としたもの
どのように間違っても常に一定の更新幅で更新
A=Iとしたもの
I:単位行列
特徴ごとに異なる更新幅を使うのではなく、同じ更新母で更新する
単純だが多くの問題で有効
有限回数で答えを見つけられる
改良版
全ての重みの平均化パーセプトロンを使う
単純なものより高精度が得られる
分類時に最後の重みではなく、全てのステップの重みの平均を使う
4.1.2 PassiveAggressive(PA)
ヒンジ損失関数を利用するもの
ヒンジ関数はSVMの時に最も使われた関数
重みベクトルの更新式
ヒンジ損失が0となるような重みの中で、 今までの重みにユークリッド距離で一番近い重みを探す
直感的な説明
ヒンジ損失が0である
今の学習データを十分なマージンで正しく分類できる重みを探す
上記を満たす重みはたくさんある
今までの学習データも同様に正しく分類できる重みを探す
場合分けして考える
ℓhinge(x(t), y(t), w(t)) > 0の場合
制約つき最適化問題の解を求めるため
ラグランジュの未定乗数法を使う
拘束条件がある関数の極値を求める方法
拘束条件gのもとで
ある関数fの極値をとる問題は、f-𝞽gの極値をとる問題に帰着できる
最適化問題の極値を求める式
Wで偏微分をとり、0になる条件
上記の式に偏微分の結果を導入
Τで偏微分をとり、oになる条件は
最終的な更新式
一般的なアルゴリズムに当てはめると
E=1
αは上式
A=I
パセプトロンは間違えた時のみ更新し、常に更新幅は一定
PAノバアイハ正しく分類できている時でも自信がない時には更新 間違えた場合に応じて渾身はばを変えている
更新幅は入力のノルムで正規化されている
学習データにノイズが含まれている場合
学習データに対するヒンジ損失関数が0である
今までの学習を全て忘れてしまうような更新が適用される
制約を緩める必要がある
PA-1更新規則
制約を破った場合のペナルティを線形に考えた場合
PA-2更新規則
規則を破った場合のペナルティを2乗に考えた場合
最終的なPA-1,PA-2の更新式
4.1.3 Confidence Weighted Learning (CW)
重みwが正規分布に従い 生成されると考えたもの
N(μ,∑)は、μ∈Rmを平均、∑∈すもさもを共分散行列とした正規分布
現時点で最も信頼している重みがμであり、 各重みの自信を∑で保持している
∑iiの値が大きければ、その重みの分散は大きい
その重みに対して自信がないことを表現
これまでの分布と近い分布を探す
分布間の近さを表す尺度として カルバック・ライブラー・ダイバージェンスを利用する
学習データを間違えないという条件は、 学習データを確率ηより小さい確率でしか間違えないという条件に変える
分布を求める問題の定式化
PW~N(μ,∑)は、wが正規分布N(μ,∑)によって生成された場合の確率
この最適化は以上のような閉じた形で表すことができる
更新時に各特徴ごとの更新幅を変えることができる
確信度が高い時には、更新幅を小さく
確信度が低い場合には、更新幅を大きくする
精度は高いが計算量が増大する
4.1.4 Adaptive Regularization of Weight Vectors (AROW)
CWがノイズに弱いという問題を克服した手法
ARROWは 学習時に3つの条件を同時に考慮し、 最適化する
一つ目
現在の学習データを正しく分類すること
二つ目
今までの分布に近い分布を探すこと
三つ目
各特徴の確信度を更新ごとに上げること
更新則
4.1.5 Soft Confidence-Weighted Learning (SCW)
CWとARROWの特徴を備えた手法
APの時と同様に制約を緩める
SCW-1
SCW-2
4.1.6 まとめ

4.2 オンライン分散並列学習

4.2.1 確率的勾配降下法の並列化
確率的勾配降下法の定式化のおさらい
学習したいパラメータをw
特にtステップ目での値をw(t)
各ステップにおいて、 学習データはある分布に従って 独立にサンプリングされる
損失関数を 何らかの分布からサンプリングする とみなすこともできる
そこから導出される損失関数ℓ(t)(W)の 期待値が目的関数L(w)に一致する
L(w)を最小化するパラメータwを求める
反復式
目的関数の勾配を直接用いる勾配降下法と比べて、 反復1回の計算コストは小さくなる
損失関数は期待値である目的関数と大きくずれているため、 一回の反復では目的関数の勾配から外れた向きに進む
計算コストがかかる
反復1回の計算コストを抑えながら、 目的関数とのズレが小さい損失関数を扱えれば、 効率的な計算が可能となる
ミニバッチ確率的勾配降下法 (Minibatch stochastic gradient descent)
X(t)はB個の学習データに対応する損失関数の集合
各反復tにおいて、ミニバッチX(t)は独立分布からサンプリングされると仮定
ミニバッチ内の各サンプルに対する勾配の計算を並列に行う
並列化ミニバッチ確率的勾配降下法
アルゴリズム
各プロセスが一回更新を実行するたびに全体を同期する
各プロセスのt回目の更新が終わり、 その結果を全プロセスで共有した後にt+1回目の更新を行う
4.2.2 ParallelSGD
BSPノプロセス間の同期回数を減らす方法
学習が終わるまで同期しない
学習データをp個に均等に分割し、それらをP個の各プロセスに割り当てる
それぞれを最後まで計算して、最後に得られたP個のパラメータベクトルを平均する
アルゴリズム
損失関数が凸で、かつその勾配がリプシッツ連続ならば、 ParallelSGDアルゴリズムは最適解に収束する
プロセスごとの学習データはランダムに選ばれるため
各プロセスにおける学習結果のパラメータは確率変数とみなせる
これらのパラメータの期待値は最適解に一致する
最適解の推定量としての分散は大きいままになる
4.2.3 Iterative Parameter Mixture (IPM)
何回かのパラメータ更新の後にプロセス間でパラメータを同期する
IPM
各プロセスにデータセットを分割して配布し、
それぞれがパーセプトロンによる学習を開始する
ぜプロセスがデータセットを1周するたびに同期する
各プロセスが保持するパラメータを平均で置き換える
アルゴリズム
4.2.4 Stale Synchronous Parallel (SSP)
State Synchronous Parallel(SSP)
BSPを一般化した並列計算の枠組み
パラメータの更新が現在のパラメータに 何らかのベクトルを加算する形で描ける アルゴリズムはSSPにより並列化できる
アルゴリズム

4.3 深層学習で使われるオンライン学習

複雑な非線形モデルに対する効率的な学習方法
4.3.1 フィードフォワードニューラルネットワーク
Feed-foward neural network
入力層、1以上の隠れ層、出力層からなる多層の計算手順
各層は多数のユニットからなり、基本的に各ユニットは入力に 活性化関数(activation function)を適用した値を活性(activation)として持つ
入力層は、入力事例xの各次元値がそのまま活性として用いられる
出力層は目的に応じて特殊な関数が用いられる
D段のフィードフォワードニューラルネットワークにおいて
i∈{1,…,D}層目の活性ベクトルhi
活性化関数をfiとすると
hiはi層目の重み行列Wi及び バイアスベクトルbiを用いて 上式のように表される
活性化関数fiは成分ごとに適用される
隠れ層における活性化関数として恒等関数id(x)=xを使う場合
非線形の関数を使うことで表現力が上がる
代表的な活性化関数
シグモイド型関数だと、 学習が進むにつれて勾配の値が0に近づき、 局所解への収束が遅くなる
区分線形な活性化関数が使われる
単純なヒンジ関数f(x)=max(0,x)
4.3.2 誤差逆伝播法による勾配計算
確率的勾配降下法で学習するには、 活性に対する勾配計算が必要になる
最適化すべきパラメータは 各層の重み行列Wi及びバイアスベクトルbi
損失関数ℓの偏微分係数を求めることが目標
式
エッジの入力側ユニットの活性をhi-1,jとし
出力がわユニットの活性に関する損失関数の偏微分係数を∆hikとする
エッジの重みWijkに対する損失関数の偏微分係数
デルタルール
偏微分係数が
入力ユニットの活性、 出力ユニットによる偏微分係数 及び活性化関数の積で求められる
隠れ層の活性による偏微分形雨∆hikの計算
ニューラルねっとを逆向きに伝搬させることで計算できる
各層ごとに順に計算する必要がある
確率的勾配降下法等の学習データに対する 勾配計算の回数が少ないアプローチを利用する
その他のアプローチ
Hessian-Free法
2階微分に基づく効率的な手法
4.3.3 ミニバッチ確率的勾配降下法
ニューラルネットワークではミニバッチがよく使われる
理由
局所解の近傍において収束がより早くなる
確率的勾配降下法では、 最適化の序盤では効率的だが、 局所解の近くに来ると 損失項の確率的な揺らぎがさまだけとなり、 収束が遅くなる
ミニバッチを用いることで 損失項の確率的な揺らぎが抑えられるため、 早く局所解に到達できる
並列計算による高速化に向いている
ニューラルネットワークの誤差逆伝搬法は、 基本的に行列演算と局所的な非線形演算のみで計算できるので
GPUを用いた高速化がしやすい
一般的にバッチサイズとして数十から数百程度の値が用いられる
4.3.4 モーメンタム法
更新方向の分散を抑えるために
勾配の変化を抑える工夫
一つ前の更新における更新方向と現在のパラメータに対する勾配の平均をとる
モーメンタム法 (Momentum method)
巨大なニューラルネットワークの最適化によく使われる
パラメータの更新に損失関数の勾配を直接用いずに、勾配の移動平均を用いる
μ:モーメンタム係数
過去の更新ベクトルをどれくらい重視するかを表す
μ=0の場合、確率的勾配降下法と一致する
μを1に近づけると、更新ベクトルは変化しずらくなる
モーメンテム法の更新の可視化
モーメンタム法は実装が容易
4.3.5 加速勾配法
モーメンタム法は勾配ベクトルに対して更新ベクトルの方向に感性をつけたものと考えられる
更新の式
Nesterovの加速勾配法(Nesterov’s accelerated gradient)
勾配を計算する位置を少しだけずらす
4.3.6 パラメータの不安定性
不快ニューラルネットワークを最適化する場合、 誤差逆伝搬法により確率的勾配降下法を用いるために、 解決すべき課題がある
各ユニットの活性の微分係数や重み関数などの値が小さすぎると、 入力槽に地下スゼクに連れて伝搬されるごさが小さくなる
最適化が進まなくなる
極端に大きすぎても精度が保てなくなる
パラメータの初期値や学習率に敏感
ハイパーパラメータの最適化はモデル選択の問題として捉えられる
交差検証法やBaysian Optimizationなどのメタアルゴリズムを用いるのが一般的
4.3.7 学習率の減衰方法
目的関数が凸関数の場合は、 確率的勾配降下法を最適解へ収束させるためには、 学習率を和が無限大に発散し、 二乗和が収束するような数列にする必要がある
深層学習では、 局所解が多数存在するような非凸関数を最適化する
目的は、任意の局所解に早く収束することではなく 良い局所解に素早く収束すること
大規模深層学習では、 目的関数の値が十分安定した時に減衰するように、 学習率の減衰係数を手動で調整する
4.3.8 AdaGrad·
学習率を自動で調整する方法
確率的勾配降下法の更新式
A(t)∈ℝdxdは勾配を変形させるための正則行列
学習率の代わりに使われる
A(t)として目的関数のヘッセ行列∇2Lを用いるのが「ニュートン法」
学習率の自動調節をA(t)によって達成する
ニューラルネットワークを確率的勾配降下法で学習する場合
学習データによっては一部のパラメータは使用されない
例
活性化関数としてReLUを使用する場合
あるユニットへの入力が負であればそのユニットの活性は0になる
この場合、この不活性なユニットに隣接する エッジのパラメータは勾配が0となる
パラメータは更新されない
直感的に、たくさん更新されたパラメータに関しては、 学習率を小さくした方が局所解への収束が早まると考えられる
勾配の各次元を、その次元の今までの香辛料を用いてスケールさせる
Aを上式のような対角行列とする
g(t)をtステップ目におけるミニバッチの平均勾配ベクトルとする
ηは学習率のスケールを定める定数
AdaGradアルゴリズム
各次元ごとに更新の履歴を見て、 大きく移動してきた次元については 更新ベクトルを縮小する
大きく移動したとは
その次元の平均的な勾配の大きさに対して相対的に考える
AdaGradによる次元Iの更新量は上式で表される
実際は手動で調整したモーメンテム法の方が良い精度が出る場合が多い
4.3.9 RMSprop
非凸な関数の対極的な形状が、 関数の値と勾配という局所的な情報からは予測できない
非凸性の問題に対する一つのアプローチ
学習率を全ての履歴から決めるのではなく、直近の履歴から決める
関数がある程度滑らかであると仮定すると上記のアプローチが成り立つ
パラメータを更新するアルゴリズム
RMSprop
RMSは(root mean square:二乗平均の平方根)の略
ヒューリスティックによる手法
よく似た手法として「ADADELTA」というアルゴリズムもある
4.3.10 vSGD
はじめに
過去の更新履歴ではなく、 損失関数の局所解付近での形状に 性質の良い仮説を置くことで効率化
ミニバッチでない場合のvSGD
ミニバッチの場合のvSGD

第 5 章 性能解析

5.1 オンライン学習の性能

オンライン学習の性能解析により パラメータの更新により良い方向に行っているのか?を判定

5.2 パーセプトロンの学習定理

前提条件
入力をm次元のベクトルx∈Rm
パラメータである重みをw∈Rmとする
sign(wTx)をパーセプトロンの出力とする
sign(z)は、 z≥0の時1、 z<0の時-1 となるような関数
パーセプトロンは、はじめに重みをw(1)=0と初期化する
学習データ(x,y) ,x∈Rm, y∈{0,1}を受け取り
パーセプトロンの推定の結果と学習データの出力が異なれば(sign(wTx)≠y)
重みwを更新
性能解析を行う準備
用語の定義
学習データのマージン
学習データの半径
パーセプトロンの学習定理
パーセプトロンの更新回数の上限は、 学習データの半径と、マージンの大きさのみに依存する
学習データ数や次元に依存しない
データが高次元でも、 データがスパースであれば半径は小さいので、 パーセプトロンの更新回数を少なくできる

5.3 線形分離可能でない場合の パーセプトロンの学習定理

パーセプトロンは学習データが線形分離できない場合でも、 多くのデータを分類できる
学習データのペナルティ
学習データのぺナルティのノルム
線形分離可能ではない場合のパーセプトロンの学習定理
学習データが線形分離可能でない場合でも、 パーセプトロンの更新回数(間違った回数)は、 半径RとペナルティノルムDにのみ依存する

5.4 リグレット解析

はじめに
リグレット解析(regret analysis)
アルゴリズムが最適な戦略を取った場合と比べて どの程度悪かったか、そのリグレット(後悔)を測る とこでアルゴリズムの性能を測る
リグレット解析の問題設定
プレイヤーは毎回、可能なアクション集合Kから一つのアクションθ∈Kを選択する
その後にコスト関数fが提示され、その分のコストf(θ)が決まる
例:株の投資
プレイヤーはどの会社にいくら投資するかというアクションを選択する
コスト関数は各会社の株価の、その日の減少分
減少分が-100円であれば、100円株価が上昇したという意味
コストの合計は減少分の合計
プレイヤーのアクションを決める方法を戦略と呼ぶ
プレイヤーはどのような戦略を取れば 合計コスト∑(t)f(t)(θ(t))を最小化できるのか
コスト関数f(t)がわからない場合でも、 合計コスト最小化ができるような戦略を取ることができるのか
同じアクションしかとらない戦略
θ*とする
ある戦略のリグレットは上記のように定義される
最適な(固定)戦略を取っている場合と比べて、 現在の戦略がどれくらい悪いのかを測り
あの戦略を取っていればと考えるのがリグレット(後悔)
リグレットはどのような意味を持つのか?
Regretγ(A)が試行回数Tに対して線形の時
鳥だけ試行回数を重ねても、最適な固定戦略との差は縮まらない
Regretγ(A)が試行回数に対しTの線形関数より大きい時
試行を重ねるにつれ、最適な固定戦略との差は縮まる
リグレット解析はオンライン学習を特殊ケースとして含む
オンライン学習のパラメータθ(t)∈Rmをプレイヤーのアクション
アクションはデータ(x,y)ではなく、パラメータ
オンライン学習では学習者はパラメータ選択というアクションをする
損失関数f(t)(θ) =(x(t), y(t), θ)をコスト関数とする
リグレット解析は、 問題があまり大きく変化しない場合に適用される
固定戦略との差
問題が大きくなると固定戦略のコストが大きくなる
5.4.1 FollowTheLeader(FTL)
最も単純な戦略
これまでのコストの合計を最小にするような アクションを次のアクションとする方法
T回目のアクションθ(t)を上式のように定義する
Follow The Leader (FTL)
うまくいかない例
アクションが1次元-1≤θ≤1の中の点
I番目のコスト関数をf(t)(θ)=(1/2)(-1)tθとする
FTLの取るアクションは
最初はθ(1)=0
次はθ(2)=-1
θ(3)=1
-1と1の間を行ったり来たりする
コストは最初以外は常に1/2
最適な固定値はθ=0、コストの合計値は0
最適な固定値に近づかない
5.4.2 RegularizedFollowTheLeader(RFTL)
FTLの改善
アクションが振動してしまう場合にFTLは問題となる
コスト関数以外に何らかの制約を加えてアクションを安定させる
T回目のアクションθ(t)を上式のように定める
R(θ)は凸関数
正則化関数
Η≥0はどの程度正則化を考慮するかのパラメータ
Regularized Follow The Leader (RFTL)
RFTLのリグレット
前提条件
半正定値行列Aに基づくノルム
コスト関数のノルム
実行可能領域の直径
RFTLのリグレット
どんなコスト関数がやってきても動的に対応できる枠組み
5.4.3 損失関数が強凸関数のリグレット
損失関数が強凸関数の場合は、勾配降下法を用いて、さらに小さいリグレットを得ることができる
強凸という概念
ある関数f(x)がα-強凸とは
∇2f(x)≥αIであると定義する
∇2f(x)はfのヘッセ行列
A≥Bとは、行列A-Bが半正定値行列であることを示す
例:
二乗誤差関数f(x)=∥x-a∥22は1-強凸関数
強凸な損失関数に対する勾配降下法のリグレット

第 6 章 実装

6.1 ベクトルの実装

はじめに
自然言語処理のBOWでは、 非常に高次元になる(10万〜100万というオーダー)
非零要素は数十〜数百
数百分の一から数千分の一
疎ベクトル(sparse vector)
密ベクトル
大半の要素が非零
6.1.1 ベクトルの内部表現
密ベクトルの場合
全ての次元の情報を、 浮動小数点の配列としてメモリの連続領域に配置する
疎ベクトルの場合
非零の要素だけをメモリに持っておく
非零の次元(整数値)とその値のペアのみを保存する
計算量
6.1.2 内積計算
ベクトル演算
内積
疎と疎
両方に含まれる非零の要素のみ計算
疎ベクトル同士の内積計算
密と密
一番シンプル
内積計算アルゴリズム
各要素ごとに掛け合わせていくだけ
ベクトル化を行うと、CPUのベクトル演算命令を使って効率化できる
数倍早くなる
コンパイル時にベクトル化して効率化
疎と密
0に何をかけても0
内積計算アルゴリズム
疎ベクトルx中の非零要素のみで計算
6.1.3 ベクトルの加算
積算と同様に各次元ごとに行われる
密ベクトル同士の加算
アルゴリズム
密ベクトルに疎ベクトルを加算
0に何を足しても結果が変わらないことを利用
アルゴリズム
疎ベクトル同士の加算
両者の非零要素のみをマージ
いずれかが非零の場合は要素を全て利用する

6.2 アルゴリズムの実装

6.2.1 平均化法の効率的な実装
過去のパラメータを取っておいて、最後に平均する
パラメータベクトルが安定しない問題に対応
平均化パーセプトロン
アルゴリズム
平均化確率的勾配降下法(average stochastic gradient descent, ASGD)
単純に平均をとると計算効率が悪くなる
各更新における差分に重みをかけながら足し込んでいく
式
6.2.2 lazyupdate
入力データが疎ベクトルの時は計算が効率化できる
正則化項の計算では全ての重みを計算しなくてはならない
Lazy updateによる対応
自然言語処理等で対応
アルゴリズム

6.3 浮動小数点数における制約

6.3.1 浮動小数点数の仕組み
計算機の内部ではあらゆる情報(実数値も)は0と1のバイナリ形式となる
実数値は「浮動点小数点数」によって表現される
浮動小数点とは
実数値の表現方法の方式の一つ
正負の符号の他に、仮数部と指数部の2つの情報に分けて表現する形式
実数xの表現方法
s:符号部(バイナリ)
1ビット
0か1
f:仮数部(バイナリ)
52ビット
1以上2未満
e:指数部(バイナリ)
11ビット
符号付き整数値
B:基数
2で固定
IEEE754で規定
正規化数と呼ばれる
正規化数以外の数
0
無限
非数(NaN)
正常な値で亡くなった数
例:0/0を計算した時
非正規化数
通常の正規化数の指数では表現できないくらい0に近い値
非正規化数に対する計算は正規化数の計算の100倍近くなる
6.3.2 巨大な実数値の扱い
実装する際の気をつけなくてはいけないポイント
浮動点小数の制約によるオーバーフローやアンダーフロー
ロジスティック回帰で出現する指数関数では、容易にオーバーフローする
結果がオーバーフローとなると無限大として扱われその後は何を足しても引いても無限大になる
アンダーフローは0として扱われる
logsumexp関数による回避
6.3.3 桁落ち
浮動小数点の正数と不数の加算がプログラムに含まれている時
軽落ちが発生する可能性がある
極めて値の近い浮動点小数点数の現在を行うと、 正確な計算結果が得られなくなる
例:x=1.001001, y=1.000000とした時
有効数字が十進数で4桁だと、x=1.001, y=1.000となり、x-yは0.001となり下の行の情報が消える
√(x+e)-√xは桁落ちが起きる
E/(√x + √(x+e))に変形すると、 桁落ちを回避できる
CWの計算で利用する

付録 A

A.1 式(3.35)の導出
A.2 ラグランジュ未定乗数法とKKT条件
A.3 CWの変数
A.4 AROWの変数
A.5 SCWの変数
A.6 SSPを用いた並列確率的勾配降下法のリグレット解析