Blog Khoa Học Máy Tính

Tôi muốn giới thiệu một bài báo thú vị của David Donoho với tựa đề: The blessings and curses of dimensionality. Donoho là một siêu sao trong ngành thống kê của thập niên 90, ông cũng là một cây viết thú vị. Các bài viết của Donoho dù technical hay không, thường tạo ra nhiều cảm hứng và nhiệt tình cho người đọc. Bài báo trên của Donoho là một lời kêu gọi sự chú ý của giới làm toán nói chung hãy quan tâm hơn và đóng góp các công cụ toán học đến những vấn đề xử lý dữ liệu hóc búa của thế kỷ 21. Đọc nó, và hy vọng bạn sẽ thấy đó cũng là lời kêu gọi đến những nhà khoa học máy tính của hôm nay và ngày mai.

Những vấn đề xử lý dữ liệu không hề xa lạ với dân KHMT chúng ta. Quả thật đó cũng chính là nồi cơm của chúng ta: Làm thế nào để “make sense of” luồng dữ liệu khổng lồ trên web, trong hệ thống máy, trong các sensor networks, trong genome của người và các sinh vật khác, các loại dữ liệu ở dạng text, ảnh, âm thanh, v.v. Làm thế nào để máy tính được grounded trong data mà không bị chết sặc. Những tiến bộ trong công nghệ thông tin — communication, networking, hardware, software, data structure và algorithms — đã tạo nên một cơ sở hạ tầng tuyệt vời để thu thập và biểu hiện dữ liệu. Song chưa đủ. Xử lý luồng dữ liệu khổng lồ như thế nào lại là một chuyện phức tạp hơn nhiều. Ở thế kỷ 21, rất nhiều ngành khoa học lý thuyết, tính toán và thực nghiệm phải cùng nhau xắn tay vào để giải quyết những vấn đề như vậy.

Dân KHMT cũng không lạ gì khái niệm “curses of dimensionality” do Richard Bellman sử dụng lần đầu tiên. Curses of dimensionality nói đến sự khó khăn trong việc giải quyết các bài toán liên quan đến high dimension. Một cách cụ thể, số lượng dimension của bài toán có thể là số lượng biến số liên quan, có thể do số lượng sensors dùng để thu thập data rất lớn. Tùy theo dạng dữ liệu khác nhau mà sensors ở đây cũng nên hiểu theo nghĩa rất linh động, có thể là các routers trong một network, các cameras, các websites, các pixels của từng hình ảnh, độ dài của chuỗi DNA và protein trong sinh học phân tử, v.v. Để xử lý data với dimension khổng lồ như trên với số lượng khổng lồ đòi hỏi tìm kiếm trong một state space lớn gấp nhiều lần, có thể theo đa thức hoặc hàm số mũ (exponential). Đó chính là curses of dimensionality. Đừng vội nghĩ exponential complexity mới là tồi tệ. Nếu thuật toán của bạn scan database lần, với số dimension ở mức hàng chục triệu thì đã khó chấp nhận rồi.

Điều thú vị là high-dimension có nhiều blessings. Bạn hãy tự hỏi, tại sao con người ta luôn luôn phải đối mặt với rất nhiều sensory data (qua 7 giác quan) mà thường vẫn không bị tẩu hỏa nhập ma. Tất nhiên đây là một câu hỏi mở để ta cùng suy ngẫm. Trong toán học, một trong những yếu tố thuận lợi của high dimensions chính là khái niệm concentration of measure. Trong lý thuyết xác suất chúng ta đều biết law of large numbers: giá trị trung bình của các sự thể hiện ngẫu nhiên thường hội tụ về giá trị kỳ vọng của biến ngẫu nhiên (constant). Hay định luật central limit: Giá trị trung bình của các sự thể hiện ngẫu nhiên có hành vi giống như biến Gauss. Sâu hơn một chút, một hàm số được định nghĩa trên rất nhiều biến (high dimension), mà sự đóng góp của từng biến vào giá trị hàm số đều nhỏ, thì hàm số đó có hành vi giống như constant vậy. Kỳ thực rất nhiều hàm số mà chúng ta quan tâm trong cuộc sống đều có tính chất này. Trong hình học lồi (convex geometry), rất nhiều vật thể lồi trong high dimension thường có những tính chất phản trực quan: ví dụ một hình hộp trong không gian nhiều chiều có hình dạng rất khác một hình hộp ta biết trong 2 hay 3 chiều. Song những tính chất đó lại được tận dụng một cách hiệu quả để đưa ra những đáp án rất ngoạn mục cho các vấn đề liên quan đến high dimension.
[[Addition 04/03/07: Một quyển sách rất hay và dễ đọc giới thiệu về v/đ này: Keith Ball, Elementary introduction to convex geometry, ở đây .]]
Donoho còn liệt kê ra và dẫn chứng một số yếu tố blessings khác trong không gian nhiều chiều. Để có nó ta cần phải sử dụng các công cụ khác trong toán học.

