論文の概要: Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
- arxiv url: http://arxiv.org/abs/2005.14105v3
- Date: Thu, 11 Jul 2024 09:39:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-16 06:11:12.061140
- Title: Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
- Title（参考訳）: 境界サイズのニューラルネットワークによるクナプサック問題の解法
- Authors: Christoph Hertrich, Martin Skutella,
- Abstract要約: 古典的なNP-hard Knapsack問題(NP-hard Knapsack problem)の例として,ニューラルネットワークの表現力について検討する。
最適クナプサック解を求めるには、最適クナプサック解の利益に依存する深さ4と幅のRNNが十分である。
- 参考スコア（独自算出の注目度）: 6.959718867617964
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neural networks through the example of the classical NP-hard Knapsack Problem. Our main contribution is a class of recurrent neural networks (RNNs) with rectified linear units that are iteratively applied to each item of a Knapsack instance and thereby compute optimal or provably good solution values. We show that an RNN of depth four and width depending quadratically on the profit of an optimum Knapsack solution is sufficient to find optimum Knapsack solutions. We also prove the following tradeoff between the size of an RNN and the quality of the computed Knapsack solution: for Knapsack instances consisting of $n$ items, an RNN of depth five and width $w$ computes a solution of value at least $1-\mathcal{O}(n^2/\sqrt{w})$ times the optimum solution value. Our results build upon a classical dynamic programming formulation of the Knapsack Problem as well as a careful rounding of profit values that are also at the core of the well-known fully polynomial-time approximation scheme for the Knapsack Problem. A carefully conducted computational study qualitatively supports our theoretical size bounds. Finally, we point out that our results can be generalized to many other combinatorial optimization problems that admit dynamic programming solution methods, such as various Shortest Path Problems, the Longest Common Subsequence Problem, and the Traveling Salesperson Problem.
- Abstract（参考訳）: ニューラルネットワークの性能に関する満足度と厳密な数学的理解の開発は、人工知能の大きな課題である。
そこで本研究では,従来のNP-hard Knapsack問題(NP-hard Knapsack problem)を例に,ニューラルネットワークの表現力について検討する。
我々の主な貢献は、Knapsackインスタンスの各項目に反復的に適用される整列線形ユニットを持つリカレントニューラルネットワーク(RNN)のクラスであり、それによって最適または証明可能な優れた解値を計算する。
最適クナプサック解を求めるには, 最適クナプサック解の利得に依存する深さ4, 幅のRNNが十分であることを示す。
また、RNNのサイズと計算されたKnapsackソリューションの品質のトレードオフも証明する:$n$アイテム、深さ5のRNN、幅$w$からなるKnapsackインスタンスは、少なくとも1-\mathcal{O}(n^2/\sqrt{w})の値の解を計算する。
この結果は、クナップサック問題における古典的動的プログラミングの定式化と、クナップサック問題に対する多項式時間近似スキームの中核である利益値の慎重なラウンド化に基づいて構築される。
慎重に計算された研究は、理論的なサイズ境界を定性的に支持する。
最後に, 様々な最短経路問題, 長期共通列問題, トラベリングセールスパーソン問題など, 動的プログラミング解法を許容する多くの組合せ最適化問題に対して, 結果の一般化が可能であることを指摘する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Approximating Solutions to the Knapsack Problem using the Lagrangian
Dual Framework [0.0]
ラグランジアンデュアルフレームワークを用いて,クナプサック問題の解を近似するニューラルネットワークモデルを開発した。
我々は,ベースラインニューラルネットワークと比較して,最適性をわずかに低減した強い制約満足度を示す。
論文 参考訳（メタデータ） (2023-12-06T10:50:27Z) - 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) - Approximately Optimal Core Shapes for Tensor Decompositions [7.1439425093981574]
我々は,高次特異値への接続による再構成誤差の証明可能な近似保証付きアルゴリズムを提案する。
具体的には、NPハードであることが証明された新しいタッカーパッキング問題を導入し、マトロイドを用いた2次元クナップサック問題への還元に基づく制約時間近似スキームを提案する。
論文 参考訳（メタデータ） (2023-02-08T05:24:01Z) - A deep learning method for solving stochastic optimal control problems driven by fully-coupled FBSDEs [1.0703175070560689]
最初にこの問題をStackelberg微分ゲーム問題(リーダー-フォロワー問題)に変換する。
ユーティリティーモデルによる投資消費問題の2つの例を計算した。
その結果,提案手法の有効性が示された。
論文 参考訳（メタデータ） (2022-04-12T13:31:19Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem [0.0]
D-Wave 2000Q adiabatic quantum computer to solve the integer-weight knapsack problem。
断熱的量子最適化では、knapsackの最適充填に対応する解が得られない。
論文 参考訳（メタデータ） (2020-08-17T16:29:34Z) - Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。
ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
論文 参考訳（メタデータ） (2020-07-07T17:03:02Z) - Specific Single- and Multi-Objective Evolutionary Algorithms for the
Chance-Constrained Knapsack Problem [14.352521012951865]
我々は、チャンス制約付きknapsack問題に対して、新しい効果的な多目的モデルを提案する。
実験結果から, 進化的多目的アルゴリズムを用いた場合, 性能が大幅に向上することが示唆された。
論文 参考訳（メタデータ） (2020-04-07T08:46:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。