#####Q1: 采样在机器学习中的应用？
A1: 采样本质是对随机现象的模拟，即根据给定的概率分布，模拟产生对应的随机事件。
采样也可以看作是一种非参数模型，即用较少量的样本点来近似总体分布，并刻画分布中的不确定性。这个角度考虑，也可以当作一种信息降维。
常见的如自助法和刀切法(Jack knife)，通过对样本的多次重采样来估计统计量的偏差、方差等信息。重采样来处理分类模型的训练样本不均衡问题。
此外，很多模型由于结构复杂、含有隐变量等原因，没有显示的解析解，可以利用采样方法进行随机模拟，对复杂模型进行近似求解或推理。例如，在隐狄利克雷模型和深度玻尔兹曼机(Deep Boltzmann Machines, DBM)的求解过程中，可以采用吉布斯采样来简化求解过程。
######Q1-1: 如何用自助法或刀切法来估计偏差、方差？
A1-1[1]:
Bootstrap自助法
有两种形式：非参数bootstrap和参数化的bootstrap，但基本思想都是模拟。 1)参数化的bootstrap假设总体的分布已知或总体的分布形式已知，可以由样本估计出分布参数，再从参数化的分布中进行再采样，类似于MC。 2)非参数化的bootstrap是从样本中再抽样，而不是从分布函数中进行再抽样。
自助法估计偏差、方差的基本步骤如下[2]： （1）采用重抽样技术从原始样本中抽取一定数量（自己给定）的样本，此过程允许重复抽样。 （2）根据抽出的样本计算给定的统计量T。 （3）重复上述B次（一般大于1000），得到N个统计量T。 （4）计算上述B个统计量T的样本方差，得到统计量的方差。
举个例子：
- 背景。比如要算一个统计量T，它是是一个从样本（X1,X2,X3……Xn）得来的函数，比如中位数，就是从（X1,X2,X3……Xn）中取中间的那个数，计算过程写成函数T0=T(X1,X2,X3……Xn)
-
做法。根据一次样本（X1,X2,X3……Xn）我们只能得到一个T的值，然后就是关键步骤了，在{X1,X2,X3……Xn}这个集合中有放回的抽取N个元素出来，这N个元素（可能出现两次X1）重新做为样本，计算一次T，把这个结果记为T1，这样重复抽取B次，我们就算了B个T出来。
- 结论。这B个T的方差，就是统计量T的方差的估计。
- 补充。这个方差有什么用，比如可以用正态构建95%的置信区间（T0+1.96*方差）
刀切法
Jackknife(刀切法)是有Maurice Quenouille (1949)提出的一种再抽样方法，其原始动机是降低估计的偏差。Jackknife类似于“Leave one out”的交叉验证方法。令X=(X1,X2,…,Xn)为观测到的样本，定义第i个Jackknife样本为丢掉第i个样本后的剩余样本即
由此生成的Jackknife样本集之间的差异很小，每两个Jackknife样本中只有两个单个的原始样本不同。
Jackknife不适合的场合
统计函数不是平滑函数：数据小的变化会带来统计量的一个大的变化如极值、中值。如对数据X=(10,27,31,40,46,50,52,104,146)的中值得到的结果为48,48,48,48,45,43,43,43,43,偶数个数的中值为最中间两个数的平均值。
Jackknife与Bootstrap自助法的联系
首先，自助法通过经验分布函数构建了自助法世界，将不适定的估计概率分布的问题转化为从给定样本集中重采样。第二，自助法可以解决不光滑参数的问题。遇到不光滑(Smooth)参数估计时，刀切法会失效，而自助法可以有效地给出中位数的估计。第三，将自助法估计用泰勒公式展开，可以得到刀切法是自助法方法的一阶近似。第四，对于线性统计量的估计方差这个问题，刀切法或者自助法会得到同样的结果。但在非线性统计量的方差估计问题上，刀切法严重依赖于统计量线性的拟合程度，所以远不如自助法有效。
######Q1-2: 在隐狄利克雷模型和深度玻尔兹曼机中，具体如何用吉布斯采样求解？
######Q1-3: 进行模型求解时，马尔可夫蒙特卡洛采样法与常见的最大期望算法、变分推断法有什么联系和区别？
Q2: 如何编程实现均匀分布的随机数生成器？
A2: 首先，计算机只能产生伪随机数（伪随机是指这些数字虽然是通过确定性的程序产生的，但是它们能通过近似的随机性测试）。其次，计算机只能产生离散的均匀分布（因为计算机的存储和计算单元只能处理离散状态值），然后通过离散分布来逼近连续分布。
一般用线性同余法(Linear Congruential Generator)来生成离散均匀分布伪随机数，计算公式为
\(x_{t+1} = a \cdot x_t + c (\mod m) \tag{1}\),
产生区间$[0, m-1]$上的随机整数。但是，上式得到的随机数显然不是相互独立的。事实上，该算法需要$a$和$m$的精心选择才能使循环周期尽可能接近$m$。具体实现中，比如gcc采用的glibc版本：$m = 2^{31}-1, a = 1103515245, c = 12345$。
Q2-1: 线性同余法的随机种子($x_0$)一般如何选定？
Q2-2: 如果需要产生高维样本或大量样本，线性同余法存在什么问题？
Q2-3: 如何证明上述得到的序列可以近似为均匀分布?
Q3: 通用的采样方法或采样策略？
Reference
[1] https://www.jianshu.com/p/7ce411e3c377
