Minorization-Maximization Algorithm

Surrogate function

M (θ_{m} | θ_{m}) = f (θ_{m})

then find $θ_{m + 1} = a r g m a x M (θ)$ such that $m (θ | θ_{m + 1}) = f (θ_{m + 1})$

Beta binomial Regression Example

Y_{i} \sim B i n o m i a l (m_{i}, p_{i})

where $Y_{i}$ is a count variable

E (Y_{i}) = m_{i} p_{i}, V a r (Y_{i}) = m_{i} p_{i} (1 - p_{i})

and $p_{i}$ is assumed to follow a Beta Distribution $(α_{i_{1}}, α_{i_{2}})$

E (p_{i}) = \frac{α_{i_{1}}}{α_{i_{1}} + α_{i_{2}}} = \frac{α_{i_{1}}}{α_{i +}}

V a r (p_{i}) = \frac{α_{i_{1}} α_{i_{2}}}{α_{i +}^{2} (1 + α_{i +})^{2}}

$V a r (p_{i})$ dependds on the size of $α_{i_{1}}$ and $α_{i_{2}}$

Beta Binomial distribution of $Y$ and $p_{i}$

\begin{aligned} f_{B B} (y_{i}; \underset{\sim}{α_{i}}) & = \int_{p_{i}} f_{B i n} (y_{i}; p_{i}) f_{B e t a} (p_{i}; α_{i}) d x \end{aligned}

= \frac{m_{i}!}{y_{i}! (m_{i} - y_{i})!} \frac{Γ (α_{i +})}{Γ (α_{i_{1}}) Γ (α_{i_{2}})} \frac{Γ (y_{i} + α_{i_{1}}) Γ (m_{i} - Y_{i} + α_{i_{2}})}{Γ (m_{i} + α_{i +})}

The mean and variance of the $Y_{i}$ with the BB distribution are then given by

E (Y_{i}) = E (E (Y_{i} | p_{i})) = E (m_{i} p_{i}) = m_{i} \frac{α_{i_{1}}}{α_{i +}}

\begin{aligned} V a r (Y_{i}) & = V a r (E (Y_{i} | p_{i})) + E (V a r (Y_{i} | P_{i})) = V a r (m_{i} p_{i}) + E (m_{i} p_{i} (1 - p_{i})) \\ = m_{i}^{2} \frac{α_{i_{1}} α_{i_{2}}}{α_{i +}^{2} (1 + α_{i +}^{2})} + E (m_{i} p_{i}) - E (m_{i} p_{i}^{2}) \\ = m_{i} \frac{α_{i 1}}{α_{i +}} (1 - \frac{α_{i 1}}{α_{i +}}) \frac{m_{i} + α_{i 1}}{1 + α_{i +}} \end{aligned}

L (\underset{\sim}{β}; x_{i}) = f_{B B} (y_{i}; α_{i})

$y_{i 1}$ is the number of successes on the sample $m_{i}$

l (\underset{\sim}{β}) = \sum \log f_{B B} (y_{i}; \underset{\sim}{β}) = \sum_{i = 1}^{n} [\sum_{l = 0}^{y_{i 1} - 1} \log (e^{x_{i} β + l}) + \sum_{l = 0}^{m_{i} - y_{i} - 1} \log (e^{})]

the negative log is not concave

In the application of Jensen's inequality, for a concave function $ϕ (\cdot)$ with contants $a$ 's

a_{1} = \exp (\underset{\sim}{x_{i}})

Surrogate of the first function $f_{1}$

\log (e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{i}}} + l) = \log (a_{1} v_{1} + a_{2} v_{2}) \geq a_{1} \log v_{1} + a_{2} \log v_{2}

= \exp (\underset{\sim}{x_{i}} β)

Surrogate of the second function

f_{2} (β) = - \sum_{i = 1}^{n} \sum_{l = 0}^{m_{i} - 1} \log (e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{i}}} + e^{\underset{\sim}{x_{i} \underset{\sim}{β_{2}}}} + l)

because $l o g (\cdot)$ is concave, $- l o g (\cdot)$ is convex, choose $ϕ (\cdot) = - l o g (\cdot)$

\begin{aligned} \log (v) & = - \log (e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{i}}} + e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{2}}} + l) \\ \geq - \log (v^{(t)}) + \frac{d (- l o g (v))}{d v} |_{v = v^{(t)}} (v - v^{(t)}) \\ = - \log (v^{(t)}) - \frac{1}{v^{(t)}} (v - v^{(t)}) \\ = - \log (e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{i}}} + e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{2}}} + l) - \frac{e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{i}}} + e^{\underset{\sim}{x_{i}} \underset{\sim}{β_{2}}} - e^{\underset{\sim}{x_{i}} {\underset{\sim}{β_{i}}}^{(t)}} - e^{\underset{\sim}{x_{i}} {\underset{\sim}{β_{2}}}^{(t)}}}{e^{\underset{\sim}{x_{i}} {\underset{\sim}{β_{i}}}^{(t)}} + e^{\underset{\sim}{x_{i}} {\underset{\sim}{β_{2}}}^{(t)}} + l} \\ f_{2} (\underset{\sim}{β}) & \geq g_{2} (\underset{\sim}{β} | {\underset{\sim}{β}}^{(t)}) = - \sum_{α = 1}^{2} \sum_{i = 1}^{n} \sum_{l = 0}^{m_{i} - 1} \exp (\underset{\sim}{x_{i}} \underset{\sim}{β_{d}}) \end{aligned}

In combination we have a surrogate function $g (β)$ for the objective $f (β)$ as

\begin{aligned} f (\underset{\sim}{β}) & = f_{1} (β) + f_{2} (β) \geq g (\underset{\sim}{β} | {\underset{\sim}{β}}^{(t)}) = g_{1} (\underset{\sim}{β} | {\underset{\sim}{β}}^{(t)}) + g_{2} (\underset{\sim}{β} | {\underset{\sim}{β}}^{(t)}) \\ = \sum_{α = 1}^{2} \sum_{i = 1}^{n} (\sum_{l = 0}^{y_{i d} - 1} \frac{\exp (\underset{\sim}{x_{i}} β_{d}^{(t)})}{\exp (\underset{\sim}{x_{i}} \underset{\sim}{β_{d}^{(t)}}) + l} \underset{\sim}{x_{i}} β_{d} + \sum_{l = 0}^{m_{i} - 1} \frac{1}{\sum_{d = 1}^{2} \exp (\underset{\sim}{x_{i}} \underset{\sim}{β_{d}^{(t)}}) + l} \exp (\underset{\sim}{x_{i}} \underset{\sim}{β_{d}})) + C^{(t)} \\ = [\sum_{α = 1}^{2} \sum_{i = 1}^{n} W_{i}^{(t)} (y_{i d}^{* (t)} \underset{\sim}{x_{i}} \underset{\sim}{β_{d}} - \exp (\underset{\sim}{x_{i}} \underset{\sim}{β_{d}}))] + c^{(t)} \end{aligned}