Processo de Dirichlet

Em teoria das probabilidades, os processos de Dirichlet, que recebem este nome em homenagem ao matemático alemão Johann Peter Gustav Lejeune Dirichlet, são uma família de processos estocásticos cujas observações são distribuições de probabilidade. Em outras palavras, um processo de Dirichlet é uma distribuição de probabilidade cujo intervalo é ele mesmo um conjunto de distribuições de probabilidade. É frequentemente usado em inferência bayesiana para descrever conhecimento a priori sobre a distribuição de variáveis aleatórias — qual a probabilidade de que as variáveis aleatórias sejam distribuídas de acordo com uma ou outra distribuição particular.

Retiradas a partir de um processo de Dirichlet $\mathrm {DP} (N(0,1),\alpha )$. As quatro linhas usam diferentes $\alpha$ (de cima para baixo: 1, 10, 100 e 1000) e cada linha contém três repetições do mesmo experimento. Como visto a partir dos gráficos, retiradas de um processo de Dirichlet são distribuições discretas e se tornam menos concentradas (mais espalhadas) conforme $\alpha$ aumenta. Os gráficos foram geradas usando-se a visão do processo quebra-vara (descrito abaixo) para o processo de Dirichlet.

O processo de Dirichlet é especificado por uma distribuição de base $H$ e um número real positivo $\alpha$ chamado de parâmetro de concentração (também conhecimento como parâmetro de escalonamento). A distribuição de base é o valor esperado do processo, isto é, o processo de Dirichlet obtém distribuições "em torno da" distribuição de base da mesma forma que uma distribuição normal obtém números reais em torno de sua média. Entretanto, mesmo se a distribuição de base for contínua, as distribuições obtidas do processo de Dirichlet são quase certamente discretas. O parâmetro de escalonamento especifica quão forte é esta discretização: no limite de $\alpha \rightarrow 0$, as observações estão todas concentradas em único valor, enquanto que no limite de $\alpha \rightarrow \infty$, as observações se tornam contínuas. Entre os dois extremos, as observações são distribuições discretas com cada vez menos concentração conforme $\alpha$ aumenta.

O processo de Dirichlet também pode ser visto como a generalização de dimensão infinita da distribuição de Dirichlet. Da mesma forma que a distribuição de Dirichlet é o conjugado a priori para a distribuição categórica, o processo de Dirichlet é o conjugado a priori para distribuições discretas, não paramétricas e infinitas. Uma aplicação particularmente importante dos processos de Dirichlet é como uma distribuição de probabilidade a priori em modelos infinitos de mistura.

O processo de Dirichlet foi formalmente introduzido pelo estatístico Thomas Ferguson em 1973. Tem sido desde então aplicado em mineração de dados e aprendizado de máquina, entre outras áreas relacionadas com processamento de linguagem natural, visão computacional e bioinformática.

Introdução

Os processos de Dirichlet são geralmente usados quando se modelam dados que tendem a repetir valores anteriores de uma forma em que "o rico fica mais rico". Especificamente, suponha que a geração de valores $X_{1},X_{2}\dots$ possa ser simulada pelo seguinte algoritmo:

Input: $H$ (uma distribuição de probabilidade chamada de distribuição de base), $\alpha$ (um número real positivo chamado de parâmetro de escalonamento)

1. Obtenha $X_{1}$ a partir da distribuição $H$.

2. Para $n>1$:

a) Com probabilidade ${\frac {\alpha }{\alpha +n-1}}$, obtenha $X_{n}$ a partir de $H$.

b) Com probabilidade ${\frac {n_{x}}{\alpha +n-1}}$, configure $X_{n}=x$, em que $n_{x}$ é o número de observações anteriores $X_{j},j<n$, tal que $X_{j}=x$.

Ao mesmo tempo, em outro modelo comum para os dados, pressupõe-se que as observações $X_{1},X_{2},\dots$ são independentes e identicamente distribuídas de acordo com alguma distribuição $P$. O objetivo ao introduzir processos de Dirichlet é poder descrever os procedimentos descritos acima neste modelo de variáveis independentes e identicamente distribuídas.

