@[toc]
https://jackwish.net/2019/neural-network-quantization-introduction-chn.html
https://zhuanlan.zhihu.com/p/149659607

0. 前言

近年来，基于神经网络的深度学习在图像处理、自然语言处理、语音识别等领域取得了显著效果。一般情况下，一个神经网络模型越大（一般指参数量越大），模型的拟合能力更强，准确度越高。这将进一步导致运行模型时需要的内存（包内存容量和内存带宽）、磁盘存储消耗增大，推理时延和功耗也会变大，从而限制模型的工业化落地。
为了解决这个问题，可以从两方面来下手：

• 从原理上设计更高效地网络结构，即参数量更少的模型，并保持精度下降可以接受。
• 不改变原有模型结构，而是对已有的模型进行参数压缩。

1. 量化压缩方法简介

量化压缩就是上一章节中的第二种解决方案，即对已有的模型进行参数压缩。所谓量化，就是用精度更低的类型来存储权重参数。例如，通常情况下模型默认以float32类型变量来存储权重，低精度就是以float16，int8甚至更低精度的类型来存储。最极端的情况下，可以采用一个bit来存储，也即二值神经网络。工业界中常采用的是int8类型。
在训练过程中，一般还是全精度（float32）类型，到了推理阶段，则有两种方案：一种是所有算子都支持量化后的类型的数据运算（以int8为例），因此模型的全过程中数据流都是int8；另一种是数据流仍是float32，每个算子前后分别有quantize层和dequantize层用以将float32转换为int8或者反过来。

2. 量化压缩原理

2.1. 定点数与浮点数

在计算机的存储中，int属于定点数，float和double属于浮点数。定点数与浮点数的介绍见https://www.jianshu.com/p/d39fb5792ac8
浮点数的存储与转换方式详解见https://www.cnblogs.com/lan0725/p/11515584.html
int8的值域为[-128,127],取值个数为$2^{8};$float32的值域为$[(2^{-23}-2)\times 2^{127},(2-2^{-23})\times 2^{127}]$,取值个数约为$2^{32}$。int8在整个值域上的精度分布是均匀的，而float32不是均匀的,0附近的精度越高，越往值域区间两边精度越低。这是因为，在给定指数时，float32在此指数对应的区间内数值个数是一定的，如下图所示（图片来源https://jackwish.net/2019/neural-network-quantization-introduction-chn.html）

2.2. 将浮点数量化为定点数

量化压缩的过程本质上是一个一个区间放缩到另一个区间的过程，这里仅讨论线性放缩:

round表示取整
首先确定放缩因子：

而

所以：

也即：

在工程中，int8可能会取[0,255] (无符号整数)

有时float类型的极大值和极小值会太极端，从而使得放缩因子太大，导致最后量化后的结果太集中于某一个小的子区间，浪费了其他部分的值域空间。这时，可以读float类型的极大值极小值进行clip。例如，认为设为-1.0和1.0.

这里留一个小彩蛋，为什么（2-3)里面不用$x-x^{min}$来与缩放因子相乘，而是采用$x-x^{max}$呢？虽然从数学上是等价的，但是工程实现上的效果会有点不一样，读者可以自己思考一下

@[toc]

1 张量（Tensor）基本概念回顾

张量（Tensor）其实就是多维数组，类似于NumPy里面的np.array。
这里的维度，更准确的讲法应该叫阶（rank），这是为了跟向量（vector）的维度区分开的。vector其实就是rank为1的张量，我们说一个vector是n维的其实是说它有n个分量（标量）。而如果张量的维度（阶）是n维的，并不是说它有n个标量分量，而是说在表示这个张量时需要用n个坐标轴。每个轴上都可以有多个分量。为了表示每个轴上的分量个数，引入形状（shape）的概念。
例如，一个三阶的张量，可以理解为是一个立方体。假设它的shape是$[3,2,5]$,那么下图就是一个具体的例子（下面两张图的来源均为https://www.tensorflow.org/guide/tensor）：

而一个四阶张量的例子则用下图表示：

TensorFlow/PyTorch中使用比较多的tensor的阶为4，shape为$[Batch, Height, Weight, Features]$.

n阶张量的排列规律如下图所示（图片来源https://syborg.dev/posts/understanding-tensors-in-pytorch）：

可以将规律总结为：从shape列表的最右边往左遍历，最开始三个阶按照“下-右-里”的顺序排列，然后打包成一个group，再将整个group按照“下-右-里”的顺序排列，满三次后再打包成一个group，如此往复循环。。

2 tensor在计算机内存中的存储方式

前面提到的rank和shape，都是数学上的定义，实际在内存中是一维存储的。
排列规律为：

1. 假设rank为n，即shape列表的size为n.
2. 初始位置为原点
3. 将shape[n-1]方向上的元素按照这个方向上的坐标递增的顺序进行线性排列。
4. shape[n-1]方向上的元素排完后再将shape[n-2]上的坐标递增，继续排shape[n-1]方向上的元素，直到shape[n-2]方向上的坐标到了最大值，并且排完了这个坐标上的shape[n-1]方向的元素，此时shape[n-2]方向上坐标归零。
5. 将shape[n-3]上的坐标递增，继续3,4，直到shape[n-3]方向上的坐标和shape[n-2]方向上的坐标到了最大值，并且排完了这个坐标上的shape[n-1]方向的元素，此时shape[n-3]和shape[n-2]方向上坐标归零
6. 对shape[n-i] (i=4,5,…,n)上的坐标递增,并重复前面的过程。

一般情况下，假设高阶tensor的各个下标存在数组coordinates中, 各个阶的维数存在数组shape中，则转换为一维向量的下标index过程如下：

1
2
3
4
5
6
7
8

int index=0;
for(int i=0;i<coordinates.size(); i++){
    int tmp=coordinates[shape.size()-1-i];
    for(int j=0;j<i;j++){
        tmp=tmp*shape[shape.size()-1-j];
    }
    index=index+tmp;
}

当然，还有一种基于动态规划的更高效的计算方法：

1
2
3
4

int index = coordinates[0];
for(int i=1; i<coordinates.size(); i++){
index = index * shape[i] + coordinates[i];
}

@[toc]

1. 梯度和Jacobian矩阵

设$f(x)\in R^1$是关于向量$x\in R^n$的函数，则它关于$x$的导数定义为：

函数$f(x)\in R^1$关于向量$x\in R^n$的导数是一个列向量，称之为$f(x)$关于$x$的梯度。

如果$f(x)\in R^M$是关于向量$x\in R^n$的函数向量，则$f(x)$关于$x$的导数定义为：

