图嵌入，即用一个低维，稠密的向量去表示图中的点，该向量表示能反映图中的结构。但是在介绍图嵌入之前，可以大概描述一下词嵌入。

bert时代之前，word2vec是很有名的词嵌入技术，训练快，效果提升也比不用词向量明显。本质上就是由输入序列得到每个word的embedding，其目标函数为

即希望：给定上下文，当前词的概率更大。（skip-gram的意思也一致）

基本的图嵌入算法也借鉴了这个思想，问题就是图如何转化为序列

DeepWalk

DeepWalk: Online Learning of Social Representations. 2014

DeepWalk通过截断随机游走(truncated random walk)学习网络的嵌入表示，就是等于对图进行采样，得到多个节点序列，跳转概率可以由节点之间的权重决定。然后对节点序列学习节点的embedding表示

random walk实际上是一种可回头的DFS

LINE

Large scale information network embedding. 2015

高维空间中相近的点在低维空间中也是相近的，相近的定义如下

一阶相近

• 高维空间中：节点$i,j$之间的权重有经验分布：$\hat{p}_1(i,j)=\frac{w_{i,j}}{\sum_{(i,j)\in E}}$
• 低维空间中：则可以理解为embedding$\mu_i,\mu_j$的sigmoid函数（$p_1(i,j)=\frac{1}{1+\exp{(-u_i^Tu_j)}}$）
• 目标为最小化两个分布的距离，距离用KL散度，$O_1=-\sum_{(i,j)\in E}w_{i,j}\log p_1(i,j)$

二阶相近，用于有向图

• 高维：node之间有多少公共一度节点(比如5和6之间有4个公共一度节点，也就是有多少相同的邻居)，经验分布为$\hat{p}_2(i,j)=\frac{w_{i,j}}{d_i}$，$d_i$是节点的出边的权值和
• 低维：条件概率$p_2(j|i)$可以表示为softmax形式
• 目标为最小化两个分布的距离，距离用KL散度，$O_2=-\sum_{(i,j)\in E}w_{i,j}\log p_2(j|i)$

每个顶点维护两个embedding向量，一个是该顶点本身的表示向量，一个是该点作为其他顶点的上下文顶点时的表示向量

Node2vec

node2vec: Scalable Feature Learning for Networks. 2016

Node2vec基于二阶随机游走，通过参数$p,q$来控制游走策略，平衡BFS和DFS（DFS倾向于获取结构相似性，BFS倾向于获取内容相似性，即局部相似性）。通过改变采样结果来优化效果

定义当前节点为$v$，上一节点为$t$，随机游走到下一个节点$x$的概率为

其中，$\alpha$是控制函数，其定义为

其中，$d_{tx}$是节点$t,x$之间的最短路径长度，因为最大就为2，所以有二阶的概念。$q$为前进参数（决定搜索远离$t$的节点的概率），$p$为回溯参数（决定了有多少概率下一个节点还是$t$）

如果图的边存在初始权重，则计算下一节点为$x$的概率时需要考虑权重，也就是归一化的时候乘上权重。

BTY：当$p=1,q=1$时，Node2vec等价于random walk

SDNE

Structural Deep Network Embedding. 2016

SDNE使用深度学习模型学习网络嵌入，使用自编码器的思想尝试对图的邻接矩阵进行嵌入表示，并且加入节点相似的考虑，属于半监督方法。其损失函数与LINE类似，可以分为一阶相似损失和二阶相似损失，其中

• 一阶损失：邻居节点之间的表示向量应该接近
  • $\mathcal{L}_1=\sum_{i,j} s_{i,j}||u_i-u_j||_2^2$，其中$s_{i,j}$表示两个节点的权值，$u$是节点的embedding
  • 这一部分是监督模式
• 二阶损失：具有相似邻居的节点之间的表示向量应该相似
  • $\mathcal{L}_2=\sum_{i} ||(\hat{x}_i-x_i)\odot b_i||_2^2$
  • 这个便是自编码器的重建误差，$x_i$是原始的邻接向量，$\hat{x}_i$是重建的邻接向量
  • 这里的$b_i$主要用来惩罚$x_i=0$的情况，因为邻接向量一般比较稀疏，解码器输出全0向量也是不错的解；另外不邻接也不代表没关系
  • 这一部分是无监督模式

整体的损失函数如下：

最后一项是正则项，主要对网络中的参数进行惩罚

Struc2vec

struc2vec:Learning Node Representations from Structural Identity. 2017

Struc2vec认为embedding不应该任何相邻性，而只考虑空间结构相似性。也就是要从：相似的节点往往有比较相似的空间结构

论文表示空间结构相似的方法是：如果两个节点的所有邻接节点构成的序列相似，那么这两个节点相似.

定义$R_k(u)$为与节点$\mu$距离为$k$的节点集合，$s(K)$表示节点集合$K$的有序度序列，函数$g$可以表示两个序列的相似度函数(这里可以使用DTW算法)，令

表示节点$u,v$之间的结构不相似性。我们按照不同的$k$分层，同层之间的节点权重为

不同层的话，需要先层级转换，有上一层、下一层两种选择，对应权重为

其中，$\overline{w_k}$是第$k$层的平均权值，$\Gamma_k(u)$表示第$k$层与$u$相连的边的边权大于平均边权的边的数量。是每一步会以一个概率$p$留在当前层，$1-p$跳出本层，如果留在本层，则下一个节点的概率是

如果跳出本层，则有

综上所述，基本流程如下：

• 根据上面的权重公式计算：
  • 同一层中的节点权重($w_k(u,v)$)
  • 不同层次的同一顶点权重($w(u_k,u_{k\pm1})$)
• 获取顶点序列
  • 在当前层游走($p_k(u,v)$)
  • 切换到上下层的层游走($p(u_k,u_{k\pm 1})$)
• Skip-Gram来生成representation，然后训练embedding表示

Struc2vec有成功的工业应用案例，蚂蚁金服风控模型应用了Struc2vec后，较之前的node2vec有了质的提升

GraphSAGE

Inductive representation learning on large graph. 2017

上面的方法都是直推式的学习方法，可以从graph中学习到一个矩阵表示，当图结构变化时是需要重新学习的。而GraphSAGE是一种归纳式学习方法，可以用邻居节点直接学习出新增节点的embedding

对每一层，主要有以下几个步骤

1. 采样当前节点的邻居顶点
2. 用聚合函数将上一层邻居的表示聚合起来
   • 聚合函数应该对输入顺序不敏感，且有较好的表达能力，候选有
   • mean aggregator
   • pooling aggregator
   • LSTM aggregator
3. 将上一层邻居的聚合表示和上一层当前节点的表示拼接起来，做一个线性映射

参数学习

• 有监督：比如节点分类，可以根据任务目标直接设置
• 无监督：临近的顶点具有相似的向量表示，分离的顶点的表示尽可能区分

GraphGAN

GraphGAN: Graph Representation Learning with Generative Adversarial Nets. 2018

主要思想：

Discriminator$D(v,v_c;\theta_D)$

D判断一条边是否为原始图中的边，即给定节点，判断是否存在边$p(e_{i,j}|v_i,v_j)$

给定两个节点的表示，D判定两个节点有边的概率是

这里$d_i,d_j$是D中的节点embedding，所有节点构成的embedding集合就可以看成是D的参数$\theta_D$

Generator$G(v|v_c;\theta_G)$

G生成图中一条不存在的边，也就是要根据给定节点做一个连接，也就是要学习$p(v|v_c)$.（毕竟我们的主要目的就是学习到采样算法）。容易想到用softmax来表示，

这里$g_v,g_{v_c}$是G中的节点embedding，所有节点构成的embedding集合就可以看成是G的参数$\theta_G$。G和D中不共用节点表达，所以最后的训练结果不能当作节点embedding。但是存在两个问题

• 计算量大
• 没有考虑网络的拓扑结构

Graph Softmax

文章提出了Graph Softmax的概念，解决上述两个问题

• 以$v_c$为根，BFS构建树，树中$v_c$到任意节点可达且路径唯一，通过定义父子节点的关联概率（softmax，这里因为是父子节点，所以维度小很多了）和路径概率连乘，我们可以求得$v_c$到任意节点的概率

模型训练的时候就是训练D和G的参数，然后利用G进行路径采样，按照skip-gram的方式训练embedding，G的采样可以是：

• 根据Graph Softmax的结果直接进行采样
• 文章还提供了一种方法，不介绍了

效果：链接预测任务在效果上并没有提升太多，比DeepWalk好，跟node2vec差不多。但是也就是套上了GAN吧

引用

[1]. Graph Neural Network Review. 2018

[2]. All the paper mentioned above.

BERT开启了NLP领域预训练模型的时代，BERT之后大量的改型出现，以下会介绍一些。

ALBERT

ALBERT的设计目标是解决BERT参数量大的问题

其主要做了如下的修改

• embedding分解
  • intuition是：transformer的输入词的embedding维度和隐层输出维度一样大，但是隐层除了词本身信息还包含了上下文信息，所以词的embedding维度可以小一点
  • 降低维度的方法是对输入的onehot矩阵进行分解，映射到低维度空间E，然后再映射到H维，输入到Transformer中。将参数量由O(VH)降到O(VE+EH)，当E远小于H时，参数量会下降很多。（假设V为词的总数）
• 参数贡献
  • 共享encoder内的所有参数，包含多头注意力和前向网络
• Sentence-Order Prediction
  • BERT的next sentence prediction是个二分类任务，负样本是通过采用两个不同的文档的句子，后续的研究发现该任务效果并不好。NSP其实包含主题预测与句子关系一致性预测两个子任务，但是主题预测相比于关系一致性预测简单太多了，模型学习NSP任务的时候可能只学到了主题预测，而没学到句子关系一致性
  • SOP则在样本选取上去除了主题不同的因素，将正样本反过来当作负样本

ALBERT论文表示在训练了100w步之后，模型依旧没有过拟合，于是乎作者移除了dropout，没想到对下游任务的效果竟然有一定的提升。这也是业界第一次发现dropout对大规模的预训练模型会造成负面影响

ERNIE

ERNIE是大百度的中文预训练模型，有两个版本

1.0

ERNIE1.0在BERT的基础上做了如下事情

• 在mask语言模型上，不再局限于mask单个token，而是考虑mask短语和实体
• 直接对先验语义知识单元进行建模，增强了模型语义表示能力
• 海量中文数据，Dialogue Language Model

2.0

ERNIE2.0的要点如下：

• 多任务学习的引入，输入层加入了task embedding
• 构建了词法级别，语法级别，语义级别的预训练任务
  • 词法
    • mask短语和实体，同1.0
    • 大写字母预测：大写的词一般会有特殊含义
    • Token-Document关系预测：预测一个词在文中的A 段落出现，是否会在文中的B 段落出现
  • 语法
    • 句子顺序预测：文本分段，所有shuffle的组合后模型预测正确顺序
    • 句子距离预测：三分类任务（0表示两个句子是同一个文章中相邻的句子，1表示两个句子是在同一个文章，但是不相邻，2表示两个句子是不同的文章）
  • 语义
    • 判断句子对之间的语义关系，比如修辞
    • 搜索下query和title的相关性
• 大量的百度生态语料
  • 搜索日志
  • 贴吧对话
  • 百科数据
  • 新闻内容

XLNET

XLNet: Generalized Autoregressive Pretraining
for Language Understanding

Elmo、GPT这种单向语言模型属于自回归语言模型(
autoregressive)，模型在当前位置只能看到之前看到过的数据。Bert这类双向语言模型，属于自编码语言模型（autoencoder），可以对上下文进行完整建模，在BERT与GPT的对比数据中也可以看出来其优点。但是这种模型也存在问题：

• bert训练时用到了mask语言模型，引入了[MASK]标识，但是fine-tuning阶段没有，导致预训练阶段和fine-tuning阶段存在不一致的问题
• 模型在预测一个被mask掉的单词，无法利用其他被mask掉的单词信息

xlnet就是想鱼和熊掌兼得，那么怎么能够在单词Ti的上文中Contenxt_before中揉入下文Context_after的内容呢?

Permutation Language Model

最naive的思想就是：在预测$x_k$时，固定$x_k$，将$x_{!= k}$打乱，这样当前单词就能看见原来在其之后的单词了。在随机排列组合后的各种可能里，再选择一部分作为模型预训练的输入。

但是这样会有问题，假设出现一个长度为n的序列，原序列为$x$，两个排列$z^{(1)},z^{(2)}$，第t个位置不一样(对应于之前的$x_i,x_j$)，之前的位置都一样，所以由自回归语言模型定义可知

即，对$x_i,x_j$的预测满足同一分布，这显然是不合理的

并且，fine-tuning时不可能也去排列组合原始输入

双流自注意力机制

双流注意力机制就是为了解决上述问题的，分为query流和内容流，其实就是在两个层面表示当前输入（内容层面和位置层面），其中

• 内容流self-attention
  • 内容编码信息$h_t$，计算方式和标准的self-attention一致
  • 能看到自己
  • 内容流输入是token的Embedding向量
