SIMD

单指令多数据

向量体系结构 多媒体SIMD指令集扩展 与GPU

VMIPS

如果循环的迭代没有相关性，那么这种相关称为循环间相关。这些代码可以向量化。

向量处理器中，每个向量指令只会因为等待每个向量的第一个元素而等待一次。

向量执行时间

取决于三个要素：

1.操作数向量的长度

2.操作之间的结构冒险

3.数据相关

护航指令组：

一组可以一直执行的向量指令。

钟鸣：

度量估计护航指令组的时间

执行由m个护航指令组构成的向量序列需要m次钟鸣，向量长度为n的时候，大约为mxn个时钟周期。

向量长度寄存器

使用条带挖掘技术，把向量分割成不大于MVL大小的小向量来进行处理

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

//MVL 最大向量长度


low = 0；

VL = (n%MVL) 

for (int j=0;j< (n/MVL);j++){

	for(int i=low;i< low + VL;i++){
    	//运算
    }
    
    low = low + VL
    
    VL = MVL // 复位为最大长度向量

}

上面这段代码表示除了第一段部分长度为VL，向量其余长度都为MVL

向量遮罩寄存器

代码向量化程度低的原因：

1.存在IF条件语句

2.稀疏矩阵

于是向量遮罩寄存器可以把条件执行IF转换为直行代码序列，方便代码进行向量化。

如果元素对应的向量遮罩寄存器对应数值为1，说明该数值不受该向量影响。

1
2
3
4
5
6

LV V1,RX
LV V2,RY
L.D F0,#0
SNEVS.D V1,F0  #若V1(i)!=F0 ,则VM（i）设置为1
SUBVV.D V1,V1,V2
SV V1,RX

内存组

为向量载入/存储单元提供带宽

时钟周期提取或者存储一个字的初始化速率，约等于寄存器向存储器载入或者提取新字的速度，于是存储器必须能够生成或者接收那么多数据，将访问对象分散在多个独立的存储器中。

处理非连续存储器

步幅：所要收集的寄存器元素之间的距离

1
2
3
4
5
6
7
8
9
10
11

for(int i=0;i<100;i++){

	for(int j=0;j<100;j++){
    
		for(int k=0;k<100;k++){

			D[k][i] = A[i][j]+B[i][k]
		}    
    
    }
}

考虑双字，那么这里D的步幅就是100*8;
A的步幅为8

当 组数/（步幅与组数的最小公倍数）< 组繁忙时间

例如 八个存储器组，组繁忙时间为6个时钟周期，总存储器延迟为12个时钟周期，以步幅1完成一个64元素的向量载入操作，需要时间？如果步幅32呢？

第一种情况：步幅为1

12+64 = 76 周期

第二种情况： 步幅为32

8 / gcd(32,8) = 1 < 6

12 + 1 + 63 * 6 = 391

第一次访问之后，对存储器的每次访问会和上一次访问发生冲突。

集中——分散：在向量体系结构中处理稀疏矩阵

GPU中所有载入操作都是集中，所有存储都是分散。

采用索引向量的集中——分散操作。VMIPS指令：LVI,SVI

图形处理器 GPU

CUDA（COMPUTE UNIFIED DEVICE ARCHITECTURE）

CUDA为系统处理器生成C/C++,为GPU生成C和C++方言。

编译器和硬件把许多CUDA线程聚合在一起，利用CPU各种并行类型：多线程，SIMD和指令级并行。这些线程被分块，执行的时候以32个线程为1组，称为线程块。执行整个线程的硬件为多线程SIMD处理器。

CUDA编程模型是一个异构模型，需要CPU与GPU协同工作。

host 指CPU以及内存

device 指GPU及其内存

host与device之间进行通信，可以进行数据拷贝。

cuda程序执行流程：

1.分配host内存，进行数据初始化

2.分配device内存，然后host把数据拷贝到device上

3.调用cuda的核函数在device上完成指定运算

4.把device运算结果拷贝到host上

5.释放device和host上分配内存。

kernel 是device上线程并行执行的函数，核函数用global 符号声明，调用的时候要用<<grid,block>>来指定kernel要执行的线程数量。

cuda中每一个线程都要执行核函数，并且每个线程会分配一个唯一的线程号thread ID，ID可以通过核函数的内置变量threadIdx来获得。

GPU异构模型，需要用函数限定词来区分host与device上的代码

1
2
3
4
5
6
7
8
9
10

__global__  

返回类型一定要是void，不支持可变参数，kernel是异步的，host不会等你kernel执行完就执行下一步

__device__

在device上执行，仅从device中调用，不可以和__global__同时用


__host__ 在host上执行，尽可以从host上调用

GPU上有很多并行化的轻量级线程，kernel在device上执行的时候启动很多线程。

一个kernel启动的所有线程成为一个网格(grid)同一个网格的线程共享相同的全局内存空间。

grid是线程结构的第一层次，而一个grid又可以分为很多block（线程块）

一个线程块包含很多线程。

1
2
3
4
5
6

dim3 grid（3，2）；
dim3 block (5,3);
kernel_fun<<<grid,block>>>(params..)

grid为GRID中block的个数，
block为block中thread的个数

用nvcc编译，文件名为xxx.cu

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <stdio.h>
#include <cuda_runtime.h>


__global__ void vectorADD(int *a,int *b,int *c){

	
	int index = threadIdx.x; //当前线程序号
	if(index < blockDim.x){
		c[index] = a[index] + b[index];
	}

}


int main(){


	int N = 10;

	int *h_a = (int*) malloc (sizeof(int)*N);
	int *h_b = (int*) malloc (sizeof(int)*N);
	int *h_c = (int*) malloc (sizeof(int)*N);

	/*initialize*/

	for(int i=0;i<10;i++){

		h_a[i] = i;
		h_b[i] = i;
	}

	int size = sizeof(int)*N;

	int *d_a;
	int *d_b;
	int *d_c;

	//第一个参数是cpu内存中指针变量的地址，会改变实参的数据
	cudaMalloc((void**)&d_a,size);
	cudaMalloc((void**)&d_b,size);
	cudaMalloc((void**)&d_c,size);

	//把本地数组拷贝到GPU内存
	cudaMemcpy(d_a,h_a,size,cudaMemcpyHostToDevice);
	cudaMemcpy(d_b,h_b,size,cudaMemcpyHostToDevice);

	// 定义一个GPU运算块，由10个运算线程组成
	dim3 DimBlock = N;
	
	//一个块，十个线程
	vectorADD<<<1,DimBlock>>>(d_a,d_b,d_c);
	
	//把运算结果复制回host
	cudaMemcpy(h_c,d_c,size,cudaMemcpyHostToHost);
	
	
	cudaFree(d_a);
	cudaFree(d_b);
	cudaFree(d_c);

	for(int j=0;j<N;j++)
		printf("%d\n",h_c[j]);
	printf("\n");
	
}

但是上面的例子中，没有使用托管内存，其可以共同管理host与device中的内存，自动在host与device中进行数据传输。

所有线程可以访问全局内存，每个线程块有local memory,而且还有包含共享内存，可以被线程块中所有线程共享，生命周期与线程块一致。

grid之间通过global memory交换数据

block之间不能相互通信，只能通过global memory共享数据

即线程之间可以通过同步通信。

矩阵乘法实例：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <iostream>
using namespace std;

struct Matrix{
	
	int width;
	int height;
	float *elements;

};

__device__ float getElement(Matrix* A,int row,int col){

	return A->elements[row*A->width+col];
}

__device__ void setElement(Matrix* A,int row,int col,float value){

	A->elements[row*A->width+col] = value;
}

//每个线程计算一个元素
__global__ void matMul(Matrix *A,Matrix *B,Matrix *C){

	float Cvalue = 0;
	//global index of a thread
	int row = threadIdx.y + blockIdx.y * blockDim.y;
	int col = threadIdx.x + blockIdx.x * blockDim.x;
	
	for(int i=0;i<A->width;i++){
		Cvalue += getElement(A,row,i)*getElement(B,i,col);
	}

	setElement(C,row,col,Cvalue);

}


int main(){

	int width = 1<<10;
	int height = 1<<10;
	Matrix *A,*B,*C;
	cudaMallocManaged((void**)&A,sizeof(Matrix));
	cudaMallocManaged((void**)&B,sizeof(Matrix));
	cudaMallocManaged((void**)&C,sizeof(Matrix));
	int nbytes = width*height*sizeof(float);	
	cudaMallocManaged((void**)&A->elements,nbytes);
	cudaMallocManaged((void**)&B->elements,nbytes);
	cudaMallocManaged((void**)&C->elements,nbytes);

	A->height = height;
	A->width = width;	
	B->height = height;
	B->width = width;
	C->height = height;
	C->width = width;

	for(int i=0;i<width*height;i++){
		A->elements[i]  = 1.0;
		B->elements[i]  = 2.0;
	
	}

	dim3 blockSize(32,32);
	dim3 gridSize((width + blockSize.x -1) / blockSize.x,
		(height+blockSize.y -1)/blockSize.y);
	//kernel
	matMul <<< gridSize,blockSize>>> (A,B,C);

	//确保host 与device 是异步的
	cudaDeviceSynchronize();
	float maxError = 0.0;
	for(int i=0;i<width*height;i++){
		maxError = fmax(maxError,fabs(C->elements[i]-2*width));
	}
	cout<<maxError<<endl;	
	return 0;
	
}

指令级并行

指令之间可以重叠执行

基本概念：

提高ILP常见基本方法： 循环级并行

数据相关：

相关会带来冒险，解决方法两种：

1.指令调度，保持相关，但避免发生冒险

2.通过代码变换消除相关

数据流经寄存器的时候，检测容易。

但是若数据流动经过存储器的时候，检测比较复杂。

因为实际逻辑地址与物理地址转换之间的关系，导致相同形式的地址有效地址未必相同，而形式不同的地址有效地址可能相同。

复习：

名称相关

名称为指令所访问的寄存器或者存储器单元的名称

如果两条指令使用相同的名称，但是它们之间并没有数据流动，则称这两条指令存在名称相关。

相关有两种：

1.反相关：

指令j写的名称 = 指令i读的名称

2.输出相关：

指令j写的名称 = 指令i写的名称

如果指令中名称改变了，不影响另一条指令的执行。

换名技术：

1.改变指令中操作数的名称来消除名相关。

2.对于寄存器操作数进行换名：寄存器换名

保证程序的正确执行：数据流与异常行为

BEQZ RNAME,ADDRESS 若R ==0 ，跳转到ADDRESS的偏移地址处

基本流水线调度与循环展开

1
2
3
4

for(i=999;i>=0;i=i-1){
	x[i]  = x[i] + s;
}

转换为MIPS
假设R1的初值是数组元素的最高地址，8（R2）指向最后一个元素。F2包含标量值s

1
2
3
4
5
6
7
8
9

LOOP: LW F1,0(R1)
	stall
	ADD F4,F1,F2
	stall
    stall
    SW  F4 ,0(R1)
	ADDI R1,R1 #-8
	BNEQZ R1,R2,LOOP

指令调度之后的MIPS

1
2
3
4
5
6
7

Loop： LW F1,0(R1)
		Addi R1,R1,#-8
       	ADD F4,F1,F2
        STALL
        STALL
        SW F4 ,0(R1)
        BNEQZ R1,R2,loop

循环展开技术

把循环体代码复制多次并且按顺序排列，然后相应调整循环的结束条件。

给编译器进行指令调度带来更大空间

总结：

指令级并行做法：

1.循环展开

2.寄存器重命名以消除冒险

3.指令调度

使用高级分支预测降低分支成本

1
2
3
4
5
6

if （aa= =2）
	 aa= 0；
if （bb= =2）
	 bb= 0；
if （aa！= bb）{  }；

MIPS

1
2
3
4
5
6
7
8

ADDI R3,R1,#-2
BNEQZ R3,L1
ADD R1,R0,R0
L1: ADDI R3,R2,#-2
	BNEQZ R3,L2
    ADD R2,R0,R0
L2: SUB R3,R1,R2
	BNEQZ R3,L3

相关预测

利用其他分支行为进行预测的分支预测器

竞赛预测器：

动态调度克服数据冒险

静态调度： 仅仅依靠编译器对代码进行静态调度，减少相关和冒险。

只是在编译而不是程序执行的阶段进行代码调度和优化，本质上是把相关指令拉开距离来减少可能产生的停顿。

动态调度：

在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。

动态调度思想：

把Decode阶段拆分为两个阶段

指令调度使得异常处理变得复杂：

不精确异常：

当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行指令i时的现场不同。

精确异常:

当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行指令i时的现场相同。

Tomasulo 算法

