
## 2.7.2 Relating Lle To Meu

We can see the similarity now between LLE and the Laplacian eigenmaps. If we interpret MM> as a Laplacian we notice that the eigenvalue problem being solved for LLE to recover the embedding is similar to that being solved in Laplacian eigenmaps. The key difference between LLE and Laplacian eigenmaps is the manner in which the Laplacian is parameterized.

When introducing MEU we discussed how it is necessary to constrain the Laplacian matrix to be positive definite
(see Section 2.5.1). One way of doing this is to assume the Laplacian factorizes as

## L = Mm>

where M is non-symmetric. If M is constrained so that M>1 = 0 then we will also have L1 = 0. As we saw in the last section this constraint is easily achieved by setting the diagonal elements mi,i = −Pj∈N(i) mj,i. Then if we force mj,i = 0 if j /∈ N (i) we will have a Laplacian matrix which is positive semidefinite without need for any further constraint on M. The sparsity pattern of L will, however, be different from the pattern of M. The entry for `i,j will only be zero if there are no shared neighbors between i and j.

We described above how the parameters of LLE, W, are chosen to reflect locally linear relationships between neighboring data points. Here we show that this algorithm is actually approximate maximum likelihood in the MEU model. Indeed LLE turns out to be the specific case of maximum entropy unfolding where:
1. The diagonal sums, mi,i, are further constrained to unity.

2. The parameters of the model are optimized by maximizing the *pseudolikelihood* of the resulting GRF.

As we described in our introduction to LLE, traditionally the reconstruction weights, wi, are constrained to sum to 1. If this is the case then by our definition of M we can write M = I − W. The sparsity pattern of W matches M, apart from the diagonal of W which is set to zero. These constraints mean that (I − W)
>1 = 0. The LLE
algorithm [Roweis and Saul, 2000] proscribes that the smallest eigenvectors of (I − W)(I − W)
> = MM> = L are used with the constant eigenvector associated with the eigenvalue of 0 being discarded. This matches the CMDS
procedure as applied to the MEU model, where the eigenvectors of L are computed with the smallest eigenvector discarded through the centering operation.

## 2.7.3 Pseudolikelihood Approximation

To see how pseudolikelihood in the MEU model results in the LLE procedure we firstly review the pseudolikelihood approximation [Besag, 1975].

The Hammersley-Clifford theorem [Hammersley and Clifford, 1971] states that for a Markov random field (of which our Gaussian random field is one example) the joint probability density can be represented as a factorization over the cliques of the graph. In the Gaussian random field underlying maximum entropy unfolding the cliques are defined by the neighbors of each data point and the relevant factorization is

$$p(\mathbf{Y})\propto\prod_{i=1}^{n}p(\mathbf{y}_{i,:}|\mathbf{Y}_{\setminus i}),$$
$$(11)$$
p(yi,:|Y\i), (11)
where Y\i represents all data other than the ith point and in practice each conditional distribution is typically only dependent on a sub-set of Y\i (as defined by the neighborhood). As we will see, these conditional distributions are straightforward to write out for maximum entropy unfolding, particularly in the case where we have assumed the factorization of the Laplacian, L = MM>.

The pseudolikelihood assumes that the proportionality in (11) can be ignored and that the approximation

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

is valid.

To see how the decomposition into cliques applies in the factorizable MEU model first recall that

$$\operatorname{tr}\left(\mathbf{YY}^{\top}\mathbf{MM}^{\top}\right)=\sum_{i=1}^{n}\mathbf{m}_{:,i}^{\top}\mathbf{YY}^{\top}\mathbf{m}_{:,i}$$
