Sistemas Periciais 2022-23 PDF

SISTEMAS PERICIAIS EXPERT SYSTEMS Inteligência Artificial Joaquim Filipe  2 SISTEMAS PERICIAIS VS. INFORMÁTICA CONVENCIONAL Razão de ser dos sistemas periciais Sistemas de apoio à decisão...

SISTEMAS PERICIAIS EXPERT SYSTEMS Inteligência Artificial Joaquim Filipe  2 SISTEMAS PERICIAIS VS. INFORMÁTICA CONVENCIONAL Razão de ser dos sistemas periciais Sistemas de apoio à decisão Meta-modelos da realidade? Decisão/Ação Informação ou conhecimento? Sintaxe vs. semântica vs. pragmática Resolução de problemas Complexos, sem solução algorítmica Usando heurísticas, i.e. conhecimento humano Modelos vs. Teorias Inteligência Artificial © Joaquim Filipe  3 ALGORITMO Sequência finita de instruções bem definidas, não ambíguas, para resolver um problema particular num intervalo de tempo finito com uma quantidade de esforço finito. (Introdução à Informática, usando o Pascal – Pavão Martins) Inteligência Artificial © Joaquim Filipe  4 INTELIGÊNCIA ARTIFICIAL A Inteligência Artificial interessa-se por desenvolver máquinas para resolver problemas em que de momento os seres humanos são melhores. (Artificial Intelligence, Elaine Rich) Inteligência Artificial © Joaquim Filipe  5 PROBLEMA Frequentemente as pessoas são capazes de resolver problemas para os quais não existe uma solução algorítmica conhecida. Nesses casos a informática convencional tem um problema. É necessário recorrer a técnicas de IA Inteligência Artificial © Joaquim Filipe  6 MODELOS A realidade é demasiado complexa. Realidade ➔ É necessário usar modelos para interagir com a realidade e resolver problemas. Inteligência Artificial © Joaquim Filipe  7 EXEMPLOS Sistema de produção de papel da PORTUCEL Diagnóstico de avarias Modelos físicos são possíveis mas demasiado complexos Modelos físicos dos processos não são usados na prática Em vez disso usam-se modelos heurísticos. Sistema Financeiro Gestão de carteiras de ativos Modelos matemáticos são falíveis devido à complexidade do mercado e à subjetividade dos agentes A utilização desses modelos assenta em pressupostos que nem sempre são válidos (vide crises bolsistas) Em vez disso usa-se modelos de preferências e de utilidade, os quais são subjetivos e nem sempre coerentes Inteligência Artificial © Joaquim Filipe  8 TEORIAS VS. MODELOS Um modelo é uma simplificação da realidade. Modelos Uma teoria é um modelo internamente consistente em termos sintáticos, i.e. Teorias não contém contradições. E a Semântica? Boas Uma boa teoria deve ser Teorias válida, i.e. deve ser um Realidade modelo semanticamente consistente. Inteligência Artificial © Joaquim Filipe  9 A TEORIA E A PRÁTICA Não há nada mais prático do que uma boa teoria. Uma boa teoria deverá ter poder descritivo e prescritivo e por isso ajudar a compreender a realidade e a resolver problemas. Inteligência Artificial © Joaquim Filipe  10 RESOLUÇÃO DE PROBLEMAS Dilema sobre a abordagem à resolução de problemas: A) modelar a realidade? Conhecimento rigoroso (teórico) Aplicar algoritmos que oferecem soluções rigorosas. B) modelar a forma como a pessoa vê a realidade? Conhecimento empírico Aplicar heurísticas Inteligência Artificial © Joaquim Filipe  SISTEMA PERICIAL: UM 11 META-MODELO? Método de Método de modelação indireto modelação direto Realidade Modelo Modelo Informal Formal (Humano) (Matemático) da Realidade da Realidade Sistema Pericial: não Algorítmico Programa Convencional: Algorítmico Inteligência Artificial © Joaquim Filipe  12 MODELAÇÃO INDIRETA DO CONHECIMENTO DO ESPECIALISTA O Especialista A Realidade Conhecimento Simbólico: Factos, Regras Raciocínio Lógico O Sistema Pericial Inteligência Artificial © Joaquim Filipe  13 ARQUITETURA Inteligência Artificial © Joaquim Filipe  14 CARACTERISTICAS DOS PRINCIPAIS COMPONENTES Base de Conhecimento: Contém os modelos de domínio Factos e Regras Dependente do domínio Hipótese do “mundo fechado” Natureza essencialmente declarativa Máquina de Inferência Contém os mecanismos lógicos de raciocínio Independente do domínio Natureza essencialmente procedimental Inteligência Artificial © Joaquim Filipe  15 EXPLICAÇÃO Um sistema pericial pode errar, na medida em que: Reflete o conhecimento de seres humanos (ainda que especialistas no domínio de aplicação) Pode ter uma base de conhecimento incompleta Necessário providenciar mecanismos de validação ao utilizador do sistema O módulo de explicação indica a sequência de regras aplicadas pelo sistema e respetiva instanciação com factos presentes na base de conhecimento Inteligência Artificial © Joaquim Filipe  16 EXEMPLOS: MYCIN Desenvolvido em Stanford / Ed. Shortliffe et al. 1970’s Objetivos: Diagnóstico de infeções bacteriológicas Prescrição de terapia baseada no diagnóstico Características: Bloco de notas ativo Modelo do especialista humano / Não substitui o especialista Diálogo em formato de linguagem natural, próximo do especialista Desempenho verificável, comparável ao dos especialistas Inteligência Artificial © Joaquim Filipe  17 EXCERTO DE DIÁLOGO Inteligência Artificial © Joaquim Filipe  18 DIPMETER ADVISOR Schlumberger / Luc Steels 1977 Objetivos: Interpretação de medições geofísicas Identificação de estruturas baseadas em compostos orgânicos (petróleo, gás, etc.) Características: Bloco de notas ativo Permite análise detalhada de partes do problema Interface visual diretamente utilizável pelo especialista Inteligência Artificial © Joaquim Filipe  19 EXEMPLO DE REGRA Inteligência Artificial © Joaquim Filipe  20 XCON Carnegie-Mellon Uni. / John Mc Dermott 1978 para a Digital Equipment Corporation (DEC) Objetivos: Configuração de computadores da família VAX Caracteristicas: Problema complexo: Mais de 400 componentes só para o VAX 11/780 Mais de 5,000 regras e mais de 20,000 componentes Pioneiro na área de SPs aplicados à tecnologia Elevado sucesso prático Mais de US$25 milhões em poupanças por ano Inteligência Artificial © Joaquim Filipe  21 AUTHORIZER'S ASSISTANT American Express (AMEX) Desenvolvido pela Inference Corp (agora MindBox) em 1988 Esteve em produção contínua e em desenvolvimento desde essa altura. Aplica-se agora a todos os produtos da AMEX. Contém mais de 35,000 regras Aumento de 20% na produtividade Redução em 33% do crédito não concedido Elevado ROI Inteligência Artificial © Joaquim Filipe  22 EMYCIN Inteligência Artificial © Joaquim Filipe  23 SHELLS Ferramentas de desenvolvimento de sistemas periciais Análogas às ferramentas CASE Aplicáveis a qualquer domínio Permitem a reutilização da máquina de inferência, dado que esta é: De natureza sintática Independente do domínio de aplicação Exige a construção da base de conhecimento, dado que esta é: De natureza semântica Dependente do domínio de aplicação Inteligência Artificial © Joaquim Filipe  24 SHELLS JESS – Java Expert System Shell Sandia National Labs (fundado em 1940 para realizar o projeto Manhattan) http://herzberg.ca.sandia.gov/ CLIPS – C Language Integrated Production System NASA's Johnson Space Center (de1985 a1996) http://clipsrules.sourceforge.net/ EXSYS – Expert System Software and Services http://www.exsys.com/ E muitas outras: http://www.kbsc.com/rulebase.html Inteligência Artificial © Joaquim Filipe Inteligência Artificial © Joaquim Filipe 25 RACIOCINIO LÓGICO EM SISTEMAS PERICIAIS  26 INFERÊNCIA/RACIOCÍNIO LÓGICO EM GERAL Raciocínio dedutivo P➔Q Usando o silogismo lógico Q➔R Resultados garantidamente válidos Então: P ➔ R Análogo às relações entre conjuntos (A contém B) Raciocínio indutivo Usando formas de generalização/extrapolação Resultados não são garantidamente válidos Raciocínio abdutivo Usando as observações para procurar uma explicação provável Frequentemente usado em medicina Resultados não são garantidamente válidos Inteligência Artificial © Joaquim Filipe  27 QUANTAS LÓGICAS? Proposicional ou de ordem zero: conjunto de expressões sintáticas (fórmulas bem formadas, ou fbfs) atómicas. Exemplo: A^B Predicativo ou de primeira ordem: fbfs são quantificáveis e decomponíveis em termos Termos: constantes, variáveis e predicados (funções booleanas que podem receber variáveis como argumentos). Exemplo: ∀𝑥 ℎ𝑜𝑚𝑒𝑚 𝑥 → 𝑚𝑜𝑟𝑡𝑎𝑙(𝑥) Modal ou de ordem superior: fbfs incluem predicados de ordem superior. Um predicado de ordem superior tem um ou mais predicados como argumentos. Em geral, um predicado de ordem superior de ordem n toma um ou mais predicados de ordem (n − 1) como argumentos, onde n > 1. Inteligência Artificial © Joaquim Filipe  28 BASE DO RACIOCINIO DEDUTIVO Silogismo Lógico Equivalente a: Modus Ponens P➔ Q Quando chove há nuvens no céu P Está a chover Q Então: há nuvens no céu Modus Tollens (lei da contraposição / redução ao absurdo) P➔ Q Quando chove há nuvens no céu ~Q Não há nuvens no céu ~P Então: não está a chover Inteligência Artificial © Joaquim Filipe  29 ENCADEAMENTO PARA A FRENTE O raciocínio dedutivo pode encadear regras de dois modos: Modo dirigido por dados (data driven) Encadeamento para a frente (forward chaining) Base de factos: Premissa A R1 Conclusão C Facto A R2 Conclusão D R4 Conclusão F ➔ Facto C (R1) ➔ Facto D (R2) R3 Conclusão E Premissa B Facto B ➔ Facto E (R3) ➔ Facto F (R4) Inteligência Artificial © Joaquim Filipe  30 ENCADEAMENTO PARA TRÁS Modo dirigido por objetivos (goal driven) Encadeamento para trás (backward chaining) Começa por se colocar uma hipótese, a qual se tenta demonstrar com dados-base (ground data) Base de factos: Premissa A R1 Facto A Conclusão C Facto B R2 Conclusão D Conclusão F R4 Hipótese F  C, D, E R3 Conclusão E Hipótese C Premissa B  A (base) Hipótese D  A (base) Hipótese E  B (base) Inteligência Artificial © Joaquim Filipe  31 SISTEMAS DE PRODUÇÃO Sistema computacional baseado em regras de comportamento (de produção). Cada regra de produção tem duas partes: IF (precondição sensorial ou premissa) THEN (ação ou conclusão) Se uma precondição satisfaz (matching) o Post 1941 estado corrente do mundo, então a ação da regra é “disparada” (fired). A precondição também é designada por “Lado esquerdo” (left-hand side, LHS) e a ação por “Lado direito” (right-hand side, RHS) Inteligência Artificial © Joaquim Filipe  32 FACTOS, PADRÕES E REGRAS BASE DE CONHECIMENTO As variáveis têm nomes começados por ? Factos (homem Socrates) + Regras (R1 (homem ?x) => (mortal ?x)) LHS => RHS (homem ?x) é um Padrão Inteligência Artificial © Joaquim Filipe  33 CONCEITOS BÁSICOS DO PROCESSO DE INFERÊNCIA Memória permanente ou memória de longo prazo (modelos de domínio) Memória de trabalho ou memória de curto prazo (modelos de caso) Ciclo de encadeamento para a frente: emparelhar activar resolver conflito disparar. Inteligência Artificial © Joaquim Filipe  34 EMPARELHAMENTO (MATCHING) O emparelhamento é feito elemento a elemento, por ordem. Constante ~ Constante Variável ~ Variável ou Constante (mediante uma substituição adequada) O resultado do emparelhamento de um padrão com um facto é uma substituição (de variáveis) Exemplo: (a ?x ?y) ~ (a b c) ➔ ((?x b) (?y c)) Inteligência Artificial © Joaquim Filipe  35 ATIVAÇÃO DE REGRAS Se o lado esquerdo emparelhar com um ou mais factos na base de conhecimento, então a regra é ativada. Exemplo Regra R1: (a ?x c) (b) => (d ?x) Factos na Base de Conhecimento: F1: (a); F2: (a b c); F3: (b) A regra R1 é ativada com a substituição: ((?x b)) Inteligência Artificial © Joaquim Filipe  36 RESOLUÇÃO DE CONFLITOS Um conflito surge quando várias regras podem ser activadas simultaneamente; Nesse caso é preciso escolher uma regra para “disparar”. A escolha é determinada por critérios heurísticos (por exemplo: regra com maior número de premissas) Inteligência Artificial © Joaquim Filipe  37 DISPARAR UMA REGRA Se uma regra activada é selecionada para ser disparada, então: Identifica-se a lista de substituições possíveis. Selecciona-se uma das substituições Depois de aplicada a devida substituição, o lado direito da regra é inserido na memória de trabalho do sistema. Exemplo: a Regra R1: (a ?x c) (b) => (d ?x) , com a substituição ((?x b)) leva a que seja inserida na memória de trabalho do sistema pericial o facto (d b). Inteligência Artificial © Joaquim Filipe  38 COMPLEXIDADE DO PROCESSO DE INFERÊNCIA Admitindo R regras, P padrões por regra (em média) e F factos, a complexidade computacional seria de O(RFP) Exemplo: Possibilidades de combinação: 9=32 f1, f1 f2, f1 f3, f1 Regra r1 Factos: f1, f2 f2, f2 f3, f2 Padrões: p1, p2 f1, f2, f3 f1, f3 f2, f3 f3, f3 BC estável => maioria dos testes seriam repetidos. Ineficiência elevada Inteligência Artificial © Joaquim Filipe  39 PRINCIPAIS CONCEITOS A RETER Raciocínio: encadeamento de regras 2 modos, ambos dedutivos: para a frente (baseado em factos) e para trás (baseado em objetivos) A aplicação de uma regra implica O matching (emparelhamento) dos padrões da regra com os factos que constam na base de conhecimento: constantes emparelham com constantes iguais; variáveis emparelham com quaisquer constantes ou variáveis. Depois da ativação de todas as regras é preciso escolher (mediante um processo de resolução de conflitos) a que vai de facto ser aplicada (disparada) O processo é complexo, baseado num ciclo que se repete até não haver ativação de regras, em que o número de operações de comparação na fase de matching é da ordem de RFP Inteligência Artificial © Joaquim Filipe  40 EXEMPLO Base de conhecimento: Regras R1: pai(?x, ?y), pai(?y, ?z) => avô(?x, ?z) R2: pai(?x, ?y), irmão(?x, ?z) => tio(?z, ?y) Factos: F1: pai(Manuel, José) F2: pai(José, Ana) F3: irmão(Manuel, António) Raciocício dedutivo em encadeamento para a frente: F1,F2 + R1 → F4: avô(Manuel, Ana) F1,F3 + R2 → F5: tio(António, José) Inteligência Artificial © Joaquim Filipe  41 EXERCICIO Considere o contexto das relações familiares. 1. Escreva um conjunto de regras do tipo A➔B que permitam definir todas as relações familiares de que se lembre, por forma a permitir a inserção de um modelo das relações familiares na base de conhecimento de um sistema pericial. 2. Adicione factos à base de conhecimento para permitir que estes em conjunção com as regras anteriormente definidas possam ser usados pela máquina de inferência do sistema para deduzir, em modo encadeamento para a frente, que José é sobrinho de António. Inteligência Artificial © Joaquim Filipe Inteligência Artificial © Joaquim Filipe 42 EFICIÊNCIA DOS SISTEMAS DE PRODUÇÃO  43 ENQUADRAMENTO RETE ~ rede em Latim. Charles Forgy (1982) A ineficiência antes referida é aliviada através da manutenção em memória dos resultados dos testes anteriores. Shells: OPS5, ART, CLIPS, JESS, etc. Inteligência Artificial © Joaquim Filipe  44 JUSTIFICAÇÃO DA EFICIÊNCIA Explora 2 aspetos comuns nos sistemas baseados em regras: Redundância temporal: poucos factos criados por uma regra ser disparada; poucas regras afectadas por esses novos factos. Similaridade estrutural: mesmo padrão aparece no LHS de mais de uma regra. Inteligência Artificial © Joaquim Filipe  45 ESTRUTURA DE DADOS DE SUPORTE Grafo dirigido acíclico: Nós: representam padrões (excepto a raíz) Caminhos da raíz para as folhas representam padrões nos LHSs de regras. Em cada nó está a informação acerca dos factos satisfeitos pelos padrões. Inteligência Artificial © Joaquim Filipe  46 TIPOS DE NÓS NO RETE 3 tipos de nó: Nó raíz, Nó padrão (tipo 1) (alfa) e Nó junção (tipo 2) (beta). Nó raíz: tem como sucessores nós tipo 1 Cada padrão em cada regra dá origem a um nó alfa tipo 1. A memória alfa tem tantas colunas quantas as variáveis de um nó alfa. Os nós beta são construídos com base nos nós alfa e em outros nós beta, dando origem a uma memória beta. Inteligência Artificial © Joaquim Filipe  47 NÓS BETA A construção de nós beta segue a seguinte metodologia: Para cada regra Ri Bi,2 deriva de Ai,1 e Ai,2. Bi,j, para j>2, deriva de Bi,j-1 e Ai,j. Ai, Ai, Ai, 1 2 3 Bi,2 Bi,3 Inteligência Artificial © Joaquim Filipe Inteligência Artificial © Joaquim Filipe 48 RACIOCINIO INEXATO  49 LÓGICA SEM INCERTEZA Lógica Booleana 2 valores lógicos (falso e verdade / 0 e 1) Conectivas lógicas: ^(conjunção), v (disjunção) e ~ (negação). Regra de inferência: Modus Ponens ou Modus Tollens George Boole Cálculos Lógicos / Álgebras booleanas: (1815-1864) Proposicional ou de ordem zero Predicativo ou de primeira ordem Modal ou de ordem superior No entanto … no mundo real existe incerteza e portanto os valores lógicos verdade/falso não são em geral suficientes para criar boas teorias. Inteligência Artificial © Joaquim Filipe  50 FONTES DE INCERTEZA Incerteza em relação à validade do conhecimento contido na base de conhecimento, nomeadamente as regras de inferência. Exemplo: (?x cão) (?x ladra) => (?x não morde) Qual o grau de confiança? Incerteza em relação à validade dos dados introduzidos no sistema pericial. Exemplo: se o sistema perguntar (João velho)? A resposta poderá ser sim ou não mas com um grau de confiança dependente da idade do João. Inteligência Artificial © Joaquim Filipe  51 MODELAÇÃO DA INCERTEZA Incerteza subjetiva Lógica “Fuzzy” Raciocinio qualitativo Incerteza objetiva Probabilidades – lei de Bayes Inferência estatística para atualizar a confiança numa hipótese de cada vez que se faz uma observação Factores de confiança Simplificação da lei de Bayes, assumindo independência estatística Inteligência Artificial © Joaquim Filipe  52 LÓGICA FUZZY Esta abordagem permite tratar a incerteza associada quer às regras quer aos dados. Origem: Lotfi Zadeh, 1965. Ideia basilar: uma instância é um conceito se pertencer ao conjunto de todas as instâncias do mesmo. O conjunto é geralmente definido intensionalmente, usando uma função de pertença Booleana (0=não; 1=sim) Zadeh propõe a utilização de uma função de pertença com contradomínio no intervalo [0, 1]; 0=não; 1=sim; todos os restantes valores representam diferentes níveis de incerteza. Inteligência Artificial © Joaquim Filipe  53 HARD SETS VS. FUZZY SETS Hard Set Fuzzy set C1 C2 p2 p1 𝑝1 ∈ 𝐶1 ?... {0, 1} 𝑝2 ∈ 𝐶2 ?... [0, 1] Inteligência Artificial © Joaquim Filipe  54 EXEMPLO Conceito qualitativo: “Pessoa Alta” 1 0 1m10 1m60 1m90 2m30 O João tem 1.90.................... Valor lógico (fuzzy) = 0,86 Inteligência Artificial © Joaquim Filipe  55 COMBINAÇÃO DE VALORES LÓGICOS FUZZY NEGAÇÃO: Em lógica booleana: se A é verdade ~A é falso e vice-versa A ~A 0 1 1 0 Em lógica fuzzy se o valor fuzzy de uma premissa i é f(i) então a negação é dada por f(~i)=1-f(i) Inteligência Artificial © Joaquim Filipe  56 CONJUNÇÃO CONJUNÇÃO Em lógica booleana, a conjunção segue a seguinte tabela de verdade: P Q P^Q 0 0 0 0 1 0 1 0 0 1 1 1 Em lógica fuzzy, a conjunção tem como valor lógico o mínimo dos valores lógicos das proposições elementares. Inteligência Artificial © Joaquim Filipe  57 DISJUNÇÃO DISJUNÇÃO Em lógica booleana, a disjunção segue a seguinte tabela de verdade: P Q PvQ 0 0 0 0 1 1 1 0 1 1 1 1 Em lógica fuzzy, a conjunção tem como valor lógico o máximo dos valores lógicos das proposições elementares Inteligência Artificial © Joaquim Filipe  58 ABORDAGEM BAYESIANA Pretende-se identificar a melhor hipótese (i.e. a mais provável), dentre um conjunto H de hipóteses, que é justificada por um conjunto D de dados. h = arg max P(h | D) Thomas Bayes hH 1701-1761 Na interpretação Bayesiana “probabilidade” é uma medida do “grau de crença” (não necessariamente coincidente com a frequência relativa) O teorema de Bayes relaciona o grau de crença numa proposição antes e depois de uma observação. Inteligência Artificial © Joaquim Filipe  59 TEOREMA DE BAYES P(D): probabilidade a priori de ocorrência dos dados D (factos observados) P(h): probabilidade a priori de ocorrência da hipótese h (conclusão) (notar que P(h) é uma medida do nosso conhecimento do problema). P(D|h): probabilidade a priori de que, dada uma hipótese h, se observe o conjunto de dados D. Quer-se conhecer a probabilidade a posteriori P(h|D). P ( D | h) P ( h ) P(h | D) = P( D) O teorema de Bayes permite efetuar o cálculo da probabilidade a posteriori em termos das probabilidades a priori. Inteligência Artificial © Joaquim Filipe  60 FACTORES DE CONFIANÇA (CERTAINTY FACTORS) A utilização de fatores de confiança representa uma simplificação do método de Bayes, que só é válida se existir independência estatística entre as observações. Método da União A probabilidade de uma conclusão ser válida havendo possibilidade de a obter por uma de duas vias é dada pela probabilidade de ocorrência de um de dois eventos A ou B: P(A ou B) = P(A) + P(B) - P(A e B) Presume-se normalmente a independência estatística das diferentes contribuições. Portanto: P(A e B) = P(A). P(B). Logo: P(A ou B) = P(A) + P(B) - P(A). P(B) = P(A) + P(B). (1 – P(A)) Inteligência Artificial © Joaquim Filipe  61 FACTORES DE CONFIANÇA (CERTAINTY FACTORS) Método da União Este método permite ultrapassar o problema indicado para a lógica fuzzy. Considere-se duas regras, R1 e R2, que concluem o mesmo com diferentes graus de confiança: cf1=0.2; cf2=0.5. O factor de confiança na conclusão é: cf(conclusão) = cf1+ cf2- cf1. cf2 = cf1+ cf2 (1 - cf1) No exemplo presente cf(conclusão)=0.6. R1 cf(conclusão) = 0.2 + 0.5 (1 - 0.2) = 0.6 R2 Notar que o cf cresce incrementalmente, sem nunca atingir o valor 1. Presume-se a independência estatística das diferentes contribuições. Inteligência Artificial © Joaquim Filipe  62 MYCIN Cálculo do fator de confiança da conclusão de uma regra cf k = RI k (cf ).[ Rk (cf )] Em que: Rk(cf) é o fator de confiança da regra k RIk(cf) é o fator de confiança composto das premissas (inputs) da regra k Inteligência Artificial © Joaquim Filipe Inteligência Artificial © Joaquim Filipe 63 DESENVOLVIMENTO DE SISTEMAS PERICIAIS  64 ENGENHARIA DE SISTEMAS PERICIAIS Incerteza elevada ➔Ciclo de vida: espiral Feito à medida ROI exigido elevado Inteligência Artificial © Joaquim Filipe  65 ESCOLHA DO DOMÍNIO DE APLICAÇÃO Caracteristicas fundamentais: Utilização de conhecimento especializado Necessidade de abordagem não-convencional Disponibilidade de especialistas no domínio Elevada valorização da captura do conhecimento especializado Aceitável obtenção de sucesso limitado Tipo de tarefa: Requer principalmente raciocínio simbólico Requer utilização de heurísticas Envolve um leque de conhecimentos estreito e não senso comum Inteligência Artificial © Joaquim Filipe  66 PARTICIPANTES NO DESENVOLVIMENTO Especialista: Fornece conhecimento teórico e empírico do domínio Critica o sistema pericial à medida que se desenvolve Engenheiro do conhecimento Conhece as tecnologias de Sistemas Periciais Adquire, codifica e insere o conhecimento do especialista numa base de conhecimento Treina os utilizadores do sistema Utilizador Critica as funcionalidades e a usabilidade do sistema à medida que este se desenvolve Ajuda a compreender a aplicação do sistema em contexto real Inteligência Artificial © Joaquim Filipe AQUISIÇÃO DE CONHECIMENTO  68 INTRODUÇÃO A fase de aquisição de conhecimento é simultânea com a fase de representação de conhecimento. Frequentemente considerado o estrangulamento principal no processo de construção de sistemas periciais. Tipicamente necessária a interacção humana (semelhante ao que acontece com programação heurística e sistemas de suporte à decisão). Duas abordagens principais, em sistemas periciais baseados em regras: Aquisição directa dos especialistas do domínio Aquisição através de registos históricos, por indução de regras. Inteligência Artificial © Joaquim Filipe  69 AQUISIÇÃO ATRAVÉS DE UM ESPECIALISTA NO DOMÍNIO 4 razões porque a aquisição directa através do especialista no Domínio pode não resultar: Pode não haver um especialista no Domínio. Os alegados especialistas podem exibir um desempenho pobre a medíocre. Os especialistas podem não querer revelar os seus “segredos” profissionais. Os especialistas podem não ser capazes de articular o método de resolução de problemas que usam. Inteligência Artificial © Joaquim Filipe  70 O ENGENHEIRO DO CONHECIMENTO E O ESPECIALISTA Por vezes o engenheiro do conhecimento torna-se um especialista no domínio. Por exemplo: o XCON. J.McDermott usou alguns manuais de configuração do VAX para, com um esforço de cerca de 3 pessoas-mês produzir um protótipo com 250 regras. Argumento contra: tipicamente é necessário cerca de 10 anos para uma pessoa se tornar um especialista, mediante a aquisição de 50,000 a 100,000 heurísticas. Alternativamente pode usar-se o especialista como engenheiro do conhecimento: abordagem comum em pequenos sistemas periciais pessoais. Problemas: custo de formação e custo de oportunidade. Inteligência Artificial © Joaquim Filipe  71 INDUÇÃO DE REGRAS Alternativa a usar um especialista humano: converter uma base de dados existente num conjunto de regras de produção. A base de dados deve ter exemplos pertinentes ao problema em causa, cuja resolução foi considerada adequada (exemplos de boas decisões). A geração automática de regras (indução) permite geralmente produzir pelo menos um bom primeiro protótipo. Inteligência Artificial © Joaquim Filipe  72 EXEMPLO Para ilustrar a abordagem usa-se o problema da identificação de aeronaves, dentre um universo contendo apenas 4 tipos, para simplificar a compreensão do método. C130 C5A C141 B747 Inteligência Artificial © Joaquim Filipe  73 OBJECTOS, ATRIBUTOS E VALORES Cada objecto (dentre 4 classes) tem um conjunto de atributos, como por exemplo (no caso dos aviões): # motores, tipo (jacto, hélice,...), posição das asas (acima na fuselagem ou abaixo), forma das asas, forma da cauda, comprimento, tara, velocidade, altitude, etc. Depois de identificar um número de atributos é preciso filtrar os que são importantes para suportar o processo de resolução do problema. Usar muitos atributos conduz a espaços de elevada dimensionalidade (maldição da dimensionalidade “curse of dimensionality”) Problema da esparsidade dos dados num espaço de elevada dimensionalidade reduz a significância estatistica. Inteligência Artificial © Joaquim Filipe  74 ÁRVORES DE DECISÃO Nó: representa uma questão acerca do valor de um atributo ou uma conclusão. Ramo: representa um dos valores possíveis para o atributo associado ao nó que o origina. Tipo do avião Atributo C130 C141 C5A B747 Tipo motor Hélice Jacto Jacto Jacto Posição das asas Alta Alta Alta Baixa Forma das asas Convenc. Em V Em V Em V Cauda Convenc. Em T Em T Convenc. Protuberâncias na fusel. Sob asas Atr. Asas Nenhuma Atr. cockpit Inteligência Artificial © Joaquim Filipe  75 ÁRVORE DE DECISÃO PARA A IDENTIFICAÇÃO DE Tipo motor AVIÕES Jacto Hélice Forma asas Convenc. Em V C130 ?? Posição asas Alta Baixa B747 Forma cauda Convenc. Em T ?? Protuberâncias Nenhuma. Atr. asas C5A C141 ?? ?? Inteligência Artificial © Joaquim Filipe  76 UMA ÁRVORE DE DECISÃO MELHOR Reordenando os nós e eliminado ramos que conduzem a conclusões impossíveis (desconhecidas) podemos chegar a uma árvore de decisão simplificada e mais eficaz. Tipo motor Jacto Hélice Posição asas Alta Baixa C130 Protuberâncias B747 Atr. asas Nenhuma. C141 C5A Inteligência Artificial © Joaquim Filipe  77 CONVERTER ÁRVORES DE DECISÃO EM REGRAS A árvore de decisão anterior não tem nós intermédios. Este aspecto é um pre-requisito para a seguinte abordagem: Definição: uma cadeia é definida como sendo o caminho de um nó para outro em que se atravessa os ramos numa única direcção. 1. Identificar um nó conclusão ainda não tratado. 2. Percorrer a cadeia desde a conclusão até à raíz da árvore. 3. Na cadeia, os nós em círculos são nós THEN (conclusões) enquanto as caixas são nós IF (premissas). 4. Construir o conjunto de regras de produção para a cadeia em causa e repetir este processo para cada nó conclusão. Inteligência Artificial © Joaquim Filipe  78 EXEMPLO (regra 1 (regra 3 (tipo-motor hélice) (tipo-motor jacto) => (posicao-asas alta) (protuberancias nenhuma) (tipo-aviao C130)) => (tipo-aviao C5A)) (regra 2 (regra 4 (tipo-motor jacto) (tipo-motor jacto) (posicao-asas baixa) (posicao-asas alta) => (protuberancias atras-asa) (tipo aviao B747)) => (tipo aviao C141)) Inteligência Artificial © Joaquim Filipe  79 A ÁRVORE MÍNIMA Contudo era possível simplificar ainda mais a árvore de decisão, mediante a análise de um único atributo: as protuberâncias. (convida-se o leitor a definir a árvore de decisão e o correspondente conjunto de regras) A ordem em que se escolhe os nós determina a geração de árvores de decisão diferentes e de conjuntos de regras diferentes. Em vez de um processo ad-hoc existem abordagens sistemáticas. Por exemplo: o algoritmo ID3 (Quinlan, 1983). Inteligência Artificial © Joaquim Filipe  80 O ALGORITMO ID3 Algoritmo para a geração sistemática de árvores de decisão mínimas e geração do correspondente conjunto de regras de produção. Baseado na noção de minimização da entropia informacional. John Ross Quinlan 1983 Existem programas comerciais que implementam este algoritmo, ou variantes. Inteligência Artificial © Joaquim Filipe  81 QUANTIFICAÇÃO DA INFORMAÇÃO USANDO ENTROPIA “Informação” pode ser vista como uma contribuição para a redução da incerteza. Em Teoria da Informação é vulgar usar-se a entropia como medida da incerteza, i.e. do inverso da quantidade de informação. Exemplo: Considere-se o problema de adivinhar uma palavra em Português com base no conhecimento da sua primeira letra. Qual a quantidade exata de informação que se obtém quando se fornece a informação de que a palavra começa pela letra A? Será maior ou menor do que se fornecer a informação de que a palavra começa pela letra Z? Inteligência Artificial © Joaquim Filipe  82 ENTROPIA E MICROESTADOS Quanto maior o número disponível de possibilidades (microestados de um sistema) maior a sua entropia. Exemplo: Considere uma caixa quadrada com 100 bolas (50 brancas e 50 pretas). Quantas possibilidades há de arrumar todas as bolas brancas num retângulo de um lado e todas as bolas pretas do outro? 4 E quantas são as possibilidades de arrumação aleatória? Combinações n p a p = 100! / (50! X 50!) = 1029 Qual a probabilidade de estar num estado “arrumado”? Pode-se reduzir a entropia de um sistema fornecendo energia (sistema físico) organizando-o, ou fornecendo informação (sistema simbólico), i.e. organizando-o! Reduz-se em qualquer caso o número de microestados possíveis. Inteligência Artificial © Joaquim Filipe  83 ENTROPIA E EQUILÍBRIO TERMODINÂMICO: LEI DE BOLTZMANN A partir de um estado inicial um sistema tende para estados com maior número de microestados, i.e. mais prováveis, até que atinge o estado de máxima probabilidade, ou seja o estado do equilíbrio térmico. Aplicando esta conclusão à segunda lei da termodinâmica, a grandeza a que costumamos chamar entropia pode ser identificada com a probabilidade do estado em questão. Este resultado central na obra de Boltzmann habitualmente é representado pela equação seguinte: S = k log(W) S representa a entropia, k a constante de Boltzmann, W a "probabilidade termodinâmica" e log o logaritmo natural. A denominação "probabilidade", neste contexto, é enganadora. Ela representa aqui o número de microestados, caraterizados por lugar e impulso de todas as partículas, que correspondem a um estado do sistema abrangente, ou seja, o macroestado, no caso de um gás caraterizado por pressão, volume e temperatura. Inteligência Artificial © Joaquim Filipe  84 REPRESENTAÇÃO LOGARÍTMICA DA ENTROPIA A entropia de um estado ou evento elementares deverá ser tanto menor quanto mais a probabilidade de ocorrência (p) se aproxima de 0 ou de 1, sendo máxima quando a probabilidade é 0.5, caso em que: H=-log(2-1)=log(2) H = -[p.log(p) + (1-p).log(1-p)] H 0 1 p Pode-se usar o log2 (base 2) ou outra qualquer base do logaritmo. Notar que log2(1)=0 e que log2(0