Aprendizado semissupervisionado via competição de partículas em redes complexas: modelagem, análise e aplicações

Aprendizado semissupervisionado viacompetição de partículas em redes

complexas: modelagem, análise e aplicações

Thiago Christiano Silva

ii

iii

SERVIÇO DE PÓS-GRADUAÇÃO DOICMC-USP

Data de Depósito: 20 de setembro de 2011

Assinatura:

Aprendizado semissupervisionado via competição departículas em redes complexas: modelagem, análise e

aplicações

Thiago Christiano Silva

Orientador: Prof. Dr. Zhao Liang

Monografia apresentada ao Instituto de Ciências Ma-temáticas e de Computação — ICMC/USP, para oexame de Qualificação, como parte dos requisitos paraobtenção do título de Doutor em Ciências de Compu-tação e Matemática Computacional.

USP - São CarlosSetembro de 2011

iv

Resumo

Aprendizado de máquina figura como uma área de pesquisa que visa a de-senvolver métodos computacionais capazes de “aprender” com a experiência.As técnicas tradicionais de aprendizado de máquina, na construção de clas-sificadores, necessitam de uma grande quantidade de dados rotulados. Estesdados são geralmente difíceis de serem obtidos, principalmente quando envol-vem a rotulação manual por parte de um especialista. Recentemente, uma novavertente da área de aprendizado de máquina, intitulada aprendizado semissu-pervisionado, tem atraído a atenção de muitos pesquisadores. Esta forma deaprendizado objetiva a propagação de rótulos para todos os dados não rotula-dos, de tal forma a preservar a distribuição original. Além disso, recentemente,um crescente interesse nas técnicas que utilizam redes para representar os da-dos foi verificado. Este fato deve-se ao surgimento das redes complexas comoum tópico unificador de sistemas complexos e como uma poderosa ferramentade representação e abstração de dados, sendo capazes de capturar suas relaçõesespaciais, topológicas e funcionais. Nos últimos anos, foram desenvolvidas téc-nicas de aprendizado de máquina baseadas em competição partículas por meiode redes complexas, as quais dispõem de alta precisão e baixa complexidadecomputacional. Todavia, apenas resultados empíricos estão presentes na litera-tura, carecendo tal modelo de uma análise matemática rigorosa. Com o intuitode suprir esta lacuna, neste projeto serão desenvolvidas técnicas de competi-ção de partículas, no contexto de aprendizado semissupervisionado, baseadasem competição e cooperação de partículas em redes complexas, em conjuntocom uma modelagem analítica do sistema competitivo. A hipótese assumida éque tal modelo de competição exista e possa ser analiticamente avaliado. Alémdisso, o assunto de confiabilidade dos dados em aprendizado semissupervisio-nado será analisado, o qual ainda configura-se como um ramo pouco estudadona literatura. Com o objetivo de validar as técnicas desenvolvidas em proble-mas reais, estas serão aplicadas para análise de dados em bases amplamenteaceitas na comunidade. Os modelos matemáticos propostos serão avaliadosquanto a sua acurácia na previsão dos processos descritos, por meio de méto-dos estatísticos. Enfim, acredita-se que este estudo possa gerar contribuiçõesrelevantes para a área de aprendizado de máquina.

Palavras-chave: aprendizado competitivo, caminhadas aleatórias, aprendizado semis-supervisionado, classificação, redes complexas.

v

vi

Abstract

Machine Learning is evidenced as a research area whose main purpose is todevelop computational methods that are capable of learning with their previ-ously acquired experiences. The traditional machine learning techniques, inwhat concern about classifiers, must be presented to a significant amount oflabeled data in order to produce relevant results. In a general manner, thesedata are cumbersome and expensive to gather, by virtue of requiring manuallabeling of an expert. Recently, a new branch of this research area, denomina-ted semi-supervised learning, has attracted attention of the researchers. Thislearning paradigm aims to propagate labels to all the unlabeled data, alwayspreserving its initial distribution. Besides that, in the last years, an increasinginterest in techniques based on graphs has been verified. This emergence isexplained by the inherent advantages provided by the complex network re-presentation, which is able to capture the spatial, topological and functionalrelations of the data. In the recent years, it has been proposed machine le-arning techniques based on particle competition by using complex networks,which harmonize high precision and low computational complexity. However,only empirical results have been presented, without any rigorous mathemati-cal analysis. In light of this absence, in this work, we will develop techniquesbased on particle competition, in the context of semi-supervised learning, aswell as a solid analytical model which describes the behavior of the proposedtechnique. The assumed hypothesis is that such competition model exists andis passible of being analytically evaluated. In addition to that, data reliabilityissues will be explored in the semi-supervised learning. Such matter is found tobe of little investigation in the literature. With the purpose of validating thesetechniques on real problems, simulations on broadly accepted databases willbe conducted. Ultimately, the proposed mathematical model will be evaluatedagainst the empirical behavior of the model, with the aid of statistical methods.Finally, it is expected that this study will contribute, in a relevant manner, tothe machine learning area.

Keywords: competitive learning, random walks, semi-supervised learning, classifica-tion, complex networks.

vii

viii

Sumário

Resumo v

Abstract vii

Sumário ix

Lista de Figuras xi

1 Introdução 11.1 Objetivos e Motivações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Organização do Documento . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Redes Complexas 112.1 Evolução Histórica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Modelos de Formação de Rede . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.1 Redes Randômicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.2 Redes de Pequeno Mundo . . . . . . . . . . . . . . . . . . . . . . . 152.2.3 Redes Livre de Escala . . . . . . . . . . . . . . . . . . . . . . . . . 172.2.4 Redes Aleatórias Clusterizadas . . . . . . . . . . . . . . . . . . . . 18

2.3 Detecção de Comunidades . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3.1 Conceitos Relevantes . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3.2 Trabalhos Relevantes . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3.3 Competição de Partículas para Detecção de Comunidades . . . . 21

2.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3 Aprendizado Semissupervisionado 253.1 Aprendizado de Máquina . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2 Aprendizado Semissupervisionado: Definições, Motivações e Modelos . 28

3.2.1 Uma Breve Evolução Histórica . . . . . . . . . . . . . . . . . . . . 283.2.2 Motivações para o Aprendizado Semissupervisionado . . . . . . 293.2.3 Formulação Matemática . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3 Abordagens de Aprendizado Semissupervisionado . . . . . . . . . . . . 323.3.1 Modelos Generativos . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3.2 Métodos de Separação por Regiões de Baixa Densidade . . . . . . 333.3.3 Métodos Baseados em Grafos . . . . . . . . . . . . . . . . . . . . . 33

3.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

ix

x Sumário

4 Resultados Obtidos 494.1 Modelagem do Sistema de Competição de Partículas via Sistema Dinâ-

mico Estocástico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.1 Visão Geral do Modelo . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.2 Derivação da Matriz de Transição Competitiva . . . . . . . . . . . 524.1.3 O Modelo de Aprendizado Competitivo Semissupervisionado . . 604.1.4 As Condições Iniciais do Sistema Competitivo . . . . . . . . . . . 624.1.5 O Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.1.6 Análise de Complexidade Algorítmica . . . . . . . . . . . . . . . . 64

4.2 Análise Matemática do Modelo Competitivo . . . . . . . . . . . . . . . . 674.2.1 Resultados Teóricos . . . . . . . . . . . . . . . . . . . . . . . . . . 674.2.2 Um Exemplo Numérico . . . . . . . . . . . . . . . . . . . . . . . . 804.2.3 Validação dos Resultados Teóricos . . . . . . . . . . . . . . . . . . 83

4.3 Simulações Computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . 854.3.1 Análise Empírica da Sensibilidade dos Parâmetros do Modelo . . 854.3.2 Simulações com Bases de Dados Artificiais . . . . . . . . . . . . . 874.3.3 Simulações em Bases de Dados Reais . . . . . . . . . . . . . . . . 904.3.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5 Proposta de Pesquisa 975.1 Estratégia de Desenvolvimento . . . . . . . . . . . . . . . . . . . . . . . . 97

5.1.1 Modelagem da Técnica de Competição de Partículas para Apren-dizado Semissupervisionado . . . . . . . . . . . . . . . . . . . . . 98

5.1.2 Análise Matemática do Modelo de Competição Semissupervisi-onado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.1.3 Extensão do Modelo Competitivo ao Aprendizado Não Supervi-sionado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5.1.4 Detecção de Vértices e Comunidades Sobrepostos . . . . . . . . . 1005.1.5 Tratamento da Confiabilidade dos Dados no Processo de Apren-

dizado Semissupervisionado . . . . . . . . . . . . . . . . . . . . . 1015.2 Atividades e Cronograma . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025.3 Materiais e Recursos Disponíveis . . . . . . . . . . . . . . . . . . . . . . . 1035.4 Forma de Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . 103

Referências Bibliográficas 105

Lista de Figuras

1.1 Exemplo de rede com estrutura de comunidades retirado de uma redede proteínas. As cores representam as comunidades. Figura extraída de(Girvan e Newman, 2002) . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.1 Um exemplo de rede aleatória de Erdös e Rényi. (a) uma rede construídapor meio da abordagem randômica proposta por Erdös e Rényi; (b) ográfico da média de distribuição de grau de uma rede apresentando N =10000 e p = 0.2. Figura integralmente extraída de Costa et al. (2007). . . . 14

2.2 Método de construção de uma rede de pequeno mundo, de acordo como proposto por Watts e Strogatz em (Watts e Strogatz, 1998). Figura ex-traída de Costa et al. (2007). . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Comportamento da rede com a mudança do parâmetro responsável pelafrequência de remanejamento das arestas. . . . . . . . . . . . . . . . . . 16

2.4 (a) Ilustração de uma rede livre de escala; (b) Gráfico da distribuição degrau em função do grau k. Figura modificada a partir da proposta emBarabasi e Albert (1999). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5 Esquemático de uma rede aleatória clusterizada. As comunidades sãorepresentadas pelas cores. Figura integralmente retirada de Papadopou-los et al. (2009). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1 Esquemático dos três modos de aprendizado de máquina. Aprendizado:(a) não supervisionado (agrupamento); (b) semissupervisionado (classi-ficação semissupervisionada); (c) supervisionado (classificação supervi-sionada). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2 Motivação para o estudo de aprendizado semissupervisionado. A linhapontilhada mostra o plano decisor que divide as duas classes feita porum algoritmo supervisionado. A linha contínua denota o plano decisorgerado por um algoritmo semissupervisionado. . . . . . . . . . . . . . . 30

3.3 Motivação para utilização de grafos. (a) Problema inicial para classi-ficação semissupervisionada. (b) Resultado obtido aplicando SVM. (c)Resultado obtido aplicando kNN. (d) Resultado ideal. Figura extraídade Zhou et al. (2003). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

xi

xii Lista de Figuras

4.1 Uma típica situação em que a partícula vermelha, presentemente locali-zada no vértice v1, tem de selecionar o próximo vizinho a visitar. Nesteexemplo, há 2 partículas, vermelha e azul (a partícula azul não é mos-trada). A cor bege denota os vértices que ainda não foram dominadospor quaisquer partículas até o instante t. . . . . . . . . . . . . . . . . . . . 55

4.2 Ilustração do procedimento de reanimação. Há duas partículas, a ver-melha e azul, localizadas nos vértices v17 e v1 no instante t, respectiva-mente, as quais se tornaram exaustas. A rede engloba 20 vértices. Acor do vértice representa qual partícula está impondo o maior nível dedominação no tempo t. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.3 Diagrama de fluxo que indica, em alto nível, como o sistema dinâmicoφ evolui no tempo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.4 Tempo consumido para que N(t) se estabilize. Cada ponto na curva éuma média de 10 realizações independentes. As barras verticais de errorepresentam o maior e menor tempos de processamento. . . . . . . . . . 68

4.5 Uma rede construída para ilustrar a trajetória que uma partícula devepercorrer para aumentar uma entrada arbitrária de N(t) o mais rápidopossível. (a) Rede sem autolaços; (b) rede com autolaços. . . . . . . . . . 74

4.6 Comparação entre as distribuições teórica e empírica para três vérticesdistintos: v4, v11 e v16 em relação ao nível de dominação imposto pelapartícula vermelha. Pode-se verificar que o nível de dominação maisprovável que a partícula vermelha imporá ao vértice v4 será aproxima-damente de 0.88 com 34% de chance, ao vértice v11 será 0.53 com 47% dechance, e ao vértice v16 será 0.14 com 33% chance. . . . . . . . . . . . . . 85

4.7 Acurácia de classificação vs. λ. Nestas simulações, N = 1000, há 4comunidades de mesmo tamanho, 〈k〉 = 16, zout/〈k〉 = 0.4 e ∆ = 0.07.Cada ponto na curva é a média de 100 realizações. As barras verticaisindicam o desvio padrão. . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.8 Acurácia de classificação vs. λ. Nestas simulações, N = 1000, há 4comunidades de mesmo tamanho, 〈k〉 = 16, zout/〈k〉 = 0.4 e λ = 0.6.Cada ponto na curva é a média de 100 realizações. As barras verticaisindicam o desvio padrão. . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4.9 Ilustração de um processo de classificação semissupervisionada via com-petição de partículas. As redes possuem 100 vértices. Vértices escurosainda não foram dominados por nenhuma partícula. As cores nos vér-tices representam a partícula que o está dominando. Retrato da redequando: (a) t = 0; (b) t = 100; (c) t = 200; e (d) t = 300. . . . . . . . . . . 88

4.10 Comportamento evolucional do nível de dominação médio imposto pe-las partículas no modelo. (a) Nível médio de dominação imposto pelapartícula 1; e (b) Mesma informação para a partícula 2. . . . . . . . . . . 89

4.11 Classificação de dados semissupervisionada. A cor do vértice indica apartícula que o está dominando. Os pontos escuros são vértices aindanão dominados. (a) e (b) Duas classes com formatos de banana; (c) e (d)Duas classes, cada qual seguindo uma distribuição Highleyman; (e) e (f)Duas classes, cada qual seguindo uma distribuição Lithuanian; (g) e (h)Quatro classes, cada qual seguindo uma distribuição Gaussiana. . . . . . 91

CAPÍTULO

1Introdução

Os seres humanos nascem com uma capacidade surpreendente de aprender. Comela, absorvem e assimilam conhecimento durante toda a vida. Com o propósito de si-mular computacionalmente esta capacidade, surgiu a área da Ciência da Computaçãodenominada aprendizado de máquina. Essa área visa a desenvolver métodos compu-tacionais capazes de “aprender” com a experiência (Bishop, 2007; Duda et al., 2000;Mitchell, 1997). Por meio da representação computacional de dados obtidos a partirde domínios diversos, as técnicas de aprendizado de máquina podem, de forma auto-mática, gerar modelos capazes de organizar o conhecimento existente ou ainda imitaro comportamento de um especialista humano nos domínios considerados. De umaforma geral, as técnicas de aprendizado de máquina são tradicionalmente classificadasem dois modos principais: aprendizado supervisionado e aprendizado não supervisionado(Bishop, 2007; Mitchell, 1997). No aprendizado supervisionado, o objetivo é deduzirconceitos a partir de exemplos rotulados de acordo com uma classe conhecida. Istoé, o processo de aprendizagem visa à construção de uma função de mapeamento en-trada/saída com base na observação dos dados de treinamento fornecidos. Quandoo rótulo é composto por valores discretos, o problema é denominado classificação e,quando valores contínuos são utilizados, regressão. Já no aprendizado não supervisi-onado, a tarefa principal está no agrupamento de dados segundo algum critério desimilaridade estabelecido, e o processo, neste caso, é guiado pelos dados, pois não énecessário um conhecimento prévio sobre as classes existentes (Mitchell, 1997).

A tarefa de rotular manualmente os dados pode ser um processo lento e caro, quenormalmente envolve o trabalho de um especialista. Para lidar com essa dificuldade,foi proposto o aprendizado semissupervisionado, cujo objetivo primário reside em pro-pagar os rótulos para os dados não rotulados. O classificador semissupervisionado

1

2 Capítulo 1 - Introdução

é induzido a partir de uma base de dados, geralmente, composta por uma grandequantidade de dados não rotulados e apenas uma pequena parcela de dados rotula-dos é fornecida. Desta forma, o trabalho do especialista na rotulagem dos exemplos éconsideravelmente reduzido. Além disso, resultados empíricos têm demonstrado quea utilização de dados não rotulados pode aumentar o desempenho do classificador(Chapelle et al., 2006).

A competição é um processo natural observável na natureza e em diversos siste-mas sociais que compartilham recursos escassos, tais como água, comida, parceiros,territórios, entre muitos outros. O aprendizado competitivo é uma importante abor-dagem no aprendizado de máquina e é amplamente utilizado em redes neurais arti-ficiais para realizar aprendizado não supervisionado. Trabalhos relevantes anterioresincluem o desenvolvimento do famoso Mapa Auto-Organizável (SOM - Self-organizingMap) (Kohonen, 1990), Aprendizado Competitivo Diferencial (Kosko, 1991), e Teoriade Ressonância Adaptativa (ART - Adaptive Resonance Theory) (Carpenter e Grossberg,1987; Grossberg, 1987). Desde então, muitas redes neurais baseadas em aprendizadocompetitivo foram desenvolvidas (Amorim et al., 2007; Athinarayanan et al., 2002; Jainet al., 2010; Kaylani et al., 2010; López-Rubio et al., 2009; Lu e Ip, 2009; Meyer-Bäse eThümmler, 2008; N. Allinson e Slack, 2001; Principe e Miikkulainen, 2009; Tan et al.,2008) e uma vasta gama de aplicações foi verificada (Bacciu e Starita, 2008; Chen et al.,2005; Deboeck e Kohonen, 2010; do Rêgo et al., 2010; Liu et al., 2008; Wang et al., 2009;Xu e II, 2005), quais sejam em agrupamento de dados, visualização computacionalde dados, reconhecimento de padrões e processamento de imagens. Sem sombras dedúvidas, redes neurais baseadas em aprendizado competitivo representam um dosprincipais sucessos do desenvolvimento de redes neurais. Entretanto, dois problemasremanescem: (i) geralmente, a rede construída é pequena. Desta forma, a competiçãoocorre entre um pequeno número de neurônios; consequentemente, o modelo podenão exibir grande robustez para o processamento dos dados. (ii) Não há uma ligaçãodireta entre os dados de entrada e a rede neural treinada. Quando um grande conjuntode dados é mapeado em uma rede com um pequeno número de neurônios, constituiuma tarefa complexa traduzir a correspondência entre os dados originais e a rede neu-ral treinada. Esta é uma das razões pelas quais as redes neurais são, normalmente,consideradas como sistemas “caixa-preta”.

Uma caminhada aleatória é uma formalização matemática de uma trajetória consis-tindo em tomar sucessivos passos aleatórios. Tal conceito já foi usado para descrevermuitos fenômenos naturais, bem como foi aplicado para resolver inúmeros problemasde engenharia, tais como em correspondência entre grafos (graph matching) e reconhe-cimento de padrões (Gori et al., 2005), segmentação de imagens (Grady, 2006), modela-gem de redes neurais (Jiang e Wang, 2000; Liang et al., 2009), indicação de centralidadede uma rede (Noh e Rieger, 2004), partição de redes (Zhou, 2003a), construção e aná-

- 3

lise de redes de telecomunicação (Zeng et al., 2010; Zhong et al., 2008), entre diversosoutros. Entretanto, até o presente momento, não há teoria ainda que descreva um pro-cesso geral de várias caminhadas aleatórias que se interagem.

Nos últimos anos, ocorreu um intenso desenvolvimento em uma área de pesquisachamada redes complexas. Tais redes têm emergido como um tópico unificador em sis-temas complexos e estão presentes em vários ramos da ciência (Bornholdt e Schuster,2003). Estruturalmente, as redes complexas são representadas por um grafo de grandeescala G = 〈V , E〉, em que V representa o conjunto de vértices e E , o conjunto dearestas. Segundo Albert et al. (2004), as redes complexas são modelos para sistemasem geral, em virtude de possuírem uma topologia não trivial, além de serem com-postas por uma grande quantidade de vértices. Dentre alguns exemplos plausíveisde representação em rede, incluem-se: a Internet (Faloutsos et al., 1999), a World WideWeb (WWW) (Albert et al., 1999), redes neurais biológicas (Sporns, 2002), redes sociaisentre indivíduos (Scott, 2000) e entre companhias e organizações (Mizruchi, 1982), ca-deias alimentares (Montoya e Solé, 2002), redes do metabolismo (Jeong et al., 2000) ede distribuição como a corrente sanguínea (West et al., 1999), rotas de entrega postal ede distribuição de energia elétrica (Albert et al., 2004), etc. De acordo com (Strogatz,2001), algumas características inerentes a esse tipo de rede são: a complexidade estru-tural - que se traduz na dificuldade de visualização da rede; a evolução - que marcaa constante alteração na estrutura da rede devido à inclusão e à remoção de vérticese conexões; a diversidade de conexões - pois estas ligações entre os vértices podemapresentar muitas variações em suas características, tais como a capacidade, o compri-mento, a largura e o sentido; e a dinâmica e a estrutura complexas - as quais influem emgrande escala nos estados de uma rede, já que podem ser entendidas como o tráfegode informações (Zhao et al., 2007), as ocorrências de falhas de comunicação (Zhao et al.,2004, 2005, 2007), as relações de similaridade entre vértices, a distribuição de funções(Newman, 2003), entre outras.

As redes com topologias complexas eram tradicionalmente descritas, em meadosda década de 60, de acordo com o modelo proposto em (Erdös e Rényi, 1959), mais co-nhecido como grafos randômicos ou redes randômicas. Em 1998, Watts e Strogatz des-cobriram que a média de caminhos mais curtos em uma rede pode ser drasticamentereduzida por uma alteração aleatória de poucas ligações, partindo-se de uma rede re-gular (Watts e Strogatz, 1998). Esta rede resultante é chamada de Rede de PequenoMundo (Small-World Network). Em 1999, Barabási e Albert descobriram que muitasredes reais têm uma distribuição de grau dos vértices que obedece a lei de potência:P(k) ∼ k−γ, na qual k é o número de ligações de um vértice escolhido aleatoriamentee γ é o expoente de escala (Barabasi e Albert, 1999). Essa distribuição heterogênea mo-dela a existência de um pequeno grupo de vértices que apresenta um grande númerode ligações. Tais redes são denominadas Redes Livres de Escala (Scale-free Networks).


Por outro lado, existem as Redes Aleatórias (Random Networks), que têm uma distribui-ção de grau homogênea, resultando, nesse caso, na ausência de vértices dominantes.

Ademais, algumas redes complexas, ou modelagens de sistemas e dados como re-des, apresentam comunidades (Danon et al., 2007). Tais comunidades podem ser defini-das como grupos de vértices da rede densamente conectados, enquanto que as cone-xões entre vértices de grupos diferentes são esparsas (Newman e Girvan, 2004), con-forme pode ser observado na Figura 1.1. Pela figura, é de fácil percepção que existeminúmeras conexões entre vértices da mesma comunidade e uma quantidade escassa domesmo entre comunidades distintas. As comunidades representam padrões de intera-ção entre os vértices de uma rede e sua identificação é importante para o entendimentodos mecanismos de crescimento e formação da rede (Clauset, 2005).

Figura 1.1: Exemplo de rede com estrutura de comunidades retirado de uma rede de proteínas.As cores representam as comunidades. Figura extraída de (Girvan e Newman, 2002)

Recentemente, muitas técnicas para a detecção de comunidades têm sido desen-volvidas (Boccaletti et al., 2007; Danon et al., 2007; Newman e Girvan, 2004; Reichardte Bornholdt, 2004; Zhou, 2003b). As técnicas de detecção de comunidades em redescomplexas podem ser diretamente empregadas para se realizar o aprendizado não su-pervisionado de agrupamento de dados (Cook e Holder, 2000; Karypis et al., 1999;Quiles et al., 2008; Schaeffer, 2007). Para tanto, o conjunto de dados deve ser trans-formado em uma rede. Este processo pode ser realizado tomando cada item de dadocomo um vértice de uma rede. As ligações entre os vértices definem as similaridadesentre os dados. Assim, dados com maiores similaridades estarão mais conectados en-

- 5

tre si e pouco ligados a outros dados com menores similaridades. Logo, a aplicação detécnicas de detecção de comunidades na rede permite evidenciar os grupos de vérticesfortemente ligados, ou seja, as comunidades. Em suma, uma tarefa de agrupamento dedados se transforma em uma tarefa de detecção de comunidades, tão logo que a redeseja construída a partir do conjunto de dados. Além disso, essa abordagem apresentainteressantes vantagens em relação a outras abordagens de agrupamento de dados,como a capacidade de detecção de clusters de formas variadas e a representação hie-rárquica dos dados, como, por exemplo, na forma de dendogramas (Duda et al., 2000;Jain et al., 1999).

1.1 Objetivos e Motivações

Este projeto de pesquisa traz como objetivo geral o desenvolvimento e fundamen-tação teórico-matemática de uma nova técnica de aprendizado semissupervisionadopara a análise de dados baseada em redes complexas. A hipótese assumida é da exis-tência de tal modelo matemático que represente o comportamento de competição departículas. Os objetivos específicos são listados abaixo.

1. Proposição e desenvolvimento de uma nova técnica de aprendizado semissuper-visionado baseada em competição de partículas em redes complexas. Neste caso,alguns vértices da rede são rotulados, ou seja, suas classes (grupos) são previa-mente definidas. O modelo a ser desenvolvido deverá ser capaz de propagar osrótulos para os outros vértices da rede via competição e cooperação de partícu-las, de forma eficiente em relação aos algoritmos já produzidos na literatura. Ummecanismo de cooperação entre as partículas será desenvolvido, de forma quepartículas do mesmo time propaguem o mesmo tipo de rótulo (classe). Espera-se que a proposição desse modelo dinâmico competitivo trará uma contribuiçãopara o campo de múltiplas caminhadas aleatórias com interação, cuja modela-gem e estudo inexistem na literatura.

2. A partir do modelo semissupervisionado desenvolvido na etapa anterior, seráconduzida uma análise matemática do modelo, a fim de descrever o compor-tamento empírico do mesmo por meio de equações probabilísticas. É esperadotambém que uma validação seja realizada, com o propósito de constatar se omodelo matemático realmente se assemelha com o comportamento empírico domodelo competitivo.

3. O modelo semissupervisionado será estendido ao modo de aprendizado não su-pervisionado. Neste caso, espera-se que o modelo possa realizar tarefas de detec-ção de comunidades e agrupamento de dados. Para o caso de tarefas de detecção


de comunidades, serão utilizados benchmarks bem conhecidos (Danon et al., 2005;Fortunato, 2010) e redes reais para verificar a qualidade do modelo. Quanto àstarefas de agrupamento de dados, serão utilizadas algumas bases de dados forne-cidas pelo repositório UCI (Frank e Asuncion, 2010) e pela base de dados MNISTde dígitos manuscritos (LeCun et al., 1998). Por último, a partir da própria infor-mação gerada pelo modelo competitivo, será proposta uma medida para estima-ção do número de clusters em uma base de dados.

4. A partir do modelo de competição de partículas proposto, será estudada e de-senvolvida uma nova medida para detecção de vértices sobrepostos (overlappingvertices). Para validar a medida proposta, simulações com bases de dados co-nhecidas na literatura serão conduzidas, tais como a rede de karatê de Zachary(Zachary’s karate club network) (Zachary, 1977), rede social de golfinhos (dolphin so-cial network) (Lusseau, 2003), rede da novela Les Misérables (Les Misérables network)(Knuth, 1993), rede representando uma liga de futebol americano (American col-lege football network) (Girvan e Newman, 2002) e rede de colaboração científica(scientific collaboration network) (Newman, 2006).

5. Na última fase, será tratado do assunto de confiabilidade na classificação dosdados no aprendizado semissupervisionado. Especificamente, espera-se que atécnica a ser desenvolvida seja capaz de: (i) oferecer nível de pertinência de cadaitem de dado a cada classe (soft-label), ao invés de só oferecer rótulo de classe(hard-label); e (ii) detectar outliers e, consequentemente, impedir a sua propaga-ção. Por fim, serão conduzidos estudos e análises de propagação de erros (dadoserroneamente rotulados) junto à propagação de rótulos em redes, ou seja, certapercentagem de erros será introduzida antes do processo de propagação de ró-tulos. Pretende-se identificar, com isso, o ponto crítico de porcentagem de er-ros introduzidos que leva a uma precisão de classificação drasticamente decaída.Esse tipo de estudo é muito importante não só para obter uma classificação pre-cisa, mas também para obter um melhor entendimento do conjunto de dados emprocessamento.

As motivações vêm do fato de que as redes complexas são ferramentas podero-sas para muitas disciplinas da ciência, inclusive para a modelagem e a aplicação deaprendizado de máquina em análise de dados. Em razão da alta complexidade e daversatilidade dessa aproximação, ainda existe um grande espaço para exploração.

Outra motivação embasa-se no argumento que o processo de competição de partí-culas é muito similar a diversos processos sociais e naturais, quais sejam: competiçãoentre animais, exploração territorial por humanos (animais), campanhas eleitorais, en-tre outros. Ademais, a movimentação aleatório-preferencial incorporada na política de

1.1 - Objetivos e Motivações 7

movimentação das partículas pode, de forma substancial, melhorar a taxa de classi-ficação, como será visto no capítulo de resultados obtidos. Este modelo corrobora aimportância do papel da aleatoriedade em sistemas evolucionários, cuja função prin-cipal é de evitar, de forma automática, que as partículas caiam em armadilhas locais,além de proporcionar, para as partículas, a habilidade de explorar territórios desco-nhecidos. Logo, uma certa quantidade de aleatoriedade é essencial para o processode aprendizado. Tal aleatoriedade é incumbida de representar o estado “Não sei” epresta-se como um eficiente “explorador de novas características”.

O modelo de competição de partículas foi originalmente proposto em Quiles et al.(2008) no campo de aprendizado não supervisionado, em que apenas um procedi-mento de competição de partículas foi introduzido, sem nenhuma definição formal.Tal técnica mostra pelo menos duas vantagens salientes, em cotejo entre muitas outrastécnicas de detecção de comunidades atuais (Boccaletti et al., 2007; Danon et al., 2007;Newman e Girvan, 2004; Reichardt e Bornholdt, 2004; Zhou, 2003b): (i) o mecanismode competição de partículas não só oferece uma técnica de detecção de comunidades,mas também apresenta um esquema geral de aprendizado de máquina competitivo;e (ii) a técnica apresenta alta precisão de detecção e, ao mesmo tempo, baixa ordemde complexidade computacional. No trabalho presente, uma definição rigorosa seráfornecida, na qual a competição de partículas é formalmente modelada a partir de umsistema dinâmico estocástico. Tal modelo é, ao contrário do originalmente proposto emQuiles et al. (2008), utilizado em classificação semissupervisionada, i.e., no campo deaprendizado semissupervisionado. Além disso, um mecanismo de cooperação entreas partículas será introduzido. Tendo em vista que o modelo de várias partículas quese interagem corresponde a muitos sistemas naturais e artificiais, o estudo deste tó-pico configura-se como uma importante tarefa. Em virtude da ausência de teoria paratais modelos, este trabalho (a definição do modelo per se) é um importante passo paracompreender e dominar tais sistemas. Adicionalmente, o mecanismo de cooperaçãoentre partículas permite que partículas do mesmo time propaguem o mesmo tipo derótulo e, ao mesmo tempo, times distintos compitam uns contra os outros para definiras bordas das classes. Outra característica saliente do modelo é a propagação local dosrótulos, i.e., em decorrência do processo competitivo, cada partícula apenas visita umaporção de vértices potencialmente pertencente àquela partícula ou ao seu time. Estacaracterística pode ser entendida como um efeito “dividir para conquistar” embutidono próprio esquema competitivo-cooperativo. Em função disto, muitas caminhadaslongas e redundantes realizadas pelas partículas são evitadas. Como resultado, o al-goritmo apresenta complexidade temporal baixa. Outra particularidade importante éque a rede subjacente é construída diretamente do conjunto de dados de entrada; por-tanto, a correspondência entre os dados de entrada e o resultado de processamento (arede final) é mantida. Como consequência disso, o efeito “caixa-preta”, o qual existe,


por exemplo, em muitos sistemas competitivos neurais, é significativamente reduzido.As técnicas tradicionais de aprendizado semissupervisionado baseadas em grafo

envolvem minimização de uma função de custo e multiplicação de matrizes. Destaforma, a complexidade computacional dessas técnicas é geralmente da ordem O(V3)

ou superiores (Belkin e Niyogi, 2003; Belkin et al., 2004; Zhou et al., 2003), onde V éo número de vértices. Espera-se que os modelos gerados baseados em competiçãode partículas sejam mais eficientes, o que é importante para tratar grandes bases dedados. Portanto, a técnica a ser proposta deve tentar suprir essa lacuna, no que tangeà complexidade computacional.

Quanto à detecção de vértices e comunidades sobrepostos, deve ser exaltado quea maioria dos métodos de detecção de comunidades propostos na literatura objetivadesignar um vértice a apenas um grupo (classe) (Danon et al., 2005; Fortunato, 2010).Entretanto, em redes reais, os vértices normalmente são compartilhados entre gruposdiferentes (Fortunato, 2010). Por exemplo, em uma rede de associação semântica deconceitos (Kiss et al., 1973), o conceito “Brilhante” pode ser um membro de vários gru-pos, tais como o grupo representando os conceitos relativos à “Luz”, à “Astronomia”,à “Cor”, e assim sucessivamente (Palla et al., 2005). Em uma rede social, cada pessoanaturalmente pertence ao grupo da empresa em que trabalha e também ao grupo re-presentando os membros de sua família. Diante desse cenário, a descoberta de vérticessobrepostos é importante não só para mineração de dados, mas também para a análisedos dados em geral.

Em aprendizado semissupervisionado, o problema de confiabilidade pode serainda mais crítico, pois uma pequena quantidade de erros pode se espalhar desde umpequeno subconjunto até o conjunto inteiro de dados. Por exemplo, em um diagnós-tico médico, em virtude da quantidade de trabalho e da complexidade do problema,pode acontecer que somente uma pequena percentagem de sintomas é classificada (ro-tulada) por determinado especialista humano. A técnica de aprendizado semissuper-visionado deve propagar esses rótulos de classes para sintomas (itens de dados) nãorotulados. Neste processo, o erro em rotulação de poucos sintomas pode contaminaruma percentagem razoável de sintomas não rotulados, causando diagnósticos errados.Portanto, a confiabilidade de resultados do aprendizado semissupervisionado, apesarde pouco estudada, é crucial em muitos sistemas de classificação. Por isso, este projetode pesquisa tem a expressa preocupação de tratar do assunto referente à confiabilidadedos dados no contexto de aprendizado semissupervisionado.

1.2 Organização do Documento

Este documento foi organizado da seguinte forma: nos Capítulos 2 e 3, serão for-necidos uma revisão bibliográfica pertinente ao projeto de pesquisa proposto: Redes

1.2 - Organização do Documento 9

Complexas e Aprendizado Semissupervisionado, respectivamente. No capítulo 4, osresultados obtidos são apresentados minuciosamente. Por fim, no capítulo 5, é apre-sentado o plano de pesquisa deste projeto.


CAPÍTULO

2Redes Complexas

Neste capítulo, será apresentada toda fundamentação teórica relevante ao plano depesquisa desse projeto concernente à área de Redes Complexas. Aqui serão ilustradosa trajetória de evolução desse sub-ramo de pesquisa da área de Inteligência Artificial,as suas principais técnicas de formação de rede, bem como os conceitos e métodos dedetecção de comunidades.

2.1 Evolução Histórica

