Fairness of Classifiers in the Presence of Constraints between Features

Martin C. Cooper および Imane Bousdira による論文「特徴間の制約が存在する際の分類子の公平性」の詳細な技術的要約を以下に示す。

1. 問題定義

本論文は、機械学習の分類子における公平性の定義と評価において重要な欠落を扱っている：特徴間の論理的制約の存在である。

• 文脈: 公平性の標準的な定義（例えば、無関心による公平性）は、意思決定が保護された特徴（性別、人種など）に依存しない場合、その決定は公平であると仮定することが多い。
• 課題: 現実世界のシナリオでは、特徴はほとんど独立していない。制約は以下の理由で存在する：
  • 符号化: 例えば、正確に 1 つのブール特徴が真でなければならないワンホット符号化。
  • 現実世界の論理: 例えば、「ある人が産休中である場合、その人は女性であり、かつ雇用されている必要がある」といったもの。
• 結果: これらの制約を無視すると、偽陽性（公平な分類子を不公平とみなす）または偽陰性（不公平な分類子を公平とみなす）につながる可能性がある。
  • 例: 性別が反転するとモデルの出力が変化するため、モデルが性別に依存しているように見える場合でも、制約により性別を反転させることが他の特徴（雇用状況など）の変更を強制する場合、その決定は実際には有効な特徴空間において性別に依存していない可能性がある。
• 目的: 制約 ($C$) の存在下で公平性を形式的に定義し、これらの定義を検証する計算複雑性を分析すること。

2. 手法と中核概念

著者らは、制約付き特徴空間内で帰納的説明 (AXp) と 主項 (PI) を利用する。

主要な定義

• 特徴空間 ($F$): 特徴ドメインのデカルト積。
• 制約 ($C$): 有効なインスタンスを制限する論理規則の集合。有効な空間は $F[C]$ である。
• 保護された特徴 ($P$) と保護されていない特徴 ($N$): $P$ には機微属性（例：性別）が含まれる；$N$ には他のものが含まれる。
• 帰納的説明 (AXp): インスタンス $x$ における $S$ の値を固定することで、$F[C]$ 内のインスタンスのみを考慮して分類子出力 $\kappa(x)$ を保証する特徴の部分集合 $S$。
• 主項説明 (PI 説明): 他の AXp によって厳密に包含されない AXp。制約付き空間では、包含関係は単なる集合の包含ではなく、$F[C]$ 内での論理的含意によって定義される。
• 公平な PI 説明: 保護された特徴を含まない PI 説明（$S \cap P = \emptyset$）。

提案される公平性の定義

本論文は、分類子 $\kappa$ の公平性に対する 3 つの明確な定義を提案する：

1. 制約付き無関心による公平性 (Constrained FTU):

   • すべての $x, y \in F[C]$ について、$x_N = y_N$（保護されていない特徴が同一）であれば、$\kappa(x) = \kappa(y)$ である。
   • これは、決定が有効な空間内においてのみ保護されていない特徴に依存することを保証する。

2. 存在論的公平性:

   • すべての決定 $\kappa(x) = c$ に対して、少なくとも 1 つの公平な PI 説明が存在する。
   • 意味: 保護された特徴に依存しない、決定に対する何らかの有効な理由が存在する。

3. 普遍的公平性:

   • すべての決定 $\kappa(x) = c$ に対して、すべての PI 説明が公平である。
   • 意味: 決定に対するすべての最小限の理由は、保護された特徴を回避する。

理論的分析

著者らは、異なる制約シナリオ下でのこれらの定義間の関係を分析する：

• $P$ と $N$ 間の制約: これらを無視すると、公平性の評価が劇的に変化する可能性がある。決定が $F[C]$ においては普遍的に公平であっても、制約のない $F$ においては不公平に見える場合、またはその逆もあり得る。
• $P$ 内でのみ存在する制約: 制約が保護された特徴間でのみ存在する場合、公平な PI 説明の存在は、制約のない空間から制約付き空間へと維持される（命題 1）。
• $N$ 内でのみ存在する制約: 公平な PI 説明の存在は、これらの制約に依存しない（命題 2）。ただし、$N$ 内の制約は、制約のない空間には存在しなかった不公平な PI 説明を生み出す可能性がある（例 7）。

