図面 (/)

技術 情報処理システム、情報処理方法及びプログラム

出願人 株式会社デンソーアイティーラボラトリ
発明者 内海慶
出願日 2016年4月20日 (5年1ヶ月経過) 出願番号 2016-084325
公開日 2017年10月26日 (3年7ヶ月経過) 公開番号 2017-194818
状態 特許登録済
技術分野 知識ベースシステム
主要キーワード 状態クラス ベータ分布 補助変数 状態列 最大次数 観測系列 スパースネス 隠れ変数
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年10月26日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (15)

課題

隠れマルコフモデルにおいて、二つ以上前の状態を考慮しつつ計算量を抑える。

解決手段

過去にサンプルされた状態列文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定部11と、状態列の対象位置における観測系列と、当該対象位置を基準として決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を状態列の各位置において決定する確率決定部13と、状態列の各位置において、決定された当該位置における前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定部14と、決定された状態列を用いて、文脈木を更新する更新部15と、を備える。更新後の文脈木を用いて、次数決定部で次数が決定され、その後、確率決定部、状態列決定部、及び更新部の処理が繰り返される。

概要

背景

系列データを処理するための手法として、隠れマルコフモデル(Hidden Markov Model:HMM)が広く使われている。音声認識においては音声信号音声符号に変換するための音響モデルとして、自然言語処理では形態素解析品詞推定等に用いられる。多くの場合、計算量の問題から出力となる状態は1つ前の状態にのみ依存する1次マルコフモデル、あるいは長い状態の依存を考慮する場合でも2次マルコフモデルが用いられている。しかし、現実のデータにおいてある時刻の状態が直前の状態にのみ依存しているとは限らない。時刻t−2よりも更に過去の状態に依存している場合もあれば,現在時刻tの状態はそれ以前の状態とは独立である場合も考えられる。これまで提案されてきたHMMの手法では、状態数をデータによって可変にするinfinite HMM(非特許文献1参照)や、出力変数(Emission)で過去の値への依存を考慮するAuto-Regressive HMM(非特許文献2参照)等が提案されている。

概要

隠れマルコフモデルにおいて、二つ以上前の状態を考慮しつつ計算量を抑える。過去にサンプルされた状態列文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定部11と、状態列の対象位置における観測系列と、当該対象位置を基準として決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を状態列の各位置において決定する確率決定部13と、状態列の各位置において、決定された当該位置における前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定部14と、決定された状態列を用いて、文脈木を更新する更新部15と、を備える。更新後の文脈木を用いて、次数決定部で次数が決定され、その後、確率決定部、状態列決定部、及び更新部の処理が繰り返される。

目的

本発明は、上記問題に鑑みてなされたものであり、隠れマルコフモデルにおいて二つ以上前の状態を考慮しつつ計算量を抑えることを可能とする情報処理システム情報処理方法及びプログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

過去にサンプルされた状態列文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定部と、状態列の対象位置における観測系列と、当該対象位置を基準として前記決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を前記状態列の各位置において決定する確率決定部と、前記状態列の各位置において、前記決定された当該位置における前記前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定部と、前記決定された状態列を用いて、前記文脈木を更新する更新部と、を備え、更新後の前記文脈木を用いて、前記次数決定部で前記次数が決定され、その後、前記確率決定部、前記状態列決定部、及び前記更新部の処理が繰り返される情報処理システム

請求項2

前記文脈木は、階層ベイスモデルによって推定されたサンプル済の状態列の配置である請求項1に記載の情報処理システム。

請求項3

前記確率決定部は、前記前向き確率を計算するときの前記観測系列の確率の計算において、これまでの全ての観測系列を使用する請求項1または2に記載の情報処理システム。

請求項4

前記文脈木は前記状態遷移の文脈木と出力変数の文脈木とがあって、前記出力変数の文脈木は状態の数だけある請求項1から3のいずれか一項に記載の情報処理システム。

請求項5

