作为一个伪ACMer,先来首广为人知的打油诗:
模拟只会猜题意，贪心只能过样例，数学上来先打表，规律一般是DP，组合数学碰运气，计算几何瞎暴力，图论一顿套模板，数论只会GCD,递归递推伤不起，搜索茫然TLE，分治做得像枚举，暴力枚举数第一，数据结构干瞪眼，怒刷水题找信心。

1、什么是树

如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。

2、最小生成树

一个图中可能存在多条相连的边,我们一定可以从一个图中挑出一些边生成一棵树。这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。

一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

3、最小生成树的应用

要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

4、实现最小生成树的两种算法

4.1 prim (普里姆算法)

算法分析:

Prim算法每次循环都将一个蓝点u变为白点，并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边，最后得到的一定是最小生成树。

我们通过对下图最小生成树的求解模拟来理解上面的思想。蓝点和虚线代表未进入最小生成树的点、边；白点和实线代表已进入最小生成树的点、边。

初始时所有点都是蓝点，min[1]=0,min[2、3、4、5]=∞。权值之和MST=0。

第一次循环自然是找到min[1]=0最小的蓝点1。将1变为白点，接着枚举与1相连的所有蓝点2、3、4，修改它们与白点相连的最小边权。

min[2]=w[1][2]=2;
min[3]=w[1][3]=4;
min[4]=w[1][4]=7；
第二次循环是找到min[2]最小的蓝点2。将2变为白点，接着枚举与2相连的所有蓝点3、5，修改它们与白点相连的最小边权。

min[3]=w[2][3]=1;
min[5]=w[2][5]=2;

第三次循环是找到min[3]最小的蓝点3。将3变为白点，接着枚举与3相连的所有蓝点4、5，修改它们与白点相连的最小边权。

min[4]=w[3][4]=1;
由于min[5]=2 < w[3][5]=6;所以不修改min[5]的值。
最后两轮循环将点4、5以及边w[2][5],w[3][4]添加进最小生成树。

最后权值之和MST=6。这n次循环，每次循环我们都能让一个新的点加入生成树，n次循环就能把所有点囊括到其中；每次循环我们都能让一条新的边加入生成树，n-1次循环就能生成一棵含有n个点的树；每次循环我们都取一条最小的边加入生成树，n-1次循环结束后，我们得到的就是一棵最小的生成树。这就是Prim采取贪心法生成一棵最小生成树的原理。算法时间复杂度：O (N2)。

精彩例题:

题目链接:https://www.acwing.com/problem/content/860/

Code:

	// prim 算法求最小生成树 
	
	#include <cstdio>
	#include <string>
	#include <cstring>
	#include <iostream>
	#include <algorithm>
	
	#define INF 0x3f3f3f3f
	
	using namespace std;
	
	const int maxn = 505;
	
	int a[maxn][maxn];
	
	int vis[maxn],dist[maxn];
	
	int n,m;
	
	int u,v,w;
	
	long long sum = 0;
	
	int prim(int pos) {
		dist[pos] = 0;
		// 一共有 n 个点,就需要 遍历 n 次,每次寻找一个权值最小的点,记录其下标
		for(int i = 1; i <= n; i ++) {
			int cur = -1;
			for(int j = 1; j <= n; j ++) {
				if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) {
					cur = j;
				}
			}
			// 这里需要提前终止
			if(dist[cur] >= INF) return INF;
			sum += dist[cur];
			vis[cur] = 1;
			for(int k = 1; k <= n; k ++) {
			    // 只更新还没有找到的最小权值
				if(!vis[k]) dist[k] = min(dist[k],a[cur][k]);
			}
		}
		return sum;
	}
	
	int main(void) {
		scanf("%d%d",&n,&m);
		memset(a,0x3f,sizeof(a));
		memset(dist,0x3f,sizeof(dist));
		for(int i = 1; i <= m; i ++) {
			scanf("%d%d%d",&u,&v,&w);
			a[u][v] = min(a[u][v],w);
			a[v][u] = min(a[v][u],w);
		}
		int value = prim(1);
		if(value >= INF) puts("impossible");
		else printf("%lld\n",sum);
		return 0;
	} 

