論文の概要: NN-Steiner: A Mixed Neural-algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem

• arxiv url: http://arxiv.org/abs/2312.10589v1
• Date: Sun, 17 Dec 2023 02:42:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-19 15:45:36.027281
• Title: NN-Steiner: A Mixed Neural-algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem
• Title（参考訳）: NN-Steiner:rectilinear Steiner Minimum Tree問題に対する混合ニューラルネットワークアルゴリズム
• Authors: Andrew B. Kahng, Robert R. Nerem, Yusu Wang, Chien-Yi Yang
• Abstract要約: ICレイアウト設計において重要となるリチ線形スタイナー最小木(RSMT)問題に着目する。 提案するNN-Steinerは,RSMTを演算するための新しいニューラル・アルゴリズムフレームワークである。 特にNN-Steinerは、アルゴリズムフレームワーク内で繰り返し呼び出される4つのニューラルネットワーク(NN)コンポーネントのみを必要とする。
• 参考スコア（独自算出の注目度）: 5.107107601277712
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent years have witnessed rapid advances in the use of neural networks to solve combinatorial optimization problems. Nevertheless, designing the "right" neural model that can effectively handle a given optimization problem can be challenging, and often there is no theoretical understanding or justification of the resulting neural model. In this paper, we focus on the rectilinear Steiner minimum tree (RSMT) problem, which is of critical importance in IC layout design and as a result has attracted numerous heuristic approaches in the VLSI literature. Our contributions are two-fold. On the methodology front, we propose NN-Steiner, which is a novel mixed neural-algorithmic framework for computing RSMTs that leverages the celebrated PTAS algorithmic framework of Arora to solve this problem (and other geometric optimization problems). Our NN-Steiner replaces key algorithmic components within Arora's PTAS by suitable neural components. In particular, NN-Steiner only needs four neural network (NN) components that are called repeatedly within an algorithmic framework. Crucially, each of the four NN components is only of bounded size independent of input size, and thus easy to train. Furthermore, as the NN component is learning a generic algorithmic step, once learned, the resulting mixed neural-algorithmic framework generalizes to much larger instances not seen in training. Our NN-Steiner, to our best knowledge, is the first neural architecture of bounded size that has capacity to approximately solve RSMT (and variants). On the empirical front, we show how NN-Steiner can be implemented and demonstrate the effectiveness of our resulting approach, especially in terms of generalization, by comparing with state-of-the-art methods (both neural or non-neural based).
• Abstract（参考訳）: 近年、組合せ最適化の問題を解決するためにニューラルネットワークを使うことが急速に進歩している。 それでも、与えられた最適化問題を効果的に処理できる「正しい」ニューラルモデルの設計は困難であり、しばしば結果のニューラルモデルの理論的理解や正当化は存在しない。 本稿では,ICレイアウト設計において重要な問題であるリチ線形スタイナー最小木(RSMT)問題に着目し,その結果,VLSI文学において多くのヒューリスティックなアプローチを惹きつけている。 私たちの貢献は2倍です。 本稿では,この問題を解決するために,Arora の PTAS アルゴリズムフレームワークを活用した RSMT 計算のための新しい混合ニューラルネットワークアルゴリズムフレームワークである NN-Steiner を提案する。 私たちのNN-Steinerは、AroraのPTAS内の重要なアルゴリズムコンポーネントを、適切なニューラルネットワークコンポーネントで置き換えます。 特にNN-Steinerは、アルゴリズムフレームワーク内で繰り返し呼び出される4つのニューラルネットワーク(NN)コンポーネントのみを必要とする。 重要なことに、4つのNNコンポーネントはそれぞれ、入力サイズに依存しない境界サイズでしかなく、訓練が容易である。 さらに、NNコンポーネントが一般的なアルゴリズムステップを学んでいるため、一度学習されると、結果として得られる混合ニューラルネットワークアルゴリズムフレームワークは、トレーニングで見られないはるかに大きなインスタンスに一般化される。 NN-Steinerは、私たちの知る限り、RSMT(および変種)をほぼ解く能力を持つ境界サイズの最初のニューラルネットワークアーキテクチャです。 経験的観点からは、NN-Steinerがどのように実装され、特に、最先端の手法(ニューラルベースと非ニューラルベースの両方)と比較することにより、一般化の観点から、結果のアプローチの有効性を示す。

関連論文リスト

• Comparative Study of Neural Network Methods for Solving Topological Solitons [0.0]
  位相ソリトンは、非線形微分方程式の安定で局所的な解である。 我々は,ソリトンを効率的に解くためにニューラルネットワーク(NN)を用いた新しい手法を開発した。 同様のNNアプローチとして、物理情報ニューラルネットワーク(PINN)がある。
  論文  参考訳（メタデータ） (2024-11-22T13:54:52Z)
• NeuralFastLAS: Fast Logic-Based Learning from Raw Data [54.938128496934695]
  シンボリック・ルール学習者は解釈可能な解を生成するが、入力を記号的に符号化する必要がある。 ニューロシンボリックアプローチは、ニューラルネットワークを使用して生データを潜在シンボリック概念にマッピングすることで、この問題を克服する。 我々は,ニューラルネットワークを記号学習者と共同でトレーニングする,スケーラブルで高速なエンドツーエンドアプローチであるNeuralFastLASを紹介する。
  論文  参考訳（メタデータ） (2023-10-08T12:33:42Z)
• A Hybrid Neural Coding Approach for Pattern Recognition with Spiking Neural Networks [53.31941519245432]
  脳にインスパイアされたスパイクニューラルネットワーク(SNN)は、パターン認識タスクを解く上で有望な能力を示している。 これらのSNNは、情報表現に一様神経コーディングを利用する同質ニューロンに基づいている。 本研究では、SNNアーキテクチャは異種符号化方式を組み込むよう、均質に設計されるべきである、と論じる。
  論文  参考訳（メタデータ） (2023-05-26T02:52:12Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。 私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。 以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-18T13:59:02Z)
• Optimization-Informed Neural Networks [0.6853165736531939]
  制約付き非線形最適化問題を解くために最適化インフォームドニューラルネットワーク(OINN)を提案する。 簡単に言うと、OINNはCNLPをニューラルネットワークトレーニング問題に変換する。 提案手法の有効性は古典的な問題の収集を通じて実証される。
  論文  参考訳（メタデータ） (2022-10-05T09:28:55Z)
• Extrapolation and Spectral Bias of Neural Nets with Hadamard Product: a Polynomial Net Study [55.12108376616355]
  NTKの研究は典型的なニューラルネットワークアーキテクチャに特化しているが、アダマール製品(NNs-Hp)を用いたニューラルネットワークには不完全である。 本研究では,ニューラルネットワークの特別なクラスであるNNs-Hpに対する有限幅Kの定式化を導出する。 我々は,カーネル回帰予測器と関連するNTKとの等価性を証明し,NTKの適用範囲を拡大する。
  論文  参考訳（メタデータ） (2022-09-16T06:36:06Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks [54.27962244835622]
  本稿では、オーバーパラメータ化ディープニューラルネットワーク(DNN)のための新しい平均場フレームワークを提案する。 このフレームワークでは、DNNは連続的な極限におけるその特徴に対する確率測度と関数によって表現される。 本稿では、標準DNNとResidual Network(Res-Net)アーキテクチャを通してフレームワークを説明する。
  論文  参考訳（メタデータ） (2020-07-03T01:37:16Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  一般化構造方程式モデル(SEM)のクラスにおける推定について検討する。 線形作用素方程式をmin-maxゲームとして定式化し、ニューラルネットワーク(NN)でパラメータ化し、勾配勾配を用いてニューラルネットワークのパラメータを学習する。 提案手法は,サンプル分割を必要とせず,確固とした収束性を持つNNをベースとしたSEMの抽出可能な推定手順を初めて提供する。
  論文  参考訳（メタデータ） (2020-07-02T17:55:47Z)
• Artificial Neural Network Pruning to Extract Knowledge [0.0]
  本稿では,これらの問題を解決するための基本的NN単純化問題と制御プルーニング手順を列挙する。 提案手法は,各タスクに対するNNの最適構造を確認し,各入力信号とNNパラメータの影響を測定し,NNのアルゴリズムとスキルの詳細な記述を提供する。
  論文  参考訳（メタデータ） (2020-05-13T12:24:40Z)

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

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