論文の概要: Self-Directed Linear Classification
- arxiv url: http://arxiv.org/abs/2308.03142v1
- Date: Sun, 6 Aug 2023 15:38:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-08 16:19:16.770769
- Title: Self-Directed Linear Classification
- Title（参考訳）: 自己指向線形分類
- Authors: Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
- Abstract要約: オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。
そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
- 参考スコア（独自算出の注目度）: 50.659479930171585
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In online classification, a learner is presented with a sequence of examples
and aims to predict their labels in an online fashion so as to minimize the
total number of mistakes. In the self-directed variant, the learner knows in
advance the pool of examples and can adaptively choose the order in which
predictions are made. Here we study the power of choosing the prediction order
and establish the first strong separation between worst-order and random-order
learning for the fundamental task of linear classification. Prior to our work,
such a separation was known only for very restricted concept classes, e.g.,
one-dimensional thresholds or axis-aligned rectangles.
We present two main results. If $X$ is a dataset of $n$ points drawn
uniformly at random from the $d$-dimensional unit sphere, we design an
efficient self-directed learner that makes $O(d \log \log(n))$ mistakes and
classifies the entire dataset. If $X$ is an arbitrary $d$-dimensional dataset
of size $n$, we design an efficient self-directed learner that predicts the
labels of $99\%$ of the points in $X$ with mistake bound independent of $n$. In
contrast, under a worst- or random-ordering, the number of mistakes must be at
least $\Omega(d \log n)$, even when the points are drawn uniformly from the
unit sphere and the learner only needs to predict the labels for $1\%$ of them.
- Abstract（参考訳）: オンライン分類では、学習者は一連の例を示し、そのラベルをオンラインの方法で予測し、間違いの総数を最小限に抑えることを目的としている。
自己指向型では、学習者は予めサンプルのプールを知り、予測される順序を適応的に選択することができる。
本稿では,予測順序の選択能力について検討し,線形分類の基本課題に対する最低次学習とランダム次学習の第一の強い分離を確立させる。
我々の研究以前は、そのような分離は、例えば1次元のしきい値や軸方向の矩形のような非常に制限された概念クラスに対してのみ知られていた。
主な結果は2つある。
もし$x$が$d$-dimensional unit sphereからランダムに引き出された$n$のデータセットであれば、$o(d \log \log(n))$の間違いを生じさせ、データセット全体を分類する効率的な自己指向学習器を設計します。
もし$x$が任意の$d$-dimensionalデータセットサイズ$n$であれば、$x$のラベルを$99\%で予測し、$n$とは無関係にバインドする効率的な自己指向学習器を設計します。
対照的に、最悪の順序付けやランダム順序付けでは、点が単位球面から一様に引かれ、学習者がラベルを1〜%の値で予測するだけでよい場合でも、誤りの数は少なくとも$\omega(d \log n)$でなければならない。
関連論文リスト
- Transfer Learning for Latent Variable Network Models [18.31057192626801]
潜在変数ネットワークモデルにおける推定のための伝達学習について検討する。
潜伏変数が共有されている場合、エラーの消滅が可能であることを示す。
我々のアルゴリズムは、$o(1)$エラーを達成し、ソースやターゲットネットワーク上でパラメトリック形式を仮定しない。
論文 参考訳（メタデータ） (2024-06-05T16:33:30Z) - Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。
計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。
我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-05-21T17:31:10Z) - High-dimensional Asymptotics of Feature Learning: How One Gradient Step
Improves the Representation [89.21686761957383]
2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。
我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
論文 参考訳（メタデータ） (2022-05-03T12:09:59Z) - Online Selective Classification with Limited Feedback [82.68009460301585]
オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。
私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。
smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
論文 参考訳（メタデータ） (2021-10-27T08:00:53Z) - Littlestone Classes are Privately Online Learnable [28.04975353867202]
プライバシー制約下でのオンライン分類の問題点を考察する。
この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。
学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
論文 参考訳（メタデータ） (2021-06-25T09:08:33Z) - Locality defeats the curse of dimensionality in convolutional
teacher-student scenarios [69.2027612631023]
学習曲線指数$beta$を決定する上で,局所性が重要であることを示す。
我々は、自然の仮定を用いて、トレーニングセットのサイズに応じて減少するリッジでカーネルレグレッションを実行すると、リッジレスの場合と同じような学習曲線指数が得られることを証明して結論付けた。
論文 参考訳（メタデータ） (2021-06-16T08:27:31Z) - Remember What You Want to Forget: Algorithms for Machine Unlearning [37.656345901739506]
学習モデルからデータポイントを忘れる問題について検討する。
最大$O(n/d1/4)のサンプルを削除できるアンラーニングアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-03-04T19:28:57Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - The generalization error of max-margin linear classifiers: Benign
overfitting and high dimensional asymptotics in the overparametrized regime [11.252856459394854]
現代の機械学習分類器は、トレーニングセットに消滅する分類誤差を示すことが多い。
これらの現象に触発され、線形分離可能なデータに対する高次元の最大マージン分類を再検討する。
論文 参考訳（メタデータ） (2019-11-05T00:15:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。