論文の概要: Symbolic Regression is NP-hard
- arxiv url: http://arxiv.org/abs/2207.01018v2
- Date: Tue, 5 Jul 2022 13:21:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-06 11:41:57.749956
- Title: Symbolic Regression is NP-hard
- Title(参考訳): 記号回帰はnpハードである
- Authors: Marco Virgolin, Solon P. Pissis
- Abstract要約: シンボリック回帰(シンボリックレグレッション、英: Symbolic regression、SR)は、数学的表現の形でデータのモデルを学ぶタスクである。
SRは計算集約的なタスクであることを示す。
SR が NP-hard であることを示すことによって、答えがおそらく負であることを示す証拠を提供する。
- 参考スコア(独自算出の注目度): 1.5330785573575156
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Symbolic regression (SR) is the task of learning a model of data in the form
of a mathematical expression. By their nature, SR models have the potential to
be accurate and human-interpretable at the same time. Unfortunately, finding
such models, i.e., performing SR, appears to be a computationally intensive
task. Historically, SR has been tackled with heuristics such as greedy or
genetic algorithms and, while some works have hinted at the possible hardness
of SR, no proof has yet been given that SR is, in fact, NP-hard. This begs the
question: Is there an exact polynomial-time algorithm to compute SR models? We
provide evidence suggesting that the answer is probably negative by showing
that SR is NP-hard.
- Abstract(参考訳): シンボリック回帰(シンボリックレグレッション、英: Symbolic regression、SR)は、数学的表現の形でデータのモデルを学ぶタスクである。
その性質上、SRモデルは正確で人間に解釈できる可能性を持っている。
残念なことに、そのようなモデル、すなわちSRを実行することは、計算集約的なタスクである。
歴史的に、SRは欲求や遺伝的アルゴリズムのようなヒューリスティックな手法に取り組んでおり、SRの硬さを示唆する研究もあるが、実際にはNPハードであることの証明は与えられていない。
SRモデルを計算するための正確な多項式時間アルゴリズムはあるだろうか?
SR が NP ハードであることを示すことによって、答えがおそらく負であることを示す証拠を提供する。
関連論文リスト
- NSSR-DIL: Null-Shot Image Super-Resolution Using Deep Identity Learning [0.02932486408310998]
ISRタスクを学習するために,画像データセットに依存しない新しいISRアルゴリズムを提案する。
本稿では,劣化モデルと逆劣化モデルとの同一性を利用したDeep Identity Learningを紹介する。
提案したNSSR-DILモデルは、少なくとも10のオーダーで計算資源を少なくし、ベンチマークISRデータセット上での競合性能を示す。
論文 参考訳(メタデータ) (2024-09-17T03:43:07Z) - States Hidden in Hidden States: LLMs Emerge Discrete State Representations Implicitly [72.24742240125369]
本稿では,チェーン・オブ・ステップ・バイ・ステップの解に頼らずに,拡張された計算列を実行する本質的な能力を明らかにする。
注目すべきは、最も先進的なモデルでは、2桁の加算結果を直接出力できることだ。
論文 参考訳(メタデータ) (2024-07-16T06:27:22Z) - Prove Symbolic Regression is NP-hard by Symbol Graph [5.68255131309463]
本稿では,数式空間全体の包括的表現としての記号グラフの概念を紹介する。
我々は適度に調整されたSteiner Arborescence (DCSAP) を同定する。
NPハードであることが証明されたDCSAPの複雑さは、直接的に、SR問題のNPハードの性質を意味する。
論文 参考訳(メタデータ) (2024-04-22T01:48:58Z) - On the Representational Capacity of Recurrent Neural Language Models [56.19166912044362]
計算時間を持つ有理重み付きRLMは、有理重み付き遷移を持つ決定論的確率的チューリングマシン(PTM)をシミュレートできることを示す。
また, 実時間計算の制約下では, 決定論的実時間有理PTMをシミュレートできることを示した。
論文 参考訳(メタデータ) (2023-10-19T17:39:47Z) - Active Learning in Symbolic Regression with Physical Constraints [0.4037357056611557]
進化的記号回帰(SR)は記号方程式をデータに適合させ、簡潔な解釈可能なモデルを与える。
本研究では,身体的制約のあるアクティブな学習環境において,どのデータを収集すべきかをSRを用いて提案する。
論文 参考訳(メタデータ) (2023-05-17T17:07:25Z) - SRFormerV2: Taking a Closer Look at Permuted Self-Attention for Image Super-Resolution [74.48610723198514]
SRFormerは、大きなウィンドウの自己注意の恩恵を享受できる、単純だが斬新な方法である。
我々のSRFormerはUrban100データセットで33.86dBのPSNRスコアを獲得し、SwinIRよりも0.46dB高い。
実験により, SRFormerV2と呼ばれるスケールモデルにより, 結果がさらに向上し, 最先端の達成が期待できることがわかった。
論文 参考訳(メタデータ) (2023-03-17T02:38:44Z) - Rethinking Symbolic Regression Datasets and Benchmarks for Scientific
Discovery [12.496525234064888]
本稿では,シンボリック回帰(SR)のデータセットと評価基準を再検討する。
科学的発見のための象徴的回帰(SRSD)のパフォーマンスを議論するために120個のデータセットを再現する。
論文 参考訳(メタデータ) (2022-06-21T17:15:45Z) - Revisiting RCAN: Improved Training for Image Super-Resolution [94.8765153437517]
一般的なRCANモデルを再検討し、SRにおける異なるトレーニングオプションの効果について検討する。
RCAN は CNN をベースとした SR アーキテクチャのほぼすべてにおいて,標準ベンチマークで RCAN 以降のアーキテクチャよりも優れるか,あるいは適合することを示す。
論文 参考訳(メタデータ) (2022-01-27T02:20:11Z) - StackRec: Efficient Training of Very Deep Sequential Recommender Models
by Layer Stacking [34.46361802163175]
層スタッキングによる深層SRモデルのためのシンプルで非常に効率的なトレーニングフレームワークであるStackRecを紹介します。
まず、よく訓練された深層SRモデルにおける残留層/ブロックが同様の分布を有するという重要な洞察を提供する。
そこで本研究では,事前学習した残存層/ブロックを段階的に積み重ね,より深く,より訓練しやすいSRモデルを提案する。
論文 参考訳(メタデータ) (2020-12-14T14:41:43Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z) - Closed-loop Matters: Dual Regression Networks for Single Image
Super-Resolution [73.86924594746884]
ディープニューラルネットワークは、画像超解像において有望な性能を示した。
これらのネットワークは、低分解能(LR)画像から高分解能(HR)画像への非線形マッピング関数を学習する。
本稿では,可能な関数の空間を削減するために,LRデータに新たな制約を導入することで,二重回帰手法を提案する。
論文 参考訳(メタデータ) (2020-03-16T04:23:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。