Introdução

 

 Um processo de aprendizagem inclui a aquisição de novas formas de conhecimento: o desenvolvimento motor e a habilidade cognitiva (através de instruções ou prática), a organização do novo conhecimento (representações efetivas) e as descobertas de novos fatos e teorias através da observação e experimentação. Desde o início da era dos computadores, tem sido realizadas pesquisas para implantar algumas destas capacidades em computadores. Resolver este problema tem sido o maior desafio para os pesquisadores de inteligência artificial (IA). O estudo e a modelagem de processos de aprendizagem em computadores e suas múltiplas manifestações constituem o objetivo principal do estudo de aprendizado de máquinas.

 

O objetivo de aprendizado de máquinas

Atualmente, o campo de aprendizado de máquinas é organizado sobre três principais focos de pesquisa:

Por conseqüência das muitas pesquisas e esforços na direção destes objetivos, progressos na direção de uma meta freqüentemente conduzem a progressos na direção de outra. Por exemplo, um razoável ponto de partida para a pesquisa do espaço de métodos de aprendizado possíveis pode tomar como iniciativa o exemplo de um robusto comportamento aprendiz, chamado comportamento humano. Similarmente, investigações psicológicas do aprendizado humano podem ser auxiliadas por análises teóricas que sugerem vários modelos de aprendizagem plausíveis. A necessidade de adquirir uma forma particular de conhecimento em alguns estudos orientados a trabalho pode, por si só, gerar novas análises teóricas ou propor a seguinte questão: "Como os humanos adquirem estas habilidades (ou conhecimentos) específicos?" Este mútuo desafio é uma das principais reflexões do campo de inteligência artificial, onde pesquisas com sistemas especialistas, simulação cognitiva e estudos teóricos providenciam um cruzamento de problemas e idéias entre os estudiosos deste assunto.

 

Sistemas de aprendizagem aplicados: uma prática necessária

 Atualmente, instruir um computador ou um robô a realizar um trabalho, requer uma definição correta e completa de um algoritmo para esta tarefa, e então um laborioso programa de computador. Estas atividades envolvem tipicamente um tedioso e demorado esforço por parte de especialistas treinados.

No presente momento, sistemas de computadores não podem aprender a executar uma tarefa através de exemplos ou por analogia a algum trabalho similar e previamente resolvido. Eles não podem melhorar sua performance significativamente através de seus erros passados, ou adquirir habilidades por observação e/ou imitação. Pesquisas em aprendizado de máquinas esforçam-se para abrir a possibilidade de instruir computadores em novos caminhos, e deste modo prometem facilitar a carga que os programadores têm devido ao aumento de complexidade da informação. A rápida expansão dos aplicativos e a disponibilidade dos computadores atualmente, tornam esta possibilidade mais atrativa e desejável.

Quando nos aproximamos de uma aquisição de conhecimento orientado a trabalho, devemos cuidar para que o resultado computacional seja interagente com humanos, sendo compatível com suas habilidades. O argumento tradicional de que uma aproximação engenhosa não precisa refletir a execução humana ou biológica não é realmente aplicável para aprendizado de máquinas. Aprendizado de máquinas devem interagir com as pessoas que vão manuseá-las e, consequentemente, os conceitos e habilidades que elas adquirirem (não necessariamente seus mecanismos internos) devem ser compreendidos pelos humanos.

 

Aprendizado de máquinas como ciência

A dúvida sobre as habilidades dotadas de genética em um sistema biológico (versus habilidade ou conhecimento adquirido), tem fascinado biólogos, psicólogos, filósofos e pesquisadores de Inteligência Artificial. Um forte candidato para a invariante cognição em humanos é o mecanismo de aprendizado - a inata habilidade de adquirir fatos, habilidades e muitos conceitos abstratos. Então, entender o aprendizado humano suficientemente bem para reproduzir aspectos do comportamento aprendiz em um sistema computacional é uma merecedora meta científica. O computador pode render substancial assistência para a psicologia cognitiva podendo ser usado para o teste de consistência e "completeza" de teorias de aprendizado, forçando um compromisso com alto nível de detalhe, evitando desta forma, inexpressividade, tautologia ou teorias não testadas.

O estudo do processo de aprendizado humano é de considerável e significativa prática. Não é surpresa que pesquisas em computadores instruídos com inteligência, com ênfase para desenvolvimento de sistemas tutoriais, partilhem muitas das metas e perspectivas das pesquisas em aprendizado de máquinas. Um particular e interessante desenvolvimento é em computadores com sistemas tutoriais que incorporam habilidades para inferir modelos de competência estudantil pela observação de sua performance. Inferindo o escopo do conhecimento de um estudante e sua habilidade em uma área particular, torna-se mais efetivo e individualizado o ensino.

Um igualmente objetivo básico científico de aprendizado de máquinas é a exploração de mecanismos alternativos de aprendizado, incluindo a descoberta de diferentes algoritmos de indução, o escopo e limitações de certos métodos, a informação que deve estar disponível para o aprendiz, a geração de dados com valores incorretos e a criação de técnicas aplicáveis em muitos domínios de trabalho. Não há razão para acreditar que o método de aprendizado humano é a única forma de adquirir conhecimento e habilidade. De fato, o senso comum sugere que o aprendizado humano representa apenas um ponto do grande espaço de possibilidades de métodos de aprendizagem - um ponto que através do processo evolucionário é particularmente bem localizado para vencer o ambiente físico que nós vivemos. Muitos trabalhos teóricos em aprendizado de máquinas tem concentrado-se na criação, caracterização e análise de métodos de aprendizado globais, com maior ênfase na análise geral e performance psicológicas plausíveis.

Enquanto análises teóricas providenciam um meio de exploração do espaço de métodos de aprendizado, a aproximação orientada a tarefa providencia um veículo para teste e melhoria da performance de sistemas de aprendizado funcional. Por construção e teste aplicado a sistemas aprendizes, podemos determinar o custo efetivo e limitações do aprendizado. Neste caminho, pontos de dados individuais no espaço de possibilidades de sistemas aprendizes são explorados, e o espaço passa a ser melhor entendido.

 

Aquisição de conhecimento versus refinamento de habilidades

Há duas formas básicas de aprendizado: aquisição de conhecimento e refinamento de habilidades. Quando nós dizemos que alguém aprendeu física, nós dizemos que esta pessoa adquiriu conceitos de física, entendeu estes conceitos e compreendeu a relação de cada um deles com o meio físico. A essência do aprendizado neste caso é a aquisição de conhecimento, que inclui descrições e modelos de sistemas físicos e seu comportamento, incorporando uma variedade de representações - desde simples e intuitivos modelos, exemplos e imagens, até completos testes de equações matemáticas e leis físicas. Uma pessoa é dita ter aprendido mais se seu conhecimento explica um largo escopo de situações, é mais exato, e é mais hábil para predizer o comportamento do mundo físico. Esta forma de aprendizado é chamada aquisição de conhecimento. Então, aquisição de conhecimento é definido como aprendizado de novos simbolismos juntamente com a habilidade para aplicar estas informações de maneira efetiva.

A segunda forma de aprendizado é o gradual desenvolvimento motor e cognitivo de uma habilidade através da prática (como andar de bicicleta ou tocar piano). Adquirir conhecimento de um livro ou aprender como executar estas atividades representa apenas a fase inicial do desenvolvimento da habilidade. O centro do processo de aprendizado consiste do refinamento da habilidade, mental ou motora, pela repetição e pela correção dos desvios do comportamento desejável. Esta forma de aprendizado é chamado aprendizado por refinamento de habilidades, diferindo em muitos caminhos do processo de aquisição de conhecimento. Então a essência da aquisição de conhecimento pode ser um processo consciente que resulta na criação de novas estruturas de conhecimento simbólico e modelos mentais, enquanto que o refinamento de habilidades ocorre em um nível subconsciente por virtude da prática da repetição. Muitos aprendizados humanos são uma mistura de ambas as atividades, com tentativa de favorecer a forma intelectual anterior e a coordenação motora, melhorando os trabalhos posteriores.

 

Uma taxonomia da pesquisa de aprendizado de máquinas

A classificação de sistemas de aprendizado computacional pode ser feita de várias formas. Nós escolhemos três dimensões de classificação:

 

Cada ponto do espaço definido por dimensões corresponde a uma particular estratégia de aprendizado, empregando uma representação particular de conhecimento, sobre um domínio específico. Existem,

então, rotinas de aprendizado que empregam múltiplas representações e processos; muitas tem sido aplicadas para mais que um domínio, com sistemas sendo caracterizados para vários pontos do espaço.

As subseções abaixo descrevem os valores explorados em cada uma destas dimensões. O largo espaço de todas as possibilidades de aprendizado está parcialmente explorada e entendida. Existem sistemas de aprendizado correspondendo a pequenas porções do espaço, porque eles representam um pequeno número de valores possíveis de combinações.

 

Classificação baseada em estratégia de aprendizado

Desde que nós distinguimos estratégias de aprendizado pela importância da inferência do aprendiz sobre a informação disponível, nós consideramos dois extremos: execução sem inferência e execução com uma substancial quantidade de inferência. Se um computador é programado diretamente, seu conhecimento é incrementado, mas esta execução não tem inferência alguma; todo o esforço cognitivo fica por conta do programador. Inversamente, se um sistema descobre novas teorias ou inventa novos conceitos independentemente, ele executa uma substancial quantia de inferência. Um ponto intermediário deste espectro pode ser um estudante procurando resolver um problema de matemática por analogia aos exemplos resolvidos do livro - um processo que requer inferência, mas muito menos que descobrir uma ramificação da matemática sem ser guiado por um professor ou um livro.

