EM for active tree link-loss tomography

Inputs. Use a finite-tree multicast loss experiment with observed counts $n_{d,y}$, where $n_{d,y}\in {\mathbb{N}}_0$, ${\sum }_{y\in \{0,1{\}}^{C_d}}{n}_{d,y}=N_d$, and $p_e$ is the success probability for edge $e$. Supply an initial vector $p^{(0)}\in (0,1{)}^E$, a likelihood tolerance $\tau \ge 0$, and an iteration cap $M\in {\mathbb{N}}_{>0}$. The data are admissible only when every pattern with positive count has ${\mathrm{\Omega }}_{d,y}\mathrm{\ne }\mathrm{\varnothing }$ and every link is traversed by at least one probe, that is,

$$N_e:=\sum _{d:e\in E_d}{N}_d>0(e\in E)\mathrm{.}$$

For algorithm calculations, extend the finite law to candidate vectors in the closed cube as follows. For $a\in [0,1]$ and $z\in \{0,1\}$, let $b(a,z)=a$ if $z=1$ and $b(a,z)=1-a$ if $z=0$. For $p\in [0,1{]}^E$, set

$$w_{p,d}^{\mathrm{c}\mathrm{l}}(x):=\prod _{e\in E_d}b(p_e,x_e),Z_{d,y}(p):=P_{p,d}^{\mathrm{c}\mathrm{l}}(y):=\sum _{x\in {\mathrm{\Omega }}_{d,y}}{w}_{p,d}^{\mathrm{c}\mathrm{l}}(x)\mathrm{.}$$

The sets ${\mathrm{\Omega }}_{d,y}$ partition the link-state space and ${\sum }_{x\in \{0,1{\}}^{E_d}}{w}_{p,d}^{\mathrm{c}\mathrm{l}}(x)={\prod }_{e\in E_d}((1-p_e)+p_e)=1$, so $P_{p,d}^{\mathrm{c}\mathrm{l}}$ is a probability law for every $p\in [0,1{]}^E$. For $p\in (0,1{)}^E$, $P_{p,d}^{\mathrm{c}\mathrm{l}}(y)=P_{p,d}(y)$ from the tree-experiment definition. This closed-cube extension is used only to evaluate candidate iterates; the experiment's parameter space remains $(0,1{)}^E$. When $Z_{d,y}(p)>0$ define

$$m_{e,d,y}(p):=\frac{\sum _{x\in {\mathrm{\Omega }}_{d,y}}{x}_e{w}_{p,d}^{\mathrm{c}\mathrm{l}}(x)}{Z_{d,y}(p)}(e\in E_d)\mathrm{.}$$

The algorithm's observed log likelihood on the closed cube is

$$\mathrm{\ell }(p):=\sum _{d=1}^D\sum _{y:n_{d,y}>0}{n}_{d,y}\log Z_{d,y}(p),$$

with $\mathrm{\ell }(p)=-\mathrm{\infty }$ if any positive-count pattern has zero probability.

Output. Return the finite iterate list and one status: invalid-input, zero-likelihood-current, zero-likelihood-candidate, likelihood-tolerance-met, or iteration-cap-reached. For admissible input, the list begins with $p^{(0)}$ and every later iterate lies in $[0,1{]}^E$. If an input check fails, the list is the one-element list $(p^{(0)})$ containing the supplied initial vector.

Procedure.

1. Validate the count constraints, pattern feasibility, interior initial vector, nonnegative tolerance, positive iteration cap, and $N_e>0$ for each link. If any check fails, return the one-element iterate list $(p^{(0)})$ and status invalid-input.

2. Initialize the list with $p^{(0)}$. At each current iterate $p^{(t)}$, compute $Z_{d,y}(p^{(t)})$ for every positive-count pattern. If any is zero, return the current iterate list, ending in $p^{(t)}$, with status zero-likelihood-current.

3. For each link $e$, compute its expected number of latent successes

$${\widehat{S}}_e^{(t)}=\sum _{d:e\in E_d}\sum _{y:n_{d,y}>0}{n}_{d,y}{m}_{e,d,y}(p^{(t)})\mathrm{.}$$

Set

$$p_e^{(t+1)}={\widehat{S}}_e^{(t)}\mathrm{/}{N}_e(e\in E)\mathrm{.}$$

This finite sum is the E-step conditional expectation of the complete-data success count; the displayed ratio is the M-step update instruction and lies in $[0,1]$ for each edge. Coordinates equal to $0$ or $1$ are allowed after an update.

4. Compute $\mathrm{\ell }(p^{(t+1)})$. If any positive-count pattern has zero probability, return the current iterate list, ending in the last valid iterate $p^{(t)}$, with status zero-likelihood-candidate. Otherwise append $p^{(t+1)}$. If $\mathrm{\mid }\mathrm{\ell }(p^{(t+1)})-\mathrm{\ell }(p^{(t)})\mathrm{\mid }\le \tau$, return the list with status likelihood-tolerance-met. If not, continue from $p^{(t+1)}$ until $M$ updates have been made, then return the list with status iteration-cap-reached.

All state sums are finite, and the finite link-state conditional probabilities are calculated directly; the generic measure-space/KL branch of the EM procedure is not invoked. The status records only the stopping rule that fired; it asserts neither parameter convergence nor a global optimum.

Finite-tree multicast loss experiments

Expectation-maximization

Xi, Michailidis, and Nair, §4.2

Lawrence, Michailidis, and Nair, §3.2