三个凑皮匠,顶一个诸葛亮,打一算法: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

由于Pairwise方式的排序学习方法 训练样本构建方便、速度快同时效果也还可以,因此在工业界和学术的应用非常广泛^_^

2002-RankSvm

RankSvm是最经典的一种,将其余的相关实现方法学习总结简单的记录到本文中。
RankSvm的学习记录在这里

2006-IRSVM

IRSVM直接是RankSvm的改进,RankSvm的训练目标是让序列pair的不一致pair对对最少,其优化函数为:
$$\tau(r_a,r_b)=\frac{P-Q}{P+Q}=1-\frac{2Q}{\binom{m}{2}}$$
因此直接暴露了两大问题:

问题1:位置误差

Read More

RankSvm是Pairwise的学习排序中最早也是非常著名的一种算法,主要解决了传统PontWise构建训练样本难的问题,
并且基于Pair的构建的训练样本也更为接近排序概念

基本介绍

RankSvm是在2002年提出的,之前工作关于LTR的工作貌似只有Pointwise相关的,比如PRanking,这样的排序学习算法Work需要含有档位标注的训练样本,一般有以下几种获取方式:

  1. 需要人工/专家标注
  2. 诱导用户对展现的搜索结果进行反馈

这样就会存在会成本高、可持续性低、受标准者影响大等缺点。

Read More

McRank是学习排序(Learning to Rank)的单文档排序分支(Pointwise)中较为经典的一种,本文是读原Paper[1]之后自己的一个理解.

基本介绍

McRank的全称是Multiple Classification Rank,可以理解为将学习排序转为机器学习中的一个多分类问题.
McRankDCG指标进行优化,并且可以证明DCG的误差可以被分类误差给bounded住.

折损累积增益

DCG(Discounted Cumulative Gain)是在信息检索领域评估一个rank好坏的常用指标。(在实际使用中一般会进行归一化,称为NDCG,可以看这里).

假设在指定的query下通过某个排序算法对$n$个文档进行排序,则可以得到
$$DCG=\sum_{i=1}^{n}c_{[\pi_i]}(2^{y_i}-1)$$

Read More

这应该严格意义上不算Hexo的bug,但是在写Mathjax的时候就会踩中-_-

说起Markdown写文章时,加粗的第一反应是**,斜体的第一反应是*,因为各种Markdown格式规范的文章里面都是这么教的,但是你不知道的是__可以支持粗体,_可以支持斜体,一般而言这是没什么问题,但是当在写LatexHexo里使用Mathjax实现)数据公式时,_表示下标,并且使用频率很高,当一行里面有多个_出现时,Hexo进行解析导致所期待的公式失效。

自从用Hexo写数学公式的时候,就发现一点小问题,公式复杂了,在Hexo里面就不work,起初以为是Mathjax的支持不完善的缘故,后来发现用了Mathjax的其他博客里面都可以写复杂的公式,而今天又遇到了这个问题:
我的公式文本是:
对于每个$X_i$,$P(X_i|Y=y_k)$服从高斯分布$N(\mu_{ik},\sigma_i)$
结果生成页面查看之后却发现:

Read More

为啥要做Proximity计算

先来看下信息检索/搜索引擎 的一般架构流程:

  1. Doc进行分词,这些分词也叫做Term,然后离线做各种计算
  2. 将这些Term灌入倒排索引中
  3. 用户查询
  4. 根据倒排召回命中Term的文档
  5. 将文档根据各个Term算分排序

其实可以发现这里查的Term 都是bag-of-words的形式,并且第五步的算法也一般是在线的,所以基本不会做全文扫描之类的事情,那么这样的话问题就来了:

Read More