O estudo de redes teve início a partir do desenvolvimento da teoria dos grafos,inaugurada por Leonhard Euler em 1736 com a solução do problema das sete pon-tes de Königsberg, hoje, Kaliningrado, Rússia. O problema, bem discutido na época,registrava que existiam sete pontes que atravessavam o rio Pregel, com duas ilhas in-termediárias, com as quais os moradores desejavam saber se era possível atravessartodas essas sete pontes, sem repetição, e regressar ao ponto de partida. Euler demons-trou para a Academia de Ciências Russa de São Petersburgo, analiticamente, que nãoera possível completar tal caminhada, com auxílio de uma representação gráfica cons-tituída de pontos e curvas interligando estes pontos. Era o início da representação for-mal e gráfica de uma rede ou grafo, até hoje conhecido, com vértices e arestas. A partirdesse momento, vários pesquisadores começaram a estudar esse ramo de pesquisa embusca de novos teoremas e aplicações (Newman, 2003).

De fato, o primeiro grande passo para o estudo de Redes Complexas foi impulsio-nado por Paul Erdös e Alfréd Réyni que analisaram um certo tipo de rede, denominadade redes aleatórias, ou redes randômicas, em seu trabalho publicado em 1959, abrindo

11

12 Capítulo 2 - Redes Complexas

portas para uma área de estudos: a teoria de redes aleatórias, que representa uma mis-tura de teoria dos grafos e teoria da probabilidade (Erdös e Rényi, 1959).

Seguindo a cronologia, em 1967, Stanley Milgram resolveu aceitar o desafio pro-posto por Frigyes Karinthy, inspirado pelas conjecturas de Guglielmo Marconi em1909, o qual desafiava alguém encontrar outra pessoa a qual não poderia ser conec-tada por meio de, no máximo, 5 pessoas intermediárias (Milgram, 1967). Estava lan-çado o conceito denominado de separação em seis graus, que constituiu a sementepara o estudo de redes de pequeno mundo. Para solucionar tal desafio, Milgram con-duziu experimentos no intuito de tentar descobrir a probabilidade de duas pessoasquaisquer se conhecerem. Para tanto, foram enviadas cartas para pessoas aleatóriasresidentes em regiões pré-determinadas dos Estados Unidos, cujo conteúdo versavasobre informações de outra pessoa qualquer. Caso a pessoa referida na carta fosse co-nhecida pelo leitor, então este remetia a carta para o destinatário. Por outro lado, casonão a conhecesse, então deveria enviar para alguma outra pessoa conhecida. No fimdo experimento, Milgram constatou que a média de encaminhamentos de uma pessoapara outra atingia 5, 5 pessoas. Estava, portanto, descoberta a propriedade de pequenomundo, em termos empíricos, que afirma que mesmo que existam milhões de vérti-ces interconectados em uma rede social, a distância média entre eles não passa de umpequeno valor, no caso do exemplo, 5, 5 pessoas (Milgram, 1967).

Apesar das conclusões de Milgram, foi somente no final da década de 90 que aspesquisas foram retomadas nesta área. Em 1998, Watts e Strogatz descobriram que amédia de caminhos mais curtos em uma rede pode ser drasticamente reduzida poruma alteração aleatória de poucas ligações, partindo-se de uma rede regular (Watts eStrogatz, 1998). Esta rede resultante é chamada de Rede de Pequeno Mundo (Small-World Network), já empiricamente descoberta por Milgram. Em 1999, Barabási e Albertdescobriram que muitas redes reais têm uma distribuição de grau dos vértices queobedece a lei de potência: P(k) ∼ k−γ, na qual k é o número de ligações de um vérticeescolhido aleatoriamente e γ é o expoente de escala (Barabasi e Albert, 1999). Essadistribuição heterogênea modela a existência de um pequeno grupo de vértices quepossuem um grande número de ligações. Tais redes são denominadas Redes Livre deEscala (Scale-free Networks).

Impulsionada pelo avanço tecnológico computacional e as crescentes proporçõesde dados a serem analisados, as redes complexas têm emergido como um tópico unifi-cador em sistemas complexos e estão presentes em vários ramos da ciência (Bornholdte Schuster, 2003). Estruturalmente, as redes complexas são representadas por um grafode grande escala G = 〈V , E〉, onde V representa o conjunto de vértices e E , o conjuntode arestas. Segundo Albert et al. (2004), as redes complexas são modelos para sistemasem geral, em virtude de possuírem uma topologia não trivial, além de serem com-postas por uma grande quantidade de vértices. Dentre alguns exemplos plausíveis de

2.1 - Evolução Histórica 13

representação em rede, incluem-se: a Internet (Faloutsos et al., 1999), a World Wide Web(Albert et al., 1999), redes neurais biológicas (Sporns, 2002), redes sociais entre indiví-duos (Scott, 2000) e entre companhias e organizações (Mizruchi, 1982), cadeias alimen-tares (Montoya e Solé, 2002), redes do metabolismo (Jeong et al., 2000) e de distribuiçãocomo a corrente sanguínea (West et al., 1999), rotas de entrega postal e de distribuiçãode energia elétrica (Albert et al., 2004), etc. De acordo com (Strogatz, 2001), algumas ca-racterísticas inerentes a esse tipo de rede são: a complexidade estrutural - que se traduzna dificuldade de visualização da rede; a evolução - que marca a constante alteraçãona estrutura da rede devido à inclusão e à remoção de vértices e conexões (Dorogovt-sev e Mendes, 2003); a diversidade de conexões - pois estas ligações entre os vérticespodem apresentar muitas variações em suas características, tais como a capacidade, ocomprimento, a largura e o sentido; e a dinâmica e a estrutura complexas - as quaisinfluem em grande escala nos estados de uma rede, já que podem ser entendidas comoo tráfego de informações (Zhao et al., 2007), as ocorrências de falhas de comunicação(Zhao et al., 2004, 2005, 2007), as relações de similaridade entre vértices, a distribuiçãode funções (Newman, 2003), entre outras.

2.2 Modelos de Formação de Rede

Com a expectativa de estudar propriedades topológicas que estão presentes emredes reais, diversos modelos de redes foram propostos. Alguns desses modelos, in-clusive, ensejam um estudo aprofundado devido às suas características de grande inte-resse. Como exemplo de categorias de redes importantes, podem ser elencadas: redesrandômicas, o modelo de pequeno mundo, as redes aleatórias clusterizadas e as redesde Barabási-Albert, mais conhecidas como redes livres de escala (Costa et al., 2007).Nas próximas subseções, serão revisados os principais modelos de rede conhecidos naliteratura.

2.2.1 Redes Randômicas

A rede desenvolvida por Erdös e Rényi pode ser considerada o modelo mais fun-damental das redes complexas. No seu artigo de 1959 (Erdös e Rényi, 1959), Erdöse Rényi apresentaram um modelo gerador de redes aleatórias consistindo de N vér-tices e M arestas. Iniciando de N vértices completamente desconectados (nenhumaaresta na rede), a rede é construída a partir da adição de L arestas aleatoriamente, sem-pre evitando conexões múltiplas ou autoconexões (determinado vértice i ligar com elemesmo). Outro modelo similar define N vértices e uma probabilidade p de conectarcada par de vértices. O último modelo é amplamente reconhecido como o modelo deErdös e Rényi. A Figura 2.1a mostra um exemplo que goza dessa propriedade de rede


randômica.

Figura 2.1: Um exemplo de rede aleatória de Erdös e Rényi. (a) uma rede construída por meioda abordagem randômica proposta por Erdös e Rényi; (b) o gráfico da média de distribuição degrau de uma rede apresentando N = 10000 e p = 0.2. Figura integralmente extraída de Costaet al. (2007).

Uma vez que, para cada vértice i da rede (de um total de N), existem N − 1 possi-bilidades de conexão, segue que a cardinalidade do espaço amostral, que representa atotalidade de opções em uma rede que uma aresta pode existir, é dada por:

|Ω| = N(N − 1)2

, (2.1)

sendo que a divisão por dois decorre do fato que as arestas aqui tomadas não sãodirecionadas, isto é, se existe uma aresta que origina de vi e termina em vj, então, porconsequência, existe uma aresta que origina de vj e termina em vi. Em termos gerais, apresença dessas duas arestas representa a ocorrência do mesmo evento probabilístico.Tendo como base quen para cada aresta que esteja inclusa no espaço amostral Ω, existea probabilidade p dela ocorrer e 1− p, caso contrário, e sabendo que há (N−1

k ) formasde escolher k vértices entre N − 1 no total, e pk é a probabilidade deles terem k arestas,então (N−1

k )pk representa a probabilidade de um vértice da rede possuir arestas parak outros vértices. Entretanto, deve-se impor no modelo que não exista mais nenhumaaresta, além dessas k, ou seja, para a quantidade de vértices restantes, dada por N −1 − k, deva ocorrer o evento complementar de existir arestas, isto é, (1 − p)(N−1−k).Portanto, a distribuição de grau segue uma Binomial(N − 1, p), cuja equação é regidapela seguinte expressão:

P(grau(k)) =(

N − 1k

)pk(1− p)(N−1)−k. (2.2)

Dado que N → ∞ e p sejam suficiente pequenos, é possível mostrar que uma

2.2 - Modelos de Formação de Rede 15

Binomial(N− 1, p) aproxima-se da distribuição de Poisson(λ) (Meyn e Tweedie, 2009),com a seguinte expressão de relacionamento:

(N − 1)p = λ. (2.3)

Retomando da teoria de probabilidade que a média e variância de uma distribuiçãode Poisson(λ) são dadas simplesmente por µ = σ2 = λ, nota-se, a partir da observaçãoda rede na Figura 2.1b, a qual é construída a partir dos parâmetros N = 10000 e p = 0.2,que a distribuição realmente é de Poisson com média (pico) próxima de λ = (N −1)p = (10000− 1)0.2 ≈ 2000.

Ademais, a média do menor caminho 〈l〉 é pequena nessas redes, aumentando deforma proporcional ao logaritmo do tamanho da rede, isto é, 〈l〉 ∼ ln(N)

ln(〈k〉) , sendo 〈k〉dado pela média da distribuição de Poisson (média do grau), ou seja, 〈k〉 = λ = (N −1)p, sempre que N → ∞ e p sejam suficiente pequenos (Costa et al., 2007).

A maior descoberta de Erdös e Rényi foi que muitas propriedades importantesde uma rede randômica aparecem conforme se incrementam os hiperparâmetros daBinomial(N − 1, p), de forma que, por exemplo, para uma determinada probabilidadecrítica p, a maioria das redes apresentam alguma propriedade específica Q, tal comoapresentar apenas um componente. Para valores superiores a essa probabilidade crí-tica, a rede não mais apresenta um único componente, mas sim vários sub-grafos des-conexos (Newman, 2003).

2.2.2 Redes de Pequeno Mundo

Muitas redes do mundo real exibem a propriedade de mundo pequeno, isto é, amaioria dos vértices pode ser atingido por quaisquer outros, por meio de um pequenonúmero de arestas. Esta característica é encontrada, por exemplo, em redes sociais,onde praticamente todas as pessoas do mundo podem ser alcançadas por uma pe-quena cadeia de pessoas (Watts, 2003; Watts e Strogatz, 1998).

De forma a construir uma rede que goze da propriedade de pequeno mundo, pode-se utilizar um processo de formação de rede da seguinte forma: a rede é inicialmenteregular, composta de N vértices, tal como mostra a Figura 2.2, na qual cada vérticeconecta-se com os seus k vizinhos mais próximos em cada direção, totalizando 2k co-nexões. Em seguida, cada aresta é aleatoriamente remanejada, isto é, dado um vérticei qualquer da rede, toma-se uma aresta genérica ligando os vértices i e j e troca-se ovértice-destino ao qual aquela aresta ligava, ou seja, substitui-se j por um outro vérticek qualquer, tal que j 6= k, com uma probabilidade p. Quando p = 0, não haverá rema-nejamentos e, portanto, a rede continuará sendo regular, enquanto que, para o caso emque p tende ao valor máximo 1, o remanejamento se torna constante e é muito provávelque todas as arestas troquem de vértice-destino (Watts e Strogatz, 1998). A Figura 2.3


traz um esquemático do comportamento do parâmetro p, responsável pela frequênciade remanejamento das arestas. Perceba que para valores de p pequenos, tem-se redesefetivamente regulares. Conforme p aumenta, a propriedade de pequeno mundo setorna evidente. Quando p = 1, a rede se torna randômica. O pico da distribuição degrau, seguindo esta abordagem de construção, se localiza próximo do valor 2k (Watts,2003; Watts e Strogatz, 1998).

Figura 2.2: Método de construção de uma rede de pequeno mundo, de acordo com o propostopor Watts e Strogatz em (Watts e Strogatz, 1998). Figura extraída de Costa et al. (2007).

Figura 2.3: Comportamento da rede com a mudança do parâmetro responsável pela frequênciade remanejamento das arestas.

A implicação imediata para redes que apresentem a propriedade de pequenomundo é que o transporte de qualquer informação, posto que ela foi gerada em qual-quer vértice da rede, é muito rápido. Por exemplo, no contágio viral: dado que umapessoa contraiu algum vírus, o qual esteja vivendo em um ambiente propício para suamultiplicação e disseminação, então, espera-se que, em pouco tempo, várias pessoasestejam contagiadas por este vírus.


2.2.3 Redes Livre de Escala

Em um estudo proposto por Barabási e Albert, eles notaram que algumas redespossuem um pequeno número de vértices com graus elevados, enquanto que a maio-ria possui graus muito reduzidos (Barabasi e Albert, 1999). Com esta observação emmente, em 1999, eles propuseram as redes livre de escala, na qual a distribuição degrau obedece a lei de potência (power-law) dada por:

P(k) ∼ k−γ, (2.4)

onde γ representa um expoente de escala. Analiticamente, pode ser mostrado que omodelo de construção que será estudado abaixo evolui para um estado de escala inva-riante, o qual segue uma a lei de potência com expoente γ = 3, independentemente doconjunto inicial de vértices (Barabasi e Albert, 1999). Perceba que, fixando γ, conformeo grau k aumenta, o número de vértices que possui grau k diminui. Assim, espera-se que P(k) tenha um alto valor para baixos valores de k e um baixo valor para altosvalores de k, o que condiz com a observação encontrada por Barabási e Albert.

O modelo de rede de Barabási e Albert baseia-se em duas regras fundamentais: ocrescimento e a ligação preferencial. A rede é gerada a partir de um conjunto m0 de vér-tices. Em seguida, a cada passo da construção, a rede cresce por meio da adição denovos vértices. Para cada novo vértice agregado, m novas arestas são inseridas entreo novo vértice e alguns vértices anteriores aleatoriamente escolhidos. Os vértices querecebem essas novas arestas são escolhidos segundo uma regra de ligação preferenciallinear, isto é, a probabilidade de um novo vértice i se conectar com um vértice j exis-tente é proporcional ao grau do vértice j. Em termos matemáticos, se ki denotar o graudo vértice i, então esta característica pode ser precisamente indicada por:

P(i→ j) =k j

∑u ku. (2.5)

Portanto, os vértices mais conectados possuem maior probabilidade de receber aligação de novos vértices. Barabasi e Albert (1999) argumentaram que a natureza dasredes livre de escala estava associada a dois mecanismos básicos, compartilhados pordiversos tipos de redes reais. Os modelos anteriores consideravam um conjunto inicialde vértices fixo, dado por N, e apenas o conjunto de arestas era modificado conformeavançavam-se nos passos do algoritmo de formação de rede. A maioria das redes reais,no entanto, representa sistemas que crescem pela adição contínua de vértices, que écaracterístico de redes complexas, devido à sua dinamicidade. Partindo de um núcleopequeno de vértices, o número de vértices total aumenta durante a vida útil da rede,por meio de subsequentes adições de vértices. Um exemplo clássico é a World WideWeb, cujo crescimento é exponencial em relação ao tempo, tendo em vista que a adição


de novas páginas ocorre a praticamente todo momento. Outro ponto que difere dasabordagens anteriores é que os modelos vistos assumem que a probabilidade de doisvértices serem conectados independe do grau dos vértices, ou seja, é feita de formauniformemente aleatória. A maioria das redes reais, todavia, exibe a propriedade deligação preferencial, na qual a existência de uma aresta depende diretamente do graudo vértice em questão. Retomando o exemplo da World Wide Web, fica evidente queé muito mais provável haver uma ligação de uma nova página a outra que seja maisreferenciada em relação àquelas já existentes na rede (Barabasi e Albert, 1999). A Figura2.4a ilustra um exemplo de rede livre de escala. Perceba que, com o auxílio da Figura2.4b, constata-se um número reduzido de vértices com grau alto (evidenciado comcores na rede em Figura 2.4a), enquanto que existem muitos vértices com grau baixo,o que mostra a tendência de novos vértices de se conectarem a vértices com graus jáelevados.

Figura 2.4: (a) Ilustração de uma rede livre de escala; (b) Gráfico da distribuição de grau emfunção do grau k. Figura modificada a partir da proposta em Barabasi e Albert (1999).

2.2.4 Redes Aleatórias Clusterizadas

Algumas redes reais, tais como sociais e biológicas, apresentam estruturas modula-res (Girvan e Newman, 2002). Essas redes são constituídas de conjuntos ou comunida-des de vértices, com a característica de que vértices pertencentes a mesma comunidadepossuem muitas arestas os interligando e, ao mesmo tempo, vértices de comunidadesdistintas possuem poucas arestas ligando uma comunidade com a outra. Um modelopara gerar tais comunidades foi proposto por Girvan e Newman (2002). Inicialmente,um conjunto de N vértices é disposto em M comunidades distintas, sem sobreposição.


Em seguida, dois vértices são selecionados e conectados com probabilidade pin, se elespertencerem a mesma comunidade, ou pout, se eles forem oriundos de comunidadesdistintas. Os valores de pin e pout devem ser escolhidos de acordo com quão definidasas comunidades devem ser. Um valor alto de pin remete a uma rede com comunidadesbem definidas, enquanto que valores baixos tornam a propriedade de comunidades narede pouco visível. Em termos empíricos, pout pin para haver comunidades bemdefinidas na rede. A Figura 2.5 ilustra uma rede com quatro comunidades bem defini-das. Atente às comunidades na figura as quais apresentam-se de forma bem definida,já que o número de arestas ligando vértices da mesma comunidade é muito maiorque a quantidade de arestas ligando vértices de comunidades distintas. Diante dessasquantidades, também definem-se o número de arestas intracomunidades e intercomu-nidades zin e zout, respectivamente, para uma rede arbitrária de grau médio 〈k〉. Combase nisso, pode-se definir a fração de arestas intracomunidades zin/〈k〉 e, da mesmaforma, a fração de arestas intercomunidades zout/〈k〉. A quantidade zout/〈k〉 quantifica amistura entre as comunidades, i.e., conforme zout/〈k〉 aumenta, as comunidades ficammais difíceis de serem visualizadas. Estas quantidades são bastante utilizadas no ben-chmark proposto em Danon et al. (2005), o qual será utilizado neste projeto em capítulosposteriores.

Figura 2.5: Esquemático de uma rede aleatória clusterizada. As comunidades são representa-das pelas cores. Figura integralmente retirada de Papadopoulos et al. (2009).


2.3 Detecção de Comunidades

Nesta seção, será dada uma visão geral sobre os conceitos e técnicas de detecção decomunidades. Especificamente, especial atenção será importada à técnica proposta emQuiles et al. (2008), uma vez que o plano de pesquisa relaciona-se com esta técnica.

2.3.1 Conceitos Relevantes

A ciência moderna em redes trouxe um avanço substancial para o entendimento deredes complexas. Uma das características evidentes e de destaque em redes complexasé a presença de comunidades. A noção de comunidade em redes é direta: cada comuni-dade é definida como um sub-grafo cujos vértices estão densamente interconectados,e, ao mesmo tempo, tais vértices possuem poucas ligações com o restante da rede. Adetecção de comunidades em redes complexas tornou-se um importante tópico em mi-neração em grafos e dados (Danon et al., 2005; Fortunato, 2010; Newman, 2004a). Nateoria dos grafos, a detecção de comunidades corresponde ao problema de partição degrafos, o qual já foi mostrado ser um problema NP-completo (Fortunato, 2010).

Outro conceito importante é de comunidades e vértices sobrepostos (Fortunato,2010). Tais vértices são definidos como membros de mais de uma comunidade ouclasse ao mesmo tempo (Palla et al., 2005). Por exemplo, em uma rede de associação se-mântica de conceitos (Kiss et al., 1973), o conceito “Brilhante” pode ser um membro devários grupos, tais como o grupo representando os conceitos relativos à “Luz”, à “As-tronomia”, à “Cor”, e assim sucessivamente (Palla et al., 2005). Em uma rede social,cada pessoa naturalmente pertence ao grupo da empresa em que trabalha e tambémao grupo representando os membros de sua família. Diante desse cenário, a descobertade vértices e comunidades sobrepostos é importante não só para mineração de dados,mas também para a análise dos dados em geral.

2.3.2 Trabalhos Relevantes

Tendo em vista que o problema de detecção de comunidades de forma exata éNP-completo, muitos esforços estão sendo gastos para desenvolver soluções aproxi-madas e eficientes, tais como métodos espectrais (Newman, 2006), a técnica baseadana medida “betweenness” (Newman, 2004a), otimização da modularidade (Newman,2004b), detecção de comunidades baseada no modelo de Potts (Reichardt e Bornholdt,2004), sincronização (Arenas et al., 2006), teoria da informação (Fortunato et al., 2004) ecaminhadas aleatórias (Zhou, 2003a). Fortunato (2010) apresenta uma recente revisãoneste tópico.

Quanto às técnicas de detecção de vértices e comunidades sobrepostos, vários mé-todos foram propostos na literatura (Evans e Lambiotte, 2009; Lancichinetti et al., 2009;

2.3 - Detecção de Comunidades 21

Nicosia et al., 2009; Palla et al., 2005; Shen et al., 2009; Sun et al., 2011; Zhang et al., 2007).Em Zhang et al. (2007), os autores combinam a ideia da função de modularidade Q, re-laxação espectral e agrupamento por meio de fuzzy c-means com o intuito de construiruma nova função de modularidade baseada na função generalizada Q de Newman eGirvan. Em Palla et al. (2005), as estruturas de comunidades são descobertas por meiode percolações em cliques de k vértices, enquanto que as sobreposições em comuni-dades são garantidas pelo fato que um vértice pode participar de mais de um cliqueao mesmo tempo. Entretanto, o método por cliques de tamanho k traz alguns efei-tos indesejáveis, e.g., alguns vértices podem não pertencer a nenhuma comunidade narede. Além disso, a estrutura hierárquica pode não ser revelada, dependendo da es-colha do parâmetro k. Em Lancichinetti et al. (2009), é apresentado um algoritmo queencontra tanto comunidades sobrepostas, quanto a estrutura hierárquica das partiçõesem comunidades, por intermédio de uma função de otimização e um parâmetro deresolução fornecidos pelo usuário. Recentemente, Evans e Lambiotte (2009) propuse-ram um método para reconhecer estrutura de comunidades sobrepostas por meio dapartição de um grafo em sub-grafos menores. Um ponto negativo da maioria dessastécnicas é que a detecção de comunidades e vértices sobrepostos é realizada como umprocesso dedicado, ou seja, separado do processo de detecção de comunidades. Destaforma, um processamento computacional adicional é necessário.

2.3.3 Competição de Partículas para Detecção de Comunidades

A técnica proposta por Quiles et al. (2008) será estudada em detalhes nesta seção,uma vez que ela se assemelha muito ao principal tópico de pesquisa desse documento.Em termos gerais, tal técnica se baseia em competição de partículas. Essas partícu-las navegam na rede com o propósito de conquistar novos vértices, enquanto que,também, tentam defender seus vértices previamente conquistados. O modelo foi ori-ginalmente proposto para detecção de comunidades em redes complexas e, portanto,figura-se como uma técnica pertencente ao aprendizado não supervisionado.

Um partícula, denotada por ρj, é matematicamente expressa por duas variáveis es-calares: (i) ρv

j (t), a qual representa o vértice vi visitado pela partícula ρj no instante t; e(ii) ρω

j (t) ∈ [ωmin, ωmax], a qual indica o potencial de exploração da partícula no tempot. A dinâmica que rege a movimentação e atualização da capacidade de exploração daspartículas é dada por:

ρvj (t + 1) = vi (2.6)


ρωj (t + 1) =

ρω

j (t) se vρi (t) = 0

ρωj (t) + (ωmax − ρω

j (t))∆ρ se vρi (t) = ρj 6= 0

ρωj (t)− (ρω

j (t)−ωmin)∆ρ se vρi (t) 6= ρj 6= 0

(2.7)

onde ∆ρ controla a variação do nível de exploração ou potencial que cada partículaperde ou ganha, dependendo da natureza do vértice que visita. Especificamente, casovisite um vértice dominado pela partícula visitante, o nível de exploração daquela par-tícula é aumentado, caso contrário, decrementado.

Cada vértice vi da rede é representado por meio de três variáveis escalares: (i) vρi (t),

a qual define a partícula proprietária do vértice vi no instante t; (ii) vωi (t) indica o nível

de dominação imposto pela partícula ρj ao vértice vi no instante t; e (iii) vγi simboliza

se o vértice vi está sendo visitado por alguma partícula no instante t. Com o auxíliodessas variáveis, a dinâmica dos vértices é regida pelo seguinte conjunto de equações:

vρi (t + 1) =

vρ

i (t) se vγi (t) = 0

ρj se vγi (t) = 1 e vω

i (t) = ωmin(2.8)

vωi (t + 1) =

vω

i (t) se vγi (t) = 0

maxωmin, vωi (t)− ∆v se vγ

i (t) = 1 e vρi (t) 6= ρj

ρωj (t + 1) se vγ

i (t) = 1 e vρi (t) = ρj

(2.9)

onde ∆v denota a fração de nível de exploração perdida por um vértice, caso umapartícula rival venha a visitá-lo. O algoritmo de detecção de comunidades inicia in-serindo K partículas em K vértices escolhidos aleatoriamente. No início do processodinâmico, cada partícula ρj e cada vértice vi possuem potencial igual a ρω

j (0) = ωmin

e vωi (t) = ωmin, respectivamente. Além disso, cade vértice não é dominado por ne-

nhuma partícula, i.e., ela está no estado livre, o qual é matematicamente modelado porvρ

i (0) = 0. A cada iteração, cada partícula escolhe um vértice para visitar, segundouma política de movimentação aleatória ou determinística. Na primeira, a partículavisita aleatoriamente os vizinhos, enquanto que, na segunda, a partícula prefere visi-tar vértices já dominados por ela. A seguir, ilustram-se os casos que podem ocorrerquando da escolha, por um partícula, de um vértice adjacente:

1. Se o vértice visitado vi ainda não pertencer a uma partícula: vρi (0) = 0. Logo, o

vértice passa a pertencer a essa partícula visitante, i.e., vρi (t) = ρj. O potencial

da partícula ρj não é alterado e o potencial do vértice vi recebe o potencial dapartícula: vω

i (t) = ρωj (t);

2. Se o vértice visitado é dominado pela mesma partícula, o potencial da partículavisitante, ρj, é incrementado e vi recebe o novo potencial da partícula: vω

i (t) =

2.3 - Detecção de Comunidades 23

ρωj (t);

3. Caso o vértice visitado pertença a partícula diversa, então os potenciais da par-tícula e do vértice são enfraquecidos. Se o potencial da partícula ρω

j atingir umvalor inferior que ωmin, então essa partícula é reiniciada em um novo vértice es-colhido aleatoriamente. Caso o potencial do vértice vω

j atingir um valor menorque ωmin, então o vértice não mais é propriedade de partícula alguma no modelo,i.e., o mesmo regressa ao estado livre: vω

j = 0.

Assim, o nível de dominação de um vértice aumenta, caso seja visitado pela par-tícula a qual o domina no instante atual. A contrario sensus, quando da visita de umapartícula rival a um vértice não dominado pela mesma, ocorre um enfraquecimentodo nível de dominação da partícula proprietária sobre aquele vértice. Caso essa domi-nação não for sólida o suficiente, a partícula ora dominante perde a propriedade sobreaquele vértice. Em um amplo período de tempo, espera-se que cada partícula domineuma comunidade na rede.

O modelo proposto em Quiles et al. (2008) apresenta duas características salientes:(i) altas taxas de detecção de comunidades e (ii) baixa complexidade computacional.No entanto, no trabalho original, apenas um procedimento de competição de partícu-las é introduzido, sem nenhuma definição formal. Isto impossibilita qualquer análiseou predição do comportamento do modelo. Como será visto mais para frente, uma dasprincipais contribuições dessa pesquisa é apresentar um modelo rigoroso por meio deum sistema dinâmico estocástico competitivo.

2.4 Considerações Finais

Neste capítulo, foi explorada a área de redes complexas, mostrando as vantagensinerentes à sua utilização, como a de levar em consideração a topologia estrutural pararealizar as tarefas a que são incumbidas. Esta vantagem é de especial importância, poistraz independência do modelo a distâncias de similaridade, característica comum emmétodos que não utilizam redes complexas. Além disso, foram revisados os conceitosde comunidades e sobreposição de comunidades e vértices. Por último, as principaistécnicas de detecção de comunidades propostas na literatura baseadas em Redes Com-plexas foram revistas, com especial importância para a técnica de detecção de comuni-dades via competição de partículas.


CAPÍTULO

3Aprendizado Semissupervisionado

Neste capítulo, serão fornecidos conceitos fundamentais sobre o aprendizado se-missupervisionado. Especificamente, serão analisadas técnicas pertencentes ao apren-dizado semissupervisionado, com ênfase nas baseadas em redes.

3.1 Aprendizado de Máquina

Tradicionalmente, existem dois tipos fundamentais de aprendizados em aprendizadode máquina. O primeiro é intitulado de aprendizado não supervisionado, cuja formulaçãoé dada a seguir: seja X = x1, . . . , xn um conjunto de n exemplos ou pontos, emque xi ∈ χ para todo i ∈ [n] := 1, . . . , n, onde χ representa o espaço caracterís-tico dos dados. Tipicamente, é assumido que os pontos são identicamente e indepen-dentemente distribuídos com uma distribuição comum χ. É conveniente definir, porquestões de clareza, para um problema em que os pontos são d-dimensionais, a matrizde dimensões n× d denotada por X = (xT

i )Ti∈[n] que contém, em cada uma de suas n

linhas, os itens de dados. Fundamentalmente, pode-se dizer que o problema de apren-dizado não supervisionado consiste em estimar a densidade geradora dos dados emχ (Chapelle et al., 2006). Entre as principais tarefas de aprendizado não supervisio-nado, podem-se destacar: agrupamento (Girvan e Newman, 2002; Karypis et al., 1999;Newman, 2006), detecção de outliers (Liu et al., 2004; Lu et al., 2003), redução de di-mensionalidade (Lim e Park, 2009), associação (Piatetsky-Shapiro, 1991), entre outras.No agrupamento, espera-se encontrar grupos em que itens de dados do mesmo gruposejam bem semelhantes uns aos outros, enquanto que itens de dados de grupos dis-tintos pouco se assemelhem, em termos da função de similaridade adotada (Mitchell,1997). Na detecção de outliers, a meta é encontrar itens de dados que destoam muito da

25

26 Capítulo 3 - Aprendizado Semissupervisionado

distribuição original que o gerou, i.e., objetiva-se encontrar aqueles itens de dados quesão diferentes da maioria (Liu et al., 2004). Na redução de dimensionalidade, espera-sedispor os itens de dados em um espaço dimensional inferior ao espaço da distribuiçãooriginal, com o fim de simplificar as relações entre os dados (Lim e Park, 2009). Na as-sociação, buscam-se gerar regras que relacionem subconjuntos de atributos preditivos(Piatetsky-Shapiro, 1991).

O segundo tipo de aprendizado denomina-se aprendizado supervisionado. A metaaqui é aprender um mapeamento de x para y, dado o conjunto de treinamento cons-tituído pelos pares (xi, yi). Neste caso, yi ∈ Y é chamado de rótulo do exemplo xi.Se os rótulos tiverem natureza numérica, então y = (yi)

Ti∈[n] denota o vetor-coluna

de rótulos. Novamente, um requisito padrão é que os pares (xi, yi) sejam amostradosidenticamente e independentemente distribuídos de uma distribuição mapeada no es-paço χ× Y (Chapelle et al., 2006). Este aprendizado é bem definido, uma vez que essemapeamento pode ser avaliado através do desempenho preditivo do classificador noconjunto de testes. Quando Y = R ou Y = Rd, isto é, o conjunto possível de rótulosé contínuo, a tarefa é chamada de regressão. Caso o conjunto de rótulos possíveis sejadiscreto, a tarefa é dita de classificação. Existem duas famílias de algoritmos para oaprendizado supervisionado. Os algoritmos generativos tentam modelar a densidadecondicional das classes p(x|y) utilizando algum procedimento de aprendizado não su-pervisionado. A densidade preditiva pode ser inferida a partir do teorema de Bayes:

p(y | x) =p(x | y)p(y)∫

Y p(x | y)p(y)dy. (3.1)

De fato, p(x | y)p(y) = p(x, y) representa a densidade conjunta dos dados, daqual os pares (xi, yi)χ× Y podem ser gerados. Já como segundo tipo de algoritmo deaprendizado supervisionado, existem os métodos discriminativos que não tentam esti-mar como os xi foram gerados, mas sim focalizam em estimar p(y|x). Alguns métodosdiscriminativos até limitam-se a modelar se p(y|x) é maior ou igual a 0, 5; um exemplodisto é as Máquinas de Vetor Suporte (SVM - Support Vector Machines) (Chapelle et al.,2006).

Em outras palavras, a principal diferença de uma tarefa relacionada ao aprendizadosupervisionado com outra concernente ao aprendizado não supervisionado reside nofato de que a primeira possui todo o conjunto de treinamento rotulado, sendo que oobjetivo é criar uma função preditiva que possa generalizar a partir deste conjuntode treinamento. Por outro lado, tarefas de aprendizado não supervisionado buscamcomportamentos ou tendências nos dados, tentando agrupá-los de forma que dadosmais similares estejam em um mesmo grupo. Pode-se dizer que, neste caso, tais tarefasguiam-se a partir da composição intrínseca dos dados. Como uma nova vertente depesquisa, o aprendizado semissupervisionado foi proposto, de forma a aliar os pontos

3.1 - Aprendizado de Máquina 27

positivos de cada modo de aprendizado. Nele, apenas alguns dados são rotulados,enquanto que a maioria não é rotulada. O objetivo é propagar o rótulo de exemplosrotulados para os exemplos não rotulados. A Figura 3.1 ilustra um esquemático mos-trando a diferença dos três modos de aprendizado. Especificamente, na Figura 3.1a émostrada como uma tarefa de agrupamento é realizada em aprendizado não supervi-sionado. Observe-se que não há informação alguma sobre os dados e o agrupamentoé realizado a partir de uma função de similaridade entre os dados. Na Figura 3.1bé ilustrado o cenário de uma classificação semissupervisionada em aprendizado se-missupervisionado. Note que alguns dados já possuem rótulos de antemão e outrosnão. O classificador deve propagar estes rótulos para os dados não rotulados. Por fim,na Figura 3.1c é explicitada uma tarefa de classificação em aprendizado supervisio-nado. Inicialmente, apenas os dados circulares são apresentados para o classificador,todos rotulados. Após o mesmo induzir uma hipótese sobre aquele conjunto de dados,novos dados - explicitados pelos dados triangulares - são apresentados para o classifi-cador decidir sobre qual classe cada um pertence. Na próxima seção, serão detalhadosos conceitos sobre aprendizado semissupervisionado, o qual será objeto de estudo nopresente projeto de pesquisa.

(a)

(b)

(c)

Figura 3.1: Esquemático dos três modos de aprendizado de máquina. Aprendizado: (a) nãosupervisionado (agrupamento); (b) semissupervisionado (classificação semissupervisionada);(c) supervisionado (classificação supervisionada).


3.2 Aprendizado Semissupervisionado: Definições, Moti-

vações e Modelos

