(57)【特許請求の範囲】
【請求項１】
圧縮復号部を有するプロセッサにより、入力データシーケンス“ｘ”から出力圧縮状態シーケンス
【数１】
0005645777.tif 000049
を求めるための方法であって、圧縮状態シーケンス“ｓ０”の確率は、
【数２】
0005645777.tif 000050
に従って前記入力データシーケンスの全てのセグメンテーション“ｙ”を周辺化することによって与えられ、ここで、シンボル
【数３】
0005645777.tif 000051
は圧縮関数を表し、該方法は、
前記プロセッサへ前記入力データシーケンスを入力するステップと、
ｐ(ｃ＝ｃ０|ｘ）に従う前記入力データシーケンス“ｘ”＝｛ｘ１，ｘ２，．．．，ｘＴ｝に対応する可能な圧縮状態シーケンスの長さｃの確率を求めるステップと、
前記出力圧縮状態シーケンス
【数４】
0005645777.tif 000052
の長さ
【数５】
0005645777.tif 000053
を推定するステップであって、前記長さ
【数６】
0005645777.tif 000054
は    
【数７】
0005645777.tif 000055
に従う最大確率を有するものと、
【数８】
0005645777.tif 000056
に従う長さ
【数９】
0005645777.tif 000057
を有する出力圧縮状態シーケンスにおいて各状態ｓｉの確率を求めるステップであって、ここで、
【数１０】
0005645777.tif 000058
であるものと、
【数１１】
0005645777.tif 000059
に従う最大確率を有する各圧縮状態
【数１２】
0005645777.tif 000060
を推定して、前記出力圧縮状態シーケンス
【数１３】
0005645777.tif 000061
を推定するステップと、
推定された前記出力圧縮状態シーケンスを前記プロセッサから出力するステップと、
を備えた、方法。
【請求項２】
前記入力データシーケンスがロボットの移動環境の情報であり、前記出力圧縮状態シーケンスはロボットを追跡する、請求項１に記載の方法。
【請求項３】
前記入力データシーケンスが連続する入力点間の量子化された角度であり、前記出力圧縮状態シーケンスは単一ストロークの文字を認識する、請求項１に記載の方法。
【請求項４】
前記入力データシーケンスが形状コンテキスト特徴に対応する観測値であり、前記出力圧縮状態シーケンスは手書きの単語を認識する、請求項１に記載の方法。
【請求項５】
前記入力データシーケンスが車両及びトレーラーの画像であり、前記出力圧縮状態シーケンスは前記車両のタイヤ及びトレーラーの数をカウントして料金を求める、請求項１に記載の方法。
【請求項６】
前記入力データシーケンスが発話された単語であり、前記出力圧縮状態シーケンスは発話を認識する、請求項１に記載の方法。
【請求項７】
前記出力圧縮状態シーケンスにおける各前記状態は確率を示すラベルを含む、請求項１に記載の方法。
【請求項８】
前記出力圧縮状態シーケンスは隠れマルコフモデルを用いて求められる、請求項１に記載の方法。
【請求項９】
前記出力圧縮状態シーケンスは条件付き確率場を用いて求められる、請求項１に記載の方法。
【請求項１０】
前記入力データシーケンスは時系列である、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的にはデータの入力シーケンスから状態シーケンスを求めるための方法に関し、より詳細には圧縮状態シーケンスを求めることに関する。
【背景技術】
【０００２】
シーケンシャルデータにラベルを割り当てることは、発話認識、計算言語学、コンピュータービジョン、及びロボット工学等の用途における一般的な問題である。たとえば、品詞を分析するとき、課題は、言語の文法構造を考えることによって単語のシーケンスにタグ付けすることであり、たとえば動詞−動詞−名詞−名詞−動詞−形容詞は英語において可能性が極めて低い文法シーケンスである一方、名詞−動詞−副詞はそうではない。同様に、発話認識において、単語又は音素は、特にそれらの順序に関して、基礎となる言語の或る特定の発音規則に従う。
【０００３】
同様に、基礎となる言語の文法によって強制される構造を利用することによって手書きの文字（character）のシーケンスに表音文字（letter）及び数字を割り当てることができる。これらの例において、シーケンシャルパターンが重要であり、シーケンシャルパターンを利用して大きなデータセットから情報を抽出することができる。
【０００４】
そのような問題を解決するための２つの一般的なモデルは、隠れマルコフモデル（ＨＭＭ）及び条件付き確率場（ＣＲＦ）である。これらのモデルは非常に強力であるが、データのタイプが異なると、用途に特有の変更が必要となるので、モデルが様々に拡張されることになる。
【０００５】
たとえば、半マルコフ型ＣＲＦは、セグメンテーション問題へのより一般的な解法であり、データのセグメントにおける非マルコフ型状態遷移を可能にし、個々のサンプルではなくシーケンスに直接ラベルを割り当てる。
【０００６】
別の方法は、現実的でない状態遷移を防ぐために状態持続性を有するシステムの非パラメトリック事前確率を説明している。この方法は状態持続性をもたらし、無限状態空間内で遷移確率をトレーニングすることも可能にする。上記の例において、最終状態シーケンス推測の基本課題は、正確な状態シーケンスを推定することである。
【０００７】
しかしながら、多くの用途において、これは必須の目標ではない。そうではなく、目標は状態シーケンスの何らかの確定関数を推定することである。特に、目標は、各状態における滞留時間を考慮することなく状態遷移を追跡することである。
【０００８】
例示的な用途では、人の動きが追跡されるが、このとき、「座る（ｓ）」、「飛び跳ねる（ｊ）」、「歩く（ｗ）」、及び「走る（ｒ）」等の状態間の正確な遷移は曖昧でありかつ重要でないが、特定の順序で発生した状態の固有のシーケンスの検出が重要である。
【０００９】
たとえば、人間の動きの例示的なグラウンドトルース状態シーケンスは“ｙ”＝｛ｓ，ｓ，ｊ，ｊ，ｊ，ｗ，ｗ，ｒ，ｒ｝であり、データの入力シーケンスは“ｘ”＝｛ｘ１，ｘ２，．．．，ｘ９｝である。目標は、確定関数ｃｏｍｐｒｅｓｓの出力を正確に予測することであり、ここで、ｃｏｍｐｒｅｓｓ（“ｙ”）＝｛ｓ，ｊ，ｗ，ｒ｝である。すなわち、圧縮シーケンスにおいて重複した状態が取り除かれている。
【００１０】
さらに、ｊからｗへちょうど遷移する時に、状態「ｗ」の最初の出現を「ｊ」に変換することによって、予測状態シーケンス“ｙ’”＝｛ｓ，ｓ，ｊ，ｊ，ｊ，ｊ，ｗ，ｒ，ｒ｝が取得される場合、従来のアプリケーションではエラーとなるが、圧縮状態シーケンス推測を用いるアプリケーションでは、ｃｏｍｐｒｅｓｓ（“ｙ”）＝ｃｏｍｐｒｅｓｓ（“ｙ’”）であるので、エラーとならない。
【００１１】
逆に、予測シーケンスが“ｙ’’ ”＝｛ｓ，ｓ，ｊ，ｊ，ｗ，ｊ，ｗ，ｒ，ｒ｝である場合、１つの状態のみが“ｙ”と異なる場合であっても、このアプリケーションには致命的なエラーとなる。ここで、状態遷移の曖昧性がこの問題の唯一の特徴ではなく、圧縮された出力の長さが知られておらず、かつ任意であり、たとえば人間の動作中にいくつの固有の動作が出現順に発生したかは不明確である。
【００１２】
滞留時間を考えることなくシーケンス内の固有な状態をカウントすることに関心が持たれている状態カウントプロセスを含めて、状態シーケンス推測には、そのような特殊な処置を必要とするいくつかの他の問題が存在する。この発明者らの知る限り、これは、機械学習用途において大部分対処されていない問題である。
【００１３】
ビデオ解釈アプリケーションのための圧縮シーケンスが説明されている。正確な状態遷移は曖昧であり、ビデオ解釈には区別できる状態のみが重要である。この方法は、状態の数が非常に多数であることに起因して、非常に限定された領域にのみ適用可能であり、確率モデルを用いることができない。
【００１４】
別のビデオ解釈アプリケーションでは、単純な遷移−コストモデルが用いられ、同じ状態への状態遷移はコストを有しないと仮定されるのに対し、全ての他の可能な遷移は同じコストＫを有すると仮定される。これは同じ状態への全ての遷移について重みゼロを有し、他の全ての遷移について重みとして同じコストＫを有する確率シーケンシャルモデルをトレーニングすることと非常に類似している。これは、状態遷移のシーケンシャルモデリングが破壊されるので多くの用途において完全に非現実的である。
【００１５】
図１は従来の圧縮状態シーケンス推測方法を示している。データの入力シーケンス“ｘ”＝｛ｘ１，ｘ２，．．．，ｘＴ｝１０１及び事前にトレーニングされたＨＭＭ／ＣＲＦパラメーター｛λｊ，μｋ｝１０６を所与とすると、ＨＭＭ／ＣＲＦ復号方法１０２は、データ１０１に対応する完全な状態シーケンス“ｙ”＝｛ｙ１，ｙ２，．．．，ｙＴ｝１０３を予測する。ここで、インデックスＴのインクリメントは時間ステップである。次に、確定圧縮関数（deterministic compress function）ｆ１０４が完全状態シーケンス１０３に適用され、固有な状態の圧縮シーケンス“ｓ”＝ｆ（“ｙ”）＝｛ｓ１，ｓ２，．．．，ｓｃ｝１０５が求められる。圧縮状態シーケンスにおいて、完全状態シーケンス１０３内の全ての重複する状態は除去される。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
隠れマルコフモデル（ＨＭＭ）及び条件付き確率場（ＣＲＦ）はシーケンシャルデータ“ｘ”をモデリングするための非常に一般的な技法である。ＣＲＦ及びＨＭＭを用いる状態シーケンス推測手順によって、データの入力シーケンス“ｘ”を所与として状態シーケンス“ｙ”の推定が可能になる。
【００１７】
しかしながら、多くの用途において、正確な（完全な）状態シーケンスの推定は必ずしも目標ではない。そうではなく、目標は状態シーケンス“ｘ”の或る確定関数ｆを推定して、圧縮状態シーケンス“ｙ”を得ることである。そのような用途において、従来の状態シーケンス推測技法によって状態シーケンスを推定し、その後、該推定から関数マッピングを求めることは必ずしも最適ではない。
【課題を解決するための手段】
【００１８】
したがって、この発明はデータの入力シーケンス“ｘ”から圧縮状態シーケンス“ｓ”を直接求める。
【００１９】
特に、確定関数ｆ（“ｘ”）が固有の状態遷移のみを追跡し、各状態の滞留時間を追跡しない特定の問題を考える。
【００２０】
従来の圧縮状態シーケンス推測技法よりも性能が優れた多項式時間圧縮状態シーケンス推測方法を提供する。この発明が解決する問題は、ロボット追跡、文字認識、手書き認識、及び発話認識等の多くの異種の用途において一般に生じる。
【発明の効果】
【００２１】
ＣＲＦ及びＨＭＭのための従来の状態シーケンス推測技法は、正確な予測に焦点を当てるが、これは目標が各状態の滞留時間を追跡することではなく、状態遷移を追跡することであるいくつかの用途では必要とされない。この発明は、この問題を解決するように明示的に設計された多項式時間状態シーケンス推測手順を提供する。
【図面の簡単な説明】
【００２２】
【図１】従来のＨＭＭ／ＣＲＦ復号及びそれに続く確定関数ｆの適用のブロック図である。これによって圧縮状態シーケンスが生成される。
【図２Ａ】この発明の実施の形態による、圧縮状態シーケンスを直接出力する圧縮ＨＭＭ／ＣＲＦ復号のブロック図である。
【図２Ｂ】この発明の実施の形態による、圧縮状態シーケンスを直接出力する圧縮ＨＭＭ／ＣＲＦ復号のブロック図である。
【図３Ａ】この発明の実施の形態による、圧縮状態シーケンス推測方法の概略図である。
【図３Ｂ】この発明の実施の形態による、圧縮状態シーケンス推測方法の概略図である。
【図３Ｃ】この発明の実施の形態による、圧縮状態シーケンス推測方法の概略図である。
【図４Ａ】この発明の実施の形態による、ロボットロケーション追跡アプリケーションの概略図である。
【図４Ｂ】この発明の実施の形態による、ロボットロケーション追跡アプリケーションの概略図である。
【図４Ｃ】時間の関数としての動きのグラフである。
【発明を実施するための形態】
【００２３】
図２Ａ及び図２Ｂは、この発明の実施の形態による圧縮状態シーケンス推測方法を示している。データの入力シーケンス“ｘ”＝｛ｘ１，ｘ２，．．．，ｘＴ｝２０１を所与とする。ここでデータはＴによってインデックス付けされている。たとえば、シーケンスは時系列である。圧縮復号方法２０２は、トレーニングされたＨＭＭモデル又はＣＲＦモデルのパラメーター｛λｊ，μｋ｝２０４を用いて、推定圧縮状態シーケンス“ｓ”＝｛ｓ１，ｓ２，．．．，ｓｃ｝２０３を直接出力する。本方法のステップは、当該技術分野において既知のようにメモリ及び入力／出力インターフェースに接続されたプロセッサ２００において実行することができる。
【００２４】
条件付き確率場及び状態シーケンス推測技法
直鎖条件付き確率場（ＣＲＦ）及び隠れマルコフモデル（ＨＭＭ）は、シーケンシャルデータをラベル付けするのに用いることができる２つの確率モデルである。データがラベル付けされた後、状態シーケンスを求めることができる。選択された特徴関数に依拠して直鎖ＣＲＦ及びＨＭＭを交換可能に用いることができる。この発明はＣＲＦの手順に焦点を当てる。
【００２５】
しかしながら、手順はＨＭＭにも等しく適用可能である。この発明の方法にとって、いずれの特定のモデルを用いるかは重要ではない。すなわち、結果は一方から他方に一般化することができる。本明細書では直鎖ＣＲＦを用いるが、本方法はＨＭＭにも適用可能である。
【００２６】
従来の条件付き確率場
条件付き分布ｐ（“ｘ”｜“ｙ”）をモデル化するための直鎖ＣＲＦを以下のように定義することができる。
【００２７】
【数１】
0005645777.tif 000002
【００２８】
ここで、Ψはポテンシャル関数であり、ｇは或る状態から次の状態への遷移特徴関数（transition feature function）であり、ｕは特徴関数であり、λ及びμはトレーニングプロセスによって推定されるパラメーターであり、Ｚは入力データシーケンスの関数である正規化係数である。
【００２９】
従来の状態シーケンス推測技法
データシーケンスの従来のラベル付けは、同時密度“ｙ＊”＝ａｒｇ  ｍａｘｙｐ（“ｙ”｜“ｘ”）を用い、ここで関数「ａｒｇ  ｍａｘ」は最大値を返す。解は、再帰δｔ（ｊ）＝ｍａｘｉΨ（ｊ，ｉ．ｘｔ）δｔ−１を用いてビタビ手順により求めることができる。これは、最大積法則に基づいて最可能経路を伝播する。しかしながら、多くの用途において、完全なシーケンスを正確に予測することは非常に困難であるので、個々の予測が用いられる。これは、Ｆｏｒｗａｒｄ−Ｂａｃｋｗａｒｄ（前向き後ろ向き）と呼ばれる動的プログラミング手順を適用することによって、周辺分布ｐ（ｙｉ，ｔ｜”ｘ”）からｙｉ，ｔを予測することにより達成することができる。前方再帰はαｔ（ｊ）＝ΣｉΨ（ｊ，ｉ，ｘｔ）αｔ−１（ｉ）であり、ここでαｔ（ｊ）は前方変数であり、後方再帰はβｔ（ｉ）＝ΣｉΨｔ＋１（ｊ，ｉ，ｘｔ＋１）βｔ＋１（ｊ）であり、ここでβｔ（ｉ）は後方変数である。次に、これらの変数を用いることによって周辺確率を求めることができる。
【００３０】
制約付き前方手順を用いて、前方再帰を制約付き状態シーケンスに制約することによって特定の状態シーケンスにおける信頼度を求めることができる。制約集合Ｙ’＝｛ｙｑ，．．．，ｙｒ｝を所与とすると、変更された前方手順を用いて任意のデータシーケンスがＹ’を満たす確率を求めることができる。
【００３１】
変更された前方再帰は、全てのｙｔ＋１２Ｙ’について、
【００３２】
【数２】
0005645777.tif 000003
【００３３】
であり、ここで、演算子
【００３４】
【数３】
0005645777.tif 000004
【００３５】
は「ｊは制約ｙｔ＋１に従う」として定義される。インデックスＴにおいて、特定の制約の信頼度はＺ’／Ｚである。ここで、制約付き格子因子
【００３６】
【数４】
0005645777.tif 000005
【００３７】
は制約付き前方変数を用いて求められ、制約なし格子因子Ｚ＝ΣｉαＴ（ｉ）は制約なし前方変数を用いて求められる。同様に、周辺確率ｐ（ｙｉ，，ｔ｜“ｘ”）を推定している間、集合Ｙ’内に単一の制約ｙｉ，ｔを有することによって同じ方法が辿られる。
【００３８】
圧縮状態シーケンス推測
この発明の実施の形態は、取得データから状態の圧縮シーケンスを推測するための方法を提供する。人間の動きを予測する１つの用途例では、状態の圧縮シーケンスを、“ｓ”＝ｃｏｍｐｒｅｓｓ（“ｙ”）として定義する。ここで、ｓ、ｊ、ｗ、ｒは任意の状態である。“ｙ”＝｛ｓ，ｓ，ｊ，ｊ，ｊ，ｗ，ｗ，ｒ，ｒ｝である場合、“ｓ”＝ｃｏｍｐｒｅｓｓ（“ｙ”）＝｛ｓ，ｊ，ｗ，ｒ｝である。これ以降、シンボル
【００３９】
【数５】
0005645777.tif 000006
【００４０】
を用いて関数ｃｏｍｐｒｅｓｓを表す。この発明の目標は、圧縮シーケンス“ｓ”を可能な限り正確に予測することである。確率ｐ（“ｓ”｜“ｘ”）を求めるための枠組みを構築する。
【００４１】
圧縮状態シーケンス“ｓ０”の確率が全てのセグメンテーション“ｙ”にわたる周辺化によって与えられる。ここで圧縮表現“ｓ０”の確率は、
【００４２】
【数６】
0005645777.tif 000007
【００４３】
であり、シンボル
【００４４】
【数７】
0005645777.tif 000008
【００４５】
は圧縮関数を表す。
【００４６】
確率ｐ（“ｙ”｜“ｘ”）を求めることは効率的であるが、式（４）の総和は指数関数的な演算数ＭＴを含む。ここでＭは状態数であり、Ｔは完全状態シーケンス“ｙ”の長さであり、これは扱い難い。したがって、動的プログラミング前向き後ろ向き手順を用いてｐ（“ｓ”＝“ｓ０”｜“ｘ”）を求めるための多項式時間手順を提供する。
【００４７】
ここでこの発明の圧縮状態シーケンス推測方法の基本ステップを記述する。
【００４８】
確率ｐ（“ｓ”＝“ｓ０”｜“ｘ”）を求める
式（４）において、圧縮シーケンス“ｓ０”に対応する指数関数的な個数の可能な完全状態シーケンス“ｙ”が存在し得る。この問題を克服するために、前方再帰を適用しながらシーケンス“ｓ”の遷移を追跡することを説明する。
【００４９】
図３Ａに示すように、シーケンス“ｓ０”の長さはｃ＝｜“ｓ０”｜である。表記を容易にするために、“ｓ０”の個々の項をｓｉと呼ぶ。ここで、ｉ＝１，…，ｃである。シーケンス“ｓ０”内の正確にｉ−１個の遷移をｔまで追跡する前方変数
【００５０】
【数８】
0005645777.tif 000009
【００５１】
を定義する。インデックスｔ−１からインデックスｔまで、前方変数は以下に基づいて更新される。
入力データｘｔについて同じ状態に留まり（矢印３１１で示される）、
状態ｓｉからｓｉ＋１への遷移を行う（矢印３１２で示される）。
【００５２】
動的プログラミング法は以下の通りである。
【００５３】
シーケンス“ｓ０”の確率ｐ（“ｓ”＝“ｓ０”｜“ｘ”）は
【００５４】
【数９】
0005645777.tif 000010
【００５５】
である。これは再帰
【００５６】
【数１０】
0005645777.tif 000011
【００５７】
によって求められる。ここで、ｉ＝１，．．．，ｃである。
【００５８】
インデックス（時刻）Ｔにおいて、
【００５９】
【数１１】
0005645777.tif 000012
【００６０】
を得る。
【００６１】
この再帰によって、格子正規化係数（lattice normalization factor）
【００６２】
【数１２】
0005645777.tif 000013
【００６３】
を求める。正規化係数Ｚは、ｐ（“ｓ”＝“ｓ０”｜“ｘ”）＝Ｚ（“ｓ０”）／ＺによってＺ（“ｓ０”）を確率に変換する。正規化係数Ｚの計算は以下に説明される。この方法の証明が付録において与えられている。
【００６４】
ｐ（ｃ＝ｃ０｜“ｘ”）を求める
データ“ｘ”の入力シーケンスを所与とすると、圧縮シーケンス“ｓ”を求める最初のステップは、シーケンス“ｓ”の長さｃを求めることである。ここで、ｃは、状態遷移が存在しないことを意味する１から、最大で、全ての１つ１つのインクリメントにおいて遷移が存在することを意味するシーケンス長Ｔまでの値を取ることができる。全てのｃ＞Ｔについて、ｐ（ｃ＝ｃ０｜“ｘ”）＝０である。長さｉの圧縮シーケンスの集合は“Ｓｉ”であり、すなわちｉ＝１，．．．，Ｔについて“Ｓｉ”＝｛“ｓ”：｜“ｓ”｜＝ｉ｝である。ｉ≠ｊについて
【００６５】
【数１３】
0005645777.tif 000014
【００６６】
である場合、確率ｐ（ｃ＝ｃ０｜“ｘ”）は
【００６７】
【数１４】
0005645777.tif 000015
【００６８】
である。
【００６９】
長さｃの１つの可能なシーケンス“ｓ０”の確率はｐ（“ｓ”＝“ｓ０”｜“ｘ”）である。図３Ｂに示すように、２つの可能な圧縮シーケンス“ｓ１”及び“ｓ２”を有する場合、
【００７０】
【数１５】
0005645777.tif 000016
【００７１】
である。ここで、
【００７２】
【数１６】
0005645777.tif 000017
【００７３】
は、シーケンスｓｉに前方再帰が適用されたことを意味する。しかしながら、これらの２つのシーケンスは、圧縮領域の１つの点においてのみ異なる。同じ格子によってシーケンスを表し、複数の計算を回避することを可能にするために、テーブルに
【００７４】
【数１７】
0005645777.tif 000018
【００７５】
のベクトル表現を表す。前方変数αｔはＭ次元であり、以前の
【００７６】
【数１８】
0005645777.tif 000019
【００７７】
はｃ次元である。この発明の
【００７８】
【数１９】
0005645777.tif 000020
【００７９】
はｃ×Ｍ次元である。
【００８０】
格子に対する全ての制約の集合は、Ｑ＝｛…，ｑｌ−１，ｑｌ，ｑｌ＋１，…｝であり、ここで各制約ｑｌはテーブルの非ゼロエントリの１組の座標である。たとえば、特定の圧縮シーケンス“ｓ０”の場合、集合は｛（１，ｓ１），（２，ｓ２），…，（ｃ，ｓｃ）｝に対応する。特定の集合“Ｓｉ”の場合、この集合は高さＩを有するテーブルの全ての座標に対応し、
【００８１】
【数２０】
0005645777.tif 000021
【００８２】
で表される。所与の制約集合Ｑのための再帰は以下の通りである。
【００８３】
【数２１】
0005645777.tif 000022
【００８４】
図３Ｂに示すように、この再帰はテーブル内の全ての非ゼロエントリを通って伝播し、全てのゼロエントリを無視する。なぜなら、ゼロエントリは格子Ｑ内に含まれないためである。
【００８５】
図３Ｃは、制約がインデックスｔ−１からｔ及びｔからｔ＋１の格子の全てのロケーションに含まれる再帰を示している。
【００８６】
式（６）の再帰は、集合Ｑによって以下のように定義される全ての圧縮シーケンスの確率を求める。
【００８７】
【数２２】
0005645777.tif 000023
【００８８】
制約集合表記
【００８９】
【数２３】
0005645777.tif 000024
【００９０】
を用いると、確率ｐ（ｃ＝ｃ０｜“ｘ”）は、
【００９１】
【数２４】
0005645777.tif 000025
【００９２】
である。
【００９３】
これは、制約集合
【００９４】
【数２５】
0005645777.tif 000026
【００９５】
を用いて式（６）において再帰を適用し、行ｃ０におけるエントリの和を求めることに対応する。上述したように、ｃ０＞Ｔ又はｃ０＜１のとき、ｐ（ｃ＝ｃ０｜“ｘ”）＝０である。この手順を制約集合
【００９６】
【数２６】
0005645777.tif 000027
【００９７】
に対して実行する場合、テーブル
【００９８】
【数２７】
0005645777.tif 000028
【００９９】
の行の和によって全ての格子因子
【０１００】
【数２８】
0005645777.tif 000029
【０１０１】
が同時に得られる。このテーブルの総和は正規化係数Ｚに等しく、これはｐ（“ｓ”＝“ｓ０”｜“ｘ”）＝Ｚ（“ｓ０”）＝Ｚ及び
【０１０２】
【数２９】
0005645777.tif 000030
【０１０３】
を求めるのに必要である。この識別情報は、“ｓ”の全ての可能な長さ及び組み合わせについて、Ｚが格子因子の総和に等しいということから得られる。
【０１０４】
ｐ（ｓｉ＝ｊ｜“ｘ”，ｃ）を求める
周辺分布ｐ（ｓｉ＝ｊ｜“ｘ”，ｃ）を求めるために、行ｉにおけるエントリを除いて、高さｃを有するテーブルの全てのエントリを含めることによって、制約集合Ｑｉ，ｊを構築する。次に、この集合に（ｉ，ｊ）を加える。この特定の制約集合構成は、長さｃ及びｓｉ＝ｊの全ての可能な圧縮シーケンス構成を含む。このとき、周辺確率は、ｐ（ｓｉ＝ｊ｜“ｘ”，ｃ）＝Ｚ（Ｑｉ，ｊ）／ΣｊＺ（Ｑｉ，ｊ）である。
【０１０５】
圧縮シーケンス
次に、上記のステップを適用し、以下を最大にすることによって、圧縮状態シーケンスが求められる。
【０１０６】
【数３０】
0005645777.tif 000031
【０１０７】
によってｃを推定し、
【０１０８】
【数３１】
0005645777.tif 000032
【０１０９】
によってｓｊを推定する。
【０１１０】
データから状態シーケンスを生成するための方法
上記に続いて、図２Ｂは方法２０２をより詳細に示している。
最初に、ｐ＝（ｃ｜“ｘ”）に従って入力データシーケンス“ｘ”＝｛ｘ１，ｘ２，．．．，ｘＴ｝２０１に対応する、可能な圧縮状態シーケンスの長さｃ２６１の確率を求める（２５１）。ここで、ｉ＝１，．．．，Ｔである。
次に、出力圧縮状態シーケンス
【０１１１】
【数３２】
0005645777.tif 000033
【０１１２】
２０３の長さ
【０１１３】
【数３３】
0005645777.tif 000034
【０１１４】
２６２を推定する（２５２）。ここで、長さ
【０１１５】
【数３４】
0005645777.tif 000035
【０１１６】
はａｒｇ  ｍａｘ  ｐ（ｃ｜“ｘ”）に従う最大確率を有し、関数ａｒｇ  ｍａｘは最大確率を返す。
次に、
【０１１７】
【数３５】
0005645777.tif 000036
【０１１８】
に従う長さ
【０１１９】
【数３６】
0005645777.tif 000037
【０１２０】
を有する出力圧縮状態シーケンス
【０１２１】
【数３７】
0005645777.tif 000038
【０１２２】
内の各状態ｓｊ２６３の確率を求める（２５３）。ここで、
【０１２３】
【数３８】
0005645777.tif 000039
【０１２４】
である。
そして最後に、
【０１２５】
【数３９】
0005645777.tif 000040
【０１２６】
に従う最大確率を有する各圧縮状態
【０１２７】
【数４０】
0005645777.tif 000041
【０１２８】
を推定して（２５４）、出力圧縮状態シーケンス
【０１２９】
【数４１】
0005645777.tif 000042
【０１３０】
を推定する。これらのステップはプロセッサにおいて実行される。
【０１３１】
応用形態
この発明の圧縮状態シーケンス推測方法の以下の応用形態を説明する。
【０１３２】
移動ロボットのロケーション追跡
移動ロボットへの応用形態において、ロボットはグリッドを用いて環境内で追跡される。特に環境を発掘する目的で、シーケンシャルモデルが頻繁に用いられる。この応用形態では、正確なグリッド反復は重要でなく、ロボットが順番に横切ったロケーションを示す圧縮バージョンが重要である。
【０１３３】
例示的なロボット応用形態について図４Ａに示されているように、ロボットは該ロボットが部屋の色（青（Ｂ）、緑（Ｇ）、黄（Ｙ）、赤（ｒ））、及びそのロケーションへの動きを妨げる障害物（ブロック）を検知することができる環境内を移動する。
【０１３４】
全てのステップにおいて、ロボットは移動｛上、下、左、右｝を試みる。ここでロボットは方向をランダムに選択する。意図される方向に障害物が存在する場合、ロボットは再度試行する。
【０１３５】
図４Ｂは、ロボットの一例示の経路４０１を示している。この問題において、状態は（ｘ，ｙ）座標におけるロボットのロケーションを指し、観測値は観測される色を指し、これはセンサー、たとえばカメラの出力である。
【０１３６】
図４Ｃは、図４Ｂにおける経路４０１について、観測される色の観点で、時間の関数として動きを示している。不都合なことに、色検出の的中率は不完全である可能性があり、たとえば平均８０％である。この場合、ロボットは異なるロケーションにいるにも関わらず、図４Ｃの雑音４０２によって示すようにセンサー出力は誤ったものとなる。しかしながら、圧縮状態シーケンス推測方法は、カメラ観測値のシーケンスに関して、ロボットが順番に横切る正しいロケーションを予測する。
【０１３７】
単一ストローク文字認識
この応用形態は、スマートフォン、携帯情報端末（ＰＤＡ）、及びタブレットＰＣ等の、タッチスクリーンを用いて文字及びグリフの入力を可能にする電子デバイスと共に用いることができる。一般に、問題は、通常１つの連続ストロークでタッチスクリーン上に描かれた形状を認識することである。
【０１３８】
この応用形態では、状態は方向｛上、右、下、左｝を指し、観測値は連続する入力点間の量子化された角度を指す。一般に、現在のシステムは、この目的のために確率的有限状態マシン又はＨＭＭを用いる。通例、ＨＭＭ又は有限状態マシンは単一の文字に関してトレーニングされる。次に、モデルを用いたデータ尤度試験によって１つのクラスが選択される。この方法の１つの欠点は、任意の形状を扱う能力が限られていることである。全ての文字について単一のモデルをトレーニングして、そのモデルを用いることによって状態を復号することができる。それにもかかわらず、単一の状態誤りによって予測全体が誤ったものとなる可能性がある。このため、雑音に耐性のある状態シーケンス推測方法を提供する。さらに、１つの状態から別の状態への移行は通常曖昧であるので、状態遷移における曖昧性も問題である。
【０１３９】
しかしながら、この発明の方法は正確な遷移を推定しない。その代わり、この発明の方法は、このタスクには十分である遷移シーケンスを生成する。観測値、たとえばユーザーインターフェースから取得される連続点間の量子化された角度を所与とすると、この発明の圧縮状態シーケンス推測方法は、全ての方向を順番に生成し、これは特定の文字を示す。
【０１４０】
手書きの単語認識
手書きの認識は通常、最初に手書きをセグメント化し、次にそれらのセグメントをサポートベクターマシン（ＳＶＭ）等のマルチクラス分類器を用いて認識することによって実行される。多くの場合に、言語の文法も用いられる。しかしながら、セグメント化は前処理として行われることが通常想定される。
【０１４１】
この発明の方法によれば、文字はセグメント化されず、シーケンスの長さは知られることも必要とされることもない。なぜなら、手書きの単語は異なる長さを有する可能性があるためである。入力の手書きは画像の形態をとる。この応用形態では、各インクリメントは手書きの画像内の１つの垂直列に対応する。状態は対応するセグメントを指し、観測値は形状コンテキスト特徴に対応する。
【０１４２】
特徴を抽出する間、まずスライディングウィンドウ技法を用いることによって画像から重複するパッチを取る。画像内の列毎に１つのパッチが取られる。次に、形状コンテキスト記述子を適用する。次に、Ｋ平均クラスタリングを適用して、トレーニングデータを用いて辞書をトレーニングする。また、トレーニングされた辞書内のパッチ毎にヒストグラムを生成する。トレーニングされた辞書は、パッチから抽出された各点を該辞書内のクラスター中心にマッピングする。ＣＲＦモデルはインクリメント毎の観測値としての形状コンテキスト特徴のヒストグラムを用いてトレーニングされ、状態はその観測値を生成する文字に対応する。
【０１４３】
分類している間、同じマッピング手順を実行し、トレーニングセットとの共有空間、すなわちヒストグラム空間を有するようにする。試験を通じたスライディングウィンドウを通じて求められた観測値、たとえば形状コンテキスト特徴のヒストグラムを所与とすると、圧縮状態シーケンス推測は、シーケンス内の所与の単語における文字を予測する。
【０１４４】
料金収受
電子料金収受（ＥＴＣ）の応用形態において、目標は、カメラ又は３Ｄセンサーを用いて車両のタイヤ及びトレーラーの数をカウントすることである。圧縮状態シーケンス推測方法は、経時的にこれらの観測値を用いて、全ての状態、たとえば車体、タイヤ、牽引棒を推定し、これによって、料金を求めるための、車両のタイヤ及びトレーラーの数に関する情報がもたらされる。
【０１４５】
発話認識
発話認識において、ＨＭＭ、並びにビタビ及びＦｏｒｗａｒｄ−Ｂａｃｋｗａｒｄ等の従来の状態シーケンス推測方法は、多くの場合に、発話された単語をテキストに変換するために用いられる。オーディオ信号の基礎にある状態は音素であり、一般的に、２つの状態間の正確な遷移点は曖昧である。しかしながら、発話された単語の速度に基づいて、オーディオ信号の長さは同じ単語について変動する可能性がある。圧縮状態シーケンス推測は、正確な遷移点を見つけることなく発話された単語を音素に復号する。これは発話認識には十分な情報である。
【０１４６】
付録
証明。一般性を損なうことなく、ｓ０，１＝１、ｓ０，２＝２、ｓ０，３＝３、．．．ｓ０，ｃ＝ｃとし、ｔ１、ｔ２からｔｃ−１までを状態遷移時間とする。すなわちｔ１はｓ０，１＝１からｓ０，２＝２への遷移である。
【０１４７】
【数４２】
0005645777.tif 000043
【０１４８】
式（１３）において、分配法則を用いることによって式（１２）を書き換える。式（１４）において、単に時間Ｔを計算から除外することによって総和を２つのケースに分割する。（１）第１の部分は、時刻Ｔにおいてｃ−１からｃへの遷移が存在するケースを考え、（２）第２の部分は時刻Ｔにおいて遷移が存在せず、このためｃ−１からｃへの遷移がＴより前であり、時刻Ｔにおいて以前の状態ｃが反復されると考える。次に、(オーバーバー)αＴ(ｃ)としてのｓ領域の前方変数を以下のように定義する。
【０１４９】
【数４３】
0005645777.tif 000044
【０１５０】
このとき、式（１４）における２つの総和項をこれらの前方変数に関して以下のように書き換えることができることが明らかである。
【０１５１】
【数４４】
0005645777.tif 000045
【０１５２】
最後に、再帰式
【０１５３】
【数４５】
0005645777.tif 000046
【０１５４】
を得る。
【０１５５】
この証明は全ての長さｃについて有効である。換言すれば、１からｃ−１までの信号をこの発明の信号と見なすことができる。このため、任意の長さにおいて、時刻Ｔにおける再帰は以下のように書くことができる。
【０１５６】
【数４６】
0005645777.tif 000047
【０１５７】
さらに、これは、Ｔに戻って再帰することによって任意のｔ＝１，．．．，Ｔにも同様に一般化することができる。このため、最終形式は、
【０１５８】
【数４７】
0005645777.tif 000048
【０１５９】
となる。
【図１】
0005645777.tif 000062
【図２Ａ】
0005645777.tif 000063
【図２Ｂ】
0005645777.tif 000064
【図３Ａ】
0005645777.tif 000065
【図３Ｂ】
0005645777.tif 000066
【図３Ｃ】
0005645777.tif 000067
【図４Ａ】
0005645777.tif 000068
【図４Ｂ】
0005645777.tif 000069
【図４Ｃ】
0005645777.tif 000070