Categories

Calendar

November 2017
M T W T F S S
« Jun    
 12345
6789101112
13141516171819
20212223242526
27282930  

求最小的几个特征值

在机器学习中经常都会遇到特征值问题,例如 Laplacian Eigenmaps 或者一大堆的 KernelPCA 派的降维方法,或者谱聚类之类的。通常都是对于一个很大并且比较稀疏的矩阵,求最大或者最小的几个特征值以及对应的特征向量。在 Matlab 里,eig 函数可以用来求得一个矩阵的全部特征值和特征向量,然而,如果我们只需要其中最大或者最小的那几个,用 eig 来求就显得杀鸡用牛刀了,费力还不讨好。而且,eig 还不能处理稀疏矩阵的情况,所以,这个时候通常就需要 eigs 出场了。

eigs 可以只求矩阵的几个最小的或者最大的(或者最接近某一个数值的)特征值和对应的特征向量,并且能够处理稀疏矩阵(如果矩阵规模很大而且稀疏程度有很高的话,使用稀疏矩阵速度会快很多)。当然它使用的算法和 eig 不一样,是迭代的方式(具体的细节我也不是很清楚,记得数值分析课上讲过 power method ,不过也忘得精光了 -.-)。这也造成了一个小缺点,就是当矩阵是 singular 或者 near-singular 的时候,如果求最小的几个特征值,就会有问题。例如下面这个极端的例子,我们造一个 rank 为 1 的矩阵:

a = rand(3,1);
A = a*a';
eigs(A, 2, ‘SM’);

Matlab 就会在这里出错。让人很痛苦,因为有时候会在数据中碰到矩阵 near-singular 的情况。一开始我找不到解决办法,因为 eig 是可以处理 singular 矩阵的,所以干脆在遇到 eigs 出错的时候转由 eig 来计算,然后手工选出最小的几个特征值和特征向量。

Generate Recursive Images

在上一篇 blog 中我提到了递归图片,还给了一个有趣的例子,这次还说递归图片,再给另一个例子:

不过这次的例子是我自己生成的,而篇 blog 就是要讲如何来生成这样一张递归图片。其实方法很简单,类推一下,多花一些功夫的话,之前给的那个“二次递归”的例子也是可以“轻松”做出来的。

为 Python 的 HTTP 客户端加入自定义的 Cookie

几乎所有脚本语言都提供了方便的 HTTP 客户端处理的功能,Python 也不例外,使用 urllib 和 urllib2 可以很方便地进行 HTTP GET 和 POST 等各种操作。并且还允许以类似于插件的形式加入一些 handler ,来定制 request 和 response ,比如代理的支持和 cookie 的支持都是这样添加进来的。具体来说,通过如下方式构造一个 opener :

opener = urllib2.build_opener(urllib2.HTTPCookieProcessor())

然后这个 opener 就可以处理 cookie 了,相当方便,并且可定制性也……好吧,总之,现在我希望能在客户端手动插入一些 cookie 值,但是不管是 HTTPCookieProcessor 还是 cookielib 里的 CookieJar 都没有提供类似的方法可以来实现。

Tidy your Rakefile

Rake 我就不再介绍了,Ruby 的 Make ,许多方面都比 Make 要更好用一些。和 Makefile 不同的是,Rakefile 本身其实就是一段 Ruby 代码,这样的好处有很多,一方面在 Rake 里面就可以很直接地做任何 Ruby 能做的事了,另一方面由于 Ruby 对 DSL 支持良好,所以 Rakefile 通常看起来也并不那么“代码”。

不过,代码始终是代码,Makefile 尚且可以写得很乱,Rakefile 要写乱就更容易了,幸运地是,Rake 提供了一些功能让我们可以来对 Rakefile 做一些组织工作。

RabbitMQ: high performance messaging solution

RabbitMQ 是一个由 Erlang 写成的 Advanced Message Queuing Protocol (AMQP) 实现,AMQP 的出现其实也是应了广大人民群众的需求,虽然在同步消息通讯的世界里有很多公开标准(如 COBAR 的 IIOP ,或者是 SOAP 等),但是在异步消息处理中却不是这样,只有大企业有一些商业实现(如微软的 MSMQ ,IBM 的 Websphere MQ 等),因此,在 2006 年的 6 月,Cisco 、Redhat、iMatix 等联合制定了 AMQP 的公开标准。反正现在这个世道通常都是小公司拥抱标准,大企业自己搞一套标准,不过公开标准总还是对大众有利的。

