Logistics回归与Fisher线性判别分析

Logistic回归

阶跃函数

对于二分类任务来说，线性回归模型产生连续的预测值，需要将其转化为 $y\in \{0, 1\}$

最理想方式是将预测值 $z$ 带入如下的单位阶跃函数：
$y =\left\{ \begin{array}{l} 0 & z \leq 0 \\ 0.5 & z = 0 \\ 1 & z > 0 \end{array} \right.$
然而阶跃函数不连续、无法微分，于是找到替代函数（对数几率函数）：
$y = \frac{1}{1+e^{-x}}$
具体算法
1. 初始化模型，输入数据集：
  $D = \{ (x_1,y_1),...,(x_m,y_m)\} \in R^{m * d},y_i\in\{0,1\}$
2. 模型输出：
  - 初始化模型参数 $w \in R^{d}, b \in R$
  - 建立逻辑回归模型
    $p_1(x) = p(y = 1|x) = \frac{e^{w^Tx+b}}{1+e^{w^Tx+b}}\\ p_0(x) = p(y=0|x) = \frac{1}{1+e^{w^Tx+b}}$
    令 $\beta = (w,b),\tilde{x_i} = (x_i,1)$
    $p_1(x) = p(y = 1|x) = \frac{e^{\beta^T\tilde{x_i}}}{1+e^{\beta^T\tilde{x_i}}}\\ p_0(x) = p(y=0|x) = \frac{1}{1+e^{\beta^T\tilde{x_i}}} \\ \ln{\frac{p_1(x)}{p_0(x)}} = \beta^T\tilde{x_i}\\ \ln p_{0}(x) = \ln(1 - p_1(x)) = -\ln(1 + \beta^T\tilde{x_i})$
3. 令输出结果 $y_i$ 服从两点分布，有 $P(y_i|x_i,\beta) = p_1(x)^{y_i}(1 - p_(x))^{1 - y_i}$
  $\begin{array}{l}\ln P(y_i|x_i,\beta) \\ = y_i\ln p_1(x_i) + (1 - y_i)ln(1-p_1(x)) \\ = y_i\ln \frac{p_1(x)}{1-p_1(x)}+ \ln(1 - p_1(x))\\ = y_i \beta^T\tilde{x_i} -\ln(1 + \beta^T\tilde{x_i}) \end{array}$
  构造样本 $D = \{ (x_1,y_1),...,(x_m,y_m)\}$ 的对数似然函数
  $L(\beta) = \prod_{i=1}^mp(y_i|x_i,\beta)\\ -\ln L(\beta) = \Sigma_{i=1}^m(-y_i \beta^T\tilde{x_i} +\ln(1 + \beta^T\tilde{x_i}))$
  
  将负对数似然函数作为损失函数，求其最小值
  $\frac{\partial-\ln L(\beta)}{\partial\beta_j} = -\Sigma_{i=1}^m\tilde{x}_{ij}(y_i - p_1(\tilde{x}_i;\beta))\\ \frac{\partial^2{-\ln L(\beta)}}{\partial\beta_j\partial\beta_k^T} =- \Sigma_{i=1}^m\tilde{x}_i\tilde{x}_i^Tp_1(\tilde{x}_i;\beta)(1-p_1(\tilde{x}_i;\beta))$
  
  特别地有：
  $\frac{\partial^2{-\ln L(\beta)}}{\partial\beta_0\partial\beta_j^T} =- \Sigma_{i=1}^m\tilde{x}_ip_1(\tilde{x}_i;\beta)(1-p_1(\tilde{x}_i;\beta))\\ \frac{\partial^2{-\ln L(\beta)}}{\partial\beta_0\partial\beta_0^T} =- \Sigma_{i=1}^mp_1(\tilde{x}_i;\beta)(1-p_1(\tilde{x}_i;\beta))$
  令一阶导数等于0，通过数值方法求出 $\vec \beta$ 。
  
  再将 $\beta$ 带入二阶偏导数构成的 $Hesse$ 矩阵，若矩阵正定，则负对数似然函数在 $\vec \beta$ 处取得极小值
  
  将得到的 $\vec \beta$ 带入 $p_1(x)$ ，得到训练后的Logistic回归模型

梯度下降法

image-20200420223613139.png

Hesse矩阵

image-20200420224945921.png

牛顿法和拟牛顿法

image-20200420224646366.png

image-20200420224709214.png

image-20200420224730516.png

image-20200420224753994.png

Fisher 线性判别分析

线性判别分析(Linear Discriminant Analysis)，LDA是一种经典的线性学习方法，最早由Fisher提出，也称作“Fisher判别分析”
LDA的思想：给定训练样例集(包含两个特征)，设法将样例投影到一条直线上使得同类样例的投影点尽可能接近、异类样例投影点尽可能相互远离。在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别

image-20200420232430335.png

给定数据集 $D = \{(x_i,y_i)\}_{i=1}^m,y_i \in \{0,1\}$ ，令 $X_i,\mu_i,\Sigma_i$ 分别表示第 $i$ 类示例的集合、均值向量、协方差矩阵。若将数据投影到直线 $y = w^Tx$ 上，则两类样本的中心在直线上投影为 $w^T\Sigma_0w$ 和 $w^T\Sigma_1w$
要使得样例的投影点尽可能接近，可以使同类样例投影点的协方差 $w^T\Sigma_0w+w^T\Sigma_1w$ 尽可能小

要使得异类样例的投影点尽可能远离，即 $||w^T\mu_0-w^T\mu_1||^2$ 尽可能大，由此得到目标函数
$J = \frac{||w^T\mu_0-w^T\mu_1||^2}{w^T\Sigma_0w+w^T\Sigma_1w}=\frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w}$
定义“类内散度矩阵”
$S_w =\Sigma_0+\Sigma_1 = \Sigma_{x \in X_0}(x - \mu_0)(x - \mu_0)^T + \Sigma_{x \in X_0}(x - \mu_1)(x - \mu_1)^T$
定义“类间散度矩阵”
$S_b = (\mu_0 - \mu_1)(\mu_0 - \mu_1)^T$
目标函数重写为
$J = \frac{w^TS_bw}{w^TS_ww}$
即 $S_b$ 与 $S_w$ 的"广义瑞利商"
为了确定 $w$ ，由于分子分母均含有 $w$ ，因此 $J$ 与 $w$ 的模长无关而仅与其方向有关，得到等价的约束优化目标：
$min_w -w^TS_bw\\ s.t. w^TS_ww = 1$
利用拉格朗日乘子法
$L(w) = -w^TS_bw + \lambda (w^TS_ww - 1)\\ \frac{\partial L(w)}{\partial w} = 0 \\$
解得
$S_bw = \lambda(\mu_0 - \mu_1)\\ w = S_w^{-1}(\mu_0 - \mu_1)$
实践中通常对 $S_w$ 进行奇异值分解，分别求出分解矩阵的逆，进而求得 $S_w^{-1}$
推广到多分类问题，假定存在N个类，第 $i$ 类样例数为 $m_i$

