逻辑斯蒂回归|LR
📜

逻辑斯蒂回归|LR

❤️二项逻辑斯蒂回归和sigmoid函数


二项逻辑斯蒂回归模型是二分类模型,是一种生成模型,用条件概率p(y|x)表示:
P(y=1x)=exp(wx+b)1+exp(wx+b):=πw(x)P(y=0x)=11+exp(wx+b):=1πw(x)\begin{aligned}P(y=1|x)&=\frac{exp(w\cdot x+b)}{1+exp(w\cdot x+b)}:=\pi_w(x)\\P(y=0|x)&=\frac{1}{1+exp(w\cdot x+b)}:=1-\pi_w(x) \end{aligned}
x=(x(1),x(2),,x(n))Rnx=(x^{(1)},x^{(2)},\ldots,x^{(n)})\in R^n是输入,y{0,1}y\in \{0,1\}为输出;
w=(w1,w2,,wn)Rnw=(w_1,w_2,\ldots,w_n)\in R^n是权值向量,b是偏置;
wx=w1x(1)+w2x(2)++wnx(n)w\cdot x=w_1x^{(1)}+w_2x^{(2)}+\ldots+w_nx^{(n)}
sigmoid函数是一种激活函数,将输出限制在(0,1)之间,
sigmoid(t)=11+et\operatorname{sigmoid}(t)=\frac{1}{1+e^{-t}}
notion image
二项逻辑斯蒂回归模型的概率输出为
πw(x)=sigmoid(wx+b)\pi_w(x)=\operatorname{sigmoid}(w\cdot x+b)
即将wx+bw\cdot x+b映射到概率(0,1)区间。
 
二分类模型:感知机VS支持向量机VS二项逻辑斯蒂回归
notion image
感知机&支持向量机:f(x)=sign(wx+b)f(x)=\operatorname{sign}(w\cdot x+b) 仅能知道样本被分类的结果,但不知道它属于一个类的概率是多少;
二项逻辑斯蒂回归:πw(x)=sigmoid(wx+b)\pi_w(x)=\operatorname{sigmoid}(w\cdot x+b) 通过sigmoid函数将距离转化为概率
知道概率的好处:现实中可能遇到这样的情况,要得到最有可能被分类到A类的前10个样本以对用户进行推荐,有了概率只需要对模型的结果进行排序,就可以解决这个问题。
 

🧡二项逻辑斯蒂回归的损失函数以及模型的训练


损失函数:负对数似然函数也是交叉熵损失函数
模型的似然函数
L(w,b)=i=1N[πw(xi)]yi[1πw(xi)]1yiL(w,b)=\prod_{i=1}^N\left[\pi_w\left(x_i\right)\right]^{y_i}\left[1-\pi_w\left(x_i\right)\right]^{1-y_i}
负对数似然函数等价于交叉熵损失函数,极大似然估计也即极小化交叉熵损失函数
logL(w,b)=i=1N[yilogπw(xi)+(1yi)log(1πw(xi))]=i=1N[yi(wxi+b)log(1+e(wxi+b))]\begin{aligned}-\log L(w,b)&=-\sum_{i=1}^N\left[y_i \log \pi_w\left(x_i\right)+(1-y_i)\log \left(1-\pi_w\left(x_i\right)\right)\right]\\&=-\sum_{i=1}^N\left[y_i(w\cdot x_i+b)-\log \left(1+e^{(w\cdot x_i+b)}\right)\right]\end{aligned}
注意⚠️:在上式中,N表示样本数,xix_i表示某一个样本
从几率(odds)的角度理解
几率和概率
odds=p1podds = \frac{p}{1-p}
例子:假设中国队和巴西队踢足球,赢的概率是0.01,输的概率是0.99,则赢的几率是1/99,输的几率是99.
对数几率和概率
log(odds)=logp1plog(odds)=\log\frac{p}{1-p}p=11+elog(odds)p=\frac{1}{1+e^{-\log(odds)}}
即逻辑回归中的sigmoid函数,而log(odds)又被称为logit函数。
二分类的交叉熵损失函数
(ylogp+(1y)log(1p))=(ylogp1p+log(1p))-(y\log p+(1-y)\log(1-p))=-(y\log\frac{p}{1-p}+\log(1-p))
 
