1 Вопросно-ответные системы Анатолий Никитин гр.3539 Павел Райков гр.3539 Friendly software should listen and speak …

2 План Введение QA-система Start Статистические техники для анализа естественного языка Восстановление смысловых связей Ссылки

3 Введение

4 Вопросно-ответные системы Определение Вопросно-ответная система: информационная система Поисковая Справочная Интеллектуальная использует естественно-языковой интерфейс

5 Источники информации Сеть Интернет Проблема доступа к внешним ресурсам Локальное хранилище Необходимость хранения локальной копии информации

6 История и области применения QA-систем 1960-е гг. – первые QA-системы Использовались как естественно-языковые оболочки для экспертных систем Современные QA-системы: Узкоспециализированные (closed-domain) Области применения: Медицина Автомобили Справочная информация Японцы … Требования к точности ответов Составление онтологий для предметных областей Общие (open-domain) Универсальность Наиболее известная система – Start (1993 г.)

7 Архитектура QA-системы Вопрос Анализатор вопросов Методы обработки естественных языков (NLP) Генератор ответов Ответ Поиск документов Фильтрация

8 Проблемы Типы вопросов Обработка вопросов Контекстные вопросы Источники знаний для QA-систем Выделение ответов Формулировка ответа Ответы на вопросы в реальном времени Многоязыковые запросы Интерактивность Механизм рассуждений (вывода) Профили пользователей QA-систем

9 Вопросно-ответная система Start

10 QA-система Start. Создана в MIT Artificial Intelligence Laboratory в 1993 году под руководством Boris Katz Универсальная Использует английский язык Источники знаний: локальное хранилище (База Знаний) сеть Интернет Основания системы Start: Применение особых методов NLP, разработанных специально для системы Start Идея создания аннотаций на естественных языках к блокам информации

11 Start. Виды вопросов Вопросы об определениях: What is a fractal? Вопросы о фактах: Who invented the telegraph? Вопросы об отношениях: What country is bigger, Russia or USA? Списковые запросы: Show me some poems by Alexander Pushkin …

12 Start. Примеры вопросов 1. География Give me the states that border Colorado. What's the largest city in Florida? Show me a map of Denmark List some large cities in Argentina Which is deeper, the Baltic Sea or the North Sea? Show the capital of the 2nd largest country in Asia 2. Искусство When was Beethoven born? Who composed the opera Semiramide? What movies has Dustin Hoffman been in?

13 Start. Примеры вопросов 3. Наука и справочная информация What is Jupiter's atmosphere made of? Why is the sky blue? Convert 100 dollars into Euros How is the weather in Boston today? How far is Neptune from the sun? Show me a metro map of Moscow. 4. История и культура What countries speak Spanish? Who was the fifth president of the United States? What languages are spoken in the most populous country in Africa? How many people live on Earth?

14 Start. База знаний doc1 doc2 doc3 doc4 Parser База Знаний Generator text

15 Start. База знаний Состоит из 3-х частей: Тернарные выражения (T-выражения) Синтаксические/семантические правила вывода (S-правила) Каталог слов (Лексикон)

16 Start. Тернарные выражения T-выражения – это выражения вида В качестве объекта/субъекта одного T-выражения могут выступать другие T-выражения Прилагательные, притяжательные местоимения, предлоги и другие части предложения используются для создания дополнительных T-выражений Остальные атрибуты предложения (артикли, времена глаголов, наречия, вспомогательные глаголы, знаки препинания и т.д.) хранятся в специальной структуре History, связанной с T-выражением.

17 Start. Пример T-выражения Parser Bill surprised Hillary with his answer with answer>

18 Start. Обработка запросов с помощью T-выражений Анализатор вопросов Parser Whom did Bill surprise with his answer? Bill surprised whom with his answer? with answer> Whom = Hillary Bill surprised Hillary with his answer База Знаний with answer> Генератор

