論文の概要: Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem

• arxiv url: http://arxiv.org/abs/2209.09983v1
• Date: Tue, 20 Sep 2022 20:42:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-22 16:43:18.348511
• Title: Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem
• Title（参考訳）: Deep-Steiner: Euclidean Steiner Treeの問題を解決するための学習
• Authors: Siqi Wang, Yifan Wang, Guangmo Tong
• Abstract要約: ユークリッド・スタイナーのツリー問題は、標的位置の集合を接続するミニコストネットワークを求める。 本稿では,グラフ表現学習によって強化された強化学習を用いたユークリッドスタイナーツリー問題の解法について述べる。
• 参考スコア（独自算出の注目度）: 12.80183119319533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Euclidean Steiner tree problem seeks the min-cost network to connect a collection of target locations, and it underlies many applications of wireless networks. In this paper, we present a study on solving the Euclidean Steiner tree problem using reinforcement learning enhanced by graph representation learning. Different from the commonly studied connectivity problems like travelling salesman problem or vehicle routing problem where the search space is finite, the Euclidean Steiner tree problem requires to search over the entire Euclidean space, thereby making the existing methods not applicable. In this paper, we design discretization methods by leveraging the unique characteristics of the Steiner tree, and propose new training schemes for handling the dynamic Steiner points emerging during the incremental construction. Our design is examined through a sanity check using experiments on a collection of datasets, with encouraging results demonstrating the utility of our method as an alternative to classic combinatorial methods.
• Abstract（参考訳）: Euclidean Steiner ツリー問題では、ターゲット位置の集合体を接続するミニコストネットワークが求められ、無線ネットワークの多くの応用の基礎となっている。 本稿では,グラフ表現学習によって強化された強化学習を用いたユークリッドスタイナーツリー問題の解法について述べる。 トラベルセールスマン問題や探索空間が有限である車両ルーティング問題など、一般的に研究されている接続問題とは異なり、ユークリッドステイナーツリー問題はユークリッド空間全体を探索する必要があるため、既存の手法は適用できない。 本稿では,Steiner木の特徴を活かした離散化手法を設計し,インクリメンタルな構成中に出現する動的Steiner点を扱うための新しいトレーニング手法を提案する。 従来型組合せ法に代わる方法としての手法の有用性を実証し,データセットの集合実験を用いて健全性チェックを行い,提案手法の有効性を検証した。

関連論文リスト

• Query-decision Regression between Shortest Path and Minimum Steiner Tree [20.092639310758145]
  本稿では,最短経路問題とSteiner木問題に焦点をあてる。 我々は、スコアリングモデルを構築するための実現可能な仮説空間の設計に関する理論的知見を提供する。 実験により,そのような問題を統計的に有意な程度に解決できることが示唆された。
  論文  参考訳（メタデータ） (2024-02-03T17:05:01Z)
• 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)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  ニューラルネットワークモデルは、Kolmogorov複雑性を使って形式化された、同じ好みを共有している、と我々は主張する。 実験の結果、事前訓練された言語モデルでも、低複雑さのシーケンスを生成するのが好まれることがわかった。 これらの観察は、ますます小さな機械学習モデルで異なるように見える問題を統一する深層学習の傾向を正当化する。
  論文  参考訳（メタデータ） (2023-04-11T17:22:22Z)
• Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
  ノードの集合が与えられるグラフ上のスタイナー木問題を考える。 目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
  論文  参考訳（メタデータ） (2022-08-25T10:31:00Z)
• Neural Bregman Divergences for Distance Learning [60.375385370556145]
  本稿では,入力凸ニューラルネットワークを用いて任意のブレグマン分岐を微分可能な方法で学習するための新しいアプローチを提案する。 提案手法は,新しいタスクと以前に研究されたタスクのセットにおいて,より忠実に相違点を学習することを示す。 我々のテストはさらに、既知の非対称なタスクにまで拡張するが、Bregmanでないタスクでは、不特定性にもかかわらず、我々のメソッドは競争的に機能する。
  論文  参考訳（メタデータ） (2022-06-09T20:53:15Z)
• Boosting Graph Search with Attention Network for Solving the General Orienteering Problem [7.0786689796236155]
  本稿では,ビームサーチと学習アルゴリズムを組み合わせたオリエンテーリング問題の解法を提案する。 我々は,ノード間の距離を入力とするアテンションネットワークを用いてアルゴリズムを取得し,強化学習フレームワークを用いて学習する。 提案手法は,幅広いベースラインを超えることができ,最適あるいは高度に専門化されたアプローチに近い結果が得られる。
  論文  参考訳（メタデータ） (2021-09-10T08:23:19Z)
• Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
  本稿では,スタイナーツリー問題に取り組む。 低コストのSteiner木を計算するために4つの学習フレームワークを使用します。 我々の発見は,従来の2-近似アルゴリズムよりもGNN手法のアウト・オブ・ボックス適用の方が悪いことを示唆している。
  論文  参考訳（メタデータ） (2021-08-18T19:55:16Z)
• Probabilistic DAG Search [29.47649645431227]
  探索空間の潜伏構造を利用して探索木間で情報を共有するための確率的フレームワークを開発する。 我々は、Tic-Tac-Toeの既存の非確率的代替品と特徴選択アプリケーションとを比較検討するアルゴリズムを実証的に見出した。
  論文  参考訳（メタデータ） (2021-06-16T11:35:19Z)
• Fusing the Old with the New: Learning Relative Camera Pose with Geometry-Guided Uncertainty [91.0564497403256]
  本稿では,ネットワークトレーニング中の2つの予測系間の確率的融合を含む新しい枠組みを提案する。 本ネットワークは,異なる対応間の強い相互作用を強制することにより学習を駆動する自己追跡グラフニューラルネットワークを特徴とする。 学習に適したモーションパーマリゼーションを提案し、難易度の高いDeMoNおよびScanNetデータセットで最新のパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-04-16T17:59:06Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)
• Solving Sparse Linear Inverse Problems in Communication Systems: A Deep Learning Approach With Adaptive Depth [51.40441097625201]
  疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。 提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
  論文  参考訳（メタデータ） (2020-10-29T06:32:53Z)

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

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