coursera机器学习笔记

线性回归

LMS梯度下降法(基于最小均方)

时间复杂度：$O(kn^2)$
梯度下降法指的是参数（权重）同时更新，而不是先更新$\theta_0$再更新$\theta_1$

正确：

$$temp0:=\theta_0-\alpha\frac{\partial}{\partial \theta_0}J(\theta_0,\theta_1)$$ $$temp1:=\theta_1-\alpha\frac{\partial}{\partial \theta_1}J(\theta_0,\theta_1)$$ $$\theta_0:=temp0$$ $$\theta_1:=temp1​$$

错误：

$$temp0:=\theta_0-\alpha\frac{\partial}{\partial \theta_0}J(\theta_0,\theta_1)$$ $$\theta_0:=temp0$$ $$temp1:=\theta_1-\alpha\frac{\partial}{\partial \theta_1}J(\theta_0,\theta_1)$$ $$\theta_1:=temp1$$

批量梯度下降法(Batch Gradient Descent)

再推导：
$\frac{\partial}{\partial \theta_j}J(\theta) = \frac{\partial}{\partial \theta_j}\frac{1}{2}(h_\theta(x)-y)^2$
$=2·\frac{1}{2}(h_\theta(x)-y)·\frac{\partial}{\partial \theta_j}(h_\theta(x)-y)$
$=(h_\theta(x)-y)·\frac{\partial}{\partial \theta_j}(\sum_{i=0}^n\theta_ix_i-y)$
$=(h_\theta(x)-y)x_j$

二元

$repeat\{$
$\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})$
$\theta_1:=\theta_1-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x^{(i)}$
$\}$

多元

$repeat\{$
$\theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$
$\}$

随机梯度下降法(Stochastic Gradient Descent)

效率较低，常用于在线学习
$Loop\{$
$\space \space for\space i=1\space to\space m,\{$
$\space \space \space \space \theta_j := \theta_j+\alpha(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$
$\space \space \}$
$\}$

计算$J(\theta) = \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2$不太现实，所以一般判断是否收敛有两种方式：

1. 在使用$(x^{(i)},y^{(i)})$训练之前，计算$\frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2$，训练之后，再重新计算该值
2. 每1000次迭代或者2000次迭代后，计算总的cost值

随机梯度下降法会进入局部最优值，要进入全局最优值，可以缓慢减少学习速率$\alpha$，例如：

$$\alpha = \frac{const1}{iterationNumber+const2}$$

小批量梯度下降法(Mini-Batch Gradient Descent)

每次选取b个（少量，比如10个）进行梯度下降法。

特征缩放和均值化

当特征之间的数值范围比较接近时，梯度下降法能够更有效地工作。
特征缩放，将变量值除以（最大值-最小值）。
另外一个，均值化

$$x_i=\frac{x_i-u_i}{s_i}$$

$s_i$一般是最大值减最小值或者标准差。

选择学习效率

根据迭代次数对代价函数进行画图

最好的是第一个，称之为收敛；
第二个为学习效率较小的状态，原因是多次迭代仍然下降幅度较大；
第三个为学校效率较大的状态，原因是如下图，逐次上升。

多项式回归

例如拟合$h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_1^2+\theta_3x_1^3$
造出$x_2=x_1^2$和$x_3=x_1^3$
但这种情况需要很注意归一化问题。

正规方程Normal Equation

特征维数比较少时使用，不需要归一化，不需要迭代，不需要选择学习效率。

$$\begin{align*} \nabla_\theta J(\theta)&=\nabla_\theta \frac{1}{2}(X\theta-\vec y)^T(X\theta - \vec y) \\ &=\frac{1}{2}\nabla_\theta(\theta^TX^TX\theta-\theta^TX^T\vec y- \vec y^TX\theta + \vec y^T \vec y) \\ &=\frac{1}{2}\nabla_\theta tr(\theta^TX^TX\theta - \theta^TX^T \vec y- \vec y^TX\theta + \vec y^T \vec y) \\ &=\frac{1}{2}\nabla_\theta(tr\theta^TX^TX\theta-2tr \vec y^T X\theta) \\ &=\frac{1}{2}(X^TX\theta + X^TX\theta - 2X^T \vec y) \\ &=X^TX\theta - X^T \vec y \end{align*}$$ $$X^TX\theta = X^T \vec y$$ $$\theta = (X^TX)^{-1}X^Ty$$

时间复杂度：$O(n^3)$

不适用情况

一般时$X^TX$无法求逆，原因有两个：

1. 大量重复多余的特征，例如之间线性相关；
2. 过多的特征$m \leq n$。

局部线性回归

用预测点周围的点计算线性回归，给训练集的点赋予权重进行计算。
$J(\theta)=\sum_i w^{(i)}(y^{(i)}-\theta^Tx^{(i)})^2$
$w^{(i)}=exp(-\frac{(x^{(i)}-x)^2}{2\tau^2})$
一个标准取法是上述。

证明最小二乘法

$y^{(i)}=\theta^Tx^{(i)}+\epsilon^{(i)}$
$\epsilon是误差，遵循高斯分布$
$p(\epsilon^{(i)})=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(\epsilon^{(i)})^2}{2\sigma^2})$
$p(y^{(i)}|x^{(i)};\theta)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})$
$likelihood \space function:$
$L(\theta)=L(\theta;X,\vec y)=p(\vec y|X;\theta)$

