Đại Học Quốc Gia Tp. Hồ Chí Minh
TRƯỜNG ĐẠI HỌC BÁCH KHOA

NGUYỄN PHAN THANH BỬU

PHƯƠNG PHÁP MONTE CARLO
ỨNG DỤNG VÀO XỬ LÝ TÍN HIỆU
VÀ MƠ HÌNH HĨA TRÊN DSP
(MONTE CARLO METHODS APPLIED TO SIGNAL
PROCESSING AND MODELLING BASED ON DSP)
Chuyên ngành : Kỹ thuật điện tử
Mã số ngành : 60.52.70

LUẬN VĂN THẠC SĨ

Tp. Hồ Chí Minh, tháng 7 năm 2007


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học: PGS-TS Lê Tiến Thường

Cán bộ chấm nhận xét 1:

Cán bộ chấm nhận xét 2:

Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC
SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . . tháng 7 năm 2007.

TRƯỜNG ĐẠI HỌC BÁCH KHOA

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

PHÒNG ĐÀO TẠO SĐH

ĐỘC LẬP – TỰ DO – HẠNH PHÚC
Tp. HCM, ngày . . . . tháng . . . . năm 2007

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: Nguyễn Phan Thanh Bửu
Ngày, tháng, năm sinh: 07/04/1983
Chuyên ngành: Kỹ thuật điện tử

Phái: Nam
Nơi sinh: Đồng Nai
MSHV:01405298

I- TÊN ĐỀ TÀI: ‘PHƯƠNG PHÁP MONTE CARLO ỨNG DỤNG TRONG XỬ LÝ TÍN
HIỆU VÀ MƠ HÌNH HĨA TRÊN DSP’
II- NHIỆM VỤ VÀ NỘI DUNG:
•

Nghiên cứu vấn đề xử lý tín hiệu model-based và các mơ hình dynamic system.
• Xây dựng thuật toán cho các phương pháp Monte Carlo (phương pháp MCMC và
SMC ) ứng dụng trong xử lý tín hiệu dựa vào mơ hình: tính tốn BER, hàm
likelihood,.. và một số ứng dụng khác.
•


Mơ phỏng các thuật tốn của các phương pháp Monte Carlo ứng dụng trong xử lý
tín hiệu cũng như một số vấn đề quan trọng khác (neural networks,…) để thấy
được hiệu suất BER của các phương pháp trong kênh truyền fading và khả năng
ứng dụng của các phương pháp Monte Carlo trong các mơ hình khơng gian trạng
thái tuyến tính, phi tuyến, hỗn hợp, mơ hình Bayesian, mơ hình nhiễu Gauss,…
vào các vấn đề quan trọng trong thực tiễn. Thơng qua đó tiến hành so sánh các
phương pháp với nhau.
• Thực hiện mơ hình hóa một số thuât toán của các phương pháp MCMC và SMC
ứng dụng trong xử lý tín hiệu model-based trên kit DSP TMS320C6711, đánh giá
kết quả thu được trên DSP kit TMS320C6711 so sánh với kết quả mô phỏng trên
Matlab.

III- NGÀY GIAO NHIỆM VỤ: 22/02/2007
IV- NGÀY HOÀN THÀNH NHIỆM VỤ: 06/07/2007
V- CÁN BỘ HƯỚNG DẪN : PGS.TS LÊ TIẾN THƯỜNG
CÁN BỘ HƯỚNG DẪN

CN BỘ MÔN
QL CHUYÊN NGÀNH

Nội dung và đề cương luận văn thạc sĩ đã được Hội đồng chuyên ngành thông qua.
Ngày…...tháng…..năm 2007
TRƯỞNG PHÒNG ĐT – SĐH

TRƯỞNG KHOA QL NGÀNH


LỜI CẢM ƠN
Tôi xin chân thành cảm ơn thầy Lê Tiến Thường đã tận tình hướng dẫn,
giúp đỡ tạo mọi điều thuận lợi về tài liệu cũng như trang thiết bị để tơi

hồn thành luận văn này.
Tơi cũng xin chân thành cảm ơn quý thầy cô ở Khoa Điện-Điện Tử
trường Đại Học Bách Khoa, là những người dạy dỗ, truyền đạt kiến thức
và định hướng nghiên cứu trong suốt khóa đào tạo sau đại học.
Cuối cùng xin cảm ơn ba, mẹ, anh, chị, đồng nghiệp và bạn bè đã giúp
đỡ, động viên tơi trong suốt q trình học tập và nghiên cứu.
Xin chân thành cảm ơn
Nguyễn Phan Thanh Bửu


LÝ LỊCH TRÍCH NGANG
Họ và tên:

NGUYỄN PHAN THANH BỬU

Ngày sinh:

07/04/1983

1. Lý lịch:
⋅

Nơi sinh: Thành Phố Biên Hòa, Tỉnh Đồng Nai.

⋅

Thường trú : Xóm 1, Khu 2, Bàu Cá, Trung Hịa, Trảng Bom, Đồng Nai

⋅


Tạm trú : 497/1C Sư Vạn Hạnh, P.12, Q.10, Tp.HCM

⋅

Dân tộc : Kinh

⋅

Điện thoại : 0903.382. 466

Tôn giáo: Khơng
Email:

2. Q trình đào tạo:
⋅

1997-2000: Trường Phổ Thơng Năng Khiếu – Đại học Quốc Gia
Tp.HCM (chuyên Toán).

⋅

2000-2005: Đại Học Bách Khoa – Đại học Quốc Gia Tp.HCM. Khoa
Điện-Điện Tử - Chuyên ngành Điện Tử - Viễn Thông.

⋅

2005-2007: Đại Học Bách Khoa – Đại học Quốc Gia Tp.HCM. Cao
học ngành Kỹ thuật Điện tử.

3. Q trình cơng tác

12/2005: Cơng ty Cổ phần tin học HPTvietnam corperation


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

LỜI GIỚI THIỆU
Các phương pháp Monte Carlo là một lớp các thuật toán để giải quyết nhiều bài tốn trên
máy tính theo kiểu không xác định, thường bằng cách sử dụng các số ngẫu nhiên (thường là
các số giả ngẫu nhiên). Một ứng dụng cổ điển của phương pháp này là việc tính tích phân
xác định, đặc biệt là các tích phân nhiều chiều với các điều kiện biên phức tạp, một số ứng
dụng khác trong các lĩnh vực khoa học kỹ thuật ứng dụng như xử lý tín hiệu trong hệ thống
thơng tin viễn thơng.
Phương pháp Monte Carlo có một vị trí hết sức quan trọng trong vật lý tính tốn và nhiều
ngành khác, có ứng dụng bao trùm nhiều lĩnh vực, từ tính tốn trong sắc động lực học lượng
tử, mơ phỏng hệ spin có tương tác mạnh, đến thiết kế vỏ bọc nhiệt hay hình dáng khí động
lực học đến xử lý tín hiệu trong điện tử viễn thơng. Các phương pháp này đặc biệt hiệu quả
khi giải quyết các phương trình vi-tích phân; ví dụ như trong mơ tả trường bức xạ hay trường
ánh sáng trong mơ phỏng hình ảnh 3 chiều trên máy tính, có ứng dụng trong trò chơi điện tử,
kiến trúc, thiết kế, phim tạo từ máy tính, các hiệu ứng đặc biệt trong điện ảnh, hay trong
nghiên cứu khí quyển, và các ứng dụng nghiên cứu vật liệu bằng laser...
Trong toán học, thuật toán Monte Carlo là phương pháp tính bằng số hiệu quả cho nhiều bài
tốn liên quan đến nhiều biến số mà khơng dễ dàng giải được bằng các phương pháp khác,
chẳng hạn bằng tính tích phân. Hiệu quả của phương pháp này so với các phương pháp khác
tăng lên khi số chiều của bài toán tăng. Phương pháp Monte-Carlo cũng được ứng dụng cho
nhiều lớp bài tốn tối ưu hóa, như trong ngành tài chính.
Phương pháp Monte Carlo được thực hiện hiệu quả hơn với số giả ngẫu nhiên, thay cho số
ngẫu nhiên thực thụ, vốn rất khó tạo ra được bởi máy tính, đặc biệt là hiệu quả rất cao trong
xử lý tín hiệu. Các số giả ngẫu nhiên có tính xác định , tạo ra từ chuỗi giả ngẫu nhiên có quy

