Le catene Markov sono un modo (quasi standard) di generare random gibberish che sembra intelligente per gli occhi inesperti. Come andresti a identificare il testo generato da markov dal testo scritto umano.Algoritmi per identificare il contenuto generato da Markov?
Sarebbe fantastico se le risorse a cui si punta fossero compatibili con Python.
Potresti usare un approccio "forza bruta", in cui confronti la lingua generata con i dati raccolti su n-grammi di livello superiore ordine rispetto al modello Markov che lo ha generato.
Ad esempio, se la lingua è stata generata con un modello Markov del 2 ° ordine, fino a 3 grammi avranno le frequenze corrette, ma probabilmente non lo saranno 4 grammi.
È possibile ottenere fino a frequenze di 5 grammi da Google pubblica n-gram dataset. È enorme anche se - 24G compressa - è necessario farlo per posta su DVD da LDC.
EDIT: aggiunto alcuni dettagli di implementazione
I n-grammi sono già stati contati, quindi è solo bisogno di memorizzare i conteggi (o frequenze) in un modo che è veloce per la ricerca. Un database indicizzato correttamente, o forse un indice di Lucene dovrebbe funzionare.
Dato un pezzo di testo, scansionarlo e cercare la frequenza di ogni 5 grammi nel tuo database, e vedere dove si colloca rispetto agli altri 5 grammi che iniziano con le stesse 4 parole.
Praticamente, un ostacolo più grande potrebbe essere il termine di licenza del set di dati. Usarlo per un'app commerciale potrebbe essere vietato.
Se disponevi di numerosi testi generati da Markov di grandi dimensioni, è possibile determinare che lo fossero confrontando le frequenze di parola tra ciascun campione. Poiché le catene di Markov dipendono dalle probabilità di parola costante, le proporzioni di ogni parola data dovrebbero essere approssimativamente uguali da un campione all'altro.
Si potrebbe anche pagare per guardare il toolkit del linguaggio naturale basato su python: http://nltk.sourceforge.net/ - detto questo, potrebbe essere un po 'eccessivo se sei interessato solo alle frequenze delle parole. – Markus
Se le frequenze di parola sono generate per apparire come testo reale potresti avere problemi se lavori con frequenze di parole come il ... – Janusz
Il problema con questo approccio è che se il testo generato dall'uomo e il testo generato dalla catena di Markov sono fatti da testo con frequenze di transizione di parole e parole simili, il testo generato dalla catena di Markov sarà simile al testo generato dall'uomo. –
Un approccio semplice sarebbe avere un grande gruppo di persone che legge il testo di input per te e vedere se il testo ha senso. Sto solo scherzando, questo è un problema complicato.
Credo che questo sia un problema difficile, perché il testo generato dalla catena di Markov avrà molte delle stesse proprietà del testo umano reale in termini di frequenza delle parole e relazioni semplici tra l'ordine delle parole.
Le differenze tra testo reale e testo generato da una catena di Markov sono nelle regole di grammatica e nel significato semantico di livello superiore, che sono difficili da codificare a livello di codice. L'altro problema è che le catene di Markov sono abbastanza buone per generare del testo che a volte escogitano affermazioni grammaticalmente e semanticamente corrette.
A titolo di esempio, ecco un aphorism from the kantmachine:
Oggi, si sarebbe sentito convinto che la volontà umana è libera; Domani, considerando la natura indissolubile della natura , avrebbe guardato alla libertà come una semplice illusione e dichiarare la natura come all-in-all.
Mentre questa stringa è stata scritta da un programma per computer, è difficile dire che un essere umano non lo direbbe mai.
Penso che se non ci puoi fornire dettagli più specifici sul computer e sul testo generato dall'uomo che espongono le differenze più evidenti sarà difficile risolverlo utilizzando la programmazione del computer.
Questo è piuttosto inquietante, infatti. Ho letto Critique of Pure Reason (l'unica opera di Kant I potrebbe davvero essere in grado di leggere/comprendere) e, non direi MAI, che l'aforisma sia generato da una macchina. – shylent
@shylent - questo è stato il quarto successo della pagina, e sono d'accordo, è molto nello stile di Kant. Questo sarebbe un ottimo esempio per un corso che coinvolge le catene di Markov! –
Crowdsourcing. Usa Mechanical Turk e ottieni un numero di umani per votare su questo. Ci sono persino alcune librerie per aiutarti a fare questo. Per esempio:
Ecco un post sul blog da O'Reilly Radar su consigli per l'utilizzo di Mechanical Turk per il proprio lavoro:
Suggerisco una generalizzazione della risposta di Evan: crea un tuo modello Markov e allenalo con una grossa fetta di il campione (molto grande) che ti viene dato, riservando il resto del campione come "dati di test". Ora, guarda quanto bene il modello che hai allenato fa sui dati del test, ad es.con un test chi quadrato che suggerirà una situazione in cui "l'adattamento è TROPPO buono" (suggerendo che i dati del test sono effettivamente generati da questo modello) e quelli in cui l'adattamento è pessimo (suggerendo un errore nella struttura del modello - un -trovato modello con la struttura sbagliata fa un lavoro notoriamente cattivo in questi casi).
Ovviamente ci sono ancora molti problemi per la calibrazione, come la struttura del modello - sospetti un modello semplice basato su Ntuple di parole e poco più, o uno più sofisticato con stati grammaticali e simili. Fortunatamente è possibile calibrare le cose abbastanza bene utilizzando grandi corpora di testo noto come naturale e anche quelli che si generano con modelli di varie strutture.
Un approccio diverso è quello di utilizzare nltk per analizzare le frasi che vengono fornite - un numero esiguo di errori di lettura è da aspettarsi anche nel testo naturale (poiché gli utenti sono imperfetti e quindi il parser - potrebbe non sapere che la parola X può essere usata come un verbo e classificarla come un nome, ecc. ecc.), ma la maggior parte dei modelli di Markov (a meno che non modellano essenzialmente la stessa struttura grammaticale usata dal parser - e tu puoi usa diversi parser per cercare di neutralizzarlo! -) causerà VASTAMENTE più mis-parses che persino gli umani dislessici. Ancora una volta, calibralo sui testi naturali e sintetici e vedrai cosa intendo! -)
Se si scrive un programma che genera probabilità di transizione markoviana da qualsiasi sequenza di simboli, quindi calcola la frequenza di entropia della matrice markov. (vedi http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains) Si tratta fondamentalmente di una stima della facilità con cui il testo potrebbe essere previsto usando solo la catena markov (maggiore entropia significa più difficile da prevedere). Quindi penserei che più è bassa l'entropia della matrice markov, più è probabile che il campione di testo sia controllato da una matrice markov. Se hai domande su come scrivere questo codice, mi capita di avere un programma in python che fa esattamente questo sul mio computer, quindi posso aiutarti
Mi piace questo approccio, ma penso che questo sarebbe computazionalmente irrealizzabile? – agiliq
Non vedo come, ha aggiunto alcuni dettagli alla risposta. – pufferfish