Algoritmos capazes de aprender utilizando apenas alguns exemplos rotulados têmdespertado o interesse da comunidade de Inteligência Artificial. O aprendizado se-missupervisionado visa, dentre outras características, a reduzir o trabalho do especia-lista na rotulação de dados. Esta característica é bastante interessante principalmentequando o processo de análise dos dados é caro e demorado, como, por exemplo, emindexação de vídeo, classificação de sinais de áudio, categorização de textos, diagnósti-cos médicos, dados do genoma, dentre outros (Chapelle et al., 2006). Na Subseção 3.2.1,serão exploradas as raízes do aprendizado semissupervisionado. Já na Subseção 3.2.2,algumas motivações são elucidadas. Finalizando, na Subseção 3.2.3, uma formulaçãomatemática rigorosa é apresentada.

3.2.1 Uma Breve Evolução Histórica

Conforme a literatura indica, uma das primeiras ideias de se utilizar dados nãorotulados para classificação foi no auto-aprendizado, que ocorreu em meados da dé-cada de 60. Este representa um algoritmo iterativo que repetidamente utiliza métodossupervisionados a cada iteração. No seu início, apenas são utilizados, na sua fase detreinamento, os dados previamente rotulados. À medida que cada passo se conclui,uma parte dos dados não rotulados é rotulada de acordo com uma função de decisão.Após isso, o método supervisionado é retreinado utilizando suas próprias prediçõescom os dados adicionais que o método rotulou nos passos anteriores (Chapelle et al.,2006).

Um aspecto negativo do auto-aprendizado reside no fato de que o efeito de rotularnovos dados não rotulados depende do método de supervisão utilizado neste apren-dizado. Se o auto-aprendizado for utilizado para minimização de riscos empíricos, i.e.,para descrever limites teóricos para o desempenho do algoritmo, e de perdas binárias,os dados não rotulados não surtirão efeitos na solução. Ao invés disso, se for utilizadoum método de maximização marginal, como resultado, os limites de decisão serão alo-cados em lugares que se situam longe dos dados não rotulados (Vapnik, 1998). Umgrande aplicação de auto-aprendizado pode ser encontrada para desambiguação depalavras em Yarowsky (1995).

Seguindo a cronologia, o aprendizado semissupervisionado obteve um grande de-senvolvimento em meados da década de 70, quando o problema de estimar o discri-minante linear de Fisher com dados não rotulados foi analisado. Mais precisamente,o problema examinado constituía o caso em que cada densidade condicionada às clas-ses era Gaussiana com matrizes de covariância iguais. A probabilidade do modelo é

3.2 - Aprendizado Semissupervisionado: Definições, Motivações e Modelos 29

então maximizada utilizando tanto os dados rotulados quanto os não rotulados com oauxílio de um algoritmo iterativo, tal como o Expectation Maximization (Dempster et al.,1977).

Já na década de 90 e na primeira década do século XXI, o interesse em aprendizadosemissupervisionado cresceu no âmbito de aplicações (Chapelle et al., 2006), sendo quefoi utilizado em problemas de linguagem natural, classificação de textos (Yarowsky,1995) e análise e desenvolvimento de técnicas com baixas complexidade temporal eespacial (Breve et al., 2010; Callut et al., 2008).

3.2.2 Motivações para o Aprendizado Semissupervisionado

De um ponto de vista de engenharia, é claro que a coleta de dados rotulados émuito mais intensa e onerosa em relação à coleta de dados não rotulados. Entretanto, opropósito do aprendizado semissupervisionado vai além de considerações puramenteutilitárias. De forma discutível, a maioria do aprendizado natural (humano e animal)ocorre no regime semissupervisionado. No mundo em que se vive, os seres vivosestão em uma constante exposição a um fluxo de estímulos naturais. Tais estímulosenglobam os dados não rotulados que são facilmente perceptíveis. Por exemplo, emum contexto de aquisição e reconhecimento fonológico, uma criança é exposta a muitossons acústicos. Muitos destes sons não são familiares à criança. Um feedback positivopor parte de uma outra pessoa é a fonte principal de dados rotulados. Em muitoscasos, uma pequena porção de feedback é suficiente para permitir a criança dominar omapeamento acústico-fonético de quaisquer linguagens (Belkin et al., 2005, 2006).

A habilidade humana de aprender conceitos não supervisionados, como, por exem-plo, clusters e categorias de objetos, sugere que dados não rotulados podem ser utiliza-dos de forma satisfatória para aprender invariâncias naturais, para formar categoriase para construir classificadores. Em muitas tarefas de reconhecimento de padrões, hu-manos apenas têm acesso a uma pequena quantidade de dados rotulados. Logo, osucesso do aprendizado humano nesse pequeno conjunto de dados reconhecido, semsombras de dúvida, acontece pela efetiva utilização de grandes conjuntos de dados nãorotulados para extrair informação que é útil para generalização. Consequentemente, seo objetivo for progredir no entendimento e dominação de como o aprendizado naturalse processa, há a necessidade de se pensar em termos de aprendizado semissupervisi-onado (Belkin et al., 2004, 2006).

Outra motivação para o estudo de aprendizado semissupervisionado está intrinsi-camente ligada à melhoria da acurácia de modelos. Em um recente trabalho propostopor Singh et al. (2008), foi definido que, utilizando uma análise de amostras finita, se acomplexidade da distribuição sob consideração for muito alta para ser aprendida porn dados rotulados, mas é pequena o suficiente para ser aprendida por m n dados


não rotulados, então o aprendizado semissupervisionado é capaz de melhorar o de-sempenho de uma tarefa supervisionada. Como exemplo, considere a Figura 3.2 emque os círculos escuros denotam dados rotulados, enquanto que círculos claros, da-dos não rotulados. Aplicando-se um algoritmo supervisionado, a fronteira de decisãoseria estabelecida, muito provavelmente, nas vicinidades da linha pontilhada. De ma-neira análoga, algoritmos semissupervisionados fixariam, com uma grande margemde certeza, a fronteira de decisão na linha contínua. No caso desse exemplo, algorit-mos supervisionados não seriam capazes de eficientemente classificar os exemplos nãorotulados. Por outro lado, algoritmos semissupervisionados, a partir da utilização dedados não rotulados, poderiam obter acurácias bem superiores. Isto é exatamente oque ocorre na figura, a qual mostra que o algoritmo semissupervisionado reflete maisfielmente a distribuição das classes. Isto decorre graças à utilização da informação dosdados não rotulados no ato do treinamento do classificador.

Figura 3.2: Motivação para o estudo de aprendizado semissupervisionado. A linha pontilhadamostra o plano decisor que divide as duas classes feita por um algoritmo supervisionado. Alinha contínua denota o plano decisor gerado por um algoritmo semissupervisionado.

3.2.3 Formulação Matemática

De uma forma geral, o aprendizado semissupervisionado pode ser definido da se-guinte maneira (Chapelle et al., 2006): seja um conjunto de dados X = x1, x2, . . . , xn,dividido em duas partes, Xl = x1, x2, . . . , xl onde l < n e Xu = xl+1, . . . , xn. Já,Y = 1, 2, . . . , c representa o conjunto de rótulos. Para todo exemplo xi ∈ Xl, umrótulo yj ∈ Y é fornecido. Os rótulos do subconjunto Xu não são conhecidos a priori.Normalmente, l u, ou seja, a grande maioria de vértices não possui um rótulo (Cha-pelle et al., 2006). Isto ocorre porque a tarefa de rotulação é extremamente onerosa edeve ser feita por especialista. A Figura 3.1b ilustra um esquemático de uma tarefa declassificação semissupervisionada.

Com base nestas definições, o aprendizado semissupervisionado pode ter comofunção tanto tarefas de classificação de dados, quando os exemplos rotulados são uti-lizados no processo de rotulação de exemplos não rotulados, quanto de tarefas de

3.2 - Aprendizado Semissupervisionado: Definições, Motivações e Modelos 31

agrupamento. Neste último caso, os exemplos rotulados são responsáveis por guiaro processo de formação de clusters (Chapelle et al., 2006).

Entretanto, para um adequado funcionamento das técnicas de aprendizado semis-supervisionado, algumas suposições sobre a consistência dos dados são essenciais(Chapelle et al., 2006):

• Suposição de agrupamento: pontos que pertençam a uma mesma região de altadensidade, isto é, estejam localizados em um mesmo agrupamento são plausíveisde pertencerem a mesma classe. Esta suposição também é referenciada comosuposição de variedade, onde assume-se que dados pertencentes a uma mesmavariedade também são rotulados com a mesma classe.

• Suposição de suavidade: pontos próximos no espaço de atributos são prováveis depertencerem a mesma classe. Esta suposição força que a função responsável porrotular seja mais suave em regiões de alta densidade do que em regiões de baixadensidade. Fica claro o porquê desta restrição: basta pensar que, em regiões ondeexistam vários pontos adjacentes, é mais provável que estes pertençam à mesmaclasse; logo, ficaria incoerente ter uma função que mudasse rapidamente de saídapara estas regiões. Esta análise vai ao encontro com a suposição de agrupamentoe as duas, portanto, se complementam.

• Suposição de existência de manifolds: Tal ideia se embasa na premissa que um con-junto de dados em alta dimensão pode ser, de forma aproximada, reduzido a umespaço de menor dimensão (manifold dos dados). Esta hipótese é normalmenteseguida para amenizar o problema da maldição da dimensionalidade. Tal pro-blema é relativo ao fato que o volume do espaço aumenta exponencialmente como número de dimensões, e um número exponencialmente maior de exemplos énecessário para indução de classificadores com o mesmo poder de acurácia.

A forma como os algoritmos de aprendizado semissupervisionado tratam essas su-posições de consistência representa uma das diferenças fundamentais entre eles. Vá-rios algoritmos de aprendizado semissupervisionado foram propostos (Chapelle et al.,2006; Zhu, 2005a), sendo que grande parte destes utiliza como base algum algoritmoque foi projetado como técnica de aprendizado supervisionado ou não supervisionado,o qual é modificado para tratar dados rotulados e não rotulados. Como exemplo: COPK-Means (Wagsta et al., 2001) e outros, que são modificações do K-Means; SVM transdu-tiva (Cortes e Vapnik, 1995; Vapnik, 1998), que é uma extensão da técnica SVM (Vapnik,1999); algoritmos baseados em Expectation Maximization (Nigam et al., 2000); dentre di-versos outros (Chapelle et al., 2006; Zhu, 2005b).

Outra abordagem interessante é utilizada pela técnica denominada Co-Training. OCo-Training visa a rotular automaticamente mais exemplos a partir de um pequeno con-


junto previamente rotulado. Esta técnica se baseia na cooperação de dois algoritmos deaprendizado supervisionado, sendo que a ideia principal consiste em um classificadorrotular exemplos que são utilizados pelo segundo classificador e vice-versa (Blum eMitchell, 1998; Goldman e Zhou, 2000). Desta forma, espera-se aumentar a precisão declassificação quando comparado com a aplicação direta de uma técnica de aprendizadosupervisionado.

3.3 Abordagens de Aprendizado Semissupervisionado

A divisão de abordagens que os algoritmos de aprendizado semissupervisionadopodem tomar difere muito entre autores. Neste documento, a divisão de classes seráelencada baseando-se em Chapelle et al. (2006). Em termos gerais, existem três tipos:os modelos generativos, explorados na Subseção 3.3.1, os métodos de separação porregiões de baixas densidades, vistos na Subseção 3.3.2, e os métodos baseados em gra-fos, detalhados na Subseção 3.3.3. Dentre essas abordagens, o desenvolvimento detécnicas baseadas em grafos tem, nos últimos anos, obtido maior atenção (Chapelleet al., 2006; Zhu, 2005a). Nas próximas seções, serão analisadas essas abordagens emdetalhes, com atenção especial para a última.

3.3.1 Modelos Generativos

A inferência por modelos generativos envolve a estimação da densidade condi-cional p(x | y). Nesta abordagem, qualquer informação adicional correspondente ànatureza de p(x) é de extrema valia. Para efeitos didáticos, suponha, por exemplo,que p(x | y) seja Gaussiano (Chapelle et al., 2006). Então, pode-se utilizar o algoritmoExpectation Maximization para encontrar os parâmetros concernentes à distribuição ge-radora da Gaussiana para cada classe do problema. A única diferença entre o famosoalgoritmo Expectation Maximization padrão, aquele utilizado para agrupamento, e o emestudo resta no fato de que as variáveis desconhecidas associadas a cada exemplo ro-tulado, na verdade, não são a priori desconhecidas, ou seja, são sabidas e devem seriguais aos rótulos das classes já pré-definidos ao longo de todo o processo de otimiza-ção do Expectation Maximization (Zhu e Goldberg, 2009). Vale frisar que a suposição declusters deve ser cumprida, a fim de que o método gere resultados coerentes.

Um ponto forte da abordagem generativa é que o conhecimento da estrutura doproblema ou dos dados pode ser facilmente incorporado ao modelo. De acordo comRatsaby e Venkatesht (1995), os dados rotulados corretamente são exponencialmentemais efetivos para a minimização do erro de classificação do que os dados não rotula-dos. Já para o caso de dados não rotulados, conforme Shahshahani e Landgrebe (1994)indica, estes podem degradar o desempenho de classificadores utilizando esta aborda-

3.3 - Abordagens de Aprendizado Semissupervisionado 33

gem se forem introduzidos apenas dados outliers, ou, em outras palavras, dados quesão muito diferentes que os outros da sua classe.

Nota-se, portanto, que as técnicas que utilizam esta abordagem são, de maneirageral, muito sensíveis aos dados rotulados e não rotulados. Uma pré-análise deve serefetuada antes de proceder às simulações computacionais desses algoritmos, visto queruídos podem degradar consideravelmente o desempenho final do algoritmo (Alpay-din, 2004; Chapelle et al., 2006; Gärtner, 2008; Zhu e Goldberg, 2009).

3.3.2 Métodos de Separação por Regiões de Baixa Densidade

Nesta abordagem, os algoritmos buscam implementar a suposição de baixa densi-dade interclasse por meio do afastamento dos limites de decisão (hiperplanos de deci-são) dos dados não rotulados (Chapelle et al., 2006). O método mais comum para atin-gir esse objetivo consiste em utilizar o algoritmo de maximização marginal, tal comoas SVMs transdutivas. Entretanto, salienta-se que tal problema de maximização é, namaioria dos casos, não convexo e, portanto, apresenta sérias dificuldades na sua oti-mização, tendo em vista que encontrar o melhor hiperplano que maximize a distânciatotal não é trivial (Zhu e Goldberg, 2009).

Algumas alternativas, com o intuito de resolver esses problemas de maximizaçãonão convexa, foram propostas na literatura (Alpaydin, 2004; Chapelle et al., 2006; Cor-tes e Vapnik, 1995; Zhu e Goldberg, 2009). Por exemplo, em Vapnik (1998), inicia-sede uma solução da SVM treinada apenas com os dados rotulados, e, conforme cadaiteração avança, os dados não rotulados são rotulados por meio de predições da SVM.O processo é refeito com os novos dados rotulados até se atingir alguma condição deparada específica. Cada iteração é conduzida de forma que os pesos dos dados nãorotulados utilizados na maximização são sucessivamente incrementados. Como outroexemplo, o trabalho proposto em De Bie e Cristianini (2004) discute uma abordagemalternativa baseada na relaxação convexa do problema de otimização associada emSVM transdutivas.

3.3.3 Métodos Baseados em Grafos

Durante os últimos anos, a área mais ativa de pesquisa no campo de aprendizadosemissupervisionado foi a relacionada a métodos baseados em grafos ou redes. Oponto comum das técnicas que utilizam essa abordagem consiste no fato de utilizaremos dados como sendo os vértices da rede, enquanto que ligações entre os dados exis-tem, dependendo da função de similaridade escolhida, bem como da rotulação dos vér-tices (Chapelle et al., 2006). Uma das vantagens salientes da utilização de grafos para aanálise de dados está na habilidade de revelar a estrutura topológica entre o conjuntode dados. Por exemplo, considere uma tarefa de classificação semissupervisionada em


um problema binário, conforme mostrada na Figura 3.3a, em que as classes possuemdistribuição com formato de bananas e apenas dois dados foram pré-rotulados. O re-sultado da técnica SVM é dado na Figura 3.3b, enquanto que o resultado da técnicak-vizinhos mais próximos (kNN) é mostrado na Figura 3.3c. Considere que a classifi-cação ideal é dada na Figura 3.3d. Em ambos os resultados anteriores, os algoritmosnão foram capazes de encontrar as classes corretamente. A utilização de grafos nessetipo de problema pode revelar a estrutura topológica entre os dados, permitindo, as-sim, a detecção de classes e grupos com formatos arbitrários (Karypis et al., 1999; Zhouet al., 2003).

Figura 3.3: Motivação para utilização de grafos. (a) Problema inicial para classificação semis-supervisionada. (b) Resultado obtido aplicando SVM. (c) Resultado obtido aplicando kNN. (d)Resultado ideal. Figura extraída de Zhou et al. (2003).

O aprendizado semissupervisionado baseado em redes começa pela construção dografo a partir do conjunto de treinamento. Matematicamente, sejam (xi, yi)l

i=1 oconjunto de vértices rotulados e xjl+u

j=l+1, o conjunto de vértices não rotulados. Cla-ramente, a rede será de larga escala se l + u, o número de instâncias rotuladas e nãorotuladas, for grande. Perceba que, uma vez que a rede seja construída, o processode aprendizado envolverá designar o valor yt para todo vértice não rotulado xt. Istoé possível por meio da informação que as arestas, as quais interconectam os vértices,transportam (Chapelle et al., 2006). É de extrema valia mencionar que, em contrastecom as técnicas tradicionais que se utilizam de tabelas atributo-valor para conduzirsuas análises sobre os dados, a utilização de grafos utiliza diretamente a informaçãoda vizinhança para analisar os dados. Conforme explicitado em Zhu (2005b), isto podegerar mais robustez e eficácia na construção de classificadores.


Quanto à natureza das arestas, a literatura indica que podem ser direcionadas (dí-grafos), não direcionadas, com peso, entre outros tipos. Na maioria dos problemas,normalmente, as arestas são consideradas não direcionadas (um contraexemplo são oslinks de página web). O peso da aresta wij entre dois vértices xi e xj pode representar,por exemplo, a similaridade entre essas duas instâncias. Neste caso, a ideia é que se wij

for grande, então os dois rótulos de yi e yj são esperados de serem o mesmo. Observeaqui a conexão com a suposição de suavidade, porém com representação distinta: aoinvés de regiões de alta densidade, aqui considera-se o peso wij. Portanto, é de extremaimportância a designação correta dos pesos das arestas do grafo, pois esses traduzemas relações entre o conjunto de dados para a representação em grafo. Os pesquisadoresda área especificam os pesos das arestas a partir de heurísticas bem conhecidas, algu-mas das quais são elencadas a seguir. Reitera-se que a lista apresentada fica longe deser exaustiva.

• Rede completamente conectada: cada par de vértices xi, xj é conectado por umaaresta. O peso da aresta decresce à medida que a distância ‖xi − xj‖ aumenta.Uma função de peso popular é dada por:

wij = exp

(−‖xi − xj‖2

2σ2

)(3.2)

onde σ é conhecido como o parâmetro de comprimento de banda e faz o papelde controlar a velocidade na qual os pesos são decrementados, conforme cadaunidade de distância aumenta. Este peso tem a mesma forma que uma funçãoGaussiana, e, por isso, esta função também é intitulada como kernel Gaussianoou kernel RBF (do inglês - Radial Basis Function). Esse peso equivale um quandoxi = xj e zero quando ‖xi− xj‖ → ∞ (Zhou e Schölkopf, 2004). Um exemplo bemutilizado para calcular a distância ‖xi − xj‖ é a função de Minkowski para um pfixo, cuja expressão satisfaz:

d(xi, xj) = ‖xi − xj‖ =(

d

∑k=1|xik − xjk|2

) 1p

(3.3)

em que d representa a dimensão dos dados. Claramente, pode-se verificar que,quando p = 2, a Equação (3.3) reduz-se ao caso Euclidiano. Adicionalmente,quando p = 1, a Equação (3.3) torna-se a de Manhattan. A última normalmenteé utilizada em problemas geográficos de rodovias, corridas de táxis, entre outros(Duda et al., 2000).

• Rede k-vizinhos mais próximos (kNN): cada vértice define seus k vizinhos mais pró-ximos a partir de uma distância de similaridade, tal como a Euclidiana. Vale


notar que, em um grafo dígrafo, se xi estiver entre os k vizinhos mais próximosde xj, o contrário não é necessariamente verdade, isto é, xj pode não estar entreos k vizinhos mais próximos de xi. Haverá uma conexão, portanto, entre xi exj, caso qualquer um dos dois estiver na vizinhança dos k mais próximos um dooutro. Se xi e xj não forem conectados, então wij = 0. O método de construçãokNN naturalmente adapta-se às densidades das instâncias no espaço gerado pelodomínio das características. Em outras palavras, em uma região densa, o raio devizinhança kNN será pequeno, já que, por suposição, existem vários vértices per-tos uns dos outros, enquanto que, em uma região esparsa, este raio de vizinhançatende a ser maior em relação ao anterior. Empiricamente, as redes kNN com valo-res de k pequenos cumprem satisfatoriamente seus papéis (Chapelle et al., 2006).

• Redes ε-radius: conectam-se xi e xj se ‖xi − xj‖ ≤ ε, onde ε representa o tamanhoda vizinhança desejado. As arestas podem ser tanto sem peso ou com peso. Noúltimo caso, geralmente, utiliza-se a própria similaridade entre os dois dados. Sexi e xj não estiverem conectados, então wij = 0. Nota-se, nesta composição, queum pequeno aumento em ε pode surtir uma grande elevação do grau médio darede, dado que a rede não apresenta muitos dados dispersados. Em contraste,para uma rede dispersa, um alto valor de ε será necessário, ou incorre-se o riscoda rede ter muitos componentes separados (Alpaydin, 2004).

De uma forma geral, os métodos baseados em redes podem ser caracterizados comotécnicas transdutivas (Zhu, 2005a), isto é, o algoritmo visa a obter um valor para cadavértice não rotulado sem a necessidade de gerar (induzir) uma função global de mape-amento entrada-saída para os dados. Dentre as principais vantagens destas técnicas,podem ser citadas (Chapelle et al., 2006; Zhu, 2005a):

• Representam agrupamentos com formas variadas;

• Não dependem explicitamente de uma função de distância;

• Facilitam a representação de bases com múltiplas classes;

• Alguns problemas são originalmente representados por redes, por exemplo: da-dos de conexões entre sites, redes de interações de proteínas, etc;

• Dentre outras.

A seguir, serão resumidas algumas técnicas representativas de aprendizado semis-supervisionado baseado em redes.


Classificador de Regularização Local e Global

Nesta seção, será analisado o classificador de Regularização Local e Global (Zhouet al., 2003), pioneiro na área e um dos responsáveis por alavancar as pesquisas no ramode aprendizado semissupervisionado baseado em redes. Tal classificador considerao problema geral de aprendizado de dados rotulados e não rotulados por meio daconstrução de uma função de classificação que é suficientemente suave com respeito àestrutura intrínseca que é revelada pelos dados rotulados e não rotulados.

Antes de adentrar nos conceitos específicos da técnica supracitada, é válido regis-trar alguns pontos fundamentais que esta técnica tem em comum com outros métodosbaseados em minimização de energia. Em termos gerais, tais técnicas objetivam a mi-nimização de uma expressão de custo, constituída essencialmente por duas funçõesque modelam aspectos distintos do conjunto de dados em análise, quais sejam: (i)função de perda: objetiva penalizar o algoritmo para decisões em que os dados já pré-rotulados tem seus rótulos modificados ao longo do processo de propagação. Em ter-mos práticos, para minimizar este termo, basta evitar a mudança de rótulos de vérticespré-rotulados; e (ii) função regularizadora: responsável por modelar o custo de propa-gar rótulos a dados ainda não previamente rotulados. Tendo em vista a suposição desuavidade, tal função deve ser suave em regiões densas da rede.

Vistos estes pontos em comum, o Classificador de Regularização Local e Glo-bal agora é apropriadamente explanado. Vale notar que esta seção foi baseadaem sua maior parte em Zhou et al. (2003). Dado um conjunto de pontos X =

x1, . . . , xl, xl+1, . . . , xn ⊂ Rm e um conjunto de rótulos L = 1, . . . , c, os primei-ros l pontos xi (i ≤ l) são previamente rotulados como yi ∈ L, enquanto que os pontosremanescentes xu (l + 1 ≤ u ≤ n) não estão rotulados. A meta é rotular este segundoconjunto de vértices com base em alguma função de classificação.

Considere que = denote o conjunto de matrizes de dimensões n× c, todas com en-tradas não negativas. Uma matriz F = [FT

1 , . . . , FTn ]

T ∈ = corresponde a uma classifi-cação dos itens de dados X, de tal forma que, a cada dado não rotulado xi, é designadoum rótulo a partir da expressão yi = arg max

j≤cFij. Pode-se entender F como sendo uma

função vetorial F : X → Rc que atribui um vetor Fi para cada dado xi, isto é, para cadadado, o algoritmo mantém o nível de pertinência para cada rótulo possível, sendo que,este dado recebe, ao fim das iterações, aquele rótulo cujo nível de pertinência é o maior.Defina também uma matriz Y de dimensões n × c com Yij = 1 se xi estiver rotuladocomo yi = j e atribua Yij = 0, caso contrário. Claramente, Y é consistente com os rótu-los iniciais, uma vez que isto é manualmente feito pelo algoritmo na primeira iteraçãoe cada rótulo é fornecido pelo usuário. O algoritmo procede da seguinte forma (Zhouet al., 2003):

1. Crie a matriz de afinidade W, a qual é definida por Wij = exp(‖xi−xj‖2

2σ2 ) se i 6= j e


Wii = 0, caso contrário.

2. Construa a matriz S = D−12 WD−

12 , na qual D é uma matriz diagonal com sua

entrada (i, i) equivalente à soma da i-ésima linha de W

3. Itere F(t + 1) = αSF(t) + (1− α)Y até que convirja, onde α representa um parâ-metro entre (0, 1).

4. Considere que F∗ denote o limite da sequência F(t). Então, rotule cada dadoxi seguindo a fórmula: yi = arg max

j≤cF∗ij .

Em Zhou et al. (2003) foi demonstrado que tal sequência F(t) converge e quetambém a solução do problema de propagação de rótulos assume uma fórmula fechadadada por:

F∗ = limt→∞

F(t) = (I − αS)−1Y. (3.4)

Com a Equação (3.4), fica viável encontrar a solução ótima F∗ sem nenhuma itera-ção, bastando apenas realizar a inversão matricial. Além disso, esta equação mostraque o resultado final da iteração, depois de convergido, não depende das condiçõesiniciais do problema (Smola e Kondor, 2003). É importante notar também que estealgoritmo, com o propósito de obter a solução ótima, deve realizar uma tarefa de in-versão de matrizes, incorrendo, portanto, em uma complexidade temporal custosa,O(V3). Assim, para redes de grande escala, esta técnica não é viável.

De acordo ainda com Zhou et al. (2003), esses realizaram uma dedução de um fra-mework de regularização motivados pelo algoritmo supracitado. Este framework visa àminimização de uma função de custo que, na esfera física, pode ser entendida comouma função de energia. Tal função, denotada aqui por F, é definida como:

C(F) =12

n

∑i,j=1

Wij

∥∥∥∥∥ 1√Dii

Fi −1√Djj

Fj

∥∥∥∥∥2

+ µn

∑i=1‖Fi −Yi‖2

, (3.5)

onde µ > 0 é o parâmetro regularizador. Neste caso, a função de classificação fica:

F∗ = arg minF∈=

C(F). (3.6)

O primeiro termo da Equação (3.5) traduz-se como uma restrição de suavidade,significando que uma boa função classificadora não deve mudar muito de valor entredados próximos. É exatamente a definição de uma função regularizadora. Já o segundotermo simboliza uma restrição de ajuste, relatando que uma boa função classificadoratambém não deve mudar muito os rótulos dos vértices inicialmente rotulados. Neste


caso, tal termo encaixa-se perfeitamente na descrição de uma função de perda. O con-trapeso entre estas duas quantidades conflitantes é indicado pelo parâmetro positivo µ.Observe que a restrição de ajuste contém tanto dados rotulados quanto não rotulados(Zhou et al., 2003).

Matematicamente falando, fica fácil evidenciar a restrição de suavidade da Equação(3.5), bastando notar que um grande valor de Wij, que acontece quando os dados são

bem similares, deve ser nulificado ou minimizado por uma norma∥∥∥∥ 1√

DiiFi − 1√

DjjFj

∥∥∥∥2

reduzida; e, para conseguir tal fato, as entradas Fi e Fj devem ser próximas, ou seja,necessitam ter os mesmos rótulos dominantes. Quanto ao segundo termo, com o in-tuito de minimizá-lo, fica claro que não constitui uma boa mudança, a priori, trocaros rótulos dos vértices que foram inicialmente rotulados, incorrendo no risco, caso ostroquem, de uma penalidade indicada por uma aumento desta função de custo, já que,neste caso, Fi 6= Yi.

Regularizador por Manifolds

A técnica proposta por Belkin et al. (2006) baseia-se em uma família de algoritmosde aprendizado fundamentados em uma nova forma de regularização, que permite aexploração da geometria da distribuição marginal dos dados. Em específico, a princi-pal contribuição do trabalho em comento é a unificação de três conceitos, antes tratadosindependentemente, em um framework genérico. Tais conceitos são listados abaixo.

• O primeiro deles se remete à teoria espectral de grafos (Chung, 1997) que já foiaplicada em uma ampla gama de tarefas de classificação e agrupamento. Taismétodos, tipicamente, reduzem-se à análise dos autovalores do laplaciano dografo.

• O segundo conceito origina-se do ponto de vista geométrico dos dados. Tal abor-dagem toma como hipótese a existência de manifolds nos dados. Esses métodostentam usar a distribuição de probabilidades gerada por essa geometria para aconstrução de manifolds de Riemann (Weinberger e Saul, 2006).

• O terceiro conceito embasa-se no conjunto de ideias que norteiam regularizado-res em espaços de Hilbert (Smola e Kondor, 2003). Isto leva a uma classe dealgoritmos baseados em kernels para classificação e regressão.

Tecnicamente, os frameworks, até então propostos, alicerçavam-se apenas sobre doistermos, em relação à composição da função de energia, quais sejam: a função de perdae a função regularizadora (como, por exemplo, a técnica que foi vista anteriormente).Já o framework em Belkin et al. (2006) inaugura um terceiro termo, o qual é responsável


pelo aprendizado baseado em manifolds. Manifold é definido como um espaço topoló-gico de dimensão menor que o espaço original dos dados, cuja transformação é feitapreservando as características locais dos dados. Matematicamente, a função de energiaé expressa por (Belkin et al., 2006):

f ∗ = arg minf∈HK

1l

l

∑i=1

V(xi, yi, f ) + γA‖ f ‖2K + γI‖ f ‖2

I , (3.7)

onde ‖ f ‖2I é um termo penalizador que reflete a estrutura geométrica da distribuição

marginal dos dados. Intuitivamente, ‖ f ‖2I é um penalizador suave correspondendo a

distribuição probabilística dos dados. Por exemplo, se for possível a redução da distri-buição probabilística para um manifold, então ‖ f ‖2

I poderá penalizar f neste novo es-paço. γA controla a complexidade da função classificadora no espaço ambiente (espaçooriginal dos dados), enquanto que γI controla a complexidade da função classificadoraperante a geometria dos dados oriunda da probabilidade marginal dos mesmos. Emtermos sucintos, o primeiro termo é a função de perda, a qual penaliza modificaçõesde rótulos de dados já pré-rotulados; o segundo termo é um regularizador, o qual pe-naliza rotulações não suaves entre dados próximos no espaço original dos dados; e oterceiro termo é um outro regularizador, o qual penaliza rotulações não suaves em umespaço de menor dimensão dos dados (manifold), gerado a partir da distribuição mar-ginal. Os coeficientes γA e γI são incumbidos de dar maior ou menor importância aosdois últimos termos regularizadores, dependendo de suas magnitudes.

Embora a técnica seja uma framework genérico dependente dos dados, pode ser ob-servado que ela sofre de alguns inconvenientes, quais sejam: (i) erro de generalizaçãoe convergência: o problema crucial de análise do erro de generalização como uma fun-ção dos dados rotulados e não rotulados não foi apresentado; (ii) a seleção do modeloenvolve a escolha de muitos parâmetros, alguns dos quais altamente dependentes dosdados em análise; (iii) o framework proposto tem ordem de complexidade cúbica emfunção do número de exemplos. Escalabilidade e aplicações em problemas reais são,portanto, limitadas.

Classificador Semissupervisionado Guiado pela Medida de Modularidade

Nesta seção, será discutida uma técnica recentemente proposta em Silva e Zhao(2011a). A principal ideia desse método consiste em uma modificação estrutural doalgoritmo de otimização de modularidade para o paradigma de aprendizado semis-supervisionado, algoritmo o qual foi originalmente proposto para o aprendizado nãosupervisionado (Clauset, 2005; Newman, 2006). Em termos gerais, o algoritmo criauma rede utilizando o conjunto de dados de entrada e, a partir de modificações re-


alizadas no próprio processo de otimização de modularidade, realiza a classificaçãosemissupervisionada por meio da propagação de rótulos artificiais.

Inicialmente, é dada uma breve descrição do algoritmo cuja técnica em apreço ob-teve inspiração: o método de detecção de comunidades via otimização da modula-ridade (Clauset, 2005; Newman, 2006). Sumariamente, a medida de modularidadequantifica a qualidade de um particionamento da rede. Pequenos valores representamredes totalmente aleatórias, enquanto que valores altos indicam a presença de comu-nidades na rede em análise. Matematicamente, ela é calculada a partir da expressão:

Q =1

2m ∑i,j

(ei,j −

kik j

2m

)δ(ci, cj), (3.8)

onde m representa o número total de arestas na rede; ki é o grau do vértice i; δ(x, y) é afunção Delta de Kronecker, que produz 1 se x = y e 0, caso contrário; eij caracteriza afração de arestas que une as comunidades i e j. Em adição a isso, a matriz responsávelpor quantificar o potencial incremento de duas comunidades i e j, caso sejam fundidasem uma única comunidade, é dada por (Clauset et al., 2004):

∆Qij =

1

2m −kikj(2m)2 , se i e j estiverem conectadas

0, caso contrário. (3.9)

No algoritmo original proposto em Clauset (2005), a cada iteração, duas comunida-des, diga-se i e j, são fundidas, de tal forma que ocorra o maior incremento (ou menordecremento) da modularidade da rede. Na sua configuração inicial, cada vértice é umacomunidade. Uma propriedade interessante do processo de otimização é que, uma vezque todas as entradas da matriz ∆Q sejam negativas, fusões subsequentes sempre gera-rão novas matrizes ∆Q com todas as entradas negativas. Neste processo de otimização,nenhuma restrição quanto às comunidades a serem fundidas é estabelecido.

De forma a adaptar o algoritmo de otimização de modularidade para o contexto deaprendizado semissupervisionado, serão realizadas as seguintes modificações:

Passo I Inicialmente, existem |L| vértices rotulados na rede. A tarefa consiste em pro-pagar esses rótulos para vértices não rotulados. Uma vez que um vértice nãorotulado recebe um rótulo, este não pode ser mais mudado.

Passo II A cada passo, serão fundidas as comunidades (no começo, cada comunidadeengloba apenas um vértice) de tal forma que a modularidade é maximizada. En-tretanto, tal fusão é sujeita a algumas restrições: com o intuito de imitar a pro-pagação de rótulos na rede, uma fusão apenas ocorrerá se pelo menos uma das


comunidades a serem fundidas já foi rotulada anteriormente. Suponha que as co-munidades ci e cj foram selecionadas para serem fundidas no passo atual, cadaqual carregando os rótulos cl

i e clj (considere que ∅ denote uma classe sem rótu-

los), então um dos quatro casos a seguir deve acontecer:

Caso 1 A fusão não ocorre se cli 6= cl

j, desde que cli 6= ∅ e cl

