# Adaptive Learned Belief Propagation for Decoding Error-Correcting Codes
## 5 Adaptive Learned Message Passing Algorithms
### Parallel Decoders
To this end, a static WBP (with no parameter sharing) is trained offline given a dataset \(\{(\mathbf{y}^{(i)},\mathbf{c}^{(i)})\}_{i}\). The empirical cumulative distribution of the weights in each iteration is computed as an approximation to \(C_{t}(.)\). However, if the BER is low, it can be difficult to obtain a dataset that contains a sufficient number of examples corresponding to incorrectly decoded words required to obtain good generalization. To address this issue, we apply active learning [23; 83]. This approach is based on the fact that the training examples near the decision boundary of the optimal classifier determine the classifier the most. Hence, input examples are sampled from a probability distribution with a support near the decision boundary. The following approach to active learning is considered. At epoch \(e\) in the training of the WBP, random codewords \(\mathbf{c}\) and the corresponding outputs \(\mathbf{y}\) are computed. The decoder from the epoch \(e-1\) is applied to decode \(\mathbf{y}\) to \(\hat{\mathbf{c}}=\mathrm{WBP}(\boldsymbol{\tau},L(\mathbf{y}))\). An acquisition function \(A_{f}(\mathbf{c},\hat{\mathbf{c}}):\mathcal{C}\times\mathbb{F}_{2}^{n}\mapsto \mathbb{R}^{+}\) evaluates whether the example pair \((\mathbf{y},\mathbf{c})\) should be retained. A candidate example is retained if \(A_{f}(\mathbf{c},\hat{\mathbf{c}})\) is in a given range. The choice of the acquisition function depends on the specific problem being solved, the architecture of the NN, and the availability of the labeled data [83]. In the context of training the NN decoders for channel coding, the authors of [23] use _distance parameters_ and _reliability parameters_. Inspired by [23], the authors of [84] define the acquisition function using importance sampling. In this paper, the acquisition function is the number of errors \(A_{f}(\mathbf{c},\hat{\mathbf{c}})=\|\mathbf{c}-\hat{\mathbf{c}}\|_{H}=d_{H}( \mathbf{c},\hat{\mathbf{c}})\), where \(d_{H}\) is the Hamming distance. The dataset is incrementally generated and pruned as follows. At each epoch \(e\), a subset \(S_{e}=\{(\mathbf{y}^{(i)},\mathbf{c}^{(i)})\}_{i=1}^{\mathsf{b}_{1}}\) of \(\mathsf{b}_{1}\) examples, filtered by the acquisition function, is selected. The entire dataset at epoch \(e\) is \(S^{e}=\mathrm{Prune}(\cup_{e^{\prime}=1}^{e}S_{e^{\prime}})\) and has size \(\mathsf{b}_{2}>\mathsf{b}_{1}\). The operator Prune removes the subsets \(S_{e^{\prime}}\) introduced in old epochs \(e^{\prime}\in[e-e_{0}]\) if \(e>e_{0}\stackrel{{\Delta}}{{=}}\mathsf{b}_{2}/\mathsf{b}_{1}\) and otherwise leaves its input intact. At each epoch \(e\), the loss function is averaged over a batch set of size \(\mathsf{b}_{s}\) obtained by randomly sampling from \(S^{e}\). _Complexity of the parallel decoders_: The computational complexity of the decoder is measured in real multiplications (RMs). For instance, the complexity of the WMS with \(T\) iterations, \(\alpha_{v}=1\), without parameter sharing, or with Type \(T_{b}\) parameter sharing, is \(\mathrm{RM}=2T|E|\), where \(|E|=nd_{v}=md_{e}\) is the number of edges of the Tanner graph of the code. For the WMS decoder with Type \(T_{a}\) or Type \(T_{b}VC\) parameter sharing, \(\mathrm{RM}=T(m+n)\). The latter arises from the fact that equal weights factor out of the \(\sum\) and the min terms in BP and are applied once. Thus, the complexity of \(\
u\) parallel WMS decoders with Type \(T_{a}\) parameter sharing is \(\mathrm{RM}=\
u T(m+n)\). If \(\alpha_{v}\
eq 1\), \(nT\) is added to the above formulas. Finally, the complexity of Type \(T_{a}VC\) decoder is \(\mathrm{RM}=n\) per single iteration. These expressions neglect the cost of the syndrome check.