点击率预估算法survey之FTRL

发表于 | 分类于 |

论文主要内容

参考的paper是。文章中给出了可以工程化的实践。

在LR算法训练中，在第t个instance上的logloss为

​ $logloss_t(w_t) = -y_tlog p_t - (1-y_t)log(1-p_t)$

其中$w_t$是训练当前这轮的权重，$y_t$是label，$p_t$是预估的结果，即sigmoid函数的计算结果。一般$y_t$是0或者1。因此这个公式可以简化为

​ $$ logloss_t(w_t)= \begin{cases} -log(1-p_t), & \text {if $y_t=0$} \ -logp_t, & \text{if $y_t=1$} \end{cases} $$

从而推倒出的gradient为

$g = (p_t-y_t)x_t$，而instance在预处理之后对应的$x_t$一般是libsvm的数据格式，即$featid:1$，所以$x_t$的值一般是1，因此这里可以等价为$g = p_t-y_t$。

在FTRL算法中，这个是$g$是迭代的主要变量。$n,z$均是基于这个$g$进行构建。

Online Gradient Descent(OGD)被证明是有效的，但是不不擅长产出sparse模型。而在具体的线上服务，计算pctr的时候，sparsity决定了服务性能；并且简单的对logloss增加$L_1$正则化参数并不能非常有效的产出0值权重；

像FOBOS类似的复杂算法是简单粗暴的砍掉接近0值的权重以产生sparsity。

RDA算法在sparsity和accuracy之间取的平衡，而google提出的FTRL算法比RDA有更好的效果(更sparse的基础上更有accuracy)。

当没有正则化参数时候，FTRL算法等价于OGD，但是FTRL中使用了称为lazy representation of model coefficient $w$，因此实现$L_1$正则上更有效率。

对所有coordinate设置相同的学习率并不是很理想的。因此文章提出来per-coordindate learning rate。

这里贴出完整的ftrl算法

ftrl算法

一般的实现上严格按照这里的表达式进行计算即可。在具体的实践中有几个trick：

第一个即sigmoid函数结果有个上限。

return 1.0 / (1.0 + math.Exp(-math.Max(math.Min(w, 35), -35)))

即累加值$\sum(w*x)$设置在$[-35, 35]$之间即可。

工程实现

这里使用python以及golang分别实现ftrl算法。使用的数据下载自kaggle的train、test数据。大部分逻辑是参考以github相关开源的实现。记录下来供参考。

数据的格式为csv的格式，我下载的数据内容为这里avazu点击数据，压缩后数据大小为1G多，包含有40428968行。这里给出具体的实现内容并分

析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

from csv import DictReader 
from math import exp, log, sqrt
from datetime import datetime

import sys

D = 2 ** 20

train="../py-ftrl-kaggle/small.csv"
train = sys.argv[1]

### since the date in data is 21-30
### then if date = 30, then take it as the validate data to calc the logloss
holdafter = 9
holdout = 100

