首页 > 其他分享 >【数学】主成分分析(PCA)的详细深度推导过程

【数学】主成分分析(PCA)的详细深度推导过程

时间:2024-04-23 14:22:33浏览次数:27  
标签:范数 Tx 推导 深度 矩阵 arg PCA 向量 lambda

Based on Deep Learning (2017, MIT) book.

本文基于Deep Learning (2017, MIT),推导过程补全了所涉及的知识及书中推导过程中跳跃和省略的部分。
blog

1 概述

现代数据集,如网络索引、高分辨率图像、气象学、实验测量等,通常包含高维特征,高纬度的数据可能不清晰、冗余,甚至具有误导性。数据可视化和解释变量之间的关系很困难,而使用这种高维数据训练的神经网络模型往往容易出现过拟合(维度诅咒)。
主成分分析(PCA)是一种简单而强大的无监督机器学习技术,用于数据降维。它旨在从大型变量集中提取一个较小的数据集,同时尽可能保留原始信息和特征(有损压缩)。PCA有助于识别数据集中最显著和有意义的特征,使数据易于可视化。应用场景包括:统计学、去噪和为机器学习算法预处理数据。

  • 主成分是什么?
    主成分是构建为原始变量的线性组合的新变量。这些新变量是不相关的,并且包含原始数据中大部分的信息。

2 背景数学知识

这些知识对下一节的推导很重要。

  • 正交向量和矩阵:
    • 如果两个向量垂直,则它们是正交的。即两个向量的点积为零。
    • 正交矩阵是一个方阵,其行和列是相互正交的单位向量;每两行和两列的点积为零,每一行和每一列的大小为1。
    • 如果\(A^T=A^{-1}\)或\(AA^T=A^TA=I\),则\(A\)是正交矩阵。
    • 在机器人学中,旋转矩阵通常是一个\(3\times3\)的正交矩阵,在空间变换中它会旋转向量的方向但保持原始向量的大小。
  • 矩阵、向量乘法规则:
    • \((AB)^T=B^TA^T\),两个矩阵的乘积的转置。
    • \(\vec{a}^T\vec{b}=\vec{b}^T\vec{a}\),两个结果都是标量,标量的转置是相同的。
    • \((A + B)C = AC + BC\),乘法是可分配的。
    • \(AB \neq{} BA\),乘法一般不满足交换律。
    • \(A(BC)=(AB)C\),乘法满足结合律。
  • 对称矩阵:
    • \(A=A^T\),\(A\)是对称矩阵。
    • \(X^TX\)是对称矩阵,因为\((X^TX)^T=X^TX\)。
  • 向量导数规则(\(B\)是常量矩阵):
    • \(d(x^TB)/dx=B\)
    • \(d(x^Tx)/dx=2x\)
    • \(d(x^TBx)/dx=2Bx\)
  • 矩阵迹规则:
    • \(Tr(A)=Tr(A^T)\)
    • \(Tr(AB)=Tr(BA)\)
    • \(Tr(A)=\sum_i{\lambda_i}\),其中\(\lambda\)是\(A\)的特征值。
    • 迹在循环移位下不变:\(Tr(ABCD)=Tr(BCDA)=Tr(CDAB)=Tr(DABC)\)
  • 向量和矩阵范数:
    • 向量的\(L^2\)范数,也称为欧几里得范数:\(||x||_2=\sqrt{\sum_i|x_i|^2}\)。
    • 通常使用平方的\(L^2\)范数来衡量向量的大小,可以计算为\(x^Tx\)。
    • Frobenius范数用于衡量矩阵的大小:\(||A||_F=\sqrt{\sum_{i,j}A^2_{i,j}}\)
    • Frobenius范数是所有矩阵元素的绝对平方和的平方根。
    • Frobenius范数是矩阵版本的欧几里得范数。
  • 特征值分解和特征值:
    • 方阵\(A\)的特征向量是一个非零向量\(v\),使得\(A\)的乘法仅改变\(v\)的比例:\(Av=\lambda v\)。\(\lambda\)是特征值,\(v\)是特征向量。
    • 假设矩阵\(A\)有\(n\)个线性无关的特征向量\(v^{(i)}\),我们可以将所有特征向量连接起来形成一个矩阵\(V=[v^{(1)},\ldots,v^{(n)}]\),并通过连接所有特征值\(\lambda=[\lambda_1,\ldots,\lambda_n]^T\)形成一个向量,那么\(A\)的特征分解是\(A=Vdiag(\lambda)V^{-1}\)
    • 每个实对称矩阵都可以分解为\(A=Q\Lambda Q^T\),其中\(Q\)是由\(A\)的特征向量组成的正交矩阵,\(\Lambda\)(读作'lambda')是一个对角矩阵。
  • 拉格朗日乘数法:
    • 拉格朗日乘数法是一种在方程约束下寻找函数局部最大值和最小值的策略。
    • 一般形式:\(\mathcal{L}(x,\lambda)=f(x)+\lambda\cdot g(x)\),\(\lambda\)称为拉格朗日乘子。

