Hướng dẫn gaussian mixture model from scratch python - mô hình hỗn hợp gaussian từ python đầu

• Ngày 5 tháng 6 năm 2019
• Python & nbsp;
• Thống kê & NBSP;
• Từ đầu & nbsp;
• Học máy & NBSP;

Xem xét bộ dữ liệu thúc đẩy sau đây:

Dữ liệu không thể thực hiện được

Rõ ràng là những dữ liệu này có một số loại cấu trúc; Điều đó có nghĩa là, chúng chắc chắn không được rút ra từ một phân phối đồng phục hoặc đơn giản khác. Cụ thể, có ít nhất một cụm dữ liệu ở phía dưới bên phải rõ ràng tách biệt với phần còn lại. Câu hỏi đặt ra là: Thuật toán học máy có thể tự động khám phá và mô hình hóa các loại cấu trúc này mà không cần sự trợ giúp của con người không?

Mọi mô hình mà chúng tôi nhìn vào cho đến nay đều cho rằng chúng tôi có một định nghĩa rõ ràng về điều chúng tôi đang cố gắng dự đoán và chúng tôi đã biết câu trả lời chính xác cho mọi ví dụ trong tập huấn luyện. Một vấn đề về biểu mẫu Chỉ cần tìm cho tôi một số mối quan hệ hoặc cấu trúc thú vị, bất kỳ mối quan hệ nào, bất kỳ mối quan hệ nào sẽ không phù hợp với khung này bởi vì không có nhãn hiệu thực sự nào được biết đến trước. Chính thức hơn: Mọi vấn đề cho đến nay đều là một vấn đề học tập được giám sát của người Viking, trong đó bộ đào tạo bao gồm các cặp được dán nhãn \ ((x, y) \) và nhiệm vụ là dự đoán \ (y \) từ \ (x \) . Vấn đề khám phá cấu trúc hoặc mối quan hệ thú vị từ các ví dụ không được gắn nhãn \ (x \) được gọi là vấn đề học tập không giám sát của Hồi giáo, và hoàn toàn kêu gọi một bộ kỹ thuật và thuật toán khác.and that we already know the correct answer for every example in the training set. A problem of the form “just find me some kind interesting relationships or structure, any will do” does not fit into this framework because no “true” labels are known in advance. More formally: every problem so far has been a “supervised” learning problem, where the training set consists of labeled pairs \((X, Y)\) and the task was to predict \(Y\) from \(X\). The problem of discovering interesting structure or relationships from unlabeled examples \(X\) is called the “unsupervised” learning problem, and calls for a different set of techniques and algorithms entirely.

Các loại học tập không giám sát

Có hai cách tiếp cận rộng rãi để học tập không giám sát: giảm kích thước và phân tích cụm.

Trong giảm kích thước, chúng tôi tìm kiếm một hàm \ (f: \ mathbb {r}^a \ mapsto \ mathbb {r}^b \) trong đó \ (a \) là kích thước của dữ liệu gốc \ (\ mathbf {x} \ \ ) và \ (b \) thường nhỏ hơn nhiều so với \ (a \). Ví dụ kinh điển về thuật toán giảm kích thước là PCA nhưng có nhiều loại khác, bao gồm các kỹ thuật phi tuyến tính như T-SNE, các mô hình chủ đề như LDA và hầu hết các ví dụ về việc học đại diện như Word2VEC. Ý tưởng cơ bản là bằng cách giảm xuống không gian chiều thấp hơn, chúng tôi bằng cách nào đó nắm bắt được các đặc điểm thiết yếu của từng điểm dữ liệu trong khi loại bỏ nhiễu, đa hình và các tính năng không thiết yếu. Hơn nữa, có thể xây dựng lại điểm dữ liệu gốc trong không gian nguyên bản \ (a \)-chiều từ chỉ số nén \ (b \)-biểu diễn kích thước với tổn thất tối thiểu. Tùy thuộc vào kỹ thuật cụ thể được sử dụng, không gian chiều thấp hơn cũng có thể được thiết kế để có các thuộc tính mong muốn như ma trận hiệp phương sai đẳng hướng/hình cầu hoặc hàm khoảng cách có ý nghĩa trong đó các điểm dữ liệu mà con người sẽ đồng ý là tương tự gần nhau. Chúng tôi sẽ trở lại giảm kích thước trong một số bài viết trong tương lai.\(f : \mathbb{R}^a \mapsto \mathbb{R}^b\) where \(a\) is the dimension of the original data \(\mathbf{X}\) and \(b\) is usually much smaller than \(a\). The classic example of a dimensionality reduction algorithm is PCA but there are many others, including non-linear techniques like t-SNE, topic models like LDA, and most examples of representation learning such as Word2Vec. The basic idea is that by reducing to a lower dimensional space we somehow capture the essential characteristics of each data point while getting rid of noise, multicollinearity, and non-essential features. Furthermore, it should be possible to approximately reconstruct the original data point in the original \(a\)-dimensional space from just its compressed \(b\)-dimensional representation with minimal loss. Depending on the specific technique used, the lower dimensional space may also be designed to have desirable properties like an isotropic/spherical covariance matrix or a meaningful distance function where data points that a human would agree are “similar” are close together. We will return to dimensionality reduction in some future article.

Cách tiếp cận thứ hai để học tập không giám sát được gọi là phân cụm và được đặc trưng bằng cách tìm kiếm một hàm \ (f: \ mathbb {r}^a \ mapsto \ {1,2, ..., k \} \) Chính xác một trong các lớp \ (k \) có thể. Ví dụ kinh điển về thuật toán phân cụm là \ (k \)-có nghĩa là. Giảm dữ liệu phong phú, đa biến thành một số lượng nhỏ các khả năng hữu hạn có vẻ cực đoan, nhưng vì lý do tương tự, nó cũng có thể cực kỳ làm rõ. Trong bài viết này, chúng tôi sẽ triển khai trên mô hình phân cụm cụ thể được gọi là mô hình hỗn hợp Gaussian hoặc chỉ là GMM.\(f : \mathbb{R}^a \mapsto \{1,2, ..., k\}\) which maps each data point to exactly one of \(k\) possible classes. The classic example of a clustering algorithm is \(k\)-means. Reducing rich, multivariate data to a small finite number of possibilities seems extreme, but for that same reason it can be extremely clarifying as well. In this article we will implement on particular clustering model called the Gaussian mixture model, or just GMM for short.

Mô hình hỗn hợp Gaussian

Mô hình hỗn hợp Gaussian chỉ đơn giản là một hỗn hợp của các bản phân phối Gaussian. Trong trường hợp này, người Gaussian có nghĩa là phân phối bình thường đa biến \ (\ mathcal {n} (\ boldsymbol {\ mu}, \ sigma) \) và hỗn hợp của Hồi có nghĩa là một số phân phối Gaussian khác nhau, tất cả đều có các vectơ trung bình khác nhau \ (( \ boldsymbol {\ mu} _j \) và các ma trận hiệp phương sai khác nhau \ (\ sigma_j \), được kết hợp bằng cách lấy tổng trọng số của các hàm mật độ xác suất:\(\mathcal{N}(\boldsymbol{\mu}, \Sigma)\) and “mixture” means that several different gaussian distributions, all with different mean vectors \(\boldsymbol{\mu}_j\) and different covariance matrices \(\Sigma_j\), are combined by taking the weighted sum of the probability density functions:

\ [\ start .

Chủ đề của:

\ [\ sum_ {j = 1}^k \ Phi_j = 1 \ TAG {2} \]

Một phân phối bình thường đa biến duy nhất có một đồi Hill Hill hoặc và Bump nằm ở \ (\ Boldsymbol {\ mu} _i \); Ngược lại, GMM là một phân phối đa phương thức với vết sưng riêng biệt cho mỗi lớp. . .) Điều này làm cho nó phù hợp với mô hình hóa dữ liệu như đã thấy trong ví dụ thúc đẩy của chúng tôi ở trên, nơi dường như có nhiều hơn một vùng trên mật độ cao.\(\boldsymbol{\mu}_i\); in contrast, a GMM is a multimodal distribution with on distinct bump per class. (Sometimes you get fewer than \(k\) distinct local maxima in the p.d.f., if the bumps are sufficiently close together or if the weight of one class is zero or nearly so, but in general you get \(k\) distinct bumps.) This makes it well suited to modeling data like that seen in our motivating example above, where there seems to be more than one region on high density.

Chúng ta có thể xem đây là một quá trình tổng quát hai bước. Để tạo ví dụ \ (i \)-th:\(i\)-th example:

1. Mẫu một lớp ngẫu nhiên chỉ số \ (c_i \) từ phân phối phân loại được tham số hóa bởi \ (\ boldsymbol {\ Phi} = (\ Phi_1, ... \ Phi_k) \).\(C_i\) from the categorical distribution parameterized by \(\boldsymbol{\phi} = (\phi_1, ... \phi_k)\).
2. Mẫu một vectơ ngẫu nhiên \ (\ mathbf {x} _i \) từ phân phối đa biến liên quan đến lớp \ (c_i \)-th.\(\mathbf{X}_i\) from the multivariate distribution associated to the \(C_i\)-th class.

Các mẫu độc lập \ (n \) \ (\ mathbf {x} _i \) là các vectơ hàng của ma trận \ (\ mathbf {x} \).\(n\) independent samples \(\mathbf{X}_i\) are the row vectors of the matrix \(\mathbf{X}\).

Một cách tượng trưng, ​​chúng tôi viết:

để {\ mu} _ {c_i}, \ sigma_ {c_i}) \ tag {4} \\ \ end {align} \]

Để phù hợp với mô hình GMM vào một bộ dữ liệu cụ thể, chúng tôi cố gắng tìm ước tính khả năng tối đa của các tham số \ (\ theta \):\(\Theta\):

A

Bởi vì ma trận \ (n \ lần m \) \ (\ mathbf {x} \) được coi là nhận thức của \ (n \) i.i.d. Các mẫu từ \ (f_ {gmm} (\ mathbf {x}) \), chúng ta có thể viết ra chức năng khả năng của mình như\(n \times m\) example matrix \(\mathbf{X}\) is assumed to be a realization of \(n\) i.i.d. samples from \(f_{GMM}(\mathbf{x})\), we can write down our likelihood function as

\ [\ mathcal {l} (\ theta; \ mathbf {x}) = p (\ mathbf {x}; \ theta) = \ prod_ {i = 1} C_i = j) p (\ mathbf {x} _i | c_i = j) \ tag {6} \]

Chúng ta biết rằng \ (\ mathbf {x} _i \) có phân phối bình thường đa biến với các tham số được xác định bởi lớp, do đó xác suất có điều kiện \ (p (\ mathbf {x} _i | c_i = j) \) khá nhiều trực tiếp từ định nghĩa:\(\mathbf{X}_i\) has a multivariate normal distribution with parameters determined by the class, so the conditional probability \(P(\mathbf{X}_i|C_i=j)\) can be written down pretty much directly from the definition:

\ [P (\ mathbf {x} _i | c_i = j) = \ frac {1} {\ sqrt {(2 \ pi)^k | . {7} \]

Có được một công thức cho \ (p (c_i = j | \ mathbf {x} _i) \) yêu cầu thêm một chút công việc. Chúng tôi biết rằng xác suất vô điều kiện được đưa ra bởi vectơ tham số \ (\ boldsymbol {\ Phi} \):\(P(C_i=j|\mathbf{X}_i)\) requires a little more work. We know that the unconditional probability is given by the parameter vector \(\boldsymbol{\phi}\):

\ [P (c_i = j) = \ Phi_j \ tag {8} \]

Vì vậy, sử dụng định lý Bayes, chúng ta có thể viết điều này theo phương trình (7):

\ [\ start {align} p (c_i = j | \ mathbf {x} _i) & = \ frac {p (c_i = j) Ul l)} \\ \ end {align} \ tag {9} \]

Nếu chúng ta thay thế phương trình (7) thành (9), chúng ta có thể có được một công thức rõ ràng hơn nhưng rất xấu, vì vậy tôi để điều đó cho trí tưởng tượng của người đọc.

Phương trình (6), (7) và (9), khi được thực hiện cùng nhau, tạo thành hàm khả năng hoàn toàn \ (\ mathcal {l} (\ theta; \ mathbf {x}) \). Tuy nhiên, các phương trình này có một vấn đề - chúng phụ thuộc vào biến ngẫu nhiên không xác định \ (c_i \). Biến này cho chúng ta biết lớp nào \ (\ mathbf {x} _i \) đã được rút ra và làm cho lý do dễ dàng hơn nhiều \). Đây được gọi là một biến ngẫu nhiên tiềm ẩn và sự hiện diện của nó trong mô hình của chúng tôi gây ra một loại vấn đề gà và trứng. Nếu chúng ta biết \ (\ boldsymbol {\ mu} _j \) và \ (\ sigma_j \) cho \ (j = (1, 2, ..., k) \) thì chúng ta có thể đoán được những gì \ (c_i \) là bằng cách nhìn vào đó \ (\ boldsymbol {\ mu} _j \) là gần nhất với \ (\ mathbf {x} _i \). Nếu chúng ta biết \ (c_i \), chúng ta có thể ước tính \ (\ boldsymbol {\ mu} _j \) và \ (\ sigma_j \) bằng cách chỉ lấy ý nghĩa và hiệp phương sai trên tất cả \ (x_i \) trong đó \ (c_i = j \). Nhưng làm thế nào chúng ta có thể ước tính hai bộ tham số này lại với nhau, nếu chúng ta không biết khi nào chúng ta bắt đầu?\(\mathcal{L}(\Theta;\mathbf{X})\). However, these equations have a problem - they depend on the unknown random variable \(C_i\). This variable tells us which class each \(\mathbf{X}_i\) was drawn from and makes it much easier to reason about the distribution, but we don’t actually know what \(C_i\) is for any \(i\). This is called a latent random variable and its presence in our model causes a kind of chicken-and-egg problem. If we knew \(\boldsymbol{\mu}_j\) and \(\Sigma_j\) for \(j = (1, 2, ..., k)\) then we could make a guess about what \(C_i\) is by looking at which \(\boldsymbol{\mu}_j\) is closest to \(\mathbf{X}_i\). If we knew \(C_i\), we could estimate \(\boldsymbol{\mu}_j\) and \(\Sigma_j\) by simply taking the mean and covariance over all \(X_i\) where \(C_i = j\). But how can we estimate these two sets of parameters together, if we don’t know either when we start?

Thuật toán EM

Giải pháp cho tình huống khó xử gà và trứng của chúng tôi là một thuật toán lặp lại được gọi là thuật toán tối đa hóa kỳ vọng, hoặc thuật toán EM viết tắt. Thuật toán EM thực sự là một thực phẩm siêu Mô hình hỗn hợp.

Thuật toán EM yêu cầu chúng tôi giới thiệu một tham số giả để mô hình hóa các biến tiềm ẩn chưa biết \ (C_I \). Bởi vì \ (c_i \) có thể đảm nhận các giá trị riêng biệt \ (k \), tham số mới này sẽ là một ma trận \ (n \ lần k \) trong đó mỗi phần tử \ (w_ {ij} \) là ước tính của \ (p (C_i = j | \ mathbf {x} _i; \ theta) \). Mỗi yếu tố của ma trận này biểu thị xác suất rằng điểm dữ liệu \ (i \)-th đến từ cụm \ (j \). Tr trừ nhìn giả này chỉ được sử dụng khi lắp mô hình và sẽ bị loại bỏ sau đó; Theo nghĩa đó, nó không phải là một tham số thực sự của mô hình.\(C_i\). Because \(C_i\) can take on \(k\) discrete values, this new parameter will be a \(n \times k\) matrix where each element \(w_{ij}\) is an estimate of \(P(C_i = j|\mathbf{X}_i;\theta)\). Each element of this matrix represents the probability that the \(i\)-th data point came from cluster \(j\). This pseudo-parameter is only used when fitting the model and will be discarded afterwards; in that sense it is not a true parameter of the model.

