Category Archives: Computer Science

Forward-Backward Splitting (FOBOS) 算法简介

 

FOBOS 算法简介

(1)FOBOS(Forward Backward Splitting)算法原理

前向后向切分(FOBOS,Forward Backward Splitting)是 John Duchi 和 Yoran Singer 提出的。在该算法中,权重的更新分成两个步骤:

W^{(t+0.5)}=W^{(t)}-\eta^{(t)}G^{(t)}

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

第一个步骤实际上是一个标准的梯度下降(SGD),第二个步骤是对第一个步骤的结果进行局部调整。写成一个公式那就是:

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

假设 F(W)=\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W),如果 W^{(t+1)} 存在一个最优解,那么可以推断 0 向量一定属于 F(W) 的次梯度集合:

0 \in \partial F(W)=W-W^{(t)}+\eta^{(t)}G^{(t)}+\eta^{(t+0.5)}\partial\Psi(W).

因为 W^{(t+1)}=argmin_{W}F(W), 那么可以得到权重更新的另外一种形式:

W^{(t+1)}=W^{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t+0.5)}\partial\Psi(W^{(t+1)})

从上面的公式可以看出,更新后的 W^{(t+1)} 不仅和 W^{(t)} 有关,还和自己 \Psi(W^{(t+1)}) 有关。这也许就是”前向后向切分”这个名称的由来。

(2)FOBOS(Forward Backward Splitting)的 L1 正则化

假设 \Psi(W) 是 L1 范数,中间向量是 W^{(t+0.5)}=(v_{1},...,v_{N})\in\mathbb{R}^{N}, 并且参数 \tilde{\lambda}=\eta^{(t+0.5)}\lambda,那么公式就可以展开得到

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

=argmin_{W}\sum_{i=1}^{N}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|).

所以,可以对特征权重 W 的每一个维度进行单独求解:

w^{(t+1)}_{i}=argmin_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|) for all $latex 1\leq i \leq N$.

Claim. 如果 w_{i}^{*}\min_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|) 的最优解,那么 w_{i}^{*}v_{i}\geq 0.

证明:反证法,如果 w_{i}^{*}v_{i}<0,那么 \frac{1}{2}v_{i}^{2}<\frac{1}{2}(w_{i}^{*}-v_{i})^{2}+\tilde{\lambda}|w_{i}^{*}|, 这与条件矛盾。

通过数学计算可以证明:在 L1 正则化下,FOBOS 的特征权重的各个维度的更新公式是:

w_{i}^{(t+1)}=sgn(v_{i})\max(0,|v_{i}|-\tilde{\lambda})

= sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\} for all 1\leq i \leq N,

其中 g_{i}^{(t)} 是梯度 G^{(t)} 在第 i 个维度的分量。

从公式上看,

如果 |w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\leq\eta^{(t+0.5)}\lambda, 则有 w_{i}^{(t+1)}=0. 意思就是如果这次训练产生梯度的变化不足以令权重值发生足够大的变化时,就认为在这次训练中该维度不够重要,应该强制其权重是0.

如果 |w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\geq\eta^{(t+0.5)}\lambda,那么则有

w_{i}^{(t+1)}=(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})-\eta^{(t+0.5)}\lambda \cdot sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})

L1-FOBOS 的算法:

(1)输入 \lambda,初始化 W\in\mathbb{R}^{N}
(2)for t=1,2,3..., 计算 G=\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
     按照公式更新 Ww_{i} = sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\} 
     for all 1\leq i \leq N
(3)Return W

(3)L1-FOBOS 与 Truncated Gradient 的关系

\theta=+\infty, k=1, \lambda_{TG}^{(t)}=\eta^{(t+0.5)}\lambda,可以得到 L1-FOBOS 与 Truncated Gradient 完全一致,换句话说 L1-FOBOS 是 Truncated Gradient 在一些特定条件下的形式。

 

Regularized Dual Averaging Algorithm (RDA)

Regularized Dual Averaging Algorithm 算法介绍

(一)RDA(Regularized Dual Averaging Algorithm)算法原理

RDA(Regularized Dual Averaging Algorithm)叫做正则对偶平均算法,特征权重的更新策略是:

W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \Psi(W) +\frac{\beta^{(t)}}{t}h(W)\}

