Entity Resolution: The most common data science challenge
1–10 of 28 posts
Re: Entity Resolution: The most common data science challenge
#2Danger awaits all ye who enter this tutorial and have large datasets.
The tutorial is fun marketing material and all but its FAR too slow to be used on anything at scale. Please, for your sanity, don't treat this as anything other than a fun toy example.
ER wants to be an an O(n^2) problem and you have to fight very hard for it not to turn into one. Most people doing this at scale are following basically the same playbook:
1) Use a very complicated speed optimized non-ml algorithm to find groups of entities that are highly likely to be the same, usually based on string similarity, hashing, or extremely complicated heuristics. This process is called blocking or filtering.
2) Use fancy ML to determine matches within these blocks.
If you try to combine 1 & 2, skip 1, or try to do 1 with ML on large datasets you are guaranteed to have a bad time. The difference between mediocre and amazing ER is how well you are doing blocking/filtering.
Re: Entity Resolution: The most common data science challenge
#3Danger awaits all ye who enter this tutorial and have large datasets. The tutorial is fun marketing material and all but its FAR too slow to be used on anything at scale. Please, for your sanity, don't treat this as anything other than a fun toy example. ER wants to be an an O(n^2) problem and you have to fight very hard for it not to turn into one. Most people doing this at scale are following basically the same pla…
You are 100% correct, this is a toy example that I decided to put together for fun after talking to a bunch of people who mentioned it as a problem that they experience.
The main idea I wanted to add to the discussion (which is not that crazy of an addition) is that you can possible use sentence embedding instead of fuzzy matching on the actual letters to get more "domain expertise"
How to actually compare these embeddings with all the other embeddings you have in a large dataset is a problem that is completely out of the scope of this tutorial
Re: Entity Resolution: The most common data science challenge
#4I was expecting the use of sentence-transformers (sbert.net). If you have a long list of entities you could use an approximate similarity search library such as annoy. The authors store the embeddings in a database and decode json for each comparison. Very inefficient in my opinion. At least load the whole table of embeddings in a np.array from the start, np.dot is plenty fast if your list not huge.
The problem is still not solved. Having a list of the most similar entities does not tell you which are similar and which are just related. You need a classifier. For that you can label a few hundred pairs of positive and negative examples and use the same sbert.net to finetune a transformer. The authors use the easier route of thresholding cosine similarity score at 0.8, but this threshold might not work for your case.
Re: Entity Resolution: The most common data science challenge
#5Danger awaits all ye who enter this tutorial and have large datasets. The tutorial is fun marketing material and all but its FAR too slow to be used on anything at scale. Please, for your sanity, don't treat this as anything other than a fun toy example. ER wants to be an an O(n^2) problem and you have to fight very hard for it not to turn into one. Most people doing this at scale are following basically the same pla…
Great advice! What is your rough guesstimate - in big O - of a general least upper bound of what you can do with ER?
Re: Entity Resolution: The most common data science challenge
#6Entity resolution/record linkage/deduplication is an oddly specialized domain of knowledge given that it's such a common problem. I put together a page of resources a while back if anyone is interested: https://github.com/ropeladder/record-linkage-resources
Re: Entity Resolution: The most common data science challenge
#7Danger awaits all ye who enter this tutorial and have large datasets. The tutorial is fun marketing material and all but its FAR too slow to be used on anything at scale. Please, for your sanity, don't treat this as anything other than a fun toy example. ER wants to be an an O(n^2) problem and you have to fight very hard for it not to turn into one. Most people doing this at scale are following basically the same pla…
You are 100% correct, this is a toy example that I decided to put together for fun after talking to a bunch of people who mentioned it as a problem that they experience. The main idea I wanted to add to the discussion (which is not that crazy of an addition) is that you can possible use sentence embedding instead of fuzzy matching on the actual letters to get more "domain expertise" How to actually compare these embe…
Yeah, totally, I get you. I'm not trying to do a takedown, ER is just hard.
The point I was trying to make is that at scale one does not simply:
> compare these embeddings with all the other embeddings you have
You just can't, similarity metrics (especially cosine) on 768 dim arrays are prohibitively slow.
Using embeddings is quite common in the literature and in deployment (I have, in fact, deployed ER that uses embeddings), but only as part of #2, the matching step. In many projects, doing full pairwise comparisons would take on the order of years, you have to do something else to refine the comparison sets first.
Re: Entity Resolution: The most common data science challenge
#8Danger awaits all ye who enter this tutorial and have large datasets. The tutorial is fun marketing material and all but its FAR too slow to be used on anything at scale. Please, for your sanity, don't treat this as anything other than a fun toy example. ER wants to be an an O(n^2) problem and you have to fight very hard for it not to turn into one. Most people doing this at scale are following basically the same pla…
So much this. I work on spatiotemporal entity resolution and it requires extreme care and cleverness to not turn it into a proverbial "boiling the ocean" compute problem for all but the most trivial cases. The implied state that needs to be managed alone is often effectively intractable. At one time supercomputers were used for large-scale entity resolution problems; they may still.
Re: Entity Resolution: The most common data science challenge
#9Danger awaits all ye who enter this tutorial and have large datasets. The tutorial is fun marketing material and all but its FAR too slow to be used on anything at scale. Please, for your sanity, don't treat this as anything other than a fun toy example. ER wants to be an an O(n^2) problem and you have to fight very hard for it not to turn into one. Most people doing this at scale are following basically the same pla…
Great advice! What is your rough guesstimate - in big O - of a general least upper bound of what you can do with ER?
Caveat: just my personal hunch.
My suspicion is O(kn), where k is both constant and rather large. This would be highly reliant on an extremely good blocking algorithm. Maybe trending towards O(nlogn)? I don't know. It's really tough.
The blocking algorithm for this hypothetical solution would most likely be an approximate hashing algorithm sort of resembling a bloom filter. The input data would have to be amenable to hashing, like a single string field. Add multiple fields and shit just got complicated fast. Look up q-gram blocking if you want to read a sort of simple example of a blocking algorithm like this.
Re: Entity Resolution: The most common data science challenge
#10A good starting point for Entity Resolution/Deduplication is the Python Dedupe project [1, 2] and the PhD thesis on whose work it is based [3]
[1] https://github.com/dedupeio/dedupe
[3] http://www.cs.utexas.edu/~ml/papers/marlin-dissertation-06.p...