CTR预估入门及各种模型介绍

学习和预测用户的反馈对于个性化推荐、信息检索和在线广告等领域都有着极其重要的作用。在这些领域,用户的反馈行为包括点击、收藏、购买等。本文以点击率(CTR)预估为例,介绍常用的CTR预估模型,试图找出它们之间的关联和演化规律。

机器不学习:CTR系列(1) CTR预估入门及LR介绍

数据特点

在电商领域,CTR预估模型的原始特征数据通常包括多个类别,比如[Weekday=Tuesday,Gender=Male, City=London, CategoryId=16],这些原始特征通常以独热编码(one-hot encoding)的方式转化为高维稀疏二值向量,多个域(类别)对应的编码向量链接在一起构成最终的特征向量。

机器不学习:CTR系列(1) CTR预估入门及LR介绍

高维稀疏多Field是输入给CTR预估模型的特征数据的典型特点。以下介绍的模型都假设特征数据满足上述规律,那些只适用于小规模数据量的模型就不介绍了。

Embedding表示

由于即将要介绍的大部分模型都或多或少使用了特征的embedding表示,这里做一个简单的介绍。

Embedding表示也叫做Distributed representation,起源于神经网络语言模型(NNLM)对语料库中的word的一种表示方法。相对于高维稀疏的one-hot编码表示,embedding-based的方法,学习一个低维稠密实数向量(low-dimensional dense embedding)。类似于hash方法,embedding方法把位数较多的稀疏数据压缩到位数较少的空间,不可避免会有冲突;然而,embedding学到的是类似主题的语义表示,对于item的“冲突”是希望发生的,这有点像软聚类,这样才能解决稀疏性的问题。

Google公司开源的word2vec工具让embedding表示方法广为人知。Embedding表示通常用神经网络模型来学习,当然也有其他学习方法,比如矩阵分解(MF)、因子分解机(FM)等。这里详细介绍一下基于神经网络的embedding学习方法。

通常Embedding向量并不是通过一个专门的任务学习得到的,而是其他学习任务的附属产出。如下图所示,网络的输入层是实体ID(categorical特征)的one-hot编码向量。与输入层相连的一层就是Embedding层,两层之间通过全连接的方式相连。Embedding层的神经元个数即Embeeding向量的维数(m)。输入层与Embedding层的链接对应的权重矩阵M(n×m),即对应n个输入实体的m维embedding向量。由于one-hot向量同一时刻只会有一个元素值为1,其他值都是0,因此对于当前样本,只有与值为1的输入节点相连的边上的权重会被更新,即不同ID的实体所在的样本训练过程中只会影响与该实体对应的embedding表示。假设某实体ID的one-hot向量中下标为i

i的值为1,则该实体的embedding向量为权重矩阵M的第i行。

机器不学习:CTR系列(1) CTR预估入门及LR介绍

1. LR

LR模型是广义线性模型,从其函数形式来看,LR模型可以看做是一个没有隐层的神经网络模型(感知机模型)。

机器不学习:CTR系列(1) CTR预估入门及LR介绍
机器不学习:CTR系列(1) CTR预估入门及LR介绍

LR模型一直是CTR预估问题的benchmark模型,由于其简单、易于并行化实现、可解释性强等优点而被广泛使用。然而由于线性模型本身的局限,不能处理特征和目标之间的非线性关系,因此模型效果严重依赖于算法工程师的特征工程经验。

为了让线性模型能够学习到原始特征与拟合目标之间的非线性关系,通常需要对原始特征做一些非线性转换。常用的转换方法包括:连续特征离散化、特征之间的交叉等。

连续特征离散化的方法一般是把原始连续值的值域范围划分为多个区间,比如等频划分或等间距划分,更好的划分方法是利用监督学习的方式训练一个简单的单特征的决策树桩模型,即用信息增益指标来决定分裂点。

