domingo, 30 de março de 2008

Redes Semânticas

Rodrigo Real
rreal@inf.ufrgs.br

Introdução

Uma rede semântica é uma notação gráfica composta por nodos interconectados. As redes semânticas podem ser usadas para representação de conhecimento, ou como ferramenta de suporte para sistemas automatizados de inferências sobre o conhecimento. As redes semânticas podem ser divididas em [SOW 2002]:

  • Redes de Definição - enfatiza o subtipo, ou a relação do tipo ``é um'' entre um tipo conceitual e um recém definido subtipo. A rede resultante suporta a regra da herança através da cópia de propriedades definidas para o supertipo para todos os seus subtipos. Já que as definições são verdadeiras por definição, a informação neste tipo de rede é geralmente assumida como necessariamente verdadeira;
  • Redes de Asserção - são desenvolvidas para garantir proposições. Diferentemente das redes de definição, a informação em uma rede de asserção é considerada contingentemente verdadeira, a não ser que seja explicitamente marcada com um operador de modo;
  • Redes de Implicação - usa a implicação com principal relação para conexão de nodos. Eles podem ser usados para representar padrões de crenças, causalidade, ou inferências;
  • Redes Executáveis - incluem algum mecanismos, como procedimentos anexos, para execução de inferências, passagem de mensagens, ou busca por padrões e associações;
  • Redes de Aprendizado - constrói, ou estende sua representação através da aquisição de conhecimento a partir de exemplos. O novo conhecimento pode mudar a antiga rede pela adição e remoção de arcos e nodos, ou pela alteração de valores numéricos, que associam nodos e arcos;
  • Redes Híbridas - combinam duas ou mais das redes anteriores.

Redes de Definição

É a mais antiga das redes semânticas. Foi proposta pelo filósofo grego Porfírio que ilustrou o método de categorização proposto por Aristóteles. O método se utilizava de uma estrutura hierárquica de tipos e subtipos. A figura 1 apresenta uma versão da árvore de Porfírio.

As primeiras implementações de redes semânticas surgiram para definições de tipos conceituais e para padrões de relação para máquinas de tradução.

Figura: Árvore de Porfírio

image

A árvore de Porfírio serviu de base para a concepção da linguagem KL-One (Knowledge Language One)[BRA 85], implementada em 1979.

A linguagem KL-One é um linguagem gráfica, o conhecimento é representado na forma de diagramas, com símbolos diferenciados para, por exemplo, conceitos gerais ou conceitos individuais (exemplo círculos brancos ou sombreados). Arcos duplos estabelecem uma relação de subtipo para supertipo. O círculo no centro de algumas flechas representam propriedades (roles). A figura 2 apresenta um exemplo de uma rede semântica utilizando a KL-One.

Figura 2: Exemplo de uso da KL-One

image

Redes de Asserção

Foram desenvolvidas para a asserção de proposições lógicas. A notação gráfica foi criada com base na notação utilizada pela química orgânica. Esta notação foi criada por Although Peirce em 1882, e serviria para mostrar ``os átomos e as moléculas da lógica''.

A Stagirite teacher of a Macedonian conqueror of the world is a disciple and an opponent of a philosopher admired by Church Fathers.

Figura 3: Um grafo relacional

image

Os grafos relacionais conseguem representar apenas dois tipos de operadores: operadores de conjunção image e operadores de "existência" image . Outros operadores como disjunção e negação apresentavam problemas na representação gráfica com relação a delimitação de escopo. A expressão abaixo é equivalente ao grafo apresentado:

image

Diversas propostas foram feitas no sentido de melhorar a notação gráfica deste tipo de rede semântica, permitindo que outros operadores lógicos fossem também utilizados. A primeira implementação utilizada na área de inteligência artificial foi feita por Stuart Saphiro em 1971. Esta primeira implementação evoluiu para o chamado Semantic Network Processing System (SNePS)[SHA 79]. SNePS foi feito para que a base de conhecimento fosse construída a partir de uma representação em linguagem natural[SHA 92].

Figura 4: Exemplo de uso de SNePS

image

A figura 4 apresenta um exemplo do uso de SNePS, no exemplo é representada a frase ``Sue thinks that Bob believes that a dog is eating a bone''. Cada um dos nodos nomeados de M1 a M5 representam uma proposição distinta, cujo conteúdo relacional está em anexo ao nodo de proposição.

Redes de Implicação

As redes de implicação estabelecem relações de implicação entre os nodos. Dependendo da interpretação, estas redes podem ser vistas como redes de crenças e redes Bayesianas, para isto seria necessário envolver valores de probabilidade nas relações de verdadeiro e falso.

Uma rede de implicação pode ser usada, conforme o exemplo apresentado na figura 5, para representar o tipo de conhecimento necessário para que alguém que tenha escorregado na grama possa inferir sobre as possíveis causas.

Figura: Exemplo de redes de implicação

image

Diferentes métodos de raciocínio existem e podem ser aplicados a um mesmo grafo como o da figura 5, algumas vezes é necessária a inclusão de anotações para indicar valores verdadeiros ou probabilidades. As principais abordagens são:

Lógica
métodos de inferência lógica são utilizados em sistema de manutenção da verdade (TMS). Um TMS iniciaria em nodos onde valores verdadeiros são conhecidos, propagando estes valores através da rede. Para o caso da pessoa que escorregou na grama, o sistema iniciaria com valor T para o fato de que a grama está escorregadia, e a partir disto faria a propagação para os outros nodos em busca das possíveis conclusões. Adicionalmente poderiam ser informados outros fatos conhecidos, por exemplo, o fato de se estar na estação das chuvas, este segundo fato seria também propagado e contribuiria para a conclusão final.

Probabilística
muito do raciocínio empregado na abordagem lógica pode ser também empregado na probabilística, na qual também podem ser construídos TMSs. Neste caso a verdade seria considerada com probabilidades iguais a 1.0 e a falsidade com valores iguais a 0.0. Uma contínua faixa de probabilidades existe entre o 0.0 e o 1.0, este fato leva a possibilidade de interpretações mais refinadas dos estados, bem como aumenta a complexidade em termos de processamento da rede. O trabalho de [PEA 96] apresenta alternativas para o uso deste tipo de rede abordando o tratamento de incertezas.

Redes Executáveis

As redes executáveis contém mecanismos que permitem a alteração dinâmica na própria rede. Três tipos de mecanismos são mais comumente utilizados:

  1. Passagem de mensagens - dados passados entre os nodos
  2. Procedimentos anexados - cada nodo possui um procedimento
  3. Transformações de grafos - combinar, modificar e quebrar grafos

Estes três mecanismos podem ser combinados de diversas formas. As mensagens passadas de nodo para nodo podem ser processadas por procedimentos anexos aos nodos, transformações no grafo podem também ser disparadas por mensagens que aparecem nos nodos.

Figura: Exemplo de redes executáveis

image

Programas dataflow podem ser considerados como redes executáveis com procedimentos anexados, o diagrama contém nodos passivos que armazenam dados, e nodos ativos que pegam dados na entrada fazem algum processamento e enviam os resultados para a saída. A figura 6 apresenta um exemplo de programa em dataflow no qual os nodos passivos são representados por uma caixa retangular, e os nodos ativos por um losango. Os labels nas caixas representam o tipo de dado em questão, e nos losangos o nome do procedimento a ser executado.

Um exemplo bastante utilizado de redes executáveis são as redes de Petri. As redes de Petri são um formalismo que combina passagem de um marcador com procedimentos. Assim como diagramas dataflow, as redes de Petri possuem nodos passivos, e nodos ativos, chamados respectivamente de lugares (places) e transições. Adicionalmente elas possuem um conjunto de regras para marcar lugares com pontos, chamados de tokens e para execução e disparo de transições. Para ilustrar o fluxo dos tokens, a figura 7 apresenta uma rede de Petri para uma parada de ônibus, onde três tokens representam as pessoas esperando e um token representa a chegada do ônibus.

Figura 7: Exemplo de Rede de Petri

image

 

Redes de Aprendizado

Um sistema de aprendizado, natural ou artificial, responde a novas informações através da alteração de sua representação interna do conhecimento. Os sistemas que utilizam redes podem se valer de três mecanismos para alteração de sua rede:

  1. Rote memory - conversão da nova informação em uma rede e adição da mesma na rede atual
  2. Alteração de pesos - Alteração de valores associados a nodos ou arcos
  3. Reestruturação - é o mais complexo de todos, e implica basicamente na alteração das conexões entre os nodos

