Introduction to Recommender System

2017-05-02

Algorithm

recommender system

推荐系统在电子商务以及基于social的社会化网站上取得了巨大的成功，web2.0下，海量的用户数据使我们能够更加智能地发现用户的口味和需求。

推荐系统接受的输入包括：

要推荐物品、内容的元数据，比如关键字
系统用户的基本信息，比如姓名、年龄等
用户对物品信息的偏好，评分、查看记录、购买记录等
- 显示的用户反馈：评分、评价
- 隐式的用户反馈：购买记录，查看记录

混合推荐机制

加权混合
切换混合：适合的机制用在适合的场景
分区推荐：amazon，不同推荐结果展示于不同位置
分层推荐：多种推荐机制，将一个推荐机制的结果作为另一个推荐机制的输入

Super Washing Machines

2017-04-02

LeetCode

题目描述

You have $n$ super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any $m (1 ≤ m ≤ n)$ washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time .

Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.

Example1

Input: [1,0,5]
Output: 3

Explanation: 
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3    
3rd move:    2     1 <-- 3    =>    2     2     2   
Example2

Input: [0,3,0]
Output: 2

Explanation: 
1st move:    0 <-- 3     0    =>    1     2     0    
2nd move:    1     2 --> 0    =>    1     1     1     
Example3

Input: [0,2,0]
Output: -1

Explanation: 
It's impossible to make all the three washing machines have the same number of dresses. 
Note:
The range of n is [1, 10000].
The range of dresses number in a super washing machine is [0, 1e5].

解题思路

首先，如果所有洗衣机的衣服总和不能被$n$整除，返回-1.
然后对于每个洗衣机，计算它的gain/lose数组，表示还需要移除多少件衣服使得自己达到平衡状态。

举个栗子：
对于[0,0,11,5]，每个洗衣机应该有4件衣服，所以它的gain/lose数组为[-4,-4,7,1]。从第一个机器开始考虑，第一个要加入4件，得从第二个机器中过来，所以这个状态可以以4次移动的代价变成[0,-8,7,1]。同理第二个状态也可以以8次移动的代价变成状态三[0,0,-1,1]，最后以一次移动的代价变成[0,0,0,0]。

因为每一次移动可以选取任意个元素，并朝左边或者右边移动一个元素，所以总共需要的移动次数就是gain/lose数组中出现的最大值。

int findMinMoves(vector<int>& machines) {
    int sum = accumulate(machines.begin(), machines.end(), 0);
    if (sum % machines.size() != 0) return -1;
    int ret=0, tmp=0, n=sum / machines.size();
    for (int num : machines) {
        tmp += num-n;
        ret = max(max(ret, num-n), abs(tmp));
    }
    return ret;
}

代码中num-n没加绝对值，我的理解是对于初始gain/lose数组的负数，可以从两边同时添加衣服，如果是正数，那么那么每次只能移除一件衣服。而tmp加了绝对值，是因为tmp表示左边一个缺少/多的衣服数，这些衣服得从右边过来，并且一个一个达到当前位置，所以得加绝对值。

Contiguous Array

2017-04-01

LeetCode

题目描述

给定一个只包含0和1的整形数组，输出最长的连续子串的长度，要求子串中0和1的个数相同。

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

数组长度不会超过50000.

解题思路

$O(n^2)$的思路容易想到，但是数组长度太长，会超时。

方法如下：

先将数组中的0变成-1，这样连续子序列的和为0的时候满足条件
记录下0-k位置的和与k的对应关系，可以hash map的方法。和相同的只记录最左边的，毕竟长度要最长嘛
如果后面遇到了记录过的和，位置相减就能得到满足条件的子序列长度
时间复杂度为$O(n)$

代码如下：

int findMaxLength(vector<int>& nums) {
    int n = nums.size(), ret=0, sum=0;
    unordered_map<int, int> map;
    map[0] = -1; // 没有数和也为0，防止只有[0,1]时输出0
    for (int i=0; i<n; i++) if (nums[i]==0) nums[i] = -1;
    for (int i=0; i<n; i++) {
        sum += nums[i];
        // 以前遇到过sum值，现在位置-以前位置可以得到一个满足要求的序列长度
        if (map.find(sum) != map.end()) {
            ret = max(ret, i-map[sum]);
        } else { // 第一次遇到sum值，记录就行
            map[sum] = i;
        }
    }
    return ret;
}

Remove Boxes

2017-04-01

DP, LeetCode

题目描述

Given several boxes with different colors represented by different positive numbers.
You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get k*k points.
Find the maximum points you can get.

Example 1

Input:
[1, 3, 2, 2, 2, 3, 4, 3, 1]
Output:
23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----> [1, 3, 3, 3, 1] (1*1=1 points) 
----> [1, 1] (3*3=9 points) 
----> [] (2*2=4 points)

Note: The number of boxes n would not exceed 100.

解题思路

本题可以采用递归+memory（DP）的方法解决，思路是：使用数组map[i][j][k]表示从第i个元素到第j个元素，并且后面还有k个boxes[j]，也就是说现在至少有k+1个boxes[j]。对于i-j之间的满足boxes[p]=boxes[j]的元素，满足一下条件

$\begin{aligned} for\;& p\; with\;boxes[p]==boxes[j]: \\ &map[i][j][k]=\max_p(map[i][j][k], map[i][p][k+1]+map[p+1][r-1][0]) \end{aligned}$

代码为：

