Francais | English | Espanõl

From Wikipedia, the free encyclopedia

Radial basis functions (RBF) are a means for interpolation in a stream of data. They differ from statistical approaches in that approximations must be performed on streams of data rather than on complete data sets. RBFs use supervised learning and sometimes unsupervised learning to minimize approximation error in a stream of data. They are used in function approximation, time series prediction, and control.

Contents 1 Overview 2 The problem 3 Architecture 3.1 Unnormalized 3.2 Normalized 3.2.1 Normalized architecture 3.2.2 Theoretical motivation for normalization 3.3 Local linear models 4 Objective functions 5 Training 5.1 Gradient descent training of the linear weights 5.2 Projection operator training of the linear weights 5.3 Training the basis function centers 6 Examples 6.1 Logistic map 6.2 Function approximation 6.2.1 Unnormalized radial basis functions 6.2.2 Normalized radial basis functions 6.3 Time series prediction 6.4 Control of a chaotic time series 7 See also 8 External links 9 References

[edit] Overview

Radial basis functions (RBF) are powerful techniques for interpolation in multidimensional space. An RBF is a function which has built into it a distance criterion with respect to a center. Such functions can be used very efficiently for interpolation and for smoothing of data. Radial basis functions have been applied in the area of neural networks where they are used as a replacement for the sigmoidal transfer function. Such networks have 3 layers, the input layer, the hidden layer with the RBF non-linearity and a linear output layer. The most popular choice for the non-linearity is the Gaussian. RBF networks have the advantage of not being locked into local minima as do feedforward networks.

[edit] The problem

The problem solved by RBF's is the development of an analytic approximation for the input/output mappings described by a deterministic, noisy, or stochastic data stream

<math> \left \{ \left[ \mathbf{x}(t) , y(t) \right] : \left[ \mathbb{R}^n , \mathbb{R} \right] \right \} _{t=1}^{ \infty } </math>

where

<math> \mathbf{x}(t) </math> is the input vector at time t,

<math> y(t) </math> is the output at time t, and

<math> n </math> is the dimension of the input space.

In the deterministic case the data is drawn from the set

<math> \left \{ \left[ \mathbf{x}(t) , y(t) = f \big( \mathbf{x}(t) \big) \right] \right \} _{t=1}^{ \infty } </math>.

In the noisy case data is drawn from the set

<math> \left \{ \left[ \mathbf{x}(t) , y(t) = f \big( \mathbf{x}(t) \big) + \epsilon(t) \right] \right \} _{t=1}^{ \infty } </math>

where <math> \epsilon(t) </math> is a partially known random process.

In the stochastic case, data is drawn from the joint probability distribution

<math> P \left( \mathbf{x} \land y \right ) </math>.

[edit] Architecture

RBF architectures come in two forms, normalized and unnormalized. The forms can be expanded into a superposition of local linear models.

[edit] Unnormalized

The unnormalized radial basis function architecture, <math> \varphi : \mathbb{R}^n \to \mathbb{R} </math> , is

<math> \varphi ( \mathbf{x} ) \ \stackrel{\mathrm{def}}{=}\ \sum_{i=1}^N a_i \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>

where <math> \varphi </math> is the approximation to the data, <math> \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>, known as a "radial basis function," is a local function of the distance <math> \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert </math> between the input vector <math> \mathbf{x} </math> and a "basis function center"

<math> \mathbf{c}_i </math> <math> (i=1,N) </math>,

and

<math> a_i </math> <math> (i=1,N) </math>

are weights to be determined by data. Typically the distance is taken to be the Euclidean distance and the basis function is taken to be Gaussian

<math> \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) \propto \exp \left[ -\beta \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert ^2 \right] </math>.

The weights <math> a_i </math>, <math> \mathbf{c}_i </math>, and <math> \beta </math> are determined in a manner that optimizes the fit between <math> \varphi </math> and the data.

[edit] Normalized

[edit] Normalized architecture

The normalized RBF architecture is

<math> \varphi ( \mathbf{x} ) \ \stackrel{\mathrm{def}}{=}\ \frac { \sum_{i=1}^N a_i \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } { \sum_{i=1}^N \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } = \sum_{i=1}^N a_i u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>

