論文の概要: Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
- arxiv url: http://arxiv.org/abs/2012.06344v2
- Date: Sun, 14 Feb 2021 09:22:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-15 21:40:38.969864
- Title: Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
- Title（参考訳）: 世論調査から学ぶ:MAX-E-$3$-SATのためのニューラルネットワーク
- Authors: Raffaele Marino
- Abstract要約: 本稿では,最大3-Stisfiability (MAX-E-$3$-SAT) 問題に対して$Theta(N)$で近似解を計算するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Many natural optimization problems are NP-hard, which implies that they are
probably hard to solve exactly in the worst-case. However, it suffices to get
reasonably good solutions for all (or even most) instances in practice. This
paper presents a new algorithm for computing approximate solutions in
${\Theta(N})$ for the Maximum Exact 3-Satisfiability (MAX-E-$3$-SAT) problem by
using deep learning methodology. This methodology allows us to create a
learning algorithm able to fix Boolean variables by using local information
obtained by the Survey Propagation algorithm. By performing an accurate
analysis, on random CNF instances of the MAX-E-$3$-SAT with several Boolean
variables, we show that this new algorithm, avoiding any decimation strategy,
can build assignments better than a random one, even if the convergence of the
messages is not found. Although this algorithm is not competitive with
state-of-the-art Maximum Satisfiability (MAX-SAT) solvers, it can solve
substantially larger and more complicated problems than it ever saw during
training.
- Abstract（参考訳）: 多くの自然最適化問題はnpハードであり、最悪の場合に正確に解くのが難しいことを意味する。
しかし、実際にはすべての(あるいはほとんどの)インスタンスに対して合理的に優れたソリューションを得るのに十分です。
本稿では,Deep Learning法を用いて,最大3-Satisfiability(MAX-E-$3$-SAT)問題に対して${\Theta(N})$で近似解を計算するアルゴリズムを提案する。
この手法により,調査伝播アルゴリズムによって得られた局所情報を用いてブール変数を修正可能な学習アルゴリズムを作成できる。
複数のブール変数を持つmax-e-$3$-satのランダムなcnfインスタンスについて、正確な分析を行うことで、この新しいアルゴリズムは、デシメーション戦略を避けて、メッセージの収束が見つからない場合でも、ランダムな値よりも優れた代入を構築できることを示した。
このアルゴリズムは最先端のMaximum Satisfiability (MAX-SAT)ソルバと競合するものではないが、トレーニング中に見たよりもはるかに大きく複雑な問題を解くことができる。
関連論文リスト
- 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) - torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability
Problem [1.5850859526672516]
最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。
我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
論文 参考訳（メタデータ） (2024-02-06T02:33:00Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳（メタデータ） (2023-12-16T12:44:36Z) - Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。
本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。
我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
論文 参考訳（メタデータ） (2023-10-05T15:48:41Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
本稿では,軽度条件下での有限個の判定問題に対して,対話型意思決定のための最初のインスタンス最適化アルゴリズムを設計する。
本研究の結果は, 具体的問題に着目し, 多腕バンディットの古典的ギャップ依存境界と, 線形バンディットに関する先行研究を復元した。
論文 参考訳（メタデータ） (2022-06-06T02:56:10Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Curriculum learning for multilevel budgeted combinatorial problems [7.804994311050265]
マルチレベル最適化問題はそれらの一般化であり、複数のプレイヤーが逐次決定を下す状況を含んでいる。
グラフ上のゼロサムゲームにおいて、2人のプレイヤーが関与する多段階の予算問題を解決するための価値ベース手法を考案する。
我々のフレームワークは単純なカリキュラムに基づいており、もしエージェントが$B$までの予算を持つインスタンスの価値を見積もる方法を知っているなら、可能なすべての余剰状態の方向に関係なく、予算が$B+1$のインスタンスを時間内に解決することができる。
論文 参考訳（メタデータ） (2020-07-07T01:09:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。