論文の概要: It's Not What Machines Can Learn, It's What We Cannot Teach

• arxiv url: http://arxiv.org/abs/2002.09398v2
• Date: Sun, 28 Jun 2020 16:43:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 00:08:30.295349
• Title: It's Not What Machines Can Learn, It's What We Cannot Teach
• Title（参考訳）: 機械が学べるものではなく、私たちが学べないもの
• Authors: Gal Yehuda, Moshe Gabel, Assaf Schuster
• Abstract要約: 対象分布からの高密度な一様サンプリングのトレーニングを必要とする機械学習アプローチは、計算的に難しい問題を解くには利用できないことを示す。 この結果から,対象分布からの高密度な一様サンプリングの訓練を必要とする機械学習手法は,計算上の難解な問題を解くには利用できないことが示唆された。
• 参考スコア（独自算出の注目度）: 12.85437822164676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Can deep neural networks learn to solve any task, and in particular problems of high complexity? This question attracts a lot of interest, with recent works tackling computationally hard tasks such as the traveling salesman problem and satisfiability. In this work we offer a different perspective on this question. Given the common assumption that $\textit{NP} \neq \textit{coNP}$ we prove that any polynomial-time sample generator for an $\textit{NP}$-hard problem samples, in fact, from an easier sub-problem. We empirically explore a case study, Conjunctive Query Containment, and show how common data generation techniques generate biased datasets that lead practitioners to over-estimate model accuracy. Our results suggest that machine learning approaches that require training on a dense uniform sampling from the target distribution cannot be used to solve computationally hard problems, the reason being the difficulty of generating sufficiently large and unbiased training sets.
• Abstract（参考訳）: ディープニューラルネットワークは、どんなタスクでも、特に複雑性の高い問題を解くことができるだろうか? この問題は、旅行セールスマン問題や満足度といった計算的に困難なタスクに取り組む最近の研究によって、多くの関心を集めている。 この作業では、この質問に対する異なる視点を提供します。 一般的な仮定として、$\textit{NP} \neq \textit{coNP}$は$\textit{NP}$-hard問題サンプルに対する多項式時間サンプルジェネレータであり、実際、より簡単な部分確率から得られる。 我々は経験的にケーススタディ、結合型クエリ封じ込めを探索し、一般的なデータ生成手法がバイアス付きデータセットを生成し、実践者がモデル精度を過大に見積もる方法を示す。 この結果から,対象分布から高密度な一様サンプリングの学習を必要とする機械学習手法は,十分に大規模かつ偏りのない学習セットを生成するのが難しいため,計算的に難解な問題を解くには利用できないことが示唆された。

関連論文リスト

• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  条件分布は機械学習の中心的な問題です ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。 我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
  論文  参考訳（メタデータ） (2024-10-03T16:12:59Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  ニューラルネットワークモデルは、Kolmogorov複雑性を使って形式化された、同じ好みを共有している、と我々は主張する。 実験の結果、事前訓練された言語モデルでも、低複雑さのシーケンスを生成するのが好まれることがわかった。 これらの観察は、ますます小さな機械学習モデルで異なるように見える問題を統一する深層学習の傾向を正当化する。
  論文  参考訳（メタデータ） (2023-04-11T17:22:22Z)
• On Inductive Biases for Machine Learning in Data Constrained Settings [0.0]
  この論文は、データ制約された設定で表現力のあるモデルを学ぶという問題に対する異なる答えを探求する。 ニューラルネットワークを学ぶために、大きなデータセットに頼るのではなく、データ構造を反映した既知の関数によって、いくつかのモジュールを置き換えるつもりです。 我々のアプローチは「帰納的バイアス」のフードの下に置かれており、これは探索するモデルの空間を制限する手元にあるデータの仮説として定義することができる。
  論文  参考訳（メタデータ） (2023-02-21T14:22:01Z)
• Is Stochastic Gradient Descent Near Optimal? [0.0]
  本研究では,多数のサンプルとクエリの総数を用いて,勾配勾配勾配の誤差が小さいことを示す。 このことは、SGDがJoen & Van Roy (arXiv:2203.00246) の情報理論的なサンプル複雑性境界を計算的に効率よく達成していることを示唆している。
  論文  参考訳（メタデータ） (2022-09-18T18:26:43Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks [16.64116123743938]
  我々は、Sigmoid, rectified linear unit (ReLU) を用いた2層ニューラルネットワークの探索問題を考える。 そして、その境界を利用して、Emphfat-shattering dimensionを通じてそのようなネットワークの保証を確立する。 特に、我々の境界はサンプルの複雑さも良い(低次数$$d$のポリノミアル)。
  論文  参考訳（メタデータ） (2021-03-02T17:36:03Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)

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

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