模型的训练:利用梯度下降法或拟牛顿法
损失函数对参数w,b的梯度
L(w,b)w=i=1N(yixixi1+ewxi+b))-\frac{\partial L(w,b)}{\partial w}=-\sum_{i=1}^N\left(y_i x_i-\frac{x_i}{1+e^{-(w \cdot x_i+b)}}\right)L(w,b)b=i=1N(yi11+ewxi+b))-\frac{\partial L(w,b)}{\partial b}=-\sum_{i=1}^N\left(y_i-\frac{1}{1+e^{-(w \cdot x_i+b)}}\right)
 

💛多项逻辑斯蒂回归与softmax


多项逻辑斯蒂回归模型是多分类模型
P(y=kx)=exp(wkx+b)1+k=1K1exp(wkx+b):=πk(x),k=1,2,,K1P(y=Kx)=11+k=1K1exp(wkx+b):=1k=1K1πk(x)\begin{aligned}P(y=k|x)&=\frac{exp(w_k\cdot x+b)}{1+\sum_{k=1}^{K-1} exp(w_k\cdot x+b)}:=\pi_k(x),k=1,2,\ldots,K-1\\P(y=K|x)&=\frac{1}{1+\sum_{k=1}^{K-1} exp(w_k\cdot x+b)}:=1-\sum_{k=1}^{K-1}\pi_k(x) \end{aligned}
softmax函数是一种激活函数,将一个向量映射到一个概率分布熵,
softmax(zk)=ezkk=1Kezk\operatorname{softmax}(z_k)=\frac{e^{z_k}}{\sum_{k=1}^K e^{z_k}}
输入向量(z1,z2,,zK)T(z_1,z_2,\ldots,z_K)^T,softmax输出向量
(ez1k=1Kezkez2k=1KezkezKk=1Kezk)\left(\begin{matrix}\frac{e^{z_1}}{\sum_{k=1}^K e^{z_k}}\\\frac{e^{z_2}}{\sum_{k=1}^K e^{z_k}}\\\cdots\\\frac{e^{z_K}}{\sum_{k=1}^K e^{z_k}}\end{matrix}\right)
softmax函数的数值溢出问题
  • 数值上溢:zk+z_k\rightarrow+\infty时,经过指数运算后的值接近无穷大,程序输出为NAN;
  • 数值下溢:zkz_k\rightarrow-\infty时,经过指数运算后的值接近0,程序输出为0.
解决数值上溢: zkmax(z)z_k-\max(z)
softmax(zk)=softmax(zkmax(z))=ezkmax(z)k=1Kezkmax(z)\operatorname{softmax}(z_k)=\operatorname{softmax}(z_k-\max(z))=\frac{e^{z_k-\max(z)}}{\sum_{k=1}^K e^{z_k-\max(z)}}
解决数值下溢:log-softmax
log[Softmax(zk)]=logezkmax(z)k=1Kezkmax(z)=zkmax(z)log(k=1Kezkmax(z))\begin{aligned}\log \left[\operatorname{Softmax}\left(z_k\right)\right]&=\log \frac{e^{z_k-\max(z)}}{\sum_{k=1}^K e^{z_k-\max(z)}}\\&=z_k-\max (z)-\log \left(\sum_{k=1}^K e^{z_k-\max (z)}\right)\end{aligned}
 

💚逻辑斯蒂回归实现多分类的三种方法


