人工智能之SVD算法
原创 张志荣
前言：人工智能机器学习有关算法内容，请参见公众号“科技优化生活”之前相关文章。人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下SVD算法。 ^_^
机器学习中会用到降维方法，常用的降维方法有两种：PCA（主成分分析）和SVD（奇异值分解）。PCA算法之前已经介绍过， 请参见人工智能（46），今天给大家介绍一下SVD算法。
SVD奇异值分解作为一个很基本的算法，在很多机器学习算法中都有它的身影。SVD奇异值分解是线性代数中一种重要的矩阵分解，是矩阵分析中正规矩阵酉对角化的推广。只需要线性代数知识就可以理解SVD算法，简单实用，分解出的矩阵解释性不强，但不影响它的使用，因此值得研究。
SVD在信号处理、统计学、机器学习等领域有重要应用，比如：LSA（隐性语义分析）、推荐系统、图像处理、自然语言处理和特征压缩（或称数据降维）等。SVD奇异值分解则是谱分析理论在任意矩阵上的推广。
SVD算法概念：
SVD奇异值分解（Singular Value Decomposition）是很多机器学习算法的基石。在某些方面与对称矩阵或Hermite矩阵基于特征向量的对角化类似。然而这两种矩阵分解尽管有其相关性，但还是有明显的不同。谱分析的基础是对称阵特征向量的分解，而奇异值分解则是谱分析理论在任意矩阵上的推广。SVD奇异值分解在矩阵理论的重要性不言而喻，它在最优化问题、特征值问题、最小乘方问题、广义逆矩阵、统计学、图像处理和自然语言处理等方面都有十分重要的应用。
SVD算法本质：
SVD算法本质是：将一个比较复杂的矩阵用更小更简单的3个子矩阵的相乘来表示，这3个小矩阵描述了大矩阵重要的特性。
SVD算法描述：
假设矩阵M是一个m×n阶矩阵，其中的元素全部属于域 K，也就是实数域或复数域。存在这样一个分解使得：
其中U是m×m阶酉矩阵；Σ是半正定m×n阶对角矩阵；V*是V的共轭转置，是n×n阶酉矩阵。称这样的分解叫做矩阵M的奇异值分解。Σ对角线上的元素Σi，其中Σi即为M的奇异值。
注：若矩阵V满足：VV* = V*V=En（n阶单位矩阵），则V为酉矩阵。即酉矩阵的共轭转置和它的逆矩阵相等。
常见做法是为了奇异值由大而小排列。如此Σ便能由M唯一确定了。
在矩阵M的奇异值分解中,U的列(columns)组成一套对M的正交"输入"或"分析"的基向量。这些向量是MM*的特征向量。V的列(columns)组成一套对M的正交"输出"的基向量。这些向量是M*M的特征向量。Σ对角线上的元素是奇异值，可视为是在输入与输出间进行的标量的"膨胀控制"。这些是M*M及MM*的奇异值，并与U和V的列向量相对应。
对于任意的奇异值分解，矩阵Σ的对角线上的元素等于M的奇异值。U和V的列分别是奇异值中的左、右奇异向量。
如果一个奇异值中可以找到两个左（或右）奇异向量是线性相关的，则称为退化。退化的奇异值具有不唯一的奇异向量。如果M 具有退化的奇异值，则它的奇异值分解是不唯一的。
非退化的奇异值具有唯一的左、右奇异向量。因此，如果M的所有奇异值都是非退化且非零，则它的奇异值分解是唯一的。
奇异值往往隐含着矩阵M中潜在的重要信息，重要性和奇异值大小正相关，每一个矩阵可以表示成一系列的秩为1的特殊矩阵之和，而奇异值则是衡量这些矩阵的权重。
SVD几何意义：
根据公式M=UΣV* 。
因为U 和V 向量都是单位化的向量, U的列向量u1,...,um组成了K空间的一组标准正交基。同样，V的列向量v1,...,vn也组成了K空间的一组标准正交基。
几何意义是：将一个向量从V这组正交基向量的空间旋转到U这组正交基向量的空间，并且按照Σ在各个方向做了缩放，缩放的倍数就是奇异值。
SVD算法优点：
1）算法稳定；
2）适用面广；
3）简化数据，减小处理量；
4）去除噪声；
5）算法效果好。
SVD算法缺点：
1）计算代价很大，时间复杂度是3次方的，空间复杂度是2次方的；
2）不能共享内存；
3）很难并行计算；
4）数据转换可能难以理解。
SVD算法应用：
SVD算法的应用范围广泛。SVD奇异值分解算法经常用在信号处理、统计学模式识别、图像处理和机器学习等领域，比如LSA（隐性语义分析）、推荐系统、特征压缩、数据降维等。
1）SVD算法被用来计算矩阵的伪逆从而可以求解线性最小平方、最小二乘法问题。
2）利用SVD算法中的平行奇异值把频率选择性衰落信道进行分解。
3）SVD在统计中的主要应用为PCA主成分分析，用来找出大量数据中所隐含的“模式”，它可以用在模式识别，数据压缩等方面。
4）SVD算法可以实现降维，把数据集映射到低维空间中。数据集的特征值在SVD中用奇异值来表征，按照重要性排列，降维过程就是舍弃不重要的特征向量的过程，而剩下的特征向量组成的空间即为降维后的空间。
5）在图像处理领域，SVD算法不仅可以应用在数据压缩上，还可以对图像进行降噪处理。
结语:
SVD算法是一个降维算法，是很多机器学习领域算法的基础。SVD算法是线性代数中一种重要的矩阵分解，是矩阵分析中正规矩阵酉对角化的推广。SVD算法是一种非常实用的学习算法，应用范围很广，在信号处理、统计学、机器学习等领域有重要应用。简单实用，分解出的矩阵解释性不强，但不影响它的使用，因此值得研究。
------以往文章推荐-----
机器学习
深度学习
人工神经网络
决策树
随机森林
强化学习
迁移学习
遗传算法
朴素贝叶斯
支持向量机
蒙特卡罗方法
马尔科夫模型
Hopfield神经网络
回归模型
K邻近算法
卷积神经网络
受限玻尔兹曼机
循环神经网络
长短时记忆神经网络
Adaboost算法
ID3算法
C4.5算法
CART算法
K-Means算法
Apriori算法
PCA算法
ICA算法
TD-Learning算法
Q-Learning算法
SOM算法
GBM算法
GBDT算法
EM算法
