IMI共同利用研究 公開ワークショップ「実社会に見られる複雑なネットワークと無限粒子系の交差点Ⅱ」
本研究課題の目標：「無限粒子系と実問題の共通部分を見つける」
ワークショップの目的：
問題意識の共有と話題提供
問題意識：
昨年度の課題の継続・発展→最初の講演で話したいこと
IMI共同利用研究「実社会に見られる複雑なネットワークと無限粒子系の交差点Ⅱー複雑ネットワーク上の情報流ー」（組織委員）
森 隆大（京都大学 数理解析研究所 ）林 晃平（東京大学大学院数理科学研究科）
須田 颯（慶應義塾大学 理工学研究科）
上島 芳倫（北海道大学 数理・データサイエンス教育研究センター）
長田 翔太（九州大学マス・フォア・インダストリ研究所）
新井 裕太（千葉商科大学 基盤教育機構）
早川 知志（Mathematical Institute, University of Oxford）（アドバイザー）
恐神 貴行（IBM東京基礎研究所）

IMI共同利用研究 公開ワークショップ「実社会に見られる複雑なネットワークと無限粒子系の交差点Ⅱ」
ワークショップのキーワード：
行列式点過程，サンプリング，機械学習，etc…
今日の講演：
早川 知志（University of Oxford・大学院生）
数値積分のための点過程とサブサンプリング
平尾 将剛（愛知県立大学・准教授）
球面上の行列式点過程とその周辺
中村 ちから（株式会社ニコン 研究開発本部 数理技術研究所）
機械学習手法による極値統計学のハイパーパラメータ選定について

恐神 貴行（IBM東京基礎研究所）
強化学習における多様性

IMI共同利用研究 公開ワークショップ「実社会に見られる複雑なネットワークと無限粒子系の交差点Ⅱ」
参加者の方へのお願い
ZOOM表示名とGoogle form登録名の統一をお願いします．
スクリーンショットや録画等はご遠慮ください．
本ワークショップは録画しています．
講演中はマイクをオフにしてください．
進
行：講演30分~40分＋ディスカッション（共同ホスト）＋休憩10~20分．
質疑応答：共同ホストは随時チャット・音声．
参加者は・講演中→チャット ・講演後→チャット・挙手
IMI共同利用研究「実社会に見られる複雑なネットワークと無限粒子系の交差点Ⅱー複雑ネットワーク上の情報流ー」（組織委員）

森 隆大（京都大学 数理解析研究所 ）林 晃平（東京大学大学院数理科学研究科）
須田 颯（慶應義塾大学 理工学研究科）
上島 芳倫（北海道大学 数理数理・データサイエンス教育研究センター）
長田 翔太（九州大学マス・フォア・インダストリ研究所）
新井 裕太（千葉商科大学 基盤教育機構）
早川 知志（Mathematical Institute, University of Oxford）（アドバイザー）

恐神 貴行（IBM東京基礎研究所）

実社会に見られる複雑なネット
ワークと無限粒子系の交差点

九州大学マス・フォア・インダストリ研究所
長田翔太
2021年8月19日（木）「実社会に見られる複雑なネットワークと無限粒子系の交差点Ⅱ」

昨年度の振り返り
昨年度の目標： 無限粒子系：ポイントクラウド，信号，ランダムウォーク．．．
 複雑なネットワーク：複雑ネットワーク，ニューラルネットワーク．．．
→これらのインターセクションを見つける．
昨年度の成果：・行列式点過程を用いたモンテカルロ法による数値積分．
→離散化・カップリングによるコストと精度のトレードオフを提案．
今年度の方針：・昨年度の議論を継続・発展させる．
→具体的課題の設定・広がりの開拓.
中心的トピック：行列式点過程，機械学習目次

内容：昨年度の振り返り（MC with DPP，コストと精度のトレードオフ）
行列式点過程（Determinantal Point Process）
Monte Carlo with DPPDPPの離散化

DPPのカップリング

窓ガラスの雨粒 と 鳥の巣
窓ガラスに付いた雨粒

