# treepartition

Tree-partitioned nonlinear function for nonlinear ARX models

## Description

A `treepartition` 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 `treepartition` unit functions that operate on a radial combination of inputs. Mathematically, `treepartition` 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 `treepartition` as the value of the `OutputFcn` property of an `idnlarx` model. For example, specify `treepartition` when you estimate an `idnlarx` model with the following command.

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

You can configure the `treepartition` 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 = treepartition``
``T = treepartition(numUnits)``

### Description

example

````T = treepartition` creates a `treepartition` 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 = treepartition(numUnits)` specifies the number of `treepartition` 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 information for signals used for estimation, specified as vectors of m property-specific values, where m is the number of input signals. The `Input` properties for each input signal are as follows:

• `Name` — Names of the input signals, specified as a 1-by-m string or character array, where m is the number of inputs

• `Mean` — Mean of the input signals, specified as a numeric scalar

• `Range` — Ranges of the input signals, specified as a 2-by-m numeric array that contains the minimum and maximum values

Output signal information, specified as property-specific values. The `Output` properties are as follows:

• `Name` — Name of the output signal, specified as a string or a character array

• `Mean` — Mean of the output signal, specified as a numeric scalar

• `Range` — Range of the output signal, specified as a 2-by-1 numeric array that contains the minimum and maximum values

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`.

• `Minimum` — Minimum bound on `Value`, specified as a 1-by-p vector. If `Minimum` is specified with a finite value and the starting value of `Value` is finite, then the software enforces that minimum bound during model estimation.

• `Maximum` — Maximum bound on `Value`, specified as a 1-by-p vector. If `Maximum` is specified with a finite value and the starting value of `Value` is finite, then the software enforces that maximum bound during model estimation.

• `SelectedInputIndex` — Indices of `treepartition` inputs (see `Input.Name`) that are used as inputs to the linear function, specified as an 1-by-nr integer vector, where nr is the number of inputs. The `RegressorUsage` property of the `idnlarx` model determines these indices.

The software computes the value of `LinearFcn` as `(X-X0)'*L`, where `X0` is the regressor mean.

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`.

• `Minimum` — Minimum bound on `Value`, specified as a numeric scalar or `–Inf`. If `Minimum` is specified with a finite value and the value of `Value` is finite, then the software enforces that minimum bound during model estimation. The default value is `-Inf`.

• `Maximum` — Maximum bound on `Value`, specified as a numeric scalar or `Inf`. If `Maximum` is specified with a finite value and the starting value of `Value` is finite, then the software enforces that maximum bound during model estimation. The default value is `Inf`.

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.`treepartition`, 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 `treepartition` 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`.

• `SelectedInputIndex` — Indices of `treepartition` inputs (see `Input.Name`) that are used as inputs to the nonlinear function, specified as an 1-by-nr integer vector, where nr is the number of inputs. The `RegressorUsage` property determines these indices.

• `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 a `treepartition` object with default settings.

`T = treepartition`
```T = Tree Partition Nonlinear Function: Tree Partition with number of units chosen automatically. Linear Function: uninitialized Output Offset: uninitialized Input: [1×1 idpack.Channel] Output: [1×1 idpack.Channel] LinearFcn: [1×1 nlident.internal.StructuredFcn] NonlinearFcn: [1×1 nlident.internal.TreeFcn] Offset: [1×1 nlident.internal.Offset] ```

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 Nonlinear Function: Tree Partition with 31 units. Linear Function: initialized to [1.19 -0.419 0.873 0.844] Output Offset: initialized to 0.249 Input: [1×1 idpack.Channel] Output: [1×1 idpack.Channel] LinearFcn: [1×1 nlident.internal.StructuredFcn] NonlinearFcn: [1×1 nlident.internal.TreeFcn] Offset: [1×1 nlident.internal.Offset] ```

`T` now has 31 nodes.

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

Create a `treepartition` object and use dot notation to set parameters.

```T = treepartition; 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.

`disp(sys.OutputFcn)`
```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 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 Input: [1×1 idpack.Channel] Output: [1×1 idpack.Channel] LinearFcn: [1×1 nlident.internal.StructuredFcn] NonlinearFcn: [1×1 nlident.internal.TreeFcn] Offset: [1×1 nlident.internal.Offset] ```
`disp(sys.OutputFcn.Input)`
``` Channel with properties: Name: [1×14 string] Mean: [0.2033 0.2035 0.2149 0.2159 0.0405 0.0338 0.0338 0.0338 0.0405 10.0493 10.0491 1 1 1] Range: [2×14 double] ```
`disp(sys.OutputFcn.Offset)`
```Output Offset (fixed to 0.2) Value: 0.2000 Minimum: -Inf Maximum: Inf Free: 0 ```
`disp(sys.OutputFcn.NonlinearFcn)`
``` TreeFcn with properties: NumberOfUnits: 15 Structure: [1×1 nlident.internal.TreeStructure] Parameters: [1×1 nlident.internal.TreeFcnParameters] Free: 1 SelectedInputIndex: [1 2 3 4 5 6 7 8 9 10 11 12 13 14] ```

## 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 `treepartition` 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'`, `treepartition` uses a noniterative technique for estimating parameters. Iterative refinements are not possible for models containing this nonlinearity estimator.

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

## Compatibility Considerations

expand all

Not recommended starting in R2021a 