Weekly project update: date parsing, candidate generation, and a string-sort bug
A weekly status email Alyssa was sending out to collaborators on a CRM-with-machine-learning project: the system extracted facts from text, stored them in a Neo4j graph database, and used ML to reconcile records that referred to the same person. This week’s update covers improvements to the date parser, a broader candidate-generation strategy for record matching, and the kind of string-vs-integer sort bug that catches everyone at least once.
This week, I made a bunch of improvements to the UI, and to several of the machine learning systems. Unfortunately, these still haven’t been uploaded to the public-facing server; the new code isn’t compatible with the old ML models, and not all of the new models have been trained yet (there are a bunch of new features, so I’m making new training data sets with them included). Sorry about that. But I’ll try to walk through some of what I’ve done, and why I think it’ll be useful.
First, while there are many types of information you can extract from text, one type that’s found in almost everything is dates and times. Dates come in a huge number of formats — “January 23rd, 2016” is the same as “1/23/2016”, which is the same as “23-01-2016”, which is the same as “this Saturday” (if, at the moment, it’s the week before the 23rd). Fortunately, the date parser is pretty clever — not only does it handle all of these, but it makes inferences based on what the date and time is right now. For example, if I write “let’s meet tomorrow, at 8 PM”, the parser will automatically infer that (right now) tomorrow is Monday, August 22nd, so the meeting goes on the calendar at 8/22/2016, 8:00. But, the inference is so aggressive that the machine learning algorithm downstream can’t tell how precise the original date was. For example, if I write “next year”, I’m probably talking about a very broad range of time. However, both “next year” and “August 21st, 2017” will get parsed to the same result (since the current date is August 21st, 2016, “August 21st” is interpolated into “next year”). Of course, that creates problems for reconciliation, as well as things like weighing how important different events are. So I went into the parser’s source code, and figured out the (undocumented) functions that returned which parts of each date had been extrapolated; these date flags are now some of the new machine learning features. (In turn, these flags let me create a new “Agenda” tab — listing details of future events in chronological order — without it being full of junk. In the development version, I’ve now set this as the default homepage.)
Second, I managed to make the candidate generation system much broader, without making it impractically inefficient. Candidate generation is the first step in reconciliation — if there’s a pool of, say, 10,000 person names, I want to know which pairs of names might possibly be the same guy, so I can feed those pairs into the machine learning system. An easy way of doing candidate generation is writing queries like this: match (n:person)-[:date-of-birth]->(d)<-[:date-of-birth]-(m:person) return n, m which returns all pairs of people with the same date of birth. But of course, lots of dates and so on aren’t exact, so this approach misses many possible pairs. What you’d like to do is walk down the list of birthdays (or names, or locations, etc.), in sorted order, keep a “sliding window” of all the elements within a certain range of each other, and flag those as possible matches. Unfortunately, I don’t think this is possible inside neo4j queries. But since reconciliation is now done continuously, only a few items will ever be non-reconciled at a time. So I split the search up into a two-part neo4j query: first, find the birthday (or whatever parameter) of all people who haven’t yet been reconciled; second, search the neo4j index for a range around each birthday, and flag any possible matches. This requires a separate lookup for each person, but since each index range lookup is only log(N), it’s still acceptably fast.
And of course, there’s been the usual assortment of bug fixes, UI tweaks, CSS improvements, and so on. (Maybe an experienced front-end dev would disagree, but I still think CSS is badly designed — half the time I’ll think something like “oh, this div needs to be shifted down”, so I’ll duly write “div#foobar { margin-top: 20 px; }”, and the browser then just ignores this and doesn’t tell you why.) Just as one example of the kinds of bugs I’ve found, the frontend Javascript has to retrieve certain facts about each person in the CRM — their name, their email address, where they live, and so on. These results are grouped into rows, with one row for each type of fact, and the rows are numbered and sorted so they appear in a pre-defined order. In testing, this worked great. However, when I added some more rows, it broke. The reason turned out to be that the row numbers were returned from the database as strings, not as integers. If you have this set of strings, one string for each row: “4” “2” “8” “1” “3” “7” “5” “6” sorting the rows returns: “1” “2” “3” “4” “5” “6” “7” “8” which is perfectly fine. But if there are eleven rows: “9” “4” “2” “11” “8” “1” “3” “10” “7” “5” “6” then string (alphabetic) sort stops being the same thing as integer sort: “1” “10” “11” “2” “3” “4” “5” “6” “7” “8” “9” and then everything breaks. Fortunately, it’s easy to fix once you know what’s going on.