1. 首页
  2. 程序人生

40万亿“新基建”来了!程序员的新翻身机会终于也来了

0万亿“新基建”来了!程序员的新翻身机会终于也来了"

3月以来,“新基建” 成为热词,全国31个省份宣布未来投入“新基建”的投资总额已经超过40万亿!

这意味着,“新基建”所包含的七大领域:5G 基建、特高压、城际高速铁路和城际轨道交通、新能源汽车充电桩、大数据中心、人工智能、工业互联网,将迎来新的战略增长。

其中,人工智能在技术商业场景应用需求提升,产业规模将持续扩大。根据前瞻产业研究院预测,2020年我国人工智能市场规模增速45%,远超全球市场规模增速水平。

中央定调“新基建”,互联网大厂继续加码人工智能。然而,AI产业却面临着巨大的人才缺口!在这样的大环境下,如果你有志应聘相关的技术岗,只有苦练内功,趁早磨刀,比如认真刷题,才有可能在面试中致胜。

以下分享2个算法岗的经典面试题,选自《百面机器学习:算法工程师带你去面试》一书。

40万亿“新基建”来了!程序员的新翻身机会终于也来了

LDA (线性判别分析) 和 PCA 的区别与联系

首先将LDA 扩展到多类高维的情况,以和问题1 中PCA 的求解对应。假设有N 个类别,并需要最终将特征降维至d 维。因此,我们要找到一个d 维投影超平面40万亿“新基建”来了!程序员的新翻身机会终于也来了,使得投影后的样本点满足LDA 的目标—最大化类间距离和最小化类内距离。

回顾两个散度矩阵, 类内散度矩阵40万亿“新基建”来了!程序员的新翻身机会终于也来了在类别增加至N 时仍满足定义, 而之前两类问题的类间散度矩阵40万亿“新基建”来了!程序员的新翻身机会终于也来了在类别增加后就无法按照原始定义。图4.6 是三类样本的分布情况,其中40万亿“新基建”来了!程序员的新翻身机会终于也来了分别表示棕绿黄三类样本的中心,μ 表示这三个中心的均值(也即全部样本的中心),Swi 表示第i 类的类内散度。我们可以定义一个新的矩阵St,来表示全局整体的散度,称为全局散度矩阵

40万亿“新基建”来了!程序员的新翻身机会终于也来了

如果把全局散度定义为类内散度与类间散度之和,即St=Sb+Sw,那么类间散度矩阵可表示为

40万亿“新基建”来了!程序员的新翻身机会终于也来了

其中mj 是第j 个类别中的样本个数,N 是总的类别个数。从式(4.29)可以看出,类间散度表示的就是每个类别中心到全局中心的一种加权距离。我们最大化类间散度实际上优化的是每个类别的中心经过投影后离全局中心的投影足够远。

根据LDA 的原理,可以将最大化的目标定义为

40万亿“新基建”来了!程序员的新翻身机会终于也来了

其中W是需要求解的投影超平面,WTW=I,根据问题2 和问题3 中的部分结论,我们可以推导出最大化J(W) 对应了以下广义特征值求解的问题

40万亿“新基建”来了!程序员的新翻身机会终于也来了

求解最佳投影平面

40万亿“新基建”来了!程序员的新翻身机会终于也来了

即求解

40万亿“新基建”来了!程序员的新翻身机会终于也来了

矩阵特征值前d 大对应的特征向量组成的矩阵,这就将原始的特征空间投影到了新的d 维空间中。至此我们得到了与PCA 步骤类似,但具有多个类别标签高维数据的LDA 求解方法。

(1)计算数据集中每个类别样本的均值向量μj,及总体均值向量μ。

(2)计算类内散度矩阵Sw,全局散度矩阵St,并得到类间散度矩阵40万亿“新基建”来了!程序员的新翻身机会终于也来了

(3)对矩阵进行特征值分解,将特征值从大到小排列。

(4)取特征值前d 大的对应的特征向量40万亿“新基建”来了!程序员的新翻身机会终于也来了,通过以下映射将n 维样本映射到d 维

40万亿“新基建”来了!程序员的新翻身机会终于也来了

从PCA 和LDA 两种降维方法的求解过程来看,它们确实有着很大的相似性,但对应的原理却有所区别。

首先从目标出发,PCA 选择的是投影后数据方差最大的方向。由于它是无监督的,因此PCA 假设方差越大,信息量越多,用主成分来表示原始数据可以去除冗余的维度,达到降维。而LDA 选择的是投影后类内方差小、类间方差大的方向。其用到了类别标签信息,为了找到数据中具有判别性的维度,使得原始数据在这些方向上投影后,不同类别尽可能区分开。

举一个简单的例子,在语音识别中,我们想从一段音频中提取出人的语音信号,这时可以使用PCA 先进行降维,过滤掉一些固定频率(方差较小)的背景噪声。但如果我们的需求是从这段音频中区分出声音属于哪个人,那么我们应该使用LDA 对数据进行降维,使每个人的语音信号具有区分性。

