# Inferring Agents' Goals from Observing Successful Traces
## 4 Experiments
For example, if our hypothesis is \(H=(a\wedge c\wedge d)\vee(b\wedge d)\) and the real set of goals is \(G=(a\wedge d)\vee(b\wedge c\wedge d)\), we have:  
\[d(H,G)=d((a\wedge c\wedge d),G)+d((b\wedge d),G) \tag{1}\]  
\[d(H,G)=min(Card(\{c\}),Card(\{a,b\}))+min(Card(\{a,b\}),Card(\{c\})) \tag{2}\]  
\[d(H,G)=min(1,2)+min(2,1)=1+1=2 \tag{3}\]  
The second measure is the accuracy of the three algorithms, it is the fraction of successfully classified examples and it is calculated as follows:  
\[accuracy=(Tp+Tn)/(Tp+Tn+Fn+Fp) \tag{4}\]  
And the last one is the recall (also called sensitivity), which is the fraction of positive examples that are successfully classified as such by the algorithms, we calculated as follows:  
\[recall=Tp/(Tp+Fn) \tag{5}\]  
Where \(Tp\), \(Tn\), \(Fp\), and \(Fn\) are respectively, True Positive, True Negative, False Positive, and False Negative. \(Card(X)\) is the function cardinal which is equal to the number of elements in \(X\). Results:  
As shown by the experiment, the average syntactic distance between the agent's actual goals and the results provided by LFST is pretty good because this average is a little less than 9 in the worst-case for GridWorld, as we can see in Figure 5. Knowing that for GridWorld, the agent has four goals composed of three atoms each, which means that on average, in the worst-case, LFST still finds almost one third of the atoms composing each real goal. Moreover, even when using as few as 20% of the initial data set, the results are still correct. Indeed, the average syntactic distance being around 5. It means that almost two thirds of the atoms composing each real goal of the agent are still deducted even in this case. MGI is more constant and thus stays to an average distance of 4 from the actual set of goals, being less precise than LFST until 60% of missing data where LFST gets worse. This difference can be explained by the fact that MGI will generate more specific prototypes than LFST. Thus, even if the actual goal is a conjunction of three atoms, MGI will generate a prototype of four or five atoms that cover the goal, and since they do not cover any negative examples, it will stop there. LFST will generate more general prototypes that the negative examples will invalidate, so the prototypes will start to be more and more specific and eventually as specific as the actual goals. Nevertheless, when there is not enough data,the prototypes which are too general will not be invalidated anymore due to the lack of negative examples, so the average syntactic distance from the actual goals will increase. However, as we can see in Figure 6, the accuracy of LFST is always better than the one of MGI and remains on average around 99.7%. As expected, the accuracy of both algorithms is decreasing with the quantity of data used. The difference between the two algorithms is that LFST will rarely fail to classify a positive example. Thus, it will produce very few False Negatives when MGI fails more often to classify a positive example. C4.5 has excellent accuracy in this environment, being even slightly better than LFST and reaching 100% of accuracy, though it is only a small gain compare to LFST. However, the most significant difference in efficiency for the algorithms is the recall; Figure 7 shows that the value for the recall of LFST and C4.5 is much better than the one of MGI, which is just around the average (50%). The reason for this result is the same as before since the recall is highly dependent on the number of False Negatives. As for CubeWorld, in this environment, the agent has three goals of six atoms, so the syntactic distance cannot exceed 18, and we can see in Figure 8 that LFST obtains a bit less  
Figure 2:0 Comparison of the average distance from the actual goals in GridWorld. Figure 2:1 Comparison of the average accuracy in GridWorld. than 10 in the worst-case, so we infer more than one third of the goals in this case. The value of the distance for MGI is, on average, around 9, which is almost the worst value for LFST, so here also LFST is more accurate.