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 が与えられた時の出力yの条件付き確率分
布P(y| x)を、N 個の入出力ペアである訓練データ集合{( x(i), y(i))}i=1Nをもとに推定する問題
 出力が実数値 y 2 Rである場合が「回帰」

 y が離散値、出力の取りうる集合Yが：– 2クラス分類：+1 と -1 の2値– 多クラス分類：{1,2, …,C}のC通りのような場合が「分類」
 分類問題における出力を、特別にクラスと呼ぶ。

4

THE UNIVERSITY OF TOKYO

回帰手法でも分類問題を解くことは可能ですがそれは必ずしもベストの方法ではありません 目標とする出力値を y(i) 2 { +1, -1 }とすれば、形式的には2クラス分類に回帰手法を適用することは可能 実際は訓練データの出力を y(i) 2 {+1,-1}とするのではなく、出力が+1の訓練データの数を|N+|、出力が-1の訓練データの数を|N-|とすると y(i) 2{+1/|N+|}, -1/|N-|}としたほうがよい 多クラス分類の場合にも、データが C 個のクラスの各々に属するかどうかを{+1, -1}で表し、出力値をベクトルで書けば（ベクトル出力に一般化した）回帰手法を適用できる
 しかし、2乗誤差を損失関数とする線形回帰では、確率モデルの仮定として「線形モデルの出力にガウス的なノイズが載る」と仮定– これは、出力が{+1,-1}のどちらかであるとする分類モデルの背後にあるべき確率モデルとしては適当ではない
5

THE UNIVERSITY OF TOKYO

より分類に特化したモデルとして、ロジスティック回帰を中心に紹介します ロジスティック回帰：より分類という目的を直接的にモデル化したモデル
 モデル（パラメータ）の学習は回帰のときのように、逆行列1回のようなシンプルではなくなる

6

THE UNIVERSITY OF TOKYO

分類問題の応用

7

THE UNIVERSITY OF TOKYO

分類の応用は、結構あります 2クラス分類：– 購買予測：ある人xが商品を購入する(y= +1)か否(y = -1)か予測– 活性予測：ある化合物xが、活性をもつ(y = +1)か否(y = -1)か予測– 与信：ある人xが、融資したお金を返済してくれる(y = +1)か否(y = -1)か予測
 多クラス分類：– テキスト分類：ある文書xが、どのカテゴリに属するか（y 2 {政治, 経済, スポーツ, …}）を判別– 画像認識：ある画像xに映っているものが何か（y 2 {自動車, 家,飛行機, …} ）を識別
– 行動識別：ある人に取り付けたセンサーデータxからその人の行動（y 2 {走っている, 歩いている, …}） を識別
8

THE UNIVERSITY OF TOKYO

2クラス分類の複雑なケース：関係の予測 2つのデータの間の「関係の有無」を予測するような場合も2クラス分類の特殊なケースとして考えられる
 2つのデータxとx’の間に関係がある( y = +1 )か否( y = -1 )かを予測

 たとえば：– タンパク質の相互作用予測：2つのタンパク質（データ）の間に物理的な相互作用（チームで働くなど）があるかを予測– 購買予測：顧客と商品の間の購買関係を予測
 入力が2データのペアであるような2クラス分類問題になるので、通常の（1データに対する）2クラス分類問題の一般化になっている
 関係にも複数種類がある場合には、多クラス分類になる

9THE UNIVERSITY OF TOKYO多値分類の極端なケースとしては、構造データのラベルづけ問題などがあります 構造データのラベルづけ問題：自然言語処理における品詞付け問題• 文（単語列）x に含まれる単語のそれぞれに対して、その品詞（{名詞, 動詞, 副詞, …}など複数ありうる）を割り当てるタスク• 他、固有表現抽出、DNAからの遺伝子発見の問題等色々 それぞれの単語を独立のものと考えれば、単語の多クラス値分類問
題となるが、通常、品詞は互いに依存関係にあり（例えば、名詞の後には動詞が来やすいなど）独立に扱うのは適切ではない
 そこで、文に含まれる単語全てに対する品詞の組み合わせ（1単語目が「名詞」で2単語目が「動詞」など）を1つのクラスとして考えると、クラスの数は (可能な品詞数)(文中の単語数)となり、非常に多くのクラスを持つ（しかも、文長に依存してその数が変化する）ような分類問題になる
10THE UNIVERSITY OF TOKYO

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

