Báo Cáo Phương pháp ước lượng xác suất thứ cấp dựa trên lý thuyết entropy cực đại trong ứng dụng nén dữ liệu

PHưƠNG PHÁP ưỚC LưỢNG XÁC SUẤT THỨ CẤP DỰA TRÊN
LÝ THUYẾT ENTROPY CỰC ĐẠI TRONG ỨNG DỤNG NÉN DỮ LIỆU
SECONDARY PROBABILITY ESTIMATION METHODS BASED ON MAXIMUM
ENTROPY PRINCIPLE IN DATA COMPRESSION APPLICATIONS

SVTH: Nguyễn Hải Triều Anh
Lớp 05DT1, Khoa Điện tử Viễn thông, Trường Đại học Bách khoa
GVHD: ThS. Hoàng Lê Uyên Thục
Khoa Điện tử Viễn thông, Trường Đại học Bách khoa

TÓM TẮT
Mô hình hóa dữ liệu và mã hóa là hai quá trình quan trọng nhất của nén dữ liệu. Mã hóa
được thực hiện tối ưu và hiệu quả với mã hóa số học. Tuy nhiên không thể tính toán mô hình tối
ưu cho một nguồn dữ liệu cho trước. Bài báo sẽ giới thiệu phương pháp ước lượng xác suất thứ
cấp. Trong đó mỗi mô hình sơ cấp ước lượng xác suất bit tiếp theo là bit 1 hoặc bit 0 một cách độc
lập. Các xác suất ước lượng được kết hợp lại với nhau bằng phương pháp tương tự như mạng
nơtron. Sau khi bit được mã hóa, bộ ước lượng được cập nhật theo hướng tối thiểu chi phí mã
hóa thay vì theo hướng giảm sai số dự đoán.
ABSTRACT
Data modeling and coding is two most important processes of data compression. An
optimal and effective coding process can be implemented using arithmetic coding. However,
optimal model is not computable. This paper introduces a secondary probability estimation method.
In this method, each primary model independently estimates the probability that the next bit of data
is 0 or 1. Results of estimation are combined by using a method similar to a neural network. After a
bit is coded, the estimator will be updated in the direction that minimizes coding cost instead of the
direction that minimizes mean square error.
1. Đặt vấn đề
Nén dữ liệu là biện pháp nhằm giảm số bit cần dùng để lưu trữ hoặc truyền dữ liệu.
Các thuật toán nén có hai quá trình thiết yếu nhất là quá trình ước lượng phân bố xác suất
và quá trình mã hóa. Người ta đã chứng minh được rằng không thể tìm ra ước lượng phân
bố xác suất tối ưu cho một nguồn cho trước [1][2]. Tuy nhiên quá trình mã hóa có thể được
thực hiện hiệu quả và tối ưu với mã hóa số học [3]. Độ dài từ mã trung bình mà bộ mã hóa
tạo ra bị giới hạn bởi entropy của nguồn. Giả sử biến ngẫu nhiên x nhận giá trị thuộc tập
X={x1, x2, }; mỗi giá trị xi có xác suất là pi, lí thuyết thông tin [4] định nghĩa entropy
của x là:
(1)
Entropy của nguồn tin được xác định nếu ta biết trước được phân bố xác suất của nguồn
đó. Tổng quát thì phân bố xác suất của nguồn là không thể biết trước đồng thời phân bố tối
ưu của nguồn là không tính toán được, vì vậy chỉ có thể thực hiện ước lượng các giá trị .
Do đó tính hiệu quả của một thuật toán nén dữ liệu phụ thuộc chủ yếu vào quá trình ước
lượng xác suất. Mặt khác để ước lượng xác suất của sự kiện xi người ta có thể sử dụng
nhiều phương pháp, nhiều cách tiếp cận khác nhau. Bài toán đặt ra là thực hiện kết hợp ước
lượng xác suất từ các bộ ước lượng sơ cấp để tạo ra phân bố xác suất thích hợp nhất nhằm
mã hóa nguồn tin hiệu quả nhất.
2. Phương pháp kết hợp dựa trên lí thuyết entropy cực đại
2.1. Cơ sở lí thuyết
Ta xét biến ngẫu nhiên x nhận giá trị thuộc tập X={x1, x2, , xn}. Xác suất ước
lượng của xi với từ m bộ ước lượng sơ cấp khác nhau là , với . Xác
suất ước lượng tại đầu ra của bộ kết hợp là .
Các điều kiện ràng buộc của [5]:
- Entropy: (2)
- Kì vọng của các xác suất sơ cấp: (3)
- Mặt khác phải thỏa mãn: (4)
Áp dụng phương pháp số nhân Lagrange với các điều ràng buộc như trên. Định
nghĩa các hằng số , ( ) và hàm Lagrange L:
(5)
Lý thuyết entropy cực đại dựa trên tiền đề là khi ước lượng phân bố xác suất với
các ràng buộc cho trước ta nên chọn phân bố có entropy cực đại [5][6]. Có nghĩa là tìm ,
( ), và ( ) sao cho L lớn nhất [5]. Tức là xác suất tại đầu ra
phải thỏa mãn điều kiện và các điều kiện (2)(3)(4). Suy ra:
(6)
Các giá trị có thể được xác định bằng phương pháp lặp tổng quát và đảm bảo sẽ
hội tụ đến nghiệm duy nhất [6].
Dựa vào công thức (6) ta thấy: để có thể kết hợp các bộ dự đoán một cách đơn giản
nhất thì các bộ dự đoán phải là các bộ dự đoán nhị phân (dự đoán từng bit). Gọi P là xác
suất bit tiếp theo là bit 1, xác suất bit tiếp theo là bit 0 là (1-P). Tương tự gọi là xác