Logistic回归：定义
我们希望能找到一种方法，可以将分离超平面（来自感知机）这一概念与概率工具（来自最小二乘线性回归）相结合
线性判别分析需要两个假设，其一是\(y\sim {\rm Bern}(\pi)\)，其二是\(x|y \sim N(\mu, \Sigma)\)。而且\(w_0\)和\(w\)都需要巨大的计算量求解。考虑LDA的逻辑，对于给定的\(x\)，只有当\(\ln [p(y=1|x)/p(y=0|x)] > 0\)满足时，我们把它标记为\(y=1\)。但是LDA并不直接定义\(p(y|x)\)，而是将\(p(y)\)定义为伯努利分布，将\(p(x|y)\)按照自己希望的分布设计（例如定义为单个高斯分布），然后使用贝叶斯定律\(p(y|x) = p(x|y)p(y) / p(x)\)并消掉\(p(x)\)求出最后的值
因此，我们可以直接从\(p(y|x)\)入手。考虑之前提到的log odds \[ L = \ln \frac{p(y=+1|x)}{p(y=-1|x)} \] 可以注意到
- 如果$L >!!> 0 \(，则我们更有把握说\)y=+1$
- 如果$L <!!< 0 \(，则我们更有把握说\)y=-1$
- 如果\(L = 0\)，则都可以
而线性函数\(x^\mathsf{T}w + w_0\)可以满足我们的这些需求：
- 可以计算超平面跟向量的距离。用\((w, w_0)\)表示，为 \[ \left|\frac{x^\mathsf{T}w}{|\!|w|\!|_2} + \frac{w_0}{|\!|w|\!|_2}\right| \]
- 函数的符号可以指明\(x\)在超平面的哪一侧
- \(x\)远离/靠近\(H\)意味着我们的信心越强/越弱
因此我们可以用超平面来表示前面的log odds，即 \[ \ln \frac{p(y=+1|x)}{p(y=-1|x)} = x^\mathsf{T}w + w_0 \]
这里我们对\(w_0\)，\(w\)和\(x\)都没有任何假设，不像LDA有很多前提条件。
考虑到要有\(p(y=-1|x) = 1- p(y=+1|x)\)，可以解得 \[ p(y=+1|x) = \frac{\exp\{x^\mathsf{T}w + w_0\}}{1 + {\exp\{x^\mathsf{T}w + w_0\}}} = \sigma(x^\mathsf{T}w + w_0) \]
\(\sigma\)被称作是sigmoid函数
因此到这里我们可以得到完整的问题定义： 令 \[ w \leftarrow \left[\!\begin{array}{c} w_0 \\ w \end{array}\!\right],\ x \leftarrow \left[\!\begin{array}{c} 1 \\ x \end{array}\!\right] \] 令\((x_1, y_1), \ldots, (x_n, y_n)\)为一系列二元分类的数据集，且有\(y \in \{-1, +1\}\)，Logistic回归模型认为每个\(y_i\)都是独立生成的，而且有 \[ P(y_i = +1|x_i, w) = \sigma(x_i^\mathsf{T}w),\ \ \sigma(x_i;w) = \frac{e^{x_i^\mathsf{T}w}}{1 + e^{x_i^\mathsf{T}w}} \]
Logistic回归是一个判别方法（计算\(p(y|x)\)），LDA/Bayes分类器是生成方法（对\(x\)建模，计算\(p(x|y)\)和\(p(y)\)）
Logistic回归似然
记\(\sigma_i(w) = \sigma(x_i^\mathsf{T}w)\)，则\(y_1, \ldots, y_n\)的联合似然为 \[ \begin{align*} p(y_1, \ldots, y_n|x_1, \ldots, x_n,w) &= \prod_{i=1}^n p(y_i|x_i, w) \\ &= \prod_{i=1}^n \sigma_i(w)^{1(y_i = +1)}(1-\sigma_i(w))^{1(y_i = -1)} \end{align*} \]
式子可以进一步化简 \[ \begin{align*} &\frac{e^{y_ix_i^\mathsf{T}w}}{1 + e^{y_ix_i^\mathsf{T}w}} = \left(\frac{e^{x_i^\mathsf{T}w}}{1 + e^{x_i^\mathsf{T}w}}\right)^{1(y_i = +1)}\left(1-\frac{e^{x_i^\mathsf{T}w}}{1 + e^{x_i^\mathsf{T}w}}\right)^{1(y_i = -1)} \\ \rightarrow &\sigma_i(y_i\cdot w) = \sigma_i(w)^{1(y_i = +1)}(1-\sigma_i(w))^{1(y_i = -1)} \end{align*} \]
因此联合似然可以简写为 \[ p(y_1, \ldots, y_n|x_1, \ldots, x_n,w) = \prod_{i=1}^n \sigma_i(y_i \cdot w) \]
我们的目标是求\(w\)使得这个值最大化。其MLE解为 \[ \begin{align*} w_{\rm ML} &= {\rm arg}\max_w \sum_{i=1}^n \ln \sigma_i(y_i\cdot w) \\ &= {\rm arg}\max_w \mathcal{L} \end{align*} \]
该式也没有解析解，需要迭代求解。在第\(t\)步，有 \[ w^{(t+1)} = w^{(t)} + \eta \nabla_w \mathcal{L} \] 其中 \[ \nabla_w \mathcal{L} = \sum_{i=1}^n (1-\sigma_i(y_i \cdot w))y_ix_i \]
由于\(\sigma_i(y_i\cdot w)\)是分对的概率，因此\(1-\sigma_i(y_i \cdot w)\)是分错的概率。即每次梯度下降都会选取分错的点着重学习，修改\(w\)。实际上正确的点也有贡献，但是错误的点贡献更大，这点与感知机算法不同
如果某个超平面可以分离所有训练数据，那么\(||w||_2\)逼近\(\infty\)，即对每个\((x_i,y_i)\)都有\(\sigma_i(y_i,w) \rightarrow 1\)，可能会过拟合。因此我们也可以加一个\(\ell_2\)正则项\(\lambda w^\mathsf{T}w\)，最优权重变成了 \[ \begin{align*} w_{\rm MAP} &= {\rm arg}\max_w \sum_{i=1}^n \ln \sigma_i (y_i \cdot w) - \lambda w^\mathsf{T}w \\ &= {\rm arg}\max_w \sum_{i=1}^n \ln \sigma (y_i x_i^\mathsf{T} w) - \frac{\lambda}{2} w^\mathsf{T}w \end{align*} \]
这里正则项可以看做是\(w\)的先验，即\(w \sim N(0, \lambda^{-1}I)\)。后验为 \[ p(w|x, y) = \frac{p(w)\prod_{i=1}^n\sigma_i(y_i \cdot w)}{\int p(w)\prod_{i=1}^n\sigma_i(y_i \cdot w) dw } \] 这个式子无法直接求解，只能逼近
拉普拉斯近似
因为无法求解\(p(w|x,y)\)，所以只能退而求其次地选择一个分布来对其进行近似。可以说 \[ p(w|x,y) \approx {\rm Normal}(\mu, \Sigma) \] 现在就是要求解出\(\mu\)和\(\Sigma\)
做一个转化，可知 \[ p(w|x,y) = \frac{e^{\ln p(y,w|x)}}{\int e^{\ln p(y,w|x)} dw} \] 我们的目的是对\(\ln p(y,w|x)\)进行近似
令\(f(w) = \ln p(y,w|x)\)，则可以对其进行二阶Taylor展开。即对变量\(w \in \mathbb{R}^{d+1}\)，对任意一个点\(z \in \mathbb{R}^{d+1}\)，有 \[ f(w) \approx f(z) + (w-z)^\mathsf{T}\nabla f(z) + \frac{1}{2}(w-z)^\mathsf{T}(\nabla^2f(z))(w-z) \]
其中\(\nabla f(z)\)是\(\nabla_wf(w)|_z\)的缩写
在拉普拉斯近似中，\(z= w_{\rm MAP}\)
所以将上式代入，可得 \[ \begin{align*} p(w|x,y) &= \frac{e^{f(w)}}{\int e^{f(w)}dw} \\ &\approx \frac{e^{f(z) + (w-z)^\mathsf{T}\nabla f(z) + \frac{1}{2}(w-z)^\mathsf{T}(\nabla^2f(z))(w-z)}}{\int e^{f(z) + (w-z)^\mathsf{T}\nabla f(z) + \frac{1}{2}(w-z)^\mathsf{T}(\nabla^2f(z))(w-z)} dw} \end{align*} \]
这里\(f(z)\)与\(w\)无关，因此分母中可以把这一项从积分中提出来，然后与分子中的相同项约掉。而且由于\(w_{\rm MAP}\)的定义就是使\(\nabla f(w)\)为0 的\(w\)，因此将其代入，分子分母中一阶导数都为0，也可以消掉，所以上式相当于 \[ p(w|x,y) \approx \frac{e^{-\frac{1}{2}(w-w_{\rm MAP})^\mathsf{T}\left(-\nabla^2 \ln p(y, w_{\rm MAP}|x)\right)(w - w_{\rm MAP})}}{\int e^{-\frac{1}{2}(w-w_{\rm MAP})^\mathsf{T}\left(-\nabla^2 \ln p(y, w_{\rm MAP}|x)\right)(w - w_{\rm MAP})} dw} \] 可以看出这是一个多变量高斯分布，其中\(\mu = w_{\rm MAP}, \Sigma = \left(-\nabla^2 \ln p(y, w_{\rm MAP}|x)\right)^{-1}\)
其中 \[ \nabla^2 \ln p(y, w_{\rm MAP}|x) = -\lambda I - \sum_{i=1}^n \sigma (y_i \cdot x_i^\mathsf{T}w_{\rm MAP})\left(1 - \sigma (y_i \cdot x_i^\mathsf{T}w_{\rm MAP})\right)x_ix_i^\mathsf{T} \]
