Categories

Calendar

October 2017
M T W T F S S
« Jun    
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

支持向量机:Numerical Optimization

本文是“支持向量机系列”的第五篇,参见本系列的其他文章。

作为支持向量机系列的基本篇的最后一篇文章,我在这里打算简单地介绍一下用于优化 dual 问题的 Sequential Minimal Optimization (SMO) 方法。确确实实只是简单介绍一下,原因主要有两个:第一这类优化算法,特别是牵涉到实现细节的时候,干巴巴地讲算法不太好玩,有时候讲出来每个人实现得结果还不一样,提一下方法,再结合实际的实现代码的话,应该会更加明了,而且也能看出理论和实践之间的差别;另外(其实这个是主要原因)我自己对这一块也确实不太懂。

支持向量机:Outliers

本文是“支持向量机系列”的第四篇,参见本系列的其他文章。

在最开始讨论支持向量机的时候,我们就假定,数据是线性可分的,亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据,使用 Kernel 方法对原来的线性 SVM 进行了推广,使得非线性的的情况也能处理。虽然通过映射 $\phi(\cdot)$ 将原始数据映射到高维空间之后,能够线性分隔的概率大大增加,但是对于某些情况还是很难处理。例如可能并不是因为数据本身是非线性结构的,而只是因为数据有噪音。对于这种偏离正常位置很远的数据点,我们称之为 outlier ,在我们原来的 SVM 模型里,outlier 的存在有可能造成很大的影响,因为超平面本身就是只有少数几个 support vector 组成的,如果这些 support vector 里又存在 outlier 的话,其影响就很大了。例如下图:

用黑圈圈起来的那个蓝点是一个 outlier ,它偏离了自己原本所应该在的那个半空间,如果直接忽略掉它的话,原来的分隔超平面还是挺好的,但是由于这个 outlier 的出现,导致分隔超平面不得不被挤歪了,变成途中黑色虚线所示(这只是一个示意图,并没有严格计算精确坐标),同时 margin 也相应变小了。当然,更严重的情况是,如果这个 outlier 再往右上移动一些距离的话,我们将无法构造出能将数据分开的超平面来。

支持向量机: Kernel

本文是“支持向量机系列”的第三篇,参见本系列的其他文章。

前面我们介绍了线性情况下的支持向量机,它通过寻找一个线性的超平面来达到对数据进行分类的目的。不过,由于是线性方法,所以对非线性的数据就没有办法处理了。例如图中的两类数据,分别分布为两个圆圈的形状,不论是任何高级的分类器,只要它是线性的,就没法处理,SVM 也不行。因为这样的数据本身就是线性不可分的。

对于这个数据集,我可以悄悄透露一下:我生成它的时候就是用两个半径不同的圆圈加上了少量的噪音得到的,所以,一个理想的分界应该是一个“圆圈”而不是一条线(超平面)。如果用 $X_1$ 和 $X_2$ 来表示这个二维平面的两个坐标的话,我们知道一条二次曲线(圆圈是二次曲线的一种特殊情况)的方程可以写作这样的形式:

\[
a_1X_1 + a_2X_1^2 + a_3 X_2 + a_4 X_2^2 + a_5 X_1X_2 + a_6 = 0
\]

注意上面的形式,如果我们构造另外一个五维的空间,其中五个坐标的值分别为 $Z_1 = X_1$, $Z_2=X_1^2$, $Z_3=X_2$, $Z_4=X_2^2$, $Z_5=X_1X_2$,那么显然,上面的方程在新的坐标系下可以写作:

支持向量机: Support Vector

本文是“支持向量机系列”的第二篇,参见本系列的其他文章。

上一次介绍支持向量机,结果说到 Maximum Margin Classifier ,到最后都没有说“支持向量”到底是什么东西。不妨回忆一下上次最后一张图:

可以看到两个支撑着中间的 gap 的超平面,它们到中间的 separating hyper plane 的距离相等(想想看:为什么一定是相等的?),即我们所能得到的最大的 geometrical margin $\tilde{\gamma}$ 。而“支撑”这两个超平面的必定会有一些点,试想,如果某超平面没有碰到任意一个点的话,那么我就可以进一步地扩充中间的 gap ,于是这个就不是最大的 margin 了。由于在 $n$ 维向量空间里一个点实际上是和以原点为起点,该点为终点的一个向量是等价的,所以这些“支撑”的点便叫做支持向量。

支持向量机: Maximum Margin Classifier

本文是“支持向量机系列”的第一篇,参见本系列的其他文章。

支持向量机即 Support Vector Machine,简称 SVM 。我最开始听说这头机器的名号的时候,一种神秘感就油然而生,似乎把 Support 这么一个具体的动作和 Vector 这么一个抽象的概念拼到一起,然后再做成一个 Machine ,一听就很玄了!

不过后来我才知道,原来 SVM 它并不是一头机器,而是一种算法,或者,确切地说,是一类算法,当然,这样抠字眼的话就没完没了了,比如,我说 SVM 实际上是一个分类器 (Classifier) ,但是其实也是有用 SVM 来做回归 (Regression) 的。所以,这种字眼就先不管了,还是从分类器说起吧。

SVM 一直被认为是效果最好的现成可用的分类算法之一(其实有很多人都相信,“之一”是可以去掉的)。这里“现成可用”其实是很重要的,因为一直以来学术界和工业界甚至只是学术界里做理论的和做应用的之间,都有一种“鸿沟”,有些很 fancy 或者很复杂的算法,在抽象出来的模型里很完美,然而在实际问题上却显得很脆弱,效果很差甚至完全 fail 。而 SVM 则正好是一个特例——在两边都混得开。

