机器学习课程_笔记04

牛顿方法

首先假设存在一个函数f(\Theta)，然后算法的目标是找到一个\Theta，使得f(\Theta)=0。

牛顿方法的一次迭代： \Theta^{(t+1)}= \Theta^{(t)} - \frac {f(\Theta^{(t)})} {f'(\Theta^{(t)}) }

持续地迭代下去，就可以得到f(\Theta)=0。

同样的，假设现在存在一个函数\ell(\Theta)，也就是对数似然率，目标是找到一个\Theta，使得\ell(\Theta)最大化。可以容易想到\ell(\Theta)的一阶导数\ell'(\Theta)为0时，\ell(\Theta)即达到最大化了。

同样运用牛顿方法，其一次迭代： \Theta^{(t+1)} = \Theta^{(t)} - \frac {\ell'(\Theta^{(t)})} {\ell''(\Theta^{(t)})}

事实证明牛顿方法是一个收敛速度非常快的算法，它的收敛速度用术语可以描述为二次收敛。如果不考虑常量因子，牛顿方法的每一次迭代都会使你正在逼近的解的有效数字的数目加倍。当实现牛顿方法时，对于logistic回归来说通常会在十几次迭代之后收敛。

一般化的牛顿方法中，\Theta是一个向量，因而一般化的算法是这样的： \Theta^{(t+1)} = \Theta^{(t)} - H^{-1} \ell'(\Theta) 其中H​是Hessian矩阵，该矩阵中元素定义如下： H_{ij} = \frac {\partial^2 \ell} {\partial \Theta_i \partial \Theta_j} 通常情况下你会看到算法收敛一般情况下会执行十几次迭代，和梯度上升比起来算法收敛所需要的迭代次数要少得多。牛顿方法的缺点是每一次迭代你都需要重新计算一次Hession矩阵的逆，Hessian矩阵是一个(n+1)*(n+1)的矩阵，如果你要处理的问题中有大量的特征，将会花费很大的代价，但是对于规模较小 特征数量合理的问题，这通常情况下会是一个很快的算法。

广义线性模型

在线性回归中，服从高斯分布 P(y|X; \Theta) \sim N(\mu, \sigma^2) 在logistics回归中，服从伯努利分布 P(y|X;\Theta) \sim B(\phi) 上述两种分布只是都是一类分布的特例，这类分布被称为指数分布族。

指数分布族可以写成以下的形式： P(y;η)=b(y)exp(η^T T(y)-a(η)) 其中η被称为分布的自然参数，T(y)被称为充分统计量。

通常情况下，我们经常见到的许多例子里，包括伯努利分布和高斯分布，T(y)=y。

我们固定这三个函数a、b和T，那么这个公式就定义了一个概率分布的集合，它以η为参数，定义了一类概率分布。

这里推导一下分啥说伯努利分布、高斯分布都是指数分布族的特例。

推导伯努利分布

P(y=1;\phi) = \phi \\ P(y;\phi) = \phi^y (1 - \phi)^{1-y} \\ = exp(log\phi^y(1-\phi)^{1-y}) \\ = exp(ylog\phi + (1-y)log(1-\phi)) \\ = exp(log \frac \phi {1-\phi} y + log(1-\phi)) \\ = b(y)exp(η^T T(y)-a(η)) \quad where \quad b(y)=1, \quad η= log \frac \phi {1-\phi}, \quad T(y)=y, \quad a(η)=-log(1-\phi)

感觉上面的推导像在硬拼，呵呵。

推导高斯分布

N(\mu, \sigma^2) \quad assume \quad \sigma=1 \\ N(\mu, \sigma^2) = \frac 1 {\sqrt{2\pi}} (- \frac 1 2 (y - \mu)^2) \\ = \frac 1 {\sqrt{2\pi}} exp(- \frac 1 2 y^2)exp(\mu y - \frac 1 2 \mu^2) \\ = b(y)exp(η^T T(y)-a(η)) \quad where \quad b(y)=\frac 1 {\sqrt{2\pi}} exp(- \frac 1 2 y^2), \quad η= \mu, \quad T(y)=y, \quad a(η)=\frac 1 2 \mu^2 = \frac 1 2 η^2

感觉上面的推导像在硬拼，呵呵。

指数分布族推导出一个广义线性模型

广义线性模型通常被简写为GLM。

三个假设，也可以将它们看成是设计决策，这可以使我生成广义线性模型：

Assume: \quad y|X;\Theta \quad \sim ExpFamily(η) \\ Give \quad X, goal \quad is \quad to \quad output \quad ExpFamily[T(y)|X] , \quad Want \quad h(X) = ExpFamily[T(y)|X] \\ η=\Theta^T X

下面将伯努利分布推导出对应的广义线性模型

h_\Theta(X) = ExpFamily[T(y)|X; \Theta] = P(y=1|X;\Theta) = P(y=1;\phi) \\ =\phi \\ = \frac 1 {1+e^{-\mu}} \\ = \frac 1 {1+e^{-\Theta^T X}}

这里 g(η)=ExpFamily[y;η]=11+e−η

g(η)将自然参数η与y的期望值联系起来，这个函数被称为正则响应函数，而g^{-1}被称为正则关联函数。

多项式分布

多项式分布是指在k可能取值上的分布。

推导过程：

y \in {1, \cdots, k} \\ Parameters: \quad \phi_1,\phi_2,\cdots,\phi_k \\ P(y=i) = \phi_i \\ \sum_{i=1}^k P(y=i) = 1 \\ \phi_k = 1- \sum_{i=1}^{k-1} \phi_i \\ Assume \quad Parameters: \quad \phi_1,\phi_2,\cdots,\phi_{k-1} \\ T(1) = \begin{bmatrix}1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \quad T(k-1) = \begin{bmatrix}0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}, \quad T(k) = \begin{bmatrix}0 \\ 0 \\ \vdots \\ 0 \end{bmatrix} \in \mathbb R^{k-1} \\ \mathbb{1}\{True\} =1, \mathbb{1}\{False\} =0 \\ T(y)_i = \mathbb{1}\{y=i\} \\ P(y) = \phi^{\mathbb{1}\{y=1\}}\phi^{\mathbb{1}\{y=2\}}\cdots\phi^{\mathbb{1}\{y=k\}}\\ =\phi^{T(y)_{1}}\phi^{T(y)_{2}}\cdots\phi^{T(y)_{k-1}}\phi^{1-\sum_{j=1}^{k-1}T(y)_j} \\ = b(y)exp(η^T T(y)-a(η)) \quad where \quad b(y)=1, \quad η= \begin{bmatrix} log(\frac {\phi_1} {\phi_k}) \\ \vdots \\ log(\frac {\phi_{k-1}} {\phi_k}) \end{bmatrix} \in \mathbb R^{k-1}, \quad T(y)_i = \mathbb{1}\{y=i\}, \quad a(η)=-log(\phi_k)

这样就将概率分布从多项式分布的形式转化成了指数分布族的形式。

这里将η定义为\Theta的函数，求解这个式，最后得到这个结果：

\phi_i= \frac {e^η_i} {1+ \sum_{j=1}^{k-1} e^{η_j}} \quad Here \quad (i=1, \cdots, k-1) \\ = \frac {e^{\Theta_i^T X}} {1+ \sum_{j=1}^{k-1} e^{\Theta_j^T X}}

学习算法的假设函数就可以推导为：

h_\Theta(X) = ExpFamily[T(y)|X;\Theta] \\ = ExpFamily\left[ \begin{matrix} \mathbb 1\{j=1\} \\ \vdots \\ \mathbb 1\{j=k-1\} \end{matrix} \arrowvert X; \Theta \right] \\ = \begin{bmatrix} \phi_1 \\ \vdots \\ \phi_{k-1} \end{bmatrix} \\ = \begin{bmatrix} \frac {e^{\Theta_1^T X}} {1+ \sum_{j=1}^{k-1} e^{\Theta_j^T X}} \\ \vdots \\ \frac {e^{\Theta_{k-1}^T X}} {1+ \sum_{j=1}^{k-1} e^{\Theta_j^T X}} \end{bmatrix}

上述算法就叫softmax回归，是logistics回归的推广。

softmax回归的求解过程就可以归纳如下：

Assume \quad y \in \{1, \cdots, k\} \\ You \quad Have: \quad (X^{(1)}, y^{(1)}), \cdots, (X^{(m)}, y^{(m)}) \\ L(\Theta) = \Pi_{i=1}^m P(y^{(i)}|X^{(i)}; \Theta) \\ = \Pi_{i=1}^m \phi_1^{\mathbb 1 \{y^{(i)} = 1\}} \cdots \phi_k^{\mathbb 1 \{y^{(i)} = k\}} \quad Here \quad \begin{bmatrix} \phi_1 \\ \vdots \\ \phi_{k-1} \end{bmatrix} = \begin{bmatrix} \frac {e^{\Theta_1^T X}} {1+ \sum_{j=1}^{k-1} e^{\Theta_j^T X}} \\ \vdots \\ \frac {e^{\Theta_{k-1}^T X}} {1+ \sum_{j=1}^{k-1} e^{\Theta_j^T X}} \end{bmatrix}

然后使用极大似然估计法求出\Theta。