論文の概要: Streaming Kernel PCA Algorithm With Small Space
- arxiv url: http://arxiv.org/abs/2303.04555v1
- Date: Wed, 8 Mar 2023 13:13:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 14:03:47.053801
- Title: Streaming Kernel PCA Algorithm With Small Space
- Title（参考訳）: 空間を小さくしたストリーミングカーネルPCAアルゴリズム
- Authors: Yichuan Deng, Zhao Song, Zifan Wang, Han Zhang
- Abstract要約: 近年,大規模なデータセットを効率的に処理できるため,ストリーミングPCAが注目されている。
我々はOjaの従来のスキームに基づくKernel問題に対するストリーミングアルゴリズムを提案する。
提案アルゴリズムは,PCAのメモリ使用量を削減するとともに,その精度を維持するという課題に対処する。
- 参考スコア（独自算出の注目度）: 24.003544967343615
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Principal Component Analysis (PCA) is a widely used technique in machine
learning, data analysis and signal processing. With the increase in the size
and complexity of datasets, it has become important to develop low-space usage
algorithms for PCA. Streaming PCA has gained significant attention in recent
years, as it can handle large datasets efficiently. The kernel method, which is
commonly used in learning algorithms such as Support Vector Machines (SVMs),
has also been applied in PCA algorithms.
We propose a streaming algorithm for Kernel PCA problems based on the
traditional scheme by Oja. Our algorithm addresses the challenge of reducing
the memory usage of PCA while maintaining its accuracy. We analyze the
performance of our algorithm by studying the conditions under which it
succeeds. Specifically, we show that, when the spectral ratio $R :=
\lambda_1/\lambda_2$ of the target covariance matrix is lower bounded by $C
\cdot \log n\cdot \log d$, the streaming PCA can be solved with $O(d)$ space
cost.
Our proposed algorithm has several advantages over existing methods. First,
it is a streaming algorithm that can handle large datasets efficiently. Second,
it employs the kernel method, which allows it to capture complex nonlinear
relationships among data points. Third, it has a low-space usage, making it
suitable for applications where memory is limited.
- Abstract（参考訳）: 主成分分析(PCA)は、機械学習、データ分析、信号処理において広く使われている技術である。
データセットのサイズと複雑さの増大に伴い、PCAの低空間利用アルゴリズムを開発することが重要になっている。
近年,大規模データセットを効率的に処理できるストリーミングpcaが注目されている。
サポートベクターマシン(svm)などの学習アルゴリズムで一般的に用いられるカーネル法は、pcaアルゴリズムにも適用されている。
本稿では,Oja の従来のスキームに基づく Kernel PCA 問題に対するストリーミングアルゴリズムを提案する。
本アルゴリズムは,PCAのメモリ使用量を削減し,精度を向上する。
我々は,アルゴリズムが成功する条件を調べることにより,その性能を解析する。
具体的には、ターゲット共分散行列のスペクトル比$R := \lambda_1/\lambda_2$を$C \cdot \log n\cdot \log d$で下限にすると、ストリーミングPCAは$O(d)$スペースコストで解決できることを示す。
提案アルゴリズムは既存手法に対していくつかの利点がある。
まず、大規模なデータセットを効率的に処理できるストリーミングアルゴリズムである。
第二に、カーネル法を用いて、データポイント間の複雑な非線形関係をキャプチャする。
第3に、メモリ使用量が少ないため、メモリ制限のあるアプリケーションに適している。
関連論文リスト
- Efficient Sparse PCA via Block-Diagonalization [13.38174941551702]
スパースPCAを効率的に近似する新しいフレームワークを提案する。
既製のスパースPCAアルゴリズムを利用することができ、計算速度を大幅に向上させることができる。
このアルゴリズムを統合すると、ランタイムを$mathcalOleft(fracddstar cdot g(k, dstar) + d2right)$に削減します。
論文 参考訳（メタデータ） (2024-10-18T00:16:10Z) - Learning-Augmented K-Means Clustering Using Dimensional Reduction [1.7243216387069678]
主成分分析(PCA)を用いたデータセットの次元性低減手法を提案する。
PCAは文献でよく確立されており、データモデリング、圧縮、可視化の最も有用なツールの1つになっている。
論文 参考訳（メタデータ） (2024-01-06T12:02:33Z) - Improved Privacy-Preserving PCA Using Optimized Homomorphic Matrix
Multiplication [0.0]
主成分分析(英: principal Component Analysis、PCA)は、機械学習とデータ分析の領域で広く利用されている重要な技術である。
近年,セキュアなクラウドコンピューティングシナリオにおいて,プライバシ保護型PCAアルゴリズムの同型暗号化を活用する取り組みが進められている。
本稿では,これらの制約に対処するプライバシー保護PCAに対して,従来の手法に比べて効率,精度,拡張性に優れる新たなアプローチを提案する。
論文 参考訳（メタデータ） (2023-05-27T02:51:20Z) - Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA [43.106438224356175]
ほぼ最適誤差保証付き頑健なPCAのためのニア線形時間アルゴリズムを開発した。
また,メモリ使用量にほぼ線形なロバストPCAのためのシングルパスストリーミングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-04T04:45:16Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳（メタデータ） (2022-10-21T15:56:13Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Large-scale Optimization of Partial AUC in a Range of False Positive
Rates [51.12047280149546]
ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。
近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。
提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
論文 参考訳（メタデータ） (2022-03-03T03:46:18Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。