neuralnets-2012-001 08_Lecture8 neuralnets-2012-001 08_Lecture8 01_A_brief_overview_of_Hessian_Free_optimization

WARNING:OPTIONALEXTRAMATERIAL,Thematerialinthisvideoisconsiderablymoredifficultthaninmostoftheothervideos.IhaveincludeditforthosewhowanttogetsomeideaofhowtheHFoptimizerworks.YoudonotneedtounderstandhowHFworksinordertounderstandtheremainingvideosinlecture8.Thequestionsintheweeklyquizandthefinaltestwillnotbeaboutthematerialinthisvideo,soyoucansafelyskipitifyouwant.,NeuralNetworksforMachineLearningLecture8aAbriefoverviewof“Hessian-Free”optimization,Howmuchcanwereducetheerrorbymovinginagivendirection?,Ifwechooseadirectiontomoveinandwekeepgoinginthatdirection,howmuchdoestheerrordecreasebeforeitstartsrisingagain?Weassumethecurvatureisconstant(i.e.itsaquadraticerrorsurface).Assumethemagnitudeofthegradientdecreasesaswemovedownthegradient(i.e.theerrorsurfaceisconvexupward).Themaximumerrorreductiondependsontheratioofthegradienttothecurvature.Soagooddirectiontomoveinisonewithahighratioofgradienttocurvature,evenifthegradientitselfissmall.Howcanwefinddirectionslikethese?,betterratio,Newtonsmethod,Thebasicproblemwithsteepestdescentonaquadraticerrorsurfaceisthatthegradientisnotthedirectionwewanttogoin.Iftheerrorsurfacehascircularcross-sections,thegradientisfine.Soletsapplyalineartransformationthatturnsellipsesintocircles.Newtonsmethodmultipliesthegradientvectorbytheinverseofthecurvaturematrix,H:Onarealquadraticsurfaceitjumpstotheminimuminonestep.Unfortunately,withonlyamillionweights,thecurvaturematrixhasatrilliontermsanditistotallyinfeasibletoinvertit.,CurvatureMatrices,Eachelementinthecurvaturematrixspecifieshowthegradientinonedirectionchangesaswemoveinsomeotherdirection.Theoff-diagonaltermscorrespondtotwistsintheerrorsurface.Thereasonsteepestdescentgoeswrongisthatthegradientforoneweightgetsmessedupbythesimultaneouschangestoalltheotherweights.Thecurvaturematrixdeterminesthesizesoftheseinteractions.,ijk,ijk,Howtoavoidinvertingahugematrix,Thecurvaturematrixhastoomanytermstobeofuseinabignetwork.Maybewecangetsomebenefitfromjustusingthetermsalongtheleadingdiagonal(LeCun).Butthediagonaltermsareonlyatinyfractionoftheinteractions(theyaretheself-interactions).ThecurvaturematrixcanbeapproximatedinmanydifferentwaysHessian-freemethods,LBFGS,IntheHFmethod,wemakeanapproximationtothecurvaturematrixandthen,assumingthatapproximationiscorrect,weminimizetheerrorusinganefficienttechniquecalledconjugategradient.Thenwemakeanotherapproximationtothecurvaturematrixandminimizeagain.ForRNNsitsimportanttoaddapenaltyforchanginganyofthehiddenactivitiestoomuch.,Conjugategradient,Thereisanalternativetogoingtotheminimuminonestepbymultiplyingbytheinverseofthecurvaturematrix.Useasequenceofstepseachofwhichfindstheminimumalongonedirection.Makesurethateachnewdirectionis“conjugate”tothepreviousdirectionssoyoudonotmessuptheminimizationyoualreadydid.“conjugate”meansthatasyougointhenewdirection,youdonotchangethegradientsinthepreviousdirections.,Apictureofconjugategradient,Thegradientinthedirectionofthefirststepiszeroatallpointsonthegreenline.Soifwemovealongthegreenlinewedontmessuptheminimizationwealreadydidinthefirstdirection.,Whatdoesconjugategradientachieve?,AfterNsteps,conjugategradientisguaranteedtofindtheminimumofanN-dimensionalquadraticsurface.Why?AftermanylessthanNstepsithastypicallygottheerrorveryclosetotheminimumvalue.Conjugategradientcanbeapplieddirectlytoanon-quadraticerrorsurfaceanditusuallyworksquitewell(non-linearconjugategrad.)TheHFoptimizerusesconjugategradientforminimizationonagenuinelyquadraticsurfacewhereitexcels.Thegenuinelyquadraticsurfaceisthequadraticapproximationtothetruesurface.,NeuralNetworksforMachineLearningLecture8bModelingcharacterstringswithmultiplicativeconnections,Modelingtext:Advantagesofworkingwithcharacters,Thewebiscomposedofcharacterstrings.Anylearningmethodpowerfulenoughtounderstandtheworldbyreadingtheweboughttofindittrivialtolearnwhichstringsmakewords(thisturnsouttobetrue,asweshallsee).Pre-processingtexttogetwordsisabighassleWhataboutmorphemes(prefixes,suffixesetc)Whataboutsubtleeffectslike“sn”words?WhataboutNewYork?WhataboutFinnishymmartamattomyydellansakaan,.,.,.,.,.,.,.,.,Anobviousrecurrentneuralnet,1500hiddenunits,character:1-of-86,1500hiddenunits,c,predicteddistributionfornextcharacter.,Itsaloteasiertopredict86charactersthan100,000words.,softmax,Asub-treeinthetreeofallcharacterstrings,IfthenodesareimplementedashiddenstatesinanRNN,differentnodescansharestructurebecausetheyusedistributedrepresentations.Thenexthiddenrepresentationneedstodependontheconjunctionofthecurrentcharacterandthecurrenthiddenrepresentation.,.fix,fixi,fixin,i,e,n,InanRNN,eachnodeisahiddenstatevector.Thenextcharactermusttransformthistoanewnode.,fixe,ThereareexponentiallymanynodesinthetreeofallcharacterstringsoflengthN.,Multiplicativeconnections,Insteadofusingtheinputstotherecurrentnettoprovideadditiveextrainputtothehiddenunits,wecouldusethecurrentinputcharactertochoosethewholehidden-to-hiddenweightmatrix.Butthisrequires86x1500 x1500parametersThiscouldmakethenetoverfit.Canweachievethesamekindofmultiplicativeinteractionusingfewerparameters?Wewantadifferenttransitionmatrixforeachofthe86characters,butwewantthese86character-specificweightmatricestoshareparameters(thecharacters9and8shouldhavesimilarmatrices).,Usingfactorstoimplementmultiplicativeinteractions,Wecangetgroupsaandbtointeractmultiplicativelybyusing“factors”.Eachfactorfirstcomputesaweightedsumforeachofitsinputgroups.Thenitsendstheproductoftheweightedsumstoitsoutputgroup.,vectorofinputstogroupc,scalarinputtoffromgroupb,scalarinputtoffromgroupa,Groupb,Groupa,Groupc,Usingfactorstoimplementasetofbasismatrices,Wecanthinkaboutfactorsanotherway:Eachfactordefinesarank1transitionmatrixfromatoc.,scalarcoefficient,outerproducttransitionmatrixwithrank1,Groupb,Groupa,Groupc,1500hiddenunits,character:1-of-86,Using3-wayfactorstoallowacharactertocreateawholetransitionmatrix,predicteddistributionfornextcharacter,1500hiddenunits,Eachfactor,f,definesarankonematrix,Eachcharacter,k,determinesagainforeachofthesematrices.,k,NeuralNetworksforMachineLearningLecture8cLearningtopredictthenextcharacterusingHF,Trainingthecharactermodel,IlyaSutskeverused5millionstringsof100characterstakenfromwikipedia.Foreachstringhestartspredictingatthe11thcharacter.UsingtheHFoptimizer,ittookamonthonaGPUboardtogetareallygoodmodel.IlyascurrentbestRNNisprobablythebestsinglemodelforcharacterprediction(combinationsofmanymodelsdobetter).Itworksinaverydifferentwayfromthebestothermodels.Itcanbalancequotesandbracketsoverlongdistances.Modelsthatrelyonmatchingpreviouscontextscannotdothis.,Howtogeneratecharacterstringsfromthemodel,Startthemodelwithitsdefaulthiddenstate.Giveita“burn-in”sequenceofcharactersandletitupdateitshiddenstateaftereachcharacter.Thenlookattheprobabilitydistributionitpredictsforthenextcharacter.Pickacharacterrandomlyfromthatdistributionandtellthenetthatthiswasthecharacterthatactuallyoccurred.i.e.tellitthatitsguesswascorrect,whateveritguessed.Continuetoletitpickcharactersuntilbored.Lookatthecharacterstringsitproducestoseewhatit“knows”.,HewaselectedPresidentduringtheRevolutionaryWarandforgaveOpusPaulatRome.TheregimeofhiscrewofEngland,isnowArabwomensiconsinandthedemonsthatusesomethingbetweenthecharacterssistersinlowercoiltrainswerealwaysoperatedonthelineoftheephemerablestreet,respectively,thegraphicorotherfacilityfordeformationofagivenproportionoflargesegmentsatRTUS).TheBeverychordwasastronglycoldinternalpalettepoureventhewhiteblade.”,Somecompletionsproducedbythemodel,Sheilathrunges(mostfrequent)Peoplethrunge(mostfrequentnextcharacterisspace)Shiela,ThrungelinidelRey(firsttry)Themeaningoflifeisliteraryrecognition.(6thtry)Themeaningoflifeisthetraditionoftheancienthumanreproduction:itislessfavorabletothegoodboyforwhentoremoveherbigger.(oneofthefirst10triesforamodeltrainedforlonger).,Whatdoesitknow?,Itknowsahugenumberofwordsandalotaboutpropernames,dates,andnumbers.Itisgoodatbalancingquotesandbrackets.Itcancountbrackets:none,one,manyItknowsalotaboutsyntaxbutitsveryhardtopindownexactlywhatformthisknowledgehas.Itssyntacticknowledgeisnotmodular.ItknowsalotofweaksemanticassociationsE.g.itknowsPlatoisassociatedwithWittgensteinandcabbageisassociatedwithvegetable.,RNNsforpredictingthenextword,TomasMikolovandhiscollaboratorshaverecentlytrainedquitelargeRNNsonquitelargetrainingsetsusingBPTT.Theydobetterthanfeed-forwardneuralnets.Theydobetterthanthebestothermodels.Theydoevenbetterwhenaveragedwithothermodels.RNNsrequiremuchlesstrainingdatatoreachthesamelevelofperformanceasothermodels.RNNsimprovefasterthanothermethodsasthedatasetgetsbigger.Thisisgoingtomakethemveryhardtobeat.,NeuralNetworksforMachineLearningLecture8dEchostatenetworks,Thekeyideaofechostatenetworks(perceptronsagain?),Averysimplewaytolearnafeedforwardnetworkistomaketheearlylayersrandomandfixed.Thenwejustlearnthelastlayerwhichisalinearmodelthatusesthetransformedinputstopredictthetargetoutputs.Abigrandomexpansionoftheinputvectorcanhelp.,TheequivalentideaforRNNsistofixtheinputhiddenconnectionsandthehiddenhiddenconnectionsatrandomvaluesandonlylearnthehiddenoutputconnections.Thelearningisthenverysimple(assuminglinearoutputunits).ItsimportanttosettherandomconnectionsverycarefullysotheRNNdoesnotexplodeordie.,SettingtherandomconnectionsinanEchoStateNetwork,Setthehiddenhiddenweightssothatthelengthoftheactivityvectorstaysaboutthesameaftereachiteration.Thisallowstheinputtoechoaroundthenetworkforalongtime.Usesparseconnectivity(i.e.setmostoftheweightstozero).Thiscreateslotsoflooselycoupledoscillators.,Choosethescaleoftheinputhiddenconnectionsverycarefully.Theyneedtodrivethelooselycoupledoscilla