研究成果の簡単な解説

これまで前原が行ってきた研究成果 (発表論文) の内容を簡単に紹介します.時系列順 (新しいほど上) になっています.

Continuous relaxation for discrete DC programming

連続最適化では「凸関数は最小化しやすく,非凸関数は最小化しにくい」と言われていますが,非凸関数とひとくくりにするのではなく,その中でも比較的扱いやすいものを特定しよう,という試みが一昔前に流行しました.その中で中心的な役割を果たしたのが差凸関数という「2 つの凸関数の差で表される関数」のクラスでした.最近前原・室田はこの関数クラスの離散類似物 (離散差凸関数) を定義し,その基本的な性質を調べました.この研究もその流れの上にあります.

本研究では離散差凸関数を最小化する実用的な手法を考えました.一般に,離散関数を最適化するアプローチに連続緩和があります.これは離散最適化問題に対応する連続最適化問題を作って連続最適化アルゴリズムで解いて離散解に丸める枠組みですが,離散差凸関数 g - h について f, g それぞれに連続緩和を施し,連続の最適化アルゴリズムを使うというのが本研究のアイデアです.

本研究の最も重要な結果は「離散凸部分は線型・離散凹部分は任意凹に拡張する (lin-vex extension) ことで離散最適解と連続最適解が一致する (整数性ギャップが消える)」ことです.これは凹関数が端点で最適値を取ることから直ちに導かれます.この拡張に基づく DC アルゴリズムは,離散最適化問題と連続凸関数の勾配計算を繰り返すものとなります.計算機実験の結果から,この枠組みはいくつかの問題に対して効率的な実用的アルゴリズムを与えることが分かりました.

Existence of outsiders as a characteristic of online communication networks

人間同士の繋がりを表現したグラフはソーシャルネットワークと呼ばれており,古くから社会学・統計物理学などで研究されてきました.近年の重要なテーマに,従来の (オフラインの) ソーシャルネットワークと Twitter などのオンラインのソーシャルネットワークが構造的にどう異なるのか,という点が注目されています.

ネットワークの特徴量の1つにアソータティビティがあります.アソータティビティは枝でつながっている頂点同士の次数相関で,正 (アソータティブ) であれば「(次数の意味で) 似た頂点同士が繋がっている」ことを意味しており,負 (ディスアソータティブ) であればその逆であることを意味します.オフラインのソーシャルネットワークはアソータティブであると言われており,オンラインソーシャルネットワークもそうなのかが気になりますが,実際に実験してみると (わずかに) ディスアソータティブとなることが報告されていました.本研究はこの構造を理解することを動機としてスタートしました.

本研究では,Twitter ネットワークではグラフから少数の頂点を除くことでアソータティビティを大きくできることを発見しました.他のネットワークでも同じことを試みた結果,この性質は Twitter ネットワークに特有のものであることがわかりました.いくつかの統計的な検証を行った結果,Twitter ネットワークの構造は下図のようなものであることが予想できます.すなわち,オフラインネットワークと同じようなクラスタ構造をもつネットワークに,アソータティビティを負にするような例外的な存在がくっついている,という形です.

Twitter ネットワークの構造模式図

Exact Computation of Influence Spread by Binary Decision Diagrams

