論文の概要: Multicalibrated Partitions for Importance Weights
- arxiv url: http://arxiv.org/abs/2103.05853v1
- Date: Wed, 10 Mar 2021 03:32:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-12 00:38:51.159446
- Title: Multicalibrated Partitions for Importance Weights
- Title(参考訳): 重要重量のマルチキャリブレーション分割
- Authors: Parikshit Gopalan, Omer Reingold, Vatsal Sharan, Udi Wieder
- Abstract要約: 重要度重みは、多くの分野、特に統計学と機械学習において、基本的な役割を果たす。
最大エントロピー法では、集合の基底的真理の重みの平均が明らかに大きい場合でも、計算量$ に対して高い平均スコアを割り当てることができない可能性がある。
標準学習可能性仮定の下でこれらの境界を満たす重みを計算する効率的なアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 17.1726078570842
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The ratio between the probability that two distributions $R$ and $P$ give to
points $x$ are known as importance weights or propensity scores and play a
fundamental role in many different fields, most notably, statistics and machine
learning. Among its applications, importance weights are central to domain
adaptation, anomaly detection, and estimations of various divergences such as
the KL divergence. We consider the common setting where $R$ and $P$ are only
given through samples from each distribution. The vast literature on estimating
importance weights is either heuristic, or makes strong assumptions about $R$
and $P$ or on the importance weights themselves.
In this paper, we explore a computational perspective to the estimation of
importance weights, which factors in the limitations and possibilities
obtainable with bounded computational resources. We significantly strengthen
previous work that use the MaxEntropy approach, that define the importance
weights based on a distribution $Q$ closest to $P$, that looks the same as $R$
on every set $C \in \mathcal{C}$, where $\mathcal{C}$ may be a huge collection
of sets. We show that the MaxEntropy approach may fail to assign high average
scores to sets $C \in \mathcal{C}$, even when the average of ground truth
weights for the set is evidently large. We similarly show that it may
overestimate the average scores to sets $C \in \mathcal{C}$. We therefore
formulate Sandwiching bounds as a notion of set-wise accuracy for importance
weights. We study these bounds to show that they capture natural completeness
and soundness requirements from the weights. We present an efficient algorithm
that under standard learnability assumptions computes weights which satisfy
these bounds. Our techniques rely on a new notion of multicalibrated partitions
of the domain of the distributions, which appear to be useful objects in their
own right.
- Abstract(参考訳): 2つの分布が$R$と$P$をポイントに与える確率の比率は、重み付けまたは確率スコアとして知られ、多くの異なる分野、特に統計学と機械学習において基本的な役割を果たす。
その応用中、重要度重みはドメイン適応、異常検出、klダイバージェンスのような様々な多様性の推定の中心である。
私たちは、$R$と$P$が各ディストリビューションのサンプルからのみ与えられる共通の設定を検討します。
重みの見積に関する膨大な文献は、ヒューリスティックなものか、R$とP$に関する強い仮定、あるいは重要性の重みそのものに関するものである。
本稿では,重要度重みの推定に対する計算的視点を考察し,境界のある計算資源で得られる限界と可能性の要因について考察する。
我々は MaxEntropy アプローチを用いた以前の研究を大幅に強化し、$Q$ を$P$ に最も近い分布で定義し、これはすべての集合 $C \in \mathcal{C}$ に対して$R$ と同じように見えるが、$\mathcal{C}$ は集合の巨大な集合であるかもしれない。
マックスエントロピー法は、集合の基底真理重みの平均が明らかに大きい場合でも、$C \in \mathcal{C}$の集合に高い平均スコアを割り当てることに失敗することを示した。
同様に、平均スコアは$C \in \mathcal{C}$と過大評価される可能性がある。
したがって、サンドウィッチ境界を重み付けのセットワイズ精度の概念として定式化する。
これらの境界について検討し,重みから自然完全性と音質要件を捉えた。
標準学習可能性仮定の下でこれらの境界を満たす重みを計算する効率的なアルゴリズムを提案する。
我々の手法は、分布の領域の多重校正分割という新しい概念に依存しており、これはそれ自体が有用であるように見える。
関連論文リスト
- TIC-TAC: A Framework To Learn And Evaluate Your Covariance [119.82937345718378]
State-of-the-art method predict the mean $f_theta(x)$ and covariance $textrmCov(f_theta(x))$ of the target distribution through the two neural network using the negative log-likelihood。
1)予測共分散は予測平均のランダム性を真に捉えているのか?
論文 参考訳(メタデータ) (2023-10-29T09:54:03Z) - Compressed and distributed least-squares regression: convergence rates
with applications to Federated Learning [9.31522898261934]
機械学習の勾配アルゴリズムに対する圧縮の影響について検討する。
いくつかの非バイアス圧縮演算子間の収束率の差を強調した。
我々はその結果を連合学習の事例にまで拡張する。
論文 参考訳(メタデータ) (2023-08-02T18:02:00Z) - Value-aware Importance Weighting for Off-policy Reinforcement Learning [11.3798693158017]
重要度サンプリングは、強化学習における非政治予測の根底にある中心的な考え方である。
本研究では,非政治学習におけるサンプルの修正のために,より広範な重み付けを考察する。
このような重みの計算方法が導出され、結果として生じる重みの重要特性が詳細に説明される。
論文 参考訳(メタデータ) (2023-06-27T17:05:22Z) - There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning
for Mazes [64.05903267230467]
相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。
場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
論文 参考訳(メタデータ) (2022-06-09T04:23:26Z) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳(メタデータ) (2022-05-28T05:13:45Z) - Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。
我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
論文 参考訳(メタデータ) (2022-02-16T16:24:31Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳(メタデータ) (2021-10-19T17:43:50Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Leveraged Matrix Completion with Noise [84.20092979053119]
未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry.
我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
論文 参考訳(メタデータ) (2020-11-11T16:25:45Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。