版本空间(学习)

版本空间学习是机器学习领域的的一种逻辑方法,特别是二进制分类。 版本空间学习算法搜索预定义的假设空间,将其视为一组(数理逻辑上的)句子(logical sentence)。 正式的定义来说,若假设h对于数据集内的所有例子(x,c(x)),h(x)=c(x)都成立,则称假设h是一致的。而版本空间是假设空间H的一个子集,即假设空间H中所有一致的假设h的并集(disjunction)。

简介

版本空间学习是机器学习领域的的一种逻辑方法,特别是二进制分类。版本空间学习算法搜索预定义的假设空间,将其视为一组(数理逻辑上的)句子(logical sentence)。

正式的定义来说,若假设h对于数据集内的所有例子(x,c(x)),h(x)=c(x)都成立,则称假设h是一致的。而版本空间是假设空间H的一个子集,即假设空间H中所有一致的假设h的并集(disjunction)。

版本空间学习有两种算法:

1.列表后消除算法(List-Then-Eliminate Algorithm):

  1. 将版本空间表示为假设空间H中所有的假设的合集;
  2. 对每一个样本数据(x,c(x)),将与其不一致的假设h从版本空间中去除;
  3. 输出剩余的假设合集

2.候选消除算法(Candidate Elimination Algorithm):

在这个算法中涉及到有关版本空间的表示的两个概念——一般的边界(General boundary,G)和具体的边界(Specific boundary,S),又称特殊边界。

一般边界G涵盖观察到的正例,但也覆盖剩余的特征空间而不包括任何负例。这个边界如果进一步扩大就会包括反例,与样本数据变得不一致。因此这些最大假设本质上构成了一个(乐观的)主张,即真正的概念仅仅由已经观察到的负面数据来定义:因此,如果观察到一种新的(从未见过的)数据点,则应该假定它是正面的。(也就是说,如果之前没有排除数据,那么它就被排除在外)。

具体/特殊边界S覆盖了观察到的正例,并尽可能少地覆盖了剩余的特征空间。这些假设,如果进一步减少,就排除一个正例,因此变得不一致。这些最小的假设本质上构成了一个(悲观的)主张,即真正的概念仅仅由已经观察到的正面数据来定义:因此,如果观察到一种新颖的(从未见过的)数据点,则应该假定它是负面的。(也就是说,如果之前没有统计过数据,则排除该数据)。

因此在假设存在一般性排序的环境中,可以用两组假设来表示版本空间:(1)最具体的一致假设;(2)最一般的一致假设。在学习过程中,版本空间(本身是一个集合-可能是无限的-包含所有一致的假设)可以用其下限和上限(最一般和最具体的假设集合)来表示。

候选消除算法的具体思路为,依次对样本数据d进行判断:

  1. 若d是正例:
    1. 将与d不一致的假设从G边界中移除
    2. 从边界S中移除与d不一致的假设s
    3. 把s的所有的最小一般化的假设h加入到S中,其中h需要与d一致,并且G中的某个假设应该比h更一般
    4. 若S中有比其他假设更一般的假设,则将更一般的假设移除
  2. 若d是反例:
    1. 从S中移除与d不一致的假设
    2. 从G中移除与d不一致的假设g
    3. 把g的所有的极小具体化的假设h加入到G中,其中g需要与d一致,并且S中的某个假设应该比g更具体
    4. 若G中有比其他假设更具体的假设,则将更具体的假设移除

在学习之后,可以通过测试算法学习的假设来对看不见的例子进行分类。如果该例子与多个假设一致,则可以应用多数投票规则。

以下图为例,假设绿色加号代表正例,红色圆圈代表反例。则最大限度不包含任何反例的边界即为版本空间的下限——最一般的边界GB,包含所有正例的最窄的边界即为版本空间的上限——最具体的边界SB。

[图片来源:https://upload.wikimedia.org/wikipedia/commons/3/33/Version_space.png]

[描述来源:Mitchell, Tom M. (1997). Machine Learning. Boston: McGraw-Hill.]

[描述来源:维基百科 URL: https://en.wikipedia.org/wiki/Version_space_learning]

发展历史

描述

版本空间的概念是Mitchell在20世纪80年代初引入的,作为理解涉及到基本的监督学习问题的框架。Sverdlik和Reynolds于1992提出了动态版本空间学习,Hong和Tsang在1997年发表的论文中设计了适用于有噪声、不确定的数据的版本空间学习算法,该算法包括搜索和修建两个阶段,并且可以在时间复杂度和准确度之间进行权衡。2002年Dubois和Quafafou用粗糙集理论(rough set theory)来改进版本空间学习不能处理有噪声的数据的这个缺陷。

主要事件

年份

事件

相关论文/Reference

1982

Mitchell引入版本空间的概念

Mitchell T. M. (1982). Generalization as search. Artificial Intelligence. 18 (2): 203–226.

1992

Sverdlik和Reynolds于1992提出了动态版本空间学习

Sverdlik, W.; Reynolds, R.G. (1992). Dynamic version spaces in machine learning.Proceedings, Fourth International Conference on Tools with Artificial Intelligence (TAI '92). Arlington, VA. pp. 308–315.

1997

Hong和Tsang设计了适用于有噪声、不确定的数据的版本空间学习算法

Hong T. P.; Tsang S. S. (1997). A generalized version space learning algorithm for noisy and uncertain data. IEEE Transactions on Knowledge and Data Engineering. 9 (2): 336–340.

2002

Dubois和Quafafou用粗糙集理论(rough set theory)来改进版本空间学习不能处理有噪声的数据的这个缺陷。

Dubois V.; Quafafou M. (2002). Concept learning with approximation: Rough version spaces. Rough Sets and Current Trends in Computing: Proceedings of the Third International Conference. pp. 239–246.

发展分析

瓶颈

版本空间学习的一个主要缺点是它无法处理噪声:任何一对不一致的例子都会导致版本空间崩溃,即变成空集,从而使分类变得不可能。另外利用版本空间学习互斥的概念(disjunctive concept)是很困难的。

未来发展方向

事实上关于版本空间学习目前在进行的研究并不是很多,概念学习(concept learning)这一领域目前不是很热门,版本空间主要是涉及到概念学习的任务的基本概念之一,如语言处理。

Contributor: Yuanyuan Li

相关人物
汤姆·M·米切尔
汤姆·M·米切尔
TOM M.Mitchell是卡内基梅隆大学的教授,讲授“机器(AAA)的主席:美国《Machine Leaming》杂志、国际机器学习年度会议(ICML)的创始人:多种技术杂志的撰稿人,曾发表过许多文章,出版过多本专著,是机器学习领域的著名学者。
简介
相关人物