可変次数マルコフモデル

確率過程の数学理論において、可変次数マルコフ（VOM）モデルは、よく知られているマルコフ連鎖モデルを拡張した重要なモデル群です。マルコフ連鎖モデルでは、マルコフ性を持つ系列内の各確率変数は固定数の確率変数に依存しますが、VOMモデルでは、この条件付け確率変数の数は、観測された具体的な実現値に基づいて変化する可能性があります。

この実現シーケンスはしばしばコンテキストと呼ばれ、そのためVOMモデルはコンテキストツリーとも呼ばれます。^{[ 1 ]} VOMモデルは、色付き確率的サフィックスツリー（PST）によって美しく表現されます。^{[ 2 ]}条件付け確率変数の数の柔軟性は、統計分析、分類、予測などの多くのアプリケーションにとって大きな利点となります。^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}

例

例えば、それぞれが三項アルファベット{ $a$ $,$ $b$ $,$ $c$ $}$ $から値を取る$ ランダム変数のシーケンスを考えてみましょう。具体的には、部分文字列 $aaabc$ の無限連結から構成される文字列 $aaabcaaabcaaabcaaabc\dotsaaabc$ を考えてみましょう。

この例では、 $Pr(c | ab) = Pr(c | b) = 1.0$ であるため、より短いコンテキスト $b$ だけで次の文字を決定できます。同様に、最大次数 3 の VOM モデルでは、条件付き確率の要素が 5 つだけ使用して文字列を正確に生成できます。これらの要素はすべて 1.0 です。

実際の状況では、マルコフ連鎖の次数が増加するにつれて指数関数的に増加する条件付き確率成分の数を正確に推定するのに十分なデータが得られることはほとんどない。

可変次数マルコフモデルは、現実的な設定では、過去の状態の一部が将来の状態から独立している状態（コンテキストによって表される）の特定の実現が存在すると仮定しています。したがって、「モデルパラメータの数を大幅に削減できます。」^{[ 1 ]}

意味

$A を$ サイズの状態空間 (有限アルファベット) とする $|A|$ 。

マルコフ性を持つ数列を考える $x_{1}^{n}=x_{1}x_{2}\dots x_{n}$ $n$ 個の確率変数の実現値のうち、 $x_{i}\in A$ $位置i$ における状態 (記号) は $\scriptstyle (1\leq i\leq n)$ 、そして州の連結 $x_{i}$ そして $x_{i+1}$ は、 $x_{i}x_{i+1}$ 。

観測された状態のトレーニングセットが与えられた場合、 $x_{1}^{n}$ VOMモデルの構築アルゴリズム^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}は、過去の状態（以前に観測されたシンボル）または将来の状態に基づいて、シーケンス内の各状態に対する確率割り当てを提供するモデル $P$ を学習します。

具体的には、学習者は条件付き確率分布を生成する。 $P(x_{i}\mid s)$ 記号の場合 $x_{i}\in A$ 文脈が与えられた場合 $s ∈ A*$ ここで、* 記号は、空のコンテキストを含む任意の長さの状態のシーケンスを表します。

VOMモデルは、次の形式の条件付き分布を推定しようと試みる。 $P(x_{i}\mid s)$ コンテキストの長さ $|s|\leq D$ 利用可能な統計情報によって異なる。対照的に、従来のマルコフモデルは、コンテキストの長さを固定すると仮定して、これらの条件付き分布を推定しようとする。 $|s|=D$ したがって、これらはVOMモデルの特殊なケースとみなすことができる。

実際、与えられたトレーニングシーケンスに対して、VOMモデルは固定次数マルコフモデルよりも優れたモデルパラメータ化を得ることがわかっており、学習されたモデルの分散とバイアスのトレードオフが改善します。 ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}

応用分野

VOMモデルのパラメータを推定するためのさまざまな効率的なアルゴリズムが考案されている。^{[ 4 ]}

VOMモデルは、機械学習、情報理論、バイオインフォマティクスなどの分野にうまく適用されており、コーディングやデータ圧縮^{[ 1 ]}、文書圧縮^{[ 4 ]}、DNAおよびタンパク質配列の分類と識別^[⁶^]などの具体的なアプリケーションも含まれています。^{[ 3 ]}統計的プロセス管理、^{[ 5 ]}スパムフィルタリング、^{[ 7 ]}ハプロタイピング、^{[ 8 ]}音声認識、^{[ 9 ]}社会科学におけるシーケンス分析、^{[ 2 ]} その他。

参考文献

