Polynomial Feature Expansion

mediumFREELinear RegressionMachine Learning 1

Implement polynomial feature expansion for a single-feature input.

Given a list of values $x$ and a degree $d$ , create the expanded feature matrix where each row contains $[x_i, x_i^2, x_i^3, ..., x_i^d]$ .

For example, if $x = [2, 3]$ and degree $= 3$ , the output matrix is: $\begin{bmatrix} 2 & 4 & 8 \\ 3 & 9 & 27 \end{bmatrix}$

Return the feature matrix as a 2D list, with each value rounded to 4 decimal places.

Example

Input

x = [2, 3]
degree = 3

Output

[[2, 4, 8], [3, 9, 27]]

Reasoning

Inputs: x holds two samples of a single feature, $x_1 = 2$ and $x_2 = 3$ , and degree $d = 3$ says how many power terms each sample is expanded into.
Row 1 ( $x_1 = 2$ ): the powers $1$ through $3$ give $2^1 = 2$ , $2^2 = 4$ , $2^3 = 8$ , so the row is $[2, 4, 8]$ .
Row 2 ( $x_2 = 3$ ): likewise $3^1 = 3$ , $3^2 = 9$ , $3^3 = 27$ , giving $[3, 9, 27]$ .
Output: a $2 \times 3$ matrix [[2, 4, 8], [3, 9, 27]]: one row per sample, one column per power. Column $j$ is the feature $x^j$ , so a linear model on these columns can fit a cubic in $x$ .
Notice: there is no column of ones ( $x^0$ ); the exponents start at $1$ . The output has $d$ columns no matter how many samples there are, and fractional inputs such as $0.5$ shrink with each power ( $0.5, 0.25, 0.125$ ), which is where the 4-decimal rounding matters.

Constraints

x is a list of numbers, degree is a positive integer >= 1
Return a 2D list where row i has [x_i, x_i^2, ..., x_i^degree]
Round each value to 4 decimal places
Do NOT include a bias column of ones

Learn this in

Linear RegressionML Study Plan ClassificationML Study Plan Support Vector MachinesML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

Polynomial feature expansion is a technique used in linear regression to increase the dimensionality of the input data. The goal is to transform the original features into new features that can capture more complex relationships between the inputs and outputs. This is particularly useful when dealing with non-linear relationships, as linear models can struggle to fit the data. By expanding the features into higher-order polynomials, we can create a more expressive model that can better capture the underlying patterns in the data.

The concept of polynomial feature expansion is rooted in the idea of basis functions, which are used to transform the input data into a more suitable representation for the model. In this case, the basis functions are simply powers of the input feature, i.e., $x^1, x^2, x^3,..., x^d$ . By combining these basis functions, we can create a new feature space that is more amenable to linear regression. This technique is commonly used in machine learning to improve the performance of linear models on non-linear data.

The degree of the polynomial expansion, denoted by $d$ , controls the number of basis functions used to transform the input data. A higher degree expansion will result in a more complex model that can capture more subtle patterns in the data, but may also increase the risk of overfitting. Therefore, it's essential to carefully choose the degree of the expansion based on the specific problem and data at hand.

Algorithm/Approach

The general approach to solving this problem involves using a loop to iterate over each input value and calculate the corresponding polynomial features. The main concept employed in this approach is the use of nested loops to generate the expanded feature matrix. The outer loop iterates over each input value, while the inner loop calculates the polynomial features for each degree up to $d$ .

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty list to store the expanded feature matrix.
Iterate over each input value $x_i$ in the list $x$ .
For each $x_i$ , calculate the polynomial features $x_i^1, x_i^2, x_i^3,..., x_i^d$ using a loop.
Append the calculated features as a new row in the expanded feature matrix.
Round each value in the feature matrix to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to initialize the expanded feature matrix before appending new rows.
Using incorrect loop indices or bounds, leading to incorrect calculations or IndexError exceptions.
Failing to round the values in the feature matrix to the correct number of decimal places.

Time & Space Complexity

The expected time complexity of the solution is $O(n \cdot d)$ , where $n$ is the number of input values and $d$ is the degree of the polynomial expansion. This is because we need to iterate over each input value and calculate the polynomial features for each degree up to $d$ . The space complexity is also $O(n \cdot d)$ , as we need to store the expanded feature matrix, which has $n$ rows and $d$ columns.

solution.py

Python 3.13

Test results