# Probabilistic linebreaking algorithm

I'm currently trying to implement this paper:

Bouckaert, Remco R., A probabilistic line breaking algorithm, Gedeon, Tamás D. (ed.) et al., AI 2003: Advances in Artificial Intelligence. 16th Australian conference on AI, Perth, Australia, December 3--5, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20646-9/pbk). Lecture Notes in Computer Science 2903. Lecture Notes in Artificial Intelligence, 390-401 (2003). ZBL1205.68488.

Based on a bayesian network, the paper stays unclear about how to ultimately use its content ("straightforward inference"). But after a lot of researches (I have no background in that field), I think I can apply Viterbi algorithm to get the expected result. I will give here a description of my problem but as I might have misunderstood some things, the non biased description of the algorithm is available Section 3.1 of the paper.

We try to find a set of breakpoint $$S$$.

The test case is "aaa bb cc ddddd" with text width 6 which should result in:

aaa
bb cc
ddddd


which is a set of breakpoints $$S = \{0,1,3,(4?)\}$$. Just for information, for the test, I use o-=14 and o+=3 to get more manageable results (ref. paper).

We try to find the boolean value of $$i \in S$$ for each word (character in the paper). We start with the beginning of the paragraph with nlw0=0 (nwli is the width of a line from previous breakpoint) and $$0 \in S$$.

First take next token c1 = "aaa" with width cw1 = 3.

So, trying to use the Viterbi algorithm, I explore both possibilities of $$i \in S$$ and $$i \not\in S$$. It leaves us with two paths, set of breakpoints with nlwi = 3 (Pa is described page 7):

{0,1} with Pa(0, -6)≅0.8713
and {0} with Pa = 1

No choices here to make so it's seems okay. But I'm not sure if I even use Pa the right way...

Then I tried a few things which all ended wrong. It more or less looked like this:

Take next token cw2, try all possibilities and keep only the best ones for 2 ∈ S and 2 ∉ S.

It gives use 4 different sets:

{0,2} with Pa(3, -3) 4.45 product previous Pa. Total≅ 4.45
{0,1,2} with Pa(3, -3)≅ 4.45 product previous Pa. Total≅ 3.877
{0} Pa=1. Total=1
{0,1} Pa=1. Total≅ 0.8713

The best two sets we keep are {0,2} and {0} which already discards the expected result. Anyway I usually end up with no breakups at all...

So I'm probably missing something important. There are a few things I don't get in the paper either:

• What is node bi used for?
• and why is Pa described as the "acceptability of breaking-up up to ci instead of ci-1?
• Isn't P_a the probability function? Why do you have values outside of [0,1]? – merv Sep 6 '18 at 15:29
• Hum. Yes, I think Pa is the probability function or at least I treated that way. What do you mean by "outside [0,1]"? "[0,1]" is a set of indexes for which i ∈ S. – lprndn Sep 6 '18 at 15:35
• By [0,1] I mean the interval from 0 to 1, which is where probability values are valid. – merv Sep 6 '18 at 15:55
• In my code (in clojure), I keep them together in a record {:breakups [0, 1], :acceptability 0.873} . As I understand the probability of a path at i as the probability of i-1 multiplied by current Pa so I don't need to keep them further, do I? – lprndn Sep 6 '18 at 16:13
• Correct, you shouldn't need to store previous intermediate probabilities, but you might want to for debugging. I'm just asking why are you getting a probability value of 4.45? That doesn't make any sense - you can't have probabilities greater than 1. – merv Sep 6 '18 at 16:59