A total of 2,552 players on over 2,000 teams participated in the Home Depot Product Search Relevance competition which ran on Kaggle from January to April 2016. Kagglers were challenged to predict the relevance between pairs of real customer queries and products. In this interview, the first place team describes their winning approach and how computing query centroids helped their solution overcome misspelled and ambiguous search terms.
The Basics
What was your background prior to entering this challenge?
Andreas: I have a PhD in Wireless Network Optimization using statistical and machine learning techniques. I worked for 3.5 years as Senior Data Scientist at AGT International applying machine learning in different types of problems (remote sensing, data fusion, anomaly detection) and I hold an IEEE Certificate of Appreciation for winning first place in a prestigious IEEE contest. I am currently Senior Data Scientist at Zalando SE.
Andreas on Kaggle
Alex: I have a PhD in computer science and work as data science consultant for companies in various industries. I have built models for e-commerce, smart home, smart city and manufacturing applications, but never worked on a search relevance problem.
Alex on Kaggle
Nurlan: I recently completed my PhD in biological sciences where I worked mainly with image data for drug screening and performed statistical analysis for gene function characterization. I have also experience in application of recommender system approaches for novel gene function predictions.
Nurlan on Kaggle
How did you get started competing on Kaggle?
Nurlan: The wide variety of competitions hosted on Kaggle motivated me to learn more about applications of machine learning across various industries.
Andreas: The opportunity to work with real-world datasets from various domains and also interact with a community of passionate and very smart people was a key driving factor. In terms of learning while having fun, it is hard to beat the Kaggle experience. Also, exactly because the problems are coming from the real world, there are always opportunities to apply what you learned in a different context, be it another dataset or a completely different application domain.
Alex: I was attracted by the variety of real world datasets hosted on Kaggle and the opportunity to learn new skills and meet other practitioners. I was a bit hesitant to join competitions in the beginning as I was not sure if I would be able to dedicate the time for it, but then never regretted to get started. The leaderboard, the knowledge exchange in forums and working in teams creates a very exciting and enjoyable experience, and I was often able to transfer knowledge gained on Kaggle to customer problems in my day job.
What made you decide to enter this competition?
Alex: Before Home Depot, I participated in several competitions with anonymized datasets where feature engineering was very difficult or didn’t work at all. I like the creative aspect of feature engineering and I expected a lot of potential for feature engineering in this competition. Also I saw a chance to improve my text mining skills on a very tangible dataset.
Nurlan: I had two goals in this competition: mastering state of the art methods in natural language processing and model ensembling techniques. Teaming up with experienced kagglers and kaggle community through forums provided opportunities to achieve my goals.
Andreas: Learning more about both feature engineering and ML models that are doing well in NLP was a first driver. The decent but not overwhelming amount of data gave also good opportunities for ensembling and trying to squeeze the most out of the models, something that I enjoy doing when there are no inherent time or other business constraints (as is often the case in commercial data science applications).
Let’s get technical
What preprocessing and supervised learning methods did you use?
Figure 1: Overview of our prediction pipeline - most important features and models highlighted in orange.
Preprocessing and Feature Engineering
Our preprocessing and feature engineering approach can be grouped into five categories: keyword match, semantic match, entity recognition, vocabulary expansion and aggregate features.
Keyword Match
In keyword match we counted the number of matching terms between search term and different sections of product information and also stored the matching term position. To overcome the misspellings we used fuzzy match where we counted the character n-grams matches instead of complete term. We also computed tf-idf normalized scores of the matching terms to normalize for the non-specific term matches.
Semantic Match
Figure 2: Visualization of word embedding vectors trained on product descriptions and titles - related words cluster in word embedding space (2D projection using multi-dimensional scaling on cosine distance matrix, k-means clustering).
To capture the semantic similarity (e.g. shower vs bathroom) we performed matrix decomposition using latent semantic analysis (LSA) and non-negative matrix factorization (NMF). To further catch the similarities that were not captured with LSA or NMF, which were trained on Home Depot corpus, we used pre-trained word2vec and GloVe word embeddings that are trained on various external corpora. Among LSA, NMF, GloVe and word2vec, GloVe word embeddings gave the best performance. See in figure 2 how it captures similar entities.
Main Entity Extraction
The main motivation was to extract main entities being searched and being described in the queries and product titles respectively. Our primary approach was to include positional information of the matched terms but oob error analysis revealed that it was not enough. We also experimented with POS tagging but we noticed that many of the terms that represent entity attributes and specifications were also captured as nouns and there was no obvious pattern to distinguish them from the the main entity terms. Instead, we decided to extract last N terms as potential main entities after reversing the order of the terms whenever we see prepositions such as "for", "with", "in", etc., which were usually followed by entity attributes/specifications.
Vocabulary Expansion
To catch 'pet' vs 'dog' type of relationships we performed vocabulary expansion for main entities extracted from the search terms and product titles. Vocabulary expansion included synonym, hyponym and hypernym extraction from WordNet.
Aggregate Features
See “What was your most important insight into the data?” section for details.
Feature Interactions
We also performed basis expansions by including polynomial interaction terms between important features. These features also contributed further to the performance of our final model.
Supervised Learning Methods
Apart from the usual suspects like xgboost, random forest, extra trees and neural nets, we worked quite a lot with combinations of unsupervised feature transformations and generalized linear models, especially sparse random and Gaussian projections as well as Random Tree Embeddings (which did really good). On the supervised part, we tried a large number of Generalized Linear Models using the different feature transformations and different loss functions. Bayesian Ridge and Lasso with some of the transformed features did really well, the first also getting almost no hyperparameter tuning (and thus saving time). Another thing that worked really good was the regression through classification approach based on Extra Tree Classifiers. Selecting the optimal number of classes and tweaking the model to get reliable posterior probability estimates was important and took computational effort but it contributed some of the best models (just next to the very best xgboost models).
The idea was always to get models that are individually good on their own but have as little correlation as possible so that they can contribute meaningfully in the ensemble. The feature transformations, different loss functions, regression through classification, etc. all played well in this general goal.
Figure 3. Comparison of unsupervised random tree embedding and supervised classification in separating the relevant and non-relevant points (2D projections).
The two figures above are showing the effectiveness of the unsupervised Random Tree Embedding transform (upper of the two pictures). The separation visualized here is between two classes only (highly relevant points tend to be high on the left and not relevant low and towards the right) and it is mingled. But we need to consider that this is a 2D projection done in a completely unsupervised way (the classes are actually visualized on top of the data and the labels were not used for anything other than visualization). For comparison, the other image (bottom picture) visualizes the posterior estimates for the two classes derived from a supervised Extra Tree classification algorithm (again the highly relevant area is up and to the left, while the non-relevant bottom right).
How did you settle on a strong cross-validation strategy?
Alex: I think everyone joining the competition realized very early that a simple cross-validation does not properly reflect the generalization error on the test set. The amount of search terms and products only present in the test set biased the cross-validation error and lead to overfitted models. To avoid that, I tried first to generate cross-validation folds that account for both unseen search terms and products simultaneously, but I was not able to come up with a sampling strategy that meets these requirements. I finally got the idea to “ensemble” multiple sampling schemes and it turned out to work very well. We created two runs of 3-fold cross-validation with disjoint search terms among the folds, and one 3-fold cross-validation with disjoint product id sets. Taking the average error of the three runs turned out to be a very good predictor for the public and private leaderboard score.
What was your most important insight into the data?
Figure 4. Information extraction about relevance of products to the query and quantification of query ambiguity by aggregating the products retrieved for each query.
In the beginning we were measuring search term to product similarity by different means, but search terms were quite noisy (i.e. misspellings). Since most of the products retrieved are relevant, we clustered products for each query, then computed cluster centroid and used this centroid as a reference. Calculating similarity of the products to the query centroid provided powerful information (See figure above, left panel).
On top of this, some queries are ambiguous (e.g. ‘manual’ as opposed to ‘window lock’) and these ambiguous terms would be unclear for the human raters too and might lead to less relevant score. We decided to include this information as well by computing the mean similarity of the products to the query centroid for each query. Figure above (right panel) shows this relationship.
Were you surprised by any of your findings?
Andreas: One surprising finding was that the residual errors of our predictions were exhibiting a strange pattern (different behavior in the last few tens of thousands of records), that hinted towards a bias somewhere in the process. After discussing it, we thought that a plausible explanation was a change of annotators or change in the annotations policy. We decided to model this by adding a binary variable (instead of including the id directly) and it proved a good bet.
Alex: I was surprised by the excellent performance of word embedding features compared to classical TF-IDF approach, even though the word embeddings were trained on a rather small corpus.
Which tools did you use?
Andreas: We used a Python tool chain, with all of the standard tools of the trade (scikit-learn, nltk, pandas, numpy, scipy, xgboost, keras, hyperopt, matplotlib). Sometimes R was also used for visualization (ggplot).
How did you spend your time on this competition?
Alex: We spent most of the time on preprocessing and feature engineering. To tune the models and the ensemble, we reused code from previous competitions to automate hyperparameter optimization, cross-validation and stacking, so we could run them overnight and while we were at work.
What was the run time for both training and prediction of your winning solution?
Alex: To be honest, recalculating the full feature extraction and model training pipeline takes several days, although our best features and models would finish after a few hours. We often tried to remove models and features to reduce the complexity of our solution, but it almost always increased the prediction error. So we kept adding new models and features incrementally over several weeks, leading to more than 20 independent feature sets and about 300 models in the first ensemble layer.
Words of wisdom
What have you taken away from this competition?
Alex: Never give up and keep working out new ideas, even if you are falling behind on the public leaderboard. Never throw away weak features or models, they could still contribute to your final ensemble.
Nurlan: Building a cross-validation scheme that's consistent with leaderboard score and power of ensembling.
Andreas: Persistency and application of best practices on all aspects (cross-validation, feature engineering, model ensembling, etc.) is what makes it work. You cannot afford to skip any part if you want to compete seriously in Kaggle these days.
Do you have any advice for those just getting started in data science?
Alex: Data science is a huge field - focus on a small area first and approach it through hands-on experimentation and curiosity. For machine learning, pick a simple toy dataset and an algorithm, automate the cross validation, visualize decision boundaries and try get a feeling for the hyperparameters. Have fun! Once you feel comfortable, study the underlying mechanisms and theories and expand your experiments to more techniques.
Nurlan: This was my first competition and in the beginning I was competing alone. The problem of unstable local CV score demotivated me a bit as I couldn't tell how much my new approach helped until I made a submission. Once I joined the team, I learnt great deal from Alexander and Andreas. So get into a team with experienced Kagglers.
Andreas: I really recommend participating in Kaggle contests even for experienced data scientists. There is a ton of things to learn and doing it while playing is fun! Even if in the real world you will not get to use an ensemble of hundreds of models (well most of the time at least), learning a neat trick on feature transformations, getting to play with different models in various datasets and interacting with the community is always worth it. Then you can pick a paper or ML book and understand better why that algorithm worked or did not work so well for a given dataset and perhaps how to tweak it in a situation you are facing.
Teamwork
How did your team form?
Alex: Andreas and me are former colleagues and after we left the company we always planned to team up once for a competition. I met Nurlan at a Predictive Analytics meet-up in Frankfurt and invited him to join the team.
How did your team work together?
Alex: We settled on a common framework for the machine learning part at the very beginning and synchronized changes in the machine learning code and in hyper parameter configuration using a git repository. Nurlan and me had independent feature extraction pipelines, both producing serialized pandas dataframes. We shared those and the oob predictions using cloud storage services. Nurlan produced several new feature sets per week and kept Andreas and me very busy tuning and training models for them. We communicated mostly via group chat in Skype, only had two voice calls during the whole competition.
How did competing on a team help you succeed?
Andreas: We combined our different backgrounds and thus were able to cover a lot of alternatives fast. Additionally, in this contest having a lot of alternate ways of doing things like pre-processing, feature engineering, feature transformations, etc. was quite important in increasing the richness of the models that we could add in our stacking ensemble.
Just for fun
If you could run a Kaggle competition, what problem would you want to pose to other Kagglers?
Alex: If I had access to a suitable dataset, I would run a competition on predictive maintenance to predict remaining useful lifetime of physical components. Also I would love to work on a competition where reinforcement learning can be applied.
The Team
Dr. Andreas Merentitis received B.Sc., M.Sc., and Ph.D. degrees from the Department of Informatics and Telecommunications, National Kapodistrian University of Athens (NKUA) in 2003, 2005, and 2010 respectively. Between 2011-2015 he was Senior Data Scientist at AGT International. Since 2015 he works as Senior Data Scientist at Zalando SE. He has more than 30 publications in machine learning, distributed systems, and remote sensing, including publications in flagship conferences and journals. He was awarded an IEEE Certificate of Appreciation as a core member of the team that won the first place in the “Best Classification Challenge” of the 2013 IEEE GRSS Data Fusion Contest. He has a master ranking in Kaggle.
Alexander Bauer is a data science consultant with 10 years of experience in statistical analysis and machine learning. He holds a degree in electrical engineering and a PhD in computer science.
Nurlanbek Duishoev received his BSc and PhD degrees in biological sciences from Middle East Technical and from Heidelberg University respectively. His research focused on drug screenings and biological image data analysis. He later moved on to apply recommender system approaches for gene function prediction. The wealth of data being generated in the biomedical field, like in many other industries, motivated him to master state-of-the-art data science techniques via various MOOCs and participate in Kaggle contests.