Learning From Data——Softmax Regression

Learning From Data是研究生修的一门课，其实也就是机器学习的另一种叫法。第一门课中介绍了Linear Regression，Logistic Regression，Softmax Regression.虽然前两个都学过，但是还是有一些收获，比如另外的解释方法等等。

Linear Regression

这次Linear Regression主要学习到的新的东西是，从概率角度来理解为什么使用Least Square.

假设目标函数是 \(Y = W^Tx+ \epsilon\)，其中\(\epsilon\)是N维向量.假设\(\epsilon\)是独立同分布（IID）的，而且满足高斯分布\(N(0,\sigma)\),则: \[ p(y_n|X_n,W) = \frac 1 {\sqrt{2\pi }\sigma } exp \left(-\frac{(Y_n - W^TX_n)^2}{2\sigma ^2} \right) \]

而出现这个样本的概率如下：

\(L(W) = p(Y|X,W) = \prod _{n=1}^N p(y_n|X_n,W)\).

我们想要求得最大概率估计（Maximum Likelihood Estimation）:\(W_{MLE} = argmax_W(L{W})\).

展开之前我们应该加个log，因为我们喜欢sum而不是prod。如下：

\[ \begin{array} {l} \log{L(W)} &= \sum _{n=1}^N(\log{\frac 1 {\sqrt {2 \pi} \sigma} }- \frac 1 {2\sigma ^2 } (Y_n - W^TX_n)^2 \log e )\\ &= m \log{\frac 1 {\sqrt {2 \pi }\sigma} } - \frac 1 {2\sigma ^2 } \sum_{n=1}^N (Y_n - W^TX_n)^2 \end{array} \]

所以，\(argmax_{W} (L(W)) = argmin_{W} (\sum_{n=1}^N (Y_n - W^TX_n)^2 )\).这也正是我们的cost function的定义。

Logistic Regression

Logistic Regression学习了从另一种角度思考得到另一种定义cost function的方法，当然最终效果是一致的。

之前的logsitic regression对于\(P(X_i \bigcap y_i)\)的估计如下： \[ P(X_i \bigcap y_i) =\frac {(y_i+1)} 2 P(X_i) \times P(y_i = +1|X_i) +\frac {(1 - y_i)} 2 P(X_i) \times (1 - P(y_i = +1|X_i)) \]

实际上有另外一种可以达到一样的效果,不过此时我们需要的就是另外一种对\(y\)的定义了：\(y \in {0,1}\): \[ P(X_i \bigcap y_i) = (P(X_i) \times P(y_i = 1|X_i))^{y_i} (P(X_i) \times (1 - P(y_i = 1|X_i)))^{1-y_i} \]

因此出现这个样本的概率为： \[ L(W) = \prod _{i=1}^N (P(X_i \bigcap y_i) = P(X_i) \times h_w(X_i) )^{y_i} (P(X_i) \times (1-h_W(X_i)))^{1-y_i} . \]

我们可以略去这些\(P(X_i)\),因为这是确定的而且也不是我们需要注意的。 这时候log之后，得到最后的cost funtion的形式与之前就有了一些不同：

\[ f(W) = -(\sum _{i=1}^N y_i \log h_W{X_i} + (1 - y_i)\log{ (1 -h_W{X_i})}) \]

接下来要做的就是求这个函数的梯度，但是为了看的清楚，首先说明下各个函数的意义：

\[ h_W(X) = \frac 1 {1 - e^{-g_W(X)} } \]

\[ g_W(X) = W^TX \]

求梯度过程如下：

