論文の概要: EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis

• arxiv url: http://arxiv.org/abs/2412.17330v1
• Date: Mon, 23 Dec 2024 06:48:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 15:52:35.184220
• Title: EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis
• Title（参考訳）: EcoSearch: プログラム合成のための定遅延ベストファースト検索アルゴリズム
• Authors: Théo Matricon, Nathanaël Fijalkow, Guillaume Lagarde,
• Abstract要約: 本稿では,前世代コスト関数の定時遅延アルゴリズムであるEcoSearchを提案する。 EcoSearchは2つの古典的ドメインで前者よりも優れています。
• 参考スコア（独自算出の注目度）: 4.523850593225294
• License:
• Abstract: Many approaches to program synthesis perform a combinatorial search within a large space of programs to find one that satisfies a given specification. To tame the search space blowup, previous works introduced probabilistic and neural approaches to guide this combinatorial search by inducing heuristic cost functions. Best-first search algorithms ensure to search in the exact order induced by the cost function, significantly reducing the portion of the program space to be explored. We present a new best-first search algorithm called EcoSearch, which is the first constant-delay algorithm for pre-generation cost function: the amount of compute required between outputting two programs is constant, and in particular does not increase over time. This key property yields important speedups: we observe that EcoSearch outperforms its predecessors on two classic domains.
• Abstract（参考訳）: プログラム合成に対する多くのアプローチは、与えられた仕様を満たすものを見つけるために、プログラムの広い空間内で組合せ探索を行う。 探索空間の爆発を抑えるため、従来の研究は確率的およびニューラルなアプローチを導入し、この組み合わせ探索をヒューリスティックなコスト関数を誘導した。 最優先探索アルゴリズムは、コスト関数によって引き起こされる正確な順序で探索することを保証する。 本稿では,2つのプログラムの出力に要する計算量は一定であり,特に時間とともに増加しない,EcoSearchというアルゴリズムを提案する。 EcoSearchは2つの古典的なドメインで前バージョンよりも優れています。

関連論文リスト

• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。 本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。 第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
  論文  参考訳（メタデータ） (2024-07-17T21:26:27Z)
• Program Synthesis with Best-First Bottom-Up Search [14.146892127555217]
  現在の最先端のコスト誘導型BUSアルゴリズムは、有用な情報を失うという共通の問題に悩まされている。 本稿では,情報損失を被らず,低コストでボトムアップ合成を最優先で行う,新しいボトムアップ検索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-06T15:44:47Z)
• HUSP-SP: Faster Utility Mining on Sequence Data [48.0426095077918]
  高実用性シーケンシャルパターンマイニング (HUSPM) が重要視されている。 シークエンスプロジェクション(seqPro)と呼ばれるコンパクトな構造を設計し、シークエンスプロ構造(HUSP-SP)を用いた効率的なアルゴリズムを提案する。 HUSP-SPは, 実行時間, メモリ使用量, 検索空間のプルーニング効率, スケーラビリティにおいて, 最先端のアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2022-12-29T10:56:17Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• CrossBeam: Learning to Search in Bottom-Up Program Synthesis [51.37514793318815]
  ボトムアップ合成のためのハンズオン検索ポリシーを学習するためのニューラルネットワークのトレーニングを提案する。 私たちのアプローチは、CrossBeamと呼ばれ、ニューラルモデルを使用して、以前に探索されたプログラムを新しいプログラムに組み合わせる方法を選択します。 我々はCrossBeamが効率的に検索することを学び、最先端技術と比較してプログラム空間のより小さな部分を探索する。
  論文  参考訳（メタデータ） (2022-03-20T04:41:05Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples [10.993342896547691]
  自然言語処理(NLP)タスクの逆例を生成するために,複数のブラックボックス探索アルゴリズムの動作について検討した。 検索アルゴリズム,検索空間,検索予算の3つの要素を詳細に分析する。
  論文  参考訳（メタデータ） (2020-09-09T17:04:42Z)
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
  プログラムのボトムアップ検索に学習を活用する新しい合成手法を提案する。 特に、入力出力例のセットに基づいて、探索条件中の中間値の合成を優先順位付けするようにモデルを訓練する。 単純な教師付き学習アプローチであっても,学習とボトムアップ検索の組み合わせは極めて効果的であることを示す。
  論文  参考訳（メタデータ） (2020-07-28T17:46:18Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)

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

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