11THE UNIVERSITY OF TOKYOロジスティック回帰モデル（2クラスの場合）
 2クラス{+1,-1}の場合のロジスティック回帰モデル：

 関数 ¾ は、シグモイド関数（もしくはロジスティック関数）と呼ばれ、実数値を (0,1) の間の値に変換する（＝確率化する）
 ¾ の中身は、ちょうど線形回帰と同じ形
 「線形回帰モデルの出力する実数値を確率値に変換している」
 モデルパラメータは線形回帰のときと同じく(w, b)のD+1個
 w> Á(x) が大きいほど P(y=+1|x; w)も大きいので、wの各次元はÁ(x)の各次元（が正の値をもつこと）が、クラス+1への所属にどの程度貢献しているかを表す
12THE UNIVERSITY OF TOKYO線形回帰のときと同じくbは無かったことにしてしまいます（簡単にするために）
 線形回帰の時と同じく b を w に含めてしまう：– 併せて特徴ベクトルÁ(x)も変更
 モデルはになる ロジスティック回帰を用いた予測は、P(y = +1| x; w) > 0.5 であれば+1、P(y = +1| x; w) < 0.5 であれば -1 と予測すればよい– それぞれ w>Á(x) > 0 と w>Á(x) < 0 に相当する
 つまり、D次元の超平面である w>Á(x) = 0を境に、クラス+1と-1が分割されていることになる– この超平面のことを分割超平面と呼ぶ
13

THE UNIVERSITY OF TOKYO

分類問題の定式化

14

THE UNIVERSITY OF TOKYO我々の目的は、将来のデータに対して、その正解に高い確率（の対数）を与えるモデルを得ることです 我々の目的は（一応）条件付き確率分布P(y| x; w)を推定すること
 その推定の良さをどのように定義したらよいだろうか？
 与えられた訓練データ集合{( x(i), y(i))}i=1N に対してでなく、出力未知の入力 x(N+1)に対して、対応する正しい出力 y(N+1)を出力すること

 いいかえると、入力 x(N+1)に対する y(N+1)の確率（の、なぜか対数）を大きくすることと言える– 確率0.1と0.2の違いと、0.8と0.9の違いはどちらも0.1の差であるが我々は前者の差を重く見る（対数をとる＝比で考える）– この値の符号を逆転したものは、情報理論における符号化の文脈において、データを符号化するのに必要な記述長を表す。
• 記述長は短いほうが良い＝効率良く符号化できるほうが良い
15

THE UNIVERSITY OF TOKYO我々の（最大化すべき）目的関数は、未知データの対数尤
度の、真のデータ分布による期待値です log P (y(N+1)|Á(x(N+1)); w)を大きくするのが目的とするとして、我々は、次にどのような(x(N+1), y(N+1))が来るかは知らないので、これを直接大きくすることはできそうにない– 訓練データ集合{(x(i), y(i))}i=1N を使うしかない (x(N+1), y(N+1))を生み出している確率分布Q(x(N+1), y(N+1))を考えてみる
 我々が最大化したいのは、log P (y(N+1)|Á(x(N+1)); w) の Q(x(N+1), y(N+1))についての期待値であるといえる

16THE UNIVERSITY OF TOKYO

未知データの対数尤度の、真のデータ分布による期待値は、訓練データの対数尤度で近似されます 訓練データおよび将来のデータ{(x(i), y(i))}i=1N+1は、すべて同一の分
布 Q から独立に取り出されたものとすると– 大数の法則：独立なサンプルの平均は、サンプル数を大きくすると、その期待値に近づくから

 期待値の代わりに対数尤度の和で代用し、これを最大化するようにパラメータを決定する ＝ つまり最尤推定17THE UNIVERSITY OF TOKYOなお、事後確率最大化（MAP推定）からはL2正則化項が出てくるのでした 最尤推定によってパラメータを決定すれば：

 事後確率最大化（MAP）推定では： 事前分布が正規分布である場合には：– L2正則化項が出てくる– 以降はMAP推定／正則化を前提として話をすすめる
18

THE UNIVERSITY OF TOKYO

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

19

THE UNIVERSITY OF TOKYO

分類問題の最適解は閉じた形で求まらないことが多いのでパラメータを尐しづつ改善する方法をとります MAP推定の目的関数を最大化する方法を考える– これが最大になるような w を求めたい 回帰の場合とは異なり、これを wで微分し 0 と置いても、連立方程式のような簡単な形（閉じた形の解）は得られない
 そこで、wを尐しづつ改善していくステップを繰り返す– 現時点でのパラメータを w(t) とすると、これを、目的関数が改善するような w(t+1) に更新する

