Is choice of machine learning algorithm a secondary issue?

Question

Currently I’m attending the great "How to Win a Data Science Competition" course on Coursera. At one point it’s authors claim that given their experience, the actual choice of machine learning algorithm^† and parameter tuning is far less important then feature engineering. On one hand this seems to intuitively have much sense, on another, it seems to contradict the “no free lunch” theorem. Do you know any references that more rigorously deal with this topic?

^{† Notice that they implicitly seem to consider here only the high performing algorithms like XGBoost.}

Answer 1

You want citations for the claims, but I think this advice, while useful, stems from this context specifically.

The fact that these methods work so well on Kaggle and other competitions has to do with the type of datasets in those competitions. Often, especially in elementary competitions, data consists of many examples, with heterogeneous data types (categorical, continuous, missing), that are all mildly predictive, and there are interaction effects to leverage. Housing pricing competitions are a typical example of that. In such cases tree based ensembles like XGBoost and Random Forests are extremely effective and practical. They are flexible enough to learn interactions and nonlinearities, don't overfit too much if done correctly, and can deal naturally with all kinds of data.

Both in more advanced competitions and in practice, with other types of data (images, text, or just not a lot of data), and other problem settings (forecasting, recommendation systems), XGBoost will typically not be the best solution, or at most a part of the approach. Not to say that there are also many problems in practice where XGBoost is just the best approach in terms of classification or regression performance.

On textual data, or on images, tree-based methods are known to not work so well. Timeseries data is also a really different beast. An interesting example on Kaggle I think is for example the chess rating competition, you can find the winning methods here: https://www.kaggle.com/c/ChessRatings2/discussion/568.

Answer 2

Isn't the NFL concerned with algorithms which are data-independent? Feature engineering is completely data-dependent, because it's not a rigorous, well-defined algorithm, expecially in the sense meant by Kagglers. For different data sets they choose different features based on expertise, Intuition and a lot of hand-waving. It's not like they use a principled, well-defined a priori approach. In other words, they don't always use the same feature engineering algorithm for different competitions.

Answer 3

Thank you for the interesting question. I think the question will be hard to conclusively answer without a more rigorous definition of feature engineering which seems hard to give.

I don't think there is any tension with no free lunch, since I think that feature engineering involves changing the optimisation problem. There is a version of no free lunch (equivalent to the original theorem) which states the following:

Theorem (Radcliffe and Surry, 1995) Consider functions $f,g$ lying in the set of all functions between finite sets $X$ and $Y$. Let $V_m(A, f)$ denote the length $m$ performance vector generated by $A$ and $f$. For any two algorithms A and B, and for any function $f$, there exists a function $g$ such that $V(A, f) = V(B,g)$.

I think this has an interesting interpretation in light of your question. If you're willing to model feature engineering as invertible transformations of your objective function $f$, then there is a sequence permutations which takes $f$ to $g$, and algorithm $B$ does just as well as $A$. So in this sense, it would seem to confirm the folklore that the algorithm is less important than the problem formulation. My notation is taken from (Schumacher et al. 2001) which compares several version of no free lunch.

Radcliffe, Nicholas J., and Patrick D. Surry. "Fundamental limitations on search algorithms: Evolutionary computing in perspective." Computer Science Today. Springer, Berlin, Heidelberg, 1995. 275-291.

Schumacher, Chris, Michael D. Vose, and L. Darrell Whitley. "The no free lunch and problem description length." Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. Morgan Kaufmann Publishers Inc., 2001.