# System Identification on the Families of Auto-Regressive with Least-Square-
Batch Algorithm

Moh Kamalul Wafi1 1Moh Kamalul Wafi is with Laboratory of Embedded and Cyber-
Physical Systems, Department of Engineering Physics, Institut Teknologi
Sepuluh Nopember, 60111, Indonesia, kamalul.wafi at its.ac.id

###### Abstract

The theories of system identification have been highly elaborated so as to
achieve the true system. This paper much discuses regarding the stochastic
processes along with the divergent of whether or not the system has zero-mean
under scenario of either white and coloured noise. The mathematical
foundations, including mean, variance, covariance, optimal parameters, along
with some modified scenarios among them, are presented in detail from various
system along with some basic idea behind them. The families of auto-regressive
(1) and (2) are compared both mathematical and simulation in order to obtain
the best design approaching the true system, Moreover, the least-square
algorithm is used to examine the effectiveness of some number of iteration
along with ”batch” theorem.

###### Index Terms:

System Identification, Auto-Regressive, Least-Square Algorithm, Batch Theorem

##  I Introduction

System identification, an error-correcting training scheme, is becoming more
important dealing with either a system or process requiring to estimate the
states with certain unknown variables. Further research even has modified from
classic statistical method to regularisation considering the unhealthy matrix
of minimization scheme [1], [2]. The idea of auto-regressive involves current
and preceding data to be estimated with mutually independent per-sequence [3].
This model is then modified so as to obtain the best prediction, reducing the
error. This is well-conducted by [4] proposing unknown number of epoch formula
each sequence inducing the Markov process. Thanks to [5], the very early idea
in predicting one-step ahead using either the median and the log-normal
process of distribution. Moreover, the procedural modification applying Lasso
scenario is also a choice as presented in [6]. This research is to examine
basic properties from the family of auto-regressive along with the benefit of
some iteration $N$ and batch $\kappa$. Beyond that, the assumptions of zero-
mean and its counterpart along with either white and coloured noise are also
considered.

The first and foremost is the stability properties of the system. The Lyapunov
scenario as the most famed algorithm is proposed in this project [7]. While
there has been a broad modification in determining the stability of the
system, including strong passivity in nonlinear system as stated in [8], the
mathematical foundation should be well-defined [9]. These basic information
are then ready followed by some recursive or forecasting scheme with other
bunch of methods. Least-square as prediction is to portray the best linear to
show the data along with forecast the following data with respect to some
instant time $t$, consisting the trend and the level of development. The more
generalized with coloured noise system is presented in [10] referring to the
original [11]. This paper comprises the problem formulation followed by the
basic mathematical concepts. The next is the analytical result with three
divergent scenarios ended by the numerical design and conclusion.

##  II Problem Formulation

This paper presents the objectives of system identification:

  1. 1.

To elaborate the functions of expected value, variance, and covariance in a
stationary process via static representation

  2. 2.

To describe mathematically the identification abilities of AR models of
increasing order

  3. 3.

To compare the theoretical results with its simulation with empirical Least
Square (LS) estimation

  4. 4.

To highlight the impact of coloured noises on the LS estimation

##  III Basic Mathematical Theories

General design of the system model is presented in Fig. (1) defining that $P$
is the system plant along with $\xi$ as its parameter. $\nu$ comprises either
fault $(f)$ or disturbances $(d)$ whilst $u$ and $z$ denote as the accessible
input and the controlled variable in turn. The space of possible results is
denoted by $\mathcal{S}$ and its single result of $s$ is $\in\mathcal{S}$
while the events of certain interest are defined as $s_{\epsilon}$ which is
also the subset of $\mathcal{S}$. Furthermore, the patterns of the output
depend on the parameters on algebraic equation of the system $P_{\xi}$
resulting its roots either real or complex. The common features of the
dynamics constitute that the $(t)$ continuous or $(z)$ discrete-mathematical
structure is built by differential equation and it has been a-priori knowledge
being found from the physical properties of the system.

$P_{\xi(t,z)}$$\nu\sim(f,d)$$u$$z$ Figure 1: The general dynamic systems

The applied random variable is a variable of $\mathcal{F}(s)$ obtaining values
according to the result $s\in\mathcal{S}$ of a random trial through a function
$\Theta(\bullet)$. The probability distribution function supplies the data on
the random variable so that the equation of $F(x)=\mathcal{P}(v\leq x)$ can be
denoted as,

$\mathcal{P}(v\in[a,b])=F(b)-F(a)$ (1)

meaning that $\mathcal{P}$ is the specific probability distribution being made
of function $F$ with points between $a$ and $b$ while the probability density
of $f^{\dagger}$ creating an area of $\mathcal{P}(v\in[a,b])$ is defined as
follows,

$f^{\dagger}(x)=\frac{\partial F}{\partial x}$ (2)

Furthermore, the expected value E and its variance $\mathcal{Q}$ of a fault
and disturbance are presented as,

$\displaystyle\textbf{E}(v)$
$\displaystyle=\int_{-\infty}^{+\infty}xf^{\dagger}(x)\,dx$ (3)
$\displaystyle\mathcal{Q}_{v}$
$\displaystyle=\int_{-\infty}^{+\infty}\left[x-\textbf{E}(v)\right]^{2}f^{\dagger}(x)\,dx$
(4)

with standard deviation of $\sigma(v)=\sqrt{\mathcal{Q}_{v}}$. Keep in mind
that, given two variables of $v_{1}(s)$ and $v_{2}(s)$, the results of $v(s)$,
$\textbf{E}(v)$, and $\mathcal{Q}_{v}$ are $v(s)=v_{1}(s)+v_{2}(s)$,
$\textbf{E}(v)=\textbf{E}(v_{1})+\textbf{E}(v_{2})$, and

$\mathcal{Q}(v)\neq\mathcal{Q}(v_{1})+\mathcal{Q}(v_{2})$ (5)

in turn, with
$\mathcal{Q}_{v}=\textbf{E}\left\\{[v-\textbf{E}(v)][v-\textbf{E}(v)]^{T}\right\\}$.
A Gaussian random variable exists if the average $\mu=\textbf{E}(v)$ and
variance $\mathcal{Q}$ or $\sigma^{2}$ satisfies:

$g(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-k}\longrightarrow
k=\frac{(x-\mu)^{2}}{2\sigma^{2}}$ (6)

with respect to the properties of the $v$ in terms of correlation and
independent, again, the two random variables $v_{1}$ and $v_{2}$ are
uncorrelated if

$\textbf{E}\left\\{[v_{1}-\textbf{E}(v_{1})][v_{2}-\textbf{E}(v_{2})]^{\top}\right\\}=0$
(7)

whereas they are called as independent if

$\mathcal{P}(v_{1},v_{2})=\mathcal{P}(v_{1})\mathcal{P}(v_{2})$ (8)

hence, the stochastic process originally requires the portrayal of probability
distribution and is a collection of infinite random variable sequenced with
respect to time. A stochastic process of $v(t)$ is called white being defined
as $v\sim\mathcal{W}\mathcal{N}(0,\lambda^{2})$ if $\textbf{E}[v(t)]=0$ and

$\mathcal{Q}(x)=\begin{cases}\lambda^{2},&x=0\\\ 0,&x\neq 0\end{cases}$ (9)

Beyond that, apart from examine the unbiased estimation, the minimization of
the variance $\Phi$ could be tested. The estimator of $\bar{\theta}^{1}$ is
better than that of $\bar{\theta}^{2}$ if
$\Phi_{\bar{\theta}^{1}}\leq\Phi_{\bar{\theta}^{2}}$ or, if $\bar{\theta}^{i}$
is a vector, then $\Phi_{\bar{\theta}^{2}}-\Phi_{\bar{\theta}^{1}}\geq 0$. The
asymptotic characteristic is affected by the number of simulated data $N$
which also influence the better estimation and reduce the uncertainty. Suppose
three different variances $\Phi_{m}$ with the same expected value E such that
$\textbf{E}[\bar{\theta}^{i}]=\theta$ with $i=1\to m$ and $m_{3}>m_{2}>m_{1}$,
the estimate $\bar{\theta}^{m}$ is said good at converging to $\theta$ if

$\displaystyle\lim_{m\to\infty}\Phi_{\bar{\theta}^{m}}=0\longrightarrow\lim_{m\to\infty}\textbf{E}\left[\lVert\bar{\theta}^{m}-\theta\rVert^{2}\right]=0$

where $\bar{\theta}^{m},\theta$ and $\lVert\bar{\theta}^{m}-\theta\rVert$ are
the random and constant vector along with a scalar random with good mean
variable in turn.

##  IV Analytical Results

This section acts as the numerical findings which are then compared to the
simulations with Least Square algorithm being elaborated in the following
section. There are three different scenarios. First is the basic with zero-
mean and the second is to alter from zero-mean to non-zero mean yet the other
conditions are kept the same and the following is to change the covariance
instead of the mean.

###  IV-A Independent and Zero-mean

The dynamics of a stationary stochastic process $y(\bullet)$ is presented in
the following Fig. (2) in which $q(\bullet)$ and $v(\bullet)$ are independent,
such that:

$\dfrac{1}{1-\lambda z^{-1}}$$+$$v\sim(f,d)$$q(t)$$y(t)$ Figure 2: Dynamic
systems of the proposed model

where $q\sim\mathcal{W}\mathcal{N}\left(\bar{q},\delta^{2}\right)$,
$v\sim\mathcal{W}\mathcal{N}\left(\bar{v},\xi^{2}\right)$, with
$\left[\bar{q},\bar{v}\right]=0$ and $\lambda\in\mathbb{R},|\lambda|<1$. It
can clearly be shown from the Fig. (2) that there have been two variables
which influence the point of output $y(t)$ so that, by applying some algebra
shown in Appendix A from inversing the $z-$transform to (time) $t-$domain, it
follows that:

$\displaystyle y(t)=\frac{1}{1-\lambda z^{-1}}q(t)+v(t)$ (10)

can be then written as the true system of the following formula, therefore

$\mathcal{S}:y(t)=\lambda y(t-1)+q(t)+v(t)-\lambda v(t-1)$ (11)

As the inputs process of $q(\bullet)$ and $v(\bullet)$ are stationary and the
point of $\lambda$ lies strictly inside the unit circle as well as
$|\lambda|<0$ which makes the value of $|z|<0$, the dynamic model generating
the stochastic process is asymptotically stable which implies that the steady
state stochastic process $y(t)$ is stationary. Furthermore, since the zero-
mean, the expected value $\textbf{E}[y(t)]=\bar{y}$ computed in Appendix B is
zero,

$\displaystyle\textbf{E}[y(t)]=\bar{y}=0\longrightarrow\left[\bar{q},\bar{v}\right]=0$
(12)

