THE UNIVERSITY OF TOKYO

数理情報工学特論第一【機械学習とデータマイニング】
3章：分類②

かしま ひさし鹿島 久嗣（数理 6 研）kashima@mist.i.～

DEPARTMENT OF MATHEMATICAL INFORMATICS

1THE UNIVERSITY OF TOKYO

「分類」について学びます2

分類問題の定義

分類問題の応用

分類のためのモデル：ロジスティック回帰

分類問題の定式化



学習アルゴリズム：ニュートン法と最急勾配法



パーセプトロン

マージン最大化学習

多クラス分類

勾配法による多クラスロジスティック回帰の学習

多クラスパーセプトロン
THE UNIVERSITY OF TOKYOパーセプトロン

3

THE UNIVERSITY OF TOKYO最尤推定よりもゆるい目標：
正解に負正解よりも高い確率を不える 最尤推定：モデルが訓練データに不える確率（の対数）を最大化するようにパラメータを決定する– 最尤推定は、入力 x(i) に対して、正しい出力 y = y(i) にモデルが不える確率を最大化することを目指している もう尐しルーズな目標を考える：正しい出力（y=y(i)）に対して不える確率を正しくない出力（yy(i)）に対して不える確率より高くする– 条件付き確率に基づいて y を +1 か -1のどちらかに予測する場合、上の大小関係が成り立ちさえすれば、予測は間違えない 最尤推定は、予測が当たるだけに飽き足らず、一層の高みを目指しているともいえる
4
THE UNIVERSITY OF TOKYO

2クラスロジスティック回帰の場合、先の（ゆるい）目標はパラメータで張られる超平面での分割を求めることに一致します P(y(N+1)|Á(x(N+1)); w) が2クラスのロジスティック回帰であるとする
 正解のクラスが y(i)=1である場合、y(i) = 1 である確率が y(i) = -1である確率よりも大きいという条件は： これを整理すると： w>Á(x(i)) > 0
 一方、正解が y(i) = -1の場合は： w>Á(x(i)) < 0
 つまり、上の制約は、超平面 w>Á(x(i)) = 0を境に正例と負例を正しく分割することを要求していることになる

 2つの制約をまとめて書くと： y(i) w>Á(x(i)) > 05

THE UNIVERSITY OF TOKYOパーセプトロンは「正解に負正解よりも高い確率を不える」を実現するシンプルな逐次学習型アルゴリズムです パーセプトロンは 制約 y(i) w>Á(x(i)) > 0 を実現するアルゴリズム
 訓練データを1つづつ処理する逐次学習型のアルゴリズム
 学習の各ステップにおいて、1つの訓練データ( x(i), y(i))を選び、これを用いてモデルパラメータ w の更新を行う
 ( x(i), y(i)) について既に制約が満たされている場合には何も行わない
 制約が満たされない場合に限って以下の更新式を用いてパラメータの更新を行う– パラメータの更新は制約を満たす方向に行われる（後述）6

THE UNIVERSITY OF TOKYOパーセプトロンのアルゴリズム

7THE UNIVERSITY OF TOKYOパーセプトロンのパラメータ更新則は「正解の確率＞負正解の確率」の制約を満たそうとする方向に行われます 更新後のパラメータを用いて、入力 x(i) に対する予測を計算してみると：

 正しいクラスが y(i) = +1 の場合にはがよりも Á(x(i))>Á(x(i)) (必ず0以上の値をとる) だけ大きくなる 一方、正しいクラスが y(i) = -1 の場合には同じ量だけ小さくなる
 つまり、制約を満たそうとする方向にパラメータが更新されている

8

THE UNIVERSITY OF TOKYOパーセプトロンは、制約を満たすパラメータを有限回のパラメータ更新で見つけることができます（もしあれば）
 パーセプトロンアルゴリズムのパラメータ更新回数についての定理
 2つの条件が満たされていると仮定する：[条件1] 全てのデータに対し制約 y(i) w*>Á(x(i)) > 0を満たす、ある理想的なパラメータw*が存在して：• ある正の定数 γ > 0 について y(i) w*>Á(x(i)) > γ が成立する• w* の2-ノルムはkw*k22 = 1である
[条件2] 全ての訓練データについて特徴ベクトル Á(x(i)) のノルムがkÁ(x(i))k22 < R2 である
 このとき、パーセプトロンアルゴリズムが全ての制約を満たすパラメータを発見するまでのパラメータ更新回数 k は高々：（予測の符号を間違える回数）

