Indução de linguagens regulares

Origem: Wikipédia, a enciclopédia livre.

Em teoria da aprendizagem computacional, indução de linguagens regulares refere-se à tarefa de obter a descrição formal (e.g. gramática) de uma linguagem regular a partir de um dado conjunto de exemplos de cadeias. Embora Mark E. Gold tenha mostrado que nem toda linguagem regular pode ser obtida dessa forma (veja identificação de linguagem no limite), abordagens têm sido investigadas para uma variedade de subclasses. Elas são esboçadas neste artigo. Para a obtenção de gramáticas mais gerais, veja indução de gramática.

Exemplo[editar | editar código-fonte]

Uma linguagem regular é definida como um conjunto (finito ou infinito) de cadeias que pode ser descrito por um dos formalismos matemáticos chamados "autômato finito", "gramática regular", ou "expressão regular", onde todas eles têm o mesmo poder de expressão. Uma vez que as expressões regulares apresentam notações consideravelmente menores, elas serão introduzidas e utilizadas aqui. Dado um conjunto Σ de símbolos (também chamado de alfabeto), uma expressão regular pode ser

  • ∅ (denotando o conjunto vazio de cadeias),
  • ε (denotando o conjunto unitário contendo somente a cadeia vazia),
  • a (onde a é qualquer caractere contido em Σ, denotando o conjunto unitário contento somente a cadeia com o caractere a),
  • r+s (onde r e s são, por sua vez, expressões regulares, denotando o conjunto que representa a união entre r e s),
  • rs (denotando o conjunto de todas as possíveis concatenações entre cadeias dos conjuntos r e s),
  • r+ (denotando o conjunto de n concatenações repetidas entre cadeias do conjunto r, para qualquer n ≥ 1), ou
  • r* (analogamente, denotando o conjunto de n concatenações repetidas, mas também incluindo a cadeia vazia, quando n é igual a 0).

Por exemplo, considerando Σ = { 0,1 }, a expressão regular (0+1+ε)⋅(0+1) denota o conjunto de todos os números binários com um ou dois dígitos (zeros à esquerda são permitidos) enquanto 1⋅(0+1)*⋅0 denota o conjunto (infinito) de todos os números binários pares (zeros à esquerda não são permitidos).

Dado um conjunto de cadeias (também chamado de "exemplos positivos"), a tarefa de indução de linguagem regular é criar uma expressão regular que denota o conjunto contendo todas elas. Como um exemplo, dado { 1, 10, 100 }, uma descrição "natural" pode ser a expressão regular 1⋅0*, correspondendo a caracterização informal "um 1 seguido arbitrariamente por muitos (talvez até nenhum) 0s". No entanto, (0+1)* e 1+(1⋅0)+(1⋅0⋅0) são outras expressões regulares, denotando o maior (assumindo Σ = {0,1}) e o menor conjunto contendo as cadeias dadas, chamados de generalização trivial superior e generalização trivial inferior, respectivamente. Algumas abordagens trabalham em uma configuração estendida onde um conjunto de "exemplos negativos" de cadeias também é dado; então, uma expressão regular pode ser encontrada para gerar todos os positivos, mas nenhum dos exemplos negativos.

Reticulado de autômatos gerando as cadeias 1, 10, e 100 (exemplos positivos). Para cada um dos exemplos negativos de cadeias 11, 1001, 101, e 0, o segmento inicial dos autômatos gera como mostrado. O único autômato que gera todo o { 1, 10, 100}, mas nenhum do { 11, 1001, 101, 0 } são os autômatos triviais de baixo e o mais da direita da imagem, correspondendo a expressão regular 1⋅0*.

Reticulado de autômatos[editar | editar código-fonte]

Dupont et al. mostrou que o conjunto de todos os autômatos finitos estruturalmente completos [nota 1] gerando um dado conjunto de entrada de cadeias exemplo forma um reticulado, com o autômato trivial generalizado inferior e a generalização superior como o elemento de baixo e de cima, respectivamente. Cada membro do reticulado pode ser obtido pela fatoração do autômato generalizado inferior por uma relação de congruência apropriada. A imagem mostra um exemplo para o conjunto de cadeias de entrada { 1, 10, 100 }. Cada autômato é denotado por uma expressão regular equivalente. Para a generalização trivial inferior do nó de baixo da imagem, a forma do autômato também está esboçada em cinza, consistindo dos estados a, b, c, e d. Cada nó do autômato é o resultado da fatoração do autômato de baixo da imagem pela relação de congruência mostrada em cinza embaixo do nó.

Se ambos os exemplos positivos e negativos de cadeias são dados, Dupont et al. constrói o reticulado a partir dos exemplos positivos e então investiga a fronteira de separação entre os autômatos que geram os exemplos negativos e os que não geram. Os mais interessantes são os autômatos imediatamente abaixo da fronteira.[1] Na imagem, as fronteiras de separação são mostradas para o exemplo negativo de cadeias 11, 1001, 101, 0.

Coste e Nicolas apresentam um método de busca próprio dentro deste reticulado, o qual é relacionado ao paradigma de aprendizagem versão espaço de Mitchell. Para encontrar a fronteira de separação, eles utilizam uma algoritmo de coloração de grafos no estado de relação de desigualdade induzido pelos exemplos negativos.[2] Posteriormente, eles investigam uma série de relações de ordenação no conjunto de todos os possíveis estados de fusão.[3]

Kudo e Shimbo usam a representação por fatoração de autômatos para criar um framework único para as seguintes abordagens (esboçadas abaixo):

Cada uma dessas abordagens corresponde a um tipo particular de relação de congruência utilizada para fatoração.[5]

Abordagens[editar | editar código-fonte]

Linguagens k-reversíveis[editar | editar código-fonte]

Angluin considera os chamados autômatos regulares "k-reversíveis", isto é, autômatos determinísticos os quais cada estado pode ser alcançado a partir de, no máximo, um estado, seguindo uma cadeia de transições de tamanho k. Formalmente, se Σ, Q, e δ denotam o alfabeto de entrada, o conjunto de estados e a função de transição de um autômato A, respectivamente, então A é chamado de k-reversível se: ∀a0,...,ak ∈ Σ ∀s1, s2Q: δ*(s1,a0...ak) = δ*(s2,a0...ak) ⇒ s1 = s2, onde δ* significa a extensão homomórfica de δ para palavras arbitrárias. Angluin apresenta um algoritmo cúbico para a obtenção da menor linguagem k-reversível para um dado conjunto de palavras de entrada; para k = 0, o algoritmo tem complexidade quase linear.[6][7] A singularidade do estado requerido após k + 1 símbolos dados força a unificação dos estados do autômato, levando a uma generalização apropriada diferente do autômato trivial generalizado inferior. Esse algoritmo tem sido utilizado para aprender partes simples da sintaxe do inglês;[8] posteriormente, uma versão incremental foi fornecida [9] Outra abordagem baseada em autômatos k-reversíveis é o método de "agrupamento-cauda".[10]

Autômatos sucessores[editar | editar código-fonte]

A partir de um dado conjunto de cadeias de entrada, Vernadat e Richetin constroem o chamado autômato sucessor, consistindo de um estado para cada caractere distinto e uma transição entre cada dois estados de caracteres adjacentes.[11] Por exemplo, o conjunto unitário de entrada { aabbaabb } conduz a um autômato correspondente a expressão regular (a+b+)*.

Uma extensão dessa abordagem é o método do antecessor-sucessor o qual generaliza cada repetição de caractere imediatamente em um fecho de Klenee e depois inclui para cada caractere o conjunto dos seus possíveis antecessores no seu estado. Autômatos sucessores podem expressar exatamente a classe das linguagens locais. Uma vez que cada linguagem regular é a imagem homomórfica de uma linguagem local, gramáticas de uma classe formadora pode ser obtida por levantamento, se um [[homomorfismo]] apropriado (dependendo da aplicação pretendida) é fornecido. Em particular, existe um homomorfismo para a classe das linguagens que podem ser obtidas pelo método do antecessor-sucessor.[12] A aprendizibilidade das linguagens locais pode ser reduzida para as linguagens k-reversíveis.[13][14]

Derivação de Brzozowski (no fundo vermelho) de um dicionário de conjunto de cadeias relacionadas a "con"
Ilustração do lema do bombeamento para autômatos regulares

Abordagens iniciais[editar | editar código-fonte]

