論文の概要: Finding a Fair Scoring Function for Top-$k$ Selection: Hardness, Algorithms, and Experiments

• arxiv url: http://arxiv.org/abs/2503.11575v1
• Date: Fri, 14 Mar 2025 16:40:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-17 22:04:29.417157
• Title: Finding a Fair Scoring Function for Top-$k$ Selection: Hardness, Algorithms, and Experiments
• Title（参考訳）: 上位k$選択のための公正なスコーリング関数の探索:硬さ、アルゴリズム、実験
• Authors: Guangya Cai,
• Abstract要約: ここでは, 線形スコアリング関数を, 公平なトップ$k$選択に対して同定する問題を考える。 関数は各項目のスコアを(数値的な)属性値の重み付け和として計算する。 既存のアルゴリズムは大規模で高次元のデータセットに効果的にスケールしない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Selecting a subset of the $k$ "best" items from a dataset of $n$ items, based on a scoring function, is a key task in decision-making. Given the widespread use of automated decision-making software nowadays, it is important that the outcome of this process, called top-$k$ selection, is fair. Here we consider the problem of identifying a linear scoring function for top-$k$ selection that is fair. The function computes a score for each item as a weighted sum of its (numerical) attribute values. Additionally, the function must ensure that the subset selected is a faithful representative of the entire dataset for a minority or historically disadvantaged group. Existing algorithms do not scale effectively on large, high-dimensional datasets. Our theoretical analysis shows that in more than two dimensions, no algorithm is likely to achieve good scalability with respect to dataset size (i.e., a run time of $O(n\cdot \text{polylog}(n))$), and the computational complexity is likely to increase rapidly with dimensionality. However, there are exceptions for small values of $k$ and for this case we provide significantly faster algorithms. We also provide efficient practical variants of these algorithms. Our implementations of these take advantage of modern hardware (e.g., exploiting parallelism). For large values of $k$, we give an alternative algorithm that, while theoretically worse, performs better in practice. Experimental results on real-world datasets demonstrate the efficiency of our proposed algorithms, which achieve speed-ups of up to several orders of magnitude compared to the state of the art (SoTA).
• Abstract（参考訳）: スコアリング関数に基づいて$n$アイテムのデータセットから$k$ "best"項目のサブセットを選択することは、意思決定における重要なタスクである。 近年、自動意思決定ソフトウェアが広く使われていることを考えると、このプロセスの成果であるトップ・ドル・セレクション(top-k$ selection)が公平であることが重要である。 ここでは、公平なトップ=k$選択に対する線形スコアリング関数を同定する問題を考察する。 関数は各項目のスコアを(数値的な)属性値の重み付け和として計算する。 さらに、選択されたサブセットが少数または歴史的に不利なグループのデータセット全体の忠実な代表であることを保証する必要がある。 既存のアルゴリズムは大規模で高次元のデータセットに効果的にスケールしない。 我々の理論的分析は、2次元以上の場合、データセットサイズ(すなわち、$O(n\cdot \text{polylog}(n))$)に関して優れたスケーラビリティを達成するアルゴリズムは存在しないことを示している。 しかし、$k$の小さな値には例外があり、この場合、かなり高速なアルゴリズムを提供する。 また、これらのアルゴリズムの効率的な実用的変種も提供する。 これらの実装は、現代のハードウェア(例えば、並列性を活用)を活用しています。 k$の大きい値に対して、理論的には悪いが、実際はより良い性能を示す代替アルゴリズムを与える。 実世界のデータセットによる実験結果から,提案アルゴリズムの効率性を示すとともに,最先端(SoTA)と比較して最大数桁の高速化を実現している。

関連論文リスト

• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
  論文  参考訳（メタデータ） (2025-02-13T01:27:11Z)
• Approximate Top-$k$ for Increased Parallelism [1.2557921586915128]
  そこで本研究では,バケット付き近似式をk$のアルゴリズムで評価する。 上位$が正確であるという要件を緩和することで、バケット付きアルゴリズムは利用可能な並列性を劇的に向上させることができる。 PyTorch用の高速なバケット付きトップ$実装もリリースしています。
  論文  参考訳（メタデータ） (2024-12-05T17:17:28Z)
• Efficient Budget Allocation for Large-Scale LLM-Enabled Virtual Screening [0.9558392439655016]
  そこで我々は,LLM-as- human-evaluatorアプローチによるスクリーニングを事実上実施し,コスト負担を低減した。 我々は,トップ$m$greedy評価機構を用いて,探索ファーストの上位$m$greedy (EFG-$m$) アルゴリズムを設計する。 驚いたことに、我々はボーナスランキング効果を発見し、アルゴリズムは選択されたサブセット内で、自然に無関心なランキングを誘導する。
  論文  参考訳（メタデータ） (2024-08-18T16:44:41Z)
• Identifying Easy Instances to Improve Efficiency of ML Pipelines for Algorithm-Selection [0.20718016474717196]
  本稿では,アルゴリズムの選択を必要とせず,ジェネリストソルバを用いて簡単に解決できる簡単なインスタンスを同定する手法を提案する。 これにより、機能計算に関連する計算予算が削減され、ASパイプライン内の他の場所で使用できるようになる。
  論文  参考訳（メタデータ） (2024-06-24T12:25:04Z)
• The Limits of Assumption-free Tests for Algorithm Performance [6.7171902258864655]
  与えられたモデリングタスクにおいてアルゴリズムはどの程度うまく機能し、どのアルゴリズムが最善を尽くすか? 一方、特定のトレーニングデータセットに対して$A$を実行して生成された特定の適合モデルが$n$であるのか?
  論文  参考訳（メタデータ） (2024-02-12T03:19:30Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
  我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。 提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
  論文  参考訳（メタデータ） (2023-03-01T18:49:10Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms [17.57585822765145]
  本稿では,小データセットに適した正確なアルゴリズムと,大データセットにスケールする任意の$varepsilon in (0, 1)$に対して$frac1-varepsilon integer 5$-approximationアルゴリズムを提案する。 実世界のデータセットに対する実験は、提案アルゴリズムが既存のデータセットよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-05T13:02:35Z)
• Compactness Score: A Fast Filter Method for Unsupervised Feature Selection [66.84571085643928]
  本稿では,CSUFS (Compactness Score) と呼ばれる高速な教師なし特徴選択手法を提案する。 提案アルゴリズムは既存のアルゴリズムよりも正確で効率的である。
  論文  参考訳（メタデータ） (2022-01-31T13:01:37Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Test Score Algorithms for Budgeted Stochastic Utility Maximization [12.360522095604983]
  既存のスコアリング機構、すなわちレプリケーションテストスコアを拡張して、異種アイテムのコストとアイテムの値を統合する。 我々のアルゴリズムと近似は、テストスコアが特定の期待値のノイズ見積もりであると仮定する。 我々は,我々のアルゴリズムが,同じ近似保証を維持しながら,商品が同じ方法で到着する状況に適応できることを示す。
  論文  参考訳（メタデータ） (2020-12-30T15:28:41Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• An Efficient $k$-modes Algorithm for Clustering Categorical Datasets [8.528384027684194]
  我々は, OTQT と呼ばれる$k$-modes の斬新で効率的な実装を提供する。 OTQTは既存の$k$-modesアルゴリズムでは検出不可能な目的関数を改善するために更新されていることを証明している。 OTQTはイテレーション毎に常に正確で、最終最適化までほぼ常に高速である(一部のデータセットではわずかに遅い)。
  論文  参考訳（メタデータ） (2020-06-06T18:41:36Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。