Blocking rule learning, similar to dedupe library

[NickCrews]

Posting this here, create an issue from this if you want.

One of the most time-consuming steps for me is tuning the blocking rules. Too loose, and I get too many pairs, too strict and I get low recall. It's currently painful to manually tweak these.

The dedupe library learns the blocking rules for you. Could we do something like that?

I believe they

• start with a set of atomic blocking rules
• from these, generate more complex rules by AND-ing and OR-ing them together in a random forest
• select rules using a set-cover algorithm: "choose the rules that make the fewest false-positives, while covering at least n% of the true positives"

refs:

• docs: https://docs.dedupe.io/en/latest/how-it-works/Making-smart-comparisons.html#learning-good-blocking-rules-for-given-data
• implementation: https://github.com/dedupeio/dedupe/blob/c0afd4fa70b21ef55fa3bd5cd78e80926010dfc6/dedupe/training.py#L26
• Other idea they had: blocking for partitioning dedupeio/dedupe#870

[RobinL]

Hi Nick. This is great feedback, thanks, and nice research on how it's done in dedupe.io - very useful.

I agree that choosing blocking rules is more painful than it needs to be, and that we should aim to automate this. Some thoughts:

• I think a prerequisite to is implementing a more efficient way of estimating the total comparisons generated by a given blocking rule. This would enable us to quickly test a variety of different blocking rules to find which ones lead to an acceptable number of comparisons . At the moment, we essentially do a select count(*) from df as l inner join df as r on {blocking_rule}, which creates the comparisons and then counts them. But this is slow. For most blocking rules, this can be achieved without the join with something more like with a as (select count(*)^2 as count from df group by {blocking condition}) select sum(count) from a. I believe @ThomasHepworth has been doing some initial work on this already

• I'm not convinced that the dedupe.io approach using labelled data to generate optimal blocking rules is the best approach for two reasons:

1. We don't usually have high quality labels. By high quality I mean labels that we can trust and capture all of the edge cases*. Simple blocking rules generally capture the easy matches, but miss edge cases. So we’d have to be sure the labels included the edge cases.

2. The problem is more about optimising runtime than optimising recall**. We're trying to make the blocking rules as loose as possible within a particular target runtime. A blocking rule that creates lots of comparisons is not a problem so long as runtime is acceptable.

I'd be interested in your thoughts about the above, and whether you agree. All above is a gut feeling - I can’t prove it quantitively.

*Humans are often quite bad at manual labelling in our experience
**Clearly in reality it’s a tradeoff between the two. But in the absence of labels, it’s probably better to focus on runtime i.e. what are the loosest blocking rules that result in an acceptable runtime.