As observações $X_{1},X_{2},\dots$ não são independentes, já que temos que considerar os resultados anteriores ao gerar o próximo valor. Elas são, no entanto, intercambiáveis. Este fato pode ser demonstrado ao calcular a distribuição de probabilidade conjunta das observações e perceber que a fórmula resultante depende apenas de quais valores $x$ ocorrem entre as observações e quantas repetições cada um tem. Por causa desta intercambiabilidade, o teorema da representação de De Finetti se aplica e implica que as observações $X_{1},X_{2},\dots$ são condicionalmente independentes dada uma distribuição (latente) $P$. Esta $P$ é ela mesma uma variável aleatória e tem uma distribuição. Esta distribuição (sobre distribuições) é chamada de processo de Dirichlet ($\mathrm {DP}$). Em suma, isto significa que obtemos um procedimento equivalente ao algoritmo acima:

1. Obtenha uma distribuição $P$ a partir de $\mathrm {DP} (H,\alpha )$,

2. Obtenha observações $X_{1},X_{2},\dots$ independentemente de $P$.

Na prática, entretanto, obter uma distribuição concreta $P$ é impossível, já que sua especificação exige uma quantidade infinita de informação. Este é um fenômeno comum no contexto da estatística não paramétrica bayesiana, em que uma tarefa típica é descobrir distribuições em espaços de função, o que efetivamente envolve infinitamente muitos parâmetros. A intuição mais importante é que, em muitas aplicações, as distribuições de dimensões infinitas aparecem apenas como um dispositivo computacional intermediário e não são exigidas nem para a especificação inicial das ideias anteriores, nem para a afirmação da inferência final. Os processos de Dirichlet podem ser usados para contornar exigências computacionais infinitas como descrito acima.

Definição formal

Dado um conjunto mensurável $S$, uma distribuição de probabilidade de base $H$ e um número real positivo $\alpha$, o processo de Dirichlet $\mathrm {DP} (H,\alpha )$ é um processo estocástico cujo caminho amostral (ou observação, isto é, um conjunto infinito de variados aleatórios obtidos a partir do processo) é uma distribuição de probabilidade sobre $S$ e o seguinte se aplica. Para qualquer partição finita e mensurável de $S$, diga $\{B_{i}\}_{i=1}^{n}$, se $X\sim \mathrm {DP} (H,\alpha )$, então:

$(X(B_{1}),\dots ,X(B_{n})\sim \mathrm {Dir} (\alpha H(B_{1}),...,\alpha H(B_{n})),$

em que $\mathrm {Dir}$ denota a distribuição de Dirichlet e a notação $X\sim D$ significa que a variável aleatória $X$ é distribuída de acordo com a distribuição $D$.

Visões alternativas

Há várias visões equivalentes do processo de Dirichlet. Além da definição acima, o processo de Dirichlet pode ser definido implicitamente por meio do teorema de De Finetti como descrito na primeira seção. Isto é frequentemente chamado de processo do restaurante chinês. Uma terceira alternativa é o processo quebra-vara, que define o processo de Dirichlet construtivamente ao escrever uma distribuição amostrada a partir do processo conforme $f(x)=\sum _{k=1}^{\infty }\beta _{k}\delta _{x_{k}}(x)$, em que $\{x_{k}\}_{k=1}^{\infty }$ são amostras a partir da distribuição de base $H$, $\delta _{x_{k}}$ é uma função indicadora centrada em $x_{k}$ (igual a zero em qualquer lugar exceto para $\delta _{x_{k}}(x_{k})=1$) e os $\beta _{k}$ são definidos por um esquema recursivo que repetidamente amostra a partir da distribuição beta $\mathrm {Beta} (1,\alpha )$.

Uso em modelos de mistura de Dirichlet

Simulação de 1.000 observações retiradas a partir de um modelo de mistura de Dirichlet. Cada observação no interior de um cluster é retirada independentemente a partir da distribuição normal multivariada $N(\mu _{k},1/4)$. As médias de cluster $\mu _{k}$ são retiradas a partir de uma distribuição $G$ que é ela mesma retirada a partir de um processo de Dirichlet com parâmetro de concentração $\alpha =0,5$ e distribuição de base $H=N(2,16)$. Cada linha é uma nova simulação.

Para entender o que os processos de Dirichlet são e o problema que eles resolvem, consideramos o exemplo do clustering de dados. É uma situação comum pressupor que os pontos de dados estão distribuídos de uma forma hierárquica em que cada ponto de dado pertence a um cluster (aleatoriamente escolhido) e que os membros de um cluster são posteriormente distribuídos aleatoriamente no interior daquele cluster.

Exemplo 1

Por exemplo, podemos estar interessados em como as pessoas votarão em uma série de questões em uma eleição futura. Um modelo razoável para esta situação pode ser classificar cada eleitor como um liberal, um conservador ou um moderado e, então, modelar o evento em que um eleitor diz "sim" a qualquer questão particular como uma variável aleatória de Bernoulli com probabilidade dependente do cluster político ao qual ele pertence. Ao observar como os votos foram distribuídos em propostas de legislação semelhante em anos anteriores, pode-se ajustar um modelo preditivo usando um algoritmo simples de clustering tal como k-means. Entretanto, este algoritmo exige que se saiba antecipadamente o número de clusters que geraram os dados. Em muitas situações, não é possível determinar isto antecipadamente e, mesmo quando podemos pressupor razoavelmente um número de clusters, ainda assim gostaríamos de poder verificar esta pressuposição. Por exemplo, no exemplo da votação acima, a divisão em liberais, conservadores e moderados pode não corresponder satisfatoriamente à realidade, já que atributos como religião, classe ou raça também podem ser críticos ao modelar comportamento eleitoral.

Exemplo 2

Em um outro exemplo, podemos estar interessados em modelar as velocidades das galáxias usando um modelo simples que assume que as velocidades estão divididas em clusters, por exemplo, pressupondo que cada velocidade é distribuída de acordo com a distribuição normal $v_{i}\sim N(\mu _{k},\sigma ^{2})$, em que a $i$-ésima observação pertence ao $k$-ésimo cluster de galáxias com velocidade esperada comum. Neste caso, não está claro como determinar a priori quantos clusters (de velocidades comuns) deve haver e qualquer modelo para isto seria altamente suspeito e deveria ser verificado com base nos dados. Ao usar um processo de Dirichlet antecipadamente para a distribuição das médias do cluster, contornamos a necessidade de especificar explicitamente antes do tempo quantos clusters há, mesmo que o parâmetro de concentração ainda o controle implicitamente.

Consideramos este exemplo com mais detalhe. Um primeiro modelo ingênuo é pressupor que há $K$ clusters de velocidades normalmente distribuídas com uma variância comum conhecida fixa $\sigma ^{2}$. Denotando o evento em que a $i$-ésima observação está no $k$-ésimo cluster como $z_{i}=k$, podemos escrever este modelo como:

${\begin{aligned}(v_{i}\mid z_{i}=k,\mu _{k})&\sim N(\mu _{k},\sigma ^{2})\\\mathrm {P} (z_{i}=k)&=\pi _{k}\\({\boldsymbol {\pi }}\mid \alpha )&\sim \mathrm {Dir} \left({\frac {\alpha }{K}}\cdot \mathbf {1} K\right)\\\mu _{k}&\sim H(\lambda )\end{aligned}}$

Isto é, pressupomos que os dados pertencem $K$ clusters distintos com médias $\mu _{k}$ e que $\pi _{k}$ é a probabilidade a priori (desconhecida) de um ponto de dado pertencer ao $k$-ésimo cluster. Assumimos que não temos qualquer informação inicial que distinga os clusters, o que é capturado pelo a priori simétrico $\mathrm {Dir} (\alpha /K\cdot \mathbf {1} _{K})$. Aqui, $\mathrm {Dir}$ denota a distribuição de Dirichlet e $\mathbf {1} _{K}$ denota um vetor de comprimento $K$ em que cada elemento é igual a 1. Nós atribuímos posteriormente distribuições independentes, idênticas e a priori $H(\lambda )$ a cada uma das médias de cluster, em que $H$ pode ser qualquer distribuição paramétrica com parâmetros denotados como $\lambda$. Assume-se que os hiperparâmetros $\alpha$ e $\lambda$ são constantes fixas conhecidas, escolhidas para refletir nossas crenças a priori sobre o sistema. Para entender a conexão com os a prioris do processo de Dirichlet, reescrevemos este modelo em uma forma equivalente, mas mais sugestiva:

${\begin{aligned}(v_{i}\mid {\tilde {\mu }}_{i})&\sim N({\tilde {\mu }}_{i},\sigma ^{2})\\{\tilde {\mu }}_{i}&\sim G=\sum _{k=1}^{K}\pi _{k}\delta _{\mu _{k}}({\tilde {\mu }}_{i})\\({\boldsymbol {\pi }}\mid \alpha )&\sim \mathrm {Dir} \left({\frac {\alpha }{K}}\cdot \mathbf {1} _{K}\right)\\\mu _{k}&\sim H(\lambda )\end{aligned}}$

Em vez de imaginar que primeiramente se atribui a cada ponto de dado um cluster e, em seguida, se obtém o ponto de dado a partir da distribuição associada com aquele cluster, pensamos agora em cada observação associada com o parâmetro ${\tilde {\mu }}_{i}$ obtido a partir de alguma distribuição discreta $G$ com suporte nas médias $K$. Isto é, estamos tratando agora ${\tilde {\mu }}_{i}$ como retirado a partir da distribuição aleatória $G$ e nossa informação a priori é incorporada ao modelo pela distribuição sobre as distribuições $G$.

Animação do processo de clusterização para dados unidimensionais usando distribuições gaussianas obtidas a partir de um processo de Dirichlet. Os histogramas dos clusters são mostrados em cores diferentes. Durante o processo de estimação do parâmetro, novos clusters são criados e crescem sobre os dados. A legenda mostra as cores dos clusters e os números de pontos de dados atribuídos a cada cluster.

Gostaríamos agora de estender este modelo à operação sem especificar previamente um número fixo de clusters $K$. Matematicamente, isto quer dizer que gostaríamos de selecionar uma distribuição aleatória a priori $G({\tilde {\mu }}_{i})=\sum _{k=1}^{\infty }\pi _{k}\delta _{\mu _{k}}({\tilde {\mu }}_{i})$, em que os valores das médias dos clusters $\mu _{k}$ são novamente independentemente distribuídas de acordo com $H\left(\lambda \right)$ e a distribuição sobre $\pi _{k}$ é simétrica sobre o conjunto infinito de clusters. Isto é exatamente o que é acompanhado pelo modelo:

${\begin{aligned}(v_{i}\mid {\tilde {\mu }}_{i})&\sim N({\tilde {\mu }}_{i},\sigma ^{2})\\{\tilde {\mu }}_{i}&\sim G\\G&\sim \mathrm {DP} (H(\lambda ),\alpha )\end{aligned}}$

Com isto em mãos, podemos entender melhor os méritos computacionais do processo de Dirichlet. Suponha que queremos obter $n$ observações a partir do modelo ingênuo com exatamente $K$ clusters. Um algoritmo simples para fazer isto seria obter $K$ valores de $\mu _{k}$ a partir de $H(\lambda )$, uma distribuição $\pi$ a partir de $\mathrm {Dir} \left(\alpha /K\cdot \mathbf {1} _{K}\right)$ e, então, para cada observação, amostrar independentemente o cluster $k$ com probabilidade $\pi _{k}$ e o valor da observação de acordo com $N\left(\mu _{k},\sigma ^{2}\right)$. É fácil ver que este algoritmo não funciona no caso em que nós permitimos clusters infinitos porque isto exigiria a amostragem de um parâmetro de dimensões infinitas $\pi$. Entretanto, ainda é possível amostrar observações $v_{i}$. Pode-se usar, por exemplo, a representação do restaurante chinês descrita abaixo e calcular a probabilidade para clusters usados e para um novo cluster a ser criado. Isto evita ter que especificar explicitamente $\pi$. Outras soluções são baseados em um truncamento de clusters. Um limite superior (alto) ao número real de clusters é introduzindo e os números de clusters superiores ao limite inferior são tratados como um cluster.

Ajustar o modelo descrito acima baseado em dados observados $D$ significa encontrar a distribuição a posteriori $p\left({\boldsymbol {\pi }},{\boldsymbol {\mu }}\mid D\right)$ sobre as probabilidades de cluster e suas médias associadas. No caso de dimensões infinitas, é obviamente impossível descrever explicitamente a distribuição a posteriori. Entretanto, é possível obter amostras a partir desta distribuição a posteriori usando uma amostragem de Gibbs modificada. Este é o fato crítico que torna a distribuição a priori do processo de Dirichlet útil para inferência.

Processo do restaurante chinês

Animação de um processo de restaurante chinês com parâmetro de escalonamento $a=0,5$. As mesas estão ocultas, uma vez que os clientes de uma mesa não podem mais ser dispostos. Entretanto, cada mesa tem infinitamente muitas cadeiras. (Registro de uma animação interativa.)

Uma metáfora amplamente empregada para o processo de Dirichlet é baseada no chamado processo do restuarante chinês. O nome deriva da impressão de que restaurantes chineses teriam infinitamente muitas mesas. A metáfora é como se segue:

Imagine uma restaurante chinês em que os clientes entram. Um novo cliente senta em uma mesa com uma probabilidade proporcional ao número de clientes já sentados lá. Adicionalmente, um cliente abre uma nova mesa com uma probabilidade proporcional ao parâmetro de escalonamento $\alpha$. Depois que infinitamente muitos clientes entraram, obtém-se a distribuição de probabilidade sobre infinitamente muitas mesas a serem escolhidas. Esta distribuição de probabilidade sobre as mesas é uma amostra aleatória das probabilidades das observações retiradas a partir do processo de Dirichlet com parâmetro de escalonamento $\alpha$.

Se as retiradas a partir da medida de base $H$ forem associadas com toda mesa, a distribuição resultante sobre o espaço amostral $S$ é uma amostra aleatória de um processo de Dirichlet. O processo do restaurante chinês é relacionado como um esquema de amostragem de urna de Pólya que produz amostras a partir de distribuições finitas de Dirichlet.

Já que os clientes sentam em uma mesa com uma probabilidade proporcional ao número de clientes já sentados na mesa, duas propriedades do processo de Dirichlet podem ser deduzidas:

1. O processo de Dirichlet exibe uma propriedade auto-reforçante: quanto maior a frequência com que um dado valor foi amostrado no passado, maior a probabilidade de que ele seja amostrado novamente.
2. Mesmo se $H$ for uma distribuição sobre um conjunto não enumerável, há uma probabilidade diferente de zero de que duas amostras terão exatamente o mesmo valor, porque a massa da probabilidade se concentrará sobre um pequeno número de mesas.

Processo quebra-vara

Uma terceira abordagem ao processo de Dirichlet é a visão do chamado processo quebra-vara. Lembre-se de que retiradas de um processo de Dirichlet são distribuições sobre um conjunto $S$. Conforme notado previamente, a distribuição retirada é discreta com probabilidade igual a 1. Na visão do processo quebra-vara, nós usamos explicitamente a discrição e damos a função massa de probabilidade desta distribuição discreta (aleatória) como:

$f(\theta )=\sum _{k=1}^{\infty }\beta _{k}\cdot \delta _{\theta _{k}}(\theta )$

em que $\delta _{\theta _{k}}$ é a função indicadora que avalia em zero para todos os lugares, exceto para $\delta _{\theta _{k}}(\theta _{k})=1$. Já que esta distribuição é ela mesma aleatória, sua função massa é parametrizada por dois conjuntos de variáveis aleatórias: as locações $\{\theta _{k}\}_{k=1}^{\infty }$ e as probabilidades correspondentes $\{\beta _{k}\}_{k=1}^{\infty }$. No que se segue, apresenta-se sem a prova quais são estas variáveis aleatórias. As locações $\theta _{k}$ são independentes e identicamente distribuídas de acordo com $H$, a distribuição de base do processo de Dirichlet. As probabilidades $\beta _{k}$ são dadas por um procedimento que lembra a quebra de uma vara de comprimento unitário (daí o nome):

$\beta _{k}=\beta '_{k}\cdot \prod _{i=1}^{k-1}(1-\beta '_{i})$