$$\begin{align*} L(\theta)&=\prod_{i=1}^mp(y^{(i)}|x^{(i)};\theta) \\ &=\prod_{i=1}^m\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2}) \end{align*}$$

$log \space likelihood l(\theta):$

$$\begin{align*} l(\theta) &= log\space L(\theta) \\ &=log\prod_{i=1}^m\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2}) \\ &=\sum_{i=1}^mlog\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2}) \\ &=m \space log\frac{1}{\sqrt{2\pi}\sigma}-\frac{1}{\sigma^2}·\frac{1}{2}\sum_{i=1}^m(y^{(i)}-\theta^Tx^{(i)})^2 \end{align*}$$

最大化l$(\theta)$，即最小化$\frac{1}{2}\sum_{i=1}^m(y^{(i)}-\theta^Tx^{(i)})^2$

Logistic回归

Sigmoid函数/Logistic函数

$$g(z)=\frac{1}{1+e^{-z}}$$

Logistic回归

Logistic回归，因为$0 \leq h_\theta \leq 1$，使用Logistic函数，所以才叫Logistic回归，但一般用来分类。

$$h_\theta(x)=g(\theta^Tx)$$

假设：
$P(y=1|x;\theta)=h_\theta(x)$
$P(y=0|x;\theta)=1-h_\theta(x)$
$p(y|x;\theta)=(h_\theta(x))^y(1-h_\theta(x))^{1-y}$

