吴恩达机器学习 course3 week2 推荐系统和PCA算法

序言

推荐系统在商业上的应用广泛，如在亚马逊、Netflix等网站中为用户推荐商品或电影。推荐系统的经济价值巨大，许多公司的销售由推荐系统驱动。课程以预测电影收视率的应用为例，介绍了推荐系统的基本框架，包括用户和项目（如电影）的评级。推荐系统的目标是预测用户对未评级项目的评分，以便向用户推荐他们可能感兴趣的项目。课程还特别强调了在没有项目特征的情况下，如何让算法工作。

1.1 电影评分预测

我们以“推荐系统”案例–“预测电影评分”

给出下面的数据集，预测用户对于没有看过的电影的评分。进而可以“为你推荐”

注：默认用户对电影的评分为(0,1,2,3,4,5)这6种分数。
问号“?”表示用户并没有看过当前电影，就没有评分。
一般的推荐问题中，将研究对象称为“item”，比如本例中就是“电影”。

数学符号

• $n_u$: 用户的数量
• $n_m$: 电影的数量
• $n$: 电影的特征数量
• $\vec w^{(j)},b^{(j)}$: 第 j 个用户的参数，前者为 1×n的一维向量，后者为一个数
• $W,\vec b$: 所用用户参数，前者为$n_u \times n$维矩阵 ，后者为1×n的一维向量
• $X$: $n_m \times n$ 二维矩阵，所有的电影特征
• $\vec x^{(i)}$: 1×n一维向量，第i个电影的特征
• $r(i,j)$: 二元取值，表示用户 j 对电影 i 是否打分，打分(1)、或者是没打分(0)
• $y^{(i,j)}$: 一个值，用户 j 对电影i的评分
• $m^{(j)}$: 一个值，表示用户 j 已经评分的电影总数

1.2 使用每个特征

因此，让我们来看一下如果我们具有每个项目或每部电影的特征，我们如何开发一个推荐系统

使用“电影特征”计算“用户参数”

$x_1$: 假设表示电影的“浪漫”程度。
$x_2$: 假设表示电影的“打斗激烈”程度
$\vec x^{(i)} = [x_1^{(i)},x_2^{(i)} ]$：表示电影i的特征

假设我们目前完全已知电影的特征。那显然就可以直接使用“线性回归”，假设用户 j 对电影 i 的评分为$\hat y^{(i,j)} = \vec w^{(j)} \vec x^{(i)} + b^{(j)}$ 于是便可最小化代价函数求解用户 j 的 参数 $\vec w^{(j)} , b^{(j)}$。下面给出模型及单个用户的代价函数、全体用户的代价函数：
下面给出模型及单个用户的代价函数、全体用户的代价函数

1. Linear model:
   $$
   \hat{y}^{(i,j)} = \vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)}
   $$

2. Cost function of user ( j ):
   $$
   \min_{\vec{w}^{(j)}, b^{(j)}} J(\vec{w}^{(j)}, b^{(j)}) = \frac{1}{2m^{(j)}} \sum_{i: r(i,j)} (\vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)} - y^{(i,j)})^2 + \frac{\lambda}{2m^{(j)}} \sum_{k=1}^{n} (w_k^{(j)})^2
   $$

3. Cost function of ALL users:
   $$
   \min_{W, \vec{b}} J(W, \vec{b}) = \frac{1}{2} \sum_{j=1}^{n_u} \sum_{i: r(i,j)=1} (\vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)} - y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{j=1}^{n_u} \sum_{k=1}^{n} (w_k^{(j)})^2
   $$

使用“用户参数”计算“电影特征”

那现在假设我们不知道电影特征，但是完全已知用户参数。显然根据上一段给出的“线性回归”模型，我们也可以使用“用户参数”来计算“电影特征”。仿照上一段，模型和代价函数如下(代价函数误差项的不同仅在求和符号上)：

1. Linear Model:
   $$
   \hat{y}^{(i,j)} = \vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)}
   $$

2. Cost function of movie ( i ):
   $$
   \min_{\vec{x}^{(i)}} J(\vec{x}^{(i)}) = \frac{1}{2} \sum_{j: r(i,j)} (\vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)} - y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{k=1}^{n} (x_k^{(i)})^2
   $$

