julius/factoring_sub.c

言語スコアのfactoring計算 [詳細]

#include <julius.h>

factoring_sub.cのインクルード依存関係図

ソースコードを見る。

関数
static void	add_successor (WCHMM_INFO *wchmm, int node, WORD_ID w)
	木構造化辞書上のあるノードの successor list に単語を追加する．
static boolean	match_successor (WCHMM_INFO *wchmm, int node1, int node2)
static void	free_successor (WCHMM_INFO *wchmm, int scid)
static void	compaction_successor (WCHMM_INFO *wchmm)
static void	shrink_successor (WCHMM_INFO *wchmm)
void	make_successor_list (WCHMM_INFO *wchmm)
void	max_successor_cache_init (WCHMM_INFO *wchmm)
static void	max_successor_prob_iw_free ()
void	max_successor_cache_free ()
void	make_iwcache_index (WCHMM_INFO *wchmm)
	単語先頭ノードのうちFactoring においてキャッシュが必要なノードの リストを作成する．
static LOGPROB	calc_successor_prob (WCHMM_INFO *wchmm, WORD_ID last_nword, int node)
	木構造化辞書上の 1-gram factoring 値を計算して格納する．
LOGPROB	max_successor_prob (WCHMM_INFO *wchmm, WORD_ID lastword, int node)
	単語内のあるノードについて factoring 値を計算する．
LOGPROB *	max_successor_prob_iw (WCHMM_INFO *wchmm, WORD_ID lastword)
	単語間の factoring 値のリストを返す．
変数
static LOGPROB *	probcache
	Word-internal factoring cache indexed by scid, holding last score.
static WORD_ID *	lastwcache
	Word-internal factoring cache indexed by scid, holding last N-gram entry ID.
static LOGPROB **	iw_sc_cache
	Cross-word factoring cache to hold last-word-dependent factoring score toward word head nodes.
static int	iw_cache_num

---

説明

言語スコアのfactoring計算

作者:

Akinobu LEE

日付:

Mon Mar 7 23:20:26 2005

このファイルには，第１パスにおいて言語スコアの factoring を行うための 関数が含まれています．木構造化辞書上でのサブツリー内の単語リスト (successor list) の構築，および認識中の言語スコア計算ルーチンが 含まれます．

successor list は，木構造化辞書の各ノードに割り付けられる， そのノードを共有する単語のリストです．木構造化辞書において， 枝部分の次のノードがこのリストを保持します．実際にはリストが変化する 場所，すなわち木構造化辞書の枝の分岐点に割り付けられます． 例えば，以下のような木構造化辞書の場合，数字の書いてあるノードに successor list が割り付けられます．

2-o-o - o-o-o - o-o-o word "A" / 1-o-o \ 4-o-o word "B" \ / 3-o-o - 5-o-o - 7-o-o word "C" \ \ \ 8-o-o word "D" 6-o-o word "E"

各 successor list はそのサブツリーに含まれる単語のリストです． この例では以下のようになります．

node | successor list (wchmm->state[node].sc) ======================= 1 | A B C D E 2 | A 3 | B C D E 4 | B 5 | C D 6 | E 7 | C 8 | D

ある successor list に含まれる単語が１つになったとき，その時点で 単語が確定する．上記の場合，単語 "A" はノード 2 の位置ですでに その後続単語として "A" 以外無いので，そこで確定する． すなわち，単語 A の正確な言語スコアは，単語終端を待たずノード 2 で決まる．

第１パスにおける factoring の計算は，実際には beam.c で行なわれる． 2-gram factoringの場合，次ノードに successor list が存在すれば, その successor list の単語の 2-gram の最大値を求め, 伝搬してきている factoring 値を更新する．successor list に単語が1つのノードでは， 正しい2-gramが自動的に割り当てられる． 1-gram factoringの場合，次ノードに successor list が存在する場合， その successor list の単語の 1-gram の最大値を求め，伝搬してきている factoring 値を更新する．successor list に単語が１つのノードで，はじめて 2-gram を計算する．

実際では 1-gram factoring では各 successor list における factoring 値 は単語履歴に非依存なので，successor list 構築時に全てあらかじめ計算して おく．すなわち，エンジン起動時に木構造化辞書を構築後，successor list を構築したら，単語を2個以上含む successor list についてはその 1-gram の 最大値を計算して，それをそのノードの fscore メンバに格納しておき，その successor list は free してしまえばよい．単語が１つのみの successor list についてはその単語IDを残しておき，探索時にパスがそこに到達したら 正確な2-gramを計算すれば良い．

DFA文法使用時は，デフォルトでは言語制約(カテゴリ対制約)を カテゴリ単位で木を構築することで静的に表現する．このため， これらの factoring 機構は用いられない．ただし， CATEGORY_TREE が undefined であれば，決定的 factoring を用いた言語制約 適用を行うことも可能である． すなわち，次ノードに successor list が存在すれば, その successor list 内の各単語と直前単語の単語対制約を調べ, そのうち一つでも接続可能な単語があれば，その遷移を許し，一つも なければ遷移させない．この機能は技術参考のために残されているのみである．

This file contains functions to do language score factoring on the 1st pass. They build a successor lists which holds the successive words in each sub tree on the tree lexicon, and also provide a factored LM probability on each nodes on the tree lexicon.

The "successor list" will be assigned for each lexicon tree node to represent a list of words that exist in the sub-tree and share the node. Actually they will be assigned to the branch node. Below is the example of successor lists on a tree lexicon, in which the lists is assigned to the numbered nodes.

2-o-o - o-o-o - o-o-o word "A" / 1-o-o \ 4-o-o word "B" \ / 3-o-o - 5-o-o - 7-o-o word "C" \ \ \ 8-o-o word "D" 6-o-o word "E"

The contents of the successor lists are the following:

node | successor list (wchmm->state[node].sc) ======================= 1 | A B C D E 2 | A 3 | B C D E 4 | B 5 | C D 6 | E 7 | C 8 | D

When the 1st pass proceeds, if the next going node has a successor list, all the word 2-gram scores in the successor list on the next node will be computed, and the propagating LM value in the token on the current node will be replaced by the maximum value of the scores when copied to the next node. Appearently, if the successor list has only one word, it means that the word can be determined on that point, and the precise 2-gram value will be assigned as is.

When using 1-gram factoring, the computation will be slightly different. Since the factoring value (maximum value of 1-gram scores on each successor list) is independent of the word context, they can be computed statically before the search. Thus, for all the successor lists that have more than two words, the maximum 1-gram value is computed and stored to "fscore" member in tree lexicon, and the successor lists will be freed. The successor lists with only one word should still remain in the tree lexicon, to compute the precise 2-gram scores for the words.

When using DFA grammar, Julian builds separated lexicon trees for every word categories, to statically express the catergory-pair constraint. Thus these factoring scheme is not used by default. However you can still force Julian to use the grammar-based deterministic factoring scheme by undefining CATEGORY_TREE. If CATEGORY_TREE is undefined, the word connection constraint will be performed based on the successor list at the middle of tree lexicon. This enables single tree search on Julian. This function is left only for technical reference.

Revision

1.3

factoring_sub.c で定義されています。

---

関数

static void add_successor	(	WCHMM_INFO *	wchmm,
		int	node,
		WORD_ID	w
	)			[static]

木構造化辞書上のあるノードの successor list に単語を追加する．

すでに同じ単語が登録されていれば，新たに登録はされない． 単語はIDで昇順に保存される．

引数:

	wchmm	[i/o] 木構造化辞書
	node	[in] ノード番号
	w	[in] 単語ID

factoring_sub.c の 184 行で定義されています。

参照元 make_successor_list().

static boolean match_successor	(	WCHMM_INFO *	wchmm,
		int	node1,
		int	node2
	)			[static]

２つのノード上の successor list が一致するかどうかチェックする

引数:

	wchmm	[in] 木構造化辞書
	node1	[in] １つめのノードID
	node2	[in] ２つめのノードID

戻り値:

完全に一致すれば TRUE，一致しなければ FALSE．

factoring_sub.c の 236 行で定義されています。

参照元 make_successor_list().

static void free_successor	(	WCHMM_INFO *	wchmm,
		int	scid
	)			[static]

指定ノード上の successor list を空にする．

引数:

	wchmm	[i/o] 木構造化辞書
	scid	[in] node id

factoring_sub.c の 276 行で定義されています。

参照元 make_successor_list().

static void compaction_successor

(

WCHMM_INFO *

wchmm

)

[static]

木構造化辞書上からリンクが消された successor list について， その実体を削除してリストを詰めるガーベージコレクションを行う．

引数:

wchmm

[i/o] 木構造化辞書

factoring_sub.c の 305 行で定義されています。

参照元 make_successor_list().

static void shrink_successor

(

WCHMM_INFO *

wchmm

)

[static]

successor list 用に割り付けられたメモリ領域を有効な長さに縮める． 初期構築時や，1-gram factoring のために削除された successor list 分の メモリを解放する．

引数:

wchmm

[i/o] 木構造化辞書

factoring_sub.c の 341 行で定義されています。

参照元 max_successor_cache_init().

void make_successor_list

(

WCHMM_INFO *

wchmm

)

木構造化辞書上の全ノードに successor list を構築するメイン関数

引数:

wchmm

[i/o] 木構造化辞書

factoring_sub.c の 360 行で定義されています。

参照元 build_wchmm2().

void max_successor_cache_init

(

WCHMM_INFO *

wchmm

)

木構造化辞書用の factoring キャッシュをメモリ割り付けして初期化する． この関数はプログラム開始時に一度だけ呼ばれる．

引数:

wchmm

[i/o] 木構造化辞書

factoring_sub.c の 602 行で定義されています。