4.2 kruskal (克鲁斯卡尔算法)

Kruskal（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。

算法描述:

在描述 kruskal 算法时先了解一下连通块的概念, 我们将无向图中相互连通的一些点称为处于同一个连通块中。

从上图我们可以清晰的看到,有 3 个连通块(1,2),(3),(4,5,6)。

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。

Kruskal（克鲁斯卡尔）算法开始时，认为每一个点都是孤立的，分属于n个独立的集合。

5个集合{ {1}，{2}，{3}，{4}，{5} }

生成树中没有边
Kruskal每次都选择一条最小的边，而且这条边的两个顶点分属于两个不同的集合。将选取的这条边加入最小生成树，并且合并集合。
第一次选择的是<1,2>这条边，将这条边加入到生成树中，并且将它的两个顶点1、2合并成一个集合。

4个集合{ {1，2}，{3}，{4}，{5} }
生成树中有一条边{ <1,2> }
第二次选择的是<4,5>这条边，将这条边加入到生成树中，并且将它的两个顶点4、5合并成一个集合。

3个集合{ {1，2}，{3}，{4，5} }
生成树中有2条边{ <1,2> ，<4,5>}
第三次选择的是<3,5>这条边，将这条边加入到生成树中，并且将它的两个顶点3、5所在的两个集合合并成一个集合

2个集合{ {1，2}，{3，4，5} }
生成树中有3条边{ <1,2> ，<4,5>，< 3，5>}
第四次选择的是<2,5>这条边，将这条边加入到生成树中，并且将它的两个顶点2、5所在的两个集合合并成一个集合。

1个集合{ {1，2，3，4，5} }
生成树中有4条边{ <1,2> ，<4,5>，< 3，5>，<2,5>}
算法结束，最小生成树权值为19。

通过上面的模拟能够看到，Kruskal算法每次都选择一条最小的，且能合并两个不同集合的边，一张n个点的图总共选取n-1次边。因为每次我们选的都是最小的边，所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合，最后n个点一定会合并成一个集合。通过这样的贪心策略，Kruskal算法就能得到一棵有n-1条边，连接着n个点的最小生成树。

精彩例题:

题目链接:https://www.acwing.com/problem/content/861/

Code:

	// Kruskal 算法求最小生成树 
	
	#include <cstdio>
	#include <string>
	#include <cstring>
	#include <iostream>
	#include <algorithm>
	
	using namespace std;
	
	const int maxn = 2e5 + 10; 
	
	struct node {
		int x,y,z;
	}edge[maxn];
	
	bool cmp(node a,node b) {
		return a.z < b.z;
	}
	
	int fa[maxn];
	
	int n,m;
	
	int u,v,w; 
	
	long long sum;
	
	int get(int x) {
		return x == fa[x] ? x : fa[x] = get(fa[x]);
	}
	
	int main(void) {
		scanf("%d%d",&n,&m);
		for(int i = 1; i <= m; i ++) {
			scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
		}
		for(int i = 0; i <= n; i ++) {
			fa[i] = i;
		}
		sort(edge + 1,edge + 1 + m,cmp);
		// 每次加入一条最短的边
		for(int i = 1; i <= m; i ++) {
			int x = get(edge[i].x);
			int y = get(edge[i].y);
			if(x == y) continue;
			fa[y] = x;
			sum += edge[i].z;
		}
		int ans = 0;
		for(int i = 1; i <= n; i ++) {
			if(i == fa[i]) ans ++;
		}
		if(ans > 1) puts("impossible");
		else printf("%lld\n",sum);
		return 0;
	} 

5、总结

从上面的两道模板可得知,解决最小生成树的问题一般有两种方式:prim 和 Kruskal ,那么,什么时候选择哪种策略就成为了我们应该思考的一个问题:
稀疏图一般选择 prim,采用 邻接矩阵 进行存储边之间的关系。
稠密图一般选择 Kruskal ,采用邻接表进行存储边之间的关系(更多采用结构体的方式)。

