Mô hình hỗn hợp quy trình Dirichlet

• 23 Tháng Sáu, 2014
• Vasilis Vryniotis
• . 2 Bình luận

Bài đăng trên blog này là phần thứ tư của loạt bài về Phân cụm với các mô hình hỗn hợp quy trình Dirichlet. Trong các bài viết trước, chúng tôi đã thảo luận về Mô hình hỗn hợp Dirichlet hữu hạn và chúng tôi đã lấy giới hạn của mô hình của chúng cho k cụm vô hạn, điều này đã dẫn chúng tôi đến phần giới thiệu của Quy trình Dirichlet. Như chúng ta đã thấy, mục tiêu của chúng ta là xây dựng một mô hình hỗn hợp mà không yêu cầu chúng ta chỉ định số lượng k cụm / thành phần ngay từ đầu. Sau trình bày các đại diện khác nhau của các Quy trình Dirichlet, đã đến lúc thực sự sử dụng DP để xây dựng Mô hình hỗn hợp vô hạn cho phép chúng ta thực hiện phân cụm. Mục tiêu của bài viết này là xác định các Mô hình Hỗn hợp Quy trình Dirichlet và thảo luận về việc sử dụng Quy trình Nhà hàng Trung Quốc và Lấy mẫu Gibbs. Nếu bạn chưa đọc các bài viết trước thì rất nên làm vì chủ đề này hơi lý thuyết và cần hiểu rõ về việc xây dựng mô hình.

Cập nhật: Khung học máy của Datumbox hiện là nguồn mở và miễn phí tải về. Kiểm tra gói com.datumbox.framework.machinelearning.clustering để xem việc triển khai Mô hình hỗn hợp quy trình Dirichlet trong Java.

1. Định nghĩa về Mô hình hỗn hợp quy trình Dirichlet

Sử dụng các quy trình Dirichlet cho phép chúng ta có một mô hình hỗn hợp với các thành phần vô hạn, có thể được coi là lấy giới hạn của mô hình hữu hạn cho k đến vô cùng. Giả sử rằng chúng ta có mô hình sau:

Phương trình 1: Mô hình hỗn hợp quy trình Dirichlet

Trong đó G được định nghĩa là và được sử dụng như một ký hiệu ngắn cho đó là một hàm delta mất 1 nếu và 0 ở những nơi khác. Θ_i là các tham số cụm được lấy mẫu từ G. Phân phối tổng hợp F được định cấu hình bởi các tham số cụm θ_i và được sử dụng để tạo x_i quan sát. Cuối cùng, chúng ta có thể xác định phân phối Mật độ đó là phân phối hỗn hợp của chúng tôi (hỗn hợp vô hạn có thể đếm được) với tỷ lệ trộn và trộn các thành phần .

Hình 1: Mô hình đồ thị của Mô hình hỗn hợp quy trình Dirichlet

Ở trên, chúng ta có thể thấy Mô hình đồ họa tương đương của DPMM. G₀ là phân phối cơ sở của DP và nó thường được chọn là liên hợp trước phân phối tổng hợp F của chúng ta để làm cho việc tính toán dễ dàng hơn và sử dụng các tính chất toán học hấp dẫn. Α là siêu tham số vô hướng của Quy trình Dirichlet và ảnh hưởng đến số lượng cụm mà chúng ta sẽ nhận được. Giá trị của α càng lớn thì càng nhiều cụm; α càng nhỏ thì càng ít cụm. Chúng ta cần lưu ý rằng giá trị của α thể hiện sức mạnh của niềm tin trong G₀. Giá trị lớn chỉ ra rằng hầu hết các mẫu sẽ khác biệt và có các giá trị tập trung vào G₀. G là phân phối ngẫu nhiên trên không gian tham số được lấy mẫu từ DP để gán xác suất cho các tham số. Θ_i là một vectơ tham số được vẽ từ phân phối G và chứa các tham số của cụm, phân phối F được tham số hóa bởi θ_i và x_i là điểm dữ liệu được tạo bởi Phân phối tạo F.

