CS229 Note1

只要是人都是依靠自己的知识与认知并且被之束缚生活着的，那就叫做现实。但是知识与认知是模糊不清的东西，现实也许只是镜中花水中月，人都是活在自己的执念中的。

这篇文章的主要内容包括梯度下降算法的数学原理，逻辑回归的推导，牛顿法的应用，如何构造一个广义线性模型。

梯度下降算法的数学原理

算法公式

$$\theta=\theta_0-\eta.\Delta f(\theta_0)$$

一阶泰勒展开

$$f(\theta) \approx f(\theta_ 0)+(\theta-\theta_0).\Delta f(\theta_0)$$

数学思想：曲线函数的线性拟合近似

$\theta-\theta_0$是微小矢量，其大小是步进长度$\eta$，为标量。$\theta-\theta_0$的单位向量用$v$表示。则

$$\theta-\theta_0=\eta v$$ $$f(\theta)\approx f(\theta_0)+\eta v.\Delta f(\theta_0)$$

我们希望每次$\theta$更新让$f(\theta)$变小。也就是说希望$f(\theta) < f(\theta_0)$

$$f(\theta)-f(\theta_0)\approx \eta v.\Delta f(\theta_0) < 0$$

$\eta$是标量

$$v.\Delta f(\theta_0) = ||\Delta f(\theta_0)||cos(\alpha)< 0$$

其中$v$是$\theta-\theta_0$的单位向量,其方向就是梯度下降算法中要前进的方向，从上式可以看出算法要前进的方向与当前梯度方向(当前梯度方向即当前是在上升还是在下降)完全相反时，即夹角$\alpha$为180度时，$f(\theta)$减小得最快。

$$v.\Delta f(\theta_0) = ||\Delta f(\theta_0)||cos(\pi)$$ $$v = -\frac{\Delta f(\theta_0)}{||\Delta f(\theta_0)||}$$

因为$||\Delta f(\theta_0)||$是标量，可以并入$\eta$。所以

$$\theta = \theta_0-\eta \Delta f(\theta_0)$$

局部加权线性回归

最小化

$$\sum_i w^{(i)}(y^{(i)}-\theta^Tx^{(i)})^2$$ $$w^{(i)}=exp(-\frac{(x^{(i)}-x)^2}{2\tau^2})$$

上式中参数$x$为新预测的样本特征数据，它是一个向量，参数控制了权值变化的速率
离$x$很近的样本，权值接近于1，而对于离$x$很远的样本，此时权值接近于0，这样就是在局部构成线性回归，它依赖的也只是周边的点

对于局部加权线性回归算法，每次进行预测都需要全部的训练数据（每次进行的预测得到不同的参数$\theta$)，没有固定的参数，是非参数算法

逻辑回归

假设函数

$$h_{\theta}(x)=g(\theta^Tx)=\frac{1}{1+e^{-\theta^Tx}}$$ $$g(z)=\frac{1}{1+e^{-z}}$$

该函数的实用属性：

$$\begin{align} g'(z)&=\frac{d}{dz}\frac{1}{1+e^{-z}}\\ &=\frac{1}{(1+e^{-z})^2}(e^{-z})\\ &=\frac{1}{1+e^{-z}}(1-\frac{1}{1+e^{-z}})\\ &=g(z)(1-g(z)) \end{align}$$

拟合参数

概率假设

$$p(y|x;\theta)=(h_{\theta}(x))^y(1-h_{\theta}(x))^{1-y}$$

对于所有训练集，最大似然估计

$$\begin{align} L(\theta) &= p(\overrightarrow{y}|X;\theta)\\ &=\prod_{i=1}^m p(y^{(i)}|x^{(i)};\theta)\\ &=\prod_{i=1}^m (h_\theta(x^{(i)}))^{y^{(i)}}(1-h_\theta(x^{(i)}))^{1-y^{(i)}} \end{align}$$

对似然函数取log进行最大化