特征分区间之后,每个区间上目标(y)的分布可能是不同的,从而每个区间对应的新特征在模型训练结束后都能拥有独立的权重系数。特征离散化相当于把线性函数变成了分段线性函数,从而引入了非线性结构。比如不同年龄段的用户的行为模式可能是不同的,但是并不意味着年龄越大就对拟合目标(比如,点击率)的贡献越大,因此直接把年龄作为特征值训练就不合适。而把年龄分段后,模型就能够学习到不同年龄段的用户的不同偏好模式。

离散化的其他好处还包括对数据中的噪音有更好的鲁棒性(异常值也落在一个划分区间,异常值本身的大小不会过度影响模型预测结果);离散化还使得模型更加稳定,特征值本身的微小变化(只有还落在原来的划分区间)不会引起模型预测值的变化。

特征交叉是另一种常用的引入非线性性的特征工程方法。通常CTR预估涉及到用户、物品、上下文等几方面的特征,往往单个特征对目标判定的贡献是较弱的,而不同类型的特征组合在一起就能够对目标的判定产生较强的贡献。比如用户性别和商品类目交叉就能够刻画例如“女性用户偏爱美妆类目”,“男性用户喜欢男装类目”的知识。特征交叉是算法工程师把领域知识融入模型的一种方式。

LR模型的不足在于特征工程耗费了大量的精力,而且即使有经验的工程师也很难穷尽所有的特征交叉组合。


CTR系列(1) CTR预估入门及LR介绍 我们讲到了利用LR训练CTR预估点击模型,LR的好处就是线性简单,速度快,容易debug,但是在特征组合和特征工程的过程中需要大量的经验。

既然特征工程很难,那能否自动完成呢?模型级联提供了一种思路,典型的例子就是Facebook 2014年的论文中介绍的通过GBDT(Gradient Boost Decision Tree)模型解决LR模型的特征组合问题。思路很简单,特征工程分为两部分,一部分特征用于训练一个GBDT模型,把GBDT模型每颗树的叶子节点编号作为新的特征,加入到原始特征集中,再用LR模型训练最终的模型。

机器不学习:CTR系列(2) CTR预估 LR + GBDT

GBDT模型能够学习高阶非线性特征组合,对应树的一条路径(用叶子节点来表示)。通常把一些连续值特征、值空间不大的categorical特征都丢给GBDT模型;空间很大的ID特征(比如商品ID)留在LR模型中训练,既能做高阶特征组合又能利用线性模型易于处理大规模稀疏数据的优势。

面简单的介绍一下该算法:

1.GBDT+LR 模型

首先,该模型不算是新的模型了,在一些大公司的ctr的模型中已经使用了。

机器不学习:CTR系列(2) CTR预估 LR + GBDT

如图就是该论文中提出的组合模型GBDT+LR,可以将GBDT看做是对特征一种组合编码的过程,最后的LR才是最终的分类(回归)模型。

1)数据的灌入,一般特征会有连续的和离散的,树模型还是更适合处理一下连续的特征(网上可以查询)。

方案一:

将连续的数据和离散的数据分开输入到GBDT中,最终使用的叶子进行编码,然后约定离散值和连续值的位置。

这过程中可以考虑只对连续值使用GBDT进行编码,而离散的特征就使用原本的onehot编码,最终拼接起来。完成特征的编码

机器不学习:CTR系列(2) CTR预估 LR + GBDT

方案二:

可以对离散的特征也进行GBDT编码,之后组合起来(参考GBDT+FFM这个里面改进),对离散型的数据新进行统计,

对于出现频次高的特征进行保留,过滤掉稀疏的少的特征值,这样就可以使用GBDT学习编码。

机器不学习:CTR系列(2) CTR预估 LR + GBDT

GBDT+FFM中就是这样处理的,但是那些离散的非异常值,其实仍可以使用onehot的形式进行编码,在最后一层中使用。

使用GBDT的组合作用,但是树形的组合是重复的,其一个特征可以在树的不同层中出现参与构造组合,这个要比FM

和FFM的组合要更深一些。

其编码的结果含有上下文的一些属性。在进行数据的输入,不是固定的,可以使用不同的输入方式,上面只是列举了两种比较

常见的方法,使用树形来进行编码。