$$\begin{align*} L(\theta)&=p(\vec y|X;\theta) \\ &=\prod_{i=1}^mp(y^{(i)}|x^{(i)};\theta) \\ &=\prod_{i=1}^m(h_\theta(x^{(i)}))^{y^{(i)}}(1-h_\theta(x^{(i)}))^{1-y^{(i)}} \end{align*}$$ $$\begin{align*} -l(\theta)&=-log \space L(\theta) \\ &=-\sum_{i=1}^m y^{(i)}log \space h(x^{(i)})+(1-y^{(i)})log(1-h(x^{(i)}) \end{align*}$$

求导：

$$\begin{align*} \frac{\partial}{\partial \theta_j}-l(\theta) &= -(y\frac{1}{g(\theta^Tx)}-(1-y)\frac{1}{1-g(\theta^Tx)})\frac{\partial}{\partial \theta_j}g(\theta^Tx) \\ &= -(y\frac{1}{g(\theta^Tx)}-(1-y)\frac{1}{1-g(\theta^Tx)})g(\theta^Tx)(1-g(\theta^Tx))\frac{\partial}{\partial \theta_j}\theta^Tx \\ &=-(y(1-g(\theta^Tx))-(1-y)g(\theta^Tx))x_j \\ &=-(y-h_\theta(x))x_j \end{align*}$$

所以：
$\theta_j:=\theta_j-\alpha[-(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}]​$

决策边界

分开两类的超平面

cost function

分类之后，需要计算cost function，直接用线性回归的cost function，无法计算，因为不是凸函数。采用新的cost function。
$\space$
$J(\theta)=\frac{1}{m}\sum_{i=1}^mCost(h_\theta(x^{(i)}, y)$
$\space$
$Cost(h_\theta(x^{(i)}, y) = -log(h_\theta(x))\space if\space y=1$

$Cost(h_\theta(x^{(i)}, y) = -log(1-h_\theta(x))\space if\space y=0$

$Cost(h_\theta(x^{(i)}, y) = -ylog(h_\theta(x))-(1-y)log(1-h_\theta(x))$
$\space$
$J(\theta)=-\frac{1}{m}\sum_{i=1}^m[-y^{(i)}log(h_\theta(x^{(i)}))-(1-y^{(i)})log(1-h_\theta(x^{(i)}))]$
$向量形式：$
$h=g(X\theta)$
$J(\theta)=\frac{1}{m}·(-y^Tlog(h)-(1-y)^Tlog(1-h))$
$更新公式：$
$\theta_j:=\theta_j-\frac{\alpha}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$

更优的优化算法

• 共轭梯度法
• 牛顿法(二阶)

$\theta:=\theta-\frac{f(\theta)}{f’(\theta)}$
$目的是让l(\theta)最小值，即l’(\theta)=0$
$\theta:=\theta-\frac{l’(\theta)}{l’’(\theta)}$
$向量形式为：$
$\theta:=\theta-H^{-1} \nabla_\theta l(\theta)$
$其中H_{ij}=\frac{\partial^2l(\theta)}{\partial \theta_i \partial \theta_j}$

• 拟牛顿法

多分类

一对多（One-vs-all）

感知器学习算法Perceptron Learning Algorithm

$g(z)=1,if \space z \ge 0$
$g(z)=0, if \space z < 0$
$let \space h_\theta(x) = g(\theta^Tx)$
$\theta_j:=\theta_j+\alpha(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$

过拟合(overfit)

欠拟合(underfit) 高偏差
过拟合(overfit) 高方差

防止过拟合

1. 减少特征个数
   减少一些多余的或者贡献较小的特征，可以采用特征选择算法(model selection algorithm)。

2. 正则化
   给$\theta$前加上系数，限制$\theta$的作用。

正则化

当不确定具体需要限制哪些$\theta$的作用时，采用总体的限制，比如范数

$$min_\theta \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2+\lambda\sum_{j=1}^n \theta_j^2$$

梯度下降法

$更新公式：$
$\{$
$\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$
$\theta_j:=\theta_j-\alpha[\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda}{m}\theta_j] \space j \in \{1,2…n\}$
$\}$
$上式可写作：$
$\theta_j:=\theta_j(1-\alpha \frac{\lambda}{m})-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} \space j \in \{1,2…n\}$
可以看作，相比于原本的更新公式，该更新公式每次更新会减小一点$\theta$的值。

Normal Equation

$\theta = (X^TX+ \lambda·L)^{-1}X^Ty$

L为$(n+1)*(n+1)维$。

Logistic回归

$J(\theta) = -\frac{1}{m}\sum_{i=1}^m[y^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2$
$更新公式：$
$\{$
$\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$
$\theta_j:=\theta_j-\alpha[\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda}{m}\theta_j] \space j \in \{1,2…n\}$
$h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}$
$\}$

神经网络

$$\begin{align*} a_1^{(2)} = g(\Theta_{10}^{(1)}x_0 + \Theta_{11}^{(1)}x_1 + \Theta_{12}^{(1)}x_2 + \Theta_{13}^{(1)}x_3) \newline a_2^{(2)} = g(\Theta_{20}^{(1)}x_0 + \Theta_{21}^{(1)}x_1 + \Theta_{22}^{(1)}x_2 + \Theta_{23}^{(1)}x_3) \newline a_3^{(2)} = g(\Theta_{30}^{(1)}x_0 + \Theta_{31}^{(1)}x_1 + \Theta_{32}^{(1)}x_2 + \Theta_{33}^{(1)}x_3) \newline h_\Theta(x) = a_1^{(3)} = g(\Theta_{10}^{(2)}a_0^{(2)} + \Theta_{11}^{(2)}a_1^{(2)} + \Theta_{12}^{(2)}a_2^{(2)} + \Theta_{13}^{(2)}a_3^{(2)}) \newline \end{align*}$$

$s_j表示第j层拥有的神经元数目，所以\Theta^{(j)}的维数s_{j+1}\times(s_j+1)$

$z^{(j)} = \Theta^{(j-1)}a^{(j-1)}$
$a^{(j)} = g(z^{(j)})$

逻辑运算的例子

多分类的例子

cost function

$\begin{gather} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k) + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] + \frac{\lambda}{2m}\sum_{l=1}^{L-1} \sum_{i=1}^{s_l} \sum_{j=1}^{s_{l+1}} ( \Theta_{j,i}^{(l)})^2\end{gather}$
上式为多分类时cost function，$L$为神经网络层数，$K$为分类类数，直接导致最终结果的向量维数，等于最后一层的神经元数。即对每一种类别采用logistic回归时的cost function。

误差反向传播

误差反向传播四个核心公式：

1. $\delta_i^{(L)} = -(y_i-a_i^{(L)})f’(z_i^{(L)})$

2. $\delta_i^{(l)}=(\sum_{j=1}^{n_{l+1}}\delta_j^{(l+1)}w_{ji}^{(l+1)})f’(z_i^{(l)})$

3. $\frac{\partial E}{\partial w_{ij}^{(l)}}=\delta_i^{(l)}a_j^{(l-1)}$

4. $\frac{\partial E}{\partial b_i^{(l)}}=\delta_i^{(l)}$

具体参考coursera深度学习里的推导，主要用的是求导的链式法则。

梯度检验Gradient Checking

$\dfrac{\partial}{\partial\Theta}J(\Theta) \approx \dfrac{J(\Theta + \epsilon) - J(\Theta - \epsilon)}{2\epsilon}$
$\dfrac{\partial}{\partial\Theta_j}J(\Theta) \approx \dfrac{J(\Theta_1, \dots, \Theta_j + \epsilon, \dots, \Theta_n) - J(\Theta_1, \dots, \Theta_j - \epsilon, \dots, \Theta_n)}{2\epsilon}$
将结果与梯度比较，若正确则将梯度检验关闭，因为梯度检验速度很慢

随机初始化Random Initialization

随机初始化是为了打破对称。

Theta1 = rand(1,1) * (2 * INIT_EPSILON) - INIT_EPSILON;

训练步骤

1. 随机初始化权重
2. 向前传播，得到$h_\theta(x^{(i)})$
3. 计算cost function $J(\theta)$
4. 向后传播，计算偏导数
5. 使用梯度检验，之后关闭
6. 使用梯度下降等方法最小化成本函数

建议

1. $训练:测试:验证=6:2:2$
2. $高方差 or 高偏差$

1. 正则化的作用

1. 学习曲线

收集更多数据量对高方差是有作用的。

总结：

1. 收集更多数据量：高方差
2. 尝试更少的特征数：高方差
3. 收集更多的特征：高偏差
4. 增加多项式次数：高偏差
5. 减小$\lambda$：高偏差
6. 增加$\lambda$：高方差

朴素贝叶斯

特征量

如果每个特征需要N个样本，那么对于10个特征将需要N¹⁰个样本，对于包含1000个特征的词汇表将需要N¹⁰⁰⁰个样本。可以看到，所需要的样本数会随着特征数目增大而迅速增长。如果特征之间相互独立，那么样本数就可以从N¹⁰⁰⁰减少到1000×N。

朴素贝叶斯常见模型

1. 高斯模型
   假设这些一个特征的所有属于某个类别的观测值符合高斯分布，目前还没看到例子，不理解

2. 多项式模型
   按照次数作为特征，常用于文本

3. 伯努利模型
   出现/不出现，对应01向量

k-means聚类

步骤

1. 随机初始化k个点
2. 将样本归类到最近的点
3. 计算同个簇的点的均值点，作为新的簇中心点
4. 将23重复，直到样本归类不再发生变化

k的取值

肘部法：最近一次明显下降的点。

PCA降维

步骤

1. 特征均值化
2. 计算协方差矩阵$\Sigma = \frac{1}{m} \sum_{i=1}^n (x^{(i)})(x^{(i)})^T$
3. $[U,S,V]=svd(Sigma);$
4. $Z = U(1:K)’*X;$
5. 重建：$X=U(1:K)*Z$

K的取值

根据贡献率选取：

$$\frac{\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2}{\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2}\leq 0.01$$

贡献率：99%
上式同等于：

$$1-\frac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}} \leq 0.01$$ $$\frac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}} \ge 0.99$$

