Prévia do material em texto

<p>Sistemas Inteligentes</p><p>Sistemas Inteligentes</p><p>Sumário</p><p>1 Introdução à Inteligência Artificial .........................................1</p><p>2 Conhecimento ......................................................................8</p><p>3 Sistemas Baseados em Regras .............................................23</p><p>4 Sistemas Baseados em Casos ..............................................32</p><p>5 Sistemas de Recomendação ................................................53</p><p>6 Sistemas Multiagente ..........................................................73</p><p>7 Teoria dos Jogos .................................................................90</p><p>8 Algoritmos Genéticos ........................................................102</p><p>9 Redes Neurais Artificiais ....................................................119</p><p>10 Exemplos de Implementações de Sistemas ........................134</p><p>Introdução à</p><p>Inteligência Artificial1</p><p>Apresentação</p><p>A Inteligência Artificial (IA) é apresentada como uma área da</p><p>Ciência da Computação que enfatiza o estudo de sistemas</p><p>inteligentes, ou seja, sistemas que apresentam características</p><p>associadas à inteligência no comportamento humano, tais</p><p>como, compreensão de linguagem, aprendizagem, raciocínio</p><p>e resolução de problemas.</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 1</p><p>2 Sistemas Inteligentes</p><p>Este capítulo tem como objetivo ajudar o aluno a entender</p><p>um pouco do que é a Inteligência Artificial.</p><p>O termo Inteligência Artificial foi criado em 1956 por John</p><p>McCarthy no Massachusetts Institute of Technology (MIT) como</p><p>título de uma conferência sobre as possibilidades de fornecer</p><p>inteligência à máquina. Segundo ele, IA é a capacidade de</p><p>uma máquina de realizar funções que se fossem realizadas</p><p>pelo ser humano seriam consideradas inteligentes.</p><p>Outros autores também apresentaram o conceito de IA,</p><p>como, por exemplo:</p><p>Elaine Rich: “IA é o estudo de como fazer os computa-</p><p>dores realizarem coisas que, hoje são feitas melhores pelas</p><p>pessoas”.</p><p>Winston: “IA é o estudo das ideias que permitem aos com-</p><p>putadores serem inteligentes”.</p><p>Russel e Norvig: “IA é o estudo e implementação de agen-</p><p>tes racionais”.</p><p>Pode-se dizer que a IA tem como objetivo:</p><p>Teórico: a criação de teorias e modelos para a capacidade</p><p>cognitiva.</p><p>Prático: a implementação de sistemas computacionais ba-</p><p>seados nesses modelos.</p><p>Pode-se dizer que a IA corresponde a um conjunto de téc-</p><p>nicas interdisciplinares que busca implementar sistemas e pro-</p><p>cessos em domínios que não possuem tratamento algorítmico.</p><p>Capítulo 1 Introdução à Inteligência Artificial 3</p><p>Sistemas que utilizam técnicas de IA são normalmente mais</p><p>flexíveis e adaptáveis ao usuário e capazes de processar infor-</p><p>mações simbólicas.</p><p>Existem várias abordagens na área da IA, nas quais variam</p><p>a manipulação do conhecimento, no sentido de como adquiri-</p><p>-lo, armazená-lo ou utilizá-lo.</p><p>A Figura 1 apresenta uma classificação para as diferentes</p><p>subáreas de IA, quanto ao método de solução de problemas e</p><p>quanto à localização espacial:</p><p>Figura 1.1: Subáreas da Inteligência Artificial.</p><p>Quanto ao método de solução de problemas, tem-se a IA</p><p>Simbólica, a IA Conexionista, a IA Evolucionária e a IA</p><p>Híbrida.</p><p>A IA Simbólica possui a lógica como ferramenta básica</p><p>para manipular o conhecimento.</p><p>4 Sistemas Inteligentes</p><p>A IA Conexionista usando Redes Neurais Artificiais (RNA),</p><p>aplica-se a problemas mal definidos, mas que são conhecidos</p><p>por meio de exemplos. Entre os campos de aplicações das</p><p>técnicas conexionistas estão o reconhecimento de padrões,</p><p>controle de processos industriais, robótica.</p><p>Na IA Evolucionária, os mecanismos utilizados são os mes-</p><p>mos encontrados na evolução biológica. A IA Híbrida reúne</p><p>vantagens de mais de um tipo de abordagem para a resolução</p><p>do problema.</p><p>Tanto a IA Simbólica quanto a IA Conexionista podem ser</p><p>utilizadas em vários tipos de aplicações, porém, em alguns</p><p>casos, existem particularidades que podem tornar uma mais</p><p>atrativa do que a outra.</p><p>Quanta à localização espacial, tem-se a IA Monolítica e a</p><p>IA Distribuída.</p><p>A IA Monolítica envolve sistemas simples sem modularida-</p><p>de, como, por exemplo, os sistemas especialistas (baseados</p><p>em regras).</p><p>Já o funcionamento da IA Distribuída depende de um de-</p><p>terminado conjunto de partes (ou módulos) para resolver de</p><p>modo cooperativo um determinado tipo de problema.</p><p>1.1 Subáreas da IA</p><p>Dentro da IA podemos encontrar diferentes subáreas, como,</p><p>por exemplo:</p><p>Capítulo 1 Introdução à Inteligência Artificial 5</p><p>a) Resolução de problemas (planejamento)</p><p>Â Quebra-cabeça, jogos.</p><p>Â Problemas que requerem conhecimento especialista</p><p>(diagnóstico médico, localização de recursos minerais,</p><p>configuração de computadores).</p><p>b) Percepção (visão e fala)</p><p>Â Reconhecimento de objetos por meio de imagens.</p><p>Â Reconhecimento de voz ou identificação de imagens.</p><p>c) Processamento de linguagem natural</p><p>Â O que significa um conjunto de palavras.</p><p>Â Tradução de idiomas.</p><p>d) Extração de conhecimento</p><p>Â Descoberta de conhecimento.</p><p>e) Aprendizado</p><p>Â Desenvolver sistemas que melhorem seu desempenho a</p><p>partir de experiências.</p><p>Â Desenvolver sistemas que auxiliem no aprendizado de</p><p>alunos.</p><p>f) Programação</p><p>Â Distribuição da resolução de problemas.</p><p>Â Sistemas multiagentes.</p><p>6 Sistemas Inteligentes</p><p>1.2 Algumas diferenças entre a Inteligência</p><p>Artificial e a computação convencional</p><p>É importante perceber as diferenças entre a computação con-</p><p>vencional e a utilização de técnicas da Inteligência Artificial</p><p>para compreender quando é necessária a utilização destas. As</p><p>diferenças podem existir considerando o processo de solução,</p><p>o processamento e os métodos de solução.</p><p>Na computação convencional, o processo de solução de</p><p>problema é determinístico, ou seja, é possível construir um al-</p><p>goritmo para definir os passos de solução do problema. Na</p><p>IA, o processo da solução é não determinístico: os passos de</p><p>solução do problema são desconhecidos e buscados por ten-</p><p>tativa e erro, durante o processamento.</p><p>Em relação ao processamento, na computação convencio-</p><p>nal, ele é principalmente numérico. Na IA, o processamento é</p><p>fundamentalmente simbólico.</p><p>Quanto aos métodos de programação, na computação</p><p>convencional, eles são impessoais, ou seja, o resultado inde-</p><p>pende do programador. Já na IA os métodos de programação</p><p>são pessoais e o resultado depende do programador que for-</p><p>nece o método de solução do problema.</p><p>Por fim, na computação convencional, os métodos de so-</p><p>lução são codificados no programa e dificilmente modificados</p><p>posteriormente. Na IA, o método de solução é fornecido com</p><p>os dados e pode ser adaptado.</p><p>Capítulo 1 Introdução à Inteligência Artificial 7</p><p>Os próximos capítulos deste livro apresentam algumas</p><p>abordagens dessas subáreas apresentadas. O Capítulo 2</p><p>apresenta um conceito de muita importância na IA simbólica:</p><p>conhecimento. O Capítulo 3 apresenta os sistemas baseados</p><p>em regras e o Capítulo 4 apresenta os sistemas baseados em</p><p>casos, ambos pertencentes a IA simbólica. O Capítulo 5 apre-</p><p>senta os sistemas de recomendação.</p><p>O Capítulo 6 introduz os sistemas multiagente, pertencen-</p><p>tes a IA distribuída. O Capítulo 7 apresenta os conceitos de te-</p><p>oria dos jogos, que são utilizados pelos sistemas multiagente.</p><p>Já o Capítulo 8 apresenta os algoritmos genéticos, pertencen-</p><p>tes a IA evolucionária. A IA conexionista está representada no</p><p>Capítulo 9, que introduz as redes neurais. Por fim, o Capítulo</p><p>10 apresenta exemplos de implementações de algumas das</p><p>abordagens vistas.</p><p>Recapitulando</p><p>Este capítulo apresentou as diferentes áreas que fazem parte</p><p>da Inteligência Artificial e o que cada uma dessas áreas tenta</p><p>solucionar.</p><p>Conhecimento1</p><p>Apresentação</p><p>Este capítulo tem como objetivo introduzir os leitores no mun-</p><p>do de sistemas baseados em conhecimento. Esses sistemas uti-</p><p>lizam conhecimento especialista para resolver problemas que,</p><p>normalmente, são resolvidos pelo</p><p>as preferências do usuário. Esses sistemas sabem como</p><p>um determinado produto se encaixa na necessidade de um</p><p>usuário específico e são capazes de raciocinar sobre a relação</p><p>entre uma necessidade e uma possível recomendação.</p><p>A principal vantagem da abordagem baseada em conheci-</p><p>mento é que ela não depende das avaliações prévias de outros</p><p>clientes, evitando a dificuldade inicial do sistema (cold start). O</p><p>conhecimento pode ser expresso como um modelo de usuário</p><p>detalhado, um modelo de processo de seleção ou uma descri-</p><p>ção de itens que serão sugeridos.</p><p>Conforme apresentado em (Ricci et al., 2011), nos Siste-</p><p>mas de Recomendação Baseados em Conhecimento, o co-</p><p>nhecimento pode ser expresso como um modelo detalhado do</p><p>usuário, um modelo de um processo de seleção ou a descri-</p><p>ção de itens que serão sugeridos ao cliente.</p><p>Capítulo 5 Sistemas de Recomendação 67</p><p>Um dos primeiros sistemas de recomendação baseados</p><p>em conhecimento é o Entrée, apresentado em (Torres, 2004).</p><p>Ele é um sistema de recomendação de restaurantes que provê</p><p>recomendações, encontrando restaurantes parecidos com os</p><p>que o usuário conhece e gosta, porém em uma nova cidade.</p><p>A abordagem empregada nesse sistema permite que ele res-</p><p>ponda questões do tipo “Para que restaurante parecido com o</p><p>restaurante X eu poderia ir?”. O sistema permite que o usuário</p><p>critique as recomendações apresentadas a ele com o objetivo</p><p>de modificar a consulta inicial.</p><p>Sistemas de recomendação baseados em casos (SRBC) uti-</p><p>lizam a abordagem de Raciocínio Baseado em Casos (RBC),</p><p>onde o conhecimento é representado a partir de casos na base</p><p>de casos. O conhecimento pode ser sobre os produtos, os usu-</p><p>ários, as sessões de recomendação, sobre a avaliação do usu-</p><p>ário sobre produtos ou até mesmo uma mistura de todos esses</p><p>exemplos.</p><p>No processo de recomendação básico desse tipo de siste-</p><p>ma, o usuário está procurando por algum produto para com-</p><p>prar, e o sistema solicita suas preferências. Com essas infor-</p><p>mações o sistema inicia uma busca na base de casos para</p><p>identificar produtos que possam ser recomendados, ou seja,</p><p>aqueles produtos que satisfazem as preferências desse usuário.</p><p>Nesse processo, pode-se identificar alguns elementos básicos,</p><p>como a entrada (onde o usuário informa suas preferências), a</p><p>recuperação de produtos (onde o sistema procura os produtos</p><p>de acordo com as preferências do usuário) e a saída (onde</p><p>alguma recomendação é apresentada ao usuário).</p><p>68 Sistemas Inteligentes</p><p>A Figura 5.5 apresenta o ciclo de funcionamento de um</p><p>sistema de recomendação baseado em casos definido em</p><p>(Lorenzi & Ricci, 2005). A partir de um novo problema, o</p><p>sistema recupera da base os casos mais similares. Esses ca-</p><p>sos recuperados são recomendados ao usuário. Quando as</p><p>soluções do caso apresentado precisam de alguma modifica-</p><p>ção, é realizada a etapa de adaptação. A solução adaptada</p><p>passa pelo processo de revisão e após pode ser inserida na</p><p>base como um novo caso (etapa de retenção e também cha-</p><p>mada de aprendizado). O último passo desse processo é a</p><p>interação com o usuário, onde este pode criticar o resultado</p><p>apresentado pelo sistema.</p><p>Figura 5.5: Ciclo de funcionamento de um sistema de recomendação</p><p>baseado em casos (Lorenzi & Ricci, 2005).</p><p>Capítulo 5 Sistemas de Recomendação 69</p><p>Recapitulando</p><p>Este capítulo apresentou os sistemas de recomendação, bem</p><p>como as técnicas de recomendação que podem ser utilizadas.</p><p>Os sistemas de recomendação são utilizados para que seja</p><p>possível recomendar opções mais direcionadas ao perfil do</p><p>usuário, resolvendo o problema da existência de muita infor-</p><p>mação na Internet.</p><p>Referências bibliográficas</p><p>ADOMAVICIUS, G.; TUZHILIN, A. Toward the Next Generation</p><p>of Recommender Systems: a survey of the state-of-the-art</p><p>and possible extensions. IEEE Transactions on Knowledge</p><p>and Data Engineering, Piscataway, NJ, USA, v. 17, n. 6, p.</p><p>734-749, 2005.</p><p>BILLSUS, D.; PAZZANI, M. A Hybrid User Model for News Story</p><p>Classification. In: SEVENTH INTERNATIONAL CONFEREN-</p><p>CE ON USER MODELING, UM ’99, Banff, Canada. Proce-</p><p>edings. . . [S.l.: s.n.], 1999.</p><p>BURKE, R. Knowledge-based Recommender Systems. In: DAILY,</p><p>J. E.; KENT, A.; LANCOUR, H. (Ed.). Encyclopedia of Library</p><p>and Information Science. [S.l.]: Marcel Dekker, 2000. v. 69.</p><p>LORENZI, F.; RICCI, F. Case-based recommender systems: a</p><p>unifying view. In: INTELLIGENT TECHNIQUES FOR WEB</p><p>PERSONALIZATION. Anais. . . Springer Verlag, 2005. p.</p><p>89-113.</p><p>MILLER, B. et al. MovieLens Unplugged: experiences with an</p><p>occasionally connected recommender system. In: ACM</p><p>70 Sistemas Inteligentes</p><p>2003 INTERNATIONAL CONFERENCE ON INTELLIGENT</p><p>USER INTERFACES (IUI’03), Chapel Hill, North Carolina.</p><p>Proceedings. ACM Press, 2003.</p><p>RICCI, F.; ROKACH, L.; SHAPIRA, B.; KANTOR, P.B. Recom-</p><p>mender Systems Handbook. 1. Ed. Springer , 2011.</p><p>TORRES, Roberto. Personalização na Internet: como descobrir</p><p>os hábitos de consumo de seus usuários, fidelizá-los e au-</p><p>mentar o lucro de seu negócio. São Paulo: Novatec, 2004.</p><p>Atividades</p><p>1) É considerado um objetivo de um Sistema de Recomenda-</p><p>ção...</p><p>a) … sugerir produtos ao usuário de acordo com o quanto</p><p>ele tem para gastar.</p><p>b) … sugerir produtos ao usuário de acordo com os produ-</p><p>tos disponíveis para venda.</p><p>c) … sugerir produtos ao usuário de acordo com suas pre-</p><p>ferências, auxiliando o usuário na grande quantidade de</p><p>informações disponíveis.</p><p>d) … sugerir produtos ao usuário de acordo com as entre-</p><p>vistas realizadas.</p><p>e) nenhuma das alternativas anteriores.</p><p>2) É considerada uma técnica de recomendação.</p><p>a) Filtragem colaborativa.</p><p>Capítulo 5 Sistemas de Recomendação 71</p><p>b) Filtragem baseada em dados.</p><p>c) Filtragem baseada em vídeos.</p><p>d) Entrevistas estruturadas.</p><p>e) Nenhuma das alternativas anteriores.</p><p>3) A técnica de filtragem colaborativa considera...</p><p>a) … os produtos que o usuário já viu ou comprou.</p><p>b) ... o perfil do usuário com os outros usuários do sistema.</p><p>c) … os casos que já aconteceram.</p><p>d) … os produtos e os casos que já aconteceram com o</p><p>usuário.</p><p>e) nenhuma das alternativas anteriores.</p><p>4) É considerado um problema da técnica de filtragem cola-</p><p>borativa:</p><p>a) Falta de dados sobre o produto recomendado.</p><p>b) Cold-start.</p><p>c) Ovelha negra.</p><p>d) Falta de dados dos produtos comprados.</p><p>e) Nenhuma das alternativas anteriores.</p><p>5) Que técnica é considerada complementar às técnicas de</p><p>filtragem colaborativa e filtragem baseada em conteúdo?</p><p>a) Filtragem baseada em perfil.</p><p>72 Sistemas Inteligentes</p><p>b) Filtragem baseada em conhecimento.</p><p>c) TF-IDF.</p><p>d) Recuperação de casos.</p><p>e) Nenhuma das alternativas anteriores.</p><p>Gabarito</p><p>1) c</p><p>2) a</p><p>3) b</p><p>4) b</p><p>5) b</p><p>Sistemas Multiagente1</p><p>Apresentação</p><p>Este capítulo apresenta os principais conceitos envolvidos na</p><p>IA distribuída, onde o principal ator é o agente.</p><p>Durante muito tempo, os pesquisadores da área da IA pro-</p><p>curaram desenvolver agentes isolados com algum comporta-</p><p>mento inteligente. Segundo (Wooldridge, 2002) um agente é</p><p>uma entidade real ou virtual, imersa em um ambiente onde</p><p>ele pode agir e no qual ele possui percepção e representação</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 6</p><p>74 Sistemas Inteligentes</p><p>parcial desse ambiente. Porém, o desenvolvimento de compu-</p><p>tadores com maior poder de processamento, o aumento da</p><p>complexidade das redes de computadores e a necessidade de</p><p>resolver os problemas de forma distribuída fizeram a Inteligên-</p><p>cia Artificial Distribuída (IAD) se tornar uma área de grande</p><p>importância.</p><p>Uma das motivações para o crescimento da IAD é a possi-</p><p>bilidade de resolver problemas que não podem ser resolvidos</p><p>de forma centralizada (por limitação de recursos ou desempe-</p><p>nho).</p><p>A IAD é tradicionalmente dividida em duas áreas: Resolu-</p><p>ção Distribuída de Problemas (RDP) e sistemas multiagentes</p><p>(SMA).</p><p>6.1 Resolução Distribuída de Problemas</p><p>A Resolução Distribuída de Problemas (RDP) tem como objeto</p><p>principal o problema a ser</p><p>resolvido, ou seja, o centro de tudo</p><p>é a solução de um problema particular. Nesse tipo de sistema,</p><p>os agentes são programados para realizar tarefas específicas e</p><p>comunicar-se com outros agentes da sociedade para resolver</p><p>o problema global.</p><p>O mecanismo funciona como se o problema global fosse</p><p>subdividido em vários subproblemas (como um quebra-cabe-</p><p>ça, por exemplo) e cada agente trata um subproblema.</p><p>Capítulo 6 Sistemas Multiagente 75</p><p>6.2 Sistemas Multiagente</p><p>Os Sistemas Multiagente (SMAs) são compostos por vários</p><p>agentes autônomos que interagem uns com os outros. Agentes</p><p>autônomos possuem determinação própria e decidem o que</p><p>devem fazer e quando devem realizar tarefas. Eles têm a habili-</p><p>dade de decidir quais objetivos terão que cumprir e que ações</p><p>deverão realizar para atingir esses objetivos.</p><p>Os agentes autônomos exibem duas características funda-</p><p>mentais: são capazes de agir de forma autônoma, o que leva à</p><p>tomada de decisões para atingir seus objetivos, e são capazes</p><p>de interagir com outros agentes utilizando protocolos de inte-</p><p>ração social inspirados nos humanos.</p><p>Os agentes em um SMA são projetados para resolver</p><p>qualquer tipo de problema e não um problema em específico</p><p>como acontece na RPD. Isso se deve, basicamente, porque,</p><p>nos SMAs, esses agentes são entidades autônomas que têm</p><p>conhecimento da sua própria existência e da existência de ou-</p><p>tros agentes e, dessa forma, colaboram uns com os outros</p><p>para atingirem um objetivo comum dentro de um ambiente.</p><p>Nos SMAs, os agentes representam a parte central e de-</p><p>vem se comunicar e trocar conhecimento para obter a solução</p><p>de problemas antes desconhecidos, ou seja, o problema pode</p><p>surgir após a construção da arquitetura do sistema. Assim, o</p><p>problema não é necessariamente específico e o processo de</p><p>coordenação das ações dos agentes ocorre em tempo de exe-</p><p>cução.</p><p>76 Sistemas Inteligentes</p><p>Um SMA possui algumas características, como, por exem-</p><p>plo:</p><p>Â Cada agente tem informação ou capacidade incomple-</p><p>tas, ou seja, visão limitada para resolver o problema.</p><p>Â Não existe um controle global do sistema.</p><p>Â Os dados são descentralizados.</p><p>Os SMAs podem possuir algumas das seguintes funciona-</p><p>lidades: comunicação, coordenação e negociação (coope-</p><p>rativa ou competitiva).</p><p>Comunicação entre os agentes</p><p>Para o completo funcionamento de um SMA, é necessário um</p><p>protocolo ou uma linguagem de comunicação para que os</p><p>agentes se entendam, ou seja, para que os agentes tenham</p><p>uma linguagem comum. O objetivo do processo de comuni-</p><p>cação é a troca de informações.</p><p>Uma linguagem que vem sendo utilizada na comunica-</p><p>ção entre os agentes é a KQML (Knowledge Query and Mani-</p><p>pulation Language). KQML é uma linguagem projetada para</p><p>suportar interações entre agentes inteligentes. Ela foi desen-</p><p>volvida pelo ARPA no Programa de Compartilhamento de</p><p>Informações e implementada independentemente por vários</p><p>grupos de pesquisa.</p><p>Capítulo 6 Sistemas Multiagente 77</p><p>Coordenação entre os agentes</p><p>A coordenação entre os agentes é necessária para evitar o</p><p>caos entre os agentes. Como os SMAs preveem vários agentes</p><p>envolvidos em um ambiente normalmente complexo, conflitos</p><p>acabam acontecendo. Por essa razão, a coordenação é um</p><p>processo muito importante nos SMAs.</p><p>Quando agentes autônomos trabalham para cumprir de-</p><p>terminado objetivo, eles devem agir como uma unidade, coor-</p><p>denando suas ações, compartilhando recursos ou minimizan-</p><p>do esforços.</p><p>Rede de Contrato (Contract Net)</p><p>A técnica Rede de Contratos (Contract Net) é um protocolo de</p><p>interação para solução de problemas de forma interativa entre</p><p>agentes. Se um agente não consegue resolver o problema com</p><p>seus recursos locais, ele decompõe o problema em subpro-</p><p>blemas e tenta encontrar outros agentes para resolver esses</p><p>problemas. Os agentes podem assumir o papel de contratante</p><p>ou contratado.</p><p>Conforme apresentado na Figura 6.1, inicialmente, um</p><p>contratante (que geralmente tem uma tarefa a ser executada e</p><p>não tem recursos suficientes) abre um edital e convida outros</p><p>agentes para a elaboração de propostas para execução dessa</p><p>tarefa. Os agentes dispostos a aceitar a proposta retornam</p><p>com ofertas. O contratante atribui a tarefa ao agente que fez</p><p>a melhor oferta.</p><p>78 Sistemas Inteligentes</p><p>Figura 6.1: Exemplo de rede de contrato.</p><p>Negociação entre os agentes</p><p>Devido à falta de visão e conhecimento globais, os SMAs são</p><p>passíveis de falhas e inconsistências nos objetivos dos agen-</p><p>tes. Para que os agentes atinjam seus objetivos, resolvendo os</p><p>problemas de forma coerente, essas falhas devem ser resolvi-</p><p>das. A principal abordagem para resolver esses problemas em</p><p>SMAs é a negociação.</p><p>Capítulo 6 Sistemas Multiagente 79</p><p>A negociação é vista como um método para resolução de</p><p>conflitos entre os agentes. Segundo (Sycara, 1988), algumas</p><p>características são necessárias nos SMAs para que haja nego-</p><p>ciação:</p><p>Â A presença de algum tipo de conflito que pode ser resol-</p><p>vido de forma descentralizada.</p><p>Â Racionalidade limitada.</p><p>Â Informação incompleta.</p><p>Normalmente, na negociação, os agentes se comunicam e</p><p>trocam propostas e contrapropostas em várias iterações. Dada</p><p>a importância da negociação, várias pesquisas têm se concen-</p><p>trado no desenvolvimento de negociações automáticas entre</p><p>agentes, como, por exemplo, modelos de leilões, negociações</p><p>diretas (agente a agente) ou negociações baseadas em argu-</p><p>mentações.</p><p>Negociação é o processo onde duas ou mais partes tomam</p><p>uma decisão em conjunto (Zhang et al., 2005). Na negocia-</p><p>ção de agentes, eles primeiro verbalizam o pedido e então</p><p>buscam um acordo com outros agentes, fazendo contrapro-</p><p>postas e tentando novas alternativas.</p><p>O processo de negociação é acionado quando o agente</p><p>percebe que ele não é a melhor opção na realização de uma</p><p>tarefa. Pode ser que esse agente esteja sobrecarregado, que</p><p>ele não tenha capacidade de realizar a tarefa localmente ou</p><p>até mesmo que outro agente possa realizar a tarefa com mais</p><p>qualidade do que ele. A negociação pode trazer as seguintes</p><p>vantagens ao SMA:</p><p>80 Sistemas Inteligentes</p><p>Â Melhorar a qualidade das soluções.</p><p>Â Melhorar a eficiência em atingir os objetivos.</p><p>Â Resolver tarefas que não podem ser resolvidas pelo</p><p>agente.</p><p>No momento em que o agente precisa realizar a tarefa, ele</p><p>avalia a utilidade (custo e tempo) de realização dessa tarefa</p><p>e decide se ele mesmo realizará ou se inicia o processo de</p><p>negociação com outros agentes. A negociação pode ser clas-</p><p>sificada em dois tipos: colaborativa e competitiva.</p><p>A negociação cooperativa (também conhecida como ne-</p><p>gociação colaborativa) é um processo onde são encontradas</p><p>alternativas de ganho comum, que atendam aos interesses de</p><p>todas as partes. Pode ser vista também como um processo de</p><p>busca distribuído onde os agentes tentam atingir a utilidade</p><p>global máxima que leva em conta o quanto às atividades de</p><p>cada agente valem a pena.</p><p>Já a negociação competitiva ocorre entre agentes onde</p><p>cada um tenta maximizar sua utilidade local, ou seja, os resul-</p><p>tados de uma das partes são prejudicados em relação à outra.</p><p>Nesse tipo de negociação, as partes assumem algum conflito</p><p>de interesses. O grau de incompatibilidade nos objetivos e os</p><p>métodos para lidar com os conflitos determinam as estratégias</p><p>a serem adotadas pelos agentes em diferentes circunstâncias.</p><p>Os agentes visam seu próprio ganho, não considerando o</p><p>grande grupo. Esse tipo de negociação se identifica como um</p><p>jogo de soma zero, ou seja, o ganho de um jogador é a perda</p><p>do outro. Um exemplo é a negociação do preço de um pro-</p><p>Capítulo 6 Sistemas Multiagente 81</p><p>duto entre um comprador e um vendedor, onde as duas partes</p><p>possuem objetivos antagônicos: o comprador quer o menor</p><p>preço e o vendedor persegue o maior.</p><p>Dependendo do tipo de negociação, os agentes se com-</p><p>portam de forma diferente. Em um ambiente competitivo, o</p><p>agente precisa ser ágil e ficar atento ao tempo que ele possui</p><p>para negociar. Já em um ambiente colaborativo, a negociação</p><p>acontece com outros</p><p>agentes da sua própria comunidade.</p><p>6.3 Tipos de agentes</p><p>Segundo (Wooldridge, 2002), um agente é uma entidade real</p><p>ou virtual, imersa em um ambiente onde ele pode agir e no</p><p>qual ele possui percepção e representação parcial desse am-</p><p>biente.</p><p>As propriedades dos agentes e sua intensidade caracteri-</p><p>zam seu comportamento dentro de uma sociedade.</p><p>Algumas propriedades que podem ser encontradas nos</p><p>agentes são:</p><p>Â Autonomia: é a capacidade de executar ações, com o</p><p>objetivo de executar suas tarefas, sem a interferência do</p><p>usuário final.</p><p>Â Mobilidade: é a capacidade de se transportar de uma</p><p>máquina para outra.</p><p>82 Sistemas Inteligentes</p><p>Â Comunicabilidade: é a capacidade do agente de se</p><p>comunicar com outros agentes.</p><p>Â Aprendizagem: é a capacidade de alterar seu compor-</p><p>tamento baseado em experiências prévias.</p><p>Â Reatividade: reage às mudanças no ambiente.</p><p>Â Pró-atividade: é a capacidade de não responder so-</p><p>mente ao ambiente, mas sim perseguir seu objetivo.</p><p>Â Comportamento Adaptativo: capacidade do agente</p><p>de modificar seu comportamento em função de experi-</p><p>ências anteriores.</p><p>Â Discurso: propriedade onde o usuário e agente con-</p><p>cordam sobre o que deve ser feito e por quem deve ser</p><p>feito.</p><p>Â Flexibilidade: habilidade dos agentes em escolher que</p><p>ações e em que sequência deve tomá-las em resposta a</p><p>um evento do ambiente.</p><p>As arquiteturas de agentes podem ser classificadas em três</p><p>diferentes tipos (Wooldridge, 2002): arquitetura cognitiva (ou</p><p>deliberativa), arquitetura reativa (não deliberativa) e arquitetu-</p><p>ra híbrida.</p><p>Reativo (não deliberativo)</p><p>Um agente age em função apenas de seu conhecimento in-</p><p>terno, não levando em conta sua percepção. Nesse tipo de</p><p>Capítulo 6 Sistemas Multiagente 83</p><p>agente, a inteligência está no projetista e não no agente. Os</p><p>agentes reativos não modelam o mundo para determinar suas</p><p>ações. Eles são agentes simples que possuem um mapeamento</p><p>de situações e respostas associadas. Assim, quando um estado</p><p>ambiental ocorre, o agente executa a ação correspondente.</p><p>Esse processo é chamado de estímulo-resposta.</p><p>Figura 6.2: Arquitetura de um agente reativo (Russel & Norvig, 2004).</p><p>Como mostra a Figura 6.2, um agente é qualquer entidade que:</p><p>Â Percebe seu ambiente a partir de sensores (ex.: câmeras,</p><p>microfone, teclado).</p><p>Â Age sobre o ambiente a partir de atuadores (ex.: vídeo,</p><p>alto-falante, impressora, ftp, e-mail).</p><p>Pode-se dizer então que um agente decompõe:</p><p>84 Sistemas Inteligentes</p><p>Â Problema em percepções, ações, objetivo e ambiente (e</p><p>outros agentes).</p><p>Â Não possuem memória e, por esse motivo, não são ca-</p><p>pazes de planejar suas ações.</p><p>A Figura 6.3 apresenta o exemplo do Mundo do Aspirador</p><p>de Pó, inventado por Russel e Norwig (2004). Nesse mundo, o</p><p>ambiente é representado por apenas dois locais: os quadrados</p><p>A e B e o agente é o Aspirador de Pó.</p><p>Figura 6.3: Exemplo do agente aspirador de pó.</p><p>O agente aspirador de pó percebe em que quadrado está e</p><p>se existe sujeira no quadrado. Ele pode escolher o movimento</p><p>(esquerda ou direita) e se aspira a poeira ou se não faz nada.</p><p>A função do agente é:</p><p>Se o quadrado atual estiver sujo</p><p>Então</p><p>Aspirar</p><p>Capítulo 6 Sistemas Multiagente 85</p><p>Senão</p><p>Mover-se para o outro quadrado</p><p>Função agente-aspirador-pó (posição, estado): retorna uma</p><p>ação</p><p>Início</p><p>se estado=sujo</p><p>então</p><p>retornar Aspirar</p><p>senão</p><p>se posição = A</p><p>então</p><p>retornar Direita</p><p>senão</p><p>se posição = B</p><p>então</p><p>retornar Esquerda</p><p>senão</p><p>retornar fazer_nada</p><p>Fim</p><p>86 Sistemas Inteligentes</p><p>Cognitivo (deliberativo)</p><p>Um agente cognitivo tem seu comportamento determinado</p><p>pela sua própria experiência. Esse tipo de agente opera com</p><p>sucesso em qualquer ambiente e possui uma representação</p><p>explícita do ambiente e dos outros agentes, além de memória,</p><p>o que possibilita que ele planeje suas ações.</p><p>Esses agentes também são conhecidos como agentes autô-</p><p>nomos, ou seja, eles têm o controle de suas ações, executan-</p><p>do-as independentemente do que aconteça a sua volta.</p><p>Híbridos</p><p>A arquitetura híbrida mistura componentes das arquiteturas</p><p>cognitivas e reativas com o objetivo de torná-la mais adequa-</p><p>da e funcional para a construção de agentes.</p><p>Nesse tipo de arquitetura, os agentes são dotados de com-</p><p>portamento reativo com relação aos eventos que ocorrem no</p><p>ambiente e comportamento cognitivo onde existe uma defini-</p><p>ção simbólica do mundo para a tomada de decisões.</p><p>Recapitulando</p><p>Este capítulo introduziu o aluno na área de Inteligência Artifi-</p><p>cial Distribuída e apresentou o principal conceito da área: o</p><p>agente. Os tipos de agentes mais conhecidos são: reativo e</p><p>cognitivo.</p><p>Capítulo 6 Sistemas Multiagente 87</p><p>Referências bibliográficas</p><p>Russell, S. and Norvig, P. (2004). Inteligência Artificial. Cam-</p><p>pus, Rio de Janeiro, RJ.</p><p>SYCARA, K. Resolving goal conflicts via negotiation. In: SE-</p><p>VENTH NATIONAL CONFERENCE ON ARTIFICIAL IN-</p><p>TELLIGENCE, 1988. Proceedings. . . [S.l.:s.n.], 1988. p.</p><p>245-250.</p><p>ZHANG, X.; LESSER, V.; PODOROZHNY, R. Multi-Dimensio-</p><p>nal, Multistep Negotiation for task allocation in a coopera-</p><p>tive system. Autonomous Agentes and Multi-Agent Systems,</p><p>[S.l.], v. 10, n. 1, p. 5-40, 2005.</p><p>WOOLDRIDGE, M. J. An Introduction to MultiAgent Systems.</p><p>Chichester: John Wiley & Sons, 2002.</p><p>Atividades</p><p>1) Quanto à motivação da Inteligência Artificial Distribuída, é</p><p>correto afirmar que:</p><p>a) A ideia surgiu a partir dos sistemas baseados em co-</p><p>nhecimento, onde existe um especialista que resolve os</p><p>problemas.</p><p>b) A ideia surgiu a partir da necessidade de dividir as tare-</p><p>fas em vários computadores da empresa.</p><p>c) A ideia surgiu a partir da percepção de que alguns pro-</p><p>blemas não podem ser resolvidos de forma centralizada.</p><p>88 Sistemas Inteligentes</p><p>d) A ideia surgiu a partir da necessidade de existir um con-</p><p>trole centralizado sobre o conhecimento da empresa.</p><p>e) Nenhuma das alternativas anteriores.</p><p>2) As características básicas de um agente em um sistema mul-</p><p>tiagente são:</p><p>a) Comunicação, coordenação e envio.</p><p>b) Envio, coordenação e negociação.</p><p>c) Comunicação, coordenação e negociação.</p><p>d) Negociação, envio e comunicação.</p><p>e) Nenhuma das alternativas anteriores.</p><p>3) Não é uma característica de um agente reativo?</p><p>a) Age em função apenas de seu conhecimento interno,</p><p>não levando em conta sua percepção.</p><p>b) A inteligência está no projetista e não no agente.</p><p>c) Opera com sucesso em qualquer ambiente.</p><p>d) Baseia-se no processo estímulo-resposta.</p><p>e) Nenhuma das alternativas anteriores.</p><p>4) Quanto à coordenação entre os agentes, é correto afirmar que:</p><p>a) Sem coordenação, os agentes não conseguiriam se co-</p><p>municar.</p><p>b) Por meio da coordenação, não é possível evitar o caos</p><p>entre os agentes.</p><p>Capítulo 6 Sistemas Multiagente 89</p><p>c) A coordenação atrapalha o desempenho dos agentes.</p><p>d) A coordenação permite aumentar o desempenho dos</p><p>agentes.</p><p>e) Nenhuma das alternativas anteriores.</p><p>5) A negociação entre agentes pode ser classificada como:</p><p>a) Negociação imperativa.</p><p>b) Negociação cooperativa e competitiva.</p><p>c) Negociação baseada em casos.</p><p>d) Negociação baseada no histórico dos agentes.</p><p>e) Nenhuma das alternativas anteriores.</p><p>Gabarito</p><p>1) c</p><p>2) c</p><p>3) c</p><p>4) d</p><p>5) b</p><p>Teoria dos Jogos1</p><p>Apresentação</p><p>Este capítulo introduz o tema de “teoria dos jogos” e como ele</p><p>pode ser aplicado no desenvolvimento de sistemas multiagentes.</p><p>Teoria dos jogos é o estudo matemático de decisões in-</p><p>terativas, onde aqueles que tomam as decisões são afetados</p><p>tanto pelas suas próprias escolhas quanto pelas decisões dos</p><p>outros envolvidos. Esse estudo se baseia em dois princípios: 1)</p><p>as escolhas das pessoas são motivadas por preferências bem</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 7</p><p>Capítulo 7 Teoria dos Jogos 91</p><p>definidas e estáveis sobre os possíveis resultados das suas de-</p><p>cisões, e 2) as pessoas agem estrategicamente, ou seja, levam</p><p>em consideração a relação entre as suas escolhas e as deci-</p><p>sões dos outros.</p><p>Em 1928, John Von Neumann começou a utilizar a mate-</p><p>mática para mostrar que as pessoas ajudam as outras porque</p><p>ganham algo com isso. Ele iniciou um estudo sobre o com-</p><p>portamento racional, com o objetivo de criar modelos para</p><p>explicar o comportamento humano.</p><p>Anos após, John Nash realizou um estudo para provar que</p><p>o melhor resultado provém quando todos do grupo fazem o</p><p>que é melhor para si e para o grupo. Nesse estudo, John Nash</p><p>ajustava o conceito da “mão invisível”, criada pelo filósofo</p><p>Adam Smith, considerado o pai da economia moderna. Esse</p><p>conceito de Smith dizia que “...ao empregar seu capital o indi-</p><p>víduo tem em vista apenas sua própria segurança; ao orientar</p><p>sua atividade de tal maneira que sua produção possa ser de</p><p>maior valor, visa apenas o seu próprio ganho e, neste, como</p><p>em muitos casos, é levado como que por uma mão invisível a</p><p>promover um objetivo que não fazia parte de suas intenções.</p><p>Aliás, nem sempre é pior para a sociedade que esse objeti-</p><p>vo não faça parte das intenções do indivíduo. Ao perseguir</p><p>seus próprios objetivos, o indivíduo muitas vezes promove o</p><p>interesse da sociedade muito mais eficazmente do que quanto</p><p>tenciona realmente promovê-lo.”</p><p>Essa teoria de John Nash foi chamada de “Equilíbrio de</p><p>Nash” e afirma que a ambição individual não é a estratégia</p><p>que dá o melhor resultado.</p><p>92 Sistemas Inteligentes</p><p>7.1 Principais conceitos</p><p>Um jogo é uma situação onde ocorrem interações entre jogado-</p><p>res que se comportam de forma estratégica visando atingir um</p><p>objetivo que depende do comportamento dos outros jogadores.</p><p>O elemento básico em um jogo é o conjunto de jogadores.</p><p>Cada jogador tem um conjunto de estratégias, suas preferências ou</p><p>interesses para cada situação do jogo e pode fazer uma escolha.</p><p>Para caracterizar um jogo, então, é necessário descrever</p><p>os jogadores, as regras, os resultados e as utilidades (payoffs)</p><p>possíveis.</p><p>A teoria dos jogos considera que não basta estudar o com-</p><p>portamento isolado dos jogadores, pois o resultado do com-</p><p>portamento de um jogador pode ser obtido pelo comporta-</p><p>mento de outro. Dessa forma, é necessário considerar todas</p><p>as possibilidades de comportamentos (decisões, opções, es-</p><p>colhas) para chegar a uma escolha ideal para os jogadores.</p><p>Podemos classificar os jogos em dois diferentes tipos: soma</p><p>zero (também conhecido como ganha/perde) e soma não zero</p><p>(também conhecido como jogo ganha/ganha).</p><p>Os jogos de soma zero são jogos em que a soma total dos</p><p>benefícios de todos os jogadores é sempre igual a zero (ou</p><p>seja, um jogador só pode ganhar se outro perder). Pode-se</p><p>citar como o exemplo o Xadrez e o Pôquer.</p><p>Os jogos de soma não zero são jogos em que cada jo-</p><p>gador preocupa-se apenas com o seu resultado. O resultado</p><p>final é avaliação da pontuação de ambos os jogadores.</p><p>Capítulo 7 Teoria dos Jogos 93</p><p>Os jogos podem ser também estratégicos ou extensivos. Nos</p><p>jogos estratégicos, os jogadores agem ao mesmo tempo e uma</p><p>única vez. Já nos jogos extensivos, apenas um jogador joga a</p><p>cada vez e ele conhece o histórico de jogadas anteriores.</p><p>7.2 Modelos de jogos</p><p>Esta seção apresenta alguns modelos de jogos.</p><p>7.2.1 Dilema do Prisioneiro</p><p>Dois suspeitos (A e B) são presos pela polícia. A polícia tem</p><p>provas insuficientes para condená-los, então resolve separá-</p><p>-los e oferecer a ambos o mesmo acordo: se um dos prisionei-</p><p>ros testemunhar para a procuradoria contra o outro e o outro</p><p>permanecer em silêncio, o prisioneiro que confessou (coope-</p><p>rou) sai livre, e o que ficou em silêncio ganha pena de 10</p><p>anos.</p><p>Â Se ambos ficarem em silêncio, a polícia só pode conde-</p><p>ná-los a 6 meses de cadeia cada um.</p><p>Â Se ambos traírem o outro (ou seja, cooperarem com a</p><p>polícia), cada um leva 2 anos de cadeia.</p><p>A Tabela 7.1 apresenta a matriz de payoff do exemplo</p><p>apresentado para o dilema do prisioneiro. Cada prisioneiro</p><p>faz sua decisão sem saber o que o outro vai escolher, e eles</p><p>não tem certeza da decisão do outro. A questão que o dilema</p><p>propõe é: como cada prisioneiro vai reagir?</p><p>94 Sistemas Inteligentes</p><p>Tabela 7.1: Matriz de payoff</p><p>B</p><p>Confessa Não confessa</p><p>Confessa 2 anos/2 anos 0/10 anos</p><p>Não confessa 10 anos/0 6 meses/6 meses</p><p>7.2.2 Dilema do Prisioneiro Iterado</p><p>Â O pesquisador Axelrod criou um torneio de “Dilema do</p><p>Prisioneiro Iterado” em computador, nos moldes dos tor-</p><p>neios de xadrez, onde várias equipes se inscreveram e</p><p>tinham como objetivo apresentar diferentes estratégias a</p><p>serem utilizadas em situações em que os interesses dos</p><p>jogadores não eram absolutamente opostos. Durante o</p><p>torneio, diversas estratégias foram apresentadas, como,</p><p>por exemplo: Poliana: o jogador coopera independente-</p><p>mente da estratégia do jogador adversário.</p><p>Â Antissocial: escolhe pela traição (confessar) sempre, in-</p><p>dependentemente da estratégia do jogador adversário.</p><p>Â Retaliadora: toma a iniciativa de cooperar, mas em se-</p><p>quência responde com a mesma ação empregada por</p><p>seu oponente na jogada anterior. Se ele cooperou, ele</p><p>coopera e, se ele traiu, ele opta pela traição. Essa estra-</p><p>tégia é mais conhecida como “tit-for-tat” – olho por olho.</p><p>A estratégia tit-for-tat foi a vencedora do torneio, pois foi</p><p>a estratégia que teve a maior soma de pontos no final das</p><p>rodadas. Analisando as estratégias, percebeu-se que algumas</p><p>propriedades são importantes para o sucesso de uma estraté-</p><p>gia, como, por exemplo:</p><p>Capítulo 7 Teoria dos Jogos 95</p><p>Â Bondade: uma vez que o jogador sempre começa coo-</p><p>perando, ele evita entrar em problemas desnecessaria-</p><p>mente.</p><p>Â Reciprocidade: o fato de agir da forma como o outro</p><p>agiu na jogada anterior desencoraja a oposição, já que</p><p>esta será retaliada.</p><p>Â Perdão: retribuir cooperação, mesmo tendo havido uma</p><p>oposição anterior, ajuda a restaurar a cooperação mútua.</p><p>Â Clareza: faz a estratégia compreensível para o outro jo-</p><p>gador, evitando retaliações por atitudes mal compreen-</p><p>didas.</p><p>7.2.3 Problema do Bar</p><p>O problema do bar foi descrito por Brian Arthur (Arthur, 1994),</p><p>que toda quinta-feira à noite frequentava o bar El Farol na</p><p>localidade de Santa Fé, Novo México. Como o bar era pe-</p><p>queno, em alguns dias o bar ficava cheio demais e em outros</p><p>dias muito vazio. Brian percebeu que as pessoas decidiam se</p><p>iam ou não ao bar sem nenhuma informação ou comunicação</p><p>com outras pessoas e então decidiu definir o problema como</p><p>um modelo matemático, que prevê:</p><p>Se 60% das pessoas resolve ir ao bar, o local fica agradável</p><p>e elas têm uma noite muito divertida.</p><p>Se mais de 60% das pessoas decide ir ao bar, ele fica lo-</p><p>tado, e consequentemente as pessoas não têm uma noite di-</p><p>vertida.</p><p>96 Sistemas Inteligentes</p><p>Cada pessoa faz sua escolha (de ir ou não ao bar) com</p><p>base, por exemplo:</p><p>Â Na mesma escolha da última semana.</p><p>Â A média das últimas quatro semanas.</p><p>Â O mesmo número de pessoas que foram há duas se-</p><p>manas.</p><p>Â O mesmo número de pessoas que foi nas cinco sema-</p><p>nas anteriores.</p><p>Brian Arthur percebeu que não há decisão de raciocínio</p><p>dedutivo que permita a uma pessoa chegar à melhor decisão</p><p>de ir ou não ao bar.</p><p>7.2.4 Tragédia dos Comuns</p><p>A tragédia dos comuns foi formulada pela primeira vez pelo</p><p>filósofo político David Hume, onde ele abordou a questão do</p><p>uso individual e sem restrições dos recursos coletivos que, na</p><p>maioria das vezes, leva a escassez desses recursos.</p><p>Podemos dizer que a tragédia dos comuns é uma boa apli-</p><p>cação da teoria dos jogos, porque ela reflete o comportamento</p><p>instintivo das pessoas e mostra que o comportamento humano</p><p>pode ser expresso pelas equações dessa teoria, que apontam</p><p>para um alto benefício individual contra um baixo custo para</p><p>cada um da comunidade.</p><p>Um dos exemplos mais clássicos da tragédia dos comuns é</p><p>a ida de 10 amigos a um restaurante, que no final dividem o</p><p>pagamento da conta. Imaginando que 9 pedem hambúrguer</p><p>Capítulo 7 Teoria dos Jogos 97</p><p>e 1 pede um prato de camarão, ao dividir a conta, os 9 que</p><p>comeram hambúrguer pagarão uma pequena diferença na</p><p>conta. Porém, se todos resolverem fazer o mesmo pedido</p><p>de</p><p>camarão, a conta ficará muito cara.</p><p>A estratégia possível para o bem de todo grupo é impor</p><p>penalidades caso alguém se comporte diferente dos demais,</p><p>fazendo com que as pessoas tenham um comportamento mais</p><p>altruísta.</p><p>Outro exemplo é a utilização de impressora do laborató-</p><p>rio. Imagine que a impressão seja liberada, e um único aluno</p><p>decide imprimir uma apostila de 500 páginas. Isso implicará</p><p>na falta de papel e de tonner para que os próximos alunos</p><p>imprimam seus trabalhos. Para solucionar esse problema, a</p><p>universidade deve criar regras para impressão, impondo um</p><p>limite de folhas impressas por aluno.</p><p>7.3 Teoria dos jogos aplicada na</p><p>negociação entre os agentes</p><p>Nos sistemas multiagente, um modelo de teoria dos jogos é</p><p>aquele que estuda o comportamento estratégico dos agentes,</p><p>os quais tomam decisões com base nos objetivos bem defini-</p><p>dos e no seu conhecimento ou nas suas expectativas sobre o</p><p>comportamento dos outros agentes.</p><p>Conforme vimos no Capítulo 6, em um sistema multiagen-</p><p>te, é necessário que os agentes coordenem suas ações, pois</p><p>eles não possuem uma visão global do problema. Cada agen-</p><p>98 Sistemas Inteligentes</p><p>te conhece apenas seus objetivos, ou seja, possui apenas co-</p><p>nhecimento local, o que dificulta a cooperação entre eles. No</p><p>momento em que o agente precisa realizar a tarefa, ele avalia</p><p>a utilidade (custo e tempo) de realização dessa tarefa e decide</p><p>se ele mesmo realizará ou se inicia o processo de negociação</p><p>com outros agentes. A negociação pode ser classificada em</p><p>dois tipos: colaborativa e competitiva.</p><p>Como vimos anteriormente, a negociação competitiva</p><p>ocorre entre agentes onde cada um tenta maximizar sua uti-</p><p>lidade local, ou seja, os resultados de uma das partes são</p><p>prejudicados em relação à outra. Nesse tipo de negociação,</p><p>as partes assumem algum conflito de interesses. O grau de</p><p>incompatibilidade nos objetivos e os métodos para lidar com</p><p>os conflitos determinam as estratégias a serem adotadas pelos</p><p>agentes em diferentes circunstâncias. Os agentes visam seu</p><p>próprio ganho, não considerando o grande grupo. Esse tipo</p><p>de negociação se identifica como um jogo de soma zero, ou</p><p>seja, o ganho de um jogador é a perda do outro. Um exemplo</p><p>é a negociação do preço de um produto entre um compra-</p><p>dor e um vendedor, onde as duas partes possuem objetivos</p><p>antagônicos: o comprador quer o menor preço e o vendedor</p><p>persegue o maior.</p><p>Dependendo do tipo de negociação, os agentes se com-</p><p>portam de forma diferente. Em um ambiente competitivo, o</p><p>agente precisa ser ágil e ficar atento ao tempo que ele possui</p><p>para negociar. Já em um ambiente colaborativo, a negociação</p><p>acontece com outros agentes da sua própria comunidade.</p><p>Capítulo 7 Teoria dos Jogos 99</p><p>Recapitulando</p><p>Este capítulo apresentou os principais conceitos envolvidos na</p><p>área de Teoria dos Jogos. Alguns modelos bem conhecidos</p><p>foram apresentados.</p><p>Referências Bibliográficas</p><p>Arthur, W. Brian, “Inductive Reasoning and Bounded Rationali-</p><p>ty”, American Economic Review (Papers and Proceedings),</p><p>84,406-411, 1994.</p><p>Atividades</p><p>1) Quanto à Teoria dos Jogos, pode-se afirmar que:</p><p>a) É possível analisar um jogo de soma não zero com ape-</p><p>nas um jogador.</p><p>b) Preocupa-se em analisar o comportamento isolado dos</p><p>jogadores.</p><p>c) Considera que jogos de soma zero são melhores do que</p><p>jogos de soma não zero.</p><p>d) Preocupa-se em analisar qualquer situação que envolva</p><p>um conflito de interesses.</p><p>e) Nenhuma das alternativas anteriores.</p><p>2) Quanto aos jogos do tipo estratégico, pode-se dizer que:</p><p>a) Vários jogadores jogam em uma rodada e todos conhe-</p><p>cem os outros jogadores.</p><p>100 Sistemas Inteligentes</p><p>b) Apenas um jogador joga a cada vez e ele não conhece</p><p>o histórico de jogadas anteriores.</p><p>c) Apenas um jogador joga a cada vez e ele conhece o</p><p>histórico de jogadas anteriores.</p><p>d) Os jogadores agem ao mesmo tempo e uma única vez.</p><p>e) Nenhuma das alternativas anteriores.</p><p>3) Quanto aos jogos do tipo extensivo, pode-se dizer que:</p><p>a) Vários jogadores jogam em uma rodada e todos conhe-</p><p>cem os outros jogadores.</p><p>b) Apenas um jogador joga a cada vez e ele não conhece</p><p>o histórico de jogadas anteriores.</p><p>c) Apenas um jogador joga a cada vez e ele conhece o</p><p>histórico de jogadas anteriores.</p><p>d) Os jogadores agem ao mesmo tempo e uma única vez.</p><p>e) Nenhuma das alternativas anteriores.</p><p>4) Sobre o dilema do prisioneiro, é correto afirmar que:</p><p>I – Não existem estratégias que levem ao equilíbrio de</p><p>Nash.</p><p>II – É possível chegar ao equilíbrio de Nash se os jogadores</p><p>colaborarem entre si.</p><p>III – É possível chegar ao equilíbrio de Nash se os jogado-</p><p>res traírem um ao outro.</p><p>a) Somente a afirmativa I está correta.</p><p>Capítulo 7 Teoria dos Jogos 101</p><p>b) Somente a afirmativa II está correta.</p><p>c) Somente a afirmativa III está correta.</p><p>d) Somente as afirmativas I e II estão corretas.</p><p>e) Todas as afirmativas estão corretas.</p><p>5) Sobre o problema do bar, é correto afirmar que:</p><p>I – É um problema do tipo estratégico.</p><p>II – É um problema do tipo soma não zero.</p><p>III – É um problema que envolve comunicação entre os</p><p>jogadores.</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente a afirmativa II está correta.</p><p>c) Somente a afirmativa III está correta.</p><p>d) Somente as afirmativas I e II estão corretas.</p><p>e) Todas as afirmativas estão corretas.</p><p>Gabarito</p><p>1) d</p><p>2) d</p><p>3) c</p><p>4) b</p><p>5) d</p><p>Algoritmos Genéticos1</p><p>Apresentação</p><p>Este capítulo tem como objetivo apresentar os principais con-</p><p>ceitos da IA evolucionária, que tem como seu principal ele-</p><p>mento os algoritmos genéticos.</p><p>Conforme vimos no Capítulo 1 deste livro, a IA tem uma</p><p>subárea chamada de IA evolucionária, com conceitos oriun-</p><p>dos da evolução biológica. Essa subárea também é conhecida</p><p>como Computação Evolutiva e visa ao desenvolvimento de sis-</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 8</p><p>Capítulo 8 Algoritmos Genéticos 103</p><p>temas que resolvem problemas por meio de modelos compu-</p><p>tacionais que se baseiam na teoria da evolução natural.</p><p>Os algoritmos genéticos, por exemplo, fazem parte dessa</p><p>área da Inteligência Artificial. Esses algoritmos são utilizados</p><p>para resolução de problemas do mundo real, onde cada indi-</p><p>víduo da população corresponde a uma possível solução para</p><p>o problema. Um mecanismo de produção baseado no proces-</p><p>so evolutivo é aplicado sobre a população atual para explo-</p><p>rar o espaço de busca, tentando encontrar melhores soluções</p><p>para o problema.</p><p>Algoritmos Genéticos (AG), idealizados por Jonh Holland</p><p>em 1975, constituem uma técnica de busca, inspirada no pro-</p><p>cesso de evolução dos seres vivos, baseada na seleção na-</p><p>tural de Darwin. Considerando os sistemas biológicos como</p><p>um todo, observa-se que os mesmos desenvolveram, ao longo</p><p>da sua evolução, estratégias de adaptação de comportamen-</p><p>to, que possibilitaram a sua sobrevivência e a perpetuação de</p><p>suas espécies.</p><p>Com base nessa analogia com o processo de evolução</p><p>biológica das espécies, chamada de metáfora biológica, os</p><p>AGs são métodos adaptativos que podem ser usados para re-</p><p>solver problemas de busca e otimização. Dado um determi-</p><p>nado problema, o conjunto de todas as possíveis soluções é</p><p>chamado de espaço de busca e o AG tenta encontrar a melhor</p><p>solução nesse espaço de busca.</p><p>Muitos problemas computacionais envolvem busca por</p><p>meio de um grande número de possíveis soluções e requerem</p><p>que o programa seja adaptativo, apto a agir em um ambiente</p><p>104 Sistemas Inteligentes</p><p>dinâmico. Os AGs são apropriados na solução desses proble-</p><p>mas.</p><p>Os AGs são utilizados em um diverso número de aplica-</p><p>ções, como, por exemplo:</p><p>Gerenciamento de redes: supervisão do tráfego nos links e</p><p>das filas nos buffers de roteadores para descobrir rotas ótimas</p><p>e para reconfigurar as rotas existentes no caso de falha de</p><p>algum link.</p><p>Computação Evolutiva: gera programas que se adaptam a</p><p>mudanças no sistema ao longo do tempo.</p><p>Problemas de otimização complexos: problemas com mui-</p><p>tas variáveis e espaços</p><p>de soluções de dimensões elevadas.</p><p>Ex.: problema do caixeiro viajante.</p><p>8.1 Principais conceitos de AG</p><p>Biologicamente, um indivíduo é formado por um conjunto de</p><p>cromossomos. O cromossomo é composto de genes, sendo</p><p>que cada gene possui um local fixo no cromossomo (deno-</p><p>minado de “locus”). Os genes possuem instruções que deter-</p><p>minam muito do repertório de comportamento do organismo.</p><p>Um único conjunto completo de genes é chamado de Genó-</p><p>tipo.</p><p>As características do genótipo formam o fenótipo (cor dos</p><p>olhos, altura etc.). A maneira pela qual um indivíduo muda e</p><p>reage a outros indivíduos faz parte do fenótipo. Cada indiví-</p><p>Capítulo 8 Algoritmos Genéticos 105</p><p>duo começa a partir do genótipo, considerado um conjunto de</p><p>instruções que é utilizado para crescer o fenótipo do indivíduo.</p><p>No AG, o gene é denominado de “bit” e o “locus”, de po-</p><p>sição do “bit” no indivíduo. O genótipo é representado por um</p><p>vetor de bits, onde cada elemento denota a presença (1) ou</p><p>ausência (0) de uma determinada característica. Os elementos</p><p>podem ser combinados formando as características reais do</p><p>indivíduo (o seu fenótipo). Teoricamente, essa representação</p><p>é independente do problema, pois uma vez encontrada a re-</p><p>presentação em vetores binários, as operações padrão podem</p><p>ser utilizadas, facilitando o seu uso em diferentes classes de</p><p>problemas.</p><p>Normalmente, os AGs trabalham com um conjunto de indi-</p><p>víduos (população), no qual, cada elemento é candidato a ser</p><p>a solução desejada. A cadeia de cromossomos pode ser codi-</p><p>ficada de diversas formas. A representação mais comum utiliza</p><p>números binários (0 e 1) é de comprimento fixo (e pode variar</p><p>de acordo com a aplicação). A codificação pode ser também</p><p>através de valores, onde cada cromossomo é uma sequência</p><p>de alguns valores. Estes podem ser qualquer coisa relaciona-</p><p>da com o problema, tais como: números reais, caracteres ou</p><p>qualquer outro objeto.</p><p>A população inicial normalmente é criada randomicamen-</p><p>te. A partir dessa população, existe um algoritmo que é segui-</p><p>do com o objetivo de que a solução “evolua”.</p><p>Na busca pela melhor solução, o AG executa o seguinte</p><p>algoritmo:</p><p>106 Sistemas Inteligentes</p><p>1) Avalia o grau de adaptação (fitness) de cada genótipo</p><p>da população.</p><p>2) Cria uma nova população consistindo de cópias de par-</p><p>te dos genótipos da antiga população.</p><p>3) Realiza operação de crossover.</p><p>4) Realiza mutação em alguns dos genótipos da nova po-</p><p>pulação.</p><p>5) Volta ao passo 1.</p><p>8.1.1 Avaliação dos indivíduos</p><p>Avaliação dos indivíduos (chamado de fitness) é considerada</p><p>um ajuste na população, onde os indivíduos mais aptos da</p><p>geração atual são selecionados. Todos os indivíduos da popu-</p><p>lação são avaliados e, quanto mais adaptado for um genótipo</p><p>(indivíduo), maior é o número de descendentes que ele pode</p><p>ter na nova população.</p><p>A função a ser otimizada é o ambiente, no qual a popula-</p><p>ção inicial será inserida. A partir dos mecanismos de evolução</p><p>das espécies e da genética natural, espera-se que somente os</p><p>mais aptos se reproduzam e, também, que cada nova geração</p><p>esteja mais apta ao ambiente.</p><p>O grau de aptidão de cada indivíduo é obtido pela avalia-</p><p>ção de tal indivíduo, a partir da função a ser otimizada. Se o</p><p>objetivo for maximizar, a aptidão é diretamente proporcional ao</p><p>valor da função. Caso o objetivo seja a minimização da função,</p><p>a aptidão será inversamente proporcional ao valor da função.</p><p>Capítulo 8 Algoritmos Genéticos 107</p><p>Cada indivíduo tem uma probabilidade proporcional a sua</p><p>aptidão de ser selecionado. Um método de seleção muito uti-</p><p>lizado é o método da Roleta, onde indivíduos de uma geração</p><p>são escolhidos para fazer parte da próxima geração, a partir</p><p>de um sorteio de roleta. Os indivíduos cujas regiões possuem</p><p>maior área terão maior probabilidade de serem selecionados</p><p>várias vezes. E, como consequência, a seleção de indivíduos</p><p>pode conter várias cópias de um mesmo indivíduo, enquanto</p><p>outros podem desaparecer.</p><p>8.1.2 Criação de uma nova população</p><p>Com a avaliação de cada indivíduo, o próximo passo é execu-</p><p>tado: a criação da próxima geração. Essa nova geração será</p><p>uma evolução da anterior e, para que isso ocorra, os indivídu-</p><p>os mais aptos terão maior probabilidade de serem seleciona-</p><p>dos para dar origem à nova geração.</p><p>8.1.3 Operadores Genéticos</p><p>Após a avaliação, operadores genéticos são utilizados para a</p><p>criação da nossa geração, tais como, crossover e mutação.</p><p>Esses operadores são utilizados para assegurar que a nova</p><p>geração seja totalmente nova, porém com características de</p><p>seus pais, ou seja, a população se diversifica e mantém carac-</p><p>terísticas de adaptação adquiridas pelas gerações anteriores.</p><p>Para prevenir que os melhores indivíduos não desapareçam da</p><p>população pela manipulação dos operadores genéticos, eles</p><p>podem ser automaticamente colocados na próxima geração,</p><p>por meio da reprodução elitista.</p><p>108 Sistemas Inteligentes</p><p>Crossover</p><p>O crossover acontece pela aproximação dos cromossomos</p><p>dos dois indivíduos (pais), que trocam entre si partes de seus</p><p>cromossomos. Isso resulta em dois cromossomos diferentes</p><p>que, porém, ainda guardam influências dos pais.</p><p>Existem várias formas possíveis de se realizar o crossover.</p><p>A forma mais simples é o chamado “crossover” de um ponto</p><p>(One-Point), onde, primeiro um local de cruzamento é escolhido</p><p>com probabilidade uniforme sobre o comprimento do cromos-</p><p>somo, sendo, então, os “strings” correspondentes permutados.</p><p>A segunda forma é o crossover de dois pontos (Two-Point). A</p><p>Figura 8.1 apresenta um exemplo de cruzamento de um ponto.</p><p>Figura 8.1: Exemplo de cruzamento um ponto.</p><p>Capítulo 8 Algoritmos Genéticos 109</p><p>Mutação</p><p>A mutação consiste em alterações na cadeia dos cromos-</p><p>somos, dando origem a uma nova cadeia, que armazenará</p><p>pouca ou nenhuma informação da cadeia mãe. Na realidade,</p><p>mutação é a denominação dada a vários mecanismos de al-</p><p>teração genética, os quais têm em comum o fato de fazerem</p><p>o novo cromossomo apresentar pouca informação dos pais.</p><p>Essa alteração ocorre de forma que cada gene em cada</p><p>cromossomo é um candidato à mutação, enquanto que a sele-</p><p>ção é determinada pela probabilidade de mutação. Essa pro-</p><p>babilidade é mantida, normalmente em um valor baixo, para</p><p>evitar a perda de um número grande de cromossomos bons.</p><p>Dentre os principais mecanismos de alteração genética,</p><p>que recebem a denominação global de mutação, destacam-</p><p>-se: troca simples, translocação, inversão, exclusão e adição.</p><p>Na exclusão, ocorre a retirada de um gene do cromos-</p><p>somo e na adição, ocorre a inserção de mais um gene na</p><p>cadeia. Geralmente, esses mecanismos não são utilizados em</p><p>algoritmos genéticos, pois alteram o comprimento da cadeia</p><p>do cromossomo.</p><p>A troca simples consiste em um erro de cópia, de um ou</p><p>mais genes da cadeia. Por exemplo, dado um genótipo, foi</p><p>codificado com bits; se um gene vale 1 (um), ele é trocado por</p><p>0 (zero) e vice-versa.</p><p>110 Sistemas Inteligentes</p><p>Figura 8.2: Exemplo de mutação.</p><p>Se a codificação é por valores (por exemplo, números re-</p><p>ais), um pequeno valor é adicionado ou subtraído dos genes</p><p>selecionados.</p><p>A inversão consiste na retirada e inserção de um pedaço</p><p>da cadeia, porém, na ordem inversa da que foi retirada. Ao</p><p>contrário da inversão, onde um pedaço do código é retirado e</p><p>colocado no mesmo local com ordem inversa, a translocação</p><p>retira uma parte do cromossomo e coloca em outra posição</p><p>do mesmo cromossomo. Esses três últimos mecanismos não</p><p>alteram o comprimento original do cromossomo.</p><p>8.2 Parâmetros necessários em um AG</p><p>Na utilização dos AGs, é necessário que alguns parâmetros</p><p>sejam definidos. São eles:</p><p>Â Tamanho da População: o tamanho da população</p><p>afeta o desempenho global e a eficiência dos AGs. Com</p><p>uma população pequena, o desempenho pode cair,</p><p>pois, desse modo, a população fornece uma pequena</p><p>Capítulo 8 Algoritmos Genéticos 111</p><p>cobertura do espaço de busca do problema. Por outro</p><p>lado, uma grande população geralmente fornece uma</p><p>cobertura representativa do domínio do</p><p>problema. Em</p><p>contrapartida, para trabalhar com grandes populações,</p><p>são necessários maiores recursos computacionais.</p><p>Â Taxa de Cruzamento: quanto maior for a taxa de cru-</p><p>zamento, mais rapidamente novos indivíduos serão in-</p><p>troduzidos na população. Porém, se essa taxa for muito</p><p>alta, estruturas com boas aptidões poderão desaparecer</p><p>da população mais rapidamente. Com um valor baixo,</p><p>o algoritmo pode tornar-se muito lento.</p><p>Â Taxa de Mutação: uma baixa taxa de mutação previne</p><p>que uma dada posição fique estagnada em um valor,</p><p>além de possibilitar que se chegue em qualquer ponto</p><p>do espaço de busca. Com uma taxa muito alta, a busca</p><p>se torna essencialmente aleatória.</p><p>Â Intervalo de Geração: esse parâmetro controla a por-</p><p>centagem da população que será substituída durante a</p><p>próxima geração. Com um valor alto, a maior parte da</p><p>população será substituída, o que leva à perda de estru-</p><p>turas de alta aptidão. Com um valor baixo, o algoritmo</p><p>pode se tornar muito lento.</p><p>8.3 Exemplo de implementação de um AG</p><p>Esta seção apresenta o AG que descobre uma palavra secreta</p><p>digitada pelo usuário implementado em (Serrão et al., 2006).</p><p>112 Sistemas Inteligentes</p><p>O usuário digita uma palavra, e o AG busca em sua popula-</p><p>ção a frase mais parecida.</p><p>O primeiro passo da implementação foi definir o que seria</p><p>um cromossomo nesse domínio e qual seria o espaço de bus-</p><p>ca. Um indivíduo corresponde a uma palavra, representada</p><p>por um vetor onde cada posição armazena o código ASCII</p><p>correspondente à letra.</p><p>Considerando a tarefa de descobrir a palavra secreta, o</p><p>espaço de busca do AG é 27n, onde 27 representa o número</p><p>de letras (maiúsculas) do alfabeto + o espaço em branco; e n</p><p>é o tamanho do indivíduo (que é dinâmico sendo definido no</p><p>momento em que o usuário digitar a sua palavra secreta).</p><p>O segundo passo foi definir, ainda na modelagem do siste-</p><p>ma, alguns parâmetros principais do AG, tais como, a função</p><p>de aptidão e o crossover.</p><p>Função de Aptidão (fitness): Essa função serve para ava-</p><p>liar a aptidão de cada indivíduo em relação à palavra digitada</p><p>pelo usuário. Nesse exemplo, a função de aptidão é um cálcu-</p><p>lo realizado entre a palavra digitada e o indivíduo.</p><p>Taxa de Crossover: esse parâmetro corresponde à forma</p><p>que será realizado o cruzamento entre os pais. Nesse exem-</p><p>plo, o crossover é de um ponto e foi definido na modelagem</p><p>do sistema, não permitindo ao usuário modificar a forma do</p><p>crossover durante a execução do programa.</p><p>Capítulo 8 Algoritmos Genéticos 113</p><p>Outros parâmetros importantes, como a mutação, o inter-</p><p>valo da geração e o critério de parada, também precisam ser</p><p>definidos. Nesse sistema, esses parâmetros podem ser defini-</p><p>dos pelo próprio usuário, como mostra a Figura 8.3. Dessa</p><p>forma, o usuário pode alterar os parâmetros a cada execução</p><p>e fazer comparações entre os resultados obtidos.</p><p>Figura 8.3: Tela principal do AG.</p><p>Conforme pode-se ver na Figura 8.3, o usuário pode defi-</p><p>nir os seguintes parâmetros:</p><p>Â Tamanho da População: nesse parâmetro, o usuário</p><p>define o tamanho da população, que representará seu</p><p>espaço de busca.</p><p>Â Intervalo da geração: nesse parâmetro, o usuário defi-</p><p>ne quantos novos indivíduos de sua população deverão</p><p>ser gerados a cada novo ciclo. É importante lembrar que</p><p>esse número não pode ser ímpar, pois ele também cor-</p><p>responde ao número de pais que serão utilizados para a</p><p>geração dos novos indivíduos.</p><p>114 Sistemas Inteligentes</p><p>Â Taxa de mutação: nesse parâmetro, é necessário de-</p><p>finir quantas posições do cromossomo serão trocadas</p><p>nos novos indivíduos gerados. Nesse exemplo, definiu-</p><p>-se que somente uma posição (escolhida de forma alea-</p><p>tória) será trocada em cada novo indivíduo.</p><p>Â Máximo de repetições: esse parâmetro correspon-</p><p>de ao critério de parada, ou seja, se o AG não chegar</p><p>a uma solução aceitável, o algoritmo encerra quando</p><p>chegar no número máximo de ciclos definido.</p><p>A Figura 8.4 apresenta a tela resultante após a execução do</p><p>AG, onde a palavra digitada pelo usuário é “Paralelepípedo”.</p><p>Como é uma palavra grande, foi necessário definir uma popu-</p><p>lação grande também (5000 indivíduos). Para essa população,</p><p>definiu-se um intervalo de geração de 400, ou seja, a cada</p><p>nova geração, 400 indivíduos serão substituídos. O número</p><p>máximo de repetições foi definido como 600, porém, percebe-</p><p>-se que o AG encontrou a solução na repetição número 425.</p><p>Figura 8.4: Teste do AG com a palavra “Paralelepípedo”.</p><p>Capítulo 8 Algoritmos Genéticos 115</p><p>Com esse exemplo apresentado, pode-se chegar a algu-</p><p>mas conclusões, tais como:</p><p>Â Se o tamanho da população for pequena, o desem-</p><p>penho do algoritmo pode cair, pois ela representa um</p><p>pequeno espaço de busca do problema; em contrapar-</p><p>tida, uma grande população consegue representar bem</p><p>o domínio do problema.</p><p>Â Como o intervalo de geração controla o percentual da</p><p>população que será substituída a cada nova geração,</p><p>se ele for definido com um valor alto, a maior parte da</p><p>população será substituída, levando à perda de estrutu-</p><p>ras de alta aptidão. Em contrapartida, se esse valor for</p><p>muito baixo, o AG perde desempenho.</p><p>Â Em relação à taxa de mutação, se essa for baixa, pre-</p><p>vine-se que uma determinada posição fique estagnada</p><p>em um valor, além de possibilitar que se chegue em</p><p>qualquer ponto do espaço de busca. Com uma taxa</p><p>muito alta, a busca se torna essencialmente aleatória.</p><p>Atividades</p><p>1) Sobre o Intervalo de Geração, pode-se afirmar que:</p><p>I – O método pôquer é o mais utilizado para definir o inter-</p><p>valo de geração.</p><p>II – Controla o percentual da população que será substitu-</p><p>ído durante a próxima geração.</p><p>III – Um valor baixo torna o algoritmo muito lento.</p><p>116 Sistemas Inteligentes</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente a afirmativa II está correta.</p><p>c) Somente a afirmativa III está correta.</p><p>d) Somente as afirmativas II e III estão corretas.</p><p>e) Nenhuma das alternativas anteriores.</p><p>2) Sobre Algoritmos Genéticos, pode-se afirmar que:</p><p>I – Um único conjunto completo de genes é chamado de</p><p>Fenótipo.</p><p>II – O indivíduo que evolui é uma possível solução para um</p><p>dado problema.</p><p>III – Dado um determinado problema, o conjunto de todas</p><p>as possíveis soluções é chamado de espaço de busca.</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente as afirmativas I e II estão corretas.</p><p>c) Somente as afirmativas II e III estão corretas.</p><p>d) Todas as afirmativas estão corretas.</p><p>e) Nenhuma das alternativas anteriores.</p><p>3) No método de seleção dos pais do tipo Roleta, os pais são</p><p>selecionados da seguinte forma:</p><p>a) Aleatória.</p><p>b) Os melhores têm menor probabilidade de serem esco-</p><p>lhidos.</p><p>Capítulo 8 Algoritmos Genéticos 117</p><p>c) Os melhores têm maior probabilidade de serem esco-</p><p>lhidos.</p><p>d) Os melhores são escolhidos.</p><p>e) Nenhuma das alternativas anteriores.</p><p>4) Sobre o tamanho da população, pode-se afirmar que:</p><p>I – Um valor baixo torna o algoritmo muito lento.</p><p>II – Quanto maior, mais possíveis soluções podem ser en-</p><p>contradas.</p><p>III – Quanto menor, menos possíveis soluções podem ser</p><p>encontradas.</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente a afirmativa II está correta.</p><p>c) Somente a afirmativa III está correta.</p><p>d) Somente as afirmativas II e III estão corretas.</p><p>e) Nenhuma das alternativas anteriores.</p><p>5) São considerados tipos de mutação que modificam a estru-</p><p>tura do indivíduo em um AG:</p><p>a) Inversão e Divisão.</p><p>b) Troca simples e Adição.</p><p>c) Exclusão e Multiplicação.</p><p>d) Adição e Exclusão.</p><p>e) Nenhuma das alternativas anteriores.</p><p>118 Sistemas Inteligentes</p><p>Recapitulando</p><p>Este capítulo apresentou os principais conceitos da IA Evolu-</p><p>cionária, especialmente os Algoritmos Genéticos. Estes são</p><p>utilizados, na maioria das vezes, para auxiliar no processo de</p><p>busca e otimização, especialmente em problemas que apre-</p><p>sentam muitas possíveis soluções.</p><p>Referências bibliográficas</p><p>SERRÃO, R., VIEGEL, A., ALVES, J, CANDIAGO, P. Aplicação</p><p>de algoritmos genéticos para descoberta da palavra secre-</p><p>ta. Relatório de pesquisa, 2006.</p><p>Gabarito</p><p>1) d</p><p>2) c</p><p>3) c</p><p>4) d</p><p>5) d</p><p>Redes Neurais Artificiais1</p><p>As redes neurais artificiais (RNAs), também chamadas de sis-</p><p>temas conexionistas, foram inspiradas em sistemas biológicos</p><p>em que um grande número de células nervosas funcionam in-</p><p>dividualmente de forma lenta e perfeita, porém coletivamente</p><p>são capazes de realizar tarefas que muitos computadores não</p><p>têm capacidade de fazer.</p><p>As RNAs são formadas por diversos processadores simples,</p><p>interconectados com vários elementos de memória, cujos pe-</p><p>sos das conexões são ajustados por experiência. Esse ajuste de</p><p>pesos caracteriza a capacidade de aprendizado de uma RNA.</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 9</p><p>120 Sistemas Inteligentes</p><p>A grande motivação que levou ao estudo das RNAs foi a</p><p>inspiração biológica. Percebeu-se a dificuldade dos sistemas</p><p>convencionais em resolver certas classes de problemas, como,</p><p>por exemplo, o reconhecimento de formas, reconhecimento de</p><p>objetos e classificações de padrões.</p><p>Entre as características mais importantes das RNAs, desta-</p><p>cam-se:</p><p>Treinamento: normalmente as redes são treinadas para re-</p><p>alizar uma determinada tarefa (e não programadas).</p><p>Â Interligação: os neurônios são amplamente interligados</p><p>de forma que o estado de um neurônio afeta o poten-</p><p>cial, de um grande número de neurônios.</p><p>Â Conexões: os pesos das conexões são adaptativos,</p><p>ajustam-se conforme a rede aprende.</p><p>Â Funções: as unidades de processamento contêm funções</p><p>de ativação do tipo não linear.</p><p>A Figura 9.1 apresenta as principais semelhanças entre um</p><p>neurônio biológico e um neurônio artificial. A Figura 9.1 (a)</p><p>mostra um neurônio biológico, com seus dendritos (que cor-</p><p>respondem às entradas) e seus axônios (que correspondem às</p><p>saídas do neurônio artificial). A Figura 9.1 (b) está apresentan-</p><p>do um neurônio artificial, onde X são as entradas, W são os</p><p>pesos e Y representa a saída.</p><p>Capítulo 9 Redes Neurais Artificiais 121</p><p>Figura 9.1: (a) Neurônio biológico e (b) Neurônio artificial.</p><p>Analisando os dois neurônios apresentados na figura 9.1,</p><p>percebe-se que a maior diferença concentra-se nas sinapses,</p><p>pois, nos neurônios biológicos, não existe uma ligação física</p><p>(as trocas de informações são realizadas por meio de neu-</p><p>rotransmissores), enquanto que nos neurônios artificiais existe</p><p>uma ligação física, e o armazenamento das informações de-</p><p>pende dos pesos sinápticos. Assim como nos sistemas biológi-</p><p>cos não é possível determinar exatamente em quais neurônios</p><p>as informações estão armazenadas, elas encontram-se distri-</p><p>buídas ao longo da rede neural artificial.</p><p>Esse neurônio artificial simples, composto de três entradas,</p><p>denominadas x0, x1 e x2, em que x0 pode ser considerada</p><p>uma polarização de valor 1. Aos pesos sinápticos w0, w1 e</p><p>w2, inicialmente são atribuídos valores aleatórios entre -0.1</p><p>e 0.1. Esses valores normalmente são ajustados ao longo do</p><p>treinamento. O somatório Σ calculado a partir da soma das</p><p>entradas multiplicadas pelos pesos de cada uma irá ativar a</p><p>saída.</p><p>122 Sistemas Inteligentes</p><p>A saída denominada Y1 irá depender da função de ativação</p><p>f, que no exemplo é uma função bipolar. Essas funções são de-</p><p>terminadas no início de um projeto de redes neurais, e, na maio-</p><p>ria dos casos, são utilizadas funções sigmoidais. Em uma defini-</p><p>ção formal, descrita por (De Azevedo, 1997), o autor apresenta</p><p>o modelo geral de neurônio com base na Teoria de Sistemas e as</p><p>principais funções de transferência utilizadas em RNAs.</p><p>O neurônio artificial é composto por 3 entradas denomina-</p><p>das X 0, X1 e X2.</p><p>Aos pesos sinápticos (W0, W1 e W2) inicialmente são atri-</p><p>buídos valores aleatórios entre -0,1 e 0,1 (esses valores são</p><p>ajustados ao longo do treinamento).</p><p>O somatório (∑) – calculado pela soma das entradas multi-</p><p>plicadas por seus respectivos pesos, serve para ativar a saída.</p><p>A saída (Y1) depende da função de ativação f, que no exem-</p><p>plo é uma função bipolar. Essas funções são determinadas no</p><p>início do projeto de uma RNA e, na maioria das vezes, são</p><p>utilizadas funções sigmodais.</p><p>O primeiro modelo de neurônio artificial foi apresentado</p><p>por McCulloch e Pitts (1943), e em 1959 foram apresentados</p><p>simultaneamente os Perceptrons por Rosemblatt e os Adalines</p><p>por Widrow e Hoff, tanto os Perceptrons quanto os Adalines</p><p>possuíam regras de aprendizado. Existe prova da convergência</p><p>do algoritmo de aprendizado associado aos perceptrons. No</p><p>Adaline é possível calcular pesos pelo método dos mínimos</p><p>quadrados, apesar de ter sido apresentado com aprendizado</p><p>iterativo.</p><p>Capítulo 9 Redes Neurais Artificiais 123</p><p>9.1 Topologias das RNAs</p><p>As RNAs podem ser subdivididas em redes diretas e redes re-</p><p>correntes. As redes diretas são aquelas nas quais o fluxo de</p><p>informações segue um uma única direção, enquanto que as</p><p>redes recorrentes (ou de realimentação) podem se realimentar</p><p>de uma saída, demonstrando troca de estados.</p><p>Figura 9.2: Classificação para RNAs.</p><p>A Figura 9.2 apresenta um diagrama que classifica as re-</p><p>des neurais conforme a sua topologia: realimentação (recor-</p><p>rentes) ou diretas. No caso de redes com realimentação (ou</p><p>feedback), podem ainda ser subdivididas em construídas (por</p><p>exemplo, redes do tipo BAM – Bidirectional Associative Me-</p><p>mories) ou treinadas (Redes do tipo Hopfield ou do tipo ART –</p><p>Associative Resonance Theory – por exemplo). As redes diretas</p><p>podem ser subdivididas em redes lineares e não lineares.</p><p>124 Sistemas Inteligentes</p><p>As redes não lineares podem ser subdivididas conforme o</p><p>algoritmo de aprendizado: supervisionado e não supervisiona-</p><p>do. A próxima subseção explica os algoritmos de treinamento</p><p>com mais detalhes.</p><p>9.2 Algoritmos de Treinamento</p><p>Os algoritmos de treinamento ou regra de aprendizado ditam</p><p>como são feitos os ajustes dos pesos sinápticos para que a</p><p>rede adquira experiência ao longo do treinamento.</p><p>9.2.1 Supervisionado</p><p>As regras ou algoritmos de aprendizado do tipo supervisionado</p><p>atuam com o auxilio de um professor. A rede precisa conhecer</p><p>o conjunto de entrada e o conjunto de saída. A saída obtida</p><p>pela rede é calculada conforme a saída desejada, calcula-se</p><p>um erro que é utilizado para corrigir os pesos sinápticos.</p><p>Uma das regras do tipo supervisionada mais utilizada é</p><p>a regra de Hebb. Donald Hebb teorizou que a memória as-</p><p>sociativa biológica concentra-se nas conexões sinápticas das</p><p>células nervosas, e que o processo de aprendizado e armaze-</p><p>namento de memória associativa biológica centra-se nas co-</p><p>nexões sinápticas das células nervosas, e que o processo de</p><p>aprendizado e armazenamento de memória envolve trocas nas</p><p>forças com as quais os sinais nervosos são transmitidos a partir</p><p>das sinapses individuais.</p><p>Capítulo 9 Redes Neurais Artificiais 125</p><p>9.2.2 Não Supervisionado</p><p>Regras de aprendizado do tipo não supervisionado atuam de</p><p>forma competitiva ou autossupervisionada. Para esse tipo de</p><p>regras, somente o conjunto de entrada é fornecido às redes.</p><p>Os neurônios da rede competem entre si fornecendo uma</p><p>classificação como saída. Existe, além da competição, uma</p><p>coordenação entre os neurônios da rede. Entre os algoritmos</p><p>mal conhecidos, destaca-se o vencedor leva tudo (the winner</p><p>takes it all) e a inibição lateral.</p><p>9.2.3 Por Reforço</p><p>O aprendizado por reforço (reinforcement learning) é um mé-</p><p>todo por tentativa e erro. Existe um índice de desempenho cha-</p><p>mado de sinal de reforço que é utilizado para otimização.</p><p>9.3 Modelos de Redes Neurais</p><p>9.3.1 Perceptron/Adaline</p><p>Os valores de entrada e níveis de ativação são -1 ou +1. Os</p><p>pesos têm valores reais, e o nível de ativação dele é dado pela</p><p>soma dos valores ponderados das entradas (∑WiXi).</p><p>Esses modelos usam uma função linear simples, onde uma</p><p>ativação acima de um linear resulta em um valor de saída 1,</p><p>caso contrário esse valor será -1. Eles são capazes de resolver</p><p>problemas linearmente separáveis, tais como os operadores</p><p>lógicos Ou e E. A Figura 9.3 apresenta o exemplo do operador</p><p>126 Sistemas Inteligentes</p><p>lógico Ou. Ele é considerado um problema “linearmente sepa-</p><p>rável”, pois é possível traçar uma reta entre os dois resultados</p><p>(0 e 1).</p><p>Figura 9.3: Exemplo do operador lógico Ou.</p><p>Dado valores de entrada Xi, pesos Wi e um linear t, a rede</p><p>calcula o seu valor de saída como:</p><p>1 se</p><p>-1 se</p><p>Seja C uma constante cujo tamanho determina a taxa de</p><p>aprendizagem e D o valor de saída desejado, o ajuste para</p><p>o peso no i-ésimo componente do vetor de entrada é dado</p><p>como:</p><p>Capítulo 9 Redes Neurais Artificiais 127</p><p>9.3.2 Backpropagation</p><p>O Backpropagation é um modelo multicamadas, derivado do</p><p>Perceptron, que possui aprendizado supervisionado e alimen-</p><p>tação à frente. Conforme apresentado na Figura 9.4, seus</p><p>neurônios são compostos por três ou mais camadas de percep-</p><p>trons/adalines interconectados, tendo a camada intermediária</p><p>(hidden). Essa camada não existe nos perceptrons/adalines.</p><p>Figura 9.4: Exemplo de Backpropagation.</p><p>Esse modelo foi criado para ser possível a representação</p><p>de funções complexas, como exemplo, o XOR (ou exclusivo),</p><p>considerado um problema não linearmente separado. A Figu-</p><p>ra 9.5 apresenta o exemplo do XOR e como os resultados (0</p><p>e 1) não podem ser separados a partir de uma reta (como é</p><p>possível fazer no operador Ou).</p><p>128 Sistemas Inteligentes</p><p>Normalmente, as redes backpropagation utilizam a função</p><p>sigmoid como função de limiar. Nesse modelo, calcula-se a</p><p>contribuição de cada peso no erro da saída da rede, que é</p><p>transferido para as camadas intermediárias (Erro Médio Qua-</p><p>drado).</p><p>Figura 9.5: Exemplo do XOR.</p><p>9.3.3 Mapas Auto-organizáveis</p><p>Os mapas auto-organizáveis, do inglês Self-Organized Maps</p><p>(SOM), são conhecidos também como mapas de Kohonen,</p><p>pois foram desenvolvidos por Teuvo Kohonen.</p><p>Esse modelo apresenta topologia bidimensional, camada</p><p>competitiva e aprendizado não supervisionado. Existe uma</p><p>camada única de neurônios, dividida em linhas e colunas,</p><p>conforme pode ser visto na Figura 9.6. Não existe um reco-</p><p>nhecimento de padrão, mas sim uma classificação de padrão,</p><p>formando classes (também chamadas de clusters).</p><p>Capítulo 9 Redes Neurais Artificiais 129</p><p>Figura 9.6: Topologia Mapas Auto-organizáveis.</p><p>No momento em que um padrão é inserido na rede, esta o</p><p>coloca na classe onde ele melhor se enquadra, conforme suas</p><p>características.</p><p>Esse modelo varia conforme os padrões de entrada defini-</p><p>das, pois ele simplesmente faz a distribuição desses padrões</p><p>na rede. Quando um padrão é inserido na rede, calcula-se</p><p>a distância de cada neurônio de saída e depois se verifica o</p><p>neurônio que alcançou o maior valor, chamado de neurônio</p><p>vencedor (the winner takes it all).</p><p>Os pesos da rede são ajustados após um determinado nú-</p><p>mero de iterações, podendo então classificar corretamente os</p><p>padrões a serem reconhecidos. Quando um padrão é inserido,</p><p>as unidades de saída competem entre si para serem ativadas.</p><p>O resultado é apenas uma unidade de saída ativada, indican-</p><p>do que ele tem a menor distância em relação à entrada.</p><p>130 Sistemas Inteligentes</p><p>Os mapas auto-organizáveis possuem aprendizado não</p><p>supervisionado, baseado na aprendizagem competitiva, pois</p><p>o objetivo é descobrir padrões ou características nos dados</p><p>de entrada sem um professor ou crítico, agrupando dados em</p><p>classes.</p><p>O algoritmo de treinamento dos mapas auto-organizáveis</p><p>segue os seguintes passos:</p><p>1) Inicializa a rede com valores baixos escolhidos aleatoria-</p><p>mente.</p><p>2) Insere o padrão de entrada.</p><p>3) Calcula a distância de saída.</p><p>4) Seleciona a menor distância.</p><p>Atualiza os pesos do neurônio vencedor e de seus vizinhos,</p><p>definido pelo raio de vizinhança.</p><p>Wi(t+1)=Wi(t)+n(t)*(X(t)-Wi(t)) se i ∈ vizinhança</p><p>Wi(t) se fora da vizinhança</p><p>Onde: n(t) é o coeficiente de aprendizado no tempo t, que</p><p>pode variar da seguinte forma: n(t) =09*(1.t/1000).</p><p>Repetir a partir do passo 2.</p><p>Recapitulando</p><p>Este capítulo apresentou os principais conceitos de Redes Neu-</p><p>rais, utilizadas na solução de problemas onde não temos co-</p><p>Capítulo 9 Redes Neurais Artificiais 131</p><p>nhecimento para resolver o problema, e a rede então é treina-</p><p>da para reconhecer.</p><p>Atividades</p><p>1) Considere as afirmativas a seguir:</p><p>I – A função booleana OU exclusivo (XOR) pode ser im-</p><p>plementada usando uma rede perceptron de camada</p><p>única.</p><p>II – Os Mapas de Kohonen, também chamados de Mapas</p><p>Auto-organizáveis, possuem aprendizado supervisiona-</p><p>do.</p><p>III – Retropropagação (backpropagation) é um algoritmo de</p><p>aprendizagem supervisionada.</p><p>Assinale a alternativa correta.</p><p>a) Somente as afirmativas I e II são corretas.</p><p>b) Somente as afirmativas II e III são corretas.</p><p>c) Somente a afirmativa II está correta.</p><p>d) Somente a afirmativa III está correta.</p><p>e) Nenhuma das alternativas anteriores.</p><p>2) Quais são os tipos de aprendizados que podem ser aplica-</p><p>dos no algoritmo de treinamento de uma rede neural arti-</p><p>ficial?</p><p>a) Não Supervisionado e Por regras.</p><p>132 Sistemas Inteligentes</p><p>b) Supervisionado e Por regras.</p><p>c) Supervisionado, Não Supervisionado e Por Reforço.</p><p>d) Por pesos.</p><p>e) Nenhuma das alternativas anteriores.</p><p>3) Que modelo neural é utilizado para classificação que aplica</p><p>o método the winner takes it all?</p><p>a) Adaline.</p><p>b) Mapas de Kohonen.</p><p>c) Backpropagation.</p><p>d) Redes de Hopfield.</p><p>e) Nenhuma das alternativas anteriores.</p><p>4) Os algoritmos de backpropagation são:</p><p>a) Redes neurais artificiais com realimentação.</p><p>b) Redes neurais artificiais baseadas em casos.</p><p>c) Redes neurais artificiais que possuem camadas ocultas.</p><p>d) Redes neurais de alimentação direta com uma única ca-</p><p>mada.</p><p>e) Nenhuma das alternativas anteriores.</p><p>5) Os modelos Perceptrons são:</p><p>a) Redes neurais artificiais com realimentação.</p><p>Capítulo 9 Redes Neurais Artificiais 133</p><p>b) Redes neurais artificiais baseadas em casos.</p><p>c) Redes neurais artificiais que possuem camadas ocultas.</p><p>d) Redes neurais de alimentação direta com uma única ca-</p><p>mada.</p><p>e) Nenhuma das alternativas anteriores.</p><p>Gabarito</p><p>1) d</p><p>2) c</p><p>3) b</p><p>4) c</p><p>5) d</p><p>Exemplos de</p><p>Implementações de</p><p>Sistemas1</p><p>Apresentação</p><p>Neste capítulo, são apresentados alguns exemplos de siste-</p><p>mas implementados utilizando algumas das técnicas vistas ao</p><p>longo do livro. Alguns foram implementados como trabalho</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 10</p><p>Capítulo 10 Exemplos de Implementações de Sistemas 135</p><p>de conclusão de curso e outros como trabalhos práticos na</p><p>disciplina de Inteligência Artificial.</p><p>10.1 Sistemas baseados em regras</p><p>A Figura 10.1 apresenta o sistema baseado em regras desen-</p><p>volvido para análise de possíveis problemas que podem acon-</p><p>tecer em uma empresa. O objetivo é evitar que o problema</p><p>aconteça, apresentando no final uma lista de ações que de-</p><p>vem ser tomadas para tal.</p><p>136 Sistemas Inteligentes</p><p>Figura 10.1: Exemplo de sistema baseado em regras.</p><p>A Figura 10.2 apresenta o sistema baseado em regras</p><p>desenvolvido para realização do Inventário de Depressão de</p><p>Beck, teste realizado por profissionais da área da psicologia.</p><p>Nesse exemplo, o usuário responde a um conjunto de ques-</p><p>tões, e no final o sistema apresenta o nível de depressão, con-</p><p>siderando as respostas inseridas.</p><p>Capítulo 10 Exemplos de Implementações de Sistemas 137</p><p>Figura 10.2: Exemplo de sistema baseado em regras – depressão de Beck.</p><p>10.2 Sistemas baseados em casos</p><p>A Figura 10.3 (Carrer, 2010) apresenta o sistema de esti-</p><p>mativa de desenvolvimento de softwares baseado em casos. O</p><p>sistema possibilita minimizar o equívoco do tempo estimado</p><p>atualmente na alocação de desenvolvedores para realização</p><p>de tarefas e também auxilia para que o prazo de entrega das</p><p>atividades seja respeitado.</p><p>138 Sistemas Inteligentes</p><p>Figura 10.3: Exemplo de sistema baseado em caso.</p><p>A Tabela 10.1 apresenta os atributos que compõe um caso</p><p>no sistema. Podemos ver que alguns atributos representam a</p><p>descrição do problema e o atributo tempo representa a solu-</p><p>ção do problema.</p><p>Tabela 10.1: Atributos de representação do caso</p><p>Atributos do Problema Tipo de Dado Valores Peso</p><p>Número de Regras do Caso de Uso Inteiro [0…N] 3</p><p>Número de Entradas Inteiro [0…N] 2</p><p>Número de Saídas Inteiro [0…N] 2</p><p>Quantidade de Tabelas Envolvidas Inteiro [0…N] 4</p><p>Número de Códigos-Fonte alterados Inteiro [0…N] 4</p><p>Quantidade de Aplicações Inteiro [0…N] 3</p><p>Atributo de Solução Tipo de Dado Valores</p><p>Tempo Inteiro [0…N] -</p><p>Capítulo 10 Exemplos de Implementações de Sistemas 139</p><p>10.3 Sistemas de recomendação</p><p>A Figura 10.4 apresenta o sistema de recomendação para</p><p>grupos (Brum, 2010), desenvolvido com o objetivo de ser um</p><p>sistema configurável, sendo possível utilizá-lo para chegar à</p><p>solução de diferentes tipos de problemas de recomendação</p><p>considerando um grupo de pessoas.</p><p>Figura 10.4: Tela de recomendação para o usuário.</p><p>O algoritmo desenvolvido nesse sistema auxilia o grupo</p><p>na busca de um consenso com relação à escolha de um de-</p><p>terminado item, ou seja, de uma recomendação que satisfaça</p><p>a maioria dos usuários, considerando que as pessoas de um</p><p>grupo possuem preferências diferentes.</p><p>10.4 Agentes</p><p>Esta seção apresenta exemplos de implementação de agentes</p><p>reativos.</p><p>Conforme visto no Capítulo 6, os agentes reativos recebem</p><p>dados a partir de seus atuadores, processam esses dados e</p><p>140 Sistemas Inteligentes</p><p>reagem conforme sua programação. A Figura 10.5 apresenta</p><p>um jogo de futebol implementado.</p><p>Figura 10.5: Simfut – jogo de futebol composto por agentes reativos.</p><p>A Figura 10.6 apresenta um exemplo de um jogo formi-</p><p>gueiro. Nesse jogo, as formigas são agentes reativos que de-</p><p>vem andar pelo ambiente buscando por doces. Quando elas</p><p>encontram o doce, elas carregam de volta para o formigueiro.</p><p>No ambiente, existe alguns lugares com água, que podem ma-</p><p>tar as formigas.</p><p>Capítulo 10 Exemplos de Implementações de Sistemas 141</p><p>Figura 10.6: Implementação de um formigueiro com agentes reativos.</p><p>Referências bibliográficas</p><p>Brum, Carlos. “Sistema de Recomendação Configurável para</p><p>Grupos.” Trabalho de Conclusão de Curso. (Graduação</p><p>em Ciência da Computação) – Universidade Luterana do</p><p>Brasil, 2009.</p><p>142 Sistemas Inteligentes</p><p>Carrer, Helene. “SISTEMA DE ESTIMATIVA DE DESENVOL-</p><p>VIMENTO DE SOFTWARES BASEADO EM CASOS.” Tra-</p><p>balho de conclusão de curso, Universidade Luterana do</p><p>Braisl, 2010.</p><p>Fraga, Lianderson, Pineda Jr, José e Machado, Eduardo. “Sim-</p><p>fut: um agente reativo.” Relatório de trabalho prático rea-</p><p>lizado na disciplina de Inteligência Artificial, Universidade</p><p>Luterana do Braisl, 2008.</p><p>ser humano.</p><p>Sistemas Baseados em Conhecimento (SBC) aplicam me-</p><p>canismos automatizados de raciocínio para a representação e</p><p>inferência de conhecimento. Um Sistema Baseado em Conhe-</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 2</p><p>Capítulo 2 Conhecimento 9</p><p>cimento consegue reproduzir o conhecimento de um especia-</p><p>lista adquirido ao longo dos anos de trabalho. O conhecimen-</p><p>to especialista envolve uma combinação de um entendimento</p><p>teórico do problema com uma coleção de regras heurísticas</p><p>para resolvê-lo, que demonstrou ser efetiva no domínio em</p><p>questão.</p><p>Conhecimento inclui a informação sobre o domínio e a</p><p>forma como essa informação é utilizada para resolver proble-</p><p>mas. Por exemplo: “João tem mais de 18 anos. Maiores de 18</p><p>anos podem tirar carteira de habilitação. João pode fazer sua</p><p>carteira de habilitação”. Podemos decompor esse parágrafo</p><p>da seguinte forma:</p><p>Dado: Representação simbólica de um objeto ou informa-</p><p>ção do domínio (Qualquer conjunto relativamente circunscrito</p><p>de atividades) sem considerações de contexto, significado ou</p><p>aplicação. Ex.: 19 anos.</p><p>Informação: Reconhecimento dos objetos do domínio, suas</p><p>características, suas restrições e seus relacionamentos com os</p><p>outros objetos, sem ater-se a utilidade dessa informação. Ex.:</p><p>Idade de João = 19 anos.</p><p>Conhecimento: como a informação deve ser utilizada para</p><p>resolução de um problema. Ex.: Pessoas maiores de 18 anos</p><p>podem tirar habitação. Como João tem mais de 18 anos, en-</p><p>tão ele pode fazer sua carteira de habilitação.</p><p>O conhecimento não é um bem estático a ser minerado, só</p><p>existe quando se produz algo com ele ou a partir dele. Pode-se</p><p>10 Sistemas Inteligentes</p><p>dizer que o conhecimento não é genérico, mas associado ou</p><p>produzido pela solução de uma classe particular de problema.</p><p>No desenvolvimento de um sistema baseado em conheci-</p><p>mento, o conhecimento dos especialistas do domínio é adqui-</p><p>rido, organizado e representado na base de conhecimento.</p><p>Essa base pode ser consultada por meio do sistema quando</p><p>necessário.</p><p>Imagine, por exemplo, que a empresa XYZ tem dois técnicos</p><p>de suporte de hardware que atendem à matriz e mais três filiais.</p><p>Se ocorrer um problema em uma das filiais, um dos técnicos</p><p>deve ser deslocado para atender o problema. Ele vai até a em-</p><p>presa e resolve o problema. Porém, não existe nenhum controle</p><p>de como o problema foi resolvido ou se o problema já havia</p><p>ocorrido anteriormente. Se o problema ocorrer novamente e, o</p><p>outro técnico for deslocado para resolver o problema, ele terá</p><p>que investigar sobre como resolver o problema e iniciar todo</p><p>processo já realizado pelo técnico anterior. Isso indica que, se</p><p>existisse um sistema baseado em conhecimento para auxiliar no</p><p>processo de help-desk, o atendimento seria mais rápido, pois</p><p>todas as soluções estariam armazenadas no sistema.</p><p>A Figura 3.1 apresenta a relação entre dados e experiên-</p><p>cia. O dado, por exemplo, pode ser um fato, texto ou código</p><p>de programa. Quando o dado é organizado, ele passa a ser</p><p>informação. Quando a informação se torna útil para resolver</p><p>um determinado problema, ela passa a ser conhecimento. O</p><p>conhecimento pode ser perícia, do nível de peritos em um de-</p><p>terminado assunto ou ele pode ser experiência, quando temos</p><p>um especialista no assunto.</p><p>Capítulo 2 Conhecimento 11</p><p>Figura 2.1: Evolução do dado.</p><p>O desenvolvimento de um sistema baseado em conheci-</p><p>mento prevê a execução das seguintes etapas:</p><p>Aquisição de conhecimento: essa etapa refere-se à ob-</p><p>tenção de conhecimento de diversas fontes, tais como, livros,</p><p>documentos ou especialistas humanos. O conhecimento refe-</p><p>re-se à solução de problemas em um domínio de aplicação e</p><p>envolve os objetos do domínio, os procedimentos e a forma</p><p>geral de como o conhecimento é aplicado.</p><p>Representação de conhecimento: nessa etapa, é neces-</p><p>sário definir a forma de representação do conhecimento, mo-</p><p>delando o conhecimento.</p><p>Validação do conhecimento: verificação da consistência</p><p>da base de conhecimento.</p><p>12 Sistemas Inteligentes</p><p>Inferência: definição dos procedimentos de manipulação</p><p>e aplicação do conhecimento, com fins de implementação.</p><p>Explicação e justificativa: envolve a recuperação do ra-</p><p>ciocínio do sistema ao atingir determinada conclusão e a de-</p><p>finição da forma de apresentar esses caminhos de inferência</p><p>para o usuário.</p><p>2.1 Aquisição de conhecimento</p><p>Uma das etapas muito importantes do desenvolvimento de um</p><p>sistema especialista é a Aquisição de Conhecimento. Essa eta-</p><p>pa é considerada o componente crítico no desenvolvimento de</p><p>sistemas baseados em conhecimento.</p><p>A aquisição de conhecimento tem como objetivo obter o</p><p>conhecimento utilizado pelo especialista na solução de pro-</p><p>blemas, traduzindo a perícia do especialista para o formalismo</p><p>computacional. Por exemplo, o conhecimento de um técnico</p><p>da área de suporte utilizado na análise da impressora que não</p><p>está imprimindo pode ser adquirido e utilizado na construção</p><p>de um sistema que analise os possíveis problemas que podem</p><p>acontecer com impressoras (baseado nesse conhecimento ex-</p><p>traído do especialista).</p><p>O especialista é aquela pessoa que gastou mais de 20000</p><p>horas em treinamento na solução de um determinado proble-</p><p>ma e sabe identificar com rapidez os elementos fundamentais</p><p>da sua especialidade. O especialista possui a experiência e a</p><p>habilidade em resolver problemas em determinado domínio.</p><p>Capítulo 2 Conhecimento 13</p><p>Para adquirir o conhecimento do especialista, surge a fi-</p><p>gura do engenheiro de conhecimento. Este é responsável por</p><p>guiar a etapa de aquisição do conhecimento. A aquisição de</p><p>conhecimento é desenvolvida pelo engenheiro do conheci-</p><p>mento por meio das seguintes etapas:</p><p>1) Identificação e estudo do problema: como todo o conhe-</p><p>cimento necessário para o desenvolvimento do sistema</p><p>será adquirido do especialista, o primeiro passo é a es-</p><p>colha desse especialista. Em seguida, deve-se delimitar</p><p>o problema que se quer resolver e, que conhecimento</p><p>será necessário para a solução do problema. Normal-</p><p>mente, o especialista define qual o problema deve ser</p><p>resolvido pelo sistema, e o problema é restringido para</p><p>algo tratável computacionalmente, onde as entradas e</p><p>saídas do sistema são definidas.</p><p>2) Entrevistas com o especialista: são realizadas entrevistas</p><p>com o especialista de forma a detalhar que conhecimen-</p><p>to é aplicado na solução do problema e de que forma.</p><p>Existe um grande número de técnicas de aquisição de co-</p><p>nhecimento. É importante escolher uma técnica simples e de</p><p>rápida aplicação, que seja adaptável a vários domínios, base-</p><p>ada em situações bem perto da realidade e fornecendo dados</p><p>de fácil transformação para os formalismos computacionais de</p><p>representação de conhecimento.</p><p>Apesar da grande variedade de técnicas, não existe algu-</p><p>ma metodologia específica que seja considerada a mais efi-</p><p>ciente na obtenção do conhecimento e existem muitas dúvidas</p><p>em relação a como extrair o conhecimento de um especialista.</p><p>14 Sistemas Inteligentes</p><p>Entre as técnicas existentes, as mais utilizadas são: entrevistas</p><p>estruturadas e entrevistas não estruturadas.</p><p>Â Entrevistas não estruturadas ou abertas</p><p>As informações são obtidas a partir de conversa direta com</p><p>o especialista, onde ele apresenta livremente o problema e a</p><p>forma como este é resolvido. Pode-se aplicar dois métodos</p><p>distintos: protocolos verbais retrospectivos e protocolos verbais</p><p>concorrentes.</p><p>O método de protocolos verbais retrospectivos permite os</p><p>primeiros contatos com o especialista, onde o engenheiro do</p><p>conhecimento inicia a entrevista a partir de poucas questões</p><p>gerais sobre a aplicação, respondidas pelo especialista. É mui-</p><p>to importante interferir o mínimo possível, pois qualquer inter-</p><p>ferência tende a modificar a linha de raciocínio do especialista.</p><p>Já os protocolos verbais concorrentes nem sempre podem</p><p>ser aplicados, pois trata-se de observar o especialista na so-</p><p>lução de um problema. A maior</p><p>dificuldade desse método é</p><p>transformar as informações obtidas na observação para o mo-</p><p>delo computacional. Na maioria das vezes, o engenheiro do</p><p>conhecimento grava as entrevistas e faz com que o especialista</p><p>“pense em voz alta” e realize suas tarefas.</p><p>Esse método tende a ser muito mais fiel para demonstrar</p><p>as heurísticas do especialista do que o protocolo verbal re-</p><p>trospectivo. Quando o especialista explica suas ações, para</p><p>solucionar problemas, tende a descrevê-las nos termos em que</p><p>cientificamente são aceitas e não como realmente são aplica-</p><p>Capítulo 2 Conhecimento 15</p><p>das. Isso acontece, pois, ao descrever as ações, vê-se obriga-</p><p>do a descrever seus métodos efetivos.</p><p>Â Entrevistas estruturadas</p><p>Após as entrevistas não estruturadas, é necessário anali-</p><p>sar as informações construindo listas de conceitos ou objetos</p><p>descritos pelo especialista. Na análise inicial, tenta-se separar</p><p>esses objetos em classes, verificando relações de dependência</p><p>ou semelhança entre eles. A partir dessa análise, o especialista</p><p>determina quais são os pontos a serem explorados.</p><p>3) Análise do conhecimento e representação de conheci-</p><p>mento: a informação obtida é analisada de forma a evi-</p><p>denciar sua consistência, completeza e suficiência para</p><p>a solução do problema. O conhecimento é estruturado</p><p>segundo uma forma de representação de conhecimento.</p><p>A representação de conhecimento é uma combinação de</p><p>estruturas de dados e procedimentos de interpretação que le-</p><p>vam um sistema a apresentar um comportamento inteligente</p><p>(Rezende, 2005). O conhecimento pode ser considerado a</p><p>descrição dos objetos do mundo, suas relações com os outros</p><p>objetos e a forma como essas informações podem ser úteis</p><p>para resolver problemas.</p><p>Várias técnicas podem ser utilizadas para representar co-</p><p>nhecimento, como, por exemplo, lógica, redes semânticas,</p><p>quadros (frames) ou regras de produção. Algumas dessas téc-</p><p>nicas serão apresentadas na próxima subseção.</p><p>16 Sistemas Inteligentes</p><p>2.2 Técnicas de representação de</p><p>conhecimento</p><p>Esta seção apresenta algumas técnicas de representação de</p><p>conhecimento.</p><p>2.2.1 Redes Semânticas</p><p>Uma rede semântica é um grafo, onde os nodos representam</p><p>os objetos e os arcos representam as relações entre esses ob-</p><p>jetos.</p><p>A Figura 2.2 representa uma rede semântica que modela</p><p>o conhecimento do domínio de agências de viagens. É im-</p><p>portante lembrar que essa representação é parcial, pois está</p><p>sendo utilizada apenas como exemplo.</p><p>Figura 2.2: Exemplo de rede semântica.</p><p>Capítulo 2 Conhecimento 17</p><p>2.2.2 Quadros (frames)</p><p>Um quadro é uma estrutura de informação, ou seja, consiste</p><p>em um conjunto de atributos que, a partir de seus valores, des-</p><p>crevem as características do objeto representado pelo quadro.</p><p>Essa técnica foi derivada das redes semânticas.</p><p>A Figura 2.3 apresenta um exemplo da representação do</p><p>domínio de agência de viagens a partir de quadros.</p><p>Figura 2.3: Exemplo de quadros no domínio de agência de viagens.</p><p>18 Sistemas Inteligentes</p><p>2.2.3 Regras de Produção</p><p>O conhecimento pode ser representado também na forma de</p><p>regras de produção. As regras são formadas por premissas e</p><p>conclusões que são representadas na forma de se... então.</p><p>As regras podem ser disparadas de acordo com o conjun-</p><p>to de fatos conhecido (inicialmente fornecido pelo usuário e</p><p>posteriormente ampliado pelas deduções feitas pelo sistema).</p><p>Exemplo:</p><p>SE meio de transporte é avião</p><p>ENTÃO realizar reserva de passagens.</p><p>2.3 Tipos de Sistemas Baseados em</p><p>Conhecimento</p><p>Os sistemas baseados em conhecimento podem ser classifi-</p><p>cados em alguns tipos. Os dois principais tipos de sistemas</p><p>baseados em conhecimento são: sistemas baseados em regras</p><p>e sistemas baseados em casos.</p><p>Os sistemas baseados em conhecimento têm sido utilizados</p><p>para o desenvolvimento de um grande número de aplicações</p><p>nos mais diversos domínios, tais como:</p><p>Â Diagnósticos: sistemas de diagnósticos baseados em co-</p><p>nhecimento tentam recuperar casos antigos que tenham</p><p>sintomas parecidos com o novo problema e sugerem um</p><p>diagnóstico para esse problema baseado nessa recupe-</p><p>Capítulo 2 Conhecimento 19</p><p>ração de casos. A maioria dos sistemas de diagnósticos</p><p>refere-se a diagnósticos médicos.</p><p>Â Help desk: sistemas utilizados na área de serviços ao</p><p>consumidor, tratando de problemas com os produtos.</p><p>Â Suporte à decisão: na tomada de decisões, quando as</p><p>pessoas se deparam com um problema complexo, elas</p><p>geralmente procuram por problemas análogos a procu-</p><p>ra de soluções possíveis aos seus problemas.</p><p>Â Projetos: no domínio de projetos, sistemas baseados em</p><p>conhecimento têm sido desenvolvidos para projetos ar-</p><p>quitetônicos e industriais. Esses sistemas auxiliam o usu-</p><p>ário em apenas uma fase do projeto.</p><p>Nos próximos capítulos, veremos dois tipos de sistemas</p><p>baseados em conhecimento: sistemas baseados em regras e</p><p>sistemas baseados em casos.</p><p>Recapitulando</p><p>Este capítulo teve como objetivo permitir que você aluno en-</p><p>tenda um pouco mais sobre o que é conhecimento. Porque</p><p>algumas vezes falamos dados, outras informação e outras co-</p><p>nhecimento.</p><p>A partir desse conhecimento, é possível desenvolvermos sis-</p><p>temas baseados em conhecimento e nos próximos capítulos</p><p>veremos estes com mais detalhes.</p><p>20 Sistemas Inteligentes</p><p>Referências bibliográficas</p><p>REZENDE, Solange Oliveira. Sistemas Inteligentes: fundamen-</p><p>tos e aplicações. Baureri, SP: Manole, 2005.</p><p>Atividades</p><p>1) Sobre conhecimento, é possível afirmar que:</p><p>I – Dados representam os objetos de um domínio.</p><p>II – Informação representa os objetos e as relações entre</p><p>eles.</p><p>III – Conhecimento representa a utilidade da informação.</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente a afirmativa II está correta.</p><p>c) Somente a afirmativa III está correta.</p><p>d) Todas as afirmativas estão corretas.</p><p>e) Todas as afirmativas estão incorretas.</p><p>2) Conhecimento pode ser considerado como a descrição dos</p><p>_________ do mundo, suas relações com os outros objetos</p><p>e a forma como essas informações podem ser úteis para</p><p>resolver problemas.</p><p>a) Papéis.</p><p>b) Objetos.</p><p>c) Representantes.</p><p>Capítulo 2 Conhecimento 21</p><p>d) Casos.</p><p>e) Nenhuma das alternativas anteriores.</p><p>3) A etapa de aquisição de conhecimento é considerada o gar-</p><p>galo no desenvolvimento de sistemas baseados em conhe-</p><p>cimento. Marque a alternativa que apresenta duas técnicas</p><p>aplicadas nessa etapa:</p><p>a) Entrevistas e vídeos.</p><p>b) Entrevistas abertas e análise do conhecimento.</p><p>c) Análise do conhecimento e visita.</p><p>d) Entrevistas estruturadas e vídeo.</p><p>e) Nenhuma das alternativas anteriores.</p><p>4) Técnicas de representação de conhecimento são utilizadas</p><p>para representar o conhecimento em sistemas inteligentes.</p><p>Marque a alternativa que apresenta duas dessas técnicas:</p><p>a) Casos e Regras.</p><p>b) Frames e Casos.</p><p>c) Regras de produção e Quadros.</p><p>d) Redes semânticas e Casos.</p><p>e) Nenhuma das alternativas anteriores.</p><p>5) É considerado um tipo de sistema baseado em conhecimento:</p><p>a) Quadros.</p><p>b) Redes semânticas.</p><p>22 Sistemas Inteligentes</p><p>c) Sistemas baseados em casos.</p><p>d) Lógica proposicional.</p><p>e) Nenhuma das alternativas anteriores.</p><p>Gabarito</p><p>1) d</p><p>2) b</p><p>3) b</p><p>4) c</p><p>5) c</p><p>Sistemas Baseados em</p><p>Regras1</p><p>Apresentação</p><p>Este capítulo tem como objetivo apresentar os principais con-</p><p>ceitos envolvidos no desenvolvimento de um sistema baseado</p><p>em regras.</p><p>Como vimos no capítulo anterior, em alguns domínios, é</p><p>possível resolver problemas a partir da programação conven-</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 3</p><p>24 Sistemas Inteligentes</p><p>cional, porém, em outros domínios, só é possível revolver pro-</p><p>blemas a partir do conhecimento especialista. Por exemplo,</p><p>vamos imaginar uma agência de viagens em que um cliente</p><p>entra para comprar um pacote de viagens. A Figura 3.1 mos-</p><p>tra o diálogo entre o agente de viagem e o cliente.</p><p>Figura 3.1: Diálogo entre um agente de viagem e um cliente.</p><p>Podemos ver no diálogo apresentado pela Figura 3.1 que o</p><p>cliente não tem certeza de muita coisa, apenas que quer viajar.</p><p>Que tipo de pacote o agente de viagem poderia oferecer com</p><p>base nas respostas do cliente? Essa é uma tarefa bem difícil,</p><p>pois as respostas foram muito vagas. Nesse tipo de situação, o</p><p>agente de viagem utiliza o seu conhecimento (de vários paco-</p><p>tes já oferecidos para outros clientes) para selecionar algumas</p><p>opções e oferecer ao cliente. Podemos então, desenvolver um</p><p>sistema baseado em conhecimento para auxiliar o agente de</p><p>viagem na recomendação de pacotes turísticos aos clientes.</p><p>Esse sistema poderia ser baseado em regras.</p><p>Os Sistemas Baseados em Regras (SBR) são sistemas de</p><p>computação que executam funções semelhantes àquelas nor-</p><p>Capítulo 3 Sistemas Baseados em Regras 25</p><p>malmente executadas por um especialista humano. Esses sis-</p><p>temas utilizam a representação de conhecimento na forma de</p><p>regras de produção, de maneira a executar funções semelhan-</p><p>tes às de um especialista humano naquele domínio.</p><p>Um dos primeiros sistemas baseados em regras desenvol-</p><p>vidos foi o MYCIN, que tinha o objetivo de aconselhar sobre</p><p>o diagnóstico e terapia de doenças infecciosas. Esse tipo de</p><p>aconselhamento torna-se útil quando o médico responsável</p><p>não é um especialista em infecções, principalmente em am-</p><p>biente hospitalar. O usuário responde algumas perguntas a</p><p>respeito do paciente, como, por exemplo, nome, idade, sexo,</p><p>tempo de manifestação dos sintomas, resultados de exames</p><p>e, a partir dessas informações, o sistema utiliza sua base de</p><p>regras e estabelece um diagnóstico, propondo uma terapia</p><p>adequada.</p><p>Em um sistema baseado em regras, o conhecimento é re-</p><p>presentado na forma de regras de produção, onde:</p><p>Se <condição></p><p>Então <ação></p><p>Por exemplo:</p><p>Se o cliente gosta de praia</p><p>Então oferecer pacote nordeste brasileiro</p><p>Sistemas baseados em regras são aplicados em domínios</p><p>em que o conhecimento é bem definido e não existem exce-</p><p>ções às regras. O sistema só consegue aprender quando uma</p><p>nova regra for incluída na base de conhecimento.</p><p>26 Sistemas Inteligentes</p><p>A Figura 3.2 apresenta os dois principais componentes de</p><p>um sistema baseado em regras: a base de conhecimento e</p><p>o mecanismo de inferência. Na base de conhecimento ficam</p><p>armazenados todos fatos e regras relacionados ao domínio</p><p>(que representa o conhecimento do sistema), e a máquina de</p><p>inferência é responsável pela manipulação e aplicação do co-</p><p>nhecimento.</p><p>Figura 3.2: Funcionamento de um sistema especialista.</p><p>Nos sistemas baseados em regras, normalmente o usuá-</p><p>rio responde algumas perguntas ou escolhe algumas opções</p><p>apresentadas na tela principal. Essas escolhas e respostas são</p><p>consideradas os fatos que são incluídos no sistema. Esses fatos</p><p>são aplicados à base de conhecimento, e a reposta do sistema</p><p>é considerada a perícia do sistema.</p><p>O mecanismo de inferência é responsável pela forma que</p><p>os fatos serão aplicados às regras armazenadas na base de</p><p>conhecimento, ou seja, o método de raciocínio que será utili-</p><p>zado para resolução do problema.</p><p>Capítulo 3 Sistemas Baseados em Regras 27</p><p>Existem dois modos de raciocínio possíveis: encadeamen-</p><p>to progressivo e encadeamento regressivo. No encadeamento</p><p>progressivo (do inglês, forward chaining), as regras da base</p><p>de conhecimento são utilizadas para gerar informação nova,</p><p>ou seja, novos fatos, a partir de um conjunto inicial de dados.</p><p>Esses fatos gerados passam a fazer parte da base de conheci-</p><p>mento.</p><p>No encadeamento regressivo (do inglês, backward chai-</p><p>ning) e também conhecido como encadeamento para trás, as</p><p>regras da base de conhecimento são utilizadas para responder</p><p>as perguntas, provando se o fato é verdadeiro. Somente as</p><p>regras relevantes para a pergunta são disparadas.</p><p>No desenvolvimento de sistemas baseados em regras, é</p><p>preciso considerar alguns detalhes importantes, como, por</p><p>exemplo:</p><p>Â Desempenho: o sistema deve ter um alto desempenho,</p><p>ou seja, ele deve conseguir responder com o nível de</p><p>competência igual, ou melhor, ao do especialista.</p><p>Â Tempo de resposta: o sistema deve ter um tempo de res-</p><p>posta adequado.</p><p>Â Flexibilidade: o sistema pode ter uma vasta quantidade</p><p>de conhecimento e, por essa razão, é importante ter um</p><p>mecanismo eficiente para acrescentar, modificar ou ex-</p><p>cluir conhecimento quando necessário.</p><p>Confiabilidade: o sistema deve ser confiável e não propen-</p><p>so a falhas, caso contrário, não será utilizado.</p><p>28 Sistemas Inteligentes</p><p>Um dos gargalos do desenvolvimento de sistemas base-</p><p>ados em regras é a aquisição de conhecimento. Apesar das</p><p>regras serem uma forma natural de representação de conheci-</p><p>mento, em alguns domínios torna-se muito complicado adqui-</p><p>rir as regras do especialista.</p><p>Recapitulando</p><p>Este capítulo apresentou os sistemas baseados em regras e</p><p>seus principais conceitos. É importante lembrar que em domí-</p><p>nios em que a extração das regras é muito difícil e onde exis-</p><p>tem muitas exceções às regras, devemos optar pelo desenvol-</p><p>vimento de sistemas baseados em casos, ao invés de regras. O</p><p>próximo capítulo apresenta os principais conceitos de sistemas</p><p>baseados em casos.</p><p>Atividades</p><p>1) No desenvolvimento de um Sistema Baseado em Conheci-</p><p>mento, buscam-se as seguintes características:</p><p>I – O sistema deve conseguir responder com o nível de</p><p>competência igual (ou melhor) ao do especialista.</p><p>II – O sistema não precisa se preocupar em explicar seu</p><p>raciocínio durante a execução, pois esse raciocínio foi</p><p>adquirido do especialista na etapa de aquisição de co-</p><p>nhecimento.</p><p>III – O sistema deve ser confiável e não propenso à falhas,</p><p>caso contrário não será utilizado.</p><p>Capítulo 3 Sistemas Baseados em Regras 29</p><p>Marque a alternativa correta:</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente as afirmativas I e II estão corretas.</p><p>c) Somente as afirmativas I e III estão corretas.</p><p>d) Todas as alternativas estão corretas.</p><p>e) Nenhuma das alternativas anteriores.</p><p>2) Sobre os Sistemas Baseados em Regras, é correto afirmar</p><p>que esse tipo de sistema:</p><p>a) “Pode aprender automaticamente através da seleção e</p><p>aquisição de novos casos, tornando a manutenção da</p><p>base de conhecimento mais fácil”.</p><p>b) “Permite a reutilização da informação através da utiliza-</p><p>ção de bases de dados, que contenham implicitamente,</p><p>o conhecimento na solução de problemas do dia a dia</p><p>das instituições”.</p><p>c) “Tem na etapa de aquisição de conhecimento o gargalo</p><p>do desenvolvimento do sistema, pois a aquisição de ca-</p><p>sos reais é muito complicada e lenta”.</p><p>d) “É mais estável e confiável, pois aprende através dos</p><p>casos armazenados na base”.</p><p>e) Nenhuma das alternativas anteriores.</p><p>3) Um sistema baseados em regras:</p><p>30 Sistemas Inteligentes</p><p>a) Propõe a solução dos problemas através da utilização</p><p>de modelos.</p><p>b) Propõe a solução de novos problemas adaptando solu-</p><p>ções que foram utilizadas para resolver problemas ante-</p><p>riores.</p><p>c) Propõe a solução dos problemas através da utilização</p><p>de regras.</p><p>d) Propõe a solução de problemas através da adaptação</p><p>de modelos neurais.</p><p>e) Nenhuma das alternativas anteriores.</p><p>4) Um sistema baseado em regras busca as seguintes carac-</p><p>terísticas:</p><p>a) Desempenho, lentidão, flexibilidade e confiabilidade.</p><p>b) Desempenho, tempo de resposta, flexibilidade e confia-</p><p>bilidade.</p><p>c) Desempenho, tempo de resposta, flexibilidade e lenti-</p><p>dão.</p><p>d) Lentidão, tempo de resposta, flexibilidade e confiabili-</p><p>dade.</p><p>e) Nenhuma das alternativas anteriores.</p><p>5) São considerados dois modos de raciocínio para as regras:</p><p>a) Antigo e Novo.</p><p>b) Progressivo e Regressivo.</p><p>Capítulo 3 Sistemas Baseados em Regras 31</p><p>c) Progressivo e Novo.</p><p>d) Antigo e Regressivo.</p><p>e) Nenhuma das alternativas anteriores.</p><p>Gabarito</p><p>1) c</p><p>2) c</p><p>3) c</p><p>4) b</p><p>5) b</p><p>Sistemas Baseados em</p><p>Casos1</p><p>Apresentação</p><p>Este capítulo introduz o conceito de Raciocínio Baseado em</p><p>Casos e como ela é aplicada no desenvolvimento de sistemas</p><p>baseados em casos.</p><p>Raciocínio Baseado em Casos (RBC) é uma abordagem de</p><p>Inteligência Artificial, para representação de conhecimento e</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 4</p><p>Capítulo 4 Sistemas Baseados em Casos 33</p><p>inferência, que propõe a solução de novos problemas, adap-</p><p>tando soluções que foram utilizadas para resolver problemas</p><p>anteriores. O objetivo é utilizar soluções passadas para resol-</p><p>ver novos problemas; surgiu a partir dos estudos cognitivos de</p><p>memória de Roger Schank (Aadmot & Plaza, 1994). Segundo</p><p>Schank, a memória humana se modifica com o resultado de</p><p>experiências e, de acordo com novos acontecimentos, surgem</p><p>novas questões a serem respondidas. Portanto, a compreen-</p><p>são obriga a rever as experiências antigas ao se processar as</p><p>novas, e a memória não se comporta igual duas vezes, pois as</p><p>experiências mudam.</p><p>O primeiro sistema de RBC, chamado Cyrus, foi desen-</p><p>volvido por Janet Kolonder. Esse sistema continha casos de</p><p>viagens e encontros do ex-secretário do estado Cyrus Vance,</p><p>dos Estados Unidos. Cyrus serviu de base para outros sistemas</p><p>de RBC, entre eles:</p><p>Mediator (Simpson, 1985): trabalha na solução de dis-</p><p>putas entre diversas partes, propondo possíveis soluções de</p><p>consenso. Pode-se citar, como exemplo, a situação em que</p><p>dois alunos desejam retirar o mesmo livro na biblioteca ao</p><p>mesmo tempo. O sistema considera os alunos como as partes,</p><p>e o seu objetivo é solucionar a disputa pelo mesmo livro entre</p><p>as partes. No sistema Mediator, a representação de casos foi</p><p>implementada por meio de “frames”, permitindo representar</p><p>a descrição do problema, as características do problema ou</p><p>restrições (se existirem). Os objetivos do sistema não são re-</p><p>presentados explicitamente, pois o sistema só tem um objetivo,</p><p>resolver a disputa. É por meio da descrição do problema que</p><p>o sistema identifica seus objetivos. Se uma proposta sugerida</p><p>34 Sistemas Inteligentes</p><p>para satisfazer as partes envolvidas na disputa falhar, o siste-</p><p>ma registra a falha ocorrida e gera uma nova proposta para a</p><p>disputa, evitando que a falha aconteça novamente no futuro.</p><p>Chef (Hammond, 1989): desenvolve novos pratos a par-</p><p>tir de outros. Tendo como domínio a criação de receitas, o</p><p>sistema recebe como entrada diversos objetivos (ingredientes</p><p>disponíveis, tipo de refeição) a serem satisfeitos e recupera da</p><p>sua base de casos a receita que possa satisfazer tantos obje-</p><p>tivos quanto possível e, a partir dela, gera uma nova receita</p><p>para a situação proposta. Todas as receitas são indexadas por</p><p>suas características, permitindo que posteriormente elas pos-</p><p>sam ser recuperadas. Quando uma receita é recuperada, ela</p><p>deve ser adaptada para se ajustar às novas especificações.</p><p>Essa adaptação é realizada em dois passos: 1) o sistema cria</p><p>uma instância do caso recuperado e utiliza suas características</p><p>com novos valores adequados ao problema do usuário; e 2) o</p><p>sistema então aplica críticas para modificar a receita antiga de</p><p>maneira que ela possa ser reutilizada para a criação do novo</p><p>prato. Por exemplo, a partir de uma receita onde a carne é de</p><p>gado, gera uma nova com a característica carne modificada</p><p>para frango.</p><p>No sistema Chef , quando uma receita é criada, mas algo</p><p>de errado acontece com ela, como, por exemplo, a carne</p><p>queimou ou a salada ficou muito salgada, o sistema explica</p><p>porque o plano da receita falhou e repara o plano que falhou,</p><p>para evitar a mesma falha no futuro. O raciocínio do Chef é</p><p>muito parecido com o sistema Mediator: cria o plano, aplica-</p><p>-o, recebe o feedback sobre o plano, explica falhas e repara o</p><p>plano. Porém, a representação é diferente, pois o sistema Chef</p><p>Capítulo 4 Sistemas Baseados em Casos 35</p><p>não registra as falhas. Ao invés disso, o sistema utiliza as ex-</p><p>plicações das falhas para determinar como seus casos devem</p><p>ser indexados.</p><p>Quando comparado a outras técnicas de representação e</p><p>inferência, como, por exemplo, sistemas baseados em regras,</p><p>um sistema de RBC possui as seguintes vantagens:</p><p>Â Não requer um modelo explícito de domínio, pois utiliza</p><p>exemplos reais. Os sistemas de RBC utilizam a experi-</p><p>ência que especialistas acumulam durante suas vidas</p><p>profissionais na forma de problemas já resolvidos, não</p><p>sendo necessário extrair do especialista as regras que</p><p>definem o processo de solução de problemas. Dessa</p><p>forma, a aquisição de conhecimento na fase inicial do</p><p>projeto é agilizada, permitindo a criação de sistemas</p><p>operantes com recursos menores. Já em sistemas basea-</p><p>dos em regras, estas devem ser extraídas do especialista,</p><p>o que torna o processo de aquisição de conhecimento</p><p>mais lento. Além disso, um sistema RBC é mais estável e</p><p>confiável, pois aprende a partir dos casos armazenados</p><p>na base. Nos sistemas baseados em regras, o sistema</p><p>precisa saber como o problema foi resolvido, sendo ne-</p><p>cessário extrair novas regras do especialista, dificultando</p><p>a manutenção do sistema.</p><p>Â Permite a reutilização da informação, por meio da uti-</p><p>lização de bases de dados pré-existentes, que conte-</p><p>nham, implicitamente, o conhecimento na solução de</p><p>problemas do dia a dia das instituições. Dessa forma, a</p><p>implementação é reduzida a identificar as características</p><p>36 Sistemas Inteligentes</p><p>significantes dos problemas descritos no banco de da-</p><p>dos para compará-los a novos problemas e reaplicar a</p><p>solução lá descrita.</p><p>Â Pode aprender automaticamente por meio da seleção e</p><p>aquisição de novos casos, tornando a manutenção da</p><p>base de conhecimento mais fácil. Essa capacidade de</p><p>aprendizado é uma característica importante de um sis-</p><p>tema de RBC. A noção de RBC não somente indica um</p><p>método de raciocínio particular ou de como os casos</p><p>são adquiridos, mas também indica um paradigma de</p><p>aprendizado de máquina que possibilita aprendizado</p><p>assistido, adaptando a base de casos depois de um pro-</p><p>blema ter sido resolvido. O aprendizado em RBC ocor-</p><p>re naturalmente pelo produto da solução do problema.</p><p>Quando um problema é resolvido com sucesso, a expe-</p><p>riência é mantida para resolver problemas semelhantes</p><p>no futuro. Quando uma tentativa para resolver uma fa-</p><p>lha, o erro é identificado e relembrado para evitar que o</p><p>mesmo erro ocorra no futuro.</p><p>Os itens acima mostram algumas vantagens de um sistema</p><p>RBC, que oferece soluções para muitos dos problemas enfrenta-</p><p>dos no desenvolvimento de sistemas baseados em conhecimento.</p><p>4.1 Funcionamento de um sistema de RBC</p><p>Um sistema de RBC resolve problemas por meio de uma se-</p><p>quência de etapas. Cada uma dessas etapas está representa-</p><p>Capítulo 4 Sistemas Baseados em Casos 37</p><p>da no ciclo de funcionamento descrito por (Aamodt & Plaza,</p><p>1994), que demonstra as ações realizadas pelo sistema desde</p><p>que é confrontado com um novo problema, até que seja apre-</p><p>sentada, avaliada e aprendida uma solução para esse proble-</p><p>ma, conforme apresentado na Figura 4.1.</p><p>Figura 4.1: Ciclo de funcionamento de um sistema de RBC (Admodt &</p><p>Plaza, 1994).</p><p>As etapas do ciclo de funcionamento de um sistema de</p><p>RBC são: recuperação, reutilização, revisão e retenção. Elas</p><p>são conhecidas como as etapas 4 R’s.</p><p>Recuperação: recupera, na base de casos, o caso mais</p><p>parecido com o novo problema. Identifica e pesquisa índices,</p><p>calcula a similaridade entre o caso recuperado e o novo pro-</p><p>blema.</p><p>Reutilização: reutiliza a solução associada ao caso recu-</p><p>perado no contexto do novo problema, identificando as dife-</p><p>38 Sistemas Inteligentes</p><p>renças entre o caso recuperado e o novo problema e identifi-</p><p>cando a parte do caso recuperado que pode ser transferida ao</p><p>novo problema. Geralmente, a solução do caso recuperado é</p><p>transferida ao novo problema diretamente como sua solução.</p><p>Adaptação (Revisão): é necessário revisar (adaptar) a so-</p><p>lução do caso recuperado gerada pelo processo de reutiliza-</p><p>ção quando a solução não pode ser aplicada diretamente no</p><p>novo problema. Isso mostra uma oportunidade de aprender</p><p>com a falha.</p><p>Retenção: é o processo de incorporar tudo que for útil no</p><p>novo problema na biblioteca de casos. Isso envolve decidir</p><p>que informação armazenar e de que</p><p>forma armazenar, como</p><p>indexar o caso para futuras recuperações e integrar o novo</p><p>caso à biblioteca de casos.</p><p>A aquisição, representação e indexação dos casos não</p><p>aparecem explicitamente no ciclo, pois são executadas ainda</p><p>na construção do sistema, para a criação da base de casos.</p><p>As próximas seções apresentam cada uma das etapas en-</p><p>volvidas no ciclo de funcionamento de um sistema de RBC.</p><p>4.1.1 Representação de Casos</p><p>Um caso é um pedaço contextualizado de conhecimento repre-</p><p>sentando uma experiência que ensina uma lição fundamental</p><p>para atingir o objetivo do raciocinador (Kolodner, 1993). Um</p><p>caso representa um conhecimento específico, relacionado a</p><p>uma situação em um determinado contexto.</p><p>Capítulo 4 Sistemas Baseados em Casos 39</p><p>Casos são de diferentes formas e tamanhos, porém todos</p><p>têm em comum o fato de representarem uma experiência real</p><p>registrada em todas as suas características relevantes ou não.</p><p>A ideia de um caso se opõe a estereótipos de ações ou lem-</p><p>branças gerais de eventos, que registram os fatos como deve-</p><p>riam ter sido ou como comumente acontecem. Essa situação</p><p>real, quando relembrada, traz junto todo o conhecimento a</p><p>ela atrelado.</p><p>Um caso possui três componentes muito importantes, sen-</p><p>do que, para algum caso específico, talvez eles não estejam</p><p>preenchidos. São eles:</p><p>1. A descrição do problema que foi resolvido: a descrição</p><p>dos aspectos relevantes do problema que caracterizam</p><p>uma situação em particular a ser resolvida.</p><p>2. A descrição da solução: a solução utilizada para o pro-</p><p>blema específico na sua descrição.</p><p>3. Conclusão: a avaliação da solução utilizada para deter-</p><p>minado problema.</p><p>Com base nesses três componentes, podemos concluir que</p><p>os casos que incluem um problema e uma solução podem</p><p>ser usados para derivar soluções para novos problemas. Os</p><p>casos com uma descrição de situação e conclusão podem</p><p>ser usados na avaliação de soluções propostas, antecipando</p><p>problemas antes que eles ocorram. Para isso, o sistema RBC</p><p>compara as similaridades entre o novo problema e os casos da</p><p>base. Portanto, a representação do problema deve ter detalhes</p><p>40 Sistemas Inteligentes</p><p>suficientes para conseguir julgar a aplicabilidade do caso no</p><p>novo problema.</p><p>Vamos considerar um sistema de RBC que está sendo de-</p><p>senvolvido para sugerir se uma empresa pode ou não receber</p><p>um empréstimo bancário. Após a etapa de aquisição de co-</p><p>nhecimento, a base de casos foi criada e um caso possui os</p><p>seguintes atributos apresentados na Figura 4.2. Os atributos</p><p>nome, ramo, tempo de empresa, faturamento anual e núme-</p><p>ro de funcionários representam a descrição do problema, en-</p><p>quanto os atributos empréstimo e valor representam a descri-</p><p>ção da solução.</p><p>Figura 4.2: Exemplo de um caso.</p><p>A forma como o caso será representado em um sistema</p><p>de RBC é de extrema importância, ou seja, é imprescindível</p><p>decidir o que será armazenado em um caso, definindo a me-</p><p>lhor estrutura para descrever o conteúdo dele e decidir como</p><p>a base de casos deve ser organizada e indexada para uma</p><p>posterior recuperação e reutilização dos casos.</p><p>Capítulo 4 Sistemas Baseados em Casos 41</p><p>Diferentes formalismos podem ser utilizados em um sistema</p><p>de RBC para representar um caso. No Capítulo 2, vimos algu-</p><p>mas técnicas de representação, tais como, redes semânticas,</p><p>quadros e regras. Já no sistema Hypo, os casos são represen-</p><p>tados em uma rede semântica.</p><p>4.1.2 Indexação</p><p>Sistemas baseados em casos derivam seu poder da sua ha-</p><p>bilidade em recuperar casos relevantes da base de casos de</p><p>forma eficiente. O fundamental para atingir uma recuperação</p><p>de casos eficiente é saber como essa base de conhecimento</p><p>deve ser indexada de maneira que o processo de recuperação</p><p>seja mais preciso e eficiente.</p><p>Dada a descrição do problema, os índices devem apontar</p><p>quais características do caso devem ser comparadas, determi-</p><p>nando assim o caso que pode ser útil para se chegar a uma</p><p>solução. Isso implica em definir índices nos casos no momento</p><p>de sua inserção na base de casos, para que mais tarde estes</p><p>possam ser recuperados.</p><p>4.1.3 Recuperação de casos</p><p>A etapa de recuperação de casos tem início com uma descri-</p><p>ção de problema e termina quando um caso for encontrado.</p><p>A partir de um novo problema, o sistema procura o caso mais</p><p>parecido na base de casos. Para decidir qual o caso armaze-</p><p>nado na base é parecido ou igual ao novo problema, é preci-</p><p>so medir a similaridade (semelhança) entre eles.</p><p>42 Sistemas Inteligentes</p><p>A recuperação de casos é dividida em três subtarefas: iden-</p><p>tificação das características, comparação e seleção, executa-</p><p>das nessa ordem:</p><p>Identificação das características: identificar um problema</p><p>pode envolver simplesmente suas características de entrada.</p><p>As características não conhecidas podem ser desprezadas ou</p><p>solicitadas para serem explicadas pelo usuário. Por exemplo,</p><p>no sistema Protos (Kolodner, 1993) se uma característica de</p><p>entrada não é conhecida pelo sistema, o usuário deve suprir</p><p>com uma explicação que ligue a característica à rede semân-</p><p>tica existente. Na verdade, essa subtarefa serve para identifi-</p><p>car as características relevantes para a solução do problema,</p><p>descartando as não necessárias. Como visto anteriormente,</p><p>neste trabalho, as características foram encontradas a partir da</p><p>análise matemática e da aquisição de conhecimento.</p><p>Comparação: a subtarefa de comparação busca um con-</p><p>junto de casos candidatos na base de casos.</p><p>Seleção: é um processo onde é selecionado o melhor caso</p><p>do conjunto de casos candidatos, obtido no processo de com-</p><p>paração. A procura de um conjunto de casos é feita pelo uso de</p><p>características, problemas como índices para a base de casos de</p><p>uma maneira direta ou indireta. A recuperação de um caso ou</p><p>de um conjunto de casos pode acontecer de três formas diferen-</p><p>tes: 1) seguindo os índices diretos apontados para as caracterís-</p><p>ticas do problema; 2) procurando uma estrutura de índice; ou</p><p>3) procurando um modelo de domínio de conhecimento geral.</p><p>Diferentes métodos de recuperação podem ser aplicados</p><p>na etapa da recuperação. Eles podem ser aplicados de for-</p><p>Capítulo 4 Sistemas Baseados em Casos 43</p><p>ma combinada também. Os métodos abaixo são os mais</p><p>utilizados:</p><p>Vizinho mais próximo: combina casos recuperados com</p><p>base no somatório de pesos das características do novo pro-</p><p>blema. Os casos com o total de comparações com alguma</p><p>similaridade métrica são retornados do processo de compara-</p><p>ção. O método vizinho mais próximo, Nearest Neighbor, para</p><p>a recuperação dos casos. O algoritmo desse método constitui-</p><p>-se dos passos abaixo:</p><p>Â Dado uma base de casos L.</p><p>Â Dado um novo problema P.</p><p>Â Calcula a similaridade entre os atributos (f) do novo pro-</p><p>blema p e os atributos de cada caso x de L.</p><p>Â Retorna o(s) caso(s) mais parecido(s) com o novo pro-</p><p>blema p.</p><p>n</p><p>Distância(L, p) = ( ∑ w</p><p>f</p><p>* sim(x</p><p>f</p><p>, p</p><p>f</p><p>)2 ) 1/2</p><p>f = 1</p><p>O algoritmo do vizinho mais próximo assume que cada</p><p>caso x = {x1, x2, ..., xn} é definido por um conjunto de n</p><p>características f. Dado um novo problema P, a biblioteca de</p><p>casos L e o peso w de cada atributo f, que é previamente defi-</p><p>nido pelo especialista, o algoritmo recupera o caso mais pare-</p><p>cido com o novo problema, ou seja, aquele que tiver a menor</p><p>distância.</p><p>44 Sistemas Inteligentes</p><p>A função de similaridade local entre o novo problema e os</p><p>casos da base pode se dar da seguinte forma:</p><p>| xf - pf |, ou seja, a distância euclidiana entre os valores,</p><p>quando as características numéricas do caso.</p><p>1, quando existe similaridade (valores são iguais) ou 0,</p><p>quando os valores comparados são diferentes.</p><p>Método de Recuperação Indutivo: torna-se o melhor mé-</p><p>todo quando a meta da recuperação é bem-definida. Casos</p><p>são indexados com base nas características mais importantes.</p><p>Esse método utiliza os atributos mais discriminantes para gerar</p><p>uma árvore de decisão que organiza a base de casos. A árvore</p><p>resultante provê tempos de recuperação mais rápidos do que</p><p>o método de recuperação Vizinho Mais</p><p>Próximo. Consideran-</p><p>do o mesmo exemplo de um sistema de RBC para sugestão</p><p>de empréstimos, a Figura 4.3 apresenta a árvore de decisão</p><p>gerada após a utilização do algoritmo de indução ID3. Os</p><p>atributos mais importantes encontram-se no top da árvore e as</p><p>folhas representam os casos.</p><p>Figura 4.3: Exemplo de árvore de decisão.</p><p>Capítulo 4 Sistemas Baseados em Casos 45</p><p>Observando a Tabela 4.1 podemos perceber que o atribu-</p><p>to status do empréstimo representa a solução de um caso.</p><p>Tabela 4.1: Casos da base (método de indução)</p><p>Casos Status do</p><p>empréstimo</p><p>Rendimento</p><p>mensal</p><p>Tipo do</p><p>emprego</p><p>Pagamento</p><p>mensal</p><p>Caso 1 Bom R$ 2.000,00 Assalariado R$ 200,00</p><p>Caso 2 Ruim R$ 4.000,00 Assalariado R$ 600,00</p><p>Caso 3 Muito bom R$ 3.000,00 Recibo R$ 300,00</p><p>Caso 4 Muito ruim R$ 1.500,00 Assalariado R$ 400,00</p><p>4.1.4 Reutilização de Casos</p><p>A etapa de reutilização de casos para a solução associada ao</p><p>caso recuperado é reutilizada no contexto do novo problema.</p><p>Nessa etapa, os casos similares recuperados na etapa de</p><p>recuperação de casos são apresentados ao usuário.</p><p>4.1.5 Revisão de Casos</p><p>Na etapa de revisão de casos, também conhecida como adap-</p><p>tação de casos onde, após o caso ser recuperado da base,</p><p>o sistema RBC deve adaptar a solução do caso recuperado</p><p>para solucionar o novo problema. A solução associada ao</p><p>caso recuperado deve ser adaptada para as necessidades do</p><p>novo problema. Na maioria dos sistemas, são aplicadas re-</p><p>gras para procurar as diferenças entre o caso recuperado e</p><p>46 Sistemas Inteligentes</p><p>o novo problema e aplicar a solução do caso recuperado ao</p><p>novo problema.</p><p>A adaptação de um caso recuperado no contexto do novo</p><p>problema está focalizada em dois aspectos: 1) as diferenças</p><p>entre o caso passado e o atual; 2) qual parte de um caso recu-</p><p>perado pode ser transferido para o novo caso. São subtarefas</p><p>da reutilização de casos:</p><p>Copiar: na classificação de tarefas simples, as similarida-</p><p>des são consideradas relevantes e a solução do caso recupe-</p><p>rado é transferida para o novo caso como sua solução. Esse é</p><p>um tipo de reutilização trivial.</p><p>Adaptar: existem duas maneiras de reutilizar casos passa-</p><p>dos. A primeira, reutiliza a solução do caso passado (estrutu-</p><p>ral) e a segunda reutiliza o método passado que construiu a</p><p>solução (derivacional), ou seja, como o problema foi resolvido.</p><p>Adaptação estrutural: as regras de adaptação são apli-</p><p>cadas diretamente na solução armazenada nos casos. O sis-</p><p>tema Chef (Hammond, 1986) utiliza esse tipo de adaptação.</p><p>Adaptação derivacional: reutiliza os algoritmos, métodos</p><p>ou regras que geraram a solução original para produzir uma</p><p>nova solução para o novo problema. Esse tipo de adaptação</p><p>é encontrado no sistema Mediator (Simpson, 1985).</p><p>Existem várias técnicas de adaptação de casos, tais como:</p><p>Ajuste de parâmetros: técnica estrutural que compara os</p><p>parâmetros específicos do caso recuperado com o novo pro-</p><p>blema para modificar a solução.</p><p>Capítulo 4 Sistemas Baseados em Casos 47</p><p>Criação de novas instâncias: cria instâncias das velhas</p><p>características com novas características, como, por exemplo,</p><p>o sistema Chef (Hammond, 1986) que cria uma instância de</p><p>uma receita de bife com brócolis, utilizando galinha e espina-</p><p>fre, criando uma nova receita.</p><p>Adaptação nula: quando o sistema não utiliza adapta-</p><p>ção, ou seja, a solução do caso recuperado é aplicada dire-</p><p>tamente ao novo problema. Essa técnica é válida para pro-</p><p>blemas que envolvem um raciocínio complexo, mas com uma</p><p>solução simples.</p><p>4.1.6 Retenção de Casos</p><p>Esse é o processo responsável por armazenar a solução, utiliza-</p><p>da para resolver o problema, junto ao conhecimento existente.</p><p>O aprendizado do sucesso ou da falha da solução proposta</p><p>é disparado pelo resultado da avaliação e possível reparo. É</p><p>preciso selecionar qual informação do caso deve ser retida,</p><p>em que forma vai ser retida, como indexar o caso para uma</p><p>recuperação posterior e como integrar o novo caso à estrutura</p><p>de memória.</p><p>Extrair: a base de casos é atualizada não importando de</p><p>que maneira o problema foi resolvido. Se ele foi resolvido por</p><p>meio do uso de um caso anterior, um novo caso pode ser</p><p>construído. Se o problema foi resolvido por meio de outros</p><p>métodos, com a intervenção do especialista, por exemplo, o</p><p>novo caso precisará ser construído. Por exemplo, no sistema</p><p>Casey (Kotton, 1989), as explicações são incluídas nos casos</p><p>48 Sistemas Inteligentes</p><p>aprendidos e reutilizadas em modificações posteriores de ca-</p><p>sos.</p><p>Índice: esse é o problema dos sistemas de RBC, onde é im-</p><p>portante decidir que tipo de índice utilizar para futuras recupe-</p><p>rações e como estruturar a procura desses índices. É possível</p><p>utilizar índices diretos, porém o problema está na identificação</p><p>de que tipo de índice utilizar. Isso se torna um problema de</p><p>aquisição de conhecimento. Uma solução trivial para esse pro-</p><p>blema é utilizar as características do caso como índices.</p><p>Integrar: essa é a subtarefa final da atualização da base</p><p>de conhecimento com o conhecimento do novo caso. A modi-</p><p>ficação dos índices de casos existentes é uma parte importan-</p><p>te do aprendizado do sistema RBC. Os índices são ajustados</p><p>para um caso ou uma solução particular durante o sucesso</p><p>ou a falha na utilização desse caso para a solução do novo</p><p>problema.</p><p>Recapitulando</p><p>Este capítulo apresentou os sistemas baseados em casos e</p><p>seus principais conceitos. Optamos pelo desenvolvimento des-</p><p>se tipo de sistema quando existe um grande volume de dados</p><p>históricos e muitas exceções às regras.</p><p>Atividades</p><p>1) Um sistema baseado em casos deve ser utilizado quando:</p><p>I – Existe um grande volume de dados históricos.</p><p>Capítulo 4 Sistemas Baseados em Casos 49</p><p>II – Existem muitas exceções às regras.</p><p>III – A experiência pode ser utilizada.</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente a afirmativa II está correta.</p><p>c) As afirmativas I e II estão corretas.</p><p>d) As afirmativas I, II e III estão corretas.</p><p>e) As afirmativas I, II e III estão incorretas.</p><p>2) Sobre as etapas do desenvolvimento de um Sistema Basea-</p><p>do em Casos, é correto afirmar que:</p><p>I – A recuperação de casos depende de como os mesmos</p><p>foram indexados.</p><p>II – Na reutilização dos casos, a solução associada ao caso</p><p>recuperado é reutilizada no contexto do novo proble-</p><p>ma.</p><p>III – A aquisição dos casos é considerada o gargalo do</p><p>desenvolvimento.</p><p>a) Somente a afirmativa I está correta.</p><p>b) Somente a afirmativa II está correta.</p><p>c) As afirmativas I e II estão corretas.</p><p>d) As afirmativas I, II e III estão corretas.</p><p>e) As afirmativas I, II e III estão incorretas.</p><p>50 Sistemas Inteligentes</p><p>3) Sobre os Sistemas Baseados em Casos, não é correto afir-</p><p>mar que esse tipo de sistema:</p><p>a) “Pode aprender automaticamente através da seleção e</p><p>aquisição de novos casos, tornando a manutenção da</p><p>base de conhecimento mais fácil”.</p><p>b) “Permite a reutilização da informação através da utiliza-</p><p>ção de bases de dados, que contenham, implicitamente,</p><p>o conhecimento na solução de problemas do dia a dia</p><p>das instituições”.</p><p>c) “É mais estável e confiável, pois aprende através dos</p><p>casos armazenados na base”.</p><p>d) “Tem na etapa de aquisição de conhecimento o gargalo</p><p>do desenvolvimento do sistema, pois a aquisição de ca-</p><p>sos reais é muito complicada e lenta”.</p><p>e) Nenhuma das alternativas anteriores.</p><p>4) Raciocínio Baseado em Casos é uma abordagem da Inteli-</p><p>gência Artificial que:</p><p>a) Propõe a solução dos problemas por meio da utilização</p><p>de modelos.</p><p>b) Propõe a solução de novos problemas adaptando solu-</p><p>ções que foram utilizadas para resolver problemas ante-</p><p>riores.</p><p>c) Propõe a solução dos problemas por meio da utilização</p><p>de regras.</p><p>Capítulo 4 Sistemas Baseados em Casos 51</p><p>d) Propõe a solução de problemas por meio da adaptação</p><p>de modelos neurais.</p><p>5) Sobre a etapa de Recuperação de Casos, pode-se afirmar</p><p>que:</p><p>a) É a etapa responsável pela indexação dos casos da base.</p><p>b) Preocupa-se em adaptar as soluções dos casos anterio-</p><p>res para o novo problema.</p><p>c) É a etapa considerada</p><p>o gargalo do desenvolvimento de</p><p>sistemas baseados em conhecimento, mas amenizada</p><p>na aquisição de casos.</p><p>d) Identifica e pesquisa índices, calcula a similaridade entre</p><p>o caso recuperado e o novo problema.</p><p>e) Nenhuma das alternativas anteriores.</p><p>Referências bibliográficas</p><p>AAMODT, A. e PLAZA, E. Case-Based Reasoning: Foundatio-</p><p>nal issues, Methodical Variations and System Approaches.</p><p>AI Communications, vol 7(1), 1994.</p><p>ASHLEY, K. Modeling Legal Argument:Reasoning with Cases</p><p>and Hypotheticals. M.I.T. Press, Cambridge, MA, 1990.</p><p>Hammond, K. J., ed. DARPA Case-based Reasoning Workshop.</p><p>San Francisco: Morgan Kaufmann Publishers, 1989</p><p>KOLODNER, J. Case-based reasoning. Morgan Kaufman pub,</p><p>San Mateo, CA, 1993.</p><p>52 Sistemas Inteligentes</p><p>KOTON, P. Using experience in learning and problem solving.</p><p>MIT, Laboratory of Computer Science Ph.D. Dissertation,</p><p>October 1989), MIT/LCS/TR-441</p><p>SIMPSON, R.L. A Computer Model of Case-based Reaso-</p><p>ning in Problem-solving: An Investigation in the Domain of</p><p>Dispute Mediation. PhD thesis, School of Information and</p><p>Computer Science, Georgia Institute of Technology, 1985.</p><p>Gabarito</p><p>1) d</p><p>2) c</p><p>3) d</p><p>4) b</p><p>5) d</p><p>Sistemas de</p><p>Recomendação1</p><p>Apresentação</p><p>Este capítulo apresenta os principais conceitos de Sistemas de</p><p>Recomendação.</p><p>1 Prof. Dra. Fabiana Lorenzi, professora dos cursos da área de Tecnologia e Infor-</p><p>mação da ULBRA Canoas.</p><p>Fabiana Lorenzi1</p><p>Capítulo 5</p><p>54 Sistemas Inteligentes</p><p>5.1 Introdução aos Sistemas de</p><p>Recomendação</p><p>A Internet vem sendo cada vez mais utilizada pelos usuários na</p><p>busca e compra de produtos. O comércio eletrônico apresenta</p><p>facilidades ao usuário, que não precisa mais se deslocar até</p><p>uma loja para efetuar a compra de um determinado produto.</p><p>Entretanto, a quantidade de informação disponibilizada na</p><p>Internet ocasiona uma sobrecarga a este usuário. Comprar um</p><p>produto às vezes pode se tornar uma tarefa difícil. Sistemas de</p><p>recomendação (SR) (Ricci et al., 2011) surgiram com o obje-</p><p>tivo de auxiliar o usuário no processo de tomada de decisão,</p><p>apresentando a ele opções que estejam de acordo com suas</p><p>necessidades. Esses sistemas têm sido utilizados para auxiliar</p><p>na tomada de decisões mesmo que o usuário não tenha co-</p><p>nhecimento suficiente sobre as alternativas existentes.</p><p>SRs são capazes de aprender com as preferências do usu-</p><p>ário e automaticamente sugerir produtos que atendam ao seu</p><p>perfil (Adomavicius e Tuzhilin, 2005). Eles podem ser definidos</p><p>como sistemas que utilizam as opiniões de uma comunidade</p><p>de usuários para auxiliar indivíduos a identificarem conteúdos</p><p>de interesse em um conjunto de opções.</p><p>Para gerar recomendações para um usuário o sistema pre-</p><p>cisa buscar informações sobre esse usuário. Essa busca de in-</p><p>formações pode acontecer de formas diferentes, tais como:</p><p>Explicitamente: quando o usuário interage com o sistema,</p><p>explicitando suas preferências. Exemplos: Crítica (notas), pala-</p><p>vras-chaves utilizadas ou atributos escolhidos.</p><p>Capítulo 5 Sistemas de Recomendação 55</p><p>Implicitamente: quando não existe interação direta com o</p><p>usuário e o sistema utiliza informações do comportamento do</p><p>usuário para descobrir suas preferências. Exemplos: navega-</p><p>ção, objetos comprados, pesquisados, baixados, clicados, re-</p><p>jeitados.</p><p>Por Inferência: quando o sistema consegue prender o perfil</p><p>ou comportamento do usuário.</p><p>5.2 Técnicas de recomendação</p><p>Diferentes técnicas de recomendação podem ser utilizadas pe-</p><p>los sistemas. Essas técnicas se diferem pela forma como as</p><p>informações do perfil do usuário são recuperadas para reco-</p><p>mendar, como, por exemplo:</p><p>Â Resumos estatísticos: as recomendações são geradas</p><p>por meio de resumos estatísticos, como, por exemplo,</p><p>os índices de satisfação do usuário ou os índices de pro-</p><p>dutos mais vendidos.</p><p>Â Seleção manual: é o método de recomendação mais</p><p>simples, onde especialistas que conhecem o público-</p><p>-alvo propõem as recomendações.</p><p>Â Baseado em atributos: um sistema baseado em atributos</p><p>recomenda produtos com base nas características des-</p><p>ses produtos. Para um usuário que gosta de um determi-</p><p>nado escritor, por exemplo, um lançamento de um novo</p><p>56 Sistemas Inteligentes</p><p>livro desse escritor seria uma possível recomendação do</p><p>sistema para ele.</p><p>Â Correlação item-para-item: essa técnica tenta identificar</p><p>produtos que, de alguma forma, estão relacionados a</p><p>produtos que o usuário demonstrou interesse no seu his-</p><p>tórico de interação.</p><p>Â Correlação usuário-para-usuário: essa técnica busca</p><p>recomendar produtos de acordo com a similaridade do</p><p>usuário com outros usuários do sistema.</p><p>A seguir, são apresentadas diferentes técnicas de recomen-</p><p>dação que são atualmente utilizadas por sistemas de recomen-</p><p>dação.</p><p>Top N</p><p>Essa técnica é bem simples e visa recomendar objetos mais as-</p><p>sociados a um grupo de pessoas a partir do uso de estatísticas.</p><p>Normalmente, são apresentados os produtos mais vendidos</p><p>ou mais vistos pelos usuários.</p><p>Exemplos: livros mais vendidos, músicas mais tocadas na</p><p>rádio, artigos mais lidos ou softwares mais baixados.</p><p>A Figura 5.1 apresenta um exemplo de Top 5, em que os 5</p><p>produtos mais vendidos dentro da seção do produto que está</p><p>sendo visto pelo usuário são apresentados ao usuário.</p><p>Capítulo 5 Sistemas de Recomendação 57</p><p>Figura 5.1: Exemplo de recomendação Top 5.</p><p>Cross-sell</p><p>Nesse tipo de recomendação, o sistema tenta apresentar uma</p><p>venda cruzada, ou seja, quem comprou o produto X, também</p><p>comprou o produto Y. Essa técnica é bastante utilizada pelos</p><p>sites do comércio eletrônico na tentativa de apresentar aos</p><p>usuários itens diferentes do que ele está analisando no site.</p><p>58 Sistemas Inteligentes</p><p>A Figura 5.2 apresenta um exemplo de cross sell em que o</p><p>usuário está fazendo uma pesquisa sobre livros sobre sistemas</p><p>multiagentes e o sistema apresenta outra opção de livro que</p><p>também foi comprada por outros usuários.</p><p>Figura 5.2: Exemplo de recomendação Cross Sell.</p><p>Comentários (especialista/revisões do</p><p>usuário)</p><p>A técnica de comentários visa a utilização de comentários por</p><p>parte do usuário. O sistema solicita que o usuário apresente</p><p>uma revisão do produto. Essa revisão pode ser positiva ou</p><p>negativa e pode acontecer de diferentes formas, como, por</p><p>exemplo:</p><p>Capítulo 5 Sistemas de Recomendação 59</p><p>Â Críticas: onde o usuário escreve uma revisão sobre o</p><p>produto.</p><p>Â Gostei ou não gostei: quando o usuário tem apenas</p><p>as opções de “gostei” e “não gostei” para avaliar o</p><p>produto.</p><p>Â Notas: nessa opção, o usuário pode atribuir notas ao</p><p>produto. Normalmente, essa atribuição de notas repre-</p><p>senta o número de estrelas que o produto recebe.</p><p>A Figura 5.3 apresenta um exemplo de revisão por notas de</p><p>um site de comércio eletrônico.</p><p>Figura 5.3: Exemplo de atribuição de notas.</p><p>Filtragem Colaborativa</p><p>Essa técnica de recomendação utiliza a similaridade entre os</p><p>usuários, em uma correlação usuário-a-usuário, que reco-</p><p>menda produtos avaliados de um usuário para outro usuário</p><p>com perfis semelhantes. Essa técnica permite a formação de vi-</p><p>zinhança entre usuários que possuem as mesmas preferências.</p><p>A técnica de filtragem colaborativa é uma das mais utiliza-</p><p>das em SR e ela tenta identificar indivíduos que possuem prefe-</p><p>rências comuns, formando um grupo de indivíduos com gostos</p><p>60 Sistemas Inteligentes</p><p>comuns. Os indivíduos desse grupo colaboram então entre si a</p><p>partir dos produtos que os mesmos gostam para encontrar um</p><p>produto que um usuário-alvo ainda não possua.</p><p>A técnica de filtragem colaborativa funciona da seguinte</p><p>forma:</p><p>Â Os usuários avaliam os produtos em questão, e as ava-</p><p>liações são armazenadas no sistema. Essas avaliações</p><p>são expressas por valores inteiros, normalmente de 1 a</p><p>5 ou 1 a 7, e, quanto maior a avaliação, mais o usuário</p><p>gostou do produto.</p><p>Â Com base nas avaliações já armazenadas, o sistema</p><p>compara essas avaliações com as avaliações dos outros</p><p>usuários; os usuários com maior similaridade entre si</p><p>são agrupados por perfis semelhantes. A maioria dos</p><p>sistemas que utilizam a</p><p>filtragem colaborativa utiliza o</p><p>Coeficiente de Pearson para definir a correlação entre</p><p>os usuários.</p><p>Â O sistema retorna uma predição dos produtos e/ou con-</p><p>teúdos que possam ser mais relevantes ao usuário ativo.</p><p>A Figura 5.4 apresenta um exemplo com quatro usuários</p><p>diferentes e suas avaliações de filmes. O sistema está bus-</p><p>cando uma recomendação para o usuário João. É então cal-</p><p>culada a correlação entre o usuário João e todos os outros</p><p>usuários (Maria Eduarda, Pedro e Luiz Felipe) e tem-se: 0,53</p><p>(João e Maria Eduarda), 0,67 (João e Pedro) e 0,23 (João e</p><p>Luiz Felipe). Serão então recomendados os filmes 7 e 8, pois</p><p>Capítulo 5 Sistemas de Recomendação 61</p><p>eles foram bem-avaliados pelo usuário Luiz Felipe (que é o</p><p>mais similar ao usuário João).</p><p>Figura 5.4: Exemplo de recomendação de filmes.</p><p>Na filtragem colaborativa, a recomendação depende da</p><p>informação prévia de clientes, e é necessário um grande nú-</p><p>mero de interações entre usuários e o sistema para que a re-</p><p>comendação seja confiável.</p><p>Um exemplo da aplicação da filtragem colaborativa é o</p><p>sistema implementado na Amazon.com. Na seção de livros,</p><p>o usuário pode obter recomendação de livros, mas primeiro</p><p>é solicitado que ele colabore, avaliando livros que ele tenha</p><p>lido.</p><p>Outro exemplo é o MovieLens (MILLER et al., 2003) que</p><p>também utiliza a filtragem colaborativa para sugerir filmes ao</p><p>usuário.</p><p>A técnica de filtragem colaborativa se embasa em avalia-</p><p>ções de usuários para gerar a recomendação. Essas avalia-</p><p>ções fornecem ao sistema uma independência de conteúdo,</p><p>gerando recomendações de diversos tipos de produtos. Entre-</p><p>62 Sistemas Inteligentes</p><p>tanto, a capacidade de produzir recomendações de qualidade</p><p>depende das avaliações fornecidas por outros usuários.</p><p>O algoritmo da filtragem colaborativa normalmente é rea-</p><p>lizado em etapas, como, por exemplo:</p><p>Â Cálculo do peso de cada usuário em relação à similari-</p><p>dade ao usuário (métrica de similaridade). Nessa etapa,</p><p>pode-se utilizar o algoritmo de vizinhança (k-nearest-</p><p>-neighbor) para verificar quem são os usuários mais pa-</p><p>recidos.</p><p>Â Seleção de um subconjunto de usuários mais similares</p><p>(vizinhos) ao usuário para considerar na predição.</p><p>Apesar de eficiência, a técnica de filtragem colaborativa</p><p>possui alguns pontos negativos, como, por exemplo:</p><p>Â Problema de cold start: os bons resultados da técnica de</p><p>filtragem colaborativa dependem de avaliações prévias</p><p>de outros usuários. Se o sistema não possuir essas ava-</p><p>liações, temos o chamado problema de cold start, ou</p><p>seja, não tem dados necessários para comparar com o</p><p>usuário que está solicitando a recomendação.</p><p>Â Ovelha negra: o problema da ovelha negra acontece</p><p>quando usuários possuem perfis diferentes dos demais</p><p>usuários ou quando eles são reconhecidos como se-</p><p>melhantes para o sistema, mas na realidade esses usu-</p><p>ários não possuem preferências parecidas para outros</p><p>itens.</p><p>Capítulo 5 Sistemas de Recomendação 63</p><p>Filtragem Baseada em Conteúdo</p><p>A técnica de filtragem baseada em conteúdo utiliza preferên-</p><p>cias (passadas e atuais) de um cliente específico para reco-</p><p>mendar novos produtos a ele. Nessa técnica, apenas os dados</p><p>do usuário atual são utilizados no processo de recomendação.</p><p>Os sistemas de recomendação que utilizam essa técnica</p><p>geram descrições dos conteúdos dos itens de forma automá-</p><p>tica e comparam a descrição de cada item com a descrição</p><p>dos interesses dos usuários ou com o histórico de compras do</p><p>mesmo, com o objetivo de verificar se o item é interessante</p><p>para o usuário em questão.</p><p>O sistema NewsDude (BILLSUS; PAZZANI, 1999), por</p><p>exemplo, observa quais são as histórias que o usuário já leu (e</p><p>também as que ele ainda não leu) e aprende para apresentar</p><p>novas histórias que ele possa estar interessado.</p><p>As comparações são realizadas comparando-se os pro-</p><p>dutos que existem no perfil do usuário a todos os produtos</p><p>possíveis para recomendação, identificando os produtos mais</p><p>similares ao perfil desse usuário. Para tanto, o perfil do usuário</p><p>é um dos pontos-chave para o funcionamento dessa técnica.</p><p>Normalmente, o perfil do usuário contém as características</p><p>descritivas (palavras-chave) dos produtos que o usuário deseja</p><p>ou não deseja. As descrições dos produtos são, geralmente,</p><p>textos que expressam o conteúdo do produto.</p><p>Uma das técnicas mais utilizadas na filtragem baseada em</p><p>conteúdo aplicada em domínios textuais é a TF-IDF (Term-fre-</p><p>quencyInverse-Document-Frequency). Essa técnica calcula a si-</p><p>64 Sistemas Inteligentes</p><p>milaridade de textos baseada na frequência com que palavras-</p><p>-chave aparecem nas descrições dos produtos armazenados</p><p>no banco de dados.</p><p>Para que seja possível determinar a similaridade textual por</p><p>meio da técnica TF-IDF, são necessários os seguintes itens:</p><p>Â Discriminância de palavras: o quanto uma palavra é dis-</p><p>criminante em uma coleção de documentos. Por exem-</p><p>plo: em uma base de textos sobre Tecnologia da Infor-</p><p>mação, a palavra tecnologia não diferencia um texto do</p><p>outro, mas governança sim.</p><p>Â Frequência de palavras: a frequência das palavras co-</p><p>muns entre dois textos é um forte indicativo de similari-</p><p>dade entre eles.</p><p>Â Normalização: a normalização é necessária para reduzir</p><p>a diferença entre documentos grandes e pequenos.</p><p>Antes de aplicar a técnica TF-IDF em um texto, é neces-</p><p>sário executar um pré-processamento nele, retirando as stop-</p><p>words (palavras que não são importantes para análise, tais</p><p>como preposições e artigos) e após executar stemming (extrair</p><p>o radical das palavras). Por exemplo, o texto “Sistemas de re-</p><p>comendação são uma excelente solução para a sobrecarga de</p><p>informações na Internet”, após o processo de stemming seria</p><p>considerado como “Sistema recom excel soluc sobrecarga in-</p><p>for Internet” (Torres, 2004).</p><p>O IDF expressa o quanto uma palavra é discriminante den-</p><p>tro da coleção de documentos. Cada palavra possui um único</p><p>valor IDF em toda a coleção. A fórmula para o cálculo do IDF</p><p>Capítulo 5 Sistemas de Recomendação 65</p><p>é: IDP(p) = log(D/Np), onde D = número de documentos de</p><p>uma coleção e Np = Número de documentos da coleção em</p><p>que a palavra p aparece.</p><p>O TF (taxa de frequência) representa o número de ocor-</p><p>rências de cada palavra em cada um dos documentos ana-</p><p>lisados. Para determinar a similaridade entre os documentos,</p><p>multiplica-se o TF pelo IDF de cada palavra, para construir</p><p>a representação vetorial dos documentos. A partir da repre-</p><p>sentação vetorial, utiliza-se o cosseno entre eles para medir a</p><p>similaridade.</p><p>A técnica de filtragem baseada em conteúdo possui algu-</p><p>mas vantagens, como, por exemplo:</p><p>Â Não possui o problema de cold start: por não precisar</p><p>de avaliações de outros usuários, a filtragem baseada</p><p>em conteúdo não possui o problema de cold start.</p><p>Â Possui a capacidade de recomendar todos os itens:</p><p>Os produtos disponíveis no banco de dados são todos</p><p>comparados com o perfil do usuário, assim, todos os</p><p>produtos possuem chances de serem recomendados ao</p><p>usuário.</p><p>Â O usuário recebe recomendação do que deseja confor-</p><p>me seu perfil formado no sistema, pois, para todo texto</p><p>e/ou atributo, pode ser medida a similaridade com o</p><p>perfil do usuário. Dessa forma, dificilmente um sistema</p><p>de FBC não consegue gerar uma recomendação, ao</p><p>contrário da FC.</p><p>Como desvantagens, podemos citar as seguintes:</p><p>66 Sistemas Inteligentes</p><p>Â Ela não considera alguns aspectos importantes, como,</p><p>por exemplo, a qualidade do texto e o renome do autor.</p><p>Â Superespecialização, que acontece porque, como a técnica</p><p>de filtragem baseada em conteúdo compara as palavras-</p><p>-chave, as recomendações geradas podem ser semelhan-</p><p>tes às palavras-chave encontradas no perfil do usuário.</p><p>Filtragem Baseada em Conhecimento</p><p>A abordagem baseada em conhecimento é considerada com-</p><p>plementar às abordagens filtragem baseada em conteúdo e</p><p>filtragem colaborativa (Burke, 2000). O conhecimento sobre</p><p>clientes e sobre o domínio da aplicação é utilizado para ra-</p><p>ciocinar sobre quais produtos se enquadram melhor, conside-</p><p>rando</p>