Encontrar a expressão regular mínima é um problema completo do NP?

43

Estou pensando no seguinte problema: Quero encontrar uma expressão regular que corresponda a um conjunto específico de cadeias de caracteres (por exemplo, endereços de email válidos) e não a outros (endereços de email inválidos).

Suponha que por expressão regular queremos dizer alguma máquina de estado finito bem definida, que eu não conheço a terminologia exata, mas vamos concordar com alguma classe de expressões permitidas.

Em vez de criar manualmente a expressão, quero dar a ela um conjunto de exemplos positivos e um conjunto de exemplos negativos.

Em seguida, deve aparecer uma expressão que corresponda aos +, rejeite os - e é mínima em algum sentido bem definido (número de estados nos autômatos?).

Minhas perguntas são:

  • Este problema foi considerado, como pode ser definido de alguma maneira mais concreta e pode ser resolvido com eficiência? Podemos resolvê-lo em tempo polinomial? É NP completo, podemos aproximar de alguma forma? Para quais classes de expressões isso funcionaria? Eu apreciaria qualquer indicação de livros, artigos ou outros que discutam esse tópico.
  • Isso está relacionado de alguma forma à complexidade de Kolmogorov?
  • Isso está relacionado de alguma forma ao aprendizado? Se a expressão regular é consistente com meus exemplos, em virtude de ser mínima, podemos dizer algo sobre seu poder de generalização em exemplos ainda não vistos? Que critério de minimalidade seria mais adequado para isso? Qual seria mais eficiente? Isso tem alguma conexão com o aprendizado de máquina? Novamente, qualquer ponteiro seria útil ...

Desculpe pela pergunta confusa ... Aponte-me na direção certa para descobrir isso. Obrigado !

László Kozma
fonte
2
A página a seguir parece muito relevante para o aspecto de aprendizado da pergunta: people.dsv.su.se/~henke/ML/MERLIN.html
Tsuyoshi Ito
11
… ou talvez não. Parece haver muitos trabalhos sobre o aprendizado do DFA de qualquer maneira.
Tsuyoshi Ito
2
Esta questão foi discutida recentemente no blog da comunidade .
Aaron Sterling

Respostas:

39

OPTkkP=NP

Em relação à pergunta de aprendizado: Kearns e Valiant provaram que você pode codificar o RSA em um DFA. Portanto, mesmo que os exemplos rotulados venham da distribuição uniforme, ser capaz de generalizar para exemplos futuros (também provenientes da distribuição uniforme) quebraria o RSA. Portanto, pensamos que, na pior das hipóteses, ter exemplos rotulados não ajuda no aprendizado de um DFA (no modelo PAC). Este é um dos resultados clássicos de dureza criptográfica para aprendizado.

Ambas as questões estão entrelaçadas devido ao que chamamos de Teorema da Navalha de Occam . Basicamente, afirma que, se tivermos um procedimento para encontrar a menor hipótese de uma determinada classe que seja consistente com uma amostra rotulada por uma hipótese da mesma classe, então o PAC poderá aprender essa classe. Portanto, dado o resultado da dureza RSA, esperamos que encontrar o menor DFA consistente seja difícil em geral!

Para adicionar um resultado positivo de aprendizado, Angluin mostrou que você pode aprender um DFA se criar seus próprios exemplos, mas isso requer o poder adicional de poder perguntar "minha hipótese atual está correta?" Este também foi um artigo seminal na aprendizagem.

Para responder sua outra pergunta, tudo isso está realmente relacionado à complexidade de Kolmogorov, pois o problema de aprendizado se torna mais fácil quando a representação canônica do DFA de destino tem baixa complexidade.

Lev Reyzin
fonte
3
Você me venceu com um resultado mais recente e mais forte! Você deve postar uma resposta melhor mais tarde !! 1 !!
Tsuyoshi Ito
OPA, desculpe! Eu gastei tempo suficiente aprendendo o DFA que tive que pular nisto :)
Lev Reyzin
11
Apenas no caso, eu estava brincando no meu comentário anterior. Claro que estou feliz em ver uma resposta melhor!
Tsuyoshi Ito
11
então, em outras palavras, a principal diferença entre esse problema e a minimização regular de DFAs é a presença de exemplos negativos, sim?
Suresh Venkat
11
eu não entendo sem exemplos negativos, o menor dfa consistente possui apenas 1 estado - o estado de aceitação que aponta para si mesmo ...
Lev Reyzin
13

Eu respondo os aspectos relacionados à aprendizagem da pergunta.

Esse problema parece ser chamado de "aprendizado do DFA" na literatura.

Gold [Gol78] mostrou que é NP-completo decidir, dados k ∈ℕ e dois conjuntos finitos P e N de cadeias, se existe um autômato determinístico de estado finito (DFA) com no máximo k estados que aceita cada cadeia em P e nenhuma das cordas em N . O artigo [PH01] parece discutir problemas relacionados a essa motivação (pode haver muito mais; isso surgiu quando tentei encontrar artigos relevantes com o Google).

Referências

[Gol78] E Mark Gold. Complexidade da identificação de autômatos a partir de dados fornecidos. Information and Control , 37 (3): 302–320, junho de 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh e Vasant Honavar. Aprendendo o DFA com exemplos simples. Machine Learning , 44 (1–2): 9–35, julho de 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh- dfa.pdf

