Inteligência Artificial

Prévia do material em texto

Histórico e Conceitos da Inteligência
Artificial
O OBJETIVO É APRESENTAR SUCINTAMENTE OS CONCEITOS INICIAIS E O
HISTÓRICO DA DISCIPLINA INTELIGÊNCIA ARTIFICIAL.
AUTOR(A): PROF. LEANDRO ZERBINATTI
INTELIGêNCIA ARTIFICIAL
Segundo o dicionário Aurélio Inteligência pode assumir os seguintes
significados:
1 Conjunto de todas as faculdades intelectuais (memória, imaginação,
juízo, raciocínio, abstração e concepção).; 2 Qualidade de inteligente; 3
Compreensão fácil; 4 Pessoa muito inteligente e erudita; 5 Acordo,
conluio; 6 Harmonia; 7 Habilidade.
Já o termo Artificial pode assumir os significados de:
1 Que não é natural; 2 Dissimulado, fingido; 3 Postiço; 4 Factício.
Ainda pelo dicionário, Inteligência Artificial é o “ramo da informática que
estuda o desenvolvimento de sistemas computacionais com base no
conhecimento sobre a inteligência humana“.
Porém, a Inteligência Artificial é muito mais abrangente do que isso. A
Inteligência Artificial é uma disciplina que busca compreender e criar em
sistemas computacionais faculdades humanas que devem ser reconhecidas
como de Inteligência.
O termo Inteligência Artificial não é bem definido pois o termo
inteligência, por sí só, também não é bem definido, apesar de ter uma
ampla discussão na sociedade sobre o tema.
Segundo estudiosos da Inteligência Artificial ela pode ser definida de
diversas maneiras, na qual apresento duas:
- Modelagem da inteligência humana com o objetivo de descobrir como o
cérebro humano funciona;
- Construir máquinas inteligentes para auxiliar os humanos a executar
tarefas que sejam muito caros, ineficientes, morosos ou ainda muito
perigosos para ser executados por nós. (Harris, 1988)
Segundo Russell & Norvig [5], as definições de IA, encontradas na
literatura científica, podem ser agrupadas em quatro categorias
principais:
1 - sistemas que pensam como humanos;
2 - sistemas que agem como humanos;
3 - sistemas que pensam logicamente;
4 - sistemas que agem logicamente
O TESTE DE TURING
Para identificar precisamente o que seria Inteligência Artificial, Alan
Turing (1950) propôs um testes para determinar se uma máquina era
inteligente.
O Teste proposto por Allan Turing era que, por meio de um terminal
computacional, um ser humano deveria elaborar perguntas para dois
outros terminais. Em um deles estaria um ser humano e em outro uma
máquina. Se após um determinado tempo ele não fossse capaz de
identificar quem seria o ser humano e quem seria a máquina, estaria
provado que a máquina era provida de inteligência.
De acordo com Russel & Norvig, a tarefa de programação para passar
neste teste necessitaria de compatibilizar as seguintes propriedades:
- Processamento de Linguagem Natural;
- Representação do Conhecimento;
- Raciocínio Automatizado;
- Aprendizado de Máquina;
Legenda: O TESTE DE TURING
HISTóRICO DA INTELIGêNCIA ARTIFICIAL
(1943_1950) – No início das pesquisas da Inteligência Artificial, as
pesquisas estavam ligadas aos modelos dos neurônios artificiais que
possibilitaria o desenvolvimento de máquinas que fossem capazes de
aprender.
(1951-1969) – Na próxima fase os pesquisadores se concentraram em
soluções capazes de jogar xadrez, provar teoremas lógicos, emular o
raciocínio humano, comunicar através de linguagem natural, além de
analisar as estruturas moleculares para emular através de modelos
matemáticos computacionais.
(1970 – 1980) – Com os problemas de armazenamento de dados e
processamento, que são requisitos de Sistemas Complexos, muito do
entusiasmo inicial foi freado.]
(1981 – hoje) – Com a evolução do hardware, projetos de desenvolvimento
de inteligência artificial foram retomados com soluções utilizando
diversas técnicas.
Hoje grande parte dos mecanismos de busca na Internet e das redes
sociais é equipada com algoritmos de inteligência artificial.
ABORDAGENS DA INTELIGêNCIA ARTIFICIAL
Existem quatro principais abordagens da Inteligência Artificial:
- Conexionista – baseia-se na hipótese segundo um modelo
suficientemente preciso do cérebro humano é suficiente para reproduzir a
inteligência humana. Trata de problemas imprecisos, mas que podem ser
definidos (Ex: redes neurais artificiais)
- Simbólica – baseia-se no conjunto de estruturas simbólicas e um
conjunto de regras de manipulação das estruturas como suficientes para a
reprodução de inteligência. (Ex: sistemas especialistas)
- Evolucionária – baseia-se na teoria evolutiva de Charles Darwin onde
modelamos a evolução de uma população, a partir da evolução dos
indivíduos e seus genes, usando operações genéticas (Ex: Algoritmos
Genéticos)
- Estatístico / Probalilístico – baseia-se no conhecimento acumulado a
partir de experiências pré ocorridas, para inferir uma possibilidade de
solução futura. (Ex: Redes Bayesianas)
APLICAçõES DE INTELIGêNCIA ARTIFICIAL
Dentre inúmeras aplicações atuais da Inteligência Artificial, podemos
citar as seguintes:
- Jogos eletrônicos computacionais;
- Robótica (domiciliar e industrial);
- Otimização e Controle de Processos;
- Processamento de linguagem natural;
- Mineração de dados e textos;
- Aprendizagem de máquinas;
- Reconhecimento de Faces, voz, ambiente.
ATIVIDADE FINAL
Segundo o Teste de Turing, prova-se que um computador é inteligente
 se:
A. O interrogador não conseguir identificar se as respostas estão sendo
originadas aleatóriamente.
B. O interrogador não conseguir identificar se as respostas estão sendo
originadas pela máquina (computador) ou pelo humano.
C. Se os questionamentos estão sendo originados pela máquina (computador)
D. Se os questionamentos estão sendo originados pelo ser humano.
REFERÊNCIA
Rich, Elaine e Knight, kevin. 1993. Inteliência Artificial. São Paulo  : Makron
Books, 1995.
Russel, Stuart e Norvig, Peter. 2004. Inteligência Artificial. Rio de Janeiro  :
Elsevier, 2004.
Lógica Proposicional
ESSE TÓPICO TEM A FUNÇÃO DE DEMONSTRAR OS CONCEITOS
FUNDAMENTAIS DA LÓGICA PROPOSICIONAL, TAMBÉM CHAMADA DE
CÁLCULO PROPOSICIONAL.
AUTOR(A): PROF. LEANDRO ZERBINATTI
LóGICA PROPOSICIONAL
Todo o tempo, nós seres humanos podemos imaginar coisas. Nós ouvimos
palavras e frases dentro de nossas mentes. Nós visualizamos situações que
ainda não existem e podemos explorar imagens predizendo os efeitos de
possíveis ações. Muito da nossa capacidade humana vem da possibilidade
de manipularmos representações mentais de objetos, eventos e conceitos.
(Minsky 2006).
Com essa capacidade podemos utilizar alguns objetos físicos para
representar algum outro conhecimento, por exemplo, quando utilizamos
um mapa para nos guiar em uma cidade ou ainda quando utilizamos
palavras para descrever o caminho entre as ruas e os sentidos a percorrer
nesse mapa, ou ainda, identificamos características ao olhar e analisar
uma imagem de radiografia.Para responder questões sobre um evento
passado, nós usamos aquilo que chamamos de memória. A memória é um
registro realizado no momento de ocorrência de um evento prévio. Não é
possível armazenar o evento em si, nós somente podemos fazer registros
sobre alguns objetos, idéias e relações do evento. (Minsky 2006)
Nós utilizamos diferentes formas de pensar sobre o mesmo evento.
Utilizamos explicações verbais, manipulando diagramas mentais,
visualizando as expressões faciais e gestos das pessoas envolvidas.
Experiências práticas são importantes para consolidar essas várias formas
de informação que nos embasa a tomada de decisões. (Minsky 2006)
Nós seres humanos somos os únicos animais capazes de tratar idéias como
se fossem coisas, ou conceituar. (Minsky 2006)
Temos a capacidade de inventar novos conceitos e os colocamos em uso,
representamos novas idéias em formas estruturais que instalamos em
redes do nosso cérebro. Um pequeno fragmento de conhecimento não tem
sentido, a menos que faça parte de uma estrutura mais vasta e que tenha
ligações com outras partes de nossa rede de conhecimentos, não
importando a forma através da qual estes links estão conectados. (Minsky
2006)A linguagem é uma das formas mais naturais para formalmente
representar o conhecimento. Para isto utilizamos os símbolos alfa-
numéricos compondo palavras e sentenças de forma a expressar, de forma
livre, o conhecimento sobre determinada área de domínio.Um dos
componentes centrais de uma base de conhecimento é um conjunto de
sentenças, que são expressas em uma linguagem, chamada de linguagem
de representação do conhecimento e representa alguma asserção sobre o
mundo. (Russel e Norvig 2004)
Essas sentenças são expressas de acordo com a sintaxe da linguagem de
representação, a semântica da linguagem, que define o significado das
sentenças. Dentre algumas linguagens de representação de conhecimento
citamos a lógica proposicional. (Russel e Norvig 2004)
 
A lógica proposicional é um formalismo matemático através do qual podemos
abstrair a estrutura de um argumento, eliminado a ambiguidade existente na
linguagem natural.
Esse formalismo é composto por uma linguagem formal e por um conjunto de
regras de inferência que nos permitem analisar um argumento de forma precisa
e decidir a sua validade (Rich, 1995).
Informalmente, um argumento é uma sequência de premissas seguida de uma
conclusão.
Dizemos que um argumento é válido quando sua conclusão é uma consequência
necessária de suas premissas.
Como exemplo, veja o o argumento:
Sempre que o aluno estuda, ele é aprovado.
O aluno está estudando.
Logo, o aluno será aprovado.
É válido; pois sua conclusão é uma consequência necessária de suas premissas.
PROPOSIçãO
Uma Proposição é uma sentença declarativa afirmativa, da qual faça
sentido afirmar que seja verdadeira ou falsa.
Pelos princípios da não contradição e do terceiro excluído, uma
proposição tem um, e apenas um, valor lógico.
Exemplos:
“São Paulo está situada no Brasil” = Verdadeiro
“A Lua é quadrada” = Falso
SINTAXE DA LóGICA PROPOSICIONAL
Os símbolos usados na Lógica Proposicional são as constantes (V) -
verdadeiro ou (F) - falso, que são alocadas aos símbolos proposicionais.
As proposições são expressas através das letras minúsculas do alfabeto
latino.
Os conectivos lógicos também são alocadas a cada expressão Lógica que
se compõem de duas ou mais proposições.
Entre os conectivos lógicos temos:
(~) – Negação
(Ë¿) – E – Conjunção
(Ë¿) – OU – Disjunção
(→) – Se....Então – (Condicional)
(↔) – ...se e somente se... – (Bicondicional)
Dessa forma, podemos expressar a fórmula da seguinte forma:
- Se o semáforo está vermelho, então o carro deve parar.
 
