Planar Ultrametric Rounding for Image Segmentation, NIPS2015
planer graphにおけるheirarchical clusteringを考える。
planer graphは辺が頂点以外で交わる事のないようなグラフである。
ultrametricは三角不等式の代わりに、d(u,v) =< max{d(u,w), d(v,w)}が成り立つ事を仮定した距離測度である。
本論では、グラフカットを考え、カットのない状態から、全てのエッジ間がカットされた状態までの階層的なカットを考える。
この時各階層に対してしきい値が設定されており、multicut indicaterと呼ばれる、あるエッジに対してカットが行われる層に対応したしきい値をそのエッジに対応する距離、すなわちultrametricとして用いる。
この設定の元、入力として実際のエッジ重みが与えられた際に、ultrametricとエッジ重みの二乗誤差を最小化する。
この問題は層数Lとしきい値を固定し、グラフカットを最適化するための整数線形計画問題になる。
この問題はNP困難のため、実際は整数の制約を緩和し実数条件下で近似的に解く。
この問題はcutting-plane法を用いて解く事が可能だが、その解は問題の制約を満たす事が難しい。
代わりに本論では、planer graph上で、グラフを2つに分割するtwo-way cutを考え、その上で得られるmulticutがtwo-cutを示す行列の線形和で表せる事を利用する。
これよりtwo-cutの線形和(superposition)に関するconic hullはmulti-cutのconic hullに一致し、結局解きたいmulti-cutの問題をplaner graph上のtwo-cutに関する線形計画問題に帰着させる事ができる。
実際にはこの問題はまだ解く事が難しいため、さらに近似的なアプローチで解く事になる。
Tagger: Deep Unsupervised Perceptual Grouping, NIPS2016
segmentationに関して、その入力、特徴に関する理由付けを可能にするフレームワークを提案する。
このフレームワークは教師ありだけでなく、教師なし学習の文脈においてもsegmentationにおけるグルーピング処理を行う事ができる。
この時、NNにおける表現力を向上させる事で、入力と、抽出された特徴に関して逐次的に異なる物体のグルーピングを、互いに独立性を仮定する事で行う。
このグルーピングは物体のカテゴリ、そのグルーピングをEMアルゴリズム的な相互更新を行う事で行われる。
この処理は実際にはdenoising autoencoderの文脈を用いて、根底の生成モデルを直接学習するのではなく、代わりにグルーピングを逐次改善するモデルを学習させる事で、学習の難易度を下げる。
提案フレームワークは他の従来手法と異なり、入力が画像以外のものに関しても適用可能である。
例えば音声認識におけるカクテルパーティ効果で示されるような音声分離が挙げられる。
Learning to learn by gradient descent by gradient descent, NIPS2016
ディープラーニングにおいては、特徴量を自動で学習する事を可能にした事で飛躍的な性能改善を可能にした。
しかし最適化手法に関しては、例えばdeep learningではADAM、ADAGRADなど、未だに人手によって作られている。
本論ではそうした最適化手法を学習問題に置き換える手法を提案する。
この手法は、対象とする問題の構造を元に自動で最適な最適化手法を学習する事を可能にする。
つまり、各ステップにおけるパラメータの更新値を関数として扱い、これをRNNとして各ステップ毎に動的に学習する。
No Free Lunch Theoremで知られるように、結局最適化手法は解きたい問題に対して特化させなければ上手くいかない。
この特化を考えるとき、従来であれば対象の問題を解析し、汎化誤差を出来る限り小さくできるようなアルゴリズム設計を行う。
これはつまり、学習したい真の関数とそれに関するサンプルセットに対して、まだ見ぬ新たなサンプルに対する損失が小さくなるような関数を学習する事を目的とする。
本論ではこの考え方をある問題で学習された構造を他の問題へ知識転用する転移学習の文脈で考え、この場合汎化誤差とは与えられているサンプル(=問題)がまだ見ぬ(サンプル=他の問題)どの程度へどれだけ知識を転用出来るかという事になる。
この考え方はメタ学習の文脈で議論されてきた。
本論では、RNNを用いてパラメータや損失の変化を元に逐次的に更新値を推測する。
実際の適用においては、パラメータ空間が膨大になる場合を考え、coordinate wiseな更新を行う事となる。