Phi Transformation for Polynomial Features

Problem

Implement the phi transformation to generate polynomial features from input data. Given a feature vector and a degree, produce the expanded feature vector containing all polynomial terms up to the specified degree.

Solution

def phi_transform(x, degree):
    result = []
    for d in range(1, degree + 1):
        for val in x:
            result.append(val ** d)
    return result

Explanation

1. For each degree from 1 to the specified maximum degree, raise each feature to that power.
2. For a feature vector [x1, x2] with degree 2, the output is [x1, x2, x1^2, x2^2].
3. This is a simple polynomial basis expansion (without interaction terms).
4. Adding a bias term (1) at the start is sometimes included depending on the problem specification.
5. Polynomial features allow linear models to learn non-linear relationships.

Complexity

• Time: O(d * n) where d is degree and n is number of features
• Space: O(d * n) for the expanded feature vector