1

京都大学集中講義

機械学習と深層学習の
数理と応用
(1)
鈴木大慈
東京大学大学院情報理工学系研究科数理情報学専攻
理研AIP
Japan Digital Design
2018年12月17日

自己紹介
• 現職：

• 東京大学大学院情報理工学系研究科
数理情報学専攻 准教授• 理研AIP「深層学習理論チーム」チームリーダー• 専門：• 機械学習の数理• 汎化誤差理論• 確率的最適化• 数理統計学• 高次元統計• ノンパラメトリック法

2

本講義の目的• 対象：機械学習初学者• 機械学習の数理，特に深層学習の数理を解説• Pythonによる簡単な実装も体験してもらう
評価• 出席とレポート• レポート内容：• 数学的問題に回答• Pythonによる深層学習の実装 (Google colab)

3

講義の予定スライドを用いた講義• １回目：機械学習全般の概論• ２回目：深層学習の概論
黒板を用いた講義• ３回目：ニューラルネットワークの近似理論• 万能近似能力，Sobolev空間における近似精度• ４回目：NNの汎化誤差解析• Rademacher複雑度• ５回目：速い汎化誤差の収束レート，その他• Talagrandの不等式，ミニマックスレート最適性4

AlphaGo/Alpha Zero
深層学習+強化学習+モンテカルロ木探索+自己対戦

2015年10月5～9日欧州覇者Fan Hui (2段) に5-0で勝利
2016年3月9～15日イ・セドルと対局し4-1で勝利
2017年5月23～27日柯潔と対局し3-0で勝利
2017年12月 AlphaZeroが4時間の自己対戦のみでelmo, AlphaGo Zeroを上回る．
[Silver et al. (Google Deep Mind): Mastering the game of Go with deep neural networks and tree search,
Nature, 529, 484—489, 2016]

5

自動運転

ADAS(先進運転支援システム)[End to End Learning for Self-Driving Cars, Nvidia 2016]6身近にあふれる機械学習
推薦システム検索エンジン

遺伝子データ解析

音声認識
機械学習プラットフォーム

7

人工知能と機械学習
人工知能

本日の様相
弱い人工知能「人工知能」≒「機械学習」
強い人工知能

人間のような知能

自分で問題設定ができ，その解決もできる．

“汎用人工知能”

人間の作業の一部を代行可能限られたタスクは解ける

機械学習

統計的アプローチ
SVM
トピックモデル
スパース学習
テンソル学習…

深層学習

8

機械学習の立ち位置
数理
最適化
統計学
データ
マイニング

理論計算
機科学

人工知能

機械学習
自然言語
処理

9

音声認識
画像認識

さまざまな分野の複合領域

機械学習コミュニティの実体

10

機械学習主要国際会議

NeurIPS (Neural Information Processing Systems)
ICML (International Conference of Machine Learning)
COLT (Conference of Learning Theory)
ICLR (International Conference on Learning Representations)
AISTATS, UAI, ECML, …
関連国際会議••••

データマイニング
KDD，ICDM，WWW，WISDM，SIGIR，SDM
人工知能
IJCAI，AAAI
コンピュータビジョン
CVPR，ICCV，ECCV
自然言語処理ACL，NAACL，EMNLP，COLING 全て査読あり：ダブルブラインド，採択率20～25%- NIPS2016 (568/2500, 22.7%), ICML2016 (322/1327, 24.3%)

NIPS2015@Montreal

ICML2016@NYC

NeurIPS201811• 投稿数：4856件• 採択数：1011件• 査読プロセス：double blind(Senior) Area Chair: 約280人，査読者：約2500人
 1査読者あたり6本を査読，そのうち1-2本がaccept

通常レジストレーション（2000席）
11分38秒で完売（論文採録者，トップ査読者は別）[去年は8000席が2週間で完売]

会場の様子12

2015年の様子

Deep learning tutorial

ポスター発表企業ブースの様子 (NIPS2017)13機械学習の目的

14• 人間と同様の知的情報処理を計算機で実現するための技術・手法
Arthur Samuel 「Field of study that gives computers the ability tolearn without being explicitly programmed 」 (1959)

過去の経験（データ）

学習

未知の状況

汎化

なるべく最適な決定を下したい予測と推測機械学習の活用法

予測（より機械学習的）15

推測（より数理統計的）船“Hello”• Outcomeを正しく当てる．
• 解釈よりも予測精度を重視．
例：深層学習

肺癌

第○○遺伝子が肺癌に寄与
有意水準5％• 原因の究明．
• 仮説検定は典型例．
例：線形回帰分析

理論的にはこの二つはある種のトレードオフの関係にある．

機械学習における数学の役割

1. 問題の数学的定式化（モデリング）
2. 手法の導出と記述（アルゴリズム）
3. 正当性の保証（学習理論）
モデリング
問題を数式で
表現

学習手法

学習方法を
導出・記述

