Inductive learning is learning from examples.

The inductive learning hypothesis says any hypothesis found to approximate the target function well over a sufficiently large set of training examples will also approximate the target function well over other unobserved examples.

Decision Trees

A decision tree is used to approximate discrete-valued target functions, it is a disjunction of conjunctions of constraints on feature values of instances / data points. The learnt trees are effectively sets of if-then rules.

Each node is a test of the value of a feature for a data point. Each leaf node is the value to be returned.

Example decision tree

Given the dataset:

We may generate the tree:

Trivially, there exists a consistent decision tree for any training set where we have one path to each leaf for each example. Path tests each feature in turn and follows value for example.

However this will not generalise, we prefer to find more compact decision trees.

After we pick a feature, one of five things can happen:

1. Remaining examples are positive, we are done and answer “yes”.
2. Remaining examples are negative, we are done and answer “no”.
3. There are some positive / negative examples, choose best feature to split on.
4. If there are no examples left, we must return a default value. We could use plurality classification: best guess based on parent node. Could be majority, i.e. yes if most examples at parent are “yes”. Could be random pick, weighted by ratio of examples at parent node.
5. If there are no features left, but there are still positive / negative examples then we could use plurality classification. This may occur due to noise / unobservability of features.

Decision Tree Learning Algorithm

def DTL(examples, attributes, parent_examples):
	if examples is empty:
		return plurality_value(parent_examples)
	else if all examples have same classification:
		return common_classification(examples)
	else:
		best = most_important_attribute(attributes, examples)
		tree = new decision tree with root best
		for value in best:
			examples = { elements of examples with best = value }
			remaining_attributes = attributes - best
			subtree = DTL(examples, remaining_attributes, examples)
			add branch to tree with label value and subtree
	return tree

Entropy

We will measure information in a feature by looking at how it reduces entropy.

Entropy (probability distribution)

Entropy in a probability distribution $⟨P_1,\dots ,P_n⟩$ is $H(⟨P_1,\dots ,P_n⟩)={\sum }_{i=1}^n-P_i{\log }_2{P}_i$Maximum for a uniform distribution, minimum for a single point.

Link to original

log2

$${\log }_2(x)=\frac{{\log }_{10}(x)}{{\log }_{10}(2)}$$Link to original

Suppose we have a set $S$ of $p$ positive and $n$ negative examples at the root. If we had to pick the class at this point, we could compute probability based on examples.

Chance of Class $=1$ would be $p(Class=1)=\frac{p}{p+n}$. So we have a probability distribution over classes, and we can compute the entropy of $S$: $H(S)=H\left(\begin{array}{c}⟨\frac{p}{p+n},\frac{n}{p+n}⟩\end{array}\right)$

Example: for 12 restaurant examples, $p=n=6$ so the entropy is $1$.

Information Gain

Information gain (entropy)

A feature $A$ splits the examples $S$ into subsets $S_i$, each of these subsets is a new branch in the decision tree which have their own entropy. We can measure how ‘good’ $A$ is by the reduction in entropy of $S$ and entropy of all of the $S_i$, this difference is called the information gain:

$$\text{Gain}(S,A)=H(S)-\sum _i\frac{|S_i|}{|S|}H(S_I)$$

So the entropy of $S_i$ collectively is the weighted sum of their entropies.

Link to original

Example: putting it all together

Assuming $S_i$ has $p_i$ positive and $n_i$ negative examples, the entropy is: $H(S_i)=H\left(\begin{array}{c}⟨\frac{p_i}{p_i+n_i},\frac{n_i}{p_i+n_i}⟩\end{array}\right)$

And so the gain is: $\text{Gain(S,A)}=H(S)-{\sum }_i\frac{p_i+n_i}{p+n}H\left(\begin{array}{c}⟨\frac{p_i}{p_i+n_i},\frac{n_i}{p_i+n_i}⟩\end{array}\right)$

The feature $A$ with the biggest $\text{Gain}(S,\text{A})$ is the one to pick.

https://git.is.horse/insert/university/algorithms/-/blob/master/ml1/entropy.py

Information gain has an inherent bias, it favours features that have many values.

Imagine if you add a restaurant name or time to the example: the name creates a unique classification (hence information gain would have its highest value for this feature) With enough precision, time would also uniquely identify each case.

Gain Ratio

Gain Ratio

Gain Ratio is a new metric that incorporates another metric split information that penalises features with lots of values (we ask what the value of the feature is):

$$\begin{array}{rl}\text{SplitInformation}(S,A)& =-\sum _i\frac{|S_i|}{|S|}{\log }_2\frac{|S_i|}{|S|}\\ \text{GainRatio}(S,A)& =\frac{\text{Gain}(S,A)}{\text{SplitInformation(S,A)}}\end{array}$$

We now use gain ratio as the new way of picking the best feature.

Link to original

Gini Ratio

