"入力データシーケンスxから出力圧縮状態シーケンスを求めるための方法であって、前記圧縮状態シーケンスs0の確率は、に従って前記入力データシーケンスの全てのセグメンテーションyを周辺化することによって与えられ、ここで、シンボルは圧縮関数を表し、該方法は、p=c|xに従う前記入力データシーケンスx={x1,x2,...,xT}に対応する可能な圧縮状態シーケンスの長さcの確率を求めるステップであって、ここでi=1,...,Tであるものと、前記出力圧縮状態シーケンスの長さを推定するステップであって、前記長さはargmaxpc|xに従う最大確率を有し、関数argmaxは最大確率を返すものと、に従う長さを有する前記出力圧縮状態シーケンスにおいて各状態sjの確率を求めるステップであって、ここで、であるものと、に従う最大確率を有する各圧縮状態を推定するステップであって、前記出力圧縮状態シーケンスを推定するものと、を備え、前記各ステップはプロセッサにおいて実行される、方法。各前記状態sjの前記確率は周辺確率であり、前記方法は、制約集合Qを構築することであって、該制約集合Qは前記圧縮状態シーケンス内の可能な遷移を含み、前記周辺確率は、であり、ここでZは正規化係数であるもの、をさらに含む、請求項1に記載の方法。前記出力圧縮状態シーケンスはロボットを追跡するものである、請求項1に記載の方法。前記出力圧縮状態シーケンスは単一ストロークの文字を認識するものである、請求項1に記載の方法。前記出力圧縮状態シーケンスは手書きの単語を認識するものである、請求項1に記載の方法。前記出力圧縮状態シーケンスは車両のタイヤ及びトレーラーの数をカウントして料金を求めるものである、請求項1に記載の方法。前記出力圧縮状態シーケンスは発話を認識するものである、請求項1に記載の方法。前記出力圧縮状態シーケンスにおける各前記状態はラベルを含む、請求項1に記載の方法。前記出力圧縮状態シーケンスは隠れマルコフモデルを用いて求められる、請求項1に記載の方法。前記出力圧縮状態シーケンスは条件付き確率場を用いて求められる、請求項1に記載の方法。前記入力データシーケンスは時系列である、請求項1に記載の方法。前記周辺確率は動的プログラミング前向き後ろ向き手順を用いて求められる、請求項2に記載の方法。隠れマルコフモデルHMM及び条件付き確率場CRFはシーケンシャルデータxをモデリングするための非常に一般的な技法である。CRF及びHMMを用いる状態シーケンス推測手順によって、データの入力シーケンスxを所与として状態シーケンスyの推定が可能になる。しかしながら、多くの用途において、正確な完全な状態シーケンスの推定は必ずしも目標ではない。そうではなく、目標は状態シーケンスxの或る確定関数fを推定して、圧縮状態シーケンスyを得ることである。そのような用途において、従来の状態シーケンス推測技法によって状態シーケンスを推定し、その後、該推定から関数マッピングを求めることは必ずしも最適ではない。したがって、この発明はデータの入力シーケンスxから圧縮状態シーケンスsを直接求める。特に、確定関数fxが固有の状態遷移のみを追跡し、各状態の滞留時間を追跡しない特定の問題を考える。従来の圧縮状態シーケンス推測技法よりも性能が優れた多項式時間圧縮状態シーケンス推測方法を提供する。この発明が解決する問題は、ロボット追跡、文字認識、手書き認識、及び発話認識等の多くの異種の用途において一般に生じる。CRF及びHMMのための従来の状態シーケンス推測技法は、正確な予測に焦点を当てるが、これは目標が各状態の滞留時間を追跡することではなく、状態遷移を追跡することであるいくつかの用途では必要とされない。この発明は、この問題を解決するように明示的に設計された多項式時間状態シーケンス推測手順を提供する。図2A及び図2Bは、この発明の実施の形態による圧縮状態シーケンス推測方法を示している。データの入力シーケンスx={x1,x2,...,xT}201を所与とする。ここでデータはTによってインデックス付けされている。たとえば、シーケンスは時系列である。圧縮復号方法202は、トレーニングされたHMMモデル又はCRFモデルのパラメーター{λj,μk}204を用いて、推定圧縮状態シーケンスs={s1,s2,...,sc}203を直接出力する。本方法のステップは、当該技術分野において既知のようにメモリ及び入力/出力インターフェースに接続されたプロセッサ200において実行することができる。条件付き確率場及び状態シーケンス推測技法直鎖条件付き確率場CRF及び隠れマルコフモデルHMMは、シーケンシャルデータをラベル付けするのに用いることができる2つの確率モデルである。データがラベル付けされた後、状態シーケンスを求めることができる。選択された特徴関数に依拠して直鎖CRF及びHMMを交換可能に用いることができる。この発明はCRFの手順に焦点を当てる。しかしながら、手順はHMMにも等しく適用可能である。この発明の方法にとって、いずれの特定のモデルを用いるかは重要ではない。すなわち、結果は一方から他方に一般化することができる。本明細書では直鎖CRFを用いるが、本方法はHMMにも適用可能である。従来の条件付き確率場条件付き分布px|yをモデル化するための直鎖CRFを以下のように定義することができる。ここで、Ψはポテンシャル関数であり、gは或る状態から次の状態への遷移特徴関数transitionfeaturefunctionであり、uは特徴関数であり、λ及びμはトレーニングプロセスによって推定されるパラメーターであり、Zは入力データシーケンスの関数である正規化係数である。従来の状態シーケンス推測技法データシーケンスの従来のラベル付けは、同時密度y=argmaxypy|xを用い、ここで関数argmaxは最大値を返す。解は、再帰δtj=maxiΨj,i.xtδt-1を用いてビタビ手順により求めることができる。これは、最大積法則に基づいて最可能経路を伝播する。しかしながら、多くの用途において、完全なシーケンスを正確に予測することは非常に困難であるので、個々の予測が用いられる。これは、Forward-Backward前向き後ろ向きと呼ばれる動的プログラミング手順を適用することによって、周辺分布pyi,t|xからyi,tを予測することにより達成することができる。前方再帰はαtj=ΣiΨj,i,xtαt-1iであり、ここでαtjは前方変数であり、後方再帰はβti=ΣiΨt1j,i,xt1βt1jであり、ここでβtiは後方変数である。次に、これらの変数を用いることによって周辺確率を求めることができる。制約付き前方手順を用いて、前方再帰を制約付き状態シーケンスに制約することによって特定の状態シーケンスにおける信頼度を求めることができる。制約集合Y’={yq,...,yr}を所与とすると、変更された前方手順を用いて任意のデータシーケンスがY’を満たす確率を求めることができる。変更された前方再帰は、全てのyt12Y’について、であり、ここで、演算子はjは制約yt1に従うとして定義される。インデックスTにおいて、特定の制約の信頼度はZ’/Zである。ここで、制約付き格子因子は制約付き前方変数を用いて求められ、制約なし格子因子Z=ΣiαTiは制約なし前方変数を用いて求められる。同様に、周辺確率pyi,,t|xを推定している間、集合Y’内に単一の制約yi,tを有することによって同じ方法が辿られる。圧縮状態シーケンス推測この発明の実施の形態は、取得データから状態の圧縮シーケンスを推測するための方法を提供する。人間の動きを予測する1つの用途例では、状態の圧縮シーケンスを、s=compressyとして定義する。ここで、s、j、w、rは任意の状態である。y={s,s,j,j,j,w,w,r,r}である場合、s=compressy={s,j,w,r}である。これ以降、シンボルを用いて関数compressを表す。この発明の目標は、圧縮シーケンスsを可能な限り正確に予測することである。確率ps|xを求めるための枠組みを構築する。圧縮状態シーケンスs0の確率が全てのセグメンテーションyにわたる周辺化によって与えられる。ここで圧縮表現s0の確率は、であり、シンボルは圧縮関数を表す。確率py|xを求めることは効率的であるが、式4の総和は指数関数的な演算数MTを含む。ここでMは状態数であり、Tは完全状態シーケンスyの長さであり、これは扱い難い。したがって、動的プログラミング前向き後ろ向き手順を用いてps=s0|xを求めるための多項式時間手順を提供する。ここでこの発明の圧縮状態シーケンス推測方法の基本ステップを記述する。確率ps=s0|xを求める式4において、圧縮シーケンスs0に対応する指数関数的な個数の可能な完全状態シーケンスyが存在し得る。この問題を克服するために、前方再帰を適用しながらシーケンスsの遷移を追跡することを説明する。図3Aに示すように、シーケンスs0の長さはc=|s0|である。表記を容易にするために、s0の個々の項をsiと呼ぶ。ここで、i=1,...,cである。シーケンスs0内の正確にi-1個の遷移をtまで追跡する前方変数を定義する。インデックスt-1からインデックスtまで、前方変数は以下に基づいて更新される。入力データxtについて同じ状態に留まり矢印311で示される、状態siからsi1への遷移を行う矢印312で示される。動的プログラミング法は以下の通りである。シーケンスs0の確率ps=s0|xはである。これは再帰によって求められる。ここで、i=1,...,cである。インデックス時刻Tにおいて、を得る。この再帰によって、格子正規化係数latticenormalizationfactorを求める。正規化係数Zは、ps=s0|x=Zs0/ZによってZs0を確率に変換する。正規化係数Zの計算は以下に説明される。この方法の証明が付録において与えられている。pc=c0|xを求めるデータxの入力シーケンスを所与とすると、圧縮シーケンスsを求める最初のステップは、シーケンスsの長さcを求めることである。ここで、cは、状態遷移が存在しないことを意味する1から、最大で、全ての1つ1つのインクリメントにおいて遷移が存在することを意味するシーケンス長Tまでの値を取ることができる。全てのc>Tについて、pc=c0|x=0である。長さiの圧縮シーケンスの集合はSiであり、すなわちi=1,...,TについてSi={s:|s|=i}である。i≠jについてである場合、確率pc=c0|xはである。長さcの1つの可能なシーケンスs0の確率はps=s0|xである。図3Bに示すように、2つの可能な圧縮シーケンスs1及びs2を有する場合、である。ここで、は、シーケンスsiに前方再帰が適用されたことを意味する。しかしながら、これらの2つのシーケンスは、圧縮領域の1つの点においてのみ異なる。同じ格子によってシーケンスを表し、複数の計算を回避することを可能にするために、テーブルにのベクトル表現を表す。前方変数αtはM次元であり、以前のはc次元である。この発明のはc×M次元である。格子に対する全ての制約の集合は、Q={...,ql-1,ql,ql1,...}であり、ここで各制約qlはテーブルの非ゼロエントリの1組の座標である。たとえば、特定の圧縮シーケンスs0の場合、集合は{1,s1,2,s2,...,c,sc}に対応する。特定の集合Siの場合、この集合は高さIを有するテーブルの全ての座標に対応し、で表される。所与の制約集合Qのための再帰は以下の通りである。図3Bに示すように、この再帰はテーブル内の全ての非ゼロエントリを通って伝播し、全てのゼロエントリを無視する。なぜなら、ゼロエントリは格子Q内に含まれないためである。図3Cは、制約がインデックスt-1からt及びtからt1の格子の全てのロケーションに含まれる再帰を示している。式6の再帰は、集合Qによって以下のように定義される全ての圧縮シーケンスの確率を求める。制約集合表記を用いると、確率pc=c0|xは、である。これは、制約集合を用いて式6において再帰を適用し、行c0におけるエントリの和を求めることに対応する。上述したように、c0>T又はc0<1のとき、pc=c0|x=0である。この手順を制約集合に対して実行する場合、テーブルの行の和によって全ての格子因子が同時に得られる。このテーブルの総和は正規化係数Zに等しく、これはps=s0|x=Zs0=Z及びを求めるのに必要である。この識別情報は、sの全ての可能な長さ及び組み合わせについて、Zが格子因子の総和に等しいということから得られる。psi=j|x,cを求める周辺分布psi=j|x,cを求めるために、行iにおけるエントリを除いて、高さcを有するテーブルの全てのエントリを含めることによって、制約集合Qi,jを構築する。次に、この集合にi,jを加える。この特定の制約集合構成は、長さc及びsi=jの全ての可能な圧縮シーケンス構成を含む。このとき、周辺確率は、psi=j|x,c=ZQi,j/ΣjZQi,jである。圧縮シーケンス次に、上記のステップを適用し、以下を最大にすることによって、圧縮状態シーケンスが求められる。によってcを推定し、によってsjを推定する。データから状態シーケンスを生成するための方法上記に続いて、図2Bは方法202をより詳細に示している。最初に、p=c|xに従って入力データシーケンスx={x1,x2,...,xT}201に対応する、可能な圧縮状態シーケンスの長さc261の確率を求める251。ここで、i=1,...,Tである。次に、出力圧縮状態シーケンス203の長さ262を推定する252。ここで、長さはargmaxpc|xに従う最大確率を有し、関数argmaxは最大確率を返す。次に、に従う長さを有する出力圧縮状態シーケンス内の各状態sj263の確率を求める253。ここで、である。そして最後に、に従う最大確率を有する各圧縮状態を推定して254、出力圧縮状態シーケンスを推定する。これらのステップはプロセッサにおいて実行される。応用形態この発明の圧縮状態シーケンス推測方法の以下の応用形態を説明する。移動ロボットのロケーション追跡移動ロボットへの応用形態において、ロボットはグリッドを用いて環境内で追跡される。特に環境を発掘する目的で、シーケンシャルモデルが頻繁に用いられる。この応用形態では、正確なグリッド反復は重要でなく、ロボットが順番に横切ったロケーションを示す圧縮バージョンが重要である。例示的なロボット応用形態について図4Aに示されているように、ロボットは該ロボットが部屋の色青B、緑G、黄Y、赤r、及びそのロケーションへの動きを妨げる障害物ブロックを検知することができる環境内を移動する。全てのステップにおいて、ロボットは移動{上、下、左、右}を試みる。ここでロボットは方向をランダムに選択する。意図される方向に障害物が存在する場合、ロボットは再度試行する。図4Bは、ロボットの一例示の経路401を示している。この問題において、状態はx,y座標におけるロボットのロケーションを指し、観測値は観測される色を指し、これはセンサー、たとえばカメラの出力である。図4Cは、図4Bにおける経路401について、観測される色の観点で、時間の関数として動きを示している。不都合なことに、色検出の的中率は不完全である可能性があり、たとえば平均80である。この場合、ロボットは異なるロケーションにいるにも関わらず、図4Cの雑音402によって示すようにセンサー出力は誤ったものとなる。しかしながら、圧縮状態シーケンス推測方法は、カメラ観測値のシーケンスに関して、ロボットが順番に横切る正しいロケーションを予測する。単一ストローク文字認識この応用形態は、スマートフォン、携帯情報端末PDA、及びタブレットPC等の、タッチスクリーンを用いて文字及びグリフの入力を可能にする電子デバイスと共に用いることができる。一般に、問題は、通常1つの連続ストロークでタッチスクリーン上に描かれた形状を認識することである。この応用形態では、状態は方向{上、右、下、左}を指し、観測値は連続する入力点間の量子化された角度を指す。一般に、現在のシステムは、この目的のために確率的有限状態マシン又はHMMを用いる。通例、HMM又は有限状態マシンは単一の文字に関してトレーニングされる。次に、モデルを用いたデータ尤度試験によって1つのクラスが選択される。この方法の1つの欠点は、任意の形状を扱う能力が限られていることである。全ての文字について単一のモデルをトレーニングして、そのモデルを用いることによって状態を復号することができる。それにもかかわらず、単一の状態誤りによって予測全体が誤ったものとなる可能性がある。このため、雑音に耐性のある状態シーケンス推測方法を提供する。さらに、1つの状態から別の状態への移行は通常曖昧であるので、状態遷移における曖昧性も問題である。しかしながら、この発明の方法は正確な遷移を推定しない。その代わり、この発明の方法は、このタスクには十分である遷移シーケンスを生成する。観測値、たとえばユーザーインターフェースから取得される連続点間の量子化された角度を所与とすると、この発明の圧縮状態シーケンス推測方法は、全ての方向を順番に生成し、これは特定の文字を示す。手書きの単語認識手書きの認識は通常、最初に手書きをセグメント化し、次にそれらのセグメントをサポートベクターマシンSVM等のマルチクラス分類器を用いて認識することによって実行される。多くの場合に、言語の文法も用いられる。しかしながら、セグメント化は前処理として行われることが通常想定される。この発明の方法によれば、文字はセグメント化されず、シーケンスの長さは知られることも必要とされることもない。なぜなら、手書きの単語は異なる長さを有する可能性があるためである。入力の手書きは画像の形態をとる。この応用形態では、各インクリメントは手書きの画像内の1つの垂直列に対応する。状態は対応するセグメントを指し、観測値は形状コンテキスト特徴に対応する。特徴を抽出する間、まずスライディングウィンドウ技法を用いることによって画像から重複するパッチを取る。画像内の列毎に1つのパッチが取られる。次に、形状コンテキスト記述子を適用する。次に、K平均クラスタリングを適用して、トレーニングデータを用いて辞書をトレーニングする。また、トレーニングされた辞書内のパッチ毎にヒストグラムを生成する。トレーニングされた辞書は、パッチから抽出された各点を該辞書内のクラスター中心にマッピングする。CRFモデルはインクリメント毎の観測値としての形状コンテキスト特徴のヒストグラムを用いてトレーニングされ、状態はその観測値を生成する文字に対応する。分類している間、同じマッピング手順を実行し、トレーニングセットとの共有空間、すなわちヒストグラム空間を有するようにする。試験を通じたスライディングウィンドウを通じて求められた観測値、たとえば形状コンテキスト特徴のヒストグラムを所与とすると、圧縮状態シーケンス推測は、シーケンス内の所与の単語における文字を予測する。料金収受電子料金収受ETCの応用形態において、目標は、カメラ又は3Dセンサーを用いて車両のタイヤ及びトレーラーの数をカウントすることである。圧縮状態シーケンス推測方法は、経時的にこれらの観測値を用いて、全ての状態、たとえば車体、タイヤ、牽引棒を推定し、これによって、料金を求めるための、車両のタイヤ及びトレーラーの数に関する情報がもたらされる。発話認識発話認識において、HMM、並びにビタビ及びForward-Backward等の従来の状態シーケンス推測方法は、多くの場合に、発話された単語をテキストに変換するために用いられる。オーディオ信号の基礎にある状態は音素であり、一般的に、2つの状態間の正確な遷移点は曖昧である。しかしながら、発話された単語の速度に基づいて、オーディオ信号の長さは同じ単語について変動する可能性がある。圧縮状態シーケンス推測は、正確な遷移点を見つけることなく発話された単語を音素に復号する。これは発話認識には十分な情報である。付録証明。一般性を損なうことなく、s0,1=1、s0,2=2、s0,3=3、...s0,c=cとし、t1、t2からtc-1までを状態遷移時間とする。すなわちt1はs0,1=1からs0,2=2への遷移である。式13において、分配法則を用いることによって式12を書き換える。式14において、単に時間Tを計算から除外することによって総和を2つのケースに分割する。1第1の部分は、時刻Tにおいてc-1からcへの遷移が存在するケースを考え、2第2の部分は時刻Tにおいて遷移が存在せず、このためc-1からcへの遷移がTより前であり、時刻Tにおいて以前の状態cが反復されると考える。次に、αTとしてのs領域の前方変数を以下のように定義する。このとき、式14における2つの総和項をこれらの前方変数に関して以下のように書き換えることができることが明らかである。最後に、再帰式を得る。この証明は全ての長さcについて有効である。換言すれば、1からc-1までの信号をこの発明の信号と見なすことができる。このため、任意の長さにおいて、時刻Tにおける再帰は以下のように書くことができる。さらに、これは、Tに戻って再帰することによって任意のt=1,...,Tにも同様に一般化することができる。このため、最終形式は、となる。"