2次元配列を作成して値を入力し、配列を読み取ってまったく異なる値を取得するのに問題があります。奇妙なことに、2 つの配列を 2 つ保持しており、そのうちの 1 つは値を正しく格納しており、もう 1 つはそうではありません。私も要素を上書きしていないと確信しています。私は、C が苦手でない人には明らかな愚かなエラーを犯していると思います。
私はviterbi アルゴリズムを実装していることに注意してください。しかし、私が理解している一般的なアルゴリズムは Python で実装されています。これは、C の配列が私に悲しみを与えているだけです。
私がやっていること：
1) 2 つの配列を malloc します。これらは 2D 配列として使用されますが、連続したメモリ ブロックを割り当てます。ビタビ アルゴのフォワード ステップを通過する際に配列のすべてのエントリを入力する必要があるため、配列を明示的に初期化しません。
double *viterbi_table = malloc(sizeof(double) * n_samples * n_states);
int *best_path_table = malloc(sizeof(int) * n_samples * n_states);
2) ビタビ アルゴの前方部分については、観測データをウォークスルーし、各状態の最も可能性の高い状態と確率を計算します。
for (t = 1; t < n_samples; t++) // for each piece of observed data
{
for (i = 0; i < n_states; i++)
{
max_state_index = 0;
max_p = -DBL_MAX;
// calculate the max state and probability by looping through all the states
// yada yada...
// IMPORTANT PART: We set the array values here
viterbi_table[t * n_samples + i] = max_p;
best_path_table[t * n_samples + i] = max_state_index;
printf("\tbest_path_table[%d][%d] or [%d] = %d => %d\n",
i, t, t * n_samples + i, best_path_table[t * n_samples + i], max_state_index);
}
// IMPORTANT PART: print out rows of best path table to see if what we thought we inserted is in there
if (debug)
{
printf("best_path, [ ", t);
for (i = 0; i < n_states; i++)
{
printf("[%d], %d ", t * n_samples + i, best_path_table[t * n_samples + i]);
}
printf("]\n");
}
}
3) コードを実行すると、設定した配列要素が、設定したと思っていたものと一致する代わりに、初期化されていない要素のように見える大きな負または正の数値が得られます。何を与える？それらのブロックに値を割り当てました。問題を示す出力の選択された部分を次に示します。
t=36 => sample=X
best_path_table[0][36] or [1404] = 0 => 0
best_path_table[1][36] or [1405] = 0 => 0
best_path_table[2][36] or [1406] = 0 => 0
best_path_table[3][36] or [1407] = 0 => 0
...
best_path, [ [1404], 1399607453 [1405], -1070347604 [1406], 1399607453 [1407], 0 ... ]
対照的に、以下のものが正しいです。
t=37 => sample=X
best_path_table[0][37] or [1443] = 3 => 3
best_path_table[1][37] or [1444] = 3 => 3
best_path_table[2][37] or [1445] = 3 => 3
...
best_path, [ [1443], 3 [1444], 3 [1445], ... ]
12 個未満の観測など、短いデータに対してコードを実行すると、このような問題は発生しません。より長いデータに対して実行すると、ほとんどの最適パス テーブルが正しく入力されていません。パターンは次のようになります。
observation#
1) correct
2-3) garbage
4) correct
4-5) garbage
and so on
コード
この要点を参照してください。サードパーティのライブラリには依存しません。
編集：
ビタビ テーブルの最初の行は、アルゴリズムの前方部分の前のステップで初期化されます。
for (i = 0; i < n_states; i++)
{
state_i = states[i];
sample_t = samples[0];
viterbi_table[i*n_samples]
= prior(state_i, 0, true) + emission(sample_t, state_i, true);
}
EDIT2：
以前のバージョンのコードでは、より標準的な 2D 配列の初期化 (非連続ブロック内) と対応する配列アクセスを行っていました。これによりbus error、より大きな入力データに対して一貫して対応できました。これは完全に理にかなっています。
double **viterbi_table = malloc(sizeof * viterbi_table * n_states);
int **best_path_table = malloc(sizeof * best_path_table * n_states);
...
viterbi_table[j][t - 1] = ...
EDIT3、ソリューションに関するコメント:
これはばかげた添え字の間違いであることがわかりました。viterbi および最適パス配列のサイズは n_samples * n_states、つまり 17 * 39 = 663 です。これにより、私の例のように 1404 のインデックスは除外されます。
具体的な問題は、n_states の代わりに n_samples を誤って使用したため、配列のインデックス付けが混乱していたことです。特定の観測インデックス t (30) と特定の状態インデックス i (14) の場合、計算は次のようになります。
// Original, wrong
t * n_samples + i = 30 * 39 + 14 = 1184
// New, correct
t * n_states + i = 30 * 17 + 14 = 524
変数tは、現在のサンプル数を既にエンコードしているため、それに状態数を掛けるだけです。
EDIT4、修正コード: 修正コードはここにあります。また、ユース ケースの放出確率と遷移確率も調整しました。