狠狠撸

機械学習とその理論 (情報オリンピック2015春合宿講義資料)

前置き
? これは情報オリンピック2015春合宿講義の資料です
? 機械学習の概要と理論 (大体PAC学習) の話をします
? アニメーションを分割したせいでページ数が多いように
見えますが実際は70枚程度です
? 画像は以下のサイトのクリエイティブ?コモンズ?ライセンスの
ものを使用しています
? http://en.wikipedia.org/
? https://www.flickr.com/
? http://pictogram2.com/
? http://www.publicdomainpictures.net/

記述しがたいタスク
世の中には厳密に定義するのが難しいタスクがたくさんある

文字認識
紙でアンケート
取りました

文字認識
自動で集計
したい…
紙でアンケート
取りました

スパムフィルター

おはようございます

もう寝ます

@xxxx @yyyy @zzzz @abcdefg
激安サングラス1999円今すぐ購入
もう寝ます

もう寝ます
!!??

もう寝ます
!!?? こういうのは
消し去りたい!!!

自動化してコンピュータに解かせたい！！！！！
? でもそもそも問題を定義できない
? 与えられた画像に書かれた数字が 0 とか 1 であるとは？
? 文がスパムであるとは？

ルールを書くのは辛い
数字とか穴の数とかで判定すれば？
「激安」が含まれていたらスパムでは？

また激安スパムか

穴を閉じてない同じ数字でも
穴の数違う
また激安スパムか
これはスパムではない

そこは線を太くして穴を塞げば…

穴が潰れる

このようにタスクを解くために「ルール」を書くのは辛い
? 考えても抜け穴が出てくる
?人間の認識メカニズムは実はとても複雑
?現実のデータは過酷：ノイズ，様々な環境，…
? それを塞ごうとしてどんどん複雑化
穴が潰れる

我々は激安サングラスの恐怖に怯えるしかないのか？？？
穴が潰れる

我々は激安サングラスの恐怖に怯えるしかないのか？？？
穴が潰れる
機械学習!!!!!!!!!

今日のお話
機械学習
? 人工知能の分野の一つ
? 人間は経験からものごとを学習するが，それを計算機上で
やる，というのがコンセプトらしい
? 様々な応用
?画像認識，音声認識，
自然言語処理，…
今日はその概要を話します

実践先？
2011年の NASA の機械学習コンテスト(topcoder)
http://www.slideshare.net/ckleclerc/open-
sourceatnasa-fong

実践先？
sourceatnasa-fong
画像に乗り物が映ってるか
判定して精度を競う

実践先？
sourceatnasa-fong
50万円
画像に乗り物が映ってるか
判定して精度を競う

実践先？
そして最近も…

実践先？
そして最近も…
賞金ゲットのチャンスか!!!!!?????

今日のお話
…ですが今日はそういう話はしません
? 機械学習の概要について触れます
? その上でその背後にある理論について述べます

今日のお話
問題を厳密に定義できなくて
困ってるのに理論って
どういうこと？

今日のお話
問題を厳密に定義できなくて
困ってるのに理論って
どういうこと？
厳密に定義できないところは無視，
機械学習の枠組み部分だけを解析する

この話を選んだ理由
JOIをはじめとする競技プログラミングではアルゴリズムや
データ構造など，理論的にしっかりしたものがよく扱われる
? 評価しやすいため
? 学びやすいため
しかし実用上は最初に述べたような「記述しがたい問題」を
解くことは非常に重要… そこで
? ふわっとした問題は理論が好きな人には扱いにくく見えるが，
実はその解き方には理論がある
何らかの形で興味を持ってもらえると幸い

なお
今回の話は Shalev ら著「Understanding Machine Learning」を
参考に作っています
? 2014年5月出版
? サブタイに「理論からアルゴリズムへ」とある通り
理論から入りそこから実用的なアルゴリズムの話に入る

今日の予定
第1部入門っぽい話
第2部理論っぽい話

人间はなぜ认识できるのか
? 人間には元々文字を認識する機能がある
?生まれた時に文字読める人は居ない
? 他人に教えてもらったから
? …
これは数字の 3
80x80のビットマップで
各画素が白と黒です

数字の 3

数字の 3 数字の 3
ではない

ではない
なるほど～

ではない
なるほど～
こういうノリをコンピューターに持ち込んでみよう

機械学習とは
一般的説明：集められたデータから問題を解くのに必要な特徴
や情報を抽出し，ルールを自動で獲得する手法
データ

機械学習とは
データ
なる
ほど

機械学習とは
データ
なる
ほど
これは 3

機械学習とは
データ
なる
ほど
これは 3
ルールの獲得

機械学習とは
データ
なる
ほど
これは 3
ルールの獲得
? どうすんのこれ？

ナッツ農家から学ぶ機械学習
以下のお話を例に解説
? ナッツをザックザク採れる農家がいる
? なぜか採れたナッツが美味しかったり不味かったりする
? 困る
? ナッツが美味しいか不味いか分類器を作りたい

? 困る
助けて

? 困る
助けて
……

ヒントを集める
美味しいかどうかとか知らないし…

ヒントを集めよう

小さいやつの方が美味しい気がする

色が濃いやつの方が美味しい気がする

大きさと色から判断してみよう
色が濃いやつの方が美味しい気がする

データを集める
大きい/小さいとか，色が濃い/薄いとか，どう判断する？
→ 実データを集めて眺めてみよう

大きさ色美味しい
1.9 0.6 Yes
1.3 0.4 Yes
1.1 0.5 Yes
0.3 0.9 Yes
4.3 0.5 No
2.2 0.3 No
1.3 0.9 No
1.2 0.8 No

1.9 0.6 Yes
1.3 0.4 Yes
1.1 0.5 Yes
0.3 0.9 Yes
4.3 0.5 No
2.2 0.3 No
1.3 0.9 No
1.2 0.8 No
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
色
大きさ
美味しい
美味しくない

1.9 0.6 Yes
1.3 0.4 Yes
1.1 0.5 Yes
0.3 0.9 Yes
4.3 0.5 No
2.2 0.3 No
1.3 0.9 No
1.2 0.8 No
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
色
大きさ
美味しい
美味しくない
このへんで
分かれそう？？？

直線で分離
曲線とか難しいんでとりあえず直線にしましょう

直線で分離
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
色
大きさ
美味しい
美味しくない

直線で分離
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
色
大きさ
美味しい
美味しくない
a×大きさ + b×色 = c

直線で分離
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
色
大きさ
美味しい
美味しくない
i 番目のナッツが
美味しい ? a×大きさ[i] + b×色[i] < c
美味しくない ? a×大きさ[i] + b×色[i] > c
みたいになってほしい

直線で分離
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
色
大きさ
美味しい
美味しくない
i 番目のナッツが
美味しい ? a×大きさ[i] + b×色[i] < c
美味しくない ? a×大きさ[i] + b×色[i] > c
みたいになってほしい
が，
ならないやつがいる…
出来るだけ多くのナッツを
分類できればいいことにしよう

定式化
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない
大きさ → x1
色 → x2 と表すことにする
美味しい → -1
美味しくない → +1 とする

定式化
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない
i 番目のナッツについて
大きさ，色 → (x1[i], x2[i])
美味しさ → y[i]
で表す
大きさ → x1
美味しい → -1

定式化
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない
a1x1 + a2x2 = b
大きさ，色 → (x1[i], x2[i])
で表す
大きさ → x1
美味しい → -1

定式化
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない
a1x1 + a2x2 = b
大きさ，色 → (x1[i], x2[i])
で表す
大きさ → x1
美味しい → -1
直線の良さ := ???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]?
?=1

定式化
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない
a1x1 + a2x2 = b
大きさ，色 → (x1[i], x2[i])
で表す
大きさ → x1
美味しい → -1
直線の良さ := ???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]?
?=1
これを最大にするような直線のパラメータ
a1, a2, b を求めたい

ここまでのまとめ
データ

データ
大きさと色
を使おう

データ特徴の取り出し
1.9 0.6 1
1.3 0.4 1
… … …
大きさと色
を使おう

1.9 0.6 1
1.3 0.4 1
… … …
大きさと色
を使おう
まっすぐに
分離しよう

1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
大きさと色
を使おう
まっすぐに
分離しよう

1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
大きさと色
を使おう
まっすぐに
分離しよう
???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標

1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
大きさと色
を使おう
まっすぐに
分離しよう
???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標
なるべく
その通りに
分離したい

1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
大きさと色
を使おう
まっすぐに
分離しよう
???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標
なるべく
その通りに
分離したい
一番良い分類器

1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
大きさと色
を使おう
まっすぐに
分離しよう
???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標
なるべく
その通りに
分離したい
この一連の
流れを学習とか
訓練と呼ぶ

1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
大きさと色
を使おう
まっすぐに
分離しよう
???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標
なるべく
その通りに
分離したい
?
この一連の
流れを学習とか
訓練と呼ぶ

一番良い分類関数？
…で，実際にどうやって求めんの？
直線の良さ := ???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]?
?=1

一番良い分類関数？
…で，実際にどうやって求めんの？
? ちょっとややこしい
? 普通は必ず説明するんですが準備する時間なかったんで
今回はスキップします
? とりあえずこういうのは求められるという
前提で進めます
直線の良さ := ???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]?
?=1

余談：モデル化
モデル化: いままでやったように「現実の対象を便宜上扱い
やすくするために単純に記述する」こと
? たとえばモデル化して考えた分類関数
(直線とか)は分類モデルと呼ばれる
「モデル」は一般的な用語で
自然科学全般で使われる
(e.g. 数理モデル)
大きさと色
を使おう
まっすぐに
分離しよう
なるべく
その通りに
分離したい

残念なお知らせ
データをもっと集めてみたところ…

0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない

全然分類できてない!!!
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない

モデルを変える
? 直線だと思ってたけど直線じゃなかった
? 折れ線にでもしてみよう
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない

モデルを変える
? 直線だと思ってたけど直線じゃなかった
? 折れ線にでもしてみよう
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない
全部分類できた！！！！常勝！！！！
※ここでもこういう折れ線
をどうやって求めてるかは
とりあえず置いておきます

本当に常勝？
ありがと
う！！！
！！！！
！！！！
x2
x1
できました！！

本当に常勝？
あの分類器
ぶっちゃけ微妙
なんだけど…
～数日後～
ええ？
0.0
0.2
0.4
0.6
0.8
1.0
x2
美味しい
美味しくない
全部分類できてるん
じゃないの？

過学習
そもそもなぜ分類器が必要だったか？
↑このような(見知らぬものを正しく分類する)
能力のことを汎化能力という
今回みたいに手元では精度が高いのに
汎化能力は低いことを過学習という
? 過学習は機械学習ではしばしば起こる
? 今手元にあるナッツを(美味しさで)分類するため
? すでにわかってるものを分類してどうする？
? 見知らぬナッツを(美味しさで)分類するため

過学習
過学習が起きる理由
? 分類モデルが複雑すぎる
? データが少なすぎる
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない

過学習
過学習が起きる理由
? 分類モデルが複雑すぎる
? データが少なすぎる
0.0
0.2
0.4
0.6
0.8
1.0
0.0 2.0 4.0 6.0
x2
x1
美味しい
美味しくない
分類モデルが複雑ということは
考えられる可能性がたくさんある
ということ
→ データがたくさん無ければまとも
なものに定めることができない

過学習
解決策
モデルの複雑さ訓練データの個数
良いバランスが重要

過学習
解決策
モデルの複雑さ訓練データの個数
? 単純すぎると上手くデータに
当てはまらない (高バイアス)
? 複雑すぎると汎化性能が
ダダ落ち (過学習)
良いバランスが重要
? 基本的に多いほど良い
? でもたくさん準備するのは大変
このような作業を「データ
アノテーション」と言う．

余談：鳩も過学習する？
? B.F.スキナーによる実験
? 小屋に入れた鳩にランダムな時間間隔(20秒とか)で餌を
あげているとやがて奇妙な行動を取り始める
?くるくる回ったり羽根をバタバタさせたり…
https://www.youtube.com/
watch?v=TtfQlkGwE2U
餌入れ

余談：鳩も過学習する？
なんでこんなことに？
? 鳩はなぜ自分が餌をもらえたのか考える
?直前の行動のせいでは？と予測
?少ない過去の事例から無理に理由付けしようとしている
(過学習？)
? 当然ずっとくるくる回っていたりすればそのうち(行動とは
無関係に)餌はもらえる
?それを自分の行動のせいだと勘違い
?鳩の変な行動がさらに強化され，以降ずっと続く

精度の測り方
新しいデータを持ってきてそれで測るのが良い
でも美味しいかどうか
分かってないといけない
訓練用とテスト用に
データを2分割しよう