One Vs One
OvO 的方法就是将多个类别中抽出来两个类别,然后将对应的样本输入到一个逻辑斯蒂回归的模型中,学到一个对这两个类别的分类器,然后重复以上的步骤,直到所有类别两两之间都存在一个分类器
假设存在4个类别,那么分类器的数量为6,如下:
A
B
C
D
A
A vs B
A vs C
A vs D
B
B vs C
B vs D
C
C vs D
D
在预测时,需要运行每一个模型,然后记录每个分类器的预测结果,也就是每个分类器都进行一次投票,取获得票数最多的那个类别就是最终的多分类的结果。
OvO方法的开销
  1. 当需要预测的类别变得很多的时候,那么我们需要进行训练的分类器也变得很多了,这一方面提高了训练开销。
  1. 每一个训练器中,因为只需要输入两个类别对应的训练样本即可,这样就又减少了开销。
  1. 从预测的角度考虑,这种方式需要运行的分类器非常多,而无法降低每个分类器的预测时间复杂度,因此预测的开销较大。
One Vs All
OvA 方法就是从所有类别中依次选择一个类别作为1,其他所有类别作为0,来训练分类器,因此分类器的数量为类别数K,要比 OvO 的数量少得多。
作为1的类别
作为0的类别
A
B C D
B
A C D
C
A B D
D
A B C
预测时,是根据每个分类器对其对应的类别1的概率进行排序,选择概率最高的那个类别作为最终的预测类别。
OvA方法的开销
  • 虽然分类器的数量下降了,但是对于每一个分类器来说,训练时需要将所有的训练数据全部输入进去进行训练,因此每一个分类器的训练时间复杂度是高于 OvO 的。
  • 从预测的方面来说,因为分类器的数量较少,而每个分类器的预测时间复杂度不变,因此总体的预测时间复杂度小于 OvA。
从sigmoid到softmax
 

🩵逻辑斯蒂回归的正则化


在逻辑斯蒂回归中如果不使用正则化,模型会尝试使用所有的特征(包括噪音和无用特征等)做拟合那么在预测时无用特征的作用会导致预测结果的偏离。而特征权重如果特别大,那么当一个特征的数值有一个小波动(噪音),就会造成预测结果的大幅度变化,也会造成结果的偏离。
notion image
正则化的两种思路:加惩罚项、或加参数先验
  1. 在损失函数后面,加上一个对权重的惩罚项
    1. Loss=logL(w)+j=1nH(wj)=i=1N[yilogπw(xi)+(1yi)log(1πw(xi))]交叉熵损失+j=1nH(wj)惩罚项\begin{aligned}Loss&=-\log L(w)+\sum_{j=1}^nH(w_j)\\&=\underbrace{-\sum_{i=1}^N\left[y_i \log \pi_w\left(x_i\right)+(1-y_i)\log \left(1-\pi_w\left(x_i\right)\right)\right]}_{交叉熵损失}+\underbrace{\sum_{j=1}^nH(w_j)}_{惩罚项}\end{aligned}
      注意⚠️:在上式中,N表示样本数,n表示特征维数。
  1. 引入权重的先验信息,极大似然估计MLE改为极大后验估计MAP
    1. MLEmaxwL(w)=maxwP(Yw)MLE: \max_w L(w)=\max_w P(Y|w)Bayes:P(wY)=P(Yw)P(w)P(Y)=P(Yw)P(w)wP(Yw)P(w)dwBayes:P(w|Y)=\frac{P(Y|w)P(w)}{P(Y)}=\frac{P(Y|w)P(w)}{\int_wP(Y|w)P(w)dw}MAP:maxwP(wY)=maxwP(Yw)P(w)MAP:\max_w P(w|Y)=\max_w P(Y|w)P(w)
      故加入权重先验信息的逻辑斯蒂回归的极大后验估计MAP为
      maxwP(wY)=maxw[i=1N[πw(xi)]yi[1πw(xi)]1yi参数w的似然j=1nP(wj)参数w的先验]=minw[i=1N[yilogπw(xi)+(1yi)log(1πw(xi))]交叉熵损失+j=1n[logP(wj)]惩罚项]\begin{aligned}\max_w P(w|Y)&=\max_w\left[\underbrace{ \prod_{i=1}^N\left[\pi_w\left(x_i\right)\right]^{y_i}\left[1-\pi_w\left(x_i\right)\right]^{1-y_i}}_{参数w的似然}\underbrace{\prod_{j=1}^nP(w_j)}_{参数w的先验}\right]\\&=\min_w\left[\underbrace{-\sum_{i=1}^N\left[y_i \log \pi_w\left(x_i\right)+(1-y_i)\log \left(1-\pi_w\left(x_i\right)\right)\right]}_{交叉熵损失}+\underbrace{\sum_{j=1}^n\left[-\log P(w_j)\right]}_{惩罚项}\right]\end{aligned}