另外,在人脸识别领域中,PCA 和LDA 都会被频繁使用。基于PCA 的人脸识别方法也称为特征脸(Eigenface)方法,该方法将人脸图像按行展开形成一个高维向量,对多个人脸特征的协方差矩阵做特征值分解,其中较大特征值对应的特征向量具有与人脸相似的形状,故称为特征脸。Eigenface for Recognition 一文中将人脸用7 个特征脸表示(见图4.7),于是可以把原始65536 维的图像特征瞬间降到7 维, 人脸识别在降维后的空间上进行。然而由于其利用PCA 进行降维,一般情况下保留的是最佳描述特征(主成分),而非分类特征。如果我们想要达到更好的人脸识别效果,应该用LDA 方法对数据集进行降维, 使得不同人脸在投影后的特征具有一定区分性。

40万亿“新基建”来了!程序员的新翻身机会终于也来了

从应用的角度,我们可以掌握一个基本的原则—对无监督的任务使用PCA 进行降维,对有监督的则应用LDA。

40万亿“新基建”来了!程序员的新翻身机会终于也来了

K-均值算法收敛性的证明

首先,我们需要知道K 均值聚类的迭代算法实际上是一种最大期望算法(Expectation-Maximization algorithm),简称EM 算法。EM 算法解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题。假设有m 个观察样本,模型的参数为θ,最大化对数似然函数可以写成如下形式:

40万亿“新基建”来了!程序员的新翻身机会终于也来了

当概率模型中含有无法被观测的隐含变量时,参数的最大似然估计变为:

40万亿“新基建”来了!程序员的新翻身机会终于也来了

由于z(i) 是未知的, 无法直接通过最大似然估计求解参数, 这时就需要利用EM 算法来求解。假设z(i) 对应的分布为

40万亿“新基建”来了!程序员的新翻身机会终于也来了

,并满足

40万亿“新基建”来了!程序员的新翻身机会终于也来了

。利用Jensen 不等式,可以得到:

40万亿“新基建”来了!程序员的新翻身机会终于也来了

要使上式中的等号成立,需要满足

40万亿“新基建”来了!程序员的新翻身机会终于也来了

,其中c 为常数,且满足

40万亿“新基建”来了!程序员的新翻身机会终于也来了

;因此,

40万亿“新基建”来了!程序员的新翻身机会终于也来了

,不等式右侧函数记为r(x|θ)。当等式成立时,我们相当于为待优化的函数找到了一个逼近的下界,然后通过最大化这个下界可以使得待优化函数向更好的方向改进。

图5.5 是一个θ 为一维的例子,其中棕色的曲线代表我们待优化的函数,记为f(θ),优化过程即为找到使得f(θ) 取值最大的θ。在当前θ 的取值下(即图中绿色的位置),可以计算40万亿“新基建”来了!程序员的新翻身机会终于也来了,此时不等式右侧的函数(记为r(x|θ))给出了优化函数的一个下界,如图中蓝色曲线所示,其中在θ 处两条曲线的取值时相等的。接下来找到使得r(x|θ) 最大化的参数θ′,即图中红色的位置,此时f(θ′) 的取值比f(θ)(绿色的位置处)有所提升。可以证明,f(θ′) ≥ r(x|θ)=f(θ),因此函数是单调的,而且40万亿“新基建”来了!程序员的新翻身机会终于也来了从而函数是有界的。根据函数单调有界必收敛的性质,EM 算法的收敛性得证。但是EM 算法只保证收敛到局部最优解。当函数为非凸时,以图5.5 为例,如果初始化在左边的区域时,则无法找到右侧的高点。40万亿“新基建”来了!程序员的新翻身机会终于也来了

由上面的推导,EM 算法框架可以总结如下,由以下两个步骤交替进行直到收敛(1)E 步骤:计算隐变量的期望

40万亿“新基建”来了!程序员的新翻身机会终于也来了

(2)M 步骤:最大化

40万亿“新基建”来了!程序员的新翻身机会终于也来了

剩下的事情就是说明K 均值算法与EM 算法的关系了。K 均值算法等价于用EM 算法求解以下含隐变量的最大似然问题:

40万亿“新基建”来了!程序员的新翻身机会终于也来了

其中

40万亿“新基建”来了!程序员的新翻身机会终于也来了

是模型的隐变量。直观地理解,就是当样本x 离第k个簇的中心点μk 距离最近时,概率正比于

40万亿“新基建”来了!程序员的新翻身机会终于也来了

,否则为0。

在E 步骤,计算

40万亿“新基建”来了!程序员的新翻身机会终于也来了

这等同于在K 均值算法中对于每一个点x(i) 找到当前最近的簇z(i)。

在M步骤,找到最优的参数40万亿“新基建”来了!程序员的新翻身机会终于也来了,使得似然函数最大:

40万亿“新基建”来了!程序员的新翻身机会终于也来了

经过推导可得

40万亿“新基建”来了!程序员的新翻身机会终于也来了

因此,这一步骤等同于找到最优的中心点40万亿“新基建”来了!程序员的新翻身机会终于也来了,使得损失函数40万亿“新基建”来了!程序员的新翻身机会终于也来了达到最小,此时每个样本x(i) 对应的簇z(i) 已确定,因此每个簇k 对应的最优中心点μk 可以由该簇中所有点的平均计算得到,这与K 均值算法中根据当前簇的分配更新聚类中心的步骤是等同的。

……以上是《百面机器学习:算法工程师带你去面试》中的部分精华。

本文来自投稿,不代表程序员编程网立场,如若转载,请注明出处:http://www.cxybcw.com/187628.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code