标签：分类器 标签 学习 监督 类别 数据 标注

1   相关概念

1.1  半监督学习的定义

同时利用有标注数据和无标注数据学习

 

1.2  半监督分类/回归

给定标注数据和无标注数据，学习得到一个分类器f，要求该分类器f比只用标注数据学习得到的学习器更优。

 

1.3  半监督聚类/降维

给定标注数据，但是另外对数据做一些限制

聚类：两个点必须在一个簇，或两个点一定不能在一个簇

降维：两个点降维后必须接近

 

1.4  半监督学习的基本假设

半监督学习有效，必须满足一些假设。

1.4.1 平滑假设

如果高密度区域中在两个点x₁,x₂距离较近，那么对应的输出y₁,y₂也应该接近。

1.4.2 聚类假设

如果两个点在同一个簇，那么它们很有可能属于同一个类别。

1.4.3 流形假设

输入空间由所有数据点所在的多个低维流行构成。

位于同一个流形上的数据点具有相同的标签。

流形上距离近的点的标签相似。

 

2   半监督分类

2.1  自我训练算法

2.1.1 基本假设

输出的高度置信的预测是正确的

2.1.2 自学习算法基本流程

1.从(x_L,y_L)学习f

2.对x∈D_u，计算预测结果f(x)。

3.把(x,f(x))加入到标注数据。

4.重复

2.1.3 自我训练的变体

加入一些置信度最高的(x,f(x))到标注数据集

把所有(x,f(x))加到标注数据

把所有(x,f(x))加到标注数据，为每条数据安置置信度赋予权重

2.1.4 自我训练的优点

简单，效果好

是一种wrapper方法，可以应用到已有的（复杂）分类器上

2.1.5 自我训练的缺点

早期的错误会被强化。

在收敛性方面没有保障。

 

2.2  协同训练

2.2.1 基本思想

在标注数据上训练多个分类器，多个分类器互相教对方，将各自最有信心的的预测加到其他分类器的标注数据。

2.2.2 协同训练的基本假设

要求特征可分裂x=[x⁽¹⁾;x⁽²⁾]，x⁽¹⁾和x⁽²⁾在给定类别后条件独立

 

2.2.3 协同训练的算法流程

1.训练两个分类器，从(X_L⁽¹⁾,y_L)学习f⁽¹⁾，从(X_L⁽²⁾,y_l)学习f⁽²⁾

2.用f⁽¹⁾和f⁽²⁾分别对D_u分类

3.把f⁽¹⁾的k个置信度最高的预测结果(x,f⁽¹⁾(x))当做f⁽²⁾的标注数据

4.把f⁽²⁾的k个置信度最高的预测结果(x,f⁽²⁾(x))当做f⁽¹⁾的标注数据

5.重复第2步

 

2.2.4 协同训练案例（以网页为例）

多视图学习

从不同的视图看待一个对象，如一个网页，可以从图像角度和HTML文本角度看待，训练一个图像分类器和一个文本分类器，两个分类器互相教对方。

特征分裂

每个实例由两个特征集合x=[x⁽¹⁾;x⁽²⁾]表示

x⁽¹⁾ = 图像特征

x⁽²⁾ = web页面文本

2.2.5  协同训练的优点

对错误不那么敏感。

2.2.6 协同训练的缺点

自然的特征可能无法分裂。

使用全部特征的模型可能更好。

 

2.3 生成模型

2.3.1 特点

假设所有数据都由一个潜在的模型生成

模型参数将无标注数据和学习目标联系起来

无标注数据的标签可视为模型的缺失参数，可通过基于EM算法进行极大似然估计求解。

2.3.2 应用

高斯混合模型（GMM）

混合多项式分布（朴素贝叶斯）

隐马尔科夫模型（HMM）

 

2.3.3 以二分类任务的高斯混合模型为例

1. 先在有标签数据上使用MLE估计参数θ={π,μ,Σ}。

  类别k的比例：

  类别k的样本均值：

  类别k的样本协方差：

 

2. 在E步骤中，计算所有无标签数据数据所属类别的期望。

p(y=k|x_i,θ)：给定标签x_i，其属于k的概率。

 

3. 在M步骤中，用有标签数据X_L和无标签数据X_U，采用MLE估计参数θ。（标红的为原始估计公式，黑色部分为新添加的无标签数据）

加上了属于k类别的无标签数据的期望概率

分子第一项加上了属于k类别的无标签数据的值，由于与后验概率相乘，样本越偏离k类，概率越小，x的值越小，权重越轻。

2.3.4 生成模型的优点

清晰，有良好的理论基础

当模型接近真实的分布时，非常有效

2.3.5 生成模型的缺点

验证模型的正确性困难

EM局部最优

生成模型错误时，无监督数据错误也会加重

2.3.6 减少风险的方法

更加仔细的建立生成模型，如每个类别使用多个高斯分布，降低无标签数据的权重

 

2.3.7 基于聚类标签法半监督分类

先在无标注数据上进行聚类。一个簇内，以样本数量最多的类别为准，将其他类别的标记为该类。

优点：简单。

缺点：很难分析好坏，簇的假设不正确，结果会很差。

 

2.4  半监督SVM（S³VM）

2.4.1 SVM回顾

标准SVM