• query流self-attention
  • 位置编码信息$g_t$，后一层的query向量不包含当前位置的查询向量
  • 不能看到自己
  • 在模型输入端对每个token都是统一的，是可学习的参数

上图中，预测下一层的内容向量时，用到当前层能看到的所有内容向量（包括自己）[a]；预测下一层的query向量时，用到当前层能看到的所有内容向量（不包括自己）[b]。

整体上来看，以序列$x=[x_1,x_2,x_3,x_4]$为例，通过attention mask矩阵来完成mask操作，决定排列顺序后即可得到mask矩阵。假如排列之后得到$[x_3,x_2,x_4,x_1]$，mask矩阵也有两个分为内容流（能看见自己）、query流（不能看见自己）两个，上图中，红色表示可见，白色表示不可见，第$k$行表示第$k$个位置能看到哪些位置的信息

Transformer XL

借助transformer xl，增强对长文本的友好程度，其主要思想就是分段然后引入recurrent连接结构

pretrain & finetune

• pretrain阶段
  • 在输出端对query流向量预测相应的token
  • 只预测有足够长的依赖上下文的token，降低训练难度
  • 放弃了Next Sentence Prediction任务
  • 与BERT相比，加大增加了预训练阶段使用的数据规模
• finetune阶段
  • 只需要内容流向量，不再需要query流向量
  • 使用的时候，只需要内容流向量

RoBerta

RoBERTa: A Robustly Optimized BERT Pretraining Approach

较于BERT，其升级点如下

• 训练模型时间更长，Batch Size更大，数据更多
• 放弃Next Sentence Prediction训练任务
• 对较长序列的训练
• 动态mask应用于训练数据的mask模式
  • BERT静态mask：随机mask和替换在开始时只执行一次，后续保存
  • 作者将训练数据重复10次，以便在40个epoch中以10种不同的方式对每个序列进行mask，避免在每个epoch中对每个训练实例使用相同的mask
• 新建数据集（CC-NEWS）
• 使用Sennrich[2]等人提出的Byte-Pair Encoding (BPE)字符编码
  • 避免出现较多的未登录词

T5

ELECTRA

Efficiently Learning an Encoder that Classifies Token Replacements Accurately

ELECTRA的特色如下

• 放弃BERT随机选取token预测的方法，而是通过MLM过滤非常容易学到的token，加大学习难度
• 预测目标不是预测目标究竟是哪个token，而是预测这个句子中哪些词被替换过，也就是说模型需要看输入的每一个token，而不仅仅是被mask选取的那些，加速了学习过程
• 解决BERT中MASK标志在train和finetune阶段的不一致问题

GAN视角

模型整体可以看成有两部分，一部分是Generator，一部分是Discriminator。模型依然需要随机地mask一部分token，但是用途不一样

流程

• 对于输入文本序列，随机mask一部分token（15%）
• 带MASK标志的输入序列，G会预测每个被MASK掉的token具体是什么，这里其实就是MLM做的事情
• D判别这个序列中哪些token是G生成的
  • 二分类，

需要注意的是，G的训练方式与传统的GAN不一样，G的训练目标不是去糊弄Discriminator，而是通过极大似然估计训练。因为D的梯度不能直接流到G，原因是G输出的token在表示上是离散的

其中，$i$是被选中mask的token序号。作者也尝试了用强化学习的训练思路做，但是效果没有直接使用MLE效果好

而Discriminator因为是要对每个token判断是否是原始token，所以可以看成一个二分类问题（序列上看也可以看成序列标注，只是tag之间没有直接关系），其损失函数为交叉熵形式

这里可以看成是使用MLM的负采样方法，颇有word2vec的CBOW意味。类似地，把多分类换成二分类也可以有效降低参数数量。此外，D的目标也刚好消除了BERT中MASK标识导致的mismatch问题

所以，整体的目标就是

其中，$X$是整体的数据集，$\lambda$是平衡系数，作者设为50，原因是D的任务较G简单，损失也小。

其他点

• G和D共享token的embedding
  • G会对embedding进行调整，但是D不会，所以需要参数共享
• 建议G要小一点
  • G太猛了，D学起来会比较费劲。D可能会将注意力更多放在对G的建模上而不是实际的数据分布
  • 建议G的规模为D的1/4-1/2

[1]. 一文揭开ALBERT的神秘面纱

[2]. 一文读懂最强中文NLP预训练模型ERNIE

[3]. XLNet:运行机制及和Bert的异同比较

[4]. 自然语言处理之XLNet

[5]. XLNet: Generalized Autoregressive Pretraining
for Language Understanding

[6]. RoBERTa: A Robustly Optimized BERT Pretraining Approach

[7]. 如何评价RoBERTa?

[8]. Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer

[10]. ELECTRA: PRE-TRAINING TEXT ENCODERS AS DISCRIMINATORS RATHER THAN GENERATORS

[11]. 如何评价NLP算法ELECTRA的表现？

XGBoost是提升树的一种，是一种非常常用且效果很好的算法。

目标函数

提升树的基本思想就是将$K$个弱学习器以相加的方式集成到一起

假设有数据集$D=\{(x_1,y_1),…,(x_n,y_n)\}$
对于树型弱学习器，结构化损失函数的形式如下：

其中，正则项有两个部分，$T$表示叶子节点的数量，$w$是叶子节点的权值。

为了推导，我们假设第$t$次迭代的损失函数为

做一次泰勒二次展开

其中，$g_i=\partial_{\hat{y_i}^{(t-1)}}l(y_i,\hat{y_i}^{(t-1)})$是$l$对$\hat{y_i}^{(t-1)}$的一阶导数，$h_i=\partial^2_{\hat{y_i}^{(t-1)}}l(y_i,\hat{y_i}^{(t-1)})$是二阶导数。将常数项放在一起，我们有

做一次转换，将上式中的样本求和转换到以叶子节点求和。令$q(x_i)$表示$x_i$属于的叶子节点（也就是表示了整课树了），$I_j=\{i|q(x_i)=j\}$表示属于第$j$个叶子节点的样本序号集合。对于$\sum_i^ng_if_t(x)$，将其分散到各个叶子节点上，第$j$个叶子节点上的样本序号为$I_j$，整体有

对于$w$而言，上式是一个二次函数。最优值可以通过对$w_j$求导，有

带回损失函数有

上式可以看成对树结构$q$函数的度量。有了上式，我们可以衡量分裂节点前后目标函数的变化。未分裂时，当前节点就是叶子节点，分裂后一个叶子节点($I$)变成了两个($I_L$和$L_R$)，树的其他部分不变化，所以我们只考虑在当前位置的目标函数变化