称上述矩阵为Jacobian矩阵。
一些常用推论：

1. 假设$v,x\in R^n$: $$\frac{d}{dx}(v^Tx)=\frac{d}{dx}(x^Tv)=v\tag{1-4}$$
2. 假设$y\in R^1$,$z\in R^m$,$x\in R^n$,$z=g(x)$,y=f(z)： $$\frac{dy}{dx}=\left(\frac{dz}{dx}\right)^T\frac{dy}{dz}\tag{1-5}$$ 可以从向量矩阵的维度适配上去理解和记忆，因为$\frac{dy}{dx}\in R^n$,$\frac{dy}{dz}\in R^m$,$\frac{dz}{dx}\in R^{m\times n}$，所以必须有上述的公式才能适配。
3. 假设$y\in R^k$,$z\in R^m$,$x\in R^1$,$z=g(x)$,y=f(z)： $$\frac{dy}{dx}=\frac{dy}{dz}\frac{dz}{dx}\tag{1-6}$$
4. 假设$y\in R^k$,$z\in R^m$,$x\in R^n$,$z=g(x)$,y=f(z)： $$\frac{dy}{dx}=\frac{dy}{dz}\frac{dz}{dx}\tag{1-7}$$

   2. pytorch求变量导数的过程

   在pytorch和TensorFlow中，是不支持张量对张量的求导。这不是因为数学上没法求，而是因为工程实现上比较麻烦。因为向量对向量求导是个矩阵，二阶张量（矩阵）对二阶张量（矩阵）求导得到一个四阶张量，这样很容易会产生阶数爆炸。所以pytorch和TensorFlow（猜测其他深度学习框架也是这样）对外的接口干脆不支持张量对张量求导。如果遇到张量对张量求导的情况，例如向量对向量求导的情况，需要对因变量乘以一个维度一样的向量，转换为标量对向量的求导，这样可以大大减少计算量（具体见后文）。并且，因为pytorch和TensorFlow是为了机器学习/深度学习模型设计的，机器学习/深度模型的求导基本上都是损失函数(标量)对参数的求导，很少直接用到向量对向量求导，因此上述过程是有实际意义和需求的。

假设有一个三维tensor $x=[x_1,x_2,x_3]^T=[1,2,3]^T$,另一个三维tensor y:

那么在计算y相对于x的导数时，

在pytorch中实际计算时，不能直接用y对x求导，需要先用一个向量$w$左乘y，再转置。例如，$w^T=[3,2,1]$。因此，pytorch算的其实是：

$w$可以理解为是对$[\frac{\partial y_1}{\partial x},\frac{\partial y_2}{\partial x},\frac{\partial y_3}{\partial x}]^T$的权重参数。因此我们得到的是y的各个分量的导数的加权求和。

代码如下：

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

import torch
x1=torch.tensor(1, requires_grad=True, dtype = torch.float)
x2=torch.tensor(2, requires_grad=True, dtype = torch.float)
x3=torch.tensor(3, requires_grad=True, dtype = torch.float)
y=torch.randn(3)
y[0]=x1**3+2*x2**2+3*x3
y[1]=3*x1+2*x2**2+x3**3
y[2]=2*x1+x2**3+3*x3**2
v=torch.tensor([3,2,1],dtype=torch.float)
y.backward(v)
print(x1.grad)
print(x2.grad)
print(x3.grad)

利用链式求导的原理来理解，可以理解为$w$是（远方）某个标量对$y$的导数。pytorch之所以要这么设计，是因为在机器学习/深度学习模型中，求导的最终目的一般是为了让损失函数最小。损失函数一般都是一个标量，因此无论链式求导的过程多么复杂，中间过程也许有很多向量对向量求导的子过程，但是最开始一定会有一个标量（损失函数）对向量的求导过程，这个导数就是前面的$w$。

下面看一个带两个隐藏层的神经网络解决线性回归问题的例子，来进一步说明这点。
为了简单起见，考虑batch_size=1的情况。设输入数据为$x=[x_1,x_2]^T$,输入层到第一个隐藏层的权重矩阵为

第一个隐藏层的值为$z=[z_1,z_2]^T$,
第一个隐藏层到第二个隐藏层的权重矩阵为

第二个隐藏层的值为$s=[s_1,s_2]^T$,
输出层的值为$y$,隐藏层到输出层的权重参数为$v=[v_1,v_2]^T$。则有：

损失函数为$L=(y-\hat y)^2/2$
则损失函数关于权重参数$w_1$的导数为：

可以验证$(2-9)$和前面$(2-8)$中直接求得的导数值是一样的。
这里发现了一个小彩蛋：
假设在pytorch的底层实现中，如果从左往右计算，则需要进行进行大量的矩阵乘法。如果有n个$2\times 2$的方阵相乘，那么需要进行$4\times (n-1)$次内积。如果从又往左计算，只需要进行$2\times n$次内积。

[TOC]

1. Introduction

Before feeding our text data into a model, we need firstly transformed it to a numerical format that the model can understand. That is called text representation, and it is a necessary data pre-processing procedure for almost every kind of nlp task.

From the view of language granularity, text representation can be divided into word representation, sentence representation and document representation. Word representation is the fundamental of the other two and we’ll introduce it first. Then we will introduce sentence representation in details. Documentation representation can be simiplified to sentence representation in many situations, so we won’t spend too much time on it.

2. Word Representation

Word representation includes two categories of models: discrete word representation and distributed word representation. The major difference between discrete and distributed representation is whether it considers the relationships among words. Discrete representation assumes that words are independent, and it fills in the word vector mainly by extracting features from the properties of the word itself, such as occurrence and frequency. Therefore, the word vector of discrete representation can’t capture the semantic and syntactic information of the word, and it is usually high dimensional and sparse. On the contrary, distributed representation analyzes relationships among the word and other words and learns a dense and low-dimensional feature vector to represent the word vector. We will firstly introduce one-hot encoding, a classical and simple method of discrete representation. Then we’ll discuss word embedding, the most popular frame of distributed representation techniques in recent years.

2.1. One-hot Encoding

Given a fixed set of vocabulary $V=\{w_1,w_2,\cdots,w_{|V|}\}$, one-hot encoding encodes a word $w_i$ with a $|V|$-dimensional vector $X$, of which the i-th dimension where $w_i$ occurs is 1 and the other dimensions are all zeros.
For example, if we have a corpus as follows(This example will also be used in the later chapters, and we mark it as Example 1):

1
2
3
4

"I like mathematics."
"I like science."
"You like computer science."
"I like computer and science."