同等性のための特殊条件

本論文は、複雑な定義（存在論的/普遍的）が検証しやすい制約付き FTU に単純化される条件を特定する：

• 緩い制約: 保護された特徴のいかなる部分割り当ても、すべての保護されていない特徴の割り当てを厳密に包含しない場合、制約付き FTU は存在論的公平性を意味する。
• 分離された分類子: 分類子が「分離されている」とは、保護されていない特徴の集合 $N$ が、いかなる不公平な AXp によっても厳密に包含されない弱い AXp である場合を指す。これは存在論的公平性を保証する。

3. 主要な貢献

1. 制約付き公平性の形式化: 本論文は、論理制約を説明（PI 説明）の定義に直接統合することで、標準的な「無関心」の定義を超えて公平性を形式化した。
2. 制約の影響の証明: 産休、養子縁組機関などの複数の例を通じて、制約を無視することが誤った公平性評価につながることを著者らは証明した。
3. 公平性定義の階層: 本論文は、制約付き FTU、存在論的公平性、普遍的公平性の間の論理的関係を確立した。
   • 普遍的 $\implies$ 存在論的 $\implies$ 制約付き FTU。
   • 逆の含意は、特定の条件（「緩い制約」や「$P$ と $N$ 間の制約がない」など）が満たされない限り、一般には成り立たない。
4. 複雑性の分析: 著者らは、これらの公平性概念を検証する計算複雑性を多項式階層内でマッピングした。

4. 結果と複雑性分析

本論文は、これらの公平性定義を検証するための厳密な複雑性分析を提供する：

公平性の概念	複雑性クラス	注記
公平な PI 説明の存在（単一の決定について）	$\Sigma^P_3$	$\exists \forall \exists$ の量化子交代を含む。
不公平な PI 説明の存在	$\Sigma^P_3$	上記の補集合。
存在論的公平性の検証（分類子）	$\Pi^P_4$	全インスタンス ($\forall x$) に対して $\Sigma^P_3$ 性質をチェックする必要がある。
普遍的公平性の検証（分類子）	$\Pi^P_3$	どのインスタンスに対しても不公平な説明が存在しないことをチェックすることに相当する。
制約付き FTU の検証	coNP 完全	単一の SAT ソルバー呼び出しで解決可能（同じ $N$ を持つが出力が異なる $\exists x, y$ の存在をチェック）。

主要な複雑性の洞察:

• 制約付き FTU の検証は計算的に実行可能（coNP 完全）であり、標準的な SAT ソルバーで処理できる。
• 存在論的/普遍的公平性 の検証ははるかに困難（$\Pi^P_3$ または $\Pi^P_4$）であり、量化付きブール式 (QBF) ソルバーを必要とする。
• 実用的な示唆: 著者らは、存在論的公平性を保証する十分条件として「緩い制約」または「分離された」チェック（これらは $\Pi^P_2$）を使用することを提案しており、QBF ソルバーの代わりに単純な SAT ソルバーを使用可能にする。

5. 意義と結論

• 理論的基盤: 本論文は、公平性を真空状態で評価することはできず、特徴空間の論理構造（制約）が決定の「理由」の定義を根本的に変えることを確立した。
• 実用的ガイダンス: 制約を無視することが多い標準的な公平性ツールは、誤解を招く結果を生む可能性があると実務家に警告する。
• トレードオフ: 公平性定義の厳格さと計算の実行可能性の間にはトレードオフがある。
  • 普遍的公平性は最も厳格だが、検証が最も困難である。
  • 制約付き FTU は検証が最も容易だが、制約を介して保護された特徴に技術的に依存している決定の事例を見逃す可能性がある。
• 将来の方向性: 著者らは、この論理フレームワークを統計的相関の処理に拡張し、因果グラフ（因果的独立性による公平性 - FTCI）を用いた「保護された特徴の選択」の探求を提案する。

要約すると、本論文は公平性は特徴制約に文脈依存であると主張する。それは主項説明を通じて公平性を定義するための形式的フレームワークを提供し、理論的厳密性と計算の実行可能性のバランスを取りながら、これらの定義を検証するためのロードマップを提供する。