Đây là một ví dụ của những bài báo mà khi đọc xong, tôi không khỏi cảm thấy mình thật là may mắn vì được sống trong một không gian rất nhiều chiều. Không phải vì mình đã nắm hết được hết các blessings kể trên, mà vì khả năng được tìm tòi và sử dụng các công cụ toán học đẹp đó để giải quyết các vấn đề rất thiết thực. Bring it on, your curses, dear Professor Bellman!

Chủ đề: Giới thiệu sá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ê | Bình luận (2) »

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ê | Bình luận (1) »

Prof. Richard Karp chuẩn bị dạy một lớp bậc cao học về những thuật toán quan trọng và nổi tiếng trong KHMT. Lời giới thiệu của syllabus:

From time to time a new algorithm comes along that causes a sensation in
theoretical computer science or in an area of application because of
its resolution of a long-standing open question, its surprising efficiency,
the novelty of its setting or approach, the elegance of its structure, the
subtlety of its analysis or its range of applications.

Không phải là tất cả (tất nhiên!), nhưng dây là một danh sách của Prof. Karp để ta tham khảo. Một số đã được nhắc tới đâu đó trong blog này:

• Elementary examples: Binary arithmetic, sorting, Euclidean algorithm,
  greedy algorithm, Dijkstra shortest-path algorithm, Gaussian elimination
• Simplex algorithm for linear programming (1947)
• Fast Fourier Transform (1959)
• Gale-Shapley proposal algorithm (1962)
• Edmonds’ nonbipartite matching algorithm (1965)
• Union-find algorithm (1975)
• Lattice basis reduction algorithm (1982)
• Buchberger’s Grobner basis algorithm (1982)
• Ajtai-Komlos-Szemeredi sorting network (1983)
• Randomized algorithms for approximating volume (1989)
• Koutsoupias-Papadimitriou k-server algorithm (1994)
• Shor’s quantum factoring algorithm (1994)
• The Winnow (1988) and Adaboost (1995) algorithms for statistical
  classification
• Interior-point algorithms for linear programming(1984) and semidefinite
  programming (1995)
• Streaming algorithms for computing moments (1995)
• Sudan’s list decoding algorithm (1997)
• LT codes and Raptor codes for data distribution (2002, 2003)
• Reingold’s logspace algorithm for st-connectivity (2004)

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ê | Bình luận (1) »

Bài này cũng tương tự như (có lẽ dễ hơn một chút) bài toán thổi bóng . Khác ở đây là các quả bóng đã được thổi sẵn :-), nhưng dẫu sao cũng thuộc một dạng optimal sequential decision making problem:

Giả sử có n quả bóng đã được thổi, có thể tích để trong một cái giỏ. Bạn bị bịt mắt và chỉ có thể dựa vào khả năng so sánh 2 quả bóng trong tay xem quả nào lớn hơn mà thôi. Đầu tiên, bạn sẽ nhặt hoàn toàn ngẫu nhiên một quả bóng trong giỏ. Sau đó tiếp tục như sau: Tại từng thời điểm, bạn nhặt hoàn toàn ngẫu nhiên thêm một quả trong giỏ, so sánh quả vừa nhặt và quả đang có trong tay, so sánh xem quả nào lớn/nhỏ hơn và sẽ giữ lại một quả trong số hai quả đó. Quả bóng đã bỏ đi rồi thì không được nhặt lại nữa. Hỏi làm thế nào nhặt ra được quả bóng lớn nhất (quả có thể tích 1), với xác suất cao nhất? Xác suất cao nhất ấy là bao nhiêu (khi n tiến tới vô hạn)?

Trích từ: Optimal stopping rules. A. N. Shiryayev. Springer-Verlag, 1978.

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

Nối tiếp bài viết về bài báo nổi tiếng của Shannon, tôi muốn nói về một bài báo kinh điển trong thống kê cùng giai đoạn những năm 40, có vai trò đặc biệt đến KHMT, kinh tế, và operations research, và đẻ ra cả một lĩnh vực mới trong thống kê gọi là sequential analysis. Đó là bài báo sau đây của Abraham Wald, vốn là giáo sư đại học Columbia:

Wald, A. (1945). Sequential tests of statistical hypotheses. Annal of Mathematical Statistics. 16, 117-186.

Bài báo này giới thiệu một vấn đề mới mẻ trong một trong những lĩnh vực quan trọng nhất của ngành thống kê, đó là hypothesis testing, và giới thiệu một hướng giải quyết trọn vẹn. Được thai nghén trong thời kỳ chiến tranh thế giới lần thứ 2, có lẽ Wald đã quan tâm đến những vấn đề rất cụ thể trong lĩnh vực signal processing, như radar signal detection, missile detection, và system failure detection. Chẳng hạn chúng ta có một dãy dữ liệu mà radar có thể bắt được. Chúng ta muốn biết đó là một máy bay địch hay ta, để báo động cho quân đội và dân chúng. Ta muốn ra quyết định sớm nhất có thể được, nhưng cũng hạn chế tình huống báo động giả (false alarm, nói là máy bay kẻ thù trong khi đó là máy bay của ta), cũng như hạn chế tối thiểu tình trạng detection failure (không phát hiện được đây là máy bay địch). False alarm còn được gọi là type 1 error, còn detection failure probability được gọi là type 2 error trong ngôn ngữ ngành thống kê.