20

THE UNIVERSITY OF TOKYO更新の差分d(t)について目的関数を最大化します 更新の差分d(t)はどのように求めたらよいであろうか？
 我々が実現したいことは L(w(t+1)) すなわちをd(t)について最大化すること、つまり、d(t) = argmaxd L(w(t+1) + d(t))

を解くことである

21

THE UNIVERSITY OF TOKYO

目的関数を現在のパラメータの周りで展開してみます L(w(t+1) + d(t)) はそのままでは扱いづらいので、これを現在のパラメータw(t)の周りでテーラー展開してみると：– r(w(t)) は L(w(t+1) ) の w = w(t) における勾配ベクトル：– H(w(t+1) )はヘッセ行列とよばれる D£D 行列– 最後のO(d3)は3次以上の項を表すとする
 勾配は目的関数L(w) のw=w(t)の周りでの傾き具合を、ヘッセ行列はさらにその「曲がり具合」を表す
22

THE UNIVERSITY OF TOKYO

高次の項を打ち切って目的関数を近似し、最大化すると、ニュートン法の更新式が得られます 3次以降の項を省略して目的関数の近似をつくる：

 これの偏微分を計算してみると：

 これを 0と置いて解けば、解はのように求まるので、更新式は：

 この更新式によってパラメータ更新を行う最適化法をニュートン法と呼ぶ
23

THE UNIVERSITY OF TOKYO近似は必ずしも正しくないので、パラメータ更新の方向だけを採用し、更新量は学習率として別途決めることにします もしも近似式が正しければ、w(t+1) は目的関数を最大化する解となる– そもそもこの近似が正しければ、更新を繰り返す必要は無い（= 2次関数） しかし、実際にはこの近似式は「近似」であるので、ここで求まるw(t+1) は、あくまで目的関数を2次近似したときの最適解である。
 そこで、パラメータの更新分の方向だけを採用し、その方向にパラメータをどれだけ動かすかは別途決めるという考え方もできる 更新のステップ幅を決定する正の定数 η(t) を導入すると：– η(t) は学習率などと呼ばれる24THE UNIVERSITY OF TOKYO

学習率 η(t) の決定方法：線形探索などを行います η(t) の簡単な決定方法：– 十分に小さい定数に取る– η(t) = 1/tなどとする（ステップ幅が次第に小さくなっていく）
 もう尐しきちんと決めたい場合には η(t)の線形探索を行う
つまり、1変数最適化問題を解く η(t) の簡便な探索方法としては、η を適当な初期値から初めて：
1. もし L(w(t)+ηd) > L(w(t)) となるならば、その η を η(t) として採用

2. そうでないならば η を1/2倍してステップ1へ

25

THE UNIVERSITY OF TOKYO

最急勾配法：もっとも目的関数が増加する方向にパラメータを更新する簡便な方法です （線形探索付きの）ニュートン法の更新式を実行するためには、以下の2つの計算が必要：– 現在のパラメータw(t)における勾配ベクトルr(w(t))• これは比較的易しい（尐ない計算量）– ヘッセ行列の逆行列 H(w(t))-1• これをパラメータ更新の度に計算することは大変 そこで、単純な近似として、ヘッセ行列の逆行列をH(w(t))-1 ≡ -I と置いてしまうことにすると、更新式は：
 目的関数が最も大きい方へ変化する方向r(w(t)) に向かってパラメータを更新するので 最急勾配法と呼ぶ
26
THE UNIVERSITY OF TOKYO

パラメータの更新式における勾配r(w(t))を具体的に計算してみます 目的関数を w で偏微分すると、

 モデルとしてロジスティック回帰を用いることにする、
つまり P(y(N+1) = +1| Á(x(N+1)); w) ≡ ¾(w> Á(x(i)))とする

 以下の2つの事実：–– シグモイド関数の微分：
より偏微分が計算できる：

27

THE UNIVERSITY OF TOKYO

若干複雑になりますが、ヘッセ行列も同様に求まります 勾配r(w(t)) をもう一度微分して、ヘッセ行列を求めておくと：

 なお、HP(w) は、P(y(N+1)|Á(x(N+1)); w)に対するヘッセ行列– HP(w) の (k, l)要素は：

28

THE UNIVERSITY OF TOKYO