where

<math> u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) \ \stackrel{\mathrm{def}}{=}\ \frac { \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } { \sum_{i=1}^N \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } </math>

is known as a "normalized radial basis function."

[edit] Theoretical motivation for normalization

There is theoretical justification for this architecture in the case of stochastic data flow. Assume a Stochastic kernel approximation for the joint probability density

<math> P\left ( \mathbf{x} \land y \right ) = \sum_{i=1}^N \, \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) \, \sigma \big ( \left \vert y - e_i \right \vert \big )</math>

where the weights <math> \mathbf{c}_i </math> and <math> e_i </math> are exemplars from the data and we require the kernels to be normalized

<math> \int \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) \, d^n\mathbf{x} =1</math>

and

<math> \int \sigma \big ( \left \vert y - e_i \right \vert \big ) \, dy =1</math>.

The probability densities in the input and output spaces are

<math> P \left ( \mathbf{x} \right ) = \int P \left ( \mathbf{x} \land y \right ) \, dy = \sum_{i=1}^N \, \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big )</math>

and

<math> P \left ( y \right ) = \int P \left ( \mathbf{x} \land y \right ) \, d^n \mathbf{x} = \sum_{i=1}^N \, \sigma \big ( \left \vert y - e_i \right \vert \big ) </math>

The expectation of y given an input <math> \mathbf{x} </math> is

<math> \varphi \left ( \mathbf{x} \right ) \ \stackrel{\mathrm{def}}{=}\ E\left ( y \mid \mathbf{x} \right ) = \int y \, P\left ( y \mid \mathbf{x} \right ) dy </math>

where

<math> P\left ( y \mid \mathbf{x} \right ) </math>

is the conditional probability of y given <math> \mathbf{x} </math>. The conditional probability is related to the joint probability through Bayes theorem

<math> P\left ( y \mid \mathbf{x} \right ) = \frac {P \left ( \mathbf{x} \land y \right )} {P \left ( \mathbf{x} \right )} </math>

which yields

<math> \varphi \left ( \mathbf{x} \right ) = \int y \, \frac {P \left ( \mathbf{x} \land y \right )} {P \left ( \mathbf{x} \right )} \, dy </math>.

This becomes

<math> \varphi \left ( \mathbf{x} \right ) = \frac { \sum_{i=1}^N a_i \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } { \sum_{i=1}^N \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } = \sum_{i=1}^N a_i u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>

when the integrations are performed.

[edit] Local linear models

It is sometimes convenient to expand the architecture to include local linear models. In that case the architectures become, to first order,

<math> \varphi \left ( \mathbf{x} \right ) = \sum_{i=1}^N \left ( a_i + \mathbf{b}_i \cdot \left ( \mathbf{x} - \mathbf{c}_i \right ) \right )\rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>

and

<math> \varphi \left ( \mathbf{x} \right ) = \sum_{i=1}^N \left ( a_i + \mathbf{b}_i \cdot \left ( \mathbf{x} - \mathbf{c}_i \right ) \right )u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>

in the unnormalized and normalized cases, respectively. Here <math> \mathbf{b}_i </math> are weights to be determined. Higher order linear terms are also possible.

This result can be written

<math> \varphi \left ( \mathbf{x} \right ) = \sum_{i=1}^{2N} \sum_{j=1}^n e_{ij} v_{ij} \big ( \mathbf{x} - \mathbf{c}_i \big ) </math>

where

<math> e_{ij} = \begin{cases} a_i, & \mbox{if } i \in [1,N] \\ b_{ij}, & \mbox{if }i \in [N+1,2N] \end{cases} </math>

and

<math> v_{ij}\big ( \mathbf{x} - \mathbf{c}_i \big ) \ \stackrel{\mathrm{def}}{=}\ \begin{cases} \delta_{1j} \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) , & \mbox{if } i \in [1,N] \\ \left ( x_{ij} - c_{ij} \right ) \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) , & \mbox{if }i \in [N+1,2N] \end{cases} </math>

