Komplexität von Problemen bei der Verarbeitung natürlicher Sprache [geschlossen]

Welche Verarbeitungsprobleme in natürlicher Sprache sind NP-Complete oder NP-Hard?

Ich habe die gesucht natural-lang-verarbeitung und Komplexitätstheorie Tags (und zugehörige Komplexitäts-Tags), haben jedoch keine Ergebnisse erzielt.

Keine der empfohlenen NLP-Fragen ist hilfreich. Die nächsten sind die folgenden:

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

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

• Welche Aspekte der Linguistik sind für die Verarbeitung natürlicher Sprache notwendig oder gut?

In der Wikipedia-Liste der NP-vollständigen Probleme sind keine Komplexitätsergebnisse für NLP aufgeführt.

Der einzige Hinweis, den ich gefunden habe, ist die Arbeit Theoretische und effektive Komplexität in der Verarbeitung natürlicher Sprache von J. Morin (1995).

Jede Hilfe oder Hinweise wird geschätzt!

Die LFG- Erkennung (Lexical-Functional Grammar) ist NP-vollständig .

Auf Anfrage bearbeiten: Lexikalisch-funktionale Grammatik (LFG) [1] ist eine Theorie der Syntax natürlicher Sprache, die als Alternative zu Chomskys Theorien der Transformationssyntax entwickelt wurde. Einige Versionen von Chomskys Theorien entsprechen rechnerisch den uneingeschränkten Grammatiken. Im Gegensatz dazu bietet LFG einen Grammatikformalismus, der aus einer kontextfreien Grammatik besteht, die durch ein Feature-System erweitert wird.

Es ist das Funktionssystem, das NP-vollständig ist. Der Beweis funktioniert im Wesentlichen, indem erstens festgestellt wird, dass das Merkmalssystem mindestens so leistungsfähig ist wie die Aussagenlogik, und zweitens, dass die Grammatikalität darauf beruht, alle für den Satz maßgeblichen Satzbeschränkungen zu erfüllen. Es ist also das Problem der Zufriedenheit, das sich unter einem anderen Deckmantel versteckt.

[1] "Lexikalisch-funktionale Grammatik: Ein formales System zur grammatikalischen Darstellung" von Ronald M. Kaplan und Joan Bresnan. Das Papier erschien ursprünglich in The Mental Representation of Grammatical Relations , hrsg. Joan Bresnan (Cambridge, MA: MIT Press, 1982).

Vielleicht sollte man zuerst definieren, was ein Problem der Verarbeitung natürlicher Sprache (NLP) ist.

Zum Beispiel wurden kontextfreie (CF) Grammatiken und Sprachen von Linguisten eingeführt (Chomsky Typ 2 Sprache, Arbeit von Bar-Hillel und anderen). Mehrdeutigkeit ist ein Hauptproblem in der Linguistik für die Analyse realer Sätze und für das formale Studium von CF-Grammatiken (Mehrdeutigkeit) und Sprachen (inhärente Mehrdeutigkeit). Die Mehrdeutigkeit einer Grammatik ist nur halb entscheidbar.

Ich denke, das Problem der Mehrdeutigkeit sollte eine Antwort auf Ihre Frage sein. Wird es als NLP-Problem klassifiziert?

Wenn Sie nun einige moderne Syntaxformalisierungen wie ein CF-Backbone mit Feature-Strukturen (dh strukturierten Attributen) verwenden, erhalten Sie schnell Turing-Leistung (vgl. LFG, die sich je nach Variante als NP-hart oder sogar als Turing-vollständig erwiesen hat ). Wenn Sie also nicht aufpassen, haben Sie alle Komplexitätsprobleme, von denen Sie träumen könnten.

Weitere Informationen finden Sie auch in dieser Frage aus der SE-Linguistik: " Hat die P-gegen-NP-Vermutung in der Informatik eine direkte Relevanz für die Linguistik? "

In meiner eigenen Antwort kritisiere ich tatsächlich die Aussagekraft der Frage oder zumindest einige ihrer Interpretationen. Viele der Probleme, die in der Linguistik in Bezug auf die Analyse von Sätzen für Übersetzungen oder andere Zwecke berücksichtigt werden, sind kleine Probleme, die in sehr kurzer Zeit gelöst werden müssen. Einige Linguisten könnten sogar bestreiten, dass es eine echte Rekursion in der Sprachstruktur gibt, da jede Rekursion, die es gibt, selten sehr tief ist. Daher könnte man sich über die sprachliche Relevanz der Komplexitätsanalyse wundern, die asymptotisch definiert ist. Die erste Frage sollte sein, ob wir der Asymptote jemals nahe genug kommen, damit eine asymptotische Analyse sinnvoll ist.

Diese Bemerkung gilt jedoch nicht für einige Aspekte von NLP, wenn große Datenmengen verarbeitet werden müssen. Ich kenne mindestens zwei Fälle:

• Data Mining in großen Unternehmen.

• Das umgekehrte Problem der Linguistik: Analyse großer Korpora, um die eine Sprache charakterisierenden Daten mechanisch zu extrahieren, sowohl strukturell als auch um umfangreiche Listen von Bestandteilen wie Phoneme, Vokabeln für verschiedene Wortarten (auch bekannt als Preterminale ), Präfixe und Suffixe oder Flexionen zu erstellen Mechanismen, um einige Beispiele zu nennen.

Ich bin kein Experte für Data Mining und weiß daher nicht, ob dies tatsächlich zu Komplexitätsproblemen im Zusammenhang mit der Größe der zu verarbeitenden Korpora führt. In diesem Fall wäre die asymptotische Komplexität in der Tat ein Problem. Wenn es sich jedoch hauptsächlich aus einer großen Anzahl kleiner additiver Aufgaben zusammensetzt, ist es zweifelhafter, dass die asymptotische Komplexität von großer Bedeutung ist. Ich würde mir jedoch vorstellen, dass einige Data Mining-Techniken mit Korrelationen zwischen unabhängigen Dokumenten funktionieren und dass dies zu Problemen mit der korpusabhängigen Komplexität führen sollte.

Im Fall des inversen Problems der Linguistik, der Identifizierung einer Sprache (die vermutlich als Data-Mining-Problem angesehen werden könnte), versuchen wir tatsächlich, Informationen zu extrahieren, indem wir alle Teile großer Korpora korrelieren. Dann wird asymptotische Komplexität äußerst relevant. Ich habe leider kein spezifisches Problem im Sinn, wahrscheinlich weil solche Systeme ein pragmatisches Ziel haben und die Leute, die sie entwickeln, dazu neigen, einfach jede Form höherer Komplexität zu vermeiden, da quadratisch wahrscheinlich bereits über die verfügbaren Ressourcen hinausgeht. Eine Literaturrecherche würde jedoch wahrscheinlich einige Komplexitätsprobleme aufwerfen.

Ein weiterer Punkt ist, dass die Linguistik keine eindeutigen Gesetze wie die Physik hat. Es geht eher darum, dem aktuellen sprachlichen Konsens nahe genug zu sein, da keine zwei Personen genau dieselbe Sprache sprechen. Daher sind gute Annäherungen normalerweise ausreichend, wenn das Ziel so schwer zu erreichen ist. Die Techniken, die ich gesehen habe, waren hauptsächlich Fixpunkttechniken, um Parameter durch iterative Neuberechnung einer Funktion basierend auf der Korpusstruktur zu identifizieren, bis sie keinen großen Unterschied mehr macht (plus Benutzereingaben, um verbleibende pathologische Fälle auszusortieren).

Die Analyse der Eigenschaften von Grammatiken und anderen formalisierten Sprachstrukturen kann auch eine Quelle für Probleme mit hoher Komplexität sein, wie oben aus Gründen der Mehrdeutigkeit erwähnt, da Beschreibungen natürlicher Sprachen normalerweise groß genug sind, damit eine asymptotische Analyse sinnvoll ist.

Wie in meinem Kommentar kann P / NP-Komplexität manchmal, obwohl sie ziemlich mächtig ist, ein Hammer sein, der alle Komplexitätsfragen wie Nägel aussehen lässt, und im Bereich der KI- und Sprachübersetzung mit statistischen, probabilistischen, ungenauen und maschinellen Lernaspekten möglicherweise nicht Manchmal ist dies die ideale Messung, und die theoretische Komplexität der Berechnungen wird nicht immer als zentral oder relevant angesehen, insbesondere bei stärker angewandter KI / maschinellem Lernen. In gewisser Weise hat das gesamte Gebiet einen empirischeren Aspekt bei der Messung der Komplexität angewandter Probleme. Hier ist jedoch ein Winkel, auf den in anderen Antworten noch nicht hingewiesen wurde. Es gibt einige P / NP-Überlegungen bei der NLP-Sprachübersetzung. zB diese beiden Papiere

• Phrasenbasierte statistische maschinelle Übersetzung als reisender Verkäufer Problem / Zaslavskiy, Dymetman, Cancedda

• Computerkomplexität der statistischen maschinellen Übersetzung / Udupa, Magi

  Wir beweisen, dass IBM Modelle 1-2 zwar konzeptionell und rechnerisch einfach sind, Berechnungen mit den höheren (und nützlicheren) Modellen jedoch schwierig sind. Da es unwahrscheinlich ist, dass es für eines dieser schwierigen Probleme eine polynomielle Zeitlösung gibt (es sei denn$P = NP$ und $P^{\#P} = P$) unterstreichen und begründen unsere Ergebnisse die Notwendigkeit, für diese Berechnungen polynomielle Zeitnäherungen zu entwickeln.