引言

在信息检索中文本相关性计算是至关重要的一个特征,关于文本相关性计算时用的比较多的有:词频/频率tf/idf/tf*idfbm25布尔模型空间向量模型以及语言模型,本文主要是对于[1]的一些学习理解,虽然[1]历史久远,但是可行性高,同时目前也有不少搜索引擎在使用[1]的方法,主要介绍的是语言模型在信息检索中使用的平滑方法,主要侧重点就是性能。

Language Model

现假设query是基于文档d进行生成的,那么给定一个query$q=q_1q_2..q_n$以及一个文档$d=d_1d_2…d_n$,我们比较关心的是$p(d|q)$这个条件概率,即在观察到$q$的情况下生成$d$的一个概率,假设文档中的词是相关独立的,根据贝叶斯公式,则有:
$$p(d|q) \propto p(q|d)p(d)$$

Read More

AUC介绍

AUC(Area Under Curve)是机器学习二分类模型中非常常用的评估指标,相比于F1-Score对项目的不平衡有更大的容忍性,目前常见的机器学习库中(比如scikit-learn)一般也都是集成该指标的计算,其计算原理可以参考这个ROC和AUC介绍以及如何计算AUC ,但是有时候模型是单独的或者自己编写的,此时想要评估训练模型的好坏就得自己搞一个AUC计算模块,本文在查询资料时发现libsvm-tools1有一个非常通俗易懂的auc计算,因此抠出来用作日后之用。

Read More

为啥要有LambdaRank

首先来看这么一个问题,机器学习一般都会有两个指标,一个叫做优化指标(Optimization Cost),另一个叫做评测指标(Target Cost),其中优化指标是训练时一直优化的目标,他一般都是需要连续可导(否则优化难度很大),另一个评测指标就是模型训练完了之后来评估这个模型的好坏。比如SVM模型的优化指标就是样本点距离分类面的距离最大化($\underset{w,b}{max} \quad \gamma$),而其评测指标一般都是准确率、F1值或者AUC等。
在信息检索领域其实也是这样,其排序的评测指标一般是NDCG、MAP、ERR等,但是这类指标都是非凸或者不连续,并无法直接进行优化,所以很多排序学习算法的优化一般都是都是Corss Entropy或者MSE

RankNet中优化的目标是Corss Entropy,他们是近似于Pairwise Error,但是这个评估指标并没有考虑排在靠前的文档。

Read More

RankNet是一种基于pairwise的学习排序,假设文档AP的概率排在文档B的前面,则RankNet就是使用神经网络算法来使得这个概率最大化.last update at:2016-08-28

算法原理

假设现在有一对文档$D_i$和$D_j$,给定一个目标概率$\bar{P}_{i,j}$,以表示文档$D_i$将会排在文档$D_j$的前面.

  1. 如果$\bar{P}_{i,j}=1$,表示$D_i$一定会排在$D_j$前面
  2. 如果$\bar{P}_{i,j}=0.5$,表示$D_i$和$D_j$的前后关系将无法确定
  3. 如果$\bar{P}_{i,j}=0$,表示$D_i$一定不会排在$D_j$前面

现在有一个实值的排序函数$f$,如果$f(x_i) > f(x_j)$,则会有$D_i \triangleright D_j$(表示$D_i$会排在$D_j$前面)

这里$x$是为文档$D$所表示的特征向量

Read More

GBRank是一种pairwise的学习排序算法,他是基于回归来解决pair对的先后排序问题。在GBRank中,使用的回归算法是GBT(Gradient Boosting Tree),可以参考这个pairwise相关的可以参考这个

算法原理

一般来说在搜索引擎里面,相关性越高的越应该排在前面。现在query-doc的特征使用向量$x$或者$y$表示,假设现在有一个文档对$\left \langle x_i,y_i \right \rangle$,当$x_i$排在$y_i$前面时,我们使用$x_i \succ y_i$来表示。

我们含顺序的pair对用如下集合表示(也就是真的$x_i$真的排在$y_i$前面):$$S=\{ \left \langle x_i,y_i \right \rangle | x_i \succ y_i,i = 1…N \}$$