由上可知两种方法的形式其实是等价的,惩罚函数就是先验函数的负对数
H(w)=logP(w)H(w)=-\log P(w)
L0正则 正则化项为非0权重的个数
H(wj)={1,wj00,wj=0}H\left(w_j\right)=\left\{\begin{array}{ll}1, & w_j \neq 0 \\0, & w_j=0\end{array}\right\}
L0正则化容易理解,但在迭代时并不容易求解,因为这是一个NP难问题
L1正则 正则化项为权重绝对值之和(权重的先验为laplace分布)
L1 正则加入的先验知识是,模型的权重符合拉普拉斯分布,且平均值为0,
P(wj)=12λewjλP(w_j)=\frac{1}{2\lambda}e^{-\frac{|w_j|}{\lambda}}H(w)=j[logP(wj)]=CjwjH(w)=\sum_j\left[-\log P(w_j)\right]=C\sum_j|w_j|
Laplace分布:f(w)=12λewμλf(w)=\frac{1}{2 \lambda} e^{-\frac{|w-\mu|}{\lambda}}
notion image
  • L1正则将模型中不重要特征的权值下降到0
    • L1正则项对w的导数{(w)=1,w>0(w)=1,w<0\begin{cases}(|w|)^{\prime}=1, & w>0 \\ (|w|)^{\prime}=-1, & w<0\end{cases}
      可以看出在L1正则化中,每次优化,都会下降一个固定值,直到w的值为0。
      notion image
  • L1正则能保留重要的权值
    • 目标函数不仅要考虑的是权重是否为0,还要考虑分类的准确性。对分类不重要的特征,正则项的优化贡献大,最终就被优化到0;而对分类重要的特征,交叉熵的优化贡献大,于是就不会被优化到0,最后这个特征就被保留了下来。
L2正则 正则化项为权重的平方和(权重的先验为正态分布)
L2正则加入的先验知识是,模型的权重符合正态分布,且平均值为0,
P(wj)=12πσewj22σ2P(w_j)=\frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{w_j^2}{2 \sigma^2}}H(w)=j[logP(wj)]=Cjwj2H(w)=\sum_j\left[-\log P(w_j)\right]=C\sum_jw_j^2
  • L2正则解决了特征权值过大造成的过拟合问题
    • L2正则项对w的导数(w2)=2w(w^2)'=2w,也就是说梯度随着权值w的下降而下降,因此一开始下降的比较快,往后越来越慢,会慢慢地逼近0,但不会等于0.
      notion image
如何理解过拟合时对应的特征权值过大
notion image
在对训练数据进行拟合时,需要照顾到每个点,从而使得拟合函数波动性非常大,即方差大。在某些小区间里,函数值的变化性很剧烈,意味着函数在某些小区间里的导数值的绝对值非常大,由于自变量的值在给定的训练数据集中的一定的,因此只有系数足够大,才能保证导数的绝对值足够大。因此,减小特征权值过大的权重,能让拟合函数不那么波动。
L1正则化和L2正则化可视化解释
notion image
可以看出L1正则化会让部分权重为0,而L2的正则化不会让权值为0.
弹性网络Elastic Net 是对 L1 正则和 L2 正则的一个结合
Loss(w)=i=1N[yilogπw(xi)+(1yi)log(1πw(xi))]+λj=1M[ρwj22+(1ρ)wj]\begin{gathered}Loss(w)=-\sum_{i=1}^N\left[y_i \log \pi_w\left(x_i\right)+\left(1-y_i\right) \log \left(1-\pi_w\left(x_i\right)\right)\right]\\+\lambda \sum_{j=1}^M\left[\rho \frac{w_j^2}{2}+(1-\rho)\left|w_j\right|\right]\end{gathered}
通过调节超参数 λ 和 ρ ,可以调整 L1 正则项和 L2 正则项对优化函数的贡献程度。
 

