计算机视觉
图像处理

一些知识点的初步理解3

一些知识点初步理解(核函数,ing…)

       在SVM中经常听说核函数,关于各种核函数的推导公式写得天花乱坠。SVM大概意思是说将低维不可分的样本映射到高维空间中后就线性可分了,由于最后用 训练出来的模型进行分类预测  时需要求高维空间中映射特征间的内积,而核函数的功能就是我们计算时不需要考虑高维空间的具体形式,降低了其计算复杂度。

      下面就简单讲讲核函数的作用,当然这里是以2分类器为例。

      首先我们需要了解我们的目的是用训练样本学习到一个线性的表达式,即下面的公式:  (1)

      通过训练数据可以学校到其中的权值向量w和阈值向量b,对于新来的特征向量x代入到上式中,求出y,如果y>0则为正例,y<0则为负例。

      上面过程看起来很简单,比较自然,且有核函数的相关理论可以知道,求出的w表达式为:  (2)代入到上面那个公式就可以得到

         (3)

      到目前为止,我们新来一个样本,只需让它与所有的训练样本做内积,然后线性相加等操作即可,比较幸运的是,只有当为支持向量时才不为0,其它位置的都为0,所以只需要进行少数的线性组合计算即可。

      现在还没有必要使用核函数,那是因为用上面的方法进行预测时,样本本身具有线性可分的特点。如果我们在样本空间下不能够线性可分呢?那么这样求出的w和b用来预测就是错误的了。

     如果低维线性不可分,但在高维中线性可分,这样就需要将低维的x映射到高维的了,因此在公式(3)中的内积映射为

  我们把映射后的内积用一个函数表示K(x,z)表示,这个函数就是我们这里讲的核函数了。即

(4)

  因为公式(4)左边的计算复杂度为核函数的计算复杂度,核函数是由为映射过的特征x和z构成的,所以复杂度比较低,不像公式(4)的右边,由高维的特征向量构成,复杂度高。

因此我们的问题转化成了,当来了一个新的向量x,对其分类时使用下面的公式:

(5)

  公式(5)后面的内积我们就用核函数代替了,那么我们为什么这么有必要用核函数去代替呢?除了开始说的的为了减轻运算复杂度(也就是运算量)外,另外一个原因就是我们的映射函数很难确定,不好寻找。

  到此为止,我们已经知道了核函数的部分作用了。

  当然了,至于什么样的核函数K能够代替,这就是核函数的有效性另一套理论了,不是本次所讲述的重点。

一些知识点的初步理解(随机森林,ing…)

  在机器学习中,随机森林由许多的决策树组成,因为这些决策树的形成采用了随机的方法,因此也叫做随机决策树。随机森林中的树之间是没有关联的。 当测试数据进入随机森林时,其实就是让每一颗决策树进行分类,最后取所有决策树中分类结果最多的那类为最终的结果。因此随机森林是一个包含多个决策树的分 类器,并且其输出的类别是由个别树输出的类别的众数而定。随机森林可以既可以处理属性为离散值的量,比如ID3算法,也可以处理属性为连续值的量,比如 C4.5算法。另外,随机森林还可以用来进行无监督学习聚类和异常点检测。

随机森林由决策树组成,决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二,比如说下面的决策树(其属性的值都是连续的实数):

 

将空间划分为成的样子为:

随机深林的优点:比较适合做多分类问题;训练和预测速度快;对训练数据的容错能力,是一种有效地估计缺失数据的一种方法,当数据集中有大比例的 数据缺失时仍然可以保持精度不变;能够有效地处理大的数据集;可以处理没有删减的成千上万的变量;能够在分类的过程中可以生成一个泛化误差的内部无偏估 计;能够检测到特征之间的相互影响以及重要性程度;不过出现过度拟合;实现简单容易并行化。

 

下面是具体决策树的生成过程:

其中关于信息增益这里就不作具体的介绍,反正信息增益越大,就说明那个属性相对来说越重要。流程图中的identical values 可以理解为是分类值,离散值,就是它本身不具备数值的意义,比如说颜色分为红,绿,蓝等,是人为给它标定的一个离散值而已。流程图中的 real values可以理解为连续的实数,也就是说属性本身是具有数值的,比如说物体的长度,这就是一个real value,在进行这种连续值属性构造决策数时,需要按照属性值的范围进行生成子节点。

当可以生成好决策树后,就比较容易生成随机森林了。下面是随机森林的构造过程:

1. 假如有N个样本,则有放回的随机选择N个样本(每次随机选择一个样本,然后返回继续选择)。这选择好了的N个样本用来训练一个决策树,作为决策树根节点处的样本。

2. 当每个样本有M个属性时,在决策树的每个节点需要分裂时,随机从这M个属性中选取出m个属性,满足条件m << M。然后从这m个属性中采用某种策略(比如说信息增益)来选择1个属性作为该节点的分裂属性。

3. 决策树形成过程中每个节点都要按照步骤2来分裂(很容易理解,如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性,则该节点已经达到了叶子节点,无须继续分裂了)。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。

4. 按照步骤1~3建立大量的决策树,这样就构成了随机森林了。

从上面的步骤可以看出,随机森林的随机性体现在每颗数的训练样本是随机的,树中每个节点的分类属性也是随机选择的。有了这2个随机的保证,随机森林就不会产生过拟合的现象了。

随机森林有2个参数需要人为控制,一个是森林中树的数量,一般建议取很大。另一个是m的大小,推荐m的值为M的均方根。

参考资料:

   决策树模型组合之随机森林与GBDT

random forest

http://en.wikipedia.org/wiki/Random_forest

一些知识点的初步理解(Graph Cuts,ing…)

  Graph cuts是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。Graph Cuts理论最早是出现在流网络优化领域的,比如说水管网络,通信传输网络,城市车流网络等。此时的Graph Cuts算法是用来确定网络流的最小分割,即寻找一个容量最小的边的集合,去掉这个集合中的所有边就可以阻挡这个网络了。需要注意的是,通常所说的 Graph Cuts算法是指的采用最大流-最小分割来优化的模型,其它的Graph Cutting算法一般用graph partitioning这个名词来代替。

首先还得先理解Graph Cuts中的Graph和Cuts的意思。此处的Graph和普通的Graph稍有不同。普通的图由顶点和边构成,如果边的有方向的,这样的图被则称为有 向图,否则为无向图,且边是有权值的,不同的边可以有不同的权值,分别代表不同的物理意义。而Graph Cuts图是在普通图的基础上多了2个顶点,这2个顶点分别用符号”S”和”T”表示,统称为终端顶点。其它所有的顶点都必须和这2个顶点相连形成边集合 中的一部分。所有Graph Cuts中的边也分为两种,一种是普通顶点与相邻点或者与之有关联的点之间的连线,一种是刚讲的普通顶点和2个终端顶点之间的连线。 Graph Cuts中的Cuts是指这样一个边的集合,很显然这些边集合包括了上面2种边,该集合中边的断开会导致残留”S”和”T”图的分开,且这些边的集合中所 有权值之和是最小的。因此也称为最小割。关于Graph Cuts的示意图如下所示:

图割在图像分割中应用得很广,那么应该怎样将图割理论和计算机视觉联系起来呢?图割模型和图像该怎么建立联系呢?有一位网友在他的博文图割小结做了个小结,比喻得还不错,可以让大家图割在图像分割中的作用有个初步的印象。

在参考了iccv2001的文章Interactive graph cuts for optimal boundary & region segmentation of objects in ND images后,或许能够找到上述问题的一点答案。首先,一张image可以看作是一个矩阵,图中的每个像素就是矩阵中的一个位置,这个像素可以看做是图 中的一个顶点。然后我们把相邻顶点之间用短线(有向或无向都行)连接起来,这就形成了边,现在这幅image有顶点和边了,也就构成一幅Graph了。至 于边的权值怎么计算,则是很理论的东西。看了下论文中的解释,图像中边的权值一般由2部分构成,平滑项和数据项,这2部分的比重用1个系数来平衡,其中平 滑项主要体现顶点像素和其相邻区域像素之间值的变化强度,如果变化剧烈说明这两者很有可能出于边缘部分,则被分割开的可能性比较大,而按照最小割的分割原 理,这时2者的平滑项权值应该较小。而数据项部分则表示对应顶点属于前景或者背景的惩罚项。其论文中的数学公式为:

 

