发表于   |   分类于

整型

占用 bits

  • char $\leq$ short $\leq$ int $\leq$ long $\leq$ long long
  • char 占用1字节，unsigned最大值255
  • short 至少占用16 bit，unsigned最大值65535，6万多
  • long 至少占用32 bit，unsigned最大值4294967295，40多亿

相关库

用\, \头文件查看最值

1
2
3
4
#include <limits.h>

int max = INT_MAX;
int min = INT_MIN;

signed 与 unsigned

整型默认signed，只有char由实现定义

其它

  • int 被编译器认为是“最自然”的整型。在运算时，比 int “低级”的类型会转换成int类型处理
  • % 运算符，对于负整数的处理，可视为：a % b = a - (a/b) * b

浮点数

占用 bits

  • 浮点数的指数部分至少从-37取到37，也就是取值范围（正数）至少是E-37 ~ E+37
  • float $\leq$ double $\leq$ long double
  • float 至少占用32 bit
  • double 至少占用48 bit

存储结构

分为2部分，一是指数部分 $e$，二是尾数部分 $r$，所表示的值为 $r \times 10^e$，这就像把 $r$ 作为整数的小数点移动 $e$ 位一样，所以称为浮点数。

相关库

\, \对浮点数有相关限定

1
2
3
4
#include <float.h>

float max = FLT_MAX; // double: DBL_MAX, long dboule: LDBL_MAX
float min = FLT_MIN; // double: DBL_MIN, long dboule: LDBL_MIN

其它

常量小数默认为 double，如需float加f或F，需long double加L

参考

发表于   |   分类于

声明

先导知识：随机梯度下降法，矩阵分解，并行/并发计算。

本文是对学习 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个分块优先级相同的情况，它为每个分块优先级加上一个随机小数。

工作线程程序：