2. NE(Normalized Entropy)归一化熵

使用NE(归一化熵)进行评估,

机器不学习:CTR系列(2) CTR预估 LR + GBDT

其中

机器不学习:CTR系列(2) CTR预估 LR + GBDT

,p是训练数据集的点击率,以此来消除不同训练集中的差异,这个公式就是在logloss损失

上添加了训练样本的影响,(在计算时应该注意y的范围是-1 和1 )

机器不学习:CTR系列(2) CTR预估 LR + GBDT

可以作为一种评价指标来使用,但是后来的论文中很少见有使用这种NE的。具体可以根据场景进行选使用。

3.Data freshness

使用新数据对模型进行更新,在实际的使用当中数据的分布是动态的,不是不变的,使用新数据来更新模型可以获得不错的

收益,文中指出GBDT树模型是每天更新,LR模型是实时更新的。以此来保持模型的准度。历史数据特征(统计型特征)对于

数据新鲜的变化不敏感,但是上下文特征就比较明显。这一点在很多机器学习模型中都会有实时或者近实时的更新模型,保证模型的能力。

4.Calibrate

这个校准不是所有都需要,一般我们在训练模型时,都会对样本进行采样,或是负采样等,这样会改变原来样本的数据分布,对于数据预测时的影响是很微弱的,但是对于像LR这种我们在得到预测的数据之后可能使用这个数据参与新的计算,就会出现偏差。为了解决这个偏差,就需要对模型的输出进行Calibrate(校准)。

机器不学习:CTR系列(2) CTR预估 LR + GBDT

其中p是模型预测出的正例的概率值,w是采样的比例w(是原始样本中正负的比例)一般是小数,来将模型的输出值校准到一个正常的数据。

小结:

GDBT+LR算是经典的CTR与预估模型,其使用了GBDT的非线性进行组合特征的学习,使用LR来学习特征的关联,最终预测出点击率。目前LR也仍是主流,只是输入的特征组合是使用其他的一些方式产出的,如FM,FFM,GBDT,DNN等。因此如何将原始的数据与这些模型结合得到最大的效果,仍需不断的去尝试,根据不同的场景去调节。

利用skitlearn做了一个简单的实现:

# 弱分类器的数目

n_estimator = 10

# 随机生成分类数据。

X, y = make_classification(n_samples=80000)

# 切分为测试集和训练集,比例0.5

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5)

# 将训练集切分为两部分,一部分用于训练GBDT模型,另一部分输入到训练好的GBDT模型生成GBDT特征,然后作为LR的特征。这样分成两部分是为了防止过拟合。

X_train, X_train_lr, y_train, y_train_lr = train_test_split(X_train, y_train, test_size=0.5)

# 调用GBDT分类模型。

grd = GradientBoostingClassifier(n_estimators=n_estimator)

# 调用one-hot编码。

grd_enc = OneHotEncoder()

# 调用LR分类模型。

grd_lm = LogisticRegression()

”’使用X_train训练GBDT模型,后面用此模型构造特征”’

grd.fit(X_train, y_train)

# fit one-hot编码器

grd_enc.fit(grd.apply(X_train)[:, :, 0])

”’

使用训练好的GBDT模型构建特征,然后将特征经过one-hot编码作为新的特征输入到LR模型训练。

”’

grd_lm.fit(grd_enc.transform(grd.apply(X_train_lr)[:, :, 0]), y_train_lr)

# 用训练好的LR模型多X_test做预测

y_pred_grd_lm = grd_lm.predict_proba(grd_enc.transform(grd.apply(X_test)[:, :, 0]))[:, 1]

# 根据预测结果输出

fpr_grd_lm, tpr_grd_lm, _ = roc_curve(y_test, y_pred_grd_lm)


FM(Factorization Machine)是由Konstanz大学Steffen Rendle(现任职于Google)于2010年最早提出的,旨在解决稀疏数据下的特征组合问题。下面以一个示例引入FM模型。假设一个广告分类的问题,根据用户和广告位相关的特征,预测用户是否点击了广告。源数据如下

