期权知识第608页

骰子作画的算法

程序员Scott MacDonald做了一个很有趣的项目----骰子作画。他用黑底白点的骰子。模拟出一张人像照片。把图像放大，就可以看得更清楚。他一共用了2500多颗骰子。最后的成品就是这样。任何一张图片都可以用骰子模拟出来，算法非常简单：将图片分成若干个区域，每个区域经过计算以后，用1-6之间的一个整数表示，代表骰子的一个面。这种将连续的量转化成不连续的整数的算法，属于vector quantization（矢量量化）的一个应用。具体来说，第一步，将图片分割成...

期权知识 2020-08-18 466 0
基于用户投票的排名算法（一）：Delicious和Hacker News

互联网的出现，意味着"信息大爆炸"。用户担心的，不再是信息太少，而是信息太多。如何从大量信息之中，快速有效地找出最重要的内容，成了互联网的一大核心问题。各种各样的排名算法，是目前过滤信息的主要手段之一。对信息进行排名，意味着将信息按照重要性依次排列，并且及时进行更新。排列的依据，可以基于信息本身的特征，也可以基于用户的投票，即让用户决定，什么样的信息可以排在第一位。下面，我将整理和分析一些基于用户投票的排名算法，打算分成六个部分连载，今天是第一篇。一、Delicious 最直觉、最简单的算法...

期权知识 2020-08-18 459 0
基于用户投票的排名算法（二）：Reddit

（不好意思，这个系列中断了近两周，我会尽快在这几天，把后面几篇写完。）上一次，我介绍了Hacker News的排名算法。它的特点是用户只能投赞成票，但是很多网站还允许用户投反对票。就是说，除了好评以外，你还可以给某篇文章差评。 Reddit是美国最大的网上社区，它的每个帖子前面都有向上和向下的箭头，分别表示"赞成"和"反对"。用户点击进行投票，Reddit根据投票结果，计算出最新的"热点文章排行榜"。怎样才能将赞成票和反对票结合起来，计算出一段时间内最受欢迎的文章呢？如果文章A有100张赞成票、5张...

期权知识 2020-08-18 620 0
基于用户投票的排名算法（三）：Stack Overflow

上一篇文章，我介绍了Reddit的排名算法。它的特点是，用户可以投赞成票，也可以投反对票。也就是说，除了时间因素以外，只要考虑两个变量就够了。但是，还有一些特定用途的网站，必须考虑更多的因素。世界排名第一的程序员问答社区Stack Overflow，就是这样一个网站。你在上面提出各种关于编程的问题，等待别人回答。访问者可以对你的问题进行投票（赞成票或反对票），表示这个问题是不是有价值。一旦有人回答了你的问题，其他人也可以对这个回答投票（赞成票或反对票）。排名算法的作用是，找出某段时...

期权知识 2020-08-18 465 0
基于用户投票的排名算法（四）：牛顿冷却定律

这个系列的前三篇，介绍了Hacker News，Reddit和Stack Overflow的排名算法。今天，讨论一个更一般的数学模型。这个系列的每篇文章，都是可以分开读的。但是，为了保证所有人都在同一页上，我再说一下，到目前为止，我们用不同方法，企图解决的都是同一个问题：根据用户的投票，决定最近一段时间内的"热文排名"。你可能会觉得，这是一个全新的课题，伴随着互联网而产生，需要全新的方法来解决。但是，实际上不是。我们可以把"热文排名"想象成一个"自然冷却"的过程：　　（1）任一时刻，网站中所有的文...

期权知识 2020-08-18 482 0
基于用户投票的排名算法（五）：威尔逊区间

迄今为止，这个系列都在讨论，如何给出"某个时段"的排名，比如"过去24小时最热门的文章"。但是，很多场合需要的是"所有时段"的排名，比如"最受用户好评的产品"。这时，时间因素就不需要考虑了。这个系列的最后两篇，就研究不考虑时间因素的情况下，如何给出排名。一种常见的错误算法是：　　得分 = 赞成票 - 反对票假定有两个项目，项目A是60张赞成票，40张反对票，项目B是550张赞成票，450张反对票。请问，谁应该排在前面？按照上面的公式，B会排在前面，因为它的得分（550 - 450 = 100）...

期权知识 2020-08-18 416 0
基于用户投票的排名算法（六）：贝叶斯平均

（这个系列实在拖得太久，今天是最后一篇。）上一篇介绍了"威尔逊区间"，它解决了投票人数过少、导致结果不可信的问题。举例来说，如果只有2个人投票，"威尔逊区间"的下限值会将赞成票的比例大幅拉低。这样做固然保证了排名的可信性，但也带来了另一个问题：排行榜前列总是那些票数最多的项目，新项目或者冷门的项目，很难有出头机会，排名可能会长期靠后。以IMDB为例，它是世界最大的电影数据库，观众可以对每部电影投票，最低为1分，最高为10分。系统根据投票结果，计算出每部电影的平均得分。然后，再根据平均得分，排出...

期权知识 2020-08-18 592 0
虚数的意义

有人在Stack Exchange问了一个问题：　　"我一直觉得虚数（imaginary number）很难懂。　　中学老师说，虚数就是-1的平方根。　　　　可是，什么数的平方等于-1呢？计算器直接显示出错！　　直到今天，我也没有搞懂。谁能解释，虚数到底是什么？　　它有什么用？" 帖子的下面，很多人给出了自己的解释，还推荐了一篇非常棒的文章《虚数的图解》。我读后恍然大悟，醍醐灌顶，原来虚数这么简单，一点也不奇怪和难懂！下面，我就用自己的语言，讲述我所理解的虚数。一、什么是虚数？...

期权知识 2020-08-18 547 0
贝叶斯推断及其互联网应用（三）：拼写检查

（这个系列的第一部分介绍了贝叶斯定理，第二部分介绍了如何过滤垃圾邮件，今天是第三部分。）使用谷歌的时候，如果你拼错一个单词，它会提醒你正确的拼法。比如，你不小心输入了 seperate。谷歌告诉你，这个词是不存在的，正确的拼法是 separate。这就叫做"拼写检查"（spelling corrector）。有好几种方法可以实现这个功能，谷歌使用的是基于贝叶斯推断的统计学方法。这种方法的特点就是快，很短的时间内处理大量文本，并且有很高的精确度（90%以上）。谷歌的研发总监 Peter No...

期权知识 2020-08-18 514 0
高斯模糊的算法

通常，图像处理软件会提供"模糊"（blur）滤镜，使图片产生模糊的效果。 "模糊"的算法有很多种，其中有一种叫做"高斯模糊"（Gaussian Blur）。它将正态分布（又名"高斯分布"）用于图像处理。本文介绍"高斯模糊"的算法，你会看到这是一个非常简单易懂的算法。本质上，它是一种数据平滑技术（data smoothing），适用于多个场合，图像处理恰好提供了一个直观的应用实例。一、高斯模糊的原理所谓"模糊"，可以理解成每一个像素都取周边像素的平均值。上图中，2是中间点，周边点都是1...

期权知识 2020-08-18 494 0