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.

In [36]:
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:

In [37]:
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()
No description has been provided for this image

A small split from zip.train. The RNG will not reproduce R's sample() exactly.

In [38]:
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.

In [39]:
digits_lda = LinearDiscriminantAnalysis()
digits_lda.fit(X_train, Y_train)
Out[39]:
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
solver solver: {'svd', 'lsqr', 'eigen'}, default='svd'

Solver to use, possible values:
- 'svd': Singular value decomposition (default).
Does not compute the covariance matrix, therefore this solver is
recommended for data with a large number of features.
- 'lsqr': Least squares solution.
Can be combined with shrinkage or custom covariance estimator.
- 'eigen': Eigenvalue decomposition.
Can be combined with shrinkage or custom covariance estimator.

.. versionchanged:: 1.2
`solver="svd"` now has experimental Array API support. See the
:ref:`Array API User Guide <array_api>` for more details.
'svd'
shrinkage shrinkage: 'auto' or float, default=None

Shrinkage parameter, possible values:
- None: no shrinkage (default).
- 'auto': automatic shrinkage using the Ledoit-Wolf lemma.
- float between 0 and 1: fixed shrinkage parameter.

This should be left to None if `covariance_estimator` is used.
Note that shrinkage works only with 'lsqr' and 'eigen' solvers.

For a usage example, see
:ref:`sphx_glr_auto_examples_classification_plot_lda.py`.
None
priors priors: array-like of shape (n_classes,), default=None

The class prior probabilities. By default, the class proportions are
inferred from the training data.
None
n_components n_components: int, default=None

Number of components (<= min(n_classes - 1, n_features)) for
dimensionality reduction. If None, will be set to
min(n_classes - 1, n_features). This parameter only affects the
`transform` method.

For a usage example, see
:ref:`sphx_glr_auto_examples_decomposition_plot_pca_vs_lda.py`.
None
store_covariance store_covariance: bool, default=False

If True, explicitly compute the weighted within-class covariance
matrix when solver is 'svd'. The matrix is always computed
and stored for the other solvers.

.. versionadded:: 0.17
False
tol tol: float, default=1.0e-4

Absolute threshold for a singular value of X to be considered
significant, used to estimate the rank of X. Dimensions whose
singular values are non-significant are discarded. Only used if
solver is 'svd'.

.. versionadded:: 0.17
0.0001
covariance_estimator covariance_estimator: covariance estimator, default=None

If not None, `covariance_estimator` is used to estimate
the covariance matrices instead of relying on the empirical
covariance estimator (with potential shrinkage).
The object should have a fit method and a ``covariance_`` attribute
like the estimators in :mod:`sklearn.covariance`.
if None the shrinkage parameter drives the estimate.

This should be left to None if `shrinkage` is used.
Note that `covariance_estimator` works only with 'lsqr' and 'eigen'
solvers.

.. versionadded:: 0.24
None
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.

In [40]:
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.

In [41]:
# 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().

In [42]:
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.

In [43]:
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()
No description has been provided for this image

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}$.

In [44]:
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
In [45]:
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:

In [46]:
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:

In [47]:
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:

In [48]:
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$:

In [49]:
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.

In [50]:
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
In [51]:
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()
No description has been provided for this image

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.

In [52]:
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