3y ago

69 Views

3 Downloads

285.29 KB

18 Pages

Transcription

Path signatureMachine learning applicationsRough Paths and its Applications in MachineLearningLim NengliSingapore University of Technology and DesignJuly 20, 2017Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsHistory and motivation Terry Lyons (1998), Differential equations driven by rough signals,Rev. Mat. Iberoamericana 14. Originally formulated to study stochastic differential equations in apath-wise manner. Rough paths theory theory of regularity structures Solution to KPZ equation (Martin Hairer, Fields medal 2014). Now begin applied to other hard problems in statistical physics. Recently, rough paths theory is finding applications in machinelearning.Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsControlled differential equationsConsider the following differential equation:yt0 V (yt ) xt0First-order approximation to the solution: For s, t [0, T ],ZtV (yr ) xr0 drZ t' V (ys )xr0 dryt ys ss V (ys ) (xt xs )Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsSecond-order approximationZtV (yr1 ) xr01 dr1s Z t Z r1 V (ys ) V 0 (yr2 ) yr02 dr2 xr01 dr1ss Z t 0 V (ys )xr1 dr1s Z t Z r100V (yr2 )V (yr2 ) xr2 dr2 xr01 dr1 ss Z t dxr1' V (ys )s Z t Z r1 0 V (ys )V (ys )dxr2 dxr1yt ys sLim NengliRough Paths and its Applications in Machine LearningsSingapore University of Technology and Design

Path signatureMachine learning applicationsSeparating signal from vector fieldIn one dimension:yt ys ' V (ys ) [xt xs ] V 0 (ys )V (ys ) 12(xt xs )2 In d dimensions:yt ys ' V (ys ) [xt xs ] V (ys )V (ys ) d Z t ZXi,j 1Lim NengliRough Paths and its Applications in Machine Learningssr1dxr(i)2dxr(j)1 ei ej Singapore University of Technology and Design

Path signatureMachine learning applications2-dimensional case# (1) 0 "(1)(1)x(y)(y)VVtt21 t 0 , 0 yt0 (2)(2)(2)(2)V1 (yt ) V2 (yt )xtyt Given(1)yt 0 we have"#"#(1)(1)(1)(1)V1 (ys ) V2 (ys ) xt xsyt ys '(2)(2)(2)(2)V1 (ys ) V2 (ys ) xt xs"R Rt r1(1)(1)dx 2 dxr1Rst Rsr1 r(2) V (ys )V (ys )(1)dxr2 dxr1s sLim NengliRough Paths and its Applications in Machine Learning#!R t R r1(1)(2)dxr2 dxr1ssR t R r1.(2)(2)dxr2 dxr1s sSingapore University of Technology and Design

Path signatureMachine learning applications2-dimensional case cont."R Rt r1(1)(1)dx 2 dxr1Rst Rsr1 r(2)(1)dxr2 dxr1s s#R t R r1(1)(2)dxdxrr21Rst Rsr1(2)(2)dxdxrr21s s 2(1)(1) (2) xxxs,t s,t 1 s,t1 0Ats 2 (2)2 x (2) x (1)2 Ats 0xs,ts,t s,t{z} {z} anti symmetric partsymmetric partwhere(k)(k)xs,t : xt xs(k) ,k 1, 2,and the Lévy-area is given byZ t Z r1Z tZt(1)(2)As dxr2 dxr1 ssLim NengliRough Paths and its Applications in Machine Learningssr1dxr(2)dxr(1).21Singapore University of Technology and Design

Path signatureMachine learning applicationsGreen’s theoremA 12I x (2) dx (1) x (1) dx (2)CLim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsSignature of a pathFor all 0 s t T , Sn (x)s,t : 1, xs,t , x2s,t , . . . , xns,t n R Rd Rd Rd · · · Rd,where xks,t is the conventional k-th iterated integral of the path x overthe interval [s, t]:xks,t dXj1 ,.,jk 1 Zs r1 ··· rk tLim NengliRough Paths and its Applications in Machine Learning dxr(j1 1 ) · · · dxr(jk k ) ej1 · · · ejk .Singapore University of Technology and Design

