HM3: Mô hình PAC. HM5: Mô hình giả thuyết không nhất quán và định lý hội tụ đều Vapnik-Chervonenkis. Trong các bài trước ta đã đề cập đến một số vấn đề không học được trong mô hình PAC và tầm quan trọng của việc biểu diễn lớp giả thuyết như thế nào. Có lẽ [...]
HM2 — Thêm vài ví dụ trong mô hình nhất quán HM4: Độ phức tạp mẫu và VC dimension. 3. Mô hình có lẽ xấp xỉ đúng (Probably Approximately Correct) (viết tắt là mô hình PAC) Hạn chế lớn nhất của mô hình nhất quán, như đã nói, là nó không đếm xỉa gì đến [...]
HM1: Học máy từ góc nhìn của lý thuyết tính toán. HM3: Mô hình PAC. Trong bài trước ta đã định nghĩa cụ thể mô hình nhất quán. Có một vài điểm tinh tế cần nói rõ hơn. Thứ nhất, tổng số concepts trong lớp concepts đã biết thường là rất lớn, có thể là [...]
HM2 — Thêm vài ví dụ trong mô hình nhất quán Computational Learning Theory (COLT) bắt đầu từ bài báo kinh điển của Valiant hồi 1984 trên tờ CACM. (Thế mới thấy CACM bây giờ chán, không còn thấy original research articles mấy nữa. Hy vọng là cố gắng cải tổ của Moshe Vardi mới [...]
Bên gỡ rối tơ lòng, bạn Thắng hỏi: Trong một cuốn sách em thì nó nói rằng nếu có cái điều kiện gì gì đó thì A |– B sẽ suy ra A |= B. Nhờ anh chỉ giùm cho em thấy sự khác biệt giữa 2 khái niệm A|–B và A|== B này cái…rồi [...]
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 [...]
Bản nháp báo cáo của một workshop do NSF tài trợ.
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.
Lần trước tôi link về số đặc biệt cho Turing của tờ Notices mà quên link đến số đặc biệt cho Kurt Godel.
Issue mới của tờ Notices là số đặc biệt về Alan Turing. Liên quan nhất đến blog KHMT là bài Turing Thesis, Theo cùng tinh thần bài Chung Qui Chỉ Tại Cantor.
Quyển Computers and Intractability: A Guide to the Theory of NP-Completeness của Garey và Johnson là tham khảo kinh điển về lý thuyết NP-đầy đủ. Trong 30 năm qua, Johnson vẫn tiếp tục viết các NP-complete columns để cho ta biết các cập nhật mới nhất về các bài toán NP-đầy đủ. Hồi xưa, ta [...]
Tôi đã nhắc đến Probabilistically Checkable Proofs trên blog này. Năm ngoái, Irit Dinur có một chứng minh “đơn giản” cho định lý PCP — một trong những định lý quan trọng nhất của Theoretical Computer Science trong vòng 15 năm đổ lại. Bài này thắng giải best paper của STOC 2006. Radhakrishnan và Sudan [...]
Một bài tổng quan rất rất hay của Avi Wigderson, bổ túc cho cái talk ông nói ở ICM 2006. Bài này đào sâu vào phần cuối (và các phát triển sau đó) của bài Chung Qui Chỉ Tại Cantor. Tôi tin rằng tất cả các sinh viên KHMT đều phải đọc qua bài của [...]
Một bài viết trong CACM mới đây mắc vài lỗi nghiêm trọng. Xem thảo luận ở complexity blog. Vụ này hứa hẹn nhiều hậu quả đầy màu sắc.
Sau lớp 11, chắc ai cũng biết định nghĩa (vô hạn các) hàm không liên tục. Tuy nhiên, có một số nhà toán học theo trường phái constructive mathematics cho rằng tất cả các hàm tính được (computable) đều liên tục. Andrej Bauer có một bài ngắn về đề tài này. Constructive Mathematics và intuitionism [...]