luật, có thể sử dụng để chạy thử, hoặc chạy lại mô phỏng theo cùng điều kiện như trước. Các
số giả ngẫu nhiên trong các mô phỏng như xử lý tín hiệu chỉ cần tỏ ra "đủ mức ngẫu nhiên",
nghĩa là chúng theo phân bố đều hay theo một phân bố định trước, khi số lượng của chúng
đủ lớn.
Phương pháp Monte Carlo thường thực hiện lặp lại một số lượng rất lớn các bước đơn giản,
song song với nhau; một phương pháp phù hợp cho máy tính. Kết quả của phương pháp này
càng chính xác (tiệm cận về kết quả đúng) khi số lượng lặp các bước càng tăng.
Luận văn sẽ trình bày các phương pháp Monte Carlo ứng dụng vào xử lý tín hiệu. Trong đó
tập trung vào 2 phương pháp: Markov Chain Monte Carlo (MCMC) methods và
Sequential Monte Carlo (SMC) methods và ứng dụng của chúng trong các vấn đề xử lý
tín hiệu như: ứng dụng trong mơ hình cân bằng mù (blind equalization), ứng dụng trong giải
chập chuỗi xung (deconvolution of impulsive sequence) , ứng dụng trong optimal filtering và
ứng dụng trong neural networks,...Để đánh giá được hiệu quả các phương pháp này, luận
văn sẽ tiến hành mơ phỏng trên Matlab và giả lập mơ hình xử lý tín hiệu trên kit DSP
TMS320C6711. Qua đó, so sánh và đánh giá ưu khuyết điểm các phương pháp, đưa ra nhận
xét các kết quả thu được và hướng phát triển của đề tài.

Lời Giới Thiệu

ii

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

Nội dung luận văn bao gồm 5 phần:
-


Phần I: Xử Lý Tín Hiệu Model-Based Và Các Mơ Hình Dynamic Systems gồm 2
chương
o Chương 1: Xử Lý Tín Hiệu Model-Based trình bày các vấn đề xử lý tín hiệu
mơ hình cơ bản như cân bằng mù, giải chập chuỗi xung, phân tích phổ,…
o Chương 2: Các Mơ Hình Dynamic Systems trình bày các vấn đề về mơ hình
khơng gian-trạng thái gồm các mơ hình khơng gian trạng thái phi tuyến, mơ
hình khơng gian-trạng thái trộn giữa phi tuyến và tuyến tính, mơ hình khơng
gian-trạng thái tuyến tính, …

-

Phần II: Phương Pháp Monte Carlo Và Ứng Dụng gồm 5 chương
o Chương 3: Tổng Quan Về Phương Pháp Monte Carlo trình bày tổng quan
về phương pháp Monte Carlo, các phương pháp Monte Carlo cổ điển, các
phương pháp lấy mẫu, …..
o Chương 4: Phương Pháp Markov Chain Monte Carlo trình bày về phương
pháp MCMC, các thuật tốn Metropolis-Hastings, thuật toán MetropolisHastings one-at-time và bộ lấy mẫu Markov tổng quát, bộ lấy mẫu Gibb
sampler, thuật toán Reversible jump MCMC,..
o Chương 5: Ứng dụng Markov Chain Monte Carlo trình bày ứng dụng của
phương pháp MCMC ứng dụng trong cân bằng mù với thuật toán lấy mẫu
single-site Gibbs sampler, thuật toán Block Gibb sampler, Data Augmentation
… và ứng dụng trong giải chập chuỗi xung với các thuật toán Gibbs
sampler+MH steps, thuật toán collapsed Gibbs samplers,… cũng như ứng
dụng Reversible jump MCMC vào lựa chọn mơ hình Bayesian và ứng dụng
Reversible jump MCMC simulated annealing.
o Chương 6: Phương Pháp Sequential Monte Carlo trình bày các phương pháp
SMC, thuật tốn SIR, bộ lọc particel filter (PF), các bộ lọc marginalized
particle filter, thuật tốn particle smoother và thuật tốn particle smoother
thích nghi.

o Chương 7: Ứng dụng Sequential Monte Carlo trình bày bộ lọc tối ưu (ứng
dụng SIR), bộ lọc trộn Kalman filter đối với mơ hình khơng gian trạng thái
Gaussian tuyến tính, bộ lọc Gauss, bộ lọc Cost-reference, bộ lọc RBPF đối với
mạng Bayesian động, bộ lọc Kalman mở rộng, bộ lọc Unscented particle
filter, ứng dụng SMC với MCMC step trong lựa chọn mơ hình Bayesian.
- Phần III: Mơ Phỏng Phương Pháp Monte Carlo Trong Xử Lý Tín Hiệu Và Một
Số Ứng Dụng Khác gồm 3 chương
o Chương 8 : Mô Phỏng MCMC thực hiện mơ phỏng các thuật tốn trong
phương pháp MCMC gồm mô phỏng BER ứng dụng trong bộ cân bằng mù
MCMC với kênh truyền fading, mơ phỏng thuật tốn reversible jump MCMC
ứng dụng trong lựa chọn mơ hình Bayesian với detect tín hiệu và robot data
arm, và mơ phỏng thuật tốn reversible jump MCMC simulated annealing.
o Chương 9 : Mơ Phỏng SMC thực hiện mô phỏng phương pháp SMC ứng
dụng vào blind detection trong kênh truyền fading, mô phỏng RBOF đối với
mơ hình Gauss và mạng Bayesian động, tiến hành mơ phỏng bộ lọc Kalman
mở rộng với thuật tốn cực đại kỳ vọng(EM_expectation maximum)_phương

Lời Giới Thiệu

iii

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

pháp HySIR, ứng dụng EKF vào các vấn đề price call option, ứng dụng
Unscented paticle filter,….

o Chương 10: Đánh Giá Kết Quả Mô Phỏng trình bày kết quả đã mơ phỏng
được từ các phương pháp Monte Carlo trên, so sánh với kết quả thực trong lý
thuyết và thông qua kết quả mô phỏng đánh giá hiệu suất thực hiện của các
phương pháp cũng như khả năng ứng dụng các phương pháp MCMC và SMC
cùng các thuật toán cụ thể vào một số vấn đề như xử lý tín hiệu, huấn luyện
mạng neuron network và ứng dụng thực tiễn vào thống kê kinh tế,….
-

Phần IV: Mơ Hình Hóa Phương Pháp Monte Carlo Trên DSP gồm 4 chương
o Chương 11: Tổng Quan Về Kit DSP Texas InTrusment TMS320C6711
trình bày tổng quan về kit DSP TMS320C6711 gồm sơ đồ hệ thống của kit
DSP, cấu trúc và các thành phần của C6711 như bộ nhớ, tổ chức tập lênh,
CPU, định địa chỉ, ngắt, các thanh ghi …. Chương này cũng trình bày mơ hình
thí nghiệm trên kit DSP đáp ứng cho việc thực hiện mơ hình hóa cho các
phương pháp MCMC và SMC trên kit TMS320C6711..
o Chương 12: Mơ Hình Hóa MCMC thực hiện mơ hình hóa phương pháp
MCMC trên kit DSP TMS320C6711 ứng dụng vào bài tốn tính tốn hiệu suất
BER trong bộ cân bằng mù MCMC trong kênh truyền fading. Phần này lấy kết
quả thu được từ file kết quả tập tin.log, sau khi đã thực thi file chương trình mơ
hình hóa (đã qua trình biên dịch Code Composer Studio v3.2) trên DSP
TMS320C6711 và xử lý kết quả trên excel, đưa vào Matlab để mô phỏng trên
đồ thị. Dựa vào kết quả đồ thị BER thu được, ta so sánh kết quả thu được khi
mô hình hóa trên DSP so với kết quả mơ phỏng Matlab và kết quả trong lý
thuyết
o Chương 13: Mơ hình Hóa SMC thực hiện mơ hình hóa phương pháp SMC
ứng dụng vào bài tốn tính BER trong máy thu SMC trong kênh fading, so
sánh kết quả thu được khi mô hình hóa với kết quả trên mơ phỏng Matlab và
kết quả lý thuyết.
o Chương 14 : Đánh Giá Kết Quả Mơ Hình Hóa Trên DSP trình bày các kết
quả thu được từ việc mơ hình hóa các phương pháp MCMC và SMC trên kit

