# Online Batch Selection for Enhanced Generalization in Imbalanced Datasets
## 3 Methodology
### Batch Selection with Biased Sampling  
An original version of the BSBS approach appeared in [3]. Training of a neural network can be formulated as a non-convex optimization problem aiming to minimize a loss function. Given a dataset, the optimization goal is to minimize the sum of the losses across all data samples. The training process usually consists of two steps that are repeated through a certain number of epochs:  
* Sampling a batch of samples according to a distribution \(P\)
* Applying the update with regard to the chosen optimizer algorithm (i.e., SGD)  
The algorithm batch selection with biased sampling focuses on the first step. At the end of each epoch, \(BSBS\) finds \(k\) samples with the lowest loss (easy examples) and swaps them out, replacing them with the \(k\) highest loss samples (difficult ones). Essentially, during each epoch, the model sees the hard samples twice while the easier ones none. Here, we are going to introduce some notation. Let \(X\) be the dataset, \(HL^{k}\subseteq X\) be the \begin{table}
\begin{tabular}{c c c} \hline \hline
**Methods** & **Advantages** & **Disadvantages** \\ \hline \multirow{2}{*}{Oversampling} & - More data useful for NNs & - Increases learning time \\  & - Can add synthetic data & - Preprocessing computational cost \\ \hline \multirow{2}{*}{Undersampling} & - Removal of redundant samples & \multirow{2}{*}{- Can discard useful data} \\  & - Less storage needed & \\ \hline \multirow{2}{*}{Cost sensitive learning} & - Better with larger datasets & - Difficult hyperparameter tuning \\ \hline \multirow{2}{*}{Online Sampling} & - Less preprocessing & \multirow{2}{*}{- Longer training time} \\  & - Scalable to very large datasets & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Advantages and disadvantages of all the methods in literature. highest-loss samples, and \(LL^{k}\subseteq X\) be the lowest-loss ones. Consequently, at each epoch, the trainset changes from the original \(X\), so it is better to refer to the trainset as \(X_{t}\) at the \(t\) epoch. The trainset can be written in the following form:  
\[X_{t}=(X-LL^{k}_{X_{t-1}})\cup HL^{k}_{X_{t-1}}=LL^{k^{\prime}}_{X_{t-1}}\cup HL ^{k}_{X_{t-1}}, \tag{1}\]  
with \(LL^{\prime}_{X_{t-1}}\) being the samples that do not belong in \(LL^{k}_{X_{t-1}}\). It is preferable to use the second part of the Equation (1) because it makes the implementation easier. However, to compute \(HL\) and \(LL\) accurately, an extra forward pass is needed at the end of each epoch. This creates a large overhead, which is quite time consuming. It was shown that a good approximation of those sets can be derived from the batch loss (\(BL\)), which is the loss obtained after each batch update. \(BL\) is not ideal because samples, which were selected in the initial batches of the epoch, might have a substantial difference in loss at the end of the epoch compared to the loss depicted in \(BL\). Nonetheless, because the algorithm only needs the \(k\) highest and lowest-loss samples and not the actual loss values, it is possible to take advantage of \(BL\), as shown in [3]. For the \(LL\) set, the lowest losses of \(BL\) are located and swapped out. For the \(HL\), an exponential moving average (\(EMA_{BL}\)) of \(BL\) is computed to find the highest losses. The \(EMA_{BL}\) can be written as:  
\[EMA_{BL_{t}}=lm*EMA_{BL_{t-1}}+(1-lm)*BL_{t}, \tag{2}\]  
with \(lm\in[0,1]\) being the momentum of the exponential moving average of batch loss (\(BL\)). Before writing the two sets in formulas, the notation of the \(k\) highest (or lowest) elements of a set will be introduced. Let \(S\) be a set with \(k\) or more elements. Then, the highest \(k\) elements of \(S\) will be noted as \(\hat{H}_{k}(S)\) and the lowest \(k\) elements of \(S\) as \(\hat{L}_{k}(S)\).