3 详细PCA推导

需求描述

我们有\(m\)个点的输入数据,表示为\({x^{(1)},...,x^{(m)}}\)在\(\mathbb{R}^{n}\)的实数集中。因此,每个点\(x^{(i)}\)是一个列向量,具有\(n\)维特征。

需要对输入数据进行有损压缩,将这些点编码以表示它们的较低维度版本。换句话说,我们想要找到编码向量\(c^{(i)}\in \mathbb{R}^{l}\),\((l<n)\)来表示每个输入点\(x^{(i)}\)。我们的目标是找到产生输入的编码向量的编码函数\(f(x)=c\),以及相应的重构(解码)函数\(x\approx g(f(x))\),根据编码向量\(c\)计算原始输入。

解码的\(g(f(x))\)是一组新的点(变量),因此它与原始\(x\)是近似的。存储\(c^{(i)}\)和解码函数比存储\(x^{(i)}\)更节省空间,因为\(c^{(i)}\)的维度较低。

解码矩阵

我们选择使用矩阵\(D\)作为解码矩阵,将编码向量\(c^{(i)}\)映射回\(\mathbb{R}^{n}\),因此\(g(c)=Dc\),其中\(D\in \mathbb{R}^{n\times l}\)。为了简化编码问题,PCA将\(D\)的列约束为彼此正交。

衡量重构的表现

在继续之前,我们需要弄清楚如何生成最优的编码点\(c^{*}\),我们可以测量输入点\(x\)与其重构\(g(c^*)\)之间的距离,使用\(L^2\)范数(或欧几里得范数):\(c^{*}=\arg\min_c||x-g(c)||_2\)。由于\(L^2\)范数是非负的,并且平方操作是单调递增的,所以我们可以转而使用平方的\(L^2\)范数:

\[c^{*}={\arg\min}_c||x-g(c)||_2^2 \]

向量的\(L^2\)范数是其分量的平方和,它等于向量与自身的点积,例如\(||x||_2=\sqrt{\sum|x_i|^2}=\sqrt{x^Tx}\),因此平方的\(L^2\)范数可以写成以下形式:

\[||x-g(c)||_2^2 = (x-g(c))^T(x-g(c)) \]

由分配率:

\[=(x^T-g(c)^T)(x-g(c))=x^Tx-x^Tg(c)-g(c)^Tx+g(c)^Tg(c) \]

由于\(x^Tg(c)\)和\(g(c)^Tx\)是标量,标量等于其转置,\((g(c)^Tx)^T=x^Tg(c)\),所以:

\[=x^Tx-2x^Tg(c)+g(c)^Tg(c) \]

为了找到使上述函数最小化的\(c\),第一项可以省略,因为它不依赖于\(c\),所以:

\[c^*={\arg\min}_c-2x^Tg(c)+g(c)^Tg(c) \]

然后用\(g(c)\)的定义\(Dc\)进行替换:

\[={\arg\min}_c-2x^TDc+c^TD^TDc \]