Then the vocabulary is:

1

{I, like, mathematics, science, You, computer, and}

For word “mathematics”, its one-hot vector is:

1

(0,0,1,0,0,0,0)

One-hot encoding only captures the information of the word’s occurrence and position in the vocabulary, neglecting the frequency information and co-occurrence of different words.
In practice, one-hot encoding can be transformed into storage of the indexes of words in the vocabulary, so the the characteristics of high dimensionality and sparsity won’t cause computation problems. However, it is seldomly used directly for word representation because of its lack of semantic and syntactic information. Instead, it is used to tokenizing the word in other representation methods.

2.2. Word Embedding

Generally, the phrase “word embedding” has two meanings: 1. The technique to find a function that maps a word to a multi-dimensional and dense vector. 2. The word vector obtained in 1.
As peviously mentioned, one-hot encoding has serval problems: high dimension, sparsity and lack of semantics. The first two problems can be easily solved in word embedding by choosing appropriate dimension number of the result vector. What about the third problem? We haven’t discuss the exact definition of semantics. We won’t discuss too much of it since it is inherited from linguistic, instead we only give some intuitions. Semantics represents the meaning of a word and words with similar meanings should have similar semantics.
With the hypothesis of distributional semantics——linguistic items with similar distributions have similar meanings, the problem of learning word semantics can be transformed into modeling the relations among the target word and its context, and that is what statistical language model does. In fact, the earliest word embedding is the by-product of neural networks language model. In the following sections, we will introduce some classical word embedding methods.

2.2.1. Word2Vec

2.2.1.1. Continuous Bag of Words Model(CBOW)

2.2.1.2. Skip-Gram Model

[TODO]

3. Sentence Representation

3.1. Bag of Words

The model of Bag-of-Words represents a sentence as a bag of words, and each word of the sentence is represented by one-hot encoding. Then the sentence vector is the sum of all of the word vector:

Where $X(w_i)$ is the one-hot encoding vector of $w_i$ in sentence $s$, and $X(s)$ is the vector of $s$.
In example 1, for a sentence “I like computer and science”, its sentence vector is:

1

(1,1,0,1,0,1,1)

3.1.1. Bag of Words weighted by term count

In one-hot encoding, every word has the same value—1, in the non-zero component of its feature vector, which ignores importance of different words. Thus, it can’t distinguish these two sentences: “I like computer and science” and “I like computer and computer science”.
To evalute the importance of a word, a straightforward way is to multiply the one-hot vector by a weight—the count of the word in the sentence. Then, the vector of “I like computer and computer science” can be represented as:

1

(1,1,0,1,0,2,1)

3.1.2. Word of Bags weighted by TF-IDF

A better choice is to use TF-IDF(Term Frequency-Inverse Document Frequency. In this section, document is identity with sentence) as the weight, where $TF(t)=\frac{counts\ of\ word\ t\ in\ the\ doc}{num\ of\ words\ in\ the\ doc}$.

The original definition of IDF is:

where $n$ is the number of documents while $df(t)$ is number of documents containing the target word $t$. To avoid division by zero, we can use the smoothing technique: $IDF(t)=ln\frac{1+n}{1+df(t)}$, and it looks like that there is a document containing all the words. What’s more, to avoid $IDF=0$, we can add one to IDF:

Then, TF-IDF$=TF(t)\cdot IDF(t)$
Finally,

TF-IDF representation can be easily implemented by calling the following sk-learn functions:

1
2
3

vectorizer=CountVectorizer()
transformer=TfidfTransformer()
tfidf=transformer.fit_transform(vectorizer.fit_transform(corpus))

or

1
2

transformer=TfidfVectorizer()
tfidf2=transformer.fit_transform(corpus)

3.1.3. Bag of Words with Word Embeddings

In this method, each word is represented by word embeddings instead of one-hot encoding. The sentence is then represented by the average or weighted average of all the word vectors, like what we discussed above.

@[toc]

1. 前馈神经网络的缺点

对于输入向量中个分量的位置信息不感知，也即无法利用序列型输入特征向量中的位置信息（将个分量调换顺序最后训练出的模型是等价的），但是在实际的任务中，各分量是有先后关系的。例如，我们在理解一段文本时，孤立地理解每个字或者词是不够的，还要将它们作为一个整体的序列来理解。

2. 循环神经网络RNN

2.1. RNN的基本结构与数学定义

RNN的输入数据，一般有三个维度：batch大小，时间长度，特征维数。TensorFlow中的RNN层API的输入数据shape为[batch, timesteps, feature]。因为本节的图片来自Andrew NG的Coursera公开课中的例子，因此这里的RNN输入数据形状将以Andrew NG的习惯为例，这不影响原理的讲解。输入层的维数是$(n_x,m,T_x)$,其中$n_x$是每个训练样本的维数；$m$是一个batch的大小；$T_x$是输入序列的长度。

输出层的维数是$(n_y,m,T_y)$,其中$n_y$是输出预测向量的维数；$m$是一个batch的大小；$T_y$是输出序列的长度。

我们先研究输入向量和输出向量相等，即$n_x=n_y$的情况，结构图如下所示（图片来源https://www.coursera.org/learn/nlp-sequence-models/notebook/X20PE/building-a-recurrent-neural-network-step-by-step）。

上下标说明举例：$a_5^{(2)[3]<4>}$表示第2个训练样本，第3层，第4个时刻，激活函数输出向量的第5维。
每个RNN-Cell的内部结构见下图

注意，输出$\hat y$是状态向量$a$经过线性变换再经过softmax变换得到的。

需要注意的是，在不同的RNN-Cell中，上述公式里面的参数$W,b$都是共享的。

2.2. 输入输出长度的讨论

2.2.1. $n_x=n_y=n$

第一种情况是输入输出长度相等的情况，如下图所示（图片来源https://www.jianshu.com/p/c5723c3bb921）

常用于序列标注模型，例如命名实体识别模型中。

2.2.2. $n_x=n,n_y=1$

第二种情况是输入长度为N，输出长度为1（图片来源https://www.jianshu.com/p/c5723c3bb921）

模型只在最后一个时刻输出，常用于文本分类模型
利用RNN网络预测sin函数的代码例子：https://github.com/lankuohsing/TensorFlow-Examples/blob/master/RNN/RNN_sin.py

2.2.3. $n_x=1,n_y=n$

第三种情况是输入长度为1，输出长度为N。uti实现时，可以将输入作为最开始时刻的输入，也可以作为所有时刻的输入（图片来源https://www.jianshu.com/p/c5723c3bb921）

