論文の概要: Generalization of Machine Learning for Problem Reduction: A Case Study
on Travelling Salesman Problems
- arxiv url: http://arxiv.org/abs/2005.05847v2
- Date: Tue, 8 Sep 2020 03:13:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 18:23:17.780729
- Title: Generalization of Machine Learning for Problem Reduction: A Case Study
on Travelling Salesman Problems
- Title（参考訳）: 問題解決のための機械学習の一般化:旅行セールスマン問題の事例研究
- Authors: Yuan Sun, Andreas Ernst, Xiaodong Li and Jake Weiner
- Abstract要約: 機械学習モデルでは、最適解の一部ではないと予測される最適化問題から決定変数を強引に除去できることを示す。
1) 問題の特徴,2) 問題のサイズ,3) 問題タイプ。
未使用変数の予測精度は、テストインスタンスがトレーニングセットからさらに離れているため、自然に劣化するが、異なるTSP問題でテストしても、機械学習モデルは有用な予測を行う。
- 参考スコア（独自算出の注目度）: 5.370742369840518
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial optimization plays an important role in real-world problem
solving. In the big data era, the dimensionality of a combinatorial
optimization problem is usually very large, which poses a significant challenge
to existing solution methods. In this paper, we examine the generalization
capability of a machine learning model for problem reduction on the classic
travelling salesman problems (TSP). We demonstrate that our method can greedily
remove decision variables from an optimization problem that are predicted not
to be part of an optimal solution. More specifically, we investigate our
model's capability to generalize on test instances that have not been seen
during the training phase. We consider three scenarios where training and test
instances are different in terms of: 1) problem characteristics; 2) problem
sizes; and 3) problem types. Our experiments show that this machine learning
based technique can generalize reasonably well over a wide range of TSP test
instances with different characteristics or sizes. While the accuracy of
predicting unused variables naturally deteriorates as a test instance is
further away from the training set, we observe that even when tested on a
different TSP problem variant, the machine learning model still makes useful
predictions about which variables can be eliminated without significantly
impacting solution quality.
- Abstract（参考訳）: 組合せ最適化は現実世界の問題解決において重要な役割を果たす。
ビッグデータ時代において、組合せ最適化問題の次元性は、通常非常に大きく、既存の解法にとって大きな課題となる。
本稿では,古典的旅行セールスマン問題(TSP)における問題解決のための機械学習モデルの一般化能力について検討する。
提案手法は最適解の一部ではないと予測される最適化問題から決定変数をゆるやかに除去できることを実証する。
具体的には,トレーニング段階では見られなかったテストインスタンスを一般化するモデルの能力について検討する。
トレーニングとテストのインスタンスが異なる3つのシナリオを考えます。
1) 問題の特徴
2)問題のサイズ,及び
3)問題の種類。
実験の結果,この機械学習に基づく手法は,異なる特性やサイズを持つ幅広いTSPテストインスタンスに対して,合理的に一般化可能であることがわかった。
未使用変数の予測精度は、テストインスタンスがトレーニングセットからさらに離れているため、自然に劣化するが、異なるTSP問題変種でテストしても、機械学習モデルは、ソリューションの品質に大きな影響を及ぼすことなく、どの変数を排除できるかを有用な予測を行う。
関連論文リスト
- Neural Collapse Terminus: A Unified Solution for Class Incremental
Learning and Its Variants [166.916517335816]
本稿では,3つの課題における不整合ジレンマに対する統一解を提案する。
ラベル空間全体の最大等角的クラス間分離を有する固定構造である神経崩壊終端を提案する。
本手法は,データ不均衡やデータ不足にかかわらず,神経崩壊最適度を漸進的に保持する。
論文 参考訳（メタデータ） (2023-08-03T13:09:59Z) - A Novel Plug-and-Play Approach for Adversarially Robust Generalization [38.72514422694518]
本稿では,MLモデルを摂動テストデータから保護するために,逆向きに堅牢なトレーニングを採用する頑健なフレームワークを提案する。
私たちの貢献は、計算学と統計学の両方の観点から見ることができます。
論文 参考訳（メタデータ） (2022-08-19T17:02:55Z) - Ensemble Methods for Robust Support Vector Machines using Integer
Programming [0.0]
我々は、トレーニングデータが不確実性にさらされていると仮定する二項分類問題について検討する。
この問題を解決するために、堅牢な機械学習の分野では、トレーニングデータの小さな摂動に対して堅牢なモデルを開発することが目的である。
論文 参考訳（メタデータ） (2022-03-03T10:03:54Z) - CMW-Net: Learning a Class-Aware Sample Weighting Mapping for Robust Deep
Learning [55.733193075728096]
現代のディープニューラルネットワークは、破損したラベルやクラス不均衡を含むバイアス付きトレーニングデータに容易に適合する。
サンプル再重み付け手法は、このデータバイアス問題を緩和するために一般的に使用されている。
本稿では,データから直接明示的な重み付け方式を適応的に学習できるメタモデルを提案する。
論文 参考訳（メタデータ） (2022-02-11T13:49:51Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文 参考訳（メタデータ） (2021-10-21T07:28:11Z) - Characterizing possible failure modes in physics-informed neural
networks [55.83255669840384]
科学機械学習における最近の研究は、いわゆる物理情報ニューラルネットワーク(PINN)モデルを開発した。
既存のPINN方法論は比較的自明な問題に対して優れたモデルを学ぶことができるが、単純なPDEであっても、関連する物理現象を学習するのに失敗する可能性があることを実証する。
これらの障害モードは,NNアーキテクチャの表現力の欠如によるものではなく,PINNのセットアップによって損失状況の最適化が極めて困難であることを示す。
論文 参考訳（メタデータ） (2021-09-02T16:06:45Z) - Learning Hard Optimization Problems: A Data Generation Perspective [44.4747903763245]
本稿では,トレーニングデータのボラティリティと,それを近似する能力について述べる。
そこで本研究では,教師付きタスクに対処可能な最適化問題に対して,(実際にあるいは近似的に)解を生成(生成)する方法を提案する。
論文 参考訳（メタデータ） (2021-06-04T17:03:44Z) - How to effectively use machine learning models to predict the solutions
for optimization problems: lessons from loss function [0.0]
本稿では,高度な機械学習手法を用いた制約最適化問題に対する良質な解の予測を目的とする。
citeabbasi 2020predictingの仕事を拡張し、大規模最適化モデルのソリューションを予測するために機械学習モデルを使用する。
論文 参考訳（メタデータ） (2021-05-14T02:14:00Z) - Automatically Learning Compact Quality-aware Surrogates for Optimization
Problems [55.94450542785096]
未知パラメータで最適化問題を解くには、未知パラメータの値を予測し、これらの値を用いて問題を解くための予測モデルを学ぶ必要がある。
最近の研究によると、複雑なトレーニングモデルパイプラインのレイヤーとして最適化の問題を含めると、観測されていない意思決定の繰り返しを予測することになる。
我々は,大規模最適化問題の低次元サロゲートモデルを学習することにより,解の質を向上させることができることを示す。
論文 参考訳（メタデータ） (2020-06-18T19:11:54Z) - Total Deep Variation for Linear Inverse Problems [71.90933869570914]
本稿では,近年のアーキテクチャ設計パターンを深層学習から活用する,学習可能な汎用正規化手法を提案する。
本稿では,古典的画像復元と医用画像再構成問題に対する最先端の性能について述べる。
論文 参考訳（メタデータ） (2020-01-14T19:01:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。