Les chaînes de Markov sont un moyen (presque standard) de générer random gibberish qui semble intelligent pour les yeux non formés. Comment feriez-vous pour identifier le texte généré par markov à partir de texte écrit?Algorithmes permettant d'identifier le contenu généré par Markov?
Ce serait génial si les ressources que vous indiquez sont compatibles avec Python.
Vous pourriez utiliser une approche de «force brute», par laquelle vous comparez la langue générée aux données recueillies sur n-grammes de plus haut ordre que le modèle de Markov qui l'a généré. C'est-à-dire que si la langue a été générée avec un modèle de Markov de second ordre, jusqu'à 3 grammes auront les bonnes fréquences, mais probablement pas 4 grammes.
Vous pouvez obtenir jusqu'à des fréquences de 5 grammes de Google publics de n-gram dataset. Il est énorme si - 24G comprimé - vous devez l'obtenir par la poste sur DVD de LDC.
EDIT: Ajout de quelques détails de mise en œuvre
Les n-grammes ont déjà été comptés, vous avez juste besoin donc de stocker les comptes (ou fréquences) d'une manière qui est rapide à rechercher. Une base de données correctement indexée, ou peut-être un index Lucene devrait fonctionner.
Pour une partie de texte, parcourez le et cherchez la fréquence de chaque 5 grammes dans votre base de données, et voyez où elle se classe par rapport aux autres 5 grammes qui commencent par les mêmes 4 mots. En pratique, les conditions de licence de l'ensemble de données constituent un obstacle plus important. L'utiliser pour une application commerciale peut être interdit.
Si vous aviez plusieurs grands textes générés par Markov, vous pourriez éventuellement déterminer qu'ils l'étaient en comparant les fréquences des mots entre chacun des échantillons. Puisque les chaînes de Markov dépendent de probabilités de mots constantes, les proportions d'un mot donné devraient être approximativement égales d'un échantillon à l'autre.
Il peut aussi être payant de regarder la boîte à outils en langage naturel python: http://nltk.sourceforge.net/ - Cela dit, il pourrait être un peu excessif si vous êtes juste intéressé par les fréquences des mots. – Markus
Si les fréquences de mots sont générées pour ressembler à du texte réel, vous pouvez avoir des problèmes si vous travaillez avec des fréquences de mots comme le ... – Janusz
Le problème avec cette approche est que si le texte généré par l'homme et le texte généré par la chaîne de Markov sont faits de texte avec des fréquences de transition de mots et de mots similaires, le texte généré par la chaîne de Markov ressemblera beaucoup au texte généré par l'humain. –
Une approche simple consisterait à faire en sorte qu'un grand groupe d'humains lise le texte d'entrée pour vous et vérifie si le texte a du sens. Je ne fais que plaisanter, c'est un problème délicat. Je crois que c'est un problème difficile, parce que le texte généré par une chaîne de Markov va avoir beaucoup des mêmes propriétés du vrai texte humain en termes de fréquence des mots et de relations simples entre l'ordre des mots. Les différences entre le texte réel et le texte généré par une chaîne de Markov se trouvent dans les règles de grammaire et de signification sémantique de niveau supérieur, qui sont difficiles à coder par programmation. L'autre problème est que les chaînes de Markov sont assez bonnes pour générer du texte, ce qui arrive parfois avec des instructions grammaticalement et sémantiquement correctes.
À titre d'exemple, voici un aphorism from the kantmachine:
Aujourd'hui, il se sentirait convaincu que la volonté humaine est libre; demain, compte tenu de la chaîne indissoluble de nature, il regarderait la liberté comme une simple illusion et déclarerait que la nature est tout-en-tout.
Bien que cette chaîne ait été écrite par un programme informatique, il est difficile de dire qu'un humain ne dirait jamais cela. Je pense qu'à moins que vous ne puissiez nous donner des détails plus précis sur l'ordinateur et le texte généré par l'homme qui exposent des différences plus évidentes, il sera difficile de résoudre cela en utilisant la programmation informatique.
C'est assez dérangeant, en fait. J'ai lu la Critique de la Raison Pure (le seul travail de Kant que je pourrais obtenir moi-même pour lire/comprendre) et, je ne dirais jamais, que l'aphorisme est généré par la machine. – shylent
@shylent - c'était le quatrième hit sur la page, et je suis d'accord, c'est très dans le style de Kant. Ce serait un très bon exemple pour un cours qui implique des chaînes de Markov! –
Crowdsourcing. Utilisez Mechanical Turk et demandez à un certain nombre d'humains de voter à ce sujet. Il y a même quelques bibliothèques pour vous aider à le faire. Par exemple:
Voici un blog de Radar O'Reilly sur les conseils pour l'utilisation de Mechanical Turk pour faire votre travail:
Je suggère une généralisation de la réponse d'Evan: faites votre propre modèle de Markov et entraînez-le avec un gros morceau de l'échantillon (très grand) qui vous est donné, en réservant le reste de l'échantillon en tant que "données de test". Maintenant, voyez à quel point le modèle que vous avez entraîné agit sur les données de test, par ex.avec un test du khi carré qui suggérera une situation dans laquelle «l'ajustement est TROP bon» (suggérant que les données de test sont effectivement générées par ce modèle) ainsi que celles dans lesquelles l'ajustement est très mauvais (suggérant une erreur dans la structure du modèle). modèle mal formé avec la mauvaise structure fait un travail notoirement mauvais dans de tels cas).
Bien sûr, il existe encore de nombreux problèmes d'étalonnage, tels que la structure du modèle: soupçonnez-vous un modèle simple basé sur Ntuples de mots et un peu plus, ou un modèle plus sophistiqué avec des états grammaticaux. Heureusement, vous pouvez très bien calibrer les choses en utilisant de gros corpus de textes connus pour être naturels et ceux que vous générez vous-même avec des modèles de structures diverses. Une approche différente consiste à utiliser nltk pour analyser les phrases qui vous sont attribuées - un petit nombre de erreurs d'analyse est à prévoir même dans un texte naturel (car les humains sont imparfaits, tout comme l'analyseur syntaxique). ne sait pas que le mot X peut être utilisé comme un verbe et le classer comme un nom, etc, etc), mais la plupart des modèles de Markov (à moins qu'ils ne modélisent essentiellement la même structure grammaticale que votre analyseur utilise - et vous pouvez utilisez plusieurs parseurs pour essayer de contrer cela! -) provoquera VASTEMENT plus de mauvaises analyses que même les humains dyslexiques. Encore une fois, calibrer cela sur les textes naturels vs synthétiques, et vous verrez ce que je veux dire! -)
Si vous écrivez un programme qui génère des probabilités de transition markoviennes à partir de n'importe quelle séquence de symboles, puis calcule le taux d'entropie de la matrice markov. (voir http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains) Il s'agit essentiellement d'une estimation de la facilité avec laquelle le texte pourrait être prédit en utilisant simplement la chaîne markov (entropie supérieure signifie plus difficile pour prédire). Par conséquent, je pense que plus l'entropie de la matrice markov est faible, plus l'échantillon de texte est contrôlé par une matrice markov. Si vous avez des questions sur la façon d'écrire ce code, il se trouve que j'ai un programme en python qui fait exactement cela sur mon ordinateur, donc je peux vous aider
J'aime cette approche, mais je pense que ce serait infaisable d'un point de vue informatique? – agiliq
Ne vois pas comment, ajouté quelques détails à la réponse. – pufferfish