Existem melhorias no algoritmo de Dana Angluin para aprender conjuntos regulares

33

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.nmO(mn2)n1

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


Referências e perguntas relacionadas

Artem Kaznatcheev
fonte
Felizmente, @DominikFreydenberger aparece em algum momento no futuro. Ele saberá.
Raphael
2
Suspeito que o @LevReyzin também saiba a resposta ... e foi por isso que originalmente pensei em perguntar sobre a história, mas acho que devo ajudar a expandir esse novo site.
Artem Kaznatcheev 9/03/12
Não é uma resposta para a pergunta, mas ainda pode ser útil: [ citeulike.org/user/erelsegal-halevi/article/9275508 Um núcleo universal para aprender idiomas regulares]
Erel Segal-Halevi
obrigado pelo link @Erel, mas não entendo como isso se relaciona. O núcleo universal de Kontorovich não é eficientemente computável, e o modelo de aprendizado não possui contra-exemplos.
Artem Kaznatcheev

Respostas:

15

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(n2+nlogm)


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 2S se s 1s 2 então r O w ( s 1 ) r o w ( s 2 ) . Isso garante que | S |(S,E,T)(S,E,T)s1,s2Ss1s2row(s1)row(s2) 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|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 é:zzSeEe(S,E,T)Se

s,sS,aΣs.trow(s)=row(sa)ando(δ(q0,se))o(δ(q0,sae))

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 .oq0δessa

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 mezriz=piri0|pi|=i<|z|sipilogmko(δ(q0,skrk))o(δ(q0,sk+1rk+1)rk+1eE

Artem Kaznatcheev
fonte
5

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

Umbert
fonte
Obrigado por esta resposta! Você tem uma referência em papel para o algoritmo Howar e para TTT?
Artem Kaznatcheev 23/03
Isto para Observação Pacote de ligação Howar e isso para TTT algoritmo de ligação TTT Você pode encontrar a implementação em LearLib (Observação pacote é chamado lá Discriminação Tree)
Umbert