so for the MEU model we have5

$$p(\mathbf{Y})\propto\exp\left(-{\frac{1}{2}}\mathrm{tr}\left(\mathbf{YY}^{\top}\mathbf{MM}^{\top}\right)\right)=0$$
Yn
i=1
$$\left[\exp\left(-\frac{1}{2}\mathbf{m}_{:,i}^{\top}\mathbf{YY}^{\top}\mathbf{m}_{:,i}\right).\right]$$

This provides the necessary factorization for each conditional density which can now be rewritten as

$$p(\mathbf{y}_{i,:}|\mathbf{Y}_{\backslash i})=\left({\frac{m_{i,i}^{2}}{\tau}}\right)^{\frac{p}{2}}\exp\left(-{\frac{m_{i,i}^{2}}{2}}\left\|\mathbf{y}_{i,:}+\sum_{j\in{\mathcal{N}}(i)}{\frac{m_{j,i}}{m_{i,i}}}\mathbf{y}_{j,:}\right\|_{2}^{2}\right).$$

Optimizing the pseudolikelihood is equivalent to optimizing the conditional density for each of these cliques independently,

$$\log p(\mathbf{Y})\approx\sum_{i=1}^{n}\log p(\mathbf{y}_{i,:}|\mathbf{Y}_{\setminus i}),$$

which is equivalent to solving n independent regression problems with a constraint on the regression weights that they sum to one. This is exactly the optimization suggested in (9). In maximum entropy unfolding the constraint arises because the regression weights are constrained to be wj,i/mi,i and mi,i =Pj∈N(i) wj,i. In standard LLE a further constraint is placed that mi,i = 1 which implies none of these regression problems should be solved to a greater precision than another. However, as we derived above, LLE is also applicable even if this further constraint isn't imposed.

Locally linear embeddings make use of the pseudolikelihood approximation to parameter determination Gaussian random field. Underpinning this is a neat way of constraining the Laplacian to be positive semidefinite by assuming a factorized form. The pseudolikelihood also allows for relatively quick parameter estimation by ignoring the partition function from the actual likelihood. This again removes the need to invert to recover the covariance matrix and means that LLE can be applied to larger data sets than MEU or MVU. However, the sparsity pattern in the Laplacian for LLE will not match that used in the Laplacian for the other algorithms due to the factorized representation.

## 2.7.4 When Is The Pseudolikelihood Valid In Lle?

The pseudolikelihood was motivated by Besag [1975] for computational reasons. However, it obtains speed ups whilst sacrificing accuracy: it doesn't make use of the correct form of the normalization of the Gaussian random field. For a Gaussian model the normalization is the determinant of the covariance matrix,

## |K| = |L + Γi| −1.

However, under particular circumstances the approximation is exact. Here we quickly review an occasion when this occurs.

Imagine if we force M to be lower triangular, i.e. we have a Cholesky form for our factorization of L = MM>.

The interpretation here is now that M is a weighted adjacency matrix from a *directed acyclic graph*. When constructing the LLE neighborhood the triangular form for this matrix can be achieved by first imposing an ordering on the data points. Then, when seeking the nearest K neighbors for i, we only consider a candidate data point j if *j > i*. In the resulting directed acyclic graph the neighbors of each data point are its *parents*6. The weighting of the edge between node j and its parent, i, is given by the (*i, j*)th element of M. To enforce the constraint that M>1 = 0 the diagonal elements of M are given by the negative sum of the off diagonal elements from each column
(i.e. the sum of their parents). Note that the last data point (index n) has no parents and so the (*n, n*)th element of M is zero. Now we use the fact that the log determinant of L is given by logMM> =Pi log m2 i,i if M is lower triangular. This means that for the particular structure we have imposed on the covariance the true log likelihood