1. Sinusoidal Positional Encoding (Vaswani et al 2017)
2. RoPE – Rotary Positional Encoding (Su et al., 2021)
3. ALiBi – Attention with Linear Biases, Ofir Press et al 2021
4. Extending pre-trained context window
   • Position Interpolation (Chen et al 2023)
   • NTK aware scaling (block97 2023)
   • YaRN – Yet Another RoPE extensioN method (Peng et al 2023)

Sinusoidal Positional Encoding (Vaswani et al., 2017)

Prior to transformer architecture proposed in the paper Attention Is All You Need” (Vaswani et al., 2017), sequence modelling tasks such as language translation were handled using recurrent neural networks (RNNs) and recurrent variants such as LSTMs. In recurrent architectures, tokens are processed sequentially, one after another.

For a sequence of tokens , the the hidden state evolves as,

where,

• is the embedding of token at position
• is the hidden state after processing token

Since tokens are processed sequentially, the order is naturally embedded into the computation. However, sequential processing prevents parallel implementation during training because a token at position cannot be processed until the previous tokens has been consumed.

Transformer architecture

In Transformer architecture all tokens in sequence can be processed in parallel. To encode the sequence information, a positional encoding vector defined using sinusodial basis functions is defined for each element in the sequence.

In the following sections, we will go over the positional encoding scheme followed by attention scheme. In the attention layer, the interactions between the tokens (with the injected position embeddings) is used to understand the intuitions behind the definition of the positional encoding.

Positional Encoding

Each token is mapped into an embedding vector of dimension as,

Stacking all the all the embedding vectors for the sequence of length ,

The position embedding at token position is defined as :

Positional embedding can be visualized as even & odd dimensions having sine/cosine terms and with multiple frequencies across the dimension ,

Stacking all the all the positional encoding vectors for the sequence of length ,

To encode the sequence information, postitional embeddings are added into the token embeddings.

The combined input matrix capturing the sequence of token embedding and position encoding is defined as,

Self-attention layer

The transformer architecture models interactions between all tokens using the self-attention mechanism. The combined input matrix containing token embeddings and positional encoding is projected into three learned representations called query, key and value as,

where, the learned matrices , and project the token embeddings into different representation spaces.

Broadly,

• (query) captures what information a token is searching for
• (key) captures what information a token contains
• (value) contains the information passed forward to the next layer

The interaction between every pair of tokens is computed through the query-key similarity matrix,

where the element measures how strongly token attends to token ,

The interaction score is normalized by the key dimension and converted into attention weights using softmax ^{(refer post Gradients for multi class classification with Softmax)},

The output of the attention layer is computed as,

Each token representation is updated by aggregating information from all other tokens in the sequence.

Multi-head attention

Instead of using a single attention computation, transformer architecture employs multiple attention heads, where each head learns different relationships between tokens.

For attention head , the query, key and value projections are computed as,

Each head independently computes self-attention as,

The outputs of all heads are concatenated and projected as,

where denotes the number of attention heads.

Using multiple attention heads enables the model to simultaneously learn different relationships such as local context, long-range dependencies, syntax and semantics.

Stacking multiple transformer layers

The first layer takes the position encoded token embeddings as input,

The transformer architecture consists of multiple stacked attention layers. The output of one layer is passed as the input to the next layer, progressively refining the token representations.

If the input to layer is , then the output of the transformer block is defined as,

where denotes the transformer block consisting of

• multi-head self-attention,
• feed-forward network,
• residual connections ^{(refer paper Deep Residual Learning for Image Recognition, He et al 2015)} and
• layer normalization ^{(refer paper Layer Normalization, Lei Ba et al 2016)}

Expanding the operations,

where,

• denotes the multi-head attention operation
• denotes the position-wise feed-forward network (see
• denotes layer normalization

After stacked transformer layers, the final representation becomes,

Parameters in Sinusoidal Positional Encoding

In the additive sinusoidal Positional encoding described in the previous section, authors makes several key design choices, namely

• sinusoidal basis functions
• Exponentially spaced frequencies
• Emperically chosen base frequency

In the rest of the section, let us explore the intuitions and rationale behind some of the choices.

Need for sinusoidal basis function

To understand the rationale for sine and cosine terms in positional embedding, let us consider the input to the attention block for a token at ,

In the attention layer, the interaction between two tokens at position and is computed as,

Assuming that the terms and are identity matrices, the score can be approximated as,

Taking the position interaction term,

Applying the trignometric identity,

the position interaction term simplifies to

The position interaction term depends only on the relative distance between the tokens .

The choice of using sine and cosine terms in the position encoding, leverages the sinusoidal identity makes the position interaction term to a decaying function which depends only on the relative distance between tokens.

Normalized positional encoding terms

Let us define the normalized position interaction terms as

Plot of the normalized positional encoding terms

code @ positional_encoding/autocorrelation_positional_encoding.ipynb

Can see that , which captures the relative positional similarity (autocorrelation of positional encoding), exhibits an overall decaying envelope as the distance increases due to multiple frequency components being out of phase. The overall decaying trend indirectly encodes information about the relative distance between tokens.

Need for multiple frequencies

In the position encoding, multiple frequencies are chosen for various dimension as

where, the frequencies are spaced exponentially as

If only a single frequency is chosen, the relative position encoding term becomes periodic. This means different relative distance can produce identical positional similarities which causes ambiguity. Plotting the normalised positional similarity term for different number of frequency counts, can see that :

• with few frequencies (low D) : stronger oscillations
• with more frequencies (higher D) : smoother decay

Summarising, by combining multiple frequencies, the broad intuition is :

• high frequencies capture local relative distances
• low frequencies capture the long range distances

Together, they increase the probability of each relative distance having a unique signature enabling the model to distinguish near by and far away tokens.

code @ positional_encoding/multiple_frequencies_positional_encoding.ipynb

Thus, the use of multiple exponentially spaced frequencies allows the model to encode position as a combination of signals at different scales, enabling robust representation of both local and global structure.

The choice of the constant 10,000

The choice of 10,000 as the base in the geometric progression of frequencies was an empirical engineering decision.

The positional encoding uses frequencies

which span from high-frequency components (short wavelengths) to low-frequency components (long wavelengths).

a) At (shortest wavelength):

The angular frequency is , giving a wavelength of

This short wavelength changes rapidly across nearby positions, helping the model distinguish tokens that are close to each other.

b) At (longest wavelength):

The angular frequency is approximately

giving a wavelength of

This long wavelength varies slowly across positions, helping the model encode coarse distinctions between tokens that are far apart.

Thus, the choice of 10,000 creates a spectrum of frequencies that provides both local positional resolution and long-range positional awareness.

The plot of autocorrelation of positional encoding for different base frequencies of 1000, 10000 (default) and 100000 is below.

Based on the autocorrelation plot, handwaving explanation for the choice of the base frequency, and on hindsight that typical sequence lengths around the 2017 ish were around 512 tokens,

• With a base of 1000, the relative positional similarity decays more rapidly, dropping below about 0.2 at a relative distance near 100 tokens.
• With a base of 10,000, the decay is slower, and the same similarity threshold is reached only around 600 tokens.
• When the base is increased further to 100,000, the decay becomes even slower, but the lower slope reduces the separation of tokens which are close by.

So, a base of 10,000 appears to be a practical compromise between distinguishing nearby tokens and retaining information across the full training context.

Code @ positional_encoding/base_frequency_positional_encoding.ipynb

RoPE – Rotary Positional Encoding (Su et al., 2021)

In the paper RoFormer: Enhanced Transformer with Rotary Position Embedding“Su et. al 2021, the authors proposed a multiplicative approach for positional encoding instead of the additive approach for sinusoidal positional encoding.

The token embedding be of dimension , and defined as :

The token embedding at position is grouped into adjacent dimension pairs, i.e . . The token embedding at position is first projected into query and key representations using learned projection matrices and .

The query and key vectors are then grouped into adjacent dimension pairs, i.e., and .

The rotation matrix for the pair is defined as

where,

The complete rotation matrix for positional encoding is formed by stacking these 2×2 rotation blocks across the diagonal, where each 2×2 block rotates a pair of embedding dimensions with a different angular frequency.

The rotary positional encoding is then applied to the query and key vectors as,

Expanding the matrices for ,

Similarly, the rotated query and key vectors for the token at position are defined as

Note :

Unlike sinusoidal positional encoding, which is added once to the input embeddings, RoPE is applied inside the self-attention block by rotating the query and key vectors. Since each transformer layer contains a self-attention block, the rotation operation is applied at every attention layer of the transformer architecture.

Interaction terms

In the attention layer, the interaction between two tokens at position and is computed as

.

For intuition, assuming that the terms and are identity matrices. Then the query and key terms simplify to

With this assumption, the score is approximated as,

Expanding the terms,

Let us find the score consider onlying the first frequency pair ,

Expanding the multiplication terms,

Grouping common terms,

Applying the trigonometric identities,

the interaction term corresponding to the frequency becomes

Since and , the term simplifies to

Notice the key result that sine and cosine terms depend only on , and hence the interaction term depends only on the relative distance.

Extending for all frequencies, for the frequency pair , the interaction term becomes

Summing across all frequency pairs, the overall interaction score becomes