其中 G^{(t)}\cdot W 指的是向量 G^{(t)}W 的内积,\Psi(W) 是正则项,h(W) 是一个严格凸函数,\{\beta^{(t)}|t\geq 1\} 是一个非负递增序列。

从公式中可以看出:

  1. \frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W 包括了之前所有梯度的平均值。
  2. 具有正则项 \Psi(W)
  3. 额外项 \frac{\beta^{(t)}}{t}h(W)

 (二)RDA 的 L1 正则化

假设 \Psi(W)=||W||_{1}h(W)=\frac{1}{2}||W||_{2}^{2},i.e. h(W) 是一个严格凸函数;\beta^{(t)}=\gamma\sqrt{t} \text{ with } \gamma>0 是一个非负递增序列。那么 RDA 算法就可以写成:

W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \lambda||W||_{1}+\frac{\gamma}{2\sqrt{t}}||W||_{2}^{2}\}

此时可以采取同样的策略,把各个维度拆分成 N 个独立的问题来处理。也就是:

w_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}

其中,\lambda>0, \gamma>0,  \overline{g}_{i}^{(t)}=\frac{1}{t}\sum_{r=1}^{t}g_{i}^{(r)}.

通过数学推导可以证明:

w_{i}^{(t+1)}=0, if |\overline{g}_{i}^{(t)}|<\lambda

w_{i}^{(t+1)}=-\frac{\sqrt{t}}{\gamma}(\overline{g}_{i}^{(t)}-\lambda\cdot sgn(\overline{g}_{i}^{(t)})), otherwise

意思就是:当某个维度的累加平均值 |\overline{g}_{i}^{(t)}| 小于 \lambda 时,该维度的权重被设置成零,此时就可以产生特征权重的稀疏性。

RDA 的算法

(1)输入 \gamma, \lambda,初始化 W\in \mathbb{R}^{N}, G=0\in\mathbb{R}^{N}
(2)for t=1,2,3... 
         G=\frac{t-1}{t}G+\frac{1}{t}\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
         更新 Ww_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}
     end
     return W

(三)L1-RDA 与 L1-FOBOS 的对比

从截断方式来看,在 RDA 的算法中,只要梯度的累加平均值小于参数 \lambda,就直接进行截断,说明 RDA 更容易产生稀疏性;同时,RDA 中截断的条件是考虑梯度的累加平均值,可以避免因为某些维度训练不足而导致截断的问题,这一点与 TG,FOBOS 不一样。通过调节参数 \lambda 可以在精度和稀疏性上进行权衡。

(四)L1-RDA 与 L1-FOBOS 形式上的统一

在 L1-FOBOS 中,假设 \eta^{(t+0.5)}=\eta^{(t)}=\Theta(t^{-0.5}),可以得到:

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t)}\lambda||W||_{1}\}

通过计算可以把 L1-FOBOS 写成:

W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-W^{(t)}||_{2}^{2}

同时 L1-RDA 可以写成:

W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-0||_{2}^{2} \}

其中 G^{(1:t)}=\sum_{s=1}^{t}G^{(s)}。如果令 \sigma^{(s)}=\frac{1}{\eta^{(s)}}-\frac{1}{\eta^{(s-1)}}, \sigma^{(1:t)}=\frac{1}{\eta^{(t)}}, \sigma^{(1:t)}=\sum_{s=1}^{t}\sigma^{(s)}, 上面的公式可以写成:

L1-FOBOS:

W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-W^{(t)}||_{2}^{2}\}

L1-RDA :

W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-0||_{2}^{2} \}

可以看出:

  1. L1-FOBOS 考虑了梯度和当前模的 L1 正则项,L1-RDA 考虑的是累积梯度。
  2. L1-FOBOS 的第三项限制 W 不能够距离已经迭代过的 W^{(t)} 值太远,L1-RDA 的第三项限制的是 W 不能够距离 0 太远。

KL散度(Kullback-Leibler Divergence)

在信息论和概率论里面,Kullback-Leibler 散度(简称KL散度,KL divergence)是两个概率分布 PQ 的一个非对称的度量公式。这个概念是由 Solomon Kullback 和 Richard Leibler 在 1951 年引入的。从概率分布 Q 到概率分布 P 的 KL 散度用 D_{KL}(P||Q) 来表示。尽管从直觉上看 KL 散度是一个度量或者是一个距离,但是它却不满足度量或者距离的定义。例如,从 QP 的 KL 散度就不一定等于从 PQ 的 KL 散度。

