ONLINELEARNINGALGORITHMSFORMININGTRAJECTORYDATAAND THEIRAPPLICATIONS By DingWang ADISSERTATION Submittedto MichiganStateUniversity inpartialful˝llmentoftherequirements forthedegreeof ComputerScienceDoctorofPhilosophy 2021 ABSTRACT ONLINELEARNINGALGORITHMSFORMININGTRAJECTORYDATAAND THEIRAPPLICATIONS By DingWang Trajectoriesarespatio-temporaldatathatrepresenttracesofmovingobjects,suchas humans,migratinganimals,vehicles,andtropicalcyclones.Inadditiontothegeo-location information,atrajectorydataoftencontainother(non-spatial)featuresdescribingthestates ofthemovingobjects.Thetime-varyinggeo-locationandstateinformationwouldcollec- tivelycharacterizeatrajectorydataset,whichcanbeharnessedtounderstandthedynamics ofthemovingobjects.Thisthesisfocusesonthedevelopmentofe˚cientandaccuratema- chinelearningalgorithmsforforecastingthefuturetrajectorypathandstateofamoving object.Althoughmanymethodshavebeendevelopedinrecentyears,therearestillnumer- ouschallengesthathavenotbeensu˚cientlyaddressedbyexistingmethods,whichhamper theire˙ectivenesswhenappliedtocriticalapplicationssuchashurricaneprediction.These challengesincludetheirdi˚cultiesintermsofhandlingconceptdrifts,errorpropagationin long-termforecasts,missingvalues,andnonlinearitiesinthedata. Inthisthesis,Ipresentafamilyofonlinelearningalgorithmstoaddressthesechallenges. Onlinelearningisane˙ectiveapproachasitcane˚ciently˝tnewobservationswhileadapt- ingtoconceptdriftspresentinthedata.First,Iproposedanonlinelearningframework called OMuLeT forlong-termforecastingofthetrajectorypathsofmovingobjects. OMuLeT employsanonlinelearningwithrestartstrategytoincrementallyupdatetheweightsofits predictivemodelasnewobservationdatabecomeavailable.Itcanalsohandlemissingvalues inthedatausinganovelweightrenormalizationstrategy. Second,Iintroducedthe OOR frameworktopredictthefuturestateofthemovingobject. Sincethestatecanberepresentedbyordinalvalues, OOR employsanovelordinallossfunction totrainitsmodel.Inaddition,theframeworkwasextendedto OOQR toaccommodatea quantilelossfunctiontoimproveitspredictionaccuracyforlargervaluesontheordinal scale.Furthermore,Ialsodevelopedthe OOR- and OOQR- frameworkstogeneratereal- valuedstatepredictionsusingthe insensitivitylossfunction. Third,Idevelopedanonlinelearningframeworkcalled JOHAN ,thatsimultaneouslypre- dictsthelocationandstateofthemovingobject. JOHAN generatesitspredictionsbyleverag- ingtherelationshipbetweenthestateandlocationinformation. JOHAN utilizesaquantileloss functiontobiasthealgorithmtowardspredictingmoreaccuratelylargecategoricalvaluesin termsofthestateofthemovingobject,say,forahighintensityhurricane. Finally,Ipresentadeeplearningframeworktocapturenon-linearrelationshipsintra- jectorydata.Theproposed DTP frameworkemploysaTDMapproachforimputingmissing values,coupledwithanLSTMarchitecturefordynamicpathprediction.Inaddition,the frameworkwasextendedto ODTP ,whichappliedanonlinelearningsettingtoaddressconcept driftspresentinthetrajectorydata. Asproofofconcept,theproposedalgorithmswereappliedtothehurricaneprediction task.Both OMuLeT and ODTP wereusedtopredictthefuturetrajectorypathofahurricane upto48hoursleadtime.Experimentalresultsshowedthat OMuLeT and ODTP outperformed variousbaselinemethods,includingtheo˚cialforecastsproducedbytheU.S.National HurricaneCenter. OOR wasappliedtopredicttheintensityofahurricaneupto48hours inadvance.Experimentalresultsshowedthat OOR outperformedvariousstate-of-the-art onlinelearningmethodsandcangeneratepredictionsclosetotheNHCo˚cialforecasts. Sincehurricaneintensitypredictionisanotoriouslyhardproblem, JOHAN wasappliedto improveitspredictionaccuracybyleveragingthetrajectoryinformation,particularlyfor highintensityhurricanesthatarenearlandfall. Copyrightby DINGWANG 2021 ACKNOWLEDGEMENTS PursuingaPhDisafantasticjourneyinmylife.Duringthislongjourney,Imetwonderful peopleandhavemanywonderfulmemories.Iwouldliketosincerelyacknowledgethem fortheirsupportandhelpduringmyPhDstudy.Thisjourneyhasgreatlyexpandedmy knowledgeandwillcontinuetoin˛uencemycareerlife. Firstandforemost,Iwouldliketothankmyadvisor,Dr.Pang-NingTanforthecontin- uoussupportofmyPhDstudyandresearch.Igotmyundergraduateandmasterdegrees inphysics,butIalwayshaveastronginterestincomputerscience.ThankstoDr.Tanfor givingmetheopportunitytojointhe˝eldofcomputerscience.Heisaveryknowledgeable, patientandresponsiblementor,andheiswillingtospendtimecommunicatingwithstudents anddiscussingtheirresearches.Underhisguidance,Ihavelearnedhowtoconductresearch correctlyandhowtoidentifyandsolveproblemsencounteredinresearch.Theseknowledge willbethegreatwealthIhaveinmylife.ItismyhonortoworkwithDr.Tan,andIwill alwaysrememberhisguidance. Second,IwouldliketothankmyPhDcommitteemembers,Dr.Abdol-HosseinEsfa- hanian,Dr.JiayuZhouandDr.PouyanNejadhashemifortheirsupportandguidance throughoutmyPhDprogram.IhadtakenthecourseAlgorithmicGraphTheoryfromDr. EsfahanianandcourseIntroductiontoMachineLearningfromDr.Zhou.Theyareallvery interestingandusefulcourses.Ilearnedalotfromthesecoursesandappliedtheknowledge tomyresearch.Dr.Pouyanprovidedmewithmanysuggestionsongeographicalperspec- tives.Thisisveryhelpfulformyresearch,becausemyresearchfocusesontheapplication ofonlinealgorithmsinhurricaneforecasting.Iamveryhappytoworkwitheveryoneonmy committee,andIamverygratefulfortheirsupportandhelpinmyresearch. Furthermore,Iwouldliketothankallmycurrentandpreviouscolleagues,especially, BoyangLiu,JianpengXu,XiLiu,ShuaiYuan,QiaoziGao,ShaohuaYang,FarzanMasrour, TylerWilson,CourtlandVanDamandZubinAbraham.Wenotonlyhelpeachotherin v research,butarealsogoodfriendsinlife. Inaddition,thisthesisispartiallysupportedbytheNationalScienceFoundationunder grant#IIS-1615612.IwouldalsoliketothanktheDepartmentofComputerScienceand Engineeringforprovidingmewithfellowshipsduringmythesiswriting. Lastbutnotleast,Iwanttothankmyparentsandwifefortheirencouragement,support andunconditionallovetome.Withouttheirsupport,Iwouldnotbeabletoaccomplishmy PhDdegree. vi TABLEOFCONTENTS LISTOFTABLES ................................... x LISTOFFIGURES ................................... xii LISTOFALGORITHMS ................................ xvi CHAPTER1INTRODUCTION ........................... 1 1.1TrajectoryDataset................................1 1.2TrajectoryDataMining.............................2 1.3ApplicationtoHurricanePrediction.......................3 1.4ResearchChallenges...............................4 1.5ThesisStatement.................................6 1.6ThesisContributions...............................6 1.7Publications....................................8 1.8ThesisOrganization................................9 CHAPTER2LITERATUREREVIEW ........................ 11 2.1TrajectoryDataPreprocessing..........................11 2.1.1DataCleaning...............................12 2.1.2TrajectoryCompression.........................12 2.1.3MapMatching..............................13 2.1.4TrajectorySegmentation.........................13 2.2TrajectoryDataMiningAlgorithms.......................14 2.2.1TrajectoryClustering...........................14 2.2.1.1ClusteringTrajectories.....................14 2.2.1.2ClusteringTrajectorySegmentsorPoints..........15 2.2.2TrajectoryClassi˝cation.........................15 2.2.3TrajectoryPatternMining........................16 2.2.3.1PeriodicPatternMining....................16 2.2.3.2SequentialPatternMining...................16 2.2.3.3GroupPatternMining.....................17 2.2.4TrajectoryPrediction...........................19 2.2.5TrajectoryOutlierDetection.......................20 2.3TrajectoryDataMiningApplications......................20 CHAPTER3ONLINEMULTI-LEADTIMETRAJECTORYLOCATIONPRE- DICTION ................................ 23 3.1RelatedWork...................................26 3.2ProblemFormulation...............................27 3.3Methodology...................................29 3.3.1WeightRenormalization.........................30 3.3.2GeographicDistanceLossFunction...................34 vii 3.3.3 OMuLeT Framework............................35 3.3.3.1ObjectiveFunction.......................37 3.3.3.2ComputationalComplexity..................41 3.4ExperimentalEvaluation.............................42 3.4.1PerformanceComparison.........................44 3.4.2SensitivityAnalysis............................49 3.5Conclusions....................................49 CHAPTER4ONLINEMULTI-LEADTIMETRAJECTORYSTATEPREDIC- TIONWITHORDINALDATA .................... 50 4.1RelatedWork...................................53 4.2ProblemStatement................................53 4.3Methodology...................................55 4.3.1 OOR Framework..............................55 4.3.2 OOQR Framework.............................58 4.3.3 OOR- Framework.............................59 4.3.4 OOQR- Framework............................62 4.4Experiments....................................63 4.4.1BaselineandEvaluationMetrics.....................63 4.4.2ExperimentalResultsfor OOR / OOQR ...................64 4.4.2.1PerformanceComparison...................64 4.4.2.2CaseStudy...........................68 4.4.3ExperimentalResultsfor OOR- / OOQR- .................70 4.4.3.1PerformanceComparison...................70 4.4.4AblationStudy..............................75 4.4.4.1CaseStudy...........................76 4.5Conclusions....................................78 CHAPTER5ONLINEJOINTPREDICTIONOFTRAJECTORYLOCATION ANDSTATE .............................. 79 5.1RelatedWorks...................................82 5.2ProblemStatement................................84 5.3Methodology...................................85 5.3.1 JOHAN Framework.............................86 5.3.1.1 L tra withDistanceQuantileRegression............87 5.3.1.2 L int withQuantileOrdinalRegression............89 5.3.1.3QuantileHyperparameterUpdate...............92 5.4Experiments....................................93 5.4.1BaselineandEvaluationMetrics.....................95 5.4.2ExperimentalResults...........................97 5.4.3AblationStudy..............................99 5.4.4ComparisonofModelWeights......................100 5.4.5CaseStudy................................102 5.5Conclusions....................................102 viii CHAPTER6LSTMFORTRAJECTORYLOCATIONPREDICTION ....... 103 6.1RelatedWorks...................................104 6.2ProblemFormulation...............................105 6.3Methodology...................................106 6.3.1 DTP Framework..............................106 6.3.1.1TemporalDecayMemory...................107 6.3.1.2ModelPerformanceLayer...................109 6.3.1.3PredictionLayer........................110 6.3.2 ODTP Framework.............................110 6.4Experiments....................................112 6.4.1BaselineandEvaluationMetrics.....................113 6.4.2PerformanceComparison.........................114 6.4.2.1CaseStudy...........................115 6.4.2.2AnalysisoftheModelPerformanceLayer..........117 6.5Conclusions....................................118 CHAPTER7CONCLUSIONSANDFUTUREWORKS ............... 119 7.1SummaryofThesisContributions........................119 7.2FutureWorks...................................121 BIBLIOGRAPHY .................................... 122 ix LISTOFTABLES Table3.1:ExampleofNHCbesttrackhurricanetrajectorydataalongwiththe forecastsgeneratedbyanensembleofdynamicalmodelssuchasAEMI, AEMN,andCLP5forHurricanesSandyandIrmaatdi˙erentleadtimes. N/Adenotesmissingvalues..........................25 Table3.2:Summaryofnotations.............................41 Table3.3:Comparisonofmeangeographicdistanceerror(inmiles)forvarioushur- ricanetrajectoryforecastingmethods.....................45 Table3.4:Comparisonofmeangeographicdistanceerror(inmiles)forvarioushur- ricanetrajectoryforecastingmethods.....................45 Table4.1:Sa˚r-Simpsonhurricanewindscale(SSHWS),for1-minutemaximum sustainedwinds.................................50 Table4.2:ComparisonofMAEforvarioushurricanecategoryforecastingmethods atdi˙erentleadtimes..............................65 Table4.3:ComparisonofF1-scoreforvarioushurricanecategoryforecastingindif- ferentcategories.................................65 Table4.4:Comparisonofprecision,recall,andF1-scorefor OOQR withdi˙erent hyperparameter ˘ ................................68 Table4.5:ComparisonoftheintensityandcategoryMAEforvarioushurricane intensityforecastingmethodsatdi˙erentleadtimes.............71 Table4.6:ComparisonofF1-score,precisionandrecallforvarioushurricaneinten- sityforecastingmethodsatdi˙erentcategories................72 Table4.7:ComparisonofF1-score,precision,andrecallfor OOQR- withdi˙erent valuesof ˘ ....................................73 Table4.8:ComparisonofintensityandcategoryMAEfor OOR- variationsatdif- ferentleadtimes.................................76 Table4.9:ComparisonofF1-score,precisionandrecallfor OOR- variationsatdif- ferentcategories.................................76 Table5.1:Literaturereviewofrecentworksontropicalcycloneprediction......80 x Table5.2:Trajectoryandintensityforecasterrorsfordi˙erentmethodsatvarying leadtimesfrom12to48hours........................98 Table5.3:Trajectoryandintensityforecasterrorsforhurricaneswithin200nmi tocoastlinewithintensityatleast64ktfordi˙erentmethodsatvarying leadtimesfrom12to48hours........................98 Table5.4:ComparisonofF1-score,precisionandrecallforvarioushurricaneinten- sityforecastingmethodsatdi˙erentcategories................99 Table5.5:ComparisonofF1-score,precisionandrecallforhurricaneswithin200n mitocoastlinewithvarioushurricaneintensityforecastingmethodsat di˙erentcategories...............................99 Table5.6:Trajectoryandintensityforecasterrorsfordi˙erentvariationsof JOHAN ..100 Table5.7:Trajectoryandintensityforecasterrorsforhurricaneswithin200nmi tocoastlineandatleast64ktusingdi˙erentvariationsof JOHAN .....100 Table6.1:Trajectoryandintensityforecasterrorsfordi˙erentmethodsatvarying leadtimesfrom12to48hours.........................114 xi LISTOFFIGURES Figure1.1:Exampleofatrajectory.Bluelineisthetraceofamovingobject.Blue dotsarethesamplepoints...........................1 Figure1.2:Generalframeworkoftrajectorydatamining................3 Figure2.1:Generalframeworkoftrajectorydatamining................11 Figure2.2:ThetrajectoriesA,B,CsharedacommonsequenceastrajectoryD withsimilartimeinterval...........................17 Figure2.3:TrajectoryAconsidersonlyspatialproperty;trajectoryBconsidersonly temporalproperty;whiletrajectoryCconsidersbothspatio-temporal properties....................................17 Figure2.4:Exampleofasequentialgrouppatterns:(a)˛ock,(b)convoy,(c)swarm..18 Figure2.5:TrackerrorsofNHCo˚cialforecastsfromyear1990to2019[12].Figure (a)showstheerrorsatAtlanticbasin.Figure(b)showstheerrorsat EasternNorthPaci˝cbasin..........................21 Figure3.1:Hurricanetrackforthefollowing48hourspredictedbyanensembleof dynamicalmodelsforHurricaneIrmaonSeptember10,2017.Thegreen linesrepresentthevariousforecastsproducedbytheensemblemembers whereastheblackdashlinecorrespondstotheensemblemean.Thered linecorrespondstothebesttrackaccordingtotheNationalHurricane Center......................................24 Figure3.2:Anillustrationofthepartiallyobservedlabeleddataproblem.Thered rectanglesdenotethesetofmodelforecastsforwhichgroundtruthare availableattime t ...............................30 Figure3.3:Normalizeddistributionoftrajectoryforecasterrors(in50milesbin)for 5di˙erentdynamicalmodelsalongtheirlatitudeandlongitudedirections.32 Figure3.4:Proposedonlinemulti-leadtimetrajectoryforecastingframework.....36 Figure3.5:Comparisonof48-hourforecastsforHurricaneIrmafrom2017/09/08 to2017/09/10bydi˙erentmethods.....................46 Figure3.6:Percentageofforecastimprovementof OMuLeT comparedtothebaseline methods.....................................46 xii Figure3.7:Globalweightchangesovertime.......................47 Figure3.8:The48hourforecasterroroveryear2012to2018..............47 Figure3.9:E˙ectofvaryingthehyperparameters ˆ;;!;; onmeanforecast error(ME)...................................48 Figure4.1:Hurricanecategorydistributionfromyear2012to2020...........51 Figure4.2:Availabilityofensemblemodelforecastdata.Thedarkcellsdenotethe timestepsinwhichthemodelforecastsareavailablewhilethewhite cellsdenoteotherwise.............................55 Figure4.3: OOR / OOR- frameworkwithbacktrackingandrestart............57 Figure4.4:Comparisonoftheconfusionmatricesforhurricanecategorypredictions frommultiplebaselinealgorithms.......................66 Figure4.5:Weightforthemodellearnedfrom OOR overhurricanesfromyear2012 to2020.....................................67 Figure4.6:The˝gureshowsthepredictiondi˙erencefor OOQR frameworkwithdif- ferenthyperparameter ˘ .Theresultsconsideredthe48-hourforecasts generatedby OOQR frameworkforthehurricanesfromyear2012toyear 2020.......................................69 Figure4.7:Comparisonoftheconfusionmatricesforhurricanecategorypredictions frommultiplebaselinealgorithms.......................69 Figure4.8:Comparisonof48-hourforecastsforHurricaneDorianfrom2019/08/28 to2019/08/29bydi˙erentmethods.Theerrorbarsrepresenttherange ofcategoryforecastsfromensemblemembers................70 Figure4.9:48-hourforecastdistributionof OOQR- fordi˙erent ˘ ............74 Figure4.10:ComparisonofQQplotfor48-hourforecastswithdi˙erentmethods...74 Figure4.11:ComparisonofQQplotfor OOR- and OOQR- ................75 Figure4.12:6to48hourforecastsofHurricaneDorianfromAugust28to29,2019. Theerrorbarsrepresenttherangeofintensitypredictionsfromthe ensemblemembers...............................77 xiii Figure5.1:ErrorsofNHCo˚cialforecastsatAtlanticbasinbasinfromyear1990 to2019[12].Figure(a)showsthetrackerror.Figure(b)showsthe intensityerror.................................80 Figure5.2:Heatmapshowingtherelationshipbetweenhurricaneintensityandits distancetonearestU.S.coastline.Negativedistanceindicatethatthe hurricanehasmadelandfall..........................82 Figure5.3:Decompositionofthedistancelossvector.Thegreencircleisthetrue locationandtheredstarisitsprojectednearestcoastline.Theunit vector n pointsinthedirectiontowardstheland.Thebluecircleis thepredictedlocation.Thevectordirectedfromthegreencircletothe bluecircleisthedistancelossvector d ,whichcanbedecomposedinto aparallel d k andaperpendicularcomponent d ? ..............88 Figure5.4:Proposed JOHAN framework..........................93 Figure5.5:Distancetocoastlineforhurricanesfromyear2012to2017atdi˙erent timebeforelandfall..............................96 Figure5.6:Trajectoryandintensitymodelweightsin JOHAN changesovertime....101 Figure5.7:6to48hourforecastsofHurricaneIrmafromSep.4thtoSep.5th, 2017.Figure(a)to(d)showsthemulti-leadtimetrajectoryforecasts generatedfromdi˙erentmethods.Figure(e)to(h)demonstratethe multi-leadtimeintensitypredictionsfromdi˙erentmethods.Theerror barsrepresenttherangeofintensitypredictionsfromtheensemblemembers.101 Figure6.1:The˝gureillustratethe DTP framework.Figure(a)showsmodelper- formancelayer.Figure(b)showspredictionlayer..............107 Figure6.2:TemporalDecayMemoryfordataimputation................108 Figure6.3:The˝gureillustratethe ODTP framework.Figure(a)showsmodelper- formancelayer.Figure(b)showspredictionlayer..............111 Figure6.4:The ODTP frameworkusingbacktrackingandrestartstrategy........112 Figure6.5:Comparisonof48-hourforecastsforHurricaneIrmafrom2017/09/08 to2017/09/09bydi˙erentmethods.....................115 Figure6.6:Comparisonof48-hourforecastsforHurricaneIrmafrom2017/09/08 to2017/09/09bydi˙erentmethods.....................116 xiv Figure6.7:Meanresidualdistanceerror e t ˝;m;˝ vs.mean t;m ˝ ofallthetimesteps withinonehurricaneforphysicalmodelAVNO.Thecorrelationsscores are-0.7294,-0.5489,-0.3457,-0.2133for12-hour,24-hour,36-hour,48- hourleadtimeforecasts,respectively.....................117 xv LISTOFALGORITHMS Algorithm1:Proposed OMuLeT framework...................... 41 Algorithm2:Proposed OOR / OOQR / OOR- / OOQR- framework............. 57 Algorithm3:Proposed JOHAN framework....................... 94 Algorithm4:Proposed ODTP framework....................... 112 xvi CHAPTER1 INTRODUCTION TrajectorycomesfrommodernLatinword trajectorium ,whichmeansthe"pathdescribed byabodymovingunderthein˛uenceofgivenforces" 1 .Althoughthepathofamoving objectiscontinuousandcontainsin˝nitenumberofpositionsandtimepoints,trajectory datasetstypicallycontainonlyasubsetofthesepositionsmeasuredatdiscretetimepoints. 1.1TrajectoryDataset Thetrajectoryofamovingobjectischaracterizedbyitsspatialandtemporalproperties. Thespatialpropertycorrespondstoitslocationandistypicallydenotedbya2-dimensional (or3-dimensional)vector,e.g., x =( x i ;y i ) 2 R 2 .Thetrajectorypathofanobjectcanthus berepresentedbyasetofdatapoints P = f p 0 ;p 1 ;:::;p n g ,where p i =( x i ;y i ;t i ) and t i denote the i -thtimestep,asshowninFigure1.1. Figure1.1:Exampleofatrajectory.Bluelineisthetraceofamovingobject.Bluedotsare thesamplepoints. Inadditiontoitstime-varyinglocationinformation,atrajectorydatasetoftencontains other(non-spatial)featuresdescribingthestateofthemovingobject.Forexample,thestate ofamovingvehiclecouldbetheaggressivelevelofitsdriver;thestateofatropicalcyclone couldbeitsintensitylevel;whilethestateofapedestriancouldbehis/herwalkingspeed 1 https://www.etymonline.com/word/trajectory 1 andmood.Assumingthestateandpathofthemovingobjectisrecordedatdiscretetime steps t 1 ;t 2 ; ;t T ,theoveralltrajectorydataisrepresentedas D = f ( x i ; s i ;t i ) g T i =1 ,where x i 2 R 2 and s i 2 R d areitsrespectivelocationandstatevectorsattime t i . Atrajectorydatasetcanbecollectedinmanyways,dependingontheapplicationdo- main.Insomeapplications,thetrajectorydataisrecordedbythemovingobjectitself usingaGlobalPositioningSystem(GPS)sensororothergeo-positioningdevices.Forexam- ple,travellerscanusetheirGPS-equippedcellphonestorecordthetrajectorypathsoftheir journeys.Inotherapplications,thetrajectoriesarerecordedbyexternalobserverswhomon- itoredthepathstraversedbythemovingobjects.Forexample,thepathsofahurricaneare constantlymonitoredbytheNationalOceanicandAtmosphericAdministration(NOAA) 2 . Anotherexampleisthevehicletrajectorydataobtainedfromtra˚cmonitoringcameras, wherethetrajectoriesformultiplevehiclescanbecollectedatthesametime. 1.2TrajectoryDataMining Trajectorydataminingisanimportanttasktodiscoverusefulinformationfromtrajectory datasets.AgeneralframeworkfortrajectorydataminingisshowninFigure1.2.Afterthe dataiscollected,preprocessingisoftenneededtoalleviateanydataqualityissuesbefore applyingdataminingalgorithms.Examplesofdatapreprocessingstepsincludenoisereduc- tion,datacompression,mapmatching,andtrajectorysegmentation.Theprocesseddataset canthenbeusedforsubsequenttrajectoryminingtasks. Similartotraditionaldatamining,trajectoryminingtaskscanbeclassi˝edintoseveral categories,suchasclustering,classi˝cation,regression,patternmining,andoutlierdetection. Therearemanyapplicationsthatutilizetheresultsofthesetrajectoryminingtasks.For example,clusteringofhumanmobilitypatternscanbeusedtostudysocialevents;frequent patternminingonvehicletrajectoriescanhelpidentifybottlenecksthatleadtotra˚cjams; whileoutlierdetectionmayrevealinstancesoffraudulenttaxidrivingactivities.Amore 2 http://www.noaa.gov 2 Figure1.2:Generalframeworkoftrajectorydatamining. comprehensivereviewonthedi˙erenttrajectoryminingtasksandtheirapplicationsisgiven inChapter2. 1.3ApplicationtoHurricanePrediction HurricanesareoneofthemostpowerfulstormsonEarththathavethepotentialtocause devastatinglossesanddestructionalongtheirpaths.Giventheirsevereimpact,accurate long-termforecastingofhurricanetrajectoryiscriticaltogiveampletimeforemergency responseteamstotakeappropriateactionsthatwillminimizepropertydamagesandlossof humanlives.Inadditiontoitstrajectory,hurricaneintensityisanotherimportantaspect thatmustbeaccuratelypredictedsinceitisdirectlyrelatedtothepotentialdestructive powerofahurricane.AccordingtotheNationalHurricaneCenter(NHC),high-intensity hurricanesusuallycausehugedamages.Tosupportemergencypreparednesse˙orts,accurate long-termforecastingofthelocationandintensityofanimpendinghurricaneisofupmost importance. Therehasbeengrowinginterestinrecentyearstoapplymachinelearningmethodstothe hurricanetrajectoryforecastingproblem[59,69,3].LeeandLiu[59]presentedaRecurrent NeuralNetwork(RNN)basedapproachtopredictthehurricanetrajectorypathswhileKo- rdmahallehetal.[69]employedasparseRNNwith˛exibletopologyforhurricanetrajectory 3 prediction.Sheilaetal.[3]usedLSTMandGridmodeltoforecastthehurricanetrajectory. However,thereareseverallimitationstothesemachinelearningapproaches.First,theyare mostlybasedonauto-regressiveorrecurrentneuralnetworkmodels,usingonlyhistorical observationdata.Duetotheinherenterrorpropagationproblem[16]insuchmodels,they aremostlysuitableforshort-rangepredictions.Second,duetothechaoticnatureofthe weathersystemandthevaryingconditionsintheatmosphereandoceantemperature,the historicaldataalonemaynotbeenoughtotrainareliablelong-rangeforecastingmodel. Third,thepreviousmethodsaremostlydesignedforbatchlearning.Thus,theyrequirethe modeltobere-trainedfromscratchwhenevernewobservationsbecomeavailable.Anonline learningmethodismoreappealingasitallowsthemodeltobee˚cientlyupdatedto˝tthe newobservationswhileadaptingtotheconceptdriftspresentinthedata. 1.4ResearchChallenges Thisthesisfocusesonthedevelopmentofnovelalgorithmstoaddresssomeofthefundamen- talchallengesinpredictivemodelingoftrajectorydata.Asproofofconcept,thealgorithms developedinthisresearchwillbeappliedtothehurricanepredictionproblem.Eventhough numeroustrajectoryminingalgorithmshavebeendeveloped,therearestillnotablechal- lengesthathavenotbeensu˚cientlyaddressedaslistedbelow. 1. Trajectorydatacollectionisoftenacontinuousprocess,withnewpathandstate informationcollectedovertime.However,duetothedynamicallychangingandnon- stationaryenvironmentoftenencounteredinmanyreal-worldapplications,thepresence ofconceptdriftwilldegradetheperformanceofmanyexistingtrajectoryprediction models.Therefore,akeychallengeistoe˚cientlydevelopmodelsthatwilladaptto changesinthedatadistributionby˝ttingthenewobservationdataavailable. 2. Forecastingthefuturetrajectorypathofamovingobjectisinherentlyamulti-lead timepredictionproblem.Thus,themodelstrainedforpredictingthefuturelocationsor statesofamovingobjectmusttakeintoaccounttheinherenttemporalautocorrelation 4 ofthemulti-leadtimepredictiontask.However,currentmulti-leadtimeprediction modelsaresusceptibletoerroraccumulationproblem,wherethepredictionerrorata giventimestepmaybepropagatedtoitsfuturetimesteps. 3. Missingvaluesinthetrajectorydatacanhampertheperformanceoftrajectorypre- dictionmodels.Forexample,inhurricaneprediction,outputsfromanensembleof physics-basedmodelscanbeusedasinputfeaturesforbuildingahurricaneprediction model.However,structuredmissingpatternsmayexistinthedataastheoutputs fromsomephysicalmodelsintheensemblecanbegeneratedatdi˙erenttimeintervals orareavailableonlyforcertainhurricanes.Handlingmissingvaluesinthetrajectory dataisachallengethathasyettobesu˚cientlyaddressed. 4. Thestateofamovingobjectcanberepresentedasbothqualitativeandqualitative attributes.Forexample,theintensityofahurricanecanbemeasuredinbothratio andordinalscales.Designinganalgorithmthatpredictsthestateofthemovingobject inbothratioandordinalscalesisachallenge. 5. Inpractice,somepredictiontasksaremoreimportantthanothers.Forexample, accuratepredictionofhigh-intensityhurricanesorhurricanesthatwillmakelandfall indenselypopulatedareasareessentialtominimizecasualtiesandpropertydamages. Sincesuchtrajectoriestendtooccurlessfrequently,thismayleadtoaclassimbalance (ordistributionskew)problem.Therefore,designingpredictionmodelsthatconsider thetrade-o˙betweenpredictionaccuracyfordi˙erentclassesisanotherchallengethat needstobeaddressed. 6. Sincethelocationandstateofthemovingobjectareoftenhighlyrelated,itisnatural toconsiderlearningtheirpredictionmodelstogether.Designingapredictivemodeling algorithmthatcansimultaneouslypredictthetrajectoryandqualitativestateofa movingobjectisanotherchallengethathasnotbeenaddressedintheliterature. 5 7. Sincethetrajectoryofamovingobjectistypicallygovernedbynonlineardynamical processes,developingmodelsthataccountfornonlinearrelationshipsinthedatais anothermajorresearchchallenge. 1.5ThesisStatement Onlinelearningisanidealapproachformodelingtrajectorydatainnon-stationaryenviron- ments,sinceitsmodelcanbee˚cientlyupdatedto˝tthenewobservationswhileadapting toconceptdriftspresentinthedata.Inthisresearch,Iwilldevelopafamilyofonline learningalgorithmsfortrajectorydatathatovercometheresearchchallengesdescribedin theprevioussection.Speci˝cally,mythesisaimstoaddressthefollowingresearchquestions. RQ1: Howtodevelopanonlinelearningalgorithmtogeneratemulti-leadtimeforecasts fortrajectorypredictiontask? RQ2: Howtoextendtheonlinemulti-leadtimeforecastingalgorithmtostateprediction thatconsiderbothordinalandratiodatatypes? RQ3: Howtoadapttheonlinelearningalgorithmtomakeitpaymoreattentionsona subsetofthetrajectorydata? RQ4: Howtocombinetheonlinelearningalgorithmsforlocationandstatepredictions intoauni˝edlearningframework? RQ5: Howtodevelopanonlinedeeplearningmodelfortrajectorypredictiontohandle nonlinearitiesinthedata? 1.6ThesisContributions Inthisthesis,afamilyofonlinelearningalgorithmsweredevelopedtoaddressvarious challengesintrajectoryandstatepredictiontasks.Thealgorithmswereappliedtohurricane 6 predictiontaskasproofofconcept. First,Idevelopedaframeworkcalled OMuLeT fortrajectorypredictionbycastingthe taskasamulti-leadtimelocationpredictionproblem. OMuLeT employsanonlinelearning withrestartstrategytoincrementallyupdatethemodelparametersasnewobservationdata becomeavailable.Itcanalsohandlethevaryingfeaturelengthproblemduetomissing valuesusingare-normalizationstrategy. OMuLeT wasappliedtopredictthetrajectoriesof hurricaneswithaleadtimerangingfrom6to48hours.Experimentalresultsusingthe AtlanticandEasternPaci˝churricanedatashowedthat OMuLeT signi˝cantlyoutperforms variousbaselinemethods,includingtheo˚cialforecastsproducedbytheU.S.National HurricaneCenter(NHC). Second,Iextendedthe OMuLeT frameworktopredictthestateofthemovingobject, wherethestatevariablehasanordinaldatatype.Speci˝cally,Iproposedanonlinelearning frameworkcalled OOR ,whichemploysanordinallossfunctiontopredicttheordinal-valued targetvariable.Theframeworkwassubsequentlybeextendedto OOQR toaccommodatea quantilelossfunctioninordertoimproveitspredictionaccuracyforthehigh/lowordinal values.The OOR / OOQR frameworkswereappliedtothehurricanedatasettopredictthe hurricanecategorieswithleadtimesfrom6to48hours.Experimentalresultsshowedthat OOR / OOQR outperformedvariousstate-of-the-artonlinelearningmethodsandcangenerate predictionsclosetotheNHCo˚cialforecasts.The OOQR frameworkcanfurtherimprove itsaccuracyinpredictinghighcategoryhurricanes.Furthermore,usingthe insensitivity lossfunction,Ialsodevelopedthe OOR- and OOQR- frameworkstogeneratereal-valued predictionsofthehurricaneintensitiesbesidesthecategoryinformation.I'veshownthat leveragingreal-valuedintensityinformationwithconstraintsontheordinalcategoriesinto thelearningformulationcanfurtherimprovetheaccuracyofhurricaneintensityprediction. Third,Iinvestigatedthefeasibilityoflearningajointmodelforpredictingthetrajectory andstateofamovingobjectsimultaneously.Aframeworkcalled JOHAN isproposedthat utilizesquantilelossfunctionsforboththelocationandstatepredictiontasks.Thehyper- 7 parametersofthequantilelossfunctionswereupdatedjointlyinanonlinelearningfashion. JOHAN wasappliedtothehurricanedatasetwiththegoalofimprovingtheperformanceof hurricaneintensityprediction,particularlyforhighcategoryhurricanesthatareneartothe coastalland.Experimentalresultsdemonstratethat JOHAN canfurtherimprovethehurri- caneintensitypredictionsbyincorporatingthelocationinformation.Theresultsalsoveri˝ed that JOHAN hasbetterperformanceintermsofidentifyinghighcategoryhurricaneswiththe potentialtostriketheland. Finally,IproposedanLSTM-basedapproachcalled DTP formulti-leadtimelocation predictiontask.WhileexistingRNNbasedapproachesfortrajectorypredictionusually learnfromhistoricalobservationsonly,theyaremostlysuitableforshort-rangepredictions duetotheinherenterrorpropagationproblem[16]. DTP aimstoproduceaccuratelong-range predictionsbyutilizingthemulti-leadtimelocationpredictionsgeneratedbyanensembleof predictionmodels.ATDM(TemporalDecayMemory)wasdesignedtohandlethemissing valueprobleminthedata.The DTP frameworkwasextendedtoanonlinelearningapproach knownas ODTP tohandletheconceptdriftissuepresentintrajectorymodelingtasks.The proposedframeworkswereappliedtothehurricanedatasettogeneratepredictionswith aleadtimeupto48hours.Experimentalresultsshowedthat ODTP canachievebetter performancethan DTP ,andgenerallyoutperformsotherlinearbaselineapproaches. 1.7Publications Thematerialsinthisthesisareadaptedfromthefollowingpublications: DingWang,BoyangLiu,Pang-NingTanandLifengLuo,OMuLeT:OnlineMulti-Lead TimeLocationPredictionforHurricaneTrajectoryForecasting, Proceedingsof34th AAAIConferenceonArti˝cialIntelligence ,2020(Chapter3) DingWang,BoyangLiu,Pang-NingTan,OnlineLearningAlgorithmforHurricane IntensityPrediction, FEED20:FragileEarth:DataScienceforaSustainablePlanet , 2020(Chapter4) 8 1.8ThesisOrganization Theremainderofthisthesisisorganizedasfollows. Chapter2:LiteratureReview Inthischapter,Ireviewedthetrajectorydatamining algorithmsanddiscussedtheirapplications.Similartothedataminingalgorithms,the trajectorydataminingalgorithmscanbeclassi˝edintoseveralmajorcategories,suchas clustering,classi˝cation,patternmining,predictionandoutlierdetection. Chapter3:OnlineMulti-LeadTimeTrajectoryLocationPrediction Inthischap- ter,Ipresentedanonlinelearningframeworkcalled OMuLeT ,whichwasdevelopedforonline multi-leadtimelocationpredictiontask. OMuLeT wasappliedtoreal-worldhurricanedataset togeneratehurricanetrajectoryforecastinginmulti-leadtimes. Chapter4:OnlineMulti-LeadTimeTrajectoryStatePredictionwithOrdinal Data Inthischapter,Ipresentedanovelalgorithm OOR ,whichisanextensionof OMuLeT tohandleordinaldatatypeforthetrajectorystateprediction.Inaddition,theframework canbefurtherextendedto OOQR ,whichaccommodateaquantilelossfunctiontoimprove itsaccuracyforhigh/lowordinaldata.Bothalgorithmwasappliedtohurricanedatasetto predictthehurricaneintensitycategory,whichisoneofthemostimportantstatedatafor hurricanes.Furthermore,using insensitivityloss, OOR- and OOQR- frameworkscanbe developedtogeneratereal-valuedpredictionsofthehurricaneintensities. Chapter5:OnlineJointPredictionofTrajectoryLocationandState Inthis chapter,Iinvestigatedtheadvantagesoflearningthetrajectorylocationandstatepredictions jointlyandpresentanovelapproachcalled JOHAN .Itwasappliedtohurricanedatasetwith thegoalofimprovingthemodelperformanceofthenearlandhighcategoryhurricanes. 9 Chapter6:LSTMforTrajectoryLocationPrediction Inthischapter,Iproposeda LSTMbasedapproach DTP formulti-leadtimelocationpredictiontask.Thisframeworkwas furtherextendedto ODTP ,whichusingonlinelearningtoaddresstheconceptdriftissuein trajectorypredictiontasks.Bothframeworkswereappliedtohurricanedatasettogenerate hurricanetrajectoryforecastinginmulti-leadtimes. Chapter7:ConclusionandFutureWorks Inthischapter,Isummarizedthewhole thesisandgaveacomprehensiveconclusion.Ialsodiscussedhowtofurtherexpandthe currentresearch. 10 CHAPTER2 LITERATUREREVIEW Dataminingistheprocessofextractingusefulinformationfromlargedatasets[31,79]. Sinceitsinception,datamininghasbeensuccessfullyappliedtovariousdomains,including trajectorydata.Thegoaloftrajectorydataminingistwo-fold:tobuildaccurateprediction modelsandtodiscoverinterestingpatternsfromthetrajectorydata.Thegeneralframework fortrajectorydataminingisshowninFigure2.1.Thischapterreviewspreviousworkrelated totrajectorydatamining. Figure2.1:Generalframeworkoftrajectorydatamining. 2.1TrajectoryDataPreprocessing Therawtrajectorydataoftencontainnoise,missingvalues,andotherimperfections.Thus, apreprocessingstepisneededtoimprovethequalityofthetrajectorydataforsubsequent miningtasks.Somedownstreamtasksmayalsorequireadditionalpreprocessingstepssuch astrajectorysegmentationandmapmatching.Inthissection,Ipresentsomecommon approachesforpreprocessingthetrajectorydata. 11 2.1.1DataCleaning Rawtrajectorydata,suchasthecoordinatesrecordedbyGPSdevices,tendtobenoisy.The errorintherecordedpositionscanbeaslargeashundredsofmeters,whichmaya˙ectthe resultsofthetrajectoryanalysis.Datacleaningaimsto˝lternoisefromthetrajectorydata. Therearenumerousapproachesavailabletocleanthetrajectorydata.Inordertoimprove thepositioningaccuracyofGPSdata,avarietyof˝lteringtechniquescanbeapplied,such asmeanandmedian˝lters,Kalmanandparticle˝lters[67,60].ForvehicleGPSdata,a highdensityofGPSpointsindicatesahighprobabilityofbeingontheroad,whilealow densityindicatesthatthevehiclehasdeviatedfarfromtheroad.Inthiscase,lowdensity pointsarenotasimportantandcanbetreatedasoutliers.Thissuggeststhepossibility ofapplyingoutlierdetectionalgorithmstocleanuptheGPSdataset[89,90,91,96,98]. Inadditions,Yangetal.proposedaGPSdatacleaningmethodthatconsidersmovement consistency[85]. 2.1.2TrajectoryCompression Trajectorydatasetsrequireconsiderabledatastorageastheycontainthepathsforalarge numberofobjectsortrajectorieswithhightemporalresolutions.Massivecomputingpoweris alsoneededtoprocessthedatainsubsequentminingtasks.Trajectorycompressionhelpsto reducethesizeofthetrajectorydatawhilestillaccuratelyretainsmostoftheinformationin thetraces.Thecompressionapproachrequiresbalancingthetrade-o˙betweenmaximizing compressionratioandminimizingerrors.Therearetwocategoriesoftrajectorycompression methocompression[26,47]andonlinecompression[51,66].O˜inecompression aimstogeneratelowerresolutiontrajectorieswithfewernumberofsampledpointsfrom atrajectorydataset.Sincemanyapplicationsrequiretrajectorycompressioninatimely fashion,onlinecompressionwasemployedtodetermineifanewlycollectedpositionshould beretainedinthetrajectorydataset. 12 2.1.3MapMatching Additionalsideinformationisoftenneededtoimprovetheperformanceofsometrajectory miningtasks.Forexample,themodelingofvehicletrajectoriescanbeimprovedbyusing informationabouttheroadnetworktopology.Mapmatchingconvertstrajectorysample pointsfromasequenceofcoordinatestoasequenceofroadsegments.Di˙erentmapmatching algorithmshavebeendeveloped,suchastopologicalalgorithms[42,86]andprobabilistic algorithms[71,75,74].Topologicalalgorithmsconsidertheshapeandconnectionofroad networkandmaptheGPSpositionsequencetotheroadnetworkwithlowestdistance measure.Probabilisticalgorithmsconsidermultiplepathsonroadnetworkandcalculate theprobabilitiesfromthetrajectorysamplepoints.Probabilisticalgorithmscanhandle noisyorlow-samplingtrajectorydatasets. 2.1.4TrajectorySegmentation Inmanycases,weneedtodividethetrajectoryintosegmentsforfurtherprocessing.Instead ofusingtheentiretrajectory,sub-trajectoriesenableustominericherinformation.In addition,processingtrajectorysegmentscanbelesstimeconsuming.Atrajectorycanbe segmentedbasedonitsproperties.Therearethreetypesoftrajectorysegmentationmethods. The˝rsttypeofthemethodsisbasedontimeinterval.Ifthetimeintervalbetweentwo datapointsislargerthanathreshold,thetrajectoryisseparatedintotwoparts.Thesecond typeofthemethodsisbasedontheshapeofatrajectory[56].Ifthemovementdirection ofthetrajectorychangesbeyondacertainthreshold,thetrajectorywillsplitatthatpoint. Thethirdtypeofthemethodsisbasedonitssemanticmeaning[57,92,93].Forexample, Yuanetal.[92]estimatedthetravelspeedofataxibasedonthesub-trajectoriesofthetaxi whenitisdriving.Thestoppoints,whichcorrespondtoparkedtaxis,areusedtosplita trajectoryintoasetoftrajectorysegments. 13 2.2TrajectoryDataMiningAlgorithms Trajectorydataminingalgorithmsaredesignedtodiscoverusefulknowledgefromatrajec- torydataset.Manyofthesealgorithmsareextensionsoftraditionaldataminingalgorithms. Similartotraditionaldatamining,trajectorydataminingapproachescanbedividedinto severalcategories,suchastrajectoryclustering,trajectoryclassi˝cation,trajectorypattern miningandtrajectoryprediction.Inthissection,Iwillreviewthevarioustrajectorydata miningalgorithms. 2.2.1TrajectoryClustering Clusteringisthetaskofgroupingtogetherrelatedobjectssuchthatobjectsinthesame grouparemoresimilartoeachotherthantothoseinothergroups.Clusteringcanbe appliedto˝ndrepresentativetrajectoriesormovementpatternssharedbydi˙erentmoving objects.Speci˝cally,trajectoriesthatsharesimilarmovementcharacteristicswillbegrouped togetherintothesamecluster.Atypicalclusteringalgorithmrequiresspecifyingasimilarity measurebasedonfeaturesextractedfromthegivenobjects.Thiscanbechallengingasthe trajectoriescanhavedi˙erentlengths,locations,etc.Clusteringcanbeperformedeitheron thewholetrajectoryoronsegmentsofthetrajectory. 2.2.1.1ClusteringTrajectories Manytrajectoryclusteringalgorithmsareextensionsoftraditionalclusteringalgorithms usingsimilaritymeasuresspeci˝callyde˝nedforthetrajectorydata.Forexample,Birant andKut[7]presentedanextensionofDBSCAN[30],whichisadensity-basedclustering algorithm,knownasST-DBSCAN,toclusterspatio-temporaldata.Ga˙neyandSmyth [33]introducedaprobabilisticmixtureregressionbasedapproachtoclustertrajectories. Furthermore,theyappliedtheirmethodtoclustercyclonetrajectoriesbasedontheiroverall directions[34]. 14 2.2.1.2ClusteringTrajectorySegmentsorPoints Sometrajectoryclusteringtasksrequiresclusteringsegmentsofasingletrajectoryinstead ofclusteringmultipletrajectories.Forexample,Leeetal.[56]designedapartition-and- groupframeworkforclusteringtrajectorysegmentsanddiscoveringcommonsub-trajectories. Palma[72]introducedaspatio-temporalclusteringapproachtoidentifystopsinthetrajec- tory.Accordingtotheirde˝nition,atrajectoryiscomposedofasetofstopsandmoves, withthestopbeingthemostimportantpartofthetrajectory. 2.2.2TrajectoryClassi˝cation Classi˝cationisthetaskofassigningobjectsintoasetofpre-de˝nedcategories(labels orclasses).Classi˝cationisasupervisedlearningtaskthatrequiresasetofannotated labeledexamplestobeavailablefortrainingaclassi˝cationmodel.Traditionalclassi˝cation algorithmscanbeappliedtothetrajectoryclassi˝cationtaskby˝rstextractingrelevant featuresfromthetrajectoriesbeforetrainingaclassi˝cationalgorithmontheextracted features.Forexample,Zhengetal.[97]partitionedthetrajectorydataintosegmentsand extractedfeaturessuchasdirectionchangerate,velocitychangerate,andstopratefrom thesegments.Thesefeaturesarethenusedtoconstructadecisiontreemodelforclassifying trajectoriesintotheirdi˙erenttransportationmodes.Bolboletal.[10]employedasupport vectormachineapproachtoclassifyGPStrajectorydataintodi˙erenttransportationmodes. They˝rstidenti˝edthebestdiscriminativefeaturesofthetrajectorysegmentsbeforetraining anSVMclassi˝ertodeterminethetransportationmodes. Therearesomecommonstepsintrajectoryclusteringandclassi˝cation.Bothneedto extractfeaturesfromthetrajectorydataandthenapplyclusteringorclassi˝cationmethods ontheextractedfeatures.Insomecases,trajectoryclusteringcanbeperformedasaprior steptotrajectoryclassi˝cation.Forexample,Leeetal.[58]proposedaSVMbasedclassi˝- cationframeworkthatutilizestrajectorysegmentationandclusteringtoextractregionsand sub-trajectoryfeaturesfortrajectoryclassi˝cationpurposes. 15 2.2.3TrajectoryPatternMining Trajectorypatternminingdiscoversfrequentlyoccurringmovementpatternsinasingle trajectoryoragroupoftrajectories.Trajectorypatternmininghelpstobetterunderstand thecharacteristicsofmovingobjects.Therearedi˙erenttypesoftrajectorypatternmining tasks.Thetaskscanbemainlygroupedinto3categories,includingperiodicpatternmining, sequentialpatternminingandgrouppatternmining. 2.2.3.1PeriodicPatternMining Periodicpatternminingisapplicabletotrajectorydatawithperiodicactivitypatterns,such as,theannualmigrationpatternsofanimalsorthedailyroutestakenbyabus.Mining periodicpatternsfromthetrajectorydataisachallengeduetothecomplexperiodicbe- haviorsincludingmultipleinterleavingperiods,noise,andoutliers.Caoetal.[14]proposed analgorithmtodiscoverfrequentregionsanditerativelycombinethemtoobtainthecom- pleteperiodicpatterns.Thisapproachisappliedtospatio-temporalsequences,thoughit assumesthattheperiodicityisknownbytheuser.Lietal.[63]suggestedanalternative approachthatcandetecttheperiodsinadvance.First,theydetectedmultipleperiodsinthe movementusingamethodthatcombinesFouriertransformwithtemporalauto-correlation. Theythendesignedaprobabilisticmodeltorevealtheperiodicbehaviorfrommovement sequencesusinghierarchicalclustering. 2.2.3.2SequentialPatternMining Sequentialpatternminingisthetaskof˝ndingcommonsubsequencessharedbymultiple trajectories.Thecommonsubsequenceisasubsetoflocationsthatappearsinmultiple trajectories.Thediscoveredsequentialpatternsenableustobetterunderstandtherelation- shipbetweendi˙erenttrajectories.AnexampleofasequentialpatternisshowninFigure 2.2.ThetrajectoriesA,B,andCshareacommonsubsequence D containingthepath 16 p 2 2hour ! p 4 1hour ! p 5 . A : p 1 1hour ! p 2 1.2hour ! p 3 0.8hour ! p 4 1hour ! p 5 B : p 2 1.2hour ! p 6 1hour ! p 4 1hour ! p 5 1hour ! p 7 C : p 1 1.2hour ! p 2 2.2hour ! p 4 0.5hour ! p 8 0.6hour ! p 5 D : p 2 2hour ! p 4 1hour ! p 5 Figure2.2:ThetrajectoriesA,B,CsharedacommonsequenceastrajectoryDwithsimilar timeinterval. Thesequentialpatternscanbeuncoveredaccordingtotheirspatial,temporal,orspatio- temporalproperties,asshowninFigure2.3.Sometrajectoryminingtasksconsideronlythe spatialproperty,whichisthesequenceoflocations.Caoetal.[13]proposedanalgorithmto ˝ndsequentialpatterns.First,theytransformedtheoriginalsequenceintoalistofsequence segmentsbeforedetectingthefrequentregions.Thepatternsarefoundbyemployinga substringtreestructureapproachthatextendstheAprioritechnique.Giannottietal.[37] introducedthenotionofatrajectorypattern(T-Pattern)anddevelopedseveralapproaches toextractthemfromagiventrajectorydata. A : p 1 ! p 2 ! p 3 ! p 4 ! p 5 B : p 1hour ! p 2hour ! p 2hour ! p 1hour ! p C : p 1 1hour ! p 2 2hour ! p 3 2hour ! p 4 1hour ! p 5 Figure2.3:TrajectoryAconsidersonlyspatialproperty;trajectoryBconsidersonlytem- poralproperty;whiletrajectoryCconsidersbothspatio-temporalproperties. 2.2.3.3GroupPatternMining Grouppatternminingextractsthemovementpatternsforagroupofobjectsmovingtogether. Therearedi˙erentkindsofgrouppatterns,suchas˛ocks[45,44,6],convoys[49,50]and 17 swarms[62].Thesegrouppatternsarethemajorcategoriesofgrouppatternswithexamples showninFigure2.4. Figure2.4:Exampleofasequentialgrouppatterns:(a)˛ock,(b)convoy,(c)swarm. A˛ock[45]isagroupofobjectsthattraveltogetherforatleastkconsecutivetimestamps andstaywithinadiscofradiusr.Onemajorconcernisthattheprede˝neddiscofradiusr maynotrepresenttheactualgroupsofmovingobjectsintermsoftheirshapesandsizes.To addressthisissue,Jeungetal.[49,50]de˝nedaconvoypatternasagroupofobjectsthat traveltogetherforatleastkconsecutivetimestampsandstaywithinashapegeneratedby density-basedclustering.Theconvoypatternrelaxesthediscshapeassumptionrequiredby ˛ocktoanyshapesformedbythemovingobjects.However,both˛ockandconvoypatterns requirethegroupofobjectstomovetogetherforatleastkconsecutivetimesteps.Later, Lietal.[62]proposedannewgrouppattern,calledswarm,whichisde˝nedasagroupof objectsthattraveltogetherforatleastkpossiblynon-consecutivetimestamps. 18 2.2.4TrajectoryPrediction Thegoaloftrajectorypredictionistoforecastthefuturelocationofamovingobjectbased onitsprevioustrajectorypaths.Asaharaetal.[4]designedamethodforpredictingpedes- trianmovementusingamixedMarkov-chainmodel(MMM).Speci˝cally,theymodeledthe pedestrian'spersonalityasanunobservableparameterandutilizedthepedestrian'sprevious status.Mathewetal.[64]presentedamethodforpredictinghumanmobilitybasedon HiddenMarkovModels(HMMs).They˝rstclusteredthelocationhistoriesaccordingto theircharacteristicsandthentrainedanHMMforeachcluster.BesidesMarkovmodels,the futuretrajectorypathcanbepredictedbyusingtrajectorypatternmining.Forexample, Monrealeetal.[68]presentedamethod,calledWhereNext,topredictthenextlocationofa movingobjectwithadecisiontreebuiltfromtheextractedtrajectorypatterns.Yingetal. [87]modeleduser'smovementbehaviorusinghistoricaltrajectorypatternsandestimated theprobabilityofuser'snextlocation. Morerecently,therehasbeenconsiderableinterestsinapplyingdeeplearningapproaches tothetrajectorypredictiontask.Alahietal.proposedaLongShort-TermMemory(LSTM) basedapproachtopredictfuturetrajectoriesofhumansincrowdedspaces.Theybuilt multipleLSTMsforpedestriansandapoolinglayertosharetheinformationbetweenLSTMs. Kimetal.[52]designedane˚cientLSTMbasedframeworktopredictvehicletrajectories. TheyemployedLSTMtoanalyzethevehicletemporalbehaviorandtopredictthefuture locationsofthesurroundingvehiclesonagridmap.LeeandLiu[59]presentedaRNNbased approachtopredictthefeaturelocationofhurricanes.Kordmahallehetal.[69]usedsparse RNNwith˛exibletopologyforhurricanetrajectorypredictions.Toforecastthehurricane trajectory,theyfoundthemostsimilarhurricanestothetargethurricaneandtrainedtheir RNNmodelwithageneticalgorithm(GA).However,theywereonlyinterestedinshort-term forecasts(upto6hours).Sheilaetal.[3]usedLongShort-TermMemory(LSTM)andGrid modeltoforecasthurricanetrajectory.Theyalsofocusedonshort-termforecastingupto6 hoursofleadtime. 19 2.2.5TrajectoryOutlierDetection Outlierdetectionaimsto˝ndunusualtrajectoriesorsub-trajectoriesthatdonothavesimilar patternsinthegiventrajectorydataset.Trajectoryclusteringorclassi˝cationalgorithmscan beusedfortrajectoryoutlierdetection.Forexample,Leeetal.[57]extendedthepartition- and-groupframeworktheyhaddevelopedin[56]fortrajectoryclusteringtoatrajectory outlierdetectiontask.Lietal.[61]designedarule-basedclassi˝ertodetectabnormal movingobjects.Theyextractedfeaturesfromthetrajectoriestoformahierarchicalfeature spaceandtrainedarule-basedclassi˝ertodetecttheoutliers. Trajectoryoutlierdetectioncanbeappliedeithertothewholetrajectory[94]orsub- trajectories[57,88].Zhangetal.[94]presentedanalgorithmfordiscoveringanomalous drivingpatternsfromGPStracesoftaxirides.Yuanetal.[88]extractedfeaturesfrom trajectorysegmentsandemployedadistancemeasureto˝ndoutliers. 2.3TrajectoryDataMiningApplications Therearemanyimportantapplicationsoftrajectorydatamining.Forexample,theGPS trajectoriesoftaxiscanbeusedtostudycitytra˚cdynamics.Thestudyoftheuser'stravel trajectorycanbeusedtogeneratetravelrecommendations.Inthisthesis,Iinvestigatedthe hurricanetrajectorypredictiontask,whichisoneofthemostimportanttrajectoryprediction tasks.Idevelopedasetoftrajectorypredictionalgorithmsandappliedthemtoreal-world hurricanedata.Inthissection,therecentapplicationsforhurricanepredictiontaskswere discussed. Hurricanesarestrongtropicalcycloneswithwindspeedexceeding75milesperhour thatitcancauseseveredamagesatlandfall.Therefore,hurricanetrajectoryforecastingis crucial,whichallowsthecivilianstohavemoretimetoprepareandevacuate.Hurricane trajectoryforecastingpredictsfuturepositionsofthehurricane.Thehurricanetrajectory forecastingreliesoncomplexphysicalmodels,whicharecomplexsystemcontainsmathe- maticalformulationsofphysicalprocesses.Therearenumbersofdi˙erentphysicalmodels, 20 (a) (b) Figure2.5:TrackerrorsofNHCo˚cialforecastsfromyear1990to2019[12].Figure(a) showstheerrorsatAtlanticbasin.Figure(b)showstheerrorsatEasternNorthPaci˝c basin. suchasAVNO,AVNI,AEMN,AEMI 1 .Scientistsareinterestedinimprovingtheaccuracy oftrajectoryforecastsforextendedperiodoftime.Forexample,forecastforupcomingdays. However,itisdi˚culttoimprovetheperformancesincetheseforecastmodelsaresensitive tothecomplexityandnonlinearityofatmosphericsystem.NHCpublishedtheerrortrendof theiro˚cialtrackforecastingerroroverpastdecades[12]asshowninFigure2.5.Withbet- tersatellitedataandfastercomputers,theforecastperformancehasbeenslowlyimproved sincethepastdecades. Numerousdataminingandmachinelearningapproacheshavebeenappliedtothehur- ricanepredictionproblem.Forexample,LeeandLiu[59]presentedaneuralnetwork-based approachtopredictthefeaturesofhurricanes.Kordmahallehetal.[69]usedsparseRNN with˛exibletopologyforhurricanetrajectorypredictions.Toforecastthehurricanetra- jectory,theyfoundthemostsimilarhurricanestothetargethurricaneandtrainedtheir RNNmodelwithGeneticAlgorithm(GA).Sheilaetal.[3]utilizedLongShort-TermMem- ory(LSTM)andGridmodeltoforecasthurricanetrajectory.However,theseapproaches weremostlylimitedtoshort-termforecasts(of6hours)only.Accuratepredictionoflong- termforecastsisneededtogiveampletimeforemergencypreparatione˙orts.TheNational 1 https://www.nhc.noaa.gov/modelsummary.shtml 21 HurricaneCenter(NHC)oftheNationalOceanicandAtmosphericAdministration(NOAA) generateso˚cialforecastsforimpendinghurricanesbasedonvariousmodels.Thesemodels canbecategorizedintofourcategories:dynamical,statistical,statistical-dynamical,anden- sembleorconsensusmodels.Duringthelifetimeofahurricane,NOAAprovidesitso˚cial forecastsevery6hours,whichincludeinformationsuchaslongitude,latitude,maximum windspeed,andthecentralpressure. 22 CHAPTER3 ONLINEMULTI-LEADTIMETRAJECTORYLOCATIONPREDICTION Trajectorypredictionisoneofthemostimportanttasksintrajectorydatamining.The goalofthistaskistoinferthefuturelocationsofamovingobject.Trajectoryprediction isthereforeequivalenttoamulti-leadtimelocationpredictiontask,whichachallenging problemduetotheinherenterrorpropagationproblem[16].Thepresenceofconceptdrift inthedatawillalsoresultinoutdatedmodels,therebydegradingtheirpredictiveaccuracy overtime.Inthischapter,Iproposetoaddressthesechallengesbydevelopinganonline learningalgorithmtogeneratetheanticipatedtrajectorypathofthemovingobject.As proofofconcept,theframeworkwasappliedtohurricanetrajectoryprediction,whichisan importantapplicationwithsigni˝cantreal-worldimplications. HurricanesareoneofthemostpowerfulstormsonEarththathavethepotentialto causedevastatinglossesanddestructionalongtheirpaths.Forexample,theGalveston Hurricaneof1900isconsideredthedeadliesthurricaneinUnitedStates,responsiblefor atleast8000deaths[9].In2005,HurricaneKatrinatookawaymorethan1500livesand causedatleast$108billionofpropertydamages[9].Giventheirsevereimpact,accurate long-rangepredictionofhurricanetracksiscriticaltogiveampletimeforemergencyresponse teamstotakeappropriateactionsthatwillminimizepropertydamagesandlossofhuman lives.Towardsthisend,dynamicalmodelssuchasNOAA'sHurricaneWeatherResearch andForecasting(HWRF)systemandU.S.NavyGlobalEnvironmentalModel(NAVGEM) havebeenwidelyusedastheprimarytoolforhurricaneforecasting.Althoughtheskillsof thesemodelshaveimprovedsteadilyovertheyears,theforecasterrorsandvariabilityamong themodelpredictionsstillincreasewithleadtime,asshowninFig.3.1. Ensembleforecastingseekstobetterrepresenttherangeofforecastuncertaintiesby combiningoutputsgeneratedbymultipledynamicalmodels.Eachdynamicalmodelcan produceoneormoreensemblememberoutputsbyperturbingitsinitialconditionsormodel 23 Figure3.1:Hurricanetrackforthefollowing48hourspredictedbyanensembleofdynamical modelsforHurricaneIrmaonSeptember10,2017.Thegreenlinesrepresentthevarious forecastsproducedbytheensemblememberswhereastheblackdashlinecorrespondsto theensemblemean.TheredlinecorrespondstothebesttrackaccordingtotheNational HurricaneCenter. parameters.Theensemblemeanormedianarecommonlyusedasthedeterministicforecast fromtheensemble.Theseestimatesassumethateverymemberisequallyskillful,andthus, theirpredictionsshouldbeweightedequally.Suchanassumptionmaynotberealisticdue totheinherentdi˙erencesinthewaytheensemblememberoutputsaregenerated.Thusin anoperationalforecastenvironmentwhensuchensembleforecastsareissuedonaregular basis,theweightofeachmembermustbeestablishedbasedontheiraccuracyinpredicting thetracks.However,determiningtheappropriateweightsisnotatrivialtaskastheskillsof themodelsmayvaryovertime.Toovercomethischallenge,theprimarygoalofthischapter istodevelopanonlinetrajectoryforecastingframeworkthatcandynamicallyupdatethe weightsoftheensemblemembersbasedontheirpastandrecentperformancewhenveri˝ed againstobservations. 24 Ensemblememberforecastsatdi˙erentleadtimes, ˝ ˝ =1 (24hrs) ˝ =2 (48hrs) Hurricane Time NHCBest AEMI AEMN CLP5 AEMI AEMN CLP5 h i t track, y i;t x i;t; 1 1 x i;t; 1 2 x i;t; 1 3 x i;t; 1 1 x i;t; 2 2 x i;t; 2 3 SANDY 1 [12.7;-78.7] [14.6;-77.8] N/A [13.4;-80.7] [18.4;-76.4] N/A [14.2;-82.3] 2 [12.9;-78.1] [15.7;-77.7] N/A [14.1;-79.2] [19.8;-76.8] N/A [15.6;-79.9] 3 [14.0;-77.6] [17.8;-76.9] N/A [16.0;-77.5] [22.7;-76.5] N/A [18.0;-77.9] IRMA 1 [16.4;-32.5] [18.5;-35.3] [18.8;-35.3] N/A [19.1;-39.7] [19.2;-40.0] N/A 2 [17.1;-34.2] [18.4;-38.4] N/A N/A [18.2;-42.9] N/A N/A 3 [17.9;-36.1] [18.4;-40.2] [18.7;-40.5] N/A [17.5;-44.4] [17.6;-45.0] N/A Table3.1:ExampleofNHCbesttrackhurricanetrajectorydataalongwiththeforecasts generatedbyanensembleofdynamicalmodelssuchasAEMI,AEMN,andCLP5forHur- ricanesSandyandIrmaatdi˙erentleadtimes.N/Adenotesmissingvalues. IntheUnitedStates,theNationalHurricaneCenter(NHC)isresponsibleformonitoring andprovidingo˚cialforecastsofthetrajectoryandintensityofhurricanesintheAtlantic andEasternPaci˝ctothepublic.Withasetofdynamicalmodelforecastsasguidance,the o˚cialNHCforecastsareproducedbasedontheexperienceandjudgmentoftheforecasters. Asecondarygoalofthischapteristoinvestigatethefeasibilityofusinganonlinelearning approachtogenerateforecaststhatareequallyormoreskillfulthantheo˚cialforecasts reportedbyNHC. Therehasbeengrowingresearchinrecentyearstoapplydataminingandmachinelearn- ingmethodstothehurricanetrajectoryforecastingproblem[59,69,3].However,thereare severallimitationstotheseapproaches.First,theyaremostlybasedonauto-regressiveor recurrentneuralnetworkmodels,usingonlythehistoricalobservationdata.Duetotheinher- enterroraccumulationproblem[16]insuchmodels,theyaremostlysuitableforshort-range predictionsandareine˙ectiveforearlywarningsystems.Second,duetothechaoticnature oftheweathersystemandthevaryingconditionsintheatmosphereandoceantempera- ture,thehistoricaldataalonemaynotbeenoughtotrainareliablelong-rangeforecasting model.Bygroundingthehistoricalobservationswithmulti-modelensembleforecastsfrom dynamicalmodels,itmayleadtomorereliablepredictions.Third,thepreviousmethods aremostlydesignedforbatchlearning.Thus,theyrequirethemodeltobere-trainedfrom scratchwhenevernewobservationsbecomeavailable.Anonlinelearningmethodismore 25 appealingasitallowsthemodeltobee˚cientlyupdatedto˝tthenewobservations. Designinganonlinelearningalgorithmforhurricanetrajectoryforecastingisachallenge forseveralreasons.First,themodelstrainedforpredictingthehurricane'slocationatdif- ferentleadtimesmusttakeintoaccounttheinherentautocorrelationalongthetrajectory. Furthermore,theyaresusceptibletothepartiallyobserveddataproblemdescribedin[84]. Forexample,ifthemodelisupdatedeverysixhourswithnewobservationdataandthe forecasthorizon(i.e.,maximumleadtime)is48hours,itisinsu˚cienttoreviseonlythe latestmodel.Instead,weshouldalsorevisetheoldermodelsforallleadtimesstarting from48hoursagoupto6hoursago.Otherwise,theerrorsfromtheoldermodelswill continuetopropagateintofutureprediction.Anotherchallengeisthattheensemblemem- bersavailablemayvaryfromonehurricanetoanother(seeTable3.1).Duetothemissing forecastsbysomemodelmembers,theonlinealgorithmmustadaptivelylearntheweights inspiteofthevaryingfeaturelengths.Toaddressthesechallenges,weproposeanovel frameworkcalled OMuLeT ( O nline Mu lti- Le ad T imeForecasting),whichemploysanonline learningwithrestartstrategytoincrementallyupdatetheweightsoftheensemblemembers. OMuLeTcanalsohandlethevaryingnumberofensemblememberforecastsbyemployinga novelweightrenormalizationscheme.Theoreticalproofsareprovidedtojustifytheweight renormalizationapproach.ExperimentalresultsusingtheAtlanticandEasternPaci˝chur- ricanedatashowedthat OMuLeT canimprovethe48-hourleadtimeo˚cialforecastofNHC bymorethan10%. 3.1RelatedWork Alemanyetal.[3]categorizedpreviousmethodsforhurricanetrajectoryforecastinginto4 types:(1)dynamicalmodels[81,22],(2)statisticalmodels[24,76],(3)statistical-dynamical models[80]and(4)ensembleorconsensusmodels[95].Dynamicalmodelsrequirepowerful computerstosolvethephysicalequationsdescribingchangesintheatmosphericsystem. Incontrast,statisticalmodelsconsidertherelationshipbetweenthecurrentandhistorical 26 trajectories.Statistical-dynamicalmodelsarehybridsofbothtechniqueswhileensemble modelsgenerateforecastsbymergingtheforecastsfromasuiteofdynamicaland/orstatis- ticalmodels. Inadditiontohurricanetracks,themulti-leadtimetrajectorypredictioncanbeappliedto otherdomains.Forexample,Asaharaetal.[4]designedamethodforpredictingpedestrian movementusingamixedMarkov-chainModelwhileMathewetal.[64]presentedamethod forpredictinghumanmobilitybasedonhiddenMarkovmodels(HMMs).Trajectorypattern miningmethodshavealsobeendevelopedfortrackprediction.Forexample,Monrealeetal. [68]presentedamethodcalledWhereNexttolocatethepositionofamovingobjectusing adecisiontreetrainedto˝tfeaturesextractedfromtrajectorypatterns.Yingetal.[87] useshistoricaltrajectorypatternstoestimatetheprobabilityofauser'snextlocation.More recently,deeplearningmethodshavebeendevelopedfortrajectorypredictiontasks.For example,Alahietal.[2]proposedaLongShort-TermMemory(LSTM)basedapproachto predicthumanfuturetrajectoriesincrowdedspaceswhileKimetal.[52]designedanLSTM basedframeworktopredictvehicletrajectories. Therehavealsobeensomepreliminaryworkonhurricanetrajectoryforecastingusing deeplearning.LeeandLiu[59]presentedaRecurrentNeuralNetwork(RNN)basedapproach topredictthehurricanetrajectorypathswhileKordmahallehetal.[69]employedasparse RNNwith˛exibletopologyforhurricanetrajectoryprediction.Sheilaetal.[3]usedLSTM andGridmodeltoforecastthehurricanetrajectory.Noneoftheseapproachesutilizethe multi-modelensembleforecastnorweretheydesignedforanonlinelearningsettingunlike theapproachproposedinthisthesis. 3.2ProblemFormulation Weinvestigatetheproblemofpredictingthetrajectoryofamovingobjectbasedona setofinputfeaturesthatcanbederivedeitherfromhistoricalobservationsorthrough othermeans(e.g.,forecastsgeneratedfromamulti-modelensembleinthecaseofhurricane 27 trajectoryprediction).Forbrevity,therestofthediscussioninthischapterispresentedin thecontextofhurricaneprediction,althoughtheproblemformulationandmethodologycan beappliedtootherdomainswithsimilarcharacteristics.Considerasetof N hurricanes, h 1 h 2 h N ,orderedbytheirstarttimes.Forthe i -thhurricane,let y i;t 2 R 2 denote itslocation(latitudeandlongitude)attime t ,where t 2f t i; 1 ; ;t i; i g and i denotes theobservedtrajectorylengthforhurricane h i .Furthermore,ateachtime t ,ourgoalisto forecastthehurricane'slocationatafuturetimestep t + ˝ ,where ˝ 2f 1 ; ;T g isthelead timeand T istheforecasthorizon. Let m i bethenumberofensemblememberforecastsavailableforhurricane h i .Thesetof ensemblememberforecastsavailabletopredictthelocationof h i attime t + ˝ isrepresented bythematrix X i;t;˝ 2 R 2 m i ,whileitsgroundtruthlocationisgivenby y i;t + ˝ 2 R 2 .The hurricanetrajectorydataisgivenbyasetof2-tuples, f ( X i;t;˝ ; y i;t + ˝ ) g ,wherethesuperscript i denotesthehurricane, t istheforecastgenerationtime,and ˝ istheforecastleadtime. VaryingFeatureLength: Oneofthekeycharacteristicsofthemulti-modelensemblehur- ricanetrajectorydataisthatitsfeaturelength,i.e.,numberofensemblememberforecasts ( m i )associatedwitheachhurricane,mayvaryfromonehurricanetoanother.Speci˝- cally,althoughtherearenumerousensemblememberforecastsgeneratedovertheyears, eachhurricanehasforecastsobtainedfromanaverageofonly19ensemblemembersinour dataset.Theunavailableensemblememberswouldcreatenon-randommissingpatternsin thedata.Imputingthemissingvaluesisnotaviablesolutionduetothehighmissingrate. Instead,weproposeanapproachthatcanautomaticallyhandlethevaryingfeaturelength byrenormalizingtheweightsoftheensemblemembers. TemporalInconsistencies: Outputsfromthedynamicalmodelshavevaryingdegrees oftemporalinconsistencies.First,thedynamicalmodelscanhavedi˙erentforecasttime intervals.Somemodelsgeneratetheirforecastsevery6hours,whileothersevery12hours. Toaddressthisproblem,weperforminterpolationtoimputethemissingvaluesofthe12- hourlyforecastintervalstoobtain6-hourforecastsforallensemblemembers.Second,the 28 forecastdurationoftenvariesamongtheensemblemembers.Forexample,somemembers generatetheirforecastsforonlyafewdays,whileothersmayextendlongerthanaweek. Inaddition,theirforecasthorizonarealsodi˙erent.Forexample,somemodelsproduce forecastswithamaximumleadtimeof24hours,whileothersmaygenerateforecastsfor aleadtimeupto120hours.Anovelweightrenormalizationapproachisproposedinthis chaptertoaddresssuchtemporaldiscrepancies. PartiallyObservedLabeledData: Anotherchallengeisthatgroundtruthvaluesforthe multi-leadtimeforecastsareonlypartiallyobserved.ThisproblemisillustratedinFigure 3.2.Let X i;t 1 ; 1 bethesetofensemblememberforecastsgeneratedforhurricane h i attime t 1 fortheleadtime ˝ =1 .Ifthecurrenttimeis t ,thenthegroundtruthvalue y i;t will beavailabletoverifytheaccuracyoftheforecastsin X i;t 1 ; 1 .However,forthelonger-range forecasts, X i;t 1 ; 2 , X i;t 1 ; 3 , , X i;t 1 ;T ,thegroundtruthvalueshavenotbeenobserved.In fact,thegroundtruthvaluesareonlyavailableforanypreviousforecast X i;t k;˝ forwhich ˝ k 0 .ThiscorrespondstotheredrectanglesshowninFigure3.2.Astimeprogressesto t +1 ,thetruevaluefor y i;t +1 willbeknown.Conventionalonlinelearningalgorithmsusethe newobservation y i;t +1 toupdatetheirlatestmodelsonly.Thisisinsu˚cientformulti-lead timeforecastingasthenewobservationdatamaytriggeracascadinge˙ectsincesomeofthe earliermodelsfromwhichthecurrentmodelsareobtainedarealsooutdated.Themodels forvariousleadtimesgeneratedattime t mustberolled-backallthewaytotime t T +1 andupdatedagainwiththenewobservationdatatoalleviatetheerrorpropagationproblem. Thisstrategyisknownasonlinelearningwithrestart[84]. 3.3Methodology Weconsideranonlinemodeloftheform f ( X i;t;˝ )= X i;t;˝ w i;t;˝ forpredictingthelocation ofhurricane h i attime t + ˝ ,where w i;t;˝ 2 R m i istheestimatedweightvectorassociated withthe m i ensemblememberforecasts.Conventionalonlinelearningalgorithms[21,84] typicallyassumethatthefeaturematrix X i;t;˝ iscomplete,i.e.,hasnomissingvalues,or 29 Figure3.2:Anillustrationofthepartiallyobservedlabeleddataproblem.Theredrectangles denotethesetofmodelforecastsforwhichgroundtruthareavailableattime t . containsmissingvaluesthathavebeenimputed.However,duetothevaryingfeaturelength problemdescribedintheprevioussection,someensemblememberforecastsmaynotbe availableforagivenhurricane h i .Below,wedescribeourproposedapproachtoaddressthis problem. 3.3.1WeightRenormalization Thissectionpresentstheweightrenormalizationapproachemployedbyouronlinelearning frameworktoovercomethevaryingfeaturelengthproblem.Let = f 1 ; 2 ; ; m g be thesetofallensemblemembersand M i bethesubsetofmemberswhoseforecasts areavailableforhurricane h i .Since j M i j˝ m ,imputingthemissingensemblemember forecastsisnotane˙ectiveapproachgiventhelargeamountofmissingvaluespresentinthe data.Instead,wepresentanonlinelearningapproachthatusesonlytheensemblemember forecastsavailableforthegivenhurricane( M i )andupdatetheirweightsaccordinglywhen newobservationdatabecomesavailableateachtimestep.Speci˝cally,weassumethe forecastsfromeachensemblememberfollowaGaussiandistributioncenteredatthetrue location.Toillustratethis,Figure3.3showsanormalizedhistogramofthetrajectoryforecast 30 errorsfor5dynamicalmodelswhenappliedtomorethan200hurricanesinourdataset. ObservethattheforecasterrordistributionindeedresemblesthatofaGaussiandistribution. Wealsoassumethattheweightsoftheensemblemembersforman m -dimensionalsimplex, i.e.: m = f w i 1 ;w i 2 ; ;w i m 8 i : X j w i j =1 ;w i j 0 g : Givenahurricane h i ,ourframeworkperformsthefollowingstepstoincrementallyupdate theweights: 1. Weextractthesubvector w i 0 2 R m i fromthefullvector w 2 R m ,whoseelements containonlytheweightsofthe m i ensemblemembersin M i . 2. Wenormalize w i 0 tohaveunitsumasfollows: w i 0 w i 0 =c; where c = j w i 0 j 1 = X j w i 0 ;j 3. Ateachtimestep t = f t i; 1 ;t i; 2 ; ;t i; i g : a) Weusethenormalizedweightstopredictthelocationofthehurricaneatlead time t + ˝ ,i.e., f ( X i;t;˝ )= X i;t;˝ w i;t;˝ ,where w i;t;˝ iscomputedfrom w i 0 according toEqn.(3.6). b) Afterobservingthegroundtruthlocation y i;t ,weupdate w i;t;˝ usingthemethod describedinSection3.3.3. 4. Afterthelastupdateattime t = i ,theupdatedweightsarerenormalizedtotheir originalsum: w i 0 c w i 0 (3.1) beforebeingreplacedintothefullvector w .Thisensuresthat w remainsasimplex aftertheweightupdate. Theprecedingapproachenablesourframeworktoupdateonlytheweightsoftheensemble memberswhoseforecastsareavailableforhurricane h i .Theweightsneedtoberenormalized 31 whenreplacingthembackintothefullvector w .Below,weprovideaformaljusti˝cation fortheweightrenormalizationapproach.Forbrevity,weassumethehurricanelocationisa scalarvariable,eventhoughthetheorembelowcanbeextendedto2-dimensionallocation vectors. (a)Forecasterrorsalongthelatitudedirec- tion. (b)Forecasterrorsalongthelongitudedirec- tion. Figure3.3:Normalizeddistributionoftrajectoryforecasterrors(in50milesbin)for5 di˙erentdynamicalmodelsalongtheirlatitudeandlongitudedirections. Example1. Considerasetofforecastsgeneratedfromanensembleof5members.Assume theirweightsisgivenbythefullvector w =[0 : 15 ; 0 : 1 ; 0 : 4 ; 0 : 05 ; 0 : 3] .Supposewewantto update w basedontheobservedtrajectoryofhurricane h i .Assumetheforecastdataof h i areonlyavailableforthesecondandthirdensemblemembers.Inthe˝rststep,weextract thesubvector w i =[0 : 1 ; 0 : 4] .Afternormalizingthevectortohaveunitsum,theweights become w i =[0 : 2 ; 0 : 8] .Usingtheforecastdatafromthetwoensemblemembersandtheir groundtruthvalues,supposetheweightsareupdatedto w i =[0 : 4 ; 0 : 6] .Werenormalize theirvaluestomaintaintheoriginalsumof0.5beforereplacingthemintothefullweight vector.Thefullvectoraftertheweightupdateis w =[0 : 15 ; 0 : 2 ; 0 : 3 ; 0 : 05 ; 0 : 3] . Next,weprovideformalproofstojustifytherationaleforourproposedweightrenormal- izationapproach.Forbrevity,weassumethehurricanelocationisascalarvariableinstead 32 ofa2-dimensionalvectoroflatitudeandlongitude,thoughtheproofbelowcanbeextended to d -dimensionallocationvectors. Theorem1. Let y denotesthetruehurricanelocationand f X 1 ;X 2 ; , X M g be M i.i.d. variables,representingthe M ensemblememberforecasts.Assumeeach X j isarandom perturbationaround y ,i.e.: X j = y + (0 ;˙ 2 j ) ; where (0 ;˙ 2 j ) isaGaussiandistributionwithmean0andvariance ˙ 2 j .Then,thebest unbiasedlinearestimator(BLUE)for y is z = P j w j X j ,where w j = 1 ˙ 2 j P M j =1 1 ˙ 2 j . Proof. Weconsiderlinearestimatorsoftheform z = P j w j X j .Since f X 1 ;X 2 ;:::;X M g are i.i.d.variables: E ( z )= M X j =1 w j E ( X j )= M X j =1 w j y (3.2) Since z isunbiased,itsexpectedvalueisequalto E [ y ] .Thus, E ( z )= M X j =1 w j y = y ) M X j =1 w j =1 (3.3) Thevarianceofthelinearestimatoris Var ( z )= M X j =1 w 2 j Var ( X j )= M X j =1 w 2 j ˙ 2 j (3.4) To˝ndthe w thatminimizesthevariance,subjecttotheconstraintinEq.(3.3),weconsider thefollowingLagrangianfunction: L = M X j =1 w 2 j ˙ 2 j ( M X j =1 w j 1) Takingitspartialderivativew.r.t w k andsettingitto0yields @L @w k =2 w k ˙ 2 j =0 ) w k = 2 ˙ 2 k Followingtheconstraint P M j =1 w j =1 ,wecansolvefor andobtain: w j = 1 ˙ 2 j = M X k =1 1 ˙ 2 k (3.5) whichcompletestheproof. 33 Theprecedingtheoremconsidersanestimator z computedfrom M i.i.d.variables.Let ~ z beanotherestimatorcomputedusing K ofthei.i.d.variablesin f X j g .Withoutlossof generality,weassumethe K variablesare X 1 ;X 2 ; ;X K . Corollary1. Let y bethetruelocationofthehurricaneand ~ z = P K j =1 ~ w j X j bealinear estimatorof y ,whereeach X j = y + (0 ;˙ j ) 2 .Thenthebestlinearunbiasedestimator (BLUE)for y usingthe K i.i.d.variablesis ~ z = P K j =1 ~ w j X j ,where ~ w j = cw j and c = 1 P K j =1 w j . Proof. TheBLUEfor ~ w j issimilartoEq.(3.5)exceptthesuminthedenominatorgoes from1toK.Takingtheratioof ~ w j to w j : ~ w j w j = 1 P K j =1 1 ˙ 2 j = P M l =1 1 ˙ 2 l = 1 P K j =1 w j c Thus, ~ w j = cw j ,whichcompletestheproof. Theprecedingcorollaryshowsthenormalizationfactorneededtore-scaletheweightsof asubsetoftheensemblemembers. 3.3.2GeographicDistanceLossFunction Insteadofusingasquared ` 2 (Euclidean)lossfunction,ourframeworkconsidersthesquared geographicdistancetocomputetheerrorinlocationestimation.Let z i;t;˝ =[ z i;t;˝ 1 ;z i;t;˝ 2 ] be thepredictedlatitudeandlongitudepositionofhurricane h i attime t fortheleadtime ˝ and y i;t + ˝ =[ y i;t + ˝ 1 ;y i;t + ˝ 2 ] bethecorrespondingtruelocation.Thesquaredgeographicdistance betweenthepredictedandtruelocations, d [ z i;t;˝ ; y i;t + ˝ ] 2 ,canbeestimatedasfollows: R 2 e ( z i;t;˝ 1 y i;t + ˝ 1 ) 2 +( z i;t;˝ 2 y i;t + ˝ 2 ) 2 cos 2 y i;t + ˝ 1 ; where R e istheradiusoftheearth.As R e isaconstantthatcanbeabsorbedintotheregular- izertermofanobjectivefunction,wecanset R e =1 tosimplifythenotation.Furthermore, 34 bytransformingthecoordinatesofthelocationto ~ y i;t + ˝ =[ y i;t + ˝ 1 ;y i;t + ˝ 2 cos y i;t + ˝ 1 ] ~ z i;t;˝ =[ z i;t;˝ 1 ;z i;t;˝ 2 cos y i;t + ˝ 1 ] thegeographicdistancecanbefurthersimpli˝edasfollows: d ( z i;t;˝ ; y i;t + ˝ ) 2 = k ~ z i;t;˝ ~ y i;t + ˝ k 2 whichisan ` 2 lossonthetransformedcoordinates. 3.3.3 OMuLeT Framework Ourproposedframework,named OMuLeT ,learnstheoptimalweightsfortheensemblemem- bersinanonlinefashion.Let M bethetotalnumberofensemblemembersand m i bethe numberofensemblememberswhoseforecastsareavailableforhurricane h i .Assumewe haveextractedthesubvector w i whoseelementsconsistoftheweightsofthe m i selected membersandrenormalizetheweightstosumupto1.Topredictthelocationofhurricane h i attime t + ˝ ,weusethefollowinglinearestimator, z i;t;˝ = X i;t;˝ w i;t;˝ ,where X i;t;˝ 2 R 2 m i , w i;t;˝ 2 R m i ,and 1 T m i w i;t;˝ =1 .Inaddition,allweightsshouldbenon-negativeaccording Theorem1,wheretheweightisassumedtobe 1 ˙ 2 .Tosimplifytheproblem,werelaxitand removetheweightnon-negativeconstraint.Instead,weprojecttheweighttoanon-negative weightspace.Thedetailsisdiscussedinthefollowingsection. OMuLeTassumestheweightvector w i;t;˝ canbedecomposedintothesumofthefollow- ingthreefactors: w i;t;˝ = o i + u i;t + v i;t;˝ (3.6) where 1 T m i o i =1 ; 1 T m i u i;t =0 ; 1 T m i v i;t;˝ =0 The˝rstterm, o i ,isa globalweight factorthatretainstheweightinformationfromthe analysisofpasthurricanes.Thesecondterm, u i;t ,isa hurricane-speci˝c factorthatmodi˝es 35 Figure3.4:Proposedonlinemulti-leadtimetrajectoryforecastingframework. theglobalweighttobetter˝tthepredictionforthecurrenthurricane.Thethirdterm, v i;t;˝ , isa leadtimeadjustment factortoimprovethemodelpredictionatleadtime ˝ . TheoverallframeworkisshowninFigure3.4.Givenahurricane h i ,weextractthe subvector w i from w andnormalizeittohaveunitsumbeforeassigningitastheinitialvalue for o i .Both u i; 0 and v i; 0 ;˝ areinitializedtoavectorofallzeros, 0 m i .Asnewobservation databecomeavailable,wewillupdate u i;t and v i;t;˝ accordinglyusingtheonlineapproach describedinSection3.3.3.1.Notethattheglobalweight o i isnotupdatedthroughoutthe onlineupdate.Afterprocessingalltheobservationdataforhurricane h i , o i isusedtoderive thenewweight w i asfollows: w i = o i + ˆ u i; i : (3.7) where i denotesthetrajectorylengthfor h i .Thehyperparameter ˆ controlsthetradeo˙ betweenbiasing w i withthelearnedweightsfromcurrentandpasthurricanes.Finally,the weightsin w i arerenormalizedbasedontheformulagiveninCorollary1beforereplacing theiroriginalvaluesin w . 36 3.3.3.1ObjectiveFunction Theonlinelearningprocessfortrajectory i isillustratedinthebottomdiagramofFig- ure3.4.Attime t ,whenthetruelocation y i;t isknown,itcanbeusedtoverifythe followingsetofearlierforecasts, X i;t = f X i;t 1 ; 1 , X i;t 2 ; 2 , , X i;t T;T g .Let W i;t 1 = [ w i;t 1 ; 1 ; w i;t 1 ; 2 ; ; w i;t 1 ;T ] denotetheweightmatrixforallleadtimesattime t 1 .Us- ing y i;t toupdatetheweightmatrix W i;t 1 aloneisinsu˚cientassomeoftheweightvectors in W i;t 1 arealsooutdatedsincetheyignorethetruevaluesfor X i;t .Instead,ourproposed frameworkemploysabacktrackingandrestartstrategyinitsonlinelearningprocess.Specif- ically,since W i;t 1 wasupdatedfrom W i;t 2 ,whichinturn,wasupdatedfrom W i;t 3 ,and soon,werestarttheweightupdateprocedurefromtime t T andupdate w i;t T;T toaccount forthenewgroundtruthvalueavailablefor X i;t T;T .Theupdatedweightmatrix W i;t T is thenusedtoupdate W i;t T +1 ,takingintoaccountthenewgroundtruthvalueavailablefor X i;t T +1 ;T 1 .Thisprocedureisrepeateduntilthenewweightmatrix W i;t isobtained. Theweightsareupdatedbasedontheobjectivefunctionbelow: min u i;t ; f v i;t;˝ g 1 2 T X ˝ =1 i;t;˝ ˝ d z i;t;˝ ; y i;t + ˝ 2 + ! 2 T 1 X ˝ =1 w i;t;˝ +1 w i;t;˝ 2 + 2 u i;t u i;t 1 2 + 2 T X ˝ =1 v i;t;˝ v i;t 1 ;˝ 2 + 2 T X ˝ =1 v i;t;˝ 2 s.t. 8 t;˝ : 1 T m i u i;t =0 ; 1 T m i v i;t;˝ =0 ; (3.8) where d [ ] isthegeographicdistancefunctiondescribedinSection3.3.2while i;t;˝ isdelta functionwhosevalueis1if y i;t + ˝ isknownattime t and0otherwise.The˝rsttermin theobjectivefunctionrepresentstheforecasterror.Thehyperparameter determinesthe relativeimportanceofmakingaccurateforecastsatdi˙erentleadtimes ˝ .Thesecondterm ensuressmoothnessinthemodelparametersfordi˙erentleadtimeswhereasthethirdand fourthtermsaredesignedtoensurethehurricane-speci˝cfactor u i;t andleadtimeadjustment 37 factor v i;t donotchangerapidlyfromtheirpreviousvaluesattime t 1 .Thelasttermin theobjectivefunctionimposesasparsityconstraintontheleadtimeadjustmentfactor. TheLagrangeformulationfortheoptimizationproblemis L = 1 2 T X ˝ =1 i;t;˝ ˝ ~ X i;t;˝ w i;t;˝ ~ y i;t + ˝ 2 2 + 1 2 Tr h V i;t T ( ! L + I ) V i;t i + 2 u i;t u i;t 1 2 + 2 V i;t V i;t 1 2 F 1 T m i u i;t T X ˝ =1 ˝ 1 T m i v i;t;˝ (3.9) where V i;t =[ v i;t; 1 ; v i;t; 2 ;:::; v i;t;T ] and L isamatrixde˝nedasfollows L i ; j = 8 > > > > > > > > > > < > > > > > > > > > > : 1 ; if i = j =1 or i = j = T 2 ; if i = j 6 =1 and i = j 6 = T 1 ; if i = j +1 or i = j 1 0 ; otherwise Tosolvethefunction,takingthepartialderivativeof L andsettingittozero.Then,we canbuiltanequationasfollows @ L @ u i;t = T X ˝ =1 i;t;˝ ˝ ~ X i;t;˝ T ~ X i;t;˝ w i;t;˝ ~ y i;t + ˝ + u i;t u i;t 1 1 d i = T X ˝ =1 i;t;˝ ˝ ~ X i;t;˝ T ~ X i;t;˝ ( w i;t 1 ;˝ + u i;t + v i;t;˝ ) ~ y i;t + ˝ + u i;t 1 d i = ~ M i;t + I d i u i;t + T X ˝ =1 i;t;˝ M i;t;˝ v i;t;˝ + ~ C i;t 1 d i = 0 d i (3.10) @ L @ v i;t; ^ ˝ = i;t; ^ ˝ ^ ˝ ~ X i;t; ^ ˝ T ~ X i;t;˝ w i;t; ^ ˝ ~ y i;t +^ ˝ + V i;t Q ˝ + v i;t; ^ ˝ v i;t 1 ; ^ ˝ ^ ˝ 1 d i = i;t; ^ ˝ ^ ˝ ~ X i;t; ^ ˝ T ~ X i;t; ^ ˝ ( w i;t 1 ; ^ ˝ + u i;t + v i t; ^ ˝ ) ~ y i;t +^ ˝ + V i;t Q ˝ + v i;t; ^ ˝ ^ ˝ 1 d i = i;t; ^ ˝ M i t; ^ ˝ u i;t + i;t; ^ ˝ M i t; ^ ˝ + I d i v i t; ^ ˝ + V i;t Q ˝ + i;t; ^ ˝ C i t; ^ ˝ ^ ˝ 1 d i = 0 d i (3.11) 38 where [ V i;t Q ] ˝ isthe ˝ th columnof [ V i;t Q ] .Fromthede˝nition,wehave V i;t Q ˝ = 8 > > > > > > < > > > > > > : ( ! + ) v i;t; 1 ! v i;t; 2 if ˝ =1 (2 ! + ) v i;t;˝ ! v i;t;˝ 1 ! v i;t;˝ +1 if 1 <˝ > > > > > > > > > < > > > > > > > > > > : ( ! + v i;t; 1 ! v i;t; 2 +( ! + ) v i;t 1 ; 1 ! v i;t 1 ; 2 if ˝ =1 (2 ! + v i;t;˝ ! v i;t;˝ 1 ! v i;t;˝ +1 +(2 ! + ) v i;t 1 ;˝ ! v i;t 1 ;˝ 1 ! v i;t 1 ;˝ +1 if 1 <˝ > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > : ~ C i;t if j =1 i;t;j 1 C i;t;j 1 ( ! + ) v i;t 1 ;j 1 + ! v i;t 1 ;j if j =2 i;t;j 1 C i;t;j 1 (2 ! + ) v i;t 1 ;j 1 + ! v i;t 1 ;j 2 + ! v i;t 1 ;j if 2 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > : ~ M i;t + I m i if j =1 ;k =1 i t;j M i t;j if j> 1 ;k =1 i t;k M i t;k if j =1 ;k> 1 ! I m i if 2 j T;k = j +1 ! I m i if 2 k T;j = k +1 i;t; 1 M i;t; 1 +( ! + + ) I m i if j =2 ;k =2 i;t;T M i;t;T +( ! + + ) I m i if j = T +1 ;k = T +1 i;t;T M i;t;T +(2 ! + + ) I m i if j = k; 2 > < > > : g (~ y t;˝ ) ; if ~ y t;˝ isavailable g (~ z t;˝ ) ; otherwise ~ ˘ t;˝ = 8 > > < > > : ~ g ( y t;˝ ) ; if y t;˝ isavailable ~ g ( z t;˝ ) ; otherwise (5.2) where L tra correspondstothelossfunctionfortrajectorypredictionwhile L int isthelossfor intensityforecasting. and ~ arehyperparametersassociatedwiththehurricanetrajectory predictiontasks,respectively.Thequantilehyperparameters ˘ and ~ ˘ areneededtobiasthe modeltowardspredictingmoreaccuratelyhurricanesthatareclosetothecoastlineorthose withhighcategories.Unliketraditionalquantileloss,thequantilehyperparametershereare notconstantsbutareautomaticallyupdatedinanonlinefashion.Speci˝cally,thequantile losstermsareupdatedtore˛ectthesigni˝cantthreatofahurricaneusingthefunctions g ( ) and ~ g ( ) .Recallthat y t;˝ isthetruehurricanelocationand ~ y t;˝ isthetrueintensityattime 86 t forleadtime ˝ .However,since y t;˝ and ~ y t;˝ maynotavailableduringmodelupdate,we usethemodelpredictions z t;˝ and ~ z t;˝ toestimatethemandcalculatetheircorresponding quantilehyperparameters.DetailsofthequantilefunctionsaregiveninSection5.3.1.3. 5.3.1.1 L tra withDistanceQuantileRegression Ashurricanescancauseseveredamagesincivilianpopulatedareas,itisimperativeto accuratelyidentifyhurricanesthatareapproachinglandfall.Therefore,wewouldliketo biasthemodeltowardslearninghurricaneswithpotentialtostriketheland.Thiscanbe donebyencouraginghurricaneforecaststhataremorelikelytomakelandfall.Thepossibility ofhurricanelandfallcanbemeasuredbythedistancebetweenitscurrentlocationtothe nearestcoastline.Speci˝cally,weintroduceadistancelossdecompositiontoevaluatethe modelperformancebytakingintoaccountitspredicteddistancetothecoastline.Forevery groundtruthlocation y ,wecan˝nditscorrespondingprojectedpoint p tothenearest coastline.Aunitnormalvectortothecoastlinecanbecalculatedas n = p y k p y k .Givena predictedlocation z ,itsdistancelossisde˝nedas d = z y .Thedistancelossvector d can bedecomposedintoaparallel, d k = d n ,andaperpendicularcomponent, d ? = d d k , asshowninFigure5.3.Withthede˝nitionofdistancelossdecomposition,thesquareloss 1 2 k z y k 2 2 canbeexpressedequivalentlyasfollows L tra = 1 2 2 + 2 +( z y ) 2 ? s.t. ( z y ) k = ; 0 ; 0 (5.3) Inordertoencouragepredictionswithshorterdistancestothecoastline,Eqn.(5.3)can befurtherextendedtoaccommodatethequantilelossinEqn.(5.4).NotethatEqn.(5.4) isequivalenttoEqn.(5.3)bysettingthehyperparameter ˘ to0.5. 87 Figure5.3:Decompositionofthedistancelossvector.Thegreencircleisthetruelocation andtheredstarisitsprojectednearestcoastline.Theunitvector n pointsinthedirection towardstheland.Thebluecircleisthepredictedlocation.Thevectordirectedfromthe greencircletothebluecircleisthedistancelossvector d ,whichcanbedecomposedintoa parallel d k andaperpendicularcomponent d ? . L tra =(1 ˘ ) 2 + ˘ 2 + 1 2 ( z y ) 2 ? s.t. ( z y ) k = ; 0 ; 0 (5.4) Weassumethattheweightvectors w t;˝ inEqn.(5.1)canbedecomposedintothe followingfactors: w t;˝ = u t + v t;˝ s.t. 1 T m t u t =1 ; 1 T m t v t;˝ =0 (5.5) where u t isthesharedweightvectorsforallleadtimeswhile v t;˝ isadjustmenttothe weightvectorsassociatedwiththedi˙erentleadtimes ˝ .Forbrevity,wedenote W t = [ w t; 1 ; w t; 2 ; ; w t;T ] astheweightmatrixforall T leadtimesattimestep t .Toextendthe 88 precedingformulationtoanonlinemulti-leadtimeforecastingsetting,theweightmatrix W t isupdatedbyminimizingthefollowingobjectivefunctionateachtimestep t : L tra = T X ˝ =1 t;˝ ˝ (1 ˘ ) t;˝ 2 + ˘ t;˝ 2 + 1 2 ( z t;˝ y t;˝ ) 2 ? + ! 2 T 1 X ˝ =1 w t;˝ +1 w t;˝ 2 + 2 u t u t 1 2 + 2 T X ˝ =1 v t;˝ v t 1 ;˝ 2 + 2 T X ˝ =1 v t;˝ 2 s.t. 8 t;˝ : 1 T m t u t =1 ; 1 T m t v t;˝ =0 ; ( z t;˝ y t;˝ ) k = t;˝ t;˝ ; t;˝ 0 ; t;˝ 0 (5.6) where t;˝ isanindicatorfunctionwhosevalueis1if X t;˝ and y t;˝ valuesarebothavailable; otherwiseitsvalueis0.Intheobjectivefunction,the˝rsttermrepresentstheforecast errorsforalltheleadtimes.Thehyperparameter ˘ determinestheimportanceofmaking locationpredictionswithshorterdistancetocoastlines.Thehyperparameter decidesthe relativeimportanceofmakingaccuratepredictionsatdi˙erentleadtimes.Thesecondterm ensuresthattheestimatedmodelparameterswouldvarysmoothlyatdi˙erentleadtimes, thuspreservingthetemporalautocorrelationofthepredictedintensities.Thethirdand fourthtermsguaranteethatthesharedweightvector u t andleadtimeadjustmentweight vectors v t;˝ areclosetotheirvaluesatprevioustimestep.Thelasttermpenalizeslarge valuesintheleadtimeadjustmentweightvectors. !;; arehyperparametersdetermine therelativeimportanceofeachtermintheobjectivefunction.Ifwechoosealarge ˘ ˇ 1 , thenthedistancelosscanbeignoredif ( z t;˝ y t;˝ ) k > 0 .Itmeansthat L tra willgivehigh weightsonthemodelswithpredictionswithshorterdistancetothecoastline. 5.3.1.2 L int withQuantileOrdinalRegression Ourgoalistogenerateaccuratelongrangepredictionsofhurricanereal-valuedintensity andcategory.Here,weusethe -insensitivelosstomeasuretheintensitypredictionerror. 89 Comparedtomeansquareloss,the -insensitivelossismorerobustasitprovidesamargin oftolerance [28,5]whenlearningtheregressionfunction. L int = + s.t. z y + z y 0 ; 0 (5.7) Second,inordertocommunicatetheseverityofanimpendinghurricanetothepublic, accuratepredictionofitscategoryisoftenmoreimportantthanthewindspeeditself.As notedinSection4.2,intensitypredictionaloneisinsu˚cientbecauseitignoreswhether thepredictionerrora˙ectsitspredictioncategory.Therefore,weintroduceanordinalloss toensurethemodelisfocusedmoreondatapointslocatedneartheboundarybetween twoordinalcategories.Analogoustothelossfunctionde˝nedforsupportvectorordinal regression[17],theordinallossfunctionisde˝nedasfollows: L int = + s.t. z b y 1+ ; z b y 1 1 ; 0 ; 0 (5.8) OurintensitypredictionlosscanbemeasuredbycombiningEqns.(5.7)and(5.8)as follows.Inaddition,topenalizemodelsthatincorrectlypredicthighcategoryhurricanes,it canbeextendedtoaccommodatethequantilelossas (1 ˘ ) + ˘ . L int =(1 ˘ ) + ˘ s.t. z b ^ y 1+ z b ^ y 1 1 z y + z y 0 ; 0 (5.9) 90 Similartothetrajectorymodel,weassumethattheintensityweightvector ~ w t;˝ canbe decomposedintothefollowingfactors: ~ w t;˝ = ~ u t + ~ v t;˝ s.t. 1 T ~ m t ~ u t =1 ; 1 T ~ m t ~ v t;˝ =0 (5.10) where ~ u t isthesharedweightvectorsforallleadtimeswhile ~ v t;˝ isadjustmenttothe weightvectorsassociatedwiththedi˙erentleadtimes ˝ .Forbrevity,wedenote ~ W t = [ ~ w t; 1 ; ~ w t; 2 ; ; ~ w t;T ] astheweightmatrixforall T leadtimesattimestep t . Puttingittogether,theweightmatrix ~ W t forintensitypredictionistrainedtominimize thefollowingobjectionfunction: L int = 1 2 T X ˝ =1 ~ t;˝ ~ ˝ (1 ~ ˘ ) t;˝ + ~ ˘ t;˝ + ~ ! 2 T 1 X ˝ =1 ~ w t;˝ +1 ~ w t;˝ 2 + ~ 2 ~ u t ~ u t 1 2 + ~ 2 T X ˝ =1 ~ v t;˝ ~ v t 1 ;˝ 2 + ~ 2 T X ˝ =1 ~ v t;˝ 2 s.t. 8 t;˝ : 1 T ~ m t ~ u t =1 ; 1 T ~ m t ~ v t;˝ =0 ; ~ z t;˝ b ^ y t;˝ 1+ t;˝ ~ z t;˝ b ^ y t;˝ 1 1 t;˝ ~ z t;˝ ~ y t;˝ + t;˝ ~ z t;˝ ~ y t;˝ t;˝ t;˝ 0 ; t;˝ 0 (5.11) where ~ t;˝ isanindicatorfunctionwhosevalueis1if ~ x t;˝ and ~ y t;˝ valuesarebothavailable; otherwiseitsvalueis0.Intheobjectivefunction,the˝rsttermrepresentstheforecasterrors foralltheleadtimes.Thehyperparameter ~ ˘ determinestheimportanceofmakingaccurate predictionsforhighcategoryhurricanes.Themeaningsofothertermsintheobjective functionaresimilartoEquation5.6. 91 5.3.1.3QuantileHyperparameterUpdate Asdescribedintheprevioussection,thequantilehyperparametersareupdatedinanonline fashion.Ingeneral,wewantthequantilehyperparameterfortrajectorypredictiontobelarge ifthehurricanecategoryishigh;andthequantilehyperparameterforintensityprediction tobelargeifthehurricanelocationisclosetocoastline.Inourframework,weuseasigmoid function ˙ ( x )=1 = (1+ e x ) togeneratethequantilehyperparameters. For L tra ,thehyperparameter ˘ t;˝ iscalculatedfromthefunction g ( x ) de˝nedinEqn. (5.2)asfollows: g ( x )= 8 > > < > > : 0 : 5 ; for x< ˙ ([ x ] =c ) ; otherwise (5.12) where x isthegroundtruthorpredictedintensitywithcurrentweightvector, isahy- perparameterthatdecidewhenquantilelossisnotneeded, c isthehyperparameterthat determinesthemagnitudeofquantilehyperparameters.Whenthehurricaneintensityis low, g ( x )=0 : 5 ,andthus,the˝rstlosstermin L tra reducestothesquaredlossfunction. Forhighintensityhurricanes, g ( x ) ˇ 1 .Inthiscase,theframeworkgiveshigherweightsfor modelsthatpredictlocationswithshorterdistancetothecoastline. For L int ,thehyperparameter ~ ˘ t;˝ iscalculatedfromthefunction ~ g ( ) de˝nedinEqn. (5.2)asfollows: ~ g ( x )= 8 > > < > > : 0 : 5 ; for d coast ( x ) > ~ ˙ ([ ~ d coast ( x )] = ~ c ) ; otherwise (5.13) where x iseitherthegroundtruthorpredictedlocationforthecurrentweightvector, d coast ( ) isafunctionthatcomputesdistancetocoastline, ~ isahyperparameterthatdetermineswhen thequantilelossisnotneeded, ~ c isthehyperparameterthatdeterminesthemagnitudeof quantilehyperparameters.Whenthehurricaneisfarfromthecoastline,wehave g ( x )=0 : 5 . The˝rstlosstermof L int isthusreducedto ` 1 loss.Whenthehurricaneisveryclosethe land, g ( x ) ˇ 1 .Inthiscase,theframeworkgiveshigherweightstomodelsthatpredict higherintensities. 92 Figure5.4:Proposed JOHAN framework. Errorpropagationisachallengeformulti-leadtimeforecasting.Itisinsu˚cienttoup- date W t and ~ W t from W t 1 and ~ W t 1 aloneasthepreviousweightsareoutdatedwithout usingthenewobservation.Toaddressthisproblem,weapplythebacktrackingandrestart strategydescribedinChapter3.Theoverallframeworkwithbacktrackingandrestartstrat- egyisillustratedinFigure5.4.Thepseudocodefortheproposedframeworkisdescribedin Algorithm3.Ateachtimestep t ,thenewlyavailablegroundtruthvaluecanbedetermined as f y t T;T ; y t T +1 ;T 1 ;:::; y t 1 ; 1 g fortrajectoryforecastsand f ~ y t T;T ; ~ y t T +1 ;T 1 ;:::; ~ y t 1 ; 1 g forintensityforecasts.Therefore,tomakeallthepreviouslearnedweightvectorsuptodate, weupdatedtheweightvectorsfromtimestep t T until t 1 withquantilehyperparam- etersgeneratedbyEqn.(5.12)and(5.13).Then,themulti-leadtimepredictionsforboth trajectoryandintensitycanbeproducedgiventheensembleofmodeloutputsandupdated modelweightvectors. 5.4Experiments Weperformedexperimentsusingreal-worldhurricanetrajectoryandintensitydatafrom varioussources.Thegroundtruthhurricanetrajectoryandintensitydataalongwiththe 93 Input: ; ~ ;˘;˘ Output: Modelparameters w ; ~ w andforecasts z ; ~ z Initialize : w = 1 m =m; ~ w = 1 m =m ; for t=1,2,...,N do if t isthe˝rsttimestepofatrajectory then Extract u t from w , ~ u t from ~ w Normalize: u t u t = j u t j ; v t;˝ 0 ; ~ u t ~ u t = j ~ u t j ; ~ v t;˝ 0 end Observe y t ; ~ y t /*Backtrackingandrestartstep*/ for t 0 = t T;t T +1 ;:::;t 1 do Trajectorypredictions z t 0 ;˝ = f t 0 ;˝ ( X t;˝ )= X t 0 ;˝ w t 0 ;˝ Intensitypredictions ~ z t 0 ;˝ = ~ f t;˝ ( ~ x t 0 ;˝ )= ~ x t 0 ;˝ ~ w t 0 ;˝ Calculatehyperparameter ˘ t;˝ and ~ ˘ t;˝ usingEq.5.12and5.13 Update u t 0 +1 ; v t 0 +1 ;˝ byminimizing L tra Update ~ u t 0 +1 ; ~ v t 0 +1 ;˝ byminimizing L int end /*Predictionstep*/ for ˝ =1 ; 2 ; ;T do Compute w t;˝ and ~ w t;˝ forallleadtimes Trajectorypredictions z t;˝ = f t;˝ ( X t;˝ )= X t;˝ w t;˝ Intensitypredictions ~ z t;˝ = ~ f t;˝ ( ~ x t;˝ )= ~ x t;˝ ~ w t;˝ end if t isthelasttimestepofatrajectory then Substitute u t backintothefullvector w Substitute ~ u t backintothefullvector ~ w end end Algorithm3: Proposed JOHAN framework o˚cialforecastsareobtainedfromtheNationalHurricaneCenter(NHC)website 1 ,while theensemblememberforecastsareobtainedfromtheHurricaneForecastModelOutput websiteatUniversityofWisconsin-Milwaukee 2 .Wecollected6-hourlyhurricanetrajectory andintensitydatafromtheyear2012to2020,whichcontains336tropicalcyclones.Each tropicalcyclonehasanaveragelengthof21.9timesteps(datapoints),whichgivesatotalof 7364datapoints.Thereare27trajectoryforecastmodelsand21intensityforecastmodels usedinourexperiments,whichareasubsetofthemodelsusedbyNHCinthepreparation 1 https://www.nhc.noaa.gov 2 http://derecho.math.uwm.edu/models 94 oftheiro˚cialforecasts.Thedatafrom2012to2017(208tropicalcyclones)areusedfor trainingandvalidation,whilethosefrom2018to2020(128tropicalcyclones)areusedfor testing. 5.4.1BaselineandEvaluationMetrics Wecompared JOHAN againstthefollowingbaselinemethods: 1. Ensemblemean :Thismethodcomputesthemeanvalueoverallensemblemembers foreachgivenleadtime. 2. Persistence :Thismethodassumesthattheintensityandmovingspeedofthehurri- caneatthenexttimestepisthesameascurrenttimestep. 3. Passive-Aggressive(PA) [21]:Thisisawell-knownonlineregressionalgorithm. 4. ORION [84]:Thisisanonlinemulti-tasklearningalgorithmforensembleforecasting. 5. OMuLeT :ThisistheonlinelearningalgorithmdescribedintheChapter3fortra- jectoryprediction.Itcanbealsoappliedtotheintensitypredictionaswellusingthe ensemblememberforecastsaspredictors. 6. NHC :Thiscorrespondstotheo˚cialforecastsgeneratedbyNHC,whichisthegold standard. Forafaircomparison,thebaselinemethods(PA,ORION,OMuLeT,andJOHAN)also applythebacktrackingandrestartstrategytoupdatetheirweights.Hyperparametersofthe methodsweretunedbyminimizingthefollowingmeandistanceerror(MDE)fortrajectory forecastsandmacro-averagedmeanabsoluteerror(MAE)forintensityforecastsonthe validationset. MDE = 1 N X t;˝ dis z t;˝ ; y t;˝ (5.14) 95 Figure5.5:Distancetocoastlineforhurricanesfromyear2012to2017atdi˙erenttime beforelandfall. macro-MAE = 1 6 5 X i =0 0 @ 1 N i X ^ y t;˝ = i ^ z t;˝ ^ y t;˝ 1 A (5.15) where N istotalnumberoftrajectoryforecastsinthevalidationset, N i isthenumberof datapointsofcategoryiinthevalidationset.WeuseMDEonthetrajectorytestdatato evaluatethelocationpredictionerror,andMAEontheintensitytestdatatoevaluatethe errorinbothreal-andordinal-valuedpredictions.WealsouseF1-scoretoevaluateaccuracy oftheordinalcategorypredictions. For JOHAN framework,thehyperparameters and ~ aretunedwiththe˝xedquantile hyperparameters ˘ = ~ ˘ =0 : 5 .Thethreshold forthefunction g ( ) issetto34knots (kt),whichisthelowerboundforintensityofatropicalstorm.Asthereareveryfew timestepswithintensitymorethan64ktthehyperparameter c iscalculatedbysolving g ( x )= ˙ ([ x ] =c )=0 : 9 with x =64 kt.Forthefunction ~ g ( ) ,Figure5.5showsthe distancetocoastlineforlandfallhurricanesatdi˙erenthoursbeforelandfall.Thethreshold ~ issetto300nauticalmiles(nmi)wherethehurricanesareunlikelytostrikethelandin 48hours.Thehyperparameter ~ c iscalculatedbysolving ~ g ( x )= ˙ ([ ~ d coast ( x )] = ~ c )=0 : 9 96 with x =200 nmiwhichisthedistancefromthecoastlineforhurricanesthatmightreach landfallafter24hours. 5.4.2ExperimentalResults Table5.2summarizesthetrajectoryandintensityforecasterrorsof JOHAN andotherbaseline methodswithleadtimesfrom12hoursto48hours.Fortrajectoryprediction,thereare severalinterestingconclusionsthatcanbedrawn.First,theperformanceofensemblemean iscomparabletotheNHCo˚cialforecast,whichvalidatestheadvantageofusinganensemble ofphysicalmodeloutputsaspredictors.Second,persistenceperformsmuchworsethanother baselines.Thisisreasonablesincepersistenceassumesthatthemovingspeedofhurricane isunchanged.Third, OMuLeT and JOHAN generatecomparableresultsandbothoutperform otherbaselines,includingtheo˚cialforecastsfromNHC.Thisisnotsurprisingasboth methodsemploysimilarstrategiestoupdatetheirtrajectorypredictionmodels.However, aswillbeshownbelow, OMuLeT isinferiorto JOHAN intermsofitstrajectoryprediction errorforhurricaneswithin200nmifromthecoastline. Forintensityforecasts,theperformanceofensemblemeanissigni˝cantlyworsethan NHCasshowninTable5.2.Thisisnotsurprisingasintensityforecastingisstillavery challengingproblemforthedynamicalandstatisticalmodelsintheensemble.Second,both persistenceandPAperformpoorly,muchmoresothanothermethods.Fourth, JOHAN generallyhassigni˝cantlybetterperformanceespeciallyatlongerleadtimeswithresults comparabletotheo˚cialforecastsofNHC.Thisisimpressiveconsideringthefactthatthe ensemblemembersusedin JOHAN isonlyasubsetofthemodelsusedbyNHCtogenerate theiro˚cialforecasts. JOHAN isdesignedtomaximallyidentifythreateninghurricaneswithpotentialtostrike landfall.Table5.3summarizesthetrajectoryandintensityforecasterrorsforhurricanes within200nmitocoastlinewithanintensityofatleast64ktfordi˙erentprediction methodsatvaryingleadtimes(from12to48hours).Therelativeperformanceofallthe 97 Trajectoryerror(innmi) Intensityerror(inkt) Method 12 24 36 48 12 24 36 48 EnsembleMean 23.30 36.34 50.22 65.03 6.742 8.692 9.899 11.036 Persistence 34.84 88.89 155.87 229.63 7.717 13.797 18.246 22.102 PA 23.30 36.34 50.23 64.80 6.547 10.563 13.294 15.268 ORION 23.37 36.36 50.21 65.00 5.792 7.941 9.388 10.551 OMuLeT 22.20 34.94 48.07 62.10 5.632 7.923 9.285 10.513 JOHAN 22.25 35.01 48.13 62.08 5.732 7.700 8.948 10.026 NHC 24.59 38.49 52.17 65.74 5.019 7.730 8.959 10.140 Table5.2:Trajectoryandintensityforecasterrorsfordi˙erentmethodsatvaryingleadtimes from12to48hours. Trajectoryerror(innmi) Intensityerror(inkt) Method 12 24 36 48 12 24 36 48 EnsembleMean 15.80 28.47 41.21 52.09 13.274 17.325 20.246 20.382 Persistence 34.28 87.62 159.38 228.91 13.121 22.547 29.194 32.762 PA 15.81 28.48 41.22 51.98 8.765 16.042 24.275 24.656 ORION 16.02 28.61 41.29 52.15 8.483 13.171 16.806 17.555 OMuLeT 15.33 28.28 39.65 49.67 9.064 14.435 17.562 18.317 JOHAN 15.28 28.15 39.28 49.06 8.963 13.367 16.270 16.554 NHC 16.69 29.47 42.83 54.07 7.962 13.585 16.097 17.587 Table5.3:Trajectoryandintensityforecasterrorsforhurricaneswithin200nmitocoastline withintensityatleast64ktfordi˙erentmethodsatvaryingleadtimesfrom12to48hours. baselinemethodsissimilartoTable5.2.Thetrajectorypredictionof JOHAN outperformsall otherbaselinesfornearlandhurricanes.Thissuggeststhat JOHAN iscapableofutilizingthe relationshipbetweenhighintensityhurricanesanddistancetothecoastlinetoimproveits prediction.Forintensitypredictions, JOHAN stillmaintainsthebestpredictiveperformance atlongerleadtimes. Inaddition,wealsoevaluatedthehurricanecategorypredictionforthedi˙erentmethods bycomputingtheirF1-scores.TheresultsareshowninTable5.4.First,ensemblemeanper- formspoorlyforhighcategorypredictions,whichisnotsurprisingasthedi˙erentensemble membersarenotequallyskillful.Second,theoverallmacro-F1performanceofpersistence issimilartoensemblemeanandmuchworsethanotherbaselines.Third,PAisbetterthan ensemblemeanbutstillworsethanbothORIONandOMuLeT.Themacro-F1scoreof JOHAN isslightlyhigherthanORIONandOMuLeT,though JOHAN hasbetterperformance 98 F1-score Category macro-F1 0 1 2 3 4 5 EnsembleMean 0.390 0.917 0.449 0.309 0.305 0.168 0.190 Persistence 0.396 0.859 0.327 0.247 0.234 0.330 0.378 PA 0.453 0.912 0.487 0.323 0.321 0.362 0.313 ORION 0.491 0.922 0.530 0.377 0.349 0.418 0.350 OMuLeT 0.494 0.923 0.502 0.367 0.386 0.380 0.404 JOHAN 0.499 0.922 0.499 0.357 0.385 0.380 0.450 NHC 0.540 0.924 0.554 0.411 0.390 0.462 0.502 Table5.4:ComparisonofF1-score,precisionandrecallforvarioushurricaneintensityfore- castingmethodsatdi˙erentcategories. F1-score Category macro-F1 0 1 2 3 4 5 EnsembleMean 0.378 0.919 0.414 0.234 0.318 0.188 0.195 Persistence 0.394 0.854 0.309 0.182 0.236 0.389 0.392 PA 0.454 0.899 0.412 0.281 0.298 0.395 0.436 ORION 0.505 0.927 0.509 0.330 0.375 0.431 0.459 OMuLeT 0.493 0.923 0.465 0.290 0.402 0.435 0.445 JOHAN 0.496 0.923 0.462 0.274 0.402 0.447 0.467 NHC 0.516 0.920 0.511 0.328 0.362 0.442 0.534 Table5.5:ComparisonofF1-score,precisionandrecallforhurricaneswithin200nmito coastlinewithvarioushurricaneintensityforecastingmethodsatdi˙erentcategories. forthehighercategories.Table5.5summarizestheF1-scoresforhurricaneswithin200nmi fromthecoastline,whichclearlydemonstratesthesuperiorityof JOHAN comparedtoother baselinesforhighcategoryhurricanes. 5.4.3AblationStudy Akeyaspectof JOHAN isitsabilitytoupdatethequantilehyperparameterinanonline fashion.Toinvestigatetheadvantagesofutilizingavaryingquantilehyperparameter,we considertwovariationsofourframework. JOHAN-NQ removesthequantilelossforthe˝rst terminEqn.(5.6)and(5.11)andreducedthemtosquaredlossand ` 1 loss. JOHAN-Q uses a˝xedquantilehyperparameterforalltheweightupdates. Table5.6summarizesthetrajectoryandintensityforecasterrorsforthetwovariations 99 of JOHAN frameworkwhileTable5.7summarizestheircorrespondingforecasterrorsfornear landhighintensityhurricanes.Itisclearthatincreasingthe˝xedquantilehyperparameters wouldleadtobetterperformancefornearland,highintensityhurricanes(Table5.6)butat theexpenseofdecreasingoverallpredictionaccuracy(Table5.7). JOHAN ,withitsvarying quantilehyperparameter,managestomaintainconsistentlyaccuratepredictionsinboth scenarios. Trajectory(nmi) Intensity(kt) Method 12 24 36 48 12 24 36 48 JOHAN 22.25 35.01 48.13 62.08 5.732 7.700 8.948 10.026 JOHAN-NQ 22.20 34.94 48.07 62.10 5.700 7.654 8.880 9.840 JOHAN-Q( ˘ =0.6) 22.21 34.94 48.08 62.07 5.696 7.647 8.877 9.872 JOHAN-Q( ˘ =0.7) 22.23 34.94 48.07 62.06 5.704 7.659 8.897 9.939 JOHAN-Q( ˘ =0.8) 22.27 34.96 48.08 62.09 5.722 7.704 8.964 10.064 JOHAN-Q( ˘ =0.9) 22.33 35.01 48.11 62.14 5.749 7.781 9.073 10.248 Table5.6:Trajectoryandintensityforecasterrorsfordi˙erentvariationsof JOHAN . Trajectory(nmi) Intensity(kt) Method 12 24 36 48 12 24 36 48 JOHAN 15.28 28.15 39.28 49.06 8.963 13.367 16.270 16.554 JOHAN-NQ 15.33 28.28 39.65 49.67 9.176 13.642 16.791 16.854 JOHAN-Q( ˘ =0.6) 15.30 28.23 39.53 49.50 9.047 13.488 16.537 16.743 JOHAN-Q( ˘ =0.7) 15.28 28.18 39.43 49.33 8.985 13.398 16.346 16.630 JOHAN-Q( ˘ =0.8) 15.27 28.15 39.35 49.16 8.950 13.362 16.256 16.606 JOHAN-Q( ˘ =0.9) 15.27 28.14 39.29 49.00 8.986 13.412 16.256 16.671 Table5.7:Trajectoryandintensityforecasterrorsforhurricaneswithin200nmitocoastline andatleast64ktusingdi˙erentvariationsof JOHAN . 5.4.4ComparisonofModelWeights Thetime-varyingmodelweightsgeneratedby JOHAN areshowninFigure5.6fortrajectory andintensityforecasts,respectively.Despitethesharedinformationbetweenthetrajectory andintensitycomponentsoftheframework,itisclearthatthebestmodelsfortrajectory predictionarenotexactlythesameasthebestmodelsforintensityprediction.Forexample, AVNOwasfoundtobeoneofthebestmodelsfortrajectorypredictionbutitsweight 100 (a)Trajectorymodelweights (b)Intensitymodelweights Figure5.6:Trajectoryandintensitymodelweightsin JOHAN changesovertime. forintensitypredictioniscloseto0.Thisresultisalsoreportedby[29].Comparedwith hurricanetrackforecasting,intensityforecastingisstillaverychallengingproblem[11]. (a) (b) (c) (d) (e) (f) (g) (h) Figure5.7:6to48hourforecastsofHurricaneIrmafromSep.4thtoSep.5th,2017.Figure (a)to(d)showsthemulti-leadtimetrajectoryforecastsgeneratedfromdi˙erentmethods. Figure(e)to(h)demonstratethemulti-leadtimeintensitypredictionsfromdi˙erentmeth- ods.Theerrorbarsrepresenttherangeofintensitypredictionsfromtheensemblemembers. 101 5.4.5CaseStudy Figure5.7showsanexampleoftrajectoryandintensityforecastsgeneratedbythedi˙erent methodsforamajorhurricane,Irma,fromSeptember4thto5th,2017.Fortrajectory prediction,our JOHAN frameworkisclosesttothebesttrackidenti˝edbyNHC.Thehurricane intensi˝edatthebeginningoftheperiod,butneither JOHAN norotherframeworkswereable topredictitasnoneoftheensemblememberswereabletocapturetheintensi˝cation. Nevertheless,astimeprogresses, JOHAN wasabletoadaptitsweightsandits˝nalprediction getsclosetothegroundtruthintensity.NotethatPAandORIONalgorithmswereable togeneratehighintensitypredictionsoutsidetherangeoftheensemblemembersastheir modelweightsarenotconstrainedtosumupto1.However,theycaneasilyoverestimate theintensityatlatertimesteps,asshowninFigure5.7(g)and(h). 5.5Conclusions Thischapterpresentsanovelframeworkcalled JOHAN forpredictinglong-rangehurricane trajectoryandintensitysimultaneously.Theframeworkisdesignedtoaddressresearchques- tion RQ4 describedinChapter1. JOHAN employsanovelexponentially-weightedquantile lossfunctiontoimproveitsaccuracyinpredictinghighcategoryhurricaneswiththepo- tentialfornearlandfall.Experimentalresultsvalidatedthee˚cacyof JOHAN ,especiallyin termsofaccuratelypredictingnearlandfall,highcategoryhurricanes. 102 CHAPTER6 LSTMFORTRAJECTORYLOCATIONPREDICTION Long-rangetrajectorypredictionhasattractedwidespreadattentionfromresearchers.There aremanyapplicationsfortrajectorypredictionsuchasanimalmigrationprediction,vehi- cletrajectoryforecastingandhurricanetrajectoryforecasting.Thesetasksusuallyrequire forecastingmultipleleadtimesintothefuture,inwhichtheforecastsbetweenleadtimes areoftenhighlycorrelated.Researchershaddevelopedmanymachinelearningalgorithms tomodelthecorrelationbetweenmulti-leadtimes[84,82].InChapter3,Iproposedan onlinelearningapproachcalled OMuLeT ,whichcanproduceaccuratemulti-leadtimesloca- tionpredictions.However,onepotentiallimitationof OMuLeT isthatitisalinearmodel. Duetothecomplexityandnonlinearityofatmosphericsystem,thedependenciesbetween thefeaturesaswellasthemulti-leadtimeforecastscouldbenon-linear,inwhichcasethe OMuLeT frameworkmaynotbeabletolearntheme˙ectively. Aneuralnetworkisdesignedtohandlenonlinearitiesintheinputfeatures,byusing nonlinearactivationfunctions.Inrecentyears,deeplearningapproacheshavefoundsuccess inmanypredictiontasks,fromcomputervisionandnaturallanguageprocessingtohealthcare andenvironmentalsciences.Amongthesedeeplearningmodels,longshort-termmemory (LSTM)isonetypeofrecurrentneuralnetwork(RNN)thatiswidelyusedfortimeseries prediction.ManyvariationsofLSTMmodelhadbeendevelopedtohandlevarietiesoftime seriesandsequencepredictiontasks.Therehasalsobeengrowinginterestrecentlytoapply deeplearningmethodstothehurricanetrajectoryforecastingproblem[59,69,3].However, thereareseverallimitationstotheseapproaches.First,theyaremostlydesignedtogenerate short-rangeforecastsonly.Second,theyonlyutilizeshistoricalobservationdata,which maynotbesu˚cienttoovercometheerrorpropagationproblem.Forapplicationssuchas hurricaneprediction,thehistoricaldataaloneisinsu˚cienttocapturethecurrentandfuture environmentalconditionsthata˙ectitstrajectorypath.Similartotheapproachdescribedin 103 Chapter3,wewillusetheforecastsgeneratedfromanensembleofstatisticalanddynamical modelstogeneratemoreaccuratetrajectorypredictionsforhurricanes.Third,mostofthe previousdeeplearningapproachesforhurricanepredictionaredesignedinabatchlearning setting. Toaddresstheseissuesandresearchquestion RQ5 ,anovelLSTM-basedframework, called DTP ( D eep T rajectory P rediction)isproposedtoaggregatethemulti-modelensemble forecastswithatemporalattention-likemechanism.LSTMisatypeofRecurrentNeural Network(RNN)thatcane˙ectivelymodeltimeseriesdatawithlong-termdependencies. Theproposedarchitectureconsistsoftwostages.The˝rststageconsistsofasetofLSTM basedlayerscalledmodelperformancelayerstolearntheperformanceoftheindividual ensemblemembers.Thesecondstageisthepredictionlayer,whichusestheoutputfromthe previousstagetogeneratethe˝nalmulti-leadtimepredictions.Theproposedframework allowsustolearnthenonlinearrelationshipsamongtheensemblememberforecastsaswell asthetemporalautocorrelationsofthepredictions.Theproposedframeworkgeneratesits multi-stepforecastsbyutilizingtheoutputsofmulti-modelensemblemembersandtheir correspondingattentionweights.Asthe DTP algorithmistrainedinabatchmode,itcannot captureconceptdriftpresentinthedata.Toovercomethislimitation,Iextendedthe DTP frameworkto ODTP ( O nline D eep T rajectory P rediction),whichisanonlinelearning formulationtoaddresstheconceptdriftissue.Theproposedframeworkswereappliedto real-worldhurricanedatatopredictfuturetrajectorypathofthehurricaneforleadtimes upto48hours.Experimentalresultsshowedthat ODTP canachievebetterperformancethan DTP ,andgenerallyoutperformsotherbaselineapproaches. 6.1RelatedWorks Deeplearninghasbeenwidelyusedinhurricanetrajectorypredictiontasks,becauseofits abilitytoe˙ectivelymodelthecomplexnon-linearrelationships.Inordertogeneratefu- turetracks,existingmethodsusuallyusehistoricaltrajectorydata,climate/meteorological 104 dataortheoutputofphysicalmodelsasinputfeaturesoftheirpredictionmodels.[69] appliedsparseRNNwith˛exibletopologyforhurricanetrajectorypredictions.Togen- eratethepredictions,theyfoundthemostsimilarhurricanestothetargethurricaneand trainedtheirRNNmodelwithGeneticAlgorithm(GA).Alemanyetal.[3]utilizedLong Short-TermMemory(LSTM)withgriddeddatatoforecasthurricanetrajectory.These approachesareonlyinterestedin6-hourshort-rangeforecastsusinghistoricaltrajectories. Becausethehistoricaldatacannotcapturecurrentandfutureenvironmentalconditionsthat a˙ectthepathofahurricane,itsperformanceisoftenpoorandcanonlybeusedtogenerate short-rangeforecasts.Methodsusingmeteorologicaldataareusuallybasedondeeplearn- ingtechniques,suchas,thegeneralizedadversarialnetworks(GAN)[77]andconvolutional LSTM(ConvLSTM)[54].Sincethesemodelsareusuallytrainedusingcoarse-scaleimages (e.g., 0 : 5 0 : 5 ),theirpredictionerrorsarestillrelativelylarge.Methodsthatusephysical modeloutputtendtoproducemorereliablelong-rangeforecasts[29,82].Asthephysical modelstakecurrentenvironmentalconditionsasinputandsimulatefutureenvironmental conditions,theiroutputscanbeusedtogeneratereliablelong-rangepredictions. 6.2ProblemFormulation Forbrevity,wepresentthenonlineartrajectorypredictiontaskinthecontextofhurricane trajectoryforecastingproblem.Theproblemformulationandmethodologyisapplicable tootherdomainswithsimilarproperties.Considerasetofhurricanes, f h 1 ;h 2 ;:::;h C g , orderedbytheirstarttimes.Assumingthereare n i datapoints(timesteps)associated withhurricane h i ,then N = P C i =1 n i isthetotalnumberoftimestepsinthehurricane dataset.Assume T istheforecasthorizon,i.e.,maximumlead-timeoftheforecastingtask, and M isthetotalnumberofensemblememberforecasts.Let X2 R 2 M T N bethesetof trajectoryforecastsgeneratedbytheensembleofdynamical(physical)models,whereeach X t 2 R 2 M T correspondstothehurricanetrajectoryforecastsgeneratedattimestep t . Let ~ n i betheaccumulatednumberofdatapointsfromhurricane h 1 to h i ,i.e. ~ n i = P i j =1 n j . 105 Thus, fX j j ~ n i 1 > < > > : t;m ˝ ; if k t;˝;m =1 ; otherwise (6.8) Finally,themulti-leadtimepredictionsattimestep t canbecomputedasalinearcom- binationoftheensemblememberforecasts. z t;˝ = M X i =1 t;˝ i x t;˝;i (6.9) 6.3.2 ODTP Framework The DTP frameworkdescribedintheprevioussubsectionistrainedinabatchmode.Dueto conceptdrift,suchamodelcaneasilybecomeoutdatedwhenappliedtoreal-worldproblems suchashurricaneprediction.Toovercomethislimitation,the DTP frameworkisextendedto 110 (a)Modelperformancelayer (b)Predictionlayer Figure6.3:The˝gureillustratethe ODTP framework.Figure(a)showsmodelperformance layer.Figure(b)showspredictionlayer. anonlinelearningapproachcalled ODTP ,whichallowsthemodeltobecontinuouslyupdated asnewobservationdatabecomeavailable. Theproposed ODTP frameworkisshowninFigure6.3.Similartothe DTP framework, ODTP alsocontainstwolaymodelperformancelayerandthepredictionlayer.Unlike themodelperformancelayerin DTP thatemploysa˝xedsequenceoflength T totrainthe LSTMmodel, ODTP considersonlyasequenceoflength1toupdatethemodelincrementally. Furthermore,foreachgivensequenceoflength T ,thehiddenstatein DTP isinitializedto zero.Incontrast,thehiddenstateoftheLSTMcellisinheritedfromitsprevioustime step.Thisstrategyallowsthehiddenstateforeachmodeltobecontinuouslyupdatedin anonlinefashion.Inaddition,onlinelearningisappliedtoupdatethemodelto˝tthe newobservations.FollowingthestrategydescribedinChapter3,toalleviatetheerror propagationproblem,thealgorithmwillbacktracktoitsprevious T timestepsandrestart theupdatefromthetimestep t T andincrementallyupdatethemodeluntilthecurrenttime step t .Theonlinelearningwithbacktrackandrestartstrategyadoptedby ODTP framework canthushelptoadapttoconceptdriftandovercometheerrorpropagationissueinmulti- leadtimeforecastingproblems.TheoverallproposedframeworkisshowninFigure6.4,with thepseudocodegiveninAlgorithm4. 111 Figure6.4:The ODTP frameworkusingbacktrackingandrestartstrategy. Input: Hyperparameter for ODTP model M Output: Forecasts z Initialize :Pre-trainmodel M (0) usingtrainingdataset; for t=1,2,...,N do Observethetrajectorylocationattime t /*Backtrackingandrestartstep*/ for t 0 = t T;t T +1 ;:::;t 1 do Updatemodel M ( t 0 ) usingbackpropagationwithallobservedtrajectory locationstillcurrenttime t end M ( t ) M ( t 1) /*Predictionstep*/ for ˝ =1 ; 2 ; ;T do Generatetrajectorypredictions z t;˝ usingmodel M ( t ) end end Algorithm4: Proposed ODTP framework 6.4Experiments Thehurricanebesttrack(groundtruth)dataandNHCo˚cialforecastsareavailablefrom theNHCwebsite 1 ,whiletheensemblememberforecastsweredownloadedfromtheHurricane ForecastModelOutputwebsiteatUniversityofWisconsin-Milwaukee 2 .AccordingtoNHC, 46modelswereusedinthepreparationoftheiro˚cialforecasts.However,only27ofthem havedataavailablefromtheyear2012to2020attheUWMwebsite.Wewillusethe 1 https://www.nhc.noaa.gov 2 http://derecho.math.uwm.edu/models 112 forecastsfromthese27modelsasensemblemembersinourexperiments.Wecollectedthe hurricanetrajectorydatafromyear2012to2020.The˝naldatasetcontains336tropical cyclonesandtotal7364observationsat6hourinterval.Eachtropicalcycloneshasaaverage lengthof21.9timesteps.Forensemblememberswith12-hourlyinterval,weperformed linearinterpolationtoimputethemissingvaluessothateveryensemblememberhas6- hourlyforecasts.Thehurricanedatafrom2012to2017(208tropicalcyclones)wereused fortrainingandvalidationwhilethosefrom2018to2020(128tropicalcyclones)wereused fortesting. 6.4.1BaselineandEvaluationMetrics Wecomparedour DTP frameworkagainstthefollowingbaselinemethods: 1. Ensemblemean :Thismethodsimplycalculatesthemeanvalueoftheensemble memberoutputsateachleadtimeasitspredictions. 2. Persistence :Thismethodassumesthemovingspeedateachtimestepisequalto movingspeedatitsprevioustimestep.Then,thenewlocationcanbeeasilycalculated foreachleadtime. 3. Passive-Aggressive(PA) [21]:Thisisawell-knownonlinelearningalgorithmthat updatestheweightsbasedonnewlyobserveddatapoints. 4. ORION [84]:Thisisanonlinemulti-tasklearningalgorithmformulti-leadtime forecasting. 5. OMuLeT :ThisistheonlinelearningalgorithmdescribedintheChapter3fortrajec- toryprediction. 6. NHC :Thisisthegoldstandard,correspondingtotheo˚cialforecastsgeneratedby NHC. 113 Onlinemodel Trajectoryerror(innmi) LeadTime 12 24 36 48 EnsMean 23.30 36.34 50.22 65.03 Persistance 34.84 88.89 155.87 229.63 NHC 24.59 38.49 52.17 65.74 PA 23.30 36.34 50.23 64.80 ORION 23.37 36.36 50.21 65.00 OMuLeT 22.33 35.33 48.97 63.77 LSTM 41.64 94.50 160.35 232.80 DTP 23.20 36.08 49.72 64.40 ODTP 22.90 35.50 48.85 63.27 Table6.1:Trajectoryandintensityforecasterrorsfordi˙erentmethodsatvaryingleadtimes from12to48hours. 7. LSTM :ThisisthevanillaLSTMarchitecturetrainedonthehistoricaltrajectories withawindowsizeof48hoursand6-hourinterval. Forafaircomparison,themodelistrainedonthesametrainingset.Theperformance oftheforecastscanbeevaluationbytheMeanDistanceError(MDE).Themeandistance errorforleadtime ˝ canbede˝nedasMDE ˝ inthefollowingequation: MDE ˝ = 1 P t k t;˝ X t;k t;˝ =1 distance ( z t;˝ ; y t;˝ ) (6.10) 6.4.2PerformanceComparison Theresultscomparingthehurricanetrajectorypredictionerrorsforvariousmethodsfrom 12hourto48hourforecastleadtimesareshowninTable6.1.Notethattheresultsreported herefor OMuLeT areslightlydi˙erentfromtheonesgiveninSection3.4.1sincethelatter werebasedonmodelstrainedandtestedonhurricanedatafromtheyearsupto2018only. Theperformancecomparisonresultsshowninthetablecanbesummarizedasfollows.First, observethattheperformanceofthepersistenceandvanillaLSTMmethodsaresigni˝cantly worsethanotherapproaches.Thisisbecausebothmethodsuseonlyhistoricaltrajectories, whichareinsu˚cienttogenerateaccuratetrajectoryforecasts.Second,theperformance 114 of DTP frameworkisslightlyworsethan OMuLeT framework,thoughtheybothoutperform otherbaselinesincludingtheNHCo˚cialforecasts.Furthermore, ODTP canfurtherimprove theperformanceof DTP inallleadtimes,whichsuggeststheadvantagesofusinganonline learningapproachtoadaptthemodeltochangesinthedistributionofthedata.Speci˝cally, the48-hourforecasterrorisdecreasedfrom64.40nmito63.27nmi.Experimentresultsalso showthat ODTP outperformallotheronlinelinearmodelssuchasPA,ORION,and OMuLeT at36hourormoreforecastleadtimes.Thissuggeststhebene˝tsofusinganonlinearmodel tocapturetherelationshipsinthemulti-leadtimeforecastsgeneratedatdi˙erenttimesteps. 6.4.2.1CaseStudy (a) (b) (c) (d) (e) (f) Figure6.5:Comparisonof48-hourforecastsforHurricaneIrmafrom2017/09/08to 2017/09/09bydi˙erentmethods. Figure6.5showsanexampleofthetrajectoryforecastsforHurricaneIrmafromSeptem- 115 (a) (b) (c) (d) (e) (f) Figure6.6:Comparisonof48-hourforecastsforHurricaneIrmafrom2017/09/08to 2017/09/09bydi˙erentmethods. ber8toSeptember9,2017.Theplotscomparetheforecastsgeneratedby ODTP against DTP andseveralotherbatchlearningalgorithms.TheresultssuggestthatthevanillaLSTM canonlypredictshort-termforecastsaccurately,butnotforlongerleadtimes.Inmostof thecases,theforecastsgeneratedby ODTP algorithmareclosesttothebesttrackcompared tootherbaselinemethods.Althoughthetrajectoryforecastsgeneratedbytheensemble membersvaryquitesigni˝cantly, ODTP canlearntheappropriateattentionweightstothe ensemblememberstomakethepredictionmoreaccurate.Furthermore, ODTP alsoproduces moreaccuratepredictionsthan DTP ,whichcanbeclearlyseenfromFigures6.5(b)and(c). Thisveri˝estheimportanceofusinganonlinelearningapproachfortrajectoryprediction. Figure6.6compares ODTP algorithmagainstallotheronlinelearningbaselinealgorithms.As canbeseenfromthe˝gure,onlinelearningalgorithmsgeneratequitecomparablemulti-lead timeforecasts.However,asshowninTable6.1,thereisstillimprovementsin ODTP compared 116 Figure6.7:Meanresidualdistanceerror e t ˝;m;˝ vs.mean t;m ˝ ofallthetimestepswithin onehurricaneforphysicalmodelAVNO.Thecorrelationsscoresare-0.7294,-0.5489,-0.3457, -0.2133for12-hour,24-hour,36-hour,48-hourleadtimeforecasts,respectively. tootheronlinelinearmodels. 6.4.2.2AnalysisoftheModelPerformanceLayer BasedonthediscussioninSection6.3.1.2,weexpecttheperformancelayershouldbeableto learnanembeddingoftheensemblemembersbasedontheirmodelperformance.Theem- beddingsarethenusedtogenerateappropriateattentionweightsfortheensemblemembers. Toverifythis,wewillanalyzetherelationshipbetweentheinputandoutputofthemodel performancelayer.Foreachphysicalmodel m ,theinputoftheLSTMinmodelperformance layeristhedistanceerror ~ e t;m whileitsoutputcorrespondstotheembeddingvector, t;m . Figure6.7showsthescatterplotsofmeanresidualdistanceerror e t ˝;m;˝ againstthemean vector t;m ˝ forallthetimestepsinagivenhurricanefortheAVNOmodel.Thecorrelation betweenthemeandistanceerrorsandmeanvector t;m ˝ are-0.7372,-0.5440,-0.3450,-0.2128 for12-hour,24-hour,36-hour,48-hourleadtimeforecasts,respectively.Eventhoughthe output t;m alsodependsonthelong-termmemoryinLSTM,itisclearthatthereisa 117 signi˝cantnegativerelationshipbetweentheresidualdistanceerror e t ˝;m;˝ andtheoutput score t;m ˝ .Thelargertheresidualerror,thesmallertheembeddingvector t;m ˝ .Thisagrees withourexpectationthat t;m ˝ capturestheperformanceoftheensemblemember m . 6.5Conclusions Inthischapter,IproposedanLSTMbasedtrajectoryforecastingframeworkcalled DTP and itsonlinecounterpart, ODTP .UnlikeexistingRNNbasedapproachesforhurricanetrajec- toryprediction,theproposedframeworksaimtoproduceaccuratelong-rangeforecastsby leveragingtheoutputsgeneratedfromanensembleofstatisticalanddynamicalmodels.To handlethemissingvalueproblem,anovelTDM(TemporalDecayMemory)structurewas developed.Bothframeworkswereappliedtoreal-worldhurricanedatasettopredictthehur- ricanetrajectoryforupto48hoursleadtime.Experimentalresultsshowedthat ODTP can achievebetterperformancethan DTP ,andgenerallyoutperformsotherbaselineapproaches. 118 CHAPTER7 CONCLUSIONSANDFUTUREWORKS Inthischapter,asummaryofthethesiscontributionsarepresentedalongwithsuggestions forfutureresearch. 7.1SummaryofThesisContributions Inthisthesis,afamilyofonlinelearningalgorithmswasdevelopedtohandleavarietyof trajectorylocationpredictionandstatepredictiontasks.Thesealgorithmsweredesignedto overcomethevariouslimitationsofexistingapproaches,includinghandlingmulti-leadtime predictions,missingvalues,ordinal-valuedstatepredictions,etc. Firstofall,toaddressresearchquestion RQ1 ,Idevelopedaframeworkcalled OMuLeT formulti-leadtimelocationprediction.Theproposedframeworkcouldimprovetrajectory predictionbycombiningoutputsgeneratedfromanensembleofpredictionmodelsinan onlinefashion.Inordertogenerateaccuratelongrangepredictions, OMuLeT employsa backtrackingwithrestartstrategytoincrementallyupdatethemodelweightswhennew observationdatabecomeavailable.Itcanalsohandlethevaryingfeaturelengthissuewith aweightre-normalizationstrategy. Second,Iproposedthe OOR frameworktoaddressresearchquestion RQ2 ,whichisto handlethestatepredictiontaskwithanordinaltargetvariable. OOR employsanordinalloss functioninitsformulationtoprocesstheordinalvariableandgenerateordinalpredictions. Toaddresstheresearchquestion RQ3 ,theframeworkwasextendedto OOQR ,whichaccom- modatesaquantilelossfunctiontoimproveitspredictionaccuracyforhigh/lowordinal categoryvalues.Furthermore,usingan -insensitivelossfunction,the OOR- and OOQR- frameworksweredevelopedtosimultaneouslygeneratereal-valuedandordinal-valuedstate predictions. Third,Iintroducedajointlearningframeworkcalled JOHAN forthesimultaneouslocation 119 andstatepredictionofamovingobjectinordertoaddressresearchquestion RQ4 . JOHAN utilizesanexponentially-weightedquantilelossfunctioninitsformulationsforlocationand statepredictions,inwhichthehyperparameterofthequantilelossfunctionisupdatedjointly inreal-time. Finally,IproposedaLSTMbasedapproachcalled DTP forresearchquestion RQ5 . DTP approachaimstoproduceaccuratelong-rangepredictionsusesthelocationpredictionsgen- eratedfromanensembleofpredictingmodels.Inordertosolvetheconceptdriftproblemin thetrajectorypredictiontask,Idevelopedanonlineimplementationofthe DTP framework called ODTP tofurtherimprovethepredictionperformance. Allofthedevelopedapproachesweresuccessfullyappliedtothehurricanepredictiontask. The OMuLeT approachwasusedtopredictthefuturehurricanetrajectory.Experimentalre- sultsshowedthat OMuLeT signi˝cantlyoutperformedvariousbaselinemethods,includingthe o˚cialtrajectoryforecastsproducedbyNHC.The OOR / OOQR frameworkwasusedtopredict theordinal-valuedhurricanecategories.Experimentalresultssuggestedthat OOR generates moreaccuratepredictionsofthehurricanecategoriescomparedtoseveralbaselinemethods. Inaddition,avariationoftheframeworkcalled OOQR canfurtherimproveitsaccuracyin predictinghighcategoryhurricanes.The JOHAN frameworkcangeneratehurricanetrajectory andintensitypredictionssimultaneously.Experimentalresultsdemonstratedthat JOHAN can furtherimprovehurricaneintensitypredictionsandachievessuperiorperformanceinterms ofidentifyinghighcategoryhurricanesapproachingtheland.The DTP / ODTP arenon-linear modelsthatwereusedtopredictthetrajectorypathsofhurricanes.Experimentalresults showedthat DTP outperformsvariousbatchlearningalgorithmswhereasitsonlineversion, called ODTP ,canfurtherboosttheperformanceandgeneratesmoreaccuratelongrange predictionsthanotherbaselinemethods. 120 7.2FutureWorks Althoughtheproposedframeworksshowedgreatpromiseintermsofaddressingthehurricane predictionproblem,thereareseveralpotentialdirectionsforfutureresearchthatcanbe pursued.Thissectionoutlinessomeofthepotentialfutureworks. ApplicationtootherDomains Inthisthesis,Imainlyappliedtheproposedframeworks tohurricanepredictiontasks.However,itisclearthatmanyoftheseframeworksarealso applicabletootherdomains,inwhichusefulfeaturesbeyondhistoricaltrajectory(orstate) informationareavailable.Forexample,the OMuLeT frameworkcanbeusedtoforecast vehicletrajectory,utilizingasetofmulti-leadtimelocationpredictionsfromvariousreal- timefeaturesavailable.The OOR / OOR- frameworkscanalsobeappliedtootherordinal predictiontasks. LSTMforTrajectoryLocationandStatePrediction The DTP / ODTP frameworks weredevelopedandevaluatedfortrajectorylocationpredictions.Extendingtheframeworks toajointlearningapproachforlocationandstatepredictionisapotentialfutureresearch direction.Inparticular,howtocombinethejointtrajectory/statelearningintodeeplearning frameworkisaninterestingproblemthathasnotbeensu˚cientlyaddressed. DeepLearningApproachforHurricaneTrajectoryPredictionwithImageData Inthisthesis,wedevelopedanLSTM-basedalgorithms DTP / ODTP ,whichusestheoutputs fromanensembleofstatistical/dynamicalmodels.Inrecentyears,deeplearningapproaches, suchasconvolutionalneuralnetworks,havebeensuccessfullyappliedtosatelliteimagery data[54,39,38]forhurricanelocationpredictions.Mergingmyproposedframeworkswith trajectorypredictionbasedonsatelliteimagerydatawillbeaninterestingdirectionto pursue. 121 BIBLIOGRAPHY 122 BIBLIOGRAPHY [1] AssessingtheU.S.Climatein2018. NationalCentersforEnvironmentalInformation (NCEI) ,2019. [2] A.Alahi,K.Goel,V.Ramanathan,A.Robicquet,L.Fei-Fei,andS.Savarese.Social lstm:Humantrajectorypredictionincrowdedspaces.In CVPR ,pages971,2016. [3] S.Alemany,J.Beltran,A.Perez,andS.Ganzfried.Predictinghurricanetrajectories usingarecurrentneuralnetwork.In ProceedingsoftheAAAIConferenceonArti˝cial Intelligence ,volume33,pages2019. [4] A.Asahara,K.Maruyama,A.Sato,andK.Seto.Pedestrian-movementprediction basedonmixedMarkov-chainmodel.In Proceedingsofthe19thACMSIGSPATIAL , pagesACM,2011. [5] M.AwadandR.Khanna.Supportvectorregression.In E˚cientlearningmachines , pagesSpringer,2015. [6] M.Benkert,J.Gudmundsson,F.Hübner,andT.Wolle.Reporting˛ockpatterns. ComputationalGeometry ,2008. [7] D.BirantandA.Kut.ST-DBSCAN:Analgorithmforclusteringoraldata. Data&KnowledgeEngineering ,2007. [8] E.S.BlakeandD.A.Zelinsky.TropicalCycloneReport:HurricaneHarvey. National HurricaneCenter ,2018. [9] E.S.Blake,C.W.Landsea,andE.J.Gibney. Thedeadliest,costliest,andmost intenseUnitedStatestropicalcyclonesfrom1851to2010(andotherfrequentlyrequested hurricanefacts) .NationalWeatherService,NationalHurricaneCenter,2011. [10] A.Bolbol,T.Cheng,I.Tsapakis,andJ.Haworth.Inferringhybridtransportation modesfromsparseGPSdatausingamovingwindowSVMclassi˝cation. Computers, EnvironmentandUrbanSystems ,2012. [11] D.Brown.TropicalCycloneIntensityForecasting:StillaChallengingProposition. NationalHurricaneCenter ,2017. [12] J.P.Cangialosi.NationalHurricaneCenterforecastveri˝cationreport:2019hurricane season,2020. [13] H.Cao,N.Mamoulis,andD.W.Cheung.Miningfrequentspatio-temporalsequential patterns.In DataMining,FifthIEEEInternationalConferenceon ,pagesIEEE, 2005. 123 [14] H.Cao,N.Mamoulis,andD.W.Cheung.Discoveryofperiodicpatternsinspatiotempo- ralsequences. IEEETransactionsonKnowledgeandDataEngineering , 2007. [15] J.S.Cardoso,J.F.P.daCosta,andM.J.Cardoso.Modellingordinalrelationswith SVMs:Anapplicationtoobjectiveaestheticevaluationofbreastcancerconservative treatment. NeuralNetworks ,2005. [16] H.Cheng,P.-N.Tan,J.Gao,andJ.Scripps.Multistep-AheadTimeSeriesPrediction. In Proceedingsofthe10thPaci˝c-AsiaConferenceonKnowledgeDiscoveryandData Mining ,pages7652006. [17] W.ChuandS.S.Keerthi.Supportvectorordinalregression. Neuralcomputation ,19 2007. [18] U.Costliest.TropicalCyclonesTablesUpdated. NationalHurricaneCenter ,2018. [19] T.S.Cox,C.S.Hoi,C.K.Leung,andC.R.Marofke.Anaccuratemodelforhurricane trajectoryprediction.In 2018IEEE42ndAnnualComputerSoftwareandApplications Conference(COMPSAC) ,volume2,pagesIEEE,2018. [20] K.CrammerandY.Singer.Prankingwithranking.In Advancesinneuralinformation processingsystems ,pages6412002. [21] K.Crammer,O.Dekel,J.Keshet,S.Shalev-Shwartz,andY.Singer.Onlinepassive- aggressivealgorithms. JournalofMachineLearningResearch ,2006. [22] C.Davis,W.Wang,S.S.Chen,Y.Chen,K.Corbosiero,M.DeMaria,J.Dudhia, G.Holland,J.Klemp,J.Michalakes,etal.Predictionoflandfallinghurricaneswith theadvancedhurricaneWRFmodel. Monthlyweatherreview ,2008. [23] M.DeMariaandJ.Kaplan.Astatisticalhurricaneintensitypredictionscheme(SHIPS) fortheAtlanticbasin. WeatherandForecasting ,1994. [24] M.DeMaria,M.Mainelli,L.K.Shay,J.A.Kna˙,andJ.Kaplan.Furtherimprove- mentstothestatisticalhurricaneintensitypredictionscheme(SHIPS). Weatherand Forecasting ,2005. [25] H.DikkersandL.Rothkrantz.Supportvectormachinesinordinalclassi˝cation:An applicationtocorporatecreditscoring. NeuralNetworkWorld ,15(6):491,2005. [26] D.H.DouglasandT.K.Peucker.Algorithmsforthereductionofthenumberofpoints requiredtorepresentadigitizedlineoritscaricature. Cartographica:TheInternational JournalforGeographicInformationandGeovisualization ,1973. [27] O.M.Doyle,E.Westman,A.F.Marquand,P.Mecocci,B.Vellas,M.Tsolaki, I.Kªoszewska,H.Soininen,S.Lovestone,S.C.Williams,etal.Predictingprogres- sionofAlzheimer'sdiseaseusingordinalregression. PloSone ,9(8):e105542,2014. 124 [28] H.Drucker,C.J.Burges,L.Kaufman,A.Smola,andV.Vapnik.Supportvector regressionmachines. Advancesinneuralinformationprocessingsystems , 1996. [29] E.Eslami,Y.Choi,Y.Lops,andA.Sayeed.ADeepLearningDrivenImprovedEn- sembleApproachforHurricaneForecasting. 2019ESIPWinterMeeting ,2019. [30] M.Ester,H.-P.Kriegel,J.Sander,X.Xu,etal.Adensity-basedalgorithmfordiscov- eringclustersinlargespatialdatabaseswithnoise.In KDD ,volume96,pages 1996. [31] U.M.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy.Advancesin knowledgediscoveryanddatamining.1996. [32] F.Fernandez-Navarro,P.Campoy-Munoz,C.Hervas-Martinez,X.Yao,etal.Address- ingtheEUsovereignratingsusinganordinalregressionapproach. IEEEtransactions oncybernetics ,2013. [33] S.Ga˙neyandP.Smyth.Trajectoryclusteringwithmixturesofregressionmodels.In Proceedingsofthe˝fthACMSIGKDDinternationalconferenceonKnowledgediscovery anddatamining ,pages72.ACM,1999. [34] S.J.Ga˙ney,A.W.Robertson,P.Smyth,S.J.Camargo,andM.Ghil.Probabilistic clusteringofextratropicalcyclonesusingregressionmixturemodels. Climatedynamics , 2007. [35] S.Gao,P.Zhao,B.Pan,Y.Li,M.Zhou,J.Xu,S.Zhong,andZ.Shi.Anowcasting modelforthepredictionoftyphoontracksbasedonalongshorttermmemoryneural network. ActaOceanologicaSinica ,2018. [36] G.Georgoulas,S.Kolios,P.Karvelis,andC.Stylios.Examiningnominalandordinal classi˝ersforforecastingwindspeed.In 2016IEEE8thInternationalConferenceon IntelligentSystems(IS) ,pages504IEEE,2016. [37] F.Giannotti,M.Nanni,F.Pinelli,andD.Pedreschi.Trajectorypatternmining.In Proceedingsofthe13thACMSIGKDD ,pages39.ACM,2007. [38] S.Gi˙ard-Roisin,M.Yang,G.Charpiat,B.Kégl,andC.Monteleoni.DeepLearning forHurricaneTrackForecastingfromAlignedSpatio-temporalClimateDatasets.In Modelinganddecision-makinginthespatiotemporaldomainNIPSworkhop ,2018. [39] S.Gi˙ard-Roisin,M.Yang,G.Charpiat,B.Kégl,andC.Monteleoni.Fuseddeeplearn- ingforhurricanetrackforecastfromreanalysisdata.In ClimateInformaticsWorkshop Proceedings2018 ,2018. [40] S.Gi˙ard-Roisin,M.Yang,G.Charpiat,C.KumlerBonfanti,B.Kégl,andC.Mon- teleoni.Tropicalcyclonetrackforecastingusingfuseddeeplearningfromalignedre- analysisdata. FrontiersinBigData ,3:1,2020. 125 [41] S.Gopalakrishnan,Q.Liu,T.Marchok,D.Sheinin,N.Surgi,R.Tuleya,R.Yablonsky, andX.Zhang.HurricaneWeatherResearchandForecasting(HWRF)modelscienti˝c documentation. LBernardetEd ,75:7655,2010. [42] J.S.Greenfeld.MatchingGPSobservationstolocationsonadigitalmap.In 81th annualmeetingofthetransportationresearchboard ,volume1,pages2002. [43] B.Gu,V.S.Sheng,K.Y.Tay,W.Romano,andS.Li.Incrementalsupportvector learningforordinalregression. IEEETransactionsonNeuralnetworksandlearning systems ,2014. [44] J.GudmundssonandM.vanKreveld.Computinglongestduration˛ocksintrajectory data.In Proceedingsofthe14thannualACMinternationalsymposiumonAdvancesin geographicinformationsystems ,pages42.ACM,2006. [45] J.Gudmundsson,M.vanKreveld,andB.Speckmann.E˚cientdetectionofmotionpat- ternsinspatio-temporaldatasets.In Proceedingsofthe12thannualACMinternational workshoponGeographicinformationsystems ,pages257.ACM,2004. [46] P.A.Gutiérrez,S.Salcedo-Sanz,C.Hervás-Martínez,L.Carro-Calvo,J.Sánchez- Monedero,andL.Prieto.Ordinalandnominalclassi˝cationofwindspeedfromsynoptic pressurepatterns. EngineeringApplicationsofArti˝cialIntelligence , 2013. [47] J.E.HershbergerandJ.Snoeyink. SpeedinguptheDouglas-Peuckerline-simpli˝cation algorithm .UniversityofBritishColumbia,DepartmentofComputerScience,1992. [48] T.F.Hogan,M.Liu,J.A.Ridout,M.S.Peng,T.R.Whitcomb,B.C.Ruston,C.A. Reynolds,S.D.Eckermann,J.R.Moskaitis,N.L.Baker,etal.Thenavyglobal environmentalmodel. Oceanography ,2014. [49] H.Jeung,H.T.Shen,andX.Zhou.Convoyqueriesinspatio-temporaldatabases. In 2008IEEE24thInternationalConferenceonDataEngineering ,pages IEEE,2008. [50] H.Jeung,M.L.Yiu,X.Zhou,C.S.Jensen,andH.T.Shen.Discoveryofconvoysin trajectorydatabases. ProceedingsoftheVLDBEndowment ,2008. [51] E.Keogh,S.Chu,D.Hart,andM.Pazzani.Anonlinealgorithmforsegmentingtime series.In ICDM ,pages289IEEE,2001. [52] B.Kim,C.M.Kang,J.Kim,S.H.Lee,C.C.Chung,andJ.W.Choi.Probabilistic vehicletrajectorypredictionoveroccupancygridmapviarecurrentneuralnetwork. In 2017IEEE20thInternationalConferenceonIntelligentTransportationSystems (ITSC) ,pages404.IEEE,2017. [53] K.-j.KimandH.Ahn.Acorporatecreditratingmodelusingmulti-classsupportvector machineswithanordinalpairwisepartitioningapproach. Computers&Operations Research ,2012. 126 [54] S.Kim,H.Kim,J.Lee,S.Yoon,S.E.Kahou,K.Kashinath,andM.Prabhat.Deep- hurricane-tracker:Trackingandforecastingextremeclimateevents.In 2019IEEE WinterConferenceonApplicationsofComputerVision(WACV) ,pages176 IEEE,2019. [55] Y.-J.KimandM.Chi.TemporalBeliefMemory:ImputingMissingDataduringRNN Training.In InProceedingsofthe27thInternationalJointConferenceonArti˝cial Intelligence(IJCAI-2018) ,2018. [56] J.-G.Lee,J.Han,andK.-Y.Whang.Trajectoryclustering:apartition-and-group framework.In Proceedingsofthe2007ACMSIGMODinternationalconferenceon Managementofdata ,pages604.ACM,2007. [57] J.-G.Lee,J.Han,andX.Li.Trajectoryoutlierdetection:Apartition-and-detectframe- work.In DataEngineering,2008.ICDE2008.IEEE24thInternationalConferenceon , pagesIEEE,2008. [58] J.-G.Lee,J.Han,X.Li,andH.Gonzalez.TraClass:trajectoryclassi˝cationusing hierarchicalregion-basedandtrajectory-basedclustering. ProceedingsoftheVLDB Endowment ,2008. [59] R.S.LeeandJ.N.Liu.Tropicalcycloneidenti˝cationandtrackingsystemusing integratedneuraloscillatoryelasticgraphmatchingandhybridRBFnetworktrack miningtechniques. IEEETransactionsonNeuralNetworks ,2000. [60] W.-C.LeeandJ.Krumm.Trajectorypreprocessing.In Computingwithspatialtrajec- tories ,pages.Springer,2011. [61] X.Li,J.Han,S.Kim,andH.Gonzalez.Roam:Rule-andmotif-basedanomalydetection inmassivemovingobjectdatasets.In SDM ,pages273SIAM,2007. [62] Z.Li,B.Ding,J.Han,andR.Kays.Swarm:Miningrelaxedtemporalmovingobject clusters. ProceedingsoftheVLDBEndowment ,2010. [63] Z.Li,B.Ding,J.Han,R.Kays,andP.Nye.Miningperiodicbehaviorsformoving objects.In Proceedingsofthe16thACMSIGKDD ,pages109ACM,2010. [64] W.Mathew,R.Raposo,andB.Martins.PredictingfuturelocationswithhiddenMarkov models.In Proceedingsofthe2012ACMconferenceonubiquitouscomputing ,pages ACM,2012. [65] P.McCullagh.Regressionmodelsforordinaldata. JournaloftheRoyalStatistical Society:SeriesB(Methodological) ,1980. [66] N.MeratniaandA.Rolf.Spatiotemporalcompressiontechniquesformovingpoint objects.In InternationalConferenceonExtendingDatabaseTechnology ,pages 782.Springer,2004. [67] A.MohamedandK.Schwarz.AdaptiveKalman˝lteringforINS/GPS. Journalof geodesy ,1999. 127 [68] A.Monreale,F.Pinelli,R.Trasarti,andF.Giannotti.Wherenext:alocationpredictor ontrajectorypatternmining.In Proceedingsofthe15thACMSIGKDD ,pages ACM,2009. [69] M.MoradiKordmahalleh,M.GorjiSe˝dmazgi,andA.Homaifar.ASparseRecurrent NeuralNetworkforTrajectoryPredictionofAtlanticHurricanes.In Proceedingsofthe GeneticandEvolutionaryComputationConference2016 ,pages957ACM,2016. [70] M.Mudigonda,S.Kim,A.Mahesh,S.Kahou,K.Kashinath,D.Williams,V.Michalski, T.O'Brien,andM.Prabhat.Segmentingandtrackingextremeclimateeventsusing neuralnetworks.In DeepLearningforPhysicalSciences(DLPS)Workshop,heldwith NIPSConference ,2017. [71] W.Y.Ochieng,M.A.Quddus,andR.B.Noland.Map-matchingincomplexurban roadnetworks.2003. [72] A.T.Palma,V.Bogorny,B.Kuijpers,andL.O.Alvares.Aclustering-basedapproach fordiscoveringinterestingplacesintrajectories.In Proceedingsofthe2008ACMsym- posiumonAppliedcomputing ,pages68.ACM,2008. [73] M.Pérez-Ortiz,M.Cruz-Ramírez,M.D.Ayllón-Terán,N.Heaton,R.Ciria,and C.Hervás-Martínez.Anorganallocationsystemforlivertransplantationbasedon ordinalregression. AppliedSoftComputing ,2014. [74] O.PinkandB.Hummel.Astatisticalapproachtomapmatchingusingroadnetwork geometry,topologyandvehicularmotionconstraints.In IntelligentTransportationSys- tems,2008.ITSC2008.11thInternationalIEEEConferenceon ,pages862IEEE, 2008. [75] M.A.Quddus,R.B.Noland,andW.Y.Ochieng.Ahighaccuracyfuzzylogicbasedmap matchingalgorithmforroadtransport. JournalofIntelligentTransportationSystems , 2006. [76] B.J.Reich,M.Fuentes,etal.AmultivariatesemiparametricBayesianspatialmodeling frameworkforhurricanesurfacewind˝elds. TheAnnalsofAppliedStatistics , 264,2007. [77] M.Rüttgers,S.Lee,S.Jeon,andD.You.Predictionofatyphoontrackusinga generativeadversarialnetworkandsatelliteimages. Scienti˝creports ,2019. [78] S.StewartandR.Berg.TropicalCycloneReport:HurricaneFlorence. NationalHur- ricaneCenter ,2019. [79] P.-N.Tanetal. Introductiontodatamining .PearsonEducationIndia,2007. [80] G.A.Vecchi,M.Zhao,H.Wang,G.Villarini,A.Rosati,A.Kumar,I.M.Held,and R.Gudgel.StatisticaldynamicalpredictionsofseasonalNorthAtlantichurricaneac- tivity. MonthlyWeatherReview ,2011. 128 [81] P.Vickery,P.Skerlj,andL.Twisdale.SimulationofhurricaneriskintheUSusing empiricaltrackmodel. Journalofstructuralengineering ,2000. [82] D.Wang,B.Liu,P.-N.Tan,andL.Luo.OMuLeT:OnlineMulti-LeadTimeLocation PredictionforHurricaneTrajectoryForecasting.In Proceedingsof34thAAAIConfer- enceonArti˝cialIntelligence ,2020. [83] S.WangandR.Toumi.Recentmigrationoftropicalcyclonestowardcoasts. Science , ,2021. [84] J.Xu,P.-N.Tan,andL.Luo.ORION:OnlineRegularizedmultI-taskregressiONand itsapplicationtoensembleforecasting.In ICDM ,pages1066.IEEE,2014. [85] X.Yang,L.Tang,X.Zhang,andQ.Li.Adatacleaningmethodforbigtracedata usingmovementconsistency. Sensors ,18(3):824,2018. [86] H.YinandO.Wolfson.Aweight-basedmapmatchingmethodinmovingobjects databases.In Scienti˝candStatisticalDatabaseManagement,2004.Proceedings.16th InternationalConferenceon ,pages437IEEE,2004. [87] J.J.-C.Ying,W.-C.Lee,andV.S.Tseng.Mininggeographic-temporal-semanticpat- ternsintrajectoriesforlocationprediction. ACMTransactionsonIntelligentSystems andTechnology(TIST) ,5(1):2,2013. [88] G.Yuan,S.Xia,L.Zhang,Y.Zhou,andC.Ji.Trajectoryoutlierdetectionalgorithm basedonstructuralfeatures. JournalofComputationalInformationSystems ,7(11): 2011. [89] J.Yuan,Y.Zheng,C.Zhang,W.Xie,X.Xie,G.Sun,andY.Huang.T-drive:driving directionsbasedontaxitrajectories.In Proceedingsofthe18thSIGSPATIAL ,pages ACM,2010. [90] J.Yuan,Y.Zheng,X.Xie,andG.Sun.Drivingwithknowledgefromthephysical world.In Proceedingsofthe17thACMSIGKDD ,pages24.ACM,2011. [91] J.Yuan,Y.Zheng,X.Xie,andG.Sun.T-Drive:EnhancingDrivingDirectionswith TaxiDrivers'Intelligence. IEEETrans.Knowl.DataEng. ,2013. [92] N.J.Yuan,Y.Zheng,L.Zhang,andX.Xie.T-˝nder:Arecommendersystemfor˝nding passengersandvacanttaxis. IEEETransactionsonknowledgeanddataengineering ,25 2012. [93] N.J.Yuan,Y.Zheng,L.Zhang,andX.Xie.T-˝nder:Arecommendersystemfor˝nding passengersandvacanttaxis. IEEETransactionsonknowledgeanddataengineering ,25 2013. [94] D.Zhang,N.Li,Z.-H.Zhou,C.Chen,L.Sun,andS.Li.iBAT:detectinganomalous taxitrajectoriesfromGPStraces.In Proceedingsofthe13thinternationalconference onUbiquitouscomputing ,pages08.ACM,2011. 129 [95] Z.ZhangandT.Krishnamurti.Aperturbationmethodforhurricaneensemblepredic- tions. MonthlyWeatherReview ,1999. [96] Y.Zheng,Y.Chen,X.Xie,andW.-Y.Ma.GeoLife2.0:alocation-basedsocialnet- workingservice.In MobileDataManagement:Systems,ServicesandMiddleware,2009. MDM'09.TenthInternationalConferenceon ,pages58.IEEE,2009. [97] Y.Zheng,Y.Chen,Q.Li,X.Xie,andW.-Y.Ma.Understandingtransportationmodes basedonGPSdataforwebapplications. ACMTransactionsontheWeb(TWEB) ,4 (1):1,2010. [98] Y.Zheng,X.Xie,andW.-Y.Ma.Geolife:Acollaborativesocialnetworkingservice amonguser,locationandtrajectory. IEEEDataEng.Bull. ,2010. 130