Tính toán hiệu quả các thuật toán nhỏ nhất trong NumPy

Question

Tôi cần giải quyết một tập hợp lớn các hệ thống tuyến tính, theo nghĩa tối thiểu. Tôi gặp khó khăn trong việc tìm hiểu sự khác biệt về hiệu suất tính toán của numpy.linalg.lstsq(a, b), np.dot(np.linalg.pinv(a), b) và việc triển khai toán học.

tôi sử dụng các ma trận sau:

h=np.random.random((50000,100)) 
a=h[:,:-1].copy() 
b=-h[:,-1].copy() 

và kết quả của các thuật toán là:

---

# mathematical implementation 
%%timeit 
np.dot(np.dot(np.linalg.inv(np.dot(a.T,a)),a.T),b) 

10 vòng, tốt nhất là 3: 36,3 ms mỗi vòng lặp

---

# numpy.linalg.lstsq implementation 
%%timeit 
np.linalg.lstsq(a, b)[0] 

10 vòng, tốt nhất là 3: 103 ms mỗi vòng lặp

---

%%timeit 
np.dot(np.linalg.pinv(a), b) 

1 vòng lặp, tốt nhất là 3: 216 ms mỗi vòng lặp

---

Tại sao lại có một sự khác biệt?

Answer 1

Thường lệ lstsq xử lý mọi hệ thống: xác định quá mức, chưa xác định hoặc được xác định rõ. Sản lượng của nó là những gì bạn sẽ nhận được từ pinv (a) * b nhưng nó nhanh hơn so với tính toán pseudoinverse. Đây là lý do:

Lời khuyên chung: không tính toán ma trận nghịch đảo trừ khi bạn thực sự cần nó. Giải quyết một hệ thống cho một bên tay phải cụ thể là nhanh hơn đảo ngược ma trận của nó.

Tuy nhiên, cách tiếp cận của bạn bằng cách giải quyết ^T a = a ^T b nhanh hơn, ngay cả khi bạn đang đảo ngược ma trận. Đưa cái gì? Vấn đề là, đảo ngược một ^T a chỉ có giá trị khi có một thứ hạng cột đầy đủ. Vì vậy, bạn đã hạn chế vấn đề với tình huống cụ thể này, và đạt được tốc độ như là một thương mại cho ít tổng quát và, như tôi hiển thị dưới đây, vì sự an toàn ít hơn.

Nhưng đảo ngược ma trận vẫn không hiệu quả. Nếu bạn biết rằng một có cột thứ hạng đầy đủ, sau đây là nhanh hơn so với bất kỳ của ba nỗ lực của bạn:

np.linalg.solve(np.dot(a.T, a), np.dot(a.T, b)) 

---

Điều đó nói rằng, lstsq vẫn còn thích hợp hơn để ở trên khi giao dịch với ma trận kém lạnh. Tạo thành sản phẩm là ^T một cách cơ bản hình vuông số điều kiện, vì vậy bạn có nhiều khả năng nhận được kết quả vô nghĩa hơn. Dưới đây là một ví dụ cảnh báo, sử dụng mô-đun scipy của linalg (mà chủ yếu là tương đương với NumPy nhưng có phương pháp hơn):

import numpy as np 
import scipy.linalg as sl 
a = sl.hilbert(10) # a poorly conditioned square matrix of size 10 
b = np.arange(10)  # right hand side 
sol1 = sl.solve(a, b) 
sol2 = sl.lstsq(a, b)[0] 
sol3 = sl.solve(np.dot(a.T, a), np.dot(a.T, b)) 

đây lstsq cho hầu hết sản lượng giống như solve (giải pháp độc đáo của hệ thống này).Tuy nhiên, sol3 là hoàn toàn sai vì các vấn đề số (mà bạn thậm chí sẽ không được cảnh báo về).

sol1:

[ -9.89821788e+02, 9.70047434e+04, -2.30439738e+06, 
    2.30601241e+07, -1.19805858e+08, 3.55637424e+08, 
    -6.25523002e+08, 6.44058066e+08, -3.58346765e+08, 
    8.31333426e+07] 

sol2:

[ -9.89864366e+02, 9.70082635e+04, -2.30446978e+06, 
    2.30607638e+07, -1.19808838e+08, 3.55645452e+08, 
    -6.25535946e+08, 6.44070387e+08, -3.58353147e+08, 
    8.31347297e+07] 

sol3:

[ 1.06913852e+03, -4.61691763e+04, 4.83968833e+05, 
    -2.08929571e+06, 4.55280530e+06, -5.88433943e+06, 
    5.92025910e+06, -5.56507455e+06, 3.62262620e+06, 
    -9.94523917e+05]