牛客网算法八股刷题系列(十)再回首——线性判别分析与核函数

news/2024/3/29 16:44:53/文章来源:https://blog.csdn.net/qq_34758157/article/details/130367059

牛客网算法八股刷题系列——线性判别分析与核函数

题目描述

下面哪些是基于的机器学习算法(多选) ? ( ) ?(\quad) ?()

A Expectation Maximization \mathcal A \quad \text{Expectation Maximization} AExpectation Maximization

B Radial Basis Function \mathcal B \quad \text{Radial Basis Function} BRadial Basis Function

C Linear Discriminate Analysis \mathcal C \quad \text{Linear Discriminate Analysis} CLinear Discriminate Analysis

D Support Vector Machine \mathcal D \quad \text{Support Vector Machine} DSupport Vector Machine

正确答案: B C D \mathcal B\mathcal C\mathcal D BCD

题目解析

在刷题系列(五)——过拟合、模型复杂度与核函数中对核函数的描述是特征转换后的样本之间内积的一种方式:
κ ( x ( i ) , x ( j ) ) = [ ϕ ( x ( i ) ) ] T ⋅ ϕ ( x ( j ) ) ( x ( i ) , x ( j ) ∈ X ) \kappa(x^{(i)},x^{(j)}) = [\phi(x^{(i)})]^T \cdot \phi(x^{(j)}) \quad (x^{(i)},x^{(j)} \in \mathcal X) κ(x(i),x(j))=[ϕ(x(i))]Tϕ(x(j))(x(i),x(j)X)

从更泛化的角度观察,它实际上就是两个高维向量内积的一种表达方式。也就是说,更重要的是内积:因为如线性核函数 ( Linear Kernel ) (\text{Linear Kernel}) (Linear Kernel)并没有改变样本特征的维度信息。下面观察 4 4 4个选项,哪些选项中出现了内积现象

关于 A \mathcal A \quad A 选项,我们介绍过 EM \text{EM} EM算法 ( Expectation Maximization ) (\text{Expectation Maximization}) (Expectation Maximization)关于参数的优化过程:
θ ^ = arg ⁡ max ⁡ θ log ⁡ P ( X ∣ θ ) ⇔ arg ⁡ max ⁡ θ ∫ Z Q ( Z ) log ⁡ P ( X , Z ∣ θ ) Q ( Z ) d Z ⏟ ELBO \begin{aligned} \hat \theta & = \mathop{\arg\max}\limits_{\theta} \log \mathcal P(\mathcal X \mid \theta) \\ & \Leftrightarrow \mathop{\arg\max}\limits_{\theta} \underbrace{\int_{\mathcal Z} \mathcal Q(\mathcal Z) \log \frac{\mathcal P(\mathcal X,\mathcal Z \mid \theta)}{\mathcal Q(\mathcal Z)} d\mathcal Z}_{\text{ELBO}} \end{aligned} θ^=θargmaxlogP(Xθ)θargmaxELBO ZQ(Z)logQ(Z)P(X,Zθ)dZ
其中 Z \mathcal Z Z是模型中与观测变量相对的隐变量 ( Latent Variable ) (\text{Latent Variable}) (Latent Variable)。即便我们将 log ⁡ P ( X ∣ θ ) \log \mathcal P(\mathcal X\mid \theta) logP(Xθ)按照样本角度进行展开:
这里 z ( i ) z^{(i)} z(i)则表示:模型中 x ( i ) x^{(i)} x(i)作为输入样本的条件下,模型中被激活的隐变量。它包含模型中所有隐变量分量,但仅对 x ( i ) x^{(i)} x(i)一个样本的服务结果。
θ ^ = arg ⁡ max ⁡ θ ∑ i = 1 N [ ∫ z ( i ) Q ( z ( i ) ) log ⁡ P ( x ( i ) , z ( i ) ∣ θ ) Q ( z ( i ) ) d z ( i ) ] \hat \theta = \mathop{\arg\max}\limits_{\theta} \sum_{i=1}^N \left[\int_{z^{(i)}} \mathcal Q(z^{(i)}) \log \frac{\mathcal P(x^{(i)},z^{(i)} \mid \theta)}{\mathcal Q(z^{(i)})} dz^{(i)}\right] θ^=θargmaxi=1N[z(i)Q(z(i))logQ(z(i))P(x(i),z(i)θ)dz(i)]
我们依然没有发现内积现象。因此, EM \text{EM} EM算法不是基于核的机器学习算法。

