論文の概要: 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}$と過大評価される可能性がある。
したがって、サンドウィッチ境界を重み付けのセットワイズ精度の概念として定式化する。
これらの境界について検討し,重みから自然完全性と音質要件を捉えた。
標準学習可能性仮定の下でこれらの境界を満たす重みを計算する効率的なアルゴリズムを提案する。
我々の手法は、分布の領域の多重校正分割という新しい概念に依存しており、これはそれ自体が有用であるように見える。
関連論文リスト
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Kernel Density Estimators in Large Dimensions [9.299356601085586]
カーネルによる密度$hatrho_hmathcal D(x)=frac1n hdsum_i=1n Kleft(fracx-y_ihright)$の推定は帯域幅$h$に依存する。
本稿では,Kullback-Leibler分散に基づく帯域幅の最適しきい値が,本論文で同定された新しい統計体系に含まれることを示す。
論文 参考訳（メタデータ） (2024-08-11T15:56:44Z) - A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。
適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文 参考訳（メタデータ） (2024-05-24T11:22:19Z) - 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) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。