Blog_Header-4
Blog_Banner_v3

How Machine Learning Will Affect Your Next Vacation

Posted by Sarah Anderson on Wed, Dec 04, 2013

vacation suitcaseYou may not be paying much attention to data science, but it’s paying attention to you — and will deliver personalized search results in due time.

For those of us who prefer to stay on the shopping side of recommender engines, how online retailers seem to know which hotels we’ll book, what flights we’ll take, or what brand of pots and pans we’ll buy next is simply math, or for those of us with a little more knowledge, algorithms. For most everyone else, it pretty much falls under something more akin to science so advanced it might as well be magic. Of course, for the machine learning data scientists who create these recommender engines, all engines are different, complex — and definitely not magic.

One type of recommender engine most consumers are relatively familiar with (whether they realize it is or not) is the type developed with the purpose of figuring out your next vacation. Expedia, the world’s largest online travel agency, just wrapped up a competition for data scientists to build a recommender engine that best matches hotels with customers. Our very own machine learning data scientists, Michael Jahrer and Andreas Toescher, took home first place in this global competition, which had over 300 teams and more than 3,500 entries. The pair has won similar competitions before, including the well-known Netflix Prize — twice. But they say this competition was different than Netflix, and indeed, it was. So what makes a good recommender engine? What sorts of parameters come into play? And most important, how might this affect your next vacation?

When you go to a travel site like Expedia to book a hotel, you give it some very basic information just to see what hotels are available (city, check-in and -out dates, and how many people will be staying with you). And the next page is where would-be vacationers fall down the rabbit hole. For example, we did a search for hotels in Manhattan for four days and were given 363 results. So from here, you can filter by rating and price (5 options each), neighborhood (18 options), accommodation type (5 options), preferences (16 options), and accessibility (7 options). When the end user clicks on these filters, the results list changes. It’s being narrowed down according to the user’s priorities.

But how does Expedia know which priorities are deal breakers and which ones are just niceties? That’s where machine learning comes in. Every time a user goes to a site like this and clicks around, data is being recorded. If you click “pets allowed” every single time you visit a site like this, that probably indicates that you never travel without your pet, and therefore, the model assigns that feature a higher value than, say, free newspaper. For the guy who can’t even get dressed without seeing that day’s headlines, however, free newspaper may get the higher value.

So most sites use each search to take this information in and quickly return a new list with hotels that include all the features you wanted. But how does the site know which hotel to put first? (Hint: That’s a trick question. If they knew that, they wouldn’t have needed the competition.) The one listed first is most likely to be clicked on and ultimately purchased. And seeing as how we humans don’t have long attention spans, travel agencies only have a few seconds or a couple of clicks before the user decides the responses aren’t up to par and leaves the site altogether. So figuring out which one should come first is the question our scientists and hundreds of others needed to answer.

Our scientists looked at all of the preferred attributes, as well as users’ click and purchase history to figure out which hotels should be presented first to each user depending on their past click and purchase history. They started with the data set, which was partitioned into queries. The scientists had about 400,000 queries, and each query consisted of 30 hotel IDs that needed to be ranked. While it may sound similar to the Netflix challenge in that both involved recommender engines, the algorithms were quite different. (Warning: Here’s where things get technical.) For Netflix, SVD (singular value decomposition) and factor models gave very good results. In theory, similar models could have been applied here, but our scientists discovered that tree maps and neural networks worked better. They attribute this to the fact that they had a lot more information with this challenge than they did with the Netflix challenge, which used user IDs, item IDs, and ratings. For Expedia, they had more well-rounded information on the users and the hotels. More information equals bigger data, and in this case better results. In the end, Expedia’s solution looked very different than Netflix’s solution.

Jahrer and Toescher also attribute this difference to the error measure used for Expedia. This competition used Normalized Discounted Cumulative Gain to measure the usefulness, or “gain” of each result. In other words, it ranked each result on a scale of 0 to 1, with the highest-scoring hotel earning the first ranking. This error measure is not nearly as common as AUC, or Area Under the receiver operator Curve, which involves classifying an instance as either positive or negative. It’s safe to say that this is what most online travel agencies are using today. They answer the question, “Does this hotel meet the selected criteria of the user?” If the answer is yes, it goes on the list. If the answer is no, it doesn’t. How the answers are ranked can usually be set by the user, who is given a few options, such as price, rating, most popular, or distance from key landmark.

It’s not a bad system, but it’s not great, either. As mentioned above, we all have our deal breakers. If you have kids and they’re going to be along on the trip, chances are pretty good you’ll want a pool, even if you’re only making a one-night stop on a long road trip. If the pickings are slim, mom’s bathtub may need to take a backseat to the kids’ entertainment. These sorts of choices are subtle and nuanced, but a machine can still detect them. Even if you don’t realize it at the time, you’re inputting those subtleties every time you search for a hotel room — even if you don’t make a purchase.

So how does this affect the average consumer? The difference between the two error measures discussed here is essentially the same as saying “Here’s a list of all 363 hotels that meet your criteria” and “Here’s a list of all 363 hotels that meet your criteria, but they’re sorted according to which one you are statistically most likely to choose.” For an online travel agency, this level of science is pure gold. For a consumer, these types of results can be serious time savers.

When you plan your next trip, the search engine you use may already know that when you travel with your kids you need a pool, but when you travel for business, room service is a must, and when you travel internationally, you prefer baths over showers (probably because you don’t trust the water pressure). With machine learning science working behind the scenes of your hotel search, the recommendation engine is quickly calculating all the little nuances that make your trip better, so not only can you plan your trip faster, but you might actually have a better trip because the machine remembers things you might forget — like when you travel with your family, free breakfast is worth a lot more than just breakfast.

For more details on the Expedia Challenge, download the case study.

Download Now

 

Topics: Big Data, Machine Learning, Competitions