声明
先导知识：随机梯度下降法，矩阵分解，并行/并发计算。
本文是对学习 LIBMF 2.01 的备忘录，其中相当多的内容直接来自于论文: W.-S. Chin, Y. Zhuang, Y.-C. Juan, and C.-J. Lin. A Fast Parallel Stochastic Gradient Method for Matrix Factorization in Shared Memory Systems. ACM TIST, 2015.
文中的计算单元可理解为一条线程或进程。
相关资料备份：论文 PDF 及源代码
简介
LIBMF（2.01）由台湾大学机器学习团队开发，是用于矩阵分解的开源API。LIBMF 主要使用了作者所提出的 FPSG 与 RPCS （可参考LIBMF分析的姊妹篇：RPCS —— SGD 下降速率方案与 LIBMF 分析）算法。LIBMF 的源代码本身没有多少注释，但是官网上公布了三篇相关论文介绍其算法，而且源码附带的 README 文件对关键数据结构与 API 做了较详细的解释。所以可以说“注释”是相当详尽的。
矩阵分解
以推荐系统为例。矩阵 $R{u \times v}$ 记录了u个用户对v项商品的购买评分，推荐系统根据已有的评分预测用户对未评商品的评分，从而向用户做商品推荐。矩阵分解所做的，给定 k ，把 $R{u \times v}$ 分解成 $P{k \times u}$ 和 $Q{k \times v}$ ，用 $P^\mathrm{T} Q = \hat{R}$ 近似表示 $R$ ，而 $\hat{R}$ 填充了 ${R}$ 中未知的部分。
其核心是解决最优化问题：
$$\min{P, Q} \sum{u, v}((r_{u,v} - p_u^\mathrm{T}q_v)^2 - \lambda_p ||p_u||^2 - \lambda_q ||q_v||^2) \label{opt} \tag{1}$$
其中 ${\lambda_p}$ 与 $\lambda_q$ 是正则化参数。
随机梯度下降
随机梯度下降法求解最优化问题 $\ref{opt}$，相对梯度下降法更快。求解出 $p_u$, $q_v$ 下降公式：
$$p_u \leftarrow pu + \gamma ((r{u,v} - p_u^\mathrm{T}q_v)q_v - \lambda_p p_u) \label{sgdP} \tag{2}$$
$$q_v \leftarrow qv + \gamma ((r{u,v} - p_u^\mathrm{T}q_v)p_u - \lambda_q q_v) \label{sgdQ} \tag{3}$$
FPSG
即Fast Parallel Stochastic Gradient，快速的并行梯度下降算法。顾名思义，在求解 $P$, $Q$ 时，运用并行计算和梯度下降算法实现对矩阵的快速分解。
相关算法
HogWild
运用并行计算和梯度下降算法。并行计算实现方法是将公式 $\ref{sgdP}$ 与公式 $\ref{sgdQ}$ 分别交由2个计算单元P1, P2处理，重要的是，P1、P2之间无需进行同步，避免了P1、P2对资源的竞争。
其隐藏的问题是，当2个计算单元同时选取了相同的u或v，可能出现数据的污染。比如，P1、P2同时选取了同一个u值，当P1写入 $p_u$ 时，P2可能同时读取 $p_u$ 的数据，P2可能读入只完成了部分写入的 $p_u$，即读入了错误的数据。然而，这个问题被证明是极少出现的。
DSGD
同样运用并行计算和梯度下降算法。它将 $R$ 划分成 $s \times s$ 的分块，再将其中的s个分块分给s个计算单元对 $P$、$Q$ 进行随机梯度下降计算，每个计算单元只被允许选取分块中的 (u, v)。为了避免数据污染，每个被分配的分块u、v值不能重合。例图：
其中，每一个大矩阵视作一次迭代，每次迭代中，R被分为了3X3的分块，灰色分块被选中分配给计算单元，而且明显每个灰色区域间u、v不重合。
FPSG
FPSG 主要在DSGD上做了2处重要改进。
无锁调度
增加分块
在 DSGD 中，由于 $R$ 被划分成 $s \times s$ 的分块后，最多只能分配给s个计算单元，当某个计算单元完成了一个分块计算后，只能等待其他所有计算单元完成任务重新随机分块进行下一次迭代。显然这造成了资源浪费。
FPSG 的方案是至少划分 $(s+1) \times (s+1)$ 的分块，当某个计算单元完成了一个分块计算，它可以马上选择其他分块而无需等待。例图：
其中有 $(3+1) \times (3+1)$ 个分块，3个非白色块是当前正在计算的分块，此时红色分块计算完成，有3个分块可以直接进行下一步计算。
均衡分块
同时，研发者发现，分块内记录（ $r_{u,v} \neq 0$ ）的稀疏程度影响了块内(u,v)被选中更新的概率。因为，如果分块内记录稀疏，意味着分块计算更快，使得分块更新的频率更高，进而增加了该分块内(u,v)更新的频率。这可能导致某些记录稠密的分块内 $p$、$q$ 更新不足。
为解决以上问题，FPSG在分块前将 $R$ 分别按行、按列打乱，使得记录分布更均匀。例图：
其中，黑点表示记录，在”After the random shuffle”中，黑点分布较为均匀，甚至在分块后，每个块的记录都是一个。
之后，FPSG做了更进一步优化。它启用了一个调度程序，用一个优先级队列记录每个分块被更新的次数，每当一个计算单元完成任务请求下一个分块时，调度程序分配给它更新最少（且未被占用）的分块。
按序更新
程序读取连续的数据相比读取分散的数据更快，所以FPSG的计算单元按行顺序更新分块，放弃了随机选择的方式。在 均衡分块 部分的配图“shuffle blocks”中，“Sort row indices in each block”部分在更新开始前对分块内的行进行了排序。例图：
其中按行选取分块内 $r_{u,v}$，这样，基本上 $p^\mathrm{T}$ 是被连续读取的。
这样处理似乎失去了采样的随机性，但FPSG已经在 无锁调度 中保证了一定程度的随机性。
LIBMF
作者给出了伪代码：
其中的 scheduler 程序：
在 GET_JOB 子程序中，scheduler 只抽取了优先级最高的空闲的块，而在 PUT_JOB 子程序中，为了避免出现2个分块优先级相同的情况，它为每个分块优先级加上一个随机小数。
工作线程程序：