前記決定された状態列の各位置における次数を用いて、状態列の各位置における閾値を確率的にサンプリングする閾値決定部を更に備え、前記確率決定部は、前記状態列の各位置において、前記決定された当該位置における前記閾値未満の遷移確率を無視して、前記決定された当該位置における前記閾値以上の遷移確率を用いて前記前向き確率を計算する請求項1から4のいずれか一項に記載の情報処理システム。

請求項6

過去にサンプルされた状態列の文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定手順と、状態列の対象位置における観測系列と、当該対象位置を基準として前記決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を前記状態列の各位置において決定する確率決定手順と、前記状態列の各位置において、前記決定された当該位置における前記前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定手順と、前記決定された状態列を用いて、前記文脈木を更新する更新手順と、更新後の前記文脈木を用いて、前記次数決定手順で前記次数が決定され、その後、前記確率決定手順、前記状態列決定手順、及び前記更新手順の処理が繰り返される手順と、を有する情報処理方法

請求項7

コンピュータを、過去にサンプルされた状態列の文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定部と、状態列の対象位置における観測系列と、当該対象位置を基準として前記決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を前記状態列の各位置において決定する確率決定部と、前記状態列の各位置において、前記決定された当該位置における前記前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定部と、前記決定された状態列を用いて、前記文脈木を更新する更新部と、として機能させるためのプログラムであって、更新後の前記文脈木を用いて、前記次数決定部で前記次数が決定され、その後、前記確率決定部、前記状態列決定部、及び前記更新部の処理が繰り返されるプログラム。

技術分野

0001

本発明は、情報処理システム情報処理方法及びプログラムに関する。

背景技術

0002

系列データを処理するための手法として、隠れマルコフモデル(Hidden Markov Model:HMM)が広く使われている。音声認識においては音声信号音声符号に変換するための音響モデルとして、自然言語処理では形態素解析品詞推定等に用いられる。多くの場合、計算量の問題から出力となる状態は1つ前の状態にのみ依存する1次マルコフモデル、あるいは長い状態の依存を考慮する場合でも2次マルコフモデルが用いられている。しかし、現実のデータにおいてある時刻の状態が直前の状態にのみ依存しているとは限らない。時刻t−2よりも更に過去の状態に依存している場合もあれば,現在時刻tの状態はそれ以前の状態とは独立である場合も考えられる。これまで提案されてきたHMMの手法では、状態数をデータによって可変にするinfinite HMM(非特許文献1参照)や、出力変数(Emission)で過去の値への依存を考慮するAuto-Regressive HMM(非特許文献2参照)等が提案されている。

先行技術

0003

M.J.Beal, Z.Ghahramani, and C.E.Rasmussen, "The Infinite Hidden Markov Model," NIPS, 2001
Murphy, Kevin P. "Switching kalman filters." technical report, UC Berkeley, 1998

発明が解決しようとする課題

0004

しかし、各時刻tの状態について2次を超える高次モデルはこれまで計算量的に難しい。また仮に計算量の問題が無かったとしてもデータスパースネスの問題から現実的ではなかった。

0005

本発明は、上記問題に鑑みてなされたものであり、隠れマルコフモデルにおいて二つ以上前の状態を考慮しつつ計算量を抑えることを可能とする情報処理システム、情報処理方法及びプログラムを提供することを目的とする。

課題を解決するための手段

0006

本発明の第1の態様に係る情報処理システムは、過去にサンプルされた状態列文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定部と、状態列の対象位置における観測系列と、当該対象位置を基準として前記決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を前記状態列の各位置において決定する確率決定部と、前記状態列の各位置において、前記決定された当該位置における前記前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定部と、前記決定された状態列を用いて、前記文脈木を更新する更新部と、を備え、更新後の前記文脈木を用いて、前記次数決定部で前記次数が決定され、その後、前記確率決定部、前記状態列決定部、及び前記更新部の処理が繰り返される。

0007

この構成によれば、必要なところは高次まで参照し、必要ないところは低次までしか参照しないので、探索範囲が減り、計算量を抑えることができる。

0008

本発明の第2の態様に係る情報処理システムは、第1の態様に係る情報処理システムであって、前記文脈木は、階層ベイスモデルによって推定されたサンプル済の状態列の配置である。

