Probabilistic Scraping of Plain Text Tables (2013)

https://edinburghhacklab.com/2013/09/probabalistic-scraping-of-plain-text-tables/

by polm23 • 7 years ago

92 8 7 years ago

Oh a blast from my past! That was some super fun work using mixed integer programming to fuse hard global knowledge (table structure) with soft information (OCR predictions). It worked pretty well. My only regret was spelling the title wrong, it hurts me reading it everytime.

stereolambda• 7 years ago

This is very, very neat and not requiring excessive setup, which would be needed with practically any kind of ML procedure (manual annotation - probably defeating the purpose, handling structure). Fitting around 1000 booleans is indeed not much of a problem.

Would you mind sharing how many rows was it? I know it's probably possible to reverse-engineer it from other information, but I think it would be illustrative.

Also, this fragment is interesting:

Whilst integer programming is NP-hard to solve in general, these problem instances are not pathological instances

Could this kind of tabular data have turned out to be pathological? Would it mean that constraints cannot be met and we had to search the whole space to ascertain that? I imagine these general solvers don't do specific heuristics when searching.

tlarkworthy3• 7 years ago

Depends on the table, the digikey catalog is thousands of small tables, but most are around 20 rows. It's worth noting some header rows are multi line, which is part of the difficulty, the MIP encodes where to start in the ASCII representation where the header ends and the data starts.

these problem instances are not pathological instances

With MIP, the solver churns when you get a lot of information suggesting that one path is likely to be the optimal but actually it's another path but you have been mislead by red herrings. One cause would be a subset of weak classifiers are configured incorrectly so they are actively misleading. Another cause might be that the table structure is very ambiguous and requires a lot of global deductive reasoning to figure it out.

However, given digikey is not maliciously trying to create difficult to read tables, I don't think these cases really come up. Misleading weak classifiers would be a bug, though its sometimes hard to spot if enough of the system still reaches the correct decision. There is probably some math to assign utility to certain classifiers though I never looked at it beyond case by case debugging of decision samples.

Also worth noting this never went into full production due to the surrounding business being broken for completely non-technical reasons. But I do think the MIP + MLE is a useful technique for a few different forms of problems where you want to integrate hard ontological constraints over a fuzzy reasoning system.

comfymatrix• 7 years ago

Out of curiosity, what stopped you from making several regexes, especially for the product numbers (ending in "-ND")? Was it mainly for edge cases or cases where it might have been slightly different?

Or, was it due data context, which I assume is more plausible. I ask because I maintain an old, slightly large, and growing project which contains about 12 different regexes and is used on messy unstructured data. I'm in the process of rewriting it into a more general framework using NER + RNNs or HMMs, but this seems like a very interesting approach.

tlarkworthy3• 7 years ago

So a regex is used for the weak classifiers, just they are not trusted. So you say a thing ending in -ND is 90% chance of being a part number. So you have regexes with wiggle room. Then u dictate hard knowledge that table headers must be above data, and then the MIP solver has the freedom to override the regexes classifiers with knowledge from elsewhere. This works well if you have some really strong top level structural knowledge.

JadeNB• 7 years ago

I'm not sure if mirroring typos in the linked article is the intention, but of course it should be 'probabilistic', not 'probabalistic', even though the linked article has it the latter way.

dang2• 7 years ago

Fixed above now. Thanks!

dang2• 7 years ago

Discussed at the time: https://news.ycombinator.com/item?id=6334178

Probabilistic Scraping of Plain Text Tables (2013)

Related Stories