Thuật toán EM sau đó tiến hành lặp đi lặp lại, với mỗi lần lặp được chia thành hai bước: bước điện tử và bước M. Tôi sẽ mô tả những điều này trong các nét rộng trước, vì vậy bạn có thể cảm nhận được ý định chung của thuật toán, sau đó chúng tôi sẽ nghiên cứu chi tiết hơn trong các phần sau.

Trong E-bước, chúng tôi sử dụng kiến ​​thức tốt nhất hiện tại của chúng tôi về các trung tâm và hình dạng của từng cụm để cập nhật các ước tính của chúng tôi về điểm dữ liệu nào đến từ lớp nào. Một cách cụ thể, chúng tôi giữ \ (\ boldsymbol {\ mu} _j \) và \ (\ sigma_j \) đã sửa và cập nhật \ (w_ {ij} \) và \ (\ boldsymbol {\ Phi} \).\(\boldsymbol{\mu}_j\) and \(\Sigma_j\) fixed and update \(w_{ij}\) and \(\boldsymbol{\phi}\).

Trong M bước, chúng tôi sử dụng kiến ​​thức tốt nhất hiện tại của chúng tôi về lớp mỗi điểm thuộc về cập nhật và cải thiện ước tính của chúng tôi cho trung tâm và hình dạng của từng cụm. Một cách cụ thể, chúng tôi sử dụng \ (w_ {ij} \) làm trọng số mẫu khi cập nhật \ (\ boldsymbol {\ mu} _j \) và \ (\ sigma_j \) bằng cách lấy trung bình có trọng số trên \ (x \). Ví dụ: nếu \ (w_11 = 0,01 \) và \ (w_11 = 0,99 \), chúng ta biết rằng điểm dữ liệu \ (x_1 \) không có khả năng ở lớp 1, nhưng rất có thể ở lớp 2. Do đó, khi Ước tính trung tâm của lớp đầu tiên \ (\ boldsymbol {\ mu} _1 \), chúng tôi cung cấp cho trọng lượng gần như không đáng kể, nhưng khi ước tính trung tâm của lớp thứ hai \ (\ boldsymbol {\ mu} _2 Cho \ (x_1 \) Trọng lượng gần như đầy đủ. Điều này kéo theo trung tâm của mỗi cụm về phía các điểm dữ liệu được coi là một phần của cụm đó.\(w_{ij}\) as sample weights when updating \(\boldsymbol{\mu}_j\) and \(\Sigma_j\) by taking weighted averages over \(X\). For example, if \(w_11 = 0.01\) and \(w_11 = 0.99\) we know that the data point \(X_1\) is unlikely to be in class 1, but very likely to be in class 2. Therefore, when estimating the center of the first class \(\boldsymbol{\mu}_1\) we give \(X_1\) almost negligible weight, but when estimating the center of the second class \(\boldsymbol{\mu}_2\) we give \(X_1\) almost full weight. This “pulls” the center of each cluster towards those data points which are considered likely to be part of that cluster.

Trực quan, quá trình lặp lại trông giống như thế này:

Với mỗi lần lặp, thuật toán cải thiện ước tính của nó về vị trí của các cụm, từ đó cho phép nó đoán rõ hơn về điểm nào từ các cụm, từ đó cho phép nó tinh chỉnh hơn nữa ước tính của nó về trung tâm và hình dạng của từng cụm , và như vậy trên AD Infinitum.

Quá trình này được đảm bảo để hội tụ một khả năng tối đa (cục bộ) vì nguyên tắc Ratchet: ở mỗi bước, khả năng chỉ có thể tăng và không bao giờ giảm. Điều này có thể được xem như là một loại tọa độ đi lên. Các cực đại này không phải là duy nhất và GMM sẽ có xu hướng hội tụ đến các giải pháp cuối cùng khác nhau tùy thuộc vào các điều kiện ban đầu.

Một tài nguyên trên GMM và thuật toán EM tôi đã sử dụng là bài giảng Stanford này của Andrew Ng. Tôi đã liên kết với một phần của bài giảng nơi anh ấy hiển thị bước cập nhật này bởi vì điều đó phù hợp nhất với việc thực hiện thuật toán nhưng toàn bộ bài giảng là đáng xem nếu bạn muốn hiểu các khái niệm. Một tài nguyên tốt khác về các nguyên tắc cơ bản của thuật toán EM là sàn trượt này; Nó cung cấp một ví dụ đơn giản có thể được làm bằng tay mà tôi thấy là một cách tuyệt vời để xây dựng trực giác trước khi giải quyết vấn đề phức tạp hơn nhiều khi áp dụng thuật toán EM cho GMM.

Bây giờ chúng tôi sẽ xử lý các bước E-Bước và M cho trường hợp cụ thể của GMM một cách chi tiết.

E-step

Centroid \ (\ boldsymbol {\ mu} _j \) và ma trận hiệp phương sai \ (\ sigma_j \) cho lớp \ (j \) là cố định Điều đó \ (x_i \) đến từ mỗi lớp và bình thường hóa:\(\boldsymbol{\mu}_j\) and covariance matrix \(\Sigma_j\) for class \(j\) is fixed, we can update \(w_{ij}\) by simply calculating the probability that \(X_i\) came from each class and normalizing:

\ [w_ {ij} = \ frac {p (x_i | k = j)} {p (k_i)} = \ frac {p (x_i | k = j) X_i | k = l)} \ tag {10} \]

