TP2

ipynb15 kBPython · 11 cellsIn TP 2

TP2- Linear Algebra for Machine Learning

Real Data Applications in Python: Performance & Accuracy

Objectives

  • Manipulate vectors and matrices and connect these operations to ML tasks (similarities, PCA, SVD).
  • Compare accuracy and execution time between homemade implementations and optimized library functions.
  • Develop skills in profiling (time measurement) and numerical validation (errors, stability).

Instructions

For each question:

  1. Read the Reminder of the method or algorithm.
  2. Implement a naive Python version (loops, direct formulas).
  3. Compare with the optimized version using NumPy or scikit-learn.
  4. Measure and discuss execution times.

Exercises

Question 1: Determinant of a Matrix

Reminder: The determinant of an n×nn × n matrix can be computed recursively using Laplace expansion:

det(A)=∑j=1n(−1)i+jaijdet(Mij)\text{det}(A) = \sum_{j=1}^{n} (-1)^{i+j} a_{ij} \text{det}(M_{ij})

where M1jM_{1j} is the minor of AA obtained by removing row 11 and column jj. Complexity grows as O(n!)O(n!).

Task

Implement this recursive method in Python and compare with numpy.linalg.det.

Python
def my_determinant(M):
    # TODO: implement recursicec Laplace expansion
    return det

Measuer execution time for matrices of size n=3,5,7,10n = 3, 5, 7, 10 and discuss complexity.

Solution
In [ ]
import numpy as np, time

np.random.seed(0)


def minor_matrix(A, i, j):
    # remove row i and column j
    return np.delete(np.delete(A, i, axis=0), j, axis=1)


def det_laplace(A):
    A = np.asarray(A, dtype=float)
    n, m = A.shape
    assert n == m, "Matrix must be square."
    if n == 0:
        return 1.0
    if n == 1:
        return A[0, 0]
    if n == 2:
        return A[0, 0] * A[1, 1] - A[0, 1] * A[1, 0]
    # Expand along first row
    s = 0.0
    for j in range(n):
        cofactor = ((-1) ** (0 + j)) * A[0, j] * det_laplace(minor_matrix(A, 0, j))
        s += cofactor
    return s


def time_det(n, trials=3):
    t_lap = t_np = 0.0
    max_err = 0.0
    for _ in range(trials):
        A = np.random.randn(n, n)
        t0 = time.time()
        d1 = det_laplace(A)
        t_lap += time.time() - t0
        t0 = time.time()
        d2 = np.linalg.det(A)
        t_np += time.time() - t0
        max_err = max(max_err, abs(d1 - d2))
    t_lap /= trials
    t_np /= trials
    speedup = (t_lap / t_np) if t_np > 0 else float("inf")
    return t_lap, t_np, max_err, speedup


if __name__ == "__main__":
    for n in [3, 5, 7]:
        t1, t2, err, ratio = time_det(n, trials=3)
        print(
            f"n={n} | Laplace {t1:.4f}s | NumPy {t2:.6f}s | max|Delta|={err:.3e} | speedup={ratio:.1f}x"
        )

Question 2: Eigenvalues and Eigenvectors

Reminder: The Power Iteration algorithm finds the dominant eigenvalue λ\lambda of a matrix AA:

  1. Choose random vector b0b_0.
  2. Iterate bk+1=Abk∣∣Abk∣∣b_{k+1} = \frac{Ab_k}{||Ab_k||} until convergence.
  3. Approximate eigenvalue: λk=bkTAbkbkTbk\lambda_k = \frac{b_k^T A b_k}{b_k^T b_k}.
Task

Implement Power Iteration to approximate the largest eigenvalue of a symmetric matrix. Compare results and execution times with numpy.linalg.eig.

Solution
In [ ]
import numpy as np, time

np.random.seed(1)


