Fair Clustering & Search 2

研究紹介 大阪大学大学院情報科学研究科 天方 大地

自己紹介 ◼ Name: Daichi Amagata（天方 大地） ◼ Job: Assistant Professor at Osaka University  BE: Osaka University  MSc: Osaka University（佐々木先生はsenior studentだった）  Ph.D. (information science) Osaka University（鬼塚先生は博士論文の副査担当） • DC1 ◼ Love:  Football (watching w-cup, EURO, and champions league)  Reading comics (>1800 e-comics ≫ #papers read ever) No. 1

研究テーマ：データベース，データマイニング，および機械学習のための高速アルゴリズム No. 2 問い合わせ • ここの計算をとにかく高速に！ 結果の出力 Google & Microsoft も自社内で精力的に開発 Meta は良さそうなアルゴリズムをFaiss lib. に導入 • 実際に動く & 理論的性能保証！

研究テーマ：データベース，データマイニング，および機械学習のための高速アルゴリズム 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない 探索 クラスタリング 要約 外れ値検出 No. 3

探索：条件に合致したデータを出力 No. 4 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 フィルタ 𝒀 に関わるデータにだけアクセスすることで高速化を実現

クラスタリング：𝑿をグループに分ける No. 5 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 分類 クラスタとはこうである，を定式化したとき， そのクラスタを出力するために必要な処理 のみを行うことにより高速化を実現

要約：𝑿 → 𝑿′ s.t. 𝑿′ ≪ 𝑿 No. 6 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 選択 ∗ 𝑆 = arg max𝑆⊆𝑋, 𝑆 =𝑘 𝒇 𝑺 ′ 𝑓 𝑆 = min 𝑑𝑖𝑠𝑡 𝑥, 𝑥 𝑥,𝑥 ′ ∈𝑆 要約とはこうである，を定式化し，その要約を出力するために 必要な処理のみを行うことにより高速化を実現

外れ値検出：条件に合致したデータを出力 No. 7 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 分類 外れ値とはこうである，を定式化したとき， 各データに対して 外れ値？ or not？ （← 探索） を高速に判定する仕組みを設計

研究テーマ：データベース，データマイニング，および機械学習のための高速アルゴリズム 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない 探索 クラスタリング 公平性の概念を組み込んだ定式化 要約 外れ値検出 No. 8

この分野における「公平性」ってなに？？？ 定義は沢山ありますが，私が扱う研究では （たぶん） 公平性 ≒ 平等 「探索」，「クラスタリング」，および「要約」における平等ってなに？？？ No. 9

この分野における「公平性」ってなに？？？ No. 10 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない 公平性 ≒ 平等 「探索」，「クラスタリング」，および「要約」における平等ってなに？？？

この分野における「公平性」ってなに？？？ No. 11 巨大な入力 要件を満たす集合 出力 𝑿 𝒁 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない 公平性 ≒ 平等 「探索」，「クラスタリング」，および「要約」における平等ってなに？？？

探索問題における「公平性」ってなに？？？ No. 12 巨大な入力 要件を満たす集合 出力 𝑿 𝒁 𝒀 = 𝑛 個のデータの集合 = 𝑚 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない ∀𝒙 ∈ 𝒁, 𝐏𝐫𝐨𝐛 𝒙 ∈ 𝒀 = 𝟏/ 𝒁 ：統計的に重要な条件 𝑍: 条件を満たす全てのデータ 𝑌: 𝑍からランダムサンプルされたデータ

公平な探索問題の何が難しい？？？ No. 13 巨大な入力 要件を満たす集合 出力 𝑿 𝒁 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない 𝑿 から 𝒁 を計算 = 𝑚 個のデータの集合 ランダムサンプリング → 𝑍 が大きい → 少なくとも大きい数のデータにアクセスする必要有 → 遅い（計算コスト大） 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない

公平な探索問題で何を達成した？ No. 14 内積探索問題 [1] 𝑥 | 𝑥 ∈ 𝑋, 𝑥 ⋅ 𝑞 ≥ 𝜏 から，ランダムな 𝑡 個のデータをサンプルする時間（期待値）：log 𝑛 + 𝑡 に比例 インターバル探索問題 [2] 𝑥 | 𝑥 ∈ 𝑋, 𝑥 ∩ 𝑞 ≠ ∅ から，ランダムな 𝑡 個のデータをサンプルする時間：log 2 𝑛 + 𝑡 に比例 空間ジョイン問題 (𝑥, 𝑦) | 𝑥, 𝑦 ∈ 𝑋 ⋈ 𝑌 から，ランダムな 𝑡 個のデータをサンプルする時間（期待値）：𝑛 + 𝑚 + 𝑡 にほぼ比例 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 [1] K. Aoyama et al., “Simpler is Much Faster: Fair and Independent Inner Product Search,” In SIGIR, 2023. [2] D. Amagata, “Independent Range Sampling on Interval Data,” In ICDE 2024.

研究テーマ：データベース，データマイニング，および機械学習のための高速アルゴリズム 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない 探索 クラスタリング 公平性の概念を組み込んだ定式化 要約 外れ値検出 No. 15

クラスタリングにおける「公平性」ってなに？？？ グループ公平性 個人公平性 各データの属性を考慮 類似したデータ → 類似した結果 No. 16

クラスタリングにおける「グループ公平性」ってなに？ グループ公平性 w/o over- & lower-representation 各データの属性を考慮 = "𝛼𝑗 ≤ 𝐶𝑖 ∩ 𝑃𝑗 ≤ 𝛽𝑗 " No. 17 → 各クラスタ𝐶𝑖 には属性𝑗のデータが𝛼𝑗 以上𝛽𝑗 以下属する． → あるクラスタが特定の属性に独占されないようにする． Matroid constraint = " 𝑆 ∩ 𝑃𝑗 = 𝑘𝑗 ∀𝑗 ∈ 1, 𝑚 , 𝑆 = 𝑘" → クラスタ中心には属性𝑗から𝑘𝑗 個選ばれる． → クラスタ中心が特定の属性に独占されないようにする． Social fairness Δ 𝐶,𝑃𝑖 𝑃𝑖 𝑚 = min max → 各属性に対して遠いクラスタセンタを抑制 → クラスタ中心が特定の属性に対して遠い，を防ぐ．

クラスタリングにおける「個人公平性」ってなに？？？ 定義 個人公平性 各データに対して、クラスタセンタが自身の 類似したデータ → 類似した結果 𝑛/𝑘-最近傍に含まれている． No. 18

公平なクラスタリングの何が難しい？ No. 19 𝑘-クラスタリング ：𝑆 ∗ = argmin 𝑓(𝑃, 𝑆) 𝑆 =𝑘 𝑆 はクラスタセンタの集合であり， 𝑆 ∗ の計算はNP困難（多項式時間では解が得られない） → 𝑺∗ っぽい解を高速に探したい w/o over- & lower-representation = "𝛼𝑗 ≤ 𝐶𝑖 ∩ 𝑃𝑗 ≤ 𝛽𝑗 " → 各クラスタ𝐶𝑖 には属性𝑗のデータが𝛼𝑗 以上𝛽𝑗 以下属する． → あるクラスタが特定の属性に独占されないようにする． Matroid constraint = " 𝑆 ∩ 𝑃𝑗 = 𝑘𝑗 ∀𝑗 ∈ 1, 𝑚 , 𝑆 = 𝑘" → クラスタ中心には属性𝑗から𝑘𝑗 個選ばれる． → クラスタ中心が特定の属性に独占されないようにする． Social fairness Δ 𝐶,𝑃𝑖 𝑃𝑖 𝑚 = min max → 各属性に対して遠いクラスタセンタを抑制 → クラスタ中心が特定の属性に対して遠い，を防ぐ．

公平なクラスタリング問題で何を達成した？ Fair k-center clustering with outliers [3] 𝑆 ∗ = argmin𝑆⊆𝑃∖𝑃𝑜𝑢𝑡 , 𝑆 =𝑘,∀𝑖∈ 1,𝑚 , 𝑆∩𝑃𝑖 ≤𝑘𝑖 No. 20 max 𝑑𝑖𝑠𝑡 𝑝, 𝑆 𝑝∈𝑃∖𝑃𝑜𝑢𝑡 There is an 𝑂(𝑛𝑘) time algorithm that needs 𝑂(𝑛) space and yields a (3 + 𝛾)-approximation result for the fair (𝑘, 1 + 𝜖 𝑧)-center clustering problem with probability at least 𝑧 1−𝑛 [3] D. Amagata, “Fair k-center Clustering with Outliers,” In AISTATS 2024. 𝜖 𝑘−1 , by returning exactly 𝑘 centers and removing at most 1+𝜖 1 + 𝜖 𝑧 points.

まとめ：この分野における「公平性」とは No. 21 巨大な入力 出力 𝑿 𝒀 = 𝑛 個のデータの集合 ～2010年代前半：𝑛 = million は大きい 2010年代後半～：𝑛 = billion も珍しくない 公平性 ≒ 平等 探索における公平性：解に入る確率が平等（同じ） クラスタリングにおける公平性：グループ公平性（属性が平等に扱われる）と個人公平性（似たデータがクラスタセンタ）

共同研究っぽい何かは絶賛大募集 No. 22 巨大な入力 公平な出力 𝑿 𝒀 = 𝑛 個のデータの集合 提供できます！ • データ処理関係で困ってることの解決 是非教えて下さい！ • 実はこんな公平性が求められています、的な話 • 〇〇な処理は不公平な結果を出しがち、的な話