int dfs(vector<int>& boxes, int start, int end, int k, int map[100][100][100]) {
    int ret=0;
    if (start > end) return 0;
    if (map[start][end][k] > 0) return map[start][end][k];
    // 记录后面连续boxes[end]的数量
    while (start<end && boxes[end-1]==boxes[end]) {--end; ++k;}
    map[start][end][k] = dfs(boxes, start, end-1, 0, map)+(k+1)*(k+1);
    for (int i=start; i<end; i++) {
        if (boxes[i] == boxes[end]) {
            map[start][end][k]=max(map[start][end][k], dfs(boxes, start, i, k+1, map)+dfs(boxes, i+1, end-1, 0, map));
        }
    }
    return map[start][end][k];
}
int removeBoxes(vector<int>& boxes) {
    int map[100][100][100]={0};
    return dfs(boxes, 0, boxes.size()-1, 0, map);
}

word2vec

2017-03-31

Algorithm

NLP, machine learning

统计语言模型

自然语言处理中的一个基本问题是计算一段文本序列在某种语言下出现的概率，统计语言模型给出了这一类问题的一个基本解决框架。

对于一段文本序列$S=w_1,…,w_T$，它的概率是

$\begin{aligned} P(S)=P(w_1,...,w_T)=\prod_{t=1}^Tp(w_t|w_1,...,w_{t-1}) \end{aligned}$

问题变成了如何去预测这些条件概率.

Ngram

上述模型的参数空间巨大，一个改进方法是Ngram，有

$\begin{aligned} p(w_t|w_1,...,w_{t-1}) \approx p(w_t|w_{t-n+1},...,w_{t-1}) \end{aligned}$

Ngram本质上是将词当做一个个孤立的原子单元去处理的，用ont-hot的方式向量化word，向量维度等于词典大小。
Ngram及其他gram模型仍有局限性：

由于参数空间的爆炸式增长，它无法处理更长程的context
没有考虑词与词之间内在的联系性

Distributed Representation

用ont-hot的方式向量化单词面临着维度灾难问题，能否用一个连续的稠密向量去刻画一个word的特征呢？这样不仅可以直接刻画词与词之间的相似度，还可以建立一个从向量到概率的平滑函数模型，使得相似的词向量可以映射到相近的概率空间上。这个稠密连续向量也被称为word的distributed representation.

在信息检索领域里，这个概念被称为向量空间模型（Vector Space Model），VSM是基于一种Statistical Semantics Hypothesis，比较广为人知的两个版本是Bag of Words Hypothesis和Distributional Hypothesis，分别表示

Bag of Words Hypothesis：一篇文档的词频（而不是词序）代表了文档的主题
Distributional Hypothesis：上下文环境相似的两个词有着相近的语义

基于Bag of Words Hypothesis，我们可以构造一个term-document矩阵$A$，矩阵里的元素$A_{ij}$代表着word $w_i$在文档$D_j$中出现的次数（或频率）。可以提取行向量做为word的语义向量。

基于Distributional Hypothesis，我们可以构造一个word-context的矩阵$B$，矩阵里的元素$B_{ij}$代表着word $w_i$在context $C_j$中出现的次数（或频率）

这种co-occurrence矩阵仍然存在着数据稀疏性和维度灾难的问题，解决方法是基于SVD的稀疏矩阵分解方法。

word2vec原理

假设预料为$D=\lbrace w_1,…,w_V \rbrace$

CBoW模型（Continuous Bag-of-Words Model）

Continuous Bag-of-Words Model

CBoW的描述(N对应图中的|V|)

利用位置$t$前后的$2m$个words，以它们的one-hot编码$x_k$作为输入。通过一个共享的$n\times N$投影矩阵$V$，将每个输入投影成$n$维词向量，$N$是词典大小。$v_{t+j}=Vx_{t+j},j\in \lbrace -m,…-1,1,…,m \rbrace$这里的$V$矩阵最终包含的就是我们要的结果。
在PROJECTION层上，将$2m$个投影结果汇总（平均值，舍弃了位置信息）.$\hat{v_t}=\frac{1}{2m}\sum_{j}v_{t+j},j\in \lbrace -m,…-1,1,…,m \rbrace$，通过矩阵$U_{Nn}(U^T=[u_1,…,u_N])$连接到输出层。
最后是softmax层，$N$个节点，每个节点表示中心词是$w_i$的概率。输出层的输入向量为$z$，$z_i=u_i^T\hat{v_t}$，输出结果为$y$，$\hat{y_i}=softmax(z_i)$

模型参数是两个词向量矩阵：$U,V$，对于中心词$w_t$，模型对它的损失函数为：

$\begin{aligned} J_t&=-logP(w_t|w_{t-m},...,w_{t-1},w_{t+1},...,w_{t+m}) \\ &=-log(softmax(z_t)) \\ &=-log\frac{e^{u_t^T\hat{v_t}}}{\sum_{k=1}^V e^{u_k^T\hat{v_t}}} \\ &=-z_t+log\sum_{k=1}^V e^{z_k} \end{aligned}$

所以，整个模型的经验风险为

$\begin{aligned} J&=\sum_{w_{t+m},w_{t-m}\in D} J_t \end{aligned}$

风险$J$对$U,V$的导数为：

$\begin{aligned} \frac{\partial J}{\partial u_i} &= (\hat{y_i}-y_i)\hat{v_t} \\ \frac{\partial J}{\partial U^T} &= \hat{v_t}(\hat{y_t}-y)^T \\ \frac{\partial J}{\partial v_{t+j}} &= \frac{1}{2m}U^T(\hat{y}-y) \end{aligned}$

采取sgd更新方式，梯度下降。

Skip-gram

Skip-gram以当前词为中心，预测window内的词语，细节图中描述的很清楚了。为了描述方便，不妨假设图中的矩阵$W,W{\’}$分别为$U,V$。

