Re: Page and line penalties

[Joe Neeman]

On Fri, 7 Apr 2006 19:55, Han-Wen Nienhuys wrote:
> Joe Neeman wrote:
> > Suppose we add penalties. Let G(B) be the penalty function for a
> > partition into lines. G(B) has no nice structure at all. It will probably
> > be zero most of the time, with a few very large spikes. And we want to
> > minimize F(B) + G(B). Suppose the user makes a small change:
>
> I believe most of what you say; however, there are some questions:
>
> * IIRC, line breaking is not that stable as you suggest. It tends to
> have the same problem. Due to uniform density scoring, two consecutive
> line breaks may also have global effects.
You're right, it isn't very stable. But it certainly has the property that, if 
I take an optimal solution then a small change in the solution will produce a 
small change in the badness. For eg, if B is optimal and B' is B but with 
some breakpoint moved forward one bar and B'' is B but with the same 
breakpoint moved forward 2 bars, then F(B) < F(B') < F(B'').

>
> * Did you look at penalties for page-breaking at rests, or did you also
> put penalties for line-breaking?
I didn't put any penalties for line-breaking. My line-breaking arguments here 
are mostly speculation, but I have certainly observed instability in the 
page-breaking when demerits are involved.

>
> * Isn't it possible to devise a G(B) which has a more regular structure?
>    What kind of G(B)'s did you try?  I can imagine it might be
> difficult, but have we thought about all the alternatives?
I don't think so -- G(B) is zero unless the user introduces a penalty (and 
then, currently, it will be either -10001 or 10001). For page breaks, G(B) 
will be zero if the rest is long enough. The point is that G(B) depends only 
on the music at one specific point (the line/page break/turn) while F depends 
on the stretching of an interval of music. If I add an extra bar to the line 
I'm currently breaking, F will move along a parabola while G will jump up and 
down unpredictably.

>
> The problem that you sketch is not caused by F(B) being nice and G(B)
> not, but rather because their magnitudes are very similar.
I think they have to be. In the page-turning case, if G is much smaller than 
F, the penalties for a bad turn get ignored. Conversely, if G is too big, we 
sacrifice nice spacing. I hadn't actually thought of this before, but it 
looks like this might be a main cause of the instability. I don't see a way 
around it while keeping penalties, though.

>
> For example, what if you adjust the penalty of a page-breaks by using
> the max distance to the next/previous rest? Then an isolated rest in a
> fully filled score will get a huge bonus, but for scores with more
> rests, the penalties will be small, relative to the spacing penalties.
I don't think an isolated rest needs much of a bonus. If available page turns 
are widely spaced, the line- and page-breaking force becomes much more 
significant than penalties because we will be unable to squeeze any more on 
that particular page.

>
> * is there any value in removing page-break penalties? Shouldn't we
> rather add a forbid/allow property, and otherwise just use normal
> penalties?  Then we use forbid/force for user tweaks, with automatic
> penalties (ie. restrict the domain of possible B). This doesn't change
> the shape of the graph, just the parts that we consider. Of course, this
>   may still cause jumps of the optimum, but they might be more predictable

I've been using page-break penalties to break my own scores for some time now 
and I would ask the opposite question -- is there any value in keeping them? 
The problem is that we end up with statements like "if this rest is 1/8 
longer, we would be willing to accept an extra force of 2.2". These numbers 
are really pretty arbitrary and they don't have much meaning. Typical use 
case (for me):
1) Break a score with the default values
2) Decide that the algorithm is skipping a perfectly good page turn because 
the penalty is too high
3) Tweak context settings so the penalty function is a bit smaller
4) Find that I didn't tweak it enough. Tweak more.
5) Now it's too permissive. I have bad turns all over the place.
6) ...

I would prefer just having a threshold -- allow breaks for rests longer than 
the threshold, forbid them for shorter rests.
1) Break a score with the default values
2) Decide that the algorithm is skipping a perfectly good page turn because 
the threshold is too high.
3) Manually add \allowBreak. This won't affect any of the other potential 
breakpoints and I don't have to guess parameters and recompile endlessly. 
Also, I know that the spacing will /only get better/ because the only thing 
that has changed is that LilyPond has an extra option in deciding turns.

So I don't think (any more) that page turn penalties are valuable. It would be 
nice if LilyPond could intelligently avoid bad page turns but adding 
penalties based on rest length just makes things fiddly and hard to override.

Now my current algorithm _does_ use penalties. I can try to clean up my 
patches and submit it without removing the penalties. Then other people can 
test for themselves instead of just taking my word for it.

Joe