論文の概要: Source Identification for Mixtures of Product Distributions

• arxiv url: http://arxiv.org/abs/2012.14540v1
• Date: Tue, 29 Dec 2020 00:21:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2021-04-19 07:32:17.321450
• Title: Source Identification for Mixtures of Product Distributions
• Title（参考訳）: 製品分布の混合成分の源同定
• Authors: Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
• Abstract要約: 我々は$ n$ビットで$ k$製品分布の混合物のソース識別のためのアルゴリズムを与える。 その結果,これらの混合物のソース同定の計算複雑性に初めて明示的な境界が与えられた。
• 参考スコア（独自算出の注目度）: 4.893896929103367
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give an algorithm for source identification of a mixture of $k$ product distributions on $n$ bits. This is a fundamental problem in machine learning with many applications. Our algorithm identifies the source parameters of an identifiable mixture, given, as input, approximate values of multilinear moments (derived, for instance, from a sufficiently large sample), using $2^{O(k^2)} n^{O(k)}$ arithmetic operations. Our result is the first explicit bound on the computational complexity of source identification of such mixtures. The running time improves previous results by Feldman, O'Donnell, and Servedio (FOCS 2005) and Chen and Moitra (STOC 2019) that guaranteed only learning the mixture (without parametric identification of the source). Our analysis gives a quantitative version of a qualitative characterization of identifiable sources that is due to Tahmasebi, Motahari, and Maddah-Ali (ISIT 2018).
• Abstract（参考訳）: 我々は、$n$ビット上の$k$の製品分布の混合物のソース識別のためのアルゴリズムを与える。 これは、多くのアプリケーションによる機械学習の根本的な問題である。 提案手法は, 2^{o(k^2)} n^{o(k)}$演算演算を用いて,複数線形モーメントの近似値(例えば,十分大きなサンプルから導出する)を入力として, 同定可能な混合物のソースパラメータを同定する。 その結果,これらの混合物のソース同定の計算複雑性に初めて明示的な境界が与えられた。 Feldman氏、O'Donnell氏、Servedio氏(FOCS 2005)、Chen and Moitra氏(STOC 2019)による以前の結果の改善は、(ソースのパラメトリック識別なしで)混合を学習することのみを保証する。 本分析は,tahmasebi,motahari,maddah-ali(isit 2018)による同定可能な情報源の質的特徴を定量的に評価した。

関連論文リスト

• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• Learning Shared Kernel Models: the Shared Kernel EM algorithm [0.0]
  予測最大化 (EM) は有限混合分布のパラメータを推定するための教師なし学習法である。 まず、複数の目標追跡の分野からのデータアソシエーションのアイデアを用いた標準EMアルゴリズムの再帰について述べる。 この手法は、共有カーネルモデルに対して、ほとんど知られていないがより一般的なタイプの教師付きEMアルゴリズムに適用される。
  論文  参考訳（メタデータ） (2022-05-15T10:10:08Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• One to Multiple Mapping Dual Learning: Learning Multiple Sources from One Mixed Signal [38.00036571066844]
  単一チャネルブラインドソース分離(SCBSS)は、単一センサによって収集された混合信号から複数のソースを分離することを指す。 本稿では,並列二重生成逆数ネットワーク(PDualGAN)を設計し,複数のソースを混合体から分離するアルゴリズムを提案する。 このアルゴリズムは、線形瞬時混合モデルや畳み込み混合モデルのような混合モデルに適用できる。
  論文  参考訳（メタデータ） (2021-10-13T08:34:02Z)
• Unsupervised Multi-source Domain Adaptation Without Access to Source Data [58.551861130011886]
  Unsupervised Domain Adaptation (UDA)は、ラベル付きソースドメインから知識を転送することで、ラベル付きドメインの予測モデルを学ぶことを目的としている。 本稿では,ソースモデルと適切な重み付けを自動的に組み合わせ,少なくとも最良のソースモデルと同等の性能を発揮する新しい効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-05T10:45:12Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)
• Algebraic and Analytic Approaches for Parameter Learning in Mixture Models [66.96778152993858]
  1次元の混合モデルにおけるパラメータ学習のための2つの異なるアプローチを提案する。 これらの分布のいくつかについては、パラメータ推定の最初の保証を示す。
  論文  参考訳（メタデータ） (2020-01-19T05:10:56Z)

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

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