論文の概要: Hybrid Learning with New Value Function for the Maximum Common Subgraph Problem

• arxiv url: http://arxiv.org/abs/2208.08620v1
• Date: Thu, 18 Aug 2022 03:43:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-19 13:35:55.607785
• Title: Hybrid Learning with New Value Function for the Maximum Common Subgraph Problem
• Title（参考訳）: 最大共通グラフ問題に対する新しい値関数を用いたハイブリッド学習
• Authors: Yanli Liu, Jiming Zhao, Chu-Min Li, Hua Jiang, Kun He
• Abstract要約: ブランチ・アンド・バウンド(BnB)は、最大共通誘導部分グラフ(MCS)のための効率的なアルゴリズムのクラスの基礎である MCSのための新しいBnBアルゴリズムであるMcSplitDALを定義するために、強化学習に使用される新しい値関数とハイブリッド選択戦略を提案する。
• 参考スコア（独自算出の注目度）: 17.08436177950109
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Maximum Common induced Subgraph (MCS) is an important NP-hard problem with wide real-world applications. Branch-and-Bound (BnB) is the basis of a class of efficient algorithms for MCS, consisting in successively selecting vertices to match and pruning when it is discovered that a solution better than the best solution found so far does not exist. The method of selecting the vertices to match is essential for the performance of BnB. In this paper, we propose a new value function and a hybrid selection strategy used in reinforcement learning to define a new vertex selection method, and propose a new BnB algorithm, called McSplitDAL, for MCS. Extensive experiments show that McSplitDAL significantly improves the current best BnB algorithms, McSplit+LL and McSplit+RL. An empirical analysis is also performed to illustrate why the new value function and the hybrid selection strategy are effective.
• Abstract（参考訳）: Maximum Common induced Subgraph (MCS) は、幅広い現実世界の応用において重要なNPハード問題である。 ブランチ・アンド・バウンド(bnb)はmcsの効率的なアルゴリズムのクラスの基礎であり、これまでに見いだされた最良の解よりも優れた解が存在しないことを発見したとき、マッチングとpruningのための頂点を連続的に選択する。 マッチングする頂点を選択する方法はBnBの性能に不可欠である。 本稿では,新しい頂点選択法を定義するために強化学習に使用される新しい値関数とハイブリッド選択戦略を提案し,mcsのための新しいbnbアルゴリズムであるmcsplitdalを提案する。 大規模な実験により、McSplitDALは現在の最高のBnBアルゴリズムであるMcSplit+LLとMcSplit+RLを大幅に改善した。 また、新しい値関数とハイブリッド選択戦略が有効である理由を説明するための実証分析を行った。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。 これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。 我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
  論文  参考訳（メタデータ） (2024-07-22T23:24:03Z)
• 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)
• An Efficient High-Dimensional Gene Selection Approach based on Binary Horse Herd Optimization Algorithm for Biological Data Classification [1.1510009152620668]
  Horse Herd Optimization Algorithm (HOA)は、異なる年齢の馬の行動に基づく新しいメタヒューリスティックアルゴリズムである。 本稿では、離散的な問題を解くためにHOAのバイナリバージョンを提案し、特徴部分集合を選択する。 提案手法 (MRMR-BHOA) は, 精度, 最小選択特性において優れた性能を示す。
  論文  参考訳（メタデータ） (2023-08-18T19:40:59Z)
• A Comprehensively Improved Hybrid Algorithm for Learning Bayesian Networks: Multiple Compound Memory Erasing [0.0]
  本稿では、新しいハイブリッドアルゴリズムMCME(multiple compound memory erasing)を提案する。 MCMEは、最初の2つの手法の利点を維持し、上記のCIテストの欠点を解消し、方向判別段階におけるスコアリング機能に革新をもたらす。 多くの実験により、MCMEは既存のアルゴリズムよりも優れた、あるいは類似した性能を示している。
  論文  参考訳（メタデータ） (2022-12-05T12:52:07Z)
• Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
  本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。 本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。 可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
  論文  参考訳（メタデータ） (2021-07-02T06:46:23Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Stepwise Model Selection for Sequence Prediction via Deep Kernel Learning [100.83444258562263]
  本稿では,モデル選択の課題を解決するために,新しいベイズ最適化(BO)アルゴリズムを提案する。 結果として得られる複数のブラックボックス関数の最適化問題を協調的かつ効率的に解くために,ブラックボックス関数間の潜在的な相関を利用する。 我々は、シーケンス予測のための段階的モデル選択(SMS)の問題を初めて定式化し、この目的のために効率的な共同学習アルゴリズムを設計し、実証する。
  論文  参考訳（メタデータ） (2020-01-12T09:42:19Z)

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

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