20 vạn dặm dưới đáy biển

Chủ đề Mạng máy tính | Phản hồi »

HM5 — Định lý Vapnik-Chervonenkis cho mô hình giả thuyết không nhất quán

Chúng ta tiếp tục chuỗi bài về đề tài “Học máy từ góc nhìn của lý thuyết tính toán”. Các bài trước là:

  1. HM1 — Giới thiệu học máy và mô hình nhất quán
  2. HM2 — Một số ví dụ trong mô hình nhất quán
  3. HM3 — Mô hình PAC và ví dụ
  4. HM4 — Độ phức tạp mẫu và VC dimension.

Hai mô hình (nhất quán và PAC) chúng ta thấy cho đến nay đều không thực tế lắm. Trên thực tế dữ liệu thường có nhiễu, việc tìm một giả thuyết nhất quán với nhiều mẫu trở nên khó khăn. Đôi khi không tồn tại giả thuyết nào nhất quán với dữ liệu, hoặc cho dù có tồn tại thì nhiễu cũng làm cho không tồn tại. Vả lại, nhất quán với dữ liệu bị nhiễu thì cũng không hay ho gì. Đó là chưa kể việc đi tìm một giả thuyết nhất quán với dữ liệu có thể là bài toán NP-khó, và thậm chí có thể trên thực tế không tồn tại cái khái niệm mà mình đang muốn học.

(Từ giờ trở đi, tôi sẽ dịch “learner” là “học giả”. Học giả ở đây là một thuật toán máy tính chứ không phải là một gã hói đầu. “Học giả như hòa như đạo. Bất học giả như cảo như thảo.”)

Như vậy chúng ta cần một mô hình cho phép học giả trả về một giả thuyết không nhất quán với mẫu, và phải tìm cách đo chất lượng học giả — kể cả khi không có cái khái niệm mà mình muốn học. Bài này kết thúc bằng chứng minh định lý Vapnik-Chervonenkis, một trong những định lý quan trọng nhất của lý thuyết học máy thống kê (statistical learning theory).

Đọc tiếp »

Chủ đề Lý thuyết tính toán, Trí tuệ nhân tạo, Xác suất & thống kê | 10 phản hồi »

VC

Vapnik-Chervonenkis (dimension), Voice Channel, Vertex Cover, Visual C++, Virtual Circuit, Video Card/Camera, Venture Capital, Video Conferencing, Vector Calculus, Virtual Container, …

Viet Cong

Vitamin C, Very Cute, …

Chủ đề Vui - Giải Trí | 7 phản hồi »

Rabbi and Priest

Dạo này tôi làm việc thường xuyên với một bạn Israel. Bạn hay kể chuyện tếu. Cắt dán lại đây vài chuyện:

Copy ở đây

A rabbi and a priest get into a car accident and it’s a bad one. Both cars are totally demolished, but, amazingly, neither of the clerics is hurt. After they crawl out of their cars, the rabbi sees the priest’s collar and says, “So you’re a priest. I’m a rabbi. Just look at our cars. There’s nothing left, but we are unhurt. This must be a sign from God. God must have meant that we should meet and be friends and live together in peace the rest of our days.”

The priest replies, “I agree with you completely. This must be a sign from God.”

The rabbi continues, “And look at this. Here’s another miracle. My car is completely demolished but this bottle of Mogen David wine didn’t break. Surely God wants us to drink this wine and celebrate our good fortune.” Then he hands the bottle to the priest.

The priest agrees, takes a few big swigs, and hands the bottle back to the rabbi. The rabbi takes the bottle, immediately puts the cap on, and hands it back to the priest.

The priest asks, “Aren’t you having any?”

The rabbi replies, “No…I think I’ll wait for the police.”

Đọc tiếp »

Chủ đề Vui - Giải Trí | Phản hồi »

Toán ứng dụng và Toán lý thuyết (Nguyễn Tiến Dũng)

Bác Nguyễn Tiến Dũng có bài rất hay. Xin trích một paragraph nhỏ:

Những phần phía trên tôi viết không có nghĩa là Việt Nam không cần đến toán lý thuyết, hay còn gọi là toán cơ bản. Vì có cơ bản thì mới có ứng dụng. Ý tôi muốn nói là, mục đích chính của việc học toán cơ bản, không phải là để tiếp tục sản sinh ra toán cơ bản, rồi lại tiếp tục sản sinh ra toán cơ bản, theo kiểu «toán học vị toán học», để cho đẹp. Toán học tuy đẹp thật, nhưng rất ít ai thưởng thức được cái đẹp xa xỉ phẩm đó. Vai trò chính của toán học trong xã hội không phải là để «làm đẹp», mà là làm công cụ giải quyết các vấn đề khác. Đối với các cá nhân, ai thích cái gì nhất, có khiếu cái gì nhất, thì nên đi làm cái đấy nếu tìm được hạnh phúc trong đó. Từ quan điểm chiến lược của tập thể lớn, trong việc chia nguồn lực có hạn, thì phải phân bổ lực lượng sao cho đạt hiệu quả chung cao nhất. Trong việc phân bổ lực lượng đó, trung bình mỗi lý thuyết cần có được nhiều ứng dụng. Tỷ lệ giữa lý thuyết và ứng dụng phải là 1:10, hay như các cụ có nói, học một hiểu mười, biết được 1 cái áp dụng được vào 10 cái, chứ không phải ngược lại.