DSP, so sánh các kết quả và đánh giá khách quan hiệu suất thực hiện trên kit
DSP so với kết quả mô phỏng trên Matlab và trong lý thuyết.

-

Phần V: Kết Luận và Hướng Phát Triển gồm 2 chương
o Chương 15: Kết Luận trình bày những vấn đề đã làm được, những hạn chế về
các phương pháp Monte Carlo, các phương pháp MCMC, SMC với các thuât
toán và ứng dụng trong xử lý tín hiệu và ứng dụng trong một số vấn đề khác.
Phần này cũng đánh giá kết quả thực hiện mô phỏng trên Matlab của các
phương pháp và q trình thực hiện mơ hình hóa các phương pháp trên kit
DSP TMS320C76711, qua đó so sánh các phương pháp với nhau.

o Chương 16: Hướng Phát Triển trình bày những hạn chế của các phương
pháp Monte Carlo và mở rộng các phương pháp này ứng dụng vào các vấn đề
khác, đưa ra hướng phát triển đề tài với việc ứng dụng các phương pháp vào
các mơ hình hỗn hợp và ứng dụng các ưu điểm của các phương pháp phù hợp
trong từng ứng dụng cụ thể.
Lời Giới Thiệu

iv

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

ABSTRACT

In many areas of signal processing, the trend of addressing problems with increased
complexity continues. This is best reflected by the forms of the models used for describing
phenomena of interest. Typically, in these models the number of unknowns that have to be
estimated is large and the assumptions about noise distributions are often non-tractable for
analytical derivations. One major reason that allows researchers to resolve such difficult
problems and delve into uncharted territories is the advancement of methods based on Monte
Carlo simulations including Markov chain Monte Carlo sampling methods and Sequential
Monte Carlo methods.
The aim of this thesis is to provide the basic knowledge of these methods and apply into
signal processing: sample and/or maximize high-dimensional probability distributions,
perform likelihood for complex non-Gaussian signal processing problems, applications for
blind equalization, deconvolution of impulse sequences and optimal filtering, neural
networks ….To evaluate these methods, we has simulated them by using Matlab and
modelled them on DSP kit. After that, will compare advantages and disadvantages between
Monte Carlo methods, then elaborate on the most recent advances in the field and improve
the applications of these methods into many other areas.

TÓM TẮT
Nhu cầu xác định các vấn đề cần thiết trong xử lý tín hiệu ngày càng gia tăng mạnh mẽ. Điều
này được thể hiện qua các mô hình dùng để mơ tả các hiện tượng được quan tâm trong xử lý
tín hiệu. Đặc trưng trong các mơ hình này là số ẩn chưa biết cần được đánh giá là tương đối
lớn và những giả định đối với các phân bố nhiễu là rất khó kiểm sốt khi phân tích chi tiết.
Một nguyên nhân chính cho phép các nhà nghiên cứu tiếp tục giải quyết các vấn đề khó khăn
này và nghiên cứu đào sâu các vấn đề chưa được nghiên cứu trước đó là sự phát triển của các
phương pháp mô phỏng Monte Carlo gồm các phương pháp Markov Chain Monte Carlo và
Sequential Monte Carlo.
Luận văn sẽ trình bày tổng quan các vấn đề cơ bản các phương pháp Monte Carlo và ứng
dụng chúng trong xử lý tín hiệu như: lấy mẫu và/hoặc cực đại phân bố xác suất highdimensional, tính tốn likelihood đối với xử lý tín hiệu complex non-Gaussian, ứng dụng
trong cân bằng mù, deconvolution chuỗi xung và optimal filtering, neural networks….Để
đánh giá các phương pháp này, luận văn tiến hành mô phỏng trên Matlab và mơ hình hóa

trên kit DSP. Thơng qua đó sẽ so sánh các ưu khuyết điểm của các phương pháp với nhau, và
nói thêm về các ứng dụng gần đây của Monte Carlo trong xử lý tín hiệu cũng như hướng
phát triển các phương pháp này ứng dụng trong các lĩnh vực rộng lớn hơn.

Tóm tắt luận văn

1

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

Nội dung luận văn bao gồm 5 phần:
-

Phần I: Xử Lý Tín Hiệu Model-Based Và Các Mơ Hình Dynamic Systems gồm 2
chương
o Chương 1: Xử Lý Tín Hiệu Model-Based
o Chương 2: Các Mơ Hình Dynamic Systems

-

Phần II: Phương Pháp Monte Carlo Và Ứng Dụng gồm 5 chương
o Chương 3: Tổng Quan về Phương Pháp Monte Carlo
o Chương 4: Phương Pháp Markov Chain Monte Carlo
o Chương 5: Ứng dụng Markov Chain Monte Carlo
o Chương 6: Phương Pháp Sequential Monte Carlo

o Chương 7: Ứng dụng Sequential Monte Carlo

-

Phần III: Mô Phỏng Phương Pháp Monte Carlo Trong Xử Lý Tín Hiệu Và Một Số
Ứng Dụng Khác gồm 3 chương
o Chương 8: Mô Phỏng MCMC
o Chương 9: Mô Phỏng SMC
o Chương 10: So Sánh Các Phương Pháp Và Đánh Giá

-

Phần IV: Mơ Hình Hóa Phương Pháp Monte Carlo Trên DSP gồm 4 chương
o Chương 11: Tổng Quan Về KIT DSP Texas InTrusment C6711
o Chương 12: Mơ Hình Hóa MCMC
o Chương 13: Mơ hình Hóa SMC
o Chương 14 : So Sánh Các Phương Pháp và Đánh Giá

-

Phần V: Kết Luận và Hướng Phát Triển gồm 2 chương
o Chương 15: Kết Luận
o Chương 16: Hướng Phát Triển

Tóm tắt luận văn

2

HV : Nguyễn Phan Thanh Bửu



MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

PHẦN I
XỬ LÝ TÍN HIỆU MODEL-BASED
VÀ CÁC MƠ HÌNH DYNAMIC SYSTEMS
CHƯƠNG I
XỬ LÝ TÍN HIỆU MODEL-BASED
Trong xử lý tín hiệu thống kê, nhiều vấn đề có thể trình bày hệ thống như sau.
Ta quan tâm đến việc thu được các ước lượng các biến ngẫu nhiên X của đối tượng nhận
được từ các giá trị của tập hợp χ cho bởi mối quan hệ của các đối tượng thỏa mãn quan hệ
thống kê Y=y. Trong model-based, ta quan tâm đến hàm likelihood cho bởi xác suất hoặc
hàm mật độ xác suất (probibality density function_pdf) p(y|x) của Y bằng y tại X=x. Trong
trường hợp này, theo lý thuyết chuẩn, ước lượng của X được tính theo ước lượng cực đại
likelihood (maximum likelihood_ML):
(1.1)
X = arg max p ( y | x )
ML

x∈χ

Vấn đề càng rõ ràng hơn khi ứng dụng tính tốn Bayesian inference. Trong đó, nó thiết lập
phân bố ưu tiên (prior) trên X (gọi là p(x)) và tất cả các (Bayesian) inference dựa vào phân
bố ưu tiên cho bởi định lý Bayes :
p(x | y) =

Với


p( y | x) p( x)
p( y)

(1.2)

∫ p( y | x) p( x)dx = p( y )

Cho ví dụ, ước lượng minimum mean-square error (MMSE) của X với Y=y được xác định
bởi:
x M M SE =

∫ xp ( x | y )dx

(1.3)

Chú ý: ta ký hiệu zi:j = {zi,zi+1,…..,zj } cho tất cả các chuỗi zn

1. 1 Cân bằng mù
Xét 1 chuỗi nhị phân độc lập b2:L:T ( bk = ±1 ) qua 1 kênh đáp ứng xung hữu hạn h=(h0, h1,…,
hL-1)T và đối tượng trong nhiễu Gauss với variance (phương sai) σ 2 , nghĩa là:
L −1

(1.4)

yn = ∑ hk bn − k + vk = hT bn − L +1:n + vn
k =0

i .i . d .

Với vk ∼ N (0, σ 2 ) . Cho trước 1 tập đối tượng y1:T , chúng ta quan tâm đến ước lượng chuỗi

nhị phân chưa biết b2− L:T khi h và σ 2 đã biết, hàm likelihood p ( y1:T | b2− L:T , h, σ 2 ) được cho
bởi:
p ( y1:T | b2− L:T , h, σ 2 ) ∝ exp(−
Tóm tắt luận văn

3

T

1
2σ

2

∑(y
n =1

n

− hT bn − L +1:n ) 2 )

(1.5)

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG


Trong trường hợp này để cực đại hóa likelihood p ( y1:T | b2 − L:T , h, σ 2 ) đối với b2− L:T , ta dùng giải
thuật Vertebi. Khi đã biết các thơng số (h, σ 2), nó được dùng để ước lượng ( b2− L:T ,h, σ 2)
bằng cách cực đại joint likelihood của chúng nhằm đạt được ước lượng joint maximum
2
2
) bởi vì khi T → ∞ thì ( hJML , σ JML
likelihood (JML) (b2− L:T , JML , hJML , σ JML
) sẽ không hội tụ về giá
trị thực của chúng. Một ước lượng chuẩn các thông số (h, σ 2 ) bằng cách cực đại marginal
likehood là:

p( y1:T | h,σ 2 ) = ∑ p( y1:T | b2−L:T , h,σ 2t)

(1.6)

b2−LT
:

1.2 Giải chập chuỗi xung
Xét một mô hình đơn giản các đối tượng được cho bởi phương trình (2.7). Tuy nhiên trong
trường hợp này b2− L:T khơng là một chuỗi các symbols nhị phân nữa mà là:
(1.11)

i .i . d .

bk ∼ λ N (0, σ b2 ) + (1 − λ )δ 0

Nghĩa là với xác xuất 1 − λ , ta có bk=0 và ngược lại nếu nó có phân bố theo N (0, σ b2 ) . Mơ
hình này có ứng dụng số trong lĩnh vực vật lý và khoa học hạt nhân. Chỉ cần sư thay đổi đơn
giản tính chất của bk sẽ làm vấn đề trở nên khó khăn hơn. Trong hầu hết các ứng dụng, ta

quan tâm đến việc xác định thay đổi khi 1 xung xuất hiên ở thời điểm k, nghĩa là nếu
bk ∼ N (0, σ b2 ) hoặc bk=0. Để làm được điều này, ta tạo một tập hợp i.i.d. (indepentdent
identically distributed) tương ứng với giá trị i2− L:T với ik chỉ nhận 2 giá trị tùy ý, có thể là
{0,1},
Pr(ik=1)=1-Pr(ik=0)=λ và

(1.12)

bk | ik = 0 ∼ δ 0 , bk | ik = 1 ∼ N (0, σ b2 )

1.3 Phân tích phổ
Xét vấn đề ước lượng một số nhiễu hình sin (sinusoids). Cho y 1:T là một vector đối tượng
của T mẫu data thực. Các phần tử của y 1:T được thể hiện trong các mơ hình khác nhau Mk
tương ứng với hoặc các mẫu của nhiễu (k=0) hoặc k ( k ≥ 1 ) đường sin chồng chập sai lệch do
nhiễu
Ta có :
M 0 : yn = vk ,n

k=0

k

M k : yn = ∑ (ac j ,k cos[ω j ,k n] + as j ,k sin[ω j ,k n]) + vk ,n

(1.17)
k ≥1

j =1

Với


ωj ,k ≠ωj ,k
1

2

đối với j1 ≠ j2 và

ac j ,k

asj,k ω

j ,k

lần lượt là biên độ và tần số góc của

thành phần sin thứ j tương ứng đối với mô hình k thành phần sin. Chuỗi nhiễu v1:T ,k được giả
định là nhiễu zero-mean white Gauss của variance σ k2 . Với dạng vecto ma trận là:
y1:T = D (ωk ) ak + v1:T , k

Tóm tắt luận văn

4

(1.18)

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS


THD : PGS.TS LÊ TIẾN THƯỜNG

CHƯƠNG II
CÁC MÔ HÌNH DYNAMIC SYSTEMS
Hầu như các lớp mơ hình tổng qt được xem xét là stochastic differential-algebraic
equation (SDAE). Tuy nhiên phần lớn các mơ hình hiện tại được sử dụng trong xử lý tín hiệu
và điều khiển tự động là các mơ hình state-space, xác định là một trường hợp đặc biệt quan
trọng của mơ hình SDAE.
Cơng thức tổng qt của một mơ hình được cho bởi:

F(z(t), z(t), u(t),θ , t) = 0

(2.1)

với dấu “.” tượng trưng cho các thời gian w.r.t khác nhau, z là vector internal varible, u đặc
trưng cho tín hiệu ngồi, θ đặc trưng cho một vector thông số time-invariant và t là thời
gian. Cuối cùng dynamics được mô tả bởi hàm possibly nonlinear F, là một phương trình
differential-algebraic equation (DAE).
Mơ hình 1: Mơ hình SDAE
Mơ hình nonlinear SDAE được cho bởi:
F ( z (t ), z (t ), u (t ), w(t ), θ , t ) = 0

(2.4)

z (t ) = f ( z (t ), u (t ), w(t ), θ , t )

với wt và e(tk) là stochastic process

2.1 Mơ hình khơng gian-trạng thái

Mơ hình hệ thống là dynamic model mơ tả tiến trình của các biến trạng thái(state variables)
theo thời gian. Đặc tính cơ bản của mơ hình hệ thống là Markov property
Markov property: Một process discrete-time stochastic {xt } được nói là đã process Markov
property nếu:
(2.6)
p ( xt +1 | x1 ,..., xt ) = p( xt +1 | xt )

Điều này nghĩa là thực hiện process tại thời điểm t bao gồm tất cả thơng tin trước đó, cần
thiết để tính tốn những behaviour tương lai trong hệ thống. Vì vậy nếu thực hiện process
hiện tại đã biết, thì tương lai sẽ khơng phụ thuộc vào q khứ. Đặc tính này đôi khi giống
như nguyên lý generalized causality (nhân quả), tương lai sẽ được dự đốn (predict) từ hiện
tại. Mơ hình system model có thể được mơ tả như sau:
xt +1 ∼ pθ ( xt +1 | x1 ,..., xt ) = pθ ( xt +1 | xt )

(2.7)

Mơ hình 2 (Mơ hình HMM)
Mơ hình HMM được xác định bởi
xt +1 ∼ pθ ( xt +1 | xt )
yt ∼ pθ ( yt | xt )

(2.11)

với θ biểu thị cho thơng số static parameter

Tóm tắt luận văn

5

HV : Nguyễn Phan Thanh Bửu



MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

Mơ hình khơng gian trạng thái phi tuyến
Phần chính của đoạn này là giới thiệu các mơ hình nonlinear, non-Gaussian state-space
models. Nó cũng chỉ ra rằng mơ hình kết quả thực sự là một trường hợp đặc biệt discretetime của Model 1. Các giả định của explicit cho cả system model và measurent model
trong kết quả (2.11) :
xt +1 = f ( xt , wt , θ , t )

(2.12)

yt = h( xt , et ,θ , t )

với wt và et là các biến độc lập ngẫu nhiên (independent random variables), phổ biến
như process noise và measurent noise tương ứng.
Mơ hình 3 (Nonlinear state-space model with additive noise)
Mơ hình nonlinear, discrete-time state-space với additive noise được cho như
sau
xt +1 = f ( xt , θ , t ) + wt

(2.13)

yt = h( xt , θ , t ) + et

với wt và et được giả sử là process noise độc lập lẫn nhau
Mơ hình 4 (Nonlinear state-space model with affine parameters)
Một mơ hình nolinear state-space model với các thơng số affine được xác định

bởi:
xt +1 = f1 ( xt , ut , t )θ + f 2 ( xt , ut , t )θ + wt

(2.19)

yt = h1 ( xt , ut , t )θ + h2 ( xt , ut , t )θ + et

với wt ∼ N (0, Qt ) và et ∼ N (0, Rt ) là các chuỗi nhiễu white (white noise
sequences)

2.2 Linear Differential-AlgeBraic Equations
Mơ hình6 (Linear stochastic differential-algebraic equation model )
Mơ hình linear stochastic differential-algebraic equation model được cho bởi:
E (θ ) z (t ) + F (θ ) z (t ) = Bw (θ ) w(t )

(2.25)

y (tk ) = C (θ ) z (tk ) + e(tk )

với E(θ ) phải singular và wt và e(tk) là Gausssian noise
Nguyên nhân cho việc tổng hợp white noise trong linear DAEs là nó mở rộng cho các
phương pháp chuẩn của statistical signal processing (xử lý tín hiệu thống kê). Đặc biệt hơn,
nó cho phép systematic treatment của 2 vấn đề estimating các biến internal variables z(t) và
các static parameters θ. Tuy nhiên, các mơ hình thu được từ object-oriented modelling
languages thì hầu như là continuous-time, hơn nữa là chuyển đổi yêu cầu để có thể giới thiệu
stochastic process trong các mơ hình continuous-time DAEs models.
Tóm tắt luận văn

6


HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

PHẦN II
PHƯƠNG PHÁP MONTE CARLO VÀ ỨNG DỤNG
CHƯƠNG III
TỔNG QUAN VỀ PHƯƠNG PHÁP MONTE CARLO
3.1 Phương pháp Monte Carlo
Xét hàm mật độ xác suất (probability density function) (pdf) π (x) tại x ∈ X. Ta giả định từ
bây giờ π(x) được biết như là hằng số chuẩn hóa
(3.12)
−1

π ( x) = Z π ( x)

ở đây π đã biết nhưng hằng số chuẩn hóa

Z =

∫ π ( x ) dx

(3.13)

X

là chưa biết.

Trong tất cả các ứng dụng quan trọng, không gian X là đặc trưng có nhiều chiều (high
dimensional) X=R1000 hoặc X={0,1}1000 . Trong phương pháp Monte Carlo ta quan tâm đến
các vấn đề dưới đây:
Computing integrals : đối với mọi hàm kiểm tra ϕ : X → R ta tính được

E π (ϕ ) =

∫ ϕ ( x )π ( x ) dx

(3.14)

X

x = ( x1, x2 ) ∈ X1 x X2 ta tính phân bố biên (Marginal

Marginal distributions : Giả sử
distribution)

π ( x1 ) =

∫ π ( x , x )dx
1

2

2

(3.15)

X2


Optimization Cho π(x) ta có:

arg max π ( x) = arg max π ( x)
x∈X

x∈X

(3.16)

Integration/Optimization Cho phân bố biên (Marginal distribution) như trên ta tính được :

arg max π ( x1 ) = arg max π ( x1 )
x∈X1

x∈X1

(3.17)

3.2 Các phương pháp MC cổ điển
Ở đây chỉ trình bày ngắn gọn về phương pháp Classic MC. Nó tạo nhiều mẫu từ một phân bố
chuẩn (như uniform, Gaussian,Gamma, Poisson,..) sử dụng các kỹ thuật chuẩn. Hầu như tất
cả các kỹ thuật này đều dựa trên chuyển đổi hàm phân bố lũy tiến đảo inverse cummulative
(cummulative distribution function_cdf) và phương pháp acceptance-rejection. Phương pháp
Tóm tắt luận văn

7

HV : Nguyễn Phan Thanh Bửu



MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

cdf đảo chỉ ứng dụng cho những phân bố xác suất đơn giản biết được một cách chính xác
hơn là chỉ đến 1 hằng số bình thường. Phương pháp acceptance khơng địi hỏi nhiều về hằng
số normalizing. Tuy nhiên. Nó thì khơng hiệu quả đối với các phân bố high-dimension.

3.2.1 Acception-Rejection Method
Chúng ta quan tâm đến lấy mẫu từ π(x) ∝ π ( x ) . Ta có thể lấy mẫu từ hàm pdf khác q(x)
∝ q ( x) với π ( x ) ≤ Cq ( x ) với mọi x ∈ χ
Acception-Rejection sampling
1) Lấy mẫu một candidate x*∼q(.)
2) Lấy mẫu u ∼U[1,0] (hàm phân bố Poisson trên đoạn [0,1])
3) Nếu u ≤ π ( x* ) /(Cq ( x* )) thì trả lại giá trị x* , ngược lại trở lại bước 1
Giá trị chấp nhận candidate x*được phân bố theo π.

3.3.2 Importance sampling
Một lựa chọn cho phương pháp acceptance-rejection là importance sampling. Ở đây, ta
có thể dùng hàm phân bố xác suất q(x) ∝ q ( x) để lấy mẫu các candidate, phân bố xác
suất này được gọi là importance distribution. Tuy nhiên thay vì chấp nhận các candidate
với xác suất cho trước, tất cả các candidates được chấp nhận được gán trọng số để tạo
sự trái ngược giữa q(.) và π(.).
Thật vậy, giả sử rằng π(x) > 0 ⇒ q(x) > 0, ta có các phương trình

π(x) = ω(x) q(x)
=
ở đây


ω ( x)q ( x )
∫ ω (u)q(u)du

(3.27)

ω(.) còn được gọi importance weight xác định bởi
ω ( x) =

π ( x)
q ( x)

(3.28)

CHƯƠNG 4
MARKOV CHAIN MONTE CARLO METHODS
4.1 Giới thiệu
4.1.1 Markov Chain Monte Carlo sampling (MCMC sampling) [2] [8] [5]
Ý tưởng chính của MCMC methods là tạo các samples bằng cách thực hiện 1 ergodic
chain mà phân bố cân bằng (equilibrium distribution) của nó là desired distribution. Một
markov chain khơng theo chu kỳ (aperiodic) và tối giản (irreducible) có đặc tính hội tụ
đến 1 hàm phân bố trạng thái duy nhất (unique stationary distribution) mà không phụ
thuộc vào mẫu ban đầu hoặc số lần lặp lại j. Nếu P( x ( j ) | x ( j −1) ) là chuyển đổi kernel (
transition kernel ) của chain (mắt xích) and p(x) là desired stationary distribution, và nếu
chain thỏa mãn phương trình detailed balance dưới đây
Tóm tắt luận văn

8

HV : Nguyễn Phan Thanh Bửu



MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

p(x( j−1))P(x( j) | x( j−1)) = p(x( j))P(x( j−1) | x( j))

(4.5)

nó sẽ tạo ra các samples( sau khi hội tụ) từ stationary distribution p(x). Việc tạo các
samples từ required distribution là rất dễ dàng. Nếu 1 mẫu x * có hàm mật độ π (. | x ( j −1) )
với x ( j −1) là mẫu tạo ra cuối cùng, thì xác suất chấp nhận (accepted probability) của nó
là:
(4.6)
( j −1) *

α( x

, x ) = min(1,α0 )