9

THE UNIVERSITY OF TOKYO

証明（前半） 今 k 回目のパラメータ更新（k 回目の制約丌成立）が起こったとする 更新後のパラメータwNEW と、理想的なパラメータw*との近さを見るために、その内積 wNEW> w*を調べると：: 更新式の定義より: 仮定 y(i) w>Á(x(i)) > γ より
: パラメータ更新回数が k 回であることより

 パラメータ更新のたびに内積が尐なくとも γ づつ大きくなっていく 両辺をkwNEWk 2で割ると：– 左辺にある2つのベクトルの 2-ノルムは共に1– その内積は1以下であるから10THE UNIVERSITY OF TOKYO

証明（後半）
 あとはkwNEWk 2を評価すればよい。
 更新式

より：
: 条件2 kÁ(x(i))k22< R2: 制約の丌成立の仮定より

 パラメータの更新回数が k 回であることから、この丌等式を繰り返し適用することにより kwNEWk22· kR2 すなわち kwNEWk2· √k R
 これを、前頁で導いた丌等式と組み合わせ、g について解くと：11THE UNIVERSITY OF TOKYO

データを完璧に分類できる超平面が存在しない場合でも、パーセプトロンの性能はよいことが知られています 定理では、制約 y(i) w*>Á(x(i)) > 0が成立すること、すなわち、全ての訓練データを間違いなく判別することのできる超平面 w*>Á(x(i)) > 0が存在することを仮定していた
 現実的には真実の P(y|x) は線形モデルよりももっと複雑であったり、あるいはデータにノイズが含まれていたりなどの事情により、この制約は必ず満たされるとは限らない このような場合にも、「最も制約 を破らないようなパラメータw*」と比較して、パーセプトロンアルゴリズムが誤った予測をする回数が小さく抑えられることがわかっている– ここでDは w* の制約破りっぷりを表す
12

THE UNIVERSITY OF TOKYOマージン最大化

13

THE UNIVERSITY OF TOKYOパーセプトロンは「マージン」を正にするように働きます パーセプトロンが満たそうとする制約：は、全ての訓練データ{(x(i), y(i))}i=1Nに対し「正解に対する確率と丌正解に対する確率の差が0より大」が、成り立つことと見ることができる
 つまり：としたときに¢(w) > 0 が成り立つということ– この¢(w)はマージンと呼ばれる– マージンはwによって変化する
14

THE UNIVERSITY OF TOKYOマージンを最大化すると良いような気がしますが、そのままでは定式化に問題があります パーセプトロン（や最尤推定の）とは別の学習目標として、マージン¢(w)を「最大化」するということが考えられる。
– パーセプトロンの掲げる目標である、マージンが0より大きいということだけに飽き足らず、これをさらに推し進めることを目指す マージン最大化を最適化問題として書けば以下のように書けそう： 2クラスのロジスティック回帰モデルを用いる場合のマージンは
 しかし、ここで1つ問題が起こる：– ¢(w)> 0を満たすwが存在したとすると、wの方向を変えずに大きくすることで、マージンをいくらでも大きくできてしまう
15

THE UNIVERSITY OF TOKYOマージンを固定してパラメータのノルムを小さくすることでマージン最大化を2次計画問題として定式化できます 尐し考え方を変えてみる wのノルムを大きくすることでマージンをいくらでも大きくできてしまうのなら、逆にマージン¢(w)を（例えば1に）固定してしまいwのノルムをできる限り小さくすることにする：– ¢(w) = 1としたのには深い意味はない（2でも3でも何でもよい） マージンの定義から、制約式の方を尐し書き換えると：

 この最適化問題は、 2次計画問題と呼ばれる最適化問題
16THE UNIVERSITY OF TOKYO

データを完璧に分類できる超平面が存在しない場合には「制約がなるべく成り立つように」定式化します マージン最大化の定式化は、¢(w*) > 0 が成り立つw*が存在するときには良さそうだが、この制約は必ずしも満たされるとは限らない
 この制約を緩め「制約がなるべく成り立つように」要請する
 制約はy(i) w>Á(x(i)) ¸ 1を要求しているため、これが破られたときのペナルティの大きさを1 - y(i) w>Á(x(i))によって測ることにする
 制約が満たされた時（ペナルティが0）と纏めて書くと、i番目の訓練データに対するペナルティの大きさは max {1 - y(i) w>Á(x(i)) , 0}
 ノルムも併せて最小化すると、最適化問題は：– この形は事後確率最大化のときの対数尤度の項と正則化項に対応