常用于文字生成模型中。

2.2.4. $n_x=n,n_y=m$，Encoder-Decoder模型

第四种情况是输入长度为N,输出长度为M的情况，也即Encoder-Decoder模型（图片来源https://www.jianshu.com/p/c5723c3bb921）

常用于语音识别、机器翻译等场景。在后面的章节中我们会详细介绍Encoder-Decoder模型

3. RNN的复杂变种

3.1. GRU(Gated Recurrent Unit)

GRU的提出是为了解决RNN难以学习到输入序列中的长距离信息的问题。
GRU引入一个新的变量——记忆单元，简称$C$。$C^{\langle t\rangle}$其实就是$a^{\langle t\rangle}$
$C$的表达式不是一步到位的，首先定义$C$的候选值$\tilde C$:

更新门：

在实际训练好的网络中$\Gamma$要么很接近1要么很接近0，对应着输入序列里面有些元素起作用有些元素不起作用。

也即输入序列的有些元素，记忆单元不需要更新，有些元素需要更新。

The cat, which already ate …, was full

cat后面的词直到was之前，都不需要更新$C$,直接等于cat对应的$C$
可以解决梯度消失的问题.输出层的梯度可以传播到cat处

注：$C$和$\Gamma$都可以是想聊，它们在相乘时采用的是element-wise的乘法。当为向量时，与cat的单复数无关的词对应的$\Gamma$可能有些维度为零，有些维度不为零。为零的维度，是用来保留cat的单复数信息的；不为零的维度可能是保留其他语义信息的，比如是不是food呀之类的
目前讨论的是简化版的GRU，结构图如下

完整的GRU：

$\Gamma_r$表示了$\tilde C^{\langle t\rangle}$和$C^{\langle t-1\rangle}$之间的相关程度

3.2. LSTM(Long Short-Term Memory)

没有了$\Gamma_r$，将$1-\Gamma_u$用$\Gamma_f$代替

(注意公式里面的$\Gamma_u$等价于图片中的$\Gamma_i$)

3.2.1. peephole连接

3.2.2 projection

对隐藏层状态a进行一次线性变换，降低其维数

4. Encoder-Decoder模型

由前面的章节我们知道，Encoder-Decoder模型就是输入输出长度为一般情况的RNN模型，示意图如下：

其中Encoder负责将输入进行编码，得到语义编码向量C；Decoder负责将语义编码向量C进行解码，得到输出。以机器翻译为例，英文作为输入，输出为中文。可以用如下的数学模型来表示：

从Encoder得到C的方式有多种，可以将Encoder最后一个时刻的隐藏状态作为C，也可以将所有的隐藏状态进行某种变换得到C。
语义编码C在Decoder中的作用当时有多种，常见的有如下两种
（1） C作为Decoder的初始状态$h_0$。

（2） C作为Decoder的每一步输入。

4.1. 几种典型的encoder-decoder

4.1.1. 第一种:语义编码C作为Decoder的初始输入

本小节的encode-decoder模型可以看成是seq2seq的开山之作，来源于google的论文https://arxiv.org/abs/1409.3215 Sequence to Sequence Learning with Neural Networks。该论文的模型是为了翻译问题而提出的，其中的encoder和decoder都采用LSTM，decoder中采用了beam search来提升效果。此外，该论文还采用了一个tric——将输入源句子倒序输入。这是因为，无论RNN还是LSTM，其实都是有偏的，即顺序越靠后的单词最终占据的信息量越大。如果源句子是正序的话，则采用的是最后一个词对应的state来作为decoder的输入来预测第一个词。这样是是不符合直觉的，因为没有对齐。将源句子倒序后，某种意义上实现了一定的对齐。

Encoder：

Decoder:

4.1.2. 第一种:语义编码C作为Decoder的每一步输入

https://arxiv.org/pdf/1406.1078 Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation

Encoder：

Decoder:

4.2. Encoder-Decoder的缺点

1. 对于输入序列的每个分量的重要程度没有区分，这和人的思考过程是不相符的，例如人在翻译的时候，对于某个一词多义的词，可能会结合上下文中某些关键词进行辅助判断。
2. 如果在Decoder阶段，仅仅将C作为初始状态，随着时间往后推进，C的作用会越来越微弱。

事实上，Attention机制的提出，主要就是为了解决上述问题。

5. Attention机制详解

前面讲到，在一般形式的encoder-decoder中，输入信息先经过encoder编码保存在C中，C再被decoder使用。这种“直接粗暴”的方式，可能会导致输入信息没有被合理的利用，尤其是当输入信息过长的时候。为了解决这个问题，Attention机制被提出，解决的思路是：在decoder阶段，每个时间点输入的C是不同的(示意图如下图所示)，需要根据当前时刻要输出的y去合理地选择输入x中的上下文信息。

具体来讲，就是对encoder的隐藏状态进行加权求和，以便得到不同的C，以中文翻译英文为例，示意图如下：

记$a_{ij}$为encoder中第$j$个隐藏状态$h_j$到decoder中第$i$个隐藏状态$h_i’$对应的$c_i$的权重，可以通过训练确定的，具体计算方法见后文。attention机制的核心思想可以概括为”对输入信息加权求和得到编码信息c”，也即如下公式：

5.1. attention机制中权重系数的计算过程

attention机制中权重系数有多种计算过程，对应于不同种类的attention机制。但是大部分的attention机制，都能表示为下文提到的三个抽象阶段。这里先引入几个概念。
我们将模型输入内容记为source，输出内容记为target。
source可以表示为一个一个的，target则表示为一个一个的query。在机器翻译中，key和value合并为一个，就是输入句子中每个单词对应的隐藏层状态。
通过计算Query和各个Key的相似性或者相关性（需要进行softmax归一化），得到每个Key对应Value的权重系数，然后对Value进行加权求和，即得到了最终的Attention数值。

具体来说可以分为三个阶段，如下图所示：

其中第一阶段计算相似性时有多种方法，例如向量点积、余弦相似度，甚至可以用一个小的神经网络来通过学习的方式计算。
第二阶段softmax归一化的公式如下：

5.2. 几种典型的attention机制

5.2.1. 第一种:Bahdanau Attention

https://arxiv.org/abs/1409.0473 Neural Machine Translation by Jointly Learning to Align and Translate，这篇论文可以看做是attention机制的开山论文。该论文也是为了解决翻译问题而提出的模型，encoder采用了双向的RNN结构，正向RNN和反向RNN的每个时刻的隐藏state拼接成一个两倍长的新的state。如果要用一个简洁的公式来概括attention，那就是mlp + softmax+加权求和。之前的模型都是用一个固定长度的语义向量C来将encoder和decode连接起来，而这篇论文里是采用一个attention模型来连接。

