The aspect Bernoulli model: multiple causes of presences and absences

Abstract

We present a probabilistic multiple cause model for the analysis of binary (0–1) data. A distinctive feature of the aspect Bernoulli (AB) model is its ability to automatically detect and distinguish between “true absences” and “false absences” (both of which are coded as 0 in the data), and similarly, between “true presences” and “false presences” (both of which are coded as 1). This is accomplished by specific additive noise components which explicitly account for such non-content bearing causes. The AB model is thus suitable for noise removal and data explanatory purposes, including omission/addition detection. An important application of AB that we demonstrate is data-driven reasoning about palaeontological recordings. Additionally, results on recovering corrupted handwritten digit images and expanding short text documents are also given, and comparisons to other methods are demonstrated and discussed.

Appendices

Appendix A

The following holds for any distributions q _n (·):

$$ \begin{aligned} \,&\sum_n \log p({{\user2{x}}}_n|{{\user2{s}}}_n,{{\user2{a}}}) \\ &\quad = \sum_n \sum_{{{\user2{z}}}_n}q_n({{\user2{z}}}_n)\log p({{\user2{x}}}_n|{{\user2{s}}}_n,{{\user2{a}}}) \end{aligned} $$

(36)

$$ =\sum_n \sum_{{{\user2{z}}}_n} q_n({{\user2{z}}}_n)\log \frac{p({{\user2{x}}}_n,{{\user2{z}}}_n|{{\user2{s}}}_n,{{\user2{a}}})} {p({{\user2{z}}}_n| {{\user2{x}}}_n,{{\user2{s}}}_n,{{\user2{a}}})}\frac{q_n ({{\user2{z}}}_n)}{q_n({{\user2{z}}}_n)} $$

(37)

$$ \begin{aligned} &= \underbrace{\sum_n \left[ \sum_{{{\user2{z}}}_n}q_n({{\user2{z}}}_n) \log p({{\user2{x}}}_n,{{\user2{z}}}_n| {{\user2{s}}}_n, {{\user2{a}}}) -\sum_{{{\user2{z}}}_n}q_n({{\user2{z}}}_n)\log q_n({{\user2{z}}}_n)\right]}_{F_{{{\user2{s}}}_1,\ldots,{{\user2{s}}}_N, {{\user2{a}}}} ({{\user2{x}}}_1,\ldots,{{\user2{x}}}_N; \; q_1(\cdot),\ldots,q_N(\cdot))} \\ &\quad + \sum_n \underbrace{\sum_{{{\user2{z}}}_n} q_n({{\user2{z}}}_n)\log \frac{q_n({{\user2{z}}}_n)} {p_n({{\user2{z}}}_n|{{\user2{x}}}_n,{{\user2{s}}}_n, {{\user2{a}}})}}_{KL(q_n(\cdot)|| p(\cdot|{{\user2{x}}}_n,{{\user2{s}}}_n, {{\user2{a}}}))} \end{aligned} $$

(38)

We can recognise that the first term of F in (38) is the sum of conditional expectations of the joint likelihood of the data and latent variables z _n , conditioned on s _n . The second term is the sum of entropies of q _n . Finally, the last term is the sum of Kullback–Leibler distances between the (so far arbitrary) distributions q _n over z _n and the true conditional posterior distributions of z _n , conditioned on s _n .

Since the KL divergence is always positive [63] (which can easily be shown by using Jensen’s inequality), F is always a lower bound to the log likelihood log p(x _n |s _n ,a), irrespective of the distributions q _n (·). When q _n (·)≡ p(·|x _n ,s _n ,a), ∀ n = 1,…,N, then the KL divergence becomes zero and, therefore, the lower bound approaches the log likelihood exactly.

The iterative EM procedure is then: In the E-step, having some fixed estimates of s _n , n = 1,…,N and a, we maximise $F_{{{\user2{s}}}_1,\ldots,{{\user2{s}}}_N,{{\user2{a}}}}({{\user2{x}}}_1, \ldots,{{\user2{x}}}_N; \, q_1(\cdot),\ldots,q_N(\cdot))$ with respect to all q _n (·). This is achieved by setting these to the true conditional posteriors p(·|x _n ,s _n , a), for all n = 1,…,N, which—from Bayes’ rule—are the following:

$$ p({{\user2{z}}}_n|{{\user2{x}}}_n,{{\user2{s}}}_n,{{\user2{a}}})= \frac{p({{\user2{x}}}_n|{{\user2{z}}}_n,{{\user2{a}}})p({{\user2{z}}}_n| {{\user2{s}}}_n)}{\sum_{{{\user2{z}}}_n} p({{\user2{x}}}_n|{{\user2{z}}}_n,{{\user2{a}}})p({{\user2{z}}}_n| {{\user2{s}}}_n)} $$

(39)

$$ = \frac{\prod_t\prod_k [a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}]^{z_{tnk}} \prod_t\prod_k [s_{kn}]^{z_{tnk}}}{\prod_t \sum_k s_{kn} a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}} $$

(40)

$$ =\prod_t \frac{\prod_k [s_{kn}a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}]^{z_{tnk}}}{\sum_k s_{kn}a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}} $$

(41)

$$ = \prod_t p(z_{tn}|x_{tn},{{\user2{s}}}_n, {{\user2{a}}}_t) $$

(42)

In (39), we used that p(x _n |z _n ,a) = p(x _n |s _n ,z _n ,a), which follows from the dependency structure of AB, namely that x _n depends on s _n only through z _n , therefore, knowing z _n makes x _n independent of s _n .

It may be interesting to note that the above conditional posterior distribution p(z _n |x _n ,s _n ,a) factorises naturally, without having imposed a factor form. Of course, as we know, this posterior is conditioned on the value of s _n , so even though it is an exact conditional posterior quantity, there is no tractable exact posterior over the joint distribution of all hidden variables of the model, which would be p(s _n ,z _n |x _n ,a) = p(s _n |x _n , a)p(z _n |x _n ,s _n , a). The latter term is what we just computed, while the former term is intractable as discussed earlier in the main text, and so a point estimate for s _n will be obtained as part of the M-step.

In the M-step, we keep the posterior distributions q _n (·) fixed at the values computed in the previous E-step, and compute the most probable value of s _n for each x _n as well as the parameters a. This is achieved by maximising $F_{{{\user2{s}}}_1,\ldots,{{\user2{s}}}_N,{{\user2{a}}}}({{\user2{x}}}_1, \ldots,{{\user2{x}}}_N; \; q_1(\cdot),\ldots,q_N(\cdot))$ with respect to all s _n and a.

To ensure the constraint ∑ _k s _kn  = 1 is met, we add a Lagrangian term. Denoting

$$ q_{k,t,n,x_{tn}}\equiv p(z_{tn}=k|x_{tn},{{\user2{s}}}_n, {{\user2{a}}}_t)= \frac{s_{kn}a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}} {\sum_{\ell} s_{\ell n}a_{t\ell}^{x_{tn}}(1-a_{t\ell})^{1-x_{tn}}} $$

(43)

where the last equality follows from (41), and replacing the result obtained from the previous E-step into F, the expression to maximise, up to a constant term, is

$$ Q = \sum_n \left[ \sum_{{{\user2{z}}}_n}q_n({{\user2{z}}}_n) \log p({{\user2{x}}}_n,{{\user2{z}}}_n| {{\user2{s}}}_n, {{\user2{a}}}) - \lambda_n \left(\sum_k s_{kn}-1\right)\right] $$

(44)

$$ = \sum_n \left[\sum_t\sum_k\left[\sum_{{{\user2{z}}}_n}q_n({{\user2{z}}}_n) z_{tnk}\right]\log [ s_{kn}a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}] -\lambda_n\left(\sum_k s_{kn}-1\right)\right] $$

(45)

$$ =\sum_n \left[\sum_t \sum_k q_{k,t,n,x_{tn}} \log [ s_{kn}a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}] -\lambda_n\left(\sum_k s_{kn}-1\right)\right] $$

(46)

