Algoritmi per identificare Markov contenuti generati?
https://stackoverflow.com/questions/1185369
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Catene di Markov sono un modo (quasi normale) per generare incomprensibile casuale che sembra intelligente per un occhio inesperto. Come si va circa identificare Markov testo generato dal testo scritto umana.
Sarebbe fantastico se le risorse si punta a Python sono gentile.
Soluzione
È possibile utilizzare un approccio di "forza bruta", per cui si confronta il linguaggio generato i dati raccolti su n-grammi di ordine superiore rispetto al modello di Markov che lo ha generato.
vale a dire. Se la lingua è stata generata con un 2 ° ordine modello di Markov, fino a 3-grammi stanno per avere le frequenze corrette, ma a 4 grammi probabilmente non lo farà.
È possibile ottenere fino a frequenze di 5 grammi di Google pubblica n-gram dataset è enorme anche se - 24G compressa - è necessario farlo per posta in DVD di LDC .
EDIT: Aggiunto alcuni dettagli di implementazione
I n-grammi sono già stati contati, in modo che solo bisogno di memorizzare i conteggi (o frequenze) in un modo che è veloce per la ricerca. Un correttamente indicizzato del database, o forse un indice di Lucene dovrebbe funzionare.
Dato un pezzo di testo, eseguire la scansione attraverso di esso e cercare la frequenza di ogni 5 grammi nel database, e vedere dove si classifica rispetto ad altri 5-grammi che iniziano con le stesse 4 parole.
In pratica, un ostacolo più grande potrebbe essere i termini di licenza del set di dati. Usandolo per un'applicazione commerciale potrebbe essere proibito.
Altri suggerimenti
Un approccio semplice sarebbe quella di avere un grande gruppo di umani leggono testo di input per voi e vedere se il testo ha un senso. Sto scherzando solo a metà, questo è un problema difficile.
Credo che questo è un problema difficile, perché Markov-chain testo generato sta per avere un sacco di le stesse proprietà di vera e propria del testo umano in termini di frequenza delle parole e semplici rapporti tra l'ordinamento delle parole.
Le differenze tra il testo vero e proprio e il testo generati da una catena di Markov sono nelle regole di livello superiore di grammatica e nel significato semantico, che sono difficili da codificare a livello di codice. L'altro problema è che le catene di Markov sono abbastanza buoni a generare il testo che a volte venire con grammaticalmente e semanticamente affermazioni corrette.
A titolo di esempio, ecco un rel="noreferrer"> aforisma :
Oggi, si sarebbe sentito convinto che la volontà umana è libera; Domani, considerando la catena indissolubile la natura, guardava sulla libertà come mera illusione e dichiarare natura essere all-in-tutti.
Mentre questa stringa è stato scritto da un programma per computer, è difficile dire che un essere umano non avrebbe mai detto questo.
Credo che se non ci si può dare dettagli più specifici relativi al computer e il testo umana generati che espongono le differenze più evidenti sarà difficile risolvere questa programmazione computer utilizzando.
Suggerisco una generalizzazione della risposta di Evan: fare un modello di Markov della propria e formare con una grossa fetta del campione (molto grande) si è dato, riservando il resto del campione come "dati di prova". Ora, vedere come il modello che hai addestrato fa sui dati di test, per esempio con un test chi quadrato che suggeriscono situazione in cui "in forma è troppo buono" (che suggerisce i dati del test è infatti generato da questo modello), oltre a quelli in cui la forma è molto male (errore nella struttura del modello che suggerisce - un over il modello -formate con la struttura sbagliata fa un cattivo lavoro notoriamente in questi casi).
Naturalmente ci sono ancora molti problemi per la calibrazione, come ad esempio la struttura del modello - stai sospettare un semplice modello basato su Ntuples di parole e poco più, o un più sofisticato uno con gli stati di grammatica e simili. Fortunatamente è possibile calibrare le cose abbastanza bene utilizzando grandi corpora di quelli noti-to-be-naturali di testo e anche di generare da soli con i modelli di varie strutture.
Un approccio diverso è quello di utilizzare NLTK per analizzare le frasi si è dato - un piccolo numero di mis-analizza c'è da aspettarsi anche nel testo naturali (come gli esseri umani sono imperfetti e così è il parser - non può sapere che la parola X può essere usato come un verbo e solo classificarlo come un sostantivo, ecc, ecc), ma la maggior parte dei modelli di Markov (a meno che stanno modellando essenzialmente la stessa struttura grammaticale tuo parser capita di utilizzare - ed è possibile utilizzare diversi parser per cercare di contrastare questo -!) causerà molto più mis-analizza che anche gli esseri umani dislessici. Anche in questo caso, calibrare che il naturale vs testi sintetici, e vedrete cosa intendo -!)
Se avete avuto diversi grandi testi Markov-generati, si potrebbe stabilire che fossero così confrontando le frequenze di parole tra ciascuno dei campioni. Poiché catene di Markov dipendono probabilità dei termini costanti, le proporzioni di una data parola dovrebbe essere approssimativamente uguale da campione a campione.
Crowdsourcing. Utilizzare Mechanical Turk e ottenere un numero di esseri umani a votare su questo. Ci sono anche alcune librerie per aiutarti a tirare fuori questo. Ad esempio:
Ecco un post sul blog da O'Reilly Radar su consigli per l'utilizzo di Mechanical Turk per ottenere il vostro lavoro fatto:
Se si scrive un programma che genera probabilità di transizione Markoviane da qualsiasi sequenza di simboli, e quindi calcola il tasso di entropia di Markov. (Vedi http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains ) Questo è fondamentalmente una stima di quanto facilmente il testo potrebbe essere previsto utilizzando solo la catena di Markov (mezzi entropia superiori difficile per prevedere). Perciò io penserei che più basso è l'entropia della matrice di Markov è, più è probabile che il campione di testo è controllato da una matrice di Markov. Se avete domande su come scrivere questo codice, mi capita di avere un programma in python che fa esattamente questo sul mio computer, in modo da poter dare una mano