由于输入向量$w_t$是one-hot向量(不妨假设第$k$行是1)，所以$Uw_t$就相当于$U$的第$k$列，在这里将其命名为$u_k$。经过$V$矩阵，得到$z=Vu_k,z_i=v_iu_k$，$v_i$是$V$的第$i$行。这里$V$也可以看成包含了所有单词对应向量的矩阵，$z$就表示了$u_k$和$V$中其他向量的相似度。最后对$z$做softmax归一化得到结果$y$(假设应该是$w_{t+1}$)，最大的对应输出。

假设真实的输出为$\hat{y}$（one-hot，$p$行为1），损失函数使用交叉熵，则对这单个样例的损失函数为

$\begin{aligned} l(t,t+1)=-logy_p=-log\frac{e^{v_iu_k}}{\sum_ie^{v_iu_k}} \end{aligned}$

所以一个句子的损失为

$\begin{aligned} L=-\frac{1}{T}\sum_{t=1}^T\sum_{i=t-m}^{t+m}l(t,i) \end{aligned}$

然后分别对$U,V$求导即可得到梯度。

Negative Sampling

继续skip-gram模型，在计算$l(t,i)$的时候，需要计算$w_t$对应的向量与每一个其他向量的相似程度$v_iu_k$，softmax对于特别大的词汇计算量很大。

负采样的思想就是把这里计算其他所有词的相似度改成只计算一部分的相似度，具体地，将这里的类softmax分类的方法变成logistic regression的方法，当前词的context的词为正样本，然后采样一部分其余的词作为负样本。

也就是将$log\frac{e^{v_iu_k}}{\sum_ie^{v_iu_k}}$变成

$\begin{aligned} log\;\sigma(v_iu_k)+\sum_{j=1}^n E_{w_i\sim p_{neg}(w_t)}[log\;\sigma(-v_ju_k)] \end{aligned}$

其中，$n$是超参数，表示负采样的数量，一般地，对小的训练集$n\in [20,50]$；对大的数据集，$n$可能只有$[2,5]$之间。$ p_{neg}(w_t)$表示对$w_t$负采样的分布。启发式的采样方法可以如下：

随机选取非正样本$w_i$，然后以一定的概率舍弃之，这个概率是

$\begin{aligned} p(w_i)=1-\sqrt{\frac{c}{f(w_i))}} \end{aligned}$

其中，$f(w_i)$是词$w_i$的词频，$c$是常数，一般在$10^{-5}$左右。这样选择，会过滤掉词频小于$c$的词，并且保证词频大的词语被选中的概率更大。

层次Softmax

由于原始的CBoW和skip-gram最后都有softmax层，导致复杂度能达到O(nN)，Hierarchical Softmax是一种对输出层进行优化的策略，输出层从原始模型的利用softmax计算概率值改为了利用Huffman树计算概率值。

投影层的输出沿着huffman树不断进行logistic二分类，并修正各中间向量和词向量
词表中的全部词作为叶子节点，词频作为节点的权，叶子结点包含word本身
每一个非叶子结点都看作是一个logistic分类器，决定下一层的走向，它包含权值
从根节点出发，到达指定叶子节点的路径是唯一的
路过非叶子结点，修正logistic参数，并且累计误差，误差最后用来修正投影矩阵$V$
Hierarchical Softmax正是利用这条唯一路径来计算指定词的概率

实现过程中，可以

不考虑投影矩阵，而是将每个词对应的向量（投影后的）设置为随机向量
通过huffman的每一个节点时都计算累加误差，利用累计误差更新当前节点的LR参数
累计误差将被用来调整词向量

word2vec的应用

广告投放

U1  a1,a2,a3……
U2  a2,a3,a5,……
U3  a1,a3,a6,……

公司A目前有很多用户的浏览数据，如用户u浏览了公司A的页面a1，a2，a3等。把每个用户的整体浏览记录当作一篇doc，每个记录就是一个word。利用word2vec算法，将每个记录转化为一个向量。向量化的页面就能够计算相似度，进而根据各种推荐规则进行推荐。

ctr预估模型

CTR（Click-Through-Rate）即点击通过率，是互联网广告常用的术语，指网络广告（图片广告/文字广告/关键词广告/排名广告/视频广告等）的点击到达率，即该广告的实际点击次数（严格的来说，可以是到达目标页面的数量）除以广告的展现量（Show content）。

广告ctr计算存在冷启动的问题，冷启动问题就是一个广告是新上线的，之前没有任何的历史投放数据，这样的广告由于数据不足，点击率模型经常不怎么凑效。

解决方法：使用同类型广告点击率来缓解，拿一个同行的广告的各种特征作为这个广告的特征，对这个新广告的点击率进行预估。
比如在媒体公司A上面有1000个广告主，它们的主页分别是a1、a2、……、a1000，运行word2vec得到每一个页面的向量，然后运行kmean或者其他聚类算法，把这1000个广告主聚成100个簇，然后每个簇里面的广告主看成是一个。

引用
[1] word2vec前世今生
[2] 深度学习word2vec笔记之应用篇
[3] 自己动手写word2vec
[4] word2vec的python实现

Latent Dirichlet Allocation

2017-03-31

Algorithm

NLP, machine learning

TF-IDF

问题的起源是文档排名，就像使用搜索引擎那样，给定关键字，返回排好序的文档列表。既然提到排序，就肯定有衡量标准，给定关键词，一个文档的重要性或者说相关性如何度量呢？

TF

首先，直观地，如果一篇文档中出现要查询的词的次数越多，相关性应该越大。于是很容易想到词频(TF)这个标准

词频TF(t)就是关键词t在文档中出现的次数

IDF

