論文の概要: Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing

• arxiv url: http://arxiv.org/abs/2603.13242v1
• Date: Fri, 20 Feb 2026 02:01:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 08:17:42.222439
• Title: Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing
• Title（参考訳）: 動的プログラミングアルゴリズムの解析と改善の自動化と自然言語処理への応用
• Abstract要約: この論文は、動的プログラムを自動解析し、改善するシステムを開発する。 最適なランタイムで正しいプログラムを見つけることは、直感的で、時間がかかり、エラーが発生しやすい。 実際に,自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
• 参考スコア（独自算出の注目度）: 10.169706093621421
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This thesis develops a system for automatically analyzing and improving dynamic programs, such as those that have driven progress in natural language processing and computer science, more generally, for decades. Finding a correct program with the optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. This thesis aims to automate this laborious process. To this end, we develop an approach based on 1. a high-level, domain-specific language called Dyna for concisely specifying dynamic programs 2. a general-purpose solver to efficiently execute these programs 3. a static analysis system that provides type analysis and worst-case time/space complexity analyses 4. a rich collection of meaning-preserving transformations to programs, which systematizes the repeated insights of numerous authors when speeding up algorithms in the literature 5. a search algorithm for identifying a good sequence of transformations that reduce the runtime complexity, given an initial, correct program We show that, in practice, automated search -- like the mental search performed by human programmers -- can find substantial improvements to the initial program. Empirically, we show that many speed-ups described in the NLP literature could have been discovered automatically by our system. We provide a freely available prototype system at https://github.com/timvieira/dyna-pi.
• Abstract（参考訳）: この論文は、自然言語処理や計算機科学の進歩を数十年にわたって推進してきたような動的プログラムを自動的に分析し、改善するシステムを開発する。 最適な漸近ランタイムで正しいプログラムを見つけることは、直感的、時間を要する、エラーを起こしやすい。 この論文は、この退屈なプロセスを自動化することを目的としています。 そこで本研究では、動的プログラムを簡潔に特定するためのDynaと呼ばれる高レベルドメイン固有言語を1.ベースとして開発し、これらのプログラムを効率的に実行するための汎用的な解法3、型解析と最悪の時間/空間の複雑さ分析を提供する静的解析システム4、文学におけるアルゴリズムを高速化する際、多くの著者の繰り返し洞察を体系化するプログラムへの意味保存変換の豊富なコレクション5、ランタイムの複雑さを減少させる変換の優れたシーケンスを同定する検索アルゴリズムについて述べる。 実験により,NLP文献に記載されている多くのスピードアップが,我々のシステムによって自動的に検出された可能性が示唆された。 我々は、https://github.com/timvieira/dyna-pi.comで無料で利用できるプロトタイプシステムを提供しています。

関連論文リスト

• Grammar-Guided Evolutionary Search for Discrete Prompt Optimisation [63.97051732013936]
  本稿では,2段階からなる離散的な自動最適化に対する進化的探索手法を提案する。 第1段階では、文法誘導型遺伝的プログラミングが実行され、プロンプト生成プログラムを合成する。 第2段階では、局所探索を用いて、最高のパフォーマンスプログラムの周辺を探索する。
  論文  参考訳（メタデータ） (2025-07-14T14:34:15Z)
• LLM Program Optimization via Retrieval Augmented Search [71.40092732256252]
  提案手法は,提案手法によって最適化されたビーム探索を行う検索アルゴリズムであるRetrieval Augmented Search (RAS) である。 我々は、RASが従来の最先端のブラックボックス適応戦略よりも1.8$times$パフォーマンスが高いことを示す。 また、トレーニング例を「アトミックな編集」に分解することで、解釈可能性を向上させるAEGISと呼ばれる手法を提案する。
  論文  参考訳（メタデータ） (2025-01-31T06:34:47Z)
• Searching Latent Program Spaces [0.0]
  ニューラルモデルに直接テストタイム検索を構築する新しいアーキテクチャであるLatent Program Network (LPN)を提案する。 テスト時にコンパクトな潜在空間を探索し、事前定義されたドメイン固有言語の必要性を回避します。 ARC-AGIベンチマークを用いて、プログラム空間を学習し、新しいタスクに適応するためにテスト時に検索できることを実証した。
  論文  参考訳（メタデータ） (2024-11-13T15:50:32Z)
• Improved Tree Search for Automatic Program Synthesis [91.3755431537592]
  重要な要素は、有効なプログラムの空間における効率的な探索を可能にすることである。 ここでは2つの大きな異なるDSL上でのアート結果の状態を導くMCTSの変種を提案する。
  論文  参考訳（メタデータ） (2023-03-13T15:09:52Z)
• Genetic Micro-Programs for Automated Software Testing with Large Path Coverage [0.0]
  既存のソフトウェアテスト技術は、検索アルゴリズムを利用して、高い実行パスカバレッジを実現する入力値を見つけることに重点を置いている。 本稿では、進化したソリューションが入力値ではなく、繰り返し入力値を生成するマイクロプログラムである新しい遺伝的プログラミングフレームワークの概要を述べる。 我々のアプローチは多くの異なるソフトウェアシステムに適用できるような一般化が可能であり、そのため、トレーニングされた特定のソフトウェアコンポーネントのみに特化していない、と我々は主張する。
  論文  参考訳（メタデータ） (2023-02-14T18:47:21Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。 実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
  論文  参考訳（メタデータ） (2021-09-14T20:52:55Z)
• Recent Developments in Program Synthesis with Evolutionary Algorithms [1.8047694351309207]
  関連する進化的プログラム合成手法を同定し,その性能を詳細に解析する。 私たちが特定する最も影響力のあるアプローチは、スタックベース、文法誘導、および線形遺伝プログラミングである。 今後の研究のために、研究者は、プログラムのアウトプットを使用して、ソリューションの品質を評価するだけでなく、ソリューションへの道を開くことを奨励します。
  論文  参考訳（メタデータ） (2021-08-27T11:38:27Z)
• Leveraging Language to Learn Program Abstractions and Search Heuristics [66.28391181268645]
  LAPS(Language for Abstraction and Program Search)は、自然言語アノテーションを用いて、ライブラリとニューラルネットワークによる合成のための検索モデルの共同学習をガイドする手法である。 最先端のライブラリ学習システム(DreamCoder)に統合されると、LAPSは高品質なライブラリを生成し、検索効率と一般化を改善する。
  論文  参考訳（メタデータ） (2021-06-18T15:08:47Z)
• Automated Aggregator -- Rewriting with the Counting Aggregate [0.0]
  本稿では,補完的な性能を持つ等価プログラム群を生成する自動書き換えシステムを提案する。 本稿では,自動解答器選択ツールにおけるシステムの利用を提案する。
  論文  参考訳（メタデータ） (2020-09-22T00:48:33Z)
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
  プログラムのボトムアップ検索に学習を活用する新しい合成手法を提案する。 特に、入力出力例のセットに基づいて、探索条件中の中間値の合成を優先順位付けするようにモデルを訓練する。 単純な教師付き学習アプローチであっても,学習とボトムアップ検索の組み合わせは極めて効果的であることを示す。
  論文  参考訳（メタデータ） (2020-07-28T17:46:18Z)

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

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