是基于统计数据而非字典/表格的“字谜解算器”?
machine-learning
5
0

我的问题从概念上讲与解决字谜类似,只是我不能只使用字典查找。我试图找到合理的单词,而不是真实的单词。

我基于一堆文本中的字母创建了一个N元语法模型(目前为N = 2)。现在,给定一个随机的字母序列,我想根据转换概率将它们置换为最可能的序列。我以为开始时会需要维特比算法 ,但是从更深的角度看,维特比算法会根据观察到的输出优化一系列隐藏的随机变量。我正在尝试优化输出顺序。

有没有一种我可以阅读的知名算法?还是我在维特比(Viterbi)上走上正轨,只是不知道如何应用它?

更新资料

我增加了赏金,要求对这个问题有更多的了解。 (分析说明了为什么无法采用有效的方法,模拟退火以外的其他启发式/近似方法等)

参考资料:
Stack Overflow
收藏
评论
共 3 个回答
高赞 时间 活跃

作为练习,我在MATLAB中编写了马尔可夫链的简单实现。基本上,它是基于字母的概率模型来生成单词。

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

我们将需要一些文本来训练模型。我们使用古腾堡计划中的“绿野仙踪”。

%# 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

最后,我们使用该模型对随机单词或来自一组字母的单词进行采样:

%# 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))

这是从字母“ markovchains”生成的一堆示例,以及给定模型的单词的对数概率:

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

您会看到,尽管没有一个是正确的单词,但它们仍然比随机字母序列更好。显然仅使用前一个字符来生成下一个是不够的,但仍可以轻松地将其扩展到更复杂的情况(N-gram)。

这种方法的好处是它不仅限于一种语言,而且可以通过简单地从您选择的语言中馈送文档来适应任何其他语言。

收藏
评论

将K个字母集视为图形中的顶点。

添加有向边以表示从每个字母到所有其他字母的2克字母,其权重与它们的概率相对应。

那么,“单词”是通过(完整的,有向的)图的路径。

您正在寻找使用所有字母(访问所有顶点)的最佳(权重最低或权重最高的)“单词”(路径)。

这是非对称旅行商问题 。它是NP完整的。我认为如果使用大于N = 2的N-gram不会变得更容易,因此您不太可能找到有效的算法,但是请告诉我们

(模拟退火或类似方法可能是可行的方法)

收藏
评论

如果我正确理解了您的问题,那么您正在搜索单词中所有字母的排列,以寻找2克概率乘积最低的那个。

如果您说的话太长,无法简单地对所有组合进行暴力破解,那么我发现随机优化算法可在短时间内产生良好的效果。我(具有数学背景)已经对“ 模拟退火 ”算法做了一些工作,我认为它非常适合您的问题。而且很容易实现。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号