Monthly Archives: August 2014

Address Parser and the Sexiest Profession of the 21st Century

Posted on by
Reply

Address Parsing is an issue of crucial importance to record linkage of people, and thus central to our business. Last Tuesday, during my boss’s presentation at the Seattle Marketing and Analytics Group meetup, a couple of data science practitioners from the retailers’ side asked us the question. Yes. We use our own address parsing software, and we have no choice but do it ourselves.

On one hand, we just have too many different data sources that we want to link and aggregate. Each has their schema and their own propensity of making errors in their addresses. We have to have something specific for each data source instead of just use the standard government issued or open source GIS address parsers to clean all of them up. On the other hand, to process the 20 plus billion records we have, pinging Google Map or Bing Map to parse the addresses is simply out of the question. Even if we can make it possible, they are still not good enough. When an ill-parsed address leads a Google Map user to the opposite side of the city, all he or she can do is giving a tirade among his family/friends on how bad Google Map is. It does not really matter to Google because nobody can really quit them. But it is not the same with us, when we get an address wrong, the angry customer will actually be on the other side of phone taking it out on our poor customer representatives, and demanding a full refund if not compensations.

But there is reason why it seems that Google Map and Bing Map have been so “deaf” to the cries of their users for improving their address accuracy. It is not they are too arrogant, address parsing is just such a hard problem. Over the years, many brilliant papers have been published in the area, promising great performance improvements. But really making these great algorithms working at an industrial scale and at a customer acceptable accuracy is not a simple task. You need to cover so many edge cases, collect so much training data and have to do so much tweaking, you have to have researchers and scientists who are not only experts at the algorithms, understanding them thoroughly and knowing how to adapt them to the problem at their hands, improving them to meet their needs, but also have the patience and dedication of sitting there through long hours of sifting through the data, cleaning them up, patching up all the edge cases, to make them work.

Unfortunately, these days, some data science practitioners understand the basics of these algorithms, use them off the shelve as if they are a black box, but never have the patience to make them really work. If one algorithm does not work, they will try another one, and if none of the off the shelves algorithms work, they will blame it on the academic and move on. They are more keen on building systems, than in actually making one simple system working elegantly and smoothly.  Some even complain that the hard work of making a machine learning based system work is just too menial and below them–they will not waste their life on them, leaving the real stake-holders (the business side), shaking their collective head, say, ‘so this is all machine learning/datamining/data science can do? It is not any better than the heuristic rule-based system that we are using.’

When I was a fresh graduate student, I asked my Ph.D. thesis adviser, Dr Thomas G Dietterich, the founding president of the International Society of Machine Learning, the secret of getting the great algorithms we were learning and developing work for real world problems. I still remember that he paused for a moment and told me, ‘the most important thing is to become a real domain expert, spending hours and hours designing and engineering your features, cleaning up your data, and tweaking the parameters. If it still does not work, write your own algorithms and beat them as hard as possible till they finally fit the shape of your problems.’

This is how we were able to build a successful record linkage system with both a high precision and recall. When I told some of my colleagues that our models usually have precision of 99.6% and recall typically in the range of 80% to 92%, most of them could not believe me. I did not lie. Nothing we used was truly magically. The only miraculous thing we did was hours and hours of feature engineering, training data cleaning, and parameter tuning.

They say that Data Science is the sexiest profession of the 21st century, but as we all know, being sexy is not that easy. It takes a lot of work, hours and hours of grueling work in the gym, all the cardio, weight lifting, squats, contouring… You have to pay meticulous details to nutrition, even to the point of being tyrannical to yourself. For us girls, we also have to spend hours and hours working on our skin, hair, make-up, clothes, …Same for the sexiest profession of the 21st century, beneath that glory outlook is hours and hours of grueling meticulous work.

Scaling For Big Graph

Posted on by
Reply

Scaling up for big data is hard, scaling up a big graph based clustering system is even harder, especially if you are not Google or Facebook, and don’t have an unlimited budget.

We learned the lesson the hardest way. At Inome, one of our biggest challenges is the clustering of 20+ billion records into about 250 million people profiles. We need to put the 20 billion records into a similarity graph and partition them into clusters by the values from carefully tuned and engineered machine learning based similarity models. It does not take much to describe the approach, we just have a couple of papers on it, but to build a system that implements it is no simple task.

We started from making our system work for a couple of billions of records, and scaling up a couple of billions or hundreds of millions a time, all the way to 20 billion. It has been a uphill struggle, how to optimize, best parallelize each step of the pipeline, especially the steps iterating over a large part of the graph, or synchronizing over the entire graph. Every step in the scaling up process was pure pain, sometimes we had to completely rewrite key algorithms and develop new ways to implement and improve them. That is not all. The more you parallelize the algorithm, the more stages your pipeline contains, and making the entire pipeline running robust and smoothly becomes all the more important. To do it, more stages of validation, normalization and quantative analysis on the quality of data input and output of each stage have to be added, before we finally have a robust and solid system.

