N-грама

N-грама — послідовність з n елементів[1]. З семантичної точки зору, це може бути послідовність звуків, складів, слів або букв. На практиці частіше зустрічається N-грами як ряд слів, стійкі словосполучення називають колокацію. Послідовність з двох послідовних елементів часто називають біграм, послідовність з трьох елементів називається триграма. Не менш чотирьох і вище елементів позначаються як N-грами, N замінюється на кількість послідовних елементів.

Використання N-грам

Загальне використання N-грам

N-грами в цілому знаходять своє застосування в широкій області наук. Вони можуть застосовуватися, наприклад, в галузі теоретичної математики, біології, картографії, а також в музиці. Найбільш часто використання N-грам включає наступні області:

  • вилучення даних для кластеризації серії супутникових знімків Землі з космосу, щоб потім вирішити, які конкретні частини Землі на зображенні,
  • пошук генетичних послідовностей,
  • в області генетики використовуються для визначення того, з яких конкретних видів тварин зібрані зразки ДНК, 
  • в комп'ютерному стисненні,
  • для індексування даних в пошукових системах; з використанням N-грам, як правило, індексовані дані, пов'язані зі звуком.

Також N-грами широко застосовуються в обробці природної мови.

Використання N-грам для потреб обробки природної мови

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

Інше застосування N-грам є виявлення плагіату. Якщо розділити текст на кілька невеликих фрагментів, представлених N-грамами, їх легко порівняти один з одним, і таким чином отримати ступінь подібності контрольованих документів[3]. N-грами часто успішно використовуються для категоризації тексту та мови. Крім того, їх можна використовувати для створення функцій, які дозволяють отримувати знання з текстових даних. Використовуючи N-грами, можна ефективно знайти кандидатів, щоб замінити слова з помилками правопису.

Приклад біграмної моделі

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

P = P (щастя) * P (є | щастя) * P (задоволення | щастя є) * P (без | щастя є задоволення) * P (каяття | щастя є задоволення без)

Розрахувати ймовірність P (щастя) справа нехитра: потрібно всього лише порахувати скільки разів це слово зустрілося в тексті і поділити це значення на загальне число слів. Але розрахувати ймовірність P (каяття | щастя є задоволення без) уже не так просто. На щастя, ми можемо спростити цю задачу. Приймемо, що ймовірність слова в тексті залежить тільки від попереднього слова. Тоді наша формула для розрахунку фрази прийме наступний вигляд:

P = P (щастя) * P (є | щастя) * P (задоволення | є) * P (без | задоволення) * P (каяття | без)

Вже простіше. Розрахувати умовну ймовірність P (є | щастя) не складно. Для цього вважаємо кількість пар 'щастя є' і ділимо на кількість в тексті слова 'щастя'.

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

Науково-дослідні проекти Google

Дослідницькі центри Google використовували N-грамні моделі для широкого кола досліджень і розробок. До них належать такі проекти, як статистичний переклад з однієї мови на іншу, розпізнавання мови, виправлення орфографічних помилок, вилучення інформації та багато іншого. Для цілей цих проектів були використані текстові корпуси, які містять кілька трильйонів слів.

Google вирішила створити свій навчальний корпус. Проект називається Google teracorpus і він містить 1 024 908 267 229 слів, зібраних із загальнодоступних вебсайтів[4].

Методи для вилучення N-грам

У зв'язку з частим використанням N-грам для вирішення різних завдань необхідний надійний і швидкий алгоритм для вилучення їх з тексту. Відповідний інструмент для вилучення N-грам повинен бути в змозі працювати з необмеженим по розміру текстом, працювати швидко і ефективно використовувати наявні ресурси. Є кілька методів вилучення N-грам з тексту. Ці методи засновані на різних принципах:

Синтаксичні N-грами

Синтаксичні N-грами - це N-грами, що визначаються шляхами в деревах синтаксичних залежностей або деревах складових, а не лінійною структурою тексту[6][7].Наприклад, речення: «Економічні новини мають незначний вплив на фінансові ринки» може бути перетворено в синтаксичні N-грами слідуючи деревовидної структурі його відносин залежностей: новини-економічні, вплив-незначний, вплив-на-ринки-фінансові та інші[6].

Синтаксичні N-грами відображають синтаксичну структуру на відміну від лінійних N-грам і можуть використовуватися в тих же програмах, що й лінійні N-грами, в тому числі як ознаки у векторній моделі. Застосування синтаксичних N-грам дає кращі результати при вирішенні певних завдань, ніж використання стандартних N-грам, наприклад, для визначення авторства[8].

Компроміси

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

Методи згладжування

Є завдання балансування ваги між нечастими грамами (наприклад, якщо власне ім'я зустрінеться один раз в навчальних даних) та частими грамами. Крім того, елементи які не з'являлись в навчальних даних отримають ймовірність 0.0 без згладжування. Для незнайомих, але правдоподібних даних з вибірки, можна ввести псевдокількості.

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

Див. також

Примітки
  1. Proceedings of the 7th Annual Conference ZNALOSTI 2008, Bratislava, Slovakia, pp. 54-65, February 2008.
  2. Jurafsky, D. and Martin, J.H. {{{Заголовок}}}. — 988 p. — ISBN 9780131873216.
  3. Proceedings of the ITAT 2008, Information Technologies — Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008.
  4. FRANZ, Alex, BRANTS, Thorsten.
  5. M.
  6. Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández.
  7. Grigori Sidorov.
  8. Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh, and Liliana Chanona-Hernández.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.