論文の概要: 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)による同定可能な情報源の質的特徴を定量的に評価した。

関連論文リスト

• An efficient construction of Raz's two-source randomness extractor with improved parameters [0.14999444543328289]
  2ソースランダムネス抽出器は弱いランダムソースをほぼ完全なランダム数に蒸留する。 ラズの抽出器は、1つの源がその長さに比例する線形のミンエントロピーを持つような環境でこれを初めて達成した。 本稿では、準線形計算時間を持つRazの抽出器の改良版と、エントロピー要求を低減した新しい解析定理を提案する。
  論文  参考訳（メタデータ） (2025-06-18T15:18:57Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  この研究において、ラベルは(ガウス)$d$-次元入力にのみ依存し、低次元$r = O_d(1)$部分空間への射影を通して得られる。 生成的跳躍指数 $kstar$, [Damian et al.'24] から生成的指数の自然拡張をマルチインデックス設定に導入する。
  論文  参考訳（メタデータ） (2025-06-05T18:34:56Z)
• Single-Sample and Robust Online Resource Allocation [14.956072215503797]
  本稿では,オンラインリソースアロケーションのための新しい指数価格アルゴリズムを提案する。 外れ値モデルと値拡張モデルにおける汚職に対して堅牢である。 アイテムの価格設定にオンライン学習アルゴリズムを使用する従来のアプローチから運用されている。
  論文  参考訳（メタデータ） (2025-05-05T18:48:11Z)
• A finite time analysis of distributed Q-learning [6.663174194579773]
  マルチエージェント強化学習(MARL)は、単一エージェント強化学習(RL)の適用において達成された経験的成功によって、目覚ましい関心の高まりを目撃している。 本研究では,多くのエージェントが局所報酬の平均値である中央報酬関数にアクセスせずに逐次意思決定問題を協調的に解決する分散Q-ラーニングシナリオについて考察する。
  論文  参考訳（メタデータ） (2024-05-23T00:52:38Z)
• 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)

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

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