ネットワークフローを利用したCollective Flow Diffusion Model の効率的な推定

(1)

ネットワークフローを利用した

Collective Flow Diﬀusion Model

の効率的な推定

Eﬃcient Inference for Collective Flow Diﬀusion Model

via Minimum Convex Cost Flow Algorithm

赤木康紀

1∗

_西村拓哉

1 †

_田中佑典

1

_倉島健

1

_戸田浩之

1

Yasunori Akagi

1

_{, Takuya Nishimura}

1

_{, Yusuke Tanaka}

1

_,

Takeshi Kurashima

1

_{, Hiroyuki Toda}

1

_{日本電信電話株式会社 NTT サービスエボリューション研究所}

1

_{NTT Service Evolution Laboratories, NTT Corporation}

Abstract: Collective Flow Diffusion Model (CFDM) is a general framework to find the hidden movements underlying aggregated population data. The key procedure in CFDM analysis is MAP inference of hidden variables. Unfortunately, existing approaches fail to offer exact MAP inferences, only approximate versions, and take a lot of computation time when applied to large scale problems. In this paper, we propose an exact and efficient method for MAP inference in CFDM. Our key idea is formulating the MAP inference problem as a combinatorial optimization problem called Minimum Convex Cost Flow Problem (C-MCFP) with no approximation or continuous relaxation. On the basis of this formulation, we propose an efficient inference method that employs the C-MCFP algorithm as a subroutine. Our experiments on synthetic and real datasets show effectiveness of our method.

1. はじめに

GPS や Wi-Fi などの無線通信技術の発達により，位置情報の収集は容易になりナビゲーションなどの様々な分野で利用されるようになっている．しかし，プライバシーに対する懸念やそれぞれの個人を長時間に渡ってトラッキングすることの難しさから，個人ごとの詳細な位置情報を得ることは困難であることが多い．それに対し，人の位置情報を集計した人口データは，個人の位置情報を陽に含まないため比較的入手・利用されやすい．例えば，モバイル空間統計 [9] は，携帯電話の通信情報から計算される，正方形エリアの一定時間ごとの人口のデータである．別の例として，交通の分野においても，それぞれの車を追跡したデータではなく，道路に設置されたカメラやセンサよって得られた人口データが手に入る場合が多い．このような集計された人口データには様々な用途があるが，「人々がどこからどこへ移動したか」という情報を含まず，人々の移動の様子を直接知ることができないことからその応用可能性は限られたものになって ∗連絡先：赤木康紀，NTT，神奈川県横須賀市光の丘 1-1，[email protected] †現在，株式会社 NTT データ技術革新統括本部いる．このようなデータを活用するために，Collective Graphical Model と呼ばれる，集計された人口データに関する学習や推論を行うことのできる確率モデルが提案されている [7]．特に，CGM の特殊ケースである Collective Flow Diﬀusion Model (CFDM) [4] は，エリア間の人々の移動をマルコフ連鎖によってモデリングすることにより人々の移動を推定することが可能なモデルであり，交通ネットワーク [4] や都市空間 [3, 2]，や展示会場 [8] などの様々な場面において，人口データからその背後にある移動を解析するために利用されている． CFDM における解析において非常に重要なサブルーチンとなるのが，人口データと確率モデルのパラメータが与えられた際に，移動人数の MAP 推定を行う操作である．この操作は主に以下の二つの場合に用いられる．(i) 観測された人口データと人間の移動の確率モデルが与えられた際に，人々の流れを推定するため．ドメイン知識や少量のトラジェクトリデータを利用した学習によって人間の移動の確率モデルを設計することができた場合でも，エリア間の移動人数を知るためには MAP 推定を行う必要がある．(ii) 人々の流れと人間の移動の確率モデルのパラメータを同時に推定するための EM アルゴリズムの E ステップとして用いるため．人工知能学会研究会資料 SIG-FPAI-B901-02

(2)