Quanto mais inferência o aprendiz for capaz de incrementar, menos o professor ou o ambiente externo precisará fazer. É mais difícil programar um computador para executar um trabalho complexo que instruir uma pessoa para realizar o mesmo trabalho; a programação requer explícitas especificações de todos os detalhes requeridos, porém uma pessoa recebendo instrução pode usar conhecimento e bom senso para completar os mais mundanos detalhes. A taxonomia abaixo captura esta noção de quantidade de esforço requerido do aprendiz e do professor:

    1. Aprendizado e implantação direta de novos conhecimentos: nenhuma inferência ou outra transformação de conhecimento é requerida da parte do aprendiz. Variantes deste método incluem:
    2. - Aprender pela programação, construção ou modificação feita por uma entidade externa, não requerendo nenhum esforço por parte do aprendiz (ex. a programação convencional).

      - Aprender pela memorização de fatos e dados sem inferência da informação de entrada (ex. execução por sistemas de banco de dados primitivos ).

       

    3. Aprendendo por instrução - adquirir conhecimento de um professor ou outra fonte, como um livro, requer que o aprendiz transforme o conhecimento de uma linguagem de entrada para uma representação interna, e esta nova informação deve ser integrada com o conhecimento anterior para uso efetivo. Então, é requerido do aprendiz executar alguma inferência, mas uma grande fração da obrigação fica por conta do professor, que deve estar presente e deve organizar tudo de forma que incremente o conhecimento anterior do aprendiz. Aprender por instrução paralela é o método educacional mais formal. Portanto, o trabalho de aprendizado de máquinas é uma forma de construção que pode aceitar instruções ou conselhos guardando e aplicando este conhecimento eficientemente.
    4. Aprendendo por analogia - adquirir novos fatos ou habilidades pela transformação e aumento do conhecimento existente trazendo forte similaridade para o novo conceito ou habilidade desejada em uma forma eficiente e usual em novas situações. Ex. uma pessoa que nunca dirigiu um caminhão, mas já conduziu algum automóvel, deverá transformar a habilidade atual para a nova situação. Similarmente, um aprendizado por analogia deve ser aplicado para converter um programa de computador existente para outro que execute uma função próxima mas diferente da função original. Aprender por analogia requer mais inferência por parte do aprendiz do que o aprender por instrução. Um fato ou habilidade análogo é um parâmetro relevante que deve ser recuperado da memória; então o conhecimento recuperado deve ser transformado, aplicado a novas situações e guardado para uso futuro.
    5. Aprendendo de exemplos: ( um caso especial de aprendizado indutivo) - Pegando uma série de exemplos e contra-exemplos de um conceito, o aprendiz induz uma descrição geral que descreve todos os exemplos positivos do conceito. Aprender por exemplos é um método que tem sido fortemente investigado em inteligência artificial. A porção de inferência executada pelo aprendiz é bem maior que o se aprender por execução e alguma coisa maior que aprender por analogia. Aprender de exemplos pode ser subcategorizado de acordo com a origem dos exemplos:
    6.  

      - A fonte é um professor que conhece o conceito e generaliza seqüências de exemplos para ajudar tanto quanto possível o conhecimento do aprendiz. Se o professor infere o estado de conhecimento do aprendiz, os exemplos podem ser selecionados para otimizar a convergência para o conhecimento desejado.

      - A fonte é o próprio aprendiz. O aprendiz tipicamente sabe seu estado de conhecimento, mas claramente não conhece o conceito a ser adquirido. Então o aprendiz pode gerar modelos ( tendo uma entidade externa como ambiente, ou um professor classificando os exemplos como positivos ou negativos) na base de informação, e confia na discriminação do conceito argumentado. Ex. um aprendiz que adquire o conceito de substância ferromagnética, generalizando os possíveis candidatos como todos os metais. Testando um objeto de cobre e outros metais com um magneto, o aprendiz descobre que cobre é um contra-exemplo, e então, o conceito de ferromagnetismo deixa de ser generalizado para todos os metais.

      - A fonte é um ambiente externo: neste caso, o processo de generalização do exemplo é randômico; o aprendiz deve depender das observações que lhe são disponíveis. Ex. um astrônomo que conhece o conceito de uma estrela cadente, mas não pode saber quando e onde ela irá ocorrer, nem pode induzir este fenômeno.

       

      Uma possível classificação de aprendizado, pode ser pelo tipo de exemplo disponível para o aprendiz:

       

      - Apenas exemplos positivos: exemplos positivos providenciam instâncias de conceitos para serem adquiridos. Eles não fornecem informação que previna super generalização do conceito inferido. Neste caso de aprendizado, deve-se ter cuidado e procurar considerar o mínimo de generalizações possíveis, ou então depender de conhecimento prévio para restringir o conceito a ser inferido.

      - Exemplos positivos e negativos: nesta situação, exemplos positivos forçam generalização enquanto os exemplos negativos previnem a super generalização ( o conceito induzido nunca pode ser tão geral a ponto de incluir alguns dos exemplos negativos ). Esta é a mais típica forma de aprendizado por exemplos.

       

      Aprender de exemplos pode ser um processo experimental ou incremental. No primeiro caso, todos os exemplos são apresentados uma única vez. No último caso, o sistema deve formar uma ou mais hipóteses do conceito ( ou série de conceitos) consistentes com os dados disponíveis, refinando as hipóteses antes de considerar exemplos adicionais. A aproximação incremental mais próxima com o aprendizado humano, permite ao aprendiz usar parcialmente conceitos aprendidos ( para performance ou para guiar o processo de generalização), e habilita o professor a focalizar os aspectos básicos do novo conceito antes de intentar para os detalhes menores. Em outra mão, a aproximação passo a passo é menos apta para o aprendizado de um caminho que gere uma escolha justa de exemplos iniciais para a formulação do novo conceito.

       

    7. Aprendendo de observação e descoberta ( chamado de aprendizado não supervisionado): esta é uma forma muito geral de aprendizado indutivo que inclui sistemas de descoberta, formação de teorias, criação de critérios de classificação para formar hierarquias e trabalhos similares sem a ajuda de um professor externo. Esta forma de aprendizado requer do aprendiz um maior grau de inferência do que as formas de aprendizado anteriores. O aprendiz não dispõe de exemplos de um conceito particular, nem tem acesso a qualquer fonte de classificação de exemplos de generalização ( exemplos positivos ou negativos). Além disso, focalizando um simples conceito por vez, as observações podem detectar outros conceitos que precisam ser adquiridos, introduzindo um severo foco de atenção para o problema. Há uma possível subclassificação do aprendizado por observação de acordo com a medida de interação com o ambiente externo. Os pontos extremos destas dimensões são:

A classificação das estratégias de aprendizado acima ajudam a comparar vários sistemas de aprendizado em termos de seus mecanismos, da fonte de informação disponível e em termos da medida de dependência do conhecimento previamente organizado.

 

Classificação de acordo com o tipo de conhecimento adquirido

Um sistema de aprendizado pode adquirir regras de comportamento, descrições de objetos físicos, heurísticas de solução de problemas, classificação sobre uma amostra do espaço de possibilidades e muitos outros tipos de conhecimento úteis na performance de uma variedade de tarefas. A lista baixo apresenta tipos de conhecimento adquirido, primeiramente em função do tipo de representação deste conhecimento:

      1. Parâmetros em expressões algébricas - aprender neste conceito, consiste de ajustar parâmetros numéricos ou coeficientes em expressões algébricas de uma forma funcional fixa para obter a performance desejada. Por exemplo, "perceptrons [ Rosenblatt, 1958; Minsky & Papert, 1969]" ajusta coeficientes para a entrada lógica de elementos ponderando o aprendizado de reconhecimento de modelos bidimensionais.
      2. Árvores de decisão - alguns sistemas adquirem árvores de decisão para discriminação entre classes de objetos. Os nós em uma árvore de decisão correspondem a selecionados atributos dos objetos, e as arestas correspondem a determinados valores alternativos para estes atributos. As folhas da árvore correspondem a valores de objetos de classes idênticas.
      3. Gramáticas formais - em aprendizados para o reconhecimento de linguagens (usualmente artificiais), gramáticas formais são induzidas de seqüências de expressões da linguagem. Estas gramáticas são tipicamente representadas como expressões regulares, autômatos finitos, regras de gramática livres de contexto ou regras de transformação.
      4. Regras de produção - uma regra de produção é um par condição ->ação {c=>a}, onde 'c' é uma ou mais condições e 'a' é uma seqüência de ações. Se todas as condições da regra de produção são satisfeitas, então a seqüência de ações é executada.
      5. Devido a esta simplicidade e facilidade de interpretação, regras de produção são largamente usadas em representação de conhecimento de sistemas aprendizes. As quatro operações básicas onde regras de produção podem ser adquiridas e aprimoradas são:

        Criação: uma nova regra é construída para um sistema ou adquirida de uma entidade externa;

        Generalização: condições são diminuídas ou tornadas menos restritivas, sendo aplicadas em um número maior de situações;

        Especialização: condições adicionais são acrescentadas ao grupo, ou tornadas mais restritivas, sendo aplicadas em um numero menor de casos (casos específicos).

        Composição: duas ou mais regras que são aplicadas em seqüência são compostas em uma única regra, e então formam um processo "compilado" que elimina qualquer redundância de condição ou ação.

      6. Expressões lógicas formais e formalismos relacionados - estas representações de plano geral tem sido usadas para formular descrições de objetos individuais ( entrada do sistema aprendiz) e para formular descrições de conceitos resultantes ( saída do sistema aprendiz). Estas representações tomam a forma de expressões da lógica formal em que os componentes são proposições, predicados arbitrários, variáveis de valores finitos, afirmações restringindo séries de variáveis ( como um número entre 1 e 9), ou encaixam expressões lógicas.
      7. Grafos e redes - em muitos domínios, grafos e redes providenciam uma forma mais conveniente e eficiente de representação que expressões lógicas, através do expressivo poder de representação da rede que é comparável a das expressões lógicas formais. Algumas técnicas de aprendizado exploram esquemas de casamento e transformação de grafos para comparação e indexação de conhecimento eficientemente.
      8. Frames e esquemas - estes tipos de representação providenciam maiores unidades de representação que expressões lógicas simples ou regras de produção. Frames e esquemas podem ser vistos como coleções de entidades rotuladas ( slots), cada slot tem uma certa tarefa prescrita na representação. Eles tem sido usados em muitas aplicações de inteligência artificial. Por exemplo, um sistema que adquire plantas gerais deve ser hábil para representar e manipular algumas plantas como unidades, através de sua estrutura interna que deve ser arbitrariamente complexa. Além disso, em aprendizado experimental, sucessos passados, alternativas não testadas, causas de falha e outras informações devem ser gravadas e comparadas em indução e refinamento de várias regras de comportamento. "Esquemas" providenciam um formalismo apropriado.
      9. Programas de computador e outros códigos procedurais - o objetivo de algum sistema de aprendizado é adquirir a habilidade de eliminar um especifico processo eficientemente, antes de ponderar sobre sua estrutura interna. Muitos sistemas de programação automática falham nesta categoria. Em adição a programas de computador, códigos procedurais incluem habilidades motoras humanas (como andar de bicicleta), seqüências de instruções para manipulação robótica, e outros "compilados" humanos ou habilidades de máquina. Diferente de descrições lógicas, redes e frames, a detalhada estrutura interna do código procedural resultante não precisa ser entendido por humanos, ou pelos sistemas de raciocínio automáticos. Apenas o comportamento externo da habilidade procedural adquirida precisa ser entendido pelo sistema de raciocínio.
      10. Taxonomias - aprender por observação pode resultar em estruturas globais de objetos do domínio em uma hierarquia ou taxonomia. Quantidades de descrição de objetos em novas categorias propostas e formação de classificação hierárquica requerem que o sistema formule relevantes critérios de classificação.
      11. Representações múltiplas - alguns sistemas de aquisição de conhecimento usam alguns esquemas de representação para o novo conhecimento adquirido. Mais notável, algumas descobertas e sistemas de formação teórica que adquirem conceitos, operações destes conceitos e regras heurísticas para um novo domínio deve selecionar combinações apropriadas de esquemas de representação aplicáveis para as diferentes formas de conhecimento adquirido.

 