class FTRL:
    ## l1, l2
    def __init__(self, l1, l2, alpha, beta, epoch, interaction):
        self.n = [0.] * D
        self.w = {}
        self.z = [0.] * D

        self.l1 = l1
        self.l2 = l2
        self.epoch = epoch
        self.interaction = interaction

        self.alpha = alpha
        self.beta = beta


    def data(self, file, D):
        for t, row in enumerate(DictReader(open(file))):
            ID = row["id"]

            ## delete row["id"] for memory saving
            del row["id"]

            y = 0.
            if "click" in row and row["click"] == "1":
                y = 1.

            ## delete row["click"] for memory saving
            del row["click"]

            ## data oriented, the train data use day 21-30 for train
            date = int(row["hour"][4:6])
            date -= 20

            ## write useful hour data
            row["hour"] = row["hour"][6:]


            ## for each value ,generate its index
            x = []
            for key in row:
                value = row[key]

                index = abs(hash(key + "_" + value)) % D
                x.append(index)
                
            
            yield t, date, ID, x, y



    ## for instance x, produce cross feature if need interaction
    def fullindex(self, x):
        
        ## for bais index
        yield 0

        for index in x:
            yield index

        ## if support interaction
        if self.interaction:
            l = len(x)
            x = sorted(x)
            for i in xrange(l):
                for j in xrange(i+1, l):
                    yield abs(hash(str(x[i]) + "_" + str(x[j]))) % D


    ## handle one instance x
    def predict(self, x):
        wtx = 0.
        z = self.z
        n = self.n

        a = self.alpha
        b = self.beta
        l1 = self.l1
        l2 = self.l2
        
        w = {}

        wtx = 0
        ## maybe has cross feature
        for i in self.fullindex(x):
            sign = -1. if z[i] < 0 else 1.

            if sign * z[i] <= l1:
                w[i] = 0.
            else:
                w[i] = (sign * l1 - z[i])/((b + sqrt(n[i]))/a + l2)
        
            wtx += w[i]

        ## get updated w
        self.w = w

        return 1. / (1. + exp(-max(min(wtx, 35.), -35.)))

    ## for instance x, calculate the p 
    ## using g to update n and z
    def update(self, x, p, y):
        a = self.alpha
        b = self.beta
        n = self.n
        z = self.z

        w = self.w

        ## here actually g = (p - y) * x, and x here is 1.
        g = p - y

        ## if has interaction, update the n and z for cross features
        for i in self.fullindex(x):
            sigma = (sqrt(n[i] + g*g) - sqrt(n[i]))/a
            z[i] = z[i] + g - sigma * w[i]
            n[i] = n[i] + g * g


    ## hope the p in the gap [10e-15, 1-10e-15]
    def logloss(self, p, y):
        p = max(min(p, 1. - 10e-15), 10e-15)
        return -log(p) if y == 1 else -log(1. - p)

    def run(self):
        start =  datetime.now()
        learner = FTRL(l1=1., l2=1., alpha=0.1, beta=1., epoch=1, interaction=False)

        logcount = 0
        totalloss = 0.
        for t, date, ID, x, y in self.data(train, D):

            p = self.predict(x)
            #print "p:", p

            ## date is 1-10
            if date > holdafter:
                print "date:",date,"holdafter:",holdafter
                logcount += 1
                loss = self.logloss(p, y)
                totalloss += loss

            else:
                self.update(x, p, y)

        if logcount != 0:
            print "avg logloss:", totalloss / logcount, \
                    "logcount:", logcount,\
                    "time elapsed:", datetime.now() - start
def main():

    ftrl = FTRL(l1=1., l2=1., alpha=0.1, beta=1., epoch=1, interaction=False)
    ftrl.run()

## run
main()

我们跑了10w个数据，结果如下：

1
2
3
date: 10 holdafter: 9
date: 10 holdafter: 9
avg logloss: 0.160171832485 logcount: 2 time elapsed: 0:00:07.045008

这里需要说明，date这一列的数据形式为14102100，即YY-MM-DD-HH，其中Hour设置为0，train数据中日期的分布是1021-1030。这里我们取出date后再减去20，得到的日期范围为1-10。其中10我们不参与训练，而是用在计算logloss上，作为model的validate。

代码初始花，我们设置了$n,z$两个变量用来存储训练中的迭代变量。

$x$对于一行instance，读取文件后，基于hash() %D，作为这列特征值的id，并以这个id作为索引在$n,z$中读写。

其中提供的fullindex(self, x)是基于原始$x$，构建cross特征的id。代码中设置任何两个变量之间进行cross。当然这里没有做太多的特征工程，只是简单的cross了所有特征。

如果interaction=False，那么训练的还是原始数据instance。

predict以及update严格按照google的paper中给出的算法

结语

相对于之前使用的LBFGS，或OWLQN，最大的不同是以前的的算法会严格提出stopping criterion。但是FTRL并没有这么做。我理解，首先作者已经给出了证明，这个算法是必然收敛的；其次这里给出的是简单的遍历所有instance进行train，实际的工程使用中，可能有其他的策略变化，这里待补充实际的工业实践。