Many-to-One Output Selector
Problem Statement
Select the final relevant output from a batch of variable-length sequences.
Background
In "Many-to-One" architectures (e.g., sentiment analysis), sequences in a batch often have different lengths. We pad shorter sequences but need to extract the hidden state at the last valid timestep for each sequence.
Your Task
Write a function get_final_states(hidden_states, sequence_lengths) that extracts the final hidden state for each sequence in the batch.
Input Format
- hidden_states: numpy array of shape (batch_size, max_seq_len, hidden_dim)
- sequence_lengths: list of integers, length of each sequence in the batch
Output Format
Return a numpy array of shape (batch_size, hidden_dim) containing the last valid hidden state for each sequence.
Example:
hidden_states shape (2, 3, 4), sequence_lengths = [2, 3]
Shape (2, 4) with hidden_states[0,1,:] and hidden_states[1,2,:]
For batch 0, take index 1 (length 2, 0-indexed). For batch 1, take index 2 (length 3).
Constraints:
- 1 <= batch_size <= 64
- 1 <= max_seq_len <= 512
- 1 <= hidden_dim <= 512
- sequence_lengths[i] >= 1 for all i
Many-to-One Output Selector: Comprehensive Background
1. Background Knowledge
Core Concepts
Many-to-One Architecture In sequence-to-sequence learning, many-to-one settings occur when multiple input sequences need to be reduced to a single output representation. This is fundamental in tasks like sentiment analysis, where an entire text sequence is classified into a single sentiment label.
Variable-Length Sequences and Padding Real-world sequences have different lengths. To process them efficiently in batches, shorter sequences are padded with dummy values (typically zeros) to match the longest sequence length. However, padding tokens don't carry meaningful information, so we must extract the hidden state at the last valid (non-padded) position for each sequence.
Hidden States in RNNs/LSTMs In recurrent architectures, the hidden state at each timestep encodes information about the sequence up to that point. The final hidden state (at the last valid timestep) serves as a compressed representation of the entire sequence, making it ideal for downstream classification or regression tasks.
Why This Matters
Without proper final state extraction, your model would use padding information, degrading performance. This is a critical preprocessing step in any sequence classification pipeline.
2. Algorithm Approach
Direct Indexing Strategy
The most efficient approach uses advanced indexing to directly access the correct position for each sequence:
Conceptual Steps:
- Create a batch index array: [0, 1, 2,..., batch_size-1]
- Create a position index array from sequence_lengths - 1 (convert to 0-indexed)
- Use fancy indexing to extract: hidden_states[batch_indices, position_indices, :]
This avoids loops and leverages NumPy's vectorized operations.
Alternative: Loop-Based Approach
result = []
for i in range(batch_size):
result.append(hidden_states[i, sequence_lengths[i] - 1, :])
While intuitive, this is slower for large batches.
3. Step-by-Step Strategy
Step 1: Understand the Indexing Problem
- Shape: (batch_size, max_seq_len, hidden_dim)
- For sequence i, the last valid position is sequence_lengths[i] - 1
- Goal: Extract hidden_states[i, sequence_lengths[i] - 1, :] for all i
Step 2: Create Index Arrays
batch_indices = np.arange(batch_size) # [0, 1, 2,...]
position_indices = np.array(sequence_lengths) - 1 # Convert to 0-indexed
Step 3: Apply Fancy Indexing
NumPy's advanced indexing allows simultaneous indexing across multiple dimensions:
result = hidden_states[batch_indices, position_indices, :]
This selects hidden_states[0, seq_len-1, :], hidden_states[1, seq_len-1, :], etc.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.