Данная статья является авторским черновиком опубликованной в Springer Analysis of Images, Social Networks and Texts англоязычной публикации Cognitive Semiotic Model for Query Expansion in Question Answering.

Александр Сиренко

Московский Государственный Технический Университет им. Баумана, Россия, Москва, 2-я Бауманская улица, стр. 5; TNHH Cốc Cốc, Vietnam.

alexander.sirenko@gmail.com

Галина Черкасова

Институт Лингвистики, Российская Академия Наук, Россия, Москва, Большой Кисловский переулок, стр.1

gacherk@mail.ru

Юрий Филиппович

Государственный Технический Университет им. Н.Э.Баумана, Россия, Москва, 2-я Бауманская улица, стр. 5

y_philippovich@mail.ru

Юрий Караулов

Институт Русского языка им. В.В.Виноградова Российской Академии Наук, Россия, Москва, ул. Волхонка, 18/2

karaoulov@rambler.ru

Аннотация.

Расширение запроса увеличивает полноту этапа извлечения документов в цепочке работы вопросно-ответной системы. Мы утверждаем важность персонализированной и автономной обработки запроса и автоматизируем семиотическую модель для достижения данных характеристик. Модель функционирует как контекстно-зависимая взвешенная грамматика, используя алгоритм применения правил с неполным совпадением. Семиотическая модель стала основой регрессионной модели предсказания релевантных запросу термов. ROC-анализ оценивает регрессионную модель и участвует в выборе оптимального порога отсечения. Мы сравниваем ранжирование термов регрессионной моделью и ранжирование внешней информационно-поисковой системы (ИПС).

Ключевые слова.

семиотическое моделирование, когнитивные эксперименты, грамматика, расширение запроса, регрессия, вопросно-ответная система.

1. Введение.

Вопросно-ответная задача (Question Answering - QA) глубоко проработана в научных работах, в том числе через специальные направления конференции Text REtrieval Conference (TREC). Опубликованные недавно решения следуют стандартной последовательности шагов (QA pipeline) [Bilotti04]:

  1. обработать запрос;
  2. извлечь релевантные запросу документы/фрагменты;
  3. извлечь информацию и сформировать возможные ответы;
  4. ранжировать ответы для выбора наилучшего.

QA pipeline находит ответы в коллекции неструктурированных текстов, поэтому качество извлечения документов может ограничить производительность всей системы. Существуют различные способы увеличить полноту извлечения. В данном исследовании мы фокусируемся на расширении запроса релевантными термами в рамках подхода (QA pipeline).

Поскольку Интернет является наиболее популярным способом предоставления информационных сервисов, мы отмечаем два тренда: персонализацию сервисов и широкое использование мощных персональных устройств для доступа в сеть. Сегодня пользователи предоставляют личную информацию (историю запросов, местоположение, тексты сообщений) поисковой системе для получения релевантных результатов. Если запрос предобрабатывается локально без общения с внешней системой, вероятнее, что пользователь предоставит личную информацию для обработки. Подобный локальный препроцессор должен быть построен без ручного структурирования информации.

Мы предполагаем построение когнитивной семиотической модели на основе ассоциативной сети и набора когнитивных элементов [PhilippovichNeuromodel2013]. Психолингвисты научной школы “Русская языковая личность” описали когнитивную модель и опросили людей для сбора эмпирических данных. Это позволяет построить модель для “усредненного” носителя русского языка.

2. Предшествующие работы.

Последние разработки вопросно-ответных систем используют различные подходы к расширению запроса: техника общей информации [Berger2000,Bilotti04,Komiya2013]; статистический машинный перевод [Riezler07]; техника обратной связи релевантности, расширяющая запрос на основе первых результатов поисковой выдачи [Derczynski2008]. Эти техники требуют наличие вопросно-ответного корпуса или доступной поисковой системы для расширения запроса. Это противоречит идеям персонализации и автономности, поэтому мы предлагаем использовать когнитивную модель для расширения запроса. Когнитивные модели обычно специфичны к задаче (трансформационная грамматика Ноама Хомского [ChomskyMinProgram]), либо наоборот - являются фреймворками общего назначения (ACT-R [ACT-R], Soar [SoarIntro1996]). Выбранная когнитивная модель принимает на вход предложение в естественно-языковой форме, возвращая набор термов. Модель соответствует вопросно-ответной задаче, в тоже время соответствуя идеям персонализации и автономности.

