修士論文 要旨

有向ハイパーグラフ上の全変動正則化

1 はじめに数理情報学専攻 48-196232

山中遥太

指導教員

岩田覚教授

3 提案手法：有向ハイパーグラフ上の全変動正則化

機械学習において構造正則化は，モデルのパラメータに特定の構造を持たせる正則化であり，過学習を避けモ

3.1

有向ハイパーグラフ上の全変動正則化

デルの解釈性を向上させる．無向ハイパーグラフ上の有向ハイパーグラフ D = (V, E) では，各有向ハイ全変動正則化 [3] は，パラメータの成分にグループ単位

パーエッジ e ∈ E が始点集合 T (e) ⊆ V と終点集合で同じ値を持たせる構造正則化である．

H(e) ⊆ V を持つ．各頂点がモデルのパラメータの各成

本研究では，無向ハイパーグラフ上の全変動正則化の拡張として，有向ハイパーグラフ上の全変動正則化，およびその正則化項の近接作用素計算手法を提案する．

分に対応している有向ハイパーグラフ D を考える．D上の全変動正則化項をTVD (w) =有向ハイパーグラフ上の全変動正則化は，グループ単位∑max{ce ( max wi − min wi ), 0}i∈T (e)e∈Ei∈H(e)でのパラメータの増加性を導く．論文の分野推定の数で定義する．ce は枝 e の重みである．TVD は始点集合値実験では，有向ハイパーグラフ上の全変動正則化によの最大成分と終点集合の最小成分の差を小さくするたり著者の特徴を捉えたパラメータ推定が可能になり，無め，推定されるパラメータは始点集合から終点集合に

向ハイパーグラフ上の全変動正則化に比べ推定精度がかけて，グループ単位で増加性を持ったものとなりや改善されることを確かめた．

すい．

2 既存手法：無向ハイパーグラフ上の全変動正則化
機械学習において正則化では，損失関数 f : R → Rnと正則化項 Ω : Rn → R の和を最適化する．つまり

3.2

近接作用素の計算

TVD の近接作用素
proxλTVD (u) = argminw∈Rnの計算手法を提案する．有向ハイパーグラフのカット関数 κD は，δD (A) = {e ∈ E | T (e) ∩ A ̸= ∅, H(e) ∩minn f (w) + λΩ(w)(V \ A) ̸= ∅} として κD (A) =w∈Rを解くことで，モデルのパラメータの推定を行う．特に，パラメータに特定の構造を持たせる正則化は構造正則化と呼ばれる．モデルの特徴に合わせた構造正則化を行うことで，過学習の防止や，モデルの解釈性向上が∑
3.1. B(κD ) = {x ∈ RV | i∈A xi∑
κD (A)(∀A ⊂ V ), i∈V xi = κD (V )} として，構造正則化の一種として，無向ハイパーグラフ上の全各成分に対応している無向ハイパーグラフ H = (V, E)を考える．H 上の全変動正則化では，∑e∈Ee∈δD (A) ce で定義さ定理s∈B(κD )変動正則化 [3] がある．各頂点がモデルのパラメータの∑れる．本研究では次の定理を証明した．

proxλTVD (u) = − min期待できる．

TVH (w) =1∥w − u∥22 + λTVD (w)2∑1i∈V2≤1(λsi −ui )2 + ∥u∥22 .
2

この最適化問題は基多面体上の分離凸関数最小化問題であり，以下のパラメトリック劣モジュラ関数の最小解が切り替わるような α ∈ R（ブレークポイント）を全て求める問題と等価であることが知られている [1]：ce (max wi − min wi )i∈eκαD (A) = κD (A) −i∈e

∑ uii∈Aλ− |A|α .

を正則化項として用いる．ce は枝 e の重みである．

TVH は，ハイパーエッジ内の最大成分を小さく，最小定理 3.2. D の各ハイパーエッジに対して，図 1 のよ成分を大きくすることで，ハイパーエッジ内の成分全てうに補助頂点と補助枝を加え有向グラフ G を構築する．に同じ値を持たせる．本研究ではこれを拡張し，有向ハ

この時，イパーグラフ上の全変動正則化を提案する．

καD (A) = min κG ({s} ∪ A ∪ B) −B⊆W

∑ uii∈V

λ− |V |α .

有向ハイパーグラフ上の全変動正則化 (山中遥太)

図 1. καD のグラフ表現．

したがって，καD は，G に最大流アルゴリズムを適用することで，最小化が可能である．この時，パラメトリック最大流アルゴリズム [2] を用いることで，一つの最大流問題を解くのと同じ最悪計算量で κα
D の全てのブレークポイントを計算する事が可能である．

図 2. 各正則化の誤答率．誤答率計算の対象とした論文は，左上：全論文，右上：過去（2011 年以前）から直近（2012 年以降）にかけ平均ラベルが増加している著者の論文，左下：過去から直近にかけ平均ラベルが減少している著者の論文，右下：ラベルが全て同一の著者の論文．

4 数値実験：論文の分野推定
4.1

実験設定

機械学習分野の論文 (9274 件) のラベルを 1，データベース分野の論文 (6915 件) のラベルを-1 とし，いくつかの論文に正解ラベルが与えられたもとで，残りの論文のラベル推定を行った．損失関数はラベルベクトルl ∈ {−1, 0, 1}V との二乗誤差 f (w) = 12 ∥l − w∥22 とし，無向ハイパーグラフ H = (V, E) 上と，３種類の有向ハ→→←←↔

イパーグラフ D = (V, E ∪ E), D = (V, E ∪ E), D =←→(V, E ∪ E ∪ E) 上で全変動正則化を行う．ここで，無向ハイパーエッジ e ∈ E は各著者に対応し，その著者→ ←の全ての論文から構成される．E, E はいずれも有向ハイパーエッジのみを含む．各著者の論文を 2011 年以前に採択されたグループと，2012 年以降に採択された→グループに分割し，E では前者を始点集合，後者を終←点集合とし，E では後者を始点集合，前者を終点集合とした．事前に与えたラベル数は 500, 1000, ..., 5000 とした．

4.2

結果ラメータに方向性が導かれなかったためだと考えられる．全てのタイプの著者で精度の良い推定ができたため，TV↔ が既存手法の TVH より低い誤答率を記録でDきたと考察できる．

5 結論
有向ハイパーグラフ上の全変動正則化，およびその正則化項の近接作用素計算手法を提案した．論文の分野
推定の数値実験では，各著者の過去の論文と直近の論文との間に両向きに有向ハイパーエッジを張ることで，各著者の特徴を捉えたラベル推定が可能になり，無向ハイパーグラフ上の全変動正則化に比べ推定精度が改善されることを確かめた．本実験では損失関数を二乗誤差としたが，損失関数が二乗誤差以外の場合でも近接勾配法を用いた最適化が可能であり，様々な問題設定への応用が可能である．

参考文献

結果は図 2 のようになった．TV→ がラベルの増加性Dを導き，ラベルが増加している著者の論文に対して精度の良い推定をしている．同様に減少著者の論文に対して TV← が低い誤答率を記録している．両方向に枝をD貼った TV↔ は，増加・減少著者の両方で精度の良い推D定ができており，データの特徴とは逆方向の方向性を導く枝を張っても，推定精度はそれほど悪化しない事が分かる．また，ラベル一定の著者の論文に対しての TV↔
Dの低誤答率は，増加・減少の効果が打ち消し合い，パ[1] Satoru Fujishige. Submodular Functions and Optimization. North-Holland, 1991.
[2] Giorgio Gallo, Michael D. Grigoriadis, and Robert E.
Tarjan. A fast parametric maximum flow algorithm
and applications. SIAM Journal on Computing,18(1):30–55, 1989.
[3] Matthias Hein, Simon Setzer, Leonardo Jost, andSyama S. Rangapuram.
The total variation on
hypergraphs-learning on hypergraphs revisited. In
Advances in Neural Information Processing Systems,pages 2427–2435, 2013.