Study of Set-Membership Kernel Adaptive Algorithms and Applications
R. C. de Lamare André Flores

Freezeout systematics due to the hadron spectrum
    Subhasis Samanta
    December 30, 2023
================================================


Adaptive algorithms based on kernel structures have been a topic of
significant research over the past few years. The main advantage is
that they form a family of universal approximators, offering an elegant
solution to problems with nonlinearities. Nevertheless these methods
deal with kernel expansions, creating a growing structure also known
as dictionary, whose size depends on the number of new inputs. In
this paper we derive the set-membership kernel-based normalized least-mean
square (SM-NKLMS) algorithm, which is capable of limiting the size
of the dictionary created in stationary environments. We also derive
as an extension the set-membership kernelized affine projection (SM-KAP)
algorithm. Finally several experiments are presented to compare the
proposed SM-NKLMS and SM-KAP algorithms to the existing methods. 



 Kernel methods, sparsification, set-membership kernel
adaptive filtering. 






§ INTRODUCTION


Adaptive filtering algorithms have been the focus of a great deal
of research in the past decades, and the machine learning community
has embraced and further advanced the study of these methods. However,
conventional adaptive algorithms often work with linear strucutres,
limiting the performance that they can achieve and constraining the
number of problems that can be solved. Under this scope a new family
of nonlinear adaptive filter algorithms based on kernels was developed.
A kernel is a function that compares the similarity between two inputs.
The kernel adaptive filtering (KAF) algorithms have been tested in
many different scenarios and applications <cit.><cit.>
<cit.><cit.>,
showing very good results.

As described in <cit.>, one of the main advantages
of KAF algorithms is that they are universal approximators, which
gives them the capability to treat complex and nonlinear problems.
In other words, they can model any input-output mapping. Many of these
algorithms have no local minima, which is also a desirable characteristic.
However, the computational complexity is significantly higher than
their linear counterparts<cit.>.

One of the first KAF algorithms to appear and widely adopted in the
KAF family because of its simplicity is the kernel least-mean square
(KLMS) proposed in <cit.> and extended in
<cit.>. The KLMS algorithm is inspired by the least-mean
square algorithm and showed good results, so that many researchers
have worked since then in the development of new kernel versions of
conventional adaptive algorithms. A few years later, a kernelized
version of the NLMS algorithm was proposed in <cit.>
using a nonlinear regression approach for time series prediction.
In <cit.>, the affine projection algorithm (APA)
was modified to develop a family of four algorithms known as the kernel
affine projection algorithms (KAPA). The recursive least squares algorithm
(RLS) was also extended in <cit.>, where the kernel recursive
least squares was introduced (KRLS). Later , the authors of <cit.>
proposed an extended version of the KRLS algorithm. Also the use of
multiple kernels was studied in <cit.> and <cit.>.


All the algorithms mentioned before have to deal with kernel expansions.
In other words, they create a growing structure, also called dictionary,
where they keep every new data input that arrives to compute the estimate
of the desired output. The natural problem that arises is that the
time and computational cost spent to compute a certain output could
exceed the tolerable limits for a specific application. Several criteria
were proposed to solve this problem. One of the most simple criteria
is the novelty criterion, presented in <cit.>. Basically
it establishes two thresholds to limit the size of the dictionary.
Another method, the approximate linear dependency (ALD) was proposed
in <cit.> and verifies if a new input can be expressed
as a linear combination of the elements stored before adding this
input to the dictionary. The coherence criterion was introduced in
<cit.> also to limit the size of the dictionary
based on the similarity of the inputs. A measure called surprise was
presented in <cit.> to remove redundant data.

In this work, we present the set-membership normalized kernel
least-mean square (SM-NKLMS) and the set-membership kernel affine
projection (SM-KAP) adaptive algorithms, which can provide a faster
learning than existing kernel-based algorithms and limit the size of
the dictionary without compromising performance. Similarly to
existing set-membership algorithms
<cit.>,
the proposed SM-NKLMS and SM-KAP algorithms are equipped with
variable step sizes and perform sparse updates that are useful for
several applications
<cit.>.
Unlike existing kernel-based adaptive algorithms the proposed
SM-NKLMS and SM-KAP algorithms deal with in a natural way with the
kernel expansion because of the data selectivity based on error
bounds that they implement.