Similar to the additive positional encoding defined earlier, the interaction term in multiplicative positional encoding defined in RoPE also depends only on the relative distance between tokens .

However, unlike additive sinusoidal positional encoding, multiplicative positional encoding in RoPE does not introduce token-position cross interaction terms such as .

Complex Number Interpretation

The derivation for rotary positional encoding using explicit matrix multiplication can be expressed compactly using complex numbers. The token embedding at position is grouped into adjacent dimension pairs, i.e. , where each pair can be represented as a complex number

where,

is the imaginary unit.

The rotary positional encoding is applied as a complex phase rotation,

Thus, the rotated embedding becomes,

Expanding the multiplication terms,

Since ,

Comparing the real and imaginary components, we observe that this is identical to the math derived earlier.

Interaction terms

In the attention layer, the interaction between two rotated token embeddings at positions and can be written using complex number representation.

For simplicity, assuming the query and key projection matrices are identity matrices, the rotated embedding pair at frequency is expressed as

The interaction score is computed using the complex conjugate of the second term and taking the real-valued component of the output,

with,

the interaction term becomes

The absolute token position cancels out, leaving only the relative token distance .

Normalized Positional Encoding

Let us define the embedding interaction term as,

where,

• is the embedding similarity magnitude
• is the embedding dependent phase difference

To isolate the positional component independent of the token embedding, consider

• embedding interactions are normalized i.e.
• embedding interaction phase effects are not there i.e.

With this the score simplifies to,

Then the normalized positional encoding over all the dimensions is,

This is identical to the sinusoidal positional encoding defined earlier.

ALiBi – Attention with Linear Biases, Ofir Press et al 2021

In the paper “Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation, Ofir Press et al 2021″, authors note that both additive sinusoidal positional encoding and multiplicative rotary positional encoding (RoPE) degrade when evaluated on sequence lengths significantly longer than those seen during training.

They also note that RoPE extrapolates better than additive sinusoidal positional encoding, with potential reasons being :

• rotary positional encoding injects positional information in every layer and not just the initial one as in additive sinusoidal positional encoding
• rotary positional encoding is done only on queries () and keys () and not to values ()

With this intuition, authors proposed Attention with Linear Bias (ALiBi), where a static non learned bias is applied to the query key dot product prior to softmax computation.

Equations

Consider a sequence of length (). In standard self-attention, the attention score between a query at position () and a key at position () is computed as

where,

• is the query at position ,
• , and with causal language modelling the first i keys with and
• is the head dimension

ALiBi modifies the attention score directly by adding a position-dependent linear bias . The modified attention score becomes,

where,

• is head specific scalar fixed before training.

• for a model with attention heads, the set of slope is geometrically spaced and starts at .

The ALiBi paper focused on the auto-regressive causal language models, where a query at position can only attend to the first keys. Under this causal constraint, the bias term between a query at position and a key at position is calculated linearly based on their directed distance:

This creates a lower triangular bias matrix, with the diagonal elements receive a penalty of 0, and the penalty grows increasingly negative as the key moves further back into the past tokens.

This relative position information is injected at every attention operation across layers by adding a position dependent bias.

toy implementation @ positional_encoding/alibi_causal_positional_encoding.ipynb

Extending pre-trained context window

Multiple approaches for extending the pre-trained context length to a higher number has emerged in literature. In the rest of the sections, we cover three approaches – scaling the token position index, scaling by a frequency dependent factor and a scheme which combines the above approaches.

Position Interpolation (Chen et al 2023)

In the paper Extending Context Window of Large Language Models via Position Interpolation, Chen et al 2023, proposes an approach to extend the context window of RoPE based LLMs which was trained for typically ~2048 tokens to around 32768 tokens (16x).

With RoPE, the rotation factor for token at position along the the dimension is,

where,

With Position Interpolation, the rotation factor for token position is scaled by a factor , to become

where,

• is the context length for which the model is trained
• is the desired context length

NTK aware scaling (bloc97, 2023)

In the reddit post ^{(link here)} author bloc97 proposed an alternate way to extend to longer context lengths of RoPE based Large Language Models (LLMs). The key intuition comes from Neural Tangent Kernel (NTK) perspective of neural networks which suggested that neural networks are more sensitive to distortions in high frequencies than low frequency ones.

So instead of uniformly compressing all frequencies as in Positional Interpolation (PI), NTK aware scaling applies a frequency dependent scaling.

This is achieved by by introducing a frequency dependent scaling where highest frequency dimension is preserved, and progressively scaling lower frequencies, till reaching the scaling factor for the lowest frequency .

Equations

The base frequency in RoPE is defined as,

To scale the context window by factor , the base is modified as,

Substituting,

For highest frequency (), the scale modifier is , preserving the high frequency local positional context.

For the lowest frequency (), the scale factor is, scaling the lowest frequency by the desired scaling factor .

toy implementation @

positional_encoding/pi_ntk_aware_scaling.ipynb

YaRN – Yet Another RoPE extensioN method (Peng et al 2023)

In the paper YaRN: Efficient Context Window Extension of Large Language Models, Peng et al 2023, authors noted the following limitations :

• As the Position Interpolation scales all dimensions (frequencies) by equally by a factor , it alters the high frequency components of RoPE
• The NTK aware scaling alleviated this to large extend by scaling high frequencies less and low frequencies more. However, identifying the optimal base frequency has to be found emperically and increasing the difficulty and cost for a fine tuned model.

To address this, authors proposed NTK by parts approach described below

NTK by parts

Let the wavelength at dimension is defined as,

Authors observe that, dimensions where the wavelength is longer than the maximum context length seen during pre-training captures the absolute positional information. However, for the dimensions where wavelength is short, it typically captures the relative positional information.

Equations

Defining the ratio between pre-trained context length and wavelength at dimension as,

Based on the ratio, the following constraints are defined :

1. Do not interpolate for the dimensions whose wavelength is smaller than the pre trained context length i.e.
2. Do the interpolation for the dimensions whose wavelength bigger than the pre trained context length i.e
3. For the dimensions in between, have a bit of both

Capturing this in equations,

where,

• is the scale factor to increase the context length from pre-trained length to
• is a ramp function defined as

• are thresholds to be tuned.

In the paper, authors proposed on the Llama family of models.

Pluggin in numbers,

for a pre-trained context length of and scaling to by i.e. to extend the context length to.

Ratio	Wavelength (for )	Remark
		Interpolation
		Linear transition
()		No interpolation.

toy implementation @

positional_encoding/yarn_scaling.ipynb

Attention scaling

In addition to the frequency scaling methods described above, authors propose that scaling the attention helps lower the perplexity of the model.

The scaled attention is defined as,

where,

• 
• is the scale factor to increase the context length from pre-trained length to

The equation for temperature scaling is found by fitting at the lowest perplexity against different values of .

Summary

This post covers the following :

• the transformer positional encodings from additive sinusoidal vectors to multiplicative rotary matrices (RoPE) and static linear attention biases (ALiBi).
• Focuses on how their mathematical interactions capture relative token distance.
• Discuss the context-extension methods like Position Interpolation, NTK-Aware Scaling, and YaRN .
• Code snippets for each of the scheme is provided.

The post Positional Encoding in Transformers appeared first on DSP LOG.

The machine learning models we have discussed – binary classification ^{(refer post Gradients for Binary Classification with Sigmoid)} or multiclass classification ^{(refer post Gradients for multi class classification with Softmax)} needs tweaks to learn from these imbalanced datasets. Without these adjustments, the models can “cheat” by favouring the majority class and can report a pseudo high accuracy though the class specific accuracy is low.

Different strategies have emerged over the years, and in this article we are covering the approaches listed below.

1. Weighted cross entropy
   • Foundational baseline, where a class-specific weight factor to the standard cross-entropy loss to weight the loss based on frequency of the class.
2. Focal Loss for Dense Object Detection, Lin et al. (2017)
   • Propose a modulating factor to the cross-entropy loss to down-weight easy/frequent examples which indirectly forces the model to focus on hard/rare examples
3. Asymmetric Loss for Multi-Label Classification, Ridnik et al. (2021)
   • Extended the intuition of Focal Loss by having independent hyper-parameter for positive and negative samples. This allows for more aggressive “pushing” of easy/frequent examples while preserving the gradient signal for hard/rare samples.
   • Additionally, authors introduces a probability margin that explicitly zeros out the loss from easy/frequent samples.
4. Class-Balanced Loss Based on Effective Number of Samples, Cui et al. (CVPR 2019)
   • Based on the intuition that there are similarities among the samples, authors propose a framework to capture the diminishing benefit when more datasamples are added to a class.
5. Long-tail Learning via Logit Adjustment, Menon et al. (ICLR 2021)
   • Based on the foundations from Bayes Rule, authors propose that adding a class dependent offset based on the prior probabilities help the model learn to minimise the balanced error rate (the average of error rates for each class) instead of minimising global error rate.

Weighted Cross Entropy

Standard Cross Entropy treats all classes equally, which becomes problematic when your dataset contains 1,000s of easy background examples but only 100s of rare foreground objects. In such cases, the majority class dominates the loss and biases the model. Weighted Cross Entropy (WCE) addresses this by assigning a static weight to each class, manually boosting the importance of rare samples.

Binary weighted Cross Entropy

