BETA

音声認識サービスの精度評価をしたかった その2

投稿日:2018-11-26
最終更新:2019-04-18

はじめに / Introduction

この記事はその1の続きです。
背景を知りたい方はその1をどうぞ。

This page picks up where I left off.
Please read it if you want to know the background on this.

評価方法 / How to evaluate

ja-JP

前提条件・評価項目・コストなどを考慮した結果、個人的な興味によりWord Error Rate(以下、WER)を指標値として採用しました。
概要を説明するとこんな感じ。

  • 比較対象の間違えた単語数を数えます
    • 間違え方はInsert:挿入 / Delete:削除 / Substitute:置換 に分けられます
  • 正解の全単語数で割ります
  • 小さい程精度が高いです

例えば、以下の2文を比べたときはWER = ((Ins = 1) + (Sub = 2) / 4 = 0.25 となります。

  • 正解: This is a pen.
  • 比較対象: That is an apple pen.

なお、Ins / Del / Sub の数は一意に定まらないことがあります。
詳細は参考リンクにお任せしますが、特徴としては重み付けが不要である点や意味の類似度には使えない点があると思います。
この記事では備忘録兼幅出しとして、参考リンクより基礎的な情報をメインに記載します。

WERを自分で実装しようとしたとき、レーベンシュタイン距離(= 編集距離)を計算することになります。
編集距離はOCRなどのエラー測定などで使われるようで、参考リンクでも単語内の文字間違いに関して書かれています。しかし、これを文章に置き換えると、間違えた単語数 = 編集距離であり、(編集距離)/(正解の全単語数) = WER となります。

ここから数学的な話に近づいていきます。
編集距離を計算するときの方策は動的計画法(以下、DP)で行うのが簡単です。
これは、正解の単語が先頭からi番目だとしたとき、編集距離LD[i]はLD[i-1]が分かっていれば以下のように書けるからです。

  • 0番目: LD[0] = 0 (∵ 正解も比較対象も単語がない)
  • 比較対象が正しいとき: LD[i] = LD[i-1]
  • 比較対象が正しくないとき: LD[i] = LD[i-1] + n(1とは限らない)

なお、nは比較対象がその時に取り得る単語を調べればわかるので、正解と比較対象の2次元配列で計算できます。
なんやかんやして、ガリガリ書くとこうなりました。
参考リンクでは図示してくださっているので、より分かりやすいかもです。

ちなみに。私のコードでは2次元配列を全探索しているので計算量はO(ij)ですが、diffのアルゴリズムを参考にすると計算量を削減できるようです。

en-US

I decided to use Word Error Rate(WER) as a metric to evaluate STT services chosen in the previous article because of evaluating criteria, prerequisite, costs, and especially my curiosity.
Very simple overviews of WER is in below bullets.

  • Count errors in comparison data.
    • Errors are separated Insert, Delete, and Substitute.
  • Calculate (Counts of all errors) / (Counts of all words in the answer)
  • The smaller WER the higher accuracy.

For example, WER = ((Ins = 1) + (Sub = 2) / 4 = 0.25 comparing 2 sentences as follows.

  • Answer: This is a pen.
  • Comparison: That is an apple pen.

By the way, maybe Ins, Del, and Sub are not determined uniquely (please read references in detail).
We don't have to set weight (= parameter) and can't use for similarity evaluation of meanings are main features of WER.
I will write more basic information in this article than references as a memo.

We have to calculate Levenstein Distance(LD) when we code WER ourselves.
It is often used error evaluation of characters in a word like OCR. In references, they deal with character.
However, we deal with LD as Counts of all errors if we replace character error in a word with words error in texts, and then LD / (Counts of all words in an answer) = WER.

I write about an algorithm like mathematics.
Dynamic Programming(DP) is one of the most simple ways to calculate LD.
Now, we think that a target word is i-th from the start of the answer.
LD[i] can be defined in below if we know LD[i -1] and LD[0] = 0 because of neither texts of answer nor comparison.

  • If comparison is correct: LD[i] = LD[i-1]
  • If comparison is wrong: LD[i] = LD[i-1] + n (more than 1)

So we can calculate to use a 2D array because n is decided by possible comparison words when an answer word is i-th.
This is my LD code.
I think references are much easy to comprehension because of figures.

P.S.
Complexity is O(i * j) = O(n^2) in my code because of searching full space.
Perhaps, we can reduce complexity as follow "Diff" algorithm.

参考リンク / References

次の記事 / Next

https://tmyoas.qrunch.io/entries/xhNv0b4P2V60jDer

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

@tmyoasの技術ブログ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!