但是仅仅考虑词频必然会出现问题，因为不同的词应该有不同的重要性，举个例子：在计算机科学类的paper中，出现算法和文学类paper中出现算法的重要性是不一样的，又或者“的”这个字在汉语中出现的次数相当大，一篇文档中没有“的”字的概率是很小的，此时仅仅按照关键词中的“的”判断文档排名显然是不准确的。于是，我们希望加大稀缺词的权重，所以定义了逆文档频率(IDF)，IDF的定义如下 $IDF(t) = log\frac{N} {DF(t)}$ 其中，$N$为文档总数，$DF(t)$为所有文档中出现了关键词$t$的文档个数。所以，越是普遍的单词（“的”，“因此”等）IDF越小，而稀缺的单词（如文学paper中的“算法”）就对应着比较大的IDF。

将TF和IDF结合到一起，得到TF-IDF的计算方法： $TF-IDF(t,d) = TF(t,d) * IDF(t)$ 所以，一篇文档和一条Query的相关度为Query中所有单词在这篇文档中的TF-IDF值之和。而两个文档间的相关度是文档向量的余弦值，余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫”余弦相似性”。

TF-IDF的缺陷

单纯地认为文本频数小的单词就越重要，文本频数大的单词就越无用，并不是完全正确的
不能有效地反映单词的重要程度和特征词的分布情况，TF-IDF的精度并不是很高
没有体现出单词的位置信息，这也是空间向量模型的不足

主题模型

TF-IDF模型中没有考虑文字背后的语义关联，即语义层面上的关联，可能在两个文档共同出现的单词很少甚至没有，但两个文档是相似的。判断文档相关性的时候需要考虑到文档的语义，而语义挖掘的利器是主题模型，LDA就是其中一种比较有效的模型。

主题模型的思想源于生成模型，其思想如下：一篇文章的每个词都是通过：以一定概率选择了某个主题，并从这个主题中以一定概率选择某个词语，形式化表述为 $p(word|doc)=\sum_{topic}p(word|topic)\times p(topic|doc)$ ，具体内容在下文中描述。

能够发现文档-词语之间所蕴含的潜在语义关系（即主题）——将文档看成一组主题的混合分布，而主题又是词语的概率分布——从而将高维度的“文档-词语”向量空间映射到低维度的“文档-主题”和“主题-词语”空间，有效提高了文本信息处理的性能。

基础知识

二项分布（Binomial distribution）

$n$次重复伯努利试验，一次概率为$p$，$k$次试验概率函数为 $P(K=k)=C_n^kp^k(1-p)^{n-k}$ ，二项分布计为$X\sim b(n,p)$。

多项式分布

每次试验可能有$k$种结果，每种结果的可能性是$p_i$，则$n$次试验各种结果出现次数分别为$x_1,…,x_k$的概率是

$\begin{aligned} P(x_1,...,x_k;n,p_1,...,p_k)=\frac{n!}{x_1!...x_k!}p_1^{x_1}...p_k^{x_k} \end{aligned}$

是二项分布的扩展。

gamma函数

gamma函数形如 $\Gamma(x)=\int_0^{\infty}t^{x-1}e^{-t}dt$ 这个函数有如下性质$\Gamma(x+1)=x\Gamma(x)$，因此gamma函数可以看作是阶乘在实数集上的延拓 $\Gamma(n)=(n-1)!$ 此外，gamma函数还有如下性质

对$x\in (0,1)$，$\Gamma(1-x)\Gamma(x)=\frac{\pi}{sin(\pi x)}$
$\Gamma(\frac{1}{2})=\sqrt{\pi}$

共轭先验分布

定义
设$\theta$是总体分布中的参数，$p(\theta)$是$\theta$的先验密度函数，假如由抽样信息$x$算得的后验密度函数$p(\theta|x)$与$p(\theta)$有相同的函数形式(同一个分布簇)，则称$p(\theta)$是$p(\theta|x)$的(自然)共轭先验分布，称$p(\theta)$和$p(\theta|x)$为共轭分布。

Beta分布-二项分布的共轭先验分布

给定参数$\alpha>0,\beta>0$，取值范围为$[0,1]$的随机变量$x$的概率密度函数为

$\begin{aligned} f(x;\alpha,\beta)&=\frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)}x^{\alpha-1}(1-x)^{\beta-1} \\ &=\frac{1}{B(\alpha,\beta)} x^{\alpha-1}(1-x)^{\beta-1} \end{aligned}$

则称$x$满足Beta分布，Beta分布的均值为$\frac{\alpha}{\alpha+\beta}$，方差为$\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}$。参数$\alpha,\beta$共同控制Beta分布的函数的形状，见下图。

假定先验分布$p(\theta)$和似然概率$p(x|\theta)$满足

$\begin{aligned} p(\theta)&=\frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)}\theta^{\alpha-1}(1-\theta)^{\beta-1}\\&=\frac{1}{B(\alpha,\beta)}\theta^{\alpha-1}(1-\theta)^{\beta-1} \\ p(x|\theta)&=C_n^k\theta^k(1-\theta)^{n-k} \end{aligned}$

那么，考虑到$p(x)$为常数项，可知后验概率

$\begin{aligned} p(\theta|x)&=\frac{p(x|\theta)p(\theta)}{p(x)} \\ &= \frac{1}{Z} \theta^{\alpha+k-1}(1-\theta)^{\beta+n-k-1}. \end{aligned}$

所以，根据定义，$p(\theta)$和$p(\theta|x)$是共轭分布。

Dirichlet分布

维度$k \ge 2$的狄利克雷分布在参数$\alpha_1, …, \alpha_k > 0$上，其概率密度函数为

$\begin{aligned} f(\theta_1,..,\theta_k;\alpha_1,...,\alpha_k)&=\frac{1}{B(\alpha)} \prod_{i=1}^k\theta_i^{\alpha_i-1} \\ B(\alpha) &= \frac{\prod_{i=1}^k\Gamma(\alpha_i)}{\Gamma(\sum_{i=1}^k\alpha_i)} \end{aligned}$