- O semáforo está vermelho – p
- O carro deve parar – q
Se o semáforo está vermelho, então o carro deve parar – (p→q)
SEMâNTICA DA LóGICA PROPOSICIONAL
Uma fórmula da Lógica Proposicional deve estar aderente à interpretação
dos seus símbolos proposicionais e da tabela verdade resultante da
aplicação dos conectivos lógicos
p q ~p pË¿q pË¿q p→q p↔q
V V F V V V V
V F F F V F F
F V V F V V F
F F V F F V V
 
PROVA LóGICA
Uma fórmula lógica proposicional é uma Tautologia se todos os
argumentos resultantes da aplicação dos conectivos lógicos forem
Verdadeiros.
Por outro lado, se nenhuma interpretação satisfaça a verdade, e todos os
argumentos sejam falsos, ele é denominado como Contradição.
Podemos definir também que, se os argumentos finais tiverem tantos
elementos verdadeiros, bem como falsos, eles são denominados como
Contingência.
Portanto, uma prova lógica proposicional deve fornecer, na aplicação dos
conectivos lógicos as seguintes definições:
- Tautologia;
- Contradição, ou;
- Contingência.
ATIVIDADE FINAL
Uma tautologia se caracteriza por:
A. Os argumentos resultantes da tabela verdade, na aplicação de uma fórmula,
sejam tanto verdadeiros como falsos.
B. Todos os argumentos resultantes da tabela verdade, na aplicação de uma
fórmula, sejam falsos.
C. Todos os argumentos resultantes da tabela verdade, na aplicação de uma fórmula,
sejam verdadeiros. 
D. Os argumentos resultantes da tabela verdade sejam contraditórios.
E. Os argumentos resultantes da tabela verdade sejam considerados de
contingência.
REFERÊNCIA
Minsky, Marvin. 2006. The Emotion Machine: commonsense thinking, artificial
intelligence, and the future of the human mind. New York  : Simon & Schuster,
2006.
Rich, Elaine e Knight, kevin. 1993. Inteliência Artificial. São Paulo  : Makron
Books, 1995.
Russel, Stuart e Norvig, Peter. 2004. Inteligência Artificial. Rio de Janeiro  :
Elsevier, 2004.
Lógica de Primeira Ordem
DESCREVER SUMARIAMENTE OS CONCEITOS DE LÓGICA DE PREDICADOS
(OU LÓGICA DE PRIMEIRA ORDEM)
AUTOR(A): PROF. LEANDRO ZERBINATTI
Lógica de Predicados (Ou Lógica de Primeira Ordem)
Existem vários argumentos que não são adequadamente formalizados em lógica
Proposicional, assim, com alguns recursos da Lógica de Predicados é possível a
sua formalização e uso computacional.
Quantificadores e Variáveis
Quantificador Universal
Considere o exemplo:
Todo S é P.
Utilizando a letra ‘x’ como uma variável para representar objetos individuais,
expressamos tal enunciado por:
Qualquer que seja x, se x é S, então x é P.
Essa formulação contém um condicional, que adotamos o símbolo ‘∀’, que
significa “qualquer que seja” ou “para todo”. Esse símbolo chama-se de
quantificador universal.
Em vez de escrever ‘x é S’, escreveremos ‘Sx’, e de forma similar escreveremos
‘Px’. Utilizando ‘→’ para o condicional, o enunciado se torna:
∀x(Sx→Px)
Já o enunciado de Nenhum S é P, pode ser expresso nessa notação, e que
significa:
Qualquer que seja x, se x é S, então, x não é P, isto é:
∀x(Sx→~Px)
 
Quantificador Existencial
Considere o exemplo:
Algum S é P.
Ele pode ser expresso como:
Para pelo menos um x, x é S e x é P.
Ela contém uma conjunção. Adotamos o símbolo ‘∃’para significar “para pelo
menos um”, ou abreviadamente, “para algum”.
Reescrevemos a proposição como:
∃x(Sx & Px)
 
Uma forma equivalente de expressar o de ‘∃' é “existe...tal que”. Assim, a fórmula
acima pode ser lida como:
Existe um x, tal que x é S e x é P.
Da mesma forma a proposição,
Algum S não é P, pode ser expressa através da notação;
∃x(Sx & ~Px)
Que significa que “para pelo menos um x, x é S e x não é P”, ou de forma
equivalente “Existe um x tal que x é S e x não é P”.
 
Predicados e Nomes próprios
 
Nem todos os enunciados contêm quantificadores. Existem enunciados do tipo
sujeito-predicado, onde é atribuída uma propriedade a uma pessoa ou alguma
coisa. Podemos interpretar as letras minúsculas do início de do meio de nosso
alfabeto como nomes próprios para indivíduos, e adotamos por convenção de
escrever o sujeito depois do predicado.
Assim a sentença:Jones é um ladrão.
É formalizada por:
Lj
Onde ‘j’ é interpretada como o nome próprio ‘Jones’ e ‘L’ como predicado ‘é
ladrão’.
Alguns predicados podem ser combinados com dois ou mais nomes próprios para
formar uma sentença. Eles são escritos em notação lógica, na ordem predicado-
sujeito-objeto.
O enunciado:
Bob ama Cathy.
É formalizado por;
Abc
E a sentença;
Cathy ama Bob.
É formalizada por
Acb
 
Regras de formação
Mais precisamente a linguagem formal dividimos o vocabulário dessa linguagem
em duas partes: os símbolos lógicos (cuja interpretação permanece fixa em todos
os contextos) e os símbolos não lógicos (cuja interpretação varia de problema
para problema).
Símbolos Lógicos
Operadores lógicos: ‘~’, ‘&’, ‘v’, ‘→’,’↔’
Quantificadores: ‘∀’, ‘∃’
Parênteses: ‘(‘, ‘)’
 
Símbolos não-lógicos
Letras nominais: letras minúsculas de ‘a’ a ‘t’
Variáveis: letras minúsculas de ‘u’ a ‘z’
Letras predicativas: letras maiúsculas.
Definimos de fórmula da linguagem como sendo qualquer sequencia finita de
elementos do vocabulário (símbolos lógicos e não-lógicos)
 
Regras de Inferência
 
O cálculo de predicados usa as mesmas regras do cálculo proposicional.
Temos ainda as regras de introdução e de eliminação para os quantificadores. Do
mesmo modo que no cálculo proposicional, as regras de inferências não podem
se aplicadaspara uma fórmula qualquer, em uma derivação hipotética, depois de
concluída a derivação.
A regra de eliminação do quantificador universal estabelece que o que é
verdadeiro para qualquer coisa deve ser verdadeiro, também, para um individuo
particular.
Veja o exemplo:
Todos os homens são mortais
Sócrates é um homem.
Logo, Sócrates é mortal
Utilizando ‘H’ para ‘é um homem’, ‘M’ para ‘ é mortal’ e ‘s’ para ‘Sócrates’,
formalizamos esse argumento por:
∀x(Hx→Mx)
Hs
Ms
 
ATIVIDADE FINAL
Qual a alternativa que representa, através da Lógica de Primeira
Ordem, a sentença:
Todos os homens são felizes
Sendo 'H' a representação de homem e 'F' a representação de felizes
A. 
B. 
C. 
D. 
REFERÊNCIA
Nolt, J; Rohatyn, D;, Lógica, 1991, Schaum McGraw-Hill
 
Redes Semânticas e Redes Frames
APRESENTAR OS CONCEITOS DAS REDES SEMÂNTICAS E DAS REDES FRAMES.
AUTOR(A): PROF. LEANDRO ZERBINATTI
REDES SEMâNTICAS
A perspectiva de representar tudo no mundo é assustadora. Lógico que
não podemos representar tudo, mas as redes semânticas oferecem auxílios
gráficos para visualização de uma base de conhecimento e algoritmos
eficientes para a dedução de propriedades de um objeto, de acordo com a
sua pertinência a uma categoria.
Em 1909, Charles Peirce propôs uma notação gráfica de nós e arcos,
denominados arcos existênciais, que ele chamou de "a lógica do futuro". A
partir de então, abriu-se um longo debate entre os cientístas das áreas da
lógica e da redes semanticas.
Esse debate ofuscou o fato que as redes semântica são uma forma de
lógica.
A notação que as redes semântica oferecem é mais intuitiva, oferecendo
os conceitos de objetos, relações, quantificação. Existem alguns tipos de
redes semânticas, mas elas são capazes de representar objetos individuais,
categorias de objetos e relações entre os objetos.
Uma notação gráfica típica exibe os nomes de objetos ou categorias em
elipses ou retângulos e os conecta por meio de links (ou arcos) rotulados.
É bastante intuitivo a criação das bolhas e setas de tal forma que
podemos, de certa forma, nos empolgar e começar a pensar em
representar todo o conhecimento humano dessa foram.
NOTAçãO DA REDE SEMâNTICA
A notação da rede semântica torna muito convenirente executar o
racioncíno de herança.
Assim um objeto sempre herda a propriedade de seu objeto ou categoria
subjacente.
Para identificar se existe a propriedade herdada identificando o algoritmo
de herança, deve-se seguir o link (arco) desde o objeto avaliado até o à
qual ela pertence.
A simplicidade e a eficiência desse mecanismo de inferência, comparado à
prova de teoremas lógicos, foi um dos principais fatores de atração das
redes semânticas.
A herança é complicada a partir do ponto à qual ela pertence a duas ou
mais categorias, ou se ela faz parte de um subconjunto de mais de uma
categoria. Quando isso ocorre recebe o nome de herança múltipla.
Em casos semelhantes a esses, pode-se encontrar dois ou mais valores
conflitantes que respondam a essa consulta.
Deve-se ter notado que uma desvantagem da notação de rede semântica,
em comparação com a lógica de primeira ordem é o fato dos arcos entre os
objetos ou categorias representam somente relações binárias.
Veja a representação da asserção lógica Voar(TAM, São Paulo,   Rio de
Janeiro, Ontem).
 
Legenda: REPRESENTAçãO DE REDE SEMâNTICA
REDE FRAME
As Redes Frames foram primeiramente publicadas por Minsky (1974,
Winston (1975), Haugeland (1981) Brachman e Levesque (1985).
Essa Rede é uma evolução das Redes Semânticas e um Frame é
identificado por um nome e descreve um objeto complexo através de um
conjunto de atributos. 
Em sua evolução pode-se citar:
1. Os nós são substituidos por Frames
2. Os arcos são substituidos por atributos (slots)
Cada Frame portanto possui esses dois atributos - Nome e o tipo de
atributo.
Cada atributo aponta para um outro frame ou para um tipo primitivo e é
constituido de um conjunto de facetas.
As Facetas descrevem o conhecimento ou algum procedimento relativo ao
atributo.
Eles tem as seguintes propriedades:
Valor: especifica o único valor possível
Valor default: especifica o valor assumido pelo atributo caso não haja
nenhuma informação a esse respeito;
Tipo: indica o tipo de dado do valor
Legenda: A REPRESENTAçãO ABSTRATA DE UM FRAME
ATIVIDADE FINAL
A descrição de que é uma representação à qual existem nós que
representam objetos ou categorias, arcos (links) que denominam
atributos de ligação entre os objetos, é característica de:
A. Redes Semânticas
B. Redes Frames
C. Redes Lógicas Dedutivas
D. Representação do Conhecimento por Ontologias
REFERÊNCIA
Rich, Elaine; Knight, Kevin, Inteligência Artificial, Segundo Edição, Editora
McGraw-Hill Ltda.., 1993, p.290-316
Russel, Stuart; Norvig, Peter. Artificial Intelligence. A Modern Approach.
Prentice-Hall Inc., 1995, p. 316-327
Resolução de Problemas por Busca
em Profundidade
DESCREVER DE FORMA SINTÉTICA OS CONCEITOS RELACIONADOS À BUSCA
EM PROFUNDIDADE
AUTOR(A): PROF. LEANDRO ZERBINATTI
RESOLUçãO DE PROBLEMAS POR TéCNICA DE
BUSCA.
Uma das características da conceito de Inteligência é a capacidade de
resolver problemas e a busca no espaco de estados é uma das técnicas
mais utilizadas para a resolução de problemas na Inteligência Artificial.
A ideia é capacitar um agente inteligente capaz de executar ações que
modificam o estado o estado de seu mundo. Dessa forma, um estado
inicial do problema é apresentado, uma configuração do mundo do agente,
um conjunto de ações que o agente é capaz de executar e uma descrição
da meta que se deseja atingir.
A solução se dá na sequência de ações que, quando executada pelo agente,
transforma o estado inicial num estado de meta.
Nesse material, descreveremos o conceito de espaço estados e as
estratégias de busca cega denominada de busca em profundidade.
 
ESPAçO DE ESTADOS
O espaço de estados é descrito por um grafo onde os vértices representam
estados e as arestas, ações.
Um caminho no espaço de estados é uma seqüência de estados conectada
por uma seqüência de ações.
 Uma solução para um problema é um caminho do estado inicial para um
estado meta (objetivo).
� A qualidade da solução é medida pela função de custo da solução.
Uma vez formulado o problema, o estado meta deve ser buscado no espaço
de estados.
 A busca é representada em uma árvore de busca que possui as seguintes
ações:
1. Raiz: corresponde ao estado inicial;
2. Expande-se o estado corrente: aplica-se a função sucessor ao estado
corrente, gerando um novo conjunto de sucessores;
3. Escolhe-se o próximo estado a expandir seguindo uma estratégia de
busca;
4. Prossegue-se até sucesso (atingir estado meta – retorna solução) ou
falha.
Normalmente o desempenho do algoritmo de busca em IA é medido no
intuito de verificar se ele está:
Completo: se existir uma solução, ela certamente é encontrada?
Ótimo: a busca encontra a solução de menor custo?
Complexidade temporal: quanto tempo demora para encontrar a
solução?
Complexidade espacial: quanto de memória é usada para realizar a
busca?
� Em IA a árvore de busca é tipicamente infinita e sua complexidade é
expressa por:
– b : fator de ramificação (branching) ou número máximo de sucessores de
um nó;
– d : profundidade (depth) do nó-meta mais próximo da raiz;
– m : comprimento máximo de um caminho no espaço de estados.
Legenda: ESPAçO DE ESTADOS
BUSCA EM PROFUNDIDADE
Na busca em profundidade, expandimos sempre o estado mais �a
esquerda, no n��ível mais profundo da �árvore de busca at�e que uma
solu�ção seja encontrada, ou at�é que um o nó terminal seja atingido.
Nesse �último caso, retrocedemos e reiniciamos a busca no pr�óximo
estado ainda não expandido, posicionado mais a esquerda, no nível mais
profundo da árvore.
O algoritmo de busca em profundidade é obtido pela sistematização da
ordem de inserção e remoção de estados no conjunto usando uma pilha.
Esta estratégia não é completa (caminho pode ser infinito)nem é ótima.
Se usar uma estratégia que não permite estados repetidos nem caminhos
redundantes, ela é completa. �
Quanto à complexidade espacial, essa estratégia mantém na memória o
caminho que está sendo expandido no momento, e os nós irmãos dos nós
no caminho para possibilitar o retrocesso (backtracking ). Ela apaga
subárvores já visitadas.
Finalizando as orientações, para problemas com várias soluções, esta
estratégia pode ser bem mais rápida do que a busca em largura, porém
esta estratégia deve ser evitada quando as árvores geradas são muito
profundas ou geram caminhos infinitos.
Legenda: BUSCA EM PROFUNDIDADE
ATIVIDADE FINAL
Quando o algoritmo da estratégia de busca em profundidade encontra o
nó terminal, a ação que ele executa é:
A. Retrocede ao nó origem e reinicia a busca pela esquerda. 
B. Expande os nós irmãos.
 
C. Retrocede um nível e expande outro nó filho. 
D. Retrocede até o 1º nível e executa a busca até o nó terminal.
REFERÊNCIA
Rich, Elaine; Knight, Kevin, Inteligência Artificial, Segundo Edição, Editora
McGraw-Hill Ltda.., 1993
Russel, Stuart; Norvig, Peter. Artificial Intelligence. A Modern Approach.
Prentice-Hall Inc., 1995
Resolução de Problemas por Busca
em Amplitude
DESCREVER BREVEMENTE O FUNCIONAMENTO DA BUSCA EM AMPLITUDE
(LARGURA)
AUTOR(A): PROF. LEANDRO ZERBINATTI
Busca em Amplitude (Largura)
 
A busca em amplitude (largura) explora o espaço nível por nível. Apenas quando
não houver mais estados a serem explorados num determinado nível é que o
algoritmo fará a busca para o próximo nível. É um método em que todos os nós
de um mesmo nível são verificados antes de prosseguir para o nível mais baixo, o
que será realizado se não for encontrada a solução no nível da busca. A expansão
dos nós é realizada da seguinte forma:
1. Nó raiz;
2. Todos os nós de profundidade 1;
3. Todos os nós de profundidade 2;
4. Todos os nós de profundidade 3;
5. ...até os nós de maior profundidade.
A figura abaixo ilustra o algoritmo.
 
Legenda: BUSCA EM AMPLITUDE
Na busca em amplitude a solução é encontrada percorrendo-se o menor número
de níveis possível. Com relação aos critérios de avaliação dos algoritmos, ela é
completa, pois sempre encontra uma solução se ela existir, e é ótima se o custo
dos passos forem identicos, pois sempre encontra a solução mais "rasa".
Outra avaliação a ser realizada é em relação a quantidade de tempo e de
memória necessários para se completar a busca. Segundo Russel, na busca em
largura a complexidade de tempo e espaço é exponencial ao tamanho do
caminho.
Dessa forma, essa estratégia consome muito tempo e memória, visto a
necessidade de que todo nó deve ser mantido em memória pois faz parte do
caminho ou é um descendente de um nó do caminho. 
Aplicações
São diversas as aplicações dos algoritmos de busca, dentre elas estão:
Encontrar componentes conectados;
Encontrar todos os nódulos conectados a apenas um componente;
Encontrar o menor caminho entre um nó raiz e os outros nós do grafo;
Testar bipartição em grafos.
ATIVIDADE FINAL
Dada a estrutura:
              A
          /       \ 
      B             E
   /       \      /       \ 
C         D    F        G
O caminho percorrido, a partir do nó A,   pelo algoritmo de busca em
largura é:
 
A. A-B-C-D-E-F-G
B. A-B-E-C-D-F-G
C. A-B-C-D-F-G-E
D. A-B-D-C-E-G-F
REFERÊNCIA
Rich, Elaine; Knight, Kevin, Inteligência Artificial, Segundo Edição, Editora
McGraw-Hill Ltda.., 1993
Russel, Stuart; Norvig, Peter. Artificial Intelligence. A Modern Approach.
Prentice-Hall Inc., 1995
Estratégias de Busca Heurística
ESTRATÉGIAS DE BUSCA HEURÍSTICA
AUTOR(A): PROF. PRISCILA ANGELA BERTON
Estratégias de busca heurística
Como vimos anteriormente, as estratégias de busca cega encontram soluções
testando e expandindo estados, sistematicamente. Infelizmente, além de serem
ineficientes, essas estratégias não garantem encontrar soluções de custo
mínimo.
Existem três estratégias de busca heurística:
a primeira, baseada no conceito de custo de ação, garante encontrar uma
solução de custo mínimo;
a segunda, baseada do conceito de função heurística, é muito eficiente, mas não
garante encontrar uma solução de custo mínimo;
a terceira, que combina as duas estratégias anteriores, não só é muito eficiente,
mas também garante encontrar uma solução de custo mínimo.
Custo de ação
Em muitos problemas, as ações podem ter custos associados, dependendo da
dificuldade que o agente tem em executá-las. Para levar essa informação em
conta durante a busca, precisamos adicionar mais um campo na especificação
dos operadores que é o custo da ação, que transforma o estado s num estado s ,
dado que a condição esteja satisfeita.
Como exemplo:
0
Vamos considerar o Problema das Rotas. Esse problema consiste em, dado um
mapa de vias, uma cidade de origem e uma cidade de destino, encontrar uma
rota de distância mínima entre essas duas cidades. Nesse domínio, o agente é
capaz de viajar de uma cidade à outra e, portanto, suas ações podem ser
especificadas conforme segue.
Legenda: MAPA DE VIAS ENTRE AS CIDADES
via (a, b, 7)
via (a, c, 9)
via (a, d, 3)
via (b, f 3)
via (b, i, 4)
via (c, j, 5)
via (d, e, 1)
via (f, g, 2)
via (g, h, 3)
via (i, k, 5)
via (j, l, 6)
via (k, l, 4)
Custo de caminho
Quando as ações têm custo. Por exemplo, de acordo com a figura acima, o custo
do caminho [via(a, d), via(d, e)] é 3 + 1 = 4. Numa árvore de busca, todo estado s
está associado a um caminho que levado estado inicial s até s. Então, podemos
definir o custo de um estado numa árvore de busca como sendo o custo do
caminho que leva até ele.
Busca pelo menor custo
O algoritmo de busca pelo menor custo combina os comportamentos da busca
em largura (amplitude) e da busca em profundidade. Nesse tipo de busca, cada
vez que um estado é expandido, um custo é associado a cada um de seus
sucessores. O algoritmo progride expandindo sempre o estado de menor custo,
até que um estado meta seja encontrado.
Exemplo:
Sejam A o conjunto de ações para o Problema das Rotas (dada no custo de ação),
s =a e G=k. O rastreamento de busca Menor Custo (A, s G) produz a árvore de
busca, onde os estados estão numerados na ordem em que são expandidos
durante a busca e cada um deles tem um custo associado. Observe que o
algoritmo pula de uma ramo para outro da árvore, misturando busca em largura
com busca em profundidade. Observe também que, quando o estado i:11 é
expandido, o estado meta k:16 é gerado. Entretanto, em vez de parar a busca, o
0 
0 0, 
algoritmo prossegue expandindo os estados g:12, j:14 e h:15, que têm custos
menores. Isso é necessário porque, eventualmente, a expansão de um desses
estados poderia gerar um estado k com custo menor que 16.
Legenda: BUSCA MENOR CUSTO
Função heurística
Uma função heurística é uma função que estima o custo mínimo de um caminho
(desconhecido) que leva de um determinado estado a um estado meta. Seja h
uma função que cálcula o custo mínimo exato de um caminho que leva de um
determinado estado a um estado meta. Formalmente, uma função heurística
pode ser qualquer função h que apresente a seguinte propriedade h(s).
Essa propriedade garante que a estimativa dada pela função heurística seja
admissível, ou seja, que nunca super estime o custo real de uma solução. Note
que as funções heurísticas dependem do domínio de aplicação, bem como da
criatividade e experiência de quem a projeta.
Exemplo:
O problema do Quebra-Cabeça de 8 peças consiste em movimentar as peças do
quebra-cabeça horizontal ou verticalmente (para ocupar a posição vazia
adjacente à peça) de modo que a configuração final seja alcançada:
Legenda: QUEBRA CABEçA DE 8 PEçAS
Por exemplo, expandindo o estado corrente acima, temos:
Legenda: QUEBRA CABEçA DE 8 PEçAS
Agora, usando uma função heurística, o algoritmo de busca deveria expandir o
melhor entre esses dois estados sucessores. Mas como decidir qual deles é o
melhor?
Uma possibilidade é verificar oquão longe cada peça encontra-se de sua posição
na configuração final e apontar como melhor estado aquele cuja soma das
distâncias é mínima. Por exemplo, no estado s , as peças 1, 5, 6, 7 e 8 já estão em
suas posições finais. Para as peças 2, 3 e 4, a distância é 1. Portanto, h(s )=3.
Analogamente, temos h(s )=5. Esses valores indicam que uma solução a partir
do estado s pode ser obtida com no mínimo mais três expansões, enquanto que
uma solução a partir de s requer no mínimo mais cinco expansões. Então,
evidentemente, o algoritmo de busca deve expandir o estado s .
Busca pela melhor estimativa
1
1
2
1
2
1
O algoritmo de busca pela melhor estimativa é semelhante ao algoritmo de
busca pelo menor custo. A diferença é que, em vez de se basear no custo g(s), do
caminho já percorrido até s, para selecionar os estados a serem expandidos
durante a busca, a busca pela melhor estimativa se baseia no custo estimado h(s)
do caminho que ainda precisa ser percorrido, a partir de s, até um estado meta.
Exemplo:
Vamos considerar novamente o Problema das Rotas, visto no sub-item Custo de
Ação. Como heurística, usaremos a distância em linha reta entre a cidade
corrente e a cidade que se deseja atingir. Vamos encontrar uma rota que leve da
cidade a à cidade k e, para facilitar a exposição, vamos definir a função
heurística da seguinte forma:
h(a)=15
h(b)=7
h(c)=6
h(d)=14
h(e)=15
h(f)=7
h(g)=8
h(h)=5
h(i)=5
h(j)=3
h(k)=0
h(l)=4
O rastreamento da Busca Melhor Estimativa (A, a, k) produz a árvore de busca da
figura abaixo, onde os estados estão numerados na ordem em que são
expandidos durante a busca e cada um deles tem uma heurística associada.
Legenda: BUSCA MELHOR ESTIMATIVA
Observe que o uso da heurística orienta a busca de tal forma que algoritmo,
praticamente, segue direto em direção à meta. Evidentemente, a busca pela
melhor estimativa nem sempre é tão eficiente assim. Tudo vai depender do
problema sendo resolvido e da heurística utilizada. Entretanto, apesar de
eficiente, a busca pela melhor estimativa não pode garantir que uma solução de
custo mínimo será encontrada. Nesse exemplo, a solução encontrada tem custo
24, um custo bem superior ao custo daquela solução encontrada pelo algoritmo
de busca pelo menor custo.
Busca A* ( Busca Ótima)
Conforme vimos, a busca pelo menor custo minimiza o custo do caminho
percorrido até o estado corrente, enquanto a busca pela melhor estimativa tenta
minimizar o custo estimado do caminho a ser percorrido do estado corrente até
um estado meta. Para garantir a solução de custo mínimo, a busca pelo menor
custo acaba tendo que examinar uma grande quantidade de estados no espaço de
estados do problema, podendo ser muito ineficiente. Por outro lado, a busca pela
melhor estimativa reduz o espaço de busca consideravelmente; porém, não
consegue garantir uma solução de custo mínimo. Felizmente, é possível
combinar essas duas estratégias de busca num mesmo algoritmo, denominado
A*.
O algoritmo de busca A* minimiza o custo total do caminho percorrido, desde o
estado inicial até um estado meta, usando uma função da forma f(s)=g(s)+h(s),
onde g(s) é uma função de custo e h(s) é uma função heurística.
Exemplo:
Vamos continuar com o Problema das Rotas, cujos custos das ações foram
especificados no sub-item Custo de Ação e cujos valores da função heurística
foram definidos no exemplo do Custo da Melhor Estimativa. O rastreamento da
Busca A* (A, a, k) produz a árvore de busca da figura abaixo, onde os estados
estão numerados na ordem em que são expandidos durante a busca e cada um
deles tem associada a soma de seu custo com a sua heurística. Observe que o uso
da função custo g(s) garante que o algoritmo encontre uma solução de custo
mínimo (como na busca pelo menor custo) e, ao mesmo tempo, o uso da
heurística h(s) reduz o espaço de busca explorado, melhorando a eficiência do
algoritmo (como na busca pela melhor estimativa).
Legenda: BUSCA ÓTIMA (A*)
ATIVIDADE FINAL
A rede ilustrada a seguir é a representação de um conjunto de 11
prédios residenciais construídos em uma área afastada da cidade. As
linhas ligando os prédios são os canos que foram instalados para a
passagem de toda a fiação elétrica, telefônica, etc. e os números
próximos às linhas indicam o comprimento (em metros) destes
encanamentos. Um esquema de segurança a ser adotado pelo
condomínio implica na colocação de dois dispositivos eletrônicos que
devem ser interligados, sendo um na portaria do prédio A e outro na
portaria do prédio I. Como deve ser instalada a fiação destes
dispositivos de segurança de maneira que a quantidade de fio gasto
para conectar o dispositivo do prédio A ao dispositivo do prédio I seja a
mínima possível? 
 
Usando um algoritmo de busca ótimo para resolver o problema, a
solução encontrada indicará que fiação deve passar pelos canos que
ligam os prédios: 
A. A, B, D, H e I
B. A, B, G, J e I
C. A, C, E e I
D. A, C, E, K e I
Considere o problema de roteamento no qual se deseja encontrar uma
rota  que ligue o roteador A ao roteador I.  No grafo abaixo cada arco
indica o custo do operador (distância em km) e  entre parênteses é
indicado uma estimativa do custo até o nó objetivo.  Encontre a rota
utilizando a estratégias de busca melhor estimativa. 
? 
A. A-B-E-I 
B. A-B-E-D-F-H-I 
C. A-C-D-G-H-I 
D. A-B-E-D-G-H-I 
Considere o problema de roteamento no qual se deseja encontrar uma
rota que ligue o roteador A ao roteador I. No grafo abaixo cada arco indica
o custo do operador (distância em km) e entre parênteses é indicado uma
estimativa do custo até o nó objetivo. Encontre a rota utilizando a estratégias
de busca menor custo.
Processamento de Linguagem
Natural
DESCREVER DE FORMA SUCINTA OS CONCEITOS PRELIMINARES DE PROCESSAMENTO DE LINGUAGEM
NATURAL
AUTOR(A): PROF. LEANDRO ZERBINATTI
PROCESSAMENTO DE LINGUAGEM NATURAL
Entre os anos de 1960 e 1985 muitos estudos relacionados à lingüística, psicologia, inteligência
artificial e processamento de linguagem natural foram dominados por uma abordagem racional, ou
seja, caracterizada por acreditar que o conhecimento na mente humana não é derivado do senso e
sim derivada de herança genética (Manning, et al., 1999).
Chomsky sugere na abordagem racionalista que as partes principais da linguagem são inatas, ou
seja, são escritas no cérebro ao nascer, fazendo parte da herança genética humana (Manning, et al.,
1999).
A capacidade da língua é um dos componentes da moderna teoria da evolução. A capacidade
humana para imaginação criativa, linguagem e outros modelos de simbolismos, matemáticos,
interpretação e armazenamento de fenômenos naturais, práticas sociais entre outros, é uma
capacidade cristalizada nos 50.000 anos de existência humana e que nos difere de qualquer outro
animal, inclusive outros hominídeos (Chomsky, 2006).
Este é um dos famosos desentendimentos entre dois dos fundadores da Teoria da Evolução das
Espécies. Alfred Russel Wallace afirmava, ao contrário de Darwin, que a evolução desta capacidade
não ocorreu de acordo com a variação da seleção natural somente, mas requereu “alguma outra
influência, lei, ou agência”, como a teoria gravitacional, coesão, e outras forças sem as quais o
universo não existiria (Chomsky, 2006).
Vários cientistas concordam com o paleoantropólogo Ian Tattersall que afirma ser quase certo que
a invenção da linguagem foi um acontecimento súbito e serviu de estímulo para libertar a
capacidade humana para registrar sua evolução proporcionando um salto evolutivo (Chomsky,
2006).
O biólogo evolucionário Jared Diamond descreveu este processo como o resultado de algum evento
genético que permitiu ao cérebro originar a linguagem humana com uma rica sintaxe, de forma a
permitir uma multiplicidade de modos de manifestação, sendo uma condição essencial para o
desenvolvimento social. Isto propiciou mudanças bruscas de comportamento que são revelados por
arquivos arqueológicos (Chomsky, 2006).Esta mudança proporciou uma evolução do conhecimento humano, que foi aumentado com a
capacidade de representar o conhecimento de forma escrita. Os conhecimentos humanos evoluíram
em diversas áreas e normalmente é utilizada a forma escrita da linguagem natural como forma de
registro e compartilhamento de conhecimento.Um dos objetivos da ciência linguística é
caracterizar e explicar as múliplas observações linguísticas em torno da conversação, escrita ou
através de outras mídias. Parte deste conhecimento se encontra na cognição de como o homem
adquire, produz e entende a linguagem, e outra parte se encontra no entendimento da relação da
língua através da palavra, e uma outra parte ainda se demonstra em entender a estrutura da língua
que utilizamos para nos comunicar (Manning, et al., 1999).
A análise da linguagem escrita pode ser dividida nas abordagens morfológicas, sintática e
semântica (Charniak, 1993).
A análise morfológica estuda a estrutura das palavras, a estrutura das sentenças, o significado das
sentenças individuais e como as sentenças se relacionam entre si.
Na análise sintática determina-se o significado de uma frase que contribui para a determinação do
significado do todo.
A análise da semântica da linguagem pode ser abordada por alguns aspectos. Um deles é a análise a
partir do núcleo mínimo, ou seja, o significado dos elementos, incluindo os mais simples deles, e
em segundo os princípios que permitem combinações de símbolos, organizados hierarquicamente,
que fornecerão os meios para a utilização da língua nos seus múltiplos aspectos (Chomsky, 2006).
Existe ainda uma abordagem empírica que foi dominante nas principais pesquisas entre 1920 e
1960 e agora está ressurgindo. A definição de empírico está associada a um conceito frequêncial de
probabilidade que é determinada com base na proporção de vezes que um evento “A” ocorre em
certo número de observações. Em outras palavras, a probabilidade é determinada pela frequência
relativa: quanto maior o número de observações, mais o valor calculado tenderá ao valor real da
probabilidade. Estes métodos empíricos estão fornecendo novas abordagens explicativas aos
problemas de processamento da linguagem, fornecendo abordagens para a compreensão, aquisição,
e inferência da linguagem, mantendo a sofisticação dos modelos simbólicos (Chater, et al., 2006).
AS ETAPAS DA COMUNICAçãO
A pesquisa em processamento de linguagem natural tem dois objetivos:
1. Construção de modelos computacionais da língua para facilitar a comunicação entre o ser
humano e a máquina.
2. Utilização do computador para validar as teorias linguísticas.
Se dois agentes inteligentes precisam se comunicar para realizar uma tarefa, existem
essencialmente duas técnicas: modificar diretamente a representação interna do outro agente, ou
utilizar uma linguagem. No primeiro caso, o processo será muito eficiente, mas inviável em
situações complexas. No segundo caso, tem o custo de produzir e decodificar mensagens na
linguagem usada, mas também tem a vantagem que não é preciso se preocupar com representação
interna do agente.
É claro que quanto mais estereotipada a linguagem, mais fácil será o processo. Mas isso não é
sempre possível. Em muitas aplicações, especialmente quando um agente humano está envolvido, é
preciso lidar com uma língua natural.
Uma primeira coisa a notar em relação à comunicação em linguagem natural é que um enunciado
representa um ato como qualquer outro, isto é, com um efeito desejado. Chamaremos isso de ato de
fala.
Às vezes um ato de fala é equivalente a um outro ato. Por exemplo, se eu entro em um elevador
para ir no décimo andar, eu posso apertar o botão desse andar, ou pedir para alguém de apertar
para mim. O efeito será o mesmo na maiora dos casos (normalmente ninguém se recusa a fazer esse
favor). Portanto, na interpretação de uma frase em português, não é só o conteúdo semântica que é
extraído, mas também o ato que ela representa.
Eis alguns exemplos de atos de fala:
Informar: Dar uma informação com o objetivo que o receptor atualize seu conhecimento com essa
nova informação. Por exemplo: O João chegou.
Perguntar: Pedir ao outro agente uma informação que não temos, como em Quando chegou o
João?, ou para verificar um fato, como em O João chegou?.
Responder: Fornecer uma informação esperada. Isso é diferente do ato informar, pois nesse caso
devemos statisfazer uma expectativa. Exemplo: O João chegou ontem.
Pedir ou Mandar: O objetivo é que o receptor realize uma ação: Você pode apertar o botão de
décimo andar, por favor?
Prometer: Eu vou resolver esse problema. Nesse caso, o efeito e de criar no receptor da mensagem
uma expectativa de que a ação será realizada.
O processamento da linguagem natural não é uma tarefa fácil. No caso de produção de um
enunciado, é uma tarefa de planejamento. Devemos escolher entre várias maneiras de apresentar as
coisas, e várias maneiras de expressar isso em português. Tudo isso dependerá da intenção do
emissor da mensagem e do efeito desejado sobre o receptor, e também dos conhecimentos que eles
têm naquele momento.
Etapas da comunicação
Ator Etapas Exemplo
Emissor Intenção E quer que R acredite em P
  Geração E escolhe sequencia de palavras S
  Síntese E emite W
Receptor Percepção R percebe W' (idealmente W'=W)
  Análise R infere possíveis significados P1....Pn
  Desambiguação R infere que S quer dizer P1 (idealmente P1 = P)
  Incorporação R resolve acreditar em P1 (ou rejeitar)