4.1.2 A generalized Markov sampler
Ta có thể mơ tả generalized Gibbs sampler 1 cách tóm tắt. Sampler này tạo 1 chain (mắt
xích) trong không gian I x X, với I là tập hơp chỉ số (index) và X là tập hợp đích (target)
Giả sử G := {x(1),x(2),…} là 1 Markov chain tạo bởi Gibbs sampler chuẩn hoạt động
trong 1 không gian d chiều (d-dimensional space). Và mỗi phần tử x ∈ Rd được biểu
diễn dưới dạng {x1(j), x2(j), …xd(j)}. G’ = {x1(1), x2(1), …xd(1), x1(2), x2(2), …} có cùng phân bố
giới hạn (limiting distribution) như G nhưng khơng phải là Markov chain.
Ta có thể xét G” = [(1, x1(1)), (2, x2(2)), ….,(d, xd(1)), (1, x1(2),….} là 1 Markov chain
trong I x X. Vì thế Gibbs sampler là 1 Markov chain trong không gian I x X. Phép chiếu
(projection) của phân bố giới hạn trên X là phân bố giới hạn bắt buộc.


4.2 Metropolis-Hastings Algorithm and Gibbs sampler
Giới thiệu một candidate phân bố kernel q(.|.). Phần chính (kernel) của Metropolis-Hasting
đươc cho bởi:
K MH ( x ' | x) = α ( x ' | x) q( x ' | x)

(4.13)

+δ ( x '− x ) ∫ (1 − α (u | x)) q (u | x) du

với
α ( x ' | x) = min(1,

π ( x ')q( x ' | x)
)
π ( x)q ( x ' | x)

(4.14)

Vì các lựa chọn khả năng đối với proposal kernel q (. | .) , ta có thể sử dụng
q ( x ' | x ) = q ( x ') [independent proposal] hoặc q ( x ' | x ) = q ( x '− x ) [random walk proposal]. Thật
dễ dàng chỉ ra rằng KMH là π - reversible, nghĩa là
π ( x ') K MH ( x | x ') = π ( x) K MH ( x ' | x)

(4.15)

Điều này chứng tỏ rằng KMH chấp nhận π như là phân bố bất biến (invariant)
π ( x ') = ∫ π ( x) K MH ( x ' | x)

(4.16)


với

∫K

MH

( x | x ') = 1

(4.17)

là hàm pdf của x’. Một cách logic, ta có thể mơ phỏng realization của Markov chain chuyển
đổi kernel KMH bằng cách dùng giải thuật dưới đây

Tóm tắt luận văn

9

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

4.2.1 Metropolis-Hastings Algorithm
Khởi tạo
• Chọn ngẫu nhiên hoặc xác định x (0)
Bước lặp (Iteration) n ( n ≥ 1)
• Lấy mẫu x* ∼ q(. | x ( n −1) )

• Lấy mẫu u ∼ U [0,1]
• Nếu u ≤ α ( x* | x ( n −1) ) thì set x ( n ) = x* ; ngược lại x ( n ) = x ( n −1)

4.2.2 Gibbs sampler
Khởi tạo
• Chọn ngẫu nhiên hoặc xác định x (0) = ( x1(0) , x2(0) ,..., xP(0) )
Bước lặp n ( n ≥ 1)
• Cho i=1:P
Lấy mẫu xi( n ) ∼ π i (. | x1:( ni −)1 , xi(+n1:−P1) )
Kết thúc vòng lặp i

4.3 Reversible Jump MCMC
Xem xét trường hợp ta quan tâm đến việc lấy mẫu từ phân bố π xác định trên 1 không gian
mà là hợp của các subspace (không gian con), nghĩa là: X = ∪ ∞k =0 {k } × X k . Ta viết phân bố
này là π (k , xk ) (với xk ∈ X k ).
Đối với các vấn đề này, không thể ứng dụng thuật giải MH chuẩn để jump từ X k đến X l nếu
dim( X k ) ≠ dim( X l ) . Một giải pháp được đề xuất bởi Green gọi là reversible Jump MCMC
dựa trên một reversible constraint để chuyển đổi giữa các tập hợp { X k } khác nhau. Để jump
từ X 1 đến X 2 , ta lấy mẫu các biến phụ u ∼ q1→2 (.) và thiết lập:
(4.23)

( x2 , u2 ) = ϕ1→ 2 ( x1 , u1 )

Tương tự, để jump từ X 2 đến X 1 , ta lấy mẫu u2 ∼ q2→1 (.) và thiết lập:
(4.24)

( x1 , u1 ) = ϕ 2→1 ( x2 , u2 )

(4.25)


với q2→1 (ϕ1→2 ( x1 , u1 )) = ( x1 , u1 )
Reversible jump MCMC algorithrm
Khởi tạo
• Lựa chọn ngẫu nhiên hoặc xác định (k (0) , x (0) ) .
Bước lặp n ( n ≥ 1)
• Giả sử ta có x( n−1) = (k ( n−1) , xk( n −1) )
( n−1)

• Đưa ra một chuyển đổi từ X k
Tóm tắt luận văn

( n −1 )

10

đến X l với xác suất

pk ( n−1) →l

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

• Lấy mẫu uk

THD : PGS.TS LÊ TIẾN THƯỜNG
( n −1)

∼ pk ( n−1) →l (.)


• Đặt ( xl* , ul ) = ϕk

( n −1)

→l

( xk( n( n−−1)1) , uk ( n−1) )

• Với xác suất

min(1,

π(l, xl*)

pl→k(n−1) ql→k(n−1) (u1)

)|
π(k(n−1) , xk(n(n−−1)1) ) pk(n−1) →lqk(n−1) →l (uk(n−1) )

ϕk

( n−1)

(n−1)
→l k(n−1) k(n−1)
(n−1)
k(n−1) k(n−1)

(x


∂(x

,u

,u

)

)

|

(4.27)

đặt x ( n ) = (l , xl* ) , ngược lại x ( n ) = x ( n −1) .

4.4 Simulated Annealing for global optimization
Ta nói đến khả năng ước lượng global optimum của phân bố π bằng cách đơn giản hóa các
mẫu thu được phân bố theo nó và sử dụng kết quả (3.21)

arg max π ( x ( i ) )
{ x( i ) }

Vì tính phù hợp, phương pháp này có thể hiệu quả đối với một số trường hợp. Mặt khác nếu
phân bố tương đối diffuse, hầu như các mẫu được tập trung từ global mode. Ý tưởng đằng
sau mô phỏng annealing là lấy mẫu ở bước lặp thứ n từ phân bố target bổ sung cho bởi
phương trình (4.28) với {γ n }n≥1 là chuỗi dương tăng và lim γ n = ∞ . Đối với γ n > 1 , phân bố ở
n →∞


(4.28) sẽ tập trung hơn xung quanh global maxima hơn là phân bố π và giới hạn π ∞ sẽ tập
π . Thật vậy, giả sử 1 global
trung xung quanh nó trên tập hợp global maxima của
optimum cho bởi

xmax

sao cho với mọi x ≠ xmax thì π ( x ) < π (max)
π n ( x) =

[π ( x) \ π ( xmax )]γ n

∫ [π (u ) \ π ( x

max

γn

)] du

→ 0 khi n → ∞

(4.30)

CHƯƠNG 5
ỨNG DỤNG MCMC METHODS
5.1 Blind Equalization
Ta xem xét mơ hình mơ tả trong mục trước phần “Blind Equalization”. Ta đã thiết lập rằng
phân bố posterior p(b2− L:T | y1:T ) được cho bởi (2.6). Có 2T + L −1 xác suất đối với chuỗi nhị phân
b2− L:T . Để tính gần đúng p (b2− L:T | y1:T ) , ta trình bày các giải thuật MCMC dưới đây.

Ở đây các phân bố full conditional có thể tính được dễ dàng như phương trình dưới đây:
p (bk = 1| y1:T , b2− L:k −1 , bk +1:T ) = 1 − p (bk = 0 | y1:T , b2− L:k −1 , bk +1:T )
p (b2 − L:k −1 , bk +1:T , bk = 1| y1:T )
=
p (b2 − L:k −1 , bk +1:T , bk = 1| y1:T ) + p (b2− L:k −1 , bk +1:T , bk = 0 | y1:T )

(5.1)

Hằng số normalising chưa biết của p(b2− L:T | y1:T ) không cần thiết phải biết khi nó xuất hiện
trong cả numerator và denominator của phân bố full conditional. Một bộ Gibbs sampler lấy
mẫu từ p(b2− L:T | y1:T ) được xử lý dưới dây:
Tóm tắt luận văn

11

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

5.1.1 Thuật toán 1: Single-site Gibbs sampler
Khởi tạo
• Chọn ngẫu nhiên hoặc xác định b2(0)− L:T
Bước lặp n( n ≥ 1)
• Cho k=1:K
- Lấy mẫu bk( n ) ∼ p (. | y1:T , b2( −n )L:k −1 , bk( n+1:−1)T )
Kết thúc vòng lặp k
Đây chỉ là một bộ Gibbs sampler đặc biệt. Thay vì lấy mẫu các symbol bk tại cùng

1 thời điểm, ta có thể lấy mẫu chúng bằng các subblock có chiều dài M Để dơn
giản, giả sử rằng K = (T + L − 1) / M là một số nguyên, bao gồm cả các giải thuật
bên dưới.

5.1.2 Thuật tốn 2: Block Gibbs sampler
Khởi tạo
• Chọn ngẫu nhiên hoặc xác định b2(0)− L:T
Bước lặp n( n ≥ 1)
• Cho k = 1: K
Lấy mẫu b2( −n )L +( k −1) M :2− L + kM −1 ∼ p(. | y1:T , b2( −n )L:( k −1) M −1 , b2( −n−L1)+ kM :T )
Kết thúc vòng lặp k

5.1.3 Thuật tốn 3: Data Augmentation
Khởi tạo
• Chọn ngẫu nhiên hay xác định (h (0) , σ 2(0) )
Bước lặp n ( n ≥ 1)
• Lấy mẫu b2( −n )L:T ∼ p (. | y1:T , h ( n −1) , σ 2( n −1) ) dùng cách thức lấy mẫu ford-wardbackward
• Lấy mẫu (h ( n ) , σ 2( n ) ) ∼ p (. | y1:T , b2( −n )L:T )

5.2 Deconvolution of Impulse Sequences
Ở đây, ta xét mơ hình đã mơ tả ở phần I model-based “deconvolution of Impulse
Sequences”. Trước tiên xem xét trường hợp thông số θ là chưa biết. Chúng ta quan tâm đến
việc lấy mẫu từ p(i2− L:T , b2− L:T | y1:T ) . Một cấu trúc đơn giản sẽ được sử dụng dùng giải thuật
Gibbs sampling.

5.2.1 Thuật tốn 1: Data Augmentation
Khởi tạo

Tóm tắt luận văn


12

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

• Chọn ngẫu nhiên hoặc xác định (h (0) , σ 2(0) )
Bước lặp n( n ≥ 1)
• Lấy mẫu b2( −n )L:T ∼ p (. | y1:T , h ( n −1) , σ 2( n −1) ) dùng cách thức lấy mẫu forwardbackward.
• Lấy mẫu (h ( n ) , σ 2( n ) ) ∼ p (. | y1:T , b2( −n )L:T )

5.2.2 Thuật toán 2: Single-site Gibbs sampler
Khởi tạo
• Chọn ngẫu nhiên hoặc xác định i2(0)− L:T
Bước lặp n( n ≥ 1)
• Cho k = 2 − L : T
Lấy mẫu ik( n ) ∼ p (. | y1:T , i2( n−)L:k −1 , ik( n+1:−1)T )
Kết thúc lặp
Chain này cung cấp các mẫu {i2( n−)L:T } tiệm cận phân bố theo p (i2− L:T | y1:T ) , nếu ta
quan tâm đến các mẫu từ phân bố joint p(i2− L:T , b2− L:T | y1:T ) , ta có thể lấy mẫu từ
b2( n−)L:T ∼ p (. | y1:T , i2( n−)L:T ) dùng simulation smoother.

5.2.3 Thuật tốn 3: MCMC Algorithm (Gibbs+MH steps)
Khởi tạo
• Chọn ngẫu nhiên hoặc xác định (i2(0)− L:T , θ (0) )
Bước lặp n ( n ≥ 1)
• Cho k = 2 − L : T

Lấy mẫu ik( n ) ∼ p (. | y1:T , θ ( n −1) , i2( n−)L:k −1 , ik( n+1:−1)T )
Lấy mẫu θ * ∼ q (. | θ ( n −1) ) với xác suất
min(1,

p (i2( n−)L:T , θ * | y1:T )q(θ ( n −1) | θ * |)
)
p (i2( n−)L:T , θ ( n −1) | y1:T )q (θ * | θ ( n −1) |)

Cho θ ( n ) = θ * , ngược lại θ ( n ) = θ ( n −1) )
Không thể lấy mẫu từ p(θ | y1:T , i2− L:T ) một cách chính xác, vì vậy ta cập nhật giá trị
thông số dùng bước MH (MH step). Việc thiết kế phân bố q (. | .) sẽ gặp khó khăn.
Vì vậy một lựa chọn phù hợp là giải thuật (collapsed) Gibbs sampling.

CHƯƠNG 6
SEQUENTIAL MONTE CARLO
Phương pháp sequential Monte Carlo (hay còn gọi là phương pháp particle-phần tử) , liên
quan đến vấn đề hàm ước lượng đệ quy mật độ xác suất p(xt|Ys). Theo quan điểm của
Tóm tắt luận văn

13

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

Bayesian, p(xt|Ys) bao gồm tất cả thông tin thống kê về các trạng thái khác nhau xt, dựa trên
thông tin Ys. Hàm mật độ xác suất có thể được dùng để xác định các trạng thái khác nhau:


I ( g ( xt )) E{g ( xt ) | Ys } =

∫ g( xt ) p( xt | Ys )dxt

(6.1)

Rxn

Ý tưởng chủ chốt trong phương pháp SMC là mô tả hàm mật độ xác suất bằng 1 tập hợp các
mẫu (có thể xem như là các phần tử, vì vậy nó cịn có tên gọi là phương pháp phần tử ) và
các trọng số phụ thuộc của nó. Hàm mật độ xác suất p (xt|Ys) là tương đương gần đúng với
hàm mật độ (theo kinh nghiệm) như sau:
M

p ( xt | Ys ) ≈ ∑ q δ ( xt − x )
i =1

(i )
t

(i )
t |s

M

∑ qt(i ) = 1 ,

qt( i ) ≥ 0∀ i


i =1

(6.2)

Với δ( .) là hàm Dirac delta và q~t(i ) biểu thị cho trọng số liên hợp với phần tử xt(|is) .

6.1 Sequential Importance sampling and resampling (SIR)
Cho 1 mẫu có trọng số {x1:( in)−1 , ωn(i−)1} xấp xỉ từ π n −1 , ta xét mở rộng mỗi phần x1:( in)−1 bằng cách
lấy mẫu:
xn( i ) ∼ qn (. | x1:( in)−1 )

(6.4)

Theo đó, các trọng số của mỗi phần tử phải được update theo công thức:
ωn(i ) ∝ ωn( i−)1

π n ( x1:(in) )

(6.5)

π n −1 ( x1:( in)−1 )qn ( xn(i ) | x1:(in)−1 )
Incremental weight

với

N

∑ω
i =1


(i )
n

= 1 . Thật vậy, phương pháp này là trường hợp đơn giản của importance sampling

với importance distribution cho trước tại bước n là:
n

(6.6)

qn ( x1:n ) = μ ( x1 )∏ qk ( xk | x1:k −1 )
k =2

Thuật tốn:
Khởi tạo
• Lấy mẫu x1(i ) ∼ q1 với i = 1, 2,..., N
• Tính tốn và normalized các trọng số
ω1(i ) ∝

π 1 ( x1(i ) )

(6.14)

q1 ( x1( i ) )

Nếu ESS ({ωn(i ) }) < ngưỡng, resample {x1(i ) , ω1(i ) } để đạt được {x1( i ) , N −1}
Bước lặp n( n ≥ 2 )
• Lấy mẫu xn(i ) | xn( i−)1 ∼ qn (. | x1(:in)−1 ) với i = 1, 2,..., N
Tóm tắt luận văn


14

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

• Tính tốn và normalized các trọng số
ωn(i ) ∝ ωn( i−)1

π n ( x1:(in) )

π n −1 ( x1:( in)−1 )qn ( xn(i ) | x1:(in)−1 )

(6.15)

Nếu ESS ({ωn(i ) }) < mức ngưỡng, resample {x1:(in) , ωn(i ) } để đạt được {x1:( in) , N −1}
Để đơn giản ký hiệu, ta dùngđối với các phần tử {x1:(in) } trước khi và sau khi resampling tốt
hơn là sử dụng {x1:(in) } . Giải thuật này có độ tính tốn phức tạp theo bậc O(N).

6.2 Particle filter
Particle filtering là 1 phương pháp sequential Monte Carlo dùng trong sequential signal
processing. So với lý thuyết Bayes , nó khai thác theo nguyên lý của importance sampling.
Sự quan tâm particle filtering xuất phát (stems) từ tiềm năng (potential) của nó đối với việc
đi tiên phong giải quyết các vấn đề khó khăn của tín hiệu nonlinear và/hoặc non-Gaussian .
Ý tưởng cơ bản trong particle filtering là xấp xỉ đệ quy (recursive approximation) của các
phân bố xác suất liên quan bằng ước lượng ngẫu nhiên rời rạc (discrete random measures).
Ứng dụng đơn giản nhất của phương pháp sequential Monte Carlo methods là trong lĩnh vực

phát triển polymer (growing polymers)
Mô tả chuẩn của vấn đề particle filters được cho bởi mơ hình dynamic state-space đặc
trưng bằng state-space và observation equations

x t = f t ( x t −1 , u t )

(6.16)

y t = g t ( xt , vt )
ở đây xt là 1 vector trạng thái, ft (.) là 1 hàm chuyển đổi hệ thống (system transition
function), yt là vector của observations, gt (.) là 1 hàm ước lượng, ut and vt là các noise
vectors, and t đặc trưng cho 1 chỉ số thời gian rời rạc (discrete time index).
Phương trình đầu tiên là phương trình trạng thái, phương trình thứ 2 là phương trình ước
lượng. Giả định rằng dạng phân tích của các functions và phân bố của 2 loại nhiễu là đã
biết. Dựa trên observations yt và những giả định ở trên sẽ ước lượng được xt bằng đệ quy
(recursively).
Vấn đề chính của particle filtering là việc ước lượng ngẫu nhiên rời rạc sẽ thối hóa
(degenerates) 1 cách nhanh chóng. Chỉ sau vài samples, tất cả các particles (ngoại trừ một
vài) sẽ được gán các trọng số (weights) khơng đáng kể. Sự thối hóa (degeneracy) này dẫn
đến hiệu suất của particle filter suy giảm 1 cách đáng kể. Tuy nhiên, sự thối hóa có thể
giảm bằng cách dùng good importance sampling functions and resampling.
Resampling là 1 kỹ thuật loại ra (eliminates) các particles có trọng số nhỏ và thay thế bằng
các particles có trọng số lớn. Về nguyên lý, nó được cài đặt như sau:
1. Draw M particles, xt*(m ) từ discrete distribution χ t
2.Cho x m(t ) = xt*(m ) , và assign equal weights (1/M) tới các particles.

Tóm tắt luận văn

15


HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG

Thuật toán Particle filter
(i )

M

•

Khởi tạo các particles {x0|−1}i=1 ∼ px0 ( x0 ) và set t:=0

•

Measurement update : tính các importane weights {qt(i ) }iM=1 theo
qt(i ) = p( yt | xt(|it )−1 ) với i = 1, 2,.., M

Và normalize (chuẩn hóa) qt = qt /
(i )

(i )

∑

M


(i )
j =1 t

q

• Resampling :draw M particles, với các replacement theo biểu thức
sau:
Pr( xt(|it ) = xt(|tj−)1 ) = qt( j ) , với i = 1, 2,.., M

• Time update: predict các particle mới theo :
xt(+i )1|t ∼ p ( xt +1|t | xt(|it ) )

• Set t:=t+1 và trở lại bước 2
Resampling algorithms
Bước resampling bao gồm việc drawing một tập các particle mới {xt(|it ) }iM=1 với
replacement từ các particle trước đó {xt(|it )−1}iM=1 , trong trường hợp này
probability của drawing xt(|it )−1 được cho bởi qt(i ) theo biểu thức sau:
Pr( xt(|it ) = xt(|tj−)1 ) = qt( j ) , với i = 1, 2,.., M

Systematic sampling alogorithm
•

Generate M ordered numbers theo biểu thức:

uk =

k −1 + u
, u ∼ U (0,1)
M


•
Các resampled particles thu được bằng tạo ni copies của particle x ( i ) ,
với
i −1

i

s =1

s =1

ni = the number of uk ∈ (∑ qt( s ) , ∑ qt( s ) ]

6.3 Marginalized particle filter
Thuật toán Marginalzed particle filter
1.Khởi tạo: Khởi tạo các particle và set các giá trị khởi tạo đối với các
biến linear state variable được sử dụng trong Kalman filter.
2. Particle filter measurement update: đánh giá các trọng số quan trọng
(importance weights) và chuẩn hóa.
3. Resampling với replacement.
Tóm tắt luận văn

16

HV : Nguyễn Phan Thanh Bửu


MONTE CARLO METHODS

THD : PGS.TS LÊ TIẾN THƯỜNG


4. Particle filter time update và Kalman filter
a) Kalman filter measurement update.
b) Particle filter time update: Predict các particle mới
c) Kalman filter time update (cập nhật theo thời gian)
5. Lặp lại từ bước 2.
Chỉ có 1 điểm khác nhau duy nhất từ bộ lọc chuẩn standard particle filter là ở trong bước 4,
với 2 bước thêm được giới thiệu. Hai bước này tương ứng với efficient estimation của các
biến linear state variables dùng Kalman filter.

CHƯƠNG 7
ỨNG DỤNG SMC METHODS
7.1 Optimal filtering
7.1.1 Filtering in general state-space models
Ở đây, ta nói đến ứng dụng của phương pháp SIR trong optimal filtering. Phần này đã
được thảo luận trong phần I, mục 2.4. Trong ứng dụng này , ta quan tâm đến ước lượng
chuỗi unobserved Markov {xn }n≥1 initial density μ và transition density
xn | xn −1 ∼ f (. | xn −1 ) . Đối tượng { yn }n ≥1 độc lập với
{xn }n≥1 của marginal
density yn | xn ∼ g (. | xn ) . Trong trường hợp này chuỗi phân bố target của {π n }n≥1 được cho
bởi:
n

n

k =2

k =1

π n ( x1:n ) = p ( x1:n | yn ) ∝ μ ( x1 )∏ f ( xk | xk −1 )∏ g ( yk | xk )


(7.1)

Ta chọn q( xn | yn , xn −1 ) như một approximation của p ( xn | yn , xn −1 ) dùng bộ lọc Kazman mở
rộng (extended Kalman filter_EKF) hoặc unscented Kalman filter (UKF). Tóm lại giải
thuật SIR áp dụng cho mơ hình filtering state-space được thể hiện như dưới đây:
SIR cho Optimal Filtering
Khởi tạo
• Lấy mẫu x1(i ) ∼ q1

với i = 1, 2,..., N

• Tính tốn và normalized các trọng số
ω1( i ) ∝

μ1 ( x1(i ) ) g ( y1 | x1( i ) )
q ( x1(i ) | y1 )

• Nếu ESS ({ωn(i ) }) < mức ngưỡng, resample {x1( i ) , ω1(i ) } để đạt được
{x1(i ) , N −1}

Bước lặp n( n ≥ 1)
• Lấy mẫu xn(i ) ∼ qn (. | y y , xn(i−)1 ) với i = 1, 2,..., N
• Tính và normalized các trọng số
Tóm tắt luận văn

17

HV : Nguyễn Phan Thanh Bửu