2018-11-22 MNIST【1】softmax regression

1、前言：

mnist在Kaggle的方准确率演化过程

mnist数据集出现在视野里面时候是3年前，而这个比赛在2012年7月25号就上线了，本文的主要工作就是追随大神们这几年的脚步，复原对于本问题的详细解法以及研究思路演化路径。本文主要以文字为主，展示思路，具体内容可看连接。（忍不住又要开始敲一敲公式了。。）

mnist数据集合的几种方法：

92%：softmax回归。

97%：非线性模型：包括kNN，随机森林等

98-99%：SVM+非线性核or全连接的神经网络，再在二者基础上选择合理的参数。

99.5%：CNN LeNet5

99.5%以上需要更多的数据集合。所以我来代码复现下上面几种方法。综合对比下实际效果。在做之前，先明确下以下条件！

Warning！！The original dataset has 70000 images split in 60k train and 10k test. Kaggle splits the same dataset into 42k train and 28k test. Thus Kaggle's unknown test images are contained with known labels in the original dataset's training subset. Therefore, you can not train your models with the original MNIST dataset.详见数据集下载地址

2、方法测试

2.1 softmax回归

基础概念：指数分布族

2.1.1合适的预测函数

我们的问题是10分类问题，所以我们的目标值 $y^{(i)}$ 取值范围为： $y^{(i)} \in \{1,\ldots,K\}$ （不是0-9，这样的做法是比较好标记类比数并可清晰阐述相关问题），同时我们的输入 $x$ 是784（28×28）维的向量，目标是求出合适 $\theta$ ，以便找到我们的高纬度的线性边界 $\theta^{\top} x$ 。

基于我们的softmax函数（又称归一化指数函数）： $\sigma(x) _j=\frac{\exp(\theta^{(j)\top} x)}{ \sum_{j=1}^{K}{\exp(\theta^{(j)\top} x) }}$ ，得到我们的预测函数 $h_\theta(x)$ ：

$\begin{align}h_\theta(x) =\begin{bmatrix}P(y = 1 | x; \theta) \\P(y = 2 | x; \theta) \\\vdots \\P(y = K | x; \theta)\end{bmatrix}=\frac{1}{ \sum_{j=1}^{K}{\exp(\theta^{(j)\top} x) }}\begin{bmatrix}\exp(\theta^{(1)\top} x ) \\\exp(\theta^{(2)\top} x ) \\\vdots \\\exp(\theta^{(K)\top} x ) \\\end{bmatrix}\end{align}$

强调，数据较多情况下， $\sum_{j=1}^{K}{\exp(\theta^{(j)\top} x)}$ 很可能在出现 $\inf$ 的情况。所以要十分注意！！

softmax python实现代码

强调：softmax只是把我们输入的向量，映射到0-1空间，而且会突出数值比较的大的项，具体可以见下图。

图片来自台大李宏毅《一天搞懂深度学习》

上图中虽然看似没啥问题：实则溢出问题蕴含其中！假如 $z_1,z_2,z_3=1000,1000,10000$ 这样就会出现 $\inf$ 情况的产生！我程序编程实现中发现 $y$ 经过一轮迭代后，最大值可达到3,000,000额，着实有点大。那么怎么解决这个问题，其实用到了softmax函数的性质： $softmax(x) =softmax(x-a)$ ,证明过程如下：

$\begin{align}\sigma(x+a) _j&=\frac{\exp(\theta^{(j)\top} x+a)}{ \sum_{j=1}^{K}{\exp(\theta^{(j)\top} x+a) }} \\& = \frac{\exp(\theta^{(j)\top} x)\exp(a)}{\exp(a) \sum_{j=1}^{K}{\exp(\theta^{(j)\top} x) }} \\&=\sigma(x)_j\end{align}$

2.1.2 Cost Function

借鉴Logistic regression的方法，我们得到二分类的Cost Function：

$J(\theta) = -\left[ \sum_{i=1}^m y^{(i)} \log h_\theta(x^{(i)}) + (1-y^{(i)}) \log (1-h_\theta(x^{(i)})) \right]$

我们对 $J(\theta)$ 做个更形象化的改化：

$J(\theta) = - \left[ \sum_{i=1}^{m} \sum_{k=0}^{1} 1\left\{y^{(i)} = k\right\} \log P(y^{(i)} = k | x^{(i)} ; \theta) \right]$

这里 $1\{\hbox{a true statement}\}=1;1\{\hbox{a false statement}\}=0$

所以我们可以由此得到softmax的cost function（ $K$ 的取值变一下，以及 $h_\theta(x)$ 带入就可以了）。

$J(\theta) = - \left[ \sum_{i=1}^{m} \sum_{k=0}^{K} 1\left\{y^{(i)} = k\right\} \log P(y^{(i)} = k | x^{(i)} ; \theta^{(k)}) \right]$

J_\theta

的求法

2.1.3 Gradient Descent

既然损失函数差不多样子，那么内核（sigmoid和softmax）不同的两个函数偏导会不会也差不多呢？

先列出Logistic regression的 $\nabla_{\theta_j}J(\theta)$ 为：

$\nabla_{\theta_j}J(\theta) = \frac{1}{m} \sum_{i=1}^m(h_\theta( x^{(i)}) -y^{(i)}) x_{j}^{(i)}$

与Logistic regression的对单个 $\theta_j$ 求导不同，softmax regression需要对每个 $\theta^{(k)}$ 中的第 $j$ 个元素求偏导 $\frac{\partial J(\theta)}{\partial \theta_{j}^{(k)}}$ 。

求softmax的偏导 $\nabla_{\theta^{(k)}} J(\theta)$ 具体过程如下：

第一步将与 $j$ 相关或者无关的项拆分，这样便于求偏导

$\begin{align}\nabla_{\theta^{(k)}} J(\theta) = -\frac{1}{m}\left[ \sum_i^m \frac{\partial}{\partial\theta_j} (1\left\{y^{(i)} = j\right\} \log P(y^{(i)} = j | x^{(i)} ; \theta^{(j)})+\sum_{k\neq j}^K1\left\{y^{(i)} = k\right\} \log P(y^{(i)} = k | x^{(i)} ; \theta^{(k)})) \right]\end{align}$

针对 $\log$ 项进行化简计算

$\log P(y^{(i)} = j | x^{(i)} ; \theta^{(j)}) = \log\frac{\exp(\theta^{(j)\top} x)}{ \sum_{j=1}^{K}{\exp(\theta^{(j)\top} x) }}=\theta^{(j)\top} x-\log(\sum_{j=1}^{K}{\exp(\theta^{(j)\top} x) })$

得到：

$\begin{align}\end{align}$ $\begin{align}\nabla_{\theta^{(k)}} J(\theta) & = -\frac{1}{m}\left[ \sum_i^m((1\left\{y^{(i)} = j\right\} ( x^{(i)}- \frac{\exp(\theta^{(j)\top} x^{(i)})x^{(i)}}{ \sum_{l=1}^{K}{\exp(\theta^{(l)\top} x^{(i)}) }} ) + \sum_{k\neq j}^K1\left\{y^{(i)} = k\right\} ( -\frac{\exp(\theta^{(j)\top} x^{(i)})x^{(i)}}{ \sum_{l=1}^{K}{\exp(\theta^{(l)\top} x^{(i)}) }} ) \right] \\& = -\frac{1}{m}\left[ \sum_i^m(x^{(i)}( 1\left\{y^{(i)} = j\right\}- \frac{1\left\{y^{(i)} = j\right\} \exp(\theta^{(j)\top}x^{(i)})}{ \sum_{l=1}^{K}{\exp(\theta^{(l)\top} x^{(i)}) }} - \sum_{k\neq j}^K1\left\{y^{(i)} = k\right\} \frac{\exp(\theta^{(j)\top} x^{(i)})}{ \sum_{l=1}^{K}{\exp(\theta^{(l)\top} x^{(i)}) }} ) \right] \\&= - \frac{1}{m}\sum_{i=1}^{m}{ \left[ x^{(i)} \left( 1\{ y^{(i)} = k\} - P(y^{(i)} = k | x^{(i)}; \theta) \right) \right] }\end{align}$

超级类似的表达式有没有？？都是 $\sum (y-h(x))x$ 这种形式。

2.1.4 Redundant

softmax有个特性就是它的参数是冗余的。也就是说如果我们的目标参数并不唯一。证明方法就是从softmax方程中的参数向量 $\theta^{(k)}$ 中拿走 $\psi$ ，看是否还满足我的概率分布的要求，如果满足则证明有很多参数是满足我们的需求的。

$\begin{align}P(y^{(i)} = k | x^{(i)} ; \theta)&= \frac{\exp((\theta^{(k)}-\psi)^\top x^{(i)})}{\sum_{j=1}^K \exp( (\theta^{(j)}-\psi)^\top x^{(i)})} \\&= \frac{\exp(\theta^{(k)\top} x^{(i)}) \exp(-\psi^\top x^{(i)})}{\sum_{j=1}^K \exp(\theta^{(j)\top} x^{(i)}) \exp(-\psi^\top x^{(i)})} \\&= \frac{\exp(\theta^{(k)\top} x^{(i)})}{\sum_{j=1}^K \exp(\theta^{(j)\top} x^{(i)})}.\end{align}$

在实际应用中，为了使算法实现更简单清楚，往往保留所有参数，而不任意地将某一参数设置为 0。但此时我们需要对代价函数做一个改动：加入权重衰减。权重衰减可以解决 softmax 回归的参数冗余所带来的数值问题。

2.1.5 L2 regularization

正则化方法：防止过拟合，提高泛化能力！

在训练数据不够多时，或者overtraining时，常常会导致overfitting（过拟合）。其直观的表现如下图所示，随着训练过程的进行，模型复杂度增加，在training data上的error渐渐减小，但是在验证集上的error却反而渐渐增大——因为训练出来的网络过拟合了训练集，对训练集外的数据却不work。

关于过拟合的解释：过拟合的时候，拟合函数的系数往往非常大，为什么？如下图所示，过拟合，就是拟合函数需要顾忌每一个点，最终形成的拟合函数波动很大。在某些很小的区间里，函数值的变化很剧烈。这就意味着函数在某些小区间里的导数值（绝对值）非常大，由于自变量值可大可小，所以只有系数足够大，才能保证导数值很大。

过拟合

由此得到新的代价函数：

$J(\theta) = - \left[ \sum_{i=1}^{m} \sum_{k=0}^{K} 1\left\{y^{(i)} = k\right\} \log P(y^{(i)} = k | x^{(i)} ; \theta^{(k)}) \right]+\frac{\lambda }{2} \sum_{i=1}^{m}\sum_{k=1}^{K}\theta_{ik} ^2$

$\nabla_{\theta^{(k)}} J(\theta) = - \sum_{i=1}^{m}{ \left[ x^{(i)} \left( 1\{ y^{(i)} = k\} - P(y^{(i)} = k | x^{(i)}; \theta) \right) \right] }+\lambda \theta_j$