作用

1. 特征降维，以提高运算速度，减少内存使用；
2. 降至2~3维，以可视化数据；
3. 不可用于改善过拟合。

异常检测

高斯分布检测系统

1. 选取正常样本
2. 计算参数$\mu,\sigma^2$

$$\mu_j=\frac{1}{m}\sum_{i=1}^mx_j^{(i)}$$ $$\sigma_j^2 = \frac{1}{m}\sum_{i=1}^m(x_j^{(i)}-\mu_j)^2$$

1. 来了一个检测样本，计算$p(x)$

$$p(x)=\prod_{j=1}^n p(x_j;\mu_j, \sigma_j^2) = \prod_{j=1}^n \frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})$$

$判断p(x) < \varepsilon$

仍然要分出训练集、测试集和交叉验证集

异常检测 vs 监督学习

异常检测

1. 只有少量的异常样本
2. 许多不同的异常类别
3. 未来可能出现新的异常类别

监督学习

1. 大量的正常和异常样本

特征选择

将样本特征画图，如果不像正态分布，可用多种函数映射成正态分布。

$$log(x)$$ $$\sqrt{x}$$ $$...$$

多元高斯分布检测分布

动机：当出现以下这种异常点，无法检测。

协方差矩阵$\Sigma$

步骤

1. 计算$\mu,\Sigma$

