Використання триграм для корекції результатів розпізнавання


На малюнку зображено схема з 8 можливих триграм, взята з книги [1]

Природні мови можуть бути охарактеризовані розподілом частот зустрічальності своїх елементів, таких як слова, окремі букви або послідовності букв (N-грами). Формально N-граммой називається рядок N символів, що належать деякому алфавіту, що складається з кінцевого числа символів. Про теоретичних і прикладних питаннях застосування апарату N-грам для автоматичної корекції тексту можна прочитати в роботі [2].


У даній статті ми будемо розглядати тільки алфавіт, що складається з букв російської мови, далі ми розповімо про можливості застосування триграм (послідовностей з трьох символів) для постобробки (корекції з метою зменшення помилок) результатів розпізнавання російськомовних документів. В якості механізму розпізнавання виступали згорткові нейронні мережі.


1. Опис моделі триграми
Модель триграм складається з набору (словника) трійок символів {gі1, gі2, gі3} і приписаного їм ваги wі. Триграми впорядковані по вазі, більшу вагу означає більшу частоту зустрічальності триграми у природній мові, точніше в деякому корпусі текстів на природній мові.


В ідеальному випадку під вагою  триграми ми розуміємо ймовірність її зустрічальності у природній мові. Зрозуміло, на різних вибірках текстів природної мови ми можемо отримувати розрізняються ваги триграм. В якості прикладу можна розглянути тексти класичної літератури і таблиці, що містять абревіатури виробів, очевидно, що для цих випадків зустрічальність  триграм буде сильно відрізнятися. У той же самий час витяг триграм з корпусу однорідних слів, дозволяє отримати стабільні оцінки ваг триграм.

Ми розповімо про видаляння триграм з великих наборів прізвищ, імен та по батькові громадян Російської Федерації та про використання знайдених триграм для корекції результатів розпізнавання полів «Прізвище», «Ім'я» та «по Батькові» в паспорті громадянина Російської Федерації. Раніше ми розповідали про своїх програмних рішеннях для розпізнавання паспорта [3, 4], в яких можуть бути застосовані результати даної статті.

У нашому розпорядженні були три корпуси слів: словники прізвищ, імен та по батькові громадян Російської Федерації. З кожного з корпусів були витягнуті триграми. Для кожного слова {c1,c2,...,cn} в якому cі–символ російської мови (великі та малі літери не розрізнялися) на початок і кінець слова додавалися два фіктивних символуcF:  {cF, cF, c1, c2, ..., cn
cF, cF}. Це було зроблено для того, щоб кожному з символів cі можна було зіставити триграми <cі-2, cі-1, cі> <cіcі+1, cі+2>, наприклад, c1 можна зіставити триграму <cF, cF, c1>. Далі будемо розглядати слова з доданими до алфавіт символами cF. Для кожної трійки символів <g1, g2, g3>ми підрахували кількість примірників цієї трійки в усіх словах корпусу, отнормировали його на число можливих триграм і взяли нормоване значення в якості ваги (сума  нормованих ваг θ(g1, g2, g3), дорівнює одиниці).

Використаний великий корпус прізвищ (понад 1 500 000 прізвищ у випадковому порядку, з – них різних близько 183 000 різних прізвищ), зібраних раніше нами з відкритих джерел, дозволив побудувати словник триграм з вагами, які мало залежать від розміру вибірки слів. Для прикладу розглянемо часто зустрічають у прізвищах триграми

{О, О, О}, {До, О, О}, {Н, О, О}, {І, Н, А}, {О, О, О},

ваги яких ми обчислимо на вибірках різного обсягу, всі вибірки виймаються з корпусу прізвищ. На малюнку 1 представлені графіки залежності ваг цих триграм в залежності від обсягу вибірки, які характеризують стабільність визначення ваги зазначених триграм при обсязі вибірки, що перевищує 50 000 слів.

Звернемо увагу на те, що найпоширенішою триграм для корпусу прізвищ є {А, cF,
cF} і {В, А, cF} c вагами 0.044 і 0.033, відповідно.



Малюнок 1. Графіки прикладів залежності ваг триграм в залежності від обсягу вибірки

Аналогічно були побудовані словники триграм для імен та по батькові, у них при використання вибірок слів великого обсягу ваги часто зустрічаються триграм також обчислюються стабільно.

2. Опис результатів розпізнавання
Результати розпізнавання символу представлені альтернативами (cj, pj):  


c1, p1), (c2, p2), ..., (cn, pq),