For binary classification, a weighting factor to the standard BCE formula is used the scale the loss.

where is typically set to the inverse of the class frequency.

By setting a high for the rare class (e.g., 0.9 for the 100 foreground samples) and a low weight for the frequent class (0.1 for the 1,000 background samples), ensures that the rare foreground objects provide a sufficient gradient signal during training.

Multiclass Weighted Cross Entropy

In the multiclass case with classes, the loss for a single example where is the ground-truth label is defined as:

Where is a fixed weight assigned to class , typically calculated using the Inverse Class Frequency:

Weighted versions of cross entropy loss is natively supported in PyTorch library as :

• torch.nn.BCEWithLogitsLoss ^(refer) : using the argument pos_weight for the binary classification
• torch.nn.CrossEntropyLoss ^(refer) : using the argument weight for multiclass classification.

Toy example computing the loss using the manually vs PyTorch implementation @ loss_functions_for_class_imbalance/weighted_cross_entropy.ipynb

Focal Loss (Lin et al 2017)

In the paper Focal Loss for Dense Object Detection Lin et al. (2017) , authors propose an extension to standard Cross Entropy loss to focus training on hard/rare examples. The key intuition is that by adding a probability-dependent modulating factor to the loss, the contribution of easy/frequent examples (where the estimated probability is close to the truth) is down-weighted. This indirectly forces the training to focus specifically on the hard/rare examples.

Focal loss is defined as :

where,

• represent the ground truth labels and
• is the estimated probabilities
• is a hyperparameter to control the modulating factor

Note : The standard cross entropy loss for binary classification is

Gradients in standard Cross Entropy Loss

To understand how Focal Loss works, the gradient i.e. the derivative with respect to the model’s output logits, is explored. The model outputs a real number number, which is converted to a probability using the sigmoid function .

Using the chain rule from calculus ^{(refer wiki entry on Chain Rule)}, then the gradient of loss with respect is found as – gradient of loss with respect to probabilty multiplied with gradient of probability with respect to parameter i.e.

For standard Cross Entropy loss, as derived in the post on Gradients for Binary Classification with Sigmoid, gradient is,

The gradient is linear and depends only on the error – this means an “easy/frequent” example (where the error is small, e.g., 0.1) when summed over large number of of easy examples still contributes to the loss and can overwhelm the training.

Gradients in Focal Loss

For computing the gradients with focal loss, let us define the ground truth labels and the model’s estimated probability as :

where,

• background class with 1000’s of easy/frequent examples
• foreground class with 100’s of hard/rare examples

Taking the case of ,

Multiplying with ,

Sweeping the value of from 0 to 1 for , the behaviour of the individual terms are as shown in the plot below.

code @ focal_loss_terms.py

The model learns easy/frequent examples much faster and is close to the ground truth , which means . As approaches 1, the scaling term effectively silences the gradient.

Plugging in numbers, when the model is estimating for the frequent examples, the throttle becomes and the gradient from these examples is effectively silenced.

Thus the term acts as a throttle for easy/frequent examples.

The Weighting Factor $\alpha$

With the focusing parameter down-weighting easy/frequent examples, the choosing class weights parameter using inverse of class frequency is not preferred. To understand the intuitions, let us define as below :

The Focal Loss including is :

When we go with inverse of class frequency, typically values of is :

• high (around 0.9) for (hard/rare foreground class) and
• low (around 0.1) for (easy/frequent background class)

With the Focal Loss, the focusing term aggressively down-weights the easy examples and the accumulated loss from the background class drops drastically. Then with high the hard/rare foreground class with only 100s of examples will now dominate the gradient and can cause instability.

Therefore, as is increased, should be decreased. In the paper, for , the authors found the best balance was actually for the foreground class .

Extension to Multiclass Focal Loss

While the binary case uses a single probability , the multiclass classification involve distinct classes. In the multiclass setting, the model outputs a vector of logits, which are transformed into probabilities using the Softmax function. The estimated probability for class is :

The Multiclass Focal Loss for a single example for ground truth class is,

Typically is chosen as a scalar, and the weights factor is defined as a class dependent vector.

Choosing for the rare classes and for the frequent classes seems to be choice which can be arrived at using hyper parameter tuning. Though it is counter intuitive to give higher for frequent classes, it helps to prevent their contribution from being completely throttled by the term.

Toy example showing implementation of Focal Loss for binary and multi-class classification @ loss_functions_for_class_imbalance/focal_loss_binary_multiclass.ipynb

Assymetric Loss (2021)

In the focal loss definition, the same is used for both background class with high count of easy examples and rare foreground class. If a higher is used to throttle the gradients of easy background classes, then this also affects when the model is learning the hard foreground classes.

In the paper, Asymmetric Loss for Multi-Label Classification, Ridnik et al. (2021). authors proposed to decouple the for foreground and background classes.

To give emphasis to the contribution of positive samples, .

The typical values can be so that the hard/low count positive samples behave similar to standard cross entropy loss and to throttle gradients for easy/high count background classes.

Authors further propose adding a margin on the probability of easy backround classes by probability shifting which discards them when the probability is below a threshold.

with as a hyperparameter and a typical value being .

Combining both, the Assymetric Loss is defined as,

Toy implementation of assymetric loss @ loss_functions_for_class_imbalance/assymetric_loss.ipynb

Class-Balanced Loss (Yin Cui et al 2019)

In the paper Class-Balanced Loss Based on Effective Number of Samples, Cui et al. , authors argue that there will be similarities among the samples and as the number of samples increase, the probability that this sample is covered in the existing samples increases. Based on this intuition, authors propose a framework to capture the diminishing benefit when more datasamples are added to a class.

Derivation

Let us denote the effective number of samples as , and the total volume of this space as . Consider the case where we have examples and is going to sample the example. The probability that the newly sampled example to be overlapped with the previous samples is,

Expected volume with the example is,

To solve for , re-writing as a geometric series,

For the general can be written as

Solving for ,

Note :

• When , the effective number of samples indicating that there is no benefit in adding more samples.
• When , the expected number of samples , indicating that each sample is treated unique.

In the paper authors explore as a hyper-parameter and report that in long tailed CIFAR-10 (Imbalance Factor = 50) dataset, the best is . In this dataset, the most frequent class has 5000 images, while the rarest class has 100 images. With , the effective number of samples for the frequent and rarest class is

Weighting Scheme	β Value	Majority En​	Minority En​	Ratio (Maj/Min)
Inverse Frequency		5000	100	50.0 : 1
Class-Balanced		3934.85	99.5	39.5 : 1
Class-Balanced		993	95.3	10.4 : 1
No Weighting		1	1	1.0 : 1

Though the weight ratio between frequent class and small class is 50:1, by choosing a lower , we assume higher redundancy in the dataset and give lesser weightage to the sample count of majority class.

Applying to loss

To balance the loss, for each class which has samples, a weighting factor that is that is inversely proportional to the effective number of samples for each class is found out, i.e

.

To make the total loss roughly in the same scale when applying , a normalization factor to scale the sum of to the class count i.e.

With this definition,

a) the class balanced softmax loss is,

b) class balanced focal loss is,

Class-Balanced Loss as a specific weighting strategy for standard loss functions and it provides a mathematically grounded way to calculate the weight capturing the “effective number of samples“

Code to find the class balanced weights @ loss_functions_for_class_imbalance/class_balanced_weights.ipynb

Logit Adjustment (Menon et al 2021)

In the paper Long-tail Learning via Logit Adjustment, Menon et al. (ICLR 2021), authors argue that for scenarios with heavy class imbalance, the average misclassification error is not a suitable metric.

Average Classification error in Multiclass classification

Consider that is an dimensional input feature vector and the model is trained on a multiclass classification task to learn the probability of classes.

The model outputs a vector which captures the logarithm of the probability (aka logit) for each class. The scores are converted into probabilities using SoftMax function. For the class , the estimated probability is,

Taking logarithm,

where, constant .

The training loop to estimate the probability of the true class given the input , minimizes the negative log likelihood i.e.

From the above equation, we can see that – when the logit corresponding to true class is much greater than the logit corresponding to incorrect class i.e. , the exponential term and the loss tends to 0.

To understand how the class imbalance affects the loss, the term can be expanded using Bayes rule ^{(refer wiki entry)} as,

If the classes are balanced, then the class frequency term tends to 0 and does not contribute to the loss. However, when there is class imbalance, for example with with the class being rare, then the term is a large positive number contributing to the loss.

To minimize the loss, instead of doing the “hard work” of learning discriminative features in the likelihood term , the model can “cheat” by biasing its predictions toward the majority class .

Thus we can see that a model which minimizes the average misclassification error has its learning affected by the prior probabilities i.e. .

Logit Adjustment for Balanced Error rate

For a model to minimize the balanced error rate i.e. , the loss should depend only on the likelihood and not be affected by the prior probabilities .

This is can be done by dividing the posterior probabilities by the prior probabilities. This is equivalent to subtraction of the log prior for each class i.e from the model output capturing the log probabilities .

Defining as the probability of each class , the adjusted logit for each class is,

where, is a hyperparameter to tune.

