文章目录

• 第一部分-基础知识
• • 概率论基础和蒙特卡洛

第一部分-基础知识

概率论基础和蒙特卡洛

概率质量函数pmf：变量的取值范围是一个离散的集合
概率密度函数pdf：连续随机变量
性质： ∫ X p ( x ) d x = 1 \int_{\mathcal{X}}p(x)dx = 1 ∫X​p(x)dx=1

离散概率分布， f ( x ) f(x) f(x)的期望是 E X ∼ p ( x ) [ f ( x ) ] = ∑ x ∈ X p ( x ) ⋅ f ( x ) E_{X\sim p(x)}[f(x)] = \sum_{x \in \mathcal{X}}p(x) \cdot f(x) EX∼p(x)​[f(x)]=∑x∈X​p(x)⋅f(x)
连续概率分布， f ( x ) f(x) f(x)的期望是 E X ∼ p ( x ) [ f ( x ) ] = ∫ X p ( x ) f ( x ) d x E_{X\sim p(x)}[f(x)] = \int_{ \mathcal{X}} p(x)f(x)dx EX∼p(x)​[f(x)]=∫X​p(x)f(x)dx

蒙特卡洛/monte carlo
求一元函数定积分 I = ∫ a b f ( x ) d x I = \int_a^b f(x)dx I=∫ab​f(x)dx

1. 在区间[a, b]上做随机抽样，得到n个样本，记作： x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1​,x2​,…,xn​
2. 计算 I ≈ q n = ( b − a ) ⋅ 1 n ∑ i = 1 n f ( x i ) I \approx q_n = (b - a) \cdot \frac{1}{n}\sum_{i = 1}^nf(x_i) I≈qn​=(b−a)⋅n1​∑i=1n​f(xi​)

求多元函数定积分 I = ∫ Ω f ( x ) d x I = \int_\Omega f(\bold{x})d\bold{x} I=∫Ω​f(x)dx，其中 x \bold{x} x是d维向量

1. 在集合 Ω \Omega Ω上做均匀随机抽样，得到n个样本，记作： x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1​,x2​,…,xn​
2. 计算集合 Ω \Omega Ω的体积： v = ∫ Ω d x v = \int_\Omega dx v=∫Ω​dx
3. 计算 I ≈ q n = v ⋅ 1 n ∑ i = 1 n f ( x i ) I \approx q_n = v \cdot \frac{1}{n}\sum_{i = 1}^nf(x_i) I≈qn​=v⋅n1​∑i=1n​f(xi​)

上面求积分，都是做了均匀抽样，改用非均匀抽样，可以更快收敛，即：
求多元函数定积分 I = ∫ Ω f ( x ) d x I = \int_\Omega f(\bold{x})d\bold{x} I=∫Ω​f(x)dx，其中 x \bold{x} x是d维向量

1. 按概率密度函数 p ( x ) p(x) p(x)在集合 Ω \Omega Ω上做非均匀随机抽样，得到n个样本，记作： x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1​,x2​,…,xn​
2. 计算 I ≈ q n = 1 n ∑ i = 1 n f ( x i ) I \approx q_n = \frac{1}{n}\sum_{i = 1}^nf(x_i) I≈qn​=n1​∑i=1n​f(xi​)

tricks
按照上面的做法，需要保存所有 f ( x ) f(x) f(x)，比较废内存，更节省的方法（robbins-monro）如下：
初始化 q 0 = 0 q_0 = 0 q0​=0，从t = 1到n，依次计算：
q t = ( 1 − 1 t ) ⋅ q t − 1 + 1 t ⋅ f ( t ) (1) \tag{1} q_t = (1 - \frac{1}{t}) \cdot q_{t - 1} + \frac{1}{t} \cdot f(t) qt​=(1−t1​)⋅qt−1​+t1​⋅f(t)(1)
可以证明 q n = 1 n ∑ i = 1 n f ( x i ) q_n = \frac{1}{n}\sum_{i = 1}^nf(x_i) qn​=n1​∑i=1n​f(xi​)
把 ( 1 ) (1) (1)中的 1 t \frac{1}{t} t1​替换成 α t \alpha_t αt​，有：
q t = ( 1 − α t ) ⋅ q t − 1 + α t ⋅ f ( t ) q_t = (1 - \alpha_t) \cdot q_{t - 1} + \alpha_t \cdot f(t) qt​=(1−αt​)⋅qt−1​+αt​⋅f(t)
α t \alpha_t αt​需要满足

1. lim ⁡ n → ∞ ∑ t = 1 n α t = 0 \lim_{n \to \infty} \sum_{t=1}^n \alpha_t = 0 limn→∞​∑t=1n​αt​=0
2. lim ⁡ n → ∞ ∑ t = 1 n α t 2 < ∞ \lim_{n \to \infty} \sum_{t=1}^n \alpha_t^2 < \infty limn→∞​∑t=1n​αt2​<∞

其中 α t \alpha_t αt​也就是学习率

monte-carlo也用在随机梯度下降的batch里，实际上优化的是monte-carlo的近似梯度