O processo inverso da interpretação de uma mensagem é uma tarefa de reconhecimento de plano.
O agente deve tentar reconhecer no enunciado qual era a intenção do locutor, e qual é o conteúdo
vinculado.
Para isso, será necessário resolver algumas ambiguidades que podem aparecer. É importante saber
que para interpretar ou produzir um enunciado, devemos usar certo conhecimento do mundo e um
mecanismo de inferência.
Considere por exemplo o seguinte discurso: Me venderam uma televisão de má qualidade. Eu a
devolvi e até agora não consegui recuperar o meu dinheiro.
Para entender esse discurso, é preciso saber que normalmente eu tive que pagar para obter a
televisão, e que normalmente quem está insatisfeito de um produto tem direito de ser reembolsado.
Isso não aparece no discurso. É um conhecimento básico que tudo mundo tem, e que o agente
inteligente deve ter também para entender esse discurso. Além disso o agente deve ser capaz de
inferir que a pessoa que produziu esse discurso tentou ser reembolsada e não conseguiu até agora.
Eis as principais etapas da comunicação (E e R representam o emissor e ou receptor,
respectivamente):
 
 
 
 
 
 
 
 
ANáLISE DO PROCESSAMENTO DE LINGUAGEM
NATURAL
A análise de um enunciado requer vários processos:
Análise fonética: Reconhecimento das sílabas a partir dos sons que formam o enunciado.
Análise morfológica: Identificação dos elementos básicos que formam as palavras. Por exemplo, o
verbo chegou expressa a ação de chegar mas também, devido à presença do sufixe -ou, temos a
informação que essa ação aconteceu no passado. Outro exemplo, a palavra pessoas contém o
sufixo -s que indica que a palavra denota mais de uma pessoa.
Análise sintática: O resultado da análise morfológica é um conjunto de palavras cujas categorias
foram identificadas, junto com todas as informações pertinentes que foi possível extrair da
composição morfológica. A análise sintática tenta identificar como as palavras se combinam para
determinar a estrutura da frase.
Análise semântica: A estrutura produzida pela análise sintática é normalmente uma árvore cujas
folhas são as palavras e os nodos internos, categorias. A partir das folhas, informações são
propagadas até a raiz para produzir uma representação do conteúdo vinculado pela frase.
Análise do discurso: Para interpretar uma frase, às vezes é preciso se referir às frases anteriores. É
o caso com os pronomes. Considere, por exemplo, a segunda frase do seguinte discurso: Há muito
tempo que Joãoestá com meu livro. Eu gostaria de recuperá-lo. Para interpretar o pronome da
segunda frase, é preciso procurar um antecedente na frase que precede. Nesse caso, teremos um
mecanismo para relacionar o pronome com o meu livro e não com João
A ANáLISE SINTáTICA
Para analisar uma frase é preciso usar uma gramática e um léxico.
Uma gramática descreve como uma frase pode ser decomposta em sintagmas.
Um sintagma é uma sequência de palavras que formam uma unidade significativa. Cada sintagma
tem uma palavra principal, que é chamada núcleo e outras palavras dependentes desse núcleo.
Recursivamente, as palavras que acompanham o núcleo podem formar outros sintagmas. Considere
por exemplo a frase João viu Maria.
Nessa frase, a palavra Maria forma um grupo com o verbo viu. Isso é o sintagma verbal viu Maria,
que denota a ação de ver Maria. Esse sintagma, combinado com Joao, forma a sentença. Vamos ver
agora como um analisador pode processar tal frase
Primeiro, precisamos de uma gramática para representar o fato que uma sentença (S) pode ser
formada por um nome próprio (NP) seguido de um sintagma verbal (SV). Recursivamente, a
gramática deve conter uma regra que permite combinar um verbo e un nome próprio para formar
um sintagma verbal.
Eis as duas regras que essa gramática contém:
S ==> NP, SV
SV ==> V, NP
Para determinar a estrutura, é preciso um léxico que relaciona as palavras com as categorias que
pode lhe ser atribuídas:
viu: V
Maria: NP
Joao: NP
Com essa gramática e esse léxico, podemos identificar uma estrutura sintática para a sentença João
viu Maria:
INCLUIR OBJETO DE ANÁLISE DA FRASE
Considere agora as seguintes frases:
1. João dormiu.
2. João viu uma casa.
3. Ele dormiu.
No primeiro caso, temos um verbo sem complemento, o que exige o acréscimo de mais uma regra
para o sintagma verbal, que agora pode conter somente um verbo:
SV ==> V
O segundo exemplo tem uma estrutura semelhante à estrutura associada à sentença Joao viu Maria.
Ao invés de ter um nome próprio só, pode aparecer um sintagma mais complexo, composto de um
determinante (o artigo uma) e um substantivo. Isso sugere mais uma regra para o sintagma
nominal:
SN ==> Det, Subst
O último exemplo mostra mais um caso de sintagma nominal. O pronome ele, que tem aqui a
mesma função que João e um homem, deve ser considerado como um tipo de sintagma nominal:
SN ==> Pro
Note também que agora o sujeito do verbo pode ser outra coisa que um nome próprio. Na verdade,
ele pode ser qualquer sintagma nominal. Juntando tudo, obtemos a seguinte gramática:
S ==> SN, SV;
SV ==> V;
SV ==> V, SN;
SN ==> Pro;
SN ==> NP;
SN ==> Det, Subst.
Supondo um léxico aumentado com as outras palavras dos exemplos, podemos usar essa gramática
para analizá-los.
 
