【学习排序】 Learning to Rank中Pointwise关于PRank算法源码实现_pranking with ranking

    最近终于忙完了Learning to Rank的作业,同时也学到了很多东西.我准备写几篇相关的文章简单讲述自己对它的理解和认识.第一篇准备讲述的就是Learning to Rank中Pointwise的认识及PRank算法的实现.主要从以下四个方面进行讲述：
    1.学习排序(Learning to Rank)概念
    2.基于点的排序算法(Pointwise)介绍
    3.基于顺序回归(Ordinal Regression-based)的PRank排序算法
    4.PRank算法Java\C++实现及总结

一. 学习排序(Learning to Rank)概念

    学习排序概念推荐转载的文章：机器学习排序之Learning to Rank简单介绍
    1.首先,为什么会出现学习排序呢?
    传统的排序方法是通过构造一个排序函数实现，在Information Retrieval领域一般按照相关度进行排序。比较典型的是搜索引擎中一条查询query，将返回一个相关的文档document，然后根据(query,document)之间的相关度进行排序,再返回给用户。
    而随着影响相关度的因素(如PageRank)变多，Google目前排序方法考虑了200多种方法。这使得传统排序方法变得困难，人们就想到通过机器学习来解决这一问题，这就导致了Learning to Rank的诞生。
    2.然后是学习排序的基本流程如下图所示.
    很明显它就是基本步骤就是通过训练集数据(Train Set)学习得到模型h,然后通过该模型去对测试集数据(Test Set)进行计算和排序,最后得到一个预测的结果.

二. 基于点的排序算法(Pointwise)介绍

    机器学习解决排序学习问题可分为3类:
    1.基于回归排序学习(regression-based algorithms):序列转为实数
    2.基于分类排序学习(classification-based algorithms):二值分类
    3.基于顺序回归排序学习(ordinal regression-based algorithms)
    但是这里我想讲述的是最常见的分类,它们应该与上面是交叉的:
    1.基于点的LTR算法——Pointwise Approach
    2.基于对的LTR算法——Pairwise Approach
    3.基于列的LTR算法——Listwise Approach

    Pointwise处理对象是一篇文档,将文档转化为特征向量后,机器学习系统根据训练得出的模型对文档进行打分(注意:训练集学习出权重模型去给测试集文档打分是LTR中非常经典的用法),打分的顺序即为搜索排序的结果.
    Score(x)=w1*F1+w2*F2+w3*F3+...+w136*F136
    其中w1-w136为136维对应权重参数,由训练集训练得到;F1-F136为测试文档给出136个特征值.
    原数据有5个类标(0-4代表相关程度：Perfect>Excellent>Good>Fair>Bad),则设置5个阈值来区分所得分数的分类.如果得分大于相关阈值,则划分为相应的类.常见算法包括：Prank、McRank
    下面是我自己画的一张图,其中四根红线是四个阈值,它把这些文档集划分为了五个不同类.每当一个新的文档来测试,它都会根据已有模型计算出相应分数,再根据分数和阈值划分类即可.

三. PRank算法介绍

    PRank算法是基于点的排序学习,顺序回归学习问题.其算法主要参考Kolby Crammer & Yoram Singer(From:The HeBrew University,以色列希伯来大学)论文《Pranking with Ranking》.网址如下：
    http://papers.nips.cc/paper/2023-pranking-with-ranking.pdf
    算法过程如下：

四. PRank算法Java\C++实现及总结

    1.Java代码实现
    代码中有详细注释,每个步骤都是按照上面的算法进行设计的.左图是主函数,它主要包括：读取文件并解析数据、写数据(该函数可注释掉,它是我用于验证读取是否正确时写的)、学习排序模型和打分预测.右图是预测排序结果的算法.

    2.C++代码实现
    该部分代码参考自新浪播客：
    http://blog.sina.com.cn/s/blog_4c98b960010008xn.html
    运行结果过程如下图所示,通过train.txt数据集得到model.txt,里面存储的是46个权重.如:
    -0.052744 1.886342 1.002179 -6.400005 -1.824795 0.000000 0.000000 ..
    然后通过该模型对test.txt进行打分预测,同时计算正确率(已标注Label=预测Label).

