## 2 Definition of Activity Recognition problem
### Classifiers for activity recognition  
To solve general classification problems, different algorithms have been proposed, supervised and non supervised [15]. Supervised methods build class models using labelled data, whereas non supervised methods try to discover the structure of the data. Examples of supervised methods are kNN, Neural Networks and Classification Trees. Examples of non supervised methods are clustering techniques. In Human Activity Recognition, the most accepted classification techniques are Hidden Markov Models (HMMs), because activities have temporal structure and HMMs can tackle with this kind of processes. However, others methods have been succesfully used [4]: Neural Networks, Neuro-Fuzzy systems, C4.5.  
_etc._  
Be a system that can be described using a set of N different states, where random transitions are produced over time, according to a given probability distribution for each state. The state on the system on each moment depends on the state that it was in the previous moments. This kind of stochastic process is called \"Markov Model\". Additionally, if the present state of the system can not be observed, i.e., it could be only measured by an effect that it produces, the system is called \"Hidden Markov Model\".  
A Hidden Markov Model \(\lambda\)[16] is defined by the tuple \(\lambda\equiv(S,M,A,B,\Pi)\) where:  
* \(S=\{S_{0},\ldots,S_{N}\}\) is the set of hidden states of the model. The state at time \(t\) is denoted by \(q_{t}\).
* \(M\) is the set of observation symbols of the model.
* \(A=\{a_{ij}\}\) is the state transition probability distribution: \[a_{ij}=p\left(q_{t+1}=S_{j}\mid q_{t}=S_{i}\right)\] (3)
* \(B=\{b_{j}\}\) is the observation symbol probability distribution in state \(j\): \[b_{j}=p\left(v\mid q_{t}=j\right)\] (4)
* \(\Pi=\{\pi_{j}\}\) is the initial state probability distribution: \[pi_{j}=p\left(q_{0}=j\right)\] (5)  
One of the most powerful features of HMMs is that it can model both large duration and small duration activities. To model large duration activities, an HMM is defined for each activity. Given a sequence \(O=o\_1\ldots o\_k\) of observations to classify as a large duration activity, and a set of HMM activity models \(\Lambda=\{\lambda_{1}\ldots\lambda_{n}\}\), the sequence is associated to the HMM with the highest probability of generating \(O\):  
\[\arg\max_{i}P\left(m_{i}\mid O\right) \tag{6}\]  
\(P\left(O\mid m_{i}\right)\) can be estimated using Forward-Backward algorithm [16].  
When the recognition target are small duration activities, only one HMM is used, with one state per activity to classify. Given a sequence \(O=o\_1\ldots o_{k}\) of observations to classify as small duration activities, the problem to solve is the association of each observation with the state most likely of generating it:  
\[q_{t}=\arg\max_{i}P\left(S_{i}\mid o_{t},q_{t-1}\right) \tag{7}\]  
The solution to estimate the current state of the HMM can be found using Viterbi algorithm [PERSON] (1996). Viterbi algorithm computes the most likely state sequence that has generated the observed output. The algorithm proceeds as fallows:  
1. Initialization: \[\delta_{1}\left(i\right) =\pi_{i}b_{i}\left(o_{1}\right) 1\leq i\leq N\] (8) \[\psi_{1}\left(i\right) =0\] (9)
2. Recursion: \[\delta_{t}\left(j\right) =\max_{1\leq i\leq N}\left[\delta_{t-1}\left(i\right)a_{ij} \right] b_{j}\left(o_{t}\right) 2\leq t\leq K\] (10) \[1\leq j\leq N\]
3. Finalization: \[p^{*} =\max 1\leq i\leq N[\delta_{K}\left(i\right)]\] (12) \[q_{K}^{*} =\arg\max 1\leq i\leq N[\delta_{K}\left(i\right)]\] (13)
4. Path Backtracking: \[q_{t}^{*}=\psi_{t+1}\left(q_{t+1}^{*}\right)\ \ \ t=K-1,K-2,\ldots,1\] (14)  
The algorithm give us the optimal state sequence stored in vector \(q^{*}\). \(p^{*}\) is the probability of \(q^{*}\) generating O.