論文の概要: 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 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) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳(メタデータ) (2022-04-06T13:50:33Z) - Clustering Mixtures with Almost Optimal Separation in Polynomial Time [21.509452343745252]
高次元における平均分離ガウス多様体のクラスタリング混合問題について考察する。
Delta = Theta (sqrtlog k)$ の分離は必要であり、良いクラスタリングを回復するのに十分である。
我々は多くのサンプルと時間を要し、優れたクラスタリングをうまく回復できるアルゴリズムを提示する。
論文 参考訳(メタデータ) (2021-12-01T18:34:09Z) - Deep Transfer Learning for Multi-source Entity Linkage via Domain
Adaptation [63.24594955429465]
マルチソースエンティティリンクは、データのクリーニングやユーザ縫合といった、高インパクトなアプリケーションにおいて重要である。
AdaMELは、多ソースエンティティリンクを実行するための一般的なハイレベルな知識を学ぶディープトランスファー学習フレームワークである。
本フレームワークは,教師付き学習に基づく平均的手法よりも8.21%向上した最先端の学習結果を実現する。
論文 参考訳(メタデータ) (2021-10-27T15:20:41Z) - One to Multiple Mapping Dual Learning: Learning Multiple Sources from
One Mixed Signal [38.00036571066844]
単一チャネルブラインドソース分離(SCBSS)は、単一センサによって収集された混合信号から複数のソースを分離することを指す。
本稿では,並列二重生成逆数ネットワーク(PDualGAN)を設計し,複数のソースを混合体から分離するアルゴリズムを提案する。
このアルゴリズムは、線形瞬時混合モデルや畳み込み混合モデルのような混合モデルに適用できる。
論文 参考訳(メタデータ) (2021-10-13T08:34:02Z) - Learning Gaussian Mixtures with Generalised Linear Models: Precise
Asymptotics in High-dimensions [79.35722941720734]
多クラス分類問題に対する一般化線形モデルは、現代の機械学習タスクの基本的な構成要素の1つである。
実験的リスク最小化による高次元推定器の精度を実証する。
合成データの範囲を超えて我々の理論をどのように適用できるかを論じる。
論文 参考訳(メタデータ) (2021-06-07T16:53:56Z) - "Don't quote me on that": Finding Mixtures of Sources in News Articles [85.92467549469147]
各ソースのtextitaffiliationとtextitroleに基づいてソースのオントロジーラベリングシステムを構築します。
これらの属性を名前付きソースに推論し、ニュース記事をこれらのソースの混合物として記述する確率モデルを構築します。
論文 参考訳(メタデータ) (2021-04-19T21:57:11Z) - Unsupervised Multi-source Domain Adaptation Without Access to Source
Data [58.551861130011886]
Unsupervised Domain Adaptation (UDA)は、ラベル付きソースドメインから知識を転送することで、ラベル付きドメインの予測モデルを学ぶことを目的としている。
本稿では,ソースモデルと適切な重み付けを自動的に組み合わせ,少なくとも最良のソースモデルと同等の性能を発揮する新しい効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-04-05T10:45:12Z) - Brain Image Synthesis with Unsupervised Multivariate Canonical
CSC$\ell_4$Net [122.8907826672382]
我々は,新しいCSC$ell_4$Netを用いて,イントレとイントラモーダルの両方にまたがる専用特徴を学習することを提案する。
論文 参考訳(メタデータ) (2021-03-22T05:19:40Z) - MISO-wiLDCosts: Multi Information Source Optimization with Location
Dependent Costs [0.0]
本稿では,複数の情報ソースに対するブラックボックス最適化について述べる。
i) Augmented Gaussian Process、(i) Augmented Gaussian Process、(i) Augmented Gaussian Process、(i) Augmented Gaussian Process、(i) Augmented Gaussian Process、(ii) Augmented Gaussian Processは、各ソースの位置依存コストをモデル化する。
論文 参考訳(メタデータ) (2021-02-09T17:04:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。