Giải Nevalina 2010

Giải Nevalina năm nay được trao cho bạn Spielman (đại học Yale). Bài dưới đây nói qua về công trình của Spielman. Sáng nay vừa mở máy tính ra thì bạn Tào đã làm ngay hai bài dài ngoằng nói về tất cả các giải thửơng của IMU, bạn nào quan tâm rất nên đọc. Bác Sơn Đàm cũng viết một bài rất hay về các công trình được giải liên quan đến vât lý.

Tôi viêt thêm về chủ đề của Spielman vì chủ đề này có những bài toán mở (open problem) tương đối dễ hiếu và thú vị. Bạn có thể (và nên) đọc song song với bài của Tào, và tham khảo thêm bài của Spielman và Teng trên proceeding của IMU 2002, bài này cũng rất dễ đọc và không cần nhiều kiến thức chuẩn bị.

Công trình tôi muốn nói tới là “Smoothed Analysis” của Spielman và Teng. Hai bạn này chú trọng đến simplex algorithm, nhưng tốt hơn là ta phát biểu khái niệm này một cách tổng quát.

Mục đich của bạn Spielman và Teng là phân tích hiện tượng sau:

Có một dữ liệu (data) , thường được biểu diến dưới dạng một ma trận rất to. Ta muốn chạy một phép toán với input là . ̣Trường hợp cụ thể mà Spielman-Teng phân tích là simplex algorithm rất thông dụng trong quy hoạch tuyến tính.

Câu hỏi cơ bản nhất trong lý thuyết tính toán: Máy chạy mất bao lâu ?

Để trả lời câu hỏi này, người ta thường phân tích trường hợp “xấu nhất” (worst case analysis-worst matrix ). Câu trả lời cho simplex algorithm, và tương đối nhiều phép toán khác, là “Rất lâu !! Chờ nhé !!” (exponential time). Các nhà toán học đã viết ra một số ma trận cụ thể với kích thước không lớn lắm mà phép toán này sẽ phải chạy hàng nghìn năm (trên máy tính xịn) mới ra kết quả.

Nhưng, trong thực tế, simplex algorithm rất hỗn. Nó cười khảy vào các kết quả trên và luôn chạy băng báng. Điều này làm các nhà toán học rất tức tối, phải làm cho ra ngô ra khoai. Muốn vậy, phải dùng một ít xác suất.

Sau một số lớn các cách giải thích chưa được hoàn toàn trọn vẹn, cách đây chừng 10 năm, Spielman và Teng đưa ra cách giải thích sau: Trong tính toán luôn luôn có tiếng ồn, sai số (noise). Khi bạn đo một dữ liệu, mặc dầu kết quả thực là , nhưng trên thực tế không bao giờ ta nhận được . Vậy máy tính sẽ không chạy trên input , mà chạy trên input , trong đó là sai số. Sai số này thường được biếu diến dưới dạng một ma trận ngẫu nhiên.

Định lý chính của Spielman và Teng nói là nếu là một ma trận Gauss và là một ma trận bất kỳ ( cùng có kích thước ) thì với xác suất cao, simplex algorithm với input sẽ chạy nhanh (polynomial time).

Ma trận Gauss là ma trận ngẫu nhiên với các phần tử là biến Gauss độc lập. Xác suât cao là xác suất tiến tới 1 nếu tiến tới vô cùng. Polynomial time là , với là một hằng số.

Cách giải thích của S-T rất hợp lý, vì nó cho phép có thể là bất kỳ ma trận nào, kể cả những ma trận xấu tính nhất
đến từ worst case analysis. Tôi thấy nó thú vị vì thường trong các ứng dụng dùng đén thuật toán, tiếng ồn và sai số luôn là thủ phạm của các vụ rắc rối khi ta cần tính một cái gì cụ thể, nhưng ở đây nó lại có vai trò “tích cực”. Sai số làm cho các ma trận xấu tính không thể trở nên quá xấu.

Đây là ý tưởng chính trong công trình dẫn tới giải Nevalina của Spielman và giải Godel và Fulkerson chung cho hai người.

Định lý S-T được phát biểu dưới dạng phép toán (algorithmic), vậy mấu chốt toán học của nó ở đâu ? Quan sát quan trọng nhất của S-T có lẽ là bổ đề sau.