0009

この構成によれば、状態遷移の事前分布が、指数的に減少する分布(べき乗則を表す分布)となる。状態遷移の事前分布は、次数が大きくなるとともにより急峻な分布となる。サンプルされた状態遷移から推定された高次の遷移確率は、事前分布を入れたことで少数の高次の状態遷移が高い確率を持ち、その他のほとんどの状態遷移はゼロではないが小さい確率が与えられる。これにより、次数が高次の場合は、ほとんどの状態遷移を無視することができ、計算の爆発を避けられるとともに、ほとんどの状態遷移の確率が0となってしまうデータスパースネスの問題も解決できる。

0010

本発明の第3の態様に係る情報処理システムは、第1または2の態様に係る情報処理システムであって、前記確率決定部は、前記前向き確率を計算するときの前記観測系列の確率の計算において、これまでの全ての観測系列を使用する。

0011

この構成によれば、観測系列について最大の次数まで考慮することができるので、観測系列について全ての問題を考慮することができる。

0012

本発明の第4の態様に係る情報処理システムは、第1から3のいずれかの態様に係る情報処理システムであって、前記文脈木は前記状態遷移の文脈木と出力変数の文脈木とがあって、前記出力変数の文脈木は状態の数だけある。

0013

この構成によれば、状態毎に出力変数確率を変更することができる。例えば、状態が品詞を表す場合には、状態が名詞のときと動詞のときとで出力確率を変更することができる。

0014

本発明の第5の態様に係る情報処理システムは、第1から4のいずれかの態様に係る情報処理システムであって、前記決定された状態列の各位置における次数を用いて、状態列の各位置における閾値を確率的にサンプリングする閾値決定部を更に備え、前記確率決定部は、前記状態列の各位置において、前記決定された当該位置における前記閾値未満の遷移確率を無視して、前記決定された当該位置における前記閾値以上の遷移確率を用いて前記前向き確率を計算する。

0015

この構成によれば、閾値未満の遷移確率を無視できるので、状態が増えたとしても計算量の増加を抑えることができる。

0016

本発明の第6の態様に係る情報処理方法は、過去にサンプルされた状態列の文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定手順と、状態列の対象位置における観測系列と、当該対象位置を基準として前記決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を前記状態列の各位置において決定する確率決定手順と、前記状態列の各位置において、前記決定された当該位置における前記前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定手順と、前記決定された状態列を用いて、前記文脈木を更新する更新手順と、更新後の前記文脈木を用いて、前記次数決定手順で前記次数が決定され、その後、前記確率決定手順、前記状態列決定手順、及び前記更新手順の処理が繰り返される手順と、を有する。

0017

この構成によれば、必要なところは高次まで参照し、必要ないところは低次までしか参照しないので、探索範囲が減り、計算量を抑えることができる。

0018

本発明の第7の態様に係るプログラムは、コンピュータを、過去にサンプルされた状態列の文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する次数決定部と、状態列の対象位置における観測系列と、当該対象位置を基準として前記決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を前記状態列の各位置において決定する確率決定部と、前記状態列の各位置において、前記決定された当該位置における前記前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する状態列決定部と、前記決定された状態列を用いて、前記文脈木を更新する更新部と、として機能させるためのプログラムであって、更新後の前記文脈木を用いて、前記次数決定部で前記次数が決定され、その後、前記確率決定部、前記状態列決定部、及び前記更新部の処理が繰り返されるプログラムである。

0019

この構成によれば、必要なところは高次まで参照し、必要ないところは低次までしか参照しないので、探索範囲が減り、計算量を抑えることができる。

発明の効果

0020

本発明によれば、必要なところは高次まで参照し、必要ないところは低次までしか参照しないので、探索範囲が減り、計算量を抑えることができる。

図面の簡単な説明

0021