3. Данные.

Ассоциативный эксперимент проводился по методу свободных ассоциаций, в котором респондент предоставляет первую ассоциацию на заданное слово. Мы строим сеть из лемматизированного ассоциативного словаря русского языка [ASNI07]. Сеть содержит 63,700 узлов, 394,000 связей в нелемматизированном виде и 29,290 узлов, 132,456 связей в лемматизированном. Вот пример необработанных ассоциаций: (дорога, далеко, 28), (дорога, длинная, 19), (дорога, домой, 15), где последнее число - сила ассоциативной связи. Когнитивный эксперимент методически повторяет игру “кроссворд”, где респондент угадывает слово по описанию. Пары (вопрос, ответ) с дополнительными атрибутами образуют когнитивные единицы (когнемы). Когнема имеет 5 компонент: \(Знак\), \(Смысл\), \(Формула\_смысла\), \(Функция\), \(Область\). \(Знак\) это слово, должное быть угаданным. \(Формула\_смысла\) определяет структуру утверждения из \(Смысл\) (дефиниция, метафора и т.д.). \(Функция\) отражает важность когнемы для респондента. \(Область\) позиционирует когнитивную единицу относительно прочих когнем респондента (литература, армия, инструменты и т.д.) Например:

  1. (“акцент”, “Способ произнесения говорящим на естественном языке”, “Дефиниция”, “обязательно”, “Язык”);
  2. (“дерево”, “имеет зеленые листья”, “Дескрипция”, “обязательно”, “Лес”);

Исходный набор из 18,300 когнем покрывает 55 вариатнов \(Формулы\_смысла\) и 231 вариант \(Области\). Множество когнем содержит 11,000 уникальных знаков и 31900 слов в \(Смысле\). Лемматизированные когнемы включают 3,974 слов в \(Знаке\) и 22,208 слов в \(Смысле\).

4. Построение препроцессора запросов.

Препроцессор запросов в данном случае классифицирует термы на релевантность запросу, используя когнитивную модель в качестве источника параметров, по которым проводится классификация. Для построения препроцессора мы:

  1. Строим контекстно-свободную грамматику \(G\) из ассоциативной сети и словаря синонимов [Abramov99];
  2. Строим взвешенную контекстно-зависимую грамматику \(G_{Ext}\) из \(G\) и множества когнем;
  3. Формируем множество вероятных термов расширения с помощью \(G_{Ext}\);
  4. Обучаем регрессионную модель, выбираем оптимальный порог отсечения и оцениваем получившийся классификатор.

4.1. Контекстно-свободная грамматика.

Элементы ассоциативной сети: \(S\) - стимул, \(R\) - реакция, \(SR\) - стимул и реакция, \(prob_{ij}\) - вероятность встретить ассоциацию от узла \(i\) к \(j\) в свободном ассоциативном эксперименте. Ассоциативная сеть и синонимы объединены в контекстно-свободную грамматику: узлы сети и синонимы формируют символы грамматики. Вывод в \(G\) выполняется аналогично цепям Маркова: мы определяем вероятность получения следующего предложения, основываясь на вероятности текущего предложения и вероятности правила. Ассоциации формируют правила замены стимула на реакцию с вероятностью \(prob_{ij}\). Синонимичные пары образуют правила с \(prob_{ij}=1\).

\(G\) применяет правила с наибольшей вероятностью в процессе генерации предложений из запроса. Применяемое правило \((t_k, (t_m...t_n), prob_{k,m..n})\) заменяет терм \(t_k\) в запросе термами \((t_m...t_n)\), генерируя новое предложение \(S_i\). Вероятность генерации \(S_i\) рассчитывается как произведение вероятностей примененных правил. Например: Запрос \(S_0=(t_1,t_2,t_3)\) после применения правил \(r_1=(t_1,t_4,prob_{1,4})\) и \(r_2=(t_4,t_5,prob_{4,5})\) сгенерирует \(S_1=(t_4,t_2,t_3)\) с вероятностью \(prob_{1,4}\); \(S_2=(t_5,t_2,t_3)\) с вероятностью \(prob_{1,4}*prob_{4,5}\). Если предложение \(S_i\) может генерироваться различными последовательностями примененных правил, его вероятность агрегирует произведения вероятностей по каждой цепочке вывода.

