系列信号検索装置および系列信号検索方法
【課題】誤りを含む系列信号から複数候補を効率よく処理できる系列信号検索装置および系列信号検索方法を提供する。
【解決手段】音声データの音声認識結果の音節列と検索語の音節列から2次元配列を表し、前記2次元配列の要素として音節間の距離、すなわち類似度を用いることにより平面を構成し、前記平面上で直線を検出することにより、検索語による音声データの検索処理を実現する。距離を考慮した索引付けを用いることで高速な検出が可能となるとともに、音声認識の複数候補を考慮することで高精度な検出も可能になる。そして、距離を考慮した索引付けは、距離の近い、あるいは近似的に近い候補から探索を進めることができるため探索を打ち切る必要は無く、適切なしきい値が設定できる。さらに、しきい値で探索を打ち切らないので、ノイズが大きい場合でも、距離の近い、あるいは近似的に近い候補から順番に解を見つけることができるようになる。
【解決手段】音声データの音声認識結果の音節列と検索語の音節列から2次元配列を表し、前記2次元配列の要素として音節間の距離、すなわち類似度を用いることにより平面を構成し、前記平面上で直線を検出することにより、検索語による音声データの検索処理を実現する。距離を考慮した索引付けを用いることで高速な検出が可能となるとともに、音声認識の複数候補を考慮することで高精度な検出も可能になる。そして、距離を考慮した索引付けは、距離の近い、あるいは近似的に近い候補から探索を進めることができるため探索を打ち切る必要は無く、適切なしきい値が設定できる。さらに、しきい値で探索を打ち切らないので、ノイズが大きい場合でも、距離の近い、あるいは近似的に近い候補から順番に解を見つけることができるようになる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、検索装置および検索方法に関し、特に、音声データ中に使用された言葉の検索、またはOCR後の誤りを含むテキストデータからの検索などのように系列信号について検索するための検索装置および検索方法に関するものである。
【背景技術】
【0002】
音声・画像・ビデオの記録・編集機器の拡大、およびインターネットをはじめとする情報通信網の発展により、誰でも気軽にコンテンツを作成・公開することが可能となり、マルチメディアコンテンツの情報爆発が進行しつつある。これらのコンテンツには、ファイル名やタイトル以外にはメタデータが付与されていないことが多く、従来のテキストベースの検索技術だけでは、目的のコンテンツにたどり着くことは困難である。一方、話し言葉を含むコンテンツの場合には、大語彙連続音声認識技術を利用することで、言語情報を利用した検索が可能である。このような音声言語情報を対象とした検索技術は「音声ドキュメント検索(Spoken
Document Retrieval)」または、単に「音声検索」と呼ばれ、マルチメディアコンテンツの情報爆発時代に必要不可欠な技術である。
【0003】
音声ドキュメント検索のうち、入力した検索語(クエリ、パターンなどと呼ぶ)が音声データ中で現れる位置を特定する問題は、音声中の検索語検出(Spoken
Term Detection;STD)、音声中の既知語検索(Known Item Retrieval)、音声キーワード検索、あるいは単に音声検索、などと呼ばれ、音声情報処理の分野では活発に研究が行われている問題である。1997年には、米国NIST主催の評価型ワークショップTRECの音声ドキュメント検索トラック(SDR
Track)において、Known Item Retrievalの評価が行われた[非特許文献1]。また、2006年にNISTは再びSpoken
Term Detectionを研究課題として設定し、それ以降未知語の検出を重視したSTDの研究が盛んに行われるようになった[非特許文献2]。音声情報処理の代表的な国際会議であるICASSP(International Conference on Acoustic, Speech and Signal Processing)でも2009年に音声ドキュメント検索のスペシャルセッションが組まれている。また、日本においても情報処理学会音声言語情報処理研究会のワーキンググループにおいて、STDの評価用テストコレクションの整備が進行中である[非特許文献3]。
【0004】
STDに対する従来手法は、音声認識の認識誤りを、比較的研究が進んでいるテキストを対象とした検索手法の枠組みの中で扱う方法がほとんどである。前述TRECのSDR
Trackでは、音声認識結果の一位の候補に加えて二位以下の複数候補を利用することで性能改善できることが示されている。その後の手法は、認識結果の複数候補を効率よく表現する方法、たとえば代表的な方法として、Confusion
Network[非特許文献4]やTALE(Time−Anchored Lattice
Expansion)[非特許文献5]、に焦点が当てられ、検索については誤りの無いテキスト検索方法と同様の手法で索引付けする方法を用いるものがほとんどであった。これらの手法は、完全一致の索引を用いるため索引付けに漏れがあると全く検出できなくなるという問題点がある。特に、音声認識の認識語彙外語(未知語ともいう)の扱いが問題である。これに対し、音素や音節認識の結果を併用する手法も提案されているが、認識率の低下が問題となっている。また、誤認識の対処のため利用する認識候補数を大きく取ると、索引の数が大きくなり検索効率が悪化するという問題点もある。
【0005】
一方、手島らは、サフィックスアレイを用いた索引付け手法をSTDに適用した検索法を提案している〔非特許文献6]。STDに近似文字列照合を適用した方法と位置づけられるが、サフィックスアレイ(あるいは、サフィックスツリー)で認識の複数候補を扱うことは難しく、検索精度に問題がある。また、従来のいずれの方法もテキストベースの索引付け法をそのまま適用しているため、索引自体は一致/不一致の2値情報しか含んでいない。そのため、検索時や検索後にDP(Dynamic Programming)マッチングなどを用いて距離の計算を要するという問題点がある。
【0006】
一方、テキストデータを対象としてパターンと類似した部分を見つける問題は、「近似文字列照合(Approximate
String Matching)」と呼ばれる。近似文字列照合は、テキストがその場で与えられることを仮定してテキストを前処理することなしに照合を行うオンライン手法と、あらかじめテキストが与えられていることを仮定してテキストを前処理して索引付け(Indexing)を行うオフライン手法の2つに分類される。
【0007】
また、オフライン近似文字列照合の索引付け手法としては、以下の3種類に分類される[非特許文献7]。
【0008】
(1)サフィックスツリー(Suffix Tree)またはサフィックスアレイ(Suffix Array)に基づく手法
(2)n−gram索引を用いる手法
(3)距離空間上の索引を用いる手法[非特許文献8]
【0009】
これらの手法をSTDに用いる場合、上記(1)は音声認識の複数候補を扱えない、上記(2)は検出位置には検索語と一定割合以上の完全一致箇所が含まれている必要がある、といった問題点がある。また、上記従来法(1)(2)のいずれの手法も「ある一定のエラーの範囲内の全候補を探す」という問題設定に対する手法となっており、「最も距離の近い上位N個の候補を求める」といった問題に適応するには、しきい値を決め直して再検索するなど、追加コストがかかることも問題である。一方、上記(3)の距離空間上の索引を用いる手法は、これまでSTDに適用されていない。
【先行技術文献】
【非特許文献】
【0010】
【非特許文献1】John S.Garofolo and Cedric G. P. Auzanne and Ellen M. Voorhees, “The TREC SpokenDocument Retrieval Track: A Success Story”, In Proceedings of TREC-9, page107-129, 1999.
【非特許文献2】NIST, “TheSpoken Term Detection Evaluation”:http://www.itl.nist.gov/iad/mig/tests/std/2006/index.html
【非特許文献3】伊藤慶明, 西崎博光, 胡新輝, 南条浩輝, 秋葉友良, 相川清明, 河原達也, 中川聖一, 松井知子, 山下洋一,“音声中の検索語検出のためのテストコレクション構築−中間報告−”, 情報処理学会研究報告,Vol.2009-SLP-78 No.4, 2009.
【非特許文献4】L.Mangu, E.Brill andA.Stolcke: “Finding Consensus in Speech Recognition: Word Error Minimizationand Other Applications of Confusion Network” Computer Speech andLanguage,Vol.14, No.4, pp.373-400, 2000.
【非特許文献5】P. Yu, Y. Shi and F. Seide,“Approximate Word-Lattice Indexing with Text Indexers: Time-Anchored LatticeExpansion”, In Proceedings of International Conference on Acoustic, Speech andSignal Processing (ICASSP), pp.5248-5251, 2008.
【非特許文献6】手島 茂樹,桂田 浩一,新田 恒雄: “Suffix Array を用いた高速なキーワード音声検索システム”, 日本音響学会2009年秋季研究発表会講演論文集,1-R-26 (2009-9).
【非特許文献7】G. Navarro, et al., “Indexingmethods for approximate string matching”, IEEE Data Eng. Bull., 24(4):12-27,2001.
【非特許文献8】G. Navarro, et al., “A Metric Indexfor Approximate String Matching”, Theoretical Computer Science (TCS) 352(1-3):266-279, 2006.
【発明の概要】
【発明が解決しようとする課題】
【0011】
従来法は、曖昧性の無いテキストを対象とした索引付け手法をベースにしているため、音声認識結果のような、(1)複数の候補を扱う方法、(2)連続的な距離を扱う方法、に問題があり、そのため精度あるいは効率のいずれかを犠牲にすることに問題があった。前記(1)については、一致/不一致の二値の索引付けを適用するため、複数候補を全く扱えないか、複数候補を扱うと候補数が多くなり効率が悪化してしまう。また前記(2)について、音声などの曖昧な情報を扱う場合は、連続的な距離(尤度、信頼度、確率、など)の扱いが必要である。
【0012】
従来法は離散的な距離(n文字異なる、など)を扱うことを目指しており、索引自体には距離情報を利用していなかった。そのため、検索時や検索後にDPマッチングなどを用いて距離の計算を要するという問題点がある。また、従来法は探索にしきい値を必要とし、適切なしきい値の設定が難しいという問題がある。
【0013】
そこで、本発明は、複数候補を効率よく行うとともに、検索処理を簡素化することのできる検索装置および検索方法を提供することを目的とする。
【課題を解決するための手段】
【0014】
上記目的を達成するために、本発明者らは、鋭意検討の結果本発明に至った。
【0015】
すなわち、系列信号検索装置にかかる本発明は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出手段と、前記信号特徴抽出手段により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出手段と、前記類似距離算出手段により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成手段と、前記系列信号情報、前記参照信号特徴、前記信号特徴の特徴量の類似度を示す距離、および、前記特徴ベクトルを記憶する記憶装置と、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出手段と、前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成手段と、前記信号特徴列生成手段により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定手段と、前記検索結果を出力する出力手段とを備えたことを特徴とする系列信号検索装置を要旨とすることができる。
【0016】
上記発明の判定手段については、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成手段により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定手段とすることができる。
【0017】
また、上記発明において、前記系列信号情報を音声データとし、前記信号特徴および前記参考信号特徴が、音素、音節または音素もしくは音節のn−gramによって特徴付けられる信号特徴とすることができる。
【0018】
他方、系列信号検索方法にかかる本発明は、記憶装置に蓄積された情報に接続される計算機を介して検索する方法において、前処理過程および実行時処理過程とで構成された系列信号検索方法であって、前処理過程は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出過程と、前記信号特徴抽出過程により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出過程と、前記類似距離算出過程により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成過程とで構成され、実行時処理過程は、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出過程と、前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成過程と、前記信号特徴列生成過程により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定過程と、前記検索結果を出力する出力過程とで構成されたことを特徴とする系列信号検索方法を要旨としている。
【0019】
上記発明の判定過程としては、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成過程により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定過程とすることができる。
【0020】
また、上記発明において、前記信号特徴抽出過程は、音声データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する信号特徴抽出過程であり、前記検索信号特徴抽出過程は、文字データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する検索信号特徴抽出過程である構成とすることができる。
【0021】
なお、上記構成の検索方法は従来技術のうち、距離空間上の索引を用いる手法に分類されると考えられるが、従来技術における手法が文字列全体の距離空間上で直接索引付けするのに対し、本発明は距離空間を線形に再構成可能な部分距離空間に分割し、各部分空間で距離空間索引付けを行うものである。
【0022】
また、本発明の検索方法は、大規模な音声データ中から、入力した検索語と類似した箇所を、類似度の高い順に高速に検索する、STD手法の一つである。音声データからのキーワード検索のほかに、検索語を分割した単位、たとえば音声検索の場合は音素、音節、音節や音素のn−gramなど、と検索対象データの各位置の間に距離、特に連続値による距離または類似度が定義されている系列からの類似箇所検索一般に適用可能である。たとえば、近似文字列照合、OCR後の誤りを含むテキストからの検索などに適用可能である。特に、検索対象データについて、各位置に複数の候補がある場合にも適用可能であることから、誤りを含む系列からの類似列検索に適している。
【発明の効果】
【0023】
本発明によれば、距離を考慮した索引付けを用いることで高速な検出が可能となるとともに、音声認識の複数候補を考慮することで高精度な検出も可能になる。
【0024】
そして、距離を考慮した索引付けは、距離の近い、あるいは近似的に近い候補から探索を進めるという良い性質を持っている。また、従来技術は、索引は距離を考慮していないので可能性のある候補を等価に扱う必要があり、そのため探索を打ち切るしきい値を必要とし、適切なしきい値の設定が難しいという問題があったが、本発明の検索方法によれば、しきい値を設定する必要は無く、この問題を回避できる。
【0025】
このように、本発明の検索装置は、その性質により、新たなSTDシステムの運用方法が可能になる。また、本発明の検索方法によれば、しきい値で探索を打ち切ることを行わないので、どんなにノイズが大きい場合でも、距離の近い、あるいは近似的に近い候補から順番に解を見つけることができる、という良い性質を持つ。この性質により、これまでにないシステムの運用が可能である。例えば、最初のN個の解が見つかるまで検出を行うといった運用や、検出に時間がかかる場合は、距離の類似した対立候補が多くそもそも検索語が存在しないなど良い結果が得られないことが示唆されるので、一定時間だけで検索を打ち切るなど、システム構築の際にこの性質を活かした運用を行うことが可能である。
【図面の簡単な説明】
【0026】
【図1】xy平面上の直線検出による検索語の検出の模式図である。
【図2】音節距離配列の模式図である。
【図3】距離順にソートされた位置iのベクトル(スタック)を示す模式図である。
【図4】前処理(索引付け)アルゴリズムのフローチャートである。
【図5】検索アルゴリズムのフローチャートである。
【図6】検索アルゴリズムのフローチャートである。
【図7】近傍生成の例を示す模式図である。
【図8】Confusion Networkを考慮した音節間距離の模式図である。
【図9】挿入、削除、誤りを考慮した音節間距離を表す模式図である。
【図10】本発明の実施形態における前処理のための索引データ作成装置の模式図である。
【図11】本発明の実施形態における検索処理装置の模式図である。
【図12】本発明の実施形態における連続DPのSTD実験結果を示すグラフである。
【図13】本発明の実施形態におけるSTD実験結果を示すグラフである。
【発明を実施するための形態】
【0027】
以下、本発明の実施の形態を説明する。本発明の基本的な原理は、STD問題の性質を利用して効率よい索引付け(前処理)手段と直線検出手段を利用した検索方法(実行時処理)に特長がある。
【0028】
系列信号情報としては、音声データ、テキストデータ、音楽データおよび画像データなどが挙げられるが、本実施形態では音声データを例示して説明する。また、音声データについて分割する単位には、音素、音節または音素もしくは音節のn−gramなどを挙げることができるが、説明の容易さから音節を単位として音声データを分割し、それぞれの音節について、個々の音節を信号特徴として認識する場合について説明する。なお、各音節における信号特徴およびその類似度は、発音された音声波形と参照音節波形との間の物理的な差異を尺度とするほか、発声方法の相違点に着目した解析方法によって特徴付けられる基準により尺度を決定する場合もあり得る。より具体的には、音節をHidden Markov Model(HMM)でモデル化して、そのモデル間の距離を尺度とすることができる。そのため、以下の説明中に示した「音節」には、上述のように特徴付けられた「音節ごとの信号特徴」を含む場合があるものとし、また、参照信号特徴とは、正確な発音をした場合の音節ごとの信号特徴を意味する。
【0029】
音声データの音声認識結果の音節列をx軸、検索語の音節列をy軸にとった平面を考える(図1)。STDは、この平面から直線を検出する問題ととらえることができる。xy平面は、要素として音節間の距離(類似度)が代入された音声データ長n×検索語長mの2次元配列D[i][j]
(0≦i<n,0≦j<m)で表現することができる。
【0030】
このとき、例えば(最も一般的なマッチングのケースである) 傾き1の直線 y=x+c の検出には、数1を各i(0≦i<n)で計算し、T[i]の小さい箇所を類似箇所として検出する、と言った問題に定式化できる。
【0031】
【数1】
【0032】
これ以降、j(0≦j<m−1)に関する<式>の総和を Σ_j <式> と表す。
【0033】
画像の直線検出の場合は、2次元配列D[i][j]がその場で得られるので、すべてオンラインで計算する必要がある。
【0034】
一方、STDの場合は、音声データは検索前に既知であると仮定できるので、検索語のある分割単位(音素、音節、音節や音素のn−gram、など。以下、音節と呼ぶ。)aごとに音声データの各位置での距離の配列D(a)[i] (0≦i<n)をオフラインで計算しておくことができる(図2)。検索時には検索語の音節系列a[0],a[1],・・,a[m−1]によって距離の配列D(a[0])[i],D(a[1])[i],・・,D(a[m−1])[i]をy軸方向に順番に並べるだけで2次元配列D[i][j]を構成できる(すなわち、D[i][j]=D(a[j])[i]となる)。
【0035】
さらに、距離の配列D(a)[i]は、オフラインで距離の昇順にソートしておくことができる。つまり、類似距離の最小値から信号特徴を順次配列させるのである。音節aについて音声データ中の各位置iをD(a)[i]に従って距離の昇順にソートしたスタックをS(a)、そのスタックトップをS(a).topとする(図3)。
【0036】
以上で述べた、D(a)[i]およびS(a)を計算するアルゴリズムのフローチャートを(図4)に示す。以下、(図4)に従って手順を説明する。
【0037】
まず、音声データを音声認識する等の手段で、音節Confusion Network CN[i]を用意する(ステップA1)。音節集合Aを初期化し、全音節を代入する(ステップA2)。Aから音節aを一つ取り出し、位置iを0に初期化する(ステップA3)。aとCN[i]の距離を計算し、それを距離の配列D(a)[i]に代入し、iをインクリメントする(ステップA4)。位置iが文書長nに達したら次のステップA6に、そうでなければステップA4に戻る(ステップA5)。求めたD(a)[i]に従って、文書位置を昇順にソートし、ソートされた位置ベクトルS(a)を得る(ステップA6)。音節集合Aにまだ音節が残っていたらステップA3に戻る(ステップA7)。求めた位置ベクトルS(a)と距離ベクトルD(a)[i](両ベクトルを合わせて特徴ベクトルという)を出力する(ステップA8)。
【0038】
前処理で計算しておいたS(a)を検索の索引として用いると、見込みのある位置から順に検出をする効率的な検出方法が構成可能である。より具体的には、以下の手順に従い、高速な検索語検出が可能である。
【0039】
検索処理のフローチャートを(図5)に示す。以下、(図5)に従って手順を説明する。
【0040】
まず、検索語を入力し、その音節列a[0],a[1],・・,a[m−1]に従って、予め前処理で計算されているスタックの列S(a[0]),S(a[1]),・・,S(a[j]),・・,S(a[m−1])を用意する。また、R={},count[i]=0
(0≦i<n)に初期化する(ステップB1)。各スタック列のスタックトップの要素からなる集合U={S(a[0]).top,S(a[1]).top,・・,S(a[j]).top,S(a[m−1]).top}から、ある基準でjを選び、S(a[j]).topをスタックS(a[j])から取り出し(ポップし)、位置i=S(a[j]).top−jについて、投票した回数を数えるカウンタcount[i]に1を加える(投票する)(ステップB2)。ある値kについて、count[i]≧k
がまだ成り立っていないなら、ステップB2に戻る(ステップB3)。位置iを検索結果候補集合Rに加える(ステップB4)。
R中の各候補iについて、ある基準を満たしたものを、検索結果として出力する。出力した候補はRから取り除く(ステップB5)。終了条件が満たされていない場合はステップB2に戻る(ステップB6)。
【0041】
以上の手順において、基本的には各候補について距離の計算は全く行う必要はないことに注意されたい。また、以降で述べるように、ステップB5で用いる基準によっては各候補の距離
【0042】
【数2】
【0043】
を計算する必要があるが、あらかじめ求められている各音節の距離D(a[j])[i+j]を足し込んでいくだけで、高価な計算なしに求めることができる。
【0044】
ステップB2のjを選ぶ基準には、U中で最小の距離を持つ要素(argmin_j D(a[j])[S(a[j]).top])などが考えられる。ステップB6の終了条件には、「最初の検索結果が得られるまで」「最初のN個の検索結果が得られるまで」「検索結果の距離があるしきい値を越えるまで」「ある一定時間が経過するまで」などが考えられる。また、ステップB5は各繰り返しで必ず実行する必要は無く、例えば、ステップB4を一定回数実行したら1回実行する、といった実装も考えられる。
【0045】
ステップB3のkとステップB5の基準の選択は、精度と効率に関係する。ステップB3のkを小さくすると効率は良くなるが、精度は落ちる。そのためステップB5である基準により結果の評価を行い、安全なものを出力する。
【0046】
最も単純な実装方法は、k=m(検索語長)として、ステップB5には何も基準を課さず、すぐに検索結果を出力することが考えられる。また、効率を改善するには、ステップB5の基準を課さないまま、kを小さく取れば良い。例えば、ある実数α(0<α<1)についてk=αmとすると、検索語長に対して割合αだけ投票されたときに出力することとなる。
【0047】
これらの、ステップB5で基準を課さない単純な実装のフローチャートを(図6)に示す。
【0048】
図6において、ステップB1、ステップB2、ステップB3、ステップB6は、図5の対応するステップと同じである。図6のステップB45では、位置iを検索結果としてそのまま出力する。
【0049】
図5において、特にk=1とした場合、ステップB5に次の基準1を用いると、以降の繰り返しで出力する候補よりも悪い(距離の大きい)候補は出力しないことを保証する最適解アルゴリズムが得られる。
【0050】
(基準1) Σ_j D(a[j])[i+j]≦Σ_j S(a[j]).topが成り立つ。
【0051】
さらに、ステップB5で距離の小さい候補から順番に出力すれば、距離の昇順に解を出力するアルゴリズムとなる。また、集合Rは2分探索木やB木など順序を保持するデータ構造を用いれば、効率よく実装できる。
【0052】
基準1の妥当性は、以下の補題から明らかである。
【0053】
(補題1)まだ一度も投票が行われていない位置iの、数2で定義される最終的な距離T[i]は、スタックトップの距離の総和Σ_j S(a[j]).top
【0054】
【数3】
以上である。
【0055】
(証明)スタックは昇順にソートされているので、まだ投票の無い位置iについては任意の音節位置jについて、
【0056】
【数4】
が成り立つ。よって、
【0057】
【数5】
が成り立つ。(証明終)
【0058】
(補題2)Σ_j S(a[j]).topより距離の小さい候補位置iは、少なくとも1回ある音節位置jで投票が行われている。
【0059】
(証明)補題1の対偶により明らか。
【0060】
以上により、候補集合R以外にΣ_j
S(a[j]).topより距離の小さい候補は存在しないことが分かり、最適解が得られることが保証される。
【0061】
以上が基本的なアルゴリズムであるが、種々のバリエーションが考えられる。ここまでの説明では、最も単純な傾き1の直線y=x+cの場合を想定したが、これは距離尺度としては、文字列間のハミング距離に相当する。近似文字列照合の分野で使われる手法である近傍生成を適用することにより、直線の近傍となる直線や折れ線についても投票先T[i]を用意し同様な計算が可能であり、より一般的な文字列間の距離尺度である編集距離やその他の距離に適用できる(図7)。
【0062】
また、距離配列D(a)[i]には、音節aと音声データ中の位置iから求まる任意の距離を用いることが可能である。複数音声認識結果のコンパクトな表現方法であるConfusion
NetworkやTALE(Time−Anchored Lattice Expansion)などを用いた複数候補を考慮した距離(図8)、認識のもっともらしさを表現した距離、挿入誤りや削除誤りを考慮して直線からの逸脱を許容するために隣接する音節との距離も考慮した距離(図9)、などより複雑な距離を使用することができる。
【実施例】
【0063】
〔前処理〕次の手順で索引データ(前記実施の形態に示したスタックS(a))を作成する。(図10)
【0064】
1.ハードディスク、CD−ROMなどの記憶装置102に記録された音声データ201を用意する。音声データ102を、計算機101上にインストールした音声認識デコーダを用いて認識し、その認識結果である複数認識候補を表現した音節Confusion
Network202を記憶装置102上に作成する。音節Confusion Network202の代わりに、よりシンプルな認識結果の音節列をそのまま用いても良い。また、音節の代わりに、音素や、音節・音素のn−gramなど、検索語を分割して得られる任意の単位を用いても良い(以下では、これらをまとめて音節と呼ぶ。)
【0065】
2.音節aについて、音節Confusion Network202の各位値iの複数音節候補それぞれとの距離を計算機101で計算し、音節間距離の最小値を求める。すべての位置について距離計算した結果を、音節距離配列203として記憶装置102上に作成する。以上の操作をすべての音節で繰り返し、音節毎の音節距離配列203を作成する。
【0066】
3.各音節aについて、音節距離配列203に従って位置iを計算機を用いて昇順にソートし、その出力である音節位置のベクトル204を記憶装置上に作成する。
【0067】
〔検索処理〕前処理で作成した音節位置ベクトル(スタック)を用いて検索処理を行う。(図11)
【0068】
1.音声データ401と〔前処理〕で作成した音節毎の音節位置ベクトル403を、ハードディスクなどの記憶装置302に用意する。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、音節毎の音節距離配列402も記憶装置302に用意する。音声認識結果のテキストを検索結果とする場合には、音声データ401の代わりに音声認識結果のテキストを記憶装置上に用意しても良い。
【0069】
2.システムユーザの与える検索語(音節列)をキーボードなどの入力装置303を使って計算機301へ入力する。入力された音節列に含まれる各音節すべてについて、対応する音節位置ベクトル403を記憶装置302から計算機301に読み込んで、計算機メモリ上にスタックを構成する。スタックは、検索語を構成する各音節ごとに1つ、検索語の音節数だけ用意する。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、対応する音節距離配列402も計算機301のメモリ上に読み込む。
【0070】
このとき、入力装置303には、キーボードの他、音声認識や手書き文字認識など、音節列を入力可能な任意の入力装置が利用できる。また、音節距離配列402はメモリに読み込む代わりに、記憶装置302にそのまま配置し、必要なときにランダムアクセスで参照することも可能である。音節位置ベクトル403も、記憶装置から一度にメモリ上に読み込む必要はなく、ベクトルを先頭からある長さまでのブロックに分割し、必要に応じて1ブロックずつ読み込むことも可能である。また音節ベクトルのうち距離の大きなものが記録されている接尾部分は、使用される可能性が低いので、記憶装置302の記憶容量の節約のため、削除してしまうことも可能である。
【0071】
3.計算機301のメモリ上の音節毎に用意されたスタックを参照・操作しながら、前記実施の形態で示した方法により検索語出現位置を求める。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、計算機メモリ上(または、記憶装置上)の音節距離配列402も参照して処理を行う。
【0072】
4.検出された検索語出現位置にしたがって、記憶装置302上の音声データ401から検索語出現位置付近の音声を取り出し、検索結果とする。音声認識結果のテキストを用いる場合は、検索語出現位置のテキストを検索結果とする。検索結果として出力する範囲は、検索語そのものや、検索語を含むより広い範囲の文や文書など、用途に応じて任意に選択することができる。検索結果は、音声再生装置やディスプレイ装置などの出力装置304を用いてユーザにそのまま提示してもよいし、機械翻訳、音声合成器、Webサーバ、などの各種サービスを提供する任意の装置への入力として利用することもできる。
【0073】
以上の〔前処理〕〔検索処理〕で説明した装置を構成する要素である、記憶装置302、入力装置303、出力装置304、および計算機301は、直接接続することもできるし、ネットワーク上に分散して配置し、通信により相互接続して装置を構成することもできる。
【0074】
また、記憶装置302上のデータである、音声データ401、音節距離配列402、音節位置ベクトル403は、それぞれ別の記憶装置に配置することも出来る。例えば、記憶装置302上のデータのうち音声データ401をネットワーク越しのサーバ上の記憶装置に配置し、音節位置ベクトルだけ計算機301に直結した記憶装置に配置することもできる。
【0075】
また、入出力装置303をWeb上のクライアントで、その他をWebサーバ上に構築することもできる。
【0076】
実施例に示した装置の実装と評価実験を、以下の手順で行った。
【0077】
日本語の学会講演と模擬講演を記録したコーパスである「日本語話し言葉コーパス(CSJ)」中の177講演(約44時間)の音声データを対象としたSTDシステムを構築した。前記CSJを検索対象とした音声ドキュメント検索用テストコレクションに含まれる前記CSJの1bestの音声認識結果を音素列に展開し、音素を分割単位として索引付けを行った。
【0078】
音素aと検索対象位置iの間の距離尺度としては、音素弁別特徴間のハミング距離[非特許文献6]を用いた。
【0079】
検索語として、前記CSJを対象とした検索語検出のためのテストコレクション[非特許文献3]の検索語を用いた。
【0080】
上記実施例と同条件の距離しきい値による連続DPマッチングと比較を行った。実験結果を(図12)と(図13)に示す。この結果から、検索性能を落とすこと無く、検索効率が大幅に改善されていることがわかる。
【符号の説明】
【0081】
101…計算機
102…記憶装置
201…音声データ
202…Confusion Network
203…音節距離配列
204…音節位置ベクトル
301…計算機
302…記憶装置
303…入力装置
304…出力装置
401…音声データ
402…音節距離配列
403…音節位置ベクトル
【技術分野】
【0001】
本発明は、検索装置および検索方法に関し、特に、音声データ中に使用された言葉の検索、またはOCR後の誤りを含むテキストデータからの検索などのように系列信号について検索するための検索装置および検索方法に関するものである。
【背景技術】
【0002】
音声・画像・ビデオの記録・編集機器の拡大、およびインターネットをはじめとする情報通信網の発展により、誰でも気軽にコンテンツを作成・公開することが可能となり、マルチメディアコンテンツの情報爆発が進行しつつある。これらのコンテンツには、ファイル名やタイトル以外にはメタデータが付与されていないことが多く、従来のテキストベースの検索技術だけでは、目的のコンテンツにたどり着くことは困難である。一方、話し言葉を含むコンテンツの場合には、大語彙連続音声認識技術を利用することで、言語情報を利用した検索が可能である。このような音声言語情報を対象とした検索技術は「音声ドキュメント検索(Spoken
Document Retrieval)」または、単に「音声検索」と呼ばれ、マルチメディアコンテンツの情報爆発時代に必要不可欠な技術である。
【0003】
音声ドキュメント検索のうち、入力した検索語(クエリ、パターンなどと呼ぶ)が音声データ中で現れる位置を特定する問題は、音声中の検索語検出(Spoken
Term Detection;STD)、音声中の既知語検索(Known Item Retrieval)、音声キーワード検索、あるいは単に音声検索、などと呼ばれ、音声情報処理の分野では活発に研究が行われている問題である。1997年には、米国NIST主催の評価型ワークショップTRECの音声ドキュメント検索トラック(SDR
Track)において、Known Item Retrievalの評価が行われた[非特許文献1]。また、2006年にNISTは再びSpoken
Term Detectionを研究課題として設定し、それ以降未知語の検出を重視したSTDの研究が盛んに行われるようになった[非特許文献2]。音声情報処理の代表的な国際会議であるICASSP(International Conference on Acoustic, Speech and Signal Processing)でも2009年に音声ドキュメント検索のスペシャルセッションが組まれている。また、日本においても情報処理学会音声言語情報処理研究会のワーキンググループにおいて、STDの評価用テストコレクションの整備が進行中である[非特許文献3]。
【0004】
STDに対する従来手法は、音声認識の認識誤りを、比較的研究が進んでいるテキストを対象とした検索手法の枠組みの中で扱う方法がほとんどである。前述TRECのSDR
Trackでは、音声認識結果の一位の候補に加えて二位以下の複数候補を利用することで性能改善できることが示されている。その後の手法は、認識結果の複数候補を効率よく表現する方法、たとえば代表的な方法として、Confusion
Network[非特許文献4]やTALE(Time−Anchored Lattice
Expansion)[非特許文献5]、に焦点が当てられ、検索については誤りの無いテキスト検索方法と同様の手法で索引付けする方法を用いるものがほとんどであった。これらの手法は、完全一致の索引を用いるため索引付けに漏れがあると全く検出できなくなるという問題点がある。特に、音声認識の認識語彙外語(未知語ともいう)の扱いが問題である。これに対し、音素や音節認識の結果を併用する手法も提案されているが、認識率の低下が問題となっている。また、誤認識の対処のため利用する認識候補数を大きく取ると、索引の数が大きくなり検索効率が悪化するという問題点もある。
【0005】
一方、手島らは、サフィックスアレイを用いた索引付け手法をSTDに適用した検索法を提案している〔非特許文献6]。STDに近似文字列照合を適用した方法と位置づけられるが、サフィックスアレイ(あるいは、サフィックスツリー)で認識の複数候補を扱うことは難しく、検索精度に問題がある。また、従来のいずれの方法もテキストベースの索引付け法をそのまま適用しているため、索引自体は一致/不一致の2値情報しか含んでいない。そのため、検索時や検索後にDP(Dynamic Programming)マッチングなどを用いて距離の計算を要するという問題点がある。
【0006】
一方、テキストデータを対象としてパターンと類似した部分を見つける問題は、「近似文字列照合(Approximate
String Matching)」と呼ばれる。近似文字列照合は、テキストがその場で与えられることを仮定してテキストを前処理することなしに照合を行うオンライン手法と、あらかじめテキストが与えられていることを仮定してテキストを前処理して索引付け(Indexing)を行うオフライン手法の2つに分類される。
【0007】
また、オフライン近似文字列照合の索引付け手法としては、以下の3種類に分類される[非特許文献7]。
【0008】
(1)サフィックスツリー(Suffix Tree)またはサフィックスアレイ(Suffix Array)に基づく手法
(2)n−gram索引を用いる手法
(3)距離空間上の索引を用いる手法[非特許文献8]
【0009】
これらの手法をSTDに用いる場合、上記(1)は音声認識の複数候補を扱えない、上記(2)は検出位置には検索語と一定割合以上の完全一致箇所が含まれている必要がある、といった問題点がある。また、上記従来法(1)(2)のいずれの手法も「ある一定のエラーの範囲内の全候補を探す」という問題設定に対する手法となっており、「最も距離の近い上位N個の候補を求める」といった問題に適応するには、しきい値を決め直して再検索するなど、追加コストがかかることも問題である。一方、上記(3)の距離空間上の索引を用いる手法は、これまでSTDに適用されていない。
【先行技術文献】
【非特許文献】
【0010】
【非特許文献1】John S.Garofolo and Cedric G. P. Auzanne and Ellen M. Voorhees, “The TREC SpokenDocument Retrieval Track: A Success Story”, In Proceedings of TREC-9, page107-129, 1999.
【非特許文献2】NIST, “TheSpoken Term Detection Evaluation”:http://www.itl.nist.gov/iad/mig/tests/std/2006/index.html
【非特許文献3】伊藤慶明, 西崎博光, 胡新輝, 南条浩輝, 秋葉友良, 相川清明, 河原達也, 中川聖一, 松井知子, 山下洋一,“音声中の検索語検出のためのテストコレクション構築−中間報告−”, 情報処理学会研究報告,Vol.2009-SLP-78 No.4, 2009.
【非特許文献4】L.Mangu, E.Brill andA.Stolcke: “Finding Consensus in Speech Recognition: Word Error Minimizationand Other Applications of Confusion Network” Computer Speech andLanguage,Vol.14, No.4, pp.373-400, 2000.
【非特許文献5】P. Yu, Y. Shi and F. Seide,“Approximate Word-Lattice Indexing with Text Indexers: Time-Anchored LatticeExpansion”, In Proceedings of International Conference on Acoustic, Speech andSignal Processing (ICASSP), pp.5248-5251, 2008.
【非特許文献6】手島 茂樹,桂田 浩一,新田 恒雄: “Suffix Array を用いた高速なキーワード音声検索システム”, 日本音響学会2009年秋季研究発表会講演論文集,1-R-26 (2009-9).
【非特許文献7】G. Navarro, et al., “Indexingmethods for approximate string matching”, IEEE Data Eng. Bull., 24(4):12-27,2001.
【非特許文献8】G. Navarro, et al., “A Metric Indexfor Approximate String Matching”, Theoretical Computer Science (TCS) 352(1-3):266-279, 2006.
【発明の概要】
【発明が解決しようとする課題】
【0011】
従来法は、曖昧性の無いテキストを対象とした索引付け手法をベースにしているため、音声認識結果のような、(1)複数の候補を扱う方法、(2)連続的な距離を扱う方法、に問題があり、そのため精度あるいは効率のいずれかを犠牲にすることに問題があった。前記(1)については、一致/不一致の二値の索引付けを適用するため、複数候補を全く扱えないか、複数候補を扱うと候補数が多くなり効率が悪化してしまう。また前記(2)について、音声などの曖昧な情報を扱う場合は、連続的な距離(尤度、信頼度、確率、など)の扱いが必要である。
【0012】
従来法は離散的な距離(n文字異なる、など)を扱うことを目指しており、索引自体には距離情報を利用していなかった。そのため、検索時や検索後にDPマッチングなどを用いて距離の計算を要するという問題点がある。また、従来法は探索にしきい値を必要とし、適切なしきい値の設定が難しいという問題がある。
【0013】
そこで、本発明は、複数候補を効率よく行うとともに、検索処理を簡素化することのできる検索装置および検索方法を提供することを目的とする。
【課題を解決するための手段】
【0014】
上記目的を達成するために、本発明者らは、鋭意検討の結果本発明に至った。
【0015】
すなわち、系列信号検索装置にかかる本発明は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出手段と、前記信号特徴抽出手段により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出手段と、前記類似距離算出手段により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成手段と、前記系列信号情報、前記参照信号特徴、前記信号特徴の特徴量の類似度を示す距離、および、前記特徴ベクトルを記憶する記憶装置と、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出手段と、前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成手段と、前記信号特徴列生成手段により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定手段と、前記検索結果を出力する出力手段とを備えたことを特徴とする系列信号検索装置を要旨とすることができる。
【0016】
上記発明の判定手段については、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成手段により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定手段とすることができる。
【0017】
また、上記発明において、前記系列信号情報を音声データとし、前記信号特徴および前記参考信号特徴が、音素、音節または音素もしくは音節のn−gramによって特徴付けられる信号特徴とすることができる。
【0018】
他方、系列信号検索方法にかかる本発明は、記憶装置に蓄積された情報に接続される計算機を介して検索する方法において、前処理過程および実行時処理過程とで構成された系列信号検索方法であって、前処理過程は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出過程と、前記信号特徴抽出過程により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出過程と、前記類似距離算出過程により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成過程とで構成され、実行時処理過程は、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出過程と、前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成過程と、前記信号特徴列生成過程により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定過程と、前記検索結果を出力する出力過程とで構成されたことを特徴とする系列信号検索方法を要旨としている。
【0019】
上記発明の判定過程としては、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成過程により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定過程とすることができる。
【0020】
また、上記発明において、前記信号特徴抽出過程は、音声データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する信号特徴抽出過程であり、前記検索信号特徴抽出過程は、文字データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する検索信号特徴抽出過程である構成とすることができる。
【0021】
なお、上記構成の検索方法は従来技術のうち、距離空間上の索引を用いる手法に分類されると考えられるが、従来技術における手法が文字列全体の距離空間上で直接索引付けするのに対し、本発明は距離空間を線形に再構成可能な部分距離空間に分割し、各部分空間で距離空間索引付けを行うものである。
【0022】
また、本発明の検索方法は、大規模な音声データ中から、入力した検索語と類似した箇所を、類似度の高い順に高速に検索する、STD手法の一つである。音声データからのキーワード検索のほかに、検索語を分割した単位、たとえば音声検索の場合は音素、音節、音節や音素のn−gramなど、と検索対象データの各位置の間に距離、特に連続値による距離または類似度が定義されている系列からの類似箇所検索一般に適用可能である。たとえば、近似文字列照合、OCR後の誤りを含むテキストからの検索などに適用可能である。特に、検索対象データについて、各位置に複数の候補がある場合にも適用可能であることから、誤りを含む系列からの類似列検索に適している。
【発明の効果】
【0023】
本発明によれば、距離を考慮した索引付けを用いることで高速な検出が可能となるとともに、音声認識の複数候補を考慮することで高精度な検出も可能になる。
【0024】
そして、距離を考慮した索引付けは、距離の近い、あるいは近似的に近い候補から探索を進めるという良い性質を持っている。また、従来技術は、索引は距離を考慮していないので可能性のある候補を等価に扱う必要があり、そのため探索を打ち切るしきい値を必要とし、適切なしきい値の設定が難しいという問題があったが、本発明の検索方法によれば、しきい値を設定する必要は無く、この問題を回避できる。
【0025】
このように、本発明の検索装置は、その性質により、新たなSTDシステムの運用方法が可能になる。また、本発明の検索方法によれば、しきい値で探索を打ち切ることを行わないので、どんなにノイズが大きい場合でも、距離の近い、あるいは近似的に近い候補から順番に解を見つけることができる、という良い性質を持つ。この性質により、これまでにないシステムの運用が可能である。例えば、最初のN個の解が見つかるまで検出を行うといった運用や、検出に時間がかかる場合は、距離の類似した対立候補が多くそもそも検索語が存在しないなど良い結果が得られないことが示唆されるので、一定時間だけで検索を打ち切るなど、システム構築の際にこの性質を活かした運用を行うことが可能である。
【図面の簡単な説明】
【0026】
【図1】xy平面上の直線検出による検索語の検出の模式図である。
【図2】音節距離配列の模式図である。
【図3】距離順にソートされた位置iのベクトル(スタック)を示す模式図である。
【図4】前処理(索引付け)アルゴリズムのフローチャートである。
【図5】検索アルゴリズムのフローチャートである。
【図6】検索アルゴリズムのフローチャートである。
【図7】近傍生成の例を示す模式図である。
【図8】Confusion Networkを考慮した音節間距離の模式図である。
【図9】挿入、削除、誤りを考慮した音節間距離を表す模式図である。
【図10】本発明の実施形態における前処理のための索引データ作成装置の模式図である。
【図11】本発明の実施形態における検索処理装置の模式図である。
【図12】本発明の実施形態における連続DPのSTD実験結果を示すグラフである。
【図13】本発明の実施形態におけるSTD実験結果を示すグラフである。
【発明を実施するための形態】
【0027】
以下、本発明の実施の形態を説明する。本発明の基本的な原理は、STD問題の性質を利用して効率よい索引付け(前処理)手段と直線検出手段を利用した検索方法(実行時処理)に特長がある。
【0028】
系列信号情報としては、音声データ、テキストデータ、音楽データおよび画像データなどが挙げられるが、本実施形態では音声データを例示して説明する。また、音声データについて分割する単位には、音素、音節または音素もしくは音節のn−gramなどを挙げることができるが、説明の容易さから音節を単位として音声データを分割し、それぞれの音節について、個々の音節を信号特徴として認識する場合について説明する。なお、各音節における信号特徴およびその類似度は、発音された音声波形と参照音節波形との間の物理的な差異を尺度とするほか、発声方法の相違点に着目した解析方法によって特徴付けられる基準により尺度を決定する場合もあり得る。より具体的には、音節をHidden Markov Model(HMM)でモデル化して、そのモデル間の距離を尺度とすることができる。そのため、以下の説明中に示した「音節」には、上述のように特徴付けられた「音節ごとの信号特徴」を含む場合があるものとし、また、参照信号特徴とは、正確な発音をした場合の音節ごとの信号特徴を意味する。
【0029】
音声データの音声認識結果の音節列をx軸、検索語の音節列をy軸にとった平面を考える(図1)。STDは、この平面から直線を検出する問題ととらえることができる。xy平面は、要素として音節間の距離(類似度)が代入された音声データ長n×検索語長mの2次元配列D[i][j]
(0≦i<n,0≦j<m)で表現することができる。
【0030】
このとき、例えば(最も一般的なマッチングのケースである) 傾き1の直線 y=x+c の検出には、数1を各i(0≦i<n)で計算し、T[i]の小さい箇所を類似箇所として検出する、と言った問題に定式化できる。
【0031】
【数1】
【0032】
これ以降、j(0≦j<m−1)に関する<式>の総和を Σ_j <式> と表す。
【0033】
画像の直線検出の場合は、2次元配列D[i][j]がその場で得られるので、すべてオンラインで計算する必要がある。
【0034】
一方、STDの場合は、音声データは検索前に既知であると仮定できるので、検索語のある分割単位(音素、音節、音節や音素のn−gram、など。以下、音節と呼ぶ。)aごとに音声データの各位置での距離の配列D(a)[i] (0≦i<n)をオフラインで計算しておくことができる(図2)。検索時には検索語の音節系列a[0],a[1],・・,a[m−1]によって距離の配列D(a[0])[i],D(a[1])[i],・・,D(a[m−1])[i]をy軸方向に順番に並べるだけで2次元配列D[i][j]を構成できる(すなわち、D[i][j]=D(a[j])[i]となる)。
【0035】
さらに、距離の配列D(a)[i]は、オフラインで距離の昇順にソートしておくことができる。つまり、類似距離の最小値から信号特徴を順次配列させるのである。音節aについて音声データ中の各位置iをD(a)[i]に従って距離の昇順にソートしたスタックをS(a)、そのスタックトップをS(a).topとする(図3)。
【0036】
以上で述べた、D(a)[i]およびS(a)を計算するアルゴリズムのフローチャートを(図4)に示す。以下、(図4)に従って手順を説明する。
【0037】
まず、音声データを音声認識する等の手段で、音節Confusion Network CN[i]を用意する(ステップA1)。音節集合Aを初期化し、全音節を代入する(ステップA2)。Aから音節aを一つ取り出し、位置iを0に初期化する(ステップA3)。aとCN[i]の距離を計算し、それを距離の配列D(a)[i]に代入し、iをインクリメントする(ステップA4)。位置iが文書長nに達したら次のステップA6に、そうでなければステップA4に戻る(ステップA5)。求めたD(a)[i]に従って、文書位置を昇順にソートし、ソートされた位置ベクトルS(a)を得る(ステップA6)。音節集合Aにまだ音節が残っていたらステップA3に戻る(ステップA7)。求めた位置ベクトルS(a)と距離ベクトルD(a)[i](両ベクトルを合わせて特徴ベクトルという)を出力する(ステップA8)。
【0038】
前処理で計算しておいたS(a)を検索の索引として用いると、見込みのある位置から順に検出をする効率的な検出方法が構成可能である。より具体的には、以下の手順に従い、高速な検索語検出が可能である。
【0039】
検索処理のフローチャートを(図5)に示す。以下、(図5)に従って手順を説明する。
【0040】
まず、検索語を入力し、その音節列a[0],a[1],・・,a[m−1]に従って、予め前処理で計算されているスタックの列S(a[0]),S(a[1]),・・,S(a[j]),・・,S(a[m−1])を用意する。また、R={},count[i]=0
(0≦i<n)に初期化する(ステップB1)。各スタック列のスタックトップの要素からなる集合U={S(a[0]).top,S(a[1]).top,・・,S(a[j]).top,S(a[m−1]).top}から、ある基準でjを選び、S(a[j]).topをスタックS(a[j])から取り出し(ポップし)、位置i=S(a[j]).top−jについて、投票した回数を数えるカウンタcount[i]に1を加える(投票する)(ステップB2)。ある値kについて、count[i]≧k
がまだ成り立っていないなら、ステップB2に戻る(ステップB3)。位置iを検索結果候補集合Rに加える(ステップB4)。
R中の各候補iについて、ある基準を満たしたものを、検索結果として出力する。出力した候補はRから取り除く(ステップB5)。終了条件が満たされていない場合はステップB2に戻る(ステップB6)。
【0041】
以上の手順において、基本的には各候補について距離の計算は全く行う必要はないことに注意されたい。また、以降で述べるように、ステップB5で用いる基準によっては各候補の距離
【0042】
【数2】
【0043】
を計算する必要があるが、あらかじめ求められている各音節の距離D(a[j])[i+j]を足し込んでいくだけで、高価な計算なしに求めることができる。
【0044】
ステップB2のjを選ぶ基準には、U中で最小の距離を持つ要素(argmin_j D(a[j])[S(a[j]).top])などが考えられる。ステップB6の終了条件には、「最初の検索結果が得られるまで」「最初のN個の検索結果が得られるまで」「検索結果の距離があるしきい値を越えるまで」「ある一定時間が経過するまで」などが考えられる。また、ステップB5は各繰り返しで必ず実行する必要は無く、例えば、ステップB4を一定回数実行したら1回実行する、といった実装も考えられる。
【0045】
ステップB3のkとステップB5の基準の選択は、精度と効率に関係する。ステップB3のkを小さくすると効率は良くなるが、精度は落ちる。そのためステップB5である基準により結果の評価を行い、安全なものを出力する。
【0046】
最も単純な実装方法は、k=m(検索語長)として、ステップB5には何も基準を課さず、すぐに検索結果を出力することが考えられる。また、効率を改善するには、ステップB5の基準を課さないまま、kを小さく取れば良い。例えば、ある実数α(0<α<1)についてk=αmとすると、検索語長に対して割合αだけ投票されたときに出力することとなる。
【0047】
これらの、ステップB5で基準を課さない単純な実装のフローチャートを(図6)に示す。
【0048】
図6において、ステップB1、ステップB2、ステップB3、ステップB6は、図5の対応するステップと同じである。図6のステップB45では、位置iを検索結果としてそのまま出力する。
【0049】
図5において、特にk=1とした場合、ステップB5に次の基準1を用いると、以降の繰り返しで出力する候補よりも悪い(距離の大きい)候補は出力しないことを保証する最適解アルゴリズムが得られる。
【0050】
(基準1) Σ_j D(a[j])[i+j]≦Σ_j S(a[j]).topが成り立つ。
【0051】
さらに、ステップB5で距離の小さい候補から順番に出力すれば、距離の昇順に解を出力するアルゴリズムとなる。また、集合Rは2分探索木やB木など順序を保持するデータ構造を用いれば、効率よく実装できる。
【0052】
基準1の妥当性は、以下の補題から明らかである。
【0053】
(補題1)まだ一度も投票が行われていない位置iの、数2で定義される最終的な距離T[i]は、スタックトップの距離の総和Σ_j S(a[j]).top
【0054】
【数3】
以上である。
【0055】
(証明)スタックは昇順にソートされているので、まだ投票の無い位置iについては任意の音節位置jについて、
【0056】
【数4】
が成り立つ。よって、
【0057】
【数5】
が成り立つ。(証明終)
【0058】
(補題2)Σ_j S(a[j]).topより距離の小さい候補位置iは、少なくとも1回ある音節位置jで投票が行われている。
【0059】
(証明)補題1の対偶により明らか。
【0060】
以上により、候補集合R以外にΣ_j
S(a[j]).topより距離の小さい候補は存在しないことが分かり、最適解が得られることが保証される。
【0061】
以上が基本的なアルゴリズムであるが、種々のバリエーションが考えられる。ここまでの説明では、最も単純な傾き1の直線y=x+cの場合を想定したが、これは距離尺度としては、文字列間のハミング距離に相当する。近似文字列照合の分野で使われる手法である近傍生成を適用することにより、直線の近傍となる直線や折れ線についても投票先T[i]を用意し同様な計算が可能であり、より一般的な文字列間の距離尺度である編集距離やその他の距離に適用できる(図7)。
【0062】
また、距離配列D(a)[i]には、音節aと音声データ中の位置iから求まる任意の距離を用いることが可能である。複数音声認識結果のコンパクトな表現方法であるConfusion
NetworkやTALE(Time−Anchored Lattice Expansion)などを用いた複数候補を考慮した距離(図8)、認識のもっともらしさを表現した距離、挿入誤りや削除誤りを考慮して直線からの逸脱を許容するために隣接する音節との距離も考慮した距離(図9)、などより複雑な距離を使用することができる。
【実施例】
【0063】
〔前処理〕次の手順で索引データ(前記実施の形態に示したスタックS(a))を作成する。(図10)
【0064】
1.ハードディスク、CD−ROMなどの記憶装置102に記録された音声データ201を用意する。音声データ102を、計算機101上にインストールした音声認識デコーダを用いて認識し、その認識結果である複数認識候補を表現した音節Confusion
Network202を記憶装置102上に作成する。音節Confusion Network202の代わりに、よりシンプルな認識結果の音節列をそのまま用いても良い。また、音節の代わりに、音素や、音節・音素のn−gramなど、検索語を分割して得られる任意の単位を用いても良い(以下では、これらをまとめて音節と呼ぶ。)
【0065】
2.音節aについて、音節Confusion Network202の各位値iの複数音節候補それぞれとの距離を計算機101で計算し、音節間距離の最小値を求める。すべての位置について距離計算した結果を、音節距離配列203として記憶装置102上に作成する。以上の操作をすべての音節で繰り返し、音節毎の音節距離配列203を作成する。
【0066】
3.各音節aについて、音節距離配列203に従って位置iを計算機を用いて昇順にソートし、その出力である音節位置のベクトル204を記憶装置上に作成する。
【0067】
〔検索処理〕前処理で作成した音節位置ベクトル(スタック)を用いて検索処理を行う。(図11)
【0068】
1.音声データ401と〔前処理〕で作成した音節毎の音節位置ベクトル403を、ハードディスクなどの記憶装置302に用意する。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、音節毎の音節距離配列402も記憶装置302に用意する。音声認識結果のテキストを検索結果とする場合には、音声データ401の代わりに音声認識結果のテキストを記憶装置上に用意しても良い。
【0069】
2.システムユーザの与える検索語(音節列)をキーボードなどの入力装置303を使って計算機301へ入力する。入力された音節列に含まれる各音節すべてについて、対応する音節位置ベクトル403を記憶装置302から計算機301に読み込んで、計算機メモリ上にスタックを構成する。スタックは、検索語を構成する各音節ごとに1つ、検索語の音節数だけ用意する。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、対応する音節距離配列402も計算機301のメモリ上に読み込む。
【0070】
このとき、入力装置303には、キーボードの他、音声認識や手書き文字認識など、音節列を入力可能な任意の入力装置が利用できる。また、音節距離配列402はメモリに読み込む代わりに、記憶装置302にそのまま配置し、必要なときにランダムアクセスで参照することも可能である。音節位置ベクトル403も、記憶装置から一度にメモリ上に読み込む必要はなく、ベクトルを先頭からある長さまでのブロックに分割し、必要に応じて1ブロックずつ読み込むことも可能である。また音節ベクトルのうち距離の大きなものが記録されている接尾部分は、使用される可能性が低いので、記憶装置302の記憶容量の節約のため、削除してしまうことも可能である。
【0071】
3.計算機301のメモリ上の音節毎に用意されたスタックを参照・操作しながら、前記実施の形態で示した方法により検索語出現位置を求める。検索処理中に音節と位置の間の距離を要する方法を用いる場合は、計算機メモリ上(または、記憶装置上)の音節距離配列402も参照して処理を行う。
【0072】
4.検出された検索語出現位置にしたがって、記憶装置302上の音声データ401から検索語出現位置付近の音声を取り出し、検索結果とする。音声認識結果のテキストを用いる場合は、検索語出現位置のテキストを検索結果とする。検索結果として出力する範囲は、検索語そのものや、検索語を含むより広い範囲の文や文書など、用途に応じて任意に選択することができる。検索結果は、音声再生装置やディスプレイ装置などの出力装置304を用いてユーザにそのまま提示してもよいし、機械翻訳、音声合成器、Webサーバ、などの各種サービスを提供する任意の装置への入力として利用することもできる。
【0073】
以上の〔前処理〕〔検索処理〕で説明した装置を構成する要素である、記憶装置302、入力装置303、出力装置304、および計算機301は、直接接続することもできるし、ネットワーク上に分散して配置し、通信により相互接続して装置を構成することもできる。
【0074】
また、記憶装置302上のデータである、音声データ401、音節距離配列402、音節位置ベクトル403は、それぞれ別の記憶装置に配置することも出来る。例えば、記憶装置302上のデータのうち音声データ401をネットワーク越しのサーバ上の記憶装置に配置し、音節位置ベクトルだけ計算機301に直結した記憶装置に配置することもできる。
【0075】
また、入出力装置303をWeb上のクライアントで、その他をWebサーバ上に構築することもできる。
【0076】
実施例に示した装置の実装と評価実験を、以下の手順で行った。
【0077】
日本語の学会講演と模擬講演を記録したコーパスである「日本語話し言葉コーパス(CSJ)」中の177講演(約44時間)の音声データを対象としたSTDシステムを構築した。前記CSJを検索対象とした音声ドキュメント検索用テストコレクションに含まれる前記CSJの1bestの音声認識結果を音素列に展開し、音素を分割単位として索引付けを行った。
【0078】
音素aと検索対象位置iの間の距離尺度としては、音素弁別特徴間のハミング距離[非特許文献6]を用いた。
【0079】
検索語として、前記CSJを対象とした検索語検出のためのテストコレクション[非特許文献3]の検索語を用いた。
【0080】
上記実施例と同条件の距離しきい値による連続DPマッチングと比較を行った。実験結果を(図12)と(図13)に示す。この結果から、検索性能を落とすこと無く、検索効率が大幅に改善されていることがわかる。
【符号の説明】
【0081】
101…計算機
102…記憶装置
201…音声データ
202…Confusion Network
203…音節距離配列
204…音節位置ベクトル
301…計算機
302…記憶装置
303…入力装置
304…出力装置
401…音声データ
402…音節距離配列
403…音節位置ベクトル
【特許請求の範囲】
【請求項1】
検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出手段と、
前記信号特徴抽出手段により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出手段と、
前記類似距離算出手段により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成手段と、
前記系列信号情報、前記参照信号特徴、前記信号特徴の特徴量の類似度を示す距離、および、前記特徴ベクトルを記憶する記憶装置と、
検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出手段と、
前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成手段と、
前記信号特徴列生成手段により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定手段と、
前記検索結果を出力する出力手段と
を備えたことを特徴とする系列信号検索装置。
【請求項2】
前記判定手段は、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成手段により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定手段であることを特徴とする請求項1に記載の系列信号検索装置。
【請求項3】
前記系列信号情報が音声データであり、前記信号特徴および前記参考信号特徴が、音素、音節または音素もしくは音節のn−gramによって特徴付けられる信号特徴であることを特徴とする請求項1または2に記載の系列信号検索装置。
【請求項4】
記憶装置に蓄積された情報に接続される計算機を介して検索する方法において、前処理過程および実行時処理過程とで構成された系列信号検索方法であって、
前処理過程は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出過程と、
前記信号特徴抽出過程により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出過程と、
前記類似距離算出過程により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成過程とで構成され、
実行時処理過程は、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出過程と、
前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成過程と、
前記信号特徴列生成過程により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定過程と、
前記検索結果を出力する出力過程とで構成された
ことを特徴とする系列信号検索方法。
【請求項5】
前記判定過程は、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成過程により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定過程であることを特徴とする請求項4に記載の系列信号検索方法。
【請求項6】
前記信号特徴抽出過程は、音声データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する信号特徴抽出過程であり、前記検索信号特徴抽出過程は、文字データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する検索信号特徴抽出過程であることを特徴とする請求項4または5に記載の系列信号検索方法。
【請求項1】
検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出手段と、
前記信号特徴抽出手段により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出手段と、
前記類似距離算出手段により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成手段と、
前記系列信号情報、前記参照信号特徴、前記信号特徴の特徴量の類似度を示す距離、および、前記特徴ベクトルを記憶する記憶装置と、
検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出手段と、
前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成手段と、
前記信号特徴列生成手段により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定手段と、
前記検索結果を出力する出力手段と
を備えたことを特徴とする系列信号検索装置。
【請求項2】
前記判定手段は、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成手段により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定手段であることを特徴とする請求項1に記載の系列信号検索装置。
【請求項3】
前記系列信号情報が音声データであり、前記信号特徴および前記参考信号特徴が、音素、音節または音素もしくは音節のn−gramによって特徴付けられる信号特徴であることを特徴とする請求項1または2に記載の系列信号検索装置。
【請求項4】
記憶装置に蓄積された情報に接続される計算機を介して検索する方法において、前処理過程および実行時処理過程とで構成された系列信号検索方法であって、
前処理過程は、検索対象の系列信号情報を所定単位ごとに分け、単位ごとの信号特徴を抽出する信号特徴抽出過程と、
前記信号特徴抽出過程により抽出された信号特徴と参照信号特徴との特徴量の類似度を示す距離を計算する類似距離算出過程と、
前記類似距離算出過程により算出された類似距離の最小値から信号特徴を順次配列させた特徴ベクトルを前記参照信号特徴ごとに生成する特徴ベクトル生成過程とで構成され、
実行時処理過程は、検索信号情報を所定単位ごとに分け、単位ごとの検索信号特徴を抽出する検索信号特徴抽出過程と、
前記検索信号特徴に一致する参照信号特徴ごとに前記特徴ベクトルを整列させ、各特徴ベクトルの最小値から順次選択して所定の信号列を生成する信号特徴列生成過程と、
前記信号特徴列生成過程により生成された信号特徴列が検索信号特徴の一部または全部を特定したとき、検索結果として判定する判定過程と、
前記検索結果を出力する出力過程とで構成された
ことを特徴とする系列信号検索方法。
【請求項5】
前記判定過程は、前記検索信号情報を先頭から配列した列と、前記系列信号情報を先頭から配列した列とを記憶し、前記二つの列で構成されるマトリクス上において前記信号特徴列生成過程により生成された信号特徴列が直線状に整列するとき、検索結果として判定する判定過程であることを特徴とする請求項4に記載の系列信号検索方法。
【請求項6】
前記信号特徴抽出過程は、音声データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する信号特徴抽出過程であり、前記検索信号特徴抽出過程は、文字データを音素、音節または音素もしくは音節のn−gramを単位として分割し、該単位ごとの信号特徴を抽出する検索信号特徴抽出過程であることを特徴とする請求項4または5に記載の系列信号検索方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2011−128903(P2011−128903A)
【公開日】平成23年6月30日(2011.6.30)
【国際特許分類】
【出願番号】特願2009−286883(P2009−286883)
【出願日】平成21年12月17日(2009.12.17)
【出願人】(304027349)国立大学法人豊橋技術科学大学 (391)
【Fターム(参考)】
【公開日】平成23年6月30日(2011.6.30)
【国際特許分類】
【出願日】平成21年12月17日(2009.12.17)
【出願人】(304027349)国立大学法人豊橋技術科学大学 (391)
【Fターム(参考)】
[ Back to top ]