文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Jerusalem
侵权投诉

Jerusalem

We introduce an efficient parallel implementation of a Kernel Ridge Regression solver, based on the Gaussian Belief Propagation algorithm (GaBP). Our approach can be easily used in Peer-to-Peer and grid environments, where there is no central authority tha

ALarge-ScaleGaussianBeliefPropagationSolverfor

KernelRidgeRegression

SchoolofEngineeringand

ComputerScienceTheHebrewUniversityof

Jerusalem

DannyBickson

IBMHaifaResearchLabHaifaUniversityCampusHaifa31905,Israel

EladYom-Tov

yomtov@il.ibm.com

SchoolofEngineeringand

ComputerScienceTheHebrewUniversityof

Jerusalem

DannyDolev

GivatRam,Jerusalem91904,

Israel

danny.bickson@gmail.com

ABSTRACT

Weintroduceanef cientparallelimplementationofaKernelRidgeRegressionsolver,basedontheGaussianBeliefPropagationalgo-rithm(GaBP).OurapproachcanbeeasilyusedinPeer-to-Peerandgridenvironments,wherethereisnocentralauthoritythatallocateswork.Empirically,oursolverhashighaccuracyinsolvingclassi -cationproblems.Wehavetestedourdistributedimplementationonlargescaledatasetsusingupto1,024CPUsofanIBMBlueGenesupercomputer.

1.KERNELRIDGEREGRESSION

KernelRidgeRegression(KRR)implementsaregularizedformoftheleastsquaresmethodusefulforbothregressionandclassi -cation.Thenon-linearversionofKRRissimilartotheSupport-VectorMachine(SVM)problem.However,inthelatter,specialemphasisisgiventopointsclosetothedecisionboundary,whichisnotprovidedbythecostfunctionusedbyKRR.Giventrainingdata

D={xi,yi}li=1,xi∈Rd

,yi∈R

theKRRalgorithmdeterminestheparametervectorw∈Rdofanon-linearmodel(usingthe“kerneltrick”),viaminimizationofthefollowingobjectivefunction:[2]:

minλ||w||2

+

l(yi wTΦ(xi))2

i=1

whereλisatradeoffparameterbetweenthetwotermsofthetimizationfunction,andΦ(˙op-)

isa(possiblenon-linear)mappingofthetrainingpatterns.

Onecanshowthatthedualformofthisoptimizationproblemisgivenby:

maxW(α)=yT

a+1/4λαT

Kα 1/4αT

α

(1)

whereKisamatrixwhose(i,j)-thentryisthekernelfunctionKi,j=Φ(xi)TΦ(xj).

Theoptimalsolutiontothisoptimizationproblemis:

α=2λ(K+λI)

1

y

GivatRam,Jerusalem91904,

Israel

dolev@cs.huji.ac.il

Thecorrespondingpredictionfunctionisgivenby:

f(x)=wTΦ(x)=yT(K+λI) 1K(xi,x).

2.SOLVINGAKRRPROBLEMUSINGGABP

Thecontributionsofthispaperaretwofold:First,weutilizeGaus-sianBeliefpropagation,anef cientdistributedalgorithmthathas

beenshowntoconvergeempiricallyfaster[6]thanothermethodsproposedintheliteratureforsolvingthiskindofproblem.ThesemethodsarethoseusedforsolvingGaussianProcesses(forare-viewsee[8])andincludeblockGauss-Seidel,ConjugateGradient,andothers.Additionally,wepresentaverylargescaleimplantation(testedupto1,024computingnodes)oftheparallelGaBPsolveranddemonstrateitsapplicabilityforsolvingsupportvectorregres-sionandclassi cationproblems.

TheGaBPalgorithmisaspecialcaseofthesum-productalgorithmwhentheunderlyingdistributionisGaussian.Ouraimisto ndα,asolutiontothequadraticcostfunction1.AsthekernelmatrixKissymmetricwecande neajointlyGaussianprobabilityp(α)=exp(W(α))andinfermaxp(α)whichisanoptimalsolutionfortheKRRproblem.