KL 散度的数学定义:

对于离散空间的两个概率分布 PQ 而言,从 QP 的KL散度被定义为

D_{KL}(P||Q)=\sum_{i}P(i)\log_{2}(P(i)/Q(i)).

换句话说,它是两个概率分布 PQ 的对数差的期望,这里的期望是以概率 P 来描述的。KL散度有定义当且 Q(i)=0 \implies P(i)=0 对于所有的 i 都成立。如果 P(i)=0, 那么可以假设KL散度的第 i 项是零,因为 \lim_{x\rightarrow 0^{+}}x\log_{2}x=0.

对于连续空间 X 的两个概率分布 PQ 而言,从 QP 的 KL 散度被定义为:

D_{KL}(P||Q)=\int_{X}p(x)\log_{2}(p(x)/q(x))dx,

这里的 pq 是概率分布 PQ 的概率密度。

KL 散度的基本性质:

(1)KL 散度总是非负的,并且只有 P(x)=Q(x) 几乎处处成立的时候,才会有

D_{KL}(P||Q)=0.

证明:利用Jensen’s Inequality。

D_{KL}(P||Q)=-E_{P}(\log_{2}(q(x)/p(x)))

\geq -log_{2}(E_{p}(q(x)/p(x)))=-log_{2}(\int_{X}q(x)dx)=0.

(2)如果 P_{1}, P_{2} 是独立分布,并且联合分布是 P(x,y)=P_{1}(x)P_{2}(y), Q_{1},Q_{2} 是独立分布并且联合分布是 Q(x,y)=Q_{1}(x)Q_{2}(y), 那么

D_{KL}(P||Q)=D_{KL}(P_{1}||Q_{1}) + D_{KL}(P_{2}||Q_{2}).

(3)如果定义分布 PQ 的交叉墒是

H(P,Q)=-\int_{X}p(x)\log_{2}q(x)dx,

分布P的熵是

H(P)=-\int_{X}p(x)\log_{2}p(x)dx,

那么 D_{KL}(P||Q)=H(P,Q)-H(P).

(4)KL 散度是两个概率分布 PQ 差别的非对称性的度量。 KL 散度是用来度量使用基于 Q 的编码来编码来自 P 的样本平均所需的额外的位元数。典型情况下, P 表示数据的真实分布,Q 表示数据的理论分布,模型分布,或 P 的近似分布。

(5)从KL散度的定义可以得出

D_{KL}(P||Q)\neq D_{KL}(Q||P),

所以 KL 散度不满足距离的对称性。当然,如果需要把它弄成对称的,可以定义

DS_{KL}(P,Q)=(D_{KL}(P||Q) + D_{KL}(Q||P))/2.

简单例子:

比如有四个类别,一个方法 P 得到四个类别的概率分别是0.1,0.2,0.3,0.4。另一种方法 Q(或者说是事实情况)是得到四个类别的概率分别是0.4,0.3,0.2,0.1,那么这两个分布的 KL 散度就是

D_{KL}(P||Q)

=0.1*\log_{2}(0.1/0.4) + 0.2*\log_{2}(0.2/0.3) + 0.3*\log_{2}(0.3/0.2) + 0.4*\log_{2}(0.4/0.1).

案例分析:

在实际的工作中,我们通常会有某个网页或者app被用户点击或者播放的数据,同时,我们会拥有用户画像(personas),此刻我们关心的问题就是如何计算网页里面的某个新闻或者app里面的某个专辑受到不同维度的用户画像的喜好程度。比如,如何判断该新闻是受到各个年龄层的用户的喜爱还是只是受到某个年龄层的用户的喜爱?如何判断某个电台节目是受到大众的喜爱还是更加受到男性或者女性的喜爱?此时,怎么计算物品被用户的喜欢程度就成为了一个重要的关键。

通常的方案就是,比方说:某个电台专辑被66.7%的男性用户播放过,被33.3%的女性用户播放过,那么该物品是不是真的就是更加受到男性用户的青睐呢?答案是否定的。如果使用这款app的用户的男女比例恰好是1:1,那么根据以上数据,该电台专辑显然更加受到男性用户的喜爱。但是,实际的情况,使用这款app的用户的男女比例不完全是1:1。如果男性用户:女性用户=2:1的话,如果某个电台专辑被66.7%的男性用户播放过,被33.3%的女性用户播放过,那么说明该专辑深受男女喜欢,两者对该专辑的喜好程度是一样的。因为基础的男女比例是2:1,该专辑被男女播放的比例是2:1,所以,该专辑对男女的喜爱程度恰好是1:1。

