Laplacian Regularization

In Least Square learning methods, we calculate the Euclidean distance between sample points to find a classifier plane. However, here we calculate the minimum distance along the manifold of points and based on which we find a classifier plane.

In semi-supervised learning applications, we assume that the inputs $x$ must locate in some manifold and the outputs $y$ vary smoothly in that manifold. In the case of classification, inputs in the same manifold are supposed to have the same label. In the case of regression, the maps of inputs to outputs are supposed to vary smoothly in some manifold.

Take the Gaussian kernal function for example:

$$f_{\theta}(x)=\sum_{j=1}^{n}\theta_{j}K(x,x_{j}),\quad K(x,c)=\exp\left(-\frac{\|x-c\|^{2}}{2h^{2}}\right)$$
There are unlabeled samples $\{x_{i}\}_{i=n+1}^{n+n'}$ that also be utilized:
$$f_{\theta}(x)=\sum_{j=1}^{n+n'}\theta_{j}K(x,x_{j})$$
In order to make all of the samples (labeled and unlabeled) have local similarity, it is necessary to add a constraint condition:
$$\min_{\theta}\left[\frac{1}{2}\sum_{i=1}^{n}\left(f_{\theta}(x_{i})-y_{i}\right)^{2}+\frac{\lambda}{2}\|\theta\|^{2}+\frac{v}{4}\sum_{i,i'=1}^{n+n'}W_{i,i'}\left(f_{\theta}(x_{i})-f_{\theta}(x_{i'})\right)^{2}\right]$$
whose first two terms relate to the $\ell_{2}$ regularized least square learning and last term is the regularized term relates to semi-supervised learning ( Laplacian Regularization). $v\geq 0$ is a parameter to tune the smoothness of the manifold. $W_{i,i'}\geq 0$ is the similarity between $x_{i}$ and $x_{i'}$. Not familiar with similarity? Refer to:

http://blog.csdn.net/philthinker/article/details/70212147

Then how to solve the optimization problem? By the diagonal matrix $D$, whose elements are sums of row elements of $W$, and the Laplace matrix $L$ that equals to $D-W$, it is possible to transform the optimization problem above to a general $\ell_{2}$ constrained Least Square problem. For simplicity, we omit the details here.

n=200; a=linspace(0,pi,n/2);
u=-10*[cos(a)+0.5 cos(a)-0.5]'+randn(n,1);
v=10*[sin(a) -sin(a)]'+randn(n,1);
x=[u v]; y=zeros(n,1); y(1)=1; y(n)=-1;
x2=sum(x.^2,2); hh=2*1^2;
k=exp(-(repmat(x2,1,n)+repmat(x2',n,1)-2*x*(x'))/hh);
w=k;
t=(k^2+1*eye(n)+10*k*(diag(sum(w))-w)*k)\(k*y);

m=100; X=linspace(-20,20,m)';X2=X.^2;
U=exp(-(repmat(u.^2,1,m)+repmat(X2',n,1)-2*u*(X'))/hh);
V=exp(-(repmat(v.^2,1,m)+repmat(X2',n,1)-2*v*(X'))/hh);
figure(1); clf; hold on; axis([-20 20 -20 20]);
colormap([1 0.7 1; 0.7 1 1]);
contourf(X,X,sign(V'*(U.*repmat(t,1,m))));
plot(x(y==1,1),x(y==1,2),'bo');
plot(x(y==-1,1),x(y==-1,2),'rx');
plot(x(y==0,1),x(y==0,2),'k.');