Classificação por domínio de aplicação

Uma forma usual de classificação de sistemas aprendizes é na área de aplicação. A lista abaixo especifica áreas de domínio de aplicação onde os sistemas de aprendizado existentes tem sido aplicados. A seqüência de apresentação não reflete qualquer significância do resultado de aprendizado de máquinas.

        1. agricultura
        2. química
        3. modelagem cognitiva (simulação de processos humanos)
        4. programação computacional
        5. educação
        6. sistemas expertos (alta performance, programas de domínio específico)
        7. jogos ( xadrez, poker, etc.)
        8. métodos gerais ( sem domínio específico)
        9. reconhecimento de imagem
        10. matemática
        11. diagnóstico médico
        12. música
        13. processamento de linguagem natural
        14. caracterização física de objetos
        15. física
        16. solução de problemas
        17. robótica
        18. predição de seqüências
        19. reconhecimento de fala

 

 

Uma teoria e metodologia de aprendizado indutivo

 

A presente teoria mostra o aprendizado indutivo como uma busca heurística através do espaço de descrições simbólicas, gerado pela aplicação de várias regras de inferência sobre as características inicialmente observadas. As regras de inferência incluem regras de generalização, que executam transformações em descrições e regras convencionais dedutivas com preservação da originalidade. A aplicação destas regras de inferência para descrições é restringida pelo problema do conhecimento prévio, e guiada por critérios de evolução da qualidade das afirmações indutivas geradas.

Baseada nesta teoria, uma metodologia geral para aprendizado de descrições estruturais através de exemplos, chamado STAR, é descrito e ilustrado por um problema da área de análise conceitual de dados.

 

Introdução

A habilidade das pessoas para fazer generalizações exatas de fatos espalhados ou descobrir modelos em coleções aparentemente confusas é um fascinante tópico de pesquisa. A compreensão desta habilidade é agora também de crescente importância prática, pois ela tem a chave para o desenvolvimento de métodos pelo qual computadores podem adquirir conhecimento. Uma necessidade para o desenvolvimento é evidenciado pelo fato de que aquisição de conhecimento é presentemente o mais limitado "gargalo" no desenvolvimento de modelos de conhecimento intensivo de sistemas de Inteligência Artificial. Uma habilidade maior é conseguida por um processo chamado aprendizado indutivo, isto é, inferência indutiva de fatos providos por um professor ou ambiente externo. O estudo e a modelagem desta forma de aprendizado é um dos principais tópicos de aprendizado de máquinas.

Antes de discutirmos este tópico, vamos primeiro discutir o potencial de aplicação dos sistemas de aprendizado indutivo. Uma possível aplicação é em construção automática de bases de conhecimento para sistemas especialistas. A presente abordagem para construção da base de conhecimento envolve um tedioso processo de formalização de conhecimento especialista e codificação em alguns sistemas de representação de conhecimento, como regras de produção ou redes semânticas. Programas de aprendizado indutivo podem prover melhorias nas técnicas de programação correntes e uma base para o desenvolvimento alternativo de métodos de aquisição de conhecimento.

Em pequenos e selecionados domínios, programas indutivos já são hábeis para determinar regras de decisão por indução em exemplos de decisões especialistas. Este processo notoriamente simplifica a transferência de conhecimento de um perito para uma máquina. A praticidade de algumas formas de aquisição de conhecimento indutivo tem sido demonstrada no sistema especialista PLANTS/ds, para o diagnóstico de doenças da soja. Neste sistema, as regras de diagnóstico foram testadas em poucas centenas de casos doentes. Outro exemplo é em aquisição indutiva de regras de decisão para jogo de xadrez.

Um menos direto, mas potencialmente promissor uso do aprendizado indutivo é para o refinamento de bases de conhecimento inicialmente desenvolvidas por especialistas humanos. Aqui, programas de aprendizado indutivo podem ser usados para detectar e retificar inconsistências, remover redundâncias, fechar lacunas e para simplificar regras de decisão derivadas de um perito. Aplicando um programa de inferência indutiva para os dados, consistindo de regras originais e exemplos de resultados corretos e incorretos da aplicação destas regras para novas situações, os dados podem ser incrementalmente melhorados com pouca ou sem nenhuma assistência humana.

Outra importante aplicação de programas indutivos é em vários campos da ciência (vistos anteriormente). Aqui, eles auxiliam o usuário a detectar modelos conceituais interessantes ou revelam estruturas em coleções de dados. As largas técnicas de análise de dados usadas em matemática e estatística, como análise de regressão, classificação numérica não são suficientes para o potencial deste trabalho. Métodos para análise de dados conceitual são necessários, nos campos em que os resultados não são meramente fórmulas matemáticas, mas caracterização de dados em termos de alto-nível, conceitos orientados a humanos e relacionamentos. Um exemplo desta aplicação é o META-DENDRAL, que infere regras de divisão para simulação de massa espectral.

Há dois modos básicos em que programas indutivos podem ser utilizados: como ferramentas interativas para aquisição de conhecimento de fatos específicos ou exemplos, ou como parte de sistemas de aprendizado de máquinas. No primeiro modo, um usuário supre a máquina com exemplos de aprendizado e fortes exercícios de controle sobre o caminho em que o programa é usado.

No segundo modo, um programa indutivo é um componente de um sistema de aprendizado integrado onde outros componentes geram os exemplos de aprendizado necessários. Alguns exemplos positivos e negativos constituem o feedback de tentativas do sistema para executar uma tarefa desejada. Um exemplo do segundo modo é o sistema de aprendizado LEX para integração simbólica, onde um módulo "generalizador" executa inferências indutivas em instâncias providas por um módulo "crítico".

Do ponto de vista de aplicação, como auxiliar na construção de sistemas especialistas ou análise conceitual de dados experimentais, o mais relevante é o aprendizado indutivo conceitual. Nós usamos este termo para designar um tipo de aprendizado indutivo que são descrições simbólicas em alto nível de produtos finais, termos orientados a humanos e formatos. As descrições são tipicamente aplicadas para objetos ou fenômenos do mundo real, preferencialmente a conceitos de matemática abstrata ou computacional.

O mais freqüente tipo de aprendizado estudado é o aprendizado de exemplos ( chamado de aquisição de conhecimento), onde a tarefa é induzir descrições gerais de conceitos de instâncias específicas destes conceitos. Os estudos iniciais deste assunto começaram por volta de 50 anos atrás, por exemplo com [ Hovland, 1952; Bruner et al., 1956; Newell et al., 1960; Amarel, 1960; Feigenbaum, 1963; Kochen, 1960; Banerji, 1962; Simon & Kotovsky, 1963; Hunt et al., 1966; Hajek et al., 1966; Bongard, 1970]. Juntamente com eles, as mais recentes contribuições são [ Winston, 1970; Waterman, 1970; Michalski, 1972; Hayes-Roth, 1973; Simon & Lea, 1974; Stoffel, 1974; Vere, 1975; Larson & Michalski, 1977; Mitchell, 1978; Quinlan, 1979; Moraga, 1981]. Uma importante variante do aprendizado de exemplos é o conceito de refinamento incremental, onde a entrada de informações inclui, em adição aos exemplos, hipóteses previamente aprendidas, ou hipóteses iniciais providenciadas por humanos que podem ser parcialmente incorretas ou incompletas [Michalski & Larson, 1978]. Outro tipo de aprendizado indutivo conceitual é o conceito de aprendizado por observação (ou generalização descritiva), concernida com o firmamento de novos conceitos ou teorias caracterizando fatos adquiridos. Esta área inclui alguns tópicos como formação automática de teorias (por exemplo [Lenat, 1976]), descoberta de relações entre dados (por exemplo [Hajek & Havranek, 1978]; [Pokorny, 1980], [Zagoruiko, 1981]) ou construção automática de taxonomias. Diferenças entre o conceito de aprendizado de exemplos e o conceito de aprendizado por observação são discutidas em mais detalhes na próxima seção.

