algorithm - grams - ngram googl

"Anagrama solver" basado en estadísticas en lugar de un diccionario/tabla?

Question

Mi problema es conceptualmente similar a resolver anagramas, excepto que no puedo usar una búsqueda de diccionario. Estoy tratando de encontrar palabras plausibles en lugar de palabras reales.

He creado un modelo de N-gramas (por ahora, N = 2) basado en las letras en un montón de texto. Ahora, dada una secuencia aleatoria de letras, me gustaría permutarlas en la secuencia más probable de acuerdo con las probabilidades de transición. Pensé que necesitaría el algoritmo de Viterbi cuando comencé esto, pero a medida que miro más profundo, el algoritmo de Viterbi optimiza una secuencia de variables aleatorias ocultas basadas en la salida observada. Estoy tratando de optimizar la secuencia de salida.

¿Hay algún algoritmo conocido para esto sobre el que pueda leer? ¿O estoy en el camino correcto con Viterbi y simplemente no estoy viendo cómo aplicarlo?

Actualizar

He agregado una recompensa para pedir más información sobre este problema. (Análisis que explica por qué no es posible un enfoque eficiente, otras heurísticas / aproximaciones además del recocido simulado, etc.)

Answer 1

Como ejercicio, escribí una implementación simple de Markov Chains en MATLAB. Básicamente es un modelo probabilístico basado en letras para generar palabras.

function mc = MC(numStates)
    N = numStates;
    PI = ones(1,N)/N;
    TR = ones(N,N)/N;
    mc = struct(''logprob'',@logprob, ''train'',@train, ...
                ''sample'',@sample, ''sampleFiltered'',@sampleFiltered);

    function train(seqs)
        PI = 1 + histc(cellfun(@(c)c(1), seqs)'', 1:N); %#''
        TR = ones(N,N);
        for i=1:numel(seqs)
            ind = sub2ind([N N], seqs{i}(1:end-1), seqs{i}(2:end));
            TR = TR + reshape(histc(ind,1:N*N), [N N]);
        end
        PI = bsxfun(@rdivide, PI, sum(PI,2)+(sum(PI,2)==0));
        TR = bsxfun(@rdivide, TR, sum(TR,2)+(sum(TR,2)==0));
    end

    function seq = sample(len)
        seq = zeros(1,len);
        seq(1) = randsample(1:N, 1, true, PI);
        for t=2:len
            seq(t) = randsample(1:N, 1, true, TR(seq(t-1),:));
        end
    end

    function seq = sampleFiltered(allowed)
        len = numel(allowed);
        seq = zeros(1,len);
        seq(1) = randsample(allowed, 1, true, PI(allowed));
        allowed( find(allowed==seq(1),1,''first'') ) = [];
        for t=2:len-1
            seq(t) = randsample(allowed, 1, true, TR(seq(t-1),allowed));
            allowed( find(allowed==seq(t),1,''first'') ) = [];
        end
        seq(t) = allowed;
        seq = seq(seq~=0);
    end

    function LL = logprob(seq)
        LL = log(PI(seq(1))) + ...
             sum( log(TR(sub2ind([N N],seq(1:end-1),seq(2:end)))) );
    end
end

Necesitaremos algunos textos para entrenar el modelo. Usamos ''The Wonderful Wizard of Oz'' del Proyecto Gutenberg.