CFDM が提案された論文においては MCMC[7] によって E ステップが実行されていたが，スケーラビリティに問題があった．この問題を解決するため，通常の期待値操作を MAP 推定によって代替する手法が提案され，後続研究において広く利用されている [3, 2, 8]．このように CFDM における移動人数の MAP 推定は非常に重要であるが，既存の手法には以下のような大きな欠点がある．(i) 連続緩和及びスターリングの近似の適用が必要であり，正確な MAP 推定を行うことができない．(ii) 連続緩和の適用により，出力される解が整数値ではなくなってしまう．「移動人数」という量が整数値でないのは不自然である上，非零の要素を含む疎ではない解になってしまい解の保持に多くのメモリが必要となってしまう．(iii) 大規模な問題に適用した場合，計算に非常に時間がかかってしまう．これらの問題を解決するため，本論文では CFDM における新しい MAP 推定の手法を提案する．鍵となるアイデアは，CFDM における MAP 推定問題を（非線形）最小費用流問題 (Minimum Cost Flow Problem, MCFP) と呼ばれる組合せ最適化問題として定式化することである．さらに，適切な定式化によって構築された MCFP においては，全てのコスト関数が離散凸性（凸性の離散空間における類似）を満たすことが証明できる．この事実は，定式化された MCFP が最小凸費用流問題 (Minimum Convex Cost Flow Problem, C-MCFP) に含まれる問題であることを意味する．C-MCFP には効率的に解くためのアルゴリズムが存在するため，これを用いることで元の MAP 推定問題を効率的に解くことができる．提案手法は以下のような長所を持つ． 1. 近似を一切用いない正確な MAP 推定である． 2. 出力される解が整数値であり，移動人数表す数値として自然である (1.5 人移動，などの解が出力されない)．さらに，解がスパースになりやすく，スパース行列などのデータ構造を用いることによって軽量に保持することが可能である． 3. C-MCFP の効率的なアルゴリズムを用いることにより，高速な推定が可能である．さらに，ハイパーパラメーターの設定が不要であり，計算時間が確率モデルや最適解の性質などに依存しにくいという，実用上使いやすい性質を持つ．最後に，人工データ及び実データを用いた実験において提案手法の有用性を検証した．ほとんどの場合において，提案手法は既存手法に比べて計算時間が 10 倍以上短くなり，解のスパース性を大きく向上させることが確認された．

2. 背景

2.1 問題設定

本論文を通して，正の整数 k について, [k] :={1, . . . , k} と表記する. 対象となる空間は n 個のエリアに分割さ れているとする. タイムステップ t においてエリア i にいた人々は，それぞれそのエリアに留まるか別のエ リアに移動し，タイムステップ t + 1 においていずれ かのエリア j で観測される．このプロセスが，T を全 体のタイムステップ数として t∈ [T − 1] について行わ れる． 本論文で取り組む問題は，タイムステップ t におけ るエリア i の人口 Nt,i(i ∈ [n], t ∈ [T ]) が与えられた 場合に，タイムステップ t にエリア i を主発し，タイ ムステップ t + 1 にエリア j に移動した人数 Mtij(i∈ [n], j∈ [n], t ∈ [T − 1]) を推定することである．

2.2 Collective Flow Diﬀusion Model

Γi ⊆ [n] をエリア i からの移動の到着先の候補とな るエリア全体の集合とする. 人口 Nt,i とエリア間の移 動確率 θi = {θij}j_∈Γi (∑ j∈Γiθij = 1 ) が与えられた とき, 移動人数 Mti={Mtij}_j_∈Γ i(t∈ [T − 1], i ∈ [n]) は Mti∼ Multi(Nt,i, θi) という多項分布に従うと仮定 する．N = {Nt,i | t ∈ [T ], i ∈ [n]} と M = {Mti | t∈ [T − 1], i ∈ [n]} が与えられたとき，尤度関数は P (M | N, θ) = T−1_∏ t=1 ∏ i∈[n]  _∏ Nt,i! j∈ΓiMtij! ∏ j∈Γi θMtij ij   (1) と計算できる．さらに，それぞれのエリアの人口 Nt,iと エリア間の移動人数 Mtiは，人数の保存則を表現する 関係式 Nt,i = ∑ j∈ΓiMtij, Nt+1,i = ∑ j∈ΓiMtji (t ∈ [T − 1], i ∈ [n]). を満たす． 我々の目的はエリア間を移動する人数を推定するこ とであるが，大きく分けて (i) N と θ が与えられたと きに M を推定する (ii) N が与えられたときに M , θ を推定するという二種類の問題が想定される．問題 (i) は，例えばドメイン知識や地理情報，もしくは人の移動に関する他のデータ（少数の個人のトラジェクトリなど）を用いて，対象となる空間における人の移動の 確率モデル（すなわち θ）を設計することができる場 合などに現れる．それに対し，問題 (ii) は θ に関する 手がかりが何もなく，M , θ の両方を N のみから推定 する必要がある場合に現れる．

(3)

いずれのケースにおいても， max M . P (M | N, θ) s.t. Nt,i= ∑ j∈Γi Mtij (t∈ [T − 1], i ∈ [n]), Nt+1,i = ∑ j∈Γi Mtji (t∈ [T − 1], i ∈ [n]), Mtij∈ Z≥0 (2) という MAP 推定問題を解くことが重要なサブルーチンとなる．問題 (i) の解としては，(2) の最適解をそのまま出力すればよい．問題 (ii) を解くための一般的な方 法は，M を隠れ変数，θ を確率モデルのパラメータと みなした EM アルゴリズムによって M と θ を同時に 推定する方法である．隠れ変数 M の期待値を MCMC によって計算するためには非常に長い計算時間が必要であるため，期待値計算を MAP 推定問題の解で置き換える方法が提案されており [6]，広く利用されている．このアプローチにおいては，問題 (2) を繰り返し解く必要がある．以上のように，いずれのケースにおいても，問題 (2) を効率的に解く手法の設計が非常に重要である．

3. 提案手法

3.1 最小凸費用流問題

（非線形）最小費用流問題 (Minimum Cost Flow Problem, MCFP) とは，以下のような組合せ最適化問 題である．G = (V, E) を有向グラフとし，各頂点 i∈ V は供給量 bi ∈ Z を，各辺 (i, j) ∈ E は容量 lij ∈ Z≥0 とコスト関数 cij :Z≥0→ R を持つとする．MCFP とは，各頂点における供給量制約と各辺における容量制 約を満たす G 上のフローの中で，コストを最小化する ものを求める問題である．数式で表現すると min x_∈Z|E|. ∑ (i,j)∈E cij(xij) s.t. ∑ j:(i,j)_∈E xij− ∑ j:(j,i)_∈E xji= bi (i∈ V ), 0≤ xij ≤ lij ((i, j)∈ E) (3) となる．本論文では整数値フローのみを考えることに 注意されたい（すなわち x∈ Z|E|_{）．一般的に，MCFP} (3) は NP-Hard であり効率的に解くことは難しい．しかし，コスト関数が特別な形の場合，効率的なアルゴリズムを設計することが可能になる．例えば，全てのコスト関数が線形関数である問題（一般的にはこのケースを単に最小費用流問題ということも多い）は多項式時間で解くことが可能であり，様々な効率的なアルゴリズムが提案されている．また，全てのコスト関数が「離散 凸性」cij(x + 1) + cij(x− 1) ≥ 2 · cij(x) (x = 1, 2, . . .) を満たす問題は最小凸費用流問題 (Minimum Convex Cost Flow Problem, C-MCFP) と呼ばれ，効率的なアルゴリズムが設計できることが知られている．

3.2 定式化の方法

最適化問題 (2) が C-MCFP として定式化できるこ とを示す．目的関数 (1) の対数をとり，M に依存しな い項を無視すると，目的関数は∑_t_{∈[T −1]}∑_i_∈[n]∑_j_∈Γ i

