现在的位置: 首页 > 读书笔记 > 正文
【读书笔记】从动态规划到新闻分类
2012年07月18日 读书笔记 ⁄ 共 2744字 评论数 1 ⁄ 被围观 3,153 views+

聊聊数日,《数学之美》已读过20章,从感叹到兴奋,转而迷惑又似神奇。

想那香农的信息论,专业选修课上倒也听老师讲过,只是印象颇浅,作者吴军则从世界杯冠军的预测开始,以二分法引出的信息量定义,实在是深入浅出;

热力学中用作衡量不确定程度的熵的概念,被这些伟大的学者引入信息论,进而延展到自然语言处理中,倍感自然神妙,大道相通;

谈及大名鼎鼎的PageRank算法,作者的文笔则甚是小心,明显不如《搜索引擎技术基础》这本书中所述直观,包括引擎索引和网络爬虫,均是点到为止,甚至让人有云里雾里的感觉,想必作者是碍于身份,也许是另有深意;

介绍词频(TF)和逆文本频率指数(IDF)时,作者又是一边引述一般分析,不放过读者任何一个可能的疑点,尤其是让看到IDF的定义时,已经引得读者想起前文熵的形式,从而文后顺理成章一番推导;

……

这其中,尤以两个章节给人留下的印象又颇为典型,分别为“地图和本地搜索的最基本技术——有限状态机和动态规划”和“余弦定理和新闻的分类”,所以,效仿作者的“从水门事件到·莫妮卡莱温斯基”,顾彼而言他。

地图和本地搜索的最基本技术——有限状态机和动态规划

如果我没有猜错的话,阅读本章的基础知识应该是《图论》,缺少《图论》基础的我,有限状态机的部分勉强可以看过,尽管不清楚到底如何使用,也对示意图中从“省”的状态如何能直接到“区县”的状态而耿耿于怀。

但是看到动态规划部分时,真的有点摸不着头脑,虽然说例子通俗简单,不过以全国公路网为例来寻找北京到广州的最短线路。但是终归存有两个疑问:

1.原文结论为“我们可以先找到从北京出发到这条线上(一条贯穿乌鲁木齐、西宁、兰州、西安、郑州、济南的弧线。)所有城市的最短路径,最后得到的全程最短路线一定包括这些局部最短线路中的一条。这样,就可以将一个‘寻找全程最短路线’的问题,分解成一个个寻找局部最短线路的小问题。只要将这条横切线从北京向广州推移,直到广州为止,我们的全程最短路线就找到了。这便是动态规划的原理。”

我的疑问就是,按照我的理解,那就是以北京到郑州为例,只有两条线路,A: “北京->石家庄->郑州”;B: “北京->济南->郑州”,倘若“北京->石家庄”比“北京->济南”的路线短,并且,“石家庄->郑州”也比“济南->郑州”短,那自然A线路就是最短。可是如果“北京->石家庄”比“北京->济南”的路线短,但是,“石家庄->郑州”也比“济南->郑州”长呢?前文中的反证法还是没有完全消除我的疑惑。此外,什么又叫做“只要将这条横切线从北京向广州推移”呢?

2.原文描述“在上面的例子中,每加入一条横切线,线上平均有10个城市,从广州到北京最多经过15个城市,那么采用动态规划的计算量是10×10×15……”要说看到这里,我基本上可以理解第一个问题中,作者所说的“只要将这条横切线从北京向广州推移”就是指再加入横切线,那么这横切线又该从哪里加入呢?更疑惑的是,作者如何得知“线上平均有10个城市,从广州到北京最多经过15个城市”,是假设还是计算所得?这“10×10×15”又是如何解释?

坦白说,本章这段内容是我对本书最疑惑的地方,固然自己的理解力有限,但是作者倘若能以更明晰的语言和图例解释,学习和理解起来必然会省力不少,从这一点上而言,想起书中所说“Google招聘产品经理时要求能给老太太将清楚什么是搜索引擎”的问题,不免觉得此处仍然有待改进,算是小小意见吧。

余弦定理和新闻的分类

与前一章节类似,我发觉本章所要求基础知识是《线性代数》,虽然不才,大学的线性代数考得不好,加之毕业几年来未曾使用,连两个矩阵如何计算都忘记了。但是,触类旁通:使用PS软件首先要根据图片的特征完成选择;识人辨物或以外形轮廓为特征,或以DNA,物质结构为特征;对任何事物的操作同样要寻找其特征,成功识别后才论其他……所以,这矩阵当然有其识别的特征,不论“特征向量”还是“特征值”,还是以后出来的其他什么特征,总之是使其与其他矩阵区别的标志。

对新闻的分类,除了人工辨别的劳力法子,还是自动化的法子省力高效,本章的内容虽不深奥,但是也精妙得很!将一篇新闻的文本作为一个矩阵来看,其中的字词自然是其特征,以语言中全部的词汇为向量,每个字词在这篇新闻中的信息量(例如TF-IDF值)为值,就可以找到这篇新闻的特征向量。

而两篇新闻的相似性,则以其特征向量的夹角余弦为表征,接触广义的余弦定理,两个特征向量倘若重叠,多半就是同一个向量(这特征向量的“坐标”如此之多,两篇不同新闻有相同向量的可能性自然极小),两个特征向量的夹角越大,余弦值越小,自然越不相似,等到夹角为90度,即是正交,想想那三维坐标中的X轴和Y轴,两个互相不能表示,自然是完全不同了。

就这样,直观上两篇新闻的相似性被两篇新闻的特征向量的夹角所表征,感性的东西被定量化了,如何不妙?(虽然我相信还存在其他以感性表征感性的方法。)

基于上述方法,通过计算成千上万篇新闻的特征向量两两之间的余弦相似性,将相似性大于一个阈值的新闻分为一小类;然后计算这一小类新闻的特征向量,再计算于其他小类的特征向量两两之间的余弦相似性,再将相似性大于阈值的新闻分为一类……如此反复计算,最终就可以实现自动化的新闻归类。当然,这计算细节的诀窍仍有很多,作者在后文也有所介绍。

至此,这篇文章被我酣畅淋漓地读完了!同样,我不知道没有《线性代数》基础的朋友是否也能看得如我这般兴奋,倘若如此,说明作者的表述手法精湛过人,否则的话,恐怕仍得有劳作者改进。

当然,一个人到达更高层次的境界后,再想反过来站在没有达到这种境界的人的角度,为其讲授知识,肯定不是易事。从这一点上,我对本书的作者仍然是崇敬有加!只是今日读书有感,不吐不快,书是好书,否则也不会终日抱在身前了!

抱歉!评论已关闭.

×