文章目录
第一部分-基础知识
概率论基础和蒙特卡洛
概率质量函数pmf：变量的取值范围是一个离散的集合
概率密度函数pdf：连续随机变量
性质：
∫
X
p
(
x
)
d
x
=
1
\int_{\mathcal{X}}p(x)dx = 1
∫Xp(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∈Xp(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)]=∫Xp(x)f(x)dx
蒙特卡洛/monte carlo
求一元函数定积分
I
=
∫
a
b
f
(
x
)
d
x
I = \int_a^b f(x)dx
I=∫abf(x)dx
- 在区间
[a, b]上做随机抽样，得到n个样本，记作： x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1,x2,…,xn - 计算 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=1nf(xi)
求多元函数定积分
I
=
∫
Ω
f
(
x
)
d
x
I = \int_\Omega f(\bold{x})d\bold{x}
I=∫Ωf(x)dx，其中
x
\bold{x}
x是d维向量
- 在集合
Ω
\Omega
Ω上做均匀随机抽样，得到
n个样本，记作： x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1,x2,…,xn - 计算集合 Ω \Omega Ω的体积： v = ∫ Ω d x v = \int_\Omega dx v=∫Ωdx
- 计算 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=1nf(xi)
上面求积分，都是做了均匀抽样，改用非均匀抽样，可以更快收敛，即：
求多元函数定积分
I
=
∫
Ω
f
(
x
)
d
x
I = \int_\Omega f(\bold{x})d\bold{x}
I=∫Ωf(x)dx，其中
x
\bold{x}
x是d维向量
- 按概率密度函数
p
(
x
)
p(x)
p(x)在集合
Ω
\Omega
Ω上做非均匀随机抽样，得到
n个样本，记作： x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1,x2,…,xn - 计算 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=1nf(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=1nf(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需要满足
- lim n → ∞ ∑ t = 1 n α t = 0 \lim_{n \to \infty} \sum_{t=1}^n \alpha_t = 0 limn→∞∑t=1nαt=0
- 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的近似梯度