CS229 笔记 04

Nov 16 2017

Logistic Regression

  • Newton’s Method

    根据之前的讨论，在 Logistic Regression 中的一些符号有：

    $$ \begin{eqnarray*} P(y=1|x;\Theta)&=&h_\Theta(x)=\frac{1}{1+e^{-\Theta^{\rm T}x}} \\[1em] P(y|x;\Theta)&=&[h_\Theta(x)]^y[1-h_\Theta(x)]^{1-y} \\[1em] l(\Theta)&=&\log{L(\Theta)} \\[1em] &=&\sum_i^m{\log{P(y^{(i)}|x^{(i)};\Theta)}} \\[1em] &=&\sum_i^m{y^{(i)}\log{[h_\Theta(x^{(i)})]}+(1-y^{(i)})\log{[1-h_\Theta(x^{(i)})]}} \\[1em] \end{eqnarray*} $$

    与之前讨论的不同点在于参数 $\Theta$ 的迭代方式，在这里使用牛顿方法。为得到 $l(\Theta)$ 的最大值，只需要计算使得 $l^{‘}(\Theta)={\bf 0}$ 成立 $\Theta$ 。

    当 $\Theta$ 是一个标量时可以用以下方法计算：

    $$ \Theta^{t+1}=\Theta^{t}-\frac{h_\Theta^{'}(x)}{h_\Theta^{''}(x)} $$

    当 $\Theta$ 是一个向量时（设 $\Theta \in {\Bbb R}^{n+1}$）可以用以下方法计算（引用了第三篇笔记中的结论）：

    $$ \begin{eqnarray*} \Theta^{t+1}&=&\Theta^{t}-H^{-1}\nabla_\Theta l(\Theta) \\[1em] \nabla_\Theta l(\Theta)&=&\sum_i^m{\frac{2y^{(i)}-1}{1+e^{\Theta^{\rm T}x^{(i)}}}x^{(i)}} \\[1em] [H]_{pq}&\xlongequal{def}&\frac{\partial^2 l(\Theta)}{\partial \theta_p \partial \theta_q} \\[1em] &=&\frac{\partial}{\partial \theta_q}\frac{\partial l(\Theta)}{\partial \theta_p} \\[1em] &=&\frac{\partial}{\partial \theta_q}\sum_i^m{\frac{2y^{(i)}-1}{1+e^{\Theta^{\rm T}x^{(i)}}}x^{(i)}_p} \\[1em] &=&\sum_i^m\frac{e^{\Theta^{\rm T}x^{(i)}}(1-2y^{(i)})}{\left(1+e^{\Theta^{\rm T}x^{(i)}}\right)^2}x^{(i)}_px^{(i)}_q \\[1em] \therefore H&=&\sum_i^m\frac{e^{\Theta^{\rm T}x^{(i)}}(1-2y^{(i)})}{\left(1+e^{\Theta^{\rm T}x^{(i)}}\right)^2}x^{(i)}(x^{(i)})^{\rm T} \\[1em] \end{eqnarray*} $$

Exponential Family

  • Exponential Family

    $$ P(y;\eta)=b(y)\exp{\left[\eta^{\rm T}T(y)-a(\eta)\right]} $$

    $\eta$ ：Natural Parameter（自然参数）

    $T$ ：Sufficient Statistic（充分统计量），通常 $T(y)=y$

  • Bernoulli Distribution（伯努利分布）

    $$ \begin{eqnarray*} P(y;\phi)&=&\phi^y(1-\phi)^{1-y} \\[1em] &=&\exp\left\{\log\left[\phi^y(1-\phi)^{1-y}\right]\right\} \\[1em] &=&\exp\left[y\log\phi+(1-y)\log(1-\phi)\right] \\[1em] &=&\exp\left\{y[\log\phi-\log(1-\phi)]+\log(1-\phi)\right\} \\[1em] &=&\exp\left[\log\left(\frac{\phi}{1-\phi}\right) \cdot y+\log(1-\phi)\right] \\[1em] \end{eqnarray*} $$

    其中：

    $$ \begin{eqnarray*} \eta&=&\log\left(\frac{\phi}{1-\phi}\right) \\[1em] T(y)&=&y \\[1em] a(\eta)&=&-\log(1-\phi)\\[1em] b(y)&=&1 \end{eqnarray*} $$

    经过变换可得：

    $$ \begin{eqnarray*} \phi&=&\frac{1}{1+e^{-\eta}} \\[1em] a(\eta)&=&-\log(1-\phi) \\[1em] &=&-\log(1-\frac{1}{1+e^{-\eta}}) \\[1em] &=&\log(1+e^\eta) \\[1em] T(y)&=&y\\[1em] b(y)&=&1 \end{eqnarray*} $$

    可得到 Logistic Function（或称 Sigmoid Function）

  • Gaussian Distribution（高斯分布）

    假设 $y \sim {\scr N}(\mu, 1) $

    $$ \begin{eqnarray*} P(y)&=&\frac{1}{\sqrt2\pi}\exp\left[-\frac{1}{2}(y-\mu)^2\right] \\[1em] &=&\frac{1}{\sqrt2\pi}\exp\left(-\frac{1}{2}y^2+\mu y-\frac{1}{2}\mu^2\right) \\[1em] &=&\frac{1}{\sqrt2\pi}\exp\left(-\frac{1}{2}y^2\right)\exp\left(\mu y-\frac{1}{2}\mu^2\right) \\[1em] \end{eqnarray*} $$

    其中：

    $$ \begin{eqnarray*} b(y)&=&\frac{1}{\sqrt2\pi}\exp\left(-\frac{1}{2}y^2\right) \\[1em] \eta&=&\mu \\[1em] T(y)&=&y\\[1em] a(\eta)&=&-\frac{1}{2}\mu^2 \\[1em] &=&-\frac{1}{2}\eta^2 \\[1em] \end{eqnarray*} $$

  • Poisson Distribution（泊松分布）

    假设 $y \sim \pi(\mu, 1) $

    $$ \begin{eqnarray*} P(y)&=&\frac{e^{-\lambda}\lambda^y}{y!} \\[1em] &=&\frac{1}{y!}e^{-\lambda}e^{\log\lambda^y} \\[1em] &=&\frac{1}{y!}\exp(y\log\lambda-\lambda) \\[1em] \end{eqnarray*} $$

    其中：

    $$ \begin{eqnarray*} b(y)&=&\frac{1}{y!}\\[1em] T(y)&=&y\\[1em] \eta&=&\log\lambda\\[1em] a(\eta)&=&-\lambda\\[1em] &=&-e^\eta \end{eqnarray*} $$

  • Multinomial Distribution（多项分布）

    当 $y$ 服从多项分布时， $y \in {1,2,\cdots,k}$ 。

    多项分布的参数有 $\phi_1,\phi_2,\cdots,\phi_k$ ，因为 $\sum_i^k{\phi_i}=1$ ，所以 $\phi_k$ 可以省略。

    多项分布是少数的 $T(y) \neq y$ 的分布。 $T(y) \in {\Bbb R}^{k-1}$ ，其被定义为：

    $$ T(1)=\begin{bmatrix}1\\0\\\vdots\\0\end{bmatrix},T(2)=\begin{bmatrix}0\\1\\\vdots\\0\end{bmatrix},\cdots,T(k-1)=\begin{bmatrix}0\\0\\\vdots\\1\end{bmatrix},T(k)=\begin{bmatrix}0\\0\\\vdots\\0\end{bmatrix} $$

    再定义一个符号： $I{true}=1,I{false}=0$ 。

    $T(y)_i$ 表示 $T(y)$ 向量中的第 $i$ 个分量。

    概率密度函数为：$P(y=i)=\phi_i$ ，即：

    $$ \begin{eqnarray*} P(y)&=&\phi_1^{I\{y=1\}}\phi_2^{I\{y=2\}}\cdots\phi_k^{I\{y=k\}} \\[1em] &=&\phi_1^{T(y)_1}\phi_2^{T(y)_2}\cdots\phi_k^{1-\sum_{i=1}^{k-1}T(y)_i} \\[1em] &=&\exp\left\{\log\left[\phi_1^{T(y)_1}\phi_2^{T(y)_2}\cdots\phi_k^{1-\sum_{i=1}^{k-1}T(y)_i}\right]\right\} \\[1em] &=&\exp\left[T(y)_1\log\phi_1+T(y)_2\log\phi_2+\cdots+\left(1-\sum_{i=1}^{k-1}T(y)_i\right)\log\phi_k\right] \\[1em] &=&\exp\left[\sum_{i=1}^{k-1}T(y)_i\log\phi_i+\log\phi_k-\sum_{i=1}^{k-1}T(y)_i\log\phi_k\right] \\[1em] &=&\exp\left[\sum_{i=1}^{k-1}T(y)_i(\log\phi_i-\log\phi_k)+\log\phi_k\right] \\[1em] &=&\exp\left[\sum_{i=1}^{k-1}T(y)_i\log\frac{\phi_i}{\phi_k}+\log\phi_k\right] \\[1em] &=&\exp\left[\eta^{\rm T}T(y)+\log\phi_k\right] \\[1em] \end{eqnarray*} $$

    其中：

    $$ \eta=\begin{bmatrix}\log\frac{\phi_1}{\phi_k}\\\log\frac{\phi_2}{\phi_k}\\\vdots\\\log\frac{\phi_{k-1}}{\phi_k}\end{bmatrix} $$

    因为 $T(y)_i$ 当中只有一项为 1，其它为 0，所以 $\sum_{i=1}^{k-1}T(y)_i\log\frac{\phi_i}{\phi_k}$ 当中只会剩下一项 $T(y)_i\log\frac{\phi_i}{\phi_k}$ ，使用 $\eta^{\rm T}T(y)$ 正好能表示那一项。

    下面使用 $\eta$ 来表示 $\phi_k$ ：

    $$ \begin{eqnarray*} \eta_i&=&\log\frac{\phi_i}{\phi_k} \\[1em] \exp(\eta_i)&=&\frac{\phi_i}{\phi_k} \\[1em] \sum_{i=1}^{k-1}\exp(\eta_i)&=&\sum_{i=1}^{k-1}\frac{\phi_i}{\phi_k} \\[1em] \sum_{i=1}^{k-1}\exp(\eta_i)&=&\frac{1-\phi_k}{\phi_k} \\[1em] \phi_k&=&\frac{1}{1+\sum_{i=1}^{k-1}\exp(\eta_i)} \\[1em] \phi_i&=&\phi_k\exp(\eta_i) \\[1em] &=&\frac{\exp(\eta_i)}{1+\sum_{i=1}^{k-1}\exp(\eta_i)} \\[1em] \end{eqnarray*} $$

    所以：

    $$ \begin{eqnarray*} b(y)&=&1\\[1em] \eta&=&\begin{bmatrix}\log\frac{\phi_1}{\phi_k}\\\log\frac{\phi_2}{\phi_k}\\\vdots\\\log\frac{\phi_{k-1}}{\phi_k}\end{bmatrix}\\[1em] a(\eta)&=&-\log\phi_k \\[1em] &=&-\log\left(\frac{1}{1+\sum_{i=1}^{k-1}\exp(\eta_i)}\right) \\[1em] &=&\log\left(1+\sum_{i=1}^{k-1}\exp(\eta_i)\right) \\[1em] \end{eqnarray*} $$

Generalized Linear Models

当决定使用指数分布族来解决问题后，就会推导出一个广义的线性模型。

使用指数分布族需要有以下假设：

  1. $y$ 服从指数分布族中的某种分布，即 $y|x;\Theta \sim ExpFamily(\eta)$
  2. 给定一些样本 $x$ ，目标是估计对应的 $y$ ，$y$ 可以用充分统计量 $T(y)$ 来表示，所以问题就变成了估计 $T(y)$ 的期望，即 $h(x)=E[T(y)|x]$ 。
  3. 指数分布族中的参数 $\eta$ 与输入的特征（也就是输入的样本）$x$ 之间的关系是线性关系，即 $\eta=\Theta^{\rm T}x$ 。

以下是一些常见分布（在之前被证明了属于指数分布族的）的估计函数的推导过程：

  • Bernoulli Distribution（伯努利分布）-> Logistic Regression（逻辑回归）

    假设 $y|x;\Theta \sim ExpFamily(\eta)$ 中的伯努利分布，即：

    $$ \begin{eqnarray*} h_\Theta(x)&=&E[T(y)|x;\Theta] \\[1em] &=&P(y=1|x;\Theta) \\[1em] &=&\phi \\[1em] &=&\frac{1}{1+e^{-\eta}} \\[1em] &=&\frac{1}{1+e^{-\Theta^{\rm T}x}} \\[1em] \end{eqnarray*} $$

  • Gaussian Distribution（高斯分布）-> Least Square（最小二乘）

    假设 $y|x;\Theta \sim ExpFamily(\eta)$ 中的高斯分布，即：

    $$ \begin{eqnarray*} h_\Theta(x)&=&E[T(y)|x;\Theta] \\[1em] &=&\mu \\[1em] &=&\eta \\[1em] &=&\Theta^{\rm T}x \end{eqnarray*} $$

  • Multinomial Distribution（多项分布）-> Softmax Regression

    假设 $y|x;\Theta \sim ExpFamily(\eta)$ 中的多项分布，由于多项分布的参数 $\eta$ 是一个向量，所以 $\Theta$ 将会是一个矩阵， $\Theta \in {\Bbb R}^{(n+1)\times(k-1)}$ ，即 $\Theta_i \in {\Bbb R}^{(n+1)}$ , 则估计函数为：

    $$ \begin{eqnarray*} h_\Theta(x)&=&E[T(y)|x;\Theta] \\[1em] &=&\begin{bmatrix}\phi_1\\\phi_2\\\vdots\\\phi_{k-1}\end{bmatrix} \\[1em] &=&\begin{bmatrix}\frac{\exp(\eta_1)}{1+\sum_{i=1}^{k-1}\exp(\eta_i)}\\\frac{\exp(\eta_2)}{1+\sum_{i=1}^{k-1}\exp(\eta_i)}\\\vdots\\\frac{\exp(\eta_{k-1})}{1+\sum_{i=1}^{k-1}\exp(\eta_i)}\end{bmatrix} \\[1em] &=&\begin{bmatrix}\frac{\exp(\Theta_1^{\rm T}x)}{1+\sum_{i=1}^{k-1}\exp(\Theta_i^{\rm T}x)}\\\frac{\exp(\Theta_2^{\rm T}x)}{1+\sum_{i=1}^{k-1}\exp(\Theta_i^{\rm T}x)}\\\vdots\\\frac{\exp(\Theta_{k-1}^{\rm T}x)}{1+\sum_{i=1}^{k-1}\exp(\Theta_i^{\rm T}x)}\end{bmatrix} \\[1em] \end{eqnarray*} $$

Machine Learning