参考链接:https://www.cnblogs.com/SeanOcean/p/10975694.html

目录

a. 基本随机数

1．rand() 

2．randn()

b. 连续型分布随机数

3．unifrnd()

4．normrnd()

5．chi2rnd()

6．frnd()

7．trnd()

8．betarnd()

10．gamrnd()

11．lognrnd()

12．raylrnd()

c. 离散型分布随机数

14．unidrnd()

15．binornd()

16．geornd()

17．poissrnd()

---

a. 基本随机数

Matlab 中有两个最基本生成随机数的函数。

1．rand() 

生成（0,1）区间上均匀分布的随机变量。基本语法：

rand([M,N,P ...])

生成排列成 M*N*P... 多维向量的随机数。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=rand(100000,1);

hist(x,30);

由此可以看到生成的随机数很符合均匀分布。

2．randn()

生成服从标准正态分布（均值为 0，方差为 1）的随机数。基本语法和 rand() 类似。

randn([M,N,P ...])

生成排列成 M*N*P... 多维向量的随机数。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=randn(100000,1);

hist(x,50);

由图可以看到生成的随机数很符合标准正态分布。

b. 连续型分布随机数

如果你安装了统计工具箱（Statistic Toolbox)，除了这两种基本分布外，还可以用 Matlab 内部函数生成符合下面这些分布的随机数。

3．unifrnd()

这个函数生成某个区间内均匀分布的随机数。基本语法

unifrnd(a,b,[M,N,P,...])

生成的随机数区间在 (a,b) 内，排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数都在 (-2,3) 区间内.

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=unifrnd(-2,3,100000,1);

hist(x,50);

由图可以看到生成的随机数很符合区间 (-2,3) 上面的均匀分布。

4．normrnd()

此函数生成指定均值、标准差的正态分布的随机数。基本语法

normrnd(mu,sigma,[M,N,P,...])

生成的随机数服从均值为 mu，标准差为 sigma（注意标准差是正数）正态分布，这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的正态分布都是均值为 2，标准差为 3.

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=normrnd(2,3,100000,1);

hist(x,50);

如图，上半部分是由上一行语句生成的均值为 2，标准差为 3 的 10 万个随机数的大致分布，下半部分是用小节 “randn()” 中最后那段语句生成 10 万个标准正态分布随机数的大致分布。

注意到上半个图像的对称轴向正方向偏移（准确说移动到 x=2 处），这是由于均值为2的结果。

而且，由于标准差是 3，比标准正态分布的标准差（1）要高，所以上半部分图形更胖 (注意 x 轴刻度的不同)。

5．chi2rnd()

此函数生成服从卡方（Chi-square) 分布的随机数。卡方分布只有一个参数：自由度 v。基本语法

chi2rnd(v,[M,N,P,...])

生成的随机数服从自由度为 v 的卡方分布，这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的卡方分布的自由度都是5

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=chi2rnd(5,100000,1);

hist(x,50);

6．frnd()

此函数生成服从 F 分布的随机数。F分布有2个参数：v1, v2。基本语法

frnd(v1,v2,[M,N,P,...])

生成的随机数服从参数为 (v1,v2) 的卡方分布，这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的参数为 (v1=3,v2=5) 的 F 分布

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=frnd(3,5,100000,1);

hist(x,50);

从结果可以看出来， F分布集中在 x 正半轴的左侧，但是它在极端值处也很可能有一些取值。

7．trnd()

