여기에서는 정상적인 그래프 생성 접근 방식과 관련된 특정 data-preparation stages를 단계별로 설명합니다.

 

이 방법에 대한 대부분의 세부 사항은 우리 tools에 하드 코딩되어 있지 않습니다. 우리는 단지 현재 어떻게 done 되어 있는지 설명하고 있습니다. 이 섹션이 혼란 스러우면 가장 좋은 해결책은 Mohri et al.의 "Speech Recognition with Weighted Finite-State Transducers" 을 읽는 것입니다. 경고 : 그 Paper는 꽤 길며, FST에 익숙하지 않은 사람들에게는 적어도 몇 시간이 걸릴 것입니다. 또 다른 좋은 자료는 OpenFst website 로서 심볼 테이블과 같은 것들에 대한 더 많은 컨텍스트를 제공합니다.

 

Preparing the initial symbol tables

우리는 OpenFst symbol tables words.txt 및 phones.txt를 준비해야합니다. 이것들은 우리 시스템 안의 integer id's 를 모든 단어와 phones에 할당합니다. OpenFst는 epsilon을 위해심볼 0을 예약합니다. An example of how the symbol tables look for the WSJ task is:

 

## head words.txt

<eps> 0
!SIL 1
<s> 2
</s> 3
<SPOKEN_NOISE> 4
<UNK> 5
<NOISE> 6
!EXCLAMATION-POINT 7
"CLOSE-QUOTE 8
## tail -2 words.txt
}RIGHT-BRACE 123683
#0 123684
## head data/phones.txt
<eps> 0
SIL 1
SPN 2
NSN 3
AA 4
AA_B 5

 

words.txt 파일에는 단일 명확성(disambiguation)기호 "#0"(used for epsilon on the input of G.fst))이 포함되어 있습니다. 이것은 레시피에서 마지막으로 번호가 매겨진 단어입니다. 사전에 단어 "#0"이 포함되어 있으면 주의하십시오. phones.txt 파일에는 명확성 기호가 포함되어 있지 않지만 L.fst를 만든 후 명확성 기호가 포함 된 phone_disambig.txt 파일을 만듭니다 (디버깅에 유용함).

 

Preparing the lexicon L

먼저 처음에는 명확성 기호가없는 텍스트 형식의 lexicon을만듭니다. 우리의 C ++ 툴은 이것과 상호 작용하지 않으며, lexiconFST를 생성하는 스크립트에 의해서만 사용될 것입니다. WSJ lexicon의일부는 다음과 같습니다.

 

## head data/lexicon.txt

!SIL SIL
<s>
</s>
<SPOKEN_NOISE> SPN
<UNK> SPN
<NOISE> NSN
!EXCLAMATION-POINT EH2_B K S K L AH0 M EY1 SH AH0 N P OY2 N T_E
"CLOSE-QUOTE K_B L OW1 Z K W OW1 T_E

 

phones 의 시작, 끝 및 stress markers(예 : T_E 또는 AH0)는 WSJ recipe에따라 다르며 툴킷에 관한 한 별도의 phones로 취급됩니다 (however, we do handle the tree-building specially for this setup; read about the roots file in The tree building process).

 

words with empty phonetic representations는 허용됩니다. 이 lexicon은 훈련에 사용 된 L.fst를 만드는 데 사용됩니다 (without disambiguation symbols). 또한 decoding그래프 생성에 사용되는 disambiguation symbols가 포함 된 lexicon을 만듭니다. 이 파일의 추출은 다음과 같습니다.

 

# [from data/lexicon_disambig.txt]