定义“全局散度矩阵”
$S_t = S_b + S_w = \Sigma_{j=1}^N\Sigma_{i=1}^{m_j}(x_i - \bar \mu)(x_i - \bar \mu)^T$
定义“全局类内散度矩阵”
$S_w = \Sigma_{i=1}^{N}S_{w_i} = \Sigma_{i=1}^{N}\Sigma_{x \in X_i}(x - \mu_i)(x - \mu_i)^T$
由此得到“全局类间散度矩阵”
$S_b = S_t - S_w =\Sigma_{i=1}^Nm_i(\mu_i - \bar \mu)(\mu_i - \bar \mu)^T$
由此可知 $S_t,S_b,S_w$ 可以做到“知二推三”
多分类问题常见的优化目标
$\max_{W} \frac{tr(W^TS_bW)}{tr(W^TS_wW)}， W \in \mathbb R^{d * N-1}$
按照相似的拉格朗日乘数法，令 $\frac{\partial L(W)}{\partial W} = 0$ 得到
$S_bW = \lambda S_wW \\ W = \lambda S_b^{-1}S_wW$
$W$ 的闭式解恰好是 $S_b^{-1}S_w$ 的N-1个最大广义特征值对应的特征向量组成的矩阵
LDA可以被视为一种经典的监督降维技术，例如将二维的样本 $(x_i,y_i)$ 投影到一维直线 $y = w^Tx$ 上