此函数生成服从 t 分布 (Student's t Distribution，这里 Student 不是学生的意思，而是 Cosset.W.S. 的笔名) 的随机数。t 分布有 1 个参数：自由度 v。基本语法

trnd(v,[M,N,P,...])

生成的随机数服从参数为 v 的t分布，这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的参数为 (v=7) 的 t 分布

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=trnd(7,100000,1);

hist(x,50);

可以发现t分布比标准正太分布要 “瘦”，不过随着自由度 v 的增大，t 分布会逐渐变胖，当自由度为正无穷时，它就变成标准正态分布了。

接下来的分布相对没有这么常用，同时这些函数的语法和前面函数语法相同，所以写得就简略一些。

8．betarnd()

此函数生成服从 Beta 分布的随机数。Beta 分布有两个参数分别是 A 和 B。

生成beta分布随机数的语法是：

betarnd(A,B,[M,N,P,...])

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=betarnd(3,5,100000,1);

hist(x,50);

9．exprnd()

此函数生成服从指数分布的随机数。指数分布只有一个参数: mu。

生成指数分布随机数的语法是：

exprnd(mu,[M,N,P,...])

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=exprnd(0.5,100000,1);

hist(x,50);

10．gamrnd()

生成服从 Gamma 分布的随机数。Gamma 分布有两个参数：A 和 B。

生成 Gamma 分布随机数的语法是：

gamrnd(A,B,[M,N,P,...])

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=gamrnd(3,5,100000,1);

hist(x,50);

11．lognrnd()

生成服从对数正态分布的随机数。其有两个参数：mu 和 sigma，服从这个这样的随机数取对数后就服从均值为 mu，标准差为 sigma 的正态分布。

生成对数正态分布随机数的语法是：

lognrnd(mu,sigma,[M,N,P,...])

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=lognrnd(-1,1/1.2,100000,1);

hist(x,50);

12．raylrnd()

生成服从瑞利（Rayleigh）分布的随机数。其分布有 1 个参数：B。

生成瑞利分布随机数的语法是：

raylrnd(B,[M,N,P,...])

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=raylrnd(2,100000,1);

hist(x,50);

13．wblrnd()

生成服从威布尔（Weibull）分布的随机数。其分布有 2 个参数：scale 参数 A 和 shape 参数 B。

生成 Weibull 分布随机数的语法是：

wblrnd(A,B,[M,N,P,...])

还有非中心卡方分布(ncx2rnd)，非中心F分布(ncfrnd)，非中心t分布（nctrnd)，括号中是生成服从这些分布的函数，具体用法用：help 函数名 的方法查找。

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=wblrnd(3,2,100000,1);

hist(x,50);

c. 离散型分布随机数

离散分布的随机数可能的取值是离散的，一般是整数。

14．unidrnd()

此函数生成服从离散均匀分布的随机数。Unifrnd 是在某个区间内均匀选取实数（可为小数或整数），Unidrnd 是均匀选取整数随机数。离散均匀分布随机数有 1 个参数：n, 表示从 {1, 2, 3, ... N} 这 n 个整数中以相同的概率抽样。基本语法：

unidrnd(n,[M,N,P,...])

这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的参数为 (10,0.3) 的二项分布

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=unidrnd(9,100000,1);

hist(x,9);

可见，每个整数的取值可能性基本相同。

15．binornd()

此函数生成服从二项分布的随机数。二项分布有 2 个参数：n, p。考虑一个打靶的例子，每枪命中率为 p，共射击 N 枪，那么一共击中的次数就服从参数为（N,p）的二项分布。注意 p 要小于等于1 且非负，N 要为整数。基本语法：

binornd(n,p,[M,N,P,...])

生成的随机数服从参数为 (N,p) 的二项分布，这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的参数为 (10,0.3) 的二项分布

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=binornd(10,0.45,100000,1);

hist(x,11);

我们可以将此直方图解释为，假设每枪射击命中率为 0.45，每论射击 10 次，共进行 10 万轮，这个图就表示这 10 万轮每轮命中成绩可能的一种情况。

16．geornd()

此函数生成服从几何分布的随机数。几何分布的参数只有一个：p。几何分布的现实意义可以解释为，打靶命中率为 p，不断地打靶，直到第一次命中目标时没有击中次数之和。注意 p 是概率，所以要小于等于1且非负。基本语法：

geornd(p,[M,N,P,...])

这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的参数为(0.4)的二项分布

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=geornd(0.4,100000,1);

hist(x,50);

17．poissrnd()

