半监督学习的一些文章(Semi-supervised)

半监督学习现在可是火红火热了！那是监督学习的成本实在是太高了，不仅要去特意标签数据，而且还需要人工刷选，而且最重要的是时间花很多，很麻烦。那么有没有一些方法，既可以使用未标签数据又可以学习到结果？

那就是两种——半监督学习和Active Learning(这种方法需要的样本量更加小）

为什么Semi-supervised 可以学习？
因为我们是估计underlying distribution (response value Y)，而且我们可以从数据知道的是，因为样本是从同一个distribution 抽取出来的，如果有相似的X,那么我们就会‘聚类’出相似的Y ，其实Semi-supervised 在ML课上面首先讲的是EM算法 (Mixure Gaussian Model) ,这个我会在文章的最后补充。

半监督学习现在主要的方法有三种：

1. Transductive SVM （和Inductive SVM 相对） （这种严格来说不是Semi的方法了）
2. Co-training: (协同训练）
3. Label Propagation: （图的标签传播算法）

Transductive 和 Inductive（semi-supervised) SVM的区别：

Inductive 是拿training 和testing 的数据来学习参数w, 并且把参数w 用在testing set 里面，这就像我现从大量的现象提取出general idea，并且把这种general idea 用到新的范式当中。Inductive 是用label points 和unlabeled points 一起来训练的分类器。
Transductive 先学习training data, 然后拿unlabel data 做testing data。这里还是先用training set 来做出一个classifer, 然后放进testing set， testing set 如果靠近训练集就会被标记为训练集。

Paste_Image.png

例如上面，有颜色的点是训练集（数量很小），我们通过KNN算法来算出越靠近有标记的点就会去标记某个种类。Transductive 只是用于标记没有标记的数据，并没有太好的预测作用。Joachims 提出要使用TSVM的方法，在文本分类中有大量的应用并且取得非常好的效果。例如query relevance feedback, news filtering, document collection 等等。

Paste_Image.png Paste_Image.png

其实这个方法说到底也很简单，第一步用正常的方法来训练（training set), 然后用测试集来做regularized的方法使得模型有哦bias,然后增加bias来增加模型的准确性。但是我们不能使用unlabel data 来调整参数或者选择kernel.

Transductive Algorithm:
(1) 用training set 来训练SVM。
(2) Tune the parameter C (开始给出一个很小的value)
(3) increase C (slack variable)
(4) retrain the classifier
(5) nonlinear using kernel

Transductive 的优点
（1） 只需要少量的测试集就可以训练模型
（2） 训练的次数快而且计算量不会太占空间。

缺点：
（1）不能成为预测模型，只能对测试集进行分类
（2） 因为没有训练出一个参数，所以每次有新的测试集进来的时候，都要重新计算一遍。

Co-Training:
协同训练：
协同训练是非常重要的半监督学习，最初是由Tom Mitchell 奠基的理论现在已经成为了一个非常重要的训练范式。其基本的思想是，通过互相训练条件独立的训练器然后把结果进行投票。但是协同训练的基本前提是，训练集是需要在Y的情况下独立，就是conditional indepence. 然而在某些数据的情况是不能这样做，所以后面发展了很多协同训练的理论，例如说Co-random forest 等等。

Tom 论文中主要的算法思想：
L 代表 有标记训练集：
U 代表没有标记的训练集：

（1） 从U 中抽样，抽出u个案例

用L去训练 H1 训练器
用L去训练 H2训练器
得到两个参数之后：
我们用H1的参数去标记 u的 分类， p + n-
我们用H2 的参数去标记u 的分类， p+ n-

把这些分类放到Labeled data 里面

然后在U 中选出样本再放进 u中，补充u

选择k次迭代

我们要注意的是H1,H2用的是同样的分类器例如是Navie Bayes 或者random forest ，然后H1,H2 可以是不同的参数。
而且L对于两个的训练数据可以是不一样的。例如H1就用了weblink上面的字，H2就用了context里面的内容。 文章里面比较了supervised learning 和unsupervised learning 的表现准确率，发现H1,H1组合起来的正确率非常高。

