随着应用数据的增长,在大规模数据集上进行统计分析和机器学习越来越成为一个巨大的挑战。目前,适用于统计分析/机器学习的语言/库有很多,如专为数据分析用途而设计的R语言,Python语言的机器学习库Scikits,支持分布式环境扩展的有基于Map-Reduce实现的Mahout,以及分布式内存计算框架Spark上的机器学习库MLlib等等。目前Spark框架也推出了R语言的接口SprakR。但是,本文要讨论的,则是另外一种设计思路,在database中实现统计分析和机器学习算法,即In-Database Analysis,Madlib库就是这种设计思路的代表。
把机器学习库内置到database中(通过database的UDF)有许多优点,执行机器学习算法时只需要编写相应的SQL语句就可以了,同时database本身作为分析的数据源,使用非常方便,大大降低了机器学习的应用门槛。当然缺点也是明显的,由于受限于database提供的UDF编程接口,实现算法时会受到很多限制,很多优化难以实现,而大规模数据集上的机器学习,尤其是需要迭代计算的,通常对算法性能和结果收敛速度要求较高,否则很难做到实用。本文的重点就是讨论如何在In-database Analysis的框架下,高效的实现机器学习中的SGD(随机梯度下降)算法。由于很多机器学习算法如linear SVM分类器、K-mean、Logistic Regression都可以采用SGD算法来实现,只需要针对不同算法设计不同的目标函数即可。因此在database上实现高性能的SGD算法框架,便可用来执行一大类机器学习算法。
以Madlib为例,如果要Madlib用SVM算法对数据集做训练,可以执行如下SQL语句:
SELECT madlib.lsvm_classification( 'my_schema.my_train_data', 'myexpc', false );
madlib.lsvm_classification是Madlib中实现的SVM计算函数,上述方式的调用则是采用SGD算法进行linear SVM分类,其中my_schema.my_train_data是训练数据表,必须满足如下结构定义:
TABLE/VIEW my_schema.my_train_table ( id INT, -- point ID ind FLOAT8[], -- data point label FLOAT8 -- label of data point,即分类结果 );
执行之后生成的Model将会被存到第二个参数’myexpec’指定的表中。第三个参数(true/false)指定算法是否需要并行执行。
生成Model表myexpec后,执行以下SQL语句就可以进行预测:
SELECT madlib.lsvm_predict( 'myexpc', '{10,-2,4,20,10}' );
madlib.lsvm_classification函数还有更多的参数可以设置。如可以设置kernel-function,那么这时候计算实现的方式就不是SGD了,还可以设置迭代精度阈值等,具体参见Madlib文档。
从这个例子可以看出,Madlib库的使用是非常方便的,只要我们按照库函数要求建好相应的数据表并导入数据,就可以通过调用Madlib库中的SQL函数来进行模型训练和模型预测了。目前Madlib支持PostgreSQL、Greenplum、Pivotal HAWQ。
但是,在很多情形下,Madlib的执行性能是很差的,以基于SGD算法实现的机器学习训练模型为例,在数据量大的情况下经常需要几十小时甚至几百小时来完成,为了提高计算速度和模型收敛速度,有两个非常值得优化的地方:一是改为并发更新模型,二是优化数据读取顺序。
首先看基本的SGD算法框架在database的UDFA(自定义聚合函数)上的实现。以linear SVM为例,可以定义如下目标函数f(x):
其中<xi, yi>就是训练数据,w是训练模型。如下的梯度下降算法通过迭代找出使这个目标函数值尽可能小的w:
其中是步长值。
但是直接按照上式计算,每迭代一次,就需要遍历所有的数据,难以在实际场景中应用,因此就有了SGD(随机梯度下降)算法,对每一步迭代中的f(x),近似的用随机的一个数据点来代替原有f(x)中对所有数据点的求和:
在原始数据顺序随机的情况下,每次迭代只需要顺次取出一条记录并按上式进行迭代即可。这种迭代更新的计算方式,和database中提供的UDFA扩展接口是非常吻合的。可以把这个计算过程抽象为三个函数:
initialize(state) transition(state, row_data) terminate(state)
state用于存储这个UDFA计算上下文,对应SDG算法,state存的就是不停被迭代更新的model。row_data是每次读入的一行记录,即一个数据点。terminate函数返回最终的计算结果。具体这三个函数调用的次序如下图所示:
在PostgreSQL数据库中,这三个函数分别被命名为initcond、sfunc和finalfunc。
在训练数据表上执行一次这样的UDFA,相当于顺次用表中所有的数据按照上述的迭代式计算了一遍。通常要对总体数据迭代多遍才能得到想要精度的结果,因此Madlib库中那些训练函数实际上是用SQL脚本语言编写的函数,其中包含了对整个表数据的多轮迭代,直到获得所需精度的结果。如果数据表的数据顺序是有序的,那么顺次迭代将大大降低算法的收敛速度,这时可以先将数据表的数据顺序打乱再执行上述算法,如在PostgreSQL中,可以先用order by random()打乱数据顺序,然后再进行迭代计算。
上述的UDFA执行过程存在着两大缺陷:1.没有并行化。2.在数据量大的情况下,将数据次序打乱可能是一个非常大的开销。下面先讨论并行化的改进方案:
一个简单的并行化计算方法是,将表数据分为多个部分,每个部分有自己的model state,每个部分的model各自进行各自的迭代计算,当各个model都计算完毕时再进行合并。简单的合并方案就是将所有的model做平均值得到最终的model。为什么SDG算法可以用这种方法拆分计算然后取model平均值,可以参见这篇论文[1]。当然,这要求database对UDFA提供一个merge(state, state)的函数接口让用户来自定义合并方式。这种简单的并行化方式不仅可以应用在单机database上,也可以用在数据分布到多个结点上的分布式database/datawarehouse上,如Cloudera Impala。但是这种简单的share nothing的并行计算方案通常会极大的影响model的收敛速度,因此还需要寻找更好的并行执行方案。
实现不影响收敛速度的并行执行,就需要所有在不同区段数据上并发执行的UDFA去更新同一个model,这就要database提供Share-Memory的接口以便于UDFA访问共享内存。像PostgreSQL就提供了相应的接口[3]。
但是这种并发更新model的方式又带来了另外一个矛盾,在用迭代式更新model时必须对model加锁,假设多个UDFA计算线程同时工作,在同一时刻显然只有一个线程能获得锁进行计算并更新模型,本质上还是等同于单线程的计算效率。要解决这个矛盾,可以采用论文[2]中提出的lock-free parallelizing SGD算法。这个算法避免了更新model时对model加锁,核心思想是通过稀疏化model,使得每次迭代只需要更新model中的很少一部分分量,然后证明在lock-free方式下并发更新,收敛速度有一个不错的下限。
第二个问题是如何避免大数据量情况下打乱数据次序的开销,因为如果原始数据是有序的话,可能对model收敛速度有很大影响,但是打乱大量数据通常又要耗费大量开销。一个简单的方法是,对所有表数据做reservior sampling,这是一个经典的算法,通过一遍扫描原始数据集进行等概率抽样。然后对抽样数据打乱次序后在抽样数据上进行迭代。当然这种算法缺点也很明显,大量有效的数据点被舍弃了,对训练结果的准确性影响很大。为了避免这个缺陷,可以把数据抽样和按数据顺序迭代相结合,即如下的multiplexed reservior sampling:
如上图所示,设立两个工作线程并发更新Model,一个是I/O线程,分配好buffer A;另一个是Memory线程,分配好buffer B。
第一轮迭代,只有I/O线程工作,假设buffer A的容量为M,总记录数为N,遍历每一条记录,前M条记录直接填入buffer A。从M+1条记录开始,假设当前为第i条记录,第i条记录有M/i的概率被选中,如果被选中那么替换掉buffer A中的随机一条记录,替换出的记录被丢弃,否则直接丢弃第i条记录。这时候用被丢弃的记录更新模型,直到所有记录遍历完成。
第一轮迭代后交换buffer A和buffer B。第二轮以后的迭代都是I/O线程和Memory线程同时工作。Memory线程负责循环读取出buffer B中的数据并用来更新model,I/O线程的工作和第一轮的工作方式相同。每一轮迭代过后交换buffer使得memory线程可以用到上一轮I/O线程采样出的数据。
基于Hadoop的分布式SQL查询引擎Cloudera Impala也集成了Madlib库,当然现在还很不成熟,感兴趣的读者可以点击:
http://blog.cloudera.com/blog/2013/10/how-to-use-madlib-pre-built-analytic-functions-with-impala/
这个项目的Github地址在:
https://github.com/cloudera/madlibport
这个项目把Madlib库和Bismark计算框架移植到了Impala上,当然好处是可以利用Impala的分布式处理能力,至于性能和成熟度,目前还无法期待太多,毕竟Imapla也才刚刚在1.2的版本中加入了UDFA的编程接口,还有太多局限的地方。
相关推荐
一旦数据被导入到数据库中,我们就可以使用MadLib库来训练机器学习模型。MadLib是一个开源的机器学习库,可以在PostgreSQL和Greenplum等数据库中使用SQL语句直接训练模型。它支持多种机器学习算法,包括线性回归、...
马德利布:registered:是可扩展的数据库内分析的开源库。 它为结构化和非结构化数据提供了数学,统计和机器学习方法的数据并行实现。 安装和贡献 请访问项目网站,以获取最新二进制文件和源程序包的链接。 我们感谢...
基于postgresql+机器学习库MadLib实现的的上海地区二手房价格预测和推荐Python源码+文档说明 - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,...
在玩游戏之前, npm install在应用程序文件夹中运行npm install来安装颜色模块 用户通过输入node app.js play开始玩游戏。 用户可以通过输入以下数字从1个,2个或3个中选择3个主题。 如果用户的ipnut不正确,则...
人工智能毕业设计&课程设计
该存储库包含一组SAS MACRO,使用户可以将SAS模型发布到Greenplum,HAWQ和PostgreSQL数据库中,并具有基于MADlib SQL的高级分析和用于数据库内评分的机器学习库。 如今存在两种类型的MACRO 发布MACRO:转换SAS...
<项目介绍> 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!...
如何安装将存储库的zip添加到您的madlib.json 运行madlib install本地安装如何使用它看法MadUI中没有真正的组件概念。 取而代之的是,您具有一个可以组成的主要渲染函数,并且是State的函数。 状态可以是任何用户...
Marviq 应用程序开发库(又名 madlib)是我在 Marviq 工作时开发的。 他们很酷,让我可以使用我的个人 github 帐户而不是公司帐户发布它。 我们决定将其开源,以实现我们的互惠互利,并确保在我决定离开公司时的未来...
2、本系统主要功能:爬取链家上海地区二手房信息,使用postgresql的机器学习库MADlib,采用KNN算法对用户输入的需求信息预测房价及推荐五个相似房源。3、开发环境:centos7 64位、PostgreSQL9.5、MadLib1.13、pg...
生成器-madlib-restify-api 基于的生成器,用于基于 ...入门验证用途: : API 文档基于 Swagger: : 单元测试是用 Mocha 完成的: : 断言库是 chai: : 代码覆盖是用毯子.js 完成的: : 与 mocha cobertura 记者: ...
Madlib Creator是一个用于根据预先存在的文本语料库生成madlib句子的库。 该项目已于2015年1月在纽约先锋公司的Art Hack Day:Deluge中用作电视助手的一部分。 该库将收集文本文件的集合,并从其中创建伪狂的lib...
智能电表数据分析系统-SMAS ...分析层使用 PostgreSQL 作为数据库,MADLib (madlib.net) 作为(数据库内)机器学习库,Highcharts ( www.highcharts.com) 作为可视化引擎,Tomcat 作为 Web 应用服务器。 SMAS的架构
将存储库克隆到您具有权限的目录中。 这真的可以在任何地方。 运行startup.sh 打开Web浏览器到startup.sh指示的位置,可能是http://localhost:1031 技术领域 HTML jQuery(我很着急,可以很容易地将其删除) ...
创建一个新的回购名称,然后单击“从此模板创建存储库”。 现在,您已经从该模板创建了一个新的仓库,单击友好的绿色“代码”按钮。 单击剪贴板图标以获取您的仓库的URL。 在您的终端中, git clone your-copied-...
本文介绍了符合ISO/IEC 11172-3(MPEG 1 Audio codec Layer I, Layer II and Layer III audio specifications) 或 ISO/IEC 13818-3(BC Audio Codec)的音频编码原理。通过madlib解码库进行实现。
基于 Apache MADLib 的高级机器学习功能 Greenplum 采用 Apache 协议开源之后,加上之前的 HAWQ,PostgreSQL 以及 PostGIS,完全可以构建一体化的 PostgreSQL 企业数据架构。 Greenplum的架构采用了MPP...
Spark MLlib Spark的机器学习库 MADlib 基于SQL的数据库内置的可扩展的机器学习库 16 云平台技术 AWS S3 ⼀种对象存储服务,提供⾏业领先的可扩展性、数据可⽤性、安全性和性能 存储和保护各种⽤例数据 GCP Google...