# Parameter Identification of ARX Models Based on Modified Momentum Gradient Descent Algorithm

Authors: Quan Tu; Yingjiao Rong; Jing Chen
Journal: Complexity
 (2020)

---

## Abstract

The parameter estimation problem of the ARX model is studied in this paper. First, some traditional identification algorithms are briefly introduced, and then a new parameter estimation algorithm—the modified momentum gradient descent algorithm—is developed. Two gradient directions with their corresponding step sizes are derived in each iteration. Compared with the traditional parameter identification algorithms, the modified momentum gradient descent algorithm has a faster convergence rate. A simulation example shows that the proposed algorithm is effective.


---

## Body

## 1. Introduction

There are many identification algorithms which can estimate the parameters of linear models and nonlinear models, such as the coupled identification algorithms [1, 2], the filtered identification algorithms [3, 4], and the hierarchical identification algorithms [5–7]. The autoregressive exogenous (ARX) model is based on the traditional autoregressive model, adding measurable external inputs at various times to generate output. Such a model is widely used in engineering practice. For example, Naveros used the ARX model to identify physical parameters of walls [8], Qin et al. applied the ARX model to control the magnetic levitation ball system [9], Haddouche et al. utilized the ARX model to control the gas condition tower [10]. Since a robust controller often has the assumption that the structures of the systems should be given in prior [11–13], the system identification plays an important role in control engineering. Its basic idea is to use the identification algorithms to determine a mathematical model [14–17] and by which the behavior of the systems can be predicted.The gradient descent algorithm is usually used for ARX model identification. It can effectively reduce the computational efforts but with slow convergence rates [18, 19]. The gradient descent algorithm includes two steps: the first is to determine a direction, which is called negative gradient, and the second is to determine a suitable step size for the direction. Besides, the least squares algorithm is another widely used method in system identification, which has a faster convergence rate [20–26]. However, the least squares algorithm has heavy computational efforts and needs to solve a derivative function. Therefore, it is inefficient for some models with complex nonlinear structures.In order to determine the step size of the gradient descent algorithm, the root of a higher-order equation needs to be calculated, which is challenging/impossible. Fortunately, the stochastic gradient (SG) algorithms [27, 28] avoid the root calculation by updating the parameters in each sampling time with only one set input-output data. It can be widely used in engineering practice for its simple structure. However, only one set of data is used at each sampling instant; the convergence rate of the SG algorithm is slow. To improve the convergence rate, Ding et al. first proposed a multi-innovation stochastic gradient algorithm and a multi-innovation least squares algorithm for linear regression models [29, 30], which have quick convergence rates. The conjugate gradient descent method is another method which has quicker convergence rate when comparing with the gradient descent algorithm, but it is only available for offline identification [31–34]. Inspired by the conjugate gradient descent algorithm, the focus of this paper is to propose a modified momentum gradient descent algorithm, which has a quicker convergence rate and no root calculation.The remainder of this paper is organized as follows. Section2 introduces the ARX model and the traditional SG algorithm. The multi-innovation stochastic gradient algorithm is presented in Section 3. In Section 4, a modified momentum gradient descent algorithm is developed. A simulation example is given in Section 5. Finally, the conclusions and future directions are summarized in Section 6.


## 2. Stochastic Gradient Descent Algorithm