分裂树节点可以使用贪婪的方法进行，从单个结点开始.

收缩（shrinkage）与列采样

除了上一节损失函数中加入正则项，XGBoost还有收缩（shrinkage）与列采样这两种减少过拟合的方法

• shrinkage在每迭代一棵树后为其加上一个收缩权值，减少当前树的作用，为后续的树留下空间
• 列采样的思想在随机森林中出现，就是在建树过程中选择一部分属性值作为可能分裂属性，而不是所有；除了减少过拟合，还可以降低计算复杂度

节点分裂

贪婪算法

• 对于离散特征，枚举所有的分裂方法（所有特征、所有取值），根据目标函数选择分割方法
• 对于连续特征：一般会先排序，但是枚举带来的计算复杂度太高

近似算法

主要思想是根据特征的分位数给出候选分割点，根据分割点将连续特征转换到bucket中，计算bucket中的聚合统计量。候选分割点可以在算法初始阶段计算（全局），也可以在每次split之后重新计算（局部），一般地，全局策略需要更多的候选分裂点，可以重复使用；而局部策略在每次split之后计算，在层数较深的树中会比较好。

稀疏性

现实中，输入很可能是稀疏的：

• 缺失值
• 未见过的值
• 类似ont-hot的人工特征

算法对于缺失值的处理如下：

• 遇到缺失值，算法将其划分到默认的分支
• 默认分支选取是通过非缺失样本算出来的最优解

下图是计算划分以及默认分支的算法

系统设计

• Column Block：支持列采样；使得列的划分点查找可以并行化
• Cache-aware Access：预取技术、block大小
• 外存（Out-of-core）计算：主存有限，需要外存，如何解决外存
  • block压缩
  • block分片，即使用多个外存

[1]. Tianqi Chen, Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. 2016

介绍

BERT=Bidirectional Encoder Representation from Transformers，就是用双向transformer编码器学习表征

基本结构如下

模型是层级结构，每层一个transformer的encoder。与模型体量相关的变量是：

• 层数$L$：即transformer encoder的个数
• 隐层维度$H$：等于word embedding的维度
• 多头注意力的头数$A$：self-attention中multi-head的head数量

输入

输入token表征是由三个加起来得到的，分别是token的embedding、位置编码、句子的embedding。bert中位置编码是当作参数学习出来的（transformer则是写死的）

预训练

Masked语言模型

训练过程中随机mask 15%的token，而不是把像cbow一样把每个词都预测一遍。最终的损失函数只计算被mask掉那个token。

如果一直用标记[MASK]代替（在实际预测时是碰不到这个标记的）会影响模型，所以随机mask的时候10%的单词会被替代成其他单词，10%的单词不替换，剩下80%才被替换为[MASK]

下个句子预测

涉及到QA、推理方面的任务，所以训练加入了句子关系建模。训练的输入是句子A和B，模型预测B是不是A的下一句。

语料的选取很关键，要选用document-level的而不是sentence-level的，这样可以具备抽象连续长序列特征的能力。

微调与应用

• 单个句子分类：结果在CLS对应的位置
• 句子对分类：结果在CLS对应的位置
• 问答任务：第二个句子是答案段落，

调参

• Batch size: 16, 32
• 学习率 (Adam): 5e-5, 3e-5, 2e-5
• Number of epochs: 3, 4

总结

优点

• 用的是Transformer，也就是相对rnn更加高效、能捕捉更长距离的依赖
• 效果很好

缺点：

• [MASK]标记在实际预测中不会出现，训练时用过多[MASK]影响模型表现
• 每个batch只有15%的token被预测，所以BERT收敛得比left-to-right模型要慢

相关工作

ELMO

ELMO使用两层双向LSTM抽取特征，最后将双向的结果拼接起来

GPT

GPT使用的是自左向右的transformer，即不能看到后面的数据，只能与前面的word计算attention

[1]. BERT: Pre-training of Deep Bidirectional Transformers for
Language Understanding.

[2]. Google BERT详解

介绍

Transformer放弃了将RNN/CNN作为encoder-decoder，仅仅用attention组件。不仅取得了更好的效果，并且其可并行的结构也可以降低训练时间

整体上看，Transformer是一个序列到序列的模型，基于encoder-decoder框架。编码器、解码器多个叠加在一起，大致如下所示：

编码器

每个编码器包括两个层，分别是多头注意力层和position-wise的前向网络，每个层都有一个残差连接+层normalization，

多头注意力层

先看单头注意力，其核心是Scaled Dot-Product Attention（编码器中的Scaled Dot-Product Attention不需要mask，因为编码时可以看到整个序列）。基本是这样，每个头有3个线性映射矩阵$Q, K, V$，对于输入（向量序列构成矩阵），乘以3个矩阵映射到$Q’,K’,V’$，然后计算

其实也就是计算$Q’$每个向量和$K’$每个向量的关系，归一化后当作$V’$的系数加权求和，其中$d_k$是$Q’$中单个向量的维度。

多头注意力，每个头有不同的$Q, K, V$（目的是学习到不同的表征），得到的多个结果拼接起来，最后做一个线性变换

encoder是并行的体现，并行主要是可以同时计算多个head的输出

前向网络

这一层的输入输出维度一直，并且，属于输入序列中的每个位置i，其对应的参数是一致的，所以叫position-wise

解码器

解码器有两种attention，第一种直接作用在输入上的self-attention，多了mask的概念（因为解码按顺序进行的，不能获取未来的信息）。第二种不是self-attention，其中的$K’,V’$均来自编码器，$Q’$来自解码器

多个解码器叠加，每个解码器中的第二个attention中的$K’,V’$均来自编码器。最后的输出经过线性变换+softmax得到输出

输入与位置编码

对输入序列的每一个word，先将其通过词嵌入算法转换为词向量，第一个编码器接受词向量序列，后面的编码器接受前面编码器的输出

但是问题是这种方法没有考虑加入位置信息，所以作者加入了位置向量，并且将每个word的位置向量和词向量加起来作为这个词的特征向量。每个word的位置向量和其词向量维度一样，假设其位置为$pos$，则其位置向量为

其中$d$是词向量的维度。这个编码可以表示词之间的相对位置。

总结

self-attention处理特别长的序列时，计算复杂度会比较高，会做一些限制，比如当前位置只能看到其前后$r$个位置的词

self-attention之于CNN、RNN的优势

• 每层的计算复杂度
• 序列操作
• 最大路径长度（信号需要在网络中前向、后向传递的长度）
• 可解释性