正当性の保証手法の正当性を保証

記述言語：数学• 確率-統計，線形代数，関数解析，最適化理論

16

17

機械学習の歴史機械学習と人工知能の歴史
１９４６： ＥＮＩＡＣ，高い計算能力
フォン・ノイマン「俺の次に頭の良い奴ができた」
１９５２： Ａ．Ｓａｍｕｅｌによるチェッカーズプログラム
ルールベース
１９５７：Ｐｅｒｃｅｐｔｒｏｎ，ニューラルネットワークの先駆け
１９６０年代前半：

ＥＬＩＺＡ（イライザ），
擬似心理療法士
１９８０年代：
エキスパートシステム

人手による学習ルールの作りこみの限界「膨大な数の例外」
Siriなどにつながる

18

統計的学習

第一次ニューラルネットワークブーム
１９６３：線形サポートベクトルマシン

線形モデルの限界

１９８０年代：多層パーセプトロン，誤差逆伝搬，畳み込みネット
第二次ニューラルネットワークブーム

非凸性の問題

１９９２： 非線形サポートベクトルマシン（カーネル法）１９９６： スパース学習 （Lasso）
２００３： トピックモデル （LDA）
２０１２： Supervision （Alex-net）
第三次ニューラルネットワークブーム

データの増加＋計算機の強化

19

人間

四則演算

単純なルール

機械

難 193707721×761838257287-267＝？-1 易
人の手でプログラムするのは無理
顔認識
learn without being explicitly programmed

複雑なルール

易

難

人によって顔が違う，照明の当たり方で見え方・色が変わる，表情の違い，髪型の違い，顔の向きの違い，．．．．

統計的学習の考え方

20• 人がプログラムするのは認識の仕方ではなく学習の仕方→数学で記述

大量画像データ

学習

初見の画像も正しく認識（汎化）• 強い将棋ソフトを作りたい → 大量の棋譜データで学習• 顔認識ソフトを作りたい → 大量の画像データで学習• 車道を認識したい → 大量の車載カメラ画像で学習

線形分類機

21

Bag-of-wordsx=
文章のベクトル表現例

スパムメール

wTx>0

x

分類平面

wTx<0

w

x

正常なメール

サポートベクトルマシン (SVM)[Vapnik,63]

マージンを最大化

VC (Vapnik-Chervonenkis) 理論による正当化

マージン

サポートベクトル

𝑦𝑦 = −1𝑦𝑦 = 1

数理最適化

22

ソフトマージンSVM[Cortes+Vapnik,95]

マージンを最大化
誤分類も許すソフトマージン23機械学習と人工知能の歴史
１９４６： ＥＮＩＡＣ，高い計算能力
フォン・ノイマン「俺の次に頭の良い奴ができた」
１９５２： Ａ．Ｓａｍｕｅｌによるチェッカーズプログラム

24

統計的学習

１９５７：Ｐｅｒｃｅｐｔｒｏｎ，ニューラルネットワークの先駆け
第一次ニューラルネットワークブーム
１９６３：線形サポートベクトルマシン

線形モデルの限界

１９８０年代：多層パーセプトロン，誤差逆伝搬，畳み込みネット
第二次ニューラルネットワークブーム

非凸性の問題

１９９２： 非線形サポートベクトルマシン（カーネル法）１９９６： スパース学習 （Lasso）
２００３： トピックモデル （LDA）
２０１２： Supervision （Alex-net）
第三次ニューラルネットワークブーム

データの増加＋計算機の強化非線形判別25

ネオコグニトロン

26[福島,79]・人間の脳を模倣
・畳み込みネットの初期型
・自己組織型学習→素子を足してゆくLeNet[LeCun+etal,89]

27

LeNet-5[LeCun etal,98]• 畳み込み＋プーリング：現在も使われている構造• 誤差逆伝搬法でパラメータを更新• 手書き文字認識データセット（MNIST）で９９％の精度を達成

機械学習と人工知能の歴史
１９４６： ＥＮＩＡＣ，高い計算能力
フォン・ノイマン「俺の次に頭の良い奴ができた」
１９５２： Ａ．Ｓａｍｕｅｌによるチェッカーズプログラム
ルールベース
１９５７：Ｐｅｒｃｅｐｔｒｏｎ，ニューラルネットワークの先駆け
１９６０年代前半：

ＥＬＩＺＡ（イライザ），
擬似心理療法士
１９８０年代：
エキスパートシステム

人手による学習ルールの作りこみの限界「膨大な数の例外」
Siriなどにつながる

28

統計的学習

第一次ニューラルネットワークブーム
１９６３：線形サポートベクトルマシン

線形モデルの限界

１９８０年代：多層パーセプトロン，誤差逆伝搬，畳み込みネット
第二次ニューラルネットワークブーム

非凸性の問題

