📘

Softmax Function

MediumClassification 📚 Machine Learning 1

Implement the softmax function for multi-class classification.

Given a list of logits (raw scores) $z = [z_1, z_2, ..., z_k]$ , compute the softmax probabilities:

$\text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^{k} e^{z_j}}$

For numerical stability, subtract the maximum value from all logits before exponentiating: $\text{softmax}(z_i) = \frac{e^{z_i - \max(z)}}{\sum_{j=1}^{k} e^{z_j - \max(z)}}$

Return the probability distribution as a list, rounded to 4 decimal places.

Example:

Input:

logits = [2.0, 1.0, 0.1]

Output:

[0.6590, 0.2424, 0.0986]

Reasoning:

First, we find the maximum value in the input list: $\max(z) = 2.0$
Then, we subtract this maximum value from all logits to ensure numerical stability: $z' = [2.0-2.0, 1.0-2.0, 0.1-2.0] = [0.0, -1.0, -1.9]$
Next, we compute the exponentials of these stabilized logits: $e^{z'} = [e^{0.0}, e^{-1.0}, e^{-1.9}] \approx [1.0, 0.368, 0.149]$
Finally, we calculate the softmax probabilities by dividing each exponential by their sum: $\text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^{k} e^{z_j}} \approx \frac{[1.0, 0.368, 0.149]}{1.0 + 0.368 + 0.149} \approx [0.6590, 0.2424, 0.0986]$

Constraints:

Input is a list of floats (logits)
Return a list of probabilities that sum to 1 (approximately)
Round each value to 4 decimal places
Use the numerical stability trick (subtract max)

More from Machine Learning 1

RBF Kernel MatrixHard Polynomial KernelMedium Hinge LossEasy Linear Decision BoundaryEasy Gradient Boosting Residual StepHard

Background Knowledge

The softmax function is a crucial component in multi-class classification problems, where the goal is to predict one of multiple classes or labels. It takes a list of logits (raw, unnormalized scores) as input and outputs a probability distribution over all classes. The softmax function is often used in the final layer of neural networks to ensure that the output values are valid probabilities, i.e., non-negative and summing up to 1.

In the context of machine learning, the softmax function is used to model the probability of each class given the input features. The exponential function is used to map the logits to non-negative values, and the normalization step ensures that the probabilities sum up to 1. The softmax function is widely used in various applications, including image classification, natural language processing, and recommendation systems.

To ensure numerical stability, it's essential to subtract the maximum value from all logits before exponentiating. This trick helps prevent overflow issues when dealing with large input values. By doing so, we can avoid NaN (Not a Number) or inf (infinity) values in the output, which can occur when the exponential function is applied to large numbers.

Algorithm/Approach

The general approach to solving this problem involves implementing the softmax function using the given formula. The key steps include:

Computing the maximum value of the input logits
Subtracting the maximum value from all logits to ensure numerical stability
Applying the exponential function to the normalized logits
Computing the sum of the exponentiated values
Normalizing the exponentiated values by dividing them by the sum

This approach can be implemented using a variety of programming languages and libraries, including Python and NumPy.

Step-by-Step Strategy

To implement the softmax function, follow these steps:

Compute the maximum value of the input logits: max_value = max(z)
Subtract the maximum value from all logits: z_normalized = [z_i - max_value for z_i in z]
Apply the exponential function to the normalized logits: exp_values = [ez_i for z_i in z_normalized]**
Compute the sum of the exponentiated values: sum_exp_values = sum(exp_values)
Normalize the exponentiated values: probabilities = [exp_value / sum_exp_values for exp_value in exp_values]
Round the probabilities to 4 decimal places: probabilities = [round(p, 4) for p in probabilities]

Common Pitfalls

When implementing the softmax function, watch out for the following common pitfalls:

Forgetting to subtract the maximum value from all logits, which can lead to numerical instability
Using the wrong formula or implementation, which can result in incorrect output
Not handling edge cases, such as input lists with zero or negative values

Time & Space Complexity

The time complexity of the softmax function is O(k), where k is the number of classes or logits. This is because we need to iterate over the input list to compute the maximum value, apply the exponential function, and normalize the values.

The space complexity is also O(k), as we need to store the normalized logits, exponentiated values, and output probabilities. However, the space complexity can be reduced by using in-place computations and avoiding unnecessary memory allocations.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.