論文の概要: Leximax Approximations and Representative Cohort Selection

• arxiv url: http://arxiv.org/abs/2205.01157v2
• Date: Tue, 17 May 2022 18:32:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-19 16:38:20.885310
• Title: Leximax Approximations and Representative Cohort Selection
• Title（参考訳）: レキシマックス近似と代表コホート選択
• Authors: Monika Henzinger, Charlotte Peale, Omer Reingold, Judy Hanwen Shen
• Abstract要約: 幅広い候補から代表コホートを見つけることは、多くの文脈で発生する目標である。 レキシマックス解を見つけることは、ある群の効用の小さなバリエーションに大きく依存することができる。 線形ユーティリティを用いたレキシマックスコホート選択の整数解を見つけることはNP-Hardであることを示す。
• 参考スコア（独自算出の注目度）: 10.55182802721649
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding a representative cohort from a broad pool of candidates is a goal that arises in many contexts such as choosing governing committees and consumer panels. While there are many ways to define the degree to which a cohort represents a population, a very appealing solution concept is lexicographic maximality (leximax) which offers a natural (pareto-optimal like) interpretation that the utility of no population can be increased without decreasing the utility of a population that is already worse off. However, finding a leximax solution can be highly dependent on small variations in the utility of certain groups. In this work, we explore new notions of approximate leximax solutions with three distinct motivations: better algorithmic efficiency, exploiting significant utility improvements, and robustness to noise. Among other definitional contributions, we give a new notion of an approximate leximax that satisfies a similarly appealing semantic interpretation and relate it to algorithmically-feasible approximate leximax notions. When group utilities are linear over cohort candidates, we give an efficient polynomial-time algorithm for finding a leximax distribution over cohort candidates in the exact as well as in the approximate setting. Furthermore, we show that finding an integer solution to leximax cohort selection with linear utilities is NP-Hard.
• Abstract（参考訳）: 幅広い候補者から代表的コホートを見つけることは、委員会や消費者パネルの選択など、多くの文脈で発生する目標である。 コホートが人口を表す程度を定義するには多くの方法があるが、非常に魅力的な解概念は語彙的最大性(leximax)であり、これは、既に悪化している人口の有用性を低下させることなく、人口の効力を増大させることができるという自然な解釈を提供する。 しかし、レキシマックス解を見つけることは、ある群の効用における小さな変化に大きく依存することができる。 本研究では,アルゴリズム効率の向上,有用性の向上,雑音に対するロバスト性という3つの動機を持つ近似レキシマックス解の新たな概念について検討する。 その他の定義的貢献の中で、同様に魅力的な意味論的解釈を満たす近似語彙の概念をアルゴリズムで実現可能な近似語彙の概念に関連付ける。 群ユーティリティがコホート候補よりも線形である場合、近似設定と同様に正確にコホート候補に対するレキシマックス分布を求める効率的な多項式時間アルゴリズムを与える。 さらに,線形ユーティリティを用いたレキシマックスコホート選択の整数解を求めることはNP-Hardであることを示す。

関連論文リスト

• DALex: Lexicase-like Selection via Diverse Aggregation [6.394522608656896]
  DALex(Diversely Aggregated Lexicase)は,レキシケース選択とその緩和された変種に対して,大幅な高速化を実現することを示す。 プログラム合成, 深層学習, 記号回帰, 学習システムの結果から, DALexは語彙選択とその緩和された変種に対して, 大幅な高速化を実現することが示された。
  論文  参考訳（メタデータ） (2024-01-23T01:20:15Z)
• Calculating lexicase selection probabilities is NP-Hard [0.0]
  lex-prob というこの問題が NP-Hard であることを示す。 この証明は、よく知られたNP-Complete問題であるSATを、時間内にlex-probに還元することで達成する。
  論文  参考訳（メタデータ） (2023-01-17T06:51:44Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  我々は、ブラックウェルの接近性からインスピレーションを得て、フォン・ノイマンの勝者の概念をマルチ基準設定に一般化する。 本フレームワークは,基準間の選好の非線形集約を可能にし,多目的最適化から線形化に基づくアプローチを一般化する。 凸最適化問題の解法として,マルチ基準問題インスタンスのブラックウェルの勝者が計算可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-05T03:23:11Z)
• Certifiably Polynomial Algorithm for Best Group Subset Selection [0.9667631210393929]
  ベストグループサブセットの選択は、応答変数の最良の解釈可能性を達成するために重複しないグループの小さな部分を選択することを目的としている。 有効群を反復的に検出し,無力群を除外するグループスプライシングアルゴリズムを提案する。 提案手法の効率と精度を,合成データセットと実世界のデータセットを比較して検証する。
  論文  参考訳（メタデータ） (2021-04-23T03:05:11Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets [5.222705629027499]
  超体積インジケータのサブモジュラー特性を利用した新しい遅延グリードアルゴリズムを提案する。 実験結果から,提案アルゴリズムは元のグレディ包摂アルゴリズムよりも数百倍高速であることがわかった。
  論文  参考訳（メタデータ） (2020-07-04T09:19:45Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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