１９９２： 非線形サポートベクトルマシン（カーネル法）１９９６： スパース学習 （Lasso）
２００３： トピックモデル （LDA）
２０１２： Supervision （Alex-net）
第三次ニューラルネットワークブーム

データの増加＋計算機の強化問題点• 誰でも実装できるわけではなかった．

e.g．「LeNetはYan LeCunしか実装できない」といった噂• 様々な職人芸的なノウハウが存在．
パラメータのチューニング：学習率，層の数，層の幅• 大域的最適解の計算が難しい．
局所最適解しか得られない．
→これらは現代でも未解決(実装に関してはライブラリの充実でかなり解決)
誰でも実装できて，最適解が一つの手法が欲しい．
→ カーネルを用いたサポートベクトルマシン

29

カーネル法非線形分類

30

カーネルトリック

非線形写像

非線形回帰
http://wiki.eigenvector.com/index.php?title=Svmda

http://www.eric-kim.net/eric-kim-net/posts/1/kernel_trick.html

関数解析：再生核ヒルベルト空間の理論• 凸最適化問題で解ける．
 効率的な最適化手法が存在．
 解は一つ．誰が解いても同じ答えが返ってくる．
• VC理論・経験過程の理論による汎化誤差の保証．
Vladimir Vapnik

９０年代以降
データ解析としての機械学習
統計学やデータマイニングとの融合• 高次元スパース学習• ベイズモデリング• オンライン学習，確率的最適化→ ビッグデータ解析への活用
メディアに出る「人工知能」はここに属することが多い• データの増加＋計算機の強化→深層学習再興，第三次ニューラルネットワークブームへ

31

決定木

32

• 解釈可能性が高い• 決定木を組み合わせた勾配ブースティングは
データマイニング系コンペティションで常連(判別だけでなく回帰にも利用可能)

顧客の再帰率男？女？
男
25歳以上?
25歳以上
再帰率
90%

25歳未満
再帰率
20%

女
年収500万円以上?
500万以上
再帰率
80%

500万未満再帰率
15%• 学習された決定木から要因を把握しやすい．
• 分析結果から対策を立てるのに有用．

決定木

33

決定木の様子2次元の説明変数

図はHastie, Tibshirani, Friedman: The
Elements of Statistical Learning, Springer,
2001.よりPython scikit-learnによるiris(アヤメ)データ分類

勾配ブースティング

34• XGBoostやLightGBMが有名• 「決定木の和」で強力な判別を実現

 決定木一つでは複雑な判別が難しい→ 複数用意してその和(多数決)を取る
 和の取り方に勾配ブースティングと呼ばれる技法を使用「コンピュータゲームが好きか？」を判別

沢山の決定木の多数決を出力[Chen, Guestrin: XGBoost: A Scalable Tree Boosting System. KDD2016. ][Ke, Meng, Finley, Wang, Chen, Ma, Ye, Liu: LightGBM: A Highly Efficient Gradient Boosting
Decision Tree. NIPS2017. ]勾配ブースティング
XGBoostは各種データ解析コンペティションで好成績

35

36

機械学習の数理機械学習の問題設定
教師あり学習：データ：(x,y)←ある入力xとそれに対するラベルyの組問題の例：回帰，判別

(

入力

,３) (
ラベル

入力

,５)
ラベル

教師なし学習：データ：(x) ←ラベルがない問題の例：クラスタリング，音源分離，異常検知

半教師有り学習：ラベルの付いているデータと付いてないデータが混在

37

回帰

線形
入力xから実数の出力yを予測
• 線形
• 非線形

38

非線形

判別

線形

39

非線形

入力xからカテゴリーの出力yを予測
• 線形
• 非線形

クラスタリング
文章データ(ニュース記事など)

40

政
治
スポーツ
科
学

混合ガウス分布によるクラスタリング

トピックモデル• 文章分類

強化学習

41

報酬

状態
Google research blog, 8/March/2016.
“Deep Learning for Robots: Learning from Large-Scale Interaction.”[Silver et al. (Google Deep Mind): Mastering the game of Go with deepneural networks and tree search,
Nature, 529, 484—489, 2016]

環境

アクション

教師あり学習42

画像-猫 (y=1)-犬 (y=2)-人間 (y=3)

学習：「関数」をデータに当てはめる
モデル：関数の集合（例：深層NNの表せる関数の集合）

予測モデルの学習

問題ごと

43

共有化可能

分野ごとに様々なノウハウ
深層学習（Deep learning）：
自動的に特徴量を抽出
予測モデルの構築

判別・回帰など

学習規準：汎化誤差最小化

モデルの
パラメータ

一度特徴ベクトルに変換してしまえばあとは統計の問題．
→ 汎用的な手法 (機械学習) を適用できる．

線形モデル𝑦𝑦 = 𝛽𝛽1 𝑥𝑥1 + 𝛽𝛽2 𝑥𝑥2 + ⋯ + 𝛽𝛽𝑝𝑝 𝑥𝑥𝑝𝑝 + 𝛽𝛽0 + 𝜖𝜖
𝑦𝑦:従属変数, 𝑥𝑥:特徴ベクトル

