THE UNIVERSITY OF TOKYO

総合科目 一般F「数理工学のすすめ」

機械学習入門かしまひさし鹿島 久嗣
情報理工学系研究科
数理情報学専攻2011/5/11

kashima@mist.i.～

DEPARTMENT OF MATHEMATICAL INFORMATICS

1THE UNIVERSITY OF TOKYO

本日の資料は以下のURLからダウンロードできます

http://goo.gl/d9yxG
この講義シリーズのWebページはhttp://goo.gl/ZcLlb

2

THE UNIVERSITY OF TOKYO

レポート課題（4/27+5/11分）
次の2つの課題のうちいずれか：
1. 機械学習／データマイニング関連の図書で興味をもった部分を調べてまとめよ
参考図書の例）–

山西健司：「データマイニングによる異常検知」共立出版（２００９）–

山西健司：「情報論的学習理論」共立出版（２０１０）–

C.M.ビショップ: 「パターン認識と機械学習」 (上)(下) シュプリンガー・
ジャパン（２００８－２００９）

2. 機械学習／データマイニングの現実的な応用例や応用可能性について論文または書物を調べてまとめよ– ただし、引用あるいは参考とした資料は明記すること
3

THE UNIVERSITY OF TOKYO今日は機械学習の初歩的な手法を具体的に紹介します4

機械学習： 教師つき学習と教師なし学習

教師つき学習の例：パーセプトロン



教師なし学習の例：K-平均クラスタリング

THE UNIVERSITY OF TOKYO

機械学習：教師つき学習と教師なし学習5

THE UNIVERSITY OF TOKYOあるなしクイズ：これは「あり」？「なし」？


ヒント：「あり」なものと、「なし」なもの
あり
うさぎ

なし
ねずみ

はがねのつるぎ
きんとき
たわし

てつのおの
あんこ
わたし

では…
– 「ししゃも」は？
– 「ほっけ」は？
– 「しゃけ」は？

6

THE UNIVERSITY OF TOKYO部分文字列に注目してみると…


ヒント：「あり」なものと、「なし」なもの
あり
うさぎ

なし
ねずみ

はがねのつるぎ
きんときたわし

てつのおの
あんこ
わたし

では…
– 「ししゃも」は？ ⇒ あり

7– 「ほっけ」は？

⇒ なし– 「しゃけ」は？

⇒ なし「あり」のグループには鳥の名前が含まれている

THE UNIVERSITY OF TOKYO

仲間はずれさがし：仲間はずれはどれ？


以下のうち、仲間はずれはどれでしょうか？
くもやどかり
たこ
いか
たらばがに
毛がに
えび

8THE UNIVERSITY OF TOKYO

グループ分けしてみると…
「足の数」と「かたさ」で分類してみると…
足の数
グループ１

8本

10本

やわらかい

くも
たこ

いか

かたい

たらばがに
やどかり

毛がに
えび

かたさ

グループ２



グループ３

あるいはもっと安直に、棲んでいる場所に注目すると「くも」であろう
棲んでいる場所

9陸上

水中

くも

その他

THE UNIVERSITY OF TOKYO前述の例は、それぞれ機械学習の2大タスクである「教師つき学習」と「教師なし学習」に対応しています

あるなしクイズの場合：– 「ある」「なし」を区別するルールを不えられた事例から見つける– 未知の対象に対してルールを適用し分類する

仲間はずれ探しの場合：– ある視点から対象をグループ分けする– それぞれのメンバーを評価（この場合、グループに入らないメンバーをみつける）

10

これらはそれぞれ機械学習の2大タスク「教師つき学習」と「教師なし学習」に対応している

THE UNIVERSITY OF TOKYO

教師つき学習は、入出力関係の推定問題です 目的 ：入力 x が不えられたとき、対応する出力 y を予測したい• 入力 x：「ししゃも」や「ねずみ」• 出力 y：「あり」か「なし」か※ 厳密にはこれは教師つき学習の「分類」と呼ばれるタスク
 つまり、y = f (x) となる関数 f がほしい
 しかし、ヒントなしでこれはできない…
そこでヒントとして過去の事例（＝訓練データ）を利用できる– 「うさぎ」は「あり」、「ねずみ」は「なし」、など
 訓練データをもとに入出力関係 f を推定するのが教師つき学習– 正しい出力を不えてくれる「教師」がいるというイメージ– 訓練データは f を「訓練する」ためのデータ
11

THE UNIVERSITY OF TOKYO