其中R(A)表示的是区域数据项,B(A)表示的是边界平滑项,E(A)表示的是权值,即损失函数,也叫能量函数,图割的目标就是优化能量函数使其值达到最小。

另外由于Graph Cuts需要有2个终端节点”S”和”T”,分别表示初始的目标区域和背景区域,在计算机视觉的图像分割领域时,需要人工指定初始的s顶点和t顶点,如果 有HCI的话,可以用鼠标分别直接点这2个区域。其中一个区域代表所需分割目标上的一个像素位置,另一个为背景上的一个像素位置。有了能量函数的定义和初 始的终端顶点,就可以采用图割理论来不断迭代对目标进行分割了。

参考资料:

http://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision

http://www.cnblogs.com/longdouhzt/archive/2012/05/11/2496373.html

[基础算法] Graph Cut and Its Application in Computer Vision

[论文笔记] CUDA Cuts: Fast Graph Cuts on the GPU

图割小结

Boykov, Y. Y. and M. P. Jolly (2001). Interactive graph cuts for optimal boundary & region segmentation of objects in ND images. Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, IEEE.

 

一些知识点的初步理解(独立成分分析-ICA,ing…)

  独立成分分析(后面都用ICA代替)在维基百科中的解释是:一种利用统计原理进行计算的方法它是一个线性变换。这个变换把数据或信号分离成统计独立的非高斯的信号源的线性组合。独立成分分析是盲信号分离(Blind source separation)的一种特例。

可以感性上对比下ICA和PCA的区别,PCA是将原始数据降维并提取出不相关的属性,可以参考前面博文的介绍:PCA算法学习_1(OpenCV中PCA实现人脸降维)和PCA算法学习_2(PCA理论的matlab实现), 而ICA是将原始数据降维并提取出相互独立的属性。我们知道两个随机变量独立则它们一定不相关,但2个随机变量不相关则不能保证它们不独立,因为独立是表 示没有任何关系,而不相关只能表明是没有线性关系。且PCA目的是找到这样一组分量表示,使得重构误差最小,即最能代表原事物的特征。ICA的目的是找到 这样一组分量表示,使得每个分量最大化独立,能够发现一些隐藏因素。由此可见,ICA的条件比PCA更强些。

另外,对任意两个相互独立的随机变量s1和s2,有下面的关系式成立:

其中的函数g1和g2是任意的非线性变换(当然也包括了线性变换),也就是说任意的相互独立的随机变量的任意非线性变换后是不相关的。

ICA的理解可以首先看下面的公式:

我们的目的就是要根据已知向量X(可以把矩阵转换成向量)来求出变换矩阵A和对应的系数列向量s。此时这里只已知了X。并且在求A和s的过程中有下面几个假设:

1.  s中的每个元素是相互统计独立的。

2.  s中的每个元素是非高斯分布的。

3.  变换矩阵A是可逆方阵。

4.  s中元素的平方和为1.

至于具体怎么去求解A和s,都是一些数学优化的东西,没怎么看懂,这节就不介绍了(本节目标也只是初步理解下ICA)。

 

下面来看看ICA模型在图片分析中的理解:

一般情况下我们的图片都是基于像素表示的,即图片中的每个位置给出一个像素值,然后保存这些像素值即可。不过这里我们采用基于图片basis的 表示方法,即对一张图片用少数几个系数和对应的一组basis images表示。Basis image指的是基图片,即其它的图片可以用这些basis image线性组合表示,有点类似基坐标系这一概念。如下图所示,一副图片可以用几个basis image表示:

其数学上的表示可以表示如下:

其中Ai就可以看做是basis image,Si可以看成是basis images图片的系数。当然了经过一系列的数学分析,Si是可以从原图像I(x,y)中求到的,公式如下:

转载注明来源:CV视觉网 » 一些知识点的初步理解3

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 3

评论前必须登录!