Os sistemas que se utilizam de Rote memory são mais indicados para aplicações que necessitam da recuperação exata de dados. Sistemas que utilizam alteração de pesos (exemplo: redes neurais) são mais indicados para reconhecimento de padrões.

Figura 8: Uma rede neural

image

As redes neurais são um exemplo de rede semântica de aprendizado, estas redes realizam o aprendizado através da alteração de pesos associados aos nodos e arcos da rede. Na figura 8 é apresentado um exemplo de uma rede neural, nesta rede a entrada é uma seqüência de números que indicam a proporção relativa de algumas características selecionados e a saída é outra seqüência de números que indicam o conceito que mais se enquadra dados os valores de entrada. Em um aplicação, por exemplo, de reconhecimento de caracteres, as características seriam linhas, curvas e ângulos, e os conceitos seriam as representações das letras que possuem aquelas características.

Considerações Finais

As redes semânticas podem ser aplicadas em diversas áreas da computação. Muitos dos tipos de redes semânticas podem ser encarados como uma forma alternativa de processamento, tal como é o caso das redes neurais, ou das redes executáveis. As redes semânticas podem apresentar características muito boas para determinados tipos de problemas, tais como problemas de reconhecimento de padrões, e de tratamento de linguagem natural.

O uso de redes semânticas pode também trazer vantagens com relação a simplificação sobre a forma de representar o problema. Em alguns casos, como nas redes de implicação, podem ser estabelecidas relações de causa e efeito de forma bastante simplificada e intuitiva. Nestes casos, podem ser criados sistemas especialistas, nos quais o conhecimento é representado em uma codificação que o ser humano consegue interpretar sem grandes dificuldades.

Referências Bibliográficas

BRA 85
BRACHMAN, R. J.; SCHMOLZE, J. G. An overview of the KL-ONE knowledge representation system. Cognitive Science, v.9, n.2, p.171-216, 1985.

PEA 96
PEARL, J. Decision making under uncertainty. ACM Computing surveys, v.28, n.1, mar 1996.

SHA 79
SHAPIRO, S. C. The SNePS semantic network processing system. In: FINDLER, N. V. (Ed.). Associative networks: representation and use of knowledge by computers. New York: Academic Press, 1979. p.179-203.

SHA 92
SHAPIRO, S.; RAPAPORT, W. The SNePS family. Computers and Mathematics with Applications, Special Issue on Semantic Networks in Artificial Intelligence, Part 1, v.23, n.2-5, 1992.

SOW 2002
SOWA, J. F. Semantic networks. Disponível em: http://www.jfsowa.com/pubs/semnet.htm.

About this document ...

Redes Semânticas

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -white -split 0 -dir html -address rreal@inf.ufrgs.br -white -no_navigation redes_semanticas.tex

The translation was initiated by Rodrigo Real on 2003-03-21


rreal@inf.ufrgs.br

34 comentários:

Anônimo disse...

Imagine what you could achieve if you devoted 28 hours a week to doing something far more constructive?3Legendary icon can be called sentimental The material fed back from that phrase alone would keep them busy for weeks They'd say the most bizarre things that meant nothing to me until after an event took place and then there would be this sudden ah-ha moment and I would finally understand what it was they had been trying to say to me
If mobile industry insists on not accepting it, customers will be there to hunt them down No better demonstration than the recent exposure of pedophile scandals is needed to prove this4 Why is that? Very simple! When these civilizations were taking control over other civilizations, against their Free Will and their way of life, it helped to create a deep anger, and frustration and all kind of energies that accumulated and became a universal force which was ready to explode at the right time

Peyton Manning Youth Jersey
Arian Foster Blue Jersey

Most of you simply do not know the force that controls your so-called autonomic nervous system Some times people need specific skills to perform a specific part of their workA word to the wise: Before I begin, I'd like to stress that this article is intended only to assist you with basic cleaning of the laser toner from your laser printer One may not always come out with award winning plans or make the best of decisions all the time, which means there is room for making mistakes

Arian Foster Elite Jersey

Anônimo disse...