$$\ell(\theta)=log(L(\theta))=\sum_{i=1}^{m}y^{(i)}logh(x^{(i)})+(1-y^{(i)})log(1-h(x^{(i)}))$$

使用梯度上升

$$\begin{align} \frac{\delta}{\delta\theta_j}\ell(\theta)&=(y\frac{1}{g(\theta^Tx)}-(1-y)\frac{1}{1-g(\theta^Tx)})\\ &=(y\frac{1}{g(\theta^Tx)}-(1-y)\frac{1}{1-g(\theta^Tx)})g(\theta^Tx)(1-g(\theta^Tx))\frac{\delta}{\delta\theta_j}\theta^Tx\\ &=(y(1-g(\theta^Tx))-(1-y)g(\theta^Tx))x_j\\ &=(y-h_\theta(x))x_j \end{align}$$ $$\theta_j:=\theta_j + \alpha(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$$

牛顿法

求函数的零点

$$\theta:=\theta-\frac{f(\theta)}{f'(\theta)}$$

当我们想最大化似然函数$\ell(\theta)$(如逻辑回归)，即求$\ell’(\theta)$的零点。所以

$$\theta:=\theta-\frac{\ell'(\theta)}{\ell''(\theta)}$$

在逻辑回归里，$\theta$是一个向量。 牛顿法在多维环境下的泛化为：

$$\theta:=\theta-H^{-1}\Delta \ell(\theta)$$ $$H_{ij}=\frac{\delta^2\ell(\theta)}{\delta\theta_i\delta\theta_j}$$

其中，$\Delta\ell(\theta)$是$\ell(\theta)$在$\theta_i$维的偏导数的向量，H是$\ell(\theta)$对每一维求二阶导数的矩阵。

广义线性模型

指数分布族

$$p(y;\eta)=b(y)exp(\eta^TT(y)-a(\eta))$$

$\eta$是自然参数(natural parameter)
$T(y)$是充分统计量(sufficient statistic)
伯努利分布和高斯分布都是指数分布族的特例

伯努利分布

\begin{align}
p(y;\phi)&=\phi^y(1-\phi)^{1-y}\\
&=exp(ylog\phi+(1-y)log(1-\phi))\\
&=exp((log(\frac{\phi}{1-\phi}))y+log(1-\phi))
\end{align}

$$\eta=log(\frac{\phi}{1-\phi})$$ $$T(y)=y$$ $$a(\eta)=-log(1-\phi)=log(1+e^\eta)$$ $$b(y)=1$$

高斯分布

\begin{align}
p(y;u)&=\frac{1}{\sqrt{2\pi}}exp(-\frac{1}{2}(y-u)^2)\\
&=\frac{1}{\sqrt{2\pi}}exp(-\frac{1}{2}y^2).exp(uy-\frac{1}{2}u^2)
\end{align}
注:$\sigma$的值不影响最终的参数收敛，所以这里取1方便理解

$$\eta=u$$ $$T(y)=y$$ $$a(\eta)=\frac{u^2}{2}=\frac{\eta^2}{2}$$ $$b(y)=(\frac{1}{\sqrt{2\pi}})exp(-y^2/2)$$

构造广义线性模型

对于通过f(x)来预测随机变量y的值的问题（分类或者回归），要构造广义线性模型，y给定x的条件分布要满足以下三个条件。

1. $y|x;\theta $~ExponentialFamily$(\eta)$,给定$x$和$\theta$，$y$的分布遵从指数族分布，自然参数为$\eta$
2. 给定$x$，目标是预测$T(y)$，在大多数例子里$T(y)=y$，这意味着$h(x)=E[y|x]$（预测$h(x)$是x条件下y发生的期望）
3. 自然参数$\eta$与输入$x$是线性相关的：$\eta=\theta^Tx$
   第三个条件通常被认为是“构造GLM的选择”而不是“构造GLM的假设”(PS：我也没从讲义里看到这个的推导)

普通最小二乘(线性回归)

给定x，y服从高斯分布$N(u,\sigma^2)$，前面已证明高斯分布是指数分布族的特例，满足了广义线性模型第一个条件。有$u=\eta$

$$h_\theta(x)=E(y|x;\theta)=u=\eta=\theta^T x$$

第一个等式满足了广义线性模型的第二个条件。
第二个等式是高斯分布的特性，第三个等式是之前(高斯分布是指数分布族)推导出来的，第四个等式满足第三个条件。

逻辑回归

给定x，y服从伯努利分布，$\phi=\frac{1}{1+e^{-\eta}}$,$E[y|x;\theta]=\phi$
\begin{align}
h_\theta(x) &= E[y|x;\theta]\\
&=\phi \\
&= \frac{1}{1+e^{-\eta}}\\
&= \frac{1}{1+e^{-\theta^Tx}}
\end{align}
所以，逻辑回归sigmod函数的形式是广义线性模型与指数分布族的定义的结果。

Softmax Regression

多分类问题，response variable仍然是离散的，但是不止两个，首先推导这个分布属于指数分布族。
使用k个参数$\phi_1,…,\phi_k$来指定每一个输出的概率。实际上只需要k-1个参数，因为他们的概率都是相互独立的且和为1.

$$\phi_k=1-\sum_{i=1}^{k-1}\phi_i$$

定义$T(y)$为$T(y)\in R^{k-1}$,只有$T[y]_i=1$，其余元素都为0($i$代表$T(y)$属于哪一类的序号).
引入符号$1\lbrace True\rbrace =1,1\lbrace False\rbrace =0$
所以$T(y)$与$y$之间的关系可以描述为

$$(T(y))_i=1\lbrace y=i \rbrace$$

即$T(y)$属于第$i$类时（即第$i$个元素为1），$i$与$y$相等
现在开始推导该分布属于指数分布族

$$\begin{align} p(y;\phi) &= \phi_i^{1\lbrace y=1 \rbrace}\phi_2^{1\lbrace y=2 \rbrace}...\phi_k^1{\lbrace y=k \rbrace}\\ &=\phi_1^{(T(y))_1}...\phi_k^{1-\sum_{i=1}^{k-1}(T(y))_i}\\ &=exp((T(y))_1log(\phi_1)+(T(y))_2log(\phi_2)+...+(1-\sum_{i=1}^{k-1}(T(y))_i)+log(\phi_k))\\ &=exp((T(y))_1log(\phi_1/\phi_k)+...+(T(y))_{k-1}log(\phi_{k-1}{\phi_k})+log(\phi_k))\\ &=b(y)exp(\eta^T T(y)-a\eta) \end{align}$$ $$\eta = \begin{bmatrix} log(\phi_1/\phi_k) \\ ... \\ log(\phi_{k-1}/\phi_k) \\ \end{bmatrix}$$ $$a(\eta)=-log(\phi_k)$$ $$b(y)=1$$

link function

$$\eta_i=log\frac{\phi_i}{\phi_k}$$ $$e^{\eta_i} = \frac{\phi_i}{\phi_k}$$ $$\phi_k\sum_{i=1}^ke^{n_i}=\sum_{i=1}^k\phi_i=1$$

response(softmax) function

$$\phi_i=\frac{e^{\eta_i}}{\sum_{j=1}^ke^{\eta_j}}=\frac{e^{\theta_i^{T}x}}{\sum_{j=1}^{k}e^{\theta_j^Tx}}=p(y=i|x;\theta)$$

参数拟合

$$\begin{align} \ell(\theta) &= \sum_{i=1}^{m}logp(y^{(i)}|x^{(i)};\theta) &= \sum_{i=1}^{m}log\prod_{i=1}^k(\frac{e^{\theta_l^Tx^{(i)}}}{\sum_{j=1}^{k}e^{\theta_l^{T}x^{(i)}}})^{1\lbrace y^{(i)}=l \rbrace} \end{align}$$

然后使用梯度上升或者牛顿法来解决。