O Modelo de Mistura de Processo Dirichlet

• 23 de Junho de 2014
• Vasilis Vryniotis
• . 2 Comentários

Esta postagem do blog é a quarta parte da série sobre Agrupando com Modelos de Mistura de Processo de Dirichlet. Em artigos anteriores, discutimos os Modelos de Misturas Finitas de Dirichlet e tomamos o limite de seu modelo para clusters de k infinitos, o que nos levou à introdução dos Processos de Dirichlet. Como vimos, nosso objetivo é construir um modelo de mistura que não exija que especifiquemos o número de k clusters / componentes desde o início. Após apresentando diferentes representações dos processos de Dirichlet, agora é hora de realmente usar DPs para construir um modelo de mistura infinito que nos permite realizar agrupamento. O objetivo deste artigo é definir os Modelos de Mistura de Processo de Dirichlet e discutir o uso do Processo de Restaurante Chinês e Amostragem de Gibbs. Se você ainda não leu os posts anteriores, é altamente recomendável que o faça, pois o tema é um pouco teórico e requer um bom entendimento sobre a construção do modelo.

Atualização: O Datumbox Machine Learning Framework agora é de código aberto e gratuito para download. Confira o pacote com.datumbox.framework.machinelearning.clustering para ver a implementação de Modelos de Mistura de Processo Dirichlet em Java.

1. Definição do Modelo de Mistura de Processo de Dirichlet

O uso de processos de Dirichlet nos permite ter um modelo de mistura com componentes infinitos que pode ser pensado como levando o limite do modelo finito de k ao infinito. Vamos supor que temos o seguinte modelo:

Equação 1: Modelo de Mistura de Processo de Dirichlet

Onde G é definido como e usado como uma notação curta para que é uma função delta que leva 1 se e 0 em outro lugar. O θ_i são os parâmetros do cluster que são amostrados de G. A distribuição generativa F é configurada pelos parâmetros do cluster θ_i e é usado para gerar x_i observações. Finalmente, podemos definir uma distribuição de densidade que é a nossa distribuição de mistura (mistura infinita contável) com proporções de mistura e misturar componentes .

Figura 1: Modelo Gráfico do Modelo de Mistura de Processo de Dirichlet

Acima podemos ver o Modelo Gráfico equivalente do DPMM. O G₀ é a distribuição de base de DP e geralmente é selecionada para ser conjugada antes de nossa distribuição generativa F, a fim de tornar os cálculos mais fáceis e fazer uso das propriedades matemáticas atraentes. O α é o hiperparâmetro escalar do Processo de Dirichlet e afeta o número de clusters que obteremos. Quanto maior for o valor de α, maior será o número de clusters; quanto menor o α, menos aglomerados. Devemos notar que o valor de α expressa a força de acreditar em G₀. Um grande valor indica que a maioria das amostras serão distintas e terão valores concentrados em G₀. O G é uma distribuição aleatória sobre Θ espaço de parâmetro amostrado do DP que atribui probabilidades aos parâmetros. O θ_i é um vetor de parâmetros que é extraído da distribuição G e contém os parâmetros do cluster, a distribuição F é parametrizada por θ_i e x_i é o ponto de dados gerado pela Distribuição Gerativa F.

É importante notar que o θ_i são elementos do espaço de parâmetros Θ e eles “configuram” nossos clusters. Eles também podem ser vistos como variáveis ​​latentes em x_i que nos dizem de qual componente / cluster o x_i vem e quais são os parâmetros deste componente. Assim, para cada x_i que observamos, desenhamos um θ_i da distribuição G. A cada sorteio, a distribuição muda de acordo com as seleções anteriores. Como vimos no esquema de urna Blackwell-MacQueen, a distribuição G pode ser integrada e nossas seleções futuras de θ_i dependem apenas de G₀: . Estimar os parâmetros θi da fórmula anterior nem sempre é viável porque muitas implementações (como o Processo de Restaurante Chinês) envolvem a enumeração por meio do aumentando exponencialmente os componentes k. Assim, métodos computacionais aproximados são usados, como a Amostragem de Gibbs. Finalmente, devemos notar que, embora os k clusters sejam infinitos, o número de clusters ativos é . Assim, o θ_i irá repetir e exibir um efeito de agrupamento.

2. Usando o processo do restaurante chinês para definir um modelo de mistura infinita

O modelo definido no segmento anterior é matematicamente sólido, mas tem uma grande desvantagem: para cada novo x_i que observamos, devemos amostrar um novo θ_i levando em consideração os valores anteriores de θ. O problema é que, em muitos casos, a amostragem desses parâmetros pode ser uma tarefa difícil e cara do ponto de vista computacional.

Uma abordagem alternativa é usar o Processo do Restaurante Chinês para modelar as variáveis ​​latentes z_i de atribuições de cluster. Desta forma, em vez de usar θ_i para denotar os parâmetros do cluster e as atribuições do cluster, usamos a variável latente z_i para indicar a id do cluster e, em seguida, usar esse valor para atribuir os parâmetros do cluster. Como resultado, não precisamos mais amostrar um θ cada vez que obtivermos uma nova observação, mas em vez disso, obtemos a atribuição de cluster por amostragem z_i do CRP. Com este esquema, um novo θ é amostrado apenas quando precisamos criar um novo cluster. Abaixo, apresentamos o modelo desta abordagem:

Equação 2: Modelo de Mistura com CRP

O acima é um modelo generativo que descreve como os dados x_i e os clusters são gerados. Para realizar a análise de cluster, devemos usar as observações x_i e estimar as atribuições do cluster z_i.

3. Inferência do Modelo de Mistura e Amostragem de Gibbs

Infelizmente, uma vez que os processos de Dirichlet são não paramétricos, nós não posso usar algoritmo EM para estimar as variáveis ​​latentes que armazenam as atribuições do cluster. Para estimar as atribuições, usaremos o Amostragem de Gibbs recolhidos.

O Collapsed Gibbs Sampling é um algoritmo simples de Markov Chain Monte Carlo (MCMC). É rápido e nos permite integrar algumas variáveis ​​durante a amostragem de outra variável. No entanto, este algoritmo exige que selecione um G₀ que é um conjugado antes da distribuição generativa F, a fim de ser capaz de resolver analiticamente as equações e ser capaz de amostrar diretamente a partir de .

As etapas da Amostragem de Gibbs recolhido que usaremos para estimar as atribuições do cluster são as seguintes:

• Inicialize o z_i atribuições de cluster aleatoriamente
• Repita até a convergência
• Selecione machado aleatoriamente_i
  
• Fique com o outro z_j fixo para cada j ≠ i:
• Atribuir um novo valor em z_i calculando a "probabilidade de CRP" que depende de z_j e x_j de todos j ≠ i:

No próximo artigo, vamos nos concentrar em como realizar a análise de cluster usando modelos de mistura de processos de Dirichlet. Vamos definir dois modelos diferentes de mistura de processos de Dirichlet que usam o processo de restaurante chinês e a amostragem de Gibbs recolhida para realizar agrupamento em documentos e conjuntos de dados contínuos.