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) »

Talk của Nick Harvey (MIT), talk của Baochun Li (Toronto), talk của Yunnan Wu (Princeton). Trong đó talk của Baochun Li hay nhất.

Tôi sẽ viết tiếp chuỗi bài về lý thuyết mã mạng trong vài tuần tới.

Chủ đề: Lý thuyết thông tin & Lý thuyết tính toán & Mạng máy tính & Thuật Toán | Bình luận (4) »

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) »

Bài blog gần đây của anh Hưng nhắc đến câu chuyện với John McCarthy. Vị GS nổi tiếng này cho rằng: (…) không tin rằng common sense có gì fundamentally statistical hay probabilistic. Tôi nghĩ đây là một vấn đề thú vị — “blog-friendly” topic — nên lôi nó ra đây.

JMC là một trong những người đặt nền móng cho ngành TTNT cổ điển từ đầu thập kỷ 60. Ông là một trong những người khởi xướng việc sử dụng ngôn ngữ logic để biểu diễn và suy diễn kiến thức (knowledge) và common sense. Ý tưởng và sự ảnh hưởng của JMC thống trị giới nghiên cứu mainstream về AI trong suốt các thập kỷ sau đó. Nghiên cứu về AI liên quan chủ yếu đến số 0 và số 1 và gọi là “symbolic AI”, cho đến khi Judea Pearl xuất bản quyển sách landmark về graphical models năm 1988, và một số tác giả về cognitive science (Rumelhart, Hinton và William) nghiên cứu các mô hình neural networks cho learning. Với sự ra đời (thực ra là re-discovery) của neural nets, giống như nhiều thứ buzzwords trong KHMT và trong AI, có một dạo người ta tung hô “connectionist AI” như một câu trả lời mới cho TTNT. “Symbolic AI” bị rơi vào tình trạng defensive từ những ngày đó. Tuy nhiên ta không nên bị cuốn vào sự phân biệt non nớt giả tạo này.

Để hiểu JMC nói gì, tất nhiên ta phải đồng ý với nhau về ngôn ngữ. Trước hết, common sense là gì ? Common sense theo nghĩa thông thường, và common sense trong TTNT? Không dễ trả lời, cũng như nhiều thứ trong nghiên cứu TTNT, các khái niệm thường không có định nghĩa rõ ràng và gây tranh cãi, giống như câu hỏi “thế nào là AI” vậy. Hãy tạm đồng ý với nhau common sense là … common sense theo nghĩa hiểu của con người, đó là những mớ kiến thức căn bản thông thường trong cuộc sống, cần thiết cho sự sinh tồn và giao tiếp. Tất nhiên đây không phải là định nghĩa, nhưng có thể làm cho nó chặt chẽ hình thức hơn.

Giả sư chúng ta đồng ý với nhau về common sense rồi. Rất có thể JMC có lý, rằng khái niệm common sense (do JMC định nghĩ) không có tính chất probabilistic về bản chất. Nhưng cũng có thể JMC không đúng.

Với tôi thì common sense là khái niệm probablistic hay logical không quan trọng. Câu hỏi quan trọng mà tôi quan tâm là: Common sense có phải là khái niệm hữu ích hay không trong việc xây dựng máy tính thông minh? Cụ thể hơn, đó có phải là một khái niệm constructive hay không. Khái niệm này có thể được mổ xẻ và tổng hợp một cách tự động từ giao tiếp của computers với thế giới bên ngoài? Khái niệm đó có thể dễ dàng transfer từ computers này sang computers khác, có thể được tổng quát hoá và suy diễn (inductive and deductive inference) để tạo ra những khái niệm mới có ích?

Nói theo ngôn ngữ của AI, làm thế nào để học (learn) được common sense ? Câu hỏi này đến nay không hề được giải quyết. Một trong những khó khăn khi dùng pure logic để định nghĩa common sense là những khái niệm như “noise” và “uncertainty”. Những thứ này được coi là nuisance, chứ không phải là một phần của mô hình. Có nhiều cố gắng để khắc phục, những khái niệm khá rắc rối như non-monotonic logic và circumscription, nhưng vẫn không đạt được nhừng yêu cầu mà tôi nhắc tới ở trên: khả năng learnability (inductive inference).

