FFM (Field-aware Factorization Machines)

一.简介

通过引入field的概念,FFM把相同性质的特征归于同一个field。FFM相对于FM加入了field的概念,每个特征的隐向量不再是只有一个,而是针对每个field学习一个独立的隐向量,防止互相影响

二.原理

连续特征,一个特征就对应一个Field (也可连续特征离散化,一个分箱成为一个特征);  离散特征,采用one-hot编码,同一种属性的归到一个Field。

以上文的表格数据为例,计算用户1的FFM组合特征:

算一下𝑦̂ 𝑣1,𝑓2的偏导

注意𝑥2,𝑥3,𝑥4是同一个属性的one-hot表示,即𝑥2,𝑥3,𝑥4中只有一个为1,其他都为0 (对于每个样本来说,同一个field下只有一个feature的值不是0,其他feature的值都是0)。在本例中𝑥3=𝑥4=0, 𝑥2=1,所以:

推广到一般情况:

𝑥𝑗属于Field 𝑓𝑗,且同一个Field里面的其他𝑥𝑚都等于0。实际项目中𝑥是非常高维的稀疏向量,求导时只关注那些非0项即可。

三.参考

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