前三项的比较如下图

其中，$n$序列长度，$d$是模型维度，$k$是卷积核大小，$r$是受限的self-attention对应的neighborhood大小

transformer的缺陷如下：

• 是不是对局部特征的捕捉能力降低了
• 位置编码用三角函数是不是不够

最后贴上经典的transformer动态图

Transformer XL

理论上，Transformer的encoder可以接受无限长的输入，但是限于计算资源问题，通常encoder处理的长度也是有限的。Transformer XL就是要解决输入长度过长的情况

语言模型建模

以语言模型为例，语言模型就是要计算输入序列的概率

对于条件概率$p(t_i|t_{0:t-1})$，可以使用transformer对其建模。需要注意的一点是，上面的条件概率要求只能看到当前左侧的token，所以需要使用类似masked attention的方法

vanilla model

实作上，一种简单粗暴的方法是对输入进行截断，在每个segment内分别处理，忽略了段之间的上下文信息。具体地

• 训练阶段：把文本切成segment，每个segment单独训练
• 预测阶段：按segment处理，移动步长为1

大致的训练方法见 深度Transformer构建字符语言模型

recurrent model

主要思想是将上一个segment对应的hidden state保存起来，论文图中当前segment也只会用到上一segment中的信息，不用上上个segment的信息。可以形成segment的recurrent结构，不过只要增大cache，可以考虑使用前面更多的segment信息

[1]. Attention Is All You Need. 2017

[2]. 图解Transformer（完整版）

[3]. Transformer-XL: Attentive Language Models
Beyond a Fixed-Length Contexthttps://arxiv.org/pdf/1901.02860.pdf

SGD：Stochastic Gradient Descent

mini-batch的更新方法

• 输入学习率$\epsilon$
• 停止条件未满足
  • 从样本集合中采样$m$个样本的batch
  • 计算梯度$g=\frac{1}{m}\bigtriangledown_{\theta} \sum_i L(f(x_i,\theta),y_i)$
  • 参数更新$\theta=\theta-\epsilon g$

学习率是SGD中的关键参数。在实践中，有必要随着时间推移减小学习率，一般的实践是将学习率线形衰减指导第$\tau$次迭代
math
\epsilon_k=(1-\alpha)\epsilon_0+\alpha \epsilon_{\tau}

其中$\alpha=\frac{k}{\tau}$。在$\tau$次迭代后，一般使$\epsilon$保持常数。$\tau_t$可以设置为$\tau_0$的1%。

Momentum

SGD在处理高曲率、小但一致的梯度，或者带噪声的梯度时，学习过程有时会很慢。动量算法引入了变量$v$充当速度角色。

• 输入初始速度$v$，学习率$\epsilon$
• 停止条件未满足
  • 从样本集合中采样$m$个样本的batch
  • 计算梯度$g=\frac{1}{m}\bigtriangledown_{\theta} \sum_i L(f(x_i,\theta),y_i)$
  • 计算更新速度$v=\alpha v-\epsilon g$
  • 参数更新$\theta=\theta+v$

$\alpha$叫做动量参数，一般取值为0.5、0.9、0.99。

Nesterov：Nesterov Accelerated Gradient（NAG）

此方法与动量方法的不同在于计算梯度步骤，Nesterov在每一步更新中，使用当前参数和速度得到临时更新，然后在临时更新后的参数的基础上计算梯度。Nesterov方法可以解释为往标准动量方法中添加了一个校正因子。

• 输入初始速度$v$，学习率$\epsilon$
• 停止条件未满足
  • 从样本集合中采样$m$个样本的batch
  • 计算临时更新$\hat{\theta}=\theta+\alpha v$
  • 计算梯度$g=\frac{1}{m}\bigtriangledown_{\hat{\theta}} \sum_i L(f(x_i,\hat{\theta}),y_i)$
  • 计算更新速度$v=\alpha v-\epsilon g$
  • 参数更新$\theta=\theta+v$

AdaGrad

AdaGrad记录参数在每个维度上的梯度累计量，然后缩放每个参数反比于其梯度累积量平方根，减小梯度过大的方向更新过快、梯度过小的方向更新过满的缺陷。

• 输入小常数$\delta(10^{-7})$，学习率$\epsilon$
• 初始化梯度累计量$r=\bold{0}$
• 停止条件未满足
  • 从样本集合中采样$m$个样本的batch
  • 计算梯度$g=\frac{1}{m}\bigtriangledown_{\theta} \sum_i L(f(x_i,\theta),y_i)$
  • 累计平方梯度$r=r+g\odot g$
  • 计算更新$\Delta \theta\gets- \frac{\epsilon}{\delta+\sqrt{r}}\odot g$
  • 应用更新$\theta= \theta+\Delta \theta$

在凸优化背景下，AdaGrad有一些令人满意的性质。但经验上，对于训练深度模型，AdaGrad从训练开始时累计梯度会导致有小学习率过早、过量的减小。此算法在某些模型上效果不错，但不是全部。

RMSProp：Root Mean Square Prop

RMSProp是为了解决AdaGrad中从训练开始时累计梯度会导致有小学习率过早、过量的减小的缺陷，也有忘掉过去的功能，方法是引入参数$\rho$进行权重衰减。

• 输入小常数$\delta(10^{-6})$，学习率$\epsilon$，衰减速率$\rho$
• 初始化梯度累计量$r=\bold{0}$
• 停止条件未满足
  • 从样本集合中采样$m$个样本的batch
  • 计算梯度$g=\frac{1}{m}\bigtriangledown_{\theta} \sum_i L(f(x_i,\theta),y_i)$
  • 累计平方梯度$r=\rho r+(1-\rho)g\odot g$
  • 计算更新$\Delta \theta\gets- \frac{\epsilon}{\sqrt{\delta+r}}\odot g$
  • 应用更新$\theta= \theta+\Delta \theta$

RMSProp已被证明是一种有效且实用的深度神经网络优化算法，是实践者常采用的方法之一。

Adam：A Method for Stochastic Optimization

Adam是采用了梯度的一阶估计、二阶估计的算法，并且加入了偏差修正，可以看成是AdaGrad、RMSProp思想的结合。

• 输入矩估计的指数衰减速率$\rho_1,\rho_2$(默认建议为0.9、0.99)
• 输入小常数$\delta(10^{-6})$，步长$\epsilon$，衰减速率$\rho$
• 初始化一阶矩、二阶矩量$s=\bold{0},r=\bold{0}$
• 初始化时间步$t=0$
• 停止条件未满足
  • 从样本集合中采样$m$个样本的batch
  • 计算梯度$g=\frac{1}{m}\bigtriangledown_{\theta} \sum_i L(f(x_i,\theta),y_i)$
  • $t=t+1$
  • 更新有偏一阶矩估计$s=\rho_1 s+(1-\rho_1)g$
  • 更新有偏二阶矩估计$r=\rho_2 r+(1-\rho_2)g\odot g$
  • 修正一阶矩的偏差$\hat{s}=\frac{s}{1-\rho_1^t}$
  • 修正二阶矩的偏差$\hat{r}=\frac{r}{1-\rho_2^t}$
  • 计算更新$\Delta \theta=-\epsilon \frac{\hat{s}}{\sqrt{\hat{r}}+\delta}\odot g$
  • 应用更新$\theta= \theta+\Delta \theta$

这里的偏差修正可以这么看，刚开始一般会给定一个$s_0=0$，初期计算的几个结果会与真是的平均值有较大的差异，也就是有冷启动问题。用上面的修正公式进行修正，随着$t$增大，$\hat{s}$与$s$越来越接近，刚开始差距大一些，后期影响逐渐减小。

至于为什么第一步是$\frac{1}{1-\beta}$，是因为给定$\beta$，指数加权平均可以近似看成$\frac{1}{1-\beta}$个数据的移动平均值。见参考文献

Adam通常被认为对超参数的选择相当鲁棒。

[1]. 什么是指数加权平均、偏差修正?

python有多种工具包，其中就包括一些可以提供网页服务的package，比如Django、CherryPy等。在不同的情况下一般有不同的选择，比如如果只想是通过浏览器下载服务器上的文件，那么通过SimpleHTTPServer即可

1

python -m SimpleHTTPServer 8000

今天介绍的是一种上手极快的工具，CherryPy，下面会通过一些例子展示如何快速搭建自己需要的简单网页。

安装

pip安装即可

返回静态网页

一般的使用方法都是封装一个app类，然后在这个类中定义函数，将函数设置为cherrypy.expose则表示可以通过url访问这个函数。生效的时候通过quickstart(Test(), '/', conf)函数生效，这个函数有三个参数，后两个是应用的根位置和配置词典，为可选参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import cherrypy

class Test(object):
    @cherrypy.expose
    def index(self):
        return "Hello world!"

    @cherrypy.expose
    def generate(self, param='bingo'): #给定param参数
        return 'calling generate %s' % param 


if __name__ == '__main__':
    cherrypy.quickstart(Test())

上面这个例子，我们可以通过http://localhost:8080/generate?param=success返回calling generate success.

提交form

如果我们希望在网页端采集用户的输入，那么我们就需要通过form获取了。网页端用户操作的组件由html中的name属性指示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import cherrypy


class Test(object):
    @cherrypy.expose
    def index(self):
        return """<html>
          <head></head>
          <body>
            <form method="get" action="generate">
              <input type="text" value="bingo" name="param" />
              <button type="submit">generate</button>
            </form>
          </body>
        </html>"""

    @cherrypy.expose
    def generate(self, param='bingo'):
        return 'calling generate %s' % param


if __name__ == '__main__':
    cherrypy.quickstart(Test())

如果想返回一个网页，那么直接return这个网页的内容即可。这里是通过get方式发送form数据，也可以使用post，推荐使用post

配置

默认配置一般在Lib/site-packages/cherrypy/scaffold/site.conf中，内容如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14

[global]
# Uncomment this when you're done developing
#environment: "production"

server.socket_host: "0.0.0.0"
server.socket_port: 8088

# Uncomment the following lines to run on HTTPS at the same time
#server.2.socket_host: "0.0.0.0"
#server.2.socket_port: 8433
#server.2.ssl_certificate: '../test/test.pem'
#server.2.ssl_private_key: '../test/test.pem'

tree.myapp: cherrypy.Application(scaffold.root, "/", "example.conf")

全局配置

这里主要是全局【global】配置，在代码中可以通过

1
2

cherrypy.config.update({'server.socket_host': '64.72.221.48',
                        'server.socket_port': 80})

进行更改

如果修改端口后浏览器上打不开网页，其他都ok的话，需要看一下这个端口是不是系统默认端口，比如9090

局部配置

局部配置仅在单个app内部生效，由/符号开头，形式如下

1
2
3
4
5

[/]
tools.trailing_slash.on = False

[/app1]
tools.trailing_slash.on = True

代码中这样用

1
2
3
4
5
6

config = {'/':
    {
        'tools.trailing_slash.on': False,
    }
}
cherrypy.tree.mount(Root(), config=config)

其他配置

也可以加其他配置，与上面所述配置区分开即可

1
2
3
4

[Databases]
driver: "postgres"
host: "localhost"
port: 5432

当然这些配置自己准备配置文件也可以

用户session

session的使用就是要记住用户的一些设置或历史数据，主要是通过cherrypy.session这个字典完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import cherrypy

class Test(object):
    @cherrypy.expose
    def index(self):
        return "Hello world!"

    @cherrypy.expose
    def generate(self, param='bingo'): #给定param参数
        ret = 'calling generate %s' % param
        cherrypy.session['buf'] = ret
        return ret

    @cherrypy.expose
    def display(self):
        return cherrypy.session['buf']


if __name__ == '__main__':
    conf = {
        '/': {
            'tools.sessions.on': True
        }
    }
    cherrypy.quickstart(Test(), '/', conf)

多应用

单个应用的时候，我们通过

1

cherrypy.quickstart(Blog())

启动应用，但是多个应用的时候这个函数的capacity不够，这时候用cherrypy.tree.mount函数，如下

1
2
3
4
5

cherrypy.tree.mount(Blog(), '/blog', blog_conf)
cherrypy.tree.mount(Forum(), '/forum', forum_conf)

cherrypy.engine.start()
cherrypy.engine.block()

实现上，mount函数是把quickstart函数的返回结果当作一个参数使用，所以mount与quickstart并不互斥

概念

Hough转换是由Hough于1959年首次提出的，是图像分析、计算视觉中的一种特征提取算法，这个算法的目的是通过投票程序找到具有特定形状物体的不完美实例，其中投票程序在参数空间完成。在参数空间中，目标候选是选取名为累积空间的局部最大。

在数字图像处理领域，存在寻找直线、圆、椭圆的子问题。许多情况下，边界检测是此问题的预处理步骤，然而，由于数据本身、边界检测算法存在的不足，可能会导致边界数据缺失、空间错位等问题。所以，需要将提取的边界特征组合成一些规则的图形（线、圆、椭圆）。Hough转换的目标就是将边界特征组合成物体候选。

内容

Hough转换最简单的应用是检测直线，一条直线可以由斜率$k$和截距$b$确定，这里$$就构成了参数空间的一个点。给定一个点，可以找到经过这个点的无数条直线，每个直线在参数空间都对应一个点。但是这种方法有个缺陷，就是直线的斜率可能无限大。所以一般都把Hesse normal形式当做参数空间。

具体地，以$y=kx+b$为例，可以将其写成$r=x\cos\theta+y\sin\theta$，如上图所示，$r$是直线到原点的距离，所以一条直线就对应参数空间中的一个点$$，这个参数空间就是直线对应的Hough Space。

经过平面中的一个点可以确定无数条直线，每个直线都在参数空间对应一个点，这些点构成一个正弦波行。也就是说一个点在参数空间中对应一个正弦线。并且，共线的点在参数空间中会交于点$$，这个点就是这个直线对应的参数空间中的点。所以，查找共线点问题可以转化为检测共点曲线问题。

数值计算方法

直线检测的方法如下，以二维直线为例。构建一个二维累加器，记录对应的离散$r,\theta$对应的累加值。对每一个点及其邻居点

• 算法决定这两个点之间是否会构成直线，如果是，计算出这条直线对应的$$值
• 在二位累加器中找到对应的位置，加一

计算完后，检查二维累加器，局部极大值点可能就对应一条直线，当然直线的数量需要合适阈值决定。下图是一个例子，

泛化

To Be Continue
上面是直线检测的方法，参数空间是二维的。同理地，圆和椭圆都可以通过三维参数空间搞定。方法同上。

广义的方法于1981年由Dana H. Ballard提出，见https://en.wikipedia.org/wiki/Generalised_Hough_transform

引用

[1]. Hough transform. From Wikipedia, the free encyclopedia

GRU和LSTM都是RNNs中的特殊cell，目的是为了解决标准RNNs中的长期依赖的问题。这个问题是由于简单的RNNs求导公式中存在多个相同矩阵相乘的问题，容易造成梯度消散。使用Relu也只能说在一定程度解决了消散问题，但是会存在梯度爆炸的问题（见参考文献2）。

基本结构

相似点：都是通过引入门结构来解决长期依赖问题
不同点：门的数量，种类有差异

GRU

每个GRU单元的输入有$x^{(t)}$、$h^{(t-1)}$，分别表示当前步的输入和上一步的隐状态。基本思想是先构建新的memory，然后再和上一隐含状态加权得到新的隐含状态。

基本结构如下图所示

GRU包含几个门，分别是

• reset($r^{(t)}$)：从构建新new memory的角度出发，$r^{(t)}$决定$h^{(t-1)}$对new memory的贡献多大
• new memory($\hat{h}^{(t)}$)：由当前输入和上一步的隐含状态决定，当然，上一阶段隐含状态的重要性也受到reset gate的影响
• update($z^{(t)}$)：决定$h^{(t-1)}$对$h^{(t)}$的贡献多大
• hidden state($h^{(t)}$)：有上一步的隐含状态和new memory加权得到，权重有update gate决定

公式如下，懒得打了：

LSTM

同样地，每个LSTM单元的输入有$x^{(t)}$、$h^{(t-1)}$，分别表示当前步的输入和上一步的隐状态。需要注意的是，LSTM cell中的流动数据不仅包括隐含状态，还包括final memory 。然后生成final memory，这个过程需要input gate和forget gate。最后由output gate辅助生成当前的隐含状态(GRU没有这一步)。结构图如下

• new memory：由当前输入和前一步的隐含状态决定，前一步的隐含状态贡献度由
• final memory：由上一步的final memory和当前的new memory生成。其中上一步final memory的贡献度由forget gate决定，当前new memory的贡献度由input gate决定
• input gate：作用在上面已经说明了，由上一步隐含状态和当前输入决定
• forget gate：同input gate
• output gate：决定final memory对当前隐层状态的贡献

贴一下公式

需要注意的是，上面公式倒数第二个写错了，forget gate决定的是$c^{(t-1)}$.

关于LSTM、GRU是如何避免梯度问题的，关键是将简单RNN的求导过程中的乘法变成了加法，之前的记忆不会受到乘法的影响，因此不会过分衰减。同时又通过其他的门结构保证灵活性。

引用

[1]. LSTM 和GRU的区别

[2]. 理解RNN梯度消失和弥散以及LSTM为什么能解决

音乐信息检索是一个复杂的工作，需要涉及信号处理、计算机算法等知识。以下是粗略介绍。

基本概念

声音的物理特性

中学物理告诉我们，声音来源于振动，声音需要在介质中传播。声音有纯音（pure tone）和实音（real tone）之分，前者是标准的正弦波，后者则是前者的复杂组合。中学数学告诉我们，正弦波有两个主要的特质，分别是振幅dB（amplitude）和频率（frequency）。

音乐简单背景

音符（musical notes）

乐谱是由多个音符构成的，每个音符都有持续时间（duration）和响度（loudness）这两个性质。乐谱的音符可以划分成八度音阶（octaves），每个八度音阶就是8个音符（A-G or Do-Si），八度音阶有如下特点：

• 一个八度音阶中的音符的频率是上一个八度音阶中的音符的频率的2倍

多数乐器都提供了不止8个音符，这些多出来的就叫做半音（半拍）。

音色（Timbre）

对于同一个音符，不同乐器也会有不同的音色。乐器的声音通常都是有一个基础频率加上多种弦外之音（overtones）合成的。多数乐器都产生和声，但是打击乐器不是。

频谱图

以上是频谱图示例，信息包含时间、频率和振幅，振幅大小由颜色深度指示。这种图在深度学习处理声音数据的时候也要用到。

傅立叶变换

傅立叶变换FT可以将时域信号$x(t)$转变为频域信号$f(w)$，有如下几种：

连续时间傅立叶变换

具体原理推导省略，其逆变换为：

离散时间傅立叶变换

以上公式是连续时间信号的变换，离散信号的变换可以使用离散傅立叶变换DFT，公式如下：

为了在科学计算和数字信号处理等领域使用计算机进行傅里叶变换，必须将函数定义在离散点上而非连续域内，且须满足有限性或周期性条件。这种情况下有：

N个结果，表示N个频率（每个k对应一个频率）以及其对应的振幅。也就是说其计算复杂度为O(N^2)，每个结果都是复数，其模就是对应的振幅。

基本过程