Ở dạng đơn giản nhất, bài toán của Wald có thể tóm tắt như sau: Giả sử có một dãy biến ngẫu nhiên độc lập và có cùng hàm phân phối (probability distribution) là P_0 hoặc P_1: X_1, X_2,…,X_n,… Làm thế nào để biết những biến ngẫu nhiên này có hàm phân phối P_0 hay P_1 với sai số nhỏ nhất (cả có thể được mà lại tốn ít mẫu dữ liệu (data sample) nhất? Nếu bạn chỉ cho tôi m mẫu dữ liệu là X_1, X_2,…, X_m, thì vấn đề này đã hoàn toàn đã được giải quyết bằng Neyman-Pearson lemma, và qua đó ta có thể tính được số mẫu dữ liệu tối ưu m là bao nhiêu. Như vậy, lời giải của bài toán radar detection trên là, tùy thuộc vào đòi hỏi tối đa về xác suất báo động giả và xác suất không báo động kịp (type 1 and type 2 probability errors), ta có thể tính được giá trị m tối ưu, và sau khi đã có đủ m mẫu dữ liệu thì sẽ đưa ra quyết định cuối cùng. Phương pháp này gọi là fixed-sample-size test. Tuy nhiên, trên thực tế, nếu bạn là người quan sát radar signal, có lẽ bạn sẽ không chịu làm như vậỵ Nhiều khi bằng cách quan sát chuỗi dữ liệu và theo dõi cách chúng thay đổi, chúng ta có thể đưa ra quyết định chính xác và sớm hơn nhiều.

Những cảm nhận tự nhiên và đơn giản thường là đúng, nhưng phải đợi đến Wald thì mọi việc mới sáng tỏ. Quả thật quan sát này của Wald gây chấn động trong giới thống kê. Hơn nữa, Wald còn đưa ra giải pháp tối ưu cho bài toán trên, sau này đươc gọi là Wald’s sequential likelihood ratio test:

Tại từng thời điểm, sau khi nhận được tín hiệu X_i, chúng ta tính likelihood ratio u_n = P_1(X_n)/P_0(X_n). Quan sát sự biến chuyển của tổng S_n = u_1 +…+u_n, và chúng ta sẽ dừng lại khi S_n vượt ra ngoài một khoảng [A,B] thích hợp. Nếu S_n <>P_0, còn nếu S_n > B thì ta kết luận ngược lại. S_n còn gọi là random walk, và thời điểm n mà chúng ta dừng lại chính là một dạng biến ngẫu nhiên, gọi là hitting time của random walk S_n.

Phải hai năm sau, Wald và học trò của mình là Paul Wolfowitz chứng minh một cách chặt chẽ rằng phương pháp trên là tối ưu nhất. Trên thực tế, Wald’s test có thể tiết kiệm được từ một nửa đến 1/3 số mẫu dữ liệu nếu ta dùng fixed-sample-size test. Điều đáng nói là cùng thời gian đó Arrow, Blackwell và Girshick cũng xuất bản một bài báo chứng minh về tính tối ưu của Wald’s test. Đặc biệt bài báo này lần đầu tiên giới thiệu phương pháp dynamic programming, với khái niệm “cost to go” nổi tiếng, mà 8 năm sau đó được Richard Bellman tổng quát hóa lên cho Markov Decision Processes. Rất tiếc là sau này người ta thường chỉ nhắc đến Bellman với danh nghĩa là người đã sáng tạo ra thuật toán dynamic programming. Bài báo của Wald châm ngòi cho cả lĩnh vực sequential decision-making theory, được áp dụng và phát triển dưới các màu sắc và thuật ngôn khác nhau trong thống kê(sequential analysis), trong operations research (markov decision processes), và trí tuệ nhân tạo ( reinforcement learning)…

Những nhân vật liên quan đến những ngày đầu của sequential analysis đều là những tên tuổi lớn trên bầu trời khoa học. Abraham Wald được coi là một trong những nhà thống kê học lỗi lạc và có ảnh hưỏng nhất của thế kỷ 20, sánh ngang hàng với Fisher và Neyman, những người được coi là ông tổ của thống kê. Kennet Arrow, hiện vẫn là giáo sư ở Stanford, vốn là một học trò của Wald, về sau này được nhận giải Nobel vì những cống hiến trong game-theory. Còn David Blackwell, giáo sư ở Berkeley, được coi là nhà toán học vĩ đại nhất người da đen, có rất nhiều cống hiến về game theory, kinh tế và thống kê học.

Một số tham khảo khác:

Arrow, K. J., Blackwell, D. and Girshick, M. Ạ (1949). Bayes and minimax solutions of sequential decision problems. Econometrica 17, 213-244.

Wald, A and Wolfowitz, J (1948). Optimum character of the sequential probability ratio test. Annal of Math. Statistics 19, 326-339.

Bellman, R (1957). Dynamic programming. Princeton University Press.

Chủ đề: Toán tối ưu & Xác suất & thống kê | Bình luận (3) »