Aprendizado indutivo conceitual tem um forte sabor de ciência cognitiva. Ele dá maior ênfase à indução orientada a humanos que a descrições orientadas a máquina, e isto é interessante principalmente em domínios não matemáticos, distinguindo de outros tipos de aprendizado indutivo, como inferência gramatical e síntese de programas. Em inferência gramatical, a tarefa é determinar uma gramática formal que possa gerar uma série de strings (por exemplo, [Solomonoff, 1964; Biermann & Feldmann, 1972; Yau & Fu, 1978; Gaines, 1979]). Em síntese de programas o objetivo é construir um programa de computador de pares de I/O ou traços computacionais, ou para transformar um programa de uma forma para outra pela aplicação de regras de transformação com correta preservação (exemplo [ Shaw et al., 1975; Burstall & Darlington, 1977, Case & Smith, 1981; Biermann, 1978; Jouannaud & Kodratoff, 1980; Smith, 1980; Pettorossi, 1980]). O resultado final de tanto aprendizado é um programa de computador, em uma linguagem pré-estabelecida, destinada para máquinas antes do "consumo" humano. Por exemplo, o método de "modelo de inferência" por Shapiro(1981), na construção de um programa PROLOG caracterizando uma série de fatos matemáticos.

Anos recentes tem testemunhado o desenvolvimento de um número de sistemas de aprendizado indutivo orientado a tarefa que tem demonstrado uma impressionante performance em seus domínios de aplicação. A maior deficiência, quase sempre, persiste nas pesquisas nesta área. Em muitos sistemas faltam generalidade e extensibilidade. Os princípios teóricos sobre os quais eles trabalham são raramente bem explanados. A falta de uma terminologia comum e uma adequada teoria formal cria dificuldades para comparação de diferentes métodos de aprendizagem.

Nas próximas seções, formularemos fundamentos lógicos de aprendizado indutivo, definindo vários tipos de aprendizado, mostrando regras de inferência para generalização de descrições de conceitos e finalmente descreveremos um método geral, chamado STAR, para o aprendizado estrutural de descrições através de exemplos. Para melhorar a leitura deste capítulo, a tabela abaixo apresenta uma listagem dos símbolos usados, bem como uma pequena explanação sobre cada um deles:

 

Tabela de símbolos básicos:

 

~ -- negação

& -- conjunção (produto lógico)

V -- disjunção (soma lógica)

Þ -- implicação

Û -- equivalência lógica

« -- termo reescrito

-\ -- exceção (diferença simétrica)

F -- uma série de fatos ( formalmente, um predicado

que é verdade para todos os fatos)

H -- uma hipótese (uma afirmação indutiva)

|> -- especialização

|< -- generalização

|= -- reformulação

$ vi -- quantificador existencial sobre vi

$ (I)vi -- quantificador numérico sobre vi (I é uma série de inteiros)

" vi -- quantificador universal sobre vi

Di -- uma descrição de um conceito

Ki -- um predicado afirmando o nome de um conceito

(uma classe)

::> -- uma implicação ligando a descrição de um

conceito com o nome do conceito

ei -- um evento ( uma descrição de um objeto ou situação)

Ei -- um predicado que é verdade apenas para alguns

exemplos de um conceito Ki

xi -- um atributo (argumento do descritor zero ou um)

LEF -- uma evolução lexicográfica funcional

DOM(p) -- o domínio do descritor p

 

 

Tipos de aprendizado indutivo

 

Paradigma indutivo

 

Como mencionado anteriormente, aprendizado indutivo é um processo de aquisição de conhecimento pela extração de inferências indutivas de um professor ou fatos providos pelo ambiente. Esta é uma das mais comuns formas de aprendizado, tendo porém uma fraqueza: exceto para casos especiais, a aquisição de conhecimento não pode, em princípio, ser totalmente validada. Este apuro, observado pelo filósofo escocês David Hume, séc. 18, é devido ao fato de que afirmações adquiridas indutivamente são hipóteses com um infinito potencial de conseqüências, enquanto apenas um número finito de testes confirmados podem ser executados.

Alguns sistemas de inferência indutiva, que já tem sucesso, vem sendo construído e um corpo de conhecimento está imergindo sobre a natureza destas inferências. O restante deste capítulo irá analisar a base lógica para inferência indutiva, apresentando várias regras de generalização, que podem ser vistas como regras de inferência indutiva.

Em contraste a dedução, as premissas da indução são fatos específicos a axiomas gerais. A meta de inferência é formular afirmações gerais que esclareçam os fatos fornecidos e sejam hábeis para produzir novos fatos. Em outras palavras, inferência indutiva atenta para obter uma completa e correta descrição de um fenômeno ou parte dele. Como mencionado anteriormente, dos dois aspectos de inferência indutiva - a geração de hipóteses plausíveis e sua validação ( a estabilidade de seu estado verdade) - apenas o primeiro é de primário interesse para as pesquisas de aprendizado indutivo. O problema de validação das hipóteses, um assunto de vários inquéritos filosóficos (por exemplo, [Carnap, 1962]), é considerado de menor importância, porque é assumido que as hipóteses geradas são julgadas por especialistas humanos, e testadas por métodos conhecidos de inferência dedutiva e estatísticas.

Como descrito anteriormente, há diferentes métodos pelo qual um humano (ou máquina) pode adquirir conhecimento. Por exemplo, rota de aprendizado ( ou aprender por programação), aprendizado por instrução, aprendizado de exemplos providos por um professor (aquisição de conceitos) e aprendizado pela observação do ambiente e suas descobertas.

Através de todos estes caminhos, com exceção do primeiro, todos envolvem uma porção de inferência indutiva, e nos dois últimos, isto é, aprender de exemplos e por observação, esta inferência é a operação central do processo. Estas duas formas são consideradas como as maiores formas de aprendizado indutivo. Em ordem de explanação, vamos formular um paradigma geral para inferência indutiva.

 

Tomemos:

 

Procuramos:

 

 

Uma hipótese H tautologicamente implica um fato F se F é uma conseqüência de H, isto é, se a expressão H => F é verdade para todas as interpretações ("=>" denota implicação lógica). Isto é expressado da seguinte forma:

 

H |> F (lê-se: H especializado por F) (1)

Ou

F |< H (lê-se: F generalizado por H) (2)

 

Os símbolos |> e |< são chamados símbolos de especialização e generalização, respectivamente. Se HÞ F é verdade, e H é verdade, então por modus ponens, F deverá ser verdade. Derivar F de H (inferência dedutiva), será, portanto, com preservação da verdade. Em contraste, derivar H de F ( inferência indutiva) será com não preservação, ou seja com falsa preservação da verdade.

A condição de que H levemente implica F quer dizer que fatos F não são certos, mas apenas plausíveis ou parciais conseqüências de H. Pela concordância da leve implicação, este paradigma inclui métodos para geração de hipóteses "softs", que permanecem apenas probabilisticamente, e hipóteses parciais, que narram alguns mas não todos os fatos (exemplo, hipóteses representando modelos dominantes ou características de dados inconsistentes). Nós iremos limitar nossa atenção para hipóteses que tautologicamente implicam fatos.

Para algumas séries de fatos fornecidos, um potencial infinito de hipóteses que impliquem estes fatos podem ser geradas. Conhecimento prévio é então necessário para providenciar as restrições e o critério de preferência para redução da infinita escolha de uma hipótese ou umas poucas preferidas.

Um caminho típico de definição de algum critério é especificar as propriedades preferidas das hipóteses - por exemplo, para requerer que as hipóteses sejam mais curtas ou descrições mais econômicas, consistentes com todos os fatos (como, por exemplo, [Michalski, 1973]). Alguns critérios como uma "biased-choice" (escolha tendenciosa) são necessários quando a linguagem de descrição é completa, isto é, hábil para expressar qualquer hipótese possível. Uma alternativa é usar um critério de linguagem tendenciosa [Mitchell, 1978], restringindo a linguagem de descrição em que as hipóteses são expressadas ( isto é, usando uma linguagem de descrição incompleta). Em muitos métodos, o conhecimento anterior não é um estado explícito, os autores retiram as suposições implícitas com algum propósito.

 

Aquisição de conceito versus generalização descritiva

Como mencionado anteriormente, nós podemos distinguir dois grandes tipos de aprendizado indutivo: aprendizado de exemplos (aquisição de conceitos) e aprendizado por observação (generalização descritiva). Em aquisição de conceito, as características observadas são caracterizações de alguns objetos (situações, processos, etc.) pré- classificadas por um professor em uma ou mais classes (conceitos). A hipótese induzida pode ser vista como uma regra de reconhecimento de conceito, tal que se um objeto satisfaz esta regra, então ele representa o conceito. Por exemplo, uma regra de reconhecimento do conceito "filósofo" poderia ser:

"Uma pessoa que procura sabedoria e ganho de conhecimento pela observação da realidade e por alto disciplina intelectual é um filósofo".

Em generalização descritiva a meta é determinar uma descrição geral (uma lei, uma teoria) que caracteriza uma coleção de observações. Por exemplo, observando que os filósofos Aristóteles, Platão, e Sócrates são Gregos, mas que Spencer é britânico, uma possível conclusão poderia ser:

"Muitos filósofos são Gregos"