(− log Mtij! + Mtijlog θij) となる．問題 (2) は t の値

ごとに別々に解くことが可能であるため，各 t∈ [T −1] に対して最適化問題 min Mt . ∑ i∈[n] ∑ j∈Γi

(log Mtij!− Mtijlog θij)

s.t. Nt,i= ∑ j_∈Γi Mtij (i∈ [n]), Nt+1,i= ∑ j_∈Γi Mtji (i∈ [n]), Mtij ∈ Z≥0 (i∈ [n], j ∈ Γi) (4) を独立に解けばよい．問題 (4) を MCFP として定式化するため，以下のような手順で MCFP のインスタンスを構築する． 1. 頂点集合 V を{o, d, u1, . . . , un, v1, . . . , vn} とする． 2. 各 i∈ [n] について, コスト関数が 0 (定数関数) であ り，容量 Nt,iの辺 (o, ui) を追加する． 3. 各 i∈ [n] について, コスト関数が 0 (定数関数) であ り，容量 Nt+1,iの辺 (vi, d) を追加する． 4. 各 i∈ [n]，j ∈ Γiについて，コスト関数が fij(x) := log x!− x · log θijであり，容量 +∞ の辺 (ui, vj) を追加する． 5. S := ∑_i_∈[n]Nt,iとして，bo = S, bd =−S，bui = bvi= 0 (i∈ [n]) とする． 図 1 は MCFP としての定式化の一例を示している．上記の手順で構築された MCFP のインスタンスについて，次の二つの命題が成り立つ． Proposition 1. x∗を上記の手順で構築した MCFP のインスタンスの最適解とする．Mtij∗ = x∗uivj (i ∈ [n], j ∈ Γi) で定義される Mt∗について，Mt∗ は問題 (4) の最適解である． Proposition 1 は，MCFP を解くことによって問題 (4) の最適解を得ることができることを意味している．

(4)

,QSXW $UHD , 10 1 $UHD , 60 $UHD , 20 $UHD , 20 $UHD , 40 $UHD , 30 FRVWFDSDFLW\ log ! ⋅ log ௜௝∞ 0&)3)RUPXODWLRQ ௢ 90 ݋ ݀ ଵ ଶ ଷ ଵ ଶ ଷ ௗ 90 図 1: エリア数 n = 3 の場合の MCFP への定式化の例 Proposition 2. 上記の手順で構築された MCFP のイ ンスタンスについて，全てのコスト関数は離散凸性を 満たす．すなわち，任意の (i, j)∈ E について cij(x + 1) + cij(x− 1) ≥ 2 · cij(x) (x = 1, 2, . . .). Proposition 2 の証明. 定数関数が離散凸性を満たすこ とは明らかであるため，fijが条件を満たすことを確か めれば良い. fij(x+1)+fij(x−1)−2·fij(x) = log(x+

1)! + log(x− 1)! − 2 · log x! = log(x + 1) − log x ≥ 0.

より fijが離散凸性を満たすことが分かる． Proposition 2 は構築された MCFP が C-MCFP に属することを意味している．3.1 章で述べたように C-MCFP には効率的なアルゴリズムが存在するため，それを利用してもとの MAP 推定問題 (4) を効率的に解くことができる．

3.3 アルゴリズム

F :=∑_i_∈[n]Nt,iを対象エリアの総人口としたとき， 現実のデータを扱う際には F は非常に大きくなるこ とがある．例えば，首都圏エリアにおけるモバイル空 間統計データにおいては F は 106_–107_{程度となる．そ} のため，C-MCFP を解くための手法は F に関して劣 線形の時間計算量を持つことが望ましい．本論文では Capacity Scaling algorithm (CS)[5] と呼ばれる手法を 利用する．CS は，時間計算量が log F に比例するとい う点で，今回の問題を解くために望ましい性質を持っ