This paper is organized as follows. In section II, the problem formulation
is presented. In section III the SM-NKLMS and the SM-KAP algorithms
are derived. Section IV presents the simulations and results of the
algorithms developed in an application involving a time series prediction
task. Finally, section V presents the conclusions of this work. 






§ PROBLEM STATEMENT


Let us consider an adaptive filtering problem with a sequence
of training samples given by {x[i],d[i]},
where x[i] is the N-dimensional input vector
of the system and d[i] represents the desired signal at time instant
i. The output of the adaptive filter is given by


    y[i]=𝐰^Tx[i],

where 𝐰 is the weight vector with length N.

Let us define a non-linear transformation denoted by φ:ℝ→𝔽
that maps the input to a high-dimensional feature space. Applying
the transformation stated before, we map the input and the weights
to a high-dimensional space obtaining:

    φ[i]=φ(x[i]),


    ω[i]=φ(𝐰[i]),



The error generated by the system is given by e[i]=d[i]-ω^T[i]φ[i].
The main objective of the kernel-based adaptive algorithms is to model
a function to implement an input-output mapping, such that the mean
square error generated by the system is minimized. In addition, we
assume that the magnitude of the estimated error is upper bounded
by a quantity γ. The idea of using an error bound was reported
in <cit.> and was used since then to develop different
versions of data selective algorithms.








§ PROPOSED SET-MEMBERSHIP KERNEL-BASED ALGORITHMS




Assuming that the value of γ is correctly chosen then there
exists several functions that satisfy the error requirement. To summarize,
any function leading to an estimation error smaller than the defined
threshold is an adequate solution, resulting in a set of filters.
Consider a set S̅ containing all the possible
input-desired pairs of interest {φ[i],d[i]}.
Now we can define a set θ with all the possible
functions leading to an estimation error bounded in magnitude by γ.
This set is known as the feasibility set and is expressed by


    θ=⋂_{φ,d}∈S̅{ω∈𝔽 / |d-ω^Tφ|≤γ}



Suppose that we are only interested in the case in which only measured
data are available. Let us define a new set ℋ[i]
with all the functions such that the estimation error is upper bounded
by γ . The set is called constraint set and is mathematically
defined by

    ℋ[i]={ω∈𝔽 / |d[i]-ω^Tφ[i]|≤γ}



It follows that for each data pair there exists an associated constraint
set. The set containing the intersection of the constraint sets over
all available time instants is called exact membership set and is
given by the following equation:

    ψ[i]=⋂_k=0^iℋ[i]



The exact membership set,ψ[i], should become small
as the data containing new information arrives. This means that at
some point the adaptive filter will reach a state where ψ[i]=ψ[i-1],
so that there is no need to update ω[i].
This happens because ψ[i-1] is already a subset of
ℋ[i].As a result, the update of any set-membership
based algorithm is data dependent, saving resources, a fact that is
crucial in kernel-based adaptive filters because of the growing structure
that they create.

As a first step we check if the previous estimate is outside the constraint
set, i.e., |d[i]-ω^T[i-1]φ[i]|>γ.
If the error exceeds the bound established, the algorithm performs
an update so that the a posteriori estimated error lies in ℋ[i]
.If the previous case occurs we minimize ||ω[i+1]-ω[i]||^2
subject to ω[i+1]∈ℋ[i],
which means that the a posteriori error ξ_ap[i]
is given by


    ξ_ap[i]=d[i]-ω^T[i+1]φ[i]=±γ



The NKLMS update equation presented in <cit.>
is given by:

    ω[i+1]=ω[i]+μ[i]/ε+||φ[i]||^2e[i]φ[i],

where μ[i] is the step size that should be chosen
to satisfy the constraints of the algorithm and ε is
a small constant used to avoid numerical problems. Substituting (<ref>)
in (<ref>) and using the kernel trick to replace
dot products by kernel evaluations we arrive at:

    ξ_ap[i]=e[i]-μ[i]/ε+κ(x[i],x[i])e[i]κ(x[i],x[i])



Assuming that the constant ε is sufficiently small to
guarantee that κ(x[i],x[i])/ε+κ(x[i],x[i])≈1
and following the procedure stated in <cit.>we get:


    μ[i]=[ 1-γ/|e[i]|;          0 ]   [ |e[i]|>γ;          ]



We can compute ω recursively as follows:


    ω[i+1]     =    ω[i-1]+μ[i-1]e[i-1]/ε+||φ[i-1]||^2φ[i-1]
           +μ[i]/ε+||φ[i]||^2e[i]φ[i]




    ⋮


    ω[i+1]=ω[0]+∑_k=1^iμ[k]/ε+||φ[k]||^2e[k]φ[k]



