論文の概要: Learning with distributional inverters

• arxiv url: http://arxiv.org/abs/2112.12340v1
• Date: Thu, 23 Dec 2021 03:20:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-24 16:25:24.463104
• Title: Learning with distributional inverters
• Title（参考訳）: 分散インバータによる学習
• Authors: Eric Binnendyk, Marco Carmosino, Antonina Kolokolova, Ramyaa Ramyaa, Manuel Sabin
• Abstract要約: 我々はFurst et al., 1991 を一般化し、サンプリング可能な分布上で概念クラスを学ぶことから、一様分布上で同じ概念クラスを学ぶことへ還元する。 この還元は、$mu$ のサンプルがターゲット概念クラスに含まれ、1989年の Impaglia & Luby の意味で効率的に可逆であるときに成功する。
• 参考スコア（独自算出の注目度）: 3.0011388623776023
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We generalize the "indirect learning" technique of Furst et. al., 1991 to reduce from learning a concept class over a samplable distribution $\mu$ to learning the same concept class over the uniform distribution. The reduction succeeds when the sampler for $\mu$ is both contained in the target concept class and efficiently invertible in the sense of Impagliazzo & Luby, 1989. We give two applications. - We show that AC0[q] is learnable over any succinctly-described product distribution. AC0[q] is the class of constant-depth Boolean circuits of polynomial size with AND, OR, NOT, and counting modulo $q$ gates of unbounded fanins. Our algorithm runs in randomized quasi-polynomial time and uses membership queries. - If there is a strongly useful natural property in the sense of Razborov & Rudich 1997 -- an efficient algorithm that can distinguish between random strings and strings of non-trivial circuit complexity -- then general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time, given membership queries to the target function
• Abstract（参考訳）: 我々はFurstらの"間接学習"技術を一般化する。 1991年、一様分布上の同じ概念クラスを学ぶために、samplable 分布上の概念クラスを学習することから$\mu$ を減じる。 この還元は、$\mu$ のサンプルがターゲット概念クラスに含まれ、1989年の Impagliazzo & Luby の意味で効率的に可逆であるときに成功する。 2つのアプリケーションを与えます。 - ac0[q]が簡潔に記述された製品分布よりも学習可能であることを示す。 AC0[q] は多項式サイズが AND, OR, NOT で、無有界ファインのモジュロ$q$ゲートを数える定数深さブール回路のクラスである。 我々のアルゴリズムはランダム化された準多項式時間で動作し、メンバシップクエリを使用する。 -ラズボロフ&ルディッヒ1997 -- ランダム弦と非自明な回路複雑性の文字列を区別できる効率的なアルゴリズム -- の意味で、非常に有用な自然特性がある場合、一般多項式サイズのブール回路は、対象関数へのメンバシップクエリが与えられた場合、ランダム化された多項式時間で、任意の効率的なsamplable分布上で学習することができる。

関連論文リスト

• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums [0.9208007322096532]
  量子回路の族は、実際には記号経路積分によって時間内にシミュレートできることを示す。 したがって、このクラスの回路時間の効率的なシミュラビリティに関する開予想を解く。
  論文  参考訳（メタデータ） (2024-08-05T18:56:20Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Generalized Differentiable RANSAC [95.95627475224231]
  $nabla$-RANSACは、ランダム化された堅牢な推定パイプライン全体を学ぶことができる、微分可能なRANSACである。 $nabla$-RANSACは、精度という点では最先端のシステムよりも優れているが、精度は低い。
  論文  参考訳（メタデータ） (2022-12-26T15:13:13Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Turing-Universal Learners with Optimal Scaling Laws [2.7485183218472016]
  我々は,全ての学習アルゴリズムにおいて,最適な分布依存率を実現する「ユニバーサル学習者」アルゴリズムの存在を観察する。 構成そのものは、レヴィンの普遍探索の単純な拡張である(Levin, 1973)
  論文  参考訳（メタデータ） (2021-11-09T18:44:35Z)
• Learning algorithms from circuit lower bounds [0.0]
  構成回路下界の様々な概念から効率的な学習アルゴリズムの既知の構成を再考する。 難しい問題を解こうとする多くのpサイズの回路の誤りを、特定のインタラクティブな方法で効率的に見つけることができれば、pサイズの回路は一様分布を通じてPACを学ぶことができることを証明します。
  論文  参考訳（メタデータ） (2020-12-28T04:47:36Z)
• Theory and Algorithms for Shapelet-based Multiple-Instance Learning [5.08418565337126]
  本稿では,データ単位がバッグと呼ばれるインスタンスから構成されるMultiple-Instance Learning(MIL)の新たな定式化を提案する。 目標は、"shapelet"(またはパターン)との類似性に基づいて、バッグの優れた分類器を見つけることである。 私たちの定式化では、すべての可能なので、したがって無限に多くのシェイプレットを使い、よりリッチな分類器のクラスを生み出す。
  論文  参考訳（メタデータ） (2020-05-31T17:10:59Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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