• : Theoretically aligns the model to minimize the balanced error rate, typically chosen value.
• : Provides a partial correction, useful for balancing overall accuracy and per-class recall in noisy datasets
• : Over-corrects for minority classes, pushing decision boundaries further to prioritize rare class recall
• : Disables the adjustment, reverting the model to standard cross entropy loss.

The loss function with adjusting the logits is ,

Incorporating into the training loss, enforces a class-dependent margin. This forces the model to “work harder” on minority classes by requiring a higher logit score for a rare class to achieve the same loss as a majority class.

During inference, the adjustment is typically removed to use the raw learned likelihoods, resulting in a model that has learned to treat each class with equal importance regardless of its original frequency in the training set.

Example code with logit adjusted loss @ loss_functions_for_class_imbalance/logit_adjusted_loss.ipynb

Summary

This article covers :

Evolution: How we move beyond standard Cross Entropy to specialized loss functions like Focal Loss and Asymmetric Loss to handle extreme class imbalance.

Math: Detailed derivations of the gradients for Focal Loss and a Bayesian decomposition of Logit Adjustment to show how models “cheat” using prior probabilities.

Intuition: A look at the Effective Number of Samples framework, capturing the diminishing returns of adding more data to a majority class.

Code: Complete Python and PyTorch implementations, including toy examples and notebooks comparing manual derivations against library-standard functions.

The post Loss functions for handling class imbalance appeared first on DSP LOG.

Papers referred :

1. Neural Probabilistic Language Model, Bengio et al 2003
   • proposed a neural network architecture to jointly learn word feature vector and probability of words in a sequence.
2. Hierarchical Probabilistic Neural Network Language Model, Morin & Bengio (2005)
   • given the softmax layer for finding the probability scales with vocabulary, proposed a hierarchical version of softmax to reduce the complexity from to .
3. Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics, Gutmann et al 2012,
   • Instead of directly estimating the data distribution, noise contrastive estimation estimates the probability of a sample being from the data versus from a known noise distribution.
   • This approach was extended to neural language models in the paper A fast and simple algorithm for training neural probabilistic language models A Mnih et al, 2012.
4. Efficient Estimation of Word Representations in Vector Space, Mikolov et al 2013.
   • proposed simpler neural architectures with the intuition that simpler models enable training on much larger corpus of data.
   • Continuous Bag of Words (CBOW) to predict the center word given the context, Skip Gram to predict surrounding words given center word was introduced.
5. Distributed Representations of Words and Phrases and their Compositionality, Mikolov et al 2013
   • speedup provided by sub sampling of frequent words helps to improve the accuracy of the less-frequent words
   • simplified variant of Noise Contrastive estimation called Negative Sampling
6. GloVe: Global Vectors for Word Representation, Pennington et al 2014
   • propose that ratio of co-occurrence probabilities capture semantic information better than co-occurance probabilities.

In this post we will cover the key aspects proposed in the above papers with supporting python code.

Neural Probabilistic Language Model (Bengio et al, 2003)

Reference : Neural Probabilistic Language Model, Bengio et al 2003

The probability of sequence of words can be expressed as conditional probability of sequence of previous words, i.e

For example, consider a sequence of 4 words,

Then, by the chain rule of probability:

Substituting the actual words:

For a long word sequence, instead of conditioning on all previous words, it is common to approximate the probability by conditioning only on the last words. That is:

Neural network Architecture

The neural probabilistic language model builds on the n-gram approximation and proposes a way to

• Jointly learn word feature vector (each word in the vocabulary has a feature vector — a real-valued vector in ) and
• Learn the probability of the sequence of words in terms of sequence of word feature vectors

The objective is to learn a model that predicts the probability of the next word given the previous words, i.e.

The model is subject to the following constraints:

• For any sequence of words, the model outputs a non-zero probability, i.e.
• The sum of probabilities over all possible next words in the vocabulary equals 1, i.e.

where is the vocabulary size, and indexes over all possible words in the vocabulary.

Note :

• Non-zero probability: Ensures that the model never completely rules out any word as a possible next word, allowing it to adapt to all possible word sequences and avoid zero-probability issues during training.

• Probabilities sum to one: Guarantees that f defines a valid probability distribution over the vocabulary for the next word, so the total probability of all possible next words is exactly 1.

The estimation of the function is done as follows :

• for any word in the vocabulary , lookup a real vector
• a function maps an input sequence of feature vectors for words in the context, to a conditional probability distribution over words in for the next word

Model

The neural network model can be expressed as:

where:

• is the concatenated input feature vector of the previous words, with dimension .
• is a weight matrix of size , which transforms the input into the hidden layer space.
• is a bias vector for the hidden layer, of dimension .
• is a weight matrix of size that maps the hidden layer activations to the output layer, where is the vocabulary size.
• is a weight matrix of size that connects the input directly to the output layer.
• is the bias vector for the output layer, of dimension .
• is the output vector containing the unnormalized log-probabilities (scores) for each word in the vocabulary, of dimension .

Using softmax to convert the output vector into a probability distribution over the vocabulary,

Using softmax layer ensures the constraints defined earlier:

• All probabilities are positive, satisfying the constraint.
• The probabilities sum to one across all possible next words, satisfying the normalization constraint .

Loss function

The maximum likelihood estimate for selecting the target word over all the words in vocabulary is equivalent to minimising the negative log likelihood,

where,

is multiple word sequence examples

As can be seen in the section on Loss for Multiclass classification ^{(refer post on Gradients for Multiclass classification with SoftMax)}, the negative log likelihood is indeed the Categorical Cross Entropy Loss.

Python code

The training of a Neural Probabilistic Language Model in PyTorch involves a few key components, each corresponding to the mathematical elements discussed earlier:

• torch.nn.Embedding — implements the word feature vector lookup function . Each word index in the vocabulary maps to a dense vector in .
• torch.nn.Linear — implements the fully-connected (dense) layers, corresponding to the transformation matrices , .
• torch.nn.Parameter – the parameters and are explicitly created.
• torch.nn.functional.log_softmax — applies the SoftMax in log space to obtain while maintaining numerical stability.
• torch.nn.NLLLoss — implements the Negative Log Likelihood Loss, which directly minimises for the correct target word index.

These functions, combined with an optimizer such as torch.optim.SGD or torch.optim.Adam, form the complete training loop for the model.

code @ word_embeddings/neural_probabilistic_language_model.ipynb
The training loop implementing the model for a simple toy example of 20 sentences shows that the model is doing reasonable in predicting the probability of next word.

Hierarchical Softmax (Morin & Bengio 2005)

Reference : Hierarchical Probabilistic Neural Network Language Model, Morin & Bengio (2005)

As computing of the probability of all tokens using SoftMax scales with vocabulary size , in the paper Hierarchical Probabilistic Neural Network Language Model, Morin & Bengio (2005) proposed an approach to reduce the complexity from to .

Based on the intuition shared in the paper Classes for Fast Maximum Entropy Training, J Goodman 2001, to compute , instead of directly computing the probability of the target word given the context words , we decompose it hierarchically as product of :

• : probability of in class given context
• : probability of word , given is in class AND context

i.e

where,

• : the target word we want to predict (e.g., “dog”).
• : the context (the surrounding words or features used to predict the next word, e.g., “the big”).
• : the cluster/class that the target word belongs to (e.g., dog → Noun class).

Derivation

To derive the the decomposition of , let us introduce a class variable , i.e. the word belongs to the class .

Then the probability of can be written as the sum of is in the class or not

Since each word belongs to exactly one class, the term is zero.

Hence,

The term can be expanded using the chain rule of conditional probabilities as follows:

Summarizing,

Thus, computing reduces to first predicting the class given the context and then predicting the word within that class conditioned on .

Complexity

With this approach, instead of computing probability over the entire vocabulary , this is broken down to computing the probability over the classes, and then computing the probability over the words within the chosen class.

Taking the example shared in the paper, assuming that is 10000 words, and we break it down into 100 classes, with each class having 100 words. Then the computations needed are:

• Finding probability over 100 classes
• Finding probability over 100 words in the chosen class

This reduces the computation to ~200 probability calculations instead of 10000 in the flat structure. Equivalently, the complexity reduces from to operations.

Binary Tree

An alternative to class-based grouping is to arrange the vocabulary words as the leaves of a binary tree. Each internal node corresponds to a binary decision (left or right child), and each leaf corresponds to one word in the vocabulary. This hierarchical arrangement reduces the search complexity from to , making it efficient for large vocabularies.

For constructing the binary tree, multiple approaches are possible :

• Perfect binary tree
  • Requires the leaves to be a power of 2 (for eg, 2, 4, 8, 16 etc).
  • If is not a power of 2, some leaves will remain unused
  • To reach every word, it takes the same path length i.e .
  • Average depth: exactly since all leaves are at the same level.
• Balanced binary tree
  • Tries to keep the left and right subtrees of equal size.
  • When the vocabulary is not a power of 2, leaf depths differ by at most 1.
  • No empty leaves; every leaf corresponds to a word.
  • Average depth: approximately , often slightly smaller because some leaves are shallower.
• Word frequency based tree
  • Constructed using a Huffman coding structure, frequent words are placed closer to the root node while rare words are deeper.
  • This minimises the average number of binary decisions required to reach a word.
  • Average depth: depends on the frequency distribution; it is minimised and typically much smaller than for natural language vocabularies (due to Zipf’s law).

