# Mining Hidden and Fragmented API Usages in Android Applications
## 5 Code Completion with the Generalized API Sequence
### Statistical Model Generator  
The statistical model was generalized using the HAPI [17]. HAPI is known to outperform than SLANG [20], which uses \(n\)-gram and recurrent neural networks. The HAPI was designed to learn the API usages for each set of classes instead of generating one model for every usage. For example, one model was generated for one class java.util.LinkedList, whereas another model was generated for the class java.util.String. The remainder of this section will explain the HAPI model briefly.  
HAPI was employed to approximate the probabilities of state transitions and method invocations. Figure 6 presents the simplified state diagram and a HAPI model of the class MediaPlayer that belongs to the Android standard library. The state diagram presents the methods expected to be invoked from each state. However, such state diagrams are rarely provided with exiting libraries and frameworks including Android. The HAPI aims to generate probabilistic diagrams based on the collected API usages.  
Each HAPI learns the invocation probability of each method in a given set of classes. A HAPI model has \(k\) hidden states, \(\mathbf{H}=\{h_{1},\ldots,h_{k}\}\); \(n\)invocable methods, \(\mathbf{M}=\{m_{1},\ldots,m_{n}\}\); a transition matrix \(\mathbf{A}=\{a_{ij}\}\)\(\in\)\(\mathbf{k}\wedge\mathbf{j}\)\(\in\)\(\mathbf{k}\), where \(a_{ij}\) is the transition probability from \(h_{i}\) to \(h_{ij}\); output probability \(\mathbf{B}=\{b_{ij}|i\}\)\(\in\)\(k\)\(\wedge\)\(j\)\(\in\)\(n\), where \(b_{ij}\) is the probability of emitting \(m_{j}\) in \(h_{i}\); and \(\mathbf{\Pi}=\{\pi_{1},\pi_{2},\ldots,\pi_{k}\}\), where \(\pi_{i}\) is the probability of an API sequence that started from the hidden state \(h_{i}\). In other words, the HAPI needs to determine the parameters \(\lambda=(\mathbf{A},\mathbf{B},\mathbf{\Pi})\). This can be solved using the Baum-Welch algorithm [37],  
Figure 5: Example of extracting API sequences  
Figure 6: Example of extracting API sequences.  
which performs both forward procedures and backward procedures and updates parameters until the parameters converge. Given an API sequence \(\mathcal{S}=(s_{1},\ldots,s_{l})\), forward probability \(a_{i,t}\) is the probability of sequence \(s_{1},\ldots,s_{t}\) when the current state \(c_{t}\) is \(h_{i}\). Moreover, backward probability \(b_{i,t}\) is the probability of sequence \(s_{t+1},\ldots\)\(s_{l}\) when \(c_{t}\) is \(h_{i}\).  
\[a_{i,t}=\ P(s_{1},\ldots,s_{t},c_{t}=\ h_{i}|\lambda)b_{i,t}=\ P(s_{t+1}, \ldots,s_{l}|c_{t}=\ s_{i},\lambda)\]  
With forward and backward probabilities, we can calculate the transition matrix and emission matrix as follows.  
\[\gamma_{i}(t) =P(c_{t}=h_{i}|\mathbf{M},\ \lambda)=\frac{a_{t,i}b_{i,t}}{P(\mathbf{M}| \lambda)}e_{\mathrm{ij}}(t) =P\Big{(}c_{t}=h_{i},c_{t+1}=h_{j}|\mathbf{M},\ \lambda\Big{)}\]  
Both forward probability and backward probabilities are recalculated until the parameters \(\gamma\) and \(\epsilon\) converge. Note that among the parameters, the number of hidden states should be determined empirically.