Gini impurity is an alternative to choose best features. Suppose we have a set $S$ of $p$ positive and $n$ negative examples at root, we assign a probability based on the number of examples. $p(\text{Class}=\top )=\frac{p}{p+n}$

Gini Ratio

The Gini Ratio (Gini Impurity) is a measure of statistical dispersion, i.e. a measure of inequality (probability of this classification mislabelling a randomly selected example):

$$\text{G}(S)=1-\sum _{i=1}^c{p}_i^2$$

Where $c$ is the number of classes.

Link to original

Example: putting it together

Now if we have just two classes, we find: $G(S)=1-\left(\begin{array}{c}{\left(\begin{array}{c}\frac{p}{p+n}\end{array}\right)}^2+{\left(\begin{array}{c}\frac{n}{p+n}\end{array}\right)}^2\end{array}\right)$

If we have a feature $A$ that splits $S$ into subsets $S_i$, then the Gini impurity of these sets is $G(S,A)={\sum }_i\frac{|S_i|}{|S|}G(S_i)$ To pick a feature, we calculate $G(S,A)$ for each feature, and pick the feature with the lowest impurity.

Overfitting

The DTL grows the tree just enough to perfectly classify all examples however it can easily lead to overfitting if:

• the set is too small; or
• the set contains noise

Given two decision trees $d$ and $d^{\prime }$, $d$ is said to overfit the training data if:

1. $d$ has a smaller error than $d^{\prime }$ on the training data
2. $d^{\prime }$ has a smaller error than $d$ on all other instances

Two main approaches to prevent overfitting are:

1. Stop growing tree earlier (don’t get to point of overfitting)
2. (possibly) overfit then prune the tree (seems more successful)

Reduced error pruning

In reduced error pruning:

• consider every branch in tree as a candidate for pruning
• remove the branch, make the root of the branch into a leaf
• use plurality classification for examples at leaf
• test the new tree
• keep a branch pruned if the pruned tree performs better on some validation set than the original tree did
• repeat while it is possible to prune a branch and improve performance

However we now need (1) training data, (2) pruning data, and (3) test data. (this is a problem when data is limited, so we take another approach)

Rule post-pruning

In rule post-pruning (a solution to pruning with limited data):

1. Build decision tree as before
2. Create a rule set One rule for each path from root to leaf
3. Remove preconditions (feature tests) from rules if that improves their accuracy
4. Sort rules by accuracy and apply them in order / sequence when classifying examples

Broadening decision tree approach

Briefly covered

• Multivalued features: when features have many values, information gain gives inappropriate estimate of the usefulness of the feature e.g. convert these to boolean tests
• Continuous / integer input features: infinite sets of possible values Modify our approach to identify split points which give highest information gain e.g. $\text{weight}>160$
• Continuous output values When trying to predict continuous output values we need to create a regression tree which ends with a linear function

Slides 51-52 skipped.

Linear regression

Linear regression is learning a linear function of continuous inputs. The (univariate) equation is of the form: $h_w(x)=w_{1}x+w_0$ Where $w$ subscript indicates the vector $[w_0,w_1]$. Our goal is to estimate $w_0$ and $w_1$ from the data.

Example: predict house prices by floor area

We want to find the $h_w$ that best fits the data (choose $w$ so that $h_w$ is close to $y$ for our training examples). To fit the line, we find $[w_0,w_1]$ that minimise $\frac{\text{loss}}{\text{cost}}$.

We use the squared loss function $L_2$ to determine loss:

$$\begin{array}{rl}J(h_w)& =\text{Loss}(h_w)\\ & =\sum _{j=1}^N{L}_2(y_j,h_w(x_j))\\ & =\sum _{j=1}^N(y_j-h_w(x_j){)}^2\\ & =\sum _{j=1}^N(y_j-(w_1{x}_j+w_0){)}^2\end{array}$$

This is summed over all training examples, and where the data we have are pairs $(x_i,y_i)$ (this is the cost function). So we would like to find: (our optimisation objective)

$$w^{\ast }=\arg \underset{w}{\min }\text{Loss}(h_w)$$

We can plot the loss / cost function and produce something like this:

Similarly, this works with more axes:

Gradient descent algorithm

To choose the best $w$, we use the gradient descent algorithm which in effect:

• Start with some initial values for $w_0$, $w_1$
• Keep changing values until cost / loss function $J(h_w)$ is reduced For each $w_i$, we update with $w_i\leftarrow w_i-\alpha \frac{\partial }{\partial w_i}\text{Loss}(w)$ where $\alpha$ is the learning rate and controls how big of a step we take downhill.
  • if $\alpha$ is too small, then we take small steps and convergence takes long
  • if $\alpha$ is too large, we might miss the minimum and not converge
• Continue until we reach a minimum

The slope at the minimum is $0$ which means $\frac{\partial }{\partial w_i}\text{Loss}(w)=0$.