精度の測り方
データ
訓練用
テスト用
x2
x1
x2
x1
こっちで
訓練して
こっちで
測る

精度の測り方
データ
訓練用
テスト用
x2
x1
x2
x1
こっちで
訓練して
こっちで
測る
精度75%
こういうのを交差検定といいます

ナッツ農家まとめ
機械学習の一連の流れ
データから必要な特徴の選択と分類のモデルを前もって選び，
しかるべき基準のもとで適切な分類器を選ぶ
過学習
モデルが複雑すぎ / 訓練データが少ないと精度が出ない
交差検定
分類器の精度は訓練データじゃなくてテストデータで測ろう
パラメータの最適化

文字認識
…で，ナッツの美味しさ判定してはしゃいでたわけだが
? これで文字認識とかどうやるの？
? 基本的なフローは同じ
元画像何らかの
特徴
x1 x2 数字
1.9 0.6 0
1.3 0.4 8
… … …
画像特有のテクが必要
高次元になることが多い
(数百～数千)
x2
x1
学習
高次元な大量の
訓練データを捌くため
高速なアルゴリズムが必要

補足
ぶっちゃけナッツの例みたいに2次元しかない要素なら
コンピュータなんか使わないで良い
? エクセルでプロットして目視でスパッと分類器を推測すれば
いい
コンピュータが必要な理由
? データが高次元：目視ではまず分析できない
?要素の中には役に立つものもあれば役に立たないものも
ある．そういったものを自動で取り出したりふるい落とした
りしてくれるのが強い
? データが大量：高速な手法が必要
?これはコンピュータが無ければできないこと

画像の特徴
? 判断するのによく使う特徴は何か？
?エッジ(画素値が急激に変わる点)が重要とされている
?特に角が重要
? ちょっとした変形をしても特徴があまり変わらないのが良い
?平行移動，微妙な回転，ノイズ，…
? 様々な研究がされており，どのような特徴が良いかは色々
知られている

学習理論
良い分類器を得るためには「学習モデルの複雑さ」と
「訓練データの個数」のバランスが重要だった
? モデルが単純すぎ → データにうまく当てはまらない
? モデルが複雑すぎ → 過学習
データ増やせばなんとでもなるかというと…
アノテーションは苦痛!!!!!
たすけて学習理論：
このバランスを数学的に
調べる分野

学習理論の設定
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数

訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
各データは組 (??, ??) で
表される
? ?? は特徴のベクトル
(e.g., 「大きさ」「色」)
? ?? はラベル
(e.g., 「美味しい or not」)
訓練データ全体を ?，
訓練データの個数を?
とする
? から
?

訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
分類用の関数
各データは組 (??, ??) で
表される
? ?? は特徴のベクトル
(e.g., 「大きさ」「色」)
? ?? はラベル
(e.g., 「美味しい or not」)
モデルでありうる関数
全体を ? で表す
(e.g., 線形関数全体)
訓練データ全体を ?，
訓練データの個数を?
とする
? から
? ∈ ? を1つ
選ぶ作業
? は分類器
(特徴をラベルに写す関数)
?

???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標分類用の関数
? ∈ ?

???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標分類用の関数
? ∈ ?
分類器 ? のデータ (?, ?) に対する誤差を
? ? ? = ? なら 0 (誤差無し)
? ? ? ≠ ? なら 1 (誤差有り)
とする．これを ?(?, (?, ?)) と記す
分類器 ? の訓練データ ? に対する誤差を
1
?
?(?, ??, ?? )
?
?=1
とする．これを ? ? ? と記す．

???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標
? ∈ ?

???? ?1 ?1 ? + ?2 ?2 ? ? ? ? ?[?]
?
?=1
良さの指標
? ? ?
? ∈ ?
単純に誤差 ? ?, ? が最小な
分類器を選べばよい
(訓練誤差最小化)
argmin
?∈?
?(?, ?)
これを ? ? と記す

さて，そもそもデータはどこから来るのでしょう？
なんでもあり？
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
?
?
良い分類器を作れると期待しているということは
データになんらかの偏り?傾向があるはず
→ なんでもありではない
美味しい
ゾーン
美味しくない
ゾーン