关于 B \mathcal B \quad B 选项,径向基核函数 ( Radial Basis Function,RBF ) (\text{Radial Basis Function,RBF}) (Radial Basis Function,RBF),也就是高斯核函数,它就是一种描述高维向量内积的方式:
其中系数 1 2 σ 2 \begin{aligned}\frac{1}{2\sigma^2}\end{aligned} 2σ21不影响内积运算的复杂度,仅是各元素少了一个系数。
κ ( x ( i ) , x ( j ) ) = exp ⁡ { − 1 2 σ 2 ∣ ∣ x ( i ) − x ( j ) ∣ ∣ 2 } ⇒ exp ⁡ { − ∣ ∣ x ( i ) − x ( j ) ∣ ∣ 2 } = ϕ ( x ( i ) ) ⋅ ϕ ( x ( j ) ) \begin{aligned} \kappa(x^{(i)},x^{(j)}) & = \exp \left\{-\frac{1}{2\sigma^2} ||x^{(i)} - x^{(j)}||^2\right\} \\ & \Rightarrow \exp \left\{- ||x^{(i)} - x^{(j)}||^2\right\} \\ & = \phi(x^{(i)}) \cdot \phi(x^{(j)}) \end{aligned} κ(x(i),x(j))=exp{2σ21∣∣x(i)x(j)2}exp{∣∣x(i)x(j)2}=ϕ(x(i))ϕ(x(j))
其中:
使用‘泰勒公式’的展开结果。
{ ϕ ( x ( i ) ) = exp ⁡ [ − ( x ( i ) ) 2 ] ⋅ ∑ m = 0 ∞ 2 m m ! ( x ( i ) ) m ϕ ( x ( j ) ) = exp ⁡ [ − ( x ( j ) ) 2 ] ⋅ ∑ m = 0 ∞ 2 m m ! ( x ( j ) ) m \begin{cases} \begin{aligned} \phi(x^{(i)}) = \exp [-(x^{(i)})^2] \cdot \sum_{m=0}^{\infty} \sqrt{\frac{2^m}{m!}}(x^{(i)})^m \end{aligned} \\ \begin{aligned} \phi(x^{(j)}) = \exp [-(x^{(j)})^2] \cdot \sum_{m=0}^{\infty} \sqrt{\frac{2^m}{m!}}(x^{(j)})^m \end{aligned} \end{cases} ϕ(x(i))=exp[(x(i))2]m=0m!2m (x(i))mϕ(x(j))=exp[(x(j))2]m=0m!2m (x(j))m
因此,它可以表示为高维向量内积的形式。

关于 C \mathcal C \quad C 选项:我们在线性分类中介绍过它的参数求解过程。其中线性判别分析关于参考系/投影方向 W \mathcal W W的策略/损失函数表示如下:
J ( W ) = W T ( X C 1 ˉ − X C 2 ˉ ) ( X C 1 ˉ − X C 2 ˉ ) T W W T ( S C 1 + S C 2 ) W \mathcal J(\mathcal W) = \frac{\mathcal W^T(\bar{\mathcal X_{\mathcal C_1}} - \bar{\mathcal X_{\mathcal C_2}})(\bar{\mathcal X_{\mathcal C_1}} - \bar{\mathcal X_{\mathcal C_2}})^T \mathcal W}{\mathcal W^T(\mathcal S_{\mathcal C_1} + \mathcal S_{\mathcal C_2}) \mathcal W} J(W)=WT(SC1+SC2)WWT(XC1ˉXC2ˉ)(XC1ˉXC2ˉ)TW

其对应的模型为: h ( x ) = W T x h(x) = \mathcal W^Tx h(x)=WTx。其 W \mathcal W W最优解 W ^ \hat {\mathcal W} W^可表示为如下形式:
∂ J ( W ) ∂ W ≜ 0 ⇒ W ^ = W T S w i t h W W T S s e t W S w i t h − 1 S b e t W \frac{\partial \mathcal J(\mathcal W)}{\partial \mathcal W} \triangleq 0 \Rightarrow \hat {\mathcal W} = \frac{\mathcal W^T\mathcal S_{with}\mathcal W}{\mathcal W^T\mathcal S_{set}\mathcal W} \mathcal S_{with}^{-1} \mathcal S_{bet} \mathcal W WJ(W)0W^=WTSsetWWTSwithWSwith1SbetW

其中 S w i t h \mathcal S_{with} Swith表示类内方差
S C i ( i = 1 , 2 ) \mathcal S_{\mathcal C_i}(i=1,2) SCi(i=1,2)表示类 i i i自身的方差结果; N i \mathcal N_i Ni表示类 i i i中的样本数量,下同。
{ S w i t h = S C 1 + S C 2 S C i = 1 N i ∑ x ( j ) ∈ X C i ( x ( j ) − X C i ˉ ) ( x ( j ) − X C i ˉ ) T \begin{cases} \mathcal S_{with} = \mathcal S_{\mathcal C_1} + \mathcal S_{\mathcal C_2} \\ \begin{aligned} \mathcal S_{\mathcal C_i} = \frac{1}{\mathcal N_i} \sum_{x^{(j)} \in \mathcal X_{\mathcal C_i}} (x^{(j)} - \bar{\mathcal X_{\mathcal C_i}})(x^{(j)} - \bar{\mathcal X_{\mathcal C_i}})^T \end{aligned} \end{cases} Swith=SC1+SC2SCi=Ni1x(j)XCi(x(j)XCiˉ)(x(j)XCiˉ)T
S b e t \mathcal S_{bet} Sbet表示类间方差
X C i ˉ ( i = 1 , 2 ) \bar{\mathcal X_{\mathcal C_i}}(i=1,2) XCiˉ(i=1,2)描述类 i i i内的均值结果。而 S b e t \mathcal S_{bet} Sbet是将‘均值结果’作为样本去描述‘均值的方差结果’。同上,和真正的方差相比,少了一个系数,但不影响 W ^ \hat {\mathcal W} W^的最优解方向。
{ S b e t = ( X C 1 ˉ − X C j ˉ ) ( X C 1 ˉ − X C j ˉ ) T X C i ˉ = 1 N i ∑ x ( j ) ∈ X C i x ( j ) \begin{cases} \mathcal S_{bet} = (\bar{\mathcal X_{\mathcal C_1}} - \bar{\mathcal X_{\mathcal C_j}})(\bar{\mathcal X_{\mathcal C_1}} - \bar{\mathcal X_{\mathcal C_j}})^T\\ \begin{aligned} \bar{\mathcal X_{\mathcal C_i}} = \frac{1}{\mathcal N_i} \sum_{x^{(j)} \in \mathcal X_{\mathcal C_i}} x^{(j)} \end{aligned} \end{cases} Sbet=(XC1ˉXCjˉ)(XC1ˉXCjˉ)TXCiˉ=Ni1x(j)XCix(j)
在求解过程中,无论是 S b e t \mathcal S_{bet} Sbet还是 S w i t h \mathcal S_{with} Swith,我们都要去求解向量内积。只不过这个内积的元素有些特殊
{ S b e t ⇒ X C 1 ˉ − X C j ˉ S w i t h ⇒ x ( j ) − X C i ˉ \begin{cases} \mathcal S_{bet} \Rightarrow \bar{\mathcal X_{\mathcal C_1}} - \bar{\mathcal X_{\mathcal C_j}} \\ \mathcal S_{with} \Rightarrow x^{(j)} - \bar{\mathcal X_{\mathcal C_i}} \end{cases} {SbetXC1ˉXCjˉSwithx(j)XCiˉ
即便是有些特殊,但是既然是内积,就可以使用核函数进行表示。此时 C \mathcal C \quad C 选项正确;

如果观察,会发现向量 X C 1 ˉ − X C j ˉ \bar{\mathcal X_{\mathcal C_1}} - \bar{\mathcal X_{\mathcal C_j}} XC1ˉXCjˉ向量 x ( j ) − X C i ˉ x^{(j)} - \bar{\mathcal X_{\mathcal C_i}} x(j)XCiˉ的大小和 x ( j ) x^{(j)} x(j)均相同。这意味着:无论是哪种内积结果,其执行内积过程中并没有维度上的变化。可以将其视作一个线性核函数
本质上,我们可能并没有使用所谓的线性核函数,而仅是求解了它们的类内方差和类间方差。但是,其内部包含了‘线性核函数’的思想。

线性判别分析作为一个经典的分类模型,它对样本的要求是线性可分的。如果遇到线性不可分的情况,线性判别分析的模型也会相应发生变化:
h ( x ) = W T ϕ ( x ) h(x) = \mathcal W^T\phi(x) h(x)=WTϕ(x)
相比于线性可分,在线性不可分的条件下,我们需要对 x x x进行特征转换,使其有机会在高维线性可分。并且通过核函数对特征转换的内积结果进行优化。对应算法被称作核线性判别分析 ( Kernalized Linear Discriminant Analysis,KLDA ) (\text{Kernalized Linear Discriminant Analysis,KLDA}) (Kernalized Linear Discriminant Analysis,KLDA)
这里不过多展开描述。推荐一篇文章,详见下方链接,侵删。

关于线性判别分析的一些小误区:关于上述 W \mathcal W W W ^ \hat {\mathcal W} W^关系式中,由于分子、分母均是标量,则有:

  • 1 λ = W T S w i t h W W T S s e t W \begin{aligned}\frac{1}{\lambda} = \frac{\mathcal W^T\mathcal S_{with}\mathcal W}{\mathcal W^T\mathcal S_{set}\mathcal W}\end{aligned} λ1=WTSsetWWTSwithW,原式可变化为:
    λ W ^ = S w i t h − 1 S b e t W \lambda \hat {\mathcal W} = \mathcal S_{with}^{-1} \mathcal S_{bet} \mathcal W λW^=Swith1SbetW
  • 这意味着 W ^ \hat {\mathcal W} W^ S w i t h − 1 S b e t \mathcal S_{with}^{-1} \mathcal S_{bet} Swith1Sbet最大非零广义特征值对应的特征向量组成的矩阵,我们仅需要选择特征值较大结果对应的特征向量,就可以将原始样本空间降维到新的参考空间。也就是说,线性判别分析被视作一种经典的基于监督学习的降维方法。
    • W ^ \hat {\mathcal W} W^中的向量就是一组基,各向量之间两两正交。
    • 这里的最大非零广义特征值,欢迎小伙伴们讨论。《机器学习》(周志华著) P63 3.4 线性判别分析

关于 D \mathcal D \quad D 选项的支持向量机,我们在引出对偶问题一节中将对偶问题转化为只包含 λ ( i ) ( i = 1 , 2 , ⋯ , N ) \lambda^{(i)}(i=1,2,\cdots,N) λ(i)(i=1,2,,N)变量的优化问题:
《机器学习》(周志华著) P123 6.2 对偶问题
{ max ⁡ λ − 1 2 [ ∑ i = 1 N ∑ j = 1 N λ ( i ) λ ( j ) y ( i ) y ( j ) ( x ( i ) ) T x ( j ) ] + ∑ i = 1 N λ ( i ) { s . t . λ ( i ) ≥ 0 ∑ i = 1 N λ ( i ) y ( i ) = 0 \begin{cases}\mathop{\max}\limits_{\lambda} -\frac{1}{2} \left[\sum_{i=1}^N\sum_{j=1}^N \lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}\left(x^{(i)}\right)^{T}x^{(j)}\right] + \sum_{i=1}^N\lambda^{(i)} \\ \begin{cases} s.t. \quad \lambda^{(i)} \geq 0 \\ \sum_{i=1}^N \lambda^{(i)}y^{(i)} = 0 \end{cases} \end{cases} λmax21[i=1Nj=1Nλ(i)λ(j)y(i)y(j)(x(i))Tx(j)]+i=1Nλ(i){s.t.λ(i)0i=1Nλ(i)y(i)=0
明显存在样本之间内积的项: [ x ( i ) ] T x ( j ) [x^{(i)}]^Tx^{(j)} [x(i)]Tx(j),同样针对线性不可分问题,或者计算复杂度较高的情况,可以使用核函数进行优化。

相关参考:
【机器学习】表示定理和核线性判别分析(KLDA)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_103661.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【HTML+CSS+JS】登录注册页面大合集

前言 学JS也学了一段时间,正巧碰上了人工智能要调用人脸识别接口进行真人人脸识别,于是便萌生了用人脸来进行注册和登录的想法,这样的话就需要开发一个登录注册页面,然后用JS绑定注册事件调用人脸识别接口进行登录注册 饭要一口一…

【数据结构:线性表】单链表

在学习了顺序表,我们可能会对其有一些思考: 中间/头部的插入删除,时间复杂度为O(N)增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容…

【校招VIP】面试了一个抽奖的项目,我终于搞明白了,是8股文终于开始作恶了

最近因为招实习生,进行了很多次面试。 但面试的结果不尽人意。 就感觉今年的面试跟以前差距太大了。 直到经过这个同学的面试,我终于明白了是什么原因。 这个同学是南京一所211的研究生,他的项目经历是做了一个抽奖的微服务管理平台。 也…

10、Mysql常见面试题

Mysql常见面试题 文章目录 Mysql常见面试题一 Mysql索引001 Mysql如何实现的索引机制?002 InnoDB索引与MyISAM索引实现的区别是什么?003 一个表中如果没有创建索引,那么还会创建B树吗? 004 说一下B树索引实现原理(数据…

2023移动云大会 | “六大”服务承诺 全力做优“心级服务”

4月25日,以“云擎未来 智信天下”为主题的2023移动云大会在苏州金鸡湖国际会议中心举办,众多政府领导、院士专家、知名企业客户与合作伙伴高层等数千名嘉宾齐聚一堂。 大会期间,移动云深入践行“为国建云”的使命,推出“六大”服…

电感知识大全

目录 一、电感的种类 1、共模电感 2、差模电感 3、工字电感 功率电感 4、磁珠 5、变压器 6、R棒电感、棒形电感、差模电感 二、电感符号 三、电感特性 前面在学习电容的时候,为了让大家更形象,更通俗的去理解这个元器件,都是拿水缸去…

【Vue 移动端开发】适配百分之99的屏幕方案

之前提起移动端适配,都是一些视口的概念,包括物理像素和逻辑像素,理想视口,dpr等等等。利用 media query 和 rem 是最常见的移动端适配方案。如下代码: const deviceWidth document.documentElement.clientWidth || …

为什么很多程序员不反感加班?行内人:老板给钱是真的给啊

为什么很多程序员不反感加班?行内人:说给钱老板真的给! 一提到程序员,大部分人第一反应是加班多、996、脱发,这几乎成了外界对程序员刻板印象的标配。不少知名的互联网大厂也是加班之风盛行,譬如著名的华为…

论文阅读:Heterogeneous Graph Contrastive Learning for Recommendation(WSDM ’23)

论文链接 Motivation: 在推荐系统中,图神经网络在建模图结构数据上已经变成一个强有力的工具。但是现实生活的推荐语义通常涉及异质关系(像用户的社交关系,物品知识关系的依赖),这些都包含丰富的语义信息…

17、Logos使用摘要

本篇将讲述如何将WX的设置界面添加两个自定义的UI行: 包含是否启用某功能的开关,以及手速设置.并且如何定位到修改的代码.采用的是砸过壳的包. 成品也就是增加了两个UI及开关联动效果、 界面分析 如果我们要破解别人的App, 首先从界面UI入手,定位UI 1、使用class-dump导出全部…

直升机空气动力学基础---002 桨叶的主要参数

源于 1.桨叶的平面形状和主要参数 由于其设计制造比较简单,早期直升机大多采用矩形桨叶,缺点是在高速气流中,无法抑制桨尖涡,会消耗向下的诱导速度,降低旋翼的拉力。现代多采用梯形桨叶。 桨尖后掠能够降低桨尖涡 …

Flowable打印调用原生API查询接口的SQL日志

一.简介 建议在 Spring Boot 的 application.properties 中添加如下配置,开启 flowable 日志: logging.level.org.flowabledebug这个配置表示开启 flowable 的日志,开启日志的好处是可以看到底层的 SQL语句。 二.查询部署信息 例如查询流…

使用 chat_flutter 进行聊天记录展示

前言 最近需要实现一个聊天记录的页面展示,在网上发现没有适合自己的,于是自己就造了一个,总体感觉还不赖。 下面奉上地址、效果图和教程。 效果图 地址 github: https://github.com/xiaorui-23/chat_fluttergitee: https://gitee.com/xi…

selenium_交互 (谷歌浏览器驱动下载 xpath插件安装)

安装selenium (1)查看谷歌浏览器版本 谷歌浏览器右上角 ‐‐> 帮助 ‐‐> 关于 查看 浏览器版本: (2)操作谷歌浏览器驱动下载地址 http : // chromedriver . storage . googleapis . com / index . html 找到…

YOLOv5网络模型的结构原理讲解(全)

目录 前言1. 基本概念2. 输入端2.1 Mosaic 图像增强2.2 自适应锚框计算2.3 自适应图片缩放 3. Backbone层3.1 Focus结构3.2 CSP结构 3. Neck网络3.1 SPP结构3.2 PAN结构 4. 输出端4.1 Bounding box损失函数4.2 NMS非极大值抑制 前言 YOLOv5有几种不同的架构,各网络…

Qt信号槽原理

Qt之信号槽原理 一.概述 所谓信号槽,实际就是观察者模式。当某个事件发生之后,比如,按钮检测到自己被点击了一下,它就会发出一个信号(signal)。这种发出是没有目的的,类似广播。如果有对象对这…

Openswan安装和简单配置

Openswan安装和简单配置 安装环境: 操作系统:Ubuntu20.0.4TLS 用户权限:root下载Openswan: wget https://github.com/xelerance/Openswan/archive/refs/tags/v3.0.0.zip安装Openswan: 解压Openswan:(PS&#xff1a…

银行数字化转型导师坚鹏:商业银行数字化风控(2天)

商业银行数字化风控 课程背景: 数字化背景下,很多银行存在以下问题: 不清楚商业银行数字化风控发展现状? 不清楚对公业务数字化风控工作如何开展? 不知道零售业务数字化风控工作如何开展? 课程特色…

海光信息业绩高歌猛进,但其作为国产CPU龙头的“地基”并不牢固

‍数据智能产业创新服务媒体 ——聚焦数智 改变商业 在“芯片寒冬”的大背景下,2022年全球头部芯片半导体公司纷纷下调业绩预期,英特尔、英伟达、美光等无一幸免。但是随着AIGC异军突起,仿佛寒冬中的一股暖流,催生着半导体市场行…

C. Trailing Loves (or L‘oeufs?)(求某个质因子在n的阶乘中的个数 + 思维)

Problem - C - Codeforces Aki喜欢数字,尤其是那些带有尾随零的数字。例如,数字9200有两个尾随零。Aki认为数字拥有的尾随零越多,它就越漂亮。 然而,Aki认为,一个数字拥有的尾随零的数量并不是固定的,而是…