音声中の検索語検出(STD)におけるN-gram Tree 構造を用いた高速化手法の検討
A Consideration of Fast Spoken Term Detection using N-gram Tree Structure
感性情報学講座 0312015164 横田 平志
指導教員：伊藤慶明 小嶋和徳
をサブワード N-gram として抽出し，サブワード

1. はじめにN-gram 単位で検索を行う．本講座の先行研究 2)

記憶媒体の大容量化に伴い，音声データを含む

では事前にすべての N-gram の組み合わせに対マルチメディアデータを多く利用する機会が増して検索を行い，検索結果を用いる手法が提案さ加し，マルチメディアデータ中の音声データを用れたが事前検索結果の作成に多くの時間を要すいて特定の場面を検索する機能として，音声中のるという問題がある．

検索語検出(Spoken Term Detection : STD)の研究が盛んに行われている．

提案方式ではサブワードを N 個並べたサブワード N-gram を用いる．音声データをサブワード

STD では検索語(クエリ)が辞書に登録されて系列とし，サブワードを一つずつずらしてサブワいない未知語を検出できることが重要であり，未ード N-gram を抽出する(N-gram 抽出)．抽出し知語の検出にはサブワードを用いる方式が一般たすべてのサブワード N-gram を辞書順にソー的である．サブワードを用いた STD システムでトし，保持する(N-gram Suffix Array)．N-gram

は，音声データを予めサブワードで音声認識し，Suffix Array はソート済みのデータ構造なので検索対象データをサブワード系列としておく．ク

Tree 化(N-gram Tree)を行い，二文探索で高速検エリの音節系列が与えられると，規則に基づき自索を可能とする．

動的にサブワード系列に変換し，検索対象データ

本論文ではサブワードを triphone としとサブワードレベルで連続 DP(Dynamictriphone の N-gram とする．triphone N-gram はProgramming)照合を行う．連続 DP 照合を全音4-gram，5-gram について実験を行う．検索語が声データに対して行う方式では，検索時間は音声与えられると，検索語を音声データと同様，サブデータのデータ量に比例して増加する．先行研究

ワード N-gram として抽出し，それぞれのサブワ

1) 2)

では一次検索により候補を絞ることで，検索ード N-gram について N-gram Tree を検索，一精度の低下を抑え検索時間の高速化を実現した．

次候補として抽出する．この限定された候補に対1)

先行研究 では音声認識結果の音素列からして連続 DP 照合を行い最終的な STD 結果とす

Suffix Array を作成し，Suffix Array を Tree に見る．これにより，連続 DP 照合を行う候補数を限立て(Suffix Tree)，これに対して一次検索を行っ定し，検索の高速化を実現する．ている．Suffix Tree の根の深さは統一されてい2.2 類似候補追加手法ないため枝切処理が複雑となっている．
本論文では Suffix Tree の根の深さを一定にし，音声データを音声認識する際，誤認識の発生は避けられず，検索語の話されている区間と検索語音声データのサブワード系列を N-gram としてのサブワード N-gram が完全に一致しなくなる．

抽出し，サブワード N-gram の Suffix Array を作

そのため十分な数の候補が得られず，高い検索精成し，Tree 化(N-gram Tree)することで単純な処度が得られない場合が生ずる．

理で探索可能な高速検索手法を提案する．

本手法について図 1 のサブワード 2-gram の例で説明する．検索語[aoi]が与えられると，検索2. 提案方式

対象と同様にサブワード 2-gram 抽出を行い[ao]2.1 N-gram Tree を用いた高速検索方式[oi]とする．[ao]の検索では 2-gram Tree にその音声データ中，検索語が発話されている区間にパスが存在するためその候補を抽出して終了すは，検索語の部分的なサブワード列が存在するとる．[oi]の検索では 2-gram Tree の高さ１の[o]想定できる．そこで，検索対象と検索語それぞれのパスを通り，[o]の二次の子ノードに[i]がない．

この場合候補抽出を中止するのではなく，候補子

3.2.1 類似候補追加手法

ノードの[e][u]と[i]との音響間距離を求め，閾値CSJ177 講演に対する結果を表 1，CSJ2,702 講（図 1 では 1.1）以内のものをその後も継続して演に対する結果を表 2 に示す．表 1，表２ともに探索する．図中の 2-gram Tree の検索結果は[ao]4-gram が検索時間の増加はほぼなく，精度が高[oe]となり，[ao][oe]のノードが候補となる．

