Upgrade to Pro — share decks privately, control downloads, hide ads and more …

SIGIR2022 Paper (Optimizing generalized Gini in...

Toshihiro NAKAE
November 12, 2022
43

SIGIR2022 Paper (Optimizing generalized Gini indices for fairness in rankings)

Toshihiro NAKAE

November 12, 2022
Tweet

Transcript

  1. Optimizing generalized Gini indices for fairness in rankings IR Reading

    2022 秋 株式会社ビズリーチ 中江 俊博 2022-11-12
  2. 自己紹介 中江 俊博 (なかえ としひろ) 株式会社ビズリーチ リクルーティングプロダクト本部 プラットフォーム開発部 AI1グループ Mgr

    経歴 NTTデータ数理システム(-2018) データ分析コンサルタント TripleW(2018-2019) 排尿予測モデル実装 ビズリーチ (2019-現職) 推薦モデルなどの機械学習関連の 実装の統括担当 IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness 2
  3. 今回対象となる論文 Optimizing generalized Gini indices for fairness in rankings Virginie

    Do, Nicolas Usunier (Meta AI Research) SIGIR 2022 この論文のベースになる同一著者の論文が NeurIPS2021 で出ている Two-sided fairness in rankings via Lorenz dominance 要旨 レコメンドにおいてItemに対するpreferenceが与えられた状況で、 User側のutilityの和と、ItemのGini係数(の拡張 ; GGFs)の和が 最良になる fair なランキングの手法を提案。 前年の論文で、微分可能な関数による手法を提案していた。 今回の論文で、微分不可能な Gini係数を、微分可能な関数の手法に 帰着させることで解決を図る、という筋書。 IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 3
  4. 前提 User に Item を確率的にレコメンド ... User が Item にもつ価値

    ... User に対して Item が 番目にお薦めされる確率 ... User が 番目にお薦めの Item に接触する確率 (単調減少) User の utility : 価値の高いアイテムほど上位に出ていればutility大きい Item の exposure : アイテムが上位にレコメンドされる頻度が多いほどexposure大きい を Fix した状態で を動かし、 utility / exposure を増やすようにする問題と考える。 IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 4
  5. Lorenz efficiency Generalized Lorenz Curve utility を低いほうから累積和をとったもの(図はNeurIPS2021) 下に突き出ているほど不平等 青 :

    user utility の総和 max → itemが不平等 赤 : user も item もまだ上に持っていける余地がある。 Lorenz efficiency user/item いずれも curve を上側に改善できない状態 論文著者にとっての fairness の定義 IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 5
  6. Frank-Wolf アルゴリズムの適用 は確率行列(tensor)なので、 で和をとると1になる制約を満たす必要がある。 この場合、凸集合での微分可能な関数を最適化する手法である Frank-Wolfアルゴリズム が使える Step 1: Step

    2 : Step 3 : Step1 の argmax の見つけ方 微分 を計算 の User ごとの降順ソートに対応する 置換行列 が argmax を満たしている! 置換行列が確率行列(tensor)であることに注意。 IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 7
  7. GGFs 同じ手続きを item exposure の Gini 係数最小化に使えないか? これが SIGIR2022 論文の目標!

    Generalized Gini welfare Functions (GGFs) 非増加の重み列 をパラメータとする関数 次元の入力 について 昇順ソート を使って次のように定義される。 特に item exposure に対する gini 係数は、 GGFsを使った次の値を最大化することと(ほぼ)等価 IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 8
  8. GGFs と Lorenz efficiency 例えば次の関数を最大にするレコメンド は、 user utility / item

    gini 係数のバランスをとることができる。 GGFs の線形和の形となっている ( はパラメータ) 実は GGFs の線形和の形の関数を最大にするレコメンド は、 Lorenz efficiency を満たしている では、そのような をさっきと同じように微分で求めよう! 残念! GGFs は単純に微分できない (昇順ソートがあるから) IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 9
  9. GGFsの最適化 骨子 : Step1/2 の繰り返し (上下幅を縮めながら) Step1. 微分可能な関数で上下を挟み、挟んだ関数上で微分 Step2. 微分をつかって

    Frank-Wolf で を Update 上下を挟むなめらかな関数 (モーロー包 ; Moreau envelope) 微分不可能な関数 に対して 次の は比較的簡単な手続きで微分できる。 計算できた部分 を使って、GGFsの線形和全体の微分を算出 これをソートして、更新して... IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 10
  10. 数値実験 : 条件 対象データ : Lastfm-2k, MovieLens-20m を対象 user-item preference

    は行列分解から算出 ランクごとの接触重みは DCG を利用 比較手法 FairRec(*) : Userが順に1つずつとる(先取り)ドラフト会議方式 微分可能な関数による方法 welf : NeurIPS(2021)で提案された減衰関数 を使う。 eq. exposure (stf) : item exposure の分散を使う (Giniっぽい) GGF : 提案法 GGFについては、utility が小さい user に重みを付ける two-side fairness を考慮した計算も実施。 (*) Patro+(2020), FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms (WWW2020, arxiv/2002.10764) IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 11
  11. 数値実験結果 : Lastfm-2k 左 : user については utility の合計を max

    にする場合 右 : user については utility の小さい 25% に重みを付ける場合 いずれも user/item のバランス を変化させた結果をプロット GGF の パレート曲線 がいずれも左上に来ている (最適手法) IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 12
  12. まとめ user/item 両方の Lorenz 曲線が改善できない = fairである これを Lorenz efficiency

    という GGFs を使った user/item の fairness を考慮したランキングを提案 GGFs の和を最大にするランキングは Lorentz efficiency を満たす 本来微分不可能な関数である GGFs を、微分可能な関数で近似できる 近似した関数での微分を使って、Frank-Wolfで最適化できる GGFs を使ったランキングは従来手法より、 user utility /item exposure を改善 IR Reading 2022 秋 / Optimizing generalized Gini indices for fairness in rankings 13