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:
- Read the Reminder of the method or algorithm.
- Implement a naive Python version (loops, direct formulas).
- Compare with the optimized version using NumPy or scikit-learn.
- Measure and discuss execution times.
Exercises
Question 1: Determinant of a Matrix
Reminder: The determinant of an matrix can be computed recursively using Laplace expansion:
where is the minor of obtained by removing row and column . Complexity grows as .
Task
Implement this recursive method in Python and compare with numpy.linalg.det.
def my_determinant(M):
# TODO: implement recursicec Laplace expansion
return detMeasuer execution time for matrices of size and discuss complexity.
Solution
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 of a matrix :
- Choose random vector .
- Iterate until convergence.
- Approximate eigenvalue: .
Task
Implement Power Iteration to approximate the largest eigenvalue of a symmetric matrix. Compare results and execution times with numpy.linalg.eig.
Solution
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 of a matrix can be obtained by computing the dominant eigenvector of . Then . 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
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:
- Center data: .
- Compute covariance:
- Find eigenvectors/eigenvalues of .
- Project data on top 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
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 :
Task
Implement cosine similarity manually. Compare with sklearn.metrics.pairwise.cosine_similarity. Test with vectors of dimension , and compare execution times.
Solution
Will not work as intended due to memory issues.
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}")