# A Time-Series Model for Varying Worker Ability in Heterogeneous Distributed Computing Systems
## 3 Estimation of Latent Variable and Parameters
### Filtering and Smoothing  
We resort to the sampling method to approximate the function \(Q(\mathbf{\theta}|\mathbf{\theta}^{(v)})\) since the integral (10) is analytically intractable. Our goal is to find an approximation of  
\[p(x_{1:G,0:T}|\eta_{1:G,0:T},l_{1:G,0:T},\mathbf{\theta}^{(v)}).\]  
Since the distribution is independent across groups, we only need to infer  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]  
for each group \(i\), which is the so-called a smoothed estimate. To obtain the smoothed estimate, we use the particle method [22] since it is efficient in high-dimensional sampling and more suitable for filtering [23; 24; 25] compared to the other competing schemes. Specifically, we choose sequential Monte Carlo (SMC) for the filtering algorithm [26]. The algorithm is based on sequential importance sampling with resampling, which has advantages in controlling the variance of estimates [27]. Note that the SMC algorithm is based on importance sampling, and the sampled object is called the _particle_ (hence, its name). For workers in group \(i\) and the task assigned at \(t\), the number of particle sequences is denoted by \(L\) and the \(l\) (\(\in[L]\))-th particle is denoted by \(x_{i,l}^{(l)}\). We need to obtain the proposal (importance) distributions \(q_{0}(x_{i,0}|\eta_{i,0})\) and \(q(x_{i,l}|\eta_{i,t},x_{i,l-1})\). The optimal choices of the proposal distribution and proposal function are just the distributions of themselves, i.e.,  
\[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]  
and  
\[q(x_{i,l}|\eta_{i,t},x_{i,t-1})=p(x_{i,l}|\eta_{i,t},x_{i,t-1}).\]  
However, evaluating these distributions is intractable in our model. Although there are several possible methods to obtain a proposal distribution, we choose the following, which are known to work well in practice:  
\[q_{0}(x_{i,0}|\eta_{i,0})=\frac{f_{0}(x_{i,0}|\mathbf{\theta}^{(v)})g(\eta_{i,0}| x_{i,0},l_{i,0})}{g(\eta_{i,0}|x_{init},l_{i,0})} \tag{11}\]  
and  
\[q(x_{i,l}|\eta_{i,t},x_{i,t-1})=\frac{f(x_{i,l}|x_{i,t-1})g(\eta_{i,l}|x_{i,t}, l_{i,t})}{g(\eta_{i,l}|x_{i,t-1},l_{i,t})} \tag{12}\]  
for \(t\in[T]\). Here, \(x_{init}\) is an initial guess of \(x_{0}\). These choices ease the computation of importance weights, which are given as follows for the \(l\)-th particle sequence:  
\[w_{i,0}(x_{i,0}^{(l)})=\frac{f_{0}(x_{i,0}|\mathbf{\theta}^{(v)})g(\eta_{i,0}|x_{i,0}^{(l)})}{q(x_{i,0}^{(l)}|\eta_{i,0})}=g(\eta_{i,0}|x_{init},l_{i,0})\]\[w_{i,t}(x^{(l)}_{i,t-1:t})=\frac{g(\eta_{i,t}|x^{(l)}_{i,t},l_{i,t})f(x^{(l)}_{i,t} |x^{(l)}_{i,t-1})}{q(x^{(l)}_{i,t}|\eta_{i,t},x^{(l)}_{i,t-1})}=g(\eta_{i,t}|x^{( l)}_{i,t-1},l_{i,t}).\]  
Note that we can skip the resampling step for \(t=0\) since the importance weights \(w_{i,0}(x^{(l)}_{i,0})\) for \(t=0\) are independent of the particles \(l\in[L]\), which means all particles have the same weights. Therefore, \(x_{init}\) has no effects on the algorithm practically. The algorithm for SMC filtering on workers in group \(i\) is summarized in Algorithm 2. One additional shorthand notation  
\[x^{(l)}_{i,(0S)|s}=(x^{(l)}_{i,0|s},x^{(l)}_{i,1|s},\ldots,x^{(l)}_{i,s|s})\]  
is used in describing Algorithm 2. ```
Input: \(\eta_{i,0,S}\), \(l_{1,0S}\), \(\mathbf{\theta}^{(v)}\). - At time \(t=0\). * Sample \(x^{(l)}_{i,0}\) from \(q_{0}(x_{i,0}|\eta_{i,0})\), \(l=1,2,\ldots,L\). - At time \(t=1,\ldots,s\), * Sample \(x^{(l)}_{i,t}\) from \(q(x_{i,t}|\eta_{i,t},x^{(l)}_{i,t-1})\), \(l=1,2,\ldots,L\). * Set \(x^{(l)}_{i,0,t}\leftarrow\left(\tilde{x}^{(l)}_{i,0,t-1},x^{(l)}_{i,t}\right)\). * Compute unnormalized importance weights \[w_{i,t}(x^{(l)}_{i,t-1:t})=g(\eta_{i,t}|x^{(l)}_{i,t-1}).\]
* Compute normalized weights \[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]0
* Resample from \(\{W^{(l)}_{i,t},x^{(l)}_{i,0,t}\}_{l=1,\ldots,L}\) to obtain \(L\) equally weighted resampled particles \(\{1/L,\tilde{x}^{(l)}_{i,0,t}\}_{l=1,\ldots,L}\). Output: \(\hat{p}(x_{i,0:s}|\eta_{i,0:s},l_{i,0:s},\mathbf{\theta}^{(v)})\).