此函数生成服从泊松 (Poisson) 分布的随机数。泊松分布的参数只有一个：lambda。此参数要大于零。基本语法：

geornd(p,[M,N,P,...])

这些随机数排列成 M*N*P... 多维向量。如果只写 M，则生成 M*M 矩阵；如果参数为 [M,N] 可以省略掉方括号。例如：

%注：上述语句生成的随机数所服从的参数为(2)的泊松分布

通过下面代码，可以生成大量随机数，查看大致的分布情况：

x=poissrnd(2,100000,1);

hist(x,50);

其他离散分布还有超几何分布 (Hyper-geometric, 函数是 hygernd) 等，详细见 Matlab 帮助文档。

本博客文字大多来自博客 MATLAB随机数生成_MALSIS的博客-CSDN博客_matlab生成一个随机数

一、概述

生成对抗网络(Generative Adversarial Networks)是一种无监督深度学习模型，用来通过计算机生成数据，由Ian J. Goodfellow等人于2014年提出。模型通过框架中(至少)两个模块：生成模型(Generative Model)和判别模型(Discriminative Model)的互相博弈学习产生相当好的输出。生成对抗网络被认为是当前最具前景、最具活跃度的模型之一，目前主要应用于样本数据生成、图像生成、图像修复、图像转换、文本生成等方向。

GAN这种全新的技术在生成方向上带给了人工智能领域全新的突破。在之后的几年中生GAN成为深度学习领域中的研究热点，近几年与GAN有关的论文数量也急速上升，目前数量仍然在持续增加中。

GAN论文数量增长示意图

2018年，对抗式神经网络的思想被《麻省理工科技评论》评选为2018年“全球十大突破性技术”(10 Breakthrough Technologies)之一。 Yann LeCun(“深度学习三巨头”之一，纽约大学教授，前Facebook首席人工智能科学家)称赞生成对抗网络是“过去20年中深度学习领域最酷的思想”，而在国内被大家熟知的前百度首席科学家Andrew Ng也把生成对抗网络看作“深度学习领域中一项非常重大的进步”。

二、GAN基本原理

1. 构成

GAN由两个重要的部分构成：生成器(Generator，简写作G)和判别器(Discriminator，简写作D)。

• 生成器：通过机器生成数据，目的是尽可能“骗过”判别器，生成的数据记做G(z)；
• 判别器：判断数据是真实数据还是「生成器」生成的数据，目的是尽可能找出「生成器」造的“假数据”。它的输入参数是x，x代表数据，输出D(x)代表x为真实数据的概率，如果为1，就代表100%是真实的数据，而输出为0，就代表不可能是真实的数据。

这样，G和D构成了一个动态对抗(或博弈过程)，随着训练(对抗)的进行，G生成的数据越来越接近真实数据，D鉴别数据的水平越来越高。在理想的状态下，G可以生成足以“以假乱真”的数据；而对于D来说，它难以判定生成器生成的数据究竟是不是真实的，因此D(G(z)) = 0.5。训练完成后，我们得到了一个生成模型G，它可以用来生成以假乱真的数据。

GAN示意图

2. 训练过程

• 第一阶段：固定「判别器D」，训练「生成器G」。使用一个性能不错的判别器，G不断生成“假数据”，然后给这个D去判断。开始时候，G还很弱，所以很容易被判别出来。但随着训练不断进行，G技能不断提升，最终骗过了D。这个时候，D基本属于“瞎猜”的状态，判断是否为假数据的概率为50%。
• 第二阶段：固定「生成器G」，训练「判别器D」。当通过了第一阶段，继续训练G就没有意义了。这时候我们固定G，然后开始训练D。通过不断训练，D提高了自己的鉴别能力，最终他可以准确判断出假数据。
• 重复第一阶段、第二阶段。通过不断的循环，「生成器G」和「判别器D」的能力都越来越强。最终我们得到了一个效果非常好的「生成器G」，就可以用它来生成数据。

3. GAN的优缺点

1)优点