Consider the following ARX model:(1)Azyt=Bzut+vt,where yt is the output, ut is the input, vt is the noise, and Az and Bz are polynomials:(2)Az=1+a¯1z−1+a¯2z−2+⋯+a¯nz−n,(3)Bz=b1z−1+b2z−2+⋯+bmz−m.Take equations (2) and (3) into equation (1), and let ai=−a¯i,i=1,2,…,n, the ARX model can be written by(4)yt=a1yt−1+a2yt−2+⋯+anyt−n+b1ut−1+b2ut−2+⋯+bmut−m+vt.Letθ∗ be the true value, θ^ be the estimated one:(5)θ∗=a1,a2,…,an,b1,b2,…,bmT∈ℝm+n,θ^=a^1,a^2,…,a^n,b^1,b^2,…,b^mT∈ℝm+n,and φt is the information vector:(6)φt=yt−1,yt−2,…,yt−n,ut−1,ut−2,…,ut−mT∈ℝn+m.Define the cost function as follows:(7)Jθ^=12yt−φTtθ^2.To obtain the minimum value ofJθ^, let the iteration function be(8)Fθ^=θ^+ap.When the estimated parameter vectorθ^ converges to the true value θ∗,(9)θ^=Fθ^=θ^+ap,(10)p=−ΔJ=φtyt−φTtθ^,where p is the negative gradient direction of Jand a is the step size. Substituting equation (6) into equation (4) yields(11)Ja=12yt−φTtθ^+ap2.In order to get the minimum value ofJa, use(12)∂J∂a=yt−φTtθ^+ap−φTtp,and let ∂J/∂a=0. The steepest descent algorithm can be obtained:(13)θ^t=Fθ^t−1=θ^t−1+φtyt−φTtθ^t−1φTtφt.Remark 1.
Whenθ^t is close to the true value, the calculated step size would be imprecise, which will cause the error to fluctuate. Therefore, the steepest descent algorithm is inefficient.
The SG algorithm proposed in the following can deal with this problem:(14)θ^t=θ^t−1+φta′tyt−φTtθ^t−1,φt=yt−1,yt−2,…,yt−n,ut−1,ut−2,…,ut−mT,at′=at−1′+φTtφt,a0′=0.Remark 2.
The step size will be reduced with the increase in time. Whenθ^t is close to the true value, the smaller step size reduces the fluctuation dramatically.


## 3. Two-Innovation Stochastic Gradient (TI-SG) Descent Algorithm

Because of the slow convergence rate of the SG algorithm, Ding proposed a multi-innovation stochastic gradient (MI-SG) algorithm in [6]. As a special case of the MI-SG algorithm, when two sets of input-output data are performed in each iteration, we term it as two-innovation stochastic gradient (TI-SG) algorithm.For the ARX model, two sets input-output data are collected in each iteration as follows:(15)φt−1=yt−2,yt−3,…,yt−n−1,ut−2,ut−3,…,ut−m−1T,φt=yt−1,yt−2,…,yt−n,ut−1,ut−2,…,ut−mT.Establishing the following two functionsJ1θ^ and J2θ^, we get(16)J1θ^=12yt−1−φTt−1θ^2,J2θ^=12yt−φTtθ^2.We can calculate the negative gradient directionsp1 and p2, respectively:(17)p1=−ΔJ1=φt−1yt−1−φTt−1θ^,p2=−ΔJ2=φtyt−φTtθ^.The cost function is established as follows:(18)Jθ^=J1θ^+J2θ^=12yt−1−φt−1θ^2+12yt−φtθ^2.Let the iteration function be(19)Fθ^=θ^+ap1+p2.Update the parametersθ^=Fθ^, then the cost function is(20)Ja=∑i=0112yt−i−φTt−iθ^+ap1+p22.There are two ways to calculate the step sizea:(1)
The two-innovation stochastic gradient descent algorithm has the same step size as that in the SG algorithm. Let the initial value of the step size be 0. The TI-SG algorithm can be designed as(21)θ^t=θ^t−1+p1+p2at′,p1=φt−1yt−1−φTt−1θ^t−1,p2=φtyt−φTtθ^t−1,φt−1=yt−2,yt−3,…,yt−n−1,ut−2,ut−3,…,ut−m−1T,φt=yt−1,yt−2,…,yt−n,ut−1,ut−2,…,ut−mT,at′=at−1′+φTtφt,a0′=0.(2)
The other method is to calculate the optimal step size, which is called modified two-innovation stochastic gradient (MT-SG) descent algorithm.(22)∂J∂a=∑i=01yt−i−φTt−iθ^t−1+ap1+p2⋅−φTt−ip1+p2.Let∂J/∂a equal 0, then(23)a=p1+p2Tp1+p2∑i=01φTt−ip1+p22.The MT-SG algorithm can be designed as(24)θ^t=θ^t−1+atp1+p2,p1=φt−1yt−1−φTt−1θ^t−1,p2=φtyt−φTtθ^t−1,φt−1=yt−2,yt−3,…,yt−n−1,ut−2,ut−3,…,ut−m−1T,φt=yt−1,yt−2,…,yt−n,ut−1,ut−2,…,ut−mT,at=p1+p2Tp1+p2∑i=01φTt−ip1+p22.Remark 3.
The traditional two-innovation algorithm and the modified two-innovation algorithm use two gradients and assume that the two gradient directions have the same step size. Although the computational effort is reduced, it is not optimal. Because each gradient direction plays a different role in estimating the parameters, it is necessary to consider assigning different weights to each gradient.Remark 4.
Compared with the traditional two-innovation method, the modified two-innovation method calculates the optimal step size in each sampling instant. Therefore, the modified two-innovation algorithm has a faster convergence rate but with heavier computational efforts.