19 Start. Обработка запросов с помощью T-выражений Анализатор вопросов Parser Did Bill surprise with his answer? Bill surprised Hillary with his answer? with answer> Yes! Yes, Bill surprised Hillary with his answer База Знаний Генератор

20 Т-выражения vs. ключевые слова The bird ate the young snake The snake ate the young bird The meaning of life A meaningful life The bank of the river The bank near the river

21 Т-выражения vs. ключевые слова Ключевые слова: Утрачивается информация о смысловых связях между словами Тексты сравниваются не со семантическим признакам, а по статистическим характеристикам ключевых слов T-выражения: Отражают порядок слов в предложении и смысловые связи между ними Выразительной силы T-выражений достаточно для составления аннотаций на естественных языках Эффективны при индексировании

22 What do frogs eat? Поиск, основанный на T-выражениях выдал 6 ответов, из которых 3 правильных: Adult frogs eat mainly insects and other small animals, including earthworms, minnows, and spiders One group of South American frogs feeds mainly on other frogs Frogs eat many other animals, including spiders, flies, and worms …

23 What do frogs eat? Поиск, основанный на ключевых словах, выдал 33 результата, в которых также встречались ответы на вопрос What eats frog? и просто совпадения слов eat и frog: Bowfins eat mainly other fish, frogs, and crayfish Cranes eat a variety of foods, including frogs, fishes, birds, and various small mammals. …

24 = Start. S-правила S-правило Surprise Where n i Nouns = Проблема: Решение: with n 3 > Bills answer surprised Hillary Bill surprised Hillary with his answer with answer> Parser

25 Start. S-правила S-правила описывают лингвистические вариации: Лексические Синонимы Морфологические Однокоренные слова Синтаксические Инверсии Активный/пассивный залог Притяжательные прилагательные Также используются для описания логических импликаций

26 Start. S-правила. Примеры S-правило Kill-Die Where n i Nouns S-правило Sell-Buy Where n i Nouns to n 3 > from n 1 >

27 Start. S-правила Некоторые S-правила могут использоваться в 2-х направлениях: в прямом при пополнении базы знаний новыми T- выражениями в обратном при обработке запроса пользователя

28 Start. Лексикон Некоторые S-правила применимы к группам слов В Лексиконе содержатся перечень слов языка, причем для каждого слова указан список групп, к которым оно относится S-правило ERV Where n i Nouns and v emotional-reaction-verbs with n 3 >

29 WordNet Семантический лексикон английского языка Состоит из синсетов (смыслов) Синсет: несколько синонимичных слов описание значения Одно слово – несколько синсетов (значений) слов, синсетов, пар «слово – синсет»

30 WordNet. Семантические отношения между синсетами Существительные Гиперонимы: Y – гипероним X, если X – разновидность Y Гипонимы: Y – гипоним X, если Y – разновидность X Равные по рангу: X и Y равны по рангу, если у них общий гипероним Голонимы: Y – голоним X, если X – часть Y Меронимы: Y – мероним X, если Y – часть X

31 WordNet. Семантические отношения между синсетами Глаголы Двигаться – гипероним Бегать Шептать – гипоним Говорить Спать – следование Храпеть Ходить – равный по рангу Бегать

32 Start. WordNet WordNet используется в системе Start при поиске совпадения с T-выражениями Пусть в базе есть T-выражение Canary – гипоним Bird На вопрос: Can canary fly? Start ответит Yes

33 Start. Omnibase «Универсальная база» Используется для выполнения запросов о фактах Модель «объект-свойство-значение» Пример: Federico Fellini is a director of La Strada Объект: La Strada Свойство: director Значение: Federico Fellini Каждому объекту сопоставлен источник данных (data source): Star Wars imdb-movie

34 Start. Omnibase. Примеры ВопросОбъектСвойствоЗначение Who wrote the music for Star Wars? Star WarsComposerJohn Williams Who invented dynamite? DynamiteInventorAlfred Nobel How big is Costa Rica? Costa RicaArea51,100 sq. km How many people live in Kiribati? KiribatiPopulation94,149 What languages are spoken in Guernsey? GuernseyLanguagesEnglish, French Show me paintings by Monet MonetWorks[images]