那么如何计算该专辑的喜好程度呢?首先我们会使用KL散度来描述这件事情。

 

 

 

 

 

 

 

 

 

机器学习的基本模型—入门知识

机器学习的各种算法在于如何使用特定函数与已知的数据集相匹配,从而达到训练和测试的目的。本篇文章对一些近似的模型做一些相应的介绍。

线性模型

一维输入变量

假设学习对象f函数的输入是一组实数,那么对该函数进行近似的时候,最简单的方案就是f_{\theta}(x)=\theta\cdot x。在这里,\theta是这个函数的斜率,也就是这个函数f_{\theta}(x)的参数。机器学习就是通过对这个参数的学习,完成函数的近似计算。这个模型对于\theta而言是一个线性函数,操作起来十分方便,但是对于实际的情况来说,该模型过于简单,没有太大的使用价值。 由于上面这个模型过于简单,那么在实际应用中,会对上述的模型进行必要的扩展,使得函数f_{\theta}(x)变成参数的线性模型,这样这个模型就可以用来表示非线性的输入和输出了。可以把\theta\cdot x扩展成如下形式:

f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(x).

在这个式子中,\phi_{j}(x)是基函数向量\phi(x)=(\phi_{1}(x),\cdot\cdot\cdot,\phi_{b}(x))^{T}的第j个分量,\theta_{j}\theta=(\theta_{1},\cdot\cdot\cdot,\theta_{b}))^{T}的第j个分量,b是基函数\phi(x)的维数。根据上面f_{\theta}(x)的定义,可以得到该函数是参数向量\theta的线性函数。也就是说对于b维参数\theta,\theta^{'}\alpha\in \mathbb{R},满足

f_{\theta+\theta^{'}}(x)=f_{\theta}(x)+f_{\theta^{'}}(x),

f_{\alpha \theta}(x)=\alpha f_{\theta}(x).

那么这个时候如何选择基函数\phi(x)就成为了一个关键所在。

数学分析里面有一个经典定理叫做Weierstrass定理,陈述如下:

Weierstrass第一逼近定理:假设f(x)是闭区间[a,b]上的连续函数,对于任意的\epsilon>0,则存在多项式P(x)使得对于所有的x\in [a,b],有|f(x)-P(x)|<\epsilon 

根据Weierstrass第一逼近定理,对于任何一个闭区间上面的连续函数,都可以用多项式去逼近。所以联系到机器学习,就可以把基函数\phi(x)的分量设置为多项式,换句话说

\phi_{j}(x)=x^{j-1}

\phi(x)=(1,x,x^{2},\cdot\cdot\cdot, x^{b-1})^{T}.

那么上述的\theta的线性函数却是关于自变量x的非线性函数,而且f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\cdot x^{j-1}可以逼近关于x的闭区间上任何一个连续函数。

与Weierstrass逼近定理类似,用Fourier级数也可以逼近Lipchitz连续函数。所以也可以选择基函数

\phi_{0}(x)=1,\phi_{2j-1}(x)=\sin(jx),\phi_{2j}(x)=\cos(jx), 其中j\geq 1. 

简单来说就是令b=2m+1, \phi(x)=(1,\sin(x),\cos(x),\cdot\cdot\cdot,\sin(mx),\cos(mx))^{T}. 根据这些模型,f_{\theta}(x)就可以表示复杂的非线性模型了。

高维输入变量

对于高维的变量\textbf{x}=(x^{(1)},\cdot\cdot\cdot,x^{(d)}), 函数依旧可以扩展成如下模式:

f_{\theta}(\textbf{x})=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(\textbf{x})={\theta}^{T}\phi(\textbf{x}).

对于多维的输入向量\textbf{x},可以用一维的基函数来构造多维基函数的乘法模型加法模型

乘法模型指的是把一维的基函数作为因子,通过使其相乘而获得多维基函数的方法。表达式如下:

f_{\theta}(x)=\sum_{j_{1}=1}^{b^{'}}\cdot\cdot\cdot\sum_{j_{d}=1}^{b^{'}}\theta_{j_{1},\cdot\cdot\cdot,j_{d}}\phi_{j_{1}}(x^{(1)})\cdot\cdot\cdot \phi_{j_{d}}(x^{(d)}).

在上面的式子中,b^{'}是各个维数的参数个数。对于这个模型而言,它的表现力十分丰富,但是不足之处在于所有的参数个数是(b^{'})^{d}, 是一个非常巨大的数字,导致的维数灾难,所以在实际运用中,不主张用这个模型。

