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 . 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 . Độ 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 đị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 :

- 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 . Có nghĩa là tìm ,

( ), và ( ) sao cho L lớn nhất . 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 .

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á