$$\mu = \frac{1}{m}\sum_{i=1}^m x^{(i)}$$ $$\Sigma = \frac{1}{m}\sum_{i=1}^m (x^{(i)}-\mu)(x^{(i)}-\mu)^T$$

1. 计算$p(x)$

$$p(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$$

$判断p(x) < \varepsilon$

当$m >> n$时，才使用多元高斯分布，其他情况使用普通高斯分布。

推荐系统

$n_u = 用户数量$
$n_m = 电影数量$
$r(i,j) = 1 如果用户j给电影i评了分$
$y^{(i,j)} = 用户j给电影i评的分$

基于内容的推荐系统

$对于每个用户j，我们要学习出一个\theta^{(j)}；而对于每部电影i，我们要学习出一个x^{(i)}，则预测评分为(\theta^{(j)})^T(x^{(i)})$
$m^{(j)} = 用户j评分的电影部数$
$优化目标为：$

$$min_{\theta^{(j)}} = \frac{1}{2} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{k=1}^n(\theta_k^{(j)})^2$$ $$min_{\theta^{(1)},...,\theta^{(n_u)}} = \frac{1}{2} \sum_{j=1}^{n_u} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u} \sum_{k=1}^n(\theta_k^{(j)})^2$$

$\space$
$梯度下降法：$

$$\theta_k^{(j)}:=\theta_k^{(j)} - \alpha \sum_{i:r(i,j)=1} ((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)} \space (for \space k =0)$$ $$\theta_k^{(j)}:=\theta_k^{(j)} - \alpha (\sum_{i:r(i,j)=1} ((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)} + \lambda \theta_k^{(j)}) \space (for \space k \neq 0)$$

$基于内容的推荐系统需要事先对每部电影给出x^{(i)}，操作性不够强$

基于协同过滤的推荐系统

$假设每个用户的\theta^{(j)}已给出，则要学习出x^{(i)}$
$优化目标：$

$$min_{x^{(i)}} \frac{1}{2} \sum_{j:r(i,j)=1} (( \theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{k=1}^n (x_k^{(i)})^2$$ $$min_{x^{(1)},...,x^{(n_m)}} \frac{1}{2} \sum_{i=1}^{n_m} \sum_{j:r(i,j)=1} (( \theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{i=1}^{n_m} \sum_{k=1}^n (x_k^{(i)})^2$$

$结合基于内容的推荐系统，我们可以先随机取值\theta，然后学习出x，再学习出\theta……$
$不用那么麻烦的办法，同时训练学习出\theta和x：$

$$J(x^{(1)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)})=\frac{1}{2} \sum_{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_m} \sum_{k=1}^n (x_k^{(i)})^2 + \frac{\lambda}{2} \sum_{j=1}^{n_u} \sum_{k=1}^n (\theta_k^{(j)})^2$$

步骤

1. $随机初始化x和\theta为小的随机值$
2. $使用梯度下降法，最小化J(x^{(1)},…,x^{(n_m)},\theta^{(1)},…,\theta^{(n_u)})$

$$x_k^{(i)}:=x_k^{(i)} - \alpha (\sum_{j:r(i,j)=1} ((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})\theta_k^{(j)}+\lambda x_k^{(i)})$$ $$\theta_k^{(j)}:=\theta_k^{(j)} - \alpha (\sum_{i:r(i,j)=1} ((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})\theta_k^{(i)}+\lambda \theta_k^{(j)})$$

1. $\theta^Tx即为预测评分$

均值化

1. 每行求平均值

1. 矩阵每个值都减去该行的平均值

1. 最后算出来的评分再加上该平均值$(\theta^{(j)})^T(x^{(i)})+\mu_i$

Map-reduce

将样本分开到每个计算机计算，之后再加和。
有将样本加和的步骤都可以采用Map-reduce。