Chủ đề Toán Ứng Dụng | 1 phản hồi »

CS Theory Overflow

đã mở cho công chúng, các bạn có câu hỏi gì về các đề tài nghiên cứu liên quan đến lý thuyết máy tính có thể đặt ở đó. Nhớ rằng, giống như MathOverflow, cstheory dành cho các câu hỏi nghiên cứu chứ không phải để hỏi bài tập thiết kế thuật toán.

Một câu hỏi thú vị từ cstheory:

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square.

Is there a fast algorithm to determine whether a string is square, or is it NP-hard? The obvious dynamic programming approach doesn’t seem to work.

Even the following special cases appear hard: (1) strings in which each character appears at most four times, and (2) strings with only two distinct characters.

Chủ đề Thông báo | Phản hồi »

Hãy để ngày ấy lụi tàn

  • Chủ nghĩa tư bản Mỹ đang dãy chết vì bệnh béo phì

  • Chủ nghĩa bành trướng bá quyền Tàu khựa sẽ chết vì kẹt xe:

    Did you have a bad commute today? How long did you sit in traffic — an hour, maybe two? Thousands of motorists in China have been stuck for ten days in a jam that goes on for more than 60 miles.

Chủ đề Vui - Giải Trí | Phản hồi »

Bình loạn trong chương trình (máy tính)

Bên Stackoverflow có câu hỏi: “What is the best comment in source code you have ever encountered?” Dưới đây là vài câu trả lời.

Nếu bạn không cười lăn ra đất thì bạn nên chuyển sang làm địa ốc, làm máy tính không thích hợp với bạn.

#define if while
//When I wrote this, only God and I understood what I was doing
//Now, God only knows
//
// Dear maintainer:
//
// Once you are done trying to 'optimize' this routine,
// and have realized what a terrible mistake that was,
// please increment the following counter as a warning
// to the next guy:
//
// total_hours_wasted_here = 16
//
// sometimes I believe compiler ignores all my comments
Exception up = new Exception("Something is really wrong.");
throw up;
// I dedicate all this code, all my work, to my wife, Darlene, who will
// have to support me and our three children and the dog once it gets
// released into the public.
#define TRUE FALSE //Happy debugging suckers
// I am not responsible of this code.
// They made me write it, against my will.

Chủ đề Lập trình, Vui - Giải Trí | 3 phản hồi »

Makefile tổng quát

Hôm qua lọ mọ viết một Makefile cho sinh viên cho các bài tập lập trình học kỳ tới. Makefile này khá tổng quát cho các chương trình cỡ chục nghìn dòng lệnh đổ lại. Nó giả sử là mỗi .c đều có .h tương ứng. Dễ dàng sửa lại một chút để nó dịch các chương trình C++. Ghi lại đây biết đâu lại có lợi cho ai đó.

Đọc tiếp »

Chủ đề Lập trình, Mạng máy tính | 2 phản hồi »

Ngô Bảo Châu!

Một tin cực vui!

Chúc mừng Hòa Thượng! Giải Fields là món quà xứng đáng cho một nỗ lực phi thường của một tài năng lớn.

Chúc mừng các bạn T., H., N., A., và tất cả những ai đã góp phần vào thành tựu này.

Chủ đề Nhân vật và sự kiện | 15 phản hồi »

Vì sao ta có con?

Chính xác hơn, câu hỏi phải là “Ta có con là nhằm mục đích gì?” Khi người ta làm bất cứ một cái gì, người ta phải có một mục đích. Người ta mua một chiếc xe là để người ta có thể tự mình mỗi sáng đi ra quán phở đối diện công viên Lê Văn Tám. Đi ra quán phở công viên Lê Văn Tám là vì người ta cần ăn một bữa sáng chất lượng. Cần ăn sáng chất lượng là vì người ta cần năng lượng để làm việc cả ngày cho thật tốt. Làm việc cả ngày thật tốt là để mau lên lương. Mau lên lương là để có tiền mua một chiếc xe xịn hơn, khi chạy vào quán hủ tíu Nam Vang trên đường Võ Văn Tần gần đường Cống Quỳnh cũng thấy oai phong lẫm liệt. Không ai vô duyên vô cớ lại đi mua một tấm vé xem phim, hay đi sửa một căn nhà. Có một đứa con cũng vậy, cũng phải vì một lý do này hay nguyên cớ nọ. Tạo ra một sinh linh để nó chịu khổ trên đời đâu phải chuyện dỡn chơi. Nhưng ngẫm đi nghĩ lại, trừ những trường hợp bị cưỡng ép mà phải sinh con, dường như người ta sinh con chỉ hoặc là vì người ta bất cẩn, không biết suy nghĩ đến nơi đến chốn, thậm chí không hề suy nghĩ, hoặc là vì người ta ích kỉ không nghĩ gì đến đứa trẻ sẽ ra đời.

