Các bài báo kinh điển KHMT (8): Graphical models
Nguyễn Xuân Long | 24 tháng 09, 2005 | 
Bản để in
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:
- 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 (bác 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.
Ngành trí tuệ nhân tạo nói riêng và KHMT nói chung có nhiều sáng kiến có tính nhất thời, thường là mất giá trị rất nhanh sau một thời gian nóng sốt giả tạo. Tôi nghĩ rằng graphical models sẽ có giá trị vững chắc hơn và lâu dài hơn nhiều, vì nó được xây dựng trên nền tảng là những viên gạch của ngành thống kê cổ điển, nhưng lại có sự đóng góp của nghiên cứu về thuật toán và computational complexity.
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
Những nghiên cứu hiện nay còn tập trung vào việc phát triển và ứng dụng những mô hình vô hạn chiều. Nếu bạn nghiên cứu về graphical models, bạn sẽ nhận ra là mình có thể nói chuyện được với dân làm về xác suất thống kê, dân làm về vật lý lý thuyết, dân làm về signal processing, dân làm về lý thuyết thuật toán, dân làm về sinh học phân tử. Nghiên cứu về GMs là một sự giao thoa thú vị của khá nhiều ngành khác nhau, cho cả những người có thiên hướng về lý thuyết và những người thích những ứng dụng cụ thể.
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.
Một đồng nghiệp của tôi, Matt Beal , cũng có ứng dụng graphical models vào các vấn đề sinh học, và có bài báo với sư phụ bác Long.
Người viết: Ngô Quang Hưng
Anh Long co the giai thich them ve moi tuong quan giua
Conditional Random Field, Log-Linear Model, va Graphical Models duoc ko?
Vai nam gan day Graphical Models dang duoc ua chuong nhac den nhieu. Su phu bac Long lai la to su mon GM nay. Tam thoi vi su phu bac nhu kieu Vuong Trung Duong cua Toan Chan Giao, con anh Long sau nay thanh tai xuong nui roi chac thanh Khuu Xu Co day nhi.
Người viết: Bach Hung Nguyen
CRF là một ví dụ của graphical models (với undirected graph). Giống HMM ở chỗ là đều dùng chained graph, nhưng khác ở chỗ hidden variables khác nhau, và HMM dùng directed graph. Do đó có tradeoff về statistical inference vs. parameter estimation. Nguyên xem thể tham khảo của Andrew McCallum (UMass) và John Lafferty (CMU) ứng dụng cho text processing. Một số ứng dụng gần đây, xem Max Welling (UCI), và Eric Xing (CMU).
Log-linear model, hoặc tổng quát hơn một chút, generalized linear models, là những mô hình thống kê cổ điển, có thể dùng làm building blocks cho graphical models. (Các conditional probability distribution cho các clique trong graphical models). Mấy mô hình này mô tả quan hệ tuyến tính và phát triển lên quan hệ phi tuyến tính ở dạng đơn giản. Nhiều sách thống kê kinh điển có nói về mấy mô hình này. Một tham khảo kinh điển về GLIM:
McCullagh, P. and J.A. Nelder. 1989. Generalized Linear Models. Chapman and Hall:
Người viết: XLN
Tôi cũng đang tìm hiểu để ứng dụng GM. Tôi muốn hỏi về MCMC mà cụ thể là Metropolis – Hastings algorithm.
Như tôi hiểu thì thuật toán này xây dựng một markov process. Process này là stationary tức là sau một số bước đủ lớn thì sẽ hội tụ tới một một hàm phân bố xác suất nào đó. Mục tiêu là xây dựng markov process sao cho hàm hội tụ này chính là hàm phân bố mà ta cần sampled.
Đối với stationary markov process mà có hữu hạn trang thái thì hoàn toàn được mô tả bởi một ma trận vuông P có kích thước bằng số trạng thái có thể. Khi do hàm phân bố xác suất tại trạng thái stationary là một vector hữu hạn chiều chính là eingenvector tương ứng với eingenvalue 1 của P.
Vấn đề này sinh là nếu markov process có vô hạn (nhưng đếm được ) trạng thái. Ma trận P như vậy không tồn tại. Tôi không biết là việc xác định hàm phân bố xác suất tại trạng thái stationary làm thế nào và ngược lại việc xác định markov process (tức là các probability transitions) như thế nào nếu biết trước stationary distribution.
Nếu domain của MC không phải là finite discrete nữa (ví dụ, continuous domain chẳng hạn) thì transition matrix P của bạn phải trở thành một transition kernel (function). Nê’u dùng Gibbs sampling mà các conditional distributions có liên hệ conjugate thì vẫn tính được các acceptance probability một cách dê~ dàng. Nê’u khong co quan he conjugate thì phải dùng Metropolis-Hasting; nói chung vẫn tính được các probability ratio cần thiết.
Bước đầu bạn có thể tham khảo thêm bài báo giới thiệu này:
http://www.cs.berkeley.edu/~jordan/papers/mlintro.ps
Thanks anh Long
Anh Long cho hỏi về sự khác nhau giữa CRF và Markov networrks thông thường về mặt representation, inference và learning. CRF có lợi thề hơn chút nào không và phải trả giá về mặt nào. Tôi tìm hiều nhưng thỉ mới thấy khác nhau về mặt hình thức còn phần tiếp theo thì vẫn không thấy sự khác nhau. Cảm ơn anh.
CRF cũng chỉ nên coi là trường hợp đặc biệt của Markov random fields, nên so sánh chung chung thì cũng không có ý nghĩa. Với sequential data (thứ mà CRF được tailor-made cho thì tôi cũng có nhận định như bạn (có vẻ có sự trade-off giữa parameter estimation và inference phases). Để trả lời cụ thể thì phải hỏi ai đã sử dụng nó nhiều (bạn Nguyên ở CMU?).
Tôi muốn hỏi về EM-Algorithm. Như tôi hiểu thì EM-Algorithms cũng là để estimate parameters như maximum likelihood (ML) và thường dùng cho mixture models.
Đối với các Models đơn giản (gaussian, binomial etc.) thì các estimated parameters hoặc là tính được (analytical solution) hoạc trong trường hợp phức tạp hơn thì có thể dùng numerical optimization. Lời giải luôn tồn tại vì hàm likelihood là convex function.
Tôi muốn hỏi là đối với mixture models thì có thể dùng phương pháp ML truyền thống được không? Hàm likelihood khi đó có convex không? Nếu vẫn dùng ML bình thường được thì tại sao EM lại tốt hơn?
Cũng câu hỏi như thế cho parameter learning của HMM?
Cảm ơn nhiều.