マンション価格=𝛽𝛽1 × 床面積 + 𝛽𝛽2 × 築年数 + 𝛽𝛽3 +(揺らぎ)

最小二乗法

44

最小二乗法n個の観測値（サンプル）：

𝛽𝛽 ∗ を真の回帰係数（これを推定したい）とすると，=

45

訓練誤差と汎化誤差
パラメータ
損失関数

46

：データの構造を表す変数（例：判別平面）：パラメータ がデータをどれだけ説明しているか

汎化誤差：損失の期待値

本当は最小化したいもの．

訓練誤差：有限個のデータで代用

代わりに最小化するもの．

※クラスタリング等，教師なし学習も尤度を使ってこのように書ける．

この二つには大きなギャップがある．
[過学習]基本的な考え方47• パラメータをθとしたときに，観測されたデータが観測される確率（尤度）
尤度：確率モデル

尤度が高ければ，観測データが観測される確率が高い→「尤もらしい」

負の対数尤度→最小化で観測データを良く表現するパラメータが得られる．

「最尤推定」

線形回帰（ベイズ推定も重要だがここでは割愛）
正規分布
平均𝑥𝑥𝑖𝑖⊤ 𝜃𝜃, 分散1→最小二乗法KL-divergence

真の分布モデルの分布サンプル平均で代用

対数尤度最大化はKL-divergence最小化の近似ともみなせる

48

回帰の損失関数49※各損失関数は必ずしも確率モデルと対応するわけではない

判別
• 判別
損失関数

（ロジスティック損失）
訓練誤差最小化（ロジスティック回帰）

𝑦𝑦𝑖𝑖 = 1

𝑦𝑦𝑖𝑖 = −150

方向判別の損失関数

51

凸代理損失

過学習
複雑なモデル（例えば深層ニューラルネット）を用いるのが常に良い選択か？
→ そうとは限らない．「過学習」に注意する必要あり．

学習機の複雑さと学習能力

53• オッカムの剃刀「ある事柄を説明するためには、必要以上に多くを仮定するべきでない」とする指針• No free lunch theorem「あらゆる問題で性能の良い汎用的学習機は実現不可能であり，ある問題に特殊化された手法に勝てない」
性能

ある問題に特化した方法
汎用的な方法機械学習への教訓

平均「必要以上に複雑なモデルを当てはめると失敗する」
問題
William of Ockham：1285-1347．スコラ学の神学者，哲学者．
No free lunch theorem: [D.H.Wolpert and W.G. Macready: 1995,1997][Y.C. Ho and D.L. Pepyne: 2002]

多項式回帰の過学習

54正則化学習法
正則化：データに合った単純なモデルを当てはめる→ 過学習を回避
正則化訓練誤差最小化

手元にあるデータへの当てはまり

正則化項

複雑さへの罰則
代表的な例：リッジ正則化（L2ノルム）正則化の代表例

56

多項式回帰（１５次多項式，リッジ回帰）

リッジ正則化と言う手元のデータには良くあてはまるが真の関数からは遠い

=0

過学習

= 0.1

= 50

良い推定

過小学習

正則化によってあまり複雑にならないよう制御がかかる正則化の強さと汎化誤差の関係

57

多項式回帰（１５次多項式，リッジ回帰）

過学習

過小学習
汎化誤差

訓練誤差が小さければよいわけではない
小

訓練誤差

𝜆𝜆

良い推定

大

横軸：正則化パラメータ(log-スケール)． 縦軸：汎化誤差（青），訓練誤差（赤）.

適切なλを選ぶ方法→交差検証法，Mallows’ Cp

バイアスとバリアンスの分解
線形モデル (ノイズは平均0，分散)：任意の推定量に対して以下の分解が成り立つ：

リッジ正則化の場合：※両方を同時に小さくすることはできない．

58

バイアスとバリアンスの分解バイアスとバリアンスのトレードオフ••

モデルが大きい：バイアス小，バリアンス大
モデルが小さい：バイアス大，バリアンス小

サンプルサイズに合わせて適切なモデルを選択する必要がある．

59

Mallows’ CP規準

Mallows’ CP規準2
訓練誤差

※ λ=0の時，AICと一致する．

補正項

60

クロスバリデーション (Cross-Validation)61

適切なハイパーパラメータを選ぶ方法• 観測データへの当てはまりではなく予測誤差を最小化．
• 観測データへの当てはまりを最良にするのは λ= 0.

とにかくあらゆる問題に適用可能「とりあえずクロスバリデーション」

特に k = n (サンプルサイズ) の時，Leave-One-Out-CV (LOOCV) と呼ぶ．

62

yn

y１ y2

X１ X2

・
・
・

Xn

63

yn

y１ y2

X１ X2

・
・
・

Xn

64

yn

y１ y2