同上，假设$\theta=(\theta_1,…,\theta_k)$有先验分布和似然函数,可以有

$\begin{aligned} p(\theta)&= \frac{1}{B(\alpha)} \prod_{i=1}^k\theta_i^{\alpha_i-1} \\ p(x|\theta)&= \frac{n!}{n_1!...n_k!}\theta_1^{n_1}...\theta_k^{n_k} \\ p(\theta|x)&= \frac{1}{Z} \prod_{i=1}^k\theta_i^{\alpha_i+n_i-1} \end{aligned}$

和Dirichlet分布形式一致。
Dirichlet分布的均值向量为$\left( \frac{\alpha_1}{\sum_i^k \alpha_i},…,\frac{\alpha_k}{\sum_i^k \alpha_i} \right)$。

铺垫模型

定义：

$w$表示词，$V$表示所有单词的个数（固定值）
$z$表示主题，$k$是主题的个数（预先给定，固定值）
$D=(d_1,…,d_M)$表示语料库，其中$M$是语料库中的文档数（固定值）
$d=(w_1,…,w_N)$表示一个文档，其中$N$表示一个文档中的词数（随机变量）

Unigram model

对于文档$d=(w_1,…,w_N)$，用$p(w_n)$表示$w_n$的先验概率，生成文档$d$的概率为 $p(d)=\prod_{n-1}^Np(w_n)$ unigram model假设文本中的词服从Multinomial分布，而Multinomial分布的先验分布为Dirichlet分布。

Unigram model

上图中，$w_n$是在文本中观察到的第$n$个词，$p$和$α$是隐含未知变量,其中

$p$是词服从的Multinomial分布的参数
$\alpha$是Dirichlet分布（即Multinomial分布的先验分布）的参数

一般$\alpha$由经验事先给定，$p$由观察到的文本中出现的词学习得到，表示文本中出现每个词的概率。

Mixture of unigrams model

Mixture of unigrams model生成过程是：给某个文档先选择一个主题，再根据该主题生成文档，该文档中的所有词都来自一个主题。假设主题有$z_1,…,z_k$，生成文档$d$的概率为

$\begin{aligned} p(d)=\sum_zp(z) \prod_{n=1}^N p(w_n|z) \end{aligned}$

Mixture of unigrams model

如上图所示。

PLSA模型

Mixture of unigrams model中假定一篇文档只由一个主题生成，可实际中，一篇文章往往有多个主题，只是这多个主题各自在文档中出现的概率大小不一样。PLSA是一种词袋模型，不关注词和词之间的出现顺序。

假设一组共现(co-occurrence)词项关联着一个隐含的主题类别$z_k\in \lbrace z_1,…,z_K \rbrace$。同时定义

$p(d_i)$表示海量文档中某篇文档被选中的概率
$p(w_j|d_i)$表示词$w_j$在给定文档$d_i$中出现的概率
$p(z_k|d_i)$表示具体某个主题$z_k$在给定文档$d_i$下出现的概率
$p(w_j|z_k)$表示具体某个词$w_j$在给定主题$z_k$下出现的概率，与主题关系越密切的词，其条件概率越大

文档到词项的生成方法

按照概率$p(d_i)$选择一篇文档$d_i$
选定文档$d_i$后，从主题分布中按照概率$p(z_k|d_i)$选择一个隐含的主题类别$z_k$
选定$z_k$后，从词分布中按照概率$p(w_j|z_k)$选择一个词$w_j$

整个过程便是：选定文档->生成主题->确定主题生成词。

发现文档集中的主题（分布）

PLSA

如上图所示，文档$d$和单词$w$是可被观察到的（样本），但主题$z$却是隐藏的。因为$p(w_j|d_i)$是已知的(统计文档词频)，根据大量已知的文档-词项信息可以训练出$p(z_k|d_i),p(w_j|z_k)$。文档中每个词的生成概率为

$\begin{aligned} p(w_j,d_i) &= p(d_i)p(w_j|d_i) \\ &= p(d_i)\sum_{k=1}^Kp(w_j|z_k)p(z_k|d_i) \end{aligned}$

其中$p(d_i)$可事先计算求出，$p(z_k|d_i),p(w_j|z_k)$未知。

考虑词和词($N$)之间、文档($M$)和文档之间的独立性，则整个语料库中词的分布为

$\begin{aligned} p(w,D)=\prod_{i=1}^M\prod_{j=1}^Np(w_j,d_i)^{n(w_j,d_i)} \end{aligned}$

其中$n(w_j,d_i)$表示词项$w_j$在文档$d_i$中出现的次数，$n(d_i)$表示文档$d_i$中词的总数，并且令$p(w_j|z_k)=\phi_{kj},p(z_k|d_i)=\theta_{ik}$将未知量矩阵化成$\Phi,\Theta$。所以得到对数似然函数

$\begin{aligned} l(\Phi,\Theta)&= \sum_{i=1}^M\sum_{j=1}^Nn(w_j,d_i)\log p(w_j,d_i) \\ &= \sum_{i=1}^M\sum_{j=1}^Nn(w_j,d_i)\left(\log p(d_i)+\log\sum_{k=1}^Kp(w_j|z_k)p(z_k|d_i)\right) \\ &= \sum_{i=1}^Mn(d_i)\left( \log p(d_i)+ \sum_{j=1}^N \frac{n(w_j,d_i)}{n(d_i)} \log\sum_{k=1}^K \phi_{kj}\theta_{ik} \right) \\ &\propto \sum_{i=1}^M \sum_{j=1}^N n(w_j,d_i) \log\sum_{k=1}^K \phi_{kj}\theta_{ik} \\ & \ge \sum_{i=1}^M \sum_{j=1}^N n(w_j,d_i) \sum_{k=1}^K p(z_k|d_i,w_j) \log(\phi_{kj}\theta_{ik}) \end{aligned}$

