Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A linear memory algorithm for Baum-Welch training   Background: Baum-Welch training is an expectation-maximisation algorithm for
training the emission and transition probabilities of hidden Markov models in a
fully automated way.
  Methods and results: We introduce a linear space algorithm for Baum-Welch
training. For a hidden Markov model with M states, T free transition and E free
emission parameters, and an input sequence of length L, our new algorithm
requires O(M) memory and O(L M T_max (T + E)) time for one Baum-Welch
iteration, where T_max is the maximum number of states that any state is
connected to. The most memory efficient algorithm until now was the
checkpointing algorithm with O(log(L) M) memory and O(log(L) L M T_max) time
requirement. Our novel algorithm thus renders the memory requirement completely
independent of the length of the training sequences. More generally, for an
n-hidden Markov model and n input sequences of length L, the memory requirement
of O(log(L) L^(n-1) M) is reduced to O(L^(n-1) M) memory while the running time
is changed from O(log(L) L^n M T_max + L^n (T + E)) to O(L^n M T_max (T + E)).
  Conclusions: For the large class of hidden Markov models used for example in
gene prediction, whose number of states does not scale with the length of the
input sequence, our novel algorithm can thus be both faster and more
memory-efficient than any of the existing algorithms.

28
The categories of this paper are: alg-geom
36
The categories of this paper are: cmp-lg
24
The categories of this paper are: dg-ga
3
The categories of this paper are: physics
23
The categories of this paper are: solv-int
22
The categories of this paper are: chao-dyn
20
The categories of this paper are: acc-phys
0
The categories of this paper are: hep-ph
5
The categories of this paper are: gr-qc
8
The categories of this paper are: hep-ex
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
12
The categories of this paper are: nucl-th
25
The categories of this paper are: patt-sol
26
The categories of this paper are: bayes-an
32
The categories of this paper are: atom-ph