Chomsky e Miller (1957)[15] usaram o lema do bombeamento: Eles "advinham" uma parte v de uma cadeia de entrada uvw e tentam construir um ciclo de correspondência no autômato a ser obtido; usando consultas de pertinência eles perguntam, para um k apropriado, qual das cadeias uw, uvvw, uvvvw, ..., uvkw também pertence a linguagem a ser obtida, refinando dessa forma a estrutura do autômato. Em 1959, Solomonoff generalizou essa abordagem como gramáticas livre de contexto, a qual também obedece ao lema do bombeamento.[16]

Autômatos de cobertura[editar | editar código-fonte]

Câmpeanu et al. entende um autômato finito como uma representação compacta de uma linguagem grande e finita. Dado uma linguagem F, eles procuram pelo chamado autômato de cobertura A tal que a sua linguagem L(A) cubra F no seguinte sentido: L(A) ∩ Σl = F, onde l é o tamanho da cadeia mais longa em F, e Σl denota o conjunto de todas as cadeias que não são maiores que l. Se tal autômato de cobertura existe, F é unicamente determinado por A e l. Por exemplo, F = { ad, read, reread } tem l = 6 e um autômato de cobertura correspondendo a expressão regular (re)*ad.

Para duas cadeias x e y, Câmpeanu et al. define x ~ y se xzFyzF para qualquer cadeia z de tamanho tal que ambos xz e yz não são maiores que l.[17] Baseado nessa relação, cuja falta de transitividade[nota 2] causa problemas técnicos consideráveis, eles fornecem um algoritmo O(n4)[nota 3] para construir a partir de F um autômato de cobertura A com um número mínimo de estados. Além isso, para união, intersecção e diferença de duas linguagens finitas, eles fornecem operações correspondentes em seus autômatos de cobertura.[18][19] Păun et al. melhorou a complexidade de tempo para O(n2).[20]

Autômatos residuais[editar | editar código-fonte]

Para um conjunto S de cadeias e a cadeia u, a derivativa de Brzozowski u−1S é definida como o conjunto de todo o restante de cadeias que podem ser obtidas a partir de uma cadeia em S tirando o prefixo u (se possível), formalmente: u−1S = { v ∈ Σ*: uvS }, conforme a imagem.[21] Denis et al. define o autômato residual como um autômato finito não-determinístico A onde cada estado q corresponde a uma derivativa de Brzozowski da sua linguagem de aceitação L(A), formalmente: ∀qQu∈Σ*: L(A,q) = u−1L(A), onde L(A,q) denota a linguagem aceita a partir de q como estado inicial.

Eles mostram que cada linguagem regular é gerada por um único autômato residual mínimo. Seus estados são ∪-indecomponíveis derivativas de Brzozowski, e pode ser exponencialmente menor que o menor autômato determinístico. Além disso, eles mostram que o autômato residual para linguagens regulares pode ser obtido em tempo polinomial, mesmo assumindo amostras de entradas favoráveis. Eles forneceram o algoritmo de obtenção do autômato residual e provaram que pode-se obter o autômato pela sua amostra característica de entradas de cadeias positivas e negativas.[22][23]

Expressões regulares reduzidas[editar | editar código-fonte]

Brill define uma expressão regular reduzida como

  • a (onde a é qualquer caractere em Σ; denotando o conjunto unitário contendo apenas a cadeia com o único caractere a),
  • ¬a (denotando qualquer outro caractere individual em Σ exceto a),
  • • (denotando qualquer caractere individual em Σ)
  • a*, (¬a)*, ou •* (denotando arbitrariamente muitos, possivelmente zero, repetições de caracteres provenientes do conjunto de a, ¬a, ou •, respectivamente), ou
  • rs (onde r e s são, por sua vez, simplesmente expressões regulares reduzidas; denotando o conjunto de todas as possibilidades de concatenação de cadeias dos conjuntos r e s).

Dado um conjunto de cadeias de entrada, ele constrói passo a passo a árvore na qual cada ramo é nomeado por uma expressão regular reduzida aceitando um prefixo de algumas cadeias de entrada, e cada nó é nomeado com o conjunto de tamanho de prefixos aceitos. Ele objetiva a obtenção de regras de correção para os erros de grafia da língua inglesa,[nota 4] ao invés de considerações teóricas sobre a aprendizibilidade das classes de linguagem. Consequentemente, ele usa heurísticas para podar a árvore durante a construção, trazendo uma melhora de tempo de execução considerável.[24]

Aplicações[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. i.e. autômato finito sem estados e transições desnecessários, em relação a um dado conjunto de cadeias de entrada
  2. Por exemplo, F = { aab, baa, aabb } conduz a aab ~ aabb (somente z=ε precisa ser considerado para checar isso) e aabb ~ baa (analogamente), mas não aab ~ baa (de acordo com o caso z=b). De acordo com Câmpeanu et al. (2001, Lemma 1, p.5), no entanto x ~ yy ~ zx ~ z é verdadeiro para cadeias x, y, z com |x| ≤ |y| ≤ |z|.
  3. onde n é o número de estados do AFD AF tal que L(AF) = F
  4. Por exemplo, substituir "past" por "passed" no contexto "(¬to)*SINGULAR_NOUNpast"

Referências

  1. P. Dupont, L. Miclet, E. Vidal (1994). «What is the Search Space of the Regular Inference?». In: R. C. Carrasco and J. Oncina. Proceedings of the Second International Colloquium on Grammatical Inference (ICGI): Grammatical Inference and Applications. Col: LNCS. 862. [S.l.]: Springer. pp. 25–37 
  2. F. Coste, J. Nicolas (1997). «Regular Inference as a Graph Coloring Problem». Proc. ICML Workshop on Grammatical Inference, Automata Induction, and Language Acquisition. [S.l.: s.n.] 
  3. F. Coste, J. Nicolas (1998). «How Considering Incompatible State Mergings May Reduce the DFA Induction Search Tree». In: Vasant Honavar and Giora Slutzki. Grammatical Inference, 4th International Colloquium, ICGI. Col: LNCS. 1433. [S.l.]: Springer. pp. 199–210 
  4. Dominique Luzeaux (agosto de 1997). «A Universal Approach to Positive Regular Grammar Inference». Proc. 15th World IMACS Congress on Scientific Computation, Modelling and Applied Mathematics. [S.l.: s.n.] Consultado em 22 de novembro de 2015. Arquivado do original em 13 de janeiro de 2005 
  5. M. Kudo, M. Shimbo (1988). «Efficient Regular Grammatical Inference Techniques by the Use of Partial Similarities and Their Logical Relationships». Pattern Recognition. 21: 401–409. doi:10.1016/0031-3203(88)90053-2 
  6. D. Angluin (1981). «A Note on the Number of Queries Needed to Identify Regular Languages». Information and Control. 51: 76–87. doi:10.1016/s0019-9958(81)90090-5 
  7. D. Angluin (1982). «Inference of Reversible Languages». J.ACM. 293: 741–765 
  8. Robert C. Berwick, Samuel F. Pilato (1987). «Learning Syntax by Automata Induction». Machine Learning. 2 (1): 9–38. doi:10.1007/bf00058753 
  9. Rajesh Parekh, Codrin Nichitiu, Vasant Honavar (janeiro de 1997). «A Polynomial Time Incremental Algorithm for Regular Grammar Inference». AI Research Group, Iowa State Univ. (TR 97-03). 14 páginas 
  10. L. Miclet, C. Faure (1985). «Reconnaissance des Formes Structurelle: Développement et Tendances». INRIA 
  11. F. Vernadat, M. Richetin (1984). «Regular Inference for Syntactic Pattern Recognition: A Case Study». Proc. 7th International Conference on Pattern Recognition (ICPR). [S.l.: s.n.] pp. 1370–1372 
  12. P. Garcia, E. Vidal, F. Casacuberta (1987). «Local Languages, The Successor Method, and a Step Towards a General Methodology for the Inference of Regular Grammars». IEEE Trans. on Pattern Analysis and Machine Intelligence. 9 
  13. Takashi Yokomori (outubro de 1989). «Learning Context-Free Languages Efficiently». In: K.P. Jantke. Proc. Int. Workshop AII. Col: LNAI. 397. [S.l.]: Springer. pp. 104–123 
  14. Satoshi Kobayashi, Takashi Yokomori (1994). «Learning Concatenations of Locally Testable Languages from Positive Data». In: Setsuo Arikawa and Klaus P. Jantke. Proc. 5th ALT. Col: LNAI. 872. [S.l.]: Springer. pp. 405–422 
  15. N. Chomsky, G.A. Miller (1957). «Pattern Conception». ASTIA (Document AD110076) 
  16. R. Solomonoff (junho de 1959). «A New Method for Discovering the Grammars of Phrase Structure Languages». Proc. Int. Conf. on Information Processing. [S.l.]: R.Oldenbourg. pp. 285–290 
  17. Essa relação generaliza RF a partir do Teorema de Myhill-Nerode. Foi investigado em mais detalhes na seção 3 do: Cynthia Dwork and Larry Stockmeyer (1990). «A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata». SIAM Journal on Computing. 19 (6): 1011–1023. doi:10.1137/0219069 
  18. a b Cezar Câmpeanu and Nicolae Sântean and Sheng Yu (1998). «Minimal Cover-Automata for Finite Languages». In: J.-M. Champarnaud and D. Maurel and D. Ziadi. Proc. Workshop on Implementing Automata (WIA) (PDF). Col: LNCS. 1660. [S.l.]: Springer. pp. 43–56. doi:10.1007/3-540-48057-9_4 
  19. Cezar Câmpeanu and Nicolae Sântean and Sheng Yu (2001). «Minimal Cover-Automata for Finite Languages» (PDF). Theoretical Computer Science. 267: 3–16. doi:10.1016/s0304-3975(00)00292-9 
  20. Andrei Păun and Nicolae Sântean and Sheng Yu (setembro de 2001). «An O(n2) Algorithm for Constructing Minimal Cover Automata for Finite Languages». In: Sheng Yu and Andrei Păun. Proc. 5th Int. Conf. on Implementation and Application of Automata (CIAA) (PDF). Col: LNCS. 2088. [S.l.]: Springer. pp. 243–251. ISBN 978-3-540-42491-8 
  21. Janusz A. Brzozowski (1964). «Derivatives of Regular Expressions». JACM. 11: 481–494. doi:10.1145/321239.321249 
  22. François Denis, Aurélien Lemay, Alain Terlutte (2000). «Learning Regular Languages Using Non Deterministic Finite Automata». In: Arlindo L. Oliveira. Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI. Col: LNCS. 1891. [S.l.]: Springer. pp. 39–50. ISBN 3-540-41011-2 
  23. François Denis, Aurélien Lemay, Alain Terlutte (2001). «Learning Regular Languages using RFSA». Proc. ALT '01 (PDF). [S.l.: s.n.] 
  24. a b Eric Brill (2000). «Pattern–Based Disambiguation for Natural Language Processing». Proc. EMNLP/VLC. [S.l.: s.n.] 
  25. Alvis Brazma, Inge Jonassen, Jaak Vilo and Esko Ukkonen (1998). «Pattern Discovery in Biosequences». In: Vasant Honavar and Giora Slutzki. Grammatical Inference, 4th International Colloquium, ICGI. Col: LNCS. 1433. [S.l.]: Springer. pp. 257–270 
  26. M.S. Waterman, ed. (janeiro de 1989). Mathematical Methods for DNA Sequences. [S.l.]: CRC Press. ISBN 084936664X 
  27. Fernando Pereira, Yves Schabes (1992). «Inside-Outside Reestimation for partially Bracketed Corpora». Proc. 30th Ann. Meeting of the Assoc. for Comp. Linguistics. [S.l.: s.n.] pp. 128–135 
  28. Helena Ahonen (novembro de 1996). Generating Grammars for Structured Documents Using Grammatical Inference Methods (Ph.D.). Report. A-1996-4. University of Helsinki, Department of Computer Science 
  29. Stephen Watkinson (1997). Induction of Musical Syntax (Master). Dept. of AI, Univ. Edinburgh 
  30. Pedro P. Cruz-Alcázar, Enrique Vidal (1998). «Learning Regular Grammars to Model Musical Style: Comparing Different Coding Schemes». In: Vasant Honavar and Giora Slutzki. Grammatical Inference, 4th International Colloquium, ICGI. Col: LNCS. 1433. [S.l.]: Springer. pp. 211–222 
  31. Alexander S. Saidi, Souad Tayeb-bey (1998). «Grammatical Inference in Document Recognition». In: Vasant Honavar, Giora Slutzki. Grammatical Inference, 4th International Colloquium, ICGI. Col: LNCS. 1433. [S.l.]: Springer. pp. 175–186. ISBN 3-540-64776-7