Performance Analysis of Learning Algorithms Based on Simplified Maximum Zero-Error Probability

Ⅰ. Introduction

Many tasks in machine learning or adaptive signal processing require robustness against noise and rapid learning speed and lower steady state error. The common mean squared error(MSE) based learning algorithms are known not to yield sufficient performance in non-Gaussian noise environments[1],[2]. On the other hand, learning algorithms developed from minimum error entropy(MEE) criterion can break through these obstacles[3],[4]. The MEE criterion is a powerful approach for robust machine learning as well as for non-Gaussian signal processing[4].

MEE criterion has been designed to create error entropy using error probability density based on Parzen density method[5]. In kernel density estimation method like Parzen density, the estimate for error density converges to the true error probability as the number of error samples increases[6]. That is, the MEE requires sufficient error samples for correct calculation of error entropy, which in turn makes the system complicated.

For this reason there has not been any research of using reduced sample points before the approach of using only the current error sample e_k and the previous one e_k-1 for calculating the error entropy has recently been proposed[7]. The calculation reduced simplified MEE(SMEE) has shown almost equal performance unlike the belief of researchers who work on MEE[7].

The SMEE criterion contains the term e_k-e_k-1 and the variance of e_k-e_k-1 could be larger than that of e_k or e_k-1 itself, which the maximum zero error probability(MZEP) criterion handles error samples not their differences[8]. The variance of error samples leads us to propose a new simple learning algorithm based on the MZEP criterion using only e_k and e_k-1. In this paper, learning performance of the proposed simplified MZEP(SMZEP) is analyzed through adaptive equalization experiment in a communication system model with severely distorted multi-path fading and impulsive noise[9].

Ⅱ. MSE Criterion and LMS Algorithm

In case of FIR linear filter, a linear combiner with L weights W_k at time k can be used for input vector $$ X_k={\left[x_k,x_{k-1},x_{k-2},\dots ,x_{k-L+1}\right]}^T$$ and output $$ y_k=W_k^T{X}_k$$[1]. Defining the error as e_k = a_k - y_k where a_k is the desired value or training symbol, its MSE is derived as

Using the instant error power $$ e_k^2$$ instead of estimating the ensemble average of error power we obtain the weight update equation 1.

Where μ_LMS is a step-size or convergence parameter that controls its stability. From the fact that LMS algorithm employs the instant error power instead of using the statistically averaged error power (1), we can refer to the LMS algorithm as a simplified version of MSE based algorithms using the ensemble average of error power.

Ⅲ. MZEP Criterion based on ITL

The ITL based performance criterion is constructed by error probability density which uses Parzen window method[5].

In this section we briefly introduce the ITL based criterion that maximizes zero-error probability f_E(e = 0) so as to create a concentration of error samples around zero. The estimated error probability $$ f_E^{\wedge }\left(e\right)$$ can be calculated using the Parzen window method with the sample size N and the Gaussian kernel of kernel size σ[5].

This criterion can be developed by minimizing quadratic probability distance $$ QD=\int {\left(f_E\left(e\right)-\delta \left(e\right)\right)}^{2}de$$ between the PDF of error signal f_E(e) and Dirac-delta function of error δ(e), so that f_E(e) is forced to form the shape of δ(e).

The term $$ \int {\delta }^2\left(e\right)de$$ is not defined mathematically but can be treated as a constant since it has no relations with the system weights.

Minimization of QD in (5) induces minimization of $$ \int f_E^2\left(e\right)de$$ and maximization of f_E(0), simultaneously. It is noticeable that minimization of $$ \int f_E^2\left(e\right)de$$ indicates maximization of error entropy that makes error samples spread apart. It is apparent that this contradicts the MEE criterion that maximizes $$ \int f_E^2\left(e\right)de$$[3],[4]. To avoid this contradiction, MZEP criterion that maximizes only the term f_E(0) in (5) has been proposed in [8] as:

The estimated zero-error probability $$ f_E^{\wedge }\left(0\right)$$ can be calculated by replacing e with zero in the kernel density estimation method (3) with the sample size N.

Ⅳ. Simplified MZEP Criterion and related Algorithms

In Parzen window method as in (3), the estimate for error density $$ f_E^{\wedge }\left(e\right)$$ converges to the true error probability f_E(e) as N increases[6]. Also for the error entropy criterion[3], the error entropy approaches Renyi entropy as N increases. For these reasons, there has not been any research of using reduced sample points even to N = 2 for e_k and e_k-1. The approach of using only e_k and e_k-1 for calculating the error entropy has recently been proposed in [7]. The SMEE criterion V°(e_k) can be written as