Encoder：

语义向量：

其中$e_{ij}$是Encoder中$j$时刻隐藏层状态$h_j$对Decoder中$i$时刻的处处状态$s_i$的影响程度；$a(s_{i-1},h_j)$称为一个对齐模型，本论文中采用的是一个单隐藏层的多层感知机$a(s_{i-1},h_j)=v_a^T tanh(W_a s_{i-1}+U_ah_i)$，注意在实际推理的时候，$U_ah_i$是可以在推理之前预先算好的以减少推理计算量；$\alpha_{ti}$是对$e_{ti}$进行softmax归一化成的概率，也即前文提到的$a_{ij}$或者叫attention权重；$c_t$是$t$时刻的语义向量。可见上述计算得到权重系数$\alpha_{ij}$的的过程主要分为两步：MLP+SOFTMAX
Decoder:

5.2.2. 第二种： Luong Attention

源自此论文https://arxiv.org/abs/1508.04025 Effective Approaches to Attention-based Neural Machine Translation。该论文提出了两种不同的attention：global attention和local attention。前者attention将作用在源句子的每个词，计算量较大；后者是出于减小计算量的考虑，只关注一个区间内的词（并且是在一个句子内部）。

5.2.2.1. Global attention

Encoder与上一小节中的不同之处在于，采用最顶层的LSTM的隐藏状态用于计算后续的语义向量C。
语义向量与上一小节的不同之处在于，在计算权重系数$\alpha_{ij}$的时候利用的是decoder中第$i$个隐藏状态（上一小节是第$i-1$个）和encoder中第$j$个隐藏状态来计算：

其中$a(s_{i},h_j)$的选择有多种：

Decoder：

5.2.2.2. Local Attention

Global attention的缺点在于，预测某个target word时，需要计算该target对应的hidden state与encoder汇总所有hidden state之间的关系。当输入句子比较长时，这将非常耗时。Local attention就散为了解决这个问题，它只关注源句子中一个窗口内的词对应的hidden state。它的思想来源于soft-attention和hard-attention。

具体来说，对于要预测的某个target word， 首先计算出一个对齐位置$p_j$,然后一个以$p_i$为中心的窗口$[p_i-D,p_i+D]$会被用来计算$c_i$。窗口大小由经验给定。计算$c_i$的方法与前面类似。
因此，重点在于如何计算$p_i$。论文给出了两种方法：

1. 单调对齐方式（Monotonic alignment）：假设源句子和目标句子是单调对齐的。取$p_i=i$。
2. 预测对齐方式（Predictive alignment）：采用如下公式计算$p_i$: $$p_i=S\cdot sigmoid(v_p^Ttanh(W_ps_i))\tag{5-9}$$ 其中S是源句子的长度。同时，为了增大$p_i$附近的hidden state权重，权重系数将再乘上一个高斯分布： $$a_{ij}=\alpha_{ij}\cdot exp\left(-\frac{(j-p_i)^2}{2\delta^2}\right)\tag{5-10}$$ 其中$\delta=D/2$。$p_i$是个实数，而j是个整数

   5.2.3. Self-Attention

   参考https://jalammar.github.io/illustrated-transformer/
   Self-Attention最著名的应用是在论文https://arxiv.org/abs/1706.03762 Attention Is All You Need中，作为transformer结构的一个重要组成部分。
   前面提到的几种attention，都是应用于基于RNN或者LSTM的encoder-decoder架构，通过计算decoder中隐藏状态和encoder中各个隐藏状态之间的关系来得到对应的权重。在《Attention Is All You Need》中，完全抛弃RNN/LSTM/CNN等结构，仅采用attention机制来进行机器翻译任务。并且在本论文中的attention机制采用的是self-attention，在encode源句子中一个词时，会计算这个词与源句子中其他词的相关性，减少了外部信息的依赖（这里我的理解是，与前面的几种attention机制不同，self-attention不需要decoder中的信息，也即encode一个句子时只用到了自身的信息，这就是self的含义）。
   下面个详细讲解self-attention原理。第一阶段是计算三个vector，见下图：图片来源https://jalammar.github.io/illustrated-transformer/

为了简单起见，假设输入句子只有两个词，是”Thinking Machines”。如上图所示：首先得到这两个词的Embedding向量$x_1,x_2$（跟一般的nlp任务中的Embedding向量是一个概念），然后对于每个词，都计算出三个向量：Query Vector，Key Vector和Value Vector。计算过程为分别乘以三个矩阵：$W^Q,W^K,W^V$。
第二阶段是计算attention分数，假设现在要计算的是”Thinking”的attention值，那么需要计算”Thinking”与该句子中所有词的分数。需要计算$score(q_1,k_1),score(q_1,k_2)$。常见是计算公式是内积。过程如下图所示：

第三阶段是对分数进行归一化。首先除以$\sqrt d_k$（Key Vector的维度），这是为了避免梯度爆炸；然后进行softmax归一化，这样是为了使得分数都在$[0,1]$之间。

这个分数代表了encode “Thinking”需要放置多少注意力在各个单词上,不妨记为$s_{1i}$。
第四阶段就是利用上述得到分数对所有的Value Vector加权求和得到”Thinking”的representation： $z_1=\sum_{i=1}^{L_x}s_{1i}*v_i$

值得注意的是，上述过程是可以并行化计算的，这是self-attention相对于RNN,LSTM等序列模型的优势（在处理长序列问题上）。
最后，我们给出self-attention的紧凑表达式：

这样就一步到位得到了输入句子中所有词的represent vector。

5.2.4. Multi-Head Attention

所谓multi-head attention，其实就是将输入的Embedding切分成多份，对每一份独立地进行self-attention，然后将结果concat在一起。这是为了增加模型对于其他位置的词的注意力能力。因为如果只是一个self-attention，很容易使得某个词的注意力大部分集中在它自身。

参考：https://blog.csdn.net/Tonywu2018/article/details/83897806

0. 背景故事

t检验又叫学生t检验（Student‘s t test），它是由20世纪爱尔兰的一家啤酒厂-健力士酒厂的一名员工（戈斯特）采用笔名“Student”发表的学术文章而得名。

1. 从一个例子引入t检验的思路

