Text By the Bay 2015: Jeff Sukharev, Machine Translation Approach for Name Matching in Record Link
my name is jeff sukhorith and i come to you from ancestry.com the world's largest genealogy service company in this talk i'm going to talk about the problem of finding alternative name name spellings it's an important problem in name matching part of record linkage so we started working on this project a project a project while working on several problems for instance.com including uh search engine um optimization and also including um three node duplication so first a few words about ancestry and ancestry products over the years census accumulated over 60 million user-generated family trees and over 16 billion personal records so here on the left side you see typical example of a family tree where nodes represent individual people and ages represent relations on the right side you see a kind of a basic example of a scanned documents and we have multiple types of documents there could be birth certificates uh death documents death certificates um military records uh census data uh also newspapers journal and lots of other historical documents uh one popular way of interacting with nsg data is using ancestry search entity search is basically a form based search where users specify names locations dates anything they know about about you about the person they're searching for what can be actually found what could be actually found on the forum and then the result of this search the output is basically collection of relevant records found for the information that user provided unfortunately very often user doesn't exactly know what's the right spelling of the person they're searching for due to multiple reasons maybe they just don't know the right spelling or maybe the spelling has changed or maybe the documents contain errors or they're also ocr errors as well so the idea is that you it's either user has to be really aware of all possible variations of the spelling and some users do like professional genealogists uh but most users do not know this information so the idea is to do it automatically so we would actually help users to find the credible list of alternative name spellings and that way we'll actually improve search and improve the recall of relevant documents so what are the typical example of of kind of alternative spellings of the different last names for instance and we're looking here at the western western last names so if you see a few examples for instance mcdonald can be spelled with an mic it can also be spelled as an mc clark can be spelled as a clark without e at the end can be spelled with e at the end there are you see other examples here so uh clearly it seems to seem to us when we started this project that there must be a good way of finding kind of the list of alternative name spellings there are existing methods out there but most of those methods are rule-based for instance there are phonetic methods that return basically a list of similar sounding last names there are also kind of edit distance or similarity metrics so we wanted to see if we can actually use those methods and see if we can actually generate our own method that would be ideally ideal for our particular data and then stick has lots of data especially lots of name data lots of geographical location data so our goals were three-fold first we're going to produce a data-driven method that would improve our our recall and also be precise enough for our purposes we also wanted to generate a training data set that we could want to share with the wider community so anybody could actually use our training set and generate their own models and the third goal was to compare our method using kind of rigorously compare it with the existing methods out there so we were motivated by a collaborative filtering something similar to what amazon or netflix does when they recommend your movies or books our actions of our users actually suggested us labels so our users when they interact with our website they search for relevant relevant documents um for a particular person on their family tree then they attach those documents to the fam to the to the actual relevant node so they kind of kind of become like a they actually bring us the information and bring us the linkages between the data also users use search and they reformulate the searches we can capture all this information in our logs then the idea is when we actually collect the data with how we can use this data we can try to divide the data into negative and positive clauses and positive clauses may be relatively simple to identify but negative clause is more difficult in this case how do you know for sure that two names may not necessarily be spellings on one another maybe the user knows better so at the end we decided to use the parallel corporate method where we basically use all the data and we're not going to divide it into classes so the two processes that we really identified as the sources of our data sets where what we call the records data set and search data set so records like our data set is basically like already mentioned it's the it's this linkage between the tree node of some person and a related document connected to that node so you can find the name information in a tree node that's how users specify the name and in the record that's the official record you can also find the same information as well very often this information is going to be identical but often enough it's not identical often enough it's actually there are significant differences and that will give us training data uh search dataset is basically reformulation data again we basically captured them from uh user searches we captured it in time we basically looked at particular user at certain certain time found what he was searching for and then looked at the next next searches of the same user in a certain period of time then they captured this information and created the pairs from this as well so now we have two independent data sources and we wanted to build models using this using those data using this data here on the right side you see the image of basically some example of different distributions on the left side of our pairs and the right side of our pairs while you would think that in the search reformulation distribution may be similar uh in our records data set distribution is significantly different because uh in the tree notes it's typically the last name spelling is uh by modern users how they actually think the modern spelling is while in the records the distribution is different it's skewed to historical spellings of last names because our data contained errors it was really critical for us to set up a pipeline uh shown here for cleaning the data set the two important steps in this pipeline are current filter and jacquard coefficient in concurrence filter we basically select the top co-current pairs to be left for training for training sets and jacquard coefficient we're going to discriminate against um high frequency individual names for instance if there'll be a pair of johnson smith we wanted to just to kind of remove those pairs as well even so individual johnson and smith would be very high frequent names we wanted to discriminate against those pairs so now that we have a kind of clean enough training set we decided to on the method we're going to use to train the model we looked at machine translation and we've looked at our problem as a kind of a translation problem where on the left side you'll have a one language which is consists of names only on the other side you have another language which is basically different distribution of names only and the idea was to basically use machine translation method and come calculate kind of a alignment rules that would show us the basic rules that would that would be needed to apply to certain names to translate them into into other certain names uh in in our case we treated uh machine translation problem a little differently so we had a certain caveat that the individual words would be actually characters and the sentences would be just the complete names here in on the top of the slide you see the basic formula from machine translation community but again slightly modified for our purposes what we wanted to find is the key maximum probabilities of target name given the source name and what it equals to is the again k maximum products of the name model and alignment model so i'll go in a few more details what they are a name model is just basically statistics described describing a target language and the way we actually implemented a model using n-gram where n-gram is just the probability of the certain letter coming after and other letters there are multiple actually open source solutions to to actually calculate the name models uh alignment rules actually what what was the point of actually training the model um so alignment rules were well computed using expectation maximization method and here i can give you like a brief simple example at the bottom where you see a typical alignment alignment rules like you see those errors from one spelling of the last name thorough good to another spelling on the same last name and you see that all you results in one letter o while the other alignment rule is 2g and h disappears and two g's become single g that's another alignment rule that was produced by by our model but they produced tons of other alignment rules now the idea was to actually when we actually got the model and we actually experimented with it we wanted to compare it with other other methods using the same common framework the methods that we selected were commonly used in our search engine and commonly use another database as well those are phonetic methods including sound decks dimitaphone nycs and couple of other methods and the string similarity meter so that's another cluster method we wanted to compare against we identified lievenstein winkler and weakler method and our math was machine translation which was implemented using modus library so what are just a few words about about other methods so so phonetic methods are basically kind of rule-based methods for um computing a certain code so all similar sounding names would actually map into a certain code and the way this code is computed actually that's how each phonetic method is different from one another for instance the most popular and very efficient method sound x which is but which is also not precise uh their code looks looks the following basically they take the first letter from the name and also compute three-digit code from the rest of the rest of characters and they remove all vowels uh and nyc is a different method and it's actually has all all character code they don't have digits this is just basic example of codes produced by different phonetic methods another class of method we compared against was similarity methods and similarity methods can be shown here using example of edit distance also called levenshtein method it's basically um it comes from from the edit distance and the idea is it's a it's a set of it's a number that represents a number of simple operations that you need in order to convert one string into another string and simple operations are basically deletion insertion or substitution this matrix just shows how the how the actual edit distance is implemented the actual similarity is being computed from the actual edit distance by this formula so you actually divide the edit distance by the length of the maximum string and then you subtract this value which is the value between zero and one from from one then you get actual similarity value so now to our standard can evaluation framework that we used we use the standard evaluation framework in the sense that we wanted to actually help some of those methods to compete with data-driven method for instance phonetic methods they could only return a binary result it's either either the last name is two last name sign the same i consider to be the same because they have the same code or or they're not considered to be similar then they don't have the same code so it's basically one or zero answer so we wanted to actually our common framework looks like this look at alignment scores produced by um produced by basically our methods it's either machine translation method uh similarity measure measure measure or phonetic method and we multiply it by language model score in language model score we compute for machine translation we also computed it for um for similarity and for phonetic methods just to be fair to those methods here our results this is this result shown using records data uh we basically show a precision recall graph where you have curves for each individual method that we looked at uh we used the ten-fold cross validation here so we trained on kind of one-tenth of data that we had and we trained on the rest and we tested them on the rest and we didn't so basically for every method we generated 10 uh 10 curves uh so here you see those 10 curves shown as kind of a confidence regions around the centroid curve so the in order for the method to be the best method it has to be closer its curve needs to be closer to the right top corner so on the right top corner here you see actually moses five gram method that's the that's the basic machine translation data driven method it's five gram because that's that's what we chose from other possibilities for our language model we tried experimenting with two gram up to six gram and five gram apparently was the best for in our precision recall the worst performing methods were phonetic methods and out of phonetic methods what we found curious that nyc's method was performed better than um than all other phonetic methods this was also important finding of this work on our data of course uh the next best methods were similarity measures but it's kind of difficult to save from from our results which of the similarity measures were the best because their confidence regions were overlapping but what's one thing is was clear that that our method was better than other methods we looked at so we got very similar conclusions from our second data set from search reformulation and that gave us more confidence because those two methods were produced by completely different processes so we used primarily moses kind of open source library for our machine translation needs we use rstlm package for just to generate a language model and we use giza plus plus package for statistical character alignment we also use the pf federal library with peter christensen from university of south australia for implementations of similarity measures and financial algorithms we also implemented some of some of them ourselves and we also use other libraries just to compare so in the conclusion our finding basically showed that on our data our machine translation data-driven method significantly outperform other methods and became deemed to be useful for our query expansion our search engine so now it's actually being incorporated into ancestry search engine and it will improve precision and recall uh nyc's phonetic method showed up to be significantly better than other phonetic methods and that's another thing we're also trying now because we use sound decks and not in other cases you know not another kind of services for the company um and we also share our data set with the community so you can find it on this url it's also in the paper we published a paper on this in icdm in 2014. that's it you have questions that's right yes this actually more applies to also geographical locations because first names there are problems let's say this cases like richard dig which it basically you can't come up with the rule here because it's really exception so we're actually thinking about this right now because we also experiment with this for first names and it's not that great because of that because we really want to capture those those things so we want to kind of change our whole idea but i think we still can use um we can still use our pairs but for instance one solution would be to just pre-compute statistically kind of using collaborative filtering and say for common first names just go to that table but then the whole benefit of this is that you don't have to have all the names in your training set here you can you can find some kind of new name completely but still use the same rules to come up with alternative spelling set with if you would just use a table that would not be the case so that's still kind of ongoing effort on what uh unfortunately our whole data set is coming and forgot to mention that most of our users actually western europe u.s canada australia new zealand so we have some data from china and we we um but not enough for us to to to try it but that's definitely gold if we have if we find the data we would love to we would love to try it but we don't have it yet but we tried on eastern european languages and that works fine that so any other questions all right thank you