3. Cost function of ALL movies:
   $$
   \min_X J(X) = \frac{1}{2} \sum_{i=1}^{n_m} \sum_{j: r(i,j)=1} (\vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)} - y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{j=1}^{n_m} \sum_{k=1}^{n} (x_k^{(i)})^2
   $$

1.3 协同过滤算法

将上面两种情况综合起来，根据已知的的用户评分，来协同求解未知的电影特征、用户参数，就是“**协同过滤算法(Collaborative filtering)**”。注意到，“所有用户的代价函数”、“所有电影的代价函数”中的“平方误差项”完全相同，都使用到了所有用户已经打分的数据，于是便可以考虑将两者合并，再加上所有的正则项，即可得到完整的代价函数:

梯度下降：

$$ \begin{cases} i = 1, 2, \ldots, n_m, \ j = 1, 2, \ldots, n_u, \ k = 1, 2, \ldots, n. \end{cases} $$ 梯度下降 (Gradient Descent) 重复直到收敛：

$$
\begin{cases} w_k^{(j)} = w_k^{(j)} - \alpha \frac{\partial}{\partial w_k^{(j)}} J(W, \vec{b}, X), \ b^{(j)} = b^{(j)} - \alpha \frac{\partial}{\partial b^{(j)}} J(W, \vec{b}, X), \ x_k^{(i)} = x_k^{(i)} - \alpha \frac{\partial}{\partial x_k^{(i)}} J(W, \vec{b}, X). \end{cases}
$$

1.4 二进制标签

事实上，很多“推荐算法”或者说是“协同过滤算法”都只使用“二进制标签”，来表示用户喜欢(1)、不喜欢(0)，而不是可以给出连续取值的电影评分。比如下面给出了“二进制标签”的可能含义，包括但不限于短视频平台、社交软件、购物平台、广告推送等：

• 用户是否观看30s以上。或者说是完播率。
• 用户是否点赞或收藏。
• 用户是否购买了某种商品。
• 用户是否点击。

于是对于这种情况，就需要将“线性回归模型”转换成“逻辑回归模型”，代价函数中的“平方误差”也要转换成“二元交叉熵”：
$$
\text{Logistic model:} \quad \hat{y}^{(i,j)} = f_{\vec{w}, \vec{b}, X}(\vec{x}^{(i)}) = g(\vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)}) = \frac{1}{1 + e^{-(\vec{w}^{(j)} \vec{x}^{(i)} + b^{(j)})}}
$$

$$
\text{Cost function: } \min_{W, \vec{b}, X} J(W, \vec{b}, X) = \sum_{(i,j): r(i,j)=1}^{m} \left[ -y^{(i,j)} \log(\hat{y}^{(i,j)}) - (1 - y^{(i,j)}) \log(1 - \hat{y}^{(i,j)}) \right]
$$
$$
+\frac{\lambda}{2} \sum_{j=1}^{n_u} \sum_{k=1}^{n} (w_k^{(j)})^2 + \frac{\lambda}{2} \sum_{j=1}^{n_m} \sum_{k=1}^{n} (x_k^{(i)})^2,
$$

1.5 均值归一化

上面已经介绍“协同过滤算法”的线性回归形式和逻辑回归形式，但在执行这个算法之前，首先还需要进行数据预处理——“均值归一化(mean normalization)”，会使算法的效果更好。这是因为新用户没有对任何电影做出评分，于是对于“代价函数”中的“误差项”不起作用，再加上“正则项”会进行减小用户参数的影响，于是新用户的参数$\vec w^{(j)}$全为0(一般初始化$b^{(j)}$为0)，此时对于任何电影的评分也就是全是0。也就是说：

1. 不进行“均值归一化”，新用户的默认评分全是0(全都不喜欢)，这就没法推荐了。
2. “均值归一化”后，新用户的默认评分是当前电影的平均评分。起码也可以默认推荐平均分较高的电影。

总结：“均值归一化”使得推荐算法对于新用户、很少评价电影的用户的预测更加准确。

