# Parsing Expression Grammars and Their Induction Algorithm
## 4 Results and Discussion
It also brings together several crucial conceptual components; the structures it learns are (i) variable-order, (ii) hierarchically composed, (iii) context dependent, (iv) supported by a previously undocumented statistical significance criterion, and (v) dictated solely by the corpus at hand. Blue-fringe [21] and Traxbar [22], the instances of state merging algorithms, can be downloaded from an internet archive ([[http://abbadingo.cs.nuim.ie/dfa-algorithms.tar.gz](http://abbadingo.cs.nuim.ie/dfa-algorithms.tar.gz)]([http://abbadingo.cs.nuim.ie/dfa-algorithms.tar.gz](http://abbadingo.cs.nuim.ie/dfa-algorithms.tar.gz))). They start from building a prefix tree acceptor (PTA) based on examples, and then iteratively select two states and do merging unless compatibility is broken. The difference between them comes from many ways in which the pair of states needed to merge can be chosen. [PERSON] and [PERSON] [23] described an algorithm for constructing the smallest deterministic FSA consistent with a complete labeled training set. The PTA is squeezed into a smaller graph by merging all pairs of states that represent compatible mappings from word suffixes to labels. This algorithm for completely labeled trees was generalized by [PERSON] (1992) [22] to produce a (not necessarily minimum) automaton consistent with a sparsely labeled tree. Blue-fringe grows a connected set of red nodes that are known to be unique states, surrounded by a fringe of blue nodes that will either be merged with red nodes or promoted to red status. Merges only occur between red nodes and blue nodes. Blue nodes are known to be the roots of trees, which greatly simplifies the code for correct merging. We also included one machine learning approach. An unsupervised data-driven distributed representation, called ProtVec [24], was applied and protein family classification was performed using a support vector machine classifier (SVM) [25] with the linear kernel. Figure 4: Combined amyloid databases used in this work. Pos and Neg denote, respectively, positive and negative word counts in the database. The data were randomly split into two subsets, a training (75% of total) and a test set (25% of total). Given the training set and the test set, we used all algorithms to infer predictors (automata or grammars) on the training set, tested them on the test set, and computed their performances. Comparative analyses of the following five measures: Precision, Recall, F-score, the AUC, and Matthews correlation coefficient are summarized in Table 5. The measures are given below:  
* Precision, P = _tp_/(_tp_+_fp_);
* Recall, R = _tp_/(_tp_+_fn_);
* F-score, \(\text{F1}=2\times\text{P}\times\text{R}/(\text{P}+\text{R})\);
* Accuracy, \(\text{ACC}=(\textit{tp}+\textit{tn})/(\textit{tp}+\textit{tn}+\textit{fp}+ \textit{fn})\);
* Area under the ROC curve, \(\text{AUC}=(\textit{tp}/(\textit{tp}+\textit{fn})+\textit{tn}/(\textit{fp}+ \textit{tn}))/2\);
* Matthews correlation coefficient, \(\text{MCC}=\frac{\textit{tp}\times\textit{tn}-\textit{fp}\times\textit{fn}}{ \sqrt{(\textit{tp}+\textit{fp})(\textit{tp}+\textit{fn})(\textit{tn}+\textit{ fp})(\textit{tn}+\textit{fp})}}\);  
where the terms true positives (_tp_), true negatives (_tn_), false positives (_fp_), and false negatives (_fn_) compare the results of the classifier under test with trusted external judgments. Thus, in our case, _tp_ is the number of correctly recognized amyloids, _fp_ is the number of nonamyloids recognized as amyloids, _fn_ is the number of amyloids recognized as nonamyloids, and _tn_ is the number of correctly recognized nonamyloids. The last column concerns CPU time of computations (induction plus classification in s). Figure 5: Combined amyloid databases used in work. Pos and Neg denote, respectively, positive and negative word counts in the database. The results show that there is no single method that outperformed the remaining methods regardless of an established classification measure. However, the methods can be grouped as relatively good and relatively weak from a certain angle.