加法模型指的是把一维的基函数作为因子,通过相加而活得高维基函数的方法。表达式如下:

f_{\theta}(x)=\sum_{k=1}^{d}\sum_{j=1}^{b^{'}}\theta_{k,j}\phi_{j}(x^{(k)}).

加法模型中所有参数的个数是b^{'}d, 它是一个关于维数d的线性函数,复杂度没有乘法模型大,但是表现力和乘法模型比起来则差很多。

核模型

在线性模型中,多项式或三角函数等基函数的选择都是与训练样本无关的,核模型则与之相反,会在进行基函数构造的时候使用输入样本\{\mathbf{x}_{i}\}_{i=1}^{n}.  在核模型中,会使用核函数

K(\mathbf{x},\mathbf{c})=\exp(-||\mathbf{x}-\mathbf{c}||_{2}^{2}/(2h^{2})), 

其中||\cdot||_{2}指的是欧几里德2-范数,h表示核函数的带宽\mathbf{c}指的是核函数的均值 从核函数的定义可以可以延伸出模型

f_{\theta}(\mathbf{x})=\sum_{j=1}^{n}\theta_{j}\cdot K(\mathbf{x},\mathbf{x}_{j}).

在这个模型中,关于\theta而言仍然满足线性关系。换句话说,对于\theta,\theta^{'}\in\mathbb{R}^{n},f_{\theta+\theta^{'}}(x)=f_{\theta}(x)+f_{\theta^{'}}(x)f_{\alpha\theta}(x)=\alpha f_{\theta}(x). 对于核函数来说,无论输入的是一维变量还是高维变量,核函数都可以容易的进行扩展。

层级模型

对参数来说是非线性的模型,都称为非线性模型。下面要介绍的就是非线性模型中的层级模型,它在很多领域都有应用。假设模型是

f_{\theta}(\mathbf{x})=\sum_{j=1}^{b}\alpha_{j}\cdot\phi(\mathbf{x};\mathbf{\beta}_{j}).

上式中,\phi(\mathbf{x};\mathbf{\beta})是关于参数向量\mathbf{\beta}的基函数,层级模型是基于参数向量\mathbf{\alpha}=(\alpha_{1},\cdot\cdot\cdot,\alpha_{b})^{T}的线性形式。同时也包含参数向量\{\beta_{j}\}_{j=1}^{b}, 所以层级模型是基于参数向量\mathbf{\theta}=(\mathbf{\alpha}^{T},\mathbf{\beta}_{1}^{T},\cdot\cdot\cdot,\mathbf{\beta}_{b}^{T})^{T}的非线性形式。 基函数通常采用S型函数

\phi(\mathbf{x};\beta)=1/(1+\exp(-\mathbf{x}^{T}\omega-\gamma)), 其中\beta=(\omega^{T},\gamma)^{T}

或者高斯函数

\phi(\mathbf{x};\beta)=\exp(-||\mathbf{x}-\mathbf{c}||_{2}^{2}/(2h^{2})), 其中\beta=(\mathbf{c}^{T},h)^{T}.

其中S函数模仿的是人类脑细胞的输入输出函数,因此使用S函数的层级模型也被称为人工神经网络模型

针对像人工神经网络这样的层级模型,采用贝叶斯学习的方法是不错的选择。人工神经网络也以学习过程艰难异常而著称。

点击率(CTR)融入物品相似度

假设物品A与其余三个物品1,2,3的相似度分别是S_{A1}, S_{A2}, S_{A3}.物品1,2,3的点击率(click through rate)分别是CTR(1), CTR(2), CTR(3). 此刻如果物品3的点击率过低,那么需要把第3个物品与物品A的相似度降低,使得第4个物品与A的相似度S_{A4}>S_{A3},从而使得第4个物品能够取代第3个物品。

定义物品A与物品1,2,3的相似度如下:

S_{Aj}^{'}(x)=\frac{S_{Aj}\cdot(x+CTR(j))}{x+(\sum_{k=1}^{3}S_{Ak}\cdot CTR(k))/(\sum_{k=1}^{3}S_{Ak})} \text{ for all }1\leq j\leq 3.

其中x\geq 0是待定的系数。下面就来研究新的相似度满足的性质。

性质1. 相似度的总和没有变化。i.e. \sum_{j=1}^{3}S_{Aj}^{'}(x)=\sum_{j=1}^{3}S_{Aj}对任何的实数x\geq 0都成立。

性质2. 如果CTR(1)=\max_{1\leq k\leq 3}CTR(k), i.e. 第1个物品的点击率最高,那么

(i) S_{A1}^{'}(x)\geq S_{A1}对于任何x\geq 0都成立。

(ii) S_{A1}^{'}(x)对于x是非增函数,i.e. 导数DS_{A1}^{'}(x)\leq 0.

(iii) \lim_{x\rightarrow \infty}S_{A1}^{'}(x)=S_{A1}.换句话说,随着x的增大,S_{A1}^{'}(x)是递减趋向于原始的相似度S_{A1}.

性质3. 如果第3个物品的点击率最低,i.e. CTR(3)=\min_{1\leq k\leq 3} CTR(k), 那么

(i) S_{A3}^{'}(x)\leq S_{A3}对于任何x\geq 0都成立。

(ii) S_{A3}^{'}(x)对于x是非减函数,i.e. 导数DS_{A3}^{'}(x)\geq 0.

(iii) \lim_{x\rightarrow \infty}S_{A3}^{'}(x)=S_{A3}.换句话说,随着x的增大,S_{A3}^{'}(x)逐渐增大趋向于原始的相似度S_{A3}.

(iv) 特别的,如果CTR(3)=0,那么S_{A3}^{'}(0)=0, 通过选择合适的x_{0}\geq 0, 可以使得S_{A3}^{'}(x_{0})<S_{A4}.在这里的S_{A4}指的是物品A与第4个物品的相似度。

物质扩散模型

引言

在推荐系统中,常常用二部图来表示用户和物品的关系:把用户(Users)看成一类点,把物品(Objects)看成另一类点。如果用户购买了某种物品,那么用户和物品之间就存在一条连线,也就是一条边。如果用户没有购买某种物品,那么用户和物品之间就没有连线。但是用户和用户之间,物品和物品之间是不存在连线的。换句话说就是同一类点之间是不存在连线的。这样的图结构就叫做二部图。电子商务中间的物品推荐,可以看成是二部图的边的挖掘问题。扩散过程可以用来寻找二部图中两个节点的关联强度。经典的扩散过程分成两类:一种叫做物质扩散(Probabilistic Spreading),它满足能量守恒定律;另一种叫做热传导(Heat Spreading),一般由一个或多个热源(物品)驱动,不一定满足能量守恒定律。

物质扩散(Probabilistic Spreading)算法流程

probabilistic spreading

如图所示,用黄色的点来表示用户,用红色的点表示物品。用户有三位,物品有四个。第一个用户和第一个物品有连线表示第一个用户购买了第一个物品,而与第二个物品没有连线表示第一个用户没有购买第二个物品。根据图像(a)所示,第一个物品和第三个物品有能量1,第二个物品和第四个物品有能量0.对于物质扩散过程,第一个物品需要把自己的能量1平均分配给购买过它的用户一和用户二。第三个物品也需要把自己的能量1平均分配给购买过它的用户一和用户三。用户的能量就是所有用物品得到的能量的总和。正如图像(b)所示,第一个用户此时具有能量1,第二个和第三个用户都具有能量1/2.接下来,每个用户再把自身的能量平均分配给所有购买过的物品,物品的能量则是从所有用户得到的能量的总和。所以第一个物品的能量就是第一个用户的能量乘以0.5加上第二个用户的能量乘以1/3,所得的能量则是2/3.其他物品的能量用类似的方法计算。

物质扩散(Probabilistic Spreading)数学模型

假设有m个用户(Users)和n个物品(Objects),可以构造矩阵A_{m\times n}, 如果a_{ij}=1,那么表示用户i购买了物品j;如果a_{ij}=0, 那么表示用户i没有购买物品j。用(c_{1},\cdot\cdot\cdot, c_{n})来表示物品1到物品n的能量。用k(U_{\alpha})=\sum_{j=1}^{n}a_{\alpha j}表示用户\alpha的度,也就是该用户购买的物品数量。用k(O_{j})=\sum_{i=1}^{m}a_{ij}表示物品j的度,也就是该物品被多少个用户购买过。根据物质扩散的算法描述,第一步需要计算出用户从物品那里得到的能量,此时用户i得到的能量用b_{i}表示,那么

b_{i}=\sum_{\ell=1}^{n} a_{i\ell}\cdot c_{\ell}/k(O_{\ell}) \text{ for all } 1\leq i\leq m.

后面需要通过用户的能量来更新物品的能量,假设物品j的新能量用c_{j}^{'}表示,那么

c_{j}^{'}=\sum_{i=1}^{m}a_{ij}\cdot b_{i}/ k(U_{i}) \text{ for all } 1\leq j \leq n.

b_{i}的公式带入上面可以得到对于1\leq j\leq n,我们有

c_{j}^{'}=\sum_{\ell=1}^{n}\left(\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}\right)\cdot c_{\ell}=\sum_{\ell=1}^{n}w_{j\ell}^{P}\cdot c_{\ell}.

在这里对于1\leq j\leq n, 1\leq \ell \leq n,

w_{j\ell}^{P}=\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}.

假设n\times n矩阵W^{P}=(w_{j\ell}^{P}), 列向量\vec{C}=(c_{1},\cdot\cdot\cdot,c_{n})^{T}\vec{C^{'}}=(c_{1}^{'},\cdot\cdot\cdot,c_{n}^{'})^{T},那么\vec{C^{'}}=W^{P}\vec{C}.

性质1. 矩阵W^{P}每列的和都是1,i.e. \sum_{j=1}^{n}w_{j\ell}^{P}=1对于所有的1\leq \ell \leq n都成立。

证明. \sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{j=1}^{n}\sum_{i=1}^{m}\frac{1}{k(O_{\ell})}\cdot\frac{a_{ij}a_{i\ell}}{k(U_{i})}=\sum_{i=1}^{m}\frac{a_{i\ell}}{k(O_{\ell})}=1.

性质2. \frac{w_{j\ell}^{P}}{k(O_{j})}=\frac{w_{\ell j}^{P}}{k(O_{\ell})}对于所有的1\leq j,\ell\leq n都成立。换言之,矩阵W^{P}不一定是对称矩阵,只有在所有物品的度都完全一致的情况下才是对称矩阵。

证明. 根据w_{j\ell}^{P}w_{\ell j}^{P}的定义可以得到结论。

性质3. 矩阵W^{P}对角线上的元素是该列的最大值。i.e. w_{jj}^{P}\geq w_{\ell j}^{P}对于所有的1\leq j,\ell\leq n都成立。

证明. 根据矩阵A的定义,对于所有的1\leq j,\ell\leq n,可以得到

w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}\geq\frac{1}{k(O_{j})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}=w_{\ell j}^{P}.

性质4. 能量守恒定律:\sum_{j=1}^{n}c_{j}^{'}=\sum_{\ell=1}^{n}c_{\ell}.

证明. 根据前面的性质,已经知道W^{P}矩阵每一列的和都是1,i.e. \sum_{j=1}^{n}w_{j\ell}^{P}=1. 可以直接计算得到:\sum_{j=1}^{n}c_{j}^{'}=\sum_{j=1}^{n}\sum_{\ell=1}^{m}w_{j\ell}^{P}c_{\ell}=\sum_{\ell=1}^{n}c_{\ell}\cdot\sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{\ell=1}^{m}c_{\ell}.

性质5. 如果物品O_{j}的用户都是物品O_{\ell}的用户,换句话说,如果a_{ij}=1, 则有a_{i\ell}=1.那么w_{jj}^{P}=w_{\ell j}^{P}对于所有的1\leq \ell \leq n都成立。反之,如果w_{jj}^{P}=w_{\ell j}^{P},那么物品O_{j}的用户都是物品O_{\ell}的用户。

证明. 根据w_{j\ell}^{P}的定义,可以得到

w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{\{1\leq i\leq m, a_{ij}=1\}}\frac{1}{k(U_{i})},

w_{\ell j}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{i\ell}a_{ij}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{1\leq i\leq m, a_{ij}=1}\frac{a_{i\ell}}{k(U_{i})}.

根据条件,如果a_{ij}=1,则有a_{i\ell}=1,那么上面两个式子相等。i.e. w_{jj}^{P}=w_{\ell j}^{P}对于所有的1\leq \ell \leq n都成立。

根据上面性质,可以定义变量

I_{j}=\sum_{\ell=1}^{n}(w_{\ell j}^{P}/w_{jj}^{P})^{2},

其中w_{\ell j}^{P}/w_{jj}^{P}可以看成物品O_{j}与物品O_{j}的独立程度。如果w_{\ell j}^{P}/w_{jj}^{P}=1,那么说明物品O_{j}的用户都是物品O_{\ell}的用户。如果w_{\ell j}^{P}/w_{jj}^{P}=0,那么说明物品O_{j}的用户与物品O_{\ell}的用户则没有交集。换言之,物品O_{j}与物品O_{\ell}则相对独立。根据这个性质,如果I_{j}越小,那么物品O_{j}与其他物品就相对独立。

性质6. 1\leq I_{j}\leq n对于所有的1\leq j\leq n都是成立的。

证明. 根据以上性质可以得到w_{\ell j}^{P}\leq w_{jj}^{P}对于1\leq \ell \leq n都成立,并且I_{j}\geq (w_{jj}^{P}/w_{jj}^{P})^{2}=1,所以上面性质成立。

基于物质扩散算法的用户相似度

回顾一下基于用户的协同过滤算法:用户U_{\alpha}, U_{\beta}的相似度是

S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\min\{k(U_{\alpha}),k(U_{\beta})\}

或者使用余弦表达式

S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\sqrt{k(U_{\alpha})\cdot k(U_{\beta})}.

如果用户U_{i}并没有选择物品O_{j},那么预测分数则是

v_{ij}=(\sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}\cdot a_{j\ell}) / \sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}.

这里的求和指的把除了用户i的其他用户做相似度的加权,看用户U_{\ell}是否购买了物品O_{j}.然后对于任意的用户和物品组成的对(i,j), 只要a_{ij}=0(意思是用户U_{i}并没有购买过物品O_{j}),根据预测分数v_{ij}从大到小对1\leq j\leq n排序,推荐v_{ij}值大的物品给用户U_{i}即可。以上就是基于用户的协同过滤算法。

下面来介绍基于物质扩散方法的算法。与上面的方法类似,第一步就是定义用户相似度S_{\alpha \beta}^{P}如下:

S_{\alpha \beta}^{P}=\frac{1}{k(U_{\beta})}\cdot \sum_{j=1}^{n}\frac{a_{\alpha j}\cdot a_{\beta j}}{k(O_{j})}.

上面定义表示物品O_{j}购买的人越多,用户的相似度S_{\alpha \beta}^{P}就会减少。原因就是比方说像新华字典这种购买的人非常多的物品,并不能说明大多数人都是相似的,反而是购买数学分析这种物品的人相似性比较大。也就是说物品的热门程度k(O_{j})对计算用户相似度的时候有抑制作用。此时的评分系统则是:如果用户U_{\alpha}之前没有购买物品O_{i},那么其预测分数则是

v_{\alpha i}=(\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}\cdot a_{\beta i})/\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}

对于物质扩散的算法,可以用以下简单方法进行推广。增加参数d>0,定义用户U_{\alpha}和用户U_{\beta}的相似度S_{\alpha \beta}^{P}(d)如下:

S_{\alpha \beta}^{P}(d)=\frac{1}{k(U_{\beta})}\cdot \sum_{j=1}^{n}\frac{a_{\alpha j}\cdot a_{\beta j}}{(k(O_{j}))^{d}}.

d>1时,减弱了热门物品对用户相似度的影响;当d\in (0,1)时,增加了热门物品对用户相似度的影响。某篇论文显示基于某些数据,d=1.9是最佳的参数。

Xcode 和 OpenCv 入门

OpenCv 中文网站

http://wiki.opencv.org.cn/index.php/%E9%A6%96%E9%A1%B5

安装Xcode和OpenCv

Bear實驗室: 在Xcode上使用OpenCV

在Xcode使用openCV – – 博客频道 – CSDN.NET

Mac OS X 安装 OpenCV2.4.3【详述】 – china_lzn的专栏 – 博客频道 – CSDN.NET

[筆記] OS X Mavericks for OpenCV 編譯失敗 – TakoBear