Hi, everyone. In this video,
I will tell you how I and my teammates,
Stanislav Smirnov solved Kaggle Expedia hotel recommendations competition.
Personally, one of my favorites,
probably among top five most interesting competitions I've ever participated in.
I'll state the problem now.
So, if you came here right after Data Leaks lesson,
it should already be familiar to you.
Anyway, in that competition,
we worked with lots of customer behavior.
These include what customers searched for,
how they interacted with search results, clicks or books,
and whether or not the search result was a travel package,
and Expedia was interested in predicting which hotel group a user is going to book.
Important thing here is prediction target the hotel group.
In other words, characteristics of actual hotel, remember it.
As it turned out, this competition had a very
non-trivial and extremely hard to exploit data leak.
From the first glance,
data leak was pretty straightforward.
We had a destination distance among the feature.
It's a distance from user city to an actual hotel he clicked on booked.
And, as I said earlier,
our prediction target is a characteristic of an actual hotel.
Furthermore, destination distance was
very precise so unique user city and destination distance pairs
corresponded to unique hotels.
Putting two and two together,
we can treat user city and destination distance pair as a proxy to our target.
When in this set, we encountered such pair already present in train set,
we could simply take a label from there as our prediction.
It worked nearly perfect for the pairs present in both train and test.
However, nearly half of test set consisted from new pairs without a match from train set.
This way we had to go deeper.
But, how exactly can we improve our solution?
Well, there are two different ways.
First, one is to create current features on
corteges similar to user city and destination distance pair.
For example, like how many hotels of which group there are for user city,
hotel country, hotel city triplet.
Then, we could train some machine learning model on such features.
Another way is to somehow find more matches.
For that purpose, we need to find true coordinates of users cities and hotel cities.
From that, to guess it was destination distance feature,
it was possible to find good approximation for the coordinates of actual hotels.
Let's find out how to do it.
First of all, we need to understand how to calculate the distance.
Here, we work with geographical coordinates so the distances are geodesic.
It's done via Haversine formula,
not a pleasant one.
Now, suppose that we know true coordinates of
three points and distances from fourth point with unknown coordinates to each of them,
if you write down a system of three equations,
one for each distance,
we can unambiguously solve it and get true coordinates for the fourth point.
Now, we have four points with known coordinates.
I think you get the idea.
So, at first, by hook or by crook,
we reverse engineer true coordinate of three big cities.
After that, we can iteratively find coordinates of more and more cities.
But as you can see from the picture,
some cities ended up in oceans.
It means that our algorithm is not very precise.
A rounding error accumulates after every iteration and everything starts to fall apart.
We get some different method and indeed we can do better.
Just compare this picture with the previous one.
It's obviously much more accurate.
Remember how in iterative method we solved a system of
three equations to unambiguously find coordinates or fourth unknown point.
But why limit ourselves with three equations?
Let's create a giant system of equations from
all known distances with true coordinates being done on variables.
We end up with literally hundreds or thousands of equations and tens of thousands
of unknown variables.
Good thing it's very sparse.
We can apply special methods from SciPy to efficiently solve such a system.
In the end, after solving that system of equations,
we end up with a very precise coordinates for both hotel cities and user cities.
But as you remember,
we're predicting a type of a hotel.
Using city coordinates and destination distance,
it's possible to find an approximation of true coordinates of an actual hotel.
When we fix user city and draw a circumference
around it with the radius of destination distance,
it's obvious that true hotel location must be somewhere on that circumference.
Now, let's fix some hotel city and draw such circumferences from
all users cities to
that fixed hotel cities and draw them for every given destination distance.
After doing so, we end up with pictures like the ones on the slide.
A city contains a limited number of hotels so the intuition here is that hotels
actually are on the intersection points
and the more circumferences intersect in such point,
the higher the probability of a hotel being in that point.
As you can see, the pictures are beautiful but pretty messy.
It's impossible to operate in terms of singular points.
However, there are explicit clusters of points and this information can be of use.
We can do some kind of integration.
For every city, let's create a grid around its center.
Something like 10 kilometers times 10 kilometers with step size of 100 meters.
Now, using training data,
for every cell in the grid,
we can count how many hotels of which type are present there.
If a circumference goes through a cell,
we give plus one to the hotel type corresponding to that circumference.
During inference, we also draw a circumference based on destination distance feature.
We see from what degree its cells it went through and use information
from those cells to create features like a sum of all counters,
average of all counters,
maximum of all counters and so on.
Great. We have covered the part of feature engineering.
Note that all the features directly used target label.
We cannot use them as is in training.
We should generate them in out-of-fold fashion for train data.
So we had training data for years 2013 and 2014.
To generate features for year 2014,
we used labelled data from year 2013 and vice versa,
used the year 2014 to generate features for the year 2013.
For the test features,
which was from year 2015,
we naturally used all training data.
In the end, we calculated a lot of features and serve them into Xgboost model.
After 16 hours of training for the course,
we got our results.
We ended up on third position on public leader-boards and forth on private.
We did good, but we still did not fully exploit data leakage.
If you check the leaderboard,
you'll notice the difference in scores between first place and the rest.
Under speculation, the winner did extraordinary.
Although, in general, his methods were very similar to ours.
He was able to extract way more signal.
Finally, I hope you enjoyed my story.
As you can see, sometimes working with
data leakage could be very interesting and challenging.
You may develop some unusual skills and broaden your horizons.
Thank you for your attention.