論文の概要: Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing
- arxiv url: http://arxiv.org/abs/2301.05146v1
- Date: Thu, 12 Jan 2023 17:01:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-13 14:10:36.586636
- Title: Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing
- Title（参考訳）: 量子アニーリングに基づく多様なケメニーランクアグリゲーションのヒューリスティック
- Authors: Sven Fiergolla, Kevin Goergen, Patrick Neises, Petra Wolf
- Abstract要約: ソリューションの多様性の枠組みは、人工知能の分野で若く繁栄するトピックである。
我々は、ケメニ・ランク・アグリゲーション問題を解くために量子アニールを用いて、代表的解の集合を計算する。
KRAインスタンスが量子アニールによってどのように解けるかを説明し、実験的な評価と実装を提供する。
- 参考スコア（独自算出の注目度）: 1.0323063834827415
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Kemeny Rank Aggregation (KRA) problem is a well-studied problem in the
field of Social Choice with a variety of applications in many different areas
like databases and search engines. Intuitively, given a set of votes over a set
of candidates, the problem asks to find an aggregated ranking of candidates
that minimizes the overall dissatisfaction concerning the votes. Recently, a
diverse version of KRA was considered which asks for a sufficiently diverse set
of sufficiently good solutions. The framework of diversity of solutions is a
young and thriving topic in the field of artificial intelligence. The main idea
is to provide the user with not just one, but with a set of different
solutions, enabling her to pick a sufficiently good solution that satisfies
additional subjective criteria that are hard or impossible to model.
In this work, we use a quantum annealer to solve the KRA problem and to
compute a representative set of solutions. Quantum annealing is a meta search
heuristic that does not only show promising runtime behavior on currently
existing prototypes but also samples the solutions space in an inherently
different way, making use of quantum effects. We describe how KRA instances can
be solved by a quantum annealer and provide an implementation as well as
experimental evaluations. As existing quantum annealers are still restricted in
their number of qubits, we further implement two different data reduction rules
that can split an instance into a set of smaller instances. In our evaluation,
we compare classical heuristics that allow to sample multiple solutions such as
simulated annealing and local search with quantum annealing performed on a
physical quantum annealer. We compare runtime, quality of solution, and
diversity of solutions, with and without applying preceding data reduction
rules.
- Abstract（参考訳）: Kemeny Rank Aggregation(KRA)問題(英語版)は、データベースや検索エンジンなど、様々な分野の様々な応用で社会選択の分野でよく研究されている問題である。
直感的には、一組の候補者に対して一組の票が与えられると、問題は投票に関する全体的な不満を最小限に抑える候補者の合計ランキングを見つけることを求める。
近年、KRAの多様なバージョンが検討され、十分多様な優れた解を求めるようになった。
ソリューションの多様性の枠組みは、人工知能の分野で若くて活発なトピックである。
主なアイデアは、ユーザに対して1つだけでなく、さまざまなソリューションセットを提供することで、モデリングが困難あるいは不可能な追加の主観的基準を満たす十分な優れたソリューションを選択できるようにすることです。
本研究では,量子アニールを用いてKRA問題を解き,代表的な解の集合を計算する。
量子アニーリング(quantum annealing)はメタ検索のヒューリスティックであり、既存のプロトタイプ上で有望な実行時の振る舞いを示すだけでなく、量子効果を利用した本質的に異なる方法で解空間をサンプリングする。
KRAインスタンスが量子アニールによってどのように解けるかを説明し、実験的評価と実装を提供する。
既存の量子アニールは量子ビット数に制限されているため、インスタンスを小さなインスタンスの集合に分割できる2つの異なるデータ還元ルールをさらに実装します。
本評価では,物理量子アニーラ上で行う量子アニーラリングとシミュレーションアニーラリングや局所探索のような複数の解をサンプリングできる古典ヒューリスティックスを比較した。
先行するデータ削減ルールを適用せずに、ランタイム、ソリューションの品質、ソリューションの多様性を比較します。
関連論文リスト
- Quantum Algorithms for Drone Mission Planning [0.0]
ミッションプランニングはしばしば、一連のミッション目標を達成するためにISR(Intelligence, Surveillance and Reconnaissance)資産の使用を最適化する。
このような解を見つけることはNP-Hard問題であり、古典的なコンピュータでは効率的に解けないことが多い。
我々は、現在の古典的手法に対してスピードアップを提供する可能性のある、短期量子アルゴリズムについて検討する。
論文 参考訳（メタデータ） (2024-09-27T10:58:25Z) - Validation and benchmarking of quantum annealing technology [0.0]
この論文は、量子アニールのベンチマークと検証の問題に焦点を当てている。
実世界の問題を解くための2つのアルゴリズムを提案し、それらが現在の世代の量子アニール上でどのように機能するかをテストする。
論文 参考訳（メタデータ） (2023-12-06T14:56:45Z) - Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-26T18:23:21Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。
本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。
最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。
これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
論文 参考訳（メタデータ） (2023-10-18T17:59:45Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Multi-Label Quantification [78.83284164605473]
定量化とは、教師なしデータサンプルにおいて、興味あるクラスの相対周波数の予測子を生成する教師付き学習課題である。
本研究では,その相対頻度をより正確に予測するために,興味あるクラス間の依存関係を活用しようとするクラス有病率値の推定手法を提案する。
論文 参考訳（メタデータ） (2022-11-15T11:29:59Z) - Quantum-Assisted Greedy Algorithms [1.5049442691806054]
我々は、量子アニール(QA)を利用して、欲求アルゴリズムの候補をよりよく選択する方法を示す。
問題依存型ハミルトンの基底状態から採取したQAを低温で使用する。
論文 参考訳（メタデータ） (2022-08-03T13:09:17Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Sampling diverse near-optimal solutions via algorithmic quantum
annealing [0.3506539188356145]
主要な開問題の1つは、典型的なモンテカルロ解法に対するエルゴディディティの欠如、あるいはモード崩壊である。
本稿ではNP-hard最適化問題に対する独立近似解の数を定量化する新しい多様性尺度を提案する。
論文 参考訳（メタデータ） (2021-10-20T13:33:37Z) - Diversity metric for evaluation of quantum annealing [1.0499611180329802]
量子解法が古典的手法と比較して構成空間をいかによくサンプリングするかは分かっていない。
メタヒューリスティックス・ソルバの評価のための指標として,時間と多様性を用いる。
このことは、量子と古典的な解を組み合わせたポートフォリオソルバが全ての解法に勝っていることを示唆している。
論文 参考訳（メタデータ） (2021-10-19T18:37:01Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。