#!/usr/bin/env python3
# Source: t4-optimization.html
import numpy as np

def em_gmm_1d(x, k=2, n_iter=100, seed=0):
    rng = np.random.default_rng(seed)
    pi = np.full(k, 1 / k)
    mu = rng.choice(x, k, replace=False)
    var = np.full(k, x.var())
    prev = -np.inf
    for it in range(n_iter):
        # E-step: responsibilities r[i, j] = p(z = j | x_i), in log space
        logp = (-0.5 * np.log(2 * np.pi * var)
                - 0.5 * (x[:, None] - mu) ** 2 / var + np.log(pi))
        m = logp.max(axis=1, keepdims=True)
        log_lik = (m.ravel() + np.log(np.exp(logp - m).sum(axis=1))).sum()
        r = np.exp(logp - m); r /= r.sum(axis=1, keepdims=True)
        # M-step: weighted MLE
        nk = r.sum(axis=0)
        pi = nk / len(x)
        mu = (r * x[:, None]).sum(axis=0) / nk
        var = (r * (x[:, None] - mu) ** 2).sum(axis=0) / nk
        assert log_lik >= prev - 1e-9   # EM never lowers the likelihood
        if log_lik - prev < 1e-8:
            break
        prev = log_lik
    return pi, mu, var, it

rng = np.random.default_rng(1)
x = np.concatenate([rng.normal(-2, 0.5, 300), rng.normal(3, 1.0, 700)])
pi, mu, var, it = em_gmm_1d(x)
print(np.round(pi, 2), np.round(mu, 2), np.round(np.sqrt(var), 2), it)
# [0.3 0.7] [-2.05  2.96] [0.46 1.02] 21