Setting ω[0] to zero leads to:


    ω[i+1]=∑_k=1^iμ[k]/ε+||φ[k]||^2e[k]φ[k]



The output f(φ[i+1])=ω^T[i+1]φ[i+1]of
the filter to a new input φ[i+1]
can be computed as the following inner product

    f(φ[i+1])=[∑_k=1^iμ[k]e[k]/ε+||φ[k]||^2φ^T[k]]φ[i+1]




    =∑_k=1^iμ[k]e[k]/ε+||φ[k]||^2φ^T[k]φ[i+1].



Using the kernel trick we obtain that the output is equal to:

    ∑_k=1^iμ[k]e[k]/ε+κ(x[k],x[k])κ(x[k],x[i+1]),

where μ[k] is given by (<ref>) . Let
us define a coefficient vector a=μ[i]e[i],
so that equation (<ref>) becomes:


    ∑a_i/ε+κ(x[k],x[k])κ(x[k],x[i+1])



Equations (<ref>) -(<ref>) summarize the
algorithm proposed. We set the initial value of ω
to zero as well as the first coefficient. As new inputs arrive we
can calculate the output of the system with (<ref>).
Then the error may be computed and if it exceeds the bound established
we calculate the step size with (<ref>). Finally we
update the coefficients a_i . Note that some coefficients
may be zero due the data selective characteristic of the algorithm.
We do not need to store the zero coefficients as they do not contribute
to the output computations, resulting in a saving of resources. This
is an important result because it controls in a natural way the growing
network created by the algorithm. In stationary environments the algorithm
will limit the growing structure.

Consider now the KAP algorithm, which uses the last K inputs to
update the coefficients. Based on this fact, let us redefine our problem
and use the past K constraint sets to perform the update. Under
this scope it is also convenient to express the exact membership as
follows:


    ψ[i]=(⋂_j=0^i-Kℋ[j])(⋂_l=i-K+1^iℋ[l])=ψ^i-K[i]⋂ψ^K[i],

where ψ^K[i] designates the use of K constraint
sets for updating. This means that the vector ω[i]
should belong to ψ^K[i] . In order to develop the
SM-KAP algorithm we need to set several bounds γ̅_k[i],
for k=1,…,K, so that the error magnitudes should satisfy this
constraints after updating. It follows that there exists a space S(i-k+1)
containing all vectors ω satisfying d(i-k+1)-ω^Tφ(i-k+1)=γ̅_k[i]
for k=1,…,K. The SM-KAPA should perform an update whenever
ω[i]∉ψ^K[i],
so that the equation ∥ω[i]-ω[i-1]∥^2
subject to d[i]-Φ^T[i]ω[i]=γ̅[i]
should be minimized, where γ̅[i]
is a vector containing all the K bounds. This constraint can also
be expressed as d[i]-γ̅[i]=Φ^T[i]ω[i].
Solving the problem with the method of the Lagrange multipliers we
get:


    ℒ(ω[i])     =    ∥ω[i]-ω[i-1]∥^2
           +λ^T[i](d[i]-Φ^T[i]ω[i]-γ̅[i]),

where λ^T[i] is the vector of Lagrange
multipliers. Now we can compute the gradient of ℒ(ω[i])
and equate it to zero.

    ∂ℒ(ω[i])=/∂ω[i]2ω[i]-2ω[i-1]-λ^T[i]Φ^T[i]=0


    ω[i]=ω[i-1]+1/2Φ[i]λ[i]


    d[i]-γ̅[i]=Φ^T[i](ω[i-1]+1/2Φ[i]λ[i])


    d[i]-γ̅[i]=Φ^T[i]ω[i-1]+Φ^T[i]Φ[i]λ[i]/2


    λ[i]/2=(Φ^T[i]Φ[i])^-1(e[i]-γ̅[i]),



We can now formulate the updating equation, which is used as long
as the error is greater than the established bound, i.e., |e[i]|>γ̅

    ω[i]=ω[i-1]+Φ[i](Φ^T[i]Φ[i])^-1(e[i]-γ̅[i]),