Tsuyoshi Ito
fonte
11
Obrigado pela resposta, estou olhando as referências. Posso votar em mais de uma melhor resposta neste site? :) Mais uma vez, fico envergonhado por ter perdido todo o subcampo "DFA learning", mesmo tendo estudado o aprendizado de máquina por anos.
László Kozma
@ Steve: Você pode aceitar apenas uma resposta, mas pode votar quantas respostas quiser.
Jukka Suomela
2
Observe que [Gold78] também declara que o DFA pode ser aprendido em tempo polinomial (dentro da estrutura de aprendizado de identificação no limite). Veja também o livro recente sobre inferência gramatical ( pagesperso.lina.univ-nantes.fr/~cdlh/book_webpage.html ) para uma visão geral.
mgalle
@ mgalle: Obrigado pelas informações adicionais.
Tsuyoshi Ito
8

Ao longo desta discussão, assumiu-se que encontrar uma expressão regular mínima equivale a encontrar um FSM mínimo que reconheça o idioma, mas essas são duas coisas diferentes. Se bem me lembro, um DFA pode ser minimizado em tempo polinomial, enquanto que encontrar uma expressão regular mínima que represente uma determinada linguagem regular é difícil para o PSPACE. Este último é um daqueles resultados que pertencem ao folclore da Teoria dos Autômatos, mas cuja prova não pode ser encontrada em lugar algum. Eu acho que é declarado como um exercício no livro de Papadimitrou.


fonte
11
É correto que o comprimento da expressão regular e o número de estados no DFA sejam diferentes funções objetivas. Respondi sobre a minimização do DFA porque ela possui uma propriedade melhor (por exemplo, existe um DFA exclusivo com o número mínimo de estados) e, pela maneira como a pergunta foi feita, tive a impressão de que a função exata do objetivo era flexível.
Tsuyoshi Ito
Comentário aleatório: dado que uma expressão regular do tamanho f (n) pode ser simulada por um NFA do tamanho O (f (n)), minimizar expressões regulares é mais como minimizar NFAs, o que é obviamente mais difícil.
Hsien-Chih Chang #
parte disso é abordada nos comentários da resposta de @ keith
Lev Reyzin
2

Veja também este post de estouro de pilha. O livro que você procura parece ser Introdução à Teoria da Computação, de Michael Sipser.

Você está fazendo algumas perguntas diferentes, portanto, faça uma de cada vez:

Is finding a minimal Finite State Machine for a language L NP-complete?

Não, não é. O post Stack Overflow discute um algoritmo n ^ 2 ingênuo para reduzir um FSM ao tamanho mínimo. (Trabalhando para trás a partir de estados de parada, combine estados que são "idênticos" em um sentido preciso.)

Aparentemente (não segui o link), existe um algoritmo n log n para fazer isso.

I have a training set of strings, how do I find the minimal FSM 
that separates the good examples from the bad?

Conforme você o formulou, seu conjunto de treinamento descreve um idioma finito . Os idiomas finitos são mapeados trivialmente para um FSM - crie um conjunto linear de estados que terminam em um estado de parada para cada sequência no seu idioma, sem a necessidade de loop. Em seguida, execute o algoritmo de minimização do FSM na máquina resultante.

Is this a good way to build a classifier?

Eu não diria isso. Minimizar o FSM não muda seu poder discriminativo - esse é o ponto. O FSM mínimo aceita exatamente o conjunto de seqüências de caracteres como qualquer FSM não mínimo equivalente.

Em geral, expressões regulares não são adequadas para classificar novos dados. Para qualquer conjunto de treinamento finito, você receberá um RE / FSM que corresponde apenas aos exemplos positivos nesse conjunto, sem capacidade de generalizar para novos dados. Nunca vi uma abordagem que tente encontrar uma linguagem regular infinita que corresponda a algum corpus de treinamento.

Para aprendizado de máquina, você procuraria algo como um classificador Bayes ingênuo, árvore de decisão, rede neural ou algo mais exótico. A Inteligência Artificial de Russell e Norvig : Uma Abordagem Moderna é um lugar tão bom quanto qualquer outro para encontrar uma visão geral das técnicas de aprendizado de máquina (e muito, muito mais).

Comunidade
fonte
2
Eu não concordo com esta resposta. Se você simplesmente pegar todos os exemplos positivos e construir um FSM que aceite apenas esses exemplos e nada mais, seu FSM pode ser enorme. Por outro lado, o menor FSM que aceita todos os exemplos positivos e nenhum exemplo negativo pode ser muito menor.
Jukka Suomela 01/10/10
3
Eu acho que a pergunta original deixou bem claro: "uma expressão que corresponde aos +, rejeita os - e é mínima em algum sentido bem definido".
Jukka Suomela 01/10/10
5
@ A distinção entre a sua resposta e a minha é bastante sutil. ao criar seu dfa, criando novos estados para cada sequência na amostra, você se compromete com um idioma possivelmente diferente daquele representado pelo dfa mínimo que separa os exemplos positivos e negativos. portanto, o algoritmo para gerar um dfa e minimizá-lo infelizmente não funciona!
Lev Reyzin
11
Não sei se entendi essa distinção. Se temos um conjunto de exemplos positivos e negativos, temos uma família de idiomas que satisfazem essas restrições. para cada um há um (conjunto de) dfas mínimos. Desde que eu retorne um DFA de tamanho mínimo, como importa qual desses idiomas eu escolho.
Suresh Venkat
11
Para aprender, você deseja escolher o menor DFA, pois ele tem a melhor capacidade de generalização. O procedimento do @ kieth não seleciona o DFA mínimo em todos esses idiomas, apenas o menor para o idioma comprometido em usar o procedimento.
Lev Reyzin