ている．n をエリアの数，m を Γiから定まるエリア

の隣接関係グラフの辺数としたとき，CS の計算量は

O(m2_{· log n · log F ) となる．アルゴリズムの詳細につ}

いては [1] などを参照されたい．

3.4 実行可能解が存在しない場合の対処

∑ i∈[n]Nt,i ̸= ∑ i∈[n]Nt+1,i である場合や |Γi| (i ∈ [n]) が小さい場合に，問題 (4) は実行可能解を持たな い場合がある．このような現象はノイズの多い現実のデータを扱う際に頻繁に発生する．この問題は，3.2 章で説明した MCFP のインスタンスの構築手順に，幾つかのステップを追加することで解決することができる． まず，C を十分大きな定数として，コスト関数 C· x， 容量 +∞ の辺 (o, d) を追加する．そして，S := max (∑_i_∈[n]Nt,i, ∑ i∈[n]Nt+1,i) として bo = S, bd = −S, bui= bvi= 0 (i∈ [n]) とする．このようにして作られ た新しい MCFP は必ず実行可能解を持ち，全ての辺のコスト関数が離散凸性を満たすため，3.2 章で構築した問題と同様の方法で解くことができる．

4. 実験

提案手法の実用性を示すための数値実験の結果について述べる．全ての実験は Xeon(R) Gold 6126 CPU (2.60GHz)x2，512GB メモリの 64-bit CentOS 7.3 マシンで行った．CS は C++ (g++ 4.8.5 with the -O3 option) で実装し，それ以外については python 2.7.12 及び SciPy で実装した．

4.1 比較手法

CFDM の推定のために一般的によく使われる手法 [3, 2, 8] を比較手法とした．この手法は各 t について， もとの問題 (4) の目的関数にスターリングの近似及び連 続緩和を適用した項 f (Mt) と，人数保存制約の破れを表 すペナルティ項 g(Mt) の重み付き和 f (Mt)+λ₂·g(Mt) を，Mt≥ 0 の制約下で最小化する．λ はペナルティ項の影響の強さをコントロールするハイパーパラメータ であり，λ が大きければ人数保存制約を守ることを優先 し，λ が小さければ尤度を大きくすることを優先する． この最適化問題は凸な目的関数と矩形制約を持つため， scipy.optimize などに実装されている L-BFGS-B 法などを使うことによって大域的最適解を得ることができ る．実験では，λ = 1, 10, 100 と設定した手法を比較手 法とした．

4.2 人工データ

まず，MAP 推定問題 (2) を解くために必要な計算時間と解の特徴について，人工データを用いてそれぞれ の手法を比較した．サイズ L× L のグリッド空間（エ リア数 n は L2_{になる）を考え，それぞれのセルがエ} リアを表すとする．_{∀i ∈ [n] について，Γ}iを [n] とする

(5)

表 1: F = 104_{の場合（上）と L = 20 の場合（下）の 10 個の人工の問題における平均計算時間（秒）．“>” がつ}

いた値は，時間制限の影響により過小評価されている．

θの生成方法 Dirichlet Exponential decay

L 10 20 30 10 20 30

Proposed 0.05 0.61 4.54 0.03 0.46 6.29

L-BFGS-B (λ = 1) 6.51 132.86 357.32 13.51 273.25 >911.22

L-BFGS-B (λ = 10) 7.40 143.14 387.09 13.87 281.40 >936.14

L-BFGS-B (λ = 100) 9.65 169.83 440.77 15.79 297.40 >975.64

θの生成方法 Dirichlet Exponential decay

