机器学习算法原理及其Python实现(二):工业界的明珠——LR逻辑回归

Posted by nickiwei on March 1, 2018

这个系列从最基础的K邻近算法开始, 逐一介绍了机器学习(不含神经网络)的各个典型算法, 以及一些常用的工程技术(如Adaboost, PCA, SVD等), 并比较了各个算法的优劣和适用场景, 另外, 每个算法都配有一个mini project应用帮助理解。 这是本系列的第一篇, 主要介绍了K邻近, k决策树和朴素贝叶斯三种算法。

欢迎转载, 转载请注明出处及链接。

完整代码库请查看我的GithubRepo: https://github.com/nick6918/MyMachineLearning .部分代码参考了stanford CS229以及《机器学习实践》示例代码。

特别说明

1, 本系列中的code全部使用Python/Numpy编写, 在无特别说明的情况下, 未经验证的默认Python/Numpy提供的标准算法为时空复杂度最优的。

2, 为了与矩阵论中保持一致, 本文中的所有独立向量均为列向量, 特征矩阵中, 每一个数据为一个列向量。 所有依赖向量(或Label)均为横向量/List。

从线性回归到逻辑回归

统计学中最常见的回归模型是线性回归, 我们用一条直线逼近所有的数据样本, 希望最终尽可能的减少训练样本误差(即线性回归的损失函数), 从而拟合出一条直线对未来进行预测。

线性回归有两个重要特性需要注意:

1, 线性回归的取值范围是(部分)实数域上的一段连续值

2, 线性回归假设数据预测值是正态分布的

但工业界中, 我们往往会遇到二值预测, 比如广告中的点击率预估(用户点击/不点击), 内容低俗识别(低俗/不低俗)等等, 因此, 我们需要:

1, 取值范围是0/1两个离散值。

2, 预测值实际上是伯努利分布的。

为此, 我们在线性回归的基础上, 构造出sigmoid激活函数, 将预测值映射到一个0,1空间中, 当阀值取为0.5时, 可以证明, 此时的分布恰为伯努利分布(至于为什么是sigmoid以及为什么用sigmoid激活后恰巧是伯努利分布, 请查阅广义线性分布相关资料, 事实上, 这两个问题是相辅相成的)。

最终, 我们得到如下的逻辑回归公式:

lr

LR的地位

由于LR简单的公式和优异的性能, LR至今仍然是工业界分类问题的重要选择之一(相比之下, 原理晦涩复杂的SVM则越来越少的被使用)。 特别是在推荐系统中, 由于无论如何推荐系统(内容/广告)也需要构建用户/内容/场景的特征, 因此, 深度学习DNN并不显著优于LR(相对应的, 由于在图像和NLP中, DNN可以自己抓取特征, 因此适用性更强)。即使是全方位转型至DNN类模型, LR也可以作为一个特征, 或者, 作为与DNN平行的另一组成部分(如wide and deep模型)而存在, 帮助模型收敛, 提高模型performance。

特别的, LR对处理ID类纯离散特征效果优异, 在组合模型中, LR被看作是记忆部, 相对于DNN则更多突出其泛化的能力。这一部分具体可查看我的另一篇文章《推荐系统与CTR预估(二): 排序模型串讲》之中对wide and deep 模型的介绍。

损失函数: 从线性回归到逻辑回归

讨论完了为什么引入逻辑回归, 我们希望解决的下一个问题是, 如何优化逻辑回归的待估参数。 由于sigmoid函数是一个固定无参函数, 因此, 优化线性回归和优化逻辑回归, 实际上, 优化的是同一批参数。 为此, 我们先来看一下我们是如何通过构造并优化线性回归的损失函数来优化线性回归的。

Linear_cost

由此, 我们可以看出, Linear Regression的cost function为:

Linear_cost

这与我们在统计学上利用最小二乘法求线性回归的最优解是一致的。

那么, 逻辑回归呢?《统计学习方法》中演算如下:

Linear_cost

由此, 我们可以看出, 利用最大似然法得到的逻辑回归的损失函数, 其实就是常用的交叉商。

LR的实现

当parameters确定后, 测试阶段应用LR进行分类是非常简单的, 如下:

def logisticClassify(parameters, test_matrix):
	result = sigmond(dot(parameters.T, test_matrix))
	return [int(item > 0.5) for item in result[0]]

在测试阶段, 我们应用梯度上升法优化parameters:

def gredientAscent(x_matrix, y_vector, initialParameters, step, times):
	"""
	x_matrix -- (N, D)
	paramters -- (D, 1)
	y_vector -- (N, 1)
	
	dparameters = X(y-y_hat)		???
	"""
	#initialParameters = ones((featureNumber, 1))
	parameters = initialParameters
	for i in range(times):
		delta_vector = y_vector - sigmond(dot(parameters.T, x_matrix))
		dparameters = dot(x_matrix, delta_vector.T)
		parameters = parameters + step * dparameters
	return parameters

全量的梯度上升虽然准确, 却非常浪费时间, 另一个极端是, 我们每个iter_times随机选取一批数据(通常称为一个batch)进行优化:

def stocgredientAscent(x_matrix, y_vector, initialParameters, step, iter_times):
	#initialParameters = ones((featureNumber, 1))
	parameters = initialParameters
	dataNumbers = len(x_matrix[0])
	para_matrix = zeros((len(parameters), iter_times))
	for j in range(iter_times):			#modification 1
		dataIndex = range(dataNumbers)
		for i in range(dataNumbers):
			alpha = 4.0/(1+i+j) + step		#modification 2
			#alpha = step #comparison for 2

			index = random.randint(0, len(dataIndex)-1)  #modification 3
			data_index = dataIndex[index]
			del(dataIndex[index])

			#data_index = i      #comparison for modification 3
			delta = y_vector[data_index] - sigmond(dot(parameters.T, x_matrix[..., data_index]))
			dparameters = delta * x_matrix[..., data_index]
			parameters = parameters + alpha * dparameters[..., newaxis]
		para_matrix[..., j:j+1] = parameters
		if j%100 == 0:
			print j, " times have finished"
	#plot_parameters(para_matrix)
	return parameters

LR特征选择

我们通常选择单特征CTR评估来确定特征选择, CTR最准确的理解是, 在贝叶斯先验条件下, 目标为正例和负例的后验概率比(注意, 由于是后验概率, 所以正负例概率之和不是1, 实际上是远低于1的), 以下例子对CTR的解释非常清晰:

CTR

可见, 正例概率为0.06, 负例概率0.04, CTR为0.6. 更具体的解释是,

p(正例概率 app_id=A) = p(app_id=A) * p(app_id=A 正例)

通过改变单特征提升最终CTR的方法, 被称为CTR单特征评估, 这也是特征选择中最基础也最重要的方法。

那么, 确定了特征选择的方法, 我们有哪些特征可供选择呢?

在推荐系统中, 我们通常有三大类基本特征, 用户特征, 内容特征和场景特征。 都很好理解, 用户特征记录用户偏好, 内容特征记录内容属性及调性, 场景特征记录当前场景偏好。

特别的, 我们会引入一些高阶特征, 这些高阶特征往往是低阶特征cos组合后的组合特征。为什么要引入组合特征呢? 一个普遍认同的定性化解释是:

从业务角度看, 在LR推荐系统中, 基本特征实际上是一种全局特征, 这种全局特征往往对某些用户有偏, 组合特征更加精细, 是个性化建模, 但组合特征过多又易于导致特征爆炸问题, 所以, 合适的选择组合特征, 组合和基本特征并用, 是综合全局和个性化建模的最优选择。

此外, 从统计学角度来看, 基本特征仅仅是真实特征在低维空间的映射, 不足以描述真实分布(可以理解成用面来给空间建模, 维度不一致), 加入组合特征是强迫模型在更高维度的空间中建模, 使得拟合分布更真实, 效果更准确。

但是, 无论是基本特征还是组合特征, 特征的选择, 组合和取舍实际上是一个非常庞大而复杂的工程, 可不可以自动化呢? FM(Factorization Model)系列模型正是对自动化特征组合的一种抽象, 这一部分可以阅读我的另一篇博客:《推荐系统与CTR预估(三): FM模型族串讲》