Ignorance is bless Though, he also points out that people have not been using them long enough for us to be sure4 Use gentle motions and vacuum as necessary
With most people, regardless of the industry you are in, in some way you do change lives She is former member of the founding board of the Vancouver Chapter of the International Coaching Federation (ICF) and a current member of the ICF and CoachvilleFine emeralds are generally cut cushion shape with step cutting, and in the East are often cut cabochon Use your vacuum to remove spilled laser toner from within the printer's internal compartment

[url=http://www.newyorkgiantsteamproshop.com/]Victor Cruz Authentic Jersey[/url]
[url=http://fans-chicago.com/]Julius Peppers Jersey[/url]

Do it so that you get to live your purpose, so you can live in joy, so that you care about what is happening around you, so that your children will get to grow up and not live your limitations Again, use your intuitionMobile Manufacturers Forum rejected Professor Challis's call for them to be used on hands-free kits Take an some time with each of your feathered kids and give them the royal treatment

[url=http://www.seahawksnflprostore.com/]Marshawn Lynch Youth Jersey[/url]

Anônimo disse...

buy cheap tramadol buy tramadol online echeck - tramadol 100mg overnight

Anônimo disse...

xanax 1mg what a xanax high is like - xanax withdrawal cold turkey

Anônimo disse...

buy tramadol online buy tramadol online from usa - buy tramadol online usa

Anônimo disse...

tramadol no prescription buy tramadol online no prescription usa - how much tramadol dosage

Anônimo disse...

buy tramadol cod fedex tramadol dose pediatric - cheapest tramadol online no prescription needed

Anônimo disse...

buy tramadol online tramadol addiction blog - order tramadol online international

Anônimo disse...

buy tramadol online how to buy tramadol legally - tramadol for dogs same for humans

Anônimo disse...

buy carisoprodol carisoprodol 350 mg for pain - what is carisoprodol 350 mg side effects

Anônimo disse...

buy tramadol online cod 350 mg tramadol high - tramadol hcl 50mg narcotic

Anônimo disse...

generic tramadol buy tramadol no prescription cheap - tramadol withdrawal loperamide

Anônimo disse...

xanax online xanax pills prescribed - buy xanax craigslist

Anônimo disse...

buy tramadol without rx buy tramadol online florida - tramadol hcl 50 mg 627

Anônimo disse...

buy cialis online cialis price in pakistan - cialis trial offer

Anônimo disse...

cialis online reviews for online cialis - cialis free printable coupon

Anônimo disse...

cialis online cialis usage - cialis webmd

Anônimo disse...

buy cialis online generic cialis 5mg - lloyds pharmacy cialis price

Anônimo disse...

xanax online xanax bars for anxiety - xanax bars your system

Anônimo disse...

buy cialis online buy cialis 5 mg - cialis price list

Anônimo disse...

buy tramadol buy tramadol no prescription overnight - buy tramadol for dogs online

Anônimo disse...

http://landvoicelearning.com/#44827 tramadol 50 mg to get high - tramadol hcl with tylenol

Anônimo disse...

http://buytramadolonlinecool.com/#61458 tramadol dosage weight loss - tramadol purchase online usa

Anônimo disse...

http://landvoicelearning.com/#51602 tramadol 50 mg and - tramadol withdrawal symptoms nausea

Anônimo disse...

buy tramadol mastercard order tramadol online without script - tramadol 100mg no prescription

Anônimo disse...

http://buytramadolonlinecool.com/#28875 tramadol for dogs side effects - tramadol 50 mg ratiopharm

Anônimo disse...

buy tramadol online buy tramadol online paypal - tramadol 50 mg half life

Anônimo disse...

buy ativan online ativan online canada - generic ativan india

Anônimo disse...

buy tramadol 100mg online tramadol online sale - tramadol 50 mg common side effects

Anônimo disse...

ways to buy ativan online how to buy ativan online - ativan generic name classification

Anônimo disse...

http://reidmoody.com/#96318 ativan for alcohol shakes - ativan side addiction

Anônimo disse...

http://ranchodelastortugas.com/#58720 xanax makes me sleepy - xanax online overnight

Anônimo disse...

http://bayshorechryslerjeep.com/#1833 xanax overdose like - xanax 1mg street value

Anônimo disse...

http://www.achildsplace.org/banners/tramadolonline/#7902 order tramadol online overnight - buy tramadol cod overnight