The paper is devoted to the analysis of the possibilities of using Markov chains for analyzing the accuracy of stochastic gradient relay estimation of image geometric deformations. One of the ways to reduce computational costs is to discretize the domain of studied parameters. This approach allows to choose the dimension of transition probabilities matrix a priori. However, such a matrix has a rather complicated structure. It does not significantly reduce the number of computations. A modification of the transition probabilities matrix is proposed, it's dimension does not depend on the dimension of estimated parameters vector. In this case, the obtained relations determine a recurrent algorithm for calculating the matrix at the estimation iterations. For the one-step transitions matrix, the calculated expressions for the probabilities of image deformation parameters estimates drift are given.
[9]. The next parameter estimate α i is determined as: αˆi,t =αˆi,t − λi,t−1 sign (∂Qˆi ( Ζ1, Ζ2 , αˆ t−1 ) ∂α i ) , αˆi0 ∈ Ω(α) , (1) (2) where Ω(α) is the domain of α . The estimates sequence t = 1,T [9]:
T w(αˆ 0 , αˆ 1, ..., αˆ T ) = w(αˆ 0 ) ∏t=1 π t (αˆ t | αˆ t−1 ) .
The apparatus for analysis of Markov sequences makes it possible to take into account the finiteness of the domain Ωαˆ of possible values of IID parameter estimates for different rules of PD behavior at the boundaries of parameter domain.
If the domain Ωαˆ of αˆ t is continuous, then the sequence (3) is a simple Markov sequence; if it is discrete, then (3) is a Markov chain [10]. The latter is true, in particular, in the relay procedure (2). Attracting a well-developed mathematical apparatus of Markov sequences [10, 11] and chains [10, 12] for analyzing the effectiveness of PD with a finite number of iterations allows to obtain a number of useful results.
Let us consider the possibility of using the apparatus of the Markov chain theory for modeling the process of stochastic gradient estimation of IID parameters.
Λt 2. The relationship of the matrix of transition probabilities with the probabilities of drift estimates If in (1) the gain matrix is diagonal, then the matrix of conditional probabilities Πi (l, t ) = P{αˆit = aik |αˆil = aij } can be expressed in terms of estimates drift probabilities (EDP) of the IID parameters [13, 14]. The EDP of the parameter is the probability of the estimate improvement after the SGP iteration (taking into account possible changes in the estimates of other parameters). Then, with a variable step λt of the increment in (2), the elements π jk (l, t ) of matrix Π(l, t ) : ρα+ (ε j ), if l = t − 1, k = j + ∆t signε j , π jk (l, t ) = ραo (ε j ), if l = t, k = j;, ρα− (ε j ), if l = t − 1, k = j − ∆t signε j , 0, other case, where π jk (l,t ) is the probability that the estimate αˆi will be equal to value aik , if at an earlier iteration l < t the estimate had a value aij ; ρα+ (ε j ) is the probability of changing the parameter to α iт ; ρα− (ε j ) is probability of estimate change from α iт ; ρα0 (ε j ) - probability of no change of the estimate; ε ij = (α iт − aij ) ; α iт is the exact value of the parameter α i ; ∆t is the number of possible states of parameter α in the interval from a j to ak , including the state ak . In the future, to simplify the recording, the index «i» will be omitted when considering one parameter.
At a constant step λt the elements π jk (l, t ) are also directly expressed through the EDP: ρα+i (ε j ), if l = t − 1, k = j + signε j ; π jk (l, t) = ραoi (ε j ), if l = t, k = j; ρα−i (ε j ), if l = t − 1, k = t − signε j ; 0, other case.
Under these conditions, we obtain a homogeneous Markov chain (3), for which Π(t ) = Πt , (5) where Π is the matrix of one-step transition probabilities. At t → ∞ such a chain becomes stationary.
However, with an increasing the number of estimated parameters, the application of the classical mathematical apparatus of Markov chains becomes problematic due to the sharp increase in the size of the transition probability matrix.
One of the main parameters determining computing costs, when using the Makovsky chain apparatus, is the number of possible values of IID parameter estimates. A priori, choose the size of the matrix Π allows the discretization of the estimated parameters domain. However, the use of the classical apparatus of the Markov chain theory remains reasonable only when estimating one parameter, since an increase in the number m of estimated parameters by one leads to an increase in computational costs at least by K 2 , where K is the number of possible discrete values of estimates of the (m + 1) -th parameter. In problems of measuring the IID parameters, the value K reaches several orders of magnitude. In this case, the determination of PD of parameter estimates, based on the use of a matrix of one-step transitions, becomes an obstacle for probabilistic modeling of the stochastic gradient process of measuring the parameters of inter-frame deformations. 3. Adaptation of the Markov chains apparatus to the solved problem To reduce computational costs, we use the fact that at the t -th iteration, regardless of the state of the estimates of other parameters, transitions from the j -th state of parameter α i estimate are possible only to the known k -th state, where k ∈{j +ν it + 1, j +ν it , j, j −ν it , j −ν it − 1,}, ν it = int (λit / ∆αi ) . In this case, the transition probabilities are determined by the state of other parameter estimates. The integral probability of the transition of estimate αˆi from the j -th state (αˆ = aij ) to the k -th state (αˆ = aik ) is determined by the sum of the transition probabilities from the subdomains ωik of the parameter space, i = 1, m , k = 1, Ki . For example, to use relay-type procedures when evaluating three parameters α1 , α 2 and α 3 the overall probability ρ~ij of deterioration of the estimate αˆ1 = a1 j at the t -th iteration can be written as [15]:
K1 K3 ρ~1−j = ∑ p2k (t −1)∑ p3l (t −1)ρ − (ε 1 j ,ε 2k ,ε 3l ),
k=1 l=1 where plk (t − 1) = P(αˆl = alk |αˆ1 = aij ) is the probability that at the (t − 1) -th iteration for αˆl = alk , k = 1, Kl the value αˆ1 is equal to a1 j ; ε lk = alk −α lт is deviation of the estimate αˆl from the exact value α lт , l = 1, 2, 3 . For m parameters we have:
K2 K3 Km ρ~1−j = ∑ p2k (t − 1)∑ p3l (t − 1)...∑ (pmn (t − 1)ρ − (ε 1 j ,ε 2k ,...,ε mn ))... .
k =1 l=1 n=1 Similarly, the expressions for probabilities ρ~1oj and ρ~1+j can be written.
With this approach, the matrices of one-step transitions are also change, which for this case we denote Πi (t) = π (jkt) (i,ρ~i* ) , where i is the number of parameter; π (jkt) (i,ρ~i*j ) is probability of transition ~
j of i -th estimate from the state a j at the (t − 1) -th iteration to the state ak to the t -th iteration:
K2 Km ρ~i*j = ν∑=1 p1ν (t − 1)...∑ (pml (t − 1)ρ i* (ε 1ν ,...,ε ij ,...,ε ml )) ,
l=1 where ρ i* (⋅) are values of probabilities ρ i+ (⋅) , ρ io (⋅) and ρ i− (⋅) at a vector of estimates mismatch ε i = (ε 1ν ,...,ε ij ,...,ε ml )T , ε ik = aik −α iт . At the same time, the size of the matrix with m parameters compared with the traditional approach is reduced from ∑im=1 Ki × ∑im=1 Ki to Ki × Ki . Computational costs are about as much reduced. This reduction occurs due to the loss of information about the probability of belonging to the estimation of the parameter vector of each of the subdomains of the parameter space. Only information about the projections of the distribution in this space is saved. In this case, this information is sufficient for calculating the PD of IID estimates for a finite number of iterations. To calculate the PD of the estimate of the i -th parameter at the t -th iteration of the SGP, you need to know the PD of the estimates of all parameters on the (t − 1) -th iteration: piT (t) = piT (0) ∏t Π~ i (s) . (8)
s=1 ~ Thus, determining the matrix Πi (t) allows only a recurrent method of calculation. Note also that, ~ when Πi (t) is used even at λi = const the Markov chain of estimates formed by the SGP, it can no longer be considered homogeneous. Accordingly, the expression (5) for this case is not true. To calculate the discrete probability distribution pTi (t ) of estimates of the i -th parameter using the matrix ~ Πi (t) , we obtain the recurrent procedure:
~ pTi (t ) = pTi (t − 1)Πi (t), i = 1, m .
~ For a variable step λit with adopted simplifications, the matrix Πi (t) for the parameter α i can be (9) (10) (11) determined as: ~ Πi (t) = ρ~i−1ρ~+−ρ~io1
i ρ~−2 .
For constant λi the expression, determining the matrix element is significantly simplified: ρ~i−j + ρ~ioj , if ρ~i−j , if π (jki) (t, ρ~i*j ) = ρρ~~iio+jj ,, iiff ρ~ioj + ρ~i+j , if 0, j = k = 1, j = k −1,1 < j < Ki , j = k, 1 < j < Ki , j = k + 1,1 < j < Ki , j = k = Ki , another case.
~
Relations (7)-(11) determine the recurrent algorithms for calculating the matrix Πi (t) and the PD of the parameter estimation errors for the required iteration of estimation, starting from the initial ~ approximation. The size of Πi (t) does not depend on the dimension of the vector α and is determined only by the discretization parameters of the domain of definition of a specific parameter α i . Computational costs with an increase in the dimension of the vector of parameters grow in m proportion to ∑ K , which allows to find a compromise between the accuracy of the calculation of PD i=1 i and the requirements for computational resources. Further reduction of computational costs is possible due to the imposition of restrictions on the range of allowable values of the estimated parameters and the introduction of rules for taking into account probabilities beyond the boundaries of this area. 4. Conclusion It is shown that the sequence of estimates of the parameters of IID, obtained using GSP, is a sequence without aftereffect and is a vector Markov process. With one estimated parameter for probabilistic modeling of the stochastic gradient estimation process, it is advisable to use the mathematical apparatus of the Markov chain theory. The study of expressions that allow calculating the transition probabilities of the matrix of one-step transitions through the probabilities of parameter estimation drift showed that for relay algorithms with one estimated parameter, the single-step transition matrix has a five-diagonal structure and does not depend on the iteration number, determining the Markov chain uniformity. However, for the vector of parameters, the use of the classical apparatus of the Markov chain theory becomes problematic due to a sharp increase in the size of the transition probability matrix. A priori, the matrix size can be chosen to discretize the domain of the parameters to be estimated, but even with this approach, the use of the classical apparatus makes sense only when evaluating one parameter.
In order to reduce computational costs, one-step transition matrices are proposed, the dimension of which is determined only by discretization of the domain of the corresponding parameters and does not depend on their number. The resulting matrix allows only a recurrent method of its calculation from the initial approximation of the parameters to the required iteration. Moreover, the Markov chain of estimates loses the property of homogeneity. Also, accurate information about the probability distribution in the parameter space is lost. Only the projections of this spatial distribution are saved. However, this is enough to solve the problem of finding the PD of parameter estimates for inter-frame deformations with a finite number of iterations.