昨天提到了Generative Model以及Low-density Separation，今天就要继续介绍其他半监督式学习的方式。

Smoothness Assumption

• 近朱者赤，近墨者黑。

它的假设是， 的分布是不平均的，在某些地方很集中，某些地方很分散，如果今天 他们在一个high density的region很接近的话，那它们的label 才会是相同的，也就是说它们可以用high density的path做connection。

举例来说，下图是我们data的分布，假设我们有三笔data ，而Smoothness Assumption的假设是相似要透过一个high density的region，也就是说， 相连的地方是通过一个high density path相连的。

假设只看下图的这几笔资料，单看它们的pixel相似度可能2跟3是比较像的。

但是如果今天看了所有的data，就会发现这两个2中间有很多连续的变化、很多过渡的型态，也就是说它们中间有很多不直接相连的相似，所以根据Smoothness Assumption你就可以发现两个2是属於同一个class，而2跟3是属於不同的class。

Cluster and then Label

Cluster and then Label是实作Smoothness Assumption最简单的方法，下图中橘色是class 1，绿色是class 2，蓝色是unlabeled data，接下来就把这些data做clustering，可能就可以分成3个cluster，然後你会发现cluster 1的橘色class 1的label data最多，所以cluster 1里面的data都算是class 1，而cluster 2, 3都算是class 2。

Graph-based Approach

另一个方法是引入Graph structure，用Graph structure来表达connected by high density path，也就是说，我们把所有的data point建成一个graph，而你要想办法算出它们之间的singularity并把它们之间的edge建出来。有了这个graph之後，如果今天有两个点，它们在这个graph上面是相连的，他们就是同一个class。

要如何建一个graph？有些时候这个graph的representation是很自然就可以得到的，举例来说，你现在要做一个网页的分类，然後你有纪录网页和网页之间的hyperlink，那hyperlink就会告诉你这些网页是怎麽连结的。或是论文的分类，论文和论文之间有引用的关系，这些引用也可以是另外一种graph的edge。但有时候你还是要自己想办法建一个graph。

Graph-based Approach - Graph Construction

要如何建一个graph？首先你要先定义如何计算两个object之间的相似度，举例来说，影像base on pixel算相似度可能表现不太好，可能base on autoencoder抽出来的feature算相似度可能表现会比较好等等。

接着就可以建graph。

• K Nearest Neighbor
  • 假设有一堆data，我都可以算出data跟data之间的相似度，设定 ，就代表每一个point都跟它最接近、最相似的3个点相连。
• e-Neighborhood
  • 每一个点只有跟它相似度超过某一个threshold，跟它相似度大於e的点才不会被圈在一起。

而edge也不是只有相连跟不相连两种选择而已，也可以给edge权重，让你的edge跟要被连接起来的两个data point之间的相似度成正比，这边建议用RBF function来定义相似度，式子如下图所示，其中取exponential可以让表现比较好，因为有取exponential让整个function下降速度很快，所以只有当两个点非常相近的时候，它的singularity才会大，只要距离稍微远一点，singularity就会下降的很快，变得很小。

所以Graph-based的方法，它的精神是，假设我在这个graph上面有一些labeled data，那跟它们有相连的，它们是class 1的机率也会上升，所以每一笔data会影响它的邻居，而它的邻居还会继续影响它的邻居，也就是说它会通过graph的link传递过去。

刚刚都是定性的说怎麽使用这个graph，接下来我要说明的是怎麽定量的使用这个graph。它是在graph的structure上面定一个label的smoothness，也就是会定义这个label有多符合我们刚刚提到的Smoothness Assumption的假设。

如果我们看下图的两个例子，其中data point和data point之间的数字代表edge的weight，假设我们给每一个data不同的label，左边的给{1,1,1,0}，右边的给{0,1,1,0}，很明显的会觉得左边比较smooth，但是我们要用一个数字来定量的描述它有多smooth，所以我们就可以使用下图的公式，计算出来的值越小，代表越smooth。

而我们可以把 串成一个vector，里面包含labeled data也包含unlabeled data，然後我们就可以把原本的式子写成 ，这个 我们称之为Graph Laplacian，它可以写成两个matrix相减，其中 代表每一个data point两两之间的weight的connection的关系，而 是把 的每一个row合起来。

现在我们知道可以用 来评估我们的label有多smooth，当你要把graph的information考虑到neural network的训练的时候，你就只要在原本的Loss加一项smoothness的值乘上一个可调的参数 ，而这一项就像是一个Regularization term。当然算smoothness不一定是要在output的地方，如果今天是一个deep neural network，你可以在network的任何地方算smoothness。

参考资料

李宏毅老师 - ML Lecture 12