Então, em contraste com aquisição de conceitos que produz descrições de objetos classificados em classes sobre a base das propriedades dos objetos, generalização descritiva especifica propriedades dos objetos para uma certa classe. Aqui estão alguns exemplos das duas categorias:

 

    1. Aquisição de conceitos

 

 

2. Generalização descritiva

 

Esta explanação é concernida primariamente com problemas de aquisição de conceitos. Neste caso, a série de características observadas F pode ser vista como uma coleção de implicações:

 

F : { eik ::> Ki }, iÎ I (3)

 

Onde eik (um training evento) denota a descrição do Kth exemplo do conceito (classe) afirmada pelo predicado Ki (classe Ki) e I é um conjunto indexando classes Ki. É assumido aqui que qualquer evento fornecido representa apenas um conceito. O símbolo ::> é usado e será usado de agora em diante , para denotar a implicação ligando a descrição de um conceito com um predicado de mesmo nome ( em ordem para distinguir esta implicação entre descrições arbitrárias). A afirmação indutiva H pode ser caracterizada como um conjunto de regras de reconhecimento de conceitos:

 

H : { Di ::> Ki}, i Î I (4)

 

onde Di é uma descrição do conceito de uma classe Ki, que é, uma expressão de condições, tal que quando elas são satisfeitas por um objeto, o objeto é considerado uma instância da classe Ki.

De acordo com a definição da afirmação indutiva, nós teremos:

 

H |> F (5)

 

Pela substituição (3) e (4) para F e H, respectivamente, em (5), e fazendo as apropriadas transformações:

 

" i Î I ( Ei Þ Di) (6)

e

" i, j Î I ( Di Þ ~Ej), se j ¹ i (7)

onde Ei, i Î I, é uma descrição satisfeita por todos os eventos da classe Ki.

A expressão (6) é chamada de "condição de completeza", e (7) é chamada de "condição de consistência". Estas duas condições devem ser satisfeitas para uma afirmação indutiva ser aceita como uma regra de reconhecimento de conceito. O estado da condição de completeza diz que todos os eventos de alguma classe devem satisfazer a descrição Di de alguma classe. O estado da condição de consistência diz que se um evento satisfaz a descrição de alguma classe, então ele não pode ser membro de alguma outra classe. Em aprendizado de conceito de exemplos e contra exemplos, o último constitui a outra classe. As condições de completeza e consistência providenciam o fundamento lógico de algoritmos de aquisição de conceitos por exemplos.

 

Características versus descrições discriminantes

 

As condições de completeza e consistência permite-nos claramente expor a distinção entre as características previamente mencionadas e as descrições discriminantes. Uma descrição de características de uma classe de objetos é uma expressão que satisfaz a condição de completeza ou é o produto lógico de algumas expressões. Esta é tipicamente uma conjunção de algumas propriedades comuns de todos os objetos da classe. Do ponto de vista de aplicação, as mais interessantes são as descrições de características máximas (máxima generalização conjuntiva) que são os mais específicos produtos lógicos caracterizando todos os objetos de uma classe fornecida, usando termos de uma linguagem também fornecida. Algumas descrições são intencionadas para discriminar a classe em questão de outras possíveis classes.

Uma descrição discriminante é uma expressão que satisfaz as condições de completeza e consistência , ou é a disjunção lógica de algumas expressões. Ela especifica um ou mais caminhos para distinguir uma classe fornecida de um fixo número de outras classes. As mais interessantes são as descrições discriminantes mínimas que são curtas expressões (isto é , tem o mínimo número de descritores) distinguindo todos os objetos de uma classe de objetos fornecidos de todas as outras classes.

 

Conceito de aprendizado simples versus múltiplo

 

Isto é instrutivo para distinguir entre aprender um simples conceito, e aprender uma coleção de conceitos. Em aprendizado de um conceito simples, podemos distinguir dois casos: quando as características observadas são apenas exemplos de um conceito a ser aprendido (aprender de apenas exemplos positivos ) e quando eles são exemplos e contra exemplos de um conceito ( aprender de exemplos positivos e negativos).

No primeiro caso, devido a falta de contra exemplos, a condição de consistência não é aplicada, e não há um limite para que a descrição Di (onde, i=1) possa ser generalizada. Um caminho para impôr um limite é especificar restrições sobre a forma e propriedades de uma descrição procurada. Por exemplo, requerer descrições máximas de características, isto é, que a longa declaração conjuntiva satisfaça a condição de completeza (por exemplo, [Vere, 1975; Hayes-Roth & McDermott, 1978]). Outro caminho é requerer que a descrição não exceda uma medida de generalidade fornecida, por exemplo, pela razão do número de todos os eventos distintos com os que potencialmente satisfizeram a descrição do número de instâncias [Stepp, 1978].

No segundo caso, quando o professor além disso providencia contra exemplos do conceito fornecido, o processo de aprendizado é consideravelmente simplificado. Estes contra exemplos podem ser vistos como representações de uma classe diferente, e a condição de consistência providencia um limite óbvio da extensão que uma hipótese pode ser generalizada. Os mais usados contra exemplos são os chamados "near misses", que apenas diferem dos exemplos positivos levemente [Winston, 1970, 1977].

Em múltiplo conceito de aprendizado , podemos distinguir dois casos: quando as descrições Di de diferentes classes são requeridas para ser mutuamente disjuntas, isto é, um evento não pode satisfazer mais que uma descrição; e quando eles são sobrepostos. Em uma generalização sobreposta, um evento pode satisfazer mais que uma descrição. Em algumas situações isto é desejável. Por exemplo, se um paciente tem duas doenças, os sintomas dele deverão satisfazer as descrições de ambas as doenças, e neste caso a condição de consistência não é aplicável.

Uma generalização sobreposta pode ser interpretada como um caminho que sempre indica apenas uma classe de decisão. Por exemplo, as regras de reconhecimento de conceitos, Di ::> Ki, podem ser aplicadas em uma ordem linear, e a primeira regra satisfeita gera a decisão. Neste caso, se uma descrição de conceito Di para a classe Ki contém uma condição conjuntiva A, e precede a regra para a classe Kj que contém a condição ~A, então a condição ~A é supérflua e pode ser removida. Como resultado, as regras de reconhecimento linearmente ordenadas podem ser significativamente simplificadas. Por exemplo, as regras:

 

D1 ::> K1

D2 ::> K2

D3 ::> K3

são logicamente equivalentes a:

D1 ::> K1

~D1 & D2 ::> K2

~D1 & ~D2 & D3 ::> K3

Existem alguns outros caminhos para derivar uma simples decisão de regras de sobreposição, como aquelas vistas em [Davis & Lenat, 1981].

A forma acima de múltiplo conceito de aprendizado tem sido implementado em programas indutivos AQVAL/1 [Michalski, 1973] e AQ11 [ Michalski & Larson, 1978].

 

Linguagem de descrição

 

Inclinação para a compreensibilidade

 

Em aquisição de conceito, o principal interesse é em derivação de descrições simbólicas que são orientadas a humanos, isto é, que são facilmente entendidas e facilmente usadas para criação de modelos mentais da informação que eles carregam. Uma tentativa de critério para julgar afirmações indutivas de tal ponto é providenciado pelo postulado abaixo:

O resultado da indução computacional deveria ser descrições simbólicas de entidades fornecidas, semanticamente e estruturalmente similares àquelas produzidas por especialistas humanos ao observarem algumas entidades. Componentes destas descrições deveriam ser compreensíveis como simples pedaços de informação, diretamente interpretáveis em linguagem natural, e relatados quantitativa e qualitativamente em um integrado estilo.

 

Como praticamente um guia, poderíamos assumir que os componentes das descrições ( sentenças simples, regras, rótulos sobre os nós em uma hierarquia, etc.) deveriam ser expressões que tivessem apenas poucas (isto é, menos que cinco) condições em uma conjunção, poucas condições simples em uma disjunção, maior nível de chaves, mais que uma implicação, não mais que dois quantificadores, e nenhuma recursão ( o número exato pode ser discutido, mas a principio é zero). Sentenças são retidas dentro de tais limites, substituindo nomes para apropriados sub-componentes. Alguns operadores usados em descrições deverão ter uma interpretação intuitiva simples. Conceitualmente sentenças relatadas são organizadas em estruturas de dados simples, preferivelmente a hierarquias superficiais ou listas lineares, como um frame [Minsky, 1975].

O início racional deste postulado é para assegurar que descrições geradas por inferência indutiva sejam similares com representações do conhecimento humano [ Hintzman, 1978], e então, fáceis de serem compreendidas. Este requerimento é muito importante para muitas aplicações. Por exemplo, em desenvolvimento de bases de conhecimento para sistemas especialistas, é importante que especialistas humanos possam facilmente e confiantemente verificar as afirmações indutivas e relatar-lhes sobre o seu domínio de conhecimento. Satisfazer a compreensibilidade do postulado irá facilitar a debugação ou desenvolvimento dos programas indutivos. Quando a complexidade dos problemas de indução em computadores é muito grande, a compreensibilidade dos descritores gerados irão ser um critério crucial. Esta orientação de pesquisa fita bem a tarefa de inteligência artificial enfrentada por Michie[1977] para estudar e desenvolver métodos para interface conceitual homem-máquina e refinamento de conhecimento.

 

Linguagem de afirmações

 

Uma das dificuldades de inferência indutiva é sua infinita gama de possibilidades. Isto quer dizer que quando uma afirmação indutiva é criada a respeito de alguns aspectos da realidade, não há um limite natural para o nível de detalhe em que esta realidade pode ser descrita, ou para a riqueza de formas em que as afirmações podem ser expressas. Consequentemente, quando conduzimos pesquisas nesta área, é necessário restringir muito cuidadosamente as metas e os problemas a serem resolvidos. Isto inclui definir a linguagem e o escopo das afirmações que irão ser expressas, tanto quanto o modo de inferência que irá ser usado. A linguagem de descrição deverá ser escolhida tal que características cruciais sejam facilmente codificadas enquanto informações periféricas ou irrelevantes sejam ignoradas.

Um instrutivo critério de classificação de métodos de aprendizado indutivo é também o tipo de linguagem usada para expressar as afirmações indutivas. Muitos autores usam uma forma restrita de cálculo de predicados ou notação relatada rigorosamente (por exemplo, [Plotkin, 1971; Fikes et al., 1972; Morgan, 1975; Vere, 1975; Banerji, 1980; Michalski, 1980 a; Sammut, 1981; Zagoruiko, 1981]). Alguns outros formalismos incluem árvores de decisão [Hunt et e., 1966; Quinlan, 1979], regras de produção ([Watermann, 1970; Hedrick, 1974]), redes semânticas, e frames. No seu trabalho (por exemplo, [Michalski, 1972, 1973, 1975 a, 1975b]) este autor usou um cálculo em lógica proposicional multi valorada com variáveis de tipo, chamado VL(o variable-valued logic propositional one). Mais tarde, uma extensão do cálculo de predicados, chamado VL2, foi desenvolvido e foi especialmente orientado para facilitar inferência indutiva [Michalski, 1980 a].

Aqui nós iremos usar uma versão modificada e estendida desta última linguagem, chamada de cálculo de predicado anotado (APC). O APC adiciona ao cálculo de predicados convencional formas adicionais e novos conceitos que incrementam o poder de expressão e facilitam inferências indutivas. A maior diferença entre o cálculo de predicados anotado e o cálculo de predicados convencional pode ser resumido como abaixo:

 

O conceito de anotação é mostrado com mais detalhes na próxima seção.

 

Problemas de conhecimento prévio

 

Componentes básicos

 

Como mencionado anteriormente, dado um conjunto de características observadas, é possível construir um número infinito de afirmações indutivas que implicam essas características. É então necessário o uso de algumas informações adicionais, problema de conhecimento prévio, para restringir o espaço de possibilidades de afirmações indutivas e localizar as mais desejáveis. Nesta seção nós vamos mostrar vários componentes do problema do conhecimento prévio empregados numa metodologia de aprendizado chamada STAR. Estes componentes incluem:

 

Antes de nós examinarmos estes componentes em grandes detalhes, vamos primeiro considerar o problema da escolha de descritores nos dados observados afetando as afirmações indutivas geradas.

 

Relevância dos descritores iniciais

 

Um problema fundamental do trabalho de aprendizado de máquinas indutivo é saber qual informação é provida para máquina e qual informação ela deve aprender ou produzir. Como mencionado no paradigma indutivo, o maior componente de uma entrada para o sistema aprendiz é um conjunto de características observadas. Os descritores usados naquelas afirmações são características observadas e medidas disponíveis dos objetos sobre consideração. Estes descritores são selecionados como relevantes para o trabalho de aprendizado especificado por um professor.

Determinar estes descritores é a principal parte do problema de aprendizado indutivo. Se eles capturam as propriedades essenciais dos objetos, a tarefa do processo de aprendizado é simplificar o arranjo destes descritores em expressões constituindo apropriadas expressões indutivas. Se os descritores selecionados são completamente irrelevantes para a tarefa de aprendizado ( como a cor ou tamanho da peça no xadrez é irrelevante para decidir o movimento certo), o sistema não será hábil para construir uma afirmação indutiva significativa.

Há um alcance de possibilidades intermediárias entre os dois extremos. Consequentemente, métodos de aprendizado podem ser caracterizados sobre a base de que os descritores iniciais são relevantes para o problema de aprendizado. Três casos podem ser distinguidos:

 

1. Relevância completa: neste caso todos os descritores das características observadas são assumidas como diretamente relevantes para o trabalho de aprendizado. O trabalho do sistema de aprendizado é formular uma afirmação indutiva que é uma expressão matemática ou lógica de algumas formas gerais que devidamente relata estes descritores (por exemplo, uma regressão polinomial).

 

2.Relevância parcial: as características observadas podem conter um grande número de descritores irrelevantes ou redundantes. Alguns dos descritores, quase sempre, são relevantes. O trabalho do sistema de aprendizado é selecionar os mais relevantes descritores e construir afirmações indutivas apropriadas deles.

 

3.Relevância indireta: as características observadas podem conter descritores não diretamente relevantes. De qualquer maneira, entre os descritores iniciais há alguns que podem ser usados para construir descritores derivados que são diretamente relevantes. O trabalho do sistema de aprendizado é construir aqueles descritores derivados e formular afirmações indutivas apropriadas. Uma forma simples em que esse caso ocorre é, por exemplo, quando um descritor relevante é o volume de um objeto, mas as características observadas contém apenas a informação sobre as dimensões do objeto ( e vários fatos irrelevantes).

 

Os três casos representam problemas que colocam progressivamente menos demanda de relevância dos descritores iniciais ( isto é, que requerem menos trabalho de uma pessoa definindo o problema) e mais demanda dos sistema de aprendizado. Trabalhos iniciais em sistemas de controle adaptativo e formação de conceitos representam o caso 1. Pesquisas mais recentes tem sido repartidas com o caso 2, que é endereçado em seletivo aprendizado indutivo. Um método de tal aprendizado tem eficientes mecanismos para determinar combinações de descritores que são relevantes e suficientes para o trabalho de aprendizado. Lógica formal providencia tais mecanismos, e portanto ele vem a ser o maior formalismo para métodos seletivos.

Um exemplo de um método de aprendizado seletivo é implementado em AQ11 [Michalski & Larson, 1978] que indutivamente determina regras de diagnósticos de doenças da soja para o sistema PLANT/DS, mencionada na introdução. Um tipo diferente de método seletivo foi implementado no programa ID3 que determina uma árvore de decisão para classificação de um largo número de eventos. Uma comparação entre estes dois programas é descrito por O'Rorke[ 1982].

O caso 3 representa o trabalho de aprendizado indutivo construtivo. Aqui, um método deve ser capaz de formular novos descritores (isto é, novos conceitos, novas variáveis), da estimativa de relevância deles para o trabalho de aprendizado e do uso deles para construção de afirmações indutivas. O programa de plano geral INDUCE para descrições de aprendizado estrutural de exemplos incorpora algumas técnicas de generalização construtiva [Larson, 1977; Michalski, 1980 a].

 

Anotações de descritores

 

Uma anotação de um descritor (isto é, de um predicado, variável, ou função) é um depósito de informação prévia sobre este descritor para o problema de aprendizado sobre consideração. Isto pode incluir:

 

Vamos considerar alguns destes componentes de anotação em mais detalhes.

 

O domínio e o tipo de um descritor

Dado um problema específico, é usualmente possível especificar um conjunto de valores que cada descritor pode adotar caracterizando vários objetos de uma população sobre consideração. Como um conjunto entendemos o domínio (ou o value conjunto) de um descritor. O domínio é usado para restringir a extensão para qual um descritor pode ser generalizado.

Outra importante informação para conduzir o processo de generalização é concernido com a estrutura do domínio, isto é, com a relação existente entre os elementos do domínio. Para descritores numéricos, alguns relacionamentos são especificados por uma escala de medida. Dependendo da estrutura do domínio do descritor, nós podemos distinguir três tipos básicos de descritores:

 

Descritores estruturados podem ser, além disso, subdivididos em descritores estruturados ordenados e não ordenados.

Algumas vezes, descritores podem ser organizados em uma hierarquia generalizada. Por exemplo, como já mencionado, os descritores "comprimento", "largura", e "profundidade" pertencem a classe "dimensões". Informações sobre o tipo de um descritor são tão úteis como determinar as operações aplicáveis para um descritor.

 

Restrições do espaço de descrição

 

Para um dado problema de indução podem existir uma variedade de restrições sobre o espaço de descrições de conceito aceitáveis, devido as propriedades e relações entre os descritores. Aqui estão alguns poucos exemplos destes relacionamentos:

 

 

[estado(folha da planta) = normal] Þ [descoloração(folha da planta) = NA]

 

onde NA é um valor especial que quer dizer não aplicável.

 

 

" P1,P2 e P3, (precede(P1,P2) & precede(P2,P3)) Þ precede(P1,P3).

 

 " P, comprimento(P) >= largura(P)

 Além disso, descritores podem ser relatados por equações conhecidas. Por exemplo, a área de um retângulo é o produto de sua largura pela sua altura:

 

" P, ([formato(P) = retângulo] Þ [área(P) = altura(P) X largura(P)]

 

Operador infixo "X" é usado para simplificar a notação do termo:

multiplicar(largura(P), altura(P)).

 

A forma de afirmações observacionais e indutivas

A forma básica de afirmações da metodologia STAR são c- expressões, definidas como afirmações conjuntivas:

 

< quantificador>< conjunção das afirmações relacionais> (8)

 

onde <quantificador> posiciona-se para zero ou mais quantificadores, e <afirmações relacionais> são predicados em uma forma especial. Abaixo temos um exemplo de uma c- expressão:

 

