論文の概要: Searching for More Efficient Dynamic Programs

• arxiv url: http://arxiv.org/abs/2109.06966v1
• Date: Tue, 14 Sep 2021 20:52:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-16 15:08:36.323857
• Title: Searching for More Efficient Dynamic Programs
• Title（参考訳）: より効率的な動的プログラムの探索
• Authors: Tim Vieira and Ryan Cotterell and Jason Eisner
• Abstract要約: 本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。 実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
• 参考スコア（独自算出の注目度）: 61.79535031840558
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions. Algorithms for such problems often employ dynamic programming and are not always unique. Finding one with optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. Our work aims to automate this laborious process. Given an initial correct declarative program, we search for a sequence of semantics-preserving transformations to improve its running time as much as possible. To this end, we describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a heuristic search procedure to improve this metric. 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 common speed-ups described in the NLP literature could have been discovered automatically by our system.
• Abstract（参考訳）: 人間言語の計算モデルは、しばしば組合せ問題を伴う。 例えば、確率論的解析器は指数関数的に多くの木を疎外して予測を行う。 このような問題のアルゴリズムは、しばしば動的プログラミングを採用し、必ずしも一意ではない。 最適な漸近ランタイムを持つものを見つけることは直観的で、時間がかかり、エラーを起こしやすい。 私たちの仕事は、この手間のかかるプロセスを自動化することを目指している。 最初の正しい宣言型プログラムが与えられたら、できるだけ実行時間を改善するために、セマンティックス保存変換のシーケンスを探索する。 この目的のために,プログラム変換のセット,変換されたプログラムの効率を評価するための簡単なメトリック,このメトリックを改善するためのヒューリスティック探索手順について述べる。 実際には、自動検索は、人間のプログラマが行うメンタル検索のように、最初のプログラムを大幅に改善できることを示している。 実験により,NLP文献に記述される多くの一般的なスピードアップが,我々のシステムによって自動的に検出されたことを示す。

関連論文リスト

• Searching Latent Program Spaces [0.0]
  本研究では,連続空間における潜伏プログラム上の分布を学習し,効率的な探索とテスト時間適応を可能にするプログラム誘導アルゴリズムを提案する。 テスト時間適応機構を利用して、トレーニング分布を超えて一般化し、目に見えないタスクに適応できることを示す。
  論文  参考訳（メタデータ） (2024-11-13T15:50:32Z)
• Efficient Bottom-Up Synthesis for Programs with Local Variables [7.387053183440393]
  我々のアルゴリズムは,プログラムをローカル変数で効率的に探索することができる。 Lifted interpretationは、ローカル変数のすべてのバインディングコンテキストを列挙するメカニズムを提供する。 私たちのアイデアは、Webオートメーションの領域でインスタンス化されています。
  論文  参考訳（メタデータ） (2023-11-07T04:02:52Z)
• Improved Tree Search for Automatic Program Synthesis [91.3755431537592]
  重要な要素は、有効なプログラムの空間における効率的な探索を可能にすることである。 ここでは2つの大きな異なるDSL上でのアート結果の状態を導くMCTSの変種を提案する。
  論文  参考訳（メタデータ） (2023-03-13T15:09:52Z)
• Learning to compile smartly for program size reduction [35.58682369218936]
  プログラムサイズ削減のためのパスを選択するためのポリシーを学習する新しいアプローチを提案する。 提案手法では,有用なパスシーケンスを識別する検索機構と,最適なシーケンスを選択するための注意をカスタマイズしたGNNを用いる。
  論文  参考訳（メタデータ） (2023-01-09T16:42:35Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Recent Developments in Program Synthesis with Evolutionary Algorithms [1.8047694351309207]
  関連する進化的プログラム合成手法を同定し,その性能を詳細に解析する。 私たちが特定する最も影響力のあるアプローチは、スタックベース、文法誘導、および線形遺伝プログラミングである。 今後の研究のために、研究者は、プログラムのアウトプットを使用して、ソリューションの品質を評価するだけでなく、ソリューションへの道を開くことを奨励します。
  論文  参考訳（メタデータ） (2021-08-27T11:38:27Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Latent Programmer: Discrete Latent Codes for Program Synthesis [56.37993487589351]
  プログラム合成や文書要約などの多くのシーケンス学習タスクにおいて、重要な問題は出力シーケンスの広い空間を探索することである。 本稿では,検索対象とする出力の表現を学習することを提案する。 本稿では,まず入力/出力サンプルから離散潜在コードを予測するプログラム合成手法であるemphLatent Programmerを紹介し,そのプログラムを対象言語で生成する。
  論文  参考訳（メタデータ） (2020-12-01T10:11:35Z)
• Learning Differentiable Programs with Admissible Neural Heuristics [43.54820901841979]
  ドメイン固有言語におけるプログラムとして表現される微分可能関数の学習問題について検討する。 我々は、この最適化問題を、プログラム構文のトップダウン導出を符号化した重み付きグラフの探索として構成する。 私たちの重要なイノベーションは、さまざまなニューラルネットワークのクラスを、プログラムの空間上の連続的な緩和と見なすことです。
  論文  参考訳（メタデータ） (2020-07-23T16:07:39Z)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。 ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
  論文  参考訳（メタデータ） (2020-07-07T17:03:02Z)

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

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