# idTreePartition

Tree-partitioned nonlinear function for nonlinear ARX models

## Description

An `idTreePartition` object implements a tree-partitioned nonlinear function, and is a nonlinear mapping function for estimating nonlinear ARX models. The mapping function, which is also referred to as a nonlinearity, uses a combination of linear weights, an offset and a nonlinear function to compute its output. The nonlinear function contains `idTreePartition` unit functions that operate on a radial combination of inputs.

Mathematically, `idTreePartition` is a nonlinear function $y=F\left(x\right)$ that maps m inputs X(t) = [x(t1),x2(t),…,xm(t)]T to a scalar output y(t). F is a piecewise-linear (affine) function of x:

`$F\left(x\right)=xL+\left[1,x\right]{C}_{k}+d$`

Here, x belongs to the partition Pk. L is a 1-by-m vector, Ck is a 1-by-`m`+1 vector, and Pk is a partition of the x-space.

Use `idTreePartition` as the value of the `OutputFcn` property of an `idnlarx` model. For example, specify `idTreePartition` when you estimate an `idnlarx` model with the following command.

`sys = nlarx(data,regressors,idTreePartition)`
When `nlarx` estimates the model, it essentially estimates the parameters of the `idTreePartition` function.

You can configure the `idTreePartition` function to fix parameters. To omit the linear component, set `LinearFcn.Use` to `false`. Use `evaluate` to compute the output of the function for a given vector of inputs.

## Creation

### Syntax

``T = idTreePartition``
``T = idTreePartition(numUnits)``

### Description

example

````T = idTreePartition` creates a `idTreePartition` object `t` that is a binary tree nonlinear mapping object. The function computes the number of tree nodes J, represented by the property `NumberOfUnits`, automatically during estimation. The tree has the number of leaves equal to `2^(J+1)-1`. ```
````T = idTreePartition(numUnits)` specifies the number of `idTreePartition` nodes `numUnits`.```

### Input Arguments

expand all

Number of units, specified as `'auto'` or a positive integer. `numUnits` determines the number of tree nodes.

This argument sets the `T.NonlinearFcn.NumberOfUnits` property.

## Properties

expand all

Input signal names for the inputs to the mapping object, specified as a 1-by-m cell array, where m is the number of input signals. This property is determined during estimation.

Output signal name for the output of the mapping object, specified as a 1-by-1 cell array. This property is determined during estimation.

Parameters of the linear function, specified as follows:

• `Value` — Value of L, specified as a 1-by-m vector.

• `Free` — Option to update entries of `Value` during estimation. specified as a logical scalar. The software honors the `Free` specification only if the starting value of `Value` is finite. The default value is `true`.

The software computes the value of `LinearFcn` as `X'*L`.

Parameters of the offset term, specified as follows:

• `Value` — Offset value, specified as a scalar.

• `Free` — Option to update `Value` during estimation, specified as a scalar logical. The software honors the `Free` specification of `false` only if the value of `Value` is finite. The default value is `true`.

Parameters of the nonlinear function, specified as follows:

• `NumberOfUnits` — Number of units, specified as `'auto'` or a positive integer. `NumberOfUnits` determines the number of nodes N in the tree. When N is set to:

• `'auto'`, the software selects N by pruning.

• a positive integer before estimation, then the software sets N to the largest value of the form `2^(J+1)-1` less than this integer.

• `Parameters` — estimated parameter values.`idTreePartition`, specified as in the following table:

Field NameDescription
`SampleLength `Length of the estimation data
`NoiseVariance`Estimated variance of the noise in the estimation data
`Tree`

Structure that contains the tree parameters, as described in the following list:

• `TreeLevelPntr`: `N`-by-1 vector containing the levels `j` of each node.

• `AncestorDescendantPntr`: `N`-by-3 matrix, such that the entry `(k,1)` is the ancestor of node `k`, and entries `(k,2)` and `(k,3)` are the left and right descendants, respectively.

• `LocalizingVectors`: `N`-by-`(m+1)` matrix, such that the `r`th row is `B_r`.

• `LocalParVector`: `N`-by-`(m+1)` matrix, such that the `k`th row is `C_k`.

• `LocalCovMatrix`: `N`-by-`((m+1)m/2)` matrix such that the `k`th row is the covariance matrix of `C_k`. `C_k` is reshaped as a row vector.

• `Free` — Option to estimate parameters, specified as a logical scalar. If all the parameters have finite values, such as when the `idTreePartition` object corresponds to a previously estimated model, then setting `Free` to `false` causes the parameters of the nonlinear component of the function F(X) to remain unchanged during estimation. The default value is `true`.

• `Structure` — Advanced options that affect the initial model.

PropertyDescriptionDefault
`FinestCell`

Integer or character vector specifying the minimum number of data points in the smallest partition.

`'auto'`
`Threshold`Threshold parameter used by the adaptive pruning algorithm. Smaller threshold value corresponds to a shorter branch that is terminated by the active partition `D_a`. Higher threshold value results in a longer branch`1.0`
`Stabilizer`Penalty parameter of the penalized least-squares algorithm used to compute local parameter vectors `C_k`. Higher stabilizer value improves stability, but may deteriorate the accuracy of the least-square estimate.`1e-6`

## Examples

collapse all

`load iddata1 z1`

