機械学習プロフェッショナルシリーズ「劣モジュラ最適化と機械学習」読書メモ
劣モジュラ関数は、離散的な変数に関する凸関数に対応する概念であり、組合せ最適化問題において重要な概念となる。「組み合わせ」とは「何らかの選択可能な集まりの中から、その一部を選択する」という手続き、およびそれに付随する種々の計算的な性質を意味する。劣モジュラ関数は最適化や意思決定問題において、効率的な解法を見つけるために重要なツールとして用いられ、ソーシャルネットワーク分析、画像セグメンテーション、クエリ最適化、組合せ最適化等の様々な事例に適用される。ここでは機械学習プロフェッショナルシリーズ”劣モジュラ最適化と機械学習“をベースにこの劣モジュラ関数を用いたアプローチについて述べる。
「マシンが速くなるのを待ってはいられない。 通常の計算機環境で実行可能な例を中心に、 機械学習の主要問題への組合せ最適化手法の適用を解説。 NP困難な問題を含む最適化の理論に加え、 データ構造を利用した劣モジュラ最適化アルゴリズムの高速化についても述べる」
まえがき
劣モジュラ関数とその最適化の理論は、組み合わせ最適化分野での中心話題
劣モジュラ関数は、離散的な変数に関する凸関数に対応する概念
1970年のエドモンずによる論文
第1章 学習における劣モジュラ性
1.1 はじめに
組み合わせとは
「何らかの選択可能な集まりの中から、その一部を選択する」という手続き
機械学習を行う上で「組み合わせ」(的な計算)が重要な役割を担う
組み合わせの例
病院の患者データ
新しい患者の必要な入院期間の予測
機械学習的アプローチ
患者の様々な検査/調査項目から入院期間への回帰モデルを構築し、新しい患者に適用する
関係のない「項目」を選ぶと回帰モデルの性能は低下する
有用な一部の項目を選択して用いるという「組み合わせ的な計算」が、利用価値の高い回帰モデルを獲得するためには重要
利用可能な対象(または要素)の集まりからその一部を選択する
集合関数(set function)と呼ばれる 離散的な関数の最適化を行う
選択される対象の全体
台集合(ground set)
V={1,..,n}
集合関数
台集合Vの各部分集合S(⊆V)に実数を割り当てる
集合関数 f: 2V → ℝ
Vの部分集合の集まり(べき集合(power set)) : 2V
図の例
7つの要素からなる台集合
集合関数は、3つの要素からなる部分集合Sに実数値を割り当てる
集合関数の最適化では、 関数fが各部分集合Sの何らかのよさ(または悪さ)を表していて、 それを最大化(または最小化する)
ある台集合Vが与えられた時、 全ての部分集合S⊆Vの数は、 Vに含まれる要素数(|V|)に対して、 指数的に増大する
例
|V|=2の時は4通り
|V|=10では1024通り
|V|=100では1030通り
|V|=1000では10301通り
1.2 劣モジュラ性への導入
劣モジュラ性(submodularity)は集合関数における凸性にあたる
1.2.1 劣モジュラ関数の定義とその直感的解釈
定義
f(S) + f(T) ≥ f(S∪ T)+ f(S∩T) (∀S,T ⊆ V)
を満たすfは「劣モジュラ性を満たしている」
劣モジュラ性を満たす関数を劣モジュラ関数 (submodular function)
直感的な説明
V={1},そしてV={1,2}の場合
事前の準備
集合関数と、0-1ベクトル上に定義される 実数値関数(擬似ブール関数(pseudo boolean function))との対応
台集合Vが与えられた時、
台集合
(何の構造も持たない)単なる「はだか」の集合
各部分集合S⊆Vは、 Sに含まれる要素に対応する成分を1、 含まれない要素に対応する成分を0とすると、 N次元の0-1ベクトルと1対1対応する
集合関数は n次元0-1ベクトル上の実数値関数ともいえる
n次元0-1ベクトルを特性ベクトル (characteristic vector)と呼ぶ
より正確には、 任意の集合S⊆Vに対して 特性ベクトルxs=(v1,…,vn)Tは
vi=
1 i∈ S
0 それ以外
表現例
例:x(2,3) ∈ ℝ3 は(0,1,1)T
劣モジュラ性と、 連続関数の凸性との関係
集合関数fは、
V={1}の場合は集合関数は{},{1}の2通り
1次元
V={1,2}の場合は{},{1},{2},{1,2}の4通り
2次元
fは 1次元魔たは2次元の0-1格子上の点のみに定義される
劣モジュラ関数に対して、 凸関数を生成する補間(凸緩和)を数理的に厳密に定義したもの
ロヴァース拡張を用いて劣モジュラ性と凸性との関係を厳密に記述できる
集合関数が劣モジュラ関数である必要十分条件
そのロヴァース拡張が凸関数であること
劣モジュラ性の定義
右辺は、SまたはTのそれぞれへ、iをくわえた時の関数値の増分
\は集合の差を表す
S={1,2},T={1,4,5}とすると、 S\T={2}、 T\S={4,5}
Tに含有される「小さい」集合Sへ要素i(∈V\T)を加えた際の関数値の増え方が、 Sを含有する「大きい」集合Tへのそれよりも大きくなる
逓減:時間の変化とともに少しづつ減っていくこと
情報分野で現れる関数には、逓減性を持つ関数が頻繁に現れる
情報の本質的な性質
直感的な解釈
既知の情報が少ない場合に新しく得られた情報の価値は大きい
既により多くのことが既知であれば、同じ情報であってもその価値は比較的少なくなる
1.2.2 劣モジュラ関数の例
任意のn次元実ベクトルα∈ℝnに対して、 上記で定義される集合関数は、劣モジュラ性を満たす
モジュラ関数(modular function)
特性ベクトルXs∈{1,0}nを用いると線形関数f(S)=aTXsとしても表される
任意の無向グラフg=(V,E)が与えられたとき
選択したノード集合(S⊆V)とその補集合(V\S)との間の枝数を返す関数
劣モジュラ関数
何らかの有限個の要素集合と、 それらの一部をそれぞれ含むようなグループの集合Vが与えられたとき
選択したグループS⊆Vに含まれる要素の数を返すような関数を、カバー関数とよぶ
劣モジュラ関数
情報分野でよく用いられる(同時)エントロピー
変数からなる集合に関する集合関数としてみた場合は劣モジュラせいを持っている
センサ配置でエントロピーを使う
実行列Mが与えられたとき、全ての行Vの中から、その一部の行S⊆Vを選択した時に得られる部分行列のランク
劣モジュラ関数
相互情報量や情報利得、経済分野における効用関数(優モジュラ関数)、正定値対称行列の行列式、凸ゲーム、自乗重相関係数
様々な情報分野(やその他の周辺分野)における集合関数が劣モジュラ関数となる
1.3 機械学習における劣モジュラ性
特徴選択は、劣モジュラ関数を最大化する問題として定式化される
選択する集合の効用を最大化するような問題として、劣モジュラ関数を最大化するという定式化に元津せく研究が最近多くみられる
特徴選択に限らず、能動学習やノンパラメトリック・ベイズ推定、スペクトラル法、グラフ構造の推定などの機械学習の主要なアルゴリズムでの応用
グラフマイニングやバイラル・マーケティング、ネットワーク分析など大夫な応用分野に適用される
劣モジュラ関数は、多くの離散的なデータ構造を表すのに適した関数
変数間の構造的な依存関係
劣モジュラ関数を用いて表現される
変数間に階層関係がある
変数に冗長性があったり類似したものが含まれる
構造正則化
事前分かっている構造を取り込んで計算を効率化
1.4 本書で扱う話題
劣モジュラ最適化の基礎
劣モジュラ関数の最大化と貪欲法の適用
最大流とグラフカット
劣モジュラ最適化を用いた構造正則化学習
1.5 利用可能なソフトウェア
Matlabのtoolbox
第2章 劣モジュラ最適化の基礎
2.1 劣モジュラ関数の定義と具体例
2.1.1 カバー関数
基本的な劣モジュラ関数の例の一つ
Coverage function
例:センサの設置
fcov(S):センサーによりカバーされる面積
カバーされる丸い点の数
センサがカバーする領域
センサ1のみON→12点をカバー⇨fcov({1})=12
センサ2のみON→10点をカバー⇨fcov({2})=10
センサ1,2がON→21点をカバー⇨fcov({1,2})=21
V=(1,2,3,4}のとき、Vの部分集合は24=16個ある
カバー関数fcov:2V→ℝは24=16個の部分集合でできている
2.1.2 グラフのカット関数
グラフのカット関数8cut function)
無向グラフ(undirected graph)
無向グラフと枝部分集合
各枝eには、枝容量と呼ばれる正の値ceが定まっている
例
各頂点部分集合に対して実数値fcutを求める
SとV\Sにまたがった枝の容量の総和
fcut(S)=fcut(V\S)
有向グラフ(directed graph)
有効グラフと枝部分集合
反対向の枝は含まない
カット関数
fcut(S)≠fcut(V\S)
有効グラフのカット関数は劣モジュラ性を持つ
よって無向グラフのカット関数も劣モジュラ性を持つ
2.1.3 凹関数が生成する集合関数
1変数の凹関数によって生成される劣モジュラ関数
実数ℝ上の凹関数が{0,1}n上の凸関数を生成することを意味する
1変数の凹関数が生成する集合関数が劣モジュラとなることは
一変数の凹関数
xをx+∆xに変化させた時の関数値の変化量h(x+∆x)-h(x)を考える
xが大きいほどxが小さくなる
関数h(x)の例
√x, x(α-x), min{x,β) α,βは定数
集合関数fcnc:2V→h(|S|)
|S|はSに含まれる要素数
劣モジュラ関数
Fcncの重み付き版
w=(w1,w2,…,wn)を各成分が非負のn次元の定数ベクトル
劣モジュラ関数
凹関数が生成する集合関数の劣モジュラ性の証明
A=S∪T, B=S∩T
1/2(h(w(S))+h(w(T))) ≥ 1/2(h(w(S∪T))+h(w(S∩T)))
2.1.4 劣モジュラ性の特徴づけ
2つの劣モジュラの式は等価
2.2 劣モジュラ関数の基本性質
2.2.1 様々なタイプの集合関数
劣モジュラ最適化において
関数fが劣モジュラ性に加えてどのような性質を持っているかが重要
関数fによって、計算効率やアルゴリズムが大きく変化
劣モジュラ関数のタイプ分け
有限集合V={1,…,n}と集合関数f:2V→ℝについて考える
用語の導入
fが正規化されている(normalization)
f({})=0が成り立つ
fが非負(nonnegative)
全てのS⊆Vについてf(S)≥0が成り立つ
fが単調(monotone)あるいは非減少(nondescreasing)
全てのS⊆T⊆Vについてf(S)≤f(T)が成り立つ
fは対称(symmetric)
任意のS⊆Vについてf(V\S)=f(S)が成立する時
タイプ
カバー関数fcovは、単調な劣モジュラ関数
無向グラフのカット関数fcovは、対称な劣モジュラ関数
有向グラフのカット関数fdcutは、非負の関数ではあるが、単調でも対称でもない
凹かんすうが生成する劣モジュラ関数fcnc,fwcncは、一般には短調でも対称でもないが、hの選び方で短調や対象の関数になる
優モジュラ関数、モジュラ関数
優モジュラ関数 (supermodular function)
任意のS,T⊆Vに関してg(S)+g(T)≤g(S∪T)+g(S∩T)が満たされる時
gを優モジュラ関数であると言う
劣モジュラかつ優モジュラである
任意のS,T⊆Vに関して、g(S)+g(T)=g(S∪T)+g(S∩T)
gをモジュラ関数であると言う
2.2.2 劣モジュラ関数の基本操作
劣モジュラ関数などの集合関数が与えられたとき、 劣モジュラ性を保つような基本操作は?
和とスカラー倍
簡約と縮約
台集合を小さくする操作である簡約(または制限)と縮約
簡約(reduction)
簡約fSはfの関数値をSの部分集合に限ることで得られる関数
劣モジュラ性
縮約(construction)
縮約fSはfの関数値をSを含むVの集合に限り、 さらにfS({})=0となるように定数f(S)を引くことで得られる関数
劣モジュラ性
劣モジュラ関数fに関して簡約と縮約を繰り返して 得られる劣モジュラ関数をfのマイナー(minor)と呼ぶ
2.3 劣モジュラ最適化の考え方
はじめに
最小カット問題と最大カット問題
例
最小カット問題の定式化
目的
無向グラフのカット関数fcut(S)→最小
制約
S∈2𝛎\{{}, 𝛎}
Sとして明示的に{}と𝛎を除く必要がある
最大カット問題の定式化
目的
無向グラフのカット関数fcut(S)→最大
制約
S∈2𝝂
最小カット問題は理論的に解けるが、最大カットはうまく解くことが難しい
劣モジュラ最適化の基本形
劣モジュラ最適化の基本形
目的
f(S)→最小または最大
制約
S∈F⊆2V
Fは最適化において考慮する部分集合全体からなる集合族
用語の導入
目的関数(objective function)
最適化すべき対称であるf
実行可能領域(feasible region)
F⊊2Vはある制約を満たすVの部分集合からなる集合族
実行可能解(feasible solution)
実行可能領域Fに含まれるS
最適解(optimal solution)
目的関数の値を最適にする実行可能解S*∈F
最適値(optimal value)
最適解の時の目的関数値f(S*)
最小元化(minimizer)
最小化問題の時の最適解
最大元化(maximizer)
最大化問題の時の最適解
劣モジュラ問題の様々なタイプ
劣モジュラ関数fは一般の関数か?非負か?単調か? 対象か?あるいは何らかの構造を持っているのか?
最小化問題か?最大化問題か?
制約なし(つまりF=2V)か?制約ありならどのようなものか?
劣モジュラ関数の情報とアルゴリズムの計算量
劣モジュラ最適化問題に対するアルゴリズムを設計する上で、 劣モジュラ函数はの情報がどのような形で利用可能であるのか?
関数値オラクルが与えられて、 それらの呼び出しによりf(S)の値が得られる
関数値オラクル(value oracle)
オラクル(oracle)の和訳は「神託」
理論計算機科学や最適化の分野では、 何らかの決まった計算をしてくれる装置を示す
ただし、計算の過程はブラックボックスと仮定
劣モジュラ最適化アルゴリズムは、 基本演算の回数と関数値呼び出し回数が 共にnに関する多項式のオーダーで抑えられる
2.3.1 劣モジュラ関数の最小化
制約なしの劣モジュラ関数最小化問題や 対称劣モジュラ関数の最小化問題について
一般の劣モジュラ関数最小化
制約なし最小化
実行可能領域Fが2Vである
式
単純に2n通りある全ての部分集合S⊆Vに対して f(S)の値をよびだして比較することで fの最小化を求めることができる
指数時間かかり実用的ではない
非負性(または単調性や対称性)を仮定した場合はS={}が問題の最適解となる
劣モジュラ関数の最小化を 実際に扱う場合の注意点
劣モジュラ関数の理論は問題の困難性の最低ラインを保証する
劣モジュラ性を証明できると、 劣モジュラ関数の理論の様々な結果を利用できる
多項式時間アルゴリズムである保証はないが (相対的に)実用的な劣モジュラ関数最小化アルゴリズムがある
最小ノルム点アルゴリズムと呼ばれる 計算時間の多項式性の保証されていない方法が 多くの多項式時間アルゴリズムよりも 高速に劣モジュラ最小化問題解くことができる
関数fによっては(理論的にも実用的にも)より高速に最適性が解ける
高速に溶けて応用範囲の広い最小s-tカット問題がよく知られている
対称劣モジュラ関数最小化
プロパー(proper)である
部分集合S⊆Vが{}やVと異なる場合
対称劣モジュラ関数最小化(symmetric sub modular function miniztion)
永持・茨木のアルゴリズムによって解くことが可能
一般化されたキラーン(Queryranne)のアルゴリズム
2.3.2 劣モジュラ関数の最大化
はじめに
制約がある場合でもない場合でもNP困難な問題
いくつかのタイプの最大化問題に関してはかなり良い近似アルゴリズムがある
単調な劣モジュラ関数の最大化
問題の式
ネムハウザー・ウォルジー・フィッシャーによる「貪欲法アルゴリズム」
非負の劣モジュラ関数の最大化
問題の式
NP困難
最大カット問題に関しては
ゴーマンスとウィリアムソンによる半正定値計画問題に基づいた0.878-近似アルゴリズム
ブッフビンターラによる乱数を使用した0.5-近似アルゴリズム
2.4 劣モジュラ最適化と多面体
はじめに
V={1,…,n}とする
F:2V→ℝを正規化された劣モジュラ関数とする
関数fによって、 2つの多面体( 劣モジュラ多面体P(f)⊆ℝnと、 基多面体B(f)⊆ℝn)が 定義される
2.4.1 劣モジュラ多面体と基多面体
劣モジュラ多面体 (submodular polyhedron)
x(S)≤f(S)の形の2n-1個の不等式を 全て満たすx∈ℝn全体の集合として定義する
P(f) ∈ℝn
P(f)={x∈ℝn : x(S)≤f(S) ∀S⊆V)}
基多面体 (base polyhedron)
x∈P(f)で、x(V)=f(V)を満たすもの
B(f)= {x∈P(f): x(V)=f(V)}
n=2の場合の劣モジュラ多面体と基多面体
V={1,2}の時
劣モジュラ多面体P(f)⊆ℝ2は3つの不等式によって定まる多面体
基多面体B(f)∈ℝ2は2つの不等式と1つの等式によって定まる多面体
f({1})=4, f({2})=3, f({1,2})=5を満たす場合のp(f)とB(f)
n=3の場合の劣モジュラ多面体と基多面体
V={1,2,3}の時
劣モジュラ多面体P(f)∈ℝ3は7つの不等式を全て満たすような 3次元ベクトル(x1,x2,x3)の集合となる
基多面体B(f)∈ℝ3は、(x1,x2,x3)∈P(f)かつx1+x2+x3=f({1,2,3})を 満たすような3次元ベクトル全体の集合
n=3の場合のP(f)とB(f)の例
劣モジュラ多面体と基多面体の性質
2.4.2 基多面体の端点
はじめに
多面体P⊆ℝnについて、 点x∈Pが端点(extreme point)であるとは
y,z∈Pかつy≠zを満たすどのような2点についても xがy,zの中点として表されないことと定義する
多面体Pが有界である時、
Pの端点集合の凸包(Pの端点集合を含む最小の凸集合)とPが一致する
基多面体B(f)は劣モジュラ多面体P(f)の部分集合
一般にB(f)とP(f)の端点集合は一致する
n=2の場合の基多面体B(f)は端点を2個持つ
n=3の場合の基多面体B(f)は端点を6個持つ
基多面体の端点と線形順序
ℝnのn個の成分集合V={1,…,n}を並び替えることによってできる 「線形順序L(linear ordering)」
n=2の時の線形順序Lは(1.2)と(2,1)の2通り
n=3の時の線形順序Lは(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)の6通り
Vの線形順序を一つ定めると、 Lに対応する基多面体B(f)の端点 xL(x1L,x2,L…,xnL)∈ℝnを定めることができる
線形順序Lと端点xLは エドモンズ(Edmonds)によって1970年に提案された 基多面体(または劣モジュラ多面体)に関する 貪慾法(greedy algorithm)により対応づけられる
アルゴリズム
適当な点x0からスタート
x0は基多面体の任意の点x∈B(f)に対しx0≤xを満たす
P(f)内でi1,…,inの順に各成分を成分ごとに大きくして得られる点をxLとする
最終的に得られるxLは必ず基多面体B(f)の端点となる
実例での説明
n=2なのでアルゴリズムはステップ0からステップ2まで
ステップ0
例えばx0=(0,0)とおく
ステップ1
P(f)内で第1成分を最大化するのでx1=(4,0)
ステップ2
P(f)内で第2成分を最大化してx2=x(1,2)=(4,1)
手順の図1
手順2
端点xL∈ℝnを生成する貪慾法アルゴリズム
Lの最初のj個の要素からなるVの部分集合をL(j)とおく
線形順序Lに対応する基多面体B(f)の端点xLは f(L(1)),…,f(L(n))のn個の関数値を呼び出すことで容易に得られる
例:n=2
x(1,2)=(f({1}), f({1,2}) – f({1}))
x(2,1)=(f({1,2}) – f({2}), f({2}))
例n=3
2.4.3 基多面体と劣モジュラ関数最小化
2.5 劣モジュラ関数と凸性
2.5.1 集合関数のロヴァース拡張
2.5.2 劣モジュラ関数と凸関数
2.5.3 劣モジュラ関数の多重線形拡張
第3章 劣モジュラ関数の最大化と貪欲法の適用
はじめに
劣モジュラ関数を最大化する問題について
f:2V→ℝは単調な劣モジュラ関数
制約条件:選択する部分集合の要素数が最大でk個
3.1 劣モジュラ最大化と貪欲法
3.1.1 劣モジュラ最大化と近似アルゴリズム
カバー関数の例
カバー関数最大化問題
P1,P2,P3,P4のうちできるだけ多くをカバーする2つの集合を選ぶ
V={1,2,3,4}
部分集合は6通り:(1,2},(1,3},(1,4},{2,3},{2,4},{3,4}
手計算だと、最大値を達成する組み合わせはfcov({2,4})=11
近似アルゴリズム(approximation algorithm)によるアプローチ
α:近似率(approximation ratio)あるいは、 近似保証(approximation grantee)
αは1に近ければ近いほどよい
貪慾法
0.63-近似アルゴリズム
単調劣モジュラ関数がどのようなものでも 最適値の0.63倍以上の目的関数値を達成することが保証されている
3.1.2 劣モジュラ最大化のための貪欲法
貪慾法(greedy algorithm)
S={}からスタートして、 S⊆Vの要素数がkになるまで 「貪慾」に要素を増やしていく
具体的なアルゴリズム
例
初期化
ステップ0でS={}とおく
反復1
ステップ1では|S|=0<2より停止しない
ステップ2では、 fcov({}∪{1})=3, fcov({}∪{2})=5, fcov({}∪{3})=7 fcov({}∪{4})=6で I=3が選ばれてS={}∪{3}={3}となる
反復2
ステップ1では|S|=1<2より停止しない
ステップ2では、 fcov({3}∪{1})=10, fcov({3}∪{2})=9, fcov({3}∪{4})=10で I=1が選ばれて(i=4でも良い)S={3}∪{1}={1,3}となる
反復3
ステップ1では|S|=2より、 SGA={1,3}を出力してアルゴリズムは停止
3.1.3 貪欲法の近似率*
近似率の証明(割愛)
3.2 適用例1:文書要約への適用
3.2.1 文書要約の劣モジュラ最大化としての定式化
文書要約における劣モジュラ関数の定義式の概念図
ある文書が与えられた時、 その文章を構成する文を要素とする有限集合V={1,…,n}を考える
fdoc(S)=L(S) + λR(S)
文書要約で選択される文の集合をS
関連の高い文を選んだ集合をL(S)
① 2文間の相関をsijとしてL(S)=∑sijとする
文書全体と関連の高い文
② 文の集合Sに含まれる概念の集合を𝚪(S)として 各概念i∈𝚪(S)の重要度γiの和として L(S)=∑γiと定義する
③ リン(Lin)とビルメス(Bilmes)による定義
Ci(S):2V→ℝは選択した文の集合がどれだけ文iに類似しているか (つまり文iがどの程度Sによりカバーされているか) を表す単調な劣モジュラ関数
0≤γ≤1は閾値を調整するためのパラメータ
選択する文間の冗長度を少なくするように選んだ文の集合をR(S)
冗長な文に対して何らかの罰則を課す
① 文の集合Sを選択することの多様性に対する報酬を加える
Pk(k=1,…,K)は文全体の分割で、 rj>0は新しく文jを空集合へ加えることに対する報酬を表す
分割Piを得るためには、例えばクラスタリングを行う
まだ一度も選ばれていない分割の中から文iを選ぶことに対して報酬を与える
トレードオフを調整するパラメータをλ
ナップサック制約下の劣モジュラ関数最大のための貪慾法アルゴリズム
文の長さをコストとみなし、選択した文のコストの和で制約を課す
ステップ3でコストで正規化している
3.2.2 文書要約のその他の規準
その他の文書要約基準
最大限界関連度 (maximum marginal relevance)
すでに選択されている文の集合Sに対して、 新しい文i∈Vを加えた時の増分の式
Sim1(I,q)は文Iとクエリーqの間の類似度
Sim2(j,i)は文jとiの間の類似度
λ:0≤λ≤1はこれらの間のバランスを調整する係数
8
Linにより提案されて、近年実用されている ROUGE-Nスコア
34
候補となる要約と参照となるそれとの間の n-gramに基づく再現率
3.3 適用例2:センサ配置問題
はじめに
観測誤差ができるだけ小作なるようなセンサーの配置
カバー関数を使って ガウス過程回帰でモデル化し、 劣モジュラ最大化問題で得く
3.3.1 ガウス過程回帰による分布の推定
前提条件
センサーを置きうる箇所をx1,…,xnのn個あるとする
添字からなる集合をV={1,…,n}とする
センサをS⊆Vに対応する箇所に設置する
センサにはノイズがあり、 複数のセンサを用いると、 互いに情報を保管して精度が上がる
センサが複数あるとその付近は精度が高い
センサをおいた箇所S⊆Vにおける 観測量ysの分布が、多次元正規分布に従う
確率密度関数
μsは平均ベクトル
∑sは分散共分散行列
|∑s|は行列式
任意の箇所xの観測量y(x)の分布を考える
平均μ(x)と分散σ2(x)が、箇所xの関数として、非線形を表せる
p(y(x))は、まだセンサによる観測を考慮したものになっていない
センサを置いた箇所の観測量を手かがりに箇所xの観測量y(x)がどうなっているか?
条件付き確率p(y(x)|ys)(事後確率分布)が求めたい確率
ysはセンサを置いた箇所の観測量
条件付き分布p(y(x)|ys)がどのようになるか?
各箇所における観測量の間の共分散を、カーネル関数K(x,x’)で与える
放射基底関数カーネル(radial basis functional kernel)が四間用いられる
別名:ガウシアンカーネル
γ:カーネル関数のパラメータ
観測量y(x)とysの同時分布
K0:=K(x,x)
KノカクヨウソハK(x,xi)を表す
条件付き分布p(y(x)|ys)=N(μ(x|S), σ2(x|S))は上式となる
分割公式を用いて
平均ベクトルμと分散共分散行列∑の分割
3.3.2 センサ配置の規準と劣モジュラ性
センサ配置の良さを評価する基準は?
考えている領域の任意の箇所xにおける 観測の不確実性をどれだけ小さくできるか?
エントロピーを用いたアプローチ
確率変数yの同時エントロピーH(y)および 別の変数y’を条件とする条件付きエントロピーH(y|y’)は 上式となる
センサを箇所Sにおいた時の、 ある箇所xにおける観測量y(x)の条件付きエントロピーは
正規分布を仮定した場合
Σ2(x|S)を用いて計算可能
センサーを箇所Sにおいたことで、 どの程度不確実性を減らせるか
実際の計算では
任意の場所で全ては計算できない
いくつかの代表的な箇所x1,…,xmをあらかじめ選択
この箇所と、センサーを置けなかった箇所V\Sについてこの量を計算する
ySと(yV\S,y(x))の相互情報量 (metal information)
命題
エントロピーには単調製がある
多くの観測が得られればそれだけ情報量が増えて不確実性はへる
センサーの設置料には制約を加える
精度を得るには
要素数が2kまでの全集合に対して単調製があれば十分
|V|を2kに対して十分大きくする
文献30
3.4 適用例3:能動学習
はじめに
教師あり学習においてラベル付けのコストが高い場合に、 重要なサンプルのみを選択してラベル付けを行う方法
プールベース型能動学習 (pool-based active learning)
一括型能動学習 (Batch-mode active learning)
ラベル付けするサンプルを複数同時に選択する
3.4.1 一括型能動学習と劣モジュラ性
簡単のため2値分類から行う
前提条件
ラベル付けされていないサンプルをx1,…,xn∈ℝdとする
その添字の集合をV={1,…,n}と定義する
各サンプルxiの(未知の)ラベルをyi∈{-1, +1}とする
目的は、 できるだけ性能の高い分類器p(y|x)の学習が可能となるように、 ラベル付けを行うできるだけ少ない(あるいは事前に与えたk個以下の) サンプルを選択すること
ラベル付けを行うサンプルの集合が持つ有用性 (どれだけ分類器のための情報を持っているか)を “フィッシャー情報行列の概要と関連アルゴリズム及び実装例について“で述べているフィッシャー情報行列(Fisher information matrix)に 基づいて与える
観測される確率変数が対象とするモデル(パラメータ) に対して持つ情報の量を与える基準
有限のパラメータwにより記述される分類器p(y|x)であるため
フィッシャー情報行列Iq(w)は上式のように与えられる
q(x)は対象とするサンプルの分布
フィッシャー情報行列を用いた能動学習の基準
全てのサンプルに関する分布をp(x)
ラベル付けを行うサンプルに関するそれをq(x)とする
ラベル付けを行おうとするサンプルが持つ情報が、 できるだけ全サンプルのそれに近くなるように選ぼうとする基準
分類器として (線形)ロジスティック回帰 (logistic regression)を用いて定式化
ロジスティック回帰の式
ロジスティック・シグモイド関数 (logistic sigmoid function)
ロジスティック回帰に関するフィッシャー行列
有限のサンプルなので、積分の厳格な計算はできない
近似的なものを用いる
Idはd行d列の単位行列
Δ≪1は特異行列避けるために用いられる小さな実数値
S⊆Vはラベル付けを行うサンプル集合
最小化したいtr(Iq-1Ip)に代入
最終的な最小化したい目的関数
第一項は、Vに関して評価したもの
3.5 その他の適用例
Thomaらによる グラフマイニングにより得られた部分グラフ選択の劣モジュラ関数最大化
52
DasとKempeによる、 線形回帰モデルにおける変数選択の基準の劣モジュラ性
ReedとGharaminiらによる、 インディアンブッシュ過程と呼ばれる ノンパラメトリックベイズ推定の一種において
計算途中で必要となる最適化を 劣モジュラ関数最大化として近似的に定式化することで、 効率的な実装を実現
ケンペらのネットワーク上での影響最大化の劣モジュラ関数最大化としての定式化
ソーシャルネットワークにおけるマーケティングに応用
文書要約での、リンやビルメスらによる
文書の階層構造の利用
複数の文書の同時要約
センサ配置での、相互情報量とは異なる基準や頑強化されたアルゴリズムの提案
能動学習での特に重要な拡張
時事刻々と変わる状況の中での能動学習への拡張
適応劣モジュラ性(adaptive sub modularity)
9,17
さらに関連する応用話題
30
3.6 補足:センサ配置可能箇所の設定について*
センサ配置問題
補題3.6
リプシッツ連続(Lipschitz continuous)
系3.7
定理3.8
第4章 最大流とグラフカット
はじめに
劣モジュラ関数の最小化は、多項式時間で行うことが可能
一般の劣モジュラ関数の場合には、 台集合Vの要素をnとすると、 最小化には、最悪ケースでO(n5EO+n6)かかる
対称な劣モジュラ関数の場合には、 最悪ケースでO(n3EO)で実行可能な キラーン(Queyranne)のアルゴリズムがある
最小ノルム点アルゴリズムでも、 要素点の多い問題であったり、 反復的な計算をする場合は十分な速さではない
高速に最小化可能な 劣モジュラ関数の特殊クラスを考えることが必要
コンピュータービジョンで使われるグラフカットアルゴリズム
4.1 カット関数最小化と最大流アルゴリズム
はじめに
有向グラフのs-tカット関数と、最大流について
s-tカット関数は、最も基本的な劣モジュラ関数の一つ
最大流とs-tカットは、最大流最小カット定理と呼ばれる原理で密接に繋がっている
4.1.1 カットとフロー
有向グラフにおけるカットとフローの概念について
有向グラフの例
V={1,2,3,4,}とする頂点数6
枝数9
各枝の数字は枝容量
s-tカットと最小s-tカット問題
有向グラフgの頂点集合Vの順序つきの分割(V1,V2)のうち
特にs∈V1, かつt∈V2を満たすもの
s-tカット(s-t cut)
任意のs-tカットは、 Vのある部分集合S⊆Vを用いることで上式のように表せる
s-tカットについて、容量Ks-tを上式で表す
ɡの頂点の部分集合V’∈Vについて
δgout(V’)⊆εはgにおいてV’の頂点から出てV’以外の頂点に入る枝e∈εの集合とする
集合関数Ks-t:2V→ℝをs-tカット関数(s-t cut function)と呼ぶ
上記の例の有向グラフでのs-tカット関数値は
Ks-t({})=c(s1,1) + c(s,2) =10
Ks-t({1}) = c(1,3) +c(1,2) + c(s,2) =9
Ks-t({2}) = c(s,1) + c(2,3) + c(2,4) = 13
s-tカット関数Ks-tは、有向グラフのカット関数のマイナー(に定数を加えたもの)
S-t最小カット問題 (minimum s-t cut problem)
劣モジュラ関数最小化問題の特殊ケース
最大流アルゴリズムを解くことで高速に解くことができる
フローと最大流問題
有効グラフg=({s}∪{t}∪V, ε)において
入り口に対応するソースsから、出口に対応するシンクtへのものの流れであるフローについて意義する
各枝e∈εに、eの上の流れを表す実数値𝝃e∈ℝを対応させる
実数ベクトル𝛏=(𝛏e)e∈εを導入する
フロー𝛏は以下の条件を満たすとき、 実行可能フロー(feasible flow)であるという
各枝e∈εについて、e上のフロー𝝃eが0以上ce以下である
0≤𝝃e≤ce (∀e∈ε)
Sとt以外の各頂点i∈V\{s,t}=Vでは、 iから出るフローと、iに入るフローの量が等しい
流量保存制約
実行可能フローの例
枝容量ceの枝eの上をフロー𝝃eが流れている状態の表し方
実行可能フローに関して、 流量(flow value)をソースから出る 正味のフローの量として上式で表す
流量を最大にする実行可能フロー𝝃を見つける問題
最適解を最大流 (maximum flow)と呼ぶ
例
線形最適化問題
線形最適化のソルバーを用いて解くことが可能
最大流アルゴリズムを用いて高速に解くことも可能
フローとカットの関係
有効グラフのs-tカットと、任意の実行可能フローの関係についての関係式
最大流最小カット定理
例
4.1.2 最大流アルゴリズム
最大流を求める代表的なアルゴリズム
最大漁を目指して
有効グラフでのソースsからシンクtへの有向パスをs-tパスと呼ぶ
有向グラフgの最大流を求めるための単純な方法
手順
フロー𝛏を𝛏e=0(e∈ε)と初期化する
gにおけるs-tパスに沿ってフローをαだけ流す
枝(i,j)がパスP上にある→𝝃(i,j)をα増やす
枝(i,j)がパスP上にない→𝝃(i,j)はそのまま
問題点
最大流が必ずしも得られない
残余ネットワークとフローの更新
容量制限を満たしつつ𝝃をどの程度変化させられるかを表現する有向グラフを定義
残余容量(residual capacity)ce𝝃
実行可能フロー𝝃に関する残余ネットワークg𝝃の構成
枝(i,j)∈εfor𝛏ならば黒
枝(i,j)∈εrev𝛏ならば青
残余ネットワークを用いたフローの更新
残余ネットワーのs-tパス
増加パス上の残余容量の最小値が増やせる流量
最大流問題の増加パスアルゴリズム
増加パスアルゴリズム (augmenting path algorithm)
1956年、フォード・ファルカーソン (Ford-Fullkerson algorithm)
例
続き
図でのイメージ
最大流アルゴリズムの計算量
増加パスの選び方として、 複数候補がある場合には最も枝数の少ない増加パスを選ぶ
エドモンズ・カーフのアルゴリズム (Edmonds-Karp algorithm)
素股のアルゴリズム
ゴールドバーグ・タージャンのアルゴリズム (Goldberg-Tarjan algorithm)
シンク以外の頂点でもフローが溢れることを許容
ギャロ・グリゴリアディス・タージャンのアルゴリズム (Gallo-Grigoriadis-Tarjan algorithm)
パラメトリック最大流問題への応用
増加パスアルゴリズムの妥当性と最大流最小カット定理の証明
命題
最大流を用いた最小s-tカットの計算
任意の最大流𝛏では、残余ネットワークは増加パスを持たない
最大流を用いたs-tカット関数最小化アルゴリズム
4.2 マルコフ確率場における推論とグラフカット
はじめに
データの各変数が何らかの構造を持つ場合、 その構造を用いて様々な推論アルゴリズムを再帰的に記述できる
無向グラフを用いて変数間のマルコフ性を表す
マルコフ確率場の最大事後確率推定 (maximum-a-posteriori estimation)と 劣モジュラ最適化との関係
コンピュータービジョンにおけるグラフカット
4.2.1 マルコフ確率場
有限個のラベル集合L:={0,1,…,l)とd個の確率変数xi(i=1,…,d)について
各確率変数xiはl+1個のラベルのいずれかの値を取る
各変数xiに対応するような頂点集合V={1,…,d}をもつ無向グラフg=(V,ε)が与えられている
枝集合εの情報は確率変数同士の関係を表す
マルコフ確率ばでは、上式のような確率的な性質を表す
Bi:={xj:(I,j)∈ε}は、xiとグラフg上で隣接する頂点の集合を表す
条件付き独立性に基づいて、確率分布を分解する
Cはg上のクリーク(互いに隣接し合う頂点集合で極大なもの)全体からなる集合
𝚯cはクリークc内の頂点に対応する変数xc=(xi)i∈c上に定義された何らかの関数
マルコフ性に基づき確率分布かせ分解可能なモデル
確率伝搬などで利用される
マルコフ確率場で扱う分布は、一般的には正規分布などの指数型分布がほとんど
関数EX(x)は上式を元いて議論される
関数E(x):コスト関数、エネルギーと呼ばれる
インジングモデルなどの”統計物理学と人工知能技術への応用“で述べている統計物理モデルとの関係で p(x)の最大事後確率推定と 関数E(x)の最小化(エネルギー最小化(energy minimization)) との透過性に起因する
無向グラフgの形を、格子状に限定した議論
1階マルコフ確率場 (first-order Markov random field)
格子状グラフにおいてはクリークは、 グラフで隣接する変数ペアからなる要素数2の集合になる
関数は枝が存在する各ぺあごとに分解される
何らかの推論
データが与えられたときに、 それに応じて何らかの基準で xへの値の割り当てを行う演算
推論の最適化問題の式
xの取りうる範囲をLVと表記
右辺の第一項
各変数ごとに定義される量を組み込めるように加えてあるもの
θconstは定数
本質的には1項がなくても、第二項のみでも1階のマルコフ確率ばのエネルギー関数を表現可能
例:条件付き確率場 (Conditional random field)
具体例の概念図
例:ノイズのある画像yから元の画像xを復元する
x:直接は観測されない変数
xの確率分布p(x)
Cは何らかの定数
Y:観測可能な変数
変数yに対する観測値が得られたときの最大事後確率の式
4.2.2 エネルギー最小化における劣モジュラ性
エネルギー最小化問題はNP困難
xが2値変数である場合、ペア項θijが一定の条件を満たせば、多項式時間で計算が可能になる
ラベルが多数の場合でも、多項式時間で解けるための条件が知られている
文献27,28
2項変数で解けるための条件式
ペア項のある種の滑らかさを表す
元のグラフ上で隣接する頂点への0または1の割り当てがせ一致する傾向が高くなる
画像の場合に当てはめた解釈
画像中では隣と一致する場合が多い
境界面でエネルギー関数の値が大きくなるが、全体で言えば稀である
エネルギー関数の最小化をノイズ除去へ適用した例
劣モジュラ性
Vの部分集合として{},{1},{2},Vの4通り
各確率変数が二値変数である場合には、 2次項が列もジュラ性を満たせば、 グラフカットアルゴリズムで高速に解ける
具体的な方法
グラフカットのために、 再パラメータ化と呼ばれる操作を繰り返して エネルギー関数を標準形に変換する必要がある
グラフカットアルゴリズム
1階エネルギー最小化へのグラフカットに用いられるs-tグラフ
4.3 グラフ表現可能な劣モジュラ関数
はじめに
有向グラフのs-tカット関数の拡張
グラフ表現可能な劣モジュラ関数 (graph-representable submodular function)
いくつかの補助的な頂点を加えれば有向グラフのs-tカット関数として表すことができる関数
4.3.1 s-tカット関数の一般化
4.3.2 一般化したグラフカット関数の最小化
4.4 補足:プリフロー・プッシュ法*
第5章 劣モジュラ最適化を用いた構造正則化学習
はじめに
データの各変数間の構造を用いた機械学習
疎性モデリングへのアプローチ
事前情報を用いて実質的な次元を減らして学習性を向上させる
5.1 正則化による疎性モデル推定
はじめに
正則化(regularization)による蘇生モデルの推定
5.1.1 𝓁p ノルムによる正則化
損失関数の最小化
2乗誤差関数
“クロスエントロピーの概要と関連アルゴリズム及び実装例“で述べているクロスエントロピー誤差関数
損失関数を小さくするのみでは、過学習(over-fitting)が生じる
モデルを複雑にすればいくらでもデータDに対するごさは小さくできるが、 データ中のランダムな雑音までも拾ってしまう
正則化によるアプローチ
損失関数に加えて、 パラメータwが大きくなること (モデルが複雑になること)に対する罰則項Ωを加えて、 同時に最小化する
罰則項としては、 パラメータが縮退する(値を小さくしようとする)効果が 現れるノルムがよく使われる
ノルムはベクトルに対し距離を与えるための数学的道具
ℓpノルム(ℓp-norm)がよく使われる
原点(wの成分が全て0の点)から、 離れれば離れるほど値が大きくなる (最小化のためのば罰則が強くなる)]
ノルムを用いた正則化
L1ノルムを用いた方が解の多くの成分が0になりやすい
5.1.2 双対ノルムとフェンシェル共役*
双対ノルム (dual norm)
ノルムΩの双対ノルムΩ*
フェンシェル共役 (Fenchel conjugate)
任意の連続関数h:ℝd→ℝについて、 フェンシェル共役h*:ℝd→ℝは上式となる
命題
5.2 劣モジュラ関数から得られる構造的疎性
はじめに
ℓpノルムによる正則化は、各変数w1,…,wdに対して一様な扱いをする
正則化を拡張して、データの変数間にある関係を刑事的に利用する
正則化により得られる疎性の2つのタイプ
多くのパラメータを縮退させて0の値を取る形の疎性
ℓ1正則化等
事前に与えた変数上のグループ単位で考えることもできる
性質の近い複数のパラメータが、同じ値を取りやすいような疎性
5.2.1 グループ型の正則化
グループ正則化
前提条件
例:パラメータが3次元w=(w1,w2,w3)Tの場合での検討
3つのパラメータのうち、w1とw2がグループになっていて、w3はそうではない
グループ内ではℓ2正則化のように縮退のみ
グループ間ではℓ1正則化のように疎性と縮退の効果を持たせる
罰則としての記述
w1とw2は値が0になる時は同時になりやすい
重複なしℓ1/ℓpグルーブ正則化 (non-overlapping ℓ1/ℓp-group regularization)
同時に0になりやすい変数をグループに分割して 得られる{1,…,d}の部分集合の集まりをGとする
罰則項は上式となる
重複ありℓ1/ℓpグルーブ正則化 (non-overlapping ℓ1/ℓp-group regularization)
グループ正則化のイメージ
左側:重複なし
右側:重複あり
劣モジュラ関数から得られるグループ型正則化項
有限集合としてV:={1,…,d}を定義する
w∈ℝdに対し、supp(w)={I∈V : wi≠0}をサポート集合と呼ぶ
Wのℓpノルム分のコストとサポート集合に対するコストを考慮した関数
命題
ℓp正則化やℓ1/ℓp正則化との関係
グループ正則化を用いた数値例
劣モジュラ関数との関係
5.2.2 結合型の正則化
類似した変数の値が同じになるような疎性を与える
類似性を、変数上に定義された無向グラフを与えて表現する
順序がある場合は単純に一本の鎖のグラフ
画像中の画素のような場合は2次元格子のグラフ
値を近くしたい変数のペアは隣接するような無向グラフをg=(V,ε)と表す
結合正規化項は上式で表される
dij>0は各ペア(i,j)に対する重み
隣接する変数の値が同じであれば0
隣接する変数の値が離れれば離れるほど罰則が大きくなる
ℓ1ノルムが使われているので、 lassoの時間ように0をとる組が得られやすい
画像データを用いた学習によく使われる
全変動雑音除去 (total variation denoting)
gが鎖状グラフの場合は結合ラッソ (fused Lasso)と呼ばれる
結合正則化の概念図
結合正則化による最小2乗回帰の例
劣モジュラ関数との関係
結合正則化項は、無向グラフのカット関数のロヴァース拡張
結合正則化で得られる疎性
命題
5.3 劣モジュラ多面体上の分解可能凸関数最小化への帰着
5.3.1 近接勾配法の適用
最適化問題の目的関数は、 損失関数、正則化項共に凸関数
損失関数l(w)は微分可能であるが、 構造正則化行Ω(w)は微分不可能
勾配計算が必要になる、 通常の勾配法等の凸最小化アルゴリズムが適用できない
微分不可能な部分を、 一種の射影で置き換えて 勾配法と同様の手続きをする
最も単純な勾配法 (微分可能な凸関数のための最急降下法)について
ベクトルwを引数とする、 微分可能な凸関数l(w)の最小値を求める
微分可能な関数では、勾配(1階偏微分)∂l(w)/∂wiが計算できる
その勾配と逆向きにパラメータを動かせば、関数値を小さくできる
反復計算
w(k)とw(k+1)はそれぞれ更新前/更新後のパラメータ
∆l(w)=(∂l(w)/∂w1,…,∂l(w)/∂wd)T
ηk>0は更新の度合いをコントロールするパラメータ
アルゴリズム
近接勾配法は、 微分可能な部分にこの勾配法の手続きを適用する
現在の解w(k)の周りで l(w)を線形近似して得られる最小化問題を解き
最後の2次の項は、 更新によってlが現在の線形近似から 大きく離れないようにするための項
L>0はそれを調整するためのパラメータ
その解を用いて更新を行う
上式と等価
正則化項Ωがなければ、最急降下法の場合と同様の形になる
ηk=1/Lと考えれば良い
より一般的な式
この最適化問題はuの一種の射影を計算している
この問題の最適解をproxλΩ(u)とすると
UからproxλΩ(u)へ対応させる演算子は、近接演算子(proximity operator)と呼ばれる
以前の反復の解の情報を用いて更新
FISTA (Fast Iterative Shrinkage-Thresholding Algorithm)
重複ありℓ1/ℓpグループ正則化では、 計算コストの増加を防ぐために
グループの重複を避けるような補助変数を導入する
近接演算子の計算は以下に帰結して行うことができる
劣モジュラ最小化
変化しうるパラメータを色々変えながら劣モジュラ最小化を解くような問題
5.3.2 劣モジュラ多面体上の分離凸関数最小化による近接演算子
最適化問題を劣モジュラ関数の最適化へ帰着していく
構造化正則項Ωf,p(w)は、上式のように統一的に表される
これを一般的な最適化問題の式(上式)に代入すると
最終的に上式となる
最終行で与えた𝛹i(ti)は、ti≥0に対して上式と定義される
𝛹I(ti)はtiに関して凸関数なので、 近接演算子の計算は、 劣モジュラ多面体乗で分離凸関数 (各変数ごとに分離された凸関数)の 最小化問題を解けば良いことがわかる
分割アルゴリズムの適用 (Decomposition algorithm)
再帰的に、劣モジュラ関数の制限と縮約への分割を行い
各々に関して最小化計算を行い近接演算子を計算する
分割アルゴリズム
5.4 ネットワーク・フロー計算による高速化*
5.4.1 パラメトリック劣モジュラ最小化としての定式化
目的関数の中に変化しうるパラメータが入っていて、 その変化に対する解のシーケンスを計算するような最適化
ひとまず、上式のような最適化を考える
基多面体乗の分離可能凸関数の最小化問題
fは単調劣モジュラ関数
補題
補題
パラメトリック最適化問題が パラメトリック最大流問題として解ける
グループ型/結合型の構造正則化を生成する関数fは
パラメトリック最大流問題は、プリフロー・ブッシュ法と同じ計算量で計算可能
系
5.4.2 パラメトリック・フロー計算による高速化
ギャロ・グリゴリアディス・タージャン(Gallo Grigoriadis Tarjan, GGT)アルゴリズム
単調ソース・シンク(monotone source-sink)と呼ばれるクラスの問題
パラメトリック・プリフロー法アルゴリズム
5.5 補足:式(5.21)の計算について
コメント
[…] 機械学習プロフェッショナルシリーズ「劣モジュラ最適化と機械学習」読書メモ […]