由于\(D\)的正交性和单位范数约束:

\[c^*={\arg\min}_c-2x^TDc+c^TI_lc \]

\[= {\arg\min}_c-2x^TDc+c^Tc \]

目标函数

现在目标函数是\(-2x^TDc+c^Tc\),我们需要找到\(c^*\)来最小化目标函数。使用向量微积分,并令其导数等于0:

\[\nabla_c(-2x^TDc+c^Tc)=0 \]

根据向量导数规则:

\[-2D^Tx+2c=0 \Rightarrow c=D^Tx \]

找到编码矩阵 \(D\)

所以编码器函数是 \(f(x)=D^Tx\)。因此我们可以定义 PCA 重构操作为 \(r(x)=g(f(x))=D(D^Tx)=DD^Tx\)。

因此编码矩阵 \(D\) 也被重构过程使用。我们需要找到最优的 \(D\) 来最小化重构误差,即输入和重构之间所有维度特征的距离。这里使用 Frobenius 范数(矩阵范数)定义目标函数:

\[D^*={\arg\min}_D\sqrt{\sum_{i,j}(x_j^{(i)}-r(x^{i})_j)^2},\quad D^TD=I_l \]

从考虑 \(l=1\) 的情况开始(这也是第一个主成分),\(D\) 是一个单一向量 \(d\),并使用平方 \(L^2\) 范数形式:

\[d^*={\arg\min}_d{\sum_{i}||(x^{(i)}-r(x^{i}))}||_2^2, ||d||_2=1 \]

\[= {\arg\min}_d{\sum_{i}||(x^{(i)}-dd^Tx^{(i)})||_2^2}, ||d||_2=1 \]

\(d^Tx^{(i)}\) 是一个标量:

\[= {\arg\min}_d{\sum_{i}||(x^{(i)}-d^Tx^{(i)}d)}||_2^2, ||d||_2=1 \]

标量等于其自身的转置:

\[d^*= {\arg\min}_d{\sum_{i}||(x^{(i)}-x^{(i)T}dd)}||_2^2, ||d||_2=1 \]

使用矩阵形式表示

令 \(X\in \mathbb{R}^{m\times n}\) 表示所有描述点的向量堆叠,即 \(\{x^{(1)^T}, x^{(2)^T}, \ldots, x^{(i)^T}, \ldots, x^{(m)^T}\}\),使得 \(X_{i,:}=x^{(i)^T}\)。

\[X = \begin{bmatrix} x^{(1)^T}\\ x^{(2)^T}\\ \ldots\\ x^{(m)^T} \end{bmatrix} \Rightarrow Xd = \begin{bmatrix} x^{(1)^T}d\\ x^{(2)^T}d\\ \ldots\\ x^{(m)^T}d \end{bmatrix} \]

\[\Rightarrow Xdd^T = \begin{bmatrix} x^{(1)^T}dd^T\\ x^{(2)^T}dd^T\\ \ldots\\ x^{(m)^T}dd^T\\ \end{bmatrix} \]

\[\Rightarrow X-Xdd^T = \begin{bmatrix} x^{(1)^T}-x^{(1)^T}dd^T\\ x^{(2)^T}-x^{(2)^T}dd^T\\ \ldots\\ x^{(m)^T}-x^{(m)^T}dd^T\\ \end{bmatrix} \]

矩阵中的一行的转置:

\[(x^{(i)^T}-x^{(i)^T}dd^T)^T=x^{(i)}-dd^Tx^{(i)} \]

由于 \(d^Tx^{(i)}\) 是标量:

\[=x^{(i)}-d^Tx^{(i)}d=x^{(i)}-x^{(i)^T}dd \]

所以我们知道 \(X\) 的第 \(i\) 行的 \(L^2\) 范数与原始形式相同,因此我们可以使用矩阵重写问题,并省略求和符号:

\[d^*={\arg\min}_{d}||X-Xdd^T||_F^2, \quad d^Td=1 \]

利用矩阵迹规则简化 Frobenius 范数部分如下:

