线性代数|机器学习-P35距离矩阵和普鲁克问题

2024-09-08 09:28

本文主要是介绍线性代数|机器学习-P35距离矩阵和普鲁克问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 距离矩阵
  • 2. 正交普鲁克问题
  • 3. 实例说明

1. 距离矩阵

假设有三个点 x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3,三个点距离如下:
∣ ∣ x 1 − x 2 ∣ ∣ 2 = 1 , ∣ ∣ x 2 − x 3 ∣ ∣ 2 = 1 , ∣ ∣ x 1 − x 3 ∣ ∣ 2 = 6 \begin{equation} ||x_1-x_2||^2=1,||x_2-x_3||^2=1,||x_1-x_3||^2=6 \end{equation} ∣∣x1x22=1,∣∣x2x32=1,∣∣x1x32=6

  • 根据上面的公式发现不满足三角不等式定理,两边之和大于第三边 1 + 1 ≤ 6 1+1\le6 1+16
  • 根据三个点组成的距离矩阵Distance Matrix如下:
    D = [ 0 1 6 1 0 1 6 1 0 ] \begin{equation} D=\begin{bmatrix} 0&1&6\\\\ 1&0&1\\\\ 6&1&0 \end{bmatrix} \end{equation} D= 016101610
  • 假设我们有两个点 x 1 , x 2 x_1,x^2 x1,x2,那么 d i j d_{ij} dij的定义:
    D i j = ∣ ∣ x i − x j ∣ ∣ 2 = ( x i − x j ) T ( x i − x j ) = x i T x i − x i T x j − x j T x i + x j T x j \begin{equation} D_{ij}=||x_i-x_j||^2=(x_i-x_j)^T(x_i-x_j)=x_i^Tx_i-x_i^Tx_j-x_j^Tx_i+x_j^Tx_j \end{equation} Dij=∣∣xixj2=(xixj)T(xixj)=xiTxixiTxjxjTxi+xjTxj
  • 由于对称性可得: x i T x j = x j T x i x_i^Tx_j=x_j^Tx_i xiTxj=xjTxi,故化简可得:
    D i j = x i T x i − 2 x i T x j + x j T x j \begin{equation} D_{ij}=x_i^Tx_i-2x_i^Tx_j+x_j^Tx_j \end{equation} Dij=xiTxi2xiTxj+xjTxj
  • 为了方便计算,我们定义一个矩阵G表示如下:
    X = [ x i x j ] ; X T = [ x i T x j T ] → G = X T X = [ x i T x i x i T x j x j T x i x j T x j ] \begin{equation} X=\begin{bmatrix}x_i&x_j\end{bmatrix};X^T=\begin{bmatrix}x_i^T\\\\x_j^T\end{bmatrix}\to G=X^TX=\begin{bmatrix}x_i^Tx_i&x_i^Tx_j\\\\x_j^Tx_i&x_j^Tx_j\end{bmatrix} \end{equation} X=[xixj];XT= xiTxjT G=XTX= xiTxixjTxixiTxjxjTxj
  • 由此我们可以用G来表示D如下:
    D i j = G i i − 2 G i j + G j j \begin{equation} D_{ij}=G_{ii}-2G_{ij}+G_{jj} \end{equation} Dij=Gii2Gij+Gjj
  • 优势:为什么我们要这么费力的做?原因在于,我们求D矩阵的时候,我们需要不断的进行多重循环,效率非常低,如果我们这种方法,第一步通过点乘求得矩阵G,第二步只需要简单的抽取矩阵G中的元素,第三步就通过简单的加减乘除即可得到同样结果的距离矩阵D,结果是一样,但是此种算法大大减少了计算量,真是太神奇了!!!
  • 参考链接:
    斯坦福CS231N课程笔记(三)-距离矩阵的计算方法

2. 正交普鲁克问题

假设有两个矩阵A,B ,我们希望找到一个正交矩阵Q,使得 ∣ ∣ A Q − B ∣ ∣ F ||AQ-B||_F ∣∣AQBF最小?
min ⁡ ∣ ∣ A Q − B ∣ ∣ F ; s t : Q T Q = I \begin{equation} \min||AQ-B||_F;st:Q^TQ=I \end{equation} min∣∣AQBF;st:QTQ=I

  • 其中 A , B ∈ R m × n A,B\in R^{m\times n} A,BRm×n,待求 Q ∈ R n × n Q\in R^{n\times n} QRn×n为正交矩阵

3. 实例说明

  • 假设我们有一个矩阵A,B表示如下,希望找到一个正交矩阵Q使得 ∣ ∣ A Q − B ∣ ∣ F ||AQ-B||_F ∣∣AQBF尽可能的小?
    A = [ 1 0 0 1 1 1 ] ; B = [ 0 − 1 1 0 1 − 1 ] ; \begin{equation} A=\begin{bmatrix} 1&0\\\\ 0&1\\\\ 1&1\end{bmatrix};B=\begin{bmatrix} 0&-1\\\\ 1&0\\\\ 1&-1\end{bmatrix}; \end{equation} A= 101011 ;B= 011101 ;
  • 第一步: 求矩阵C
    C = A T B = [ 1 0 1 0 1 1 ] [ 0 − 1 1 0 1 − 1 ] = [ 1 − 2 2 − 1 ] ; \begin{equation} C=A^TB=\begin{bmatrix} 1&0&1\\\\ 0&1&1\end{bmatrix}\begin{bmatrix} 0&-1\\\\ 1&0\\\\ 1&-1\end{bmatrix}=\begin{bmatrix} 1&-2\\\\ 2&-1\end{bmatrix}; \end{equation} C=ATB= 100111 011101 = 1221 ;
  • 第二步:将矩阵C进行奇异值分解SVD:
    C = U Σ V T ; U = [ − 1 2 − 1 2 − 1 2 1 2 ] Σ = [ 3 0 0 1 ] ; V T = [ − 1 2 1 2 1 2 1 2 ] \begin{equation} C=U\Sigma V^T;U=\begin{bmatrix} -\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\\\ -\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix} \Sigma=\begin{bmatrix} 3&0\\\\ 0&1\end{bmatrix};V^T=\begin{bmatrix} -\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\\ \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix} \end{equation} C=UΣVT;U= 2 12 12 12 1 Σ= 3001 ;VT= 2 12 12 12 1
  • 第三步: 求出正交矩阵Q
    Q = U V T = [ − 1 2 − 1 2 − 1 2 1 2 ] [ − 1 2 1 2 1 2 1 2 ] = [ 0 − 1 1 0 ] \begin{equation} Q=UV^T=\begin{bmatrix} -\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\\\ -\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix} \begin{bmatrix} -\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\\ \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix}= \begin{bmatrix} 0&-1\\\\ 1&0\end{bmatrix} \end{equation} Q=UVT= 2 12 12 12 1 2 12 12 12 1 = 0110
  • 第四步,验证 ∣ ∣ A Q − B ∣ ∣ ||AQ-B|| ∣∣AQB∣∣
    ∣ ∣ A Q − B ∣ ∣ F = 0 \begin{equation} ||AQ-B||_F=0 \end{equation} ∣∣AQBF=0
  • 小结:这种方法还真能够找到正交矩阵Q.

这篇关于线性代数|机器学习-P35距离矩阵和普鲁克问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147728

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k