Hãy tạm vứt bỏ khái niệm common sense ra khỏi đầu và nhìn theo một hướng ngược lại, cái gì thì (máy tính) có thể (tự động) học được ? Làm thế nào để giao diện máy tính với thế giới xung quanh, thông qua dữ liệu, để học được một cái gì đó hữu ích? Trong khi trường phái AI của JMC không có câu trả lời, thì đây chính là vấn đề của thống kê học: Làm thế nào để học được các mô hình hữu ích từ dữ liệu? Lý thuyết xác suất là một ngôn ngữ hữu hiệu để biểu diễn các mô hình thống kê, và có một lý thuyết đồ sộ về lý thuyết cũng như về tính toán (computation) làm sao có thể học được các mô hình thống kê từ dữ liệu. Ứng dụng của xác suất ở khắp nơi trong các ngành khoa học có sự giao diện với dữ liệu thực.

Vậy, có sự liên hệ gì không giữa các mô hình học được (bằng ngôn ngữ xác suất thống kê) với khái niệm common sense của JMC. Đến đây, ta có thể tạm thấy rằng câu hỏi này không có nhiều ý nghĩa như trước nữa. Sự xa cách giữa hai khái niệm này cũng chính là khoảng cách giữa hai trường phái top-down và bottom-up trong TTNT. Top-down chính là dạng architecture được khởi xướng từ nhóm JMC và các lớp kế cận, và đã thống trị suy nghĩ của mainstream AI trong suốt thời gian dài. Tại sao là gọi là “top-down”? Một anh bạn chuyên gia về knowledge representation nói vui với tôi cách reasoning top-down sau đây: AI là quan trọng. Để có intelligence thì phải common sense để communicate. Do đó common sense quan trọng. Để có common sense, ta phải biểu diễn chúng, do đó vấn đề representation of logic rất quan trọng. Vì common sense có lẽ là khái niệm logical, nên ta sẽ dùng logic để biểu diễn và manipulate common sense…

Tìm cách bắc cầu giữa cái khoảng trống này (giữa hai trường phái) không phải là không thú vị. Tôi cho rằng, nhìn từ góc độ mô hình xác suất, rất có thể common sense là một dạng “emerging property/phenomenon”, song không nhất thiết là một khái niệm kiến trúc căn bản của intelligence. Nếu quả thật như thế, thì rất nguy hiểm khi bắt đầu xây dựng một intelligent system bằng cách xây dựng common sense storages. Những systems như vậy sẽ không robust.

Ngoài ngôn ngữ xác suất thì còn ngôn ngữ nào có thể dùng để học các mô hình từ dữ liệu. Có, ví dụ như fuzzy logic của Zadeh . Nhưng những thứ làm được bằng fuzzy logic cũng có thể làm được bằng lý thuyết xác suất. Và lý thuyết xác suất là một lý thuyết toán học đồ sộ hơn, đã được xây dựng từ hàng trăm năm nay. Có lẽ câu hỏi đáng nói hơn không phải là vấn đề ngôn ngữ biểu diễn, rằng thế giới của chúng ta có “fundamentally probabilistic/random” hay không. Nhưng cái này vượt ra ngoài tầm của tôi mà sang địa hạt của theoretical physicists.

Trong hoàn cảnh không (và sẽ không) có định nghĩa và định hướng rõ ràng về AI, vấn đề thú vị có lẽ không phải là: AI nên sử dụng statistical methods hay logical methods. Vấn đề thú vị với tôi là, làm thế nào để giao diện máy tính với streams of data của thế giới bên ngoài. Nói cách khác, làm thế nào để máy tính có khả năng thích ứng (adapt) với môi trường xung quanh được cảm nhận qua các loại sensory data. Data ở đây có thể là bits, pulses, radio signals, video images, sounds, texts, documents, numbers, sequences, matrices,… Tôi cho rằng đây là một trong những topic quan trọng nhất của cả computer science trong thế kỷ 21. Các chuyên ngành của KHMT như architectures, operating systems, programming languages đang từng bước đối diện với nó. Nếu đó là quan tâm chính của AI, tuyệt. Nếu không, thì tôi sẽ không quan tâm đến AI làm gì. Câu hỏi trên đây không phải là quan tâm riêng của machine learning, đó cũng là quan tâm chung của signal processing , của information theory, của statistics , của các khoa học liên quan đến dữ liệu thực. Điều mà những người computer scientists đóng góp được vào trong việc trả lời câu hỏi này, làm sao sử dụng được những công cụ tính toán (algorithms, data structures) và các công cụ toán học (sơ và cao cấp) để giải quyết khi số lượng data rất khổng lồ.