\[ \begin{array}{l} \nabla f(W) &= -(\sum _{i=1} ^N (y_i log(h_W(X_i)) + (1-y_i) log(1-h_W(X_i))))\\ &= -(\sum_{i=1}^N \left[ \frac {y_i}{h_W(X_i)} - \frac {1-y_i}{1-h_W(X_i)} \right] h_W'(x))\\ &= -(\left[y_i + \frac {1-y_i}{e^{-g_W(X_i)} } \right] \frac {e^{-g_W(X_i)} }{1 - e^{-g_W(X_i)} } g_W'(X_i)) \\\ &= -(\left[ \frac 1 {1 - e^{-g_W(X_i)} } - y_i \frac {1 - e^{-g_W(X_i)} }{1 - e^{-g_W(X_i)} } \right] g_W'(X_i))\\ &=-(y_i - h_W(X_i))X_i \end{array} \]

而且这个cost function的好处是，利用梯度下降的时候它和线性回归的步骤是非常相似的,线性回归中：

\[ \frac {\partial f(W)}{\partial w_j} = \sum _{i=1}^N(y_i - g_{W}(X_i))x_{i,j}. \]

即 \[ \nabla f(W) = \sum_{i=1}^N (y_i - g_{W}(X_i))X_i. \]

最后回到两种不同的cost funtion，实际上两者本质没有太大的区别，只是negative，positive的标识数字不同。最后得到的结果可能也不一样，但是差距不会太大，都会得到比较理想的结果。

Softmax Regression

Softmax Regression是一种多维分类算法。依然是站在概率的角度来讨论。

假设共有k类，即\(y \in {1,...,k}\).我们先给出一个概率估计，之前得概率估计是logistic函数，现在我们给出另一种情况：

\[ h_W(X_i) = \left [ \begin{matrix} p(y_i = 1|X_i;W_1)\\ p(y_i=2|X_i;W_2)\\ ...\\ p(y_i=k|X_i;W_k) \end{matrix}\right] = \frac 1 {\sum _{j=1}^k e^{W_j^TX_i} } \left[\begin{matrix} e^{W_1^TX_i}\\ e^{W_2^TX_i}\\ ...\\ e^{W_k^TX_i} \end{matrix}\right] = softmax(W,X_i) \]

同时我们定义:\(softmax(z_i) = p{y = i|X,W} = \frac {e^{z_i} }{\sum _{j=1}{k} e^{z_j} }\)，此时\(i \in {1,...,k}\).

当然，W参数也会发生变化：

\[ W = \left[ \begin{matrix} -W_1^T-\\ -W_2^T-\\ ...\\ -W_k^T- \end{matrix} \right] \]

因此我们确定了给定\(W\)和\(X\)的时候，\(y\)的概率。

而出现当前样本的概率（我们忽略\(P(W,X)\),像之前一样它不会影响结果）： \[ L(W) = \prod_{i=1}^{N} P(y_i|X_i,W). \] 其实我们可以想象的是这个式子展开了后会很复杂，因为对\(y_i\)可能的各个情况也要连乘。不如先log好了：

\[ \begin {array}{l} F(W) = \log{L(W)} &= \sum_{i=1}^N \log {p(y_i|X_i,W) }\\ &= \sum_{i=1}^N \log{\prod_{j=1}^k p_{W_j}(j|X_i,W)^{\mathbf{1}\{y_i = j\} } }\\ &= \sum_{i=1}^N \sum_{j=1}^k \mathbf{1}\{y_i = j\} \log { \frac {e^{W_jX_i} }{\sum _{l=1}^k e^{W_l^TX_i} } } \end {array} \]

这个东西，其实我推算的时候对他的符号表示已经很头大了。但是它虽然复杂但原理不难懂，和logistic regression的道理基本上一样的。

最后，我们就是要求这个函数的梯度了。这个函数的梯度求解想必是非常复杂的，但是实际上没有想象的那么麻烦。最后的结果也非常的简单：

\[ \nabla _{W_j} F(W) = \sum _{i=1}^m \left( \mathbf{1}\{y_i = j\} \log {\frac {e^{W_j^TX_i} }{\sum _{l=1}^k e^{W_l^TX_i} } } + \mathbf{1}\{y_i \ne j\} \log {\frac {e^{W_{y_i}^TX_i} }{\sum _{l=1}^k e^{W_l^TX_i} } } \right) \]

我们仔细观察原式就可以化简上面的样子。为了简化后面的步骤，假设\(g(W_l) = W_l^TX_i\). 第一种情况$ {y_i = j}$：

\[ f_1(W) = \log {\frac {e^{g(W_j)} }{\sum_{l=1}^k e^{g(W_l)} } } \]

\[ \begin{array}{l} \nabla _{W_j} f_1(W) &= \frac {\sum_{l=1}^k e^{g(W_l)} }{e^{g(W_j)} } \cdot \frac { -e^{2g(W_j)}+ (\sum_{l=1}^k e^{W_l})e^{W_j} }{(\sum_{l=1}^k e^{g(W_l)})^2} \cdot g'(W_j)\\ &= \frac{\sum_{l=1}^k e^{g(W_l) - e^{g(W_j)} } }{\sum_{l=1}^k e^{g(W_l)} } \cdot g'(W_j) \\\ &= (1 - p(y_i = l|X_i,W))X_i \end{array} \]

第二种情况\(y_i \ne j\),假设\(y_i = q \ne j\):

\[ f_2(W) = \log {\frac {e^{g(W_q)} }{\sum_{l=1}^k e^{g(W_l)} } } \]

\[ \begin{array}{c} \nabla _{W_j} f_2(W) &=\frac {\sum_{l=1}^k e^{g(W_l)} }{e^{g(W_q)} } \cdot \frac { -e^{g(W_j) e^{g(W_q)} } }{(\sum_{l=1}^k e^{g(W_l)})^2} \cdot g'(W_j)\\ &= - p(y_i = l|X_i,W)X_i \end{array} \]

也是两种情况的差别只有前面是否加一个1。合并两种情况，可以得到：

\[ \nabla _{W_j} F(W) = \sum _{i=1} ^N [(\mathbf{1}\{y_i=j\} - p(y_i=l|X_i,W))X_i] \]

上面推出来的要注意是我们想要最大化的函数。

而cost funtion的梯度应该是： $_{i=1} ^N [(-{y_i=j} + p(y_i=l|X_i,W))X_i] $

对于softmax regression我们需要知道，它的参数\(W_j\)之间并不是独立的，因为各个概率加起来为1，有这个约束后实际上，只要知道\(k-1\)个参数，就可以确定这个模型。

实际上，可以很容易证明logistic regression 是 softmax regression的特殊情况。

以上就是上节课学到的所有新东西。