## 4. Modified Momentum Gradient Descent Algorithm (MMG)

Before introducing the modified momentum gradient descent algorithm, we first introduce the conjugate gradient descent algorithm.Assume that we have collectedL input-output data. The collected information vectors and outputs are ΦL and YL, respectively,(25)φt=yt−1,yt−2,…,yt−n,ut−1,ut−2,…,ut−mT∈ℝm+n,ΦL=φTt+1,φTt+2,…,φTt+LT∈ℝL×m+n,YL=yt+1,yt+2,…,yt+LT∈ℝL.Set up the cost function as follows:(26)Jθ^=12Yt−ΦLθ^2.To calculate the minimum value ofJθ^, simply make ∂J/∂θ^=0:(27)∂J∂θ^=−ΦTLYt−ΦLθ^.LetA=ΦTLΦL and b=ΦTLYt. When the order of ΦL is greater than n+m, it is easy to know that A is a symmetric positive definite matrix, and A∈ℝm+n×m+n and b∈ℝm+n.Using the conjugate gradient descent method to solve higher-order matrix equations, letr=b−Aθ^, where r is the current negative gradient direction. Reconcile the previous iteration direction p′ with the current negative gradient direction r as the new iteration direction p, which is p=r+βp′. Making p′ and p conjugate about A, that is pTAp′=0, we have(28)β=−rTAp′p′TAp′.Let the iteration function be(29)Fθ^=θ^+ap,where a is the step size and p is the iteration direction, then(30)Ja=12Yt−ΦLθ^+ap2.Calculating the minimum value ofJa and letting(31)∂J∂a=−ΦLpTYt−ΦLθ^+ap=0,yield(32)a=pTΦTLYt−ΦLθ^pTΦTLΦLp=pTb−Aθ^pTAp=pTrpTAp.Letθ^ satisfy(33)θ^k=Fθ^k−1=θ^k−1+pkTrkpkTApkpk.The conjugate gradient descent algorithm can be designed as(34)θ^k=θ^k−1+apk,pk=rk−rkApk−1pk−1TApk−1⋅pk−1,rk=b−Aθ^k−1,a=pkTrkpkTApk,φt=yt−1,yt−2,…,yt−n,ut−1,ut−2,…,ut−mT,ΦL=φTt+1,φTt+2,…,φTt+LT,YL=yt+1,yt+2,…,yt+LT,A=ΦTLΦL,b=ΦTLYt.Remark 5.
Herer is the negative gradient direction of the current position and p′ is the direction of the last iteration. The current iteration direction p is obtained based on r and p′. Compared with the traditional gradient descent method, this method has a faster convergence rate but with heavier computational efforts.
Inspired by the conjugate gradient descent method, the modified momentum gradient descent algorithm is proposed. Its basic idea is to use two gradient directions in each iteration/sampling instant and then to assign different step sizes for each direction.
When using the TI-SG algorithm method, a set of repeated data during the neighbouring two sampling instants will be involved, which causes the step size unsolvable. To overcome this difficulty, a new method is developed. For the ARX model, collect two sets of information vectors and two outputs in each iteration asφ2t,y2t,φ2t+1, and y2t+1:(35)φ2t=y2t−1,y2t−2,…,y2t−n,u2t−1,u2t−2,…,u2t−mT,φ2t+1=y2t,y2t−1,…,y2t−n+1,u2t,u2t−1,…,u2t−m+1T.
Establish two cost functionsJ1θ^ and J2θ^ as follows:(36)J1θ^=12y2t−φT2tθ^2,J2θ^=12y2t+1−φT2t+1θ^2.
UsingJ1θ^,J2θ^ to calculate the negative gradient directions p1,p2 yields(37)p1=−ΔJ1=φ2ty2t−φT2tθ^,p2=−ΔJ2=φ2t+1y2t+1−φT2t+1θ^.
Let the iteration function be(38)Fθ^=θ^+a1p1+a2p2.
Then, the cost functions are(39)J1a1,a2=12y2t−φT2tθ^+a1p1+a2p22,J2a1,a2=12y2t+1−φT2t+1θ^+a1p1+a2p22.
Let∂J1/∂a1,∂J1/∂a2,∂J2/∂a1, and ∂J2/∂a2 all be equal to 0, then(40)y2t−φT2tθ^+a1p1+a2p2−φT2tp1=0,y2t−φT2tθ^+a1p1+a2p2−ϕT2tp2=0,y2t+1−φT2t+1θ^+a1p1+a2p2−φT2t+1p1=0,y2t+1−φT2t+1θ^+a1p1+a2p2−φT2t+1p2=0.
Letr1=y2t−φT2tθ^ and r2=y2t+1−φT2t+1θ^, we have(41)a1=r1φT2t+1p2−r2φT2tp2φT2tp1φT2t+1p2−φT2t+1p1φT2tp2,a2=r2φT2tp1−r1φT2t+1p1φT2tp1φT2t+1p2−φT2t+1p1φT2tp2.
The MMG algorithm is listed as follows:(42)θ^t=θ^t−1+a1p1+a2p2,p1=−ΔJ1=φ2tr1,p2=−ΔJ2=φ2t+1r2,r1=y2t−φT2tθ^t−1,r2=y2t+1−φT2t+1θ^t−1,a1=r1φT2t+1p2−r2φT2tp2φT2tp1φT2t+1p2−φT2t+1p1φT2tp2,a2=r2φT2tp1−r1φT2t+1p1φT2tp1φT2t+1p2−φT2t+1p1φT2tp2.
The MMG algorithm constitutes the following steps:(Algorithm1)Algorithm 1:Modified momentum gradient descent algorithm.
Initializeθ0repeatfort = 0, 1, …, ndogetφ2t,y2t,φ2t+1 and y2t+1r1=y2t−φT2tθtr2=y2t+1−φT2t+1θtifr1<tol and r2<tolthenreturnθtelsep1=r1φ2tp2=r2φ2t+1D=φT2tp1φT2t+1p2−φT2t+1p1φT2tp2a1=r1φT2t+1p2−r2φT2tp2a2=r2φT2tp1−r1φT2t+1p1θt+1=θt+1/Da1p1+a2p2enduntil convergenceRemark 6.
In each iteration, the MMG algorithm uses two directions and assigns the optimal step size for each direction. Therefore, it has a quicker convergence rate. However, some iterative algorithms [35–38] and recursive algorithms [39–42] can be extended to study the parameter identification of the ARX models in this paper.