Đó chính là thứ nghiên cứu về AI mà tôi quan tâm, cho dù nó có liên quan đến common sense hay không.

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

Nói thêm một chút về định lý của Ahlswede-Cai-Li-Yeung giới thiệu trong bài trước. Ta xét trường hợp tổng quát hơn một chút: mỗi cạnh trong mạng có khả năng truyền packets một giây. (Trong bài trước ta giả sử bằng 1, thật ra chẳng khác nhau gì vì có thể thay một cạnh với băng thông bằng cạnh mỗi cạnh có băng thông bằng 1.) Định lý phát biểu như sau:

Tốc độ multicast tối đa từ source đến tất cả các sinks bằng với capacity nhỏ nhất của các minimum-cuts giữa source và một sink bất kỳ.

Xét một sink bất kỳ nào đó. Định lý max-flow min-cut nói rằng flow lớn nhất từ source đến sink này bằng với capacity của min-cut giữa và . Nghĩa là nếu nguồn chỉ truyền dữ liệu đến một mình sink này, thì tốc độ tối đa là . Như vậy, khi multicast đến tất cả các sinks cùng một lúc, tốc độ lớn nhất có thể có là
Định lý trên nói rằng ta có thể đạt tới cận trên này dùng network coding. Xem ví dụ (ảnh) trong bài đầu tiên, dễ thấy rằng nếu không cho dùng network coding thì ta không thể nào đạt tới cận trên này được:

Với network coding, ta nhận 2 bits x và y sau 2 đơn vị thời gian. Nếu không dùng network coding, tốc độ truyền chỉ có thể tối đa là 2 bits trong 3 đơn vị thời gian.

Tốc độ truyền tối đa trong mạng máy tính thường được gọi là throughput. Điểm cực kỳ thú vị là: network coding cho phép ta đạt đến throughput lớn nhất cho bài multicast và có thể giải bài toán tìm cách truyền tốt nhất trong polynomial time, trong khi đó nếu không dùng network coding thì bài toán tìm các multicast trees cho throughputs lớn nhất là NP-hard. Khi không dùng network coding, bài toán này có thể được formulated như bài toán Steiner Tree Packing, được chứng minh NP-hard trong bài báo Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour, Packing Steiner Trees, SODA 2003.

Một bài báo khác gần đây so sánh throughput của network coding và Steiner Tree Packing: Y. Wu, P. A. Chou, and K. Jain. A comparison of network coding and tree packing. ISIT, 2004. Kết quả cho thấy, trong 6 cấu hình mạng khác nhau của 6 ISPs, thuật toán xấp xỉ Tree Packing của họ có performance khá gần với network coding. Tuy nhiên network coding vẫn có lợi ở việc tận dụng tài nguyên tốt hơn.

Chủ đề: Lý thuyết thông tin & Mạng máy tính | Bình luận (9) »

Tiếp theo bài trước, ta xét (và formalilze) một trong nhiều bài toán liên quan đến network coding.

Dùng một directed graph để mô hình một mạng máy tính. Để đơn giản hóa vấn đề, ta giả sử là acyclic graph. (Trong trường hợp cyclic, định nghĩa bài toán một cách cụ thể trở nên khó khăn hơn rất nhiều - và nói chung là người ta chưa biết nhiều về trường hợp này.) Trong đồ thị có một đỉnh là source và một số đỉnh là sinks. Ta muốn truyền dữ liệu từ source đến tất cả các sinks (multicast) trong thời gian ngắn nhất. Giả sử rằng ở mỗi đơn vị thời gian thì một đỉnh trong mạng truyền được một gói dữ liệu. (Trong trường hợp tổng quát, mỗi cạnh của mạng có thể có tốc độ truyền khác nhau, nhưng ta có thể thay một cạnh có tốc độ truyền lớn bằng nhiều cạnh đơn vị.)

Trong network coding, mỗi đỉnh trong mạng có quyền kết hợp các input packets theo cách tùy ý để gửi ra các output links. Để đơn giản, ta giả sử tất cả các packets đều có cùng kích thước là bits, nghĩa là mỗi packet có thể được xem như một phần tử của trường . Sự “kết hợp” của các inputs packets ra một output link nào đó chẳng qua là một hàm số. Ví dụ: giả sử đỉnh có input links và output links, thì tương ứng với mỗi output link sẽ có một hàm số chuyển input packets thành một output packet (cũng là một phần tử của trường ) để gửi ra link . Một bộ các hàm số như vậy gọi là một network code. Nếu network code cho phép các sinks giải mã các gói dữ liệu thì nó được gọi là network coding solution. Nếu tất cả các hàm đều là hàm tuyến tính (nghĩa là gói output trên cạnh là một tổ hợp tuyến tính của các gói inputs) thì ta có một linear network code.

Giả sử mỗi cạnh có thể dùng để truyền một gói dữ liệu trong một đơn vị thời gian. Định lý sau đây của R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung thật là tuyệt vời.

Tốc độ multicast tối đa từ source đến tất cả các sink bằng với capacity nhỏ nhất của các minimum-cuts giữa source và một sink.

Chú ý rằng: với mỗi một sink thì ta có một minimum cut capacity. Lấy capacity nhỏ nhất thì ra được tốc độ multicast tối đa. Định lý này là phiên bản information flow tương ứng của định lý max-flow min-cut lừng danh của Ford và Fulkerson

Tiếc rằng, định lý này (và chứng minh của nó) không xây dựng cho ta được một network coding solution. Nó chỉ cho biết là tồn tại một solution.

Ngoài ra, kể cả khi có solution, việc mô tả solution này cũng có thể cần exponential space, và như thế thì không thể dùng solution đó làm gì trên thực tế được. Để thấy điều này, giả sử đỉnh có input links. Mỗi hàm coding từ các input links ra một output link nào đó là một hàm số từ đến . Đặt thì tổng số các hàm như vậy là bằng , như vậy phải có ít nhất một hàm cần đến bits để miêu tả nó. Số bít này là hàm mũ của .

May thay, bài báo sau đây:
S.-Y. R. Li, R. W. Yeung, and N. Cai. “Linear network coding“. IEEE Transactions on Information Theory , Februray, 2003
cho ta biết là ta chỉ cần xét các hàm tuyến tính. Nghĩa là, nếu có một network coding solution thì có một solution tuyến tính với một giá trị nào đó của .

Chủ đề: Lý thuyết thông tin & Mạng máy tính | Bình luận (5) »

Lý thuyết thông tin và mạng máy tính hiển nhiên là có phần giao rất lớn, tương hỗ, bổ túc cho nhau. Trong khoảng 5 năm trở lại đây, một nhánh nghiên cứu cực kỳ thú vị đang càng lúc càng thu hút nhiều nhà nghiên cứu từ cả lý thuyết thông tin (đặc biệt là lý thuyết mã - coding theory) và mạng máy tính. Tên gọi của nhánh nghiên cứu mới này là network coding (tạm dịch là mã mạng). Khởi đầu từ bài báo

R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network Information Flow“, (IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000),

đến nay network coding đã có ứng dụng ở rất nhiều nơi, từ wireless communications, content distribution, đến multicasting, vân vân.

Trong loạt bài này, ta sẽ duyệt qua các ý tưởng cơ bản của lý thuyết coding cổ điển (error-detecting, error-correcting codes), các routing algorithms trên Internet, và mối liên hệ của chúng đến network coding.

Để giới thiệu về network coding, hãy xét ví dụ đơn giản sau đây:

Nodes trên cùng muốn gửi 2 bits dữ liệu x và y đến cả hai nodes phía dưới (multicasting) trong thời gian nhanh nhất. Dễ thấy rằng phương pháp truyền trong hình là tối ưu, giả sử rằng tốc độ truyền trên các cạnh của đồ thị là bằng nhau. Ví dụ này dẫn đến ý tưởng sau đây:

Nếu ta cho phép các nodes ở giữa (các routers trên Internet chẳng hạn) tham gia thay đổi (xẻ đôi, trộn) các gói dữ liệu, thì có khả năng sẽ tiết kiệm được bandwidth, delay, và các tài nguyên khác trong mạng.

Khi làm nghiên cứu, sau khi phác thảo ý tưởng cơ bản, bước kế tiếp sẽ là formalize ý tưởng này. Quá trình formalization sẽ dẫn ta đến một vài bài toán tuyệt đẹp, liên quan đến đại số trừu tượng, đại số tuyến tính, các ma trận chưa hoàn tất, network flow, và nhiều nhánh khác.

Chủ đề: Lý thuyết thông tin & Mạng máy tính | Bình luận »

Khi chúng ta học những kiến thực cơ bản đầu tiên probability theory, ta biết đến những hàm phân phối cho biến thực/tự nhiên ngẫu nhiên kinh điển như Gaussian, Poisson, Bernoulli, Laplace, Dirichlet, Cauchy, v.v. Stochastic processes là gì ? Một cách nôm na, stochastic processes là những hàm phân phối cho những objects phức tạp hơn, như một collection of variables, hoặc các hàm số, hoặc các đồ thị (graphs), v.v.

Có thể định nghĩa đủ thứ hàm phân phối lên các objects cần quan tâm. Cuộc sống của chúng ta có thể được mô hình bằng các loại objects khác nhau, khi thì có tính chất combinatorial, khi thì analytical. (Ví dụ, Graphical models là một phương pháp tổng quát để định nghĩa một dạng stochastic processes). Do đó, stochastic processes có nhiều ứng dụng trong việc mô hình, tìm hiểu và dự đoán với data. Về mặt lý thuyết, nghiên cứu tính chất và cách sử dụng các stochastic processes mới rất thú vị không chỉ với những người nghiên cứu về xác suất thống kê thuần túy, mà cả với những người làm về data modeling.

Một số sách sau đây rất tốt về probability theory và stochastic processes.

• Convergence of Stochastic Processes của David Pollard (Yale). Sự trình bày về empirical processes được coi là kinh điển, tuy đây chỉ là một phần nhỏ của quyển sách. Một phần lớn sách nói về khái niệm weak convergence (convergence in distribution) trong không gian Euclidean và các metric spaces khác. Hiểu biết các khái niệm này là bước đệm quan trọng trong việc nghiên cứu và sử dụng các loại stochastic processes trong không gian vô hạn chiều (function spaces).
  Empirical processes theory hiện là một trong những nền tảng lý thuyết cơ bản của machine learning, đặc biệt là nonparametric statistic/learning.

• The random geometry of equilibrium phases của Olle Häggström (Chalmers Univ of Technology, Sweden). Một quyển sách hay về các mô hình Markov Random Fields trong statistical physics, và các hiện tượng phase transition và percolation trong những loại mô hình này. MRF cũng chính là một dạng graphical models (với undirected graphs), có nhiều ứng dụng trong parametric machine learning và statistics. Một trong những topics có thể học được từ quyển sách này là làm thế nào có thể định nghĩa được consistent stochastic processes cho graph với infinite vertices mà chỉ dựa vào các local constraints của graphs. Đối với finite graphs thì không có vấn đề gì. Các graphical models chúng ta gặp trong ứng dụng (như Hidden markov models chẳng hạn) đều chỉ có số đỉnh (vertices) là hữu hạn. Nghiên cứu về infinite graphs cho chúng ta hiểu biết sâu hơn về finite graphs có số lượng đỉnh rất lớn. Các khái niệm phase transition, mixing time of Monte Markov chains, uniqueness of Gibbs measures có liên hệ cực kỳ thú vị trong stochastic graphs cho infinite graphs. Đây là một trong những lĩnh vực có sự giao thoa rất lý thú giữa vật lý thống kê, lý thuyết tính toán, và lý thuyết về learning/ xác suất thống kê.
• Reversible Markov Chains and Random Walks on Graphs của David Aldous (Berkeley) và Jim Fill (Johns Hopkins). Đây là một quyển sách khá sâu về Markov Chains.
• Probability in Banach spaces của Ledoux và Michel Talagrand (Paris 6). Đây là quyển sách advanced về lý thuyết xác suất đối với biến ngẫu nhiên thuộc Banach spaces. Nhiều chủ đề quan trọng như isoperimetric inequalities, concentration of product measures, và ứng dụng cho empirical processes.

