Identificação de linguagem no limite

Identificação de linguagem no limite é um modelo formal de inferência indutiva. Esse modelo foi introduzido por E. Mark Gold no seu artigo com o mesmo título.^[1] Nesse modelo, um aprendiz é fornecido com a apresentação (i.e. strings) de alguma linguagem formal. A aprendizagem é vista como um processo infinito. Cada vez que um elemento da apresentação é lido, o aprendiz deve fornecer uma representação (e.g. uma gramática formal) para a linguagem. Um aprendiz pode identificar o limite de uma classe de linguagens se dada qualquer representação de qualquer linguagem da classe, o aprendiz irá produzir somente um número finito de representações erradas, e portanto, converge na representação correta em um número finito de passos, sem necessariamente ser capaz de dizer sua correção desde um contraexemplo para que a representação possa parecer um elemento arbitrariamente grande.

Gold definiu dois tipos de apresentações:

Texto (informação positiva): uma enumeração de todas as palavras que a linguagem consiste;
Representação completa (informação positiva e negativa): uma enumeração de todas as possíveis palavras, cada uma com um rótulo indicando se a palavra pertence à linguagem ou não.

Capacidade de aprendizado[editar | editar código-fonte]

Este modelo é uma primeira tentativa de capturar formalmente a noção de capacidade de aprendizado. O artigo de Gold ^[2] introduz para o contraste dos modelos mais fortes.

Identificação finita(onde o aprendiz tem que dizer a correção depois de um número finito de passos), e
Identificação em tempo fixo(onde a correção tem que ser alcançada depois de um número de passos especificado à priori.

Um modelo mais fraco de aprendizagem é o modelo aprendizagem provavelmente aproximadamente correto (PAC), introduzido por Leslie Valiant em 1984.

Exemplos[editar | editar código-fonte]

Exemplo 4
	Professor	Aprendizes
		Advinho	Questão
0.			abab
1.	yes	abab	baba
2.	yes	a^(ba)^b^*	aa
3.	no	(ab)^(ba)^(ab)^(ba)^	bababa
4.	yes	(ab+ba)^*	babb
5.	no	(ab+ba)^*	baaa
	...	...

Exemplo 3
	Professor	Aprendiz
1.	abab	abab
2.	baba	a^(ba)^b^*
3.	aa	(ab)^(ba)^(ab)^(ba)^
4.	bababa	(ab+ba)^*
5.	~~babb~~	(ab+ba)^*
6.	~~baaa~~	(ab+ba)^*
7.	ε	(ab+ba)^*
	...	...

Exemplo 2
	Professor	Aprendiz
1.	abab	abab
2.	ba	abab+ba
3.	baba	abab+ba+baba
4.	ba	abab+ba+baba
5.	baba	abab+ba+baba
6.	abab	abab+ba+baba
7.	ε	abab+ba+baba+ε
	...	...

Exemplo 1
	Professor	Aprendiz
1.	abab	abab
2.	baba	abab+baba
3.	baabab	(b+ε)(ab)^*
4.	baabab	(b+ε)(ab)^+baabab*
5.	abbaabba	(ab)^(ba)^(ab)^(ba)^
6.	baabbaab	(ab+ba)^*
7.	bababa	(ab+ba)^*
	...	...

É didático olhar para exemplos concretos de sessões de aprendizagem a definição de identificação no limite fala.

Exemplo 1: Sessão fictícia para aprender uma linguagem regular L sobre o alfabeto {a,b} da apresentação do texto. Em cada passo o professor dá uma palavra pertencente a L, e o aprendiz advinha uma resposta para L, codificado como uma expressão regular. No 3º passo, o “palpite” do aprendiz não é consistente com a palavra vista até agora; no 4º passo, o professor dá uma palavra repetidamente. Depois do 6º passo, o aprendiz fica com a expressão regular (ab+ba)*. Se acontecer disso ser uma descrição de uma linguagem L o professor tem em mente, diz-se que o aprendiz aprendeu esta linguagem. Se um programa de computador para o papel do aprendiz existisse e fosse capaz de aprender com sucesso cada linguagem regular, esta classe de linguagens seria identificável no limite. Gold tem mostrado que esse não é o caso.^[3]
Exemplo 2: Um algoritmo de aprendizagem particular sempre supondo L é apenas a união de duas palavras visto até agora. Se L é uma linguagem finita, o aprendiz vai, eventualmente, descobrir isso corretamente, contudo, sem ser capaz de dizer quando. Embora a descoberta não tenha mudado durante o passo 3 até o 6, o aprendiz não pode ter certeza se está correto. Gold tem mostrado que a classe de linguagens finitas são identificáveis no limite; no entanto, essa classe não é nem finita nem identificada em tempo fixo.
Exemplo 3: Aprendizado de apresentação completa dita. Em cada passo, o professor dá uma palavra e diz se ela pertence a L (verde) ou não (~~vermelho, riscado~~). Cada possível palavra é eventualmente classificada nesta forma pelo professor.
Exemplo 4: Aprendizado de apresentação completa por solicitação. O aprendiz dá uma palavra como consulta, o professor diz se essa pertence a L (sim) ou não (não); o aprendiz então dá um palpite para L, seguido pela próxima palavra de consulta. Neste exemplo, o aprendiz passa como consulta, em cada passo, somente a mesma palavra como dado pelo professor no exemplo 3. Em geral, Gold tem mostrado que cada classe de linguagem identificada na configuração “apresentação solicitada” é também identificada na configuração,^[4] “apresentação-dita”, uma vez que o aluno, em vez de consultar a palavra, só precisa esperar até esta ser, eventualmente, dada pelo professor.

Caracterização de capacidade de aprendizagem[editar | editar código-fonte]

Dana Angluin deu as características de aprendizagem de texto (informação positiva) em 1980 em um artigo. ^[5] Se um aprendiz é necessário para ser eficaz, em seguida, uma classe indexada de linguagens recursivas é capaz de aprender no limite se existe um procedimento eficaz que uniformemente enumera tell-tales para cada linguagem na classe (condição 1). Isto não é difícil de ver, que se nós permitimos um aprendiz ideal (i.i, uma função arbitrária), então uma classe de linguagens indexadas são capaz de aprender no limite se cada linguagem na classe tem um tell-tale (condição 2).

Classe de linguagens capazes de aprender no limite[editar | editar código-fonte]

Linhas divisórias entre classes de linguagens identificáveis e não-identificáveis^[6]
Modelo de capacidade de aprendizado	Classe de linguagens
Apresentação textual anômala^{[note 1]}
	Recursivamente enumeráveis
	Conjunto recursivo
Apresentação Completa
	Primitive recursive^{[note 2]}
	Sensível ao contexto
	Livres do contexto
	Regular
	Superfinita.^{[note 3]}
Apresentação de texto normal^{[note 4]}
	Finita
	Única^{[note 5]}

A tabela mostra quais classes de linguagens são identificadas no limite em quais modelos de aprendizagem. No lado direito, cada classe de linguagem é uma superclasse de todas classes menores. Cada modelo de aprendizagem(i.e. tipo de apresentação) pode identifica no limite todas as classes abaixo dela. Em particular, a classe de linguagens finitas são identificadas no limite por “apresentação de texto”(cf. Exemplo 2 acima), enquanto a classe de linguagens regulares não é.

Linguagens padrões (linguagem formal), introduzidas por Dana Angluin em outro artigo em 1980, ^[7] são, também, identificáveis por apresentação textual normal; uma vez que eles estão acima das únicas (singleton) e abaixo da classe de linguagem primitiva recursiva, mas incomparável para as classes entre elas.^{[note 6]}^{[necessário esclarecer]}

Condições suficientes para aprendizado[editar | editar código-fonte]

Condição 1 no artigo de Angluin não é sempre fácil de verificar. Contudo, pessoas vêm com várias condições suficientes para a capacidade de aprendizado de uma classe de linguagens. Veja também indução de linguagens regulares para subclasses capacidade de aprendizado de linguagens regulares.

Espessura finita[editar | editar código-fonte]

Uma classe de linguagens tem espessura finita se todo conjunto de palavras não-vazias está contido no maior número finito de linguagens da classe. Isso é exatamente a condição 3 no artigo de Angluin. Angluin mostrou que se uma classe de linguagens recursivas tem espessura finita, então ela é capaz de aprender no limite.

Uma classe com espessura finita certamente satisfaz condição-MEF e condição-MMF; em outras palavras, espessura finita implica espessura M-finita.

Elasticidade finita[editar | editar código-fonte]

Uma classe de linguagens tem elasticidade finita se para toda sequencia infinita de palavras s₀, s₁,... e toda sequencia infinita de linguagens na classe L₁,L₂,..., existe um numero finito n tal que s_n não pertence L_n é inconsistente com {s₁, …, s_n-1}; isto mostra que a classe de linguagens recursivamente enumeráveis é capaz de aprender no limite se esta tem elasticidade finita.

Isto mostra que uma classe de linguagens recursivamente enumeráveis é capaz de aprende no limite se esta tem elasticidade finita.

Ideia de limite de mudança[editar | editar código-fonte]

Um limite acima do número de mudança de hipóteses que ocorre antes da convergência.

Outros conceitos[editar | editar código-fonte]

Propriedade de cruzamento infinito[editar | editar código-fonte]

Uma linguagem L tem propriedade de cruzamento infinito dentro de uma classe de linguagens se existe uma sequência infinita Li de linguagens distintas em uma sequência de conjuntos finitos T_i tal que:

$T_{1}\subset T_{2}\subset ...$ ,
$T_{i}\in L_{i}$ ,
$T_{i+1}\not \in L_{i}$ , e
$\lim _{n=\infty }T_{i}=L$ .

Note que L não é necessariamente um membro da classe de linguagem.

Não é difícil de ver que,se existe uma linguagem com propriedade de cruzamento infinito dentro da classe de linguagens, então esta classe de linguagens tem elasticidade infinita.

Relações entre conceitos[editar | editar código-fonte]

Espessura finita implica elasticidade finita;^[9] o inverso não é verdade.
Elasticidade finita e capacidade de aprender conservadoramente implica na existência de um limite acima do número de mudanças. Contudo, espessura M-finita sozinha não implica na existência de uma "ideia de limite de mudança"; mas a existência de uma "ideia de limite de mudança" implica espessura M-finita.
A existência de uma ideia de limite de mudança implica capacidade de aprendizado; o inverso não é verdade..
Se não há ordem de acumulação para uma classe de linguagens, então existe uma linguagem (não necessariamente na classe) que tem a propriedade de cruzamento infinito dentro da classe, que por sua vez implica elasticidade infinita na classe.

Questões abertas[editar | editar código-fonte]

Se uma classe contável de linguagens recursivas tem uma “ideia de limite de mudança” para aprendizes não-computáveis, a classe também tem uma “ideia de limite de mudança” para aprendizes computáveis, ou a classe é incapaz de aprender por um aprendiz computável?

Notas[editar | editar código-fonte]

↑ i.e. apresentação textual, onde a palavra(cadeia) dada pelo professor é uma função recursiva primitiva de um número de passos atual, e o aprendiz codifica um palpite de linguagem como um programa que enumera as linguagens
↑ i.e. a classe de linguagens que são decidíveis por função recursiva primitiva
↑ i.e. contendo todos os idiomas finitos e pelo menos um infinito
↑ i.e. text presentation, except for the anomalous text presentation setting
↑ i.e. a classe das linguagens consistentes de uma única cadeia (nós mencionamos aqui somente como um limite inferior para linguagens finitas e linguagens reconhecidas)
↑ incomparável para regular e para a classe linguagem livre de contexto: Theorem 3.10, p.53

Referências

↑ Gold, E. Mark (1967). «Language identification in the limit» (PDF). Information and Control. 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5
↑ p.457
↑ Teorema I.8,I.9, p.470-471
↑ Theorem I.3, p.467
↑ Dana Angluin (1980). «Inductive Inference of Formal Languages from Positive Data» (PDF). Information and Control. 45: 117–135. doi:10.1016/S0019-9958(80)90285-5
↑ Table 1, p.452, in (Gold 1967)
↑ Dana Angluin (1980). «Finding Patterns Common to a Set of Strings» (PDF). Journal of Computer and System Sciences. 21: 46–62. doi:10.1016/0022-0000(80)90041-0
↑ Motoki, Shinohara, and Wright (1991) "The correct definition of finite elasiticity: corrigendum to identification of unions", Proc. 4th Workshop on Computational Learing Theory, 375-375
↑ Wright, Keith (1989) "Identificação de união de linguagens desenhadas de Classe Identificável". Proc. 2nd Workwhop em Teoria de Aprendizado Computacional(inglês), 328-333; com correção em: ^[8]

[textual_anômala-7] .e. apresentação textual, onde a palavra(cadeia) dada pelo professor é uma função recursiva primitiva de um número de passos atual, e o aprendiz codifica um palpite de linguagem como um programa que enumera as linguagens

[8] .e. a classe de linguagens que são decidíveis por função recursiva primitiva

[9] .e. contendo todos os idiomas finitos e pelo menos um infinito

[10] .e. text presentation, except for the anomalous text presentation setting

[11] .e. a classe das linguagens consistentes de uma única cadeia (nós mencionamos aqui somente como um limite inferior para linguagens finitas e linguagens reconhecidas)

[13] rável para regular e para a classe linguagem livre de contexto: Theorem 3.10, p.53

[1] Gold, E. Mark (1967). «Language identification in the limit» (PDF). Information and Control. 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5

[2] .457

[3] Teorema I.8,I.9, p.470-471

[4] Theorem I.3, p.467

[5] Dana Angluin (1980). «Inductive Inference of Formal Languages from Positive Data» (PDF). Information and Control. 45: 117–135. doi:10.1016/S0019-9958(80)90285-5

[6] Table 1, p.452, in (Gold 1967)

[12] Dana Angluin (1980). «Finding Patterns Common to a Set of Strings» (PDF). Journal of Computer and System Sciences. 21: 46–62. doi:10.1016/0022-0000(80)90041-0

[Motoki.Shinohara.Wright.1991-14] Motoki, Shinohara, and Wright (1991) "The correct definition of finite elasiticity: corrigendum to identification of unions", Proc. 4th Workshop on Computational Learing Theory, 375-375

[15] Wright, Keith (1989) "Identificação de união de linguagens desenhadas de Classe Identificável". Proc. 2nd Workwhop em Teoria de Aprendizado Computacional(inglês), 328-333; com correção em: ^[8]

[1]

[2]

[3]

[4]

[5]

[6]

[note 1]

[note 2]

[note 3]

[note 4]

[note 5]

[7]

[note 6]

[9]

[8]