Existem melhorias no algoritmo de Dana Angluin para aprender conjuntos regulares

Em seu artigo seminal de 1987, Dana Angluin apresenta um algoritmo polinomial de tempo para aprender um DFA a partir de consultas de membros e pesquisas de teoria (contra-exemplos a um DFA proposto).

Ela mostra que, se você está tentando aprender um DFA mínimo com estados, e seu maior exemplo de comprimento é m , é necessário fazer O ( m n 2 ) consultas de associação e no máximo n - 1 teoria.$n$$m$$O(mn^2)$$n - 1$

Houve melhorias significativas no número de consultas necessárias para aprender um conjunto regular?

Referências e perguntas relacionadas

• Dana Angluin (1987) "Aprendendo conjuntos regulares de consultas e contra-exemplos", Infortmation and Computation 75: 87-106

• Limites mais baixos para aprendizado na consulta de associação e no modelo de contra-exemplo

Em sua resposta sobre cstheory.SE, Lev Reyzin me direcionou para a tese de Robert Schapire que aprimora o vínculo com as consultas de associação de na seção 5.4.5. O número de consultas de contra-exemplo permanece inalterado. O algoritmo que Schapire usa difere no que faz após uma consulta de contra-exemplo.$O(n^2 + n\log m)$

Esboço da melhoria

No nível mais alto, Schapire força do algoritmo de Angluin a ter a condição extra de que para um fechado ( S , E , T ) e cada s 1 , s 2 ∈ S se s 1 ≠ s 2 então r O w ( s 1 ) ≠ r o w ( s 2 ) . Isso garante que | S $(S,E,T)$$(S,E,T)$$s_1, s_2 \in S$$s_1 \neq s_2$$row(s_1) \neq row(s_2)$ e também tornatrivial a propriedade deconsistênciado algoritmo de Angluin. Para garantir isso, ele precisa lidar com os resultados de um contra-exemplo de maneira diferente.$|S| \leq n$

Dado um contra- , Angluin simplesmente adicionado z e todos os seus prefixos para S . Schapire faz algo mais sutil, em vez de adicionar um único elemento e de E . Esse novo e fará com que ( S , E , T ) não seja fechado no sentido de Angluin e a atualização para fechar com a introdução de pelo menos uma nova sequência de caracteres em S , mantendo todas as linhas distintas. A condição em e é:$z$$z$$S$$e$$E$$e$$(S,E,T)$$S$$e$

Onde é a função de saída, q 0 é o estado inicial e δ a regra de atualização do DFA verdadeiro 'desconhecido'. Em outras palavras, e deve servir como testemunha para distinguir o futuro de s de s ' a .$o$$q_0$$\delta$$e$$s$$s'a$

Para descobrir isso de z fazemos uma busca binária para descobrir uma sub r i tal que z = p i r i e 0 ≤ | p i | = i < | z | de modo que o comportamento de nossa máquina conjecturada seja diferente com base em um caractere de entrada. Em mais detalhe, deixamos s i ser a string correspondente ao estado alcançado em nossa máquina de conjectura, seguindo p i . Usamos a pesquisa binária (é aqui que o log $e$$z$$r_i$$z = p_ir_i$$0 \leq |p_i| = i < |z|$$s_i$$p_i$$\log m$$k$$o(\delta(q_0,s_kr_k)) \neq o(\delta(q_0,s_{k+1}r_{k+1})$$r_{k+1}$$e$$E$

Não sei se minha resposta ainda é relevante. Recentemente, foi descrita a implementação de um novo algoritmo chamado Observation Pack ou, em algumas circunstâncias, Discrimination Tree por Falk Howar. Esse algoritmo é como L *, mas use Rivest-Shapire ou outro método (consulte Steffen e Isberner) para lidar com a decomposição de contra-exemplo; e usa uma estrutura de dados, uma árvore de discriminação (uma árvore binária) para tornar eficientemente uma "peneira", ou seja, a inserção de uma transição A (onde A é cada símbolo do alfabeto) de um novo estado encontrado até que não haja fechamento . Este algoritmo existe em duas versões: OneGlobally e OneLocally, dependendo se o sufixo encontrado na decomposição é adicionado ou não a cada componente (a razão por trás do algoritmo é que todos os prefixos em um componente são equivalentes a um prefixo curto e representam o mesmo estado no destino, de acordo com os sufixos encontrados Mais tarde, com um novo contra-exemplo, é encontrado um novo sufixo que discrimina pelo menos 2 prefixos de um mesmo componente. Isso causa uma divisão desse componente em dois componentes). Com o OneLocally, há muito menos consulta de associação, mas o número de consultas de equivalência pode aumentar drasticamente com o DFA de grande destino. Em vez disso, o OneGlobally tem um número de consultas de associação sempre inferiores a L * (mas maiores que o OneLocally) e um número semelhante de consultas de equivalências que L * Posteriormente, com um novo contra-exemplo, é encontrado um novo sufixo que discrimina pelo menos 2 prefixos de um mesmo componente. Isso causa uma divisão desse componente em dois componentes). Com o OneLocally, há muito menos consulta de associação, mas o número de consultas de equivalência pode aumentar drasticamente com o DFA de grande destino. Em vez disso, o OneGlobally tem um número de consultas de associação sempre inferiores a L * (mas maiores que o OneLocally) e um número semelhante de consultas de equivalências que L * Posteriormente, com um novo contra-exemplo, é encontrado um novo sufixo que discrimina pelo menos 2 prefixos de um mesmo componente. Isso causa uma divisão desse componente em dois componentes). Com o OneLocally, há muito menos consulta de associação, mas o número de consultas de equivalência pode aumentar drasticamente com o DFA de grande destino. Em vez disso, o OneGlobally tem um número de consultas de associação sempre inferiores a L * (mas maiores que o OneLocally) e um número semelhante de consultas de equivalências que L *

Eu sei que também existe outro algoritmo: o algoritmo TTT que é melhor que o Observation Pack também, mas eu não tenho um bom conhecimento dele. O algoritmo TTT deve ser o estado da arte