j 6= ∅. Este caso re-presenta um confronto entre os limites de duas comunidades diferentes queforam anteriormente rotuladas.

Caso 2 A fusão ocorre se cli 6= ∅ e cl

j = ∅, ou cli = ∅ e cl

j 6= ∅. Este caso representaa propagação de rótulos tradicional de uma comunidade rotulada a outracomunidade sem rótulo. cl

j recebe o rótulo de cli no primeiro caso, e cl

i recebeo rótulo de cl

j no segundo caso.

Caso 3 A fusão ocorre se cli = cl

j, desde que cli 6= ∅ e cl

j 6= ∅. Neste caso, o processode fusão apenas coloca duas comunidades da mesma classe juntas, maximi-zando a modularidade.

Caso 4 A fusão não ocorre se cli = ∅ e cl

j = ∅, uma vez que nenhum rótulo estásendo propagado.

Se a fusão não ocorrer, então as próximas duas comunidades que oferecerem osegundo maior incremento de modularidade são selecionadas para serem potencial-mente fundidas, i.e., o Passo II é realizado novamente, e assim sucessivamente, atéque uma fusão válida ocorra.

Tendo em vista que o coeficiente de modularidade tenta maximizar o número dearestas entre vértices da mesma comunidade, enquanto que, concomitantemente, tentaminimizar esta quantidade entre diferentes comunidades, tal dinâmica propagará osrótulos de tal forma a manter a característica supracitada. Aqui, é estabelecido comohipótese a suposição de clusters, a qual premedita que uma classe é naturalmente umcluster. Desta forma, o algoritmo modificado de otimização de modularidade executao trabalho de propagar os rótulos de uma forma otimizada, i.e., as fusões e propaga-ções de rótulos ocorrem de forma que uma classe ou comunidade fique fortementeconectada e classes ou comunidades diferentes fiquem esparsamente conectadas.

O algoritmo finaliza quando todos os vértices não rotulados forem devidamenterotulados, desconsiderando, para todos os efeitos, o valor da modularidade da redeatual, já que não é buscada uma boa divisão da rede, mas sim uma forma ordenada derotulação de vértices, a qual é satisfeita naturalmente pelo mecanismo de otimizaçãoda modularidade. Uma análise da convergência foi conduzida em Silva e Zhao (2011a)e foi provado que o algoritmo sempre converge. Em termos técnicos, o algoritmo apre-sentado é não paramétrico, o que é uma vantagem sobre a maioria dos métodos pro-postos na literatura. Mais ainda, simulações foram conduzidas e foi demonstrado, de


forma positiva, a capacidade do modelo frente a dados de bases de dados reais. Porfim, além do classificador semissupervisionado guiado pela otimização da modulari-dade, os autores em Silva e Zhao (2011a) propuseram um esquema de redução da rede,de forma que o algoritmo possa ser aplicável a redes de larga escala.

D-Walks

Uma outra técnica que pertence ao aprendizado semissupervisionado intituladapelos autores criadores de D-Walks, que recentemente foi proposta por Callut et al.(2008), será objeto de estudo detalhado nesta seção. Uma vez que esta técnica embasa-se na teoria das cadeias de Markov, é válido defini-las formalmente a seguir.

Definição 1. Cadeias de Markov de Tempo Discreto: Uma cadeia de Markov de TempoDiscreto é definida como um processo estocástico Xt|t ∈ N, onde a variável aleatória Xtoma um valor específico para cada tempo discreto t em um conjunto contável pré-definido Ω,denominado espaço de estados, de tal forma que:

P[Xt = q|Xt−1, Xt−2, . . . , X0] = P[Xt = q|Xt−1]. (3.10)

Heuristicamente, o aspecto crítico de um modelo de Markov é que tal processo, con-forme avança no tempo, o mesmo esquece sobre seus estados passados, com exceçãodo imediatamente anterior.

Uma caminhada aleatória em uma cadeia de Markov pode ser definida da seguinteforma: um caminhante aleatório inicia em um estado q, de acordo com uma distribui-ção p0 conhecida. Logo após, ele se move para algum estado q′ ∈ Ω, respeitando amatriz probabilística de transição P. Repetindo esta última operação k vezes, resulta-se em uma caminhada aleatória de k passos. Em termos matemáticos, a matriz querepresenta a matriz de transição de k-passos é representada por Pk, caso a caminhadaseja homogênea (Szummer e Jaakkola, 2001). O conjunto destes passos no decorrer dotempo em um processo estocástico denomina-se realização do processo (Meyn e Twe-edie, 2009). Em uma cadeia de Markov, um estado q é dito ser absorvente se existe aprobabilidade de valor 1 de ir de q para ele mesmo. Em outras palavras, uma vez que oestado absorvente seja atingido em uma caminhada aleatória, o caminhante não maissairá daquele estado pelo resto dos passos subsequentes. Uma cadeia de Markov a qualpossui probabilidade 1 em terminar em um estado absorvente é classificada como umacadeia de Markov absorvedora. Em tal modelo, o conjunto de estados pode ser divididoem um conjunto de estados absorventes, denotado por ΩA e seu conjunto complemen-tar, denominado conjunto de estados transientes, denotado por ΩT = Ω \ ΩA. Afunção tempo de passagem, medida de suma importância nesta técnica, conta o nú-mero de vezes que um dado vértice foi visitado em uma caminhada aleatória (Callutet al., 2008). Matematicamente, ela é definida por:


Definição 2. Tempo de Passagem: Dada uma cadeia de Markov, M = 〈Ω, P, p0〉, o tempode passagem é uma função pt : Ω×Ω→N, tal que pt(q) é o número de vezes que o processoatinge o estado q em uma realização.

O tempo de passagem médio denota a esperança do tempo de passagem, ou seja,E[pt(q)]. O tempo de passagem médio, pois, é claramente infinito para estados absor-ventes, já que uma vez atingido ele nunca mais sai do mesmo. Para estados transientes,o tempo de passagem médio pode ser obtido a partir da matriz fundamental, dada porN = (I − PT)

−1, onde I representa a matriz identidade |XT| × |XT| (Çinlar, 1975). Aentrada nq′q contém o tempo médio de passagem do estado q ∈ ΩT durante caminha-das aleatórias começando no estado q′. Desta forma, E[pt(q)] = [pT

0 N]q, onde pT0 é a

transposta do vetor de probabilidades inicial reduzido apenas para os estados transi-entes . Mister se faz registrar que a esperança é calculada sobre todas as caminhadasaleatórias de qualquer tamanho (positivo).

A D-Walk, em termos gerais, é definida como uma caminhada aleatória que começaem um vértice rotulado e termina em um vértice cuja classe é igual ao do primeiro vér-tice em que se iniciou a caminhada. Tal ideia é rigorosamente fornecida na Definição3.

Definição 3. D-Walk: Dada uma cadeia de Markov definida no conjunto de estados Ω e umaclasse y ∈ Y, uma D-Walk é uma sequência de estados q0, q1, . . . , ql tal que yq0 = yql = y eyqt 6= y para todo 0 < t < l.

A notação Dy refere-se ao conjunto de todas as D-Walks que começam e terminamem um vértice da classe y. A função betweenness B(q, y) mede quantas vezes um vérticeq ∈ U se localiza entre os vértices da classe y ∈ Y. O betweenness B(q, y) é formalmentedefinido como o número esperado de vezes que um vértice q é encontrado duranteDy-walks, conforme pode ser observado na Definição 4.

Definição 4. Betweenness de uma D-Walk: Dado um vértice não rotulado q ∈ U e umaclasse y ∈ Y, a função de betweenness para D-Walks U ×Y → R+ é definida como:

B(q, y) ≡ E[pt(q)|Dy]. (3.11)

Agora, apresentam-se duas motivações para limitar as D-Walks: (i) complexidadealgorítmica: é fácil verificar que o tempo para o cálculo do betweenness exato é da ordemde O(n3), em virtude da realização da tarefa de inversão de matrizes, especificamentepara encontrar a matriz fundamental N, a qual é essencial no cálculo. (ii) A segundamotivação cumpre papel precípuo na análise e reside no fato de que se for prolongadomuito uma D-Walk, o caminhante acabaria por sair da região de interesse, isto é, daregião em que os vértices da sua própria classe estão localizados, e começaria a influ-enciar no betweenness de vértices mais longínquos, degenerando a taxa de classificaçãocorreta. A Definição 5 mostra precisamente a definição de D-Walks limitadas.


Definição 5. Betweenness de D-Walks limitadas: Dado um vértice não rotulado q ∈ U euma classe y ∈ Y, a função de betweenness para D-Walks limitadas U×Y → R+ é definidacomo:

B(q, y) ≡ E[pt(q) | Dy≤L], (3.12)

onde Dy≤L representa todas as D-Walks limitadas até o tamanho L. A restrição de li-

mitar o tamanho da caminhada introduz dois grandes benefícios, como já discutidosanteriormente: (i) melhores resultados de classificação são sistematicamente obtidosno que tange a caminhadas de tamanhos quaisquer (até o infinito), (ii) a medida debetweenness pode ser calculada de maneira eficiente. O betweenness com caminhadassem limites de tamanho pode ser aproximado para um de caminhadas limitadas detamanho, considerando grandes, mas finitos, valores de L. Mais precisamente, pode-se provar que o betweenness de caminhadas limitadas no tamanho converge em tempogeométrico no que diz respeito ao parâmetro L para o seu valor exato, ou seja, aquelecujas caminhadas não possuem restrições de tamanho (Callut et al., 2008).

A técnica é aplicada a todos os pares de vértices da rede pré-rotulados. O cálculodo betweenness em D-Walks limitadas pode ser realizado utilizando variáveis forward ebackward, similares àquelas propostas pelo algoritmo de Baum-Welch (Zhai, 2006). Umavez calculados todos os betweenness dos vértices não rotulados, estes são classificadosseguindo uma regra de decisão de maximização da a priori do betweenness de cadaclasse. Neste caso, a distribuição a priori P[y] utilizada será a proporção estimada devértices da classe y. Portanto, o rótulo de um vértice q ∈ U é classificado utilizando aseguinte equação:

yq = arg maxy∈Y

P [q|y] P[y]. (3.13)

Os autores em Callut et al. (2008) realizaram várias simulações com bases de dadosreconhecidas na comunidade, tais como IMDb, CORA, WebKB e obtiveram, de maneirageral, resultados de classificação superiores aos algoritmos clássicos da área, como oRegularized Laplacian (Zhu et al., 2003), Net Kit (Macskassy e Provost, 2005) e de Zhouet. Al (Zhou e Schölkopf, 2004), para várias proporções iniciais de vértices rotulados.No entanto, verifica-se no trabalho original que o cálculo do ótimo L é feito apenasempiricamente por meio de força bruta, o que acaba por aumentar a complexidadetemporal do método. Uma análise teórica do L ótimo ainda constitui um problemainteressante em aberto.


Caminhadas Aleatórias Markovianas sem Restrição

Os autores em Szummer e Jaakkola (2001) propuseram uma técnica de classifica-ção semissupervisionada baseada puramente em caminhadas aleatórias sem restrições.Neste contexto, a caminhada aleatória é baseada em uma métrica local apropriada.Usualmente, tal métrica faz uso da informação topológica da rede, no caso, a vizi-nhança local do item de dado, aqui concebido como um vértice. A partir dessa métrica,a matriz de transição probabilística é montada a partir da seguinte expressão:

P(i, j) =ai,j

∑Vu=0 ai,u

, (3.14)

onde P(i, j) denota a probabilidade de o caminhante realizar uma transição do vértice ipara o j; ai,j indica a similaridade atribuída, a partir da métrica escolhida, aos vértices ie j. No trabalho original, a métrica utilizada é o kernel Gaussiano (Chapelle et al., 2006).

A matriz construída com base na Equação (3.14) para ∀(i, j) ∈ V × V configura-se como a matriz de transição de 1 passo no processo Markoviano. Tal matriz aqui édenotada por P. A técnica desenvolvida em Szummer e Jaakkola (2001) se fundamentana análise da distribuição dos dados não rotulados por meio da utilização da matrizde transição genérica de t passos. Desta forma, a probabilidade de iniciar do vértice ie terminar em um vértice j depois de t passos é matematicamente expresso por:

Pt(i, j) = [Pt]ij. (3.15)

Na iteração inicial, é assumido que a caminhada aleatória pode se inicializar dequalquer vértice da rede, i.e., segue uma distribuição uniforme P(i) = 1/N. As proba-bilidades condicionais Pt(i, j) definem a representação dos itens de dados. Em outraspalavras, cada item de dado k é associado com um vetor de probabilidades condicio-nais Pt(i, j), i = 1, . . . , V. Os itens de dados nesta representação estarão próximos casoos mesmos demonstrem uma distribuição semelhante em relação aos estados inicias.Esta representação é crucialmente afetada pelo tamanho do passo t. Quando t → ∞,todos os itens de dados se tornam indistinguíveis, já que a distribuição de todos os vér-tices se aproxima da distribuição invariante, dado que o grafo é aperiódico e ergódico(Çinlar, 1975). Valores pequenos de t, por outro lado, aglomeram os itens de dadosem pequenos clusters. Por conseguinte, nesta representação, o parâmetro t controla aresolução na qual os dados são analisados.

O modelo de classificação assume que cada item de dado possui uma distribuiçãoP(y | i) sobre todos os rótulos y de classe presentes no problema. Essas distribuiçõessão desconhecidas a priori e representam os parâmetros a serem apropriadamente es-


timados. Com isto em mente, dado um item de dado k, o qual pode figurar como umdado rotulado ou não, este é interpretado como uma realização de uma caminhadaaleatória Markoviana de t passos. Assim, a probabilidade a posteriori do rótulo y ser doitem de dado k é dado por:

Ppost(y|k) =V

∑i=0

P(y | i)Pt(i, k). (3.16)

Com o propósito de classificar este item de dado k, o classificador escolhe a classeque maximiza esta a posteriori:

ck = arg maxc

Ppost(y = c | k). (3.17)

No entanto, P(y | i) geralmente é desconhecido para itens de dados não rotulados.Com o intuito de estimar tal distribuição, os autores em Szummer e Jaakkola (2001) uti-lizaram a técnica Expectation-Maximization (EM) de estimação paramétrica. O critériofixado é dado pela seguinte expressão dos dados rotulados:

L

∑k=1