Path signatureMachine learning applicationsChen’s Identity The signature is an element of a Lie group called the step-nnilpotent group with d generators. It satisfies n (x)u,tSn (x)s,t Sn (x)s,u S s, u, t [0, T ], s u t, n where given a 1, a1 , . . . , a , b 1, b 1 , . . . , b n , groupmultiplication is performed by : 1, c 1 , . . . , c n ,a bck kXai b k i , 1 k n.i 0 b 1 , b 2 ) (1, a1 b 1 , a2 b 2 a1 b 1 ). E.g. (1, a1 , a2 ) (1,Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsFractional Brownian motion: WtH(i) Hurst parameter: H (0, 1)(ii) Continuous paths, not differentiable a.e.2H(iii) Wt Ws N (0, t s )(iv) Covariance function: R(s, t) 12s 2H t 2H t s 2H (v) H 12 : Standard Brownian motion, R(s, t) s t.(vi) H 12 : Increments along disjoint intervals are positively correlated.(vii) H 21 : Increments along disjoint intervals are negatively correlated.(viii) Neither a Markov process nor a martingale (unless H 12 )Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsSample pathsLim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsHölder continuity and rough pathsDefinitionA function f is said to be α-Hölder continuous on an interval [0, T ] ifα f (t) f (s) C t s , s, t [0, T ]. Hölder continuity measures how ”rough” a function is. Fact: Fractional Brownian motion with Hurst parameter H is almostsurely (H ε)-Hölder continuous for any ε 0.Definition Given 13 α 12 , X 1, Xs,t , X2s,t is an α-Hölder rough path if itsatisfies Chen’s identity, X is α-Hölder continuous and X2 is 2α-Höldercontinuous.Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsItó integration as rough paths integration RTPYt dWt limkπk 0 i Yti Wti ,ti 1 , where the limit is taken inL (Ω) and not almost surely path-wise because the paths are notregular enough.02 Even so, convergence in L2 (Ω) relies on the fact Wt is a martingale,and that Yt is adapted to the filtration of Wt . Define ItoWs,t: 1, A1s,t , A2s,t Zt Ws,r1 dWr11, Ws,t ,sThen given a ”Gubinelli derivative” Y 0 ,Z TZ TYt dWt Yt dWtIto lim Yti A1ti ,ti 1 Y 0 A2ti ,ti 100kπk 0almost surely.Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsProperties of the signature The signature has more or less a one-to-one relation with its path(see T. Lyons and B. Hambly, Uniqueness for the signature of apath of bounded variation and the reduced path group, 2010). It is a graded summary of the data stream encoded in the path. Iterated integrals capture non-linear aspects of the path. Forms a natural ”basis” for functionals on data streams. It provides a rich set of features that can be used in a machinelearning pipeline.Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsApplications Finance:J. Field, L. Gyurkó, M. Kontkowski and T. Lyons (2014), Extractinginformation from the signature of a financial data stream,arXiv:1307.7244v2. Sound compression:T. Lyons and N. Sidorova (2005), Sound compression: a rough pathapproach, In Proceedings of the 4th international symposium onInformation and communication. Identifying patterns in MEG scans etc. I. Chevyrev and A. Kormilitzin (2016), A Primer on the SignatureMethod in Machine Learning, arXiv:1603.03788v1.Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsChinese handwriting recognition SCUT gPen: Online Chinese handwriting recognition software Began as a collaboration between Terry Lyons and BenGraham (University of Warwick) App developed by HCII-Lab in South China University ofTechnology State of the art: Won first place in ICDAR2013 competition with anerror rate of 2.61% (Second place: 3.13%, Human error: 4.81%). Combines rough path theory and a deep convolutional neuralnetwork. Uses first 3 levels of the signature of the path. Ben Graham (2013), Sparse arrays of signatures for online characterrecognition, arXiv:1308.0371v2.Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Path signatureMachine learning applicationsConclusion and ramblings Textbooks: Peter Friz and Martin Hairer (2014), A Course on RoughPaths, Springer. Terry Lyons, M. Caruana, and T. Lévy (2007), Differentialequations driven by Rough Paths, Springer. Future direction: Application to stochastic control and reinforcement learning:(i) Extend control theory to dynamical systems perturbed bycoloured noise.(ii) Find efficient Monte-Carlo schemes to compute optimal pathand control trajectories.Lim NengliRough Paths and its Applications in Machine LearningSingapore University of Technology and Design

Peter Friz and Martin Hairer (2014), A Course on Rough Paths, Springer. Terry Lyons, M. Caruana, and T. L evy (2007), Di erential equations driven by Rough Paths, Springer. Future direction: Application to stochastic control and reinforcement learning: (i)Extend control theory to dynamical systems perturbed by coloured noise. (ii)Find e cient Monte-Carlo schemes to compute optimal path and .

Related Documents: