Làm thế nào lớn một hệ thống là hợp lý để cố gắng làm một hồi quy tuyến tính trên?BigO của hồi quy tuyến tính là gì?
Cụ thể: Tôi có hệ thống với ~ 300 nghìn điểm mẫu và ~ 1200 cụm từ tuyến tính. Tính khả thi này có khả thi không?
Bạn có thể thể hiện điều này như một phương trình ma trận:
nơi ma trận 
là 300K hàng và 1200 cột, vector hệ số 
là 1200x1, và RHS vector 
là 1200x1.
Nếu bạn nhân hai bên bằng cách chuyển đổi ma trận 
, bạn có một hệ phương trình cho các ẩn số là 1200x1200. Bạn có thể sử dụng phân tích LU hoặc bất kỳ thuật toán nào khác mà bạn muốn giải quyết cho các hệ số. (Đây là hình vuông nhỏ nhất đang làm.)
Vì vậy, hành vi Big-O giống như O (m m n), trong đó m = 300K và n = 1200. Bạn sẽ tính toán chuyển vị, ma trận nhân, phân hủy LU, và sự thay thế về phía sau để có được các hệ số.
Vì vậy, nếu tôi đọc chính xác (và IIRC), tạo A sẽ là O (n * m) ~ = O (m^2) (trong trường hợp của tôi 'n/m = C') và phép nhân sẽ là O (n * n * m) ~ = O (n^3) và nghịch đảo sẽ là O (n^3) Bây giờ chỉ để tìm ra số nguyên không đổi. – BCS
Hồi quy tuyến tính được tính bằng (X'X)^- 1 X'Y.
Nếu X là một (nxk) ma trận:
(X' X) mất O (n * k^2) thời gian và tạo ra một (kxk) ma trận
Ma trận nghịch đảo của một (kxk) ma trận mất O (k^3) thời gian
(X' Y) có O (n * k^2) thời gian và tạo ra một (kxk) ma trận
ma trận nhân thức của hai (k x k) ma trận mất O (k^3) thời gian
Vì vậy, thời gian chạy Big-O là O (k^2 * (n + k)).
Xem thêm: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra
Nếu bạn nhận được ưa thích có vẻ như bạn có thể có được thời gian xuống đến O (k^2 * (n + k^0,376)) với các thuật toán Coppersmith-Winograd.
Thuật toán Coppersmith-Winograd không thực tế có thể sử dụng được, vì hệ số quá lớn nên nó đòi hỏi một ma trận quá lớn để bắt đầu thấy lợi ích của hiệu quả tiệm cận không thực tế: https://en.m.wikipedia.org/wiki/ Coppersmith – Winograd_algorithm – JStrahl
Các hồi quy tuyến tính của mô hình khép kín dạng được tính như sau: phái sinh của
RSS (W) = -2H^t (y-HW)
Vì vậy, chúng tôi giải quyết cho
-2H^t (y-HW) = 0
Sau đó, giá trị W là
W = (H^t H)^- 1 H^2 y
nơi: W: là vector của trọng lượng dự kiến H: là tính năng ma trận N * D trong đó N là số quan sát, và D là số tính năng y: là giá trị thực tế
Sau đó, complexit y của
H^t H là n D^2
Sự phức tạp của các transpose là D^3
Vì vậy, Sự phức tạp của
(H^t H)^-1 is n * D^2 + D^3
Đó không chỉ là sự phức tạp của việc triển khai đó? Có bằng chứng nào cho thấy đó là triển khai nhanh nhất? – BCS
Thuật toán nào? Bình phương nhỏ nhất? –
Có, Hình vuông nhỏ nhất. Tôi không biết có ai khác. – BCS