X１ X2

・
・
・

Xn

実例
n = 100，d = 10 のリッジ回帰 (ガウスマルコフモデル+二乗ノルム正則化)

予測誤差 (赤線) とCVスコア (青線)

65

特徴選択
• 重回帰分析では説明変数を追加するごとに残差は小さくなってゆく．
• 余分な説明変数を使うと過学習を起こしてしまう．

 観測済みデータによく当てはまっても，未観測のデータへの当てはまりが悪くなることがある．
 サンプルサイズに比して複雑なモデルは使うべきではない．
中古マンション価格の予測：床面積，築年数，駅からの距離，建ぺい率，...

66

AICによる特徴選択
赤池情報量規準，AIC（Akaike Information Criterion）
予測精度が一番良いモデルを選択するための規準：d変数のみを用いた最小二乗推定量

AICを最小化する変数の組を探す．

AIC = データへの当てはまりの良さ + モデルの複雑さ
 d変数を用いた推定は最初のd変数である必要はない．
 dを増やせばAICの第一項は減少し，第二項は増大．
 AICの期待値は予測誤差になることが示せる．

67

68

過学習

汎化誤差と次元dの関係

中古マンション価格データの分析

従属変数：価格
説明変数：1. 最寄駅からの距離（徒歩）2. 延床面積3. 建物の構造
4. 建ぺい率5. 容積率6. 建築年
7. 最寄り駅に急行が止まるか (0-1変数で表現)
Rの関数 lm を使って分析．

69

回帰分析関数 (lm)70

最小二乗法の計算

AICによる特徴選択

step() でAIC 最小のモデル(説明変数の組) を探索．
最寄駅からの距離 + 床面積 + 築年数の三変数モデルが採用された．

1.
2.
3.
4.
5.
6.
7.

最寄駅からの距離（徒歩）
延床面積
建物の構造
建ぺい率
容積率
築年数
最寄り駅に急行が止まるか線形モデル vs 深層学習

71

過学習の例

深層学習を使うには簡単&
データが少なすぎる

マンションの価格推定
DNN: 中間層２層横幅100の深層NN，Linear: 単回帰モデル

汎化誤差 (平均二乗誤差)： DNN: 1.30 × 1015 , Linear: 6.26 × 1013
一概に何でもかんでも深層学習が良いとは言えないこれまでのまとめ• 機械学習の歴史• 機械学習の考え方• 複雑な規則をデータから学ぶ• モデルと損失• 学習：期待損失最小化• 過学習の問題• 複雑なモデルを当てはめれば良いわけではない．
• 正則化• 変数選択72

73

高次元スパース推定

高次元データ74

インターネットや計測機器の発達により多様なデータが取得可能
多くの場合で高次元••••

遺伝子データ
テキストデータ
マーケティングデータ
金融データ
Bag of words

数百万次元
Syria 13people 5bomb
economy

遺伝子発現量

数万次元
0.5
2.4

7

4.2

1

0.2

immigrants 2

1.3

0

0.1

1

5.3

soccerwalk75

サンプルサイズ

0.3
1.2
2.2
1.5
-0.5
-1.2
0.1
0.9

次元
: サンプル

次元 > サンプルサイズ → 余分な情報を落としたい意味のある情報

無駄な情報

サンプルサイズ

ここは無視

０

0.3
1.2
2.2
1.5
-0.5
-1.2
0.1
0.9

76

次元
: サンプル

次元 > サンプルサイズ → 余分な情報を落としたい
スパースモデリング

77

０
０

0.3
1.2
2.2
1.5
-0.5
-1.2
0.1
0.9

０
０

どこが重要なのかわからない→ 特徴選択：データから学習予測に寄与する特徴量を特定できれば解釈性も上がる

AICによる特徴選択（組み合わせ的方法）

78

AIC: 赤池情報量規準 →最尤推定量の予測誤差の不偏推定量

AIC最小化

データへの
当てはまり

：L0ノルムと言う．

ただし

•
•
•

次元に対する罰則（正則化）

予測誤差を近似的に最小化
p
変数の組み合わせの数：２ 個の候補 (膨大)NP困難

線形モデルを仮定
サンプルサイズn，次元p

観測ノイズ：分散σ2の正規分布

LASSOによる特徴選択（凸最適化）
Lasso [L1正則化] (R. Tsibshirani (1996))

データへの
当てはまり
ただし

次元に対する罰則（正則化）：L1ノルムと言う．

Lassoは凸最適化と呼ばれる問題のクラス• 高速に解ける（近接勾配法等）• L1ノルムはL0ノルムを最も良く近似する
凸関数• パラメータ𝜆𝜆はクロスバリデーションで選べば良い．
• 理論が豊富．
書籍：確率的最適化，機械学習のための連続最適化

79

凸関数
凸最適化

局所最適解＝大域的最適解＝

80凸関数の最適化

局所最適解

