Blog Khoa Học Máy Tính

Làm thế nào để biểu diễn xấp xỉ một hàm số bằng các đại lượng giải tích đơn giản hơn? Đây là một câu hỏi cơ bản của lý thuyết xấp xỉ (approximation theory) . Tầm quan trọng và ứng dụng của nó rất lớn với KHMT: Hàm số ở đây có thể hiểu là các signal, các mô hình learning (thống kê), v.v những gì mà ta cần biểu diễn và estimate. Các cuộc “cách mạng” trong các ngành trong KHMT này thường được đánh dấu bởi một phương pháp xấp xỉ mới (như phương pháp waveless trong signal processing, hay neural networks và kernel methods trong machine learning, đều xảy ra trong thập kỷ 80/90).

Bài báo sau đây là một landmark paper trong approximation theory (có thể download từ Sbornik Mathematics — amazing !):

M. S. Birman and M. Z. Solomjak, Piecewise-polynomial approximations of functions in the classes , Math. USSR-Sbornik Vol. 2 (3), pages 295–317, 1967. Full text (pdf)

Không gian Sobolev bao gồm các hàm số smooth. Một chút background về không gian Sobolev có thể tìm ở đây . Chi tiết hơn thì nên đọc thêm quyển sách kinh điển của Robert Adams (title: Sobolev spaces) hoặc Second Edition.

Trước Birman và Solomjak, phần lớn lý thuyết xấp xỉ được tập trung vào phương pháp xấp xỉ tuyến tính cổ điển. Phương pháp này tập trung vào các không gian đa thức tuyến tính (như đa thức Bernstein, Fourier bases, đa thức Chebyshev, …). Bài báo của Birman và Solomjak giới thiệu và phân tích một thuật toán adaptive. Ý tưởng rất đơn giản: Chia nhỏ miền xác định của hàm số ra thành các mảnh nhỏ, và mỗi mảnh đó được xấp xỉ bằng một đa thức (dùng công cụ tuyến tính). Chỗ nào mà sự xấp xỉ chưa được tốt thì dùng các mảnh nhỏ hơn. Đặc biệt số lượng của các mảnh partition này được hạn chế tối thiểu. Vì với mỗi mảnh khác nhau của miền xác định, một không gian đa thức tuyến tính được sử dụng, kết quả là ta có một phương pháp xấp xỉ phi tuyến. Đây chính là ý tưởng căn bản của multi-resolution approximation, rất quen thuộc trong lĩnh vực xử lý ảnh hiện nay.

Sau Birman và Solomjak, những thập niên 70/80 chứng kiến sự phát triển rất nhanh về lý thuyết xấp xỉ phi tuyến. Có nhiều cộng đồng khác nhau cùng nghiên cứu về vấn đề này: Dân làm về lý thuyết xấp xỉ, lý thuyết giải tích điều hòa (harmonic analysis), dân làm về multigrid theory cho integral và differential equations, và dân làm về multiscale filterbanks trong image processing. Đến cuối thấp niên 80, những nhánh nghiên cứu này hội tụ tại cùng một điểm: kết quả là một phương pháp xấp xỉ phi tuyến hiệu quả về mặt ứng dụng, nhưng rất đẹp và elegant về mặt toán học. Đó là phương pháp xấp xỉ wavelet. Có một số chuyên gia người Việt làm về lĩnh vực này trong image processing, như các giáo sư Nguyễn Quang Trường ở UCSD, Trần Duy Trác ở John Hopkins, Đỗ Ngọc Minh ở UIUC. Ở Việt nam có nhiều chuyên gia nghiên cứu về lý thuyết xấp xỉ ở các khoa toán và tin, trước đây được đào tạo từ Soviet school của Birman, Solomjak và các vị tiền bối khác.

Bài báo của Birman và Solomjak có nhiều chi tiết technical rất thú vị:

• Thuật toán partition miền xác định của một hàm số như đã nhắc trên. Rất tổng quát, có ứng dụng trực tiếp trong việc xấp xỉ một hàm số bằng các đa thức, nhưng còn có ứng dụng trong nhiều vấn đề khác nữa. Ý tưởng và cách chứng minh thuật toán rất sơ cấp, một học sinh chuyên toán cấp 3 có thể hiểu được dễ dàng.
• Cho phép estimate -entropy và -diameters của một không gian hàm số. Đây là những khái niệm hết sức quan trọng, được dùng để định lượng độ complex của một không gian hàm số, do Kolmogorov giới thiệu. Khái niệm này không chỉ có ứng dụng trực tiếp trong lý thuyết xấp xỉ, mà còn có ứng dụng trực tiếp đến lý thuyết empirical processes trong xác suất, và statistical learning theory. Qua đó ta có thể ước lượng được số lượng data cần thiết để có thể học được một mô hình thống kê với độ chính xác nhất định.
• Các kết quả của Birman và Solomjak không chỉ giới hạn đến không gian Sobolev, mà còn được áp dụng đến các không gian khác trong giải tích có ứng dụng trực tiếp đến signal processing.

Chủ đề: Lý thuyết thông tin & Lý thuyết tính toán & Thuật Toán & Toán tối ưu & Trí tuệ nhân tạo & Xác suất & thống kê |