$ P0, P1, P2 e P3 ([contem(P0, P1, P2, P3)][ topo(P1 & P2,P3)][comprimento(P1) = 3..5][largura(P1)> largura(P2)][cor(P1) = vermelho V azul][forma (P1 & P2 & P3) = caixa]

 

que pode ser parafraseado em português:

 

"Um objeto P0 contém partes P1,P2 e P3 e apenas estas partes. As partes P1& P2 estão sobre a parte P3, comprimento de P1 está entre 3 e 5, a largura de P1 é maior que a largura de P2, a cor de P1 é vermelho ou azul, e a forma de todas as partes é de caixa."

 

Um caso especial é uma a-expressão (uma expressão atômica), em que não há disjunção interna.

Note que devido ao uso de disjunção interna uma c- expressão representa um conceito mais geral que uma conjunção universalmente quantificada de predicados, usado em regras de produção típicas.

 Progressivamente formas mais complexas de expressão são descritas abaixo:

 [L = ai] Þ Exp i, i = 1,2,3,…

 onde ai são simples elementos ou subconjuntos disjuntos

de elementos do domínio de um descritor L, e Exp i

são c-expressões.

Uma expressão case descreve uma classe de objetos

pela quebra deles em casos separados, cada um

representado por um valor diferente(s) de um certo

descritor.

 

 

C & (C1 Þ C2) (9)

 

onde C, C1 e C2 são c-expressões.

 

Esta forma de descrição é muito usada quando a ocorrência de algumas propriedades (definidas em C2) dependem da ocorrência de algumas outras propriedades (definidas em C1). Regras de produção típicas usadas em sistemas especialistas são um caso especial da expressão (9), onde C é omitido e operadores internos lógicos não são usados. Quando (C1 Þ C2) é omitido, então a expressão condicional vem a ser uma c-expressão.

 

 

D1 -\ D2

 

onde D1 e D2 são d-expressões. Esta expressão é equivalente a

 

(~D2 Þ D1) & ( D2 Þ ~D1).

 

Afirmações observadas são formuladas como uma série de regras:

 

{a-expressoes ::> Kj} (10)

 

Afirmações indutivas são expressadas como uma serie de regras:

{ Exp ::> c- expressões} (11)

 

onde Exp é uma c- expressão ou uma das expressões mais complexas descritas acima. É assumido que o lado esquerdo e o lado direito de (11) satisfazem o princípio da compreensibilidade descrito anteriormente.

 

O critério de preferência

Em detrimento às restrições impostas pelos componentes do conhecimento prévio vistos, o número de afirmações indutivas consistentes com as características observadas deverá ainda ser ilimitada. O problema então surge na escolha das afirmações indutivas mais desejadas. Em tal escolha, um ponto que devemos levar em conta são os aspectos de um particular problema de aprendizado indutivo, portanto a definição de um critério de preferência para selecionar uma hipótese é uma parte do problema de conhecimento prévio. Tipicamente, as afirmações indutivas são escolhidas em base de alguns critérios simplificados (como em [Kemeni, 1953; Post, 1960].

No contexto de descoberta científica, o filósofo Karl Popper [1968] foi advogado construindo hipóteses que são simples e fáceis de refutar. Generalizando algumas hipóteses e conduzindo experimentos visados ao refute delas, ele argumenta que foi a melhor chance de finalmente formular hipóteses verdadeiras. Ao ordenar o uso deste critério para automatizar inferência indutiva, é necessário definir sua formalidade. Isto, quase sempre, não é fácil porque aqui não há nenhuma medida universal de hipóteses simples e refutáveis.

Uma possível listagem de medidas mais específicas para evolução da "qualidade" das afirmações indutivas pode ser:

 

 

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, t 1),(c2, t 2) …

 

onde ci é um critério elementar selecionado de um "menu" disponível, e t i é uma tolerância início para o critério ci(t i Î [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 t 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 t 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 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:

 

 

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.

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Þ F é equivalente para ~F Þ ~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 Þ 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 Þ 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 "objetos redondos e marrons são bolas" pode ser generalizado para "objetos redondos são bolas". 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:

 

P(K) |< P(K) & Q(K) (16)

 

Se P(K) for "bolas são redondas" e Q(K) for "bolas são marrons", então de acordo com a regra (16), a afirmação "bolas são redondas e marrons" é uma generalização da afirmação "bolas são redondas". Nós podemos ver que a notação "o número de objetos satisfazendo a descrição" 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 Î I |< D ::> K (17)

 

Se um evento (uma descrição simbólica de um objeto ou situação) satisfaz alguma descrição Di, i Î 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.

 

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.

 

 

CTX & S ::> K |< CTX ::> K (18)

 

onde S é um predicado ou expressão lógica arbitrário.

 

Esta é uma das regras mais comumente usadas para generalização de informação.

 

 

CTX1 ::> K |< CTX1 V CTX2 ::> K (19)

 

Uma descrição de conceito pode ser generalizada pela adição, através do uso de disjunção lógica, de uma alternativa para ela. Uma forma especialmente usual desta regra é quando a alternativa é adicionada pela extensão do escopo de valores possíveis de um específico descritor. Uma operação pode ser expressa simplesmente pelo uso de um operador disjunção do cálculo de predicados anotado. Por exemplo, suponha que a descrição do conceito é generalizada para alguns objetos serem não apenas vermelhos mas também azuis. Isto pode ser expressado da seguinte forma:

 

CTX & [color = red] ::> K |< CTX& [color = red V blue] ::> K (20)

 

( formas entre colchetes são descritores; as expressões na direita da igualdade são chamadas referências)

 

Devido a importância deste caso especial, ele irá ser apresentado como uma regra geral separada.

 

 CTX & [L = R1] ::> K |< CTX & [L = R2] ::> K (21)

onde R1 Í R2 Í DOM (L) e DOM(L) denota o domínio de L.

 

Nesta regra, L é um termo, e R1 e R2 (referências) são disjunções internas dos valores de L. Referências R1 e R2 podem ser interpretadas como conjuntos de valores que o descritor L pode ter para satisfazer a descrição do conceito.

A regra afirma que uma descrição de conceito pode ser generalizada pelo aumento da referência do descritor (R2 Ê R1). Os elementos adicionados para R2 devem, quase sempre, serem do domínio de L.

Se R2 é estendida para ser daquele domínio, isto é, R2 = DOM(L),então o seletor [L = DOM(L)] é sempre verdade, e portanto pode ser removido. Neste caso, a regra de referência estendida vem a ser a regra de condição de descida. Há dois outros casos especiais de regra de referência estendida. Eles levam em consideração o tipo de descritor L [definido pela estrutura do DOM(L)]. Eles são apresentados como regras separadas abaixo.

 

 

CTX & [L = a] ::> K |

|< CTX & [L = a..b] ::> K (22)

CTX & [L = b] ::> K |

 

onde L é um descritor linear, e a e b são alguns valores específicos do descritor L. As duas premissas são assumidas serem conectadas por uma conjunção lógica (esta convenção trabalha para a permanência das regras muito bem).

A regra afirma que se duas descrições de alguma classe (as premissas da regra) diferem em valores de apenas um descritor linear, então o descritor pode ser substituído por uma simples descrição em que a referência do descritor é o intervalo ligando estes dois valores.

Para ilustrar esta regra, consideraremos como objetos dois estados de uma máquina, e K como uma classe de estados normais. A regra diz que se uma máquina está em um estado normal para duas temperaturas, ditas a e b, então a hipótese é que todos os estados em que a temperatura cai dentro do intervalo [a,b] são também normais.

Então, esta regra não é apenas uma regra de generalização logicamente válida, mas expressa alguns aspectos que são plausíveis:

 

CTX & [L=a] ::> K |

CTX & [L=b] ::> K |

(uma ou mais | < CTX & [L=s] ::> K (23)

 afirmações ) |

CTX & [L=i] ::> K |

 

onde L é um descritor estruturado, e s representa o nó origem que descende os nós a,b,c… e i, no domínio da árvore de generalização de L.

A regra é aplicável apenas para descrições envolvendo descritores estruturados, e é usada em várias formas, por exemplo [Winston, 1977; Hedrick, 1974; Lenat, 1976]. O exemplo abaixo ilustra esta regra:

$ P, CTX & [formato(P) = triângulo] ::> K |

$ P, CTX & [formato(P) = retângulo] ::> K | < $ P, CTX & [formato(P) = polígono] ::> K

 

Passando esta regra para o português: se um objeto da classe K é triangular e outro objeto desta classe é retangular, então a regra generaliza a afirmação que objetos da classe K são poligonais.

 

A regra retornar constantes em variáveis: esta regra é melhor para o caso de generalização descritiva:

 

F(a) |

(uma ou

mais afirmações)

F(b) |

| < " v, f[v] (24)

F(i) |

 

onde F[v] existe para algumas descrições (fórmulas) dependendo da variável v, e a,b…são constantes.

Se algumas descrições F[v] tem para v uma constante a ou constante b, então a regra generaliza estas observações em uma afirmação que F[v] contém para todo valor de v. Esta é a regra usada mais freqüentemente em métodos de inferência indutiva empregando cálculo de predicados:

Uma regra correspondente para aquisição de conceito é:

F[a] & F[b] &… ::> K |< $ v, F[v] ::> K (25)

 

Para ilustrar esta versão, assuma que a,b, são partes de um objeto da classe K que tem a propriedade F. A regra 25 generaliza estes fatos em uma afirmação que diz que se alguma das partes de um objeto tem a propriedade F então o objeto pertence a classe K.

F1 & F2 ::> K |< F1 V F2 ::> K (26)

onde F1 e F2 são descrições arbitrárias.

Uma descrição de conceito pode ser generalizada pela substituição do operador conjunção pelo operador disjunção.

 

 

" v, F[x] ::> K |< $ v, F[v] ::> K (27)

 

Esta regra pode ser vista como uma generalização da regra (26). Usando o conceito de quantificador numérico, esta regra pode ser expressada em um caminho ainda mais geral:

 

$ (I1)v, F[v] ::> K |< $ (I2)v, F[v] ::> K (28)

 

onde I1,I2 são os domínios dos quantificadores (conjuntos de inteiros) satisfazendo a relação I1Í I2.

Por exemplo, a afirmação "se um objeto tem duas partes (I1={2}) com propriedade F, então ele pertence a classe K" e pode ser generalizada pela regra (28) para a afirmação "se um objeto tem duas ou mais partes (I2={2,3,4…}) com propriedade F então ele pertence a classe K".

 

 

(i) Aplicada para aquisição de conceito:

A regra de inferência indutiva, chamada de o princípio da resolução, largamente usada em prova automática de teoremas, pode ser adotada como uma regra de generalização para aquisição de conceito. Na forma proposicional, o princípio da resolução pode ser expressado como:

(P Þ F1) & (~P Þ F2) |> F1V F2 (29)

onde P é um predicado e F1 e F2 são fórmulas arbitrárias. Pela interpretação de que ambos os lados de (29) são descrições de conceitos, e fazendo as transformações apropriadas, podemos obter:

P&F1 ::> K |

| < F1 V F2 ::> K (30)

~P&F2 ::> K |

 

Para ilustrar esta regra, assuma que L é o conjunto de situações quando John vai ao cinema. Suponha que tem sido observado que ele vai ao cinema quando ele tem acompanhante (P) e o filme tem alta audiência (F1), ou quando ele não tem acompanhante (~P), mas tem bastante tempo (F2). A regra (30) generaliza estas duas observações para uma afirmação "John vai ao cinema quando o filme tem alta audiência ou quando ele tem bastante tempo."

(ii) Aplicada para generalização descritiva:

Pela aplicação de equivalência lógica (Q |> P) Û (~P |> ~Q) ( a lei da contraposição) para a expressão (29), invertendo a regra obtida e substituindo os literais negativos por positivos, nós obtemos:

 

P&F1 V ~P&F2 |< F1 & F2 (31)

Esta versão foi formulada por Morgan (1975).

Ambas versões, (i) e (ii), podem ser generalizadas pela aplicação do completo princípio da resolução que usa predicados com argumentos, e o algoritmo de unificação para unificar estes argumentos (exemplo, Chang & Lee, 1973]).

 

 

CTX1 & [L = R1] ::> K |

|< [L¹ R2] ::> K (32)

CTX2 & [L = R2] ::> ~K |

 

onde conjuntos R1 e R2 são assumidos como disjuntos.

Dada a descrição de um objeto pertencente a classe K (um exemplo positivo), e uma descrição de um objeto não pertencente a esta classe (um exemplo negativo), a regra produz uma afirmação consistente mais geral com estas duas descrições. Esta é uma afirmação que classifica um objeto como pertencente a classe K se o descritor L não tem nenhum valor do conjunto R2, ignorando assim o contexto descrições CTX1 e CTX2. Esta regra é a regra básica para o aprendizado de descrições de exemplos discriminantes usado no programa previamente citado AQ11[Michalski & Larson, 1978]. Várias modificações desta regra podem ser obtidas pela substituição da referência R2 na afirmação de saída por alguns conjuntos que não tenham interseção com R1.

 

Regras de generalização construtiva

 

Regras de generalização construtiva geram afirmações que usam descritores não presentes nas afirmações originais observadas. Isto quer dizer que a regra executa uma transformação do espaço original de representação. Abaixo temos uma regra construtiva geral que realiza transformações pela aplicação de conhecimento de relacionamentos entre diferentes conceitos. É assumido que esta relação é conhecida pelo sistema de aprendizado como conhecimento anterior, como um conceito previamente aprendido, ou que este é computado de acordo com a definição de procedimento do usuário:

CTX & F1 ::> K |

|< CTX & F2 ::> K (33)

F1 Þ F2 |

 

A regra diz que se uma descrição de conceito contém uma parte F1 (um conceito, uma subdescrição,…) que é conhecida para implicar alguns outros conceitos F2, então uma descrição mais geral é obtida pela substituição de F1 por F2. Por exemplo, suponha que um sistema de aprendizado disse que se um objeto é preto, largo e longo, então ele pertence a classe K (por exemplo, um quadro-negro). Isto pode ser expressado em cálculo de predicado anotado:

$ P, [color(P) = preto][largura(P) & comprimento(P) = grande] ::> K

 

suponha que o aprendiz sabe que:

" P, ([largura(P) & comprimento(P) = grande] Þ [área(P) = grande])

Então a regra (33) produz a generalização:

$ P, [color(P) = preto][área(P) =grande] ::> K

 

Um outro exemplo, suponha que ao sistema é dado uma descrição de um objeto classificado como um arco. Esta descrição diz que uma barra horizontal está no topo de dois objetos iguais separados, B1 e B2, tendo certa cor, largura, formato, etc. Suponha agora novas características de B1 e B2 nesta descrição satisfazendo um conceito previamente aprendido de um bloco. Então a regra (33) gera a afirmação que um arco é uma barra no topo de dois blocos separados. Esta regra é a base para um conceito interativo de sistema de aprendizado desenvolvido por Sammut[1981].

Regras de generalização construtiva específicas podem ser obtidas de (33) invocando novos descritores de procedimentos computacionais F2 como funções de início ou descritores previamente derivados (contidos em F1). Abaixo estão alguns exemplos de regras de generalização de novos descritores.

 

(i)regras de contagem de argumentos:

1.A regra CQ (contagem quantificada de variáveis)- Se um conceito está na forma:

$ v1,v2…,vk, F[v1,v2…,vk]

 

então a regra gera descritores "#v-COND" representando o número de vi's que satisfazem alguma condição COND. Esta condição expressa propriedades selecionadas de vi's especificadas na descrição do conceito. Como muitos COND's podem usualmente serem formulados, a regra diminui o sistema para gerar um largo número de descritores.

Por exemplo, se o COND é "[atributo1(vi) = R]", então o descritor gerado irá ser "#vi-atributo-R" contando o número de vi's que satisfazem a condição. Se o atributo1 é, por instanciação, comprimento, e R é [2…4], então o descritor derivado é "#vi-comprimento-2…4" ( isto é, ele mede o número de vi's que estão entre 2 e 4, inclusive).

2. A regra CA (contagem de argumentos de um predicado)- Se um descritor em uma descrição é uma relação com vários argumentos, REL(v1,v2…), a regra gera descritores "#v-COND", medindo o número de argumentos em REL que satisfazem alguma condição COND. Como visto, muitos descritores podem ser gerados, cada um com diferente COND.

A anotação de um descritor provê informação sobre estas propriedades. Tal propriedade poder ser que um descritor seja , por instância, uma relação transitiva, como uma relação "acima", "dentro", "lado esquerdo", e "na frente de". Por exemplo, se a relação é "acomoda(A,B1,B2…)", dizendo que o objeto A acomoda os objetos B1, B2…, e COND é "largo e vermelho", então o descritor derivado "B-largo-vermelho-A-acomoda" mede o número de Bi-s contidos em A que são largos e vermelhos.

(ii)A regra de geração de propriedades em cadeia- Se os argumentos de diferentes ocorrências de uma relação transitiva em uma descrição de conceito forma uma cadeia (isto é, forma uma seqüência de objetos consecutivos ordenados por uma relação), a regra gera descritores caracterizando alguns objetos específicos na cadeia. Tais objetos podem ser:

 

LST-objeto: o "primeiro objeto", ou o objeto do começo da cadeia (por exemplo, o objeto base no caso da relação "acima").

MST-objeto: o objeto é o último da cadeia (por exemplo, o objeto topo).

MID-objeto: o objeto está no meio da cadeia.

Nth-objeto: o objeto está na posição Nth da cadeia (começando do LST-objeto).

 

Depois de identificar estes objetos, a regra investiga todas as propriedades conhecidas deles (como especificado nas características observadas) em ordem para determinar novos descritores potencialmente relevantes. A regra também gera um descritor caracterizando a cadeia, nomeando:

REL-cadeia-comprimento: o comprimento da cadeia definido pela relação REL.

 

Por exemplo, se o REL é "no-topo", então o descritor no-topo-cadeia-comprimento irá especificar a altura da pilha de objetos. Quando um novo descritor é gerado e adotado, uma anotação para ele é também gerada e preenchida fora, como em Lenat[1976]. Esta regra pode ser estendida para uma relação de ordem parcial. Em tais casos elas vem a ser a regra de "procura extrema de uma ordem parcial".

 

(iii)A regra de detecção de descritores interdependentes- suponha que dado um conjunto de objetos exemplificando algum conceito, e que descritores de atributos são usados para caracterizar estes objetos. Tais descritores especificam apenas valores de atributos de objetos; eles não caracterizam estrutura dos objetos. Suponha que os valores de um descritor linear x tome todos os eventos e ordene-os em ordem crescente. Se os valores 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; 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 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…Pm 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,…), 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 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:

    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.
    7.  

      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 & 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

       

      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:

      1. 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,t 1),(poscov, t 2)> (35)

onde negcov e poscov são números de exemplos negativos e positivos, respectivamente, abrigado por uma expressão em star, e t 1 e t 2 são tolerâncias.

O LEF1 minimiza o negcov (pela maximização de -negcov) e maximiza poscov.

  1. 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:
      1. regra de generalização construtiva.
      2. As heurísticas específicas do problema definidas no conhecimento prévio.
      3. As definições dos conceitos previamente aprendidos (para determinar se partes de e satisfazem alguns conceitos conhecidos).
  2. Cada novo seletor é inserido em um apropriado lugar da lista PS, de acordo com o critério de preferência LEF1. O tamanho de PS é guardado dentro do limite definido pelo parâmetro m.
  3. 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.
  4. 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.
  5.  

  6. 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.
  7. 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).

 

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; Dietterich, 1978; Michalski, 1980 a; 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, descritores e, geralmente, várias transformações multi-níveis do espaço inicial de descrição (isto é, o problema de aprendizado indutivo construtivo) tem sido abrangidos apenas superficialmente.

 

Referências:

"Readings in Knowledge acquisition and learning", Bruce G. Buchanan e David C. Wilkins, 1993 by Morgan Kaufmann Publishers, Inc.