Batch gradient descent

Consider all the training examples simultaneously, and at each step update using:

$$\begin{array}{rl}{w}_0& \leftarrow w_0+\alpha \sum _j(y_j-h_w(x_j))\\ w_1& \leftarrow w_1+\alpha \sum _j(y_j-h_w(x_j))x_j\end{array}$$

• Guaranteed to converge.
• Can be slow since we need to compute for all $N$ examples at each step.

Stochastic gradient descent

Alternatively, we could do

$$\begin{array}{rl}{w}_0& \leftarrow w_0+\alpha (y-h_w(x))\\ w_1& \leftarrow w_1+\alpha (y-h_w(x))x\end{array}$$

for each of the $N$ examples in turn.

• Often much quicker.
• If learning rate is constant, may not converge.

Multivariate linear regression

Now consider we have more variables: $x_{j,1},\dots ,x_{j,i},\dots ,x_{j,n}$ and we are interested in a vector of weights $w_i$:

• We simplify handling of the wights by creating a dummy attribute to pair with $w_0$: $x_{j,0}=1$
• Then $h_w(x_j)$ is just the weighted sum of the variable values: $h_w(x_j)={\sum }_{i=0}^{i=n}{w}_i{x}_{j,i}$

We learn as before by doing gradient descent:

• Batch gradient descent: $w_i\leftarrow w_i+\alpha {\sum }_j(y_j-h_w(x_j))x_{j,i}$
• Stochastic gradient descent: $w_i\leftarrow w_i+\alpha (y_j-h_W(x_j))x_{j,i}$

We adjust more weights each time.

But we have to avoid overfitting, so we add a regularisation term to the loss function: ${\text{Loss}}^{\prime }(h)=\text{Loss}(h)+\lambda \text{Complexity}(h)$ Where $\text{Complexity}(h_w)={\sum }_i{w}_i^2$. By intuition, smaller $w$ gives smaller functions $h_W$. $\lambda$ is the regularisation parameter which is the trade-off between fitting the data and having a simple function.

Linear classifiers

We can turn a linear function into a classifier, the function defines the decision boundary that separates the two classes.

Example: seismic data due to earthquakes and nuclear explosions

The linear separator is $x_2=1.7x_1-4.9$ or $-4.9+1.7x_1-x_2=0$

Explosions are to the right of the line: $-4.9+1.7x_1-x_2>0$

Hence we do classification as follows: $h_w(x_j)=1\text{ if }{\sum }_{i=0}^{i=n}{w}_i{x}_{j,i}>0$ otherwise the classifier returns $0$.

Learning curve for linear classifier

Typically variation across runs is very large, the curve is not smooth because boundary is hard: so we can misclassify a lot of examples even a long way into learning.

It can be worse if the data is noisy.

Logistic regression

The linear classifier always predicts $0$ or $1$, even for examples close to the boundary. In many tasks, we need more gradated predictions.

We can soften the threshold function (approximate hard threshold with continuous function) hence we use the logistic function as a threshold: $h_w(x)=\frac{1}{1+e^{-w\cdot x}}$

The update function therefore becomes: $w_i\leftarrow w_i+\alpha (y-h_w(x))\cdot h_w(x)(1-h_w(x))\cdot x_i$

"commonly uses cross-entropy loss function" whatever that means???

Convergence is slower, but behaves much more predictably.

Issues with linear separability

We cannot represent $x_1\oplus x_2$ with a single linear model.

Ensemble methods

Every classifier has an error rate - will always misclassify some examples. We can use an ensemble to improve on this, i.e. take $N$ classifiers and use them on the same example by having them vote on the classification.

For a binary classification and $5$ classifiers, error rate drops from (for example) $10\%$ to less than $1\%$. Assuming the classifiers are independent / different enough.

Boosting extends the idea of an ensemble, in which higher weighted examples are counted as more important during training (e.g. we put more copies into the training set).

Example

Say we start with all examples of equal weight, learning classifier $h_1$.

• Test it and increase weights of misclassified examples, and learn $h_2$.
• Repeat a few times.
• Final ensemble is the combination of all classifiers, weighted by how well they perform on the training set.

AdaBoost

The AdaBoost algorithm is a commonly used approach to boosting. Given an initial classifier that is slightly better than random (weak model), AdaBoost can generate an ensemble that will perfectly classify the training set.

Bagging (bootstrap aggregation): given a training set $\mathcal{D}$, we create multiple training sets ${\mathcal{D}}_1,\dots ,{\mathcal{D}}_n$ which from each we learn a classifier. To classify an example, we combine the results of the ensemble. The ${\mathcal{D}}_i$ are sampled from $\mathcal{D}$ with a uniform distribution (with replacement).

To combine results, we typically use voting, but we can use averages too.

what the fuck are you going on about!!!!

random forests:

random subspace method: