Information Technology Reference
In-Depth Information
350
800
700
300
600
250
500
200
400
150
300
100
200
50
gap length 1
gap length 2
gap length 3
gap length 1
gap length 2
gap length 3
100
0
0
0
10
20
30
40
50
0
10
20
30
40
50
Frequency of gaps
Frequency of gaps
Fig. 5.
The number of particles for which RVPF is exactly as fast as RVSE, measured for different
GFs and GLs. The figure on the left shows the results for the original 5-state HMM. The figure
on the right shows the results for the learned 10-state HMM.
50%. These results also provide a useful guide for choosing the number of particles that
maximizes RVPF's accuracy while maintaining its performance advantage over RVSE.
Figure 5 justifies our choice of 150 and 350 particles in Table 1. Namely, with 150
particles RVPF outperforms RVSE for all GLs from 10% to 50% in case of the original
5-state HMM. The same is true for 350 particles when the learned 10-state HMM is
used instead.
6.2 Accuracy of State Estimation
Since we recorded the HMM and DFA states in our traces, we can use these values to
determine the accuracy of each algorithm's state estimation. We consider first the DFA
state. Figure 6 contains our results for estimating the probability for DFA state
s
2
.The
gray line in the graphs serves as a reference value, showing exactly when the DFA was
in state
s
2
. These results are for the worst-case scenario in which there is a gap after
each observation symbol (GF = 50%).
The number of particles used for RVPF in obtaining these results was determined
as follows. To guarantee that RVPF would always be about twice as fast as RVSE, a
significant speed-up, we used the results of Figure 5 to choose the number of particles
forRVPFtobehalfofthevalueforwhich it matched RVSE's execution time.
Although we performed state estimation for each DFA state, for presentation pur-
poses, we show only the results for the estimation of DFA state
s
2
. Even though we
are usually interested in state
s
4
of the DFA, which is the error state, this state has a
very low probability of being reached. The estimated probability of
s
4
is therefore al-
most always zero and rises very slowly. Also, state
s
4
is a trap-state, meaning that once
entered, the DFA will remain in the state forever. These considerations make
s
4
less
suitable for measuring accuracy of state estimation. In contrast,
s
2
is entered and exited
frequently and is thus much more suitable for measuring accuracy of state estimation.
The effect of a 50% GF can be seen in Figure 6 as a form of jitter in the graphs for all
three algorithms. Each available observation symbol helps the algorithms increase their
certainty, whereas each gap introduces uncertainty. The repeated alternation between
visible symbols and gap symbols thus causes the estimated probability to oscillate.