雨粒は窓ガラスに一様の確率で当たる

鳥の巣（ノスリ）の分布

巣はお互いに距離をとる

これらは異なる点過程で表現される
右図：G. Akeman, et al., 2021, Journal of Theoretical Biology.より引用

Poisson点過程 と 行列式点過程：窓ガラスの雨粒 と 鳥の巣
鳥の巣
行列式点過程窓ガラスの雨粒
PoiSSON（ポアソン）点過程

規則性がない点配置
窓ガラスの雨粒・月のクレーター
自由粒子のスナップショット

整然とした点配置
動物の巣・電波の基地局
相互作用を持つ粒子のスナップショット

それぞれ500個の粒子

行列式点過程の概要
粒子系
ランダムな粒子配置のスナップショット

粒子配置のランダムダイナミクス
行列式点過程は反発力が働く粒子系を表す．

Poisson点過程
無相関

行列式点過程負の相関（反発力）

連続モデル，離散モデルの様々な対象に現れる．
数理モデリングでは，行列式点過程はRepulsiveなモデルのサンプリングとして注目される．
アイテムのピックアップ，Lebesgue測度の近似，クラスタリング

引用：
Hough, J. B., Krishnapur, M., & Peres, Y. (2009). Zeros of Gaussian analytic functions and determinantal point processes (Vol. 51). American Mathematical Soc..

行列式点過程の構成定理：有限粒子１

 𝑆 = 1, … , 𝑁 ：有限集合 𝐿: 𝑆 × S → ℂ ：正定値行列．
 このとき，෍𝑋⊂𝑆

det 𝐿𝑋 = det 𝐼 + 𝐿 .

 0,1 𝑆 上の確率測度を次で定義：ℙ 0𝑆−𝑋 1 𝑋 ≔det 𝐿𝑋.
det 𝐼 + 𝐿

このとき，𝑋 ⊂ 𝑆上の粒子の存在確率は，ℙ 1 𝑋 = det𝐿
ቤ .
𝐼+𝐿 𝑋

点過程の定義

𝑆: Polish空間．完備距離付け可能な可分空間
配置空間：
漠位相：

Conf 𝑆 = 𝑆上の非負整数値Radon測度 𝜉 = σ𝑛 𝛿𝑥 𝑛 全体
න 𝑓 𝑥 𝜉𝑛 𝑑𝑥 → න 𝑓 𝑥 𝜉(𝑑𝑥)𝑆∀𝑓 ∈ 𝐶𝑐 (𝑆)𝑆
𝒳

Conf(𝑆)-値確率変数 𝒳 （またはその分布ℙ ）を点過程という．
 𝑆が離散位相空間かつ，点過程 𝒳 が多重点を持たないとき，配置空間 Conf 𝑆 は 0,1 𝑆 （または 2𝑆 ） と同一視できる．

行列式点過程の定義

 点過程 𝒳 は以下の相関関数 𝜌𝑛 で決定される:
න𝑛𝑘

𝜌 𝑥1 , … , 𝑥𝑛 𝑑𝑚
𝑘

𝐴1 1 ×⋯×𝐴𝑙 𝑙⊗𝑛𝑙=𝔼 ෑ𝒳 𝐴𝑖 !
𝑖=1 𝒳 𝐴𝑖 − 𝑘𝑖 !

ただし𝐴1 , … , 𝐴𝑙 はdisjoint，𝑘1 + ⋯ + 𝑘𝑙 = 𝑛，𝑚は𝑆上のRadon測度．

 𝜌1 (𝑥) は点密度を表す．

 𝑆が離散位相空間のとき， 𝑚 = σ𝑥∈𝑆 𝛿𝑥 に対して
𝜌𝑛 𝑥1 , … , 𝑥𝑛 = ℙ 1 𝑥1 ,…,𝑥𝑛 .
 相関関数が核関数𝐾: 𝑆 × 𝑆 → ℂの行列式で与えられる点過程を行列式点過程という．
