One-Error多标签分类_论文阅读11——多标签特征选择
Multi-Label Informed Feature Selection
大多数现有的多标签特征选择算法：1）解决多个单标签特征选择问题，2）直接使用不完善的标签，无法找到由多个标签共享的特征。论文提出了多标签信息特征选择框架MIFS，利用标签的相关性来选择多个标签的共享特征。为了减少不好的标签信息在发现标签相关性方面的负面影响，将多标签信息分解为一个低维空间（首先对标签进行降维），然后利用减少的空间引导特征选择过程。
一、相关知识
1.1 多标签分类
多分类任务指的是一条数据只有一个标签，但是标签有多种类别。机器学习中比较经典的iris鸢尾花数据集就是标准的多分类任务，一条数据喂给模型，模型需判断它是3个类别中的哪一个。
多标签分类任务指的是一条数据可能有一个或者多个标签，举个例子：比如一个病人的体检报告，它可能被标记上，高血压，高血糖等多个标签。
多标签分类任务的两个特点：类别数量不确定，有些样本可能只有一个标签，有些样本可能存在多个标签；标签之间可能存在相互依赖关系，如一个人患有高血压，他有心血管疾病的概率也会变大，所以高血压这个label和心血管疾病的那些labels是存在一些依赖关系。
Multi-Label和传统的分类问题的区别主要在于多Label下，输出空间呈现指数级增长。目前对于Multi-Label的这类特性，学界一般是集中在更好的分析Label之间的相关性来避免这种指数增长。主要的Strategy大致可以分为三类：
First-Order Strategy：考虑label之间相互独立，就可以把Multi-label问题转换为普通的分类问题。如果一个Label有多类的话，那么就用传统的One vs All来解决。
Second-Order Strategy：考虑Label之间的两两相关性，结果会导致计算复杂度有显著的增加。
High-Order Strategy：考虑多Label之间的相关性，计算复杂度会更高。
对于Multi-Label Learning算法的评定指标一般有五个，分别为：
Hamming Loss(汉明损失)：该指标衡量预测所得标签与样本实际标签之间的不一致程度，即样本的预测标签集与世纪标签集之间的差距。这个值越小越好。
One-error(1-错误率)：该指标表示样本预测的隶属度最高的标签不属于其实际标签集的可能性。这个值越小越好。
Coverage(覆盖率)：该指标表示在预测标签集的排序队列中，从隶属度最高的类别开始向下，平均需要跨越多少标签才能覆盖其实际标签集的所有标签。这个值越小越好。
Ranking Loss(排序损失)：该指标表明了样本预测标签集中，预测正确的标签的隶属度低于预测错误的标签的隶属度的可能性。这个值越小越好。
Average Precision(平均准确度)：该指标表示预测标签集的平均准确度。这个值越高越好。
1.2 稀疏学习的特征选择
稀疏学习也就是使得许多参数的最优值变成 0（l1 相比于 l2 为什么容易获得稀疏解？https://www.zhihu.com/question/37096933）。基于稀疏学习的特征选择方法由于良好的性能和可解释性受到越来越多关注。基于2,1范式正则化的方法具有处理多类问题的能力，可以保证特征系数在多个目标之间稀疏。但这些方法不能直接应用于多标签特征选择，因为它们没有在特征选择的过程中明确考虑标签的相关性。
监督机器学习问题无非就是“minimize your error while regularizing your parameters”，也就是在规则化参数的同时最小化误差。最小化误差是为了让模型拟合训练数据，而规则化参数是防止模型过分拟合训练数据。因为参数太多，会导致模型复杂度上升，容易过拟合，训练误差会很小，但训练误差小并不是最终目标，而是希望模型的测试误差小，也就是能准确的预测新的样本。所以需要保证模型“简单”的基础上最小化训练误差，这样得到的参数才具有好的泛化性能（也就是测试误差也小），而模型“简单”就是通过规则函数来实现的。另外，规则项的使用还可以约束模型特性。可以将人对这个模型的先验知识融入到模型的学习当中，强行地让学习到的模型具有人想要的特性，例如稀疏、低秩、平滑等等。
参数稀疏有什么好处
1）特征选择(Feature Selection)：
稀疏规则化能实现特征的自动选择。一般来说，xi的大部分元素（也就是特征）都是和最终的输出yi没有关系或者不提供任何信息的，在最小化目标函数的时候考虑xi这些额外的特征，虽然可以获得更小的训练误差，但在预测新的样本时，这些没用的信息反而会被考虑，从而干扰了对正确yi的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命，它会学习地去掉这些没有信息的特征，也就是把这些特征对应的权重置为0。
2）可解释性(Interpretability)：
如患某种病的概率是y，收集到的数据x是1000维的，也就是需要寻找这1000种因素到底是怎么影响患上这种病的概率的。假设这是个回归模型：y=w1x1+w2x2+…+w1000x1000+b（当然了，为了让y限定在[0,1]的范围，一般还得加个Logistic函数）。通过学习，如果最后学习到的w就只有很少的非零元素，例如只有5个非零的wi，那么这些对应的特征在患病分析上面提供的信息是巨大的、决策性的。但如果1000个wi都非0，医生面对这1000种因素更加不好分析。
二、背景介绍
每个实例同时与多个标签相关联，如生物信息学中，一个基因可能与多种功能有关；信息检索中，每个文档可能涵盖多个主题；图像处理中，可以用不同的场景对图像进行注释。多标签数据通常是由具有很高维数的特征向量表示，多标签数据的高维性不仅显着增加了许多学习算法的存储需求和计算成本。最具区别性的信息通常仅由相关特征的子集来承载，通过消除对学习性能产生负面影响的噪音、以及多余和不相关的功能。
但直接对多标签数据进行特征选择并不容易。不同于传统的单标签特征选择类别标签互斥的，多标签数据中的不同类别通常不是独立的而是内在相关的。还要寻找一种合理的方法利用标签相关性进行多标签特征选择。
MIFS框架首先将标签信息映射到一个低维空间中，该空间可以捕获多个标签之间的相关性。然后使用低维空间代替原始标签信息进行特征选择，减轻标签信息不完善的负面影响，从而可以在多个标签之间找到相关特征。
2.1 相关研究
一种有效的策略是利用标签相关性来减少特征维数：MLLS提取多个标签之间共享的公共子空间；MDDM通过最大化原始特征描述与相关类标签之间的依赖关系，将原始数据投影到低维空间中；SFUS联合通过稀疏正则化选择特征，并发现原始特征的共享特征子空间。
这些工作与我们提出的MIFS框架有所不同：1）大多数现有的多标签学习方法着重于将原始特征空间转换为新空间，而我们的方法直接执行特征选择，保留了原始数据的物理含义；2）为减少不完善标签信息的负面影响，首先将标签分解为低维空间，利用它进行稀疏正则化的特征选择。
三、算法介绍
在多标签学习中，每个样本都具有多个类别标签，并且这些标签可能相互关联。因此特征选择时，最好明确考虑标签间的相关性，就能找到强相关标签的共同特征、弱相关标签的不同特征。但直接从多个标签中提取标签相关性是有问题的，多标签数据通常包含数百甚至数千个人类注释标签。在艰苦的注释工作中不可避免地要做出一些不正确和不完整的标签。在存在倾斜标签的情况下，直接将多个标签应用于特征选择是不合适的。受潜在语义索引（LSI）的启发，论文提出将多标签输出空间分解为低维空间，并利用该低维空间来指导特征选择过程。
将原多标签Y分解为V和B两个低维矩阵。其中V表示多标签信息的潜在语义，即，将原始的k个标签聚类为c个不同的聚类，每个聚类都有特定的语义（重新定义新标签的语义）。B是系数矩阵，每一列显示了这些新语义变量中原标签的系数。
由于低维潜在语义矩阵V标签之间的相关性大大降低，可以利用它通过回归模型和与潜在语义最相关的特征进行特征选择。
W是特征系数矩阵，W的每一行衡量第i个特征在近似潜在语义V中的权重。使用2,1-范数正则化以确保W行稀疏，对所有潜在的语义变量都实现了联合特征稀疏性。参数平衡了特征学习和标签分解的作用，参数控制模型的稀疏性。
由于使用低维潜在语义V进行特征选择，因此需要确保输入空间X和简化后的低维语义V之间的局部几何结构是一致的（如果有两个实例在输入空间X中彼此靠近，那它们在潜在语义空间V中也应该彼此靠近）。需要使下式最小化：
S是x间的相似度量矩阵，A是S的对角矩阵。整合数据的局部几何结构，用于多标签信息特征选择（MIFS）的最终目标函数可以表述为：
参数用于测量如何在潜在语义空间中保留数据的局部几何结构。 从等式中可以看出，潜在语义V与3项内容相关：捕获标签相关性、保留局部几何结构、同时指导特征选择过程。特征系数矩阵W与2项相关：通过回归模型使X近似为V，通过2,1-范数正则化实现特征选择。
四、实验设计
数据集包括一个图像数据集和三个文本数据集。Scene数据集包含来自Corel库存图片库的400张图像和一些个人图像，每个图像都与六个语义场景（长凳、日落、红叶、领域、城市和山脉）的子集相关联。RCV1，即路透社语料库第1卷，包含了超过80000条新闻专线报道。每个文档均以TF-IDF格式表示、并已进行余弦标准化。从RCV1存储库中选择三个代表性的多标签文本数据集“主题”、“地区”和“行业”。 表1列出了这些数据集的详细信息。
论文使用F-score、macro-average和micro-average来衡量多标签分类算法的性能。F-score用于评估二进制分类，被定义为精度和查全率的谐波均值：
其中TP表示真阳性的数量，FP表示假阳性的数量，FN表示假阴性的数量。micro-average可以视为所有k个标签的F度量的加权平均值：
macro-average是所有输出标签的F量度的算术平均值：
TPi、FPi和FNi分别表示第i类标签中真阳性，假阳性和假阴性的数量。值越高，分类性能越好。论文中使用到的几种多标签特征选择对比实验方法：
1）F-score：Fisher Score，通过为相似类的实例分配相似的特征值以及为不同类实例分配不同的特征值来选择特征。选择具有最高判别力的特征。
2）RFS：Robust特征选择，对损失函数和正则项均应用2,1范数正则化。对输入空间的异常值具有鲁棒性，且能够在所有实例中选择具有联合稀疏性的特征。
3）CSFS：凸半监督多标签特征选择，是一种针对大规模多标签特征选择问题设计的凸算法。论文采用监督算法进行公平比较。
4）SFUS：具有稀疏性的子特征选择，结合联合稀疏特征选择和多标签学习来发现共享特征子空间。
4个数据集的特征分别是294、14171、7236、18894，特征选择的数量变化为特征总数的{2％，4％，...，20％}分别进行实验。
（f-score应该是0-1之间的数，因此纵坐标也应该有%。实际上除了a数据集上取得的结果较好，其他准确度非常的低。）
1）随着所选特征数量的增加，分类性能首先趋于提高，然后保持稳定甚至下降；
2）在四个数据集上，MIFS和其他两种多标签学习算法CSFS和SFUS比单标签特征选择算法F-score**（事实上F-score很多时候也比其他方法要好）** 和RFS获得更好的macro-average和micro-average得分，表明执行特征选择时，将多标签信息显式合并到模型中是有益的。
3）大多数情况下，MIFS优于其他两种多标签学习算法CSFS和SFUS。表明通过将标签信息分解为低维语义空间，仍可捕获标签相关性，并减轻倾斜标签对相关特征的负面影响。
五、论文总结
论文提出了一种新颖的多标签知情特征选择框架MIFS，所提出的方法具有两个吸引人的特性：1）利用了多标签的潜在语义来指导特征选择阶段，它减轻了嘈杂标签和不完整标签在查找相关特征方面的负面影响；2）利用输出空间中的标签相关性来查找在多个标签之间共享的特征，提出了一种有效的交替优化算法来解决MIFS的优化问题。
5.1 个人体会
现在的多标签处理方式一般有两种方法：1）将问题转化为多个单标签的子问题；2）直接使用倾斜标签flawed labels（没有找到相关说明，个人理解，在影响方面所占权重不同）。而文章最突出的贡献在于：提出首先将多标签的数据进行合并、降维，去除标签之间的相关性。这样在后面特征选择的时候能够综合考虑到除去相关性的特征，不会造成选择的重复特征或者不相关特征。
实验将多标签问题分解为多个二分类问题，使用SVM作为分类算法，分别使用macro-average和micro-average作为评价指标。
找到强相关标签的共同特征，以及弱相关标签的不同特征
参考文献
https://www.jianshu.com/p/76f9e4c0d0a2
https://www.cnblogs.com/liaohuiqiang/p/9339996.html多标签学习综述（A review on multi-label learning algorithms）
https://zhuanlan.zhihu.com/p/26421688
classification总结
https://cosx.org/2016/06/discussion-of-sparse-coding-in-deep-learning/浅谈深度学习中潜藏的稀疏表达