健力士公司是酿啤酒的，啤酒的原材料是麦子，因此公司种了很多麦田。假设有两片麦田，一块采用A工艺（旧）种植，另一块采用B工艺（新）种植。A工艺的麦田平均每株麦子可以结100粒穗子。公司想知道B工艺是否相比A工艺提高了产量。为了节约成本、小小损耗，抠门的资本家老板从B工艺的麦田里随机摘了5株大麦，每株麦子的平均穗子数量为120粒，看起来似乎产量提高了，因为每株麦子的麦穗粒数均值增加了20%。如何确定这样的结论是否可信呢？

原假设：B工艺没有提高产量，即AB工艺下的每株麦子麦穗数量服从同一个分布
备选假设：B工艺提高了产量

由中心极限定理，A攻一下每株麦穗的粒数服从均值为100，方差未知的正态分布：

B工艺的单株麦穗粒数也可以认为服从正态分布。如果原假设正确的话，B和A服从同样的正态分布。那么这时候我们可以去评估出现5株均值为120的麦穗的概率是否很极端，来判断原假设是否合理。可以对B的每株麦穗数的分布归一化为标准正态分布，再去查表评估其概率值。也即要计算$\frac{\bar x-\mu_0}{\delta_0}$，其中$\bar x$是B工艺的麦穗粒数均值，$\mu_0$为A工艺的麦穗粒数均值，$\delta_0$为A工艺的麦穗粒数均值。由于B工艺是抽取出一定的样本数来计算均值$\bar x$的，因此不能代表总体均值。当样本数很大时，根据大数定理可以直接认为B工艺提高了产量；当样本数很小时，可能是随机误差。因此，不妨对前面的式子再除以一个n相关的数。为此，戈斯特构造了一个新的统计量：

该统计量越大，寿命AB工艺导致的差别越大，越有可能说明B工艺提高了产量。

3. t分布

对于t统计量：$t=\frac{\bar x-\mu_0}{\delta_0/\sqrt n}$,其对应的概率密度函数也即t分布为：

其中$\nu=n-1$称为自由度，$\Gamma(x)=\int_0^{+\infty}t^{x-1}e^{-t}dt(x>0)$是伽马函数。
t分布的函数图像与正态分布有点像，给定t值和自由度，可以通过查表的方式去找到对应的P值。t分布表如下：

以本文中的例子为例，假设置信水平wie$\alpha=0.05$，查表得T值为2.132（单侧检验）。假设A工艺的标准差为$5\sqrt5$，可计算得出t=4，大于T。因此可以拒绝原假设。

参考资料：https://www.cnblogs.com/zzdbullet/p/10087196.html

1. 方差（variance）的定义

方差是用来度量随机变量和其数学期望（均值）之间的偏离程度的一个统计量。

统计学中（所有样本）的总体方差公式：

其中$\sigma^2$是总体方差，$X$是随机变量，$\mu$是总体均值（有时也用$\bar X$表示），$N$是总体样本数。这里提到的样本，是基于样本数量$N$（几乎）无限的假设。对应的各个统计量，也是所有的样本所服从的分布的真实参数，是客观正真实的。

2. 样本方差

现实情况中，我们往往得不到所有的无限样本，而只能抽样出一定数量的有限样本。通过有限的样本来计算的方差，称为样本方差，公式如下：

注意上式的系数和总体方差公式里面的系数不一样，分母是$n-1$。为什么不用$n$作为分母呢？这是因为如果沿用总体方差的公式得到的样本方差，是对方差的一个有偏估计。用$n$作为分母的样本方差公式，才是对方差的无偏估计。

3. 总体方差公式的有偏性证明

换言之，除非正好有$\bar X=\mu$，否则一定会有

上式的右边是对方差的正确估计，左边是有偏估计。
产生这一偏差的本质是因为均值用的是样本均值$\bar X$。这将导致采样出来的样本之间不是完全相互独立的，自由度从$n$降为了$n-1$。（注意，一个好的采样有两点要求：随机采样，并且样本之间是相互独立的）这是因为，给定$\bar X$和任意$n-1$个样本，就能确定剩下的一个样本，也即只有$n-1$个样本是完全相互独立的，自由度为$n-1$。

4. 样本方差公式分母为n-1的推导

在正式推导之前，先给几个公式作为铺垫：

1. 方差计算公式： $$D(X)=E(X^2)-[E(X)]^2\tag{4-1}$$
2. 均值的均值： $$\begin{align*} E(\bar X)&=E\left(\frac{1}{n}\sum_{i=1}^{n}X_i\right)\\ &=\frac{1}{n}E(\sum_{i=1}^{n}X_i)\\ &=E(X_i)\\ &=\bar X\tag{4-4} \end{align*}$$
3. 均值的方差 $$\begin{align*} D(\bar X)&=D\left(\frac{1}{n}\sum_{i=1}^nX_i\right)\\ &=\frac{1}{n^2}D(\sum_{i=1}^{n}X_i)\\ &=\frac{1}{n}D(X_i)\\ \tag{4-5} \end{align*}$$

对于没有修正的方差计算公式，计算其期望：

结合{4-4}和{4-5}，可将{4-6}化简为

要使样本方差的期望等于总体方差，就需要进行修正，也即给样本方差乘上$\frac{n}{n-1}$
因此得到修正后的样本方差公式:

推导完毕！

参考：https://cosx.org/2010/11/hypotheses-testing/

0. 背景

在实际生产生活中，我们经常需要对一些逻辑推理进行真假判断，例如

如果你打了某种疫苗P，就不会得某种流行病Q
如果一个疑似病人隔离了14天还没确诊，那他就没有被感染新冠肺炎

在统计学里面，不会像上面那样说，而是会说：

如果你打了某种疫苗 ，就有95%的把握不会得流行病Q
如果一个疑似病人隔离了14天还没确诊，那他就有95%的把握没有被感染新冠肺炎

其中的把握水平，在统计推断中用“置信水平”来代替。置信水平是可以人为选取的。

1. 从一个硬币的例子来引入假设检验

如何从统计推断的角度来判断一个逻辑推理是否正确呢？通常，我们会给定一个置信水平，然后判断该逻辑推理是否在这个置信水平下成立。这里重新举一个硬币的例子，来引入置信水平的概念。
假设有如下命题：

if P then Q
P: 在 100 次投掷中，得到 90 次正面，10 次反面。
Q: 硬币不是均匀的。

我们想知道，如果P成立，判断Q成立的把握有多大。很多时候（但不是所有时候），在统计推断里面，要证明的结论都是直觉上可能性比较大的，直接证明可能不太方便，可以反其道行之，证明Q的反面是否成立，来推断出Q是否成立。为此，列出如下原假设和备择假设：

H0: 硬币是均匀的（P）
Ha: 硬币是不均匀的（not P）

如果原假设为真，即硬币是均匀的，就不可能会发生这样极端的事情比如：在 100 次投掷中，得到 90 次正面，10 次反面。如果真的观察到了这么极端的事情，就有把握认为硬币不是均匀的，则拒绝原假设，选择备选假设。如果观察到的是60次正面，40个反面，则没有特别大的把握拒绝原假设，这枚硬币是否有偏，需要更多的证据来证明（这通常意味着做更多的实验，比如再投1000次）。

即使观测到100次投掷中90次正面10次反面，也不能说硬币一定是不均匀的（也即不能百分之百的把握拒绝原假设）。如果原假设为真，但是拒绝了原假设，这种情况称为第一类错误。发生第一类错误的概率，称为显著性水平，用$\alpha$表示。$1-\alpha$称为置信度或者置信水平，它表示我们根据抽样样本对总体参数的估计的可靠性。$\alpha$一般是人为定的，如0.05，0.01.给定置信水平后，就可以去利用一些统计学的知识去检验原假设是否需要拒绝。
如果原假设是错误的，但是没有拒绝原假设，则称为第二类错误。如果要求犯第一类错误的概率尽可能小，就会导致第二类错误的概率增大；反之，如果要求第二类错误的Giallo极可能小，就会导致第一类错误的概率增大。在实际中需要权衡。权衡的方式就是调节$\alpha$。在实际中，我们通常认为犯第一类错误的后果比犯第二类错误的后果更为严重。例如，关于打疫苗会后会不会得病的命题，我们通常会将原假设写成：会得病，然后去搜集数据试图拒绝原假设。此时犯第一类错误的后果是比较严重的（实际会得病却认为不会得病，会放松警惕造成大流行），而犯第二类错误的后果不是很严重（实际不糊得病，却没有拒绝原假设，只是会将打疫苗的部分人隔离起来造成一定的不便）

再强调一下，一般都是先提出需要建议的假设，再搜集数据，这是统计推断的原则之一。因为如果现有了数据再提出假设，容易有主观干扰。
到这里，我们还是没有解答如何去检验原假设是否需要被拒绝。别急，接着往下看。

2. P值

如何去定义一个事件是否“极端”呢？首先我们引入“更极端”的概念。更极端，意味着概率更小。例如，91次正面9次反面，比90次正面10次反面，更为极端。因此，很自然地，我们只需要描述出原假设为真，第一类错误恰好为$\alpha$时的事件，然后判断出当前样本集合里面的事件是否比它更极端，就能判断是否要在当前显著性水平下拒绝原假设了。当然，直接这样比较麻烦，可以转换一下思路：计算出发生比当前事件（90次正面，10次反面）更极端的事件的概率P，判断P与$\alpha$的大小，如果$P<\alpha$，则说明如果原假设为真时，发生当前事件的概率很极端（比我们给定的显著性水平$\alpha$还低），因此说明原假设不合理，于是可以拒绝原假设了。此时发生第一类错误的概率小于$\alpha$。这里的概率P，称为P值。
在硬币投掷实验中，正面出现的次数服$X$服从一个二项分布：$X\sim B(n,p)$，其中$n=100,p-0.5$。根据中心极限定理，二项分布的极限分布是正态分布，因此可以由均值为$np=50$，方差为$np(1-p)=25$的正态分布来近似。我们用这个近似的正态分布的两端去考察所谓“更极端”的事件。取$\alpha=0.05$，由正态分布的性质不难得到，$P$值等于$X<10$或$x>90$的概率值，等于$2\times P(X<10)=1.2442e-15$。这个小于我们给定的$\alpha$，因此该事件很极端，原假设不合理，拒绝原假设。

nlp入门基础之语言模型

@[toc]
https://zhuanlan.zhihu.com/p/28080127
https://zhuanlan.zhihu.com/p/52061158
https://blog.csdn.net/weixin_40056628/article/details/89364456

1. 简介

语言模型（language model）是用来计算一个句子的概率的模型，或者预测下一个词出现的概率。通俗地讲，就是用来评估一个句子有多大的可能性是有意义的（是人话而不是一堆杂乱无章的词语组合）。
一段自然语言文本可以看做是一个离散时间序列$s=\omega_1,\omega_2,\cdots,\omega_T$，而一个语言模型的作用是构建这个时间序列的概率分布$P(s)$。概率计算公式可以表示为：

对于$P(\omega_t|\omega_1,\omega_2,\cdots,\omega_{t-1})$，可以在大量娱乐库中采用频率统计的方式来近似估计：

直接计算上式是不现实的。假设词汇表大小为$V$，由上式可以看到，产生第$i$个词$\omega_i$的概率是由已经产生的$i-1$个词$\omega_1,\omega_2,\cdots,\omega_{i-1}$决定的，那么我们必须考虑所有$V^{i-1}$种不同历史情况下，产生第$i$个词的概率。这样模型中就会有$V^i$个自由参数（每个条件概率看成一个参数）。这在实际中几乎是无法从训练数据中估计出这些参数的。并且，很多词的组合可能在语料库中根本不存在，这样会导致最后估计出的概率为零（数据稀疏问题）。
因此需要引入语言模型来降低参数个数。语言模型有基于统计模型的，比如n元语法（n-gram），也有基于神经网络的。

2. n元语法

n元语法(n-grams)是基于n-1阶马尔科夫链的概率语言模型，也即在n-gram模型中，一个词的出现概率只与前面n-1个词有关：

每个条件概率需要实现在大量语料库中根据频率近似求得。

• n=1: unigram，每个词独立于历史
• n=2: bigram，每个词只与它前面的一个词有关。实际中常用
• n=3: trigram，每个词只与它前面的两个词有关

n元语法模型可能的缺陷：

1. 参数空间过大
2. 数据稀疏

2.1. 一元模型（unigram）

一元模型假设每句子中的每个每个词都是独立的，也即：

需要实现在语料库中统计每个字的频率。

2.2. 二元模型（bigram）

注意需要有句子开头和结尾标识符。实践中，需要先统计语料库中词语的两两组合情况的各自频率，再统计每个词的频率，以便得到条件概率。

3. n-gram模型实践

3.1. 文本分类

假设类别有两类：$Y_1,Y_2$,原始文本为$X$。由贝叶斯公司可知：

$P(Y_i)$就是类别$Y_i$的文本比例；$P(X|Y_i)$就是在类别$Y_i$下句子$X$的概率，可以由n-gram算得