Usando a gramática da seção, agora é possível construir a estrutura de uma frase em português.
Para construir tal estrutura, duas técnicas podem ser usadas. A primeira é uma análise top-dowm,
que começa com um nodo S e tenta expandir a árvore até obtenção de uma estrutura cujas folhas
correspondem às palavras da frase. A segunda é a abordagem bottom-up, que constrói árvores
parciais a partir das palavras até obtenção de uma árvore que tem S como raiz.
ATIVIDADE FINAL
Um componente importante do Processamento da Linguagem Natural é
a análise sintática. As principais componentes da análise sintática são: 
 
A. A fonética e a semântica.
B. Uma gramática e um léxico.
C. A semântica e a análise do discurso.
D. A gramática e a análise do discurso.
REFERÊNCIA
1.    Charniak, Eugene. 1993. Statistical Language Learning. s.l. : The MIT Press, 1993.
2.      Chater, Nick e Manning, Christopher D. 2006. Probabilistic models of language processing and
acquisition. TRENDS in Cognitive Sciences. s.l. : Elsevier, 2006.
3.    Chomsky, Noam. 2006. Language and Mind. s.l. : Cambridge University Press, 2006.
4.      Manning, Christopher D. e Schütze, Hinrich. 1999. Foundations of Statistical Natural Language
Processing. s.l., EUA : The MIT Press, 1999.
Sistemas Especialistas Baseados em
Regras
O OBJETIVO É DESCREVER BREVEMENTE OS ASPECTOS DOS SISTEMAS
ESPECIALISTAS BASEADOS EM REGRAS
AUTOR(A): PROF. LEANDRO ZERBINATTI
SISTEMAS ESPECIALISTAS BASEADOS EM REGRAS
Na década de 70, finalmente foi aceito a idéia de que a máquina poderia
resolver problemas intelectuais e que dependiam de conhecimento para
sua solução, ou seja, conhecimento em um domínio específico.
(Negnevitsky, 2005)
Conhecimento pode ser definido como um entendimento teórico ou
prático de um objeto ou um domínio. Conhecimento também pode ser a
soma de vários saberes, e atualmente o conhecimento é encarado como o
novo poder. (Negnevitsky, 2005)
Quem tem esse conhecimento é chamado de Especialista e essas são as
pessoas mais importantes em diversas organizações atuais. O sucesso
dessas organizações depende cada vez mais no especialisas do domínio
do negócio na qual a organização está inserida.Ninguém pode ser
considerado um especialista do domínio se não tiver um conhecimento
profundo, tanto dos fatos como das regras, bem como uma forte
experiência prática em determinado domínio. As áreas de domínio tende a
serem limitadas.(Negnevitsky, 2005)
O processo mental humano é interno e muito complexo para ser
representado através de algoritmos. Entretanto, muitos especialistas são
capazes de expressar seu conhecimento através de regras, fatos,
modelos, etc.(Negnevitsky, 2005)
A forma de representar o conhecimento em na forma de SE-ENTÃO é
chamada de regras de produção, ou somente Regras. O termo Regra em
Inteligência Artificial é mais comum ser utilizadas como Representação
do Conhecimento, e também pode ser definida como uma estrutura SE-
ENTÃO como aquela na qual a informação ou fato é a parte do SE e as
ações estão incorporadas como ENTÃO.(Negnevitsky, 2005)
 
