論文の概要: Sampling Random Group Fair Rankings
- arxiv url: http://arxiv.org/abs/2203.00887v1
- Date: Wed, 2 Mar 2022 05:59:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-03 16:04:00.095240
- Title: Sampling Random Group Fair Rankings
- Title（参考訳）: ランダムグループフェアランキングのサンプリング
- Authors: Sruthi Gorantla, Amit Deshpande, Anand Louis
- Abstract要約: 我々は、異なるセンシティブな集団からランク付けされた項目をマージするランダム化されたグループフェアランキングの問題を考える。
公理的アプローチを採り、ランダム群フェアランキングをサンプリングするために$mathcalD$という一意分布が存在することを示す。
我々は$mathcalD$からランダム群フェアランキングをサンプリングする3つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.963918049835375
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider the problem of randomized group fair ranking that
merges given ranked list of items from different sensitive demographic groups
while satisfying given lower and upper bounds on the representation of each
group in the top ranks. Our randomized group fair ranking formulation works
even when there is implicit bias, incomplete relevance information, or when
only ordinal ranking is available instead of relevance scores or utility
values.
We take an axiomatic approach and show that there is a unique distribution
$\mathcal{D}$ to sample a random group fair ranking that satisfies a natural
set of consistency and fairness axioms. Moreover, $\mathcal{D}$ satisfies
representation constraints for every group at every rank, a characteristic that
cannot be satisfied by any deterministic ranking. We propose three algorithms
to sample a random group fair ranking from $\mathcal{D}$. Our first algorithm
samples rankings from $\mathcal{D}$ exactly, in time exponential in the number
of groups. Our second algorithm samples random group fair rankings from
$\mathcal{D}$ exactly and is faster than the first algorithm when the gap
between upper and lower bounds on the representation for each group is small.
Our third algorithm samples rankings from a distribution $\epsilon$-close to
$\mathcal{D}$ in total variation distance, and has expected running time
polynomial in all input parameters and $1/\epsilon$ when there is a large gap
between upper and lower bound representation constraints for all the groups. We
experimentally validate the above guarantees of our algorithms for group
fairness in top ranks and representation in every rank on real-world data sets.
- Abstract（参考訳）: 本稿では,異なる敏感な集団の項目のランクリストをマージするランダム化グループフェアランキングの問題を考察し,上位階層における各グループの表示における下層と上層の境界を満たしながら検討する。
ランダム化されたグループフェアランキングの定式化は、暗黙のバイアス、不完全関連情報、あるいは関連スコアやユーティリティ値の代わりに順序付けのみを利用できる場合でも有効です。
公理的アプローチをとり、一貫性と公平性公理の自然な集合を満たすランダム群フェアランキングをサンプリングするために、一意な分布 $\mathcal{d}$ が存在することを示す。
さらに、$\mathcal{d}$ は各ランクのすべてのグループの表現制約を満たすが、決定論的ランキングでは満足できない特徴である。
ランダム群フェアランキングを$\mathcal{D}$からサンプリングする3つのアルゴリズムを提案する。
最初のアルゴリズムは、グループ数で指数関数的に、正確に$\mathcal{d}$からランクを抽出します。
第2のアルゴリズムは、$\mathcal{d}$からランダムグループフェアランキングを正確にサンプリングし、各グループの表現における上界と下界の差が小さい場合、第1のアルゴリズムよりも高速である。
我々の第3のアルゴリズムは、分布 $\epsilon$-close から $\mathcal{D}$ に全変動距離でランク付けし、全ての入力パラメータのランニング時間多項式と、すべてのグループに対して上界と下界の表現制約の間に大きなギャップがある場合の1/\epsilon$ を予想している。
我々は,実世界のデータセット上の上位ランクにおけるグループフェアネスと各ランクの表現について,上記のアルゴリズムの保証を実験的に検証する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。