机器学习（十三）——机器学习中的矩阵方法（3）病态矩阵、协同过滤的ALS算法（1） 协同过滤的ALS算法
http://antkillerfarm.github.io/
向量的范数（续）
范数可用符号表示。
经常使用的有：
这里不做解释的给出例如以下示意图：
当中，0范数表示向量中非0元素的个数。
上图中的图形被称为 ball。
表征在同一范数条件下，具有相同距离的点的集合。
范数满足例如以下不等式：
向量范数推广可得到矩阵范数。
某些矩阵范数满足例如以下公式：
这种范数被称为相容范数。
注：矩阵范数要比向量范数复杂的多。还包括一些不能够由向量范数来诱导的范数，如Frobenius范数。并且仅仅有极少数矩阵范数，可由简单表达式来表达。
这里篇幅有限，不再赘述。
病态矩阵
如今有线性系统：
非常easy得到解为：
则得到一个截然不同的解：。
当解集x对A和b的系数高度敏感。那么这种方程组就是病态的 (ill-conditioned/ill-posed)。
从上例的情况来看，矩阵的行向量实际上是过于线性相关了，从而导致矩阵已经接近神秘矩阵（near singular matrix）。
病态矩阵实际上就是神秘矩阵和近神秘矩阵的还有一个说法。
參见：
http://www.cnblogs.com/daniel-D/p/3219802.html
矩阵的条件数
我们首先如果向量b受到扰动，导致解集x产生偏差。即：
也就是：
因此，由矩阵相容性可得：
同一时候。由于：
所以：
即：
我们定义矩阵的条件数
相同的，我们针对A的扰动。所导致的x的偏差。也可得到类似的结论：
可见，矩阵的条件数是描写叙述输入扰动对输出结果影响的量度。显然，条件数越大。矩阵越病态。
然而这个定义，在病态矩阵的条件下。并不能直接用于数值计算。由于浮点数所引入的微小的量化误差，也会导致求逆结果的非常大误差。
所以通常情况下，一般使用矩阵的特征值或神秘值来计算条件数。
如果A是2阶方阵，它有两个单位特征向量。
由之前的讨论可知，的线性组合所表示，即：
从这里能够看出。b在有非常密切的关系。神秘值实际上也有类似的特点。
因此，普通情况下，条件数也能够由最大神秘值与最小神秘值之间的比值。或者最大特征值和最小特征值之间的比值来表示。这里的最大和最小。都是针对绝对值而言的。
參见：
https://en.wikipedia.org/wiki/Condition_number
矩阵规则化
病态矩阵处理方法有非常多，这里仅仅介绍矩阵规则化（regularization）方法。
机器学习领域，经经常使用到各种损失函数（loss function）。也称花费函数（cost function）。这里我们用：
表示损失函数。
当样本数远小于特征向量维数时，损失函数所表示的矩阵是一个稀疏矩阵，并且往往还是一个病态矩阵。这时，就须要引入规则化因子用以改善损失函数的稳定性：
当中的表示规则化因子的权重。
注：稀疏矩阵并不一定是病态矩阵。比方单位阵就不是病态的。可是从系统论的角度，高维空间中样本量的稀疏，的确会带来非常大的不确定性。
函数V（又叫做Fit measure）和R（又叫做Entropy measure），在不同的算法中。有不同的取值。
比方，在Ridge regression问题中：
Ridge regression问题中规则化方法，又被称为 regularization，或Tikhonov regularization。
注：Andrey Nikolayevich Tikhonov，1906~1993，苏联数学家和地球物理学家。大地电磁学的发明人之中的一个。苏联科学院院士。
著有《Solutions of Ill-posed problems》一书。
很多其它的V和R取值參见：
https://en.wikipedia.org/wiki/Regularization_(mathematics)
从形式上来看，对照之前提到的拉格朗日函数，我们能够发现规则化因子。实际上就是给损失函数添加了一个约束条件。它的优点是添加了解向量的稳定度，缺点是添加了数值解和真实解之间的误差。
为了更便于理解规则化。这里以二维向量空间为例，给出了规则化因子对损失函数的约束效应。
上图中的圆圈是损失函数的等高线。坐标原点是规则化因子的约束中心。左图的方形和右图的圆形是 ball的焦点，实际上也就是这个带约束的优化问题的解。
能够看出 regularization会导致矩阵的稀疏。
參见：
https://en.wikipedia.org/wiki/Tikhonov_regularization
http://www.mit.edu/~cuongng/Site/Publication_files/Tikhonov06.pdf
http://blog.csdn.net/zouxy09/article/details/24971995
协同过滤概述
注：近期研究商品推荐系统的算法。因此，Andrew Ng讲义的内容，兴许再写。
协同过滤是眼下非常多电商、社交站点的用户推荐系统的算法基础，也是眼下工业界应用最广泛的机器学习领域。
协同过滤是利用集体智慧的一个典型方法。
要理解什么是协同过滤 (Collaborative Filtering,简称CF)，首先想一个简单的问题，如果你如今想看个电影，但你不知道详细看哪部。你会怎么做？大部分的人会问问周围的朋友，看看近期有什么好看的电影推荐，而我们一般更倾向于从口味比較类似的朋友那里得到推荐。
这就是协同过滤的核心思想。
怎样找到类似的用户和物品呢？事实上就是计算用户间以及物品间的类似度。下面是几种计算类似度的方法：
欧氏距离
Cosine类似度
皮尔逊相关系数（Pearson product-moment correlation coefficient，PPMCC or PCC）：
该系数由Karl Pearson发明。
參见《机器学习（二）》中对Karl Pearson的简单介绍。Fisher对该系数也有研究和贡献。
如上图所看到的，Cosine类似度计算的是两个样本点和坐标原点之间的直线的夹角。而PCC计算的是两个样本点和数学期望点之间的直线的夹角。
PCC能够有效解决。在协同过滤数据集中，不同用户评分尺度不一的问题。
參见：
https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient
Spearman秩相关系数（Spearman’s rank correlation coefficient）
对秩变量（ranked variables）套用PCC公式，就可以得Spearman秩相关系数。
秩变量是一类不在乎值的详细大小，而仅仅关心值的大小关系的统计量。
| 86 | 0 | 1 | 1 | 0 | 0 |
| 97 | 20 | 2 | 6 | −4 | 16 |
| 99 | 28 | 3 | 8 | −5 | 25 |
| 100 | 27 | 4 | 7 | −3 | 9 |
| 101 | 50 | 5 | 10 | −5 | 25 |
| 103 | 29 | 6 | 9 | −3 | 9 |
| 106 | 7 | 7 | 3 | 4 | 16 |
| 110 | 17 | 8 | 5 | 3 | 9 |
| 112 | 6 | 9 | 2 | 7 | 49 |
| 113 | 12 | 10 | 4 | 6 | 36 |
如上表所看到的，。
当没有反复值的时候，也可用例如以下公式计算相关系数：
注：Charles Spearman。1863～1945，英国心理学家。这个人的经历比較独特，20岁从军，15年之后退役。然后，进入德国莱比锡大学读博。中间又被军队征召，參加了第二次布尔战争，因此，直到1906年才拿到博士学位。伦敦大学学院心理学教授。
虽然他的学历和教职，都是心理学方面的。但他最大的贡献，却是在统计学领域。他也是由于在统计学方面的成就，得以当选皇家学会会员。
话说那个时代的统计学大牛，除了Fisher之外。基本都是副业比主业强。仅仅有Fisher。主业方面也是那么牛逼。不服不行啊。
由上图可见，Pearson系数关注的是两个变量之间的线性相关度，而Spearman系数能够应用到非线性或者难以量化的领域。
參见：
https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient