10TimeSeries.tex

% -*- root: Main.tex -*-
\section{Time series}
\subsection*{Markov Model}
Markov assumption: $P(Y_t|Y_{1:t-1}) = P(Y_t|Y_{t-1})$\\
Stationarity assumption:\\
$P(Y_{t+1}=y_1|Y_t=y_2) = P(Y_t=y_1|Y_{t-1}=y_2)$\\
Product rule:\\
$P(Y_t,...,Y_1) = P(Y_t|Y_{t-1},...,Y_1)\cdot ... \cdot P(Y_1)$\\
Sum rule:\\
$P(Y_{t+2}|Y_{1:t}) = \sum_{Y_{t+1}^i} P(Y_{t+2}Y_{t+1}^1|Y_{1:t})$
\subsection*{Hidden Markov Model}
triplet $M = (\Sigma, Q, \Theta)$\\
$\Sigma$ symbols, $Q$ states, $\Theta=(A,E)$ transition and emission, $e_k(b)$ emission prob. $x_k \in Q, b \in \Sigma$
\subsection*{Forward/Backward - Alternative}
Goal: $P(x_t|s) \propto P(x_t,s) = P(s_{t+1:n}|x_t)P(x_t,s_{1:k})$
\subsection*{Evaluation (Forward/Backward)}
Transition A and emission E known. Sequence s given.\\
Wanted: prob that s is generated by HMM.\\
\textbf{Forward:}\\
Wanted: $f_l(s_t) = P(x_t = l, s_{1:t})$\\
$f_l(s_{t+1}) = e_l(s_{t+1})\sum_k f_k(s_t) a_{k,l}$,\\
$f_l(s_1) = \pi_l e_l(s_1) \forall l \in Q$\\
\textbf{Backward:}\\
Wanted: $b_l(s_t) = P(s_{t+1:n}|x_t = l)$\\
$b_l(s_t) = \sum_k e_k(s_{t+1}) b_k(s_{t+1}) a_{l,k}$,\\
$b_l(s_n) = 1 \forall l \in Q$\\
Complexity in time: $\mathcal{O}(|\Sigma|^2 \cdot T)$

\subsection*{Decoding (Viterbi)}
Given: Observation sequence  $O= \{O_1 O_2 \dots O_T \}$, $a_{ij} = P(q_{t+1} = S_j | q_t = S_i)$, $b_j(k)=P(v_k \text{at t} |q_t = S_j)$ \\
Wanted: most likely path $Q = \{q_1,q_2,\ldots q_T\}$\\
$\delta_t (i) $ best score along single path, at a time t, which accounts for the first t observations and ends in $S_i$\\
$\delta_t (j) = max_{1 \leq i \leq N}[\delta_{t-1} (i)a_{ij}]b_j(O_t) $\\
$\phi_t(j)=argmax_{1\leq i \leq N} [\delta_{t-1}(i)a_{ij}]$\\
Time: $\mathcal{O}(|S|^2 \cdot T)$
Space $\mathcal{O}(|S| \cdot T)$

\subsection*{Decoding (Viterbi) - Alternative}
Transition $a_{i,j} = P(x_{t+1} = j |x_t = i)$ and emission $e_l(s_t) = P(s_t|x_t=l)$ known. Sequence s given.\\
Wanted: Most likely path x responsible for the sequence.\\
$v_l(s_{t+1}) = e_l(s_{t+1}) \max_k(v_k(s_t) a_{k,l})$\\
$v_l(s_1) = \pi_l e_l(s_1) \forall l \in Q$\\
Time: $\mathcal{O}(|\Sigma|^2 \cdot T)$, Space: $\mathcal{O}(|\Sigma| \cdot T)$
\subsection*{Learning (Baum-Welch)}
Know: Set of sequences $s^1,...,s^m$\\
Wanted: max transition A and emission E\\
\textbf{E-step I:} Compute all $f_k(s_t^j)$ (forward-algo.) \& $b_k(s_t^j)$ (backward algo.)\\
\textbf{E-step II:} Compute $A_{kl}$, $E_k(b)$ for all states and symbols\\
$A_{kl} = \sum_{j=1}^{m} \frac{1}{P(\textbf{s}^j)} \sum_{t=1}^{n}f_k^j (s_t^j)a_{kl}e_l(s_{t+1}^j)b_l^j(s_{t+1}^j)$\\
$E_k(b)=\sum_{j=1}^{m}\frac{1}{P(\textbf{s}^j)}\sum_{t|S_t^j=b}^{n}f_k^j(s_t^j)b_k^j(s_t^j)$\\
\textbf{M-step:} Compute param. estimates $a_{kl}$, $e_k(b)$\\
$a_{kl}=\frac{A_{kl}}{\sum_{i=1}^{n}A_{ki}}$, $e_k(b)=\frac{E_k(b)}{\sum_{b'}E_k(b')}$\\
Complexity: $\mathcal{O}(|\Sigma|^2)$ in storage (space).