在上述贝叶斯假设条件下，可以简化过程，直接将训练样本的n-gram特征作为输入去训练一个分类器，得到分类模型。

4. 神经网络语言模型

4.1. 基于前馈神经网络的语言模型

Bengio在2003的论文A Neural Probabilistic Language Model。

先给每个词在连续空间中赋予一个向量(词向量)，再通过神经网络去学习这种分布式表征。利用神经网络去建模当前词出现的概率与其前 n-1 个词之间的约束关系。很显然这种方式相比 n-gram 具有更好的泛化能力，只要词表征足够好。从而很大程度地降低了数据稀疏带来的问题。但是这个结构的明显缺点是仅包含了有限的前文信息。
该模型利用前n-1个词去预测下一个词，输入层是n-1个词的one-hot向量（每个向量是$1\times V$），再乘以一个$1\times D$的权重矩阵，得到$1\times D$的中间向量，将n-1个中间向量拼接成隐藏层（长度为$D(n-1)$）。隐藏层的激活函数为tanh，输出层为一个全连接层再接一个softmax函数生成概率分布。该模型的副产物就是词向量（输入层到隐藏层的权重矩阵）
这篇论文是词向量的鼻祖，后面的cbow和skip-gram都是由这里启发而来。

4.2. 基于循环神经网络的语言模型

为了解决定长信息（只能利用前面n-1个词的信息）的问题，Mikolov在2010的论文 Recurrent neural network based language model。

网络的输入层是”s我想你”，输出层可以看作是分别计算条件概率 P(w|s)、P(w|s我)、P(w|s我想)、P(w|s我想你) 在整个词表V中的值。而我们的目标就是使期望词对应的条件概率尽可能大。

相比单纯的前馈神经网络，隐状态的传递性使得RNN语言模型原则上可以捕捉前向序列的所有信息(虽然可能比较弱)。通过在整个训练集上优化交叉熵来训练模型，使得网络能够尽可能建模出自然语言序列与后续词之间的内在联系。

为了解决依赖的信息过长的问题，后续又有LSTM、attention等改进方法

SVD分解推导证明

@[toc]

0. 线性代数与矩阵基础知识回顾

本文讨论的范围实数空间，不涉及复数空间，因此各种术语和定理都以实空间下的名称为准，当然也可以推广到复数空间，只需进行一些名词的变换（对称矩阵-Hermitian举矩阵，正交矩阵-酉矩阵）。

0.1. 正交向量组

对于向量$x_1,x_2,\cdots,x_k\in R^n$，若$x_i^Tx_j=0,\forall (i,j)\in \{(i,j)\lvert 1\leq i<j\leq k\}$，则称$x_1,x_2,\cdots,x_k$是一组正交向量组，简称正交组。如果正交组里面的向量还是归一化的，即$x_i^Tx_i=1,i=1,2,\cdots,k$，则称该正交组为标准正交组。

0.2. 正交矩阵

一个实的正方矩阵$Q\in R^{n\times n}$称为正交矩阵，若：

由上述定义可以推出如下几个等价的叙述：

1. $Q$是正交矩阵
2. $Q^T$是正交矩阵
3. $Q$是非奇异的，并且$Q^T=Q^{-1}$
4. $QQ^T=Q^TQ=I$
5. $Q=[q_1,q_2,\cdots,q_n]$的列组成标准正交组
6. $Q$的行组成标准正交组
7. $\forall x\in R^n, y=Qx$的Euclidean长度与$x$的Euclidean长度相等，也即有$y^Ty=x^Tx$。

   0.3. 正定矩阵

   一个对称矩阵$A$称为

• 正定矩阵($A>0$)：若二次型$x^TAx>0,\forall x\neq 0$;
• 半正定矩阵($A\geq 0$)：若二次型$x^TAx\geq 0,\forall x\neq 0$;
• 负定矩阵：如果$-A$是正定的
• 半负定矩阵：如果$-A$是半正定的

正定矩阵的等价条件：

• 存在可逆矩阵$C$使$C^TC$等于该矩阵
• 正定矩阵$<=>$所有特征值取正实数，半正定矩阵$<=>$所有特征值取非负实数

0.4. 特征值

• 对于n阶对称矩阵$A$的特征值都是实数。
• 对于n阶对称矩阵$A$，总存在正交阵$Q$，使得$Q^{-1}AQ$是对角阵，且对角线元素就是$A$的特征值按从大到小排列。即$Q^{-1}AQ=diag(\lambda_1,\lambda_2,\cdots,\lambda_n),\lambda_1>\lambda_2>\cdots>\lambda_n$。

1. 奇异值分解（Singular Value Decomposition）

1.1. svd的数学描述

svd告诉我们，对任意$m\times n$的矩阵$A$，都可以表示为下面这种形式：

其中$U$是$m \times m$的正交阵，$V$是$n\times n$的正交阵，$\Sigma$是$m\times n$的对角阵，

$\Sigma_1=diag(\sigma_1,\sigma_2,\cdots,\sigma_r),r=rank(A)$，其对角元素按照从大到小排列

1.2. svd的证明

在开始证明前，先给出几个引理：

• 引理1：$A^TA$可对角化，且具有实的非负特征值（这是因为$A^TA$是半正定矩阵）
• 引理2：$rank(A)=rank(A^TA)=rank(AA^T)$
• 引理3：$A=0\ \Leftrightarrow\ A^TA=0$

下面开始证明：
设$rank(A)=r$，根据引理1和引理2，存在$n\times n$的正交矩阵$V$，使得

其中$\lambda_1>\lambda_2>\cdots>\lambda_r>0=\lambda_{r+1}=\cdots=\lambda_n$为$A^TA$的n个非负特征根。
令$\Sigma_1=diag(\sigma_1,\sigma_2,\cdots,\sigma_r)=diag(\sqrt\sigma_1,\sqrt\sigma_2,\cdots,\sqrt\sigma_r)$，$V_1=[v_1,v_2,\cdots,v_r]，V_2=[v_{r+1},v_{r+2},\cdots,v_{n}]$，并且有$V=[V_1,V_2]$。
从而有$A^TAV_1=V_1\Sigma_1^2$，进一步得到：

令$U_1=AV_1\Sigma_1^{-1}$，则有$U_1^TU_1=I$。此时，我们可以选择$m-r$组标准正交向量与$U_1$的列向量组成一组标准正交基，也即$U=[U_1,U_2]$是一个m阶正交阵，且$U_1^TU_2=0$。
另一方面，容易得到：

根据引理3可得$AV_2=0$

综上可得：

也即$A=U\Sigma V^T$，到此奇异值分解定理得证。