Dirichlet Xử lý quy trình nhà hàng Trung Quốc và các đại diện khác

• 20 Tháng Năm, 2014
• Vasilis Vryniotis
• . Miễn bình luận

Bài viết này là phần thứ ba của loạt bài về Clustering với Dirichlet Process Mixture Models. Lần trước, chúng tôi đã xác định Mô hình Hỗn hợp Hữu hạn dựa trên Phân phối Dirichlet và chúng tôi đã đặt ra các câu hỏi về cách chúng tôi có thể làm cho mô hình cụ thể này trở nên vô hạn. Chúng tôi đã thảo luận ngắn gọn về ý tưởng lấy giới hạn của mô hình khi k số cụm có xu hướng đến vô cùng nhưng khi chúng tôi nhấn mạnh sự tồn tại của một đối tượng như vậy là không hề nhỏ (nói cách khác, làm thế nào để chúng tôi thực sự “lấy giới hạn của một mô hình ”?). Xin nhắc lại, lý do tại sao chúng ta muốn lấy k vô hạn là vì theo cách này, chúng ta sẽ có một mô hình phi tham số mà không yêu cầu chúng ta xác định trước tổng số cụm trong dữ liệu.

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.

Mặc dù mục tiêu của chúng tôi là xây dựng một mô hình có khả năng thực hiện phân cụm trên các tập dữ liệu, nhưng trước đó chúng ta phải thảo luận về các Quy trình Dirichlet. Chúng tôi sẽ cung cấp cả các định nghĩa toán học nghiêm ngặt và các giải thích trực quan hơn về DP và chúng tôi sẽ thảo luận về các cách xây dựng quy trình. Các cấu trúc / biểu diễn đó có thể được coi là một cách để tìm các lần xuất hiện của Quy trình Dirichlet trong “cuộc sống thực”.

Mặc dù thực tế là tôi đã cố gắng điều chỉnh báo cáo nghiên cứu của mình theo cách để các bài đăng trên blog này dễ theo dõi hơn, nhưng điều quan trọng vẫn là xác định các công cụ toán học và phân phối cần thiết trước khi chúng ta bắt đầu sử dụng các mô hình. Các mô hình Quy trình Dirichlet là một chủ đề của nghiên cứu tích cực, nhưng chúng đòi hỏi bạn phải hiểu rõ về Quy trình thống kê và Stochastic trước khi sử dụng chúng. Một vấn đề khác là như chúng ta sẽ thấy trong bài viết này, các Quy trình Dirichlet có thể được biểu diễn / xây dựng bằng nhiều cách. Do đó, một số bài báo học thuật sử dụng các ký hiệu / quy ước hoàn toàn khác nhau và xem xét vấn đề từ các quan điểm khác nhau. Trong bài đăng này, tôi cố gắng giải thích chúng càng đơn giản càng tốt và sử dụng cùng một ký hiệu. Hy vọng rằng mọi thứ sẽ trở nên rõ ràng hơn với hai bài viết sắp tới tập trung vào định nghĩa của Mô hình hỗn hợp quy trình Dirichlet và về cách thực sự sử dụng chúng để thực hiện phân tích cụm.

1. Định nghĩa về Quy trình Dirichlet

Quá trình Dirichlet trên một không gian Θ là một quá trình ngẫu nhiên. Nó là một phân phối xác suất trên "phân phối xác suất trên Θ không gian" và rút ra từ nó là một phân phối rời rạc. Chính thức hơn, Phân phối Dirichlet là một phân phối trên các thước đo xác suất. Một thước đo xác suất là một hàm của các tập con của không gian Θ đến [0,1]. G là thước đo xác suất ngẫu nhiên có phân phối DP, được ký hiệu là , nếu cho bất kỳ phân vùng nào (A₁,…MỘT_n) của không gian Θ chúng ta có rằng .

Hình 1: Các biên trên các phân vùng nhỏ được phân phối Dirichlet.

DP có hai tham số: Tham số đầu tiên là phân phối cơ sở G₀ mà phục vụ như một ý nghĩa . Tham số thứ hai là tham số sức mạnh α hoàn toàn dương và phục vụ giống như phương sai nghịch đảo . Nó xác định mức độ lặp lại các giá trị của phân phối đầu ra. Giá trị của a càng cao thì độ lặp lại càng nhỏ; giá trị càng nhỏ thì sự lặp lại các giá trị của phân phối sản lượng càng cao. Cuối cùng không gian Θ là không gian tham số mà chúng ta xác định DP. Hơn nữa không gian Θ cũng là không gian xác định của G₀ cái nào giống cái G.