#include <iostream>
#include <fstream>
#include <limits>
#include <iomanip>
 
using namespace std;
 
#define K 3  //排序的序数,即如排成全相关,部分相关,不相关,序数就是3
#define N 46 //特征的维数
 
double *w;			//权值 
int *b;				//偏置项 
int *y;
int *t;
 
//从文件中获得特征值 X 存储特征向量 yt 存储标签
bool getData(double *x,int &yt,ifstream &fin)	 
{
    if (fin.eof())
        return false;
 
    char data[1024];
    int index = 1;
    fin.getline(data,1024);
    char *p = data;
    char q[100];
    q[0] = p[0];
    q[1] = '\0';
    yt = atoi(q) + 1;								// 标签 
    p = p+8;//跳过qid:xx的冒号
    for( ; *p != '\0'; ++p)
    {
        if(*p == ':')
        {
            ++p;
            int i = 0;
            for(i=0; *p != ' '; i++, p++)
            {
                q[i] = *p;
            }
            q[i] = '\0';      
            x[index ++] = atof(q);
        }
    }
    return true;
}
 
//各变量进行初始化
void Initialize()
{
    w = new double[N+1];
    b = new int[K+1];
    y = new int[K+1];
    t = new int[K+1];
    int i;
    int r;
    for(i=1; i<=N;i++)
        w[i] = 0 ;
    for(r=1;r<=K-1;r++)
        b[r] = 0;
    b[K] = std::numeric_limits<int>::max();//无穷大
}
 
//利用Prank算法进行训练
void PrankTraining(double *x,int yt)
{
    int i;
    int r;
    double wx = 0;				//存储 W*X 的计算结果 
    for(i =1; i<=N; i++)		//计算 W*X 
        wx += w[i] * x[i];
    for(r =1; r<=K; r++)		//找到满足 W*X-b<0 的最小 r 
    {
        if(wx - b[r] <0 )
            break;
    }
    int yy = r ;				//预测值 
    if (yy == yt)				//预测正确，直接返回 
	{
		return;
	}				
    else						//预测错误，权值更新 
    {
        for(r=1; r<K; r++)
        {
            if(yt <= r)
                y[r] = -1;
            else
                y[r] = 1;
        }
        for(r=1; r<K; r++)
        {
            if ((wx-b[r])*y[r] <= 0)
            {
                t[r] = y[r];
            }
            else
                t[r] = 0;
        }
        //更新 W 和 b 
        int sumt = 0;
        for(r=1; r<K; r++)
            sumt = sumt + t[r];
        for(i=1;i<=N;i++)				//更新 W 
            w[i] = w[i] + sumt*x[i];
        for(r=1; r<K; r++)				//更新 b 
            b[r] = b[r] - t[r];
    }
}
 
