論文の概要: Diversity in Kemeny Rank Aggregation: A Parameterized Approach
- arxiv url: http://arxiv.org/abs/2105.09413v1
- Date: Wed, 19 May 2021 21:50:03 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-21 13:30:10.566561
- Title: Diversity in Kemeny Rank Aggregation: A Parameterized Approach
- Title（参考訳）: kemenyランクアグリゲーションの多様性:パラメータ化アプローチ
- Authors: Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de
Oliveira Oliveira, Petra Wolf
- Abstract要約: ソリューション多様性と呼ばれる最近の人工知能のトレンドは、最適性の概念の発展に焦点を当てている。
本研究では,この組み合わせがケメニー・ランク・アグリゲーションの分野に与える影響について検討する。
我々の主な成果は、線形に順序付けられた投票よりも伝統的な集計の設定を考えるときと、部分的に投票が順序付けられたより一般的な場合の両方に当てはまる。
- 参考スコア（独自算出の注目度）: 3.6603644500568806
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In its most traditional setting, the main concern of optimization theory is
the search for optimal solutions for instances of a given computational
problem. A recent trend of research in artificial intelligence, called solution
diversity, has focused on the development of notions of optimality that may be
more appropriate in settings where subjectivity is essential. The idea is that
instead of aiming at the development of algorithms that output a single optimal
solution, the goal is to investigate algorithms that output a small set of
sufficiently good solutions that are sufficiently diverse from one another. In
this way, the user has the opportunity to choose the solution that is most
appropriate to the context at hand. It also displays the richness of the
solution space.
When combined with techniques from parameterized complexity theory, the
paradigm of diversity of solutions offers a powerful algorithmic framework to
address problems of practical relevance. In this work, we investigate the
impact of this combination in the field of Kemeny Rank Aggregation, a
well-studied class of problems lying in the intersection of order theory and
social choice theory and also in the field of order theory itself. In
particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter
tractable with respect to natural parameters providing natural formalizations
of the notions of diversity and of the notion of a sufficiently good solution.
Our main results work both when considering the traditional setting of
aggregation over linearly ordered votes, and in the more general setting where
votes are partially ordered.
- Abstract（参考訳）: 最も伝統的な設定では、最適化理論の主な関心事は、与えられた計算問題のインスタンスに対する最適解の探索である。
ソリューション多様性と呼ばれる最近の人工知能研究のトレンドは、主観性が不可欠である設定においてより適切な最適性の概念の開発に焦点を当てている。
目的は、一つの最適解を出力するアルゴリズムの開発ではなく、互いに十分に多様な十分良い解の小さなセットを出力するアルゴリズムを調査することである。
このようにして、ユーザは、目の前のコンテキストに最も適したソリューションを選択することができる。
また、解空間の豊かさも示している。
パラメタライズド複雑性理論の手法と組み合わせると、ソリューションの多様性のパラダイムは、実用的な妥当性の問題に対処する強力なアルゴリズムフレームワークを提供する。
本研究では,この組み合わせが,秩序論と社会的選択論の交叉や秩序論自体の分野においてもよく研究されている問題であるケメニー・ランク・アグリゲーションの分野に与える影響を考察する。
特に、ケメニ・ランク・アグリゲーション問題は、多様性の概念と十分良い解の概念の自然な定式化を提供する自然なパラメータに関して、一定のパラメータを抽出可能であることを示す。
我々の主な成果は、線形に順序付けられた投票よりも伝統的な集計の設定を考えるときと、部分的に投票が順序付けられたより一般的な場合の両方に当てはまる。
関連論文リスト
- Learning Joint Models of Prediction and Optimization [56.04498536842065]
Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。
本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
論文 参考訳（メタデータ） (2024-09-07T19:52:14Z) - Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization [9.838618121102053]
現実世界のアプリケーションでは、ユーザーは1つの高品質なソリューションよりも構造的に多様な設計選択を好むことが多い。
本稿では, この課題に対する新たな視点として, 与えられたしきい値を超えるペア距離の一定数の解を同定する問題を考察する。
論文 参考訳（メタデータ） (2024-08-29T09:55:55Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - A machine learning framework for neighbor generation in metaheuristic
search [4.521119623956821]
メタヒューリスティック検索における近隣世代のための汎用機械学習フレームワークを提案する。
メタヒューリスティックな2つの応用法について検証する。
論文 参考訳（メタデータ） (2022-12-22T01:58:04Z) - Computing High-Quality Solutions for the Patient Admission Scheduling
Problem using Evolutionary Diversity Optimisation [10.609857097723266]
我々は、現実世界の問題、すなわち患者受け入れスケジューリングに対する進化的多様性の最適化に適応する。
本稿では,各解の品質を考慮に入れた一組の解において,構造的多様性を実現するための進化的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-28T14:26:45Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Preference learning along multiple criteria: A game-theoretic
perspective [97.94912276610002]
我々は、ブラックウェルの接近性からインスピレーションを得て、フォン・ノイマンの勝者の概念をマルチ基準設定に一般化する。
本フレームワークは,基準間の選好の非線形集約を可能にし,多目的最適化から線形化に基づくアプローチを一般化する。
凸最適化問題の解法として,マルチ基準問題インスタンスのブラックウェルの勝者が計算可能であることを示す。
論文 参考訳（メタデータ） (2021-05-05T03:23:11Z) - PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective
Optimization Problems [0.0]
提案アルゴリズムは,実モデルのモデルによって定義される一連の代理問題の解法に基づく。
また,最適化ランドスケープのための最適なサロゲートモデルとナビゲーション戦略のメタ検索を行う。
論文 参考訳（メタデータ） (2021-03-19T11:18:03Z) - Optimistic variants of single-objective bilevel optimization for
evolutionary algorithms [6.788217433800101]
ベンチマーク問題を解くために部分的部分進化的アプローチが提案され、優れた結果が得られた。
また、一般的な収束アプローチ、すなわち楽観的で悲観的なアプローチにも新しい変種が提案されている。
実験の結果、アルゴリズムは楽観的な変量を持つ最適解に異なる収束性を示す。
論文 参考訳（メタデータ） (2020-08-22T23:12:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。