• 能更好建模数据分布(图像更锐利、清晰)；
• 理论上，GANs 能训练任何一种生成器网络。其他的框架需要生成器网络有一些特定的函数形式，比如输出层是高斯的；
• 无需利用马尔科夫链反复采样，无需在学习过程中进行推断，没有复杂的变分下界，避开近似计算棘手的概率的难题。

2)缺点

• 模型难以收敛，不稳定。生成器和判别器之间需要很好的同步，但是在实际训练中很容易D收敛，G发散。D/G 的训练需要精心的设计。
• 模式缺失(Mode Collapse)问题。GANs的学习过程可能出现模式缺失，生成器开始退化，总是生成同样的样本点，无法继续学习。

4. GAN的应用

1)生成数据集

人工智能的训练是需要大量的数据集，可以通过GAN自动生成低成本的数据集。

2)人脸生成

3)物品生成

4)图像转换

5)图像修复

三、GAN的数学原理

1.GAN的数学推导

生成模型会从一个输入空间将数据映射到生成空间(即通过输入数据，在函数作用下生成输出数据)，写成公式的形式是x=G(z)。通常，输入z会满足一个简单形式的随机分布(比如高斯分布或者均匀分布等)，为了使得生成的数据分布能够尽可能地逼近真实数据分布，生成函数G会是一个神经网络的形式，通过神经网络可以模拟出各种完全不同的分布类型。

以下是生成对抗网络中的代价函数，以判别器D为例，代价函数写作J(D)J^{(D)}J(D)，形式如下所示:

其中，E表示期望概率，x∼Pdatax \sim P_{data}x∼Pdata​表示x满足PdataP_{data}Pdata​分布。

对于生成器来说它与判别器是紧密相关的，我们可以把两者看作一个零和博弈，它们的代价综合应该是零，所以生成器的代价函数应满足如下等式：

J(G)=−J(D)J^{(G)} = -J^{(D)} J(G)=−J(D)

这样一来，我们可以设置一个价值函数V来表示J(G)J^{(G)}J(G)和J(D)J^{(D)}J(D)：

我们现在把问题变成了需要寻找一个合适的V(θ(D)，θ(G))V(θ^{(D)}，θ^{(G)})V(θ(D)，θ(G))使得J(G)J^{(G)}J(G)和J(D)J^{(D)}J(D)都尽可能小，也就是说对于判别器而言越大越V(θ(D)，θ(G))V(θ^{(D)}，θ^{(G)})V(θ(D)，θ(G))好，而对于生成器来说则是越小越好V(θ(D)，θ(G))V(θ^{(D)}，θ^{(G)})V(θ(D)，θ(G))，从而形成了两者之间的博弈关系。

在博弈论中，博弈双方的决策组合会形成一个纳什平衡点(Nash equilibrium)，在这个博弈平衡点下博弈中的任何一方将无法通过自身的行为而增加自己的收益。在生成对抗网络中，我们要计算的纳什平衡点正是要寻找一个生成器G与判别器D使得各自的代价函数最小，从上面的推导中也可以得出我们希望找到一个V(θ(D)，θ(G))V(θ^{(D)}，θ^{(G)})V(θ(D)，θ(G))对于生成器来说最小而对判别器来说最大，我们可以把它定义成一个寻找极大极小值的问题，公式如下所示：

我们可以用图形化的方法理解一下这个极大极小值的概念，一个很好的例子就是鞍点(saddle point)，如下图所示，即在一个方向是函数的极大值点，而在另一个方向是函数的极小值点。

在上面公式的基础上，我们可以分别求出理想的判别器D*和生成器G*：

下面我们先来看一下如何求出理想的判别器，对于上述的D*，我们假定生成器G是固定的，令式子中的G(z)=x。推导如下：