It is only natural that we feel a lot of pride in pulling all of this through–the kind of joy NASA scientists and engineers experience when they watch rockets rolling off a new production line, rockets that are powerful enough to send payloads to Mars. You can imagine the shock we feel when we have to scale our system down to meet some new customer needs. We never realize how much we have done until we have to link only a couple of thousand records to our corpus. Guess you never fully appreciate how sophisticated your rocket production pipeline is unless you try to use it to make a firecracker for your daughter on the Independence day. :-)

But unlike making a firecracker, we still have 250 million profiles on the other side of the bipartite graph. To make the new scale-downed pipeline robust and working well for small data (to us, it means anywhere between thousands to tens of millions), there are still a lot of optimization to go. We have imagined during our days of struggling to scale up, that one day, after we finally make it, we might have to scale it all the way back and re-adapt ourselves to the world of “small data”.

Is MTurk for problems requiring years of training or special expertise?

Posted on by
Reply

We are trying to use Mechanical Turk to solve a problem that is different from most of the MTurk projects out there. First, to accomplish the task the Turker needs to have some ‘expertise’ in our subject domain. Second, we are trying to build a Machine Learning based model with very high precision requirement out of the data we collected from the Turkers. Instead of trying to find the model with the best precision/recall trade-off, we require our model to have very high precision (99.6%) and the best recall we can get for that precision level.

We are not sure yet whether MTurk is the way to go to get quality training/evaluation data. But we have been using it for almost two years. We spent a lot of money and efforts on collecting, cleaning and maintaining. So far it is somewhat meeting our expectation.

Here are some of the points:

1. Training and maintaining a population of Turkers with high accuracy:

We maintain continuous communications with the Turkers on TurkerNation. Whenever we set up a batch of HITs on MTurks, our researchers/analysts will monitor our TurkerNation board/thread to see if the Turkers have any questions about the HITs. If they do, we will try to answer the questions right away.

We salt our HITs with examples from our golden set, and use them to evaluate the Turkers.

We offer 100% bonus to Turkers who have accuracy of 100%. Most of the time none of the Turkers got 100% of the salted HITs correct. If this is the case, we always bonus the Turker with the highest accuracy by 100%. The rest of the Turkers will receive bonus based on their accuracy level. Usually we only bonus Turkers with accuracy higher than 80%, but if the batch is too hard, we may just bonus the top 20% or 30% of Turkers regardless of their precision.

After we evaluate each batch, we usually post messages about the accuracy information of each Turker and the amount of bonus they get on TurkerNation after each batch of HITs. The Turkers who read those posts can get an estimate of how well they perform compared to other Turkers.

To train the Turkers, we build and maintain a very detailed guideline page which takes some time to read, and edit it when our task changes or feedback from the Turkers suggests that we need to change and clarify our guideline. After a while, our guideline has become so long and it is very difficult for the Turkers to reference. To make it easier for the Turkers, in addition to the guideline pages, we create a set of example HITs with the correct answer and explanation. We add a link in the instruction section on our HITs, so the Turkers can go through them for reference very conveniently.

To further improve the accuracy of our Turkers, we expose a very powerful internal feature that we used in the model to the Turkers to help them make decisions for the ambiguous cases. This internal feature/score is so powerful, that some of the Turkers treat it as if it is the Golden Oracle, and are afraid of making decisions that are contradictory to the score. The pros: We did see a big increase in the accuracy of our Turkers. The cons: Sometimes the Turker just got lazy and made decisions by looking at that feature only. But most of the cases, our Turkers take our HITs very seriously and do take time working on the HITs very carefully.

2. A multiple tier labeling system

The first tier are the Turkers. Inside this tier we use a qualification score to separate them into Turkers and Super Turkers. Some of our jobs are only available to the Super Turkers. Usually we send out three types of jobs: a. Qualification jobs–these are offered to all Turkers who has an approval rate over 98%, and have done more than 500 HITs. These batches usually go parallel with our HITs for super Turkers. We use them to recruit more Super Turkers who do well on our HITs. These HITs are usually priced at 2 cent each. b. Super Turkers–these are the Turkers with qualification score over 8.  A majority of our HITs go to these Turkers. They pay 50% better than the ones for the general public at 3 cents. c. Super Super Turkers–Super Turkers who have done really well with us and with autoqual score over 25. We send some of our arbitration batches (batches of HITs that the super Turkers disagree on) to our Super Super Turkers, and pay them 5 cents for each HITs. These are only the base pay–in addition, there are always accuracy based bonuses.

The Super Turkers autoqual scores are adjusted based on their accuracy–the good ones will get an increase of 1 or 2 or even 3, and the bad ones will get an decrease of -1 or  -2. If their performance is really bad, we just disqualify them.

The second tier are our internal Data Raters. We hire people who usually have at least a bachelor degree to do the job on an hourly basis. They can work from home at any hours that are convenient to them and as many hours as they want. We bring them in for training when we see some big problems with their labeling results. The Data Raters work on two types of HITs: Hits the Super Turkers disagree on. We also put on MTurk the False Positives and False Negatives of our models and have the Data Raters work on them.

The third tier are our researchers, data analysts and QA team. These people go through the final false positives and false negatives together–usually many of these are very ambiguous cases–and discuss what the labels should be from their own perspectives. The things we learn from these sessions will become our new Label Guidelines and training examples.