論文の概要: Polymorphic dynamic programming by algebraic shortcut fusion
- arxiv url: http://arxiv.org/abs/2107.01752v1
- Date: Mon, 5 Jul 2021 00:51:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-06 23:42:57.882202
- Title: Polymorphic dynamic programming by algebraic shortcut fusion
- Title（参考訳）: 代数的ショートカット融合による多型動的プログラミング
- Authors: Max A. Little and Ugur Kayas
- Abstract要約: 動的プログラミング (DP) は、難解で確率的な問題の効率的かつ正確な解法に対して広く適用可能なアルゴリズム設計パラダイムである。
本稿では,新しいDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
本稿では,信号処理,バイオインフォマティクス,信頼性工学などの応用例について,この形式の有効性を示す。
- 参考スコア（独自算出の注目度）: 3.264137458214843
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Dynamic programming (DP) is a broadly applicable algorithmic design paradigm
for the efficient, exact solution of otherwise intractable, combinatorial
problems. However, the design of such algorithms is often presented informally
in an ad-hoc manner, and as a result is often difficult to apply correctly. In
this paper, we present a rigorous algebraic formalism for systematically
deriving novel DP algorithms, either from existing DP algorithms or from simple
functional recurrences. These derivations lead to algorithms which are provably
correct and polymorphic over any semiring, which means that they can be applied
to the full scope of combinatorial problems expressible in terms of semirings.
This includes, for example: optimization, optimal probability and Viterbi
decoding, probabilistic marginalization, logical inference, fuzzy sets,
differentiable softmax, and relational and provenance queries. The approach,
building on many ideas from the existing literature on constructive
algorithmics, exploits generic properties of (semiring) polymorphic functions,
tupling and formal sums (lifting), and algebraic simplifications arising from
constraint algebras. We demonstrate the effectiveness of this formalism for
some example applications arising in signal processing, bioinformatics and
reliability engineering.
- Abstract（参考訳）: 動的プログラミング (dp) は広く適用可能なアルゴリズム設計パラダイムであり、それ以外は難解な組合せ問題に対する効率的で正確な解法である。
しかし、そのようなアルゴリズムの設計は、しばしばアドホックな方法で非公式に提示され、その結果、正しく適用することはしばしば困難である。
本稿では,既存のDPアルゴリズムから,あるいは単純な機能的再帰から,新しいDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
これらの導出は、任意の半環に対して証明可能正確かつ多型なアルゴリズムに導かれるので、半環の観点で表現可能な組合せ問題の全範囲に適用することができる。
例えば、最適化、最適確率、ビタビ復号、確率的辺縁化、論理的推論、ファジィ集合、微分可能なソフトマックス、リレーショナルおよび前駆的クエリなどである。
このアプローチは、構成的アルゴリズムに関する既存の文献からの多くのアイデアに基づいており、(半)多型函数、tuplingとformal sums(リフト)、および制約代数から生じる代数的単純化の一般的な性質を利用する。
本稿では,信号処理,バイオインフォマティクス,信頼性工学などの応用例について,この形式の有効性を示す。
関連論文リスト
- 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) - EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。
EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。
我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
論文 参考訳（メタデータ） (2024-05-16T15:11:37Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳（メタデータ） (2022-06-22T23:57:40Z) - Power of human-algorithm collaboration in solving combinatorial
optimization problems [0.0]
最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。
提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
論文 参考訳（メタデータ） (2021-07-25T11:21:59Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳（メタデータ） (2021-02-12T12:38:03Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Symbolic Regression using Mixed-Integer Nonlinear Optimization [9.638685454900047]
シンボリック回帰(SR)問題は、機械学習において難しい問題である。
混合整数非線形最適化と明示列挙法を組み合わせたハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、いくつかの合成データセットに対して、最先端のSRソフトウェアと最近の物理学に触発されたAI Feynmanという手法で競合していることを示す。
論文 参考訳（メタデータ） (2020-06-11T20:53:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。