我们现在的目标是希望寻找一个D使得V最大，我们希望对于积分中的项f(x)=pdata(x)logD(x)＋pg(x)log(1−D(x))f(x)=p_{data}(x)logD(x)＋p_g(x)log(1-D(x))f(x)=pdata​(x)logD(x)＋pg​(x)log(1−D(x))，无论x取何值都能最大。其中，我们已知pdatap_datapd​ata是固定的，之前我们也假定生成器G固定，所以pgp_gpg​也是固定的，所以我们可以很容易地求出D以使得f(x)最大。我们假设x固定，f(x)对D(x)求导等于零，下面是求解D(x)的推导。

可以看出它是一个范围在0到1的值，这也符合我们判别器的模式，理想的判别器在接收到真实数据时应该判断为1，而对于生成数据则应该判断为0，当生成数据分布与真实数据分布非常接近的时候，应该输出的结果为1/2.

找到了D*之后，我们再来推导一下生成器G*。现在先把D*(x)代入前面的积分式子中重新表示：

到了这一步，我们需要先介绍一个定义——Jensen–Shannon散度，我们这里简称JS散度。在概率统计中，JS散度也与前面提到的KL散度一样具备了测量两个概率分布相似程度的能力，它的计算方法基于KL散度，继承了KL散度的非负性等，但有一点重要的不同，JS散度具备了对称性。JS散度的公式如下，我们还是以P和Q作为例子，另外我们设定M=12(P+Q)M=\frac{1}{2}(P+Q)M=21​(P+Q)，KL为KL散度公式。

对于上面的MaxV(G,D)MaxV(G,D)MaxV(G,D)，由于JS散度是非负的，当且仅当pdata=pgp_{data}=p_gpdata​=pg​的时候，上式可以取得全局最小值−log(4)-log(4)−log(4)。所以我们要求的最优生成器G*，正是要使得G*的分布pg=pdatap_g=p_{data}pg​=pdata​.

2. GAN的可视化理解

下面我们用一个可视化概率分布的例子来更深入地认识一下生成对抗网络。Ian Goodfellow的论中给出了这样一个GAN的可视化实现的例子：下图中的点线为真实数据分布，曲线为生成数据样本，生成对抗网络在这个例子中的目标在于，让曲线(也就是生成数据的分布)逐渐逼近点线(代表的真实数据分布)。

虚线为生成对抗网络中的判别器，它被赋予了初步区分真实数据与生成数据的能力，并对于它的划分性能加上一定的白噪声，使得模拟环境更为真实。输入域为z(图中下方的直线)在这个例子里默认为一个均匀分布的数据，生成域为x(图中上方的直线)为不均匀分布数据，通过生成函数x=G(z)形成一个映射关系，如图中的那些箭头所示，将均匀分布的数据映射成非均匀数据。

从a到d的四张图可以展现整个生成对抗网络的运作过程。在a图中，可以说是一种初始的状态，生成数据与真实数据还有比较大的差距，判别器具备初步划分是否为真实数据的能力，但是由于存在噪声，效果仍有缺陷。b图中，通过使用两类标签数据对于判别器的训练，判别器D开始逐渐向一个比较完善的方向收敛，最终呈现出图中的结果。当判别器逐渐完美后，我们开始迭代生成器G，如图c所示。通过判别器D的倒数梯度方向作为指导，我们让生成数据向真实数据的分布方向移动，让生成数据更容易被判别器判断为真实数据。在反复的一系列上述训练过程后，生成器与判别器会进入图d的最终状态，此时pgp_gpg​会非常逼近甚至完全等于pdatap_{data}pdata​，当达到理想的pg=pdatap_g=p_{data}pg​=pdata​的时候，D与G都已经无法再更进一步优化了，此时G生成的数据已经达到了我们期望的目的，能够完全模拟出真实数据的分布，而D在这个状态下已经无法分辨两种数据分布(因为它们完全相同)，此时D(x)=12D(x)=\frac{1}{2}D(x)=21​.

四、DCGAN

1. 概述

DCGAN的创始论文《Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks》(基于深层卷积生成对抗网络的无监督表示学习)发表于2015年，文章在GAN的基础之上提出了全新的DCGAN架构，该网络在训练过程中状态稳定，并可以有效实现高质量的图片生成及相关的生成模型应用。由于其具有非常强的实用性，在它之后的大量GAN模型都是基于DCGAN进行的改良版本。为了使得GAN能够很好地适应于卷积神经网络架构，DCGAN提出了四点架构设计规则，分别是：

