CS229 笔记04

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*}
  \]