論文の概要: Fair Active Ranking from Pairwise Preferences
- arxiv url: http://arxiv.org/abs/2402.03252v1
- Date: Mon, 5 Feb 2024 18:09:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-06 14:17:24.805384
- Title: Fair Active Ranking from Pairwise Preferences
- Title（参考訳）: ペアの選好から公平にアクティブなランキング
- Authors: Sruthi Gorantla and Sara Ahmadian
- Abstract要約: 解離群に属する$n$の項目が与えられたとき、我々のゴールは、我々が提案する公正な目的関数に従って$(epsilon, delta)$-PACF-Rankingを見つけることである。
グループブラインドとグループアウェアの両方のアルゴリズムを提示し,そのサンプルパラメータを解析する。
- 参考スコア（独自算出の注目度）: 6.102498508368527
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the problem of probably approximately correct and fair (PACF)
ranking of items by adaptively evoking pairwise comparisons. Given a set of $n$
items that belong to disjoint groups, our goal is to find an $(\epsilon,
\delta)$-PACF-Ranking according to a fair objective function that we propose.
We assume access to an oracle, wherein, for each query, the learner can choose
a pair of items and receive stochastic winner feedback from the oracle. Our
proposed objective function asks to minimize the $\ell_q$ norm of the error of
the groups, where the error of a group is the $\ell_p$ norm of the error of all
the items within that group, for $p, q \geq 1$. This generalizes the objective
function of $\epsilon$-Best-Ranking, proposed by Saha & Gopalan (2019).
By adopting our objective function, we gain the flexibility to explore
fundamental fairness concepts like equal or proportionate errors within a
unified framework. Adjusting parameters $p$ and $q$ allows tailoring to
specific fairness preferences. We present both group-blind and group-aware
algorithms and analyze their sample complexity. We provide matching lower
bounds up to certain logarithmic factors for group-blind algorithms. For a
restricted class of group-aware algorithms, we show that we can get reasonable
lower bounds. We conduct comprehensive experiments on both real-world and
synthetic datasets to complement our theoretical findings.
- Abstract（参考訳）: 本稿では,ペアワイズ比較を適応的に実施することにより,アイテムのほぼ正当性(PACF)ランキングの問題を検討する。
解離群に属する$n$の項目が与えられたとき、我々のゴールは、提案する公正な目的関数に従って$(\epsilon, \delta)$-PACF-Rankingを見つけることである。
そこで,各クエリに対して,学習者が一対のアイテムを選択し,そのオラクルから確率的勝者フィードバックを受け取ることができる。
提案する目的関数は、グループのエラーの$\ell_q$ノルムを最小化するように要求する。ここで、グループのエラーは、そのグループ内のすべてのアイテムのエラーの$\ell_p$ノルムであり、$p, q \geq 1$である。
これは Saha & Gopalan (2019) によって提案された $\epsilon$-Best-Ranking の目的関数を一般化する。
客観的関数を採用することで、統一されたフレームワーク内での等式や比例エラーのような基本的な公平性の概念を探求する柔軟性を得ることができます。
パラメータの調整 $p$ と $q$ は、特定の公平な好みに合わせて調整できる。
グループブラインドとグループブラインドの両方のアルゴリズムを示し,その複雑さを解析する。
グループブレンドアルゴリズムに対して,特定の対数係数までのマッチング下限を提供する。
グループ認識アルゴリズムの制限クラスでは、妥当な下限が得られることを示す。
実世界および合成データセットの総合的な実験を行い、理論的な結果を補完する。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。
競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
論文 参考訳（メタデータ） (2024-05-31T19:26:05Z) - Monotone Individual Fairness [3.20902205123321]
オンライン学習者が予測精度を最大化し、類似した個人が同じように扱われることを保証することを目的として、オンライン学習の問題を個別の公正さで再考する。
監査者からのフィードバックを集約できる監査方式を検討する。
ここでは, 後悔, フェアネス違反の数に対して$(mathcalO(T2/3+2b),mathcalO(T5/6-b))$を0leq b leq$で上限とするオラクル効率アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-11T15:32:56Z) - Detection of Groups with Biased Representation in Ranking [28.095668425175564]
上位ランクの項目に偏りのある群を検出する問題について検討する。
2つの異なる公正度尺度に対する効率的な探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-12-30T10:50:02Z) - Sampling Ex-Post Group-Fair Rankings [8.963918049835375]
上記の分布からランダムなグループフェアランキングをサンプリングするアルゴリズムを2つ提案する。
我々の問題定式化は、暗黙のバイアス、不完全関連情報、あるいは順序付けのみのランク付けが可能である場合にも有効である。
我々は、我々のアルゴリズムが、現実のデータセット上での公正さとランキングユーティリティの最近のベースラインと好適に比較できるという実証的な証拠を与える。
論文 参考訳（メタデータ） (2022-03-02T05:59:26Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Multi-group Agnostic PAC Learnability [7.9649015115693444]
マルチグループ非依存型PAC学習可能性」について検討する。
このような予測器が存在することが保証される損失関数のキャラクタリゼーションを提供する。
本研究は,複数群フェアネス文献から得られた前向きおよび負の結果を統一し,拡張するものである。
論文 参考訳（メタデータ） (2021-05-20T18:43:36Z) - Fair for All: Best-effort Fairness Guarantees for Classification [11.818794470895837]
群に基づくフェアネスの概念は、既知の群全体のパフォーマンスの絶対測度を等化しようとする。
我々は、クラス $mathcalg$ における各グループ $g$ の保証は、$g$ の最高の分類器のパフォーマンスと関係しているという概念を提案する。
私たちはアルゴリズムを現実世界のデータセットでテストし、パフォーマンスに関する興味深い比較洞察を提供します。
論文 参考訳（メタデータ） (2020-12-18T13:22:14Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。