🤎逻辑斯蒂回归中需要关注的问题


分类的阈值选择与样本不平衡问题
通常情况下用0.5作为二分类的阈值
选择0.5是基于总体中正例和反例符合1:1的假设,也就是正例和反例相平衡。
样本不平衡的后果
如果样本数据中的样本不平衡(比如正例远远多于反例)时,模型会更倾向于去拟合正例。
样本不平衡的解决方案
  1. 样本增强 在训练的时候减少输入数量较多的类的样本,或者收集更多数量较少的类的样本,让模型训练时输入的样本平衡即可。
      • 对于不同的样本类型,可以存在不同的增强方式,比如对于图像而言,只需要将图像进行旋转,裁切,翻转,遮掩等都可以得到大量的新样本。
      • 对于文本数据,则可以通过转义,同义词替换等等方式。
  1. 自定义损失函数 让样本数多的类提供的损失减小,或者增大样本数少的类的损失
    1. 例如正反例比为10:1的样本,将损失函数修改为
      logL=i=1N[110yilogπ(xi)+(1yi)log(1π(xi))]\log L=\sum_{i=1}^N\left[\frac{1}{10} y_i \log \pi\left(x_i\right)+\left(1-y_i\right) \log \left(1-\pi\left(x_i\right)\right)\right]
  1. 修改分类的阈值 让样本数多的类的分类阈值更为严格(大于0.5)
    1. 可以将样本中正反例的数量的比值设置为分类的阈值
为什么逻辑斯蒂回归使用交叉熵损失函数,而不是MSE?
由于逻辑斯蒂回归的预测值是一个概率,交叉熵可以表示真实概率分布与预测概率分布的相似程度;另一方面,在分类问题中,样本的值不存在大小关系,与欧氏距离更无关系,因此不适用MSE。
信息熵、交叉熵、相对熵的公式可知:
DKL(PQ)=i=1nP(xi)logP(xi)Q(xi)=i=1nP(xi)logQ(xi)(i=1nP(xi)logP(xi))=H(P,Q)H(P)\begin{gathered}D_{K L}(P \| Q)=\sum_{i=1}^n P\left(x_i\right) \log \frac{P\left(x_i\right)}{Q\left(x_i\right)}\\=-\sum_{i=1}^n P\left(x_i\right) \log Q\left(x_i\right)-\left(-\sum_{i=1}^n P\left(x_i\right) \log P\left(x_i\right)\right)\\=H(P, Q)-H(P) \end{gathered}
注意⚠️:在上式中,n表示x取值的可能数,x_i表示某一个可能的取值
在逻辑斯蒂回归中,P(x)表示真实的分类标签{0,1},Q(x)为逻辑斯蒂回归模型的预测概率。由于P是固定的,故P的信息熵是常数,最小化交叉熵即最小化KL散度,也就是让预测概率分布尽可能与真实的分类相似
MSE 的损失小于交叉熵的损失,导致对分类错误的点的惩罚不够
假设label为1,预测为y_predict,那么预测错误的点的Loss如下图
notion image
显然log-loss要比MSE要大,并且对于预测错误的样本,错的越离谱,惩罚越严重。
MSE的梯度消失效应较大
 Loss =(y^iyi)2Lossw=2(y^iyi)(y^iyi)w=2(y^iyi)(11+e(wxi+b))w=2(yiy^i)(11+e(wxi+b))2e(wxi+b)w=2(y^iyi)(11+e(wxi+b))2e(wxi+b)xi=2(y^iyi)y^i(1y^i)xi\begin{aligned}& \text { Loss }=\left(\hat{y}_i-y_i\right)^2 \\& \frac{\partial{Loss}}{\partial w}=2\left(\hat{y}_i-y_i\right) \frac{\partial\left(\hat{y}_i-y_i\right)}{\partial w} \\& =2\left(\hat{y}_i-y_i\right) \frac{\partial\left(\frac{1}{1+e^{-(w x_i+b)}}\right)}{\partial w} \\& =2\left(y_i-\hat{y}_i\right)\left(\frac{1}{1+e^{-(w x_i+b)}}\right)^2 \frac{\partial e^{-(w x_i+b)}}{\partial w} \\& =2\left(\hat{y}_i-y_i\right)\left(\frac{1}{1+e^{-(w x_i+b)}}\right)^2 e^{-(w x_i+b)} x_i \\&=2\left(\hat{y}_i-y_i\right) \hat{y}_i\left(1-\hat{y}_i\right) x_i\end{aligned}
可以看到在梯度中存在y^i(1y^i)\hat{y}_i\left(1-\hat{y}_i\right)项,也就是说,当预测值接近于1或0时,会导致梯度接近于0,无法进行有效学习。
交叉熵是凸函数,MSE是非凸函数,因此使用MSE可能陷入局部最优;而交叉熵损失函数是凸函数,可以求得全局最优。
对于一个非凸函数,模型有可能陷入局部最优而无法继续优化
notion image
对上文MSE的一阶导继续求导,得到的二阶导不是恒大于0的,故以MSE为损失函数的逻辑斯蒂回归是非凸函数,使用MSE可能陷入局部最优。
可以求得交叉熵损失函数的二阶导一定大于等于0,因此是个凸函数,可以求得全局最优
逻辑斯蒂回归的并行计算方法
逻辑斯蒂回归模型的优势是计算量少而快,仍然活跃在各大应用场景之中,尤其是推荐系统,其特征数量很大,动不动就达到几百万,几千万,甚至上亿,上十亿的级别(因为会对用户 id 和物品 id 进行 one-hot 编码,有时候还需要做特征交叉),同时样本数量相比于特征来说更大,因为每个用户的每个行为都会产生样品,而在业务中,又恰恰要求推荐系统能够做到在线学习,可以非常快速地更新迭代,于是计算量少而快的逻辑斯蒂回归就是最好的选择之一。
并行运算常常运用到大量的模型算法之中,运用到逻辑斯蒂回归上,可以让其运算速度变得更快。
逻辑斯蒂回归的优化方法为梯度下降法,但使用的是batch梯度下降法,而不是随机梯度下降法。因为随机梯度下降法虽然收敛速度较快,但是收敛方向比较随机,另外会在最低点来回跳动,造成无法继续收敛的情况。
观察梯度公式:
L(w)w=1Ni=1N(yixixi1+ewxi+b))\frac{\partial L(w)}{\partial w}=\frac{1}{N} \sum_{i=1}^N\left(y_i x_i-\frac{x_i}{1+e^{-(w \cdot x_i+b)}}\right)
其中yi,xiy_i,x_i是固定值,w和xix_i是点乘的关系,也就是在各个特征纬度上的乘积之和,最后是将不同样本的梯度相加再求一个平均。故在工程上,可以用三种方式进行并行化:
在样本的层次上划分
并行任务1:ρ1=y1x1x11+ewx1并行任务2:ρ2=y2x2x21+ewx3并行任务3:ρ3=y3x3x31+ewx3并行任务N:ρN=yNxNxN1+ewxNL(w)w=1Ni=1Nρi\begin{aligned}& \text{并行任务1:}\rho_1=y_1 x_1-\frac{x_1}{1+e^{-w \cdot x_1}} \\& \text{并行任务2:}\rho_2=y_2 x_2-\frac{x_2}{1+e^{-w \cdot x_3}} \\& \text{并行任务3:}\rho_3=y_3 x_3-\frac{x_3}{1+e^{-w \cdot x_3}} \\& \cdots \\& \text{并行任务N:}\rho_N=y_N x_N-\frac{x_N}{1+e^{-w \cdot x_N}} \\& \frac{\partial L(w)}{\partial w}=\frac{1}{N} \sum_{i=1}^N \rho_i\end{aligned}
在实际情况中,还需要考虑样本数量以及特征数量来确定最佳的并行数量:
  • 如果样本量较少而特征较多,则每一个并行任务中仅计算一个样本就能达到较高的效率;
  • 如果样本较多但特征数量少,则需要每一个并行任务中多分配几个样本,因为启动线程或进程也需要时间;
  • 如果单个并行任务中的计算时间比启动任务的时间还少,那么使用并行方法反而是增加了时间消耗的。