大域的最適解凸関数は局所最適解が大域的最適解→ 効率的な最適化が可能な場合が多い

簡単な例

81

１次元の場合

𝛽𝛽̂
−𝐶𝐶/2

０

𝐶𝐶/2

𝑦𝑦

Lassoのスパース性
L1正則化

82

L２正則化（リッジ正則化）

スパース

最適解

最適解

座表軸の上に乗りやすい
スパース推定によって予測に必要な変数が自動的に選ばれる

スパース性の恩恵

83

𝑑𝑑 = 真のベクトル𝛽𝛽 ∗ の非ゼロ要素の数 (予測に寄与する変数の数)定理 (Lassoの収束レート (Bickel et al., 2009; Zhang, 2009))

ある条件のもと（制限等長性など），ある定数𝐶𝐶が存在して，• 全体の次元p はたかだかO(log(p))でしか影響しない!
• 実質的次元d が支配的．
• 高次元スパースな問題を精度よく解くことができる．
推定誤差

過学習を防止過学習してしまう

低次元性（スパース性）をうまく利用できている．

84

CVスコア
(予測精度)
ちょうどよい正則化
非ゼロ要素の個数

非凸正則化ＳＣＡＤ

ＭＣＰ• SCAD (Smoothly Clipped Absolute Deviation) (Fan and Li, 2001)• MCP (Minimax Concave Penalty) (Zhang, 2010)• Lq 正則化(q < 1), Bridge 正則化(Frank and Friedman, 1993)よりスパースな解．その代わり最適化は難しくなる．
ただし，最近は局所最適解でも統計的性質は良いことが示されている．

85

MRIへの応用

86

なるべく測定時間（観測回数）を減らしたい．
測定

画像はwavelet基底に関してスパース→少数の観測（サンプル）でも大丈夫[Lustig, Donoho and Pauly: Sparse MRI: The
application of compressed sensing for rapid MR
imaging, 2007]

スパース共分散選択

データへの当てはまり（正規分布の負対数尤度）

87

L1正則化

[Meinshausen and Buhlmann, 2006, Yuan and Lin, 2007, Banerjee et al., 2008]•の逆行列Sを推定• Sij=0 ⇔ 「XiとXjが条件付き独立」• Sij=0なら変数Xiと変数Xjは直接的に相互作用しないという意味
グラフィカルモデルが凸最適化で推定可能

遺伝子ネットワーク推定

アメリカ上院議員間の関係(政策への投票履歴から推定)[Kolar+etal,2010]

88

NASDAQ 銘柄からランダム抽出した50 銘柄．
株価データを用いた分散共分散選択. 時間差も考慮．
(2011 年1 月4 日から2014 年12 月31 日まで)
(Lie Michael, Bachelor thesis)その他のスパース性

89

スパース正則化はL1正則化だけではない．
他にも以下のようなより構造を持った正則化がある．
構造的正則化• グループ正則化：変数のグループごと０にする．
• 一般化連結正則化• トレースノルム正則化

グループ正則化• グループごとに正則化• グループ全体が0になりやすい．

Genome Wide Association Study (GWAS)[Balding `06, McCarthy et al. `08]90

グループ正則化の概形
LassoGroup Lasso

𝛽𝛽1 + 𝛽𝛽2 + 𝛽𝛽3 ≤ 1𝛽𝛽12 + 𝛽𝛽22 + 𝛽𝛽3 ≤ 1

91

一般化連結正則化（Fused Lasso）

Fused lasso による遺伝子データ解析[Tibshirani and Taylor `11]
背景切り出し [Mairal et al.: 2011]
L1正則化
テスト画像

TVデノイジング（パッチを使わないデノイジング）[Chambolle `04, Mairal et al., 2009]
L1/L2グループ正則化一般化連結正則化

92低ランク行列補完

93

ベクトルから行列の学習へ• 推薦システム

ランク１と仮定

各ユーザーが各映画をどれだけ好むかという部分的情報がある．
→ 残りの部分（*の部分）を埋めたい．
低ランク行列補完で可能．
e.g., Netflix prize (100万ドルの賞金， 48万ユーザ✕１万8千映画)

94

映画jの特徴ベクトル
ユーザiの特徴ベクトル

低ランク行列の学習は「ユーザ」と「映画」の低次元表現を学習することに他ならない．
→交互最適化法やトレースノルム正則化法で学習可能

𝑟𝑟(𝑀𝑀 + 𝑁𝑁)
推定誤差 O𝑛𝑛
𝑟𝑟:ランク𝑀𝑀𝑀𝑀≪O𝑛𝑛(低ランク性を利用しない最小二乗法)

スパース表現，辞書学習

Mairal, Elad and Sapiro: Sparse Representation for Color Image Restoration.
IEEE Transactions on Image Processing, Vol. 17, No. 1, 2008.

95

低ランク行列推定による辞書学習

スパースコーディング

4.23

