Building the tree
As Breiman’s CART algorithm is widely used for creation of decision trees, random forest and boosted decision trees. In the CARTS algorithm, trees are grown by recursive partitioning of leaves, each time maximizing some task-specific criterion. It has the ability to learn non-linear models from both numerical and categoricaldata of various scales, and also has a relatively low training time complexity. Hence we will be using the same concept in building maximum margin interval trees.
The Learning Setting
The training data is a set of labelled examples, where the target values are intervals indicating a range of acceptable values: \[S = {(x_1,y_1), (x_2,y_2)... (x_n,y_n)}\] where \(x \epsilon R^n\) is the feature variable of the model and \(y = [\underline{y},\bar{y}]\) is the intervaled target data.
The Loss Function
We consider two types of losses, hinge and squared. As our target data is interval type, hence the loss inside the interval is zero and outside follow the linear or quadratic function. We aim to minimise the convex objective function for model \(h\) \[\phi_l(\underline{y_i}-h(x_i)+\epsilon) + \phi_l(h(x_i)-\bar{y_i}+\epsilon)\] where \(l\) is a convex function and \(\phi_l(x) = l[(x)+]\) is the loss, where \((x)_+\) is the positive part of the function and \(\epsilon\) as the margin hyperparameter with regularizing effect.
Linear hinge loss: \(l(x) = x\)
Squared hinge loss: \(l(x) = x^2\)
Splitting algorithm
As proposed in the paper, the splitting is done using margin-based loss function, which yields a sequence of convex optimization problems. A dynamic programming algorithm is used to compute the optimal solution to all of these problems in log-linear time. Hence obtaining the optimal splitting value.
Partitioning Leaf
The partitioning of the tree into left and right leaf is done using 2 convex minimization problem and considering the splitting index based on minimum cost of sum of cost of left and right leaves.
Dynamic programing
The dynamic programing algorithm is used to calculate the total loss of the optimal prediction. The sum of above mentioned hinge losses is a convex piecewise function \(Pt(\mu)\).
While tracking the functions minima, the dynamic programming algorithm maintains a pointer on the left-most breakpoint that is to the right of all minima of \(Pt(\mu)\). The optimization step consists in finding the new position of this pointer after a hinge loss is added to the sum.
In this Fig, First two steps of the dynamic programming algorithm for the data \(y_1= 4, s_1= 1, y_2= 1, s_2=−1\) and margin \(\epsilon = 1\), using the linear hinge loss \(l(x) = x\).
Left: The algorithm begins by creating a first breakpoint at \(b_{1,1} = y_1−\epsilon= 3\), with corresponding function \(f_{1,1}(\mu) =\mu−3\). At this time, we have \(j_1= 2\) and thus \(b_{1,j_1}=∞\). Note that the cost \(p_{1,1}\) before the first breakpoint is not yet stored by the algorithm.
Middle: The optimization step is to move the pointer to the minimum (\(J_1=j_1−1\)) and update the cost function, \(M_1(\mu) =p_{1,2}(\mu)−f_{1,1}(\mu)\).
Right: The algorithm adds the second breakpoint at \(b_{2,1}=y_2+\epsilon= 2\) with \(f_{2,1}(μ) =μ−2\). The cost at the pointer is not affected by the new data point, so the pointer does not move.
mmit()
This function is used to create the maximum margin interval trees. It returns the learned tree as a party object.
Usage:
mmit(feature.mat, target.mat, max_depth = Inf, margin = 0, loss = "hinge", min_sample = 1)
Example:
library(mmit)
target.mat <- rbind(
c(0,1), c(0,1), c(0,1),
c(2,3), c(2,3), c(2,3))
feature.mat <- rbind(
c(1,0,0), c(1,1,0), c(1,2,0),
c(1,3,0), c(1,4,0), c(1,5,0))
colnames(feature.mat) <- c("a", "b", "c")
feature.mat <- data.frame(feature.mat)
out <- mmit(feature.mat, target.mat)Output:
Prediction
The prediction is done using predict.mmit(). It fits the new data into the MMIT model to give prediction values
Usage:
predict.mmit(tree, newdata = NULL, perm = NULL)
Example:
library(mmit)
target.mat <- rbind(
c(0,1), c(0,1), c(0,1),
c(2,3), c(2,3), c(2,3))
feature.mat <- rbind(
c(1,0,0), c(1,1,0), c(1,2,0),
c(1,3,0), c(1,4,0), c(1,5,0))
colnames(feature.mat) <- c("a", "b", "c")
feature.mat <- data.frame(feature.mat)
tree <- mmit(feature.mat, target.mat)
pred <- predict.mmit(tree)Output:
## [1] 0.5 0.5 0.5 2.5 2.5 2.5
