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

Uma teoria e metodologia de aprendizado indutivo


DisciplinaLivros24.042 materiais99.676 seguidores
Pré-visualização16 páginas
correspondentes de outro descritor linear y exibir uma ordem incremental ou decremental,
então descritor duplo:
M(x,y)
é criado, significando que x e y tem uma relação monotônica. Este descritor tem valor alto quando o valor de y é incrementado e
valor baixo quando ele é decrementado.
A idéia do M­descritor pode ser estendida em duas direções. A primeira é criar M­descritores dependentes de alguma condição
COND que deve ser satisfeita pelos eventos sobre consideração:
M(x,y)­COND
Por exemplo, o descritor:
M(comprimento, peso)­vermelho
 
diz que comprimento e peso são relacionamentos monotônicos para objetos vermelhos.
 
A segunda direção de extensão é para relaxar o requerimento para a relação monotônica\u37e isto é, não requerer que a ordem dos valores
de y sejam rigorosamente incrementado (ou decrementado), mas apenas aproximadamente incrementado (ou decrementado). Por
exemplo, o coeficiente de correlação estatística entre x e y pode ser medido, e quando seu valor absoluto está em um certo limiar, um
descritor R(x,y) é criado. O domínio deste R­descritor pode ser {alto, baixo}, indicando correlação positiva ou negativa,
respectivamente, ou ele pode ter valores representando vários sub­séries do coeficiente de correlação. Similarmente, como no caso de
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 54/60
M­descritores, R­descritores podem ser estendidos para descritores R­COND.
O M­ ou R­descritor pode ser usado para gerar novos descritores. Por exemplo, se [M(x,y) = alto], então um novo descritor z =x/y
pode ser gerado. Se z assume uma constante ou valor aproximadamente constante, então um importante relacionamento pode ter sido
descoberto. Similarmente, se [M(x,y) = baixo] então um novo descritor z = x . y pode ser gerado. Estas duas técnicas para gerar
novos descritores tem sido usadas com sucesso no sistema BACON para descoberta de expressões matemáticas representando leis
físicas ou químicas.
Estas idéias podem ser estendidas para descrições estruturais. Tais descritores envolvem não apenas propriedades globais de objetos,
mas apenas propriedades de partes de objetos e as relações entre estas partes. Suponha que em um descritor estrutural de um objeto,
variáveis quantificadas existencialmente P1,P2\u2026Pm denote estas partes. Se x(Pi) e y(Pi) são descritores lineares de Pi (por exemplo,
atributos numéricos caracterizando partes Pi, i=1,2,\u2026), as técnicas descritas para geração de M­ e R­descritores podem ser aplicadas.
 
A metodologia STAR
 
O conceito de um STAR
 
A metodologia apresentada aqui para aprendizado estrutural de descrições através de exemplos recebe este nome do maior conceito
empregado nele, de um star. No sentido mais geral, um star de um evento "e" sobre restrições E é um conjunto de todas as possíveis
alternativas de descrições não redundantes do evento e que não viola as restrições E. Alguma coisa mais restritiva de um star irá ser
usado aqui. Digamos que "e" é um exemplo de um conceito para ser aprendido e E é um conjunto de alguns contra­exemplos deste
conceito. Um star de um evento "e" contra o evento E, denotado G(e|E), é definido como o conjunto de todas as máximas c­
expressões gerais que convergem (isto é, são satisfeitas pelo) evento "e" e que não convergem para nenhum evento negativo em E.
A c­ expressão em um star pode conter descritores derivados, isto é, descritores não presentes nas características observadas. Neste
caso, testar se o evento "e" satisfaz uma dada descrição requer que apropriadas transformações sejam aplicadas para o evento. Tal
processo pode ser visto como prova que o evento implica a descrição, e portanto métodos de prova automática de teoremas podem ser
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 55/60
usados.
Em problemas práticos, um star de um evento pode conter um grande número de descrições. Consequentemente, um star teórico é
substituído por um star ramificado G(e|E,m) que contém não mais que um fixado número m de descrições. Estas m descrições são
selecionadas como as m descrições preferidas, entre outras, de acordo com o critério de preferência definido no problema de
conhecimento prévio. A variável m é um parâmetro do programa aprendiz, definido pelo usuário ou pelo próprio programa, como
uma função das pesquisas computacionalmente disponíveis.
Desde que alguns exemplos de um conceito possam sempre ser caracterizados por uma expressão conjuntiva (um produto lógico de
alguns predicados), elementos de um star podem sempre ser representados por descrições conjuntivas. Uma possível verificação é
que se o conceito a ser aprendido é descrito por uma c­expressao, então esta descrição claramente irá estar entre os elementos de um
(não ramificado) star de algum exemplo positivo simples de um conceito. Consequentemente, se existe um exemplo positivo não
convergindo para nenhuma descrição de um star, então a completa descrição do conceito deve ser disjuntiva, isto é, deve incluir mais
que uma c­ expressão.
 
Resumo do algoritmo geral
 
É assumido que todas as características observadas na forma:
a­expressão ::> K
onde a­expressão é uma expressão atômica descrevendo um objeto e K é o conceito exemplificado por este objeto.
É também assumido que afirmações indutivas são da forma de simples c­expressão ou a disjunção de c­expressões. No caso de
aprendizado de múltiplos conceitos, o algoritmo é repetido para cada conceito com modificações dependendo da interdependência
assumida entre as descrições de conceitos.
POS e NEG denotam conjuntos de eventos representando exemplos positivos e negativos de um conceito respectivamente. Uma
versão geral e simplificada da metodologia STAR pode ser descrito como abaixo:
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 56/60
1. Selecionar randomicamente um evento e de POS.
2. Gerar um star ramificado, G(e|NEG,m), do evento e contrário ao conjunto de exemplos negativos NEG, com não mais que
m elementos. No processo de geração STAR aplicar regras de generalização (ambas seletiva e construtiva), regras
específicas de trabalho, heurísticas para geração de novos descritores supridos pelo problema de conhecimento prévio, e
definições de conceitos previamente aprendidos.
3. No star obtido, procurar uma descrição D com alta preferência de acordo com o critério adotado por LEF.
4. Se a descrição D convergir para o conjunto POS completamente, então vá para o passo 6.
5. Senão, reduza o conjunto POS para conter apenas eventos não convergentes por D, e repita o processo do passo 1.
6. A disjunção de todas as descrições D geradas é uma completa e consistente descrição do conceito. Como passo final,
aplique várias regras de reformulação (definidas no problema de conhecimento prévio) e reduza as regras [equações 8 e 9]
em ordem para obter uma única expressão possível.
 
Este algoritmo é uma versão simplificada do algoritmo geral de conversão Aq [Michalski, 1975b]. A principal diferença é
que o algoritmo Aq seleciona os eventos iniciais (se possível) de eventos não convergidos por algumas das descrições de
stars gerados, preferencialmente àquelas não convergidas apenas pelas descrições D selecionadas. Por este caminho o
algoritmo é hábil para determinar a ramificação no máximo número de descrições separadas em uma disjunção necessária
para definir um conceito. Tal processo pode, de qualquer maneira, ser computacionalmente caro.
O algoritmo visto descreve apenas aprendizado a passo único. Se, depois de gerar uma descrição de um conceito, um novo
training conjunto contradiz ele, regras de especialização ou generalização são aplicados para gerar uma nova descrição de
conceito consistente. Um método para tal aprendizado incremental é descrito em [Michalski