$\newcommand{\1}{\mbox{1}\hspace{-0.25em}\mbox{l}}$
AAAI-22に採録された、AIの公平性に関する論文Online certification of preference-based fairness for personalized recommender systemsを読んだので内容を紹介したいと思います。LAMSADE（フランスの研究機関）とMeta AIの共著。
要約
- レコメンドアルゴリズムが公平に動作しているかを監査するフレームワークを提案。公平性の概念は様々にあるが、本論文では新しく「自分に対するレコメンドよりも好ましいレコメンドが他のユーザに対して行われていないか」（envy-freeness）という概念を導入
- 監査においては、通常のレコメンド結果の表示と、他ユーザへのレコメンド方針に基づいたレコメンド結果の表示のいずれかをおこない、その反応に基づいてenvy-freenessを確認する。これは、あるユーザに対するレコメンドよりも効用の高いレコメンド方針が与えられているユーザを探索する多腕バンディット問題とみなすことができる
- Last.fmとMovieLensのデータを用いて評価を実施。監査継続時間と監査コスト（監査をおこなうことで低下してしまうレコメンド効用）との関係が確認できた
所感
- 経済学方面から提案されたenvy-freenessの概念を機械学習に適用した事例としてとても面白かった。一方、レコメンドにおける公平性がenvy-freenessで十分かについては要議論ではあると思う
- 時短勤務の仕事を望む女性が男性より多かったとして、その状況が維持されるのが果たして公平なのか？など
- 監査と言いつつ、レコメンドするアイテムを変えたりとシステムの中身に入り込む必要はあるため、客観的な監査をおこなうハードルは高そう
- 実データを用いた評価についてはやや疑問の残る所もある。監査に必要な計算量が対象ユーザ数に依存しないなど、実運用を意識した良いアルゴリズムなので、評価はもう少し深堀りして欲しかった気も
論文メモ
1. Introduction
- レコメンドシステムにおいて不公平が生じていないか監査する仕組みの必要性が議論されている
- 同程度のスキルを持つ男性と女性とで、後者の方が高給な仕事のオンライン広告が表示される機会が少なかった (Detta et al. 2015)
- 似たような仕事のオンライン広告が表示される割合が男性と女性とで異なっている (Imana et al. 2021)
- これまでに提案されている監査フレームワークのほとんどは、属性間でレコメンドの不公平が生じていないかをチェックするものであるが、属性間での公平性が必ずしも個人の嗜好に沿ったものになっているとは限らない
- 個人の嗜好を考慮した公平性の監査フレームワークとして、レコメンドにおける「妬み」に着目した手法を提案
- 妬み：自分に対するレコメンドよりも良いレコメンドが他者に対して生じている状態。全ての人に対してその人自身にとってベストなレコメンドがおこなわれている場合に「妬みが無い（envy-free）」公平なレコメンドがおこなわれていると定義する
2. Related work
- 公平なレコメンドについて
- 機械学習における公平性については大きく２つの軸が存在
- 意思決定の判断基準として用いられていはいけない属性（protected attributes。人種、性別、宗教、etc.）に着目 or 個人に着目
- 予測値や予測誤差の分布不変性（parity）に着目 or 対象者の嗜好に着目（好みに沿っているのであれば予測の分布が異なっても良い）
- 提案手法は「個人」「対象者の嗜好」に着目
- 機械学習における公平性については大きく２つの軸が存在
- 多腕バンディット
- 複数のアームを引いてそれぞれ確率的に報酬が得られる場合に、できるだけ報酬が高くなるようなアームの探索をおこなう
- さまざまな探索方針が提案されているが、本論文の手法はthreshold bandits (Locatelli, Gutzeit, and Carpentier 2016; Kano et al. 2019)に近い
- 公正な配分
- envy-freenessの概念は公正な資源配分に関する経済学の研究が初出 (Foley 1967)
3. Envy-free recommendations
3.1 Framework
- ユーザ$m$に対するレコメンドの効用$u^m$は(1)式で表される。
- $m \in {1,...,M}$: ユーザ
- $\pi^m (a|x)$: ユーザ$m$に対するレコメンド方針。状況$x \in \mathcal{X}$においてアイテム$a \in \mathcal{A}$がレコメンドされる確率として表現
- $q^m(x)$: ユーザ$m$が$x$の状況になる確率
- $\nu^m (a|x)$: ユーザ$m$が$x$の状況においてアイテム$a$をレコメンドされる事で得られる報酬$r$の確率分布
- $\rho^m (a|x)$: ユーザ$m$が$x$の状況においてアイテム$a$をレコメンドされる事で得られる報酬$r$の期待値
- アイテム$a$は特定のアイテムを指す場合もあれば、構造化された複数アイテムの場合もある。以下、状況$x$とアイテム$a$の具体例
- $x$: 検索エンジンに対するクエリ、$a$: 表示されるドキュメントの順序
- $x$: ユーザが選択した曲、$a$: 次に再生される曲（またはプレイリスト全体）
- 論文では、上記確率分布が定常である（時間を経て変化しない。固定）という仮定を置いている。分布が非定常な場合についてはfuture work
- 提案手法の目的は、レコメンド方針$\pi^m (a|x)$が公平であるか否かを監査することである（公平な方針$\pi$を学習することではない）
3.2 ε-envy-free recommendations
- 既存のレコメンド監査フレームワークは主に下記2種の基準がベースとなっている
- recommendation parity: レコメンドされるアイテムの分布はユーザ（またはそのグループ）間で等しい
- equal user utility: ユーザ（またはそのグループ）はレコメンドによって同等の効用を得なければならない（すなわち$\forall m, n, u^m(\pi^m) = u^n(\pi^n)$）
- 上記2基準は、個人の嗜好に基づいたパーソナライズドレコメンデーションとは相反しうるといった課題がある
- ユーザ間で分布が等しくなるように調整されたレコメンドが、個人の嗜好とマッチしているとは限らない
- ユーザ間で効用が等しくなるような調整をおこなった場合、最大で得られるはずであった効用よりも低い効用を受け入れなければいけないユーザが生じうる
- そこで、新たにenvy-freenessの概念を新たな公平性の基準として提案する（Definition 3.1）
- 全てのユーザ$m$にとって、自身に対するレコメンド方針$\pi^m$で得られる効用（$+\epsilon$）は他のユーザに対するレコメンド方針で得られる効用よりも大きい
- あるユーザに対してベストなレコメンド方針を、それ以外のユーザに対して取ってしまった場合に不公平と判断する（「妬み」が生じる）
3.3 Compatibility of envy-freeness
- 個々のユーザにとって効用が最適となるレコメンドはenvy-freeである
- equal user utilityを実現しようとすると、効用が減少するユーザが生じうるので最適ではない（＝envy-freeではない）
- アイテム側の観点での公平性との関係について
- これまで議論してきた公平性はenvy-freeness含めユーザ側の観点での公平性であるが、アイテム側の観点での公平性についても下記の基準が存在する
- Parity of exposure: 個々のユーザに対してあるアイテムカテゴリがレコメンドされる頻度が、そのカテゴリ内のアイテム数に比例している（アイテム数の多いカテゴリほど良くレコメンドされる）
- Equity of exposure: 個々のユーザに対してあるアイテムカテゴリがレコメンドされる頻度が、そのカテゴリとそのユーザの適合度の平均に比例している（好みのカテゴリほどよくレコメンドされる）
- この時、Parity of exposureなレコメンド方針はenvy-freeであるが、Equity of exposureなレコメンド方針は一般にenvy-freeでない
- 例：アイテム$a$が大好きだが別カテゴリのアイテム$b$も好きなユーザは、アイテム$a$だけが好きなユーザを妬むことになる（$a$だけレコメンドしてくれた方が効用が大きいため？）
- これまで議論してきた公平性はenvy-freeness含めユーザ側の観点での公平性であるが、アイテム側の観点での公平性についても下記の基準が存在する
3.4 Probabilistic relaxation of envy-freeness
- これまでのenvy-freenessの定義は(a)あるユーザのレコメンド方針をその他全てのユーザと比較する、(b)全てのユーザを対象に(a)がおこなわれる、の2点が前提となっていたが、それではユーザ数が増えるごとに監査のコストが膨れ上がる
- 実用を想定し、以下の緩和をおこなうことで対象ユーザ数にコストが依存しない監査をおこなうことが可能に
- 小さな確率値$\lambda, \gamma$を導入
- 基準を「少なくとも$1-\lambda$の割合のユーザにとって、彼らに対するレコメンド方針で得られる効用が、全ての方針で得られる効用の上位$\gamma$%に属する」と緩和（$(\epsilon, \gamma, \lambda)$-envy-free）
4. Certifying envy-freeness
4.1 Auditing Scenario
- envy-freenessについて確認するためには「もし他のレコメンドを受けていたらより高い効用が得られていたか？」という事実と反する状態を想定した問いに答える必要がある（反実仮想）
- 本論文では、監査者がレコメンドを操作することで、通常のレコメンド方針とは異なるレコメンドを実際におこなった結果を元にenvy-freenessを監査するスキームを提案
- 各時刻$t$において、監査者はあるユーザに対し「通常のレコメンド結果」を示すか「他ユーザのレコメンド方針に基づいたレコメンド結果」を示すかを選択する
- 他者のレコメンド方針を用いることに倫理的な問題が無いかは確認する必要あり
4.2 The equivalent bandit problem
- 上記スキームを考えると、あるユーザにおけるenvy-freenessの確認は、既存のレコメンド方針よりも高い効用を得られるレコメンド方針が与えられている他のユーザを探索する多腕バンディット問題とみなすことができる
- 以下、多腕バンディットの表記に従ってユーザを「アーム」、確認対象のユーザを「ベースライン」と表現
- ユーザ$k$に対する効用$u^k (\pi^k))$を簡略化して$\mu_k$と表記
- あるユーザに対する監査（OECF: Online Certification of Envy-Freeness）は、パラメータ$\epsilon, \alpha$が与えられた元で下記の目標を持つ
- 正確性：OECFがenvyと判断した場合、ベースラインよりも効用の高いアームが存在（$\exists k, \mu_k > \mu_0$）。OECFが$\epsilon$-no-envyと判断した場合、全てのアームの効用はベースラインの効用+$\epsilon$以下である（$\max_{k} \mu_k \leq \mu_0 + \epsilon$）
- envyの方に$\epsilon$がついていないのは、後述する監査継続時間や監査コストを有限時間に抑えるために必要な要件
- レコメンド性能：時刻$t$までであるユーザが得られている効用の平均は、OECFが無かった場合に本来得られるはずだった効用$\times (1-\alpha)$以上である
- 正確性：OECFがenvyと判断した場合、ベースラインよりも効用の高いアームが存在（$\exists k, \mu_k > \mu_0$）。OECFが$\epsilon$-no-envyと判断した場合、全てのアームの効用はベースラインの効用+$\epsilon$以下である（$\max_{k} \mu_k \leq \mu_0 + \epsilon$）
- 目標については、confidence parameter $\delta$を導入し「確率$(1-\delta)$で上記2目標は達成されている」といった形で評価される
- また、OECFのアルゴリズム自体を評価するメトリックとして下記を考える
- 監査継続時間：アルゴリズムが収束する（envyか$\epsilon$-no-envyの判断が下される）までに要する時間
- 監査コスト：OECFが無かった場合に得られるはずであった効用の総和と、OECFによる監査の元で得られた効用の総和の差分
4.3 The OECF Algorithm
- この辺りから数式がすごいので概要だけ。。
- パラメータについて
- $\xi_t$: レコメンド性能（時刻$t$までに得られている平均的な効用が、OECFが無かった場合の$(1-\alpha)$倍以上）を担保するための条件として与えられるしきい値（式(4)）
- $\beta_k (t)$: アーム$k$の効用の信頼区間の幅
- $\underline{\mu}_k$: アーム$k$の効用の信頼区間下限
- $\bar{\mu}_k$: アーム$k$の効用の信頼区間上限
- $[K]$: ベースライン以外の$K$個のアームの集合（$K$の与え方は、後述する全体の監査で出現）
- $S_t$: 時刻$t$においてベースラインとの比較対象になっているアームの集合
- アルゴリズムの流れのイメージ
- （ステップ1）ベースライン以外の$K$個のアームを比較対象の集合の初期値$S_0$とする
- （ステップ2）各時刻$t$においてステップ3以降を実施
- （ステップ3）$S_t$からアームを一つサンプリング
- （ステップ4,5）「ベースラインの効用の信頼区間の幅」が「他のアームの効用の信頼区間の幅の最小値」より大きい（対象のユーザに対するレコメンド方針の効用を十分に観測できていない）か、レコメンド性能を担保するためのしきい値$\xi_t$が0未満である場合、アームはベースラインを指定（通常のレコメンドをおこなう）。そうでない場合は、ステップ3でサンプリングされたアームを指定（他のユーザのレコメンド方針に従ったアイテムを提示）
- （ステップ6）$x_t, a_t, r_t$（クエリ、レコメンドしたアイテム、レコメンド結果）から信頼区間のパラメータをアップデート
- （ステップ7）比較対象のアームを、ベースラインの効用の信頼区間下限$+\epsilon$よりも信頼区間上限が大きいアームに限定（ベースラインも明らかに効用が低いアームを除いている）
- （ステップ8）効用の信頼区間下限が、ベースラインの効用の信頼区間上限よりも大きいアームが存在（既存のレコメンド方針より高確率で効用の高い他のレコメンド方針が存在）したら、監査結果をenvyと返して終了
- （ステップ9）比較対象のアームがなくなったら、監査結果を$\epsilon$-no-envyとして返して終了
4.4 Analysis
- 監査継続時間と監査コストのオーダーについては、理論的に下記の通り求められる
- ベースラインと他のアームとの効用のギャップに依存
- 「正確性」の定義でenvyの方にも$\epsilon$をつけてしまうと、$\mu_k = \mu_0 + \epsilon$の時に監査継続時間が有限にならない可能性が出てしまう
4.5 Full audit
- レコメンドシステム全体を監査するためには、全てのユーザ$m=1,...,M$に対してOCEFを実施する必要があるが、ユーザ数が大規模な場合に破綻してしまう。確率的な基準を導入することで、$M$に依存しない監査を実施する手法を提案
- 上記アルゴリズムの通りにサンプリングされたユーザに対してOECFをおこない、もし一度でもenvyと出力されたらレコメンドシステムはenvy-freeでない（公平でない）、一度もenvyと出力されなければレコメンドシステムは$(\epsilon, \gamma, \lambda)$-envy-freeであると判断。この判断結果は$1-\delta$の確率で正しい。
- サンプリングされた監査対象者数および比較対象者数が$M$に依存していない
5. Experiments
- Last.fmのデータ（Cantador et al. 2011）
- 19,000ユーザの楽曲視聴履歴
- 2,500の人気楽曲を対象
- MovieLens-1Mデータ（Harper and Konstan 2015）
- ユーザによる映画の評価データ
- 上位2,000ユーザおよび2,500映画を使用
- 5段階のレーティングで3未満を「好みでない」、それ以上を「好み」とみなした2値をラベルとして使用
- レコメンドの評価をおこなうためには、全ユーザの全楽曲に対する好き嫌いを正解（ground truth）として持つ必要あり。欠損値補完の有名な手法であるmatrix completion algorithm for implicit feedback dataを使用
- https://github.com/benfred/implicit - レコメンド手法としては、低ランク行列分解を用いた手法（Bell and Sejnowski 1995）を使用
- 報酬は、レコメンドされたアイテムが好みか否かのground truthをパラメータとしたベルヌーイ分布に従う
5.1 Sources of envy
- 「妬み」を評価する方針として、妬みの最大値$\Delta^m = \max ( \max_{n \in [M]} u^m (\pi^n) - u^m (\pi^m), 0)$を用いて下記を考える
- ユーザが経験する妬みの平均：$\frac{1}{M} \sum_{m \in [M]} \Delta^m$
- 妬みの最大値が$\epsilon$以上であるユーザの割合：$\frac{1}{M} \sum_{m \in [M]} \1_{ \lbrace \Delta^m > \epsilon \rbrace }$
- Envy from model mispecification
- モデルの表現力不足による「妬み」の発生。予測モデルにおける潜在次元数（number of factors）を変化させた時、1では全員に対するレコメンド結果が等しくなるため妬みは発生しないが、次元数が増えるに従って妬みが大きくなり、さらに次元数が増えてモデルの表現力が高くなる（良いレコメンドができてくる）と妬みは低下する
- Envy from equal user utility
- ユーザ間の効用が等しくなるようなレコメンドをおこなうequal user utility (EUU)によっても妬みが発生。全てのユーザの効用が等しくなるような制約を加えた上で全体の効用を最大化するようなレコメンドをおこなうEUUと、ground truthをそのままレコメンドする手法（OPT）とを比較すると、EUUによって妬みが生じていることが確認できる
5.2 Evaluation of auditing algorithm
- 多腕バンディットのシミュレーションを用いた評価と、MovieLensおよびLast.fmのデータを用いた評価を通じて、監査継続時間と監査コストの関係について確認
- Bandit experiments
- 多腕バンディットのシミュレーションを4種の問題設定で実施
- Problem 1: ベースラインの効用が最良。他のアームの効用は同等に低い
- Problem 2: 1番目のアームの効用が最良。他のアームの効用はベースラインと同等に低い
- Problem 3: ベースラインの効用が最良。他のアームの効用はそれぞれ大きく異なる
- Problem 4: 1番目のアームの効用が最良。他のアームの効用はベースライン含めそれぞれ大きく異る
- レコメンド性能に関するパラメータ$\alpha$を変化させた時の監査継続時間（duration）と監査コスト（cost）を確認（$\alpha$が小さいほど監査による効用の低下を許さない）
- $\alpha$が大きくなるほど監査継続時間は低下し、監査コストは大きくなる傾向に（$\alpha$が大きいほど他のアームを引く機会が増えるため）
- Problem2,3,4では、ある$\alpha$において監査継続時間が極小値を取っている。これは$\alpha$を小さくすることが下記のメリット／デメリット双方を持つためである
- ベースラインを多く選択し、ベースラインの信頼区間幅が狭まることで、比較対象から他のアームが削られるメリット
- 他のアームが選択されず、他のアームの信頼区間幅がなかなか狭まらないので、比較対象から削ることができないデメリット
- コストに関する評価では、他のアームを選択する事で効用がマイナスにならないProblem 2を除いて、$\alpha$が大きくなるほどコストは増加する
- 多腕バンディットのシミュレーションを4種の問題設定で実施
- MovieLens and Last.fm experiments
- MovieLensおよびLast.fmのデータを用いた評価。レコメンド方針として、レコメンド手法で予測したスコアに対して更にsoftmax関数を適用したスコアを用いる
- softmax関数のパラメータである温度の逆数を5にした場合と10にした場合それぞれを確認。温度の逆数が5の時、最終的なスコアは均一化される傾向にあるため、皆に対して似たようなレコメンドがおこなわれenvy-freeとなる。一方で、温度の逆数が10の場合予測スコアには差が生じるため、envyが発生。
- envyなレコメンドとenvy-freeなレコメンド（EF）とで監査継続時間と監査コストを評価。EFにおいては20トライアルにおける全てのユーザの結果を、envyなレコメンドにおいては$\epsilon$-envyなユーザの結果の平均を用いた
- （envyでないユーザが被るコストを評価しなくて良いのだろうか？）
- 評価の結果、多腕バンディットのシミュレーションと同様の傾向が観測できた。envyなレコメンドの場合、$\alpha$が大きくなるほど監査コストは低下した
- （それはenvyでないユーザを除いているからでは？）
- （監査継続時間が最小でも100万ステップ弱必要なように見えるが、現実的に可能？）
- MovieLensおよびLast.fmのデータを用いた評価。レコメンド方針として、レコメンド手法で予測したスコアに対して更にsoftmax関数を適用したスコアを用いる
Conclusion
略