This website covers a past offering of CS 135. For the current offering, go to https://www.cs.tufts.edu/cs/135/.

HW7: Decision Trees, Ensembles, and Feature Importance

Last modified: 2026-04-07 16:20

Status: RELEASED.

Due date: Wed Apr 8, 2026 by end of day (11:59 pm ET) in Medford, MA

Jump to: Background   Starter Code   Problem 1   Problem 2   Problem 3  

Turn-in links:

Overview

In this HW, you'll perform sentiment analysis with decision trees and random forests. This is broken down into 3 problems:

  • Problem 1: Train a decision tree and construct counterfactual explanations
  • Problem 2: Train a random forest and investigate the effect of n_estimators
  • Problem 3: Compare models and feature importances

Evaluation Rubric

The worth of each problem is

  • 90% PDF report
  • 5% Notebook submission
  • 5% reflection

See the PDF submission portal on Gradescope for the point values of each PDF subproblem. Generally, tasks with more coding/effort will earn more potential points.

Files to Turn In:

PDF report:

  • Prepare a short PDF report (no more than 5 pages).
  • This document will be manually graded.
  • Can use your favorite report writing tool (Word or G Docs or LaTeX or ....)
  • Should be human-readable. Do not include code. Do NOT just export a jupyter notebook to PDF.
  • Should have each subproblem marked via the in-browser Gradescope annotation tool)

Submit to the notebook assignment just the file:

  • hw7_trees.ipynb (just for completeness, will not be autograded but will be manually assessed if necessary.)

Background

To complete this HW, you'll need some knowledge from the following sessions of class:

  • Decision Trees (day19) for Problem 1
  • Random Forests (day20) for Problem 2
  • And a bit of explainability (day17)

Starter Code

The starter notebook and dataset can be found in:

https://github.com/tufts-ml-courses/cs135-26s-assignments/tree/main/hw7

Use the provided hw7_trees.ipynb as the primary notebook to guide you throughout this Problem.

Dataset: Bag-of-words representations of product reviews on Amazon

Dataset credit: M. Dredze, J. Blitzer, and Fernando Pereira. https://www.cs.jhu.edu/~mdredze/datasets/sentiment/

We consider the text sentiment classification task, as in versions of Project A from past iterations of this course. Each example is one plain-text online review collected from amazon.com for a consumer product (either a book, a movie, an electronics item, or a kitchen item).

Here's an example book review that is a positive sentiment:

This all-Spanish handbook for parents with new babies will prove essential for any concerned about a child's health.

Here's one with a negative sentiment:

It completely sucked. Very long with nothing to say. Author was proud of his own knowledge of the SCA and Wiccans, and the publishers thought that obviated the need for plot or character development.

At training time, we observe N samples of feature-label pairs, where the features are a bag-of-words representation of the written text and the label is an overall binary rating of the user's feelings about the product (either 'positive' (1) or 'negative' (0)).

Our goal is to build a model that can predict the sentiment (positive or negative) from the text alone.

We have preprocessed this data for you to the bag-of-words representation, using a fixed vocabulary of the 7729 most common words provided by the original dataset creators (with some slight modifications by us). We'll emphasize that the vocabulary includes some bigrams (e.g. "waste_of") in addition to single words.

For the n-th text review, we define our features and labels as follows:

  • Feature vector \(x_n \in \mathbb{R}^F\) is a binary vector of size F=7729, indicating which terms in the vocabulary are present in the review, and which are absent.
    • Words that are not in the vocabulary are ignored therefore have no impact on this feature vector.
  • Label \(y_n\) is a binary label (\(y_n \in \{0, 1\}\)), indicating whether that review had a negative (\(y_n = 0\)) or positive (\(y_n = 1\)) star rating.

We have included the dataset in the starter code repo:

  • a training set of 6346 documents
  • a validation set of 792 documents
  • a test set of 793 documents

Our analysis goals are:

  • Can we train tree models to solve this task well?
  • Can we the inspect these trees to understand how the model is making decisions?
  • Can we perform hyper-parameter selection as in other models that we are familiar with?

Problem 1: Decision Trees

In this problem, we'll understand how trees can be used for text classification.

Implementation Step : Train a Simple Tree

Train a DecisionTreeClassifier with criterion='entropy', max_depth=4, min_samples_leaf=1, min_samples_split=2 and random_state=101.

You'll use this simple tree again later (to make Table 1).

Short Answer 1a in Report

For a training objective, we used entropy (alternatives in Sklearn include the Gini impurity and the log loss). Each split is designed to minimize the weighted entropy as much as possible (i.e. the sum of entropy at each leaf node, weighted by how many training data points are in that node). Is the following statement true or False?

"Because the tree was constructed to minimize weighted entropy, it must have the lowest weighted entropy of any possible trees of depth 4."

Short Answer 1b in Report

Assume that a decision threshold of \(\tau=0.5\) is used to threshold the model's probability predictions and return positive or negative decisions. Consider the following positive review:

Since I've already reviewed and bought both of these as separate items, I'm not gonna repeat anything about each show (see individual reviews for that). I will just rehash what I have all along. Despite its missing pieces from the book, the Original is still 5 star material. The "in betweener" is only worth it's value because it is a disc copy (as opposed to a tape copy). My advice, buy the Original separately, and read the book to get the "real missing years". If you are building a library of "ALL Richard Chamberlain", then buy both or this combo. But be prepared to be disappointed in what the alleged "Missing Years" has to offer (again see separate review)

