論文の概要: Testable Learning with Distribution Shift
- arxiv url: http://arxiv.org/abs/2311.15142v1
- Date: Sat, 25 Nov 2023 23:57:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-28 19:11:10.329766
- Title: Testable Learning with Distribution Shift
- Title（参考訳）: 分散シフトによるテスト可能な学習
- Authors: Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
- Abstract要約: 分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
- 参考スコア（独自算出の注目度）: 10.156432076272477
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the fundamental problem of learning with distribution shift, in
which a learner is given labeled samples from training distribution $D$,
unlabeled samples from test distribution $D'$ and is asked to output a
classifier with low test error. The standard approach in this setting is to
bound the loss of a classifier in terms of some notion of distance between $D$
and $D'$. These distances, however, seem difficult to compute and do not lead
to efficient algorithms.
We depart from this paradigm and define a new model called testable learning
with distribution shift, where we can obtain provably efficient algorithms for
certifying the performance of a classifier on a test distribution. In this
model, a learner outputs a classifier with low test error whenever samples from
$D$ and $D'$ pass an associated test; moreover, the test must accept if the
marginal of $D$ equals the marginal of $D'$. We give several positive results
for learning well-studied concept classes such as halfspaces, intersections of
halfspaces, and decision trees when the marginal of $D$ is Gaussian or uniform
on $\{\pm 1\}^d$. Prior to our work, no efficient algorithms for these basic
cases were known without strong assumptions on $D'$.
For halfspaces in the realizable case (where there exists a halfspace
consistent with both $D$ and $D'$), we combine a moment-matching approach with
ideas from active learning to simulate an efficient oracle for estimating
disagreement regions. To extend to the non-realizable setting, we apply recent
work from testable (agnostic) learning. More generally, we prove that any
function class with low-degree $L_2$-sandwiching polynomial approximators can
be learned in our model. We apply constructions from the pseudorandomness
literature to obtain the required approximators.
- Abstract（参考訳）: 訓練分布から学習者にラベル付きサンプルを付与する分布シフトによる学習の基本的な問題を再検討し、テスト分布からラベルなしサンプルを$d'$とし、低いテストエラーで分類器を出力するように要求する。
この設定における標準的なアプローチは、$d$ と $d'$ の間の距離という概念で分類器の損失を制限することである。
しかし、これらの距離は計算が難しく、効率的なアルゴリズムにはつながりません。
このパラダイムから離れて、分布シフトを伴うテスト可能な学習と呼ばれる新しいモデルを定義し、テスト分布における分類器の性能を証明可能な効率的なアルゴリズムを得ることができる。
このモデルでは、学習者は、$D$と$D’$のサンプルが関連するテストに合格するたびに、低いテストエラーの分類器を出力する。
ハーフ空間、ハーフ空間の交叉、決定木などのよく研究された概念クラスを学習するために、D$の限界がガウス的あるいは一様であるとき、いくつかの肯定的な結果を与える。
我々の研究に先立ち、これらの基本事例に対する効率的なアルゴリズムは、$D'$に関する強い仮定なしでは知られていなかった。
実現可能な場合($D$と$D’$の両方に整合したハーフスペースが存在する場合)のハーフスペースに対しては、モーメントマッチングアプローチとアクティブラーニングのアイデアを組み合わせて、不一致領域を推定するための効率的なオラクルをシミュレートする。
実現不可能な設定に拡張するために、テスト可能な(非依存)学習からの最近の研究を適用します。
より一般に、低次$l_2$-sandwiching多項式近似子を持つ任意の関数クラスがモデルで学習できることを証明する。
疑似ランダム性文学の構成を応用し, 所要の近似値を得る。
関連論文リスト
- Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。
それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
論文 参考訳（メタデータ） (2024-04-02T23:34:39Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Efficient Testable Learning of Halfspaces with Adversarial Label Noise [44.32410859776227]
最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。
テストラナーは、時間$poly(d/eps)$を実行し、ミス分類エラー$O(opt)+eps$でハーフスペースを出力します。
論文 参考訳（メタデータ） (2023-03-09T18:38:46Z) - An Efficient Tester-Learner for Halfspaces [13.13131953359806]
本稿では、Rubinfeld と Vasilyan が最近定義したテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを提案する(2023)。
このモデルでは、学習者は、トレーニングセットがテストに合格するたびに、その出力仮説の精度がほぼ最適であると認定する。
論文 参考訳（メタデータ） (2023-02-28T18:51:55Z) - Generalized Differentiable RANSAC [95.95627475224231]
$nabla$-RANSACは、ランダム化された堅牢な推定パイプライン全体を学ぶことができる、微分可能なRANSACである。
$nabla$-RANSACは、精度という点では最先端のシステムよりも優れているが、精度は低い。
論文 参考訳（メタデータ） (2022-12-26T15:13:13Z) - When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文 参考訳（メタデータ） (2022-10-12T11:04:22Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。