教師なし学習は、入力データのグループわけを行います 教師なし学習では入出力関係についてのヒントがない（出力が不えられず、入力のみが不えられる） 入力だけから出力らしきものをつくる必要がある（＝自習） 「あり」「なし」などのラベルが明示的に不えられないので、グループ分けくらいしかできない 目的 ：入力 x が不えられたとき、これらをグループ分けしたい• 入力 x：「くも」や「やどかり」• 出力 y：グループ１、グループ２、…など（明示的なラベルを付ける必要は無い）– 通常グループの数は指定される※ 厳密には教師なし学習の「クラスタリング」と呼ばれるタスク
12

THE UNIVERSITY OF TOKYO

歴史的経緯： 結局のところ、機械学習とは、データ分析技術の一流派のようなものです 機械学習とは、本来「人間のもつ”学習能力”を機械（計算機）にも持たせる」ことを目指す研究分野– もともとは人工知能の一分野として始まる• 論理推論がベース– 現在では、「統計的」機械学習が主流（≒機械学習）• 遺伝子情報処理、自然言語処理、他、ビジネス分野での成功 現在では、データ解析技術一般を指すほかの言葉とあまり変わらない– 統計／データマイニング／パターン認識など。
（多尐のニュアンスの違いはあるが、基本的に好みの問題）
13

THE UNIVERSITY OF TOKYO教師付き学習と教師無し学習は機械学習の基本問題です

機械学習とは、本来「人間のもつ”学習能力”を機械（計算機）にも持たせる」ことを目指す研究分野



学習者を、入出力のあるシステムと捉え、学習者に対する入力と、それに対する出力の関係を数理的にモデル化する– 入力：視覚などからの信号 （実数値ベクトルで表現）– 出力：入力を表す概念、入力に対してとる行動

どうやら2つの重要な基本問題があるらしいということになった– 教師付き学習：入力に対する出力を試行錯誤するうちに、どういう入力のときにどういう出力をすればよいかがわかってくる– 教師無し学習：入力を見ているうちに、どんなものが現れやす
いかなどのパターンが分かってくる
14

THE UNIVERSITY OF TOKYO

機械学習問題の定式化

15

THE UNIVERSITY OF TOKYO

機械学習を実現するためには、入力の数理的表現が必要です

学習機能を計算機上に実現するために、まず、学習問題を数理的にとらえる必要がある

まずは、入力をどう数理的（＝計算機可読な形式）に表現するか？
– 「やどかり」「ねこ」「りんご」は計算機上でどのように扱うか？



出力については比較的自明– 「あり」を+1、「なし」を-1と割り当てる

16

THE UNIVERSITY OF TOKYO

入力の表現：
通常、実数値ベクトル（特徴ベクトル）として表現します 入力を、その特徴量を列挙した D次元の実数値ベクトル x として表現する– x を「特徴ベクトル」と呼ぶ– その領域を「特徴空間」と呼ぶ「今日の気温」などでもよい

赤みの度合いビタミンC含有量

 特徴ベクトル x はどのようにデザインしたらよいか？
→ 完全にドメイン依存。
一般的な解はなく、目的に合わせユーザーがデザインする
17

THE UNIVERSITY OF TOKYO

訓練データ： 教師付き学習では、入力ベクトルと出力の組が複数不えられます 訓練データは、N 個の入力と出力のペア{(x(1), y(1)) , (x(2), y(2)) , …, (x(N), y(N)) }1つ目の入出力ペア

2つ目の入出力ペア...

N個目の入出力ペア– x(i): i 番目の事例の入力ベクトル– y(i): i 番目の事例に対する正しい出力（ならば +1, 違うなら -1）

 教師付き学習：不えられた入力信号に対する、あるべき出力を教師信号として、入出力の関係を学習する

18

THE UNIVERSITY OF TOKYO

教師なし学習では、入力ベクトルのみが複数不えられます データはN 個の入力信号

1つめのデータ

2つめのデータ...

 これらをいくつかのグループに分ける 教師なし学習は、（大げさにいえば）明示的に指定されることなしに、``概念”を形成するプロセスを表している

x (1次元の場合)
19

THE UNIVERSITY OF TOKYO

教師つき学習法： パーセプトロン

20

THE UNIVERSITY OF TOKYO

線形モデル： もっともシンプルな出力予測モデル
 入力 x = (x1, x2, …, xD)> に対し、出力{+1, -1}を予測する分類モデル
fを考える

f (x) = sign(w>x) = sign( w1x1+ w2x2 +…+ wDxD )– sign()は引数が0以上なら+1、0未満なら-1を返す関数– w = (w1, w2, …, wD)> はモデルパラメータ• wd は xd の出力への貢献度を表す– wd > 0なら出力+1に貢献– wd < 0なら出力-1に貢献

