8

机器学习（十三）——协同过滤的ALS算法（1）

 3 years ago
source link: http://antkillerfarm.github.io/ml/2016/09/26/Machine_Learning_13.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

机器学习（十三）——协同过滤的ALS算法（1）

2016-09-26

因子分析模型（续）

把这些结果合在一起，可得：

(1)[zx]∼N([0→μ],[IΛTΛΛΛT+Ψ])

从这个结论可以看出：x∼N(μ,ΛΛT+Ψ)

因此它的对数似然函数为：

ℓ(μ,Λ,Ψ)=log⁡∏i=1m1(2π)n/2|ΛΛT+Ψ|1/2exp⁡(−12(x(i)−μ)T(ΛΛT+Ψ)−1(x(i)−μ))

但这个函数是很难最大化的，需要使用EM算法解决之。

因子分析的EM估计

E-step比较简单。由《机器学习（十）》公式1、2和公式1，可得：

μz(i)∣x(i)=ΛT(ΛΛT+Ψ)−1(x(i)−μ)Σz(i)∣x(i)=I−ΛT(ΛΛT+Ψ)−1ΛQi(z(i))=1(2π)n/2|Σz(i)∣x(i)|1/2exp⁡(−12(x(i)−μz(i)∣x(i))TΣz(i)∣x(i)−1(x(i)−μz(i)∣x(i)))

M-step的最大化的目标是：

∑i=1m∫z(i)Qi(z(i))log⁡p(x(i),z(i);μ,Λ,Ψ)Qi(z(i))dz(i)

下面我们重点求Λ的估计公式。

首先将上式简化为:

∑i=1m∫z(i)Qi(z(i))log⁡p(x(i)∣z(i);μ,Λ,Ψ)p(z(i))Qi(z(i))dz(i)=∑i=1m∫z(i)Qi(z(i))[log⁡p(x(i)∣z(i);μ,Λ,Ψ)+log⁡p(z(i))−log⁡Qi(z(i))]dz(i)=∑i=1mEz(i)∼Qi[log⁡p(x(i)∣z(i);μ,Λ,Ψ)+log⁡p(z(i))−log⁡Qi(z(i))]

去掉和各参数无关的部分后，可得：

∑i=1mE[log⁡p(x(i)∣z(i);μ,Λ,Ψ)]=∑i=1mE[1(2π)n/2|Ψ|1/2exp⁡(−12(x(i)−μ−Λz(i))TΨ−1(x(i)−μ−Λz(i)))]=∑i=1mE[−12log⁡|Ψ|−n2log⁡(2π)−12(x(i)−μ−Λz(i))TΨ−1(x(i)−μ−Λz(i))]

去掉和Λ无关的部分，并求导可得：

(2)∇Λ∑i=1m−E[12(x(i)−μ−Λz(i))TΨ−1(x(i)−μ−Λz(i))]

因为公式2中E[⋅]部分的结果实际上是个实数，因此该公式可变形为：

∇Λ∑i=1m−E[tr⁡(12(x(i)−μ−Λz(i))TΨ−1(x(i)−μ−Λz(i)))]12(x(i)−μ−Λz(i))TΨ−1(x(i)−μ−Λz(i))=12[((x(i)−μ)T−(Λz(i))T)Ψ−1((x(i)−μ)−Λz(i))]=12[(x(i)−μ)TΨ−1(x(i)−μ)−(x(i)−μ)TΨ−1Λz(i)−(Λz(i))TΨ−1(x(i)−μ)+(Λz(i))TΨ−1Λz(i)]

去掉和Λ无关的部分，可得：

12[(Λz(i))TΨ−1Λz(i)−(x(i)−μ)TΨ−1Λz(i)−(Λz(i))TΨ−1(x(i)−μ)]∇Λ∑i=1m−E[tr⁡(12[(Λz(i))TΨ−1Λz(i)−(x(i)−μ)TΨ−1Λz(i)−(Λz(i))TΨ−1(x(i)−μ)])]=∇Λ∑i=1m−E[12tr⁡((Λz(i))TΨ−1Λz(i))−12tr⁡((x(i)−μ)TΨ−1Λz(i))−12tr⁡((Λz(i))TΨ−1(x(i)−μ))](3)=∑i=1m∇ΛE[−12tr⁡(ΛTΨ−1Λz(i)(z(i))T)+tr⁡(ΛTΨ−1(x(i)−μ)(z(i))T)]∇Atr⁡ABATC=CAB+CTABT∇Atr⁡(ΛTΨ−1Λz(i)(z(i))T)=z(i)(z(i))TΛTΨ−1+(z(i)(z(i))T)TΛT(Ψ−1)T=z(i)(z(i))TΛTΨ−1+((z(i))T)T(z(i))TΛTΨ−1=2z(i)(z(i))TΛTΨ−1

代入公式3，可得：

∑i=1mE[−Ψ−1Λz(i)(z(i))T+Ψ−1(x(i)−μ)(z(i))T]

由上式等于0，可得：

∑i=1mΛEz(i)∼Qi[z(i)(z(i))T]=∑i=1m(x(i)−μ)Ez(i)∼Qi[(z(i))T](4)Λ=(∑i=1m(x(i)−μ)Ez(i)∼Qi[(z(i))T])(∑i=1mEz(i)∼Qi[z(i)(z(i))T])−1Cov⁡(Y)=E[YYT]−E[Y]E[Y]TE[YYT]=E[Y]E[Y]T+Cov⁡(Y)

因此根据之前的讨论可得：

Ez(i)∼Qi[(z(i))T]=μz(i)∣x(i)TEz(i)∼Qi[z(i)(z(i))T]=μz(i)∣x(i)μz(i)∣x(i)T+Σz(i)∣x(i)

将上式代入公式4，可得：

Λ=(∑i=1m(x(i)−μ)μz(i)∣x(i)T)(∑i=1m(μz(i)∣x(i)μz(i)∣x(i)T+Σz(i)∣x(i)))−1

这里需要注意的是，和之前的混合高斯模型相比，我们不仅要计算Σz(i)∣x(i)，还要计算E[z]和E[zzT]。

此外，我们还可得出：（推导过程略）

μ=1m∑i=1mx(i)Φ=1m∑i=1m(x(i)(x(i))T−x(i)μz(i)∣x(i)TΛT−Λμz(i)∣x(i)(x(i))T+Λ(μz(i)∣x(i)μz(i)∣x(i)T+Σz(i)∣x(i))ΛT)

协同过滤的ALS算法

协同过滤概述

注：最近研究商品推荐系统的算法，因此，Andrew Ng讲义的内容，后续再写。

协同过滤是目前很多电商、社交网站的用户推荐系统的算法基础，也是目前工业界应用最广泛的机器学习领域。

协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering,简称CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。

如何找到相似的用户和物品呢？其实就是计算用户间以及物品间的相似度。以下是几种计算相似度的方法：

d(x,y)=∑(xi−yi)2,sim(x,y)=11+d(x,y)

Cosine相似度

cos⁡(x,y)=⟨x,y⟩∣x∣∣y∣=∑xiyi∑xi2∑yi2

这里有一个实现上需要注意的地方：

x2不可以用pow(x,2)实现，因为这里的x有可能是负数。而负数的pow运算，计算机是不支持的。

皮尔逊相关系数（Pearson product-moment correlation coefficient，PPMCC or PCC）：

p(x,y)=cov(X,Y)σXσY=E⁡[XY]−E⁡[X]E⁡[Y]E⁡[X2]−E⁡[X]2E⁡[Y2]−E⁡[Y]2=n∑xiyi−∑xi∑yin∑xi2−(∑xi)2n∑yi2−(∑yi)2

该系数由Karl Pearson发明。参见《机器学习（二）》中对Karl Pearson的简介。Fisher对该系数也有研究和贡献。

如上图所示，Cosine相似度计算的是两个样本点和坐标原点之间的直线的夹角，而PCC计算的是两个样本点和数学期望点之间的直线的夹角。

PCC能够有效解决，在协同过滤数据集中，不同用户评分尺度不一的问题。

https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient

https://mp.weixin.qq.com/s/RjpH7XD5SCMkrSdcmG394g

从PCC到MIC，一文教你如何计算变量之间的相关性

Spearman秩相关系数（Spearman’s rank correlation coefficient）

对秩变量（ranked variables）套用PCC公式，即可得Spearman秩相关系数。

秩变量是一类不在乎值的具体大小，而只关心值的大小关系的统计量。

Xi Yi xi yi di di2
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

如上表所示，Xi和Yi是原始的变量值，xi和yi是rank之后的值，di=xi−yi。

当Xi和Yi没有重复值的时候，也可用如下公式计算相关系数：

rs=1−6∑di2n(n2−1)

注：Charles Spearman，1863～1945，英国心理学家。这个人的经历比较独特，20岁从军，15年之后退役。然后，进入德国莱比锡大学读博，中间又被军队征召，参加了第二次布尔战争，因此，直到1906年才拿到博士学位。伦敦大学学院心理学教授。
尽管他的学历和教职，都是心理学方面的。但他最大的贡献，却是在统计学领域。他也是因为在统计学方面的成就，得以当选皇家学会会员。
话说那个时代的统计学大牛，除了Fisher之外，基本都是副业比主业强。只有Fisher，主业方面也是那么牛逼，不服不行啊。

由上图可见，Pearson系数关注的是两个变量之间的线性相关度，而Spearman系数可以应用到非线性或者难以量化的领域。

https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK