論文の概要: On Size and Hardness Generalization in Unsupervised Learning for the Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2403.20212v2
• Date: Tue, 19 Nov 2024 15:23:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-20 13:34:29.910907
• Title: On Size and Hardness Generalization in Unsupervised Learning for the Travelling Salesman Problem
• Title（参考訳）: 旅行セールスマン問題における教師なし学習におけるサイズとハードネスの一般化について
• Authors: Yimeng Min, Carla P. Gomes,
• Abstract要約: 旅行セールスマン問題(TSP)における教師なし学習の一般化能力について検討する。 代理損失関数で訓練されたグラフニューラルネットワーク(GNN)を用いて各ノードに埋め込みを生成する。 次に、最終予測を生成するために局所探索を適用する。
• 参考スコア（独自算出の注目度）: 30.652280460904375
• License:
• Abstract: We study the generalization capability of Unsupervised Learning in solving the Travelling Salesman Problem (TSP). We use a Graph Neural Network (GNN) trained with a surrogate loss function to generate an embedding for each node. We use these embeddings to construct a heat map that indicates the likelihood of each edge being part of the optimal route. We then apply local search to generate our final predictions. Our investigation explores how different training instance sizes, embedding dimensions, and distributions influence the outcomes of Unsupervised Learning methods. Our results show that training with larger instance sizes and increasing embedding dimensions can build a more effective representation, enhancing the model's ability to solve TSP. Furthermore, in evaluating generalization across different distributions, we first determine the hardness of various distributions and explore how different hardnesses affect the final results. Our findings suggest that models trained on harder instances exhibit better generalization capabilities, highlighting the importance of selecting appropriate training instances in solving TSP using Unsupervised Learning.
• Abstract（参考訳）: 本研究では,トラベリングセールスマン問題(TSP)における教師なし学習の一般化能力について検討する。 代理損失関数で訓練されたグラフニューラルネットワーク(GNN)を用いて各ノードに埋め込みを生成する。 これらの埋め込みを用いて、各エッジが最適経路の一部である可能性を示すヒートマップを構築する。 次に、最終予測を生成するために局所探索を適用する。 本研究は,教師なし学習手法の結果に異なるトレーニングインスタンスサイズ,埋め込み次元,分布がどう影響するかを考察する。 以上の結果から,より大きなインスタンスサイズでのトレーニングや埋め込み次元の増大により,より効率的な表現が実現され,TSPを解くモデルの能力が向上することが示唆された。 さらに、各分布の一般化を評価する際に、まず各分布の硬さを判定し、異なる硬さが最終結果にどう影響するかを考察する。 その結果,厳密なインスタンスでトレーニングされたモデルはより優れた一般化能力を示し,教師なし学習を用いたTSP解決における適切なトレーニングインスタンスの選択の重要性が示唆された。

関連論文リスト

• Generalizing to any diverse distribution: uniformity, gentle finetuning and rebalancing [55.791818510796645]
  我々は,訓練データから大きく逸脱した場合でも,様々なテスト分布によく適応するモデルを開発することを目的としている。 ドメイン適応、ドメイン一般化、ロバスト最適化といった様々なアプローチは、アウト・オブ・ディストリビューションの課題に対処しようと試みている。 我々は、既知のドメイン内の十分に多様なテスト分布にまたがる最悪のケースエラーを考慮することで、より保守的な視点を採用する。
  論文  参考訳（メタデータ） (2024-10-08T12:26:48Z)
• Accelerating exploration and representation learning with offline pre-training [52.6912479800592]
  1つのオフラインデータセットから2つの異なるモデルを別々に学習することで、探索と表現の学習を改善することができることを示す。 ノイズコントラスト推定と補助報酬モデルを用いて状態表現を学習することで、挑戦的なNetHackベンチマークのサンプル効率を大幅に向上できることを示す。
  論文  参考訳（メタデータ） (2023-03-31T18:03:30Z)
• Modeling Uncertain Feature Representation for Domain Generalization [49.129544670700525]
  提案手法は,複数の視覚タスクにおけるネットワーク一般化能力を常に改善することを示す。 我々の手法は単純だが有効であり、トレーニング可能なパラメータや損失制約を伴わずにネットワークに容易に統合できる。
  論文  参考訳（メタデータ） (2023-01-16T14:25:02Z)
• Improved architectures and training algorithms for deep operator networks [0.0]
  演算子学習技術は無限次元バナッハ空間間の写像を学習するための強力なツールとして登場した。 我々は,ニューラルタンジェントカーネル(NTK)理論のレンズを用いて,ディープオペレータネットワーク(DeepONets)のトレーニングダイナミクスを解析した。
  論文  参考訳（メタデータ） (2021-10-04T18:34:41Z)
• Exploring Data Aggregation and Transformations to Generalize across Visual Domains [0.0]
  この論文は、ドメイン一般化(DG)、ドメイン適応(DA)およびそれらのバリエーションの研究に寄与する。 本稿では,機能集約戦略と視覚変換を利用するドメイン一般化とドメイン適応の新しいフレームワークを提案する。 提案手法が確立したDGおよびDAベンチマークにおいて,最先端の競争的アプローチよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-08-20T14:58:14Z)
• Exploring Memorization in Adversarial Training [58.38336773082818]
  本稿では, 能力, 収束, 一般化, 特に強靭なオーバーフィッティングの深い理解を促進するための, 対人訓練(AT)における記憶効果について検討する。 本稿では,詳細な記憶分析を動機とした新たな緩和アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-03T05:39:57Z)
• Linear Regression with Distributed Learning: A Generalization Error Perspective [0.0]
  大規模線形回帰のための分散学習の性能を検討する。 我々は、一般化エラー、すなわち、見当たらないデータのパフォーマンスに焦点を当てる。 その結果、分散ソリューションの一般化誤差は、集中ソリューションの一般化誤差よりも大幅に高いことが示された。
  論文  参考訳（メタデータ） (2021-01-22T08:43:28Z)
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
  本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。 ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。 実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
  論文  参考訳（メタデータ） (2020-12-19T11:06:30Z)
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization [9.176056742068813]
  トラベリングセールスパーソン問題(TSP)のようなグラフ最適化問題に対するニューラルネットワークソルバのエンドツーエンドトレーニングは近年,関心が高まっている。 最先端の学習駆動アプローチは、自明に小さなサイズで訓練された場合、古典的な解法と密接に関係するが、実践的な規模で学習ポリシーを大規模に一般化することはできない。 この研究は、トレーニングで見られるものよりも大きいインスタンスへの一般化を促進する、原則化されたバイアス、モデルアーキテクチャ、学習アルゴリズムを特定するために、最近の論文を統一するエンドツーエンドのニューラルネットワークパイプラインを提示している。
  論文  参考訳（メタデータ） (2020-06-12T10:14:15Z)
• Learning What Makes a Difference from Counterfactual Examples and Gradient Supervision [57.14468881854616]
  ニューラルネットワークの一般化能力を改善するための補助的学習目標を提案する。 我々は、異なるラベルを持つ最小差の例のペア、すなわち反ファクトまたはコントラストの例を使用し、タスクの根底にある因果構造を示す信号を与える。 このテクニックで訓練されたモデルは、配布外テストセットのパフォーマンスを向上させる。
  論文  参考訳（メタデータ） (2020-04-20T02:47:49Z)

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

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