参照元 final_fusion().

static void max_successor_prob_iw_free

(

)

[static]

単語間の factoring cache のメモリ領域を解放する．

factoring_sub.c の 645 行で定義されています。

参照元 max_successor_cache_free(), と max_successor_prob_iw().

void max_successor_cache_free

(

void

)

factoring 用 cache のメモリ領域を全て解放する．

factoring_sub.c の 665 行で定義されています。

void make_iwcache_index

(

WCHMM_INFO *

wchmm

)

単語先頭ノードのうちFactoring においてキャッシュが必要なノードの リストを作成する．

1-gram factoring は，枝ノードにおいて直前単語に依存しない固定値 (unigramの最大値)を与える．このため，単語間の factoring 計算において， 木構造化辞書上で複数の単語で共有されている単語先頭ノードについては， その値は直前単語によらず固定値であり，認識時に単語間キャッシュを保持 する必要はない．

この関数では，単語先頭ノードのリストからそのような factoring キャッシュが 不要なノードを除外して，1-gram factoring 時に単語間キャッシュが必要な 単語先頭ノード（＝他の単語と共有されていない独立した単語先頭ノード）の リストを作成し，wchmm->start2isolate および wchmm->isolatenum に格納する．

引数:

wchmm

[i/o] 木構造化辞書

factoring_sub.c の 715 行で定義されています。

参照元 build_wchmm2().

static LOGPROB calc_successor_prob	(	WCHMM_INFO *	wchmm,
		WORD_ID	last_nword,
		int	node
	)			[static]

木構造化辞書上の 1-gram factoring 値を計算して格納する．

1-gram factoring では単語間で共有されている枝ノードでは 1-gram の最大値 を与える．単語履歴によらないため，その値は認識開始前に 計算しておくことができる．この関数は木構造化辞書 全体について，共有されている（successor list に２つ以上の単語を持つノード） ノードの 1-gram factoring 値を計算して格納する．1-gram factoring値を 計算後は，そのノードの successor list はもはや不要であるため，ここで 削除する．

実際には，factoring 値は wchmm->fscore に順次保存され，ノードの scid にその保存値へのインデックス(1-)の負の値が格納される．不要になった successor list は，実際には compaction_successor 内で，対応するノードの scid が負になっている successor list を削除することで行なわれる．

引数:

wchmm

[i/o] 木構造化辞書

factoring_sub.c の 842 行で定義されています。

参照元 max_successor_prob(), と max_successor_prob_iw().

LOGPROB max_successor_prob	(	WCHMM_INFO *	wchmm,
		WORD_ID	lastword,
		int	node
	)

単語内のあるノードについて factoring 値を計算する．

1-gram factoring で固定factoring値がある場合はその値が即座に返される． 他の場合は，そのノードのサブツリー内の単語の 2-gram確率（の最大値）が 計算される．

単語内 factoring キャッシュが考慮される．すなわち各ノードについて 直前単語が前回アクセスされたときと同じであれば， 前回の値が返され，そうでなければ値を計算し，キャッシュが更新される．

引数:

	wchmm	[in] 木構造化辞書
	lastword	[in] 直前単語のID
	node	[in] ノード番号

戻り値:

言語モデルスコア

factoring_sub.c の 900 行で定義されています。

参照元 get_back_trellis_proceed(), と init_nodescore().

LOGPROB* max_successor_prob_iw	(	WCHMM_INFO *	wchmm,
		WORD_ID	lastword
	)

単語間の factoring 値のリストを返す．

与えられた直前単語に対して，factoring値を計算すべき全ての単語先頭への factoring 値を計算し，そのリストを返す．このfactoring値は 直前単語ごとにリスト単位でキャッシュされる．すなわち，その直前単語が それまでに一度でも直前単語として出現していた場合，そのリストをそのまま 返す．

引数:

	wchmm	[in] 木構造化辞書
	lastword	[in] 直前単語

戻り値:

全単語先頭ノードへの factoring スコアのリスト

factoring_sub.c の 992 行で定義されています。

参照元 get_back_trellis_proceed().

---

変数

LOGPROB** iw_sc_cache [static]

Cross-word factoring cache to hold last-word-dependent factoring score toward word head nodes.

Cached values will be stored as [last_nword][n], where n is the number of word-head node on which the last_nword-dependent N-gram factoring value should be computed on cross-word transition. In 1-gram factoring, n equals to wchmm->isolatenum, the number of isolated (not shared) word-head nodes. In 2-gram factoring, n simply equals to wchmm->startnum, the number of all word-head nodes.

The cache area will be allocated per the previous word when they appeared while search. It will retain across the speech stream, so the cache area will grow to an extent as recognition was done for many files.

factoring_sub.c の 575 行で定義されています。

int iw_cache_num [static]

Maximum size of cross-word factoring cache iw_sc_cache per last word. The value is set in max_successor_cache_init().

factoring_sub.c の 580 行で定義されています。