Inteligência Artificial PDF

Inteligência Artificial 1 - Introdução O que é a Inteligência Artificial Existem muitas definições de Inteligência. São aspetos a considerar como definição de inteligência a capacidade de resolver problemas, a capacidade de usar o conhecimento, ou seja, raciocinar e capacidade de aprender. A Int...

Inteligência Artificial 1 - Introdução O que é a Inteligência Artificial Existem muitas definições de Inteligência. São aspetos a considerar como definição de inteligência a capacidade de resolver problemas, a capacidade de usar o conhecimento, ou seja, raciocinar e capacidade de aprender. A Inteligência Artificial não tem uma definição globalmente aceite, no entanto pode ser vista como o estudo de como fazer os computadores realizarem tarefas em que de momento as pessoas são melhores. Os problemas iniciais para a Inteligência Artificial foram: Jogos como Xadrez ou Damas Demonstração de Teoremas Linguagem Natural Atualmente é possível a resolução de problemas logísticos, exploração de dados e diagnóstico médico através da Inteligência Artificial. Até mesmo em jogos como o Xadrez a Inteligência Artificial ganhou ao campeão mundial. Redes Neuronais É um sistema de decisão inspirado em sistemas biológicos, programados por exemplos e com aprendizagem automática supervisionada e incremental baseada em reforço. Redes neuronais são aplicadas em: Reconhecimento de padrões Robótica e Controlo Processamento de dados e extração de informação Processamento da linguagem natural Âmbito da Inteligência Artificial A inteligência artificial permite então dar resposta a problemas com características que os tornam muito difíceis de ser resolvidos métodos convencionais como formulas matemáticas ou algoritmos. No entanto existem dois problemas principais com os quais a inteligência artificial tem de lidar: A incapacidade de usar modelos da realidade → Usar modelos mentais da forma como os especialistas resolvem os problemas. Explosão combinatória → Usar conhecimento para reduzir o espaço de procura (Heurísticas) 1 Inteligência Artificial e Conhecimento A Inteligência Artificial requer a utilização de conhecimento. Este conhecimento que lhe é dado pode ser volumoso, difícil de caracterizar com precisão e está em constante mutação. Este também é a base para o principal tipo de aplicação comercial: O Sistema Pericial. O conhecimento a induzir na Inteligência Artificial deve ser representado de forma a: Permitir representar regras gerais Ser compreendido pelas pessoas que o fornecem ao sistema Ser facilmente modificável Este conhecimento pode ser impreciso ou incompleto e pode ser usado para superar o seu próprio volume. Avaliação de uma Inteligência Artificial – Teste de Turing No teste de Turing existem 2 canais de comunicação idênticos e independentes (1 pessoa e uma máquina). Se ao fim de um período de interação razoável não for possível distinguir a pessoa da máquina, então a máquina é considerada inteligente. Atualmente a Inteligência Artificial está mais interessada em fazer máquinas que ajudem as pessoas a resolver problemas, de forma colaborativa, tirando o melhor partido das capacidades de memoria e rapidez de calculo das máquinas e das capacidades das pessoas (criatividade e tratamento de exceções). Assim, a Inteligência Artificial de hoje em dia não seria avaliável através do teste de Turing, pois está mais interessada na colaboração Humano-Máquina utilizando as capacidades dos dois ao máximo do que fazer com que as máquinas imitem seres humanos. Resolução de Problemas A resolução de problemas em Inteligência Artificial é baseada na utilização de conhecimento como forma de reduzir a explosão combinatória que resulta da exploração de todos os caminhos possíveis para a solução. Heurísticas Para resolver o problema da explosão combinatória, a Inteligência Artificial recorre à utilização de heurísticas. O conhecimento heurístico é: De natureza não científica Incerto Baseado na experiência passada Este visa sacrificar a solução ótima em benefício da garantia de encontrar uma solução satisfatória ainda que não seja a melhor. 2 2 – Procura em Espaço de Estados Espaço de Estados Uma forma simples de resolver problemas que não se podem resolver com formulas ou algoritmos, consiste em explorar o espaço de possibilidades tentando vários caminhos possíveis até encontrar a solução. Neste caso um problema terá de ser equacionado em termos de: Estados e Operadores. Terá ainda de ser definido o estado final. Representação Grafo – O Espaço de Estados pode ser representado por um grafo dirigido acíclico Nó – Cada nó do grafo representa um estado do problema, com alguma informação adicional: Ponteiro para o nó que o gerou / Heurística / Pontuação / Outros tipos de informação relevante Arco – Cada arco do grafo representa uma transição de estado ao longo do processo de resolução do problema. Estratégias de Exploração de Arvores Conceitos Nó inicial Sucessores de um nó: Nós gerados pela aplicação dos operadores lógicos Expansão de um nó: Geração de todos os sucessores Ponteiro para o nó pai: Permite obter a solução a partir do estado final Lista de nós abertos: Lista com os nós que ainda não foram explorados Lista de nós fechados: Lista com os nós que já foram expandidos Métodos de Procura – Breadth-First Neste método assume-se que o nó inicial não é um nó objetivo. Este método encontra sempre a solução que corresponde ao caminho mais curto e caso não haja solução termina com falha caso o grafo seja finito ou não termina caso o grafo seja infinito 1. Nó inicial → Abertos 2. Se Abertos estão vazios, falha 3. Remove o primeiro nó de ABERTOS (nó n) e coloca-o em FECHADOS 4. Expande o nó n. Coloca os sucessores no fim de ABERTOS e os ponteiros para n 5. Se algum sucessor for um nó objetivo sai e dá a solução. Caso contrário vai para 2 3 Métodos de Procura – Custo Uniforme Variante do Breadth-First que se interessa em minimizar o custo em vez da distância caso os custos associados aos arcos forem diferentes de arco para arco. Este algoritmo garante a minimização do custo. 1. Nó inicial → ABERTOS. Faz g(s) = 0 2. Se ABERTOS vazio, falha 3. Remove o nó de ABERTOS (n) com menor custo (g) e coloca-o em FECHADOS 4. Se (n) for um nó objetivo termina e dá a solução 5. Expande o nó n. Coloca os sucessores em ABERTOS, colocando ponteiros para (n) e calculando o g de cada um dos sucessores 6. Vai para 2. Métodos de Procura – Depth-First Neste método convenciona-se que a profundidade do nó raiz é zero e é definido um nível de profundidade máximo, a partir do qual os eles não se expandem. Quando são gerados nós sucessores que já estão em ABERTOS ou FECHADOS pode ser necessário recalcular a profundidade dos nós correspondentes. 1. Nó inicial → ABERTOS 2. Se ABERTOS vazia, falha 3. Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS 4. Se a profundidade de (n) é maior que o nível de profundidade máximo volta para 2 5. Expande o nó n. Coloca os sucessores no início de ABERTOS, com ponteiros para n 6. Se algum dos sucessores é um nó objetivo sai e dá a solução. Caso contrário volta para 2. Grafos em vez de Arvores Se o espaço de estados for um grafo, é preciso modificar os algoritmos estudados. Breadth-First o Reconhecer se um estado sucessor já está em ABERTOS ou em FECHADOS, e nesse caso não colocar o nó correspondente em ABERTOS Custo Uniforme o Se o sucessor de n está em ABERTOS ▪ Este sucessor não é adicionado se g (sucessor de n) > g (sucessor em ABERTOS) ▪ Caso contrário o sucessor de n substitui o que se encontra em ABERTOS o Se o sucessor está em fechados ignora-se o sucessor de n Depth-First o Se está em ABERTOS um nó com o mesmo estado, quer dizer que esse nó tem um custo g menor ou igual ao do nó gerado agora. Abandona o nó gerado o Se está em FECHADOS e tem um custo maior ou igual, elimina o nó antigo e coloca o nó gerado em ABERTOS, e coloca ponteiros nos sucessores do nó antigo para o nó gerado o Caso contrário, abandona o nó gerado. 4 Métodos Heurísticos ou “Informados” Para combater o facto de que todos os métodos estudados até este ponto não resolvem o problema da explosão combinatória fazendo uma procura exaustiva, sendo assim considerados métodos cegos ou não informados é necessário utilizar alternativas mais “inteligentes”. A alternativa é a utilização de Métodos Heurísticos. Estes métodos aproveitam-se do facto de por vezes ser possível utilizar regras empíricas para acelerar a procura. A ideia central é evitar considerar todas as alternativas, focando apenas nas que têm mais interesse. O interesse de um nó é calculado através de funções de avaliação. As regras utilizadas em cada problema são especificas para esse mesmo problema e podem nem resultar. Uso de Funções de Avaliação Como foi dito anteriormente é utilizada uma função de avaliação para determinar o interesse dos nós f(n). Por convenção a lista de nós ABERTOS é ordenada por ordem crescente de f(n), em que f(n) é o valor da função de avaliação aplicada ao nó. Um algoritmo que use esta convenção para realizar procura em espaço de estados cuja estrutura seja do tipo “Grafo Acíclico”, consiste na seguinte sequencia de passos: 1. Nó inicial → ABERTOS. Faz f(s) = 0 2. Se ABERTOS vazia, falha 3. Remove o nó de ABERTOS (n) com menor custo (f) e coloca-o em FECHADOS 4. Expande o nó (n) e calcula o (f) de cada um dos seus sucessores 5. Colocar os sucessores que ainda não existem em ABERTOS nem FECHADOS em ABERTOS, por ordem de f colocando também os ponteiros para n 6. Se algum sucessor for um nó objetivo termina e dá a solução. 7. Associa aos sucessores já em ABERTOS ou FECHADOS o menor dos valores de f (existente ou agora calculado). Coloca em ABERTOS os sucessores que estavam em FECHADOS cujos valores de f baixaram. Redireciona para (n) os ponteiros de todos os nós cujos valor de f baixaram. 8. Vai para 2. Algoritmo A* O algoritmo anterior não especifica o tipo de função de avaliação. Se esta consistir em f(n) = g(n) + h(n), em que g(n) é o custo do nó e h(n) é o seu valor heurístico designa-se essa família de algoritmos por A. Se se modificar o algoritmo de procura ordenada por forma a que o teste de estado objetivo seja feito sobre o nó (n) que é selecionado depois de colocar todos os sucessores em ABERTOS, tem-se o algoritmo A* 5 Admissibilidade Um algoritmo diz-se admissível se, para qualquer grafo, descobre sempre o caminho ótimo para o objetivo desde que esse caminho exista. Se h’ é um limite inferior de h então o algoritmo é admissível. A admissibilidade implica que: Quando o A* expande um nó (n) já encontrou um caminho ótimo para (n) Quando o A* expande um nó (n) a função de avaliação f’ não é maior que o custo real f. Informação Heurística Usar h’(n) = 0 reflete a ausência total de conhecimento acerca do domínio de aplicação pelo que embora o algoritmo seja admissível é pouco prático. Um algoritmo A é mais informado do que um algoritmo B se e só se h(A) > h(B) para todos os estados exceto os estados objetivo. Consistência Pode demonstrar-se que se a heurística for consistente o A* nunca expande mais nós do que um algoritmo A com informação heurística menor ou igual. Uma heurística é consistente se h’(m) – h’(n) = h’(n0) ) 4. Só se expandem nós com f’(n) beta de qualquer um dos seus antecessores MIN (corte beta) o Neste caso, o valor retornado pelo nó MAX pode ser o seu valor alfa corrente 11 Algoritmo MINIMAX com cortes Alfa-Beta Como a procura alfabeta é do tipo DFS, então apenas é necessário em cada instante considerar os nos ao longo de um ramo da arvore de procura. Sendo alfa o valor da melhor escolha encontrada até ao momento, ao longo do ramo corrente para MAX e beta o valor da melhor escolha encontrada até ao momento, ao longo do ramo corrente para MIN, o Alfa-Beta atualiza o valor de alfa e de beta ao longo da procura e corta uma subárvore (terminando uma chamada recursiva) logo que se sabe ser pior que os valores correntes de alfa e beta. Fail-Soft – Versão do Alfa-Beta permite que sejam devolvidos valores fora do intervalo [α, β] Fail-hard – Versão do Alfa-Beta na qual o valor devolvido é limitado ao intervalo [α, β] definido em parâmetros, ou seja, no caso de haver um sucessor que de origem a um corte (valor fora desse intervalo) o valor devolvido é o valor limite do intervalo. Ao utilizar cortes Alfa-Beta no algoritmo MINIMAX, assumindo que seria possível obter um estimativa da ordenação do valor dos sucessores, o Alfa-Beta apenas necessitaria de examinar O(fator de ramificaçãoprofundidade/2) nós folha para escolher o melhor lance, significando assim que o fator de ramificação efetivo é a raiz quadrada do fator de ramificação. Assim o MINIMAX com cortes Alfa-Beta consegue examinar mais níveis do que o MINIMAX no mesmo tempo, o que o torna mais eficiente Numa situação real não é possível obter a ordenação, no entanto demonstra-se que, em média, o Alfa-Beta avaliaria um número de nós na ordem de O(b3d/4) o que permite aumentar a profundidade de pesquisa em cerca de 4/3. A ordem pode ser estimada com base na função de avaliação estatística, o que faz com que a eficácia deste algoritmo dependa da heurística. Tabelas de Transposição (Hash Tables) Em certos jogos de informação perfeita, é possível chegar a um estado de mais do que uma maneira (transposições). Logo a procura pode ser acelerada através do uso de Hash Tables, que são consultadas de cada vez que se gera um novo estado, constituindo uma espécie de cache. Quando há um hit, não se poupa apenas a avaliação da posição, mas sim a de toda a subárvore abaixo da mesma. Quanto maior for o hit rate, maior o ganho de eficiência. Programação Dinâmica e Memoizacão A programação dinâmica é um método para resolver problemas complexos em que se divide um problema em problemas mais simples que ocorrem várias vezes e se guardam as soluções destes para que a resolução só seja efetuada 1 vez. Esta abordagem de guardar em memoria as soluções dos subproblemas designa-se Memoizacão. Todos os programas que jogam jogos de informação perfeita, caracterizados por explosão combinatória utilizam tabelas de Memoizacão. Limitação da Árvore de Procura Existem dois métodos de limitação da Árvore de Procura 1. Utilizar um limite de profundidade fixo (d) 2. Usar o Iterative Deepening 12 Estes métodos podem ter resultados desastrosos, pois pode haver uma variação brusca no valor da função de avaliação no nível seguinte a d gerando assim o problema do Efeito de Horizonte. Este problema é um dos mais difíceis de eliminar, pois o valor de uma posição pode aparentar ser estável durante muitas jogadas, não o sendo de facto. Procura quiescente – Para evitar este problema, a função de avaliação só é aplicada a posições com baixa probabilidade de terem variações bruscas no valor da função de avaliação. As posições não-quiescentes podem ser expandidas até atingirem posições quiescentes. Outros algoritmos Existem outros algoritmos com o mesmo objetivo do algoritmo MINIMAX: SSS*– Realiza uma procura do tipo A* em vez de DFS (Este algoritmo foi declarado impraticável) DUAL*– Similar ao SSS*, mas invertendo as operações SCOUT – Ao analisar um nó MAX admite-se que ele deverá ter um valor mínimo admissível e por isso verifica-se se cada sucessor desse nó poderá devolver um valor maior do que o mínimo. Se não devolver não há necessidade de analisar esse sucessor, se devolver existe a necessidade de analisar o sucessor. Para os nós MIN faz-se o simétrico PVS / NEGASCOUT – Algoritmo SCOUT com a logica do NEGAMAX em vez de MINIMAX MTD(F) – Usa uma função de teste que realiza procuras Alfa-Beta com janelas nulas. Uma janela nula causa mais cortes, mas devolve menos informação. Para encontrar o valor MINIMAX, este algoritmo chama o Alfa-Beta várias vezes, convergindo para o valor exato. BNS – É uma evolução do algoritmo MTD(F), que indica qual a jogada ideal do ponto de vista do MINIMAX, mas não indica o seu valor. Determina qual a subárvore em que o MINIMAX é maior ou menor que um dado valor (adivinhado), mudando este valor até que o alfa e o beta estão suficientemente próximos ou apenas uma subárvore é maior que o valor adivinhado. 4 – Sistemas Periciais Sistemas periciais são aplicações que têm por objetivo resolver problemas complexos de forma idêntica à utilizada por peritos humanos. Estes existem como sistemas de apoio à decisão e resolução de problemas complexos sem solução algorítmica através do uso de heurísticas (conhecimento humano). Modelos Existem problemas para os quais não existe uma solução algorítmica conhecida. Nesses casos a informática convencional tem um problema, sendo necessário recorrer a técnicas de Inteligência Artificial. O problema é que a realidade é demasiado complexa, sendo assim necessário usar modelos para interagir com a realidade e resolver estes problemas. Um modelo é uma simplificação da realidade 13 Teorias Uma teoria é um modelo internamente consistente em termos sintáticos, ou seja, não contem contradições. Uma boa teoria deve ser um modelo semanticamente consistente. Uma boa teoria deverá ter poder descritivo e prescritivo e por isso ajudar a compreender a realidade (poder descritivo) e a resolver problemas (poder prescritivo). Resolução de Problemas Existe um dilema sobre a abordagem à resolução de problemas. Caso se queira modelar a realidade devem de ser aplicados conhecimento teórico rigoroso e algoritmos que ofereçam soluções rigorosas. Caso se pretenda modelar a forma como a pessoa vê a realidade deve-se usar conhecimento empírico e aplicar heurísticas. Métodos de Modulação de Sistemas Periciais Direto (Como é a realidade) o Modelo Formal (Matemático) da Realidade o Programa Convencional: Algorítmico Indireto (Como a pessoa vê a realidade) o Modelo Informal (Humano) da Realidade ▪ Dado por um especialista – É conhecimento simbólico como: Factos, Regras e Raciocínio Logico o Sistema Pericial: Não Algorítmico Arquitetura de um Sistema Pericial Base de Conhecimento – A base de conhecimento contém os modelos de domínio (Factos e Regras) dados pelo especialista / operador e os dados associados ao problema. Esta é dependente do domínio, tendo hipótese do “mundo fechado” pois todos os dados que são necessário saber já lhe foram concedidos. Possui uma natureza essencialmente declarativa. Máquina de Inferência – Contém os mecanismos lógicos de raciocínio, é independente do domínio e tem natureza essencialmente procedimental Interface Inteligente – A interface inteligente é a camada de interação entre o sistema pericial e os utilizadores. Deve permitir aos utilizadores inserir informações, receber resultados e interagir de forma eficiente com o sistema Aprendizagem – O modulo de aprendizagem refere-se à capacidade do sistema pericial de adquirir conhecimento ao longo do tempo. Isto pode envolver a atualização da base de conhecimentos com novos dados, a adaptação das regras de inferência com base em experiências passadas e a melhoria continua do desempenho do sistema. Explicação – 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. Esta capacidade de explicação é essencial para que os usuários compreendam e confiem nas decisões tomadas pelo sistema pericial. Shells As Shells são ferramentas de desenvolvimento de sistemas periciais análogas às ferramentas CASE e aplicáveis a qualquer domínio. Estas permitem a reutilização da máquina de inferência dado que esta é de natureza sintática e 14 independente do domínio de aplicação. As Shells exigem a construção da base de conhecimento sendo esta de natureza semântica e dependente do domínio de aplicação. Existem varias Shells como por exemplo. JESS - Java Expert System Shell CLIPS - C Language Integrated Production System EXSYS - C Language Integrated Production System Raciocínio Logico Em Sistema Periciais Tipos de Raciocínio Raciocínio Dedutivo o Usando o silogismo logico. Exemplos: ▪ Esta a chover então há nuvens no céu ▪ Não há nuvens no céu então não esta a chover o Os resultados são garantidamente validos ▪ Análogo às relações entre conjuntos (A contém B) Raciocínio Indutivo o Usando formas de generalização / extrapolação o Resultados não são garantidamente validos Raciocínio Abdutivo o Usando as observações para procurar uma explicação provável ▪ Frequentemente usado em medicina o Resultados não são garantidamente validos Tipos de Logicas Proposicional ou de Ordem Zero – Conjunto de expresses sintáticas (formulas bem formadas, ou fbfs) atómicas. 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) Modal ou de ordem superior – fbfs incluem predicados de ordem superior Predicado de Ordem Superior: Este predicado 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. 15 Encadeamento para a Frente e para Trás (Raciocínio dedutivo) O raciocínio dedutivo pode encadear regras de dois modos: Modo Dirigido por Dados o Encadeamento para a frente Modo Dirigido por Objetivos o Encadeamento para trás o Começa por se colocar uma hipótese, a qual se tenta demonstrar com dados-base. Sistemas de Produção São sistemas computacionais baseados em regras de comportamento (de produção). Cada regra de produção tem duas partes: o IF (precondição sensorial ou premissa) e o THEN (Acão ou conclusão). Se uma precondição satisfaz (matching) o estado correte do mundo, então a Acão é disparada (fired). A precondição é também designada por “Lado esquerdo” (LHS) e a Acão por “Lado Direito” (RHS). O processo de inferência tem memoria permanente ou memoria de longo prazo em modelos de domínio e memoria de trabalho ou memoria de curto prazo em modelos de caso. Ciclo de encadeamento para a frente: 1. Matching (Emparelhar) a. O emparelhamento é feito elemento a elemento, por ordem: i. Constante ~ Constante ii. Variável ~ Variável ou Constante (mediante substituição adequada). b. O resultado do emparelhamento de um padrão com um facto é uma substituição de variáveis. 2. Ativação de Regras a. Se o lado esquerdo emparelhar com um ou mais factos na base de conhecimento então a regra é ativada. 3. Resolução de Conflitos a. Um conflito surge quando várias regras podem ser ativadas simultaneamente. Nesse caso é preciso escolher uma regra a disparar. A escolha é determinada por critérios heurísticos. 4. Fired (Disparar uma regra) a. Se uma regra ativada é selecionada para ser disparada então: i. identifica-se a lista de substituições possíveis ii. Seleciona-se uma das substituições iii. Depois de aplicada a devida substituição, o lado direito da regra é inserido na memoria de trabalho do sistema. 16 Eficiência dos Sistemas de Produção A ineficiência dos sistemas de produção é aliviada através da manutenção em memoria dos resultados dos testes anteriores. A eficiência dos Sistemas de Produção pode ser justificada pelo facto destes sistemas explorarem dois aspetos comuns nos sistemas baseados em regras: Redundância Temporal o Poucos factos criados por uma regra ser disparada. o Poucas regras afetadas por esses novos factos Similaridade estrutural o Mesmo padrão aparece no LHS de mais de uma regra. Estrutura de Dados de Suporte Os dados de suporte encontram-se num grafo dirigido acíclico em que: Nós representam padrões Caminhos da raiz para as folhas representam padrões nos LHSs de regras Em cada nó está a informação acerca dos factos satisfeitos pelos padrões Existem 3 tipos de nós no RETE Nó Raiz o Tem como sucessores nos do tipo 1 ▪ Cada Padrão em cada regra dá origem a um nó alfa (tipo 1) ▪ A memoria alfa tem tantas colunas quantas as variáveis de um nó alfa Nó Padrão (Tipo 1) (alfa) Nó Junção (Tipo 2) (beta) o São construídos com base nos nós alfa e em outros nós beta, dando origem a uma memoria beta o 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 17 Raciocínio Inexato Logica Sem Incerteza São exemplos de logicas sem incerteza a Lógica booleana (em que existe apenas 2 valores lógicos e conectivas lógicas como a conjunção a disjunção e a negação seguindo regras de inferência) e Cálculos Lógicos / Álgebras booleanas (Podem ser proposicionais, predicativos ou modal). Fontes de Incerteza No mundo real existe incerteza e, portanto, os valores lógicos verdade/falso não são, em geral, suficientes para criar boas teorias. A incerteza pode ser em relação à validade do conhecimento contido na base de conhecimento, nomeadamente as regras de inferência, ou então pode ser em relação à validade dos dados introduzidos no sistema pericial. Modelação da Incerteza A incerteza pode ser subjetiva ou objetiva. Incerteza Subjetiva: Utiliza-se a Logica de “Fuzzy” – Raciocínio qualitativo o Logica Fuzzy ▪ Negação Se o valor Fuzzy de uma premissa i é f(i) então a negação é dada por f(~i) = 1-f(i) ▪ Conjunção A conjunção tem como valor logico o mínimo dos valores lógicos das proposições elementares. ▪ Disjunção A disjunção tem como valor logico o máximo dos valores lógicos das proposições elementares. Incerteza Objetiva: Utilizam-se probabilidades (Lei de Bayes) inferindo estatística para atualizar a confiança numa hipótese de cada vez que se faz uma observação ou Fatores de Confiança que é um caso da simplificação da lei de Bayes onde se assume a independência estatística. o Na abordagem Bayesiana pretende-se identificar a melhor hipótese (a mais provável), dentro de um conjunto H de hipóteses que é justificada por um conjunto D de dados. Nesta interpretação “probabilidade” é uma medida do “grau de crença”. O Teorema de Bayes relaciona o “grau de crença” numa proposição antes e depois de uma observação. ▪ H = argmax P(h|D) 18 Teorema de Bayes O teorema de Bayes permite efetuar o cálculo da probabilidade à posteriori em termos das probabilidades à priori da seguinte forma: 𝑃(𝐷|ℎ)𝑃(ℎ) 𝑃(ℎ|𝐷) = 𝑃(𝐷) P(D): Probabilidade à priori de ocorrência dos dados D (factos observados) P(h): Probabilidade à priori de ocorrência da hipótese h (conclusão) P(D|h): Probabilidade à priori de que, dada uma hipótese h, se observe o conjunto de dados D. 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. A utilização de Fatores de Confiança faz-se através do uso do Método da União: Neste método a probabilidade de uma conclusão ser valida havendo possibilidade de a obter por uma de duas vias é dada pela probabilidade de ocorrência de um de dois eventos A ou B: o P(A ou B) = P(A) + P(B) – P(A e B) ▪ Sendo P(A e B) P(A)*P(B), pois são é presumido que estas sejam independentes. ▪ Logo P(A ou B) = P(A) + P(B) * (1 – P(A)) Este método permite ultrapassar o problema indicado para a lógica Fuzzy. Considerando duas regras com fatores de confiança 0.2 e 0.5 o fator de confiança na conclusão: o cf = 0.2 + 0.5 (1 – (0.2)) = 0.6 O cf cresce incrementalmente, sem nunca atingir o valor 1. MYCIN O cálculo do fator de confiança da conclusão de uma regra é calculado da seguinte forma: 𝑐𝑓𝑘 = 𝑅𝑖𝑘 (𝑐𝑓) ∗ [𝑅𝑘 (𝑐𝑓)] 𝑅𝑘 (cf) é o fator de confiança da regra k 𝑅𝑖𝑘 (cf) é o fator de confiança composto das premissas (inputs) da regra k Desenvolvimento de Sistemas Periciais 19 O sistema pericial está associado a uma elevada incerteza e é feito à medida, ou seja, é feito para atender a requisitos muito específicos, o que cria uma alta expectativa de retorno sobre o investimento na sua criação. O ciclo de vida do desenvolvimento de um Sistema Pericial segue uma abordagem espiral que é um modelo de desenvolvimento iterativo, no qual o processo é repetido em ciclos, permitindo o refinamento continuo do sistema com base no feedback obtido em cada iteração. Ao escolher o Domínio de Aplicação de um Sistema Pericial tem de se ter em conta as seguintes características 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 Os tipos de tarefas: Requerem principalmente raciocínio simbólico Requerem utilização de heurísticas Envolvem um leque de conhecimentos estreito e não senso comum Os participantes no desenvolvimento de um sistema pericial são: Especialista o Fornece conhecimento teórico e empírico do domínio o Critica o sistema pericial à medida que se desenvolve Engenheiro do Conhecimento o Conhece as tecnologias de Sistemas Periciais o Adquire, codifica e insere o conhecimento do especialista numa base de conhecimento o Treina os utilizadores do sistema Utilizador o Critica as funcionalidades e a usabilidade do sistema à medida de que este se desenvolve. o Ajuda a compreender a aplicação do sistema em contexto real Aquisição de Conhecimento A fase de aquisição de conhecimento é simultânea com a fase de representação de conhecimento. Esta fase é frequentemente considerada o estrangulamento principal no processo de construção de sistemas periciais. Nesta fase é tipicamente necessária a interação humana, de forma semelhante ao que acontece com a programação heurística e de sistemas de suporte à decisão. 20 Existem duas abordagens principais em Sistemas Periciais baseados em regras: Aquisição direta – Aquisição através de um especialista no domínio o Esta pode não resultar pois: ▪ 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. o Por vezes o engenheiro do conhecimento torna-se um especialista no domínio o Pode-se usar o especialista como engenheiro do conhecimento, o que é comum em pequenos sistemas periciais pessoais ▪ Isto traz problemas como custo de formação e custo de oportunidade. Aquisição através de registos históricos - Indução de Regras o Esta é uma alternativa a usar um especialista humano. Pela indução de regras converte-se uma base de dados existente num conjunto de regras de produção. Esta base de dados deve ter exemplos pertinente ao problema em causa, cuja resolução foi considerada adequada. o A geração automática de regras (indução) permite geralmente produzir pelo menos um bom primeiro protótipo. Arvores 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. Podem ser criadas arvores de decisão melhores a partir de uma arvore de decisão inicial reordenando os nós e eliminando ramos que conduzem a conclusões impossíveis (desconhecidas) tornando assim esta nova arvore mais simplificada e mais eficaz que a primeira. Conversão de Arvores de Decisão em Regras Para converter uma arvore de decisão em regras, a arvore não pode ter nós intermédios. Tendo em conta que uma cadeia é definida como sendo o caminho de um nó para outro em que se atravessa os ramos numa única direção, a conversão de uma arvore de decisão em regras faz-se seguindo os passos: 1. Identificar um nó conclusão ainda não tratado. 2. Percorrer a cadeia desde a conclusão até à raiz da arvore 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. 21 A Arvore Mínima É possível simplificar ainda mais uma arvore de decisão, mediante a analise de um único atributo. A ordem em que se escolhe os nós determina a geração de arvores de decisão diferentes e de conjuntos de regras diferentes. Em vez de um processo ad-hoc existem abordagens sistemáticas como: Algoritmo ID3 o Este é um algoritmo para a geração sistemática de arvores de decisão mínimas e geração do correspondente conjunto de regras de produção que é baseado na noção de minimização da entropia informacional. 22