概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数的值,或者说,是给定某一类别的若干正例和反例,从中获得该类别的一般定义,它在预定的假设空间中搜索假设,使其与训练样例有最佳的拟合度。
举例介绍(通过例子介绍概念学习中的相关术语)
通过以下的训练数据集来学习使EnjoySport=yes的日子:
Example | Sky | AirTemp | Humidity | Wind | Water | Forecast | EnjoySport |
---|---|---|---|---|---|---|---|
1 | Sunny | Warm | Normal | Strong | Warm | Same | Yes |
2 | Sunny | Warm | High | Strong | Warm | Same | Yes |
3 | Rainy | Cold | High | Strong | Warm | Change | No |
4 | Sunny | Warm | High | Strong | Cool | Change | Yes |
实例空间X:概念是定义在一个实例集合上的,本例中X是所有可能的日子,而Sky,AirTemp之类是日子的属性;
目标函数C:待学习的函数,可以是定义在实例集X上的任意布尔函数,形式化为C:X→{0,1};
训练样本D:是为学习概念而提供的训练实例,训练样本中的每一个条目为X中的一个实例加上此实例对应的目标函数的值C(x);
假设空间H:所有可能假设的集合,它中的每一个假设h表示X上定义的布尔函数,即h:X→{0,1};
注:机器学习要做的就是拟合出h,使h(x)=c(x)
归纳学习假设:任一假设如果在足够大的训练样例集中很好的逼近目标函数,它也能在未见实例中很好的逼近目标函数。
一般到特殊序:如果对于假设h1和h2,任何被h1划分为正例的实例都会被h2为分为正例,我们说h2比h1更一般(h2 >= h1)
变型空间:是H中与训练样例D一致的所有假设构成的集合,为H的子集表示为VSH,D (个人以为引入变型空间的概念更容易理解假设空间H的结构和之后的列表后消除算法)
决策树学习是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策树。这种学习算法是最流行的归纳推理算法之一,是一种从一般到特殊的算法。
下面的数据是一个测试用例,根据各种条件决定是否打网球。
决策树通过把实例从根结点排列(sort)到某个叶子结点来分类实例,叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性(attribute)的测试,并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根结点开始,测试这个结点指定的属性,然后按照给定实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。
图2-1 概念PlayTennis的决策树
分类一个样例的方法是,将其沿根结点排列到合适的叶子结点,然后返回与这个叶子结点关联的分类(本例中为Yes或No)。这棵决策树根据天气分类“星期六上午是否适合打网球”。
图2-1画出了一棵典型的学习到的决策树。这棵决策树根据天气情况分类“星期六上午是否适合打网球”。例如,下面的实例:
< Outlook=Sunny,Temperature=Hot,Humidity=High,Wind=Strong >
将被沿着这棵决策树的最左分支向下排列,因而被评定为反例(也就是这棵树预测这个实例PlayTennis=No)。这棵树以及表3-2中用来演示ID3学习算法的例子摘自(Quinlan 1986)。
通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction)。从树根到树叶的每一条路径对应一组属性测试的合取,树本身对应这些合取的析取。例如,图2-1表示的决策树对应于以下表达式:
(Outlook=Sunny ٨ Humidity=Normal) ٧(Outlook=Overcast) ٧(Outlook=Rain ٨ Wind=Weak)
那么,哪个属性是最佳的分类属性呢?
这就需要用到“奥坎姆剃刀”原则
奥坎姆剃刀:优先选择拟合数据的最简单假设。
这是一个心理学问题,哲学家们以及其他学者已经对这样的问题争论几个世纪了,而且这个争论至今还未解决。
决策树遵照这个原则:较短的树比较长的优先
那么怎么确定一个属性能够较好的划分训练数据呢?这就用到了信息论(information theory)
信息论是一个数学分支,由Claude shannon在20世纪40年代创建。信息论是一门用数理统计方法来研究信息的度量、传递和变换规律的科学。它主要是研究通讯和控制系统中普遍存在着信息传递的共同规律以及研究最佳解决信息的获限、度量、变换、储存和传递等问题的基础理论。
信息就是不确定性的减少,并获取新的知识。
信息是确定性的增加—-逆Shannon信息定义。
一个事件的信息量与它出现的概率最为相关。在信息论中,使用的基本单位是位(bits)。
如果一个确定发生的事件发生了,那么确定性没有任何变化,所以得到的信息为0。而如果小概率的事件发生了,那么将得到比可能发生的事情更多的信息量。所以信息量与事件发生的概率成反比。
举例来说:设字母表为{S_1,S_2,S_3,。。。S_n}
那么每个符号S_i的概率为P(S_i)=P_i(P_i>=0 且 \sum_{i=1}^{n}P_i=1)
对两个不相关的事件来说,I(S_iS_j)=I(S_i)+I(S_j)
P(S_iS_j)=P(S_i)P(S_j)
从这两个关系式中可以看出,I(S_i)应该以P(S_i)对数形式给出,所以有
I(S_i)=-log_2P_i
所以每个符号的平均信息是 E_t=-\sum_{i=1}^{M}P_ilog_2P_i
这就是“熵”
用熵建立一个信息增量的方程
信息增量最大的属性就是最佳的属性
问题是如何基于数据的观测值,给出结果的预测,如已知某天关于天气、温度、风等情况的观测(X的值),预测运动员是否进行训练(Y的值)
即要计算P(Y|X)
根据贝叶斯公式:
构造一个分类器(Naive Beyes Classifier),即目标函数f:X \to Y
我们要做的就是在X的属性观察值是X1、X2…Xn的时候,预测Y的值即:
假设观测值之间是相互独立的,那么
而 P(x_i|y_j) 和 P(y_j) 可以通过给定的样本数据来估计出,并用估计值来计算每一个P(y_j|x_1,x_2,…,x_n),取概率最大的结果作为分类结果
上世纪90年代由Vapnik和他的同事开发,可以用于进行分类或回归分析. 与传统的神经网络方法相比,具有更好的普遍性和全局最优性.
Boosting算法的形式多种多样,通常都是由多个弱分类器在一定的分布下通过循环迭代,最后组合形成一个强分类器的。当这些弱分类器被组合在一起的时候,它们总是会根据各自的准确度而在组合中占一定的权重。当一个弱分类器被加进来时,所有的数据都被重新赋予权重:那些被分错的点的权重会上升,而分对的点的权重则会下降。因此,接下来,分类器会着重注意对待之前被分错类的点。
为不失一般性, 设x为输入数据,y表示输入数据的正负属性分类,其中设正类为1,负类为-1。给定n个数据点,即有n个(x_{i},y_{i})这样的点-属性对,其中1 \le i \le n, i \in Z. 进一步假设初始弱分类器的权重分布为平均分布,即初始输入数据的权重分布为D_{1}(i)= \frac{1}{n},其中 i=1,\cdots,m
由于AdaBoost是一个迭代递进算法,设循环迭代的计数t=1,\cdots,T. 我们的目的是找出在当前分布D_{t}下,使得分类错误最小的分类器h_{t}:
其中
每次迭代中, 我们需重新计算新的权重\alpha_{t}:
进而我们可以更新数据的权重分布
其中Z_{t}是归一化的参数.
由于\sum_{i=1}^{n}D_{t+1}=1所以
可以看到,如果y_{i}与h_{t}(x_{i})的值相等的话,即当前分类器的决策是正确的,则相应的该点的权重会在下一轮迭代中下降;相反,如果y_{i}与h_{t}(x_{i})的值不相等的话,则他们符号相反,使得指数符号为正,从而使得该点的权重在下一轮迭代中上升。
设
设其最终错误函数为
最小化错误,即最小化其上限
而根据
我们可以得出
因此,我们的目标变成最小化
因为Z_{t}可以表示成
取最小极值,即求偏导等于零
我们可以得到
这也就是在算法迭代过程中,\alpha_{t}取值的原因。
Adaboost算法已被广泛地应用于计算机视觉的人脸检测方法,目前这一算法已被包含于OpenCV程序包,可以方便通过调用来实现相关功能。