paper note-learnig recommender systems with adaptive regularization_综合

- 简介
- 分解机
  - 模型公式
  - 目标函数
  - 优化算法
- 优化正则化系数
  - 问题描述
  - 梯度计算
  - 算法描述
- 结论

简介

在推荐系统中最常用的模型是分解模型（factorization model），为了防止模型的过拟合，一般需要在损失函数中添加正则项。分解模型在测试集或者实际应用中的表现很大程度上依赖正则项参数（Regularization values的)，而这个参数一般被视为超参数，即在每次实验开始前已经确定的参数。在实验过程中一般是准备多个候选值，分别进行实验，然后选取效果最好的。这样是比较耗时的。

这篇论文提出了一个新的观点，将正则化参数视为一个可以通过学习得到的参数，在学习的过程中自动的调整这个参数，从而避免耗时的调参工作。提出的算法具有以下几个特点：

列表内容将正则化参数集成到模型参数的学习算法中
算法的时间复杂度和梯度下降一样
不在需要手动的调试正则化参数，并且正则化参数的可选范围从有限变成的无限。

分解机

$S$ ：数据集

$\lambda$ ：正则化系数

$\Theta$ ：假设空间

$\theta$ ：模型参数

$y$ ：真实值

$\hat{y}$ ：预测值

$l$ ：损失函数

模型公式

由于SVD++、MF等模型可以视为分解机（Factorization Machine）的特例，所以本文采用的模型为分解机。

\hat{y} (x) = w_{0} + \sum_{l = 1}^{p} w_{l} x_{l} + \sum_{l_{1} = 1}^{p} \sum_{l_{2} > l_{1}}^{p} < v_{l_{1}}, v_{l_{2}} > x_{l_{1}} x_{l_{2}}

$\hat{y}(\textbf{x}) = w_0 + \sum_{l=1}^{p}{w_l x_l}+ \sum_{l_1=1}^{p}\sum_{l_2>l_1}^{p}<\textbf{v}_{l_1},\textbf{v}_{l_2}>x_{l_1}x_{l_2}$
公式（1）的时间复杂度为

O(kn2) O ( k n 2 ) $O(kn^2)$

通过对（1）的变形，可以将其时间复杂度降低到 $O(kn)$

y^(x) = w 0 + \sum l = 1 p w l x l + 1 2 \sum f = 1 k ((\sum l = 1 p v l, f x l) 2 ? \sum l = 1 p v 2 l, f x 2 l)

$\hat{y}(\textbf{x}) = w_0 + \sum_{l=1}^{p}{w_l x_l} + \frac{1}{2}\sum_{f=1}^k((\sum_{l=1}^pv_{l,f}x_l)^2-\sum_{l=1}^pv_{l,f}^2x_l^2)$

目标函数

一般用损失函数来量化预测评分 $\hat{y}$ 和真实值 $y$ 之间的误差，常用的损失函数有一下两种

l^{L S} (y_{1}, y_{2}) := (y_{1} ? y_{2})^{2}

$l^{LS}(y_1,y_2):=(y_1-y_2)^2$

l C (y 1, y 2) : = ? l n σ (y 1 y 2)

$l^C(y_1,y_2):=-ln\sigma(y_1y_2)$
则优化目标函数为

O P T R E G (S, λ) : = a r g m i n Θ (\sum (x, y) \in S l (y^(x | Θ), y) + \sum θ \in Θ λ θ θ 2)

$OPTREG(S,\lambda):=\mathop{argmin}_{\Theta}(\sum_{(\textbf{x},y)\in S}l(\hat{y}(\textbf{x}|\Theta),y) + \sum_{\theta\in \Theta}\lambda_{\theta}\theta^2)$
其中

λθ∈R+ λ θ ∈ R + $\lambda_\theta \in \mathbb{R}_+$ 为对应模型参数的正则系数，本文采用的是

L2 L 2 $L_2$ 正则。实际上，分解机模型的表现很大程度上依赖

λ λ $\lambda$ 的选择。如果

λ λ $\lambda$ 过大，则模型不能很好的拟合训练集，也就是训练效果不明显；如果

λ λ $\lambda$ 过小，则模型在训练集上可能会过拟合，虽然在训练集上的表现很好，但是缺乏泛化能力，即在验证集或者实际应用中的表现很差。

优化算法

对于上述目标函数，通常采用梯度下降（Gradient Descent）进行优化

θ t + 1 = θ t ? α (? ? θ t l (y^(x | Θ), y) + 2 λ θ t)

$\theta^{t+1}=\theta^t-\alpha(\frac{\partial}{\partial\theta^t}l(\hat{y}(\textbf{x}|\Theta), y)+2\lambda\theta^t)$

优化正则化系数

这是本文提出的重要概念，即在训练过程中自适应的优化正则化系数。

问题描述

为了学习正则化参数 $\lambda_{\theta}$ ，首先将数据集分为互斥的两部分： $S_V$ 和 $S_T$ 。在 $S_T$ 上，对于给定的 $\lambda_{\theta}$ ，通过公式（5）来优化模型参数。在 $S_V$ 上，评估模型的效果。我们需要求出 $\lambda^*$ 使目标函数在 $S_V$ 上的误差最小。

