0%

传统的搜索引擎排序(Ranking)问题,通常会涉及到很多的排序策略。这些策略根据不同的特征,在不同的适用范围中起作用。因此,一个传统的排序算法,至少涉及到两方面的内容:策略的制定,以及不同策略的组合。策略的组合需要考虑策略分析适用的特征,以及相应策略的适用情况。根据这些内容,通过人工或者半机器半人工的方式组合起来,才能组成一个可堪使用的排序算法。

自然语言处理中遇到的情况一样,随着数据量的增加,使用人工的方式做策略的组合,会变得越来越困难。因此,将机器学习引入搜索引擎排序问题,也就是相当自然的事情了。在排序问题中使用的机器学习算法,被称为 Learning to Rank (LTR) 算法,或者 Machine-Learning Rank (MLR) 算法。

LTR 算法通常有三种手段,分别是:Pointwise、Pairwise 和 Listwise。Pointwise 和 Pairwise 类型的 LTR 算法,将排序问题转化为回归分类或者有序分类问题。Listwise 类型的 LTR 算法则另辟蹊径,将用户查询(Query)所得的结果作为整体,作为训练用的实例(Instance)。

LambdaMART 是一种 Listwise 类型的 LTR 算法,它基于 LambdaRank 算法和 MART (Multiple Additive Regression Tree) 算法,将搜索引擎结果排序问题转化为回归决策树问题。MART 实际就是梯度提升决策树(GBDT, Gradient Boosting Decision Tree)算法。GBDT 的核心思想是在不断的迭代中,新一轮迭代产生的回归决策树模型拟合损失函数的梯度,最终将所有的回归决策树叠加得到最终的模型。LambdaMART 使用一个特殊的 Lambda 值来代替上述梯度,也就是将 LambdaRank 算法与 MART 算法加和起来。考虑到 LambdaRank 是基于 RankNet 算法的,所以在搞清楚 LambdaMART 算法之前,我们首先需要了解 MART、RankNet 和 LambdaRank 是怎么回事。

阅读全文 »

本篇基本上是原作的翻译。转载请保留本段文字。

复杂度通常会使用大-O 记号来表示,比如快速排序的平均时间复杂度是 $O(n \log(n))$。虽然我是「理解派」,但是虽然每个算法/数据结构都理解了,不时仍有可能忘记具体某个算法/数据结构的复杂度(特别是在最好、最坏和平均情形下的复杂度)。因此制作一个速查表是蛮有必要的。

动手前先看看是否已经有轮子是一个好习惯,果不其然,我找到了原作

阅读全文 »

不论是生活中还是工作中,总有一些文件会不断产生。这些文件可能是日志文件,也可以是系统核心转储文件。如若不加清理,查询特定文件就会非常困难,抑或是过多的核心转储文件占满了磁盘空间,影响正常程序执行。

为此,我们需要有一个简单高效的方式,定期清理过期文件。

阅读全文 »

此篇缘起匡世珉知乎回答。感谢匡世珉和他的铅笔们,也感谢我自己小时候为尺规作图付出的时间。

尺规作图(ruler-and-compass construction)是古希腊数学提出的一种平面几何作图方法。除了提出作图方法,古希腊人还留下了三个尺规作图困难问题。他们是:

  • 三等分任意给定的角;
  • 对任意给定的立方体,作一个新的立方体,使得新立方体的体积是前者的 2 倍;
  • 对任意给定的圆,作一个正方形,使得圆和正方形的面积相等。

如今,这三个困扰数学家上千年的问题,均已经被证明不可解——当然,一些青 (min) 年 (ke) 还在被困扰着。

此篇将介绍上述三等分角的问题。

阅读全文 »

和实际使用中的 Python 一样,伪代码的排版很讲究缩进。书写 Python 代码,通常会使用等宽字族(打字机字族),因此缩进一板一眼十分清晰;然而,在排版算法时,经常会遇到非等宽的字族和等宽字族混用的情况——此时,缩进有时候就不那么明确了。此时,给伪代码排版加上垂直的缩进提示线能够起到很好的提示作用。

阅读全文 »