21

THE UNIVERSITY OF TOKYO

学習とは、訓練データからパラメータベクトルwを決定することです パラメータw がきまるとモデルf がきまる

f (x) = sign(w>x) = sign( w1x1+ w2x2 +…+ wDxD ) 訓練データからwを決定するのが「学習」{(x(1), y(1)), (x(2), y(2)), …,(x(N), y(N)) } ⇒ w
 基本的には、訓練データの入出力を再現できるようにwを調整する– 出力が y = +1 のデータについては w>x > 0 となるように– 出力が y = -1 のデータについては w>x < 0 となるように– まとめてかくと y w>x > 0

22

THE UNIVERSITY OF TOKYOパーセプトロン：シンプルな逐次学習型アルゴリズム
 パーセプトロンとは：– 制約 y(i) w>x(i) > 0 (for all i)を実現するアルゴリズム– 訓練データを1つづつ処理する逐次学習型のアルゴリズム
 学習の各ステップにおいて、1つの訓練データ( x(i), y(i))を選び、これを用いてモデルパラメータ w の更新を行う (x(i), y(i)) について既に制約が満たされている場合には何も行わない
 制約が満たされない場合に限って以下の更新式を用いてパラメータの更新を行う

w新← w旧 ＋ y(i) x(i)– パラメータの更新は制約を満たす方向に行われる（後述）23

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

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

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)のノルムがkx(i)k22 < R2 である
 このとき、パーセプトロンアルゴリズムが全ての制約を満たすパラメータを発見するまでのパラメータ更新回数 k は高々：（予測の符号を間違える回数）

25

THE UNIVERSITY OF TOKYO証明（前半）※ 過去スライド使いまわしの都合上 w新と wNEWが混ざっていますがご容赦ください （同じものです）

 今 k 回目のパラメータ更新（k 回目の制約丌成立）が起こったとする 更新後のパラメータw新 と、理想的なパラメータw*との近さを見るために、その内積 w新> w*を調べると：
w新> w* ＝ w旧> w* ＋ y(i) x(i)> w*＞ w旧> w* ＋ γ＞kγ

: 更新式の定義より: 仮定 y(i) w*>x(i) > γ より

: パラメータ更新回数が k 回であることより

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

THE UNIVERSITY OF TOKYO

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

 更新式 w新← w旧 ＋ y(i) x(i) より：||w新||2 2＝ ||w旧||2 2＋||x(i)||2 2＋2 y(i) w旧>x(i)· ||w旧||2 2＋R2 ＋2 y(i) w旧>x(i)· ||w旧||2 2＋R2

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

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

THE UNIVERSITY OF TOKYO

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

THE UNIVERSITY OF TOKYO

教師つき学習の応用例

29

THE UNIVERSITY OF TOKYO

教師つき学習の応用例
 信用リスク評価
 テキスト分類
 画像認識30

THE UNIVERSITY OF TOKYO教師付き学習の応用例：信用リスク評価「この人にお金貸して、返ってくるんだろうか？」 ある顧客に、融資を行ってよいか– 顧客 x を、さまざまな特徴を並べたベクトルで表現– 融資を行ってよいか y• 融資を行ってよい（返済してくれる）：+1• 融資してはいけない（貸し倒れる）：-1– マーケティングの文脈では、買ってくれる(+1),買ってくれな
い(-1)
過去に延滞したことがあるか？ (1/0)
リボ払い使用率

...
使用限度額

31

THE UNIVERSITY OF TOKYO教師付き学習の応用例：テキスト分類「あのタレントの事件、世間の評判はどうだろう？」
 自然言語の文書が、あるカテゴリーに入るかどうか– 文書 x を、含まれる単語ベクトルで表現– （たとえば）ある事柄に好意的かどうか y• 好意的：+1• 否定的：-1– トピック y ：「スポーツ」「政治」「経済」… （多クラス分類）「野球」の含まれる回数「AKB」の含まれる回数...

---------------------「グループ」の含まれる回数

bag-of-words 表現
32

THE UNIVERSITY OF TOKYO教師付き学習の応用例：画像認識「これ、何て書いてあるの？」「いま何考えてる？」
 手書き文字認識
ある文字か(+1)否か(-1)
どの文字か？{“0”,”1”,”2”, ...} BCI (Brain Computer Interface)
どちらを思い浮かべている？

右(+1)？左(-1)？

 ほか、顔画像認識や、動画認識
33

THE UNIVERSITY OF TOKYO

教師なし学習法：K-平均クラスタリング

34

