論文の概要: 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つの大きな利点は、厳密でヒューリスティックな解法とは異なり、我々の手法の実行時間は、エッジの数ではなくグラフ内のノード数でしかスケールしないことである。

関連論文リスト

• On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning [85.75164588939185]
  複数モーダルな)自己教師付き表現学習のための連続領域における識別確率モデル問題について検討する。 我々は、自己教師付き表現学習における現在のInfoNCEに基づくコントラスト損失の制限を明らかにするために一般化誤差解析を行う。
  論文  参考訳（メタデータ） (2024-10-11T18:02:46Z)
• From Maximum Cut to Maximum Independent Set [7.250073177017239]
  最大独立集合(MIS)問題も特定のイジングモデルと関係があることは以前から知られていた。 この戦略により、ランダムなエルドホス・ローニイグラフの独立数に対する近似が大幅に改善されることが判明した。 また、コーディング理論から生じるベンチマークで完全なパフォーマンスを示す。
  論文  参考訳（メタデータ） (2024-08-13T09:33:41Z)
• Efficient k-means with Individual Fairness via Exponential Tilting [13.72284501663574]
  位置に基づくリソース割り当てのシナリオでは、全てのポイントを平等に扱うという原則を達成するために、個別に公平なクラスタリングがしばしば用いられる。 本稿では,クラスタリングにおける個別の公平性を実現することを目的とした,新しいアルゴリズムである傾きk平均(TKM)を提案する。
  論文  参考訳（メタデータ） (2024-06-24T11:50:31Z)
• An Efficient Difference-of-Convex Solver for Privacy Funnel [3.069335774032178]
  本稿では,プライバシ・ファンネル(PF)手法の効率的な解法を提案する。 提案した直流分離は, クローズドフォーム更新方程式を導出する。 提案手法をMNISTおよびFashionデータセットを用いて評価する。
  論文  参考訳（メタデータ） (2024-03-02T01:05:25Z)
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers [0.0]
  我々は、Rydberg量子アニールの最適化問題を解くための非ユニットディスクフレームワークを提供する。 我々の構成は、局所制御可能な光シフトを個々の量子ビットに適用する多体相互作用Rydbergシステムからなる。 我々の数値シミュレーションでは、Rydbergアニーラーを所望の多体基底状態に大域的に駆動しながら、局所分解プロトコルを実装している。
  論文  参考訳（メタデータ） (2023-08-15T14:24:45Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Exploiting Temporal Structures of Cyclostationary Signals for Data-Driven Single-Channel Source Separation [98.95383921866096]
  単一チャネルソース分離(SCSS)の問題点について検討する。 我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。 本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
  論文  参考訳（メタデータ） (2022-08-22T14:04:56Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。 目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
  論文  参考訳（メタデータ） (2022-02-15T15:39:30Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。 提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
  論文  参考訳（メタデータ） (2020-06-17T02:19:31Z)

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

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