論文の概要: Instruction and Solution Probabilities as Heuristics for Inductive Programming
- arxiv url: http://arxiv.org/abs/2506.13804v1
- Date: Fri, 13 Jun 2025 15:24:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-18 17:34:59.15376
- Title: Instruction and Solution Probabilities as Heuristics for Inductive Programming
- Title（参考訳）: 帰納的プログラミングのヒューリスティックスとしての指導と解決確率
- Authors: Edward McDaid, Sarah McDaid,
- Abstract要約: 命令サブセット(IS)は、インダクティブプログラミング(IP)検索空間のサイズを数十桁縮小することができる。
我々は、さらなる確率として命令と解決策を導入することで、ISアプローチを拡張します。
いずれの変種も、解サイズに応じて、最大数桁のIP検索空間サイズを大幅に削減できることが示される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Instruction subsets (ISs) are heuristics that can shrink the size of the inductive programming (IP) search space by tens of orders of magnitude. Here, we extend the IS approach by introducing instruction and solution probabilities as additional heuristics. Instruction probability reflects the expectation of an instruction occurring in a solution, based on the frequency of instruction occurrence in a large code sample. The solution probability for a partial or complete program is simply the product of all constituent instruction probabilities, including duplicates. We treat the minimum solution probabilities observed in code sample program units of different sizes as solution probability thresholds. These thresholds are used to prune the search space as partial solutions are constructed, thereby eliminating any branches containing unlikely combinations of instructions. The new approach has been evaluated using a large sample of human code. We tested two formulations of instruction probability: one based on instruction occurrence across the entire code sample and another that measured the distribution separately for each IS. Our results show that both variants produce substantial further reductions in the IP search space size of up to tens of orders of magnitude, depending on solution size. In combination with IS, reductions of over 100 orders of magnitude can be achieved. We also carried out cross-validation testing to show that the heuristics should work effectively with unseen code. The approach is described and the results and some ideas for future work are discussed.
- Abstract（参考訳）: 命令サブセット (IS) は、インダクティブプログラミング (IP) 検索空間のサイズを数十桁縮小できるヒューリスティックである。
ここでは、追加のヒューリスティックスとして命令と解確率を導入することで、ISアプローチを拡張した。
命令確率は、大規模なコードサンプルにおける命令発生頻度に基づいて、ソリューションで発生する命令の期待を反映する。
部分的プログラムあるいは完全プログラムの解確率は、単に重複を含むすべての構成的命令確率の積である。
異なるサイズのコードサンプルプログラムユニットで観測される最小解確率を、解確率閾値として扱う。
これらのしきい値は部分解が構築されるにつれて探索空間を振舞うために使用され、それによって命令のありそうもない組み合わせを含む枝は排除される。
新たなアプローチは、人間のコードの大規模なサンプルを使用して評価されている。
1つはコードサンプル全体にわたる命令発生に基づくもので、もう1つはIS毎に個別に分布を測定したものである。
以上の結果から, いずれの変種も, 解数に応じて, 最大数桁のIP検索空間サイズを大幅に削減できることが示唆された。
ISと組み合わせることで、100桁を超える規模の削減が達成できる。
またクロスバリデーションテストを行い、ヒューリスティックスが見えないコードで効果的に機能することを示しました。
提案手法について述べ,その結果と今後の課題について考察する。
関連論文リスト
- Probabilistic Answer Set Programming with Discrete and Continuous Random Variables [0.18416014644193066]
Probabilistic Answer Set Programming (PASP)は、不確実な情報を表す確率的事実でAnswer Set Programmingを拡張します。
我々はHPASP(Hybrid Probabilistic Answer Set Programming)を提案する。
本稿では,予測された回答集合列挙と知識コンパイルに基づいて,2つの正確なアルゴリズムの性能を議論し,実装し,評価する。
論文 参考訳（メタデータ） (2024-09-30T13:24:42Z) - Learning Submodular Sequencing from Samples [11.528995186765751]
本稿では,いくつかの複合部分モジュラー関数を最適化するために,シーケンス内の項目の選択とランク付けの問題に対処する。
本稿では,各部分モジュラ関数の曲率に依存する近似比を求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-09T01:33:13Z) - Toward a Better Understanding of Probabilistic Delta Debugging [6.393194328016689]
アドバンストなddminであるProbDDが提案され、最先端のパフォーマンスを実現している。
ProbDDの詳細な理論的解析を行い、確率とサブセットサイズの変化の傾向を明らかにする。
本稿では,ProbDDの簡易版であるCDDを提案する。
論文 参考訳（メタデータ） (2024-08-08T19:30:03Z) - Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。
近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。
本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-11T13:44:49Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - Shrinking the Inductive Programming Search Space with Instruction
Subsets [0.0]
本稿では,Zoea分散インダクティブプログラミングシステムにおける探索空間分割を支援するために構築された,新しいプログラミング言語命令共起モデルを提案する。
探索空間の異なる部分のアプローチを用いることで、並列に探索することができる。
必要となるサブセットの数は、それらを生成するために使用されるコードの量と線形に増加せず、管理可能なサブセットの数が、目に見えないコードの高い割合をカバーするのに十分である。
論文 参考訳（メタデータ） (2023-02-10T12:51:35Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Fault-Aware Neural Code Rankers [64.41888054066861]
サンプルプログラムの正しさを予測できる故障認識型ニューラルネットワークローダを提案する。
我々のフォールト・アウェア・ローダは、様々なコード生成モデルのpass@1精度を大幅に向上させることができる。
論文 参考訳（メタデータ） (2022-06-04T22:01:05Z) - Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
AID-BiOとITD-BiOの2つの一般的な双レベルマトリクスは、自然に1つまたは2つのサブプロブレムを解決する。
AID-BiO と ITD-BiO の両ループ実装選択に適用可能な統合収束解析をまず確立する。
論文 参考訳（メタデータ） (2022-05-27T20:28:52Z) - Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
凸最適化における総和係数法に着想を得て,広範な分岐関数を持つネットワーク上での検証クエリを解析するための新しい手法を提案する。
標準ケース分析に基づく完全探索手順の拡張は、各検索状態で実行される凸手順をDeepSoIに置き換えることによって達成できる。
論文 参考訳（メタデータ） (2022-03-19T15:05:09Z) - Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors [1.8130068086063333]
ストラグラーや他の障害は、全体の完了時間に深刻な影響を与える可能性がある。
符号化コンピューティングにおける最近の研究は、コード化されたタスクでストラグラーを緩和するための新しい戦略を提供する。
この厳密な定義は、失敗の確率を直接最適化しないことを示す。
論文 参考訳（メタデータ） (2022-02-07T19:20:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。