FM (Factorization Machine)

一. 应用场景

在计算广告领域,点击率CTR(click-through rate)和转化率CVR(conversion rate)是衡量广告流量的两个关键指标。准确的估计CTR、CVR对于提高流量的价值,增加广告收入有重要的指导作用。预估CTR/CVR,业界常用的方法有人工特征工程 + LR(Logistic Regression)、GBDT(Gradient Boosting Decision Tree) + LR、FM(Factorization Machine)和FFM(Field-aware Factorization Machine)

二.目的

旨在解决稀疏数据下的特征组合问题

三.优点

    • 高度稀疏数据场景;
    • 具有线性的计算复杂度。

四.原理

公示推导

    • 通过组合交叉的特性来学习特征为0样本的权重参数。每个参数 [公式] 的训练需要大量[公式] 和 [公式]都非零的样本;由于样本数据本来就比较稀疏,满足“[公式] 和 [公式]都非零”的样本将会非常少。训练样本的不足,很容易导致参数 [公式] 不准确,最终将严重影响模型的性能;[公式] 和 [公式]的系数分别为 [公式] 和 [公式] ,它们之间有共同项 [公式]即尽管 [公式]为0,但由于[公式]不为0 ,那么就可以通过[公式] 来学习[公式]。也就是说,所有包含“ [公式] 的非零组合特征”(存在某个 [公式] ,使得 [公式] )的样本都可以用来学习隐向量[公式],这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中, [公式] 和 [公式] 是相互独立的。
    • 由于[公式]是对阵矩阵,也即半正定矩阵,这边当作正定矩阵近似求解,这个矩阵就可以分解为 [公式]
    • 由于[公式] 代表向量内积(点乘/数量积),具有对称性,即<a,b>=<b,a>,所以<x_i, x_j>为实对称矩阵,则是对称矩阵,而FM项 是这个对称矩阵的上三角部分(不包含对角线),所以FM项就等于减去对角线再除以2
    • FM的复杂度是 [公式] 。通过计算优化,FM的二次项可以化简,其复杂度可以优化到 [公式]

SGD梯度更新参数

 

其中, [公式] 代表样本的特征数量,[公式]是第 [公式] 个特征的值, [公式] 是模型参数,vi/vj隐向量的长度为 [公式]

五.参考

表达式求值

中缀表达式转后缀表达式。对于普通中缀表达式的计算,我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈,扫描该中缀表达式:

  1. 如果遇到数字,直接将该数字输出到后缀表达式(以下部分用「输出」表示输出到后缀表达式);
  2. 如果遇到左括号,入栈;
  3. 如果遇到右括号,不断输出栈顶元素,直至遇到左括号(左括号出栈,但不输出);
  4. 如果遇到其他运算符,不断去除栈顶所有运算优先级大于等于当前运算符的运算符,输出。最后,新的符号入栈;
  5. 把栈中剩下的符号依次输出,表达式转换结束。

对于一个后缀表达式,只需要 维护一个数字栈,每次遇到一个运算符,就取出两个栈顶元素,将运算结果重新压入栈中 。最后,栈中唯一一个元素就是该后缀表达式的运算结果时间复杂度  。

class Solution {
    //适用于个位数,加减乘除
public:
    int calculate(string s) {
        stack<char> sign;//运算符栈
        vector<char> postfix;//后缀表达式
        for (auto ch :s) {
            if (ch == ' ')
                continue;
            else if (isdigit(ch)) {
                postfix.push_back(ch);
            } else if (ch == '(') {
                sign.push(ch);
            } else if (ch == ')') {
                while (!sign.empty() && sign.top() != '(') {
                    postfix.push_back(sign.top());
                    sign.pop();
                }
                sign.pop();
            } else {
                while (!sign.empty() && get_priority(sign.top()) >= get_priority(ch)) {//只要栈顶运算符的优先级不低于新运算符,就不断取出栈顶并输出
                    postfix.push_back(sign.top());
                    sign.pop();
                }
                sign.push(ch);
            }
        }
        while (!sign.empty()) {
            postfix.push_back(sign.top());
            sign.pop();
        }
        //遇到运算符就计算
        stack<int> nums;
        for (auto item:postfix) {
            if (isdigit(item))
                nums.push(item - '0');
            else {
                int one = nums.top();
                nums.pop();
                int two = nums.top();
                nums.pop();
                if (item == '+') {
                    nums.push(one + two);
                } else if (item == '-') {
                    nums.push(two - one);
                } else if (item == '*') {
                    nums.push(one * two);
                } else if (item == '/') {
                    nums.push(two / one);
                }
            }

        }
        return nums.top();
    }

    int get_priority(char ch) {
        if (ch == '+' || ch == '-')
            return 0;
        else if (ch == '*' || ch == '/')
            return 1;
        else
            return -1;
    }
};

Perplexity in language model

1.PPL

PPL是用在自然语言处理领域(NLP)中,衡量语言模型好坏的指标。它主要是根据每个词来估计一句话出现的概率,并用句子长度作normalize,公式为

 

由公式可知,perplexity越小,模型越好。从公式最后一部分,感觉更像是描述GPT这种生成模型。

2.Language Model

  • autoregressive (AR) language model

GPT:

 

  • autoencoding (AE)language model

BERT(denoising auto-encoding):

where mt = 1 indicates xt is masked.

3.Reference