• 使用卷积层替代池化层。首先第一点是把传统卷积网络中的池化层全部去除，使用卷积层代替。对于判别器，我们使用步长卷积(strided convolution)来代替池化层；对于生成器，我们使用分数步长卷积(fractional-strided convolutions)来代替池化层。
• 去除全连接层。目前的研究趋势中我们会发现非常多的研究都在试图去除全连接层，常规的卷积神经网络往往会在卷积层后添加全连接层用以输出最终向量，但我们知道全连接层的缺点在于参数过多，当神经网络层数深了以后运算速度会变得非常慢，此外全连接层也会使得网络容易过度拟合。有研究使用了全局平均池化(global average pooling)来替代全连接层，可以使得模型更稳定，但也影响了收敛速度。论文中说的一种折中方案是将生成器的随机输入直接与卷积层特征输入进行连接，同样地对于判别器的输出层也是与卷积层的输出特征连接，具体的操作会在后面的框架结构介绍中说明。
• 使用批归一化(batch normalization)。由于深度学习的神经网络层数很多，每一层都会使得输出数据的分布发生变化，随着层数的增加网络的整体偏差会越来越大。批归一化的目标则是为了解决这一问题，通过对每一层的输入进行归一化处理，能够有效使得数据服从某个固定的数据分布。
• 使用恰当的激活函数。在DCGAN网络框架中，生成器和判别器使用了不同的激活函数来设计。生成器中使用ReLU函数，但对于输出层使用了Tanh激活函数，因为研究者们在实验中观察到使用有边界的激活函数可以让模型更快地进行学习，并能快速覆盖色彩空间。而在判别器中对所有层均使用LeakyReLU，在实际使用中尤其适用于高分辨率的图像判别模型。这些激活函数的选择是研究者在多次实验测试中得出的结论，可以有效使得DCGAN得到最优的结果。

2. 网络结构

下图是DCGAN生成器G的架构图，输入数据为100维的随机数据z，服从范围在[-1，1]的均匀分布，经过一系列分数步长卷积后，最后形成一幅64×64×3的RGB图片，与训练图片大小一致。

对于判别器D的架构，基本是生成器G的反向操作，如下图所示。输入层为64×64×3的图像数据，经过一系列卷积层降低数据的维度，最终输出的是一个二分类数据。

3. 训练细节

1)对于用于训练的图像数据样本，仅将数据缩放到[-1，1]的范围内，这个也是tanh的取值范围，并不做任何其他处理。

2)模型均采用Mini-Batch大小为128的批量随机梯度下降方法进行训练。权重的初始化使用满足均值为0、方差为0.02的高斯分布的随机变量。

3)对于激活函数LeakyReLU，其中Leak的部分设置斜率为0.2。

4)训练过程中使用Adam优化器进行超参数调优。学习率使用0.0002，动量β1取0.5，使得训练更加稳定。

五、实现DCGAN

1. 任务目标

实现DCGAN，并利用其合成卡通人物头像。

2. 数据集

样本内容：卡通人物头像

样本数量：51223个

3. 实验结果

为了加快训练速度，实际只采用了8903个样本进行训练，执行每20轮一次增量训练。实验结果如下：

• 1轮训练

• 5轮训练

• 10轮训练

• 20轮训练

• 40轮训练

• 60轮训练

六、其它GAN模型

1)文本生成图像：GAWWN

2)匹配数据图像转换：Pix2Pix

3)非匹配数据图像转换：CycleGAN，用于实现两个领域图片互转

4)多领域图像转换：StarGAN

七、参考资源

1. 在线视频

1)李宏毅GAN教程：https://www.ixigua.com/pseries/6783110584444387843/?logTag=cZwYY0OhI8vRiNppza2UW

2. 书籍

1)《生成对抗网络入门指南》，史丹青编著，机械工业出版社