これらのキーワードがハイライトされています: 遺伝的アルゴリズム GA
第12回 情報論的学習理論と機械学習研究会†
このページはしましまが 第12回電子情報通信学会 情報論的学習理論と機械学習研究会 に参加してとったメモです.私の主観や勘違いが含まれていたり,私が全く分かってなかったりしていますので,その点を注意してご覧ください.誤りがあれば,指摘してください.
3月4日(月)†
バイアス付きPassive-Aggressiveアルゴリズム†
○立石大悟・畑埜晃平・瀧本英二(九大)
- オンラインの線形2値分類:予測誤り回数の最小化
- Perceptron, PA, Cw, AROW, NHERD などは,基本的には原点を通る超平面で分離
- 次元拡張法:バイアスを扱うにはパラメータに定数の特徴を追加 → 定数に1を入れることが多いが,入れる定数によって性能が変わる → 困る
- 次元拡張法を使わないで,Passive Agressive にバイアス項を扱えるようにする
- Passive Agressive:SVMで時刻tの事例について最適化するようなもの
- 次元拡張法を用いたときの上界は既知だが,最適な定数はデータに依存して決まるため事前には決定できない
- 時刻 t とはクラスの違う過去の事例の2点の中点を通るようにすることでバイアス項を学習する(PUMMAのアイデアの導入)
- 誤り数の上界を解析的に求め,実験的に汎化誤差を評価した
○中村文士・渡辺澄夫(東工大)
- 変分自由エネルギー:変分近似した分布と元の同時分布のKL情報量の最小値
- 既存研究では混合正規分布の混合比の事前分布に混合要素のパラメータが全て同じ場合を計算したが,要素ごとに異なる場合について変分自由エネルギーの上界・下界を計算した
Model-Based Policy Gradients with Parameter-Based Exploration by Least-Squares Conditional Density Estimation†
○Syogo Mori・Voot Tangkaratt・Tingting Zhao(Tokyo Tech)・Jun Morimoto(ATR)・Masashi Sugiyama(Tokyo Tech)
- 強化学習で政策を直接学習する政策探索法の一つ
- PGPE (Policy Gradients with Parameter-Based Exploration) 法:期待総報酬の勾配により政策を更新
- IW-PGEPE法:標本が少ないときの改良だが,標本の使い方を事前に決めておく必要がある → うまい決め方がない
- モデルフリーの PGPE法をモデルを導入した model-based PGPE (M-PGPE) の提案
- 密度推定を,LSCDE法 (least-squares conditional density estimation) で行い,そこから得たサンプルで勾配を推定し,政策の更新を行う.
○秋岡明香・村岡洋一・山名早人(早大)
- タスクグラフ:処理の流れや依存関係を示したもので,並列分散化や高速化のために必要
- 既存のタスクグラフ研究の問題点
- HPC分野:Write-Once Read-Many → 後で使うデータを高速にアクセスところに置くというパターン
- 実アプリケーションから抽出したタスクグラフはきわめて少ない ← ランダムなタスクグラフで評価
- データストリーム(オンライン機械学習)の処理:ストリームを実時間で処理して情報を要約する部分と,あとで高度な処理をする部分
○赤澤靖章・井上真郷(早大)
Dual Averaging and Proximal Gradient Descent for Online Alternating Direction Multiplier Method(双対平均化法および近接勾配法によるオンラインADMMアルゴリズム)†
○Taiji Suzuki(Univ. Tokyo)
3月5日(火)†
プライバシー保護を目的とした線形回帰モデルにおける事後確率最大推定量の分散計算法について†
○中井祥人・須子統太・松嶋敏泰(早大)
- Du の,元の値が一意に特定できなければOKという弱安全性(非常にゆるい)での,垂直分割型でのプライバシ保護制約下で線形回帰のMAP推定を解く.
- ADMM を用いた反復法による解法
- Du の安全性についての須子の証明に基づいた安全性の証明
結託攻撃におけるスペクトル拡散型電子透かしの復号性能の評価†
○山内浩史・井上真郷(早大)
- 電子透かしを入れた画像が K_c があるとき,それらの画像の平均をとることによって無効化されてしまう
- 拡散符号と利用者情報の積によって,画像に加算するようにする
- 信号数を N として拡散符号は N×D の{+1,-1}行列,利用者情報はD次元ベクトル
- ノイズが加えられたすかし画像と元画像の差 r から,ある利用者が平均画像に入っているかどうか c_k を検出する
- r と 拡散符号の相関から sの要素を一個ずつ検出するシングル復号と,ベイズ推定でまとめて復号するマルチ復号
Non-Achievability of Asymptotic Minimax Regret without Knowledge of the Sample Size†
○Kazuho Watanabe(NAIST)・Teemu Roos・Petri Myllymaki(HIIT)
- ユニバーサル符号化:最大リグレット最小化(ミニマックス解)
- 理論的には正規化最尤法(NML)で求まる → 全ての符号の出方についての総和 C_n を計算できるので一般には計算は困難
- 理想符号長 と計算し易い g_n との符号長の差が,log C_n + o(1) で抑えられる漸近的ミニマックス性を考える
- この漸近的ミニマックス性を達成するには,g が n に依存することが必要であることを示す
カーネル法とランダム行列理論によるノイズ変数の除去†
○川久保秀子・吉田裕亮(お茶の水女子大)
- ヒルベルト-シュミット独立基準 (HSIC) により変数選択を行う
- ガウスカーネルを使った独立性の基準だが,実用上は分散パラメータ設定の問題
- 目的変数との独立性との判定に使う
- ランダム行列理論:ランダムな N×P 行列 R の相関行列の固有値は Marchenko-Pastur分布に従う → この分布からはずれたところはランダムじゃなくて何か構造がある
- HSIC を利用するときは MP分布族の Pure Free Meixner 分布という族になる → この分布へのあてはめの良さにより,実際にどこまでの個数の変数を採用するのかを決める
[招待講演]メタ戦略 〜 問題解決のための実践的解法 〜†
○柳浦睦憲(名大)
組み合わせ最適化問題
長方形の詰め込み問題:長方形を箱に詰めていって高さが最小になるようにする
組み合わせ最適化問題:解や順序や割り当てのような組み合わせ的な性質をもつ最適化問題
- 巡回セールスマン問題 ← 買い物のルートを考える:どの順番でまわると効率がいいのか?
- 街の集合 V と街の間の距離 d_ij → 最小距離で全ての街を回るパスを見つける
- 一般化割り当て問題:エージェント,仕事の集合,エージェントに仕事を割り当てたときの利得と資源の消費,各エージェントごとの利用可能資源量 → 資源利用量の制限を満たした中で利得の総和を最大化
- 理屈の上では,列挙すれば解けるのだが,場合の数が多すぎて実際には解けない
- アルゴリズムの計算量とNP困難性
- 入力規模 N に対して,多項式時間=O(N^k),より大きなオーダー=O(2^N),O(k^N),O(N!)など
- NP困難問題:多項式時間では解けない問題(予想)
近似解法
最適解と近似解
- 最適解:条件を満たす解で最良のもの → 現実的な時間で求めるのは難しい
- 近似解:条件を満たす解の中でよいもの → 精度保証のあるものが(近似解法),ここでは精度保証のないもの(発見的解法)について
- 近似解を求める方法:欲張り法,局所探索法,メタ戦略
- 欲張り法,局所探索法:非常に高速 →もうちょっと時間がかかってもいいからいい解を見つけたい →
- メタ戦略(メタヒューリスティクス,メタ解法)
- 多スタート局所探索法,GRASP法/反復局所探索法,可変近傍探索法/アニーリング法/タブー探索法/遺伝アルゴリズム,散布探索法など
- 局所探索法:現在の解のσ近傍N(σ)(現在の解にじゃっかんの操作をして得られる解)により良い解があればそれに置き換えるという操作を可能な限り反復する
- 設計要素:近傍,移動戦略(近傍の中のどの解を選んでいくか),探索空間,解の評価,初期解
- 最近近傍法:巡回セールスマン問題の局所探索法 → まだいっていない一番近い街へ行くことを繰り返し,全部回ったら元の街に帰る
近傍の例
- 挿入近傍:一つの要素を外の位置に挿入
- 交換近傍:二つの要素の位置を交換する
- λ-opt近傍:たかだかλ個の要素を入れ替えることによって得られる解集合
- 巡回セールスマン問題でたかだかλ個の枝を入れ替える
探索空間
- 探索の対象となる解(実行可能解)全ての集合
- 評価関数 g:探索解を評価する基準
- 実行可能解の生成が容易なときは,実行可能解のみを探索し,目的関数を g として最適化
ペナルティ関数法(実行可能解の生成が容易でない場合の代表的な方法)
- 実行不可能解も探索の対象に含める
- ペナルティ:どれくらい制約を破っているかを表す量
- 目的関数 + ペナルティ項 → 最適化 の形で解く
- ペナルティの強さを決めるパラメータは,実行可能になることが多ければ強めるといった適応的な決定をする
解空間とは異なる探索空間を使う例
- 長方形詰め込み問題
- BL点 (bottom-left):配置可能な最も低い位置の中の最も左
- 順列によって詰まり具合が代わる → 詰め込みの空間ではなく,順列が解空間になる
メタ戦略
- 多スタート局所探索法:ランダム生成した初期解から局所探索
- GRASP法:欲張り法+ランダムで初期解生成
- 反復局所探索法:過去に良かった解をランダムにちょっと変えた解(キック)を初期解に
- 可変近傍探索法:よい解がえられなかったらキックを広めに取り直す
- キックの範囲と局所探索の近傍が同じだと,元に戻ってはまるので
改悪解への移動を許す方法
- 局所最適解は:良い解であり,経験的に良い解の周辺にはより良い解がある → 局所最適解を解領すr
- アニーリング法:近傍にランダムに移るが,そのランダムさが解の良さに依存
- タブー探索法:近傍の中で見つけた解に戻らないようにタブーリストを持つ
評価関数を変形する方法
- 誘導局所探索法:現在の局所最適解の評価値が悪くなるように評価名数を変形することで,直前の局所最適解をパスして新しい解を探す
多点探索型の手法
- 遺伝アルゴリズム:解集合お集団 + 交叉・突然変異の操作
- 効率が悪いので改良法 → 遺伝的局所探索法,散布探索法
メタ戦略:次の手順を繰り返す
- 過去の探索履歴をりようして新たな解を生成
- 生成した解を評価し次の探索に使うヒントを見つける
他手法との融合
- 数理計画との組み合わせ → ハイブリッドメタ戦略/mathheuristics
メタ戦略による問題解決
- メタ戦略の利点:簡単→幅広く適用可能,大規模,柔軟
- 高性能アルゴリズムの実現 → けっこうしんどい
- 汎用ソルバー ← ソルバーを個々の問題で作るのは大変
- 組み合わせ問題は SAT に帰着できる:帰着するときに規模が拡大したり,誤差がみつもれなくなったり
- 標準問題のセットを考えてそれらを組み合わせていろいろな問題を解きたい
- 整数計画,制約充足,資源制約プロジェクトスケジューリング,配送計画,2次元パッキング,一般化割り当て,集合被覆,一般化上下階付き集合多重被覆,最大充足可能性,カッティングストック
Constrained Least-Squares Density-Difference Estimation†
○Nguyen Tuan Duong・Marthinus Christoffel du Plessis(TokyoTech)・Takafumi Kanamori(Nagoya Univ)・Masashi Sugiyama(TokyoTech)
- 密度の差の直接推定:Least-Squares Density-Difference (LSDD) → 線形 & 2乗損失
- C(ontrained)LSDD 問題の制約を利用して精度の向上を図る:2乗損失 + 線形制約項
情報理論によるシングルフレーム超解像の限界性能評価†
○川喜田雅則・山口耕太郎・高橋規一・竹内純一(九大)
- 1枚の画像から超解像画像:圧縮センシングと教師あり学習の組み合わせ
- Yangの方法の前提:矩形領域ごとに疎表現がある +” 宿退した低解像度の生成モデルを導入
- 高解像度画像と低解像度画像の疎表現間の関連を学習し,その学習した関係を使って圧縮センシングで復元する
- 宿退の生成モデル:劣化変換 + ガウスノイズ
- この長解像度画像の高解像度画像を低解像度に写す過程が,通信路の過程に似ている
- 受信した符号から送信した符号を復元=低解像度画像から高解像度画像を復元
- アルゴリズム的にも,Yangの超解像とスパース重ね合わせ符号は似ている!
- スパース重ね合わせは通信路容量の限界を達成できるが,超解像ではどうか?
- 通信路容量より小さければ高解像度画像が復元できるはずと分かった → Yangの方法でやってみたらできなかった → 限界は達成できてない(パッチの問題や,圧縮センシングでL0をL1にしちゃってるあたりが問題か?)
○岸 悠介・中村拓磨・原田竜弘・松本 隆(早大)
- 画像の領域分割:HDP-MRFモデル + MCMC による方法 (今まではDP-MRFだった)
- MRF:隠れ変数の構造としてあり,そこから実際に観測される画素が発生する → 画像の近傍の構造をモデル化
- HDP (階層Dirichlet過程):複数の画像に同種のオブジェクトがあると階層化したことが役立つ
統計的決定理論に基づく階層構造を利用したマルチラベル分類法について†
○山本粋士・須子統太・松嶋敏泰(早大)
- 複数のラベルを同時に付けるマルチラベル問題:K 個ラベルあったら,2^K のクラスに分類する問題と等価 → 実際にはクラス数が多すぎて無理
- 従来法:複数の2値分類問題,ラベルの次元削減,ラベル間の階層構造←今回はこの方針
- ラベルベクトル y の線形変換を考えて,その損失の期待損失で測ったり,その期待損失の全データでの評価の危険関数など
- ラベルの階層構造:ラベル間に概念関係の上下あり,上位概念のラベルが付いていないと,その下位概念のラベルが付くことはない
- Cesa-Bianchi の H損失ではなく,0-1損失やハミング損失を用い,ベイズ基準での最適性を考えた
- ラベル間の木構造を利用して,順に最適化を考えていけばよくなり,効率的に計算可能
非サポートベクトルのスクリーニングを用いたSVMのパス計算†
○小川晃平・鈴木良規・竹内一郎(名工大)
- SVMは正則化の強さで結果が変わるので調整が必要
- データ点は,非SV (サポートベクトル) αi=0,SVでパラメータがCに固定αi=C,それ以外のSV 0<αi<Cとがある
- 非SVはなくても結果が変わらない → それがわかっていれば計算が楽になる (Ghaoui 2010)
- 正則化パラメータ C1<C2<C3 で,C1とC3のC1の最適解とC3の実行可能解が分かっているとき,C2で非SVになる点を事前に見つけ出す
- 解の存在範囲が,C1のそれより原点から遠く,C3の解を通る円で囲まれる領域に C2 の最適解はあるということが分かるので,これを使ってC2の非SVが事前に判定できる式が導ける
- この関係を使ってパス追跡の総計算量が削減できるか試した → C が大きいとたくさんスクリーニングできる.ガウスカーネルと高次元のときはあまりスクリーニングできなかった.
局所線形近似に基づくラベル伝播のための類似度適合†
○烏山昌幸・馬見塚 拓(京大)
- グラフ上にラベルがついているノードとついていないのとがあり,ラベルを伝搬させることで,ラベルのついていないノードのラベルを予測 → 予測精度はグラフの構造に依存
- 予測値 f_i のグラフ上でのなめらかさを最適化 → 近傍のラベルは似ていて,エッジが疎なところでラベルが変わる
Σ W_ij (f_i - f_j)^2
- グラフの辺の重みが大きいと同じラベルになりやすい
- Harmonic Gaussian Field (HGF) :ガウスっぽく辺の重みを決める → 分散で結果が変わってしまう
- ノードのラベルを伝播させるのではなく,ラベル決定にかかわるノードの特徴量を伝播させる → 適応的に重みを調整 Adaptive Edge Weighting法
- ラベルと特徴が,低次元の構造+ガウスノイズ という形になっていれば提案手法はうまくいくという分析