Les algorithmes pour identifier le contenu généré par Markov?
https://stackoverflow.com/questions/1185369
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
chaînes de Markov sont (presque standard) moyen de générer charabia aléatoire qui semble intelligent pour un œil non averti. Comment feriez-vous sur l'identification du texte généré markoviens de texte écrit humaine.
Il serait génial si les ressources vous pointez sur Python sont sympathiques.
La solution
Vous pouvez utiliser une approche « force brute », par laquelle vous comparez la langue générée aux données recueillies sur n-grammes d'ordre plus élevé que le modèle de Markov qui l'a généré.
i.e.. Si la langue a été générée avec un 2ème modèle de Markov d'ordre, jusqu'à 3 grammes vont avoir les fréquences correctes, mais 4-grammes ne sera probablement pas.
Vous pouvez obtenir jusqu'à des fréquences de 5 grammes de public Google n-gramme 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, donc il vous suffit de stocker les comptes (ou fréquences) d'une manière qui est rapide à rechercher. Une base de données correctement indexé, ou peut-être un indice Lucene devrait fonctionner.
Étant donné un morceau de texte, balayez et rechercher la fréquence de chaque 5 grammes dans votre base de données, et de voir où elle se classe par rapport aux autres 5 grammes qui commencent par les mêmes 4 mots.
En pratique, un plus grand obstacle pourrait être les conditions de licence de l'ensemble de données. Son utilisation pour une application commerciale peut être interdite.
Autres conseils
Une approche simple serait d'avoir un grand groupe d'humains lire le texte d'entrée pour vous et voir si le texte est logique. Je suis seulement la moitié plaisantant, c'est un problème délicat.
Je crois que cela est un problème difficile, car la chaîne de Markov généré texte va avoir beaucoup des mêmes propriétés du texte réel humain en termes de fréquence des mots et des relations simples entre l'ordre des mots.
Les différences entre réel texte et le texte généré par une chaîne de Markov sont des règles de niveau supérieur de la grammaire et sens sémantique, qui sont difficiles à coder un programme. L'autre problème est que les chaînes de Markov sont assez bonnes à générer du texte qu'ils viennent parfois avec grammaticalement et sémantiquement déclarations correctes.
À titre d'exemple, voici un de la kantmachine:
Aujourd'hui, il se sentirait convaincu que la volonté humaine est libre; demain, compte tenu de la chaîne de indissoluble la nature, il regardait la liberté comme simple illusion et déclarer la nature à être tout en tout.
Bien que cette chaîne a été écrit par un programme informatique, il est difficile de dire qui un être humain jamais dire cela.
Je pense que si vous pouvez nous donner des détails plus précis sur l'ordinateur et le texte d'origine humaine qui exposent des différences plus évidentes, il sera difficile de résoudre ce en utilisant la programmation informatique.
Je suggère une généralisation de la réponse de Evan: faire un modèle de Markov de votre propre et de former avec une grande partie de l'échantillon (très grand) que vous avez donné, réservant le reste de l'échantillon comme des « données de test ». Maintenant, voyez comment bien le modèle que vous avez formé sur les données fait de test, par exemple avec un test de chi carré qui suggère la situation dans laquelle « ajustement est trop bon » (ce qui suggère que les données de test est en effet généré par ce modèle), ainsi que ceux dans lesquels l'ajustement est très mauvaise (suggérant une erreur dans la structure du modèle - un plus modèle -formées avec la mauvaise structure fait un travail notoirement mauvais dans ce cas).
Bien sûr, il y a encore beaucoup de problèmes pour l'étalonnage, tels que la structure du modèle - suspectent vous un modèle simple basé sur Ntuples des mots et un peu plus, ou plus sophistiqué avec des états de grammaire et autres. Heureusement, vous pouvez calibrer les choses assez bien en utilisant de grands corpus de connus à être naturel texte et aussi ceux que vous vous générer des modèles de différentes structures.
Une autre approche consiste à utiliser NLTK pour analyser les phrases que vous avez donné - un petit nombre de mis-Parsis est à prévoir, même dans le texte naturel (comme les humains sont imparfaits et est donc l'analyseur - il ne peut pas savoir ce mot X peut être utilisé comme un verbe et ne le classer comme un nom, etc, etc), mais la plupart des modèles de Markov (à moins qu'ils ne modélisation essentiellement la même structure grammaticale votre analyseur arrive à l'aide - et vous pouvez utiliser plusieurs parseurs pour essayer de contrer cette -) causeront beaucoup plus mis-Parsis que même les humains dyslexiques. Encore une fois, calibrer que sur les ressources naturelles vs textes synthétiques, et vous verrez ce que je veux dire -)
Si vous aviez plusieurs grands textes générés par Markov, vous pourriez peut-être déterminer si elles étaient si en comparant les fréquences de mots entre chacun des échantillons. Etant donné que les chaînes de Markov dépendent des probabilités de mot constante, les proportions d'un mot donné doivent être à peu près égal d'échantillon à échantillon.
crowdsourcing. Utilisez Mechanical Turk et obtenir un certain nombre d'humains à voter à ce sujet. Il y a même des bibliothèques pour vous aider à retirer ceci. Par exemple:
Voici un blog de Radar O'Reilly sur les conseils pour l'utilisation de Mechanical Turk pour obtenir votre travail:
Si vous écrire un programme qui génère des probabilités de transition markoviens de toute séquence de symboles, et calcule alors le débit d'entropie de la matrice de Markov. (Voir http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains ) Cette est essentiellement une estimation de la facilité avec laquelle le texte pourrait être prédite en utilisant seulement la chaîne de Markov (signifie une plus grande entropie plus difficile à prévoir). Par conséquent, je pense que plus l'entropie de la matrice est markov, plus il est probable que l'échantillon de texte est contrôlé par une matrice de markov. Si vous avez des questions sur la façon d'écrire ce code, j'arrive d'avoir un programme en python qui fait exactement cela sur mon ordinateur, je peux vous aider
