（信号与信息处理专业论文）基于转导推理思想的一致性预测器.pdf

基于转导推理思想的一致性预测器 捅要 当前存在的一些机器学习分类算法多是建立在归纳、演绎逻辑推理的方法基 础之上，面对一批数据总是试图从中提取一个适用的通用分类模型，并期望此分 类模型有较高的预测性能；但是这种分类模式在高风险、小样本领域却有一定的 局限性：首先基于数量有限的小样本数据，用于归纳个通用规则的训练样本数 据较少，造成分类模型的准确度较低，而且忽略了测试集样本的信息，从而不能 充分利用所有样本数据信息；其次分类预测结果通常只是简单的将样本划分为某 一类，对样本多大程度上属于这一类没有一个量的概念，且预测结果没有置信度 衡量，在高风险领域的应用尚有不足。 本文对基于转导推理的一致性预测算法的研究就是针对此局限性而展开的。 转导推理是基于整个样本所拥有的全部信息直接进行分类识别的原则方法，分类 过程中不需归纳分类模型，而是通过探索待测数据和样本序列之间的内在联系而 进行推理判别；算法是通过k o l m o g o r o v 算法随机性理论建立一种置信度机制， 通过随机性检测函数对置信度迸行估算，且随机性检测函数的结果就是预测结果 的可信度，同时在置信度控制下其算法预测结果是域的形式。 一致性预测算法的核心部分是非一致性度量函数的设计，设计非一致性度量 函数可以融合现有分类算法进行。本文首先对k 近邻一致性预测算法和支持向量 机一致性预测算法进行研究，并在k 近邻一致性预测算法的基础上进行改进，提 出用测地线距离来代替欧式距离度量样本间相似性；然后基于逻辑回归模型实现 了基于l o g i s t i c 回归的一致性预测算法；本文所有算法都是基于m a t l a b r 2 0 0 7 b 平台实现，并基于多种标准数据集和实际应用领域的烟草行业数据进行仿真实 验，同时和w e k a 平台下的一些分类算法的分类预测率进行比对分析，来验证一 致性预测算法的性能。 本文最后对研究工作进行了总结，并指出了今后进一步的研究方向。 关键词：一致性预测器；转导推理；算法随机性理论：非一致性度量；测地线距 离；l o g is t i c 回归 c o n f o r m aip r e dic t o rb a s e do nt r a n s d u c t io n a b s t r a c t s o m ec l a s s i f i c a t i o na l g o r i t h mi nm a c h i n el e a r n i n ga r eb a s e do ni n d u c t i o na n d d e d u c t i o n ，w h e nf a c i n gt oa b a t c ho fd a t a ，t h e ya r ea l w a y st r y i n gt oe x t r a c tag e n e r a l c l a s s i f i c a t i o nm o d e lf o rt h o s ed a t a , a n de x p e c tt h ec l a s s i f i c a t i o nm o d e lh a sh i g h e r p r e d i c t i o np e r f o r m a n c e ；b u ti nh i g h - r i s ka n ds m a l ls a m p l ef i e l d s ，t h i sc l a s s i f i c a t i o n m o d e lh a v es o m el i m i t a t i o n s ：f i r s t l y , b e c a u s eo ft h el i m i t a t i o no f t h en u m b e ro fs m a l l s a m p i ed a t a , t h i sc l a s s i f i c a t i o n m o d e ln o to n l yd i d n th a v ee n o u g hd a t au s e df o r e x t r a c tag e n e r a lr u l e ，b u ta l s oc a l ln o tm a k ef u l lu s eo fa l lt h ei n f o r m a t i o no fs a m p l e d a t a ；s e c o n d l yt h er e s u l t so fc l a s s i f i c a t i o np r e d i c t i o na r ej u s ts i m p l et ou s ，a n dt h e r e s u l t sh a v en oc o n f i d e n c eo rb e l i e v a b i l i t yt om e a s u r e i nt h i sp a p e rt h er e s e a r c ha n da p p l i c a t i o no fc o n f o r m a lp r e d i c t o rb a s e do n t r a n s d u c t i o ni sa i m e da tt h i sd e f e c tt ol a u n c h t r a n s d u c t i v ei n f e r e n c ei sd i r e c t l yt o c l a s s i f ya n dr e c o g n i z ef 0 rt h ed a t as e t s w i t ht h ew h o l es a m p l ei n f o r m a t i o n , a n di t d o e s n tn e e dt ob u i l dc l a s s i f i c a t i o nm o d e li nt h ep r o c e s so fc l a s s i f i c a t i o n , i t st a r g e ti s t oe x p l o r et h ei n n e rr e l a t i o nb e t w e e nt e s t e ds a m p l ed a t aa n ds a m p l es e q u e n c e ；t h e c o n f o r m a lp r e d i c t o rb u i l d ac o n f i d e n c em e c h a n i s mt h r o u g ht h ek o l m o g o r o v a l g o r i t h mr a n d o m n e s st h e o r y , a n du s e t h ed e t e c tf u n c t i o no fr a n d o m n e s sw h o s e r e s u l t sa r et h er e l i a b i l i t yo fp r e d i c t i o n , t om e a s u r et h ec o n f i d e n c e ，a n dt h ef o r mo f r e s u l t sp r e d i c t e db ya l g o r i t h mu n d e rt h ec o n t r o lo fc o n f i d e n c ea r ed o m a i n t h em a i n l yp a r to fc o n f o r m a lp r e d i c t o r i s t o d e s i g nt h e f u n c t i o no f n o n c o n f o r m i t ym e a s u r e , w h i c hc a n b ei n t e g r a t e dc l a s s i f i c a t i o na l g o r i t h mi nt r a d i t i o n a l m a c h i n el e a r n i n g i nt h i sp a p e r , f i r s t l yt h ec o n f o r m a lp r e d i c t i o na l g o r i t h r nb a s e d 0 1 1 k - n e a r e s tn e i g h b o ra n ds u p p o r tv e c t o rm a c h i n ea r ed i s e n s s e d ，a n dt h ec o n f o r m a l p r e d i c t i o na l g o r i t h mb a s e do nk - n e a r e s tn e i g h b o r i si m p r o v e d ，t h r o u g hu s i n gg e o d e s i c d i s t a n c et or e p l a c ee u c l i d e a nd i s t a n c et om e a s u r et h es i m i l a r i t yb e t w e e ns a m p l e s ； t h e nt h ec o n f o r m a lp r e d i c t i o na l g o r i t h mb a s e do i ll o g i s t i cr e g r e s s i o nm o d e lc a l lb e a c h i e v e d ；a l la l g o r i t h m s i n t h i s p a p e ra r ep r o g r a m m e d o nt h e p l a t f o r m o f m a t l a b r 2 0 0 7 b ，a n db eu s e dt ot h ed a t as e t sf r o mu c ia n dt o b a c c oi n d u s t r y , a n d l i i t h r o u g ht h ec o m p a r i s o no fa c c u r a c yr a t ep r e d i c t e db yc o n f o r m a lp r e d i c t i o na l g o r i t h m a n do t h e ra l g o r i t h mu s e du s u a l l yt ot e s tt h ep e r f o r m a n c eo fc o n f o r m a lp r e d i c t i o n a l g o r i t h m i nt h ee n d ，t h et h e s i ss u m m a r i z e st h er e s e a r c ha n di n d i c a t e st h ef u t u r ew o r k k e y w o r d s ：c o n f o r m a lp r e d i c t o r , t r a n s d u c t i o n ，a l g o r i t h mr a n d o m n e s st h e o r y , n o n c o n f o r m i t ym e a s u r e ，g e o d e s i cd i s t a n c e ，l o g i s t i cr e g r e s s i o n i v 基f 转导推理恐想的一致惟预测器 l 概论 1 1 选题背景及研究意义 分类是数据挖掘【1 1 和机器学习【2 1 中一项很重要的数据分析技术，其主要目的 就是对于未知类别具体事物，根据已知类别的数据信息，可以将其正确划分到某 一类，从而对未知事物有一个大致的掌握和学习。现实生活中可以将很多问题转 化为分类问题，如手写体识别、图像识别、网络入侵检测、机械故障诊断、文本 分类、网络数据分析、股市市场预测、卷烟配方、故障诊断等等。机器学习基于 分类问题已经发展了很多成熟的算法如有决策树、神经网络、朴素贝叶斯方法， 还有经常用到的最近邻分类器和支持向量机等等，可供人们用于解决多种分类问 题。机器学习里的分类问题大致可以分为以下几步： 1 ) 首先将现有的已知类别信息的数据集分成训练数据集和测试数据集两部 分； 2 ) 然后根据给定的训练样本的信息，通过分类算法构造并训练一个分类模 型对数据进行描述，同时用测试样本集对新构造的分类器进行预测检验； 3 ) 测试合格后的分类模型即可用于未知类别的数据进行预测分类，辅助分 析未知数据。 可以归纳为：对类别已确定数据建立数学模型；用数学模型对未知类别数据 分类。这就是传统分类学习的般步骤，其建模的过程就是归纳推理的过程，即 从个别性信息归纳出一般性的规则；预测过程即为演绎的过程，即从一般性的规 则推理出个别性的事实，上面提到的支持向量机，k 近邻【l 】等算法大都围绕这种 归纳推理模式形成。但这些分类算法大都有一个共同点，那就是：将未知数据判 断分为某一类时，对判断结果的可信程度无法提供一个度量值；也就是说通过预 测准则对未知数据的判断预测其类别时，其判断的结果到底有多大的准确性，我 们是无从得知的：尽管随训练集的丰富，这些预测准确的概率会变大，可能近似 正确，但这些分类算法只能给出“是 或“非”两种简单且绝对的判断结果。 当面对故障诊断、医疗诊断、金融分析决策等高风险、小样本重要应用场合 问题时，面对这些分类算法给出的简单结果，显然不够有信心；而且这些基于归 基于转导推理思想的一致性预测器 纳推理上的分类模型的高准确度是需要大量数据集去训练拟合得到，但实际上高 风险小样本的数据量本身已经很少，倘若再分为训练集和测试集归纳出一个一般 的分类准则，那么这个准则的可利用性就会大大打折扣。倘若在进行模式分类预 测的同时，还能给出该次预测结果的可信程度，对其判断结果的准确性有一个量 的度量，那么对于这些高风险小样本领域来说无疑有着重大的意义。针对这种情 况发展起来的一致性预测器在判断样本类别的同时，还可以对该次判断结果提供 相应的可信程度。 一致性预测器【3 】( c o n f o r m a lp r e d i c t o r ；简称c p ) 是一种新的机器学习分类 模式，它建立在转导推理基础上，以算法随机性理论为技术基础，且本身算法的 核心部分( 非一致性度量函数) 可以基于传统分类学习方法来设计与实现；一致 性预测算法可以充分利用已知类标签样本和未知类标签样本之间的内在联系来 进行预测，其预测结果带有置信度分析，丰富了输出结果的有效信息，可应用于 高风险、小样本领域，来辅助人们对预测结果进行分析定论。 1 2 国内外研究现状 基于转导推理机制的一致性预测器是由英国伦敦大学哈勒维学院机器学习 研究中心的v l a d i m i rv o v k 、a l e xg e r m a n m a n 、g l e n ns h a f e r 等学者组成的一个研 究小组发展起来的；从1 9 9 8 年v l a d i m i rv 0 v k 和a l e xg e r m a n m a n 研究转导推理 学习【5 】的算法原理和适用性开始，并且提出了结合s v m 实现转导学y - - j 1 6 1 的方法， 即通过穷举测试数据所有可能类别实现转导推理预测，至此国内外研究者关于一 致性预测算法研究及其应用已经贡献了一些文献，但大部分的文献还是由v o v k 及其同事等人完成的，主要文献有( ( a l g o r i t h m i cl e a r n i n gi nar a n d o mw o r l d ) ) 忉、 ( ( t r a n s d u c t i o nw i t hc o n f i d e n c ea n dc r e d i b i l i t y 【8 】、( ( l e a r n i n gb yt r a n s d u c t i o n ) ) 【5 1 、 ( ( t u t o r i a lo nc o n f o r m a lp r e d i c t i o n ) ) 1 9 等；除此外还有m a r c e l om s i l v a 等用进化 计算进行转导支持向量机学y - - j 1 0 】；l i a n g c a is h u 等提出了一种带权重的近邻转导 学习机【l l 】等。 国内对一致性预测器的研究文献相对来说还比较少，主要研究成果有北京大 学陈毅松、汪国平等人研究的基于支持向量机的渐进直推式分类学习算法【1 2 】： 华中科技大学的邱德红、陈传波等人对基于算法随机性理论和奇异描述的置信学 2 基r 转导推理思想的一致性预测器 习机【1 3 】【1 4 1 的研究，并应用于签名认证取得了较好的效果；马琳等人设计的基于 转导的预测算法并在软件性能测试中做了应用验证【巧】；还有厦门大学王华珍博 士及其同事也对基于转导机制的一致性预测器有较深的研究，如在带置信度分类 器的研究与应用中提出了混合压缩一致性预测器，提高了运算效率。 1 3 论文组织结构 本文第一章介绍一致性预测算法的研究背景和意义，及目前国内外对此算法 的研究现状。 第二章详细论述一致性预测算法的推理基础、技术基础，及整个算法的内容 介绍。 第三章研究基于k 近邻算法设计非一致性度量函数，并在此基础上对算法进 行改进，所得的算法与其他机器学习分类算法的预测性能进行对比分析。 第四章研究基于支持向量机设计非一致性度量函数，将实现的算法应用于标 准数据集和实际烟草工业领域，验证其算法性能。 第五章主要研究基于l o g i s t i c 回归的一致性预测算法，并对算法进行仿真实 验。 最后一章总结论文中的主要工作和结论，并对进一步的工作方向做了展望。 3 基于转导推理思想的一致性预测器 2 一致性预测算法概述 2 1 转导推理和归纳推理 学习策略是机器学习的分类过程中的一个阶段，就是指学习中使用的推理方 法，机器学习 2 1 中常见的几种学习策略有类比学习、演绎学习、归纳学习等；所 谓归纳学习【1 7 1 ，就是系统根据有关的数据或实例，应用归纳推理抽象出一般性 的规律或结论；机器学习中的某些分类方法就是建立在归纳推理的基础上，如经 典的决策树算法等。归纳推理的一般模型如图2 1 所示： 前提结论 “j 嗨 ” 假设”、： 事实j ： ? ； 理论 ，+ 观察信息 归纳推理、 。” ”莎 规则 “ 测量信息 n 。、。 n 演绎推理 命题 经验数据。 算法 ，一 图2 - 1 归纳推理模型图 传统的归纳式学习中，学习机根据已知标签数据归纳出一个判别函数，使得 它对整个样本空间可能的分布有一个尽可能小的期望判别误差，即得到一个分类 器，而演绎过程则是通过将待预测的数据输入到该分类器中，从而得到其标签。 转导推理【5 】【7 】( 也成直推) 不同于归纳和演绎推理，其区别如图2 2 所示： 图2 - 2 转导推理和归纳推理区别图 关于归纳的数学结果通常涉及两个参数，常记作s ( 预测规则的期望精确度) 4 基于转导推理思想的致性预测器 和万( 达到精确度占的概率) ，但关于转导的数学结果只有一个参数，我们记作g ( 即能够容忍的误差概率) 。 可以看到转导推理是一种直接从训练集样本出发对未知样本进行分类，其核 心思想就是探索有标签训练样本和无标签测试数据之间的内在联系，利用无标签 测试数据的分布信息，从而尽可能的挖掘出全体样本空间分布信息【l 引。 基于归纳式学习形成的分类算法总是试图根据训练集样本信息归纳出一个 判别函数，使得这个函数在整个样本空间分布中有一个尽可能小的期望判别误 差。但是实际应用过程中，人们往往并非对整个样本空间感兴趣，相反只是想研 究某些感兴趣的数据，尤其在高风险、小样本的研究领域中，能够供研究的数据 本来就很少，这种基于归纳式推理的分类学习算法困难性就增大；而转导推理却 可以掌握所要测试的数据的一些信息，从而把特定测试数据的信息有机的加入到 推理分类过程中，因此所做的判断将更有依据；而且它不用针对所有样本寻找分 类模型，因此运算的复杂度相对来说也较低。 2 2 随机性理论 2 2 1 算法复杂性 算法复杂性【1 9 】( a l g o r i t h m i cc o m p l e x i t y ) 最早由s o l o m o n o f f , k o l m o g o r o v 和c h a i t i n 在2 0 世纪6 0 年代中期分别独立提出的概念，又称为k o l m o g o r o v 复杂 性【2 0 1 ，它用程序长度来定义描述信息量，其中有一种定义形式如下： 定义：若对于给定的字符串x ，输出该字符串的二迸制程序的最短代码长度 为y ( 功，那么字符串x 的k o l m o g o r o v 复杂度就为y ( 力，将输出x 的一串二进制 代码组成的程序叫做x 的一种描述，将描述中长度最短的叫做最小描述。 首先看一下规律性和可压缩性【2 】： 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1l1 0 0 0 1 0 l1 0 0 11 0 0 0 111 0 1 0 1 假设有上述两个序列，每个序列都由0 1 组成，可以看到序列一是有规律可 5 基于转导推理思想的一致性预测器 循的，总是0 l 的顺序排列，那么就可以说这个序列是可压缩的，对它的描述相 对于序列一本身要简单；序列二则看起来比较随机，其排列不具备规律性，则序 列二就不能对其压缩，而且对序列二的描述就跟它本身没有显著的差别。其实要 对序列进行描述，实质就是找出能输出该序列的最短程序，而这个最短程序的长 度就可作为其可压缩性的度量。当然对一个对象序列的描述可以有很多，但只有 把其中最短长度的描述称为这一对象的复杂度；k o l m o g o r o v 把数据串的复杂性 定义为计算机产生这个数据串所需的最短二元程序的长度，因此k o l m o g o r o v 复 杂性理论可以看成一种算法复杂性，它对应于程序的长度。 图灵机【2 2 】【2 3 】本质上是从有限长二元数据串集合到有限或无线长二元数据串 集合的一个映射，它是一种能运行任何程序的假象机：它通过一个读写指针，处 理一条线性方格列的字节，如果它停机了，就输出一个序列，于是每个图灵机便 定义一个部分函数，这个函数被称为是“部分递归的 或者是“可计算的 ；如 果计算的函数在所有的输入上都有定义，即图灵机对所有的输入都停机，则称之 为“全递归”，那么对图灵机的算法描述可定义为： 定义：给定一图灵机u ，如果u 在二进制序列p 和一个附加的二进制少的 输入下，停机输出为x ，那么p 就是x 的最短描述，记为u ( p ，f ) = x 。 k o l m o g o r o v 复杂性【2 0 】指的是：对于数据x ，p 是在数据少给定条件下能使 图灵机u 输出x 的程序的集合，( p ) 是尸中程序p 的长度，则在这些程序集合 中，最短程序的长度就被定义为在条件y 下的算法复杂性，表示为： k c ( x l y ) = m i n l ( p ) ( 2 1 ) t m p , u ( p , y ) - - x x 的无条件k o l m o g o r o v 复杂性定义为： q ( x ) = q ( x i 五) ( 2 2 ) 根据图灵机理论，任何二进制序列对象x 都可以用图灵机进行算法描述，而 对象x 的算法描述取决于特定图灵机u 的选择，如果它成立，那么将没有有效的 方法来描述序列的k o l m o g o r o v 复杂性了，但k o l m o g o r o v 等人已经证明了。种 通用图灵机的存在，通用图灵机可以模拟其他任何图灵机的行为。 6 基丁转导推理思想的一致性预测器 2 2 2 算法随机性 算法复杂性的应用非常广泛，但实际上分析实际复杂系统时，算法复杂性并 不具有很好的实用性，主要原因如下： 1 ) 算法复杂性往往是不可计算的，或不能精确计算而只能去上界逼近； 2 l 算法复杂性在一定意义上是随机性的度量，它认为一个随机事物具有最 大复杂性，即高度有序和完全无序都对应于很小的复杂性，也就是说复 杂性总体上应是单峰的，如图2 3 ： 翅 礤 蛾 无序性 图2 - 3 复杂性无序性的概率曲线 因为算法复杂性不可计算，但仍然可以通过一定方式去寻求对象x 的最短描 述序列，瑞典数学家m a r t i n l 6 f 找到了一种可行方法【2 4 】【2 5 1 ，采用统计学的假设 检验方法来描述序列的算法复杂性( 即k o l m o g o r o v 复杂性) ，其算法思路大致 如下： 定义d 可压缩：给定一正常数c ，如果满足c ( 功z ( 力- - c ，那么便称序列 x 是c 可压缩的；其中l ( x ) 是序列x 的长度。 不可压缩的序列是无规律可循的，否则就可用规律性来减少它的描述长度； 而一般无规律可循的序列是随机的，且算法复杂性本身一定意义上是随机性的度 量，所以可将不可压缩序列等同于随机序列。 定义：如果一序列是不可压缩的，那么就称此序列具有算法随机性。 因此可从随机性角度来说明对象的描述序列的可压缩性， 算法随机性：一个非l 一可压缩序列是不可压缩的，它具有算法随机性。 从算法描述原理看，对象的描述序列还具有两个结论：存在任意长度的算法随机 7 基于转导推理思想的一致性预测器 序列；大多数序列是不可压缩的。 2 2 3 算法随机性检测 测试序列的随机性，其实质就是检验序列是否真正随机，或者与真正随机间 的差距，假设检验【2 6 】【2 7 1 是随机性检测的理论基础。首先提出一个待检测的假设， 记为零假设或原假设，记为鼠，同时提出一个备选假设q ，这个假设是与原假 设相反的；对于检验序列的随机性，我们提出原假设鼠为：序列是随机的，备 选假设且为：序列非随机；当我们说样本是从某一分布中随机抽取，即为样本 在概率理论意义上独立的，且都有相同的分布，也即独立同分布，我们称之为随 机性假设；其假设检验的结果是接受原假设或备选假设，也就是说检验序列是随 机的还是非随机的。具体步骤可总结如下： 步骤l ：提出原假设鼠和备选假设e ； 步骤2 ：选择合适的统计量x ，构造检验统计量，计算检验统计量的样本观 测值； 步骤3 ：按给定的显著性水平a ，查统计量所对应分布的分位数表，找出临 界值，确定拒绝域； 步骤4 ：将由样本计算出的检验统计量的值与查到的临界值进行比较，如果 统计量的值落入了拒绝域，则拒绝原假设，接受备选假设q ，反之接受鼠， 拒绝鼠。通常用门限值和p v a l u e 1 直 2 刀两种方法来衡量随机性，本文讨论的随 机性测试选择p v a l u e 法，即通过选取的测试统计量来计算p - v a l u e 值，将 p v a l u e 值和显著性水平口进行比较，如果p 一比口，则接受原假设，即序 列是随机的，反之序列非随机。 m a r t i n - l b f 博士在k o l m o g o r o v 算法随机性理论上作了进一步研究，实现了 对算法随机性进行检测1 2 5 】，其定义如下： m a r t i n l 6 f 随机性测试定理：设尸是含有”个元素的序列集合b 甩上的概率 分布，对于序列空间中的元素工，一个全函数万：b 刀斗u o 。) 是一个m a r t i n l 皋于转导推理思想的一致性预测器 6 f 随机性测试，如果对于所有的n ，m n 满足： 1 ) 5 是可枚举的( 集合v = ( m ，工) n x b ”：6 ( 石) 历) 是递归可枚举的) ； 2 ) p x b “：万( z ) 脚) 2 一m 。 上述定义的第一条要求表明测试函数万是递归可计算的，即集合 ： 圪= ( 优，x ) n xb 一：万( 工) m ) 是递归可枚举的：第二条则表明规律性数量 是用位来度量的，而且每个额外位等同于展示规律性的序列数量，万( 力值称为随 机性缺失度，其值越大，序列随机性越小。 定义：对于每种p 测试万，给定一个常数c ，对于所有的x ，如果存在测试 磊( i p ) 满足8 0 ( x l e ) _ a ( x ) - c ，那么称戍( l p ) 为通用p - 测试。 在m a r t i n l s f 随机性测试定理中，显然万是可枚举的，如果万( 功m ，其中 z ( 功= n 2 m ，那么x 的长有2 肘1 种可能，x 的其他部分有2 “_ 2 卅1 ) 种可能，因此 可能总数为d x ：5 ( x ) m ，l ( x ) = n ) 2 ”，或者x 的可能总数为2 ”，综合所述得 到万是尸测试；m a r t i n l 6 f 证明了p 测试的存在，在此基础上m a r t i n l s f 检验 可以修正为p 一测试检验函数【8 1 2 8 1 ，即采用p 一觑e 法对随机性进行测试；p 值 函数的定义如下： 序列的随机性p 值函数：设尸是含有力个元素的序列集合( 样本空间) b 以上 的概率分布，函数p ：b ”j ( o ，1 】是值函数，如果对于所有的，l n ，g ( o ，1 】满 足： 1 ) p 是可枚举的； 2 ) p x b “：p ( 工) 占) s 这个随机性p 值函数是通用的，那么在此函数的基础上就可以发展一致性预 测器算法的描述函数。 9 基于转导推理思想的一致性预测器 2 3 一致性预测器相关内容介绍 由上面章节我们得知，转导推理可以只是对感兴趣的样本数据进行分析判 断，不需要在整体样本空间上归结出分类判别函数，而是直接从已知标签样本数 据出发对未知测试样本数据进行分类，来探索有标签训练样本和无标签测试数据 之间的内在联系，也即其目标就是以尽可能少的错误对某一给定的未知测试样本 数据进行分类；对于样本均来自于某个可计算概率分布p 的独立同分布样本序 列，k o l m o g o r o v 算法随机性理论就是定义一个随机性检测函数来描述样本序列 的随机性，其检测函数的输出结果反映样本序列在多大程度上是由概率分布为p 的随机模型产生的序列。一致性预测器就是建立在这两个理论基础上发展而来 的，本章节主要详述一致性预测器算法内掣7 】和流程。 2 3 1可交换性 首先假设样本由( 五，乃) ，( 而，y 2 ) 组成，每一个样本( 五，乃) 包括对象五和它的 类标签儿；对象葺是对象空间x 里的元素，类标签咒是标签空间y 里的元素，x 与y 都是可度量的。 假设x 非空，且y 至少包含两个不同的元素，那么我们就将( 葺，乃) 设为刁， 则把样本空间z 设置如下： z 一x y ( 2 3 ) 那么无限数据序列( 毛，乃) ，( 屯，奶) 即为可度量集z 。里的元素。 在空间z 上，选择一些来自概率分布为p 的且相互独立的样本，即z l ，z 2 ，是 来自z ”中的概率分布为p 的样本序列；一致性预测算法的前提假设就是序列随 机性，或者说是样本独立同分布，对样本序列毛，z 2 ，此处只需要一个相比序 列随机性要弱一些的假设，即： 来自样本空间z 上且分布为p 的样本序列( 五，乃) ，( 而，耽) ，也即z 1 乞，具 有可交换性。 可交换性即是说，对每一个正整数，z ，在1 到胛之间的元素的任一交换，都 1 n 基了二转导推理思想的一致性预测器 有以下公式成立： p “z l 乞，- j 三：；离：乞z 2 ：是z 等j 。磊。，磊。2 矿一磊。n ，e ，c 2 4 ， = p ( z l ， ，) 田：( 磊( 1 ) ，磊( 2 ) ，磊( n ) ) 其中交换后的样本为乙( 。) ，且样本空间e cz 刀；也就是说无论样本的排列 顺序如何都不影响其概率分布。 2 3 2 预测器的简单形式 如果我们只是想简单预测只，则需要这样一个函数，使得 d ：z x 一】r ( 2 5 ) 那么就将这个函数d 称之为简单预测函数( 或者说简单预测器) ，当然也假 设它是可测的，或者说可度量的；如已知类标的样本序列五，m ，吒1 ，一l z ， 未知类标的新样本艺x ( x 是对象空间) ，则对新样本类标签儿的预测， 给出简单预测函数d ( 五，y l ，小以- l ，毛) y 。 对于预测，通常某些分类算法只是选择标签空间y 中的某一单一元素作为以 的值，但我们更希望预测结果由或多或少的几个元素组成，而且每个元素带有一 个置信度的概念，使其说明被判断为某一值的程度大小。 假设标签空间y 的子集足够大，保证以会被包含在其间，同时给出不能保证 咒是否包含其内的样本空间；设置参数s ( o ，1 ) 作为显著性水平，则互补值1 一s 记为置信度水平；对于所有输入西，乃，- l ，- l ，毛，s ，我们希望有这样一个算 法r ，可以对输入的样本数据序列输出y 的一个子集： r 占“，乃，而- l ，此- l ，) ( 2 - 6 ) 且对于参数占，当q 乞，r 需满足下式： r 毛( 西，乃，毛- l 以1 ，) r 免( 五，咒，- l ，儿- l ，毛) ( 2 7 ) 直观上来看，在显著性水平g 下，算法r 对输入的样本数据序列 五，y l ，毛1 ，儿_ l ，的预测为y 。r ( 一，m ，毛巾y 柚，) ， 且有占值越小，其预 1 l 基于转导推理思想的一致性预测器 测的置信度越高，根据公式( 2 7 ) ，那么预测输出的子集规模也就越大，预测的 置信度也就越高；比如说儿的值包括 一l ，+ 1 ) ，那么输出子集为 一l ，+ 1 ) 的置信度 肯定要比输出子集为 + 1 ) 或者是 一1 ) 的置信度要高。 综合所述，对于任意正整数甩，样本数据序列五，乃，书咒- p 吒，在所有显 著性水平q 岛下，把满足( 2 7 ) 式的度量函数 擘， r ：z 。x x x ( o ，1 ) 专2 7 ( 2 - 8 ) 称为预测函数，或者说是预测器m ，其中2 y 是y 所有子集的集合；r 是可测的的 是指在任意，z 下，满足以e r 占( 五，咒，吒4 ，以- l ，) 的数据序列集s ，玉，乃，毛，只 是( 0 ，1 ) x ( x y ) “的可测子集。 2 3 3 有效性 在显著性水平g 下，对于此的预测我们希望有l - s 的置信度，即预测错误的 概率为g ；此外，对于预测样本序列( 五，乃，毛中咒小) ，其中类标签只，因 为咒属于标签空间y 中的任一可能值，取值从m 开始，然后此，乃，每取一 个值就组成一个新的样本序列，依次进行穷举每一个可能的类标签，则组成不同 的预测样本序列： ( 西，乃，毛1 ，咒- 1 ，弗) ，( 五，乃，- l ，儿- l ，吒，耽) ， 那么对所有预测序列，我们希望预测所得的误差是相互独立的。 如果任意置换具有可交换性的样本序列，所得预测误差依然相互独立的话， 那么我们就说预测器r 是“完全有效的【7 】【9 】，此处的序列可交换性是预测器有 效的一个前提；如果误差概率允许小于显著性水平占，那么就称预测器f 是“保 守有效的。 如进行独立投掷硬币实验时，依据大数法则，若出现正面的概率为s ，则出 现正面的频率会依概率收敛于占；那么“完全有效的”预测器在显著性水平g 下 的误差频率就会依概率收敛于占；据此预测器即便不完全有效，也会“渐进完全 1 2 基于转导推理思想的一致r ：颅测器 的，所以称误差频率依概率渐进于且不超过( 即误差频率上限不超过) 的预 测器为“渐进保守有效”。 定义在显著性水平s 下，预测器r 处理预测样本序列缈= “，y l ，恐，y ：，) 产生 的误差可用0 和1 表示，当只不包含在r 的输出时，就说f 预测产生误差则用1 表示，没产生误差时用0 表示，那么在第刀次试验，r 产生误差可表示为： 啪翮：= 0 糍y 稚l ，昧l ，协9 ) 且前聆次试验的总误差值为： e r r f ( r ，国) ：e r r f ( r ，缈) ( 2 1 0 ) 如果国来自于可交换性概率分布p ，那么对于指定的随机变量e 群( r ，d ，其实 际值为e r c ( r ，国) ，对任意s ， e r 噌讴，n ，e r 4 ( r ，n ， 是一个带参数占的且独立的伯努利随机变量序列；如果它是值为1 时概率为g ， 为0 的概率为1 一占独立随机参数序列，那么不管彩来自于什么样的可交换概率分 布p ，我们就说预测器r 是“完全有效的”，但是“完全有效”对于预测器却无 意义，因为： 定理：不存在完全有效的预测器。 保守有效性的概念更复杂；现在只要求孵( r ，尸) 是由带参数占的独立伯努 利随机变量序列控制，如果z 上的任一可交换概率分布户，存在这样一个概率 空间 ( 曼) ：se ( o ，1 ) ，甩- 1 ，2 ，) ，( 7 7 ) ：g ( o ，1 ) ，n = l ，2 ，) 其中邕和班是取值为0 或者1 的随机变量，且： 1 ) 对于固定的g ，茸引，筻引，是带参数f 的独立伯努利随机变量序列； 2 ) 对所有的挖和s ，彬舅6 ； 3 ) 叫( r ，尸) ，占( o ，1 ) ，z = l ，2 ，的联合分布，和磋5 ：占( o ，1 ) ，z = l ，2 ，的联 基于转导推理思想的一致性预测器 合分布一致； 那么就说预测器r 是保守有效的。 最后，定义渐进有效性。如果对任一可交换概率分布p ，预测器r 对于样本 z t ，z 2 ，和任一显著性水平g ，依概率有 那么就说r 是渐进完全有效的。 如果依概率有 l i m 垡! ! ：丝：占( 2 - 1 1 ) n - - c o 以 胁s u p 幽g ( 2 1 2 ) n 以 那么r 就是渐进保守有效的；那么根据大数法则，可以得到如下命题： 命题：一个完全有效预测器是渐进完全有效的；一个保守有效的预测器是渐 进保守有效的。 2 3 4 非一致性 根据可交换性假设，已知样本的排列的先后顺序，是不影响结果的；这里我 们需要一个“袋”的概念，“袋”与集合相似但又不同，“袋 和集合对元素的顺 序可任意排列，“袋”内元素可重复，但集合内元素是不可重复；假设一个包含 毛，z 2 ，序列的珂个元素的“袋”，其内元素可能相同或不同，元素顺序可任意 排列，那么可将“袋”写为z 1 ，z 2 ，乙l ，用z ( ) 表示刀个元素组成的“袋 的集 合。 非一致性度量，或者说是奇异值度量，是衡量序列中每一个样本与整个样本 序列分布差异性的一种方式，针对高维复杂的序列样本，寻找一种映射函数将高 维样本序列( 包括己知样本和未知新样本) 的每一个样本一一对应的映射到奇异 值空间，其形式为： 彳：z ( ) z 寸页( 2 1 3 ) 其中a 是表征未知新样本与已知样本间差异程度；当我们有预测分类方法的 时候，非一致性度量方式是很容易得到的，简单来说如下两种方式： 1 4 基于转导推理思想的一致性预测器 1 ) 若样本只由数值( z = r ) 组成，那么就取已知样本的均值为未知新样本做 简单预测，于是未知新样本的非一致性得分就是未知新样本和已知样本 均值的差的绝对值； 2 ) 在样本是数值对的回归问题上，即毛= ( 誓，咒) ，对于未知新样本似力， 由x 和已知样本计算得出未知新样本的预测类标签y ，那么未知新样本 的非一致性得分就可定义为y 与y 的差的绝对值。 当然这种特殊的映射函数z ( ) z 是不是衡量样本间非一致性的合适方式还 是有待讨论的，一般理论下，我们就把从拓展实数线上取值的可衡量函数z ( ) z 称为非一致性度量。 已知样本序列z l ，z 2 ，- z n 和未知样本z ，我们可以得出样本z 与整个样本序列 即“袋，z 2 ，乙l 的差异性衡量么，即彳( 【乙，z 2 ，磊1 ，z ) 为样本z 的非一致性 度量。 当然，也可以把上述数学形式看为是一致性度量的概念，一致性度量和非一 致性度量在数学形式上没有什么不同，可写为：z ( 勺z 专页，那么一致性度量 就为曰( z l ，z 2 ，磊1 ，z ) ，那么非一致性就可看作一致性的派生，通过严格递减 转变，则有a ：= 一b 或者是a - 1 b ；用一致性度量预测时，所预测的理想结果 就是未知新样本更符合已知样本的序列，或者说跟已知样本的分布更一致，那么 那些预测出来的标签( 即一致性得分高的) 比起那些排除在外的标签( 即非一致 性得分高的) 更应该值的关注；但是实际应用中，非一致性度量更容易应用，例 如，当比较未知新样本和已知样本均值时，习惯上定义两者之间的差距而不是去 衡量两者间有多相似接近，所以更容易用非一致性代替一致性表征未知新样本隶 属已知样本序列的程度，而且这样更符合传统数学统计，因为检验统计通常用来 衡量差异性而非一致性；所以对于，l = 1 ，2 ，定义函数 4 ：z ( ) z 寸页 ( 2 1 4 ) 那么序列( a n be ) 可缩写为( 以) 就被称为非一致性度量【7 】；这是一致性预 1 5 基于转导推理思想的一致性预测器 测算法的关键核心部分，是实现算法随机性检验的前提。 2 3 5 p 值 给出非一致性度量( 4 1 ) 和“袋”正z l ，乞，乙l 的概念后，那么对于来自概率分 布为p 样本序y