现假设学习的排序函数为$h$,我们希望当$h(x_i)>h(y_i)$时,满足$x_i \succ y_i$的数量越多越好.
现在将$h$的风险函数用如下式子表示:$$R(h) = \frac{1}{2} \sum_{i=1}^N \left( max\{0,h(y_i)-h(x_i)\} \right)^2$$

Read More

CentOS自带的python一般都是2.4.3,因为某些特殊的需求需要将其升级到2.6.2

下载python2.6.5

直接在这个地址进行下载即可https://www.python.org/download/releases/2.6.5/

进行解压

1
tar xvf Python-2.6.5.tgz

编译安装

先配置安装的前缀

1
./configure --prefix=/usr/local/python2.6.5

然后真正的执行编译安装

1
2
make
make install

注意如果是非管理员用户 请在两个make前面都加上sudo

添加快捷方式

1
ln -sf /usr/local/python2.6.5/bin/python /usr/bin/python

如果原来快捷方式存在 那么先删除,再添加

完工

python --version
Python 2.6.5 

参考

CentOS5.5下安装python2.6 实用,但是排版太难看了-_-

本文大部分参考(译)自wiki[1]
如果说Gradient Boosting是一种机器学习算法框架的话,我想GBT(Gradient Boosting Tree)看做它的实现更为合适

Gradient Boosting原理

与其他Boosting方法一样,Gradient Boosting通过迭代将弱分类器合并成一个强分类器的方法。

对于标准的$(x_i,y_i)$训练集,Gradient Boosting在迭代到第$m$次时,可能会得到一个分类能力不是很强的$f_m$模型,但是他下次迭代并不改变$f_m$,而是生成一个这样的新模型:$$f_{m+1} = f_m+G_{m+1}$$使得$f_{m+1}$较$f_m$而言拥有更为强大的分类能力,那么问题来了,这个$G_{m+1}$该如何训练呢?

Read More

今天在尝试使用scikit-learn的AdaBoost模型时一直报错,

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Library/Python/2.7/site-packages/sklearn/__init__.py", line 57, in <module>
from .base import clone
File "/Library/Python/2.7/site-packages/sklearn/base.py", line 11, in <module>
from .utils.fixes import signature
File "/Library/Python/2.7/site-packages/sklearn/utils/__init__.py", line 10, in <module>
from .murmurhash import murmurhash3_32
File "numpy.pxd", line 155, in init sklearn.utils.murmurhash (sklearn/utils/murmurhash.c:5029)
ValueError: numpy.dtype has the wrong size, try recompiling

以为是numpy包的问题:卸载重装之后还是照样有问题-_-

Read More

三个凑皮匠,顶一个诸葛亮,打一算法:AdaBoost
本文是自己对AdaBoost的理解,健忘-_-!! 故记录在此.

简介

痛点:大部分强分类器(LRsvm)分类效果还不错,但是可能会遇到过拟合问题,并且训练相对复杂,耗时~
另外大部分弱分类器(阈值分类器,单桩决策树(decision stump)等),他们分类的效果差,可能是极差,只会出现欠拟合,但是他们训练预测快,很快~

天下武功,唯快不破做减法不易,但是做加法就相对简单了^_^ 这就是提升方法.

提升方法需要解决的两个问题:

  1. 在每一轮训练时如何改变数据的权值或概率分布?
  2. 如何将弱分类器组合成一个强分类器?

AdaBoost对此进行了很好的解决:

  1. 分而治之:将前一轮分错的样本加大权重,迫使在第二轮中对这些样本尽量分对,同时减少分对样本的权重.
  2. 加权多数表决:加大错误率小的弱分类器的权重,使其在最终表决中占较大作用,同时减少错误率较大的弱分类器的权重.

Read More

机器学习算法一般都是对损失函数(Loss Function)求最优,大部分损失函数都是包含两项:损失误差项(loss term)以及正则项(regularization term):
$$J(w)=\sum_iL(m_i(w))+\lambda R(w)$$

损失误差项

常用的损失误差项有5种:

  1. Gold Standard
  2. Hinge:Svm
  3. log:logistic regression(cross entropy error)
  4. squared:linear regression
  5. Exponential:Boosting

Read More