さて，そもそもデータはどこから来るのでしょう？
なんでもあり？
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
?
?
良い分類器を作れると期待しているということは
データになんらかの偏り?傾向があるはず
→ なんでもありではない
美味しい
ゾーン
美味しくない
ゾーン
どこから来るか？確率分布であろう

確率分布？
ランダムな振る舞いをする値の現れやすさを表すもの
0
0.2
0.4
0.6
0.8
1
1 2 3 4 5 6
サイコロの目今日の晩飯
0
0.2
0.4
0.6
0.8
1
うどんカレー担々麺

確率分布？
ランダムな振る舞いをする値の現れやすさを表すもの
0
0.5
1 3
3.23
3.46
3.69
3.92
4.15
4.38
4.61
4.84
幅跳びの成績
連続も
OK

データがやってくる分布を ? と表す
? 訓練データの要素 (??, ??) は分布 ? に沿って得られるとする
? 各要素は互いに独立とする
? 我々は分布 ? を知らないものと
する
分布 ?
←これはかなり強い仮定である
がそうしないと解析できないので
ここではそういうもんだということ
にする

得られた分類器 ? ? の汎化性能を知りたい
→ 新たにデータを分布 ? から持ってきて判定
?S ∈ ?
分布 ?
? データ (?, ?) を分布 ? から新たに取る
? ただしく分類できるかどうか見る
? ? ? ? = ?(?,?)[? ? ? = ?]
確率を
取ろう

まとめると
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
? ? ? ∈ ?
一番良い分類器汎化性能
? ?(? ?)

まとめると
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
? ? ? ∈ ?
? ?(? ?)
? 特徴とラベルの組
(?, ?) がデータ
? (?, ?) は分布 ? から
得られる(ランダム)
? 分布 ? 自体は未知

まとめると
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
? ? ? ∈ ?
? ?(? ?)
? ? は前もって定まって
いる
? 訓練誤差 ? ? ? を
最小化するような ? を
選ぶ
(?, ?) がデータ
? (?, ?) は分布 ? から

まとめると
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
? ? ? ∈ ?
? ?(? ?)
いる
? 訓練誤差 ? ? ? を
選ぶ
(?, ?) がデータ
? (?, ?) は分布 ? から
得られた分類器の
汎化性能が
高ければ勝利

まとめると
訓練データ
x1 x2 y
1.9 0.6 1
1.3 0.4 1
… … …
? ? ? ∈ ?
? ?(? ?)
いる
? 訓練誤差 ? ? ? を
選ぶ
(?, ?) がデータ
? (?, ?) は分布 ? から
得られた分類器の
汎化性能が
高ければ勝利
モデルとデータ数によって
汎化性能がどの程度変わる
か調べたい

スタートライン
次のようなことがいえてしまう
定理．次の条件：
? ? が有限集合
? 汎化誤差を 0 にするような分類器が ? にある
が成り立つとき，訓練データ数が 100 log 1.01 ? 個
以上あれば確率 0.99 で汎化誤差を以下で抑えられる．
? ? ? ? ≤ 0.01.

? ? が有限集合
? ? ? ? ≤ 0.01.
モデルが単純

? ? が有限集合
? ? ? ? ≤ 0.01.
モデルが単純
誤差を0にできる可能性
神の一手

? ? が有限集合
? ? ? ? ≤ 0.01.
モデルが単純
モデルの複雑さと訓練データ
数のバランスを定量的に解析
神の一手

? ? が有限集合
? ? ? ? ≤ 0.01.
モデルが単純
訓練データはランダムに
得られると仮定していたので
ここに確率が入る
(もし大ハズレなデータが
来たら何もできないので…)
神の一手

? ? が有限集合
? ? ? ? ≤ 0.01.
モデルが単純
訓練データはランダムに
得られると仮定していたので
ここに確率が入る
(もし大ハズレなデータが
来たら何もできないので…)
COOL!!
神の一手

? ? が有限集合
これってまともなの？
直線全体の集合とかどう考えても無限
(|?|=∞)

? ? が有限集合
これってまともなの？
直線全体の集合とかどう考えても無限
(|?|=∞)
たとえば3つの実数で直線を表すときコンピュータ上では double を3つ使うことに
なるけど，それは全体で 64x3 = 192 バイト．つまりたった 2192 個しかない．
コンピュータで表す場合，実数の取りうる値は実質有限