下面是“均值归一化”的具体步骤：

1. 对于每一个电影，计算出所给出已有评分的平均分： $ \mu_i = \text{mean}_{j: r(i,j)=1}(y^{(i,j)}) $
2. 将所有评分进行“均值归一化”： $ \hat{y}^{(i,j)} = y^{(i,j)} - \mu_i $
3. 正常进行“协同过滤算法”，预测出新的评分： $ f_{W, \bar{b}, X}(x^{(i)}) $
4. 将均值加回，即为最后结果： $ \hat{y}^{(i,j)} = f_{W, \bar{b}, X}(x^{(i)}) + \mu_i $

1.6 协同过滤的TensorFlow实现

本节介绍使用TensorFlow实现“协同过滤算法”的大致框架。由于“协同过滤算法”并没有封装好的函数，所以代价函数的计算过程需要我们手动定义，但是求解偏导则可以交给TensotFlow内置的“自动微分”机制完成。具体来说，主要使用 tensorflow.GradientTape()来定义代价函数的计算过程，并使用其 .gradient() 方法计算偏导来完成迭代更新。下面给出两个代码示例

注：“Auto-diff” 也称为“Auto-Grad”，其他机器学习包也支持，如“PyTorch”。

#####################【示例1】#####################
# 使用梯度下降法迭代更新参数
# 代价函数：J=(wx-y)**2
##################################################
# 定义初始参数
w = tf.Variable(3.0) # 待优化参数，并给出初始值
x = 1.0              # 特征值
y = 1.0              # 目标值
alpha = 0.01         # 学习率
iterations = 30      # 迭代次数
# 迭代寻找代价函数最小值
for iter in range (iterations) :
    # 定义计算代价函数的步骤，方便后续的自动微分(auto-diff)。
    with tf.GradientTape() as tape:
        fwb = w*x
        costJ = (fwb - y)**2
    # 自动微分计算参数的偏导
    [dJdw] = tape.gradient(costJ, [w])
    # 对参数进行迭代更新
    w.assign_add(-alpha * dJdw)

#####################【示例2】#####################
# 使用Adam算法迭代更新参数
# 代价函数：自定义函数 myCostCal()，参考2.1节
# 给出参数：
#   X：二维矩阵，电影特征，每一行表示一个电影
#   W：二维矩阵，用户参数，每一行表示一个用户
#   b：一维向量，用户参数，每一个表示一个用户
#   Ynorm：二维矩阵，“均值归一化”后的打分
#   R：二维矩阵，表示哪些打分是有效的
#   lambda：正则化参数
##################################################
optimizer = keras.optimizers.Adam(learning_rate=1e-1)
iterations = 200
for iter in range (iterations) :
    # 定义如何计算代价函数
    with tf.GradientTape() as tape:
        # 自定义函数：使用前向传播写出代价函数的计算步骤
        cost_value = myCostCal(X, W, b，Ynorm, R, num_users, num_movies, lambda)
    # 计算代价函数对于所有待求参数的偏导
    grads = tape.gradient( cost_value, [X,W,b] )
    # 使用Adam函数中的方法更新参数
    optimizer.apply_gradients( zip(grads, [X,w,b]) )

1.7 寻找相关的特征

实际当我们浏览电影网站时，可能会有很多“相似产品”推荐，那如何评判两个电影(item)很相似呢？使用特征之间的距离平方进行衡量。比如判断 电影 p 和 电影 i 的相似程度就可以使用：

$$
\left| \vec{x}^{(p)} - \vec{x}^{(i)} \right|^2 = \sum_{k=1}^{n} \left( x_k^{(p)} - x_k^{(i)} \right)^2
$$
这同时将有助于我们提前筛选大量的数据。并且，如果我们直接推荐和用户评价的高分电影“相似”的电影，就成了“无监督学习”。

最后是 “协同过滤算法”的缺点：

• 不擅长解决“冷启动(cold start)”问题。当有一个新电影或者新用户时，“协同过滤算法”的预测值就不是很准确。虽然再均值归一化给出了一定的解决思路，但是还有更好的方法。