含有隐含变量的优化可以使用EM算法求解，很复杂，不具体写了
E步

$\begin{aligned} p(z_k|d_i,w_j)&=\frac{p(z_k,d_i,w_j)}{\sum_{l=1}^Kp(z_l,d_i,w_j)}=\frac{\phi_{kj}\theta_{ik}}{\sum_{l=1}^M\phi_{lj}\theta_{il}} \end{aligned}$

M步
经过E步，还需考虑约束条件，即

$\begin{aligned} \sum_{j=1}^N\phi_{kj}&=1 \\ \sum_{k=1}^K\theta_{ik}&=1 \end{aligned}$

用拉格朗日乘子法解得

$\begin{aligned} \phi_{kj} &= \frac{\sum_{i=1}^M n(d_i,w_j)p(z_k|d_i,w_j)} {\sum_{i=1}^M\sum_{j=1}^N n(d_i,w_j)p(z_k|d_i,w_j)} \\ \theta_{ik} &= \frac{\sum_{j=1}^N n(d_i,w_j)p(z_k|d_i,w_j) }{n(d_i)} \end{aligned}$

这样就求解出了$\Phi,\Theta$。PLSA的模型示意如下图所示:

PLSA

LDA(Latent Dirichlet Allocation)

LDA在pLSA的基础上加层贝叶斯框架，在贝叶斯框架下的LDA中，我们不再认为主题分布（各个主题在文档中出现的概率分布）和词分布（各个词语在某个主题下出现的概率分布）是唯一确定的（而是随机变量）。这体现了贝叶斯派的核心思想，把未知参数当作是随机变量，不再认为是某一个确定的值。即选主题和选词依然都是两个随机的过程。

LDA需要两个Dirichlet先验参数，这个Dirichlet先验为某篇文档随机抽取出某个主题分布和词分布。

LDA模型中文档生成方式

$\alpha$是主题分布的先验分布，$\beta$是词分布的先验分布。

按照先验概率$p(d_i)$选择一篇文档$d_i$
从Dirichlet分布$\alpha$中取样生成文档$d_i$的主题分布$\theta_i$，换言之，主题分布$\theta_i$由超参数为$\alpha$的Dirichlet分布生成
从主题的多项式分布$\theta_i$中取样生成文档$d_i$第$j$个词的主题$z_{ij}$
从Dirichlet分布$\beta$中取样生成主题$z_{ij}$对应的词语分布$\phi_{z_{ij}}$，换言之，词语分布$\phi_{z_{ij}}$由参数为$\beta$的Dirichlet分布生成
从词语的多项式分布$\phi_{z_{ij}}$中采样最终生成词语$w_{ij}$

示意图如下:

LDA

LDA在pLSA的基础上给这两参数$p(z_k|d_i),p(w_j|z_k)$加了两个先验分布的参数（贝叶斯化）：一个主题分布的先验分布Dirichlet分布$\alpha$，和一个词语分布的先验分布Dirichlet分布$\beta$。这里$\alpha,\beta$都是参数向量。

LDA生成文档的过程中，先从dirichlet先验中“随机”抽取出主题分布，然后从主题分布中“随机”抽取出主题，最后从确定后的主题对应的词分布中“随机”抽取出词。虽说是随机取值，但是不同的参数$\alpha,\beta$导致可选值的分布是不一样的，如下图所示

不同参数的dirichlet分布

LDA发现文档集中的主题

文档生成后，LDA把这两参数$p(z_k|d_i),p(w_j|z_k)$变成随机变量，且加入dirichlet先验。

在pLSA中，我们使用EM算法去估计“主题-词项”矩阵和“文档-主题”矩阵：$\Phi,\Theta$，这两参数都是个固定的值。在LDA中，估计$\Phi,\Theta$这两未知参数可以用变分(Variational inference)-EM算法，也可以用gibbs采样，前者的思想是最大后验估计MAP（MAP与MLE类似，都把未知参数当作固定的值），后者的思想是贝叶斯估计。

Gibbs采样
Gibbs抽样是马尔可夫链蒙特卡尔理论（MCMC）中用来获取一系列近似等于指定多维概率分布（比如2个或者多个随机变量的联合概率分布）观察样本的算法。

给定一个文档集合，$w$是可以观察到的已知变量，$\alpha,\beta$和是根据经验给定的先验参数，其他的变量$z，\Theta和\Phi$都是未知变量。

求解$\Theta,\Phi$的过程很复杂，最终求解的Dirichlet分布期望为：

$\begin{aligned} \phi_{kt}&=\frac{n_k^{t}+\beta_t} {\sum_{t=1}^V(n_k^{t}+\beta_t)} \\ \theta_{mk}&=\frac{n_m^{k}+\alpha_k}{\sum_{k=1}^K(n_m^{k}+\alpha_k)} \end{aligned}$

其中，$\phi_{kt}=p(w_t|z_k),\theta_{mk}=p(z_k|d_m)$，$n_t^k$是词$w_t$在主题$z_k$中出现的次数，$n_m^k$是主题$z_k$在文章$d_m$中出现的次数。

引用
[1] LDA-math-神奇的Gamma函数
[2] 共轭先验分布
[3] 通俗理解LDA主题模型
[4] 关于Beta分布、二项分布与Dirichlet分布、多项分布的关系

Prime Factor Index in Factorial

2017-03-18

Math

