Complexidade de problemas de processamento de linguagem natural [fechado]

Quais problemas de processamento de linguagem natural são NP-Complete ou NP-Hard?

Eu procurei no processamento de linguagem natural e teoria da complexidade tags (e tags de complexidade relacionadas), mas não apresentaram resultados.

Nenhuma das perguntas recomendadas da PNL é útil; as mais próximas são as seguintes:

• /cs/25925/why-is-natural-language-processing-such-a-difficult-problem

• /cs/9920/how-is-natural-language-processing-related-to-artificial-intelligence

• Quais aspectos da lingüística são necessários ou bons para o processamento de linguagem natural?

A lista de problemas completos da NP da Wikipedia não lista nenhum resultado de complexidade para a PNL.

A única pista que encontrei é o artigo Complexidade Teórica e Eficaz no Processamento de Linguagem Natural, de J. Morin (1995).

Qualquer ajuda ou sugestões são bem-vindas!

O reconhecimento de LFG (Lexical-Functional Grammar) é NP-Complete .

Editar por solicitação: A Lexical-Functional Grammar (LFG) [1] é uma teoria da sintaxe da linguagem natural, desenvolvida como uma alternativa às teorias de Chomsky sobre sintaxe transformacional. Algumas versões das teorias de Chomsky são computacionalmente equivalentes a gramáticas irrestritas. O LFG, por outro lado, fornece um formalismo gramatical que consiste em uma gramática livre de contexto aumentada por um sistema de recursos.

É o sistema de recursos que está completo com NP. A prova funciona basicamente observando primeiro que o sistema de características é pelo menos tão poderoso quanto a lógica proposicional, e segundo que a gramaticalidade repousa em satisfazer todas as restrições proposicionais que governam a sentença. Portanto, é o problema da satisfação oculto sob outro pretexto.

[1] "Gramática léxico-funcional: um sistema formal para representação gramatical", de Ronald M. Kaplan e Joan Bresnan. O artigo apareceu originalmente em The Mental Representation of Grammatical Relations , ed. Joan Bresnan (Cambridge, MA: The MIT Press, 1982).

Talvez deva-se primeiro definir o que é um problema de processamento de linguagem natural (PNL).

Por exemplo, gramáticas e idiomas sem contexto (CF) foram introduzidos por linguistas (idioma de Chomsky tipo 2, trabalho de Bar-Hillel e outros). A ambiguidade é um grande problema em Lingüística para análise de sentenças reais e no estudo formal de gramáticas e ambiguidade de CF (ambiguidade) e idiomas (ambiguidade inerente). A ambiguidade de uma gramática é apenas semi-decidível.

Então, acho que o problema da ambiguidade deve ser uma resposta para sua pergunta. É classificado como um problema de PNL?

Agora, se você tomar algumas formalizações modernas de sintaxe, como um backbone de CF com estruturas de recursos (ou seja, atributos estruturados), você obtém rapidamente o poder de Turing (cf. LFG que foi provado que NP é difícil , ou mesmo Turing completo , dependendo das variantes). Portanto, se você não for cuidadoso, terá todos os problemas de complexidade com os quais pode sonhar.

Para mais, você também pode examinar esta questão da SE-Linguistics: " A conjectura P versus NP em ciência da computação tem alguma relevância direta para a linguística? "

Na minha própria resposta , eu realmente critico a importância da questão, ou pelo menos algumas de suas interpretações. Muitos dos problemas considerados na linguística, relacionados à análise de sentenças, para tradução ou outros fins, são pequenos problemas, a serem resolvidos em um tempo muito curto. Alguns lingüistas podem até contestar que exista recursão real na estrutura da linguagem, pois qualquer recursão que ocorra raramente é muito profunda. Portanto, pode-se perguntar sobre a relevância linguística da análise de complexidade, que é definida assintoticamente. A primeira pergunta deve ser se chegamos perto o suficiente da assíntota para que a análise assintótica seja significativa.

