Max Pooling 1D

easyFREECNNs & Sequence ModelsMachine Learning 2

Implement 1D max pooling with configurable kernel size and stride.

Slide a window of size pool_size across the input with step stride, starting at index 0. At each position, output the maximum value in the window. Only windows that fit entirely inside the input are used (no padding, no partial window at the end).

Return the pooled output.

Example

Input

x = [1, 3, 2, 5, 4, 6]
pool_size = 2
stride = 2

Output

[3, 5, 6]

Reasoning

x is a sequence of $6$ numbers, pool_size = 2 is how many neighbouring values each window covers, and stride = 2 is how far the window moves between outputs.
A window may start at position $0, 2, 4$ (counting from $0$ ). Starting at $6$ would run past the end, so the number of windows is $\lfloor (6 - 2) / 2 \rfloor + 1 = 3$ .
Window at $0$ holds $1, 3$ , whose maximum is $3$ . Window at $2$ holds $2, 5$ , maximum $5$ . Window at $4$ holds $4, 6$ , maximum $6$ .
Collecting the maxima in order gives [3, 5, 6]: three values from six inputs, because with stride equal to the window size the windows tile the input without overlap.
Notice that if the stride were $1$ the windows would overlap, giving $\lfloor (6 - 2) / 1 \rfloor + 1 = 5$ outputs, and a value like $5$ could win two windows in a row.

Constraints

x: 1D list of numbers
pool_size: window size (integer >= 1)
stride: step size (integer >= 1)
Return 1D list of max-pooled values

Learn this in

Patterns & MiscellaneousDSA Study Plan CNNs & Sequence ModelsML Study Plan Text ClassificationNLP Study Plan

More from Machine Learning 2

Kernel PCAhard PCA via Covariance Matrixmedium Variance Explained Ratioeasy Feature Scalingeasy GAN Discriminator Losshard

Concept primer

Background Knowledge

Max Pooling is a technique used in Convolutional Neural Networks (CNNs) to reduce the spatial dimensions of an input, while retaining the most important features. In the context of 1D max pooling, this involves sliding a window of fixed size (pool_size) across a one-dimensional input, selecting the maximum value within each window. This process helps to:

Reduce the dimensionality of the input data
Increase the robustness of the model to small transformations
Improve the model's ability to capture larger patterns

The key concepts involved in 1D max pooling include the pool_size (the size of the sliding window) and the stride (the step size at which the window moves). These hyperparameters control the amount of downsampling that occurs during the pooling process. A larger pool_size or stride will result in a greater reduction in dimensionality, but may also lead to a loss of information.

In Sequence Models, 1D max pooling can be used to process sequential data, such as time series data or text sequences. By applying 1D max pooling to these sequences, the model can capture the most important features and patterns, while reducing the impact of noise or irrelevant information.

Algorithm/Approach

The general approach to solving this problem involves implementing a sliding window algorithm, where the window size is equal to the pool_size. At each position, the algorithm will select the maximum value within the window and output this value as part of the pooled output. The window will then move by the specified stride, repeating the process until the entire input has been processed.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty list to store the pooled output
Iterate over the input, using the stride to determine the starting position of each window
For each window, extract the corresponding subset of the input
Calculate the maximum value within the window
Append the maximum value to the pooled output
Repeat steps 2-5 until the entire input has been processed

Common Pitfalls

When implementing 1D max pooling, be careful to:

Handle edge cases, where the window extends beyond the boundaries of the input
Ensure that the pool_size and stride are correctly applied to the input
Avoid using incorrect indexing or slicing operations, which can lead to errors or incorrect results

Time & Space Complexity

The expected time complexity for 1D max pooling is $O(n)$ , where $n$ is the length of the input. This is because the algorithm involves a single pass over the input, with a constant amount of work performed at each position. The space complexity is also $O(n)$ , as the algorithm needs to store the pooled output, which can be up to the same length as the input. However, the actual space complexity will depend on the specific implementation and the values of pool_size and stride.

solution.py

Python 3.13

Test results