显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 
 
 
 

[置顶] 博客迁移至Github

2015-12-9 7:37:43 阅读345 评论0 92015/12 Dec9

网易博客是不错的产品,但Github能提供一个更自由更强大的博客编辑环境。自2015年12月4日起,此博客将暂停更新。新的博客内容请访问我的Github page(http://vividfree.github.io/)。

作者  | 2015-12-9 7:37:43 | 阅读(345) |评论(0) | 阅读全文>>

FTRL算法理解

2015-12-2 23:49:23 阅读2758 评论2 22015/12 Dec2

引言

       在工业界,越来越多的业务需要大规模机器学习,不单参与训练的数据量大,模型特征量的规模也大。例如点击率预估,训练数据量在TB量级,特征量在亿这个量级,业内常用LR(Logistic Regression)和FM(Factorization Machines)为点击率预估建模。对LR、FM这类模型的参数学习,传统的学习算法是batch learning算法,它无法有效地处理大规模的数据集,也无法有效地处理大规模的在线数据流。这时,有效且高效的online learning算法显得尤为重要。

SGD算法[1]是常用的online learning算法,它能学习出不错的模型,但学出的模型不是稀疏的。为此,学术界和工业界都在研究这样一种online learning算法,它能学习出有效的且稀疏的模型。FTRL(Follow the Regularized Leader)算法正是这样一种算法,它由Google的H. Brendan McMahan在2010年提出的[2],后来在2011年发表了一篇关于FTRL和AOGD、FOBOS、RDA比较的论文[3],2013年又和Gary Holt, D. Sculley, Michael Young等人发表了一篇关于FTRL工程化实现的论文[4]。如论文[4]的内容所述,FTRL算法融合了RDA算法能产生稀疏模型的特性和SGD算法能产生更有效模型的特性。它在处理诸如LR之类的带非光滑正则化项(例如1范数,做模型复杂度控制和稀疏化)的凸优化问题上性能非常出色,国内各大互联网公司都已将该算法应用到实际产品中。

作者  | 2015-12-2 23:49:23 | 阅读(2758) |评论(2) | 阅读全文>>

ROC和AUC介绍

2015-11-20 18:07:18 阅读670 评论0 202015/11 Nov20

ROC(Receiver Operating Characteristic)曲线和AUC(Area Under Curve)常被用来评价一个二值分类器(binary classifier)的优劣。相比准确率、召回率、F-score这样的评价指标,ROC曲线有这样一个很好的特性:当测试集中正负样本的分布变化的时候,ROC曲线能够保持不变。在实际的数据集中经常会出现类不平衡(class imbalance)现象,即负样本比正样本多很多(或者相反),而且测试数据中的正负样本的分布也可能随着时间变化。

论文[3]是篇很不错的文章,介绍了ROC和AUC的特点,如何作出ROC曲线图和计算AUC,AUC的含义,以及对多类别分类问题如何计算AUC。后来有篇博文[4]翻译了这篇文章的核心部分,浅显易懂,适合不喜欢读英文的读者。

图1摘自论文[3]。ROC曲线,是以一系列的(fp rate, tp rate)或者写成(FPR, TPR),为二维笛卡尔坐标系中的坐标点。应用到实际问题中,对一份训练集如何算出一系列的FPR和TPR,可以参考[3]或[4]。

AUC(确切的说,应该是AUROC)被定义为ROC曲线下的面积,显然这个面积的数值不会大于1。ROC曲线上的任意相邻两点与横轴都能形成梯形,把所有这样的梯形面积做加和即可得到AUC。一般而言,训练样本越多,在得到样本判别为正例的分数取值后不同分数也相对会越多,这样ROC曲线上的点也就越多,估算的AUC会更准些。这种思路很像微积分里常用的微分法。该方法正是在论文[3]中描述的方法,笔者在实际业务中实现了它,它并不难实现。

作者  | 2015-11-20 18:07:18 | 阅读(670) |评论(0) | 阅读全文>>

Index of Matrix

2015-11-14 16:48:05 阅读180 评论0 142015/11 Nov14

理论方面工程方面使用MapReduce实现大规模稀疏矩阵相乘 (上篇)(下篇

作者  | 2015-11-14 16:48:05 | 阅读(180) |评论(0) | 阅读全文>>

使用MapReduce实现大规模稀疏矩阵相乘(下)

2015-11-14 16:26:40 阅读564 评论0 142015/11 Nov14

4 适用于稀疏矩阵的矩阵相乘算法 4.1 矩阵相乘的向量表达形式

       公式1还可以用向量的形式来表达,如公式2所示,其与公式1是等价的。

C = sigma ( A[][i] * B[i][] ) , i={0,1, …, n-1} (2)

A的列向量有n个,B的行向量也有n个,将A的某个列向量与B的对应行向量相乘,得到m*k的中间结果矩阵,将这n个中间结果矩阵相加,即得到结果矩阵C。公式2表面上看似抽象,但放到具体的业务中,其实有很强的物理意义。举个例子(就用第1节中的第2个例子):现有第1份数据是每个用户浏览的URL列表,每个URL带有权重分数,第2份数据是query到URL的搜索点击关系,每个URL也带有权重分数,用户规模、query规模、URL的规模均在数千万的规模,现在有个任务是给每个用户找出一批合适的query来描述。对这个问题,矩阵A的m是全部的user,n是全部的URL;矩阵B的n是全部的URL,k是全部的搜索query。公式2的意思就是说:对某个URL而言,将其对应的user向量与query向量进行相乘,得到一个user到query的中间结果矩阵C',维度是m*k。遍历全部的URL,将得到的各个中间结果矩阵C'相加即可得到矩阵C。通过这样一个解释能看到,作为索引项的URL其实是从user到query这种联系的桥梁。

对于稀疏矩阵,某个URL对应的user向量和query向量有很多是零值,这些零值元素对计算出最终的矩阵C没有任何数值上的贡献。如果不是直接

作者  | 2015-11-14 16:26:40 | 阅读(564) |评论(0) | 阅读全文>>

使用MapReduce实现大规模稀疏矩阵相乘(上)

2015-11-14 16:26:16 阅读587 评论0 142015/11 Nov14

1. 引言

       在DT时代,挖掘海量数据并从中提炼出有价值的信息是各大互联网公司的重要目标之一。在拥有海量数据后,各种各样的数据挖掘任务就出现了,大规模稀疏矩阵相乘就是其中一项常见的计算任务。在文本处理或者说自然语言处理中,稀疏矩阵是常见的数据表达形式,对大规模稀疏矩阵做乘法的业务需求也是很常见,比如:

现有大量的object(比如数千万甚至更大的规模),已通过某种特征抽取算法建立起每个object的稀疏特征向量,这里object可以是query、word、URL、host、APP、商品、用户等,现在有个任务是对每个object找出与其相似的object。在个性化推荐领域中经常碰到这类问题。

现有第1份数据是每个用户浏览的URL列表,每个URL带有权重分数,第2份数据是query到URL的搜索点击关系,每个URL也带有权重分数,用户规模、query规模、URL的规模均在数千万的规模,现在有个任务是给每个用户找出一批合适的query来描述。

现有第1份数据是每个用户浏览的商品ID列表,每个商品ID带有权重分数,第2份数据是query到商品ID的搜索点击关系,每个商品ID也带有权重分数,用户规模、query规模、商品ID的规模均在数千万的规模,现在有个任务是给每个用户找出一批合适的query来描述。(这里,query也可以变成是商品的核心词)

已有一份词典D,其对每个query列举了与其相似query和相似性分数,左侧query的规模在数千万的规模。但是其中有些

作者  | 2015-11-14 16:26:16 | 阅读(587) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 

日志分类

 
 
日志分类列表加载中...
 
 
 
 
 

热门日志

 
 
数据列表加载中...
 
 
 
 
 

最新日志

 
 
数据列表加载中...
 
 
 
 
 
 
 
模块内容加载中...
 
 
 
 
 

Visitors

 
 
模块内容加载中...
 
 
 
 
 

新浪微博

 
 
模块内容加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017

注册 登录  
 加关注