де cj – код символу, а pj– оцінка надійності розпізнавання символу (далі – оцінки розпізнавання). Якщо pj=1, то символ cj розпізнаний з найбільшою надійністю, а якщо pj=0, то – з найменшою. При цьому cj належить алфавіту розпізнавання, що складається з q символів. Всі оцінки розпізнавання мають нормуванням:


0≤pj ≤1





Тоді результати розпізнавання слова, що складається з n символів (знакомісць) виглядають наступним чином:


c11, p11), (c12, p12), ..., (c1n, p1n)

c21, p21), (c22, p22), ..., (c2n, p2n)

...
cq1, pq1), (cq2, pq2), ..., (cqnpqn).


Механізм розпізнавання символу може помилятися. Розпізнане слово вважається розпізнаним з помилками чи без помилок в залежності від відмінності або збігу  відомого «ідеального» слова c*1c*2c*n, що заздалегідь було задано людиною, з  послідовністю символів c11c12c1n, вилучені з перших альтернатив {(c11, p11), (c12, p12),… (c1np1n)}. Визначимо для набору розпізнаних слів точність розпізнавання як частку слів, не розпізнаних без помилок.


Нижче наведено приклад результатів розпізнавання прізвища «ЄПІФАНОВ»:




У прикладі одне знакоместо (буква «Н») розпізнано з помилкою, тому все слово буде вважатися як розпізнане помилково.


Для описаних далі експериментів були використані два набору тестових даних: Т1 (2 722 слів, що складаються з 22 103 символів з низькою якістю оцифровки і, відповідно з невисокою точністю розпізнавання) і Т2 (2354 слів, що складаються з 19230 символів з середньою якістю оцифровки і більш надійним розпізнаванням). Набір Т1 складався з 896 прикладів прізвищ, 915 прикладів імен, 911 прикладів по батькові, а набір Т2 – з 776 прикладів прізвищ, 794 прикладів імен і 784 прикладів по батькові відповідно.


Вище було написано, що оцінки розпізнавання pkj інтерпретувалися як імовірності. Подивимося на наборах Т1 і Т2, як корелюють оцінки розпізнавання pkj з кількістю трапилися помилок. Для цього побудуємо гістограму кількості помилок нашого механізму розпізнавання, що трапилися з символами з оцінками pkj з визначеного діапазону відрізка [0,1]. Для наочності розіб'ємо відрізок [0,1] на 32 інтервалу [0, 1/32), [1/32, 2/32),… [31/32, 1] і для безлічі розпізнаних символів з оцінками pkj з інтервалу [d/32, (d+1)/32) підрахуємо кількість помилково розпізнаних символів. Ця гістограми наведена на рисунку 2, вид гістограми свідчить на користь інтерпретації оцінок розпізнавання pkj як ймовірностей, оскільки при малих значеннях оцінок спостерігається багато помилок, а при великих значеннях (близьких до 1) — мало. Точніше, при великих значеннях оцінок розпізнавання (більш 26/32) помилки взагалі відсутні. Ми не стали робити більш точних досліджень кореляції оцінок розпізнавання і ймовірностей (частот) появи помилок з причини обмеженого обсягу наборів Т1 і Т2.




Малюнок 2. Гістограма кількості помилок розпізнавання залежно від оцінок розпізнавання


3. Алгоритми корекції результатів розпізнавання за допомогою триграм

Опишемо простий алгоритм для корекції результатів розпізнавання.


Для всіх символів kі для 1≤in, 1≤kq (тобто для всіх символів, які є фіктивними) розглянемо два попередніх йому символу kі-2,kі-1, які вважаються вже вибраними (зафіксованими) і використовуючи готові триграми <kі-2,kі-1,kі>, містять символ kі, обчислимо нову оцінку:




відсортуємо альтернативи з новим значенням kiі зафіксуємо символ для корекції наступного символу kі+1. Тобто спочатку перерахуємо значення оцінок для першого символу слова з урахуванням двох фіктивних символів, які ми вважаємо обраними, і зафіксуємо перший символ. Після перерахунку оцінок чергового символу перейдемо до наступного за ним символу і так далі.


У формулах використовувалися припущення про те, що θ (kі-2,сki-1,сki) і pkі ймовірностями. Ми очікували від алгоритму виправлення деяких помилок розпізнавання за рахунок того, що невірні рідко зустрічаються трійки розпізнаних символів kі-2,kі-1,kі будуть замінені на зустрічаються більш часто.


Розглянемо результати роботи алгоритму на наборах Т1 і Т2, зведені в таблиці 1 і 2. У цих і наступних аналогічних таблицях містяться дані про слова, які були розпізнані з помилками, і про безпомилково розпізнаних словах і використовуються наступні характеристики:


n1 – кількість слів без помилок і в вихідному розпізнаванні і  при використанні механізму триграм;


n2 – кількість слів з помилками у вихідному розпізнаванні, не виправлені триграмами;


n3 – кількість слів з помилками у вихідному розпізнаванні, виправлені триграмами


n4 – кількість слів без помилок у вихідному розпізнаванні, що застосування триграм привнесло помилки.


Таблиця 1. Результати роботи алгоритму на тестовому наборі Т1







Прізвище

Ім'я

по Батькові

n1

811 (90.51%)

840 (91.80%)

827 (90.78%)

n2

44 (4.91%)

28 (3.06%)

31 (3.40%)

n3

36 (4.02%)

38 (4.15%)

48 (5.27%)

n4

5 (0.56%)

9 (0.98%)

5 (0.55%)



Таблиця 2. Результати роботи алгоритму на тестовому наборі Т2







Прізвище

Ім'я

по Батькові

n1

736 (94.85%)

760 (95.72%)

747 (95.28%)

n2

16 (2.06%)

7 (0.88%)

9 (1.15%)

n3

21 (2.71%)

24 (3.02%)

26 (3.32%)

n4

3 (0.39%)

3 (0.38%)

2 (0.26%)



З таблиці слід, що алгоритм коригування дає цікаві результати, оскільки триграмами виправляється більше помилок, ніж привноситься. У той же самий час виникає питання, як можна пояснити залежність символу слова від двох попередніх символів? Це питання залишається без відповіді, така залежність не може бути обґрунтована. Однак прийнята залежність сприяла створенню дуже простого алгоритму.


Не будемо піддавати описаний алгоритм подальшій критиці, відзначимо тільки, що можна придумати безліч аналогічних простих алгоритмів, наприклад, із залежністю символу від наступних двох або від двох сусідніх символів, і ці алгоритми також дадуть прийнятні результати.


Ми поставили за мету розробити алгоритм без залучення умов залежно символів від сусідніх символів, припускаючи, що такий алгоритм, будучи більш суворим, працював би краще, ніж . Розроблений алгоритм коригування результатів розпізнавання за допомогою триграм заснований на обчисленнях маргінальних розподілів і байєсівських мереж.


Для слова n символів з кожним знакоместом асоціюємо випадкову величину зі значеннями в кінцевому просторі станів і покладемо, що є алфавітом розпізнавання A, тобто безліччю букв російської мови, в якому не розрізняються великі та малі літери. Позначимо через N = {1,...,n} безліч індексів. Назвемо твір простором кінцевих конфігурацій вектора . Далі побудуємо граф за наступним правилом. Безліч є множиною вершин графа. Будемо вважати, що з кожної трійкою вершин <xj,xj+1,xj+2> асоційована нормована функція ваг триграм . З'єднаємо ребрами вершини з трійки між собою, сукупність отриманих ребер утворює безліч .


Випишемо формулу для спільного розподілу ймовірностей

/


– функція оцінок для розпізнавання i-го знакомісця, – нормована функція ваг триграм.


Для перерахунку оцінок досить порахувати маргінальні розподілу


.


Обчислення маргінальних розподілів ми реалізували за допомогою алгоритму HUGIN [5, 6]. Не розкриваючи подробиць реалізації, зазначимо, що цей алгоритм є істотно більш складним, ніж алгоритм .


Результати роботи алгоритму на тих же самих наборах Т1 і Т2 зведені в таблиці 3 і 4, при цьому в таблиці додані результати роботи алгоритму для порівняння. Також в таблиці 3 і 4 додані характеристики точності алгоритмів.


Таблиця 3. Результати роботи алгоритмів на тестовому наборі Т1











Прізвище

Ім'я

по Батькові

алгоритм 

алгоритм 

алгоритм 

алгоритм 

алгоритм 

алгоритм 

n1

811 (90.51%)

815 (90.96%)

840 (91.80%)

845 (92.35%)

827 (90.78%)

831 (91.22%)

n2

44 (4.91%)

38 (4.24%)

28 (3.06%)

30 (3.28%)

31 (3.40%)

21 (2.31%)

n3

36 (4.02%)

42 (4.69%)

38 (4.15%)

36 (3.93%)

48 (5.27%)

58 (6.37%)

n4

5 (0.56%)

1 (0.11%)

9 (0.98%)

4 (0.44%)

5 (0.55%)

1 (0.11%)

Точність вихідного розпізнавання

91.07%

92.79%

91.33%

Точність з триграмами

94.53%

95.65%

95.96%

96.28%

96.05%)

97.59%

Виграш у точності при використанні триграм

3.46%

4.58%

3.17%

3.50%

4.72%

