wGMDH :: Selectional Combinatorial GMDH

Selectional Combinatorial GMDH

We will briefly describe a general idea of the Selectional Combinatorial GMDH algorithm according to [1], albeit using a somewhat different terminology, in context of multivariate smooth-function regression. Informally, the problem of regression by GMDH can be stated as follows: out of a set of measurements, model the dependent variable as a function of explanatory variables (regressors) optimally, according to some error criterion, where the function of dependency is represented by a GMDH network.

In order to define the manner in which GMDH networks get constructed, it is necessary to first introduce the basic building-blocks of GMDH networks and their connections. We discern two kinds of GMDH network primitives, see Fig. 1, the regressor nodes $\left \{ x_{i} \right \}_{i=0}^{L_{\lambda }}$ and the network nodes $\left \{ p_{\lambda j} \right \}_{\lambda =1}^{\Lambda}_{i=0}^{L_{\lambda}-1}$ , where $\Lambda$ represents the total number of GMDH layers with the network nodes and $L_{\lambda}$ represents the beam search width i.e. the predetermined number of best partial solutions (network nodes) kept as candidates in layer $\lambda$ .

Figure 1. Building the GMDH networks

Generally, the network node $p_{\lambda j}$ is a two-input node with a second-order polynomial as the output nonlinearity. The regressor node $x_{i}$ has no inputs, as it represents the regressor input into the network node. For example the network node $p_{\lambda i}$ is constructed in the following way:

$p_{\lambda i}=a_{\lambda i0}+a_{\lambda i1}z_{\lambda i1}+a_{\lambda i2}z_{\lambda i2}+a_{\lambda i3}z_{\lambda i1}^{2}+a_{\lambda i4}z_{\lambda i2}^{2}+a_{\lambda i5}z_{\lambda i1}z_{\lambda i2}$

where $z_{\lambda i1}$ and $z_{\lambda i2}$ can be either the regressor node or network node and $a_{\lambda i0},\cdots ,a_{\lambda i5}$ are the corresponding coefficients obtained by the polynomial regression.

The GMDH network is grown iteratively by inputting the nodes (either network or regressor nodes) to a new network node in a feedforward manner and performing low-order polynomial least-squares fitting to the dependent variable in order to obtain its coefficients. In that manner, the networks with complexities too small to capture the richness of dynamics of the process, which is modeled, can be used as inputs to a more complex network, better fitting the problem.

Still, finding the optimal structure of the network remains a problem due to the size of the space of possible solutions. To make the search feasible, a beam search is typically used in the GMDH algorithm. Keeping the algorithm tractable by such a constraint causes it to perform sub-optimally, but often a satisfactory sub-optimal solution suffices.

Let T and V be the training and the validation set, respectively, written in matrix form, with measurement instances concatenated as rows

$T=\left [ \left.\begin{matrix} x_{11}^{t} & x_{21}^{t} & \cdots & x_{K1}^{t}\\ x_{12}^{t} & x_{22}^{t} & \cdots & x_{K2}^{t}\\ \vdots & \vdots & \ddots & \vdots \\ x_{1M}^{t} & x_{2M}^{t} & \cdots & x_{KM}^{t} \end{matrix}\right|\begin{matrix}y_{1}^{t} \\ y_{2}^{t} \\ \vdots \\ y_{M}^{t} \end{matrix} \right ]=\left [ \left.\begin{matrix} \mathbf{x}_{1}^{t} & \mathbf{x}_{2}^{t} & \cdots & \mathbf{x}_{K}^{t} \end{matrix} \right| \mathbf{y}^{t} \right ]$

$V=\left [ \left.\begin{matrix} x_{11}^{v} & x_{21}^{v} & \cdots & x_{K1}^{v}\\ x_{12}^{v} & x_{22}^{v} & \cdots & x_{K2}^{v}\\ \vdots & \vdots & \ddots & \vdots \\ x_{1M}^{v} & x_{2M}^{v} & \cdots & x_{KM}^{v} \end{matrix}\right|\begin{matrix}y_{1}^{v} \\ y_{2}^{v} \\ \vdots \\ y_{M}^{v} \end{matrix} \right ]=\left [ \left.\begin{matrix} \mathbf{x}_{1}^{v} & \mathbf{x}_{2}^{v} & \cdots & \mathbf{x}_{K}^{v} \end{matrix} \right| \mathbf{y}^{v} \right ]$

where $\mathbf{x_{i}}$ is the i-th regressor with samples in rows, $\mathbf{y_{i}}$ the dependent variable with samples in rows, with superscripts t and v denoting the test and the validation set, respectively, K is the number of regressors, M and N are the sizes of the training and validation sets, respectively.