1 2 3 Rissanen, J. (1983 年 9 月). "汎用データ圧縮システム". IEEE Transactions on Information Theory . 29 (5): 656–664 . doi : 10.1109/TIT.1983.1056741 .
1 2 Gabadinho, Alexis; Ritschard, Gilbert (2016). "確率的接尾辞木による状態シーケンスの分析: PST R パッケージ" . Journal of Statistical Software . 72 (3). doi : 10.18637/jss.v072.i03 . ISSN 1548-7660 . S2CID 63681202 .
1 2 3 4 Shmilovici, A.; Ben-Gal, I. (2007). "EST配列における潜在的なコーディング領域の再構築のためのVOMモデルの使用". Computational Statistics . 22 (1): 49–69 . doi : 10.1007/s00180-007-0021-8 . S2CID 2737235 .
1 2 3 4 5 Begleiter, R.; El-Yaniv, R.; Yona, G. (2004). "可変次数マルコフモデルを用いた予測について" . Journal of Artificial Intelligence Research . 22 : 385– 421. arXiv : 1107.0051 . doi : 10.1613/jair.1491 .
1 2 3 4 Ben-Gal, I.; Morag, G.; Shmilovici, A. (2003). "Context-Based Statistical Process Control: A Monitoring Procedure for State-Dependent Processes" (PDF) . Technometrics . 45 (4): 293– 311. doi : 10.1198/004017003000000122 . ISSN 0040-1706 . S2CID 5227793 .
↑ Grau J.; Ben-Gal I.; Posch S.; Grosse I. (2006). "VOMBAT: 可変次数ベイズツリーを用いた転写因子結合部位の予測" (PDF) . Nucleic Acids Research . 34 (Web Server issue). Nucleic Acids Research, vol. 34, issue W529–W533.: W529-33. doi : 10.1093/nar/gkl212 . PMC 1538886 . PMID 16845064 . 2018-09-30 にオリジナル(PDF)からアーカイブ済み. 2014-01-10に取得.
↑ Bratko, A.; Cormack, GV; Filipic, B.; Lynam, T.; Zupan, B. (2006). "統計的データ圧縮モデルを使用したスパムフィルタリング" (PDF) . Journal of Machine Learning Research . 7 : 2673– 2698.
↑ Browning, Sharon R.「可変長マルコフ連鎖を用いたマルチローカス関連マッピング」The American Journal of Human Genetics 78.6 (2006): 903–913.
↑ Smith, A.; Denenberg, J.; Slack, T.; Tan, C.; Wohlford, R. (1985). "連続音声認識への逐次パターン学習システムの応用". ICASSP '85. IEEE International Conference on Acoustics, Speech, and Signal Processing . Vol. 10. Tampa, FL, USA: Institute of Electrical and Electronics Engineers. pp. 1201–1204 . doi : 10.1109/ICASSP.1985.1168282 . S2CID 60991068 .

[Rissanen-1] 1 2 3 Rissanen, J. (1983 年 9 月). "汎用データ圧縮システム". IEEE Transactions on Information Theory . 29 (5): 656–664 . doi : 10.1109/TIT.1983.1056741 .

[:0-2] 1 2 Gabadinho, Alexis; Ritschard, Gilbert (2016). "確率的接尾辞木による状態シーケンスの分析: PST R パッケージ" . Journal of Statistical Software . 72 (3). doi : 10.18637/jss.v072.i03 . ISSN 1548-7660 . S2CID 63681202 .

[Shmilovici-3] 1 2 3 4 Shmilovici, A.; Ben-Gal, I. (2007). "EST配列における潜在的なコーディング領域の再構築のためのVOMモデルの使用". Computational Statistics . 22 (1): 49–69 . doi : 10.1007/s00180-007-0021-8 . S2CID 2737235 .

[Begleiter-4] 1 2 3 4 5 Begleiter, R.; El-Yaniv, R.; Yona, G. (2004). "可変次数マルコフモデルを用いた予測について" . Journal of Artificial Intelligence Research . 22 : 385– 421. arXiv : 1107.0051 . doi : 10.1613/jair.1491 .

[Ben-Gal-5] 1 2 3 4 Ben-Gal, I.; Morag, G.; Shmilovici, A. (2003). "Context-Based Statistical Process Control: A Monitoring Procedure for State-Dependent Processes" (PDF) . Technometrics . 45 (4): 293– 311. doi : 10.1198/004017003000000122 . ISSN 0040-1706 . S2CID 5227793 .

[6] Grau J.; Ben-Gal I.; Posch S.; Grosse I. (2006). "VOMBAT: 可変次数ベイズツリーを用いた転写因子結合部位の予測" (PDF) . Nucleic Acids Research . 34 (Web Server issue). Nucleic Acids Research, vol. 34, issue W529–W533.: W529-33. doi : 10.1093/nar/gkl212 . PMC 1538886 . PMID 16845064 . 2018-09-30 にオリジナル(PDF)からアーカイブ済み. 2014-01-10に取得.

[Bratko-7] Bratko, A.; Cormack, GV; Filipic, B.; Lynam, T.; Zupan, B. (2006). "統計的データ圧縮モデルを使用したスパムフィルタリング" (PDF) . Journal of Machine Learning Research . 7 : 2673– 2698.

[8] Browning, Sharon R.「可変長マルコフ連鎖を用いたマルチローカス関連マッピング」The American Journal of Human Genetics 78.6 (2006): 903–913.

[9] Smith, A.; Denenberg, J.; Slack, T.; Tan, C.; Wohlford, R. (1985). "連続音声認識への逐次パターン学習システムの応用". ICASSP '85. IEEE International Conference on Acoustics, Speech, and Signal Processing . Vol. 10. Tampa, FL, USA: Institute of Electrical and Electronics Engineers. pp. 1201–1204 . doi : 10.1109/ICASSP.1985.1168282 . S2CID 60991068 .

[ 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[ 8 ]

[ 9 ]

例

意味

応用分野

関連項目

参考文献