"""Chapter 6 (Information Theory) of Murphy (2022), Probabilistic Machine Learning: An Introduction.

Reproduces the figures of the chapter that are computed from data, a model or a simulation:

  6.1  entropy of a Bernoulli variable
  6.2  aligned DNA sequences, position weight matrix and sequence logo (simulated motif, see caption)
  6.3  forwards versus reverse KL: a unimodal Gaussian fitted to a bimodal mixture of Gaussians
  6.6  correlation versus the maximal information coefficient (MIC) on simulated relationships
  6.S1 supplementary: mutual information of a bivariate Gaussian, binned and nearest-neighbour estimates

Skipped figures, with the reason:
  6.4  the information diagram is a hand-drawn schematic with nothing computed;
  6.5  the picture of how MIC is computed is a reproduction of a figure of Reshef et al. (2011) (a schematic);
  6.7  the 357-variable WHO health data set behind the correlation-versus-MIC scatter is not available offline.

Besides the figures this module holds the small information-theory functions used by the notes
(entropy, cross entropy, KL, mutual information of a joint table, binned and nearest-neighbour estimators, MIC)
and exports small data for the browser demonstrations to ../data/ch06-*.json.

Run:  python ch06_information_theory.py [--fig 6.1 6.3 ...]
"""
import json
import os
import sys

import numpy as np
from scipy import optimize
from matplotlib.textpath import TextPath
from matplotlib.patches import PathPatch
from matplotlib.font_manager import FontProperties
from matplotlib.transforms import Affine2D

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import RED, BLUE, GREEN, ORANGE, GREY, PURPLE, savefig, panel_label, plt  # noqa: E402

CH = 6
DATA_OUT = os.path.normpath(os.path.join(common.HERE, "..", "data"))


# ------------------------------------------------------------------ information-theoretic functions
def xlogx(p, base=2.0):
    """p log p with the convention 0 log 0 = 0 (elementwise)."""
    p = np.asarray(p, float)
    out = np.zeros_like(p)
    m = p > 0
    out[m] = p[m] * np.log(p[m]) / np.log(base)
    return out


def entropy(p, base=2.0):
    """H(p) = -sum p log p (6.1), in bits by default."""
    return -xlogx(p, base).sum()


def cross_entropy(p, q, base=2.0):
    """H_ce(p, q) = -sum p log q (6.7); +inf if q = 0 where p > 0."""
    p, q = np.asarray(p, float), np.asarray(q, float)
    if np.any((q <= 0) & (p > 0)):
        return np.inf
    m = p > 0
    return -(p[m] * np.log(q[m])).sum() / np.log(base)


def kl(p, q, base=2.0):
    """D_KL(p || q) = H_ce(p, q) - H(p) (6.29)."""
    p, q = np.asarray(p, float), np.asarray(q, float)
    if np.any((q <= 0) & (p > 0)):
        return np.inf
    m = p > 0
    return (p[m] * np.log(p[m] / q[m])).sum() / np.log(base)


def perplexity(p, base=2.0):
    """2^H(p) (6.19) (base^H in general)."""
    return base ** entropy(p, base)


def joint_quantities(P, base=2.0):
    """H(X), H(Y), H(X,Y), H(Y|X), H(X|Y), I(X;Y) from a joint table P[x, y]."""
    P = np.asarray(P, float)
    P = P / P.sum()
    hx, hy, hxy = entropy(P.sum(1), base), entropy(P.sum(0), base), entropy(P.ravel(), base)
    return dict(HX=hx, HY=hy, HXY=hxy, HYgX=hxy - hx, HXgY=hxy - hy, I=hx + hy - hxy)


def kl_gauss(mu1, S1, mu2, S2):
    """KL(N(mu1,S1) || N(mu2,S2)) in nats (6.32)."""
    mu1, mu2 = np.atleast_1d(mu1).astype(float), np.atleast_1d(mu2).astype(float)
    S1, S2 = np.atleast_2d(S1).astype(float), np.atleast_2d(S2).astype(float)
    D = len(mu1)
    S2i = np.linalg.inv(S2)
    d = mu2 - mu1
    return 0.5 * (np.trace(S2i @ S1) + d @ S2i @ d - D + np.log(np.linalg.det(S2) / np.linalg.det(S1)))