From the results of the work[7], learning performance in communication channel equalization based on the SMEE has shown to be similar to the case of sample size N being large enough. Inspired by this idea, we propose to use only e_k and e_k-1 for the criterion of the zero-error probability and analyze its performance compared to the SMEE in (8).

Then, eq. (7) becomes the following $$ f_E^{\circ }\left(0\right)$$.

And maximization of (9) forces error samples e_k and e_k-1 to be moved to near zero.

This simplified criterion (9) and (10) can be a summarized expression of SMZEP.

For the maximization of the Criterion (9) with respect to the system $$ y_k=W_k^T{X}_k$$ in Section II, the gradient ascent method with the step-size μ_SMZEP can be employed as

where the gradient can be evaluated from

So the weight update equation (SMZEP algorithm) can be expressed as

For comparison, SMEE algorithm in [7] can be written as

It can be noticed that SMZEP algorithm applies Gaussian kernel to the error samples e_k and e_k-1 separately while SMEE deals with the difference between e_k and e_k-1. On the other hand, by comparing (2) and (13), we can notice the error term of (13) has a modified form $$ e_k^{\circ }=e_k{G}_{\sigma }\left(-e_k\right)$$ while (2) has only e_k. Likewise, it can be considered that the SMEE has a modified error $$ e_k^{\Delta }=\left(e_k-e_{k-1}\right)G_{\sigma }\left(e_k-e_{k-1}\right)$$ in (14). Then, SMZEP algorithm) becomes

And SMEE algorithm becomes

It may be worthwhile to observe how different performance would be resulted from these different features between SMZEP with $$ e_k^{\circ }$$ and SMEE with $$ e_k^{\Delta }$$. And the role of these modified errors is needed to be analyzed.

Ⅴ. Performance Results and Discussion

In this Section, the learning performance of the SMEE and the SMZEP algorithm is discussed and resulting properties are analyzed in the experiment of communication channel equalization. The experimental communication system is shown in Fig. 1.

Fig. 1.

A Base-band communication system for the experiment

The experimental setup is composed of a data generation (random symbol a_k is generated), communication channel H(z), and a receiver equipped with a linear combiner $$ y_k=W_k^T{X}_k$$. The random symbol a_k at time k is equiprobably chosen among the symbol set{±1,±3} and distorted through the multipath channel H(z) and corrupted by impulsive noise n_k.

The transfer function H(z) has two different channel model H1 and H2[9].

Both of them have spectral nulls and induce severe intersymbol interference (ISI). The impulsive noise consists of impulses and white Gaussian noise. The impulses are generated by Poisson process with variance 50 and occurrence rate 0.03[10],[11]. The variance of the background white Gaussian noise is 0.001. A sample of the impulsive noise is depicted in Fig. 2.

Fig. 2.

A sample of impulsive noise used in the experiment

The linear combiner in the receiver has 11 weights which are updated by SMEE or SMZEP with the common step size μ_SMZEP = μ_SMEE = 0.02 and the kernel size σ=0.8. Fig. 3 shows the MSE learning curves of SMEE and SMZEP for two different channel models. It is observed that the learning curve of LMS in (2) cannot converge below -16 dB. On the other hand, the SMEE and SMZEP algorithms show fast and stable convergence to below -23dB. In H1, the SMZEP in blue converges in about 1200 samples and the SMEE in red does in about 2000 samples. The steady state MSE is -26dB for SMZEP but -25dB for SMEE. In both convergence speed and lowest MSE, the proposed SMZEP shows superior performance. Similar results are observed in channel model H2 showing SMZEP has a lower minimum MSE.

Fig. 3.

MSE learning curves (red: SMEE-H1, blue: SMZEP-H1, green: SMEE-H2, orange: SMZEP-H2, gray: LMS-H1)

Fig. 4 for the comparison of system error distribution shows their performance differences more clearly. The error value on the horizontal axis is defined as the difference between the transmitted symbol and its corresponding receiver system output. The error probability is on the vertical axis. As shown in Fig. 4, the system error samples of SMEE and SMZEP produces error distributions highly concentrated around zero. Especially the proposed SMZEP has significantly narrower bell shape of error distribution than the SMEE in both channel models revealing that more of the error samples of SMZEP are around zero than those of SMEE.

Fig. 4.

Probability distribution for error samples ranging from -0.4 to 0.4 (red: SMEE-H1, blue: SMZEP-H1, green: SMEE-H2, Orange: SMZEP-H2)

To investigate the cause of the performance difference in more detail, we present the fluctuation (variance) of the center weight of each algorithm in Fig. 5. After sample number 1000 the center weight of both algorithms reaches a steady state but shows different behaviors. The variance of the center weight of SMEE stays at about 0.015 while that of SMZEP indicates 0.0025 which means the center weight of SMEE is 6 times more likely to suffer severe fluctuations.