Create an `idTreePartition` object with default settings.

`T = idTreePartition`
```T = Tree Partition Nonlinear Function: Tree Partition with number of units chosen automatically Linear Function: uninitialized Output Offset: uninitialized Inputs: {1x0 cell} Outputs: {1x0 cell} NonlinearFcn: 'Tree structure' LinearFcn: 'Linear function parameters' Offset: 'Offset parameters' EstimationOptions: 'Estimation options' ```

Estimate a nonlinear ARX model using `T`.

`sys = nlarx(z1,[2 2 1],T);`

View the output function of `sys`.

`disp(sys.OutputFcn)`
```Tree Partition Inputs: y1(t-1), y1(t-2), u1(t-1), u1(t-2) Output: y1(t) Nonlinear Function: Tree Partition with 31 units Linear Function: initialized to [1.19 -0.419 0.873 0.844] Output Offset: initialized to 5.96e-17 Inputs: {'y1(t-1)' 'y1(t-2)' 'u1(t-1)' 'u1(t-2)'} Outputs: {'y1(t)'} NonlinearFcn: '<Tree structure>' LinearFcn: '<Linear function parameters>' Offset: '<Offset parameters>' EstimationOptions: '<Estimation options>' ```

`T` now has 31 nodes.

```load iddata7 z7 ze = z7(1:300);```

Create an `idTreePartition` object and use dot notation to set parameters.

```T = idTreePartition; T.Offset.Value = 0.2; T.Offset.Free = false; T.NonlinearFcn.NumberOfUnits = 30;```

Specify model regressors.

```Reg1 = linearRegressor({'y1','u1'},{1:4, 0:4}); Reg2 = polynomialRegressor({'y1','u1'},{1:2, 0:2},2);```

Estimate a nonlinear ARX model.

`sys = nlarx(ze, [Reg1;Reg2], T);`

View postestimation `OutputFcn` properties.

`sys.OutputFcn`
```ans = Tree Partition Inputs: y1(t-1), y1(t-2), y1(t-3), y1(t-4), u1(t), u1(t-1), u1(t-2), u1(t-3), u1(t-4), y1(t-1)^2, y1(t-2)^2, u1(t)^2, u1(t-1)^2, u1(t-2)^2 Output: y1(t) Nonlinear Function: Tree Partition with 15 units Linear Function: initialized to [0.0725 0.895 -0.0727 -0.475 0.0725 -0.106 0.0304 1.02 1.43 0.000459 -0.00473 0 0 0] Output Offset: fixed to 0.2 Inputs: {1x14 cell} Outputs: {'y1(t)'} NonlinearFcn: 'Tree structure' LinearFcn: 'Linear function parameters' Offset: 'Offset parameters' EstimationOptions: 'Estimation options' ```
`sys.OutputFcn.Input`
```ans = Function inputs Name: {1x14 cell} Mean: [-4.8010e-17 -3.6007e-17 -3.6007e-17 -1.2002e-17 9.0018e-17 ... ] Range: [2x14 double] ```
`disp(sys.OutputFcn.Offset)`
```Output Offset: fixed to 0.2 Value: 0.2000 Free: 0 ```
`sys.OutputFcn.NonlinearFcn`
```ans = Tree structure NumberOfUnits: 15 Parameters: 'Tree Partition parameters' Free: 1 Inputs: {1x14 cell} Outputs: {'y1(t):Nonlinear'} ```

## Algorithms

The mapping F is defined by a dyadic partition P of the x-space, such that on each partition element Pk, F is a linear mapping. When x belongs to Pk, F(x) is given by:

`$F\left(x\right)=xL+\left[1,x\right]{C}_{k}+d$`

where L is 1-by-m vector and d is a scalar common for all elements of partition. Ck is a 1-by-(m+1) vector.

The mapping F and associated partition P of the x-space are computed as follows:

1. Given the value of J, a dyadic tree with J levels and N = 2J–1 nodes is initialized.

2. Each node at level 1 < j < J has two descendants at level j + 1 and one parent at level j – 1.

• The root node at level 1 has two descendants.

• Nodes at level J are terminating leaves of the tree and have one parent.

3. One partition element is associated to each node k of the tree.

• The vector of coefficients Ck is computed using the observations on the corresponding partition element Pk by the penalized least-squares algorithm.

• When the node k is not a terminating leaf, the partition element Pk is cut into two to obtain the partition elements of descendant nodes. The cut is defined by the half-spaces (1,x)Bk > 0 or <=0 (move to left or right descendant), where Bk is chosen to improve the stability of least-square computation on the partitions at the descendant nodes.

4. When the value of the mapping F, defined by the `idTreePartition` object, is computed at x, an adaptive algorithm selects the active node k of the tree on the branch of partitions that contain x.

When the `Focus` option in `nlarxOptions` is `'prediction'`, `idTreePartition` uses a noniterative technique for estimating parameters. Iterative refinements are not possible for models containing this nonlinearity estimator.

You cannot use `idTreePartition` when `Focus` is `'simulation'` because this nonlinear mapping object is not differentiable. Minimization of simulation error requires differentiable nonlinear functions.

## Version History

Introduced in R2007a

expand all

Behavior changed in R2022a

Not recommended starting in R2021b

Not recommended starting in R2021a