Để phát biểu bổ đề này, ta cần một vài khái niệm. Trước hết, để đơn giản hóa vấn đề, ta giả sử cả và là ma trận vuông (). Ma trận có thể coi là một ánh xạ tuyến tính từ đến . Ánh xạ này sẽ làm biến dạng không gian, cụ thể nó sẽ biến hình cầu thành một hình ellip. Hình ellip đại loại giống quả trứng, có trục dài trục ngắn. Độ dài của các trục này là các singular values của (trong trường hợp là ma trận đối xứng thì đó là giá trị tuyệt đối của các giá trị riêng). Một ma trận gọi là “tốt” nếu tỷ lệ giữa trục dài nhất và trục ngắn nhât tương đối nhỏ và “xấu” nếu tỷ lệ này lớn. (Nói nôm na là ma trận tốt thì trứng tròn còn ma trận xấu thì trứng dài.) Tỷ lệ này,
ký hiệu là , được gọi là “condition number” của và nó quyết định thời gian và độ chính xác của các thuật toán cơ bản chạy trên .

Một ma trận trong trường hợp xấu nhất có thể có condition number rất lớn (thậm chí là vô cùng nếu bậc của ma trận nhỏ hơn ; khi đó trứng sẽ thiếu mất một
hay nhiều chiều, không xơi được).

Bổ đề (S-T). Nếu là một ma trận Gauss và là một ma trận bất kỳ thì với mọt hằng số

Nội dung của bổ đề này là dù có láo cỡ nào, chỉ cần nó không quá to, thì trong phần lớn các trường hợp không thể quá xấu. Ngay cả khi là vô cùng, thì với xác suât xấp xỉ 1, vẫn nhỏ hơn (bất kỳ hàm polynomial nào của cũng đủ tốt cho ứng dụng). Bạn có thể đọc kỹ thêm trong bài ICM của S-T.

Chứng minh bổ đề trên không khó. Nhưng phần phân tich thuật toán khá phức tạp; một cách chứng minh đơn giản hơn được đưa ra sau đó bởi Vershynin.

Bây giờ nói tới bài toán mở. Ý tưởng của S-T rất hay. Nhưng giả thuyêt N là ma trận Gauss hơi mạnh. Trong các dữ liệu cụ thể, thường các số liệu là sổ nguyên, hoặc được viêt dưới dạng thập phân với một vài chữ số sau dấu phẩy. Bản thân máy tính cũng chỉ làm việc được với các số biểu diến được một cách hữu hạn mà thôi. Các số được sampled từ phân bố Gauss thì luôn là vô tỷ, thậm chí không phải số đại số. Vậy giả thuyết gần với thực tế hơn là các phần tứ của có phân bố rồi rac trên một số hữu hạn điểm.

Trường hợp đơn giản (vầ đặc trưng) nhất là khi có phân bố Bernoulli, các phần tứ là hoặc với xác suất . Bài toán mở ở đây là chứng minh Định lý S-T cho trường hợp này. Vấn đề này bạn Spielman có nói với tôi cách đây chừng năm năm, nhưng hiên nay hình như vẫn chưa ai giải.

Bước đầu tiên là chứng minh bổ đề S-T cho ma trận Bernoulli. Vấn đề này rất gần với Universality (hay Invariance) principle trong toán vật lý (xem bài của Tào về Smirnov). Nôm na mà nói, thường ta tin rằng một định lý đúng với một mô hình (hay phân bố) ngẫu nhiên nào đó thì cũng đúng với các mô hình khác. Nhưng chứng minh điều này nói chung là khó, vì thường các cách chứng minh hay dùng các tính chất cụ thể của phân bố đã cho, chẳng hạn cách ST chứng minh bổ đề dùng tính chất là phân bố Gauss trong không gian nhiều chiều có tính đối xứng rất cao (rotational invariant). Tính chất này không đúng trong trường hợp Bernoulli. Một bài toán con của bổ đề S-T trong trường hợp Bernoulli là bài toán khá nổi tiếng sau:

(Định lý Komlos, 1966): Với

Định lý này nói rằng một ma trận ngẫu nhiên có bậc đầu đủ với xắc suất gần 1. Một cách khác nữa, nếu ta lấy đỉnh ngẫu nhiên của hình lập phương thì các đỉnh này không nằm trên cùng một siêu phẳng.
Trong trường hợp ta lấy điểm từ một hình cầu, định lý này hiển nhiên đúng. Chẳng có lý do gì để điểm này nằm trên cùng một mặt phẳng. Nhưng với các phân bố rời rạc, thì chuyện lại khác.

Bạn có thể xem các mở rộng của bổ đề S-T tại đây. Công cụ chủ yểu để mở rộng bổ đề này đến từ Additive Combinatorics. Hiện vẫn còn một số vấn đề mở rất thú vị với bổ đề này. Về Định Lý S-T,chỗ vướng mắc, như tôi còn nhớ, là trong phần phân tích thuật toán, có dùng những tính chất khác khá mạnh của phân bố Gauss trong môt số Lemma mang tính kỹ thuật.