（模式识别与智能系统专业论文）多类别模式分类技术及其在多媒体分析上的应用.pdf

摘要 摘要 多媒体自动概念标注是在语义层次上进行视频浏览 搜索的关键技术 这 方面的研究经历了两个阶段 第一个阶段使用二值分类算法检测概念集中的 每个概念 并达到了一定得准确度 但是这种方法完全忽略了概念类别之间 的关系 第二阶段的方法在单独检测单个概念的基础上添加了一个语义融合 的步骤来通过挖掘概念之间的关联以此提高标注的准确度 但是这种方法会 将第一步的分类错误引入第二步中造成 误差传播 的问题 为了解决上述问 题 我们提出一种新的同时对单个概念与底层特征关系以及概念之间关系进 行建模的方法 称作关联多类别方法 c o 玎c l a t i v em u l t i l a b e l 简记c m l 我们 在t r e c v i d 数据集上与现有的算法进行了比较 并得到了满意的结果 另一方面 一般的主动学习算法可以在样本的维度上动态地构建训练集 尽管这种方法在一般的二值分类问题上取得了满意的结果 然而对于多类别 问题而言不是最优的解决方法 我们认为 对于每个选出的样本 仅仅其中的 一些有效类别需要被标注 而其它的类别可以通过类别之问的关系推断出来 这是因为考虑到类别的关联性 不同的类别对最小化分类误差的贡献是不同 的 因此 我们提出一种通过选择样本一类别对来最小化多类别贝叶斯分类误 差界的方法 我们称之为二维主动学习算法 因为它在设计主动学习策略时同 时考虑了样本维度和类别维度 进一步 由于训练样本随着时间会不断增加 如果使用基于重训练策略的多类别分类器 会大大增加计算的强度 我们开 发了一种高效的在线模型 它能够仅利用新到达的数据即可动态地更新当前 的模型 大大提高了算法的效率 我们在两个标准数据集以及一个从c o r b i s 网 站上得到的真实数据集来测试上述的算法 并得到令人满意的结果 关键词 多类别模式分类 多媒体分析 a b s t r a c t a b s t r a c t a u t o m a t i c a l l ya i l i l o t a t i n gc o n c e p t sf o rm u l t i m e d i ai sak e yt os e m 觚t i c 1 e lv i d e o b r o w s i n g s e a r c ha i l dn a v i g a t i o n t h er c s e a r c ho nt h i st o p i ce v 0 1 v e dt l l r o u g ht w o p a r a d i g m s t h ef i r s tp a r a d i g mu s e db i n a wc l a s s i f i c a t i o nt od e t e c te a c hi n d i v i d u a lc o n c e p ti nac o n c 印ts e t i ta c h i e v e d 锄 l yl i m i t e ds u c c e s s 硒i td i dn o tm o d e l 也e i l l l l e r e n t c o r r e l a t i o nb e 似e e nc o n c e p t s e g u r b a na i l db u i l d i n g t h es e c o n dp a r a d i g ma d d e da s e c o n ds t c po nt 叩o ft h ei n d i i d u a l c o n c e p td e t e c t o r st of h s em u l t i p l ec o n c 印t s h o w c v c r i t sp e r f b n i l a n c ev a r i e sb e c a u s et l l e 伽r o r si n c u n e di nt h e 矗r s td e t e c t i o ns t e pc 柚 p r o p a g a t et ot h es e c o n d 允s i o ns t e pa n dt h e r e f o r ed e 舯d et l l eo v e m np e r f o 硼a n c e t ba d d r e s st h ea b o v ei s s u e s w e6 r s tp r o p o a l i r dp a r a d i g mw h i c hs i m u l t a i l e o l l s l y c l 嬲s i 6 e sc o n c e p t sa n dm o d e l sc o r r e l a t i o n sb e t e e nt h e mi nas i n g l es t 印b yu s i n ga n o v e lc t d 脚肠 馆 勿肼也口抛 c m l 妇n e v 旧r k w ec o m p a 陀t h ep e r f o 衄a n c eb e 一 似e e nt h ep r o p o s e d 印p r o a c ha i l dt h es t a t e o f t h e a na p p r o a c h e si nt h ef i r s ta 1 1 ds e c o n d p 啪d i g m so nt h ew i d e l yu s e dt r e c dd a t as e t w er 印o ns u p e r i o rp e r f b 肌a n c e 1 j r o mt h ep r o p o s e d 印p r o a c h o nt l l eo t h e rh a n d c o i e n t i o n a la c t i v el e 砌n gd y n 锄i c a l l yc o n s t n j c t st h et r a i n i n gs e to n l ya l o n gt h es 锄p l ed i m e n s i o n w l l i l et h i si st h e 订曲ts t r a t e g yi nb i n a r y c l a s s i 矗c a t i o n i ti ss u b o p t i m a lf o rm u l t i l a b e li m a g ec l a s s i f i c a t i o n w ba 唱u et h a tf o r e a c hs e l e c t e ds 锄p l e 0 n l ys o m ee 彘c t i v el a b e l sn e e dt ob ea 1 1 n o t a t e dw r h i l eo t h e r s c a nb ei n f e r r e db ye x p l o r i n gt h el a b e lc o r r c l a t i o n s t h er e a s o ni st h ec o n t r i b u t i o n so f d i 伍 r e n tl a b e i st om i n i m i z i n gt h ec l a s s i f i c a t i o ne r r o ra r ed i f r e r e n td u et 0t l l ei n h e r e n t l a b e lc o 玎e l a t i o n s t om i se n d w ep r o p o s et os e l e c ts a m p l e l a b e lp a i r s r a t h e rt h 勰 o n l ys a m p l e s t om i n i m i z eam u l t i l a b e lb a y e s i a nc l a s s i f i c a t i o ne r r o rb o u n d w ec a l l i tt v o d i m e n s i o n a la c t i v el e a n l i n gb e c a u s ei tc o n s i d e r sb o t ht h es a m p l ed i m e n s i o n 肌d t h el a b e ld i m e n s i o n f u r t h e 册o r cb e c a u s et h en u m b e ro f t r a i n i n gs 砌p l e si si n c r c a s i n g m p i d l y0 v e rt i r n ed u et oa c t i v el e 锄i n g i tb e c o m e s i n t r a c t a b l ef o rm eo f n i n el e 锄e rt o r e t r a i nan e wm o d e l0 nt h ew h o l e 仃a i n i n gs e t s ow ed e v e l o pa ne f f i c i e n to n l i n el e a m e r t oa d a p t 也ee d s t i n gm o d e lw i t ht h en e wo n eb yi i l i n i m i z i n gt h e i rm o d e ld i s t a n c eu n i i l a b s t r a c t d e ras e to fm u l t i l a b e lc o n s t r a i n t s t h ee 彘c t i v e n e s sa n de f 狞c i e n c yo ft h ep r o p o s e d m e t h o da r ee v a l u a t e do n 鲰 0b e n c h m a r kd a t a s e t sa n dar e a l i s t i ci m a g ec 0 1 1 e c t i o nf 沁m ar e a l w o r l di m a g es h a r i n gw e b s i t e c o r b i s k e y w o r d s m u l t i i 国b e lp a t t e mc l a s s i 6 c a t i o n m u l t i m e d i aa n a l y s i s i v 表格 表格 3 1 自然场景数据集上的多类别标注 3 2 3 2 在自然场景数据集上 经过l o o 轮训练后 不同算法在6 个类别 上的f 1 值 3 4 4 1 在不同的两种用户界面上用户标注效率的对比 4 6 4 22 3 个图像类别及其在数据集c o r b i s 中出现的次数 4 8 4 3 样本选择策略使用的计算时问 4 9 4 4 更新模型使用的时问 4 9 v i i 插图 插图 1 1 多类别视频标注的三种典型方法的图示 从左到右 它们是独 立标注单个类别的支持向量机 s u p p o r tv e c t o rm a c h i n e 基于上 下文的概念融合算法 c o m e x t u a lb a s e dc o n c 印tf u s i o n 和相关 性多类别 c o 玎e l a t i v em u l t i l a b e l 标注 1 2 准对l s c o m 概念进行的视频图表标注的示例 对于示例中的视 频图片 每个都可以标注多个彼此不排斥的类别 1 3 视频内容分析的一般框架 1 1 2 1 2 2 2 3 2 4 2 5 2 6 2 7 3 2 3 3 3 4 基于g i b b s 随机场的c m l 模型解释 l s c o m l i t e 标注集中各个概念数量的分布 l s c o m l i t e 概念集在t r e c v i d2 0 0 5 数据集上归一化互信息量 t r e c v i d 数据集l s c o m t e 标注上多类别数目的分布 i n d s v m c b c f 和c m l i 的性能比较 i n d s 订 c b c f c m l i 和c m l i i 的性能比较 在部分关联方法中选取的具有较强关联的概念对 白色表示被 选的概念对 本图给出了对在线模型的一种几何解释 这里口表示由所有 可能的新模型的相应的条件概率分布p 涉l 功组成的空间 该 空间上以k l d 做为不同分布的度量 所有满足新样本训练集 上多类别约束的分布组成了一个子空问咒 因此 上述的优化 问题就变成了在冗中找到一个最优的新模型p 它到当 前模型 i x 的距离最近 从几何上来看 就是要找到当前模 型p 下 i x 到子空间上的投影p 涉i x 精确尸7 1 玑i x 和近似p r 1 协l x 边缘分布之间的相关度图 a 6 个类别 b 1 4 个类别 在自然场景数据集上不同的算法之问的比较 在y e a s t 数据集上三种算法性能的比较 i x 2 4 3 0 3 3 3 5 2 3 7 1 6 7 8 9 9 o 2 3 7 u m 掩垮侈 加 插图 3 5 y e a s t 数据集中基因样本上类别数量的分别 3 6 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 而为主动学习算法示例图 3 9 以图像为单位组织标注的用户界面 用户在每幅图像上将所有 概念标注完后再标注下一个图像 4 3 以概念为单位组织标注的用户界面 用户在一个概念上标注完 所有的图像后再标注下一个概念 4 4 以概念为单位组织标注的用户界面上针对用户标注效率进行的 用户研究 u s e rs t u d y 4 5 图像共享网站c o r b i s 的截图 4 7 一些在c o r b i s 数据集上多类别标注的图像的例子 5 0 图像的基于局部特征的二维阵列表示 5 0 不同主动学习算法的比较 1 2 d a l o n l i n e 使用2 d a l 主动学 习策略结合在线模型 2 e n a l o n l i n e 使用最大熵策略选择样 本结合在线模型 3 l d a l 0 n l i n e 使用普通的l 虬策略结合 在线模型 4 l d a l s l m 使用l d a l 策略结合s v m 分类器 5 b a s e l i n e 使用基准的随机选择样本策略 5 1 图中横坐标表示从真实类别中计算的类别之间的相关系数c 纵坐标表示在线模型参数且中的元素 虚线是图中点的线性回 归 这些图表示了真实的类别关联和足中参数的关系 随着迭 代次数的增加 尺和眉之间的关联度越来越大 这就是说 学习 得到的参数r 能够有效地反应c o r b i s 数据集上的类别关联 5 2 a 1 演示公式 日 p 一e m i n p 1 一计 日 p l o gi 6 0 x 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文 是本人在导师指导下进行研究工 作所取得的成果 除已特别加以标注和致谢的地方外 论文中不包 含任何他人已经发表或撰写过的研究成果 与我一同工作的同志 对本研究所做的贡献均已在论文中作了明确的说明 本人授权中国科学技术大学拥有学位论文的部分使用权 即 学校有权按有关规定向国家有关部门或机构送交论文的复印件和 电子版 允许论文被查阅和借阅 可以将学位论文编入有关数据库 进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位 论文 保密的学位论文在解密后也遵守此规定 作者签 第l 章引言 第1 章引言 近些年来 各种基于模式分类和机器学习的信息检索算法被越来越广泛 地研究 并被应用到各种商业搜索系统以及相关的原型中 特别是在基于内 容的多媒体信息检索0 u l t i m e d i ai n f o 衄a t i o nr e t r i e v a l 的研究中 由于底层特 征与高层语义之间存在着巨大的 语义鸿沟 如何将相关的多媒体内容与高 层的语义关键词建立正确的对应关系 使得在多媒体搜索过程中便于直接利 用这些关键词进行检索 已经成为了多媒体分析 计算机视觉 模式识别等相 关领域研究的重要的核心内容 然而现有的方法 绝大部分将现有的概念或 类别单独的进行分类 没有考虑到在现实世界中不同的类别之间存在广泛的 语义上的联系 例如 汽车 与 公路 这样的两个概念 在视频中往往会同时 出现 如果单独的进行分类 他们就可能失去这样的共生关系 导致系统的性 能下降 而在事实上 各种语义类别间不仅仅存在以上这种共生的关系 还存 在互斥的关系 比如 山脉 与 城市 往往就不会同时出现在视频或者图像中 所以 如何有效的利用语义类别之间普遍存在的联系 提高分类系统的准确 性 在模式识别和多媒体信息检索中具有重要的意义 在图1 1 中 我们比较 了三种不同的分类算法 在最左边的独立标注单个类别的支持向量机 s u p p o r t v e c t o r m a c h i n e 2 系统中 各种类别被单独的分类 所以在这种系统中 类别 之间的联系被完全忽略了 我们把这种系统称为独立分类系统 中间的一种 基于上下文的概念融合算法 c o m e x t u a lb a s e dc o n c e p tf u s i o n 3 考虑到了类别 之问的联系 但是它是建立在独立分类系统基础之上的 众所周知 现有的 独立分类系统很难保证分类结果的准确性 所以这种在后处理阶段利用语义 联系对前一步结果进行加工处理的方法 往往会导致前一步中的错误被传播 到第二步中 使得系统性能反而有所下降 我们的目标就是避免这种 误差传 播 在一个统一的系统中用一整步完成对多个类别以及他们联系的建模与分 类 图中最右边的关联多类别 c o r r e l a t i v cm u l t i l a b e l 4 标注系统就是我们希 望开发的多类别语义分类系统 另外 本文还将介绍若干与多类别模式识别相关的工作 比如 在人机交 互中 如何有效的利用类别之间的关系来提高人机交互的效率 以此提供更 l 第1 章引言 黧烹 烹 图l l 多类别视频标注的j 种典型 法的蝌示 从左到 它们灶独矗标汁单个类剐的支 持向量机 s u p p nv c c t o r m a c h m c 基于lf 文的概念融合算浃 c o n t e x m a lb c d c o n c p i f u 舯n 帛l 剃关性多类别 c o h e l a t mm u iu l a b e l 标 f 多高信息量的训练样本 这是关r 多类别主动学刊的问题 另一方碰 我wj 将 提出一种多类别在线模型 它是种相一线的多类别分类算法 呵吼避免计算 强度口人的艰训练过程 这些问题的解扶均有助丁推动多类别模式识别 多 媒体信息检索等相父理论的进一步发展 本文将且体结合多媒体信息分析和 检索技术 论述多类别分类系统的射l 关课题和算法 丰奇将片先介蜊多类j j 模式分类和般一位模式分类问题的区别及儿相关研究币点 然后简单的介 绍多妯l 体分析和检索系统的研究对象利j 木框架 紧接蔚介绑 奉文的研究动 帆和肚术内容 最后给出本文的内辑安排和具体乜4 新点 11 多类别模式分类的定义和研究现状 与通常的 值模式分娄问题不同 多类别模式分类问题中 每个样木可咀 同时被分为嚣i 一个相瓦2 问不排斥的类别 比血n 在由哥伦比亚大学提供的视 频标眭的标准集轻量级的多媒体概念本体数据集l s c o m l 1 曲is c a l ec o n c o 阱 0 n l o l o g y 向rm u i t m e d l a 中 每个视频镜头 曲0 1 或者f 镜头 s u b s h o t 被标记 为3 9 个类别巾的若千个 如罔12 中所示的按l s c 0 m 概念集进行的多媒体标 羹 熙嚣黑 vp e r s o n vs t r e e t 0b 洲d l n g xb e a c h xm o u n t a i n 围l2 准对l s c 0 m 概念进行的视频图表标注的示例 对于示倒巾的视频嘲片 每个都可 以标注多个彼此不持斥的类别 洼 每个视频图片 关键帧都可以被标注为多个彼此不捧斥的类别 更加重要 的是 这些类别之阃并不是独立存在的 他们构成了一个概念集合的奉体r 彼 此之间相互联系 共同来描述多媒体数据中的内容 从另一个方面来说 这些 概念之间存在着相互冗余的信息 上文中所讲的类别之问的互斥和共生芙系 就足这种冗余信息的体现 如何利用这种冗余的信息米提岛标注的准确性和 效率 将足本文要雨点研究的内容 目前已经存在的多类别模式分类算法可以大致分成三人类 第 类办法把所有的概念看成独立存在的单个概念 使用一般的一类分 类器进行单独的建模与分类 将每个样本分成准对各个概念的正例和负 例 这类算法的缺点是完全不考虑概念之间的相互联系 这样一方面没 3 mr 吲 叫刷抓 o m w v v v 第1 章引言 有充分的利用这种联系来提高分类的准确度 另一方面可能导致一下 矛盾的标注结果 比如 由于独立标注各个概念 在一般情况下不会同 时出现的类别就可能被标注在同一段视频上 例如 乡村风景 和 城市 市容 这类方法的代表包括各种二类分类器 比如支持向量机 s u p p o r t v e c t o rm a c h i n e 2 1 流型学习分类器 m a i l i f 0 1 dl e 锄i n gm a c h i n e 6 1 提升分 类器 b o o s t i n gc i a s s i f i e r 7 1 等等 第二类方法则是在第一类方法得到的分类结果基础上进行融合 这种方 法通过挖掘不同类别直接的联系 将独立分类的结果进行融合 使得融 合的分类结果与各个概念直接所具有的关联保持一致 这类方法的代表 包括基于上下文的概念融合算法 c 0 n t e x t u a lb a s e dc o n c e p tf u s i o n 3 两步 辨别模型融合算法 t v o s t 印d i s c r i m i n a t i v em o d e lf u s i o n 8 等 尽管这种 方法结合了概念之间的关联 但是由于它是建立在独立分类器基础之上 的 所以一旦独立分类器的结果存在较大的误差 这种误差就会被传播 到第二步概念融合的步骤里 从而影响最后输出的结果 第三类方法 就是本文将提出的通过挖掘概念之间联系设计的整体分类 器 这种分类器一方面对单个概念与底层特征之间的关系进行建模 同 时利用了概念之间的统计关系来挖掘多种类别的关联性 这种方法将单 个概念的建模和概念之间关系的挖掘建立在同一个框架中 从而有效地 避免了在第二类方法中存在的分类噪声在不同的两步问扩散的问题 在 本文的第二章中 将介绍这样的一种多类别分类算法 1 2 多媒体分析与检索系统的简介及其研究现状 视频是一个源于广播电视业的术语 它由一系列称为 帧 的单个静止图 像前后连续组成的 视频是集图像 声音 文字等为一体的综合性媒体 包含 的信息量大 内涵比较丰富 不仅包含静止图像所有的信息 还包含场景中目 标运动的信息和客观世界随时间变化的信息 近年来 随着计算机硬件 网络 能力以及视频处理软件的发展 视频信息出现了飞速膨胀 新的视频应用 如 数字图书馆 视频点播 数字电视 远程教育等等 已经为越来越多的人所接 受和熟悉 面对飞速膨胀的视频数据 如何找到所需的视频信息就成为一个 急需解决的问题 1 1 4 第1 章引言 视频数据流的一个重要特点就是它有很强的时间结构性 在视频拍摄中 常用到 场景 镜头 之类的概念 导演或创作人员将这些拍摄得到的 镜 头 或 场景 单元组合起来 就是观众最后看到的视频 但是这时候人们看 到的只是 帧帧连续图像 而 镜头 或 场景一等结构层次消失了 如果通 过某种手段能够自动分析出视频数据流中所蕴含的结构 即对视频进行结构 化 可以帮助用户更好的欣赏和管理视频内容 视频结构化就是对视频流中 的连续帧序列进行切分 把一个连续视频流按照其内容展开的不同 分成若 干语义段落单元 视频流的结构化方法能够从一部很长的视频中抽取出隐含 的情节发展结构 它为大数据量视频提供了一种非常好的浏览方式 正如一 本书通常会有目录帮助人们迅速浏览和查询内容一样 一部视频同样需要有 效的索引目录 下面给出在视频结构化的过程中一些基本术语的定义 9 j 帧 f r a m e 帧是视频流的基本组成单元 每一帧就是一幅图像 视频 流就是由连续图像帧构成的 在p a l 制式的视频中 帧速率一般为2 5 帧 秒 在n t s c 制式中 帧速率一般为3 0 帧 秒 镜头 s h o t 镜头是指由摄像机不问断拍摄的一组帧序列 它常被看成 是视频的最小结构单元 一般来说 同一个镜头中的图像帧比较相似 其对应特征基本保持不变 因此 通过发现相邻帧之间较剧烈的特征变 化 可以判断发生了镜头转换 场景 s c e n e 场景是由语义上相关时间上相邻的若干镜头组成 反映 了视频所蕴含的较高层语义内容 如 学校运动会 这个场景可以由 运 动员入场 运动员比赛 和 观众呐喊一等多个镜头组成 形成一个比 较完整的语义表达 在本文中 我们所指的视频检索多指的是在镜头层次上的检索技术 根据用 户提出的查询要求 返回的基本检索单位是一个个视频中的镜头 基于镜头 层次上的检索 既能够帮助用户搜索到视频内部 更加准确迅速地定位到要 寻找的视频片段 又提供了相对具有完整故事情节的视频搜索结果 相对于 返回单个关键帧 用户能够从搜索结果中获得更大的信息 视频检索经历了三个发展阶段 最早的视频检索是人手工对视频内容进 行语义标注 然后通过文本的方法进行检索 该做法费时费力 尤其在目前这 5 第l 章引言 种数据极度膨胀的情况已不可能实现 为了解决这一问题 上世纪九十年代以 来 出现了基于内容的视频检索 1 0 初期的基于内容的检索更准确的说应该 是基于样本的检索 也就是常说的基于样本的查询 q u e r yb ye x a m p l e 该种 方法对查询样本和待查询样本都提取底层视觉 音频和文本信息 然后计算 其相似度进行搜索 然而底层特征与高层语义概念之间存在的 语义鸿沟 阻 碍了该方法的发展 当前视频检索的核心就逐渐转移到通过对视频内容进行 处理 分析和理解以有效获取其内容 使之成为便于搜索 易于交互的数据 视频中的内容包括下面三个方面的信息 感知特征 除了图像所具有的视觉特征 如颜色 纹理等 视频还有表征 运动信息的特征 结构信息 正如 本书通常会有目录帮助人们迅速浏览内容 一部视频 同样需要构造有效的目录 视频目录可以包括镜头 场景等不同层次的 结构信息 语义信息 从视频中自动提取语义描述是非常困难的 这主要是因为难 以建立底层特征与高层语义的联系 同样的难题困扰了人工智能领域多 年 因此 一些研究转而专注于解决特定领域的应用问题 如新闻 体育 等 在这些特定领域 结合相应的领域知识 是可能将底层特征与高层 语义建立某种联系的 在对视频进行搜索之前 首先需要对视频内容进行分析 图1 3 给出了视 频内容分析的一般框架 首先通过镜头检测 将视频序列分割成一个个镜头 然后提取各镜头的各种底层特征 常用的方法是从镜头中选取具有代表性的 关键帧并提取其特征 最后进行镜头检索 可以直接通过图像检索技术对每 个镜头中的关键帧进行检索 也可以利用基于内容的视频标注方法对镜头进 行分析 建立起镜头与概念之间的联系 从而构造有效的视频索引信息以进 行基于上层语义的视频检索 其中 如何高效的进行视频标注是本文研究的 主要内容 1 3 研究动机及内容安排 针对多类别模式分类问题 本文将主要对以下几个方面展开研究 6 第j 章引言 a c t l o e v ct t s s u e o c h t c x t 图13 视颇内辑分析的一般框架1 1 l 多类别模式分类算法 目前太多数的模式分类算法都是基于单类别的 值分类算法 它们没有考虑到多个类别之问普遍存在的相互联系 这就 制约了这种分类算法性能的进一步提岛 在已有的模式识别技术的基础 上 我们希望提出一种能够在分类过程中利用不同类别之间的语义关 系 提高分类准确度的方法 在线多类别模式分类算法 在实际的榆索应用中 随着时间的发展 会 有更多的数据进入到多媒体检索系统中 如何将这些新的数据加入到已 有的系统中是一个在殳践中非常重要的问题 特别是对那些具有很大数 据量的系统 传统的方法是将新的数据与既往的数据故在一起进行重训 练 这种方法会大大提高系统的计算强度 在很多实际系统 i 足很难加 以应用的 在奉文中 我们提出一种在线多类剐学习算法 它不需要进 行重新训练 而只需要在新数据上对已有的模型进行增量式的更新即 可 有用户交互的多类别主动学习算法 主动学习通过模仿人的感知学习机 制 能够在交互式的手工标注过程中选出最具信息量的样本来进行标 7 第l 章引言 注 这样可以使得训练过程更加有效 可以在达到一定分类性能的同时 能大大减少训练集中数据的数量 具体在多类别问题中 我们希望利用 类别之问地关系 进一步减少用户标注数据的交互量 1 4 内容安排和创新点 在本文第二章中 将提出一种基于类别之间关联的多类别模式分类算法 这种算法将单个概念的建模与概念之间关系的挖掘统一在同一个框架下 可 以有效提高对训练集的使用效率并避免概念融合算法中存在的错误传播问 题 在第三章中 本文将提出一种在线增量式多类别模式分类算法 它避免了 每次新样本到来后 需要使用所有历史训练样本重新训练分类器问题 代之 以只需用新到来样本增量式更新相应模型 有效地提高了构建分类器的效率 在第四章中 将一种基于多类别的主动学习算法 它通过挖掘概念之间的联 系 对每个待标注样本找出相应的最关键的类别 大大提高了获得训练集效 率 最后 在第五章中 将总结和展望多类别模式分类技术 并探讨未来可能 的研究方向 8 第2 章 挖掘概念关系的多类别模式分类方法 第2 章挖掘概念关系的多类别模式分类方法 2 1 问题的数学定义 铆 z 1 z 2 z d t 爿是从待分类样本 比如镜头 子镜头或者关键 帧 中抽取的特征向量 j y 1 一1 表示某个样本的k 维类别指示向 量 其中j 的每个维度玑 1 一1 表示这个样本是否具有第i 个概念 十1 表示 属于 一1 表示不属于 另外 本文用刀和y 表示输入特征向量空间和类别指 示向量空间 本章的算法的出发点是学习得到一个线性分类判别函数 f j w h 臼 j 2 1 在这里 伊 是一个从zxy 映射的矢量函数 这个函数既要表示每个单独 的概念与特征之间的关系 也要同时能够表示不同类别概念之间的关系 是 上述线性组合的权重组成的向量 基于这样一个判别函数 对于任意样本对 应的输入特征向量x 该样本由这个判别函数预测的类别指示向勤 为 j 2 学f j 2 2 后面本文将会把这样一个判别函数与g i b b s 随机场 12 联系起来 并将看到以上 的最大化撕 可以通过在随机场上的快速近似算法求出 以上的向量函数曰仁 j 中的元素可以被分成如下的两个部分 分别对单个 类别的概念与底层特征之间的关系 以及概念之间的关系进行建模 i 第一类对单个概念进行建模 醴 p j z d 64 珈 2 l f 十1 一1 1 d d 1 p k 2 3 这里6 蜘 z l 表示指示函数 如果它表示的判别条件成立 则取l 否则 取o d 和k 分别是特征向量和类别指示向量的维数 p y 中的这些元 本章内容的详细版本已发表在 1 1 上 9 第2 章挖掘概念关系的多类别模式分类方法 素用来建立底层向戥和单个类别概念讥 1 七 k 之问的联系 它们 起到和一般的支持向量机类似的作用 但是 仅仅有以上给出的口 中的第一类元素不足以挖掘多类别模式 分类问题中不同类别之间的关系 所以 我们给出如下的第二类元素 i i 这一类元素表示成 口甜 j 6 蜘 m l 6 可口 礼lm n 1 一1 1 p q k 2 4 m 和n 表示正例或负例 即 1 或一1 pa n dq 是不同类别概念的索引 这些元素表示不同类别概念之间的相互作用 注意到 这种表示同 时抓住了概念对之间 正 作用关系和 负 作用关系 比如 正 作用 关系有 b u i l d i n g 和 u f b a n 因为它们同时经常出现 而 负 作用关系 有 e x p l o s i o nf i r c 和 w a t e r s c a p ew a t e m o n t 因为它们一般不会同时出 现 把上述两类元素组合在一起 就可以得到最终的p y 不难看出 p j 的总 维数是2 k d 4 壤 2 k d k 一1 当k 和d 很大时 口 j 的维数将变得 非常大 比如 如果 3 9 和d 2 0 0 那么口 会有1 8 5 6 4 维 这时 我们 可以引入核函数表示两个口 j 和臼 夕 的内积 口 j 口 夕 缸 j 1 七 k6 玑 饥l l p k6 彩l 64 雪 l 2 5 可以看到 由于指示函数64 1 带来的稀疏性 上述内积得到的核函数可以紧凑 地算出 同时 注意到0 动是在底层特征向量空间上的内积 可以引入一个 非线性的核函数 比如高斯核函数 多项式核函数 来代替它 后面将看到 类似于支持向量机算法 在推断和学习判别函数的过程中 仅需用到上述的 内积即可 本文把这个内积函数叫做关联多类别核 c o 仃e l a t i v em u l t i l a b e l 相应的算法叫做关联多类别方法 c o 仃e l a t i v em u l t i l a b e l 简记c m l 2 2 与g i b b s 随机场的关系 本节先给出上一节给出的c m l 模型的一种概率解释 这种解释基 于g i b b s 随机场 g l 心 模型 1 2 通过与g i b b s 随机场的类比 本文给出一种 近似求解公式2 2 的快速算法以预测类别指示向勤 l o 第2 章挖掘概念关系的多类别模式分类方法 图2 1 基于g i b b s 随机场的c m l 模型解释 2 2 1基于g i b b s 随机场的c m l 模型 公式2 1 可以被写成 f j m 口 y p pd p x 和 q 嵋 口 蜘 蜘 x 2 6 和 岛 蜘 x 蜊 1 t 一 以p 2 7 k g 跏 蜘 x 艇 一1 怫 孵 j 这里p 俐1 z 是一个概念索引的有限集合 其中每个p p 表 示一个概念的索引 p g 1 1 p g k 表示所有相互之间有 l 1 第2 章挖掘概念关系的多类别模式分类方法 联系的概念对组成的集合 如图2 1 所示 相应的g r f 有6 个表示概念的节 点 o u t d o o r f a c e p e r s o n p e o p l em a r c h i n g r o a d 和 w a l k i n g 舢1 n i n g 节 点中包括 o u t d o o r p e o p l em a r c h i n g f a c e p e r s o n p e o p l em a r c h i n g w a l k i n g r u m l i n g 这些相互作用的概念节点对 它们都包括在集合 中 具体在本文介 绍的c m l 模型中 将包括所有可能的概念对 并形成一个完全互联的结构 现在我们定义给定一个样本x 的相应的g l 讧的能量函数 日o k 们 一f j 一 账pd p x 慨口 口 跏 x 2 8 这样 对于x 给劫 可以定义概率测度 p k w 2 虿舌j 万e x p 一日 k w 2 9 z w 关y e x p 一日 k 是分割函数 p a n i t i o n f 蚰c t i o n 这种具有指 数形式的概率函数在y 上是严格正的 依据最大化后验概率 m a x i m u ma p o s t e r i o r i 准则 最佳的类别指示向勤可以通过最大化概率测度p k 1 来 得到 这个等价于最小化能量函数日c l x 不难看出 这种准则和最大化公 式2 2 是一致的 所以 c m l 模型与上述定义的g i 疆模型具有可类比性 这样把 公式2 8 代入公式2 9 有 p 比 2 赤n p p 尸 珈眇 州刎a i x 2 1 0 这里 p 跏l x e x p d p 铷 x 昂 口 珈 可q i x e x p 嵋 q 铷 蜘 x 我们可以看到 p 涉k 可以被分解成两种乘法因子 第一种乘子p 蜘i x 给 出了给定样板后 蜘的后验概率 这种因子建立了底层特戤和概念p 之间 的关系 注意到尸 蜘f 神仅包括公式2 3 中的第一类元素 这就说明了这样一 类元素的确仅仅表示了工和各个单独概念之间的关系 同样地 另外一类乘 子昂 坳 i x 建立了不同概念之间的关系 并仅与公式2 4 中定义的特征有 关 上述给出了对上一节中c m l 模型的概率解释 接下来本文基于这种解释 给出一种基于相应g i 江模型针对公式2 2 的快速算法 1 2 第2 章挖掘概念关系的多类别模式分类方法 2 2 2 预测类别指示向量 上面已经介绍 一旦判别函数2 1 确定后 给定一个样杠 最佳的类别指 示向勤 可以根据公式2 2 预测得到 最直接的方法是在y 中枚举所有可能的j 并发现使公式2 2 最大的j 但是 由于3 的规模相对于概念数k 成指数级增长 这种暴力枚举的算法在实际中是行不通的 比如 当 3 9 时 y 的大小将达 到2 3 9 5 5 1 0 1 1 幸运的是 通过c m l 模型和g l 讧模型的类别 最佳 可以 通过相应的概率模型利用快速推断算法得到 比如 模拟退火算法 a i l i l e a l i n g s i m u l a t i o n g i b b s 采样算法 g i b b ss 锄p l i n g 以及最近比较流行的有环嚣信 传播算法 l o o p yb e l i e f p r o p a g a t i o n 期望传播算法 e x p e c t a t i o np r o p a g a t i o n 等等都可以用来得到快速的近似最佳类别指示向量 特别地 结合公式2 5 所 得到的c m l 核 将得到如下的与原始判别函数2 1 对偶的判别函数 其中 f 夕 2 s t n 眶y 啦涉2 仇涉 口 夕 2 1 1 p pd p 跏 x 慨口 k q 蜘 贾 4 彩 牙 1 逛竹骶yq l 后 戤 孟 j4 蛳 翰l 一6 坳 彩1 髟 口 彩 吼 雪 1 i n y 啦 秒 j 弘 彩l j 慨口 吼i j 翰 彩l j 玩1 2 1 2 于是司以得到对偶能量函数是 疗眵恳w 一 p p 岛 彩 贾 p 叮 g 彩 玩 元 2 1 3 相应的g i 强的概率形式是 删 赤e x p 2 1 4 其中2 k y e x p 一疗9 阮w 是对偶能量函数的分割函数 这样 就 可以直接利用针对随机场的推理方法得到有效地近似解 1 2 1 比如迭代条件模 式 i t e r a t e dc o n d i t i o n a lm o d e s 模拟退火算法 知m e a l i n gs i i i l u l a t i o n g i b b s 采 样算法 g i b b ss a m p l i n g 有环置信传播算法 l o o p yb e l i e f p r o p a g a t i o n 期望 传播算法 e x p e c t a t i o np r o p a g a t i o n 第2 章挖掘概念关系的多类别模式分类方法 2 2 3 判别函数的学习 本节介绍如何利用核函数2 5 来训练分类判别函数2 1 以下学习过程和 一般的支持向量机算法 1 3 1 以及最近提出的结构支持向量机 1 4 是类似的 给 定训练集似 以 翟l 其慨是相应样本溉的真实类别指示向量 于是根据公 式2 1 和2 2 当如下条件成立时 将会出现一次误分类 ec l 全f 置 欺 一f 托 j h 巩涉 o 砂 鼽 y y 2 1 5 其中 吼涉 p 以 一口 j 于是 给定一组参数 后 在训练集上的经验 预测误差就是 a 似 j t w 熹 兰 涨y j 2 1 6 这里笆k j 是一个计算错误的损失函数 y w 嵋觚 o 跏 此 j y 我们的目标是求出一个参数w 以最小化经验误差兑 似 此 鍪1 w 考虑到 计算上的效率 在实际应用中 本文使用如下的凸损失函数 它是笆 j w 的 一个上界 阮 j 1 一 吼涉 2 1 8 其中 是一个分类 枢纽 损失函数 相应的 可以得到如下的经验损失风 险 同样地 它是座 他 耽 墨1 的一个上界 怠 似 舷 旨w 熹 三 e 觏删靠 洲w 2 1 9 为了避免 过拟合 引入一个正则化项q 1 f w f 2 并相应地得到正则化后的损 失函数氟 豉 整l w 于是有 鼍 n 氟 翰 耽 翟1 w a q 1 1 w l l 2 2 2 0 炒l j 这里q 是一个严格单调增的函数 a 是一个权重经验损失和正则化项的参 数 类似于 1 3 这样的正则化项能够平滑最终得到的函数以减少训练集中噪 1 4 第2 章 挖掘概念关系的多类别模式分类方法 声的影响 在实践中 上述的屉优化问题可以通过二次凸优化来解决 对每 个 y 引入松弛变量已少 优化问题2 2 0 可以被改写成 m i n w 1 1 w l l 2 害 竺l j 和 y 2 2 1 s w 仇 1 一已 6 涉 吵 舷 j y 引入拉格朗日乘予啦涉 可以得到相应的拉格朗日对偶问题 m a x a t 涉 一三 q t 涉 眵 吼涉 岛眵 s o 叽 yq t 害 j 职 j y 1 t 几 2 2 2 并且 一 q l 仇o 2 2 3 z 一1 s t s n 具体优化过程中维护一个活动集 对于每个溉 它里面包含最违反上述约束的 相应类别指示向勤 矿 甜g m 嬲曲 f j w 和 r 涉 1 这个活动集 中的所有陬 辨 在每次求解过程中用来构造2 2 2 中的约束 2 3 实验结果 本节在标准数据集t r e c v i d 上实验上述c m l 算法 并与目前流行的其他 方法进行比较 2 3 1t r e c v i d 数据集简介 本节在t i 也c v l d2 0 0 5 数据集 1 6 上进行对比实验 t i