“Solucionador de anagramas” baseado em estatísticas em vez de um dicionário/tabela?

Question

Meu problema é conceitualmente semelhante à resolução de anagramas, exceto que não posso simplesmente usar uma pesquisa no dicionário.Estou tentando encontrar palavras plausíveis em vez de palavras reais.

Eu criei um modelo de N-gramas (por enquanto, N=2) baseado nas letras de um monte de texto.Agora, dada uma sequência aleatória de letras, gostaria de permutá-las na sequência mais provável de acordo com as probabilidades de transição.Eu pensei que precisaria do Algoritmo de Viterbi quando comecei isso, mas olhando mais a fundo, o algoritmo de Viterbi otimiza uma sequência de variáveis ​​​​aleatórias ocultas com base na saída observada.Estou tentando otimizar a sequência de saída.

Existe um algoritmo bem conhecido para isso sobre o qual eu possa ler?Ou estou no caminho certo com o Viterbi e simplesmente não estou vendo como aplicá-lo?

Atualizar

Eu adicionei uma recompensa para pedir mais informações sobre esse problema.(Análise explicando por que uma abordagem eficiente não é possível, outras heurísticas/aproximações além do recozimento simulado, etc.)

Answer 1

Se entendi seu problema corretamente, você está pesquisando em todas as permutações de letras em uma palavra aquela com o menor produto de probabilidades de 2 gramas.

Se sua palavra for muito longa para simplesmente forçar todas as combinações, descobri que algoritmos de otimização estocástica produzem bons resultados em pouco tempo.Eu (com formação matemática) fiz alguns trabalhos no algoritmo "Recozimento simulado", o que acho que se encaixaria perfeitamente no seu problema.E é muito fácil de implementar.

Answer 2

Como exercício, escrevi uma implementação simples de Cadeias de Markov no MATLAB.Basicamente, é um modelo probabilístico baseado em letras para gerar palavras.

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

Precisaremos de algum texto para treinar o modelo.Usamos 'O Maravilhoso Mágico de Oz' do Projeto 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 o modelo para amostrar palavras aleatórias ou amostras de palavras de um 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))

Aqui estão alguns exemplos gerados a partir das letras 'markovchains', junto com o log-probabilidade da palavra dado o 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

Você pode ver que, embora nenhuma palavra seja correta, elas ainda são melhores do que apenas uma sequência aleatória de letras.Obviamente usar apenas o caractere anterior para gerar o próximo não é suficiente, mas pode ser facilmente estendido para casos mais sofisticados (N-grama).

O bom dessa abordagem é que ela não está restrita a um idioma e pode ser adaptada para qualquer outro, simplesmente alimentando-a com documentos do idioma de sua escolha.

Answer 3

Considere o conjunto de K letras como vértices em um gráfico.

Adicione arestas direcionadas para representar os 2 gramas de cada letra para todas as outras, com pesos que correspondam às suas probabilidades.

Uma "palavra", então, é um caminho através do gráfico (completo, direcionado).

Você está procurando a melhor "palavra" (caminho) (com menor ou maior peso) que usa todas as letras (visita todos os vértices).

Isto é o Problema do caixeiro viajante assimétrico.É NP-completo.Não acho que será mais fácil se você usar N-gramas maiores que N = 2, então provavelmente não encontrará um algoritmo eficiente, mas informe-nos se encontrar

(Recozimento simulado ou algo parecido é provavelmente o caminho a percorrer)

Answer 4

Você também poderia fazer isso estocasticamente com uma cadeia de Markov.Para começar, certifique-se de que sua tabela de N-gramas inclua um símbolo de “início de palavra”;em seguida, encontre as transições disponíveis nesse estado e filtre-as para que incluam apenas letras disponíveis do seu pool e escolha aleatoriamente entre elas usando probabilidades ponderadas.Em seguida, encontre as transições do próximo estado, filtrando até as letras ainda disponíveis, e termina quando não houver mais letras no conjunto (ou, se você atingir um estado do qual não pode fazer a transição, volte ao início e tente novamente).

Você pode realmente achar útil que isso seja mais aleatório do que algumas das outras opções disponíveis, e se for também aleatório você tem a opção de massagear as probabilidades ou simplesmente gerar algum número n (digamos 100) de palavras aleatórias, classificando-as por sua "probabilidade" e, em seguida, escolhendo aleatoriamente entre as primeiras eu (talvez 10), o que lhe dá um controle relativamente preciso sobre se as palavras geradas a partir de qualquer conjunto de letras são mais consistentes ou mais aleatórias.