algorithm - propiedad - proceso de markov

Explicar el algoritmo de la cadena de Markov en términos sencillos.

Question

No entiendo bien este Markov ... ¿se necesitan dos palabras, un prefijo y un sufijo guardan una lista de ellos y hacen una palabra al azar?

    /* Copyright (C) 1999 Lucent Technologies */
/* Excerpted from ''The Practice of Programming'' */
/* by Brian W. Kernighan and Rob Pike */

#include <time.h>
#include <iostream>
#include <string>
#include <deque>
#include <map>
#include <vector>

using namespace std;

const int  NPREF = 2;
const char NONWORD[] = "/n";    // cannot appear as real line: we remove newlines
const int  MAXGEN = 10000; // maximum words generated

typedef deque<string> Prefix;

map<Prefix, vector<string> > statetab; // prefix -> suffixes

void        build(Prefix&, istream&);
void        generate(int nwords);
void        add(Prefix&, const string&);

// markov main: markov-chain random text generation
int main(void)
{
    int nwords = MAXGEN;
    Prefix prefix;  // current input prefix

    srand(time(NULL));
    for (int i = 0; i < NPREF; i++)
        add(prefix, NONWORD);
    build(prefix, cin);
    add(prefix, NONWORD);
    generate(nwords);
    return 0;
}

// build: read input words, build state table
void build(Prefix& prefix, istream& in)
{
    string buf;

    while (in >> buf)
        add(prefix, buf);
}

// add: add word to suffix deque, update prefix
void add(Prefix& prefix, const string& s)
{
    if (prefix.size() == NPREF) {
        statetab[prefix].push_back(s);
        prefix.pop_front();
    }
    prefix.push_back(s);
}

// generate: produce output, one word per line
void generate(int nwords)
{
    Prefix prefix;
    int i;

    for (i = 0; i < NPREF; i++)
        add(prefix, NONWORD);
    for (i = 0; i < nwords; i++) {
        vector<string>& suf = statetab[prefix];
        const string& w = suf[rand() % suf.size()];
        if (w == NONWORD)
            break;
        cout << w << "/n";
        prefix.pop_front(); // advance
        prefix.push_back(w);
    }
}

Answer 1

Las cadenas de Markov son máquinas estatales con transiciones estatales que son probabilidades.

Palabra: Pollo; posibles siguientes palabras: 10% - es; 30% - fue; 50% - piernas; 10% - corre;

luego, simplemente elige la siguiente palabra al azar o mediante una selección de la rueda de la ruleta. Obtienes estas probabilidades de algún texto de entrada.

Answer 2

Según Wikipedia, una Cadena de Markov es un proceso aleatorio en el que el siguiente estado depende del estado anterior. Esto es un poco difícil de entender, así que intentaré explicarlo mejor:

Lo que estás viendo, parece ser un programa que genera una Cadena de Markov basada en texto. Esencialmente el algoritmo para eso es el siguiente:

1. Divide un cuerpo de texto en tokens (palabras, puntuación).
2. Construye una tabla de frecuencias. Esta es una estructura de datos donde, para cada palabra en su cuerpo de texto, tiene una entrada (clave). Esta clave se asigna a otra estructura de datos que es básicamente una lista de todas las palabras que siguen a esta palabra (la clave) junto con su frecuencia.
3. Generar la cadena de Markov. Para hacer esto, selecciona un punto de inicio (una clave de tu tabla de frecuencias) y luego seleccionas otro estado al azar para ir a (la siguiente palabra). La siguiente palabra que elija, depende de su frecuencia (por lo que algunas palabras son más probables que otras). Después de eso, usa esta nueva palabra como la clave y comienza de nuevo.

Por ejemplo, si observa la primera oración de esta solución, puede crear la siguiente tabla de frecuencia:

According: to(100%)
to:        Wikipedia(100%)
Wikipedia: ,(100%)
a:         Markov(50%), random(50%)
Markov:    Chain(100%)
Chain:     is(100%)
is:        a(33%), dependent(33%), ...(33%)
random:    process(100%)
process:   with(100%)
.
.
.
better:    :(100%)

Esencialmente, la transición de estado de un estado a otro se basa en la probabilidad. En el caso de una Cadena de Markov basada en texto, la probabilidad de transición se basa en la frecuencia de las palabras que siguen a la palabra seleccionada. Por lo tanto, la palabra seleccionada representa el estado anterior y la tabla de frecuencia o las palabras representan los (posibles) estados sucesivos. Encontrará el estado sucesivo si conoce el estado anterior (esa es la única forma de obtener la tabla de frecuencias correcta), por lo que encaja con la definición donde el estado sucesivo depende del estado anterior.

Shameless Plug - Hace un tiempo escribí un programa para hacer precisamente esto en Perl. Puedes leer sobre esto here .