In order to successfully ablate moving tumours in robotic radiosurgery, respiratory motion prediction is needed to compensate time delays. In this context, recent studies revealed a high potential of support vector regression (SVR). However, high computational cost is one major drawback, particularly caused by batch mode training. We evaluate two approaches to reduce the update rate as well as computation time, while keeping a low prediction error. The update rules are either based on information about the respiratory phase or based on the current prediction error. An evaluation on patient data sets revealed that the second approach on average decreases computation time by 88.53% compared to a batch mode implementation. The prediction error increased by 0.3%, hence indicating enhanced efficiency.
For simplicity, all further explanations are reduced to a one dimensional signal. The algorithms can easily be expanded to three dimensions. It is assumed that the respiratory signal is equidistantly sampled with a sampling rate fs and that the resulting sequence has length N. Let yt be the signal amplitude at time point t and yt+δ the amplitude of the predicted point. Here, δ represents the prediction horizon. The predicted value is denoted by ̂ and depends on .
Given a training set
{(
)
(
)} with
{
}
(1)
where again ui represents the training data and yi+δ the training labels, the SVR fits a functional relationship
y = f(u) to this data. Here, L is the amount of training samples and M the number of past observations used to predict a
new label. The ɛ-SVR does not penalize a fitting error up to ɛ per sample and optimizes f(u) to be as smooth as possible.
In the linear case with slope vector w and offset b, f(u) can then be used to predict a point ̂ ( ) 〈 〉
, where 〈 〉 denotes the dot product. As smoothness is equivalent to minimizing the l2-norm of w, a convex
optimization problem, that is regularized by violations of the mentioned ɛ constraint, can be formulated and solved to
finally derive f(u). A full account of the underlying principles and mathematics is given in [
The SV machine can be extended to nonlinear cases by using kernel functions used to implicitly transform the linear
case above to higher dimensions. The SVR was implemented with a Gaussian radial basis kernel (width parameter ɣ =
2) using LIBSVM Toolbox [
In contrast to general BM training, Ernst et al. [
The second update algorithm depends on the current prediction error. If at time t a value yt is measured, the algorithm computes ̂ based on the current SVR model and input ut-δ. If | ̂ | exceeds a threshold eth, the SVR model is updated. This aims at updating the model once it becomes too inaccurate. In order to estimate a general threshold independent of the signal, eth is set to a multiple f of the chosen tube size ɛ. 3
To investigate the PFUR and the EUR, we carried out three experiments on real patient data. First, we experimentally
verified the assumptions being the basis of PFUR. Second, by varying τslope, θ and f, the potential of these two update
algorithms is evaluated and compared to CFUR for the same signal. Third, EUR is further explored on 33 patient files.
According to the latencies of the CyberKnife system, the prediction horizon δ was set to 3 samples (≈115ms). All
signals have been globally scaled to a range of [
The performance was evaluated using computation time tcalc and number of SVR model updates nupdate. Whereas tcalc
depends on the specific hardware of the computer and software implementation of the algorithm, nupdate only depends on
the algorithm and is approximately governed by a linear relationship to tcalc. Prediction accuracy was measured in terms
of relative root mean square error RMSrel [
Training labels 800 SVs 1000 b) d) mean shape of respiration period
1 time [sec] SV distribution a) c)
1
In the first experiment, 20000 data points (≈770s) of a respiratory signal were processed by ɛ-SVR using a batch mode implementation (part of the signal is shown in fig. 1.a). At each time point, the number and location of the SVs were extracted from the SVR model. Fig. 1.c shows training labels and SVs for a certain time point t. The SVs are mainly distributed around the maxima in- and expiration. Over time the SVR model used an average amount of 446 from 1000 possible training samples as SVs. Per model update 3.3 elements from the SV set changed on anverage. Finally, a mean respiratory period was calculated from the signal (fig. 1.b) and divided into 20 bins. Depending on their location within the whole signal, each SV was assigned to one of the bins. Fig. 1.d shows a histogram of the accumulated number of SVs per bin normalized by the maximum number of training samples among all bins.
We further analyzed the signal used in experiment one with PFUR and EUR. For PFUR, τslope was varied between 0 and 1 in steps of 0.1 and θ was incremented in steps of 5% between 5-20%. The impact of the multiplication factor f for EUR was tested by grid search using f = {0.05, 0.1, 0.25, 0.5, 0.667, 0.8, 1, 1.25, 1.5, 2, 4, 10, 20}. The results were compared with CFUR using a global update factor τglobal varied between 0 and 1 in steps of 0.1 and assessed using RMSrel, tcalc and nupdate (Fig.2.a-f).
Based on the promising results of EUR, 33 patient files were evaluated only with this method. These signals were ran domly selected from a pool of 304 signals (31 patients) using 20000 data points for each analysis. As in section 3.2, the multiplication factor f was varied to find the optimal fopt. To compare the results for different patients i, the average RMSrel, tcalc and nupdate were calculated relative to CFUR τglobal =1: ̅̅̅̅̅̅̅̅̅ ( ); ̅̅̅̅̅̅ ( ) ; ̅̅̅̅̅̅̅̅̅̅ ( ) (3) a) 1.6 1.4 1.2 1 10-1 0.5 are illustrated. On average, EUR (f = 2) reduces tcalc by 88.53 %, and increases RMSrel by 0.3%, compared to batch mode training. The mean computation time to predict approximately 770s of respiratory signal was 534.4s. 4
In this work, we presented two updating methods to decrease computation time of an ɛ-SVR for respiratory motion prediction – one based on the current respiratory phase (PFUR) and one on the prediction error (EUR). In an initial analysis, we showed that the location of the SVs strongly depends on the phase in the respiratory period. We found that training samples at the maximum in- or expiration are likely to comprise more SVs than other periods. This result supports the initial assumption of PFUR, i.e. that the update rate can be reduced during in- and exhalation. The concept of this approach was studied for various τslope and θ on one data set. For τslope = 0.3 and θ = 15%, tcalc was reduced by 317. 4s compared to BM (nupdate,PFUR = 15159 instead of 20000 model updates), while the relative RMS error only increased by 0.34%. However, one drawback of this method is that the respiration phases, especially maximum in- and expiration, have to be known in advance or have to be identified online. This restricts the use of the PFUR for practical applications and makes it dependent on the accuracy with which the location of such extrema can be estimated. In contrast, EUR is independent of prior information and reduced tcalc by 1278.7s compared to an equivalent BM implementation, while yielding the same RMSrel increase as for the PFUR (nupdate,EUR = 111 for f = 4). The result was confirmed in an evaluation of 33 patients. The average computation time was reduced by 88.53 % from tcalc,BM = 4292.2s (BM) to tcalc,EUR = 534.4s, while the average RMSrel was increased by 0.3% only. With this method, respiratory motion prediction with SVR is performed more efficiently compared to the BM implementation. Even though it is still not possible to perform online motion prediction with SVR on an ordinary office computer, because the computation time for updating the model is larger than the sample time. But knowing when to update the model can be useful for implementing efficient multi-thread, online SVR predictors in the future. An example could be a dual-thread predictor, where one thread performs online predictions, while the second thread updates the SVR model. To reduce the calculation time even further, the algorithms could be implemented in C/C++ for instance or on dedicated hardware. Finally, it should be pointed out that EUR is not restricted to respiratory motion signals and can be applied to other applications. 5