Сучасні аспекти уявлення текстів при аналізі природної мови: класичні та альтернативні підходи

Введення

У computer science з року в рік все більш популярною стає тема обробки природної мови. Через величезну кількість завдань, де потрібно подібний аналіз, складно переоцінити необхідність автоматичної обробки текстових документів.
 
У цій статті ми максимально просто постараємося описати найбільш популярні сучасні підходи до подання текстових документів для комп'ютерної обробки. А на одному з них, який в даний час ще не отримав широкого розповсюдження, проте має на це всі шанси, зупинимося більш детально, оскільки цей метод ми використовуємо в SlickJump при розробці алгоритмів, наприклад, контекстного таргетингу реклами .
 
Відзначимо, що наведені підходи застосовні не тільки до текстів, а взагалі до будь-яких об'єктів, які можна представити у вигляді символьних послідовностей, наприклад, які-небудь макромолекули (ДНК, РНК, протеїни) з генетики. Усього ми розглянемо 4 методу:
 
 
     
  1. прізнаковая опис.
  2.  
  3. Попарне накладення (вирівнювання) текстів.
  4.  
  5. Формування профілю і прихованої марковской моделі.
  6.  
  7. Подання фрагментами.
  8.  
Отже, приступимо.
 
 

прізнаковая опис

Ознакове опис — підхід, який можна назвати класичним при аналізі природної мови. Він має на увазі, що з аналізованих текстових документів виділяється певна кількість ознак, наприклад, слів, або пар поспіль йдуть слів (так званих биграмм). Ознаки можна фільтрувати, наприклад, за частотою народження в наборі документів, або ж прибирати з їхнього списку ті, які не представляють інтересу — наприклад, прийменники чи союзи («стоп-слова»). Далі кожен документ характеризується кількістю входжень в нього даних ознак, або ж, наприклад, їх наявністю / відсутністю, що зручно представляти у вигляді вектора, де кожен елемент відповідає певному ознакою. Їх порядок, природно, повинен бути фіксований заздалегідь. Відзначимо, що важливим завданням є виявлення одних і тих же ознак в різній формі — наприклад, зручно вважати, що «Катею» і «Катя» — це один і той самий ознака. Для цього застосовують процеси стеммірованія, при якому розглядаються тільки основи слів (найчастіше, коріння, а приставки, суфікси, закінчення відкидаються) або лемматізірованія, коли всі слова приводяться до «нормальної формі», наприклад, в російській мові іменники зручно приводити до форми називного відмінка в однині. Другий процес майже завжди складніше, часто потрібно мати базу словоформ (без них, наприклад, для слова «люди» не одержати нормальну форму «людина»), тоді як для першого процесу для багатьох мов достатній список правил перетворення слів.
 
Наприклад, нехай нам дано текст, взятий з прекрасного вірша М. Гумільова «Жираф»:
 
Послухай: далеко, далеко, на озері Чад
Вишуканий бродить жираф.
Виділяємо звідси ознаки (будемо використовувати тільки окремі слова), лемматізіруем їх, отримуємо наступний набір:
 
 (слухати, далеко, озеро, Чад, вишуканий, бродити, жираф)
 
Прийменник «на" не беремо як стоп-слово. Якщо тепер уявити перший рядок даного нам тексту в векторній формі на основі вищенаведеного списку, ми отримаємо наступний вектор:
 
 (1, 2, 1, 1, 0, 0, 0)
 
Отримані вектора можна об'єднувати в матрицю, вимірювати різні відстані (яких існує велика кількість) між ними, застосовувати до них техніки перетворення частот (TF-IDF, наприклад — але в цьому випадку для адекватної його роботи кількість ознак і документів має бути достатнім).
 
 

Накладення послідовностей, формування профілів

У деяких завданнях використовується підхід, що полягає в попарном накладення (вирівнюванні) символьних послідовностей. Суть цього методу полягає в тому, щоб максимізувати число позицій, в яких знаходяться співпадаючі символи послідовностей, при цьому самі послідовності можна «розривати». Цей підхід активно використовується в задачах біоінформатики, де в ролі послідовностей символів виступають макромолекули, наприклад, ДНК, причому зазвичай такі, що одні з них є результатами зміни інших, наприклад, історичних модифікацій. Часто передбачається, що всі порівнювані послідовності мають спільного предка. Для цього підходу розроблено декілька заходів близькості, що породжують матриці відстаней, з якими і ведеться подальша робота.
 
Крім того, існує метод, що припускає формування профілю і прихованої марковской моделі для текстових документів. Цей підхід знову ж заснований на накладенні послідовностей, але не попарном, а множині. Позиції, в яких беруть участь всі послідовності, виділяються окремо. Прихована марковська модель — розвиток цього підходу, що припускає, що послідовності генеруються переходами між її станами. При кожному переході з певними ймовірностями формуються її символи. Цей метод широкого поширення не має, тому на такому короткому його описі ми і зупинимося.
 
 

фрагментного уявлення