• 无法使用“用户”或“项目”的附加信息。前面已经强调，我们并不能提前知道“用户参数”和“电影特征”的数量和含义，所以上述“协同过滤算法”类似于“盲算”。但实际上，我们可以知道电影的一些信息，比如类型、演员、出品方、预算等；也可以知道一些用户的信息，比如性别、年龄、地址、类型偏好、浏览器等。如何将这些“附加信息”利用到模型中也是需要考虑的问题。

之后介绍的“基于内容过滤”将解决上述问题。

---

2.1 基于内容过滤

基于内容过滤和协同过滤的对比：

• 协同过滤(Collaborative filtering)：根据和你相似的同类型用户的评分，也就是推荐其他人评分高的。

• 基于内容过滤(Content-based filtering)：根据用户特征和项目特征的匹配程度，也就是直接找和用户特征相似的。

注：“项目(item)”指的是“电影”这样的待推荐的产品。

“基于内容过滤(Content-based filtering)”算法是一种稳定应用在很多商业应用的推荐算法。

2.2 基于内容过滤的深度学习方法

用户原始特征：$ \vec{x}_u^{(j)} $（第 j 个用户的原始特征）

• 年龄
• 性别：比如一段长度的独热码
• 国籍：比如长度为200的独热码
• 已观看影片：比如选取1000个典型电影，看看当前用户是否观看
• 平均打分
• ……（可能有1500种特征）

电影原始特征：$\vec{x}_m^{(i)} $（第 i 个电影的原始特征）

• 发行年份
• 电影类型
• 电影评论
• 电影平均评分
• ……（可能有50种特征）

假设我们现在有一些用户、电影的原始特征（如上所示）。为了衡量“用户特征”和“电影特征”的匹配程度，我们可能使用“向量点积”。但是“向量点积”的维度需要相同，于是我们需要从 用户原始特征$ \vec{x}_u^{(j)} $推导出 用户特征 $\vec v_u^{(j)}$、从 电影原始特征$\vec{x}_m^{(i)} $推导出 电影特征 $\vec v_m^{(i)}$ ,那么用户特征 j 和电影特征 i 的匹配程度 : $\vec v_u^{(j)} \cdot \vec v_m^{(i)}$ , 那如何从长度不同的 $ \vec{x}_u^{(j)} 、 \vec{x}_m^{(i)} $ 计算出长度相同的特征 $ \vec v_u^{(j)} 、 \vec v_m^{(i)}$呢 ？显然可以使用神经网络：

假设 $ \vec{x}_u^{(j)}$ 长度为128、$ \vec v_u^{(j)} $ 长度为32; $\vec{x}_m^{(i)} $ 长度为256, $\vec v_m^{(i)} $ 长度为32

如果你想找到其他类似的电影，你可以寻找其他电影 k 使得描述电影 k 的向量和 描述电影 i 的向量之间的距离(平方距离)很小。

这可以预先计算：你可以在一夜之间运行一个计算服务器来遍历所有电影的列表，并为每部电影找到与之相似的电影，第二天如果用户访问该网站并且他们正在浏览特定的电影 ，已经预先计算出 10 或 20 部最相似的电影来展示给当时的用户。

这一点在稍后我们讨论将这种方法扩展到非常大的电影目录时会变得很重要。

上述就体现了神经网络“可连接性好”的优点，也就是可以很容易的将多个神经网络连接在一起进行训练。在实际的商业应用中，研究人员会精心挑选“原始特征”$ \vec{x}_u^{(j)} 、 \vec{x}_m^{(i)} $ ，尽管这很耗时间，但是最后可以确保算法的性能良好。

2.3 从大型目录中推荐

打开电影或者购物网站时，会在几秒之内就从数万甚至数百万个项目中，找到用户的“推荐内容”。即使神经网络已经预先训练完成，也不可能这么短的时间内全部计算完毕。实际上，当用户打开网站时，服务器只是检索最后的 $\vec{v}_u^{(j)} 、 \vec{v}_m^{(i)} $ ,并计算了“向量点积”，其他都是预先计算好，下面就来介绍如何实现这种机制：

