機械学習プロフェッショナルシリーズ 統計的学習理論 読書メモ

サマリー

機械学習アルゴリズムの統計的性質に関する理論を用いることで、機械学習アルゴリズムの性能や、データセットのサイズや複雑度による影響が理論的に解明され、モデルの選択や学習プロセスの改善を行うことができる。ここではこの統計的学習理論について機械学習プロフェッショナルシリーズ「統計的学習理論」をベースに述べている。

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

機械学習プロフェッショナルシリーズ 統計的学習理論 読書メモ

「ていねいな説明が感動的！ しっかり、よくわかる！ 学習手法を使いこなすには、確率・統計に根ざした基礎理論が不可欠。「カーネ ル法」「サポートベクトルマシン」「ブースティング」などの重要概念の自然な 導入を図った。2値から多値まで、現実のデータに即した手法が学べる一冊。」

まえがき

機械学習アルゴリズムの統計的性質に関する理論
一様大数の法則
国内外で多数の記述
Fundations of machine learning
普通カーネル
判別適合損失

第1章　統計的学習理論の枠組


1.1 問題設定

はじめに
過去の経験を将来の意思決定や予測などに役立てたい
今まで起こった事柄と、将来起こりそうな事象の間に何らかの相関がなければならない
過去に起こったことと全く同じことが将来起きることはない
過去の経験と将来の出来事とのあいだの「緩いつながり」を技術する言葉として、確率論や統計学が用いられる
観測された事象から役に立つ情報を抽出し利用することを「学習する」と表現する
データ
観測によって得られる情報を「データ」とよぶ
入力データ
入力xがとりうる値の集合を「入力空間(input space)」
出力データが有限集合に値をとる時、その値をラベルという
とりうるラベルが2種類の時、入出力データ(x,y)を2値データ、ラベルが3種類以上の時多値データとよぶ
仮説(hypotheses)
入力空間から出力集合への関数を「仮説」という
仮説の集合を「仮説集合(hypothesis set)」という
判別器(classifier)・ 判別関数(discriminant function)
有限集合に値をとる仮説を「判別器」とよぶ
判別器を記述するために用いられる実数値関数やベクトル値関数を、判別関数とよぶ
損失関数(loss function)
出力値と予測結果の間の誤差を測る関数を「損失関数」と呼ぶ
損失関数の値が大きいほど、誤差や損失が大きい
観測データから適切な仮説を学習するアルゴリズムを設計することが「機械学習」の主要なテーマ
統計的学習理論 (statical learning theory)
学習アルゴリズムにより得られる仮説の予測精度を評価し、性能を向上させるための指針を与える裏面的枠組み

1.1.1 判別問題

