<NEWS>
``And once the storm is over you won't remember how you made it through, how you managed to survive. You won't even be sure, in fact, whether the storm is really over. But one thing is certain. When you come out of the storm you won't be the same person who walked in. That's what this storm's all about.''
-Haruki Murakami
----------------------------------------------
THE OFFICIAL GOLDEN DOODLE OF UM
During an afternoon of Patrick and Oliver playing fetch with Patrick's dog Butters, Butters was recorded in a video that is slated for use in offial promotion for the University of Montana.
----------------------------------------------
COBRE GRANT AWARD
The Serang Lab has been awarded a COBRE grant. This grant will be used to hire UM graduate students to build new graphical models for two cutting-edge problems from computational biology.
----------------------------------------------
UM PILOT PROJECT GRANT AWARD
The University of Montana has awarded the Serang Lab a pilot project grant. This grant will fund a UM computer science student to work on an exciting project developing EvergreenForest, a new graphical models library.
----------------------------------------------
TEXTBOOK: CODE OPTIMIZATION IN C++11
Oliver Serang's textbook, Code Optimization in C++11 is now online.
Check it out here.
██████╗ ██████╗ ██████╗ ███████╗
██╔════╝██╔═══██╗██╔══██╗██╔════╝
██║ ██║ ██║██║ ██║█████╗
██║ ██║ ██║██║ ██║██╔══╝
╚██████╗╚██████╔╝██████╔╝███████╗
╚═════╝ ╚═════╝ ╚═════╝ ╚══════╝
██████╗ ██████╗ ████████╗██╗███╗ ███╗██╗███████╗ █████╗ ████████╗██╗ ██████╗ ███╗ ██╗
██╔═══██╗██╔══██╗╚══██╔══╝██║████╗ ████║██║╚══███╔╝██╔══██╗╚══██╔══╝██║██╔═══██╗████╗ ██║
██║ ██║██████╔╝ ██║ ██║██╔████╔██║██║ ███╔╝ ███████║ ██║ ██║██║ ██║██╔██╗ ██║
██║ ██║██╔═══╝ ██║ ██║██║╚██╔╝██║██║ ███╔╝ ██╔══██║ ██║ ██║██║ ██║██║╚██╗██║
╚██████╔╝██║ ██║ ██║██║ ╚═╝ ██║██║███████╗██║ ██║ ██║ ██║╚██████╔╝██║ ╚████║
╚═════╝ ╚═╝ ╚═╝ ╚═╝╚═╝ ╚═╝╚═╝╚══════╝╚═╝ ╚═╝ ╚═╝ ╚═╝ ╚═════╝ ╚═╝ ╚═══╝
██╗███╗ ██╗ ██████╗ ██╗ ██╗
██║████╗ ██║ ██╔════╝ ██╗ ██╗ ███║███║
██║██╔██╗ ██║ ██║ ██████╗██████╗ ╚██║╚██║
██║██║╚██╗██║ ██║ ╚═██╔═╝╚═██╔═╝ ██║ ██║
██║██║ ╚████║ ╚██████╗ ╚═╝ ╚═╝ ██║ ██║
╚═╝╚═╝ ╚═══╝ ╚═════╝ ╚═╝ ╚═╝
----------------------------------------------
THE LAUNCH OF EXPLORING SCIENTIFIC WILDERNESS
Exploring Scientific Wilderness is a new podcast miniseries with short and sweet pieces of scientific brain candy.
----------------------------------------------
EVERGREENFOREST INFERENCE ENGINE 0.9
After years of work, the beta version of
EvergreenForest has been released! It includes a fast,
lazy implementation of trimmed convolution trees, a
fast in-house FFT written in C++11 (using the lab's
work on methods for performing bit-reversed
permutation), and lots of other Waldmeister-flavored
goodies to activate your almonds.
You can read more about it and download it
here.
----------------------------------------------
THE INVENTION OF ``TRIMMED'' CONVOLUTION TREES
Trimmed convolution trees use sparsity in the solution
space exploit sparsity in the input priors and
likelihood of a convolution tree to achieve an
algorithmic and practical speedup. For example, when
all input priors are $$X_i \in \{0,1\}$$ and the
likelihood $$Y=X_1 + X_2 + \cdots X_n \in \{0,1\},$$
all posteriors can be solved with trimmed convolution
trees in $$O(n)$$ rather than the $$O(n \log(n)
\log(n))$$ required by non-trimmed convolution
trees.
Trimmed convolution trees generalize this to use
narrower priors and likelihoods, even when some priors
have larger support than others or when the likelihood
distribution has are larger support than all priors,
smaller support, or anything, making the first method
$$\in o(nk \log(nk) \log(n))$$ on some problems with
$$n$$ inputs each with $$k$$ bins.
The paper (in review) includes a demo that uses
trimmed convolution trees to estimate posterior
probabilities for peoples' orders given their total
ice cream bill; the demo is, of course, written using
the menu from
Missoula's
own Big Dipper Ice Cream.
----------------------------------------------
FAST C++11 METHODS FOR BIT-REVERSED PERMUATION
The bit-reversed permutation is an important task for
implementing an in-place FFT library. This paper
explores several bit reversal methods on the x86
architecture, including new bit twiddling tricks and a
proposed template-recursive, cache-oblivious method,
which achieves state-of-the-art performance.
The paper draft can be found
here. The
repository (linked in the paper) includes translations
in the mother tongue of each student who participated
(Chinese, German, Turkish, and Spanish) to help
students throughout the world participate in the joy
of scientific computing. So when someone says, ``Bit
reversal? How?'' you can say, ``很好!''
----------------------------------------------
A FASTER, SIMPLER MULTIDIMENSIONAL ARRAY LIBRARY IN C++11
Florian Heyl, who is doing his masters Praktikum in the
group, has just had his first paper accepted for
publication. The paper (Heyl & Serang 2017,
PROGRAMMING) introduces and benchmarks the
``template-recursive iteration over tensors'' (TRIOT)
design pattern in C++11. The method enables easy
vectorizing over tensors of different shaps and does not
require tensor dimensions to be fixed at compile
time.
Download the free header-only
library here.
----------------------------------------------
MORE ACCURATE NUMERIC P-CONVOLUTION
The lab's
second paper on the
topic (Pfeuffer
& Serang 2016, Journal of Machine Learning Research)
builds upon the original idea, looking at the curve of
(modeled using orthogonal polynomials) of a constant
number of $$L_p$$ spaces. The way that these spaces bend
toward the true maximum can allow us to estimate the
maximum better than any particular numerically stable
p-norm.
The paper highlights the approach with faster prediction
of U.S. unemployment given S&P 500 index data (via a
fast Viterbi path computation).
----------------------------------------------
THE INVENTION OF FAST NUMERIC MAX-CONVOLUTION
Max-convolution, a cousin of standard convolution but on
the semiring $$( \times, \max )$$ (consider multiplying
two polynomials but taking the maximum coefficient for
every term rather than the sum of coefficients for that
term), arises frequently in combinatorics and in
Bayesian inference. In 2006, Bremner et al. discovered
the first solution $$\in o(n^2);$$ theirs is a beautiful
method, but it's only slightly sub-quadratic and relies
on a reduction to APSP, and it is not fast enough for
large-scale use in Bayesian networks. However, this
problem can be approximated numerically by using $$L_p$$
space, where FFT can be used in $$\in O(n
\log(n))$$ (Serang
2015, Journal of Computational Biology). The method
can also be used to improve hidden Markov models (HMMs)
with with k states from $$O(k^2 n)$$ to $$O(k \log(k)~
n),$$ whenever the transition matrix is a Toeplitz
matrix.
Combined with the probabilistic convolution tree, the
method can be used for max-product inverence when $$Y =
X_1 + X_2 + \cdots + X_n.$$ This can be used to solve a
generalization of the knapsack problem on
integer-discretized supports.
----------------------------------------------
A FASTER DYNAMIC PROGRAMMING ALGORITHM
The probabilistic convolution tree (Serang 2014, PLOS ONE) is a new dynamic programming algorithm that solves a class of probabilistic problems, which are equivalent to a generalization of subset-sum on integer-discretized supports. When $$Y = X_1 + X_2 + \cdots + X_n$$ and each $$X_i \in \{0, 1, \ldots k-1\}$$ it computes all marginals simultaneously with a runtime $$\in O(n k \log(n k) \log(n)).$$
----------------------------------------------