!SIL SIL
<s> #1
</s> #2
<SPOKEN_NOISE> SPN #3
<UNK> SPN #4
<NOISE> NSN
...
{BRACE B_B R EY1 S_E #4
{LEFT-BRACE L_B EH1 F T B R EY1 S_E #4

 

이 파일은 스크립트로 작성됩니다. 이 스크립트는 추가해야 할 disambiguation symbols의 수를 출력하며, 이 것은 phone_disambig.txt symbol table을 만드는 데 사용됩니다. 이는 phone.txt와 동일하지만, disambiguation symbols#0, #1, #2 등의 integer ID도 포함합니다 (#0은, G.fst에서 왔지만 자체 루프를 통해 L.fst를 통과하는, 특수한 명확성 기호입니다.). phones_disambig.txt 파일 중간 부분은 다음과 같습니다.

 

ZH_E 338
ZH_S 339
#0 340
#1 341
#2 342
#3 343

 

이 (WSJ) recipe에서 stress와 position information를 phones에 추가했기 때문에, 숫자가 너무 높습니다. 빈 단어 (예 : <s> 및 </ s>)에 사용 된 명확성 기호는 일반 단어에 사용 된 명확성 기호와 달라야하므로이 예에서 "일반"명확성 기호는 #3부터 시작합니다.

 

명확성 기호가없는 lexicon을 FST로 변환하는 명령은 다음과 같습니다.

scripts/make_lexicon_fst.pl data/lexicon.txt 0.5 SIL | \
fstcompile --isymbols=data/phones.txt --osymbols=data/words.txt \
--keep_isymbols=false --keep_osymbols=false | \
fstarcsort --sort_type=olabel > data/L.fst

 

여기서 make_lexicon_fst.pl 스크립트는 FST의 텍스트 표현을 만듭니다. 0.5는 silence확률입니다 (즉, 문장의 시작과 각 단어 다음에, 우리는 확률 0.5로 silence을 출력합니다. silence로 할당 된 probability mass 은 1.0-0.5 = 0.5입니다.이 예의 나머지 명령은 FST를 컴파일 된 형식으로 변환하는 것과 관련이 있습니다. 나중에 compose하기 때문에 fstarcsort가 필요합니다.

 

Lexicon의 구조는 대략 예상대로입니다. 최종적인 하나의 상태 ( "the "loop state")가 있습니다. 루프 상태로 두 가지 전환이있는 시작 상태가 있습니다. one with silence and one without.루프 상태에서 각 단어에 해당하는 전이가 있으며 해당 단어는 전이의 출력 심볼입니다. 입력 기호는 해당 단어의 첫 번째 포님입니다. composition의 효율성과 minimization의 효과 를 위해, 출력 기호가 가능한 한 빨리 (즉, 단어의 끝이 아닌 처음에) 있어야합니다. 각 단어의 끝에서, 선택적 silence 를 처리하기 위해, 마지막 phone 에 대응하는 transitions는 두 가지 형태가 있다. 하나는 loop상태로 전환되고, 다른 하나는 루프 상태로 전환되는 "silence상태"로 전환된다. 우리는 silence 단어 뒤에 선택 silence을 넣는 것을 걱정하지 않는다. 우리는 silence phone이라는 하나의 phone을 가진 단어로 정의합니다.

 

disambiguation symbols lexicon을 만드는 것은 약간 더 복잡합니다. 문제는 G.fst의 disambiguation symbol#0 이 lexicon을 통해 전달 될 수 있도록 lexicon에 self-loop를 추가해야한다는 것입니다. 우리는 fstaddselfloops (c.f. Adding and removing disambiguation symbols) 프로그램을 사용 하여이 이 작업을 수행합니다. make_lexicon_fst.pl 스크립트에서 "수동으로" 쉽게 수행 할 수있었습니다.

 

phone_disambig_symbol=`grep \#0 data/phones_disambig.txt | awk '{print $2}'`
word_disambig_symbol=`grep \#0 data/words.txt | awk '{print $2}'`
scripts/make_lexicon_fst.pl data/lexicon_disambig.txt 0.5 SIL | \
fstcompile --isymbols=data/phones_disambig.txt --osymbols=data/words.txt \
--keep_isymbols=false --keep_osymbols=false | \
fstaddselfloops "echo $phone_disambig_symbol |" "echo $word_disambig_symbol |" | \
fstarcsort --sort_type=olabel > data/L_disambig.fst

 

 

fstaddselfloops 프로그램은 원래 OpenFst 명령 줄 도구 중 하나가 아니며, Kaldi 자체 tools 중 하나입니다.

 

Preparing the grammar G

문법 G는 단어를 그것의 상징으로하는 acceptor 입니다 (즉, 입력 및 출력 기호는 각 arc에서 동일합니다).입력측에만 나타나는 disambiguation symbol#0은 예외입니다. 입력이 Arpa 파일이라고 가정하면 Kaldi 프로그램 arpa2fst를 사용하여 FST로 변환합니다. 이 프로그램 arpa2fst는 내장된 기호(embedded symbols)가 있는 FST를 출력한다. Kaldi에서는 일반적으로 내장된 기호가 없는 FST를 사용한다.(즉, 별도의 심볼 테이블을 사용함). arpa2fst를 실행하는 것 이외의 단계는 다음과 같습니다.

 

더보기

- 우리는 FST에서 내장된 기호(embedded symbols)를 제거해야 한다 (그리고 disk의 symbol tables에 의존한다).

- 우리는 언어 모델에 out-of-vocabulary(OOV) word 가 없는지 확인해야 한다.

- 시작 및 종료 기호의 "illegal" 시퀀스를 제거해야 한다. 예 : <s> 뒤에 </ s>가 있다. 왜냐하면 L o G를 결정할 수 없기 때문이다.

- 입력측의 epsilons을 특수 disambiguation symbol #0으로 대체해야 한다.

이를 수행하는 실제 스크립트의 약간 단순화 된 버전은 다음과 같습니다.

gunzip -c data_prep/lm.arpa.gz | \
arpa2fst --disambig-symbol=#0 \
--read-symbol-table=data/words.txt - data/G.fst

마지막 명령 (fstisstochastic)은 진단 단계입니다 (stochasticity 유지 및 테스트 참조). 전형적인 예에서, 숫자를 출력합니다 :

9.14233e-05 -0.259833

 

첫 번째 숫자는 작으므로 호의 확률 질량에 1보다 현저히 작은 최종 상태를 더한 상태가 없음을 확인합니다. 두 번째 숫자는 중요하며 이는 "너무 많은"확률 질량을 갖는 상태가 있음을 의미합니다 (FST에있는 가중치의 숫자 값은 일반적으로 부정 로그 확률로 해석 될 수 있음). "매우 많은"확률 질량을 가진 일부 상태를 갖는 것은 백 오프가있는 언어 모델의 FST 표현에 일반적입니다. 이후의 그래프 생성 단계에서이 비 확률 성이 시작 시보 다 악화되지 않았는지 확인합니다.

 

결과 FST G.fst는 물론 테스트 시간에만 사용됩니다. 훈련 시간에는 훈련 단어 시퀀스에서 생성 된 선형 FST를 사용하지만 이는 스크립트 수준이 아닌 Kaldi 프로세스 내에서 수행됩니다.

 

Preparing LG

L을 G로 작성할 때, 우리는 상당히 표준적인 레시피를 준수합니다. 즉, min (det (L o G))을 계산합니다. 명령 행은 다음과 같습니다.

 

fsttablecompose data/L_disambig.fst data/G.fst | \
fstdeterminizestar --use-log=true | \
fstminimizeencoded | fstpushspecial | \
fstarcsort --sort-type=ilabel > somedir/LG.fst

 

OpenFst 알고리즘과는 약간의 차이가 있습니다. 우리는 커맨드 라인 도구 "fsttablecompose"로 구현 된보다 효율적인 컴포지션 알고리즘 (컴포지션 참조)을 사용합니다. 우리의 결정은 명령 행 프로그램 fstdeterminizestar에 의해 구현되는 엡실론을 제거하는 알고리즘입니다. –use-log = true 옵션은 프로그램에게 먼저 FST를 로그 반올림으로 캐스트하도록 요청합니다. 이것은 확률을 유지합니다 (로그 반고리에서). 확률 보존 및 테스트를 참조하십시오.

 

"fstminimizeencoded"프로그램으로 최소화합니다. 이것은 가중 수락 자에 적용되는 OpenFst 최소화 알고리즘 버전과 대부분 동일합니다. 여기서 관련된 유일한 변화는 무게 추를 피하여 확률을 유지한다는 것입니다 (자세한 내용은 최소화 참조).

 

"fstpushspecial"프로그램은 OpenFst의 "fstpush"프로그램과 유사하지만, 가중치가 1에 합치 지 않으면 모든 상태가 동일한 값 (일부와 다름)을 "보일"수 있도록합니다. 그래프의 시작 또는 끝에 "추가"가중치. 이것은 실패 할 수 없다는 이점이 있습니다 (FST가 "무한"한 경우 "fstpush"는 실패하거나 아주 오랫동안 반복 될 수 있습니다). 또한 훨씬 빠릅니다. 자세한 내용은 push-special.cc를 참조하십시오.

 

"fstarcsort"스테이지는 나중에 컴포지션 작업이 빠르도록 아크를 정렬합니다.

 

Preparing CLG

입력이 상황에 따른 전화 인 트랜스 듀서를 얻으려면 C o L o G와 동등한 CLG라는 FST를 준비해야합니다. 여기서 L과 G는 어휘와 문법이고 C는 음성 상황을 나타냅니다. 트라이 폰 시스템의 경우, C의 입력 심볼은 a / b / c (즉, 트리플 전화) 형태이고, 출력 심볼은 단일 전화 (예를 들어, a 또는 b 또는 c) 일 것이다. 발음 컨텍스트 창에 대한 자세한 내용과 다른 컨텍스트 크기로 일반화하는 방법은 발음 컨텍스트 창을 참조하십시오. 먼저, FST C 컨텍스트 자체를 작성하고 정상적으로 작성해야하는 경우 컨텍스트를 작성하는 방법에 대해 설명합니다 (효율성과 확장 성 때문에 스크립트가 실제로는 작동하지 않습니다).

 

A) Making the context transducer

이 섹션에서는 C를 독립형 FST로 얻는 방법을 설명합니다.

 

C의 기본 구조는 N-1 크기의 모든 가능한 전화 창에 대한 상태를 가지고 있다는 것입니다 (c.f. 음성 문맥 창; 3 개의 경우, N = 3). 발화를 의미하는 첫 번째 상태는 N-1 엡실론에 해당합니다. 각 상태는 각 전화기마다 전환이 있습니다 (현재는 자체 루프를 잊어 버리십시오). 일반적인 예로, 상태 a / b는 출력에서 ​​c로, 입력에서 a / b / c로 전환하여 상태 b / c로 전환합니다. 발화의 시작과 끝에 특별한 경우가 있습니다.

 

발화 시작시 상태가 <eps> / <eps>이고 출력 기호가 a라고 가정합니다. 일반적으로 입력 심볼은 <eps> / <eps> / a입니다. 그러나 이것은 전화를 나타내지 않기 때문에 (P = 1이라고 가정) 중심 요소는 전화가 아닌 <eps>입니다. 이 경우 호의 입력 기호를 # -1로 지정합니다.이 목적을 위해 소개하는 특수 기호입니다 (빈 단어가있을 때 결정 불가능 성을 초래할 수 있으므로 표준 레시피와 같이 엡실론을 사용하지 마십시오) ).

 

발언의 경우는 약간 복잡합니다. 컨텍스트 FST의 오른쪽 (출력측)에는 발화의 끝에서 발생하는 특수 기호 $가 있습니다. 트라이 폰 케이스를 고려하십시오. 발화가 끝날 때 모든 기호를 본 후 마지막 트라이 폰 (예 : a / b / <eps>, <eps>는 정의되지 않은 컨텍스트를 나타냄)을 플러시해야합니다. 이를 수행하는 자연스러운 방법은 입력 a / b / <eps>를 출력 a에서 b / <eps>로 출력 a를 상태 a / b에서 최종 상태로 전환하는 것입니다 (예 : b / <eps> 또는 a 특별 최종 상태). 그러나 이것은 발화의 끝이 아니었다면 제거되기 전에 그러한 전환을 탐색해야하기 때문에 구성에 비효율적입니다. 대신에 우리는 발화 끝 기호로 $를 사용하고 LG에서 각 경로 끝에 한 번 표시되도록합니다. 그런 다음 C의 출력에서 ​​<eps>를 $로 바꿉니다. 일반적으로 $의 반복 횟수는 N-P-1과 같습니다. 번거 로움으로 LG에 추가 할 수있는 후속 심볼 수를 해결해야하는 번거 로움을 피하기 위해 발언이 끝날 때 해당 심볼을 원하는 개수만큼 받아 들일 수 있습니다. 이것은 AddSubsequentialLoop () 함수와 명령 행 프로그램 fstaddsubsequentialloop에 의해 달성됩니다.

 

C 자체를 원한다면 우선 명확성 기호 목록이 필요합니다. 또한 다음과 같이 후속 심볼에 사용할 수있는 사용되지 않은 심볼 ID를 해결해야합니다.

grep '#' data/phones_disambig.txt | awk '{print $2}' > $dir/disambig_phones.list
subseq_sym=`tail -1 data/phones_disambig.txt | awk '{print $2+1;}'`

그런 다음 다음 명령을 사용하여 C를 만들 수 있습니다 (그러나 fstcompose 컨텍스트에 대해서는 아래를 참조하십시오. 실제로는 비효율적 이므로이 작업을 수행하지 않습니다).

fstmakecontextfst --read-disambig-syms=$dir/disambig_phones.list \
--write-disambig-syms=$dir/disambig_ilabels.list data/phones.txt $subseq_sym \
$dir/ilabels | fstarcsort --sort_type=olabel > $dir/C.fst

fstmakecontextfst 프로그램에는 전화 목록, 명확성 기호 목록 및 후속 기호의 ID가 필요합니다. C.fst 외에도 C.fst 왼쪽의 기호를 해석하는 "ilabels"파일을 작성합니다 (ilabel_info 오브젝트 참조). LG의 구성은 다음과 같이 수행 할 수 있습니다.

fstaddsubsequentialloop $subseq_sym $dir/LG.fst | \
fsttablecompose $dir/C.fst - > $dir/CLG.fst

C.fst 및 "ilabels"를 색인화하는 동일한 기호를 사용하여 인쇄하려면 다음 명령을 사용하여 적절한 기호 테이블을 만들 수 있습니다.

fstmakecontextsyms data/phones.txt $dir/ilabels > $dir/context_syms.txt

이 명령은 "ilabels"형식 (ilabel_info 오브젝트)에 대해 알고 있습니다. 이 기호 테이블로 인쇄 된 CLG fst (자원 관리 용)를 통한 임의의 경로 예는 다음과 같습니다.

## fstrandgen --select=log_prob $dir/CLG.fst | \
fstprint --isymbols=$dir/context_syms.txt --osymbols=data/words.txt -

0 1 #-1 <eps>
1 2 <eps>/s/ax SUPPLIES
2 3 s/ax/p <eps>
3 4 ax/p/l <eps>
4 5 p/l/ay <eps>
5 6 l/ay/z <eps>
6 7 ay/z/sil <eps>
7 8 z/sil/<eps> <eps>
8

 

B) Composing with C dynamically

일반적인 그래프 생성 레시피에서는 fstcomposecontext 프로그램을 사용하여 C의 필요한 상태와 호를 모두 낭비하지 않고 동적으로 생성합니다. 명령 행은 다음과 같습니다.

 

fstcomposecontext --read-disambig-syms=$dir/disambig_phones.list \
                  --write-disambig-syms=$dir/disambig_ilabels.list \
                  $dir/ilabels < $dir/LG.fst >$dir/CLG.fst

기본값 (3 및 1)과 다른 컨텍스트 매개 변수 N 및 P가있는 경우이 프로그램에 추가 옵션을 제공합니다. 이 프로그램은 CLG.fst의 입력 기호를 해석하는 파일 "ilabels"(ilabel_info 오브젝트 참조)를 작성합니다. 자원 관리 레시피에서 ilabels 파일의 처음 몇 줄은 다음과 같습니다.

65028 [ ]
[ 0 ]
[ -49 ]
[ -50 ]
[ -51 ]
[ 0 1 0 ]
[ 0 1 1 ]
[ 0 1 2 ]
...

 

숫자 65028은 파일의 요소 수입니다. [-49]와 같은 줄은 명확성 기호를위한 것입니다. [012]와 같은 선은 음향 상황 창을 나타내고; 처음 두 항목은 결정 가능성을 보장하기 위해 엡실론 용 [] (사용하지 않음)과 [0]으로, C의 시작 부분에서 엡실론 대신 C로 시작하는 양식 # -1의 특수 명확화 기호 용입니다.

 

C) Reducing the number of context-dependent input symbols

CLG.fst를 생성 한 후에는 크기를 줄일 수있는 선택적 그래프 생성 단계가 있습니다. 의사 결정 트리 및 HMM 토폴로지 정보에서 작동하는 프로그램 make-ilabel-transducer를 사용합니다. 컨텍스트 종속 전화의 하위 집합은 동일한 컴파일 된 그래프에 해당하므로 병합 할 수 있습니다 (각 요소의 임의 요소 선택) 모든 컨텍스트 창을 해당 컨텍스트 창으로 변환합니다. 이것은 HTK의 논리적-물리적 매핑과 유사한 개념입니다. 명령은 다음과 같습니다.

 

make-ilabel-transducer --write-disambig-syms=$dir/disambig_ilabels_remapped.list \
                        $dir/ilabels \
                        $tree $model \
                        $dir/ilabels.remapped > $dir/ilabel_map.fst

이 프로그램에는 나무와 모델이 필요합니다. "ilabels.remapped"라는 새 ilabel_info 객체를 출력합니다. 이것은 원래 "ilabels"파일과 동일한 형식이지만 줄이 더 적습니다. FST "ilabel_map.fst"는 CLG.fst로 구성되며 레이블을 다시 맵핑합니다. 이 작업을 수행 한 후 결정 및 최소화하여 크기 축소를 즉시 실현할 수 있습니다.

fstcompose $dir/ilabel_map.fst $dir/CLG.fst | \
fstdeterminizestar --use-log=true | \
fstminimizeencoded > $dir/CLG2.fst

 

일반적인 설정의 경우이 단계에서는 실제로 그래프 크기를 크게 줄이지 않으며 (5 % ~ 20 % 감소가 일반적 임), 어떤 경우에도이 메커니즘으로 축소하는 중간 그래프 작성 단계의 크기입니다. 그러나 컨텍스트가 더 넓은 시스템에서는 비용을 크게 절감 할 수 있습니다.

 

 

Making the H transducer

 

기존의 FST 레시피에서 H 트랜스 듀서는 출력에 따라 상황에 따라 달라지는 전화와 입력에 음향 상태를 나타내는 기호가있는 트랜스 듀서입니다. 이 경우 H (또는 HCLG) 입력의 기호는 음향 상태 (용어에서는 pdf-id)가 아니라 전환 ID라고합니다 (TransitionModel에서 사용되는 정수 식별자 참조). 전환 ID는 pdf-id와 전화를 포함한 다른 정보를 인코딩합니다. 각 transition-id는 pdf-id에 매핑 될 수 있습니다. 우리가 만든 H 변환기는 자체 루프를 인코딩하지 않습니다. 이들은 나중에 별도의 프로그램으로 추가됩니다. H 변환기의 상태는 초기 및 최종 상태이며,이 상태에서 ilabel_info 객체 (ilabels 파일, 위의 ilabels 파일)에서 0 번째 항목을 제외한 모든 항목에 대한 전환이 있습니다. 상황에 따른 전화의 전환은 해당 HMM의 구조로 이동 한 다음 (자체 루프 없음) 시작 상태로 돌아갑니다. 일반적인 토폴로지의 경우 HMM의 이러한 구조는 3 개의 호의 선형 시퀀스 일뿐입니다. H는 또한 각 명확화 심볼 (# -1, # 0, # 1, # 2, # 3 등)에 대한 초기 상태에 자체 루프를 가지고 있습니다.

 

H 변환기를 만드는 스크립트 섹션 (이 시점에서 자체 루프가 없기 때문에 Ha라고 함)은 다음과 같습니다.

 

make-h-transducer --disambig-syms-out=$dir/disambig_tstate.list \
              --transition-scale=1.0 $dir/ilabels.remapped $tree $model > $dir/Ha.fst

 

전환 스케일을 설정하는 옵션 인수가 있습니다. 현재 교육 스크립트에서이 척도는 1.0입니다. 이 척도는 자체 루프 확률과 관련이없는 전환 부분에만 영향을 미치며 일반 토폴로지 (Bakis 모델)에서는 전혀 영향을 미치지 않습니다. 자세한 내용은 전환 및 음향 확률 조정을 참조하십시오. FST 외에도 프로그램은 명확성 기호 목록을 작성합니다.이 기호는 나중에 제거해야합니다.

 

Making HCLG

최종 그래프 HCLG를 만드는 첫 번째 단계는 자체 루프가없는 HCLG를 만드는 것입니다. 현재 스크립트의 명령은 다음과 같습니다.

 

fsttablecompose $dir/Ha.fst $dir/CLG2.fst | \
fstdeterminizestar --use-log=true | \
fstrmsymbols $dir/disambig_tstate.list | \
fstrmepslocal | fstminimizeencoded > $dir/HCLGa.fst

 

여기에서 CLG2.fst는 심볼 세트가 줄어든 CLG 버전입니다 (HTK 용어에서 "논리"트리폰). 최소화하기 전에 명확성 기호와 제거하기 쉬운 엡실론 (엡실론 제거 참조)을 제거합니다. 우리의 최소화 알고리즘은 기호와 가중치를 누르는 것을 피하고 (따라서 확률론을 보존 함) 비 결정적 입력을 받아들입니다 (최소화 참조).

 

Adding self-loops to HCLG

HCLG에 자체 루프 추가는 다음 명령으로 수행됩니다.

 

add-self-loops --self-loop-scale=0.1 \
               --reorder=true $model < $dir/HCLGa.fst > $dir/HCLG.fst

0.1의 자체 루프 스케일이 적용되는 방법에 대한 설명은 전환 및 음향 확률 스케일링을 참조하십시오 (비 자체 루프 확률에도 영향을 미침). "재정렬"옵션에 대한 설명은 전환 순서 변경을 참조하십시오. "재주문"옵션은 디코딩 속도를 증가 시키지만 kaldi 디코더와 호환되지 않습니다. 자체 루프 추가 프로그램은 자체 루프를 추가하지 않습니다. 자체 루프를 일관된 방식으로 추가 할 수 있도록 상태를 복제하고 엡실론 전환을 추가해야 할 수도 있습니다. 이 문제는 재정렬 전환에서 약간 더 자세히 설명됩니다. 이것은 확률론을 보존하지 않는 유일한 그래프 생성 단계입니다. 자체 루프 스케일이 1이 아니므로이를 보존하지 않습니다. 따라서 fstisstochastic 프로그램은 모든 G.fst, LG.fst, CLG.fst 및 HCLGa.fst에 대해 동일한 출력을 제공해야하지만 HCLG.fst에 대해서는 그렇지 않아야합니다. . add-self-loops 단계 후에 다시 결정하지 않습니다. 명확성 기호를 이미 제거했기 때문에 실패합니다. 어쨌든, 이것은 느리고 우리는이 시점에서 결정하고 최소화함으로써 더 이상 얻을 것이 없다고 생각합니다.

FST와 ASR에 대한 내용은 "Speech Recognition with Weighted Finite-State Transducers" by Mohri, Pereira and Riley (in Springer Handbook on SpeechProcessing and Speech Communication, 2008) 을 참조. 이곳에 Kaldi가 사용하는 일반적인 접근 방식이 설명되어 있지만, 구체적으로 disambiguation symbols를 처리하는 방법과 weight-pushing을 처리하는 방법과 관련하여 일부 세부 사항이 다르다.

 

Overview of graph creation

 

디코딩 그래프 생성을위한 전반적인 overview는 그래프 HCLG = H o C o L o G를 구성하는 것이다. 각각의 심볼의 의미는 다음과 같다.

 

G는 grammar 또는 language model을 인코딩하는 acceptor (즉, 입력 및 출력 기호가 동일함)
L은 lexicon 입니다. output symbols 는 단어이고 input symbols 는 phones
C는 context-dependent 을 나타냄 : 
	출력 심볼은 phones 이고 
    입력 심볼은 context-dependent phones , 
    즉 N phones 의 windows 를 나타내고; 발음 문맥 창을 참조.
H는 HMM 정의를 포함한다. 
	출력 기호는 상황에 따른 phones 를 나타내며 
    입력 기호는 전이 ID이며 pdf-id 및 기타 정보를 인코딩한다 
    (TransitionModel에서 사용되는 정수 식별자 참조).

 

 

 

세부적인 내용은 밑에서 계속해서 설명한다. 출력을 결정하고 최소화하기 위해 HCLG를 결정하려면 disambiguation symbol를 삽입해야한다.

 

또한 HCLG가 가능한 한 stochastic 이길 원하고, 이것은 기존 레시피에선 "weight-pushing" 동작으로 수행된다. stochacity를 보장하기위한 Kaldi의 접근 방식은 다르며, no graph creation step "takes away" stochasticity보장한다. 자세한 내용은 이곳에서 확인 (Preserving stochasticity and testing it)

 

한 줄로 요약하면, 다음과 같을 것이다.

 

HCLG = asl(min(rds(det(H' o min(det(C o min(det(L o G))))))))

where asl=="add-self-loops",
      rds=="remove-disambiguation-symbols", 
      H' == H without the self-loops

 

 

 

weight-pushing 는 레시피의 일부가 아니다. 대신 우리는 G가 stochastic이라면 graph creation sate 가 확률적 결과를 막지 않도록하는 것을 목표로한다. 물론, G는 backoff 기능이있는 Arpa 언어 모델이 FST로 표현되는 방식 때문에, 일반적으로 상당히 stochastic이지 않지만, 적어도 우리의 접근 방식은 non-stochasticity "stays put" 를 유지하고 시작했을 때보다 더 나빠지지 않도록한다. 접근 방식은 weight-pushing 작업이 실패하거나 상황을 악화시키는 위험을 피한다.

 

 

Disambiguation symbols

 

Disambiguation symbols lexicon에서,phonemene sequences의 끝에 삽입되는 기호 #1, #2, #3 같은 것들이다.

1) phonemene sequences가 lexicon에서 다른 phonemene sequences의 prefix (접두어) 이거나

2) 둘 이상의 단어로 나타나는 경우, 뒤에 이 기호 중 하나를 추가해야한다.

-> 이 Disambiguation symbols은 the product (L o G)가 determinizable위해 필요하다.

 

3) LM model G의 backoff arcs 에 symbol #0 를 놓는다. 이를 통해 determinizable알고리즘이 epsilons을 제거하기 때문에 epsilons을 제거한 후 G를 결정할 수 있다(determinizable).

4) 우리는 utterance의 시작 부분에서 symbols을 출력하기 전에 context FST (C)의 왼쪽에 나타나는 epsilons대신에 symbol #1을 놓는다. empty phonetic representation이 있는 단어 (예 : 문장 기호 <s> 및 </ s>의 시작과 끝)가 있을 때 발생하는, 다소 작은 문제를 해결하는 데 필요하다.

 

 

다음은 Graph compilation의 중간 단계 (예 : LG, CLG, HCLG)가 결정 가능(determinizable)하다는 것을 공식적으로 증명하는 방법에 대한 overview이다. 이는 레시피가 절대 실패하지 않도록하는 데 중요하다.

 

일반적인 설정은 다음과 같다.

1) G를 결정할 수 있어야 한다. 그렇기 때문에 #0 기호가 필요하다 (G는 실제로 결정적이므로 결정 가능하다). 2) 그런 다음 L을 결정 가능한 G에 대해 L o G를 결정할 수 있도록 한다. [G 대신 오른쪽에 L o G가있는 C도 마찬가지입니다.] 여전히 이론에 대한 많은 세부 사항이 있지만, L이 다음과 같은 두 가지 property을 갖는 것으로 충분하다고 생각한다.

 

1) 

은 작동해야만 한다

- equivalently: any input-sequence on L must induce a unique output-sequence

- equivalently: for any linear acceptor A, A o L is a linear transducer or empty.

2) L has the twins property, i.e. there are no two states reachable with the same input-symbol sequence, that each have a cycle with the same input sequence but different weight or output sequence.

 

C Transducer 에도 동일하게 적용된다. 우리는 스크립트와 프로그램이 현재 생성하는 변환기는 이러한 property를 가지고 있다.

 


The ContextFst Object

 

ContextFst 객체 (C)는 context-dependent phones 에서 context-independent phones로의 transducer를 나타내는 동적으로 생성 된 FST object 이다. 이 object의 목적은 context 에서 가능한 모든 phones를 열거 해야하는 것을 피하기 위한 것이다. context 에서 가능한 모든 phones를 열거 해야하는 것은 Context width (N) 또는 phones의 개수가 클 때 어려울 수 있다.

 

생성자 ContextFst::ContextFst는 context-width (N)과 central-position (P)를 필요하다(triphone 시스템에 각각 N=3과 P=1). (추가설명:Phonetic context windows)

 

또한 모든 phones을 본 후 FST에서 N-P-1을 출력하는 특수 기호 인 "subsequential symbol"(위에서 '$'라고 함)의 integer ID가 필요하다 (이로 인해 context FST is output-deterministic이 보장됨). 이 외에도 integer id's of the phones및 disambiguation symbol 목록이 필요하다.

 

