机器学习课程_笔记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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

赋予人工智能记忆的人,带你梳理深度学习核心算法

作者介绍:Jürgen Schmidhuber 被称为是赋予人工智能记忆的人,递归神经网络之父,2004 年到 2009 年,担任慕尼黑大学认知与机器人领域的教...

37470
来自专栏人工智能

评分卡系列(二):特征工程

文章很长,理论和实现都讲的很细,大家可以先收藏,有时间再看。 在上一篇文章中,我们对LendingClub的数据有了一个大致的了解,这次我将带大家把10万多条、...

86970
来自专栏机器学习算法与Python学习

深度学习领域引用量最多的前20篇论文简介

19950
来自专栏Petrichor的专栏

深度学习: Zero-shot Learning / One-shot Learning / Few-shot Learning

在 迁移学习 中,由于传统深度学习的 学习能力弱,往往需要 海量数据 和 反复训练 才能修得 泛化神功 。为了 “多快好省” 地通往炼丹之路,炼丹师们开始研究 ...

41830
来自专栏机器学习算法原理与实践

SimRank协同过滤推荐算法

    在协同过滤推荐算法总结中,我们讲到了用图模型做协同过滤的方法,包括SimRank系列算法和马尔科夫链系列算法。现在我们就对SimRank算法在推荐系统的...

37610
来自专栏机器学习算法与Python学习

干货 | 条件随机场详解之模型篇

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 条件随机场部分分为两篇讲解,今天这一...

29630
来自专栏智能计算时代

统计学基础知识

1.统计学基本概念 统计学:收集、处理、分析、解释数据并从中得出结论的科学。 数据分析的方法可分为描述统计和推断统计。 ? ? ...

31250
来自专栏机器学习算法与Python学习

推荐|深度学习领域引用最多的20篇论文,建议收藏!

深度学习是机器学习和统计学交叉领域的一个子集,在过去的几年里得到快速的发展。强大的开源工具以及大数据爆发使其取得令人惊讶的突破进展。本文根据微软学术(acade...

19250
来自专栏CDA数据分析师

Python环境下的8种简单线性回归算法

本文中,作者讨论了 8 种在 Python 环境下进行简单线性回归计算的算法,不过没有讨论其性能的好坏,而是对比了其相对计算复杂度的度量。 GitHub 地址:...

20090
来自专栏数据魔术师

运筹学教学|Benders decomposition(一)技术介绍篇

相约女神节 biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 Benders decompositi...

1.6K60

扫码关注云+社区

领取腾讯云代金券