REPRESENTAçãO DO CONHECIMENTO ATRAVéS
DAS REGRAS
Qualquer regra é composta por duas partes SE-ENTÃO.
A parte SE, também chamada de antecedente, premissa ou condição, e a
parte ENTÃO que é chamada de consequente, conclusão ou ação.
A sintaxe básica para uma regra é:
 
SE
ENTÃO
 
Gerelmente uma regra pode ter vários antecedentes encadeados e ligados
através dos conectores lógicos E (conjunção) e OU (disjunção), ou uma
combinação entre ambos.
Porém é um bom habito misturar conjunções e disjunções na mesma
regra.
 
SE
E
.
.
.
En>
ENTÃO
 
A consequencia em uma regra também pode conter diversas cláusulas:
SE
ENTÃO
           
             n>
 
O antecedente em uma regra contém duas partes:
-um objeto e seu valor (EX: semáforo = verde);
- Operador (EX:siga em frente)
 
SE 'semáforo'=verde
ENTÃO 'carro'=siga em frente
 
Segundo Durkin, 1994, as regras podem representar relações,
recomendações, diretivas, estratégicas e heurísticas.
 
A ESTRUTURA DE UM SISTEMA ESPECIALISTA
BASEADO EM REGRAS
Em meados dos anos 70, Newell e Simon da Universidade Carnegie-
Mellon propôs um modelo de sistema de produção, como fundamentos
para um sistema especialista baseados em Regras. 
Um modelo de produção é baseado na idéia de que os seres humanos
resolvem problemas aplicando seu conhecimento, expresso em regras de
produção, para um dado problema representado por informações
específicas deste. As regras de produção são armazenadas em uma
memória de longa duração e as informações específicas em uma
memória de curta duração.
Um Sistema Especialista baseados em Regras contém cinco
componentes: Uma base de conhecimento, uma base de dados, uma
máquina de inferência, uma explicação da inferência e a interface com o
usuário.
A Base de Conhecimento contém o conhecimento do domínio para
resolver o problema. Em um Sistema Especialista baseado em regras, o
conhecimento é represenato por um conjunto de regras. Cada regra
especifica a relação, recomendação, direção, estratégica ou heurística na
estrutura SE (condição), ENTÃO(ação). Quando parte da condição é
satisfeita, a regra conduz a ação aser executada.(Negnevitsky, 2005)
A Base de Dados inclui um conjunto de fatos que são utilizados contra os
SE(condições) das regras armazenadas na   Base de
Conhecimento. (Negnevitsky, 2005)
A Máquina de Inferência se encarrega de racionalizar as saídas possíveis
das soluções. Ela liga as regras da base de conhecimento com os fatos
providos da base de dados.
A Explicação da Inferência é capaz de responder ao usuário como uma
conclusão particular foi identificada para um conjunto de fatos
específicos. Um sistema especialista deve estar apto para explicar seu
mecanismo lógico para aconselhar, analisar ou concluir uma ação.
A Interface como Usuário é a forma ao qual o Sistema Especialista
Baseado em Regras faz a comunicação entre o usuário que está
buscando uma solução para um problema e o sistema especialista. A
comunicação deve o mais intuitiva e amigável possível.
Legenda: COMPONENTES DE UM SISTEMA ESPECIALISTA BASEADOS EM
REGRAS
TéCNICAS DE INFERêNCIA
Em um Sistema Especialista Baseados em Regras, o conhecimento do
domínio é representado por um conjunto de regras de produção SE-ENTÃO
e os dados são representados por um conjunto de fatos sobre a situação
corrente. A máquina de inferência compara cada regra armazenada na
base de conhecimento com os fatos contidos na base de dados. Quando
uma parte   do SE de uma regra corresponde com um fato, a regra é
acionada e o ENTÃO é executado. As regras executadas podem alterar de
acordo com o conjunto de fatos adicionados.
A representação de parte do SE da regra com o fato produz uma cadeia de
inferência. A cadeia de inferência   indica como o sistema especialista
aplica a regra para se chegar a uma conclusão. Para ilustrar a técnica de
encadeamento da inferência, veja o exemplo:
Suponha que uma base de dados esteja com os fatos A, B, C, D e E, e a
base de conhecimento contenha as três regras:
 
Regra 1 : Se Y é verdadeiro
               E D é verdadeiro
               Então Z é verdadeiro
Regra 2: Se X é verdadeiro
              E B é verdadeiro
              E E é verdadeiro
              Então Y é verdadeiro
Regra 3: SE A é verdadeiro
              E X é verdadeiro
 
A cadeia de inferencia apresentado abaixo indica como um Sistema
Especialista Aplica a regras para inferir o fato Z.
 