Vào thăm homepage của Talagrand còn có nhiều quyển sách miễn phí rất hay khác, như quyển sách về Mean field models for spin glass nghiên cứu về hiện tượng phase transition trong vật lý bằng lý thuyết xác suất chặt chẽ. Có thể rất lý thú cho dân làm về statistical physics, lý thuyết các thuật toán ngẫu nhiên monte carlo markov chain, và dân làm về machine learning.

• Stochastic Calculus for mathematical finance của Steven Shreve (CMU). Quyển sách rất hay để học về stochastic partial differential equations; các mô hình thống kê cho finance và stochastic control.
• Lecture notes về stochastic processes của Amir Dembo (Stanford).

Ngoài ra, có thể tham khảo thêm danh sách sách miễn phí trên mạng của nhiều ngành toán, trong đó có lý thuyết xác suất nói chung, và stochastic processes nói riêng.

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

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) »

Xin viết kỹ hơn về phương pháp giải mã của Bob cho bài toán đang xét. Về căn bản, Alice muốn gửi cho Bob con số . Với chiến lược đã nêu, tỉ lệ q của số bit 1 trên tổng số bit nhận được sẽ gần với p nhưng không có gì đảm bảo nó sẽ bằng p. Hơn nữa, làm thế nào ta biết được là q sẽ gần với p?

Trước hết, ta xét vấn đề giải mã. Con số p Alice cần gửi là một bội số của . Có tất cả vị trí từ 0 đến 1 mà p có thể nằm. Các vị trí này cách đều nhau một khoảng bằng , từ đến . Phương pháp giải mã của Bob rất đơn giản: tính tỉ lệ q như đã nêu, sau đó làm tròn nó về bội số gần nhất của . Như vậy, miễn là thì Bob sẽ giải mã đúng.

Cho trước một sai số (ví dụ 0.001%), nếu thì Bob sẽ giải mã sai với xác suất nhiều nhất là . Để ước lượng xác suất này, ta dùng chặn Chernoff. Trong bài giảng ở đây, tôi có ghi lại chặn Chernoff ở một dạng tương đối mạnh. Với bài toán của chúng ta thì ta chỉ cần một dạng đơn giản của chặn này.

Giả sử ta có các biến ngẫu nhiên trong đó và , với là một xác suất cho trước. Dễ thấy rằng

Các chặn Chernoff cho ta ước lượng xác suất mà nằm xa expected value . Phân bố của tổng này có hai cái “đuôi” mỏng ở hai đầu, còn lại tập trung vào gần expected value (giống như hình ngọn núi), gọi là hiện tượng concentration.

Cho trước , Chernoff’s bound cho đuôi trên (upper tail) có thể viết như sau:

và cho lower tail ta có

Nói theo ngôn ngữ bình thường: khi tiến ra vô cùng, khả năng mà nằm xa trung tâm tiến đến theo hàm mũ (exponentially reduced).

Trở lại bài toán của chúng ta. Đặt bằng giá trị của bit thứ mà Bob nhận được. Như vậy, sau khi Alice gửi bits, ta có . Dùng chặn Chernoff, đặt (bỏ qua trường hợp tầm thường khi ), ta có

Như vậy, chỉ cần là Bob có sai số mong muốn.

Chủ đề: Lý thuyết thông tin & Mạng máy tính & Xác suất & thống kê | Bình luận »

Tiếp tục với câu hỏi cực kỳ thú vị lần trước.

Giả sử Bob biết n, và giả sử chuỗi nhị phân C có các bits . Gọi c là số nguyên có biểu diễn nhị phân là C. Ví dụ, nếu C = 10110 thì c = 22. Chiến lược của Alice như sau: mỗi lần gửi, gửi bit 1 với xác suất , và gửi bit 0 với xác suất 1-p. Với chiến lược này, Alice không cần phải nhớ xem mình đã gửi bit gì. Sau khi đã gửi thật nhiều bits, Bob tính tỉ lệ q của số bits 1 trên tổng số bits mà Bob đã nhận. Tỉ lệ này sẽ tiến đến p khi tổng số bits nhận được tiến đến vô cùng. Ta có thể dùng Chernoff bound để tính cụ thể xác suất mà p và q nằm trong vòng của nhau là bao nhiêu. Hơn thế nữa, ta có thể ép xác suất lớn tùy ý.

