Pruning rule in Pelt

[lebateleur]

Hi! First of all, thank you for the great library - it has been a joy to use!

I have a question about the Pelt search algorithm. In the Pelt class, the _seg method first computes the new additional cost for each chosen breakpoint and admissible partition before that. This is done at line 71:

tmp_partition.update({(t, bkp): self.cost.error(t, bkp) + pen})

But then, when pruning non-optimal partitions, at lines 77-81

            admissible = [
                t
                for t, partition in zip(admissible, subproblems)
                if sum(partition.values()) <= sum(partitions[bkp].values()) + pen
            ]

the condition (if ...) in the list comprehension adds a new penalty term pen to sum(partitions[bkp].values(). I am struggling to understand, since the algorithm you describe on p.21 of the paper does not add this second penalty term.

Is this a mistake or am I misunderstanding something? I'd be grateful for your help.

[deepcharles]

Hi, sorry for the very late reply.

We add pen to the sum for the following reason. (I use the notations of our paper.)

• pen is equal to beta,
• sum(partition.values()) is equal to Z[s] + c(ys..t) + beta,
• sum(partitions[bkp].values()) is equal to Z[t].

Therefore the rule Z[s] + c(ys..t) ≤ Z[t] (from the paper) is equivalent to Z[s] + c(ys..t) + beta ≤ Z[t] + beta (from our code).

Hope this helps