or substituting the two mean of the independent $[q,v]$ by the end of the
solution, the formula is then finished as $\bar{y}=\lambda\bar{y}$, concluding
that $\bar{y}\rightarrow 0$ and $\lambda\neq 0$. As for the variance of $y(t)$
denoted as $\Phi_{y}$, it is solved in the Appendix C, hence

$\displaystyle\Phi_{y}=\;$
$\displaystyle\frac{\delta^{2}+(1-\lambda^{2})\xi^{2}}{1-\lambda^{2}}$ (13)

Since the expected value $(\bar{y})$ is zero, the covariance function
$\Psi_{y}$ with $\tau=0,1,\ldots$ is exactly the same as the correlation
function being calculated in Appendix D and D⋆, with

$\displaystyle\Psi_{y}(\tau)=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\bar{y}\right]\left[y(t-\tau)-\bar{y}\right]\right\\}$
(14)

such that,

$\displaystyle\Psi_{y}(\tau)=\begin{cases}\dfrac{\delta^{2}}{1-\lambda^{2}}+\xi^{2}&,\tau=0\\\
\\\ \dfrac{\delta^{2}}{1-\lambda^{2}}\lambda^{\tau}&,\tau>0\end{cases}$ (15)

Furthermore, the analysis of the proposed dynamical process $y(\bullet)$ is
required using a PEM identification algorithm of the family AR(1), such that

$\displaystyle\mathbscr{F}_{1}(\theta_{1}):y(t)=\phi_{1}y(t-1)+\psi(t)$ (16)

and the corresponding stage of the design $\mathbscr{F}_{1}$ in estimation
form is,

$\displaystyle\hat{\mathbscr{F}}_{1}(\theta_{1}):\hat{y}(t|t-1)=\phi_{1}y(t-1)$
(17)

As for the higher-order of the family AR(2), the $\mathbscr{F}_{2}$ is denoted
as follows,

$\displaystyle\mathbscr{F}_{2}(\theta_{2}):y(t)=\phi_{1}y(t-1)+\phi_{2}y(t-2)+\psi(t)$
(18)

along with its prediction form, such that

$\displaystyle\hat{\mathbscr{F}}_{2}(\theta_{2}):\hat{y}(t|t-1)=\phi_{1}y(t-1)+\phi_{2}y(t-2)$
(19)

where $\theta_{1}$ and $\theta_{2}$ equal to $\phi_{1}$ and
$[\phi_{1},\phi_{2}]^{\top}$ in turn along with suitable white noise of
$\psi(t)$. Keep in mind that to compute the optimal values of those two
$\left(\theta^{\star}_{1},\theta^{\star}_{2}\right)$ with respect to
$\left(\theta_{1},\theta_{2}\right)$ respectively is to use the PEM algorithm
and according to the asymptotic theory, the convergence to one of the minima
of the two functions $\Gamma(\theta_{1})$ and $\Gamma(\theta_{2})$ can be
guaranteed, such that

$\displaystyle\Gamma(\theta_{1})=\textbf{E}\left\\{\left[\varepsilon_{\theta_{1}}(t)\right]^{2}\right\\}=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\hat{y}(t|t-1)\right]^{2}\right\\}$
(20)
$\displaystyle\Gamma(\theta_{2})=\textbf{E}\left\\{\left[\varepsilon_{\theta_{2}}(t)\right]^{2}\right\\}=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\hat{y}(t|t-1)\right]^{2}\right\\}$
(21)

where $\varepsilon_{\theta_{1}}(t)$ is the prediction error with suitable
$y(t)$ as shown in the $\mathbscr{F}_{1}$ and $\mathbscr{F}_{2}$ and regarding
the cost (optimal) functions of the two, they are defined as follows,

$\displaystyle\frac{\partial\Gamma(\theta_{1})}{\partial\phi_{1}}=\;0\quad\textrm{
and
}\quad\frac{\partial\Gamma(\theta_{2})}{\partial\phi_{1}\partial\phi_{2}}=\;0$
(22)

Furthermore, applying the concepts of [] above results in the optimality and
recalling the $\Psi_{y}(\tau)$, the values of
$\left(\theta^{\star}_{1},\theta^{\star}_{2}\right)$ are written in the
following according to the calculation being done in Appendix E and F,

$\displaystyle\theta^{\star}_{1}\coloneqq\;$
$\displaystyle\phi_{1}=\frac{\lambda\delta^{2}}{\delta^{2}+(1-\lambda^{2})\xi^{2}}$
(23) $\displaystyle\theta^{\star}_{2}\coloneqq\;$
$\displaystyle\left[\phi_{1},\phi_{2}\right]^{\top}=\begin{cases}\phi_{1}=\dfrac{\lambda\delta^{2}\left(\delta^{2}+\xi^{2}\right)}{\left(\delta^{2}+\xi^{2}\right)^{2}-\lambda^{2}\xi^{4}}\\\
\\\
\phi_{2}=\dfrac{\lambda^{2}\delta^{2}\xi^{2}}{\left(\delta^{2}+\xi^{2}\right)^{2}-\lambda^{2}\xi^{4}}\end{cases}$
(24)

Those optimum values then are implemented in the models of AR(1) and AR(2) as
the best design of either families, $\mathbscr{F}_{1}(\theta^{\star}_{1})$
with $\theta^{\star}_{1}\coloneqq\phi_{1}$ and
$\mathbscr{F}_{2}(\theta^{\star}_{2})$ with
$\theta^{\star}_{2}\coloneqq\left[\phi_{1},\phi_{2}\right]^{\top}$,
approximating the true system. The variance of the prediction errors related
to the two designs can be calculated from [] due to the fact that the expected
values of the error from either families are zero, such that,

$\displaystyle\bar{\varepsilon}_{\theta_{1}}=\;$
$\displaystyle\textbf{E}\left[y(t)\right]-\phi_{1}\textbf{E}\left[y(t-1)\right]=0$
(25) $\displaystyle\bar{\varepsilon}_{\theta_{2}}=\;$
$\displaystyle\textbf{E}\left[y(t)\right]-\phi_{1}\textbf{E}\left[y(t-1)\right]-\phi_{2}\textbf{E}\left[y(t-2)\right]=0$
(26)

and the variance of the families are enlightened in Appendix G by substituting
the covariance, therefore

$\displaystyle\Phi_{\varepsilon_{\theta_{1}^{\star}}}=\;$
$\displaystyle\frac{\left(\delta^{2}+\xi^{2}\right)^{2}-\lambda^{2}\xi^{4}}{\delta^{2}+\left(1-\lambda^{2}\right)\xi^{2}}$
(27) $\displaystyle\Phi_{\varepsilon_{\theta_{2}^{\star}}}=\;$
$\displaystyle\frac{\left(\delta^{2}+\xi^{2}\right)^{3}-\lambda^{2}\left(\delta^{2}\xi+\xi^{3}\right)^{2}+2\lambda\delta^{4}\xi^{2}}{1-\lambda^{2}}$
(28)

###  IV-B Independent and Non-Zero Mean

Recalling the same dynamical process as Fig. (2), the $q$ and $v$ are no
longer zero-mean, constituting
$q\sim\mathcal{W}\mathcal{N}\left(\bar{q},\delta^{2}\right)$ and
$v\sim\mathcal{W}\mathcal{N}\left(\bar{v},\xi^{2}\right)$ with $\bar{q}$ and
$\bar{v}$ equal to 1 and 4 respectively. Keep in mind that when $q(\bullet)$
and $v(\bullet)$ are zero-mean, the process $y(\bullet)$ is also zero-mean and
by contrast, if the two are not, this makes the expected value of the process
is not zero anymore, recalling Appendix B, the $\bar{y}$ is,

$\displaystyle\bar{y}\coloneqq\;\textbf{E}[y(t)]=\;$
$\displaystyle\lambda\bar{y}+\bar{q}+\bar{v}-\lambda\bar{v}$
$\displaystyle=\;$
$\displaystyle\bar{v}+\dfrac{\bar{q}}{1-\lambda}\longrightarrow\frac{5-4\lambda}{1-\lambda}$
(29)

and this also leads to the introduction of the new process $\check{y}(t)$,
where $\check{y}(t)=y(t)-\bar{y}$, therefore

$\displaystyle y(t)=\check{y}(t)+\bar{y}$ (30)

such that,

$\displaystyle\Phi_{y}=\textbf{E}\left\\{[y(t)-\bar{y}]^{2}\right\\}=\textbf{E}\left\\{[\check{y}(t)]^{2}\right\\}$
(31)

However, the not zero-mean process of $y(t)$ does not yield the changes of the
variance because the mean is subtracted from it. Likewise, due to the
coincidence between the correlation function in the zero mean process
$\check{y}(t)$ and the covariance of the original process, this new process
does not give divergent results in terms of covariance, meaning that both
parameters are on par with the originals, therefore

$\displaystyle\Psi_{y}(\tau)=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\bar{y}\right]\left[y(t-\tau)-\bar{y}\right]\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[\check{y}(t)\right]\left[\check{y}(t-\tau)\right]\right\\}$
(32)

Furthermore, the AR families analysis of $\mathbscr{F}_{1}$ and
$\mathbscr{F}_{2}$ regarding the optimality
$\left(\theta^{\star}_{1},\theta^{\star}_{2}\right)$ which are affected by the
covariance as mentioned in Eqs. (21) and (22) result in the similarities of
the original processes with slight differences. Recalling the new process of
$\check{y}(t)$, the cost function $\Gamma(\theta_{1})$, $\Gamma(\theta_{2})$
along with their estimates,

$\displaystyle\hat{y}(t|t-1)_{\hat{\mathbscr{F}}_{1}}=\;$
$\displaystyle\phi_{1}y(t-1)$ $\displaystyle=\;$
$\displaystyle\phi_{1}\left[\check{y}(t-1)+\bar{y}\right]$ (33)
$\displaystyle\hat{y}(t|t-1)_{\hat{\mathbscr{F}}_{2}}=\;$
$\displaystyle\phi_{1}y(t-1)+\phi_{2}y(t-2)$ $\displaystyle=\;$
$\displaystyle\phi_{1}\check{y}(t-1)+\phi_{1}\check{y}(t-2)+\left(\phi_{1}+\phi_{2}\right)\bar{y}$
(34)

respectively. The optimal value of
$\left(\theta^{\star}_{1},\theta^{\star}_{2}\right)$ is then obtained in
Appendix H and I, such that

$\displaystyle\theta^{\star}_{1}\coloneqq\;$
$\displaystyle\phi_{1}=\frac{\lambda\delta^{2}+\left(1-\lambda^{2}\right)\bar{y}^{2}}{\delta^{2}+\left(1-\lambda^{2}\right)\left(\xi^{2}+\bar{y}^{2}\right)}$
(35)