按照特征划分
假设有3个样本和3个特征,那么可以组成一个3*3的矩阵,按照特征划分,即按照列划分:
w1
w2
w3
x1
w1*x1(1)
w2*x1(2)
w3*x1(3)
x2
w1*x2(1)
w2*x2(2)
w3*x2(3)
x3
w1*x3(1)
w2*x3(2)
w3*x3(3)
第一个并行任务
第二个并行任务
第三个并行任务
此时的每个并行任务,计算的是不同样本与单个特征的乘积,而在梯度公式中,需要将同一样本与不同特征的乘积相加,因此需要将并行任务计算的结果集合成一个大表,再根据样本的维度进行加和。
在实际情况中,还需要考虑样本数量以及特征数量来确定最佳的并行数量:
  • 如果样本量较少而特征较多,则每一个并行任务中需要传入多个特征进行计算才能达到节省时间的目的;
  • 如果样本较多但特征数量少,那么每一个并行任务分配一个特征进行计算即可;
  • 由于需要保存整个大表的计算结果,且加和运算需要放在并行化之外,因此内存和时间的开销相对较大;
按照样本和特征划分
同时在样本维度和特征维度上对矩阵进行拆分,同样在计算完成后需要保存计算结果,拼接成一个完整的矩阵后,再计算梯度。
G
w1
w2
w3
w4
x1
G(1,1)
G(1,2)
G(1,3)
G(1,4)
x2
G(2,1)
G(2,2)
G(2,3)
G(2,4)
x3
G(3,1)
G(3,2)
G(3,3)
G(3,4)
x4
G(4,1)
G(4,2)
G(4,3)
G(4,4)
并行任务1:计算G(1:2,1:2)
并行任务2:计算G(1:2,3:4)
并行任务3:计算G(3:4,1:2)
并行任务4:计算G(3:4,3:4)
为什么逻辑斯蒂回归适合稀疏矩阵
逻辑斯蒂回归常用在推荐系统上,推荐系统中的特征矩阵往往是稀疏的:因为推荐系统需要对特征进行编码,分桶和交叉,使得特征矩阵变得稀疏,这样的特征矩阵更符合现实情况,或者增加了非线性,同时也增加了鲁棒性。
稀疏矩阵用在逻辑斯蒂回归上,可以大大减少时间复杂度,比如对元素为0的部分,可以直接忽略其乘法运算,并且通过一些方式,也可以仅仅存储不等于0的元素,大大减少空间复杂度。
One hot编码
对于推荐系统,往往是基于单个用户来进行推荐的,而在特征中,如何表示单个用户呢?很简单,使用用户的ID,这往往就是一串数字。但一个很明显的问题是,数字是存在大小关系的,但用户ID之间并不存在大小关系,因此与推荐结果并不存在线性关系,于是我们对其采用 one-hot 编码,这样,当用户数量增多,特征矩阵中的用户部分,就立刻变得异常稀疏了。
用户ID
1000
1001
1002
1003
特征向量
1000
1
0
0
0
(1,0,0,0)
1001
0
1
0
0
(0,1,0,0)
1002
0
0
1
0
(0,0,1,0)
1003
0
0
0
1
(0,0,0,1)
分桶
与将用户 ID 进行 One-hot 编码类似的理由,一些特征虽然本身存在大小关系,比如用户年龄,观看视频数量,或者注册至今时长等等,但这种特征与推荐结果往往也不存在线性关系,因此我们需要对其进行分桶,来引入非线性,而分桶之后,又会增加特征矩阵的稀疏性。
注册年数
注册<2年
注册2-5年
注册>5年
特征向量
1
1
0
0
(1,0,0)
2
0
1
0
(0,1,0)
3
0
1
0
(0,1,0)
5
0
0
1
(0,0,1)
10
0
0
1
(0,0,1)
特征交叉
同样考虑现实情况,有一些特征可能它们本身与推荐结果没有关联,但它们的组合却对推荐结果存在关联,比如仅仅通过“18-25岁“,或者“观看视频活跃时间在下午2-5点“这两个特征没法判断这个人是一个学生,这个年龄也可能是上班族,观看视频活跃时间在下午2-5点也可能是老年人,但是“18-25岁且观看视频活跃时间在下午2-5点”的人则很有可能是一个大学生。
当用来交叉的特征本身是稀疏的时候,那么交叉出来的特征也会是稀疏的,而稀疏性与特征的交叉方式有关,如果是相乘(和的关系),则稀疏性可能会增加,如果是相加(或的关系),则稀疏性可能会下降(但一般而言相乘用的比较多,依据现实情况而定)。
18-25岁
观看时间在下午2-5点
18-25岁&观看时间在下午2-5点
0
0
——>
0
0
1
——>
0
1
0
——>
0
1
1
——>
1
鲁棒性
鲁棒性指的是三个层面:
  1. 要求模型的精度较高
  1. 要求噪声对模型的影响较小
  1. 要求离群点不能对模型产生较大影响