Beyond Recursion

Quine,或者说可以打印自己源代码的程序,通常被认为是比递归更神奇的东西,我以前也聊过这个话题。这次再提起来,是因为发现了另一个有趣的例子。

真相是,今天早上实验室网络检修,没法上网,而且由于考试周的接近自习室和图书馆都成了人山人海,几乎没有我等“散户”的容身之地,于是无聊中就把昨天下载的一篇传说很有趣的论文翻出来看了——发现果然很有趣。其实就是 Dahua 之前曾经介绍过的今年 CVPR 会议上分发的一篇最有趣的论文 Paper Gestalt。论文主要是讲了如何用 Computer Vision 的方法来自动判别提交到会议的论文的好坏并决定是否 accept,Dahua 的 blog 上已经介绍得很详细了,我在这里也就不多说了。总的来说,推荐去看一看论文原文,现在可以可以下载到了,语言既严谨又诙谐,简直就是给不幸被断网的小朋友的最佳读物啊! 看到赫然出现的麦克斯韦方程组的时候,我就乐坏了,当然我认为这篇论文的作者并不是 seriously 真的想要用这个系统来作为以后审稿的辅助工具的,但是这个确实很好玩,更重要的是,我看到作者对这个学术社区现状的反思,当然除了诙谐,还略带一些讽刺的意味。所以呀,学术圈也是有可爱的人以及不无聊的事的!

浅谈流形学习

总觉得即使是“浅谈”两个字,还是让这个标题有些过大了,更何况我自己也才刚刚接触这么一个领域。不过懒得想其他标题了,想起来要扯一下这个话题,也是因为和朋友聊起我自己最近在做的方向。Manifold Learning 或者仅仅 Manifold 本身通常就听起来颇有些深奥的感觉,不过如果并不是想要进行严格的理论推导的话,也可以从许多直观的例子得到一些感性的认识,正好我也就借这个机会来简单地谈一下这个话题吧,或者说至少是我到目前为止对这它的认识。

这两个词,在谈 Manifold 之前,不妨先说说 Learning ,也就是 Machine Learning 。而说道 Machine Learning 而不提一下 Artificial Intelligence 的话似乎又显得有些不厚道。人说 AI 是一门最悲剧的学科,因为每当它的一个子领域发展得像模像样之后,就立马自立门户,从此和 AI “再无瓜葛”了,而 Machine Learning 大概要算是最新的一个典型吧。这就让人有点奇怪,比如说数学,分门别类总算是够多了吧?可以不管怎么分,大家兄弟姐妹也都还承认自己是叫“数学”的。那 AI 呢?我觉得这里有很大一部分是它自身定位的问题。

如何生成随机数(上)

快三个月没有写日志了,大概是我开始认真写 blog 来第一次,也是因为发生了一些预料之外的事情,中断了许久,到后来又一直非常非常忙,不过我终于又爬上来冒个泡了,表明我还活着。

第二点要澄清的是,我这里并不是要讲“伪随机”、“真随机”这样的问题,而是关于如何生成服从某个概率分布的随机数(或者说 sample)的问题。比如,你想要从一个服从正态分布的随机变量得到 100 个样本,那么肯定抽到接近其均值的样本的概率要大许多,从而导致抽到的样本很多是集中在那附近的。当然,要解决这个问题,我们通常都假设我们已经有了一个生成 0 到 1 之间均匀分布的随机数的工具,就好像 random.org 给我们的结果那样,事实上许多时候我们也并不太关心它们是真随机数还是伪随机数,看起来差不多就行了。

现在再回到我们的问题,看起来似乎是很简单的,按照概率分布的话,只要在概率密度大的地方多抽一些样本不就行了吗?可是具体要怎么做呢?要真动起手来,似乎有不是那么直观了。实际上,这个问题曾经也是困扰了我很久,最近又被人问起,那我们不妨在这里一起来总结一下。为了避免一下子就陷入抽象的公式推导,那就还是从一个简单的具体例子出发好了,假设我们要抽样的概率分布其概率密度函数为 ,并且被限制在区间 上,如右上图所示。

CV 课程 Project:简单验证码的识别

验证码的识别可以说是一个非常困难的问题,更何况现在有一些验证码让人来辨认都有些不容易,当然正如我标题里说的,我这里讨论的是一种简单的验证码,具体来说就是经过旋转、缩放之后再加上一些随机线条作为干扰而得到的图片,如右图所示。其实这个问题最开始是 MSTC 第四届趣味程序设计竞赛中的一道题,这个学期上了一门《计算机视觉》课,最后要求交一个 Project ,老师给了一些题目,也可以自己想主题,于是我就定了这个主题。

由于最近各种 deadline ,我也没空把详细过程再用 blog 的方式写一遍了,如果感兴趣可以直接看我的 Report 文档以及完整的代码。

漫谈 Clustering (5): Hierarchical Clustering

本文是“漫谈 Clustering 系列”中的第 8 篇,参见本系列的其他文章。

系列不小心又拖了好久,其实正儿八经的 blog 也好久没有写了,因为比较忙嘛,不过觉得 Hierarchical Clustering 这个话题我能说的东西应该不多,所以还是先写了吧(我准备这次一个公式都不贴 )。Hierarchical Clustering 正如它字面上的意思那样,是层次化的聚类,得出来的结构是一棵树,如右图所示。在前面我们介绍过不少聚类方法,但是都是“平坦”型的聚类,然而他们还有一个更大的共同点,或者说是弱点,就是难以确定类别数。实际上,(在某次不太正式的电话面试里)我曾被问及过这个问题,就是聚类的时候如何确定类别数。