第一步：检索(retrieval)

• 生成候选项目列表，这个列表将尽可能涵盖用户所有可能感兴趣的内容。方法有：

  1. 根据用户最后观看的10部影片，然后找出和这10部电影最相似的10部电影。
  2. 根据用户最喜爱的前3种电影类型，找出这3种类型中最受欢迎的10部电影。
  3. 当前国家或地区最受欢迎的20部电影。

• 移除重复项、用户已经看过的电影，最后生成一个列表，比如长度为100。

注1：显然“项目列表”的长度越长，推荐结果越精确，但速度越慢。一般需要offline测试，来优化“性能-速度”的折衷。

注2：这可以提前计算 电影 k 和 电影 i 的相似程度: $\left| \vec{v}_m^{(k)} - \vec{v}_m^{(i)} \right|^2$ , 需要寻找相似电影时可以直接查表。

第二部：排名(ranking)

• 将列表中的所有电影特征$\vec{v}_m^{(i)}$ 和用户特征 $\vec{v}_u^{(j)}$ 进行点积，得到用户j对于每个电影所对应的预测评分$\hat{y}^{(i,j)}$
• 排序后展示给用户。

注：用户特征$\vec{v}_u^{(j)}$ 一般都会提前计算出，用户登录时可以直接查表。

2.4 基于内容过滤的TensorFlow实现

在实际部署“基于内容过滤”的神经网络时，注意在进行向量相乘前，需要进行向量“长度归一化”。下面是代码框架：

import tensorflow as tf
# 定义用户特征的神经网络及输入输出
user_NN = tf.keras.models.Sequential([
    tf.keras.layers.Dense(256, activation='relu'),
    tf.keras.layers.Dense(128, activation='relu'),
    tf.keras.layers.Dense(32)
])
input_user = tf.keras.layers.Input(shape=(num_user_features))
vu = user_NN(input_user)                # 神经网络输入
vu = tf.linalg.l2_normalize(vu, axis=1) # 输出归一化

# 定义项目特征的神经网络及输入输出
item_NN = tf.keras.models.Sequential([
    tf.keras.layers.Dense(256, activation='relu'),
    tf.keras.layers.Dense(128, activation='relu'),
    tf.keras.layers.Dense(32)
])
input_item = tf.keras.layers.Input(shape=(num_item_features))
vm = item_NN(input_item)                # 神经网络输入
vm = tf.linalg.l2_normalize(vm, axis=1) # 输出归一化

# 将两个神经网络的输出进行点积
output = tf.keras.layers.Dot(axes=1)([vu, vm])

# 将上述两个网络合并，定义网络整体的输入输出
model = Model([input_user, input_item], output)

# 设置代价函数为平方误差
cost_fn = tf.keras.losses.MeanSquaredError()

3.1 主成分分析（PCA）算法

“主成分分析(Principal Component Analysis, PCA)”是一个经常用于可视化的“无监督学习”算法，其主要的应用领域有：

【常用】数据可视化：将高维数据(比如50维、1000维等)压缩成二维、三维，以进行绘图及可视化。并且也可以将压缩后数据恢复成原始数据。
【没落】数据压缩：显然上述“数据可视化”的过程就是“数据压缩”。但随着存储和网络的发展，对于压缩需求变小，并且也有更先进的数据压缩算法，所以此应用逐渐没落。
【没落】加速有监督学习：先将数据集的原始特征进行压缩，再进行“有监督学习”(如“支持向量机SVM”)。但对于现在的深度学习来说，压缩原始特征并没有太大帮助，并且PCA本身也会消耗计算资源，所以此应用逐渐没落。

下面就来介绍如何使用PCA算法进行“数据可视化”。

• 长度和宽度：x_1表示汽车长度、x_2表示汽车宽度。由于道路宽度限制， x_2 变化不多，所以可以直接将汽车长度 (x_1轴) 作为压缩后的特征。
• 长度和高度：x_1表示汽车长度、x_2表示汽车高度。我们可以定义一个新的“z轴”，使用各个样本点投影到“z轴”的长度来作为压缩后的特征。

