Logistic Regression

Logistic 回归分类器的思路为：我们把每个特征上都乘以一个系数，然后把所有结果值相加（还可能加上一个偏置量），将这个总和代入 Sigmoid 函数中，这将得到一个范围在 0 到 1 之间的数值，如果大于 0.5，则把数据归为 1 类；如果小于 0.5，则把数据归入 0 类。
即 Sigmoid 函数的输入由下式得到：
\[z = b + w^{(1)} x^{(1)} + w^{(2)} x^{(2)} + \cdots + w^{(n)} x^{(n)}\]
若把 \(w^{(0)}\) 当作 \(b\) ，把 \(x^{(0)}\) 当作 1。可记 \(\boldsymbol{w} = (b, w^{(1)}, w^{(2)}, \cdots, w^{(n)})^{\mathsf{T}}, \, \boldsymbol{x} = (1, x^{(1)}, x^{(2)}, \cdots, x^{(n)})^{\mathsf{T}}\) ，上式的向量形式为：
\[z = \boldsymbol{w}^{\mathsf{T}} \boldsymbol{x}\]

则 Logistic 回归模型可写为（下式中， \(\boldsymbol{w}\) 和 \(\boldsymbol{x}\) 都是向量）：
\[\sigma = \frac{1}{1+ e^{- \boldsymbol{w}^{\mathsf{T}} \boldsymbol{x}}}\]

Sigmoid 函数的输出值在 0 到 1 之间，所以 Logistic 回归可以看作是概率估计： Logistic 回归的输出看作是 \(y=1\) 的概率。
\[P(Y=1 \mid \boldsymbol{x}) = \frac{1}{1+ e^{- \boldsymbol{w}^{\mathsf{T}} \boldsymbol{x}}}\]

对于给定的输入数据 \(\boldsymbol{x}\) ，计算 \(P(Y=1 \mid \boldsymbol{x})\) ，Logistic 回归的思想就是比较 \(P(Y=1 \mid \boldsymbol{x})\) 和 0.5 的大小关系，大于 0.5 时把数据归到 \(y=1\) 的那类，否则归到 \(y=0\) 的那类。

如何通过训练数据集估计 Logistic 回归分类器的参数向量 \(\boldsymbol{w}\) 呢？

对于给定的训练数据集 \(T = \{ (\boldsymbol{x_1}, y_1), (\boldsymbol{x_2}, y_2), \cdots, (\boldsymbol{x_N}, y_N)\}\) ，其中， \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{0, 1\}\) ，我们可以利用极大似然估计求得模型参数的估计值。

记 \(\pi(\boldsymbol{x_i}) \overset{\text{def}}{=} \sigma = \dfrac{1}{1+ e^{- \boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}}}\) ，则有：

则训练数据集的似然函数为：
\[L(\boldsymbol{w}) = \prod_{i=1}^{N}\pi(\boldsymbol{x_i})^{y_i} (1 - \pi(\boldsymbol{x_i}))^{1 - y_i}\]

其对数似然函数为：
\[\begin{aligned} \ln L(\boldsymbol{w}) & = \sum_{i=1}^{N} \left[ y_i \ln \pi(\boldsymbol{x_i}) + (1 - y_i) \ln (1 - \pi(\boldsymbol{x_i})) \right] \\ & = \sum_{i=1}^{N} \left[ y_i \ln \frac{\pi(\boldsymbol{x_i})}{1 - \pi(\boldsymbol{x_i})} + \ln ( 1 - \pi(\boldsymbol{x_i})) \right] \\ & = \sum_{i=1}^{N} \left[ y_i \ln \frac{\frac{1}{1+ e^{- \boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}}}}{ 1- \frac{1}{1+ e^{- \boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}}}} + \ln (1 - \frac{1}{1+ e^{- \boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}}}) \right] \\ & = \sum_{i=1}^{N} \left[ y_i (\boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}) - \ln (1 + e^{\boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}}) \right] \end{aligned}\]

对上式求极大值，取极大值时对应的 \(\hat{\boldsymbol{w}}\) 就是 \(\boldsymbol{w}\) 的估计值。

对于最优化问题，我们习惯于解决极小化问题，对上式（对数似然函数）的极大化相当于极小化它的相反数，所以我们可以认为 Logistic 回归的损失函数为对数似然函数的相反数 ：
\[\begin{aligned} J(\boldsymbol{w}) & = - \sum_{i=1}^{N} \left[ y_i \ln \pi(\boldsymbol{x_i}) + (1 - y_i) \ln (1 - \pi(\boldsymbol{x_i})) \right] \\ & = - \sum_{i=1}^{N} \left[ y_i (\boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}) - \ln (1 + e^{\boldsymbol{w}^{\mathsf{T}} \boldsymbol{x_i}}) \right] \end{aligned}\]
对损失函数最小化，取极小值时对应的参数 \(\hat{\boldsymbol{w}}\) 就是 \(\boldsymbol{w}\) 的估计值。

交叉验证的思想是：模型在拟合过程中不使用全部的历史数据，而是保留一部分数据，用来模拟未来的数据，对模型进行检验。

过拟合一般使模型变得过于复杂。
什么是模型的复杂度呢？如果要给多项式拟合的模型定义复杂度，则可以认为多项式的次数越高模型越复杂，如 5 次多项式模型比 2 次多项式模型要复杂得多。