ContextFst의 출력 측 vocabulary set of phones및 disambiguation symbols와 subsequential symbol로 구성된다.

 

입력측의 vocabulary는 동적으로 생성되며 (사용되지 않는 epsilon제외) phones in context, disambiguation symbols 그리고 "전통적인 레시피"에서 "#에서 엡실론을 대신하는 #-1로 쓰는 특수 기호(다른 disambiguation symbol로 취급(예 : 엡실론 제거 등 선호하는 의미에서 결정성을 보장하는 데 필요함) 에 해당한다. The vocabulary on the input side is dynamically generated and (apart from epsilon, which is not used), corresponds to phones in context, disambiguation symbols, and a special symbol that we write as #-1 that takes the place of epsilon in the "traditional recipe", but which we treat as any other disambiguation symbol (it is necessary to ensure determinizability in the sense we prefer, i.e. with epsilon removal).

 

 

전통적인 레시피에서와 같이 subsequential symbol'$'는 입력측에 해당하는 것이 없다. 입력측에서 disambiguation symbols에 대응하는 symbol id's는, 대응하는 심볼에 대한 출력측에서 사용되는 integer 식별자와 반드시 동일하지는 않다.

 

ContextFst 객체에는 std :: vector <std :: vector <int32> 유형의 객체에 대한 참조를 반환하는 함수 ILabelInfo()가 있으며, 이를 통해 사용자는 입력 측에서 각 심볼의 "의미"를 계산할 수 있다. 이 객체의 올바른 해석은 The ilabel_info object에 자세히 설명되어 있다.

 

 

