Multiple paths leading to same label during CTC Beam Search I am currently implementing CTC Beam Search:

After implementing the algorithm verbatim, and running it, I realized that I was getting probabilities that were > 1.
Looking more at the algorithm, I'm thinking that this issue is linked to the fact that lines 7, 10, 13 and 14 of the algorithm are assignment only, instead of adding to the existing value (or 0 if none existing previously). I don't really understand this : if you're reaching a labelling at time t from multiple sources, the probability sum, don't they? 
This also makes the $\hat{y}$ section of the algorithm (line 8 & 9) disappear, since $\hat{y}$ will be (or has been) considered whilst iterating over $\hat{B}$. 
Is this interpretation correct, or am I missing something in my understanding of the algorithm?
 A: I split this answer into two parts: the second part shows the discussion with Jenkar about this topic, while the first part summarizes (based on part 2) how to implement the beam search algorithm. A more in-depth presentation can be found at "Towards Data Science" [4].

Part 1: how to implement CTC beam search
As a reminder, there can be more than one path p representing the same labeling y (text), as the mapping p->y is done by first remove all duplicate characters in p and then remove all blanks (denoted as "-" in this text), e.g. "aa-b" -> "ab" but also "-ab-" -> "ab".
The essential part is to manage the probabilities separately for paths ending with a blank (B) and paths ending with a non-blank (NB).
An example for B is the path "a-" while an example for NB is "aa".
The following illustration shows the labeling "a" and one corresponding instance for a path NB ("-aa") and one for a path B ("a--") after the third iteration (time-step) of the algorithm (of course, there are other paths too).
The probabilities P_B("a",t) and P_NB("a",t) are saved for the current time-step t and the labeling "a". 
In the next (the fourth) iteration t+1, the algorithm calculates the new probabilities.
There are two main cases:


*

*NB: adding an "a" (the last character in the path) to all of these paths still yields the labeling "a". The same is true when adding "-". When adding a new character "k" (here "k" is a placeholder for some actual character, however it must be different from "a"), this yields "ak".

*B: either we add another "-" at the end, which still yields "a", or we add a new character "k" (can be equal to "a" in this case), which yields "ak".



With this information, we are able to build the beam search algorithm in the context of CTC:


*

*for a non-empty labeling y, take last character y[-1], get its probability from neural network output and multiply with P_NB(y,t) to get new P_NB(y,t+1)

*the new P_B(y,t+1) is simply the probability of "-" multiplied with P_NB(y,t)+P_B(y,t)

*a new labeling y'=y+k can be calculated by adding a new character k to the paths. If k==y[-1], then the paths must contain a separating "-", therefore we use P_B(y,t), otherwise we use P_B(y,t)+P_NB(y,t). 

*the same labeling can occur multiple times, in this case we just sum up the probabilities (e.g. labeling "a" extended by "-" yields "a", but also labeling "" extended by "a" yields "a").


The following pseudo-code shows the beam search algorithm which I use in the context of handwritten text recognition [3].
B is the set of beams, P_B and P_NB were already explained, P_TOT=P_B+P_NB, B_HAT is the set of the bw best beams, bw is the beam width, y is a labeling, k is a new character, mat is the matrix which contains the character probabilities for each time-step t=1..T as calculated by the neural network.
A character-level language model p(k|y) is integrated - it can be removed by setting p(k|y)=1 and deleting lines 23-25.


Part 2: original discussion (only for documentation - can be skipped)
I'm currently facing exactly the same problem.
Did you find a solution to this?
There is an open source implementation [2], but it looks wrong to me. They just add another entry for each new labelling y. 
I will now switch to Prefix Search Decoding and try to implement it [2]. At least Tensorflow internally uses this implementation and it works (they call it beam search). 
(I had to use the answer function as commenting is not possible [<50 reputations] for me)

Edit, 27th of September, 2017:
After doing experiments on a HTR task with both versions (summing up or assigning the probabilities), summing up yields much better results.
It also makes more sense to me to sum up the probability of all equal labellings at a give time step instead of ignoring them.
Coming back to the algorithm: Instead of assigning probabilities, one has to add them (sum up) to the current values of Pr-, Pr+ and Pr.

Edit, 23th of October, 2017:
My python implementation of beam search decoding can  be found at github [3]

Edit, 28th of March, 2018:
Split into Part 1 and Part 2

References
[1] https://www.cs.toronto.edu/~graves/phd.pdf, Algorithm 7.1
[2] https://github.com/bshillingford/ctc-beam-search/blob/master/ctc_beamsearch.py
[3] https://github.com/githubharald/CTCDecoder
[4] https://towardsdatascience.com/5a889a3d85a7