ネットワーク上で情報がどのように伝播するかを考える問題を影響拡散問題といいます.これは [Kempe, Kleinberg, Tardos 2003] から爆発的に広がったテーマであり,口コミマーケティングの効果を推定する目的等で研究されています.影響拡散量は単調劣モジュラ性とよばれる良い性質をもち,定数近似最大化アルゴリズムを設計できるなどの特徴がありますが,一方で,その値の計算そのものは非常に難しい (#P-hard) ことが分かっています.既存研究では影響拡散量を厳密に計算することは諦めて,モンテカルロ近似を用いていました.

本研究では,影響拡散量を厳密に計算する世界初のアルゴリズムを提案しました.提案アルゴリズムは枝数が 100 程度のネットワークについて実用的な時間で拡散量を計算します.枝数 100 というと非常に小さく見えますが,元々が難しい問題なので,これでも画期的といえます (愚直にやると 2^100 通りのパターンを計算しなければならない).また,小さなネットワークは依然重要であること (実ネットワークは細かなクラスタに分かれているので,クラスタ内を解析すればよい),小さなネットワークでも高精度解を求めるのはモンテカルロ近似では困難であること,厳密解と比較することでモンテカルロ近似手法の誤差評価ができること,などが主な利点として挙げられます.

技術的には,二分決定図 (binary decision diagram; BDD)というデータ構造を用いたところに新規性があります.BDD は論理関数・集合族を表現するためのデータ構造で,本研究では影響が伝わる部分グラフのパターンを表現するために利用しています.たとえば下左図のグラフにおいて頂点 s から頂点 t に情報が伝わるような部分グラフ全部を表現する BDD は下右図となります (実線は各変数を使うこと,破線は各変数を使わないことに対応).一度この BDD を構築してしまえば影響拡散量は動的計画法によって容易に計算できるので,課題はどうやって BDD を構築するかの部分になりますが,本研究では フロンティア法と呼ばれる技法と BDD の高速集合族演算を組み合わせることで実現しました.BDD は北海道大学の湊研究室が活発に研究しているデータ構造です (参考: 動画 フカシギの数え方 で触れられている「最先端のアルゴリズム」は BDD の拡張です).本研究も前原が北海道大学に滞在した際に取り組んだ課題です.

ネットワークと対応する二分決定図

Scalable algorithm for higher-order co-clustering via random sampling

世の中には多くの複数の属性間の関係として表現されたデータが存在します.たとえばオンラインショップの購買データであれば「ユーザID×商品ID → 評価値」という 2 属性のデータで表されます.2 次元のデータを扱うには行列を用いるのが普通で,行列分解などの線形代数的な手法で処理できます.3 属性以上のデータを扱いたい場合,たとえば時間を考慮して「ユーザID×商品ID×時期 → 評価値」というデータを扱いたい場合はテンソルを用いることになります.

多属性データに対する基本的処理は共クラスタリングです.共クラスタリングでは各属性をクラスタリングすることでデータ全体のクラスタリングを行います.上述した購買データ解析でいえば どのタイプのユーザがどの商品をどの時期に買ったかという情報を取り出す処理に相当します.共クラスタリングはテンソル分解 (例: Expected tensor decomposition with stochastic gradient descent) によって実現できますが,これはそれなりに計算時間のかかる処理なので,超大規模データに適用するのは困難です.

本研究では多次元データの共クラスタリングを行う高速アルゴリズムを提案しました.提案手法は多次元データをハイパーグラフとして表現します.ハイパーグラフはグラフを拡張した概念で,グラフの枝 (サイズ 2 の部分集合) の代わりにハイパーエッジ (任意サイズの部分集合) を考えます.2 属性データ (すなわちグラフ) の最適な共クラスタリングを求める問題はグラフの最小カットを求める問題に帰着でき,グラフの最小カットには「ランダムに枝を縮約するだけで高確率で最小カットが求まる」(Karger-Stein のアルゴリズム) という性質があるので,これに基づく超高速アルゴリズムを設計できます.本研究ではハイパーグラフの最小カットに対しても Karger-Stein のアルゴリズムが拡張できることを示しました.これを用いることで,共クラスタリングに対しても超高速なアルゴリズムが設計できます.

アルゴリズムの入出力

Optimal Pricing for Submodular Valuations with Bounded Curvature

Budget allocation problem with multiple advertisers: A game theoretic viewと同じく予算配分問題に関連する問題です.予算配分問題は,様々な広告チャネル (テレビ広告・新聞広告・ネット広告 ...) の中でどれに予算を配分すれば最も高い広告効果が得られるか,ということを考える広告主の最適化問題でした.本研究ではこの問題をメディア (広告を表示する場をもつ人) の立場で考えました.すなわち,どのように広告に価格をつければメディアの収益を最大化できるかという最適化問題に注目します.

本研究ではこの問題を次のように定式化します:メディアは各チャネル x に価格 p(x) を付け,さらに各広告主に (互いに素な) チャネルの部分集合を購入候補として提案します.ここでチャネルの部分集合は広告主に受け入れられるように「X は 広告主の利益 f(X) - p(X) の最大化元である」という条件 (安定条件) を満たすようにします (ただし f は広告主の効用関数).この条件を満たす価格・割当の中で,メディアの収益 (= 全ての広告主に対する p(X) の総和) を最大化するものを求める問題を本研究では扱います.一般には,安定条件を満たす価格・割当を求める問題ですら非常に難しいので,ここでは特殊ケースを考えていくことになります.

本研究では,各広告主の効用関数 f は曲率の小さな単調劣モジュラ関数であると仮定します.劣モジュラ関数の曲率は,その関数が線型関数からどれだけ離れているかを表す指標です.最適な安定割当を求める問題は線型な効用関数については比較的容易に計算できるため,曲率が小さな関数についても,その手法を拡張したものの理論評価ができます能となりま.これによって,様々な設定における理論保証付きの価格付けを与えることに成功しました.

Enumerate Lasso Solutions for Feature Selection

Finding alternate features in Lassoに続いてスパース線形回帰の解の見落としに関する研究です.スパース線型回帰はデータに対して「y = A x, ただし x の非ゼロ成分の要素数が少ない」というモデルを当てはめる手法であり,入力変数の中で出力に効果的に働くものを見出す (特徴選択) ために使われます.スパース回帰には特徴量の見落としとよばれる「複数の成分に相関のある入力では,それらのうち一方が選択されない」という問題があり.もし最終的に選択された特徴量が利用者にとって納得できないものであれば (例えば,入っているであろう特徴量が含まれていなかったら),その結果は信頼されず,使われないことになります.

この問題を解決するため,本研究では複数の解候補を提示することで利用者に納得感を与える手法を提案しました.複数の解候補の提示は納得感を与えるための一般的なアプローチで,例えばオペレーションズ・リサーチ分野のスケジューリング問題などで広く利用されています.本研究はそのアイデアを特徴選択に導入したものといえます.

提案手法は解の非ゼロ成分を様々に指定して Lasso を解いたものをロス関数の昇順に出力します.これを効率的に行うには「最適解を求め,それに含まれる解を禁止した部分問題を作り,再帰的に解く」という,離散最適化問題の解を列挙する一般的なテクニック (Lawler のテクニック) が利用できます.理論的には,線形モデルに従う問題 (すなわち y = A x + noise という形で生成されている場合) では,適当な条件を満たすまで解を列挙すれば真の x の非ゼロ成分数を特定できることを示しました.これは圧縮センシングにおける零空間特性に基づく復元定理を拡張したものです.

Finding Alternate Features in Lasso

データに対して線形モデル y = A x を当てはめる手続きは線形回帰と呼ばれており,最も基本的なデータマイニング手法として広く用いられています.線形回帰において「x の非ゼロ成分が少ない」という制約を設けたものをスパース線形回帰といいます.実際の現象を扱う場合には,しばしば「入力変数 (特徴量) x のうち少数の成分しか出力 y に効かない」というのが妥当な仮定になりますが,スパース線形回帰はそのようなときに出力に効く少数の成分を見出すために用いられます.本論文のタイトルにある Lasso はスパース線型回帰を行うための標準的なアルゴリズムです.

スパース回帰の問題に特徴量の見落としがあります.例えば x の第一成分と第二成分が強く相関していたとしましょう.このとき Lasso は第一成分だけを含む解か,第二成分だけを含む解のどちらか一方だけを出力します.ところが,回帰はあくまでモデルなので,実際には出力されなかったほうの成分が重要なことが少なくありません.そこで本研究では,Lasso が出力した解の各成分に対してもしその成分を使わなかったとしたら.代わりにどの成分を使えばよいかを出力することで,ユーザの意思決定をサポートする手法を提案しました.

提案手法の出力は二部グラフとして可視化されます (下図).グラフの左側の頂点が Lasso 解に存在する特徴量,右側の頂点が代わりとなる特徴量です.これをクラスタリングなどすることで特徴量たちの関係の理解に繋がり,結果の解釈性が高まるだろうと考えています.

特徴量間の二部グラフ1 特徴量間の二部グラフ2

Computing a tree having a small vertex cover

複数のワイヤレスセンサー間の通信経路を設計することを考えます.センサーたちを頂点・通信可能なセンサー間を枝で表現したグラフを考えると,指定したセンサーたちが連結となるような最小の通信経路を求める問題はシュタイナー木問題とよばれる組合せ最適化問題になります.シュタイナー木問題は最も基本的なネットワークデザイン問題であり,これまでに様々な設定のもとで研究が行われてきました.

本研究では新しく頂点被覆が小さなシュタイナー木を求める問題を考えました.ここで頂点被覆とはネットワークのすべての枝に隣接する頂点集合のことをいいます.この問題は「ネットワーク上のトラフィックを監視しやすい通信経路の設計」を数学的に定式化したものと考えることができます.すなわち,シュタイナー木で表現される通信経路について,その全ての通信を監視できるようにいくつかのセンサに監視装置を設置することを考えると,監視装置はシュタイナー木の頂点被覆として定式されます.監視装置が高価で個数を最小化したいと思うと,この問題が得られます.この問題はネットワークアクティベーション問題と呼ばれる一般的な問題で表現できるため,O(log n) より良い近似は難しいことが示せます.そこで本研究では制限されたグラフクラスについて考えました.

各センサーの通信可能範囲が一定だとすると,センサーネットワークはユニットディスクグラフと呼ばれる特殊なグラフになります.本研究ではユニットディスクグラフに対する最小頂点被覆シュタイナー木問題が定数倍近似できることを証明しました.証明の方針は次のとおりです:まず,この問題を別の最適化問題 (連結支配集合問題) に帰着し,線型計画問題緩和して解きます.一般にこの帰着はユニットディスク性を保たないのですが,ユニットディスクグラフの幾何学的な性質 (例:下図) を用いると,この手続きが定数倍近似を与えることがわかります.

ユニットディスクグラフの幾何学的特徴

Joint word representation learning using a corpus and a semantic lexicon

大規模テキストデータ (コーパス) から単語のベクトル表現を学習する話はここしばらく盛んに研究されているトピックです.これまで自分たちのグループも Danushka Bollegala 准教授を中心として,このテーマに関連した研究を行ってきました.

コーパスだけから表現を学習するのは自然言語処理における1つの理想ですが,それには非常に多くの正規化されたデータが必要となるため,現時点ではハードルの高い仕事です.ところで自然言語処理分野では,古くから概念辞書と呼ばれるデータベースが整備されてきました.概念辞書には物事の「意味的関係」として,例えば "cat is animal" のようなエントリーが含まれています.折角整備されたデータベースがあるのだから,このデータを援用することで小規模コーパスでも高い品質の表現が得られないか,と考えるのはごく自然な発想です.実際 [Faruqui+, NAACL-HLT'15] はコーパスから得られた単語ベクトルを初期値とし,概念辞書に関する最適化を行うことで品質を向上させられることを示しました (この手の手法は retrofitting と呼ばれています).

本研究ではこの問題について,コーパスと意味辞書に対する同時学習というアプローチで,コーパスだけを用いて学習するよりも高品質な単語ベクトル表現が得られることを実証しました.同時学習というのは,コーパスのみの学習で用いられる最適化問題 (周辺の単語を予測する問題) に,概念辞書の内容を予測する項を正則化項として追加して学習する,というアプローチです.提案手法は既存手法 (retrofitting) よりも優位に高品質なベクトル表現が得られる手法となっており,同時学習の強力さを実証した形となっています.

Expected tensor decomposition with stochastic gradient descent

機械学習の様々な領域に高次元データが現れます.例えば「どんな人がどんな映画に興味があるのか」を知りたいと思った場合, (ユーザの性別, ユーザの年齢, 映画のジャンル) の3成分で添え字づけられたテーブルなどを考えます.このテーブルをテンソルと考え,T(ijk) ≒ Σc(h) U(ih) V(jh) W(ih) と軸ごとの積に展開することをテンソル分解といいます.テンソル分解は共通因子 (トピック) を抽出する処理に対応するので,データから隠れたグループを取り出す目的で使われることが多いです.

本論文では,分解したいテンソルが疎なテンソルの期待値として表現されている場合を考えました.この設定はオンラインサービスでデータを常時収集している状況で自然に表れます.この問題に対する一番安直な解法は,テンソルの全成分をメモリに保存して通常の手法を用いることですが,疎なテンソルも集まれば密となるので,最悪の場合に非常に多くのメモリを必要とすることが問題になります.これは長期間運用を考えるオンラインサービスには不向きな制約です.そこで本研究では,確率勾配法を用いることで,ほぼ最低限のメモリでテンソル分解を行う手法を提案しました.

提案手法のポイントは2階微分の情報を用いている点です.専門的になりますが,テンソル分解は非常に歪んだ非線型最適化問題であり,単純な勾配法とは相性が悪いことが知られていました.これは確率勾配法にした場合も同様で,単純な確率勾配法は収束が遅いことが観察できます.この問題を解決するため,提案手法ではヘッセ行列 (2階微分) を計算量的に損しないギリギリの範囲で取り入れて収束速度を改善しました.こうして得られた手法は,通常のテンソル分解の標準的手法である交互最適化法の確率最適化版と見ることができます.

Risk averse submodular utility maximization

影響最大化問題や予算配分問題など,期待値として表わされる劣モジュラ関数を最大化する問題が機械学習・データマイニングの分野で流行しています.しかし,特に金融や医療などの失敗したときの損害が大きな設定を考えると,期待値を最大化することよりも,不幸なことが起きたときの損害 (リスク) を減らすほうが重要となります.たとえば下図のグラフにおいて頂点 u または v から情報を拡散させたときにどれだけの頂点が影響されるかを考えてみます.u から拡散させると高い確率で左の部分グラフはすべて影響されますが,右の部分グラフはまず影響されません.一方で,v から拡散させると運が良いと両方の部分グラフが影響されますが,運が悪いとどちらの部分グラフにも影響を与えません.このことから,頂点 v のほうが頂点 u よりもリスキーだということができます.

リスクを考慮した最適化は連続最適化の分野では広く研究されてきましたが,離散最適化の分野では研究が少なく,興味のある問題に適用できる枠組みはありませんでした.本研究はこれを解消するために始めたものです.連続最適化の分野で現在最も広く用いられているリスク指標が VaR/CVaR です.これらは銀行のリスク計測の国際的取り決めバーゼルIIでも用いられています.目的関数値 (効用) が十分高い確率 (≧ a) で t を超えるとき,そのような最大の t を信頼水準 a の VaR (value at risk) といいます.VaR は直感的ですが,リスク指標として望ましい性質のいくつかを満たさないことが知られており,また,不連続関数なので最適化も困難です.そこで,目的関数が VaR 以下であるという条件のもとで効用の期待値をとったものを CVaR (conditional value at risk) と定義します (厳密には連続性の兼ね合いで,もう少し複雑に定義します).すると CVaR はリスク指標として望ましい性質を満たし,かつ,元の目的関数が凹なら CVaR も凹になるので最適化も容易となります.(※通常VaR/CVaRは最小化問題について定義しますが,ここでは最大化問題について定義していることに注意してください).

離散の場合も VaR/CVaR は同様に定義できますが,その扱いやすさは連続の場合と大きく異なります.まず,元の関数が劣モジュラであっても CVaR は劣モジュラにならないことがわかりました.そして,適当な計算量クラスに関する仮定のもと,信頼水準 a の CVaR について,任意の (1-a)(1-b) < 1/e なる b を近似率としてもつ多項式時間アルゴリズムが存在しないことがわかりました.連続の場合は信頼水準を 0.95 などに設定するのが標準的ですが,この結果は,そのような高い信頼水準は離散では (計算量的に) 達成できないことを示しており,もし離散でリスク最小化を行いたい場合は,メタヒューリスティクスなどの手法を用いるか,CVaRとは異なる離散向きのリスク指標を導入する必要がある,ということを意味します.

リスクの差が顕著なグラフ

Efficient PageRank tracking in evolving networks

グラフ G = (V,E) の頂点に重要度を割り振る標準的な手法に Personalized PageRank (PPR) があります.これは,ウェブブラウジングの行動をモデル化したランダムウォーク:「確率 c で今いる頂点の近傍へとランダムに移動,確率 1-c で予め指定した頂点上の分布 b に従ってランダムにジャンプ」の定常分布の値のことで,グラフの確率遷移行列 P を用いると連立方程式 (1-cP) x = (1-c) b の解 x としてあらわすことができます.PPRはこれまでに様々なタスクに利用されてきました (eg: 検索エンジン・ウェブスパムの検出,etc).しかし,現在注目されている大規模グラフのほとんどは急速に成長しているため,グラフの成長に応じてPPRを効率的に更新する方法が必要となっています.

本研究では,枝が動的に追加・削除されるグラフにおいてPPRを高速に更新する手法を提案しました.基本的なアイデアは枝が追加・削除される前後でPPRはあまり変化しないだろうという直感です.この直感を最大限に生かすため,数値線型計算における古典的な手法であるGauss-Southwell法を適用しました.この手法では適当な解からはじめ,残差が最大の成分を見つけて,その成分がゼロになるように更新する,という操作を繰り返します.静的なグラフのPPR計算に適用した場合,グラフサイズに依存しない (残差の値にのみ依存する) 反復回数で終了することが保証されています.成長するグラフに適用するため,枝の追加・削除による残差の変化量を見積もることにより幾つかの理論的成果が得られました.特に重要な結果は「枝を1本ずつm本順番に挿入していったときのPPR追従にかかる全計算時間は,枝をm本挿入した後に1回だけPPRを計算する時間の高々O(log m)倍しかかからない」というものです.

数値実験を行ったところ,提案手法は既存手法を大きく上回る効率を達成することがわかりました.それだけでなく,数値実験の結果が理論解析で示唆されるとおりになっており,非常に美しい結果だと言えます.理論だけではわからなかったこととして,各更新にかかる計算時間の頻度分布がべき則的な分布をもっていることが挙げられます.このことから多くの更新は短時間で終わることがわかりますが,この現象の詳しい解析は今後の課題です.

アルゴリズムの実行例

Budget allocation problem with multiple advertisers: A game theoretic view

複数の広告枠 (TVのCM枠・新聞の広告面・ウェブ広告etc) があるとき,どこにどれだけ広告を出せば最も多くの顧客が商品を購入してくれるのか,という問題は広告主にとっての基本的問題です.この問題は顧客の行動を適当にモデル化することでナップサック制約付き単調劣モジュラ関数最大化として定式化でき,予算配分問題 (budget allocation problem)と呼ばれて広く研究されています.

さて,実際の広告市場を見てみると,そこには複数の広告主がいて,顧客を互いに奪いあっています.この状況を数学的にモデル化するため,本研究では予算配分ゲーム (budget allocation game)というゲーム理論的モデル (n人非協力ゲーム) を考えました.このモデルでは,各広告主はそれぞれ自分の利益を最大化するために予算配分問題を解いているとします.モデルの設計で重要なのは「ある顧客が複数の広告主からアプローチされた場合にどう行動するか」という部分ですが,本研究では顧客はアプローチしてきた広告主をランダムな順でチェックする (ランダム順序モデル) を採用して解析しました.

本研究で得られた主な結果は以下の3つです,まず,(1) このゲームには純粋ナッシュ均衡が存在します.一般に任意のゲームは混合戦略の意味でのナッシュ均衡をもちますが (ナッシュの定理),このゲームは純粋戦略の意味でのナッシュ均衡をもつ珍しい例となっています.このことは実用的には「現実に実現された市場をナッシュ均衡と思って解析する」ことに一定の妥当性を与えます.次に,(2) 任意の純粋ナッシュ均衡における合計顧客数は,全広告主が協力して得られる合計顧客数の1/2倍以上となります.この比の上下限はprice of anarchy/stabilityと呼ばれており,これが定数ということは,各広告主が独立に行動しても業界全体としての機会損失が大きくない,すなわち健全な市場であることを意味します.最後に (3) 近似的なナッシュ均衡が効率的に計算可能です.これにより提案したモデルのシミュレートは通常の計算機によって十分可能なものとなりました.

トップに戻る