ContextFst와 관련된 composition알고리즘에 사용하기위한 ContextMatcher라는 특수한 "Matcher" object가있다 (Matcher는 OpenFst의 composition알고리즘이 arc lookup에 사용하는 것이다. ContextMatcher는 필요한 것보다 더 많은 상태의 할당을 피함으로써 ContextFst 객체의 사용을 보다 효율적으로 만든다 (문제는 normal matcher를 사용하면 state에서 arc를 원할 때마다 대상을 할당해야한다는 것이다) 해당 상태에서 다른 모든 아크의 상태).

 

composition에 대한 left hand argument가 ContxtFst 유형 인 경우 FST 컴포지션을 수행하는 관련 함수 ComposeContextFst ()가 있고, Matcher를 사용한다. ComposeContext () 함수도 있는데, 이 함수는 비슷하지만 ContextFst 객체 자체를 만든다.


Avoiding weight pushing

 

weight-pushing는 각 상태의 arc 확률이 적절한 의미로 "sum to one(합계)"되는 것을 보장하는 FST operation이다. Kaldi는 전통적인 레시피와는 약간 다른 방식으로 weight-pushing 문제를 다룬다. log semiring(반올림)에서weight-pushing는 검색 속도를 높이는 데 도움이 될 수 있다. 그러나 경우에 따라 weight-pushing는 나쁜 영향을 줄 수 있다. 문제는 FST로 표현 될 때 통계 언어모델이 일반적으로 ""add up to more than one (하나 이상으로 합산)"하기 때문에 일부 단어는 직접적으로 backoff arcs를 통해 두 번 계산되기 때문이다.

 

우리는 절대로 pushing weights하지 않기로 했고, 대신 다른 방식으로 처리한다. 첫째, Definition: 우리는 weight가 1에 해당하는 "stochastic"FST를 호출하고 reader는 "log semiring"에 대해 이야기하고 있다고 가정 한다. "sum to one"를 의미하며 "take the max" 이 아니다.

 

그래프 생성의 각 단계는 이전 단계가 stochastic이라면 다음 단계가 stochastic이라는 특성을 갖는다. 즉, G가 stochastic이라면 LG는 stochastic이다. LG가 stochastic이라면 det(LG)는 stochastic이다. det(LG)가 stochastic이면 min(det(LG))은 stochastic등이다. 이것은 각각의 개별 작업이 적절한 의미에서 "preserve stochasticity"해야한다는 것을 의미한다. 예를 들어, 예를 들어 weight-push 알고리즘을 시도해 볼 수 있으며 원래 G fst가 둘 이상으로 합산되어 실패한 것으로 판단되면 실패를 내뱉는다.

 

우리는 더 강력한 의미로 stochasticity을 유지하려고 한다. 즉, G에 대해 모든 states에 대한 최소값과 최대값을 먼저 측정한다 (arc probabilities plus final-prob). 이것이 우리의 프로그램 "fstisstochastic"이 수행하는 일이다. G가 stochastic이라면,이 두 숫자는 모두 1이 된다 (실제로 로그 공간에서 작동하기 때문에 실제로 프로그램에서 0을 보게 될 것이다. 이것이 "log semiring" 이다). 우리는 다음과 같은 의미에서 확률을 유지하려고 한다.이 최소값과 최대 값은 "get worse" 않는다. 즉, 그들은 결코 1에서 더 멀어지지 않는다. 실제로 이것은 "local" 방식으로 확률을 유지하는 알고리즘이있을 때 자연스럽게 일어난다. stochasticity을 보존하기 위해 필요한 다음과 같은 다양한 알고리즘이 있다.

 

더보기

Minimization
Determinization
Epsilon removal

Composition (with particular FSTs on the left) There are also one or two minor algorithms that need to preserve stochasticity, like adding a subsequential-symbol loop. Minimization naturally preserves stochasticity, as long as we don't do any weight pushing as part of it (we use our program "fstminimizeencoded" which does minimization without weight pushing). Determinization preserves stochasticity as long as we do it in the same semiring that we want to preserve stochasticity in (this means the log semiring; this is why we use our program fstdeterminizestar with the option –determinize-in-log=true). Regarding epsilon removal: firstly, we have our own version of epsilon removal "RemoveEpsLocal()" (fstrmepslocal), which doesn't guarantee to remove all epsilons but does guarantee to never "blow up". This algorithm is unusual among FST algorithms in that, to to what we need it to do and preserve stochasticity, it needs to "keep track of" two semirings at the same time. That is, if it is to preserve equivalence in the tropical semiring and stochasticity in the log semiring, which is what we need in practice, it actually has to "know about" both semirings simultaneously. This seems to be an edge case where the "semiring" concept somewhat breaks down. Composition on the left with the lexicon L, the context FST C and the H tranducer (which encodes the HMM structure) all have to preserve stochasticity. Let's discuss this the abstract: we ask, when composing A o B, what are sufficient properties that A must have so that A o B will be stochastic whenever B is stochastic? We believe these properties are:

- For any symbol sequence that can appear on the input of B, the inverse of A must accept that sequence (i.e. it must be possible for A to output that sequence), and:

- For any such symbol sequence (say, S), if we compose A with an unweighted linear FST with S on its input, the result will be stochastic.

 

