論文の概要: MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning to Sparsify

• arxiv url: http://arxiv.org/abs/2403.02482v1
• Date: Mon, 4 Mar 2024 21:04:54 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-06 16:59:36.933426
• Title: MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning to Sparsify
• Title（参考訳）: MORBDD: スパーシフィケーションの学習による多目的限定2値決定図
• Authors: Rahul Patel, Elias B. Khalil, David Bergman
• Abstract要約: まず、問題に対するすべての実行可能なソリューションを表すグラフを構築するバイナリ意思決定図(BDD)に注目します。 機械学習(ML)を用いて、制限されたBDDが多目的最適化にどのように適応できるかを検討する。 MorBDDは、非常に小さな制限されたBDDを、優れた近似品質で、幅制限の制限されたBDDよりも優れ、よく知られた進化的アルゴリズムNSGA-IIを作るのに非常に効果的です。
• 参考スコア（独自算出の注目度）: 19.821484909092913
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In multicriteria decision-making, a user seeks a set of non-dominated solutions to a (constrained) multiobjective optimization problem, the so-called Pareto frontier. In this work, we seek to bring a state-of-the-art method for exact multiobjective integer linear programming into the heuristic realm. We focus on binary decision diagrams (BDDs) which first construct a graph that represents all feasible solutions to the problem and then traverse the graph to extract the Pareto frontier. Because the Pareto frontier may be exponentially large, enumerating it over the BDD can be time-consuming. We explore how restricted BDDs, which have already been shown to be effective as heuristics for single-objective problems, can be adapted to multiobjective optimization through the use of machine learning (ML). MORBDD, our ML-based BDD sparsifier, first trains a binary classifier to eliminate BDD nodes that are unlikely to contribute to Pareto solutions, then post-processes the sparse BDD to ensure its connectivity via optimization. Experimental results on multiobjective knapsack problems show that MORBDD is highly effective at producing very small restricted BDDs with excellent approximation quality, outperforming width-limited restricted BDDs and the well-known evolutionary algorithm NSGA-II.
• Abstract（参考訳）: 多目的意思決定において、ユーザは(制約された)多目的最適化問題(pareto frontier)に対する非支配的な解の集合を求める。 本研究では,完全多目的整数線形プログラミングの最先端手法をヒューリスティック領域に導入することを目的とする。 まず、問題に対するすべての実現可能な解決策を表すグラフを構築し、次にグラフをトラバースしてparetoのフロンティアを抽出する。 Paretoフロンティアは指数関数的に大きいため、BDD上でそれを列挙するのは時間を要する可能性がある。 単目的問題に対するヒューリスティックとしてすでに有効であることが示されている制限されたBDDが、機械学習(ML)を使用して多目的最適化にどのように適応できるかを考察する。 MLベースのBDDスペーサーであるMORBDDは、まずバイナリ分類器をトレーニングして、ParetoソリューションにコントリビュートしそうもないBDDノードを排除します。 多目的クナップサック問題に対する実験結果から、MORBDDは、近似品質に優れた、幅制限の制限されたBDDとよく知られた進化アルゴリズムNSGA-IIの非常に小さな制限されたBDDを生成するのに非常に効果的であることが示された。

関連論文リスト

• Balancing Pareto Front exploration of Non-dominated Tournament Genetic Algorithm (B-NTGA) in solving multi-objective NP-hard problems with constraints [0.0]
  提案手法をB-NTGA(B-NTGA)に適用した新しい平衡選択演算子を提案する。 提案したB-NTGAは,Thief Traveling ProblemやMulti-Skill Resource-Constrained Project Scheduling Problemのような,多目的および多目的の現実世界の2つのベンチマークで検討した。 実験の結果,B-NTGAは最先端手法よりも効率が高く,性能も優れていた。
  論文  参考訳（メタデータ） (2024-10-08T05:34:13Z)
• Dataset Distillation from First Principles: Integrating Core Information Extraction and Purposeful Learning [10.116674195405126]
  我々は、基礎となる最適化問題の正確な特徴付けは、関心の応用に関連する推論タスクを指定しなければならないと論じる。 我々の形式化は、様々なモデリング環境にまたがるDDの新たな応用を明らかにします。 現代の環境において重要な2つのケーススタディについて数値的な結果を示す。
  論文  参考訳（メタデータ） (2024-09-02T18:11:15Z)
• Towards Efficient Pareto Set Approximation via Mixture of Experts Based Model Fusion [53.33473557562837]
  大規模深層ニューラルネットワークに対する多目的最適化問題を解くことは、損失ランドスケープの複雑さと高価な計算コストのために難しい課題である。 本稿では,専門家(MoE)をベースとしたモデル融合を用いて,この問題を実用的でスケーラブルに解決する手法を提案する。 特殊な単一タスクモデルの重みをまとめることで、MoEモジュールは複数の目的間のトレードオフを効果的に捉えることができる。
  論文  参考訳（メタデータ） (2024-06-14T07:16:18Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• Double-Bounded Optimal Transport for Advanced Clustering and Classification [58.237576976486544]
  本稿では,2つの境界内での目標分布の制限を前提としたDB-OT(Douubly bounded Optimal Transport)を提案する。 提案手法は,テスト段階における改良された推論方式により,良好な結果が得られることを示す。
  論文  参考訳（メタデータ） (2024-01-21T07:43:01Z)
• Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
  我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。 我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
  論文  参考訳（メタデータ） (2023-07-05T13:52:10Z)
• Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features [5.663538370244174]
  本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。 提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
  論文  参考訳（メタデータ） (2022-06-23T17:19:29Z)
• Meta-Learning Adversarial Bandits [49.094361442409785]
  本研究の目的は,複数のタスクにまたがる帯域幅フィードバックを用いてオンライン学習を学習し,タスク間の平均性能を改善することである。 敵対的設定を最初に対象とするメタアルゴリズムとして,マルチアーム・バンディット(MAB)とバンディット・最適化(BLO)の2つの重要なケースに対して,特定の保証を設定するメタアルゴリズムを設計する。 我々の保証は、非正規化されたフォローザリーダーと乗法重みを組み合わせることで、オンラインで非滑らかで非Bシーケンスを学ぶのに十分であることを示すことに依存しています。
  論文  参考訳（メタデータ） (2022-05-27T17:40:32Z)
• Optimizing Binary Decision Diagrams with MaxSAT for classification [3.2894524838755608]
  説明可能な人工知能への関心の高まりは、解釈可能な機械学習(ML)モデルの必要性を動機付けている。 近年、従来の手法の弱点を克服するために、そのようなモデルを計算するためのいくつかの正確な方法が提案されている。 本稿ではまず,最適なバイナリ決定図(BDD)を学習するためのSATモデルを提案する。 次に、符号化をMaxSATモデルに上げ、限られた深さで最適なBDDを学習します。 最後に、MaxSATモデルを介して見つけたBDDの互換性のあるサブツリーをマージする手法を導入することにより、フラグメンテーションの問題に取り組む。
  論文  参考訳（メタデータ） (2022-03-21T23:17:37Z)
• Improving the filtering of Branch-And-Bound MDD solver (extended) [11.728147523456702]
  本稿では,多値決定図(MDD)に基づく制約最適化解法の効率向上のための2つのプルーニング手法を提案し,評価する。 Bergmanらによって提案されたブランチ・アンド・バウンド・フレームワークを採用している。 2016年、動的プログラムを最適に解く。
  論文  参考訳（メタデータ） (2021-04-24T13:42:42Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)

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

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