Các bài báo kinh điển KHMT (8): Graphical models
Thực ra trong bài này tôi sẽ không chỉ nói về một bài báo kinh điển mà sẽ nói về cả một chùm bài về graphical models, một phương pháp biểu diễn và suy luận thống kê tổng quát và hữu hiệu đã, đang và sẽ được ứng dụng rộng khắp trong các ngành khoa học liên quan đến dữ liệu,
Graphical models là một loại ngôn ngữ để biểu diễn mô hình về dữ liệu bằng graph và lý thuyết xác suất. Khó có thể giới thiệu súc tích hơn về graphical models bằng đoạn trích sau đây:
"Graphical models are a marriage between probability theory and graph theory. They provide a natural tool for dealing with two problems that occur throughout applied mathematics and engineering -- uncertainty and complexity -- and in particular they are playing an increasingly important role in the design and analysis of machine learning algorithms. Fundamental to the idea of a graphical model is the notion of modularity -- a complex system is built by combining simpler parts. Probability theory provides the glue whereby the parts are combined, ensuring that the system as a whole is consistent, and providing ways to interface models to data. The graph theoretic side of graphical models provides both an intuitively appealing interface by which humans can model highly-interacting sets of variables as well as a data structure that lends itself naturally to the design of efficient general-purpose algorithms.
Many of the classical multivariate probabalistic systems studied in fields such as statistics, systems engineering, information theory, pattern recognition and statistical mechanics are special cases of the general graphical model formalism -- examples include mixture models, factor analysis, hidden Markov models, Kalman filters and Ising models. The graphical model framework provides a way to view all of these systems as instances of a common underlying formalism. This view has many advantages -- in particular, specialized techniques that have been developed in one field can be transferred between research communities and exploited more widely. Moreover, the graphical model formalism provides a natural framework for the design of new systems." --- Michael Jordan, 1998.
Graphical models ở những trường hợp đặc biệt nhất đã được sử dụng trong suốt thế kỷ trước: Mô hình dùng directed graphs đã được các nhà genetics sử du.ng trong pedegree analysis từ những thập niên 70 và trước đó. Mô hình Ising (cho undirected graphs) đuợc sử dụng từ đầu thế kỷ 20 để nghiên cứu về hiện tượng phase transition. Nhưng phải đến khi quyển sách kinh điển của Judea Pearl , giáo sư UCLA, ra đời thì graphical models mới được áp dụng rộng rãi.
Pearl, J. (1988). Probabilistic Inference in Intelligent Systems.
Morgan kaufmann, CA.
Công lớn của Judea Pearl là tổng quát hóa graphical models cho bất kỳ graphs và bất kỳ hàm xác suất nào. Ông còn phát kiến ra thuật toán belief propagation nổi tiếng để thực hiện inference trong graph, hiện được sử dụng rộng rãi trong machine learning, computer vision và coding theory. Pearl còn cho rằng graphical models mới là ngôn ngữ thích hợp cho knowledge representation trong ngành trí tuệ nhân tạo, chứ không phải là logic và những biến thể logic. Điều này gây ra một sự thay đổi lớn trong ngày TTNT, vốn bị thống trị bởi trường phái về logic của John McCarthy từ những ngày đầu cho đến hết thập niên 80.
Những thập niên 90 trở đi chứng kiến rất nhiều ứng dụng rực rỡ của graphical models trong các lĩnh vực xử lý dữ liệu, trong signal processing (speech recognition, vision), trong computational biology (DNA and protein analysis, phylogenetic analysis, ...), trong ngôn ngữ và text data. Một bài blog gần đây một ví dụ.
Xin liệt kê vài GMs tiêu biểu mà chúng ta hay được nghe thấy:
Graphical models là một loại ngôn ngữ để biểu diễn mô hình về dữ liệu bằng graph và lý thuyết xác suất. Khó có thể giới thiệu súc tích hơn về graphical models bằng đoạn trích sau đây:
"Graphical models are a marriage between probability theory and graph theory. They provide a natural tool for dealing with two problems that occur throughout applied mathematics and engineering -- uncertainty and complexity -- and in particular they are playing an increasingly important role in the design and analysis of machine learning algorithms. Fundamental to the idea of a graphical model is the notion of modularity -- a complex system is built by combining simpler parts. Probability theory provides the glue whereby the parts are combined, ensuring that the system as a whole is consistent, and providing ways to interface models to data. The graph theoretic side of graphical models provides both an intuitively appealing interface by which humans can model highly-interacting sets of variables as well as a data structure that lends itself naturally to the design of efficient general-purpose algorithms.
Many of the classical multivariate probabalistic systems studied in fields such as statistics, systems engineering, information theory, pattern recognition and statistical mechanics are special cases of the general graphical model formalism -- examples include mixture models, factor analysis, hidden Markov models, Kalman filters and Ising models. The graphical model framework provides a way to view all of these systems as instances of a common underlying formalism. This view has many advantages -- in particular, specialized techniques that have been developed in one field can be transferred between research communities and exploited more widely. Moreover, the graphical model formalism provides a natural framework for the design of new systems." --- Michael Jordan, 1998.
Graphical models ở những trường hợp đặc biệt nhất đã được sử dụng trong suốt thế kỷ trước: Mô hình dùng directed graphs đã được các nhà genetics sử du.ng trong pedegree analysis từ những thập niên 70 và trước đó. Mô hình Ising (cho undirected graphs) đuợc sử dụng từ đầu thế kỷ 20 để nghiên cứu về hiện tượng phase transition. Nhưng phải đến khi quyển sách kinh điển của Judea Pearl , giáo sư UCLA, ra đời thì graphical models mới được áp dụng rộng rãi.
Pearl, J. (1988). Probabilistic Inference in Intelligent Systems.
Morgan kaufmann, CA.
Công lớn của Judea Pearl là tổng quát hóa graphical models cho bất kỳ graphs và bất kỳ hàm xác suất nào. Ông còn phát kiến ra thuật toán belief propagation nổi tiếng để thực hiện inference trong graph, hiện được sử dụng rộng rãi trong machine learning, computer vision và coding theory. Pearl còn cho rằng graphical models mới là ngôn ngữ thích hợp cho knowledge representation trong ngành trí tuệ nhân tạo, chứ không phải là logic và những biến thể logic. Điều này gây ra một sự thay đổi lớn trong ngày TTNT, vốn bị thống trị bởi trường phái về logic của John McCarthy từ những ngày đầu cho đến hết thập niên 80.
Những thập niên 90 trở đi chứng kiến rất nhiều ứng dụng rực rỡ của graphical models trong các lĩnh vực xử lý dữ liệu, trong signal processing (speech recognition, vision), trong computational biology (DNA and protein analysis, phylogenetic analysis, ...), trong ngôn ngữ và text data. Một bài blog gần đây một ví dụ.
Xin liệt kê vài GMs tiêu biểu mà chúng ta hay được nghe thấy:
- Hidden Markov Models (HMM) (cho sequential analysis trong speech recognition, trong ngôn ngữ và văn bản, trong DNA và protein sequences)
- Các biến thể của HMM trong lĩnh vực activity recognition (G.S Bùi Hải Hưng ở SRI là một chuyên gia về vấn đề này)
- Phylogenetic tree models (để nghiên cứu về tiến hóa)
- Ising models (để nghiên cứu phase transition cho spin glass magnetic models, cũng được dùng trong computer vision để mô hình hình ảnh)
- Probabilistic latent semantic indexing models (để mô hình văn bản, ảnh)
- v.v.
Quả thật, mỗi graphical model thường đươ.c định nghĩa trên cơ sở hàm xác suất (hoặc potential function) trong từng clique của graph, mà mỗi clique đó lại được mô hình hóa bằng những mô hình kinh điển của ngành xác suất thống kê). Khả năng, sự định hướng và sự tham vọng về những vấn đề về tính toán của những người làm về KHMT cho phép họ nghiên cứu những mô hình đồ sộ và thực tế hơn mà những người làm về thống kê cổ điển không thể dám mơ tới.
GMs là một cơ sở hạ tầng tự nhiên cho nhiều ý tưởng hay, và có ảnh hưởng sâu và rộng, về thuật toán, xác suất thống kê, và vật lý thống kê trong suốt thời gian qua:
- Các thuật toán sampling Markov Chain Monte Carlo (MCMC) và biến thể (Gibbs sampling, Metropolis-Hasting)
- Thuật toán EM (Expectation-Minimization)
- Thuật toán deterministic theo kiểu message-passing, như belief propagation, mean -field theory
- Liên hệ giữa phase transition của Ising models trong vật lý thống kê, và computation complexity của thuật toán MCMC
- Liên hệ giữa statistical inference và optimization trong graphical models
Sau đây là một vài bài báo (hoặc là kinh điển hoặc là khá gần đây, mang tính chất giới thiệu và survey) đáng tham khảo:
David Spiegelhalter, Philip Dawid, Steffen Lauritzen and Robert Cowell.
Bayesian Analysis in Expert Systems. Statistical Science, Vol 8, No 3, 1993.
Michael I. Jordan. Graphical Models. Statistical Science, Vol 19, 140-155, 2004.
posted by Khanh Quan Ba at 3:34 AM
<< Home