出力が有限集合yのラベルに値をとる時、 入力データから対応するラベルを予測する問題を判別問題 (classification problem)という
ラベルの候補が2種類(|y|=2)の時2値判別問題 (binary classification problem)
3種類以上(|y|≥3)の時、多値判別問題(multi class classification problem)
判別問題例
迷惑メール分類
入力データ
メールのテキスト
出力ラベル
迷惑メール(spam)と通常メール(nonーspam)
ℓerr(ȳ, y) = 1[ ȳ ≠ y] {1, y≠ŷ, 0, y=ŷ
0-1損失(0-1 loss)
クレジットカードの不払い分類
支払い可能な客を不払いとする場合と、支払い不可能な客を支払い可能とする場合では、被る被害が異なる
0-1損失を拡張する
ℓerr(ȳ, y) = 1[ ȳ ≠ y] {l, y≠ŷ, 0, y=ŷ
出力を1ではなくする

1.1.2 回帰問題

出力が実数値をとる時、入力データから出力を予測する問題を回帰問題(regression problem)と呼ぶ
例:株価や電力の予測
出力と完全に一致する値を予測できない
予測の精度を測る損失関数として 2乗損失(squared loss)を使う
ℓ(ŷ, y) = (ŷ - y)2

1.1.3 ランキング問題

2つの入力データの組(x, x') ∈ 𝓧2
xの方がx'より好ましければy=+1, そうでなければy=-1
入出力データ(x, x', y)
xの方が好ましければh(x)>h(x')、 そうでなければh(x)≤h(x')
h1=h(x)
h2=h(x')
ĥ=(h1,h2) ∈ ℝ2
出力ラベル y ∈ {+1, -1}
0-1損失
ℓ(ĥ, y) = {1, y(h1-h2) ≤ 0, 　　　　{1, その他
例:ウェブ検索
ある検索ワードに対して
検索エンジンが検索結果のページの一覧(x1,x2,...)を返す
ユーザが選んだページxiが、他のページより好ましいものを定量化
例:コンピュータによる将棋の対戦
候補となる手の良し悪し

1.2 予測損失と経験損失

データ(X,Y)が従う確率分布Dのもとでの期待値を𝔼(X,Y)~D[...]
𝔼[...]
予測損失(predictive loss)
損失関数ℓ(ý, y)
「仮説hの予測損失R(h)」を、 テストデータ(X,Y)の分布における 予測値h(X)の損失の期待値
R(h) = 𝔼(X,Y)~D[ℓ(h(X),Y)]
予測判別誤差 (predictive classification error)
0-1損失ℓerrをRerr(h)と表す
学習における通常の問題設定では、 データの分布は未知なので、 予測損失を計算することはできない
経験損失(empirical loss)
観測されるデータ(X1,Y1),...,(Xn,Yn)
入出力関係を仮説hで説明する
損失関数ℓ(ŷ, y)を用いて誤差を測る時、 観測データに対する仮説hの経験損失Ȓ(h)を、 予測値h(Xi)と観測値Yiとの間の損失の平均値
経験判断誤差 (empirical classification error)
予測損失と経験損失の間に成り立つ関係
多くの問題は、予測損失を最小化する仮説を求める問題として定式化
正確な予測損失の値は未知だが、近似値として経験損失が求められる
よって経験損失を最小化することで適切な仮説を学習かのあ
学習した仮説の精度を評価するために、経験損失と予測損失の違いを見積もる

1.3 ベイズ規則とベイズ誤差

学習の目的は、予測誤差をできるだけ小さくする仮説を求めること
定義1.1 ベイズ規則・ベイズ誤差
損失関数ℓを定めた時、
任意の可測関数h:𝒳→𝒴のもとでの予測損失の下限
損失関数ℓのもとでのベイズ誤差 (Bayese error)
下限を達成する仮説が存在する時
ベイズ規則(Bayes rule)
損失関数を定めたとき、ベイズ誤差はデータの確率分布から定まる値
予測誤差を最小にする仮説?
損失関数ℓ(ŷ,y)
テストデータの分布P
条件付き期待値
R(h)=𝔼X[𝔼Y[(ℓ(h(X),Y)|X]]
各入力X=xにおける条件付き期待値
𝔼Y[ℓ(h(x),Y)|x] = ∫ℓ(h(x),y)dP(y|x)を最小にする仮説h
𝔼Y[ℓ(h,Y)] = ∫ℓ(h,y)dP(y)を最小にするh∈𝓎
例1.1 (判別問題)損失関数として0-1損失を用いる
入力xが与えられた時、最も出現する確率が大きなラベルを予測ラベルとする仮説が最適
例1.2 (回帰問題) 回帰問題におけるベイズ規則
例1.3 (ランキング問題) 判別問題として
受信者操作特性曲線 (recider operating characteristic curve, ROC curve)
ROC曲線の下側の面積を曲線下面積 (area under the curve, AUC)
仮説hが入力にかかわらずランダムな場合、ROC曲線は45°(TP=FP), AUC(h)=0.5
ランダムな予測よりも良い仮説を選べばAUCの値は0.5より大きくなる
ベイズ規則h0はAUCを最大にする仮説により与えられる
ベイズ誤差は1-AUC(h0)
ベイズの識別規則
観測データXと所属するクラスの間に確率分布が仮定される識別問題に適用される
例:医療検査:検査項目の値と健康状態には相関があるが、その影響は確率的
ベイズの定理
事後確率
観測データXが与えられた下でそれがクラスCiに属する条件先確率
事前確率
クラスCiの生成確率
尤度分布
クラスが与えられた下での観測データxの確率分布
周辺確率
観測データxの生起確率
定理式
最大事後確率基準
観測データをx、識別クラスをCi(i=1,...K)とすると
ベイズの識別規則は上式で定義されるバゴ確率が最も大きなクラスに分類される
ベイズの識別規則
クラスCiとクラスCjの識別境界は、事後確率が等しくなる所
P(Ci|x)=p(x|Ci)xP(Ci)/p(x) = p(x|Cj)xP(Cj)/p(x)=P(Cj|x)
識別クラス=arg max p(x|Ci)P(Ci)
例
ある町1000人をランダムにサンプルしたデータ
飲酒と喫煙の有無から、健康状態を予測するためのベイズの識別規則を導く
事後確率を特徴(S,T)の全ての組み合わせについて求める
P(G|S,T)=P(S,T|G)xP(G)/P(S,T)
各クラスの事前確率
P(G=1)=800/1000
P(G=2)=200/1000
クラス条件付き確率P(S,T|G)については、SとTの間に条件付き独立P(S,T|G)=P(S|G)P(T|G)が成り立っていると仮定
喫煙に関するクラス条件付き確率P(S|G)
P(S=1|G=1)=320/800=2/5
p(S=0|G=1)=480/800=3/5
P(S=1|G=0)=160/200=4/5
P(S=0|G=0)=40/200=1/5
飲酒に関するクラス条件付き確率P(T|G)
P(T=1|G=1)=640/800=4/5
P(T=0|G=1)=480/800=3/5
P(T=1|G=0)=160/200=4/5
P(T=0|G=0)=40/200=1/5
確率

1.4 学習アルゴリズムの性能評価

学習アルゴリズムは、観測データの集合から仮説集合への関数と解釈される
ある学習アルゴリズムを用いる時、データS={(X1,Y1),...,(Xn,Yn)}から得られる仮説をhsとする
学習アルゴリズムの性能を評価する方法
損失関数を定めると、学習された仮説hsの予測損失としてR(hs)が定まる
確率的に得られる様々な観測データSに対して、予測損失はいろいろな値をとる
観測データSの分布Dに対する予測関数の期待値
期待予測損失
アルゴリズムの平均的な性能の評価
大義1.2 統計的一致性
ベイズ誤差に近い予測損失を達成する仮説を求めれれば、精度の高い予測を実現することが可能

1.5 有限な仮説集合を用いた学習

1.5.1 予測判別誤差の評価

仮説集合が有限の場合の学習された仮説の予測損失を評価
2値判別問題
有限な仮説集合H={h1,...,hT}
各仮説は入力空間Xから2値ラベル{+1,-1}への関数
ある分布Pに従う学習データS={(X1,Y1),...(Xn,Yn)}が与えられた時に、 経験判別誤差を最小にする仮説を出力する学習アルゴリズム
hs=argminȒerr(h)
補題1.3 へフディングの不等式 (Hoeffding's inequality)
確率変数Zは有界区間[1, 0]に値を取る
確率変数Z1,...,Znは独立にZと同じ分布に従う
任意のε>0に対して、上記の式が成り立つ

1.5.2 近似誤差と推定誤差


1.5.3 正則化(regularization)

適切な大きさの仮説集合を学習するための代表的な方法
大きな仮説集合を用いると推定誤差が大きくなるため、 学習の結果得られる仮説の予測判別ごさが大きくなる傾向がある
小さな仮説集合で十分対応できる場合には、大きな仮説集合を使わないようにすることが必要
仮説に対するペナルティを考慮しながら、 経験判別誤差をできるだけ小さくするような学習を行う

第2章　仮説集合の複雑度

はじめに

仮説集合の複雑さを図るための尺度として、 VC次元とらでマッハ複雑度を紹介
これらの尺度によって、予測損失と経験損失の関係がどのように統制されるか説明

2.1 VC次元

VC,VapnikとChervonenkisの頭文字から取る
主に2値判別問題のための仮説集合に対して定義される複雑度
多値問題や回帰問題の場合に拡張することも可能
VC次元は、集合族の組み合わせ的な性質をとらえるための量なので、組み合わせ論などにも応用
仮説h∈Hは、入力空間Xから|Y|=2であるようなラベル集合Yへの関数とする
VC次元は、どのようなラベル付けにも対応可能な仮説が存在するようなデータ数の上限を意味する
補題2.1 サウアーの補題 (Sauer's lemma)
2値ラベルに値を取る仮説集合HのVC次元がdのとき、 n≥dに対して常識が成り立つ
定理2.2
2値ラベルに値を取る仮説集合 H⊂{h:𝓧→ {+1, -1}のVC次元をd<∞とする 学習データ(X1,Y1),...,(Xn,Yn)は独立に同一の分布に従う 式 定理2.3 ラドンの定理 (Radon's theorem) 任意の点集合S={x1,...,xd+2} ⊂ ℝdに対して S=S1∪S2, S1∩S2=⦰かつconv(S1)∩conv(S2)≠⊘になるような分割S1,S2が存在する 例:パラメータの次元とVC次元が一致しない場合 線形判別機では判別器を指定するパラメータの次元とVC次元が一致 2.2 ラデマッハ複雑度 ラデマッハ複雑度、経験ラデマッハ複雑度は、 VC次元と異なり、実数値関数の集合に対して自然に定義される 定義2.4 経験ラデマッハ複雑度 入力空間X上の実数値関数からなる集合を𝓖⊂{f:X→ℝ} 入力点の集合をS={x1,...,xn} ⊂ Xとする +1と-1を等確率でとる独立な確率変数をσ1,...,σnとする 𝓖の経験ラデマッハ複雑度(empirical Rademacher complexity)Ȓ(𝓖)は 𝔼σ[・]はσ1,...,σnに関する期待値 経験ラデマッハ複雑度の直感的解釈 σig(xi) > 0なら予測は正しい
Σig(xi)が大きな値を持つ時、十分学習されている
定義2.5 ラデマッハ複雑度
入力点S=(x1,...,xn)が分布Dに従う確率変数のとき
𝓖の経験ラデマッハ複雑度の期待値を ラデマッハ複雑度(Rademacher complexity)

2.3 一様大数の法則

一様大数の法則は、VC次元を用いて予測判別誤差を評価した定理2.2を拡張した定理
ラデマッハ複雑度は、一様大数の法則における誤差に相当
定率2.7 一様大数の法則(uniform law of large numbers)

2.4 タラグランドの補題の証明




第3章　判別適合的損失

3.1 マージン損失

定義3.1 マージン損失

3.2 判別適合的損失

定義3.2 判別適合損失

3.3 判別適合性定理:凸マージン損失

定理3.5 凸マージン損失の判別適合性定理

3.4 判別適合性定理:一般のマージン損失

定理3.6 判別適合性定理

第4章　カーネル法の基礎

4.1 線形モデルを用いた学習

判別問題や回帰問題では、入出力データ(x, y)から入出力の間の関数関係を学習することが主な目間
統計モデルとして入力空間上の関数の集合を設定する必要がある
線形モデル(linear model)
M = {f(x) = βTΦ(x) | β ∈ ℝD}
Φ(x) = (Φ1(x),...,ΦD(x))T ∈ ℝD
入力空間XからD次元空間ℝDへの写像
基底関数Φ1(x),...,ΦD(x)の線形和


4.2 カーネル関数


4.3 再生核ヒルベルト空間


4.3.1 カーネル関数から生成される内積空間
4.3.2 内積空間の完備化
4.3.3 再生核ヒルベルト空間とカーネル関数
4.3.4 ヒルベルト空間の分類と再生核ヒルベルト空間


4.4 表現定理
4.5 再生核ヒルベルト空間のラデマッハ複雑度
4.6 普遍カーネル


第5章　サポートベクトルマシン


5.1 導入
5.2 ヒンジ損失
5.3 C-サポートベクトルマシン


5.3.1 C-サポートベクトルマシンの最適性条件
5.3.2 サポートベクトル
5.3.3 サポートベクトル比と予測判別誤差
5.3.4 予測判別誤差の上界
5.3.5 統計的一致性


5.4 ν-サポートベクトルマシン


5.4.1 ν-サポートベクトルマシンの性質
5.4.2 双対表現と最小距離問題
5.4.3 予測判別誤差の評価と統計的一致性


第6章　ブースティング


6.1 集団学習
6.2 アダブースト
6.3 非線形最適化とブースティング


6.3.1 座標降下法によるブースティングの導出
6.3.2 重み付きデータによる学習と一般化線形モデル


6.4 アダブーストの誤差評価


6.4.1 経験判別誤差
6.4.2 予測判別誤差


第7章　多値判別


7.1 判別関数と判別器
7.2 ラデマッハ複雑度と予測判別誤差の評価
7.3 判別適合的損失
7.4 損失関数


7.4.1 多値マージン損失
7.4.2 判別適合的損失の例


7.5 統計的一致性
7.6 多値判別における判別適合性定理の証明


付録A　確率不等式


付録B　凸解析と凸最適化


B.1 凸集合
B.2 凸関数
B.3 凸最適化


付録C　関数解析の初歩


C.1 ルベーグ積分
C.2 ノルム空間・バナッハ空間
C.3 内積空間・ヒルベルト空間