For a toy corpus of 12 words, construction of the binary tree with the above approaches is shown below. code @ word_embeddings/binary_tree.ipynb

Model

The probability of the next word given the context can be written as:

where,

• each word is represented by a bit vector
• the path p depends on the position of the word in the binary tree.

For example, if each word is represented by 4 bits, then the probability of predicting the next word given the context becomes:

Taking log on both sides converts the product into a summation:

In general, for a word represented with bits:

The bit vector corresponds to the path (left or right at each nodes) starting from the root node to the leaf node (the word). Each internal node outputs a probability of going right ( ). For the true label , the binary cross-entropy loss at that node is:

The total loss for predicting is the sum of the node losses along the path:

where

• is the predicted probability at the j-th node along the path.
• denotes the binary choice (0 or 1) at the j-th internal node along the path to word .

This is equivalent to the negative log-likelihood of the full word probability.

Binary Node Predictor

Each internal node of the binary tree acts as a logistic classifier that decides left vs right, based on both the (n−1)-gram context and the node embedding. The conditional probability of taking the binary decision at a node, given the past context, is modelled as:

where,

• the sigmoid function is .
• for any word in the vocabulary , lookup a real vector
• : concatenation of the previous (n−1) word embeddings,
• : bias term specific to the node,
• : projection vector applied after hidden nonlinearity,
• : bias for hidden layer,
• : weight matrix projecting context to hidden space,
• : weight matrix projecting node embedding,
• : embedding vector for the current node,

The matrices , , (projection vector) and the bias are common parameters shared across all nodes.

Each internal node has its own (scalar bias), and (node embedding). These take care of the decision boundary at each internal node.

Python code – Naive implementation using for-loops

For the toy corpus, naive implementation of hierarchical softmax using for-looops is provided.

1. Defined a toy corpus of 20 sentences which has around 42 words.
2. Training example is constructed as 3 context words and the corresponding target word
3. Constructed a balanced binary tree, which has 41 internal nodes
4. Model defined with the binary node predictor for each of the nodes
   • The parameters , , (projection vector) and the bias are shared across all nodes.
   • Each internal node has its own and parameter
5. For each target word in the training example, the path to the leaf node via the tree is known
6. Using the binary decision at each path, the loss for each example is computed
7. The loss is back propagated to find the parameters which minimizes the loss

Using the trained model, for finding the probabilities for top-k words given the context words,

• For each word in the vocabulary find the path to its leaf node
• Starting from the root node, find the probability at each node
• Based on the known decision (right vs left) at each node, use either p for going right OR (1-p) for going left
• The joint probability is the product of probabilities at each node.
• For numerical stability (loss of accuracy when many small probabilities are multiplied), log of probabilities is found and then summed
• On the final log probability is exponentiated to get back in probability (optional)
• Then the top-k candidate words are printed

code @ word_embeddings/hierarchical_probabilistic_neural_language_model.ipynb

Python code – Vectorized implementation

As one can imagine, using the for loops significantly slows down the training. To form a vectorized implementation, the following was done.

1. Path preparation
   • Assign a unique id to every internal node in the binary tree.
   • Precompute for each word:
     • sequence of node-ids on the path to its leaf,
     • binary decision targets at each node.
   • Pad all paths to a fixed length using a dummy (UNK) node id. Build a mask to ignore padded positions.
2. Parameter lookup
   • Use torch.nn.Embedding to fetch node-specific parameters (biases) and (embeddings).
   • Shapes:
     • 
     • 
     • 
3. Forward pass (vectorized)
   • Context projection: and bias .
   • Node projection: using .
   • Broadcast: .
   • Nonlinearity : .
   • Projection: with .
   • Probabilities: .
4. Loss and masking
   • Binary cross-entropy is computed between and the decision targets, with mask applied to ignore padded nodes:
     • 
     • 

Notes :

• Compute once per batch and broadcast, instead of recomputing per path.
• UNK node parameters are trainable but excluded from loss using the mask.

code @ word_embeddings/vectorized_hierarchical_probabilistic_neural_language_model.ipynb

Noise contrastive estimation (Gutmann et al 2012, Mnih et al 2012)

As computing of the probability using SoftMax scales with vocabulary size , in the paper Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics, Gutmann et al 2012, provided an approach called Noise Contrastive Estimation (NCE). Instead of directly estimating the data distribution, NCE estimates the probability of a sample being from the data versus from a known noise distribution. By learning the ratio between the data and noise distributions, and knowing the noise distribution, the data distribution can be inferred.

This approach was extended to neural language models in the paper A fast and simple algorithm for training neural probabilistic language models A Mnih et al, 2012.

Model

In Neural Probabilistic Language model, the estimation of the probability of the words using SoftMax computation is,

where,

• context words is
• term in numerator is estimated using a neural model with parameters for the target word using the context words
• term in denominator is sum over all the words in the vocabulary i.e.

Let us define a set , which is the union of two sets , where

• the class label when the word is from the true target word distribution
• the class label when the word is NOT from the true target word distribution
• is the number of true (data) samples in the batch (or dataset)
• is the the number of noise samples generated for contrast

The formulation is,

• for each true (data) sample will draw noise samples from
• the model has to learn a binary classification where the sample is from the true distribution or from the noise distribution

Further, instead of computing the denominator term for normalzing to probabilities, learn it as a context dependent normalizing term, i.e.

The probability of sample coming from the true distribution given the context can be written as ,

Similarly, the probability of the word in noise distribution is,

Further,

Since NCE reframes the problem as a binary classification task (distinguishing true data from noise), the class labels are modelled as independent Bernoulli variables. Consequently, the conditional log likelihood is the sum of the binary cross-entropy terms:

For a single true target word and its corresponding noise samples

To evaluate this loss, need to express in terms of model parameters. Using Bayes Rule, the probability that the class is true given the context and target word is,

This gives the general probability for any word . When calculating the loss for a true target word, we substitute to get the positive sample probability

Converting to sigmoid form which is used in logistic regression,

Similarly, for the target word from noise distribution i.e. the probability that the class is noise given the context and target word is,

This gives the general probability for any word . When calculating the loss for a noise target word, we substitute to get the noise sample probability

Converting to sigmoid form which is used in logistic regression,

Plugging in the terms to the log likelihood for a single example,

To obtain the objective function for the entire dataset, sum the log-likelihoods over all true training examples . For each training example at step , we have a specific context , a true target word , and a fresh set of noise samples.

The final loss function that we minimize is the negative log-likelihood over the full dataset:

Note :
In the paper, A fast and simple algorithm for training neural probabilistic language models A Mnih et al, 2012, authors mention that approximating the learning of context dependent normalizing factor to 1 did not affect the performance of downstream tasks.

Noise Distribution

The noise distribution is typically chosen proportional to the unigram frequency of words in the corpus:

Often a smoothed unigram distribution improves results:

Python code

For the toy vocabulary, the code for Neural Probabilistic Language Model, Bengio et al, with the SoftMax head replaced with with Noise Contrastive Estimation (NCE).

The code @ word_embeddings/nplm_with_noise_contrastive_estimation.ipynb

Word2Vec papers (Mikolov et al, 2013)

In the paper, Efficient Estimation of Word Representations in Vector Space, Mikolov et al 2013. proposed architectures to reduce the computation complexity in learning word embeddings , with the intuition that simpler models enable training on much larger corpus of data.

Two architectures where proposed.

Continuous Bag of Words (CBOW) Model

When comparing with Neural Probabilistic Language Model, Bengio et al 2003, the following simplifications are proposed.

• order of context words is ignored
  • instead of concatenating embedding of previous words, averaging the word embeddings of surrounding words is proposed
  • this approach is called “bag-of-words” as the order is not taken into consideration
• no non linear hidden layer
  • the model uses a shared projection layer

Additionally, the in the model context including future words too.

Equations

The neural network output is :

where:

•  is the output weight matrix, mapping from hidden dimension  to vocabulary size 
•  is the averaged context embeddings.

The averaged context embedding vector  is computed as:

where,

• is the input embedding matrix
• is the embedding of the i-th context word, and
•  is the number of words to the left or right of the target word, giving a total context size of

The probability distribution over the vocabulary is obtained using the softmax function:

where:

•  is the predicted probability of word  being the target word.

•  is the score for word  from the output layer.
• The denominator sums the exponentiated scores over all vocabulary entries.

Continuous Skip-gram Model

The Skip-gram model, tries to predict context words given the current target word. The main idea is that each word is trained to predict the words surrounding it within a context window of size n.

• Input: one-hot encoding of the target word w_t
• Output: probability distribution over vocabulary for each context word
• No non-linear hidden layer: uses a shared projection matrix (linear)

Given a target word , the model tries to predict each surrounding context word for . The training goal is to maximize the probability of all context words around each target word:

Equations

The output score,

where,

• , where is the embedding vector for the word
• is the input embedding matrix
• is the output embedding matrix and
• 

The scores are computed for each context word, and the probability of all the context word is maximized.

For either CBOW or Skipgram, both and are trainable. After training, either one (or their average) is used as the word embedding.

Naive way for finding the probability is using SoftMax,

where,

• is the output word
• is score for output word
• denominator = normalizing constant over vocabulary

For finding the probability, hierarchical softmax is proposed in the paper.

Negative Sampling

In the paper, Distributed Representations of Words and Phrases and their Compositionality, Mikolov et al 2013 introduced two concepts:

• the speedup provided by sub sampling of frequent words helps to improve the accuracy of the less-frequent words
• simplified variant of Noise Contrastive estimation called Negative Sampling

The key intuition in Negative Sampling is that noise contrastive loss defined had terms to normalize the score to approximate the probabilities. However, to learn word embeddings the probabilities are not needed and the terms

can be ignored.

With this simplification, the negative sampling loss is,

Python code

For the toy vocabulary, finding word vectors with

a) Continuous Bag of words (CBOW) with negative sampling

The code @ word_embeddings/cbow_negative_sampling copy.ipynb

b) Skip Graph with Negative Sampling

The code @ word_embeddings/skip_gram_negative_sampling.ipynb

GloVe Embeddings ( Penning et al 2014)

In the paper GloVe: Global Vectors for Word Representation, Penning et al 2014, authors propose that ratio of co-occurrence probabilities capture semantic information better than co-occurance probabilities.

Let,

• be matrix of the word co-occurance counts
• be the number of times word occur in context of word .
• be the number of times any word appear in the context of word
• be the probability that word occur in context of word .

Authors show that on the 6 billion token corpus dataset,

Taking the ratio of co-occurance probabilities,

The ratios indicate that,

• solid and ice has a higher relationship than with steam.
• gas and ice is far less likely to co-occur than with steam
• water is related to both ice and steam in similar proportions

Model

To capture this ratio relationship in a vector space, the authors search for a function that satisfies:

where

• is context word
• are target words
• are the word vectors and
• are separate context vectors.

Authors enforce that the relationship should be linear (vector difference) and the result should be a scalar (dot product), leading to :

To satisfy that, authors propose choosing function so that the dot product of vector difference can be written as ratio of probabilities,

With this choice, for a single word-context pair estimates the co-occurence probabilities,

Taking logarithm,

Note :

The model capturing the relation between two words should not change even if the words are swapped. Even though the co-occurrence counts are identical (), because the total counts of words are not equal () , the conditional probability is not symmetric ().

The above equation is not symmetric if we swap target word and context word as the row-dependent term has to be handled.

To make it symmetric, the authors absorb into a learnable bias term and then adds a corresponding bias for the context word. This ensures the model is fully symmetric i.e.

The loss function then becomes ,

The key aspect in the above simplification is that, by training for the pairs of words to minimize the above loss will indirectly ensure that the dot product of vector difference of target words with context word will arrive at the ratio of probabilities.

Weighted Least Squares

The above loss function weighs all co-occurances equally. Authors noted that rare co-occurances are noisy and around 75-95% of the co-occurance is zeros, and proposed adding a weighting function to least squares loss proposed above.

The weighting function is chosen to obey the following :

1. (to handle the zero co-occurance counts)
2. should be non-decreasing so that rare co-occurance are given less weight
3. should be relatively small for large values of so that frequent co-occurrences are not over-weighted

The parameters and are chosen empirically.

Then the Weighted Least Squares loss function becomes,

Python code

The code @ word_embeddings/glove_word_embedding.ipynb

Summary

This article covers

Evolution: How we moved from Bengio’s NPLM (2003) to efficient architectures like Word2Vec and GloVe.

Math: Detailed derivations of Hierarchical Softmax (using binary trees) and Noise Contrastive Estimation (differentiating data from noise).

Architectures: A deep look at CBOW, Skip-Gram, and the intuition behind Negative Sampling.

Code: Complete Python implementations for every model discussed, including vectorized implementations for efficiency.

Acknowledgment

In addition to the primary papers listed above, this post draws inspiration from the excellent overview in the post Learning word embedding, Weng, Lilian 2017. Credit also goes to the recent Large Language Models Gemini and ChatGPT which helped to bounce thoughts and refine the drafts.

The post Word Embeddings using neural networks appeared first on DSP LOG.

Next, the loss function using categorical cross entropy is explained and derive the gradients for model parameters using the chain rule. The analytically computed gradients are then compared with those obtained from the deep learning framework PyTorch. Finally, we implement a training loop using gradient descent for a toy multi-class classification task with 2D Gaussian-distributed data.

As always, contents from CS229 Lecture Notes and the notations used in the course Deep Learning Specialization C1W1L01 from Dr Andrew Ng forms key references.

Model

Let us take an example of estimating based on feature vector having features i.e. and there are examples.

Linear Layer

Let us assume that the variable is defined as linear function of . For a single training example, this can be written as :

where,

• is the vector of size i.e. ,
• is the parameter matrix of size i.e. ,
• is the feature vector of size i.e. and
• is the parameter vector of size i.e.

Note :

This is the definition of Linear layer in PyTorch ^{(refer entry on Linear layer)}. This is alternatively called as Dense Layer in Tensorflow ^{(refer entry on Dense)} and as Fully Connected layer in deep learning literature.

Softmax layer

To map the real valued vector to a probability vector with elements of summing up to 1, we use the softmax function ^{(refer wiki entry on SoftMax)} . Softmax function is defined as,

Equivalently, this can be written as,

where, each represents the normalized exponential of the corresponding . This ensures that

• each element lies in the range [0,1] i.e.
• sum of all the elements add upto 1, i.e. .

This makes interpretable as a probability distribution over the classes.

Derivatives

Derivative of Softmax layer

To compute the derivative of the softmax output with respect to its input , we need to find the Jacobian matrix . The Jacobian contains all partial derivatives of each output component with respect to each input component .

To find the derivative for all cases, let us split into two scenarios i.e.

Derivative for case i=j

Using the product rule of derivatives,

Derivative for case i ≠ j

Final output (matrix form)

Based on the above derivations, the derivative is defined as :

In matrix form,

Code

Python code comparing the derivative of softmax using the derivation above vs computed by PyTorch autograd function below.

Derivative of Linear layer

To find the derivative of the linear layer , with respect to parameters and , we must compute two partial derivatives:

• – how the output changes with respect to the weight matrix.
  
• – how the output changes with respect to the bias vector.
  

Derivative of Weights

To compute the derivative , we evaluate how each weight parameter affects each output dimension . The i-th component of is:

.

The partial derivative of with respect to is :

where,

• index over the output vector
• indexes the elements of the input vector

Since each output depends only on the weights in i-th row , the Jacobian simplifies to a matrix where each row is . This can be represented as

For all the rows of , the derivative is

Derivative of Bias

The bias vector is added element-wise to the output of the linear transformation . That is, each output component is given by:

So the partial derivative of with respect to is:

This implies that the Jacobian matrix of with respect to is an identity matrix:

This tells us that the bias only affects its corresponding output component (i.e., only affects ).

Loss for multi-class classification

Maximum Likelihood Estimate

The likelihood of observing the true class c, given input , under the model is:

The log-likelihood over a dataset with examples is:

where,

is the model’s predicted probability for the correct class for the i-th example.

Maximizing this log-likelihood is equivalent to minimizing the negative log-likelihood:

Connecting to Cross Entropy Loss

To map the ground truth class label to be represented as a target vector , a common choice is the one-hot encoding scheme, where the true class is indicated by a 1 in the corresponding position and 0 elsewhere. For example, suppose we have classes, and the correct label is class 2, i.e., , then the one-hot encoded vector becomes :

Cross Entropy

To compare the model’s predicted probability vector with the one-hot encoded true label , we use a metric called cross-entropy ^{(refer wiki entry on Cross Entropy)}. The cross-entropy of the distribution  relative to a distribution over a given set is defined as follows:

where,

is the expected value operator with respect to the distribution .

For discrete probability distributions and  with set of all possible outcomes or classes.

Cross Entropy Loss

In the context of training classification models, we use the cross-entropy loss as a cost function to minimize. For a single training example, to evaluate how well the predicted probability vector matches the ground truth vector , the cross-entropy loss is defined as:

where,

• is the true probability of class i and
• is the predicted probability for class i.

The loss encourages the model to assign higher probability to the correct class which indirectly lowers the probabilities to the incorrect classes. The smaller the cross-entropy loss, the closer the predicted probabilities are to the true labels.

Loss across all examples is,

When is one-hot coded, as only the correct class is non-zero, the equation reduces to

We can see that this cross entropy loss is same as the maximum likelihood estimate derived earlier.

Note :

• Function for cross entropy loss is available in PyTorch library as torch.nn.CrossEntropyLoss ^{(refer entry on CELoss in PyTorch)}.
• In the torch.nn.CrossEntropyLoss definition, we only need to provide the output of the linear layer (called logits) and the class indices as an integer. The softmax and logarithm of probabilities are computed internally, so we do not need to apply softmax before passing logits to this function.

Gradients with Cross Entropy (CE) Loss

The system model for binary classification involves multiple steps:

• firstly, the vector is defined as linear function of using parameters and ,
• then gets transformed into a estimated probability score using softmax function.
• lastly, using the true label and estimated probability score , cross entropy loss is computed

For performing gradient descent of the parameters, the goal is to the find the gradients of the loss w.r.t to the parameters and . To find the gradients, we go in the reverse order i.e.

• first, gradients of the loss w.r.t to the estimated probability score , is computed.
• then gradients of the probability score w.r.t to the output of linear function is multiplied with the gradients of loss with respect to i.e.
• lastly, to find the gradients of output of linear function w.r.t to parameters and , the product of all the individual gradients is used. This is written as,

The steps described, calculating gradients in the reverse order from the loss back to the parameters is an application of the chain rule from calculus ^{(refer wiki entry on Chain Rule)}. This method is the foundation of back propagation used in training models ^{(refer wiki entry on Backpropagation)}.

Gradients of Loss with respect to Probability (dL/da)

As defined earlier, for a multi-class classification setting, the cross-entropy loss is given by:

Derivative of w.r.t is,

So, the gradient is large if the predicted probability is small for the correct class — this penalises the model for incorrect predictions, which is desired during training. The vectorized form of the loss gradient w.r.t. the probability vector is:

Equivalently,

Gradients of Loss with respect to z (dL/dz)

Using chain rule, to the find the gradient of loss with respect to z i.e. , we multiply the derivative of softmax output which is a matrix with which is of dimension ,

In vectorized form, can be represented as

Gradients of loss with respect to Parameters (dL/dW, dL/db)

Gradients of Weights (W)

Based on the chain rule, to find the gradient of loss with respect to parameter , we multiply each row of the with the corresponding row from

This is equivalent to the outer product,

Gradients of bias (b)

Recall the linear transformation: . The gradients are:

The intuition from above equations is :

if the estimated probability is close to the true value then the gradient is small, and the update to the parameters is also correspondingly smaller. If you recall, the gradients for binary classification ^{(refer post on Gradients for Binary Classification with Sigmoid)}, linear regression ^{(refer post on Gradients for Linear Regression)} follows a similar intuitive explanation.

These gradients are then used in the optimizer (e.g., SGD) to update parameters and reduce the loss.

Vectorised operations (with m examples)

The training examples each having features is represented as,

The output, which is a probability matrix across classes for each of the examples, is:

The linear transformation before applying the activation function (e.g., softmax) is given by:

where, the parameters

• and
• 

The softmax activation is applied column-wise to the matrix to obtain the probability outputs:

In matrix form, this is written as,

The cross-entropy loss compares the predicted probabilities with the ground truth one-hot encoded labels :

The derivative of the cross-entropy loss with softmax activation, with respect to the input (logits), simplifies to:

The gradient of the loss with respect to the weight matrix is:

As the input matrix has shape , the inner product results in a matrix of shape . This captures the total gradient of the loss over all examples. Averaging over the examples is done by multiplying with .

The gradient of the loss with respect to the bias vector is computed by summing the gradient over all examples using a row vector of ones:

Here, and sums the gradients across all examples. The result is a vector, which matches the shape of .

Code (gradients)

Example code comparing the gradients computed using the derivation with autograd from PyTorch.

Training for toy example with 3 classes

Below is an example of training a multi class classifier based on the model and gradient descent. Synthetic training data data is generated from two independent Gaussian random variables with zero mean and unit variance. Mean is shifted by (-2,-2), (+2,+2 ), (-2,+2 ) corresponding to class 0, class 1, class 2 respectively.

The training loop is done using the numerically computed gradients and using the torch.autograd provided by PyTorch, and can see that both are numerically very close.

Training with Label Smoothing

In the previous section, we derived the gradients for multi-class classification using one-hot encoded targets. In the paper “Rethinking the Inception Architecture for Computer Vision” by Szegedy et al. (2016) ^{(arXiv:1512.00567)}, the idea of label smoothing was introduced. The key observation is that one-hot targets, which drives the predicted probability for the correct class toward 1 and ignore the other classes in the loss function, encourage models to become overconfident.

Label smoothing combats this by replacing the hard 1 in the true class with a slightly lower value, such as , and distributing the remaining equally among the other classes. So, instead of teaching the model that one class is absolutely correct, we teach it that one class is very likely correct — allowing for some uncertainty.

For a classification problem with classes and smoothing parameter , the smoothed label vector becomes:

For an example with =4 classes,

Even though we modify the target labels using label smoothing, the sum of the smoothed probabilities still adds up to 1. Because of this, the gradient derivations from the previous section remain valid.

Training code

For the toy training example earlier, we compare the training with smoothed labels vs one-hot coded. In PyTorch function torch.nn.CrossEntropyLoss ^{(refer entry on CELoss in PyTorch)} has an optional argument label_smoothing which implements the label smoothing as defined earlier.

In the training results on the toy example we can see that the loss is higher for the training with label smoothing and correspondingly misclassification rate is also slightly higher.

However, label smoothing has been shown to improve generalization in larger models trained on complex datasets. The concept was first introduced in Rethinking the Inception Architecture for Computer Vision (Szegedy et al., 2016), and was later used in the foundational paper Attention is All You Need (Vaswani et al., 2017). A broader study, When Does Label Smoothing Help? (Müller et al., 2019), analyzed its effectiveness in large models like ResNets and Transformers.

Summary

The post covers the following key aspects

• System model for multi class classification with linear layer and softmax
• Loss function based on categorical cross entropy and showing that this is Maximum Likelihood Estimate
• Computation of the gradient based on chain rule of derivatives
• Vectorized Operations for batch of examples which implements computations using efficient matrix and vector math.
• Training loop for the classification using both manual and PyTorch based gradients
• Explains the concept of label smoothing and implements a training loop for explaining the concept

Have any questions or feedback? Feel free to drop your feedback in the comments section.

The post Gradients for multi class classification with Softmax appeared first on DSP LOG.

In this post, the intuition for loss function for binary classification based on Maximum Likelihood Estimate (MLE) is explained. We then derive the gradients for model parameters using the chain rule. Gradients computed analytically are compared against gradients computed using deep learning framework PyTorch. Further, training loop using gradient descent for a binary classification problem having two dimensional Gaussian distributed data is implemented.

As always, contents from CS229 Lecture Notes and the notations used in the course Deep Learning Specialization C1W1L01 from Dr Andrew Ng forms key references.

Model

Let us take an example of estimating based on feature vector having features i.e. .

There are examples.

Let us assume that the variable is defined as linear function of . Then gets transformed into a probability score using sigmoid function. For a single training example, this can be written as :

where,

• is the feature vector of size i.e. and
• is a scalar

To convert the real number to a number lying between 0 and 1, let us define

where, is the sigmoid function ^{(refer wiki entry on sigmoid function})

Sigmoid function and its derivative

Sigmoid function which has a smooth S-shaped mathematical function is defined as:

which has the properties

The derivative of sigmoid is,

From the plots of derivative of sigmoid, two key observations :

• Vanishing gradients : for very large or very small , the derivative approaches 0 causing gradients to vanish during back propagation — this slows or stalls learning in deep networks.
• Low Maximum Gradient : the maximum value of derivative is 0.25, which caps the gradient flow, making it harder for deep layers to effectively update their weights

As mentioned in the article Yes you should understand backprop by Andrej Karpathy, these aspects have to be kept in mind when using sigmoid for training deeper neural networks.

Loss function for binary classification

Maximum Likelihood Estimation

Let us assume that the probability of output being 1, given input and parameters , is,

Then, for the binary classification, the probability of output being 0 is,

Since can either be 0 or 1, we can compactly write the likelihood as:

The likelihood function is the probability of the actual label given the prediction . When the multiple independent training examples are independently and identically distributed (i.i.d.), the total likelihood for the dataset is the product of the likelihoods for each example. With this assumption, for training examples, the likelihood for the parameters and is,

Log Likelihood

To avoid the product of many small numbers, we take the natural logarithm of the likelihood function. The log-likelihood for the entire dataset is the sum of the log-likelihoods for each example:

Negative Log Likelihood

Since optimizers like gradient descent are designed to minimize functions, we minimize the negative log-likelihood instead of maximizing the log-likelihood.

Averaging the Loss

Averaging the loss ensures that the total loss remains on the same scale, regardless of the size of the training dataset. This is important because it allows the use of a fixed learning rate across different dataset sizes, leading to more stable and consistent optimization behaviour.

The averaged negative log-likelihood is defined as:

This expression is known as the Binary Cross-Entropy (BCE) Loss, which is widely used in binary classification tasks. This function is available in PyTorch library as torch.nn.BCELoss ^{(refer entry on BECLoss in PyTorch)}.

Gradients with Binary Cross Entropy (BCE) Loss

The system model for binary classification involves multiple steps:

• firstly, the variable is defined as linear function of using parameters , .
• then gets transformed into a estimated probability score using sigmoid function.
• lastly, use the true label and estimated probability score , binary cross entropy loss is computed

For performing gradient descent of the parameters, the goal is to the find the gradients of the loss w.r.t to the parameters and . To find the gradients, we go in the reverse order i.e.

• firstly, gradients of the loss w.r.t to the estimated probability score
• then gradients of the probability score w.r.t to the output of linear function
• lastly, gradients of output of linear function w.r.t to parameters ,

Then the product of all the individual gradients from the gradients of loss w.r.t to the parameters. This is written as,

The steps described, calculating gradients in the reverse order from the loss back to the parameters is an application of the chain rule from calculus ^{(refer wiki entry on Chain Rule)}. This method is the foundation of backpropagation used in training models ^{(refer wiki entry on Backpropagation)}.

Deriving the gradients

