引力・斥力を制御可能なランダム部分集合の確率分布

日本OR学会研究部会：最適化の理論とアルゴリズム（RAOTA） 第10回研究会のトーク資料です．

Transcript

1. 引力・斥力を制御可能なランダム部分集合の確率分布  川島 貴大（ZOZO 研究所） @ RAOTA 第 10 回研究会 @NII  June 15, 2025
2. はじめに：機械学習における多様性と同質性
3. ランダム部分集合 有限サイズの全体集合からのランダムな部分集合の生起の確率モデル  台集合 𝒴 ≔ {1, …, 𝑁} に対し，べき集合 2𝒴 上の確率分布 例：ユーザの購買行動 3 / 52
4. ランダム部分集合と実問題：確率的最適化 不均衡データから多様性のある ミニバッチサンプリング  精度向上  Zhang et al. (2017), Zhang et al. (2019) 4 / 52
5. ランダム部分集合と実問題：反実仮想説明 決定境界 ローン審査 ✖ ローン審査 現在の状態 年収100万円UP 年収50万円UP& 上場企業入社 より多様性の高いシナリオを列挙したい (Mothilal et al. (2020)) 5 / 52
6. 多様性の機械学習 多様性は ML 分野における重要なキーワードになりつつある Spotify の研究：多様な音楽を聴くユーザのほうが，有料会員への転換率 が高く，短期退会率も低い (Anderson et al. (2020)) 6 / 52
7. 多様性はいつでも正義か？ ML アルゴリズムにおいて，多様性と精度は基本的にトレードオフ  多様性が高いからといって，一様ランダムな推薦がよいわけではない バンディットやブラックボックス最適化のような文脈では：  探索と活用がアルゴリズムの根幹をなす  はじめは探索的に多様な選択肢を選び，後半はよさげな選択肢に集中 多様性と同質性を柔軟に制御することが重要！ 7 / 52
8. 今日のおはなし ランダム部分集合の確率モデルにおける多様性・同質性の話をします • 多様性・同質性の特徴づけ • 離散最適化との関係 • 多様性モデリングのための代表的な確率分布：行列式点過程 • 多様性・同質性を制御可能な確率モデル（川島の研究） 8 / 52
9. ランダム部分集合の多様性と同質性
10. ランダム部分集合と Positive/Negative Dependence ランダム部分集合の世界では，同質性を Positive Dependence， 多様性を Negative Dependence と呼ぶ  何らかの意味で「近い」アイテム同士に引力/斥力がはたらく 10 / 52
11. ランダム部分集合と Positive/Negative Dependence Positive/Negative Dependence は conceptual なもの  コンセンサスのとれた数学的定義があるわけではない ランダム部分集合に引力的/斥力的な性質を付与する色々な特徴づけを， Positive/Negative Dependence という枠組みでまとめているイメージ  P/N Association, P/N Correlation, P/N Lattice Condition, … これら特徴づけの理論にはあまり立ち入らない（数学的にかなり難） 11 / 52
12. Negative Dependence の難しさ とくに Negative Dependence を実現するのは，Positive Dependence よりも難しいことが知られている バイナリ確率変数：𝑥𝑖 ∈ {0, 1} （ランダム部分集合と等価） ∑ 𝑖,𝑗 Cov[𝑥𝑖 , 𝑥𝑗 ] = ∑ 𝑖,𝑗 𝔼[(𝑥𝑖 − 𝔼[𝑥𝑖 ])(𝑥𝑗 − 𝔼[𝑥𝑗 ])] = 𝔼[∑ 𝑖 (𝑥𝑖 − 𝔼[𝑥𝑖 ]) ∑ 𝑗 (𝑥𝑗 − 𝔼[𝑥𝑗 ])] = 𝔼 [ [ [(∑ 𝑖 (𝑥𝑖 − 𝔼[𝑥𝑖 ])) 2 ] ] ] ≥ 0 各項 Cov[𝑥𝑖 , 𝑥𝑗 ] は 負値をとりづらい 12 / 52
13. 集合関数としてのランダム部分集合の確率分布  • 台集合：𝒴 ≔ {1, …, 𝑁} • ランダム部分集合：𝒜 ⊆ 𝒴 (𝒜 ∈ 2𝒴) • ランダム部分集合の確率分布：𝑃 : 2𝒴 → [0, 1]  ランダム部分集合の確率分布は集合関数 連続型確率分布では，対数凹/凸性は重要な概念  では，ランダム部分集合の確率分布においては？ 対数凹分布： 正規分布，ラプラス分布，ガンベル分布，… 対数凸分布： パレート分布，ガンマ分布 (𝛼 < 1)，… 13 / 52
14. 優/劣モジュラ関数 集合関数の世界では，優モジュラ性が凹性のように， 劣モジュラ性が 凸性のようにそれぞれ振るまう  優モジュラ関数： 任意の 𝒜, ℬ ⊆ 𝒴 に対し 𝑓(𝒜 ∩ ℬ) + 𝑓(𝒜 ∪ ℬ) ≥ 𝑓(𝒜) + 𝑓(ℬ) 劣モジュラ関数： 任意の 𝒜, ℬ ⊆ 𝒴 に対し 𝑓(𝒜 ∩ ℬ) + 𝑓(𝒜 ∪ ℬ) ≤ 𝑓(𝒜) + 𝑓(ℬ) モジュラ関数： 優モジュラかつ劣モジュラな集合関数 14 / 52
15. 対数優/劣モジュラ性と Positive/Negative Dependence  優モジュラ性： 𝑓(𝒜 ∩ ℬ) + 𝑓(𝒜 ∪ ℬ) ≥ 𝑓(𝒜) + 𝑓(ℬ) 劣モジュラ性： 𝑓(𝒜 ∩ ℬ) + 𝑓(𝒜 ∪ ℬ) ≤ 𝑓(𝒜) + 𝑓(ℬ) 実は確率関数 𝑃 の引力/斥力は対数優/劣モジュラ性で特徴づけ可能  対数優/劣モジュラ性：𝑃(𝒜 ∩ ℬ)𝑃(𝒜 ∪ ℬ) ⋛ 𝑃(𝒜)𝑃(ℬ) つまり，集合関数 𝑓 が劣モジュラ関数であるとき， • 𝑃𝑓 (𝒜) ≔ exp(𝑓(𝒜))/𝑍：斥力的 • 𝑃𝑓 (𝒜) ≔ exp(−𝑓(𝒜))/𝑍：引力的 15 / 52
16. 対数優/劣モジュラ性と Positive/Negative Dependence  対数優モジュラ性： 𝑃(𝒜 ∩ ℬ)𝑃(𝒜 ∪ ℬ) ≥ 𝑃(𝒜)𝑃(ℬ) 対数劣モジュラ性： 𝑃(𝒜 ∩ ℬ)𝑃(𝒜 ∪ ℬ) ≤ 𝑃(𝒜)𝑃(ℬ) 例：𝑃 が対数劣モジュラなとき，𝒜 = {𝑖}, ℬ = {𝑗} (𝑖 ≠ 𝑗) に対し 𝑃({𝑖, 𝑗})𝑃(∅) ≤ 𝑃({𝑖})𝑃({𝑗}) 𝐶 ≔ 1/𝑃(∅) = const. とすると 𝑃({𝑖, 𝑗}) ≤ 𝐶𝑃({𝑖})𝑃({𝑗})  𝑖, 𝑗 の共起確率が単体の生起確率の積の定数倍以下（斥力！） 16 / 52
17. Negative Dependence としての対数劣モジュラ性 Negative Dependence の特徴づけの中では，対数劣モ性は最も弱い条件 Borcea et al. (2009) より引用 一方，対数優モ性は Positive Dependence と しては割と強い条件 (FKG 不等式）  「Negative Dependence の難しさ」 ただしモデリングの観点からは扱いやすい  応用上は対数優モ/劣モ性が使われがち NLC = 対数劣モ性 17 / 52
18. 代表的な斥力の確率モデル：行列式点過程
19. 行列式点過程 斥力的なランダム部分集合の確率モデルとして，もっともよく研究されて いるのが行列式点過程 (Determinantal Point Process, DPP)  行列式点過程 𝑃(𝒜; 𝑳) ≔ det 𝑳[𝒜] det(𝑳 + 𝑰) ∝ det 𝑳[𝒜] 𝑳：𝑁 × 𝑁 （半）正定 値行列 𝑳[𝒜]：𝑳の主部分行列 集合関数 𝒜 ↦ log det 𝑳[𝒜] は劣モジュラ  行列式点過程は対数劣モジュラ（斥力的）な確率モデル！ 𝒜 内の要素に対応する行・列を抽出 19 / 52
20. 行列式点過程：名前に関する補足 ランダム部分集合の確率分布である行列式点過程が「点過程」の名を冠す ことに違和感がある人もいるかも？ 歴史的には，一般にサイズ無限の台集合から加算個の点の集合を取り出す モデルとして提案された (Macchi (1975)) その後，台集合が有限のときに限り，確率関数が 𝑃(𝒜; 𝑳) = det 𝑳[𝒜] det(𝑳 + 𝑰) という閉形式で書けることが示された (Borodin and Rains (2005)) 20 / 52
21. 行列式点過程と斥力 Negative Dependence  何らかの意味で「近い」アイテム同士に斥力がはたらく パラメータ 𝑳 の 𝑖, 𝑗 成分 𝐿𝑖𝑗 がアイテム 𝑖, 𝑗 間の類似度を表現！  カーネル法（カーネル行列）と同じイメージ  行列式点過程 𝑃(𝒜; 𝑳) ≔ det 𝑳[𝒜] det(𝑳 + 𝑰) ∝ det 𝑳[𝒜] 21 / 52
22. 行列式点過程と斥力：幾何学的解釈 適当な 𝑽 ∈ ℝ𝑁×𝐷 で 𝑳 = 𝑽 𝑽 ⊤ と分解可能  𝐿𝑖𝑗 = ⟨𝒗𝑖 , 𝒗𝑗 ⟩ は 𝑖, 𝑗 番目の特徴ベクトル 𝒗𝑖 , 𝒗𝑗 の内積（類似度） 𝑃(𝒜; 𝑳) ∝ det 𝑳[𝒜] = Vol({𝒗𝑖 : 𝑖 ∈ 𝒜})2 なので  𝒗𝑖 , 𝒗𝑗 の内積が大きいほど 𝑖, 𝑗 は共起しやすい（斥力！） 22 / 52
23. 対数劣モジュラモデルのモード探索 行列式点過程 𝑃(𝒜; 𝑳) ∝ det 𝑳[𝒜] は対数劣モジュラ  モード探索問題 argmax𝒜⊆𝒴 log det 𝑳[𝒜] は劣モジュラ最大化問題！  劣モジュラ最大化問題 劣モジュラ関数 𝑓 : 2𝒴 → ℝ を最大化する 𝒜 ⊆ 𝒴 を求める問題． 一般に NP 困難だが，近似的に解ける場合が多くある 𝑓 が非負・単調なら，単純貪欲法で 1 − 1/𝑒 > 0.63 近似解を得る （単調性）𝒜 ⊆ ℬ ⇒ 𝑓(𝒜) ≤ 𝑓(ℬ) 23 / 52
24. 行列式点過程のモード探索 log 𝑃(𝒜; 𝑳) = log det(𝑳[𝒜]) + const. は一般に単調な劣モ関数でない   カーネル行列 𝑳 の固有値がすべて 1 以上なら単調 Buchbinder et al. (2012)：非単調な劣モ関数を貪欲法的に最大化！ 非負・非単調な劣モジュラ関数に対して， • 決定論的アルゴリズム：1/3 近似解 • 確率的アルゴリズム：1/2 近似解（期待値の意味で） 実用上は，非負性が保証されなくともよい近似解が得られる  24 / 52
25. 行列式点過程と Buchbinder の二重貪欲法 Buchbinder のアルゴリズムは単純貪欲法とは異なり， • 𝒮 = ∅ から要素を追加していく集合 • 𝒯 = 𝒴 から要素を削除していく集合 の 2 つを同時に更新していく（二重貪欲法）  det 𝑳[𝒯] の評価コスト高（𝑛 × 𝑛 行列の det 評価は𝒪(𝑛3)） 現状これが最良なので，研究チャンス！ ？ 25 / 52
26. 行列式点過程：モード探索の実行例 問題設定 20 × 20 の 2 次元グリッドの点が各アイテム  台集合 𝒴 のサイズは 𝑁 = 400 カーネル行列 𝑳 はガウシアンカーネルから構成  𝐿𝑖𝑗 = exp(−‖𝒙𝑖 − 𝒙𝑗 ‖2 /2) 5 10 15 20 5 10 15 20 20 × 20 のグリッド 𝒙𝑖 ：𝑖 番目の格子点の座標ベクトル 26 / 52
27. 行列式点過程：モード探索の実行例 5 10 15 20 5 10 15 20 5 10 15 20 5 10 15 20 5 10 15 20 5 10 15 20  多様な点が選ばれている  選ばれるアイテム数がまちまちで，使いにくい？  27 / 52
28. 𝑘-DPPs ランダム部分集合のサイズを 𝑘 に制限した行列式点過程 (DPP)  k-DPP (Kulesza and Taskar (2011))  𝑘-DPP 𝑃(𝒜 | |𝒜| = 𝑘; 𝑳) ≔ det 𝑳[𝒜] 𝑍𝑘 (𝑳) 𝑍𝑘 (𝑳)は正規化定数： 𝑍𝑘 (𝑳) ≔ ∑ 𝒜⊆𝒴 |𝒜|=𝑘 det 𝑳[𝒜] もとの DPP との関係： 𝑃(𝒜 | 𝑳) = ∑ 𝑁 𝑘=1 𝑃(𝒜 | |𝒜| = 𝑘; 𝑳) 𝑃(|𝒜| = 𝑘) DPP 𝑘-DPP 28 / 52
29. 𝑘-DPP の正規化定数  𝑘-DPP の正規化定数 𝑍𝑘 (𝑳) は，𝑳 の固有値 𝜆1 , …, 𝜆𝑁 を用いて 𝑍𝑘 (𝑳) = 𝑒𝑘 (𝜆1 , …, 𝜆𝑁 ). と書ける．𝑒𝑘 (𝜆1 , …, 𝜆𝑁 ) は 𝑘 次の 𝑁 変数基本対称多項式 𝑁 = 3 のとき： 𝑒1 (𝜆1 , 𝜆2 , 𝜆3 ) = 𝜆1 + 𝜆2 + 𝜆3 𝑒2 (𝜆1 , 𝜆2 , 𝜆3 ) = 𝜆1 𝜆2 + 𝜆1 𝜆3 + 𝜆2 𝜆3 𝑒3 (𝜆1 , 𝜆2 , 𝜆3 ) = 𝜆1 𝜆2 𝜆3 𝜆1 , …, 𝜆𝑁 を求めた後， 𝒪(𝑁𝑘) で計算可能！ 29 / 52
30. 𝑘-DPP のモード探索 𝑘-DPP のモード探索は，サイズ制約つき非単調劣モジュラ最大化問題  Buchbinder et al. (2014) の近似保証付きアルゴリズムが使える！ 𝑘 = 50 でのモード探索の実行例： 5 10 15 20 5 10 15 20 5 10 15 20 5 10 15 20 5 10 15 20 5 10 15 20 30 / 52
31. DPP の最尤推定 DPP の最尤推定問題：部分集合列 𝒜1 , …, 𝒜𝑀 が与えられたとき， ℓ(𝑳) ≔ − 1 𝑀 ∑ 𝑀 𝑚=1 log det 𝑳[𝒜𝑚 ] + log det (𝑳 + 𝑰) 凹関数 凹関数 を（半）正定値行列 𝑳 について最小化  DC（半）正定値計画問題！ フルランク & 構造なしの 𝑳 に対しては，現状 Kawashima and Hino (2023) の MM アルゴリズムによる方法が最速  𝑳(𝑳(𝑡) + 𝑰)−1 𝑳 + 𝑸(𝑡) = 𝑶 なる形式の行列二次方程式を繰返し解く 31 / 52
32. ほかの斥力的な確率モデル：FLID FLID（Facility Location Diversity） (Tschiatschek et al. (2016))  施設配置関数 (Facility Location Function) を用いた確率モデル 𝑃(𝒜 | 𝒖, 𝑾) ≔ exp(∑ 𝑖∈𝒜 𝑢𝑖 + ∑𝐷 𝑑=1 (max𝑖∈𝒜 𝑊𝑖,𝑑 − ∑ 𝑖∈𝒜 𝑊𝑖,𝑑 )) 𝑍  施設配置関数 𝑓FC (𝒜) ≔ ∑ 𝐷 𝑑=1 max 𝑖∈𝒜 𝑊𝑖,𝑑 (𝑊𝑖,𝑑 ≥ 0) 𝑢𝑖 ：アイテム 𝑖 のバイアス 𝑊𝑖,𝑑 ：アイテム 𝑖 の埋め込み の次元 𝑑 での値 𝑍：正規化定数 32 / 52
33. 引力と斥力を制御可能な確率モデル
34. 行列式点過程の一般化 行列式点過程は強い斥力を表現できる確率モデル  斥力（多様性）はいつでも正義か？ （cf. 探索と活用）  引力や斥力，その強さを制御できる一般化を考えられないか？ α-DPP (Vere-Jones (1997)) 行列式の定義を一般化した 𝛼-permanent： per𝛼 𝐴 ≔ ∑ 𝜎∈𝑆𝑛 𝛼𝜈(𝜎) ∏ 𝑛 𝑖=1 𝑎𝑖,𝜎(𝑖) から定義 𝜈(𝜎)：置換した回数 𝛼 = −1 で行列式 𝛼 = 1 で permanent 34 / 52
35. 行列式点過程の一般化：𝛼-DPP DPP は統計物理を背景にもつモデル  フェルミオンの振るまいを表現 𝛼-DPP は 𝛼 = 1 でボソンの引力的振る まいも表現できる  𝛼-permanent per𝛼 𝐴 ≔ ∑ 𝜎∈𝑆𝑛 𝛼𝜈(𝜎) ∏ 𝑛 𝑖=1 𝑎𝑖,𝜎(𝑖) しかし 𝛼-permanent は 𝛼 = 1 のときですら少なくとも一般には #P 完全  物理的・数学的には興味深いが，工学的には扱いづらいモデル  工学的にも扱いやすい DPP に一般化を考えたい！ 35 / 52
36. 行列式点過程の一般化 ランダム部分集合の確率モデルで引力・斥力を制御するには， 𝑃𝑓 (𝒜) = exp( 𝑓(𝒜) )/𝑍 の集合関数 𝑓 を優モジュラ/劣モジュラにすればよかった 行列式点過程の確率関数は 𝑃(𝒜; 𝑳) = det 𝑳[𝒜] det(𝑳 + 𝑰) ∝ exp( log det 𝑳[𝒜] ) だった  𝒜 ↦ log det 𝑳[𝒜] を，優モ/劣モ性を切り替えられる形で一般化する 36 / 52
37. log det 𝑳[𝓐] の一般化 一般に正定値行列 𝑿 に対して log det 𝑿 = tr log 𝑿  右辺の行列対数を一般化してみる！  行列式点過程 𝑃(𝒜; 𝑳) ∝ exp(log det 𝑳[𝒜]) = exp(tr log 𝑳[𝒜]) （半）正定値行列 𝑿 = 𝑼𝚲𝑼⊤ と一変数関数 𝜑 に対して 以下を定義： 𝜑(𝑿) ≔ 𝑼𝜑(𝚲)𝑼⊤ = 𝑼 ( ( ( ( ( ( ( 𝜑(𝜆1 ) 0 ⋮ 0 0 𝜑(𝜆2 ) ⋮ 0 … … ⋱ … 0 0 ⋮ 𝜑(𝜆𝑁 )) ) ) ) ) ) ) 𝑼⊤ 37 / 52
38. 離散カーネル点過程 (DKPP) DPP の tr log を一般化したのが離散カーネル点過程 (Discrete Kernel Point Process, DKPP) (Kawashima and Hino (2025))  離散カーネル点過程 (DKPP) 連続な一変数関数 𝜑 とパラメータ（カーネル行列）𝑳 に対して， DKPP の確率関数を 𝑃𝜑 (𝒜; 𝑳) ≔ exp(tr 𝜑(𝑳[𝒜])) 𝑍 = exp(tr 𝜑(𝑳[𝒜])) ∑ 𝒜⊆𝒴 exp(tr 𝜑(𝑳[𝒜])) と定義 38 / 52
39. DKPP が含む確率モデル 𝜑 = log のとき DKPP は DPP ほかの場合は？  DKPP 𝑃𝜑 (𝒜; 𝑳) ∝ exp(tr 𝜑(𝑳[𝒜])) 𝜑 が 1 次関数 𝑏𝑥 + 𝑐 ⇒ DKPP は 𝑁 回の独立なコイン投げ  𝑖 回目で表になる確率は 𝜎(𝑏𝐿𝑖𝑖 + 𝑐) 𝜑 が 2 次関数 ⇒ DKPP はボルツマンマシン（の特殊ケース）  𝑧𝑖 ∈ {0, 1} に対して 𝑃(𝒛 | 𝒉, 𝑾) ∝ exp(∑ 𝑖 ℎ𝑖 𝑧𝑖 + ∑ 𝑖<𝑗 𝑊𝑖𝑗 𝑧𝑖 𝑧𝑗 ) 39 / 52
40. DKPP が含む確率モデル 𝜑 = log のとき DKPP は DPP ほかの場合は？  DKPP 𝑃𝜑 (𝒜; 𝑳) ∝ exp(tr 𝜑(𝑳[𝒜])) 独立 DPP ボルツマン マシン DKPP 39 / 52
41. DKPP の引力・斥力 集合関数 𝒜 ↦ tr 𝜑(𝑳[𝒜]) が優モ/劣モになるための関数 𝜑 の形は？  DKPP 𝑃𝜑 (𝒜; 𝑳) ∝ exp(tr 𝜑(𝑳[𝒜])) が引力的/斥力的になる条件 Friedland and Gaubert (2013) 𝜑′ が作用素単調増加であるとき，𝒜 ↦ tr 𝜑(𝑳[𝒜]) は優モジュラ関数  作用素単調増加性 𝜓 が任意の 𝑛 ∈ ℕ と 𝑨 ⪯ 𝑩 である任意の 𝑛 次元エルミート行列 𝑨, 𝑩 に対して 𝜓(𝑨) ⪯ 𝜓(𝑩) を満たすとき，𝜓 は作用素単調増加 40 / 52
42. DKPP の引力・斥力 集合関数 𝒜 ↦ tr 𝜑(𝑳[𝒜]) が優モ/劣モになるための関数 𝜑 の形は？  DKPP 𝑃𝜑 (𝒜; 𝑳) ∝ exp(tr 𝜑(𝑳[𝒜])) が引力的/斥力的になる条件 Friedland and Gaubert (2013) 𝜑′ が作用素単調減少であるとき，𝒜 ↦ tr 𝜑(𝑳[𝒜]) は劣モジュラ関数  作用素単調減少性 𝜓 が任意の 𝑛 ∈ ℕ と 𝑨 ⪯ 𝑩 である任意の 𝑛 次元エルミート行列 𝑨, 𝑩 に対して 𝜓(𝑨) ⪰ 𝜓(𝑩) を満たすとき，𝜓 は作用素単調減少 40 / 52
43. 作用素単調関数  作用素単調性 𝜓 が任意の 𝑛 ∈ ℕ と 𝑨 ⪯ 𝑩 である任意の 𝑛 次元エルミート行列 𝑨, 𝑩 に対して 𝜓(𝑨) ⪯ 𝜓(𝑩) を満たすとき，𝜓 は作用素単調増加 𝜓(𝑨) ⪰ 𝜓(𝑩) を満たすとき，𝜓 は作用素単調減少 • 𝜑(𝑥) = 𝑥𝑝：導関数 𝜑′ は 0 < 𝑝 ≤ 1 で作用素単調減少， 1 ≤ 𝑝 ≤ 2 で作用素単調増加 • 𝜑(𝑥) = log 𝑥：導関数 𝜑′ は作用素単調減少（DPP に対応） • 𝜑(𝑥) = 𝑥 log 𝑥：導関数 𝜑′ は作用素単調増加 41 / 52
44. Box–Cox 変換による DKPP の parametrization 引力・斥力を制御しやすい DKPP の 𝜑 の parameterization として， Box–Cox 変換の定数 (𝛽 > 0) 倍を採用： 𝜑𝛽,𝜆 (𝑥) ≔ { 𝛽 log 𝑥 if 𝜆 = 0 𝛽(𝑥𝜆−1) 𝜆 otherwise  𝜆 ∈ [0, 1] で斥力的，𝜆 ∈ [1, 2] で 引力的  𝜆 = 0 で DPP，𝜆 = 1 でコイン投げ， 𝜆 = 2 でボルツマンマシン Box–Cox 変換 42 / 52
45. DKPP による引力・斥力の制御 アイテム数 |𝒜| = 25 の 2 種の“実現値”に対する（条件付）確率値を評価  引力・斥力が制御できている！  条件付き確率𝑃𝜑𝛽,𝜆 (𝒜 | |𝒜| = 25; 𝑳) と 𝜆 の関係 𝜆 = 1 で出やすさ逆転！ 43 / 52
46. 引力的・斥力的 DKPP からのサンプリング例 20 × 20 のグリッドから 𝑛 = 25 個のアイテムをサンプリングする例  MCMC (random walk Metropolis) によるサンプリング • 引力的な設定 (𝛽 = 10, 𝜆 = 1.5)  アニメーション（リンク） • 斥力的な設定 (𝛽 = 10, 𝜆 = 0.1)  アニメーション（リンク） 44 / 52
47. MNIST からのデータ取得 ガウシアンカーネルによる 𝑳 を用いて |𝒜| = 5 の部分集合を取得 𝜆 ∈ [0, 2] を動かし， 部分集合内に いくつのクラス数があるかを評価 同じ 𝑳 による Kernel PCA 𝛽 = 10, 50 で引力/斥力の効果あり 45 / 52
48. MNIST からのデータ取得：部分集合の例 (𝛽 = 10) 𝜆 = 2, 𝛽 = 10 （引力） 𝜆 = 1, 𝛽 = 10 （独立） 𝜆 = 0, 𝛽 = 10 （斥力）  定性的にも引力・斥力の制御の効果がわかる  46 / 52
49. DKPP のパラメータ推定 DKPP のカーネル行列 𝑳 を部分集合列 𝒜1 , …, 𝒜𝑀 から推定  正規化定数が計算できないことが問題 Ratio Matching (Hyvärinen (2007))：非正規化離散モデルのための損失 𝐽(𝑳) ≔ 1 𝑀 ∑ 𝑀 𝑚=1 ∑ 𝑁 𝑛=1 𝑔(exp(tr 𝜑(𝑳[𝒜𝑚 ])) − exp(tr 𝜑(𝑳[𝒜𝑛 𝑚 ]))), 𝑔(𝑥) ≔ 1 1 + 𝑥 , 𝒜𝑛 ≔ { 𝒜 \ {𝑛} if 𝑛 ∈ 𝒜 𝒜 ∪ {𝑛} if 𝑛 ∉ 𝒜  SGD（ミニバッチ化）に対応！ Bregman ダイバージェンスとの関係：Gutmann and Hirayama (2012) 47 / 52
50. おわりに
51. まとめ ランダム部分集合の確率モデリング • 引力（同質性，Pos.Dep.）と斥力（多様性，Neg.Dep.） • 行列式点過程 (DPP)：代表的な斥力モデル  モード探索と劣モジュラ最大化  k-DPP：サイズ制約つき DPP • 離散カーネル点過程 (DKPP)：DPP の一般化  一変数関数 𝜑 の設計で引力・斥力を制御可能  Box–Cox 変換による 𝜑 の parameterization 49 / 52
52. 話せなかったこと 離散最適化との関連に軸足をおいた関係上，触れられなかった話題も多々 • DPP, DKPP のパラメータ推定の詳細  （半）正定値計画問題の対象として面白い（はず） • 確率的な諸問題  DPP の周辺確率表現（𝑲 カーネルによる表現）  DPP からのサンプリング法  DKPP の正規化定数・周辺確率・条件付き確率の推定 50 / 52
53. 参考文献
54. Anderson, A., Maystre, L., Anderson, I., Mehrotra, R., and Lalmas, M. (2020). Algorithmic Effects on the Diversity of Consumption on Spotify., in Proceedings of The Web Conference 2020, (ACM), 2155–2165. Borcea, J., Brändén, P., and Liggett, T. M. (2009). Negative Dependence and the Geometry of Polynomials. Journal of the American Mathematical Society 22, 521–567. Borodin, A., and Rains, E. M. (2005). Eynard–Mehta Theorem, Schur Process, and Their Pfaffian Analogs. Journal of Statistical Physics 121, 291–317. Buchbinder, N., Feldman, M., Naor, J., and Schwartz, R. (2012). A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization., in 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 649–658.
55. Buchbinder, N., Feldman, M., Naor, J., and Schwartz, R. (2014). Submodular Maximization with Cardinality Constraints., in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, (Society for Industrial and Applied Mathematics), 1433–1452. Friedland, S., and Gaubert, S. (2013). Submodular Spectral Functions of Principal Submatrices of a Hermitian Matrix, Extensions and Applications. Linear Algebra and its Applications 438, 3872–3884. Gutmann, M., and Hirayama, J.-i. (2012). Bregman Divergence as General Framework to Estimate Unnormalized Statistical Models. Hyvärinen, A. (2007). Some Extensions of Score Matching. Computational Statistics & Data Analysis 51, 2499–2512. Kawashima, T., and Hino, H. (2023). Minorization-Maximization for Learning Determinantal Point Processes. Transactions on Machine Learning Research.
56. Kawashima, T., and Hino, H. (2025). A Family of Distributions of Random Subsets for Controlling Positive and Negative Dependence., in Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, (PMLR), 64–72. Kulesza, A., and Taskar, B. (2011). K-Dpps: Fixed-Size Determinantal Point Processes., in International Conference on Machine Learning. Macchi, O. (1975). The Coincidence Approach to Stochastic Point Processes. Advances in Applied Probability 7, 83–122. Mothilal, R. K., Sharma, A., and Tan, C. (2020). Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations., in Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, (Association for Computing Machinery), 607–617.
57. Tschiatschek, S., Djolonga, J., and Krause, A. (2016). Learning Probabilistic Submodular Diversity Models Via Noise Contrastive Estimation., in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, (PMLR), 770–779. Vere-Jones, D. (1997). Alpha-Permanents and Their Applications to Multivariate Gamma, Negative Binomial and Ordinary Binomial Distributions. New Zealand J. Math 26, 125–149. Zhang, C., Kjellström, H., and Mandt, S. (2017). Balanced Mini-batch Sampling for SGD Using Determinantal Point Processes., in Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017, (AUAI Press). Zhang, C., Öztireli, C., Mandt, S., and Salvi, G. (2019). Active Mini-Batch Sampling Using Repulsive Point Processes., in Proceedings of the Thirty-Third AAAI
58. Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, (AAAI Press), 5741–5748.