Note: this passage's bag of words representation is row 188 of x_tr_NF

Construct a counterfactual explanation for this passage. In other words, (a) compute the current classification for the passage, and (b) describe a minimal number of changes you can make to the passage in order to swap its classification. Describe your counterfactual in an English description, i.e. "the passage would have been classified as ... if the word(s) ... were removed/the word(s) ... were added". As stated above, try to find the counterfactual with the smallest number of edits.

In order to visualize the tree in ASCII-text, you can call the helper function pretty_print_sklearn_tree found in the starter code. To interpret the printed statements, know that "Y" means the above decision question evaluated to "yes" (meaning that the printed feature was less than \(0.5\)), while "N" means "no".

Implementation Step : Find the Best Tree

Perform a grid search for the hyperparameters of your DecisionTree over the following settings:

  • max_depth in [2, 8, 32, 128]
  • min_samples_leaf in [1, 3, 9]
  • random_state in [101]

Be sure to use sklearn.model_selection.GridSearchCV

Additional requirements (keep all other settings at default values)

  • Set scoring='balanced_accuracy', since our target metric is balanced accuracy
  • Set cv=my_splitter (as in starter code), so you can use the predefined split we defined earlier.
  • Set return_train_score=True, since we want training set scores as well as test set scores
  • Set refit=False, because we only want fits on x_tr_NF

You'll use this "best" tree again later (to make Table 1).

Problem 2: Random Forest

We'll now examine whether we can produce an ensemble of decision trees to improve performance on our classification problem.

Implementation Step : Find the Best Forest

Perform a grid search for the best random forest by searching over the following hyperparameter configurations.

  • max_features in [3, 10, 33, 100, 333]
  • max_depth in [16, 32]
  • min_samples_leaf in [1]
  • n_estimators in [100]
  • random_state in [101]

Use the best-ranked configuration to obtain one "best" random forest (trained on only the training set). The starter notebook provides code to get you started; in particular you want to keep the same settings for GridSearchCV to make sure you're training on the predefined split. You'll use this best forest later in Table 1.

Implementation Step : Increase n_estimators

Take the best hyperparameter configuration you found in the previous problem and increase n_estimators to 1000. Train a random forest with this new hyperparameter configuration.

Short Answer 2a in Report

Compare the two forests you've found, one with n_estimators=100 and one with n_estimators=1000

What is the primary tradeoff this hyperparameter controls? In other words, what is gained and lost by increasing the number of trees in the forest? In particular, speak to whether increasing the number of trees leads to overfitting.

Problem 3: Comparing Models

Here, we will compare models' performance and feature importances.

Table 1 (+caption) in Report

In one table, summarize the overall performance (in terms of balanced accuracy) of all models you've developed.

Include 4 rows, one for each model pipeline:

  • Simple decision tree (from Problem 1)
  • Best decision tree (from Problem 2)
  • Best random forest with n_estimators=100 (from Problem 2)
  • Random forest with n_estimators=1000 (from Problem 2)

Include 5 columns:

  • col 1 to indicate the number of trees
  • col 2 to indicate the max_depth used (or found via search)
  • col 3-5 report balanced accuracy on each dataset (train/valid/test)

Caption: Summarizing your conclusions from this table:

  • Which method (which row) does best on the test set?
  • Does your table's relative ranking of "best tree" and "best forest" agree with course concepts? Why or why not?

Implementation Step: Evaluating Feature Importances

Recall that each internal node of each tree results in a reduction of entropy: the set of training data points entering that internal node have some entropy, and after the split there is a new, smaller weighted entropy value (computed by finding the entropy of each branch and taking a weighted sum). The change in entropy is sometimes called the information gain of a particular conditional. It is possible to show that information gain is always positive; the two branches cannot be on average more impure/mixed than the combined set entering the node. Each split is chosen to make the information gain (aka the reduction in weighted entropy) as large as possible.

For each feature in the dataset, (i.e. each word in the vocabulary) we can keep track of how much information gain it contributes, summed over every node in the tree where it is used to split. In a random forest, we can compute the information gain for each feature in each tree and average across all the trees in the forest. These values are automatically computed by Sklearn and stored in clf.feature_importances_ (note: they are normalized to sum to 1, so what is being stored is the fraction of information gain in the model coming from each feature). For models 2-3 in Table 1 (i.e. the best tree you found and the best random forest with n_estimators=100), find the 5 words with the highest feature importances and find out how many words have importance \(\leq 10^{-5}\). We'll call those words with very small importances "unused words".

Short Answer 3a in Report

For both the tree and random forest model in rows 2-3 of Table 1, report the 5 words with the highest feature importances and the numeric value of their feature importance. Also report how many words are "unused" (importance \(\leq 10^{-5}\)). In a short paragraph, explain why these values are changing when you go from a single tree to an ensemble of 100. How would you expect these values to continue to change as you increase the number of trees? (Hint: you can check your hypothesis by estimating the feature importances of the 1000-tree ensemble, but I encourage you to come up with a theory for what you will see before you check).