def h_gauss(S):
    """Differential entropy of N(mu, S) in nats (6.26)."""
    S = np.atleast_2d(S)
    return 0.5 * np.log(np.linalg.det(2 * np.pi * np.e * S))


def binned_joint(x, y, bins):
    """Joint histogram on a bins x bins equal-width grid over the ranges of x and y."""
    H, _, _ = np.histogram2d(x, y, bins=bins, range=[[np.min(x), np.max(x)], [np.min(y), np.max(y)]])
    return H / H.sum()


def binned_mi(x, y, bins, base=2.0):
    """Plug-in mutual information of the equal-width binned data, in bits (Section 6.3.5)."""
    return joint_quantities(binned_joint(x, y, bins), base)["I"]


def scott_bins(x):
    """Scott's heuristic (6.28): B = N^(1/3) (max - min) / (3.5 sd)."""
    x = np.asarray(x, float)
    return int(np.ceil(len(x) ** (1 / 3) * (x.max() - x.min()) / (3.5 * x.std(ddof=1))))


# ------------------------------------------------------------------ maximal information coefficient
def _best_columns(x, y, l, k, ncand=40):
    """Best mutual information (bits) of an l-row equipartition of y with c = 1..k columns chosen on x
    by dynamic programming over at most ncand candidate cut points (a simplified ApproxMaxMI).
    Returns an array out with out[c] the best value with c columns."""
    n = len(x)
    order = np.argsort(x, kind="mergesort")
    xs, ys = x[order], y[order]
    ranks = np.argsort(np.argsort(ys, kind="mergesort"), kind="mergesort")
    row = np.minimum((ranks * l) // n, l - 1)           # equipartition rows
    ok = np.where(xs[1:] > xs[:-1])[0] + 1
    if len(ok) == 0:
        return np.zeros(k + 1)
    if len(ok) > ncand:
        ok = ok[np.unique(np.round(np.linspace(0, len(ok) - 1, ncand)).astype(int))]
    cuts = np.concatenate(([0], ok, [n]))
    m = len(cuts)
    cum = np.zeros((n + 1, l))
    cum[np.arange(1, n + 1), row] = 1
    cum = np.cumsum(cum, axis=0)
    # g(i, j) = sum_r c log(c / total) for the column of sorted points cuts[i] .. cuts[j]-1
    g = np.full((m, m), -np.inf)
    for i in range(m - 1):
        for j in range(i + 1, m):
            c = cum[cuts[j]] - cum[cuts[i]]
            t = c.sum()
            nz = c > 0
            g[i, j] = (c[nz] * np.log(c[nz] / t)).sum()
    kk = min(k, m - 1)
    f = np.full((kk + 1, m), -np.inf)
    f[0, 0] = 0.0
    for c in range(1, kk + 1):
        for j in range(1, m):
            f[c, j] = np.max(f[c - 1, :j] + g[:j, j])
    hy = entropy(np.bincount(row, minlength=l) / n)
    out = np.zeros(k + 1)
    for c in range(1, kk + 1):
        if np.isfinite(f[c, m - 1]):
            out[c] = hy + f[c, m - 1] / n / np.log(2)      # I = H(Y) - H(Y | columns)
    return out


def mic(x, y, alpha=0.6, ncand=40):
    """Maximal information coefficient (6.76), simplified: grids with k*l <= n^alpha, one axis an
    equipartition, the other optimised by dynamic programming over at most ncand candidate cuts;
    both orientations; entries normalised by log2 min(k, l). Returns (MIC, characteristic matrix)."""
    x, y = np.asarray(x, float), np.asarray(y, float)
    n = len(x)
    B = int(n ** alpha)
    M = np.zeros((B // 2 + 1, B // 2 + 1))
    for l in range(2, B // 2 + 1):
        kmax = B // l
        if kmax < 2:
            continue
        for xfirst in (True, False):
            a, b = (x, y) if xfirst else (y, x)
            res = _best_columns(a, b, l, kmax, ncand)       # l rows on b, k columns on a
            for k in range(2, len(res)):
                val = res[k] / np.log2(min(k, l))
                kx, ky = (k, l) if xfirst else (l, k)
                if kx < M.shape[0] and ky < M.shape[1]:
                    M[kx, ky] = max(M[kx, ky], val)
    return float(min(M.max(), 1.0)), M


def ksg_mi(x, y, k=3):
    """Kraskov-Stoegbauer-Grassberger estimator 1 of I(X;Y) in nats (Section 6.3.5), own implementation."""
    from scipy.special import digamma
    from scipy.spatial import cKDTree
    x, y = np.asarray(x, float).reshape(-1, 1), np.asarray(y, float).reshape(-1, 1)
    n = len(x)
    xy = np.hstack([x, y])
    d, _ = cKDTree(xy).query(xy, k=k + 1, p=np.inf)
    eps = d[:, -1]
    tx, ty = cKDTree(x), cKDTree(y)
    nx = np.array([len(tx.query_ball_point(x[i], eps[i] - 1e-12, p=np.inf)) - 1 for i in range(n)])
    ny = np.array([len(ty.query_ball_point(y[i], eps[i] - 1e-12, p=np.inf)) - 1 for i in range(n)])
    return float(digamma(k) + digamma(n) - np.mean(digamma(nx + 1) + digamma(ny + 1)))


# ------------------------------------------------------------------ simulated relationships (Fig 6.6, demo)
SHAPES = ["linear", "parabola", "sine", "circle", "cross", "noise"]


def shape_xy(shape, u, e1, e2, sg, s):
    """Relationship with noise level s from the base random numbers u (uniform on [-1,1]), e1, e2
    (standard normal) and sg (random signs). Used by Figure 6.6 and by the demonstration."""
    if shape == "linear":
        return u, u + s * e1
    if shape == "parabola":
        return u, u ** 2 + s * e1
    if shape == "sine":
        return u, np.sin(2 * np.pi * u) + s * e1
    if shape == "circle":
        th = np.pi * u
        return np.cos(th) + s * e1, np.sin(th) + s * e2
    if shape == "cross":
        return u, sg * u + s * e1
    if shape == "noise":
        return u, e1
    raise ValueError(shape)


def base_noise(n, seed):
    r = np.random.default_rng(seed)
    return dict(u=np.round(r.uniform(-1, 1, n), 5), e1=np.round(r.standard_normal(n), 5),
                e2=np.round(r.standard_normal(n), 5), sg=r.choice([-1.0, 1.0], n))


# ------------------------------------------------------------------ Figure 6.1
def fig_6_1(out=None):
    """Entropy of a Bernoulli random variable."""
    th = np.linspace(1e-6, 1 - 1e-6, 400)
    H = np.array([entropy([t, 1 - t]) for t in th])
    fig, ax = plt.subplots(figsize=(4.2, 2.9))
    ax.plot(th, H, color=BLUE)
    ax.plot([0.5], [1], "o", color=RED, ms=5)
    ax.set_xlabel(r"$p(X=1)$")
    ax.set_ylabel(r"$H(X)$ (bits)")
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1.05)
    ax.annotate("maximum 1 bit\nat $p=1/2$", (0.5, 1), (0.62, 0.55), arrowprops=dict(arrowstyle="->", color=GREY), fontsize=9)
    savefig(fig, CH, "fig6-1", out)


# ------------------------------------------------------------------ Figure 6.2
LETTERS = "ACGT"
LCOL = {"A": "#2ca02c", "C": "#1f5fbf", "G": "#ff7f0e", "T": "#d62728"}
MOTIF = {   # position -> probabilities of A, C, G, T; unspecified positions are uniform
    3: [0.02, 0.02, 0.94, 0.02], 4: [0.05, 0.05, 0.05, 0.85], 5: [0.80, 0.05, 0.10, 0.05],
    6: [0.05, 0.05, 0.05, 0.85], 7: [0.05, 0.60, 0.05, 0.30], 8: [0.02, 0.02, 0.94, 0.02],
    9: [0.45, 0.05, 0.45, 0.05], 10: [0.05, 0.05, 0.85, 0.05], 12: [0.15, 0.55, 0.15, 0.15],
}


def motif_sequences(n=30, length=15, seed=3):
    rng = np.random.default_rng(seed)
    pw = np.array([MOTIF.get(t + 1, [0.25, 0.25, 0.25, 0.25]) for t in range(length)])
    return np.array([[rng.choice(4, p=pw[t]) for t in range(length)] for _ in range(n)]), pw


def pwm(seqs):
    """Empirical letter distribution for each column (6.5), (6.6): array (length, 4)."""
    N = seqs.shape[0]
    return np.stack([(seqs == k).sum(0) for k in range(4)], axis=1) / N


def _draw_letter(ax, ch, x, y, w, h):
    tp = TextPath((0, 0), ch, size=1, prop=FontProperties(family="DejaVu Sans", weight="bold"))
    bb = tp.get_extents()
    tr = Affine2D().translate(-bb.x0, -bb.y0).scale(w / bb.width, h / bb.height).translate(x, y)
    ax.add_patch(PathPatch(tr.transform_path(tp), fc=LCOL[ch], ec="none"))


def fig_6_2(out=None):
    """Aligned DNA sequences, position weight matrix and sequence logo."""
    seqs, _ = motif_sequences()
    th = pwm(seqs)
    T = th.shape[0]
    fig = plt.figure(figsize=(9.0, 3.0))
    ax0 = fig.add_axes([0.0, 0.0, 0.3, 1.0])
    ax1 = fig.add_axes([0.40, 0.14, 0.27, 0.74])
    ax2 = fig.add_axes([0.74, 0.14, 0.26, 0.74])
    for i in range(12):                                   # (a) the alignment (first 12 sequences)
        for t in range(T):
            c = LETTERS[seqs[i, t]]
            ax0.text(0.05 + 0.93 * t / (T - 1), 0.95 - 0.075 * i, c, color=LCOL[c], fontsize=7.5, family="monospace", weight="bold", ha="center", va="center")
    ax0.set_xlim(0, 1.05)
    ax0.set_ylim(0.0, 1.02)
    ax0.axis("off")
    ax0.text(0.5, 0.0, "(a)", ha="center", fontsize=10)
    for t in range(T):                                    # (b) PWM: letter height proportional to probability
        y = 0.0
        for k in np.argsort(th[t]):
            if th[t, k] > 0:
                _draw_letter(ax1, LETTERS[k], t + 1 - 0.45, y, 0.9, th[t, k])
                y += th[t, k]
    ax1.set_xlim(0.4, T + 0.6)
    ax1.set_ylim(0, 1.0)
    ax1.set_xticks(range(1, T + 1, 2))
    ax1.set_xlabel("sequence position")
    ax1.set_ylabel("probability")
    panel_label(ax1, "b", "upper right")
    Ht = np.array([entropy(th[t]) for t in range(T)])     # (c) logo: column height 2 - H_t bits
    for t in range(T):
        y = 0.0
        for k in np.argsort(th[t]):
            h = th[t, k] * (2 - Ht[t])
            if h > 1e-6:
                _draw_letter(ax2, LETTERS[k], t + 1 - 0.45, y, 0.9, h)
                y += h
    ax2.set_xlim(0.4, T + 0.6)
    ax2.set_ylim(0, 2.0)
    ax2.set_xticks(range(1, T + 1, 2))
    ax2.set_xlabel("sequence position")
    ax2.set_ylabel("bits")
    panel_label(ax2, "c", "upper right")
    savefig(fig, CH, "fig6-2", out)


# ------------------------------------------------------------------ Figure 6.3
P_MIX = dict(w=np.array([0.5, 0.5]), mu=np.array([[-2.2, -2.0], [2.2, 2.0]]),
             S=np.array([[[1.0, 0.7], [0.7, 1.0]], [[1.2, -0.5], [-0.5, 0.9]]]))
GRID = np.linspace(-8, 8, 321)


def mix_logpdf(X, par=P_MIX):
    out = []
    for w, mu, S in zip(par["w"], par["mu"], par["S"]):
        out.append(np.log(w) + common.gauss_logpdf(X, mu, S))
    return common.logsumexp(np.array(out), axis=0)


def _grid_points():
    gx, gy = np.meshgrid(GRID, GRID)
    return gx, gy, np.stack([gx.ravel(), gy.ravel()], 1)


def mix_moments(par=P_MIX):
    mu = (par["w"][:, None] * par["mu"]).sum(0)
    S = sum(w * (S + np.outer(m - mu, m - mu)) for w, m, S in zip(par["w"], par["mu"], par["S"]))
    return mu, S


def q_from_theta(th):
    mu = th[:2]
    s1, s2, r = np.exp(th[2]), np.exp(th[3]), np.tanh(th[4])
    return mu, np.array([[s1 ** 2, r * s1 * s2], [r * s1 * s2, s2 ** 2]])


def reverse_kl_value(th, lp, pts, dA):
    mu, S = q_from_theta(th)
    lq = common.gauss_logpdf(pts, mu, S)
    q = np.exp(lq)
    return float((q * (lq - lp)).sum() * dA)


def fit_reverse_kl(start_mu, lp, pts, dA):
    th0 = np.array([start_mu[0], start_mu[1], 0.0, 0.0, 0.0])
    res = optimize.minimize(reverse_kl_value, th0, args=(lp, pts, dA), method="Nelder-Mead",
                            options=dict(xatol=1e-6, fatol=1e-10, maxiter=4000, maxfev=8000))
    return res.x, res.fun


def fit_kl_fwd_reverse():
    """Moment-matched Gaussian (minimises KL(p||q)) and the two local minimisers of KL(q||p), by grid integration."""
    gx, gy, pts = _grid_points()
    dA = (GRID[1] - GRID[0]) ** 2
    lp = mix_logpdf(pts)
    p = np.exp(lp)
    muf, Sf = mix_moments()
    fwd = float((p * (lp - common.gauss_logpdf(pts, muf, Sf))).sum() * dA)
    sols = []
    for m0 in P_MIX["mu"]:
        th, v = fit_reverse_kl(m0, lp, pts, dA)
        sols.append((q_from_theta(th), v))
    return dict(fwd=(muf, Sf, fwd), rev=sols, lp=lp, pts=pts, dA=dA)


def fig_6_3(out=None):
    """Forwards versus reverse KL on a bimodal Gaussian mixture."""
    r = fit_kl_fwd_reverse()
    gx, gy, pts = _grid_points()
    Z = np.exp(r["lp"]).reshape(gx.shape)
    fig, axes = plt.subplots(1, 3, figsize=(8.4, 2.9), sharex=True, sharey=True)
    titles = [r"minimise $D_{\mathrm{KL}}(p\|q)$", r"minimise $D_{\mathrm{KL}}(q\|p)$ (one mode)", r"minimise $D_{\mathrm{KL}}(q\|p)$ (the other)"]
    fits = [r["fwd"], (r["rev"][0][0][0], r["rev"][0][0][1], r["rev"][0][1]), (r["rev"][1][0][0], r["rev"][1][0][1], r["rev"][1][1])]
    for ax, ttl, (mu, S, v), lab in zip(axes, titles, fits, "abc"):
        ax.contour(gx, gy, Z, levels=6, colors=BLUE, linewidths=1.0)
        Zq = np.exp(common.gauss_logpdf(pts, mu, S)).reshape(gx.shape)
        ax.contour(gx, gy, Zq, levels=5, colors=RED, linewidths=1.0)
        ax.set_xlim(-6, 6)
        ax.set_ylim(-6, 6)
        ax.set_aspect("equal")
        ax.set_title(ttl + "\nvalue %.3f nats" % v, fontsize=8.5)
        panel_label(ax, lab, "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig6-3", out)


# ------------------------------------------------------------------ Figure 6.6
FIG66_CASES = [("linear", 0.15), ("linear", 0.6), ("parabola", 0.1), ("sine", 0.2), ("circle", 0.05), ("cross", 0.1), ("noise", 0.0)]


def fig_6_6(out=None):
    """Correlation (R^2) and MIC on simulated two-dimensional relationships."""
    nz = base_noise(300, 11)
    fig, axes = plt.subplots(2, 4, figsize=(9.6, 4.6))
    for ax, (shape, s) in zip(axes.ravel(), FIG66_CASES):
        x, y = shape_xy(shape, nz["u"], nz["e1"], nz["e2"], nz["sg"], s)
        r2 = np.corrcoef(x, y)[0, 1] ** 2
        m, _ = mic(x, y)
        ax.plot(x, y, ".", ms=2.5, color=BLUE)
        ax.set_title("%s, noise %.2f\n$R^2$ = %.2f, MIC = %.2f" % (shape, s, r2, m), fontsize=8.5)
        ax.set_xticks([])
        ax.set_yticks([])
    axes.ravel()[-1].axis("off")
    fig.tight_layout()
    savefig(fig, CH, "fig6-6", out)


# ------------------------------------------------------------------ Figure 6.S1 (supplementary)
def fig_6_s1(out=None):
    """Mutual information of a bivariate Gaussian: exact value, binned plug-in and nearest-neighbour estimates."""
    rhos = np.linspace(0.0, 0.98, 12)
    n = 1000
    rng = np.random.default_rng(5)
    z1, z2 = rng.standard_normal(n), rng.standard_normal(n)
    binned, ksg = [], []
    for r in rhos:
        x, y = z1, r * z1 + np.sqrt(1 - r ** 2) * z2
        binned.append(binned_mi(x, y, scott_bins(x)))
        ksg.append(ksg_mi(x, y) / np.log(2))
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2))
    ax = axes[0]
    rr = np.linspace(0, 0.995, 200)
    ax.plot(rr, -0.5 * np.log2(1 - rr ** 2), color="k", label=r"exact $-\frac{1}{2}\log_2(1-\rho^2)$")
    ax.plot(rhos, binned, "o-", color=RED, ms=4, lw=1, label="binned, Scott's rule")
    ax.plot(rhos, ksg, "s-", color=BLUE, ms=4, lw=1, label="nearest neighbours (k = 3)")
    ax.set_xlabel(r"correlation $\rho$")
    ax.set_ylabel("mutual information (bits)")
    ax.set_ylim(0, 3)
    ax.legend(fontsize=8, loc="upper left")
    panel_label(ax, "a", "lower right")
    ax = axes[1]
    rho, n2 = 0.8, 500
    bins = np.array([2, 3, 4, 6, 8, 12, 16, 24, 32, 48])
    rng = np.random.default_rng(6)
    sims = []
    for _ in range(60):
        a, b = rng.standard_normal(n2), rng.standard_normal(n2)
        sims.append([binned_mi(a, rho * a + np.sqrt(1 - rho ** 2) * b, B) for B in bins])
    sims = np.array(sims)
    ax.errorbar(bins, sims.mean(0), sims.std(0), fmt="o-", color=RED, ms=4, lw=1, capsize=2, label="binned estimate (mean and sd)")
    ax.axhline(-0.5 * np.log2(1 - rho ** 2), color="k", label="exact")
    ax.set_xscale("log")
    ax.set_xlabel("bins per axis")
    ax.set_ylabel("mutual information (bits)")
    ax.legend(fontsize=8, loc="upper left")
    panel_label(ax, "b", "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig6-s1", out)


# ------------------------------------------------------------------ data export
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    nz = base_noise(500, 21)
    d = {k: [float(v) for v in nz[k]] for k in nz}
    d["shapes"] = SHAPES
    with open(os.path.join(DATA_OUT, "ch06-mi-shapes.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote ch06-mi-shapes.json")


FIGURES = {"6.1": fig_6_1, "6.2": fig_6_2, "6.3": fig_6_3, "6.6": fig_6_6, "6.S1": fig_6_s1}

if __name__ == "__main__":
    export_json()
    common.run(FIGURES, CH)
