# An Ensemble Extreme Learning Machine for Data Stream Classification
## 2 Background Knowledge
### Extreme Learning Machine  
Extreme learning machine is a single hidden layer feedforward neural network. The input weights and biases are randomly generated, while the output weights can be automatically determined. Compared with the traditional methods such as BP neural network [39], the speed of ELM is faster [40; 41]. The structure of ELM is shown in Figure 1.  
Figure 1: The structure of ELM. For \(N\) arbitrary distinct samples, \(\{x_{i},t_{i}\}_{i=1}^{N},x_{i}=[x_{i1},x_{i2},\cdots,x_{in}]^{T}\in\mathbb{R}^{n},t_{i}=[t_{i1},t_{i2},\cdots,t_{im}]^{T}\in\mathbb{R}^{m}\). If the activation function is \(g(\mathbf{x})\) with \(L\) hidden nodes, the output of ELM is as  
\[\sum_{j=1}^{L}\mathbf{\beta}_{j}g(\mathbf{w}_{j}\cdot\mathbf{x}_{i}+b_{j})=\mathbf{o}_{j},\quad i =1,2,\cdots,N \tag{1}\]  
where \(\mathbf{w}_{j}=\left[w_{j1},w_{j2},\cdots,w_{jn}\right]^{T}\) is the weights connecting the \(j\)th hidden node with the input nodes, \(\mathbf{\beta}_{j}=\left[\beta_{j1},\beta_{j2},\cdots,\beta_{jn}\right]^{T}\) is the weights connecting the \(j\)th hidden node with the output nodes, \(b_{j}\) is the bias of the \(j\)th hidden nodes. According to the theory [24], ELM can approximate these \(N\) samples with zero error and \(\sum_{i=1}^{N}\left\|\mathbf{o}_{i}-\mathbf{t}_{i}\right\|=0\). Thus, the output of ELM can be expressed compactly as  
\[\mathbf{H}\mathbf{\beta}=\mathbf{T} \tag{2}\]  
where \(\mathbf{H}\) is the output matrix of hidden layer and \(\mathbf{T}\) is the output matrix of output layer. They are as:  
\[\mathbf{H}= \begin{bmatrix}g(\mathbf{w}_{1},\mathbf{b}_{1},\mathbf{x}_{1})&\cdots&g(\mathbf{w}_{L},\mathbf{b}_{L},\mathbf{x}_{1})\\ \vdots&\ddots&\vdots\\ g(\mathbf{w}_{1},\mathbf{b}_{1},\mathbf{x}_{N})&\cdots&g(\mathbf{w}_{L},\mathbf{b}_{L},\mathbf{x}_{N}) \end{bmatrix} _{N\times L}\quad\text{ and }\quad\mathbf{T}= \begin{bmatrix}\mathbf{t}_{1}^{T}\\ \vdots\\ \mathbf{t}_{N}^{T}\end{bmatrix} _{N\times m} \tag{3}\]  
The output weights matrix \(\mathbf{\beta}\) can be estimated as  
\[\mathbf{\beta}=\mathbf{H}^{\ddagger}\mathbf{T} \tag{4}\]  
where \(\mathbf{H}^{\ddagger}\) is the Moore-Penrose generalized inverse of the hidden layer output matrix \(\mathbf{H}\). It can be computed by orthogonal projection method, orthogonalization method and singular value composition (SVD) [42]. To improve the generalization performance of ELM, regularization is introduced and the optimization problem of ELM is as follows:  
\[\min \frac{1}{2}\left\|\mathbf{\beta}\right\|^{2}+C\frac{1}{2}\sum_{i=1}^{ N}\left\|\mathbf{\xi}_{i}\right\| \tag{5}\] \[s.t. h(\mathbf{x}_{i})\mathbf{\beta}=\mathbf{t}_{i}^{T}-\mathbf{\xi}_{i}^{T}\quad i=1,2,\cdots,N\]  
where \(C\) is a penalty factor, and \(\mathbf{\xi}_{i}\) is the training error which is used to eliminate over-fitting. According to KKT conditions [26], if \(L<N\), the \(\mathbf{\beta}\) is as  
\[\mathbf{\beta}=(\frac{\mathbf{I}}{C}+\mathbf{H}^{T}\mathbf{H})^{-1}\mathbf{H}^{T}\mathbf{T} \tag{6}\]  
Thus, the output of ELM is as  
\[f(\mathbf{x})=h(\mathbf{x})\mathbf{\beta}=h(\mathbf{x})(\frac{\mathbf{I}}{C}+\mathbf{H}^{T}\mathbf{H})^{-1} \mathbf{H}^{T}\mathbf{T} \tag{7}\]  
If \(L\geq N\), the \(\mathbf{\beta}\) is as  
\[\mathbf{\beta}=\mathbf{H}^{T}(\frac{\mathbf{I}}{C}+\mathbf{H}\mathbf{H}^{T})^{-1}\mathbf{T} \tag{8}\]  
Thus, the final output of ELM is  
\[f(\mathbf{x})=h(\mathbf{x})\mathbf{\beta}=h(\mathbf{x})\mathbf{H}^{T}(\frac{\mathbf{I}}{C}+\mathbf{H}\mathbf{H} ^{T})^{-1}\mathbf{T} \tag{9}\]The classification label of ELM is as  
\[label(\mathbf{x})=\operatorname*{argmax}_{i\in\{1,2,\cdots,m\}}f_{i}(\mathbf{x}) \tag{10}\]  
where \(f(\mathbf{x})=[f_{1}(\mathbf{x}),f_{2}(\mathbf{x}),\cdots,f_{m}(\mathbf{x})]\). From the above descriptions, the steps of ELM are summarized as follows (Algorithm 1) [24; 25]:  
```
0: a training data \(\mathcal{X}=\{(\mathbf{x}_{i},\mathbf{y}_{i})|\mathbf{x}_{i}\in\mathbb{R}^{n},\mathbf{y}_{i} \in\mathbb{R}^{m}\}\); the number of hidden nodes \(L\); the activation function \(g(\cdot)\);
0: ELM classifier.