論文の概要: Symbolic Regression is NP-hard
- arxiv url: http://arxiv.org/abs/2207.01018v1
- Date: Sun, 3 Jul 2022 12:10:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-05 12:38:14.353768
- 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 ハードであることを示すことによって、答えがおそらく負であることを示す証拠を提供する。
関連論文リスト
- GFN-SR: Symbolic Regression with Generative Flow Networks [0.9208007322096533]
近年,DSR(Deep symbolic regression)がこの分野の一般的な手法として登場している。
ディープラーニングを用いてSRにアプローチするための代替フレームワーク(GFN-SR)を提案する。
GFN-SRは多種多様な最適表現を生成することができる。
論文 参考訳(メタデータ) (2023-12-01T07:38:05Z) - On the Representational Capacity of Recurrent Neural Language Models [61.38536173209874]
計算時間を持つ有理重み付きRLMは、有理重み付き遷移を持つ決定論的確率的チューリングマシン(PTM)をシミュレートできることを示す。
また, 実時間計算の制約下では, 決定論的実時間有理PTMをシミュレートできることを示した。
論文 参考訳(メタデータ) (2023-10-19T17:39:47Z) - Active Learning in Symbolic Regression with Physical Constraints [0.0]
進化的記号回帰(SR)は記号方程式をデータに適合させ、簡潔な解釈可能なモデルを与える。
本研究では,身体的制約のあるアクティブな学習環境において,どのデータを収集すべきかをSRを用いて提案する。
論文 参考訳(メタデータ) (2023-05-17T17:07:25Z) - SRFormer: Permuted Self-Attention for Single Image Super-Resolution [103.59735102924283]
以前の研究では、Transformerベースの画像超解像モデル(例えばSwinIR)のウィンドウサイズを増大させることで、モデルの性能は大幅に向上するが、計算オーバーヘッドもかなり大きいことが示されている。
SRFormerは、大きなウィンドウ自己注意の利点を享受できるが、計算負担がさらに少ない、単純だが斬新な方法である。
我々のPSAは単純で、ウィンドウの自己注意に基づいて既存の超解像ネットワークに容易に適用できる。
論文 参考訳(メタデータ) (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) - DynaVSR: Dynamic Adaptive Blind Video Super-Resolution [60.154204107453914]
DynaVSRは、現実世界のビデオSRのための新しいメタラーニングベースのフレームワークである。
様々な種類の合成ボケカーネルを備えたマルチフレームダウンスケーリングモジュールをトレーニングし、入力認識適応のためのビデオSRネットワークとシームレスに結合する。
実験結果から,DynaVSRは最先端のビデオSRモデルの性能を一定に向上することがわかった。
論文 参考訳(メタデータ) (2020-11-09T15:07:32Z) - A General Framework for Stable Roommates Problems using Answer Set
Programming [1.6344851071810071]
安定ルームメイト問題(SR)は、ルームメイトとして他のエージェントよりもエージェントの好みが特徴である。
SRTI-ASPと呼ばれる形式的なフレームワークを導入する。
論文 参考訳(メタデータ) (2020-08-07T09:12:36Z) - Closed-loop Matters: Dual Regression Networks for Single Image
Super-Resolution [73.86924594746884]
ディープニューラルネットワークは、画像超解像において有望な性能を示した。
これらのネットワークは、低分解能(LR)画像から高分解能(HR)画像への非線形マッピング関数を学習する。
本稿では,可能な関数の空間を削減するために,LRデータに新たな制約を導入することで,二重回帰手法を提案する。
論文 参考訳(メタデータ) (2020-03-16T04:23:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。