题目的中文翻译是：阶乘中质因数的指数。
比如说一道谷歌面试题，求2014!尾部0的个数.

求尾部0的个数，也就是求这个数中质因子5的个数，有定理

在$n!$ 中质因子$p(p<=n)$的指数为：$h=[\frac{n}{p}]+[\frac{n}{p^2}]+…$，其中[]表示取整符号。

所以2014!中5的指数是

$\begin{aligned} &\left[\frac{2014}{5}\right]+\left[\frac{2014}{25}\right]+\left[\frac{2014}{125}\right]+\left[\frac{2014}{625}\right] \\ &= 402+80+16+3 \\ &= 501 \end{aligned}$

Cpp Rule Fragment3

2017-03-16

Dev

Cpp

模板与泛型编程

定义模板

函数模板可以定义为inline、constexpr，关键字位置应该在模板参数列表之后，返回类型之前
编译器遇到模板时不生成代码，只有在实例化特定版本（使用）时，编译器才会生成代码
使用普通类对象时，类定义必须可用但成员函数的定义不必已经出现，因此类定义和函数声明放在头文件，函数、类成员函数定义在源文件。但实例化模板时，编译器需要知道模板定义，所以函数模板、类模板的定义通常放在头文件中
大多数编译错误在实例化时期报告

template <typename T>   // typename有的也写做class，意义相同
.....

template <typename T>
inline T sort(const T&, const T&); // ok

inline template <typename T> T sort(const T&, const T&); // wrong

非类型模板参数

非类型模板参数表示值，而非类型
非类型模板参数被用户提供的或者编译器推断的值替代，这些实参值必须是常量表达式
非类型参数可以是整型（实参必须是常量表达式），指向对象或函数类型的指针、左值引用（实参必须具有静态生存期（局外变量、静态变量、栈））

类模板

类的作用域包括：类定义中，源文件类成员函数的函数体内({}之内)
类的作用域中，编译器处理模板自身引用时可以不带类型名

template <typename T>
void Blob<T>::check (const T& t1, const T& t2) {
    // ......
}

// 类作用域中
Blob<T>& func();  // ok
Blob& func(); // ok
// 之外
Blob& func {   // wrong
    Blob ret = *this; // ok, in scope
    ...
    return ret;
}

类模板和友元

如果类模板包含非模板友元，则该友元可以访问所有模板实例
如果类模板包含模板友元，类可以授权给所有模板实例，也可以只授权给特定实例

template <typename T>
class A {
friend B<T>;  // 授权给特定实例，要求类型相同
friend C<F>;  // 授权给所有模板实例
}

模板类型别名

typedef Blob<string> strBlob;
// 为类模板定义一个类型别名
template<typename T> using twin = pair<T, T>;
twin<int> p;  // 定义类型为<int, int>类型

// 可以固定一个、多个模板参数
template<typename T> using partNo = pair<T, unsigned>;

静态成员

模板的static成员也定义成模板，每个模板的实例都可以有一个自己的静态成员
template<typename T> size_t Foo<T>::ctr = 0;
通过引用特定实例、作用域运算符访问成员Foo<int>::ctr;

模板参数

模板内不能重用模板参数名
模板声明必须包含模板参数
使用模板类型参数的类型成员，必须通过关键字typename(class不行)显式地告诉编译器该名字是一个类型

1
2
3

T::size_type *p; // 可以是定义指向size_type类型的指针，也可以是T的静态成员乘以p的结果

typename T::size_type *p; // 定义指向size_type类型的指针

成员模板

成员模板不能是虚函数
实例化类模板的成员模板，必须同时提供类和函数模板的实参Blob<int> a1(vi.begin(), vi.end());

class Blob {
template<typename T> void func(const T&);
}
string s = "hello";
Blob b;
b.func(s);

template<typename T> class Blob {
template<typename F> Blob(const F&);
}
string s = "hello";
Blob<int> b(s);

控制实例化

模板在使用时才会实例化，多个文件中的模板实例化可能会造成严重额外开销
通过显示实例化避免开销，编译器遇到extern模板声明时就不会在本文件中生成实例化代码
类模板的实例化会实例化所有成员（包括内联）（和普通类不同）

1 2	extern template declaration; // 实例化声明 template declaration; // 实例化定义

模板实参推断

模板转换

如果函数形参使用了模板类型参数，其采用特殊的初始化规则
编译器通常不是对实参进行类型转换，而是生成一个新的模板实例，例外在下面
- const转换，忽略顶层const
- 数组、函数指针转换（函数形参不能为引用类型）

显式模板实参、`remove_reference`

显式模板参数在<>中给出，函数名后，参数列表之前
显式模板实参按从左向右的顺序与对应的模板参数匹配，尾部的可以忽略

template<typename T1, typename T2, typename T3>
T1 func(T2, T3);  // bad
T1 func<int>(T2, T3); // T1 is int
T1 func<int, string>(T2, T3); // T1 is int, T2 is string

template<typename T1, typename T2, typename T3>
T3 func(T2, T1); // wrong
T3 func<int>(T2, T1); // wrong, T3是int，但不能推断T1、T2
T3 func<int, int, int>(T2, T1); // ok

// 尾后类型的使用
template<typename T>
auto func(T beg, T end) -> decltype(*beg) {
    return *beg;
}

// 上面迭代器返回的是引用，如果希望返回原来类型，如下
template<typename T>
auto func(T beg, T end) -> typename remove_reference<delctype(*beg)>::type {
    return *beg;  // 返回元素的拷贝
}

其中，remove_reference<T&>将得到原本的T类型，类型由其类型成员type表示

Sunday

2017-03-15

Algorithm

String

算法描述

Sunday算法是用于字符串匹配的算法，平均复杂度为O(n)，平均效率高于KMP和BM。