and $\theta^{\star}_{2}\coloneqq\;\left[\phi_{1},\phi_{2}\right]^{\top}$, with

$\displaystyle\begin{bmatrix}\dfrac{\left[\lambda\delta^{2}+\left(1-\lambda^{2}\right)\bar{y}^{2}\right]\left(\delta^{2}+\xi^{2}\right)}{\left(\delta^{2}+\xi^{2}+2\bar{y}^{2}\right)\left(\delta^{2}+\xi^{2}\right)-\xi^{2}\lambda^{2}\left(\xi^{2}+2\bar{y}^{2}\right)-2\lambda\delta^{2}\bar{y}^{2}}\\\\[15.0pt]
\dfrac{\lambda^{2}\delta^{2}\xi^{2}+\left[\delta^{2}\left(1-\lambda\right)^{2}+\xi^{2}\left(1-\lambda^{2}\right)\right]\bar{y}^{2}}{\left(\delta^{2}+\xi^{2}+2\bar{y}^{2}\right)\left(\delta^{2}+\xi^{2}\right)-\xi^{2}\lambda^{2}\left(\xi^{2}+2\bar{y}^{2}\right)-2\lambda\delta^{2}\bar{y}^{2}}\end{bmatrix}$
(36)

Likewise, these result are applied as the most optimum designs in either
families approaching the true systems, while the variance of them are modified
using these following mean of prediction error, such that

$\displaystyle\bar{\varepsilon}_{\theta_{1}}=\;$
$\displaystyle(1-\phi_{1})\bar{y}$ (37)
$\displaystyle\bar{\varepsilon}_{\theta_{2}}=\;$
$\displaystyle(1-\phi_{1}-\phi_{2})\bar{y}$ (38)

and the results are showed in Appendix J with small divergent compared to the
cost functions of $\left(\Gamma(\theta_{1}),\Gamma(\theta_{2})\right)$ by the
square of the expected values. Finally, under the initial assumption of the
characteristics $q(\bullet)$ and $v(\bullet)$, these influence almost the
whole systems leading to the shifted distribution.

###  IV-C Assumption to Parameters of $\lambda,\delta^{2},\xi^{2}$

Turning to another design with similar dynamical process as Fig. (2), the $q$
and $v$ are set as zero-mean with certain true parameters, comprising
$q\sim\mathcal{W}\mathcal{N}\left(0,4\right)$ and
$v\sim\mathcal{W}\mathcal{N}\left(0,9\right)$. This design will not change the
expected value with $\bar{y}=0$ and the result makes the variance and
covariance are counted the same as the originals (see Appendix C and D) with,

$\displaystyle\Phi_{y}=13.5$ (39)

and,

$\displaystyle\Psi_{y}(\tau)=\begin{cases}13.5&,\tau=0\\\ \\\
4.5\left(\dfrac{1}{3}\right)^{\tau}&,\tau>0\end{cases}$ (40)

Furthermore, since the model of AR(1) is affected by $\Psi_{y}(\tau)$, the
optimal value of $\theta_{1}^{\star}$ and the best design of
$\mathbscr{F}_{1}$ are

$\displaystyle\theta_{1}^{\star}\coloneqq\phi_{1}=\frac{1}{9}\longrightarrow\mathbscr{F}_{1}:y(t)=\frac{1}{9}y(t-1)+\phi(t)$
(41)

which is approaching the true system with variance $\Phi_{\theta_{1}^{\star}}$
equals to $13.333$. Likewise, as for the counterpart family of AR(2), the
optimal value of $\theta^{\star}_{2}$ is

$\displaystyle\theta^{\star}_{2}\coloneqq\;$
$\displaystyle\left[\phi_{1},\phi_{2}\right]^{\top}=\left[\frac{39}{360},\frac{1}{40}\right]^{\top}$
(42)

so that the best model of AR(2) can be written as follows

$\displaystyle\mathbscr{F}_{2}:y(t)=\frac{39}{360}y(t-1)+\frac{1}{40}y(t-2)+\phi(t)$
(43)

with the variance $\Phi_{\theta_{2}^{\star}}$ equals to $13.325$. From the
model, the AR(2) is slightly better in terms of small variance with $0.008$
difference compared to its counterpart.

(a) AR(1) $\rightarrow\alpha=1$

(b) AR(2) $\rightarrow\alpha=1$

(c) AR(1) $\rightarrow\alpha=1,\kappa$

(d) AR(2) $\rightarrow\alpha=1,\kappa$

(e) AR(1) $\rightarrow\alpha=2$

(f) AR(2) $\rightarrow\alpha=2$

(g) AR(1) $\rightarrow\alpha=2,\kappa$

(h) AR(2) $\rightarrow\alpha=2,\kappa$

Figure 3: These show the different performance of either families with
parameters of $\alpha$ and $\kappa$

##  V Numerical Design

Linear regression as typical context related to least-square estimator is
initialized with $n+1$ variables of $y(t)$,
$\theta_{1}(t),\dots,\theta_{n}(t)$ over an interval of $t=1,2,\dots,N$. It is
then required, if possible, $n$ variables
$\zeta_{1},\zeta_{2},\dots,\zeta_{n}$, such that

$\displaystyle
y(t)=\zeta_{1}\theta_{1}+\zeta_{2}\theta_{2}+\dots+\zeta_{n}\theta_{n}$ (44)

is denoted as linear regression according to $\theta(t)$ variable which is
able to rewrite as a matrix function of $\zeta^{\top}\theta$ acting as row
matrices. Recalling equation (11) with certain iteration of $N$ along with
some random sequence of either independent, the recursive equation is set as,

$\displaystyle\Pi=\begin{bmatrix}y(1)&y(2)&\cdots&y(N)\end{bmatrix}$ (45)

While the appearance of error $\epsilon$ referring to
$y(t)-\zeta^{\top}\theta$ is undeniable, to minimize it is a key by obtaining
the optimal vector of $\theta^{\star}$. It can be achieved by the function of
quadratic cost, therefore

$\displaystyle\Gamma(\theta)=\sum_{t=1}^{N}\left[y(t)-\zeta^{\top}\theta\right]^{2}\longrightarrow\theta^{\star}=\arg\min_{\theta}\Gamma(\theta)$
(46)

such that after differentiating the cost function in terms of $\theta$-element
generating the zero results, the $\theta$ could be determined by converting
the equality of both row and column vectors. If sum of the product of
$\zeta(t)\zeta(t)^{\top}$ from $1\to N$ is non-singular,

$\displaystyle\theta=\left[\sum_{t=1}^{N}\zeta(t)\zeta(t)^{\top}\right]^{-1}\sum_{t=1}^{N}\zeta(t)y(t)^{\top}$
(47)

it can be deduced that for the minimum of $\Gamma$, $\lVert
y_{N}-\zeta_{N}\theta\rVert$ should be orthogonal to $\zeta_{N}\theta$. This
is due to the symmetric and positive semi-definite so that $\theta_{N}$ yields
in local minimum of $\Gamma(\theta)$. Moreover, the sum of
$\zeta(t)\zeta(t)^{\top}$ results in two divergent scenarios of determinant
whether it is zero or not. Unique global minimum or identifiability is
situated if it is not zero while for the counterpart result, $\theta_{N}$ is
one among the infinite global minima. The least-square algorithm in Eq. (47)
is then used to computed the optimal
$\left[\theta_{1}^{\star},\theta_{2}^{\star}\right]$ of either families. The
variation of $N$ is also applied to observe the effectiveness of the
recursive. Furthermore, the $\kappa$ independent batches of the generated
$\Pi_{i}$, such that

$\displaystyle\Pi_{i}=\begin{bmatrix}y_{i}(1)&y_{i}(2)&\dots&y_{i}(N)\end{bmatrix}\quad
i=1\to\kappa$ (48)

with certain $N$ is required to calculate the empirical mean for both
families, such that

$\displaystyle\bar{\theta}_{1}=\frac{1}{\kappa}\sum_{i=1}^{\kappa}\hat{\theta}_{1}^{(i)}\qquad\textrm{and}\qquad\bar{\theta}_{2}=\frac{1}{\kappa}\sum_{i=1}^{\kappa}\hat{\theta}_{2}^{(i)}$
(49)

along with some variances as follows. The broader batches of $\check{\Pi}_{i}$
with certain constant $\alpha$, therefore $\alpha N$ is designed.

$\displaystyle\sigma_{\theta_{1}}^{2}\coloneqq\Phi_{\theta_{1}}=\frac{1}{\kappa}\sum_{i=1}^{\kappa}\left(\hat{\theta}_{1}^{(i)}-\bar{\theta}_{1}\right)^{2}$
(50)
$\displaystyle\sigma_{\theta_{2}}^{2}\coloneqq\Phi_{\theta_{2}}=\frac{1}{\kappa}\sum_{i=1}^{\kappa}\begin{bmatrix}\left(\varphi_{1}\right)^{2}&\varphi_{1}\varphi_{2}\\\\[7.0pt]
\varphi_{1}\varphi_{2}&\left(\varphi_{2}\right)^{2}\end{bmatrix}$ (51)

with,

$\displaystyle\varphi_{1}=\hat{\theta}_{2,1}^{(i)}-\bar{\theta}_{2,1}\qquad\varphi_{2}=\hat{\theta}_{2,2}^{(i)}-\bar{\theta}_{2,2}$
(52)

The process $q(\bullet)$ is supposed to be coloured noise based on the
following recursive equation,

$\displaystyle q(t)=-\frac{1}{2}q(t-1)+\eta(t)$ (53)

where $\eta\sim\mathcal{W}\mathcal{N}\left(0,1\right)$ and $\eta(\bullet)$ is
independent from $v(\bullet)$. This scenario is then observed being compared
to that of white noise in the preceding. It can be concluded that the variance
$\Phi_{\theta_{2}}^{\star}$ is slightly smaller than that of
$\Phi_{\theta_{1}}^{\star}$ meaning that the model approximation to the true
system of AR(2) is better than that of AR(1). In terms of the simulation, the
yields are closer to the hand-made calculation relative to certain $\alpha
N,\alpha=1\to\infty$, the greater $\alpha$ results in better approximation of
optimal value leading to the variance. With $\alpha=[1,2]$ and $N=1000$ in
AR(1) for instance, it generates

$\displaystyle 0.14\rightarrow N,\quad 0.12\rightarrow 2N$ (54)

optimal value $\theta_{1}^{\star}$ respectively compared to the hand
calculation $0.11$ while as for AR(2) as $\theta_{2}^{\star}$ with the same
design of $\alpha$, it yields $[\phi_{1},\phi_{2}]^{\top}$ as

