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

Uma teoria e metodologia de aprendizado indutivo


DisciplinaLivros24.112 materiais99.874 seguidores
Pré-visualização16 páginas
& Larson, 1978].
O passo central na metodologia vista é a geração de um star ramificado. Isto pode ser feito usando uma variedade de
métodos. Assim, a metodologia STAR pode ser vista como um esquema geral para implementar vários métodos de
aprendizado e estratégias. A próxima seção descreve um método específico de geração do star.
 
Geração do star: O método indutivo
 
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 57/60
Este método gera uma star ramificado G(e|NEG,m) iniciando com um conjunto de expressões que são seletores únicos,
cada um extraído de um evento para qual o star é gerado ou inferido de um evento pela aplicação de regras de
generalização construtiva ou regras de inferência providas pelo conhecimento prévio. Estas expressões são então
especializadas adicionando outros seletores até a condição de consistência estar terminada (isto é, até cada expressão não
ter intercessão com o conjunto NEG).
Em seguida, as expressões consistentes obtidas são generalizadas até que cada uma tenha o máximo de conversão para
exemplos positivos do training restantes. A melhor consistência m obtida e as c­expressões generalizadas (se algumas são
também completas, então elas são soluções alternativas) constituem a star ramificada procurada, G(e|NEG,m).
Especificadamente, os passos do procedimento são:
0. No primeiro passo seletores individuais do evento "e" são colocados na lista chamada PS. Esta lista é chamada de
star parcial, devido a seus elementos poderem abrigar alguns eventos em NEG. Estes elementos iniciais de PS
(seletores únicos de e) podem ser vistos como generalizações de eventos e podem ser obtidos pela aplicação de todos
os caminhos possíveis de diminuição da condição da regra de generalização (cada aplicação diminui todos os
seletores com exceção de um). Elementos de um star parcial PS são então ordenados do maior para o mínimo
preferido de acordo com o critério de preferência:
LEF1 = <(­negcov,\uf074 1),(poscov, \uf074 2)> (35)
onde negcov e poscov são números de exemplos negativos e positivos, respectivamente, abrigado por uma expressão em star, e \uf074 1
e \uf074 2 são tolerâncias.
O LEF1 minimiza o negcov (pela maximização de ­negcov) e maximiza poscov.
0. A lista PS é então expandida pela adição de novos seletores obtidos pela aplicação das regras de inferência abaixo para o evento
e:
a. regra de generalização construtiva.
b. As heurísticas específicas do problema definidas no conhecimento prévio.
c. As definições dos conceitos previamente aprendidos (para determinar se partes de e satisfazem alguns conceitos
conhecidos).
1. Cada novo seletor é inserido em um apropriado lugar da lista PS, de acordo com o critério de preferência LEF1. O tamanho de
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 58/60
PS é guardado dentro do limite definido pelo parâmetro m.
2. Descrições em PS são testados para a condição de consistência e completeza. Uma descrição é consistente se negcov = 0 (isto é,
se ele não abriga eventos em NEG) e é completo se poscov é igual ao número total de exemplos positivos. Descrições
consistentes e completas são removidas de PS e colocadas na lista chamada SOLUÇÕES. Se o tamanho da lista SOLUÇÕES é
maior que o parâmetro #SOL, então o algoritmo pára. O parâmetro #SOL determina o número de alternativas de descrição de
conceitos desejáveis. Descrições incompletas mas consistentes são removidas da lista PS e colocadas na lista chamada
CONSISTENTE. Se a largura da lista CONSISTENTE é maior que o parâmetro #CONS, então o controle é transferido para o
passo 6.
3. Cada expressão em PS é especializada em vários caminhos pela junção dela com um único seletor da lista original PS. Unir
seletores é menos preferível que o último seletor na expressão conjuntiva (inicialmente , a expressão tem apenas um seletor). O
parâmetro %BRANCH especifica a porcentagem de seletores de mais baixa classificação (pelo critério de preferência) que o
último seletor na conjunção corrente. Se %BRANCH = 100%, todos os seletores de baixa preferência são isoladamente unidos­
isto é, o número de novas expressões geradas desta conjunção irão ser iguais ao número de seletores que tem menor preferência
que o último seletor da conjunção. Todas as novas expressões obtidas são classificadas por LEF1 e apenas as m melhores são
guardadas. Os passos 4 e 5 são repetidos enquanto a lista CONSISTENTE contém o número de expressões especificadas pelo
parâmetro #CONS, ou enquanto o tempo alocado para este processo não estiver acabado.
 
4. Cada expressão na lista CONSISTENTE é generalizada pela aplicação da extensão contrária, fechamento do intervalo, e regras
de generalização de árvores ascendentes. Um eficiente caminho para implementar um processo é transformar o espaço da
descrição estrutural original em um atributo do espaço de descrição. Atributos (isto é, descrições com zero argumentos)
definindo este espaço são criados dos descritores de uma dada expressão da lista CONSISTENTE. A generalização das
descrições dos atributos obtidos é realizado pelo procedimento de geração do star. Detalhes deste processo de transformação de
descrições estruturais em descrições de atributos são descritos por Larson[1977]. A razão para cada transformação é que
descrições estruturais são representadas como grafos rotulados enquanto descrições de atributos são representados como strings
binárias. Isto é computacionalmente muito mais econômico para manusear strings binárias que grafos rotulados.
5. As generalizações obtidas são classificadas de acordo com o critério de preferência global LEF definido pelo conhecimento
prévio. Para obter a descrição discriminante, um típico LEF é maximizar o número de eventos convergido no conjunto POS e
minimizar a complexidade da expressão (medida, por exemplo, pelo número de seletores que ele contém). As m melhores
expressões determinadas constituindo o star ramificado G(e|NEG,m).
19/03/2016 Uma teoria e metodologia de aprendizado indutivo
http://www.inf.ufpr.br/aurora/tutoriais/aprendizadomaq/ 59/60
 
O algoritmo STAR e alguma versão restrita do método descrito foi implementado em várias formas de programa de aprendizado
indutivo [Larson, 1977\u37e Dietterich, 1978\u37e Michalski, 1980 a\u37e Hoff et al, 1982].
 
Conclusão
Uma teoria de aprendizado indutivo tem sido mostrada visando tanto o aprendizado como a busca heurística através do espaço de
descrições simbólicas, geradas pela aplicação de certas regras de inferência para as características iniciais observadas (um professor
gera exemplos de alguns conceitos ou o ambiente provê fatos). O processo de geração da afirmação meta ­ a afirmação indutiva
preferida ­ depende de universais e complementares operações de especialização ou generalização da afirmação, ordenada para
acomodar novos fatos. O domínio do conhecimento prévio tem sido mostrado ser um componente necessário do aprendizado
indutivo, que provê restrições, orientação, e um critério de seleção da afirmação mais desejada.
Uma caracterização de aprendizado indutivo é conceitualmente simples, e constitui uma estrutura teórica para descrição e
comparação de métodos de aprendizado, tão bem quanto desenvolvimento de novos métodos. A metodologia star para aprendizado
estrutural de descrições de exemplos, representa uma aproximação geral para aquisição de conceito que pode ser implementada em
uma variedade de caminhos e aplicada para diferentes domínios de problemas.
Há muitos tópicos de aprendizado indutivo que não tem sido abrangidos aqui. Entre eles está o aprendizado de informação
incompleta ou incerta, aprendizado de descrições contendo erros, aprendizado com múltiplas formas de observação, tão bem quanto
afirmações indutivas baseadas em modelos múltiplos, e aprendizado de regras gerais com exceções. O problema de descobrir novos
conceitos,