論文の概要: Solving Recurrence Relations using Machine Learning, with Application to Cost Analysis

• arxiv url: http://arxiv.org/abs/2309.07259v1
• Date: Wed, 30 Aug 2023 08:55:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-17 13:41:20.280906
• Title: Solving Recurrence Relations using Machine Learning, with Application to Cost Analysis
• Title（参考訳）: 機械学習を用いた再帰関係の解法とコスト分析への応用
• Authors: Maximiliano Klemen, Miguel \'A. Carreira-Perpi\~n\'an, Pedro Lopez-Garcia
• Abstract要約: 我々は、任意の制約付き反復関係を解くための、新しい、一般的なアプローチを開発する。 我々の手法は、そのようなシステムでは解けない再発のクラスに対して、妥当な時間で閉形式解を見つけることができる。
• 参考スコア（独自算出の注目度）: 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 other languages) are based on setting up recurrence relations representing (bounds on) the computational cost of predicates, and solving them to find closed-form functions that are equivalent to (or a bound on) them. Such recurrence solving is a bottleneck in current tools: many of the recurrences that arise during the analysis cannot be solved with current solvers, such as 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 regression techniques to guess a candidate closed-form function, and a combination of an SMT-solver and a CAS to check whether such function is actually a solution of the recurrence. We have implemented a prototype and evaluated it with recurrences generated by a cost analysis system (the one in CiaoPP). The experimental results are quite promising, showing that our approach can find closed-form solutions, in a reasonable time, for classes of recurrences that cannot be solved by such a system, nor by current CASs.
• Abstract（参考訳）: 自動静的コスト分析は、具体的なデータで実際に実行せずにプログラムが使用するリソースに関する情報を推測し、入力データサイズの関数のような情報を提示する。 論理プログラム(および他の言語)の分析ツールのほとんどは、述語の計算コストを表す(有界な)再帰関係を設定し、それらと同等(あるいは有界な)閉形式関数を見つけるためにそれらを解決することに基づいている。 コンピュータ代数システム(CAS)のような現在の解法では、解析中に発生する再発の多くは解決できないため、異なる反復のクラスに対する特定の方法を開発する必要がある。 本稿では、任意の制約付き反復関係を解くための新しい一般的な手法を開発し、機械学習のスパース回帰手法を用いて候補閉形式関数を推定し、SMT-ゾルバとCASを組み合わせて、その関数が実際に再発の解であるかどうかを確認する。 我々は,コスト分析システム(CiaoPPのプロトタイプ)を用いて試作を行い,再評価を行った。 実験結果は非常に有望であり,そのようなシステムや現在のcassでは解決できない再帰のクラスに対して,我々のアプローチが合理的な時間内に閉形式解を見つけることができることを示した。

関連論文リスト

• The Function-Representation Model of Computation [2.5069344340760713]
  本稿では,メモリとプログラムを融合した新しい計算モデル,Function-Representationを提案する。 この計算モデルは、一般的な関数表現を定義し、その複数のインスタンスをインスタンス化する。 また、Function-Representationが実装できる関数の種類についても検討し、Function-Representationの複数のインスタンスを整理するさまざまな方法を提示します。
  論文  参考訳（メタデータ） (2024-10-10T13:54:35Z)
• Bisimulation Learning [55.859538562698496]
  我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。 提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
  論文  参考訳（メタデータ） (2024-05-24T17:11:27Z)
• 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)
• A Machine Learning-based Approach for Solving Recurrence Relations and its use in Cost Analysis of Logic Programs [0.0]
  我々は、任意の制約付き反復関係を解くための、新しい、一般的なアプローチを開発する。 CiaoPPシステムにおけるプロトタイプの実装とその実験的評価は,非常に有望な結果を示した。
  論文  参考訳（メタデータ） (2024-05-11T09:51:36Z)
• Deep Generative Symbolic Regression [83.04219479605801]
  記号回帰は、データから簡潔な閉形式数学的方程式を発見することを目的としている。 既存の手法は、探索から強化学習まで、入力変数の数に応じてスケールできない。 本稿では,我々のフレームワークであるDeep Generative Symbolic Regressionのインスタンス化を提案する。
  論文  参考訳（メタデータ） (2023-12-30T17:05:31Z)
• MIRACLE: Causally-Aware Imputation via Learning Missing Data Mechanisms [82.90843777097606]
  欠落データに対する因果認識型計算アルゴリズム(MIRACLE)を提案する。 MIRACLEは、欠落発生機構を同時にモデル化することにより、ベースラインの計算を反復的に洗練する。 我々は、MIRACLEが一貫してイミューテーションを改善することができることを示すために、合成および様々な公開データセットに関する広範な実験を行う。
  論文  参考訳（メタデータ） (2021-11-04T22:38:18Z)
• Computational Graph Completion [0.8122270502556374]
  計算知識の生成、編成、推論のためのフレームワークを導入する。 計算科学と工学のほとんどの問題は、計算グラフを完成させるものであると記述できるという観察から動機づけられている。
  論文  参考訳（メタデータ） (2021-10-20T00:32:06Z)
• Symbolic Regression by Exhaustive Search: Reducing the Search Space Using Syntactical Constraints and Efficient Semantic Structure Deduplication [2.055204980188575]
  シンボリック回帰は、モデル構造に関する事前の知識が得られない産業シナリオにおいて、強力なシステム識別技術である。 この章では、これらの問題に対処するために特別に設計された決定論的シンボリック回帰アルゴリズムを紹介します。 全ての可能なモデルの有限列挙は、構造的制約と意味論的に等価な解を検出するキャッシング機構によって保証される。
  論文  参考訳（メタデータ） (2021-09-28T17:47:51Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• 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)

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

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