in the unnormalized case and

<math> v_{ij}\big ( \mathbf{x} - \mathbf{c}_i \big ) \ \stackrel{\mathrm{def}}{=}\ \begin{cases} \delta_{1j} u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) , & \mbox{if } i \in [1,N] \\ \left ( x_{ij} - c_{ij} \right ) u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) , & \mbox{if }i \in [N+1,2N] \end{cases} </math>

in the normalized case.

Here <math> \delta_{ij} </math> is a Kronecker delta function defined as

<math> \delta_{ij} = \begin{cases} 1, & \mbox{if }i = j \\ 0, & \mbox{if }i \ne j \end{cases} </math>.

[edit] Objective functions

Main article: Optimization (mathematics)

The weights, which we signify by <math> \mathbf{w} </math>, in the RBF architecture are found through optimization of an objective function. The most common objective function is the least squares function

<math> K( \mathbf{w} ) \ \stackrel{\mathrm{def}}{=}\ \sum_{t=1}^\infty K_t( \mathbf{w} ) </math>

where

<math> K_t( \mathbf{w} ) \ \stackrel{\mathrm{def}}{=}\ \big [ y(t) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ]^2 </math>.

We have explicitly included the dependence on the weights. Minimization of the least squares objective function by optimal choice of weights optimizes accuracy of fit.

There are occasions in which multiple objectives, such as smoothness as well as accuracy, must be optimized. In that case it is useful to optimize a regularized objective function such as

<math> H( \mathbf{w} ) \ \stackrel{\mathrm{def}}{=}\ K( \mathbf{w} ) + \lambda S( \mathbf{w} ) \ \stackrel{\mathrm{def}}{=}\ \sum_{t=1}^\infty H_t( \mathbf{w} ) </math>

where

<math> S( \mathbf{w} ) \ \stackrel{\mathrm{def}}{=}\ \sum_{t=1}^\infty S_t( \mathbf{w} ) </math>

and

<math> H_t( \mathbf{w} ) \ \stackrel{\mathrm{def}}{=}\ K_t ( \mathbf{w} ) + \lambda S_t ( \mathbf{w} ) </math>

where optimization of S maximizes smoothness and <math> \lambda </math> is known as a regularization parameter.

[edit] Training

Main article: Supervised learning

Choosing weights that optimize the objective function is known as "training" or "learning." Training is performed at each time step as data streams in.

[edit] Gradient descent training of the linear weights

Main article: Gradient descent

The simplest training algorithm is Gradient descent. In gradient descent training the weights are adjusted at each time step by moving them in a direction opposite from the gradient of the objective function

<math> \mathbf{w}(t+1) = \mathbf{w}(t) - \nu \frac {d} {d\mathbf{w}} H_t(\mathbf{w}) </math>

where <math> \nu </math> is a "learning parameter."

For the case of training the linear weights, <math> a_i </math>, the algorithm becomes

<math> a_i (t+1) = a_i(t) + \nu \big [ y(t) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] \rho \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big ) </math>

in the unnormalized case and

<math> a_i (t+1) = a_i(t) + \nu \big [ y(t) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] u \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big ) </math>

in the normalized case.

For local-linear-architectures gradient-descent training is

<math> e_{ij} (t+1) = e_{ij}(t) + \nu \big [ y(t) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] v_{ij} \big ( \mathbf{x}(t) - \mathbf{c}_i \big ) </math>

[edit] Projection operator training of the linear weights

For the case of training the linear weights, <math> a_i </math> and <math> e_{ij} </math>, the algorithm becomes

<math> a_i (t+1) = a_i(t) + \nu \big [ y(t) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] \frac {\rho \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} {\sum_{i=1}^N \rho^2 \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} </math>

in the unnormalized case and

<math> a_i (t+1) = a_i(t) + \nu \big [ y(t) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] \frac {u \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} {\sum_{i=1}^N u^2 \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} </math>

in the normalized case and

<math> e_{ij} (t+1) = e_{ij}(t) + \nu \big [ y(t) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] \frac { v_{ij} \big ( \mathbf{x}(t) - \mathbf{c}_i \big ) } {\sum_{i=1}^N \sum_{j=1}^n v_{ij}^2 \big ( \mathbf{x}(t) - \mathbf{c}_i \big ) } </math>

