This is an old revision of the document!
概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数的值,或者说,是给定某一类别的若干正例和反例,从中获得该类别的一般定义,它在预定的假设空间中搜索假设,使其与训练样例有最佳的拟合度。
举例介绍(通过例子介绍概念学习中的相关术语)
通过以下的训练数据集来学习使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)的测试,并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根结点开始,测试这个结点指定的属性,然后按照给定实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。
问题是如何基于数据的观测值,给出结果的预测,如已知某天关于天气、温度、风等情况的观测(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程序包,可以方便通过调用来实现相关功能。