Transforming training data for machine learning algorithms

Question

If you want to make good predictions with machine learning (supervised learning in particular), you need a good training set. And relevant predictors in your feature set can be overshadowed by irrelevant training data. Validation can help you to figure out what training data is good - you can then remove irrelevant inputs. But what if "irrelevant" data contains something useful, but it just isn't obvious?

I have an exercise schedule, and you can predict what kind of exercise - if any - I'll have for a given day based on the day of the week and my location. The same predictability is true for my friend - and just about anyone who exercises regularly. If I throw my friend's position and day of the week data into my prediction algorithm, then I may over fit because a) day of the week would be repeated, and b) my friend's position is not linearly correlated to my schedule, so it could be mistaken for irrelevant noise. Simply dumping his training set into my training set without any thought is probably bad.

However, if my friend and I are in the same location for a given day, then we are very likely to exercise together, and I follow his schedule when we exercise together. It doesn't matter if my friend is across the city or across the world, his position only becomes strongly correlated when he is very close to me. So there is something "hidden" in my friend's seemingly irrelevant position data that might be missed.

The general problem is, given a set of predictors \begin{align} P= \{{x_1,x_2,x_3,...}\} \end{align} for some data set \begin{align} P={\{y_i,x_{1i},x_{2i},x_{3i},...\}}_{i=1}^n \end{align} we want to predict \begin{align} \{ y_i \} \end{align} We can do this by using supervised machine learning techniques, and we can also try doing this by using linear regression: \begin{align} y_i = a_1 x_{1i} + a_2 x_{2i} + a_3 x_{3i} + ... + e_i \end{align} Now, consider the set of all subsets of P \begin{align} Let \space U = \{ U_j|\space U_j \subseteq P \} \end{align} And consider the set of nonlinear functions of all subsets of P that have nonzero correlation with y (this is messy notation but its just any function of any combination of predictors such that the function has nonzero correlation with whatever it is you are predicting). \begin{align} Let \space F = \{[\{f_{1j}(U_j)\},\{f_{2j}(U_j)\},\{f_{3j}(U_j)\},...]|\space \{corr(\{f_{kj}(U_j)\} \space with \space \{y_i\})\} \cap 0 = \varnothing \} \end{align}

F is a massive set, and it contains the function for any given nonlinear machine learning technique. Furthermore, the "ultimate" nonlinear predictive function for any data set would be contained in F, and it may not be the conclusion of any machine learning technique. Clearly, the linear regression model and F share no elements by construction. However, they may share linear terms if linear term coefficients are ignored.

Every element of F can be broken up into a sum of linear and nonlinear terms (even if there are no linear terms). Now, assume that the "ultimate" nonlinear predictive function contains linear and nonlinear terms such that nonlinear terms can be approximated by low order polynomials and have nonzero correlation with y - and therefore are elements of F. I propose that the addition of these low order polynomials and linear terms can approximate the "ultimate" nonlinear predictive function reasonably well.

But that starts already knowing the "ultimate" function. Now, say we want to find this function and we keep the assumptions we made. Given a set of predictors, could we search through the set "F" by approximating low order polynomials, add these nonlinear functions to our set of predictors, then add and subtract elements to our set of predictors with an iterative technique that uses linear regression techniques to arrive at a good approximation for the "ultimate" predictive function? Are these assumptions reasonable for real world data sets? And, could this be a more general approach than machine learning techniques?

I have tried implementing code that attempts to achieve this, and I seem to be able to generate new predictor sets that yield better predictions when used in KNN compared to analogous KNN predictions from the original predictor sets. So far I have generally been able to boost KNN predictive accuracy by 3-4% for all k values of various distance measures and metrics so long as data sets have reasonable distribution. But I would like to hear some opinions about this idea, and if it is reasonable approach or mathematically sound at all.

I realize that when all possible functions in F are considered, this algorithm becomes huge and computationally very expensive. But I was thinking that maybe you should only check low order polynomials that are functions of reasonable numbers of features from your set of predictors, and only consider them for your model if they meet some performance conditions. Also, you probably don't need to double count functions optimized for the same set of inputs. So If you only considered low order polynomials of two features, you would only have to search through (n^2 - n)/2 instances, and low order polynomial optimization isn't too computationally expensive. So if you limit the number of features for the functions created in this algorithm, then it becomes much more realistic. But limiting the number of features for the functions could limit the algorithm's performance with more sophisticated data sets. There Is probably some optimal balance here.

Answer 1

I suspect you are asking about feature selection. There are many reasonable algorithms for feature selection; one could write an entire book about the subject. I suggest you start by reading up on standard methods for feature selection, and see if they will meet your needs.

See, e.g., information gain, AIC, BIC, and many others. Many methods for feature selection use a held-out validation set (or cross-validation) as part of the procedure.

That said, do you really need feature selection? Probably not. In supervised learning you often don't want to do feature selection yourself as a separate step. The simplest approach is to avoid doing any feature selection at all, and just train a classifier on your data (with all of the features), and let the classifier learn which features are most helpful. it sounds like your goal is prediction rather than model building: you're not going to inspect the model or set of features as something that's interesting in its own right, but rather use it to try to help you make predictions that are as accurate as possible. Given that, feature selection is often unnecessary. Many good classifiers render it unnecessary to perform a separate feature selection step: they already incorporate some techniques to "learn" which features are most helpful and rely especially on those (e.g., they use regularization or similar methods).

For this reason, if your goal is prediction rather than model-building, and if you are using a reasonable classifier (e.g., with regularization), then I would recommend that you avoid separate feature selection and just train the classifier directly on all the features. Only do explicit feature selection yourself if the classifier is known to need feature selection or if your primary interest is in the model itself rather than in ability to make predictions.

Examples of supervised methods that normally don't need or benefit from a separate feature selection step: SVM, random forests, deep learning (with suitable drop-out or regularization), LASSO regression, ridge regression, elastic net regression.

Examples of supervised methods that often do benefit from a separate feature selection step: $k$-nearest neighbors.

Warning: This is a necessarily crude, incomplete summary of an entire area, intended to give you a gist of the field rather than to make precise, 100% accurate statements. Don't rely too heavily on the statements made here; study the area to learn the details.

Answer 2

Ok, the notation could use a bit of work and is somewhat needlessly complex, but before I begin with my answer I want to make sure that I've understood your problem formulation correctly.

Given labeled samples $(y_i, x_i)$ where $x_i$ is some $n$-vector in your feature space, you wish to find the "best-fit" model over all plausible projections.

Now to answer your question. This will most certainly give you great in-sample predictive accuracy, due to the fact that you are massively overfitting your data. You are searching through $2^n$ instances (or at least upper bounded by it) each of which are determined by only by $k \ll 2^n$ samples. If you limit yourself to lower-order polynomials over your features you can still only reasonably fit your data when the number of samples $k$ is greater than the size of your model $O(n^c)$ (without regularization techniques). If you want to proceed with your algorithm despite this concern, I would not use whatever predictive accuracy you are using as a measure of "goodness-of-fit". Predictive accuracy does not take model complexity into account.

Now what you've described is really one way to perform model selection. There are tons of ways to perform this in the literature based on AIC/BIC measures, likelihood ratios, and more complex Bayesian averaging techniques.

Even using something like LASSO or Iterative Hard Thresholding will perform some semblance of model selection without needless searching the entire projection space. For example, lift each $x_i$ to your polynomial space determined by $c$, then just run LASSO (or equivalent regularized classifier). It will still be able to determine which features (both your original and higher-order terms) will be relevant.