精华内容
下载资源
问答
  • (1)傅里叶变换炫云:傅里叶变换的全面理解,非常棒​zhuanlan.zhihu.com(2)Graph上的傅里叶变换传统的傅里叶变换定义为:公式(1)表示的意义是傅立叶变换是时域信号 与基函数 (拉普拉斯算子特征函数)的积分,那么...

    把传统的傅里叶变换以及卷积迁移到Graph上来,核心工作其实就是把拉普拉斯算子的特征函数

    变为Graph对应的拉普拉斯矩阵的特征向量

    (1)傅里叶变换

    炫云:傅里叶变换的全面理解,非常棒zhuanlan.zhihu.com
    a3398ae2284d290e120204771270a6af.png

    (2)Graph上的傅里叶变换

    传统的傅里叶变换定义为:

    公式(1)表示的意义是傅立叶变换是时域信号

    与基函数
    (拉普拉斯算子特征函数)的积分,
    那么为什么要找
    作为基函数呢?
    1. 是正交函数系。
    2. 从数学上看,
      是拉普拉斯算子
      的特征函数(满足特征方程),
      就和特征值有关。

    至于

    由何种推导得来的请参考:傅里叶变换的全面理解

    拉普拉斯算子Δ的定义:

    炫云:拉普拉斯算子和拉普拉斯矩阵,图拉普拉斯算子推导zhuanlan.zhihu.com
    a3398ae2284d290e120204771270a6af.png

    其数学定义为:

    • 为何
      是拉普拉斯算子
      的特征函数?理解如下

    广义的特征方程定义为:

    其中

    是一种变换(例如:拉普拉斯),
    特征向量或者特征函数(无限维的特征向量),
    是特征值。

    带入函数

    满足:

    当然

    就是变换
    的特征函数,
    和特征值密切相关

    由上述证明可得结论:傅立叶变换是时域信号与拉普拉斯算子特征函数的积分。

    从整体推特殊,将以上的结论推广到(离散)图中可知:图上的傅立叶变换就是时域信号与图拉普拉斯算子特征函数的求和!

    那么,处理Graph问题的时候,用到拉普拉斯矩阵(拉普拉斯矩阵就是离散拉普拉斯算子),自然就去找拉普拉斯矩阵的特征向量了。

    是拉普拉斯矩阵,
    是其特征向量,自然满足下式

    对于傅里叶变换式(1),将特征函数转换为特征向量,离散积分就是一种内积形式,将积分转换为求和,那么N个顶点图上的傅立叶变化表达式为:

    是Graph上的
    维向量,
    与Graph的顶点一一对应,
    表示第
    个特征向量的第
    个分量。
    为图拉普拉斯算子第
    个特征值,公式(5)是
    特征值(频率)对应的傅立叶变换.

    注:上述的内积运算是在复数空间中定义的,所以采用了

    ,也就是特征向量
    的共轭。

    利用矩阵乘法将Graph上的傅里叶变换推广到矩阵形式:

    在Graph上傅里叶变换的矩阵形式为

    式中:

    的定义与拉普拉斯矩阵的谱分解的相同,为拉普拉斯谱分解的正交矩阵。

    (3)Graph上的傅里叶逆变换

    类似地,为了将频率函数变换为时域函数,传统的傅里叶逆变换是对频率

    求积分:

    公式(7)和公式(1)类似,差一个常数系数。公式(1)积分之后是一个关于w的函数,公式(7) 对w积分后是关于t的函数,从频域变换到了时域。

    迁移到Graph上变为对特征值

    求和:

    利用矩阵乘法将Graph上的傅里叶逆变换推广到矩阵形式:

    在Graph上傅里叶逆变换的矩阵形式为:


    二、为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基?特征值表示频率?

    (1)为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基?

    傅里叶变换一个本质理解就是:把任意一个函数表示成了若干个正交函数(由sin,cos 构成)的线性组合。

    edd757157356ebf43d408d9dccee8f6c.png
    图6 傅里叶逆变换图示

    通过

    式也能看出,
    graph傅里叶变换也把graph上定义的任意向量
    ,表示成了拉普拉斯矩阵特征向量的线性组合,即:

    那么:为什么graph上任意的向量

    都可以表示成这样的线性组合?

    原因在于

    是graph上
    维空间中的
    个线性无关的正交向量,由线性代数的知识可以知道:
    维空间中
    个线性无关的向量可以构成空间的一组基,而且拉普拉斯矩阵的特征向量还是一组正交基。

    所以拉普拉斯矩阵的特征向量可以作为傅里叶变换的基。

    (2)怎么理解拉普拉斯矩阵的特征值表示频率?

    graph空间上无法可视化展示“频率”这个概念,那么从特征方程上来抽象理解。

    可以观看

    炫云:拉普拉斯矩阵的谱分解,图的拉普拉斯矩阵zhuanlan.zhihu.com
    a3398ae2284d290e120204771270a6af.png

    将拉普拉斯矩阵

    非负实特征值,从小到大排列为
    ,而且最小的特征值
    ,因为
    维的全1向量对应的特征值为0(由
    的定义就可以得出):

    从特征方程的数学理解来看:

    在由Graph确定的

    维空间中,越小的特征值
    表明:拉普拉斯矩阵
    其所对应的基
    上的分量、“信息”越少,那么当然就是可以
    忽略的低频部分了。

    其实图像压缩就是这个原理把像素矩阵特征分解后,把小的特征值(低频部分)全部变成0,PCA降维也是同样的,把协方差矩阵特征分解后,按从大到小取出前K个特征值对应的特征向量作为新的“坐标轴”。

    展开全文
  • 对于傅里叶变换,本文不再赘述。详细内容可以参考: 深入理解傅里叶变换 图上的傅立叶变换 傅立叶变换是将时域的函数转换成频域上的函数,是对于同一个函数的不同视角,数学定义如下: F(w)=F(f(t))=∫f(t)e−iwtdt...

    原文首发于个人站点 图卷积网络GCN(Graph Convolution Network)(二)图上的傅里叶变换和逆变换
    公众号:【DreamHub】

    由于文章篇幅较长,因此将其分解为三部分:

    背景知识

    如要了解谱图卷积,首先需要学习图理论基础和图中如何进行傅里叶变换。

    对于傅里叶变换,本文不再赘述。详细内容可以参考:

    图上的傅立叶变换

    傅立叶变换是将时域的函数转换成频域上的函数,是对于同一个函数的不同视角,数学定义如下:
    F(w)=F(f(t))=f(t)eiwtdt(1) \mathcal{F}(w)=\mathcal{F}(f(t))=\int{f(t)e^{-iwt}}dt \quad\quad\quad (1)
    公式(1)表示的意义是傅立叶变换是时域信号 f(t)f(t) 与基函数 eiwte^{-iwt} 的积分。

    为什么选择eiwte^{-iwt}作为基函数?原因有二:

    • eiwte^{-iwt}是正交函数系。
    • eiwte^{-iwt}是拉普拉斯算子Δ\Delta的特征函数。

    至于eiwte^{-iwt}由何种推导得来的请参考: 理解傅里叶变换 | 隐舍

    先解释下拉普拉斯算子Δ\Delta的定义

    在数学中,拉普拉斯算子(Laplacian)是由欧几里得空间中的一个函数的梯度的散度给出的微分算子,记为Δf=2f=f\Delta f=\nabla^{2} f=\nabla \cdot \nabla f,表示nn维空间笛卡尔坐标系xix_i中所有非混合二阶偏导数之和,其数学定义为
    Δ=i=1n22xi(2) \Delta=\sum_{i=1}^n\frac{\partial^2}{\partial{^2x_{i}}} \quad\quad\quad(2)
    这表达式什么意思呢?以二维空间为例:
    Δf(x,y)=2fx2+2fy2=[f(x+1,y)+f(x1,y)2f(x,y)]+[f(x,y+1)+f(x,y1)2f(x,y)]=f(x+1,y)+f(x1,y)+f(x,y+1)+f(x,y1)4f(x,y) \begin{aligned} \Delta f(x, y) &=\frac{\partial^{2} f}{\partial x^{2}}+\frac{\partial^{2} f}{\partial y^{2}} \\ &=[f(x+1, y)+f(x-1, y)-2 f(x, y)]+[f(x, y+1)+f(x, y-1)-2 f(x, y)] \\ &=f(x+1, y)+f(x-1, y)+f(x, y+1)+f(x, y-1)-4 f(x, y) \end{aligned}
    上式中每一项的系数就是拉普拉斯在二维图像中的卷积核:

    再解释下eiwte^{-iwt}为何拉普拉斯算子Δ\Delta的特征函数

    拉普拉斯算子的特征方程为:
    Δg=λg(3) \Delta g=\lambda g \quad\quad\quad (3)

    代入函数eiwte^{-iwt}可得:

    Δeiwt=22xieiwt=22teiwt=w2eiwt(4) \Delta e^{-iwt}=\frac{\partial ^2}{\partial^2 x_i}e^{-iwt}=\frac{\partial ^2}{\partial^2 t}e^{-iwt}=-w^2e^{-iwt} \quad\quad\quad(4)

    其中特征值 λ=w2\lambda=-w^2 ,即 ww 和特征值 λ\lambda 密切相关。

    由上述证明可得结论:傅立叶变换是时域信号与拉普拉斯算子特征函数的积分。

    从整体推特殊,将以上的结论推广到(离散)图中可知:图上的傅立叶变换就是时域信号与图拉普拉斯算子特征函数的求和!

    对于傅里叶变换式(1),将特征函数转换为特征向量(特征函数可以认为是无限维的特征向量),将积分转换为求和,那么NN个顶点图上的傅立叶变化表达式为:
    F(λl)=f^(λl)=i=1Nf(i)ul(i)(5) \mathcal{F}(\lambda_l)=\widehat f(\lambda_l)=\sum_{i=1}^N f(i)*u_l(i) \quad\quad\quad(5)

    其中, λl\lambda_l 为图拉普拉斯算子第 ll 个特征值, ulu_{l} 为第 ll 个特征值对应的特征向量,公式(5)是
    λl\lambda_{l} 对应的傅立叶变换,对于图拉普拉斯算子,具有NN个特征值,将式 (5) 全部分量展开可得:
    (f^(λ1)f^(λ2)f^(λN))=(u1(1)u1(2)u1(N)u2(1)u2(2)u2(N)uN(1)uN(2)uN(N))(f(1)f(2)f(N))(6) \left(\begin{array}{c} \hat{f}\left(\lambda_{1}\right) \\ \hat{f}\left(\lambda_{2}\right) \\ \vdots \\ \hat{f}\left(\lambda_{N}\right) \end{array}\right)=\left(\begin{array}{cccc} u_{1}(1) & u_{1}(2) & \dots & u_{1}(N) \\ u_{2}(1) & u_{2}(2) & \dots & u_{2}(N) \\ \vdots & \vdots & \ddots & \vdots \\ u_{N}(1) & u_{N}(2) & \dots & u_{N}(N) \end{array}\right)\left(\begin{array}{c} f(1) \\ f(2) \\ \vdots \\ f(N) \end{array}\right) \quad\quad\quad(6)

    将公式(6)写成矩阵形式即为:
    f^=UTf(7) \widehat f=U^{T}f \quad\quad\quad (7)
    此处UU为拉普拉斯谱分解的正交矩阵。

    最后再来看看图中拉普拉斯算子的定义:
    L=DW(8)L=D-W \quad\quad\quad (8)
    其中WW是邻接矩阵,DD是度矩阵,Di,iD_{i,i}等于WW矩阵的第ii行的和,非对角线上元素为0,DD是个对角矩阵,这个图谱理论关于图拉普拉斯算子的的定义。详细推到过程参考:图拉普拉斯算子为何定义为D-W

    拉普拉斯矩阵是实对称矩阵,实对称矩阵一定可以用正交矩阵进行正交相似对角化(特征分解):

    L=U(λ1λN)U1=U(λ1λN)UT(9)L=U\left(\begin{array}{ccc} \lambda_{1} & & \\ & \ddots & \\ & & \lambda_{N} \end{array}\right) U^{-1} =U\left(\begin{array}{ccc} \lambda_{1} & & \\ & \ddots & \\ & & \lambda_{N} \end{array}\right) U^{T} \quad\quad\quad (9)

    UU 为特征向量构成的正交矩阵,而正交矩阵的逆等于正交矩阵的转置:U1=UTU^{-1}=U^T

    假定 λ1,,λn\lambda_{1},\cdots,\lambda_{n} 从小到大排序,其对应的特征向量为 u1,,unu_1,\cdots, u_n,特征值越小,对应的特征向量越平稳,这和傅立叶变换中频率的定义是类似的。下图是对 random sensor network 做特征值分解后的特征向量分布展示,可以看到特征值越小,对应的特征向量越平滑。

    图上傅里叶逆变换

    有了傅立叶变换,如何将频率函数变换为时域函数呢?这是傅立叶逆变换需要干的事情,公式如下:

    F1[F(w)]=12πF(w)eiwtdw(10) \mathcal{F}^{-1}[\mathcal{F}(w)]=\frac{1}{2\pi}\int \mathcal{F}(w)e^{-iwt}dw \quad\quad\quad(10)

    公式(10)和公式(1)类似,差一个常数系数。公式(1)积分之后是一个关于 ww 的函数,公式(10) 对 ww 积分后是关于 tt 的函数,从频域变换到了时域,图上傅立叶变换类似为:
    (f(λ1)f(λ2)f(λN))=(u1(1)u1(2)u1(N)u1(1)u1(2)u1(N)u1(1)u1(2)u1(N))(f^(λ1)f^(λ2)f^(λN))(11)\left(\begin{array}{c} f\left(\lambda_{1}\right) \\ f\left(\lambda_{2}\right) \\ \cdots \\ f\left(\lambda_{N}\right) \end{array}\right)=\left(\begin{array}{cccc} u_{1}(1) & u_{1}(2) & \dots & u_{1}(N) \\ u_{1}(1) & u_{1}(2) & \dots & u_{1}(N) \\ \cdots & \dots & & \dots \\ u_{1}(1) & u_{1}(2) & \dots & u_{1}(N) \end{array}\right)\left(\begin{array}{c} \hat{f}\left(\lambda_{1}\right) \\ \hat{f}\left(\lambda_{2}\right) \\ \dots \\ \hat{f}\left(\lambda_{N}\right) \end{array}\right) \quad\quad\quad (11)

    写成矩阵形式:
    f=UU1f=UUTf=Uf^(12)f=\mathbf{U} \mathbf{U}^{-1} f=\mathbf{U} \mathbf{U}^{T} f=\mathbf{U} \hat{f}\quad\quad\quad (12)

    上述内容详述了如何在图中进行傅里叶变换和逆变换,下面就是主角图卷积网络GCN上场了!

    下篇更新的文章将讲述三代图卷积网络的前世今生!

    关注作者

    展开全文
  • 卷积定理:函数卷积的傅里叶变化是函数傅里叶变化的乘积,即对于函数f(t)与h(t)两者的卷积是其函数傅里叶变换乘积的逆变换: 类比到Graph上并把傅里叶变换定义带入,f与卷积核h在Graph上的卷积可以由下面步骤得到...

    傅里叶变换是将函数分解到频率不同、幅值恒为1的单位圆上;拉普拉斯变换是将函数分解到频率幅值都在变化的圆上。因为拉普拉斯变换的基有两个变量,因此更灵活,适用范围更广。

    卷积定理:函数卷积的傅里叶变化是函数傅里叶变化的乘积,即对于函数f(t)h(t)两者的卷积是其函数傅里叶变换乘积的逆变换:

    类比到Graph上并把傅里叶变换的定义带入,f与卷积核h在Graph上的卷积可以由下面步骤得到:

    f的傅里叶变换为

    卷积核h的傅里叶变换写成对角矩阵的形式 

    两者的傅里叶变换乘积即为

    由于图结构非常复杂且信息量很大,因此对于图的机器学习是一项艰巨的任务。本文介绍了如何使用图卷积网络(GCN)对图进行深度学习,GCN 是一种可直接作用于图并利用其结构信息的强大神经网络。

     

    本文将介绍 GCN,并使用代码示例说明信息是如何通过 GCN 的隐藏层传播的。读者将看到 GCN 如何聚合来自前一层的信息,以及这种机制如何生成图中节点的有用特征表征。

     

    何为图卷积网络?

     

    GCN 是一类非常强大的用于图数据的神经网络架构。事实上,它非常强大,即使是随机初始化的两层 GCN 也可以生成图网络中节点的有用特征表征。下图展示了这种两层 GCN 生成的每个节点的二维表征。请注意,即使没有经过任何训练,这些二维表征也能够保存图中节点的相对邻近性。

     

     

    更形式化地说,图卷积网络(GCN)是一个对图数据进行操作的神经网络。给定图 G = (V, E),GCN 的输入为:

     

    • 一个输入维度为 N × F⁰ 的特征矩阵 X,其中 N 是图网络中的节点数而 F⁰ 是每个节点的输入特征数。

    • 一个图结构的维度为 N × N 的矩阵表征,例如图 G 的邻接矩阵 A。[1]

     

    因此,GCN 中的隐藏层可以写作 Hⁱ = f(Hⁱ⁻¹, A))。其中,H⁰ = X,f 是一种传播规则 [1]。每一个隐藏层 Hⁱ 都对应一个维度为 N × Fⁱ 的特征矩阵,该矩阵中的每一行都是某个节点的特征表征。在每一层中,GCN 会使用传播规则 f 将这些信息聚合起来,从而形成下一层的特征。这样一来,在每个连续的层中特征就会变得越来越抽象。在该框架下,GCN 的各种变体只不过是在传播规则 f 的选择上有所不同 [1]。

     

    传播规则的简单示例

     

    下面,本文将给出一个最简单的传播规则示例 [1]:

     

    f(Hⁱ, A) = σ(AHⁱWⁱ)

     

    其中,Wⁱ 是第 i 层的权重矩阵,σ 是非线性激活函数(如 ReLU 函数)。权重矩阵的维度为 Fⁱ × Fⁱ⁺¹,即权重矩阵第二个维度的大小决定了下一层的特征数。如果你对卷积神经网络很熟悉,那么你会发现由于这些权重在图中的节点间共享,该操作与卷积核滤波操作类似。

     

    简化

     

    接下来我们在最简单的层次上研究传播规则。令:

     

    • i = 1,(约束条件 f 是作用于输入特征矩阵的函数)

    • σ 为恒等函数

    • 选择权重(约束条件: AH⁰W⁰ =AXW⁰ = AX)

     

    换言之,f(X, A) = AX。该传播规则可能过于简单,本文后面会补充缺失的部分。此外,AX 等价于多层感知机的输入层。

     

    简单的图示例

     

    我们将使用下面的图作为简单的示例:

     

    一个简单的有向图。

     

    使用 numpy 编写的上述有向图的邻接矩阵表征如下:

     

    A = np.matrix([
        [0, 1, 0, 0],
        [0, 0, 1, 1], 
        [0, 1, 0, 0],
        [1, 0, 1, 0]],
        dtype=float
    )

     

    接下来,我们需要抽取出特征!我们基于每个节点的索引为其生成两个整数特征,这简化了本文后面手动验证矩阵运算的过程。

     

    In [3]: X = np.matrix([
                [i, -i]
                for i in range(A.shape[0])
            ], dtype=float)
            X
    Out[3]: matrix([
               [ 0.,  0.],
               [ 1., -1.],
               [ 2., -2.],
               [ 3., -3.]
            ])

     

    应用传播规则

     

    我们现在已经建立了一个图,其邻接矩阵为 A,输入特征的集合为 X。下面让我们来看看,当我们对其应用传播规则后会发生什么:

     

    In [6]: A * X
    Out[6]: matrix([
                [ 1., -1.],
                [ 5., -5.],
                [ 1., -1.],
                [ 2., -2.]]

     

    每个节点的表征(每一行)现在是其相邻节点特征的和!换句话说,图卷积层将每个节点表示为其相邻节点的聚合。大家可以自己动手验证这个计算过程。请注意,在这种情况下,如果存在从 v 到 n 的边,则节点 n 是节点 v 的邻居。

     

    问题

     

    你可能已经发现了其中的问题:

     

    • 节点的聚合表征不包含它自己的特征!该表征是相邻节点的特征聚合,因此只有具有自环(self-loop)的节点才会在该聚合中包含自己的特征 [1]。

    • 度大的节点在其特征表征中将具有较大的值,度小的节点将具有较小的值。这可能会导致梯度消失或梯度爆炸 [1, 2],也会影响随机梯度下降算法(随机梯度下降算法通常被用于训练这类网络,且对每个输入特征的规模(或值的范围)都很敏感)。

     

    接下来,本文将分别对这些问题展开讨论。

     

    增加自环

     

    为了解决第一个问题,我们可以直接为每个节点添加一个自环 [1, 2]。具体而言,这可以通过在应用传播规则之前将邻接矩阵 A 与单位矩阵 I 相加来实现。

     

    In [4]: I = np.matrix(np.eye(A.shape[0]))
            I
    Out[4]: matrix([
                [1., 0., 0., 0.],
                [0., 1., 0., 0.],
                [0., 0., 1., 0.],
                [0., 0., 0., 1.]
            ])
    In [8]: A_hat = A + I
            A_hat * X
    Out[8]: matrix([
                [ 1., -1.],
                [ 6., -6.],
                [ 3., -3.],
                [ 5., -5.]])

     

    现在,由于每个节点都是自己的邻居,每个节点在对相邻节点的特征求和过程中也会囊括自己的特征!

     

    对特征表征进行归一化处理

     

    通过将邻接矩阵 A 与度矩阵 D 的逆相乘,对其进行变换,从而通过节点的度对特征表征进行归一化。因此,我们简化后的传播规则如下:

     

    f(X, A) = D⁻¹AX

     

    让我们看看发生了什么。我们首先计算出节点的度矩阵。

     

    In [9]: D = np.array(np.sum(A, axis=0))[0]
            D = np.matrix(np.diag(D))
            D
    Out[9]: matrix([
                [1., 0., 0., 0.],
                [0., 2., 0., 0.],
                [0., 0., 2., 0.],
                [0., 0., 0., 1.]
            ])

     

    在应用传播规则之前,不妨看看我们对邻接矩阵进行变换后发生了什么。

     

    变换之前

     

    A = np.matrix([
        [0, 1, 0, 0],
        [0, 0, 1, 1], 
        [0, 1, 0, 0],
        [1, 0, 1, 0]],
        dtype=float
    )

     

    变换之后

     

    In [10]: D**-1 * A
    Out[10]: matrix([
                 [0. , 1. , 0. , 0. ],
                 [0. , 0. , 0.5, 0.5],
                 [0. , 0.5, 0. , 0. ],
                 [0.5, 0. , 0.5, 0. ]
    ])

     

    可以观察到,邻接矩阵中每一行的权重(值)都除以该行对应节点的度。我们接下来对变换后的邻接矩阵应用传播规则:

     

    In [11]: D**-1 * A * X
    Out[11]: matrix([
                 [ 1. , -1. ],
                 [ 2.5, -2.5],
                 [ 0.5, -0.5],
                 [ 2. , -2. ]
             ])

     

    得到与相邻节点的特征均值对应的节点表征。这是因为(变换后)邻接矩阵的权重对应于相邻节点特征加权和的权重。大家可以自己动手验证这个结果。

     

    整合

     

    现在,我们将把自环和归一化技巧结合起来。此外,我们还将重新介绍之前为了简化讨论而省略的有关权重和激活函数的操作。

     

    添加权重

     

    首先要做的是应用权重。请注意,这里的 D_hat 是 A_hat = A + I 对应的度矩阵,即具有强制自环的矩阵 A 的度矩阵。

     

    In [45]: W = np.matrix([
                 [1, -1],
                 [-1, 1]
             ])
             D_hat**-1 * A_hat * X * W
    Out[45]: matrix([
                [ 1., -1.],
                [ 4., -4.],
                [ 2., -2.],
                [ 5., -5.]
            ])

     

    如果我们想要减小输出特征表征的维度,我们可以减小权重矩阵 W 的规模:

     

    In [46]: W = np.matrix([
                 [1],
                 [-1]
             ])
             D_hat**-1 * A_hat * X * W
    Out[46]: matrix([[1.],
            [4.],
            [2.],
            [5.]]
    )

     

    添加激活函数

     

    本文选择保持特征表征的维度,并应用 ReLU 激活函数。

     

    In [51]: W = np.matrix([
                 [1, -1],
                 [-1, 1]
             ])
             relu(D_hat**-1 * A_hat * X * W)
    Out[51]: matrix([[1., 0.],
            [4., 0.],
            [2., 0.],
            [5., 0.]])

     

    这就是一个带有邻接矩阵、输入特征、权重和激活函数的完整隐藏层!

     

    在真实场景下的应用

     

    最后,我们将图卷积网络应用到一个真实的图上。本文将向读者展示如何生成上文提到的特征表征。

     

    Zachary 空手道俱乐部

     

    Zachary 空手道俱乐部是一个被广泛使用的社交网络,其中的节点代表空手道俱乐部的成员,边代表成员之间的相互关系。当年,Zachary 在研究空手道俱乐部的时候,管理员和教员发生了冲突,导致俱乐部一分为二。下图显示了该网络的图表征,其中的节点标注是根据节点属于俱乐部的哪个部分而得到的,「A」和「I」分别表示属于管理员和教员阵营的节点。

     

    Zachary 空手道俱乐部图网络

     

    构建 GCN

     

    接下来,我们将构建一个图卷积网络。我们并不会真正训练该网络,但是会对其进行简单的随机初始化,从而生成我们在本文开头看到的特征表征。我们将使用 networkx,它有一个可以很容易实现的 Zachary 空手道俱乐部的图表征。然后,我们将计算 A_hat 和 D_hat 矩阵。

     

    from networkx import to_numpy_matrix
    zkc = karate_club_graph()
    order = sorted(list(zkc.nodes()))
    A = to_numpy_matrix(zkc, nodelist=order)
    I = np.eye(zkc.number_of_nodes())
    A_hat = A + I
    D_hat = np.array(np.sum(A_hat, axis=0))[0]
    D_hat = np.matrix(np.diag(D_hat))

     

    接下来,我们将随机初始化权重。

     

    W_1 = np.random.normal(
        loc=0, scale=1, size=(zkc.number_of_nodes(), 4))
    W_2 = np.random.normal(
        loc=0, size=(W_1.shape[1], 2))

     

    接着,我们会堆叠 GCN 层。这里,我们只使用单位矩阵作为特征表征,即每个节点被表示为一个 one-hot 编码的类别变量。

     

    def gcn_layer(A_hat, D_hat, X, W):
        return relu(D_hat**-1 * A_hat * X * W)
    H_1 = gcn_layer(A_hat, D_hat, I, W_1)
    H_2 = gcn_layer(A_hat, D_hat, H_1, W_2)
    output = H_2

     

    我们进一步抽取出特征表征。

     

    feature_representations = {
        node: np.array(output)[node] 
        for node in zkc.nodes()}

     

    你看,这样的特征表征可以很好地将 Zachary 空手道俱乐部的两个社区划分开来。至此,我们甚至都没有开始训练模型!

     

    Zachary 空手道俱乐部图网络中节点的特征表征。

     

    我们应该注意到,在该示例中由于 ReLU 函数的作用,在 x 轴或 y 轴上随机初始化的权重很可能为 0,因此需要反复进行几次随机初始化才能生成上面的图。

     

    结语

     

    本文中对图卷积网络进行了高屋建瓴的介绍,并说明了 GCN 中每一层节点的特征表征是如何基于其相邻节点的聚合构建的。读者可以从中了解到如何使用 numpy 构建这些网络,以及它们的强大:即使是随机初始化的 GCN 也可以将 Zachary 空手道俱乐部网络中的社区分离开来。 

     

    参考文献

     

    https://mp.weixin.qq.com/s/sg9O761F0KHAmCPOfMW_kQ

    [1] Blog post on graph convolutional networks by Thomas Kipf.

    [2] Paper called Semi-Supervised Classification with Graph Convolutional Networks by Thomas Kipf and Max Welling.

     

    原文链接:https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780

     

    展开全文
  • 原理短时傅里叶变换(Short Time Fourier Transform, STFT) 是一个用于语音信号处理的通用工具.它定义了一个非常有用的时间频率分布类, 其指定了任意信号随时间...短时傅里叶变换通常的数学定义如下: 其中, DTFT (D...

    原理

    短时傅里叶变换(Short Time Fourier Transform, STFT) 是一个用于语音信号处理的通用工具.它定义了一个非常有用的时间和频率分布类, 其指定了任意信号随时间和频率变化的复数幅度. 实际上,计算短时傅里叶变换的过程是把一个较长的时间信号分成相同长度的更短的段, 在每个更短的段上计算傅里叶变换, 即傅里叶频谱.

    短时傅里叶变换通常的数学定义如下:

    其中,

    DTFT (Decrete Time Fourier Transform) 为离散时间傅里叶变换.  其数学公式, 如下所示:

    其中,  x(n) 为在采样数 n 处的信号幅度. ω~ 的定义如下:

    实现时, 短时傅里叶变换被计算为一系列加窗数据帧的快速傅里叶变换 (Fast Fourier Transform, FFT),其中窗口随时间 “滑动” (slide) 或“跳跃” (hop) 。

    Python 实现

    在程序中, frame_size 为将信号分为较短的帧的大小, 在语音处理中, 通常帧大小在 20ms 到 40ms 之间. 这里设置为 25ms, 即 frame_size = 0.025;

    frame_stride 为相邻帧的滑动尺寸或跳跃尺寸, 通常帧的滑动尺寸在 10ms 到 20ms 之间, 这里设置为 10ms, 即 frame_stride = 0.01. 此时, 相邻帧的交叠大小为 15ms;

    窗函数采用汉明窗函数 (Hamming Function) ;

    在每一帧, 进行 512 点快速傅里叶变换, 即 NFFT = 512. 具体程序如下:

    #-*- coding: utf8 -*-

    importnumpy as npdef calc_stft(signal, sample_rate=16000, frame_size=0.025, frame_stride=0.01, winfunc=np.hamming, NFFT=512):#Calculate the number of frames from the signal

    frame_length = frame_size *sample_rate

    frame_step= frame_stride *sample_rate

    signal_length=len(signal)

    frame_length=int(round(frame_length))

    frame_step=int(round(frame_step))

    num_frames= 1 + int(np.ceil(float(np.abs(signal_length - frame_length)) /frame_step))#zero padding

    pad_signal_length = num_frames * frame_step +frame_length

    z= np.zeros((pad_signal_length -signal_length))#Pad signal to make sure that all frames have equal number of samples

    #without truncating any samples from the original signal

    pad_signal =np.append(signal, z)#Slice the signal into frames from indices

    indices = np.tile(np.arange(0, frame_length), (num_frames, 1)) +\

    np.tile(np.arange(0, num_frames* frame_step, frame_step), (frame_length, 1)).T

    frames= pad_signal[indices.astype(np.int32, copy=False)]#Get windowed frames

    frames *=winfunc(frame_length)#Compute the one-dimensional n-point discrete Fourier Transform(DFT) of

    #a real-valued array by means of an efficient algorithm called Fast Fourier Transform (FFT)

    mag_frames =np.absolute(np.fft.rfft(frames, NFFT))#Compute power spectrum

    pow_frames = (1.0 / NFFT) * ((mag_frames) ** 2)returnpow_framesif __name__ == '__main__':importscipy.io.wavfileimportmatplotlib.pyplot as plt#Read wav file

    #"OSR_us_000_0010_8k.wav" is downloaded from http://www.voiptroubleshooter.com/open_speech/american.html

    sample_rate, signal = scipy.io.wavfile.read("OSR_us_000_0010_8k.wav")#Get speech data in the first 2 seconds

    signal = signal[0:int(2. *sample_rate)]#Calculate the short time fourier transform

    pow_spec =calc_stft(signal, sample_rate)

    plt.imshow(pow_spec)

    plt.tight_layout()

    plt.show()

    参考资料

    1. DISCRETE TIME FOURIER TRANSFORM (DTFT). https://www.dsprelated.com/freebooks/mdft/Discrete_Time_Fourier_Transform.html

    2. THE SHORT-TIME FOURIER TRANSFORM. https://www.dsprelated.com/freebooks/sasp/Short_Time_Fourier_Transform.html

    3. Short-time Fourier transform. https://en.wikipedia.org/wiki/Short-time_Fourier_transform

    4. Speech Processing for Machine Learning: Filter banks, Mel-Frequency Cepstral Coefficients (MFCCs) and What's In-Between. https://haythamfayek.com/2016/04/21/speech-processing-for-machine-learning.html

    展开全文
  • F(w)的傅里叶逆变换定义为: 其中,i为虚数单位。由欧拉公式: 任意连续函数f(t),都可以用三角函数表示,由于三角函数是周期函数,由此可展开为傅里叶级数。本文不加证明地给出傅里叶级数展开式: 设F是...
  • 通俗点来说,FFT就是利用某些奇偶特点,进行DFT(离散傅里叶变换IDFT(离散傅里叶逆变换)的快速求解算法。 (2)FFT是干什么的,有什么用 <1>在信号学中有很大用处(具体什么用俺也不知道) <2>...
  • 傅里叶变换Fourier transform 1 傅里叶变化基本知识1.1 一维连续Fourier变换对函数f(x)...定义幅值为:定义相位为:用幅值相位表示傅立叶变换能量谱(或功率谱)现在可以来复习一下傅里叶变换hui gu yi xia:当然了...
  • 1.理解二维傅里叶变换定义 1.1二维傅里叶变换 二维Fourier变换: 逆变换: 1.2二维离散傅里叶变换 一个图像尺寸为M×N的 函数的离散傅里叶变换由以下等式给出: 其中 。其中变量uv用于确定它们的...
  • *4.3.1离散傅里叶变换定义(91) 4.3.2离散傅里叶变换的基本性质(92) 4.4傅里叶变换的应用(94) 4.4.1解积分、微分方程问题(94) 4.4.2求解偏微分方程问题(95) 4.4.3电路系统求解问题(96) 数学家简介——傅里叶(97) ...
  • 数字信号处理理论、算法与实现》是2012年清华大学出版社出版的图书...3.1.1连续周期信号的傅里叶级数 3.1.2连续非周期信号的傅里叶变换 3.1.3傅里叶级数和傅里叶变换的区别与联系 …… 下篇统计数字信号处理 附录 索引
  • Matlab信号处理基础

    2019-10-01 21:39:28
    一. 简介  离散傅立叶、离散余弦离散小波变换是图像、音频信号常用基础操作,时域信号转换到不同变换域以后,会导致不同...一维离散傅里叶变换: 一维离散傅里叶逆变换: 一维离散余弦变换对定义 一维离...
  • 《数字信号处理理论、算法与实现》是2003年清华大学出版社出版的图书,作者是胡广书。绪论 O.1数字信号处理的理论 ...3.1.3傅里叶级数和傅里叶变换的区别与联系 …… 下篇统计数字信号处理 附录 索引
  • OpenCV学习笔记(四)

    2020-10-08 15:36:10
    傅里叶变换的理论就是任意函数都可以表示成无数个正弦余弦函数的的部分。 空间域是实数,频域分解后是复数,因此变换后有实数图像,虚数图像(幅度图像,虚数图像) 傅里叶变化的时候必须需要幅度图像虚数...
  • 香农小波

    2018-09-14 17:13:00
    在泛函分析中,香农小波可以是实小波也可以是复小波。...实香农小波的解析表达式可由逆傅里叶变换得到: 也可按: 其中 是出现在香农采样定理中的常见正弦函数。该小波有级的可微性,但是...
  • 算法工程师常用的数学知识点

    千次阅读 2019-03-22 18:01:34
    算法工程师常用的数学知识点 1.求矩阵的几种方法?...有分离变量法,拉氏变换法,格林函数法,傅里叶变换 3.插值拟合的联系区别? 他们的共同点都是通过已知一些离散点集M上的约束,求取一个定义在连续集合...
  • 数字信号处理习题答案第二版

    热门讨论 2010-03-28 18:43:51
    2.2 序列的傅里叶变换定义及性质 2.3 周期序列的离散傅里叶级数及傅里叶变换表示式 2.4 时域离散信号的傅里叶变换与模拟信号傅里叶变换之间的关系 2.5 序列的Z变换 2.6 利用Z变换分析信号系统的频域特性 习题 第...
  • 6.2.4傅里叶变换及傅里叶余弦变换和正弦变换算例 6.2.5傅里叶变换的应用 6.3拉普拉斯(Laplace)变换 6.3.1拉普拉斯变换 6.3.2拉普拉斯变换的性质 6.3.3单项式的拉普拉斯变换算例 6.3.4拉普拉斯逆变换 6.3.5拉普拉斯...
  • 6.2.4傅里叶变换及傅里叶余弦变换和正弦变换算例 6.2.5傅里叶变换的应用 6.3拉普拉斯(Laplace)变换 6.3.1拉普拉斯变换 6.3.2拉普拉斯变换的性质 6.3.3单项式的拉普拉斯变换算例 6.3.4拉普拉斯逆变换 6.3.5拉普拉斯...
  • 2.3.5 为什么离散傅里叶变换比其他变换得到了更广泛的应用? 78 2.3.6 什么是卷积定理? 79 B2.7 如果一个函数是两个其他函数的卷积,它的DFT 与另两个函数的DFT 是什么关系? 79 2.3.7 如何显示一幅图像的离散...
  • 文章目录基本符号表示求矩阵解线性方程求特征值特征向量奇异值分解对角化分解奇异值的定义:奇异值分解的定义:奇异值的求解举例:广义矩阵行列式快速傅里叶变换概率分布二项分布超几何分布正态分布对数正态...
  • 离散傅里叶变换(DFT)(包括离散傅里叶级数,DFT-IDFT对,DFT) 常用信号,bin宽度,采样持续时间采样率,FFT,Goertzel算法,线性, 周期性循环卷积,DFT泄漏,以及DFT的计算).Volume IV,the 该系列的高潮...
  • 研究实变函数泛函分析,在广义函数、偏微分方程理论、经典分析和傅里叶级数领域有重要贡献。在数学教学方面颇具影响力,其多部著作(包括与盖尔范德等合作的《广义函数》)已成为经典并广为流传。 目录 · · · ...
  • 2.0.7 酉矩阵的是什么样的?...............................................................................39 2.0.8 如何能构建一个酉矩阵?.................................................................
  • 算法导论(原书第三版)

    热门讨论 2013-03-06 14:31:34
    第30章 多项式与快速傅里叶变换 30.1 多项式的表示 30.2 DFT与FFT 30.3 高效FFT实现 思考题 本章注记 第31章 数论算法 31.1 基础数论概念 31.2 最大公约数 31.3 模运算 31.4 求解模线性方程 31.5 中国余数...
  • 算法导论中文版

    2016-10-26 10:13:58
    第30章 多项式与快速傅里叶变换  30.1 多项式的表示  30.2 DFT与FFT  30.3 高效FFT实现  思考题  本章注记 第31章 数论算法  31.1 基础数论概念  31.2 最大公约数  31.3 模运算  31.4 求解模线性...
  • 下面给出我封装的傅里叶变换类 <code class="language-cs">using System; /// <summary> /// 傅里叶变换 /// </summary> public sealed class Fourier { //快速傅里叶变换 public static void FFT...

空空如也

空空如也

1 2
收藏数 32
精华内容 12
关键字:

傅里叶变换和逆变换定义是