核心思想：记录和检测指令相关，操作数一旦就绪立即执行，把发生RAW冒险的可能性减少到最小。

通过寄存器换名来消除WAR和WAW冒险

反相关会导致WAR冲突

输出相关会导致WAW冲突

其实前两个F6和最后一个F6逻辑上是没有关联的
第一个F8和最后两个F8也是没有关联的

保留站

保留站保存一条已经流出并等待到本功能部件执行的指令。
包括：操作码，操作数和用于检测和解决冲突的信息。

公共数据总线CDB

所有功能部件的计算结果都送到CDB上，由它把这些结果直接送到各个需要该结果的地方。

在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB

缓冲器

存放读写寄存器的数据与地址

寄存器换名是通过保留站和流出逻辑来共同完成的。

当指令流出的时候，操作数如果还没有计算出来，把指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。

指令流出保留站之后，操作数寄存器号或者换为数据本身，或者换成保留站的标识，不再与寄存器有关系。

Tomasulo算法特点

冒险检测与指令执行控制是分布的。

每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。

计算结果通过CDB直接从产生他的保留站传送到所有需要它的功能部件，不用经过寄存器。

Tomasulo算法

指令执行步骤：

发射： 从指令队列头部取指令

example：

当执行了第一条指令并且已经把结果写入的时候

算法两个优点：

冒险检测逻辑是分布的。

（通过保留站和CDB实现）

如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个结果一产生，就可以通过CDB同时播送给所有这些指令，使它们可以同时执行。

消除了WAW冒险和WAR冒险导致的停顿。

使用保留站进行寄存器换名，并且操作数一旦准备就绪就放到保留站。

以下是Tomasulate C++ 模拟

基于硬件推测：

1
2
3
4
5
6
7

对分支指令的结果进行猜测，并假设这个猜测
总是对的，然后按这个猜测结果继续取、流出和执
行后续的指令。只是执行指令的结果不是写回到寄
存器或存储器，而是放到一个称为ROB（ReOrder 
Buffer）的缓冲器中。等到相应的指令得到“确认”
（commit）（即确实是应该执行的）之后，才将结
果写入寄存器或存储器。

//看到PPT 101

data-plane role: forward datagrams from input links to output links

control plane: coordinate the local ,per-router forwarding actions so that datagrams are ultimately transferred end -to end

https://allenwu.itscoder.com/ji-suan-ji-wang-luo
知识点总结

Control Plane

SDN Approach

由远程服务器来决定以及分配转发表的值。

远程服务器与路由器通过交换含转发表以及其他路由信息来进行信息交换

traditional Approach

由路由算法来做决定以及分配转发表的值

网络层的三个主要功能

1.连接建立

2.转发

3.路由选择

路由器作用： 把数据报从入链路转到出链路

转发与路由选择

转发是把分组从一个输入链路接口转移到适当的输出链路接口的路由器基本动作。

路由选择是网络范围的过程，决定分组从源到目的地所采取的端到端路径。

分组交换机

定义： 一台通用分组交换设备，根据分组首部字段中的值，从输入链路接口到输出链路接口转移分组。

如果基于链路层字段做转发决定，为链路层交换机

如果基于网络层字段的值做转发决定，为路由器

虚电路和数据报网络

与运输层的UDP和TCP相似，网络层也能在两台主机之间提供无连接服务或者连接服务。无连接不需要建立握手，而连接在主机和主机之间需要进行握手

虚电路： 仅在网络层提供链接服务的计算机网络

数据报网络: 提供无连接服务的计算机网络

运输层面向连接服务是在网络边缘的端系统实现的，而网络层的连接服务除了在端系统，还会在网络核心的路由器中实现。

虚电路网络

虚电路的组成：

1.源和目的主机之间的路径（一系列链路和路由器）

2.VC号 沿着该路径的每段链路的一个号码

3.每台路由器中的转发表表项

虚电路建立的三个阶段：

虚电路建立：发送运输层与网络层联系，指定接收方地址，等待网络建立虚电路

网络层决定发送方与接收方之间的路径，即该虚电路的所有分组要通过的一系列链路与路由器。网络层也为沿着该路径的每条链路决定一个VC号。最后，网络层在沿着路径的每台路由器的转发表中增加一个表项。

数据传送：一旦创建了虚电路，分组就可以沿着虚电路流动

运输层的链接建立仅仅涉及两个端系统，但在网络层链接建立期间，端系统路径上的路由器也要参与虚电路的建立。

数据报网络

每当端系统要发送分组，就为该分组加上目的端系统的地址，然后把分组推进网络中。不维护任何虚电路的状态信息。

路由器每台都使用分组的目的地址来转发该分组，每台路由器有一个将目的地址映射到链路接口的转发表，当分组到达路由器的时候，路由器使用该分组的目的地址在转发表中查找合适的输出链路接口，然后路由器会把分组向该输出链路接口转发。

路由器通过用分组的目的地址的前缀与转发表中的表项进行匹配，如果匹配的话路由器则向与该匹配项想联系的链路转发分组。有相同前缀的，选择前缀最长对应的链路接口，并且使用最长前缀匹配规则。

数据报网络中路由器不维持连接状态信息，但是转发表维持。

路由器工作原理

路由器体系结构：

输入端口

交换结构

输出端口

路由选择处理器

• 路由器负责转发功能：把分组从入链路传送到出链路。

• 输入输出分组，交换结构实现的转发功能：路由器转发平面，用硬件来实现。

• 控制功能，即执行路由选择协议，路由器控制平面，由软件来实现

输入端口

输入端口的线路端接功能与链路层处理实现用于各个输入链路的物理层和链路层，路由器在输入端口用转发表来查找输出端口，使得到达的分组能够经过交换结构转发到输出端口。

转发表是由路由选择处理器设计和更新的。

交换结构

路由器的核心部位

正是通过这种交换结构，分组才能实际地从一个输入端口交换到一个输出端口中。

• 经内存交换

端口会先通过中断方式向路由选择处理器发出信号，分组会被复制到内存当中，路由选择处理器会从首部中提取目的地址，然后再转发表中找出适当的输出端口，并把分组复制到输出端口的缓存中。

如果内存带宽为每秒写进或者读内存Ｂ个分组，那么总的转发吞吐量必然小于Ｂ/２

• 经总线交换

不需要路由选择处理器的干预，输入端口经过一个共享总线把分组直接传送到输出端口，但一次只有一个分组能够跨越总线

• 经互联网络交换

某个时刻经过给定总线仅有一个分组能够发送。

主动队列管理

在缓存填满之前随机丢弃或者在首部加标记一个分组，以便向发送方提供一个拥塞信号。

RED：随机早期检测。

详情看课本

网际协议

网络层的三个主要组件：

１．ＩＰ协议 完成网络层的编址与转发

２．路由选择部分，决定了数据报从源到目的地所流经的路径

３．报告数据报中的差错和对某些网络层信息请求进行相应的设施（ICMP）控制报文协议

IPv4 数据报格式

链路层frame能够承载的最大数据量：最大传送单元MTU

如果MTU比IP数据包长度要小，如何把这个过大的IP分组压缩到链路层帧的有效载荷字段？

IP数据报分片，把数据报中的数据分片成两个或者更多个较小的ＩＰ数据报，用单独的链路层封装这些较小的ＩＰ数据报，然后向输出链路上发送这些帧，这些较小的数据报叫做片。

同时ＩＰｖ４设计者把标志，标识，片偏移字段放在了ＩＰ数据报首部中。

发送主机会为它发送的每个数据报的标识号加1，每个数据报具有初始数据报的源地址，目的地址和标识号。IP是一种不可靠服务，因此为了让目的主机绝对相信他已经收到了初始数据包的最后一个片，最后一个片的标志比特设为0.

一台主机通常只有一条链路连接到网络，当主机的ＩＰ想发送一个数据报的时候，他就在该链路上发送。主机与物理链路之间的边界叫做接口，路由器的任务是从链路上接收数据报并且从某些其他链路转发出去，因此路由器必须拥有两条或者多条链路与它链接。

每台主机和路由器都能发送和接收ＩＰ数据报，ＩＰ要求每台主机和路由器接口有自己的ＩＰ地址，因此一个ＩＰ地址技术上是和一个接口相关联的．

每个ＩＰ地址长度为３２bit，ｅｇ

193.32.216.9　可以表示为

11000001 00100000 11011000 00001001

用ＩＰ术语来说，互联若干个主机接口和路由器接口的网络形成一个子网。

这些主机接口与路由器接口形成一个子网。

eg 223.1.1.0/24　/24　称为子网掩码

指示了３２个ｂｉｔ最左侧的２４个ｂｉｔ定义子网地址　任何要连接到223.1.1.0 /24的主机都要求其地址具有223.1.1.xxx的形式

a.b.c.d/x 前x最高比特构成了IP地址的网络部分，称为网络前缀。

该子网内部设备的IP地址将共享前缀，这样可以减少路由器中转发表的长度

IP广播地址 255.255.255.255 主机发出一个目的地址为广播地址的数据报的时候，报文会交付给同一个网络中的所有主机。路由器会有选择的向临近子网转发该报文。

主机如何获得IP地址

1.获取一块地址

可以从ISP获取。

2.获取主机地址，动态主机配置协议

当有主机加入时候，DHCP服务器从当前可用地址池分配任意一个地址给它，每当一台主机离开的时候，地址会被收回到这个池中。除了主机IP地址的分配，还允许主机知道他的子网掩码，第一跳路由器地址与本地DNS服务器的地址。

DHCP 服务器发现

DHCP客户主机生成包含DHCP发现报文的IP数据报，其中使用广播目的地址255.255.255.255并且使用本主机的源地址0.0.0.0，DHCP客户将该IP数据报传递给链路层，链路层然后把该帧广播到所有与该子网连接的子网

DHCP 服务器提供

DHCP服务器收到一个DHCP发现报文的时候，用一个DHCP提供报文向客户作出相应。

仍然使用255.255.255.255 广播地址。报文提供了IP地址租用期，网络掩码，IP地址等信息

DHCP 请求

新到达的客户从一个或多个服务器中提供选择一个，并向选中的服务器提供一个DHCP请求报文响应。

DHCP ACK

用DHCP ACK 报文对DHCP请求报文进行响应。

3.网络地址的转换

NAT路由器通过NAT转换表来指导应该把某个分组转发给哪个内部主机,NAT转换表包含了端口号和IP地址。

ICMP

因特网控制报文协议

用于主机与路由器彼此沟通网络层的信息。典型用途是差错报告。

工作原理：

源主机向目的主机发送一系列普通的ＩＰ数据报，这些数据报每个携带了一个具有不可到达ＵＤＰ端口号的ＵＤＰ报文段，数据包的ＴＴＬ逐个增加。第Ｎ个数据报到达第Ｎ台路由器的时候，第ｎ台路由器观察到这个数据包的ＴＴＬ刚好过期。路由器会丢弃该数据报并发送一个ＩＣＭＰ告警报给源主机，这个告警报包含了路由器的名字以及ＩＰ地址。

IPV6

dual stack 使得该方法的IPV6还会有完整的IPV4实现。

三个主要概念：

环境状态，行动和奖励

强化学习的目标一般是变化的，不明确的，甚至可能不存在绝对正确的标签。

策略网络与估值网络

Policy-based 方法直接预测在某个环境下应该采取的Action，而Value based方法则预测某个环境状态下所有Action的期望价值（Q值）

策略网络预测出当前局势下应该采取的Action，给出的是执行某个Action的概率。

而估值网络预测的是当前局势下每个Action的期望价值。

Model-based 和 Model-free

基于模型的：根据环境状态和采取的行动预测接下来的环境状态，并利用这个信息训练强化学习模型。

不基于模型的：不需要对环境状态进行预测 也不考虑行动将如何影响环境。

Tensorflow 策略网络

1

r = r1+γr2+γ^2r3...

模型通过学习Action在Environment中获得的反馈，使用梯度更新模型参数。

代码参照：

见github

Tensorflow 估值网络

Q-learning 指从当前这一步到所有后续步骤，总共可以期望获取的最大价值。（Action->Q）

在每一个state下选择Q值最高的Action，Qlearning不依赖于环境模型，在有限马尔科夫决策过程中，证明最终可以找到最优策略。

Q-learning

Q-learning 指从当前这一步到所有后续步骤，总共可以期望获取的最大价值。（Action->Q）

在每一个state下选择Q值最高的Action，Qlearning不依赖于环境模型，在有限马尔科夫决策过程中，证明最终可以找到最优策略。

目标是求解函数$Q(s_{t},a_{t})$ ,以（状态，行为，奖励，下一个状态）构成的元组为样本来进行训练，其中$(s_{t},a_{t},r_{t+1},s_{t+1})$

学习目标是 $r_{t+1}+\gamma * max_{a}Q(s_{t+1},a)$ 是当前Action获得的reward加上下一步可以获得的最大期望价值。参数$\gamma$ 表示一个衰减系数，决定了未来奖励在学习中的重要性

整个Q-learning：

$$
Q_{new}(s_{t},a_{t}) =(1-a)Q_{old}(s_{t},a_{t})+a(r_{t+1}+\gamma max_{a}Q(s_{t+1},a))
$$

就是把旧的Q-learning向着学习目标按一个较小的学习速率α来学习

运输层协议

在不同主机的应用进程之间提供了逻辑通信，通过逻辑通信，运行不同进程的主机就会好像直接相连一样。

而网络层提供了主机之间的逻辑联系。

发送端： 运输层把应用程序进程接收到的报文转换成运输层分组，成为运输层报文段。实现方法为把应用报文划分为较小的块，并为每块加上一个运输层首部以生成运输层报文段。在发送端系统当中，运输层把这些报文段传递给网络层，网络层将其封装为网络层分组，向目的地发送。
网络路由器仅仅作用于数据报的网络层字段，即不检查封装在该数据报的运输层报文段的字段。

接收端：网络层提取运输层报文段，把报文段上交给运输层，运输层处理接收到的报文段，使得该报文段中的数据为接收应用进程使用。

网络层提供了主机之间的逻辑通信，而运输层为运行在不同主机上的进程提供了逻辑通信。

运输协议能够提供的服务常常受制于网络层协议的服务模型。如果网络层协议无法为主机之间发送的运输层报文段提供时延或者带宽保证的话，运输层也不能为进程之间的发送应用程序报文提供时延或者带宽保证

名词解释

UDP： 用户数据报协议：不可靠，无连接

TCP： 传输控制协议： 可靠，面向连接

运输层分组：报文段

IP：网络层的一个协议，每台主机一个IP地址，是不可靠服务

IP服务类型是尽力而为，不可靠的。

带宽： 数据通信的最大吞吐量

报文段： TCP和UDP的分组

数据报： 网络层分组

多路复用与多路分解

TCP 和 UDP 最基本责任： 把两个端系统间的IP的交付服务拓展为运行在端系统上的两个进程之间的交付服务。

这个过程也叫作多路复用和多路分解

运输层从下方的网络层接收报文段，运输层负责把这些报文段中的数据交付给主机上运行的应用程序进程。

一个进程有一个或多个套接字，socket作为进程与网络传递数据的一个门户。

那么怎么把运输层报文段定向到适当的套接字？接收端中，运输层检查这些字段，标识出接收套接字，进而把报文段定向到该套接字。

1
2
3

将运输层报文段中的数据交付到正确的套接字叫做多路分解

在源主机从不同的套接字中收集数据块，并为每个数据块封装上首部信息从而生成报文段，然后把报文段传递到网络层，叫做多路复用。

运输层报文段中的源与目的端口字段

1.套接字有唯一标识符
2.每个报文段有特殊字段来指示该报文段所要交付到的套接字。

在主机上的每个套接字能够分配一个端口号，当报文段到达主机时，运输层检查报文段中的目的端口号，并且将其定向到相应的套接字。然后报文段中的数据通过套接字进入其所连接的进程。

校检和校验的范围：伪头部，ＵＤＰ头部以及数据　伪头部用于检查ＵＤＰ用户数据报是否正确到达了指定主机(目的ＩＰ地址)的指定端口号

无连接的多路复用与分解

无连接是指发送方和接收方的运输层实体之间没有握手。
UDP是通过（目的IP,目的端口号）来标识的。如果源IP和源端口号相同，那么会两个报文段会通过相同的套接字被定向到相同的目的进程。

例子：

主机A一个进程有UDP端口19157，他要发送一个应用程序数据块给位于主机B的另一个进程，该进程具有UDP端口46428,主机A的运输层创建一个运输层报文段，其中包括应用程序数据，源端口号以及目的端口号。

运输层把报文段传递给网络层封装到一个IP数据报，然后交付给主机B。B能够运行多个进程，每个进程有自己的UDP套接字与相应的端口号。B会检查报文段的目的端口号，将每个报文段定向分解到相应的socket

而源端口号的用途就是可以作为B回发报文给A的时候，作为返回地址的一部分。

连接的多路复用与分解

TCP套接字由一个四元组（源IP地址，源端口号，目的IP地址，目的端口号）来标志。而UDP标识的二元组仅有目的IP地址和目的端口号。

当TCP报文段从网络到达一台主机的时候，主机使用全部四个数值来把报文段定向分解到相应的套接字。

具体来说，对UDP，如果两个报文段的有不同的源IP地址和源端口号，但具有相同的目的IP地址和目的端口号，那么两个报文段将通过相同的目的套接字被定向到相同的目的进程。

而TCP如果两个报文段的源IP地址和端口号不同，会被定向到两个不同的套接字。

例子：

1.TCP服务器有一个 socket 它在12000端口上等待来自TCP客户的连接请求。

2.客户创建一个套接字，发起连接请求。

1
2
3
4

clientSocket = socket(AF_INET,SOCK_STREAM)

clientSocket.connect((serverName,12000))

3.

1

connectionSoekct,addr = serverSoskct.accept()

操作系统接收到具有目的端口的连接请求报文段，该服务器进程在端口12000等待接受连接，并且创建一个新的套接字。

持续HTTP连接的使用：整条持续链接期间，客户与服务器之间经由同一个服务器套接字交换HTTP报文，然而如果使用非持续HTTP链接，每一对请求/响应都创建一个新的TCP链接然后随之关闭。

无连接运输 UDP

在发送报文段之前，发送方和接收方的运输层实体之间没有握手。直接与IP打交道，UDP从应用程序得到数据，附加上用于多路复用和分解的源端口和源地址以及其他两个小字段，然后把形成的报文段交给网络层。网络层把运输层报文段封装到一个IP数据报中，然后尽力把报文段交付给接收主机。主机接收到报文段之后UDP使用目的端口把报文段中的数据交付给正确的应用程序。

ＵＤＰ利用

面向连接的TCP

应用进程开始向另外一个进程发送数据之前，两个进程必须先相互握手。即必须相互发送某些预备报文段，以确定数据传输的参数。

• TCP链接提供的是全双工服务，如果两个进程之间存在TCP链接，那么应用层数据可以在进程B和进程A之间相互流动。

• TCP链接点对点，是单个发送方与单个接收方之间的连接。

• 面向连接：进行数据传输的时候首先要建立一条传输链接，相互发送某些预备的报文，链接双方要建立确保数据传输所需要的参数，传输完成之后要把链接释放掉。

TCP三次握手https://wenku.baidu.com/view/f0256510b207e87101f69e3143323968011cf40b.html?rec_flag=default

TCP会为每块客户数据配上一个TCP首部，从而形成多个TCP报文段，报文段被下传到网络层，网络层将其封装在网络层IP数据报中，然后再被发送到网络。

目的是防止报文段在传输链接建立过程中出现差错，也保证发送方和接收方发送和接收数据能力没有差错。

构造可靠数据传输协议

解决流水线的差错恢复两种基本方法：

1.回退N步(GBN)

发送方在发完一个数据帧之后，连续发送若干个数据帧，即使在连续发送的过程中收到了接收方发来的应答帧，也可以继续发送。发送方在发完一个数据帧的时候都要设置超时定时器，当发送了N个帧之后，如果发现该N帧的前一个帧在计时器超时后仍未返回确认信息，则判断该帧出错或者丢失，发送方不得不重新发送出错帧以及其后的N帧。

“累计确认”：允许接收端在连续收到好几个正确的确认帧之后，只对最后一个数据帧发送确认信息。

2.选择重传（SR）

通过让发送方仅重传那些它怀疑在接收方出错的分组而避免了不必要的重传。

就是接收方发现某帧出错之后，其后继续送来的正确的帧虽然不能立即递交给接收方的高层，但接收方可以收下来，存放在一个缓冲区中。

同时要求发送方重新传送出错的那一帧，一旦收到重新传来的那个帧，就可以要把缓存区的其他帧一起按正确的顺序传递给高层。

TCP报文结构

数据偏移：TCP的首部长度，以32bit为单位

窗口大小16bit，用来指示接收方滑动窗口的大小，用于实现TCP的流量控制。

校检和 实现对TCP数据的校检，所有16位字节计算反码和，然后取反

红字解答： 900 - 1000 序号对应的数据将会存储在缓存当中，当536-899重传之后，会按序发送给应用，确保按需到达。

报文段序号是第一个数据字节的字节流编号，确认号(ACK)是希望从对方接收到的数据的下一个字节的编号。

可靠数据传输

确保进程从接收缓存读出的数据流是非损坏的，连续的，非冗余的，按序的字节流。

TCP sender simulator

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
26
27
28

while{
	
    1.receive data from app layer
    2.create TCP segment with sequence number NextSeqNum
    3.if (timer currently not running)
    
      start timer
    4.pass segment to IP
    5.NextSeqNum+=len(data)
    
    
    timer timeout
    
    1.重传超时报文段(retransmit not yet ACKed segment with smallest seq Number )

	2.reset timer
    
    
    收到ACK：
    1.比较ACK与sendBase num
    if(ACK > sendBase num){
    	ACK = sendBase
        if(还有没有确认的报文){
        	start timer
        }
    }
}

重传定时器

1.定时器只与最早的未被确认的报文段关联起来。

2.采用自适应的重传计时策略

往返时间的估算

对于每一条TCP链接，维护一个变量EstimatedRTT,存放所估计的源到目的端的往返传输时间。

如果定时器过期之前数据段被确认，则记录下该次TCP报文段的往返传输时间SampleRTT

SampleRTT会变化，会使用若干最新的测量结果。

具体使用指数加权移动平均

重传超时间隔

TCP重传超时间隔：加倍时间间隔

TCP报文段超时并重传：对于重传报文段不更新RTT，把超时间隔加倍。

快速重传

如果TCP发送方收到对同一数据的3个冗余ACK，就认为发生了丢包（2个的话可能是乱序到达引起的）

GBN 和 SR

GBN

累计确认：正确接收到但是失序的报文段不会被接收方逐个确认。

定时器只与最早的未确认报文段关联起来

代码看我github

SR

超时发生的时候，只重传超时的一个报文段。

TCP会把很多正确接收但失序的报文段缓存起来。

TCP流量控制

TCP为应用程序提供了流量控制服务，用来消除发送方使得接收方缓存溢出的可能性。

TCP让发送方维护一个接收窗口的变量来提供流量控制，这个窗口用来给发送方指示接收方还有多少可用的缓存空间。

TCP———双工： 各自都维护一个接收窗口。

LastByteRead：主机B中的应用进程从缓存中读出的数据流的最后一个字节的编号。

LastByteRevd：从网络中到达的并且已经放入主机B接收缓存中的数据流的最后一个字节的编号。

TCP不允许已分配的缓存溢出：

1
2

LastByteRevd - LastByteRead <= Buffer

接收窗口用rwnd表示，根据缓存可用空间的数量来设置。

1
2

rwnd = RevBuffer - [LastByteRevd - LastByteRead]

具体实现

1.主机B把当前rwnd值放到发送给主机A的报文段中接收窗口字段中，用来通知主机A它在该连接的缓存中还有多少可用空间。

2.开始的时候主机B设定rwnd = RevBuffer ，主机A要保证

1

LastByteSent - LastByteAcked <= rwnd

特殊情况讨论：

当主机B接收窗口为0的时候，主机A继续发送一个只有一个字节数据的报文段。这些报文段会被接收方确认，最终缓存将开始清空。并且确认报文中将包含一个非0的值。

这也就是(probe)，防止死锁

糊涂窗口综合征

1
2
3

当发送端应用进程产生数据很慢、或接收端应用进程处理接收缓冲区数据很慢，或二者兼而有之；就会使应用进程间传送的报文段很小，特别是有效载荷很小。极端情况下，有效载荷可能只有1个字节；而传输开销有40字节(20字节的IP头+20字节的TCP头) 这种现象就叫糊涂窗口综合症。

就是应用程序消耗数据比到达的慢

发送端引起的：

如果发送端为产生数据很慢的应用程序服务(典型的有telnet应用)，例如，一次产生一个字节。这个应用程序一次将一个字节的数据写入发送端的TCP的缓存。如果发送端的TCP没有特定的指令，它就产生只包括一个字节数据的报文段。结果有很多41字节的IP数据报就在互连网中传来传去。解决的方法是防止发送端的TCP逐个字节地发送数据。必须强迫发送端的TCP收集数据，然后用一个更大的数据块来发送。发送端的TCP要等待多长时间呢？如果它等待过长，它就会使整个的过程产生较长的时延。如果它的等待时间不够长，它就可能发送较小的报文段，于是，Nagle找到了一个很好的解决方法，发明了Nagle算法。而他选择的等待时间是一个RTT,即下个ACK来到时。

接收端引起的：

接收端的TCP可能产生糊涂窗口综合症，如果它为消耗数据很慢的应用程序服务，例如，一次消耗一个字节。假定发送应用程序产生了1000字节的数据块，但接收应用程序每次只吸收1字节的数据。再假定接收端的TCP的输入缓存为4000字节。发送端先发送第一个4000字节的数据。接收端将它存储在其缓存中。现在缓存满了。它通知窗口大小为零，这表示发送端必须停止发送数据。接收应用程序从接收端的TCP的输入缓存中读取第一个字节的数据。在入缓存中现在有了1字节的空间。接收端的TCP宣布其窗口大小为1字节，这表示正渴望等待发送数据的发送端的TCP会把这个宣布当作一个好消息，并发送只包括一个字节数据的报文段。这样的过程一直继续下去。一个字节的数据被消耗掉，然后发送只包含一个字节数据的报文段。

解决方法：

接收方：

1.仅当窗口大小显著增加之后才发送增加窗口的通告。显著增加意味着窗口大小到达缓冲区空间的一半或者一个MSS的时候。———— 推迟确认技术

2.推迟确认的缺点是当确认延迟太大的时候，会导致不必要的重传，给TCP估计往返时间带来混乱。

发送方：

为了防止发送短的报文段，在发送报文段之前延迟，直到聚集足够多的数据量。采用Nagle算法来决定延迟的时间。

Nagle 算法

为了尽可能发送大块数据，避免网络中充斥着小数据块。任意时刻最多只能有一个未被确认的小段。

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

if data is available && window != MSS{

	send full segment
}

else{

	if there is unAcked data,then buffer the new data until an ACK arrives
    
    else{
    	send all new data now
    }
}

TCP 连接管理

三次握手：

三次握手原因：

发送方要知道自己有没有发出去，对方有没有接收到。第三次握手是为了让服务端知道自己的发送能力是没问题的。

第一次握手：客户端发送能力验证

第二次握手：服务端的接受能力与客户端的接受能力验证

第三次握手：服务端的发送能力验证（要求确认第二次握手发送成功了，问问客户端有没有成功）

另外一原因是防止已经失效的链接重传到服务器端。
当客户A发送连接请求，但因连接请求报文丢失而未收到确认。于是A会再次重传一次连接请求，此时服务器端B收到再次重传的连接请求，建立了连接，然后进行数据传输，数据传输完了后，就释放了此连接。假设A第一次发送的连接请求并没有丢失，而是在网络结点中滞留了太长时间，以致在AB通信完后，才到达B。此时这个连接请求其实已经是被A认为丢失的了。如果不进行第三次握手，那么服务器B可能在收到这个已失效的连接请求后，进行确认，然后单方面进入ESTABLISHED状态，而A此时并不会对B的确认进行理睬，这样就白白的浪费了服务器的资源。如果进行了第三次握手，那么A不会向B发送确认，那个重传的连接请求就会失效。

释放连接

释放连接可以看成四次挥手，当然FIN与ACK合并可以看成三次。

洪泛攻击

好的参考网址

http://www.52im.net/thread-515-1-1.html

拥塞控制

TCP拥塞控制原理

发送方如何限制它向其连接发送流量的速率？

TCP链接可以维护一个拥塞窗口变量，其反映了网络的容量，限制发送方向网络注入数据的速度必须小于接受窗口和拥塞窗口中的最小值。

1
2

LastByteSend- LastByteAcked <= min(recvWindow,congestWindow)

发送方如何感知其到目的地之间的路径上存在拥塞？

拥塞的时候路由器的缓存器溢出，导致报文段丢弃，引起发送方的丢失。

路径上出现拥塞。

TCP发送方发生”丢失”

1.超时
2.连续收到3个冗余的ACK

自计时 self-clocking

使用对以前未确认的报文段的确认来触发拥塞窗口congestionWindow长度的增加

慢启动

拥塞避免（加性增）

1.每个RTT窗口只能增加一个MSS

2.rtt动态变化，TCP实现中通常采用

1

congwindow = congwindow + MSS*(MSS/congwindow)

是一个线性上升的算法

出现拥塞

1.TCP TAHOE (乘性减）

TCP超时或者收到3个冗余的ACK的时候，需要重传

ssthresh缩减为拥塞窗口一半，并且拥塞窗口恢复到原来初始窗口大小，进入slow start process

1
2

ssthresh = max(congWindow/2,MSS)
congwindow = MSS

然后进入下面的快速恢复算法

快速回复，取消慢启动

TCP reno：

在进入Fast recovery 之前，cwnd与sshthresh会被更新：

• cwnd = cwnd / 2

• sshthresh= cwnd

• 进入快速恢复算法

真正的Fast recovery 算法如下：

维护ssthresh变量

1.拥塞窗口小于阈值时候进入慢启动阶段

2.大于该阈值的时候进入拥塞避免阶段

拥塞避免的总结

１.慢启动和拥塞避免

慢启动：拥塞窗口小于阈值ssthresh的时候指数增加

拥塞避免：拥塞窗口大于阈值的时候进入拥塞避免阶段(加性增)

超时(丢失)的时候乘性减：每次超时，把ｔｈｒｅｓｈｏｌｄ设置为当前拥塞窗口的一半，并重新回到慢启动阶段

慢启动是每次收到一个ＡＣＫ就增加一个ＭＳＳ，然而拥塞避免是每一个ＲＴＴ增加一个ＭＳＳ

当检测到超时而丢包的时候，进入tahoe的慢启动

ＴＣＰ出现拥塞：(tahoe)

sstｈresh = max(congwindow/2,MSS)
congwindow = MSS(即初始窗口的大小)

TCP出现拥塞:(Reno)(快速恢复)

与ｔａｈｏｅ不同的是，他是进入拥塞避免阶段

ssthresh = max(CongWindow/2,MSS)
CongWindow = ssthresh （设置为阈值）

当检测到3个冗余的ACK的丢包的时候，进入快速恢复状态，
ssthresh = CongWindow /2 ， CongWindow = ssthresh+（3×MSS）

如果收到冗余的ACK CongWindow+=MSS

超时前收到新的ACK，直接进入拥塞避免阶段

总结

1.慢启动 CongWindow < ssthresh 窗口指数级增长

2.拥塞避免 CongWindow > ssthresh 线性增长

3.收到3个冗余ACK而检测到丢包：

ssthresh = CongWindow / 2

CongWindow = ssthresh + (3*MSS)

每收到一个冗余的ACK，CongWindow +=Mss

超时前收到新的Ack，会直接进入拥塞避免阶段。

4.
超时事件发生丢包的时候，ssthresh = CongWindow/2
CongWindow = 1 MSS

UDP和TCP总结

UDP 优点：

１．协议简单，运行效率高
２．首部开销小，８个字节
３．支持一对一，多对多，一对多的交互通信

缺点：
不可靠，容易发生丢包

应用：

追求速度，例如聊天工具，实时视频聊天

ＴＣＰ优点：

提供可靠的服务，ＴＣＰ传送的数据无差错，不丢失，不重复而且按序到达

缺点：

首部开销大，２０个字节

会出现网络用塞，使得源主机发送效率降低。

协议复杂，速度慢

进程通信

进行通信实际上是进程，本书关注运行在不同端系统上的进程通信，他们通过跨越计算机网络交换报文而相互通信。

客户和服务器进程

在每队通信进程中，我们会将这两个进程之一标记为客户，另一个标记为服务器。

• 发起通信的进程被标记为客户，会话开始时候等待联系的进程是服务器。

进程与计算机网络之间的接口

进程通过一个称为套接字(socket)的软件接口向网络发送报文和从网络接收报文。

• 当一个进程想向位于另外一台主机上的另外一个进程发送报文的时候，它会把报文推出该门(socket)，该发送进程假定该门到另外一侧之间有运输的基础设施。一旦该报文抵达目的主机，他会通过接收进程的套接字传递，然后接收进程对该报文进行处理。

套接字实际上是网络和应用程序之间的可编程接口，

进程寻址

接收进程需要一个地址。为了标志该接收进程，需要定义两种信息：1.主机的地址。2.定义在目的主机中的接收进程的标识符。

主机由IP地址标识，是一个32bit的量。同时发送进程还要指定接收进程（接收socket），port number就用于这个目的。

运输服务

运输层协议负责使该报文进入接收进程的套接字。

一个运输层协议能够为调用它的应用程序提供：

• 可靠的数据运输
• 吞吐量
• 定时和安全性

Internet 提供的运输服务

TCP服务

• 面向连接的服务

TCP 让客户和服务器互相交换运输层控制信息，这个所谓握手过程提示客户和服务器，使他们为大量分组的到来做好准备。握手之后，一个TCP链接就在两个进程的套接字之间建立。

• 可靠的数据传送服务

应用程序一端将字节流传进套接字的时候，能够依靠TCP将相同的字节流交付给接收方的套接字。而没有字节的丢失和冗余。

HTTP

超文本传输协议由两个程序实现，一个客户程序和一个服务器程序。客户程序和服务器程序运行在不同的端系统中，通过交换HTTP报文进行会话，HTTP定义了这些报文的结构以及客户和服务器进行报文交换的方式。

Web

每个URL地址由两个部分组成。存放对象的服务器主机名和对象的路径名。
https://github.com/Hananel-Hazan/bindsnet

github.com 就是主机名 后面的是路径名

web 浏览器实现了HTTP的客户端，所以在web环境中交替使用浏览器和客户两个术语。

web服务器实现了HTTP的服务器端，它用于存储web对象。

HTTP定义了web客户向web服务器请求web页面的方式，以及服务器向客户传送web页面的方式。HTTP使用TCP作为其支撑运输协议，HTTP客户首先发起一个与服务器的TCP连接，一旦链接建立，浏览器和服务器进程就可以通过套接字接口访问TCP。

同时TCP也是一个无状态协议：服务器向客户发送被请求的文件，但是不存储任何关于该客户的状态信息。

非持续链接

每个请求和响应对是经过一个单独的TCP连接发送的。

持续链接

所有的请求及其响应都经过相同的TCP连接发送

TCP的三次握手

我们给出往返时间的定义。即一个短分组从客户到服务器然后再返回客户所花费的时间。

当浏览器在它和web服务器发起一个TCP链接。

第一次握手：客户向服务器发送一个TCP报文段。

第二次握手：然后服务器用一个小TCP报文段做出确认和响应。

第三次握手：客户的确认阶段，向该TCP链接发送一个HTTP请求报文，一旦报文到达服务器，服务器就在该TCP链接上发送HTML文件。该HTTP请求/响应用去了另外一个RTT。

因此总响应时间是两个RTT加上服务器传输HTML文件的时间。

用户与服务器的交互：cookie

cookie用于标识一个用户。用户首次访问一个站点的时候，可能需要提供一个用户标识，在后继会话中，浏览器向服务器提供一个cookie首部，从而向该服务器标识了用户。

Web缓存（proxy cache）

也叫代理服务器，能够代表初始web服务器来满足HTTP请求的网络实体。web缓存器有自己的磁盘存储空间，并在存储空间中保存最近请求过的对象的副本。

用户的所有HTTP请求首先会指向web缓存器，例如要访问http://www.someschool.edu/campus.gif，会发生如下情况：

• 浏览器建立一个到web服务器的TCP链接，并向Web缓存器的对象发送一个HTTP请求

• web缓存器进行检查，查看本地是否存储了该对象副本，如果有，web缓存器就向客户浏览器用HTTP响应报文返回该对象。

• 如果web缓存器没有对象，就打开一个与该对象的初始服务器的TCP链接，web缓存器则在这个缓存器到服务器的TCP链接上发送一个对该对象的HTTP请求。在收到该请求后，初始服务器向该web缓存器发送具有该对象的HTTP响应。

• 当web缓存器接收到该对象的时候，会在本地存储空间存储一个副本，并且向客户的浏览器用HTTP响应报文发送该副本。

当它接收浏览器的请求并发挥响应的时候，他是服务器，当他向初始服务器发出请求并接收响应的时候，他是一个客户。

条件GET方法

用来保证缓存器所存储的对象是最新的。

如果请求报文使用get方法而且请求报文中包含一个“If modifies since”首部行，那么HTTP请求报文就是一个条件GET请求报文。

DNS：因特网的目录服务

主机的标识方法：可以用主机名(hostname）或者(IP address)

而（DOMAIN NAME SYSTEM）就是用来进行主机名到IP地址转换的目录服务。

DNS 是什么

• DNS 是一个有分层的DNS服务器实现的分布式数据库.
• 也可以理解为一个使得主机能查询分布式数据库的应用层协议。
• DNS 服务器通常是运行在BIND软件的UNIX机器。DNS协议运行在UDP之上，使用53号端口。

工作流程

• 同一台用户主机上运行着DNS应用的客户端

• 浏览器从URL中抽取主机名，并把这台主机名传给DNS应用的客户端。

• DNS客户向DNS服务器发送一个包含主机名的请求

• DNS客户最终收到一份回答报文，含有对应于该主机名的IP地址

• 浏览器接收到来自DNS的该IP地址，能够向位于该IP地

DNS 功能

1.进行主机名到IP地址的转换。

2.主机别名（host aliasing）

为复杂主机名的主机提供简单的别名

3.邮件服务器别名。应用程序因此可以调用DNS，对提供邮件服务器别名进行解析，以获得该主机的规范主机名以及IP地址。

4.负载分配。

例如繁忙的站点会分布在多台机器上，每台服务器均运行在不同的端系统上，每个都有不同的IP地址，因此客户发出DNS请求的时候，服务器用IP地址的整个集合来进行响应。

分布式，层次的数据库

例子: 一个客户要决定www.amazon.com 的IP地址，先和根服务器之一联系，它将返回顶级域名com的TLD服务器的IP地址。该客户与这些TLD服务器之一联系，服务器将返回权威服务器的IP地址。

• 根DNS服务器
  全球有13个，用于返回TLD服务器的IP地址

• 顶级域（DNS）服务器（TLD）

负责顶级域名如 com、org、net、edu 和 gov，以及所有国家的顶级域名如 uk、fr 等。TLD 服务器返回权威服务器的 IP 地址

• 权威DNS服务器

管理属于同一机构同一域名但是的不同IP地址的不同主机。

• 本地DNS服务器
  起着代理的作用。每个Internet service provider (ISP)都有一台本地的DNS服务器，本地DNS服务器起着代理的作用，本地主机把DNS请求发向本地DNS服务器，本地DNS服务器把该请求转发到DNS服务器层次结构当中。

DNS的解析流程

浏览器访问域名的前置步骤：

1.先检查缓存中是否有该域名对应的解析过的IP地址，命中则解析过程结束，否则进行步骤2
2.检查操作系统缓存中是否有域名对应的DNS解析结果，命中则解析过程结束。

DNS在服务器之间的解析步骤

下图例子假设主机 cs.ustc.edu 想知道主机 cs.csu.edu 的 IP 地址，假设 USTC 大学的本地 DNS 服务器为 dns.ustc.edu，同时假设 CSU 大学的权威 DNS 服务器为 dns.csu.edu。

1.主机向本地DNS服务器dns.ustc.edu发送请求报文，报文中含有被转换的主机名cs.csu.edu

2.本地DNS服务器把查询报文转发给根DNS服务器，根服务器注意到edu
前缀，于是把负责edu的TLD的IP地址列表返回给本地DNS服务器

3.本地DNS服务器再次向TLD服务器之一发送DNS请求报文，TLD服务器注意到csu.edu的前缀，于是把权威服务器dns.csu.edu的IP地址返回给DNS服务器

4.本地DNS服务器向权威服务器dns.csu.edu 发送请求报文，权威服务器用cs.csu.edu的IP地址进行响应。

5.最后本地DNS服务器把查询得到的IP地址返回给主机cs.ustc.edu

DNS缓存

本地DNS服务器在完成一次查询之后会把得到的主机名到IP地址的映射缓存到本地，加快DNS的解析速度。解析大多是在本地服务器完成的

DNS记录

1

(Name,Value,Type,TTL)

1.Type=A,则Name是主机名，Value是主机对应的Ip地址

2.Type=NS，Name是域名，比如csu.edu，Value是知道如何获得域中主机IP地址的权威DNS服务器的主机名。

3.TYpe=CNAME，VALUE是别名为Name的主机对应的规范主机名

如果服务器不是用于某主机名的权威服务器，那么该服务器将包含一条类型 NS 记录，该记录对应于包含主机名的域；它还将包括一条类型 A 记录，该记录提供了在 NS 记录的 Value 字段中的 DNS 服务器的 IP 地址。举例来说，假设一台 edu TLD 服务器不是主机 gaia.cs.umass.edu 的权威 DNS 服务器，则该服务器将包含一条包括主机 cs.umass.edu 的域记录，如（umass.edu，dns.umass.edu，NS）；该 edu TLD 服务器还将包含一条类型 A 记录，如（dns.umass.edu，128.119.40.111，A），该记录将名字 dns.umass.edu 映射为一个 IP 地址。

注册一个全新的域名最少要向对应的 TLD 注入 A 型与 NS 型两种记录。

DNS 报文

DNS 报文格式前 12 个字节是首部区域，其中有几个字段。第一个字段（标识符）是一个 16 比特的数，用于标识该查询。这个标识符会被复制到对查询的回答报文中，以便让客户用它来匹配发送的请求和接收到的回答。标志字段中含有若干标志。1 比特的“查询/回答”标志位指出报文是查询报文（0）还是回答报文（1）。当某 DNS 服务器是所请求名字的权威 DNS 服务器时，1 比特的“权威的”标志位被置在回答报文中。如果客户（主机或者DNS 服务器）在该 DNS 服务器没有某记录时希望它执行递归查询，将设置 1 比特的“希望递归”标志位。如果该 DNS 服务器支持递归查询，在它的回答报文中会对 1 比特的“递归可用”标志位置位。在该首部中，还有 4 个有关数量的字段，这些字段指出了在首部后的 4 类数据区域出现的数量。
问题区域包含着正在进行的查询信息。该区域包括：①名字字段，指出正在被查询的主机名字；②类型字段，它指出有关该名字的正被询问的问题类型，例如主机地址是与一个名字相关联（类型 A）还是与某个名字的邮件服务器相关联（类型 MX）。
在来自 DNS 服务器的回答中，回答区域包含了对最初请求的名字的资源记录。前面讲过每个资源记录中有 Type（如 A、NS、CNAME 和 MX）字段、Value 字段和 TTL 字段。在回答报文的回答区域中可以包含多条 RR，因此一个主机名能够有多个 IP 地址（例如，就像本节前面讨论的冗余 Web 服务器）。
权威区域包含了其他权威服务器的记录。
附加区域包含了其他有帮助的记录。例如，对于一个 MX 请求的回答报文的回答区域包含了一条资源记录，该记录提供了邮件服务器的规范主机名。该附加区域包含一个类型 A 记录，该记录提供了用于该邮件服务器的规范主机名的 IP 地址。

HTTP协议

定义了Web客户机如何向Web服务器请求Web页面以及Web服务器如何将Web页面传递给Web客户机

http报文格式两种：

1.客户端：浏览器请求Web对象（request）报文
2.服务器：Web服务器对请求进行响应，发送包含该对象的报文

http使用TCP作为底层服务，客户端发起一个与服务器的TCP链接，同时http是无状态的

非持久性链接&持久性链接

非持久性链接：每个请求与响应对是一个经单独的TCP连接发送

其中每个TCP链接只传输一个对象，只传输一个请求报文和一个响应报文。
每个TCP链接在服务器返回对象后会关闭，即该链接不为其他对象而持续下来。

持久性链接：所有请求、响应对经相同的TCP连接发送

请求一个html文件所需的时间

往返时间RRT：

分组在客户机与服务器往返的时间

响应时间：

total time = 2*RRT + 文件传输时间

非持续链接的缺点：

为每个请求对象建立和维护一个全新的连接。
取对象的时候需要两个RTTs，每个TCP链接都要客户机和服务器分配TCP的缓冲区和保持TCP变量。

持久性链接

服务器在发送response之后，客户机与服务器之间的后续请求可以使用相同的链接。

有非流水线（客户机只能在前一个响应接收到之后才能发出新的请求）
和流水线（客户机遇到引用就会产生一个请求）方式

提交表单数据

用户所请求的Web页面的内容依赖于用户在表单字段中输入的内容。

Post方法

输入的内容将包含在http请求报文的实体主体中。

URL方法

使用GET方法

表单字段中的输入的内容放在URL字段中

put方法 把请求报文的实体主体的对象上传到指定Web服务器的指定的路径。

Cookie

1.HTTP response报文，set-cookie首部行

2.端系统中保留cookie一个文件，由浏览器管理

3.HTTP request报文： cookie首部行

4.Web站点的后端数据库

proxy server

ftp 文件传输协议

实现本地和远程文件系统上的移动文件

文件传输的时候，FTP客户和服务器之间要建立两个TCP链接。

控制链接

1.链接是持久性的。

2．控制信息的带外控制

３．ＦＴＰ客户端发起控制连接

数据连接

1.数据连接用于传输文件

2.非持久性链接

3.由FTP服务器发起数据链接（PORT模式）

4.客户机发起（PASV模式）

PORT模式

PORT模式建立数据传输通道是由服务器端发起的，服务器使用20端口连接客户端某一个大于1024的端口。

PASV模式

数据传输通道的建立是由FTP客户端发起的，他使用一个大于1024的端口链接服务器的1024以上的某一个端口。

ftp维持状态（state）

在整个会话期间，保留用户的状态信息

电子邮件

四个重要组件：

1.用户代理

撰写完邮件，用户代理将向其邮件服务器发送邮件，并且该邮件被放在邮件服务器的发送队列中

2.邮件服务器

报文队列：包含目前不能投递的邮件报文

邮箱：每个接收方在邮件服务器都有一个邮箱，邮箱管理和维护发给用户的报文

3.简单邮件传输协议

TCP

每个邮件服务器既有SMTP客户端运行，又有SMTP服务器端运行。发送邮件的时候，就表现为SMTP客户端，接收邮件的时候，表现为SMTP服务器

直接传输 不使用中间服务器来发送邮件

4.邮件访问协议

SMTP协议传输过程

1.首先客户机在25端口建立一个到SMTP服务器的TCP链接

2.传输的三个阶段：

1.握手

2.报文传输

3.结束

smtp与http的异同点

相同点

1.smtp和持久的http使用持续链接来传输文件

从web服务器向web浏览器

从一个邮件服务器向另外一个邮件服务器

2.都使用ASCII命令/响应交互

smtp与http不同点

1.pull协议和push协议

http:pull（拉协议）

使用浏览器从web服务器拉取信息，TCP是想要获取文件一方首先发起的。

email：push(协议)

发送邮件的服务器把文件推向接收邮件服务器，TCP是发送文件一方首先发起的。

2.smtp要求报文全部使用7-bit ASCII 码

如果报文包含非7-bitASCII码或者如图像的二进制数据，则通常使用base-64来进行编码

3.处理一个既包含文本也包含图形的其他多媒体类型

http：每个对象封装在各自的响应报文中。

smtp： 多个对象在一个多分部的报文中传送

创建

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

var express = require('express');
var app = express();

app.get('/',function(req,res){
    res.send('Hello world');

});

var server = app.listen(8080,function ()
{
    console.log('Server listening at http://'+server.address().address+':'+server.address().port);

});

Express 的路由

对于任何一个应用服务器，核心在与它是否有一个强劲的路由，路由指客户端所发出的网络请求机制，web在URL中指明它想要的内容，客户端通过路由，为不同的访问路径指定不同的处理方法。

app.get(‘/‘,function(req,res){ … });

第一个参数是访问路径，/表示根路径，第二个参数是回调函数，它的req参数表示客户端发来的HTTP请求，res参数表示服务器返回给客户端的响应，两个参数都是对象，在回调函数内部，使用HTTP响应的send方法，表示向浏览器发送一个字符串。

express框架相当于在HTTP模块上添加了一个中间件

Express 中间件

中间件是对HTTP请求功能的一种封装，是一个处理HTTP请求的函数，他有三个参数，一个网络请求对象，一个服务器响应对象，一个next函数。最大特点是，一个中间件处理完，再传递给下一个中间件，应用程序在运行过程中，会调用一系列的中间件。

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

var express = require('express');
var app = express();

app.use(function(req,res,next){
    console.log('processing request for ' +req.url);
    next();
});

app.use(function(req,res,next){
    console.log('terminating request');
    res.send('thanks for playing');
});

app.use(function(req,res,next){
   console.log('I never get called!');
});

第一个中间件只输出了一个log信息，把请求传给了下一个中间件，而第二个中间件真正的处理请求，这时候不会调用next（）方法，请求处理这个时候已经终止了。

Express中的cookie与session

cookie是HTTP协议的一部分，处理分为以下几步：

1.服务器向客户端发送cookie

2.浏览器把cookie保存

3.浏览器每次请求的时候，都会把之前保存的Cookie发给服务器。

Session

HTTP协议是一种无状态的协议，用户从页面A跳转到页面B的时候，会重新发送一次HTTP请求，而服务器端在返回响应的时候无法获知该用户在请求页面B之前做了什么，所以需要Session来保存用户的状态。

Express中的网络请求方法

1.

1
2

app.get('/',function(req,res){
});

2.

1
2
3
4

app.get('/user/:id',function(req,res)
{
res.send('user ' + res.params.id);
});

function(req,res)是一个回调函数，通过req对象可以获取请求的params参数。

req.params

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

function(req,res)是一个回调函数，通过req对象能够获得请求的param参数


var express = require('express');
var app = express();

app.get('/user/:id',function(req,res){
    res.send('user is '+req.params.id);
});

app.listen(8888,function(){
    console.log('Server is listening');
});

Seq2Seq 模型

翻译

先建立一个编码网络，是一个RNN的结构，RNN的单元可以使GRU也可以是LSTM，每次向该神经网络输入一个法语单词，将输入序列接收完毕之后，RNN会输出一个向量来代表这个输入序列。

接着建立一个解码网络，如上图二所示，以编码网络的输出作为解码网络的输入。之后它可以被训练为每次输出一个翻译后的单词，一直到它输出序列的结尾或者句子结尾标记。而且每次生成一个标记，都会传递到下一个单元中进行预测。

图像描述

先把图片输入到卷积神经网络中，如一个预训练的AlexNet结构，然后让其学习图片的编码，如果是图片分类任务，最后得到的一个特征向量输出到一个softmax层，而这里把softmax层替换为一个RNN，RNN要做的就是生成图像的描述，每次生成一个单词。

选择最有可能的句子

机器翻译（条件语言模型）

绿色表示encoder网络，紫色表示decoder网络，对于生成语言模型来说，encoder网络是以零向量开始，对于机器翻译模型来说，encoder网络会计算出一系列向量来表示输入的句子，有了这个输入句子，decoder网络就可以从这个句子开始，而不是从零向量开始，所以叫条件语言模型

x这里是法语句子，当进行机器翻译的时候，要找到一个英语句子y，使得条件概率最大化。通常使用束搜索方法。

我们W1生成的语言模型是在一个句子当中随机生成单词，但是例如下面句子：

随机生成的语言模型挑选了JANE IS 之后，由于going在英语中更加常见，因此很有可能采取下面那一句实际上并不太好的翻译。

Beam search

列出一个10000词的词汇表，为了简化问题，忽略大小写，把所有单词都以小写列出来，首先利用编码部分评估第一个单词的概率值，贪婪算法只会挑出最可能的一个单词，而beam search有一个参数B，例如设为3，那么就会考虑三个不同的单词。

所以第一步就是输入法语句子到编码网络，然后会解码这个网络，softmax层会输出10000个概率值，取前三个存起来。

第二步，假设已经选出了in,jane,september。作为第一个单词红最有可能的选择，算法接下来会针对每一个单词考虑第二个单词是什么。

把第一个单词输出作为下一个单元的输入，表示考虑第一个单词的情况下预测第二个单词。在第二步中我们更关心的事要找到最可能的第一个和第二个单词对，写成条件概率，就是上面的7式，等于第一个单词出现的概率乘以考虑第一个单词的情况下第二个单词的概率。

当选中了第一个单词的3个候选的时候，每个候选单词有10000个选择，所以一共有3x10000=30000中可能结果，按照第一和第二个词的概率，选出前三个，把这30000个可能性又变成了3个。

如果找到了第一个和第二个单词对最有可能的三个选择分别是in September,jane is 和jane visits，那么就去掉了september作为第一个单词的可能。

改进集束搜索

但概率都小于1，很多个小于1的数相乘，会得到很小很小的数字，会造成数值下溢。因此可以加上log，最大化这个log求和的概率值。

对于目标函数可以做一些改变，如果要预测一个很长的句子，那么每个单词都要乘以一个很小的数字，最后得到一个更小的概率值，所以这个目标函数有一个缺点，就是会不自然地倾向于更短的翻译结果。

我们可以不再最大化这个目标函数，而是把它归一化通过除以翻译结果的单词数量。这时候这个目标函数也叫作归一化的对数似然函数，也就是取每个单词的概率对数值的平均，这样很明显地减少了对输出长的结果的惩罚，

同时我们也可以对这个单词数量加上一个指数α，这是一个超参数，如果α=0，则不进行归一化，如果α为1，相当于用完全长度来归一化。

总结一下如何运行这个算法：

误差分析

模型有两个部分，一个神经网络模型（seq-to-seq），我们称为RNN模型，实际上是个编码器和解码器。另一部分是束搜索算法，以某个集束宽度B运行。

如果翻译错误的话，究竟是模型的那个部分出了错呢？

假设y*是理想结果，而与y^是机器给出的结果，如果是情况一的话，RNN模型输出的结果是

但是束搜索却选择了y^，明明y*的得分更高，因此是束搜索算法出了错。

第二种情况则是RNN模型出了错，它评分大小比较给错了。

词汇表征

one-hot encoding

比如如果man在词典里是第 5391 个,那么就可以表示成一个向量,只在第 5391 处为 1(上图
编号 2 所示),我们用O 5391 代表这个量,这里的O代表 one-hot。接下来,如果 woman 是编
号 9853(上图编号 3 所示),那么就可以用O 9853 来表示,这个向量只在 9853 处为 1

缺点 孤立了单词，使得算法对相关词的泛化能力不强

word embedding

例如要把单词表征为一个三百维的向量，每一维数值大小表示这个单词与对应类别的联系程度，如上图，man与woman与gender联系比较大，因此数值接近于1，而与royal联系比较小，因此数值趋近于0.

你能做的就是找到单词 w 来
使得,e man − e woman ≈ e king − e w 这个等式成立,你需要的就是找到单词 w 来最大化e w 与
e king − e man + e woman 的相似度,即

而计算相似度，通常使用余弦相似度。

语言模型

假如要把单词压缩成一个300维的嵌入向量，然后一共有10000个单词，那么可以随机初始化一个300x10000的矩阵。每一列代表一个单词的嵌入向量，那么把这个随机的矩阵与一个one-hot向量相乘就得到了这个单词的嵌入向量。

然后把如果你要预测

“I want a glass of orange ___.”,
的下一个词

把这个句子所有单词转换为嵌入向量后，全部放到一个隐藏层中（上图3），然后再通过一个分类的softmax层，预测出对应单词。

在这里这个隐藏层是一个1800维的向量（6x300）,有自己的参数。

如果你的目标是建立一个语言模型，那么一般选取目标词之前的几个词作为上下文。

但如果你的目标不是学习语言模型本身，也可以选择其他上下文。

例如要预测一个句子中间的单词，可以用前面和后面各4个单词作为上下文。

或者你想用一个更简单的上下文,也许只提供目标词的前一个词。

word2Vec

假设在训练集中给定了一个这样的句子:“I want a glass of orange juice to go along with
my cereal.”,在 Skip-Gram 模型中,我们要做的是抽取上下文和目标词配对,来构造一个监
督学习问题。

我们要随机选一个单词作为上下文词，比如选orange，然后要随机在一定词距内选择另外一个词，作为目标词，通过这种方法来学到一个好的词嵌入模型。

Word2Vec Model

有两个模型，一个是skip-gram，另外一个是Word2Vec模型。

但是这种方法对于词汇量很大的词汇表来说运算速度会变得非常非常的慢。

解决方法：

分级softmax分类器

意思就是
说不是一下子就确定到底是属于 10,000 类中的哪一类。想象如果你有一个分类器(上图编
号 1 所示),它告诉你目标词是在词汇表的前 5000 个中还是在词汇表的后 5000 个词中,假
如这个二分类器告诉你这个词在前 5000 个词中(上图编号 2 所示),然后第二个分类器会
告诉你这个词在词汇表的前 2500 个词中,或者在词汇表的第二组 2500 个词中,诸如此类

常用的词会在树的顶部，不常用的词会在树的更加深的地方。

而且实际上上下文词的概率p(c)的分布并不是单纯的在训练集语料库上均匀且随机的采样得到的,而是采用了
不同的分级来平衡更常见的词和不那么常见的词

Cbow 与 skip-gram

CBOW是从原始语句推测目标字词，对于小型数据库比较合适。而skip-gram正好相反，是从目标字词测出原始语句，在大型语料中表现更好。

Negative Sampling

上面介绍的skip-gram模型实际上是构造一个监督学习的任务，把上下文映射到了目标词上面，让你学到一个实用的词嵌入，缺点在于softmax计算起来很慢。

在这个算法中要做的是构造一个新的监督学习问题，给定一对单词比如orange和juice，去预测这是否是一对上下文词-目标词（context-target）

然后接下来构造一个监督学习问题，其中学习算法输入x，输入这对词，编号7，要去预测目标的标签，编号8，即预测输出y，因此问题就是给定一对词像orange和juice，判断这两个词究竟是分别在文本和字典中随机选取得到的，还是通过对靠近两个词采样获得的，这个算法就是要分辨这两种不同的采样方式。

*选取K：

K次就是确定了上下文词后，在字典中抽取K次随机的词

如何选取K？如果是小数据集，5-20比较好，如果数据集很大，K2-5比较好。

Model

学习从x映射到y的监督学习模型，这个(上图编号 2 所示)将是新的输入x,这个(上图编号 3 所示)将是你要预测的值y。

为了定义模型，将记号c表示上下文词，记号t表示可能的目标词，再用y表示0和1，表示是否是一对上下文-目标词，要做的就是定义一个逻辑回归模型，给定输入的c,t对的条件下，y=1的概率，即:

这个模型基于逻辑回归模型，不同的是我们把一个sigmoid函数作用于θ_t^Te_c,θ_t表示目标词对应的参数向量，而e_c对应上下文词的嵌入向量，如果有K个样本，可以把它看做1/K的正负样本比例，即每一个正样本你都有K个对应的负样本来训练一个类似逻辑回归的模型。

然后把它看成一个神经网络，如果输入词是orange，即词6257，你要做的事输入one-hot向量，再传递给E，通过两者相乘获得嵌入向量e6257，就得到了10000个可能的逻辑回归分类问题。其中一个将会是用来判断目标词是否是juice的分类器，但并不是每次迭代都训练全部10000个，只训练其中的（K+1）个，这样会减少计算成本，只需要更新K+1个逻辑单元。

说白了负采样就是有一个正样本词orange和juice，然后你会特意去生成一系列负样本，因此叫负采样。每次迭代你选择K个不同的随机的负样本词去训练你的算法。

该怎样选取负样本？

如果均匀且随机抽取负样本，这对于英文单词的分布非常没有代表性，而如果根据其在语料中的经验频率进行采样，会导致在like,the,of,and等词汇上有很高的频率。

Glove 词向量

我们曾通过挑选语料库中位置相近的两个词，列举出词对，glove算法就是使其关系明确化。
假定Xij是单词i在单词j上下文中出现的次数，你也可以遍历你的训练集，然后数出单词i在不同单词j上下文中出现的个数。如果定义上下文和目标词为任意两个位置相近的单词，假设是左右各10个词的距离，那么Xij就是一个能够获取单词i和单词j出现位置相近时候频率的计数器。

glove就是把他们的差距作最小化处理。

f(Xij)是一个加权项，如果Xij为0的话，f(Xij)也为0，防止出现log0的情况！

另一个作用是有的词在英语里出现十分频繁，比如this,is,of,a等等，这叫做停用词。但也有些不常用的词，比如durion，想把它考虑在内但是又不像那些常用词那样频繁，因此加权因子f(Xij)就可以是一个函数，即使是像durion这样不常用的词也能给予大量有意义的运算。

情感分类

方法一

把这个句子里的所有单词对应的嵌入向量求和或者取平均，得到一个平均值计算单元（上图编号3），把这个特征向量送入softmax分类器，然后输出y。

但是这种方法没有考虑词序，例如Completely lacking in good taste,good service and good ambiance.

good出现了很多次，分类器会有可能认为这是一个很好的评论，实际这是一个差评。

方法二：RNN

用一个多对一的RNN，考虑词的顺序效果。

由于你的词嵌入是在一个更大的数据集里训练的，这样的效果会更好，更好的泛化一些没有见过的新单词。

词嵌入除偏

https://github.com/rohit12sharma/Operations-on-word-vectors/blob/master/Operations%2Bon%2Bword%2Bvectors%2B-%2Bv2.ipynb

Overview of the model

创建一个基于字符的语言模型

在每一个时间步，RNN基于先前的字符去预测下一个字符是什么，dataset X = {x1,x2,….xT}是输入，而输出Y={y1,y2…yT}使得y^T = x^(T+1)

大概步骤

Initialize parameters
Run the optimization loop
    Forward propagation to compute the loss function
    Backward propagation to compute the gradients with respect to the loss function
    Clip the gradients to avoid exploding gradients
    Using the gradients, update your parameter with the gradient descent update rule.
Return the learned parameters

clip

防止梯度爆炸或者弥散，让所有参数的梯度都限定在一个范围内，如某一个值如果大于maxValue，则这个值设置为maxValue

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

def clip(gradients, maxValue):
    '''
    Clips the gradients' values between minimum and maximum.
    
    Arguments:
    gradients -- a dictionary containing the gradients "dWaa", "dWax", "dWya", "db", "dby"
    maxValue -- everything above this number is set to this number, and everything less than -maxValue is set to -maxValue
    
    Returns: 
    gradients -- a dictionary with the clipped gradients.
    '''
    
    dWaa, dWax, dWya, db, dby = gradients['dWaa'], gradients['dWax'], gradients['dWya'], gradients['db'], gradients['dby']
   
    for gradient in [dWax, dWaa, dWya, db, dby]:
        np.clip(gradient,-maxValue,maxValue,out=gradient)
    
    gradients = {"dWaa": dWaa, "dWax": dWax, "dWya": dWya, "db": db, "dby": dby}
    
    return gradients

sample

• step1 设置好第0层激活层和第一个输入字符为0向量

• forward propagate

生成一个概率向量，就是这个向量所有数加起来是1，每个数代表着某个字符出现的概率。

• 采样，根据生成的概率向量，选择下一个生成的字符

• 替换x^t的值为x^(t+1)，然后在forward propagate中继续重复这个过程，直到遇到”\n”字符。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

def sample(parameters, char_to_ix, seed):
    """
    Sample a sequence of characters according to a sequence of probability distributions output of the RNN

    Arguments:
    parameters -- python dictionary containing the parameters Waa, Wax, Wya, by, and b. 
    char_to_ix -- python dictionary mapping each character to an index.
    seed -- used for grading purposes. Do not worry about it.

    Returns:
    indices -- a list of length n containing the indices of the sampled characters.
    """
    
    # Retrieve parameters and relevant shapes from "parameters" dictionary
    Waa, Wax, Wya, by, b = parameters['Waa'], parameters['Wax'], parameters['Wya'], parameters['by'], parameters['b']
    vocab_size = by.shape[0]
    n_a = Waa.shape[1]
    
    ### START CODE HERE ###
    # Step 1: Create the one-hot vector x for the first character (initializing the sequence generation). (≈1 line)
    x = np.zeros((vocab_size, 1))
    # Step 1': Initialize a_prev as zeros (≈1 line)
    a_prev = np.zeros((n_a, 1))
    
    # Create an empty list of indices, this is the list which will contain the list of indices of the characters to generate (≈1 line)
    indices = []
    
    # Idx is a flag to detect a newline character, we initialize it to -1
    idx = -1 
    
    # Loop over time-steps t. At each time-step, sample a character from a probability distribution and append 
    # its index to "indices". We'll stop if we reach 50 characters (which should be very unlikely with a well 
    # trained model), which helps debugging and prevents entering an infinite loop. 
    counter = 0
    newline_character = char_to_ix['\n']
    
    while (idx != newline_character and counter != 50):
        
        # Step 2: Forward propagate x using the equations (1), (2) and (3)
        a = np.tanh(np.dot(Wax, x) + np.dot(Waa, a_prev) + b)
        z = np.dot(Wya, a) + by
        y = softmax(z)
        
        # for grading purposes
        np.random.seed(counter+seed) 
        
        # Step 3: Sample the index of a character within the vocabulary from the probability distribution y
        idx = np.random.choice(list(range(vocab_size)), p = y.ravel())

        # Append the index to "indices"
        indices.append(idx)
        
        # Step 4: Overwrite the input character as the one corresponding to the sampled index.
        x = np.zeros((vocab_size, 1))
        x[idx] = 1
        
        # Update "a_prev" to be "a"
        a_prev = a
        
        # for grading purposes
        seed += 1
        counter +=1
        
    ### END CODE HERE ###

    if (counter == 50):
        indices.append(char_to_ix['\n'])
    
    return indices

Gradient descent

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

def optimize(X, Y, a_prev, parameters, learning_rate = 0.01):
    """
    Execute one step of the optimization to train the model.
    
    Arguments:
    X -- list of integers, where each integer is a number that maps to a character in the vocabulary.
    Y -- list of integers, exactly the same as X but shifted one index to the left.
    a_prev -- previous hidden state.
    parameters -- python dictionary containing:
                        Wax -- Weight matrix multiplying the input, numpy array of shape (n_a, n_x)
                        Waa -- Weight matrix multiplying the hidden state, numpy array of shape (n_a, n_a)
                        Wya -- Weight matrix relating the hidden-state to the output, numpy array of shape (n_y, n_a)
                        b --  Bias, numpy array of shape (n_a, 1)
                        by -- Bias relating the hidden-state to the output, numpy array of shape (n_y, 1)
    learning_rate -- learning rate for the model.
    
    Returns:
    loss -- value of the loss function (cross-entropy)
    gradients -- python dictionary containing:
                        dWax -- Gradients of input-to-hidden weights, of shape (n_a, n_x)
                        dWaa -- Gradients of hidden-to-hidden weights, of shape (n_a, n_a)
                        dWya -- Gradients of hidden-to-output weights, of shape (n_y, n_a)
                        db -- Gradients of bias vector, of shape (n_a, 1)
                        dby -- Gradients of output bias vector, of shape (n_y, 1)
    a[len(X)-1] -- the last hidden state, of shape (n_a, 1)
    """
    
    ### START CODE HERE ###
    
    # Forward propagate through time (≈1 line)
    loss, cache = rnn_forward(X, Y, a_prev, parameters)
    
    # Backpropagate through time (≈1 line)
    gradients, a = rnn_backward(X, Y, parameters, cache)
    
    # Clip your gradients between -5 (min) and 5 (max) (≈1 line)
    gradients = clip(gradients, maxValue=5)
    
    # Update parameters (≈1 line)
    parameters = update_parameters(parameters, gradients, learning_rate)
    
    ### END CODE HERE ###
    
    return loss, gradients, a[len(X)-1]

model

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

# GRADED FUNCTION: model

import matplotlib.pyplot as plt
%matplotlib inline


def model(data, ix_to_char, char_to_ix, num_iterations = 50000, n_a = 50, dino_names = 7, vocab_size = 27):
    """
    Trains the model and generates dinosaur names. 
    
    Arguments:
    data -- text corpus
    ix_to_char -- dictionary that maps the index to a character
    char_to_ix -- dictionary that maps a character to an index
    num_iterations -- number of iterations to train the model for
    n_a -- number of units of the RNN cell
    dino_names -- number of dinosaur names you want to sample at each iteration. 
    vocab_size -- number of unique characters found in the text, size of the vocabulary
    
    Returns:
    parameters -- learned parameters
    """
    
    # Retrieve n_x and n_y from vocab_size
    n_x, n_y = vocab_size, vocab_size
    
    # Initialize parameters
    parameters = initialize_parameters(n_a, n_x, n_y)
    
    # Initialize loss (this is required because we want to smooth our loss, don't worry about it)
    loss = get_initial_loss(vocab_size, dino_names)
    
    # Build list of all dinosaur names (training examples).
    with open("names.txt") as f:
        examples = f.readlines()
    examples = [x.lower().strip() for x in examples]
    
    # Shuffle list of all dinosaur names
    np.random.seed(0)
    np.random.shuffle(examples)
    
    # Initialize the hidden state of your LSTM
    a_prev = np.zeros((n_a, 1))
    
    
    lossList = []
    # Optimization loop
    for j in range(num_iterations):
        
        ### START CODE HERE ###
        
        # Use the hint above to define one training example (X,Y) (≈ 2 lines)
        index = j % len(examples)
        X = [None] + [char_to_ix[ch] for ch in examples[index]] 
        Y = X[1:] + [char_to_ix["\n"]]
        
        # Perform one optimization step: Forward-prop -> Backward-prop -> Clip -> Update parameters
        # Choose a learning rate of 0.01
        curr_loss, gradients, a_prev = optimize(X, Y, a_prev, parameters, learning_rate = 0.01)
        
        ### END CODE HERE ###
        
        # Use a latency trick to keep the loss smooth. It happens here to accelerate the training.
        loss = smooth(loss, curr_loss)
        lossList.append(loss)
        # Every 2000 Iteration, generate "n" characters thanks to sample() to check if the model is learning properly
        if j % 2000 == 0:
            
            print('Iteration: %d, Loss: %f' % (j, loss) + '\n')
            
            # The number of dinosaur names to print
            seed = 0
            for name in range(dino_names):
                
                # Sample indices and print them
                sampled_indices = sample(parameters, char_to_ix, seed)
                print_sample(sampled_indices, ix_to_char)
                
                seed += 1  # To get the same result for grading purposed, increment the seed by one. 
      
            print('\n')
                
    plt.plot(range(num_iterations),lossList)
        
    return parameters

训练数据是88000个英文last name

手把手搭建RNN

RNN cell

一个RNN可以看做是一个cell的重复

1.Compute the hidden state with tanh activation: a⟨t⟩=tanh(Waaa⟨t−1⟩+Waxx⟨t⟩+ba).
2.Using your new hidden state a⟨t⟩, compute the prediction ŷ ⟨t⟩=softmax(Wyaa⟨t⟩+by). We provided you a function: softmax.
3.Store (a⟨t⟩,a⟨t−1⟩,x⟨t⟩,parameters) in cache
4.Return a⟨t⟩ , y⟨t⟩  and cache

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
26
27
28
29
30
31
32
33
34
35
36
37
38

    
def rnn_cell_forward(xt, a_prev, parameters):
    """
    Implements a single forward step of the RNN-cell as described in Figure (2)

    Arguments:
    xt -- your input data at timestep "t", numpy array of shape (n_x, m).
    a_prev -- Hidden state at timestep "t-1", numpy array of shape (n_a, m)
    parameters -- python dictionary containing:
                        Wax -- Weight matrix multiplying the input, numpy array of shape (n_a, n_x)
                        Waa -- Weight matrix multiplying the hidden state, numpy array of shape (n_a, n_a)
                        Wya -- Weight matrix relating the hidden-state to the output, numpy array of shape (n_y, n_a)
                        ba --  Bias, numpy array of shape (n_a, 1)
                        by -- Bias relating the hidden-state to the output, numpy array of shape (n_y, 1)
    Returns:
    a_next -- next hidden state, of shape (n_a, m)
    yt_pred -- prediction at timestep "t", numpy array of shape (n_y, m)
    cache -- tuple of values needed for the backward pass, contains (a_next, a_prev, xt, parameters)
    """
    
    # Retrieve parameters from "parameters"
    Wax = parameters["Wax"]
    Waa = parameters["Waa"]
    Wya = parameters["Wya"]
    ba = parameters["ba"]
    by = parameters["by"]
    
    ### START CODE HERE ### (≈2 lines)
    # compute next activation state using the formula given above
    a_next = np.tanh(np.dot(Waa, a_prev) + np.dot(Wax, xt) + ba)
    # compute output of the current cell using the formula given above
    yt_pred = softmax(np.dot(Wya, a_next) + by)
    ### END CODE HERE ###
    
    # store values you need for backward propagation in cache
    cache = (a_next, a_prev, xt, parameters)
    
    return a_next, yt_pred, cache

RNN forward

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

def rnn_forward(x, a0, parameters):
    """
    Implement the forward propagation of the recurrent neural network described in Figure (3).

    Arguments:
    x -- Input data for every time-step, of shape (n_x, m, T_x).
    a0 -- Initial hidden state, of shape (n_a, m)
    parameters -- python dictionary containing:
                        Waa -- Weight matrix multiplying the hidden state, numpy array of shape (n_a, n_a)
                        Wax -- Weight matrix multiplying the input, numpy array of shape (n_a, n_x)
                        Wya -- Weight matrix relating the hidden-state to the output, numpy array of shape (n_y, n_a)
                        ba --  Bias numpy array of shape (n_a, 1)
                        by -- Bias relating the hidden-state to the output, numpy array of shape (n_y, 1)

    Returns:
    a -- Hidden states for every time-step, numpy array of shape (n_a, m, T_x)
    y_pred -- Predictions for every time-step, numpy array of shape (n_y, m, T_x)
    caches -- tuple of values needed for the backward pass, contains (list of caches, x)
    """
    
    # Initialize "caches" which will contain the list of all caches
    caches = []
    
    # Retrieve dimensions from shapes of x and Wy
    n_x, m, T_x = x.shape
    n_y, n_a = parameters["Wya"].shape
    
    ### START CODE HERE ###
    
    # initialize "a" and "y" with zeros (≈2 lines)
    a = np.zeros((n_a,m,T_x))
    y_pred= np.zeros((n_y,m,T_x))
    # Initialize a_next (≈1 line)
    a_next = a0
    
    # loop over all time-steps
    for t in range(T_x):
        # Update next hidden state, compute the prediction, get the cache (≈1 line)
        a_next,yt_pred,cache = rnn_cell_forward(x[:,:,t], a_next, parameters)
        # Save the value of the new "next" hidden state in a (≈1 line)
        a[:,:,t] = a_next
        # Save the value of the prediction in y (≈1 line)
        y_pred[:,:,t] = yt_pred
        # Append "cache" to "caches" (≈1 line)
        caches.append(cache)
    ### END CODE HERE ###
    
    # store values needed for backward propagation in cache
    caches = (caches, x)
    
    return a, y_pred, caches

LSTM

遗忘门

我们假设我们正在阅读一段文本中的单词, 并希望使用 LSTM 来跟踪语法结构, 例如主语是单数还是复数。如果主语从一个单数词变为复数词, 我们需要找到一种方法来去除以前存储的单数/复数状态的内存值。在 LSTM 中, 遗忘门让我们这样做:

更新门

输出门

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

# GRADED FUNCTION: lstm_cell_forward

def lstm_cell_forward(xt, a_prev, c_prev, parameters):
    """
    Implement a single forward step of the LSTM-cell as described in Figure (4)

    Arguments:
    xt -- your input data at timestep "t", numpy array of shape (n_x, m).
    a_prev -- Hidden state at timestep "t-1", numpy array of shape (n_a, m)
    c_prev -- Memory state at timestep "t-1", numpy array of shape (n_a, m)
    parameters -- python dictionary containing:
                        Wf -- Weight matrix of the forget gate, numpy array of shape (n_a, n_a + n_x)
                        bf -- Bias of the forget gate, numpy array of shape (n_a, 1)
                        Wi -- Weight matrix of the update gate, numpy array of shape (n_a, n_a + n_x)
                        bi -- Bias of the update gate, numpy array of shape (n_a, 1)
                        Wc -- Weight matrix of the first "tanh", numpy array of shape (n_a, n_a + n_x)
                        bc --  Bias of the first "tanh", numpy array of shape (n_a, 1)
                        Wo -- Weight matrix of the output gate, numpy array of shape (n_a, n_a + n_x)
                        bo --  Bias of the output gate, numpy array of shape (n_a, 1)
                        Wy -- Weight matrix relating the hidden-state to the output, numpy array of shape (n_y, n_a)
                        by -- Bias relating the hidden-state to the output, numpy array of shape (n_y, 1)
                        
    Returns:
    a_next -- next hidden state, of shape (n_a, m)
    c_next -- next memory state, of shape (n_a, m)
    yt_pred -- prediction at timestep "t", numpy array of shape (n_y, m)
    cache -- tuple of values needed for the backward pass, contains (a_next, c_next, a_prev, c_prev, xt, parameters)
    
    Note: ft/it/ot stand for the forget/update/output gates, cct stands for the candidate value (c tilde),
          c stands for the memory value
    """

    # Retrieve parameters from "parameters"
    Wf = parameters["Wf"]
    bf = parameters["bf"]
    Wi = parameters["Wi"]
    bi = parameters["bi"]
    Wc = parameters["Wc"]
    bc = parameters["bc"]
    Wo = parameters["Wo"]
    bo = parameters["bo"]
    Wy = parameters["Wy"]
    by = parameters["by"]
    
    # Retrieve dimensions from shapes of xt and Wy
    n_x, m = xt.shape
    n_y, n_a = Wy.shape

    ### START CODE HERE ###
    # Concatenate a_prev and xt (≈3 lines)
    concat = np.zeros((n_a+n_x,m))
    concat[:n_a,:] = a_prev
    concat[n_a:,:] = xt
    # Compute values for ft, it, cct, c_next, ot, a_next using the formulas given figure (4) (≈6 lines)
    ft = sigmoid(np.dot(Wf,concat)+bf)
    it = sigmoid(np.dot(Wi,concat)+bi)
    cct = np.tanh(np.dot(Wc,concat)+bc)
    c_next = ft*c_prev+it*cct
    ot = sigmoid(np.dot(Wo,concat)+bo)
    a_next = ot*np.tanh(c_next)
    # Compute prediction of the LSTM cell (≈1 line)
    yt_pred = softmax(np.dot(Wy,a_next)+by)
    ### END CODE HERE ###

    # store values needed for backward propagation in cache
    cache = (a_next, c_next, a_prev, c_prev, ft, it, cct, ot, xt, parameters)

    return a_next, c_next, yt_pred, cache

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

def lstm_forward(x, a0, parameters):
    """
    Implement the forward propagation of the recurrent neural network using an LSTM-cell described in Figure (3).

    Arguments:
    x -- Input data for every time-step, of shape (n_x, m, T_x).
    a0 -- Initial hidden state, of shape (n_a, m)
    parameters -- python dictionary containing:
                        Wf -- Weight matrix of the forget gate, numpy array of shape (n_a, n_a + n_x)
                        bf -- Bias of the forget gate, numpy array of shape (n_a, 1)
                        Wi -- Weight matrix of the update gate, numpy array of shape (n_a, n_a + n_x)
                        bi -- Bias of the update gate, numpy array of shape (n_a, 1)
                        Wc -- Weight matrix of the first "tanh", numpy array of shape (n_a, n_a + n_x)
                        bc -- Bias of the first "tanh", numpy array of shape (n_a, 1)
                        Wo -- Weight matrix of the output gate, numpy array of shape (n_a, n_a + n_x)
                        bo -- Bias of the output gate, numpy array of shape (n_a, 1)
                        Wy -- Weight matrix relating the hidden-state to the output, numpy array of shape (n_y, n_a)
                        by -- Bias relating the hidden-state to the output, numpy array of shape (n_y, 1)
                        
    Returns:
    a -- Hidden states for every time-step, numpy array of shape (n_a, m, T_x)
    y -- Predictions for every time-step, numpy array of shape (n_y, m, T_x)
    caches -- tuple of values needed for the backward pass, contains (list of all the caches, x)
    """

    # Initialize "caches", which will track the list of all the caches
    caches = []
    
    ### START CODE HERE ###
    # Retrieve dimensions from shapes of x and Wy (≈2 lines)
    n_x, m, T_x = x.shape
    n_y, n_a = parameters["Wy"].shape
    
    # initialize "a", "c" and "y" with zeros (≈3 lines)
    a = np.zeros((n_a, m, T_x))
    c = a
    y = np.zeros((n_y, m, T_x))
    
    # Initialize a_next and c_next (≈2 lines)
    a_next = a0
    c_next = np.zeros(a_next.shape)
    
    # loop over all time-steps
    for t in range(T_x):
        # Update next hidden state, next memory state, compute the prediction, get the cache (≈1 line)
        a_next, c_next, yt, cache = lstm_cell_forward(x[:,:,t], a_next, c_next, parameters)
        # Save the value of the new "next" hidden state in a (≈1 line)
        a[:,:,t] = a_next
        # Save the value of the prediction in y (≈1 line)
        y[:,:,t] = yt
        # Save the value of the next cell state (≈1 line)
        c[:,:,t]  = c_next
        # Append the cache into caches (≈1 line)
        caches.append(cache)
        
    ### END CODE HERE ###
    
    # store values needed for backward propagation in cache
    caches = (caches, x)

    return a, y, c, caches

RNN backward pass

LSTM music generation

从一个更长的序列中随机选取30个数值片段来训练模型，因此不会设置x(1) 为 零向量。 设置每个片段都有相同长度Tx=30，使得矢量化更容易。

building model

对于序列生成，测试的时候不能提前知道所有的x^t数值，而使用x^t = y^(t-1)一次生成一个，因此要实现for循环来访问不同的时间步，函数djmodel()将使用for循环调用LSTM层TX T次，并且每次第Tx步都应该有共享权重，而不应该重新初始化权重。

在Keras中实现具有共享权重层的关键步骤

1.定义层对象

2.前向传播输入时候调用这些对象

1
2
3
4

n_a = 64 
reshapor = Reshape((1, n_values))
LSTM_cell = LSTM(n_a, return_state = True)
Densor = Dense(n_values, activation='softmax')

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def create_model(Tx, n_a, n_values):
    """
    Implement the model
    
    Arguments:
    Tx -- length of the sequence in a corpus
    n_a -- the number of activations used in our model
    n_values -- number of unique values in the music data 
    
    Returns:
    model -- a keras model with the 
    """
    
    # Define the input of your model with a shape 
    X = Input(shape=(Tx, n_values))
    
    # Define s0, initial hidden state for the decoder LSTM
    a0 = Input(shape=(n_a,), name='a0')
    c0 = Input(shape=(n_a,), name='c0')
    a = a0
    c = c0
    
    # Step 1: Create empty list to append the outputs while you iterate (≈1 line)
    output = []
    
    # Step 2: Loop
    for t in range(Tx):
        
        # Step 2.A: select the "t"th time step vector from X. 
        x = Lambda(lambda x:X[:,t,:])(X)
        # Step 2.B: Use reshapor to reshape x to be (1, n_values) (≈1 line)
        x = reshapor(x)
        # Step 2.C: Perform one step of the LSTM_cell
        a,_,c = LSTM_cell(x,initial_state = [a,c])
        # Step 2.D: Apply densor to the hidden state output of LSTM_Cell
        out = Densor(a)
        # Step 2.E: add the output to "outputs"
        output.append(out)
    # Step 3: Create model instance
    model = Model([X,a0,c0],output)
    
    return model

1

model = create_model(Tx = 30 , n_a = n_a, n_values = n_values)

1
2
3

opt = Adam(lr=0.1, beta_1=0.9, beta_2=0.999, decay=0.003)

model.compile(optimizer=opt, loss='categorical_crossentropy', metrics=['accuracy'])

1
2
3
4

m = 60
a0 = np.zeros((m,n_a))
c0 = np.zeros((m,n_a))
model.fit([X, a0, c0], list(Y), epochs=500)

LSTM

用上个cell预测的值来作为下个cell的输入值

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

def music_inference_model(LSTM_cell, densor, n_values = n_values, n_a = 64, Ty = 100):
    """
    Uses the trained "LSTM_cell" and "densor" from model() to generate a sequence of values.
    
    Arguments:
    LSTM_cell -- the trained "LSTM_cell" from model(), Keras layer object
    densor -- the trained "densor" from model(), Keras layer object
    n_values -- integer, umber of unique values
    n_a -- number of units in the LSTM_cell
    Ty -- integer, number of time steps to generate
    
    Returns:
    inference_model -- Keras model instance
    """
    
    # Define the input of your model with a shape 
    x0 = Input(shape=(1, n_values))
    
    # Define s0, initial hidden state for the decoder LSTM
    a0 = Input(shape=(n_a,), name='a0')
    c0 = Input(shape=(n_a,), name='c0')
    a = a0
    c = c0
    x = x0

    # Step 1: Create an empty list of "outputs" to later store your predicted values (≈1 line)
    outputs = []
    
    # Step 2: Loop over Ty and generate a value at every time step
    for t in range(Ty):
        
        # Step 2.A: Perform one step of LSTM_cell (≈1 line)
        a, _, c = LSTM_cell(x, initial_state=[a, c])
        
        # Step 2.B: Apply Dense layer to the hidden state output of the LSTM_cell (≈1 line)
        out = densor(a)

        # Step 2.C: Append the prediction "out" to "outputs". out.shape = (None, 78) (≈1 line)
        outputs.append(out)
        
        # Step 2.D: Select the next value according to "out", and set "x" to be the one-hot representation of the
        #           selected value, which will be passed as the input to LSTM_cell on the next step. We have provided 
        #           the line of code you need to do this. 
        x = Lambda(one_hot)(out)
        
    # Step 3: Create model instance with the correct "inputs" and "outputs" (≈1 line)
    inference_model = Model(inputs = [x0, a0, c0], outputs = outputs)
    
    return inference_model