$\displaystyle\begin{bmatrix}0.128\\\ 0.031\end{bmatrix}\rightarrow
N,\quad\begin{bmatrix}0.123\\\ 0.028\end{bmatrix}\rightarrow 2N$ (55)

in turn against the origin of $[0.108,0.025]^{\top}$. For certain
$\kappa=100,N=1000$ and $\alpha=[1,2]$, the $\theta_{1}^{\star}$ AR(1)
generates,

$\displaystyle\begin{bmatrix}\theta_{1}^{\star}\\\
\Phi_{\theta_{1}}\end{bmatrix}\coloneqq\begin{bmatrix}0.116\\\
0.0011\end{bmatrix}\rightarrow N,\quad\begin{bmatrix}0.112\\\
0.0005\end{bmatrix}\rightarrow 2N$ (56)

and these values of the estimated parameter is close to that of the optimal
$\theta_{1}^{\star}=0.11$. This is due to the more data provided leading to
better approximation. With respect to AR(2), the optimal parameter
$\theta_{2}^{\star}$ and the variance $\Phi_{\theta_{2}}$ with the same
scenarios of $\kappa,N,\alpha$ are obtained as follows,

$\displaystyle\theta_{2}^{\star}=\begin{bmatrix}0.1048\\\
0.0216\end{bmatrix}\quad\Phi_{\theta_{2}}=\begin{bmatrix}0.00097&-0.00006\\\
-0.00006&0.00111\end{bmatrix}$ (57)

for $N=1000$ whereas with $\alpha=2$, it gains

$\displaystyle\theta_{2}^{\star}=\begin{bmatrix}0.1086\\\
0.0245\end{bmatrix}\quad\Phi_{\theta_{2}}=\begin{bmatrix}0.00046&-0.00002\\\
-0.00002&0.00059\end{bmatrix}$ (58)

compared to the origin of $[\phi_{1},\phi_{2}]^{\top}=[0.1083,0.0250]^{\top}$.
Moving to coloured noise which generates divergent approximation, for AR(1)
with the same design as the white noise and hand-mad calculation, the optimal
value $\theta_{1}^{\star}$ comprises,

$\displaystyle-0.0137\rightarrow N,\quad-0.0259\rightarrow 2N$ (59)

This not surprising though, as for each sequence iteration, it yields a
divergent stimulated data influencing the system so that it is far compared to
that of the white. As for AR(2), $\theta_{2}^{\star}$ is reached as follows,

$\displaystyle\begin{bmatrix}-0.0686\\\ -0.0083\end{bmatrix}\rightarrow
N,\quad\begin{bmatrix}0.0014\\\ 0.0538\end{bmatrix}\rightarrow 2N$ (60)

which show the same pattern as in AR(1). With respect to batches
$\Pi_{i}\to\kappa$ scenario, the optimal value of AR(1) constitutes beyond the
origin meaning that it is biased affecting the empirical and its variances,
such that

$\displaystyle\begin{bmatrix}\theta_{1}^{\star}\\\
\Phi_{\theta_{1}}\end{bmatrix}\coloneqq\begin{bmatrix}-0.025\\\
0.0015\end{bmatrix}\rightarrow N,\quad\begin{bmatrix}-0.022\\\
0.0005\end{bmatrix}\rightarrow 2N$ (61)

and AR(2) is also performing the same another convergence number apart from
the origin (hand-made calculation), it is proven as in the following,

$\displaystyle\theta_{2}^{\star}=\begin{bmatrix}0.1048\\\
0.0216\end{bmatrix}\quad\Phi_{\theta_{2}}=\begin{bmatrix}0.00097&-0.00006\\\
-0.00006&0.00111\end{bmatrix}$ (62)

for $N=1000$ whereas with $\alpha=2$, it gains

$\displaystyle\theta_{2}^{\star}=\begin{bmatrix}0.1086\\\
0.0245\end{bmatrix}\quad\Phi_{\theta_{2}}=\begin{bmatrix}0.00046&-0.00002\\\
-0.00002&0.00059\end{bmatrix}$ (63)

##  VI Conclusion

The mathematical scenarios of switching from zero-mean to non zero-mean along
with from white to coloured have been studied to give better picture of the
mathematical characteristic from either families. The simulation designs have
been proposed in order to observe the effectiveness of certain number of
recursive $N$ along with the batches concept $\kappa$ compared to the hand
calculation of the optimal values. The greater number of $N$ and batches
$\kappa$ with the more complex design of estimate AR(2) results in better
approximation of the true system in terms of empirical mean and variance.
Further research is to compare another more complex families with modified
stochastic scenarios.

## Acknowledgment

Thanks to Professor Thomas Parisini from the Imperial College London who has
taught me in the lecture leading to finishing this paper and to LPDP
(Indonesia Endowment Fund for Education) Scholarship from Indonesia.

## References

  * [1] L. Ljung, T. Chen, and B. Mu, “A shift in paradigm for system identification,” _International Journal of Control_ , pp. 1–8, 2019.
  * [2] J. Nagumo and A. Noda, “A learning method for system identification,” _IEEE Transactions on Automatic Control_ , vol. 12, no. 3, pp. 282–287, June 1967.
  * [3] E. G. Hurst, “Bayesian autoregressive time series analysis,” _IEEE Transactions on Systems Science and Cybernetics_ , vol. 4, no. 3, pp. 317–324, Sep. 1968.
  * [4] J. Ding, S. Shahrampour, K. Heal, and V. Tarokh, “Analysis of multistate autoregressive models,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 9, pp. 2429–2440, May 2018.
  * [5] P. Stoica, “Prediction of autoregressive lognormal processes,” _IEEE Transactions on Automatic Control_ , vol. 25, no. 2, pp. 292–293, April 1980.
  * [6] Y. Nardi and A. Rinaldo, “Autoregressive process modeling via the lasso procedure,” _Journal of Multivariate Analysis_ , vol. 102, no. 3, pp. 528 – 549, 2011.
  * [7] R. K. Yedavalli, “Conditions for the existence of a common quadratic lyapunov function via stability analysis of matrix families,” in _Proceedings of the 2002 American Control Conference (IEEE Cat. No.CH37301)_ , vol. 2, May 2002, pp. 1296–1301 vol.2.
  * [8] C. Yang, J. Sun, Q. Zhang, and X. Ma, “Lyapunov stability and strong passivity analysis for nonlinear descriptor systems,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 60, no. 4, pp. 1003–1012, April 2013.
  * [9] W. R. Melvin, “Stability properties of functional difference equations,” _Journal of Mathematical Analysis and Applications_ , vol. 48, no. 3, pp. 749 – 763, 1974.
  * [10] M. V. Dragosevic and S. S. Stankovic, “A generalized least squares method for frequency estimation,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 37, no. 6, pp. 805–819, June 1989.
  * [11] M. Morf and T. Kailath, “Square-root algorithms for least-squares estimation,” _IEEE Transactions on Automatic Control_ , vol. 20, no. 4, pp. 487–497, August 1975.

##  VII Appendices

Appendix A \- $y(t)$

$\displaystyle\mathcal{H}=\;$ $\displaystyle\frac{1}{1-\lambda z^{-1}}$
$\displaystyle Y(z)=\;$
$\displaystyle\mathcal{Q}(z)\mathcal{H}(z)+\mathcal{V}(z)$ $\displaystyle
Y(z)+\frac{Y(z)}{\mathcal{H}(z)}=\;$ $\displaystyle
Y(z)+\mathcal{Q}(z)+\frac{\mathcal{V}(z)}{\mathcal{H}(z)}$ $\displaystyle
Y(z)=\;$ $\displaystyle
Y(z)-\frac{Y(z)}{\mathcal{H}(z)}+\mathcal{Q}(z)+\frac{\mathcal{V}(z)}{\mathcal{H}(z)}$
$\displaystyle=\;$ $\displaystyle
Y(z)\left[1-\frac{1}{\mathcal{H}(z)}\right]+\mathcal{Q}(z)+\frac{\mathcal{V}(z)}{\mathcal{H}(z)}$
$\displaystyle=\;$ $\displaystyle Y(z)\left[\lambda
z^{-1}\right]+\mathcal{Q}(z)+\mathcal{V}(z)\left[1-\lambda z^{-1}\right]$
$\displaystyle y(t)=\;$ $\displaystyle\lambda y(t-1)+q(t)+v(t)-\lambda v(t-1)$

Appendix B \- Expected Value $\textbf{E}_{y}$

$\displaystyle\textbf{E}[y(t)]=\;$ $\displaystyle\textbf{E}[\lambda
y(t-1)+q(t)+v(t)-\lambda v(t-1)]$ $\displaystyle=\;$
$\displaystyle\lambda\textbf{E}[y(t-1)]+\textbf{E}[q(t)]+\textbf{E}[v(t)]-\lambda\textbf{E}[v(t-1)]$
$\displaystyle=\;$
$\displaystyle\lambda\bar{y}+\bar{q}+\bar{v}-\lambda\bar{v}$
$\displaystyle=\;$ $\displaystyle\bar{v}+\dfrac{\bar{q}}{1-\lambda}$

Appendix C \- Variance $\Phi_{y}$