Fig. 5.

Variance of the center weight (red: SMEE, blue: SMZEP)

As discussed in Section IV, the modified error $$ e_k^{\circ }=e_k{G}_{\sigma }\left(-e_k\right)$$ in SMZEP and $$ e_k^{\Delta }=\left(e_k-e_{k-1}\right)G_{\sigma }\left(e_k-e_{k-1}\right)$$ in SMEE are compared in Fig. 6 in the aspect of fluctuation, that is, variance of modified error. The variance of $$ e_k^{\Delta }$$ converges to 0.042 while that of $$ e_k^{\circ }$$ does to 0.017 which is lower by more than 2 times. It can be understood that the bigger variance of $$ e_k^{\Delta }$$ from SMEE causes the performance degradation in MSE convergence and error distribution compared to SMZEP.

Fig. 6.

Variance of modified error (red: SMEE, blue: SMZEP)

Ⅵ. Conclusion

In Non-Gaussian noise environments, the common criterion MSE does not provide its’ related learning algorithms with acceptable learning performance. The approach based on ITL breaks through these problems but it has been known to require sufficient data sample size that makes the system complicated. A recent study proposed a simplified MEE that utilizes only two error samples e_k and e_k-1 in an iteration. It yields sufficiently good performance even with two error samples. In this paper, the zero error probability criterion using only two error samples e_k ande_(k-1)like the SMEE is proposed. The proposed SMZEP shows faster convergence by about 2 times and lower steady state MSE by about 1 dB than the SMEE. Also more of the system error samples of SMZEP are concentrated on zero than those of SMEE. From the analysis of the cause of the performance difference, it is found that the modified error of SMZEP produces less fluctuation, which leads to less fluctuation of weight after convergence than that of the SMEE. So we conclude that the proposed SMZEP can be an effective candidate for adaptive learning systems that may employ the existing SMEE algorithm.

Acknowledgments

본 과제(결과물)는 2023년도 교육부의 재원으로 한국연구재단의 지원을 받아 수행된 지자체-대학 협력기반 지역혁신 사업의 결과입니다(2022RIS-005).

References

• S. Haykin, Adaptive Filter Theory, 4th ed. Upper Saddle River, NJ: Prentice Hall, 2001.
• J. Principe, D. Xu, and J. Fisher, Information Theoretic Learning, in Unsupervised Adaptive Filtering, New York, NY: Wiley, pp. 265-319, 2000.
• D. Erdogmus and J. C. Principe, “An Error-Entropy Minimization Algorithm for Supervised Training of Nonlinear Adaptive Systems,” IEEE Transactions on Signal Processing, Vol. 50, No. 7, pp. 1780-1786, July 2002. [https://doi.org/10.1109/TSP.2002.1011217]
• Y. Li, B. Chen, N. Yoshimura, and Y. Koike, “Restricted Minimum Error Entropy Criterion for Robust Classification,” Learning Systems, Vol. 33, No. 11, pp. 6599-6612, November 2022. [https://doi.org/10.1109/TNNLS.2021.3082571]
• E. Parzen, “On Estimation of a Probability Density Function and Mode,” The Annals of Mathematical Statistics, Vol. 33, No. 3, pp. 1065-1076, September 1962. [https://doi.org/10.1214/aoms/1177704472]
• R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, 2nd ed. New York, NY: John Wiley & Sons, 2012.
• N. Kim and K. Kwon, “A Simplified Minimum Error Entropy Criterion and Related Adaptive Equalizer Algorithms,” The Journal of Korean Institute of Communications and Information Sciences, Vol. 48. No. 3, pp. 312-318, March 2023. [https://doi.org/10.7840/kics.2023.48.3.312]
• N. Kim and K. Kwon, “Performance Enhancement of Blind Algorithms Based on Maximum Zero Error Probability,” Journal of Theoretical and Applied Information Technology, Vol. 95, No. 22, pp. 6056-6067, November 2017.
• J. Proakis, Digital Communications, 2nd ed. New York, NY: McGraw-Hill, 1989.
• I. Santamaria, P. P. Pokharel, and J. C. Principe, “Generalized Correlation Function: Definition, Properties, and Application to Blind Equalization,” IEEE Transactions on Signal Processing, Vol. 54, No. 6, pp. 2187-2197, June 2006. [https://doi.org/10.1109/TSP.2006.872524]
• N. Kim, “Kernel Size Adjustment Based on Error Variance for Correntropy Learning Algorithms,” The Journal of Korean Institute of Communications and Information Sciences, Vol. 46, No. 2, pp. 225-230, February 2021. [https://doi.org/10.7840/kics.2021.46.2.225]