? ? が有限集合
? ? ? ? ≤ 0.01.これってどれくらい？
→ ? = 2192 を実際に代入すると約 1万3000．
? の中身や分布 ? に何も仮定を置いていない
ので最悪ケースの値が出る．

? ? が有限集合
以上あれば確率 0.99で汎化誤差を以下で抑えられる．
? ? ? ? ≤ 0.01.
このへんの値は実は正ならなんでも良い
正確には…

? ? が有限集合
が成り立つとき，訓練データ数が
1
?
log
1
?
? 個
以上あれば確率 1-δ で汎化誤差を以下で抑えられる．
? ? ? ? ≤ ?.
任意のε,δ>0 に対し，

準備
証明してみる前に準備
(和集合上界) 任意の事象 A, B に対して
? ? + ? ? ≥ ?[? ∪ ?].
(指数関数で抑える一般的なテク)
1 ? ? ≤ ???.

スタートラインの証明
証明してみよう
? 要するに大ハズレな訓練データが滅多に来ないことを
言いたい
? 訓練データ ? が大ハズレとは: ? ? ? ? > ? なこと
条件：
? ? が有限集合
? 汎化誤差を 0 にするような
分類器が ? にある
? = ??[ ? ? ? ? > ? ]
とおく．これが小さいことを言おう．

仮定から ? ? ? ? = 0 のはず．
? 汎化誤差を 0 にするような分類器は
訓練誤差も 0 にする．
条件：
? ? が有限集合
? = ??[ ? ? ? ? > ? ]
? ≤ ??[ ある ? ∈ ? があって，
? ? ? > ? かつ ? ? ? = 0]
= ??[ ? ? ? = 0?:? ? ? >? ]
≤ ??[? ? ? = 0]?:? ? ? >?
高々 |?| 個の項これは一体?
↑の考察
言い換え
和集合上界

? ∈ ? (? ? ? > ?) を固定して考える
?? ? ? ? = 0
= ??[全部の ? で ? ?? = ??]
= ?? ?,? ?
[? ?? = ??]?
?=1
= (1 ? ? ?(?))?
?=1
≤ 1 ? ? ?
≤ e???
一般的なテク
仮定
誤差0 = 全部正解
独立性
汎化誤差の定義
条件：
? ? が有限集合
? = ??[ ? ? ? ? > ? ]

よって
これが δ 以下になるのはどういうときかというと
のとき．両辺の対数を取って整理すると以下を得る．(終)
? ≤ ????
?:? ? ? >? ≤ ? ????
? ????
≤ ?
? ≥ log(
?
?
)/?
条件：
? ? が有限集合
? = ??[ ? ? ? ? > ? ]

キーポイント
で，
何の話だっけ？

キーポイント
モデルを制限したりなんらかの仮定を入れることで，
訓練データ数がこれくらいあったら高確率で汎化性能の高い
分類器を作ることができる，というのが言えた
? これは素晴らしい
? モデルを決めたときにどれくらい訓練データが要るか分かる
? あるいは訓練データを増やしたときにどれくらい精度が
上がるもんなのか分かる
で，
何の話だっけ？

PAC学習
これを一般化した概念が PAC 学習である
定義．次のとき ? は PAC 学習可能という：
関数 ?(?, ?) があって全ての ?, ? > 0, 分布 ? に対し
以下が成り立つ：
汎化誤差を 0 にするような分類器が ? にある場合，
訓練データ数が ?(?, ?) 個以上あれば確率 1 ? ? で
汎化誤差を ? 以下で抑えられる．
? ? ? ? ≤ ?.
たとえば |?| < ∞ なら ? はPAC学習可能．

PAC学習
これを一般化した概念が PAC 学習である
定義．次のとき ? は PAC 学習可能という：
関数 ?(?, ?) があって全ての ?, ? > 0, 分布 ? に対し
汎化誤差を 0 にするような分類器が ? にある場合，
汎化誤差を ? 以下で抑えられる．
? ? ? ? ≤ ?.
たとえば |?| < ∞ なら ? はPAC学習可能．
これはかなり強い仮定である．
モデルと実データが完全一致というのは普通は
まず無い．この仮定を外すとどうなるか？

不可知論的PAC学習
定義．次のとき ? は不可知論的 PAC 学習可能という：
関数 ?(?, ?) があって全ての ?, ? > 0, 分布 ? に対し
? ? ? ? ≤ min?′∈? ? ? ?′ + ?.