F 103 104 105 106 103 104 105 106 Proposed 0.27 0.71 4.19 14.25 0.30 0.68 2.44 4.93 L-BFGS-B (λ = 1) 67.94 140.16 434.25 >804.52 128.43 323.87 >1000.00 >1000.00 L-BFGS-B (λ = 10) 80.24 149.29 503.72 >880.68 129.24 340.96 >1000.00 >1000.00 L-BFGS-B (λ = 100) 83.39 175.65 793.54 >899.83 129.40 356.24 >1000.00 >887.22 表 2: 実データにおける平均計算時間（秒）．日付 2015年4月1日 2015年4月5日セルサイズ 5km 2km 1km 5km 2km 1km Proposed 0.84 9.16 59.40 0.41 6.52 54.00 L-BFGS-B (λ = 1) 196.46 >1000.00 >1000.00 68.76 >940.84 >1000.00 L-BFGS-B (λ = 10) 14.96 >1000.00 >1000.00 10.90 >1000.00 >1000.00 L-BFGS-B (λ = 100) 2.04 >811.94 >1000.00 0.99 >697.78 >1000.00 （すなわち，エリア間の隣接関係が「全結合」であると する）．T = 2 とし，F をグリッド空間の人口の総和，

p1, p2 ∼ Dirichlet(1) として Nt,i ∼ Multi(F, pt) (t =

1, 2) で各エリアの人口をランダムに生成した．θ は以 下の二通りの方法で生成した． 1. 各 i∈ [n] について独立に θi ∼ Dirichlet(1) とする 方法．この方法を “Dirichlet” と呼ぶ. 2. dist(i, j) をセル i とセル j の間のユークリッド距離と して θij = exp(−dist(i, j))/ ∑ j_∈Γiexp(−dist(i, j)) とする方法．この方法を “Exponential decay” と呼ぶ. この方法は，長距離よりも短距離を移動する頻度が高いという人間の移動の性質を反映している． 計算時間とエリア数 L2_{及び総人口 F の関係を明らか} にするため，F を 104_{に固定して L = 10, 20, 30 と動か} した場合，及び L を 20 に固定して F = 103_{, 10}4_{, 10}5_, 106_{と動かした場合それぞれについて，ランダムに 10} 個のインスタンスを作成しそれぞれの手法で解いた．表 1 にそれぞれのアルゴリズムの 10 個のインスタンスにおける平均計算時間（秒）をまとめている．それぞれの実験は 1000 秒の時間制限つきで行い，時間制限を超えた場合は計算時間は 1000 秒として計算されている．その場合，平均値は過小評価されることになる．これを明確にするために，一つ以上のインスタンスに おいて時間制限の超過が起こった場合には表中で “>” の記号を付けている．L-BFGS-B 法を用いた手法は問題のサイズが大きくなった場合に時間制限以内に解を 出力できないことが多いのに対し，提案手法は L や F が大きくても非常に短い計算時間で安定して問題を解くことができている． 提案手法と L-BFGS-B 法 (λ = 1) の出力する解の性 質を比較するため，L = 5, F = 102_{, で θ のタイプが} “Exponential decay” 及び L = 5, F = 103_{, θ のタイ} プが “Exponential decay” のインスタンスをそれぞれの手法で解き，解の様子を図 2 に示した．得られたサ イズ L2_{× L}2 _{の解行列がヒートマップとして図示され} ている．解行列の (i, j) 成分はエリア i からエリア j に 移動したと推定された人数を表している．スパース性を調べるため，1 以上の値を最も濃い色で，0 を最も薄い色（白）で表示している．L-BFGS-B 法によって得られた解は多くの 0 ではない要素を含みスパースではなくなっているのに対し，提案手法による解は非常にスパースになっている．解のスパース性を (10−4以下の要素数)/(全要素数) で計算すると，提案手法では 90%, 67%となるのに対し，L-BFGS-B 法においては 0%, 0%となり，提案手法の出力が非常にスパースであることがわかる．この結果は，提案手法による解はスパース行列などのデータ構造を用いて非常に小さな記憶容量で保持することができることを意味している．

4.3 実データ

次に，MAP 推定問題 (2) を解くために必要な計算時間と解の特徴について，現実の時空間データを用いてそれぞれの手法を比較した．データとして，2015 年 4 月 1 日（平日）と 2015 年 4 月 5 日（休日）における東京都及び神奈川県のモバイル空間統計データ [9] を