Scrapy 轻松定制网络爬虫

网络爬虫(Web Crawler, Spider)就是一个在网络上乱爬的机器人。当然它通常并不是一个实体的机器人,因为网络本身也是虚拟的东西,所以这个“机器人”其实也就是一段程序,并且它也不是乱爬,而是有一定目的的,并且在爬行的时候会搜集一些信息。例如 Google 就有一大堆爬虫会在 Internet 上搜集网页内容以及它们之间的链接等信息;又比如一些别有用心的爬虫会在 Internet 上搜集诸如 foo@bar.com 或者 foo [at] bar [dot] com 之类的东西。除此之外,还有一些定制的爬虫,专门针对某一个网站,例如前一阵子 JavaEye 的 Robbin 就写了几篇专门对付恶意爬虫的 blog (原文链接似乎已经失效了,就不给了),还有诸如小众软件或者 LinuxToy 这样的网站也经常被整个站点 crawl 下来,换个名字挂出来。其实爬虫从基本原理上来讲很简单,只要能访问网络和分析 Web 页面即可,现在大部分语言都有方便的 Http 客户端库可以抓取 Web 页面,而 HTML 的分析最简单的可以直接用正则表达式来做,因此要做一个最简陋的网络爬虫实际上是一件很简单的事情。不过要实现一个高质量的 spider 却是非常难的。

Play Babelize with Google Translate

Have you played such a game when you were young? One person think a sentence and tell another in a whisper (or just use gesture language or anything that might loss some information when transmitting the bits). Then sentence is passed along in that way until the last one. Then he tell us what he […]

Poor Man’s Picasaweb Photo Uploading Script

虽然不太常用网络相册,但是有时候也会把照片传到 Picasaweb 上作为一个备份。如果安装了 Picasa 的话可以很方便地上传,另外,也有为 IE 做的 ActiveX 控件可以方便地批量上传照片。但是 Linux 下地 Picasa 据说是用 wine 模拟的,不想用,而浏览器也没有 ActiveX 可以用,手工一个一个地上传颇有一些麻烦。后来发现 Google 其实提供了它的各种服务的 API 的 Python binding 可以比较方便地使用,这样就可以弄一个脚本来上传了。

闲谈程序的配置文件

通常我们写程序的时候都会有一些可调控的参数,简单的控制可以通过命令行参数来实现,然而复杂一些的则一般会使用配置文件的形式。可以说这几乎是每一个程序都会需要考虑的一个问题:使用什么样形式的配置文件?虽然 Microsoft 在 Windows API 中提供了注册表以及 ini 文件的读写功能,但是在这一块似乎还是没有像 zlib 之于压缩那样被广泛接受的方式。其实原因也很简单:需求差别太大了。

例如 Emacs 的配置文件,目标是达到最大的灵活性,因此它就纯粹是 Elisp 代码了。类似的有 Rake 的 Rakefile ,其内容实际上是合法的 Ruby 代码,因此写起来和用起来都比 Makefile 要方便了许多。另一方面,对于 pymmseg-cpp 或者 rmmseg-cpp 来说,性能最重要,因此配置文件(辞典)采用了最简单的以行分割的形式,没有使用二进制格式,是因为希望保持配置文件的可编辑性,虽然这个大概说成是数据文件似乎更贴切一些。

除去以上两个极端情况,其他时候使用什么格式的文件就通常是看怎么用方便了。比如我在 YASnippet 中给 snippet 文件定制的属性格式就是简单的每行一个

iRobot 之梦

iRobot 其实只是一开始胡乱找来的一个 code name ,不过现在已经成了一个小小的梦想的代名词。这个梦似乎是从 2007 年 12 月开始的。那天是去考六级,按照我以往的习惯去得有点早,教室还不让进,于是我便在东区长廊平台那里逛,想想俱乐部实践项目的事情。实践项目就是微软那边每年都会有的发放到各个俱乐部去的项目,具体做什么由自己定,当然他们那边是希望尽量和微软技术沾边的,虽然不多,但是微软也会给项目拨一些钱,不管怎么说,一些人一起做一个东西就是一件快乐的事情,这也正是俱乐部一直都在思考的一个问题啊:大家人是聚到一起了,可是要做点什么呢?虽然大家也并不是闲着,但也总想多一些点子吧!