論文の概要: A Machine Learning-based Approach for Solving Recurrence Relations and its use in Cost Analysis of Logic Programs
- arxiv url: http://arxiv.org/abs/2405.06972v2
- Date: Thu, 29 Aug 2024 23:21:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-02 20:01:42.653920
- Title: A Machine Learning-based Approach for Solving Recurrence Relations and its use in Cost Analysis of Logic Programs
- Title（参考訳）: 機械学習による再帰関係の解法と論理プログラムのコスト分析への応用
- Authors: Louis Rustenholz, Maximiliano Klemen, Miguel Ángel Carreira-Perpiñán, Pedro López-García,
- Abstract要約: 我々は、任意の制約付き反復関係を解くための、新しい、一般的なアプローチを開発する。
CiaoPPシステムにおけるプロトタイプの実装とその実験的評価は,非常に有望な結果を示した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Automatic static cost analysis infers information about the resources used by programs without actually running them with concrete data, and presents such information as functions of input data sizes. Most of the analysis tools for logic programs (and many for other languages), as CiaoPP, are based on setting up recurrence relations representing (bounds on) the computational cost of predicates, and solving them to find closed-form functions. Such recurrence solving is a bottleneck in current tools: many of the recurrences that arise during the analysis cannot be solved with state-of-the-art solvers, including Computer Algebra Systems (CASs), so that specific methods for different classes of recurrences need to be developed. We address such a challenge by developing a novel, general approach for solving arbitrary, constrained recurrence relations, that uses machine-learning (sparse-linear and symbolic) regression techniques to guess a candidate closed-form function, and a combination of an SMT-solver and a CAS to check if it is actually a solution of the recurrence. Our prototype implementation and its experimental evaluation within the context of the CiaoPP system show quite promising results. Overall, for the considered benchmarks, our approach outperforms state-of-the-art cost analyzers and recurrence solvers, and solves recurrences that cannot be solved by them. Under consideration in Theory and Practice of Logic Programming (TPLP).
- Abstract（参考訳）: 自動静的コスト分析は、具体的なデータで実際に実行せずにプログラムが使用するリソースに関する情報を推測し、入力データサイズの関数のような情報を提示する。
CiaoPPのような論理プログラム(および他の言語の多く)の分析ツールのほとんどは、述語の計算コストを表す(有界な)再帰関係を設定し、閉形式関数を見つけるためにそれらを解決することに基づいている。
このようなリカレンス解決は、現在のツールのボトルネックとなっている: 解析中に発生するリカレンスの多くは、コンピュータ代数システム(CAS)を含む最先端のリカレンスでは解決できないため、異なるリカレンスクラスの特定のメソッドを開発する必要がある。
このような課題は、任意の制約付き反復関係を解くための新しい一般的なアプローチを開発し、機械学習(疎線形および記号的)回帰手法を用いて候補閉形式関数を推定し、SMT-ソルバとCASを組み合わせることで、それが実際に再発の解であるかどうかを確認することで解決する。
CiaoPPシステムにおけるプロトタイプの実装とその実験的評価は,非常に有望な結果を示した。
総合的に比較すると,提案手法は最先端のコスト解析器や繰り返し解法よりも優れており,それらが解決できない繰り返し解法を解くことができる。
論理プログラミングの理論と実践(TPLP)
関連論文リスト
- Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization [50.485788083202124]
強化学習(Reinforcement Learning, RL)は、大規模言語モデルを人間の好みと整合させ、複雑なタスクを遂行する能力を向上させる上で重要な役割を担っている。
反応生成過程をマルコフ決定プロセス(MDP)として定式化し,ソフトアクター・クリティック(SAC)フレームワークを用いて,言語モデルによって直接パラメータ化されたQ関数を最適化する,直接Q関数最適化(DQO)を提案する。
GSM8KとMATHという2つの数学問題解決データセットの実験結果から、DQOは従来の手法よりも優れており、言語モデルを整合させるための有望なオフライン強化学習手法として確立されている。
論文 参考訳（メタデータ） (2024-10-11T23:29:20Z) - Stochastic Q-learning for Large Discrete Action Spaces [79.1700188160944]
離散的な行動空間を持つ複雑な環境では、強化学習(RL)において効果的な意思決定が重要である
我々は、$n$アクションの集合全体を最適化するのとは対照的に、おそらく$mathcalO(log(n)$)$のような変数の集合のみを考える。
提示された値ベースのRL手法には、Q-learning、StochDQN、StochDDQNなどが含まれる。
論文 参考訳（メタデータ） (2024-05-16T17:58:44Z) - Deep Generative Symbolic Regression [83.04219479605801]
記号回帰は、データから簡潔な閉形式数学的方程式を発見することを目的としている。
既存の手法は、探索から強化学習まで、入力変数の数に応じてスケールできない。
本稿では,我々のフレームワークであるDeep Generative Symbolic Regressionのインスタンス化を提案する。
論文 参考訳（メタデータ） (2023-12-30T17:05:31Z) - Solving Recurrence Relations using Machine Learning, with Application to
Cost Analysis [0.0]
我々は、任意の制約付き反復関係を解くための、新しい、一般的なアプローチを開発する。
我々の手法は、そのようなシステムでは解けない再発のクラスに対して、妥当な時間で閉形式解を見つけることができる。
論文 参考訳（メタデータ） (2023-08-30T08:55:36Z) - Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。
これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。
提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
論文 参考訳（メタデータ） (2023-04-14T11:35:35Z) - Mutual Information Learned Regressor: an Information-theoretic Viewpoint
of Training Regression Systems [10.314518385506007]
回帰問題を解くための既存の慣習は平均二乗誤差(MSE)最小化アプローチである。
近年,Yiらは相互情報に基づく教師あり学習フレームワークを提案し,ラベルエントロピー正規化を導入した。
本稿では,相互情報に基づく教師あり学習フレームワークにおける回帰について検討する。
論文 参考訳（メタデータ） (2022-11-23T03:43:22Z) - MIRACLE: Causally-Aware Imputation via Learning Missing Data Mechanisms [82.90843777097606]
欠落データに対する因果認識型計算アルゴリズム(MIRACLE)を提案する。
MIRACLEは、欠落発生機構を同時にモデル化することにより、ベースラインの計算を反復的に洗練する。
我々は、MIRACLEが一貫してイミューテーションを改善することができることを示すために、合成および様々な公開データセットに関する広範な実験を行う。
論文 参考訳（メタデータ） (2021-11-04T22:38:18Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Symbolic Regression using Mixed-Integer Nonlinear Optimization [9.638685454900047]
シンボリック回帰(SR)問題は、機械学習において難しい問題である。
混合整数非線形最適化と明示列挙法を組み合わせたハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、いくつかの合成データセットに対して、最先端のSRソフトウェアと最近の物理学に触発されたAI Feynmanという手法で競合していることを示す。
論文 参考訳（メタデータ） (2020-06-11T20:53:17Z) - Machine Learning to Tackle the Challenges of Transient and Soft Errors
in Complex Circuits [0.16311150636417257]
機械学習モデルは、回路インスタンスの完全なリストに対して、インスタンスごとの正確な関数デレートデータを予測するために使用される。
提案手法を実例に適用し,各種機械学習モデルの評価と比較を行った。
論文 参考訳（メタデータ） (2020-02-18T18:38:54Z) - On the Estimation of Complex Circuits Functional Failure Rate by Machine
Learning Techniques [0.16311150636417257]
デレーティング(De-Rating)あるいは脆弱性要因(Vulnerability Factors)は、今日の機能的安全要件によって管理される障害分析の最大の特徴である。
機械学習を用いて個々のフリップフロップの関数的デレートを推定する新しい手法が提案されている。
論文 参考訳（メタデータ） (2020-02-18T15:18:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。