noc19-cs33 Lec 29 Big Data Predictive Analytics (Part-II)

IIT Kanpur July 201
20 followers
Dec 3, 2023
Gradient boosted decision trees for regression, boosting, boosting it is a method of combining
outputs of many weak classifiers to produce a powerful ensemble.
There are several variants of boosting algorithms, AdaBoost, BrownBoost, LogitBoost and Gradient
Boosting.
Now we see in the big data that the size of the training examples are very large and also
a large number of large number of features describing the objects are present.
So therefore, this kind of scenario occurs in a situation of a big data.
So in this situation, it is very natural to assume that you would like to train a really
complex model even having such a great amount of data and hopefully this model will be accurate.
There are two basic ways in the machine learning to build the complex models.
The first one is that you have to start with a very complex model from the very beginning
and fits its parameters with the data.
So this is exactly the way how the neural networks operates.
So they operate with a very complex model in the beginning itself and they will fit
the data, they will fit the parameters and the data will be now then predicted based
on that fitting of its parameters.
Now the second way is to build a complex model iteratively.
So we can build a complex model iteratively that is with each step requires the training
of a simple model.
So in the context of boosting, these models are called weak classifiers or the base classifier.
Therefore, it is an ensemble of weak classifiers and which makes this particular model iteratively.
Let us see the regression, how this particular concept can be applied in the regression in
a gradient boosted decision trees.
So let us assume that there are samples which are given which are specified by z where x1
is the set of features in the data set and y1 is the level and x1 to xn are n different
samples in the training data set.
Now the goal here is to find an fx using this training set so that this particular minimum
of fx minus y square and the summation of this is the minimum such error will be there
and so at the test set given the test set this error should be the minimum one here
in this case.
How to build this fx is a question.
So how to build such an fx in boosting our goal is to find is to build the function fx
iteratively.
Suppose that this function fx is just a sum of other simple functions HM of x.
So in particular let us assume that each function HM is a decision tree.
So here each function is a decision tree and the aggregation of it is basically the fx
function.
Let us understand the gradient boosted decision trees for regression in more details.
So gradient boosted trees for regression problem.
So let us take the input set of n different data that is training data set which consists
of x is the set of features and yi consists of the labels.
So in turn this is the training data set of n different samples which are given as an
input to the gradient boosted trees for regression and M is the number of iterations and now
the step number 1 assumes the initial calculate the initial f 0x.
So that will be calculated by summing up all the label values and their average or their
mean is assigned over here.
So it will take the mean of the label values from the training data set and that becomes
f 0 or the initial f 0 function, initial fx function.
Now then it will iterate for M iterations wherein it will calculate the residual which
is yi cap is nothing but yi minus this residual of M minus 1 that is the previous iteration
and so here it will be 0 residual and so residuals are nothing but the differences of values
in the actual label and the predicted labels that is called the residual.
Now this after that the next step would be to fit a decision tree HM to the targets that
is yi cap and then it that means it will generate an auxiliary training set out of this particular
set wherein yi cap will be replaced here as the labels as the new labels which are
nothing but the residuals and then fm of x will be calculated by giving up particular
regularization coefficient and therefore it will calculate the value of fm and in this
manner it will iterate and compute all that things.
Now as far as regularization coefficient that is nothing but I mean it is recommended to
be less than 0.1 here in this case this is going to be important parameter in this gradient
boosted trees for regression.
So here you might have noticed that gradient boosting is somewhat similar to the gradient
descent in the optimization theory that if we want to minimize the function in the optimization
theory using gradient descent we make a small steps in the direction opposite to the gradient.
So gradient of a function by definition is a vector which points to the direction with
the fastest increase since we want to minimize the function we must move to the direction
opposite to the gradient to ensure the convergence we must make very small steps.
So you are multiplying each gradient by a small constant which is called a step size.
It is very similar to what we do in the gradient boosting.
So gradient boosting is considered minimization in the functional space that is fm of x is
nothing but f0 of x plus v times h1 of x plus v times h2 of x and so on.
So boosting is the minimization in the functional space.
So let us see the summary and boosting is the method for combining the outputs of many
weak classifiers or the regressors to produce a powerful ensemble and gradient boosting
is a gradient descent minimization of the target functions in the functional space.
So gradient boosting with the decision tree is considered to be the best algorithm for
general purpose classification or the regression problem.
Now let us see the gradient boosted decision trees for classification problem.
Let us assume that the training set which is given that is z comprises of x1, y1 and
y2 and so on up to xn, yn wherein x1 is nothing but they are the features and y1 is nothing
but the class labels.
So here there will be a class label y because this is a classification problem.
So the classes lies between lies 0 and 1.
So class labels let us assume that it is 0 and 1.
So these will be assigned as the labels in the training data set.
Now goal here is to find out that effects using the training data set such that it will
minimize this particular function that is the summation of fx which is not equal to
the label of y.
So that means the label fx is the predicted value and y is the target label if it is not
matching so that becomes an error and the summation of all such misclassification.
So the summation of so the aggregation of misclassification is to be minimized.
So that should be the value of fx which can achieve this so that this particular prediction
can be applied on the test data set.
So test data set consists of x1, y1, x2, y2 and so on up to xn.
So how to build this fx is the problem of gradient boosted decision trees.
So gradient boosted trees for classification here we have to see how we are going to build
such a function fx.
So we use the probabilistic method by using the following expression.
So the probability where y is equal to 1 given x is given by this equation that is 1 upon
1 plus exponential of minus to the risk power of summation of m is equal to 1 to m hx where
hx is the decision tree.
So therefore the value of probability function lies between 0 to 1.
Therefore we model the probability of belonging of an object to the first class and here inside
the exponential there is a sum of H m's and each H m is a decision tree.
So we can easily check that each expression for the probability will always be between
0 and 1.
So it is the normal regular probability.
This particular function is called the sigmoid function which maps all the real values into
the range between 0 and 1.
So this particular sigmoid function is 1 upon 1 by 1 plus e raise power minus x.
So here also the same equation is appearing 1 by 1 plus exponential to the power of minus
fx.
This is called sigmoid function.
So let us denote the sum of H m's by fx.
It is an ensemble of decision trees.
Then you can write the probability of the belonging to a first class in a simple way
using fx and the main idea which is used here is called the principle of maximum likelihood.
So what is this principle of maximum likelihood?
So likelihood is the probability of absorbing some data given the statistical model.
If we have the data set with an object from 1 to n, then the probability of absorbing
such data set is the multiplication of probabilities of all single objects.
The multiplication is called likelihood.
And here that can be expressed likelihood as the multiplication of the probabilities
for all single objects that is nothing but probability of y1 given x1 dot probability
of y2 given x2 and so on to probability 1.
So therefore, it comes out to be the multiplication of all the probabilities and now likelihood
function we have to calculate.
So the principle of maximum likelihood can be given by this algorithm to find a function
fx which maximizing the likelihood which is equivalent to find fx maximizing the logarithmic
of the likelihood.
Since the logarithmic is the monotone function, so that can be represented here in this case
that the logarithmic of the probability of all y1 given x1 and this particular summation
here is called Qf and we have to find out the maximum of Qf that is which will maximize
the likelihood.
So we have to find out that fx which will maximize the likelihood.
Hence we have to fit a distribution in this data set by way of principle of maximum likelihood.
So we will denote it by Q of f, the logarithmic of the likelihood and now it is the sum of
all the logarithms of the probabilities and you are going to maximize this particular
function.
Now you will use the shorthand for this logarithmic that is L by yi and fx of i.
So it is the logarithmic of the probability and here we emphasize that this logarithm
depends actually on the true labels that is yi and our predicted values that is fx of
i.
So Q of f is the sum of the logarithm of yi and fx of i.
So logarithm of yi and fx of y is nothing but given as the log of the probability of
yi at given xi and which is nothing but Qf is nothing but the summation of all i's
from 1 to n and the logarithmic of yi and fx of i.
So yi is the true label for the i-th data object in the set and fx of i is the predicted
label and this logarithm of this is represented by this likelihood and the summation of this
is represented by this likelihood which has to be maximized for that Qf.
Let us see the gradient boosted trees for classification by putting it everything whatever
we have discussed.
Now the algorithm for gradient boosted trees for classification here the input set Z is
given as xi yi wherein xi you know that is a feature in the data set and yi is the labels
which are assigned as the categorical type that is labels are given and m is the number
of iterations and for the first class the part of the objects of the first class is
p of 1 and f0 of x is equal to log of p1 minus p1 by 1 minus p1 and for iterating between
from 1 to m, so we will find out the gradient that is gi is equal to differentiation of
this likelihood function L of yi and fm of xi.
So this will calculate divided by differentiation of fm of xi.
So this is called the gradient.
So gradients are calculated and then it will fit a decision tree hm of x to the target
gi.
So auxiliary training data set which is will be used here is that xi and x1 and then it
will be replaced by label will be replaced by the gradients and this will called an auxiliary
data set.
So given the auxiliary data set it will fit the decision tree that is called hm of xi
and wherein the rho value will be argmax of rho that is for q of fm minus 1 x plus rho
times hm of x.
So rho will be calculated and fm of x is equal to fm minus 1 of x plus v is the regularization
coefficient rho m and hm of xi.
So this process will in turn will give the ensemble of different values and so it will
do this kind of classification in this particular manner.
So let us see the stochastic boosting.
So gradient boosting trees for classification if we use this stochastic boosting then it
will be represented here in this case where this auxiliary set which is used as the training
data set will be now k is equal to 0.5 m will be created by the random sampling with
the replacement.
So this particular part here we are going to use the concept of the random forest for
the bootstrap generation of the data set.
So this is the gradient boosting gradient boosted trees plus stochastic boosting is
shown over here and this way sampling with the replacement is there.
So here we have to see that the size of the sample will be reduced by k is equal to 0.5
even that is here the auxiliary training set will be reduced by the size half and it
will be created by random sampling with the replacement and this is called the concept
of bagging which will be used over here in the stochastic boosting.
So sampling with the replacement is used but here the value of k will become half of the
size of the total features.
So here it will be half of that particular feature which will be taken up into the consideration
hence as we reduce the size this becomes more efficient this particular case.
So let us see the tips for the usage first of all it is important to understand how the
regularization parameter works in this figure we can see that the behavior of the gradient
boosted decision trees with the two variants we can see with the parameter 0.1 and 0.05
that is 0.05.
So we can see that this one 0.1 is not that accurate and 0.05 is more accurate.
So what happens here is that initially stage of the learning at the initially stage of
the learning the variant that is 0.1 is better but because it has the lower testing error
but later on so at each iteration you measure the testing error of our example of on the
hold out data but eventually the variant with the lower regularization that is 0.05 reach
the lower testing error finally this variant turns out to be the superior.
So it is very typical behavior and you should not stop your algorithm after several dozens
of iterations so you should proceed over until it converges.
So convergence happens when your testing error does not change a lot the variant with the
lower regularization converges more slowly but eventually it builds a better model.
So the recommended learning rate should be less than or equal to 0.1 that we have already
seen and the bigger your data set is the larger it will be the number of iterations it will
have.
So the recommended number of iteration ranges from several hundreds to the several thousands
also the more features you have in your data set the deeper will be your decision tree
and there are very general rules because the bigger your data set is the more features
you have the more complex model you can build without overfitting in this particular scenario.
So summary it is the best method for general purpose classification and regression problems.
So it automatically handles the interaction of the features because in the core it is
based on the decision trees which can combine several features in a single tree.
But also this algorithm is computationally scalable it can be effectively executed in
a distributed environment for example in the Spark.
So it can be executed on top of the Spark cluster.
But also this algorithm has very good predictive power but unfortunately the model are not
interpretable and that problem we have also seen in the random forest but here the predictive
power is better than the random forest.
So the final ensemble effect is very large and cannot be analyzed by the human experts.
So obviously it is not having the good interpretation of this due to the complex nature of this
particular model.
So there are always a trade-off in the machine learning between the predictive power and
interpretability because the more complex and accurate your model is the harder is the
analysis of this model to be interpreted by the humans.
Spark ML based decision trees and ensemble we have to see the programming aspect of it
how using Spark ML we will now use the decision tree and ensemble.
So here we will talk about Spark ML for doing classification regression with the ensemble
trees.
And first we will see that we have to first see the decision trees how the decision tree
will be implemented over Spark ML and then we can extend it for the random forest and
gradient boosted trees.
So the first step here is to create the Spark context and the Spark session which is shown
here in this particular steps that we have to create the Spark context and we have to
also create the Spark session and this Spark session is required for building the data
frame.
And then we can download the data set and now we can see the data set after downloading
the data set into data frames and then we can see the features that it has the data
has an ID number and the label that is categorical label which can be denoted by 0 and 1 or you
can say that it is M and B finally which will be converted into 1 and 0.
So this particular data set has the features and it has the labels and it has an ID.
So there are three different important parameters it has.
So let us take this particular case where all these important parts are there in the
data set.
So now we can further look into the data set.
We can see that these data set have so these data sets so these features are the result
of the analysis and it has around 569 different examples in the data set and first we all
need to transform this label which is given in M or B to the numeric value and using string
indexer object we can do this and that is the string indexer object will create this
into the label values into the numeric values and then we can create the data frame which
is stored in the distributed manner on the cluster.
So this particular data frame will be created with the label and the feature.
So these two part will be used in the data frame which will be input to our system.
So string indexer and then it will transform so that all the values will become here.
So all these labels will be converted into the values using a string indexer.
So now after index label index all these label values are converted from letter to the numeric
values.
So here you can have this numeric value either 1 or it is 0 as the label values.
So we have now two important things one is the feature and the other is label indexed
in the data frame which is shown over here.
This particular data frame will be now used for further analysis.
Now then we will make the training test splitting into the proportion 70 to 30 that means 70%
is the training portion and 30% will be the test portion of the data set.
So first we model with that 70% data set to train the model on a single decision tree
and then we will use the 30% of the data set for testing purpose.
So this is to be done in this particular manner using random split of 70 by 30 and then we
will train the decision tree model using decision tree classifier and we will apply the label
index in this particular case and then we will fit the decision tree on the training
data set.
So this will become this will build a model called decision tree model it will build and
this will be represented as DT model as the variable.
Now you can see this particular model has how many nodes, what is the depth and what
are the important features and so on and so after the so these things now we are making
the import decision tree classifier or we can create the class that is responsible for
the training and then we call the method fit to the training data and obtain the decision
tree model that we have shown.
Now so the training was done in a very fast manner and now we have to see the results.
So the number of nodes and depth of the decision tree and the feature importance and number
of features used in a decision tree and so on.
These different things we can inspect and now we are going to see the decision tree
and we can take this one.
So we can print this decision tree model and we can see that it is nothing but an if
then else and then that means all the internal nodes of a decision tree and finally the leap
will be having the predictions.
So once the decision tree is built now we can use this decision tree to for the test
data to obtain the predictions.
So now we can use the test data and use the same decision tree model and now we will perform
the predictions.
So the predictions are now there and then we will evaluate this particular the predictions
using multi-class classifier evaluator we will evaluate these predictions which are
done by this one decision tree for its accuracy.
So what we will find here is that that accuracy is very high and the error is very less and
so the testing error is only 30% so the model is quite accurate.
So with only 3% error the model is quite accurate and now we are going to see the another method
which is called a gradient boosted decision trees.
So first of all we import the data and then create the object which will do the classification
and here we are specifying the label column as label index that we have seen in the previous
example also and the features column as the features actually it is not mandatory to specify
the feature column.
We can do it either using the assignment or without this argument.
Now the thing is so after having done this now we will fit this particular model and
apply this particular gradient boosted classifier using labeled index and the features that
we have seen.
Now we will fit this particular model on to the training data set and we will get the
model that is gradient boosted decision tree model.
So once we obtain the model then we will see it is will then we will using this particular
model we will now apply the test data on it this particular model and now using a multi
class classification evaluator we will evaluate its predictions.
So let us see so this we are going to do 100 iterations and default step is 0.1.
So after that so we will see that here the accuracy here the error is here the test error
is quite so basically this has improved over the decision tree model.
Now we are going to see the random forest and random forest again the same data set
we will take and but here the classifier we are going to change as random forest classifier
and we will fit the training data on random forest classifier and we will get a model
which is called random forest model.
Now using this particular model we will now we will transform the test data we will apply
the test data on this particular model and get the predictions.
So now after getting the predictions we are now evaluating this particular predictions
using multi class classification evaluator and this will now evaluate its prediction
accuracies and this we will now be able to see that the test error is very less that
is than the previous decision trees hence this we can see that in this example the testing
accuracy of the random forest was the best with the other data sets the situation may
be quite different and general case the bigger your data set is more features it has the
quality of complex algorithm like gradient boosted or the forest will be much better.
Now let us see the class validation using Spark ML.
So class validation helps to assess the quality of machine learning model and to find the
best model among the family of the models first of all we have to create the Spark context
that is shown over here and then we will do the Spark session then we will build the
Spark session we will build the Spark session which will create the data frames and then
we will use the data set read the data set load the data file and now we will create
the data frames df as the input data frame and now we will apply after doing various
transformations now we will input data we can see it is already indexed now we have
to do the cross validation.
So what steps are required for doing cross validation with the data set so for example
we want to select the best parameters of a single decision tree and we create the object
decision tree then we should create the pipeline.
So here we are going to create the pipeline and in this pipeline stage we are only using
the decision tree based pipeline.
So then we will apply this cross validation using parameter builder and we have to also
see the cross validation so then we import their class validator and parameter grid builder
class and you are now creating the parameter grid builder class for example you want to
select the best maximum depth of the decision tree in the range from 1 to 8 and we now have
the parameter grid builder class and we create the evaluator so we want to select the model
that which has the best accuracy among others and using this all these parameters whatever
we have said now we are going to evaluate using multiclass classification evaluator
and now we will see the evaluator will now evaluate the cross validator and cross validator
will fit into the input function and it will select the best model into the different stages.
So we create the evaluator so we want to select the model which has the best accuracy among
others so we create a cross validator class and pass a pipeline into this class parameter
grid and the evaluator and finally we select the number of folds and the number of folds
should be not less than 5 or 10 and the number of folds we have selected and after that we
create the CV model and takes some time because Spark need to make the training and evaluation
the qualify the 10 times. Now we can see that the average accuracy amount of fold for each
of the failure of the tree depths now we can see and the first stage of our pipeline was
the decision tree so you can get the best model and the best model has the depth 6 and
it has 47 nodes in this case. Then we can view this model to make the prediction
at any other data sets so in parameter grid builder we can use several parameters for
example maximum depth and some other parameter of the decision tree for example minimum instances
per node and select some other grid here but in this example we did not do it due to the
simplicity and if we evaluate only one parameter the training is much faster.
So conclusion in this lecture we have discussed the concept of random forest gradient boosted
decision trees and we have also covered a case study using Spark ML programming on decision
trees and other learning tree ensembles. Thank you.
