論文の概要: Program Synthesis with Best-First Bottom-Up Search
- arxiv url: http://arxiv.org/abs/2310.04327v1
- Date: Fri, 6 Oct 2023 15:44:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-09 15:33:31.763110
- Title: Program Synthesis with Best-First Bottom-Up Search
- Title（参考訳）: 最良ボトムアップ探索によるプログラム合成
- Authors: Saqib Ameen and Levi H. S. Lelis
- Abstract要約: 現在の最先端のコスト誘導型BUSアルゴリズムは、有用な情報を失うという共通の問題に悩まされている。
本稿では,情報損失を被らず,低コストでボトムアップ合成を最優先で行う,新しいボトムアップ検索アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 14.146892127555217
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Cost-guided bottom-up search (BUS) algorithms use a cost function to guide
the search to solve program synthesis tasks. In this paper, we show that
current state-of-the-art cost-guided BUS algorithms suffer from a common
problem: they can lose useful information given by the model and fail to
perform the search in a best-first order according to a cost function. We
introduce a novel best-first bottom-up search algorithm, which we call Bee
Search, that does not suffer information loss and is able to perform
cost-guided bottom-up synthesis in a best-first manner. Importantly, Bee Search
performs best-first search with respect to the generation of programs, i.e., it
does not even create in memory programs that are more expensive than the
solution program. It attains best-first ordering with respect to generation by
performing a search in an abstract space of program costs. We also introduce a
new cost function that better uses the information provided by an existing cost
model. Empirical results on string manipulation and bit-vector tasks show that
Bee Search can outperform existing cost-guided BUS approaches when employing
more complex domain-specific languages (DSLs); Bee Search and previous
approaches perform equally well with simpler DSLs. Furthermore, our new cost
function with Bee Search outperforms previous cost functions on string
manipulation tasks.
- Abstract（参考訳）: コスト誘導ボトムアップ探索(bus)アルゴリズムは、プログラム合成タスクの解法としてコスト関数を使用する。
本稿では,現在最先端のコスト誘導バスアルゴリズムが,モデルが提供する有用な情報を失い,コスト関数に従って最上位の検索を実行できないという,共通の問題に直面していることを示す。
提案手法は,情報喪失に苦しむことなく,コストガイド付きボトムアップ合成を最先に行うことが可能な,新しいボトムアップ探索アルゴリズムである。
重要なことに、bee searchは、プログラムの生成に関してベストファースト検索を行う。つまり、ソリューションプログラムよりも高価なメモリプログラムを生成さえしない。
プログラムコストの抽象的な空間で探索を行うことにより、生成に関する最優先の順序付けを実現する。
また、既存のコストモデルが提供する情報をよりよく利用する新しいコスト関数も導入します。
文字列操作とビットベクトルタスクに関する経験的な結果は、より複雑なドメイン固有言語(dsl)を使用する場合、蜂の検索が既存のコストガイドバスアプローチを上回ることができることを示している。
さらに, bee search を用いた新たなコスト関数は,文字列操作タスクのコスト関数よりも優れている。
関連論文リスト
- 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) - LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - Bayesian Program Learning by Decompiling Amortized Knowledge [50.960612835957875]
本稿では,ニューラルサーチポリシーを直接活用し,その記憶された知識を効果的に「分解」し,関連するプログラムコンポーネントを抽出する,新たな学習手法を提案する。
これにより、より強力な償却推論が実現され、探索幅を減らすために学習した償却知識も探索深度を減らすために使用されるようになった。
論文 参考訳（メタデータ） (2023-06-13T15:35:01Z) - Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
本稿では,品質と多様性のバランスをとる決定論的探索アルゴリズムを提案する。
提案アルゴリズムはパラメータフリーで、軽量で、効率的で、使いやすくなっている。
論文 参考訳（メタデータ） (2022-11-22T00:26:13Z) - CrossBeam: Learning to Search in Bottom-Up Program Synthesis [51.37514793318815]
ボトムアップ合成のためのハンズオン検索ポリシーを学習するためのニューラルネットワークのトレーニングを提案する。
私たちのアプローチは、CrossBeamと呼ばれ、ニューラルモデルを使用して、以前に探索されたプログラムを新しいプログラムに組み合わせる方法を選択します。
我々はCrossBeamが効率的に検索することを学び、最先端技術と比較してプログラム空間のより小さな部分を探索する。
論文 参考訳（メタデータ） (2022-03-20T04:41:05Z) - Contrastive Self-supervised Neural Architecture Search [6.162410142452926]
本稿では,新しいセルベースニューラルアーキテクチャ探索アルゴリズム(NAS)を提案する。
本アルゴリズムは,画像表現における自己教師付き学習の有効性を生かしている。
実験の結果,検索アルゴリズムが最先端の結果を得ることができた。
論文 参考訳（メタデータ） (2021-02-21T08:38:28Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。