Nguồn:
Hồi quy tuyến tính là một trong những thuật toán cơ bản cho nhiều lĩnh vực liên quan đến phân tích dữ liệu. Lý do cho điều này là hiển nhiên. Đây là một thuật toán rất đơn giản và dễ hiểu, đã góp phần giúp nó được sử dụng rộng rãi trong hàng chục, nếu không muốn nói là hàng trăm năm. Ý tưởng là chúng ta giả sử sự phụ thuộc tuyến tính của một biến vào một tập hợp các biến khác và sau đó cố gắng khôi phục sự phụ thuộc này.
Nhưng bài viết này không nói về việc sử dụng hồi quy tuyến tính để giải quyết các vấn đề thực tế. Ở đây chúng ta sẽ xem xét các tính năng thú vị của việc triển khai các thuật toán phân tán để phục hồi nó, điều mà chúng ta gặp phải khi viết mô-đun học máy bằng . Một chút toán học cơ bản, học máy và điện toán phân tán có thể giúp bạn tìm ra cách thực hiện hồi quy tuyến tính ngay cả khi dữ liệu của bạn được phân phối trên hàng nghìn nút.
Chúng ta đang nói về điều gì vậy?
Chúng ta đang phải đối mặt với nhiệm vụ khôi phục sự phụ thuộc tuyến tính. Là dữ liệu đầu vào, một tập hợp các vectơ gồm các biến được cho là độc lập được đưa ra, mỗi vectơ được liên kết với một giá trị nhất định của biến phụ thuộc. Dữ liệu này có thể được biểu diễn dưới dạng hai ma trận:
Bây giờ, vì giả định sự phụ thuộc và hơn nữa là tuyến tính, chúng ta sẽ viết giả định của mình dưới dạng tích của các ma trận (để đơn giản hóa việc ghi lại, ở đây và bên dưới giả định rằng số hạng tự do của phương trình được ẩn đằng sau và cột cuối cùng của ma trận chứa đơn vị):
Nghe có vẻ giống một hệ phương trình tuyến tính phải không? Có vẻ như vậy, nhưng rất có thể sẽ không có nghiệm nào cho hệ phương trình như vậy. Lý do cho điều này là do nhiễu, hiện diện trong hầu hết mọi dữ liệu thực. Một lý do khác có thể là do thiếu sự phụ thuộc tuyến tính, có thể khắc phục bằng cách đưa ra các biến bổ sung phụ thuộc phi tuyến vào các biến ban đầu. Hãy xem xét ví dụ sau:
Nguồn:
Đây là một ví dụ đơn giản về hồi quy tuyến tính cho thấy mối quan hệ của một biến (dọc theo trục ) từ một biến khác (dọc theo trục ). Để hệ phương trình tuyến tính tương ứng với ví dụ này có nghiệm thì tất cả các điểm phải nằm chính xác trên cùng một đường thẳng. Nhưng điều đó không đúng. Nhưng chúng không nằm trên cùng một đường thẳng chính xác vì nhiễu (hoặc vì giả định về mối quan hệ tuyến tính là sai). Vì vậy, để khôi phục mối quan hệ tuyến tính từ dữ liệu thực, thông thường cần đưa ra thêm một giả định: dữ liệu đầu vào có chứa nhiễu và nhiễu này có . Bạn có thể đưa ra các giả định về các kiểu phân bố tiếng ồn khác, nhưng trong phần lớn các trường hợp, phân bố chuẩn được xem xét và điều này sẽ được thảo luận thêm.
Phương pháp khả năng tối đa
Vì vậy, chúng tôi giả định sự hiện diện của nhiễu phân bố chuẩn ngẫu nhiên. Phải làm gì trong tình huống như vậy? Đối với trường hợp này trong toán học có và được sử dụng rộng rãi . Tóm lại, bản chất của nó nằm ở sự lựa chọn và sự tối đa hóa tiếp theo của nó.
Chúng tôi quay lại khôi phục mối quan hệ tuyến tính từ dữ liệu có nhiễu bình thường. Lưu ý rằng mối quan hệ tuyến tính giả định là kỳ vọng toán học phân phối chuẩn hiện có. Đồng thời, xác suất mà nhận giá trị này hay giá trị khác, tùy thuộc vào sự hiện diện của các giá trị có thể quan sát được , như sau:
Bây giờ chúng ta hãy thay thế и Các biến chúng ta cần là:
Tất cả những gì còn lại là tìm vectơ , tại đó xác suất này là lớn nhất. Để cực đại hóa một hàm như vậy, trước tiên thuận tiện là lấy logarit của nó (logarit của hàm sẽ đạt cực đại tại cùng điểm với chính hàm đó):
Ngược lại, điều này dẫn đến việc giảm thiểu chức năng sau:
Nhân tiện, đây được gọi là một phương pháp . Thông thường tất cả những cân nhắc ở trên đều bị bỏ qua và phương pháp này chỉ được sử dụng.
Phân tách QR
Điểm tối thiểu của hàm trên có thể được tìm thấy bằng cách tìm điểm tại đó độ dốc của hàm này bằng XNUMX. Và gradient sẽ được viết như sau:
là một phương pháp ma trận để giải bài toán tối thiểu hóa được sử dụng trong phương pháp bình phương tối thiểu. Về vấn đề này, chúng tôi viết lại phương trình ở dạng ma trận:
Vì vậy chúng ta phân tách ma trận đến ma trận и và thực hiện một loạt các phép biến đổi (bản thân thuật toán phân tách QR sẽ không được xem xét ở đây mà chỉ sử dụng nó liên quan đến nhiệm vụ hiện tại):
Ma trận là trực giao. Điều này cho phép chúng ta thoát khỏi công việc :
Và nếu bạn thay thế trên , sau đó nó sẽ hoạt động . Xem xét rằng là ma trận tam giác trên, nó có dạng như sau:
Điều này có thể được giải quyết bằng phương pháp thay thế. Yếu tố nằm ở vị trí như , phần tử trước nằm ở vị trí như và như vậy.
Điều đáng chú ý ở đây là độ phức tạp của thuật toán kết quả do sử dụng phân tách QR bằng . Hơn nữa, mặc dù thực tế là phép toán nhân ma trận được song song hóa tốt nhưng không thể viết được một phiên bản phân tán hiệu quả của thuật toán này.
Xuống dốc
Khi nói về việc giảm thiểu một hàm, điều đáng ghi nhớ là phương pháp giảm độ dốc (ngẫu nhiên). Đây là một phương pháp giảm thiểu đơn giản và hiệu quả dựa trên việc tính toán lặp lại độ dốc của hàm tại một điểm và sau đó dịch chuyển nó theo hướng ngược lại với độ dốc. Mỗi bước như vậy sẽ đưa giải pháp đến gần hơn với mức tối thiểu. Độ dốc vẫn trông giống nhau:
Phương pháp này cũng có khả năng song song và phân bố tốt do tính chất tuyến tính của toán tử gradient. Lưu ý rằng trong công thức trên, dưới dấu tổng có các số hạng độc lập. Nói cách khác, chúng ta có thể tính toán độ dốc một cách độc lập cho tất cả các chỉ số từ đầu tiên đến , song song với việc này, hãy tính độ dốc cho các chỉ số với để . Sau đó thêm các gradient kết quả. Kết quả của phép cộng sẽ giống như khi chúng ta tính ngay gradient cho các chỉ số từ đầu tiên đến . Do đó, nếu dữ liệu được phân phối giữa nhiều phần dữ liệu, độ dốc có thể được tính toán độc lập trên từng phần và sau đó kết quả của các phép tính này có thể được tổng hợp để thu được kết quả cuối cùng:
Từ quan điểm thực hiện, điều này phù hợp với mô hình . Ở mỗi bước giảm độ dốc, một tác vụ được gửi đến từng nút dữ liệu để tính toán độ dốc, sau đó các độ dốc được tính toán sẽ được thu thập cùng nhau và kết quả tổng của chúng sẽ được sử dụng để cải thiện kết quả.
Mặc dù dễ triển khai và khả năng thực thi trong mô hình MapReduce, việc giảm độ dốc cũng có những hạn chế. Đặc biệt, số bước cần thiết để đạt được sự hội tụ cao hơn đáng kể so với các phương pháp chuyên biệt khác.
LSQR
là một phương pháp khác để giải bài toán, phù hợp cho cả việc khôi phục hồi quy tuyến tính và giải hệ phương trình tuyến tính. Đặc điểm chính của nó là kết hợp các ưu điểm của phương pháp ma trận và cách tiếp cận lặp lại. Việc triển khai phương pháp này có thể được tìm thấy trong cả hai thư viện và trong . Mô tả về phương pháp này sẽ không được đưa ra ở đây (có thể tìm thấy trong bài viết ). Thay vào đó, một cách tiếp cận sẽ được chứng minh để điều chỉnh LSQR để thực thi trong môi trường phân tán.
Phương pháp LSQR dựa trên . Đây là một quy trình lặp, mỗi lần lặp bao gồm các bước sau:
Nhưng nếu chúng ta giả sử rằng ma trận được phân vùng theo chiều ngang, sau đó mỗi lần lặp có thể được biểu diễn dưới dạng hai bước MapReduce. Bằng cách này, có thể giảm thiểu việc truyền dữ liệu trong mỗi lần lặp (chỉ các vectơ có độ dài bằng số ẩn số):
Cách tiếp cận này được sử dụng khi thực hiện hồi quy tuyến tính trong .
Kết luận
Có nhiều thuật toán phục hồi hồi quy tuyến tính, nhưng không phải tất cả chúng đều có thể áp dụng được trong mọi điều kiện. Vì vậy, việc phân tách QR là giải pháp tuyệt vời cho giải pháp chính xác trên các tập dữ liệu nhỏ. Việc giảm độ dốc rất đơn giản để thực hiện và cho phép bạn nhanh chóng tìm ra giải pháp gần đúng. Và LSQR kết hợp các thuộc tính tốt nhất của hai thuật toán trước, vì nó có thể được phân phối, hội tụ nhanh hơn so với giảm độ dốc và cũng cho phép dừng sớm thuật toán, không giống như phân tách QR, để tìm giải pháp gần đúng.
Nguồn: www.habr.com