論文の概要: 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}$を得る方法を示す。 私たちの知る限り、カラムワイド・センターとスケーリングの組み合わせのいずれにおいても、正確で効率的なクロスバリデーションアルゴリズムを導出したのは初めてです。

関連論文リスト

• Matrix Product Sketching via Coordinated Sampling [15.820518033589705]
  我々は、小さな空間スケッチに基づいて行列積 $mathbfATmathbfB$ を近似するというよく研究された問題を再考する。 我々は, $mathbfA$ と $mathbfB$ がスパースであることを証明する。
  論文  参考訳（メタデータ） (2025-01-29T18:35:38Z)
• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound if $epsilon$ is constant。 また、$mu_mathbfy(mathbfX)$は計算が難しいという事前予想も否定する。
  論文  参考訳（メタデータ） (2024-12-03T18:11:37Z)
• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。 ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-11T03:43:52Z)
• Compressing Large Language Models using Low Rank and Low Precision Decomposition [46.30918750022739]
  この研究は、新しい訓練後のLLM圧縮アルゴリズムである$rm CALDERA$を導入している。 重量行列 $mathbfW$ の固有の低ランク構造を利用して、低ランクで低精度な分解によってそれを近似する。 その結果、LlaMa-$2$$7$B/$13B$/$70$BとLlaMa-$3$B $rm CALDERA$は、既存のトレーニング後の圧縮技術より優れていることが示された。
  論文  参考訳（メタデータ） (2024-05-29T08:42:30Z)
• Locality Regularized Reconstruction: Structured Sparsity and Delaunay Triangulations [7.148312060227714]
  線形表現学習は、その概念的単純さと、圧縮、分類、特徴抽出といったタスクにおける経験的有用性から、広く研究されている。 本研究では、正則化最小二乗回帰問題を解くことにより、$mathbfy$の局所再構成を形成する$mathbfw$を求める。 すべてのレベルの正則化と、$mathbfX$ の列が独自のデラウネー三角形を持つという穏やかな条件の下では、最適係数の非零成分の数は$d+1$ で上界となることを証明している。
  論文  参考訳（メタデータ） (2024-05-01T19:56:52Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• 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)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。