scikit-learn/scikit-learn — pull request #862 by duckworthd (2012-05-16 18:23:04+00:00)
Title: WIP: Kalman Filter, Smoother, EM

This is a stub for a work in progress. The goal is to provide a module for efficiently and easily applying algorithms for inferring the hidden state of a system, denoted `x`, generated from the following bit of code,

```python
for t in range(T)
e1[t] = np.random.multivariate_normal(0, Q)
e2[t] = np.random.multivariate_normal(0, R)
x[t+1] = A.dot(x[t]) + b[t] + e1[t]
z[t+1] = C.dot(x[t+1]) + d[t] + e2[t]
```

The initial goal is to provide 3 algorithms. The first two, the [Kalman Filter][1] and [Kalman Smoother][2], are for estimating `x` given observations `z`, state transition matrix `A`, transition offsets `b`, observation matrix `C`, observation offsets `d`, and covariance matrices `Q` and `R`. The two algorithms differ in one aspect: while the Filter estimated `z[t]` using `z[0:t]`, the Smoother estimates the same using `z[0:T]` at additional computational cost. The third algorithm, the [EM algorithm][3] as applied to the Linear-Gaussian system, iteratively approximates `Q` and `R` by maximizing the likelihood of the observations.

Current Progress:
+ Kalman Filter, Kalman Smoother, EM algorithm implemented, tested
+ Example provided
+ Test dataset added

Todo:
- User's Guide documentation
- Cython implementation
- Estimation of `A`, `b`, `C`, `d` in EM algorithm

All comments and suggestions are appreciated. This is my first significant contribution to an open source project, so I can use all the help I can get!

[1]: http://en.wikipedia.org/wiki/Kalman_filter
[2]: http://inst.eecs.berkeley.edu/~cs294-40/fa08/scribes/lecture14.pdf
[3]: http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm