25. 初识生成式对抗网络（GANs）
场景描述
2014年的一天，Goodfellow与好友相约到酒吧聊天。也许平日里工作压力太大，脑细胞已耗尽了创作的激情，在酒吧的片刻放松催生了一个绝妙的学术点子，然后就有了GANs的传说。GANs全称为生成式对抗网络，是一个训练生成模型的新框架。
GANs自提出之日起，就迅速风靡深度学习的各个角落，GANs的变种更是雨后春笋般进入人们的视野，诸如：WGAN、InfoGAN、f-GANs、BiGAN、DCGAN、IRGAN等等。
GANs之火，就连任何初入深度学习的新手都能略说一二。GANs刚提出时没有华丽的数学推演，描绘出的是一幅魅力感极强的故事画面，恰好契合了东方文化中太极图的深刻含义——万物在相生相克中演化，听起来很有意思。想象GANs框架是一幅太极图，“太极生两仪”，这里“两仪”就是生成器和判别器，生成器负责“生”，判别器负责“灭”，这一生一灭间有了万物。具体说来，生成器在初始混沌中孕育有形万物，判别器甄别过滤有形万物，扮演一种末日大审判的角色。回到严谨的学术语言上，生成器从一个先验分布中采得随机信号，经过神经网络的“妙手”转换，得到一个模拟真实数据的样本；判别器既接收来自生成器的模拟样本，也接收来自实际数据集的真实样本，我们不告诉判别器这个样本是哪里来的，需要它判断样本的来源。判别器试图区分这两类样本，生成器则试图造出迷惑判别器的模拟样本，两者自然构成一对“冤家”，置身于一种对抗的环境。然而，对抗不是目的，在对抗中让双方能力各有所长才是目的，理想情况下最终达到一种平衡，使得双方的能力以臻完美，彼此都没有了更进一步的空间。
问题描述
关于GANs，从基本理论到具体模型再到实验设计，我们依次思考三个问题：
（1）GANs可看作一个双人minimax游戏，请给出游戏的value function。我们知道在理想情况下最终会达到一个纳什均衡点，此时生成器表示为G，判别器表示为D，请给出解(G, D)和value function的值；在未达到均衡时，我们将生成器G固定，去寻找当前下最优的判别器DG，请给出DG和此时的value function。至此的答案都很容易在原论文中找到，这里进一步发问，倘若固定D，我们将G优化到底，那么解GD*和此时的value function是什么？
（2）发明GANs的初衷是为了更好地对概率生成模型作估计，我们知道在应用传统概率生成模型（如：马尔科夫场、贝叶斯网）时会涉及大量难以完成的概率推断计算，GANs是如何避开这类计算的？
（3）实验中训练GANs的过程会如描述的那么完美吗，求解的最小化目标函数
在训练中会遇到什么问题，你有什么解决方案？
解答与分析
（1）
在minimax游戏里，判别器的目标是将来自实际数据集的样本识别为真实样本，同时将来自生成器的样本识别为模拟样本。简单地看，这是一个二分类问题，损失函数自然是negative log-likelihood，也称为categorical cross-entropy loss或cross-entropy loss，即：
其中，D(x)表示判别器D预测x为真实样本的概率，p(data|x)和p(g|x)分别表示x为真实样本和模拟样本的后验概率。另外，p(x) = Psrc(s = data)P(x|data) + Psrc(s = g)P(x|g), 这里的P(x|data)即pdata(x)表示从实际数据集获取样本x的概率，P(x|g)即pg(x)表示从生成器生成样本x的概率。由于假定实际数据集的和生成器的样本各占一半，即Psrc(s = data)* =* Psrc(s = g) = 1/2，我们可以得到
因此，判别器最小化L(D)的过程可以化作最大化如下value function：
同时，作为另一方的生成器G最小化该value function，故这个minimax游戏可表示为：
我们发现在优化G的过程中，最小化value function本质是在最小化生成器样本分布pg与真实样本分布pdata的Jensen-Shannon divergence JSD(pdata||pg)。
进一步考虑最终达到的均衡点，JSD(pdata||pg)的最小值在pdata = pg取到零，故最优解G满足x = G(z)~pdata(x)，D满足D(x)≡1/2，此时value function的值为V(G, D) =﹣㏒4。
进一步，在训练时如果给定D求解当下最优的G，我们可以得到什么？
我们不妨假设G'表示前一步的生成器，给出的D是G'下的最优判别器
，即
那么，当前G的最小化目标变为
（2）
传统概率生成模型要定义一个描述概率分布的表达式P(X)，通常是一个联合概率分布的密度函数P(X1,X2,…, XN)，然后基于此表达式做最大似然估计。这个过程少不了做概率推断计算，如：计算边缘概率P(Xi)，计算条件概率P(Xi|Xj)，计算作分母的partition function等。当随机变量很多时，概率模型会变得十分复杂，做概率计算变得非常困难，即使做大量近似计算，效果常不尽人意。而GANs在刻画概率生成模型时，并不对概率密度函数P(X)直接建模，而是通过直接制造样本X，间接地体现出分布P(X)，就是说我们实际上看不到P(X)的一个表达式。那么怎么做呢？
我们知道，如果有两个随机变量Z和X，且它们之间存在某种映射关系，X = f(Z)，那么它们各自的概率分布PX(X)和PZ(Z)也存在某种映射关系。当Z, X∈R都是一维随机变量时，
当Z, X是高维随机变量时，导数变成Jacobian矩阵，为PX=* J PZ。因此，已知Z的分布，我们对随机变量之间的转换函数f直接建模，就唯一确定了X*的分布。
这样，不仅避开了大量复杂的概率计算，而且给了f更大的发挥空间，我们可以用神经网络来刻画f。我们知道，近些年神经网络领域大踏步向前发展，涌现出一批新技术来优化网络结构，除了经典的CNN和RNN结构，ReLu激活函数、Batch Normalization、Dropout等，都可以自由地添加到生成器的网络中，大大增强了生成器的表达能力。
（3）
在实际训练中，早期阶段的生成器G很差，生成的模拟样本很容易被判别器D识别，使得D回传给的G梯度非常非常小，达不到训练G的目的，这个现象称为优化饱和。为什么会出现这种现象呢？回答这个问题前，我们将判别器D的sigmoid输出层的前一层记为o，那么D(x)可表示成D(x) = sigmod(o(x))，当输入的是一个真实样本时x~pdata，当输入的是一个模拟样本时x = G(z;θg), z~pz。我们看判别器D的导数形式
训练生成器的loss项的导数形式为
此时生成器获得的导数基本为零，这说明判别器强大后对生成器的帮助反而变得微乎其微。怎么办呢？
26. 隐马尔科夫模型
场景描述
序列标注（sequence labeling）是对一个序列的每个元素给出标签的机器学习任务。序列标注模型被应用于文本处理相关领域，包括中文分词、词性标注、语义角色标注、命名实体识别、语音识别等。我们前面已经提到过用RNN等深度学习模型解决序列标注问题，接下来我们还将回顾序列标注的一系列经典模型。
问题描述
简述如何对中文分词问题用隐马尔科夫模型进行建模，给定一批语料，如何对模型进行训练。
解答与分析
背景：隐马尔科夫模型是机器学习中一个经典的生成式模型，描述了由隐状态的马尔科夫链随机生成观测状态序列的过程，常用于解决序列标注问题，在自然语言处理、语音识别等领域有广泛的应用。
在谈隐马尔科夫模型之前，先简单谈一谈马尔科夫过程。马尔科夫过程是满足无后效性的随机过程。假设一个随机过程中，tn时刻的状态xn的条件分布，仅仅与其前一个状态xn-1有关，即P(xn|x1, x2 … xn-1)＝P(xn|xn-1)，则将其称为马尔科夫过程，时间和状态的取值都是离散的马尔科夫过程也称为马尔科夫链。
隐马尔科夫模型是对含有未知参数（隐状态）的马尔科夫链进行建模的生成模型。在简单的马尔科夫模型中，所有状态对于观测者都是可见的，因此在马尔科夫模型里仅仅包括状态间的转移概率，而在隐马尔科夫模型中，隐状态xi对于观测者而言是不可见的，观测者能观测到的只有每个隐状态xi对应的输出yi，而观测状态yi的概率分布仅仅取决于对应的隐状态xi。在隐马尔科夫模型中，参数包括了隐状态间的转移概率、隐状态到观测状态的输出概率、隐状态x的取值空间、观测状态y的取值空间以及初试状态的概率分布。
下面我们用一个简单的例子来说明隐马尔科夫模型的建模过程。
假设现在我们有3个不同的葫芦，每个葫芦里有好药坏药若干，现在我们从这3个葫芦中按以下规则倒出药来：
随机挑选一个葫芦
从葫芦里倒出一颗药，记录是好药还是坏药后将药放回
从当前葫芦依照一定的概率转移到下一个葫芦
重复步骤2-3
在整个过程中，我们并不知道每次拿到的是哪一个葫芦。
用隐马尔科夫模型来描述以上过程，隐状态就是当前是哪一个葫芦，隐状态的取值空间为{葫芦1，葫芦2，葫芦3}，观测状态的取值空间为{好药，坏药}，初始状态的概率分布就是第1步随机挑选葫芦的概率分布，隐状态间的转移概率就是从当前葫芦转移到下一个葫芦的概率，而隐状态到观测状态的输出概率就是每个葫芦里好药和坏药的概率。记录下来的药的顺序就是观测状态的序列，而每次拿到的葫芦的顺序就是隐状态的序列。
隐马尔科夫模型包括三个基本问题：概率计算问题、预测问题、学习问题。
概率计算问题：已知模型的所有参数，计算观测序列Y出现的概率。概率计算问题可使用前向和后向算法求解。
预测问题：已知模型所有参数和观测序列Y，计算最可能的隐状态序列X。可使用维特比算法来求解最可能的状态序列，维特比算法是一个经典的动态规划算法。
学习问题：已知观测序列Y，求解使得该观测序列概率最大的模型参数。 使用Baum-Welch算法进行参数的学习，Baum-Welch算法是期望最大化算法（EM algorithm）的一个特例。
上面提到的问题和算法在此不多做介绍，感兴趣的读者可以查阅相关资料。下面回到我们开头的问题。隐马尔科夫模型通常用来解决序列标注问题，因此我们也可以将分词问题转化为一个序列标注问题来进行建模。
例如可以对中文句子中的每个字做以下标注：B表示一个词的开头一个字，E表示一个词的结尾一个字，M表示一个词中间的字，S表示一个单字词，则隐状态的取值空间为{B, E, M, S}，同时对隐状态的转移概率可以给出一些先验知识：B和M后面只能是M或者E，S和E后面只能是B或者S。而每个字就是模型中的观测状态，取值空间为语料中的所有中文字。
完成建模之后，使用语料进行训练可以分有监督训练和无监督训练。有监督训练即对语料进行标注，相当于得到了语料的所有隐状态信息，可以用简单的计数法来对模型进行极大似然估计。无监督训练可以用上文提到的Baum-Welch算法。
27. 自组织映射神经网络
场景描述
自组织映射算法是无监督学习方法中一类重要方法，可以用作聚类、高维可视化、数据压缩、特征提取等多种用途。在深度神经网络大为流行的今天，谈及自组织映射神经网络（Self-Organizing Map, SOM）依然是一件非常有意义的事情，这主要是由于自组织映射神经网络融入了大量人脑神经元的信号处理机制的特点。具体而言，在人脑的感知通道上，神经元的组织是有序排列的；同时，大脑皮层会对外界特定时空信息的输入在特定区域产生兴奋，而且相类似的外界信息输入产生对应兴奋的大脑皮层区域也连续映像的。此外，在生物神经系统中，还存在着一种“侧抑制”现象，这种抑制作用会使神经细胞之间出现竞争，其结果是某些获胜，而另一些则失败，表现形式是获胜神经细胞兴奋，失败神经细胞抑制。自组织神经网络就是对上述生物神经系统功能的一种人工神经网络模拟，该模型由芬兰赫尔辛基大学教授Teuvo Kohonen于1981年提出，因此有时也称为Kohonen网络。
问题描述
自组织映射神经网络是如何工作的？它有什么样的特点？
解答与分析
自组织映射算法是无监督学习方法中一类重要方法，可以用作聚类、高维可视化、数据压缩、特征提取等多种用途。在深度神经网络大为流行的今天，谈及自组织映射神经网络依然是一件非常有意义的事情，这主要是由于自组织映射神经网络融入了大量人脑神经元的信号处理机制的特点。该模型由芬兰赫尔辛基大学教授Teuvo Kohonen于1981年提出，因此有时也称为Kohonen网络。
生物学研究表明，在人脑的感知通道上，神经元组织是有序排列的；同时，大脑皮层会对外界特定时空信息的输入在特定区域产生兴奋，而且相类似的外界信息输入产生对应兴奋的大脑皮层区域也连续映像的。例如，生物视网膜中有许多特定的细胞对特定的图形比较敏感，当视网膜中有若干个接收单元同时受特定模式刺激时，就使大脑皮层中的特定神经元开始兴奋，且输入模式接近时与之对应的兴奋神经元也接近；在听觉通道上，神经元在结构排列上与频率的关系十分密切，对于某个频率，特定的神经元具有最大的响应，位置相邻的神经元具有相近的频率特征，而远离的神经元具有的频率特征差别也较大。大脑皮层中神经元的这种响应特点不是先天安排好的，而是通过后天的学习自组织形成的。
在生物神经系统中，还存在着一种侧抑制现象，即一个神经细胞兴奋以后，会对周围其它神经细胞产生抑制作用。这种抑制作用会使神经细胞之间出现竞争，其结果是某些获胜，而另一些则失败。表现形式是获胜神经细胞兴奋，失败神经细胞抑制。自组织神经网络就是对上述生物神经系统功能的一种人工神经网络模拟。
自组织映射神经网络本质上是一个两层的神经网络，包含输入层和竞争层（输出层）。输入层模拟感知外界输入信息的视网膜，输出层模拟做出响应的大脑皮层。竞争层中神经元的个数通常是聚类的个数，代表每一个需要聚成的类。训练时采用“竞争学习”的方式，每个输入的样例在竞争层中找到一个和它最匹配的节点，称为它的激活节点，也叫“winning neuron”；紧接着用随机梯度下降法更新激活节点的参数；同时，和激活节点临近的点也根据它们距离激活节点的远近而适当地更新参数。这种竞争可以通过神经元之间的横向抑制连接（负反馈路径）来实现。SOM的竞争层节点是有拓扑关系的。这个拓扑关系依据需求确定，如果想要一维的模型，那么隐藏节点可以是“一维线阵”；如果想要二维的拓扑关系，那么就行成一个“二维平面阵”，也如图（1）所示，也有更高维度的拓扑关系的，比如“三维栅格阵”，但并不常见。
图1. SOM常见的两种网络结构
自组织映射神经网络的自组织学习过程也可以归纳为以下四个子过程，其中假设输入空间是D维，输入模式为：x＝{xi, i＝1, …, D}，输入单元i和神经元j之间在计算层的连接权重为：w＝{wi,j, j＝1, …, N, i＝1, …, D}，其中N是神经元的总数：
基于自组织映射神经网络，通常会引发以下常见的几个问题：
-
SOM具有什么样的显著特点，为什么？
保序映射。SOM网络可以将任意维输入模式在输出层映射为一维或者二维图形，并保持拓扑结构不变。这种拓扑映射使得“输出层神经元的空间位置对应于输入空间的特定域或特征”。由其学习过程可以看出，每个学习权重更新的效果等同于将获胜的神经元及其邻居的权向量wi向输入向量x移动，同时对该过程的迭代进行会使得网络的拓扑有序。
-
怎样设计自组织映射神经网络并设定网络训练参数？
自组织映射神经网络设计和参数主要包括以下几个部分：
输出层神经元数量设定：和训练集样本的类别数相关。若不清楚类别数量，则尽可能先设定较多的节点数，以便较好的映射样本的拓扑结构，如果分类过细再酌情减少输出节点。这样可能会带来少量从未更新过权值的 “死节点”，但此问题一般可通过重新初始化权值得到解决。
输出层节点排列的设计：输出层的节点排列成哪种形式取决于实际应用的需要，排列形式应尽量直观反映出实际问题的物理意义。例如，对于一般的分类问题，一个输出节点节能代表一个模式类，用一维线阵意义明确结构简单；对于颜色空间或者旅行路径类的问题，二维平面则比较直观。
权值初始化问题：可以随机初始化，但尽量使权值的初始位置与输入样本的大概分布区域充分重合，避免出现大量的初始“死节点”。一种简单易行的方法是从训练集中随机抽取m个输入样本作为初始权值。
拓扑邻域的设计：拓扑领域设计原则是使领域不断缩小，这样输出平面上相邻神经元对应的权向量之间既有区别又有相当的相似性，从而保证当获胜节点对某一类模式产生最大响应时，其领域节点也能产生较大响应。领域的形状可以是正方形、六边形或者菱形。优势领域的大小用领域的半径表示，通常凭借经验来选择。
学习率的设计：学习率是一个递减的函数，可以结合拓扑邻域的更新一起考虑，也可分开。在训练开始时，学习率可以选取较大的值，之后以较快的速度下降，这样有利于很快捕捉到输入向量的大致结构，然后学习率在较小的值上缓降至0值，这样可以精细地调整权值使之符合输入空间的样本分布结构。
-
自组织映射神经网络中的竞争学习是怎样实现的？
网络的竞争层各神经元竞争对输入模式的响应机会，获胜的神经元将使得相关的各权重向更加有利于它竞争的方向调整，即以获胜神经元为中心，对近邻的神经元表现出兴奋性侧反馈，而对远邻的神经元表现出抑制性侧反馈，近邻者互相激励，远邻者相互抑制。近邻和远邻均有一定的范围，对更远邻的神经元则表现弱激励的作用。这种交互作用的方式以曲线可视化则类似于“墨西哥帽”，如图2所示。
图2. 神经元的激励交互方式
-
SOM对比K-means有何不同点？
（1）K-Means需要事先定下类的个数，也就是K的值； SOM则不用，隐藏层中的某些节点可以没有任何输入数据属于它。所以，K-Means受初始化的影响要比较大。
（2）K-means为每个输入数据找到一个最相似的类后，只更新这个类的参数；SOM则会更新临近的节点。所以，K-mean受noise data的影响比较大，SOM的准确性可能会比k-means低（因为也更新了临近节点）；
（3） SOM的可视化比较好，具有优雅的拓扑关系图。
28. 概率图模型
场景描述
概率图模型（Probabilistic Graphical Model）主要分为两种（如图1所示），即贝叶斯网络（Bayesian Network）和马尔可夫网络（Markov Network）；其中贝叶斯概率图模型可以用一个有向图结构表示，马尔可夫概率图模型可以表示成一个无向图的网络结构。概率图模型适用于对实体间的依赖关系进行建模，有向边用来建模单向的依赖，无向边用来建模双方的相互依赖关系。概率图模型包括朴素贝叶斯模型、最大熵模型、隐马尔可夫模型、条件随机场、主题模型等，在诸多机器学习场景中有着广泛的应用。
图1
问题描述
能否写出图1中贝叶斯网络的联合概率分布？
写出图1所示的马尔可夫网络的联合概率分布。
解释朴素贝叶斯模型的原理，并给出概率图模型表示。
解释最大熵模型的原理，并给出概率图模型表示。
知识点：概率图、贝叶斯网络、马尔可夫网络
解答与分析
1. 能否写出图1中贝叶斯网络的联合概率分布？
如图所示的贝叶斯网络中，在给定A的条件下B和C是条件独立的，因此：
在给定B和C的条件下A和D是条件独立的，因此：
于是有：
2. 写出图1所示的马尔可夫网络的联合概率分布。
在马尔可夫网络中，联合概率分布的定义为：
对于图中所有节点x＝{x1, x2, …, xn}所构成的一个子集，如果在这个子集中，任意两点之间都存在边相联，则这个子集中的所有节点构成了一个团。如果在这个子集中加入任意其他节点，都不能构成一个团，则称这样的子集构成了一个最大团。
在图1所示的网络结构中，我们可以看到（A，B），（A，C），（B，D），（C，D）构成团，同时也是最大团。因此联合概率分布可以表示如下：
如果采用如上定义的指数函数作为势函数，则有：
3. 解释朴素贝叶斯模型的原理，并给出概率图模型表示。
朴素贝叶斯模型通过预测指定样本属于特定类别的概率P(yi|x)来预测该样本的所属类别。
P(yi|x)可以写成如下的形式：
其中x＝(x1, x2, …, xn)为样本对应的特征向量，P(x)为样本的先验概率。对于特定的样本x和任意类别yi，P(x)的取值均相同，并不会影响P(yi|x)取值的相对大小，因此在计算中可以被忽略。并且假设特征x1, x2, …, xn相互独立，可以得到：
其中P(x1|yi), P(x2|yi), …, P(xn|yi)，以及P(yi)可以通过训练样本统计得到。可以看到后验概率P(xj|yi)的取值决定了分类的结果，并且任意特征xj都由yi的取值所影响。因此概率图模型可以用下图表示：
注：上图的表示为盘式记法。盘式记法是一种简洁的概率图模型表示方法，如果变量y同时对x1, x2, …,xN这N个变量产生影响，则可以简记成如图的形式。
4. 解释最大熵模型的原理，并给出概率图模型表示。
信息是指人们对事物理解的不确定性的降低或消除，而熵就是这种不确定性的度量，熵越大，不确定性也就越大。最大熵原理是概率模型学习的一个准则，指导思想是在满足约束条件的模型集合中选取熵最大的模型，即不确定性最大的模型。在平时生活中，我们也会有意无意地使用最大熵的准则，例如人们常说的鸡蛋不能放在一个篮子里，就是指在事情具有不确定性的时候，我们倾向于尝试它的多种可能性，从而降低结果的风险。同时，在我们摸清了事情背后的某种规律之后，我们可以加入一个约束，将不符合规律约束的情况排除，在剩下的可能性中去寻找使得熵最大的决策。
假设离散随机变量X的分布是P(X)，则关于分布P的熵定义为：
可以看出当X服从均匀分布时对应的熵最大，也就是不确定性最高。
给定离散随机变量X和Y上的条件概率分布P(Y|X)，定义在条件概率分布上的条件熵为：
为样本在训练数据集上的经验分布，即X的各个取值在样本中出现的频率统计。
最大熵模型就是要学习到合适的分布P(Y|X)，使得条件熵H(P)的取值最大。在我们对训练数据集一无所知的情况下，最大熵模型认为P(Y|X)是符合均匀分布的。那么当我们有了训练数据集之后呢？我们希望从中找到一些规律，从而消除一些不确定性，这时就需要用到特征函数f(x,y)。特征函数f描述了输入x和输出y之间的一个规律，例如当x=y时，f(x,y)等于一个比较大的正数。为了使学习到的模型P(Y|X)能够正确捕捉训练数据集中的这一规律（特征），我们加入一个约束，使得特征函数f(x,y)关于经验分布的期望值相等，即
求解之后可以得到最大熵模型的表达形式：
最终，最大熵模型归结为学习最佳的参数w，使得Pw(y|x)最大化。从概率图模型的角度理解，我们可以看到Pw(y|x)的表达形式非常类似于势函数为指数函数的马尔可夫网络，其中变量X和Y构成了一个最大团，如下图所示：
29. WGANs：抓住低维的幽灵
场景描述
看过《三体3》的朋友，一定听说过“降维打击”这个概念，像拍苍蝇一样把敌人拍扁。其实，低维不见得一点好处都没有。想象猫和老鼠这部动画的一个镜头，老鼠Jerry被它的劲敌Tom猫一路追赶，突然Jerry发现墙上挂了很多照片，其中一张的背景是海边浴场，沙滩上有密密麻麻的很多人，Jerry一下子跳了进去，混在人群中消失了，Tom怎么也找不到Jerry。 三维的Jerry变成了一个二维的Jerry，躲过了Tom。一个新的问题是：Jerry对于原三维世界来说是否还存在？ 极限情况下，如果这张照片足够薄，没有厚度，那么它就在一个二维平面里，不占任何体积，体积为零的东西不就等于没有吗！拓展到高维空间中，这个体积叫测度，无论N维空间的N有多大，在N+1维空间中测度就是零，就像二维平面在三维空间中一样。因此，一个低维空间的物体，在高维空间中忽略不计。对生活在高维世界的人来说，低维空间是那么无足轻重，像一层纱，如一个幽灵，似有似无，是一个隐去的世界。
2017年，一个训练生成对抗网络的新方法——WGAN被提出。在此之前，GANs已提出三年，吸引了很多研究者来使用它。原理上，大家都觉得GANs的思路实在太巧妙，理解起来一点都不复杂，很符合人们的直觉，万物不都是在相互制约和对抗中逐渐演化升级吗。理论上，Goodfellow在2014年提出GANs时，已经给出GANs的最优性证明，证明GANs本质上是在最小化生成分布与真实数据分布的Jensen-Shannon Divergence，当算法收敛时生成器刻画的分布就是真实数据的分布。但是，实际使用中发现很多解释不清的问题，生成器的训练会很不稳定。生成器这只Tom猫，很难抓住真实数据分布这只老鼠Jerry。
问题描述
请思考：原GANs中存在哪些问题，会成为制约模型训练效果的瓶颈；WGAN针对这些问题做了哪些改进； WGAN算法的具体步骤；并写出WGAN的伪代码。
知识点：JS距离、坍缩模式、Wasserstein距离、
1-Lipschitz函数
解答与分析
1. GANs的陷阱：请回答原GANs中存在哪些问题，成为了制约模型训练效果的瓶颈。
难度：★★★
GANs的判别器试图区分真实样本和生成的模拟样本。Goodfellow在论文中指出，训练判别器，实际是在度量生成器分布和真实数据分布的Jensen-Shannon Divergence，也称JS距离； 训练生成器，是在减小这个JS距离。这是我们想要的，即使我们不清楚形成真实数据的背后机制，还是可以用一个模拟生成过程去替代之，只要它们的数据分布一致。
但是实验中发现，训练好生成器是一件很困难的事，生成器很不稳定，常出现坍缩模式(Collapse Mode)。什么是坍缩模式？拿图片举例，反复生成一些相近或相同的图片，多样化太差。生成器似乎将图片记下，没有更高级的泛化，更没有造新图的能力，好比一个笨小孩被填鸭灌输了知识，只会死记硬背，没有真正理解，不会活学活用，更无创新能力。
为什么会这样？既然训练生成器基于JS距离，猜测问题根源可能与JS距离有关。高维空间中不是每点都能表达一个样本（如一张图片），空间大部分是多余的，真实数据蜷缩在低维子空间的流形（即高维曲面）上，因为维度低，所占空间体积几乎为零，就像一张极其薄的纸飘在三维空间，不仔细看很难发现。考虑生成器分布与真实数据分布的JS距离，即两个Kullback-Leibler (KL)距离的平均
初始的生成器，由于参数随机初始化，与其说是一个样本生成器，不如说是高维空间点的生成器，点广泛分布在高维空间中。打个比方，生成器将一张大网布满整个空间，“兵力”有限，网布得越大，每个点附近的兵力就越少。想象一下，当这张网穿过低维子空间时，所剩的“兵”几乎为零，成了一个“盲区”，如果真实数据全都分布在这，就对生成器“隐身”了，成了“漏网之鱼”。
回到公式，看第一个KL距离：
高维空间绝大部分见不到真实数据，处处为零，对KL距离的贡献为零；即使在真实数据蜷缩的低维空间，高维空间会忽略低维空间的体积，概率上讲测度为零。KL距离就成了：∫ ㏒2·pr(x)dμ(x)＝㏒2。
再看第二个KL距离：
同理KL距离也为：∫ ㏒2·pg(x)dμ(x)＝㏒2。因此，JS距离为㏒2，一个常量。无论生成器怎么“布网”，怎么训练，JS距离不变，对生成器的梯度为零。训练神经网络是基于梯度下降的，用梯度一次次更新模型参数，如果梯度总是零，训练还怎么进行。
2. 破解陷阱的武器：请回答WGAN针对前面问题做了哪些改进，以及什么是Wasserstein距离。
难度：★★★★
直觉告诉我们：不要让生成器傻傻地在高维空间布网，让它直接到低维空间“抓”真实数据。道理是这样，但是高维空间中藏着无数的低维子空间，怎么找到目标子空间呢？站在大厦顶层，环眺四周，你可以迅速定位远处的山峦和高塔，却很难知晓一个个楼宇间办公室里的事情。你需要线索，而不是简单撒网。处在高维空间，对抗隐秘的低维空间，不能再用粗暴简陋的方法，需要有特殊武器，这就是Wasserstein距离，也称推土机距离（Earth Mover distance）：
怎么理解这个公式？想象你有一个很大的院子，院子里几处坑坑洼洼需要填平，四个墙角都有一堆沙子， 沙子总量正好填平所有坑。搬运沙子很费力，你想知道有没有一种方案，使得花的力气最少。直觉上，每个坑都选择最近的沙堆，搬运的距离最短，但是这里面有个问题，如果最近的沙堆用完了怎么办，或者填完坑后近处还剩好多沙子，或者坑到几个沙堆的距离一样，我们需要设计一个系统的方案，通盘考虑这些问题。最佳方案是上面目标函数的最优解。可以看到，沙子分布给定，坑分布给定，我们关心搬运沙子的整体损耗，而不关心每粒沙子的具体摆放，在损耗不变的情况下，沙子摆放可能有很多选择。对应上面的公式，当你选择一对(x, y)时，表示把x处的一些沙子搬到y处的坑，可能搬部分沙子，也可能搬全部沙子，可能只把坑填一部分，也可能都填满了。
为什么Wasserstein距离能克服JS距离解决不了的问题？理论上的解释很复杂，要证明当生成器分布随参数θ变化而连续变化时，生成器分布与真实分布的Wasserstein距离，也随θ变化而连续变化，并且几乎处处可导，而JS距离不保证随θ变化而连续变化。
通俗的解释，接着“布网”的比喻，现在生成器不再“布网”，改成“定位追踪”了，不管真实分布藏在哪个低维子空间里，生成器都能感知它在哪，因为生成器只要将自身分布稍作变化，就会改变它到真实分布的推土机距离，而JS距离是不敏感的，无论生成器怎么变化，JS距离都是一个常数。因此，使用推土机距离，能有效锁定低维子空间中的真实数据分布。
3. WGAN之道：请回答怎样具体应用Wasserstein距离实现WGAN算法。
难度：★★★★★
一群大小老鼠开会，得出结论：如果在猫脖上系一铃铛，每次它靠近时都能被及时发现，那多好！唯一的问题是：谁来系这个铃铛？现在，我们知道了推土机距离这款武器，那么怎么计算这个距离？推土机距离的公式太难求解。幸运的是，它有一个孪生兄弟，和它有相同的值，这就是Wasserstein距离的对偶式：
细心的你会发现，这里的f与D不同，前者要满足||f||L≤1，即1-Lipschitz函数，后者是一个Sigmoid函数。要求在寻找最优函数时，一定要考虑个“界”，如果没有限制，函数值会无限大或无限小。Sigmoid函数的值有天然的界，而1-Lipschitz不是限制函数值的界，而是限制函数导数的界，使得函数在每点上的变化率不能无限大。神经网络里如何体现1-Lipschitz或K-Lipschitz呢？WGAN的作者思路很巧妙，在一个前向神经网络里，输入经过多次线性变换和非线性激活函数得到输出，输出对输入的梯度，绝大部分都是由线性操作所乘的权重矩阵贡献的，因此约束每个权重矩阵的大小，可以约束网络输出对输入的梯度大小。
判别器在这里换了一个名字，叫评分器(Critic)，目标函数由区分样本来源，变成为样本打分，越像真实样本分数越高，否则越低，有点类似SVM里margin的概念。打个龟兔赛跑的比方，评分器是兔子，生成器是乌龟，评分器的目标是甩掉乌龟，让二者的距离（或margin）越来越大，生成器的目标是追上兔子。严肃一点讲，训练评分器就是计算生成器分布与真实分布的Wasserstein距离；给定评分器，训练生成器就是在缩小这个距离。因此，算法中要计算Wasserstein距离对生成器参数θ的梯度，
再通过梯度下降法更新参数，让Wasserstein距离变小。
扩展阅读：
1. Martin Arjovsky, Soumith Chintala, Léon Bottou, Wasserstein GAN, 2017
2. Martin Arjovsky, Léon Bottou, Towards Principled Methods for Training Generative Adversarial Networks, 2017
30. 常见的采样方法
场景描述
对于一个随机变量，我们通常用概率密度函数来刻画该变量的概率分布特性。具体来说，给定随机变量的一个取值，我们可以根据概率密度函数来计算该值对应的概率（密度）；反过来，也可以根据概率密度函数提供的概率分布信息来生成随机变量的一个取值，这就是采样。因此，从某种意义上来说，采样是概率密度函数的逆向应用。与根据概率密度函数计算样本点对应的概率值不同，采样过程（即根据概率分布来选取样本点）往往没有那么直接，通常需要依据待采样分布的具体特点来选择合适的采样策略 。 在“采样”章节的前两个小问题中，我们展示了采样的一个具体应用（不均衡样本集的处理），以及针对特定分布（高斯分布）而特别设计的采样方法；接下来，我们来关注一些通用的采样方法和采样策略。
问题描述
抛开那些针对特定分布而精心设计的采样方法外，说一些你所知道的通用采样方法或采样策略，简单描述它们的主要思想以及具体操作步骤。
背景知识：概率与统计、采样
解答与分析
在之前采样章节的推送中我们提到，几乎所有的采样方法都是以均匀分布的采样作为基本操作。均匀分布随机数一般用线性同余法来产生（伪随机数），这里不再赘述，我们假设已经可以生成 [0,1] 上的均匀分布随机数。
对于一些简单的分布，可以直接用基于均匀采样的方法来产生样本点（如有限离散分布可以用轮盘赌算法来采样）；然而，很多分布一般不好直接进行采样，此时可以考虑函数变换法。一般地，如果随机变量x和u存在变换关系u＝φ(x)，则它们的概率密度函数有如下关系：p(u)|φ'(x)|＝p(x)。因此，如果从目标分布p(x)中不好采样x，可以构造一个变换u＝φ(x)，使得从变换后的分布p(u)中采样u比较容易，这样可以通过先对u进行采样然后通过反函数x＝φ-1(u)来间接得到x。如果是高维空间的随机向量，则上述|φ'(x)|对应Jacobian行列式。
特别地，在上述函数变换法中，如果变换关系φ(·)是累积分布函数的话，则得到所谓的逆变换采样法**** (Inverse Transform Sampling)：假设待采样的目标分布的概率密度函数为p(x)，它的累积分布函数为
按如下过程进行采样：
根据函数变换法，上述采样过程得到的xi服从p(x)分布。图1是逆变换采样法的示意图。
图1 逆变换采样法示意图
如果待采样的目标分布的累积分布函数的逆函数无法求解或者不容易计算，则不适用于逆变换采样法。此时可以构造一个容易采样的参考分布，先对参考分布进行采样，然后对得到的样本进行一定的后处理操作，使得最终的样本服从目标分布。常见的拒绝采样、重要性采样，就属于这类采样算法，下面分别简单介绍它们的具体采样过程。
拒绝采样 (Rejection sampling)，又叫接受/拒绝采样 (Accept-Reject Sampling)。对于目标分布p(x)，选取一个容易采样的参考分布q(x)，使得p(x)≤M·q(x)，则可以按如下过程进行采样：
通过简单的推导，可以知道最终得到的xi服从目标分布p(x)。如图2(A)所示，拒绝采样法的关键是为目标分布p(x)选取一个合适的包络函数M·q(x)：包络函数越紧，每次采样时样本被接受的概率越大，采样效率越高。在实际应用中，有时候寻找解析形式的q(x)比较困难，因此延伸出了自适应拒绝采样 (Adaptive Rejection Sampling)，在目标分布是对数凹函数时，用分段线性函数来覆盖目标分布的对数㏑p(x)，如图2(B)所示，这里不再细述。
图2 (A) 拒绝采样示意图；(B) 自适应拒绝采样法
重要性采样 (Importance Sampling)，其实是用于计算函数f(x)在目标分布p(x)上的积分，即
这里w(x)可以看成是样本x的重要性权重。由此，可以先从参考q(x)分布中抽取N个样本{xi}，然后利用如下公式来估计I[f]：
如果不需要计算函数积分，只想对目标分布p(x)进行采样，则可以用重要性重采样 (Sampling-Importance Re-sampling, SIR)，即在从参考分布q(x)抽取N个样本{xi}后，按照它们对应的重要性权重{w(xi)}对这些样本进行重新采样（这是一个简单的针对有限离散分布的采样），最终得到的样本服从目标分布p(x)。
图3 重要性采样示意图
在实际应用中，如果是高维空间的随机向量，拒绝采样/重要性重采样经常难以寻找合适的参考分布，采样效率低下（样本的接受概率小或重要性权重低），此时可以考虑马尔科夫蒙特卡洛采样法 (Markov Chain Monte Carlo, MCMC) 。MCMC基本思想是：针对待采样的目标分布，构造一个马尔科夫链，使得该马尔科夫链是收敛的，并且最终的稳态分布就是我们要采样的目标分布。实际操作中，核心点是构造合适的马尔科夫链，不同的马尔科夫链对应着不同的MCMC算法，常见的有Metropolis-Hastings算法和Gibbs算法。在后续的微信推送中，我们会有专门针对MCMC的问答小节，这里只简单介绍Metropolis-Hastings算法和Gibbs算法的具体操作步骤。
Metropolis-Hastings (MH) 采样：对于目标分布p(x)，首先选择一个容易采样的参考条件分布q(x|x*)，并令
然后根据如下过程进行采样：
可以证明，上述过程得到的样本序列{…, x(t-1), x(t), …}最终会收敛到目标分布p(x)。
Gibbs采样：Gibbs采样的核心思想是每次只对样本的一个维度进行采样和更新。对于目标分布p(x)，其中x＝(x1,* x*2,…, xd)是高维向量，按如下过程进行采样：
同样可以证明，上述过程得到的样本序列{…, x(t-1), x(t), …}会收敛到目标分布p(x)。另外，步骤2中对样本每个维度的抽样和更新操作，不是必须按下标顺序进行的，可以是随机顺序 。
扩展与总结
上述解答中我们只是列举了几个最常用的采样算法，简单介绍了它们的具体操作。在实际面试时，可以让面试者选择其最熟悉的某个采样算法来回答，展开来问一下该算法的理论证明、优缺点，以及相关扩展等。
