論文の概要: Classification Under Misspecification: Halfspaces, Generalized Linear
Models, and Connections to Evolvability
- arxiv url: http://arxiv.org/abs/2006.04787v1
- Date: Mon, 8 Jun 2020 17:59:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 01:43:08.303502
- Title: Classification Under Misspecification: Halfspaces, Generalized Linear
Models, and Connections to Evolvability
- Title（参考訳）: 誤特定下の分類:半空間、一般化線形モデル、進化可能性への接続
- Authors: Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
- Abstract要約: 特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。
我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。
また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
- 参考スコア（独自算出の注目度）: 29.85468294601847
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we revisit some classic problems on classification under
misspecification. In particular, we study the problem of learning halfspaces
under Massart noise with rate $\eta$. In a recent work, Diakonikolas,
Goulekakis, and Tzamos resolved a long-standing problem by giving the first
efficient algorithm for learning to accuracy $\eta + \epsilon$ for any
$\epsilon > 0$. However, their algorithm outputs a complicated hypothesis,
which partitions space into $\text{poly}(d,1/\epsilon)$ regions. Here we give a
much simpler algorithm and in the process resolve a number of outstanding open
questions:
(1) We give the first proper learner for Massart halfspaces that achieves
$\eta + \epsilon$. We also give improved bounds on the sample complexity
achievable by polynomial time algorithms.
(2) Based on (1), we develop a blackbox knowledge distillation procedure to
convert an arbitrarily complex classifier to an equally good proper classifier.
(3) By leveraging a simple but overlooked connection to evolvability, we show
any SQ algorithm requires super-polynomially many queries to achieve
$\mathsf{OPT} + \epsilon$.
Moreover we study generalized linear models where $\mathbb{E}[Y|\mathbf{X}] =
\sigma(\langle \mathbf{w}^*, \mathbf{X}\rangle)$ for any odd, monotone, and
Lipschitz function $\sigma$. This family includes the previously mentioned
halfspace models as a special case, but is much richer and includes other
fundamental models like logistic regression. We introduce a challenging new
corruption model that generalizes Massart noise, and give a general algorithm
for learning in this setting. Our algorithms are based on a small set of core
recipes for learning to classify in the presence of misspecification.
Finally we study our algorithm for learning halfspaces under Massart noise
empirically and find that it exhibits some appealing fairness properties.
- Abstract（参考訳）: 本稿では,誤特定に基づく分類における古典的な問題を再考する。
特に、Massartノイズ下でのハーフスペースの学習問題を$\eta$で検討する。
最近の研究で、Diakonikolas、Goulekakis、Tzamosは、$\eta + \epsilon$ for any $\epsilon > 0$を学習するための最初の効率的なアルゴリズムを提供することで、長年の問題を解決した。
しかし、それらのアルゴリズムは複雑な仮説を出力し、空間を$\text{poly}(d,1/\epsilon)$ regionに分割する。
ここで、より単純なアルゴリズムを与え、その過程において、いくつかの未解決の問題を解決する: (1) マッサート半空間に対する最初の適切な学習者を与え、$\eta + \epsilon$ を得る。
また、多項式時間アルゴリズムによって実現可能なサンプル複雑性の限界も改善した。
2)(1)に基づいて,任意に複雑な分類器を等しく適切な分類器に変換するブラックボックス知識蒸留法を開発した。
(3) 単純だが見過ごされた接続を進化可能性に活用することにより、任意のSQアルゴリズムは、$\mathsf{OPT} + \epsilon$を達成するために超ポリノミカルな多くのクエリを必要とすることを示す。
さらに、任意の奇数、単調、リプシッツ関数 $\sigma$ に対して $\mathbb{E}[Y|\mathbf{X}] = \sigma(\langle \mathbf{w}^*, \mathbf{X}\rangle)$ を一般化線型モデルとして研究する。
このファミリーは、前述のハーフスペースモデルを特別なケースとして含むが、よりリッチで、ロジスティック回帰のような他の基本モデルを含んでいる。
我々は,マスアートノイズを一般化する新しい汚職モデルを提案し,この環境で学習する一般的なアルゴリズムを提案する。
我々のアルゴリズムは、誤特定の有無を分類する学習のための、小さなレシピセットに基づいている。
最後に,マスアート雑音下でのハーフスペース学習のためのアルゴリズムを実証的に検討し,公平性を示すことを示す。
関連論文リスト
- Efficient Algorithms for Learning Monophonic Halfspaces in Graphs [7.619404259039284]
我々は、教師付き、オンライン、アクティブな設定において、モノフォニックなハーフスペースを学習するためのいくつかの新しい結果を証明した。
我々の主な結果は、モノフォニック半空間は、n = |V(G)|$ の時間において、ほぼ最適に複雑に学習できるということである。
また、概念クラスは遅延$operatornamepoly(n)$で列挙でき、経験的リスクは2ω(G)operatornamepoly(n)$で実行可能であることも示します。
論文 参考訳（メタデータ） (2024-05-01T20:34:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。