## 5. Example

Consider the following ARX model:(43)yt=φTtθ+vt,φt=yt−1,yt−2,yt−3,ut−1,ut−2T,θ=0.3,−0.7,0.5,0.25,0.17T.The input dataut is a random sequence with a uniform distribution on −0.5,0.5, and vt is Gaussian white noise with N0,0.012. The simulation data are shown in Figure 1.Figure 1
The simulation data.The SG, TI-SG, MT-SG, and MMG algorithms are used to identify the parameters of the ARX model. The parameter estimates and their estimation errors are shown in Figure2 and Tables 1–4.Figure 2
The parameter estimation errors.Table 1
The parameter estimates and the estimation errors (SG).
tθ1θ2θ3θ4θ5δ%50.0090−0.1416−0.01950.34060.112885.7714100.0112−0.21010.00870.31090.194778.588650−0.0030−0.28800.05230.29170.229871.2120100−0.0029−0.32800.06980.27940.258367.8208150−0.0065−0.34430.07890.27500.260166.4253200−0.0079−0.34840.08220.27590.258766.0179True value0.3000−0.70000.50000.25000.1700Table 2
The parameter estimates and the estimation errors (TI-SG).
tθ1θ2θ3θ4θ5δ%50.0900−0.2645−0.06910.44790.343082.4797100.0423−0.36930.01040.43600.397173.788450−0.0196−0.49210.11030.31700.305058.9297100−0.0128−0.54290.13270.27920.319455.1883150−0.0206−0.56230.14980.26710.300053.2816200−0.0221−0.56440.15800.27180.290852.5223True value0.3000−0.70000.50000.25000.1700Table 3
The parameter estimates and the estimation errors (MT-SG).
tθ1θ2θ3θ4θ5δ%50.0870−0.3185−0.06780.38050.388579.207910−0.0537−0.67580.19480.29650.366953.0981500.1609−0.64860.39700.26970.152519.00931000.2578−0.72590.46000.24330.19977.35211500.2925−0.70060.47970.24560.17292.32372000.3051−0.69850.50040.23890.16801.3000True value0.3000−0.70000.50000.25000.1700Table 4
The parameter estimates and the estimation errors (MMG).
tθ1θ2θ3θ4θ5δ%5−0.0585−0.74630.18310.33120.289552.2903100.0286−0.73570.17460.22830.148944.41681000.2898−0.68380.49460.25280.16842.09961500.3037−0.71140.52190.25340.16442.68412000.3076−0.69780.51140.24990.18081.8318True value0.3000−0.70000.50000.25000.1700The relative errors of each element in the parameter vector by using these four algorithms are shown in Figure3 (t=20, 50, and 100).Figure 3
The relative errors of each element in the parameter vector. (a) SG. (b) TI-SG. (c) MT-SG. (d) MMG.
(a)(b)(c)(d)Select 100 new data based on the true model, and use the estimated models by the SG, TI-SG, TI-SG and MMG algorithms to generate the predicted outputs, respectively. The errors between the true outputs and the predicted outputs are shown in Figure4.Figure 4
Output estimation errors of the four algorithms. (a) SG. (b) TI-SG. (c) MT-SG. (d) MMG.
(a)(b)(c)(d)Finally, a Monte Carlo experiment is performed by using the MMG algorithm (100 sets noises), and the results are shown in Figure5.Figure 5
The parameter estimation errors by using the Monte Carlo method.The following conclusions can be obtained:(1)
It can be seen from Figures2 and 3 and Tables 2 and 3 that the MT-SG algorithm has a significantly faster speed than the original TI-SG algorithm(2)
From Figures2 and 3 and Tables 1–4, we can see that the MMG algorithm has the fastest convergence rates among the four algorithms(3)
Figure4 demonstrates that the estimated model by using the MMG algorithm is the most accurate one among these four estimated models(4)
Figure5 shows that the MMG algorithm is robust to the noises


## 6. Conclusions

This paper proposes an improved gradient descent algorithm for ARX models based on the conjugate gradient descent method. Since two gradient directions and the two corresponding step sizes are involved in each iteration, the proposed algorithm has a quicker convergence rate. The simulation example shows the effectiveness of the proposed algorithm. This algorithm can increase the convergence rate and does not require root calculation. Therefore, it can combine other identification techniques [43–46] to study the parameter estimation issues of linear and nonlinear stochastic systems with colored noises [47–50] and can be extended to other literatures [51–54], such as signal modeling, parameter identification information processing, and engineering application systems [55–57].Although the MMG algorithm is hoped to be a powerful tool for parameter identification, its convergence property is an open and challenging problem.



---

*Source: 9537075-2020-06-17.xml*