Khóa luận Ứng dụng lọc particle trong bài toán theo vết đối tượng

từ phân phối bất kỳ. Tuy nhiên, do tính chất 26 Luận văn tốt nghiệp tuần tự của nó, thuật toán phải thực hiện rất nhiều lần để có thể sinh ra được một mẫu ngẫu nhiên mong muốn. Điểm yếu này cũng làm cho Metropolis-Hasting trở nên không phù hợp với bài toán lọc trực tuyến của chúng ta. 2.2.5. Phương pháp lấy mẫu quan trọng Trong phần trên, chúng ta đã xem xét 3 phương pháp sinh mẫu ngẫu nhiên từ một phân phối xác suất bất kỳ. Phương pháp hàm tích lũy xác suất nghịch đảo tuy đơn giản về ý tưởng và ý nghĩa toán học nhưng lại gặp phải vấn đề khi phải giải phương trình tính nghiệm ( )1XF u−=x . Phương pháp lấy mẫu loại trừ cũng không hiệu quả vì nó giả định rằng chúng ta đã biết trước được đại lượng ( )( ) | max | p π ⎧ ⎫⎪ ⎪⎨ ⎬⎪ ⎪⎩ ⎭ x z x z . Trong khi đó, phương pháp Metropolis-Hasting lại đòi hỏi quá nhiều vòng lặp của thuật toán trước khi nó thực sự hội tụ và sinh ra mẫu ngẫu nhiên của phân phối xác suất tĩnh. Vì thế, cả 3 phương pháp này đều không thích hợp cho bài toán lọc trực tuyến trong các ứng dụng thời gian thực chúng ta cần quan tâm. Trong phần này, chúng ta sẽ cùng xem xét phương pháp lấy mẫu quan trọng (Importance Sampling - IS) – phương pháp luận của lọc Particle – và tìm hiểu xem tại sao phương pháp này lại rất phù hợp với bài toán của chúng ta. Cho trước hàm mật độ xác suất ( )|π x z , gọi là hàm mật độ đề xuất (Proposal Density). Trong đó, ( )π i là một hàm mật độ có dạng đơn giản (theo nghĩa chúng ta có thể dễ dàng sinh ra các mẫu ngẫu nhiên tương ứng với nó) và thỏa điều kiện ( ) (, | 0 |D p )π∀ ∈ > ⇒x x z x z 0, nghĩa là tại mọi điểm tại đó thì x ( )|p >x z ( )|π x z cũng tồn tại và có ( )| 0π >x z . Nói cách khác, tại bất kỳ điểm nào trong miền xác định của , x ( | )π zi cũng có khả năng mô phỏng được ( )|p zi . Với những giả định trên, tích phân (2.3) được viết thành 27 Luận văn tốt nghiệp ( ) ( ) ( )( ) ( ) | | | p I f f dππ= ∫ x zx xx z z x (2.11) Suy ra ( ) ( ) ( ) ( ) ( ) ( )| | *pI f E f E f wπ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣= =x z x zx x ⎦x (2.12) Trong đó ( ) ( )( ) | * | p w π= x z x x z (2.13) Và hay ký hiệu cho kỳ vọng tương ứng với hàm mật độ xác suất . Từ giả định về hàm ( )|pE ⎡ ⎤⎣ ⎦zi i |pE ⎡ ⎤⎣ ⎦zi ( |p zi ) ( )|π x z , hiển nhiên ta có thể dễ dàng thu được một tập mẫu ngẫu nhiên độc lập, đồng nhất ( ) ( ){ }1 , , Nx x… tương ứng với ( | )π x z . Như vậy, biểu thức (2.11) có thể được ước lượng bằng tích phân Monte Carlo như sau ( ) ( )( ) ( )( )11 *N iN iI f f w iN =∑ x x (2.14) Đặt ( ) ( )( ) ( )( ) ( )( )* * | |i i i iw w p π= =x x z x z , gọi là trọng số (Importance Weight) tương ứng với các mẫu ngẫu nhiên, (2.14) trở thành ( ) ( )( ) ( )11 *N iiN iI f fN w=∑ x (2.15) Như ta đã thấy ở mục 2.2.1, biểu thức (2.15) là hợp lệ, nghĩa là, theo luật mạnh số lớn, nếu ( | )π x z có phương sai hữu hạn thì ( )NI f hội tụ về ( )I f với xác suất 1 khi . Tuy nhiên, việc lượng giá biểu thức (2.15) không hoàn toàn đơn giản. Trong những phần truớc, chúng ta chưa đề cập đến việc lượng giá N →+∞ ( )|p x z và hiểu ngầm rằng ta có thể dễ dàng tính được ( )|p x z với cho trước. Thật không may, trong thực tế, để tính được thường đòi hỏi nhiều phép tính xấp xỉ phức tạp. x ( |p x z ) 28 Luận văn tốt nghiệp IS giải quyết vấn đề này bằng cách biến đổi ( )* iw và tránh trực tiếp ước lượng biểu thức như sau ( |p x z ) ( ) ( )( ) ( )( ) ( )( ) ( )( ) ( ) ( )( ) | | 1* | | i i i i i p p p w pπ π= = × x z z x x zx z x zi (2.16) Suy ra (2.11) trở thành ( ) ( ) ( ) ( )( ) ( ) ( ) | | | p p I f f d p ππ= ∫ z x xx z x z x z x (2.17) Mặc dù ta khó có thể tính trực tiếp ( )|p x z nhưng ngược lại, ta có thể dễ dàng tính likelihood và xác suất prior ( )( )| ip z x ( )( )ip x . Chỉ còn một vấn đề nữa là làm sao lượng giá được . Thay ( )p z ( ) ( ) ( )|p p p d=z z x x x , ta có ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) |1 | | | | | | | | | | | | p p I f f d p p p f d p p d p p f d p p d ππ ππ ππ ππ = = = ∫ ∫ ∫ ∫ ∫ z x x x x z x z z x x x x z x z z x x x z x x x x z x z z x x x z x x z z x x x (2.18) Suy ra ( ) ( ) ( ) ( ) ( ) ( ) | | E f w I f E w π π ⎡ ⎤⎣ ⎦ ⎡ ⎤⎣ ⎦ = x z x z x x x (2.19) Trong đó 29 Luận văn tốt nghiệp ( ) ( ) ( )( ) |p p w π= z x x x z (2.20) Hiển nhiên đến lúc này, biểu thức trong (2.20) có thể được tính dễ dàng vì các biểu thức con trong nó đều đã được biết trước và có dạng đơn giản. Vậy, tích phân Monte Carlo trong (2.15) có thể được viết thành ( ) ( )( ) ( ) ( ) ( )( )i( )1 1 1 1 N i i N iii N N i i i f w NI f f w w N = = = ∑ ∑∑ x x (2.21) Trong đó ( )iw ký hiệu cho ( )( )iw x và trọng số chuẩn hóa i( )iw được cho bởi i ( ) ( ) ( ) ( )( ) ( )( ) 1 1 ii i N N j j j j www w w = = = ∑ ∑ x x  (2.22) Theo luật mạnh số lớn, hiển nhiên trong (2.21), ( )NI f sẽ tiến về ( )I f với xác suất 1 khi tiến đến vô cực. N Nếu ta đặt m ( ) i( ) ( ) ( )1| iiNN ip w δ==∑ xx z x (2.23) Suy ra ( ) ( )m ( ) ( ) ( )|N NI f f p d f p d= ≈∫ ∫x x z x x x z x| (2.24) (2.24) cho thấy kết quả của thuật toán IS không chỉ là ước lượng của tích phân ( ) ( )|f p∫ x x z dx ) ) mà còn là ước lượng của xác suất posterior qua một biến đổi của hệ. Đây cũng chính là tâm điểm của lọc Bayes trong đó mục tiêu chính là mật độ xác suất posterior qua các biến đổi của hệ. ( |p x z ( |p x z 30 Luận văn tốt nghiệp Qua những trình bày trên, ta thấy IS cung cấp cho ta một phương pháp để xấp xỉ mật độ xác suất mà không đòi hỏi phải thực sự có khả năng tạo tập mẫu ngẫu nhiên từ . Trong khi đối với thuật toán lấy mẫu loại trừ và thuật toán Metropolis-Hasting, các mẫu được phân phối theo hàm mật độ , thì đối với thuật toán lấy mẫu quan trọng, các mẫu được phân phối theo hàm mật độ đề xuất. Sau đó, các trọng số sẽ được cập nhật để phản ánh đúng ước lượng trong (2.21). ( |p x z ) ) ) ( |p x z ( |p x z Từ những nhận xét trên, ta thấy IS là thuật toán duy nhất có thể được áp dụng trong các bài toán lọc thời gian thực vì tính hiệu quả và chi phí thấp của nó. Nó không đòi hỏi quá trình sinh mẫu – chọn lựa cũng như thời gian thực thi đủ lâu để thuật toán hội tụ. Đây chính là lý do phương pháp lấy mẫu quan trọng trở thành phương pháp luận chủ yếu của lọc Partilce. Tên của lọc Particle có lẽ cũng xuất phát từ phương pháp luận này: dùng các phần tử mẫu (tương tự như các phần tử nhỏ, các hạt) để mô phỏng phân phối xác suất của chúng qua những lần biến đổi của hệ. 2.3. Phương pháp lấy mẫu quan trọng tuần tự Phương pháp lấy mẫu quan trọng IS là một phương pháp tích phân Monte Carlo tổng quát. Tuy nhiên, tại mỗi thời điểm , ta cần phải truy cập và sử dụng tất cả mọi thông tin trong trước khi có thể tính được t 1:tz ( )0: 1:|t tp x z . Nói theo cách khác, mỗi khi dữ liệu về quan sát mới có hiệu lực, ta phải tính toán lại trọng số đối với toàn bộ không gian trạng thái. Chi phí tính toán này sẽ tăng theo thời gian, khi mà dữ liệu tích lũy ngày càng nhiều. Trong phần này, chúng ta sẽ xem xét thuật toán lấy mẫu quan trọng tuần tự (Sequential Importance Sampling – SIS) và các tính chất của nó để có thể giải quyết vấn đề nêu trên. Như đã trình bày, thuật toán IS cho ta một phương pháp để ước lượng mật độ xác suất posterior bằng m ( )Np x . Trong đó, m ( )Np x được cho bởi tập mẫu-trọng số 31 Luận văn tốt nghiệp ( ) i( ){ } 1 , Nii i w = x , với i( )iw là trọng số chuẩn hóa tương ứng với các mẫu . Áp dụng vào bài toán lọc của chúng ta, ( )ix m ( )0: 1:|N t tp x z được cho bởi tập mẫu-trọng số ( ) i( ){ }0: 1 , Nii tt i w = x với các trọng số chưa chuẩn hóa cho bởi ( ) ( )( ) ( )( ) ( )( ) 1: 0: 0: 0: 1: | | i i t t ti t i t t p p w π= z x x x z (2.25) Mục tiêu của thuật toán lấy mẫu quan trọng tuần tự SIS là tính toán xấp xỉ của m ( )0: 1:|N t tp x z ( )0: 1:|t tp x z một cách đệ quy mà không cần tác động đến những thông tin cũ về trạng thái ( ){ }0: 1; 1, ,i t i− =x … N . Điều này có nghĩa là hàm mật độ đề xuất tại thời điểm t phải thỏa ( ) ( ) ( )0: 1: 0: 1 1: 1 0: 1 1:| | |tt t t t t t,π π π− − −=x z x z x x z (2.26) Nghĩa là (2.27) ( ) ( ) (0: 1: 0 0: 1 1: 1 | | t t t k k k k π π π − = = ∏x z x x x z ), Dựa vào ràng buộc trên, ta có thể sinh một mẫu ( ) ( )0: 0: 1:|i t tπx x z∼ t dựa vào thủ tục đơn giản sau: • Bước 1: Sinh ra một ( ) ( )0: 1 1:| ,it t tπ −x x x z∼ t mới. • Bước 2: Đặt ( ) ( ) ( ){ }0: 0: 1,i i tt t−=x x x i Không có điều kiện như trong (2.27), để sinh ra một mẫu ( )0:itx mới từ ( )0: 1:|t tπ x z , ta cần phải tái tạo lại toàn bộ các mẫu ( )0: 1i t−x trước đó. Thay (2.26) vào (2.25), ta có 32 Luận văn tốt nghiệp ( ) ( )( ) ( )( ) ( ) ( )( ) ( )( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) 1: 0: 0: 0: 1 1: 0: 1 1: 1 0: 1 1: 1 0: 1 0: 1 0: 1 1: 0: 1 1: 1 1 1 0: 1 1: | | , | | | | | , | | | | , i i t t ti t i i i t t t t t i i i i i t t t t t t i i i t t t t t i i i t t t t i ti i t t t p p w p p p p p p w π π π π π − − − t− − − − − − − − − = = × = × z x x x x z x z z x x x z x x x x z x z z x x x x x z − (2.28) Từ dòng 1 xuống dòng 2 của biểu thức, ta sử dụng giả định 2 về sự độc lập của các quan sát thu được ( ) ( ) ( )1: 1: 1: 1 1: 1| | |t tt t t tp p p − −=z x z x z x và công thức Bayes ( )( ) ( ) ( )( ) ( ) ( )( ) ( )( )0: 0: 1 0: 1 0: 1, |i i i i it tt t tp p p p− −= =x x x x x x i t− . Từ dòng 2 xuống dòng 3 của biểu thức, ta sử dụng giả định 1 về chuỗi trạng thái ( ) ( )0: 1 1| |t tt tp p− −=x x x x . Như trên đã nói, thuật toán SIS tìm kiếm một giải pháp đệ quy trong đó không cần phải sử dụng những thông tin trước đó về trạng thái cũng như các quan sát. Để thực hiện điều này, hàm mật độ đề xuất trong tử số của (2.28) cần phải được biến đổi một chút. Thứ nhất, ta không muốn lưu trữ toàn bộ thông tin về những độ đo đã có trước nên hàm mật độ đề xuất chỉ cần phụ thuộc duy nhất vào quan sát tại thời điểm , . Thứ hai, ta cũng không muốn ghi lại những thông tin về trạng thái trước 1: 1t−z t tz ( )0: 1it−x . Điều này có nghĩa là hàm mật độ đề xuất chỉ cần phụ thuộc duy nhất vào trạng thái tại thời điểm . Như vậy, (2.27) trở thành 1t − (2.29) ( ) ( ) (0: 1: 0 1 1 | t t t k k k k π π π − = = ∏x z x x x z )| , Thay (2.29) vào (2.28) ta có ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) 1 1 1 | | | , i i i t t t ti i t t i i t tt p p w w π − − − = × z x x x x x z (2.30) 33 Luận văn tốt nghiệp Như có thể thấy trong (2.30), biểu thức tính trọng số lúc này không còn yêu cầu các lưu trữ về trạng thái cũng như quan sát ( )0: 1it−x 1: 1t−z . Phương trình trong (2.30) như vậy có thể được sử dụng trong các cài đặt thực tế đòi hỏi các tính toán thời gian thực. Một cách tóm tắt, thuật toán lấy mẫu quan trọng tuần tự có thể được trình bày như trong Hình 2. Như ta có thể thấy, thuật toán SIS thực sự có ý tưởng và cấu trúc rất đơn giản, điều này khiến cho nó trở thành thuật toán rất phổ biến trong các bài toán xấp xỉ bằng lọc Bayes đệ quy. Thuật toán 1 Sequential Importance Sampling ( ) i ( ){ } ( ) ( ){ }0: 0: 11, ,N Nii it t tt t iiw SIS w ==⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥⎣ ⎦⎣ ⎦ =x x ,i z • FOR 1:i N= o Sinh ra ( ) ( )( )1| ,itit tπ −x x x∼ tz . o Tính ( )itw theo công thức ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) 1 1 1 | | | , i i i t t t ti i t t i i t tt p p w w π − − − = × z x x x x x z • END FOR • FOR , chuẩn hóa trọng số của các mẫu 1:i = N i( ) ( ) ( ) 1 i i t t N j tj ww w= = ∑ Hình 2 Thuật toán Sequential Importance Sampling 2.4. Giả lập thuật toán SIS Trong phần này, chúng ta sẽ xem xét một ví dụ trực quan về thuật toán SIS bằng cách mô phỏng sự hoạt động của nó trên một chuỗi dữ liệu mẫu sinh ngẫu nhiên của hệ cho bởi các phương trình sau 34 Luận văn tốt nghiệp ( ) ( )( )1 1 1| ; , ,t tt tkp N f k− − kQ −x x x x∼ (2.31) ( ) 2| ; 20tt t t kp N ⎛ ⎞⎜⎝ ⎠ xz x z∼ , R ⎟ (2.32) trong đó ( ) (1 11 2 1 25, 8c 2 1 t t tk t )os 1.2f k − −− − = + ++ x xx x k ) (2.33) và ( 2; ,N µ δx là hàm Gauss tương ứng với biến có kỳ vọng là x µ và phương sai δ . Hình 3 Dữ liệu giả lập thuật toán SIS Hình 3 cho ta thấy kết quả từ việc mô phỏng sự biến đổi của hệ được mô tả bởi 2 phương trình (2.32) và (2.33). Đường màu xanh tương ứng với trạng thái thực của hệ 35 Luận văn tốt nghiệp thống. Đường màu đỏ tương ứng với nhữrng quan sát thu được. Một cách trực quan, ta có thể thấy các giá trị của trạng thái và độ đo thu được là những giá trị phi tuyến rất rõ rệt. Hình 4 Kết quả lọc bằng SIS Hình 4 cho thấy kết quả sau khi thực hiện thuật toán SIS trên dữ liệu mô phỏng bên trên. Đường màu xanh trong hình vẫn là dữ liệu về trạng thái thực của hệ. Đường màu đỏ là giá trị trạng thái của hệ sau khi ước lượng bằng thuật toán SIS. Kết quả thu được chưa hoàn toàn tốt, vẫn còn có nhiều điểm, giá trị ước lượng của trạng thái còn khác nhiều so với giá trị thực của hệ. Nguyên nhân chủ yếu của hiện tượng này là do thuật toán SIS gặp phải vấn đề thoái hóa của các giá trị trọng số trong quá trình hoạt động của nó như sẽ được trình bày trong phần tiếp theo. Tuy nhiên, qua những đánh 36 Luận văn tốt nghiệp giá sơ bộ, ta có thể thấy được thuật toán lọc SIS hoàn toàn phù hợp với những ứng dụng thời gian thực của chúng ta và quan trọng hơn nữa, các kết quả cũng cho thấy nền tảng lý thuyết của lọc Particle – phương pháp Monte Carlo – là đúng đắn và là cơ sở áp dụng cho các ứng dụng theo dõi, xử lý tính hiệu số, thị giác máy tính mà chúng ta cần quan tâm. 2.5. Các vấn đề về thuật toán SIS 2.5.1. Sự thoái hóa của thuật toán SIS Thuật toán SIS chính là bộ khung của các ứng dụng lọc Bayesian theo hướng Particle. Tuy nhiên, một vấn đề thường gặp đối với thuật toán SIS chính là hiện tượng thoái hóa mẫu (Degeneracy of SIS), trong đó sau một vài vòng lặp, ngoại trừ một mẫu duy nhất trong tập mẫu, tất cả những phần tử còn lại đều có trọng số rất nhỏ, không đáng kể. Hình 5 Sự thoái hóa của thuật toán SIS 37 Luận văn tốt nghiệp Qua thực nghiệm với dữ liệu giả lập, ta có thể thấy rất rõ hiện tượng thoái hóa này. Hình 5 cho ta thấy biểu đồ trọng số của các mẫu theo thời gian. Thuật toán được thực hiện với 200 mẫu, và với 200 vòng lặp. Trục đứng trên hình biểu thị cho giá trị của các trọng số. Trục nằm ngang bên trái hình biểu thị cho số lần lặp. Trục nằm ngang bên phải hình biểu thị cho các trọng số của các mẫu. Trên hình, ta có thể thấy, trong những vòng lặp đầu tiên, các mẫu vẫn còn tương đối “tốt”, theo nghĩa, hầu như các trọng số vẫn mang giá trị đồng đều, tất cả các mẫu đều góp phần quyết định giá trị của hàm phân phối đích posterior . Tuy nhiên, chỉ trong vòng vài vòng lặp, rõ ràng có sự khác biệt giữa các trọng số này. Có rất nhiều điểm mẫu tại đó giá trị của trọng số rất lớn, gần bằng 1, thường hoán đổi vị trí cho nhau, trong khi tất cả những điểm còn lại, trọng số hầu như bằng 0. Và cho đến vòng lặp khoảng 100, chỉ có duy nhất một mẫu có trọng số, tất cả các mẫu còn lại trọng số hầu như không có. Điều này cho thấy phương sai của các trọng số tăng dần theo các bước thực hiện của thuật toán. z ( 1:|t tp x z ) * , w Trên lý thuyết, hiện tượng này có thể được chứng minh thông qua bổ đề sau Bổ đề 2.1 Sự thoái hóa của các trọng số Phương sai không điều kiện của trọng số thực sự tăng dần theo thời gian, ( ) ( )0: 1 1: 1 0: 1: * 1,var vart t t t ttwπ π− − −⎡ ⎤ ⎡ ⎤⎣ ⎦ ≤x z x z ⎣ ⎦ * t (2.34) trong đó, chỉ số dưới dòng ở biểu thức phương sai chỉ ra rằng những giá trị kỳ vọng là được tính tương ứng với chuỗi độ đo và chuỗi trạng thái tương ứng. Hơn nữa, ta lại có ( ) ( ) ( )1:0: 1: 0: 1: * 1:, ,var var |tt t t tpt tw E wπ π ⎡ ⎤⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦⎢ ⎥⎣ ⎦= zx z x z z (2.35) nghĩa là, với một chuỗi quan sát cho trước , phương sai có điều kiện của trọng số có xu hướng tăng dần. 1:tz Chứng minh Ta định nghĩa một hàm mật độ hỗ trợ như sau 38 Luận văn tốt nghiệp i ( ) ( ) ( )0: 1 1: 1 0: 1 1: 0: 1 1: 1, | , | , | ,t t t tt t t t t tπ π π− − − −x z x z x x z z x z − (2.36) ( ) ( )1| , |t t tt p 1: 1tπ − −= x x z z z (2.37) là hàm mật độ xác suất trong đó trạng thái và quan sát hiện tại được sinh ra, dựa vào điều kiện về trạng thái ngay trước và các độ đo trong quá khứ. Từ (2.36) đến (2.37), ta sử dụng giả thiết rằng quan sát thật ra không được sinh ra từ hàm mật độ đề xuất mà được sinh ra từ hàm mật độ kiểm soát quá trình quan sát của hệ. Hơn nữa, quan sát chỉ phụ thuộc vào trạng thái của hệ tại thời điểm tương ứng nên ta có . tz tz ( ) (0: 1 1: 1 1: 1| , |t tt t tp p− − −=z x z z z ) Sử dụng phương trình trong (2.16) và (2.37) ta có i ( ) i ( )0: 1 1: 1, | , * * 0: 1 1: 1, | ,t t t t t t t t t tE w w dπ π− − − −⎡ ⎤⎣ ⎦ = ∫ ∫x z x z x z x z x zt td (2.38) ( ) ( ) ( ) ( ) i ( ) 1: 0: 0: 1: 0: 1: 0: 1 1: 1 | | , | , t t t t t t t t t tt t p p p d d π π − −× = ∫ ∫ z x x z x z x z x z x z (2.39) ( ) ( ) ( ) ( ) i ( ) 1 1 1: 1 0: 1 0: 1 1: 1 | | | | , | , t t t t t t t t t t t t tt t p p w p d d π π −∗ − − − − − = × ∫ ∫ z x x xz z x x z x z x z x z , t (2.40) ( ) ( )1 | |t t t ttw p p d d∗−= ∫ ∫ z x x x x z1 tt− (2.41) ( )1 1, |t t t tt tw p d d w 1t∗ ∗− − == ∫ ∫ x z x x z − (2.42) Cho một biến ngẫu nhiên X , ta có ( ) ( )|var var var |X Y XX E E Y⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣= + ⎦ w (2.43) Dùng (2.42) ta có ( ) ( ) i( )0: 1 1: 1 0: 1 1: 1 0: 1 1: 11, , , | ,var var t tt t t t t t ttw Eπ π π− − − − − − ∗ ∗ − ⎡ ⎤⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦⎢ ⎥⎣ ⎦=x z x z x z x z (2.44) Sử dụng tiếp (2.43), suy ra 39 Luận văn tốt nghiệp ( ) ( ) i( ) ( ) 0: 1 1: 1 0: 1: 0: 1 1: 1 0: 1: 1| | , | , | var var var var t tt t t t t t t t t tt t w w E w π π π π − − − − ∗ ∗ − ∗ w∗⎡ ⎤⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ ⎣ ⎦⎢ ⎥⎣ ⎦ ⎡ ⎤⎣ ⎦ = − ≤ x z x z x z x z x z (2.45) Như vậy, Bổ đề 2.1 đã được chứng minh. Hơn nữa ( )( ) ( )0: 1:* 1: 0: 1: 0:0: 1: | | | | t t t t t t t p E w dππ⎡ ⎤⎣ ⎦ 1t t= =∫ x zz x zx z x tw (2.46) Áp dụng (2.43), suy ra 1:var | vart tE w∗ ∗⎡ ⎤⎡ ⎤⎣ ⎦⎣ ⎦ =z . Như vậy, đối với một chuỗi độ đo cho trước, phương sai có điều kiện của các trọng số có xu hướng tăng theo thời gian, gây ra sự thoái hóa của ước lượng (ĐPCM). Sự thoái hóa này là không tránh khỏi trong các bộ lọc dựa trên phương pháp Monte Carlo. Do đó, vấn đề quan tâm hàng đầu của chúng ta là làm sao giảm bớt ảnh hưởng của hiện tượng này. 2.5.2. Vấn đề chọn hàm mật độ đề xuất Như đã nói trong các phần trước, sự hợp lý của phương pháp xấp xỉ tích phân Monte Carlo đặt nền tảng trên phát biểu của luật mạnh số lớn. Để thuật toán hội tụ, chúng ta cần phải có một số lượng mẫu rất lớn trong khi chỉ có thể xử lý một lượng mẫu hữu hạn. N →∞ Chúng ta đều biết các mẫu trong thuật toán SIS không thực sự được sinh ra bởi mật độ xác suất mà là từ hàm mật độ đề xuất. Một cách trực quan, ta nhận thấy vị trí của các mẫu được sinh ra có ảnh hưởng rất lớn đến kết quả ước lượng, hay nói cách khác, mật độ đề xuất càng “tốt” chừng nào thì kết quả ước lượng càng “tốt” chừng ấy. ( |p x z ) ⎤⎦ Bổ đề 2 Mật độ đề xuất tối ưu Hàm mật độ đề xuất làm cực tiểu hóa phương sai là ( ) ( ) 1| , var i t tt i twπ −⎛ ⎞⎜ ⎟⎝ ⎠ ⎡⎣x x z 40 Luận văn tốt nghiệp ( )( ) ( )( )1| , | ,iopt t t t tt pπ − =x x z x x z1it− (2.47) Chứng minh Ta có ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) 1 1 1 | | | , i i i t t t ti i t t i i opt t tt p p w w π − − − = z x x x x x z (2.48) ( ) ( ) ( )( ) ( ) ( )( ) 1 1 1 , | | , i i t t ti t i i t tt p w p − − − = x z x x x z (2.49) ( ) ( )( )1|it t tw p i−= z x (2.50) Như vậy, trọng số ( )itw độc lập với giá trị của mẫu được sinh ra của trạng thái hiện tại, nghĩa là ( ) ( ) 1| , var 0i t tt i twπ −⎛ ⎞⎜ ⎟⎝ ⎠ ⎡ ⎤⎣ ⎦ =x x z . Có hai vấn đề đối với cách tiếp cận sử dụng hàm mật độ đề xuất này. Một là, nó đòi hỏi phải có khả năng tạo mẫu ngẫu nhiên từ hàm mật độ ( )( )1| ,it tp −x x zt , hàm mật độ này có thể là không chuẩn. Hai là, việc tính ( )itw trong (2.50) đòi hỏi phải thực hiện một phép tính tích phân ( )( ) ( )( ) ( ) ( )( )1| | |i i it t t ttp p p− = ∫z x z x x x x1i tt d− (2.51) mà có thể cũng trở nên rất phức tạp vì không thể giải bằng các biểu thức giải tích thông thường. Tuy nhiên, có cũng có hai trường hợp trong đó ta có thể sử dụng được ( )optπ i . Trường hợp đầu tiên là đối với bài toán có không gian trạng thái rời rạc, hữu hạn. Khi đó, tích phân trong (2.51) trở thành tổng hữu hạn cũng như việc phát sinh mẫu từ tx 41 Luận văn tốt nghiệp ( )( )1| ,it tp −x x zt là có thể thực hiện được. Trường hợp thứ hai, tương tự như mô hình hệ thống của lọc Kalman, là bài toán trong đó nhiễu của hệ thống có dạng Gauss và quan sát có được từ hệ thống có dạng tuyến tính. Với trường hợp này, (2.51) cũng có thể tính được vì cả hai biểu thức trong tích phân đều có dạng Gauss. Hơn nữa, vì quan sát có dạng tuyến tính nên ( )( )1| ,it tp −x x zt cũng có dạng tuyến tính và có thể phát sinh mẫu từ hàm này tương đối đơn giản. Việc sử dụng hàm mật độ đề xuất nào đóng vai trò rất quan trọng, quyết định đến hiệu suất của hệ thống. Vì vậy có rất nhiều nghiên cứu quan tâm đến vấn đề cải tiến hàm mật độ đề xuất. Những cải tiến gần đây bao gồm các bộ lọc như lọc Particle hỗ trợ (Auxiliary Particle Filter), lọc Unscented Particle (Unscented Particle Filter),… Trong thực tế, vì nhiều vấn đề về cài đặt và hiệu suất, hàm mật độ đề xuất thường được chọn trong các ứng dụng là ( )( ) ( )( )1| , |it t tt pπ 1it− −=x x z x x (2.52) Bằng cách này, chúng ta có thể dễ dàng phát sinh các mẫu trong quá trình thực hiện thuật toán. Giả sử trong một hệ ( )1t t tf − t= +x x u , với là nhiễu, để phát sinh ngẫu nhiên một mẫu mới, ta chỉ đơn giản là phát sinh một mẫu khác từ phân phối của nhiễu . Hơn nữa, bằng cách sử dụng hàm mật độ đề xuất như trên, biểu thức tính tu ( )tp u ( )itw trong (2.30) có thể được rút gọn thành ( ) ( ) ( )( )1 |i i it ttw w p−= z xt ) (2.53) Tuy nhiên, một vấn đề cần chú ý khi sử dụng hàm này là nó có thể làm cho bộ lọc hoạt động kém hiệu quả. Hình 6 cho ta thấy một cách trực quan trường hợp này. Ở đây, hàm likelihood có dạng tập trung tại một điểm, trong khi hàm mật độ đề xuất ( |t tp z x 42 Luận văn tốt nghiệp lại có mật độ trải đều khắp trên miền xác định. Như vậy, sẽ có rất nhiều mẫu ( )itx sẽ có trọng số rất nhỏ, không đáng kể và kết quả là làm giảm kết quả ước lượng. Hình 6 Ví dụ về trường hợp dẫn đến sai lầm khi chọn hàm mật độ đề xuất tối ưu Như đã được chỉ ra trong [Okuma2004], một hàm mật độ đề xuất tốt thường là hàm có khả năng sử dụng những thông tin có từ những độ đo về hệ thồng ở những thời điểm gần nhất. Đây chính là nguyên nhân làm cho hàm ( )( ) ( )( )1 1| , |i it t tt tpπ − −=x x z x x kém hiệu quả trong một số trường hợp. 2.5.3. Tái chọn mẫu Trong phần này trình bày về phương pháp thứ hai để giảm bớt tác dụng của hiện tượng thoái hóa mẫu, đó là phương pháp tái chọn mẫu (Resampling). Trong những phần trên, ta đã biết m ( ) i( ) ( ) ( )1: 1| it iN tt tN t i p w δ==∑ xx z x chính là một ước lượng rời rạc của hàm mật độ ( )1:|t tp x z . Sau một vài lần thực hiện, tất cả các mẫu đều có trọng số rất nhỏ, ngoại trừ một mẫu duy nhất có trọng số bằng 1. Tuy nhiên, ta nhận thấy không phải tất cả các mẫu đều thực sự góp phần quyết định vào giá trị của hàm mật độ posterior ( )1:|t tp x z mà chỉ có những mẫu tương đối gần 43 Luận văn tốt nghiệp với kỳ vọng ( )I f mới có đóng góp đáng kể trong việc quyết định giá trị của hàm. Phương pháp tái chọn mẫu giải quyết vấn đề này bằng cách sắp xếp và điều chỉnh lại mẫu đã có sẵn để xấp xỉ tốt hơn hàm mật độ này. N Gọi i( )itx là vector trạng thái trước khi tái chọn mẫu và ( )itx là vector trạng thái sau khi bước tái chọn mẫu được thực hiện. Vậy thủ tục tái chọn mẫu chính là ánh xạ i( ) i ( ){ } ( ) 1 1 1, , NNi i i t t t i i w N= = ⎧ ⎫⎨ ⎬⎩ ⎭→x x (2.54) sao cho ( ) i( ) i( )Pr j ji t tt w⎛ ⎞⎜ ⎟⎝ ⎠= =x x Bằng cách sắp xếp lại các mẫu và đặt lại các trọng số mới, thuật toán tránh được hiện tượng thoái hóa (tại mỗi thời điểm, trọng số của các mẫu đều như nhau và bằng 1 N ) và giúp cho thuật toán SIS tập trung vào những vị trí “hứa hẹn” nhất trong không gian trạng thái tại đó có đối tượng cần quan tâm. Cho rằng ta đã có một ánh xạ như trong (2.54), vấn đề đặt ra là làm sao biết được mức độ thoái hóa của các trọng số, hay nói cách khác, khi nào ta cần phải mẫu. Trong [Kong1994], Kong đã đề xuất một độ đo mới để tính sự thoái hóa, gọi là kích thước mẫu hiệu dụng (Effective Sample Size), ký hiệu . Độ đ