Một đơn giản hơn và hơn thế nữa cách trực quan để giải thích một Quy trình Dirichlet như sau. Giả sử rằng chúng ta có một không gian Θ có thể được phân hoạch theo bất kỳ cách nào hữu hạn (A₁,…,MỘT_n) và phân phối xác suất G gán xác suất cho chúng. G là một phân phối xác suất cụ thể trên Θ nhưng có nhiều phân phối khác. Quy trình Dirichlet trên Θ mô hình hóa chính xác điều này; nó là một phân phối trên tất cả các phân phối xác suất có thể có trên không gian Θ. Quá trình Dirichlet được tham số hóa với G₀ hàm bazơ và tham số nồng độ α. Chúng ta có thể nói rằng G được phân phối theo DP với các tham số α và G₀ nếu phân phối chung của các xác suất mà G gán cho các phân vùng của Θ tuân theo Phân phối Dirichlet. Ngoài ra, chúng ta có thể nói rằng các xác suất mà G gán cho bất kỳ phân hoạch hữu hạn nào của Θ tuân theo Phân phối Dirichlet.

Hình 2: Mô hình đồ thị của quy trình Dirichlet

Cuối cùng ở trên, chúng ta có thể thấy mô hình đồ họa của một DP. Chúng ta cần lưu ý rằng α là một siêu tham số vô hướng, G₀ là phân phối cơ sở của DP, 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ố và θ_i là một vectơ tham số được vẽ từ phân phối G và nó là một phần tử của Θ không gian.

2. Quá trình sau Dirichlet

Các quá trình Posterior Dirichlet đã được thảo luận bởi Ferguson. Chúng tôi bắt đầu bằng cách vẽ một thước đo xác suất ngẫu nhiên G từ Quy trình Dirichlet, . Vì G là phân phối xác suất trên Θ nên chúng ta cũng có thể lấy mẫu từ phân phối này và vẽ các mẫu độc lập có phân bố giống hệt nhau θ₁,…, Θ_n ~ G. Vì các bản vẽ từ Quy trình Dirichlet là các bản phân phối rời rạc, chúng ta có thể biểu diễn Ở đâu là 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. Một hiệu ứng thú vị của điều này là vì G được xác định theo cách này, nên có một xác suất dương của các mẫu khác nhau có cùng giá trị . Như chúng ta sẽ thấy ở phần sau, điều này tạo ra một hiệu ứng phân cụm có thể được sử dụng để thực hiện Phân tích cụm trên tập dữ liệu.

Bằng cách sử dụng các định nghĩa và quan sát ở trên, chúng tôi muốn ước tính hậu quả của Quy trình Dirichlet với các mẫu θ. Tuy nhiên, kể từ khi chúng ta biết rằng và bằng cách sử dụng Quy tắc Bayes và Sự kết hợp giữa Dirichlet và Đa thức, chúng ta có và .

Phương trình 1: Quá trình Posterior Dirichlet

Thuộc tính này rất quan trọng và nó được sử dụng bởi các đại diện DP khác nhau.

3. Biểu diễn Quy trình Dirichlet

Trong các phân đoạn trước, chúng tôi đã xác định Quy trình Dirichlet và trình bày mô hình lý thuyết của nó. Một câu hỏi quan trọng mà chúng ta phải trả lời là làm thế nào chúng ta biết rằng một vật thể như vậy tồn tại và làm thế nào chúng ta có thể xây dựng và đại diện một Quy trình Dirichlet.

Những dấu hiệu đầu tiên về sự tồn tại được cung cấp bởi Ferguson người đã sử dụng Định lý nhất quán Kolmogorov, đưa ra định nghĩa về Quy trình Dirichlet và mô tả Quy trình Dirichlet bí ẩn. Tiếp tục nghiên cứu của mình, Blackwell và MacQueen đã sử dụng Định lý de Finetti để chứng minh sự tồn tại của một phép đo xác suất ngẫu nhiên như vậy và giới thiệu lược đồ urn Blackwell-MacQueen thỏa mãn các tính chất của Quy trình Dirichlet. Năm 1994 Sethuraman đã cung cấp thêm một cách đơn giản và trực tiếp để xây dựng DP bằng cách giới thiệu cấu trúc Stick-break. Cuối cùng, một đại diện khác đã được cung cấp bởi Aldous người đã giới thiệu Quy trình nhà hàng Trung Quốc như một cách hiệu quả để xây dựng Quy trình Dirichlet.