6.26%



Таблиця 4. Результати роботи алгоритмів на тестовому наборі Т2











Прізвище

Ім'я

по Батькові

алгоритм 

алгоритм 

алгоритм 

алгоритм 

алгоритм 

алгоритм 

n1

736 (94.85%)

737 (94.97%)

760 (95.72%)

762 (95.97%)

747 (95.28%)

749 (95.54%)

n2

16 (2.06%)

12 (1.55%)

7 (0.88%)

5 (0.63%)

9 (1.15%)

8 (1.02%)

n3

21 (2.71%)

25 (3.22%)

24 (3.02%)

26 (3.27%)

26 (3.32%)

27 (3.44%)

n4

3 (0.39%)

2 (0.26%)

3 (0.38%)

1 (0.13%)

2 (0.26%)

0 (0.0%)

Точність вихідного розпізнавання

95.23%

96.10%

95.54%

Точність з триграмами

97.55%

98.20%

98.74%)

788 (99.24%)

773 (98.60%)

776 (98.98%)

Виграш у точності при використанні триграм

2.32%

2.96%

2.64%

3.15%

3.06%

3.44%



4. Обговорення результатів роботи алгоритмів
З таблиць 3 та 4 випливає, що на наборах Т1 і Т2 обидва алгоритму суттєво покращують вихідні результати розпізнавання, при низькій якості оцифровки точність розпізнавання може бути підвищена більше ніж на 6%. У всіх розглянутих випадках алгоритм дає кращі результати, ніж алгоритм .


Недоліком алгоритму є використання нічим не обґрунтованої гіпотези про залежності символу від двох попередніх символів.


Недоліком алгоритму є істотно більш низьку швидкодію у порівнянні з швидкодією алгоритму – більше ніж у 100 разів. Однак необхідно зазначити, що алгоритм є дуже простим, обробляє одне слово приблизно за 0.001 секунди.


У деяких випадках використання триграм призводить до погіршення вірних результатів розпізнавання. В основному, такі випадки  пояснюються двома наступними причинами:

  • початкове розпізнавання дало не дуже впевнений результат з низькими оцінками першої альтернативи, а триграми, одержувані з інших альтернатив, мають більшу вагу (наприклад, в слові «ДИНАР» знакоместо з символом «Д» має низьку оцінку, рівну 0.57, і це призводить до заміни на символ «Л» з-за того, що вага триграми «ДІН» приблизно дорівнює  0.0001,  а вага триграми «ЛІН» приблизно дорівнює 0.0034),
  • в словнику триграм відсутні триграми, необхідні для підтвердження трійок символів в рідкісних імена, прізвища або по батькові (наприклад, у словнику триграм не міститься триграми «ЗРВ», чому слово «АЗРВАРД» замінюється на «АЗРААРД»).


Розподіл кількості помилок розпізнавання залежно від оцінок розпізнавання після застосування триграм також виглядає «поліпшеним». На малюнку 3 представлена гістограма, підрахована після застосування триграм з допомогою алгоритму , в порівнянні з вихідною гістограмою. Видно, що практично на всіх інтервалах оцінок кількість помилок зменшено.




Малюнок 3. Гістограма кількості помилок розпізнавання залежно від оцінок розпізнавання до (синій) і після (червоний) застосування триграм


Висновок
Ми показали спосіб корекції розпізнаних документів з допомогою механізму триграм на прикладі  полів паспорта (ПІБ) громадянина Російської Федерації. Були описані два алгоритму такої корекції та основні проблеми їх роботи. Суттєвим є наявність розумних оцінок надійності, які формуються механізмом розпізнавання, і представницької вибірки слів для побудови словника триграм.


Описані алгоритми використані для корекції результатів розпізнавання у працюючих програмних продуктах Smart Engines.


Список корисних джерел
  1. Щуцький Ю. К. Китайська класична «Книга Змін». — 2-е вид. испр. і дод. / Під ред. А. В. Кобзєва. — М: Наука, 1993.
  2. Kukich, K. Techniques for Automatically Correcting Words in Text. ACM computing survey, Computational Linguistic, V. 24, No. 4, 377-439. 1992.
  3. «Паспортний сканер своїми руками» (https://habrahabr.ru/company/smartengines/blog/278257/)
  4. «Розпізнавання Паспорта РФ на мобільному телефоні» (https://habrahabr.ru/company/smartengines/blog/252703/)
  5. R. Cowell, P. Dawid, S. Lauritzen, D. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer, 1999.
  6. Michael I. Jordan. An introduction to probabilistic graphical models. Manuscript used for Class Notes of CS281A at UC Berkeley, Fall 2002.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.