lawmurray / birch Goto Github PK

I use Birch for implementing a HMM for a model of two legs in a course of motion. Basically, I have a state transition model, which is linear and Gaussian with a non-diagonal covariance and an observation model, which is non-linear with Gaussian noise. Thus, I use a vector expression for the state variable, which I split up in a vector of expressions to compute the observation variable.

Previously, I used split in my code. After the most recent update of Birch, split is deprecated. I guess I should use vector_split, but it is not clear to me, how a VectorSplitExpression is used. With split, I could define a new variable x (vector of expressions), whose elements I could access using the bracket operator, see code fragment below.

function state_to_observation(u:Random<Real[_]>) -> Array<Expression<Real>> {
  let x <- split<Real>(u);
  y:Array<Expression<Real>>;

  y.insert(1, x[15]*cst_0 + x[13]*cos(x[3]) + (x[14] + g)*sin(x[3]));
  ...
  return y;
}

How can I use vector_split and how can I access the elements of the vector after using vector_split?

Not sure if this is the right place to ask a question, but I did not find any other place to do so.

We recently replaced cdf functions from Boost Math with our own implementations. The aim is to do so for quantile functions too. This will allow us to integrate them with the Expression hierarchy and the various features that it provides, such as automatic differentiation, as well as future accelerator support.

As part of upgrading to C++17, we also replaced the use of the Boost FileSystem library with its new STL equivalent. Quantile functions are the last remaining use of Boost, and will allow us to eliminate it as a dependency. That may have the added side effect of improving build times given the complexity of some Boost code. Generally, though, eliminating dependencies simplifies maintenance, too.

There are two steps:

1. Augment the test suite with a new set of tests for the quantile functions. See the cdf tests as a starting point. A simple test paradigm would be to repeatedly draw random samples x from the distribution, evaluate y = quantile(cdf(x)), and check that abs(x - y) < ε.
2. Once the tests are implemented such that all the current Boost-based quantile functions are passing, reimplement them in pure Birch. The quantile functions are found in quantile.birch. Currently most of them use nested C++ code to call Boost functions. The aim is to replace this with pure Birch implementations, as has been done in cdf.birch.

Implementing the quantile functions may involve implementing some special functions, which may have standard approximations based on Taylor expansions or similar. This is part of the fun and a good learning experience. The existing implementations in Boost Math, or in a numerical library such as NumPy, may provide a good reference.

==> Installing dependencies for lawmurray/birch/birch: birch-standard, freetype, libffi, pcre, gdbm, [email protected], readline, sqlite, xz, [email protected], glib, pixman, cairo, birch-cairo and birch-sqlite
==> Installing lawmurray/birch/birch dependency: birch-standard
==> ./configure --enable-debug --enable-release --prefix=/usr/local/Cellar/birch-standard/0.195
Last 15 lines from /Users/jobo/Library/Logs/Homebrew/birch-standard/01.configure:
checking whether C++ compiler accepts -fprofile-abs-path... no
checking whether C++ compiler accepts -Wno-overloaded-virtual... yes
checking whether C++ compiler accepts -Wno-inconsistent-missing-override... yes
checking whether C++ compiler accepts -Wno-attributes... yes
checking whether C++ compiler accepts -Wno-int-to-pointer-cast... yes
checking whether C++ compiler accepts -Wno-unused-parameter... yes
checking whether C++ compiler accepts -Wno-unused-variable... yes
checking whether C++ compiler accepts -Wno-unused-value... yes
checking whether C++ compiler accepts -Wno-unused-local-typedefs... yes
checking whether C++ compiler accepts -Wno-unknown-pragmas... yes
checking for library containing dlopen... none required
checking for main in -latomic... no
checking for main in -lomp... yes
checking for main in -lbirch-debug... no
configure: error: required library not found

If reporting this issue please do so at (not Homebrew/brew or Homebrew/core):

Currently the resampling scheme is hard-coded in Birch: we use systematic resampling for standard particle filters, and multinomial resampling for conditional particle filters. The aim of this project is to implement some alternative resampling algorithms and provide the user with a choice of which to use.

Currently, all resampling functions are implemented in resample.birch. We would instead like to create a src/resampler directory and provide a hierarchy of classes such as MultinomialResampler, StratifiedResampler, etc, from which the user can choose. LibBi provides such a setup, which may be a useful reference.

For the filter and sample programs, we could then add support for choosing a resampler using something like the following in the config file, much like one can choose a filter class and sampler class at the moment:

"resampler": {
  "class": "StratifiedResampler"
}

A good set to include would be the multinomial, stratified and systematic resamplers, (see Murray, Lee & Jacob, 2015 for implementation) and the SSP algorithm (Gerber, Chopin & Whiteley, 2019).

References

• L.M. Murray, A. Lee and P.E. Jacob (2015). Parallel Resampling in the Particle Filter. Journal of Computational and Graphical Statistics. [doi] [arXiv]

• Gerber, M., Chopin, N., and Whiteley, N. (2019). Negative association, ordering and convergence of resampling methods. Ann. Statist. 47, 4:2236--2260. [doi] [arXiv]

Recursive data structures have a special place in Birch: they allow sharing of objects between particles across resampling epochs (Murray, 2020). For N particles and T steps, this enables O(T + N log N) (Jacob, Murray & Rubenthaler, 2015) or even O(T + N) (Koskela, Jenkins, Johansen & Spanò, 2020) memory use. Singly-linked containers such as Stack and Tape are particularly good in this regard. Dense arrays, on the other hand, do not enable object sharing. If dense arrays are used to store state history across resampling epochs, only O(TN) memory use is achieved. Dense arrays are represented in Birch using e.g. Real[_].

Two of the standard containers, Array and RaggedArray are implemented using a dense array under the hood. The aim is to replace them with a persistent array implementation instead. We will then have a consistent usage pattern where the containers provided by the standard library are all recursive data structures and provide efficient memory use across reampling epochs, while dense arrays are typically used only for numerical vectors and matrices. No more design paralysis between Array<MyClass> and MyClass[_]!

One possible way of implementing RaggedArray<Type> would be to use, essentially, Array<Array<Type>>.

References

• L.M. Murray (2020). Lazy object copy as a platform for population-based probabilistic programming. [arxiv]

• P.E. Jacob, L.M. Murray and S. Rubenthaler (2015). Path Storage in the Particle Filter. Statistics and Computing. 25(2):487--496. [doi] [arXiv]

• J Koskela, P A Jenkins, A M Johansen, and D Spanò. Asymptotic genealogies of interacting particle systems with an application to sequential Monte Carlo. Annals of Statistics 48(1):560-583, 2020 [AoS] [arXiv]

As per instructions in README.md, trying to run ./configure --prefix /usr/local. I am getting the following error:

checking for eigen3/unsupported/Eigen/SpecialFunctions... no
checking for unsupported/Eigen/SpecialFunctions... no
configure: error: required Eigen header not found.

What could be the problem? I installed Eigen (versions 2 and 3) using MacPorts

$ port installed | grep eigen
  eigen @2.0.17_0 (active)
  eigen3 @3.4.0_1 (active)

Hej 🙂

I just wanted to install Birch on my new computer and noticed that there are no pre-built packages available for Fedora 36. Of course, I could just compile Birch but that takes time and is less convenient than the distribution packages when I don't intend to work on Birch itself. Maybe it would be helpful also for other users to update the supported distros in the OBS and build the latest release for newer versions of Fedora, openSUSE, etc. as wel?