Why adding combinations of features would increase performance of linear SVM?

I have a dataset of ~5000 elements represented by vectors composed by ~30 binary values (0 or 1) on which I am performing binary classification with SVM with linear kernel (I use the Scikit learn lib).

For curiosity, I tried to add an extra feature that consists in a AND between two others (remember that all my features are boolean). The result was that the performance of the SVM improved. I was surprised by this improvement because the AND operation is equivalent to a multiplication, therefore I would expect that my SVM, as every linear classifier, was somehow naturally already taking into account mutiplications between features.

What is wrong with my theoretic understanding of SVM ?

Multiplication is not a linear operation. Your linear SVM constructs a (hyper-)plane $$w_0 = w_1 x_1 + w_2 x_2$$ for some weights $w_0, w_1, w_2.$

By introducing the AND-feature, you add another dimension: $$w_0 = w_1 x_1 + w_2 x_2 + w_3 x_1 x_2.$$

It might well be that your two-dimensional data set is not linearly separable, but the three-dimensional data set is.

A small addition: Would adding the OR-feature increase performance even further? No, because it is a linear combination of the other three features: $x \vee y = x + y - (x \wedge y)$ where $\vee$ is OR and $\wedge$ is AND.

• Thanks for you answer. There is something to be noticed, Multiplying two current features does not make a new feature, it adds complexity to the separator. Consider you are in 2d space and you just have y = ax + c, this is a line, and your parameters to set are a and c, by multiplying x to itself your separator would be y = ax**2 + bx + c, this has more complexity and can learn to fit lines and curves whilst the former was just able to fit the lines. Mar 10 '18 at 10:13

Suppose that you have a learning problem and it's just for fitting a function which depends on only one feature, and the function to be predicted is a quadratic shape. you can have a good performance by just having the input feature if you use linear SVM but it will have errors. adding extra features, polynomial features as the input may be useful but it adds more complexity to the classifier and it causes more computational overheads. By the way that's true. You can have better estimate of functions by adding the high order polynomials of the features in hand. I don't know if you are familiar with normal equation or not but what that does is to add high order polynomials to better fit the function which makes the current data.

Intuitively, the linear classifier you built is only trying to find a local minimum meaning he is trying a lot of different operation but it is not looking at the whole space of possibilities, if an "and" operation is relevent to your problem and you add it as a feature it will improve the SVM performance.

The fallback of adding features like this is that it can help the model overfit : it is easier to find a linear bound that separates well the data if the input space has a lot of dimensions.