%# read the text document
str = lower( urlread(''http://www.gutenberg.org/files/55/55.txt'') );
SP = char(32);                        %# delimiter (space)
str( ~isstrprop(str, ''alpha'') ) = SP; %# replace non-letters with spaces
str( findstr(str, [SP SP]) ) = [];    %# consecutive spaces as one
idx = ( str == SP );                  %# location of spaces
df = diff([1 idx 1]);
len = find(df > 0) - find(df < 0);    %# length of each word
[seqs gn] = grp2idx( str(~idx)'' );    %#'' map letters to numbers starting from 1
seqs = mat2cell(seqs'', 1, len)'';      %# put each word in a separate cell
N = length(gn);                       %# A to Z

Finalmente, usamos el modelo para muestrear palabras aleatorias o palabras de muestra de un conjunto de letras:

%# train Markov chain
mc = MC(N);
mc.train(seqs);

%# sample a random word
seq = mc.sample( randi([3 10]) );
fprintf(''word = %s , logP(word)=%f/n'', [gn{seq}], mc.logprob(seq))

%# sample a word from a set of letters
letters = lower(''markovchains'');
lettersIdx = cellfun(@(c) find(strcmp(c,gn)), cellstr(letters''));   %#''
seq = mc.sampleFiltered(lettersIdx);
fprintf(''word = %s , logP(word)=%f/n'', [gn{seq}], mc.logprob(seq))

Aquí hay un grupo de ejemplos generados a partir de las letras ''markovchains'', junto con la probabilidad logarítmica de la palabra dada al modelo:

word = mivorancask , logP(word)=-29.610819
word = arknoamshiv , logP(word)=-32.496090
word = ancoramshik , logP(word)=-29.299897
word = orchisankav , logP(word)=-29.987204
word = avinchasorm , logP(word)=-27.178507
word = aronchaskim , logP(word)=-25.651964

Puedes ver que, aunque ninguna es una palabra correcta, son mejores que solo una secuencia aleatoria de letras. Obviamente, usar solo el personaje anterior para generar el siguiente no es suficiente, aún así se puede extender fácilmente a casos más sofisticados (N-gramo).

Lo bueno de este enfoque es que no está restringido a un idioma, y ​​se puede adaptar a cualquier otro simplemente alimentándolo con documentos de su idioma de elección.

Answer 2

Considere el conjunto de letras K como vértices en un gráfico.

Agregue los bordes dirigidos para representar los 2 gramos de cada letra a todos los demás, con pesos que correspondan a sus probabilidades.

Una "palabra", entonces, es una ruta a través del gráfico (completo, dirigido).

Está buscando la "palabra" (ruta) mejor (menos o más ponderada) que utiliza todas las letras (visita todos los vértices).

Este es el problema asimétrico del vendedor ambulante . Es NP-completo. No creo que sea más fácil si usa N-grams mayor que N = 2, por lo que no es probable que encuentre un algoritmo eficiente, pero háganos saber si lo hace

(El recocido simulado o algo así es probablemente el camino a seguir)

Answer 3

Si entiendo su problema correctamente, está buscando todas las permutaciones de letras en una palabra para la que tiene el producto más bajo de probabilidades de 2 gramos.

Si su palabra es demasiado larga para simplemente forzar todas las combinaciones, he descubierto que los algoritmos de optimización estocástica producen buenos resultados en poco tiempo. Yo (que tengo una formación matemática) he hecho algo de trabajo en el algoritmo " Recocido simulado ", que creo que encajaría muy bien con su problema. Y es bastante fácil de implementar.

Answer 4

También podría hacerlo estocásticamente con una cadena de Markov. Para empezar, asegúrese de que su tabla N-gram incluya un símbolo de "principio de palabra"; luego, encuentre las transiciones disponibles de ese estado y filtrelas para que solo incluyan las letras disponibles de su grupo, y elija aleatoriamente entre ellas usando probabilidades ponderadas. Luego, encuentre las transiciones desde el siguiente estado, filtrando hasta las letras que aún están disponibles, y termine cuando ya no haya más letras en el grupo (o, si llega a un estado que no puede hacer la transición, regrese al comenzando e intente de nuevo).

En realidad, puede resultar útil que esto sea más aleatorio que algunas de las otras opciones disponibles, y si es demasiado aleatorio tiene la opción de masajear las probabilidades, o simplemente generar un número n (digamos 100) de palabras aleatorias, ordenándolas por su "verosimilitud", y luego elegir aleatoriamente de entre los mejores m (quizás 10), lo que le da un control relativamente fino sobre si las palabras que genera de cualquier bolsa de letras son más consistentes o más aleatorias.