# A Discrete Hidden Markov Model for SMS Spam Detection
## 3 The Discrete HMM for SMS Spam Detection
### Observation States and Observation Sequence  
The \(i^{th}\) SMS can be represented as the rest meaningful sequential words in the set of observation states \(W\): \(\textit{SMS}_{i}=\left\{w_{1}^{\textit{SMS}_{i}},\,w_{2}^{\textit{SMS}_{i}},\,w_ {3}^{\textit{SMS}_{i}},\,\cdots,\,w_{\textit{Length/SMS}_{i}}^{\textit{S}_{i}} \right\}\), (\(0<i\leq M\)). \(M\) is the total number of SMS. \(w_{i}^{\textit{SMS}_{i}}\) is one of the meaningful words in the \(i^{th}\) SMS.  
For example, take the following two SMS messages from the UCI repository dataset, which can be downloaded from [[http://www.dt.fee.unicamp.br/~](http://www.dt.fee.unicamp.br/~)]([http://www.dt.fee.unicamp.br/~](http://www.dt.fee.unicamp.br/~))|tiago/smsspamcollection. The same dataset has been used in [2, 4, 8, 9, 10, 11, 13, 21, 23, 25, 31, 46, 52, 53, 54, 55, 56, 57] for performance evaluations.  
_ham: What you thinked about me. First time you saw me in class._  
_spam: Are you unique enough? Find out from 30 th August. www.areyouunique.co.uk._  
Please note that the example dataset only contains 2 SMS messages and words _you_ and _me_ are duplicated in the two SMS messages.  
The two SMS messages can be segmented as word and punctuation sequences with the original order: [_What, you, thinked, about, me,, First, time, you, saw, me, in, class,._ ] and [_Are, you, unique, enough,?_, _Find, out, from, 30 th, August,._, www,._, _areyouunique,._, _co,._,._, _uk_]. After removing stop words and punctuation, the word sequences also keep its order and become refined ones: [_What, you, thought, me, First, time, you, saw, me, class_] and [_Are, you, unique, enough, Find, 30 th, August, www, areyouunique, co, uk_].  
Then, the observation states set \(W\) is generated, i.e., \(W=\{\textit{What, you, thought, me, First, time, saw, class, Are, unique, enough, Find, 30 th, August, www, areyouunique, co, uk}\). Each word in \(W\) appears in  
Figure 2: The discrete hidden Markov model for spam detection.  
ham and spam SMS sets with a certain frequency. These occurrence frequencies will be used to obtain the observation probability distribution.  
In addition, the refined two-word sequences combine together to form the observation sequence \(\underline{X}=\{o_{1},\ o_{2},\ o_{3},\ \cdots,\ o_{N}\}\). In this example, \(\underline{X}=\{\)_What, you, thinked, me, First, time, you, saw, me, class, Are, you, unique, enough, Find, 30 th, August, www, areyoununique, co, uk_\(\}\). It is obvious that the original word order is kept.  
Therefore, the observation sequence \(\underline{X}=\{o_{1},\ o_{2},\ o_{3},\ \cdots,\ o_{N}\}\) can be represented as  
\[\underline{X}=\left\{w_{1}^{\text{SMS}_{1}},\ w_{2}^{\text{SMS}_{1}},\ w_{3}^{ \text{SMS}_{1}},\ \cdots,\ w_{Length/\text{SMS}_{1}}^{\text{SMS}_{1}},\right.\]  
\[\left.\begin{array}{c}\ldots\\ \\ w_{1}^{\text{SMS}_{1}},\ w_{2}^{\text{SMS}_{1}},\ w_{3}^{\text{SMS}_{1}},\ \cdots,\ w_{Length/\text{SMS}_{1}}^{\text{SMS}_{1}},\end{array}\right. \tag{2}\]  
\[\left.\begin{array}{c}\ldots\\ \\ w_{1}^{\text{SMS}_{M}},\ w_{2}^{\text{SMS}_{M}},\ w_{3}^{\text{SMS}_{M}},\ \cdots,\ w_{Length/\text{SMS}_{M}}^{\text{S}_{1}} \end{array}\right\}\]  
Please note that different SMS may have different lengths. All sequential words in each SMS combine together to form the final observation sequence \(\underline{X}\).