Part4 线性模型

1. 线性回归

1. 线性回归采用最小二乘法作为代价函数，需要符合最小二乘法使用的基本假设，违背基本假设时，普通最小二乘法估计量不再是最小线性无偏估计量，但是还是无偏的
2. 正规方程法中如果$X^TX$XTX不可逆，两种解决方案：删除数据中多余的特征（即特征之间存在相关性）；删除部分特征数据使特征数小于样本数

2.逻辑回归

1. 当逻辑回归仍采用线性回归的代价函数时，即仍用MSE表征，定义为$J(\theta)=\frac{1}{m}\sum_{i=1}^m\frac12(h_\theta(x^{(i)}-y^{(i)})^2$J(θ)=m1​∑i=1m​21​(hθ​(x(i)−y(i))2，其中$h_\theta(x)=sigmoid(\theta^TX)$hθ​(x)=sigmoid(θTX),所得到的代价函数将是一个非凸函数，影响用梯度下降法求最小值，因此选用交叉熵损失函数

2. 利用梯度下降法求解代价函数的推导公式
   

3. 两种角度考虑逻辑回归的代价函数：

   1. 极大似然估计
   2. 

4. 多分类问题的逻辑回归

   softmax的推导过程：

   $\ln P(Y_i=1)=\beta_1 X_i-\ln Z$lnP(Yi​=1)=β1​Xi​−lnZ

   $\ln P(Y_i=2)=\beta_2 X_i-\ln Z$lnP(Yi​=2)=β2​Xi​−lnZ

   $\ln P(Y_i=3)=\beta_3 X_i-\ln Z$lnP(Yi​=3)=β3​Xi​−lnZ

   $\ln P(Y_i=K)=\beta_K X_i-\ln Z$lnP(Yi​=K)=βK​Xi​−lnZ

   这里的$lnZ$lnZ为一个常数，能够保证$\Sigma P(i)=1$ΣP(i)=1，将两边指数化，可得

   $P(Y_i=k)=\frac1Ze^{\beta_kX_i}$P(Yi​=k)=Z1​eβk​Xi​

   则有

   $Z=\sum e^{\beta_kX_i}$Z=∑eβk​Xi​

   代入上式则有：
   $\operatorname{P}\left(Y_{i}=c\right)=\frac{e^{\beta_{c} \cdot \mathbf{x}_{i}}}{\sum_{k=1}^{K} e^{\beta_{k} \cdot \mathbf{X}_{i}}}$P(Yi​=c)=∑k=1K​eβk​⋅Xi​eβc​⋅xi​​
   记$\beta_c\cdot \mathbf{x_i}=\mathbf{z_c}$βc​⋅xi​=zc​，则上式就变为了：
   $P(y=i)=\frac{e^\mathbf{z_i}}{\sum_{k=1}^{K} e^{\mathbf{z_k}}}$P(y=i)=∑k=1K​ezk​ezi​​
   softmax的损失函数

   softmax的损失函数常用对数似然代价函数，具体如下：
   $Loss=-\sum_{i} t_{i} \ln y_{i}$Loss=−i∑​ti​lnyi​
   $t_i$ti​代表第i个样本的分类，当第i个样本分类为k时，有：$t_i=1$ti​=1当i=k，$t_i=0$ti​=0当i不等于k
   

   综上，softmax的求导可为:$y_i-t_i$yi​−ti​

3. 正则化

为了避免过拟合，无论是逻辑回归还是线性模型都采用加入正则化项，当加入$L_2$L2​范数时，得到的线性模型成为岭回归，采用$L_1$L1​范数时得到LASSO回归，无论是L1范数还是L2范数，都将有助于降低过拟合的风险，但同时，L1范数更容易获得稀疏解（即求得的参数中有更少的非零分量）可用于进行特征选择

为什么L1更容易获得稀疏解，如上图所示，假设输入变量为只有两个，即在$y=\omega x+b$y=ωx+b中$\omega$ω只有两个，我们写出对应的Lasso回归和岭回归的表达式：

LASSO:

$argmin_\omega \sum_{i=1}^m(y_i-\omega^Tx_i)^2+\lambda|\omega|$argminω​∑i=1m​(yi​−ωTxi​)2+λ∣ω∣

Ridge:

$argmin_\omega \sum_{i=1}^m(y_i-\omega^Tx_i)^2+\lambda\omega^2$argminω​∑i=1m​(yi​−ωTxi​)2+λω2

由Lagrange乘数法，对于Lasso，即为求下面的条件极值：
$argmin_\omega \sum_{i=1}^m(y_i-\omega^Tx_i)^2$argminω​i=1∑m​(yi​−ωTxi​)2
$s.t. ||\omega||&lt;=C$s.t.∣∣ω∣∣<=C

对于Ridge同理，于是我们将$||\omega||&lt;=C,\omega^2&lt;=C$∣∣ω∣∣<=C,ω2<=C以及广义cost function的等值线绘制在坐标轴中如下

若最优解不在凸函数的边界取到，则一定在凸函数的内部取到，此时加不加正则化也没啥意义，但是实际情况中，最优解往往在正则化边界处渠道，此时，在所有的解中，L1范数更有可能与目标函数相交于坐标轴线上，L2范数不可能与目标函数交于坐标轴线上，使得产生的解不具有稀疏性

总的来说，一般在特征选择的时候选用L1范数，在要正则化的时候选择L2范数，其实L1也能正则化，但是实际情况为什么经常采用L2范数呢，我想可能跟L1范数不是处处可导有关

此外，在深度学习中的权重衰减也是指的L2正则化

4. FM,FFM,DeepFM

在做这些事情之前，首要做的就是One-Hot编码

LR&PLOY2

LR优点是简单高效，缺点也很明显，它太简单，视特征空间内特征之间彼此独立，没有任何交叉或者组合关系，这与实际不符合，因此PLOY2通过特征的二项式组合建模，PLOY2的函数如下
$f(x)=w_0+\sum_{i=1}^nw_ix_i+\sum_{j_{1}=1}^{n} \sum_{j_{2}=j_{1}+1}^{n} w_{h\left(j_{1}, j_{2}\right)} x_{j_{1}} x_{j_{2}}$f(x)=w0​+i=1∑n​wi​xi​+j1​=1∑n​j2​=j1​+1∑n​wh(j1​,j2​)​xj1​​xj2​​
PLOY2有一个明显的问题，就是在实际场景中，大部分特征都是稀疏的，即大部分特征值为0

FM与embedding

因此，FM就是解决稀疏数据下的特征组合问题

对于每个特征$i$i来说，认为其有一个隐向量$v_{i(k\cdot 1)}$vi(k⋅1)​，其中k为超参数，则PLOY2中的$w_{ij}=v_i^T\cdot v_j$wij​=viT​⋅vj​，则FM的表达式为
$\hat{y}(\mathbf{x})=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left(\mathbf{v}_{i} \cdot \mathbf{v}_{j}\right) x_{i} x_{j}$y^​(x)=w0​+i=1∑n​wi​xi​+i=1∑n​j=i+1∑n​(vi​⋅vj​)xi​xj​
注意：在强调一遍，这里面所涉及的特征，都是One-Hot编码后的特征

举例说明：

训练集如下：

数据集	Clicked?	Publisher	Advertiser
训练集	1	NBC	Nike
训练集	0	EPSN	Adidas

测试集如下：

数据集	Clicked?	Publisher	Advertiser
测试集	?	NBC	Adidas

首先要做的就是先把Publisher和Advertiser的特征One-Hot编码，如下：

数据集	Clicked?	NBC	ESPN	Nike	Adidas
训练集	1	1	0	1	0
训练集	0	0	1	0	1

则四个特征分别是NBC,ESPN,Nike,Adidas,对于第一个训练样本，FM参数变为$V_{N B C} \cdot V_{N i k e}$VNBC​⋅VNike​，因为其他的都是0,只有$x_{N B C} \cdot x_{N i k e}=1$xNBC​⋅xNike​=1，对于第二个训练样本，FM参数变为$V_{E P S N} \cdot V_{A d i d a s}$VEPSN​⋅VAdidas​,同理，因为只有ESPN和Adidas相乘不为0，根据训练集，上述训练集，我们训练得到$V_{N B C} ,V_{E P S N},V_{A d i d a s},V_{N i k e}$VNBC​,VEPSN​,VAdidas​,VNike​，然后在测试集上，FM参数只有$V_{NBC} \cdot V_{Adidas}$VNBC​⋅VAdidas​

则我们的任务就是，根据所有的训练集，求出所有特征的因变量$v_i$vi​，以及特征的系数$w_i$wi​和常数$w_0$w0​，共kn+n+1个变量。紧接着将训练得到的参数用于测试集，计算y

计算复杂度分析：

直接来看FM的复杂度为$O(kn^2)$O(kn2)，对FM的表达式进行优化，可将复杂度降至$O(kn)$O(kn)

FM的性能度量方法

注意，FM只是针对于原来的$f(x)=w_0+\sum_{i=1}^n w_ix_i$f(x)=w0​+∑i=1n​wi​xi​进行优化的，将FM应用于分类问题时，采用的依然是$y=\frac{1}{1+exp(-f(x))}$y=1+exp(−f(x))1​，把其中的f(x)换为FM的表达式就好

对于回归问题
$Loss=(\hat{y}(\mathbf{x})-y)^2$Loss=(y^​(x)−y)2
对于分类问题
$Loss=\log(1+e^{-y\hat{y}(\mathbf{x})})$Loss=log(1+e−yy^​(x))
embedding

继续来看fm，我们重新给定义，当特征没有被onehot时，我们称之为field，当onehot之后我们称之为feature，现在我们输入的样本假设有d个field，离散化成了n个feature，对于每个feature，在做特征组合的时候，都有一个隐向量$v_{i(k \cdot1 )}$vi(k⋅1)​，假设$d_i$di​的field离散化后有u个feature，则我们将这u个隐向量转置然后拼起来，可以构成一个$u\times k$u×k的矩阵，我们现在只考虑$d_i$di​的特征，当有m个样本经过的时候（注意，这是离散过后的特征）样本矩阵可以写成$X_{(m \times u)}$X(m×u)​，我们让他经过这个$u\times k$u×k的矩阵，就变为了$m\times k$m×k，这就是embedding过程

embedding的本质是实现稀疏特征从高维降低到低维的转变，也就是说在实际业务中u远大于k，embedding的意义：

1. 稀疏矩阵在学习过程中会产生种种问题，特别是深度学习稀疏矩阵直接输入会造成部分权值不被更新，embedding起到了一个保证输入稠密的一个作用
2. 另外在onehot的高维空间上，部分label之间的关系并没有很好的表整出来，比如说对于一句话来讲，我们对每个单词onehot然后放到高维空间里面，那么good和best的距离和good和bad的距离是一样的，不利于我们进行距离度量，而embedding将其映射到低维缓解了这个问题

注意，并不是只有离散特征有embedding方法，连续特征也有，不过连续特征的embedding就是他原来的特征，把每个值直接丢到新的空间维度就好

最后我们看一下fm的结构图

我们看到倒数第二层就是embedding层，最底层到第二层的黑线代表了$f(x)=w_0+\sum_{i=1}^nw_ix_i$f(x)=w0​+∑i=1n​wi​xi​前面的部分，简单粗暴，红线就代表了把embedding之后的和别的做融合，就是fm结构$\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left(\mathbf{v}_{i} \cdot \mathbf{v}_{j}\right) x_{i} x_{j}$∑i=1n​∑j=i+1n​(vi​⋅vj​)xi​xj​

deepFM

deepfm就是把fm和dnn给融合在一起了，上面介绍了fm的结构，这是dnn的结构，可以看到这是一个三层dnn，一个embedding，两个隐层，dnn的目的就是为了学习高阶的组合特征，可以看到，从embedding到第一层hidden layer的时候，不仅特征间有交叉，特征内也有交叉，dnn和fm，一个低阶组合特征一个高阶组合特征，两个一起相当于完成了大部分特征工程的工作

我们看一下deepfm的架构吧

[外链图片转存失败(img-cHWxeJOo-1567221700049)(https://www.hrwhisper.me/wp-content/uploads/2018/07/deep-fm.png)]

其实deepfm并不是唯一的处理特征组合的模型，剩下的还有很多，wide&deep,pnn,fnn，回头再推荐系统的时候一并讲一下

FFM

在FM中，我们认为，各个特征组合组合的时候，隐变量是保持不变的，事实上并不全是，FFM就是考虑Field-FM，大致意思是认为，对于不同类型的特征，他们组合的时候隐向量是会变化的，太绕了举个例子：

数据集	Clicked?	Publisher	Advertiser	Gender
训练集	1	NBC	Nike	Men
训练集	0	EPSN	Adidas	Women

再加一个性别特征，OneHot一下

数据集	Clicked?	NBC	ESPN	Nike	Adidas	Men	Women
训练集	1	1	0	1	0	1	0
训练集	0	0	1	0	1	0	1

在训练样本1中，FM所考虑的隐向量为：
$V_{N B C} \cdot V_{N i k e}+V_{Nike} \cdot V_{Men}+V_{N B C} \cdot V_{Men}$VNBC​⋅VNike​+VNike​⋅VMen​+VNBC​⋅VMen​
而事实上，与Advertiser类别特征相乘的$V_{NBC}$VNBC​和与Gender类别相乘的$V_{NBC}$VNBC​不一定是相等的，FFM考虑了这种与不同类型(Field)特征组合的隐变量不相等问题

FFM所考虑的隐向量为：
$\underbrace{{\bf V}_{NBC, A} \cdot {\bf w}_{Nike, P}}_{P \times A} + \underbrace{{\bf V}_{Nike, G} \cdot {\bf V}_{Men,A}}_{A \times G} + \underbrace{{{\bf V}_{NBC, G} \cdot {\bf V}_{Men,P}}}_{P \times G}$P×AVNBC,A​⋅wNike,P​​​+A×GVNike,G​⋅VMen,A​​​+P×GVNBC,G​⋅VMen,P​​​
注意，FFM考虑的是隐向量在field之间的差异，field就是没有做onehot之前的特征，也就是说，$V_{NBC,G}$VNBC,G​无论是和$V_{Men,P}$VMen,P​还是和$V_{Women,P}$VWomen,P​相乘都取的是一个值。

FFM的表达式为
$y(\mathbf{x}) = w_0 + \sum_{i=1}^d w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n (w_{i, f_j} \cdot w_{j, f_i}) x_i x_j \tag{3-1}$y(x)=w0​+i=1∑d​wi​xi​+i=1∑n​j=i+1∑n​(wi,fj​​⋅wj,fi​​)xi​xj​(3-1)
就是没有做onehot之前的特征，也就是说，$V_{NBC,G}$VNBC,G​无论是和$V_{Men,P}$VMen,P​还是和$V_{Women,P}$VWomen,P​相乘都取的是一个值。

FFM的表达式为
$y(\mathbf{x}) = w_0 + \sum_{i=1}^d w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n (w_{i, f_j} \cdot w_{j, f_i}) x_i x_j \tag{3-1}$y(x)=w0​+i=1∑d​wi​xi​+i=1∑n​j=i+1∑n​(wi,fj​​⋅wj,fi​​)xi​xj​(3-1)
变量的个数：1+n+kn(d-1),n代表onehot后特征的个数，d代表onehot前特征的个数