log(P(yk | k) =L

∑k=1

logV

∑i=1

P(yk | i)Pt(i, k). (3.18)

Um grande problema dessa técnica reside na definição exata da resolução t. Embase de dados simples, normalmente um t baixo já consegue realizar a classificaçãode forma satisfatória. No entanto, conforme a complexidade das classes cresce, um tmaior é necessário. Em contrapartida, um t muito grande faz com que a classificaçãodegenere, uma vez que todas as distribuições de qualquer item de dado será igual adistribuição invariante do grafo, sob certas condições. Em suma, o parâmetro t é muitosensível à qualidade de classificação do algoritmo e deve ser calibrado de acordo coma base de dados em análise.

3.4 Considerações Finais

Neste capítulo, foi explorados os conceitos de aprendizado semissupervisionado,explicitando onde o mesmo se localiza em função da macroárea de Inteligência Artifi-cial e da área de Aprendizado de Máquina. Foram elencadas as principais motivaçõesque contribuíram para o nascimento desta área, sendo a principal delas o aumento ex-ponencial dos dados e o alto custo de rotulação. Esta área permitiu solucionar este tipode problema, apenas se embasando nos poucos exemplos já rotulados e, a partir daí, fa-


zendo a predição dos dados remanescentes. Além disso, foram mostradas as principaisabordagens tomadas no aprendizado semissupervisionado, com uma ênfase maior nosmétodos baseados em grafos, suas limitações e vantagens sobre as abordagens gene-rativas e de baixa densidade. Estas limitações incorrem devido aos altos custos deinversão matricial e de otimização das funções quadráticas de custos. Motivados poresta razão, métodos alternativos foram propostos, na tentativa de se desvencilharemdessas operações custosas. Especificamente, foram visto em detalhes cinco métodosde aprendizado semissupervisionado baseado em redes, quais sejam: classificador deregularização local e global, regularizador por manifolds, classificador semissupervisio-nado guiado pela medida de modularidade, D-Walks e caminhadas aleatórias sem res-trição. Os dois primeiros se fundamentam na minimização de um função de energia;o terceiro embasa-se no processo de otimização da medida de modularidade, original-mente proposta para detecção de comunidades; e o quarto e quinto se alicerçam sobrea teoria de caminhadas aleatórias.

CAPÍTULO

4Resultados Obtidos

Nesta seção, serão descritos os resultados obtidos, quais sejam: (i) modelagem dosistema de competição de partículas para o modo de aprendizado semissupervisio-nado via sistema dinâmico estocástico; (ii) análise matemática do modelo proposto; e(iii) simulações computacionais. As seções seguintes seguem didaticamente estes tó-picos. Vale ressaltar que todos os resultados obtidos nesta seção baseiam-se no artigoSilva e Zhao (2011b), o qual encontra-se em processo de revisão.

4.1 Modelagem do Sistema de Competição de Partículas

via Sistema Dinâmico Estocástico

Nesta seção, será discorrido sobre a formalização do sistema de competição de par-tículas. Especificamente, na Subseção 4.1.1, é fornecida uma visão geral do modelocompetitivo; na Subseção 4.1.2, a matriz competitiva de transição é demonstrada; naSubseção 4.1.3, o sistema dinâmico estocástico é exibido; na Subseção 4.1.4, um con-junto de condições iniciais pertencente ao sistema dinâmico é elucidado; na Subseção4.1.5, o algoritmo de competição de partículas é discutido; e, finalmente, na Subseção4.1.6, a análise de complexidade computacional do método proposto é estudada.

4.1.1 Visão Geral do Modelo

Considere que seja fornecido um grafo G = 〈V , E〉, onde V = v1, . . . , vV denoteo conjunto de vértices, enquanto que E = e1, . . . , eL ⊆ V × V , o conjunto de arestas.No modelo de aprendizado competitivo, um conjunto de partículas K = 1, . . . , K é

49

50 Capítulo 4 - Resultados Obtidos

inserido nos vértices da rede de forma aleatória. Cada partícula pode ser consideradacomo portadora de uma bandeira e seu objetivo precípuo resume-se em conquistar no-vos territórios - aqui representados pelos vértices -, enquanto que, simultaneamente,também defende seus territórios previamente conquistados. Observe que, como o ter-ritório nesse modelo possui o papel de recurso escasso, um processo competitivo iráse estabelecer naturalmente entre as partículas participantes. Quando uma partículavisita um vértice arbitrário, ela fortalece seu nível de dominação sobre aquele vérticee, concomitantemente, enfraquece todos os níveis de dominação das partículas rivaissobre aquele mesmo vértice, de tal maneira a imitar a competição por recursos queocorre em muitos processos sociais e naturais. De forma a se obter uma ideia concretado processo competitivo, será considerado o problema de classificação semissupervi-sionada em redes complexas. É esperado que este modelo, em um amplo período detempo, acabe por encontrando as classes na rede, de tal forma que cada partícula, ouum time de partículas, domine inteiramente uma classe.

Nesse modelo, uma partícula pode estar em um dos seguintes estados: ativo ouexausto. Quando a partícula estiver no estado ativo, ela navega pela rede segundouma política de movimentação que mescla comportamentos aleatório e preferencial,enquanto que, quando estiver no estado exausto, a partícula substitui esta mescla decomportamentos por uma nova política de movimentação que a obriga a regressarpara seu território previamente conquistado, com o propósito de ser recarregada (e,portanto, voltar a ficar ativa). O termo de movimentação aleatória é responsável pelocomportamento aventureiro da partícula, i.e., ela visitará vértices vizinhos sem se pre-ocupar com os níveis de dominação impostos por outras partículas rivais. Por outrolado, o termo de movimentação preferencial é incumbido do comportamento defen-sivo da partícula, i.e., ela preferirá reforçar seu território já conquistado, ao invés devisitar algum vértice que ainda não esteja dominado por ela. De forma que estas pro-priedades possam ser materialmente realizadas, cada partícula carrega consigo umnível de energia que, quantitativamente, indica a capacidade exploratória da mesma.Esta energia aumenta quando uma partícula está visitando um vértice cuja proprietá-ria é a própria partícula visitante, e decresce quando a mesma visita um vértice queestá sendo dominado por outra partícula rival. Se esta energia atingir um patamarmínimo pré-estabelecido, a partícula se torna exausta naquela iteração e, consequente-mente, é transportada de volta para território seguro, i.e., um dos vértices dominadospor aquela partícula ora exausta. Nos próximos passos, a partícula possivelmente serárecarregada por meio de visitas aos seus vértices já conquistados. Com este meca-nismo de confinamento artificial, espera-se que a região de atuação de cada partículaseja restringida, reduzindo, portanto, muitas visitas a vértices longínquos da rede, apa-rentemente sem qualquer relação com aquela partícula.

No esquema semissupervisionado, um conjunto de vértices pré-rotulados é forne-

4.1 - Modelagem do Sistema de Competição de Partículas via Sistema Dinâmico Estocástico 51

cido. Cada partícula representa um vértice rotulado, que, por sua vez, é associado auma determinada classe. As partículas são portadoras dos rótulos daqueles vérticesos quais representam. Essas partículas representativas navegam pelos vértices com opropósito de propagar esse rótulo, utilizando apenas a topologia local da rede. Nãoé permitida a troca de rótulos de vértices pré-rotulados. O processo cooperativo éconsiderado na classificação da seguinte forma: cada vértice mantém os níveis de do-minação impostos por todas as partículas presentes na rede. No ato de classificaçãode um vértice não rotulado, é calculado o nível de dominação imposto por cada timede partículas. O nível de dominação do time sobre aquele vértice é dado pela somados níveis de dominação impostos por cada membro pertencente àquele time de par-tículas. Por fim, a classe de um vértice não rotulado é decidida pelo time que impor omaior nível de dominação sobre o mesmo.

Por conveniência, a Tabela 4.1 traz uma breve descrição de toda notação relevanteusada neste trabalho.

Tabela 4.1: Breve descrição das notações mais relevantes utilizadas neste trabalho.

Notação Descrição

t Índice denotador do tempo.i, j Índices caracterizadores de vértices na rede.k Índice indicador de uma partícula na rede.

aij O peso da aresta interligando os vértices i e j.N(k)

i (t) Número de visitas realizado pela partícula k ao vértice i.p(k)(t) Localização da k-ésima partícula na rede no instante t.E(k)(t) Energia da partícula k no instante t.S(k)(t) Indicator do estado da k-ésima partícula no instante t: ativa ou exausta.ωmin Energia mínima permitida a uma partícula.ωmax Energia máxima permitida a uma partícula.

∆ Fração de energia ganha/perdida de uma partícula.P(k)trans(t) Matriz de transição da partícula k no instante t.Paleat Matriz de movimentação aleatória da partícula k (invariante no tempo).

P(k)pref(t) Matriz de movimentação preferencial da partícula k.

P(k)rean(t) Matriz de reanimação da partícula k

λ Contrabalanceador da quantidade de movimentação aleatória e preferencial.V Conjunto de vértices da rede.E Conjunto de arestas da rede.K Conjunto de partículas inseridas na rede.C Conjunto de rótulos (classes).L Conjunto de vértices pré-rotulados e seus correspondentes rótulos.S Conjunto correspondendo ao espaço gerado por V ×K.I Conjunto contendo todas os elementos que satisfazem ao Lema 3.M Conjunto de todos N(t) cujas entradas estão em I .


4.1.2 Derivação da Matriz de Transição Competitiva

Quanto à política de movimentação de uma partícula k ∈ K, como já explanadoem oportunidade prévia, esta basicamente é composta por dois tipos distintos de mo-vimentação: (i) um termo de movimentação aleatória modelado pela matriz P

(k)aleat, o

qual permite que a partícula se aventure na rede, sem se responsabilizar pela defesade seus vértices previamente dominados; e (ii) um termo de movimentação preferen-cial modelado pela matriz P

(k)pref, o qual é responsável por induzir a partícula a reforçar

os vértices os quais possuem como dono a própria partícula. Com o intuito de mo-delar tal dinâmica, considere o vetor estocástico p(t) = [p(1)(t), p(2)(t), . . . , p(K)(t)],o qual denota a localização do conjunto de K partículas apresentadas à rede, onde ak-ésima entrada, p(k)(t), indica a localização da partícula k na rede no instante t, i.e.,p(k)(t) ∈ V , ∀k ∈ K. Neste modelo, é desejado encontrar a matriz de transição que go-verna a distribuição de probabilidade da movimentação das partículas para um estadofuturo subsequente, p(t + 1) = [p(1)(t + 1), p(2)(t + 1), . . . , p(K)(t + 1)].

Com o intuito de modelar os estados possíveis de cada partícula inserida na rede,será introduzido o seguinte vetor estocástico S(t) = [S(1)(t), . . . , S(K)(t)], onde a k-ésima entrada, S(k)(t) ∈ 0, 1, indica se a partícula k está ativa ou exausta no tempot. Especificamente, se S(k)(t) = 1, então a partícula k é dita estar exausta no tempot. Analogamente, quando S(k)(t) = 0, a partícula é dita estar ativa no tempo t. Logo,se S(k)(t) = 0, a partícula navega na rede segundo uma mistura de comportamentosaleatório e preferencial. Entretanto, caso S(k)(t) = 1, a partícula modifica sua políticade movimentação para uma nova regra, a qual é modelada pela matriz P

(k)rean(t). Tal

matriz é responsável por compelir a partícula a regressar ao seu território previamenteconquistado, com a meta de reanimar a correspondente partícula por meio da revita-lização de sua energia. Este fenômeno é intitulado processo de reanimação. Uma vezque a partícula esteja revitalizada, a mesma, novamente, poderá executar a sua movi-mentação aleatório-preferencial na rede. Em suma, S(t) age como uma chave, a qualdetermina a política de movimentação de todas as partículas no instante t.

Diante das informações supracitadas, pode-se definir a matriz de transição compe-titiva associada à partícula k como:

P(k)trans(t) , (1− S(k)(t))

[λP

(k)pref(t) + (1− λ)P

(k)aleat

]+ S(k)(t)P(k)

rean(t), (4.1)

onde λ ∈ [0, 1] simboliza a fração desejada de movimentação preferencial que todas aspartículas na rede realizarão. É de extrema valia salientar que a Equação (4.1) é umacombinação convexa de matrizes de transição (o primeiro termo, por sua vez, tambémo é), uma vez que a soma dos coeficientes é unitária; logo, a matriz resultante é garan-tida ser outra matriz de transição. Restam-se definir as três matrizes que compõem a


Equação (4.1) de modo detalhado.

Os passos necessários para derivar a matriz de movimentação aleatória são diretos,uma vez que essa matriz depende diretamente da matriz de adjacência do grafo, aqual é conhecida a priori. Em face disto, cada entrada (i, j) ∈ V × V da matriz P

(k)aleat é

expressa como:

Paleat(i, j) ,ai,j

∑Vu=1 ai,u

, (4.2)

onde ai,j denota a (i, j)-ésima entrada da matriz de adjacência A do grafo. Observeque a Equação (4.2) se assemelha com a matriz Markoviana tradicional para um únicocaminhante aleatório, aqui simbolizado por uma partícula (Çinlar, 1975). Cumpre re-forçar também que a matriz Paleat é invariante no tempo e é idêntica para todas aspartículas na rede. Em termos sucintos, caso a partícula esteja no vértice i, a probabi-lidade de um vizinho adjacente j ser visitado, segundo esta política de movimentação,é proporcional ao peso da aresta que interliga os vértices i e j.

Com o propósito de auxiliar no cálculo da segunda matriz da Equação (4.1),P(k)pref(t), será introduzido o seguinte vetor estocástico:

Ni(t) , [N(1)i (t), N(2)

i (t), . . . , N(K)i (t)], (4.3)

onde dim(Ni(t)) = 1× K e Ni(t) representa o número de visitas que o vértice i rece-beu de todas as partículas até o tempo t. Especificamente, a k-ésima entrada, N(k)

i (t),fornece o número de visitas feito pela partícula k ao vértice i até o tempo t. Agora,essa noção é estendida para todos os vértices da rede por meio da definição da matrizglobal que mantém o número de visitas realizado por todas as partículas a cada vérticeda rede como:

N(t) , [N1(t), N2(t), . . . , NV(t)]T, (4.4)

onde dim(N(t)) = V × K. Formalmente, também define-se o vetor de nível de domi-nação do vértice i, Ni(t), de acordo com o seguinte vetor estocástico:

Ni(t) , [N(1)i (t), N(2)

i (t), . . . , N(K)i (t)], (4.5)

onde dim(Ni(t)) = 1×K e Ni(t) retrata a frequência relativa de visitas de todas as par-tículas na rede ao vértice i até o instante t. Particularmente, a k-ésima entrada, N(k)

i (t),


indica a frequência relativa de visitas feita pela partícula k ao vértice i até o instante t.Similarmente ao caso anterior, essa noção é estendida a todos os vértices constituintesda rede por intermédio da definição da matriz global de nível de dominação, a qual éresponsável por registrar todos os níveis de dominação impostos por cada partícula atodos os vértices na rede, a partir da seguinte expressão:

N(t) , [N1(t), N2(t), . . . , NV(t)]T, (4.6)

onde dim(N(t)) = V × K. Matematicamente, pode-se calcular a entrada N(k)i (t) de tal

matriz a partir da seguinte fórmula:

N(k)i (t) ,

N(k)i (t)

∑Ku=1 N(u)

i (t). (4.7)

À luz dessas explanações, pode-se definir P(k)pref(i, j, t), quantidade a qual caracte-

riza a probabilidade de uma única partícula k realizar a transição do vértice i ao j noinstante t, usando exclusivamente o termo de movimentação preferencial. Matemati-camente, tem-se:

P(k)pref(i, j, t) ,

ai,jN(k)j (t)

∑Vu=1 ai,uN(k)

u (t). (4.8)

Claramente, a partir da Equação (4.8), observa-se que cada partícula possui umamatriz de transição associada a sua movimentação preferencial, matriz a qual diferede partícula para partícula. Mais ainda, ao contrário da matriz relativa à movimen-tação aleatória, a matriz em apreço é variante no tempo com dependência direta nosníveis de dominação de todos os vértices da rede no instante t (N(t)). É válido no-tar que a abordagem aqui tomada para caracterizar a movimentação preferencial daspartículas é a frequência de visitas que cada partícula executa em cada vértice, de talforma que, quanto mais visitas uma partícula específica realiza em um vértice arbitrá-rio, maior será a chance da mesma repetidamente retornar ao mesmo vértice. Comoúltimo ponto a ser destacado desse tipo de movimentação, é importante verificar quea Equação (4.8) produz duas características presentes em um modelo de competiçãonatural, quais sejam: (i) o fortalecimento do nível de dominação que a partícula vi-sitante impõe ao vértice o qual visita; e (ii) o consequente enfraquecimento do nívelde dominação de todas as outras partículas rivais sobre aquele mesmo vértice. Estecomportamento é inerentemente representado em função da abordagem frequencial.


Agora, por questões didáticas, um exemplo simples que sumariza os pontos-chave atéentão introduzidos é estudado.

Figura 4.1: Uma típica situação em que a partícula vermelha, presentemente localizada no vér-tice v1, tem de selecionar o próximo vizinho a visitar. Neste exemplo, há 2 partículas, vermelhae azul (a partícula azul não é mostrada). A cor bege denota os vértices que ainda não foramdominados por quaisquer partículas até o instante t.

Exemplo 1. Considere a rede de 4 vértices mostrada na Figura 4.1, em que existem duas par-tículas: a primeira indicada pela cor vermelha e a segunda, azul. Para fins ilustrativos, apenasa localização da partícula vermelha é explicitada, a qual, no momento, visita o vértice v1. Nesteexemplo, será claramente explanado o papel que o nível de dominação possui no que tange àdeterminação da matriz de transição. Ainda na figura, é didaticamente indicado o vetor nível dedominação de cada vértice na rede no instante t. Observe que o proprietário de um vértice (na fi-gura, marcado pela cor do vértice) é decidido de acordo com a partícula que está impondo o maiornível de dominação àquele vértice específico. Por exemplo, no vértice v1, a partícula vermelhaimpõe uma dominação de 60%, enquanto que, a partícula azul, apenas 40%. A meta aqui é deri-var a matriz de transição da partícula vermelha, segundo as regras da Equação (4.1). Suponhaque, no tempo t, a partícula vermelha esteja ativa; logo, S(vermelha)(t) = 0 e, consequente-mente, o segundo termo da combinação convexa na Equação (4.1) é nulo. Arbitrariamente,fixa-se λ = 0.8 para este exemplo. Com base na Equação (4.2), a matriz de movimentaçãoaleatória da partícula vermelha é dada por:

P(vermelha)aleat =

0 1/3 1/3 1/3

1 0 0 01 0 0 01 0 0 0

, (4.9)

e a matriz de movimentação preferencial é, em consonância com a Equação (4.8), expressa por:


P(vermelha)pref (t) =

0 0.57 0.07 0.361 0 0 01 0 0 01 0 0 0

. (4.10)

Finalmente, a matriz de transição associada à partícula vermelha é determinada por umacombinação ponderada entre a matriz aleatória (invariante no tempo) e a matriz preferencialno tempo t, já que a partícula, por hipótese, está ativa. Essa ponderação é influenciada peloparâmetro λ. Numericamente, aplicando a Equação (4.1) tem-se:

P(vermelha)trans (t) = 0.2

0 1/3 1/3 1/3

1 0 0 01 0 0 01 0 0 0

+ 0.8

0 0.57 0.07 0.361 0 0 01 0 0 01 0 0 0

=

0 0.52 0.12 0.361 0 0 01 0 0 01 0 0 0

. (4.11)

Portanto, a partícula vermelha terá uma maior chance de visitar o vértice v2 (52% de chance)do que os outros vértices na vizinhança. Este comportamento pode ser controlado por meio davariação do parâmetro λ. Um alto valor induz a partícula exclusivamente a realizar movimen-tos segundo o termo preferencial, i.e., continuará sempre visitando vértices cuja proprietária éa própria partícula. Em contraste, um valor baixo assegura um maior peso para o termo de mo-vimentação aleatória, fazendo com que a partícula se assemelhe a um caminhante Markovianotradicional quando λ → 0 (Çinlar, 1975). No caso extremo, i.e., λ = 0, o mecanismo de com-petição é desligado e o modelo reduz-se a múltiplas caminhadas aleatórias sem interação entreos caminhantes. Com isto em mente, o modelo aqui estudado generaliza a teoria de múltiplascaminhadas aleatórias, dependendo da escolha do parâmetro λ.

Agora, será definida cada entrada de P(k)rean(t). Tal matriz é responsável por trans-

portar uma partícula exausta k ∈ K de volta ao seu território já conquistado, com opropósito de revitalizar a energia da partícula (processo de reanimação). Suponha quea partícula exausta k esteja visitando o vértice i quando sua energia é completamenteesgotada. Nesta situação, a partícula deve regressar para um vértice arbitrário j de seudomínio no instante t, em acordo com a seguinte expressão:


P(k)rean(i, j, t) ,

1arg max

m∈K

(N(m)

j (t))=k

∑Vu=1 1

arg max

m∈K

(N(m)

u (t))=k , (4.12)

onde arg maxm∈K

(.) retorna o índice m que maximiza o argumento e 1. é a função indi-

cadora que produz 1 se o argumento for logicamente verdadeiro e 0, caso contrário.De fato, uma análise cuidadosa da Equação (4.12) revela que a probabilidade da par-tícula k retornar a um vértice arbitrário j, já dominado pela mesma partícula, segueuma distribuição de probabilidade uniforme. Além disso, todas as linhas dessa ma-triz são iguais, mostrando que essa movimentação não depende do vértice o qual umapartícula está visitando. Desta forma, uma forma compacta de computacionalmenterepresentar essa estrutura pode ser empregada. Com isto em mente, a Equação (4.12)apenas resulta em probabilidades não nulas para vértices j que estão sendo domina-dos pela partícula k no instante t, não importando a existência de uma conexão entrei e j na matriz de adjacência. Em essência, uma vez que a partícula esteja exausta, achave S(k)(t) é ativada, que, por sua vez, obriga a partícula k a retornar ao seu territó-rio previamente dominado, de tal forma a recarregá-la. No modelo proposto, sempreexistirá pelo menos um vértice dominado por cada partícula, como será explicado emoportunidade vindoura.

Agora, o desenvolvimento da política de atualização de energia das partícu-las será discutido. Primariamente, é útil introduzir o vetor estocástico E(t) =

[E(1)(t), . . . , E(K)(t)], onde a k-ésima entrada, E(k)(t) ∈ [ωmin, ωmax], ωmax ≥ ωmin,denota o nível de energia que a partícula k possui no tempo t. Matematicamente, apolítica de atualização de energia das partículas é dada por:

E(k)(t) =

min(ωmax, E(k)(t− 1) + ∆), se proprietario(k, t)

max(ωmin, E(k)(t− 1)− ∆), se proprietario(k, t)(4.13)

onde proprietario(k, t) =(

arg maxm∈K

(N(m)

p(k)(t)(t))= k

)é uma expressão lógica que es-

sencialmente resulta em verdadeiro se o vértice em que a partícula k esteja visitandono tempo t (i.e., o vértice p(k)(t)) seja dominado pela mesma partícula, e falso, casocontrário; dim(E(t)) = 1×K; ∆ > 0 simboliza o incremento ou decremento de energiaque a partícula receberá em um instante t qualquer. Ademais, a primeira expressãona Equação (4.13) representa o incremento da energia da partícula e ocorre quandoa partícula k visita um vértice p(k)(t), no tempo t, cuja proprietária seja ela mesma,i.e., arg max

m∈K

(N(m)

p(k)(t)(t))= k. Similarmente, a segunda expressão na Equação (4.13)


aponta o decremento de energia da partícula e acontece quando a partícula k visitaum vértice p(k)(t) que não é dominado pela mesma, i.e., existe um nível de dominaçãomaior imposto àquele vértice por uma partícula rival. Em derradeiro, neste modelo, aspartículas serão penalizadas caso estiverem caminhando em território das partículasrivais. Isso é feito no intuito de minimizar caminhadas irrelevantes das partículas narede, as quais serviriam apenas para reduzir a velocidade de convergência do sistemadinâmico. Pelas mesmas razões, espera-se que este comportamento possa melhorar aacurácia do classificador semissupervisionado.

Avança-se agora a definição da regra de atualização que rege S(t), vetor o qual éresponsável por determinar a política de movimentação de cada partícula. Como jáfora mencionado anteriormente, uma partícula k arbitrária será transportada de voltaao seu domínio se sua energia atingir um patamar mínimo, quantificado por ωmin.Ora, é natural que cada entrada S(k)(t), portanto, necessite monitorar a energia cor-rente da sua partícula correspondente k, i.e., se esta energia, por alguma razão, atingiro patamar mínimo, então a chave S(k)(t) necessita ser ligada. Analogamente, se a par-tícula ainda possui energia maior que esse patamar mínimo, então a chave manter-se-ádesligada. Matematicamente, a k-ésima entrada de S(t) pode ser precisamente escritacomo:

S(k)(t) = 1E(k)(t)=ωmin, (4.14)

onde dim(S(t)) = 1 × K. Especificamente, S(k)(t) = 1 se E(k)(t) = ωmin e 0, casocontrário. Como há um limite superior para a variável aleatória E(k)(t), é claro quese a partícula k frequentemente visitar vértices que estejam dominados por partículasrivais, a sua energia decrescerá de tal forma que poderá atingir ωmin e, logo, se tor-nar exausta. O limite superior, ωmax, foi estabelecido para prevenir que as partículasna rede aumentem sua energia para um valor muito alto (por meio da constante vi-sita a vértices dominados por essa partícula), e, uma vez esta energia esteja grande obastante, a partícula poderia navegar para territórios muito longínquos, visitando, as-sim, um número substancial de vértices pertencentes a outras partículas até que suaenergia fique completamente esgotada. Desta forma, a taxa de classificação do sistemadinâmico seria consideravelmente reduzida. No próximo exemplo, serão resumidosos principais conceitos introduzidos até o momento.

Exemplo 2. Considere a rede de 20 vértices retratada na Figura 4.2. Suponha que existam 2partículas, a vermelha e azul, localizadas nos vértices v17 e v1, respectivamente. Como ambas aspartículas estão visitando vértices cujas proprietárias são partículas rivais, a energia daquelaspartículas será reduzida. Considere, também, que as partículas vermelha e azul tenham atingidoo patamar mínimo de energia, i.e., ωmin, no tempo t. Portanto, de acordo com a Equação (4.14),


Figura 4.2: Ilustração do procedimento de reanimação. Há duas partículas, a vermelha e azul,localizadas nos vértices v17 e v1 no instante t, respectivamente, as quais se tornaram exaustas.A rede engloba 20 vértices. A cor do vértice representa qual partícula está impondo o maiornível de dominação no tempo t.

essas partículas se tornarão exaustas. Consequentemente, S(vermelha)(t) = 1 e S(azul)(t) = 1,e a matriz de transição associada a cada partícula somente possuirá o segundo termo não nuloda combinação convexa indicada na Equação (4.1). Em consonância às regras do sistema dinâ-mico, estas partículas serão transportadas de volta ao seu território. Esse transporte acontecerásegundo a Equação (4.12). Em vista desse cenário, a matriz de transição para a partícula ver-melha, no instante t, será:

P(vermelha)trans (i, j, t) =

19

, ∀i ∈ V , j ∈ v1, v2, . . . , v9, (4.15)

P(vermelha)trans (i, j, t) = 0, ∀i ∈ V , j ∈ V \ v1, v2, . . . , v9, (4.16)

e a matriz de transição associada a partícula azul, no mesmo instante de tempo, será:

P(azul)trans (i, j, t) =

18

, ∀i ∈ V , j ∈ v13, v14, . . . , v20, (4.17)

P(azul)trans (i, j, t) = 0, ∀i ∈ V , j ∈ V \ v13, v14, . . . , v20. (4.18)

Pode-se verificar que, dado que a partícula esteja exausta, não importa o lugar onde a par-tícula se encontre, ela será transportada de volta para seu território (conjunto de vértices cujaproprietária é essa partícula). A determinação de qual dos vértices desse subconjunto que serávisitado segue uma distribuição uniforme, i.e., cada vértice já dominado possui chances iguaisde ser visitado pela partícula ora exausta.

Uma vez definida cada matriz associada a cada partícula no modelo, neste mo-mento, agrupam-se todas essas matrizes em uma matriz de transição representativaque engloba todas as partículas, intitulada aqui Ptrans(t), usando o seguinte fato:


quando uma partícula está ativa, sua movimentação é independente de todas as partí-culas rivais, dado que se tenha conhecimento do estado presente. Em virtude disso, alocalização das outras partículas não influencia na ação de escolher o próximo vértice aser visitado pela partícula em apreço, já que todo o estado presente é sabido e a matrizde transição unicamente depende dele. A mesma ideia pode ser aplicada quando apartícula está exausta. Em função dessa propriedade, a matriz global de transição queindica a transição do vetor estocástico p(t) para p(t + 1) pode ser descrita:

Ptrans(t) = P(1)trans(t)⊗ . . .⊗P

(K)trans(t), (4.19)

onde⊗ denota o operador produto tensor de Kronecker. Assim, a Equação (4.19) com-pletamente especifica a matriz de transição de todas as partículas na rede.

Essencialmente, p(t + 1) é visto como um processo estocástico discreto, cuja distri-buição de probabilidade é dada pela linha indicada pela forma escalar de p(t) (a serdefinida) da matriz Ptrans(t). Com o intuito de tornar este processo viável, enumeram-se os estados do vetor que guarda a localização das partículas p(t), de tal forma a serpossível a sua utilização com a matriz de transição global. Isto decorre do fato que,para K ≥ 2, p(t) será um vetor e não seria possível convencionalmente definir a linhap(t) da matriz Ptrans(t). Esta enumeração do vetor p(t) para sua forma escalar é feitarespeitando à ordem natural das tuplas, i.e., p(t) = [1, 1, . . . , 1, 1] (todas as partículasno vértice 1) denota o primeiro estado; p(t) = [1, 1, . . . , 1, 2] (todas as partículas novértice 1, exceto a última partícula, a qual localiza-se no vértice 2) é o segundo estado;e assim sucessivamente, até o estado escalar VK.

Observação 1. A matriz Ptrans(t) na Equação (4.19) possui dimensões VK × VK, as quaissão indesejadamente altas. Na tentativa de economizar espaço, em todas as simulações, seráutilizada a coleção de K matrizes mostradas na Equação (4.1). A matriz global de todas aspartículas será bastante útil, como será visto, nas derivações apresentadas na seção de análisematemática.

4.1.3 O Modelo de Aprendizado Competitivo Semissupervisionado

Em vista das considerações tomadas na seção anterior, o sistema dinâmico estocás-tico proposto para modelar este comportamento competitivo entre as partículas seráanalisado aqui. Primeiramente, o estado interno do sistema dinâmico é dado por:


X(t) =

N(t)p(t)E(t)S(t)

, (4.20)

e o sistema dinâmico competitivo é dado por:

φ :

N(k)i (t + 1) = N(k)

i (t) + 1p(k)(t+1)=i

E(k)(t + 1) =

min(ωmax, E(k)(t) + ∆), se proprietario(k, t)

max(ωmin, E(k)(t)− ∆), se proprietario(k, t)

S(k)(t + 1) = 1E(k)(t+1)=ωmin

(4.21)

onde, conforme já estudado, dim(N(t)) = V × K, dim(p(t)) = 1× K, dim(E(t)) =

1× K e dim(S(t)) = 1× K, resultando que dim(X(t)) = (V + 3)× K, com N(k)i (t) ∈

[1, ∞), (i, k) ∈ S , onde S é o espaço gerado por V × K. Observe que o vetor estocás-tico p(t + 1) não possui uma fórmula fechada, uma vez que é qualificado como umadistribuição dependente de p(t) e N(t); logo, sua aquisição é meramente por geraçãode números aleatórios. Sucintamente, o estado interno do sistema, como mostrado naEquação (4.20), carrega: (i) o número total de visitas feito por cada partícula a cadavértice da rede, (ii) a localização das partículas na rede, (iii) a energia das partículas e(iv) o vetor de chaves, que indica se as partículas estão ativas ou exaustas.

Além disso, verifica-se que o sistema φ é não linear, em virtude da função indica-dora. A primeira equação do sistema φ é responsável pela atualização do número devisitas do vértice i pela partícula k até o tempo t; a segunda equação é usada para man-ter o nível de energia atual de todas as partículas inseridas na rede; e a terceira equaçãoé utilizada para chavear as partículas entre ativas ou exaustas. É de extrema valia sa-lientar que, para que o estado interno do sistema X(t) seja completamente construído,a primeira expressão do sistema φ deve ser usada para todo (i, j) ∈ S e a segunda eterceira expressões necessitam ser avaliadas por todo k ∈ K. Uma outra importantecaracterística do sistema φ, a qual será extensivamente utilizada nas próximas seções, ésua propriedade Markoviana (verificar Proposição 1). Finalmente, note que o sistemaφ também pode ser escrito de forma matricial:

φ′ :

N(t + 1) = fN(N(t), p(t + 1))E(t + 1) = fE(N(t + 1), p(t + 1))S(t + 1) = fS(E(t + 1))

, (4.22)


onde fN(.), fE(.) e fS(.) são funções matriciais, em que cada entrada dessa matriz édefinida pelos termos escalares que aparecem na Equação (4.21). Esta forma alternativamatricial será utilizada para simplificar os cálculos nas seções futuras.

4.1.4 As Condições Iniciais do Sistema Competitivo

Com o objetivo de iterar o sistema φ, um conjunto de condições iniciais é preciso.Primeiramente, a posição inicial das partículas p(0) é controlável pelo usuário. A po-sição inicial das partículas não afeta o processo de classificação, devido ao procedi-mento de reanimação. Usualmente, as partículas são colocadas nos vértices os quaisrepresentam. Secundariamente, deve-se inicializar N(0) seguindo algumas restrições.No caso semissupervisionado, é fornecido um conjunto de vértices pré-rotulados e ameta é propagar tais rótulos aos vértices ainda não rotulados. Para esses vértices inici-almente rotulados, fixa-se seu proprietário como sendo a partícula que foi gerada pararepresentá-lo da seguinte forma: como a propriedade de um vértice é representadapelo máximo nível de dominação imposto àquele vértice, pode-se simplesmente forçarque o número de visitas que essa partícula representante possua para aquele vérticepré-rotulado seja ∞ desde o início; logo, impossibilitando qualquer mudança de pro-prietário sobre esse vértice pré-rotulado. Normalmente, mais de uma partícula (time)é gerada para representar um subconjunto de vértices pré-rotulados, todos da mesmaclasse. Cada partícula tenta dominar vértices na rede independentemente. A coope-ração entre as partículas de um mesmo time ocorre no final do processo. De formaa realizar isso, para cada vértice, somam-se os níveis de dominação de partículas domesmo time para obter o nível de dominação agregado daquele time sobre aquela par-tícula.

Com isso em mente, considere um conjunto de classes C e um conjunto de exemplospré-rotulados VL ⊂ V . SejaL o conjunto em que cada elemento armazena o par: vérticepré-rotulado e sua classe correspondente, i.e., L = (v1, c1), . . . , (v|VL|, c|VL|), ondevi ∈ VL e ci ∈ C, 0 ≤ i ≤ |L| = |VL|. Então, cada entrada de N(0) é fixada como:

N(k)i (0) =

∞, se a partícula k representa o vértice i

1 + 1p(k)(0)=i, caso contrário, (4.23)

em que aplica-se a Equação (4.23) para todo (i, k) ∈ S . Note que o escalar 1 é introdu-zido na segunda expressão da Equação (4.23) com o fim de vértices não visitados e nãoinicialmente rotulados no tempo t tenham seu cálculo bem definido, de acordo com aEquação (4.7), já que o denominador não pode resultar em 0. Em relação às condiçõesiniciais de E(0), deseja-se uma competição justa entre as partículas, assim, seus valoresde energia iniciais são fixados como uma mesma constante, da seguinte forma:


E(k)(0) = ωmin +

(ωmax −ωmin

K

). (4.24)

Finalmente, a variável estocástica que é incumbida de indicar se a partícula k estáativa ou exausta no tempo inicial t = 0, S(k)(0), ∀k ∈ K, é dada por:

S(k)(0) = 0, (4.25)

i.e., inicialmente, todas as partículas estão ativas no processo competitivo.

Figura 4.3: Diagrama de fluxo que indica, em alto nível, como o sistema dinâmico φ evolui notempo.

4.1.5 O Algoritmo

Com o intuito de facilitar o entendimento de como o sistema dinâmico estocásticoproposto evolui no tempo, a Figura 4.3 mostra um diagrama de fluxo com as princi-pais tarefas que devem ser processadas. No primeiro bloco, “Configurar CondiçõesIniciais”, inicializa-se o estado interno do sistema X(0), o qual é composto por N(0),p(0), E(0) e S(0). Depois disso, o sistema começa a iterar e o comando lógico “Crité-rio de Parada” é checado a cada iteração. Para uma iteração específica, cada partícula


precisa se locomover para um outro vértice, segundo a matriz de transição no instanteatual. Isso é precisamente realizado pelo laço interno começando da condição lógica“k > K”. Dentro desse laço, gera-se a matriz de transição variante no tempo associadaa partícula k (bloco “Calcular Matriz de Transição da Partícula k”) e faz-se a transiçãoda partícula para um próximo vértice em consonância com essa matriz (bloco “Partí-cula k Visita Outro Vértice”). Quando todas as partículas tiverem, apropriadamente,realizado suas movimentações, o laço interno cessa e atualizam-se as variáveis internasremanescentes do sistema, i.e., N(t), E(t) e S(t), para um t ≥ 1 arbitrário (bloco “Atu-aliza Variáveis Restantes do Sistema”). Logo após calcular estas variáveis restantes, osistema pode evoluir no tempo mais uma iteração ou, ao invés disso, caso a condiçãode parada seja satisfeita, retornar N(t) ao usuário (bloco “Retornar Matriz de Domi-nação”). Neste caso, cada vértice não rotulado tem sua classe definida pelo time departículas que impor o maior nível de dominação sobre aquele vértice.

O Algoritmo 1 sumariza todos os passos, de forma detalhada, para iterar o sistemaφ. Essencialmente, o algoritmo aceita o conjunto de dados (dados) e um conjunto dedados pré-rotulados (L), bem como três parâmetros definidos pelo usuário: a fração deenergia ganha/perdida pelas partículas no modelo (∆), a fração desejada de movimen-tação preferencial (λ) e um fator de parada (ε). Usualmente, bons resultados podem serobtidos por intermédio da seleção de um valor arbitrário entre 0.05 e 0.4 para ∆, e 0.5até 0.8 para λ (veja a Subseção 4.3.1). ε pode ser fixado como um valor arbitrariamentepequeno. K é o número de dados rotulados e também o número de partículas inseri-das no modelo. Observe que o critério de parada também pode ser definido como umcerto número de iterações.

4.1.6 Análise de Complexidade Algorítmica

Na lista a seguir, será discutida sobre a análise de complexidade de todos os co-mandos relevantes apresentados no Algoritmo 1.

• Passo 2: A cardinalidade do conjunto pode ser avaliada por uma única passagempelo conjunto. Assim, a complexidade temporal é O(K);

• Passo 3: Construção da rede a partir do conjunto de dados de entrada. Este processopossui complexidade temporal de O(V2), uma vez que a matriz de distância deveser calculada;

• Passo 4: Geração das K partículas na rede. Esse passo tem complexidade temporalde O(K);

• Passo 5: Neste passo, deve-se visitar todas as arestas da rede. Logo, esta operaçãotem complexidade temporal de O(L), onde L denota o número de arestas na rede;


Algoritmo 1: Algoritmo de competição de partículas semissupervisionado.Entrada: dados - conjunto de dados de entrada.

L - conjunto de dados pré-rotulados.∆ - fração de energia ganha/perdida de qualquer partícula.λ - fração de movimentação preferencial.ε - critério de parada.

1 início2 K ← |L|;3 A← construirRede(dados);4 p(0)← gerarParticulas(A, L);5 Paleat ← calcularMatrizAleatoria(A): Usar (4.2);6 N(0)← calcularNInicial(p(0), L): Usar (4.23);7 N(0)← calcularNBarra(N(0)): Usar (4.7);8 E(0)← calcularEInicial(K): Usar (4.24);9 S(0)← calcularSInicial(): Usar (4.25);

10 t← 0;11 repita12 para todo k ∈ K faça13 P(k)

pref(t)← calcularMatrizPreferencial(N(t), p(t)): Usar (4.8);

14 P(k)rean(t)← calcularMatrizReanimacao(N(t), p(t)): Usar (4.12);

15 P(k)trans(t)← calcularMatrizTransicao(λ, Paleat,P

(k)pref(t),P

(k)rean(t)): Usar (4.1);

16 p(k)(t + 1)← escolherProximoVertice(P(k)trans(t),p

(k)(t));17 fim para todo18 N(t + 1)← atualizarN(N(t), p(t + 1)): Usar primeira eq. em (4.21);19 N(t + 1)← calcularNBarra(N(t + 1)): Usar (4.7);20 E(t + 1)← atualizarE(E(t),N(t + 1), p(t + 1)): Usar segunda eq. em (4.21);21 S(t + 1)← atualizarS(E(t + 1)): Usar terceira eq. em (4.21);22 t← t + 123 até ‖N(t)− N(t− 1)‖∞ < ε;24 retorna N(t)25 fim

• Passos 6 e 7: Uma simples operação deve ser feita para cada uma das K×V entradasdas matrizes N(0) e N(0), respectivamente. Portanto, estes passos caracterizam-secomo tendo complexidade temporal de O(KV);

• Passos 8 e 9: Outra simples operação é realizada para cada uma das K entradas deE(0) e S(0). Desta forma, a complexidade temporal é O(K);

• Passo 13: Suponha que 〈k〉 seja o grau médio da rede. Então, segue que este passopode ser completado em O(〈k〉);

• Passo 14: Mantém-se uma hashtable para armazenar os vértices que estão sendo do-minados por cada partícula. Assim, consegue-se encontrar um vértice dominadopor uma partícula exausta em tempo constante, i.e., O(1);

• Passo 15: Multiplicação de escalares pelo número de vizinhos do vértice que a partí-cula k está visitando. Isto é concluído em O(〈k〉);

• Passo 16: A partícula k escolhe o próximo vértice a visitar. Utiliza-se uma funçãode probabilidade cumulativa seguindo a distribuição de probabilidade calculada noPasso 15 e, a partir da geração de um número aleatório, realiza-se a transição dapartícula a um outro vértice adjacente. Logo, tendo em vista que a matriz de tran-


sição possui distribuição de probabilidade arbitrária, este passo tem complexidadetemporal O(〈k〉);

• Passos 18 e 19: Atualização das matrizes N(t) e N(t). Considerando que, no máximo,K vértices distintos serão visitados em qualquer iteração, é garantido, portanto, que,no máximo, K linhas das matrizes N and N mudarão. Por conseguinte, essa atuali-zação pode ser realizada em O(K2), em virtude de cada uma das K linhas possuir Kentradas;

• Passos 20 e 21: Completados em O(K).

Tendo em vista que os Passos 13 a 16 repetem K vezes, segue que este bloco possuicomplexidade temporal O(K〈k〉). A complexidade temporal do próximo bloco, de-finido pelos Passos 18 a 22, é determinado pelos Passos 18 e 19, i.e., O(K2). Diantedesses fatos, o algoritmo de classificação semissupervisionada, sem considerar o laço“repita”, possui complexidade temporal O(K〈k〉+ K2).

A seguir, será estimado o número de iterações do laço “repita” (Passos 11 a 23).Considere uma rede com classes completamente separadas, e suponha que cada classetenha uma única partícula. Neste cenário, cada vértice pode ser dominado por apenasuma visita da partícula; logo, o número de iterações do laço principal é certamenteO(V) = c1V, onde c1 é uma constante positiva proporcional à fração de movimenta-ção aleatória realizada pelas partículas. Agora, caso as classes estejam conectadas deuma maneira bem definida (i.e., poucas conexões interclasses), cada vértice pode tersua propriedade definida a partir de um pequeno número de visitas. Então, com oobjetivo de ter todos os V vértices dominados pelas partículas, o número de iteraçõesé novamente O(V) = c2V, onde c2 é uma constante positiva satisfazendo c2 > c1. Se-guindo o mesmo raciocínio, pode-se inferir que o número de iterações requeridas paraque todos os vértices sejam completamente dominados pelas partículas é O(V) = cV,onde c é uma constante cuja magnitude aumenta com o aumento da porção de arestasinterclasses. Portanto, a partir dessa análise, estima-se que o laço principal repita porcV vezes.

Em suma, o algoritmo de classificação semissupervisionada baseado em competi-ção de partículas possui complexidade temporalO(V2 + K〈k〉V + K2V). Alguns casosparticulares podem ser discutidos:

• Se a rede é esparsa, i.e., 〈k〉 V, o algoritmo de classificação reduz-se para umacomplexidade temporal O(V2). Note que o algoritmo, sem a fase de construção derede, rodaria em O(V);

• Se o grau médio da rede 〈k〉 for proporcional a V (uma rede altamente intercon-nectada), então o algoritmo de classificação semissupervisionada tem complexidadecomputacional O(KV2);


• Uma vez que a quantidade de partículas inseridas na rede é usualmente baixa eo grau médio da rede pode ser controlado pelo usuário de forma a ser um valorpequeno, i.e., K V e 〈k〉 V, é razoável assumir que o algoritmo de classificaçãosemissupervisionada tem complexidade temporal O(V2) na maioria dos casos, emvirtude da construção da rede. Nesse caso, o algoritmo rodaria em complexidadeO(V) se não fosse considerada a fase de construção de rede.

A seguir, a complexidade temporal do modelo proposto será observada empirica-mente. Nestas simulações, o Passo 3 não é realizado, ou seja, a rede já é dada. Semconsiderar tal passo, utiliza-se 〈k〉 = 16 V, em que espera-se que o algoritmo rodeem tempo linear (O(V)). Para a construção das redes, serão utilizadas as redes aleató-rias clusterizadas, cujo método de construção foi apresentado no Capítulo 2 (Subseção2.2.4). Tais redes serão geradas com tamanhos cada vez maiores, seguindo o padrãoV = 1000, 2000, . . . , 10000. Cada rede sempre possuirá 4 clusters com tamanhosiguais. Os clusters gerados nestas redes serão considerados as classes do problema.Para todas as simulações, rotulam-se 2 vértices de cada classe. Quanto à configuraçãodo algoritmo proposto, utilizam-se K = 8 partículas, λ = 0.6, ∆ = 0.07, ωmin = 0 eωmax = 1. Todas as partículas são inicialmente colocadas nos vértices que represen-tam. O algoritmo proposto é executado nesta redes e o tempo necessário para atingirum estado N(t), tal que suas entradas passem a ser insignificantes, é inspecionado.O tempo é quantificado em um processador Intel Core 2 CPU 6700 com 4GB of RAM.Os resultados são mostrados na Figura 4.4. Uma análise de tal figura revela que otempo cresce linearmente com o aumento do tamanho das redes geradas, confirmandoa análise teórica realizada anteriormente.

4.2 Análise Matemática do Modelo Competitivo

Nesta seção, serão fornecidos: (i) uma análise matemática detalhada do modeloproposto, (ii) um exemplo numérico mostrando o uso prático dessa análise, e (iii) umavalidação dos resultados teóricos obtidos. Para todos os efeitos, considera-se a análisede grafos não direcionados.

4.2.1 Resultados Teóricos

Primeiramente, é de extrema valia determinar a função probabilística de transiçãodo sistema φ, i.e., P(X(t + 1) | X(t)), antes que qualquer análise rigorosa seja condu-zida. Por questões de clareza, será simplificada a notação do estado interno sistema,observando que P(X(t)) = P(N(t), p(t), E(t), S(t)). De fato, a derivação algébricadetalhada da probabilidade de transição P(X(t + 1) | X(t)) é dada a seguir:


2000 4000 6000 8000 100000

50

100

150

200

125

150

175

200

225

250

Tamanho da Rede [V]

Tem

po d

e P

roce

ssam

ento

[s]

Figura 4.4: Tempo consumido para que N(t) se estabilize. Cada ponto na curva é uma médiade 10 realizações independentes. As barras verticais de erro representam o maior e menortempos de processamento.

P(X(t + 1) | X(t)) = P(N(t + 1), p(t + 1), E(t + 1), S(t + 1) | N(t), p(t), E(t), S(t))

= P(S(t + 1) | N(t + 1), p(t + 1), E(t + 1), N(t), p(t), E(t), S(t))

× P(N(t + 1), p(t + 1), E(t + 1) | N(t), p(t), E(t), S(t))

= PS(t+1)P(E(t + 1) | N(t + 1), p(t + 1), N(t), p(t), E(t), S(t))

× P(N(t + 1), p(t + 1) | N(t), p(t), E(t), S(t))

= PS(t+1)PE(t+1)P(N(t + 1) | p(t + 1), N(t), p(t), E(t), S(t))

× P(p(t + 1) | N(t), p(t), E(t), S(t))

= PS(t+1)PE(t+1)PN(t+1)Pp(t+1),

(4.26)

onde PS(t+1) = P(S(t + 1) | N(t + 1), p(t + 1), E(t + 1), X(t)), PE(t+1) = P(E(t + 1) |N(t+ 1), p(t+ 1), X(t)), PN(t+1) = P(N(t+ 1) | p(t+ 1), X(t)) e Pp(t+1) = P(p(t+ 1) |X(t)). Agora, é vital proceder para a determinação dos quatro termos que aparecemao fim da Equação (4.26).

Como primeiro termo a analisar, toma-se Pp(t+1). Notando que, para ganhar co-nhecimento sobre p(t + 1), apenas é necessário o conhecimento de p(t) e N(t), e estasduas últimas quantidades fazem parte de X(t) que, por hipótese, é dado, é válido con-cluir que a função de transição do conjunto de partículas para um estado futuro darede, denotado, por Pp(t+1), é de fato a matriz de transição indicada na Equação (4.1).Matematicamente, a seguinte equivalência vale:

4.2 - Análise Matemática do Modelo Competitivo 69

Pp(t+1) = P(p(t + 1) | X(t)) = Ptrans(N(t), p(t)). (4.27)

Neste momento, foi utilizada a notação Ptrans(N(t), p(t)) para enfatizar a depen-dência que a matriz de transição tem, no ato de sua construção, de N(t) e, no ato desua manipulação, de p(t) na sua forma escalar.

Procede-se, agora, para a avaliação de PN(t+1). Neste caso, tem-se uma informaçãoadicional em relação ao caso anterior, a qual é, além do estado anterior do sistema X(t),o conhecimento sobre p(t + 1). Uma rápida análise da regra de atualização de N(t),que é revelada pela primeira expressão do sistema φ, mostra que é possível completa-mente determinar N(t + 1), uma vez que p(t + 1) e N(t) são conhecidos por hipótese.Em função disso, a seguinte equação vale:

PN(t+1) = P(N(t + 1) | p(t + 1), X(t))

= 1N(t+1)=N(t)+QN(p(t+1)),(4.28)

onde QN(p(t + 1)) é uma matriz com dim(QN) = V × K e com dependência em p(t +1), cuja expressão é dada por:

QN(p(t + 1)) =

1p(1)(t+1)=1 · · · 1p(K)(t+1)=11p(1)(t+1)=2 · · · 1p(K)(t+1)=2

... . . . ...1p(1)(t+1)=V · · · 1p(K)(t+1)=V

. (4.29)

O argumento na função indicadora mostrado na Equação (4.28) é, essencialmente, aprimeira expressão do sistema φ, mas em uma notação matricial. Em termos sucintos,a Equação (4.28) resultará em 1 se o cômputo de N(t+ 1) estiver correto, dados p(t+ 1)e N(t), i.e., a matriz N(t + 1) resultante está em consonância com as regras do sistemadinâmico; e 0, caso contrário.

Para o terceiro termo, PE(t+1), tem-se conhecimento sobre o estado anterior do sis-tema, X(t), bem como de p(t+ 1) e N(t+ 1). Por intermédio da Equação (4.7), verifica-se que N(t + 1) pode ser diretamente calculado de N(t + 1), i.e., tendo conhecimentode N(t + 1) permite a obtenção de N(t + 1) de forma determinística. Em termos pro-babilísticos, portanto, a matriz N(t + 1) é considerada como informação dada. À luzdisso, e analisando a Equação (4.13), averigua-se que E(t + 1) pode ser calculado seexistir informação sobre E(t), p(t + 1) e N(t + 1), quantidades as quais são, de fato,conhecidas. Em razão disso, PE(t+1) pode ser completamente determinado e, analoga-


mente ao cálculo de PN(t+1), é dado por:

PE(t+1) = P(E(t + 1) | N(t + 1), p(t + 1), X(t))

= 1E(t+1)=E(t)+∆×QE(p(t+1),N(t+1)),(4.30)

onde QE (p(t + 1), N(t + 1)) é uma matriz com dim(QE) = 1× K e com dependênciaem N(t + 1) e p(t + 1). A k-ésima entrada, k ∈ K, de tal matriz é expressa por:

Q(k)E (p(t + 1), N(t + 1)) = 1proprietario(k,t+1) − 1proprietario(k,t+1). (4.31)

Observe que o argumento na função indicadora na Equação (4.31) é, essencial-mente, a Equação (4.13) em uma forma compacta matricial. Foram utilizadas funçõesindicadoras para descrever os dois comportamentos que essa variável aleatória podemostrar: incremento ou decremento, de acordo com o proprietário do vértice que umapartícula específica está visitando. Supondo que a partícula k ∈ K esteja visitando umvértice cuja proprietária é a mesma partícula, então apenas a primeira função indica-dora da Equação (4.31) é ativada, produzindo Q(k)

E (p(t + 1), N(t + 1)) = 1. Similar-mente, se a partícula k está visitando um vértice de propriedade de partícula adversa,então a segunda função indicadora será ativada, resultando Q(k)

E (p(t + 1), N(t + 1)) =−1. Esse comportamento, em conjunto com a Equação (4.30), é exatamente a expressãodada pela Equação (4.13), porém em forma matricial.

Em derradeiro, para o quarto e último termo, PS(t+1), existem mais informaçõesdadas em relação aos três termos anteriores. Especificamente, neste caso, E(t + 1),N(t + 1), p(t + 1), e o estado anterior do sistema, X(t), são dados. Avaliando a Equa-ção (4.14), verifica-se que o cálculo da k-ésima entrada de S(t + 1) é completamentecaracterizado uma vez que seja conhecido o vetor estocástico E(t + 1). Logo, pode-secompletamente determinar PS(t+1), similarmente aos dois casos anteriores. Matemati-camente, tem-se que:

PS(t+1) = P(S(t + 1) | E(t + 1), N(t + 1), p(t + 1), X(t))

= 1S(t+1)=QS(E(t+1)), (4.32)

onde QS(E(t+ 1)) é uma matriz com dim(QS) = 1×K e com dependência em E(t+ 1).A k-ésima entrada, k ∈ K, de tal matriz é calculada a partir da seguinte equação:

Q(k)S (E(t + 1)) = 1E(k)(t+1)=ωmin. (4.33)


Substituindo as Equações (4.27), (4.28), (4.30) e (4.32) na Equação (4.26), encontra-sea função probabilística de transição do sistema dinâmico competitivo adaptado para oaprendizado semissupervisionado dada por:

P(X(t + 1) | X(t)) = 1N(t+1)=N(t)+QN(p(t+1))1S(t+1)=QS(E(t+1))

× 1E(t+1)=E(t)+∆QE(p(t+1),N(t+1))Ptrans(N(t), p(t))

= 1Conformidade(t)Ptrans(N(t), p(t)),

(4.34)

onde Conformidade(t) é uma expressão lógica dada por:

Conformidade(t) = [N(t + 1) = N(t) + QN(p(t + 1))]

∧ [S(t + 1) = QS(E(t + 1))] ∧ [E(t + 1) =

E(t) + ∆QE(p(t + 1), N(t + 1))] ,

(4.35)

i.e., Conformidade(t) engloba todas as regras que devem ser satisfeitas para que cadauma das funções indicadores na Equação (4.34) sejam ativadas, i.e., resultem em 1.Se todos os valores fornecidos à Equação (4.34) estiverem em conformidade com adinâmica do sistema, então Conformidade(t) = verdadeiro; caso contrário, se houverpelo menos uma medida que não segue as regras do sistema, então, a partir da Equação(4.35), a cadeia de “E” lógicos produzirá falso, logo, Conformidade(t) = falso e afunção indicadora 1Conformidade(t) na Equação (4.34) fornecerá 0, resultando em umaprobabilidade de transição nula.

Com o intuito de obter N(t) quando t → ∞, o cálculo da distribuição conjunta detodos os estados do sistema, X(0), . . . , X(t) será útil. Essa distribuição conjunta é dadapor:

P(X(0), . . . , X(t)) = P(X(t) | X(0), . . . , X(t− 1))P(X(0), . . . , X(t− 1)), (4.36)

Aplicando o teorema de Bayes sucessivas vezes, como mostrado apenas uma vezna Equação (4.36), chega-se a:

P(X(0), . . . , X(t)) = P(X(t) | X(0), . . . , X(t− 1))

× P(X(t− 1) | X(0), . . . , X(t− 2))

× . . .× P(X(1) | X(0))P(X(0)),

(4.37)

A seguir, é mostrada uma prova que o sistema φ é Markoviano. Esta prova será


utilizada para simplificar a Equação (4.37).

Proposição 1. X(t) : t ≥ 0 é um processo Markoviano.

Demonstração. Nesta prova, procura-se concluir que o sistema φ é completamente ca-racterizado por apenas o conhecimento do estado presente do sistema dinâmico, i.e.,tal sistema independe de todos os estados passados (Çinlar, 1975). Com isto em mente,a expressão probabilística para realizar uma transição a um evento específico Xt+1 (umconjunto possível de vértices a ser visitado na próxima iteração) no tempo t + 1, dadatoda a história da trajetória do sistema, satisfaz:

P (X(t + 1) ∈ Xt+1 | X(t), . . . , X(0)) =

P

pt+1 :

fN(N(t), pt+1)

fE(N(t + 1), pt+1)

fS(E(t + 1))

∈ Xt+1 | X(t), . . . , X(0)

.(4.38)

Uma vez estabelecido o valor de pt+1, o qual deve respeitar a distribuição proba-bilística dada pela linha correspondente a forma escalar de p(t) da matriz que com-porta todas as partículas, Ptrans(N(t)), é possível determinar N(t + 1), o qual, por suavez, permite calcular E(t + 1). Essa informação, por último, é suficiente para calcularS(t + 1). Logo, note que o cálculo do estado presente não pode ser obtido de formaconcorrente. Desta forma, este cálculo deve ser realizado de forma ordenada até a ob-tenção do estado interno inteiro, X(t). Mais ainda, como já foi estudado anteriormente,pt+1 é independente do passado, em virtude de apenas necessitar de N(t) e p(t) para,de forma probabilística, determinar a distribuição para o estado subsequente imediato.Usando esse fato, tem-se que:

P

pt+1 :

fN(N(t), pt+1)

fE(N(t + 1), pt+1)

fS(E(t + 1))

∈ Xt+1 | X(t), . . . , X(0)

=

P

pt+1 :

fN(N(t), pt+1)

fE(N(t + 1), pt+1)

fS(E(t + 1))

∈ Xt+1 | X(t)

=

P (X(t + 1) ∈ Xt+1 | X(t)) . (4.39)

Finalmente, em vista da Equação (4.39), X(t) : t ≥ 0 é um processo Markoviano,uma vez que apenas depende do estado presente para completamente especificar opróximo estado.


Aplicando o fato provado na Proposição 1 à Equação (4.37), tem-se:

P(X(0), . . . , X(t)) = P(X(t) | X(t− 1))P(X(t− 1) | X(t− 2))

× . . .× P(X(1) | X(0))P(X(0)). (4.40)

Utilizando a função probabilística de transição que rege o sistema φ, tal como indi-cada na Equação (4.34), a cada termo deslocado na Equação (4.40), obtém-se:

P(X(0), . . . , X(t)) = P(X(0))t−1

∏u=1

[1Conformidade(u)Ptrans(N(u), p(u))

], (4.41)

onde P(X(0)) = P(N(0), p(0), E(0), S(0)). Porém, o principal interesse dessa aná-lise é de obter a distribuição marginal N(t) quando t → ∞. Tal quantidade podeser recuperada a partir da distribuição conjunta calculada na Equação (4.41), fazendoa soma de todas as variáveis aleatórias sem relevância em todo o seu domínio, i.e.,N(t− 1), . . . , N(0), p(t), . . . , p(0), E(t), . . . , E(0), S(t), . . . , S(0). Seguindo essa estraté-gia para obter N(t), é essencial estudar os limites inferior e superior de N(t) para um tarbitrário, uma vez que o domínio de cada entrada da matriz N(t) é [1, ∞). Com esseestudo, espera-se encontrar limites superiores atingíveis para um determinado tempot. Desta forma, valores que excedam esses limites são garantidos de ocorrerem comprobabilidade nula; logo, tal análise será responsável por podar uma grande quanti-dade de valores impraticáveis. Mais importante, a somatória sobre todos os valoresindesejados N(0), . . . , N(t − 1) será matematicamente assegurada de sempre existir,tendo em vista que existirão um número finito de termos na somatória, todos os quaislimitados por um majorante finito, como será visto. Esse majorante é definido peloLema 1, portanto, a convergência é garantida. Tal Lema é provado a seguir.

Lema 1. O maior valor que uma entrada arbitrária de N(t) pode tomar, diga-se N(k)i (t), dado

que i representa um vértice não rotulado, é expresso por:

N(k)imax

(t) =

⌈t+1

2

⌉+ 1, se t > 0 e aii = 0

t + 2, se t > 0 e aii > 0. (4.42)

Demonstração. É necessário descrever a trajetória da partícula k que oferece o maioraumento de N(k)

i (t). Ora, para tanto, supõe-se que a partícula k é prontamente geradano vértice i, caso contrário, o valor máximo teórico não seria atingido. Por questões declareza, considere dois casos específicos: (i) redes sem autolaços (self-loops) e (ii) redes


Figura 4.5: Uma rede construída para ilustrar a trajetória que uma partícula deve percorrerpara aumentar uma entrada arbitrária de N(t) o mais rápido possível. (a) Rede sem autolaços;(b) rede com autolaços.

com autolaços.

Para o primeiro caso, tem-se que ∀i ∈ V : aii = 0. Por hipótese, a partícula k começano vértice i no tempo 0 (como ilustração, considere o vértice 1 na Figura 4.5a). A formamais rápida de aumentar N(k)

i (t) ocorre quando a partícula k visita um vizinho dovértice i, e.g., vértices 2 ou 3 na Figura 4.5a, e imediatamente retorna para o vértice i(vértice 1 na Figura 4.5a). Repetindo-se esta trajetória até o instante t, espera-se queo maior valor de N(k)

i (t) seja exatamente o exposto na primeira expressão da Equação(4.42).

Para o segundo caso, ∃i ∈ V : aii > 0. Considere que a partícula k comece exata-mente nesse vértice i com autolaço. Fica claro que a forma de aumentar N(k)

i (t) maisrapidamente é sempre revisitar i pela aresta de autolaço (veja a Figura 4.5b). Em vistadisso, o maior valor que N(k)

i (t), para um t arbitrário, pode tomar é exatamente aquelemostrado na segunda expressão da Equação (4.42). O fator “+2” ocorre em razão dapartícula inicialmente ser gerada no vértice i, de acordo com a segunda expressão naEquação (4.23).

O Lema 1 não fornece informação sobre o limite máximo no caso de o vértice serpré-rotulado. No entanto, esta informação pode ser trivialmente obtida pelas condi-ções iniciais do sistema. Considere que i seja um vértice pré-rotulado e k seja a suapartícula representante, então, com o auxílio da primeira expressão na Equação (4.23),verifica-se que N(k)

i (t) = ∞, ∀t ≥ 0. Por conseguinte, esse valor permanece fixo du-rante toda a evolução do sistema dinâmico. Assim, tais vértices simplesmente sãofixados para um valor ∞, ou seja, são considerados constantes já que este valor sempreocorre com probabilidade 1 no ato do cômputo da distribuição marginal N(t).

Em relação ao limite superior de uma entrada arbitrária de E(t), por exemplo,E(k)(t), sabe-se que existe um limite superior finito, no caso, E(k)(t)max = ωmax. Logo,desde que ωmax < ∞, o limite superior da entrada E(k)(t) é sempre bem definido. En-tretanto, esta entrada não aceita apenas valores inteiros entre o intervalo [ωmin, ωmax].


Portanto, tal análise matemática sobre essa variável deve ser feita com cuidado. OLema 2 fornece um resultado para auxiliar na resolução deste detalhe.

Lema 2. O domínio atingível por uma entrada arbitrária de E(t), diga-se E(k)(t), ∀t ∈ N,denotado aqui por DE, é dado por:

DE ,

ωmin +ωmax −ωmin

K+ n∆, n = −bnic, . . . , bnmc

∪

ωmin + n∆, n =

1, 2, . . . ,

⌊ωmax −ωmin

∆

⌋∪

ωmax − n∆, n =

1, 2, . . . ,

⌊ωmax −ωmin

∆

⌋,

(4.43)

onde ni =ωmax−ωmin

K∆ ≥ 0 e nm = ωmax−ωmin∆

(1− 1

K

)≥ 0.

Demonstração. Esta prova é dividida em três partes, as quais são definidas pelos trêsconjuntos que aparecem na expressão do caput desse Lema.

O primeiro conjunto é responsável por fornecer os valores que são múltiplos de∆ tendo como offset a condição inicial de E(k)(0), i.e., E(k)(0) = ωmin +

(ωmax−ωminK

),

tal como a Equação (4.24) revela. O mínimo valor atingível de E(k)(0) é dado quandon = ni, o qual é calculado por:

ni =

(ωmin +

ωmax−ωminK

)−ωmin

∆=

ωmax −ωmin

K∆, (4.44)

enquanto que o maior valor atingível ocorre quando n = nm é satisfeito, i.e.:

nm =ωmax −

(ωmin +

ωmax−ωminK

)∆

=ωmax −ωmin

∆

(1− 1

K

). (4.45)

Depois de transcorrido um tempo, a partícula k poderá atingir um dos dois possí-veis extremos de energia permitidos: ωmin or ωmax. Em razão do operador max(.) naEquação (4.13), é necessário listar também todos os números múltiplos de ∆ partindo-se desses dois offsets: ωmin or ωmax. O segundo conjunto no caput desse lema precisa-mente fornece estes múltiplos quando o offset é tomado a partir de ωmin e o terceiroconjunto, quando é tomado ωmax. Uma vez atingido um desses dois últimos conjun-tos, a partícula não mais sai deles, i.e., o primeiro conjunto fica inatingível. Portanto,todos os valores de E(k)(t) foram apropriadamente mapeados.

Por último, o limite superior de uma entrada arbitrária é S(t) é 1, já que os valoresque esta variável pode tomar são 0, 1. À luz das análises realizadas até então, a


distribuição marginal de P(N(t)) é dada por:

P(N(t)) =V

∑p(1)(0)=1

V

∑p(2)(0)=1

. . .V

∑p(K)(0)=1

. . .V

∑p(K)(t)=1

×g(0,1)

∑N(1)

1 (0)=1

g(0,1)

∑N(2)

1 (0)=1

. . .g(0,V)

∑N(K)

V (0)=1

. . .g(t−1,V)

∑N(K)

V (t−1)=1

× ∑i(1)(0)∈DE

∑i(2)(0)∈DE

. . . ∑i(K)(0)∈DE

. . . ∑i(K)(t)∈DE

×1

∑S(1)(0)=0

1

∑S(2)(0)=0

. . .1

∑S(K)(0)=0

. . .1

∑E(K)(t)=0

P(X(0))t−1

∏u=1

[1Conformidade(u)Ptrans(N(u), p(u))

], (4.46)

onde g(t, i) é uma função por partes que indica o valor máximo de N(t) no instante tpara um vértice i qualquer. Sua definição é diretamente feita por intermédio do Lema1:

g(t, i) =

⌈t+1

2

⌉+ 1, se aii = 0

t + 2, se aii > 0. (4.47)

Os somatórios na primeira linha da Equação (4.46) são responsáveis por passar portodos os valores possíveis dos vetores estocásticos p(0), . . . , p(t). Os somatórios da se-gunda linha, por sua vez, passam por todos os valores atingíveis de N(0), . . . , N(t− 1).Cumpre relembrar que os índices das partículas representativas aos seus respectivosvértices que representam devem ser fixados em ∞, i.e., são tratados como “constantes”e, portanto, não aparecem no somatório. A terceira linha fornece os somatórios quepassam por todos os valores possíveis de E(0), . . . , E(t), vetores estocásticos os quaisconstituem um caso especial em relação aos demais, uma vez que os valores toma-dos por estes podem ser não inteiros. Com o propósito de corretamente quantificaressas variáveis, utiliza-se o conjunto DE definido no caput do Lema 2. Por último, aquarta linha indica os somatórios responsáveis por varrer todos os valores possíveisde S(0), . . . , S(t). Observe que a expressão lógica Conformidade(u) e a matriz de tran-sição dentro do produtório são construídas a partir de todos esses índices anteriores.Adicionalmente, sabe-se que P(X(0)) = P(N(0), p(0), E(0), S(0)), de tal forma que acondição inicial do sistema poderia ser uma distribuição também, i.e., o modelo mate-mático apresentado também suporta incerteza sobre a distribuição inicial das partícu-las.


Uma análise rápida e imprecisa poderia indevidamente levar a conclusão que ocálculo de P(N(t)) é direto, uma vez que todos os P(N(t)) sejam calculados a partirda Equação (4.46), i.e., poderia-se aplicar a Equação (4.5) diretamente para resolvero mapeamento N(t) 7→ N(t). Esta hipótese está incorreta pela simples razão que,geralmente, há mais de 1 distinta matriz N(t) que pode levar ao mesmo valor da ma-triz N(t). Por exemplo, considere hipoteticamente um problema com 3 partículas e2 vértices. Suponha que, no instante t, existam duas configurações, geradas por doisprocessos distintos, para a matriz N(t), a seguir:

N(t) =

[1 1 11 2 3

],

N′(t) =

[2 2 22 4 6

].

(4.48)

Então, as configurações mostradas na Equação (4.48), em conjunto com a Equação(4.7), levariam à conclusão que as duas matrizes produzem o mesmo N(t) dado por:

N(t) =

[1/3 1/3 1/3

1/6 1/3 1/2

]. (4.49)

Em vista disso, o mapeamento N(t) 7→ N(t) não é injetivo e, portanto, não inversí-vel. O resultado derivado do cenário anterior sugere que múltiplos inteiros positivosde N(t) compõem o mesmo N(t). De fato, é exatamente isto que ocorre. Antes de con-tinuar a dedução do cálculo de P(N(t)) a partir P(N(t)), o Lema a seguir apresentaalguns resultados importantes.

Lema 3. Dado qualquer vértice i não rotulado, as seguintes asserções valem para o tempo t:(a) O mínimo valor que uma entrada arbitrária de N(t) pode atingir, diga-se N(k)

i (t), sa-tisfaz:

N(k)imin

(t) =1

1 + ∑u∈K \ k g(t, u)(4.50)

(b) O maior valor que uma entrada arbitrária de N(t) pode atingir, diga-se N(k)i (t), satisfaz:

N(k)imax

(t) =g(t, i)

g(t, i) + (K− 1)(4.51)

Demonstração. (a) Por hipótese, o vértice i não é rotulado. O menor valor, segundo aEquação (4.7), ocorre quando três condições são satisfeitas: (i) a partícula k não é ini-cialmente gerada no vértice i; (ii) a partícula k nunca visita o vértice i; e (iii) todas as


outras K − 1 partículas u ∈ K \ k visitam o vértice i da maneira mais rápida pos-sível, i.e., seguindo o Lema 1. Assim, tal vértice será visitado ∑u∈K \ k g(t, u) vezespelas outras partículas. Porém, tendo em vista a inicialização de N(0) mostrada na se-gunda expressão da Equação (4.23), deve-se adicionar 1 ao total de visitas, em funçãoda existência da partícula k. Em virtude disso, é esperado que o total de visitas seja1 + ∑u∈K \ k g(t, u). Como a partícula k só visitou uma vez o vértice i, em consonân-cia à Equação (4.7), chega-se à Equação (4.50).

(b) Por hipótese, o vértice i não é rotulado. O maior valor ocorre quando as se-guintes condições são satisfeitas: (i) a partícula k é gerada no vértice i; (ii) a partículak visita i do jeito mais rápido possível, i.e., seguindo a expressão no Lema 1; e (iii) asoutras partículas u ∈ K \ k nunca visitam o vértice i. Desta forma, espera-se queg(t, i) + (K− 1) visitas sejam feitas ao vértice i, sendo que o segundo termo é devido àinicialização de N(0) conforme a segunda expressão indicada na Equação (4.23) paraas K − 1 partículas restantes. Esta informação, em conjunto com a Equação (4.7), im-plica a Equação (4.51).

Observação 2. Se o grafo não contiver autolaços, a Equação (4.50) reduz-se a:

N(k)imin

(t) =1

1 + (K− 1)g(t, i). (4.52)

O Lema seguinte fornece subsídios para determinar todos os elementos que inte-gram as entradas da matriz N(t), entre os limites assegurados pelo Lema 3.

Lema 4. Considere as frações irredutíveis denotadas da seguinte forma num/den. O domínioatingível de qualquer entrada de N(t), diga-se N(k)

i (t), é denotado por I . Tal conjunto contémtodos os valores que são satisfeitos pelas seguintes condições:(i) Em relação aos vértices não rotulados:

(a) A menor fração irredutível é dada pela expressão na Equação (4.50).

(b) A maior fração irredutível é dada pela expressão na Equação (4.51).

(c) As frações irredutíveis no intervalo satisfazendo aos itens (a) e (b) no caput desse Lematêm a forma:

I. num, den ∈ N∗.

II. num ≤ g(t, i)

III. den ≤ ∑u∈K g(t, u)

(ii) Em relação aos vértices pré-rotulados:


(a) Sempre será 0, caso a partícula k não represente o vértice i.

(b) Sempre será 1, caso a partícula k represente o vértice i.

Demonstração. A primeira parte dessa prova é relativa ao item (i) do caput.(a) e (b) Diretos a partir do Lema 3.(c) Para o inciso I, lembrando que a entrada N(k)

i (t) admite apenas valores inteirose, tendo em vista que N(k)

i (t) é calculado a partir da Equação (4.7), i.e., é uma razãode números inteiros, segue que o numerador e denominador das frações irredutíveissempre serão inteiros, logo o inciso I está demonstrado. Para o inciso I I, vale lembrarque o maior número de visitas que um vértice pode receber é dado de acordo com oLema 1. Com isso em mente e vendo que o numerador da fração irredutível, conformeindicado na Equação (4.7), só contabiliza o número de visitas feita por uma partículaa um vértice, segue que o majorante do numerador é dado por g(t, i) e o inciso I Iestá provado. Para o inciso I I I, aplica-se a mesma ideia que a anterior, porém deveser levado em consideração que no denominador aparece a soma de visitas feitas portodas as partículas ao vértice i no instante t, conforme a Equação (4.7) mostra. Assim,o majorante do denominador está demonstrado.

A segunda parte é relativa ao item (ii) do caput.(a) Por hipótese, a partícula k não é representante do vértice i. Como o vértice i

é rotulado, ∃u ∈ K : N(u)i (t) = ∞. Em vista das Equações (4.7) e (4.23), obtém-se

N(k)i (t) = 0.

(b) Por hipótese, a partícula k é representante do vértice i. Ora, pelas Equações (4.7)e (4.23), obtém-se N(k)

i (t) = 1.

Uma outra característica interessante do conjunto I é dada no Lema a seguir.

Lema 5. Dado um instante t ≤ ∞, o conjunto I indicado no Lema 4 é sempre finito.

Demonstração. Para mostrar esse lema, basta verificar que cada item apresentado nocaput do Lema 4 é finito.

Quanto ao item (i): (a) e (b) são escalares, logo, trata-se de conjuntos de um ele-mento, que, por definição, são sempre finitos. (c) O inciso I indica um ínfimo tantopara o numerador quanto para o denominador. Os incisos I I e I I I revelam um ma-jorante para o numerador e denominador, respectivamente. Também pelo inciso I,verifica-se que o intervalo entre o ínfimo e majorante é discreto. Segue, portanto, que,com certeza, o número de frações irredutíveis construídas a partir desses valores tam-bém será discreto.

Quanto ao item (ii): (a) e (b) são escalares, logo constituem um conjunto finito.Como todos os itens acima analisados têm um número finito elementos, e tendo em

vista que I é a união de todos estes conjuntos, segue que o mesmo é finito.


O Lema 4 fornece o domínio atingível de I para um entrada específica de N(t),diga-se N(k)

i (t). A seguir, essa ideia é simplesmente estendida para o espaço geradopelas matrizes N(t), i.e., restringe-se cada entrada da matriz em apreço a pertencer a I .Matematicamente, o conjunto de valores gerados nesse espaço será denominado M,i.e.:

M , N : N(k)i ∈ I , ∀(i, k) ∈ S. (4.53)

Em função das considerações anteriores, a distribuição N(t) para um t arbitrário édada por:

P(

N(t) = U : U ∈ M)=

t

∑u=1

P(

L = uN(t) : L = U), (4.54)

onde o limite superior do somatório mostrado na Equação (4.54) é tomado usandouma abordagem conservativa. De fato, a probabilidade que eventos, tais como qual-quer entrada N(t) superar g(t, i), ocorram é nula. Em virtude disso, é plausível pararo somatório tão logo que qualquer entrada da matriz uN(t) exceda esse máximo atin-gível, para um u > 0. Esta observação foi omitida da Equação (4.54) por questões declareza.

Conforme t → ∞, é esperado que a Equação (4.54) revele as classes de cada vér-tice, a partir do nível de dominação aplicado pelas partículas de uma maneira fuzzy.Tal classificação é feita verificando o rótulo da partícula que impõe o maior nível dedominação a cada um dos vértices não rotulados.

4.2.2 Um Exemplo Numérico

Para fins de clareza, nesta seção, será aplicado os resultados teóricos derivados naseção anterior a uma rede simples. Com propósito ilustrativo, apenas uma iteraçãodo sistema será analisada, especificamente, a transição de t = 0 para t = 1. Consi-dere o simples exemplo composto por uma rede regular de 3 vértices, idêntica àquelamostrada na Figura 4.5a. Nesta rede, considere que o vértice v1 seja pré-rotulado comosendo pertencente à classe 1 e o vértice v2, à classe 2, i.e., V = v1, v2, v3, VL = v1, v2e C = 1, 2. Claramente, o vértice v3 possui características de sobreposição entre asclasses 1 e 2. Agora, será teoricamente mostrado este comportamento nesta seção. Su-ponha a seguinte configuração arbitrária: K = 2 partículas são inseridas na rede, i.e.,K = 1, 2, em que a partícula 1 representa o vértice v1 (i.e., ela propagará o rótulo dovértice v1) e a partícula 2, o vértice v2, i.e., L = (v1, 1), (v2, 2). Considere tambémque exista certeza sobre a localização das partículas no instante t = 0, cuja distribuição


satisfaz à expressão:

P

N(0) =

∞ 11 ∞1 1

, p(0) = [v1 v2] , E(0), S(0)

= 1, (4.55)

i.e., existe 100% de certeza que as partículas 1 e 2 serão geradas nos vértices v1 e v2,respectivamente, no tempo t = 0. Observe que N(0), E(0) e S(0) foram escolhidos como fim de satisfazer às Equações (4.23), (4.24) e (4.25), respectivamente; caso contrário, aprobabilidade valeria 0, em vista da Equação (4.34).

A partir da Figura 4.5a, é fácil deduzir a matriz de adjacência A do grafo e, por-tanto, determinar a matriz associada à movimentação aleatória para uma partícula(lembrando que essa matriz é idêntica a todas as partículas). Então, aplicando a Equa-ção (4.2) à matriz de adjacência A, resulta em:

Paleat =

0 0.50 0.500.50 0 0.500.50 0.50 0

. (4.56)

Dado N(0), pode-se prontamente estabelecer o valor da matriz N(0) por intermé-dio da Equação (4.7):

N(0) =

1 00 1

0.50 0.50

. (4.57)

Usando a Equação (4.8), pode-se calcular as matrizes associadas à movimentaçãopreferencial das partículas a seguir:

P(1)pref(0) =

0 0 10.67 0 0.33

1 0 0

, (4.58)

P(2)pref(0) =

0 0.67 0.330 0 10 1 0

. (4.59)

Com o propósito de simplificar os cálculos, seja λ = 1, de tal forma que a Equação(4.1) reduz-se a Ptrans(0) = P

(1)pref(0)⊗P

(2)pref(0), pois as partículas estão ativas. Tal ma-


triz possui dimensões 9× 9. Ao invés de construir esta matriz, utiliza-se a Observação1 para montar p(1) com uma coleção de 2 matrizes 3 × 3, tais como mostradas nasEquações (4.58) e (4.59). Observe que, no caso especial em que λ = 1, a matriz de tran-sição das partículas simplifica-se para somente a matriz de movimentação preferencialde cada partícula, dado que as partículas estejam ativas. Para a primeira partícula,verifica-se com o auxílio da Equação (4.58) que, começando do vértice v1 (linha 1), so-mente existe um vértice possível para a partícula visitar, no caso, o vértice v3. Para asegunda partícula, o mesmo raciocínio pode ser utilizado para chegar à conclusão queo vértice v3 também é o único possível de ser visitado. Com isto em mente,

P

N(1) =

∞ 11 ∞2 2

, p(1) = [v3 v3] , E(1), S(1) | X(0)

= 1, (4.60)

onde X(0) é dado pela Equação (4.55). Além disso, como foi fixado λ = 1, é esperadoque a transição das partículas seja altamente dependente em relação aos níveis de do-minação impostos sobre os vértices da rede. Logo, dado que os vértices pré-rotuladosconstituem forças extremamente repulsivas que agem contra partículas rivais, o com-portamento preferencial dessas partículas não irá se aventurar sobre estes tipos de vér-tices. Isto serve como uma explicação natural de o estado p(1) = [v3 v3] ser o únicoestado atingível na próxima iteração do sistema competitivo.

Antes de realizar o cômputo da distribuição marginal P(N(1)), é necessário fixarum limite superior para um entrada arbitrária de um vértice não rotulado da matrizN(1). Tal quantidade pode ser prontamente avaliada a partir da Equação (4.42). Apli-cando a referida equação, obtém-se g(1, i) = N(k)

imax(1) = 2, ∀i ∈ V , implicando que só

é necessário tomar as combinações numéricas da matriz N(1) tal que cada entrada damesma deve figurar entre os valores 1, 2, uma vez que, segundo o Lema 1, valoresmaiores ocorrem com probabilidade nula. Adicionalmente, deve-se iterar o sistemasobre os valores atingíveis de E(0) e E(1). Para tanto, fixa-se, para efeitos didáticos,∆ = 0.25, ωmin = 0 e ωmax = 1. Com isso, é possível utilizar o Lema 2, produzindoE(t) ∈ 0, 0.25, 0.5, 0.75, 1. Os limites das variáveis do sistema remanescentes, i.e.,S(0) e S(1), são triviais. Nas condições presentes, e tendo em vista os cálculos anteri-ores, tem-se informação suficiente para calcular a distribuição marginal P(N(1)), emconsonância com a Equação (4.46):

P

N(1) =

∞ 11 ∞2 2

= 1× 1 = 1. (4.61)


Como último objetivo, a tarefa é determinar a distribuição P(N(1)). Segundo ospassos especificados na seção anterior, é preciso encontrar todos os elementos atingí-veis para um entrada arbitrária de N(1). Tais elementos comporão o conjunto I . Istosignifica que é apenas necessário considerar entradas da matriz N(t) que contenhamelementos do conjunto I ; os valores remanescentes de N(t) são inatingíveis e, por-tanto, ocorrem com probabilidade nula. Em vista das restrições anteriormente listadas,para calcular I , utilizam-se o Lema 3 e a Observação 2:

N(k)imin

(t) =1

1 + (K− 1)g(t, i)=

11 + (2− 1)2

=13

, (4.62)

N(k)imax

(t) =g(t, i)

g(t, i) + (K− 1)=

22 + (2− 1)

=23

. (4.63)

Assim, pelo Lema 4, tem-se I = 0, 1/3, 1/2, 2/3, 1. É de extrema valia notar queos únicos valores que os vértices 1 e 2 (pré-rotulados) podem tomar são 0, 1 ⊂ I ,como foi visto anteriormente. Observando que há conhecimento sobre a distribuiçãocompleta de N(1), então aplica-se a Equação (4.54) para encontrar P(N(1)) a seguir:

P

N(1) =

1 00 1

0.5 0.5

= 1. (4.64)

Perceba que o mapeamento entre as distribuições N(t) e N(t) não é bijetivo. Nesteexemplo especial elaborado para estudo, não houve N(t) distintos que gerassem omesmo N(t). Mas, conforme t progride no tempo, isto começa a ocorrer com maisfrequência. Este processo mostrado nesta seção é repetido até um t suficientementegrande. Uma análise detalhada do comportamento do sistema que foi derivado sugereque a Equação (4.64) vale para todo t ≥ 1 e as partículas 1 e 2 visitarão o vértice v3

com período 2. Logo, isto prova que o vértice v3 pode pertencer a mais de uma classe(sobreposição).

4.2.3 Validação dos Resultados Teóricos

Nessa seção, será demonstrado que os resultados teóricos apresentados na seçãoanterior aproximam o comportamento empírico do modelo competitivo estocástico,quando executa-se o algoritmo um grande número de vezes independentemente. Ba-seado nisso, será utilizada a rede mostrada na Figura 4.2, i.e., V = v1, . . . , v20. Arbi-trariamente, rotulam-se dois vértices, no caso, v6 com um rótulo vermelho e v18 comum rótulo azul. Colocam-se duas partículas K = 1, 2 na rede, onde a partícula 1 é


inicialmente fixada no vértice v6 e será responsável por propagar o rótulo vermelho, ea partícula 2 é posta no vértice v18, sendo incumbida de propagar o rótulo azul. Paraambas comparações teórica e empírica, convencionam-se λ = 0.6, ∆ = 0.07, ωmin = 0e ωmax = 1.

Para a avaliação empírica, uma vez que o modelo competitivo é estocástico, existea necessidade de estimar o nível de dominação empírico, traduzido pela matriz N(t).Para tanto, o algoritmo será executado 10000 vezes independentemente. Para cadaexecução, o sistema dinâmico é iterado até t = 1000 e a matriz de nível de dominaçãoé armazenada, i.e., N(1000). Agora, uma vez calculadas as 10000 matrizes de nível dedominação, são construídos V × K histogramas, com cada histograma representandouma entrada da matriz N(1000), a qual possui V × K entradas. Cada histograma épopulado segundo o valor N(k)

i (1000),∀(i, k) ∈ S atingido em cada execução do algo-ritmo. Por exemplo, colocam-se todos os níveis de dominação impostos pela partículavermelha no vértice v1, i.e., N(vermelha)

1 (1000), em um único histograma para todas as10000 execuções do algoritmo. Uma vez que o nível de dominação é contínuo no in-tervalo [0− 1], tal intervalo é discretizado usando cestas com largura de 0.01, i.e., 100cestas. No fim, para obtenção de uma distribuição probabilística estimada, cada histo-grama é normalizado.

Em relação ao cálculo teórico do nível de dominação para a rede na Figura 4.2,utiliza-se diretamente a Equação (4.54) para calcular N(1000). Uma vez que não épossível plotar a distribuição probabilística dessa matriz, já que ela está no espaçoV × K + 1, tal distribuição é marginalizada em três vértices específicos, de tal formaque seja possível graficamente demonstrar a distribuição resultante. Este processo érealizado nos vértices v4 (membro da classe vermelha), v11 (vértice na borda das duasclasses) e v16 (membro da classe azul). A Figura 4.6 mostra a distribuição de probabi-lidade estimada empiricamente (curva azul) da matriz de dominação N(1000) nestestrês vértices vértices, bem como a mesma informação para a distribuição teórica obtida(curva vermelha). O gráfico empírico foi interpolado para uma curva contínua paraefeitos ilustrativos. Como pode ser visto a partir da Figura 4.6a, o vértice v4 é quaseintegralmente dominado pela partícula vermelha, uma vez que o nível de dominaçãoimposto por esta partícula aproxima de 1 (e, consequentemente, o nível de dominaçãoimposto pela partícula neste mesmo vértice decai para 0). A Figura 4.6b confirma anatureza de sobreposição entre duas classes para o vértice v11, já que os níveis de do-minação das duas partículas são quase os mesmos. A Figura 4.6c indica que a partículavermelha tem pouca dominação sobre o vértice v16. Estas curvas devem ser interpreta-das da seguinte maneira: toma-se a Figura 4.6a por exemplo. Existe 34% de chance queo nível de dominação que a partícula vermelha imporá ao vértice v4 esteja nas redon-dezas do valor 0.88 (a redondeza é definida pelo tamanho da cesta que, no caso, vale0.01) se o sistema competitivo foi iniciado em t = 0 e parado em t = 1000. Outros valo-


res são possíveis, mas ocorrem mais raramente. Como pode-se visualmente verificar,os resultados teóricos modelam, mesmo que de forma aproximada, o comportamentoempírico das simulações, confirmando, desta forma, a análise teórica conduzida naseção anterior.

0 0.2 0.4 0.6 0.8 10

0.08

0.16

0.24

0.32

0.4

N(vermelha)4 (1000)

Pro

babi

lidad

e

Distribuição TeóricaDistribuição Empírica

(a)

0 0.2 0.4 0.6 0.8 10

0.1

0.2

0.3

0.4

0.5

N(vermelha)11 (1000)

Pro

babi

lidad

e


(b)

0 0.2 0.4 0.6 0.8 10

0.08

0.16

0.24

0.32

0.4

N(vermelha)16 (1000)

Pro

babi

lidad

e


(c)

Figura 4.6: Comparação entre as distribuições teórica e empírica para três vértices distintos: v4,v11 e v16 em relação ao nível de dominação imposto pela partícula vermelha. Pode-se verificarque o nível de dominação mais provável que a partícula vermelha imporá ao vértice v4 seráaproximadamente de 0.88 com 34% de chance, ao vértice v11 será 0.53 com 47% de chance, e aovértice v16 será 0.14 com 33% chance.

4.3 Simulações Computacionais

Nesta seção, resultados experimentais serão conduzidos com o intuito de avaliar aeficácia e qualidade do modelo competitivo proposto. Especificamente, na Subseção4.3.1, será estudada a sensibilidade dos parâmetros do modelo; na Subseção 4.3.2, seráexaminado o comportamento do sistema dinâmico φ por meio de uma simples redeartificial; e na Subseção 4.3.3, resultados em bases de dados reais são mostrados. Nocaso, utiliza-se o benchmark de Chapelle et al. (2006) e várias técnicas representativassemissupervisionadas para efeitos de comparação.

4.3.1 Análise Empírica da Sensibilidade dos Parâmetros do Modelo

Primeiramente, será estudado o comportamento do modelo frente a variações doparâmetro λ, o qual é responsável por contrabalancear a proporção de caminhadasaleatória e preferencial realizadas por todas as partículas no modelo. Para tanto, serãoutilizadas redes clusterizadas aleatórias, cujo método de construção já foi explicadoanteriormente. A Figura 4.7 mostra como a acurácia de classificação do modelo secomporta como uma função de λ de 0 (caminhadas puramente aleatórias) até 1 (cami-nhadas puramente preferenciais). Como pode ser observado pela figura, este parâme-tro é sensível ao resultado final do modelo. Usualmente, a acurácia ótima atingida pelo


modelo ocorre quando uma mistura de caminhadas aleatória e preferencial é escolhida.Especificamente, para 0.5 ≤ λ ≤ 0.8, o modelo gera bons resultados preditivos.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10.3

0.4

0.5

0.6

0.7

0.80.8

λ

Acu

ráci

a

Figura 4.7: Acurácia de classificação vs. λ. Nestas simulações, N = 1000, há 4 comunidadesde mesmo tamanho, 〈k〉 = 16, zout/〈k〉 = 0.4 e ∆ = 0.07. Cada ponto na curva é a média de 100realizações. As barras verticais indicam o desvio padrão.

Outro parâmetro importante que precisa ser estudado é ∆, o qual entra em cena noato de atualização da energia das partículas. Novamente, redes aleatórias clusteriza-das serão empregadas para análisar o comportamento desse parâmetro. A Figura 4.8retrata a acurácia de classificação atingida pelo algoritmo em função de ∆. Pode-se ve-rificar que, para valores intermediários de ∆, no caso, 0.05 < ∆ < 0.4, o modelo não émuito sensível a este parâmetro. Entretanto, conforme ∆ fica maior, o desempenho doalgoritmo começa a ser prejudicado. Isto ocorre porque, para um ∆→ ωmax, fica extre-mamente difícil de uma partícula mudar o proprietário de um vértice anteriormentedominado por outra partícula rival. A razão decorrente disso é que, tão logo uma par-tícula visite um vértice não dominado por ela, sua energia atingirá o patamar mínimoinstantaneamente, fazendo com que ela se torna exausta e volte ao seu território deorigem. Pode-se entender esse processo com um “hard labeling” artificial. Por outrolado, para um ∆→ ωmin, as partículas estarão livres para viajar na rede sem quaisquerpenalidades sobre suas correspondentes energias. Assim, elas raramente se tornarãoexaustas. Em vista disso, todos os vértices da rede estarão em constante competição eas bordas das classes não serão estabelecidas.

Cumpre ressaltar que ωmin e ωmax não precisam ser analisados, já que apenas de-finem um intervalo. A análise de ∆ já incorpora, de forma indireta, a análise dessesdois parâmetros. Por exemplo, suponha que ∆ = 0.25, ωmin = 0 e ωmax = 1. Casofosse desejado que a partícula se tornasse exausta duas vezes mais rapidamente, ape-nas dobraria-se ∆ para 0.5, ao invés de diminuir pela metade ωmax. Em suma, diante

4.3 - Simulações Computacionais 87

da análise realizada, pode-se concluir que ∆ não é um parâmetro muito sensível, umavez que o intervalo que ∆ apresenta bons resultados é bem amplo. Tendo em vista es-sas análises, em todas simulações seguintes, os seguintes parâmetros serão utilizados:∆ = 0.07, ωmin = 0 e ωmax = 1.

0 0.2 0.4 0.6 0.8 10.6

0.62

0.64

0.66

0.68

0.7

0.72

0.74

0.76

∆

Acu

ráci

a

Figura 4.8: Acurácia de classificação vs. λ. Nestas simulações, N = 1000, há 4 comunidadesde mesmo tamanho, 〈k〉 = 16, zout/〈k〉 = 0.4 e λ = 0.6. Cada ponto na curva é a média de 100realizações. As barras verticais indicam o desvio padrão.

4.3.2 Simulações com Bases de Dados Artificiais

Com a intenção de facilitar o entendimento de como a técnica aqui estudada fun-ciona, serão projetadas bases de dados artificiais com apenas duas classes, cada qualcom 50 vértices. K = 2 partículas são inseridas na rede, cada qual representando umaclasse. Com essa base de dados artificial, será observado o comportamento evolucio-nal das partículas proprietárias de cada vértice. A Figura 4.9a indica a configuraçãoinicial da rede, onde os círculos coloridos simbolizam vértices rotulados. Os dadosescuros denotam dados ainda não dominados por nenhuma partícula. A propriedadede cada vértice é dada pela partícula que impõe o maior nível de dominação sobreo mesmo e será didaticamente indicada pelas cores dos vértices (azul ou vermelho).Para esta simulação, será utilizado λ = 0.6. De acordo com a Equação (4.23), os vérti-ces pré-rotulados têm sua propriedade fixada como sendo a partícula a qual o repre-senta. Conforme o sistema dinâmico evolui, as partículas visitam os vértices da redeem consonância com a função probabilística de transição dada na matriz Ptrans(t). AFigura 4.9b mostra como os vértices estão dominados para t = 100, a Figura 4.9c, parat = 200, e a Figura 4.9d revela as partículas proprietárias dos vértices no estado emque já não há mais mudança de dominação entre os vértices, o qual é atingido quando


t = 300. Ainda para a mesma rede, será verificado como o nível de dominação médiodos vértices de uma classe se comporta para as duas partículas no modelo. A Figura4.10a indica o nível de dominação médio imposto pela partícula representando o vér-tice pré-rotulado azul nos vértices v1 ao v50 (classe azul) e v51 ao v100 (classe vermelha),enquanto que a Figura 4.10b exibe a mesma informação para a partícula representandoo vértice pré-rotulado vermelho. Claramente, conforme o tempo progride, pode-se ve-rificar que as duas classes são, de maneira inequívoca, separadas pelo sistema compe-titivo.

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(a)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(b)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(c)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(d)

Figura 4.9: Ilustração de um processo de classificação semissupervisionada via competiçãode partículas. As redes possuem 100 vértices. Vértices escuros ainda não foram dominadospor nenhuma partícula. As cores nos vértices representam a partícula que o está dominando.Retrato da rede quando: (a) t = 0; (b) t = 100; (c) t = 200; e (d) t = 300.

Seguindo com os exemplos artificiais, agora, a técnica de competição de partículaserá aplicada em classes de dados com distribuições arbitrárias. Para tanto, será utili-


300 600 900 1200 1500 1800 2100 2400 2700 30000

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

tempo

N(1

).

(t)

Vertices 1 ao 50Vertices 51 ao 100

(a)

300 600 900 1200 1500 1800 2100 2400 2700 30000

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

tempo

N(2

).

(t)

Vertices 1 ao 50Vertices 51 ao 100

(b)

Figura 4.10: Comportamento evolucional do nível de dominação médio imposto pelas partícu-las no modelo. (a) Nível médio de dominação imposto pela partícula 1; e (b) Mesma informaçãopara a partícula 2.

zado o pacote PRTools (Duin, 2000) que automaticamente gera distribuições não trivi-ais e bem conhecidas na literatura para problemas de classificação. Para todas as simu-lações realizadas com estes tipos de classe, há a necessidade de construção da rede apartir do conjunto de dados de entrada. Neste caso, cada item de dado é representadopor um vértice. Arbitrariamente, será escolhida a técnica k-vizinhos mais próximoscom k = 5, i.e., cada vértice é conectado com os seus 5 vizinhos mais próximos se-gundo uma medida de similaridade, a qual aqui é tomada como sendo a Euclidiana.Para cada 50 vértices gerados, escolhe-se aleatoriamente um entre eles e o pré-rotula.Para cada vértice rotulado, uma partícula representante é gerada. Note que, neste caso,haverá cooperação entre partículas oriundas do mesmo time. Conforme já visto, paraobter o nível de dominação agregado de um time de partículas sobre um vértice, ape-nas somam-se os níveis de dominação de cada partícula constituinte do time sobre omesmo vértice. O primeiro conjunto de dados, como mostrado na Figura 4.11a, con-siste em 600 exemplos igualmente divididos em duas classes com formatos de banana.O resultado é exibido na Figura 4.11b. A segunda base de dados, a qual pode ser vistana Figura 4.11c, é composta de 600 exemplos igualmente divididos em duas classesHighleyman. O resultado correspondente é fornecido na Figura 4.11d. A terceira basede dados, como retratada na Figura 4.11e, engloba 550 exemplos divididos em duasclasses Lithuanian. O resultado é dado na Figura 4.11f. A quarta base de dados, comopode ser visualizada na Figura 4.11g, é construída a partir de 800 exemplos igualmentedividos em quatro classes seguindo distribuições Gaussianas. O resultado é indicadona Figura 4.11h. Enfim, segundo os dados de entrada, todos os resultados obtidossão visualmente satisfatórios, reforçando o argumento de robustez da técnica frente a


dados de distribuições arbitrárias.

4.3.3 Simulações em Bases de Dados Reais

Nesta seção, o desempenho do modelo proposto será avaliado a partir de bases dedados reais. Para tanto, os experimentos serão conduzidos em 7 conjuntos de dadossemissupervisionados que compõem o benchmark de Chapelle et al. (2006). Um brevedescrição dos metadados de tais bases de dados é fornecida na Tabela 4.2. Cada base dedado neste benchmark, especialmente as construídas artificialmente (primeiras 3 basesda tabela), foi projetada no propósito de criar situações que correspondem a hipótesesque a maioria dos algoritmos semissupervisionados se baseiam, quais sejam: suavi-dade, cluster e manifold. As outras 4 bases de dados são construídas a partir de dadosde aplicações reais.

Tabela 4.2: Metadados do benchmark de Chapelle et al. (2006)

Base de Dados Classes Dimensão Número de Exemplos Tipo

g241c 2 241 1500 artificialg241d 2 241 1500 artificialDigit1 2 241 1500 artificialUSPS 2 241 1500 não balanceadaCOIL 6 241 1500 -BCI 2 117 400 -Text 2 11960 1500 dados esparsos

O benchmark de Chapelle et al. (2006) é utilizado da seguinte forma: para cada basede dados citada na Tabela 4.2, dois tipos de experimentos serão realizados: 10 e 100vértices inicialmente pré-rotulados. A escolha dos vértices pré-rotulados é realizada detal forma a assegurar que exista pelo menos 1 vértice pré-rotulado de cada classe paracada configuração. Assim, para cada base de dados e configuração inicial de vérticespré-rotulados (10 ou 100), o benchmark fornece 12 conjuntos diferentes de vértices pré-rotulados. Para cada um desses conjuntos, o modelo competitivo é rodado 100 vezesindependentemente. Finalmente, o erro do conjunto de teste para cada base de dadosé calculado tomando-se a média dessas 12× 100 = 1200 execuções do algoritmo.

Para fins de comparação, são também conduzidos experimentos com técnicas re-presentativas de classificação semissupervisionada. Os resultados obtidos para essastécnicas foram extraídos de Chapelle et al. (2006), exceto para as técnicas LGC, LP, andLNP. Por questões de clareza, uma breve descrição de cada uma dessas técnicas é dadana Tabela 4.3. A configuração paramétrica dos algoritmos pode ser consultada direta-mente na descrição minuciosa em (Chapelle et al., 2006) e nas referências mostradas natabela em comento. Em relação às técnicas LGC, LP, and LNP, os seguintes parâmetros


0.25 0.5 0.75 10

0.25

0.5

0.75

1

(a)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(b)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(c)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(d)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(e)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(f)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(g)

0.25 0.5 0.75 10

0.25

0.5

0.75

1

(h)

Figura 4.11: Classificação de dados semissupervisionada. A cor do vértice indica a partículaque o está dominando. Os pontos escuros são vértices ainda não dominados. (a) e (b) Duasclasses com formatos de banana; (c) e (d) Duas classes, cada qual seguindo uma distribuiçãoHighleyman; (e) e (f) Duas classes, cada qual seguindo uma distribuição Lithuanian; (g) e (h)Quatro classes, cada qual seguindo uma distribuição Gaussiana.


foram utilizados: (i) LGC: como sugerido pelos autores em (Zhou et al., 2004), α = 0.99e σ é escolhido como o valor que resulta na melhor acurácia de classificação no inter-valo discretizado σ ∈ 0, 1, . . . , 100; (ii) LP: o σ ótimo é determinado da mesma formaque na técnica anterior no intervalo discretizado σ ∈ 0, 1, . . . , 100; (iii) como suge-rido pelos autores em (Wang e Zhang, 2008), α = 0.99 e k é escolhido da mesma formano intervalo discretizado k ∈ 1, 2, . . . , 100.

Quanto ao algoritmo competitivo, uma vez que ele é baseado em redes, necessita-se de uma técnica de formação de redes. No caso, foi escolhida a técnica k-vizinhosmais próximos e o valor de k é otimizado no intervalo discretizado k ∈ 1, 2, . . . , 10.Quanto aos parâmetros internos do sistema dinâmico, λ é otimizado no intervalo dis-cretizado λ ∈ 0.5, 0.51, . . . , 0.8. O número de partículas inserido na rede é igual aonúmero de dados rotulados. A posição inicial das partículas é fixada como o vértice oqual a mesma é representante. Os valores obtidos pelo modelo são extraídos da médiaatingida pelo algoritmo em 100 realizações em cada uma das 12 configurações acimaexplicadas. Os resultados obtidos para essas técnicas, para o caso de apenas 10 vérti-ces pré-rotulados, são reportados na Tabela 4.4, enquanto que os resultados atingidospelos mesmos algoritmos em apreço, no caso de 100 vértices pré-rotulados, são for-necidos na Tabela 4.5. Em ambas as tabelas, é também indicada a posição média decada algoritmo, medida a qual é calculada da seguinte forma: (i) para cada base dedados, os algoritmos são ordenados segundo seu desempenho em relação ao erro co-metido no conjunto de testes, i.e., o melhor algoritmo é ordenado em primeiro lugar, osegundo melhor, em segundo lugar, e assim sucessivamente; e (ii) para cada algoritmo,a posição média é dada pela média das posições atingidas em cada base de dados.

Uma análise atenta das Tabelas 4.4 e 4.5 revela que a técnica baseada em compe-tição de partículas obteve resultados satisfatórios em relação aos outros métodos. Es-pecificamente, para o caso de poucos vértices pré-rotulados (10 vértices), a técnica emapreço atingiu melhores resultados em relação ao seu desempenho com 100 vérticesinicialmente pré-rotulados. Isto é uma característica interessante, uma vez que a ta-refa de rotulação de vértices é geralmente onerosa e propensa a erros, já que envolve aparticipação de especialistas humanos.

De forma a analisar os resultados obtidos nas Tabelas 4.4 e 4.5 e verificar se o algo-ritmo proposto realmente apresenta relevância estatística, será aplicado uma métodoestatístico conforme proposto em Demšar (2006) e Chatfield (2009). A técnica descritanos artigos ora citados utiliza a informação da posição (rank) atingida por cada algo-ritmo para cada base de dados, i.e., a posição média, já apresentada anteriormente.Essas posições médias de cada algoritmo são avaliadas segundo o Teste de Skillings-Mack (reduz-se ao Teste de Friedman quando não existem valores ausentes na tabela).Tal teste estatístico é indicado para verificar se as posições médias dos algoritmos dife-rem da esperança da posição. A hipótese nula é que todos os algoritmos são idênticos,


logo, suas posições médias são iguais. Doravante, para todos os testes futuros, é fixadoum nível de significância de 10%. Para os experimentos nas Tabelas 4.4 e 4.5, segundoDemšar (2006) e Chatfield (2009), tem-se que N = 7 e k = 17, resultando em um va-lor crítico igual a F(16, 96) ≈ 1, 55, onde os dois argumentos da função F derivam dosgraus de liberdade definidos como k− 1 e (N− 1)(k− 1), respectivamente. Em relaçãoà Tabela 4.4, obtém-se o valor FF ≈ 1.58 que é superior que o valor crítico. Portanto,a hipótese nula é rejeitada com um nível de significância de 10%. Por outro lado, comrespeito à Tabela 4.5, obtém-se o valor FF ≈ 0.17, que é inferior ao valor crítico. Logo,não há possibilidade de rejeitar a hipótese nula para o nível de significância fixado.

Como a hipótese nula foi rejeitada para os dados presentes na Tabela 4.4 (apenas10 exemplos rotulados), é possível prosseguir para testes estatísticos post-hoc, os quaisobjetivam verificar o desempenho de um algoritmo específico frente aos demais. Paraesta tarefa, opta-se por usar o Teste de Bonferroni-Dunn com o algoritmo-controle (re-ferência) fixado como a técnica de competição de partículas aqui estudada. De acordocom Demšar (2006), não é factível realizar comparações entre pares de algoritmos dis-tintos, quando a principal meta é apenas verificar se um algoritmo é melhor que os de-mais. Basicamente, o Teste de Bonferroni-Dunn quantifica se o desempenho de um al-goritmo arbitrário e a referência é significantemente diferente. Isto é feito averiguandose as posições médias desses dois algoritmos diferem, pelo menos, de um valor crítico,aqui denominado diferença crítica (DC). Se os algoritmos diferem mais do que DC, en-tão é dito que o algoritmo com melhor posição média entre os dois é estatisticamentesuperior ao com a pior posição média. Caso não apresentem diferença de tamanhamagnitude, tais algoritmos não apresentam diferença significativa. Logo, calculando-se o valor de DC para a Tabela 4.4, obtém-se DC = 4, 86. A posição média do algoritmoreferência (técnica de competição de partículas) é 5, 29. Em virtude disso, se algumaposição média de outro algoritmo pertencer ao intervalo 5.29± 4.86, a referência e estealgoritmo são estatisticamente iguais para o conjunto de dados em análise. De fato,pode-se concluir que o algoritmo de competição de partícula é superior às técnicasSVM, Regularizador Discreto, TSVM e Cluster-Kernel para o benchmark de Chapelleet al. (2006). Entretanto, a comparação com as posições médias dos outros algoritmosnão ultrapassa tal intervalo, levando a conclusão que são estatisticamente equivalentespara o benchmark de Chapelle et al. (2006). De qualquer forma, a técnica de competiçãode partículas apresentou o melhor desempenho (melhor posição média) em relação aosoutros algoritmos para o caso de apenas 10 vértices pré-rotulados.


Tabela 4.3: Técnicas selecionadas para comparação no benchmark de Chapelle et al. (2006).

Abreviação Técnicas Ref(s).

MVU + 1-NN Maximum Variance Unfolding (Sun et al., 2006; Weinberger e Saul, 2006)

LEM + 1-NN Laplacian Eigenmaps (Belkin e Niyogi, 2003)

QC + CMR Quadratic Criterion and Class Mass Regularization (Belkin et al., 2004; Delalleau et al., 2005)

Discrete Reg. Discrete Regularization (Zhou e Schölkopf, 2006)

TSVM Transductive Support Vector Machines (Chapelle e Zien, 2005; Joachims, 2003)

SGT Spectral Graph Transducer (Joachims, 2003)

Cluster-Kernel Cluster Kernels (Chapelle et al., 2003)

Data-Dep. Reg. Data-Dependent Regularization (Corduneanu e Jaakkola, 2006)

LDS Low-Density Separation (Chapelle e Zien, 2005)

Laplacian RLS Laplacian Regularized Least Squares (Sindhwani et al., 2005)

CHM (normed) Conditional Harmonic Mixing (Burges e Platt, 2006)

LGC Local and Global Consistency (Zhou et al., 2004)

LP Label Propagation (Zhu e Ghahramani, 2002)

LNP Linear Neighborhood Propagation (Wang e Zhang, 2008)

Tabela 4.4: Erros preditivos no conjunto de teste (%) com 10 vértices rotulados no conjunto detreinamento.

g241c g241d Digit1 USPS COIL BCI Text Pos. Média

1-NN 47,88 46,72 13,65 16,66 63,36 49,00 38,12 9,86SVM 47,32 46,66 30,60 20,03 68,36 49,85 45,37 14,14

MVU + 1-NN 47,15 45,56 14,42 23,34 62,62 47,95 45,32 9,86LEM + 1-NN 44,05 43,22 23,47 19,82 65,91 48,74 39,44 10,00

QC + CMR 39,96 46,55 9,80 13,61 59,63 50,36 40,79 7,86Discrete Reg. 49,59 49,05 12,64 16,07 63,38 49,51 40,37 10,86

TSVM 24,71 50,08 17,77 25,20 67,50 49,15 31,21 10,86SGT 22,76 18,64 8,92 25,36 - 49,59 29,02 6,50

Cluster-Kernel 48,28 42,05 18,73 19,41 67,32 48,31 42,72 10,86Data-Dep. Reg. 41,25 45,89 12,49 17,96 63,65 50,21 - 9,83

LDS 28,85 50,63 15,63 17,57 61,90 49,27 27,15 8,43Laplacian RLS 43,95 45,68 5,44 18,99 54,54 48,97 33,68 6,14

CHM (normed) 39,03 43,01 14,86 20,53 - 46,90 - 7,20LGC 45,82 44,09 9,89 9,03 63,45 47,09 45,50 7,29

LP 42,61 41,93 11,31 14,83 55,82 46,37 49,53 5,57LNP 47,82 46,24 8,58 17,87 55,50 47,65 41,06 7,43

Método Proposto 43,89 46,47 8,10 15,69 54,18 48,00 34,84 5,29


Tabela 4.5: Erros preditivos no conjunto de teste (%) com 100 vértices rotulados no conjunto detreinamento.

g241c g241d Digit1 USPS COIL BCI Text Pos. Média

1-NN 43,93 42,45 3,89 5,81 17,35 48,67 30,11 9,00SVM 23,11 24,64 5,53 9,75 22,93 34,31 26,45 9,14

MVU + 1-NN 43,01 38,20 2,83 6,50 28,71 47,89 32,83 11,86LEM + 1-NN 40,28 37,49 6,12 7,64 23,27 44,83 30,77 12,14

QC + CMR 22,05 28,20 3,15 6,36 10,03 46,22 25,71 7,50Discrete Reg. 43,65 41,65 2,77 4,68 9,61 47,67 24,00 8,21

TSVM 18,46 22,42 6,15 9,77 25,80 33,25 24,52 8,71SGT 17,41 9,11 2,61 6,80 - 45,03 23,09 4,67

Cluster-Kernel 13,49 4,95 3,79 9,68 21,99 35,17 24,38 6,79Data-Dep. Reg. 20,31 32,82 2,44 5,10 11,46 47,47 - 7,17

LDS 18,04 23,74 3,46 4,96 13,72 43,97 23,15 6,00Laplacian RLS 24,36 26,46 2,92 4,68 11,92 31,36 23,57 4,93

CHM (normed) 24,82 25,67 3,79 7,65 - 36,03 - 9,10LGC 41,64 40,08 2,72 3,68 45,55 43,50 46,83 10,00

LP 30,39 29,22 3,05 6,98 11,14 42,69 40,79 9,29LNP 44,13 38,30 3,27 17,22 11,01 46,22 38,48 12,50

Método Proposto 24,92 29,11 3,11 4,82 10,94 41,57 27,92 7,00

Como último experimento, será utilizada uma base de dados de larga escala, nocaso, a base de dados Letter Recognition disponível no repositório UCI. Esse conjuntode dados compreende 20.000 exemplos de 26 letras maiúsculas do alfabeto, com cadaexemplo apresentando fonte diferentes e distorções aleatórias. Na sua configuraçãooriginal, as imagens dos exemplos são convertidas em 16 descritores escalares. Serãoaplicadas duas técnicas representativas baseadas em redes (LP e LNP), bem como a téc-nica de competição de partículas. Todas as técnicas seguem as mesmas configuraçõesparamétricas discutidas em oportunidade anterior. Cada algoritmo é executado uti-lizando 3 subconjuntos de dados pré-rotulados escolhidos aleatoriamente, cada qualcom tamanho 1%, 5%, and 10% do conjunto de dados. Cada algoritmo é executado 10vezes na base de dados em apreço e a média dessas 10 execuções é disponibilizada.A Tabela 4.6 reporta os erros de predição no conjunto de teste para essas três técnicas.Novamente, verifica-se que o método de competição obteve bons resultados.

Tabela 4.6: Erros preditivos no conjunto de teste (%) obtidos para o conjunto de dados LetterRecognition.

10% Rotulados 5% Rotulados 1% Rotulado

LP 10,94 18,99 46,94LNP 24,22 34,08 54,61

Método Proposto 12,09 15,51 38,24


4.3.4 Considerações Finais

Neste trabalho, foi proposto um novo modelo matemático para competição de par-tículas em redes complexas, biologicamente inspirado pelo processo competitivo queocorre em muitos sistemas naturais e sociais. Neste modelo, várias partículas, cadauma representando uma classe, navegam na rede para explorar novos territórios e, aomesmo tempo, tentam defender seus vértices já dominados contra partículas rivais. Sevárias partículas propagam o mesmo rótulo, então um time é formado, e um processocooperativo entre partículas do mesmo time é verificado. Um mecanismo de confina-mento foi proposto com o intuito de prevenir partículas de navegarem na rede semquaisquer penalidades, possivelmente prejudicando a acurácia do algoritmo. Conse-quentemente, o algoritmo de competição propaga os rótulos de uma maneira local, aoinvés do que ocorre em diversas técnicas tradicionais semissupervisionadas de classi-ficação, em que os rótulos são propagados de forma global.

O modelo proposto é não linear e estocástico. Em virtude disso, uma análise mate-mática alternativa foi elaborada para descrever e predizer o comportamento do modeloconforme o tempo progride. Expressões fechadas para descrever a distribuição proba-bilística da matriz de nível de dominação foram apresentadas. Com esta ferramenta, épossível verificar como será o comportamento do modelo frente a uma rede qualquer.Para fins de clareza, um exemplo numérico foi introduzido. Ainda, uma validação dosresultados teóricos foi demonstrada, confirmando as predições estudadas na seção deanálise matemática.

Simulações computacionais foram realizadas com o propósito de quantificar a ro-bustez do método proposto em conjuntos de dados reais e artificiais. Uma análisedetalhada do comportamento evolucional da matriz de dominação revela que o mo-delo funciona bem em ambas situações. Mais importante, este trabalho é uma tentativade fornecer uma forma alternativa para o estudo de aprendizado competitivo.

Como trabalhos futuros, serão investigadas e propostas novas medidas para quan-tificar a natureza de sobreposição de vértices ou sub-grafos na rede. Outro tópico desuma importância que será estudado é a propagação de rótulos errados. Neste cenário,será utilizado o próprio processo competitivo para prevenir que esses rótulos erradosse propaguem pela rede. Com isso, espera-se aumentar a confiabilidade do resultadofinal produzido pelo modelo. Tendo em vista que a tarefa de rotulação usualmenteenvolve esforços humanos, os quais, por sua vez, são suscetíveis a introdução de erros,este é um tópico importante para ser futuramennte estudado pelo modelo proposto.

CAPÍTULO

5Proposta de Pesquisa

Neste capítulo, serão delineadas as atividades que serão desenvolvidas no trans-correr do projeto. Especificamente, na Seção 5.1, é apresentado como cada objetivo doprojeto será analisado e cumprido; na Seção 5.2, o cronograma de atividades é forne-cido; na Seção 5.3, é indicado os recursos infra-estruturais disponíveis e a metodologiade pesquisa utilizada; e, finalmente, na Seção 5.4, a forma de análise dos resultados éexplicitada.

5.1 Estratégia de Desenvolvimento

Nesta seção, o conteúdo técnico que o plano de pesquisa abrange será detalhado.Especificamente, na Subseção 5.1.1, é discorrido sobre a modelagem do sistema com-petitivo semissupervisionado; na Subseção 5.1.2, a modelagem matemática do sistemadesenvolvido na etapa anterior é discutida; na Subseção 5.1.3, é dada uma ideia ini-cial sobre a extensão do modelo competitivo semissupervisionado para o campo nãosupervisionado, bem como uma estratégia para estimar o número de clusters e co-munidades em uma base de dados; na Subseção 5.1.4, é fornecido, em caráter inicial,um método para detectar vértices e comunidades sobrepostos; e, finalmente, na Sub-seção 5.1.5, é apresentado o assunto de confiabilidade dos dados, crucial para algunssistemas de dados, tópico o qual possui raízes ligadas aos processos inerentes de pro-pagação de erros em razão de rotulações erradas.

97

98 Capítulo 5 - Proposta de Pesquisa

5.1.1 Modelagem da Técnica de Competição de Partículas para

Aprendizado Semissupervisionado

Esta etapa de pesquisa já foi desenvolvida, conforme foi visto no capítulo de Resul-tados Obtidos (Seção 4.1). Vale destacar alguns pontos importantes que foram realiza-dos, a partir desta modelagem:

• Foi desenvolvida uma descrição rigorosa do modelo competitivo por meio dautilização de um sistema dinâmico estocástico não linear. Tal característica é iné-dita, dado que, no trabalho original proposto por Quiles et al. (2008), apenas umprocedimento, sem qualquer rigor matemático, é introduzido.

• Generalização da teoria de caminhada aleatória simples para um modelo de múl-tiplas caminhadas aleatórias com interação por meio de competição. A genera-lização ocorre a partir da escolha do parâmetro λ do modelo, o qual é respon-sável por contrabalancear a proporção de caminhadas aleatórias e preferenciais.Quando λ = 0, o modelo reduz-se a múltiplas caminhadas aleatórias sem in-teração. No entanto, quando λ > 0, o modelo descreve múltiplas caminhadasaleatórias com interação, via competição de partículas.

• Ao contrário do modelo procedimental proposto em Quiles et al. (2008), em queà partícula somente é permitido ora fazer uma movimentação aleatória, ora pre-ferencial; no modelo proposto, uma combinação estocástica entre as duas movi-mentações é implementada, conforme a Equação (4.1) revela. Simulações realiza-das, conforme informadas na Seção 4.3, exibem a robustez e eficácia do modelo.

5.1.2 Análise Matemática do Modelo de Competição Semissupervisi-

onado

Esta etapa também já foi completada e foi discutida no capítulo de Resultados Ob-tidos (Seção 4.2). A lista abaixo discorre, resumidamente, sobre os pontos importantesdessa análise:

• Expressões probabilísticas foram deduzidas a partir do sistema dinâmico esto-cástico. Isto permite prever o comportamento do sistema competitivo para umtempo arbitrariamente alto.

• Uma validação das equações teóricas obtidas, contra o resultado empírico do mo-delo, foi conduzida. Resultados mostram que, de forma aproximada, a prediçãoteórica aproxima o comportamento empírico do modelo.

• O modelo competitivo, bem como a análise matemática, aqui descritos baseiam-se no artigo Silva e Zhao (2011b), o qual está em processo de revisão.

5.1 - Estratégia de Desenvolvimento 99

5.1.3 Extensão do Modelo Competitivo ao Aprendizado Não Supervi-

sionado

O modelo competitivo desenvolvido para aprendizado semissupervisionado porintermédio de um sistema dinâmico estocástico será estendido para o campo não su-pervisionado. A ideia inicial é modificar as condições iniciais do sistema dinâmico.No modelo semissupervisionado, as entradas da matriz N(t), a qual é responsável porarmazenar o número de visitas feito por cada partícula a cada vértice na rede, que in-dicam vértices pré-rotulados são fixadas no valor ∞. Desta maneira, não é possívelque outra partícula venha a dominá-la, senão a partícula representante daquele vérticepré-rotulado. No modelo não supervisionado, sugere-se utilizar a seguinte condiçãoinicial para esta matriz:

N(k)i (0) =

2, se a partícula k é gerada no vértice i

1, caso contrário. (5.1)

Outro ponto importante que será analisado, ainda no campo não supervisionado,é a estimação do número de clusters ou comunidades em uma base de dados. Taldeterminação é um importante tópico em agrupamento de dados (Sugar e James, 2003;Wang et al., 2009). A ideia inicial para realizar tal estimação é utilizar um avaliadorexterno, o qual monitora a informação gerada pelo próprio processo competitivo. Amedida de rede que será monitorada, aqui, denominada de média do máximo nível dedominação, 〈R(t)〉 ∈ [0, 1], é calculada utilizando a seguinte expressão:

〈R(t)〉 = 1V

V

∑u=1

maxm∈K

(N(m)

u (t))

, (5.2)

onde N(m)u (t) indica o nível de dominação que a partícula m está impondo no vértice

u no instante t e maxm∈K

(N(m)

u (t))

resulta no nível de dominação máximo imposto no

vértice u no instante t. Para uma rede que apresenta algumas comunidades, diga-se Kcomunidades, por exemplo, se forem inseridas K partículas, espera-se que cada umadomine uma comunidade distinta. Logo, uma partícula não interferirá na região deatuação das outras partículas. Consequentemente, 〈R(t)〉 será alto. No caso extremo,cada vértice é completamente dominado por apenas uma partícula, daí 〈R(t)〉 atinge1. Entretanto, se forem colocadas mais de K partículas, inevitavelmente, ocorrerá quemais de uma partícula compartilhará a mesma comunidade. Neste caso, elas disputa-rão o mesmo grupo de vértices. Em virtude disso, uma partícula irá diminuir o nívelde dominação das outras partículas, e vice-versa. Como resultado, 〈R(t)〉 será baixo.


A contrario sensus, se for introduzida na rede uma quantidade de partículas inferiorao número de comunidades (K), uma competição acirrada também irá ocorrer entreas partículas. Neste caso, elas tentarão dominar mais de uma comunidade ao mesmotempo. Novamente, 〈R(t)〉 será baixo. Logo, esses cenários sugerem que o número cor-reto de clusters ou comunidades pode ser determinado checando o maior valor 〈R(t)〉atingido.

Se, por hipótese, for aplicado este avaliador externo para determinar o númerode comunidades ou clusters que um conjunto de dados possui, é necessário rodar osistema dinâmico estocástico várias vezes. Em termos práticos, o número de partículasdeve variar de 2 até K′, onde K′ é um valor um pouco maior que K, aqui denotando onúmero real de comunidades ou clusters no conjunto de dados. Tendo em vista que onúmero de clusters é pequeno, i.e., é bem menor que o número de dados (K V), esteprocesso de estimação pode não alterar a ordem de complexidade do modelo.

Agora, será informada a forma de validação do método de competição de partícu-las não supervisionado e do procedimento de estimação de comunidades ou clusters.Especificamente, para o caso de detecção de comunidades, serão utilizados benchmarksamplamente aceitos na área (Danon et al., 2005; Fortunato, 2010), bem como redes ar-tificiais e reais. Já para o caso de agrupamento de dados, serão utilizadas bases dedados disponíveis no repositório UCI (Frank e Asuncion, 2010) e também a base dedados MNIST de dígitos manuscritos (LeCun et al., 1998).

5.1.4 Detecção de Vértices e Comunidades Sobrepostos

O modelo competitivo analisado neste projeto carrega uma gama rica de informa-ção, informação esta gerada pelo próprio processo competitivo. Por intermédio dela,será derivada uma medida para detectar comunidades ou vértices sobrepostos em umarede. Para tanto, cumpre notar que a matriz de nível de dominação N(t) pode ser uti-lizada para indicar quais vértices são membros de uma ou várias comunidades, daseguinte forma: se o nível de dominação máximo imposto por uma partícula arbitráriak em um vértice i é muito maior que o segundo maior nível de dominação imposto aomesmo vértice, então pode-se concluir que este vértice está sendo fortemente domi-nado pela partícula k. Por outro lado, quando estas duas quantidades são similares,pode-se deduzir que o vértice i apresenta características que o qualificam como mem-bro de mais de uma comunidade. À luz dessas considerações, pode-se matematica-mente modelar este comportamento a seguir: seja Mi(x, t) o x-ésimo maior nível dedominação imposto ao vértice i no instante t. Desta forma, o índice de sobreposiçãopara o vértice i, Oi(t) ∈ [0, 1], é dado por:

5.1 - Estratégia de Desenvolvimento 101

Oi(t) = 1− (Mi(1, t)−Mi(2, t)) , (5.3)

i.e., o índice de sobreposição Oi(t) mensura o intervalo entre os dois maiores níveisde dominação impostos por quaisquer pares de partículas ao vértice i. Sucintamente,quando este intervalo é grande, uma forte dominação está ocorrendo sobre o vértice i;logo, Oi(t) produz um valor pequeno. Por outro lado, quando uma competição estáocorrendo de forma intensa entre duas ou mais partículas em relação ao vértice i, al-guns desses níveis de dominação são esperados de serem semelhantes, em termos demagnitude. Consequentemente, o intervalo entre os dois maiores níveis de domina-ção provavelmente será pequeno, produzindo, assim, um valor alto para o índice desobreposição Oi(t).

Para validar a medida proposta, simulações em bases de dados conhecidas na lite-ratura serão conduzidas, tais como rede de karatê de Zachary (Zachary’s karate clubnetwork) (Zachary, 1977), rede social de golfinhos (dolphin social network) (Lusseau,2003), rede da novela Les Misérables (Les Misérables network) (Knuth, 1993), rede repre-sentando uma liga de futebol americano (American college football network) (Girvan eNewman, 2002) e rede de colaboração científica (scientific collaboration network) (New-man, 2006).

5.1.5 Tratamento da Confiabilidade dos Dados no Processo de Apren-

dizado Semissupervisionado

Na próxima fase, será tratado do assunto de confiabilidade dos dados no aprendi-zado semissupervisionado. Especificamente, a técnica a ser desenvolvida gozará dasseguintes características:

I. Geração de Nível de Pertinência para Cada Vértice: A técnica a ser desenvolvidaserá capaz de oferecer nível de pertinência de cada item de dado a cada classe(soft-label), ao invés de só oferecer rótulo de classe (hard-label).

II. Detecção de Outliers: A técnica a ser desenvolvida será capaz de detectar outlierse consequentemente tentará impedir sua propagação. Outliers referem-se a itensde dados de uma determinada classe localizados em regiões de outras classes.No modelo de cooperação/competição de partículas, uma partícula, cujo vérticerepresentado é um outlier, tem dificuldade de defender seus vizinhos, pois elaestá longe de suas colegas do time e consequentemente recebe menos ajuda dotime. Desta forma, uma partícula, cujo vértice de casa é um outlier, pode even-tualmente abandonar sua casa e migrar para uma vizinhança de partículas do


mesmo time. Portanto, neste modelo, um outlier pode ser identificado via me-dida de distância média de uma partícula ao seu vértice representado ao longodo tempo.

Além disso, serão conduzidos estudos e análises de propagação de erros (dados er-roneamente rotulados) junto à propagação de rótulos em redes. Ou seja, certa percen-tagem de erros é introduzida antes do processo de propagação de rótulos. Pretende-seidentificar, com isso, o ponto crítico de percentagem de erros introduzidos, o que levaa uma precisão de classificação drasticamente decaída. Esse tipo de estudo é muitoimportante não só para obter uma classificação segura, mas também para um entendi-mento melhor de conjunto de dados em processamento.

5.2 Atividades e Cronograma

A seguir estão descritas as atividades programadas para o período de realização docurso de doutorado. A Tabela 5.1 mostra o cronograma em sequência temporal.

I. Assistência a Disciplinas: completar os 84 créditos necessários em disciplinasdo Programa de Doutorado do ICMC-USP, dos quais 36 créditos devem ser inte-gralizados a partir de disciplinas do núcleo básico.

II. Pesquisa Bibliográfica: buscar e estudar bibliografia sobre aprendizado de má-quinas, classificação de dados, técnicas de detecção de comunidades, redes com-plexas, sistemas dinâmicos e aplicações.

III. Exame de Qualificação: elaborar o documento escrito e realizar a prova de examede qualificação atendendo à exigência do Programa de Doutorado do ICMC-USP.

IV. Desenvolvimento Teórico: modelagem do sistema dinâmico competitivo nocampo de aprendizado semissupervisionado, análise matemática do modelo se-missupervisionado, extensão do modelo competitivo ao campo não supervisi-onado, criação de medidas para detecção de vértices sobrepostos e estudo deconfiabilidade de dados.

V. Testes e Simulações: implementar modelos existentes e os modelos a serem de-senvolvidos e realizar comparações a partir de testes com simulações em dadosartificiais e dados reais.

VI. Aplicações: aplicar os modelos desenvolvidos em bases de dados do repositórioUCI e MNIST.

VII. Geração de Artigos: preparar e submeter artigos com os desenvolvimentos rea-lizados para revistas científicas e para congressos.

Proposta de Pesquisa 103

VIII. Elaboração de relatórios: elaborar e submeter relatórios de acompanhamentopara a FAPESP.

IX. Defesa de Tese: elaborar e defender a tese de conclusão.

Tabela 5.1: Cronograma das atividades.``````````````Semestre

Atividade I II III IV V VI VII VIII IX

1S/2010

2S/2010

1S/2011

2S/2011

1S/2012

2S/2012

1S/2013

2S/2013

5.3 Materiais e Recursos Disponíveis

Este projeto envolve o estudo teórico como a revisão de artigos e a elaboração demodelos matemáticos e algoritmos, bem como a realização de simulações computa-cionais. Para tanto, serão utilizados os recursos disponíveis para a comunidade daUniversidade de São Paulo como consultas a bases internacionais de publicações, te-ses e livros a partir das bibliotecas da universidade. As simulações computacionais,quando for necessária a utilização de maiores recursos, serão realizadas no Laborató-rio de Computação Bioinspirada (BioCom) ICMC-USP, em São Carlos, o qual dispõede um cluster de processamento.

5.4 Forma de Análise dos Resultados

Os resultados das investigações serão analisados a partir de comparações da pre-cisão, complexidade e eficiência da aplicação dos algoritmos e técnicas desenvolvidascom outros semelhantes. Os modelos matemáticos serão avaliados quanto à precisãona previsão dos processos descritos. Além disso, métodos estatísticos devem ser en-volvidos para medir e validar o desempenho das técnicas a serem desenvolvidas.

104 Proposta de Pesquisa

Referências Bibliográficas

Albert et al.(1999) Reka Albert, Hawoong Jeong, e Albert-Laszlo Barabasi. The diame-ter of the world wide web. Nature, 401:130–131. Citado na pág. 3, 13

Albert et al.(2004) Réka Albert, István Albert, e Gary L. Nakarado. Structural vulnera-bility of the north american power grid. Physical Review E, 69(2):025103. Citado na pág. 3,12, 13

Alpaydin(2004) Ethem Alpaydin. Introduction to Machine Learning (Adaptive Computa-tion and Machine Learning). The MIT Press. Citado na pág. 33, 36

Amorim et al.(2007) D. G. Amorim, M. F. Delgado, e S. B. Ameneiro. Polytope ART-MAP: Pattern classification without vigilance based on general geometry categories.IEEE Trans. Neural Networks, 18(5):1306–1325. Citado na pág. 2

Arenas et al.(2006) Alex Arenas, Albert D. Guilera, e Conrad J. Pérez Vicente. Synch-ronization reveals topological scales in complex networks. Physical Review Letters, 96(11):114102. Citado na pág. 20

Athinarayanan et al.(2002) R. Athinarayanan, M. R. Sayeh, e D. A. Wood. Adaptivecompetitive self-organizing associative memory. IEEE Trans. Systems, Man and Cy-bernetics , Part A, 32(4):461–471. Citado na pág. 2

Bacciu e Starita(2008) D. Bacciu e A. Starita. Competitive repetition suppression (core)clustering: A biologically inspired learning model with application to robust cluste-ring. IEEE Trans. Neural Networks, 19(11):1922–1940. Citado na pág. 2

Barabasi e Albert(1999) Albert-Laszlo Barabasi e Reka Albert. Emergence of scaling inrandom networks. Science - New York, 286(5439):509–512. Citado na pág. xi, 3, 12, 17, 18

Belkin et al.(2005) M. Belkin, Niyogi P., e V. Sindhwani. On manifold regularization.Em Proceedings of the Tenth International Workshop on Artificial Intelligence and Statis-tics (AISTAT 2005), páginas 17–24, New Jersey. Society for Artificial Intelligence andStatistics. Citado na pág. 29

Belkin e Niyogi(2003) Mikhail Belkin e Partha Niyogi. Laplacian eigenmaps for di-mensionality reduction and data representation. Neural Comp., 15(6):1373–1396. Citado

na pág. 8, 94

105

106 Referências Bibliográficas

Belkin et al.(2004) Mikhail Belkin, Irina Matveeva, e Partha Niyogi. Regularization andsemi-supervised learning on large graphs. Em In COLT, páginas 624–638. Springer.Citado na pág. 8, 29, 94

Belkin et al.(2006) Mikhail Belkin, Partha Niyogi, e Vikas Sindhwani. Manifold regula-rization: A geometric framework for learning from labeled and unlabeled examples.Journal of Machine Learning Research, 7:2399–2434. Citado na pág. 29, 39, 40

Bishop(2007) Christopher M. Bishop. Pattern Recognition and Machine Learning (Infor-mation Science and Statistics). Springer, segunda edição. Citado na pág. 1

Blum e Mitchell(1998) Avrim Blum e Tom Mitchell. Combining labeled and unlabeleddata with co-training. Em Proceedings of the 11th Annual Conference on ComputationalLearning Theory, páginas 92–100. Citado na pág. 32

Boccaletti et al.(2007) Stefano Boccaletti, Mikhail V. Ivanchenko, Vito Latora, Alessan-dro. Pluchino, e Andrea Rapisarda. Detecting complex network modularity by dy-namical clustering. Physical Review E, 75(4):045102. Citado na pág. 4, 7

Bornholdt e Schuster(2003) Stefan Bornholdt e Heinz G. Schuster. Handbook of Graphsand Networks: From the Genome to the Internet. Wiley-VCH. Citado na pág. 3, 12

Breve et al.(2010) Fabrício Breve, Liang Zhao, Marcos G. Quiles, Witold Pedrycz, eJiming Liu. Particle competition and cooperation in networks for semi-supervisedlearning. IEEE Transaction on Data and Knowledge Engineering. Citado na pág. 29

Burges e Platt(2006) C. J. C. Burges e J. C. Platt. Semi-supervised Learning. ch. Semi-Supervised Learning with Conditional Harmonic Mixing, páginas 251–273. Adaptivecomputation and machine learning. MIT Press, Cambridge, MA, USA. Citado na pág. 94

Callut et al.(2008) Jérôme Callut, Kevin Françoise, Marco Saerens, e Pierre Duppont.Semi-supervised classification from discriminative random walks. European Confe-rence on Machine Learning and Principles and Practice of Knowledge Discovery in Databa-ses, LNAI 5211:162–177. Citado na pág. 29, 43, 45

Carpenter e Grossberg(1987) G. A. Carpenter e S. Grossberg. Self-organization of sta-ble category recognition codes for analog input patterns. Applied Optics, 26(23):4919–4930. Citado na pág. 2

Chapelle e Zien(2005) O. Chapelle e A. Zien. Random-walk based approach to detectclone attacks in wireless sensor networks. Tenth International Workshop on ArtificialIntelligence and Statistics, páginas 57–64. Citado na pág. 94

Chapelle et al.(2003) O. Chapelle, J. Weston, e B. Schölkopf. Cluster kernels for semi-supervised learning. Em NIPS 2002, volume 15, páginas 585–592, Cambridge, MA,USA. MIT Press. Citado na pág. 94

Chapelle et al.(2006) Olivier Chapelle, Bernhard Schölkopf, e Alexander Zien. Semi-Supervised Learning. The MIT Press. Citado na pág. 2, 25, 26, 28, 29, 30, 31, 32, 33, 34, 36,46, 85, 90, 93, 94

Chatfield(2009) M. Chatfield. The skillings-mack test (friedman test when there aremissing data). Stata Journal, 9(2):299–305(7). Citado na pág. 92, 93


Chen et al.(2005) M. Chen, A. A. Ghorbani, e V. C. Bhavsar. Incremental communicationfor adaptive resonance theory networks. IEEE Trans. Neural Networks, 16(1):132–144.Citado na pág. 2

Chung(1997) Fan R. K. Chung. Spectral Graph Theory (CBMS Regional Conference Seriesin Mathematics, No. 92). American Mathematical Society. Citado na pág. 39

Çinlar(1975) E. Çinlar. Introduction to Stochastic Processes. Prentice-Hall, EnglewoodCliffs, N. J. Citado na pág. 44, 46, 53, 56, 72

Clauset et al.(2004) A. Clauset, M. E. J. Newman, e C. Moore. Finding community struc-ture in very large networks. Physical Review E, páginas 1–6. doi: 10.1103/PhysRevE.70.066111. Citado na pág. 41

Clauset(2005) Aaron Clauset. Finding local community structure in networks. PhysicalReview E, 72(2):026132. Citado na pág. 4, 40, 41

Cook e Holder(2000) Diane J. Cook e Lawrence B. Holder. Graph-based data mining.IEEE Intelligent Systems, 15:32–41. Citado na pág. 4

Corduneanu e Jaakkola(2006) A. Corduneanu e T. Jaakkola. Semi-supervised Learning.ch. Data-Dependent Regularization, páginas 163–190. Adaptive computation and ma-chine learning. MIT Press, Cambridge, MA, USA. Citado na pág. 94

Cortes e Vapnik(1995) Corinna Cortes e Vladimir Vapnik. Support-vector networks.Machine Learning, páginas 273–297. Citado na pág. 31, 33

Costa et al.(2007) Luciano da F. Costa, Francisco A. Rodrigues, Gonzalo Travieso, ePaulino R. Villas Boas. Characterization of complex networks: A survey of measu-rements. Advances in Physics, 56(1):167–242. Citado na pág. xi, 13, 14, 15, 16

Danon et al.(2005) Leon Danon, Albert Díaz-Guilera, Jordi Duch, e Alex Arenas. Com-paring community structure identification. Journal of Statistical Mechanics: Theory andExperiment, 2005(09):P09008. Citado na pág. 6, 8, 19, 20, 100

Danon et al.(2007) Leon Danon, Jordi Duch, Alex Arenas, e Díaz-Guilera. Communitystructure identification in large scale structure and dynamics of complex networks:From information technology to finance and natural science. World Scientific Pu-blishing Co., páginas 93–113. Citado na pág. 4, 7

De Bie e Cristianini(2004) Tijl De Bie e Nello Cristianini. Convex methods for trans-duction. Em Sebastian Thrun, Lawrence Saul, e Bernhard Schölkopf, editors, Advan-ces in Neural Information Processing Systems 16. MIT Press, Cambridge, MA. Citado na pág.

33

Deboeck e Kohonen(2010) G. Deboeck e T. Kohonen. Visual Explorations in Finance:with Self-Organizing Maps. Springer. Citado na pág. 2

Delalleau et al.(2005) Olivier Delalleau, Yoshua Bengio, e Nicolas Le Roux. EfficientNon-Parametric Function Induction in Semi-Supervised Learning, páginas 96–103. Soci-ety for Artificial Intelligence and Statistics. Citado na pág. 94


Dempster et al.(1977) Arthur P. Dempster, Nan M. Laird, e Donald B. Rubin. Maximumlikelihood from incomplete data via the EM algorithm. Journal of the Royal StatisticalSociety. Series B (Methodological), 39(1):1–38. Citado na pág. 29

Demšar(2006) Janez Demšar. Statistical comparisons of classifiers over multiple datasets. Journal of Machine Learning Research, 7:1–30. Citado na pág. 92, 93

do Rêgo et al.(2010) R. L. M. Ernesto do Rêgo, A. F. R. Araújo, e F. B. de Lima Neto.Growing self-reconstruction maps. IEEE Trans. Neural Networks, 21(2):211–223. Citado

na pág. 2

Dorogovtsev e Mendes(2003) Sergey N. Dorogovtsev e José F. F. Mendes. Evolution ofNetworks: From Biological Nets to the Internet and WWW (Physics). Oxford UniversityPress, USA. Citado na pág. 13

Duda et al.(2000) Richard O. Duda, Peter E. Hart, e David G. Stork. Pattern Classification.Wiley-Interscience, segunda edição. Citado na pág. 1, 5, 35

Duin(2000) R. P. W. Duin. PRTools - version 3.0 - a matlab toolbox for pattern recogni-tion. Proc. of SPIE, página 1331. Citado na pág. 89

Erdös e Rényi(1959) Paul Erdös e Alfréd Rényi. On random graphs I. PublicationesMathematicae (Debrecen), 6:290–297. Citado na pág. 3, 12, 13

Evans e Lambiotte(2009) T. S. Evans e R. Lambiotte. Line graphs, link partitions, andoverlapping communities. Phys. Rev. E, 80(1):016105. Citado na pág. 20, 21

Faloutsos et al.(1999) Michalis Faloutsos, Petros Faloutsos, e Christos Faloutsos. Onpower-law relationships of the internet topology. Em SIGCOMM 99: Proceedingsof the conference on Applications, technologies, architectures, and protocols for computercommunication, volume 29, páginas 251–262, New York, NY, USA. ACM. Citado na pág.

3, 13

Fortunato(2010) S. Fortunato. Community detection in graphs. Physics Reports, 486:75–174. Citado na pág. 6, 8, 20, 100

Fortunato et al.(2004) S. Fortunato, V. Latora, e M. Marchiori. Method to find commu-nity structures based on information centrality. Phys. Rev. E, 70(5):056104. Citado na pág.

20

Frank e Asuncion(2010) A. Frank e A. Asuncion. UCI machine learning repository.Citado na pág. 6, 100

Gärtner(2008) Thomas Gärtner. Kernels for Structured Data, volume 72. World ScientificPublishing Co., primeira edição. Citado na pág. 33

Girvan e Newman(2002) Michelle Girvan e Mark E. J. Newman. Community structurein social and biological networks. Proceedings of the National Academy of Sciences of theUnited States of America, 99(12):7821–7826. Citado na pág. xi, 4, 6, 18, 25, 101

Goldman e Zhou(2000) Sally Goldman e Yan Zhou. Enhancing supervised learningwith unlabeled data. Em Proc. 17th International Conf. on Machine Learning, páginas327–334. Morgan Kaufmann, San Francisco, CA. Citado na pág. 32


Gori et al.(2005) M. Gori, M. Maggini, e L. Sarti. Exact and approximate graph mat-ching using random walks. IEEE Trans. Pattern Analysis and Machine Intelligence, 27(7):167–256. Citado na pág. 2

Grady(2006) L. Grady. Random walks for image segmentation. IEEE Trans. PatternAnalysis and Machine Intelligence, 28(11):1768–1783. Citado na pág. 2

Grossberg(1987) S. Grossberg. Competitive learning: From interactive activation toadaptive resonance. Cognitive Science, 11:23–63. Citado na pág. 2

Jain et al.(1999) Anil K. Jain, M. Narasimha Murty, e Patrick J. Flynn. Data clustering:A review. ACM Computing Survey, 31(3):264–323. Citado na pág. 5

Jain et al.(2010) L. C. Jain, B. Lazzerini, e U. Halici. Innovations in ART Neural Networks(Studies in Fuzziness and Soft Computing). Physica-Verlag, Heidelberg. Citado na pág. 2

Jeong et al.(2000) H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, e A. L. Barabási. Thelarge-scale organization of metabolic networks. Nature, 407(6804):651–654. Citado na

pág. 3, 13

Jiang e Wang(2000) D. Jiang e J. Wang. On-line learning of dynamical systems in thepresence of model mismatch and disturbances. IEEE Trans. Neural Networks, 11(6):1272–1283. Citado na pág. 2

Joachims(2003) Thorsten Joachims. Transductive learning via spectral graph partitio-ning. Em Proceedings of International Conference on Machine Learning, páginas 290–297.AAAI Press. Citado na pág. 94

Karypis et al.(1999) G. Karypis, Eui-Hong Han, e V. Kumar. Chameleon: hierarchicalclustering using dynamic modeling. Computer, 32(8):68–75. Citado na pág. 4, 25, 34

Kaylani et al.(2010) A. Kaylani, M. Georgiopoulos, M. Mollaghasemi, G. C. Anagnos-topoulos, C. Sentelle, e M. Zhong. An adaptive multiobjective approach to evolvingART architectures. IEEE Trans. Neural Networks, 21(4):529–550. Citado na pág. 2

Kiss et al.(1973) G. R. Kiss, C. Armstrong, R. Milroy, e J. Piper. An associative thesaurusof English and its computer analysis. Em The computer and literary studies. UniversityPress. Citado na pág. 8, 20

Knuth(1993) Donald E. Knuth. The Stanford GraphBase: a platform for combinatorial com-puting. ACM, New York, NY, USA. Citado na pág. 6, 101

Kohonen(1990) T. Kohonen. The self-organizing map. Proceedings of the IEEE, 78(9):1464–1480. Citado na pág. 2

Kosko(1991) B. Kosko. Stochastic competitive learning. IEEE Trans. Neural Networks, 2(5):522–529. Citado na pág. 2

Lancichinetti et al.(2009) Andrea Lancichinetti, Santo Fortunato, e János Kertész. De-tecting the overlapping and hierarchical community structure in complex networks.New Journal of Physics, 11(3):033015. Citado na pág. 20, 21


LeCun et al.(1998) Y. LeCun, L. Bottou, Y. Bengio, e P. Haffner. Gradient-based learningapplied to document recognition. Proceedings of the IEEE, 86(11):2278–2324. Citado na

pág. 6, 100

Liang et al.(2009) J. Liang, Z. Wang, e X. Liu. State estimation for coupled uncertain sto-chastic networks with missing measurements and time-varying delays: The discrete-time case. IEEE Trans. Neural Networks, 20(5):781–793. Citado na pág. 2

Lim e Park(2009) Gaksoo Lim e Cheong Hee Park. Semi-supervised dimension re-duction using graph-based discriminant analysis. Em CIT 1, páginas 9–13. IEEEComputer Society. Citado na pág. 25, 26

Liu et al.(2008) D. Liu, Z. Pang, e S. R. Lloyd. A neural network method for detectionof obstructive sleep apnea and narcolepsy based on pupil size and EEG. IEEE Trans.Neural Networks, 19(2):308–318. Citado na pág. 2

Liu et al.(2004) H. Liu, S. Shah, e W. Jiang. On-line outlier detection and data cleaning.28th Computers and Chemical Engineering, páginas 1635–1647. Citado na pág. 25, 26

López-Rubio et al.(2009) E. López-Rubio, J. M. Ortiz de Lazcano-Lobato, e D. López-Rodríguez. Probabilistic PCA self-organizing maps. IEEE Trans. Neural Networks, 20(9):1474–1489. Citado na pág. 2

Lu et al.(2003) Chang-Tien Lu, Dechang Chen, e Yufeng Kou. Algorithms for spatial ou-tlier detection. Em Proceedings of the 3rd IEEE International Conference on Data Mining(ICDM 2003). IEEE Computer Society. Citado na pág. 25

Lu e Ip(2009) Z. Lu e H. H. S. Ip. Generalized competitive learning of gaussian mixturemodels. IEEE Trans. Systems, Man and Cybernetics , Part B, 39(4):901–909. Citado na pág. 2

Lusseau(2003) D. Lusseau. The emergent properties of a dolphin social network. ProcBiol Sci, 270 Suppl 2:S186–S188. Citado na pág. 6, 101

Macskassy e Provost(2005) Sofus A. Macskassy e Foster Provost. Netkit-srl: A toolkitfor network learning and inference – and its use for classification of networked data.Em Proc. Ann. Conf. North. American Assoc. Computational Social and OrganizationalScience. Citado na pág. 45

Meyer-Bäse e Thümmler(2008) A. Meyer-Bäse e V. Thümmler. Local and global sta-bility analysis of an unsupervised competitive neural network. IEEE Trans. NeuralNetworks, 19(2):346–351. Citado na pág. 2

Meyn e Tweedie(2009) S. Meyn e R. Tweedie. Markov Chains and Stochastic Stability.Cambridge University Press, segunda edição. Citado na pág. 15, 43

Milgram(1967) Stanley Milgram. The small world problem. Psychology Today, 2:60–67.Citado na pág. 12

Mitchell(1997) Tom M. Mitchell. Machine Learning. McGraw-Hill Sci-ence/Engineering/Math, primeira edição. Citado na pág. 1, 25

Mizruchi(1982) M.S. Mizruchi. The american corporate network. Sage, 2:1904–1974.Citado na pág. 3, 13


Montoya e Solé(2002) J. M. Montoya e R. V. Solé. Small world patterns in food webs.Journal of Theoretical Biololgy, 214:405–412. Citado na pág. 3, 13

N. Allinson e Slack(2001) L. Allinson N. Allinson, H. Yin e J. Slack. Advances in SelfOrganising Maps. Springer. Citado na pág. 2

Newman(2003) M. E. J. Newman. The Structure and Function of Complex Networks.SIAM Review, 45(2):167–256. Citado na pág. 3, 11, 13, 15

Newman(2006) M. E. J. Newman. Modularity and community structure in networks.Proceedings of the National Academy of Sciences, 103(23):8577–8582. Citado na pág. 6, 20, 25,40, 41, 101

Newman e Girvan(2004) M. E. J. Newman e M. Girvan. Finding and evaluating com-munity structure in networks. Physical Review Letters, (69):026113. Citado na pág. 4, 7

Newman(2004a) M.E.J. Newman. Finding and evaluating community structure innetworks. Phys. Rev. E, 69(2):026113. Citado na pág. 20

Newman(2004b) M.E.J. Newman. Fast algorithm for detecting community structurein networks. Phys. Rev. E, 69(6):066133. Citado na pág. 20

Nicosia et al.(2009) V. Nicosia, G. Mangioni, V. Carchiolo, e M. Malgeri. Extending thedefinition of modularity to directed graphs with overlapping communities. Journalof Statistical Mechanics: Theory and Experiment, 2009(03):03024. Citado na pág. 21

Nigam et al.(2000) Kamal Nigam, Andrew K. McCallum, Sebastian Thrun, e Tom Mit-chell. Text classification from labeled and unlabeled documents using EM. MachineLearning, 39(2-3):103–134. Citado na pág. 31

Noh e Rieger(2004) J. D. Noh e H. Rieger. Random walks on complex networks. Phys.Rev. Letts., 92:118701. Citado na pág. 2

Palla et al.(2005) Gergely Palla, Imre Derenyi, Illes Farkas, e Tamas Vicsek. Uncoveringthe overlapping community structure of complex networks in nature and society.Nature, 435(7043):814–818. Citado na pág. 8, 20, 21

Papadopoulos et al.(2009) Symeon Papadopoulos, Andre Skusa, Athena Vakali, Yian-nis Kompatsiaris, e Nadine Wagner. Bridge bounding: A local approach for efficientcommunity discovery in complex networks. Relatório técnico. Citado na pág. xi, 19

Piatetsky-Shapiro(1991) G. Piatetsky-Shapiro. Discovery, Analysis, and Presentation ofStrong Rules. AAAI/MIT Press, Cambridge, MA. Citado na pág. 25, 26

Principe e Miikkulainen(2009) J. C. Principe e Risto Miikkulainen. Advances in Self-Organizing Maps - 7th International Workshop, WSOM 2009, Lecture Notes in ComputerScience, Vol. 5629. Springer. Citado na pág. 2

Quiles et al.(2008) M. G. Quiles, L. Zhao, R. L. Alonso, e R. A. F. Romero. Particlecompetition for complex network community detection. Chaos, 18(3):033107. Citado na

pág. 4, 7, 20, 21, 23, 98


Ratsaby e Venkatesht(1995) Joel Ratsaby e Santosh S. Venkatesht. Learning from amixture of labeled and unlabeled examples. Em Proc. 33rd Allerton Conference onCommunication Control and Computing, páginas 412–417. ACM Press. Citado na pág. 32

Reichardt e Bornholdt(2004) Jörg Reichardt e Stefan Bornholdt. Detecting fuzzy com-munity structures in complex networks with a potts model. Physical Review Letters,93(21):218701(1–4). Citado na pág. 4, 7, 20

Schaeffer(2007) S. Schaeffer. Graph clustering. Computer Science Review, 1(1):27–64.Citado na pág. 4

Scott(2000) John P. Scott. Social Network Analysis: A Handbook. SAGE Publications. Citado

na pág. 3, 13

Shahshahani e Landgrebe(1994) B. Shahshahani e D. Landgrebe. The effect of unla-beled samples in reducing the small sample size problem and mitigating the hughesphenomenon. IEEE Transactions on Geoscience and Remote Sensing, 32(5):1087–1095.Citado na pág. 32

Shen et al.(2009) Huawei Shen, Xueqi Cheng, Kai Cai, e Mao-Bin Hu. Detect overlap-ping and hierarchical community structure in networks. Physica A: Statistical Mecha-nics and its Applications, 388(8):1706 – 1712. Citado na pág. 21

Silva e Zhao(2011a) Thiago Christiano Silva e Liang Zhao. Semi-supervised learningguided by the modularity measure in complex networks. Neurocomputing, aceito.Citado na pág. 40, 42, 43

Silva e Zhao(2011b) Thiago Christiano Silva e Liang Zhao. Network-based stochasticsemi-supervised learning. IEEE Transactions on Neural Networks, em revisão. Citado na

pág. 49, 98

Sindhwani et al.(2005) Vikas Sindhwani, Partha Niyogi, e Mikhail Belkin. Beyond thepoint cloud: from transductive to semi-supervised learning. Em ICML ’05: Procee-dings of the 22nd international conference on Machine learning, páginas 824–831, NewYork, NY, USA. ACM Press. Citado na pág. 94

Singh et al.(2008) Aarti Singh, Robert D. Nowak, e Xiaojin Zhu. Unlabeled data: Nowit helps, now it doesn’t. Em NIPS, páginas 1513–1520. Citado na pág. 29

Smola e Kondor(2003) Alexander J. Smola e Risi Kondor. Kernels and regularizationon graphs. Learning Theory and Kernel Machines. Citado na pág. 38, 39

Sporns(2002) Olaf Sporns. Networks analysis, complexity, and brain function. Com-plexity, 8(1):56–60. Citado na pág. 3, 13

Strogatz(2001) S. H. Strogatz. Exploring complex networks. Nature, 410(6825):268–276.Citado na pág. 3, 13

Sugar e James(2003) C. A. Sugar e G. M. James. Finding the number of clusters in a dataset: An information theoretic approach. Journal of the American Statistical Association,98:750–763. Citado na pág. 99


Sun et al.(2006) Jun Sun, Stephen Boyd, Lin Xiao, e Persi Diaconis. The fastest mi-xing markov process on a graph and a connection to a maximum variance unfoldingproblem. SIAM Rev., 48:681–699. ISSN 0036-1445. Citado na pág. 94

Sun et al.(2011) Peng Gang Sun, Lin Gao, e Shan Shan Han. Identification of over-lapping and non-overlapping community structure by fuzzy clustering in complexnetworks. Inf. Sci., 181:1060–1071. Citado na pág. 21

Szummer e Jaakkola(2001) Martin Szummer e Tommi Jaakkola. Partially labeled clas-sification with markov random walks. Em Advances in Neural Information ProcessingSystems, volume 14. Citado na pág. 43, 46, 47

Tan et al.(2008) A.-H. Tan, N. Lu, e D. Xiao. Integrating temporal difference methodsand self-organizing neural networks for reinforcement learning with delayed evalu-ative feedback. IEEE Trans. Neural Networks, 19(2):230–244. Citado na pág. 2

Vapnik(1999) Vladimir Vapnik. The Nature of Statistical Learning Theory (InformationScience and Statistics). Springer-Verlag, segunda edição. Citado na pág. 31

Vapnik(1998) Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Interscience. Citado

na pág. 28, 31, 33

Wagsta et al.(2001) Kiri Wagsta, Claire Cardie, Seth Rogers, e Stefan Schroedl. Cons-trained k-means clustering with background knowledge. Em Proceedings of 18th In-ternational Conference on Machine Learning (ICML-01), páginas 577–584. Citado na pág. 31

Wang et al.(2009) C.-H. Wang, C.-N. Lee, e C.-H. Hsieh. Variants of Self-Organizing Maps:Applications in Image Quantization and Compression. Lambert Academic Publishing.Citado na pág. 2, 99

Wang e Zhang(2008) Fei Wang e Changshui Zhang. Label propagation through linearneighborhoods. IEEE Transactions on Knowledge and Data Engineering, 20(1):55–67.ISSN 1041-4347. doi: 10.1109/TKDE.2007.190672. Citado na pág. 92, 94

Watts(2003) Duncan J. Watts. Small Worlds: The Dynamics of Networks between Order andRandomness (Princeton Studies in Complexity). Princeton University Press, primeiraedição. Citado na pág. 15, 16

Watts e Strogatz(1998) Duncan J. Watts e Steven H. Strogatz. Collective dynamics of’small-world’ networks. Nature, 393(6684):440–442. Citado na pág. xi, 3, 12, 15, 16

Weinberger e Saul(2006) Kilian Q. Weinberger e Lawrence K. Saul. Unsupervisedlearning of image manifolds by semidefinite programming. Int. J. Comput. Vision, 70:77–90. ISSN 0920-5691. Citado na pág. 39, 94

West et al.(1999) G. B. West, J. H. Brown, e B. J. Enquist. A general model for thestructure, and algometry of plant vascular systems. Nature, 400:122–126. Citado na pág.

3, 13

Xu e II(2005) R. Xu e D. Wunsch II. Survey of clustering algorithms. IEEE Trans. NeuralNetworks, 16(3):645–678. Citado na pág. 2


Yarowsky(1995) David Yarowsky. Unsupervised word sense disambiguation rivalingsupervised methods. Em Meeting of the Association for Computational Linguistics, pá-ginas 189–196. Citado na pág. 28, 29

Zachary(1977) W. W. Zachary. An information flow model for conflict and fission insmall groups. Journal of Anthropological Research, 33:452–473. Citado na pág. 6, 101

Zeng et al.(2010) Y. Zeng, J. Cao, S. Zhang, S. Guo, e L. Xie. Random-walk basedapproach to detect clone attacks in wireless sensor networks. IEEE Journal on SelectedAreas in Communications, 28(5):677–691. Citado na pág. 3

Zhai(2006) Mingyue Zhai. On power lines communications channels’ characteristics ofmarkov. Parallel and Distributed Computing Applications and Technologies, InternationalConference on, 0:33–37. Citado na pág. 45

Zhang et al.(2007) S. Zhang, R. Wang, e X. Zhang. Identification of overlapping com-munity structure in complex networks using fuzzy cc-means clustering. Physica A:Statistical Mechanics and its Applications, 374(1):483–490. Citado na pág. 21

Zhao et al.(2004) L. Zhao, K. Park, e Y.-C. Lai. Attack vulnerability of scale-freenetworks due to cascading breakdown. Physical Review E, 70:035101(1–4). Citado na

pág. 3, 13

Zhao et al.(2005) L. Zhao, K. Park, e Y.-C. Lai. Tolerance of scale-free networks againstattack-induced cascades. Physical Review E (Rapid Communication), 72(2):025104(R)1–4. Citado na pág. 3, 13

Zhao et al.(2007) L. Zhao, T. H. Cupertino, K. Park, Y.-C. Lai, e X. Jin. Optimal struc-ture of complex networks for minimizing traffic congestion. Chaos (Woodbury), 17(4):043103(1–5). Citado na pág. 3, 13

Zhong et al.(2008) M. Zhong, K. Shen, e J. Seiferas. The convergence-guaranteed ran-dom walk and its applications in peer-to-peer networks. IEEE Trans. Computers, 57(5):619–633. Citado na pág. 3

Zhou e Schölkopf(2006) D. Zhou e B. Schölkopf. Semi-supervised Learning. ch: DiscreteRegularization, páginas 237–250. Adaptive computation and machine learning. MITPress, Cambridge, MA, USA. Citado na pág. 94

Zhou e Schölkopf(2004) Dengyong Zhou e Bernhard Schölkopf. Learning from labeledand unlabeled data using random walks. Em Pattern Recognition, Proceedings of the26th DAGM Symposium, volume 3175, páginas 237–244. Springer, Heidelberg. Citado na

pág. 35, 45

Zhou et al.(2003) Dengyong Zhou, Olivier Bousquet, Thomas N. Lal, Jason Weston,Bernhard Schölkopf, e Bernhard S. Olkopf. Learning with local and global consis-tency. Em Advances in Neural Information Processing Systems 16, volume 16, páginas321–328. Citado na pág. xi, 8, 34, 37, 38, 39

Zhou et al.(2004) Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston,e Bernhard Schölkopf. Learning with local and global consistency. Em Advances inNeural Information Processing Systems, volume 16, páginas 321–328. MIT Press. Citado

na pág. 92, 94


Zhou(2003a) H. Zhou. Distance, dissimilarity index, and network community struc-ture. Phys. Rev. E, 67(6):061901. Citado na pág. 2, 20

Zhou(2003b) Haijun Zhou. Network landscape from a brownian particle’s perspective.Physical Review E, 67(4):041908. Citado na pág. 4, 7

Zhu(2005a) X. Zhu. Semi-supervised learning with graphs. Tese de Doutorado - CarnegieMellon University. CMU-LTI-05-192. Citado na pág. 31, 32, 36

Zhu e Ghahramani(2002) X. Zhu e Z. Ghahramani. Learning from labeled and unla-beled data with label propagation. Relatório Técnico CMU-CALD-02-107, CarnegieMellon University, Pittsburgh. Citado na pág. 94

Zhu e Goldberg(2009) X. Zhu e A. B. Goldberg. Introduction to Semi-Supervised Learning.Morgan and Claypool Publishers, Synthesis Lectures on Artificial Intelligence andMachine Learning. Citado na pág. 32, 33

Zhu(2005b) Xiaojin Zhu. Semi-supervised learning literature survey. Relatório Técnico1530, Computer Sciences, University of Wisconsin-Madison. Citado na pág. 31, 34

Zhu et al.(2003) Xiaojin Zhu, Zoubin Ghahramani, e John Lafferty. Semi-supervisedlearning using gaussian fields and harmonic functions. Em In ICML, páginas 912–919. Citado na pág. 45


Documents

Aprendizado semissupervisionado via competição de partículas em redes complexas: modelagem, análise e aplicações