音频检索的基本思想和生物信息检索的思路比较类似，都是在server端建立大量样本构成的数据库，client发送检索请求后，server端提取请求特征，然后在数据库中进行检索匹配，最后将结果返回给client。

在音频检索的场景下，这里面比较重要的部分是

• 适用于部分匹配的特征提取
• 样本存储（上千万的歌曲）
• 高效、健壮的检索

由于部分匹配要求存在，所以音频检索的特征提取算法不可能使用MD5、SHA等，并且要能处理不同格式的音乐（MP2、WMA等）。shazam选择从声音的频谱图中提取特征。

采样

和信号处理的大多数case一样，人声输入是连续的音频，比如一段mp3，是连续信号，需要对信号进行采样、数字化。采样要做的就是信号损失和存储压力之间的tradeoff，奈奎斯特定理指出，要以大于2倍于原始信号的采样频率，才能从数字信号中恢复出原始信。人类听觉上限大约是20kHZ，所以标准的数字音乐采样频率是44.1kHZ，是20kHZ的两倍多一点。

量化

采样是针对频率上的数字化，振幅的数字化则需要量化来完成。振幅的大小受到设备音量的影响。所以振幅的表示则有相对量表示，可以选定整个音乐中振幅的最值，并将其离散化，然后用这些离散值表示。标准的量化方法将振幅范围编码为16个bit，也就是65536个level，这时的信息损失已经很小了。

脉冲编码调制

经过采样、量化两个步骤之后，设备会对数据进行编码（称为PCM信号）并且送到耳机/扬声器进行播放，PCM的样例如下：

采样率为44.1kHZ的音乐，每秒钟有44100个这样的数据。

生成频谱图

本节讲的是如何由一段数字信号生成频谱图，需要用到离散傅立叶变换技术。将时序信号等时间间隔划分成多个bin，在每个bin内使用DFT得到其频率。

这里有个概念，每个bin在频率上的表示也是有固定间隔的，这个值叫做频率分辨率（frequency resolution），计算方法是：

frequency resolution = 采样率 / 窗口大小

这里窗口大小是每个bin内采样窗口（window）。比如在44.1kHZ的标准采样率情况下，4096个样本的窗口对应的频率分辨率是10.7HZ。所以一个窗口的时长大约是4096/44100=0.1s，也就是说每隔0.1s就能检测出一个变化。

为了处理一个1s长度的音频，就需要分别处理10个bin的数据。实际上也就是是用了窗口函数（处理第一个bin的时候其他的系数为0）。简单的窗口函数是矩形，也还有hamming窗口和blackbox窗口，图示如下：

不同的窗口效果不同，如下所示，左图是完美的图，右图是是用了不同的窗口函数的图像，可以看到，右图中存在被称为频谱泄漏的现象，即真是频率对应的数据蔓延到邻居点。

图中blackman窗口函数的效果要优于其他窗口函数，但是换一个大小不同的窗口也许就不一样了，他们的特性如下：

• 矩形窗口函数：可比振幅的正弦曲线效果较好，完全不同的振幅情况则比较差（音乐的振幅变动就比较大）
• blackman窗口函数：擅长处理频谱泄漏时出现的强频率掩盖弱频率的问题，同时也导致了噪声会掩盖更多的频率
• hamming窗口函数：上面两者的均衡

DFT的计算复杂度较高，在数量为1000的曲库上计算可能需要数天甚至上月才能完成。这里可以使用两个方面的优化：

1. 使用快速傅立叶变换FFT
2. 降采样：因为一首歌中大多数重要的部分都在0-5kHZ区间上，所以我们只需要11kHZ的采样率即可（奈奎斯特）。为了保持相同的频率分辨率，窗口大小降为1024即可。可以将之前4个sample的数据求均值作为一个，采样频率降为原来的1/4

0.1s的bin size, bin的频率分辨率10.7HZ，512个可能的频率（5kHZ/10.7HZ），频率范围0-5kHZ

这里我们就得到了频谱图，考虑到对噪声的鲁棒性问题，可以将振幅最大的音符留下，但是这样会存在如下问题：

• 许多歌曲中都会包含一些人耳不容易听见的声音（<500HZ），发行前都会特意加强这些音符。只保留振幅最大的可能导致保留的都是这些人耳不容易听见的声音
• 频谱泄露问题导致不存在的频率出现，要确保不会选中不存在的

解决上述问题的方法如下

1. 对每一个FFT结果（N个），把512个当成6个bands（6是超参数），bands由振幅区间划分，把这些结果放到这些bin中
2. 每个band只保留最大值
3. 计算6个band中最大值的均值（由于开头、结尾可能振幅较小，均值较小，但是我们并不想要这部分频率，所以可以考虑计算整首歌振幅最大的6个的均值）
4. 保留大于均值的band值作为结果（可以乘一个参数）

以下是示例：

特征存储与匹配

如上图所示，特征数据是<time, frequency>对，根据时长进行滑动窗口逐一匹配的复杂度过高。shazam中使用多个点同时匹配的方法，引入target zone的概念。

阐述方便，将目标区域的大小固定为5，将二维数据线性化，需要严格的先后顺序保持唯一性，比如time相同时，frequency小的在前面。所以m个<time, frequency>对的数据，可以生成m-4个目标区域。

下一步是为每个目标区域创建一个地址，当然这是在server端做的。我们还需要一个anchor锚点，anchor的选取不限制，只要是可重复的即可（比如当前目标区域之前的一个点或者前三个啥的）。把每个目标位置当做一个key<anchor频率, 首位频率, 首位和anchor的时间差>，每个key映射到一个地址，地址的形式为<anchor在歌曲中的绝对位置/时间, 歌曲ID>。

在检索阶段，对输入的音频，算法生成一个个<<anchor频率, 首位频率, 首位和anchor的时间差>, 锚点在音频中的绝对位置>，并上传到server端。server进行检索，可能会返回大量结果，这里由于没有逐一比较target zone的每个数据点，所以即使命中了也可能不一样，但是这样节省了时间，也能过滤掉大部分negative样本。细致的比较下面继续。

对于上一步得到的结果，我们需要进一步比较，策略如下

• 去除没有target zone完全匹配的结果
• 卡一下阈值

最后还需要考虑时间先后的问题，必要性见上图，这时需要

• 计算候选歌曲中的音符及其在歌曲中的绝对位置
• 计算输入音频中的音符及其在输入中的绝对位置
• 匹配的音符应该满足：音符在歌曲中的绝对位置=音符在输入中的绝对位置+匹配开始的位置。对于每首歌，我们需要找到匹配音节最多的开始位置
• 返回音符匹配最多的候选

引用

[1]. How does Shazam work