in the local-linear case.

For one basis function, projection operator training reduces to Newton's method.

[edit] Training the basis function centers

Basis function centers can be chosen from exemplars of the input data or they can be trained on the input data using self-organizing maps or unsupervised learning.

[edit] Examples

[edit] Logistic map

The basic properties of radial basis functions can be illustrated with a simple mathematical map, the logistic map, which maps the unit interval onto itself. It can be used to generate a convenient prototype data stream. The logistic map can be used to explore function approximation, time series prediction, and control theory. The map originated from the field of population dynamics and became the prototype chaotic time series. The map, in the fully chaotic regime, is given by

<math> x(t+1)\ \stackrel{\mathrm{def}}{=}\ f\left [ x(t)\right ] = 4 x(t) \left [ 1-x(t) \right ] </math>

where t is a time index. The value of x at time t+1 is a parabolic function of x at time t. This equation represents the underlying geometry of the chaotic time series generated by the logistic map.

Generation of the time series from this equation is the forward problem. The examples here illustrate the inverse problem; identification of the the underlying dynamics, or fundamental equation, of the logistic map from exemplars of the time series. The goal is to find an estimate

<math> x(t+1) = f \left [ x(t) \right ] \approx \varphi(t) = \varphi \left [ x(t)\right ] </math>

for f.

[edit] Function approximation

[edit] Unnormalized radial basis functions

The architecture is

<math> \varphi ( \mathbf{x} ) \ \stackrel{\mathrm{def}}{=}\ \sum_{i=1}^N a_i \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>

where

<math> \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) = \exp \left[ -\beta \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert ^2 \right] = \exp \left[ -\beta \left ( x(t) - c_i \right ) ^2 \right] </math>.

Since the input is a scalar rather than a vector, the input dimension is one. We choose the number of basis functions as N=5 and the size of the training set to be 100 exemplars generated by the chaotic time series. The weight <math> \beta </math> is taken to be a constant equal to 5. The weights <math> c_i </math> are five exemplars from the time series. The weights <math> a_i </math> are trained with projection operator training:

<math> a_i (t+1) = a_i(t) + \nu \big [ x(t+1) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] \frac {\rho \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} {\sum_{i=1}^N \rho^2 \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} </math>

where the learning rate <math> \nu </math> is taken to be 0.3. The training is performed with one pass through the 100 training points. The rms error is 0.15.

[edit] Normalized radial basis functions

The normalized RBF architecture is

<math> \varphi ( \mathbf{x} ) \ \stackrel{\mathrm{def}}{=}\ \frac { \sum_{i=1}^N a_i \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } { \sum_{i=1}^N \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } = \sum_{i=1}^N a_i u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) </math>

where

<math> u \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) \ \stackrel{\mathrm{def}}{=}\ \frac { \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } { \sum_{i=1}^N \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) } </math>.

Again:

<math> \rho \big ( \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert \big ) = \exp \left[ -\beta \left \Vert \mathbf{x} - \mathbf{c}_i \right \Vert ^2 \right] = \exp \left[ -\beta \left ( x(t) - c_i \right ) ^2 \right] </math>.

Again, we choose the number of basis functions as five and the size of the training set to be 100 exemplars generated by the chaotic time series. The weight <math> \beta </math> is taken to be a constant equal to 6. The weights <math> c_i </math> are five exemplars from the time series. The weights <math> a_i </math> are trained with projection operator training:

<math> a_i (t+1) = a_i(t) + \nu \big [ x(t+1) - \varphi \big ( \mathbf{x}(t), \mathbf{w} \big ) \big ] \frac {u \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} {\sum_{i=1}^N u^2 \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} </math>

where the learning rate <math> \nu </math> is again taken to be 0.3. The training is performed with one pass through the 100 training points. The rms error on a test set of 100 exemplars is 0.084, smaller than the unnormalized error. Normalization yields accuracy improvement. Typically accuracy with normalized basis functions increases even more over unnormalized functions as input dimensionality increases.