本実施形態に係るvHMMの生成モデルである。
観測ngramの文脈木の一例である。
次数ntが2の場合の状態遷移確率について説明するための図である。
本実施例に係る情報処理システム10の概略ブロック図である。
本実施例に係るCPU1の機能ブロック図である。
一つ前の位置t−1に状態番号1の状態であるときの位置tにおける確率分布の一例である。
一つ前の位置t−1から位置tへの遷移確率を表す表である。
文末の一例を示す図である。
vHMMの学習アルゴリズムの一例を示すフローチャートである。
実験例において設定されたBOSからの遷移確率の真値である。
一実験例において設定された遷移確率の真値である。
一実験例におけるBOSからの遷移確率の推定結果である。
一実験例における遷移確率の推定結果である。
一実験例における学習時の状態数の変化である。

実施例

0022

<本実施形態の概要
本発明の実施形態(以下、本実施形態という)では、第1に、iHMMの状態依存の次数nを確率変数として扱い、次数nそのものもデータから決定する。さらに出力変数(Emission)にも確率変数として次数nを与え、出力変数(Emission)の次数nもデータから推定する。これにより、必要なところは高次まで参照し、必要ないところは低次までしか参照しないので、探索範囲が減り、計算量を抑えることができる。

0023

更に、本実施形態というでは、第2に、状態遷移及び観測値について事前分布を与えることにより、高次HMMの場合に問題となるデータスパースネスの問題を解決する。以下、本発明の実施形態について、図面を参照しながら説明する。

0024

本実施形態では,ビームサンプリング(Beam Sampling:J.V.Gael et. Al, “Beam Sampling for The Infinite Hidden Markov Model,” ICML2008.)を基にし、(1)状態遷移及び出力変数(Emission)の事前分布として階層Pitman-Yor過程(以下、HPYLMという、Yee.Whye.Teh, ”Hierarchical Bayesian Language Model based on Pitman-Yor Processes,” ACL2006.)を用いる。ただし、Tehの提案するHPYLMでは、次数nは固定となるため、ここでは可変次数を扱えるよう拡張を行った持橋らのVPYLM(Mochihashi, et. al. “Infinite Markov Model.” NIPS 2007.)を用いる。

0025

<ビームサンプリング(Beam Sampling)>
まず、ベースとなるビームサンプリング(Beam Sampling)について説明する。
ビームサンプリングは,infinite HMM(iHMM)の状態列のサンプリングに動的計画法を用いて効率よく計算を行う手法である。従来のinfinite HMMでは、状態数無限を扱うために、ラティス構築して動的計画法で計算することが難しく、そのため系列(状態列)の各位置tにおける状態の確率はそれぞれ独立と仮定し、各位置tの状態のみを逐次的に更新してパラメータを更新するギブスサンプリング(Gibbs Sampling)を用いていた。

0026

それに対して、ビームサンプリングでは、出現確率に対して補助変数(閾値ともいう)uを設定し、出現確率が補助変数u以上となる状態まで抽出しそれ以外の状態を一つの状態にまとめるスライスサンプリング(slice sampling)を用いる。このスライスサンプリングを用いることで無限の状態数を有限の状態数に抑えることができる。このため、動的計画法を用いることで状態列を効率よく同時にサンプリングすることができる。

0027

<iHMMについて>
続いて、本実施形態で提案するVariable order infinite hidden Markov model (vHMM)について説明する前に、その比較としてiHMMについて説明する。iHMMの生成モデルを次の式で表される。

0028

0029

yは観測値を表し、sは状態を表す。iHMMでは状態数を無限とするため、(1)式の状態遷移確率及び、word emission確率(状態から観測が生成される条件付き確率)に事前分布として階層ディクレ過程を導入する。(1)式の同時確率から状態列をサンプリングする際、状態数が無限の場合にはHMMのラティスを組むことができない。そこで,ビームサンプリングでは系列(状態列)の各位置tに対して補助変数uを導入する。uは[0,πst-1st]の値の一様分布からサンプリングされる。

0030

0031

πは状態遷移確率を表し、πst-1stはサンプル済みの状態列の位置t−1からtへの状態遷移の確率を表す。

0032

系列(状態列)の全ての位置で、状態Kへの遷移確率がutを下回るまでStick-breaking process(SBP)によって状態を生成し、状態Kをインクリメントする。状態が生成された際に、状態Kから既存の状態への遷移は、SBPで作られた各状態のGlobal Transition Probabilityを集中度パラメータとしてディリクレ過程から生成する。上記の手続きによって、補助変数uによって各位置tでの状態遷移は有限に抑えられる。
系列(状態列)の各位置tにおける状態と観測値の同時確率(前向き確率)の式を以下に示す。

0033

0034

式(2)より,前向き確率は再帰式によって表され、動的計画法によって効率良く計算が可能となる。

0035

<vHMMについて>
続いて、本実施形態において提案するvHMMについて説明する。図1は、本実施形態に係るvHMMの生成モデルである。図1に示すように、状態列s=[s0, s1, s2, …, sT]の各位置において過去何個前までの状態まで参照するかを示す次数が可変である。また、観測系列y=[y0, y1, y2, …, yT]の各位置において過去何個前までの出力を参照するかを示す次数が可変である。状態列sの次数と、観測系列yの次数は独立である。

0036

本実施形態で提案するvHMMでは、系列(状態列)の各位置tについて次数nを導入する。vHMMの生成モデルは次の式で表される。

0037

0038

ここで、右辺の1番目の確率p(y0t|st)は出力確率を表し、右辺の2番目の確率p(st|st—nt+1t-1)は状態遷移確率を表す。また、右辺の3番目の確率p(s,y,n)は、transition VPYLMの代理客の配置zから次数nを確率的にサンプリングするときの確率である。

0039

ここで、図2を用いて出力確率を説明する。図2は、観測ngramの文脈木の一例である。図2の文脈木において、木の各ノードレストランを表す。観測されたngramに対応するレストランに客を追加する状況を想定する。図2の例では、“2 1 3”というtrigram は1回、“2 1 5”というtrigramは2回観測されている。単純に考えると“2 1 3”というtrigramの出力確率P(3|2,1)=P(pass0)×P(pass1)×P(stop2)×1/6であり、“2 1 5”というtrigramの出力確率P(5|2,1)=P(pass0)×P(pass1)×P(stop2)×2/6であるが、実際には階層的なスムージングが入るため、予測確率の計算は次のように計算される。なお、P(pass0)は0階層を通過する確率、P(pass1)は1階層を通過する確率、P(stop2)は2階層で止まる確率である。
すなわち、予測確率は、次のステップにより計算される。
1.文脈uと単語wを受け取る。
2.次数(オーダー)nの積分消去を実行する。
その際に、(1)次数(オーダー)nについて、n次で停止する確率P(n|context)を計算する。(2)次数(オーダー)をnとした時の、n次の文脈|u|=nで単語wが生成する確率であるngram確率P(w|context,n)を計算する。確率P(n|context)と、ngram確率P(w|context,n)を掛け合わせた物を全てのnについて足し合わせることにより、予測確率が算出される。ここで、確率P(n|context)と、ngram確率P(w|context,n)はそれぞれ次の式で表される。

0040

0041

a,bはそれぞれ文脈の深さnにおいて客が停止した回数,通過した回数を表す.VPYLMの更新時に,観測されたn-gramの次数nをサンプリングし,深さnの文脈へ客を追加することで,対応する文脈のレストランが持つaの頻度は更新され,そこに至るまでの文脈木の経路にある全てのレストランの持つbの頻度が更新される.αおよびβはベータ分布ハイパーパラメータを表し,通常は一様分布となるようα,βともに1が入る。
n-gram確率のcは文脈に対応するレストランにおける単語wの観測頻度,tは文脈に対応するレストランにおける単語wについて,チャニーズレストランプロセスで推定されたテーブル数を表し,単語wが低次の文脈から生成されたと推定された回数を意味する。d,θはPitman-Yor言語モデルのハイパーパラメータであり,dは深さnにおける頻度に対するディスカウントを,θは低次のn-gram確率を用いたスムージングの強さをコントロールする。π(context)は親の文脈を表し,文脈を1つ落とし低次のn-gramを見ることを意味する。

0042

続いて、図3を用いて次数ntが2の場合の状態遷移確率について説明する。図3は、次数ntが2の場合の状態遷移確率について説明するための図である。図3において、表T1には、位置t−2の状態番号及び位置t−1の状態番号が与えられたときに、位置tにおいて状態番号3が出現する確率が示されている。例えば、次数ntが2の場合において、位置t−2の状態番号が1で且つ位置t−1の状態番号が2の場合、位置tで状態番号が3になる確率はP12である。

0043

状態遷移及び出力変数にVPYLMを用いるため、新規状態への遷移確率は、次の式で表される。

0044

0045

ここで、G0は、新規の状態クラス生成確率である。例えば、1から10までの状態クラスがあったときに、11〜∞が一つにまとめられた状態クラスから、一つの11の状態クラスを作る確率がG0となる。

0046

状態列sの各状態はそれぞれが生成された隠れた次数nが存在すると仮定している.zは階層Pitman−Yor過程の階層Chinese restaurant process表現(Chinese restaurant franchise)における代理客の配置を表す隠れ変数である。vHMMのビームサンプリングでも同様に補助変数(閾値ともいう)utを導入する。utは状態列の各位置tで異なり、各位置tで以下のようにサンプルされる。

0047

0048

すなわち、状態列の各位置tにおいて、平均0且つ分散p(st|st—nt+1t-1)の一様分布から、補助変数(閾値ともいう)utがサンプリングされる。ここで、状態列の各位置tにおいて、nt自身もサンプリングされる。次数nの項は,ベイズの定理から次のように展開できる。

0049

0050

ここで式(4)の右辺の第1項はVPYLMで計算した状態のn-gram確率である。式(4)右辺の第2項にはVPYLMに置ける次数nでの代理客の停止確率が使用される。このように、次数nでの停止確率を用いて学習時には、状態列の各位置でntがサンプリングされる。
vHMMの前向き確率を次の式で表される。

0051

0052

ここで、nt>nt-1の場合、t−1が持つ低次の前向き確率で高次の前向き確率を近似する。一方、nt<nt-1の場合、t−1の前向き確率を周辺化してtの次数にあわせる。
式(5)により,vHMMが高次の場合でもビームサンプリング(Beam Sampling)が適用できる。また、状態列の持つ隠れ変数をChinese Restaurant Franchise (CRF)の代理客の配置から推定しサンプルすることで、データから次数自体も得ることができる。状態遷移確率は事前分布として一例として階層Pitman-Yor過程を用いており、学習時のラティスに新規の状態K+1を各位置で持たせることで,iHMM同様に状態数自体もデータから推定することができる。

0053

<本実施形態の効果>
本実施形態のiHMMを用いることで,既存のHMMを用いた手法では扱えなかった、高次の状態依存を効率良く扱うことが可能となる。また、データが持つ本来の次数も学習を行うことで、データの持つ複雑さを事前に仮定することなしに得ることができる。
従来、高次HMMの学習は状態遷移の組合せが爆発するため、使用可能な学習データでは十分学習が行えず、精度を出すことができなかった。しかし。提案手法では階層Pitman-Yor過程を事前分布に置くことによって適切なスムージングを行い、入手可能なサイズのデータからでも精度を落とすことなく高次HMMの学習が行える。また,階層Pitman-Yor過程を事前分布として置くことにより,高次の状態遷移確率は、より急峻な分布を持つ。そのため、ビームサンプリング(Beam Sampling)では殆どの状態遷移が足切りされ、高次でも効率良く前向き確率の計算が可能となる。

0054

<実施例>
続いて、本発明の一つの実施例について説明する。図4は、本実施例に係る情報処理システム10の概略ブロック図である。図4に示すように、CPU(Central Processing Unit)1、入力部2、RAM(Random Access Memory)3、記憶部4を備える。入力部2、RAM3及び記憶部4は、CPU1とバスを介して接続されている。
入力部2は、ユーザの入力を受け付け、受け付けた入力を示す情報をCPU1へ出力する。
RAM3には、情報を一時的に保持する。
記憶部4には、CPU1が読み出して実行するプログラムが格納されている。また、記憶部4には、文脈木に関する情報が記憶されている。

0055

CPU1は、記憶部4に格納されているプログラムを読み出して実行することにより、図5に示す次数決定部11、閾値決定部12、確率決定部13、状態列決定部14、更新部15及び判定部16として機能する。図5は、本実施例に係るCPU1の機能ブロック図である。

0056

次数決定部11は、記憶部4を参照して、過去にサンプルされた状態列sの文脈木の配置を用いて、状態列の各位置において過去何個前までの状態まで参照するかを示す次数を決定する。例えば、次数決定部11は、状態列sの各位置の次数を、ベータ分布の期待値でサンプリングする。
ここで、文脈木は、階層ベイスモデルによって推定されたサンプル済の状態列の配置である。本実施形態では一例として、階層ベイスモデルは、階層ピットマンヨー過程である。なお、階層ベイスモデルは、階層ディリクレ過程(HDP)でもよい。

0057

この構成によれば、状態遷移の事前分布が、指数的に減少する分布(べき乗則を表す分布)となる。状態遷移の事前分布は、次数nが大きくなるとともに急激に減衰する特性を有し、この状態遷移の事前分布がベータ分布に乗算されることによって、状態遷移の確率分布が生成される。これにより、次数nが高次の項に対しては、ほとんどの高次の状態遷移の遷移確率が小さくなるので、ほとんどの高次の次数の状態遷移を無視することができ、計算の爆発を避けられるとともに、階層ベイズモデルを事前分布に用いた適切なスムージングによってデータスパースネスの問題も解決できる。

0058

また、文脈木は状態遷移の文脈木と出力変数の文脈木とがあって、出力変数の文脈木は状態の数だけある。これにより、状態毎に出力変数確率を変更することができる。例えば、状態が品詞を表す場合には、状態が名詞のときと動詞のときとで出力確率を変更することができる。

0059

閾値決定部12は、決定された状態列の各位置における次数を用いて、状態列の各位置tにおける閾値を確率的にサンプリングする。

0060

確率決定部13は、状態列の対象位置における観測系列yと、当該対象位置を基準として決定された次数だけ前の位置から当該対象位置までの状態遷移とが同時に起こる確率である前向き確率を状態列の各位置において決定する。
このとき確率決定部13は、前向き確率を計算するときの観測系列yの確率の計算において、これまでの全ての観測系列を使用する。これにより、観測系列について最大の次数まで考慮することができるので、観測系列について全ての問題を考慮することができる。

0061

具体的には例えば、確率決定部13は、式(7)に従って、前向き確率を状態列の各位置において決定する。

0062

図6は、一つ前の位置t−1に状態番号1の状態であるときの位置tにおける確率分布の一例である。ここで例えば閾値ut=0.1であるとすると、状態番号1〜10は閾値ut=0.1以上であるが、状態番号11〜∞は閾値ut未満である。この場合、例えば、一つ前の位置t−1から位置tへの遷移確率は、例えば図7のように表される。図7は、一つ前の位置t−1から位置tへの遷移確率を表す表である。図7の表において、位置t−1の状態番号が1の場合、位置tにおいて状態番号1〜10は閾値ut=0.1以上の遷移確率を示し、状態番号11〜∞は一つに合算された遷移確率が示されている。

0063

確率決定部13は例えば、状態列の各位置において、決定された当該位置tにおける閾値ut未満の遷移確率(例えば、図7の表における状態番号11〜∞の遷移確率)を無視して、決定された当該位置における閾値ut以上の遷移確率(例えば、図7の表における状態番号1〜10の遷移確率)を用いて前向き確率を計算する。より詳細には、確率決定部13は例えば、当該位置における閾値ut以上の確率を持つ遷移について、当該位置に到達する全ての状態遷移と観測系列の同時確率を周辺化することで前向き確率を計算する。

0064

この構成によれば、閾値ut未満の遷移確率(例えば、図7の表における状態番号11〜∞の遷移確率)を無視できるので、状態が増えたとしても計算量の増加を抑えることができる。

