An objective function gives training a quantity to optimize. In supervised learning, a model learns from examples with known outputs; during testing, it applies what it learned to new inputs. When the objective is a loss function, its value on the training examples is the training loss. section 1.0 section 1.1
Let f(x; θ) be a model with learnable parameters θ, and let (xᵢ, yᵢ) be an input and its true label. A loss measures how far predictions are from the labels. Training seeks parameters that minimize the chosen loss; the choice depends on what the model must predict. section 1.1
Two supervised-learning objectives illustrate that choice:
- Classification: average misclassification loss counts predictions that disagree with their labels. For n examples, L(θ) = (1/n) Σᵢ 1[f(xᵢ; θ) ≠ yᵢ], where 1[·] is one when its condition is true and zero otherwise. Cross-entropy is another classification loss, deferred to later treatment. section 1.1
- Regression: mean squared error averages (yᵢ − f(xᵢ; θ))² over the examples. Squaring removes the sign of each error and penalizes larger deviations more heavily. section 1.1
An objective need not compare each prediction directly with a label. A CART decision tree chooses a feature and threshold that minimize the cost of a proposed split. For classification, Gini impurity or entropy can score how mixed the resulting regions are; both are zero for a pure region. Tree depth also matters because an overly deep tree can overfit. section 5.6
Choosing a tree split
Given a training matrix with n examples and d features, consider each feature j and candidate threshold t formed from midpoints of observed feature values. Score the resulting partition, then select the feature–threshold pair with the lowest cost. This is a greedy choice made while constructing the tree. section 5.6
Listing 5.5 CART decision tree algorithm
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
class TreeNode():
def __init__(self, gini, num_samples, num_samples_class, class_label):
self.gini = gini #1
self.num_samples = num_samples #2
self.num_samples_class = num_samples_class #3
self.class_label = class_label #4
self.feature_idx = 0 #5
self.treshold = 0 #6
self.left = None #7
self.right = None #8
class DecisionTreeClassifier():
def __init__(self, max_depth = None):
self.max_depth = max_depth
def best_split(self, X_train, y_train):
m = y_train.size
if (m <= 1):
return None, None
mk = [np.sum(y_train == k) for k in range(self
.num_classes)] #9
best_gini = 1.0 – sum((n / m) ** 2 for n in mk) #10
best_idx, best_thr = None, None
#iterate over all features
for idx in range(self.num_features):
thresholds, classes = zip(*sorted(zip(X[:,
idx], y))) #11
num_left = [0]*self.num_classes
num_right = mk.copy()
for i in range(1, m): #12
k = classes[i-1]
num_left[k] += 1
num_right[k] -= 1
gini_left = 1.0 - sum(
(num_left[x] / i) ** 2 for x in range(self.num_classes)
)
gini_right = 1.0 - sum(
(num_right[x] / (m - i)) ** 2 for x in
range(self.num_classes)
)
gini = (i * gini_left + (m - i) * gini_right) / m
if thresholds[i] == thresholds[i - 1]:
continue
if (gini < best_gini):
best_gini = gini
best_idx = idx
best_thr = (thresholds[i] +
thresholds[i - 1]) / 2 #13
#end if
#end for
#end for
return best_idx, best_thr
def gini(self, y_train):
m = y_train.size
return 1.0 - sum((np.sum(y_train == k) / m) ** 2 for k in
range(self.num_classes))
def fit(self, X_train, y_train):
self.num_classes = len(set(y_train))
self.num_features = X_train.shape[1]
self.tree = self.grow_tree(X_train, y_train)
def grow_tree(self, X_train, y_train, depth=0):
num_samples_class = [np.sum(y_train == k) for k in
range(self.num_classes)]
class_label = np.argmax(num_samples_class)
node = TreeNode(
gini=self.gini(y_train),
num_samples=y_train.size,
num_samples_class=num_samples_class,
class_label=class_label,
)
if depth < self.max_depth: #14
idx, thr = self.best_split(X_train, y_train)
if idx is not None:
indices_left = X_train[:, idx] < thr
X_left, y_left = X_train[indices_left], y_train[indices_left]
X_right, y_right = X_train[~indices_left], y_train[~indices_left]
node.feature_index = idx
node.threshold = thr
node.left = self.grow_tree(X_left, y_left, depth + 1)
node.right = self.grow_tree(X_right, y_right, depth + 1)
return node
def predict(self, X_test):
return [self.predict_helper(x_test) for x_test in X_test]
def predict_helper(self, x_test):
node = self.tree
while node.left:
if x_test[node.feature_index] < node.threshold:
node = node.left
else:
node = node.right
return node.class_label
if __name__ == "__main__":
#load data
iris = load_iris()
X = iris.data[:, [2,3]]
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2,
random_state=42)
print("decision tree classifier...")
tree_clf = DecisionTreeClassifier(max_depth = 3)
tree_clf.fit(X_train, y_train)
print("prediction...")
y_pred = tree_clf.predict(X_test)
tree_clf_acc = accuracy_score(y_test, y_pred)
print("test set accuracy: ", tree_clf_acc)
The CART implementation stores node impurity and class counts and includes a best_split method for selecting a split from training data. section 5.6
In a deep neural network, backpropagation supports minimizing an objective across layers with learnable weights and biases. More generally, an optimizer can minimize a target without that target being a training loss: simulated annealing searches an energy landscape by sometimes accepting higher-energy proposals as its temperature decreases. section 1.4 section 9.4