関数 ?(?, ?) があって全ての ?, ? > 0, 分布 ? に対し
? ? ? ? ≤ min?′∈? ? ? ?′ + ?.
神の一手

関数 ?(?, ?) があって全ての ?, ? > 0, 分布 ? に対し
? ? ? ? ≤ min?′∈? ? ? ?′ + ?.
神の一手よりちょっと悪い

関数 ?(?, ?) があって全ての ?, ? > 0, 分布 ? に対し
? ? ? ? ≤ min?′∈? ? ? ?′ + ?.
|?| < ∞ のとき ? は不可知論的PAC学習可能といえるか？

関数 ?(?, ?) があって全ての ?, ? > 0, 分布 ? に対し
? ? ? ? ≤ min?′∈? ? ? ?′ + ?.
|?| < ∞ のとき ? は不可知論的PAC学習可能といえるか？
→いえる (証明略)

いつでもPAC学習可能？
|?| < ∞ とか雑な仮定で上手くいくなら何でも上手くいきそう？
極端な話，モデルに全く仮定を置かないとどうなるか？
(つまり ? = なんでもあり)

いつでもPAC学習可能？
|?| < ∞ とか雑な仮定で上手くいくなら何でも上手くいきそう？
極端な話，モデルに全く仮定を置かないとどうなるか？
(つまり ? = なんでもあり)
モデル化を何も考えなくてもいい感じに学習してくれる
全自動学習器があれば楽できて最高！！！
← タダメシのイメージ図

ノー?フリー?ランチ定理
しかし次のようなことが言えてしまう
? つまり ? に何も仮定を置かないと
どれだけ訓練データを増やしても
精度が上がらない
? ノータダ飯
? 頑張ってモデル化しないとだめ
定義． ? がすべての関数の集合であるとき，汎化誤差
を 0 にできるような分布 ? があって以下が成り立つ：
どれだけ訓練データ数を増やしても，高い確率で
? ? ? ? ≥ 1/7.

PAC 学習まとめ
? 有限
なんでも
あり
PAC 学習可能
? =
1
?
log(
?
?
)
PAC 学習不可能

PAC 学習まとめ
? 有限
なんでも
あり
PAC 学習可能
? =
1
?
log(
?
?
)
PAC 学習不可能
この間は
どうなってるの?

PAC 学習まとめ
? 有限
なんでも
あり
PAC 学習可能
? =
1
?
log(
?
?
)
PAC 学習不可能
この間は
どうなってるの?
便利な指標が
ある

VC次元
? の複雑度を測る VC次元というなんか便利な指標がある

VC次元
?の
VC次元
1 2 3 … ? … ∞

VC次元
?の
VC次元
1 2 3 … ? … ∞
PAC学習
不可能
PAC学習可能
? =
1
?
(? + log
1
?
)

VC次元
?の
VC次元
1 2 3 … ? … ∞
PAC学習
不可能
PAC学習可能
? =
1
?
(? + log
1
?
)
次元に応じて必要な
訓練データ数が変化

補足
今回しなかった話はいっぱいあります
? 学習のアルゴリズムの話を全くしませんでした
?普通はアルゴリズムから入ることが多いです
?最適化することになりますが大体がNP困難… （???）
?目的関数を置き換えたり，数値的に解くことが多いです
? 統計の話を全くしませんでした
?妥当なモデルを作るための強力な道具
?普通は統計から入ることが多いです

補足2
? 今回は2値分類だけを扱いましたが他にも色々あります
?多値分類，回帰(実数値の予測)
? 今回のようにデータにラベルが付いている設定を
「教師あり学習」といいます
?教師無し学習:ラベル無しの設定
?クラスタリングとかそういう話

まとめ
機械学習の概要と理論の話をなんかした

自己紹介
楠本充 / @ir5
? 京大情報 (2008-2014)
? Preferred Networks 株式会社 (2014-)
?映像解析?センサーデータの解析などの研究開発
競プロ歴
? ICPC → 引退 (2008-2012)
? ICPC ジャッジ (2014-?)
細かいことは http://irreko.cc に

狠狠撸

機械学習とその理論 (情報オリンピック2015春合宿講義資料)

Recommended

More Related Content

What's hot (20)

More from irrrrr (9)

Recently uploaded (6)

機械学習とその理論 (情報オリンピック2015春合宿講義資料)