MAC499 - Trabalho de Formatura Supervisionado

Estudo de máquinas de suporte vetorial e sua aplicação na detecção de spam

Aluno: Antonio Carlos dos Santos (acsantos at linux.ime.usp.br)
Supervisor: Paulo José de Silva e Silva (pjssilva at ime.usp.br)
Tipo de Trabalho: Iniciação Científica

Introdução

Com o uso cada vez maior da Internet, a troca de mensagens eletrônicas, os e-mails, tornou-se uma ação muito frequente entre seus usuários, inclusive para discutir assuntos profissionais. Atualmente, segundo [6], aproximadamente um bilhão de mensagens eletrônicas são enviadas pela Web diariamente em todo o mundo.

Entretanto, o número de mensagens indesejadas recebidas, os spams (Stupid Pointless Annoying Messages), também é muito grande. Apenas o CERT (Centro de Estudos, Resposta e Tratamento de Incidentes no Brasil), de janeiro até o final de maio de 2005, foi notificado sobre mais de um bilhão de spams. E o site SpamCop.net detectou aproximadamente 10,7 bilhoões de spams apenas no último mês. Esta situação gera vários problemas, tanto para empresas provedoras de acesso à Internet, que têm uma carga maior de uso de seus servidores, quanto para os usuários, que gastam tempo lendo spams para depois descartá-los, e podem ainda serem prejudicados através de vírus e spywares. Segundo a empresa americana de consultoria Ferris Research, as perdas com spams chegarão a US$50 bilhões em 2005, principalmente devido à queda de produtividade dos funcionarios.

Assim, para evitar tais problemas, atualmente tem-se pesquisado bastante novas formas de detectar e bloquear mensagens consideradas spams automaticamente. Entre elas, está o uso de máquinas de suporte vetorial.

Máquinas de suporte vetorial, em inglês Support Vector Machines (SVM), são um novo conceito na área de sistemas de aprendizado computacional, baseadas na teoria de aprendizado estatístico, desenvolvida principalmente por Vladimir Vapnik. SVMs têm apresentado bom desempenho em várias aplicações, como, por exemplo, classificação de sequências de DNA e reconhecimento de imagens, e possuem um grande potencial para serem aplicadas em outras áreas.


Objetivos

O objetivo do projeto será, principalmente, estudar máquinas de suporte vetorial, e como elas podem ser aplicadas na detecção de spams.

Inicialmente, estudaremos os principais conceitos envolvidos na teoria das SVMs, como por exemplo, representações primal e dual, kernel e espaços de características. Em seguida, veremos detalhes envolvidos com a implementação do algoritmo e analisaremos algumas aplicações já conhecidas de SVMs. Finalmente, estudaremos a aplicação dos conceitos vistos na detecção de spams, realizando alguns experimentos.


Atividades já realizadas

Até o momento já foram realizadas as seguintes atividades:

  • Estudo dos conceitos básicos de aprendizado computacional, principalmente classificação linear
  • Estudo, implementação e análise do algoritmo de Rosenblatt
  • Estudo das representações primal e dual de máquinas lineares
  • Estudo do espaço de características (feature space) e do mapeamento entre um espaço de entrada e um espaço de características.
  • Análise do conceito de kernel
  • Análise do teorema de Mercer

Cronogramas das atividades a serem realizadas no segundo semestre

Durante todo o segundo semestre, a monografia estará sendo escrita e, além disso, as seguintes atividades estão planejadas:

Julho:
  • Continuação do estudo de kernels em SVMs
  • Início do estudo de aprendizado estatístico
  • Estudo da teoria de Vapnik-Chervonenkis
  • Abordagem dos conceitos de aprendizagem bayesiano

Agosto:

  • Estudo da teoria de otimização, principalmente a teoria dos lagrangianos
  • Estudo detalhado de máquinas de suporte vetorial, principalmente as lineares

Setembro:

  • Continuação do estudo de kernels em SVMs
  • Início do estudo de aprendizado estatístico
  • Estudo da teoria de Vapnik-Chervonenkis
  • Abordagem dos conceitos de aprendizagem bayesiano

Outubro:

  • Continuação do estudo detalhado de máquinas de suporte vetorial, principalmente regressão de suporte vetorial.
  • Análise das técnicas de implementação de SVMs e de suas aplicações mais conhecidas
  • Implementação de SVMs para detecção de spam

Novembro:

  • Continuação do processo de implementação
  • Realização de testes para avaliar o desempenho e corretude da implementação
  • Criação do pôster, da apresentação e término da monografia

Estrutura esperada da monografia

A parte técnica da monografia seguirá a estrutura proposta pelas agências de fomento para relatórios. Assim, a monografia possuirá os seguintes itens:

  • Introdução
  • Objetivos do trabalho
  • Trabalhos correlatos existentes na área
  • Teorias e sistemas estudados
  • Atividades realizadas
  • Resultados obtidos
  • Conclusões
  • Bibliografia

A segunda parte da monografia será sobre a experiência obtida na iniciação científica e no bacharelado de Ciência da Computação (BCC). Conterá os seguintes itens:

  • Desafios e frustações encontrados
  • Disciplinas cursadas no BCC mais relevantes para a iniciação
  • Interação com o orientador
  • Diferenças entre a forma de trabalho na realização de trabalhos de disciplinas do BCC e a forma de trabalho no projeto
  • Observações sobre a aplicação de conceitos vistos no curso e na iniciação em aplicações reais
  • Quais atitudes tomaria se fosse continuar atuando na área
  • Conclusões

Bibliografia

[1] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based methods. Cambridge University Press, 2002.

[2] C. J. C. Burges. A tutorial on support vector machines for pattern recognition.Data mining and Knowledge Discovery, 1998.

[3] J. W. Eaton. Octave Manual. Network Theory Ltd., 2002.

[4] D. S. Watkins. Fundamentals of Matrix Computations. John Wiley & Sons, 1991.

[5] http://www.nbso.nic.br. Acesso em julho de 2005.

[6] http://www.spancop.net Acessado em julho de 2005.