Tính chất có điều kiện \ (p (\ mathbf {x} _i | k = j) \) chỉ đơn giản là phân phối bình thường đa biến \ (\ mathbf {x} _i ~ \ mathcal {n} (\ mu_i, \ sigma_i) Chúng ta có thể sử dụng phương trình (4) ở trên để tính mật độ xác suất cho từng lớp, sau đó chia cho tổng số để bình thường hóa từng hàng của \ (\ mathbf {x} \) thành 1. Điều này cung cấp cho chúng ta một công thức cụ thể cho bản cập nhật đến \ (w_ij \):\(P(\mathbf{X}_i|K=j)\) is simply the multivariate normal distribution \(\mathbf{X}_i ~ \mathcal{N}(\mu_i, \Sigma_i)\) so we can use equation (4) above to calculate the probability density for each class, and then divide through by the total to normalize each row of \(\mathbf{X}\) to 1. This gives us a concrete formula for the update to \(w_ij\):

\ [w_ {ij} = \ frac {f _ {\ mathcal {n} (\ mu_i, \ sigma_i)} (\ mathbf {x} _i)} } (\ mu_l, \ sigma_l)} (\ mathbf {x} _i)} \ tag {11} \]

Xác suất của mỗi lớp \ (\ Phi \) sau đó có thể được ước tính bằng cách lấy trung bình trên tất cả các ví dụ trong tập huấn luyện:\(\phi\) can then be estimated by averaging over all examples in the training set:

\ [\ Phi_j = \ sum_ {i = 1}^n w_ {ij} \ tag {12} \]

M-step

Quên về các ước tính trong quá khứ chúng tôi đã có cho \ (\ boldsymbol {\ mu} _j \) hoặc \ (\ sigma \). Không giống như giảm độ dốc, thuật toán EM không tiến hành bằng cách thực hiện các thay đổi nhỏ đối với các ước tính tham số lặp trước đó - thay vào đó, nó tạo ra một bước nhảy vọt cho ước tính chính xác - nhưng chỉ trong các chiều nhất định. Trong m-bước, chúng tôi sẽ tính toán các ước tính ml cho \ (\ boldsymbol {\ mu} _j \) hoặc \ (\ sigma \) giả sử rằng \ (w_ {ij} \) được giữ không đổi.\(\boldsymbol{\mu}_j\) or \(\Sigma\). Unlike gradient descent, the EM algorithm does not proceed by making small changes to the previous iteration’s parameter estimates - instead, it makes a bold leap all the way to the exact estimate - but only in certain dimensions. In the M-step, we will calculate the ML estimates for \(\boldsymbol{\mu}_j\) or \(\Sigma\) assuming that \(w_{ij}\) is held constant.

Làm thế nào chúng ta có thể thực hiện một bước nhảy vọt như vậy? Chà, chúng ta có một ma trận quan sát \ (n \) \ (\ mathbf {x} _i \) với trọng số \ (w_i \) mà chúng ta tin là đến từ phân phối đa biến \ (\ mathcal {n} (\ vec {\ mu}, \ mathbb {\ sigma}) \). Điều đó có nghĩa là chúng ta có thể sử dụng các công thức quen thuộc:\(n\) observations \(\mathbf{X}_i\) with weights \(w_i\) which we believe came from a multivariate distribution \(\mathcal{N}(\vec{\mu}, \mathbb{\Sigma})\). That means we can use the familiar formulas:

\ [\ boldsymbol {\ mu} _j = {1 \ over {n}} \ sum_ {i = 1}

\ [\ Sigma_j = \ frac {1} {n} \ sum_ {i = 1}^n w_ {ij} (\ mathbf {x} _i - \ \ boldsymbol {\ mu} _j)^t \ tag {14} \]

Đây thực tế là ước tính ML cho các tham số này cho phân phối bình thường đa biến. Do đó, chúng tôi không cần phải lo lắng về tỷ lệ học tập hoặc độ dốc như chúng tôi sẽ giảm độ dốc vì những ước tính này đã tối đa! Đây là một trong những điều gọn gàng nhất về thuật toán này.

Thực hiện

Biến toán học trên thành một triển khai làm việc là thẳng về phía trước. Chương trình dưới đây tương ứng gần như một-một (một dòng mã cho một phương trình) với toán học trên. Các phương trình (11), (12) được sử dụng trong phương pháp e_step() và phương trình (13) và (14) được sử dụng trong phương pháp m_step().

Một chi tiết tôi không xử lý ở trên là khởi tạo - trong khi \ (\ boldsymbol {\ Phi} \) và \ (w_ {ij} \) Để chọn một chỉ mục ngẫu nhiên \ (i_j \) thống nhất từ ​​\ (1 \) đến \ (n \) cho mỗi lớp và sau đó khởi tạo \ (\ boldsymbol {\ mu} _j = x_ {i_j} \). Điều này đảm bảo rằng mỗi cụm Centroid nằm trong sự hỗ trợ của phân phối cơ bản và ban đầu chúng được trải ra ngẫu nhiên trên khắp không gian.\(\boldsymbol{\phi}\) and \(w_{ij}\) can use simple uniform initialization, for \(\boldsymbol{\mu}\) it is better to choose a random index \(i_j\) uniformly from \(1\) to \(n\) for each class and then initialize \(\boldsymbol{\mu}_j = X_{i_j}\). This ensures that each cluster centroid is inside the support of the underlying distribution and that they are initially spread out randomly throughout the space.

import numpy as np
from scipy.stats import multivariate_normal

class GMM:
    def __init__(self, k, max_iter=5):
        self.k = k
        self.max_iter = int(max_iter)

    def initialize(self, X):
        self.shape = X.shape
        self.n, self.m = self.shape

        self.phi = np.full(shape=self.k, fill_value=1/self.k)
        self.weights = np.full( shape=self.shape, fill_value=1/self.k)
        
        random_row = np.random.randint(low=0, high=self.n, size=self.k)
        self.mu = [  X[row_index,:] for row_index in random_row ]
        self.sigma = [ np.cov(X.T) for _ in range(self.k) ]

    def e_step(self, X):
        # E-Step: update weights and phi holding mu and sigma constant
        self.weights = self.predict_proba(X)
        self.phi = self.weights.mean(axis=0)
    
    def m_step(self, X):
        # M-Step: update mu and sigma holding phi and weights constant
        for i in range(self.k):
            weight = self.weights[:, [i]]
            total_weight = weight.sum()
            self.mu[i] = (X * weight).sum(axis=0) / total_weight
            self.sigma[i] = np.cov(X.T, 
                aweights=(weight/total_weight).flatten(), 
                bias=True)

    def fit(self, X):
        self.initialize(X)
        
        for iteration in range(self.max_iter):
            self.e_step(X)
            self.m_step(X)
            
    def predict_proba(self, X):
        likelihood = np.zeros( (self.n, self.k) )
        for i in range(self.k):
            distribution = multivariate_normal(
                mean=self.mu[i], 
                cov=self.sigma[i])
            likelihood[:,i] = distribution.pdf(X)
        
        numerator = likelihood * self.phi
        denominator = numerator.sum(axis=1)[:, np.newaxis]
        weights = numerator / denominator
        return weights
    
    def predict(self, X):
        weights = self.predict_proba(X)
        return np.argmax(weights, axis=1)

Đánh giá mô hình

Chúng tôi sẽ sử dụng bộ dữ liệu IRIS nổi tiếng làm trường hợp thử nghiệm. Đây là cùng một bộ dữ liệu được sử dụng như một ví dụ thúc đẩy ở đầu bài viết, mặc dù tôi không đặt tên cho nó vào thời điểm đó. Bộ dữ liệu IRIS có nhãn, nhưng chúng tôi đã giành chiến thắng để tiếp xúc với mô hình GMM. Tuy nhiên, chúng tôi sẽ sử dụng các nhãn này trong phần tiếp theo để thảo luận về câu hỏi, chúng tôi có thể khám phá các nhãn lớp thông qua việc học không bị giám sát không?

from scipy.stats import mode
from sklearn.metrics import confusion_matrix
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
iris = load_iris()
X = iris.data

Phù hợp với một mô hình:

np.random.seed(42)
gmm = GMM(k=3, max_iter=10)
gmm.fit(X)

Vẽ các cụm. Mỗi màu là một cụm được tìm thấy bởi GMM:

def jitter(x):
    return x + np.random.uniform(low=-0.05, high=0.05, size=x.shape)

def plot_axis_pairs(X, axis_pairs, clusters, classes):
    n_rows = len(axis_pairs) // 2
    n_cols = 2
    plt.figure(figsize=(16, 10))
    for index, (x_axis, y_axis) in enumerate(axis_pairs):
        plt.subplot(n_rows, n_cols, index+1)
        plt.title('GMM Clusters')
        plt.xlabel(iris.feature_names[x_axis])
        plt.ylabel(iris.feature_names[y_axis])
        plt.scatter(
            jitter(X[:, x_axis]), 
            jitter(X[:, y_axis]), 
            #c=clusters, 
            cmap=plt.cm.get_cmap('brg'),
            marker='x')
    plt.tight_layout()
    
plot_axis_pairs(
    X=X,
    axis_pairs=[ 
        (0,1), (2,3), 
        (0,2), (1,3) ],
    clusters=permuted_prediction,
    classes=iris.target)

Cụm GMM

Vâng, mô hình chắc chắn đã tìm thấy một cái gì đó.

Một điều chúng ta có thể nói chắc chắn là mô hình GMM tìm thấy các cụm các điểm liên quan. Nó thực hiện một công việc đặc biệt tốt khi đặt các điểm riêng biệt trực quan trong cụm (màu xanh) của riêng họ, nhưng câu chuyện với hai cụm khác ở phía trên bên phải là ít rõ ràng hơn.

So sánh với các nhãn lớp thực

Các cụm được phát hiện bởi mô hình GMM có ý nghĩa? Họ có đúng không? Đối với một vấn đề học tập không giám sát trong thế giới thực, những câu hỏi này có thể khó trả lời.

Tuy nhiên, điều đó xảy ra là bộ dữ liệu IRIS mà chúng tôi đã sử dụng thực sự được dán nhãn. Thật vậy, chúng tôi đã sử dụng các nhãn này khi đào tạo mô hình GMM. Hơn nữa, các lớp đó được liên kết với các phân phối khác nhau trong 4 biến quan sát theo cách khớp chặt chẽ với các giả định của GMM. Vì vậy, ngay cả khi chúng ta có thể hỏi về ý nghĩa của người Viking và tính đúng đắn, thì ít nhất chúng ta cũng có thể hỏi một câu hỏi liên quan chặt chẽ: Thuật toán học tập không giám sát này (lại) khám phá cấu trúc đã biết của tập dữ liệu (IRIS) này?

Đầu tiên, một chút lưu giữ sách. Các chỉ mục cụm được tìm thấy bởi mô hình theo thứ tự ngẫu nhiên. Để thuận tiện khi so sánh chúng với các nhãn lớp thực sự, chúng tôi sẽ hoán vị chúng giống nhau nhất có thể với các nhãn lớp thực sự. Tất cả những điều này đang làm là hoán đổi, giả sử, 0 cho 2 để 0 có nghĩa là cùng một điều cho cả các cụm và nhãn lớp gốc. Nó không quan trọng, nhưng nó làm cho việc so sánh dễ dàng hơn một chút.

permutation = np.array([
    mode(iris.target[gmm.predict(X) == i]).mode.item() 
    for i in range(gmm.k)])
permuted_prediction = permutation[gmm.predict(X)]
print(np.mean(iris.target == permuted_prediction))
confusion_matrix(iris.target, permuted_prediction)

0.96
array([[50,  0,  0],
       [ 0, 44,  6],
       [ 0,  0, 50]])

Đối với hạt giống ngẫu nhiên 42 (được sử dụng ở trên khi mô hình GMM được đào tạo), điều này dẫn đến thỏa thuận 96% rất hứa hẹn! Tuy nhiên, nếu chúng ta 1.000 thử nghiệm ngẫu nhiên, thay đổi hạt giống mỗi lần, chúng ta có thể thấy rằng thỏa thuận giữa các cụm từ nhãn hiệu thực sự thay đổi ngẫu nhiên từ 0,52 đến 0,99 với giá trị trung bình là 0,74.

Biểu đồ chính xác

Đây là một chút thất vọng. Chúng tôi bắt đầu từ một bộ dữ liệu thực sự là sự tổng hợp của ba lớp khác nhau và trong khi thuật toán học tập không giám sát của chúng tôi đã khám phá ra ba cụm, thỏa thuận giữa thực tế và mô hình của chúng tôi chỉ khoảng 3/4. Điều đó có nghĩa là chúng ta có thể xây dựng lại cấu trúc thực sự của bộ dữ liệu này bằng cách sử dụng kỹ thuật này. Ngược lại, một thuật toán học tập có giám sát có thể dễ dàng tìm thấy một ranh giới lớp với độ chính xác là 99%. Điều đó cho thấy rằng nếu chúng ta chạy một thuật toán học không được giám sát trên một tập dữ liệu trong thế giới thực và nó sẽ tìm thấy một số cụm cho chúng ta, chúng ta nên nghi ngờ rằng chúng đại diện cho các lớp thực sự trên thế giới thực. Trên thực tế, các thuật toán học tập không giám sát phải tuân theo một số lượng lớn các cảnh báo và hạn chế mà tôi sẽ lạc đề ngắn gọn để liệt kê.

Giới hạn

Tất cả các phương pháp học tập không được giám sát ngày nay chia sẻ những hạn chế nhất định.

Đầu tiên, họ có xu hướng dựa vào nhà nghiên cứu chọn các tham số phức tạp tùy ý nhất định như số lượng cụm \ (k \). Tệ hơn nữa, trong khi có các kỹ thuật để chọn các thông số phức tạp này, chúng là heuristic và thường không thỏa mãn trong thực tế. Có thể rất khó để biết liệu một phương pháp học tập không giám sát có phải là sự quá mức hay không, bởi vì, không có gì khác, thậm chí còn có một định nghĩa chính xác cho các vấn đề học tập không giám sát.\(k\). Worse still, while there are techniques for picking these complexity parameters, they are heuristic and often unsatisfying in practice. It can be very hard to tell if an unsupervised learning method is “overfitting”, because “overfit” doesn’t even have a precise definition for unsupervised learning problems.

Thứ hai, không có số liệu cứng như độ chính xác hoặc AUC cho phép bạn so sánh các mô hình giữa các gia đình khác nhau. Mặc dù mỗi thuật toán học tập không được giám sát sẽ có các số liệu nội bộ riêng mà họ cố gắng tối ưu hóa như phương sai được giải thích hoặc bối rối, nhưng chúng thường có thể so sánh có ý nghĩa so sánh hai mô hình sử dụng hai thuật toán khác nhau hoặc với các tham số phức tạp khác nhau. Điều này làm cho việc lựa chọn mô hình trở thành một nhiệm vụ chủ quan cơ bản-để quyết định rằng, giả sử, T-SNE đang thực hiện một công việc tốt hơn \ (k \)-có nghĩa là trên một tập dữ liệu nhất định, người lập mô hình thường giảm để làm mắt đến đầu ra.\(k\)-means on a given data set, the modeler is often reduced to eyeballing the output.

Thứ ba và cuối cùng, các yếu tố và/hoặc cụm được phát hiện bởi các thuật toán học tập không được giám sát thường không thỏa mãn hoặc phản trực giác và không nhất thiết phải xếp hàng với trực giác của con người. Một cách khác để nói điều tương tự là nếu con người trải qua và tạo nhãn \ (\ mathbf {y} \) cho tập huấn luyện \ (\ mathbf {x} \) sau khi thuật toán học không được giám sát đã được áp dụng cho nó, Họ không có khả năng đưa ra các yếu tố hoặc cụm tương tự. Nói chung, con người có xu hướng đưa ra các quy tắc mà có ý nghĩa, nhưng không giải thích được nhiều phương sai nhất có thể, trong khi các thuật toán có xu hướng tìm thấy các tính năng sâu thẳm, giải thích nhiều phương sai nhưng có các định nghĩa phức tạp khó có thể Làm cho ý nghĩa của.\(\mathbf{Y}\) for the training set \(\mathbf{X}\) after the unsupervised learning algorithm has been applied to it, they are not very likely to come up with the same factors or clusters. In general, humans tend to come up with rules that “make sense” but don’t explain as much variance as possible, while algorithms tend to find “deep” features that do explain a lot of variance but have complicated definitions that are hard to make sense of.

Đây có vẻ như là những lời chỉ trích nghiêm trọng; Điều này có nghĩa là chúng ta không nên sử dụng học tập không giám sát? Chà, tôi đã giành chiến thắng nói với bạn rằng bạn không bao giờ nên sử dụng nó, nhưng bạn nên biết những gì bạn đang tham gia. Theo mặc định, nó có xu hướng tạo ra các mô hình chất lượng thấp, khó tin, thực sự không thể được bảo vệ do số lượng quyết định chủ quan cần thiết để làm cho chúng hoạt động.

Mặt khác, việc học không giám sát có thể cực kỳ hữu ích trong quá trình nghiên cứu khám phá; Ngoài ra, dưới dạng học đại diện, đôi khi nó có thể tăng tốc học tập hoặc cải thiện hiệu suất hoặc cho phép các mô hình khái quát hóa từ một bộ đào tạo được dán nhãn cực kỳ hạn chế. Ví dụ, một mô hình phân tích tình cảm được đào tạo trên chỉ vài trăm đánh giá chỉ có thể thấy từ ngữ sterling sterling một lần, nhưng nếu nó sử dụng một mô hình nhúng từ như Word2VEC, nó sẽ hiểu rằng một cách tuyệt vời Hoặc là tuyệt vời, và do đó, sẽ có thể phân loại chính xác một ví dụ trong tương lai với từ ngữ sành điệu - điều này không xuất hiện ngay cả một lần trong tập huấn luyện - có khả năng có tình cảm tích cực. Mặc dù những câu chuyện thành công như thế này là có thể, nhưng nói chung, việc học không được giám sát đòi hỏi nhiều chuyên môn hơn, điều chỉnh thủ công hơn và nhiều đầu vào từ các chuyên gia tên miền để tạo ra giá trị, khi so sánh với các dự án học tập có giám sát.

Thật không may, chúng tôi không phải lúc nào cũng có các nhãn cần thiết cho việc học có giám sát và các bộ dữ liệu có sẵn có thể quá lớn, quá cao hoặc quá thưa thớt để có thể chấp nhận các kỹ thuật truyền thống; Đó là trong những tình huống mà lợi ích của việc học tập không giám sát có thể vượt xa những tiêu cực.

Sự kết luận

Trong bài viết này, chúng ta đã thấy việc học tập không giám sát khác với việc học có giám sát và những thách thức đi kèm với điều đó như thế nào. Chúng tôi đã thảo luận về một phương pháp để đặt ra một vấn đề học tập không giám sát như là một tối ưu hóa khả năng tối đa, và mô tả và thực hiện thuật toán EM thường được sử dụng để giải quyết những vấn đề khó khăn này. Chúng tôi đã thực hiện bê tông thuật toán EM bằng cách triển khai một mô hình biến tiềm ẩn cụ thể, mô hình hỗn hợp Gaussian, một thuật toán phân cụm không giám sát mạnh mẽ. Chúng tôi đã thấy tận mắt rằng các cụm được xác định bởi GMMS don luôn luôn phù hợp với những gì chúng tôi tin rằng cấu trúc thực sự; Điều này dẫn đến một cuộc thảo luận rộng hơn về những hạn chế của các thuật toán học tập không giám sát và khó khăn trong việc nhận được giá trị từ chúng.

Trong bài viết tiếp theo trong loạt bài này, chúng tôi sẽ tiếp tục thảo luận về các thuật toán học không được giám sát bằng cách thực hiện loại thuật toán học tập không giám sát khác bên cạnh việc phân cụm: thuật toán giảm chiều.