def power_iteration(A, max_iter=1000, tol=1e-8):
    A = np.asarray(A, dtype=float)
    n = A.shape[0]
    b = np.random.randn(n)
    b /= np.linalg.norm(b)
    lam_old = 0.0
    for _ in range(max_iter):
        Ab = A @ b
        norm = np.linalg.norm(Ab)
        if norm == 0:
            return 0.0, b
        b = Ab / norm
        lam = b @ (A @ b)  # Rayleigh quotient
        if abs(lam - lam_old) < tol:
            break
        lam_old = lam
    return lam, b


def time_power(n, trials=3):
    t_pi = t_np = 0.0
    max_err = 0.0
    for _ in range(trials):
        X = np.random.randn(n, n)
        A = (X + X.T) / 2  # make symmetric
        t0 = time.time()
        lam, v = power_iteration(A)
        t_pi += time.time() - t0
        t0 = time.time()
        w, V = np.linalg.eig(A)
        t_np += time.time() - t0
        lam_np = np.max(np.real(w))
        max_err = max(max_err, abs(lam - lam_np))
    return t_pi / trials, t_np / trials, max_err


if __name__ == "__main__":
    for n in [50, 100, 200]:
        t1, t2, err = time_power(n)
        print(
            f"n={n} | PowerIter {t1:.4f}s | NumPy eig {t2:.4f}s | max|Delta_lambda|={err:.3e}"
        )

Question 3: Singular Value Decomposition (SVD)

Reminder: The first singular vector u1u_1 of a matrix AA can be obtained by computing the dominant eigenvector of AATA A^T . Then v1=ATu1/∣∣ATu1∣∣v_1 = A^T u_1 / ||A^T u_1|| . Iterating gives an SVD-like decomposition.

Task

Implement a naive SVD approach (first singular vector via power iteration). Compare with numpy.linalg.svd. Apply both methods to a grayscale image (100 × 100) and compare reconstruction quality and execution time.

Solution
In [ ]
import numpy as np, time

np.random.seed(2)


def top_singular_vector(A, max_iter=1000, tol=1e-8):
    # Power iteration on A A^T to get u1, then v1 = A^T u1 / ||A^T u1||, sigma1 = ||A^T u1||
    A = np.asarray(A, dtype=float)
    m, n = A.shape
    u = np.random.randn(m)
    u /= np.linalg.norm(u)
    lam_old = 0.0
    for _ in range(max_iter):
        u_new = A @ (A.T @ u)
        norm = np.linalg.norm(u_new)
        if norm == 0:
            break
        u = u_new / norm
        lam = u @ (A @ (A.T @ u))
        if abs(lam - lam_old) < tol:
            break
        lam_old = lam
    v = A.T @ u
    sigma1 = np.linalg.norm(v)
    if sigma1 > 0:
        v = v / sigma1
    return u, v, sigma1  # left vec, right vec, top singular value (approx)


def time_svd(m, n, trials=3):
    t_top = t_svd = 0.0
    max_err = 0.0
    for _ in range(trials):
        A = np.random.randn(m, n)
        t0 = time.time()
        u, v, s1 = top_singular_vector(A)
        t_top += time.time() - t0
        t0 = time.time()
        U, S, VT = np.linalg.svd(A, full_matrices=False)
        t_svd += time.time() - t0
        max_err = max(max_err, abs(s1 - S[0]))
    return t_top / trials, t_svd / trials, max_err


if __name__ == "__main__":
    for shape in [(100, 100), (200, 100), (100, 200)]:
        t1, t2, err = time_svd(*shape)
        print(
            f"{shape} | Power-Top-SV {t1:.4f}s | NumPy SVD {t2:.4f}s | max|Delta_sigma1|={err:.3e}"
        )

Question 4: Principal Component Analysis (PCA)

Reminder: PCA steps:

  1. Center data: Xc=X−XˉX_c = X − \bar{X}.
  2. Compute covariance: C=1n−1XcTXcC = \frac{1}{n-1} X^T_c X_c
  3. Find eigenvectors/eigenvalues of CC.
  4. Project data on top kk eigenvectors.
