# Online Batch Selection for Enhanced Generalization in Imbalanced Datasets
## 3 Methodology
### Noisy BSBS  
Apart from re-enters, \(BSBS\) can be improved regarding generalization in another way. As mentioned in Section 2, one of the problems of extreme imbalanced datasets is the limited variety of minority samples. This makes it difficult for the network to learn a distribution close to the ideal. Inspired by algorithms, such as SMOTE [4], as well as techniques such as augmentation [39; 40; 41], which are often used in deep learning, we propose _Noisy BSBS_, another variant to the main algorithm. _Noisy BSBS_ revolves around adding noise to a part of the features of the samples in order to artificially construct new samples for the training. The algorithm, at first, creates a random noise mask, \(M_{i}\), for each sample, consisting of \(\{0,1\}\), with equal probability for both. This mask designates the features of each sample in which noise will be added. Therefore, there is a 50% chance that a feature will become noisy or left as it is. The reason for this probabilistic noise is that we do not want the model to learn a steady noise and risk the chance of overfitting to it. The type of noise that is used is following a normal (Gaussian) distribution with zero mean and standard deviation equal to 0.2. However, the noise is not added to the whole dataset. We select the \(LL^{\prime}\) set before the swaps to be the noisy set. As a result, the final trainset for each epoch is the noisy \(LL^{\prime}\) set and the clean \(HL\) set. This can be written in the following form:  
\[X_{t}=Noisy(LL^{\prime})\cup HL. \tag{5}\]The idea behind the choice of that particular set was to force the network to learn both the original and the noisy version of the difficult samples (\(HL\) set). In this way, we increase the diversity of the difficult samples. Not only that, but, adding noise to the medium difficulty samples (samples that do not belong neither in \(LL\) nor in \(HL\)) increases the probability to find another hard sample. However, finding hard samples from noisy data might imply some danger. The noisy sample might not resemble a realistic instance of the problem at hand due to the noise. This is why the amplitude of the added noise is very significant to the performance of the algorithm. Algorithm 3 presents _Noisy BSBS_ in detail. It is important to note that the two variants of _BSBS_ can work together. The combined version is called _Noisy BSBS with re-enters_, and both components work independently. This means that the \"noisy\" part still adds noise at the start of the epoch, while the \"re-enter\" part returns the most forgotten samples at the end of each epoch. To distinguish them better, the following abbreviations are introduced: _BSBS_ with re-enters will be _BSBS-R_, _Noisy BSBS_ will be _NBSBS_, and the combination of both will become _NBSBS-R_. In the following section, the performance of the three will be compared and analyzed. ```
Parameters: dataset \(D\), number of epochs \(T\), number of datapoints \(N\), batch size \(B\), loss momentum \(lm\), number of datapoints to be swapped \(k\), indexes of samples \(inds\), swapped times \(ST\), re-enter threshold \(E_{sw}\). Initializations:inds = [0,..., N - 1], \(lm\) = 0.7 for\(t=0\)to\(T\)do \(X_{t}=D[inds]\); for\(b=0\)to\(N/B\)do \(b\_inds\gets SelectBatch(X_{t},b)\) \(losses(b\_inds)\gets ForwardPass(X_{t}[b\_inds])\) \(UpdateWeights(losses)\) \(BL[b\_inds]=losses EMA[b\_inds]=lm*EMA[b\_inds]+(1-lm)*losses end \(r\_inds\gets select(ST\geq E_{sw})\) \(\mu=\frac{\sum_{i}BL_{i}}{N}\) \(BL[r\_inds]=\mu\) \(HL=\hat{H}_{k}(EMA)\) \(LL=\hat{L}_{k}(BL)\) \(inds=HL\cup LL^{\prime}\) \(ST[LL]+=1\) \(ST[inds]=0\)  end for
```  
**Algorithm 2**BSBS with re-enters  
```
Parameters: dataset \(D\), number of epochs \(T\), number of datapoints \(N\), batch size \(B\), loss momentum \(lm\), number of datapoints to be swapped \(k\), indexes of samples \(inds\), swapped times \(ST\), re-enter threshold \(E_{sw}\).