0065

状態列決定部14は、状態列の各位置において、決定された当該位置における前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する。図8は、文末の一例を示す図である。具体的には、図8に示すように、状態列決定部14は、状態列の各位置において、決定された当該位置における前向き確率を用いて、状態列の文末から確率的に状態をサンプリングする。

0066

更新部15は、決定された状態列を用いて、記憶部4に記憶されている文脈木を更新する。そして、更新後の文脈木を用いて、次数決定部11で再び次数が決定され、その後、閾値決定部12、確率決定部13、状態列決定部14、及び更新部15の処理が繰り返される。

0067

続いて上記の構成を有する情報処理システム10の動作について図9を用いて説明する。図9は、vHMMの学習アルゴリズムの一例を示すフローチャートである。

0068

(ステップS101)まずCPU1は、入力として観測系列yを取得する。

0069

(ステップS102)次にCPU1は、初期値として状態列sをランダムに設定する。

0070

(ステップS103)次にCPU1は、状態遷移確率と出力変数(Emission)確率を更新する。

0071

(ステップS104)次に次数決定部11は、状態列の各位置において次数を決定する。

0072

(ステップS105)次に閾値決定部12は、状態列の各位置における閾値を確率的にサンプリングする。

0073

(ステップS106)次に確率決定部13は、状態列の各位置において前向き確率を決定する。

0074

(ステップS107)次に状態列決定部14は、状態列の各位置において、決定された当該位置における前向き確率を用いて、状態を確率的にサンプリングして状態列を決定する。

0075

(ステップS108)次に更新部15は、決定された状態列を用いて、状態遷移の文脈木と出力変数の文脈木を更新する。

0076

(ステップS109)次に更新部15は、状態遷移確率と出力変数(Emission)確率を更新する。

0077

(ステップS110)次に判定部16は、収束条件を満たすか否か判定する。収束条件を満たす場合、終了する。収束条件を満たさない場合、処理がステップS104に戻る。

0078

<実験データ>
続いて、本実施例に係る一実験例について説明する。本実験例では、長さ20の系列を100件生成し、語彙数8、状態数4とし、初期状態数10、遷移の最大次数6(7−gram)、出力変数の最大次数4(5−gram)で学習した。

0079

図10は、一実験例において設定されたBOSからの遷移確率の真値である。BOSから状態番号1の状態に遷移することが示されている。図11は、一実験例において設定された遷移確率の真値である。図11の表では、遷移先の状態番号と遷移先の状態番号によって遷移確率が特定される。例えば、BOSからは状態番号1の状態に遷移するので、この状態番号1の状態から更に状態番号が2、3の状態に遷移する。

0080

図12は、一実験例におけるBOSからの遷移確率の推定結果である。BOSから状態番号1の状態への遷移確率が1に近い値になっており、他の状態への遷移確率が0に近い値になっており、学習が成功したことを示している。

0081

また、図13は、一実験例における遷移確率の推定結果である。状態番号1の状態から状態番号2、3の状態への遷移確率が真値0.5に近い値になっており、他の状態への遷移確率が真値0に近い値になっており、学習が成功したことを示している。

0082

図14は、一実験例における学習時の状態数の変化である。図14縦軸が状態数で横軸が計算の繰り返し回数である。図14に示すように、400回の計算の繰り返しで、状態数が5に収束している。

0083

なお、本実施例では一台の情報処理システム10が各処理を実行したが、これに限らず、複数の情報処理装置を備える情報処理システムが、各処理を、それらの複数の情報処理装置で分散して処理してもよい。

0084

また、本実施例の情報処理システムの各処理を実行するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、当該記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、プロセッサが実行することにより、本実施例の情報処理システムに係る上述した種々の処理を行ってもよい。

0085

以上、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。

0086

1:CPU(Central Processing Unit)
2:入力部
3:RAM
4:記憶部
10:情報処理システム
11:次数決定部
12:閾値決定部
13:確率決定部
14:状態列決定部
15:更新部
16:判定部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