λ ? : = a r g m i n λ \in R c + \sum (x, y) \in S V l (y^(x | O P T R E G (S T, λ)), y)

$\lambda^*:=\mathop{argmin}\limits_{\lambda\in \mathbb{R}_+^c}\sum_{(\textbf{x},y)\in S_V} l(\hat{y}(\textbf{x}|OPTREG(S_T,\lambda)),y)$

这是一个嵌套优化问题，最外层是通过在 $S_V$ 上最小化目标函数来求出最优的 $\lambda^*$ 。由公式可以看出，目标函数的最小化与 $\lambda$ 无关，而是取决于 $\hat{y}$ 的计算，由公式（1）可以知道 $\hat{y}$ 的计算仅仅取决于模型参数，也就是当模型参数固定时，有以下的求导关系。

λ ? : = a r g m i n λ \in R c + \sum (x, y) \in S V l (y^(x | Θ), y)

$\lambda^*:=\mathop{argmin}\limits_{\lambda\in \mathbb{R}_+^c}\sum_{(\textbf{x},y)\in S_V} l(\hat{y}(\textbf{x}|\Theta),y)$

? ? λ L (S V, Θ t) = ? ? λ \sum (x, y) \in S V l (y^(x | Θ t), y) = 0

$\frac{\partial}{\partial\lambda}L(S_V,\Theta^t)=\frac{\partial}{\partial\lambda}\sum_{(\textbf{x},y)\in S_V} l(\hat{y}(\textbf{x}|\Theta^t),y) = 0$

也就是说无法通过（8）求出 $\lambda$ ，原因在于，公式（8）中并未显示的出现 $\lambda$ 。

但是在（6）中， $\Theta$ 的更新公式中，显示的出现了 $\lambda$ 。于是可以换个思路，考虑优化问题：求出使 $\Theta$

的下一次更新后在验证集上损失函数最小的 $\lambda$

λ ? : = a r g m i n λ \in R c + \sum (x, y) \in S V l (y^(x | Θ t + 1), y)

$\lambda^*:=\mathop{argmin}\limits_{\lambda\in \mathbb{R}_+^c}\sum_{(\textbf{x},y)\in S_V} l(\hat{y}(\textbf{x}|\Theta^{t+1}),y)$

梯度计算

λ t + 1 = λ t + α ? ? λ l (y^(x | Θ t + 1), y)

$\lambda^{t+1}=\lambda^t + \alpha \frac{\partial}{\partial\lambda}l(\hat{y}(\textbf{x}|\Theta^{t+1}), y)$
对于

lLS l L S $l^{LS}$ :

? ? λ (y^(x | Θ t + 1) ? y) 2 = 2 (y^(x | Θ t + 1) ? y) ? ? λ (y^(x | Θ t + 1)

$\frac{\partial}{\partial\lambda}(\hat{y}(\textbf{x}|\Theta^{t+1}) - y)^2 = 2(\hat{y}(\textbf{x}|\Theta^{t+1}) - y) \frac{\partial}{\partial\lambda}(\hat{y}(\textbf{x}|\Theta^{t+1})$
对于

lC l C $l^C$

? ? λ ? l n σ (y^(x | Θ t + 1) y) = σ (y^(x | Θ t + 1) y ? 1) y ? ? λ (y^(x | Θ t + 1)

$\frac{\partial}{\partial\lambda} - ln\sigma(\hat{y}(\textbf{x}|\Theta^{t+1}) y) = \sigma(\hat{y}(\textbf{x}|\Theta^{t+1})y - 1)y \frac{\partial}{\partial\lambda}(\hat{y}(\textbf{x}|\Theta^{t+1})$

正则化系数一共有 $k+2$ 个，

$\lambda_0(w_0)$ ，

$\lambda_w(w_1,w_2,...,w_p)$ ，

$\lambda_f(\textbf{v}_{*f}), f=1,2,...k$

? ? λ 0 y^(x | Θ t + 1) = ? 2 α w t 0

$\frac{\partial}{\partial\lambda_0}\hat{y}(\textbf{x}|\Theta^{t+1}) = -2\alpha w_0^t$

? ? λ w y^(x | Θ t + 1) = ? 2 α \sum i = 1 p w t i x i

$\frac{\partial}{\partial\lambda_w}\hat{y}(\textbf{x}|\Theta^{t+1}) = -2\alpha \sum_{i=1}^pw_i^tx_i$

? ? λ f y^(x | Θ t + 1) = ? 2 α [\sum i = 1 x i v t + 1 i, f \sum j = 1 x j v t j, f ? \sum j = 1 x 2 j v t + 1 j, f v t j, f]

$\frac{\partial}{\partial\lambda_f}\hat{y}(\textbf{x}|\Theta^{t+1}) = -2\alpha [\sum_{i=1}x_iv_{i,f}^{t+1}\sum_{j=1}x_jv_{j,f}^{t} - \sum_{j=1}x_j^2v^{t+1}_{j,f}v_{j,f}^t]$

算法描述

这里写图片描述

结论

由于正则化系数个数的增加，且其取值空间从有限变为无限，引入了自适应调整正则项系数后的模型效果更好。并且由于省去了调参的过程，更省时间。