两类：y∈{+1,-1}

标注数据：{XL,YL}

权重：w

寻找一个函数f(x)=w^Tx+b

通过sign(f(x))分类

软间隔SVM

尝试保持标注点远离边界的同时最大化间隔。允许分类错误少数点。

ξi为松弛变量

 

合页损失

令f(x_i)=w^Tx_i+b，则z_i=1-y_i(w^Tx_i+b)=1-y_if(x_i)

目标函数：

更加倾向于标注的点正确的一边

2.4.2 无标注数据的合页损失

在无标注数据中，令y_if(x_i)=|f(x_i)|

故合页损失为：1-y_if(x_i)₊=(1-|f(x_i)|)₊

_{无标注数据原理决策边界f(x)=0}

2.4.3 S³VM目标函数

在合页损失SVM的目标函数加上无标注数据的合页损失。

第二项偏好最大化两类样本之间的间隔，第三项偏好使得无标注的点尽可能的远离间隔。

 

2.4.4 类别平衡限制

直接优化S3VM目标函数经常会导致大多数点落在一个类内，所以要使用一些类别平衡方法。

启发式的类别平衡方法：

放松的类别平衡限制：

这些作为约束。

 

2.4.5 S³VM算法

输入：权重w,C1,C2,(XL,yL),XU

求解优化问题f(x)=w^Tx+b

通过sign(f(x))分类新的测试点x

2.4.5 S₃VM的训练优化方法

SVM^light算法流程（局部最优）：

根据有标注数据训练一个SVM；

对无标注数据根据f(X_U)进行排序，以合适的比例对无标注数据进行标注y=1,-1（分配一个“硬”标签到无标注数据）；

for C'=10-5C2 to C2 :（外层循环：C2从0开始向上退火）

while TRUE :（内存循环成对标签交换）

  

  如果存在(i,j)可交换，则交换y_i,y_j

  如果没有可以交换的，结束while循环

 

分支定界法流程（全局最优解，但复杂度高，只能处理数百个无标注的点）

在无标注数据上构建一颗部分标注的树：

根节点：不标注

子节点：比父节点多一个无标注数据被标注

叶子节点：所有无标注数据被标注

在树上深度优先搜索

记录一个到当前为止的完整目标函数值

搜索时，如果遇到一个比最好的目标函数差的，就进行剪枝。

 

2.4.6 S³VM优点

SVM可以应用的地方，S3VM都可以

清晰的数学框架

2.4.7 S³VM缺点

半监督SVM的目标函数是非凸函数，优化困难

可能陷入局部最优

相比于生成模型和基于图的方法使用了更弱的假设，收益可能较小

 

2.5 基于图的算法

2.5.1 假设

基于所有数据点建立一个相似性图

图中数据点之间边的权重表示两个数据点的相似度

图中紧密相连的点趋向于有相同的标签

标签传播：近邻节点应该有相似的标签

2.5.2 图的构造

节点：X_L∪X_U

边：基于特征来计算相邻接点之间的相似度

目标：通过所有的路径来推导相似度

2.5.3 图的平滑性

图的平滑性计算（带权重的每对节点标签差值的总和），基于图的算法的目标就是构造图，使得图最平滑。

S越小越平滑

S=[ 2 x 1 +1 x 0 + 3 x 1 + 1 x 1 ] / 2 = [2+3+1]/2=3

2.5.4 拉普拉斯矩阵与平滑性关系

拉普拉斯矩阵L=D-W

D：度矩阵。

W：对角矩阵。

平滑性计算可以写成拉普拉斯矩阵表示

 

2.5.5 拉普拉斯矩阵最优解

无监督学习中，利用有标注点和无标注点构造的图的平滑性与标签有关，所以图的平滑性函数为：

目标是让图整体更加平滑，使得S(f)最小，故目标为求解S(f)的最小值，对S(f)求导：

用分块矩阵表示：

，，

    

    

    

对于无标签数据（第二行）：

令：

最终得到（最优解）：

2.5.6 基于图的算法的优点

清晰的数学框架

2.5.7 基于图的算法的缺点

图质量差的时候性能也差

对图的结构和权重铭感

存储需求大

3  半监督回归

大部分半监督分类算法无法直接扩展到半监督回归，且半监督回归研究相对较少

基于图的半监督回归：正则项为实数的预测值的平滑约束

基于包装器的半监督回归：自我训练\协同训练，在标注数据上构件K最近邻回归器，迭代地将伪标注数据互相传递，根据置信度选择数据点进行伪标注。

 

4  半监督聚类

聚类本身是一种无监督算法，半监督是聚类同时加入一系列领域知识

已知少量标记信息算法基本流程：

开始时利用有标注数据计算均值，将有标记数据划分到对应的簇中，开始划分无标注样本。

已知相关不相关的算法基本流程：

与K均值基本类似

K为样本x_i与均值向量μ_j（簇的中心）的距离d_ij的集合。

在K中寻找距离最小的样本和簇，尝试将样本加入到该簇，判断是否违背比连约束集合M和勿连约束集合C中的约束，满足约束才加入，否则不加；

 

 

 

 

标签：分类器,标签,学习,监督,类别,数据,标注
From： https://www.cnblogs.com/RedNoseBo/p/17118176.html