For those of you interested in the fast growing areas of applications of Machine Learning, this article about Applications and techniques for fast machine learning in science may be interesting.
It has several interesting perspectives and highly interesting applications that link scientific discoveries with efficient software and hardware. The emphasis is onintegrating power Machine Learning methods into the real-time experimental data processing loop to accelerate scientific discovery.
For neural networks and regression, should I use a design matrix with information about a polynomial fit or not? Discuss pros and cons. The example here shows some of these issues.
"""
Code to test Ridge and NNs using Scikit-Learn only
"""
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn import linear_model
from sklearn.neural_network import MLPRegressor
from sklearn.metrics import accuracy_score
import seaborn as sns
def MSE(y_data,y_model):
n = np.size(y_model)
return np.sum((y_data-y_model)**2)/n
# A seed just to ensure that the random numbers are the same for every run.
# Useful for eventual debugging.
np.random.seed(315)
n = 100
x = np.random.rand(n)
y = np.exp(-x**2) + 1.5 * np.exp(-(x-2)**2)
Maxpolydegree = 5
X = np.zeros((n,Maxpolydegree-1))
for degree in range(1,Maxpolydegree): #No intercept column
X[:,degree-1] = x**(degree)
# We split the data in test and training data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
# Decide which values of lambda to use
nlambdas = 10
lmbd_vals = np.logspace(-4, 0, nlambdas)
MSERidgePredict = np.zeros(nlambdas)
for i in range(nlambdas):
lmb = lmbd_vals[i]
RegRidge = linear_model.Ridge(lmb)
RegRidge.fit(X_train,y_train)
ypredictRidge = RegRidge.predict(X_test)
MSERidgePredict[i] = MSE(y_test,ypredictRidge)
plt.figure()
plt.plot(np.log10(lmbd_vals), MSERidgePredict, 'g--', label = 'MSE SL Ridge Test')
plt.xlabel('log10(lambda)')
plt.ylabel('MSE')
plt.legend()
plt.show()
# Neural Network part
n_hidden_neurons = 50
epochs = 100
# store models for later use
eta_vals = np.logspace(-4, 0, 10)
# store the models for later use
DNN_scikit = np.zeros((len(eta_vals), len(lmbd_vals)), dtype=object)
test_accuracy = np.zeros((len(eta_vals), len(lmbd_vals)))
sns.set()
for i, eta in enumerate(eta_vals):
for j, lmbd in enumerate(lmbd_vals):
dnn = MLPRegressor(hidden_layer_sizes=(n_hidden_neurons), activation='logistic',
alpha=lmbd, learning_rate_init=eta, max_iter=epochs)
dnn.fit(X_train, y_train)
ypredictMLP = dnn.predict(X_test)
test_accuracy[i][j] = MSE(ypredictMLP, y_test)
fig, ax = plt.subplots(figsize = (10, 10))
sns.heatmap(test_accuracy, annot=True, ax=ax, cmap="viridis")
ax.set_title("Training Accuracy")
ax.set_ylabel("$\eta$")
ax.set_xlabel("$\lambda$")
plt.show()
# Now we redefine our design matrix to include only the x-values and try out our NN
X = np.zeros((n,1))
X[:,0] = x
# We split the data in test and training data again
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
# Repeat the NN calculation
DNN_scikit = np.zeros((len(eta_vals), len(lmbd_vals)), dtype=object)
test_accuracy = np.zeros((len(eta_vals), len(lmbd_vals)))
sns.set()
for i, eta in enumerate(eta_vals):
for j, lmbd in enumerate(lmbd_vals):
dnn = MLPRegressor(hidden_layer_sizes=(n_hidden_neurons), activation='logistic',
alpha=lmbd, learning_rate_init=eta, max_iter=epochs)
dnn.fit(X_train, y_train)
ypredictMLP = dnn.predict(X_test)
test_accuracy[i][j] = MSE(ypredictMLP, y_test)
fig, ax = plt.subplots(figsize = (10, 10))
sns.heatmap(test_accuracy, annot=True, ax=ax, cmap="viridis")
ax.set_title("Training Accuracy")
ax.set_ylabel("$\eta$")
ax.set_xlabel("$\lambda$")
plt.show()
When developing your own gradient descent code, it is useful to test it first on a standard ordinary least squares problem. Then the Hessian matrix is determined by the design matrix only, namely \( \boldsymbol{H}\propto \boldsymbol{X}^T\boldsymbol{X} \).
The optimal learning rate is determined by the inverse of the largest eigenvalue of \( \boldsymbol{H} \). This can be used as a guideline for the learning rate guess.
Keeping this fixed, can aid in studyng the dependence on say the mean square value for OLS as function of the number of batches and epochs in your stochastic gradient descent code. See for example the code examples for week 40 (right before the neural network material).
For the principal component analysis, see slides from week 43, in particular from slide 28 and forward
Variance is a measure of the variability of the data you have. Potentially the number of components is infinite, so you want to "squeeze" the most information in each component of the finite set you build.
If, to exaggerate, you were to select a single principal component, you would want it to account for the most variability possible: hence the search for maximum variance, so that the one component collects the most "uniqueness" from the data set.
Maximizing the component vector variances is the same as maximizing the 'uniqueness' of those vectors. The vectors are as distant from each other as possible (orthogonal to each other).
Take for example a situation where you have 2 lines that are orthogonal in a 3D space. You can capture the environment much more completely with those orthogonal lines than 2 lines that are parallel (or nearly parallel). When applied to very high dimensional states using very few vectors, this becomes a much more important relationship among the vectors to maintain. In a linear algebra sense you want independent rows to be produced by PCA, otherwise some of those rows will be redundant.
In general terms cluster analysis, or clustering, is the task of grouping a data-set into different distinct categories based on some measure of equality of the data. This measure is often referred to as a metric or similarity measure in the literature (note: sometimes we deal with a dissimilarity measure instead). Usually, these metrics are formulated as some kind of distance function between points in a high-dimensional space.
The simplest, and also the most common is the Euclidean distance.
The simplest of all clustering algorithms is the k-means algorithm , sometimes also referred to as Lloyds algorithm. It is the simplest and also the most common. From its simplicity it obtains both strengths and weaknesses. These will be discussed in more detail later. The \( k \)-means algorithm is a centroid based clustering algorithm.
Assume, we are given \( n \) data points and we wish to split the data into \( K < n \) different categories, or clusters. We label each cluster by an integer
$$ k\in\{1, \cdots, K \}. $$In the basic k-means algorithm each point is assigned to only one cluster \( k \), and these assignments are non-injective i.e. many-to-one. We can think of these mappings as an encoder \( k = C(i) \), which assigns the \( i \)-th data-point \( \bf x_i \) to the \( k \)-th cluster.
\( k \)-means algorithm in words:
We assume we have \( n \) data-points
$$ \begin{equation}\label{eq:kmeanspoints} \boldsymbol{x_i} = \{x_{i, 1}, \cdots, x_{i, p}\}\in\mathbb{R}^p. \end{equation} $$which we wish to group into \( K < n \) clusters. For our dissimilarity measure we use the squared Euclidean distance
$$ \begin{equation}\label{eq:squaredeuclidean} d(\boldsymbol{x_i}, \boldsymbol{x_i'}) = \sum_{j=1}^p(x_{ij} - x_{i'j})^2 = ||\boldsymbol{x_i} - \boldsymbol{x_{i'}}||^2 \end{equation} $$We define the so called within-cluster point scatter which gives us a measure of how close each data point assigned to the same cluster tends to be to the all the others.
$$ \begin{equation}\label{eq:withincluster} W(C) = \frac{1}{2}\sum_{k=1}^K\sum_{C(i)=k} \sum_{C(i')=k}d(\boldsymbol{x_i}, \boldsymbol{x_{i'}}) = \sum_{k=1}^KN_k\sum_{C(i)=k}||\boldsymbol{x_i} - \boldsymbol{\overline{x_k}}||^2 \end{equation} $$where \( \boldsymbol{\overline{x_k}} \) is the mean vector associated with the \( k \)-th cluster, and \( N_k = \sum_{i=1}^nI(C(i) = k) \), where the \( I() \) notation is similar to the Kronecker delta (Commonly used in statistics, it just means that when \( i = k \) we have the encoder \( C(i) \)). In other words, the within-cluster scatter measures the compactness of each cluster with respect to the data points assigned to each cluster. This is the quantity that the \( k \)-means algorithm aims to minimize. We refer to this quantity \( W(C) \) as the within cluster scatter because of its relation to the total scatter.
We have
$$ \begin{equation}\label{eq:totalscatter} T = W(C) + B(C) = \frac{1}{2}\sum_{i=1}^n \sum_{i'=1}^nd(\boldsymbol{x_i}, \boldsymbol{x_{i'}}) = \frac{1}{2}\sum_{k=1}^K\sum_{C(i)=k} \Big(\sum_{C(i') = k}d(\boldsymbol{x_i}, \boldsymbol{x_{i'}}) + \sum_{C(i')\neq k}d(\boldsymbol{x_i}, \boldsymbol{x_{i'}})\Big). \end{equation} $$This is a quantity that is conserved throughout the \( k \)-means algorithm. It can be thought of as the total amount of information in the data, and it is composed of the aforementioned within-cluster scatter and the between-cluster scatter \( B(C) \). In methods such as principle component analysis the total scatter is not conserved.
Given a cluster mean \( \boldsymbol{m_k} \) we define the total cluster variance
$$ \begin{equation}\label{eq:totalclustervariance} \min_{C, \{\boldsymbol{m_k}\}_1^K}\sum_{k=1}^KN_k\sum||\boldsymbol{x_i} - \boldsymbol{m_k}||^2 \end{equation} $$Now we have all the pieces necessary to formally revisit the \( k \)-means algorithm.
The \( k \)-means clustering algorithm goes as follows
Let us now program the most basic version of the algorithm using nothing but Python with numpy arrays. This code is kept intentionally simple to gradually progress our understanding. There is no vectorization of any kind, and even most helper functions are not utilized.
We need first a dataset to do our cluster analysis on. In our case this is a plain vanilla data set using random numbers using a Gaussian distribution.
import time
import numpy as np
import tensorflow as tf
from matplotlib import image
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from IPython.display import display
np.random.seed(2021)
Next we define functions, for ease of use later, to generate Gaussians and to set up our toy data set.
def gaussian_points(dim=2, n_points=1000, mean_vector=np.array([0, 0]),
sample_variance=1):
"""
Very simple custom function to generate gaussian distributed point clusters
with variable dimension, number of points, means in each direction
(must match dim) and sample variance.
Inputs:
dim (int)
n_points (int)
mean_vector (np.array) (where index 0 is x, index 1 is y etc.)
sample_variance (float)
Returns:
data (np.array): with dimensions (dim x n_points)
"""
mean_matrix = np.zeros(dim) + mean_vector
covariance_matrix = np.eye(dim) * sample_variance
data = np.random.multivariate_normal(mean_matrix, covariance_matrix,
n_points)
return data
def generate_simple_clustering_dataset(dim=2, n_points=1000, plotting=True,
return_data=True):
"""
Toy model to illustrate k-means clustering
"""
data1 = gaussian_points(mean_vector=np.array([5, 5]))
data2 = gaussian_points()
data3 = gaussian_points(mean_vector=np.array([1, 4.5]))
data4 = gaussian_points(mean_vector=np.array([5, 1]))
data = np.concatenate((data1, data2, data3, data4), axis=0)
if plotting:
fig, ax = plt.subplots()
ax.scatter(data[:, 0], data[:, 1], alpha=0.2)
ax.set_title('Toy Model Dataset')
plt.show()
if return_data:
return data
data = generate_simple_clustering_dataset()
With the above dataset we start implementing the \( k \)-means algorithm.
n_samples, dimensions = data.shape
n_clusters = 4
# we randomly initialize our centroids
np.random.seed(2021)
centroids = data[np.random.choice(n_samples, n_clusters, replace=False), :]
distances = np.zeros((n_samples, n_clusters))
# first we need to calculate the distance to each centroid from our data
for k in range(n_clusters):
for n in range(n_samples):
dist = 0
for d in range(dimensions):
dist += np.abs(data[n, d] - centroids[k, d])**2
distances[n, k] = dist
# we initialize an array to keep track of to which cluster each point belongs
# the way we set it up here the index tracks which point and the value which
# cluster the point belongs to
cluster_labels = np.zeros(n_samples, dtype='int')
# next we loop through our samples and for every point assign it to the cluster
# to which it has the smallest distance to
for n in range(n_samples):
# tracking variables (all of this is basically just an argmin)
smallest = 1e10
smallest_row_index = 1e10
for k in range(n_clusters):
if distances[n, k] < smallest:
smallest = distances[n, k]
smallest_row_index = k
cluster_labels[n] = smallest_row_index
fig = plt.figure()
ax = fig.add_subplot()
unique_cluster_labels = np.unique(cluster_labels)
for i in unique_cluster_labels:
ax.scatter(data[cluster_labels == i, 0],
data[cluster_labels == i, 1],
label = i,
alpha = 0.2)
ax.scatter(centroids[:, 0], centroids[:, 1], c='black')
ax.set_title("First Grouping of Points to Centroids")
plt.show()
So what do we have so far? We have 'picked' \( k \) centroids at random from our data points. There are other ways of more intelligently choosing their initializations, however for our purposes randomly is fine. Then we have initialized an array 'distances' which holds the information of the distance, or dissimilarity, of every point to of our centroids. Finally, we have initialized an array 'cluster_labels' which according to our distances array holds the information of to which centroid every point is assigned. This was the first pass of our algorithm. Essentially, all we need to do now is repeat the distance and assignment steps above until we have reached a desired convergence or a maximum amount of iterations.
max_iterations = 100
tolerance = 1e-8
for iteration in range(max_iterations):
prev_centroids = centroids.copy()
for k in range(n_clusters):
# this array will be used to update our centroid positions
vector_mean = np.zeros(dimensions)
mean_divisor = 0
for n in range(n_samples):
if cluster_labels[n] == k:
vector_mean += data[n, :]
mean_divisor += 1
# update according to the k means
centroids[k, :] = vector_mean / mean_divisor
# we find the dissimilarity
for k in range(n_clusters):
for n in range(n_samples):
dist = 0
for d in range(dimensions):
dist += np.abs(data[n, d] - centroids[k, d])**2
distances[n, k] = dist
# assign each point
for n in range(n_samples):
smallest = 1e10
smallest_row_index = 1e10
for k in range(n_clusters):
if distances[n, k] < smallest:
smallest = distances[n, k]
smallest_row_index = k
cluster_labels[n] = smallest_row_index
# convergence criteria
centroid_difference = np.sum(np.abs(centroids - prev_centroids))
if centroid_difference < tolerance:
print(f'Converged at iteration {iteration}')
break
elif iteration == max_iterations:
print(f'Did not converge in {max_iterations} iterations')
We now have a simple , un-optimized \( k \)-means clustering implementation. Lets plot the final result
fig = plt.figure()
ax = fig.add_subplot()
unique_cluster_labels = np.unique(cluster_labels)
for i in unique_cluster_labels:
ax.scatter(data[cluster_labels == i, 0],
data[cluster_labels == i, 1],
label = i,
alpha = 0.2)
ax.scatter(centroids[:, 0], centroids[:, 1], c='black')
ax.set_title("Final Result of K-means Clustering")
plt.show()
def naive_kmeans(data, n_clusters=4, max_iterations=100, tolerance=1e-8):
start_time = time.time()
n_samples, dimensions = data.shape
n_clusters = 4
#np.random.seed(2021)
centroids = data[np.random.choice(n_samples, n_clusters, replace=False), :]
distances = np.zeros((n_samples, n_clusters))
for k in range(n_clusters):
for n in range(n_samples):
dist = 0
for d in range(dimensions):
dist += np.abs(data[n, d] - centroids[k, d])**2
distances[n, k] = dist
cluster_labels = np.zeros(n_samples, dtype='int')
for n in range(n_samples):
smallest = 1e10
smallest_row_index = 1e10
for k in range(n_clusters):
if distances[n, k] < smallest:
smallest = distances[n, k]
smallest_row_index = k
cluster_labels[n] = smallest_row_index
for iteration in range(max_iterations):
prev_centroids = centroids.copy()
for k in range(n_clusters):
vector_mean = np.zeros(dimensions)
mean_divisor = 0
for n in range(n_samples):
if cluster_labels[n] == k:
vector_mean += data[n, :]
mean_divisor += 1
centroids[k, :] = vector_mean / mean_divisor
for k in range(n_clusters):
for n in range(n_samples):
dist = 0
for d in range(dimensions):
dist += np.abs(data[n, d] - centroids[k, d])**2
distances[n, k] = dist
for n in range(n_samples):
smallest = 1e10
smallest_row_index = 1e10
for k in range(n_clusters):
if distances[n, k] < smallest:
smallest = distances[n, k]
smallest_row_index = k
cluster_labels[n] = smallest_row_index
centroid_difference = np.sum(np.abs(centroids - prev_centroids))
if centroid_difference < tolerance:
print(f'Converged at iteration {iteration}')
print(f'Runtime: {time.time() - start_time} seconds')
return cluster_labels, centroids
print(f'Did not converge in {max_iterations} iterations')
print(f'Runtime: {time.time() - start_time} seconds')
return cluster_labels, centroids
We start here with the most basic algorithm, the so-called decision tree. With this basic algorithm we can in turn build more complex networks, spanning from homogeneous and heterogenous forests (bagging, random forests and more) to one of the most popular supervised algorithms nowadays, the extreme gradient boosting, or just XGBoost. But let us start with the simplest possible ingredient.
Decision trees are supervised learning algorithms used for both, classification and regression tasks.
The main idea of decision trees is to find those descriptive features which contain the most information regarding the target feature and then split the dataset along the values of these features such that the target feature values for the resulting underlying datasets are as pure as possible.
The descriptive features which reproduce best the target/output features are normally said to be the most informative ones. The process of finding the most informative feature is done until we accomplish a stopping criteria where we then finally end up in so called leaf nodes.
A decision tree is typically divided into a root node, the interior nodes, and the final leaf nodes or just leaves. These entities are then connected by so-called branches.
The leaf nodes contain the predictions we will make for new query instances presented to our trained model. This is possible since the model has learned the underlying structure of the training data and hence can, given some assumptions, make predictions about the target feature value (class) of unseen query instances.
This tree was produced using the Wisconsin cancer data (discussed here as well, see code examples below) using Scikit-Learn's decision tree classifier. Here we have used the so-called gini index (see below) to split the various branches.
The overarching approach to decision trees is a top-down approach.
This process is then repeated for the subtree rooted at the new node.
In simplified terms, the process of training a decision tree and predicting the target features of query instances is as follows:
Then we are essentially done!
import numpy as np
import matplotlib.pyplot as plt
from sklearn.preprocessing import PolynomialFeatures
from sklearn.linear_model import LinearRegression
steps=250
distance=0
x=0
distance_list=[]
steps_list=[]
while x<steps:
distance+=np.random.randint(-1,2)
distance_list.append(distance)
x+=1
steps_list.append(x)
plt.plot(steps_list,distance_list, color='green', label="Random Walk Data")
steps_list=np.asarray(steps_list)
distance_list=np.asarray(distance_list)
X=steps_list[:,np.newaxis]
#Polynomial fits
#Degree 2
poly_features=PolynomialFeatures(degree=2, include_bias=False)
X_poly=poly_features.fit_transform(X)
lin_reg=LinearRegression()
poly_fit=lin_reg.fit(X_poly,distance_list)
b=lin_reg.coef_
c=lin_reg.intercept_
print ("2nd degree coefficients:")
print ("zero power: ",c)
print ("first power: ", b[0])
print ("second power: ",b[1])
z = np.arange(0, steps, .01)
z_mod=b[1]*z**2+b[0]*z+c
fit_mod=b[1]*X**2+b[0]*X+c
plt.plot(z, z_mod, color='r', label="2nd Degree Fit")
plt.title("Polynomial Regression")
plt.xlabel("Steps")
plt.ylabel("Distance")
#Degree 10
poly_features10=PolynomialFeatures(degree=10, include_bias=False)
X_poly10=poly_features10.fit_transform(X)
poly_fit10=lin_reg.fit(X_poly10,distance_list)
y_plot=poly_fit10.predict(X_poly10)
plt.plot(X, y_plot, color='black', label="10th Degree Fit")
plt.legend()
plt.show()
#Decision Tree Regression
from sklearn.tree import DecisionTreeRegressor
regr_1=DecisionTreeRegressor(max_depth=2)
regr_2=DecisionTreeRegressor(max_depth=5)
regr_3=DecisionTreeRegressor(max_depth=7)
regr_1.fit(X, distance_list)
regr_2.fit(X, distance_list)
regr_3.fit(X, distance_list)
X_test = np.arange(0.0, steps, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)
y_3=regr_3.predict(X_test)
# Plot the results
plt.figure()
plt.scatter(X, distance_list, s=2.5, c="black", label="data")
plt.plot(X_test, y_1, color="red",
label="max_depth=2", linewidth=2)
plt.plot(X_test, y_2, color="green", label="max_depth=5", linewidth=2)
plt.plot(X_test, y_3, color="m", label="max_depth=7", linewidth=2)
plt.xlabel("Data")
plt.ylabel("Darget")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()
There are mainly two steps
How do we construct the regions \( R_1,\dots,R_J \)? In theory, the regions could have any shape. However, we choose to divide the predictor space into high-dimensional rectangles, or boxes, for simplicity and for ease of interpretation of the resulting predictive model. The goal is to find boxes \( R_1,\dots,R_J \) that minimize the MSE, given by
$$ \sum_{j=1}^J\sum_{i\in R_j}(y_i-\overline{y}_{R_j})^2, $$where \( \overline{y}_{R_j} \) is the mean response for the training observations within box \( j \).
Unfortunately, it is computationally infeasible to consider every possible partition of the feature space into \( J \) boxes. The common strategy is to take a top-down approach
The approach is top-down because it begins at the top of the tree (all observations belong to a single region) and then successively splits the predictor space; each split is indicated via two new branches further down on the tree. It is greedy because at each step of the tree-building process, the best split is made at that particular step, rather than looking ahead and picking a split that will lead to a better tree in some future step.
In order to implement the recursive binary splitting we start by selecting the predictor \( x_j \) and a cutpoint \( s \) that splits the predictor space into two regions \( R_1 \) and \( R_2 \)
$$ \left\{X\vert x_j < s\right\}, $$and
$$ \left\{X\vert x_j \geq s\right\}, $$so that we obtain the lowest MSE, that is
$$ \sum_{i:x_i\in R_j}(y_i-\overline{y}_{R_1})^2+\sum_{i:x_i\in R_2}(y_i-\overline{y}_{R_2})^2, $$which we want to minimize by considering all predictors \( x_1,x_2,\dots,x_p \). We consider also all possible values of \( s \) for each predictor. These values could be determined by randomly assigned numbers or by starting at the midpoint and then proceed till we find an optimal value.
For any \( j \) and \( s \), we define the pair of half-planes where \( \overline{y}_{R_1} \) is the mean response for the training observations in \( R_1(j,s) \), and \( \overline{y}_{R_2} \) is the mean response for the training observations in \( R_2(j,s) \).
Finding the values of \( j \) and \( s \) that minimize the above equation can be done quite quickly, especially when the number of features \( p \) is not too large.
Next, we repeat the process, looking for the best predictor and best cutpoint in order to split the data further so as to minimize the MSE within each of the resulting regions. However, this time, instead of splitting the entire predictor space, we split one of the two previously identified regions. We now have three regions. Again, we look to split one of these three regions further, so as to minimize the MSE. The process continues until a stopping criterion is reached; for instance, we may continue until no region contains more than five observations.
The above procedure is rather straightforward, but leads often to overfitting and unnecessarily large and complicated trees. The basic idea is to grow a large tree \( T_0 \) and then prune it back in order to obtain a subtree. A smaller tree with fewer splits (fewer regions) can lead to smaller variance and better interpretation at the cost of a little more bias.
The so-called Cost complexity pruning algorithm gives us a way to do just this. Rather than considering every possible subtree, we consider a sequence of trees indexed by a nonnegative tuning parameter \( \alpha \).
Read more at the following Scikit-Learn link on pruning.
For each value of \( \alpha \) there corresponds a subtree \( T \in T_0 \) such that
$$ \sum_{m=1}^{\overline{T}}\sum_{i:x_i\in R_m}(y_i-\overline{y}_{R_m})^2+\alpha\overline{T}, $$is as small as possible. Here \( \overline{T} \) is the number of terminal nodes of the tree \( T \) , \( R_m \) is the rectangle (i.e. the subset of predictor space) corresponding to the \( m \)-th terminal node.
The tuning parameter \( \alpha \) controls a trade-off between the subtree’s complexity and its fit to the training data. When \( \alpha = 0 \), then the subtree \( T \) will simply equal \( T_0 \), because then the above equation just measures the training error. However, as \( \alpha \) increases, there is a price to pay for having a tree with many terminal nodes. The above equation will tend to be minimized for a smaller subtree.
It turns out that as we increase \( \alpha \) from zero branches get pruned from the tree in a nested and predictable fashion, so obtaining the whole sequence of subtrees as a function of \( \alpha \) is easy. We can select a value of \( \alpha \) using a validation set or using cross-validation. We then return to the full data set and obtain the subtree corresponding to \( \alpha \).
A classification tree is very similar to a regression tree, except that it is used to predict a qualitative response rather than a quantitative one. Recall that for a regression tree, the predicted response for an observation is given by the mean response of the training observations that belong to the same terminal node. In contrast, for a classification tree, we predict that each observation belongs to the most commonly occurring class of training observations in the region to which it belongs. In interpreting the results of a classification tree, we are often interested not only in the class prediction corresponding to a particular terminal node region, but also in the class proportions among the training observations that fall into that region.
The task of growing a classification tree is quite similar to the task of growing a regression tree. Just as in the regression setting, we use recursive binary splitting to grow a classification tree. However, in the classification setting, the MSE cannot be used as a criterion for making the binary splits. A natural alternative to MSE is the classification error rate. Since we plan to assign an observation in a given region to the most commonly occurring error rate class of training observations in that region, the classification error rate is simply the fraction of the training observations in that region that do not belong to the most common class.
When building a classification tree, either the Gini index or the entropy are typically used to evaluate the quality of a particular split, since these two approaches are more sensitive to node purity than is the classification error rate.
If our targets are the outcome of a classification process that takes for example \( k=1,2,\dots,K \) values, the only thing we need to think of is to set up the splitting criteria for each node.
We define a PDF \( p_{mk} \) that represents the number of observations of a class \( k \) in a region \( R_m \) with \( N_m \) observations. We represent this likelihood function in terms of the proportion \( I(y_i=k) \) of observations of this class in the region \( R_m \) as
$$ p_{mk} = \frac{1}{N_m}\sum_{x_i\in R_m}I(y_i=k). $$We let \( p_{mk} \) represent the majority class of observations in region \( m \). The three most common ways of splitting a node are given by
import os
from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import confusion_matrix
from sklearn.tree import export_graphviz
from IPython.display import Image
from pydot import graph_from_dot_data
import pandas as pd
import numpy as np
cancer = load_breast_cancer()
X = pd.DataFrame(cancer.data, columns=cancer.feature_names)
print(X)
y = pd.Categorical.from_codes(cancer.target, cancer.target_names)
y = pd.get_dummies(y)
print(y)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=1)
tree_clf = DecisionTreeClassifier(max_depth=5)
tree_clf.fit(X_train, y_train)
export_graphviz(
tree_clf,
out_file="DataFiles/cancer.dot",
feature_names=cancer.feature_names,
class_names=cancer.target_names,
rounded=True,
filled=True
)
cmd = 'dot -Tpng DataFiles/cancer.dot -o DataFiles/cancer.png'
os.system(cmd)
# Common imports
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_moons
from sklearn.tree import export_graphviz
from pydot import graph_from_dot_data
import pandas as pd
import os
np.random.seed(42)
X, y = make_moons(n_samples=100, noise=0.25, random_state=53)
X_train, X_test, y_train, y_test = train_test_split(X,y,random_state=0)
tree_clf = DecisionTreeClassifier(max_depth=5)
tree_clf.fit(X_train, y_train)
export_graphviz(
tree_clf,
out_file="DataFiles/moons.dot",
rounded=True,
filled=True
)
cmd = 'dot -Tpng DataFiles/moons.dot -o DataFiles/moons.png'
os.system(cmd)
Scikit-Learn has also another way to visualize the trees which is very useful, here with the Iris data.
from sklearn.datasets import load_iris
from sklearn import tree
X, y = load_iris(return_X_y=True)
tree_clf = tree.DecisionTreeClassifier()
tree_clf = tree_clf.fit(X, y)
# and then plot the tree
tree.plot_tree(tree_clf)
Alternatively, the tree can also be exported in textual format with the function exporttext. This method doesn’t require the installation of external libraries and is more compact:
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import export_text
iris = load_iris()
decision_tree = DecisionTreeClassifier(random_state=0, max_depth=2)
decision_tree = decision_tree.fit(iris.data, iris.target)
r = export_text(decision_tree, feature_names=iris['feature_names'])
print(r)
Two algorithms stand out in the set up of decision trees:
We discuss both algorithms with applications here. The popular library Scikit-Learn uses the CART algorithm. For classification problems you can use either the gini index or the entropy to split a tree in two branches.
For classification, the CART algorithm splits the data set in two subsets using a single feature \( k \) and a threshold \( t_k \). This could be for example a threshold set by a number below a certain circumference of a malign tumor.
How do we find these two quantities? We search for the pair \( (k,t_k) \) that produces the purest subset using for example the gini factor \( G \). The cost function it tries to minimize is then
$$ C(k,t_k) = \frac{m_{\mathrm{left}}}{m}G_{\mathrm{left}}+ \frac{m_{\mathrm{right}}}{m}G_{\mathrm{right}}, $$where \( G_{\mathrm{left/right}} \) measures the impurity of the left/right subset and \( m_{\mathrm{left/right}} \) is the number of instances in the left/right subset
Once it has successfully split the training set in two, it splits the subsets using the same logic, then the subsubsets and so on, recursively. It stops recursing once it reaches the maximum depth (defined by the \( max\_depth \) hyperparameter), or if it cannot find a split that will reduce impurity. A few other hyperparameters control additional stopping conditions such as the \( min\_samples\_split \), \( min\_samples\_leaf \), \( min\_weight\_fraction\_leaf \), and \( max\_leaf\_nodes \).
The CART algorithm for regression works is similar to the one for classification except that instead of trying to split the training set in a way that minimizes say the gini or entropy impurity, it now tries to split the training set in a way that minimizes our well-known mean-squared error (MSE). The cost function is now
$$ C(k,t_k) = \frac{m_{\mathrm{left}}}{m}\mathrm{MSE}_{\mathrm{left}}+ \frac{m_{\mathrm{right}}}{m}\mathrm{MSE}_{\mathrm{right}}. $$Here the MSE for a specific node is defined as
$$ \mathrm{MSE}_{\mathrm{node}}=\frac{1}{m_\mathrm{node}}\sum_{i\in \mathrm{node}}(\overline{y}_{\mathrm{node}}-y_i)^2, $$with
$$ \overline{y}_{\mathrm{node}}=\frac{1}{m_\mathrm{node}}\sum_{i\in \mathrm{node}}y_i, $$the mean value of all observations in a specific node.
Without any regularization, the regression task for decision trees, just like for classification tasks, is prone to overfitting.
The example we will look at is a classical one in many Machine Learning applications. Based on various meteorological features, we have several so-called attributes which decide whether we at the end will do some outdoor activity like skiing, going for a bike ride etc etc. The table here contains the feautures outlook, temperature, humidity and wind. The target or output is whether we ride (True=1) or whether we do something else that day (False=0). The attributes for each feature are then sunny, overcast and rain for the outlook, hot, cold and mild for temperature, high and normal for humidity and weak and strong for wind.
The table here summarizes the various attributes and
| Day | Outlook | Temperature | Humidity | Wind | Ride |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | 0 |
| 2 | Sunny | Hot | High | Strong | 1 |
| 3 | Overcast | Hot | High | Weak | 1 |
| 4 | Rain | Mild | High | Weak | 1 |
| 5 | Rain | Cool | Normal | Weak | 1 |
| 6 | Rain | Cool | Normal | Strong | 0 |
| 7 | Overcast | Cool | Normal | Strong | 1 |
| 8 | Sunny | Mild | High | Weak | 0 |
| 9 | Sunny | Cool | Normal | Weak | 1 |
| 10 | Rain | Mild | Normal | Weak | 1 |
| 11 | Sunny | Mild | Normal | Strong | 1 |
| 12 | Overcast | Mild | High | Strong | 1 |
| 13 | Overcast | Hot | Normal | Weak | 1 |
| 14 | Rain | Mild | High | Strong | 0 |
# Common imports
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.tree import export_graphviz
from sklearn.preprocessing import StandardScaler, OneHotEncoder
from sklearn.compose import ColumnTransformer
from IPython.display import Image
from pydot import graph_from_dot_data
import os
# Where to save the figures and data files
PROJECT_ROOT_DIR = "Results"
FIGURE_ID = "Results/FigureFiles"
DATA_ID = "DataFiles/"
if not os.path.exists(PROJECT_ROOT_DIR):
os.mkdir(PROJECT_ROOT_DIR)
if not os.path.exists(FIGURE_ID):
os.makedirs(FIGURE_ID)
if not os.path.exists(DATA_ID):
os.makedirs(DATA_ID)
def image_path(fig_id):
return os.path.join(FIGURE_ID, fig_id)
def data_path(dat_id):
return os.path.join(DATA_ID, dat_id)
def save_fig(fig_id):
plt.savefig(image_path(fig_id) + ".png", format='png')
infile = open(data_path("rideclass.csv"),'r')
# Read the experimental data with Pandas
from IPython.display import display
ridedata = pd.read_csv(infile,names = ('Outlook','Temperature','Humidity','Wind','Ride'))
ridedata = pd.DataFrame(ridedata)
# Features and targets
X = ridedata.loc[:, ridedata.columns != 'Ride'].values
y = ridedata.loc[:, ridedata.columns == 'Ride'].values
# Create the encoder.
encoder = OneHotEncoder(handle_unknown="ignore")
# Assume for simplicity all features are categorical.
encoder.fit(X)
# Apply the encoder.
X = encoder.transform(X)
print(X)
# Then do a Classification tree
tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X, y)
print("Train set accuracy with Decision Tree: {:.2f}".format(tree_clf.score(X,y)))
#transfer to a decision tree graph
export_graphviz(
tree_clf,
out_file="DataFiles/ride.dot",
rounded=True,
filled=True
)
cmd = 'dot -Tpng DataFiles/cancer.dot -o DataFiles/cancer.png'
os.system(cmd)
The above functions (gini, entropy and misclassification error) are important components of the so-called CART algorithm. We will discuss this algorithm below after we have discussed the information gain algorithm ID3.
In the example here we have converted all our attributes into numerical values \( 0,1,2 \) etc.
# Split a dataset based on an attribute and an attribute value
def test_split(index, value, dataset):
left, right = list(), list()
for row in dataset:
if row[index] < value:
left.append(row)
else:
right.append(row)
return left, right
# Calculate the Gini index for a split dataset
def gini_index(groups, classes):
# count all samples at split point
n_instances = float(sum([len(group) for group in groups]))
# sum weighted Gini index for each group
gini = 0.0
for group in groups:
size = float(len(group))
# avoid divide by zero
if size == 0:
continue
score = 0.0
# score the group based on the score for each class
for class_val in classes:
p = [row[-1] for row in group].count(class_val) / size
score += p * p
# weight the group score by its relative size
gini += (1.0 - score) * (size / n_instances)
return gini
# Select the best split point for a dataset
def get_split(dataset):
class_values = list(set(row[-1] for row in dataset))
b_index, b_value, b_score, b_groups = 999, 999, 999, None
for index in range(len(dataset[0])-1):
for row in dataset:
groups = test_split(index, row[index], dataset)
gini = gini_index(groups, class_values)
print('X%d < %.3f Gini=%.3f' % ((index+1), row[index], gini))
if gini < b_score:
b_index, b_value, b_score, b_groups = index, row[index], gini, groups
return {'index':b_index, 'value':b_value, 'groups':b_groups}
dataset = [[0,0,0,0,0],
[0,0,0,1,1],
[1,0,0,0,1],
[2,1,0,0,1],
[2,2,1,0,1],
[2,2,1,1,0],
[1,2,1,1,1],
[0,1,0,0,0],
[0,2,1,0,1],
[2,1,1,0,1],
[0,1,1,1,1],
[1,1,0,1,1],
[1,0,1,0,1],
[2,1,0,1,0]]
split = get_split(dataset)
print('Split: [X%d < %.3f]' % ((split['index']+1), split['value']))
The ID3 algorithm learns decision trees by constructing them in a top down way, beginning with the question which attribute should be tested at the root of the tree?
The ID3 algorithm selects which attribute to test at each node in the tree.
We would like to select the attribute that is most useful for classifying examples.
What is a good quantitative measure of the worth of an attribute?
Information gain measures how well a given attribute separates the training examples according to their target classification.
The ID3 algorithm uses this information gain measure to select among the candidate attributes at each step while growing the tree.
import matplotlib.pyplot as plt
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_breast_cancer
from sklearn.svm import SVC
from sklearn.linear_model import LogisticRegression
from sklearn.tree import DecisionTreeClassifier
# Load the data
cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(cancer.data,cancer.target,random_state=0)
print(X_train.shape)
print(X_test.shape)
# Logistic Regression
logreg = LogisticRegression(solver='lbfgs')
logreg.fit(X_train, y_train)
print("Test set accuracy with Logistic Regression: {:.2f}".format(logreg.score(X_test,y_test)))
# Support vector machine
svm = SVC(gamma='auto', C=100)
svm.fit(X_train, y_train)
print("Test set accuracy with SVM: {:.2f}".format(svm.score(X_test,y_test)))
# Decision Trees
deep_tree_clf = DecisionTreeClassifier(max_depth=None)
deep_tree_clf.fit(X_train, y_train)
print("Test set accuracy with Decision Trees: {:.2f}".format(deep_tree_clf.score(X_test,y_test)))
#now scale the data
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)
X_train_scaled = scaler.transform(X_train)
X_test_scaled = scaler.transform(X_test)
# Logistic Regression
logreg.fit(X_train_scaled, y_train)
print("Test set accuracy Logistic Regression with scaled data: {:.2f}".format(logreg.score(X_test_scaled,y_test)))
# Support Vector Machine
svm.fit(X_train_scaled, y_train)
print("Test set accuracy SVM with scaled data: {:.2f}".format(logreg.score(X_test_scaled,y_test)))
# Decision Trees
deep_tree_clf.fit(X_train_scaled, y_train)
print("Test set accuracy with Decision Trees and scaled data: {:.2f}".format(deep_tree_clf.score(X_test_scaled,y_test)))
from __future__ import division, print_function, unicode_literals
# Common imports
import numpy as np
import os
# to make this notebook's output stable across runs
np.random.seed(42)
# To plot pretty figures
import matplotlib
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
plt.rcParams['axes.labelsize'] = 14
plt.rcParams['xtick.labelsize'] = 12
plt.rcParams['ytick.labelsize'] = 12
from sklearn.svm import SVC
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_moons
from sklearn.tree import export_graphviz
Xm, ym = make_moons(n_samples=100, noise=0.25, random_state=53)
deep_tree_clf1 = DecisionTreeClassifier(random_state=42)
deep_tree_clf2 = DecisionTreeClassifier(min_samples_leaf=4, random_state=42)
deep_tree_clf1.fit(Xm, ym)
deep_tree_clf2.fit(Xm, ym)
def plot_decision_boundary(clf, X, y, axes=[0, 7.5, 0, 3], iris=True, legend=False, plot_training=True):
x1s = np.linspace(axes[0], axes[1], 100)
x2s = np.linspace(axes[2], axes[3], 100)
x1, x2 = np.meshgrid(x1s, x2s)
X_new = np.c_[x1.ravel(), x2.ravel()]
y_pred = clf.predict(X_new).reshape(x1.shape)
custom_cmap = ListedColormap(['#fafab0','#9898ff','#a0faa0'])
plt.contourf(x1, x2, y_pred, alpha=0.3, cmap=custom_cmap)
if not iris:
custom_cmap2 = ListedColormap(['#7d7d58','#4c4c7f','#507d50'])
plt.contour(x1, x2, y_pred, cmap=custom_cmap2, alpha=0.8)
if plot_training:
plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo", label="Iris-Setosa")
plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs", label="Iris-Versicolor")
plt.plot(X[:, 0][y==2], X[:, 1][y==2], "g^", label="Iris-Virginica")
plt.axis(axes)
if iris:
plt.xlabel("Petal length", fontsize=14)
plt.ylabel("Petal width", fontsize=14)
else:
plt.xlabel(r"$x_1$", fontsize=18)
plt.ylabel(r"$x_2$", fontsize=18, rotation=0)
if legend:
plt.legend(loc="lower right", fontsize=14)
plt.figure(figsize=(11, 4))
plt.subplot(121)
plot_decision_boundary(deep_tree_clf1, Xm, ym, axes=[-1.5, 2.5, -1, 1.5], iris=False)
plt.title("No restrictions", fontsize=16)
plt.subplot(122)
plot_decision_boundary(deep_tree_clf2, Xm, ym, axes=[-1.5, 2.5, -1, 1.5], iris=False)
plt.title("min_samples_leaf = {}".format(deep_tree_clf2.min_samples_leaf), fontsize=14)
plt.show()
np.random.seed(6)
Xs = np.random.rand(100, 2) - 0.5
ys = (Xs[:, 0] > 0).astype(np.float32) * 2
angle = np.pi/4
rotation_matrix = np.array([[np.cos(angle), -np.sin(angle)], [np.sin(angle), np.cos(angle)]])
Xsr = Xs.dot(rotation_matrix)
tree_clf_s = DecisionTreeClassifier(random_state=42)
tree_clf_s.fit(Xs, ys)
tree_clf_sr = DecisionTreeClassifier(random_state=42)
tree_clf_sr.fit(Xsr, ys)
plt.figure(figsize=(11, 4))
plt.subplot(121)
plot_decision_boundary(tree_clf_s, Xs, ys, axes=[-0.7, 0.7, -0.7, 0.7], iris=False)
plt.subplot(122)
plot_decision_boundary(tree_clf_sr, Xsr, ys, axes=[-0.7, 0.7, -0.7, 0.7], iris=False)
plt.show()
# Quadratic training set + noise
np.random.seed(42)
m = 200
X = np.random.rand(m, 1)
y = 4 * (X - 0.5) ** 2
y = y + np.random.randn(m, 1) / 10
from sklearn.tree import DecisionTreeRegressor
tree_reg = DecisionTreeRegressor(max_depth=2, random_state=42)
tree_reg.fit(X, y)
from sklearn.tree import DecisionTreeRegressor
tree_reg1 = DecisionTreeRegressor(random_state=42, max_depth=2)
tree_reg2 = DecisionTreeRegressor(random_state=42, max_depth=3)
tree_reg1.fit(X, y)
tree_reg2.fit(X, y)
def plot_regression_predictions(tree_reg, X, y, axes=[0, 1, -0.2, 1], ylabel="$y$"):
x1 = np.linspace(axes[0], axes[1], 500).reshape(-1, 1)
y_pred = tree_reg.predict(x1)
plt.axis(axes)
plt.xlabel("$x_1$", fontsize=18)
if ylabel:
plt.ylabel(ylabel, fontsize=18, rotation=0)
plt.plot(X, y, "b.")
plt.plot(x1, y_pred, "r.-", linewidth=2, label=r"$\hat{y}$")
plt.figure(figsize=(11, 4))
plt.subplot(121)
plot_regression_predictions(tree_reg1, X, y)
for split, style in ((0.1973, "k-"), (0.0917, "k--"), (0.7718, "k--")):
plt.plot([split, split], [-0.2, 1], style, linewidth=2)
plt.text(0.21, 0.65, "Depth=0", fontsize=15)
plt.text(0.01, 0.2, "Depth=1", fontsize=13)
plt.text(0.65, 0.8, "Depth=1", fontsize=13)
plt.legend(loc="upper center", fontsize=18)
plt.title("max_depth=2", fontsize=14)
plt.subplot(122)
plot_regression_predictions(tree_reg2, X, y, ylabel=None)
for split, style in ((0.1973, "k-"), (0.0917, "k--"), (0.7718, "k--")):
plt.plot([split, split], [-0.2, 1], style, linewidth=2)
for split in (0.0458, 0.1298, 0.2873, 0.9040):
plt.plot([split, split], [-0.2, 1], "k:", linewidth=1)
plt.text(0.3, 0.5, "Depth=2", fontsize=13)
plt.title("max_depth=3", fontsize=14)
plt.show()
tree_reg1 = DecisionTreeRegressor(random_state=42)
tree_reg2 = DecisionTreeRegressor(random_state=42, min_samples_leaf=10)
tree_reg1.fit(X, y)
tree_reg2.fit(X, y)
x1 = np.linspace(0, 1, 500).reshape(-1, 1)
y_pred1 = tree_reg1.predict(x1)
y_pred2 = tree_reg2.predict(x1)
plt.figure(figsize=(11, 4))
plt.subplot(121)
plt.plot(X, y, "b.")
plt.plot(x1, y_pred1, "r.-", linewidth=2, label=r"$\hat{y}$")
plt.axis([0, 1, -0.2, 1.1])
plt.xlabel("$x_1$", fontsize=18)
plt.ylabel("$y$", fontsize=18, rotation=0)
plt.legend(loc="upper center", fontsize=18)
plt.title("No restrictions", fontsize=14)
plt.subplot(122)
plt.plot(X, y, "b.")
plt.plot(x1, y_pred2, "r.-", linewidth=2, label=r"$\hat{y}$")
plt.axis([0, 1, -0.2, 1.1])
plt.xlabel("$x_1$", fontsize=18)
plt.title("min_samples_leaf={}".format(tree_reg2.min_samples_leaf), fontsize=14)
plt.show()
However, by aggregating many decision trees, using methods like bagging, random forests, and boosting, the predictive performance of trees can be substantially improved.
As stated above and seen in many of the examples discussed here about a single decision tree, we often end up overfitting our training data. This normally means that we have a high variance. Can we reduce the variance of a statistical learning method?
This leads us to a set of different methods that can combine different machine learning algorithms or just use one of them to construct forests and jungles of trees, homogeneous ones or heterogenous ones. These methods are recognized by different names which we will try to explain here. These are
We discuss these methods here.
The plain decision trees suffer from high variance. This means that if we split the training data into two parts at random, and fit a decision tree to both halves, the results that we get could be quite different. In contrast, a procedure with low variance will yield similar results if applied repeatedly to distinct data sets; linear regression tends to have low variance, if the ratio of \( n \) to \( p \) is moderately large.
Bootstrap aggregation, or just bagging, is a general-purpose procedure for reducing the variance of a statistical learning method.
Bagging typically results in improved accuracy over prediction using a single tree. Unfortunately, however, it can be difficult to interpret the resulting model. Recall that one of the advantages of decision trees is the attractive and easily interpreted diagram that results.
However, when we bag a large number of trees, it is no longer possible to represent the resulting statistical learning procedure using a single tree, and it is no longer clear which variables are most important to the procedure. Thus, bagging improves prediction accuracy at the expense of interpretability. Although the collection of bagged trees is much more difficult to interpret than a single tree, one can obtain an overall summary of the importance of each predictor using the MSE (for bagging regression trees) or the Gini index (for bagging classification trees). In the case of bagging regression trees, we can record the total amount that the MSE is decreased due to splits over a given predictor, averaged over all \( B \) possible trees. A large value indicates an important predictor. Similarly, in the context of bagging classification trees, we can add up the total amount that the Gini index is decreased by splits over a given predictor, averaged over all \( B \) trees.
heads_proba = 0.51
coin_tosses = (np.random.rand(10000, 10) < heads_proba).astype(np.int32)
cumulative_heads_ratio = np.cumsum(coin_tosses, axis=0) / np.arange(1, 10001).reshape(-1, 1)
plt.figure(figsize=(8,3.5))
plt.plot(cumulative_heads_ratio)
plt.plot([0, 10000], [0.51, 0.51], "k--", linewidth=2, label="51%")
plt.plot([0, 10000], [0.5, 0.5], "k-", label="50%")
plt.xlabel("Number of coin tosses")
plt.ylabel("Heads ratio")
plt.legend(loc="lower right")
plt.axis([0, 10000, 0.42, 0.58])
save_fig("votingsimple")
plt.show()
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=500, noise=0.30, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)
from sklearn.ensemble import RandomForestClassifier
from sklearn.ensemble import VotingClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
log_clf = LogisticRegression(solver="liblinear", random_state=42)
rnd_clf = RandomForestClassifier(n_estimators=10, random_state=42)
svm_clf = SVC(gamma="auto", random_state=42)
voting_clf = VotingClassifier(
estimators=[('lr', log_clf), ('rf', rnd_clf), ('svc', svm_clf)],
voting='hard')
voting_clf.fit(X_train, y_train)
from sklearn.metrics import accuracy_score
for clf in (log_clf, rnd_clf, svm_clf, voting_clf):
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
print(clf.__class__.__name__, accuracy_score(y_test, y_pred))
log_clf = LogisticRegression(solver="liblinear", random_state=42)
rnd_clf = RandomForestClassifier(n_estimators=10, random_state=42)
svm_clf = SVC(gamma="auto", probability=True, random_state=42)
voting_clf = VotingClassifier(
estimators=[('lr', log_clf), ('rf', rnd_clf), ('svc', svm_clf)],
voting='soft')
voting_clf.fit(X_train, y_train)
from sklearn.metrics import accuracy_score
for clf in (log_clf, rnd_clf, svm_clf, voting_clf):
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
print(clf.__class__.__name__, accuracy_score(y_test, y_pred))
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=500, noise=0.30, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)
from sklearn.ensemble import RandomForestClassifier
from sklearn.ensemble import VotingClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
log_clf = LogisticRegression(random_state=42)
rnd_clf = RandomForestClassifier(random_state=42)
svm_clf = SVC(random_state=42)
voting_clf = VotingClassifier(
estimators=[('lr', log_clf), ('rf', rnd_clf), ('svc', svm_clf)],
voting='hard')
voting_clf.fit(X_train, y_train)
from sklearn.metrics import accuracy_score
for clf in (log_clf, rnd_clf, svm_clf, voting_clf):
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
print(clf.__class__.__name__, accuracy_score(y_test, y_pred))
log_clf = LogisticRegression(random_state=42)
rnd_clf = RandomForestClassifier(random_state=42)
svm_clf = SVC(probability=True, random_state=42)
voting_clf = VotingClassifier(
estimators=[('lr', log_clf), ('rf', rnd_clf), ('svc', svm_clf)],
voting='soft')
voting_clf.fit(X_train, y_train)
from sklearn.metrics import accuracy_score
for clf in (log_clf, rnd_clf, svm_clf, voting_clf):
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
print(clf.__class__.__name__, accuracy_score(y_test, y_pred))
from sklearn.ensemble import BaggingClassifier
from sklearn.tree import DecisionTreeClassifier
bag_clf = BaggingClassifier(
DecisionTreeClassifier(random_state=42), n_estimators=500,
max_samples=100, bootstrap=True, n_jobs=-1, random_state=42)
bag_clf.fit(X_train, y_train)
y_pred = bag_clf.predict(X_test)
from sklearn.metrics import accuracy_score
print(accuracy_score(y_test, y_pred))
tree_clf = DecisionTreeClassifier(random_state=42)
tree_clf.fit(X_train, y_train)
y_pred_tree = tree_clf.predict(X_test)
print(accuracy_score(y_test, y_pred_tree))
from matplotlib.colors import ListedColormap
def plot_decision_boundary(clf, X, y, axes=[-1.5, 2.5, -1, 1.5], alpha=0.5, contour=True):
x1s = np.linspace(axes[0], axes[1], 100)
x2s = np.linspace(axes[2], axes[3], 100)
x1, x2 = np.meshgrid(x1s, x2s)
X_new = np.c_[x1.ravel(), x2.ravel()]
y_pred = clf.predict(X_new).reshape(x1.shape)
custom_cmap = ListedColormap(['#fafab0','#9898ff','#a0faa0'])
plt.contourf(x1, x2, y_pred, alpha=0.3, cmap=custom_cmap)
if contour:
custom_cmap2 = ListedColormap(['#7d7d58','#4c4c7f','#507d50'])
plt.contour(x1, x2, y_pred, cmap=custom_cmap2, alpha=0.8)
plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo", alpha=alpha)
plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs", alpha=alpha)
plt.axis(axes)
plt.xlabel(r"$x_1$", fontsize=18)
plt.ylabel(r"$x_2$", fontsize=18, rotation=0)
plt.figure(figsize=(11,4))
plt.subplot(121)
plot_decision_boundary(tree_clf, X, y)
plt.title("Decision Tree", fontsize=14)
plt.subplot(122)
plot_decision_boundary(bag_clf, X, y)
plt.title("Decision Trees with Bagging", fontsize=14)
save_fig("baggingtree")
plt.show()
Let us bring up our good old boostrap example from the linear regression lectures. We change the linerar regression algorithm with a decision tree wth different depths and perform a bootstrap aggregate (in this case we perform as many bootstraps as data points \( n \)).
import matplotlib.pyplot as plt
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.utils import resample
from sklearn.tree import DecisionTreeRegressor
n = 100
n_boostraps = 100
maxdepth = 8
# Make data set.
x = np.linspace(-3, 3, n).reshape(-1, 1)
y = np.exp(-x**2) + 1.5 * np.exp(-(x-2)**2)+ np.random.normal(0, 0.1, x.shape)
error = np.zeros(maxdepth)
bias = np.zeros(maxdepth)
variance = np.zeros(maxdepth)
polydegree = np.zeros(maxdepth)
X_train, X_test, y_train, y_test = train_test_split(x, y, test_size=0.2)
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)
X_train_scaled = scaler.transform(X_train)
X_test_scaled = scaler.transform(X_test)
# we produce a simple tree first as benchmark
simpletree = DecisionTreeRegressor(max_depth=3)
simpletree.fit(X_train_scaled, y_train)
simpleprediction = simpletree.predict(X_test_scaled)
for degree in range(1,maxdepth):
model = DecisionTreeRegressor(max_depth=degree)
y_pred = np.empty((y_test.shape[0], n_boostraps))
for i in range(n_boostraps):
x_, y_ = resample(X_train_scaled, y_train)
model.fit(x_, y_)
y_pred[:, i] = model.predict(X_test_scaled)#.ravel()
polydegree[degree] = degree
error[degree] = np.mean( np.mean((y_test - y_pred)**2, axis=1, keepdims=True) )
bias[degree] = np.mean( (y_test - np.mean(y_pred, axis=1, keepdims=True))**2 )
variance[degree] = np.mean( np.var(y_pred, axis=1, keepdims=True) )
print('Polynomial degree:', degree)
print('Error:', error[degree])
print('Bias^2:', bias[degree])
print('Var:', variance[degree])
print('{} >= {} + {} = {}'.format(error[degree], bias[degree], variance[degree], bias[degree]+variance[degree]))
mse_simpletree= np.mean( np.mean((y_test - simpleprediction)**2)
print(mse_simpletree)
plt.xlim(1,maxdepth)
plt.plot(polydegree, error, label='MSE')
plt.plot(polydegree, bias, label='bias')
plt.plot(polydegree, variance, label='Variance')
plt.legend()
save_fig("baggingboot")
plt.show()


One of the problems I had while writing dotMarks was the fact that I could not get enough URLs for my testing. I did ask friends and family to send me over their exported list of bookmarks or the bookmarks from pocket… but I needed more data, so, I look somewhere else: My browsing history.
Of course I couldn’t just get those links “and carry on“. I had to look at them, poke them and write an extension that allows me to analyse them.
Because, the idea was… what kind of high level information can Google (or anyone else) know from just looking at my browing history? and the result was as scary as you might imagine.
Bear in mind that Google knows much more than just my history… but that’s for another post. Let’s focus!
This extension basically gathers all your browing history (100 days max), sends it to dotmarks where some data-crunching happens and… then you see the results.
For example, it checks at what time you visit a link and creates this pretty graph:
Which highlights something that everybody who knows me is aware of: I do not sleep much and… that I work very early in the morning, or very late at night.
I was very curious about finding out my most visited websites… nothing surprising here:
That I do not procastinate as much as I thought is quiet clear (twitter reloads itself a lot, that’s why it ranks so high), but mostly I work on my localhost… and check how my Bitcoins are doing at Megamine.
Then, I started extracting keywords from my searches… and things got more interesting:
Yes, I do search about superheroes a lot… things of having children addicted to Thor, Spiderman and such troop.
What is really interesting is how high rank generics like java, python or ubuntu. I was a bit puzzled at first, then I realised that those keywords are ways of filtering out unwanted results. No surprise then, I do work with ubuntu, java and python.
Still, top marks for the two technologies I’ve been working more with: ElasticSearch and Docker. ElasticSearch documentation is quite dry… Docker, because I’m trying to do a bit too much I guess.
dotMarks is a self hosted bookmarks service. The idea is that you will run your own dotMarks server. I’m working hard to make it as easy as possible to run it (thanks to Docker) but if you’re curious and want to see what your browsing history says about you, download the extension and give it a go.
What I need is advice If you run the extension and think of something else I can extract I’m all ears.
Currently I’m working on a simple amazon parser, but it’s still very early… anyway, if you want to give it a go, by all means try it out and if you can share your feedback with me, I would really appreciate it.
Disclaimer: dotMarks and all related to this project is OpenSource. I do have a working version here, but as I said, the idea is that you will run your own service. Still, if you want to add your bookmarks, go ahead, and if you want to be able to find them later, use a tag that you can recognise later.


--- layout: archive title: Zulip Chat Archive permalink: /stream/113488-general/topic/newb.2C.<IP_ADDRESS>check.<IP_ADDRESS>minute.20runtime.3F.html ---
First, sorry if this is not the correct place for me to seek help for this. I haven't used zulip before and couldn't find a page with the rules to follow for this specific chat. (Should I have put this in an existing topic?)
I tried installing Lean 3.4.1 on windows 7, and when I try to run a test2.lean which consists of just "#check 5", it takes a minute and 5 seconds before it gives me the output.
5 : ℕ
<unknown>:1:1: error: unknown declaration 'main'
(when running "lean --run ../../progs/test2.lean" )
Someone else let me know that they tried a similar file
(specifically,
constant m : nat
#check m
which I tried before "#check 5" and also takes a minute for me)
on linux, and for them it ran in under a second.
They didn't have an idea for why it was running slowly except possibly my antivirus, but it still runs just as slow for me when I have that turned off.
I tend to have my computer's memory use fairly high. Would this cause Lean to run this slowly for this test case?
During the minute that it is running, my cpu use goes to around 100% (from around 20%). I tried closing my antivirus software and it didn't seem to improve the running speed.
Could anyone provide me with advice for what to do differently?
Thank you for your consideration
First, sorry if this is not the correct place for me to seek help for this. I haven't used zulip before and couldn't find a page with the rules to follow for this specific chat. (Should I have put this in an existing topic?)
I don't think we have any specific rule. Mario only pretends to complain when he sees Lolcats or memes. We only try to minimize code when asking for help, and avoid asking Sebastian about Lean 4 progress every day. That being said, I have no Windows computer so I cannot help. I can only tell you this shouldn't happen
Alright, thank you
I don't think you want "--run"
But I don't know whether that will make it not slow.
Ah! Thanks, I tried it without the "--run" , and it no longer complains about lacking main, though it still takes slightly over a minute.
Ah, I just tried running it with --profile , and, in addition to much more text than I expected, it ended with
5 : ℕ
cumulative profiling times:
compilation 6.75s
decl post-processing 2.45s
elaboration 85.4s
elaboration: tactic compilation 11.5s
elaboration: tactic execution 13.2s
parsing 12.9s
type checking 1.44s
Which I suppose says something, thought I'm not quite sure what.
Have you compiled the library files? If your core lean contains no .olean files then that could explain the long startup, since lean has to compile everything every time. Try running lean --make
first
You don't want to use --run
unless you are using lean noninteractively
it's basically the same as affixing #eval main
to the end of the given file
Ah, I had not! I will run that now, Thank you!
Ah, when I ran lean --make
by itself it finished in under a second and didn't say anything, and then I tried lean ../../progs/test2.lean
again and it still took a bit. I will time it to see if it is still taking a minute.
Still took a minute and 5 seconds.
I noticed that when I ran lean --path
it told me that "leanpkg_path_file" was "/could-not-find-home". Could that be related?
oh, I tried lean --make ..\..\progs\test2.lean
and it is saying stuff
Ah! Great! It runs in 7 seconds now. There we go. Thank you!
Interesting. I guess the precompiled binaries don't contain precompiled .olean files? Are they platform-dependent?
I almost always use linux nightlies and they have plenty of .olean files usually
{% endraw %}Last updated: Apr 24 2020 at 19:02 UTC


by Katie
Posted on 29 January, 2019
Want to learn how to do some forecasting with R? Here’s your chance to try out a new time-series forecasting package for R whose aim is to standardize and simplify the process of making and evaluating forecasts!
The Reich Lab uses an R package called ForecastFramework
to implement forecasting models. There are many benefits to using ForecastFramework
in a forecasting pipeline, including: standardized and simplified rapid model development and performance evaluation. ForecastFramework
was created by Joshua Kaminsky of the Infectious Disease Dynamics Group at Johns Hopkins University. The package is open source and can be found on Github.
After watching students in the lab working on learning how to use ForecastFramework
, I decided to create a step-by-step demonstration of the primary use cases of ForecastFramework
. The complete demo lives at reichlab.io/forecast-framework-demos/.
As the resident CS grad-student programmer in the lab, I wanted to write these demonstrations to make ForecastFramework
accessible. However, the demo only scrapes the surface of the many way that we (and others, we hope) will use ForecastFramework
. We have incorporated ForecastFramework
into our workflow for generating real-time dengue forecasts for the Ministry of Public Health in Thailand, and students have found it useful in generating small model comparison projects.
The online demo is separated into five sections. Each section will build off knowledge from the previous and will gradually increase in difficulty. However, the demos work as standalone scripts as well. The demos are categorized as the following:
ForecastFramework
models ahead.IncidenceMatrix
is, show how to format your data to be used as an IncidenceMatrix
, and exemplify functions of the IncidenceMatrix
class.ForecastFramework
, using the sarimaTD
package developed by Evan Ray.ForecastFramework
.ForecastFramework
.Try using ForecastFramework
today! I hope you find the tutorials interesting and instructive. If you have any questions or find any bugs, please let me know! I can be found at khouse [at] umass.edu or through my personal website.


Hi,
I am beginner and i haven't seen class like this...can any body explain me role of this class?
Whole code is from this site: http://www.cplusplus.com/articles/S8hv0pDG/
1 2 3 4 5 6 7 8 9 10 11 12
class StudentEntry
{
public:
StudentEntry(NAME name, MARK mark): name(name), mark(mark){}
voidoperator = (StudentEntry *entry)
{
name = entry->name;
mark = entry->mark;
}
NAME name;
MARK mark;
}*entryList[MAX_STUDENT];
And void operator = (StudentEntry *entry) is WRONG!!!
While it's legal C++ syntax, it's wrong semantically; operator= must always be defined using a (const) reference and return a ref to the instance.
1 2 3 4 5 6 7
StrudentEntry& operator=(const StudentEntry& entry)
{
name = entry.name;
mark = entry.mark;
return *this;
}
Note: Assuming name is a string and mark is an integer/double, and because this is a basic example, I have not protected against self assignment (as it's safe as it is).
Despite the errors in code I see many formatting problems that makes the text hard to read. I am not sure but I think the last revisions were not reviewed by moderators. I revised it again by the way.
@krnacandrej: The tutorial is about steps for building a program. The code in this tutorial at the implementation phase is not a well written C++ code and by many is considered even wrong.


Associated Files:
Referenced In:
Conflict of Interest:
I hereby declare that there is no conflict of interest.
Contact us for your data needs.
- Data analysis
- Data Automation
Reference:
- WAEC 2016-2018 Result Statistics: A workbook containing three years WAEC result data for all 36 states in Nigeria, Abuja, and Offshore exam locations
(by National Bureau os statistics and ProShare) Download


We use cookies on our website to improve your user experience. And, by continuing to use our site you are consenting to the use of cookies.
Our usage of cookies
Cookies are small files stored on your computer by web browsers such as Internet Explorer, Firefox etc. and are used to store information specific to the particular website. These files are not active in any way, are just text based, cannot carry viruses and as such do not pose a risk to your computer. We use cookies to help navigation and ensure only one session is open at a time in relation to our systems. No passwords or other personal information are stored in these.
If you disable cookies then you may not be able to access our website and you will not be able to access your account. For further information on how cookies work and can be managed, a guide can be found at www.allaboutcookies.org.


As of March 18, 2020, this course has been moved to Moodle due to COVID-19. This page remains as a syllabus, but the schedule, assignments, and many policies no longer apply.
This syllabus is subject to change based on specific class needs, especially the schedule. Significant deviations will be discussed in class.
The study of algorithms is one of the most crucial areas of in Computer Science. In this course, students will learn the basic tools of algorithm design and analysis through the study of some of the most well known and important algorithms. By the end of the semester, students will have developed not only a firm grounding in the analysis and design of algorithms, but working knowledge of the algorithms that have made computing what it is today.
There are too many algorithms topics to cover fully in a one semester course. To compensate, students will complete an in-depth research project on an algorithms-related topic of their choice, providing not only further depth but also project management skills. While this class focuses mostly on the theoretical design and analysis of algorithms, students will have opportunities to implement algorithms in the language of their choice.
This course will emphasize the first nine chapters of the main text (TADM) plus occasional material from other sources:
Time permitting, we’ll explore more advanced topics, such as probabilistic or approximation algorithms.
The required course textbook is:
We will occasionally pull material from other sources, especially for parallel algorithms. Any required readings will be posted on this webpage as needed.
I encourage you to take advantage of the wealth of algorithms study resources that can be found online. This material can be difficult; exposure to multiple sources is always useful and sometimes necessary to fully grasp it. I will list here some resources that may be useful (and fun!). Please suggest links to add as you find them.
The weekly workload for this course will vary by student and over the semester, but on average should be about 13 hours per week. The follow table provides a rough estimate of the distribution of this time over different course components for a 16 week semester.
| Category | Amount | Final Grade Weight | Average Time/Week (Hours) |
|---|---|---|---|
| Lectures | 52 | 10% (Participation) | 3.33 |
| Problem Sets | 6–8 | 25% | 4.5 |
| Quizzes | 5–7 | 25% | - |
| Research Project | 1 | 20% | 1.5 |
| Exam/Quiz Study | - | - | 1.67 |
| Exams | 2 | 20% | - |
| Reading | - | - | 2 |
| 13 |
Generally problem sets and quizzes will alternate weeks. There will be a research project on any algorithms-related topic, culminating in a paper and presentation to the class. There are two exams – a midterm and a final – both worth 10% each. The final exam will focus primarily, but not exclusively, on material covered since the midterm. In other words, it will contain a few questions on material from the first half of the semester.
Your participation grade is based on a variety of activities. During class I will often make use of the Socrative app, so you’ll need to install this on your phones. Participating in Socrative questions and with in-class group activities is required for a decent participation grade; an A includes asking questions either in class or in office hours.
Your final grade is based on a weighted average of particular assignment categories, with weights shown above. You can estimate your current grade based on your scores and these weights. You may always visit the instructor outside of class to discuss your current standing. Assignments and final grades use a standard grading scale shown below and will not be curved except in rare cases when deemed necessary by the instructor.
This courses uses a standard grading scale. Assignments and final grades will not be curved except in rare cases when its deemed necessary by the instructor. Percentage grades translate to letter grades as follows:
| Score | Grade |
|---|---|
| 94–100 | A |
| 90–93 | A- |
| 88–89 | B+ |
| 82–87 | B |
| 80–81 | B- |
| 78–79 | C+ |
| 72–77 | C |
| 70–71 | C- |
| 68–69 | D+ |
| 62–67 | D |
| 60–61 | D- |
| 0–59 | F |
You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge*.
You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge.
Late assignments: You have each been allotted a total of 5 late days. You may apply these to any problem sets you see fit and turn in your solutions with no penalty. However, you may use at most 2 on any individual assignment. The whole point here is to give you some flexibility that allows for things like illnesses, long trips, and the like. I am unlikely to grant further extensions.
Academic dishonesty: Monmouth College’s official policy on academic dishonesty can be found here. You are responsible for reading and complying with that policy.
In this course, any violation of the academic honesty policy will have varying consequences depending on the severity of the infraction as judged by the instructor. Minimally, a violation will result in an “F” or 0 points on the assignment in question. Additionally, the student’s course grade may be lowered by one letter grade. In severe cases, the student will be assigned a course grade of “F” and dismissed from the class. All cases of academic dishonesty must be reported to the Associate Dean who may decide to recommend further action to the Admissions and Academic Status Committee, including suspension or dismissal. It is assumed that students will educate themselves regarding what is considered to be academic dishonesty, so excuses or claims of ignorance will not mitigate the consequences of any violations
Collaboration: We encourage you to make use of the resources available to you – it is fine to seek help from a friend, tutor, instructor, internet, etc. However, copying of answers and any act worth of the label “cheating” is never permissible! In addition to listing your sources and collaborators, you should be producing your own writeup in your own words. By “your own words,” we mean you should be producing the text yourself, without some external aid. Verbatim copying of text is specifically disallowed, but so is taking a source and rearranging some phrases and changing some variable names to create a derivative version! Such behavior is definitely NOT “using your own words.” It does not matter if you helped contribute to this source text with others, since then you are still not the sole author of the text. The point of collaborating on an assignment is not to produce a jointly authored set of solutions, since that violates the course policies. Instead, it is to help you solve the problems, which sometimes involve a bit of creativity. After you have jointly come up with the ideas you need to solve the problems, though, you should part ways with your group and sit down to do the writing by yourself. I also advise against sharing the writeup you submit with others, since if someone else uses your text as a source for their own solution (with or without your permission), you will also be implicated in the violation of the academic integrity policy. In any case, if two nearly identical solutions are received, we have no way of tell which is the original, and the policy is to not award credit for either submission.
Electronic devices: Do not use your phone or other devices in class except where necessary. Any computer or tablet usage should be related to the course. If a device is not being used for Zoom or Socrative it should be put away and turned on silent. Other usage is rude and distracting to others.
General expectations: In short, I expect you to be respectful of others and take responsibility for your own learning. You are here to learn, so work hard and be professional.
Just attending class is not sufficient to truly learn the material. Read the text, use the resources available at Monmouth College, and go beyond the material.
If you miss class, you are responsible for everything covered on that day. College is, in some sense, your job. Take pride in creating quality work. Staple your assignments, label problems, and present your answers neatly and orderly.
Your job is to convince me that you have learned the material – show your work! Even if you do not know a particular answer, guide me through your thought process.
The following tentative calendar should give you a feel for how work is distributed throughout the semester. Assignments and events are listed in the week they are due or when they occur. This calendar is subject to change based on the circumstances of the course.
Unless otherwise specified, the readings come from TADM.
| Date | Topic | Assignment |
| Fri 01/17 | Intro to Algorithm Design | 1.1-1.3 |
| Mon 01/20 | Interval Scheduling, Reasoning about Correctness | 1.4-1.6 |
| Tue 01/21 | Correctness Proof Exercises | |
| Wed 01/22 | Big-O/Complexity Review | 2.1-2.4 |
| Fri 01/24 | Analyzing Selection Sort | PS 1 out (Solutions), 2.5-2.8 |
| Mon 01/27 | More Efficiency Analysis | |
| Tue 01/28 | Basic Data Structures | 3.1-3.2, Quiz 1 (Solutions) |
| Wed 01/29 | Dictionaries and Trees | 3.3 |
| Fri 01/31 | (Candidate Teaching Demo) | |
| Mon 02/03 | Balanced Binary Search Trees; PS 1 Questions | 3.4 |
| Tue 02/04 | Priority Queues and Heapsort | 3.5, 4.1-4.3 |
| Wed 02/05 | PS 1 Questions | |
| Fri 02/07 | Heaps; Hashing | PS 2 out (Solutions), 3.7 |
| Mon 02/10 | Searching | 4.9 |
| Tue 02/11 | Divide & Conquer: Mergesort | 4.5, 4.10 |
| Wed 02/12 | Analyzing Recurrences | 4.10 |
| Fri 02/14 | PS 2 Questions | Quiz 2 (Solutions) |
| Mon 02/17 | Quicksort Intuition | 4.6 |
| Tue 02/18 | Quicksort Analysis | |
| Wed 02/19 | Problem Set Questions | |
| Fri 02/21 | Problem Set Review; Quickselect | PS 3 out, (Solutions) |
| Mon 02/24 | Parallel Algorithms | |
| Tue 02/25 | Parallel Algorithm Analysis | |
| Wed 02/26 | (EE Candidate Teaching Demo) | |
| Fri 02/28 | Prefix Sums I | Project out |
| Mon 03/02 | Problem set 3 exercises | PS 3 due, |
| Tue 03/03 | Midterm Review; Prefix Sums II | |
| Wed 03/04 | Midterm (Solutions) | PS 4 out |
| (Fri 03/06) | (No class – Exam day for half-semester classes) | |
| (Mon 03/09) | (No class – Spring Break) | |
| (Tue 03/10) | (No class – Spring Break) | |
| (Wed 03/11) | (No class – Spring Break) | |
| (Fri 03/13) | (No class – Spring Break) | |
| Mon 03/16 | (No class – COVID-19) | |
| Tue 03/17 | (No class – COVID-19) | 5.1-5.4 |
| Wed 03/18 | (No class – COVID-19) | 5.5-5.7 |
| Fri 03/20 | (No class – COVID-19) | Quiz 3 |
| Mon 03/23 | Intro to Online Learning | 5.8-5.10 |
| Tue 03/24 | 6.3-6.4 | |
| Wed 03/25 | 6.1-6.2 | |
| Fri 03/27 | PS 5 out, 6.3-6.4 | |
| Mon 03/30 | Graphs and Graph Algorithms | |
| Tue 03/31 | ||
| Wed 04/01 | ||
| Fri 04/03 | Quiz 4 | |
| Mon 04/06 | ||
| Tue 04/07 | Heuristics | |
| Wed 04/08 | PS 6 out, | |
| (Fri 04/10) | (No class – Easter Break) | |
| (Mon 04/13) | (No class – Easter Break) | |
| (Tue 04/14) | (No class – Scholars Day) | |
| Wed 04/15 | Anno. Bib. due, | |
| Fri 04/17 | Quiz 5, | |
| Mon 04/20 | Dynamic Programming I | |
| Tue 04/21 | ||
| Wed 04/22 | ||
| Fri 04/24 | PS 7 out | |
| Mon 04/27 | Dynamic Programming II | |
| Tue 04/28 | ||
| Wed 04/29 | Paper Due, Peer Review out | |
| Fri 05/01 | Quiz 6 | |
| Mon 05/04 | Intractable Problems | Peer Review Due |
| Tue 05/05 | ||
| Wed 05/06 | Presentations Due | |
| Fri 05/08 3:00 PM | Final Exam |
Student Success and Accessibility Services offers FREE resources to assist Monmouth College students with their academic success. Programs include supplemental instruction for difficult classes, drop-in and appointment tutoring, and individual academic coaching. The office is here to help students excel academically, since everyone can work toward better grades, practice stronger study skills, and mange their time better.
Accessibility Services: If you have a disability or had academic accommodations in high school or another college, you may be eligible for academic accommodations at Monmouth College under the Americans with Disabilities Act (ADA). Monmouth College is committed to equal educational access. To discuss any of the services offered, please call or meet with Robert Crawley, Interim Director of Student Success and Accessibility Services. SSAS is located in the new ACE space on the first floor of Hewes Library, opposite Einstein Bros. Bagels. They can be reached at<PHONE_NUMBER> or via email at ssas@monmouthcollege.edu.


A goal must be measurable. The idea behind this is that if a goal is not measurable, it is not possible to know if you are making process towards your goal. Measuring your progress helps you keep track, reach the target dateand add excitement to your goal. Write here how your goal is measurable:


Leaderboard can be buggy, report bugs at the latest thread on /r/incremental_games
Trollers or 'hackers' will be removed from the leaderboard!
| Name | Meat | Cells |
|---|
Did you found a bug?
Did you want to request a new feature to the game?
Do you want to contribute?
Well, you can always contact me personally using this email<EMAIL_ADDRESS>You can also use the GitHub repo of Universe-God here and create issues.
If you want to contribute and you are not familiar with GitHub, just create an account on GitHub, download their Windows software then click on the "Clone in desktop" button (on the right).
Any coding help is welcome! :)


Coverage Summary for Class: TurnController (it.polimi.ingsw.controller)
| Class | Class, % | Method, % | Line, % |
|---|---|---|---|
| TurnController | 0% (0/ 1) | 0% (0/ 5) | 0% (0/ 12) |
1 package it.polimi.ingsw.controller;
2
3 import it.polimi.ingsw.model.Game;
4 import it.polimi.ingsw.model.player.Worker;
5
6 import java.util.ArrayList;
7 import java.util.List;
8
9 public class TurnController {
10
11 private Game game;
12 private List<String> nicknameQueue;
13 private String activePlayer;
14 private Worker activeWorker;
15
16 public TurnController() {
17 this.game = Game.getInstance();
18 nicknameQueue = new ArrayList<>(game.getPlayersNicknames());
19
20 activePlayer = nicknameQueue.get(0); // TODO set first active player
21 }
22
23 /**
24 * @return nickname of the active player
25 */
26 public String getActivePlayer() {
27 return activePlayer;
28 }
29
30 /**
31 * Set next active player.
32 */
33 public void next() {
34 int currentActive = nicknameQueue.indexOf(activePlayer);
35 if (currentActive + 1 < game.getNumCurrentPlayers()) {
36 currentActive = currentActive + 1;
37 } else {
38 currentActive = 0;
39 }
40 activePlayer = nicknameQueue.get(currentActive);
41 }
42
43 public void setActiveWorker(Worker worker) {
44 this.activeWorker = worker;
45 }
46
47 public Worker getActiveWorker() {
48 return activeWorker;
49 }
50 }


SVG icon
agi
auxiliary
boghammer
carrier
coastal radar site
datum
destroyer
fast attack craft
fishing vessel
fixed wing aircraft
frigate
frigate ta
helicopter
mcmv
merchant vessel
mine
missile
mpa
pirate
submarine 1
submarine 2
task group
torpedo
unknown
unmanned airborne vehicle


--- layout: post title: "A Tree functor" description: "A generalised tree object as a functor. Another functor example for object-oriented programmers." date: 2018-08-06 6:00 UTC tags: [Software Design] --- {% include JB/setup %}
{{ page.description }}
This article is an instalment in an article series about functors. In a previous article, you saw how to implement the Maybe functor in C#. In this article, you'll get another functor example: a generalised tree (also known as a rose tree).
As opposed to a binary tree, any node in a generalised tree can have an arbitrary number of children, including none.
The following Tree<T>
class can contain objects of the generic type T
. Being generic, it's a candidate for a functor, and it does, in fact, turn out to be one:
public sealed class Tree<T> : IReadOnlyCollection<Tree<T>> { private readonly IReadOnlyCollection<Tree<T>> children; public T Item { get; } public Tree(T item, IReadOnlyCollection<Tree<T>> children) { if (item == null) throw new ArgumentNullException(nameof(item)); if (children == null) throw new ArgumentNullException(nameof(children)); Item = item; this.children = children; } public Tree<TResult> Select<TResult>(Func<T, TResult> selector) { var mappedItem = selector(Item); var mappedChildren = new List<Tree<TResult>>(); foreach (var t in children) mappedChildren.Add(t.Select(selector)); return new Tree<TResult>(mappedItem, mappedChildren); } public int Count { get { return children.Count; } } public IEnumerator<Tree<T>> GetEnumerator() { return children.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return children.GetEnumerator(); } public override bool Equals(object obj) { if (!(obj is Tree<T> other)) return false; return Equals(Item, other.Item) && Enumerable.SequenceEqual(this, other); } public override int GetHashCode() { return Item.GetHashCode() ^ children.GetHashCode(); } }
As is usually the case, you can implement a tree in more than one way. Here, I chose an approach where Tree<T>
contains an Item
and is a collection of (sub)trees. Notice that the definition is recursive: in addition to its Item
, each Tree<T>
object also contains a finite collection of other trees. You create leaf nodes with empty collections.
This variation uses finite collections (IReadOnlyCollection<T>
), but you could also enable infinite trees by instead using potentially infinite sequences (IEnumerable<T>
). This would slightly complicate the implementation of the Select
method, though, so I decided to leave that as an exercise to the reader.
The Select
method first translates the contained Item
using the selector
function, and then recursively calls itself for each sub-tree in children
. This method has the desired signature, and furthermore obeys the functor laws, as you'll see later in the article. Tree<T>
is a functor.
While you can create trees directly with the Tree<T>
constructor, a few static helper methods makes it smoother:
public static class Tree { public static Tree<T> Leaf<T>(T item) { return new Tree<T>(item, new Tree<T>[0]); } public static Tree<T> Create<T>(T item, params Tree<T>[] children) { return new Tree<T>(item, children); } }
This enables you to create a tree like this:
var source = Tree.Create(42, Tree.Create(1337, Tree.Leaf(-3)), Tree.Create(7, Tree.Leaf(-99), Tree.Leaf(100), Tree.Leaf(0)));
This is a tree containing integers. You can translate it to a tree containing strings like this:
Tree<string> dest = source.Select(i => i.ToString());
or like this:
Tree<string> dest = from i in source select i.ToString();
In both of these examples, I've explicitly declared the type of dest
instead of using the var
keyword. There's no practical reason to do this; I only did it to make the type clear to you.
Haskell has a more explicit model of functors, and the language features to support it. The Haskell equivalent to the above Tree<T>
class is literally one line of code:
data Tree a = Tree a [Tree a] deriving (Show, Eq, Functor)
Notice that the Haskell compiler can automatically derive an implementation of the Functor
typeclass, although that does require the DeriveFunctor
language extension.
You can expend a few more lines of code for utility functions, so that it looks like you're actually programming:
leaf :: a -> Tree a leaf x = Tree x [] create :: a -> [Tree a] -> Tree a create = Tree
These functions correspond to the static methods on the above Tree
class. With them, you can now create a tree:
source :: Tree Int source = create 42 [ create 1337 [ leaf (-3)], create 7 [ leaf (-99), leaf 100, leaf 0]]
You can translate such a tree of integers to a tree of strings with the fmap
function:
dest :: Tree String dest = fmap show source
or with the infix operator:
dest :: Tree String dest = show <$> source
The <$>
operator is an alias for fmap
.
In F#, the type definition has the same structure as in Haskell:
type Tree<'a> = Tree of ('a * Tree<'a> list)
Unlike Haskell, however, F# doesn't have any built-in functor awareness, so you'll have to implement the map function yourself:
// ('a -> 'b) -> Tree<'a> -> Tree<'b> let rec map f (Tree (x, children)) = let mappedX = f x let mappedChildren = children |> List.map (map f) Tree (mappedX, mappedChildren)
Notice that you have to use the rec
keyword in order to make map
recursive. The implementation is similar to the C# code: first use f
to map the contained item, and then recursively map the children.
To keep all three examples equivalent, you can also define utility functions:
// 'a -> Tree<'a> let leaf x = Tree (x, List.empty) // 'a -> Tree<'a> list -> Tree<'a> let create x children = Tree (x, children)
This enables you to create a tree like this:
// Tree<int> let source = Tree.create 42 [ Tree.create 1337 [ Tree.leaf -3] Tree.create 7 [ Tree.leaf -99 Tree.leaf 100 Tree.leaf 0]]
which you can translate like this:
// Tree<string> let dest = source |> Tree.map string
Here, all of the above functions are defined in a module named Tree
.
The Select
method obeys the first functor law. As usual, it's proper computer-science work to actually prove that, but you can write some tests to demonstrate the first functor law for the Tree<T>
class. In this article, you'll see a few parametrised tests written with xUnit.net. First, you can define some reusable trees as test input:
public static IEnumerable<object[]> Trees { get { yield return new[] { Tree.Leaf(42) }; yield return new[] { Tree.Create(-32, Tree.Leaf(0)) }; yield return new[] { Tree.Create(99, Tree.Leaf(90), Tree.Leaf(2)) }; yield return new[] { Tree.Create(99, Tree.Leaf(90), Tree.Create(2, Tree.Leaf(-3))) }; yield return new[] { Tree.Create(42, Tree.Create(1337, Tree.Leaf(-3)), Tree.Create(7, Tree.Leaf(-99), Tree.Leaf(100), Tree.Leaf(0))) }; } }
This is just a collection of five small trees that can be used as input for parametrised tests. The first tree is only a single node - the simplest tree you can make with the Tree<T>
class.
You can use this static property as a source of input for parametrised tests. Here's one that demonstrates that the first functor law holds:
[Theory, MemberData(nameof(Trees))] public void FirstFunctorLaw(Tree<int> tree) { Assert.Equal(tree, tree.Select(x => x)); }
Here, I chose to implement the identity function as an anonymous lambda expression. In contrast, in the previous article, I explicitly declared a function variable and called it id
. Those two ways to express the identity function are equivalent.
As always, I'd like to emphasise that this test doesn't prove that Tree<T>
obeys the first functor law. It only demonstrates that the law holds for those five examples.
Like the above example, you can also write a parametrised test that demonstrates that Tree<T>
obeys the second functor law. You can reuse the Trees
test case source for that test:
[Theory, MemberData(nameof(Trees))] public void SecondFunctorLaw(Tree<int> tree) { string g(int i) => i.ToString(); bool f(string s) => s.Length % 2 == 0; Assert.Equal(tree.Select(g).Select(f), tree.Select(i => f(g(i)))); }
This test defines two local functions, f
and g
. Instead of explicitly declaring the functions as Func
variables, this test uses a (relatively) new C# feature called local functions.
Again, while the test doesn't prove anything, it demonstrates that for the five test cases, it doesn't matter if you project the tree
in one or two steps.
This was the second example of a functor implemented in a statically typed object-oriented language, but contrasted with implementations in statically typed functional languages. The concept of a functor translates without much loss of fidelity, but you'll have to write more verbose code. A language like C# isn't optimised for functors or their like; Haskell and F# are.
The purpose of this article series is to show enough examples of functors that you should start to see a pattern. Keep in mind, though, that a functor isn't a design pattern. It's a mathematical concept.
Next: A Visitor functor.


"BILHAH "faltering; bashful, Rachel’s handmaid, whom she gave to Jacob(Genesis 29:29). She was the mother of Dan and Naphtali (Genesis 30:3-8). Reuben was cursed by his father for committing adultry with her(35:22; 49:4). He was deprived of the birth-right, which was given to the sons of Joseph.
"BILHAH "faltering; bashful, Rachel’s handmaid, whom she gave to Jacob(Genesis 29:29). She was the mother of Dan and Naphtali (Genesis 30:3-8). Reuben was cursed by his father for committing adultry with her(35:22; 49:4). He was deprived of the birth-right, which was given to the sons of Joseph.