机器不学习:CTR系列(3) CTR预估-FM模型

“Clicked?”是label,Country、Day、Ad_type是特征。由于三种特征都是categorical类型的,需要经过独热编码(One-Hot Encoding)转换成数值型特征。

机器不学习:CTR系列(3) CTR预估-FM模型

由上表可以看出,经过One-Hot编码之后,大部分样本数据特征是比较稀疏的。上面的样例中,每个样本有7维特征,但平均仅有3维特征具有非零值。实际上,这种情况并不是此例独有的,在真实应用场景中这种情况普遍存在。例如,CTR/CVR预测时,用户的性别、职业、教育水平、品类偏好,商品的品类等,经过One-Hot编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征,如商品的末级品类约有550个,采用One-Hot编码生成550个数值特征,但每个样本的这550个特征,有且仅有一个是有效的(非零)。由此可见,数据稀疏性是实际问题中不可避免的挑战。

One-Hot编码的另一个特点就是导致特征空间大。例如,商品品类有550维特征,一个categorical特征转换为550维数值特征,特征空间剧增。

同时通过观察大量的样本数据可以发现,某些特征经过关联之后,与label之间的相关性就会提高。例如,“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征,对用户的点击有着正向的影响。换句话说,来自“China”的用户很可能会在“Chinese New Year”有大量的浏览、购买行为,而在“Thanksgiving”却不会有特别的消费行为。这种关联特征与label的正向相关性在实际问题中是普遍存在的,如“化妆品”类商品与“女”性,“球类运动配件”的商品与“男”性,“电影票”的商品与“电影”品类偏好等。因此,引入两个特征的组合是非常有意义的。

因子分解机(Factorization Machines, FM)通过特征对之间的隐变量内积来提取特征组合,其函数形式如下:

机器不学习:CTR系列(3) CTR预估-FM模型

FM和基于树的模型(e.g. GBDT)都能够自动学习特征交叉组合。基于树的模型适合连续中低度稀疏数据,容易学到高阶组合。但是树模型却不适合学习高度稀疏数据的特征组合,一方面高度稀疏数据的特征维度一般很高,这时基于树的模型学习效率很低,甚至不可行;另一方面树模型也不能学习到训练数据中很少或没有出现的特征组合。相反,FM模型因为通过隐向量的内积来提取特征组合,对于训练数据中很少或没有出现的特征组合也能够学习到。例如,特征i和特征j在训练数据中从来没有成对出现过,但特征i经常和特征p成对出现,特征j也经常和特征p成对出现,因而在FM模型中特征i和特征j也会有一定的相关性。毕竟所有包含特征i的训练样本都会导致模型更新特征i的隐向量vi,同理,所有包含特征j的样本也会导致模型更新隐向量vj,这样⟨vi,vj⟩就不太可能为0。

在推荐系统中,常用矩阵分解(MF)的方法把User-Item评分矩阵分解为两个低秩矩阵的乘积,这两个低秩矩阵分别为User和Item的隐向量集合。通过User和Item隐向量的点积来预测用户对未见过的物品的兴趣。矩阵分解也是生成embedding表示的一种方法,示例图如下:

机器不学习:CTR系列(3) CTR预估-FM模型

MF方法可以看作是FM模型的一种特例,即MF可以看作特征只有userId和itemId的FM模型。FM的优势是能够将更多的特征融入到这个框架中,并且可以同时使用一阶和二阶特征;而MF只能使用两个实体的二阶特征。

机器不学习:CTR系列(3) CTR预估-FM模型

在二分类问题中,采用LogLoss损失函数时,FM模型可以看做是LR模型和MF方法的融合,如下图所示:

机器不学习:CTR系列(3) CTR预估-FM模型

FM是一种比较灵活的模型,通过合适的特征变换方式,FM可以模拟二阶多项式核的SVM模型、MF模型、SVD++模型等。

相比SVM的二阶多项式核而言,FM在样本稀疏的情况下是有优势的;而且,FM的训练/预测复杂度是线性的,而二项多项式核SVM需要计算核矩阵,核矩阵复杂度就是N平方。

相比MF而言,我们把MF中每一项的rating分改写为 ,从公式中可以看出,这相当于只有两类特征 和 的FM模型。对于FM而言,我们可以加任意多的特征,比如user的历史购买平均值,item的历史购买平均值等,但是MF只能局限在两类特征。SVD++与MF类似,在特征的扩展性上都不如FM,在此不再赘述。

总结一下:

# fm 相比 lr 引进了特征组合(二次项)

# fm 解决了数据稀疏性导致的参数训练不充分问题(尤其对于one-hot编码之后)


FFM(Field-aware Factorization Machine)最初的概念来自Yu-Chin Juan(阮毓钦,毕业于中国台湾大学,现在美国Criteo工作)与其比赛队员,是他们借鉴了来自Michael Jahrer的论文中的field概念提出了FM的升级版模型。

FFM(Field-aware Factorization Machine)模型是对FM模型的扩展,通过引入field的概念,FFM把相同性质的特征归于同一个field。例如,“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”这三个特征都是代表日期的,可以放到同一个field中。同理,商品的末级品类编码也可以放到同一个field中。

机器不学习:CTR系列(4) CTR预估-FFM模型

简单来说,同一个categorical特征经过One-Hot编码生成的数值特征都可以放到同一个field,包括用户性别、职业、品类偏好等。在FFM中,每一维特征xi,针对其它特征的每一种field fj,都会学习一个隐向量 vi,fj。因此,隐向量不仅与特征相关,也与field相关。假设样本的n个特征属于f个field,那么FFM的二次项有nf个隐向量。

机器不学习:CTR系列(4) CTR预估-FFM模型

FM可以看作FFM的特例,在FM模型中,每一维特征的隐向量只有一个,即FM是把所有特征都归属到一个field时的FFM模型。

为了使用FFM方法,所有的特征必须转换成“field_id:feat_id:value”格式,field_id代表特征所属field的编号,feat_id是特征编号,value是特征的值。数值型的特征比较容易处理,只需分配单独的field编号,如用户评论得分、商品的历史CTR/CVR等。categorical特征需要经过One-Hot编码成数值型,编码产生的所有特征同属于一个field,而特征的值只能是0或1,如用户的性别、年龄段,商品的品类id等。除此之外,还有第三类特征,如用户浏览/购买品类,有多个品类id且用一个数值衡量用户浏览或购买每个品类商品的数量。这类特征按照categorical特征处理,不同的只是特征的值不是0或1,而是代表用户浏览或购买数量的数值。按前述方法得到field_id之后,再对转换后特征顺序编号,得到feat_id,特征的值也可以按照之前的方法获得。

在训练FFM的过程中,有许多小细节值得特别关注。

第一,样本归一化。FFM默认是进行样本数据的归一化,即 pa.norm 为真;若此参数设置为假,很容易造成数据inf溢出,进而引起梯度计算的nan错误。因此,样本层面的数据是推荐进行归一化的。

第二,特征归一化。CTR/CVR模型采用了多种类型的源特征,包括数值型和categorical类型等。但是,categorical类编码后的特征取值只有0或1,较大的数值型特征会造成样本归一化后categorical类生成特征的值非常小,没有区分性。例如,一条用户-商品记录,用户为“男”性,商品的销量是5000个(假设其它特征的值为零),那么归一化后特征“sex=male”(性别为男)的值略小于0.0002,而“volume”(销量)的值近似为1。特征“sex=male”在这个样本中的作用几乎可以忽略不计,这是相当不合理的。因此,将源数值型特征的值归一化到 [0,1] 是非常必要的。

第三,省略零值特征。从FFM模型的表达式(4)可以看出,零值特征对模型完全没有贡献。包含零值特征的一次项和组合项均为零,对于训练模型参数或者目标值预估是没有作用的。因此,可以省去零值特征,提高FFM模型训练和预测的速度,这也是稀疏样本采用FFM的显著优势。

在训练FFM的过程中,有许多小细节值得特别关注。

  • 样本归一化:FFM默认是进行样本数据的归一化,即 为真;若此参数设置为假,很容易造成数据inf溢出,进而引起梯度计算的nan错误。因此,样本层面的数据是推荐进行归一化的。
  • 特征归一化:CTR/CVR模型采用了多种类型的源特征,包括数值型和categorical类型等。但是,categorical类编码后的特征取值只有0或1,较大的数值型特征会造成样本归一化后categorical类生成特征的值非常小,没有区分性。例如,一条用户-商品记录,用户为“男”性,商品的销量是5000个(假设其它特征的值为零),那么归一化后特征“sex=male”(性别为男)的值略小于0.0002,而“volume”(销量)的值近似为1。特征“sex=male”在这个样本中的作用几乎可以忽略不计,这是相当不合理的。因此,将源数值型特征的值归一化到 是非常必要的。
  • 省略零值特征:从FFM模型的表达式可以看出,零值特征对模型完全没有贡献。包含零值特征的一次项和组合项均为零,对于训练模型参数或者目标值预估是没有作用的。因此,可以省去零值特征,提高FFM模型训练和预测的速度,这也是稀疏样本采用FFM的显著优势。

总结一下:

# fm 相比 lr 引进了特征组合(二次项)

# fm 解决了数据稀疏性导致的参数训练不充分问题(尤其对于one-hot编码之后)

# ffm 增加了field,隐向量不仅与特征相关,也与field相关

# 假设样本的 n 个特征属于 f 个field,那么FFM的二次项有 nf个隐向量。

# 而在FM模型中,每一维特征的隐向量只有一个。

# FM可以看作FFM的特例,是把所有特征都归属到一个field时的FFM模型。


MLR算法是alibaba在2012年提出并使用的广告点击率预估模型,2017年发表出来。MLR模型是对线性LR模型的推广,它利用分片线性方式对数据进行拟合。基本思路是采用分而治之的策略:如果分类空间本身是非线性的,则按照合适的方式把空间分为多个区域,每个区域里面可以用线性的方式进行拟合,最后MLR的输出就变为了多个子区域预测值的加权平均。如下图(C)所示,就是使用4个分片的MLR模型学到的结果。

机器不学习:CTR系列(5) CTR预估-MLR算法
机器不学习:CTR系列(5) CTR预估-MLR算法

上式即为MLR的目标函数,其中m为分片数(当m=1时,MLR退化为LR模型);

机器不学习:CTR系列(5) CTR预估-MLR算法

是聚类参数,决定分片空间的划分,即某个样本属于某个特定分片的概率;

机器不学习:CTR系列(5) CTR预估-MLR算法

是分类参数,决定分片空间内的预测;μ和ww都是待学习的参数。最终模型的预测值为所有分片对应的子模型的预测值的期望。数据划分规则如下公式,特征分片数m=1时,退化为LR;上图MLR中m=4。m越大,模型的拟合能力越强,一般m=12。

机器不学习:CTR系列(5) CTR预估-MLR算法

MLR模型在大规模稀疏数据上探索和实现了非线性拟合能力,在分片数足够多时,有较强的非线性能力;同时模型复杂度可控,有较好泛化能力;同时保留了LR模型的自动特征选择能力。

MLR模型的思路非常简单,难点和挑战在于MLR模型的目标函数是非凸非光滑的,使得传统的梯度下降算法并不适用。相关的细节内容查询论文:Gai et al, “Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction” 。

另一方面,MLR模型可以看作带有一个隐层的神经网络。如下图,x是大规模的稀疏输入数据,MLR模型第一步是做了一个Embedding操作,分为两个部分,一种叫聚类Embedding(绿色),另一种是分类Embedding(红色)。两个投影都投到低维的空间,维度为m,是MLR模型中的分片数。完成投影之后,通过很简单的内积(Inner Product)操作便可以进行预测,得到输出y。

机器不学习:CTR系列(5) CTR预估-MLR算法

基础知识

优化方法:

1)剃度下降:

机器不学习:CTR系列(5) CTR预估-MLR算法

大小:一阶导数,方向:导数负方向。由目标函数的泰勒一阶展开式求得

2)牛顿法:

机器不学习:CTR系列(5) CTR预估-MLR算法

大小:一阶导数,方向:-海信矩阵的逆。由目标函数的泰勒二阶展开式求

3)拟牛顿法(LBFGS):牛顿方向通过约等替换,每个样本保存下面三个参数:delta x ,delta剃度 和p:

机器不学习:CTR系列(5) CTR预估-MLR算法

增量替换,计算牛顿方向D

机器不学习:CTR系列(5) CTR预估-MLR算法

LBFGS方法通过一阶导数中值定理,避免了计算海信矩阵(复杂度太大)。但是L1范数不能求导,所以需要OWLQN方法。

4)OWLQN:

(1)次梯度定义如下,

机器不学习:CTR系列(5) CTR预估-MLR算法

(2)不可导点取左or右次梯度,如下

机器不学习:CTR系列(5) CTR预估-MLR算法

直观解释,当你打算用左偏导时,说明是在负象限,因此要加上一个负值,使得更新之后参数更往负象限前进,这样就避免了跨象限;当打算用右偏导数时,说明在正象限,一次要加上一个正值,使得更新之后参数更往正象限前进,从而避免跨象限;否则,只能直接设置subgradient为0。

(3)象限搜索line search:

机器不学习:CTR系列(5) CTR预估-MLR算法

x不在0点时,line search在x_i所在象限搜索;如果模型参数在0点,就要在(2)次梯度约束的象限内进行line search.

MLR算法

机器不学习:CTR系列(5) CTR预估-MLR算法

算法公式如下:

0计算边界下降方向d:

机器不学习:CTR系列(5) CTR预估-MLR算法

1计算梯度大小:theta在0处不可导,取sign符号函数dij。

机器不学习:CTR系列(5) CTR预估-MLR算法

2计算最终下降方向p:

机器不学习:CTR系列(5) CTR预估-MLR算法

3象限内梯度下降,同OWLQN,line search:

机器不学习:CTR系列(5) CTR预估-MLR算法

paper介绍,MLR与LBFGS有三点不同:

1)OWLQN需要计算次梯度,MLR需要计算方向导数;

2)计算最终下降方向p时,MLR也要进行象限约束;

3)象限搜索line search,与OWLQN相似。

分布式框架实现

分布式

机器不学习:CTR系列(5) CTR预估-MLR算法

User特征共享

机器不学习:CTR系列(5) CTR预估-MLR算法

个人理解是为了加快运算速度,具体特征划分如下所示。其中,c是用户特征,nc是非用户特征。

机器不学习:CTR系列(5) CTR预估-MLR算法

实验结果

实验截图略,具体图表可以查看参考paper

机器不学习:CTR系列(5) CTR预估-MLR算法

纵坐标是内存使用率,特征共享技巧使速度提高了三倍。

参考文章:

Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction


像LR这样的wide模型学习特征与目标之间的直接相关关系,偏重记忆(memorization),如在推荐系统中,wide模型产生的推荐是与用户历史行为的物品直接相关的物品。这样的模型缺乏刻画特征之间的关系的能力,比如模型无法感知到“土豆”和“马铃薯”是相同的实体,在训练样本中没有出现的特征组合自然就无法使用,因此可能模型学习到某种类型的用户喜欢“土豆”,但却会判定该类型的用户不喜欢“马铃薯”。

WDL是Google在2016年的paper中提出的模型,其巧妙地将传统的特征工程与深度模型进行了强强联合。模型结构如下:

机器不学习:CTR系列(6) CTR预估-Wide&Deep

WDL分为wide和deep两部分联合训练,单看wide部分与LR模型并没有什么区别;deep部分则是先对不同的ID类型特征做embedding,在embedding层接一个全连接的MLP(多层感知机),用于学习特征之间的高阶交叉组合关系。由于Embedding机制的引入,WDL相对于单纯的wide模型有更强的泛化能力。

从tensorflow的文档找到的论文,没几页,看上去也不复杂,赶紧弄下来看看。