那么当我们对特征数据进行分桶后,会发现离群点(异常值)也被分到了最左或者最右边的桶中,在上述第三点上增加了模型的鲁棒性。
18岁
19岁
60岁
150岁
18-25岁
>60岁
1
0
0
0
——>
1
0
0
1
0
0
——>
1
0
0
0
1
0
——>
0
1
0
0
0
1
——>
0
1
稀疏矩阵如何实现排零储存和排零计算
所谓稀疏矩阵,简单来说,就是矩阵中为0的元素比例较高的矩阵,由于0不携带信息,因此耗费空间存储0元素是很浪费资源的行为,特别是在矩阵极其巨大的情况下。
为了解决这个问题,在工程中可以对稀疏矩阵的存储和计算都做一些优化,减少空间复杂度和时间复杂度。
  • COO(Coordinate Format)
    • 以坐标的形式存储矩阵中的非0元素aija_{ij},通常使用三元组(横坐标,纵坐标,值)即xi,yj,aij(x_i,y_j,a_{ij})
      虽然每一个非0元素的存储增加里,但由于减少了0元素的存储,因此整体的空间复杂度还是降低了。
      [100200304005000000000060]压缩为(x,y,a)001032103124155346\left[\begin{matrix}1&0&0&2&0&0\\3&0&4&0&0&5\\0&0&0&0&0&0\\0&0&0&0&6&0\end{matrix}\right]-\text{压缩为}\rightarrow\begin{matrix}(x,&y,&a)\\0&0&1\\0&3&2\\1&0&3\\1&2&4\\1&5&5\\3&4&6\end{matrix}
      此时存储空间由24减少到了18.
  • CSR(Compressed Sparse Row Format)
    • COO 矩阵的行坐标进行排序后有一些元素的行坐标之间是重复的,CSR对行坐标序列的存储进行了进一步的优化:保持 COO 矩阵中的行坐标的顺序排列,然后仅记录每一组相同行坐标的第一个值在 COO 矩阵中的索引即可,如果遇到不存在的,就重复前一个的索引。
      COOCSR001113压缩为(0,2,5,5,6)\begin{matrix}COO& & CSR\\(0,0,1,1,1,3)&-\text{压缩为}\rightarrow &(0,2,5,5,6)\end{matrix}
      比如上述COO的行坐标序列为(0,0,1,1,1,3),按照上述方式仅记录索引为(0,2,5,5,6),又节省了1个存储空间。
       
 
参考链接