For simplicity, take a single example and computing gradients step by step,

Step1 : Gradients of loss w.r.t to probability score

With the loss , then the derivative of loss w.r.t to sigmoid output is,

Step2 : Gradients of probability score w.r.t to output of linear function

With as the output of sigmoid function, the derivative is

Step3 : Gradients of output of linear function w.r.t to parameters

With , the derivative is,

Similarly,

Gradients of loss w.r.t to parameters

Taking the product of the gradients from all the steps,

Similarly,

The intuition from above equations is :

if the estimated probability is close to the true value then the gradient is small, and the update to the parameters is also correspondingly smaller. If you recall, the gradients for linear regression ^{(refer post on Gradients for Linear Regression)} follows a similar intuitive explanation.

Note : With training examples the loss is averaged, and this becomes :

Vectorised operations

The training examples each having features is represented as,

The output is,

The parameters and represented as,

where,

• is the feature vector of size i.e. and
• is a scalar

The output is,

Gradients,

The gradient w.r.t to can be represented in matrix operations as,

Similarly, for the bias term

Gradients computed numerically vs PyTorch

Training – Binary Classification

Below is an example of training a binary classifier based on the model and gradient descent. Synthetic training data data is generated from two independent Gaussian random variables with zero mean and unit variance. Mean is shifted on half the samples by (-2,-2) and the remaining half by (+2,+2 ) corresponding to class 0 and class 1 respectively.

The training loop is done using the numerically computed gradients and using the torch.autograd provided by PyTorch, and can see that both are numerically very close.

The estimated probability score indicates the likelihood that the given input corresponds to one of the classes. As can be seen in the plot Predicted Probability for Each Input, inputs close to center point (0,0) have a probability close to 0.5, and as we move away from the center the probabilities tend to be closer to either 0 or 1.

To convert this probability into a class label, a decision threshold needs to be applied. In this example, as can be seen in the plot of Classification Error vs Threshold, the threshold of 0.5 is corresponding to the lowest error rate.

However, there are other scenarios where the threshold of 0.5 can be inappropriate – like dealing with imbalanced datasets, skewed class distribution etc. These require adjusting the threshold for better performance.

Summary

The post covers the following key aspects

• Loss function based on Maximum Likelihood Estimate
• Computation of the gradient based on chain rule of derivates
• Vectorized Operations Implements all computations using efficient matrix and vector math.
• Training loop for the binary classification using both manual and PyTorch based gradients

Have any questions or feedback on the gradient computation techniques? Feel free to drop your feedback in the comments section.

The post Gradients for Binary Classification with Sigmoid appeared first on DSP LOG.

The gradients computed analytically are compared against gradient computed using deep learning framework PyTorch. Further, using the gradients, training loop using gradient descent is implemented for the simplest example of fitting a straight line.

As always, contents from CS229 Lecture Notes and the notations used in the course Deep Learning Specialization C1W1L01 from Dr Andrew Ng forms key references.

Model

Let us take an example of estimating based on feature vector having features i.e. .

There are examples.

Assume that the estimate is as linear function of .

For a single training example, this can be written as :

where,

• is the feature vector of size i.e. and
• is a scalar

Least Mean Squares

To find the parameters and , based on training examples, need to formalise a metric to quantify the “closeness” of the estimate to the true value . As an arbitrary choice, let us define a metric based on the mean square error (MSE) as,

Goal is to find the parameters and which minimizes the metric . This can be considered as ordinary least squares (^{wiki entry on ordinary least squares}) model.

To find the value of parameters and which minimises the metric , let us try gradient descent method where we

i) start with initial random values of parameters and

ii) repeatedly update parameters simultaneously for all values of and

where,

is the learning rate,

and are the partial derivatives of the loss metric over parameters and respectively.

The intuition is, to take repeated steps in the opposite direction of the gradient (or approximate gradient) of the function at the current point, because this is the direction of steepest descent ^{Wiki Article on gradient descent}.

Gradients

In this formulation, we need to find the derivative of a scalar i.e. loss over the a vector of parameters of and .

For easier understanding, can define the derivative over each parameter as below,

Further, taking only one training example, the loss is

Taking the derivative w.r.t to first parameter

Similarly, for the parameter of , the gradient is

For the bias parameter , the gradient is

The intuition from above equations is :

if the estimate is close to the true value then the gradient is small, and the update to the parameters is also correspondingly smaller.

With training examples the loss is averaged, and this becomes :

Vectorised operations

Vectorised operations allow CPUs/GPUs to do SIMD (Single Instruction Multiple Data^{(Refer Wiki)}) processing, making it much faster than using for-loops.

Inputs & Outputs

In the current example, this translates to the parameters and represented as,

respectively.

The training examples of features is represented as

The output

Gradients

The gradient w.r.t to can be represented in matrix operations as,

Similarly, for the bias term

Training

Training loop – using the derivatives

The code for linear regression using the gradients descent defined in the previous section.

Computing Gradients

Using PyTorch

For the simple linear regression example, it is relatively straight forward to derive the gradients and perform the training loop. When the function for estimation involves multiple stages/layers a.k.a deep learning ^{(refer wiki)}, it becomes harder to derive the gradients.

Popular deep learning frameworks like Pytorch provides tools for automatic differentiation ( torch.autograd ^{refer pytorch entry on autograd} ) to find the gradients of each parameter based on the loss function.

Numerical approximation (finite difference method)

To verify the gradients, derivatives can be computed numerically using using finite difference ^{(refer wiki entry on finite difference)} method i.e.

where,

is the true derivative of function and

is a small constant.

Example – Analytic vs PyTorch vs Numerical Approximation

For the toy example below, can see that the gradients computed by Analytically vs PyTorch vs numerical approximation using finite difference methods are matching.

Training Loop – using PyTorch

Key aspects in the code for implementing the training loop using PyTorch :

• the variables are defined as torch tensors ^{refer pytorch article on tensors}.
  • Tensors are similar to numpy ndarrays, with capabilities to use GPU/hardware accelerators, optimized for automatic differentiation etc
• defining the parameters needing gradient computation.
  • the parameters and which needs gradient computation are initialised with requires_grad=True
• computing the gradient
  • the call loss.backward() is used to compute the gradients for the parameters and .
  • this makes the gradient values available in w.grad() and b.grad() respectively
• updating the paramaeters
  • as gradient tracking is unnecessary during parameter updates, they are performed within torch.no_grad(): context
• zeroing gradients between calls
  • PyTorch accumulates gradients by default during each backward pass i.e. each loss.backward() call
  • so, performing w.grad.zero_() and b.grad.zero_() is needed to clear previous gradients.

As would expect, both the training loop approaches converges to similar values for parameters and .

Mean Absolute Error

Another popular metric to quantify the “closeness” of the estimate to the true value is Mean Absolute Error (MAE). In the cases where there are outliers in the data, Mean Absolute Error (MAE) is preferred over Mean Squared Error (MSE) as MAE penalizes errors linearly rather than quadratically.

Formally,

For computing the gradient for the loss from Mean Absolute Error, need to find the gradient of absolute function.

Gradient – Absolute function

The absolute value of function is defined as,

The derivative is

This can be compactly written as,

The absolute function is non-differentiable at point at , where the function has a sharp corner.

The concept of subderivative (or subgradient) generalises the derivative to a convex functions which are not differentiable ^{(refer wiki entry on Subderivative)} . With this definition, subderivative at lies in the interval .

Using the concept of Symmetric derivative ^{(refer wiki entry on symmetric derivative)}, the subderivtive at can be chosen as 0.

In practice, deep learning frameworks (like PyTorch, TensorFlow) and numerical methods like NumPy define . This is the subgradient, and it works fine in optimization.

Training

Deriving the Gradients

For a single training example, for the parameter of , the gradient is

Similarly for the bias term,

Training Loop – using derivatives and PyTorch

For the same example, the code for training the linear regression using Mean Absolute Error as the Loss function.

Can see that both the training loops for Mean Absolute Error (MAE) using PyTorch and Analaytic approaches converges to the same parameters and .

Summary

The post covers the following key aspects

• Gradient Basics: How to deriving the gradients for loss functions Mean Square Error and Mean Absolute Error
• Efficient Computation: Use of vectorized operations and PyTorch autograd
• Gradient Computation: Analytical, numerical (finite difference), and PyTorch comparison
• Training Loops: Implementing updates using both manual and PyTorch-based gradients

Have any questions or feedback on the gradient computation techniques? Feel free to drop your feedback in the comments section.

The post Gradients for linear regression appeared first on DSP LOG.

One particular issue which I faced was frequent crashing of MySQL due to memory limitations. Followed few online instructions to improve the situation and the current configuration seems to be holding up (but this is a cause of worry – need to figure the right solution).

Anyhow, hope you like the decreased page load time!

Some helpful links from the web:

a) How to install WordPress on Amazone EC2

b) Move WordPress site from shared hosting to Amazon EC2

c) DIY: Enable CGI on your Apache server

d) Import MySQL Dumpfile, SQL Datafile Into My Database

e) Making WordPress Stable on EC2-Micro

f) how to enable mod_rewrite in apache2.2 (debian/ubuntu)

The post Migrated to Amazon EC2 instance (from shared hosting) appeared first on DSP LOG.