Modelos de mistura finitos são ferramentas de modelagem probabilística flexíveis e podero- sas (McLachlan e Peel, 2000; Figueiredo e Jain, 2002). Conforme discutido por McLachlan e Peel (2000) e Jordan e Xu (1995), estes modelos fornecem um conveniente compromisso entre abordagens não-paramétricas e paramétricas. A flexibilidade não paramétrica provém do fato de que o número de componentes pode crescer conforme o necessário, enquanto que o fato de os componentes da mistura serem de forma paramétrica específica6mantém a dimensão do es- paço de busca em um tamanho razoável. Modelos de mistura finitos são utilizados em diversas áreas, como Biologia, Engenharia e Medicina (McLachlan e Peel, 2000). O uso de tais modelos para o agrupamento de dados permite tratar diversas questões, como o número de grupos, de maneira formal do ponto de vista estatístico (Fraley e Raftery, 1998, 2002; McLachlan e Peel, 2000).
Conforme será discutido no Capítulo 2, a definição de um modelo de mistura requer uma decisão sobre quais formas dos componentes são apropriadas para modelar os dados. É comum, na ausência de informação a priori, supor que os componentes do modelo são distribuições de probabilidades gaussianas (Jain e Dubes, 1988). Dentre as razões para tal, pode-se destacar o fato de que, por meio de um número suficiente de componentes gaussianos, pode-se aproximar quase qualquer função de densidade com acurácia arbitrária (Bishop, 2006).
Por tais razões, nesta tese tem-se como material de estudo os modelos de mistura finitos, nos quais os componentes são distribuições de probabilidades gaussianas. Estes modelos costumam ser denominados Gaussian Mixture Models (GMMs). Em aplicações de agrupamento de dados, tanto não supervisionado quanto semissupervisionado, o uso destes modelos apresenta alguns desafios. Especificamente, a estimação de parâmetros de um GMM pode ser vista como um problema de otimização que tem como característica um grande número de mínimos locais.
1.4 Motivações e Hipóteses 7 Embora esse seja um cenário típico para aplicação de AEs, o uso destes considerando modelos gerais, com o menor número de premissas possíveis, ainda é pouco explorado. Além disso, os poucos trabalhos nesta linha de pesquisa não fazem uso da extensa literatura existente sobre o assunto no contexto de algoritmos de busca locais. Levando isso em consideração, a primeira hipótese desta tese é definida como:
Hipótese 1: Um AE desenvolvido considerando estratégias bem conhecidas da literatura de algoritmos de busca local é capaz de estimar os parâmetros de um GMM, tendo como conhecimento a priori apenas os dados e sem nenhuma imposição estrutural sob o mo- delo, de forma eficiente e competitiva com abordagens já existentes para a estimação de parâmetros.
Considerando cenários de ADR, duas linhas de pesquisa são pouco exploradas na literatura. A primeira consiste em algoritmos capazes de tratar tanto os dados quanto as restrições de forma online, e.g., dados processados sob demanda. Este tipo de algoritmo é especialmente relevante em aplicações envolvendo grandes bases de dados. Baseando-se nesta lacuna da literatura, a segunda hipótese desta tese é definida como:
Hipótese 2: Um algoritmo de ADR que processa os dados de forma online é capaz de obter acurácia comparável com algoritmos da literatura de ADR que processam os dados em lotes (batches).
Ao incorporar determinados tipos de restrições em um GMM, gera-se uma complexidade adicional à estimação dos seus parâmetros. Especificamente, o uso de restrições sobre pa- res de objetos, especialmente se dois objetos devem ou não estar no mesmo grupo7, cria uma dependência entre rótulos de objetos distintos. Tal dependência torna o modelo complexo e, usualmente, requer aproximações para que o mesmo possa ser usado na prática. Além disso, por muitas vezes estas restrições são obtidas de rótulos de classe ou sem conhecimento sobre a disposição espacial dos dados no espaço de atributos, conforme será discutido no Capítulo 4. Como uma classe não necessariamente corresponde a um grupo, em ambas as situações as restrições podem não ter nenhuma concordância com a distância entre objetos, critério pelo qual a maioria dos algoritmos de agrupamento se baseia para formar grupos. Por esta razão, diversos algoritmos da literatura ficam presos a soluções sub-ótimas quando tentam incorporar tais restrições em suas partições dos dados. Uma forma de se evitar tal problema é considerar que as restrições referem-se a classes, e que tais classes podem ser formadas por mais de um grupo. Embora existam trabalhos na literatura nessa linha de pesquisa (Zhao e Miller, 2005; Raghuram et al., 2014), os mesmos dependem de um parâmetro que define um compromisso entre atender restrições e a qualidade da solução, que por sua vez é de difícil ajuste por parte do usuário. Levando em consideração todos esses aspectos, formula-se a terceira hipótese desta tese:
Hipótese 3: É possível desenvolver algoritmos para ADR com as seguintes propriedades: (i) capacidade de lidar com situações de mais de um grupo por classe, mesmo que recebendo como supervisão restrições entre pares de objetos; (ii) ausência de parâmetros críticos de compromisso entre qualidade de soluções e rigidez de restrições; (iii) desobrigação de que o usuário defina o número de grupos por classe a priori; (iv) eficiência computacional. Considerando o exposto, esta tese tem como objetivo contribuir com a literatura tanto de aprendizado não supervisionado quanto semissupervisionado. Os algoritmos propostos, bem como os experimentos realizados para validar as hipóteses aqui levantadas, constituem contri- buições relevantes para diversas áreas, tais como: aprendizado de máquina, algoritmos evo- lutivos e MD. Boa parte do material apresentado nessa tese foi publicada durante o trabalho de doutoramento (Covões e Hruschka, 2011; Sestaro et al., 2012; Covões e Hruschka, 2013; Covões et al., 2013c,a,b).