𝜌𝑛 𝑥1 , … , 𝑥𝑛 = det 𝐾 𝑥𝑖 , 𝑥𝑗𝑖,𝑗=1,…,𝑛行列式点過程とPoisson点過程との違い
定常Poisson点過程

𝜌𝑛 𝑥1 , … , 𝑥𝑛

Ginibre点過程
𝑛=෍

𝜌1 (𝑥𝑖 )𝑖=1

粒子はお互いを気にしない𝜌2 𝑥, 𝑦 = 𝜌1 𝑥 𝜌1 (𝑦)分散は大きい𝕍 ෍𝑥∈𝒳1𝐵𝑟 (𝑥)~𝑟 2 as 𝑟 → ∞異なる場所の粒子分布は独立𝜎 𝒳𝐵𝑟 ⊥ 𝜎 𝒳𝐵𝑟𝑐𝜌𝑛 𝑥1 , … , 𝑥𝑛 = 𝑑𝑒𝑡 𝐾(𝑥𝑖 , 𝑥𝑗 )
粒子がお互いを避ける𝜌2 𝑥, 𝑦 ≤ 𝜌1 𝑥 𝜌1 (𝑦)分散が小さい𝕍 ෍𝑥∈𝒳1𝐵𝑟 (𝑥) ~𝑟 as 𝑟 → ∞剛性を持つ𝒳(𝐵𝑟 ): 𝜎 𝒳𝐵𝑟𝑐 -可測
基地局の配置モデル
ルベーグ測度の近似

Poisson点過程

行列式点過程行列式点過程の構成定理
 𝑆：可算基を持つ局所コンパクトHausdorff空間
 𝑚：𝑆上のラドン測度• 𝑆, 𝑚 の典型例は ℤ𝑑 , σ 𝛿𝑧 ,
 𝐾: 𝑆 × S → ℂ
Macchi(1975)
連続な𝐾が以下①－③を満たすとき行列式点過程が存在する：① 𝐾 𝑥, 𝑦 = 𝐾(𝑦, 𝑥)② 𝒦𝑓 ≔ ‫𝑥 𝐾 𝑆׬‬, 𝑦 𝑓 𝑦 𝑚 𝑑𝑦 , 𝑓 ∈ 𝐿2 (𝑆, 𝑚)はトレイス・クラス．
③ 𝑂 ≤ 𝒦 < 𝐼.

Macchi(1975)ではFermion processと呼んでいる．
𝐾 𝑥, 𝑦 = ෍ 𝜆𝑛 𝜑𝑛 𝑥 𝜑𝑛 (𝑦) .
𝑛∈ℕℝ𝑑 , 𝑑𝑥

行列式点過程の構成定理：無限粒子
 𝑆：可算基を持つ局所コンパクトハウスドルフ空間
 𝑚：𝑆上のラドン測度• 𝑆, 𝑚 の典型例は ℤ𝑑 , σ 𝛿𝑧 , ℝ𝑑 , 𝑑𝑥
 𝐾: 𝑆 × S → ℂ
Macchi(1975)-Shirai and Takahashi(2000, 2003)-Soshnikov(2000)
 𝐾が以下①－③を満たすとき行列式点過程が一意に存在する．
① 𝐾 𝑥, 𝑦 = 𝐾(𝑦, 𝑥).
② 𝒦は局所トレイス・クラス
i.e. Λ ⊂ 𝑆 コンパクトに対し, 𝒦Λ 𝑓 ≔ ‫׬‬Λ 𝐾 𝑥, 𝑦 𝑓 𝑦 𝑚(𝑑𝑦)はトレイス・クラス.
③ 𝑂 ≤ 𝒦 ≤ 𝐼.
*特に，①+②を満たす(𝐾, 𝑚)に対し，③は行列式点過程の存在の必要十分条件．
*①－③の条件は，𝒦 （または 𝐾）のpositive contraction propertyともよぶ．

行列式点過程の構成定理：例① 𝐾 𝑥, 𝑦 = 𝐾(𝑦, 𝑥)② 𝒦は局所トレイス・クラス．③ 𝑂 ≤ 𝒦 ≤ 𝐼.

ランダム行列の固有値分布：

