没有合适的资源?快使用搜索试试~ 我知道了~
基于成对约束的偏标记数据消歧算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 121 浏览量
2023-02-23
16:51:28
上传
评论
收藏 554KB DOCX 举报
温馨提示
试读
16页
基于成对约束的偏标记数据消歧算法.docx
资源推荐
资源详情
资源评论
偏标记数据是一种常见的弱监督数据.在这类数据中, 每个样本同时具备多个候选类别
标签, 但只有一个标签是正确的. 图 1 展示了两例典型的偏标记数据, 将新闻标题中的人名
作为新闻图像中人脸的姓名标签, 则一个人脸可能对应多个姓名标签
[1]
; 将诊断图像对应的
可能病因作为医学图像的标签, 则图像可能对应多个病因标签
[2]
.和带有唯一、正确标签的
强监督数据集类似, 偏标记数据集也常具有高维、数据不平衡的特点.但由于偏标记数据获
取成本远低于传统监督学习所需的强监督数据, 如何利用偏标记数据进行弱监督学习已成
为机器学习中的一个研究热点, 具有广阔的应用前景.
图 1 典型的偏标记数据
Fig. 1 Examples of typical partial label data
下载: 全尺寸图片 幻灯片
为利用偏标记数据进行学习, 文献[3]提出一种基于纠错输出编码的偏标记学习方法,
直接利用偏标记数据训练一个多分类器, 但该方法在训练过程中可能存在部分数据未被利
用的情况.为充分利用偏标记数据, 大多数偏标记学习算法
[4-10]
首先对偏标记数据进行消歧,
确定每个偏标记样本的正确类别标签.根据是否需要利用参数模型来假设样本分布, 现有的
消歧方法可以分为两类: 1)基于辨识(Identification)的消歧; 2)基于平均(Averaging)的消歧.
基于辨识的消歧将偏标记样本的真实标签设为参数模型的隐变量, 并基于最大似然准
则
[2]
, 或最大间隔准则
[5, 10]
建立目标函数, 之后采用迭代的方式优化目标函数求解隐变量实
现消歧.如文献[6]提出一种基于字典学习的消歧算法, 首先假设每类数据呈高斯混合分布,
然后迭代地对样本标签置信度矩阵–字典矩阵进行更新, 并根据最终的样本标签置信度矩阵
来确定样本标签.基于辨识的方法需要进行合理的模型假设, 错误的模型假设将对消歧带来
不利影响
[4]
.基于平均的消歧通过赋予偏标记样本的各个候选标签相同的权重, 综合学习模
型在各候选标签上的输出实现消歧
[7-9]
.在基于平均的消歧算法中, 图模型因无需模型假设,
以及便于描述样本间的标签关系而得到广泛应用
[7, 9]
.它是根据一定规则在样本间建立一个有
权图[Math Processing Error]G=(V,E,W), 通过分析图模型上节点候选标签间的关系来消歧.
其中[Math Processing Error]V 代表样本集合, [Math Processing Error]E 为样本间的边集
合, [Math Processing Error]W 为相应的边权重集合.文献[7]采用近邻消歧算法, 根据弱监督
学习中的流形假设
[11]
构建图模型:假设邻近样本具有相同的标签, 令样本[Math Processing
Error]x 和其近邻样本建立连边, 通过对近邻样本的候选标签集加权投票来确定[Math
Processing Error]x 的标签.文献[9]改进了文献[7], 提出基于实例的偏标记学习算法
[9]
(Instance-based partial label learning, IPAL).在构建图模型后, 该方法采用迭代的标签传播
算法进行消歧.
虽然现有的基于图模型的消歧算法具有无需模型假设的优势, 但仍存在问题.首先, 偏
标记数据通常具有较高的维度, 而欧氏距离等一些常用于度量相似度的方法在高维空间中
通常难以奏效.近年来, 在半监督学习和聚类领域, 低秩表示
[12]
因擅于表达高维数据结构而
在构建图模型时取得良好效果
[13-15]
.然而, 这些方法都是针对数据平衡的数据集, 而偏标记数
据常面临数据不平衡问题, 因此无法直接将低秩表示用于偏标记数据消歧.其次, 现有消歧
算法中, 建立图模型时只利用一种样本间约束, 即更相似样本之间边权重越大, 标签相同的
可能性越大.但在半监督、聚类领域, 有两种约束得到广泛使用, 其中一种被称为正约束
(Must-link), 即部分样本必定属于同一类, 另一种为负约束(Cannot-link), 即部分样本必定属
于不同类.这两种约束通常共同使用, 因此被合称为成对约束.研究表明利用成对约束能有效
提高聚类效果
[16-17]
.受此启发, 本文将成对约束的概念迁移至偏标记数据消歧中, 将"相似样
本应具有相同标签''定义为正约束, 将"差异较大的样本应具有不同标签''定义为负约束, 采
用成对约束对偏标记数据消歧.
综上, 本文提出一种基于成对约束的偏标记数据消歧算法(Partial label data
disambiguation algorithm based on pairwise constraints, PLDPC), 其创新之处在于: 1)针对偏标
记数据中广泛存在的数据不平衡问题, 研究该条件下低秩表示系数和样本相似度的关系; 2)
在考虑数据不平衡后, 利用低秩表示构建两个分别基于正、负约束的图模型, 并基于定义在
图模型上的能量函数
[18]
, 结合类块标准化(Class mass normalization)准则
[19]
进行消歧.
本文主要分为 5 个部分:第 1 节简要介绍低秩表示算法; 第 2 节和第 3 节是本文的主要
工作:第 2 节对数据不平衡条件下低秩表示系数和样本相似度的关系进行分析, 第 3 节基于
第 2 节中的结论提出基于成对约束的偏标记数据消歧算法; 第 4 节是仿真实验及结果; 第
5 节对本文进行总结.
1. 低秩表示
低秩表示是一种广泛应用的子空间分割方法.假设在[Math Processing Error]D 维欧几
里得空间中, 存在一组向量[Math Processing Error]X=[x1,x2,
⋯
,xn] (每列为一个样本), 这些
样本分布在[Math Processing Error]k 个线性子空间[Math Processing Error]{Si}i=1k 上, 子空
间具有低秩特性且相互独立.理想情况下, 低秩表示可以将[Math Processing Error]X 分割到
这[Math Processing Error]k 个线性子空间中, 使每个空间上的样本对应一个类.具体地, 低
秩表示将数据矩阵[Math Processing Error]X 自身作为字典矩阵, 求解[Math Processing
Error]X 在字典矩阵下的低秩表示系数矩阵[Math Processing Error]Z.问题的优化目标如式
(1)所示:
[Math Processing Error]argZmin||Z||
∗
s.t.X=XZ
(1)
其中, [Math Processing Error]||Z||
∗
为[Math Processing Error]Z 的核范数, 是[Math
Processing Error]Z 秩的凸近似, 定义为[Math Processing Error]||Z||
∗
=∑i=1rank(Z)[Math
Processing Error]δi, [Math Processing Error]δi 为[Math Processing Error]Z 第[Math
Processing Error]i 个奇异值.针对[Math Processing Error]X 中含有噪声的情况, 可通过加入
噪声项[Math Processing Error]E 来增加鲁棒性, 如式(2)所示:
[Math Processing Error]argZ,Emin||Z||
∗
+λ||E||1,1s.t.X=XZ+E
(2)
式中, 参数[Math Processing Error]λ>0, [Math Processing Error]||E||1,1=∑i∑j|Ei,j|, 用
于控制噪声的稀疏性.为较好地平衡精度和效率, 式(2)的求解通常采用非精确增广拉格朗日
乘子法
[12]
.文献[12]证明, 当[Math Processing Error]X=[X1,X2,
⋯
,Xk] ([Math Processing
Error]Xi 为[Math Processing Error]X 中第[Math Processing Error]i 类的所有样本组成的矩
阵)中每个子空间采样充足, 且噪声稀疏、有限时, 求解式(2)得到的[Math Processing
Error]Z 近似于式(3)所示的块对角矩阵, 即同一类别样本被分割到同一子空间中, 相互表示
系数绝对值较大, 而不同类别样本被分割到不同的子空间中, 相互表示系数接近于 0.因此,
低秩表示系数可以很好地描述数据全局结构
[13]
.文献[12]使用[Math Processing Error]Z 中元
素的绝对值构建样本间的相似度矩阵, 在数据平衡的 Extended Yale Database B 数据集上,
相比 4 种基准子空间聚类算法获得了最好的聚类效果.
[Math Processing Error]Z=(Z1
∗
Z2
∗
Z3
∗⋱
Zk
∗
)n×n
(3)
2. 基于低秩表示系数的样本相似度分析
记[Math Processing Error]Z 的第[Math Processing Error]i 列为[Math Processing
Error]\bmzi, 第[Math Processing Error]i 列中第[Math Processing Error]j 个元素为[Math
Processing Error]zji.由第 1 节可知, 从数据的全局结构角度分析, 当[Math Processing
Error]|zji|越大时, 样本[Math Processing Error]xi 和[Math Processing Error]xj 处于同一子空
间的可能性越大, 因此可使用[Math Processing Error]|zji|来表示[Math Processing Error]xi 和
[Math Processing Error]xj 的相似度, 称为基于全局结构的相似度.然而除了数据全局结构,
低秩表示系数还能够在一定程度上反映数据局部结构.在第 2.1 节中, 本文从数据局部结构
的角度, 分析了由低秩表示得到的基于局部结构的相似度.此外, 现有低秩表示的工作主要
是在数据平衡条件下进行的, 未考虑偏标记数据中常见的数据不平衡问题对低秩表示的影
响.为了将低秩表示用于偏标记数据消歧, 第 2.2 节在第 2.1 节的基础上分析了样本不平衡时
低秩表示系数和样本相似度的关系.
2.1 基于数据局部结构的样本相似度分析
现有工作普遍认为低秩表示系数矩阵[Math Processing Error]Z 仅能反映数据全局结构,
但实际上[Math Processing Error]Z 也可一定程度上描述数据局部结构.具体分析如下:在求解
[Math Processing Error]Z 前, 本文和文献[9]一致, 首先利用 L2 范数归一化法将每个样本的
表征向量归一化为方向不变的单位向量.根据式(1)求出[Math Processing Error]Z 后, 可得
[Math Processing Error]xi=∑j
∈
Jzjixj, [Math Processing Error]J={j|1≤j≤n}.设有[Math
Processing Error]a,b
∈
J, [Math Processing Error]xi 与[Math Processing Error]xa 的余弦相似
度[Math Processing Error]cos(xi,xa)和[Math Processing Error]xi 与[Math Processing Error]xb
的余弦相似度[Math Processing Error]cos(xi,xb)之差为
[Math Processing Error]cos(xi,xa)−cos(xi,xb)=xi
⋅
xa−xi
⋅
xb=(zaixa+zbixb+x~i)
⋅
xa−(zaixa+zbixb+x~i)
⋅
xb=[1−cos(xa,xb)](zai−zbi)+x~i
⋅
(xa−xb)
(4)
其中, [Math Processing Error]x~i=∑j
∈
J
∖
{a,b}zjixj.因为无法凭借先验知识确定[Math
Processing Error]x~i 的方向, 本文根据最大熵原则设[Math Processing Error]x~i 和[Math
Processing Error]xa−xb 之间的夹角服从[Math Processing Error][0,π]之间的均匀分布, 可得
[Math Processing Error]cos(xi,xa)>cos(xi,xb)的概率如式(5):
[Math Processing Error]P[cos(xi,xa)>cos(xi,xb)]=1πarccos[(1−cos(xa,xb))(zbi−zai)|x~i||xa−xb|]
(5)
可以看出, 当[Math Processing Error]zai>zbi 时, [Math Processing
Error]P[cos(xi,xa)>cos(xi,xb)]>P[cos(xi,xa)<cos(xi,xb)], 且[Math Processing Error]zai−zbi 越
大, [Math Processing Error]xi 与[Math Processing Error]xa 的余弦相似度越可能大于[Math
Processing Error]xi 与[Math Processing Error]xb 的余弦相似度, [Math Processing Error]xa 与
[Math Processing Error]xi 也更可能具有相同的标签, 反之亦然.
综上可知, 在对样本进行 L2 范数归一化预处理的前提下, [Math Processing Error]Z 可
反映出数据局部结构. [Math Processing Error]\bmzi 中越大的系数对应的样本和[Math
Processing Error]xi 应越相似, 反之相似度应越小, 差异越大.因此可直接使用[Math
Processing Error]zji 作为[Math Processing Error]xi 和[Math Processing Error]xj 基于局部结
构的相似度.当使用式(2)求解[Math Processing Error]Z 时, 可提高基于局部结构的相似度的
抗噪声能力.
2.2 数据不平衡时低秩表示系数和样本相似度关系
将基于全局结构、局部结构的相似度进行比较可以发现, 若[Math Processing
Error]zji>0, 两者都反映[Math Processing Error]zji 越大时, [Math Processing Error]xi 和
[Math Processing Error]xj 相似度越高; 但当[Math Processing Error]zji<0 时, 前者反映
剩余15页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3643
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功