論文の概要: Instance Based Approximations to Profile Maximum Likelihood
- arxiv url: http://arxiv.org/abs/2011.02761v1
- Date: Thu, 5 Nov 2020 11:17:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-29 11:47:17.789620
- Title: Instance Based Approximations to Profile Maximum Likelihood
- Title(参考訳): 最大確率のプロファイルに対するインスタンスベース近似
- Authors: Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
- Abstract要約: プロファイル最大度(PML)分布を近似計算するアルゴリズムを提案する。
PseudoPMLは、幅広い対称特性のクラスを推定するフレームワークである。
- 参考スコア(独自算出の注目度): 33.51964370430905
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we provide a new efficient algorithm for approximately
computing the profile maximum likelihood (PML) distribution, a prominent
quantity in symmetric property estimation. We provide an algorithm which
matches the previous best known efficient algorithms for computing approximate
PML distributions and improves when the number of distinct observed frequencies
in the given instance is small. We achieve this result by exploiting new
sparsity structure in approximate PML distributions and providing a new matrix
rounding algorithm, of independent interest. Leveraging this result, we obtain
the first provable computationally efficient implementation of PseudoPML, a
general framework for estimating a broad class of symmetric properties.
Additionally, we obtain efficient PML-based estimators for distributions with
small profile entropy, a natural instance-based complexity measure. Further, we
provide a simpler and more practical PseudoPML implementation that matches the
best-known theoretical guarantees of such an estimator and evaluate this method
empirically.
- Abstract(参考訳): 本稿では,pml分布を近似的に計算する新しい効率的なアルゴリズムを提案する。
本稿では,PML分布を近似的に計算するアルゴリズムと一致し,各インスタンスにおける観測周波数の差が小さい場合に改善するアルゴリズムを提案する。
本研究では, PML分布に近似した新しい空間構造を利用して, 独立性のある行列ラウンドリングアルゴリズムを提案する。
この結果を利用して、幅広い対称特性のクラスを推定する一般的なフレームワークであるPseudoPMLの最初の証明可能な計算効率のよい実装を得る。
さらに,プロファイラエントロピーが小さい分布に対する効率的なpmlベースの推定器を得る。
さらに,このような推定器の最もよく知られた理論的な保証に合致する,よりシンプルで実用的なpseudompml実装を提供し,経験的に評価する。
関連論文リスト
- Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳(メタデータ) (2023-07-08T15:41:48Z) - Algorithme EM r\'egularis\'e [0.0]
本稿では,より少ないサンプルサイズに対応するために,事前知識を効率的に活用するEMアルゴリズムの正規化バージョンを提案する。
実データを用いた実験では,クラスタリングのための提案アルゴリズムの性能が向上した。
論文 参考訳(メタデータ) (2023-07-04T23:19:25Z) - Provably Efficient Representation Learning with Tractable Planning in
Low-Rank POMDP [81.00800920928621]
部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究
まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。
次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
論文 参考訳(メタデータ) (2023-06-21T16:04:03Z) - Orthogonal Polynomials Approximation Algorithm (OPAA):a functional
analytic approach to estimating probability densities [0.0]
新しい直交多項式近似アルゴリズム(OPAA)を提案する。
OPAAは機能解析手法を用いて確率分布を推定する。
後部の正規化重量を推定するために応用できる。
論文 参考訳(メタデータ) (2022-11-16T00:51:00Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳(メタデータ) (2022-09-16T19:15:50Z) - Optimizing Objective Functions from Trained ReLU Neural Networks via
Sampling [0.0]
本稿では、ReLUアクティベーションを用いたトレーニングニューラルネットワークを最適化する、スケーラブルでサンプリングベースのアルゴリズムを提案する。
本稿ではまず,ReLUニューラルネットワークのピースワイズ線形構造を利用した反復アルゴリズムを提案する。
次に、各反復で計算されたLPソリューションの近傍を探索することで、このアプローチを拡張します。
論文 参考訳(メタデータ) (2022-05-27T18:35:48Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳(メタデータ) (2020-12-04T15:36:29Z) - Efficient Data-Dependent Learnability [8.766022970635898]
予測正規化最大可能性(pNML)アプローチは、最近、バッチ学習問題に対する min-max 最適解として提案されている。
ニューラルネットワークに適用すると、この近似が分散外例を効果的に検出できることが示される。
論文 参考訳(メタデータ) (2020-11-20T10:44:55Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳(メタデータ) (2020-11-05T08:04:34Z) - A General Framework for Symmetric Property Estimation [35.14819168275207]
経験的推定を行う容易な領域と,より複雑な推定器を必要とする困難な領域を同定する。
この難しい領域におけるプロファイル最大可能性(PML)分布 citeADOS16 を概算することにより、多くの特性に対して最適なサンプル複雑性を持つ対称特性推定フレームワークが得られることを示す。
論文 参考訳(メタデータ) (2020-03-02T13:00:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。