\[{\arg\min}_{d}||X-Xdd^T||_F^2 \]

\[={\arg\min}_{d}Tr((X-Xdd^T)^T(X-Xdd^T)) \]

\[={\arg\min}_{d}-Tr(X^TXdd^T)-Tr(dd^TX^TX)+Tr(dd^TX^TXdd^T) \]

\[={\arg\min}_{d}-2Tr(X^TXdd^T)+Tr(X^TXdd^Tdd^T) \]

由于 \(d^Td=1\):

\[={\arg\min}_{d}-2Tr(X^TXdd^T)+Tr(X^TXdd^T) \]

\[={\arg\min}_{d}-Tr(X^TXdd^T) \]

\[={\arg\max}_{d}Tr(X^TXdd^T) \]

由于迹是循环置换不变的,将方程重写为:

\[d^*={\arg\max}_{d}Tr(d^TX^TXd), \quad d^Td=1 \]

由于 \(d^TX^TXd\) 是实数,因此迹符号可以省略:

\[d^*={\arg\max}_{d}d^TX^TXd,\quad d^Td=1 \]

寻找最优的 \(d\)

现在的问题是找到最优的 \(d\) 来最大化 \(d^TX^TXd\),并且有约束条件 \(d^Td=1\)。

使用拉格朗日乘子法来将问题描述为关于 \(d\) 的形式:

\[\mathcal{L}(d,\lambda)=d^TX^TXd+\lambda(d^Td-1) \]

对 \(d\) 求导数(向量导数规则):

\[\nabla_d\mathcal{L}(d,\lambda)=2X^TXd+2\lambda d \]

令导数等于0,\(d\) 将是最优的:

\[2X^TXd+2\lambda d=0 \]

\[X^TXd=-\lambda d \]

\[X^TXd=\lambda' d,\quad(\lambda'=-\lambda) \]

