版本空间（学习） | 机器之心

简介

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

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

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

1.列表后消除算法（List-Then-Eliminate Algorithm）：

将版本空间表示为假设空间H中所有的假设的合集；
对每一个样本数据（x，c（x）），将与其不一致的假设h从版本空间中去除；
输出剩余的假设合集

2.候选消除算法（Candidate Elimination Algorithm）：

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

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

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

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

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

若d是正例：
1. 将与d不一致的假设从G边界中移除
2. 从边界S中移除与d不一致的假设s
3. 把s的所有的最小一般化的假设h加入到S中，其中h需要与d一致，并且G中的某个假设应该比h更一般
4. 若S中有比其他假设更一般的假设，则将更一般的假设移除
若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

简介