These properties are true of C, L and H, at least if everything is properly normalized (i.e. if the lexicon weights sum to one for any given word, and if the HMMs in H are properly normalized and we don't use a probability scale). However, in practice in our graph creation recipes we use a probability scale on the transition probabilities in the HMMs (similar to the acoustic scale). This means that the very last stages of graph creation typically don't preserve stochasticity. Also, if we are using a statistical language model, G will typically not be stochastic in the first place. What we do in this case is we measure at the start how much it "deviates from stochasticity" (using the program fstisstochastic), and during subsequent graph creation stages (except for the very last one) we verify that the non-stochasticity does not "get worse" than it was at the beginning.

 


[1] https://kaldi-asr.org/doc/graph.html

 

앞서 메모한 #RNN-T Beam search [1] 글에 이어, 최근 facebook AI 팀에서 ICASSP 2020에 제출한 것처럼 보이는 아카이브에 올린 [2] 논문에 대해서 메모하고자 한다. [2]에서는 Latency Controlled RNN과 improved RNNT Beam Search를 제안했지만, 이 글은 후자인 RNNT improved Beam Search 부분만을 위한 글이다.

 

먼저 간단하게 기본 beam search for RNNT를 리마인드 해보면 이렇다. RNN-T에서는 다음 joiner call을 할 때, 다음 time frame t+1로 넘어갈 것인지, 같은 time frame t에서의 output units을 더 emit할 것인지 결정하기 위해서, output units은 특별한 symbol인 blank symbol을 포함한다. 매번 joiner call 마다, 1) 우리는 time axis (t) 에서 다음 audio frame t+1로 넘어가거나, 2) hypothesis를 업데이트하고 같은 time frame t 에서 계속해서 symbols를 emit 할 수 있다. 전자는 Joiner가 blank symbol을 가장 큰 확률로 emit할 때이고, 후자는 blank가 아닌 chracter들 중 하나를 가장 큰 확률로 outputting 할 때이다. 기존 RNNT Beam Search는 다음과 같다.

사진 삭제

RNN-T Beam Search [3]

일반적으로 beam search를 computationally efficient하게 개선하기 위해 hypothesis pruning을 많이 시도한다. 이 논문의 beam search의 목표도 그러하다. RNNT beam search에서 hypothesis set A의 hypothesis들의 확장을 제한한다는 것이 이 논문 beam search 알고리즘의 핵심이다. pesudo code는 다음과 같다.

대표사진 삭제

Improved RNN-T Beam Search [2]

 

 

간단하다. 두 가지만 확인하면 된다.

 

1) state_beam을 도입했다. log space에서 hypothesis setB의 best hypothesis보다 (state_beam + hypothesis setA의 best hypothesis)이 더 확률이 낮은 경우, "hypothesis set B의 이미 존재하는 hypos"들이, "hypothesis setA 로부터 확장될 hypothesises들"보다 이미 더욱 좋은 hypothesises이라고 가정해서 while loop 를 끝내 버려서 그 때까지의 hypothesis로 결과를 낸다.

 

