达观数据：推荐算法深入浅出之逻辑回归
谈及机器学习或推荐算法，不得不提⼊门级的逻辑回归算法。但我们真的掌握逻辑回归了么？不妨回答⼀下以下问题：
1. 逻辑回归的代价函数以及公式推导，
2.批量梯度下降和随机梯度下降的差 异，
3. 样本太⼤，导致特征编码耗时太长怎么办，
4. 如何优化随机梯度下降使得算法⼜快⼜准。
如果你对上述问题⼼⾥没底不妨读下这篇⽂章。本⽂分为四个部分，第⼀部分介绍逻辑回归算法的推导过程，以便理解算法背后的理论基础；第⼆部分介绍逻辑回归的实现细节 ，包含特征散列的技巧以及学习率⾃适应，使得算法能够⽀撑更⼤的数据集。第三部分简单的安利⼀波逻辑回归的⼯业级实现⼯具Vowpal Wabbit，最后⼀部分分享⼀些在学习逻辑回归过程中的思考。
1
逻辑回归的理论推导
这部分的理论推导需要⼀些数学中的微积分和统计学的知识。我们分为三步，由浅⼊深的介绍。先从简单的⼀元线性回归⼊⼿（⾼中数学知识），再扩展到多元线性回归，最后延伸到逻辑回归。
一元线性回归
在⾼中时期，我们经常会碰到这样⼀道数学题：某⼩卖部为了了解热茶的销售量与⽓温之间的关系，随机统计了6天卖出热茶的杯数与当天⽓温的对照表(如下表)，如果某天的⽓温是-5℃，你能根据这些数据预测这天⼩卖部卖出热茶的杯数吗？
这是⼀道典型的求线性回归⽅程的问题。⽼师指导我们按照以下三步来解题：
1. 画出⽓温
2. 按照如下公式求解线性回归⽅程中的两个参数：斜率
3. 根据线性回归⽅程
三步流程⾛完，基本这题已经答完了。但是对于斜率a和截取b的公式由来我们不⼀定知道。这⾥简要提⼀下，具体的推导过程见⽂末。本题的⽬的是构造线性回归⽅程
TIPS
欧式距离是指m维空间中两个点之间的真实距离。这其实就是观察点(xi,yi)和直线上的点
所以最终的问题就转换成求解a,b使得代价函数
多元线性回归
我们知道数学题⽬是对现实问题的⼀种简化，就像上述⼩卖部卖热⽔的问题。现实中卖出的热⽔杯 数不仅和当天的⽓温温度有关，可能还有热⽔的温度，是否加茶叶等等。也就是影响⼩卖部卖出热⽔杯数y由多个因素x1,....xn决定，其中x1表⽰当天⽓温，x2表⽰热⽔温度，x3表⽰是否加茶叶
等。此时该问题就由⼀元线性回归问题变成了多元线性回归问题。其⽬的和之前⼀样：构造线性回归⽅程
这⾥为了⽅便，将参数a1,....am, b合并成向量形式
对于多元线性回归问题的求解就变成了找到参数w使得代价函数
过拟合vs⽋拟合:
过拟合是指模型把数据学习的太彻底，以⾄于把噪声数据的特征也学到了。体现在建模过程 是训练时误差很⼩，测试的时候误差很⼤。通俗的讲就是泛化能⼒弱。⼀般有如下解决⽅案：
1. 重新清洗数据，清除噪声特征
2. 增⼤数据的训练量
3. 采⽤正则化⽅法
4. 采⽤dropout⽅法。该⽅法在神经⽹络中常⽤，就是在训练是让神经元以⼀定的概率不⼯作
⽋拟合是指模型没有很好的捕捉到数据的特征，不能很好的拟合数据。⽐如散点图显⽰数据 是⾮线性的关系，如果此时还是⽤线性⽅程去拟合的话，就会造成⽋拟合的情况。⼀般针对 ⽋拟合有如下解决⽅案：
1. 添加其他特征项，⽐如特征交叉
2. 添加多项式特征，⽐如添加某个特征⼆次项，三次项等
3. 减少正则化参数。
逻辑回归
逻辑回归全称叫对数⼏率回归，英⽂为 logistic regression 或 logit regression 。之所以逻辑回归叫对数⼏率回归，是因为逻辑回归是对数⼏率函数和线性回归的强强组合。对数⼏率函数（logistic function）
回归vs分类:
回归模型和分类模型本质是⼀样的，差异在于模型的输出，回归模型输出的是连续数据，⽽ 分类模型输出的是离散数据。当然这样的理解：分类模型就是将回归模型的输出离散化也是 合理的。⽐如线性回归模型与逻辑回归模型，⽀持向量回归（SVR）和⽀持向量机（SVM） 等。
对于给定⼀组信号向量
这⾥
TIPS:
我们说逻辑回归是⼀个线性分类器，是因为它的决策边界是以输⼊信号的线性组合。举例来说，当阈值取0.5时，模型判断⼀组信号 xi输⼊为正例y=1 ，等价于
对于逻辑回归模型的求解，也就是信号权重w ，这个⽆法使⽤和线性回归模型相同的最⼩均⽅误差MSE ，因为根据最⼩均⽅误差计算的代价函数是⾮凸的，所以可能在寻优时容易陷⼊局部最优，也 就是⽆法找到权重w使得代价函数Cost(w)全局最⼩。
TIPS
对于凸函数⽽⾔有⼀个⾮常重要的性质：局部最⼩值就是全局最⼩值。这就是构建的代价函 数要是凸函数的原因，⽽且这样也⽅便使⽤梯度下降算法求解全局最优解。
这⾥我们使⽤最⼤似然估计(这⾥也可以⽤信息熵)构建如下代价函数
该代价函数也叫做对数损失（这⾥log的底数默认为e）。因为该函数是凸函数(证明过程)，我们可以使⽤梯度下降算法求解最优解。根据代价函数Cost(w)的偏导数不断迭代更新即可求解出代价函数 取得最优解时的权重w*（具体的偏导数推导过程见⽂末）。
从最后⼀个表达式我们可以看出要求解的权重向量w中的值wj和输⼊向量xi中的xij相关。在多元线性回归中，权重wj的解释是相关的信号量xij每增加⼀个单位，预测的结果将会增加wj。⽽在逻辑回归模型中，权重wj的解释是相关信号量xij每增加⼀个单位，它将使结果为1的事件发⽣⽐加
TIPS:
在统计和概率理论中，⼀个事件的发⽣⽐是指该事件发⽣和不发⽣的⽐率，公式就是
对数⼏率就是对⼏率取对数
优化算法
在⼀元线性回归问题中，我们只有⼀个⾃变量，⽽观察的数据肯定⼤于⾃变量的个数，所以我们始 终能够求解出结果。⽽在多元线性回归问题中，虽然我们通过置代价函数的偏导数为0求得
图中黄⾊的路线表⽰批量梯度下降，蓝⾊的路线表⽰随机梯度下降，绿⾊的路线表⽰⾃适应的随机 梯度下降算法。
批量梯度下降Batch Gradient Descent
批量梯度下降的迭代公式如下：
在每⼀次的迭代，也就是登⼭者每次确定⽅向的时候，批量梯度下降算法会使⽤全部的训练样本， 从⽽得到⼀个当前能最快到最优解的地⽅，也就是登⼭者能当前能最快下⼭的⽅向。接着按照确定 的步长
随机梯度下降Stochastic Gradient Descent
随机梯度下降的迭代公式如下：
在每⼀次的迭代时候，随机梯度下降算法只通过⼀个样本就完成了⽅向的确定，接着按照确定的步长
图中还有⼀条绿⾊的线路表⽰⾃适应随机梯度下降算法。之所以有⾃适应这步的优化是因为批量梯 度下降算法和随机梯度下降算法都是使⽤确定的步长，这就导致了初始时该步长太⼩，要⾛好⼏步 才有明显的代价损失减少；⽽靠近最优解时步长太长，经常会错过最优解。⾃适应算法是为了让梯 度下降算法在开始时⼤步向前迈，在靠近最优解时采⽤⼩碎步。⾄于如何实现⾃适应将在下章实现 技巧中介绍。
02
LR的实现技巧
俗话说得好：理想很丰满，现实很⾻感。在掌握了上述关于逻辑回归算法的理论基础以及权重求解后，我们的确可以构建⼀个逻辑回归模型来解决实际问题。但是要想使模型更加健壮⾼效，还需要学习两个技巧，⼀个是将散列技巧⽤在信号表⽰上，这样可以为前期的预处理节省⾮常多的时间；另⼀个是使⽤⾃适应步长来加快收敛以及降低因为步长太⼤导致在最优解附近锯齿震荡的现象。
散列
在我们预处理逻辑回归的数据时经常采⽤one-hot序列编码的⽅式，简单来说就是将训练样本中出现过的每个特征按照顺序递增编号。这样有个⾮常明显的问题就是训练时要⽣成⼀个特征名到特征序号的映射表，并且要将这个映射表传递给预测阶段的特征预处理。这个映射表在数据样本很⼤或者数据结构设计不好时就会⾮常浪费时间。其次有些频次很低的特征置信度不⾼，特别像⼀些异常数据（⽤户年龄100多岁等），单独出现对模型⽆益。⽽通过散列的⽅式，只要训练和预测时的散列 算法⼀致，那么对于同⼀特征的编码结果也将⼀致，也就是数据⼀致性以及预处理的速度将⼤⼤提 升，特别是针对极⼤规模特征和在线学习的情况。
那么怎么使⽤散列呢？⽐较常见的⽤法是将特征名散列到int64的整数，然后再取模m。⼤家可能会 担⼼散列可能会发⽣碰撞，⽽模m后使得碰撞的概率更⼤了。这⾥要以vowpal wabbit⾥举例，它有⼀个参数 -b 代表掩码mask的位数，默认取18，最⼤到61。每个特征号的计算⽅式是
相较于one-hot序列编码，散列技巧不需要预先维护⼀个特征映射表，使在线学习更⽅便，⽽且⼤⼤ 降低了模型训练的时间和空间上的复杂度。对于它的不⾜也有⼀些针对的”补丁”。⽐如为解决散列 的冲突引⼊了命名空间的概念，在不同命名空间中的特征序号不会发⽣冲突；还将特征空间的⼤⼩ 作为模型参数，通过观察损失函数来调节该参数。还⽐如为解决原特征反推难的问题，vowpal wabbit中⽣成命令 vw-varinfo 来展⽰所有的原特征，散列值，取值范围，权重等模型信息。
自适应
⾃适应梯度下降算法在上⼀章节介绍过，并且⽤绿⾊的线路演⽰了算法的优化过程。其关键就是对步长
从梯度下降的迭代公式中我们可以看出每个模型参数，也就是权重wj只和对应维度的信号量xij相 关，与其他维度⽆关。⽽我们期望的步长，也就是学习率
其中
上⾯两个关于逻辑回归的技巧到底有没有⽤呢？tinrtgu在参加kaggle⽐赛Display Advertising Challenge时使⽤这两个技巧的逻辑回归超过了基准线（不是第⼀名，第⼀名⽤的是FFM⽅法）。这 是⼀个⼴告CTR预估的⽐赛，由知名⼴告公司Criteo赞助举办。数据包括4千万训练样本，500万测 试样本，解压缩以后，train.txt⽂件11.7G，test.txt⽂件1.35G。特征包括13个数值特征，26个类别 特征，评价指标为logloss。该程序只使⽤了200M内存，在tinrtgu机器上跑了⼤约30分钟。这⾥将 其⼤概50⾏的代码贴出来并详细注解⼀下。
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE Version 2, December 2004
Copyright (C) 2004 Sam Hocevar
<sam@hocevar.net>
Everyone is permitted to copy and distribute verbatim or modified copies o f this license
document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO. '''
from datetime import datetime
from csv import DictReader
from math import exp, log, sqrt
#变量定###########################################
train = 'train.csv' # 训练⽂件路径 test = 'test.csv' # 测试⽂件路径
D = 2 ** 20 # 特征维度，维度固定是因为会使散列技巧
alpha = .1 # 随机梯度下降算法的初始学习率
# 函数定义###############################################
# A. 对数损失函数 $y_{i} \log p(y=1|\mathbf{x}_i) + (1-y_i)\log p(y=0|\mathb f{x}_i)$
# 输⼊参数:
# p: 预测值
# y: 真实值
# 输出：
# 预测值和真实值之间的对数损失
def logloss(p, y):
p = max(min(p, 1. -10e-12), 10e-12)
return -log(p) if y == 1.else -log(1.-p)
# B. 应⽤散列技巧将样本编码成one-code
# hash(特征名,特征值)：0/1
# 输⼊参数:
# csv_row: 单个样本数据, ⽐如: {'Lable': '1', 'I1': '357', 'I2': '', ...}
# D: 样本空间的维度，散列的模
# 输出:
# x: 特征索引列表，其对应的值都是1
def get_x(csv_row, D):
x = [0] # 偏差b的位置0都有
for key, value in csv_row.items():
index = int(value + key[1:], 16) % D # 散列函数（⽐较弱，可以优化）
x.append(index)
return x
# C. 对数⼏率函数 p(y = 1 | x; w)
# 输⼊参数:
# x: 特征列表
# w: 权重列表
# 输出:
# 给定特征和权重，预测为1的概率
def get_p(x, w):
wTx = 0.
for i in x:
wTx += w[i] * 1. # x中所有index对应的特征值都是1 return 1. / (1. + exp(-max(min(wTx, 20.), -20.))) # 带边界的sigmod函数
# D. 更新模型
#输⼊参数:
# w: 权重列表w
# n: 特征出现次数列表，⽤于⾃适应学习率
# x: 样本-特征索引列表
# p: 当前模型对样本x的预测值
# y: 样本x的标签
# OUTPUT:
# w: 更新的模型
# n: 更新的特征出现次数列表
def update_w(w, n, x, p, y):
for i in x:
# alpha / (sqrt(n) + 1) 是⾃适应的学习率 # (p - y) * x[i] 是当前下降梯度
w[i] -= (p - y) * alpha / (sqrt(n[i]) + 1.) n[i] += 1.
return w, n
# 训练和测试 ####################################
# 初始化模型参数 w = [0.] * D # 权重列表 n = [0.] * D # 特征出现次数列表
# 训练数据
loss =0. # 累计损失
for t, row in enumerate(DictReader(open(train))):
y = 1. if row['Label'] == '1' else 0.
del row['Label'] # 已经转换成y
del row['Id'] # 不需要Id信息
# 主要的训练过程
# S1: 获取散列后的特征索引列表
x = get_x(row, D)
# S2: 计算当前模型对当前样本的预测值
p = get_p(x, w)
# 过程中打印训练的样本数和累计损失
loss += logloss(p, y)
if t % 1000000 == 0 and t > 1:
print('%s\tencountered: %d\tcurrent logloss: %f' % (
datetime.now(), t, loss/t))
# S3: 更新模型参数
w, n = update_w(w, n, x, p, y)
#测试
with open('submission1234.csv', 'w') as submission:
submission.write('Id,Predicted\n')
for t, row in enumerate(DictReader(open(test))): Id = row['Id'] del row['Id']
x = get_x(row, D)
p = get_p(x, w)
submission.write('%s,%f\n' % (Id, p))
3
LR的⼯业级实现Vowpal
Wabbit
本来这⼀章节准备详细介绍⼀下Vowpal Wabbit的⽤法的，但是考虑到官⽅提供的wiki（https://github.com/VowpalWabbit/vowpal_wabbit/wiki）已经⾮常详细 了，从安装到使⽤，从输⼊格式到算法细节，从命令参数说明到服务搭建，基本上能⽀撑我们把 vowpal wabbit⽤到如臂使指。唯⼀美中不⾜的是⽂档完全是英⽂的，后续会结合它的源码学习（https://doc.haojunyu.com/vw2.3/）尝试做⼀些翻译（https://book.haojunyu.com/vw_practise/）⼯作。所以这章节主要介绍⼀下为啥选择vowpal wabbit作为逻辑回归⼯业级的⼯具。
⾸先，vowpal wabbit在使⽤逻辑回归算法上⾮常专业。该开源项⽬是由雅虎发起，⽬前是由微软研 究院维护的⼀个快速核外学习系统。虽然它⽬前的定位是在线的机器学习系统，涉及在线服务，散 列，交互学习等，但是它最初就是以线性回归为初始版本（2.3），后来⽀持了逻辑回归并加⼊了更 多的优化算法，像L-BFGS，FTRL等。所以通过它的源码能完全掌握逻辑回归的算法理论和⼯程实践。其次，vowpal wabbit⾮常⾼效和内存消耗⼩。⼀⽅⾯它是⽤C++编码，代码运⾏⾮常快，另⼀⽅⾯它⽤⾼效且消耗内存少的L-BGFS优化算法，使得其在性能⽅⾯表现极佳。这⼀点在tinrtgu的样 例中能够体现出来，⽽且vowpal wabbit能够⽐他做得更好。最后，vowpal wabbit是便捷易⽤的。它不仅⽀持命令⾏的形式来使⽤，还⽀持python使⽤，⽽且提供了像 vw-varinfo 等便捷的⼯具类 脚本。
4
思考与总结
1. 快速的迭代 vs 缓慢的精确
从上⾯优化算法的⽐对中，我们可以看出随机梯度下降⽐批量梯度下降占有很⼤的优势，基本 上⼯程的实现都会优先考虑随机梯度下降，因为训练时间短，占⽤内存⼩，能够快速的迭代更 新模型参数。⽽批量梯度下降的训练时间和样本的数量成正⽐的，随着样本规模的扩⼤，批量 梯度下降的训练时间终究会超出项⽬的忍耐限度。所以相较于缓慢精确的算法，快速迭代的算 法更符合现在这个⼤数据时代。就像吴恩达在新书《机器学习训练秘籍》所说“不要在⼀开始就 试图设计和构建⼀个完美的系统。相反，应尽可能快(例如在短短 ⼏天内)地构建和训练⼀个系 统雏形。然后使⽤误差分析法去帮助你识别出最有前景的⽅向，并据此不断迭代改进你的算 法。”
2. 是否使用散列
3. 逻辑回归中的特征⼯程是否尽量离散化
在实际项⽬中，特征的数据类型不仅有离散型，还有连续型。在⼯业界，很少直接将连续值作 为特征直接丢给逻辑回归模型，⽽是将连续特征离散化，这样有如下优点：⾸先，离散化的特 征对异常数据有很强的鲁棒性，也就是当我们将年龄>60当做⽼年⽤户时，年龄=200岁的异常 数据不会给模型带来很⼤影响。其次，将年龄从1维扩展为幼⼉，青年，壮年，⽼年4维，每个 维度都有单独的权重，相当于为模型引⼊了⾮线性，提⾼模型的表达能⼒，交叉特征也是相同 的道理。最后特征的离散化会使模型更加稳定，⽐如在推荐项⽬中会使⽤item的实时ctr这⼀特 征，它能在⼀定程度上反映出item在⽤户群体中的受欢迎程度，所以我们可以给ctr分段来降低 实时ctr带来的受欢迎程度的影响。
4. 逻辑回归的优与劣
逻辑回归算是机器学习中最简单的模型，可解释性好，特征的权重⼤⼩清楚的表现了特征的重 要性，此外⼯程上容易实现，训练耗时短。以上都是逻辑回归的优点。逻辑回归最⼤的缺点是 ⾮常依赖特征⼯程，⽽且特征⼯程基本决定了模型的好坏。这也解释了tinrtgu参加的⽐赛中是 FFM算法取得了第⼀名，同样也解释了Facebook会使⽤GBDT来筛选特征，LR来模型训练，毕 竟⼈⼒有时尽。
本⽂主要介绍了逻辑回归的理论推导以及⼯程实践技巧。理论推导部分从⼀元线性回归延伸到多元 线性回归，最终升级为逻辑回归。此外还着重介绍了它的优化算法。⽽⼯程实践技巧主要介绍了散列技巧以及⾃适应的随机梯度下降算法，最后还展⽰了⼀个50⾏左右实现全部技巧的代码。在本⽂ 的最后安利了⼀波vowpal wabbit软件以及在学习逻辑回归过程中的⼀些思考。
附：推导的过程
参考文献
1.基于Vowpal_Wabbit的⼤规模图像分类：https://www.academia.edu/31836831/基于Vowpal_Wabbit的大规模图像分类
2.Vowpal Wabbit GitHub主页：https://github.com/VowpalWabbit/vowpal_wabbit
3.Deep Dive Into Logistic Regression ：http://www.philippeadjiman.com/blog/2017/12/09/deep-dive-into-logistic-regression-part-1/
4. 逻辑回归代价函数凸证明 ：http://qwone.com/~jason/writing/convexLR.pdf
5. 梯度下降_wiki ：https://zh.wikipedia.org/wiki/梯度下降法
6. 散列技巧的冲突分析 ：http://people.csail.mit.edu/romer/papers/TISTRespPredAds.pdf
7. ⾃适应学习 ：http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41159.pdf
8. 逻辑回归实战 ：https://www.kaggle.com/c/criteo-display-ad-challenge/discussion/10322
9. vowpal wabbit源码阅读 ：https://doc.haojunyu.com/vw2.3/
10. vowpal wabbit帮助⽂档 ：https://github.com/VowpalWabbit/vowpal_wabbit/wiki
11. vowpal wabbit帮助⽂档(翻译中)：https://book.haojunyu.com/vw_practise/
BOUT
关于作者
郝俊禹：达观数据高级技术专家，负责达观数据资讯流推荐效果的优化，对推荐系统的架构以及推荐算法有一定的研究。喜欢和海量的数据，简明的架构，高效的算法，明确的指标打交道。
相关阅读