І, нарешті, останній підхід, на якому ми і зупинимо увагу, це фрагментне опис текстів. У цьому підході використовуються так звані анотовані суффіксние дерева. Анотоване суффіксное дерево (АСД) — це структура даних, використовувана для обчислення і зберігання всіх фрагментів тексту спільно з їх частотами. Вона задається як кореневе дерево (тобто одна вершина в ньому виділена і іменується коренем), в якому кожен вузол відповідає одному символу і позначений частотою того фрагмента тексту, який кодує шлях від кореня до даного вузла.
При використанні АСД весь текст розбивається на рядки — ланцюжки символів. Як правило, один рядок формується з 2-4 поспіль йдуть слів. Приклад АСД для короткого рядка показаний на малюнку нижче.
 
 
 
Суфіксом довжини рядки довжини (), що складається з символів , називається подстрока . Наприклад, для рядка суфіксом довжини 2 буде подстрока . Наведемо неформальне опис алгоритму побудови АСД по заданій рядку .
 
 
     
  1. Ініціалізувати порожню структуру для зберігання АСД — . Ця структура повинна мати можливість зберігати дерево з символами і числами (їх частотою) у вузлах.
  2.  
  3. Знайти всі суфікси рядки: .
  4.  
  5. Для кожного суфікса шукаємо в такий шлях від кореня, що збіг з початком суфікса максимально по довжині — . Для всіх символів, що потрапили в збіг , збільшуємо частоту відповідних вузлів на 1.
  6.  
  7. Якщо збіг по довжині менше , значить, суфікс не пройдений до кінця. Тоді в необхідно створити нові вузли, присвоївши їм частоту 1.
     
  8.  
При побудові АСД для двох і більше рядків суфікси всіх рядків послідовно накладаються на загальне дерево. Таким чином, представивши документ у вигляді безлічі рядків, можна побудувати для нього відповідне АСД.
АСД, побудоване для документа, дозволяє успішно вирішувати таке завдання, як знаходження близькості рядка і документа. Ця задача називається задачею визначення ступеня входження підрядка в дерево. Наведемо її рішення.
 
Введемо поняття умовної ймовірності вузла в АСД з кореневою вершиною . Частоту вузла позначимо через . Тоді умовна ймовірність вузла дорівнює:
 
 
 
де — предок вузла в дереві . Для тих вершин, для яких предком є ​​коренева вершина , формула приймає вигляд:
 
 
 
де безліч є ніщо інше, як безліч всіх вузлів на першому рівні дерева.
 
Для кожного суфікса рядки оцінка ступеня його входження в дерево виражається як сума умовних ймовірностей вузлів, що належать максимальному збігу довжини .
 
 
 
Тоді оцінка ступеня входження рядка в дерево визначається як
 
 
 
При порівнянні ступенів входження рядка в два і більше АСД формулу необхідно модифікувати, поділивши на довжину знайденого входження.
 
 
 
Якщо потренуватися і обчислити по цій формулі ступеня входження в АСД деяких рядків у наведене на малюнку вище дерево, то ми отримаємо таку табличку:
                          
Рядок Ступінь входження рядка в дерево
JAVASCRIPT 0.083
JEEP 0.125
SLICKJUMP 0.111
JK 0.291
JUKE 0.125
Алгоритм побудови АСД, наведений вище, не є оптимальним. В даний час для побудови АСД частіше застосовуються алгоритми, засновані на класичних методах роботи з рядками, наприклад, алгоритмі Укконен пошуку підрядка в рядку. Це дозволяє скоротити часові витрати як на побудову АСД, так і на обчислення оцінки входження рядка в АСД. Інший напрям — зменшення необхідних ресурсів пам'яті. Цього можна досягти шляхом застосування різних структур даних для зберігання дерев, наприклад, спеціальних масивів.
 
 

Переваги фрагментного подання

Відзначимо переваги цього підходу в порівнянні з прізнаковая методом. Прізнаковие підходи набагато гірше відчувають глибоку «структуру» тексту, навіть при використанні в якості ознак биграмм (або навіть більш довгих послідовностей слів — триграм, і т. д., що, до речі, дуже сильно збільшує розмірність векторів). Крім того, для фрагментного підходу не потрібно проводити приведення слів до нормальних форм (якщо воно, звичайно, використовує тільки правила перетворення, а не бази словоформ) — якщо слово входить у АСД, то і його основа, очевидно, розташується в АСД на який- небудь гілки. Але найголовніше — це те, що Фрагментний підхід терпимо до незначних помилок у текстах. Безумовно, є й спеціальні методи, що дозволяють навчати цьому і прізнаковие підходи, але це часто дуже ускладнює алгоритми. Пояснимо докладніше на прикладі конкретного прикладу з нашої компанії.
 
