論文の概要: Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice

• arxiv url: http://arxiv.org/abs/2503.11575v2
• Date: Wed, 11 Jun 2025 20:39:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 15:37:22.199389
• Title: Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice
• Title（参考訳）: 最高価格選択のための公正なスコーリング関数の発見:ハードネスから練習へ
• Authors: Guangya Cai,
• Abstract要約: 我々は、上位k$選択のための公平な線形スコアリング関数を同定する問題に対処する。 既存のアルゴリズムは特に高次元において効率的にスケールしない。 我々の解はSOTAと比較して最大数桁のスピードアップを達成する。
• 参考スコア（独自算出の注目度）: 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 rise of automated decision-making software, it is important that the outcome of this process, called top-$k$ selection, is fair. Here we consider the problem of identifying a fair linear scoring function for top-$k$ selection. The function computes a score for each item as a weighted sum of its (numerical) attribute values, and must ensure that the selected subset includes adequate representation of a minority or historically disadvantaged group. Existing algorithms do not scale efficiently, particularly in higher dimensions. Our hardness analysis shows that in more than two dimensions, no algorithm is likely to achieve good scalability with respect to dataset size, and the computational complexity is likely to increase rapidly with dimensionality. However, the hardness results also provide key insights guiding algorithm design, leading to our dual-algorithm solution: (1) For small values of $k$, our hardness analysis reveals a gap in the hardness barrier. By addressing various engineering challenges, including achieving efficient parallelism, we turn this potential of efficiency into an optimized algorithm delivering substantial practical performance gains. (2) For large values of $k$, where the hardness is robust, we employ a practically efficient algorithm which, despite being theoretically worse, achieves superior real-world performance. Experimental evaluations on real-world datasets then explore scenarios where worst-case behavior does not manifest, identifying areas critical to practical performance. Our solution achieves speed-ups of up to several orders of magnitude compared to SOTA, an efficiency made possible through a tight integration of hardness analysis, algorithm design, practical engineering, and empirical evaluation.
• Abstract（参考訳）: スコアリング関数に基づいて$n$アイテムのデータセットから$k$ "best"項目のサブセットを選択することは、意思決定における重要なタスクである。 自動意思決定ソフトウェアの台頭を考えると、このプロセスの成果がトップ$k$選択(top-$k$ selection)と呼ばれ、公正であることが重要である。 ここでは、上位k$選択のための公平な線形スコアリング関数を同定する問題を考察する。 関数は各項目のスコアを(数値的な)属性値の重み付け和として計算し、選択されたサブセットが少数あるいは歴史的に不利なグループの適切な表現を含むことを保証しなければならない。 既存のアルゴリズムは特に高次元において効率的にスケールしない。 我々の硬度分析は、2次元以上の場合、データセットサイズに関して優れたスケーラビリティを実現するアルゴリズムは存在せず、計算複雑性は次元性によって急速に増大する可能性が高いことを示している。 しかし、ハードネスの結果はまたアルゴリズム設計を導く重要な洞察を与えており、この二元アルゴリズムの解決策に繋がる: 1)k$の小さな値の場合、ハードネス分析はハードネス障壁のギャップを露呈する。 効率的な並列性を達成することを含む様々な工学的課題に対処することにより、この効率のポテンシャルを最適化されたアルゴリズムに転換し、実質的な性能向上を実現する。 2) 硬さが堅牢な大容量の$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)

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

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