Tài liệu Xấp xỉ ngẫu nhiên và vài ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- NGÔ THỊ TOÁN XẤP XỈ NGẪU NHIÊN VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- NGÔ THỊ TOÁN XẤP XỈ NGẪU NHIÊN VÀ MỘT SỐ ỨNG DỤNG Chuyên ngành: Lý thuyết xác suất và thống kê toán học Mã số: 60 46 15 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN HỮU TIẾN Hà Nội – Năm 2011 Mục lục Lời nói đầu 1 Lời cảm ơn 3 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều 6 1.1. Khái niệm mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2. Xấp xỉ ngẫu nhiên cho trường hợp một chiều . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1. Thuật toán Robbins-Monro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2. Thuật toán Kiefer-Wolfowitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.3. Thuật toán Dvozetky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Chương 2. Xấp xỉ ngẫu nhiên cho trường hợp nhiều chiều 21 2.1. Thuật toán Robbins-Monro trong không gian n-chiều . . . . . . . . . . . . . . . 21 2.1.1. Nội dung thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2. Đánh giá cận trên của sai số trung bình bình phương . . . . . . . . . . . . 22 2.2. Thuật toán Dvozetky trong không gian n-chiều . . . . . . . . . . . . . . . . . . . . . 28 Chương 3. Một số ứng dụng của xấp xỉ ngẫu nhiên 30 3.1. Ứng dụng của xấp xỉ ngẫu nhiên trong ước lượng có định hướng quyết định . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2. Ứng dụng của xấp xỉ ngẫu nhiên vào ước lượng tham số . . . . . . . . . . . . . 34 3.3. Ứng dụng của xấp xỉ ngẫu nhiên vào ước lượng hàm phân biệt . . . . . . . 37 3.4. Ứng dụng của xấp xỉ ngẫu nhiên trong các hàm thế . . . . . . . . . . . . . . . . . 41 4 3.5. Ứng dụng của xấp xỉ ngẫu nhiên trong ước lượng hàm mật độ xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5.1. Xấp xỉ tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5.2. Ước lượng và xấp xỉ cho hàm mật độ trộn chuẩn . . . . . . . . . . . . . . . . 45 Kết luận 49 Tài liệu tham khảo 50 5 Chương 1 Xấp xỉ ngẫu nhiên cho trường hợp một chiều 1.1 Khái niệm mở đầu Giả sử µ(x) là một hàm số có nghiệm duy nhất là x = θ nhưng dạng giải tích của hàm số này chưa biết. Tuy nhiên với mỗi giá trị x, giả sử tồn tại một biến ngẫu nhiên ξ (x) có hàm mật độ xác suất f (ξ |x) sao cho: Z µ(x) = Eξ [ξ (x)] = ξ (x) f (ξ |x)dξ (1.1) Ωξ hay µ(x) được biểu diễn dưới dạng kì vọng có điều kiện của biến ngẫu nhiên ξ khi giả thiết x cho trước. Hàm µ(x) như thế được gọi là hàm hồi quy. Việc tìm nghiệm hoặc tìm giá trị lớn nhất, nhỏ nhất của hàm hồi quy khi dạng giải tích của hàm này chưa biết sẽ là đối tượng nghiên cứu của phương pháp xấp xỉ ngẫu nhiên. Trong luận văn ta sẽ sử dụng kí hiệu x; x1 ; x2 ; . . . cho các tham biến, ω;t cho các yếu tố ngẫu nhiên đã được quan sát và ξ cho ước lượng không chệch của µ(x) hay Eξ = µ(x). Để đơn giản ta quy ước sẽ sử dụng ξ thay cho ξ (x, ω) và ξn thay cho ξ (xn , ω) ... 6 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều 1.2 Xấp xỉ ngẫu nhiên cho trường hợp một chiều 1.2.1 Thuật toán Robbins - Monro Trong mục này chúng ta sẽ giải quyết bài toán tìm nghiệm của một phương trình hàm hồi quy cho trường hợp một chiều. Không mất tính tổng quát ta có thể giả thiết là chỉ cần tìm thuật toán xác định nghiệm của phương trình sau: µ(x) = 0 (1.2) Thật vậy, nếu phải tìm nghiệm của phương trình dạng b (x) = α µ (1.3) trong đó α là một hằng số thực cho trước. b (x) − α thì lời giải cho bài toán (1.3) sẽ có thể xác định Khi đó, ta đặt µ(x) := µ từ thuật toán giải bài toán (1.2). Bây giờ ta xét việc giải phương trình hồi quy (1.2) và có nhận xét là nếu hàm hồi quy µ(x) đã cho trước thì nghiệm của phương trình (1.2) sẽ được xác định bởi các thuật toán đã xét ở giải tích số chẳng hạn bởi phương pháp lặp Newton. Vấn đề đặt ra ở đây là hàm hồi quy µ(x) chưa biết nên để tìm nghiệm của phương trình hồi quy (1.2), ta cần giả thiết thêm là ứng với mỗi giá trị xác định x = xn ta thu được một quan sát không chệch cho µ(xn ) là ξn với ∀n ∈ N. Khi đó, thuật toán tìm nghiệm xấp xỉ cho phương trình hồi quy (1.2) được Robbins - Monro đề xuất sẽ có dạng sau: xn+1 = xn − an ξn (1.4) trong đó {an } là một dãy số thực được chọn trước thích hợp và dãy đó được gọi là dãy số hiệu chỉnh. Kết quả sau đây xác định các điều kiện đủ để thuật toán Robbins - Monro xác định ở (1.4) hội tụ. Định lý 1.2.1. Giả sử các điều kiện sau thỏa mãn: • x1 là một biến ngẫu nhiên tùy ý sao cho E[x12 ] < ∞ và dãy biến ngẫu nhiên x1 ; x2 ; . . . ; xn ; . . . là các biến ngẫu nhiên độc lập cùng phân phối được xác định từ thuật toán Robbins - Monro (1.4) trong đó ξn là quan sát không chệch về hàm hồi quy µ(x) tại x = xn hay E(ξn ) = µ(xn ). • {an } là một dãy số hiệu chỉnh được chọn trước sao cho ∞ ∞ ∑ an = ∞; ∑ a2n < ∞ n=1 n=1 7 (1.5) Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều • Tồn tại các hằng số dương 0 < M1 ≤ M2 < ∞ sao cho hàm hồi quy µ(x) thỏa mãn M1 (x − θ )2 ≤ µ(x)(x − θ ) ≤ M2 (x − θ )2 (1.6) và Z Var[ξ ] = [ξ − µ(x)]2 f (ξ |x)dξ ≤ α 2 < ∞ (1.7) Ωξ Khi đó thuật toán Robbins - Monro (1.4) sẽ hội tụ theo trung bình bình phương về nghiệm θ của phương trình hồi quy (1.2) hay lim E|xn − θ |2 = 0 n→∞ Trước khi chứng minh định lý, ta có một số các nhận xét sau đây về các giả thiết hội tụ của định lý: Nhận xét 1. Ta cần chú ý như sau: • Giả thiết (1.6) cho ta biết hàm µ(x) phải nằm giữa hai đường thẳng có hệ số góc dương là M1 và M2 tương ứng. Hai đường thẳng này cắt nhau tại x = θ và điều này đảm bảo cho sự tồn tại nghiệm θ của phương trình (1.2). • Giả thiết (1.7) có nghĩa là quan sát không chệch của hàm hồi quy có phương sai hữu hạn. • Giả thiết (1.5) về dãy hiệu chỉnh {an } được hiểu như sau: do tính ngẫu nhiên của các quan sát ξn nên hệ số hiệu chỉnh an phải tiến đến 0 khi n tiến ra vô cùng nếu không thì thuật toán sẽ giao động quanh θ và không bao giờ hội tụ về giá trị θ này. Mặt khác sự hội tụ về 0 của an cần duy trì ở mức không quá nhanh nhằm loại trừ khả năng giá trị xấp xỉ xn quẩn quanh nghiệm θ chứ không tiến dần về nghiệm này. Thật vậy, do thuật toán (1.4) sử dụng ước lượng không chệch của hàm hồi quy là ξn thay cho giá trị đúng của nó là µ(xn ) nên thuật toán (1.4) cần đảm bảo rằng quan sát ξn được sử dụng nhiều lần để ảnh hưởng của nó loại trừ khả năng trên và điều này sẽ được bảo đảm nếu dãy hiệu chỉnh {an } hội tụ về 0 không quá nhanh. Giả thiết (1.5) chính là nhằm bảo đảm cho hai điều kiện trên thỏa mãn. • Việc định nghĩa hàm hồi quy như (1.1) đã nói lên rằng các hàm mật độ f (ξn |xn ) có cấu trúc hàm giống nhau cho tất cả các n vì vậy, giả thiết về tính độc lập cùng phân phối của các x1 ; x2 ; . . . ; xn ; . . . sẽ bảo đảm cho điều kiện nêu trên thỏa mãn. • Cuối cùng, ta lưu ý rằng giả thiết độc lập cùng phân phối nêu trên có thể được giảm nhẹ nếu ta thay giả thiết này bởi giả thiết về sự phụ thuộc yếu của các quan sát ξn vào x1 ; . . . ; xn hay có thể giả thiết ξn có phân phối xác 8 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều suất có điều kiện chỉ phụ thuộc vào kết quả xấp xỉ thứ n là xn chứ không phụ thuộc trực tiếp vào kết quả xấp xỉ x1 ; . . . ; xn−1 trước đó. Tuy nhiên, để các chứng minh được dễ hiểu hơn, chúng ta vẫn dùng các giả thiết về sự độc lập cùng phân phối của các biến ngẫu nhiên x1 ; . . . ; xn ; . . . Bây giờ ta bắt đầu chứng minh định lý 1.2.1. Chứng minh. Từ (1.4) ta có: [xn+1 − θ ]2 = [xn − θ ]2 − 2an ξn (xn − θ ) + a2n ξn2 (1.8)  2 Đặt Vn := E xn − θ thì Vn gọi là sai số trung bình bình phương của xấp xỉ xn cho θ Lấy kỳ vọng hai vế của (1.8) ta được     Vn+1 = Vn − 2an E ξn (xn − θ ) + a2n E ξn2 (1.9) Theo tính chất kỳ vọng có điều kiện và các giả thiết độc lập, giả thiết (1.6); (1.7) ta có:     E ξn .(xn − θ ) = E µ(xn ).(xn − θ )   ≥ E M1 (xn − θ )2 = M1Vn     E ξn2 = E µ 2 (xn ) +Varξn   ≤ E M22 (xn − θ )2 + α 2 = M22Vn + α 2 Khi đó, (1.9) trở thành: Vn+1 ≤ (1 − 2M1 an + M22 a2n )Vn + a2n α 2 (1.10) Theo nhận xét trên thì an −→ 0 khi n −→ ∞ nên với ε bất kỳ, 0 ≤ ε < 2 sẽ tồn tại một số m = m(ε) sao cho với mọi n ≥ m ta có:
  1 − 2M1 an + M22 a2n ≤ 1 − (2 − ε)M1 an   0 < 1 − (2 − ε)M1 an ≤ 1 9 (1.11) Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều Khi đó bất đẳng thức (1.10) trở thành:   Vn+1 ≤ Vn 1 − (2 − ε)M1 an + a2n α 2 , ∀n ≥ m (1.12) Ta có thể biểu diễn (1.12) một cách truy hồi như sau:   Vm+1 ≤ Vm 1 − (2 − ε)M1 am + a2m α 2   Vm+2 ≤ Vm+1 1 − (2 − ε)M1 am+1 + a2m+1 α 2    ≤ Vm 1 − (2 − ε)M1 am 1 − (2 − ε)M1 am+1 
 + α 2 a2m 1 − (2 − ε)M1 am+1 + a2m+1 ... và Vn+1 ≤ Vm βm−1,n + α 2 n ∑ a2i βin; n≥m (1.13) i=m trong đó βin được định nghĩa như sau:     ∏nj=i+1 [1 − (2 − ε)M1 a j ] nếu 0 ≤ i < n    βin = 1 nếu i = n      0 nếu i > n. Áp dụng bất đẳng thức logarit ln u ≤ u − 1, u≥0 ta có: ln[1 − (2 − ε)M1 ai ] ≤ −(2 − ε)M1 ai , i≥m Do ∑∞ i=1 ai phân kỳ nên lim βm−1,n = 0 và do đó n→∞ lim Vm βm−1,n = 0 n→∞ Lại có, βin = 0 khi i > m nên α2 n ∑ a2i βin = α 2 i=m 10 ∞ ∑ a2i βin i=m (1.14) Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều 2 Do 0 ≤ βin ≤ 1; ∀n; i và ∑∞ i=1 ai hội tụ tuyệt đối nên ta có thể chuyển qua giới hạn vào tổng. Kết hợp với (1.14) ta thu được: lim α n→∞ 2 n ∑ a2i βin = lim α 2 n→∞ i=m = α2 ∞ ∑ a2i βin i=m ∞ lim βin ∑ a2i n→∞ (1.15) i=m =0 Từ (1.13); (1.14); (1.15) ta có  2 lim Vn+1 = lim E xn+1 − θ = 0 n→∞ n→∞ Vậy thuật toán (1.4) hội tụ theo nghĩa trung bình bình phương. Định lý 1.2.1 được chứng minh xong. Chú ý: Với các bài toán có hàm hồi quy không thỏa mãn điều kiện (1.6) với mọi giá trị của x nhưng ta lại biết giá trị chân thực θ nằm trong một khoảng [u1 ; u2 ] nào đó và (1.5) thỏa mãn với mọi x ∈ [u1 ; u2 ] thì ta sẽ sử dụng thuật toán Robbins - Monro chặt cụt có dạng sau: xn+1 = truncu1 ;u2 [xn − an ξn ] trong đó     u1    truncu1 ;u2 (u) = u      u2 nếu u < u1 nếu u1 ≤ u ≤ u2 nếu u > u2 . và hàm này được gọi là hàm chặt cụt. Thuật toán Robbins - Monro chặt cụt sẽ hội tụ nếu các điều kiện còn lại của định lý 1.2.1 thỏa mãn. Ta lưu ý là sai số trung bình bình phương Vn = E[xn − θ ]2 trong mỗi bước của thuật toán rất khó thu được vì thuật toán là một quá trình truy hồi, chẳng hạn x2 phụ thuộc vào phân phối của x1 ; x3 lại phụ thuộc vào phân phối của x2 . . . . Cũng bởi vậy nên sai số trung bình bình phương chỉ phù hợp cho mỗi cách chọn dãy hiệu chỉnh an cụ thể. Dưới đây là một cận trên sai số trung bình bình phương do Dvoretzky đưa ra. Định lý 1.2.2. Giả sử tồn tại các số dương M1 ; M2 ; α 2 và V1 sao cho các điều kiện (1.6); (1.7) trong định lý 1.2.1 và điều kiện sau thỏa mãn:   E ξn − µ(xn )|x1 , . . . , xn = 0 (1.16) 11 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều 2α 2 E[x1 − θ ] = V1 ≤ M1 (M2 − M1 ) 2 (1.17) Khi đó, tồn tại dãy hiệu chỉnh {an } xác định bởi: an = M1V1 α 2 + nM12V1 (1.18) để sai số trung bình bình phương của thuật toán Robbins - Monro thỏa mãn: Vn = E[xn − θ ]2 ≤ Chứng minh. Ta có: V1 ≤ ⇒ α2 ≥ V1 M1 (M2 − M1 ) 2 α 2V1 α 2 + (n − 1)M12V1 (1.19) 2α 2 M1 (M2 − M1 ) M1V1 2V1 M1 ≤ α 2 + nM12V1 V1 M1 (M2 − M1 ) + 2nM12V1 2M1 = M1 (M2 − M1 ) + 2nM12 2 ≤ M2 + M1 Vì vậy có 0 ≤ an M1 ≤ 1 Lại có: xn+1 − θ = xn − θ − an µ(xn ) + an [µ(xn ) − ξn ] Tương tự như trong chứng minh định lý 1.2.1 và từ các điều kiện (1.6), (1.7) và (1.16) ta có: ⇒ an =  2 Vn+1 ≤ E xn − θ − an µ(xn ) + a2nVarξn Vn + a2n α 2 2 ≤ (1 − an M1 ) Ta sẽ chứng minh (1.19) bằng quy nạp.
Thật vậy: Với n = 1 thì V1 ≤ V1 (1.19) luôn đúng . Giả sử (1.19) đúng với n, ta sẽ chứng minh đúng với n + 1 12 (1.20) Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều Từ (1.20) và giả thiết quy nạp, ta có: Vn+1 ≤ (1 − an M1 )2Vn + a2n α 2 α 2V1 + a2n α 2 2 2 α + (n − 1)M1 V1 M12V1 M12V12 α 2 α 2V1 2 = (1 − 2 ) . + α + nM12V1 α 2 + (n − 1)M12V1 (α 2 + nM12V1 )2 α 2V1 = 2 α + nM12V1 ≤ (1 − an M1 )2 . ⇒ (1.19) đúng với n + 1. Vậy định lý được chứng minh xong. Nhận xét 2. Công thức (1.19) cho thấy tốc độ hội tụ của thuật toán Robbins Monro xét theo tiêu chuẩn sai số trung bình bình phương phụ thuộc vào cách chọn dãy hiệu chỉnh{an }. Dãy {an } chọn trong định lý 1.2.2 là cách chọn gần tối ưu với những n nhỏ. Tuy nhiên, ta lại quan tâm đến sự hội tụ của thuật toán khi n d rất lớn. Do đó ta có cách chọn dãy {an } như sau: Đặt M = M(θ ) = µ(x)|x=θ dx và M ≥ M1 • Nếu hàm hồi quy là tuyến tính thì ta chọn an = Vn = α2 nM 2 1 và với n đủ lớn thì nM • Nếu hàm hồi quy không tuyến tính thì do ta chỉ quan tâm sự tiệm cận của xấp xỉ đến nghiệm θ nên dãy số hiệu chỉnh {an } sẽ được chọn ở dạng 1 α2 an = và khi đó ta có lim nVn = 2 n→∞ nM M • Với một hàm hồi quy bất kỳ nhưng có các điều kiện của định lý 1.2.1 thỏa a mãn và Varξ (x) = α 2 thì ta chọn dãy hiệu chỉnh thỏa mãn an = với n xn − θ 2aM > 1. Khi đó, biến ngẫu nhiên √ có phân phối sẽ tiệm cận đến n phân phối chuẩn với kỳ vọng bằng 0 và phương sai thỏa mãn nE(xn − θ )2 = α 2 a2 2aM − 1 13 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều 1.2.2 Thuật toán Kiefer - Wolfowitz Bây giờ ta sẽ nghiên cứu việc tìm lời giải cho bài toán: Tìm giá trị của θ sao cho tại x = θ hàm hồi quy µ(x) đạt cực đại hoặc cực tiểu. Không mất tính tổng quát, chúng ta sẽ chỉ đi tìm điểm cực tiểu θ của µ(x), khi đó từ các kết quả của giải tích ta suy ra θ phải là nghiệm của phương trình µ 0 (x) = 0. Ta có thể giải bài toán trên bằng cách sử dụng thuật toán Robbins - Monro để tìm nghiệm của phương trình µ 0 (x) = 0. Thật vậy, thuật toán để tìm điểm x = θ ∂ξ mà tại đó µ 0 (x) = 0 khi giả thiết hàm µ 0 (x) chưa biết nhưng giả thiết tồn tại ∂x tại mỗi x = xn theo Robbins - Monro có dạng sau: xn+1 = xn − an ∂ ξn |x=xn ∂x Tuy nhiên, thuật toán Robbins - Moro không thể áp dụng được trong việc giải bài toán tìm cực tiểu này. Sở dĩ như vậy vì: • Hàm µ(x) chưa chắc đã khả vi. Hơn nữa biến ngẫu nhiên (∂ ξ /∂ x) có thể không thỏa mãn điều kiện sau: µ 0 (x) = ∂ ξ  ∂ Eξ = E ∂x ∂x • Mặc dù chúng ta sẽ dễ dàng thu được ξ (x) từ các quan sát ứng với giá trị ∂ξ của x nhưng sẽ không tính toán được giá trị của . ∂x Để vẫn tìm được lời giải xấp xỉ cho bài toán trên Kiefer - Wolfowitz giả thiết là tại mỗi giá trị x = xn có thể thu được một quan sát không chệch cho giá trị µ 0 (x) từ các quan sát về hàm hồi quy µ(x) ở dạng sau: ξ (xn + bn ) − ξ (xn − bn ) 2bn trong đó {bn } là dãy số dương có giới hạn tiến tới 0 (khi n → ∞). Từ đó theo ý tưởng của thuật toán xấp xỉ ngẫu nhiên Robbins - Monro, Kiefer - Wolfowitz đã đề xuất thuật toán tìm giá trị xấp xỉ của x = θ mà tại đó hàm hồi quy µ(x) có đạo hàm µ 0 (x) = 0 như sau: Nếu ở bước lặp thứ n ta có giá trị xấp xỉ là x = xn và giả sử có được hai quan sát không chệch về hàm hồi quy µ(x) tại x = xn − bn và x = xn + bn thì giá trị xấp xỉ của x = θ tại bước lặp thứ n + 1 là x = xn+1 sẽ được xác định bởi thuật toán sau:  an  xn+1 = xn − ξ (xn + bn ) − ξ (xn − bn ) (1.21) bn 14 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều trong đó {an } và {bn } là các dãy các số dương và rõ ràng số hạng ξ (xn + bn ) − ξ (xn − bn ) có thể coi như là một ước lượng của ξn0 tại x = xn . Thuật 2bn toán (1.21) được gọi là thuật toán Kiefer - Wolfowitz và sự hội tụ của dãy các xấp xỉ x = xn về x = θ đã được Kiefer - Wolfowitz chứng minh trong định lý sau: Định lý 1.2.3. Giả sử các dãy số thực dương là {an } và {bn } thỏa mãn các điều kiện sau: ∞ ∑ an = ∞ n=1 ∞ ∑ anbn < ∞ n=1 ∞ (1.22) an ∑ ( bn )2 < ∞ n=1 ∞ lim bn = 0 n=1 và các quan sát không chệch ξ (x) của hàm hồi quy µ(x) có: Varξ (x) ≤ α 2 < ∞ (1.23) đồng thời hàm hồi quy µ(x) thỏa mãn ba điều kiện sau: 1. µ(x) và đạo hàm cấp hai của nó bị chặn. 2. x = θ là điểm cực tiểu địa phương của hàm hồi quy µ(x), tức là với ∀ε > 0; µ(θ ) ≤ µ(x) nếu |x − θ | < ε. d 3. x = θ là điểm dừng duy nhất của hàm hồi quy µ(x), tức là µ(x) 6= 0 nếu dx x 6= θ . Khi đó, thuật toán Kiefer - Wolfowitz (1.21) sẽ hội tụ theo nghĩa trung bình bình phương tới θ . 1.2.3 Thuật toán Dvoretzky Thuật toán Dvoretzky được coi như thuật toán tổng quát của các thuật toán xấp xỉ ngẫu nhiên. Bây giờ chúng ta sẽ nghiên cứu thuật toán này. Cho µ(x) là một hàm hồi quy có nghiệm tại x = θ . Để tìm nghiệm x = θ của 15 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều phương trình (1.2), ta giả sử có một dãy các quan sát là các biến ngẫu nhiên ξ1 , ξ2 , . . . , ξn , khi đó thuật toán Dvoretzky sẽ được xác định như sau: xn+1 = Tn (x1 , . . . , xn ) + ηn (1.24) trong đó Tn là một phép biến đổi từ không gian n - chiều vào không gian một chiều, còn ηn là thành phần ngẫu nhiên thỏa mãn E[ηn |x1 , . . . , xn ] = 0. Sau đây là các điều kiện để thuật toán Dvoretzky hội tụ. Định lý 1.2.4. Giả sử phép biến đổi Tn trong thuật toán Dvoretzky (1.24) thỏa mãn điều kiện sau: |Tn (x1 , . . . , xn ) − θ | ≤ Fn |xn − θ | (1.25) trong đó Fn là dãy các số dương thỏa mãn: ∞ Fn ≤ 1; ∏ Fn = 0 (1.26) n=1 Khi đó, nếu E[x12 ] < ∞; ∞ ∑ E[ηn2] < ∞ (1.27) n=1   E ηn |x1 , x2 , . . . , xn = 0 (1.28) thì thuật toán (1.24) sẽ hội tụ tới θ theo nghĩa trung bình bình phương, nghĩa là lim E|xn − θ |2 = 0 n→∞ Chứng minh. Từ (1.24) ta có: [xn+1 − θ ]2 = (Tn − θ )2 + 2ηn (Tn − θ ) + ηn2   → E[xn+1 − θ ]2 = E(Tn − θ )2 + 2E ηn (Tn − θ ) + E[ηn2 ] Có Z Z   Z  E ηn (Tn − θ ) = · · · ηn f (ηn |x1 , . . . , xn )dηn × (Tn − θ ) f (x1 , . . . , xn )dx1 , . . . , xn Vì các giá trị (x1 , . . . , xn ) cho trước và theo (1.28) nên Z   ηn f (ηn |x1 , . . . , xn )dηn = E ηn |x1 , x2 , . . . , xn = 0 16 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều   Do đó E ηn (Tn − θ ) = 0. Áp dụng giả thiết (1.26) suy ra: E[xn − θ ]2 = E(Tn − θ )2 + E[ηn2 ] ≤ Fn2 E[xn − θ ]2 + E[ηn2 ] Đặt Vn = E[xn − θ ]2 và αn2 = E[ηn2 ]. Khi đó, ta có: Vn+1 ≤ Fn2Vn + αn2 Sử dụng bất đẳng thức này với Vn và lặp lại (n − 1) lần ta có : 2 Vn ≤ Fn−1 Vn−1 + αn2  2  2 2 ≤ Fn−1 Fn−2Vn−2 + αn−1 + αn2 n ≤ · · · ≤ V1 β0n + ∑ α 2j β jn j=0 trong đó    n 2  ∏  l= j+1 Fl   β jn = 1      0 nếu 0 ≤ j < n nếu j = n nếu j > n Chọn i cố định sao cho i < n, ta có: i−1 Vn+1 ≤ V1 + ∑ α 2j j=1 n
max β jn + ∑ α 2j β jn 0≤ j n Theo giả thiết có β jn bị chặn đều bởi 1 và theo (1.27) thì ∑∞j=i α 2j < ∞ Do đó: lim ∑nj=i α 2j β jn = ∑∞j=i α 2j lim β jn = 0 n→∞ n→∞ Khi đó, vế phải của (1.29) có giới hạn tiến tới 0 khi n −→ ∞ Suy ra Vn+1 −→ 0(n −→ ∞) hay lim E[xn+1 − θ ]2 = 0 n→∞ Vậy định lý được chứng minh. 17 (1.29) Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều Định lý 1.2.5. : Giả sử các điều kiện ở định lý 1.2.4 thỏa mãn. Khi đó thuật toán Dvoretzky (1.24) sẽ hội tụ về θ với xác suất 1. Chứng minh. Theo chứng minh định lý 1.2.4 ta có: lim Vn = lim E[xn − θ ]2 = 0 n→∞ n→∞ ⇒ ∀ε > 0; ∃δ > 0 và k = k(δ , ε) sao cho ∀n ≥ k thì Vn < δ 2 ε Với k cố định, ta định nghĩa một thuật toán mới như sau: 0 0 xm+1 = Tm0 (x10 , . . . , xm ) + ηm0 (1.30) trong đó: Tm0 = Tm ; ηm0 = ηm nếu m < k còn nếu m ≥ k thì   Tm (x0 , . . . , x0 ) nếu |x0 − θ | < δ m m 1 0 0 0 Tm (x1 , . . . , xm ) =  0 −θ| ≥ δ. x0 nếu |xm m ηm0 =   ηm 0 −θ| < δ nếu |xm  0 0 −θ| ≥ δ. nếu |xm Ta sẽ chỉ ra thuật toán (1.30) cũng hội tụ theo nghĩa trung bình bình phương, tức Vn0 = E[xn0 − θ ]2 < δ 2 ε với ∀n ≥ k Thật vậy, giả sử tồn tại một số nguyên dương l nhỏ nhất sao cho |xl − θ | ≥ δ và k≤l≤n 0 và η 0 = 0 ⇒ Với k ≤ m ≤ l thì Tm0 = xm m 0 0 ⇒ xm+1 = xm với ∀k ≤ m ≤ l ⇒ Vm0 < δ 2 ε với ∀k ≤ m ≤ l 0 0 = ··· = V0 Khi đó, xl = xl0 = xl+1 = · · · = xn0 và Vl = Vl0 = Vl+1 n 0 Sự tồn tại của l tương ứng với |xn − θ | ≥ δ và l tồn tại nếu và chỉ nếu maxm |xm − θ | ≥ δ với k ≤ m ≤ n Do đó, P{maxk≤m≤n |xm − θ | ≥ δ } ≤ P{|xn0 − θ | ≥ δ } δ 2ε Cho n −→ ∞ ta thu được P{maxm≥k |xm − θ | ≥ δ } ≤ 2 = ε δ Vì vậy ta thu được kết quả tương đương như sau: P{|xm − θ | ≤ δ ; m = k, k + 1, . . . } > 1 − ε Do δ và ε là bất kỳ nên thuật toán hội tụ theo xác suất 1. 18 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều Chú ý: 1. Có thể thấy, thuật toán Robbins - Monro là trường hợp đặc biệt của thuật toán Dvoretzky. Thật vậy, nếu ta lấy: Tn (x1 , . . . , xn ) = xn − an µ(xn ) ηn = an [µ(xn ) − ξn ] thì thuật toán Robbins - Monro xác định ở (1.4) sẽ là một dạng của thuật toán Dvoretzky: xn+1 = xn − an µ(xn ) − an ξn = Tn + ηn Do đó để chứng minh tính hội tụ của thuật toán Robbins - Monro ta cần kiểm tra với các điều kiện của định lý (1.2.1) thì các điều kiện của định lý 1.2.4 thỏa mãn. Thật vậy, vì x1 , x2 , . . . độc lập cùng phân phối nên ξn chỉ phụ thuộc vào xn và E[ξn |x1 , . . . , xn ] = E[ξn ] = µ(xn ) Do đó: E[ηn |x1 , . . . , xn ] = E{an [µ(xn ) − ξn ]|x1 , . . . , xn } = an {E[µ(xn ) − ξn ]|x1 , . . . , xn } = an (µ(xn ) − µ(xn ) = 0 Như vậy điều kiện (1.28) được thỏa mãn. 2 Từ các giả thiết: Var[ξ (x) ≤ α 2 < ∞ và ∑∞ n=1 an < ∞ của định lý 1.2.1 ta có: ∞ ∑ n=1 E[ηn2 ] = ∞ ∑ a2nVar[ξn ] ≤ α 2 n=1 ∞ ∑ a2n < ∞ n=1 hay điều kiện (1.27) thỏa mãn. 2 Vì ∑∞ n=1 an < ∞ nên tồn tại một số hữu hạn k sao cho với ∀n ≥ k luôn có M1 an < 1 Đặt Fn = 1 − M1 an . Áp dụng bất đẳng thức ln(1 − x) ≤ −x∀x ∈ (0; 1) ta thu được: ∞ ∞ ln ∏∞ n=k Fn = ∑n=k ln Fn ≤ − ∑n=k M1 an ∞ Sử dụng giả thiết dãy số hiệu chỉnh có ∑∞ n=k an = ∞ ta suy ra ∏n=k Fn = 0 hay điều kiện (1.26) thỏa mãn. 19 Chương 1. Xấp xỉ ngẫu nhiên cho trường hợp một chiều Lại có: |Tn (x1 , . . . , xn ) − θ | = |xn − θ − an µ(xn )| ≤ |1 − M1 an ||xn − θ |; ∀n ≥ k = Fn |xn − θ | ⇒ Điều kiện (1.25) thỏa mãn. Vậy tất cả các điều kiện của định lý 1.2.4 được thỏa mãn. Theo định lý 1.2.4 thì thuật toán Robbins - Monro hội tụ theo nghĩa trung bình bình phương. 2. Thuật toán Kiefer - Wolfowitz cũng là trường hợp đặc biệt của thuật toán Dvoretzky. Thật vậy, đặt Tn (x1 ; . . . ; xn ) = xn +  an  µ(xn + bn ) − µ(xn − bn ) bn  an  − µ(xn + bn ) + µ(xn − bn ) + ξ (xn + bn ) − ξ (xn − bn ) bn thì thuật toán Kiefer - Wolfowitz xác định ở (1.21) sẽ có dạng tương đương là xn+1 = Tn (x1 ; . . . ; xn ) + ηn . Vì vậy, thuật toán (1.21) là dạng đặc biệt của thuật toán Dvoretzky. Do đó, tương tự như trên, ta cũng chứng minh được từ các điều kiện của định lý 1.2.3 sẽ suy ra các điều kiện của định lý 1.2.4, từ đó sẽ suy ra tính hội tụ của thuật toán Kiefer - Wolfowitz hay định lý 1.2.3 được chứng minh. ηn = 20 Chương 2 Xấp xỉ ngẫu nhiên cho trường hợp nhiều chiều Trong chương này, chúng ta sẽ khảo sát các mở rộng của các thuật toán xấp xỉ ngẫu nhiên đã đề cập trong chương 1 vào trong không gian n - chiều. 2.1 Thuật toán Robbins - Monro trong không gian n - chiều 2.1.1 Nội dung thuật toán Hàm hồi quy trong không gian n - chiều ký hiệu là µ(x) và có dạng µ(x) = E[ξ (x)]. Để tìm nghiệm của phương trình µ(x) = 0, ta sử dụng thuật toán Robbins - Monro có dạng sau: xn+1 = xn − an ξ n (2.1) trong đó ξ n = ξ (xn ). Khi đó ta thu được kết quả sau: Định lý 2.1.1. Giả sử dãy số hiệu chỉnh {an } thỏa mãn ∞ ∞ n=1 n=1 ∑ an = ∞; ∑ a2n < ∞ 21 (2.2)