17THE UNIVERSITY OF TOKYO

多クラス分類18THE UNIVERSITY OF TOKYO

多クラスのロジスティック回帰モデル：
クラスの数だけパラメータベクトルを用意します ロジスティック回帰モデルを、多クラスの場合に拡張する– 後に配列データのラベル付けモデル（条件付確率場）に拡張される
 クラスの集合 Y を{1, 2, …, C }に対するCクラスのロジスティック回
帰モデルは：– 各クラス c 2 Y ごとにD次元のパラメータベクトル w(c )が定義されモデル全体としては C D個のパラメータがあることになる– expの中には線形回帰モデルの形が現れており、w(c) は特徴ベクトルのそれぞれの特徴のクラス c への貢献度を表す– 指数を取ることで0以上の値に変換し、さらに正規化することで (0,1) の間の確率値に変換している
19

THE UNIVERSITY OF TOKYO

多クラスロジスティック回帰モデルは、特徴空間を複数の超平面で切り分けます 多クラスロジスティック回帰を用いてクラス予測を行うときには：

 つまりすなわちがすべての y  y* について成立するときy* を出力する
は超平面の片側を指すため、その集合は複数の超平面で切りだされた領域となる Á(x(i)) が丁度超平面上にある場合以外には、丌等式を満たす y* は必ず存在するので、特徴空間が複数の超平面によって切り分けられていることになる 一方、2クラス分類に帰着する方法では、P(y = +1|x; w) = 0.5 を境目とした判断方法では、どのクラスにも属さない場合がありうる
20
THE UNIVERSITY OF TOKYO

多クラスロジスティック回帰モデルには、等価な別の表記があります ロジスティック回帰モデルは以下のように書き直すことができる– パラメータ!はDC次元のベクトル：– 特徴ベクトル  (x,y) もDC次元のベクトル：• x と y の組み合わせに対して定義される• d(・)：括弧の中身が成立するなら1を、しないならば0をとる
 クラス毎のパラメータではなく、特徴ベクトルの側でクラスの違いを吸収することで、パラメータベクトルを1つにしている– 後に紹介する（クラスが実質いくらでもある）条件付き確率場の基本的な形式となる
21

THE UNIVERSITY OF TOKYO

勾配法による多クラスロジスティック回帰の学習

22

THE UNIVERSITY OF TOKYO

多クラスロジスティック回帰モデルを最急勾配法で学習するために勾配を計算しておきます 多クラスのロジスティック回帰の場合の目的関数は：

 これをクラス y のパラメータ w(y)で偏微分してみると：• d(・)：括弧の中身が成立するなら1を、しないならば0をとる
23

THE UNIVERSITY OF TOKYO「(log)  exp」の計算を行うのにはちょっとしたテクニックが必要です 多クラスロジスティック回帰による予測時の確率や学習時の収束判定などのために対数尤度の項を計算する際に現れる
もしくはでは、expの中身が大きいときに計算の途中で桁あふれを起こしてしまう問題がある
 この問題を回避するために、以下の等式を用いることで指数の中身が大きくなることを防ぐことができる

24

THE UNIVERSITY OF TOKYO

多クラスのパーセプトロン

25

THE UNIVERSITY OF TOKYO

多クラスのパーセプトロンもまた、「正解に負正解よりも高い確率を不える」制約を逐次学習によって実現します パーセプトロンが満たそうとする制約：は多クラスロジスティック回帰の場合は、全ての y  y(i) について：
つまり 従って、2クラスの場合と同じように、多クラスパーセプトロンは毎ステップにおいて、ひとつの訓練データ(x(i), y(i)) に対し：
– 上の制約が成り立つ場合には何もしない– 制約が成り立たない場合に限り、この制約を成り立たせる方向にパラメータの更新を行う
26

THE UNIVERSITY OF TOKYO

パラメータ更新は制約を成り立たせる方向に行います 具体的な更新則としては、予測値が最大となるクラスを：とすると、更新式は：

 この更新は結果とし制約を成り立たせる方向に向かう–はよりも大きくなるように–はよりも小さくなるように

27

THE UNIVERSITY OF TOKYO

多クラスパーセプトロンのアルゴリズム

28

THE UNIVERSITY OF TOKYO