論文の概要: Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models

• arxiv url: http://arxiv.org/abs/2410.23934v1
• Date: Thu, 31 Oct 2024 13:48:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 17:00:49.840589
• Title: Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models
• Title（参考訳）: 階層モデルに基づく選好整合問題に対する高速アルゴリズムの実現に向けて
• Authors: Anne-Marie George, Nic Wilson, Barry O'Sullivan,
• Abstract要約: 階層モデルに基づく選好文の一貫性問題の解法として,アルゴリズム的手法を構築し,比較する。 インスタンスが一貫すると、評価関数に階層的モデルが存在し、代替関数の順序関係を誘導する。 この問題を解決するための3つのアプローチを開発する。
• 参考スコア（独自算出の注目度）: 4.007697401483925
• License:
• Abstract: In this paper, we construct and compare algorithmic approaches to solve the Preference Consistency Problem for preference statements based on hierarchical models. Instances of this problem contain a set of preference statements that are direct comparisons (strict and non-strict) between some alternatives, and a set of evaluation functions by which all alternatives can be rated. An instance is consistent based on hierarchical preference models, if there exists an hierarchical model on the evaluation functions that induces an order relation on the alternatives by which all relations given by the preference statements are satisfied. Deciding if an instance is consistent is known to be NP-complete for hierarchical models. We develop three approaches to solve this decision problem. The first involves a Mixed Integer Linear Programming (MILP) formulation, the other two are recursive algorithms that are based on properties of the problem by which the search space can be pruned. Our experiments on synthetic data show that the recursive algorithms are faster than solving the MILP formulation and that the ratio between the running times increases extremely quickly.
• Abstract（参考訳）: 本稿では,階層モデルに基づく選好文の選好一貫性問題に対するアルゴリズム的アプローチの構築と比較を行う。 この問題の事例には、いくつかの選択肢間の直接比較(制限と非制限)である選好文のセットと、すべての選択肢を評価できる評価関数のセットが含まれる。 インスタンスは階層的選好モデルに基づいて一貫したものであり、もし評価関数に階層的モデルが存在し、選好文によって与えられるすべての関係が満たされる選択肢について順序関係を誘導する。 インスタンスが一貫したかどうかを決定することは階層モデルに対してNP完全であることが知られている。 この問題を解決するための3つのアプローチを開発する。 1つはMILP(Mixed Integer Linear Programming)の定式化であり、もう2つは探索空間を刈り取ることができる問題の性質に基づく再帰的アルゴリズムである。 合成データを用いた実験により, 再帰的アルゴリズムはMILPの定式化を解くよりも高速であり, 実行時間間の比が極めて高速に増加することが示された。

関連論文リスト

• Learning Optimal Signal Temporal Logic Decision Trees for Classification: A Max-Flow MILP Formulation [5.924780594614676]
  本稿では,データから時間的時間的論理特性を推定するための新しい枠組みを提案する。 混合整数線形プログラミング最適化問題として推論過程を定式化する。 結果木に最大フローアルゴリズムを適用すると、この問題はグローバルな最適化問題に変換される。 我々は,2クラス,複数クラス,複雑な式分類シナリオを含む3つのケーススタディを実施している。
  論文  参考訳（メタデータ） (2024-07-30T16:56:21Z)
• RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
  そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。 我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。 いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
  論文  参考訳（メタデータ） (2023-11-10T13:56:15Z)
• Doubly Stochastic Matrix Models for Estimation of Distribution Algorithms [2.28438857884398]
  本稿では,自然置換問題のマッチングと割当てにDSM(Douubly Matrices)を用いる方法について検討する。 具体的には、分散アルゴリズムの推定の枠組みを採用し、DSMを置換問題に対する既存の提案と比較する。 二次代入問題の事例に関する予備実験は、この研究の行を検証し、DSMが非常に競争力のある結果が得られることを示した。
  論文  参考訳（メタデータ） (2023-04-05T14:36:48Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
  これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。 それぞれのソリューションのコストを評価するのに 費用がかかります 上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
  論文  参考訳（メタデータ） (2021-08-18T08:41:58Z)
• Learning Structure in Nested Logit Models [22.269565708490468]
  ネストロジット構造探索のための新しいデータ駆動手法を提案する。 合成データから真のネスト構造を正確に復元するアルゴリズムの能力を実証する。 Juliaプログラミング言語で記述されたカスタマイズ可能かつオープンソースなコードベースとして実装を提供しています。
  論文  参考訳（メタデータ） (2020-08-18T17:15:43Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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