PCA算法的思想是找到一组新轴，来最大可能的表示出样本间的差异。如上图所示，就展示了两个压缩二维汽车数据的示例。那该如何寻找这个具有代表性的“z轴”呢？答案是最大化方差。假设n维原始数据集为 $ m\times n $的二维矩阵$ X $, 每一行都代表一个样本$\vec x^{(i)}$, 于是PCA算法的具体步骤如下：

1. 均值归一化。计算所有样本的均值$\vec \mu$, 然后每个样本都减去此均值：$\vec x_{n}^{(i)} = \vec x^{(i)} - \vec \mu$ (下标 n 强调“均值归一化”)
2. 选取“主成分轴”。过原点旋转z轴，z轴的单位方向向量为$\vec z_n^1$(下标 n 强调“单位向量”)，然后根据所有样本在当前z轴的投影 $\vec x_{n}^{(i)} \cdot \vec z_n^1 $ 计算方差，方差最大的就是“主成分轴”
3. 选取剩余轴。z轴确定后，剩余其他轴都依次成90°，并计算出单位方向向量$\vec z_n^2,\vec z_n^3$ (可视化一般不超过3维)
4. 计算样本新坐标。新坐标就是在各轴上的投影：$[ \vec x_{n}^{(i)} \cdot \vec z_n^1, \vec x_{n}^{(i)} \cdot \vec z_n^2, \vec x_{n}^{(i)} \cdot \vec z_n^3 ]$

注：“均值归一化”是为了可以“过原点”旋转z轴，所以“均值归一化”很关键。
注：下图给出了使用PCA计算“投影”，以及根据新坐标长度“重构(reconstration)”出原始坐标的方法。

最后要说明一点，“PCA算法”不是“线性回归”，两者的差别很大：

• 线性回归是“有监督学习”；PCA算法是“无监督学习”。
• 线性回归“最小化平方误差”；PCA算法“最大化方差”。
• 线性回归是为了“预测”；PCA算法只是为了减少特征数量，方便可视化。

3.2 PCA代码实现

在Python中，主要使用 scikit-learn库来实现PCA。下面是两个代码示例：

使用PCA将2维数据压缩成2维数据，只是为了展示压缩后新坐标轴相互垂直。

from sklearn.decomposition import PCA
import numpy as np
######################## 将2维数据压缩成1维 #########################
X = np.array([[1,1], [2,1], [3,2], [-1,-1], [-2,-1], [-3,-2]])
pca_1 = PCA(n_components=1)                     # 设置压缩后维度
pca_1.fit(X)                                    # PCA压缩维度
print(pca_1.explained_variance_ratio_)          # 0.992  表示当选择一个轴时，这会捕获原始数据集中99.2%中的可变性或信息
X_trans_1 = pca_1.transform(X)                  # 计算压缩后坐标(投影)
X_reduced_1 = pca.inverse_transform(X_trans_1)  # 重构
# X_trans_1 : array([
#             [ 1.38340578] ,
#             [ 2.22189802] ,
#             [ 3.6053038 ] ,
#             [-1.38340578] ,
#             [-2.22189802] ,
#             [-3.6053038 ]])
######################## 将2维数据压缩成2维 #########################
X = np.array([[1,1], [2,1], [3,2], [-1,-1], [-2,-1], [-3,-2]])
pca_2 = PCA(n_components=2)                     # 设置压缩后维度
pca_2.fit(X)                                    # PCA压缩维度
print(pca_2.explained_variance_ratio_)          # [0.992, 0.008]
X_trans_2 = pca_2.transform(X)                  # 计算压缩后坐标(投影)
X_reduced_2 = pca.inverse_transform(X_trans_2)  # 重构
# X_trans_2 : array([
#             [ 1.38340578,  0.2935787 ] ,
#             [ 2.22189802, -0.25133484] ,
#             [ 3.6053038 ,  0.04224385] ,
#             [-1.38340578, -0.2935787 ] ,
#             [-2.22189802,  0.25133484] ,
#             [-3.6053038 , -0.04224385])

下图是把二维数据降维成一维数据

PCA(n_components=2) 时（大致重建原视数据）