Thật ra thì ta không cần nhỏ lắm, chỉ cần khoảng là đủ. Tóm lại, khi tổng số bits Alice gửi tiến đến vô cùng, thì xác suất Bob giải mã được chuỗi C tiến đến 1. Đó là lời giải cho trường hợp Bob biết trước n.

Chủ đề: Lý thuyết thông tin & Mạng máy tính & Xác suất & thống kê | Bình luận (3) »

Đọc các bài báo về IP traceback, tôi vừa học được bài toán tuyệt đẹp sau đây:

Alice có một chuỗi C gồm n bits nhị phân cần gửi cho Bob. Tuy nhiên, mỗi lần Alice chỉ có thể gửi 1 bit và gửi xong thì Alice quên béng mất là mình đã gửi bit gì (hay bit nào). Thiết kế một protocol để Alice có thể gửi C cho Bob.

Chú thích: Alice có thể gửi bao nhiêu bits cho Bob tùy ý, miễn là trong giới hạn các ràng buộc trên. Giải bài toán trong hai trường hợp: (i) Bob biết trước n bằng bao nhiêu, và (ii) Bob không biết cả n luôn.

Impossible? Tựa đề của post đã có gợi ý.

Chủ đề: Lý thuyết thông tin & Mạng máy tính & Xác suất & thống kê | Bình luận »

Giáo sư Christo H. Papadimitriou dạy một lớp với nội dung dựa trên các bài báo kinh điển của KHMT. Lấy cảm hứng từ lớp này, tôi sẽ bắt đầu một series mới các bài về đề tài này.

Mỗi post sẽ giới thiệu một bài báo kinh điển, không theo một trật tự nhất định nào. “Kinh điển” cũng không đồng nghĩa với “cổ điển”. Tôi sẽ giới thiệu cả các bài báo gần đây mà vẫn có thể xếp vào loại kinh điển. Hy vọng các bloggers khác của blog này sẽ thêm vào các bài báo kinh điển mà họ thích.

Mặc dù tựa đề của post là “các bài báo kinh điển trong KHMT”, các bài báo sẽ được trình bày trong series này không nhất thiết là chỉ thuộc về “KHMT”. Có rất nhiều các bài báo có ảnh hưởng sâu sắc đến KHMT nhưng đã được viết trong một ngữ cảnh khác.

Bài hôm nay là của Claude E. Shannon:

• C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948.

Bài báo này đánh dấu sự ra đời của lý thuyết thông tin. Để nói về ảnh hưởng sâu sắc của bài báo này nói riêng và của Shannon nói chung đến KHMT hiện đại thì ta cần vài quyển sách. Ta tóm tắt ở đây vài khái niệm và kết quả kinh điển từ bài báo này:

• Lần đầu tiên xác suất được áp dụng vào phân tích truyền thông. Ngày nay thì các phân tích và mô hình hóa bằng xác suất trong KHMT và truyền thông phổ dụng đến mức ta khó có thể tưởng tượng ý tưởng này mới như thế nào khi Shannon viết bài này.
• Ý tưởng đột phá là “thông tin” (bất kể nguồn loại gì) về căn bản là mang tính số (digital). Dấu ấn của ý tưởng này trên các ngành công nghệ hiện đại nằm ở mọi nơi: lưu trữ thông tin (CD, đĩa cứng), truyền thông tin (mạng máy tính), vân vân. Khái niệm “bit” thông tin được giới thiệu lần đầu tiên.
• Khái niệm “entropy” thông tin ra đời, dùng để đo “độ phức tạp” hay “độ ngẫu nhiên” của nguồn thông tin. Nói nôm na thì entropy của một tín hiệu thông tin đại diện cho “tổng số thông tin” mà tín hiệu này mang.
• Các kênh thông tin có một dung tích (channel capacity) mà nếu ta truyền tín hiệu với tốc độ nhỏ hơn nó thì tồn tại một cách mã hóa (code) tín hiệu mà nhờ đó ta có thể đạt được xác suất lỗi nhỏ tùy ý. Phát biểu này đại khái là nội dung của định lý noisy channel coding lừng danh.
• Bài báo cũng đặt nền tảng cho ngành nén dữ liệu (data compression), mã hóa và giải mã tín hiệu với khả năng phát hiện lỗi (error-detection code) và sửa lỗi (error-correction code). Xem thêm quyển sách kinh điển này.
• Nhờ bài báo này, truyền thông có thể hiểu nôm na là bao gồm 3 bước chính: mã hóa tín hiệu, truyền tín hiệu qua kênh thông tin, và giải mã tín hiệu.

