Polynomial Features

A linear model can only add its inputs up. Give it x and y and it can never express x² or x·y — so it can't represent a curve, and it can't represent "these two things matter together". Polynomial features fix that without changing the model: expand the inputs, and the linear model fits a curve in the original space.

Task: write polynomial_features(rows, degree) returning each row expanded.

For each row, emit every product of features with total degree 1 up to degree, in this exact order:

• degree 1 first, then degree 2, and so on;
• within a degree, every combination with replacement of the feature positions, in lexicographic order.

So [a, b] at degree 2 gives [a, b, a·a, a·b, b·b]. "With replacement" is what allows a·a — a feature multiplied by itself.

• No bias term: the constant 1 is not included.
• Every row has the same number of features and expands to the same length.
• Don't round. Integers in, integers out.
• itertools.combinations_with_replacement(range(n), d) produces exactly the tuples you need, already in the right order.

This is the same ordering scikit-learn's PolynomialFeatures(include_bias=False) uses, which matters if you ever want to compare outputs.

The thing to respect is how fast this grows. Three features at degree 2 give 9 columns; ten features at degree 3 give 285. Every one of them is a parameter to fit, so polynomial expansion buys expressiveness with variance — which is why it's nearly always paired with ridge regression to hold the new coefficients down.