Uma teoria e metodologia de aprendizado indutivo
60 pág.

Uma teoria e metodologia de aprendizado indutivo


DisciplinaLivros24.052 materiais99.748 seguidores
Pré-visualização16 páginas
38/60
O custo computacional de evolução da afirmação indutiva.
A memória requerida para guardar a afirmação indutiva.
A quantidade de informação necessária para codificar a afirmação usando operadores predefinidos [Coulon & Kayser,
1978].
 
A importância de cada medida depende do último plano de construção da afirmação indutiva. Para cada caso, a metodologia STAR
permite ao usuário construir um critério de preferência global como uma função de cada medida, para um programa de especificação
indutiva. Como algumas das medidas vistas são computacionalmente caras, simples medidas são usadas, e chamadas de critérios
elementares. Alguns destes critérios são: o número de c­expressões na afirmação, o número total de afirmações relacionais, a razão de
possíveis, mas não vistos, eventos implicados por afirmações para o total de training eventos (uma simples medida de generalização),
e o número total de descritores diferentes. O critério de preferência global é formulado pela seleção dos critérios elementares vistos
(na listagem) que são mais relevantes para o problema, e então arranjados em uma evolução funcional lexicográfica (LEF). Uma LEF
é definida como uma seqüência de pares critério­tolerância:
 
LEF: (c1, \uf074 1),(c2, \uf074 2) \u2026
 
onde ci é um critério elementar selecionado de um "menu" disponível, e \uf074 i é uma tolerância início para o critério ci(\uf074 i \uf0ce[0 .. 100%]).
Dado um conjunto de afirmações indutivas, a LEF determina um dos caminhos preferidos:
 
No primeiro passo, todas as afirmações são avaliadas do ponto de vista do critério c1, e aquele com melhor escore, ou os melhores
dentro da largura definida pela tolerância inicial \uf074 1, são guardados. Depois as afirmações guardadas são avaliadas do ponto de vista
do critério c2 e reduzidas similarmente como visto, usando a tolerância \uf074 2. Este processo continua até que o subconjunto guardado
contenha apenas uma afirmação ( a melhor), ou os pares de seqüência de critérios­tolerância tenham terminado. No último caso, o
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 39/60
grupo de afirmações guardadas são equivalentes do ponto de vista da LEF.
Um importante e surpreendente propriedade de cada aproximação é que alguns sistemas de aprendizado podem gerar descrições
características ou discriminantes de classes de objetos pela adequada definição do critério de preferência.
 
Regras de generalização:
 
Definições e uma visão
 
Construir uma afirmação indutiva de características observadas pode ser conceitualmente caracterizada como uma heurística de
procura estado­ espaço [Nilsson, 1980], onde:
 
estados são descrições simbólicas\u37e o estado inicial é um conjunto de características observadas\u37e
operadores são regras de inferência, especificadamente, generalização, especialização, e regras de reformulação, como
definido abaixo\u37e
o estado meta é uma afirmação indutiva que implica as características observadas, satisfazendo o problema de
conhecimento prévio e maximizando o critério de preferência adotado.
 
Uma regra de generalização é uma transformação de uma descrição em outra mais geral, que tautologicamente implica a descrição
inicial. Uma regra de especialização faz uma transformação oposta: pega uma descrição e gera uma conseqüência lógica para ela.
Uma regra de reformulação transforma uma descrição em outra descrição logicamente equivalente. Uma regra de reformulação pode
ser vista como um caso especial de uma regra de generalização e uma regra de especialização.
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 40/60
Regras de especialização e reformulação são as convencionais regras de inferência com preservação da verdade usadas em dedução
lógica. Em contraste com estas, as regras de generalização não são com preservação da verdade mas com falsa preservação. Isto quer
dizer que se um evento falsifica alguma descrição, então ele também falsificará uma descrição mais geral. Isto é imediatamente visto
pela observação que H\uf0de F é equivalente para ~F \uf0de ~H ( a lei da contraposição). Para ilustrar este ponto, suponha que a afirmação
"alguns pássaros deste lago são nadadores" seja generalizado como "todos os pássaros neste lago são nadadores". Se não há pássaros
no lago que são nadadores, então este fato falsifica não apenas a primeira afirmação mas também a segunda. Falsificar a segunda
afirmação não implica falsificar a primeira.
Em aquisição de conceito, transformar uma regra E ::> K em uma regra mais geral D ::> K quer dizer que a descrição E deve implicar
a descrição D:
E \uf0de D (13)
 
Então, para obter uma regra de generalização para aquisição de conceito, é possível usar uma implicação tautológica da lógica
formal. A premissa e conseqüência de cada implicação deve, quase sempre, ser interpretada como uma descrição de uma classe de
objetos. Por exemplo, a conhecida lei da simplificação:
P & Q \uf0de P (14)
pode ser mudada para uma regra de generalização:
P & Q ::> K |< P ::> K (15)
 
Se P são objetos redondos, Q são objetos marrons e K bolas, então o estado da expressão &quot;objetos redondos e marrons são bolas&quot;
pode ser generalizado para &quot;objetos redondos são bolas&quot;. Então, em aquisição de conceito, a operação de generalização teve uma
simples interpretação teórica: uma descrição é mais geral se ela é satisfeita por um largo número de objetos.
Em ordem para obter uma regra de descrição generalizada, a implicação (14) é revertida, e P e Q são interpretadas como propriedades
dos objetos de alguma classe K:
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 41/60
 
P(K) |< P(K) & Q(K) (16)
 
Se P(K) for &quot;bolas são redondas&quot; e Q(K) for &quot;bolas são marrons&quot;, então de acordo com a regra (16), a afirmação &quot;bolas são redondas
e marrons&quot; é uma generalização da afirmação &quot;bolas são redondas&quot;. Nós podemos ver que a notação &quot;o número de objetos
satisfazendo a descrição&quot; não é aplicável aqui. Generalizar quer dizer: aplicar (hipoteticamente) propriedades que são atribuídas para
uma classe de objetos.
Depois desta introdução informal nós veremos vários tipos de regras de generalização, concentrando­nos primariamente nas regras de
aquisição de conceito. Estas regras serão expressas usando a notação de cálculo de predicado anotado. O reverso destas regras são
regras de especialização e, em casos especiais, regras de reformulação.
Nós iremos restringir nossa atenção para regras de generalização que transformam um ou mais afirmações em um simples afirmação
mais geral:
 
{Di ::> K}i \uf0ce I |< D ::> K (17)
 
Se um evento (uma descrição simbólica de um objeto ou situação) satisfaz alguma descrição Di, i \uf0ce I, então ele irá satisfazer
descrição D (o inverso pode não ser verdade). Uma propriedade básica das transformações generalizadas é que elas resultam em uma
descrição com preservação de estado não conhecida, isto é, uma hipótese que deve ser testada em novos dados. Uma regra de
generalização não garante que a descrição obtida seja útil ou plausível.
Nós distinguiremos entre dois tipos de regras de generalização, seletiva e construtiva. Se todo descritor usado na geração de descrição
de conceito D é descritor que ocorre entre as descrições de conceito iniciais Di, i = 1,2,3.. então a regra é seletiva, caso contrário, ela
é construtiva.
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 42/60
 
Regras de generalização seletivas
 
Nas regras apresentadas abaixo, CTX, CTX1 e CTX2 são algumas expressões arbitrárias (descrições de contexto) que são
argumentadas por componentes adicionais para formular uma descrição de conceito.
 
A regra de condição de descida ­ esta regra é versão generalizada da regra previamente