Chương 1 Kiến thức chuẩn bị. Trước khi đi vào tìm hiểu nội dung chính của luận văn, một trong những nội dung đóng vai trò quan trọng trong hầu hết các chủ đề của thống kê, máy học và nhiều ngành khoa học dữ liệu khác là tìm nghiệm tối ưu bằng phương pháp xấp xỉ nghiệm. Có rất nhiều phương pháp để tìm nghiệm tối ưu, một trong những phương pháp được lựa chọn và sử dụng rộng rãi là phương pháp xấp xỉ số Gradient Descent (kí hiệu GD). Gradient Descent được trình bày rõ trong nhiều tài liệu ([8],[24],.) và một vài điểm nổi bật của GD được trình bày dưới đây.1 Tổng quát về Gradient Descent.
Gradient Descent được nhắc tới như một thuật toán tối ưu hóa bậc nhất được sử dụng phổ biến, trong đó • Gradient của hàm số f là đạo hàm cấp một tương ứng với mỗi biến của dY f , hay Gradient là , dX (Ở đây, Y := f (Xi ; θ) là hàm số cần được tối ưu hóa với tham số θ), • Descent là sự giảm xuống, ở đây ám chỉ việc giảm dần giá trị của hàm mục tiêu f thông qua việc cập nhật lại tham số θ. 3 Toán ứng dụng Luận văn Thạc sĩ GD về cơ bản là việc thực hiện điều chỉnh tham số θ để tối ưu hóa hàm f. GD bắt đầu bằng một θ khởi tạo ngẫu nhiên, sau đó thực hiện lặp lại các bước dưới đây cho tới khi f hội tụ như sau: 1. Tính Gradient của f với tham số θi : ∇θ f (θi ); 2.
Thực hiện cập nhật tham số thứ i + 1 theo công thức: θi+1 = θi − η∇θ f (θi ), trong đó: θi+1 là tham số ước lượng lần thứ i + 1; θi là tham số ước lượng lần thứ i; ∇θ f (θi ) là Gradient của hàm muc tiêu f với tham số θi ; η là learning rate (tốc độ học); Dấu "−" ở đây thể hiện giảm dần, hướng đi luôn trái dấu với Gradient. Vấn đề f hội tụ ta sẽ thảo luận ở phần 1.2 Các biến thể của Gradient Descent (GD Variants). Dựa vào một số tính chất, ta có thể chia GD thành 3 biến thể: Batch gradient descent, stochastic gradient descent, và mini-batch gradient descent. Batch gradient descent -BGD Batch gradient descent (hay còn gọi là vanilla GD) nói đơn giản là việc ta tính Gradient của hàm f trên toàn bộ các điểm dữ liệu để thực hiện một lần cập nhật θ: θi+1 = θi − η∇θ f (θi ).
Mỗi lần cập nhật như vậy được gọi là một "epoch". Một số ưu điểm của BGD như: tính hội tụ tốt, độ ổn định và độ chính xác cao đối với dữ liệu nhỏ. Hoàng Thị Hà 4 Toán ứng dụng Luận văn Thạc sĩ Bên cạnh đó, các khó khăn xuất hiện như việc tính gradient dựa trên toàn bộ dữ liệu nên tốn nhiều thời gian và tài nguyên tính toán. Do đó BGD dường như không phù hợp với dữ liệu có kích thước lớn, đặc biệt là dữ liệu trực tuyến; dễ rơi vào điểm tối ưu cục bộ.
Stochastic gradient descent - SGD. Với mục tiêu khắc phục khó khăn ở BGD, Stochastic gradient descent thực hiện tính Gradient dựa trên một điểm được chọn một cách ngẫu nhiên (thay vì tính gradient với toàn bộ dữ liệu như ở BGD) θi+1 = θi − η∇θ f (θi ; x(i) , y (i) ). Một "epoch" trong SGD tương ứng với n lần cập nhật (n là số quan sát trong dữ liệu). Trong thực tế thì SGD chỉ yêu cầu số lượng "epoch" rất nhỏ.
Một số ưu điểm của SGD như: việc tính gradient dựa trên một điểm dữ liệu dẫn tới khả năng tính toán nhanh chóng, tiết kiệm tài nguyên và bộ nhớ tính toán. SGD tỏ ra tiện lợi cho các dữ liệu lớn, đặt biệt các dữ liệu được cập nhật liên tục và có tốc độ hội tụ về điểm tối ưu rất nhanh. Hơn nữa, SGD có khả năng vượt qua các điểm tối ưu cục bộ. Bên cạnh ưu điểm, một số nhược điểm của SGD được biết tới như: tính không ổn định và việc khó khăn trong lựa chọn tốc độ học (learning rate) do các điểm tính được chọn một cách ngẫu nhiên.
Mini-batch gradient descent - Mini-batch GD. Tương tự SGD, Mini-batch gradient descent bắt đầu với dữ liệu ngẫu nhiên. Bằng việc chia dữ liệu thành các mini-batch nhỏ, mỗi mini-batch có p quan sát (mini-batch cuối là phần dư của n/p), mỗi lần cập nhật ở đây sử dụng một mini-batch: θi+1 = θi − η∇θ f (θi ; x(i:i+n) , y (i:i+n) ). Hoàng Thị Hà 5 Toán ứng dụng Luận văn Thạc sĩ Mini-batch GD là một kỹ thuật được ưu tiên trong phân tích.
Mỗi mini-batch thường không có tiêu chuẩn cố định nhưng nhìn chung thường nằm trong khoảng 50-256 quan sát. Mini-batch GD có nhiều ưu điểm của cả SGD và BGD như: tính tốc độ hội tụ nhanh, ổn định cũng như việc tối ưu được hiệu suất tính toán. Tuy nhiên, mini-batch GD mang tới khó khăn trong việc chọn kích thước mini-batch.3 Một số vấn đề trong Gradient descent. Tốc độ học là một tham số quan trọng trong GD, nó cho biết tốc độ di chuyển tới điểm tối ưu.
Tốc độ học lớn dẫn tới mỗi “bước nhảy” sẽ lớn, khi đó có thể dẫn tới việc nhảy qua lại giữa điểm tối ưu hoặc thậm chí không thể hội tụ (xem hình 1. Tốc độ học quá nhỏ dẫn tới việc cần rất nhiều thời gian, công sức để đạt tới điểm tối ưu, hay rất nhiều "bước nhảy" để hội tụ về nghiệm tối ưu (xem hình 1. Do đó, việc chọn tốc độ học phù hợp là rất quan trọng. Một tốc độ học Hình 1.1: Hình ảnh minh họa cho tốc độ học.
Hoàng Thị Hà 6 Toán ứng dụng Luận văn Thạc sĩ tốt thường được chọn thông qua thực nghiệm hoặc kinh nghiệm của người thực hiện. Điều kiện dừng (Stopping criteria). Gradient descent là thuật toán lặp, do đó việc xác định khi nào thuật toán cần kết thúc và cho ra kết quả rất quan trọng. Một số phương pháp xác định điều kiện dừng của thuật toán là: • Giới hạn số vòng lặp: Đây là một phương pháp đơn giản để kiểm soát số lượng vòng lặp, tuy nhiên, nhược điểm của nó là có thể sẽ dừng khi chưa gần tới điểm hội tụ.
• Xét sự thay đổi của gradient: Đo lường sự thay đổi của gradient tại hai lần cập nhật liên tiếp, nếu nó nhỏ hơn một ngưỡng nhất định (thường được xác định dựa vào người sử dụng thuật toán) thì thuật toán có thể dừng lại. • Xét sự thay đổi của hàm mục tiêu: Đo sự thay đổi của hàm số sau mỗi vòng lặp, nếu sự thay đổi nhỏ hơn một ngưỡng nhất định (thường là ngưỡng sai số) thì ta kết luận thuật toán hội tụ và kết thúc. Tuy nhiên, sự thay đổi nhỏ của hàm mục tiêu có thể do tồn tại các điểm yên ngựa hoặc cực tiểu địa phương. Điểm cực tiểu địa phương, điểm yên ngựa (Local minima, Saddle points).2: Hình ảnh minh họa cho điểm cực tiểu địa phương và điểm yên ngựa.
Hoàng Thị Hà 7 Toán ứng dụng Luận văn Thạc sĩ Có thể dễ dàng tìm thấy cực tiểu toàn cục đối với bài toán lồi, tuy nhiên trong bài toán không lồi, việc tìm cực tiểu toàn cục đôi khi rất khó do việc xuất hiện của cực tiểu địa phương (tương tự cho điểm yên ngựa, hình 1. Tại điểm cực tiểu địa phương và điểm yên ngựa, gradient của hàm mục tiêu bằng 0, điều này có thể dẫn tới việc GD bị dừng lại với mục tiêu không mong muốn (không phải cực trị toàn cục). Trong trường hợp này, một số biến thể của GD có thể áp dụng để khắc phục vượt qua các điểm đặc biệt này như: Momentum, SGD, Hybrid Approaches,.4 Các thuật toán Gradient descent. Có nhiều thuật toán Gradient descent được cải tiến với mục đích khắc phục nhiều vấn đề của GD như: Momentum, Nesterov accelerated gradient, Ada- grad,.2 Hồi quy tuyến tính.
Các phương pháp phân tích hồi quy nói chung là một chủ đề cơ bản trong phân tích dữ liệu và được trình bày rõ ràng ([18], [10], [31],. Hồi quy tuyến tính được xem là một phương pháp phân tích hồi quy cơ bản nhất và thường được mô tả một cách chi tiết và rõ ràng([28], [1], [3]). Hồi quy tuyến tính được sử dụng trong nhiều lĩnh vực như kinh tế học, tài chính, y khoa,. nhằm thực hiện các nhiệm vụ cụ thể như: dự báo doanh số, giá cổ phiếu, phân tích mối quan hệ giữa các yếu tố rủi ro khác nhau, phân tích tỷ lệ mắc bệnh, phân tích tác động của biến đổi khí hậu với tự nhiên,.
Trong chương này, chúng tôi sẽ trình bày lại phương pháp hồi quy tuyến tính một cách ngắn gọn, dễ hiểu và đầy đủ nhất có thể. Hoàng Thị Hà 8 Toán ứng dụng Luận văn Thạc sĩ 1.1 Khái niệm hồi quy tuyến tính. Phân tích hồi quy là việc nghiên cứu về mối quan hệ giữa một hay nhiều biến độc lập X (hay biến giải thích (explanatory)) và biến phụ thuộc Y. Phân tích hồi quy tuyến tính là một phương pháp hồi quy được xác định dưới dạng hàm số tuyến tính (đường thẳng hoặc các siêu phẳng).
Phân tích hồi quy tuyến tính là một công cụ thống kê phổ biến nhằm mô hình hóa mối quan hệ tuyến tính giữa biến phụ thuộc Y (Y là biến phụ thuộc nhận giá trị liên tục, thực) và một hay một số biến độc lập X1 , X2 ,. Mô hình hồi quy tuyến tính có dạng Y = β0 + β1 X1 + β2 X2 +. + βk Xk + , trong đó là sai số ngẫu nhiên (random error), β0 được gọi là hệ số chặn (intercept), βi là các hệ số hồi quy, nó cho biết mức độ ảnh hưởng của biến Xi tới giá trị Y .2 Mô hình hồi quy tuyến tính đơn. Hình thành mô hình hồi quy tuyến tính đơn.
Xét tập dữ liệu giả định (X,Y), với X là biến độc lập; Y là biến phụ thuộc. Ta giả định rằng giá trị kỳ vọng của biến phụ thuộc Y có liên quan tới biến X theo một đường thẳng với hệ số chặn β0 và hệ số góc β1. Khi đó, kỳ vọng của biến Y khi biết giá trị X được xác định bởi công thức E(Y |X) = β0 + β1 X ≈ Ŷ. Ở đây Ŷ là ước lượng của kỳ vọng E(Y |X), Ŷ còn được xem là giá trị dự đoán của Y.
Trong thực tế, các điểm dữ liệu không nhất thiết phải đi qua mô hình tuyến Hoàng Thị Hà 9 Toán ứng dụng Luận văn Thạc sĩ tính.