論文の概要: Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness
- arxiv url: http://arxiv.org/abs/2110.10942v1
- Date: Thu, 21 Oct 2021 07:28:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-23 07:51:24.411595
- Title: Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness
- Title(参考訳): 対数ロバスト性レンズによるニューラルコンビナート解法の一般化
- Authors: Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski,
Stephan G\"unnemann
- Abstract要約: ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
- 参考スコア(独自算出の注目度): 68.97830259849086
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: End-to-end (geometric) deep learning has seen first successes in
approximating the solution of combinatorial optimization problems. However,
generating data in the realm of NP-hard/-complete tasks brings practical and
theoretical challenges, resulting in evaluation protocols that are too
optimistic. Specifically, most datasets only capture a simpler subproblem and
likely suffer from spurious features. We investigate these effects by studying
adversarial robustness - a local generalization property - to reveal hard,
model-specific instances and spurious features. For this purpose, we derive
perturbation models for SAT and TSP. Unlike in other applications, where
perturbation models are designed around subjective notions of imperceptibility,
our perturbation models are efficient and sound, allowing us to determine the
true label of perturbed samples without a solver. Surprisingly, with such
perturbations, a sufficiently expressive neural solver does not suffer from the
limitations of the accuracy-robustness trade-off common in supervised learning.
Although such robust solvers exist, we show empirically that the assessed
neural solvers do not generalize well w.r.t. small perturbations of the problem
instance.
- Abstract(参考訳): エンドツーエンド(幾何学的)深層学習は、組合せ最適化問題の解の近似に初めて成功した。
しかし、NP-hard/completeタスクの領域でデータを生成することは、実用的で理論的な課題をもたらし、楽観的すぎる評価プロトコルをもたらす。
具体的には、ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
これらの効果を,局所一般化特性である逆ロバスト性(adversarial robustness)を用いて検討し,ハードでモデル固有のインスタンスとスプリアスな特徴を明らかにする。
この目的のために,SAT と TSP の摂動モデルを導出する。
摂動モデルが主観的な知覚可能性の概念に基づいて設計されている他の応用とは異なり、摂動モデルは効率的で健全であり、解法を使わずに摂動サンプルの真のラベルを決定することができる。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
このような頑健な解法は存在するが、評価されたニューラル解法が問題インスタンスの小さな摂動をうまく一般化しないことを経験的に示している。
関連論文リスト
- Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural
Networks [89.28881869440433]
本稿では,グラフニューラルネットワーク(GNN)における結合エッジモデルスパース学習の理論的特徴について述べる。
解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
論文 参考訳(メタデータ) (2023-02-06T16:54:20Z) - Stochastic Causal Programming for Bounding Treatment Effects [8.879868078611443]
部分的識別問題に対するアルゴリズムを考察する。
本研究では,標準基準による因果モデルに符号化された制約の含意と,観測可能な証拠が一致した枠組みを考察する。
フレキシブルな学習アルゴリズムとモンテカルロ法を組み合わせて、因果プログラミングという名のソリューション群を実装します。
論文 参考訳(メタデータ) (2022-02-22T10:55:24Z) - Learning through atypical ''phase transitions'' in overparameterized
neural networks [0.43496401697112685]
現在のディープニューラルネットワークは可観測性が高く(最大数十億の接続重み)、非線形である。
しかし、過剰な降下アルゴリズムによってほぼ完全にデータに適合し、予期せぬ精度の予測を達成できる。
これらは一般化なしの恐ろしい挑戦である。
論文 参考訳(メタデータ) (2021-10-01T23:28:07Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳(メタデータ) (2021-06-28T00:38:54Z) - Identifiability-Guaranteed Simplex-Structured Post-Nonlinear Mixture
Learning via Autoencoder [9.769870656657522]
この研究は、非線形に混合された潜伏成分を教師なしの方法で解き放つ問題に焦点を当てる。
潜伏成分は確率単純度内に存在すると仮定され、未知の非線形混合系によって変換される。
この問題は、非線形ハイパースペクトルアンミックス、画像埋め込み、非線形クラスタリングなど、信号およびデータ分析における様々な応用を見出す。
論文 参考訳(メタデータ) (2021-06-16T18:20:58Z) - Non-Singular Adversarial Robustness of Neural Networks [58.731070632586594]
小さな入力摂動に対する過敏性のため、アドリヤルロバスト性はニューラルネットワークにとって新たな課題となっている。
我々は,データ入力とモデル重みの共振レンズを用いて,ニューラルネットワークの非特異な対角性の概念を定式化する。
論文 参考訳(メタデータ) (2021-02-23T20:59:30Z) - Attribute-Guided Adversarial Training for Robustness to Natural
Perturbations [64.35805267250682]
本稿では,属性空間への分類器の露出を最大化するために,新しいサンプルを生成することを学習する逆学習手法を提案する。
我々のアプローチは、ディープニューラルネットワークが自然に発生する摂動に対して堅牢であることを可能にする。
論文 参考訳(メタデータ) (2020-12-03T10:17:30Z) - Active Importance Sampling for Variational Objectives Dominated by Rare
Events: Consequences for Optimization and Generalization [12.617078020344618]
本稿では,レアイベントサンプリング手法とニューラルネットワーク最適化を組み合わせて,レアイベントに支配される目的関数を最適化する手法を提案する。
重要度サンプリングは学習問題に対する解の分散を減少させ,一般化の利点を示唆することを示す。
数値実験により,高次元データと希少データの複合化が困難である場合でも,学習を成功させることができた。
論文 参考訳(メタデータ) (2020-08-11T23:38:09Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。
テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。
以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
論文 参考訳(メタデータ) (2020-06-22T21:12:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。