(6)

to from Proposed Spartsity: 90% to from L-BFGS-B (λ = 1) Sparsity: 0% to from Proposed Spartsity: 67% to from L-BFGS-B (λ = 1) Sparsity: 0% 図 2: 提案手法（左側）と L-BFGS-B 法 (λ = 1)（右 側）によって得られた MAP 推定問題の解の比較．上 側は (L, F ) = (5, 102_{)，下側は (L, F ) = (5, 10}3_{) の場} 合．スパース性を調べるため，1 以上の値を最も濃い色で，0 を最も薄い色（白）で表示している． 利用した．それぞれの日付において，Ntは t 時 (t ∈ {0, 1, . . . , 22}) の各エリアの人口を表す．セルサイズご とのそれぞれの手法の性能を比較するため，セルの人口を集計してセルサイズ 5km × 5km，2km × 2km， 1km × 1km のデータを作成した．それぞれのデータ セットにおけるセルの個数はそれぞれ 200 個，1017 個， 3711 個となった．人口データにおける “Exponential decay” と同様の方法で θ を作成し，dist(i, j) をグリッ ド空間におけるセル i とセル j のユークリッド距離と して Γi={j | j ∈ [n], dist(i, j) ≤ 5} と設定した． 実験結果は表 2 にまとめられている．人工データを用いた実験の際と同様に，それぞれの実行について 1000 秒の時間制限を設けている．提案手法は全ての設定において約 60 秒程度で解を計算できているのに対し，L-BFGS-B 法は λ の値に関係なく 2km× 2km や 1km × 1km のケースにおいて制限時間以内に解を求められていない．この結果は，提案手法の有効性を示している．

4.4 まとめ

本論文では，集計化された位置情報を解析するためのモデルである Collective Flow Diﬀusion Model の MAP 推定問題を正確かつ高速に解くための新しい手法を提案した．提案手法では，MAP 推定問題を最小凸

費用流問題と呼ばれる組合せ最適化問題として定式化し，Capacity Scaling algorithm を適用することで最適解を得る．人工データ及び実データを用いた実験により，提案手法は計算時間の面でも解のスパース性の面でも既存手法より優れていることを確認した．

参考文献

[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.

Network Flows: Theory, Algorithms, and Appli-cations. Prentice-Hall, Inc., 1993.

[2] Y. Akagi, T. Nishimura, T. Kurashima, and H. Toda. A fast and accurate method for estimat-ing people flow from spatiotemporal population data. In IJCAI, pages 3293–3300, 2018.

[3] T. Iwata, H. Shimizu, F. Naya, and N. Ueda. Esti-mating People Flow from Spatiotemporal Popula-tion Data via Collective Graphical Mixture Mod-els. ACM Transactions on Spatial Algorithms and

Systems, 3(1):1–18, 2017.

[4] A. Kumar, D. Sheldon, and B. Srivastava. Collec-tive Diﬀusion Over Networks: Models and Infer-ence. In UAI, 2013.

[5] M. Minoux. Solving integer minimum cost flows with separable convex cost objective polynomially. In Netflow at Pisa, pages 237–239. Springer, 1986. [6] D. Sheldon, T. Sun, A. Kumar, and T. Dietterich. Approximate Inference in Collective Graphical Models. In ICML, pages 1004–1012, 2013. [7] D. R. Sheldon and T. G. Dietterich. Collective

Graphical Models. In NIPS, pages 1161–1169,

2011.

[8] Y. Tanaka, T. Iwata, T. Kurashima, H. Toda, and N. Ueda. Estimating latent people flow without tracking individuals. In IJCAI, pages 3556–3563, 2018.

[9] M. Terada, T. Nagata, and M. Kobayashi. Popu-lation Estimation Technology for Mobile Spatial

Statistics. NTT DOCOMO Technical Journal,