2) 또한 A에 추가되는 hypothesises의 개수를 제한하는 expand_beam을 도입했다. hypothesis set B가, hypothesis set A에서 가장 가능성있는 hypothesis 보다 probability가 높은 W(beam width) 개의 hypothesis를 갖자마자 beam search criterion은 시간 t에서 충족되며, 프레임 t + 1 처리를 시작할 수 있다.y_t, h를 생성하는 (t, h)에서의 Joiner 호출의 경우, 먼저 Hypothesis set A 와 B 에서의 최고의 확률 값 (non-blank output unit (yt, h) 중에서 최고의 확률과, 최고의 확률)을 계산한다. 그 후, log (best prob)보다 log (Pr (k | y ∗, t)가 더 높은 output, k만 추출하여 hypothesis set A에 추가한다.

 

** hypothesis set A는 여전히 시간 t에 대해 고려되고 있는 hypothesis를 포함하고 있으며, hypothesis set B는 시간 t에서 이미 blank symbol을 emit했으며, 현재 시간 프레임인 t+1에 있는 hypothesis를 포함한다.

 


코드를 작성해보면 다음과 같다.

 

 

def recognize_beam_facebook(self, h, recog_args, rnnlm=None, state_beam, expand_beam):
    """facebook Beam search implementation for rnn-transducer.
    Args:
        h (torch.Tensor): encoder hidden state sequences (maxlen_in, Henc)
        recog_args (Namespace): argument Namespace containing options
        rnnlm (torch.nn.Module): language model module
        state_beam: ...
        expand_beam: ...
    Returns:
        nbest_hyps (list of dicts): n-best decoding results
    """
    beam = recog_args.beam_size
    k_range = min(beam, self.odim)
    nbest = recog_args.nbest
    normscore = recog_args.score_norm_transducer

    B_hyps = [{'score': 0.0, 'yseq': [self.blank], 'cache': None}]

    for i, hi in enumerate(h):
        A_hyps = B_hyps
        B_hyps = []

        while True:
            new_hyp = max(A_hyps, key=lambda x: x['score'])
            a_best_hyp = max(A_hyps, key=lambda x: x['score'])
            b_best_hyp = max(B_hyps, key=lambda x: x['score'])
            
            if log(b_best_hyp) >= state_beam + log(a_best_hyp):
                break
            
            A_hyps.remove(new_hyp)

            ys = to_device(self, torch.tensor(new_hyp['yseq']).unsqueeze(0))
            ys_mask = to_device(self, subsequent_mask(len(new_hyp['yseq'])).unsqueeze(0))
            y, c = self.forward_one_step(ys, ys_mask, new_hyp['cache'])

            ytu = torch.log_softmax(self.joint(hi, y[0]), dim=0)

            best_prob = max(ytu[1:])
            
            for k in six.moves.range(self.odim):

                if k == self.blank:
                    beam_hyp = {'score': new_hyp['score'] + float(ytu[k]),
                            'yseq': new_hyp['yseq'][:],
                            'cache': new_hyp['cache']}

                    B_hyps.append(beam_hyp)
    
                else:
                    if float(ytu[k]) >= log(best_prob) - expand_beam :
                        beam_hyp = {'score': new_hyp['score'] + float(ytu[k]),
                            'yseq': new_hyp['yseq'][:],
                            'cache': new_hyp['cache']}

                        beam_hyp['yseq'].append(int(k))
                        beam_hyp['cache'] = c

                        A_hyps.append(beam_hyp)

            if len(B_hyps) >= k_range: // beam_size (W)
                break

    if normscore:
        nbest_hyps = sorted(
            B_hyps, key=lambda x: x['score'] / len(x['yseq']), reverse=True)[:nbest]
    else:
        nbest_hyps = sorted(
            B_hyps, key=lambda x: x['score'], reverse=True)[:nbest]

    return nbest_hyps

 


[1] https://sequencedata.tistory.com/3?category=1129285

[2] M. Jain, al "RNN-T FOR LATENCY CONTROLLED ASR WITH IMPROVED BEAM SEARCH", 2020

[3] Alex Graves, "Sequence Transduction with Recurrent Neural Networks", 2012

 

 

몇 년 전, Alex Graves가 길이가 다른 input/output sequences 를 잘 mapping 할 수 있는 RNN-T 모델을 Sequence Transduction with RNN [1] 논문에서 제안했다. 여러 가지 sequence transduction 문제 중 ASR 문제에 집중을 했는데, 구글이 작년에 이 모델로 모바일 상에서 steamable 음성인식 성과를 소개해서인지, 최근들어 이 모델에 대한 관심이 급격하게 높아졌다. ASR 문제에서 input sequence는 audio signal, output sequence는 텍스트이다. RNN-T에 대한 설명은 생략하고, 이 글의 주제인 beam search for RNN-T 알고리즘에 대해서 메모를 남겨보고자 한다. 이 알고리즘은 [1] 논문에서 처음 제안되었다. pseudo code는 다음과 같다.

 

대표사진 삭제

사진 설명을 입력하세요.

 

 

RNN-T 모델을 위한 beam search를 위해 우선 time t에서 hypothesis h 는 frame embedding a_t 와 text embedding t_h 를 가진다고 가정한다. 이 두 embedding들은 결합되고 Joiner를 태워서 y_t,h output units(eg, 256) 에 대한 확률을 생성한다. while 문 안에 있는 for문에서의 y는 한 시점의 output units 이다.

 

RNN-T의 output units 은 우리가 모델링하고자 하는 output character들 외에 특별한 symbol 인 blank (∅) 가 존재한다. 이 blank symbol 은 디코딩 진행시, lattice 상에서 t 시점에 있을 때, 다음 time frame인 t+1 으로 진행할 것인지 혹은 t 시점에서의 output unit 과 같은 문자를 emit할 것인지 결정하기 위해 존재한다.

 

Beam search는 두 가지 hypothesis set A, B 를 사용하여 수행이 된다. 이것은 t + 1로 이동되는 최소 W (beam size) hypothesis가 t에서 여전히 생성 될 수있는 것보다 높은 확률을 갖도록하기 위함이다.

 

알고리즘을 보면 크게 세 부분으로 나눌 수 있다.

 

1. 첫번째는 특정시점까지 찾아진 hypothesis set A에 포함된 모든 hypothesis에 대한 probability를 그 hypothesis 의 적절한 prefix의 set을 사용하여 계산해 내는, 첫번째 for-loop에 대한 부분이다. 모든 time-step마다 그 시점까지 찾아진 hypothesis set B(=A) 에 포함된 모든 hypothesis에 대한 확률을 계산해낸다.

 

2. 두번째는 Beam search 를 진행하는 중에, hypothesis set A에서 최고 확률이 높은 hypothesis를 선택하고 blank 또는 non-blank symbol 로 확장하는 부분이다. while 를 돌며 Joiner(softmax)를 태워서 나온 y_t,h output units(eg, 256) 에서 모든 dimension output(probability)에 대해서, 기존 score(prob)에 곱한 score(prob)를 업데이트 하고, 해당 chracter(정확히는 index)를 append 시킨 새로운 hypothesis를 hypothesis set A 혹은 B에 append 한다. 이 때, blank에 해당하는 output dimension에 대해서는 score 계산 후, hypothesis set B에 append 하고, 다른 dimension에 해당하는 값(다른 캐릭터) 들에 대해서는 socre 계산 후, hypothesis set A에 append한다. While 문은 beam width 만큼 hypothesis가 hypothesis set B에 존재할 때까지 진행된다. 다시 말하면, blank가 마지막에 사용되는 expansion hypothesis는 를 hypo set B에 삽입된다. 한편, blank가 사용되지 않는 다른 모든 symbols을 사용하는 expansion hypothesis들은 hypothesis set A에 다시 삽입되어 t에서 확장 된 hypothesis set A가 계속해서 재 정의 된다.

 

3. return 할 때, hypothesis set B에 속한 W 개 미만의 hypothesis 중에 "각각의 hypotesis의 확률 값을 chracter들의 숫자로 나눈 최종 score"을 비교하여 가장 높은 score 값이 되는 hypothesis를 return 한다.

 

** 참고로 hypothesis set A, B에 저장 할 때는 {score(probability), character sequence(hypothesis)} 가 사전 형태로 함께 저장된다는 것을 함께 생각해야, 헷갈리지 않는다.


espnet에 구현되어 있는 beam search 코드[2]이다. 참고하면 더 이해하기 편하다. pseudo code와는 다르게 코드 상에선 blank output 에 대해서 해당 hypothesis를 hypothesis set B 에 append 하는 부분을 for 문 안으로 넣어놓았다.

 

 

def recognize_beam(self, h, recog_args, rnnlm=None):
    """Beam search implementation for transformer-transducer.
    Args:
        h (torch.Tensor): encoder hidden state sequences (maxlen_in, Henc)
        recog_args (Namespace): argument Namespace containing options
        rnnlm (torch.nn.Module): language model module
    Returns:
        nbest_hyps (list of dicts): n-best decoding results
    """
    beam = recog_args.beam_size
    k_range = min(beam, self.odim)
    nbest = recog_args.nbest
    normscore = recog_args.score_norm_transducer

    B_hyps = [{'score': 0.0, 'yseq': [self.blank], 'cache': None}]

    for i, hi in enumerate(h):
        A_hyps = B_hyps
        B_hyps = []

        while True:
            new_hyp = max(A_hyps, key=lambda x: x['score'])
            A_hyps.remove(new_hyp)

            ys = to_device(self, torch.tensor(new_hyp['yseq']).unsqueeze(0))
            ys_mask = to_device(self, subsequent_mask(len(new_hyp['yseq'])).unsqueeze(0))
            y, c = self.forward_one_step(ys, ys_mask, new_hyp['cache'])

            ytu = torch.log_softmax(self.joint(hi, y[0]), dim=0)

            for k in six.moves.range(self.odim):
                beam_hyp = {'score': new_hyp['score'] + float(ytu[k]),
                            'yseq': new_hyp['yseq'][:],
                            'cache': new_hyp['cache']}

                if k == self.blank:
                    B_hyps.append(beam_hyp)
                else:
                    beam_hyp['yseq'].append(int(k))
                    beam_hyp['cache'] = c

                    A_hyps.append(beam_hyp)

            if len(B_hyps) >= k_range: // beam_size (W)
                break

    if normscore:
        nbest_hyps = sorted(
            B_hyps, key=lambda x: x['score'] / len(x['yseq']), reverse=True)[:nbest]
    else:
        nbest_hyps = sorted(
            B_hyps, key=lambda x: x['score'], reverse=True)[:nbest]

    return nbest_hyps

 


[1] Alex Graves, "Sequence Transduction with Recurrent Neural Networks", 2012

[2] ESPnet; https://github.com/espnet/espnet/blob/master/espnet/nets/pytorch_backend/transducer/transformer_decoder.py

 

 

+ Recent posts