論文の概要: Optimality and complexity of classification by random projection
- arxiv url: http://arxiv.org/abs/2108.06339v3
- Date: Thu, 18 May 2023 15:51:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-19 21:08:31.024387
- Title: Optimality and complexity of classification by random projection
- Title（参考訳）: ランダム投影による分類の最適性と複雑さ
- Authors: Mireille Boutin, Evzenie Coupkova
- Abstract要約: 分類器の一般化誤差は、分類器が選択される関数の集合の複雑さに関連している。
このタイプの分類器は、任意の精度を近似する可能性が高いため、非常に柔軟であることを示す。
特に、クラス条件密度の完全な知識が与えられたとき、これらの低複素度分類器の誤差は k と n が無限大になるときの最適(ベイズ)誤差に収束する。
- 参考スコア（独自算出の注目度）: 1.5229257192293197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The generalization error of a classifier is related to the complexity of the
set of functions among which the classifier is chosen. We study a family of
low-complexity classifiers consisting of thresholding a random one-dimensional
feature. The feature is obtained by projecting the data on a random line after
embedding it into a higher-dimensional space parametrized by monomials of order
up to k. More specifically, the extended data is projected n-times and the best
classifier among those n, based on its performance on training data, is chosen.
We show that this type of classifier is extremely flexible, as it is likely to
approximate, to an arbitrary precision, any continuous function on a compact
set as well as any boolean function on a compact set that splits the support
into measurable subsets. In particular, given full knowledge of the class
conditional densities, the error of these low-complexity classifiers would
converge to the optimal (Bayes) error as k and n go to infinity. On the other
hand, if only a training dataset is given, we show that the classifiers will
perfectly classify all the training points as k and n go to infinity. We also
bound the generalization error of our random classifiers. In general, our
bounds are better than those for any classifier with VC dimension greater than
O (ln n) . In particular, our bounds imply that, unless the number of
projections n is extremely large, there is a significant advantageous gap
between the generalization error of the random projection approach and that of
a linear classifier in the extended space. Asymptotically, as the number of
samples approaches infinity, the gap persists for any such n. Thus, there is a
potentially large gain in generalization properties by selecting parameters at
random, rather than optimization.
- Abstract（参考訳）: 分類器の一般化誤差は、分類器が選択される関数の集合の複雑さに関連している。
ランダムな一次元特徴を閾値付けした低複雑性分類器群について検討する。
この特徴は、データを無作為直線上に投影し、それをk までの順序の単項によってパラメトリ化された高次元空間に埋め込むことにより得られる。
より具体的には、拡張データをn時間に投影し、トレーニングデータのパフォーマンスに基づいて、これらのnの中で最良の分類器を選択する。
このタイプの分類器は、任意の精度で、コンパクト集合上の任意の連続函数と、そのサポートを可測部分集合に分割するコンパクト集合上のブール関数とに非常に柔軟であることが示される。
特に、クラス条件密度の完全な知識が与えられたとき、これらの低複素度分類器の誤差は k と n が無限大になるときの最適(ベイズ)誤差に収束する。
一方、トレーニングデータセットのみを与えると、分類器がすべてのトレーニングポイントを完全に分類し、k と n が無限大になることを示す。
また、ランダム分類器の一般化誤差も有界である。
一般に、我々の境界は、vc次元がo(ln n)よりも大きいどの分類器よりも優れている。
特に、我々の境界は、射影 n の数が非常に大きい場合を除き、ランダム射影アプローチの一般化誤差と拡張空間における線形分類器の間には大きな利点があることを意味する。
漸近的に、サンプル数が無限に近づくにつれて、ギャップはそのような n に対して持続する。
したがって、最適化ではなくランダムにパラメータを選択することで一般化特性に大きな利益をもたらす可能性がある。
関連論文リスト
- How many classifiers do we need? [50.69951049206484]
分類器間の不一致と偏極が、個々の分類器を集約することで得られる性能向上とどのように関連しているかを詳細に分析する。
分類器の個数で不一致の挙動を示す。
我々の理論と主張は、様々なタイプのニューラルネットワークを用いた画像分類タスクに関する経験的な結果によって裏付けられている。
論文 参考訳（メタデータ） (2024-11-01T02:59:56Z) - Classification Using Global and Local Mahalanobis Distances [1.7811840395202345]
競合クラスからの観測のマハラノビス距離に基づく新しい半パラメトリック分類器を提案する。
我々のツールは、これらの距離を異なるクラスの後部確率を推定する特徴として利用するロジスティックリンク関数を持つ一般化加法モデルである。
論文 参考訳（メタデータ） (2024-02-13T08:22:42Z) - Precise Asymptotic Generalization for Multiclass Classification with
Overparameterized Linear Models [4.093769373833101]
Subramanian et al.'22 の予想では、データポイント、特徴、クラスの数はすべて一緒になる。
我々の新しい下限は情報理論の強い逆に似ており、それらは誤分類率が0か1に近づくことを証明している。
厳密な解析の鍵はハンソン・ライトの不等式の新しい変種であり、スパースラベルの多重クラス問題に広く有用である。
論文 参考訳（メタデータ） (2023-06-23T00:59:15Z) - GMMSeg: Gaussian Mixture based Generative Semantic Segmentation Models [74.0430727476634]
結合分布 p(ピクセル特徴,クラス) の高密度な生成型分類器に依存する分割モデルの新たなファミリーを提案する。
さまざまなセグメンテーションアーキテクチャとバックボーンにより、GMMSegはクローズドセットデータセットにおいて差別的よりも優れています。
GMMSegは、オープンワールドデータセットでもうまく機能する。
論文 参考訳（メタデータ） (2022-10-05T05:20:49Z) - Soft-margin classification of object manifolds [0.0]
単一対象の複数の出現に対応する神経集団は、神経応答空間における多様体を定義する。
そのような多様体を分類する能力は、オブジェクト認識やその他の計算タスクは多様体内の変数に無関心な応答を必要とするため、興味がある。
ソフトマージン分類器は、より大きなアルゴリズムのクラスであり、トレーニングセット外のパフォーマンスを最適化するためにアプリケーションで使われる追加の正規化パラメータを提供する。
論文 参考訳（メタデータ） (2022-03-14T12:23:36Z) - Local versions of sum-of-norms clustering [77.34726150561087]
本手法はボールモデルにおいて任意に閉じた球を分離できることを示す。
我々は、不連結連結集合のクラスタリングで発生する誤差に定量的な有界性を証明した。
論文 参考訳（メタデータ） (2021-09-20T14:45:29Z) - On Supervised Classification of Feature Vectors with Independent and
Non-Identically Distributed Elements [10.52087851034255]
特徴ベクトルを互いに独立だが非独立に分散した要素で分類する問題について検討する。
ラベル毎に1つのトレーニング特徴ベクトルしか持たない場合でも,特徴ベクトルの長さが大きくなるにつれて誤差確率がゼロになることを示す。
論文 参考訳（メタデータ） (2020-08-01T06:49:50Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
論文 参考訳（メタデータ） (2020-07-13T17:39:35Z) - High-Dimensional Quadratic Discriminant Analysis under Spiked Covariance
Model [101.74172837046382]
そこで本研究では,魚の識別比を最大化する2次分類手法を提案する。
数値シミュレーションにより,提案した分類器は,合成データと実データの両方において古典的R-QDAよりも優れるだけでなく,計算量の削減も要求されることがわかった。
論文 参考訳（メタデータ） (2020-06-25T12:00:26Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
[1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。
我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。
また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
論文 参考訳（メタデータ） (2020-04-17T12:47:04Z) - Intrinsic Dimension Estimation via Nearest Constrained Subspace
Classifier [7.028302194243312]
教師付き分類や固有次元推定のために,新しい部分空間に基づく分類器を提案する。
各クラスのデータの分布は、特徴空間の有限個のファイン部分空間の和によってモデル化される。
The proposed method is a generalization of classical NN (Nearest Neighbor), NFL (Nearest Feature Line) and has a close relationship with NS (Nearest Subspace)。
推定次元パラメータが正確に推定された分類器は、一般に分類精度の点で競合より優れている。
論文 参考訳（メタデータ） (2020-02-08T20:54:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。