这个方程是典型的矩阵特征值分解形式,\(d\) 是矩阵 \(X^TX\) 的特征向量,\(\lambda'\) 是对应的特征值。

利用上述结果,让我们重新审视原方程:

\[d^*={\arg\max}_{d}d^TX^TXd, \quad d^Td=1 \]

\[={\arg\max}_{d}d^T\lambda' d \]

\[={\arg\max}_{d}\lambda'd^T d \]

\[={\arg\max}_{d}\lambda' \]

现在问题已经变的非常清楚了,\(X^TX\) 的最大特征值会最大化原方程的结果,因此最优的 \(d\) 是矩阵 \(X^TX\) 对应最大特征值的特征向量。

这个推导是针对 \(l=1\) 的情况,只包含第一个主成分。当 \(l>1\) 时,\(D=[d_1, d_2, \ldots]\),第一个主成分 \(d_1\) 是矩阵 \(X^TX\) 对应最大特征值的特征向量,第二个主成分 \(d_2\) 是对应第二大特征值的特征向量,以此类推。


4 总结

我们有一个数据集,包含 \(m\) 个点,记为 \({x^{(1)},...,x^{(m)}}\)。
令 \(X\in \mathbb{R}^{m\times n}\) 为将所有这些点堆叠而成的矩阵:\([x^{(1)^T}, x^{(2)^T}, \ldots, x^{(i)^T}, \ldots, x^{(m)^T}]\)。

主成分分析(PCA)编码函数表示为 \(f(x)=D^Tx\),重构函数表示为 \(x\approx g(c)=Dc\),其中 \(D=[d_1, d_2, \ldots]\) 的列是 \(X^TX\) 的特征向量,特征向量对应的特征值大小为降序排列。\(D^Tx\)即是降维度之后的数据。

标签:范数,Tx,推导,深度,矩阵,arg,PCA,向量,lambda
From: https://www.cnblogs.com/MengWoods/p/18152772

相关文章

  • 【rust】《Rust深度学习[6]-简单实现逻辑回归(Linfa)》
    什么是LinfaLinfa是一组Rust高级库的集合,提供了常用的数据处理方法和机器学习算法。Linfa对标Python上的 scikit-learn,专注于日常机器学习任务常用的预处理任务和经典机器学习算法,目前Linfa已经实现了scikit-learn中的全部算法。项目结构依赖[package]name="rust-ml-e......
  • 【rust】《Rust深度学习[4]-理解线性网络(Candle)》
    全连接/线性在神经网络中,全连接层,也称为线性层,是一种层,其中来自一层的所有输入都连接到下一层的每个激活单元。在大多数流行的机器学习模型中,网络的最后几层是完全连接的。实际上,这种类型的层执行基于在先前层中学习的特征输出类别预测的任务。全连接层的示例,具有四个输入节点......
  • 【rust】《Rust深度学习[5]-理解卷积神经网络(Candle)》
    卷积神经网络ConvolutionalNeuralNetwork,简称为CNN。CNN与一般的顺传播型神经网络不同,它不仅是由全结合层,还由卷积层(ConvolutionLayer)和池层(PoolingLayer)构成的神经网络。在卷积层和池化层中,如下图所示,缩小输入神经元的一部分区域,局部地与下一层进行对应。每一层都有一个称......
  • 【rust】《Rust深度学习[2]-数据分析和挖掘库(Polars)》
    什么是Polars?Polars是一个用于操作结构化数据的高性能DataFrame库,可以用来进行数据清洗和格式转换、数据分析和统计、数据可视化、数据读取和存储、数据合并和拼接等等,相当于Rust版本的Pandas库。Polars读写数据支持如下:  常见数据文件:csv、parquet(不支持xlsx、json文件) ......
  • 【rust】《Rust深度学习[3]-数据可视化(Plotters)》
    什么是Plotters?Plotters是一个用纯Rust开发的图形库,用于中渲染图形、图表和数据可视化。它支持静态图片渲染和实时渲染,并支持多种后端,包括:位图格式(png、bmp、gif等)、矢量图(svg)、窗口和HTML5Canvas。Plotters对不同后端使用统一的高级API,并允许开发者自定义坐标系。在Plotters......
  • 【rust】《Rust深度学习[1]-科学计算库(Ndarray)》
    什么是Ndarray?ndarray是Rust生态中用于处理数组的库。它包含了所有常用的数组操作。简单地说ndarray相当于Rust版本的numpy。ndarray生态系统中crate的文档:ndarray基础库ndarray-rand随机数生成库ndarray-stats统计方法  顺序统计(最小、最大、中值、分位数等);  汇总......
  • 二叉树深度的题目
    #这是一道关于二叉树深度的题目。题目要求我们输入一个二叉树的结点数和每个结点的左右子结点编号,然后输出这棵二叉树的最大深度。#对于这个问题,我们可以使用递归的方法来求解。以下是一个Python的代码示例: depth=1defdfs(node,depth):ifnode==0:retu......
  • Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据
    全文链接:https://tecdat.cn/?p=36004原文出处:拓端数据部落公众号随着大数据时代的来临,深度学习技术在各个领域中得到了广泛的应用。长短期记忆(LSTM)网络作为深度学习领域中的一种重要模型,因其对序列数据的强大处理能力,在自然语言处理、时间序列预测等领域中取得了显著的成果。然......
  • Python利用GPU进行深度学习
    在深度学习当中,我们训练模型通常要对模型进行反复的优化训练,仅用CPU来进行训练的话需要花费很长时间,但是我们可以使用GPU来加速训练模型,这样就可以大大减少训练模型花费的时间。 首先我们需要一张NVIDIA显卡在搜索栏中搜索设备管理器前往NVIDIA官网下载显卡对应的Studio......
  • 初中中考阅读理解难题一网打尽!句子结构深度解析+答案揭秘,助你轻松冲刺中考高分!-009
    PDF格式公众号回复关键字:ZKYDT009原文1Howdidthelotlookatthebeginningofthestory?解析1How怎么样did,thelot场地,look看起来,atthebeginningofthestory?在故事的开头故事开始时,那个场地看起来怎么样?2Thisplacelookslikeadump.这个地方看......