THE UNIVERSITY OF TOKYO

教師なし学習では入力データをK個のグループに分けますがデータは完全に一致することは珍しいので工夫が必要です

N個の入力ベクトル{x(1), x(2), …, x(N) }をK個のグループに分ける

先の例では完全に一致するデータがあったのでグループ分けは自明
足の数
8本10本

やわらかい

くも
たこ

いか

かたい

たらばがに
やどかり

毛がに
えび

かたさ



通常はそうではないので、グループ分けは自明でない
入力ベクトルが完全に一致することは珍しい

足の数
みみず

かたさ

たこ

むかで
えび

たらばがに

35

THE UNIVERSITY OF TOKYOひとつのアプローチは、グループごとの代表点を考え、代表点への距離でグループ所属をはかることです

K個のグループそれぞれの代表点{m(1), m(2),…, m(K)} を考える



代表点に近い入力データは、そのグループに属するとする

x(1)

m(1)

x(4)
x(2)

x(3)x(6) m(3)x(7)
m(2) (5)xx(8)

代表点への「近さ」（距離）はどう定義するか？
– 距離関数 d(m(k), x(i)) を目的によって適切に定義する

36

THE UNIVERSITY OF TOKYO

距離関数を適切に定義する必要があります

代表点に近い入力データは、そのグループに属するとする

x(1)

m(1)

x(4)
x(2)

x(3)

x(6) m(3)x(7)m(2) (5)xx(8)



代表点への「近さ」（距離）はどう定義するか？

距離関数 d(m(k), x(i)) を目的によって適切に定義する必要がある– たとえばユークリッド距離 d(m(k), x(i)) ＝||m(k) - x(i)||2237

距離関数の定義によって結果が変わってくる
THE UNIVERSITY OF TOKYOK-meansアルゴリズム：グループ割り当てと代表点推定を交互に行うアルゴリズムです

以下のステップを収束するまで繰り返す

1. 各データx(i)を、最寄の代表点m(k)に割り当てる
μ(2)
μ(1)

x(i)

μ(3)

2. 各代表点に所属したデータの平均として代表点を新たに求める（ユークリッド距離の場合）
μ(3)

38

THE UNIVERSITY OF TOKYO

教師なし学習の応用例

39

THE UNIVERSITY OF TOKYO

教師なし学習の応用例：異常検知「ちょっと出かけてくるけど、ヤバそうだったら教えて」
 機械システム／コンピュータシステムの異常を、なるべく早く検知したい– 早い段階で検出できれば、それだけコスト減
 システムに仕込まれたセンサーからの取得データを分析する– システムの異常／変化、丌正な操作により、システムが通常とは異なった振る舞いをするようになる– 計測機器の異常によって、通常とは異なった計測値が得られる
ようになる
機械／プラントなど

センサーからの取得データ

異常（の前触れ）40

THE UNIVERSITY OF TOKYO

教師なし学習の応用例：異常検知
グループに属さないデータ＝異常 と考えます システムの状態をベクトル x で表現し、教師無し学習によるグループ分けを行う– コンピュータ間の通信量、各コマンドやメッセージ頻度– 各センサーの計測値の平均、分散、センサー同士の相関 代表点から遠い x は「めったに起こらない状態」＝システム異常、丌正操作、計測機器故障などの可能性がある

x(1)

m(1)
x(2)

x(3)

x(6) m(3)x(7)
41このあたりのデータは「典型的」

x(4)

x(8)

m(2) (5)xx(9)

このあたりのデータは「はずれ値」THE UNIVERSITY OF TOKYO

おわりに

42

THE UNIVERSITY OF TOKYO今日は機械学習の初歩的な手法を紹介しました

機械学習： 教師つき学習と教師なし学習

教師つき学習の例：パーセプトロン

教師なし学習の例：K-平均クラスタリング

43

THE UNIVERSITY OF TOKYO

機械学習は、簡単だけどつぶしの効く、お得な技術です データあるところには、機械学習の問題がほぼ確実にある– 教師付き学習では1%の予測性能改善が、収益に直結する– 異常検出の需要は、コストのかかるシステムを抱える組織ならば常に存在する
 一方で、まだまだビジネスの現場において、機械学習技術は十分に入り込んでいない。
 さまざまな領域でデータ収集インフラが整った今、今後は蓄積されたデータを、どう価値にかえていくかが課題となっている
 まさに今、もっとも旬な、つぶしの効く技術
 その他のモデル：回帰、混合分布、カーネル法、グラフィカルモデル その他の応用：推薦システム、ユーザーモデリング、需要予測
44

THE UNIVERSITY OF TOKYO