辞書
スパースな係数 ノイズ（イメージパッチ）
観測画像

+

=
+

0

+

1.24

96

学習された辞書

+

0

0

+

+ ・・・

各画像が
スパースな係数で表現できるよう辞書を構成

xi（i=1, ,n）：n枚の画像（i=1, ,n）：n枚の画像それぞれの係数（学習対象）
D：全画像共通の辞書（学習対象）

xi

=

D

実際はイメージパッチ（D）と係数（α）を交互に最適化して学習．

スパースコーディングを用いたデノイジング

97This image is taken from MLSS2012 tutorial by F. Bach.

Mairal et al.: Non-local sparse models for image restoration.
In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2009.

スパース表現を用いた画像補完

Mairal, Elad and Sapiro: Sparse Representation for Color Image Restoration.
IEEE Transactions on Image Processing, Vol. 17, No. 1, 2008.

98

３層ニューラルネットワーク
𝑥𝑥1

𝑥𝑥2

𝑥𝑥3

𝑥𝑥

𝑥𝑥4

𝑥𝑥5

𝑈𝑈
𝑉𝑉 ⊤
𝑓𝑓(𝑥𝑥) = 𝑉𝑉 ⊤ 𝑈𝑈𝑈𝑈⊤
𝑓𝑓(𝑥𝑥) = 𝑉𝑉 ℎ(𝑈𝑈𝑈𝑈)• 縮小ランク回帰• マルチタスク学習

𝑦𝑦

𝑦𝑦1

𝑦𝑦2

𝑦𝑦3

𝑦𝑦4

𝑦𝑦5

低ランク行列99

テンソルへの拡張

行列

応用

テンソル

• 推薦システム• 関係データ解析• 自然言語処理（単語のベクトル表現） • マルチタスク学習• 時空間データ解析

100

補助情報も入れた推薦ユーザ
コンテキスト（誰と行くか？）映画
推薦システム：ユーザー×商品×季節
広告モデル：ユーザー×サイト×広告
バイクシェアリング：会員種類×時間×位置101

低ランクテンソルモデル
𝐶𝐶𝑘𝑘:C
コンテキストの特徴ベクトル

=

B

ユーザ

A
映画

ユーザiが持つ
因子1の重みコンテキスト

映画jが持つ因子1の重み𝐴𝐴𝑖𝑖:

102

𝐵𝐵𝑗𝑗:映画の特徴ベクトル

ユーザの特徴ベクトル

コンテキストkが持つ因子1の重みA,B,Cを観察することで学習結果の解釈も可能

テンソル分解

103

CP-分解/ランク

Canonical Polyadic 分解(Hitchcock, 1927; Hitchcock, 1927)
CANDECOMP/PARAFAC (Carroll & Chang, 1970; Harshman, 1970)

計算はNP困難，ある条件の元で分解の一意性あり

Tucker-分解/ランクテンソルネットワーク(Tucker, 1966)
特異値分解で計算可能(物理学で発展)

時空間解析への応用例

104

EEGデータ解析

time ✕ frequency ✕ space
CP分解
EEG monitoring: Epileptic seizure onset localization (De Vos et al., 2007)

テンソルの学習

105

他の応用例：-時空間データ解析-画像処理-自然言語処理-深層学習
推薦システム客×品物×季節テンソルの “ランク”
CP-分解/ランク

低ランク性を有効活用した方法
通常(最小二乗法)

𝑀𝑀𝐾𝐾 ⁄𝑛𝑛

低ランク性を利用した方法(ベイズ推定法等)

次元の呪いを解消

𝑀𝑀

𝑑𝑑𝐾𝐾𝑀𝑀⁄𝑛𝑛

𝐾𝐾:次元
𝑑𝑑:ランク(≪ 𝑀𝑀)

Canonical Polyadic 分解(Hitchcock, 1927; Hitchcock, 1927)
CANDECOMP/PARAFAC (Carroll & Chang, 1970; Harshman, 1970)

Tucker-分解/ランク[Suzuki,ICML2015;Kanagawa+et al.,ICML2016;Suzuki+et al.,NIPS2016](Tucker, 1966)

106

自然言語処理に現れる低ランク性

Word2vec [Mikolov et al., 2013]• 単語のベクトル表現を得る方法“King” – “Man” + “Woman” = “Queen”“Tokyo” – “Japan” + “China” = “Beijing”
意味を足し引きできるような表現が得られる．

表現学習

107

skip-gramとContinuous Bag-of-Words(CBOW)

108

skip-gramモデル
ある単語のまわりに出現する
単語の確率分布をモデル化

CBOWモデルまわりの単語からその場所にある単語が出現する確率をモデル化

Skip-gramモデル

109

単語wOがwIの周辺（前後１０単語ほど）に現れる確率• 単語のベクトル表現との内積で表現．
• ベクトルの次元はせいぜい500ほどベクトルの次元✕単語数
単語数✕単語数＝

低ランク！