Theformulationaboveallowsustoshifttheratingproblemfromanalgebraictoaprobabilisticdomain.Insteadofsolvingadeter-ministicvector-matrixlinearequation,wenowsolveaninferenceprobleminagraphicalmodeldescribingacertainGaussiandistri-butionfunction.Themovetotheprobabilisticdomaincallsfortheutilizationofbeliefpropagationasanef cientinferenceengine.In[6]wedemonstratedhowtoderivetheGaBPupdaterulesbysubstitutingGaussiandistributionsinthecontinuousBPequations.Theoutputofthisderivationareupdaterulesthatarecomputedlocallybyeachnode,thusallowinganef cientdistributedimple-mentation.

3.

CONVERGENCEOFTHEGABPALGO-RITHM

Asuf cientconditionfortheconvergenceoftheGaBPalgorithm[1],isforthematrixJ=(K+λI)tobediagonallydominant:

iJii>Σk=i|Jik|

UndertheseconditionstheGaBPalgorithmconvergestotherightmeanandapproximatedvariance.

第1页

你可能喜欢

热门文档

相关文档

  • 浅析耶路撒冷的历史与反思

    【关键词】 :以巴冲突 宗教 民族问题 边界之争 耶路撒冷(Jerusalem)这个名称,根据传统的说法,是取自两个希伯来文"ir"--意思 是城市和"shalom"--意思是和平,...

  • Jerusalem(耶路撒冷)

    Jerusalem(耶路撒冷)Jerusalem(耶路撒冷)隐藏>> Write down the happiest thing in your life Share with your classmates The Secret to Happiness A young man ...

  • 耶路撒冷为什么是圣城

    伊斯兰教说, 这是穆罕默德夜游登宵聆听真主安拉祝福和启示的圣城, 有世界上最美丽的 清真寺 耶路撒冷(Jerusalem)这个名称,根据传统的说法,是取自两个希伯来文"ir"...

  • 耶路撒冷

    利纳·莫 holy land ---jerusalem Jerusalem is a holy city to the three major Abrahamic religions— Judaism, Christianity and Islam 圣城耶路撒冷(Jerusalem)...

  • 耶路撒冷之旅

    圣城—— 耶路撒冷 Jerusalem 旅游计划 ? 和平之城—耶路撒冷 ? 交通出行 ? 精致两日游 ? 美食与住宿 ? 温馨Tips ? 经费预算 ? 旅游心得 和平之城—耶路撒冷 ?...

  • 耶路撒冷

    耶路撒冷(英语:Jerusalem;希伯来语: 、拉丁化:Yelushalayim 或 Yelushalaim;阿拉伯文: 、拉丁化: al-Quds、汉化:古德斯,或☆渀恋猀瀀;、拉丁化:Bayt-al-Muq...

  • 5-19New Jerusalem新耶路撒冷

    5-19New Jerusalem新耶路撒冷_文化/宗教_人文社科_专业资料。中英72题基督常见问题VI-51 NEW JERUSALEM Scripture Reading: Hymn: 978 Rev. 21:2 And I saw ...

  • 免费飞机设计:Jerusalem十字架型FSS的仿真设计

    30 No. 1 Feb 2010 文章编号:1673- 4599 (2010 01- 0055- 05 ) Jerusalem 十字架型 FSS 的仿真设计安兆卫 1,王明皓 2,赵平 3,洪铁山 2,李清波 2 ...

  • 耶路撒冷旧城及其城墙

    耶路撒冷市 (Jerusalem) 位于巴勒斯坦中部犹地亚山的四座山 丘上,是一座举世闻名的历史古城,距今已有5000多年的 历史。自三千年前大卫王的王国建都于此以来,取名...

  • 耶路撒冷

    JERUSALEM The holy city---Jerusalem is well known to the world, because it is one of the oldest city in the world. The reason why we call it the...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email