7.4b The Digits Recognition Example¶
Discriminant analysis in Python¶
To make the ideas concrete we use the handwritten ZIP-code digits from The Elements of Statistical Learning. In R the data originally in ElemStatLearn are now available in tensorBSS. Here we load the same flat files: each row is a label in $\{0,1,\ldots,9\}$ followed by a $16\times 16$ grayscale image stored as 256 pixels. The task is to classify the digit. We will try LDA, QDA, FDA, and naive Bayes.
ESL also provides a proper test set zip.test ($n = 2007$). Below we instead draw a small training/test split from zip.train so that the demonstration stays fast; you should feel free to repeat the analysis on the official zip.test.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from pathlib import Path
from sklearn.discriminant_analysis import (
LinearDiscriminantAnalysis,
QuadraticDiscriminantAnalysis,
)
from sklearn.naive_bayes import GaussianNB
from sklearn.metrics import accuracy_score
from pathlib import Path
from urllib.request import urlretrieve
import gzip
import shutil
import pandas as pd
ESL_URL = "https://web.stanford.edu/~hastie/ElemStatLearn/datasets/zip.train.gz"
ZIP_TRAIN_PATH = Path.cwd() / "Downloads" / "zip.train"
def ensure_zip_train(path=ZIP_TRAIN_PATH):
path = Path(path)
path.parent.mkdir(parents=True, exist_ok=True)
if path.exists() and path.stat().st_size > 0:
print("Using cached file:", path.resolve())
return path
gz_path = path.with_name("zip.train.gz")
print("Downloading", ESL_URL)
print("Working directory:", Path.cwd())
urlretrieve(ESL_URL, gz_path)
with gzip.open(gz_path, "rb") as src, path.open("wb") as dst:
shutil.copyfileobj(src, dst)
print("Saved", path.resolve(), "size", path.stat().st_size)
return path
def load_zip_dataset(path):
return pd.read_csv(path, sep=r"\s+", header=None, engine="python", comment="#")
ZIP_TRAIN_PATH = ensure_zip_train()
zip_train_df = load_zip_dataset(ZIP_TRAIN_PATH)
print(zip_train_df.shape) # expect (7291, 257)
Using cached file: /Users/alexandrachronopoulou/Library/CloudStorage/Dropbox/Teaching/CS 598 PSL/STAT 542 Online Book/Book Code for Examples/Downloads/zip.train (7291, 257)
Column 1 (index 0 in Python) is the digit label; columns 2 through 257 are the pixels. A few training images:
fig, axes = plt.subplots(2, 3, figsize=(6, 4))
plt.subplots_adjust(wspace=0.05, hspace=0.05)
for i, ax in enumerate(axes.flat):
v = zip_train_df.iloc[i, 1:].to_numpy(dtype=float)
# R: matrix(..., nrow = 16, byrow = TRUE); then t(M)[, 16:1]
M = v.reshape(16, 16, order="C").T[:, ::-1]
ax.imshow(M, cmap="gray", interpolation="nearest", origin="lower")
ax.axis("off")
plt.show()
A small split from zip.train. The RNG will not reproduce R's sample() exactly.
rng = np.random.default_rng(598)
n = len(zip_train_df)
all_idx = np.arange(n)
train_idx = rng.choice(n, size=800, replace=False)
remaining_idx = np.setdiff1d(all_idx, train_idx, assume_unique=False)
test_idx = rng.choice(remaining_idx, size=200, replace=False)
train_zip = zip_train_df.iloc[train_idx].reset_index(drop=True)
test_zip = zip_train_df.iloc[test_idx].reset_index(drop=True)
X_train = train_zip.iloc[:, 1:257].to_numpy(dtype=float)
Y_train = train_zip.iloc[:, 0].to_numpy(dtype=int)
X_test = test_zip.iloc[:, 1:257].to_numpy(dtype=float)
Y_test = test_zip.iloc[:, 0].to_numpy(dtype=int)
print(X_train.shape, Y_train.shape, X_test.shape, Y_test.shape)
(800, 256) (800,) (200, 256) (200,)
Linear Discriminant Analysis (LDA)¶
sklearn's LinearDiscriminantAnalysis is the counterpart of R's MASS::lda. By default it uses the SVD solver, which is more stable than an explicit pooled-covariance inverse when $p$ is large.
digits_lda = LinearDiscriminantAnalysis()
digits_lda.fit(X_train, Y_train)
LinearDiscriminantAnalysis()In a Jupyter environment, please rerun this cell to show the HTML representation or trust the notebook.
On GitHub, the HTML representation is unable to render, please try loading this page with nbviewer.org.
Parameters
Fitted attributes
| Name | Type | Value |
|---|---|---|
|
classes_
classes_: array-like of shape (n_classes,) Unique class labels. |
ndarray[int64](10,) | [0,1,2,...,7,8,9] |
|
coef_
coef_: ndarray of shape (n_features,) or (n_classes, n_features) Weight vector(s). |
ndarray[float64](10, 256) | [[ 50.04,-12.01, -5.58,...,-16.8 , 17.88,-25.23], [-56.64, 13.94, 5.38,..., 7.11, -7.03, 20.66], [ 30.3 , -5.01, -1.53,..., 1.58, 7.78, 16.46], ..., [-26.79, 12.75, -0.45,..., -1.19, -6.17, -9.16], [ 0.22, 4.08, -1.11,..., 10. ,-16.23, 22.27], [ 2.36, 8.13, 0.13,..., 10.64,-14.42, -4.44]] |
|
explained_variance_ratio_
explained_variance_ratio_: ndarray of shape (n_components,) Percentage of variance explained by each of the selected components. If ``n_components`` is not set then all components are stored and the sum of explained variances is equal to 1.0. Only available when eigen or svd solver is used. |
ndarray[float64](9,) | [0.34,0.18,0.14,...,0.04,0.03,0.02] |
|
intercept_
intercept_: ndarray of shape (n_classes,) Intercept term. |
ndarray[float64](10,) | [ 1.1 ,-132.93, 33.08,..., -0.44, -28.46, 10.95] |
|
means_
means_: array-like of shape (n_classes, n_features) Class-wise means. |
ndarray[float64](10, 256) | [[-1. ,-0.99,-0.99,...,-1. ,-1. ,-1. ], [-1. ,-1. ,-1. ,...,-1. ,-1. ,-1. ], [-1. ,-0.98,-0.91,...,-0.76,-0.83,-0.95], ..., [-0.99,-0.93,-0.82,...,-1. ,-1. ,-1. ], [-1. ,-1. ,-0.98,...,-1. ,-1. ,-1. ], [-1. ,-1. ,-1. ,...,-1. ,-1. ,-1. ]] |
|
n_features_in_
n_features_in_: int Number of features seen during :term:`fit`. .. versionadded:: 0.24 |
int | 256 |
|
priors_
priors_: array-like of shape (n_classes,) Class priors (sum to 1). |
ndarray[float64](10,) | [0.16,0.18,0.1 ,...,0.09,0.05,0.08] |
|
scalings_
scalings_: array-like of shape (rank, n_classes - 1) Scaling of the features in the space spanned by the class centroids. Only available for 'svd' and 'eigen' solvers. |
ndarray[float64](256, 9) | [[-7.27, 2.94,-2.33,...,-0.67,-6.05, 2.82], [ 2.19,-0.21, 1.64,...,-0.34, 2.88,-0.07], [ 0.62,-0.39, 0.07,...,-0.86,-0.44, 0.32], ..., [ 1.59, 0.5 , 0.06,...,-0.43, 1.84, 1.26], [-1.64,-0.11,-1.63,..., 3.66,-3.22,-1.57], [ 2.05,-3.15, 2.51,...,-2.27, 6.31, 1.37]] |
|
xbar_
xbar_: array-like of shape (n_features,) Overall mean. Only present if solver is 'svd'. |
ndarray[float64](256,) | [-1. ,-0.99,-0.96,...,-0.96,-0.98,-1. ] |
9 features
| lineardiscriminantanalysis0 |
| lineardiscriminantanalysis1 |
| lineardiscriminantanalysis2 |
| lineardiscriminantanalysis3 |
| lineardiscriminantanalysis4 |
| lineardiscriminantanalysis5 |
| lineardiscriminantanalysis6 |
| lineardiscriminantanalysis7 |
| lineardiscriminantanalysis8 |
Predict and compute the test accuracy. Uncomment the cross-tab if you want the full confusion matrix.
Y_predicted = digits_lda.predict(X_test)
acc_lda = accuracy_score(Y_test, Y_predicted)
print(f"LDA test accuracy: {acc_lda:.3f}")
# pd.crosstab(pd.Series(Y_test, name="True"),
# pd.Series(Y_predicted, name="Predicted"))
LDA test accuracy: 0.845
On a given 800/200 split the accuracy is typically in the mid-80s. The number will move if you change the seed or the split sizes; the official zip.test is a harder benchmark.
Quadratic Discriminant Analysis (QDA)¶
With $p = 256$ pixels and only a few hundred observations per digit, each class covariance is rank-deficient. MASS::qda stops with an error. sklearn's QuadraticDiscriminantAnalysis will often fit anyway and emit a collinearity warning; the resulting rule is numerically unstable. A small reg_param is the analogue of the $\hat\Sigma_k + \eta I$ ridge used in the notes.
# Unregularized QDA — ill-posed here (singular Sigma_k).
# digits_qda = QuadraticDiscriminantAnalysis()
# digits_qda.fit(X_train, Y_train)
# Optional regularized version, if you want a number to compare:
# digits_qda = QuadraticDiscriminantAnalysis(reg_param=0.05)
# digits_qda.fit(X_train, Y_train)
# print(accuracy_score(Y_test, digits_qda.predict(X_test)))
Fisher Discriminant Analysis (FDA)¶
Project the data onto the Fisher directions. In R these are lda()$scaling; in sklearn they are scalings_. For ten digits there are at most $K-1 = 9$ directions.
transform() applies the same map after centering, which is the preferred way to get LD / FDA coordinates. Multiplying by scalings_ alone skips the centering step and will not match transform().
FDA_digits_directions = digits_lda.scalings_
print(FDA_digits_directions.shape) # (256, 9) if all 10 digits appear in the train split
(256, 9)
These directions turned out to be 9 in our case (provided every digit appears at least once in the training sample).
For illustration we display the projection onto the first two directions. Other pairs of columns tell different stories.
F_train = digits_lda.transform(X_train)
F_test = digits_lda.transform(X_test)
cmap = plt.cm.tab10
def plot_ld_text(ax, F, y, title):
ax.set_title(title)
ax.set_xlabel("FD 1")
ax.set_ylabel("FD 2")
for xi, yi, lab in zip(F[:, 0], F[:, 1], y):
ax.text(xi, yi, str(int(lab)), color=cmap(int(lab) % 10),
fontsize=7, ha="center", va="center")
x1, x2 = np.min(F[:, 0]), np.max(F[:, 0])
y1, y2 = np.min(F[:, 1]), np.max(F[:, 1])
mx, my = 0.05 * (x2 - x1 + 1e-8), 0.05 * (y2 - y1 + 1e-8)
ax.set_xlim(x1 - mx, x2 + mx)
ax.set_ylim(y1 - my, y2 + my)
fig, axes = plt.subplots(1, 2, figsize=(12, 5), constrained_layout=True)
plot_ld_text(axes[0], F_train, Y_train, "Training")
plot_ld_text(axes[1], F_test, Y_test, "Test")
plt.show()
The training cloud (left) looks neatly separated. The test cloud (right) does not reproduce that separation. That gap is overfitting: the nine directions were tuned to the 800 training images.
Computational remarks¶
We can recover the same directions by forming $W$ and $B$ explicitly. In R this was a no-intercept dummy regression of the features on the class labels. The Python equivalent is: residuals $\mathbf{x}_i - \hat\mu_{y_i}$ and fitted values $\hat\mu_{y_i}$.
X = np.asarray(X_train, dtype=float)
y = np.asarray(Y_train)
n, p = X.shape
classes = np.unique(y)
mu = np.vstack([X[y == c].mean(axis=0) for c in classes])
class_index = {c: i for i, c in enumerate(classes)}
mu_y = np.vstack([mu[class_index[ci]] for ci in y]) # fitted class means
R = X - mu_y # residuals
W = np.cov(R, rowvar=False, bias=False) # within-class / pooled
B = np.cov(mu_y, rowvar=False, bias=False) # between-class (R: cov(fitted))
eigvals_W, eigvecs_W = np.linalg.eigh(W)
print("W eigenvalues: min / median / max =",
eigvals_W.min(), np.median(eigvals_W), eigvals_W.max())
print("Number of nonpositive eigenvalues of W:", np.sum(eigvals_W <= 0))
# W^{-1/2}, with a floor on tiny/negative eigenvalues
ev = np.clip(eigvals_W, 1e-8, None)
A = (eigvecs_W * (1.0 / np.sqrt(ev))) @ eigvecs_W.T
W eigenvalues: min / median / max = 5.01633638376747e-05 0.04272249624718073 6.732068592273499 Number of nonpositive eigenvalues of W: 0
M = A @ B @ A.T
vals, vecs = np.linalg.eigh(M)
order = np.argsort(vals)[::-1] # R's eigen() is descending
vals, vecs = vals[order], vecs[:, order]
k = min(9, vecs.shape[1], FDA_digits_directions.shape[1])
FDA_eigen_dir = A @ vecs[:, :k]
# Signs of eigenvectors are arbitrary, so correlations may be ±1
for j in range(k):
corr = np.corrcoef(FDA_eigen_dir[:, j], FDA_digits_directions[:, j])[0, 1]
print(f"direction {j+1}: corr = {corr:+.4f}")
direction 1: corr = +1.0000 direction 2: corr = +1.0000 direction 3: corr = -1.0000 direction 4: corr = +1.0000 direction 5: corr = -1.0000 direction 6: corr = +1.0000 direction 7: corr = +1.0000 direction 8: corr = -1.0000 direction 9: corr = +1.0000
FDA vs. PCA¶
PCA ignores the labels. The leading principal axes need not be good separating directions. Obtain the top 100 PCs from the training covariance:
Sigma = np.cov(X_train, rowvar=False, bias=False)
eigvals_S, eigvecs_S = np.linalg.eigh(Sigma)
order = np.argsort(eigvals_S)[::-1]
PCA_dir = eigvecs_S[:, order][:, :100]
print(PCA_dir.shape)
(256, 100)
PCA directions are orthonormal in the usual Euclidean inner product:
print(np.round(PCA_dir[:, :10].T @ PCA_dir[:, :10], 2))
[[ 1. 0. -0. 0. -0. -0. -0. 0. -0. -0.] [ 0. 1. -0. 0. 0. -0. 0. -0. -0. 0.] [-0. -0. 1. 0. -0. -0. -0. 0. -0. 0.] [ 0. 0. 0. 1. 0. 0. -0. 0. 0. -0.] [-0. 0. -0. 0. 1. 0. -0. 0. -0. 0.] [-0. -0. -0. 0. 0. 1. 0. 0. 0. -0.] [-0. 0. -0. -0. -0. 0. 1. -0. -0. 0.] [ 0. -0. 0. 0. 0. 0. -0. 1. -0. 0.] [-0. -0. -0. 0. -0. 0. -0. -0. 1. -0.] [-0. 0. 0. -0. 0. -0. 0. 0. -0. 1.]]
but FDA directions are not:
print(np.round(FDA_eigen_dir.T @ FDA_eigen_dir, 2))
[[163.02 -5.72 -66.02 17.04 -5.23 -19.03 -12.9 -73.2 -19.52] [ -5.72 237.65 -74.32 132.83 -85.39 -19.07 64.76 92.02 -26.29] [-66.02 -74.32 161.52 -75.4 53.58 4.61 -21.17 13.26 5.67] [ 17.04 132.83 -75.4 154.69 -37.43 -14.65 57.2 71.74 -22.89] [ -5.23 -85.39 53.58 -37.43 267.88 -73.56 -69.11 15.83 19.54] [-19.03 -19.07 4.61 -14.65 -73.56 127.22 17.91 -39.99 2.55] [-12.9 64.76 -21.17 57.2 -69.11 17.91 180.46 39.21 0.27] [-73.2 92.02 13.26 71.74 15.83 -39.99 39.21 193.96 -9.2 ] [-19.52 -26.29 5.67 -22.89 19.54 2.55 0.27 -9.2 88.73]]
They are orthogonal with respect to $W$:
print(np.round(FDA_eigen_dir.T @ W @ FDA_eigen_dir, 2))
[[ 1. -0. 0. -0. -0. 0. 0. 0. -0.] [-0. 1. 0. -0. -0. 0. 0. -0. 0.] [ 0. 0. 1. 0. 0. 0. -0. -0. 0.] [-0. -0. 0. 1. -0. -0. 0. 0. 0.] [-0. -0. 0. -0. 1. 0. 0. -0. 0.] [ 0. 0. 0. -0. 0. 1. 0. 0. -0.] [ 0. 0. -0. 0. 0. -0. 1. 0. 0.] [ 0. 0. -0. 0. -0. 0. 0. 1. 0.] [-0. 0. 0. 0. 0. -0. 0. 0. 1.]]
A practical compromise is to reduce dimension with PCA first and then run LDA/FDA in the principal subspace. That often trades a little training separation for a more stable test result.
newX_train = X_train @ PCA_dir
newX_test = X_test @ PCA_dir
new_digits_lda = LinearDiscriminantAnalysis()
new_digits_lda.fit(newX_train, Y_train)
Y_test_pred = new_digits_lda.predict(newX_test)
print(pd.crosstab(pd.Series(Y_test, name="True"),
pd.Series(Y_test_pred, name="Predicted")))
print("Test error count:", np.sum(Y_test != Y_test_pred))
print("Test accuracy:", accuracy_score(Y_test, Y_test_pred))
Predicted 0 1 2 3 4 5 6 7 8 9 True 0 26 0 0 0 1 0 0 0 1 0 1 0 23 0 0 0 0 0 0 0 0 2 0 0 20 0 1 0 0 1 1 0 3 0 0 0 19 0 0 0 0 0 0 4 0 0 1 0 15 0 0 0 0 4 5 2 0 1 1 0 13 0 0 0 0 6 0 0 1 0 0 1 13 0 0 0 7 0 0 0 0 0 0 0 15 0 2 8 1 0 0 1 1 1 0 0 13 0 9 0 0 0 0 0 0 0 3 0 18 Test error count: 25 Test accuracy: 0.875
newF = new_digits_lda.transform(newX_train)
newF_test = new_digits_lda.transform(newX_test)
fig, axes = plt.subplots(1, 2, figsize=(12, 5), constrained_layout=True)
plot_ld_text(axes[0], newF, Y_train, "Training (PCA then LDA)")
plot_ld_text(axes[1], newF_test, Y_test, "Test (PCA then LDA)")
plt.show()
Training separation is less dramatic after the $256 \to 100$ compression, but the training and test pictures are more consistent — the usual signature that we have given up some overfit.
Naive Bayes prediction¶
As a high-dimensional baseline we fit Gaussian naive Bayes to a two-class slice (digits 1 versus 7). Restricting to two classes makes the confusion matrix easy to read; GaussianNB will also run on all ten digits. This is the counterpart of e1071::naiveBayes used on numeric features.
zip17_train = train_zip[train_zip.iloc[:, 0].isin([1, 7])].reset_index(drop=True)
zip17_test = test_zip[test_zip.iloc[:, 0].isin([1, 7])].reset_index(drop=True)
Y_17 = zip17_train.iloc[:, 0].to_numpy(dtype=int)
X_17 = zip17_train.iloc[:, 1:].to_numpy(dtype=float)
Y_17_test = zip17_test.iloc[:, 0].to_numpy(dtype=int)
X_17_test = zip17_test.iloc[:, 1:].to_numpy(dtype=float)
NBfit = GaussianNB()
NBfit.fit(X_17, Y_17)
y_pred = NBfit.predict(X_17_test)
print(f"Naive Bayes test accuracy (1 vs 7): {accuracy_score(Y_17_test, y_pred):.3f}")
print(pd.crosstab(pd.Series(y_pred, name="Predicted"),
pd.Series(Y_17_test, name="Actual")))
Naive Bayes test accuracy (1 vs 7): 0.950 Actual 1 7 Predicted 1 22 1 7 1 16