Fugu-MT 論文翻訳(概要): Prove Symbolic Regression is NP-hard by Symbol Graph

論文の概要: Prove Symbolic Regression is NP-hard by Symbol Graph

arxiv url: http://arxiv.org/abs/2404.13820v1
Date: Mon, 22 Apr 2024 01:48:58 GMT
ステータス: 処理完了
システム内更新日: 2024-04-23 15:36:05.684906
Title: Prove Symbolic Regression is NP-hard by Symbol Graph
Title（参考訳）: Prove Symbolic Regression is NP-hard by Symbol Graph
Authors: Jinglu Song, Qiang Lu, Bozhou Tian, Jingwen Zhang, Jake Luo, Zhiguang Wang,
Abstract要約: 本稿では,数式空間全体の包括的表現としての記号グラフの概念を紹介する。我々は適度に調整されたSteiner Arborescence (DCSAP) を同定する。 NPハードであることが証明されたDCSAPの複雑さは、直接的に、SR問題のNPハードの性質を意味する。
参考スコア（独自算出の注目度）: 5.68255131309463
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Symbolic regression (SR) is the task of discovering a symbolic expression that fits a given data set from the space of mathematical expressions. Despite the abundance of research surrounding the SR problem, there's a scarcity of works that confirm its NP-hard nature. Therefore, this paper introduces the concept of a symbol graph as a comprehensive representation of the entire mathematical expression space, effectively illustrating the NP-hard characteristics of the SR problem. Leveraging the symbol graph, we establish a connection between the SR problem and the task of identifying an optimally fitted degree-constrained Steiner Arborescence (DCSAP). The complexity of DCSAP, which is proven to be NP-hard, directly implies the NP-hard nature of the SR problem.
Abstract（参考訳）: シンボリック回帰(シンボリックレグレッション、英: Symbolic regression、SR)は、数学的表現の空間から与えられたデータセットに適合するシンボリック表現を発見するタスクである。 SR問題にまつわる研究が豊富にあるにもかかわらず、NPのハードな性質を裏付ける研究は乏しい。そこで本研究では,記号グラフの概念を数学的表現空間全体の包括的表現として導入し,SR問題のNPハード特性を効果的に説明する。シンボルグラフを活用することで、SR問題と最適な等級制約付Steiner Arborescence(DCSAP)を識別するタスクとの接続を確立する。 NPハードであることが証明されたDCSAPの複雑さは、直接的に、SR問題のNPハードの性質を意味する。

関連論文リスト

Ab initio nonparametric variable selection for scalable Symbolic Regression with large $p$ [2.222138965069487]
シンボリック回帰(SR)は、データの非線形関係を特徴付けるシンボリック表現を発見するための強力な手法である。既存のSR法は、多くの入力変数を持つデータセットにスケールしないが、これは現代の科学的応用で一般的である。本稿では,Ab初期非パラメトリック変数選択とSRを組み合わせたPAN+SRを提案する。
論文参考訳（メタデータ） (2024-10-17T15:41:06Z)
Discovering symbolic expressions with parallelized tree search [59.92040079807524]
記号回帰は、データから簡潔で解釈可能な数学的表現を発見する能力のおかげで、科学研究において重要な役割を果たす。既存のアルゴリズムは、複雑性の問題に対処する際の精度と効率の重要なボトルネックに直面してきた。本稿では,限定データから汎用数学的表現を効率的に抽出する並列木探索(PTS)モデルを提案する。
論文参考訳（メタデータ） (2024-07-05T10:41:15Z)
Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文参考訳（メタデータ） (2024-03-08T18:50:19Z)
Deep Generative Symbolic Regression [83.04219479605801]
記号回帰は、データから簡潔な閉形式数学的方程式を発見することを目的としている。既存の手法は、探索から強化学習まで、入力変数の数に応じてスケールできない。本稿では,我々のフレームワークであるDeep Generative Symbolic Regressionのインスタンス化を提案する。
論文参考訳（メタデータ） (2023-12-30T17:05:31Z)
The Complexity of Envy-Free Graph Cutting [44.58084909019557]
我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
論文参考訳（メタデータ） (2023-12-12T07:54:30Z)
GFN-SR: Symbolic Regression with Generative Flow Networks [0.9208007322096533]
近年,DSR(Deep symbolic regression)がこの分野の一般的な手法として登場している。ディープラーニングを用いてSRにアプローチするための代替フレームワーク(GFN-SR)を提案する。 GFN-SRは多種多様な最適表現を生成することができる。
論文参考訳（メタデータ） (2023-12-01T07:38:05Z)
Symbolic Regression is NP-hard [1.5330785573575156]
シンボリック回帰(シンボリックレグレッション、英: Symbolic regression、SR)は、数学的表現の形でデータのモデルを学ぶタスクである。 SRは計算集約的なタスクであることを示す。 SR が NP-hard であることを示すことによって、答えがおそらく負であることを示す証拠を提供する。
論文参考訳（メタデータ） (2022-07-03T12:10:28Z)
Symbolic Expression Transformer: A Computer Vision Approach for Symbolic Regression [9.978824294461196]
シンボリック回帰(英: Symbolic Regression、SR)は、データに最も適合する数学的表現を自動的に見つけるための回帰分析の一種である。人間はその曲線に基づいて数学的表現を推測できるという事実に触発され、記号表現変換器(SET)を提案する。 SETは、SRのコンピュータビジョンの観点からのサンプル非依存モデルである。
論文参考訳（メタデータ） (2022-05-24T05:35:46Z)
Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文参考訳（メタデータ） (2021-12-29T18:46:52Z)
Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文参考訳（メタデータ） (2021-05-27T23:41:01Z)
Sinkhorn Natural Gradient for Generative Models [125.89871274202439]
本研究では,シンクホーンの発散による確率空間上の最も急降下法として機能するシンクホーン自然勾配(SiNG)アルゴリズムを提案する。本稿では,SiNG の主要成分であるシンクホーン情報行列 (SIM) が明示的な表現を持ち,対数的スケールの複雑さを正確に評価できることを示す。本実験では,SiNGと最先端のSGD型解法を定量的に比較し,その有効性と有効性を示す。
論文参考訳（メタデータ） (2020-11-09T02:51:17Z)

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