Nhà toán học vĩ đại Kolmogorov từng nói về Shannon như sau

• Trong thời buổi mà kiến thức nhân loại càng lúc càng đuợc chuyên môn hóa, Claude Shannon là một nhà khoa học ngoại lệ. Shannon kết hợp các ý tưởng toán học sâu sắc với các hiểu biết rộng và cụ thể của các vấn đề quan trọng bậc nhất của công nghệ. Shannon là một trong những nhà toán học vĩ đại nhất đồng thời là một trong những kỹ sư giỏi nhất trong vài thập niên qua.

Chủ đề: Lý thuyết thông tin & Lý thuyết tính toán | Bình luận (5) »

Ở cuối quyển “Các cuộc phiêu lưu của một nhà toán học“, nhà toán học Stan Ulam (1909-1984) có nhắc đến bài toán 20-câu hỏi nổi tiếng: giả sử anh A nghĩ trong đầu một số nguyên từ 1 đến 1 triệu, anh B phải hỏi bao nhiêu câu hỏi nhị phân (nghĩa là chỉ trả lời có hoặc không) để đoán được bí mật này?

Giả sử anh A nghĩ một số từ 1 đến n, dễ thấy rằng phương pháp tìm kiếm nhị phân có thể áp dụng được ở đây. Anh B hỏi: “số anh nghĩ có phải từ 1 đến n/2 không?”, nếu có thì ta chia đôi đọan [1,n/2], nếu không thì ta chia đôi đọan [n/2+1, n], vân vân.

Bài toán căn bản này có nhiều biến thể khó, thú vị, và có rất nhiều ứng dụng: từ sàng DNA (DNA screening), thử máu, nghi thức giải quyết tranh chấp trong mạng máy tính (conflict resolution protocol), đến tăng hiệu suất hệ thống mạng (xem tin), vân vân.

Các điều kiện sau đây, hoặc một tập con của chúng, dẫn đến các câu hỏi toán học thú vị có tính ứng dụng cao:

1. A nghĩ trong đầu d số thay vì 1 số.
2. B phải hỏi tất cả các câu hỏi cùng một lúc, và dựa trên tất cả các câu trả lời đoán (các) bí mật của A.
3. A có thể trả lời dối vài lần.
4. Có một xác suất nhất định là A sẽ nghĩ một số.

Ví dụ: trong thời thế chiến thứ hai, khi thử máu cả trăm nghìn lính xem những ai trong đó bị một bệnh nhất định (lúc đó giang mai - syphilis - là đối tượng chính), người ta thường phải bỏ một tập con các mẫu máu vào một hợp chất hóa học. Nếu hợp chất có phản ứng (đổi màu chẳng hạn), thì trong tập con các mẫu máu đó có ít nhất một mẫu bị bệnh.

Các tập con mẫu máu này là các câu hỏi nhị phân. Các tập con phải được thiết kế trước, vì ta không thể lấy mẫu một nửa số lính, rồi tùy theo kết quả thử lấy nửa số khác hoặc chia đôi số đã lấy. Việc thiết kế trước các tập con này chính là biến thể số 2 nêu trên. Rõ ràng là tổng số “bí mật” (trong trường hợp này là số lính bị bệnh) nhiều hơn một (biến thể số 1). Ngoài ra, ta cũng không biết có nhiều nhất bao nhiêu lính bị bệnh, cho nên có thể phải tìm một xác suất bệnh (biến thể thứ 4). Các hợp chất có thể có phản ứng sai do mẫu máu không tinh khiết (biến thể thứ 3). Hiển nhiên là vì máu có hạn, nên ta phải tối ưu tổng số phép thử (đồng nghĩa với tối ưu tổng số câu hỏi).

Các bài toán này thuộc về nhánh nghiên cứu gọi là “thử nhóm” (group testing), một đề tài rất thú vị. Bạn xem thêm bài survey tôi viết đã lâu, và một bài báo khác tôi thiết kế một giải thuật như vậy.

Chủ đề: Lý thuyết thông tin & Nghiên cứu nghiên kiếc & Vui - Giải Trí | Bình luận (1) »