Uma máquina de inferência deve decidir quando determinada regra deve
ser acionada. Existe duas principais formas de execução das regras. Uma
chamada de Encadeamento para frente (forward chaining) e
Encadeamento para trás (backward chaining).
 
 
ATIVIDADE FINAL
O local lógico onde as Regras do Sistema Especialista Baseados em
Regras fica armazenado é:
A. Base de Dados
B. Máquina de Inferência
C. Base de Conhecimento
D. Interface com o Usuário
REFERÊNCIA
Negnevitsky, M. "Artificial Intelligence - A Guide to Intelligent Systems",  Addison-
Wesley2005
Rich, Elaine; Knight, Kevin, Inteligência Artificial, Segundo Edição, Editora
McGraw-Hill Ltda, 1993
Russel, Stuart; Norvig, Peter. Artificial Intelligence. A Modern Approach. Prentice-
Hall Inc., 1995
Sistemas Especialistas Baseados em
Casos
DESCREVER BREVEMENTE OS CONCEITOS RELACIONADOS AO RACIOCÍNIO BASEADOS EM CASOS
AUTOR(A): PROF. LEANDRO ZERBINATTI
SISTEMAS ESPECIALISTAS
Na década de 70, finalmente foi aceito a idéia de que a máquina poderia resolver problemas
intelectuais e que dependiam de conhecimento para sua solução, ou seja, conhecimento em um
domínio específico.
Conhecimento pode ser definido como um entendimento teórico ou prático de um objeto ou um
domínio. Conhecimento também pode ser a soma de vários saberes, e atualmente o conhecimento é
encarado como o novo poder. Quem tem esse conhecimento é chamado de Especialista e essas são
as pessoas mais importantes em diversas organizações atuais. O sucesso dessas organizações
depende cada vez mais no especialisas do domínio do negócio na qual a organização está inserida.
Ninguém pode ser considerado um especialista do domínio se não tiver um conhecimento
profundo, tanto dos fatos como das regras, bem como uma forte experiência prática em
determinado domínio. As áreas de domínio tende a serem limitadas.
O processo mental humano é interno e muito complexo para ser representado através de
algoritmos. Entretanto, muitos especialistas são capazes de expressar seu conhecimento através de
regras, fatos, modelos, etc.(Negnevitsky, 2005)
O conceito de Sistemas Especialistas Baseados em Casos está fortemente ligado ao reuso de casos
passados como maneira de resolver problemas. Método também aplicado por nós, seres humanos.
Essa técnica tem forte apoio das pesquisas psicológicas cognitivas. Parte dos fundamentos da
abordagem baseada em casos provém de estudos severos obtidos de evidências empíricas sobre o
papel específico das situações experimentadas anteriormente para solucionar problemas humanos.
A teoria também embasa que o aprendizado com as experiências passadas recentes envolvem uma
dinâmica e envolve uma estrutura de memória e identifica que os seres humanos utilizam os casos
passados para aprender e resolver os problemas. (Aamodt, Plaza, 1994)
Na terminologia de Raciocínio Baseado em Casos - RBC, um caso usualmente denota a situação de
um problema. Uma situação previamente experimentada na qual pode ser capturado e aprendido de
forma a ser reutilizada para solução de problemas no futuro, como referencia de um caso passado,
armazenado e posteriormente recuperado.
 
 
RACIOCíNIO BASEADO EM CASOS
 