对于 Logistic 回归，我们可以用特征的权重来表示模型的复杂度。
这样，为了避免过拟合（模型太复杂），我们可以把所有权重之和（为了避免正负抵消，取权重的绝对值）放入到损失函数中。
如，重定义损失函数为：
\[J(\boldsymbol{w}) = - \sum_{i=1}^{N} \left[ y_i \ln \pi(\boldsymbol{x_i}) + (1 - y_i) \ln (1 - \pi(\boldsymbol{x_i})) \right] + \lambda \sum_{j=1}^{n} \left| w^{(j)} \right|\]
上式称为 L1 正则化(L1 regularization) 。式中， \(\lambda\) 用于调节正则化因子所占的比重。

还有其它正则化手段，如定义正则化因子为权重平方和，这称为 L2 正则化(L2 regularization) 。
\[\begin{aligned} J(\boldsymbol{w}) & = - \sum_{i=1}^{N} \left[ y_i \ln \pi(\boldsymbol{x_i}) + (1 - y_i) \ln (1 - \pi(\boldsymbol{x_i})) \right] + \lambda \sum_{j=1}^{n} {w^{(j)}}^2 \\ & = - \sum_{i=1}^{N} \left[ y_i \ln \pi(\boldsymbol{x_i}) + (1 - y_i) \ln (1 - \pi(\boldsymbol{x_i})) \right] + \lambda \boldsymbol{w}^{\mathsf{T}} \boldsymbol{w} \\ & = - \sum_{i=1}^{N} \left[ y_i \ln \pi(\boldsymbol{x_i}) + (1 - y_i) \ln (1 - \pi(\boldsymbol{x_i})) \right] + \lambda \Vert \boldsymbol{w} \Vert^2 \\ \end{aligned}\]

默认 Logistic 回归仅输出两个分类。怎么让它处理多个分类的情况呢？可以采用“one vs. rest”方法（也称为“one vs. all”方法）。

“one vs. rest”方法的描述如下：
对每一个类分别训练出一个唯一的分类器，如图 7 所示的例子中我们一共可得到 3 个分类器，如图 8 所示。 对于输入数据，分别计算每一个分类器下的输出值，取“输出值最大的那个分类器对应的类别”作为预测类别。

参考：
https://en.wikipedia.org/wiki/Multiclass_classification
http://www.holehouse.org/mlclass/06_Logistic_Regression.html

Softmax 回归是 Logistic 回归模型在多分类问题上的推广。

参考：http://deeplearning.stanford.edu/wiki/index.php/Softmax%E5%9B%9E%E5%BD%92

在信息论中，设离散随机变量 \(X\) 的概率分布为 \(P(X=x^{(i)}) = p_i, \, i=1,2,\cdots,n\) ，则概率分布 \(p\) 的熵(Entropy)的定义为：
\[H(p) = - \sum_{i=1}^{n} p_i \log p_i\]
当熵定义中对数以 2 或以 \(e\) 为底时，熵的单位分别称为“比特(bit)”或者“纳特(nat)”。

关于同一组事件 \(x^{(1)}, \cdots, x^{(n)}\) 的两个分布 \(p,q\) ，其交叉熵(Cross-Entropy)的定义如下：

当两个分布完全相同时，交叉熵取最小值 \(H(p)\) 。 交叉熵可以衡量两个分布之间的相似度，交叉熵越小两个分布越相似。

下面是交叉熵的应用实例（例子摘自http://www.cs.rochester.edu/u/james/CSC248/Lec6.pdf）。
假设离散随机变量 \(X\) 有 4 个可能取值 \(A,B,C,D\) ，它的真实分布为 \(p\) ，它有两个近似的分布 \(q1,q2\) ：

求 \(H(p, q1), H(p, q2)\) （对数取 2 为底）。
\[\begin{aligned} H(p, q1) & = - \sum_{i=1}^{n} p_i \log q1_i \\ & = - (0.4 \cdot \log 0.25 + 0.1 \cdot \log 0.25 + 0.25 \cdot \log 0.25 + 0.25 \cdot \log 0.25) \\ & = 2 \\ H(p, q2) & = - \sum_{i=1}^{n} p_i \log q2_i \\ & = - (0.4 \cdot \log 0.4 + 0.1 \cdot \log 0.1 + 0.25 \cdot \log 0.1 + 0.25 \cdot \log 0.4) \\ & = 2.02 \\ \end{aligned}\]
由于 \(H(p, q1)\) 更小，我们可以认为分布 \(q1\) 比 \(q2\) 更接近真实分布 \(p\) 。

在 Logistic 回归中， \(y \in \{0, 1\}\) 是训练数据类标记，记 \(\hat{y} = \ln \pi(\boldsymbol{x})\) 为模型的输出。
记 \(p\) 为真实模型（样本数据给定的模型）， \(q\) 是训练得到的模型。则有：
\[\begin{aligned} & p_{y=1} = y, \; p_{y=0} = 1 - y \\ & q_{y=1} = \hat{y}, \; q_{y=0} = 1 - \hat{y} \end{aligned}\]
我们可以使用交叉熵 \(H(p,q)\) 来度量 \(p\) 和 \(q\) 的相似度：
\[H(p,q) = - \sum_i p_i \log q_i = - [y \log \hat{y} + (1-y) \log (1- \hat{y})]\]
我们知道，交叉熵 \(H(p,q)\) 越小表明 \(p\) 和 \(q\) 越相似，当 \(p\) 和 \(q\) 完全相同时 \(H(p,q)\) 取最小值。所以 \(H(p,q)\) 可以作为“损失函数”。

设有 \(N\) 个训练数据，则所有训练数据的交叉熵之和为：

这和前文利用对数似然得到 Logistic 回归损失函数是一致的。Logistic 回归中， 对数似然损失(Log Likelihood Loss)函数就是交叉熵损失(Cross-Entropy Cost)函数。

参考：
https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_error_function_and_logistic_regression