示例如下：
匹配时，从左到右匹配，第一个字符不匹配，看模式串后一位t对应的字符，因为t位的字符也总是要匹配的。所以我们需要查找t位字符在模式串中最右侧的位置，然后移动模式串。如果t位的字符在模式串中不存在，那么移动模式串首到当前模式串尾部的下一个位置。

suck kmy balls
kmy

对齐字母k，如下

suck kmy balls
   kmy

还不匹配，继续

suck kmy balls
     kmy

匹配出现，记录下。然后再看下一个字符，其在模式串没出现，移动模式串到

suck kmy balls
         kmy

依此类推，直到结束。

下面看一下具体移动的步长，设当前p和s的位置分别在pi和si，p结尾的最后一个位置对应于s中序号为skey = si+p.length()-pi的位置：

如果skey中的字符在模式串p中没有，则将pi=0，si移到skey+1位置

否则，要令skey与p中对应的最右相同元素对齐，设p中序号为k的元素满足条件，si需要移动变成skey-k=si+p.length()-pi-k，同样地pi=0

代码

sunday算法需要维护一个数组，记录s串中下一个字符为x时模式串移动的距离。命其名为next

void get_next(string p, vector<int> &next) {
    for (int i=0; i<p.length(); i++) {
        next[p[i]] = p.length()-i;  // 模式串有的字符
    }
}

void sunday(string s, string p) {
    vector<int> next(255, p.length()+1);  // 默认不存在模式串中的字符对应的移动长度为p.length()+1
    get_next();
    int si=0, pi=0;
    while (si+p.length() < s.length()) {
        pi = 0;
        for (pi=0; pi<p.length(), s[si++] != p[pi]; pi++); // matching
        if (pi == p.length())  // match found
            cout << "match found, index is " << si-p.length()+1 << endl;
        int skey = si + p.length() - pi;
        if (skey >= s.length) break;
        si += next(s[skey]) - pi;
    }
}

K-Nearest Neighbor

2017-03-07

Algorithm

machine learning

KNN

KNN的算法思想非常简单，不赘述。
K值的选择有讲究，一般使用交叉验证的方法来确定K值。

KD树

KNN naive的实现实现方法是线性扫描法，但是这种方法效率很差，训练集很大时非常耗时。好一点的方法是使用一个最大堆，时间复杂度为$O(nlogK)$。

下面介绍基于树的方法：kd树。

kd树是二叉树，表示对k维空间的一个划分。相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的超矩形区域。

kd树的构造方法如下：

输入：数据集$D=\lbrace x_1,x_2,…,x_n \rbrace$
其中$x_i=(x_i^{(1)},…,x_i^{(k)})$为$k$维空间的样本

1) 构造根结点，根节点对应于包含$D$的$k$维空间超矩形区域。选择$x^{(1)}$为坐标轴，以$D$中所有样本的$x^{(1)}$坐标的中位数作为切分点，切成两部分。落在超平面上的点保存在根节点，在超平面左侧、右侧的节点分别根节点深度为1的左右孩子。
2) 重复：对深度为$j$的节点，选择$x^{(l)}$作为切分的坐标轴，满足$l=j\; mod\; k + 1$，坐标轴轮流选，一轮完了再重复.
3) 迭代停止条件：如果一个节点的左右孩子中都没有样本，那么停止迭代

输出：kd树

下面介绍使用kd树进行k近邻搜索，使用最大堆辅助结构

输入：已构造的kd树，目标点$x$，近邻数$K$，空最大堆$hp$

从根节点出发，递归地向下访问kd树，若目标$x$当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到结点为叶节点为止。对每一个路过的节点，添加元素维护最大推（留下小的）。
递归的向上回退，在每个节点$p$进行以下操作
- 检查该结点未被访问过的结点$p_c$对应的区域是否有比堆顶元素更近的点或堆容量未满。具体的，检查$p_c$对应的区域是否与以目标点为求心、以目标点与堆顶元素距离为半径的球体相交
- 如果相交或$hp$容量未满，以$p_c$结点为根节点执行1，否则继续回溯
当对根节点的回溯完成以后，结束

输出：最大堆$hp$内元素即为$s$的$K$近邻

kd树更适用于训练实例数远大于空间维度数时的计算，空间维度接近训练实例数时，效率会迅速下降，几乎接近线性扫描。

推荐系统分类

根据不同用户的推荐

大众行为推荐

个性化推荐

根据数据源

基于人口统计学的推荐

根据推荐物品或内容的元数据

基于协同过滤的推荐

基于推荐模型的建立方式

基于物品和用户本身的推荐

基于关联规则的推荐

基于模型的推荐

SVD在推荐系统中的应用

混合推荐机制

题目描述

解题思路

题目描述

解题思路

题目描述

解题思路

统计语言模型

Ngram

Distributed Representation

word2vec原理

CBoW模型（Continuous Bag-of-Words Model）

Skip-gram

Negative Sampling

层次Softmax

word2vec的应用

广告投放

ctr预估模型

TF-IDF

TF

IDF

TF-IDF的缺陷

主题模型

基础知识

二项分布（Binomial distribution）

多项式分布

gamma函数

共轭先验分布

Beta分布-二项分布的共轭先验分布

Dirichlet分布

铺垫模型

Unigram model

Mixture of unigrams model

PLSA模型

LDA(Latent Dirichlet Allocation)

LDA模型中文档生成方式

LDA发现文档集中的主题

模板与泛型编程

定义模板

类模板

类模板和友元

模板参数

成员模板

控制实例化

模板实参推断

模板转换

显式模板实参、remove_reference

算法描述

代码

KNN

KD树

显式模板实参、`remove_reference`