35 Start. Omnibase. Пример запроса Анализ вопроса Who directed X?, X = Gone with the wind Gone with the wind imdb-movie Omnibase Who directed gone with the wind? Start Генерация запроса Каталог объектов Выполнение запроса imdb-movie Victor Fleming Генерация ответа Victor Fleming directed Gone with the wind (get imdb-movie Gone with the Wind Director) «обертка»

36 Start. Omnibase Преимущества: Единый формат запросов к базе Естественность использования модели «объект-свойство-значение» Недостатки: Необходимость написания «обертки» для каждого источника данных

37 Start. Список внешних источников данных Wikipedia The World Factbook 2006 Google Yahoo The Internet Movie Database Internet Public Library The Poetry Archives Biography.com Merriam-Webster Dictionary WorldBook Infoplease.com Metropla.net Weather.com

38 Семантическая паутина Новая концепция развития сети Интернет Проблема машинного анализа информации, размещенной в Сети Вся информация в Сети должна размещаться на двух языках: Человеческом Компьютерном Для создания компьютерного описания ресурса используется формат RDF (Resource Description Framework), основанный на: Формат XML Триплеты «Объект – Отношение – Субъект»

39 Start. Natural Language Annotations Предлагается к каждому информационному блоку составлять аннотацию на естественном языке Компромисс между машинно-читаемым и естественным описанием информации В базе знаний хранятся только аннотации с прикрепленными ссылками на источники Эффективная организация доступа к информации произвольного типа: Тексты Изображения Мультимедиа Базы данных Процедуры Аннотации могут быть параметризованы

40 Start. Natural Language Annotations Внедрение аннотаций: Добавление аннотаций в RDF описания документов Использование параметризованных аннотаций (схем доступа к информации) Использование схем поиска ответов

41 Start. Добавление аннотаций How many people live in Kiribati? What is the population of the Bahamas? Tell me Guams population.

42 Start. Добавление аннотаций A Country in the CIA Factbook

43 Start. Параметризованные аннотации What is the country in Africa with the largest area? Tell me what Asian country has the highest population density. What country in Europe has the lowest infant mortality rate? What is the most populated South American country?

44 Start. Параметризованные аннотации what country in $region has the largest $attribute 3. ?x a :Country 4. ?x map($attribute) ?val 5. ?x :location $region 6. display(boundto(?x, max(?val))) :population 10. :area

45 Start. Параметризованные аннотации Is Canadas coastline longer than Russias coastline? Which country has the larger population, Germany or Japan? Is Nigerias population bigger than that of South Africa?

46 Start. Параметризованные аннотации $country-1s $att is larger than $country-2s $att 3. ?x a :Country 4. ?x map($att) ?val-1 5. ?y a :Country 6. ?y map($att) ?val-2 7. display(gt(?val-1, ?val-2))) :population 11. :area

47 Start. Схема поиска ответа What is the distance from Japan to South Korea? How far is the United States from Russia? Whats the distance between Germany and England? План ответа на такой вопрос: Найти столицу одной страны Найти столицу другой страны Вычислить расстояние между ними

48 Start. Схема поиска ответа distance between $country1 and $country what is the capital of $country1 := ?capital1 6. what is the capital of $country1 := ?capital2 7. what is the distance between ?capital1 and ?capital2 8. := ?distance display(?distance) 12.

49 Start. Natural Language Annotations Преимущества: Описание информации на универсальном, естественном языке Одна параметризованная аннотация может обрабатывать сотни вопросов Автоматизация процесса составления аннотаций Запросы к Omnibase также описываются с помощью аннотаций Недостатки: сложность внедрения

50 Start. Схема работы вопрос анализатор вопросов шаблон ответа Parser T-выражение База знаний WordNet аннотация2ответ Запрос к Omnibase ссылка Omnibase doc2 doc3 doc1 docN аннотация1 Фильтр passage1 passage2 passageM генератор ответов ответ … WWW

51 Start. Текущие разработки Обработка составных запросов и их автоматическая декомпозиция Наращивание баз с целью повышения избыточности информации Автоматизация анализа семантических связей в документах Внедрение аннотаций Особые стратегии поиска ответов для различных предметных областей

52 Статистические техники для анализа естественного языка

53 Пример The dog ate. s np det the noun dog vp verb ate

54 Проблема Salespeople sold the dog biscuits. s np noun Salespeople vp verb sold np det the noun dog noun biscuits s np noun Salespeople vp verb sold np det the noun dog np noun biscuits

55 Определение части речи Sentence The det can modal verb noun verb will modal verb noun verb rust noun verb

56 Принцип выбора части речи t – таг (det, noun, …) w – слово в тексте (can, will…) p(t | w) – вероятность того, что таг t соответствует слову w p(w | t) – вероятность того, что слово w соответствует тагу t p(t1 | t2) – вероятность того, что t1 идёт после t2

57 Эффективность Тупой – 90% Современные – 97% Человек – 98%

58 Скрытые модели Маркова noun house stock adj large small det a the

59 Другой подход (transformational tagging) Применяем тупой алгоритм. Есть набор правил: Поменять у слова таг X на таг Y, если таг предыдущего слова – Z. Применяем эти правила сколько-то раз. Работают быстрее Тренировка HMM vs. Тренировка TT (Отсутствие начальной базы)

