論文の概要: Sampling Ex-Post Group-Fair Rankings
- arxiv url: http://arxiv.org/abs/2203.00887v3
- Date: Mon, 29 May 2023 05:11:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 04:27:26.756022
- Title: Sampling Ex-Post Group-Fair Rankings
- Title（参考訳）: ポストグループフェアランキングのサンプリング
- Authors: Sruthi Gorantla, Amit Deshpande, Anand Louis
- Abstract要約: 上記の分布からランダムなグループフェアランキングをサンプリングするアルゴリズムを2つ提案する。
我々の問題定式化は、暗黙のバイアス、不完全関連情報、あるいは順序付けのみのランク付けが可能である場合にも有効である。
我々は、我々のアルゴリズムが、現実のデータセット上での公正さとランキングユーティリティの最近のベースラインと好適に比較できるという実証的な証拠を与える。
- 参考スコア（独自算出の注目度）: 8.963918049835375
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Randomized rankings have been of recent interest to achieve ex-ante fairer
exposure and better robustness than deterministic rankings. We propose a set of
natural axioms for randomized group-fair rankings and prove that there exists a
unique distribution $D$ that satisfies our axioms and is supported only over
ex-post group-fair rankings, i.e., rankings that satisfy given lower and upper
bounds on group-wise representation in the top-$k$ ranks. Our problem
formulation works even when there is implicit bias, incomplete relevance
information, or only ordinal ranking is available instead of relevance scores
or utility values.
We propose two algorithms to sample a random group-fair ranking from the
distribution $D$ mentioned above. Our first dynamic programming-based algorithm
samples ex-post group-fair rankings uniformly at random in time $O(k^2\ell)$,
where $\ell$ is the number of groups. Our second random walk-based algorithm
samples ex-post group-fair rankings from a distribution $\delta$-close to $D$
in total variation distance and has expected running time $O^*(k^2\ell^2)$,
when there is a sufficient gap between the given upper and lower bounds on the
group-wise representation. The former does exact sampling, but the latter runs
significantly faster on real-world data sets for larger values of $k$. We give
empirical evidence that our algorithms compare favorably against recent
baselines for fairness and ranking utility on real-world data sets.
- Abstract（参考訳）: ランダム化ランキングは、決定論的ランキングよりも、前者の公正な露出と堅牢性を達成するために、近年の関心事である。
ランダム化されたグループフェアランキングに対する自然な公理のセットを提案し、我々の公理を満たす一意の分布$D$が存在することを証明し、ポストグループフェアランキングにのみ支持される。
我々の問題定式化は、暗黙のバイアス、不完全関連情報、あるいは、関連するスコアやユーティリティ値の代わりに順序付けのみを利用できる場合にも有効です。
上記の分布からランダムグループフェアランキングをサンプリングする2つのアルゴリズムを提案する。
我々の最初の動的プログラミングに基づくアルゴリズムは、群の数である$o(k^2\ell)$でランダムにグループ-フェアランキングをランダムにサンプリングする。
第2のランダムウォークベースアルゴリズムは,全変動距離の$\delta$-close から$d$ までの分布から,グループ-fairランキングを抽出し,与えられた上界と下界に十分なギャップがある場合に,実行時間 $o^*(k^2\ell^2)$ を推定した。
前者は正確なサンプリングを行うが、後者は実世界のデータセットでより高速に動作し、より大きな値が$k$である。
実世界のデータセット上での公平性とランキングユーティリティのベースラインとアルゴリズムが好適に比較できるという実証的な証拠を提示する。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Fair Active Ranking from Pairwise Preferences [6.102498508368527]
解離群に属する$n$の項目が与えられたとき、我々のゴールは、我々が提案する公正な目的関数に従って$(epsilon, delta)$-PACF-Rankingを見つけることである。
グループブラインドとグループアウェアの両方のアルゴリズムを提示し,そのサンプルパラメータを解析する。
論文 参考訳（メタデータ） (2024-02-05T18:09:48Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
本稿では,二部類ランキングにおける公平性を実現するためのモデルに依存しない後処理フレームワークxOrderを提案する。
xOrderは、教師なしおよび教師なしの公正度メトリックを含む、さまざまな分類モデルとランキングフェアネスメトリクスと互換性がある。
提案アルゴリズムを,4つのベンチマークデータセットと2つの実世界の患者電子健康記録リポジトリ上で評価した。
論文 参考訳（メタデータ） (2023-07-27T07:42:44Z) - Sampling Individually-Fair Rankings that are Always Group Fair [9.333939443470944]
公正ランキングタスクは、グループフェアネスの制約を満たすために、実用性を最大化するために一連のアイテムをランク付けするよう要求する。
近年の研究では、品物の効用の不確かさが不公平の原因となっている。
我々は,各アウトプットランキングがグループフェアであることを保証しながら,個別のフェア分布からランキングを抽出する効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-21T01:26:34Z) - Detection of Groups with Biased Representation in Ranking [28.095668425175564]
上位ランクの項目に偏りのある群を検出する問題について検討する。
2つの異なる公正度尺度に対する効率的な探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-12-30T10:50:02Z) - On the Problem of Underranking in Group-Fair Ranking [8.963918049835375]
ランク付けシステムのバイアスは、社会的・経済的不平等を悪化させ、意見を分極し、ステレオタイプを強化する。
本稿では,グループフェアランキングにおける下位ランクの問題について定式化する。
任意のランク付けを行い、同時にランク付けとグループフェアネスを保証した別のランク付けを出力する公平なランク付けアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-24T14:56:10Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - SetRank: A Setwise Bayesian Approach for Collaborative Ranking from
Implicit Feedback [50.13745601531148]
提案手法は,提案システムにおける暗黙的フィードバックの特性に対応するために,協調的ランキング(SeetRank)のためのセッティングワイドベイズ的手法を提案する。
具体的には、SetRankは、新しい設定された選好比較の後方確率を最大化することを目的としている。
また、SetRankの理論解析により、余剰リスクの境界が$sqrtM/N$に比例できることを示す。
論文 参考訳（メタデータ） (2020-02-23T06:40:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。