A principal tarefa do RBC, no estabelecimento de sua metodologia, é a identificação de uma
situação problema, ocorrida no passado de maneira similar ao caso presente a ser solucionado,
avaliar a solução proposta, e incrementar o sistema pela aprendizadem a partir da experiência.
Melhor descrevendo o métodos de raciocínio baseado em casos, normalmente é utilizando um caso
genérico. Um tipico caso de RBC possui um certo grau de riqueza na informação contida, bem como
uma complexidade em respeito à sua organização interna.
Algumas caracterísitcas da metodologia baseado em casos é que eles são capazes de modificar ou
adaptar, uma solução recuperados quando aplicado em um contexto de resolução de problemas
diferentes. 
Para que soluçõs prévias dos casos sejam utilizadas para a resolução de problemas futuros, de
características similares, quatro (4) premissas são adotadas para essa representação baseadas em
RBC; 
1. Regularidade: As mesmas ações executadas sob as mesmas condições terão as mesmas saídas;
2. Tipicidade: Experiências tendem a se repetir entre si; 
3. Consistência: Pequenas mudanças nas situações também requerem pequenas mudanças na
interpretação e na solução;
4. Adaptabilidade: Quando as coisas se repetem, as diferenças tendem a ser pequenas, e as pequanas
diferenças são fáceis de serem compensadas.
O CICLO DO RACIOCíNIO BASEADO EM CASOS
Para a solução de problemas utilizando o RBC é necessário seguir os seguintes passos: descrição do
problema corrente, busca por problemas similares previamente resolvidos, recuperação da solução,
adaptação da solução para o problema atual, verificação da solução e armazenamento do novo
problema resolvido. Dessa forma, desde as primeiras soluções poderão ser utilizadas para a solução
de futuros problemas.
Assim sendo, o ciclo de trabalho da metodologia de RBC pode ser melhor descrita utilizando os
quatro estágios de processamento:
1. Recuperação de Casos: Depois da situação do problema ser avaliado, o melhor caso
correspondente é pesquisado na base de casos e uma aproximação da solução é recuperada.
2. Adaptação do Caso: O caso recuperado é adaptado para melhor se encaixar no novo problema;
3. Avaliação da Solução: A solução adaptada a solução pode ser determinada antes que a solução
seja aplicada ao problema ou depois de a solução ter sido aplicada . Em qualquer caso , se o
realizado resultado não for satisfatório, a solução obtida deve ser adaptada de novo ou mais casos
devem ser recuperados.4. Atualização da Base de Casos: Se a solução for identificada como correta, esse novo caso deve ser
adicionado na base de casos.
 
 
Legenda: SISTEMA ESPECIALISTA BASEADO EM CASOS
ATIVIDADE FINAL
Quais os quatro estágios do processamento da metodologia de
Raciocíno Baseado em Casos?
A. Recuperação do Caso, Adaptação do Caso, Avaliação da Solução e Atualização do Banco de Casos.
B. Regularidade, Tipicidade, Consistência e Adaptabilidade.
C. Recuperação do Caso e Adaptação do Caso. 
D. descrição do problema corrente e busca por problemas similares previamente resolvido. 
REFERÊNCIA
(Negnevitsky, M., 2005),  Negnevitsky, M. "Artificial Intelligence - A Guide to Intelligent Systems",   2005,
Addison-Wesley.
(Aamodt, A., 1994), Aamodt, A., Plaza, E. "Case-Based Reasoning: Foundation Issues, Methodological
Variations, and System  Approaches", 1994, AI Communications. Vol. 7, pp. 39-59.
 
 
Redes Neurais Artificiais
DESCREVER DE FORMA ABRANGENTE OS CONHECIMENTOS RELACIONADOS
ÀS REDES NEURAIS ARTIFICIAIS
AUTOR(A): PROF. LEANDRO ZERBINATTI
Redes Neurais Artificiais
Redes neurais artificiais são estruturas computacionais que apresentam
interface com diversas áreas das ciências, entre elas a ciência da computação, a
engenharia, a estatística, a física, a matemática e a neurociência. Redes neurais
artificiais podem ser aplicadas em modelamento de sistemas, análise de séries
temporais, reconhecimento de padrões, processamento de sinais e controle
virtual (Haykin, 1999).
A seguinte definição formal de uma rede neural artificial foi proposta por Hecht-
Nielsen (1990):
“Uma rede neural artificial é uma estrutura que processa informação de forma
paralela e distribuída e que consiste de unidades computacionais (que podem
possuir uma memória local e podem executar operações locais) interconectadas
por canais unidirecionais, chamados de conexões. Cada unidade computacional
possui uma única conexão de saída, que pode ser dividida em quantas conexões
laterais se fizer necessário, sendo que cada uma dessas conexões transporta o
mesmo sinal, que é o sinal de saída da unidade computacional. Esse sinal de
saída pode apresentar valores contínuos ou discretos. O processamento
executado numa unidade computacional pode ser definido arbitrariamente, com
a restrição de que ele deve ser completamente local, isto é, deve depender
somente dos valores atuais dos sinais de entrada que chegam até a unidade
computacional via conexões e dos valores armazenados na memória local da
unidade computacional”.
Uma rede neural contém elementos simples de processamento e conexões entre
esses elementos. O peso das conexões representa o conhecimento da rede. Como
é inspirada na biologia, os modelos de redes neurais procuram funcionar de
modo parecido como uma mente humana (Fu, 1994).
Como demonstrado na figura abaixo, centro do sistema nervoso é composto pelo
cérebro, que recebe a informação capturada pelos sensores dos receptores e
executa a decisão apropriada. Quando na figura existem duas setas, uma para a
esquerda e outra para a direita, significa que existe feed-back do sistema. O
receptor converte estímulos físicos em impulsos elétricos. Os efeitos convertem
impulsos elétricos em respostas para a saída do sistema (Haykin,1999).
O Neurônio Artificial
O neurônio artificial possui muitos nomes diferentes na bibliografia atual. Entre
os sinônimos mais conhecidos, encontram-se: elemento de processamento, nó e
unidade computacional. Esse neurônio possui, na sua estrutura e
funcionamento, alguma similaridade com o neurônio biológico.O neurônio
artificial é a unidade computacional que forma uma rede neural artificial.  São
descritos, a seguir, os três elementos básicos para o modelamento de um
neurônio artificial:
um conjunto de sinapses ou linhas de conexão, sendo que cada uma delas é
caracterizada por uma entrada e um peso associado;
uma somatória dos sinais de entrada com os respectivos pesos associados;
uma função de ativação que limita a amplitude de saída do neurônio.
A seguir, detalha-se cada um desses elementos.
O neurônio artificial possui um ou mais sinais de entrada, como um neurônio
biológico.Uma entrada na rede neural é descrita por um sinal ,Xj, j =1,2,...,n,
sendo n o número de entradas. O sinal é multiplicado por uma constante
denominada peso sináptico.. Essas funções estão descritas abaixo.
Num sistema neural real, o peso sináptico faz o papel da influência que uma
sinapse exerce sobre o neurônio.Podem existir pesos sinápticos negativos e
positivos, assim como existem sinapses excitatórias e inibitórias.
Em termos matemáticos, representado na figura 05, descreve-se a função
somatória como:
Uma função de ativação é utilizada para limitar a amplitude de saída do
neurônio.
Normalmente, essa função é escolhida dentre as seguintes funções:
A função degrau, mostrada na figura abaixo, é definida por:
y = -1 e, x < 0;
y = 1 e, x >=0;
Legenda: FUNçãO DEGRAU
A função rampa, mostrada na abaixo, é definida por:
y = 0 e, x < 0;
y = x e, 1 >= x >= 0;
y = 1 e x > 1;
Legenda: FUNçãO RAMPA
A função logística, mostrada na figura abaixo é definida por:
y =1 / (1+e-x)
Legenda: FUNçãO LOGíSTICA
A função tangente hiperbólica, mostrada na figura abaixo, é definida por:
y = 1 – (1/ 1+x) e x>= 0
y = -1 +1/1-x) e x < 0
Legenda: FUNçãO TANGENTE HIPERBóLICA
A função de ativação é inserida posteriormente à função soma, conforme
mostrada na figura abaixo.
Em alguns modelos de redes neurais, a função de ativação é a própria função
soma das entradas ponderadas do neurônio
Legenda: O NEURôNIO ARTIFICIAL
As Redes Neurais Artificiais Supervisionadas.
Em um aprendizado supervisionado, a rede neural é treinada com auxílio de um
supervisor. Para tanto, a rede deverá possuir pares de entrada e saída, ou seja,
um conjunto de entradas e um conjunto com as saídas desejadas para cada
entrada. Toda vez que for apresentada à rede uma entrada, deverá ser verificado
se a saída obtida (gerada a partir dos cálculos efetuados a partir dos pesos que a
rede possui) confere com a saída desejada para àquela entrada. Sendo diferente,
a rede deverá ajustar os pesos de forma que armazene o conhecimento desejado.
Esta interatividade do treino deverá ser repetida com todo conjunto de
treinamento (entradas e saídas), até que a taxa de acerto esteja dentro de uma
faixa considerada satisfatória.
A seguir, apresentam-se alguns tipos de redes neurais supervisionadas.
Redes Neurais Diretas
Nas redes diretas simples, a entrada da rede envia as informações para a camada
de saída, sem passar por camadas intermediárias, conforme ilustra a figura
abaixo.
Legenda: REDE NEURAL ARTIFICIAL DIRETA
Nas redes diretas multicamadas, existem camadas intermediárias entre a camada
de entrada e a camada de saída, conforme apresentado na figura abaixo.
Numa Rede neural recorrente, há retroalimentação , ou seja, o sinal de uma
camada posterior serve de entrada para camadas anteriores.
Legenda: REDE NEURAL ARTIFICIAL MULTICAMADA
Redes Neurais Artificiais Não Supervisionadas
O modelo de Kohonen é uma rede neural tipo direta não supervisionada.
Essa rede de Kohonen consiste de uma camada de entrada e de uma camada de
saída. Normalmente os neurônios na camada de saída estão arranjados num
plano.
Conforme Kohonen (1987), o esquema básico de um modelo de Kohonen faz com
que neurônios da camada de saída disputem entre si a representação da
informação apresentada aos neurônios de entrada. O neurônio vencedor é
reajustado para vencer com mais facilidade se o mesmo estímulo for recebido
posteriormente. Dentro desse modelo não supervisionado, não somente os pesos
das conexões do vencedor, mas também os pesos de seus vizinhos são ajustados.
A figura abaixo ilustra um exemplo de um mapa de Kohonen.
Legenda: REDE NEURAL ARTIFICIAL NãO SUPERVISIONADA
O funcionamento da rede de Kohonen segue o seguinte funcionamento:
Sinteticamente (Kohonen, 1989), o mecanismo de Kohonen funcionada seguinte
forma: os pesos sinápticos iniciam-se contendo valores aleatoriamente baixos, e
um sinal de entrada x (com valores que representam uma informação qualquer)
é fornecido para a rede sem que se especifique a saída desejada (característica da
rede não supervisionada). O sinal de entrada x é escrito como:x=
[x1,x2,x3,...,xn]t.
Um neurônio de saída y responde “melhor” para a entrada respectiva, e, então, é
d I t f ô i j di d
Lógica Fuzzy
O OBJETIVO DESSE TÓPICO É APRESENTAR OS CONCEITOS PRELIMINARES DA
LÓGICA FUZZY
AUTOR(A): PROF. LEANDRO ZERBINATTI
Lógica Fuzzy
A principal motivação no desenvolvimento de um sistema utilizando a Lógica
Fuzzy é a dificuldade de se modelar e simular a complexidade do mundo real em
sistemas computacionais.
Se em sistemas convencionais é relativamente simples estabelecer e desenvolver
um modelo cuidadoso e bem documentado, em sistemas complexos essa
premissa não se torna realidade visto existirem muitas variáveis que não se pode
estabelecer valores sem restriçõe.
A Lógica Fuzzy, também é conhecida como lógica nebulosa, tem o objetivo de
modelar o raciocà nio humano de forma aproximada, a fim de desenvolver
sistemas computacionais para a tomada de decisão racional em ambientes de
incertezas (Zadeh, 1965).
Lógica Fuzzy é definida como umconjunto de principios matemáticos para a
representação do conhecimento baseada em graus de pertinência em
contrapartida da classificação da lógica binária.
Na Lógica Fuzzy sãoo modelados os conjuntos Fuzzy, que são funções que
mapeiam um valos escalar entre 0 e 1, indicando o grau de pertinência nesse
conjunto.
Normalmente um Sistema que utiliza a Lógica Fuzzy é composta de:
1. Fuzzificação;
2. Avaliação das Regras;
3. Agregação das Saí das das Regras;
4. Defuzzificação.
Um tí pico processo de desenvolvimento de um sistema especialista fuzzy
incorpora os seguintes passos:
Especificar o problema e definir as variáveis linguí sticas;
Determinar o conjunto fuzzy;
Contruir as regras fuzzy;
Relacionar os conjuntos fuzzy, regras fuzzy, procedimentos de inferencia fuzzy;
Avaliar os resultados do sistema.
Legenda: CONTROLADOR FUZZY
Fuzzificação
O primeiro passo é identificar dois grupos rispidos (0 e 1) e determinar o grau
que essa entrada irá ser alocado em cada grupo Fuzzy.
Uma entrada ríspida é um valor numérico limitado dentro do universo de
discurso. Ex: supondo duas entradas x1 e y1 (orçamento do projeto e equipe do
projeto respectivamente). Os valores x1 e y1 são limitadas pelo universo do
discurso X e Y, respectivamente. O alcance do universo do discurso deve ser
determinado por um especialista do assunto a ser modelado. Para determinar o
risco envolvido no desenvolvimento em um projeto Fuzzy, podemos perguntar a
um especialista determinar um número de 0 a 100 porcento que representa o
orçamento do projeto e a equipe do projeto respectivamente.
Em outras palavras, um especialista é solicitado a responder se a extenção do
orçamento do projeto e equipe do projeto são realmente adequado. É claro que
vários sistemas Fuzzy utilizam uma variedade diferente de conjuntos ríspidos.
Enquanto algumas medidas podem ser medidas diretamente (peso, altura, peso,
distancia, temperatura, pressão, etc), outras devem ser determinadas baseadas
somente através da estimativa de especialistas.
Uma vez obtido as entradas x1 e y1, são obtidas, elas devem ser fuzzificadas
através das variáveis linguisticas fuzzy apropriadas. A entrada X1 (orçamento do
projeto classificado por um especialista com 35%) correponde as funções de
pertinência A1 e A2 (inadequado e marginal) com os graus de 0,5 e 0,2,
respectivamente ao conjunto y1(equipe do projeto classificado com 60% por um
especialista) mapeados nas funções de pertinência B1 e B2 (pequeno e
grande)para os graus 0,1 e 0,7 respectivamente. Dessa maneira, cada entrada
fuzzificada é mapeada nas funções de pertinência utilizadas pelas regras difusas
Legenda: O PROCESSO DE FUZZIFICAçãO
Avaliação das Regras
O segundo passo é tomar as entradas fuzzificadas u(x=A1) = 0,5, u(x=A2) = 0,2,
u(y=B1)=0,1 e u(YB2) = 0,7, a aplicar os antecedentes das regras fuzzy. Se uma
regra fuzzy tiver múltiplos anteedentes, o operador fuzzy (E e OU) é utilizado
para obter um número simples que representa o resultado da avaliação dos
antecedentes. Este número é então aplicado como o fator consequente da função
de pertinência.
Legenda: AVALIAçãO DAS REGRAS
O método mais comum de correlação entre uma regra consequente com um valor
verdade obtido por uma regra antecedente é simplesmentecortar a função de
pertinência consequente ao nível da verdade antecedente. Esse método é
chamado de correlação mínima. Quando oinício da função de pertinência é
cortado, o conjunto fuzzy cortada perde algumas informações. Entretanto o
método de correlação mínima é frequentemente utilizado pois envolve menor
complexidade e mais rápido resultado matemático.
Agregação das saídas das Regras
A agregação é o processo de unificação das saídas de todas as regras. Em outras
palavras, nós levamos as funções de pertinência para todas as consequências das
regras previamente cortadas ou dimensionadas e combinadas em um único
conjunto fuzzy.
Assim, a entrada do processo de agregação é uma lista de corter e dimensões das
funções de pertinência consequentes, é a saída é um conjunto fuzzy para cada
variável de saída.
A figura abaixo demonstra com cada saída de cada regra é agregada em um
simples conjunto fuzzy para todas as saídas fuzzy.
Legenda: O PROCESSO DE AGREGAçãO DAS REGRAS
Defuzzificação
O último passo no procsso de inferência fuzzy é a defuzzificação. Ela nos ajuda a
avaliar as regras, mas a saída final de um sistema fuzzi é um número ríspido. A
entrada de um processo de defuzzificação é agregado ao conjunto de saída fuzzy
e a saída é um número simples.
Existe uma série de métodos de fuzzificação, mas provavelmente o mais popular
é a técnica do centróide. Eleencontra o ponto onde uma linha vertical corta o
conjunto agregado em duas massas iguais.
Matematicamente é o centro de gravidade. A figura abaixo mostra o método de
defuzzificação por centróide, o ponto que representa o centro de gravidade do
conjunto Fuzzy, representado pela letra A, no intervalo ab.
Em teoria, o centro de gravidade é calculado ao longo da continuidade de
ponteos agragados da função de pertinência de saída, mas na prática, uma
estimativa racional pode ser obtida calculando isto sobre uma amostra de
pontos.
A figura abaixo mostra o calculo do centro de gravidade
Legenda: O PROCESSO DE INFERêNCIA FUZZY
ATIVIDADE FINAL
A determinação das variáveis linguísticas, das funções de pertinência e
das regras que regem a dinâmica do conhecimento humano, tranferido
para o sistema computacional, são componentes de qual partes da
Lógica Fuzzy? 
A. Fuzzificação
B. Avaliação das Regras
C. Agregação das Saídas das Regras
D. Defuzzificação
REFERÊNCIA
Negnevitsky, M. "Artificial Intelligence - A Guide to Intelligent Systems",  2005,
Addison-Wesley.
Russel, S;  Norvig, Peter;, Artificial Intelligence - A Modern Approach, 1995,
Prentice-Hall.
Algoritmos Genéticos
DESCRIÇÃO OBJETIVA DOS CONCEITOS RELACIONADOS AOS ALGORITMOS
GENÉTICOS
AUTOR(A): PROF. LEANDRO ZERBINATTI
Computação Evolutiva
 
A Inteligência pode ser definida com a capacidade de um sistema a adaptar o seu
comportamento para ser utilizado em qualquer ambiente.
De acordo com Alan Turing (1950) a forma ou a aparência de um sistema é
irrelevante na avaliação de sua inteligência. No entanto, sabemos e é
evidenciado que o comportamento inteligente é facilmente observado em
humanos. Nós somos produtos de uma evolução e, a partir da modelagem do
processo de evolução, esperamos criar um comportamento inteligente. A
computação evolutiva procura simular essa evolução em computadores. O
resultado dessa simulação é uma série de algoritmos de otimização, baseada em
um simples conjunto de regras.  A otimização melhora