Task:
  • Implement PCA manually (following above steps).
  • Compare with sklearn.decomposition.PCA.
  • Use the digits dataset from scikit-learn and compare execution times and results
Solution
In [ ]
import numpy as np, time
from sklearn.datasets import load_digits
from sklearn.decomposition import PCA


def pca_manual(X, k):
    # Center, covariance, eigen-decomposition, sort, project
    X = np.asarray(X, dtype=float)
    Xc = X - X.mean(axis=0, keepdims=True)
    C = (Xc.T @ Xc) / (Xc.shape[0] - 1)
    w, V = np.linalg.eigh(C)  # symmetric
    idx = np.argsort(w)[::-1]
    w, V = w[idx], V[:, idx]
    Wk, Vk = w[:k], V[:, :k]
    Z = Xc @ Vk
    return Z, Vk, Wk


if __name__ == "__main__":
    digits = load_digits()
    X = digits.data  # shape (n_samples, n_features)
    k = 20

    t0 = time.time()
    Zm, Vm, Wm = pca_manual(X, k)
    t_manual = time.time() - t0

    t0 = time.time()
    pca = PCA(n_components=k, svd_solver="full").fit(X)
    Zsk = pca.transform(X)
    t_sklearn = time.time() - t0

    # Compare subspaces via principal angles: SVD of Vm.T * components.T
    U, S, VT = np.linalg.svd(Vm.T @ pca.components_[:k].T, full_matrices=False)
    subspace_cosines = S  # in [0,1]; closer to 1 => better alignment

    print(f"Manual PCA time:  {t_manual:.4f}s")
    print(f"sklearn PCA time: {t_sklearn:.4f}s")
    print("Subspace cosines (principal angles):", subspace_cosines)

Bonus: Cosine Similarity

Reminder: For two vectors x,y∈Rnx, y \in \mathbb{R}^n:

cos⁡(θ)=x⋅y∣∣x∣∣∣∣y∣∣\cos(\theta) = \frac{x \cdot y}{||x|| ||y||}
Task

Implement cosine similarity manually. Compare with sklearn.metrics.pairwise.cosine_similarity. Test with 10510^5 vectors of dimension 300300, and compare execution times.

Solution

Will not work as intended due to memory issues.

In [ ]
import numpy as np
from sklearn.metrics.pairwise import cosine_similarity
import time

# Generate random data: 10^5 vectors of dimension 300
n_samples, dim = 10**5, 300
X = np.random.randn(n_samples, dim)
Y = np.random.randn(n_samples, dim)


# ------------------------------
# Manual Implementation
# ------------------------------
def manual_cosine_similarity(X, Y):
    # Dot products between corresponding rows
    dot = np.sum(X * Y, axis=1)
    # Norms of each vector
    norm_x = np.linalg.norm(X, axis=1)
    norm_y = np.linalg.norm(Y, axis=1)
    # Avoid division by zero
    return dot / (norm_x * norm_y + 1e-10)


# Time manual implementation
start = time.time()
manual_result = manual_cosine_similarity(X, Y)
manual_time = time.time() - start
print(f"Manual Cosine Similarity Time: {manual_time:.4f} seconds")

# ------------------------------
# Scikit-Learn Implementation
# ------------------------------
# sklearn expects 2D arrays; it computes all pairwise similarities
# so we compute only diagonal values (same pairs)
start = time.time()
sklearn_result_full = cosine_similarity(X, Y)
sklearn_result = np.diag(sklearn_result_full)
sklearn_time = time.time() - start
print(f"Sklearn Cosine Similarity Time: {sklearn_time:.4f} seconds")

# ------------------------------
# Comparison
# ------------------------------
diff = np.mean(np.abs(manual_result - sklearn_result))
print(f"Mean absolute difference: {diff:.6f}")

In TP 2