4.2. Контекстно-зависимая грамматика.

Для каждой когнемы \(cognem=(Знак,Смысл,Области)\) мы создаем правило грамматики \(P_{Ext}=(meaning, sign, \emptyset)\). \(meaning\) и \(sign\) части \(P_{Ext}\) это лемматизированные термы \(Смысла\) and \(Знака\) когнемы \(cognem\) с сохранением порядка. Правила \(\{P_{Ext}\}\) совместно с \(G\) формируют контекстно-зависимую грамматику \(G_{Ext}\). Мы используем метрику Дамерау-Левенштейна совместно с суффиксными деревьями внутри автомата для поиска неполных соответствий \(meaning\) части \(P_{Ext}\) с запросом [SirenkoContextSensitiveRules]. Автомат определяет инвертированную стоимость \(rInvCost\) основанного на когнеме правила \(\{P_{Ext}\}\) применительно к некоторому предложению. \(rInvCost\) контекстно-свободных правил в \(G_{Ext}\) равно \(prob_{ij}\) из \(G\). \(rInvCost\) замещает \(prob_{i,j}\) в рассчете вероятности сгенерированного предложения. Так как мы смешиваем вероятности из \(G\) с эвристическим значением \(rInvCost\) для \(\{P_{Ext}\}\), то предложения, сгенерированные \(G_{Ext}\) не обладают вероятностью, но имеют вес - инвертированную стоимость предложения \(sInvCost\).

Предложения, сгенерированные \(G_{Ext}\) содержат термы, которые не присутствуют в оригинальном запросе. Эти термы формируют набор вероятных термов расширения \(expTerms\). Каждый новый терм обладает свойствами \((t_i,tInvCost_i,tUsage_i)\), где \(tInvCost_i\) - агрегированная \(sInvCost\) всех сгенерированных предложений с \(t_i\); \(tUsage_i\) - доля термов запроса, использованных в выводе \(t_i\) среди всех термов запроса.

Если \(G_{Ext}\) запустить на “Столица крупнейшей нефтедобывающей страны”, она преобразует запрос с помощью ассоциативного правила наименьшей стоимости (столица \(\rightarrow\) Советский) в “Советский крупнейшей нефтедобывающей страны”. Триплет (“Советский”, \(tInvCost_{Советский\rightarrow столица}^{-1}\), 0.25) дополнит \(expTerms\). Преобразованное предложение переносится в множество для последующего вывода. Затем \(G_{Ext}\) применяет контекстно-зависимое правило с наименьшей стоимостью к исходному запросу и отмечает исходный запрос как обработанный. В этот момент у нас имеется 1 или больше термов в \(expTerms\) и 1 или более предложений из которых можно продолжать вывод. \(G_{Ext}\) выбирает не обработанное предложение с наибольшей \(invCost\) и применяет правила преобразования к нему. Вывод в \(G_{Ext}\) останавливается, когда \(expTerms\) достигает некоторого предельного размера. См. таблицу 2.

4.3. Классификатор релевантности термов.

Модель линейной регрессии предсказывает релевантность терма \(t_i\) запросу \(query\) в виде: \(Y(t_i) = b_0 + b_1*tInvCost_i + b_2 * tUsage_i\). Мы обучаем и тестируем модель на истинно-положительных парах \((Смысл, Знак)\) из множества когнем;

Используя сокращения TP (истинно положительный), FN (ложно отрицательный), TN (истинно отрицательный), FP (ложно положительный), опишем свойства регрессионной модели:

  1. Чувствительность \(Se=\frac{TP}{TP+FN}*100\%\);
  2. Специфичность \(Sp=\frac{TN}{TN+FP}*100\%\);
  3. \(AUC\) - область под кривой ROC-графа.

ROC-анализ использует график зависимости \(Se=F(1-Sp)\). \(AUC\) положительно соотносится с качеством регрессионной модели. При пороге отсечения \(cutoff=argmax_k(Se_k+Sp_k)\) регрессионная модель классифицирует достигнутые в процессе вывода грамматикой символы на релевантность запросу. Свойство \(Область\) когнем может использоваться для улучшения качества классификации [SirenkoPhilippovichAssocClassif].

5. Результаты.

Сформированная грамматика \(G_{Ext}\) содержит: 28,000 символов, 123,000 правил и 3,900 синсетов. Символы в синсете заменяют друг-друга с инвертированнй стоимостью 1. Запуск модели с запросом “Столица крупнейшей нефтедобывающей страны” производит набор символов, который содержит верный ответ “Москва” в позиции 2 и менее релевантные символы “город”, “Россия” в позициях (7, 1) (см. таблицу 2).

Последние разработки QA-систем построены и протестированы на англоязычных данных. Для оценки влияния препроцессора необходимо сравнить производительность QA “с” и “в отсутствии” препроцессора, либо убедиться, что дополнительные термы улучшают извлечение документов в верным ответом. Так как когнитивная модель не была построена на англоязычных данных, прямое сравнение не было выполнено. Мы используем 2 метода оценки производительности препроцессора:

  1. рассматривая модель как регрессионную модель релевантности термов расширения запросу;
  2. сравнивая ранжирование термов расширения регрессионной моделью со статистикой из ИПС по запросу \(<исходный\_запрос + терм\_расширения>\).

В первом методе применяется 2 набора: 2,500 когнем для обучения регрессионной модели (см. секцию 4) и 1,342 когнем для тестирования. Здесь когнемы используются в качестве пар \((запрос,ответ)\). Если мы обучаем или тестируем модель с запросом на базе когнемы, соответствующее данной когнеме правило из \(G_{Ext}\) отключается. См. таблицу 1 для оценки \(AUC\) на различных наборах запросов. Значения выше 0.5 означают, что регрессионная модель работает лучше, чем произвольный выбор, тогда как значения 0.8-0.9 говорят о ее высоком качестве.

Таблица 1. AUC на различных наборах запросов.

Формула смысла Термов в запросе Число запросов AUC регрессионной модели
description - 199 0.86
definition - 196 0.90
- [5-10] 192 0.80
- [1-5] 200 0.87

Во втором методе используется гипотеза из метода обратной связи релевантности: релевантные термы появляются в документе совместно с запросом чаще, чем не релевантные. Тогда набор термов максимальных рангов должен сохраняться в обоих ранжированиях:

  1. основанном на совместной встречаемости в документах ИПС;
  2. основанном на регрессионной модели.

Для ИПС критерием ранжирования будет \(rcoef_{s,q}=\frac{docsCount(query\cup symbol)}{Freq_{symbol}}\): \(Symbol\) совместно встречается с запросом \(Query\) внутри документа И \(Symbol\) не является частотным в документах.

Составим запрос \(<исходный\ запрос> И <терм\ расширения\ предложенный\ моделью>\) для ИПС Bing.com для сбора \(docsCount(запрос\cup терм)\) (См. таблицу 2). Результаты, ранжированные по \(DocsCount/frequency\) содержат релевантные ответы в позициях (1,2,5), что ближе к верхним значениям. Заметим, что полностью нерелевантный ответ “красный” понизился в ранге, а “аллея” не опускается вниз из-за низкой частотности.

Таблица 2. Ранжирование запроса “Столица крупнейшей нефтедобывающей страны”