$\displaystyle\Phi_{y}=\;$
$\displaystyle\textbf{E}\left\\{[y(t)-\bar{y}]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left[y(t)^{2}-2y(t)\bar{y}+\bar{y}^{2}\right]$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left[y(t)^{2}\right]-\textbf{E}\left[\bar{y}^{2}\right]\longrightarrow\textbf{E}\left[\bar{y}^{2}\right]=0$
$\displaystyle=\;$ $\displaystyle\textbf{E}\left\\{\left[\underbrace{\lambda
y(t-1)+q(t)}_{A}+\overbrace{v(t)-\lambda v(t-1)}^{B}\right]^{2}\right\\}$
$\displaystyle=\;$ $\displaystyle\textbf{E}\left[A^{2}+2AB+B^{2}\right]$
$\displaystyle\textbf{E}\left[A^{2}\right]=\;$
$\displaystyle\textbf{E}\left[\lambda^{2}y(t-1)^{2}+2\lambda
y(t-1)q(t)+q(t)^{2}\right]$ $\displaystyle=\;$
$\displaystyle\textbf{E}\left[\lambda^{2}y(t-1)^{2}\right]+2\textbf{E}\left[\lambda
y(t-1)q(t)\right]+\textbf{E}\left[q(t)^{2}\right]$ $\displaystyle=\;$
$\displaystyle\lambda^{2}\Phi_{y}+\delta^{2}$
$\displaystyle\textbf{E}\left[2AB\right]=\;$ $\displaystyle
2\textbf{E}\left[\lambda y(t-1)v(t)-\lambda^{2}y(t-1)v(t-1)+q(t)v(t)\right.$
$\displaystyle-\lambda q(t)v(t-1)]$ $\displaystyle=\;$ $\displaystyle
2\textbf{E}\left[\lambda
y(t-1)v(t)\right]-2\lambda^{2}\textbf{E}\left[y(t-1)v(t-1)\right]$
$\displaystyle+2\textbf{E}\left[q(t)v(t)\right]-2\textbf{E}\left[\lambda
q(t)v(t-1)\right]$ $\displaystyle=\;$ $\displaystyle-2\lambda^{2}\xi^{2}$
$\displaystyle\textbf{E}\left[B^{2}\right]=\;$
$\displaystyle\textbf{E}\left[v(t)^{2}-2\lambda
v(t)v(t-1)+\lambda^{2}v(t-1)^{2}\right]$ $\displaystyle=\;$
$\displaystyle\textbf{E}\left[v(t)^{2}\right]-2\lambda\textbf{E}\left[v(t)v(t-1)\right]+\lambda^{2}\textbf{E}\left[v(t-1)^{2}\right]$
$\displaystyle=\;$ $\displaystyle\xi^{2}+\lambda^{2}\xi^{2}$
$\displaystyle\Phi_{y}=\;$
$\displaystyle\lambda^{2}\Phi_{y}+\delta^{2}-2\lambda^{2}\xi^{2}+\xi^{2}+\lambda^{2}\xi^{2}$
$\displaystyle=\;$ $\displaystyle\frac{\delta^{2}}{1-\lambda^{2}}+\xi^{2}$

Appendix D \- Covariance $\Psi_{y}$

$\displaystyle\Psi_{y}(\tau)=\;$
$\displaystyle\textbf{E}\Bigl{\\{}\left[y(t)-\bar{y}\right]\left[y(t-\tau)-\bar{y}\right]\Bigl{\\}}\longrightarrow\bar{y}=0$
$\displaystyle=\;$
$\displaystyle\textbf{E}\Bigl{\\{}\left[ay(t-1)+e(t)+v(t)-av(t-1)\right]\left[y(t-\tau)\right]\Bigl{\\}}$
$\displaystyle=\;$
$\displaystyle\lambda\textbf{E}\left[y(t-1)y(t-\tau)\right]+\textbf{E}\left[e(t)y(t-\tau)\right]$
$\displaystyle+\textbf{E}\left[v(t)y(t-\tau)\right]-\lambda\textbf{E}\left[v(t-1)y(t-\tau)\right]$
$\displaystyle\Psi_{y}(0)=\;$ $\displaystyle\lambda\Psi(1)+\delta^{2}+\xi^{2}$
$\displaystyle\Psi_{y}(1)=\;$ $\displaystyle\lambda\Psi(0)-\lambda\xi^{2}$
$\displaystyle\Psi_{y}(2)=\;$ $\displaystyle\lambda\Psi(1)$

Appendix D⋆ \- Covariance $\Psi_{y}(\tau)\longrightarrow\tau=0,1,2$

$\displaystyle\Psi_{y}(1)\coloneqq\;$
$\displaystyle\frac{\Psi(1)}{\lambda}+\xi^{2}=\lambda\Psi(1)+\delta^{2}+\xi^{2}$
$\displaystyle\coloneqq\;$
$\displaystyle\frac{\lambda\delta^{2}}{1-\lambda^{2}}$
$\displaystyle\Psi_{y}(0)\coloneqq\;$
$\displaystyle\lambda\frac{\lambda\delta^{2}}{1-\lambda^{2}}+\delta^{2}+\xi^{2}$
$\displaystyle\coloneqq\;$
$\displaystyle\frac{\delta^{2}}{1-\lambda^{2}}+\xi^{2}\longrightarrow\Phi_{y}$
$\displaystyle\Psi_{y}(2)\coloneqq\;$ $\displaystyle\lambda\Psi(1)$
$\displaystyle\coloneqq\;$
$\displaystyle\frac{\lambda^{2}\delta^{2}}{1-\lambda^{2}}\longrightarrow\frac{\lambda^{\tau}\delta^{2}}{1-\lambda^{2}}\textrm{
for }\Psi_{y}(\tau>1)$

Appendix E \- $\Gamma(\theta_{1})\longrightarrow\phi_{1}$

$\displaystyle\Gamma(\theta_{1})=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\hat{y}(t|t-1)\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\phi_{1}y(t-1)\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left[y(t)^{2}-2\phi_{1}y(t)y(t-1)+\phi^{2}_{1}y(t-1)^{2}\right]$
$\displaystyle=\;$
$\displaystyle\Psi_{y}(0)-2\phi_{1}\Psi_{y}(1)+\phi^{2}_{1}\Psi_{y}(0)$
$\displaystyle=\;$
$\displaystyle\left(1+\phi^{2}_{1}\right)\Psi_{y}(0)-2\phi_{1}\Psi_{y}(1)$
$\displaystyle\frac{\partial\Gamma(\theta_{1})}{\partial\phi_{1}}=\;$
$\displaystyle 2\phi_{1}\Psi_{y}(0)-2\Psi_{y}(1)=0$ $\displaystyle\phi_{1}=\;$
$\displaystyle\frac{\Psi_{y}(1)}{\Psi_{y}(0)}\longrightarrow\frac{\lambda\Psi_{y}(0)-\lambda\xi^{2}}{\Psi_{y}(0)}$
$\displaystyle=\;$
$\displaystyle\frac{\lambda\delta^{2}}{\delta^{2}+(1-\lambda^{2})\xi^{2}}$

Appendix F \-
$\Gamma(\theta_{2})\longrightarrow\theta_{2}^{\star}\coloneqq\left[\phi_{1},\phi_{2}\right]^{\top}$

$\displaystyle\Gamma(\theta_{2})=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\hat{y}(t|t-1)\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[y(t)-\phi_{1}y(t-1)-\phi_{2}y(t-2)\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left[y(t)^{2}+\phi^{2}_{1}y(t-1)^{2}+\phi^{2}_{2}y(t-2)^{2}\right.$
$\displaystyle-2\phi_{1}y(t)y(t-1)-2\phi_{2}y(t)y(t-2)$
$\displaystyle+2\phi_{1}\phi_{2}y(t-1)y(t-2)]$ $\displaystyle=\;$
$\displaystyle\Psi_{y}(0)+\phi_{1}^{2}\Psi_{y}(0)+\phi_{2}^{2}\Psi_{y}(0)-2\phi_{1}\Psi_{y}(1)$
$\displaystyle-2\phi_{2}\Psi_{y}(2)+2\phi_{1}\phi_{2}\Psi_{y}(1)$
$\displaystyle=\;$
$\displaystyle\left(1+\phi^{2}_{1}+\phi^{2}_{2}\right)\Psi_{y}(0)+2\phi_{1}\left(\phi_{2}-1\right)\Psi_{y}(1)$
$\displaystyle-2\phi_{2}\Psi_{y}(2)$
$\displaystyle\frac{\partial\Gamma(\theta_{2})}{\partial\phi_{1}}=\;$
$\displaystyle 2\phi_{1}\Psi_{y}(0)+2\phi_{2}\Psi_{y}(1)-2\Psi_{y}(1)=0$
$\displaystyle\phi_{1}=\;$
$\displaystyle\frac{\Psi_{y}(1)-\phi_{2}\Psi_{y}(1)}{\Psi_{y}(0)}$
$\displaystyle=\;$
$\displaystyle\frac{\Psi_{y}(1)-\left(\dfrac{\Psi_{y}(2)\Psi_{y}(0)-\Psi_{y}(1)^{2}}{\Psi_{y}(0)^{2}-\Psi_{y}(1)^{2}}\right)\Psi_{y}(1)}{\Psi_{y}(0)}$
$\displaystyle=\;$
$\displaystyle\frac{\Psi_{y}(1)\Psi_{y}(0)-\Psi_{y}(2)\Psi_{y}(1)}{\Psi_{y}(0)^{2}-\Psi_{y}(1)^{2}}$
$\displaystyle=\;$
$\displaystyle\frac{\lambda\delta^{2}\left(\delta^{2}+\xi^{2}\right)}{\left(\delta^{2}+\xi^{2}\right)^{2}-\lambda^{2}\xi^{4}}$
$\displaystyle\frac{\partial\Gamma(\theta_{2})}{\partial\phi_{1}}=\;$
$\displaystyle 2\phi_{2}\Psi_{y}(0)+2\phi_{1}\Psi_{y}(1)-2\Psi_{y}(2)=0$
$\displaystyle\phi_{2}=\;$
$\displaystyle\frac{\Psi_{y}(2)-\phi_{1}\Psi_{y}(1)}{\Psi_{y}(0)}$
$\displaystyle=\;$
$\displaystyle\frac{\Psi_{y}(2)-\left(\dfrac{\Psi_{y}(1)\Psi_{y}(0)-\Psi_{y}(2)\Psi_{y}(1)}{\Psi_{y}(0)^{2}-\Psi_{y}(1)^{2}}\right)\Psi_{y}(1)}{\Psi_{y}(0)}$
$\displaystyle=\;$
$\displaystyle\frac{\Psi_{y}(2)\Psi_{y}(0)-\Psi_{y}(1)^{2}}{\Psi_{y}(0)^{2}-\Psi_{y}(1)^{2}}$
$\displaystyle=\;$
$\displaystyle\frac{\lambda^{2}\delta^{2}\xi^{2}}{\left(\delta^{2}+\xi^{2}\right)^{2}-\lambda^{2}\xi^{4}}$

Appendix G \- $\Phi_{\theta_{1}^{\star}}$ and $\Phi_{\theta_{2}^{\star}}$

$\displaystyle\Phi_{\theta_{1}^{\star}}=\;$
$\displaystyle\Gamma(\theta_{1})=\textbf{E}\left\\{\left[\varepsilon_{\theta_{1}}(t)-\bar{\varepsilon}_{\theta_{1}}\right]^{2}\right\\}\longrightarrow\bar{\varepsilon}_{\theta_{1}}=0$
$\displaystyle=\;$
$\displaystyle\left[1+\phi_{1}^{2}\right]\Psi_{y}(0)-2\phi_{1}\Psi_{y}(1)\longrightarrow\phi_{1}\textrm{
from Eq. (21)}$ $\displaystyle=\;$
$\displaystyle\left[1+\left(\frac{\lambda\delta^{2}}{\delta^{2}+(1-\lambda^{2})\xi^{2}}\right)^{2}\right]\frac{\delta^{2}+(1-\lambda^{2})\xi^{2}}{1-\lambda^{2}}$
$\displaystyle-2\left(\frac{\lambda\delta^{2}}{\delta^{2}+(1-\lambda^{2})\xi^{2}}\right)\frac{\lambda\delta^{2}}{1-\lambda^{2}}$
$\displaystyle=\;$
$\displaystyle\frac{\left[\delta^{2}+\left(1-\lambda^{2}\right)\xi^{2}\right]^{2}-\lambda^{2}\delta^{4}}{\left[\delta^{2}+\left(1-\lambda^{2}\right)\xi^{2}\right]\left[1-\lambda^{2}\right]}$
$\displaystyle=\;$
$\displaystyle\frac{\delta^{4}\left(1-\lambda^{2}\right)+2\delta^{2}\xi^{2}\left(1-\lambda^{2}\right)+\xi^{4}\left(1-\lambda^{2}\right)^{2}}{\left[\delta^{2}+\left(1-\lambda^{2}\right)\xi^{2}\right]\left[1-\lambda^{2}\right]}$
$\displaystyle=\;$
$\displaystyle\frac{\left(\delta^{2}+\xi^{2}\right)^{2}-\lambda^{2}\xi^{4}}{\delta^{2}+\left(1-\lambda^{2}\right)\xi^{2}}$
$\displaystyle\Phi_{\theta_{2}^{\star}}=\;$
$\displaystyle\Gamma(\theta_{2})=\textbf{E}\left\\{\left[\varepsilon_{\theta_{2}}(t)-\bar{\varepsilon}_{\theta_{2}}\right]^{2}\right\\}\longrightarrow\bar{\varepsilon}_{\theta_{2}}=0$
$\displaystyle=\;$
$\displaystyle\left[1+\phi_{1}^{2}+\phi_{2}^{2}\right]\Psi_{y}(0)-\left[2\phi_{1}-2\phi_{1}\phi_{2}\right]\Psi_{y}(1)$
$\displaystyle-2\phi_{2}\Psi_{y}(2)\longrightarrow[\phi_{1},\phi_{2}]\textrm{
from Eq. (22)}$ $\displaystyle=\;$
$\displaystyle\Psi_{y}(0)^{3}-\Psi_{y}(2)^{2}\Psi_{y}(0)-2\Psi_{y}(1)^{2}\Psi_{y}(0)$
$\displaystyle+2\Psi_{y}(1)^{2}\Psi_{y}(2)\longrightarrow\textrm{after some
complex-algebra}$ $\displaystyle=\;$
$\displaystyle\left(\frac{\delta^{2}+(1-\lambda^{2})\xi^{2}}{1-\lambda^{2}}\right)^{3}-\left(\frac{\lambda^{2}\delta^{2}}{1-\lambda^{2}}\right)^{2}\frac{\delta^{2}+(1-\lambda^{2})\xi^{2}}{1-\lambda^{2}}$
$\displaystyle-2\left(\frac{\lambda\delta^{2}}{1-\lambda^{2}}\right)^{2}\frac{\delta^{2}+(1-\lambda^{2})\xi^{2}}{1-\lambda^{2}}+2\lambda\left(\frac{\lambda\delta^{2}}{1-\lambda^{2}}\right)^{3}$
$\displaystyle=\;$
$\displaystyle\frac{\left(\delta^{2}+\xi^{2}\right)^{3}-\lambda^{2}\left(\delta^{2}\xi+\xi^{3}\right)^{2}+2\lambda\delta^{4}\xi^{2}}{1-\lambda^{2}}$

Appendix H \- $\Gamma(\theta_{1})\longrightarrow\phi_{1}$; (non) zero-mean

$\displaystyle\Gamma(\theta_{1})=\;$
$\displaystyle\textbf{E}\left[y(t)^{2}-2y(t)y(t|t-1)+y(t|t-1)^{2}\right]$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[\check{y}(t)+\bar{y}\right]^{2}\right\\}-2\phi_{1}\textbf{E}\Bigl{\\{}\left[\check{y}(t)+\bar{y}\right]\left[\check{y}(t-1)+\bar{y}\right]\Bigl{\\}}$
$\displaystyle+\phi_{1}^{2}\textbf{E}\left\\{\left[\check{y}(t-1)+\bar{y}\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\left[1+\phi_{1}^{2}\right]\Psi_{y}(0)-2\phi_{1}\Psi_{y}(1)+\left(1-\phi_{1}\right)^{2}\bar{y}^{2}$
$\displaystyle\frac{\partial\Gamma(\theta_{1})}{\partial\phi_{1}}=\;$
$\displaystyle-2\Psi_{y}(1)+2\phi_{1}\Psi_{y}(0)-2\left(1-\phi_{1}\right)\bar{y}^{2}=0$
$\displaystyle\theta^{\star}_{1}\coloneqq\;$
$\displaystyle\frac{\Psi(1)+\bar{y}^{2}}{\Psi(0)+\bar{y}^{2}}$

Appendix I \-
$\Gamma(\theta_{2})\longrightarrow\theta_{2}^{\star}\coloneqq\left[\phi_{1},\phi_{2}\right]^{\top}$;
(non) zero-mean

$\displaystyle\Gamma(\theta_{2})=\;$
$\displaystyle\textbf{E}\left[y(t)^{2}-2y(t)y(t|t-1)+y(t|t-1)^{2}\right]$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[\check{y}(t)+\bar{y}\right]^{2}\right\\}-2\textbf{E}\Bigl{\\{}\left[\check{y}(t)+\bar{y}\right]\left[\phi_{1}\check{y}(t-1)\right.\Bigl{.}$
$\displaystyle+\Bigl{.}\left.\phi_{2}\check{y}(t-2)+\left(\phi_{1}+\phi_{2}\right)\bar{y}\right]\Bigl{\\}}+\phi_{1}^{2}\textbf{E}\left\\{\left[\check{y}(t-1)\right]^{2}\right\\}$
$\displaystyle+\phi_{2}^{2}\textbf{E}\left\\{\left[\check{y}(t-2)\right]^{2}\right\\}+\left(\phi_{1}+\phi_{2}\right)\textbf{E}\left\\{\left[\bar{y}\right]^{2}\right\\}$
$\displaystyle+2\phi_{1}\left(\phi_{1}+\phi_{2}\right)\textbf{E}\left\\{\left[\check{y}(t-1)\bar{y}\right]\right\\}$
$\displaystyle+2\phi_{2}\left(\phi_{1}+\phi_{2}\right)\textbf{E}\left\\{\left[\check{y}(t-2)\bar{y}\right]\right\\}$
$\displaystyle+2\phi_{1}\phi_{2}\textbf{E}\left\\{\left[\check{y}(t-1)\check{y}(t-2)\right]\right\\}$
$\displaystyle=\;$
$\displaystyle\Psi_{y}(0)+\phi_{1}^{2}\Psi_{y}(0)+\phi_{2}^{2}\Psi_{y}(0)-2\phi_{1}\Psi_{y}(1)$
$\displaystyle-2\phi_{2}\Psi_{y}(2)+2\phi_{1}\phi_{2}\Psi_{y}(1)+\left[1-\left(\phi_{1}+\phi_{2}\right)\right]^{2}\bar{y}^{2}$
$\displaystyle\frac{\partial\Gamma(\theta_{2})}{\partial\phi_{1}}=\;$
$\displaystyle 0\textrm{ and
}\frac{\partial\Gamma(\theta_{2})}{\partial\phi_{2}}=\;0$

after some complex-algebra

$\displaystyle\phi_{1}=\;$
$\displaystyle\dfrac{\Psi_{y}(1)\Psi_{y}(0)-\Psi_{y}(2)\Psi_{y}(1)+\bar{y}^{2}\left[\Psi(0)-\Psi(2)\right]}{\Psi_{y}(0)^{2}-\Psi_{y}(1)^{2}+2\bar{y}^{2}\left[\Psi(0)-\Psi(1)\right]}$
$\displaystyle\phi_{2}=\;$
$\displaystyle\dfrac{\Psi_{y}(2)\Psi_{y}(0)-\Psi_{y}(1)^{2}+\bar{y}^{2}\left[\Psi(0)-2\Psi(1)+\Psi(2)\right]}{\Psi_{y}(0)^{2}-\Psi_{y}(1)^{2}+2\bar{y}^{2}\left[\Psi(0)-\Psi(1)\right]}$

Appendix J \- $\Phi_{\theta_{1}^{\star}}$ and $\Phi_{\theta_{2}^{\star}}$;
(non) zero-mean

$\displaystyle\bar{\varepsilon}_{\theta_{1}}=\;$
$\displaystyle\textbf{E}\left[\check{y}(t)\right]+\textbf{E}\left[\bar{y}\right]-\phi_{1}\textbf{E}\left[\check{y}(t-1)\right]-\phi_{1}\textbf{E}\left[\bar{y}\right]$
$\displaystyle=\;$ $\displaystyle(1-\phi_{1})\bar{y}$
$\displaystyle\Phi_{\theta_{1}^{\star}}=\;$
$\displaystyle\Gamma(\theta_{1})=\textbf{E}\left\\{\left[\varepsilon_{\theta_{1}}(t)-\bar{\varepsilon}_{\theta_{1}}\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[\check{y}(t)+\bar{y}-\phi_{1}\check{y}(t-1)-\phi_{1}\bar{y}-\left(1-\phi_{1}\right)\bar{y}\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[\check{y}(t)-\phi_{1}\check{y}(t-1)\right]^{2}\right\\}\longrightarrow\textrm{{Appendix
E}}$ $\displaystyle=\;$
$\displaystyle\frac{\left(\delta^{2}+\xi^{2}\right)^{2}-\lambda^{2}\xi^{4}}{\delta^{2}+\left(1-\lambda^{2}\right)\xi^{2}}\longrightarrow\textrm{{Appendix
G}}$ $\displaystyle\bar{\varepsilon}_{\theta_{2}}=\;$
$\displaystyle\textbf{E}\left[\check{y}(t)\right]+\textbf{E}\left[\bar{y}\right]-\phi_{1}\textbf{E}\left[\check{y}(t-1)\right]-\phi_{2}\textbf{E}\left[\check{y}(t-2)\right]$
$\displaystyle-\left(\phi_{1}+\phi_{2}\right)\textbf{E}\left[\bar{y}\right]$
$\displaystyle=\;$ $\displaystyle(1-\phi_{1}-\phi_{2})\bar{y}$
$\displaystyle\Phi_{\theta_{2}^{\star}}=\;$
$\displaystyle\Gamma(\theta_{2})=\textbf{E}\left\\{\left[\varepsilon_{\theta_{2}}(t)-\bar{\varepsilon}_{\theta_{2}}\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\Bigl{\\{}\left[\check{y}(t)+\bar{y}-\phi_{1}\check{y}(t-1)-\phi_{2}\check{y}(t-2)\right.\Bigl{.}$
$\displaystyle\Bigl{.}\left.-\left(\phi_{1}+\phi_{2}\right)\bar{y}-\left(1-\phi_{1}-\phi_{2}\right)\bar{y}\right]^{2}\Bigl{\\}}$
$\displaystyle=\;$
$\displaystyle\textbf{E}\left\\{\left[\check{y}(t)-\phi_{1}\check{y}(t-1)-\phi_{2}\check{y}(t-2)\right]^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle\frac{\left(\delta^{2}+\xi^{2}\right)^{3}-\lambda^{2}\left(\delta^{2}\xi+\xi^{3}\right)^{2}+2\lambda\delta^{4}\xi^{2}}{1-\lambda^{2}}$

## Authors

First and Correspondence Author \- Moh Kamalul Wafi was graduated from the
Imperial College London majoring Control Systems under Department of
Electrical and Electronics Engineering. I am currently with the Laboratory of
Embedded and Cyber-Physical Systems, Department of Engineering Physics,
Institut Teknologi Sepuluh Nopember, 60111, Indonesia


11institutetext:  School of Computing and Informatics,
University of Louisiana at Lafayette, Louisiana, USA 11email:
<EMAIL_ADDRESS>22institutetext: Faculty of Information
Technology, Monash University, Victoria, Australia 22email:
<EMAIL_ADDRESS>33institutetext: Brightcove Inc. , Arizona, USA
33email<EMAIL_ADDRESS>
# Leveraging Computational Reuse for Cost- and QoS-Efficient Task Scheduling
in Clouds

Chavit Denninnart 11 Mohsen Amini Salehi 11 Adel Nadjaran Toosi 22 Xiangbo Li
33

###### Abstract

Cloud-based computing systems could get oversubscribed due to budget
constraints of cloud users which causes violation of Quality of Experience
(QoE) metrics such as tasks’ deadlines. We investigate an approach to achieve
robustness against uncertain task arrival and oversubscription through smart
reuse of computation while similar tasks are waiting for execution. Our
motivation in this study is a cloud-based video streaming engine that
processes video streaming tasks in an on-demand manner. We propose a mechanism
to identify various types of “mergeable” tasks and determine when it is
appropriate to aggregate tasks without affecting QoS of other tasks.
Experiment shows that our mechanism can improve robustness of the system and
also saves the overall time of using cloud services by more than 14%.

###### Keywords:

Task Aggregation Oversubscription Cloud Computing Video Stream Processing Task
Scheduling

##  1 Introduction

With Cloud and Edge Computing gaining more popularity as the back-end platform
of many applications, the need for efficient use of these platforms is of
paramount importance for individual users and businesses. A common practice to
efficiently utilize cloud resources is to use a central queue of arriving
tasks with a scheduler that allocates these tasks to a scalable pool of worker
Virtual Machines (VMs). The tasks often have individual deadlines that failure
to meet them compromises the Quality of Experience (QoE) expected by the end-
users.

Although cloud providers supply virtually unlimited resources, users generally
have budget constraints, thus, cannot lavishly acquire cloud resources (VMs)
[2]. Such limitation raises the _oversubscription_ problem, particularly, when
there is a surge in the tasks arriving to the system. An oversubscribed system
is defined as a system that is overwhelmed with arriving tasks to the extent
that there is no way to meet the deadlines of all the tasks, thus, violating
end-users’ QoE.

A large body of research has been dedicated to alleviate the oversubscription
problem. The approaches undertaken in these research works follow two main
lines of thinking; First, _allocation-based approaches_ that try to minimize
the impact of oversubscription through efficient mapping (scheduling) of the
tasks to the resources. Second, approaches based on _computational reuse_ that
avoid or alleviates the oversubscription through efficient caching of the
computational results.

Although both of the aforementioned approaches are effective, they are limited
in certain ways. The allocation-based approaches cannot entirely resolve the
oversubscription because there is no such a solution according to the above-
mentioned definition. In addition, many of the approaches are based on complex
scheduling algorithms that impose extra overhead to the already oversubscribed
system. The approaches based on computational reuse are also limited because
they can only reuse the computations for tasks that are identical to the ones
already completed and cached. In other words, if two tasks share part of their
computation, it cannot be captured by current caching techniques.

In this research, we propose a mechanism based on computational reuse that
aims at alleviating oversubscription by aggregating identical and similar
tasks in the scheduling queue. Our mechanism makes the scheduling queue less
busy and potentially lighten up the overhead of the scheduling process. It
complements the existing scheduling-based and caching-based approaches but is
not a replacement for them.

We define _mergeable_ tasks as those tasks that are either identical or
sharing part of their operation with other tasks. We need a mechanism to,
first, detect different types of mergeable tasks and, second, eliminate the
detected mergeable tasks from the scheduling queue without causing further
deadline violations in the system.

Our motivational case study in this research is a video streaming engine that
needs to process videos (e.g., downsizing resolution or bit-rate) in the cloud
before streaming them to viewers [1]. In this system, it is likely that
viewers request same videos to be streamed, hence, creating similar tasks in
the system especially when the system is oversubscribed. For example, two
viewers who use similar display devices may request to stream the same video
with the same or different specifications. The former case creates _identical_
tasks in the system whereas the latter one creates _similar_ tasks.

In this research, we develop an Admission Control component that is able to
detect different levels of similarity between tasks. The system is aware of
the tasks’ deadlines and performs merging without introducing additional
deadline violations. The task aggregation also results in efficient
utilization of resources and enable more tasks to meet their deadlines.
Therefore, both viewers and system providers can be benefited from the
proposed mechanism. In summary, the key contributions of this research are as
follows: (A) Proposing an efficient way of identifying potentially mergeable
tasks; (B) Determining appropriateness and potential side-effects of merging
tasks; (C) Analyzing the performance of the task aggregation mechanism on the
viewers’ QoE and time of deploying cloud resources (VMs).

Although we develop this mechanism in the context of video streaming, the idea
of task aggregation and research findings of this work are valid for other
domains.

##  2 Background for Merge-Aware Admission Control

While storing multiple versions of the same video to serve different types of
display devices is a conventional practice, Cloud-based Video Streaming Engine
(CVSE) [6] enables on-demand (i.e., lazy) processing of video streams,
particularly for rarely accessed video streams [3].

Figure 1: Overview of Merge-Aware Admission Control for CVSE system

In the CVSE architecture, each task is a GOP (Group Of Picture) of the
requested video stream. A GOP task request (hereafter, called task) includes
the operation required along with the corresponding parameters bound to that
request. Admission Control component, as shown in Figure 1, sends the task to
the batch queue (aka scheduling queue) where the task waits to be assigned by
the scheduling policy [4] to one of multiple VMs’ queues. Most of the
scheduling policies are reliant on the Time Estimator component that is aware
of the expected execution time of each task type (e.g., different transcoding
operations) on the cloud VMs [5]. Tasks get executed on the assigned VM and
streamed to the viewer (More details about CVSE is in [5, 6]).

In this paper, we develop our task aggregation mechanism inside Admission
Control component of CVSE. For an arriving task, Admission Control recognizes
if it is mergeable with the ones exist in the batch queue or local queues of
the VMs. Then, the Admission Control decides the feasibility of merging (i.e.,
if merging causes deadline violation for other tasks).

##  3 Task Similarity Detection

###  3.1 Categories of Mergeable Tasks

Mergeability of two given tasks can be explained based on the amount of
computation the two tasks share. In particular, mergeability of two or more
tasks can be achieved in the following levels:

  1. (A)

_Task-level_ : This is when more than one instance of the same task exists in
the scheduling queue. Therefore, this level is also known as _Identical tasks_
and can achieve maximum computational reusability. As these tasks are
identical, merging them consumes the same resources required for only one
task, hence, reducing both cost and processing delay.

  2. (B)

_Operation-level_ : This is when two or more tasks perform the same operation
on the same data but with different configurations. In this level of merging,
the two tasks can share part of their processing.

  3. (C)

_Data-level_ : This is when two or more tasks perform different operations on
the same data. This level of merging achieves the minimum reusability by
saving only the time and processing overhead of loading data.

It is noteworthy that the aforementioned reusability levels are generic and
can be further categorized depending on the context.

###  3.2 Detecting Similar Tasks

In this section, we provide a method to detect similar tasks. Although our
solution carry out task aggregation using Admission Control component. We
would like to note that, it is theoretically possible to carry out task
merging in the scheduling queue, i.e., after the task admission. In this case,
to find mergeable tasks, we need to scan the entire queue and perform a pair-
wise matching between the queued tasks. Practically, this approach is not
efficient, because each time the queue is scanned, it imposes a significant
number of redundant comparisons. Hence, we choose to perform task merging upon
task arrival using the Admission Control component of the system.

Assuming there are $n$ tasks in the queue, for each arriving task, a naïve
mergeable task detection method has the overhead of performing $n$ comparisons
to find the mergeable tasks. To reduce the overhead, we propose a method that
functions based on the hashing techniques. The general idea of the proposed
method is to generate a hash key from the arriving task request signature
(e.g., GOP id, processing type, and their parameters). Then, the Admission
Control finds mergeable tasks by searching for a matching key in the hash
table of tasks exist in the scheduling queue.

The explained method can detect task-level mergeability. We need to expand it
to detect operation- and data-level of task mergeabilities. To maximize the
computational reusability, an arriving task is first verified against task-
level mergeability. If there is no match in the task-level, then the method
proceeds with checking the next levels of mergeability, namely operation-level
and data-level, respectively. To achieve the multiple levels of mergeability,
we create three hash-tables —each covers one level of mergeability. The hash-
keys in each level are constructed from the tasks’ characteristics that are
relevant in deciding mergeability at that level. For instance, in video
streaming case study, keys in the hash-table that verifies task-level
mergeability are constructed from GOP id, processing type, and their
parameters. While, keys in the hash-table that verifies operation-level
mergeability are constructed from GOP id and processing type. Similarly, keys
in the hash-table of data-level mergeability are constructed from GOP id.

Upon arrival of task $j$: (1) if $j$ merges with existing task $i$ on Task-
level similarity: – No update on hash-table is required (2) if $j$ merges with
existing task $i$ on Operation- or Data-level similarity: – Add an entry to
each hash-table with hash-keys of task $j$ and point them to merged task $i+j$
(3) if $j$ matches with existing task $i$ but the system chooses not to merge
them: – Add an entry to each hash-table with hash-keys of task $j$ and point
them to task $j$ (4) if $j$ does not match with any of the existing tasks: –
Hash-keys of task $j$ are added to the respective hash-tables Upon task $j$
completing execution (i.e., dequeuing task $j$): – Remove all entries pointing
to task $j$ from hash-tables Figure 2: The procedure to update hash-tables
upon arrival or completion of tasks

Each entry of the hash-tables includes a hash-key and a pointer to the
corresponding task. Entries of the three hash-tables must be updated upon a
task arrival and execution. The only exception is Task-level merging, which
does not require updating the hash-tables. Figure 2 shows the procedure for
updating the hash-tables for a given task $j$.

When the system merges task $j$ with existing task $i$, the merged task,
denoted as $i+j$, is essentially the object of task $i$ that is augmented with
request information (e.g., processing parameters) of task $j$. In this case,
as shown in Step (2) of this procedure, the system only adds an entry to each
hash-table with hash-key of task $j$ pointing to merged task $i+j$ as existing
key for task $i$ already pointed to task $i+j$. When task $j$ is mergeable
with existing task $i$, but the system decides to add task $j$ to the batch
queue without merging. In this case, task $j$ has a higher likelihood of
merging with other arriving tasks. The reason is that task $i$ has not merged
with task $j$ and it does not merge with other arriving tasks. Hence, as shown
in Step (3) of the procedure, the matching entry pointing to task $i$ is
redirected and points to task $j$. It is worth noting that if the arriving
task does not match with any of the existing tasks, as shown in Step (4), its
hash-keys must be generated and added to the respective hash-tables. Also,
when a task completes its execution, its corresponding entries are removed
from the hash-tables.

##  4 Identifying Merging Appropriateness

Imagine an arriving task merges into an existing task in the queue. If such
merging is not a Task-level similarity, the execution time of merged task is
increased compared to a task before merging. The increased execution time
delays the execution of other tasks waiting behind in the queue which could
result in deadline violations. Therefore it is critical to assess the impact
of merging tasks before performing the merge.

Impact of merging can be assess based on additional deadline misses of tasks
following merged tasks when merging occurred against without. Impact of
merging assessor create virtual copies of scheduling queue in two scenarios:
with merging occurred and without. It simulates the scheduling and estimates
completion time of each task, then compares to its deadline. Merging is only
carried out if it does not cause additional deadline violations than it would
normally happen if the tasks are not merged.

The estimated completion time of task $i$ on a given machine $m$, denoted as
$C_{i}^{m}$ and formally shown in Equation 1, is calculated as the sum of the
four following factors: (A) current time, denoted $\tau$; (B) estimated
remaining time to complete the currently executing task on machine $m$,
denoted $e_{r}^{m}$; (C) sum of the estimated execution times of $N$ tasks
pending in machine queue $m$, ahead of task $i$. This is calculated as
$\sum_{p=1}^{N}(\mu_{p}+2\cdotp\sigma_{p})$; (D) estimated execution time of
task $i$.

$C_{i}^{m}=\tau+e_{r}^{m}+\sum_{p=1}^{N}(\mu_{p}+2\cdotp\sigma_{p})+(\mu_{i}+2\cdotp\sigma_{i})$
(1)

##  5 Performance Evaluation

###  5.1 Experimental Setup

We implemented a prototype of CVSE with task aggregation mechanism equipped.
It is designed to operate in different modes, namely real streaming mode and
emulation mode that is used for testing purposes [6]. In this study, to
examine various workloads, we used CVSE in the emulation mode. We evaluated
the proposed mechanism using eight homogeneous VMs modeled after Amazon GPU
(g2.2xlarge) VM.

The video repository we used for evaluation includes multiple replicas of a
set of benchmark videos. Videos in the benchmarking set are diverse both in
terms of the content types and length. The length of the videos in the
benchmark varies in the range of [10, 600] seconds splitting into 10-110 Group
Of Picture (GOP) segments. The benchmark videos are publicly available for
reproducibility purposes at https://goo.gl/TE5iJ5. For each GOP of the
benchmark videos, we obtained their processing times by executing each
processing operation 30 times on Amazon GPU VM. The processing operations we
benchmarked are: reducing resolution, changing codec, adjusting bit rate, and
changing frame rate.

To evaluate the system under various workload intensities, we generate [2000,
3000] GOP processing tasks within a fixed time interval. We collect the
deadline miss-rate (DMR) and makespan (i.e., execution time to finish all
tasks) of completing all tasks. We conducted each experiment 30 times, each
time with random task arrival time and order. Mean and 95% confidence interval
of the results are reported. We examined three queuing policies, namely FCFS
(First-Come-First-Serve), EDF (Earliest Deadline First), and MU (Max Urgency).
For each queuing policy, we studied no task merging versus task merging. In
the experiments, all tasks must be comepleted, even if they miss their
deadline.

###  5.2 Impact of Task Aggregation

Figure 3: Comparing the total time to complete tasks (i.e., makespan) under
varying number of arriving GOP tasks (horizontal axes) in two scenarios:
without task merging, and with task merging.

#### Evaluating Makespan:

In the first experiment, our goal is to see the impact of task merging on
makespan. In fact, makespan implies the time cloud resources are deployed,
which implies the cost incurred to execute all the tasks. We examine the
system under various subscription levels (from 2000 to 3200 GOPs) arriving
within the same time interval. As we can see in Figure 3, our proposed merging
mechanism saves between 4.40% and 14.33% in makespan. Execution time saving is
more pronounced when the system is more oversubscribed. It is worth noting
that makespan does not vary under different scheduling policies.

#### Evaluating Deadline Miss Rate (DMR):

In this experiment, our goal is to evaluate viewers’ QoE. For that purpose, we
measure the deadline miss rate resulted from no merging versus merging tasks
under various oversubscribed levels and with different scheduling policies. As
shown in Figure 4, we observe that task aggregation significantly reduces
deadline miss rate in all scheduling policies. We can see that the improvement
in deadline miss rate of FCFS is less than EDF and MU scheduling policies.
This is because FCFS by nature causes a larger average waiting time and does
not schedule tasks by considering their deadline. Therefore, task merging
mechanism performance, when combined with FCFS, is lower than other scheduling
polices.

Comparing the results shown in Figure 3 with those in Figure 4 reveals that
the difference in deadline miss rate is more dramatic than the makespan time.
This is due to the fact that even small reduction in task completion time can
cause the merged tasks meet their deadlines instead of missing that. We can
conclude that the impact of task aggregation mechanism on viewers’ QoE can
become more remarkable when it is combined with efficient scheduling policies.

(a) DMR under FCFS Queue (b) DMR under EDF Queue (c) DMR under MU Queue

Figure 4: Comparing the deadline miss-rate (DMR) under varying number of GOP
tasks (horizontal axes) in two scenarios: without task merging, and with task
merging. Subfigures (a), (b), and (c) show the DMR under FCFS, EDF, and MU
queuing polices.

##  6 Related works

Software-based computational reuse has been extensively researched and used.
However, not many systems can merge and reuse tasks before tasks are actually
executed and many of them tie very closely to one specific application. Below
are some notable works in this area.

Popa _et al._ [8] presented modules to identify identical and similar tasks to
cache partial results and reuse them on incremental computation specifically
on Dryad platform context. They proposed two solutions: One solution
automatically caches computational results. Another solution merges tasks
based on programmer’s defined merge function. Their first solution is a
caching system while their second solution is similar to our work, but more
specific to Dryad platform which does not have deadline and QoE to consider.

Paulo and Pereira _et al._ [7] developed a system to perform deduplication of
high throughput data using $Bloomfilters$. $Bloomfilters$, while fast, have
chances of giving false positive hash checking. Therefore they achieve lower
overhead data duplicate detection than hash table approach we use, at the
price of compromised accuracy.

##  7 Conclusion and Future works

In this paper, we improve efficiency of the system in oversubscribed condition
by merging arriving tasks with other (exact or similar) tasks. We dealt with
two challenges: First, how to identify identical and similar tasks in an
efficient manner? Second, how to perform merging without violating the
deadline of other tasks in the system? To address the first challenge, we
identified three main levels of similarity that tasks can be merged. Then, we
developed a method to detect different levels of task similarity within a
constant time complexity. To address the second challenge, we developed a
method that determines impact of merging and only perform merge operations if
other tasks’ deadline are not affected. Experimental results demonstrate that
the proposed system can reduce the overall execution time of tasks by more
than 14%, hence, cloud VMs can be deployed for a shorter time. This benefit
comes with improving QoE of the users. Although we implemented this system in
the context of video streaming, the concept can be applied to other domains as
long as we can define similarity levels in those domains. In the future, we
plan to extend this work by exploring the impact of marginally compromising
QoE, in favor of a remarkable cost-saving on the cloud resources.

## Acknowledgments

This research was supported by the Louisiana Board of Regents under grant
number LEQSF(2016-19)-RD-A-25.

## References

  * [1] I. Ahmad, X. Wei, Y. Sun, and Y.-Q. Zhang.  Video transcoding: an overview of various techniques and research issues.  IEEE Transactions on multimedia, 7(5):793–804, Oct 2005.
  * [2] J. Bi, H. Yuan, W. Tan, M. Zhou, Y. Fan, J. Zhang, and J. Li.  Application-aware dynamic fine-grained resource provisioning in a virtualized cloud data center.  IEEE Transactions on Automation Science and Engineering, 14(2):1172–1184, Apr 2017.
  * [3] M. Darwich, E. Beyazit, M. A. Salehi, and M. Bayoumi.  Cost efficient repository management for cloud-based on-demand video streaming.  In Proceedings of the 5th IEEE International Conference on Mobile Cloud Computing, Services, and Engineering, pages 39–44, Apr 2017.
  * [4] M. Hosseini, M. A. Salehi, and R. Gottumukkala.  Enabling Interactive Video Stream Prioritization for Public Safety Monitoring through Effective Batch Scheduling.  In Proceedings of the 19th IEEE International Conference on High Performance Computing and Communications, HPCC ’17, Dec 2017.
  * [5] X. Li, M. A. Salehi, M. Bayoumi, and R. Buyya.  CVSS: A Cost-Efficient and QoS-Aware Video Streaming Using Cloud Services.  In Proceedings of the 16th IEEE/ACM International Conference on Cluster Cloud and Grid Computing, CCGrid ’16, pages 106–115, May 2016.
  * [6] X. Li, M. A. Salehi, M. Bayoumi, N.-F. Tzeng, and R. Buyya.  Cost-Efficient and Robust On-Demand Video Stream Transcoding Using Heterogeneous Cloud Services.  IEEE Transactions on Parallel and Distributed Systems (TPDS), 29(3):556–571, Mar 2018.
  * [7] J. Paulo and J. Pereira.  Distributed exact deduplication for primary storage infrastructures.  In Proceedings of the 14th IFIP International Conference on Distributed Applications and Interoperable Systems, pages 52–66, Jun 2014.
  * [8] L. Popa, M. Budiu, Y. Yu, and M. Isard.  DryadInc: Reusing work in large-scale computations.  In Proceedings of 1st USENIX workshop on Hot Topics in Cloud Computing, HotCloud ’09, Jun 2009.