論文の概要: Dynamic programming by polymorphic semiring algebraic shortcut fusion

• arxiv url: http://arxiv.org/abs/2107.01752v5
• Date: Thu, 4 Jan 2024 11:53:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-05 18:16:13.411368
• Title: Dynamic programming by polymorphic semiring algebraic shortcut fusion
• Title（参考訳）: 多相半環代数的ショートカット融合による動的プログラミング
• Authors: Max A. Little, Xi He, Ugur Kayas
• Abstract要約: 動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
• 参考スコア（独自算出の注目度）: 1.9405875431318445
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Dynamic programming (DP) is an algorithmic design paradigm for the efficient, exact solution of otherwise intractable, combinatorial problems. However, DP algorithm design is often presented in an ad-hoc manner. It is sometimes difficult to justify algorithm correctness. To address this issue, this paper presents a rigorous algebraic formalism for systematically deriving DP algorithms, based on semiring polymorphism. We start with a specification, construct an algorithm to compute the required solution which is self-evidently correct because it exhaustively generates and evaluates all possible solutions meeting the specification. We then derive, through the use of shortcut fusion, an implementation of this algorithm which is both efficient and correct. We also demonstrate how, with the use of semiring lifting, the specification can be augmented with combinatorial constraints, showing how these constraints can be fused with the algorithm. We furthermore demonstrate how existing DP algorithms for a given combinatorial problem can be abstracted from their original context and re-purposed. This approach can be applied to the full scope of combinatorial problems expressible in terms of semirings. This includes, for example: optimal probability and Viterbi decoding, probabilistic marginalization, logical inference, fuzzy sets, differentiable softmax, relational and provenance queries. The approach, building on ideas from the existing literature on constructive algorithmics, exploits generic properties of polymorphic functions, tupling and formal sums 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. Python software implementing these algorithms can be downloaded from: http://www.maxlittle.net/software/dppolyalg.zip.
• Abstract（参考訳）: 動的プログラミング(英: dynamic programming、dp)は、非可算な組合せ問題に対する効率的で厳密な解のためのアルゴリズム的設計パラダイムである。 しかし、DPアルゴリズムの設計はしばしばアドホックな方法で表される。 アルゴリズムの正しさを正当化するのは難しい。 本稿では, 半環多型に基づくdpアルゴリズムを体系的に導出するための厳密な代数的形式論を提案する。 まず、仕様から始まり、その仕様を満たすすべての可能なソリューションを徹底的に生成し評価するため、自己明快に正しい必要解を計算するアルゴリズムを構築します。 次に、このアルゴリズムの実装であるショートカット融合を用いて、効率と正確性の両方を導出する。 また,半環昇降法を用いることで,これらの制約がアルゴリズムとどのように融合するかを示す組合せ制約によって,仕様を拡張できることを示す。 さらに,与えられた組合せ問題に対する既存のdpアルゴリズムが,その元の文脈からどのように抽象化され,再利用されるかを示す。 このアプローチは、半環の観点から表現可能な組合せ問題の全範囲に適用できる。 例えば、最適確率とビタビ復号、確率的辺縁化、論理的推論、ファジィ集合、微分可能なソフトマックス、リレーショナルおよび前駆的クエリである。 このアプローチは、構成的アルゴリズム学に関する既存の文献に基づくもので、多形関数、タップリング、形式和、および制約代数から生じる代数的単純化の一般的な性質を活用している。 本稿では,信号処理,バイオインフォマティクス,信頼性工学などの応用例について,この形式の有効性を示す。 これらのアルゴリズムを実装するPythonソフトウェアは、http://www.maxlittle.net/software/dppolyalg.zipからダウンロードできる。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。