𝑁−1𝐾 𝑁 𝑥, 𝑦 = ෍ 𝜑𝑛 𝑥 𝜑𝑛 𝑦 .

一様全域木：

𝑛=0

行列式点過程の例：直交多項式

Gaussian unitary ensembleの固有値分布
 𝑋𝑖,𝑗 , 𝑌𝑖,𝑗 ~𝒩ℝ 0,1 , 𝑖 ≤ 𝑗, 𝑖, 𝑗 = 1, … , 𝑁： i.i.d.

ℝ
𝜆1𝑋𝑖,𝑗 + 𝑖𝑌𝑖,𝑗 , 𝑖 < 𝑗𝑖 = 𝑗.
 𝐻𝑁 = 𝐻𝑖,𝑗s. t. 𝐻𝑖,𝑗 = ൞𝑋𝑖,𝑖 ,𝑖,𝑗=1,…𝑁
𝑋𝑖,𝑗 − 𝑖𝑌𝑖,𝑗 , 𝑗 < 𝑖 固有値分布はℝ上の行列式点過程：
𝐾𝑁

𝜆2

𝜆3

𝜆4

𝑁−1𝑥, 𝑦 = ෍𝑛=0

Ψ𝑛 𝑥 Ψ𝑛 𝑦 ,Ψ𝑛 𝑥 = 𝐶𝑛 ℎ𝑛 𝑥 𝑒
ここで，ℎ𝑛 ：Hermit多項式，𝐶𝑛 ：正規化定数．

−𝑥22.にょろん - 投稿者自身による作品, CC 表示-継承 3.0, https://commons.wikimedia.org/w/index.php?curid=24989408による

Monte Carlo法と行列式点過程
Monte Carlo with determinantal point processes,
R Bardenet, A Hardy - The Annals of Applied Probability, 2020.
𝑁 適切なサンプリング 𝑥𝑖 𝑁
𝑖=1 と重み 𝑤𝑖 𝑖=1 を与えて𝑓の積分値を求めたい：𝑁‫ ≈ 𝑥𝑑 𝜇 𝑥 𝑓 ׬‬෍

𝑤𝑖 𝑓 𝑥𝑖 .

𝑖=1Cf. ガウス求積（𝑓: 𝐼 = −1,1 上の多項式に対する数値積分公式）
 [BH2020]核関数がNevai-classの多変量直交多項式で与えられるDPP𝒳,−1,1 𝑑 上のコンパクト台を持つ𝐶 1 -級関数𝑓に対して誤差
𝑁ℰ𝑁 𝑓 = ෍𝑤𝑖 𝑓 𝑥𝑖 − ‫𝑥𝑑 𝜇 𝑥 𝑓 ׬‬.

𝑖=1𝕍 ℰ𝑁 𝑓 ~𝒪 𝑁

DPPのsmall variance性と思える．

典型的には𝒪 𝑁 −2− 1+1/2𝑑1

引用：
Rémi Bardenet. Adrien Hardy. "Monte Carlo with determinantal point processes." Ann. Appl. Probab. 30 (1) 368 - 417, February 2020.

Monte Carlo法と行列式点過程：コストと精度のトレードオフ
 MC with DPPは近似精度がいい．

 一般にサンプリングコストは𝑁 3 のオーダー．

 問題意識：近似精度とサンプリングコストのトレードオフは可能か？
 昨年度の提案：
1. 行列式点過程の離散近似（離散DPPのサンプルコストを下げる研究が多々ある）

例えば， Dereziński, M., Calandriello, D., & Valko, M. (2019). Exact sampling of determinantal point
processes with sublinear time preprocessing. arXiv preprint arXiv:1905.13476.

2. カップリングによるポアソン点過程と行列式点過程の補完（長田＆森，2021+）
引用：
Rémi Bardenet. Adrien Hardy. "Monte Carlo with determinantal point processes." Ann. Appl. Probab. 30 (1) 368 - 417, February 2020.