かった．すべての音声データに対して連続 DP 照合を行った結果(ALL_CDP)と 4-gram を比較す
ると表 1 では P@1，P@2，P@3 でそれぞれ２.00，４.00，5.34 ポイント低下したが約 90％の検索時間の削減を実現した．表 2 では P@1 では同精度

図１

類似候補追加手法の流れ

2.3 高位強制類似候補追加手法
本提案方式ではソート済み Tree 構造を用いて効率的に探索するため，Tree の高位のノードでの探索結果の影響が強く表れる．
類似候補追加手法の検索では N-gram Tree の上の方のノードはクエリと一致し，下の方のノードのみを類似ノードのみで許容した．そのため候補の数が不十分となる場合が想定される．そこで，本手法では高さ１と高さ２のノードを探索する
際に一定の候補を類似候補追加手法で用いた閾
値以下の根ノードを探索することで検索精度の向上を図る．

3. 評価実験
3.1 評価データ
評価用のデータセット 3) は CSJ177 講演，約44 時間分と CSJ2,702 講演，604 時間分の 2 種類を用いた．検索語は NTCIR9 の Formal Run で提供された各 50 個を用いた．評価指標には P@Nを使用した．
3.2 実験結果
本実験では類似候補追加手法で N-gram で最も良い結果が得られた閾値を設定し，4-gram，5-gram それぞれ 1.9，2.0 とした．
表1

CSJ177 講演における実験結果

N-gram 追加数 MAP（%） P@1（%） P@2（%） P@3（%） time[msec]
ALL_CDP86.6 98.00 94.00 92.67
184
類似候補追加 4-gram
71.05 96.00 90.00 87.33
11
手法5-gram
65.5 96.00 89.00 84.00
9
高さ１強制類 4-gram 3
78.49 100.00 94.00 91.33
20
似候補追加手 5-gram 473.25 100.00 93.00 90.00
15
高さ２強制類 4-gram 2
75.37 100.00 93.00 90.00
12
似候補追加手 5-gram 268.67 98.00 91.00 87.33
10

表2となり P@2 では 1.00 ポイント向上した．P@3のみ精度が低下(0.67 ポイント)したが，約 99%の検索時間の削減を実現した．
3.2.2 高位強制類似候補追加手法
表１では類似候補追加手法からの検索時間の増加を抑えて精度の向上を実現した．表 2 では類
似候補追加手法でも音声データが多いため，十分な候補数が得られたため ALL_CDP の結果との差がない．本手法は音声データが小さく候補が少数しか得られない場合に有効と考える．

4. 終わりに
本論文では，Suffix Tree の根の深さを一定にすることで処理が単純な高速検索手法を提案した．類似候補追加手法では従来の連続 DP 照合手法と比べ P@1~P@3 において精度の低下を抑え，検索の高速化を実現した．高位強制類似候補追加手法では検索対象となるデータ量が少ない場合において従来の連続 DP 照合手法と比べ検索時間の増加はほぼなく，精度の向上を実現した．今後は適切な triphone N-gram について検討する．
また，本論文では音節の音声認識結果のみを用いたが単語の音声認識結果の併用した検証を検討したいと考える．

参考文献
1)

恒雄，“Suffix Array を用いた高速音声検索語検出システムの性能評価”，電子情報学会論文誌
2)

D，2013

伊藤慶明，斉藤裕介，田中和世，李時旭，“音節 N-gram の事前検索結果を利用した音声中

CSJ2702 講演における実験結果

N-gram 追加数 MAP（%） P@1（%） P@2（%） P@3（%） time[msec]
ALL_CDP80.56 96.00 93.00 94.67
3071
類似候補追加 4-gram
73.32 96.00 94.00 94.00
44
手法
5-gram
66.92 94.00 94.00 93.33
36
高さ１強制類 4-gram 3
75.36 94.00 94.00 94.67
143
似候補追加手 5-gram 470.67 94.00 94.00 94.00
110
高さ2強制類 4-gram 2
75.07 94.00 94.00 94.67
82
似候補追加手 5-gram 2
68.61 92.00 94.00 94.00
55

桂田 浩一，勝浦 広大，入部百 合絵，新田の検索語検出の高速化方式”，情報処理学会
論文誌
3)

Vol.54，N012 (Dec．2013)

Tomoyosi Akiba et al，Overview of the IR for
Spoken Document Task in NTCIR Workshop，
NTCIR-9 Meeting，2011.