60 Treebank Строим на основе предложения деревья, пользуясь существующими грамматическими правилами. Пример: (s (np (det The) (noun stranger)) (vp (verb ate) (np (det the) (noun doughnut) (pp (prep with) (np (det a) (noun fork)))))

61 Собственный Statistical Parser Проверка Есть готовые примеры из Pen treebank Сравниваем с ними Нахождение правил для применения Назначение вероятностей правилам Нахождение наиболее вероятного

62 PCFG (Probabilistic context- free grammars) sp np vp (1.0) vp verb np (0.8) vp verb np np (0.2) np det noun (0.5) np noun(0.3) np det noun noun (0.15) np np np(0.05)

63 Считаем вероятность построенного дерева s – начальное предложение – полученное нами дерево с – пробегает внутренние вершины дерева r(c) – вероятность применения r для с

64 Построение собственной PCFG. Простой вариант. Берём готовый Pen treebank Считываем из него все деревья Читаем по каждому дереву Добавляем каждое новое правило P(правило) = количество его вхождений, делённое на общее количество

65 Two state-of-the-art statistical parsers. Markov grammars Решают проблему существования очень редких правил Идея – вместо хранения правил, считаем вероятности того, что, например np = prep + … p(t1 | f, t2) – вероятность появления тага t2 после тага t1 внутри формы f.

66 Lexicalized parsing Каждой вершине дерева припишем слово (head), характеризующее её. p(r | h) – вероятность того, что будет применено правило r для узла с заданным h. p(h | m, t) – вероятность того, что такой h является ребёнком вершины с head = m и имеет таг t.

67 Lexicalized parsing Пример (S (NP The (ADJP most troublesome) report) (VP may (VP be (NP (NP the August merchandise trade deficit) (ADJP due (ADVP out) (NP tomorrow))))) p(h | m, t) = p(be | may, vp) p(r | h) = p(posvp aux np | be)

68 Lexicalized parsing the August merchandise trade deficit rule = np det propernoun noun noun noun Conditioning eventsp(August)p(rule) Nothing2.7*10^(-4)3.8*10^(-5) Part of speech2.8*10^(-3)9.4*10^(-5) h(c) = deficit1.9*10^(-1)6.3*10^(-3)

69 Восстановление смысловых связей (Causal Reconstruction)

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

71 Пример Ребро. Одна из нескольких парных дугообразных плоских костей, идущих от позвоночника к грудной кости и составляющих грудную клетку. Существует ли для каждого ребра пара? Из чего состоит грудная клетка? Кратно ли количество рёбер 2?

72 Задача CR (Causal Reconstruction) Имея такое описание предмета из энциклопедии, программа должна уметь отвечать на содержательные вопросы.

73 Пространство переходов (Transition space) Рассматриваем процессы, как цепочки переходов The perception of causality Качественные изменения Пример Удобно генерировать из словесных докладов

74 Смысловое моделирование (Causal modeling) Нефильтрованный ввод

75 Задачи человека, делающего входные данные для CR Количество Качество Связность Стиль

76 Проверка созданной модели

77 Проверка созданной модели Количество Добавляются ли новые объекты? Качество Согласованность Выполнимость Связность Создание смыслового отношения на множестве объектов Стиль Можно ли ужать созданную модель?

78 Упрощения. 3 типа предложений Событийные Задающие статические связи между объектами Связывающие

79 Дополнительный ввод Добавление новых статических связей и утверждений Определение событий Предшествующие события Правила вывода Правила подтверждения

80 2 уровня понимания созданной модели События Объекты

81 3 типа допустимых вопросов. Уровень объекта Вопросы связанные с изменением атрибутов объекта с течением времени Что происходит с позицией курсора во время завершения работы Windows?

82 3 типа допустимых вопросов. Уровень события Отношение событий между собой Как изменение длины волны света влияет на изменение ширины интерфереционной полосы в опыте Фраунгофера? Возможные отношения между событиями, описанными в вопросе, и уже созданной моделью Как изменение влажности может повлиять на настроение?

83 Пространство переходов Представление мира человеком с помощью событий и объектов Восприятие времени как последовательность breakpointов Качественное восприятие Соединение изменений

84 Состояния против изменений (States vs. Changes) Пример Changes используются в речи

85 Пример The contact between the steam and the metal plate appears. The concentration of the solution increases. The appearance of the film changes. The pin becomes a part of the structure. The water remains inside the tank.

86 Пример The contact between the steam and the metal plate appears. The concentration of the solution increases. The appearance of the film changes. The pin becomes a part of the structure. The water remains inside the tank.

87 Классификация изменений Общая APPEAR DISAPPEAR NOT-APPEAR NOT-DISAPPEAR

88 Специализация для NOT-DISAPPEAR Качественные атрибуты CHANGENOT-CHANGE Количественные атрибуты INCREASENOT-INCREASE DECREASENOT-DECREASE

89 Предикатная нотация Название изменения Атрибут Объекты-участники Точки времени

90 Пример APPEAR(contact,, t1, t2) INCREASE(concentration, the-solution, t3, t4) CHANGE(appearance, the-film, t5, t6) APPEAR(a-part-of,, t7, t8) NOT-DISAPPEAR(inside,, t9, t10)

91 Грамматики. Первая форма ::= ::= the { { | and } }* ::= CHANGE | APPEAR и т.д. The concentration of the solution increases.

92 Грамматики. Вторая форма ::= ::= [ [ ] { { | and} }* ] ::= becomes | becomes not | remains | remains not The water becomes a vapor.

93 Ссылки 1. CLEF. CLEF 2. WordNet. WordNethttp://wordnet.princeton.edu/ 3. Pen treebank. Pen treebank 4. Start. Start 5. TREC. TREC 6. Eugene Charniak [1997], Statistical Techniques for Natural Language Parsing 7. Gary C. Borchardt [1993], Causal Reconstruction

94 Ссылки 8. Boris Katz, Beth Levin [1988] Exploiting Lexical Regularities in Designing Natural Language Systems 9. Boris Katz and Jimmy Lin. Annotating the Semantic Web Using Natural Language. September, Boris Katz, Sue Felshin, Deniz Yuret, Ali Ibrahim, Jimmy Lin, Gregory Marton, Alton Jerome McFarland and Baris Temelkuran. Omnibase: Uniform Access to Heterogeneous Data for Question Answering. June, SEMLP. SEMLP 12. RCO. RCO