次元選択の情報統計力学

+
1. 4
東京工業大学
大学院総合理工学研究科
樺島祥介
replica method
1. 2
1
greedy
0. 8
2015年度第1回駒場物性セミナー
0.6
0. 4
0.2
0
0
0.05
0.1
0.15
0.2
0.25
東京工業大学
大学院総合理工学研究科
許インイン
日本物理学会2015年秋季大会
関西大学千里山キャンパス19aCQ-6
次元選択の情報統計力学
京都大学大学院情報学研究科大関真之
単純パーセプトロンの容量
E. Gardner and B. Derrida: J. Phys. A: Math. Gen. 21 (1988) 271
} 
Gardner-Cover容量
} 
単純パーセプトロン
¨ 
} 
ラベル（出力）：入力：結合：
P個のランダムな入出力関係とN次元の結合で識別できる限界
2015.09.19 次元選択の情報統計力学
単純パーセプトロンの容量
E. Gardner and B. Derrida: J. Phys. A: Math. Gen. 21 (1988) 271
} 
Gardner-Cover容量
} 
単純パーセプトロン
¨ 
} 
ラベル（出力）：入力：結合：
P個のランダムな入出力関係とN次元の結合で識別できる限界
2015.09.19 次元選択の情報統計力学
結果概要
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
L0 norm （貪欲法）+ Perceptron（非零割合：）
} 
Gardner容量から増大！
} 
} 
貪欲法Binary Iterative Hard Thresholding
N=64、128、256 1. 4
replica method
1. 2
1
greedy
0. 8
0.6
0. 4
0.2
0
2015.09.19 次元選択の情報統計力学
0
0.05
0.1
0.15
0.2
0.25
解析概要１
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
どの結合成分をつかうかどうか？
} 
} 
} 
非零の割合：
使うかどうか：
非零の結合を指定された上でのGardner体積
} 
} 
} 
ランダムな入出力関係：
指数関数でスケール仮定：
識別可能なcが存在する：、存在しない：
2015.09.19 次元選択の情報統計力学
解析概要２
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
Complexityの定義
} 
母関数を経由して、complexityの計算をする．
} 
} 
ルジャンドル変換
母関数をレプリカ法を用いて評価する．
2015.09.19 次元選択の情報統計力学
考察
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
典型的な非零の選び方でも識別可能なとき（）
2015.09.19 次元選択の情報統計力学
考察
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
典型的な非零の選び方でも識別可能なとき（）
} 
典型的な非零の選び方では識別不可能なとき（）
Complexityが連続関数なので
である限り、である．
非零の選び方はある
2015.09.19 次元選択の情報統計力学
考察
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
典型的な非零の選び方でも識別可能なとき（）
} 
典型的な非零の選び方では識別不可能なとき（）
Complexityが連続関数なので
である限り、である．
非零の選び方はある
となり、complexityが0となるところが求めたい容量である．
2015.09.19 次元選択の情報統計力学
解析概要３
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
母関数（レプリカ対称仮定のもと）
2015.09.19 次元選択の情報統計力学
解析概要３
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
母関数（レプリカ対称仮定のもと）
} 
容量の条件
} 
の最大値（）=0
（どんなに頑張っても識別可能な結合はない）
2015.09.19 次元選択の情報統計力学
いくつかの事例
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
Complexityの計算結果
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.5
2
1
2015.09.19 次元選択の情報統計力学
3
1.5
4
2
2.5
5
3
6
3.5
7
4
結果
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
スパース結合による識別可能限界（容量）
1. 4
replica method
1. 2
1
0. 8
0.6
0. 4
0.2
0
0
0.05
2015.09.19 次元選択の情報統計力学
0.1
0.15
0.2
0.25
数値実験
L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk: IEEE Trans, IT, 59, (2013) 2082.
} 
貪欲法：Binary Iterative Hard Thresholding (BIHT)
} 
} 
手順
} 
} 
} 
} 
硬判定しきい値関数（上位K成分だけを残す）：
１: K=1から徐々に非零成分を増やす．
２: BIHTを実行する．
３: 識別できる入出力関係数Pcを記録する．
計算条件
} 
} 
サンプル数：Nsam = 10000
次元数：N=64,128,256
2015.09.19 次元選択の情報統計力学
数値実験結果
L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk: IEEE Trans, IT, 59, (2013) 2082.
} 
次元数：N=64（赤）,128（緑）,256（青）
1. 4
replica method
1. 2
1
greedy
0. 8
0.6
0. 4
0.2
0
0
0.05
2015.09.19 次元選択の情報統計力学
0.1
0.15
0.2
0.25
まとめ
M. Ohzeki, Xu Yingying and Y. Kabashima: to appear soon
} 
実はL1 norm + Perceptronでも } 
} 
Gardner容量から変わらず…
L0 norm （貪欲法）+ Perceptron
} 
Gardner容量から増大！
} 
} 
貪欲法Binary Iterative Hard Thresholding
N=64（赤）, 128（緑）, 256（青） 1. 4
replica method
1. 2
1
greedy
0. 8
} 
} 
貪欲法の良好なアルゴリズム追求
Ising Perceptronの場合は？
} 
[M. Ohzeki, Xu Yingying, and Y. Kabashima: work in progress]
0.6
0. 4
0.2
0
2015.09.19 次元選択の情報統計力学
0
0.05
0.1
0.15
0.2
0.25

Download Report