Decision Trees

 Machine Leaning is about predicting the future based on the past. This means making informed guesses about some unobserved properties of object. 

Learning is when an agent is able to extrapolate new data based on old data requirements and measurements. Learning tests the ability of one to generalize. Consider a course recommendation system for undergraduate students, and each student has taken a subset of courses, and we want to score for -2(terrible) to +2(awesome). Examples are the objects the algorithm will make predictions about. 

The core of machine learning is predicting the future based on the past. The general framework that is given is that we are given training data in which the algorithm is expected to learn and our learning algorithm will induce a function f that will map out a new example to a corresponding prediction. We always make the test factor a secret. We want to maximize the performance of the test data. 

Regression is trying to predict a real value (value of stock). Binary Classification is trying to predict a simple yes/no response. Multiclass classification is trying to put an example into one of a number of classes, and ranking is trying to put a set of objects in the order of relevance. 

The classic or natural model of machine learning is the decision tree, embodying the divide and conquer notion. You answer yes and no, and then can predict something else. We can write our set of answers in a question format and then predict whether a student liked a course or not.  

In order to learn training data is given and then from the training data you must construct your questions. We can look at the histogram of whether or not a student likes a course, then predict from there. We build histograms of sets as a result:

Then repeat this computation for each of the available features. We need to figure out how to choose subsequent features in the divide steps. Conquer step is to recurse and run the same routine. You need to create leaf nodes and guess the most prevalent answer no matter what regardless. 

DecisionTreeTrain(data, remaining features) 

    guess <= most frequent answer in data

    if the labels in data are unambiguous then

        return LEAF(guess)

    else if remaining features is empty then

        return LEAF(guess)

    else

        for all f in remaining features do

            No <= the subset of data which f = no

            Yes <= the subset of data f = yes

        score[f] = #answer in no + #answer in yes

        endfor

        f <= the feature with maximal score(f) 

        NO <= subset of data which f = NO

        YES <= subset of data which f = YES

        left <== DecisionTreeTrain(NO, remaining features \ {f})

        right <== DecisionTreeTrain(YES, remaining features \ {f})

        return NODE(f, left, right)

    end if 

         

A decision tree takes in data and a set of unused features, and returns a leaf node containing the most likely guess at a point; else, it loops over all the remaining features to loop over the one with the highest score. It constructs left and right subtrees by recursing itself and using one of the partitions of data and removes the features in consideration, until it reaches a leaf. 

A performance of a learning algorithm should be measured on the unseen "test" data, the way we measure performance should depend on the problem we are trying to solve, and there should be a strong relationship between the data the algorithm sees at the training time and the data that it sees at the test time. 

A loss function L tells us how "bad" a system prediction is in comparison to the truth. 

Regression is measured as L(x, y) = (x - y)^2 and absolute loss is L(x,y) = |x - y|.

Binary classification and multiclass classification have a loss of 0 if an element matches and 1 otherwise. We will use the probabilistic model of learning. The probability distribution over input/output pairs is called a data-generating distribution. It gives high probability to reasonable pairs and low probability to unreasonable pairs. We don't know what the data distribution is, all we get is a random sample of it. Our learning problem is defined by the following:

Loss function l, which captures the notion of what is important to learn, as well as the data generating distribution which defines what sort of data that we expect to see. Training data is a random sample of the input and output pairs and we need to induce a function that maps inputs to corresponding predictions, and we need to figure out the expected loss and minimize it, which leads us to compute our training errors:

The training error is the average error of the training diagram. We want to access our training error while minimizing the expected error, and generalize beyond the training error to some future data that has not been seen yet. 

This is the formal definition of machine learning: 

Given a loss function l and a sample d from some unknown distribution D, you must compute a function f that has low expected error e over D in respect to l. Make sure not to overtrain classifier data. You should be able to use decision trees to do machine learning. A useful way to think about learning is the geometric view of data. You select a model, use data to avoid underfitting and overfitting, and then use test data to estimate future model performance.