[论文笔记][2020-WWW]Enhanced-RCNN: An Efficient Method for Learning Sentence Similarity

前面的Related可以用来做综述

一、Architecture

二、Detail

1.Input Encoding

(a)RNN Encoder

(b)CNN Encoder

2.Interactive Sentence Representation

(a)Soft-attention Alignment(类似于ESIM)

(b)Interaction Modeling

3.Similarity Modeling

(a)Fusion Layer

(b)Label Prediction

MLP+softmax

三、Reference

文本生成中的解码策略

一.Language model decoding

given a sequence of m tokens as context, the task is to generate the next n continuation tokens to obtain the completed sequence . We assume that models compute using the common left-to-right decomposition of the text probability,

which is used to generate the generation token-by-token using a particular decoding strategy

二.Decoding Strategies

1.Maximization-based decoding

解码器的输出层后面通常会跟一个softmax函数来将输出概率归一化。如果词表比较大的话,softmax的计算复杂度会比较高(分母需要计算整个词表大小的维度)

  • Greedy decoding

每次选最高概率的一项作为输出,直到遇到结束符号,将这些输出的概率相乘,得到该sequence的概率。

缺点:每次选择都是最大的,但是整体的概率不一定是最大的,有可能错过最优的结果

考虑到`Beam Size=2`,第一步选择概率最大的两个A和B,第二步选择AB和BB(橙色大箭头)。然后以选择的AB和BB继续向上传播,又出现了四种情况ABA/ABB/BBA/BBB,依然是选择综合概率最大的两个ABB/BBB。以此类推,直至句子结束。

缺点:

    • 由于beam search的概率是一個连续相乘的結果,越早遇到结束符号,所得到的概率会越大,所以更倾向于生成短文本。解决办法是对输出概率取log,然后相加,最终结果除长度求最大概率((a * b)^ 1/2  ==》 1/2*(loga + logb)相当于概率相乘然后开方)。
    • beam size过大会导致计算复杂度过高,时间复杂度为O(N*b*V),N为序列长度,b为beam size,v为词表大小
    • 语言模型通常为格式良好的文本分配高分,但较长文本的最高分往往是通用的、重复的和尴尬的。beam search的输出,与人讲话的概率分布,很不一样。

2.Stochastic Decoding

  • Sampling with temperature

解码器的输出层计算softmax时,通过改变T可以控制概率的形貌。当t大的时候,概率分布趋向平均,随机性增大(uniform sampling/pure sampling);当t小的时候,概率密度趋向于集中,即强者愈强,随机性降低(poisson distribution/greedy decoding)。
实验证明,降低t会改善生成的质量,但是会降低生成的多样性。
  • Top-k Sampling

从词表选择topk个词,使得概率之和最大,即

缺点:k的取值难以界定。k太小,会生成比较bland和generic的结果,即缺乏diversity;k太大,会退化成随机sampling(pure sampling),会陷入语义表达错误,即sample from tail distribution

  • Top-p Sampling(nucleus sampling)

丛词表选择概率之和大于给定阈值p的词,即

采样集的大小将根据每个时间步长的概率分布动态调整。对于高的阈值来说,这一个小部分的词汇,就占据了绝大多数的概率—-核。

三.Implementation

def top_k_top_p_filtering(logits, top_k=0, top_p=0.0, filter_value=-float('Inf')):
    """ Filter a distribution of logits using top-k and/or nucleus (top-p) filtering
        Args:
            logits: logits distribution shape (vocabulary size)
            top_k >0: keep only top k tokens with highest probability (top-k filtering).
            top_p >0.0: keep the top tokens with cumulative probability >= top_p (nucleus filtering).
                Nucleus filtering is described in Holtzman et al. (http://arxiv.org/abs/1904.09751)
    """
    assert logits.dim() == 1  # batch size 1 for now - could be updated for more but the code would be less clear
    top_k = min(top_k, logits.size(-1))  # Safety check
    if top_k > 0:
        # Remove all tokens with a probability less than the last token of the top-k
        indices_to_remove = logits < torch.topk(logits, top_k)[0][..., -1, None]
        logits[indices_to_remove] = filter_value

    if top_p > 0.0:
        sorted_logits, sorted_indices = torch.sort(logits, descending=True)
        cumulative_probs = torch.cumsum(F.softmax(sorted_logits, dim=-1), dim=-1)

        # Remove tokens with cumulative probability above the threshold
        sorted_indices_to_remove = cumulative_probs > top_p
        # Shift the indices to the right to keep also the first token above the threshold
        sorted_indices_to_remove[..., 1:] = sorted_indices_to_remove[..., :-1].clone()
        sorted_indices_to_remove[..., 0] = 0

        indices_to_remove = sorted_indices[sorted_indices_to_remove]
        logits[indices_to_remove] = filter_value
    return logits

# Here is how to use this function for top-p sampling
temperature = 1.0
top_k = 0
top_p = 0.9

# Get logits with a forward pass in our model (input is pre-defined)
logits = model(input)

# Keep only the last token predictions of the first batch item (batch size 1), apply a temperature coefficient and filter
logits = logits[0, -1, :] / temperature
filtered_logits = top_k_top_p_filtering(logits, top_k=top_k, top_p=top_p)

# Sample from the filtered distribution
probabilities = F.softmax(filtered_logits, dim=-1)
next_token = torch.multinomial(probabilities, 1)

四.Reference