𝐿2 空間の間の等長変換と行列式点過程の離散近似
𝐿2 空間の等長変換を与えると，行列式点過程も変形する．
目的に応じて適切な行列式点過程のクラスを選択することで，より良いサンプリングやモデリングが期待できるだろう．

行列式点過程（反発力）

Poisson点過程（無相関）

𝐿2 空間の間の等長変換と行列式点過程の離散近似ℓ∈ℕ ：𝑆の分割の単調増大列で，各点を分離する．
ℓℓ{𝜙𝐷,𝑘𝑥 } 𝐷,𝑘 ∈Δ ℓ ×ℕ0 ：𝜙𝐷,0が𝐷 ∈ Δ(ℓ)上の定義関数となる𝐿2 (𝑆, 𝑚)上のHaarウェーブレット.

Δ ℓ・・・

ℓ
𝜙𝐷×0ℓ
𝜙𝐷×1ℓ
𝜙𝐷×2・・・

𝐿2 空間の間の等長変換と行列式点過程の離散近似(𝑆, 𝑚) ：連続空間，ラドン測度𝑚を備える．
Δ ℓ ℓ∈ℕ ：𝑆の分割の単調増大列で，各点を分離する．
ℓℓ{𝜙𝐷,𝑘𝑥 } 𝐷,𝑘 ∈Δ ℓ ×ℕ0 ：𝜙𝐷,0が𝐷 ∈ Δ(ℓ)上の定義関数となる𝐿2 (𝑆, 𝑚)上のHaarウェーブレット.

ℓ𝑈 ℓ : 𝜙𝐷,𝑘↦ 𝛿𝐷,𝑘 は 𝐿2 𝑆, 𝑚 → 𝑙 2 (Δ ℓ × ℕ0 ) への等長変換．

(𝐾, 𝑚)-行列式点過程ℙ𝐾 に対し，𝕂ℓ ≔ 𝑈𝐾𝑈 −1 .
構成定理よりΔ ℓ × ℕ0 上の 𝕂ℓ -行列式点過程ℙ𝐾,ℓ は存在する．核関数は𝕂ℓ 𝑖, 𝑗 = න 𝜙𝑖ℓ 𝑥 𝐾 𝑥, 𝑦 𝜙𝑗ℓ 𝑦 𝑚 𝑑𝑥 𝑚 𝑑𝑦 ,𝑆×𝑆

このとき，ℙ𝐾 #𝐷 = 𝑛 = ℙ𝐾,ℓ #𝐷×ℕ0 = 𝑛 , 𝐷 ∈ 𝛥 ℓ , 𝑛 ∈ ℕ.

𝑖, 𝑗 ∈ Δ ℓ × ℕ0 .

𝐿2 空間の間の等長変換と行列式点過程の離散近似
Δ ℓℓ∈ℕ ：𝑆の分割の単調増大列．

ℓ{𝜙𝐷,𝑘𝑥 } 𝐷,𝑘 ∈Δ ℓ ×ℕ0 ：Haarウェーブレット.（右図）(𝐾, 𝑚)-行列式点過程ℙ𝐾 に対し，

Δ ℓ × ℕ0 上の 𝕂ℓ -行列式点過程ℙ𝐾,ℓ を次で定める：
𝕂ℓ 𝑖, 𝑗 = න

𝜙𝑖ℓ 𝑥 𝐾 𝑥, 𝑦 𝜙𝑗ℓ 𝑦 𝑚 𝑑𝑥 𝑚 𝑑𝑦 ,𝑆×𝑆
このとき，ℙ𝐾 #𝐷 =𝑛𝑖, 𝑗 ∈ Δ ℓ × ℕ0 .

= ℙ𝐾,ℓ #𝐷×ℕ0 = 𝑛 , 𝐷 ∈ 𝛥 ℓ , 𝑛 ∈ ℕ.

ℙ𝐾,ℓ はℙ𝐾 のTree representationと呼ばれる．

Tree representationは固有関数に依らない構成という意味でロバスト．
正規直行系を目的に応じて取り換えることで，線形統計量などのDPPの持つ特性を抽出できないか？

ご清聴ありがとうございました