実際の挙動110from gensim.models import word2vec
train_file = "./mldata/text8"
data = word2vec.Text8Corpus(train_file)model = word2vec.Word2Vec(size=100, window=5, min_count=5, workers=7)
model.build_vocab(data)
model.train(data)

次元１００，前後５単語の出現頻度をモデル化，５回以下の出現単語は無視“Queen” + “Man” - “Woman” = “King” ?
>>> model.most_similar(positive=['queen','man'],negative=['woman'])[('king', 0.6050819158554077), ('scotland', 0.587989091873169), ('prince', 0.573
6681222915649), ('elizabeth', 0.571208119392395), ('lord', 0.5638244152069092),('duchess', 0.5520190000534058), ('duke', 0.5498123168945312), ('crown', 0.54618
62087249756), ('sir', 0.5441839694976807), ('lorraine', 0.5441141128540039)]

111

国と首都
Japan

Spain Russia
FranceTokyo

MadridMoscowParis

word2vecの貢献：

Germany

Berlinデータの「意味」を低次元ベクトルとして表現できること
を実験的に示した．
→ 深層学習にもつながる考え方．

Word2vecの応用

112• 商品タグから関連した商品を推薦あるユーザーの購買履歴
商品１

商品２

商品３

商品４

推薦
商品

商品１
商品２

• 口コミの要約

推薦商品

商品３
商品４

文章をベクトル化する手法：skip-thought, text2vec• 記事から関連広告を推薦• 感情分析
[Kiros, Zhu, Salakhutdinov, Zemel, Torralba, Urtasun, and Fidler: Skip-Thought Vectors. arXiv preprint arXiv:1506.06726 (2015).]• 機械学習の歴史• 機械学習の考え方

まとめ• 複雑な規則をデータから学ぶ• モデルと損失• 学習：期待損失最小化• 過学習の問題• 複雑なモデルを当てはめれば良いわけではない．
• 正則化• 変数選択• スパース高次元データ解析• Lasso• 低ランク行列/テンソル分解→深層学習にもつながる

113

114

補足資料

最適化法

手元にあるデータへの当てはまり（損失関数）

115

正則化項

記法を簡略化

最適化法：どうやってこの最適化問題を解く？
• 勾配法• 座標降下法• 交互方向乗数法

正則化項がない場合の最適化

116• 最急降下法

ステップサイズの決定には• Armijoの規準• Wolfeの規準
等がある．

116

正則化項がある場合：近接勾配法

線形近似

正則化項はそのまま（正則化項は微分不可能）

遠くへ離れないようにする項

鍵となる計算：近接写像→

L1正則化なら簡単に計算可能．
（Soft-thresholding関数）

117

近接写像を用いた表記• Ψ=0なら単なる最急降下法• Ψがある凸集合の標示関数なら射影勾配法
鍵となる計算：近接写像→

L1正則化なら簡単に計算可能．
（Soft-thresholding関数）

118具体例：L1正則化

119

座標ごとにわかれている！

とおく解が陽に書ける！

のグラフ

近接勾配法の収束速度120• 滑らかなほど・強凸なほど速い．
• Nesterov の加速法を用いれば滑らかな場合に速くなる (Nesterov, 2007, Zhang
et al., 2010)．
• 上のオーダーは勾配情報のみを用いる方法 (First order method) の中で最適．

強凸性と平滑性

121• 平滑性： 勾配の変化がゆっくり• 強凸性： ２次関数以上に曲がっている

平滑だが強凸ではない

平滑かつ強凸強凸だが平滑ではない

122

強凸性による
下からのバウンド

目的関数

平滑性による上からのバウンド
最適値はこれ以下(平滑性より)最適値はこの範囲に入っている(強凸性より)平滑性→最適値を上から抑えられる．
強凸性→最適値の範囲を限定できる．

近接勾配法の収束速度
Nesterovの加速法
加速

123

加速

※強凸関数には
もう一工夫必要• 滑らかなほど・強凸なほど速い．
• Nesterov の加速法を用いれば滑らかな場合に速くなる (Nesterov, 2007, Zhang
et al., 2010)．
• 上のオーダーは勾配情報のみを用いる方法 (First order method) の中で最適．

数値実験例

サンプルサイズn = 700，次元p = 1000，100成分のみ非ゼロ

124

総計算量

125

経験損失はO(1/n)まで下げる必要がある．(汎化誤差ミニマックスレートがO(1/n))𝐿𝐿𝜅𝜅 = ：条件数𝜇𝜇
一回の更新にかかる計算量

O(𝑛𝑛)

：n個の和

＝

×

1/nまで下げるのに必要な更新回数

総計算量
O(𝑛𝑛 𝜅𝜅log 𝑛𝑛 )O𝜅𝜅log 𝑛𝑛

Nesterovの加速法• サンプルサイズnが強く効いてくる• 大規模データの最適化が難しい→ 確率的最適化が有用