No entanto, essa observação não se aplica a algum aspecto da PNL, quando uma quantidade massiva de dados precisa ser processada. Conheço pelo menos dois casos:

• mineração de dados em grandes corpora.

• o problema inverso da lingüística: análise de grandes corpora para extrair mecanicamente os dados que caracterizam uma linguagem, estruturalmente e para produzir extensas listas de constituintes, como fonemas, vocabulário para várias partes do discurso (também conhecidas como pré-terminais ), prefixos e sufixos ou inflexões mecanismos, para dar alguns exemplos.

Não sou especialista em mineração de dados e, portanto, não sei se ele realmente gera problemas de complexidade relacionados ao tamanho dos corpora sendo processados. Nesse caso, a complexidade assintótica seria realmente um problema. Mas se é composto principalmente por um grande número de pequenas tarefas aditivas, é mais duvidoso que a complexidade assintótica importe muito. No entanto, eu imagino que algumas técnicas de mineração de dados funcionem com correlações entre documentos independentes e que devam levantar problemas de complexidade dependentes de corpus.

No caso do problema inverso da linguística, a identificação de uma linguagem (que, eu acho, poderia ser considerada um problema de mineração de dados), estamos realmente tentando extrair informações correlacionando todas as partes de grandes corpora. Então a complexidade assintótica se torna extremamente relevante. Infelizmente, não tenho nenhum problema específico em mente, provavelmente porque esses sistemas têm um objetivo pragmático, e as pessoas que os desenvolvem tenderão a simplesmente evitar qualquer forma de maior complexidade, provavelmente quadrática, além dos recursos disponíveis. Mas uma pesquisa na literatura provavelmente levantaria alguns problemas de complexidade.

Outro ponto é que a lingüística não possui leis claras como a física. É mais uma questão de estar perto o suficiente do que pode ser considerado consenso lingüístico atual, uma vez que duas pessoas não falam exatamente a mesma língua. Portanto, boas aproximações geralmente são suficientes quando o objetivo é tão esquivo. As técnicas que eu vi foram principalmente técnicas de ponto de correção para identificar parâmetros por recomputação iterativa de alguma função baseada na estrutura do corpus, até que não faça mais muita diferença (mais a entrada do usuário para eliminar os casos patológicos restantes).

Analisar propriedades de gramáticas e outras estruturas lingüísticas formalizadas também pode ser uma fonte de problemas de alta complexidade, como mencionado acima para ambiguidade, uma vez que as descrições de linguagem natural são geralmente grandes o suficiente para que a análise assintótica seja significativa.

como no meu comentário, às vezes a complexidade de P / NP, embora bastante poderosa, pode ser um martelo que faz com que todas as questões de complexidade pareçam pregos, e no campo da tradução de IA e linguagem com aspectos estatísticos, probabilísticos, de imprecisão e de aprendizado de máquina, pode não ser ser a medida ideal às vezes, e a complexidade computacional teórica nem sempre é considerada central ou relevante, especialmente no aprendizado de máquina / IA mais aplicado. de certa forma, todo o campo tem um aspecto mais empírico para medir a complexidade do problema aplicado. no entanto, aqui está um ângulo ainda não apontado em outras respostas, existem algumas considerações de P / NP na tradução da linguagem da PNL. por exemplo, esses dois papéis

• Tradução automática estatística baseada em frases como um problema de vendedor ambulante / Zaslavskiy, Dymetman, Cancedda

• Complexidade Computacional da Tradução Estatística por Máquina / Udupa, Magi

  Provamos que, embora os Modelos 1-2 da IBM sejam conceitualmente e computacionalmente simples, os cálculos envolvendo os modelos mais altos (e mais úteis) são difíceis. Como é improvável que exista uma solução de tempo polinomial para qualquer um desses problemas difíceis (a menos que$P = NP$ e $P^{\#P} = P$), nossos resultados destacam e justificam a necessidade de desenvolver aproximações de tempo polinomial para esses cálculos.