//利用得到的model进行测试
int Pranking(double *x)
{
    int i;
    int r;
    double wx = 0;
    for(i=1; i<=N; i++)
        wx = wx + w[i] * x[i];
    for(r=1; r<=K; r++)
        if(wx - b[r] <0 )
		{
			cout<< " "<<wx;
            break;
		}
    return r;
}
 
 
int main(int argc,char **argv)
{
    int right=0,wrong=0;//排正确和错误的样本数
	//输入训练数据文件名 
	string sin_train = "train.txt";
    ifstream fin_train(sin_train.c_str());
    if(fin_train.fail())
    {
        cout << "can't open the traningsetFile!"<<endl;
        return -1;
    }
	//输入输出模型文件名 
	string sout_model = "model.txt";
	ofstream fout_model(sout_model.c_str()); 
    if(fout_model.fail())
    {
        cout << "can't open the ModelFile!"<<endl;
        return -1;
    }
	//输入测试数据文件名
	string sin_test = "test.txt";
	ifstream fin_test(sin_test.c_str()); 
    if(fin_test.fail())
    {
        cout << "can't open the testsetFile!"<<endl;
        return -1;
    }
	// 输入输出结果文件名
	string sout_result = "result.txt";
	ofstream fout_result(sout_result.c_str()); 
    if(fout_result.fail())
    {
        cout << "open resultFile  failed!"<<endl;
        return -1;
    }
    double *tr = new double[N+1];	// 特征向量 
    int yt;							// 标签 
    Initialize();					//初始化权值w和偏置项b 
    int i = 0;
    //读入训练数据进行训练得到model
    while(true)
    {
        if (getData(tr,yt,fin_train))
        {
            PrankTraining(tr,yt);//训练
        }
        else
            break;
    }
	//将得到的w和b写入文件
    char   buff[128];
    cout<<"训练出的w为:\n";
    for(i=1; i<=N; i++)						//写 w
    {
        cout<<setw(8)<<w[i]<<'\t';
        memset(buff,0,sizeof(buff));  
        sprintf(buff,"%f",w[i]);
        fout_model << buff << " ";
    }
    fout_model<<endl;
    cout<<"\n\n训练出的b为:\n";
    for(i = 1; i<K;i++)						//写 b
    {
        cout<<b[i]<<'\t';
        memset(buff,0,sizeof(buff));  
        sprintf(buff,"%d",b[i]);
        fout_model << buff << " ";
    }
	//读入测试数据进行测试得到正确率
    while(true)
    {
        if (getData(tr,yt,fin_test))
        {
            int yy = Pranking(tr);
            char p[2];
            p[0] = yy -1 + 48;
            p[1] = '\0';
            fout_result << p << endl;
 
            if (yy == yt)
                right ++;
            else
                wrong ++;
 
        }
        else
            break;
    }
    cout<<"\n\n排正确的个数为"<<right<<",错误的个数为"<<wrong<<",正确率为%"<<right*100*1.0/(right+wrong)<<endl;
	cout<<b[0]<<'\t'<<b[1]<<'\t'<<b[2];
	//释放申请的空间并关闭文件  
    delete []w;   
    delete []y;
    delete []t;
    delete []b;
    delete []tr;
    fin_train.close();
    fin_test.close();
    fout_result.close();
    fout_model.close();
	system("PAUSE");
    return 0;
}

五. 总结与问题

    最后讲述在该算法中你可能遇到的问题和我的体会:
    1.由于它是读取文件,可能文件很大(几百兆或上G).最初我设计的数组是double feature[10000][136],用来存储每行特征值,但是如果行数太大时,What can do?此时我们应该设置动态数组<List<List<Float>>>x解决.
    2.最初阅读了CSDN的Prank代码,它迭代了1万次,最后查看原文发现它并没有迭代.所以你可以参考C++那部分代码,每次只需要读取一行数据处理,并记住上一次的46维权重和阈值即可.
    3.为什么我从136维数据转变成了46维数据?
    你打开136维特征值数据时,你会发现它的值特别大,不论是Pointwise,还是Pairwise和Listwise都可能出现越界,一次内积求和可能就10的7次方数据了.但是46维数据,每个特征值都是非常小的,所以如果用136维数据,你需要对数据进行归一化处理,即数据缩小至-1到1之间.
    4.评价Pointwise、Pairwise和Listwise指标通常是MAP和NDCG@k,后面讲述基于对的学习排序和基于列的学习排序会具体介绍.
    5.你可能会发现数据集中存在vail验证集,以及交叉验证、交叉熵、梯度下降后面都会讲述.但由于相对于算法,我对开发更感兴趣,很多东西也是一知半解的.
    6.最后要求该算法到Hadoop或Spark实现并行化处理,但算法的机制是串行化.有一定的方法,但我没有实现.我们做的是一种伪并行化处理,即模型得到权重后进行并行化计算分数排序.
    最后简单附上我们的实验结果,后面的算法实验结果是基于MAP和NDCG@k