Технологія контекстного націлення товарів партнерських магазинів у SlickJump базується на ймовірнісної тематичної моделі LDA (приховане розміщення Дирихле), що працює з ознаками. Взагалі розподіл усіх тематичне моделювання — це окрема велика і цікава тема, в неї лізти ми якщо і будемо, то не в цій статті. Відзначимо лише, що такий підхід дозволяє вирішувати задачу знаходження ступенів близькості документів (тобто контексту і пропонованих товарів), причому вирішувати її для величезного числа документів — а товарів партнерських магазинів у базах нашої компанії більше 2 млн.
 
Але для контекстного націлення банерів, кількість яких незрівнянно менше, ніж кількість товарів в партнерських інтернет магазинах, ми застосовуємо спеціально розроблену модель, засновану на методі АСД. Це дозволяє давати хорошу якість контекстного таргетингу навіть там, де люди пишуть як курка лапою — наприклад, на форумах. Розглянемо приклад.
 
Нехай у нас є банери магазину електроніки, що пропонують модні аксесуари для смартфонів зі знижками. І форум про мобільну техніку в якості рекламного майданчика. Рекламодавець вказує список ключових слів для своїх банерів або надає зробити це нам (що зручно, коли число банерів обчислюється тисячами, у нас є відповідний функціонал). Ми повинні підібрати релевантні контексту (як правило, веб-сторінці, повідомленням на форумі і т.д.) банери. Порівняємо дві моделі контекстного таргетингу: LDA (на основі ознак) і нашу модель на основі АСД, і дізнаємося, чи будуть знайдені релевантні банери при двох різних ситуаціях: коли люди пишуть правильно і коли вони припускаються помилок.
Якби всі люди писали без помилок, ніяких проблем з контекстним таргетингу ніколи б не виникало. Якщо є ключове слово «зарядний пристрій», а в тексті повідомлень десь зазначено «зарядка», то ніяких проблем з орієнтуванням не виникне завдяки процесу нормалізації ознак. Скріншот нижче показує, що обидві моделі знайшли релевантні банери.
 
А от якщо людина написала hts замість htc (хоч і примітивний приклад, але класика жанру), все набагато цікавіше. Спробуємо знайти банери, релевантні даному слову. Модель LDA, заснована на признаковом підході без спеціальних пристосувань, не знайде нічого (або нічого адекватного, що теж погано). А метод, заснований на АСД, видає прекрасний результат, навіть незважаючи на те, що в слові ціла одна помилка на всього три букви. Це продемонстровано на скріншоті нижче, де показані відповідні назви товарів, знайдених за запитом.
 
 

Висновок

Звичайно, архіскладних для природної мови проблем синонімії та омонімії підхід, що використовує АСД, не вирішить, так що панацеєю від усього не є. Крім того, ступінь входження рядка в дерево, необхідна для розрахунку релевантності, обчислюється за час, залежне від довжини цього рядка — чим довше рядок, тим більше час. І при примітивному підході таку перевірку треба робити в АСД для всіх документів. Але в SlickJump ми застосовуємо спеціальні структури даних вищого порядку, що дозволяють визначати список кандидатів у релевантні серед всіх документів і перевіряти ступінь входження тільки в них без втрати якості, не шукати там, де явно нічого не знайдеться. Ми активно працюємо в цьому напрямку, тут багато що ще можна поліпшити.
 
 
 
У нас немає ніяких сумнівів, що Фрагментний метод для представлення текстів у найближчі роки буде активно розвиватися, і розвиватися у багатьох напрямках. А ми в найближчих статтях зробимо огляд сучасних алгоритмів побудови та подання анотованих суффіксних дерев.
 
 
 
 

Список літератури для читання за темою

 
     
  1. Маннінг К. Д., Рагхаван П., Шютце Х. Введення в інформаційний пошук. М.: Вільямс, 2011
  2.  
  3. Миркин, Б. Г. Методи кластер-аналізу для підтримки прийняття рішень: огляд. М.: Видавничий дім Національного дослідницького університету «Вища школа економіки», 2011
  4.  
  5. Миркин Б. Г., Черняк Е. Л., Чугунова О. Н. Метод анотованого суффіксного дерева для оцінки ступеня входження рядків у текстові документи. Бізнес-інформатика. 2012. Т. 3. № 21. С. 31-41.
  6.  
  7. Дубов М. С., Черняк Е. Л. Анотовані суффіксние дерева: особливості реалізації. В кн.: Доповіді всеросійської наукової конференції АІСТ-2013 / Відп. ред.: Є. Л. Черняк; науч. ред.: Д. І. Ігнатов, М. Ю. хача, О. Баринова. М.: Національний відкритий університет «ІНТУЇТ», 2013. С. 49-57.
  8.  
  9. Mirkin BG, Core Concepts of Data Analysis. Springer, 2012
  10.  
  11. Коршунов А, Гомзін А. Тематичне моделювання текстів на природній мові. Праці ІСП РАН. 2012. №. С.215-244.
  12.  
  13. Steven Bird, Ewan Klein, Edward Loper. Natural Language Processing with Python. OReilly Media, 2009
  14.  

Джерело: Хабрахабр

0 коментарів

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