Reason

Yesterday, I said the method of evaluation seems like so limited, so I’m trying my best to search the new ways to do the evaluation.

At this time, I find the manifold learning is also a good way to achieve my goal. It could reduce the dimension of high dimension data, the index system is always in high dimension, so if we could reduce the dimension of index system, then we’ll get the evaluation result.

What is Manifold

Actually, manifold is not the shape, it is a space, it means we could embed a 2 dimension manifold in 3 dimension space, then this low dimension manifold would homeomorphism to the Euclidean Space with 2 dimension, for example, in the surface of sphere, it would be expressed with polar coordinates $\mathbb{R}^n$. $$ x = r sin\theta cos \phi \\ y = r sin \theta sin \phi \\ z = r cos \theta $$ You could see that the 3 dimension is controled by 2 variables

Manifold Learning

If we defined a $d$ dimension manifold in Euclidean Space $\mathbb{R}^d$, $f:Y \rightarrow \mathbb{R}^d$ is a smooth embedding. As for $D>d$ the order of manifold learning is reconstructing the $Y$ and $f$ according to the observed variable $x_i$ in $\mathbb{R}^D$. The hedden data $y_i$ is generated by $Y$ randomly. it could produce the observed data by embedding the $f$, it means $x_i = f(y_i)$.

MDS

MDS(Multi-Dimensional Scaling) is a custom method of reducing the dimension, the target of MDS is saving the dissimilarity in high dimension, if $x \in \mathbb{R}^D$, $x^{\prime} \in \mathbb{R}^d$, $D>d$, the target function is this. $$ \operatorname{min} \sum_{i,j}|dist(x_i,x_j)-dist(x_i^{\prime},x_j^{\prime})| $$

Then we could calculate the distance matrix $D = [d_{i,j}]=[dist(x_i,x_j)]$, then we could construct matrix $A = [a_{i,j}] = [- \frac{1}{2} d_{i,j}^2]$, after the central correction, we get the matrix $B = JDJ$, $J=I-\frac{1}{n}O$, among this, the $I$ is the unit matrix with $n \times n$, $O$ is a $n \times n$ matrix which is full of value 1. Then we could get the feature vector, $e_1,e_2,\dots,e_m$, and the feature value is $\lambda_1,\lambda_2,\dots.\lambda_m$, as last we could reconstruct $X^{\prime} = E_k \boldsymbol{\Lambda}_k^{\frac{1}{2}}$, the $\boldsymbol{\Lambda}_k$ is the diagonal matrix which is constructed with the max value of feature value. $E_k$ is a matrix which is made by $k$ feature vector.

LE

LE(Laplacian Eigenmap) is a method which means the closed points in high dimension will also be closed in low dimension.

If we need to do this method, we could get the adjacency graph, according to the Hear Kernel, the $W_{ij} = e^{\frac{-||x_i - x_j||^2}{t}}$.

Then we could start to do the feature map. $$ Lf = \lambda Df $$ In this equation, $D_{ii} = \sum_j W_{ji}$, $L=D-W$ is the laplacian matrix.

The answer of this equation is $f_0,\dots,f_{k-1}$, and $0=\lambda_0 \leq \lambda_1 \leq \lambda_{k-1}$, the feature in low dimension is $f_1, f_2, \dots, f_d$.

At last the manifold learning is a excellent tool in reducing the high dimension, but we could pay attention to the loss of this method. I also have a thought in this method, if we could combine the result of each manifold learning method?