Терм расширения tInvCost tUsage DocsCount frequency DocsCount
предложенный моделью (ранг) (ранг) (\(<запрос> + <терм>\) (терм) / frequency
город 2.271 (7) 5/6 (2) 3600 573.4 6.28
Москва 3.153 (2) 5/6 (2) 3600 633.5 5.68
дорога 2.604 (4) 5/6 (2) 1390 330.1 4.21
большой 2.374 (5) 5/6 (2) 3640 944.4 3.85
Россия 3.687 (1) 4/6 (3) 3580 952.0 3.76
завод 2.348 (6) 5/6 (2) 610 164.0 3.71
аллея 2.025 (8) 6/6 (1) 56 16.0 3.50
красный 2.786 (3) 5/6 (2) 620 240.5 2.58

6. Заключение.

Расширение запроса часто используется для улучшения эффективности подхода QA pipeline. Мы предлагаем использовать когнитивную семиотическую модель в качестве предобработчика запросов для персонализированного и автономномного расширения. Модель построена на материалах ассоциативной сети и набора когнитивных единиц. Она функционирует как контекстно-зависимая грамматика с неполным совпадением левой части правила и запроса. Для подбора термов расширения, грамматика упакована в регрессионную модель релевантности термов к запросу. Мы оцениваем эффективность регрессионной модели через ROC-анализ и \(AUC\). Термы высших рангов, предложенные моделью, имеют высокие ранги также в статистике совместной встречаемости с запросом в ИПС.

7. Благодарности.

Исследование поддержано грантом № 12-04-12039v Российского Гуманитарного научного Фонда и грантом № NSH-5740.2014.6 президента РФ.

Источники.

  1. [Bilotti04] Bilotti, M.: Query Expansion Techniques for Question Answering. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (2004)

  2. [PhilippovichNeuromodel2013] Philippovich Yu.N., Philippovich A.Yu.: Dynamic infocognitive model of verbal consciousness. Neyrokomp’yutery: sozdanie i ispol’zovanie, Vol 1, pp. 13-22 (2013) - in Russian

  3. [Berger2000] Berger, A., Caruana, R., Cohn, D., Freitag, D., Mittal, V.: Bridging the Lexical Chasm: Statistical Approaches to Answer-Finding. In Proceedings of the 23rd annual international ACM SIGIR conference (2000)

  4. [Komiya2013] Komiya, K., Abe, Y., Morita, H., Kotani, Y.: Question answering system using Q \& A site corpus Query expansion and answer candidate evaluation. SpringerPlus Vol 2, p. 396 (2013)

  5. [Riezler07] Riezler S., Vasserman, E., Tsochantaridis I., Mittal V., Liu, .Y: Statistical machine translation for query expansion in answer retrieval. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL’07) (2007)

  6. [Derczynski2008] Derczynski, L., Wang, J., Gaizauskas R., Greenwood M.: A data driven approach to query expansion in question answering. Proceedings of Coling 2008. Coling 2008 Organizing Committee, Manchester, pp. 4–41 (2008)

  7. [ChomskyMinProgram] Chomsky, N.,: The minimalist program. Current studies in linguistics series, Vol 28, MIT Press, p. 420 (1995)

  8. [ACT-R] Anderson, J. R., Bothell, D., Byrne M. D.: An Integrated Theory of the Mind. Psychological Review, Vol 111, pp. 1036-1060. (2004)

  9. [SoarIntro1996] Lehnman, J. F., Laird, J., Rosenbloom, P.: A Gentle Introduction to Soar, an Architecture for Human Cognition. University of Southern California, Information Sciences Institute. (1996)

  10. [ASNI07] Philippovich, A.Yu.: Automatized system for scientific research of associative experiments. Voprosy psikholingvistiki, Vol 6, pp. 143-153 (2007) - in Russian.

  11. [Abramov99] Abramov, N.,: Dictionary of Russian synonyms and phrases with similar meaning. Moskva: Russkie slovari, 7 (1999)

  12. [SirenkoContextSensitiveRules] Sirenko, A.: Using of non-determined finite automata for approximate substrings matching in context-sensitive grammar. Sbornik tezisov dokladov obshcheuniversitetskoy nauchno-tekhnicheskoy konferentsii ``Studencheskaya nauchnaya vesna - 2011’’, BMSTU n.a. Bauman, Moscow, pp. 310. (2011) - in Russian.

  13. [SirenkoPhilippovichAssocClassif] Philippovich, Yu.N., Sirenko, A.V.: Classification of associative network’s nodes: to build classifier. Izvestija visshih uchebnyh zavedenij, Problemy poligrafii i izdatel’skogo dela, Vol 6. (2012) - in Russian.