where λ _n are Lagrange multipliers, and the second term of F (the entropy term) was omitted for being a constant w.r.t. the variables of interest. Eq. (45) was obtained by expanding $p({{\user2{x}}}_n,{{\user2{z}}}_n| {{\user2{s}}}_n, {{\user2{a}}})=\prod_t \prod_k [s_{kn}a_{tk}^{x_{tn}}(1-a_{tk})^{1-x_{tn}}]^{z_{tnk}}$ and grouping together the terms with z _tnk . To obtain (46), we used the result (42) and the notation (43), so that $\sum_{{{\user2{z}}}_n}q_n({{\user2{z}}}_n) z_{tnk}=\sum_{{{\user2{z}}}_n}\prod_t p(z_{tn}|x_{tn},{{\user2{s}}}_n,{{\user2{a}}}_t) z_{tnk}= p(z_{tn}=k|x_{tn},{{\user2{s}}}_n,{{\user2{a}}}_t)=q_{k,t,n,x_{tn}}.$

The terms that depend on elements of s _n are

$$ Q_{{{\user2{s}}}_n}= \sum_k\sum_t q_{k,t,n,x_{tn}}\log s_{kn}-\lambda_n\left(\sum_k s_{kn}-1\right)+{\rm const.} $$

(47)

Now, we solve the system of stationary equations w.r.t. s _kn , which are the following.

$$ \frac{\partial Q_{{{\user2{s}}}_n}}{\partial s_{kn}}= \sum_t q_{k,t,n,x_{tn}}/s_{kn} =\lambda_n $$

(48)

Multiplying both sides by s _kn , we obtain

$$ \sum_t q_{k,t,n,x_{tn}} =\lambda_ns_{kn} $$

(49)

from which we have that

$$ s_{kn}= \sum_t q_{k,t,n,x_{tn}}/\lambda_n $$

(50)

The value of λ _n is obtained by summing both sides, and using ∑ _k s _kn  = 1. This gives $\lambda_n= \sum_k \sum_t q_{k,t,n,x_{tn}} = T,$ since by its definition, $\sum_k q_{k,t,n,x_{tn}} = 1.$

To complete the M-step, we now maximise Q w.r.t. a. The terms that depend on elements of a up to constants, are the following.

$$ Q_{{{\user2{a}}}}=\sum_n\sum_k\sum_t q_{k,t,n,x_{tn}} [ x_{tn}\log a_{tk}+(1-x_{tn})\log (1-a_{tk})] $$

(51)

The stationary equations are then the following.

$$ \frac{\partial Q_{{{\user2{a}}}}}{\partial a_{tk}}= \sum_n q_{k,t,n,x_{tn}} \left(\frac{x_{tn}}{a_{tk}}-\frac{1-x_{tn}} {1-a_{tk}}\right) =\sum_n q_{k,t,n,x_{tn}}\frac{x_{tn}-a_{tk}} {a_{tk}(1-a_{tk})}=0 $$

(52)

The denominator is the variance of the Bernoulli and always non-negative, it can be simplified and by isolating a _tk we have the solution:

$$ a_{tk}=\frac{\sum_n x_{tn}q_{k,t,n,x_{tn}}}{\sum_n q_{k,t,n,x_{tn}}} $$

(53)

Note that the constraint a _tk ∈ [0,1] needed not be explicitly imposed in this model setting, as it is automatically satisfied for binary data.⁹

Appendix B

The derivation of the fixed point equations (13)–(15) as an alternating optimisation of ∑ _n p(x _n | s _n ,a) (or equivalently ∑ _n p(x _n , s _n |a)) is as follows.

Denote ${\overline{a_{tk}}}=1-a_{tk}.$ The log likelihood (11) is maximised, subject to the constraints ∑ _k s _kn  = 1 and $a_{tk}+{\overline{a_{tk}}}=1.$ The corresponding Lagrangian is thus the following:

$$ \begin{aligned} {{\mathcal{L}}} &= \sum_n \sum_t \left[ x_{tn} \log \sum_k a_{tk}s_{kn} + (1-x_{tn})\log \sum_k {\overline{a_{tk}}}s_{kn}\right. \\ &\left. \quad - c_{tk}(a_{tk}+{\overline{a_{tk}}}-1) - \lambda_n \left(\sum_k s_{kn}-1\right)\right] \end{aligned} $$

(54)

where c _tk and λ _n are Lagrangian multipliers, and we have rewritten (1 − ∑ _k a _tk s _kn ) as $\sum_k {\overline{a_{tk}}}s_{kn}.$ The stationary equations of ${{\mathcal{L}}}$ with respect to both a _tk and ${\overline{a_{tk}}}$ are