Điều quan trọng cần lưu ý là θ_i là các phần tử của không gian tham số Θ và chúng "cấu hình" các cụm của chúng ta. Chúng cũng có thể được coi là các biến tiềm ẩn trên x_i cho chúng tôi biết từ thành phần / cụm x_i đến từ đâu và các thông số của thành phần này là gì. Do đó với mọi x_i mà chúng tôi quan sát, chúng tôi rút ra một θ_i từ phân phối G. Với mỗi lần rút, sự phân bổ thay đổi tùy thuộc vào các lựa chọn trước đó. Như chúng ta đã thấy trong lược đồ bình Blackwell-MacQueen, phân phối G có thể được tích hợp và các lựa chọn trong tương lai của chúng ta về θ_i chỉ phụ thuộc vào G₀: . Việc ước lượng các tham số θi từ công thức trước không phải lúc nào cũng khả thi vì nhiều cách triển khai (chẳng hạn như Quy trình nhà hàng Trung Quốc) liên quan đến việc liệt kê thông qua Tăng k thành phần theo cấp số nhân. Do đó, các phương pháp tính toán gần đúng được sử dụng như Lấy mẫu Gibbs. Cuối cùng, chúng ta cần lưu ý rằng mặc dù k cụm là vô hạn, số lượng cụm hoạt động là . Do đó θ_i sẽ lặp lại và thể hiện hiệu ứng phân cụm.

2. Sử dụng Quy trình Nhà hàng Trung Quốc để xác định Mô hình Hỗn hợp Vô hạn

Mô hình được xác định trong phân đoạn trước là chắc chắn về mặt toán học, tuy nhiên nó có một nhược điểm lớn: đối với mọi x mới_i mà chúng tôi quan sát, chúng tôi phải lấy mẫu θ mới_i có tính đến các giá trị trước đó của θ. Vấn đề là trong nhiều trường hợp, việc lấy mẫu các tham số này có thể là một nhiệm vụ khó khăn và tốn kém về mặt tính toán.

Một cách tiếp cận thay thế là sử dụng Quy trình nhà hàng Trung Quốc để mô hình hóa các biến tiềm ẩn z_i của bài tập cụm. Bằng cách này thay vì sử dụng θ_i để biểu thị cả tham số cụm và chỉ định cụm, chúng tôi sử dụng biến tiềm ẩn z_i để chỉ định id cụm và sau đó sử dụng giá trị này để gán các tham số cụm. Do đó, chúng tôi không còn cần lấy mẫu a θ mỗi khi chúng tôi nhận được một quan sát mới, mà thay vào đó chúng tôi nhận được phép gán cụm bằng cách lấy mẫu z_i từ CRP. Với lược đồ này, một θ mới chỉ được lấy mẫu khi chúng ta cần tạo một cụm mới. Dưới đây chúng tôi trình bày mô hình của cách tiếp cận này:

Phương trình 2: Mô hình hỗn hợp với CRP

Trên đây là một mô hình tổng quát mô tả cách dữ liệu x_i và các cụm được tạo ra. Để thực hiện phân tích cụm, chúng ta phải sử dụng các quan sát x_i và ước tính các nhiệm vụ cụm z_i.

3. Suy luận mô hình hỗn hợp và lấy mẫu Gibbs

Thật không may vì Quy trình Dirichlet là phi tham số, chúng tôi không thể sử dụng thuật toán EM để ước tính các biến tiềm ẩn lưu trữ các nhiệm vụ cụm. Để ước tính các nhiệm vụ, chúng tôi sẽ sử dụng Thu gọn Gibbs Sa sampling.

Lấy mẫu Gibbs thu gọn là một thuật toán Markov Chain Monte Carlo (MCMC) đơn giản. Nó nhanh chóng và cho phép chúng tôi tích hợp một số biến trong khi lấy mẫu một biến khác. Tuy nhiên, thuật toán này yêu cầu chúng ta chọn một G₀ là một liên hợp trước phân phối gen F để có thể giải các phương trình một cách phân tích và có thể lấy mẫu trực tiếp từ .

Các bước của Lấy mẫu Gibbs Thu gọn mà chúng tôi sẽ sử dụng để ước tính các nhiệm vụ cụm như sau:

• Khởi tạo z_i nhiệm vụ cụm một cách ngẫu nhiên
• Lặp lại cho đến khi hội tụ
• Chọn ngẫu nhiên rìu_i
  
• Giữ z khác_j cố định cho mọi j ≠ i:
• Gán một giá trị mới trên z_i bằng cách tính toán "xác suất CRP" phụ thuộc vào z_j và x_j của tất cả j ≠ i:

Trong phần tiếp theo, chúng tôi sẽ tập trung vào cách thực hiện phân tích cụm bằng cách sử dụng các mô hình Dirichlet Process Mixture. Chúng tôi sẽ xác định hai Mô hình Hỗn hợp Quy trình Dirichlet khác nhau sử dụng Quy trình Nhà hàng Trung Quốc và Lấy mẫu Gibbs Thu gọn để thực hiện phân nhóm trên các tập dữ liệu và tài liệu liên tục.