Belief propagation
一个图模型包含 $N$ 个随机变量 $\underline{x}=(x_1,\dots,x_N)$，从有限字母表 $\mathcal{X}$ 中取值. 需要解决一些问题，例如：
- 给定一些条件，求另一些变量的边缘分布；
- 一些后验估计相关
但是我们不会去直接计算联合分布 $p(\underline{x})$，因为它的状态空间是指数级别 $|\mathcal{X}|^N$ 个取值. BP 将这个问题转化为局部计算，利用图的稀疏性/特殊结构来避免指数级别的计算.
Example 1: Ising chain
Ferromagnetic Ising model has $\underline{\sigma}=(\sigma_1,\dots, \sigma_N), \sigma_i\in\{1,-1\}$ with joint distribution
where $Z$ is the partition function.
我们计算 $\sigma_j$ 的 marginal distribution, 这里用 $\propto$ 来省略归一化因子:
$$\mu(\sigma_j)\propto\sum_{\sigma_1,\dots,\sigma_{j-1},\sigma_{j+1},\dots,\sigma_{N}}\exp\left(\beta \sum_{i=1}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^N\sigma_i\right) \\=\sum_{\sigma_1,\dots,\sigma_{j-1},\sigma_{j+1},\dots,\sigma_{N}}\exp\left(\beta \sum_{i=1}^{j-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^{j-1}\sigma_i\right)\exp\left(\beta\sum_{i=j}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=j+1}^{N}\sigma_i\right)\exp\left(\beta B\sigma_{j}\right)$$分配拆开即可，是两个和的乘积. 定义 “message”:
This decomposition is interesting because the various messages can be computed iteratively.
Something about rust & compiler
Names of associated items
类方法、类中 associated const item 都属于 value namespace. 但是由于一个 struct 可以有多个 impl 块，仍然会有重名发生.
enum D {
A,
B,
C,
}
impl Int for D {
const FN: i32 = 1926;
fn get(&self) -> i32 {
match self {
D::A => 1,
D::B => 2,
D::C => 3,
}
}
}
impl Str for D {
fn get(&self) -> String {
match self {
D::A => String::from("A"),
D::B => String::from("B"),
D::C => String::from("C"),
}
}
}
impl D {
fn get(&self) -> i32 {
114514
}
}
impl Con for D {}
struct P {}
impl Int for P {
const FN: i32 = 2026;
fn get(&self) -> i32 {
1919810
}
}
trait Int {
const FN: i32;
fn get(&self) -> i32;
}
trait Str {
fn get(&self) -> String;
}
trait Con {
const FN: i32 = 0817;
}
struct Y {
i: i32,
p: i32,
}
fn g(d: i32, ff: &str) -> [i32; 2] {
let mut a = [0; 2];
a[0] = d;
a[1] = ff.len() as i32;
a
}
fn main() {
let d = D::B;
println!("{}", D::get(&d)); // 114514
println!("{}", Int::get(&d)); // 2
let p = P {};
println!("{}", Int::get(&p)); // 1919810
println!("{}", Str::get(&d)); // B
println!("{}", d.get()); // 114514
println!("{}", P::FN); // 2026
// println!("{}", D::FN); // error
// println!("{}", Int::FN); // error
// println!("{}", Con::FN); // error
println!("{}", <D as Con>::FN); // 817
println!("{}", <D as Int>::FN); // 1926
println!(
"{:?}",
g({ 123 }, "Hello") // [123, 5]
);
}
总之 1.field 和 method 可以重名；2.默认用 inherent impl 的 associated item, 它会覆盖 trait impl 的同名 item；3.如果要用 trait impl 的同名 item, 需要显式指定 trait 名.