Học Khoa Học Máy Tính nên đọc sách gì?
Bạn đang xem tài liệu "Học Khoa Học Máy Tính nên đọc sách gì?", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
hoc_khoa_hoc_may_tinh_nen_doc_sach_gi.pdf
Nội dung text: Học Khoa Học Máy Tính nên đọc sách gì?
- Học Khoa Học Máy Tính nên đọc sách gì? Bạn trantempo hỏi một danh sách các sách nên đọc trong KHMT. Bạn Nguyên đã đưa một danh sách sơ bộ. Tôi sẽ cập nhật từ từ vào danh sách dưới đây trong một vài tuần tới để có một danh sách hoàn tất hơn. (Cần về nhà duyệt lại tủ sách). Các bạn có thể bình luận và thêm vào các quyển sách mà bạn ưa thích. 1. Phân tích thiết kế thuật toán cơ bản (cập nhật ngày 1 tháng 10, 2007) 2. Phân tích thiết kế thuật toán nâng cao (cập nhật ngày 1 tháng 10, 2007) 3. Combinatorics (bao gồm lý thuyết đồ thị và toán rời rạc) (cập nhật ngày 2 tháng 10, 2007) 4. Xử lý ngôn ngữ tự nhiên (danh sách của anh Bạch Hưng Nguyên) (cập nhật ngày 2 tháng 10, 2007) 5. Machine learning và statistics (danh sách của anh Nguyễn Xuân Long) (cập nhật ngày 8 tháng 10, 2007) 1. Phân tích và thiết kế thuật toán (cơ bản): hiện nay có 3 quyển textbooks được dùng khá phổ biến, trong đó tôi thích quyển của Kleinberg và Tardos nhất. Tuy nhiên, từ quan điểm cá nhân thì tôi chưa thấy hài lòng với cả 3 vì các lý do khác nhau, mặc dù cả ba quyển đều rất tốt. 1. Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, Introduction to Algorithms (2e), 1180pp, ISBN: 0262032937, MIT Press, September 2001. 2. Jon Kleinberg, Éva Tardos, Algorithm Design, 864 pages, Addison Wesley, ISBN-10: 0321295358, ISBN-13: 978-0321295354, March 16, 2005. 3. S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, McGraw Hill, 2007. Hồi trước có quyển của Aho-Hopcroft-Ullman. Bây giờ đã khá lỗi thời, ít ai dùng. 1. Alfred V. Aho John E. Hopcroft Jeffrey Ullman, Data Structures and Algorithms, 427pp. ISBN: 0201000237, Addison Wesley, January 1983. Tiếc rằng Robert Tarjan không viết sách giáo khoa, nếu không sách về data structure của ông hẳn phải rất hay. Hiện nay không thể dạy thuật toán cơ bản mà không dạy về NP-Completeness và các phương pháp xác suất. Do đó, các quyển sau đây cũng rất cần thiết: 1. Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 338pp. ISBN: 0716710455, W. H. Freeman Company, November 1990.
- 2. Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press (January 31, 2005) Tôi xếp 3 tập của Knuth vào dạng “cao cấp hơn”, trong trường hợp bạn đang thắc mắc. Về lecture notes (dạng presentation) thì tôi thấy notes của tôi khá tốt (từ từ đến cuối học kỳ sẽ có toàn bộ notes.) 2. Phân tích và thiết kế thuật toán (cao cấp hơn) Khi nói đến phân tích và thiết kế thuật toán cao cấp, ta thường phải xem xét các đề tài cụ thể để giới thiệu. Các quyển sách cao cấp thường được viết về một đề tài nào đó: approximation algorithms, randomized algorithms, linear programming, convex programming, approximate counting, combinatorial optimization, network flows, algorithmic game theory, vân vân. Tôi sẽ gộp chung chúng lại và giới thiệu một vài quyển tiêu biểu. 1. Donald Knuth, The Art of Computer Programming Volumes 1, 2, 3, Addison Wesley. Vijay Vazirani, Approximation Algorithms, Springer-Verlag, 397 pages hardcover, ISBN: 3-540-65367-8, published 2001. 1. Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, 492 pages, Cambridge University Press (August 25, 1995), ISBN: 0521474655 2. Vašek Chvátal, Linear Programming, W. H. Freeman, 1983; 478pp. ISBN: 0716715872, W. H. Freeman Company, January 1983. 3. Dorit Hochbaum (Editor), Approximation Algorithms for NP-Hard Problems, 624 pages ; Brooks/Cole Pub Co; ISBN: 0534949681; 1st edition (July 26, 1996) 4. Alexander Schrijver, Theory of Linear and Integer Programming, 484pp. ISBN: 0471982326, Wiley, John & Sons, Incorporated, June 1998. 5. Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications; Unabridged edition (January 29, 1998). 6. Mark Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity (Lectures in Mathematics. ETH Zürich), Birkhäuser Basel; 1 edition (April 28, 2003) 7. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows: Theory, Algorithms, and Applications, Hardcover, 1st ed., 846pp., ISBN: 013617549X, Prentice Hall, February 1993. 8. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani (editors), Algorithmic Game Theory, Cambridge University Press, 2007.
- 9. Mark de Berg, M. van Krefeld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Second Edition, Springer; 2nd rev. ed. edition (February 18, 2000). Đây là tôi hoàn toàn chưa đụng tới rất nhiều các đề tài quan trọng khác: algorithmic number theory, algorithmic coding theory, computational biology, v.v. Chú ý: Ngoài ra, không thể nghiên cứu thuật toán hiện đại mà không có hiểu biết sâu sắc về lý thuyết độ phức tạp (computational complexity theory), lý thuyết đồ thị và toán rời rạc, lý thuyết xác suất và lý thuyết thông tin, toán tối ưu và toán ứng dụng, thậm chí cả hình học và giải tích cơ bản (cần cho computational geometry), hay lý thuyết số (cần cho các thuật toán cryptography). Tôi sẽ giới thiệu vài quyển về các đề tài này trong vài ngày tới. 3. Combinatorics (bao gồm lý thuyết đồ thị và toán rời rạc). Combinatorics rất rộng, liên quan mật thiết đến rất nhiều nhánh khác nhau của toán học và khoa học máy tính. Dưới đây tôi chỉ liệt kê một sanh sách các sách tôi đã đọc và thấy hữu dụng trong nghiên cứu và trong phát triển tư duy toán học cho KHMT. Nghĩa là không kể những thứ hữu dụng mà tôi không biết gì cả như Additive Combinatorics của bác Terry Tao và bác Vũ Hà Văn. 3.1 Toán rời rạc phổ thông. Hiển nhiên sinh viên học KHMT phải biết toán rời rạc. Tuy nhiên, tôi cực kỳ khó chịu với loại toán rời rạc thường được dạy ở bậc đại học nói chung, vì hai lý do: (1) lớp toán rời rạc kiểu này không chuẩn bị đủ kiến thức cho sinh viên học thêm lên, (2) và nó cho sinh viên một bức tranh bèm nhèm về toán rời rạc, dễ làm sinh viên hiểu không đúng về tầm mức của toán rời rạc. Dĩ nhiên tôi hiểu rằng chương trình đại học thì có giới hạn, còn bể kiến thức thì vô cùng, do đó cái “khó chịu” này của tôi không có cơ sở, Chỉ nhân đây càm ràm để “xả stress” là chính. Có bốn quyển sách “phải đọc” về toán rời rạc cho sinh viên học KHMT (và cả sinh viên toán): 1. J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press; 2nd edition (December 15, 2001). Rất tuyệt vời! Mỗi chương là một đề tài riêng biệt, từ đồ thị đến generating functions, từ design theory đến coding theory, từ q-series đến extremal set theory, v.v. đều có cả. Đa số các bài tập đều không tầm thường. Nếu bạn muốn biết combinatorics thật sự là gì, mà không có thời gian đọc nhiều quá, thì quyển này là bắt buộc! 2. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Professional. Viết bởi computer scientists cho computer scientists. Tất cả
- những thứ sinh viên KHMT cần biết về asymptotic analysis. Kiểu Knuth. Nghĩa là cực kỳ cụ thể và chi tiết về phương pháp. Dĩ nhiên, phạm vi của quyển này rất hẹp, vì đề tài và đối tượng rất cụ thể. 3. Laszlo Lovasz, Combinatorial Problems and Exercises, American Mathematical Society; 2 edition (June 26, 2007). Vừa ra 2nd edition. Cách duy nhất để học toán rời rạc là làm thật nhiều bài tập. Bạn hoàn toàn có thể trở thành một chuyên gia hạng ruồi về graph theory và extremal set theory bằng cách ngồi giải bài tập trong sách này. Nếu bạn đang lấy lớp combinatorics nào đó, nhiều khả năng là thầy của bạn lấy một vài bài tập trong này ra làm bài tập về nhà hoặc cả bài kiểm tra. 4. Martin Aigner, Günter M. Ziegler, and K.H. Hofmann, Proofs from THE BOOK, Springer; 3rd ed. edition (November 13, 2003). Tôi không biết là quyển này đã ra đến 3rd edition, tôi chỉ có 1st edition. Nói đúng ra, quyển này không phải viết về toán rời rạc. Nhưng tư tưởng của nó lại rất tương đồng với tư tưởng của toán rời rạc mà tôi cảm nhận. Khi thấy một chứng minh đẹp như mơ, Erdos hay nói rằng “chứng minh này chắc là phải nằm trong một quyển sách của thượng đế, quyển sách chứa các chứng minh đẹp nhất”. Đó là tư tưởng chính của quyển sách. Nó chứa một bộ sưu tập các chứng minh đẹp như mơ. Dân yêu toán, ai lại không mơ? 3.2 Lý thuyết đồ thị (bao gồm cả algebraic graph theory). Không có nhánh nào của KHMT mà lại không cần kiến thức cơ bản về lý thuyết đồ thị. Sách mở đầu của lý thuyết đồ thị thì có cực kỳ nhiều. Tôi vẫn thường giới thiệu quyển của West cho sinh viên vì thấy nó vừa phải và phù hợp với dân máy tính. Quyển bài tập của Lovasz ở trên có vài chương về lý thuyết đồ thị rất hay. Tôi quan tâm đến algebraic graph theory nó là công cụ chính để phân tích các expander graphs (dùng cực kỳ nhiều trong complexity theory, algorithm design, randomized algorithms, coding theory, networking, v.v.) 1. Douglas West, Introduction to Graph Theory, Prentice Hall; 3 edition (December 1, 2007). Tôi thấy phạm vi đề tài của quyển này rất thích hợp cho dân học KHMT, lại rõ ràng dễ hiểu. Sau khi đọc xong một quyển giới thiệu ngành như quyển này, các quyển kế tiếp đều phải đọc theo đề tài, như algebraic graph theory, extremal graph theory, graph coloring, matching theory, v.v. Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems, Wiley-Interscience; 1st edition (December 1994). Đây là tham khảo kinh điển về các bài toán tô màu đồ thị, dùng cực nhiều trong KHMT. 1. L. Lovász and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, 29, North-Holland Mathematics Studies, 121. Tôi tin rằng dân làm về graph theory và combinatorial optimization đều bí mật đọc
- quyển này Một đề tài rất đẹp và rất khó tìm thấy ở sách khác là về các Pfaffian và Permanent. Đặc biệt là về matching trên bipartite graphs thì tất cả những thứ tôi biết đều học từ quyển này ra, và đã dùng kiến thức học được trong ít nhất 5 bài báo! Norman Biggs, Algebraic Graph Theory, Cambridge University Press. Quyển sách be bé này giới thiệu algebraic graph theory rất tốt. Đủ để dùng làm nhiều thứ, bao gồm hiểu các thứ liên quan đến expanders. 1. Dragos M. Cvetkovic, Michael Doob, Horst Sachs, Spectra of Graphs: Theory and Applications, Academic Press; 3rd Revised edition (August 1, 1997). Đây là sách tham khảo chính về algebraic graph theory. 2. Fan Chung, Spectral Graph Theory, American Mathematical Society (May 1997). Sách viết rất tốt và rõ ràng. Cái dở duy nhất là bà Fan Chung lại chọn bộ Lapacian eigenvalues thay vì bộ eigenvalues của đồ thị như trong các applications thường dùng. Chuyển qua chuyển lại các kết quả rất mất thời gian. 3.2 Phương pháp xác suất (bao gồm random graphs). Phương pháp xác suất là một trong những công cụ chính của theoretical computer science, với ứng dụng ở khắp mọi nơi. Trong complexity theory & algorithms ta dùng phương pháp xác suất phân tích và thiết kế PCP, randomized (approximation) algorithms, derandomization, pseudo-random number generation, v.v. Trong mạng máy tính ta có randomized routing, randomized MAC protocols, blocking analysis of switches and routers, v.v. Trong cơ sở dữ liệu gần đây phát triển mạnh probabilistic databases, v.v. Tôi sẽ giới thiệu sách về xác suất và thống kê trong một đề mục riêng. Phần dưới đây chỉ nói riêng về phương pháp xác suất theo nghĩa của Erdos. 1. Noga Alon and Joel H. Spencer, The Probabilistic Method, Wiley- Interscience; 2 Sub edition (August 24, 2000). Kinh điển! Không có gì phải bàn. 2. Béla Bollobás, Random Graphs, Cambridge University Press. Lại một quyển kinh điển nữa! Quyển của Mitzenmacher và Upfal đã giới thiệu trong phần giải thuật. 3.4. Enumerative combinatorics. 1. Richard Stanley, Enumerative Combinantorics Vol. 1 & 2, Cambridge University Press. Kinh điển! Chứa hầu hết tất cả những thứ mà dân khoa học máy tính cần biết về enumerative combinatorics.
- Dennis Stanton and Dennis White, Constructive combinatorics, Springer; 1 edition (May 15, 1986). Quyển này có lẽ ít người biết nhưng tôi thấy rất hay cho dân học máy tính. Nó viết về enumerative combinatorics từ góc nhìn thuật toán và bijective proofs. Tôi đã lấy lớp của cả hai vị Dennis. Bác Stanton là người thầy có ảnh hưởng lớn nhất đến triết lý giáo dục của tôi. 1. David M. Bressoud, Proofs and Confirmations: The Story of the Alternating-Sign Matrix Conjecture, Cambridge University Press (August 13, 1999). Quyển này phải nói là trên cả tuyệt vời. Quyển sách nói về một conjecture rất nổi tiếng gọi là Alternating Sign Martrix Conjecture và duyệt lại toàn bộ quá trình người ta “tấn công” conjecture này. Tôi đã từng bỏ 6 tháng vật lộn với nó . Kết thúc bằng các công trình của Zeilberger và Kuperberg. Nó tuyệt vời ở chỗ, ngoài việc dùng làm sách giáo khoa cho một vài lớp enumerative combinatorics rất tốt, nó vẽ ra rất rõ ràng quá trình phát triển và phương pháp tư duy của một nhánh toán học dựa trên một câu chuyện cụ thể, một đề tài nghiên cứu cụ thể. Terry Tao có viết một bài hàm chứa ý tưởng tương tự về tính liên thông của các phát triển trong toán. Đến bây giờ mở sách này ra đọc tôi vẫn tìm thấy những cái mới, và cả các bài toán chưa giải được. Enumerative combinatorics là “tình yêu thời niên thiếu” của tôi, và quyển này là quyển tốt nhất giải thích tại sao tôi vẫn còn day dứt (Trong quyển này có nói về một thuật toán tính định thức của tác giả truyện Alice lạc vào xứ thần tiên!) 2. George E. Andrews, The Theory of Partitions, Cambridge University Press (July 28, 1998). George Andrews là người tìm ra những quyển sổ tay mất tích của Ramanujan. Quyển sách của ông nằm giữa giải tích, lý thuyết số, và enumerative combinatorics. Có lẽ định lý hay nhất trong sách là công thức tính tổng số integer partitions của một số nguyên bất kỳ. Đọc sách này ta sẽ thấy generating functions mạnh như thế nào, và được dùng như thế nào trong các vấn đề cực kỳ hóc búa của lý thuyết số. Ngoài ra, nó cũng là quyển sách rất tốt về các hyper-geometric series và q-series. Tuyệt cú mèo! Có một lần tôi nghe George Andrews trình bày ở một hội nghị, ông mang theo một cuộn giấy to oành in một chương trình ông viết từ hồi đầu thập niên 70 để tìm các conjectures trong enumerative combinatorics. Ông kéo cuộn giấy đi từ đầu đến cuối phòng, chưa hết một nửa. 3.5 Algebraic combinatorics. Tư tưởng của nhánh này rất gần, theo một nghĩa nhất định, với các phương pháp đại số dùng trong coding theory và complexity theory hiện đại. Nó lại liên quan mật thiết đến giải tích của các hàm vuông góc. Tôi làm M.S. Thesis Toán trong nhánh này. Mặc dù bây giờ không làm về nó nữa, nhắc lại vẫn còn thấy “nhiệt huyết” bừng bừng . Ngoài ra, nhánh này cũng là anh em cột chèo với algebraic graph theory, rất cần thiết trong cả complexity theory lẫn một số bài toán trong mạng máy tính! Đó là chưa kể liên minh sống còn với
- representation theory cũng lại được dùng trong KHMT (như trong loạt bài về nhân ma trận tôi đang viết dở). 1. Chris Godsil, Algebraic Combinatorics, Chapman & Hall/CRC (April 1, 1993). 2. Chihara, An Introduction to Orthogonal Polynomials, Routledge; 1 edition (January 1, 1978). Quyển kinh điển về các đa thức vuông góc. 3. George E. Andrews, Richard Askey, Ranjan Roy, Special Functions, Cambridge University Press; New Ed edition (February 15, 2001). Tất cả những thứ bạn cần biết về các hàm đặc biệt! William Fulton, Young Tableaux: With Applications to Representation Theory and Geometry, Cambridge University Press (December 28, 1996). 1. I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, USA; 2 edition (June 30, 1999). Quyển này và quyển của Fulton là kinh điển về symmetric functions. 3.6 Extremal set theory, extremal set systems, và design theory. Những thứ này thì dùng làm gì trong KHMT? Một vài ví dụ nhỏ: chúng liên quan mật thiết với lý thuyết thử nhóm (group testing) được dùng trong DNA library screening (bio- computing), trong thiết kế MAC protocols và thử lỗi của mạng quang (networking), và thiết kế thuật toán nói chung. Design theory lại cũng liên quan chặt chẽ với coding theory (sẽ giới thiệu sách sau) dùng trong communications và trong complexity theory. 1. Konrad Engel, Sperner Theory, Cambridge University Press. Phát triển lý thuyết của một định lý rất đơn giản và hùng mạnh trong topology: định lý Sperner. 2. Bela Bollobas, Combinatorics, Cambridge University Press. Nhỏ và hiệu quả! 3. A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance Regular Graphs, Springer (August 1989). Nhiều bài toán thiết kế các cấu trúc extremal có thể được mô hình hóa bằng distance regular graphs: một loại đồ thị rất giàu có về cấu trúc đại số, nhờ đó bài toán trở nên tổng quát hơn (dùng công cụ của đại số), và đôi khi dễ dàng hơn. 4. Ding-Zhu Du and Frank K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific Publishing Company; 2nd edition (May 2000). Quyển này là tham khảo chính (và duy nhất) cho lý thuyết thử nhóm. Nó là dạng monograph chứ không phải textbook, dùng làm tham khảo. 4. Xử lý ngôn ngữ tự nhiên (danh sách của anh Bạch Hưng Nguyên).
- Sách cơ bản: [1] Manning & Schutze, Foundation of Statistical NLP - (có online nếu có access vào MIT library) [2] Jurasky & Martin, Speech&Language Procesing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, 2nd edition. Tham khảo thêm: [3] James Allen, Natural Language Understanding [4] Fred Jelinek, Statistical Method for Speech Recognition [5] Xudong Huang et al, Spoken Language Processing Lộ trình tự đọc & học trong 1 hoặc 2 học kì theo thứ tự sau ——– Chương 1+2+3+4 - [1]: Introduction / Mathematical Foundations/ Linguistic Essential / Corpus-based Work Chương 7 - [2]: Phonetics ——– Chương 6 - [1]: Statistical Inference: n-gram Models over Sparse Data Chương 4 - [2]: N-grams ——– Chương 8 - [5]: Hidden Markov Models Chương 2 - [4]: Hidden Markov Models Chương 4 - [2]: Word Classes and Part-of-Speech Tagging Chương 6 - [2]: Hidden Markov and Maximum Entropy Models ——– Chương 3 - [3]: Grammar and Parsing Chương 12 - [2]: Formal Grammars of English Chương 11 - [1]: Probabilistic Context Free Grammar Chương 12 - [1]: Probabilistic Parsing Chương 13 - [2]: Parsing with Context-Free Grammars Chương 14 - [2]: Statistical Parsing ——–
- Chương 3 - [2]: Words and Transducers ——– Chương 22 - [2]: Information Extraction ——– Chương 25 - [2]: Machine Translation ——– Chương 15 - [1]: Topics in Information Retrieval ——– Chương 16 - [1]: Text Categorization ——– Lộ trình này giới thiệu chuyên sâu về phương pháp thống kê NLP, mô hình n- gram , mô hình Markov ẩn, & kĩ thuật phân tích câu (parsing). Sau đó là giới thiệu sơ qua một số topics mà NLP đóng vai trò quan trọng như Trích chọn Thông Tin (Information Extraction), Dịch tự động (Machine Translation), Khai Thác Thông Tin (Information Retrieval), & Phân Loại Văn Bản (Text Categorization). Về cơ bản sau khi xong lộ trình này là đủ để bắt tay vào chuyên sâu các vấn đề trong NLP. Rất nhiều topics của NLP không đề cập trong lộ trình này ví dụ như: Các máy Hữu hạn trạng thái (Finite-state Machines), Các kĩ thuật học máy (Machine Learning techniques), Nhận dạng tiếng nói (Speech Recognition), Tổng hợp tiếng nói (Speech Synthesis), Hệ thống Hỏi-Đáp (Q&A systems). 5. Machine learning và statistics Chuyển qua machine learning và statistics What? Statistics là cả một chuyên ngành riêng biệt sao phải học? Có lần một người bạn tôi hỏi David Blackwell, khi cậu ta mới chập chững vào PhD program. Rằng, có cái gì hay ho tôi nên theo đuổi trong statistics? Blackwell trả lời, nên học machine learning và nonparametric statistics. Tôi gộp cả ML và Stats vì tôi coi hai ngành này là một, dẫu về truyền thống và định hướng hiện tại thì có những sự khác biệt nhất định. Có rất nhiều sách hay trong ngành, nhưng chỉ giới thiệu một số mà tôi quen thuộc hơn cả. Như vậy còn một số sách hay mà chưa được list, xin bạn đọc bổ sung qua comments. Những quyển đánh dấu sao (*) có thể dùng làm sách nhập môn tốt. Ngoài ra, (+) cũng là những quyển sách tôi ưa thích.
- 5.1. Sách giới thiệu với hương vị machine learning 1. T. Michell, Machine Learning, Tom Mitchell, McGraw Hill, 1997. Quyển này từng là quyển sách đầu tay cho dân ML, nhưng nay nó đã lạc hậu về nội dung. 1. R. Duda, P. Hart and D. Stork. Pattern Classification. Wiley, 2000. 2. K. Fukunaga. Statistical pattern recognition. AP, 1990. 3. (*) J. Friedman, T. Hastie and R. Tibshirani. The elements of statistical learning. Springer, 2001. 5.2. Sách tập trung vào các dạng mô hình học thống kê A. Các mô hình tương đối khái quát 1. (*) C. Bishop, Neural networks for pattern recognition. Clarendon Press, 1995. 2. S. Haykin, Neural networks: A comprehensive foundation. Prentice Hall, 2nd Edition, 1998. 3. (*) B. Scholkopf and A. Smola, Learning with kernels. MIT Press, 2002. 4. J. Shawe-Taylor and N. Cristianini, Kernel methods for pattern analysis. Cambridge Univ Press, 2004. 5. J. Shawe-Taylor and N. Cristianini, Support vector machines and other kernel-based learning methods. Cambridge Univ Press, 2000. 6. (+) S. Mallat, A wavelet tour of signal processing, Academic Press, 2nd Edition, 1999. 7. (*) M. Jordan, An introducition to probabilistic graphical models. Quyển sách này tuy chưa xuất bản nhưng rất nhiều trường sử dụng làm tài liệu cho graduate course. Nếu bạn ở VN và định dạy một lớp về graphical models, có thể email tác giả để xin phép sử dụng cho lớp. B. Các mô hình chuyên sâu và/hoặc hẹp hơn: 1. T. Anderson, An Introduction to Multivariate Statistical Analysis (Wiley Series in Probability and Statistics), 3rd Edition, 2003. Kinh điển và hữu ích về (parametric) multivariate data, đặc biệt về gaussian (tốt cho việc tham khảo kết quả). 2. (+) L Devroye, L. Gyorfi and G. Lugosi, A Probabilistic Theory of Pattern Recognition. Tập trung nhiều vào lý thuyết về classification.
- 1. (+) L. Gyorfi, M. Kohler, A. Kryzak and H. Walk, A Distribution-Free Theory of Nonparametric Regression, 2002. 2. Anthony and P. Bartlett. Neural Network Learning: Theoretical Foundations, 1999. 3. V. Vapnik, Statistical learning theory, 1998. Tác giả là một trong những người có đóng góp nền móng cho phát triển cả lý thuyết và thuật toán machine learning. 4. M. Kearns and U. Varizani, An Introduction to Computational Learning Theory, MIT Press, 1994. Quyển sách serious đầu tiên của dân machine learning về machine learning theory. C. Các mô hình cho spatial data: 1. (+) G. Wahba, Spline models for observational data, SIAM, 1990. Giới thiệu cách sử dụng RKHS trong regression. 1. S. Banerjee, B. Carlin and A. Gelfand, Hierarchical Modeling and Analysis for Spatial Data. (Các mô hình hierrchical Bayesian models). 1. M. Stein, Interpolation of spatial data. Springer-Verlag, 1999. Lý thuyết hơn. 2. N. Cressie, Statistics for spatial data, Wiley and Sons, 1993. D. Các mô hình về sequential decision-making (such as reinforcement learning, online learning, etc ): 1. (*) A. Barto & R. Sutton, Reinforcement learning: An introduction, MIT Press, 1998. Giới thiệu về RL một cách nhẹ nhàng. 1. D. Bersekas & J. Tsitsiklis, Neurodynamic programming, Athena Scientific, 1996. Xây dựng lý thuyết RL một cách chặt chẽ hơn. 1. D. Bertsekas, Dynamic programming and Stochastic control, Athena Scientific, 1995. Cesa-Bianchi and Lugosi, Prediction, Learning, and Games, Cambridge Univ Press, 2006.
- 1. (*) A. Wald, Sequential analysis, 1947. Quyển sách đã khởi đầu cho cả một branch (Bellman tổng quát lên thành dynamic programming and control). 2. Shiryaev, Optimal stopping rules, 1978. Điển hình sách kiểu Nga, lý thuyết hơn. Đi sâu vào Bayesian formulations của những v/đ liên quan đến stopping rules, trong đó sequential analysis (sequential hypothesis testing, sequential change-point problems) chỉ là những trường hợp đặc biệt. 3. D. Siegmund, Sequential analysis, 1985. Đi sâu hơn vào frequentist formulations. 4. A. Sen, Sequential nonparametrics. Khá sâu. E. Các dạng mô hình/topics khác Ngoài ra, một số dạng mô hình cụ thể cũng có rất nhiều sách tham khảo, như mô hình về time series, mô hình về finance (stochastic calculus), mô hình linear/generalized linear/mixed linear các kiểu, mô hình state-space. Một số topics thú vị, như về active learning/ experiment design, concentration of measures, .Tuy nhiên scope hoặc hơi xa hoặc hơi sâu so với danh sách trên. 5.3. Phương pháp thống kê tổng quát Phần lớn dân làm machine learning/statistics sẽ đi vào các dạng mô hình cụ thể, mỗi loại thích hợp cho một ứng dụng nào đó. Các mô hình đó giải quyết câu hỏi “how” khi cần học một mô hình (hay khái niệm). Để biết “why” thì cần đọc một số quyển sách về general statistical methodogy. Thực ra, một số quyển sách mang tính lý thuyết trong machine learning, như Vapnik, Devroye-Gyorfi-Lugosi, hoặc Anthony-Bartlett cũng có thể được xếp vào đây, nhưng focus của chúng còn hẹp so với các tác phẩm của các nhà thông kế. Trường phái frequentist: 1. (*) P. Bickel and K. Doksum, Mathematical statistics: basic ideas and selected topics, Prentice Hall, 2nd Edition, 2000. 2. (*) R. Keener, Statistical theory: A Medley of Core Topics. Hình như sắp xuất bản. Viết rât rõ ràng, không sâu nhưng giới thiệu khá nhiều topics. 3. (+) E. Lehmann & J. Romano, Testing statistical hypotheses, Springer, 3rd Edition, 2005. 4. (+) E. Lehmann & G. Casella, Theory of Point Estimation, Springer, 2nd Edition, 1998. Hai quyển sách trên của Lehmann (và các đồng tác giả ở các editions sau) được coi là bible của classical (frequentist) statistics. Trường phái Bayesian:
- 1. (+) J. Berger, Statistical decision theory and Bayesian analysis, Springer- Verlag, 2nd Edition, 1985. Được coi là một bible của Bayesian statistics. Tác giả có một cái nhìn rất cân bằng giữa frequentist và bayesian methodologies. 2. (*) C. Roberts, The Bayesian choice, Springer, 2nd Edition, 2007. Có lẽ sẽ là một bible trong tương lai, hiện đại hơn quyển sách của Berger. 3. (+) J. Bernardo and A. Smith, Bayesian theory, Wiley, 1994. Đi sâu vào nhiều vấn đề foundational của statistical inference. 5.4. Bayesian computation (Markov chain Monte Carlo) 1. J. Liu, Monte Carlo Strategies in Scientific Computing, Springer, 2001. 2. A. Gelman, J. Carlin, H. Stern and D. Rubin, Bayesian data analysis, Chapman and Hall, 2nd Edition, 2003. 5.5 Sách về information and communication theory Thực ra tất cả các sách về information theory có thể xếp vào mục “asymptotic theory”. Tất nhiên xuất phát điểm thì hoàn toàn khác: đó là từ các vấn đề trong communication và data compression. 1. (*) T. Cover & J. Thomas, Elements in information theory, Wiley, 2nd Edition, 2006. Viết rất rõ ràng. 1. R. Gallager, Information theory and reliable communication. Kinh điển! 2. D. McKay, Information theory, inference and learning algorithms, 2003. Free on-line! 5.6 Asymptotic theory Mọi lý thuyết sâu sắc trong xác suất và thống kê đều phải đi về asymptotics! Tại sao? vì asymptotics là cách duy nhất (?) chúng ta có thể nói được một cách chắc chắn về tính chất của các hiện tượng không chắc chắn (uncertain phenomena). 1. (*) van der Vaart, Asymptotic statistics, Cambridge Univ Press. 2. (*) D. Pollard, Convergence of stochastic processes. Free on-line! 3. (*) P. Billingsley, Convergence of probability measures, Wiley, 1968. Kinh điển. 4. (+) A. van der Vaart & J. Wellner, Weak convergence and empirical processes, 1998.
- 5. (+) S. van de Geer, Empirical processes in M-estimation, Cambridge Univ Press, 2000. 6. L. Le Cam, Asymptotic Methods in Statistical Decision Theory, 1986. Le Cam là một trong những nhà thống kê lý thuyết sâu sắc nhất của thế kỷ vừa rồi, nhưng quyển này khá khó nhằn. 1. I. Johnstone. Theory of function estimation. Free on-line. 2. P. Bickel, C Klassen, Y. Ritov & J. Wellner, Efficient and adaptive estimation for semiparametric models, Springer 1993. Nhiều bài báo trên Annals of Statistics hóa ra chỉ giải quyết một khía cạnh nào đó của một vấn đề tổng quát hơn trong quyển sách này. Tuy nhiên ngay cả các tác giả cũng khiêm tốn nói là họ chỉ phát triển những ý tưởng căn bản của Le Cam mà thôi.