Raciocínio baseado em casos - uma visão geral e métricas de similaridade

Processando o Saber , nº 1, 2003 49 RACIOCÍNIO BASEADO EM CASOS - UMA VISÃO GERAL E MÉTRICAS DE SIMILARIDADE PESSÔA, SÁ, Fábio, Mestrando* NAKAMITI, G., Dr.** * Faculdade de Tecnologia da Baixada Santista – Campus Praia Grande Departamento de Informática Gestão de Negócios – Praça 19 de Janeiro 144, 11700-100 Praia Grande/SP - Fone (13) 3591-1303 [email protected] ** UNIP - Universidade Paulista - Rua Dr. Bacelar, 1212 - São Paulo/SP UNISANTOS - Universidade Católica de Santos - Rua Carvalho de Mendonça, 144 5º andar - Santos/SP [email protected] RESUMO Raciocínio Baseado em Casos trata-se de um modelo computacional bastante utilizado em diversos sistemas inteligentes. Essa abordagem tem motivado pesquisadores a criarem sistemas para diferentes domínios, assim como possibilidades de sistemas integrados com outras abordagens graças à flexibilidade e simplicidade desse modelo. A seção “Métricas de Similaridade” apresenta alguns modelos de métricas mais utilizados e a seção “Perspectivas para o Futuro” ilustra algumas aplicações e tendências dessa área. PALAVRAS-CHAVE: Raciocínio Baseado em Casos, Aplicações Help Desk, Métricas de Similaridade ABSTRACT Reasoning based in cases deals with computational models very much used in several intelligent systems. This approach has motivated researchers to create systems for different dominion as well as possibilities of integrated systems with other approaches thanks to the flexibility and simplicity of this model. The section “Metrics of Similarity” presents some models of metrics more used and the section “Perspectives for the Future” shows some applications and tendencies in this field. KEY-WORDS: Reasoning based in cases, Help Desk Applications, Metrics of Similarity DOI: https://doi.org/10.5281/zenodo.14188200 Processando o Saber, nº 1, 2003 50 INTRODUÇÃO Freqüentemente, o termo “raciocínio” é explicado como um processo de relacionamento de idéias, começando do nada. O dicionário Aurélio confirma essa definição como um “encadeamento, aparentemente lógico, de juízos ou pensamentos”. Raciocínio baseado em casos (RBC) tem uma concepção bastante diferente. Em RBC, a origem do conhecimento não é gerada por regras, mas por uma memória de casos guardados, registrados em episódios anteriores (LEAKE, 1996). Vários exemplos podem ilustrar essa importante abordagem da Inteligência Artificial (IA): empresas procuram profissionais qualificados através de anúncios, onde se destaca a busca por candidatos com experiência prévia em determinados serviços. É bem coerente que empresas de suporte em informática procurem candidatos que já tenham enfrentado problemas e encontrado soluções, caracterizando sua experiência pela prática adquirida no exercício constante de sua profissão. Tais profissionais adquiriram habilidades em suas tarefas enfrentando eventuais problemas com as respectivas soluções, resultando em diversos casos. O profissional de suporte, em seu dia-a-dia, encontra soluções para seus problemas novos através da lembrança ou recuperação de problemas similares anteriores, que pode ser através da sua memória ou consulta a documentações. Encontra também problemas diferentes, mas com soluções parecidas, cabendo então a adaptação de um caso que ele conhecia. No processo de remoção de um vírus de computador, por exemplo, o profissional de suporte em informática pode lembrar de uma solução utilizada anteriormente, ainda que seja para a remoção de um vírus diferente. Se funcionar, a solução deve ser revisada e devidamente armazenada, para soluções de problemas futuros, caracterizando um aprendizado desse profissional. Isso leva a crer que um profissional qualificado mantém diversos casos em sua memória. Logo, quanto mais casos adquiridos, mais experiência e melhor capacidade para executar sua função farão parte do currículo deste profissional. Esse é um dos motivos porque chamamos uma base de casos também de banco de experiências. Processando o Saber , nº 1, 2003 51 Podemos utilizar o RBC em diversas situações. De um modo geral pode-se dizer que esse sistema reutiliza experiência prévia para: (NAKAMITI, FREITAS, 1999). a) explicar novas situações (suporte em informática); b) encontrar novas demandas; c) interpretar novas situações (advogados); d) criticar novas soluções; e) criar uma solução justa para um novo problema (juízes). Estes exemplos ilustram a simplicidade do sistema RBC, mas merecem algumas explicações dos pré-requisitos, os passos essenciais, e as diferenças em comparação com outras abordagens de construção de sistemas baseados em conhecimento. O primeiro e mais importante pré-requisito é a coleção de experiências, denominados casos, armazenados na base de casos. Cada caso consiste ao menos em parte da descrição do problema, denominado problema, e parte da descrição da solução, denominada solução. Estes dois ingredientes básicos são normalmente enriquecidos por uma parte administrativa que pode incluir, por exemplo, uma identificação do caso, uma parte que explica ou justifica e que oferece mais informação sobre os passos da solução do problema em direção à solução, uma parte da descrição do contexto, e uma parte de avaliação que contém informações sobre a qualidade e a reutilização do caso. Pode-se descrever a solução de um problema com um sistema RBC pelo seguinte: Um novo problema aparece e é descrito como parte de um novo caso. Então, casos antigos contendo problemas similares são recuperados, e o mais adequado à sua solução é escolhido a tornar-se solução do novo problema. Essa solução é então testada e eventualmente guardada como um novo caso. Este último passo caracteriza uma das importantes etapas desse sistema que é o aprendizado (SPÖRL, LENZ, HÜBNER,1999). Além da base de casos composto por casos que representam situações anteriores, os sistemas de raciocínio baseado em casos requerem mecanismos para recuperá-los da base de casos, adaptá-los para o caso corrente, validar a solução proposta e armazenar o conhecimento obtido durante o processo. Processando o Saber, nº 1, 2003 52 Na figura 1 são mostradas as etapas de um Ciclo RBC clássico, que muitas vezes podem ter suas nomenclaturas diferenciadas: Problema Solução Confirmada Solução Proposta Novo Caso Caso Aprendido Caso Solucionado Caso Testado/Reparado RECUPERAÇÃO REUTILIZAÇÃO ARMAZENAMENTO REVISÃO Caso Recuperado Novo Caso Base de Casos Figura 1. Ciclo RBC. Aamodt, Plaza (1994) Pode-se citar os seguintes mecanismos encontrados no ciclo RBC: Recuperação: Através de uma indexação adequada é que se pode recuperar casos de forma eficiente. A escolha dos itens que farão parte das chaves da indexação assim como sua organização na memória, determinará a eficiência da busca na base de casos. Reutilização: Também chamado de Adaptação, este processo envolve a identificação das diferenças entre o caso recuperado e o caso corrente e a análise das partes do caso recuperado que podem ser transferidas para o caso corrente. Processando o Saber , nº 1, 2003 53 Revisão: Serve para saber se a solução gerada pelo sistema satisfaz as novas especificações. Podem ser feitas de formas diferentes, inclusive simulações. Armazenamento: Uma vez armazenado, caracteriza-se de alguma forma um aprendizado, de modo a poder ser utilizado mais tarde. Destaca-se nessa etapa especificar o que será aprendido, separar o que é importante do desnecessário. Na seção dois é apresentado um breve histórico dos sistemas de RBC. Na seção três são descritas formas de classificação desses sistemas, os tipos e suas principais características. Na seção quatro é apresentada a fundamentação teórica, onde se encontram entre outras definições, a do contêiner do conhecimento. A seção sete coloca uma das partes mais importantes de um sistema RBC, as métricas de similaridade, considerada por alguns autores como o núcleo do sistema. Em seguida, um destaque para aplicações help-desk, uma aplicação bastante natural para esses sistemas e, finalmente, uma seção sobre as perspectivas futuras onde podese encontrar aplicações para web e comércio eletrônico. HISTÓRICO Em 1977, Schank e Abelson propuseram que o conhecimento geral das pessoas sobre as situações está armazenado em scripts, permitindo que elas criem expectativas sobre o que ouvem, e assim, construam inferências sobre as relações entre as coisas das quais ouviram. Os scripts foram propostos como uma estrutura de memória conceitual, descrevendo informação sobre eventos estereotipados, como ir a um restaurante ou a uma consulta a um médico. Experimentos com scripts mostraram, entretanto, que eles não representam uma teoria completa de representação de memória, já que as pessoas confundem eventos que tem scripts similares. Os scripts fornecem apenas um tipo de conhecimento que as pessoas utilizam para o entendimento: elas se valem de também outros tipos de conhecimento, como o conhecimento sobre objetivos, planos, relações interpessoais e papéis efetuados pelas pessoas (KOLODNER, 1993). Representações sobre estes tipos de conhecimento têm sido propostas e sistemas de computadores que usam estes tipos de conhecimento para o entendimento têm sido desenvolvidos. Processando o Saber, nº 1, 2003 54 Em 1982, Roger Schank propôs a teoria da memória dinâmica (dinamic memory) e o papel central que a lembrança de situações anteriores (episódios, casos) e modelos de situações (scripts, MOPs — pacotes de organização de memória) desempenham na resolução de problemas. Este trabalho, segundo Plaza (1994), apresenta as raízes do uso de raciocínio baseado em casos na Inteligência Artificial. O primeiro sistema RBC, denominado CYRUS, foi desenvolvido por Janet Kolodner (1983). Este sistema, baseado no modelo de memória dinâmica de Schank e na teoria MOP de resolução de problemas e aprendizado, foi basicamente um sistema de questões e respostas com conhecimento de várias viagens e encontros do primeiro secretário de estado americano, Cyrus Vance. O modelo de memória de casos desenvolvido por este sistema serviu de base para outros diversos sistemas RBC, como MEDIATOR - (SIMPSON, 1985), PERSUADER - (SYCARA, 1988), CHEF - (HAMMOD , 1989), JULIA - (HINRICHS, 1992), CASEY - (KOTON, 1989). Outra base de RBC e conjunto de modelos foi desenvolvida por Bruce Porter e seu grupo na Universidade do Texas, em Austin. Inicialmente trabalhando com o problema de aprendizado automático para classificação de tarefas, o grupo desenvolveu o sistema PROTOS - (PLAZA, 1994). Esse sistema enfatiza a integração do conhecimento geral do domínio e do conhecimento específico de casos em uma estrutura de representação unificada — um modelo de memória de casos. Além dessa, outra contribuição importante para a área foi o trabalho do grupo de Edwina Rissland na Universidade de Massachussetts, em Amherst, que desenvolveu o sistema HYPO, aplicado para o domínio do Direito. Atualmente, as pesquisas em RBC têm estendido-se rapidamente, sendo percebido um crescente número de trabalhos envolvendo RBC em periódicos de IA e um aumento de aplicações comerciais de sucesso, além de pesquisas em desenvolvimento em diversos países. (WATSON, 1994). CLASSIFICAÇÃO Existem dois estilos básicos de raciocínio baseados em casos: solucionadores de problemas e interpretativos. No estilo dos RBC solucionadores de problemas, soluções para o novo Processando o Saber , nº 1, 2003 55 problema são criadas usando soluções prévias. Soluções prévias podem oferecer soluções aproximadas para os novos problemas além de avisos de falhas ou erros potenciais. Podem ser usados em uma grande variedade de tarefas de solucionadores de problemas, incluindo: − planejamentos - Ex. PLEXUS - (ALTERMAN, 1988), CHEF - (HAMMOND, 1989); − diagnósticos - Ex. SHRINK - (KOLODNER, 1987), PROTOS - (BAREISS, 1989); − projetos - Ex. JULIA - (HINRICHS, 1992). Em cada um desses tipos de RBC solucionadores de problemas, os casos são úteis para sugerir soluções e avisar sobre possíveis problemas que possam surgir. No estilo interpretativo de RBC, situações novas são avaliadas no contexto de situações prévias. Isso determina uma situação ou solução como uma entrada. Um advogado, por exemplo, faz uso de um raciocínio baseado em casos interpretativos quando ele utiliza uma série de casos prévios para justificar um argumento em um novo caso. Existem três tarefas onde o RBC interpretativo pode ser utilizado: − justificação - Ex. HYPO; − interpretação - Ex. HYPO - (ASHLEY, 1988); − projeção - Ex. BATTLE PLANNER - (GOODMAN, 1989). Esses tipos de RBC interpretativos dividem uma mesma linha de argumentação, alguns casos suportam somente uma interpretação ou efeito, outros suportarão várias interpretações ou efeitos. O sistema raciocinador deve comparar e diferenciar os casos entre eles para finalmente determinar uma solução. FUNDAMENTAÇÕES TEÓRICAS A seguir, serão apresentados alguns conceitos importantes para o estudo de sistemas de RBC. Similaridade de Casos: Similaridade em RBC é uma tentativa de representar a utilidade de um caso prévio para resolver um problema de um Processando o Saber, nº 1, 2003 56 caso corrente. Deve-se notar que um caso pode ser considerado similar ao problema corrente se a solução deste caso pode ser facilmente reutilizada para o problema. Mas, em geral, isso pode ser determinado depois de tentar a reutilização dessa solução para o problema atual. Deve-se assumir também que, quanto mais o caso prévio for parecido com o problema atual, mais útil será a solução para o caso corrente. Pode-se entender que o interesse sobre similaridade de casos se relaciona mais sobre a similaridade da descrição do problema prévio em relação ao problema atual. Contêiner de Conhecimento em RBC: Cada um dos quatro mecanismos: recuperação, reutilização, revisão e armazenamento, denominados modelo R4 (figura 1) formam um tipo de “contêiner” de um número de técnicas refinadas que podem ser utilizadas para implementação de um sistema RBC. Recuperação, por exemplo, inclui a identificação das características relevantes, a pesquisa através da memória dos casos, o cálculo dos valores de similaridade e a seleção dos casos mais parecidos. A pesquisa pode se implementada por um número de técnicas alternativas como: indexação, pesquisa linear, pesquisa de estruturas especiais, etc. O modelo de contêiner de conhecimento foi introduzido por Richter (1995). Ele é útil particularmente para descrever qual tipo de conhecimento pode ser incorporado em um sistema RBC e como tais componentes interagem. Um contêiner de conhecimento é usado para extrair conhecimento de uma determinada estrutura. Por exemplo, em sistemas baseados em regras tradicionais existem três contêineres: fatos, regras e o mecanismo de inferência. Em RBC, quatro principais contêineres podem ser identificados: − vocabulário, usado para descrever casos; − métrica de similaridade, utilizada para comparar casos; − base de casos, contendo todos os casos armazenados; − tecnologia de adaptação, necessária para transferência de soluções. Cada contêiner pode em princípio carregar e oferecer qualquer parte de conhecimento para resolver um problema corrente. Por exemplo, um sistema Processando o Saber , nº 1, 2003 57 RBC com uma base de casos completa se faz independente de outra parte de conhecimento, como a métrica de similaridade ou a adaptação. Ou seja, o sistema poderia ser implementado como um banco de dados tradicional. Métodos para Recuperação de Casos: Nos últimos anos, um número de técnicas tem sido desenvolvidas de modo a implementar tarefas de recuperação. Ex.: pesquisa por casos similares a uma questão, incluindo: − kd-trees combinando RBC e indução, visando deste modo, permitir uma recuperação baseada em similaridade e árvores de decisão. A vantagem desta abordagem é que métodos de RBC podem ser integrados com técnicas de aprendizado indutivo. Auriol, Wess, Manago, Althoff, Traphöner (1997). Isto parece ser particularmente útil para tarefas de diagnóstico. Lenz (1996). − O modelo Fish-and-Shrink, desenvolvido com o projeto FABEL, parece ser particularmente útil para domínios onde há necessidade de casos altamente estruturados, como em projetos. Börner (1996). − O modelo Redes de Recuperação de Casos (RRC), por outro lado, é ideal para domínios com a representação de casos simples, e ainda assim, lidar com base de casos grandes. Lenz, Dburkhard (1996), o que é essencial em aplicações de comércio eletrônico. Wilke, Lenz, Wess (1996). A flexibilidade de modelos RRC permite sua utilização em casos de alta desestruturação, como em RBC’s textuais. Cada uma dessas técnicas tem suas propriedades específicas, vantagens e desvantagens. Ao desenvolver um sistema RBC em particular, o domínio deve ser analisado cuidadosamente de modo que se possa escolher qual método de recuperação mais apropriado. Adaptação de Casos: Os casos similares recuperados por um sistema RBC muitas vezes não poderão ter uma aplicação direta em um problema corrente, dadas as diferenças entre as descrições dos problemas entre os casos. Conseqüentemente, as soluções devem ser ajustadas ao problema atual, caracterizando a adaptação. Em um caso geral, as adaptações se encaixam na mesma classe de problemas em uma solução baseada em conhecimento. Mas na prática existem situações onde adaptações podem ser bem mais fáceis de realizar, podendo ser percebidas e resolvidas. Processando o Saber, nº 1, 2003 64 BAREISS, E. R.: Exemplar-Based Knowledge Acquisition: A Unified Approuch to Concept Representation, Classification, and Learning. Academic Press, Boston, MA. 1989 BAREISS, R., and King J.: Similarity Assessment in Case-Based Reasoning. Proceedings of the 1989 DARPA workshop on case-based reasoning, Morgan Kaufman, Pensacola Beach, FL, pp. 67-71. 1989 BÖRNER, K..: CBR for Design. In Case Based Reasoning Technology – From Foundation to Application. Chapter 8, pages 201-234. 1996 GOODMAN, M.: CBR in battle planning. In Hammond, K. (Ed.), Proceedings: Case-Based Reasoning Workshop (DARPA), II, MorgamKaufmann. Pensacoia Beach, FL. 1989. HAMMOND, K. J.: Case-Based Planning: Viewing Planing as a Memory Task. Academic Press, Boston, MA. 1989. Hinrichs, T. R.: Problem solving in open worlds. Lawrence Erlbaum Associates, 1992. KOLODNER, J. L.: Maintaining organization in a dynamic long-term memory. Cognitive Science, Vol. 7, s.243-280. 1983 KOLODNER, J. L.: Case-Based Reasoning. San Mateo: Morgan Kaufmann, 1993. KOTON, Phyllis: Using experience in learning and problem solving. Massachusetts Institute of Technology, Laboratory of Computer Science (Ph.D. diss, October 1988). MIT/LCS/TR-441. 1989. LEAKE, D. B.: Appears in Leake, D., editor; Case-Based Reasoning: Experiences, Lessons, and Future Directions. AAAI Press/MIT Press, 1996. LENZ, Mario and H. Dburkhard: Case Retrieval Nets: Basic ideas and extensions. Em Görz an Hölldobler. Pages 227-239. 1996. LENZ, Mario: CBR for Diagnosis and Decision Support. Burkhard, P. Pirk, E. Auriol, and M. Manago.. AI Communication, 9(3): 138-146, 1996 NAKAMITI, G. e FREITAS, R.: Raciocínio Baseado em Casos: Uma visão Geral. 1999 Processando o Saber , nº 1, 2003 65 PAZZANI, Cain T. M. J. & Silverstein, G.: Using Domain Knowledge to Influence Similarity Judgments. In: Proceedings Case-Based Reasoning Workshop, May/91. Washington, D.C., Morgan Kaufmann Publishers, 191199, 1991 RICHTER, M. M..: The knowledge contained in similarity measures. Invited Talk at ICCBR-1995 SCHANK, R. C.: Dynamic Memory, A Theory of Reminding and Learning in Computers and People. New York, Cambridge University Press, 1982 SCHILD, U. J. & Kerner, Y.: Multiple Explanation Patterns. In: Topics in Case Based Reasoning. First European Workshop, EWCBR-93. Berlin, Germany, Springer-Verlag, 353, 364. 1994. SIMPSON, Robert L.: A computer model of case-based reasoning in problem solving: An investigation in the domain of dispute mediation. Technical Report GIT-ICS-85/18, Georgia Institute of Technology. 1985. SPÖRL, Lenz, Hübner: Case-Based Reasoning - Survey and Future Directions. To appear in Proc. XPS-99, Springer Verlag, LNAI STANFILL, C. & Waltz, D.: Towards Memory-Based Reasoning. Communication of ACM, vol 29 no. 12;1213-1228. 1996. STOTTLER, R. H.: Case-Based Reasoning for Bid Preparation. AI Experts, 44-49, March 1992. SYCARA, K.: Using case-based reasoning for plan adaptation and repair. Proceedings Case-Based Reasoning Workshop, DARPA. Clearwater Beach, Florida. Morgan Kaufmann, pp. 425-434. 1988. WATSON, Ian; Marir, Farhi.: Case-based Reasoning: A review. The Knowledge Engineering Review, London, v.9, n.4, p. 327-354, 1994. WILKE, W., Lenz, Mario and Wess, S..: Intelligent Sales Support with CBR. In Case Based Reasoning Technology – From Foundation to Application. 1996. YANG, H., Lu, W. F. & Lin, A. C. PROCASE: A Case-Based Process Planning System for Matching of Rotational Parts. Journal of Intelligent Manufacturing, vol. 5:430, 1994