场景是Google Play的推荐

wide & deeplearning是什么鬼?

  • wide是指高维特征+特征组合的LR。LR高效、容易规模化(scalable)、可解释性强。但是泛化性需要在特征工程上下功夫
  • deep就是deep learning了。特征工程省力,但是容易过度泛化over-generalize。

Memorization 和Generalization

文中提了两个观点,有点意思。Memorization 和Generalization。

  • Memorization 。从现有的训练数据item或者特征的共现或者相关性。局部性(topical),跟用户有行为的item直接强相关。
  • Generalization。相关性的传递(transitivity),新特征组合。多样性(diversity)好一些。

有点类似I2i里的item-base方法效果好,user-base的方法新颖性好。

我自己之前的观点是机器学习某种程度上来说就是找“相似”,这种相似有时候比较直接(Memorization),有时候比较间接(Generalization)。意思其实差不多啦。

回顾LR和DL的问题

先介绍现有LR方法,特征通通0/1编码,然后做特征组合。老套路了,基本都这样。有个问题就是特征组合如果训练数据里面没有,那就没有信息了。其实也算是数据稀疏的问题。

embedding-based的方法,比如FM、DL,学习一个low-dimensional dense embedding向量。想起hash,可以把位数比较多的稀疏数据压缩到位数比较小的空间。当然,这样会有冲突发生。不过这里有点不同,学到是类似主题或者语义的东西,希望对于item是有“冲突”的,才能解决稀疏性问题。

特殊兴趣或者小众爱好的用户,数据是很稀疏,但embedding方法还是能得到很多其他nonzero的权重,也就是前面所说的over-generalize。LR就没这个问题,只直接记住这种数量很少的特征组合。

system overview

先retrieval粗筛,用machine-learning models和human-defined rules,不要觉得人工规则low,但是工业界就是需要啊。

再ranking精排。WDL就是用在这里。看看用了啥特征。

1. user features (e.g., country, language, demographics),

2. contextual features (e.g., device, hour of the day, day of the week) 像余额宝、阿里音乐那个比赛都用了时间特征啊。

3. impression features (e.g., app age, historical statistics of an app).

  • activation function 用的是ReLu
  • 输入居然是字符串(e.g., “language=en”) ,向量怎么embedding没细说,估计是k-Shingling吧

wide & deeplearning上场

机器不学习:CTR系列(6) CTR预估-Wide&Deep

看图就明了。中间那个就是了。

一些细节

* 模型的目标是app安装。

* 对比join training和ensemble。ensemble是disjoint的。join training可以一起优化整个模型。突然想到一个问题,之前一直对DL抱有歧视,觉得这玩意拟合非线性还不如xgboost来得简单直接。没注意DL的优势:学习embedding表达,可以并行训练(不用一棵树一棵树地来)。

* 训练时候LR部分是FTRL+L1正则,我还以为FTRL只能用在online learning呢。DL用的AdaGrad

* 训练数据有5000亿??把一个pv的每个app当作一条数据倒是有可能。

* 训练的时候不会从头开始,用之前的模型作为初始模型。难怪用FTRL。模型上线前会dry run一下。习惯很好。

* 连续值先用累计分布函数CDF归一化到[0,1],再划档离散化。这个倒是不错的trick。

效果咋样

机器不学习:CTR系列(6) CTR预估-Wide&Deep

离线评估auc提升不大,取了1%的用户在线评估,效果比较好。 奇怪了,解释是说离线数据是fixed的,在线能学新的用户responses。我脑补一下,就是说你的模型效果好了,影响前面用户的点击,进而影响app的实时统计特征,最后影响后面的效果?不然就是因为排序结果变了,影响用户的点击,离线不能反映真实的用户行为。比如原来模型把差一点的排上来,导致用户安装了。你把更好的排上了反而预测错了。

总之,线上有效果最重要,理由可以慢慢编。另外就是离线评估没提升也不要轻易放弃,成功可能就跟你擦肩而过。仔细想想,离线评估确实有坑。

 

推荐文章

沪公网安备 31010702002009号