where we have to consider that the vector e[i]
is composed by the actual error and all K-1 a posteriori errors,
corresponding to the K-1 last inputs used. This means that vector
e[i] is expressed by [[        e[i]   e_ap[i-1]           ⋯ e_ap[i-K+1] ]] ,where e_ap[i-k] denotes the a posteriori error computed
using the coefficients at iteration i. In other words, e_ap[i-k]=d[i-k]-φ^T[i-k]ω[k].

Let us now consider a simple choice for vector γ̅[i].
We can exploit the fact that the a posteriori error was updated to
satisfy the constraint d[i]-Φ^T[i]ω[i]=γ̅[i].That
means that we can set the values of γ̅_k[i]
equal to e_ap[i-k+1]for i≠1. Substituting this
condition in equation (<ref>) we obtain:

    ω[i]=ω[i-1]+Φ[i](Φ^T[i]Φ[i])^-1(e[i]-γ̅_̅1̅[i])u,

where u=[[ 1 0 ⋯ 0 ]]^T. We can now select γ̅_̅1̅[i] as in the SM-NKLMS
so that


    γ̅_̅1̅[i]=γ̅e[i]/|e[i]|




    ω[i]=ω[i-1]+Φ[i](Φ^T[i]Φ[i])^-1(η[i]e[i])u




    η[i]=
    1-γ̅/|e[i]|    |e[i]|>γ̅
    
    0




    ω[i]=∑_j=1^i-1a_j[i-1]φ[j]+(η[i]e[i])Φ[i]𝐀̃[i],

where the matrix 𝐀̃[i] was redefined
as

    𝐀̃[i]=(Φ^T[i]Φ[i]+ϵ𝐈)^-1u




    a_k[i]=η[i]e[i]ã_k[i],     k=i
    
    a_k[i-1]+η[i]e[i]ã_K+k-i[i],     i-K+1≤ k
    
    a_k[i-1]     1≤ k<i-K+1

 






§ SIMULATIONS






In this section we analyze the performance of the algorithms proposed
for a time series prediction task. We used two different time series
to perform the tests, the Mackey Glass time series and a laser generated
time series. First we separate the data into two sets, one for training
and the other for testing as suggested in <cit.>.The
time-window was set to seven and the prediction horizon to one, so
that the last seven inputs of the time series were used to predict
the value one step ahead. Additionally, both time series were corrupted
by additive Gaussian noise with zero mean and standard deviation equal
to 0.04. The Gaussian kernel was used in all the algorithms to perform
all the experiments. Using the silver rule and after several tests,
the bandwith of the kernel was set to one.

For the first experiment we analyze the performance of the adaptive
algorithms over the Mackey-Glass time series. A total of 1500 sample
inputs were used to generate the learning curve and the prediction
was performed over 100 test samples. For the KAPA and the SM-KAPA
algorithms, K was set to 7 so that the algorithms used the last
seven input samples as a single input. For the KLMS algorithm the
step size was set to 0.05.The error bound for the SM-NKLMS and
the SM-KAPA algorithm was set to √(5)σ. The final results
of the algorithms tested are shown in table <ref>
where the last 100 data points of each learning curve were averaged
to obtain the MSE. The learning curves of the algorithms based on
kernels is presented in Figure <ref>. From
the curves, we see that the algorithms proposed outperform conventional
algorithms in convergence speed.




In the second experiment we consider the performance of the proposed
algorithms over a laser generated time series. In this case , 3500
sample inputs were used to generate the learning curve and the prediction
was performed over 100 test samples. The setup used in the previous
experiment was considered. Table <ref>
summarizes the MSE obtained for every algorithm tested. The final
learning curves are showed in Figure <ref>.










On the next experiment we study the size of the dictionary generated
by the conventional KLMS algorithm and by the proposed SM-NKLMS algorithm.
The result is presented in Figure <ref>. We see
that the proposed algorithm naturaly limits the size of the dictionary.




As a final experiment, we analyze and compare the robustness of the
algorithm proposed with respect to the conventional algorithms. Figure
(<ref>) shows the results obtained. It is clear that
the SM-NKLMS exhibits a better perfomance than the KLMS algorithm.
In general, all kernel algorithms overperform their linear counterparts.











§ CONCLUSIONS






In this paper two data selective kernel-type algorithms were
presented, the SM-KNLMS and the SM-KAP algorithms. Both algorithms
have a faster convergence speed than the conventional algorithms.
They also have the advantage of naturally limiting the size of the
dictionary created by kernel-based algorithms and a good noise
robustness. In general, the proposed algorithms outperform the
existing kernel-based algorithms. 



plain


