論文の概要: Distribution-Specific Agnostic Conditional Classification With Halfspaces
- arxiv url: http://arxiv.org/abs/2502.00172v1
- Date: Fri, 31 Jan 2025 21:29:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-05 15:02:07.978116
- Title: Distribution-Specific Agnostic Conditional Classification With Halfspaces
- Title(参考訳): ハーフスペースを用いた分布特異なアグノスティック条件分類
- Authors: Jizhou Huang, Brendan Juba,
- Abstract要約: 本研究では,無関係な環境下での「選択」や「条件」の分類問題について検討する。
エラー保証付き同種半空間セレクタのための最初のPAC学習アルゴリズムを提案する。
近似条件分類は加法型と乗法型の両方の近似分類と同程度に難しいことが証明された。
- 参考スコア(独自算出の注目度): 27.197384293699134
- License:
- Abstract: We study ``selective'' or ``conditional'' classification problems under an agnostic setting. Classification tasks commonly focus on modeling the relationship between features and categories that captures the vast majority of data. In contrast to common machine learning frameworks, conditional classification intends to model such relationships only on a subset of the data defined by some selection rule. Most work on conditional classification either solves the problem in a realizable setting or does not guarantee the error is bounded compared to an optimal solution. In this work, we consider selective/conditional classification by sparse linear classifiers for subsets defined by halfspaces, and give both positive as well as negative results for Gaussian feature distributions. On the positive side, we present the first PAC-learning algorithm for homogeneous halfspace selectors with error guarantee $\bigO*{\sqrt{\mathrm{opt}}}$, where $\mathrm{opt}$ is the smallest conditional classification error over the given class of classifiers and homogeneous halfspaces. On the negative side, we find that, under cryptographic assumptions, approximating the conditional classification loss within a small additive error is computationally hard even under Gaussian distribution. We prove that approximating conditional classification is at least as hard as approximating agnostic classification in both additive and multiplicative form.
- Abstract(参考訳): 我々は,「選択的」あるいは「条件的」な分類問題を不可知的条件下で研究する。
分類タスクは一般的に、大部分のデータをキャプチャする特徴とカテゴリの関係をモデル化することに焦点を当てる。
一般的な機械学習フレームワークとは対照的に、条件付き分類は、ある種の選択規則で定義されたデータのサブセットのみに基づいて、そのような関係をモデル化することを目的としている。
条件付き分類に関するほとんどの研究は、実現可能な設定で問題を解くか、最適解と比較して誤差が有界であることを保証しない。
本研究では、半空間で定義される部分集合に対するスパース線形分類器による選択的・条件的分類を考察し、ガウス的特徴分布に対して正と負の両方の結果を与える。
正の面から、同種半空間セレクタに対する最初のPAC学習アルゴリズムを誤差保証$\bigO*{\sqrt{\mathrm{opt}}}$, where $\mathrm{opt}$は、与えられた分類器と同種半空間のクラスに対して最小の条件付き分類誤差である。
負の面では、暗号的な仮定の下では、小さな加法誤差で条件付き分類損失を近似することは、ガウス分布の下でも計算的に困難である。
近似条件分類は, 加法形式と乗法形式の両方において, 近似条件分類と同程度に難しいことが証明された。
関連論文リスト
- Classification Error Bound for Low Bayes Error Conditions in Machine Learning [50.25063912757367]
機械学習における誤りミスマッチとKulback-Leibler分散の関係について検討する。
多くの機械学習タスクにおける低モデルに基づく分類誤差の最近の観測により、低ベイズ誤差条件に対する分類誤差の線形近似を提案する。
論文 参考訳(メタデータ) (2025-01-27T11:57:21Z) - Precise Asymptotic Generalization for Multiclass Classification with
Overparameterized Linear Models [4.093769373833101]
Subramanian et al.'22 の予想では、データポイント、特徴、クラスの数はすべて一緒になる。
我々の新しい下限は情報理論の強い逆に似ており、それらは誤分類率が0か1に近づくことを証明している。
厳密な解析の鍵はハンソン・ライトの不等式の新しい変種であり、スパースラベルの多重クラス問題に広く有用である。
論文 参考訳(メタデータ) (2023-06-23T00:59:15Z) - Class-Conditional Conformal Prediction with Many Classes [60.8189977620604]
類似した共形スコアを持つクラスをクラスタ化するクラスタ化共形予測法を提案する。
クラスタ化されたコンフォメーションは、クラス条件カバレッジとセットサイズメトリクスの点で、既存のメソッドよりも一般的に優れています。
論文 参考訳(メタデータ) (2023-06-15T17:59:02Z) - An Upper Bound for the Distribution Overlap Index and Its Applications [22.92968284023414]
本稿では,2つの確率分布間の重なり関数に対する計算容易な上限を提案する。
提案した境界は、一級分類と領域シフト解析においてその値を示す。
私たちの研究は、重複ベースのメトリクスの応用を拡大する大きな可能性を示しています。
論文 参考訳(メタデータ) (2022-12-16T20:02:03Z) - Parametric Classification for Generalized Category Discovery: A Baseline
Study [70.73212959385387]
Generalized Category Discovery (GCD)は、ラベル付きサンプルから学習した知識を用いて、ラベルなしデータセットで新しいカテゴリを発見することを目的としている。
パラメトリック分類器の故障を調査し,高品質な監視が可能であった場合の過去の設計選択の有効性を検証し,信頼性の低い疑似ラベルを重要課題として同定する。
エントロピー正規化の利点を生かし、複数のGCDベンチマークにおける最先端性能を実現し、未知のクラス数に対して強いロバスト性を示す、単純で効果的なパラメトリック分類法を提案する。
論文 参考訳(メタデータ) (2022-11-21T18:47:11Z) - The Interplay between Distribution Parameters and the
Accuracy-Robustness Tradeoff in Classification [0.0]
アドリラルトレーニングは、通常のモデルに比べて自然(未成熟)の例では正確でないモデルをもたらす傾向にある。
これは、アルゴリズムの欠点か、トレーニングデータ分散の基本的な性質によるものとみなすことができる。
本研究では,二進ガウス混合分類問題の下で後者のケースに焦点をあてる。
論文 参考訳(メタデータ) (2021-07-01T06:57:50Z) - Predict then Interpolate: A Simple Algorithm to Learn Stable Classifiers [59.06169363181417]
Predict then Interpolate (PI) は環境全体にわたって安定な相関関係を学習するためのアルゴリズムである。
正しい予測と間違った予測の分布を補間することにより、不安定な相関が消えるオラクル分布を明らかにすることができる。
論文 参考訳(メタデータ) (2021-05-26T15:37:48Z) - Cautious Active Clustering [79.23797234241471]
ユークリッド空間上の未知の確率測度からサンプリングされた点の分類の問題を考える。
我々のアプローチは、未知の確率測度を、各クラスに対する条件付き確率の凸結合として考えることである。
論文 参考訳(メタデータ) (2020-08-03T23:47:31Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。
テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。
以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
論文 参考訳(メタデータ) (2020-06-22T21:12:31Z) - Classifier-independent Lower-Bounds for Adversarial Robustness [13.247278149124757]
理論的には、テストタイムの逆数と雑音の分類例に対するロバスト性の限界を解析する。
最適輸送理論を用いて、与えられた分類問題に対して分類器ができるベイズ最適誤差の変分式を導出する。
一般的な距離ベース攻撃の場合,ベイズ最適誤差に対して明らかな下限を導出する。
論文 参考訳(メタデータ) (2020-06-17T16:46:39Z) - Bayesian Semi-supervised Multi-category Classification under Nonparanormality [2.307581190124002]
セミ教師付き学習はラベル付きデータとラベルなしデータの両方を使用するモデルトレーニング手法である。
本稿では,任意のカテゴリ分類問題に適用可能なベイズ半教師付き学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-01-11T21:31:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。