Đọc tiếp »

Chủ đề Chưa phân loại | 25 phản hồi »

Yên nghỉ — Nguyễn Bình Dương

Vừa nghe tin bạn mất. Bàng hoàng! Vừa rồi về mấy tháng không gặp nhau. Bây giờ thì không còn kịp nữa. Đã biết bạn bị tai biến mấy lần, nhưng năm kìa vẫn còn chén chú chén anh, tớ ỉ i.

Có lẽ, nói một cách bào chữa, trong thâm tâm tớ vẫn nghĩ bạn là thằng Dương học thi với tớ trên nóc nhà 18 năm trước. Thằng Dương lập trình C như máy — Borland C trên DOS. Tớ gõ bàn phím còn không kịp bạn, nói gì đến tư duy bằng C như bạn.

Mới đó mà …

Chúc Dương yên nghỉ!

Chủ đề Thông báo | 21 phản hồi »

Kurt Nilsen

Kurt Nilsen có giọng hát tuyệt vời. Ian Dickson nói rằng:

“Kurt, you are a hell of a marketing challenge, because you have the voice of an angel, but you look like a Hobbit.”

Lần trước ta gặp Leonard Cohen với nhạc phẩm “Dance me to the end of love”. Lần này là một tuyêt tác khác: Hallelujah. Tôi chưa tìm thấy cover nào hay hơn cái này, kể cả bản của K. D. LangAlex Burke.

Đọc tiếp »

Chủ đề Âm Nhạc | 2 phản hồi »

God’s number

Không phải con số mà “nobody calling” như trong tuyệt tác của Joan Osborne.

God’s number là số bước ít nhất để giải 6 mặt của cục Rubik, bất kể trạng thái bắt đầu. Và nó vừa được xác định là bằng 20, dùng khoảng 35 năm CPU (nhưng song song hóa nó ra). Dĩ nhiên, thuật toán tìm đường đi ngắn nhất này được gọi là God’s algorithm. God’s number chính là đường kính của đồ thị Cayley của nhóm cục Rubik (xem thêm cái này). Nhóm này có tất cả 12! 2^{12} 8! 3^8 / 12 = 43252003274489856000 thành viên — cỡ khoảng 519 quintillion. (Cho nên đừng mong chạy thuật toán Dijkstra tìm God’s number.)

Trước Rubik, năm 1970 Larry Nichols — người Canada — đã đăng ký bằng sáng chế cho phiên bản 2x2x2 của trò này. Rubik chế ra cục Rubik năm 1974 và đăng ký bằng sáng chế năm 1975. Còn một chú người Nhật, một chú người Anh cũng đăng ký các bằng sáng chế cho các “khối” tương tự trong thập niên 70. Hồi đó chưa có Internet, và khối XHCN ít giao lưu thông tin với phương Tây, do đó chắc là các sáng chế này độc lập nhau.

Đọc tiếp »

Chủ đề Vui - Giải Trí | Phản hồi »

Cân xu

Bạn Huân hỏi về một bài toán đố cổ điển: bài toán cân xu tìm xu giả. Phiên bản thường nghe là như thế này: cho 12 đồng xu trong đó có 1 đồng xu giả (không biết nặng hay nhẹ hơn các đồng khác) và một cái cân thăng bằng, cân 3 lần tìm đồng xu giả.

Có rất nhiều biến thể (tổng quát) của bài toán này. Xem bài báo này chẳng hạn. Cho n đồng xu, b cái cân, k đồng xu giả, có thể biết hoặc không biết trước là nặng hay nhẹ hơn các đồng thật; phép thiết kế chiến lược cân có được “adaptive” hay không, vân vân. Thật ra câu này hỏi bác Văn là thích hợp nhất. Bác Văn có mấy bài báo rất thú vị về các biến thể tổng quát của bài toán cân xu.

Trong khuôn khổ bài viết này, ta chỉ xét một biến thể cổ điển sau:

(Một phiên bản của bài toán tìm xu giả) Cho n đồng xu, 1 đồng giả không biết nặng hay nhẹ hơn các đồng thật thế nào, và một cái cân. Tìm số lần cân w ít nhất để chỉ ra đồng giả (nếu có) và chỉ ra luôn là nó nặng hay nhẹ hơn các đồng thật.

Câu hỏi này thật ra có hai phần: phần 1 là tìm một chiến lược chỉ ra đồng giả dùng w lần cân, và phần 2 là chứng minh rằng w-1 lần cân thì không đủ để chỉ ra đồng giả. Ta sẽ tìm liên hệ giữa wn. Phần 2 thú vị hơn phần 1, nhưng về cơ bản cũng là chặn thông tin. Do việc tìm chặn thông tin là kỹ thuật rất phổ biến trong thuật toán và lý thuyết tính toán, chúng ta sẽ duyệt qua cả hai phần.

Đọc tiếp »

Chủ đề Combinatorics, Thuật Toán | 6 phản hồi »