20

私の問題は、概念的にはアナグラムを解くのと似ていますが、辞書検索だけを使用することはできません。本当の言葉ではなく、もっともらしい言葉を見つけようとしています。

一連のテキストの文字に基づいて N-gram モデル (今のところ、N=2) を作成しました。ここで、文字のランダムなシーケンスが与えられたので、遷移確率に従って、それらを最も可能性の高いシーケンスに並べ替えたいと思います。これを始めたときは、ビタビ アルゴリズムが必要だと思っていましたが、詳しく調べてみると、ビタビ アルゴリズムは、観測された出力に基づいて一連の隠れ確率変数を最適化します。出力シーケンスを最適化しようとしています。

これについて読むことができるよく知られたアルゴリズムはありますか? それとも、Viterbi で正しい方向に進んでいるのに、それを適用する方法がわかりませんか?

アップデート

この問題についてより多くの洞察を求めるために報奨金を追加しました。(効率的なアプローチが不可能な理由を説明する分析、シミュレーテッド アニーリング以外のヒューリスティック/近似など)

4

4 に答える 4

5

K 文字のセットをグラフの頂点と見なします。

各文字から他のすべての文字への 2 グラムを表す有向辺を、それらの確率に対応する重みで追加します。

したがって、「単語」は、(完全な有向) グラフを通るパスです。

すべての文字を使用する (すべての頂点にアクセスする) 最適な (重みが最小または最大の) "単語" (パス) を探しています。

これが非対称巡回セールスマン問題です。NP完全です。N=2 より大きい N グラムを使用しても簡単にはならないので、効率的なアルゴリズムが見つからない可能性がありますが、そうでしたらお知らせください。

(シミュレートされたアニーリングまたはそのようなものがおそらく進むべき道です)

于 2010-07-23T06:54:44.340 に答える
5

演習として、マルコフ連鎖の簡単な実装を 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

モデルをトレーニングするにはテキストが必要です。Project Gutenberg の「The Wonderful Wizard of Oz」を使用しています。

%# 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) に簡単に拡張できます。

このようなアプローチの良いところは、1 つの言語に限定されず、選択した言語からドキュメントをフィードするだけで他の言語に適応できることです。

于 2010-07-27T05:57:09.987 に答える
3

私があなたの問題を正しく理解していれば、単語内の文字のすべての順列を検索して、2 グラムの確率の積が最も低いものを探しています。

あなたの言葉が長すぎてすべての組み合わせを単純に総当たり攻撃できない場合は、確率的最適化アルゴリズムが短時間で良い結果をもたらすことがわかりました。私（数学のバックグラウンドを持つ）は、アルゴリズム「シミュレーテッドアニーリング」についていくつかの作業を行いました。これは、あなたの問題にうまく適合すると思います。そして、実装は非常に簡単です。

于 2010-04-16T06:26:33.133 に答える
0

マルコフ連鎖を使って確率的に行うこともできます。手始めに、N-gram テーブルに「単語の先頭」記号が含まれていることを確認してください。次に、その状態から利用可能な遷移を見つけ、プールから利用可能な文字のみが含まれるようにそれらをフィルタリングし、加重確率を使用してそれらの中からランダムに選択します。次に、次の状態からの遷移を見つけて、まだ利用可能な文字に絞り込み、プールに文字がなくなったら終了します (または、遷移できない状態に達した場合は、元の状態に戻ります)。始めてからやり直してください）。

これが他の利用可能なオプションのいくつかよりもランダムであることは、実際には便利だと思うかもしれません。ランダムすぎる場合は、確率をマッサージするか、単純にn個（たとえば100個）のランダムな単語を生成して、その「可能性」を調べ、上位m 個(おそらく 10 個) の中からランダムに選択します。これにより、文字の袋から生成する単語がより一貫しているか、よりランダムであるかを比較的細かく制御できます。

于 2010-07-25T08:48:44.873 に答える