em que $\beta '_{k}$ são variáveis aleatórias independentes com distribuição beta $\mathrm {Beta} (1,\alpha )$. A semelhança com a quebra de uma vara pode ser vista ao considerar $\beta _{k}$ como o comprimento de uma peça de uma vara. Começamos com uma vara de comprimento unitário e, em cada passo, quebramos uma porção da vara restante de acordo com $\beta '_{k}$ e atribuímos esta peça quebrada a $\beta _{k}$. A fórmula pode ser entendida ao notar que, depois de atribuir aos primeiros $k-1$ valores suas porções, o comprimento do restante da vara é igual a $\prod _{i=1}^{k-1}(1-\beta '_{i})$ e esta peça é quebrada de acordo com $\beta '_{k}$ e atribuída a $\beta _{k}$.

Quanto menor for $\alpha$, menor porção da vara restará para valores subsequentes (em média), produzindo distribuições mais concentradas.

Esquema de urna de Pólya

Outra forma de visualizar o processo de Dirichlet e o processo do restaurante chinês é por um esquema de urna de Pólya modificada. Imagine que começamos com uma urna cheia de $\alpha$ bolas pretas. Então, procedemos como se segue:

1. Cada vez que precisarmos de uma observação, retiramos uma bola da urna.
2. Se a bola for preta, geramos uma nova cor uniformemente (diferente de preta), rotulamos uma nova bola com esta cor, depositamos esta nova bola na urna junto com a bola que retiramos e retornamos a cor que geramos.
3. De outra forma, rotulamos uma nova bola com a cor da bola que retiramos, depositamos a nova bola na urna com a bola que retiramos e retornamos a cor que observamos.

A distribuição resultante sobre as cores é igual à distribuição sobre as mesas no processo do restaurante chinês. Além disto, quando retiramos uma bola preta, se em vez de gerarmos uma nova cor, escolhêssemos um valor aleatório a partir da distribuição de base $H$ e usássemos aquele valor para rotular a nova bola, a distribuição resultante sobre os rótulos será igual à distribuição sobre valores em um processo de Dirichlet.

Aplicações do processo de Dirichlet

Processos de Dirichlet são frequentemente usados em estatística não paramétrica bayesiana. "Não paramétrica" aqui não quer dizer um modelo sem parâmetro, mas um modelo em que as representações crescem na medida em que mais dados são observados. Os modelos não paramétricos bayesianos têm ganhado considerável popularidade no campo do aprendizado de máquina devido à flexibilidade mencionada acima, especialmente no caso do aprendizado não supervisionado. Em um modelo não paramétrico bayesiano, as distribuições a priori e a posteriori não são distribuições paramétricas, mas processos estocásticos. O fato de que a distribuição de Dirichlet é uma distribuição de probabilidade sobre o simplex dos conjuntos de números não negativos que somam a um a torna uma boa candidata a modelar distribuições sobre distribuições ou distribuições sobre funções. Adicionalmente, a natureza não paramétrica deste modelo torna-o uma candidato ideal para clusterizar problemas em que o número distinto de clusters é desconhecido de antemão. Além disto, o processo de Dirichlet também tem sido usado para desenvolver misturas de modelos especialistas, no contexto de algoritmos de aprendizado supervisionado (conjuntos de regressão ou classificação). Por exemplo, misturas de processos especialistas gaussianos, em que o número de especialistas exigidos deve ser inferido a partir dos dados.

Já que as retiradas de um processo de Dirichlet são discretas, um uso importante é como uma probabilidade a priori de modelos infinitos de mistura. Neste caso, $S$ é o conjunto paramétrico de distribuições de componentes. Por isso, o processo gerativo consiste em retirar uma amostra de um processo de Dirichlet e, para cada ponto de dado por sua vez, um valor é retirado da distribuição desta amostra e usado como a distribuição do componente para aquele ponto de dados. O fato de que não há limite para o número de componentes distintos que podem ser gerados torna este tipo de modelo apropriado para o caso em que o número de componentes da mistura não está bem definido de antemão. Por exemplo, a mistura infinita de modelos gaussianos, assim como os modelos de regressão de mistura associados.

A natureza infinita destes modelos também lhes confere aplicações de processamento de linguagem natural, nas quais é frequentemente desejável que o vocabulário seja tratado como um conjunto infinito e discreto.

O processo de Dirichlet pode também ser usado para testes de hipóteses não paramétricos, isto é, para o desenvolvimento de versões não paramétricas bayesianas de testes de hipóteses não paramétricos clássicos, por exemplo, o teste do sinal, o teste U de Mann-Whitney, o teste de postos sinalizados de Wilcoxon, dentre outros. Por exemplo, as versões não paramétricas bayesianas do teste U de Mann-Whitney e o teste de postos sinalizados de Wilcoxon têm sido desenvolvidas pelo uso do processo de Dirichlet impreciso, um processo de Dirichlet com ignorância a priori.