In this discussion we will consider two different examples of markov models. First we will analyze the navigation of a website by estimating transition probabilities. Then we will use notions of filtering to come up with estimates of the movements of an object in one dimension.
Before we begin. Recall that markov models are models in which we assume the data has some notion of time. For instance when considering $X_1,X_2,...,X_n$ in this context we can think of $n$ different time intervals and $X_1$ being a measurement taken at time 1 $X_2$ as a measurment taken at time 2 and so on. The markov setting is more general than the i.i.d. setting since instead of requiring full independence we only require the following property: $$\mathbb{P}(X_i < x\, |\, X_1,X_2,...,X_{i-1}) = \mathbb{P}(X_i< x\,|\, X_{i-1}) $$ Where as if the data were i.i.d. we would have that: $$\mathbb{P}(X_i < x\, |\, X_1,X_2,...,X_{i-1}) = \mathbb{P}(X_i< x) $$ These kinds of models are especially useful when considering dynamical systems as well as considering time dependant effects like seasonality.
Suppose we are manageing a website which has 3 pages comprising it. These are a main header page, an about page, a contact page and a service. Consider the following sample paths we have of useres who visited our site:
import numpy as np
import pandas as pd
website_data = pd.read_csv('website_data.csv')
website_data[:20]
Note that for each user we have a sequence of 10 pages they visited while on our website prior to leaving. Here the states correspond as follows:
We are interested in estimating the browsing behavior of our user which is the same as calculating the probability a user will visit a page given their current viewed page on the site. A reasonable for this estimation is clearly a Markov model with the model states corresponding to each of the different pages. Let's analyze this data by first forming a state transition matrix where each cell couts the number of times we transition from one state to another:
web_arr = pd.DataFrame.as_matrix(website_data.iloc[:,1:])
(ro, co) = web_arr.shape
trans_matrix = np.zeros((4,4))
for ind_i in range(ro):
curr_use = web_arr[ind_i,:]
for ind_j in range(co-1):
cur_stat = curr_use[ind_j]
fute_stat = curr_use[ind_j+1]
trans_matrix[cur_stat,fute_stat] += 1
label_matrix = np.concatenate(([['Header'],['About'],['Contact'],['Service']],trans_matrix),1)
label_matrix = np.concatenate(([[' ','Header','About','Contact','Service']],label_matrix),0)
trans_df = pd.DataFrame(data=label_matrix[1:,1:],index=label_matrix[1:,0],columns=label_matrix[0,1:])
trans_df
Using these measurments how can we estimate the transition probabilities?
Recall the MLE estimate of the transition probabilities is given by: $$ \hat{p}_{ij} = \frac{N_{ij}}{\sum_k N_{ik}}$$
where $N_{ij}$ is the total count of times we transitioned from state $i$ to state $j$. Using this method we can construct the following probability transition matrix for our website:
sum_mat = np.dot(trans_matrix,np.ones((4,1)))
norm_mat = 1/sum_mat
#norm_mat
trans_prob_mat = norm_mat*trans_matrix
trans_prob_mat = np.around(trans_prob_mat,3)
label_matrix = np.concatenate(([['Header'],['About'],['Contact'],['Service']],trans_prob_mat),1)
label_matrix = np.concatenate(([[' ','Header','About','Contact','Service']],label_matrix),0)
trans_df = pd.DataFrame(data=label_matrix[1:,1:],index=label_matrix[1:,0],columns=label_matrix[0,1:])
trans_df
suppose we are tracking some object in 2d space, we periodically take measurments and obtain the following data set:
move_data = pd.read_csv('obj_2d_data.csv')
move_data[:20]
In this case we are interested in tracking the current position of the object using the history of the previous positions. If we know that this object is experiencing a constant acceleration we can express the relationship between these points as: $$x_{t+1} = x_{t-1} + \frac{v_0 a}{2}(2t-1) + \epsilon_t$$
Where $\epsilon_t$ is i.i.d. normal noise with known variance. In this case we would be interested in estimating the product $\frac{v_0 a}{2}$ which we can simplify into a single parameter $\beta$ and represent it as follows $$x_{t+1} = x_{t-1} + 2\beta t - \beta + \epsilon_t$$.
Observe that if we knew $\beta$ then by knowing the initial condition (which we will call $x_0$ or the position at time 0) we can derive the location of the object at any point in the future. So to form our estimate we want to solve an optimization of the form: $$\min_{\beta,\hat{x}_0} \{ \sum_{t=0}^T\|x_{t} - \hat{x}_{t}\|^2 : \hat{x}_{t+1} = \hat{x}_{t-1} + 2\beta t - \beta \; \forall 1\leq t \leq T-1 \} $$
One useful techinque we can employ in this situation involves using a Kalman Filter such as the one implemented in the Holt-Winters Algorithm. These class of models are also considered Markov models since again $x_{t+1}$ only depends on the current time and position and not on any of the positions in the past. In this case however we have rather simple dynamics so we can solve this problem by directly solving the recursion as follows:
$$ \hat{x}_0 = \hat{x}_0$$$$ \hat{x}_1 = \hat{x}_0 + 2\beta - \beta = \hat{x}_0 + \beta$$$$\hat{x}_2 = \hat{x}_1 + 4\beta - \beta = \hat{x}_0 + 4\beta$$$$...$$$$\hat{x}_t = \hat{x}_0 + t^2\beta$$Now after solving the recursion we see we can solve the following equivalent least squares problem to obtain our estimates:
$$\min_{\beta,\hat{x}_0} \{ \sum_{t=0}^T\|x_t - \hat{x}_0 - t^2 \beta\|^2\} $$So adding a $t^2$ collumn to our data we can use an OLS solver to compute our estimates.