論文の概要: Fast Partition-Based Cross-Validation With Centering and Scaling for $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$
- arxiv url: http://arxiv.org/abs/2401.13185v2
- Date: Mon, 5 Aug 2024 10:01:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-06 23:46:09.168624
- Title: Fast Partition-Based Cross-Validation With Centering and Scaling for $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$
- Title(参考訳): $\mathbf{X}^\mathbf{T}\mathbf{X}$および$\mathbf{X}^\mathbf{T}\mathbf{Y}$に対する中心とスケーリングによる高速分割型クロスバリデーション
- Authors: Ole-Christian Galbo Engstrøm, Martin Holm Jensen,
- Abstract要約: 機械学習モデルの分割に基づくクロスバリデーションを大幅に高速化するアルゴリズムを提案する。
我々のアルゴリズムは、例えば、主成分分析(PCA)、主成分回帰(PCR)、隆起回帰(RR)、通常最小二乗(OLS)、部分最小二乗(PLS)のモデル選択に応用できる。
文献に見られる代替手段とは異なり、前処理によるデータの漏洩を避ける。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present algorithms that substantially accelerate partition-based cross-validation for machine learning models that require matrix products $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$. Our algorithms have applications in model selection for, e.g., principal component analysis (PCA), principal component regression (PCR), ridge regression (RR), ordinary least squares (OLS), and partial least squares (PLS). Our algorithms support all combinations of column-wise centering and scaling of $\mathbf{X}$ and $\mathbf{Y}$, and we demonstrate in our accompanying implementation that this adds only a manageable, practical constant over efficient variants without preprocessing. We prove the correctness of our algorithms under a fold-based partitioning scheme and show that the running time is independent of the number of folds; that is, they have the same time complexity as that of computing $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$ and space complexity equivalent to storing $\mathbf{X}$, $\mathbf{Y}$, $\mathbf{X}^\mathbf{T}\mathbf{X}$, and $\mathbf{X}^\mathbf{T}\mathbf{Y}$. Importantly, unlike alternatives found in the literature, we avoid data leakage due to preprocessing. We achieve these results by eliminating redundant computations in the overlap between training partitions. Concretely, we show how to manipulate $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$ using only samples from the validation partition to obtain the preprocessed training partition-wise $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$. To our knowledge, we are the first to derive correct and efficient cross-validation algorithms for any of the $16$ combinations of column-wise centering and scaling, for which we also prove only $12$ give distinct matrix products.
- Abstract(参考訳): 行列積 $\mathbf{X}^\mathbf{T}\mathbf{X}$ および $\mathbf{X}^\mathbf{T}\mathbf{Y}$ を必要とする機械学習モデルの分割ベースのクロスバリデーションを大幅に加速するアルゴリズムを提案する。
我々のアルゴリズムは、モデル選択、例えば、主成分分析(PCA)、主成分回帰(PCR)、隆起回帰(RR)、通常最小二乗(OLS)、部分最小二乗(PLS)に応用できる。
我々のアルゴリズムは、$\mathbf{X}$と$\mathbf{Y}$のカラム単位の集中とスケーリングのすべての組み合わせをサポートします。
すなわち、計算の複雑さは $\mathbf{X}^\mathbf{T}\mathbf{X}$ と $\mathbf{X}^\mathbf{T}\mathbf{Y}$, $\mathbf{X}$, $\mathbf{X}$, $\mathbf{X}^\mathbf{T}\mathbf{X}$, $\mathbf{X}$, $\mathbf{X}^\mathbf{T}\mathbf{X}$ と $\mathbf{X}^\mathbf{T}\mathbf{Y}$ と同じである。
重要なことは、文献に見られる代替案とは異なり、前処理によるデータの漏洩を避けることである。
トレーニングパーティション間の重なり合いにおいて、冗長な計算を排除し、これらの結果を得る。
具体的には、バリデーションパーティションのサンプルのみを使用して、$\mathbf{X}^\mathbf{T}\mathbf{X}$と$\mathbf{X}^\mathbf{T}\mathbf{Y}$を操作して、プリプロセスされたトレーニングパーティションの$\mathbf{X}^\mathbf{T}\mathbf{X}$と$\mathbf{X}^\mathbf{T}\mathbf{Y}$を得る方法を示す。
私たちの知る限り、カラムワイド・センターとスケーリングの組み合わせのいずれにおいても、正確で効率的なクロスバリデーションアルゴリズムを導出したのは初めてです。
関連論文リスト
- Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models [10.603378323312809]
我々は、制約された最も予測可能な説明(CMPE)問題に対して、ほぼ最適解を出力することを学ぶディープニューラルネットワークを訓練する。
提案手法の特性を解析し,その有効性をいくつかのベンチマーク問題で実験的に実証する。
論文 参考訳(メタデータ) (2024-04-17T17:55:17Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Nonparametric Learning of Two-Layer ReLU Residual Units [22.870658194212744]
本稿では,線形整列ユニット(ReLU)を活性化した2層残基を学習するアルゴリズムについて述べる。
解析最小化器はそのパラメータと非線形性の観点から、正確な地上構造ネットワークを表現できる機能として層ワイドな目的を設計する。
我々は,アルゴリズムの統計的強い一貫性を証明し,実験によるアルゴリズムの堅牢性とサンプル効率を実証する。
論文 参考訳(メタデータ) (2020-08-17T22:11:26Z) - Fast and Near-Optimal Diagonal Preconditioning [46.240079312553796]
左か右の対角線再スケーリングにより$mathbfA$の条件数を改善する方法を示す。
構造化混合パッキングと半定値プログラムを対象とし,$widetildeO(textnnz(mathbfA) cdot textpoly(kappastar))$ timeに対して,$mathbfA$の定数係数最適スケーリングを計算する。
論文 参考訳(メタデータ) (2020-08-04T17:53:28Z) - Fast Matrix Square Roots with Applications to Gaussian Processes and
Bayesian Optimization [24.085358075449406]
行列平方根とその逆は機械学習で頻繁に現れる。
我々は,$mathbf K1/2 mathbf b$,$mathbf K-1/2 mathbf b$とその導関数を行列ベクトル乗算(MVM)により計算するための高効率二次時間アルゴリズムを導入する。
提案手法は,Krylov部分空間法と有理近似,典型的には4ドル10分の精度で100ドル未満のMVMを推定する。
論文 参考訳(メタデータ) (2020-06-19T17:56:24Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳(メタデータ) (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。