Các biểu diễn khác nhau của Quy trình Dirichlet là tương đương về mặt toán học nhưng công thức của chúng khác nhau vì chúng xem xét vấn đề từ các quan điểm khác nhau. Dưới đây, chúng tôi trình bày các đại diện phổ biến nhất được tìm thấy trong tài liệu và chúng tôi tập trung vào Quy trình nhà hàng Trung Quốc, cung cấp một cách đơn giản và hiệu quả về mặt tính toán để xây dựng các thuật toán suy luận cho Quy trình Dirichlet.

3.1 Lược đồ Blackwell-MacQueen urn

Lược đồ Blackwell-MacQueen urn có thể được sử dụng để đại diện cho một Quy trình Dirichlet và nó đã được giới thiệu bởi Blackwell và MacQueen. Nó dựa trên sơ đồ Pólya urn có thể được coi là mô hình lấy mẫu ngược lại mà không cần thay thế. Trong sơ đồ bình Pólya, chúng ta giả sử rằng chúng ta có một chiếc bình không trong suốt chứa các quả bóng màu và chúng ta vẽ các quả bóng một cách ngẫu nhiên. Khi chúng ta vẽ một quả bóng, chúng ta quan sát màu sắc của nó, chúng ta đặt nó trở lại bình và thêm một quả bóng cùng màu. Một lược đồ tương tự được sử dụng bởi Blackwell và MacQueen để xây dựng một Quy trình Dirichlet.

Lược đồ này tạo ra một chuỗi θ₁, θ₂,… với xác suất có điều kiện . Trong sơ đồ này, chúng tôi giả định rằng G₀ là sự phân bố theo màu sắc và từng θ_n thể hiện màu sắc của quả bóng được đặt trong bình. Các thuật toán là như sau:

· Chúng tôi bắt đầu với một chiếc bình rỗng.

· Với xác suất tỷ lệ với α chúng tôi vẽ và chúng tôi thêm một quả bóng màu này vào trong bình.

· Với xác suất tỷ lệ với n-1, chúng ta lấy ngẫu nhiên một quả bóng từ cái lọ, chúng ta quan sát màu sắc của nó, chúng ta đặt nó trở lại cái lọ và chúng ta thêm một quả bóng cùng màu vào trong lọ.

Trước đây, chúng tôi đã bắt đầu với Quy trình Dirichlet và bắt nguồn từ lược đồ Blackwell-MacQueen. Bây giờ chúng ta hãy bắt đầu ngược lại từ lược đồ Blackwell-MacQueen và lấy DP. Kể từ khi θ_i được rút ra theo cách iid từ G, phân phối chung của chúng sẽ bất biến đối với bất kỳ hoán vị hữu hạn nào và do đó chúng có thể trao đổi được. Do đó, bằng cách sử dụng định lý de Finetti, chúng ta thấy rằng phải tồn tại một phân phối trên các số đo để làm cho chúng ổn định và phân phối này là Quá trình Dirichlet. Kết quả là chúng tôi chứng minh rằng lược đồ urn Blackwell-MacQueen là một đại diện của DP và nó cung cấp cho chúng tôi một cách cụ thể để xây dựng nó. Như chúng ta sẽ thấy ở phần sau, sơ đồ này về mặt toán học tương đương với Quy trình Nhà hàng Trung Quốc.

3.2 Kết cấu chống gãy dính

Cấu trúc chống gãy dính là một cách thay thế để đại diện cho Quy trình Dirichlet được giới thiệu bởi Sethuraman. Đó là một cách xây dựng để hình thành phân phối và sử dụng tương tự sau đây: Chúng ta giả sử rằng chúng ta có một thanh dài 1, chúng ta bẻ gãy nó ở vị trí β₁ và chúng tôi gán π₁ bằng chiều dài của phần que mà ta bẻ. Chúng tôi lặp lại quá trình tương tự để thu được π₂, Số Pi₃,… vân vân; do cách thức mà lược đồ này được xác định, chúng ta có thể tiếp tục thực hiện nó với số lần vô hạn.

Dựa trên các π trên_k có thể được mô hình hóa như , Onde o trong khi như trong các lược đồ trước, θ được lấy mẫu trực tiếp bởi Phân phối cơ sở . Do đó, phân phối G có thể được viết dưới dạng tổng các hàm delta có trọng số với π_k xác suất bằng . Do đó, cấu trúc Stick-break cung cấp cho chúng ta một cách đơn giản và trực quan để xây dựng Quy trình Dirichlet.

3.3 Quy trình nhà hàng Trung Quốc

Quy trình Nhà hàng Trung Quốc, được giới thiệu bởi Aldous, là một cách hiệu quả khác để biểu diễn Quy trình Dirichlet và nó có thể được liên kết trực tiếp với lược đồ urn Blackwell-MacQueen. Đề án này sử dụng tương tự sau đây: Chúng tôi giả định rằng có một nhà hàng Trung Quốc với vô số bàn. Khi khách hàng bước vào nhà hàng, họ sẽ ngồi ngẫu nhiên vào bất kỳ bàn nào đã có người hoặc họ chọn ngồi vào bàn trống đầu tiên.

CRP xác định phân phối trên không gian phân vùng của các số nguyên dương. Chúng ta bắt đầu bằng cách vẽ θ₁,… Θ_n từ lược đồ urn Blackwell-MacQueen. Như chúng ta đã thảo luận trong các phân đoạn trước, chúng ta mong đợi sẽ thấy hiệu ứng phân cụm và do đó tổng số giá trị θ duy nhất k sẽ nhỏ hơn đáng kể so với n. Do đó, điều này xác định một phân vùng của tập {1,2,…, n} trong k cụm. Do đó, việc vẽ từ lược đồ urn Blackwell-MacQueen tạo ra một phân vùng ngẫu nhiên của tập hợp {1,2,…, n}. Quy trình Nhà hàng Trung Quốc là do điều này gây ra phân phối qua các phân vùng. Thuật toán như sau:

· Chúng tôi bắt đầu với một nhà hàng trống.

· Các 1^st khách hàng luôn ngồi trên 1^st bàn

· N + 1^th khách hàng có 2 lựa chọn:

o Ngồi vào bàn trống đầu tiên với xác suất

o Ngồi vào bất kỳ bàn thứ k nào có xác suất
Ở đâu là số người ngồi trên bàn đó

Trong đó α là giá trị phân tán của DP và n là tổng số khách hàng trong nhà hàng tại một thời điểm nhất định. Biến tiềm ẩn z_i lưu trữ số bàn của tôi^th khách hàng và nhận các giá trị từ 1 đến k_n nơi k_n là tổng số bàn có khách khi có n khách hàng trong nhà hàng. Chúng ta cần lưu ý rằng k_n sẽ luôn nhỏ hơn hoặc bằng n và trung bình là khoảng . Cuối cùng, chúng ta cần lưu ý rằng xác suất sắp xếp bảng là bất biến đối với hoán vị. Do đó, z_i có thể trao đổi, nghĩa là các bàn có cùng quy mô khách hàng có cùng xác suất.

Quy trình Nhà hàng Trung Quốc được kết nối chặt chẽ với chương trình Pólya urn và Quy trình Dirichlet. CRP là một cách để chỉ định một phân phối qua các phân vùng (bảng gán) của n điểm và có thể được sử dụng như một điểm trước trên không gian của biến tiềm ẩn z_i cái nào xác định các nhiệm vụ cụm. CRP tương đương với lược đồ urn của Pólya, chỉ khác là nó không gán các tham số cho từng bảng / cụm. Đi từ CRP đến kế hoạch urn của Pólya chúng tôi vẽ cho tất cả các bảng k = 1,2… và sau đó cho mọi x_i được nhóm thành bảng z_i chỉ định một . Nói cách khác, gán cho x mới_i tham số θ của bảng. Cuối cùng kể từ chúng tôi không thể chỉ định bảng θ đến vô hạn ngay từ đầu, chúng ta có thể chỉ định một θ mới mỗi khi ai đó ngồi vào một bảng mới. Do tất cả những điều trên, CRP có thể giúp chúng tôi xây dựng các thuật toán hiệu quả về mặt tính toán để thực hiện Phân tích cụm trên tập dữ liệu.

Trong bài đăng này, chúng tôi đã thảo luận về Quy trình Dirichlet và một số cách để xây dựng nó. Chúng tôi sẽ sử dụng những ý tưởng trên trong bài viết tiếp theo. Chúng tôi sẽ giới thiệu Mô hình hỗn hợp quy trình Dirichlet và chúng tôi sẽ sử dụng Trình diễn nhà hàng Trung Quốc để xây dựng Quy trình Dirichlet và phân tích cụm sơ bộ. Nếu bạn bỏ lỡ một vài điểm, đừng lo lắng vì mọi thứ sẽ bắt đầu trở nên rõ ràng hơn với hai bài viết tiếp theo.

Tôi hy vọng bạn thấy bài viết này thú vị. Nếu bạn đã làm vậy, hãy dành một chút thời gian để chia sẻ nó trên Facebook và Twitter. 🙂