$$ \frac{\partial {{\mathcal{L}}}}{\partial a_{tk}} = \sum_n \frac{x_{tn}}{\sum_\ell a_{t\ell}s_{\ell n}} s_{kn} - c_{tk} = 0 $$

(55)

$$ \frac{\partial {{\mathcal{L}}}}{\partial {\overline{a_{tk}}}} = \sum_n \frac{1-x_{tn}}{\sum_\ell \overline{a_{t\ell}}s_{\ell n}} s_{kn} - c_{tk} =0 $$

(56)

Multiplying the first of the above equations by a _tk and the second by ${\overline{a_{tk}}}$ we obtain

$$ a_{tk} \sum_n \frac{x_{tn}}{\sum_\ell a_{t\ell}s_{\ell n}}s_{kn} - c_{tk}a_{tk} = 0 $$

(57)

$$ {\overline{a_{tk}}} \sum_n \frac{1-x_{tn}}{\sum_\ell {\overline{a_{t\ell}}}s_{\ell n}}s_{kn} - c_{tk}{\overline{a_{tk}}} = 0 $$

(58)

Summing both sides and using $a_{tk}+{\overline{a_{tk}}} = 1$ provides the Lagrangian multiplier c _tk :

$$ c_{tk} = a_{tk} \sum_n \frac{x_{tn}}{\sum_\ell a_{t\ell}s_{\ell n}} s_{kn} + {\overline{a_{tk}}} \sum_n \frac{1-x_{tn}}{\sum_\ell \overline{a_{t\ell}}s_{\ell n}} s_{kn} $$

(59)

as in (15). From (57) we have the solution for a _tk in the form of a fixed point equation:

$$ a_{tk}= a_{tk}\sum_n\frac{x_{tn}}{\sum_\ell a_{t \ell}s_{\ell n}}s_{kn}/c_{tk} $$

(60)

as in (14). Solving for s _kn proceeds similarly: the stationary equation is

$$ \frac{\partial {{\mathcal{L}}}}{\partial s_{kn}} = \sum_t \left( \frac{x_{tn}}{\sum_\ell a_{t \ell}s_{\ell n}} a_{tk} + \frac{1-x_{tn}}{\sum_\ell \overline{a_{t \ell}}s_{\ell n}} {\overline{a_{tk}}} \right) - \lambda_n =0 $$

(61)

Multiplying both sides by s _kn we obtain

$$ \sum_t \left(\frac{x_{tn}}{\sum_\ell a_{t \ell}s_{\ell n}} a_{tk}s_{kn} + \frac{1-x_{tn}}{\sum_\ell \overline{a_{t \ell}}s_{\ell n}} {\overline{a_{tk}}}s_{kn} \right) = \lambda_n s_{kn} $$

(62)

Summing over k and using ∑ _k s _kn  = 1 we have the Lagrange multiplier λ _n :

$$ \lambda_n = \sum_t \frac{x_{tn}}{\sum_\ell a_{t \ell}s_{\ell n}} \sum_k a_{tk}s_{kn} + \sum_t \frac{1-x_{tn}}{\sum_\ell \overline{a_{t \ell}}s_{\ell n}} \sum_k {\overline{a_{tk}}}s_{kn} $$

(63)

$$ = \sum_t x_{tn} + \sum_t (1-x_{tn})=T $$

(64)

Having computed λ _n , from (62) we obtain the fixed point equation for s _kn , identical to (13):

$$ s_{kn}= s_{kn} \left\{\sum_t \frac{x_{tn}}{\sum_\ell a_{t \ell}s_{\ell n}}a_{tk} + \frac{1-x_{tn}}{\sum_\ell \overline{a_{t \ell}}s_{\ell n}} {\overline{a_{tk}}}\right\}/T $$

(65)

As discussed in the text, this derivation is simpler and yields the same multiplicative updates (13)–(15), obtained also via rewriting the EM algorithm (7)–(9). However, the fact that we need not iterate each multiplicative fixed point update to convergence separately before alternating these inner loops, but we can actually just alternate them while still obtaining a convergent algorithm, is less apparent from the derivation given in this section. Instead, this is a consequence of the EM interpretation presented in Appendix A. Indeed, recall that every single multiplicative update is a combination of a full E-step and an M-step update for one (group of) variables, hence it is guaranteed not to decrease the likelihood.