[edit] Time series prediction

Once the underlyting geometry of the time series is estimated as in the previous examples, a prediction for the time series can be made by iteration:

<math> \varphi(0) = x(1)</math>

<math> {x}(t) \approx \varphi(t-1) </math>

<math> {x}(t+1) \approx \varphi(t)=\varphi [\varphi(t-1)]</math>.

A comparison of the actual and estimated time series is displayed in the figure. The estimated times series starts out at time zero with an exact knowledge of x(0). It then uses the estimate of the dynamics to update the the time series estimate for several time steps.

Note that the estimate is accurate for only a few time steps. This is a general characteristic of chaotic time series. This is a property of the sensitive dependence on initial conditions common to chaotic time series. A small initial error is amplified with time. A measure of the divergence of time series with nearly identical initial conditions is known as the Lyapunov exponent.

[edit] Control of a chaotic time series

We assume the output of the logistic map can be manipulated through a control parameter <math> c[ x(t),t] </math> such that

<math> {x}^{ }_{ }(t+1) = 4 x(t) [1-x(t)] +c[x(t),t] </math>.

The goal is to choose the control parameter in such a way as to drive the time series to a desired output <math> d(t) </math>. This can be done if we choose the control paramer to be

<math> c^{ }_{ }[x(t),t] \ \stackrel{\mathrm{def}}{=}\ -\varphi [x(t)] + d(t+1) </math>

where

<math> \varphi[x(t)] \approx f[x(t)] = x(t+1)- c[x(t),t] </math>

is an approximation to the underlying natural dynamics of the system.

The learning algorithm is given by

<math> a_i (t+1) = a_i(t) + \nu \varepsilon \frac {u \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} {\sum_{i=1}^N u^2 \big ( \left \Vert \mathbf{x}(t) - \mathbf{c}_i \right \Vert \big )} </math>

where

<math> \varepsilon \ \stackrel{\mathrm{def}}{=}\ f[x(t)] - \varphi [x(t)] = x(t+1)- c[x(t),t] - \varphi [x(t)] = x(t+1) - d(t+1) </math>.

[edit] See also

• Artificial neural networks
• Predictive analytics
• Chaos theory
• Autoregressive moving average model
• Autoregressive integrated moving average
• Autoregressive conditional heteroskedasticity
• Mitchell Feigenbaum

[edit] External links

• Model Predictive Control with radial basis functions
• Control of a negative ion source

[edit] References

• J. Moody and C. J. Darken, "Fast learning in networks of locally tuned processing units," Neural Computation, 1, 281-294 (1989). Also see Radial basis function networks according to Moody and Darken
• T. Poggio and F. Girosi, "Networks for approximation and learning," Proc. IEEE 78(9), 1484-1487 (1990).
• Roger D. Jones, Y. C. Lee, C. W. Barnes, G. W. Flake, K. Lee, P. S. Lewis, and S. Qian, “Function approximation and time series prediction with neural networks,” Proceedings of the International Joint Conference on Neural Networks, June 17-21, p. I-649 (1990).
• Martin D. Buhmann, M. J. Ablowitz (2003). Radial Basis Functions : Theory and Implementations. Cambridge University. ISBN 0-521-63338-9.
• Yee, Paul V. and Haykin, Simon (2001). Regularized Radial Basis Function Networks: Theory and Applications. John Wiley. ISBN 0-471-35349-3.
• John R. Davies, Stephen V. Coggeshall, Roger D. Jones, and Daniel Schutzer, "Intelligent Security Systems," in Freedman, Roy S., Flein, Robert A., and Lederman, Jess, Editors (1995). Artificial Intelligence in the Capital Markets. Chicago: Irwin. ISBN 1-55738-811-3.bg:Невронна мрежа

de:Radiale Basisfunktion es:Red neuronal artificial fr:Réseau de neurones ko:신경망 hr:neuronska mreža ja:ニューラルネットワーク pl:Sieć neuronowa pt:Rede neural ro:Reţele neuronale ru:Нейронная сеть sl:nevronska mreža zh:神经网络