論文の概要: Dataless Quadratic Neural Networks for the Maximum Independent Set Problem
- arxiv url: http://arxiv.org/abs/2406.19532v1
- Date: Thu, 27 Jun 2024 21:12:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-01 18:31:50.624187
- Title: Dataless Quadratic Neural Networks for the Maximum Independent Set Problem
- Title（参考訳）: 最大独立集合問題に対するデータレス2次ニューラルネットワーク
- Authors: Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu, Rongrong Wang, Alvaro Velasquez,
- Abstract要約: 本稿では、最大独立集合(MIS)問題に対する連続的な二次緩和を特徴とする、新しいデータレス2次ニューラルネットワークの定式化を提案する。
本手法では,MISインスタンスをトレーニング可能なエンティティとして扱うことにより,トレーニングデータの必要性を解消する。
ADAMのような勾配に基づく最適化を採用し、市販のGPU並列実装を効果的に活用することにより、我々の手法は最先端の学習ベース手法と比較して、競争力や優れた性能を示す。
- 参考スコア（独自算出の注目度）: 23.643727259409744
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial Optimization (CO) plays a crucial role in addressing various significant problems, among them the challenging Maximum Independent Set (MIS) problem. In light of recent advancements in deep learning methods, efforts have been directed towards leveraging data-driven learning approaches, typically rooted in supervised learning and reinforcement learning, to tackle the NP-hard MIS problem. However, these approaches rely on labeled datasets, exhibit weak generalization, and often depend on problem-specific heuristics. Recently, ReLU-based dataless neural networks were introduced to address combinatorial optimization problems. This paper introduces a novel dataless quadratic neural network formulation, featuring a continuous quadratic relaxation for the MIS problem. Notably, our method eliminates the need for training data by treating the given MIS instance as a trainable entity. More specifically, the graph structure and constraints of the MIS instance are used to define the structure and parameters of the neural network such that training it on a fixed input provides a solution to the problem, thereby setting it apart from traditional supervised or reinforcement learning approaches. By employing a gradient-based optimization algorithm like ADAM and leveraging an efficient off-the-shelf GPU parallel implementation, our straightforward yet effective approach demonstrates competitive or superior performance compared to state-of-the-art learning-based methods. Another significant advantage of our approach is that, unlike exact and heuristic solvers, the running time of our method scales only with the number of nodes in the graph, not the number of edges.
- Abstract（参考訳）: 組合せ最適化(CO)は、様々な重要な問題に対処する上で重要な役割を担っている。
近年の深層学習手法の進歩を踏まえ、NP-hard MIS問題に対処するために、教師付き学習と強化学習に根ざしたデータ駆動学習アプローチの活用に向けた取り組みが進められている。
しかしながら、これらのアプローチはラベル付きデータセットに依存し、弱い一般化を示し、しばしば問題固有のヒューリスティックに依存している。
近年、組合せ最適化問題に対処するために、ReLUベースのデータレスニューラルネットワークが導入された。
本稿では,MIS問題に対する連続的な2次緩和を特徴とする,データレス2次ニューラルネットワークの新たな定式化を提案する。
特に,MISインスタンスをトレーニング可能なエンティティとして扱うことにより,トレーニングデータの必要性を解消する。
より具体的には、MISインスタンスのグラフ構造と制約を使用して、ニューラルネットワークの構造とパラメータを定義し、固定入力でトレーニングすることで問題に対する解決策を提供する。
ADAMのような勾配に基づく最適化アルゴリズムを採用し、効率の良いオフザヘルフGPU並列実装を活用することで、直感的かつ効果的なアプローチは、最先端の学習ベース手法と比較して、競争力や優れたパフォーマンスを示す。
このアプローチのもう1つの大きな利点は、厳密でヒューリスティックな解法とは異なり、我々の手法の実行時間は、エッジの数ではなくグラフ内のノード数でしかスケールしないことである。
関連論文リスト
- CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
本稿では,CHARME という名前の小さな埋め込み問題に対処するために,強化学習(RL)技術を利用した新しい手法を提案する。
CHARMEには、ポリシーモデリングのためのグラフニューラルネットワーク(GNN)アーキテクチャ、ソリューションの有効性を保証する状態遷移アルゴリズム、効果的なトレーニングのための順序探索戦略の3つの重要なコンポーネントが含まれている。
詳細では、CHARME は Minorminer や ATOM のような高速な埋め込み法に比べて優れた解が得られる。
論文 参考訳（メタデータ） (2024-06-11T10:12:10Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical
Computation Offloading [62.34538208323411]
共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。
MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
論文 参考訳（メタデータ） (2023-09-02T11:01:16Z) - Unsupervised Learning for Combinatorial Optimization with Principled
Objective Relaxation [19.582494782591386]
本研究は,最適化(CO)問題に対する教師なし学習フレームワークを提案する。
我々の重要な貢献は、緩和された目的がエントリーワイドな凹凸を満たすならば、低い最適化損失は最終積分解の品質を保証するという観察である。
特に、この観察は、対象が明示的に与えられていないアプリケーションにおいて、事前にモデル化される必要がある場合に、対象モデルの設計を導くことができる。
論文 参考訳（メタデータ） (2022-07-13T06:44:17Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳（メタデータ） (2022-03-15T19:21:31Z) - Deep Efficient Continuous Manifold Learning for Time Series Modeling [11.876985348588477]
対称正定値行列はコンピュータビジョン、信号処理、医療画像解析において研究されている。
本稿では,リーマン多様体とコレスキー空間の間の微分同相写像を利用する枠組みを提案する。
時系列データの動的モデリングのために,多様体常微分方程式とゲートリカレントニューラルネットワークを体系的に統合した連続多様体学習法を提案する。
論文 参考訳（メタデータ） (2021-12-03T01:38:38Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳（メタデータ） (2021-07-08T18:01:02Z) - Decentralized Personalized Federated Learning for Min-Max Problems [79.61785798152529]
本稿では,より広い範囲の最適化問題を含むサドル点問題に対して,PFLを初めて検討した。
この問題に対処するための新しいアルゴリズムを提案し、滑らかな(強く)凸-(強く)凹点問題を理論的に解析する。
両線形問題に対する数値実験と, 対向雑音を有するニューラルネットワークは, 提案手法の有効性を実証する。
論文 参考訳（メタデータ） (2021-06-14T10:36:25Z) - Unsupervised Learning for Robust Fitting:A Reinforcement Learning
Approach [25.851792661168698]
堅牢なモデルフィッティングを解決するための新しいフレームワークを紹介します。
他の方法とは異なり、私たちの仕事は基本的な入力機能に無知です。
実験により,本手法が既存の学習手法より優れていることを示す。
論文 参考訳（メタデータ） (2021-03-05T07:14:00Z) - Differentiable Causal Discovery from Interventional Data [141.41931444927184]
本稿では、介入データを活用可能なニューラルネットワークに基づく理論的基盤化手法を提案する。
提案手法は,様々な環境下での美術品の状態と良好に比較できることを示す。
論文 参考訳（メタデータ） (2020-07-03T15:19:17Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳（メタデータ） (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。