Paste_Image.png

但是模型有制约性，就是有违反conditional independece 的条件，他们有很多相关性，并且在设计分类器的时候，要确保分类器的差异性。

Co-forest:
不同于 Tri-Training ，CoForest 算法采用随机森林（Random Forest）来保证各分类器之间的差异性。随机森林是一个若干分类决策树的组合。它采用 Bagging 方法产生各异的训练集同时使用分类回归树作为元分类器。随机森林中单颗子树的生长过程可以概括为：首先可放回的从原标记数据集合中随机选取 n 个示例（采用 Bagging 算法获得）

Co-forest: 分类器：
（1） 训练n颗CART树，并且调整参数到最优。
（2） 对于每棵树：
加入unlabel的数据，选出在置信度区间theta里面数据并且加进树里面。
不断加入unlabel 数据，终止条件是这一次的迭代错误率大于上一次的就终止
（3）把放进unlabeldata 的数据重新再生成random forest

文章里面的实验结果是，用不同的label 和unlabel 的比例来做实验，发现无论怎样，semi的方法都是比较好的，非常robust.
这个算法的优点是：随机森林有的有点它基本都有了，样本可以减低模型的不稳定性，而且测量的是out-of-bag error. 而且又能确保模型之间的差异性。

Label Propogation:
这个是使用图论的方法来做的，就是首先用所有的data 建立一个图（Graph)，然后利用随机游走的理论来给label data 附近的点来initialize 一个概率，然后用min-cut 的方法来判断出这个点是否属于label附近的点。这个方法像KNN的方法用label data 来找到向邻近的点是否同属于一个分类。

Kaggle 比赛：
我在Forest Cover Type Prediction 当中用了semi-supervised 的方法：
因为training set: 2000
testing set over 10,000
所以加入测试集可以使performance 增加：

Elevation - Elevation in meters 高度
Aspect - Aspect in degrees azimuth 方位角
所有角度以正北方設為000°，順時針轉一圈後的角度為360°。
因此：
正北方：000°或360°
正東方：090°
正南方：180°
正西方：270°

Slope - Slope in degrees 坡度
Horizontal_Distance_To_Hydrology - Horz Dist to nearest surface water features 到水文的距离
Vertical_Distance_To_Hydrology - Vert Dist to nearest surface water features 垂直到水文的位置
Horizontal_Distance_To_Roadways - Horz Dist to nearest roadway 到roadways 的距离

Hillshade_9am (0 to 255 index) - Hillshade index at 9am, summer solstice 光的投射度 （夏至）
Hillshade_Noon (0 to 255 index) - Hillshade index at noon, summer solstice 光的投射度 （夏至）
Hillshade_3pm (0 to 255 index) - Hillshade index at 3pm, summer solstice 光的投射度 （夏至）

Horizontal_Distance_To_Fire_Points - Horz Dist to nearest wildfire ignition points
Wilderness_Area (4 binary columns, 0 = absence or 1 = presence) - Wilderness area designation：
1 - Rawah Wilderness Area Colorado
2 - Neota Wilderness Area Colorado
3 - Comanche Peak Wilderness Area Colorado
4 - Cache la Poudre Wilderness Area
Soil_Type (40 binary columns, 0 = absence or 1 = presence) - Soil Type designation

Cover_Type (7 types, integers 1 to 7) - Forest Cover Type designation

Paste_Image.png

Transformation of the data:
Aspect: 0 north eastnorth 90
distance: hillshade (the change of hillshade)
kick out some multicollineary data: hillshade 3pm hillshade 9am
find out the strong explanation of the variables: such as evaluation (Decision Tree ,single )
elimination of the outliers.

Model Building:
Using Random forest with first trial.
Gradient Boosted Machine (tree)
Add testing data to training set- co forest to train
Spruce and Lodge Poe, hard seperate, so use semi-SVM to train the data and inject biased. The existing feature can not seperate the Spruce and Lodge poe well since their environment is quite similar to each other.
(Using to build a special classifer to them)