close

Вход

Забыли?

вход по аккаунту

?

Natural Language Processing

код для вставкиСкачать
Вычислительная лингвистика
Фёдор Царёв
tsarev@rain.ifmo.ru
02 ноября 2005 года
Язык – исторически сложившаяся
система звуковых, словарных и
грамматических средств,
объективирующая работу мышления
и являющаяся орудием общения,
обмена мыслями и взаимного
понимания людей в обществе
Толковый словарь русского языка
Цель
• Дать общее представление о моделях и
методах вычислительной лингвистики,
не вдаваясь особо в подробности
План доклада
1.
2.
3.
4.
5.
Что это такое?
История
Основные методы
Конкретный пример
Открытые вопросы и перспективы
План доклада
1.
2.
3.
4.
5.
Что это такое?
История
Основные методы
Конкретный пример
Открытые вопросы и перспективы
Что это такое?
• Это наука, рассматривающая методы
создания приложений, использующих
знания о языке
Зачем это нужно?
• Огромное количество информации
доступно в форме текстов
• Создание новых типов интерфейсов
• Проверка правописания
• Автоматический перевод
• Информационный поиск
• Системы автоматического ответа на
вопросы
Простой пример
• Программа wc в UNIX’е
– Когда считает байты и строки – просто
программа
– Когда считает слова – использует знания о
языке
6 разделов языкознания
•
•
•
•
•
Фонетика
Морфология
Синтаксис
Семантика
Pragmatics – использование языка для
достижения неких целей
• Discourse – изучение лингвистических
категорий, более широких, чем
предложение
Основная проблема неоднозначность
• Вход называется неоднозначным, если
существует несколько различных
лингвистических структур для него
• Пример: I made her duck
План доклада
1.
2.
3.
4.
5.
Что это такое?
История
Основные методы
Конкретный пример
Открытые вопросы и перспективы
1940-1957
• Два подхода:
– Автоматный (Kleene, Chomsky, Backus,
Naur)
– Теоретико-информационный, или
вероятностный (Shannon)
• Из возможных вариантов выбрать
наиболее вероятный
• 1952 год – статистическая система
распознавания цифр на слух
Тест Тьюринга
• Предложен Аланом
Тьюрингом (Alan
Turing) в 1950 году
• Игра для трех
игроков
• Цель компьютера –
обмануть людей
• Цель человека –
помочь обнаружить
компьютер
Человек
Игрок 1
Игрок 2
1957-1970
• Два подхода:
– Символический (symbolic)
– Стохастический (stochastic)
1970-1983
• Четыре парадигмы:
– Stochastic
– Logic-based
– Natural language understanding
– Discourse modeling
1983-1993
• Finite-state phonology
• Finite-state morphology
• Использование эмпирических моделей
1994-…
• Использование всего, что
использовалось когда-либо…
План доклада
1.
2.
3.
4.
5.
Что это такое?
История
Основные методы
Конкретный пример
Открытые вопросы и перспективы
Разрешение неоднозначности
• Многие алгоритмы разрешают
неоднозначность на том или ином
уровне
– Лексическая неоднозначность
– Синтаксическая неоднозначность
– и т.д.
Алгоритмы и модели процедурные модели
• Детерминированные конечные
автоматы
• Недетерминированные конечные
автоматы
• Finite-state transcuders (могут
записывать в выходной поток)
• Взвешенные автоматы
Алгоритмы и модели –
описательные модели
• Регулярные выражения
• Контекстно-свободные грамматики
• Их вероятностные варианты
Пример
• Грамматика для простых предложений
английского языка
<предложение> ::=
<вопросительное предложение> |
<повествовательное предложение>
Пример (продолжение)
<вопросительное предложение> ::=
<вопросительное слово>
<вспомогательный глагол>
<подлежащее> <основной глагол>
<второстепенные члены предложения>
<повествовательное предложение> ::=
<подлежащее> <сказуемое>
<второстепенные члены предложения>
Алгоритмы и модели –
алгоритмы
• Поиск по некоторому множеству
гипотез:
– Поиск в глубину
– Динамическое программирование
– Различные вероятностные варианты
Алгоритмы и модели – другие
•
•
•
•
Машинное обучение
Использование логики первого порядка
Языки типа PROLOG’а
Нейронные сети
Эти подходы сегодня рассматриваться
не будут
План доклада
1.
2.
3.
4.
5.
Что это такое?
История
Основные методы
Конкретный пример
Открытые вопросы и перспективы
Алгоритм Витерби
• Применяется для распознавания речи
• Пусть уже входной звук разбит на
последовательность известных нам
звуков
• Осталось выяснить, что конкретно было
сказано
Постановка задачи – 1
• Дан ориентированный граф G=<V,E>
• Дано множество звуков Σ
• Каждой дуге uv сопоставлены:
– Звук σ(uv)
– Вероятность p(uv) издать этот звук
• Заданы:
– Начальная вершина v0
– Последовательность звуков w1…wn
Постановка задачи – 2
• Сумма вероятностей на дугах,
исходящих из некой вершины, равна
единице
• Произнесения последовательных звуков
независимы
• Найти наиболее вероятный путь в графе
Решение – динамическое
программирование
• Пусть a(i, j) – максимальная
вероятность «попасть» в вершину i
после произнесения
последовательности звуков w1w2…wj
Решение – инициализация и
рекуррентное соотношение
• Инициализация: a(v0,0) = 1
• Рекуррентное соотношение:
a(v,k) max a(u,k 1 ) p(uv)
uv E
σ(uv) w k
Как теперь получить ответ?
План доклада
1.
2.
3.
4.
5.
Что это такое?
История
Основные методы
Конкретный пример
Открытые вопросы и перспективы
Перспективы
• Создание интерфейса с пользователем,
использующего естественный язык
• Создание систем, способных
анализировать тексты
Заключительный слайд
Если не запомнили ничего другого:
• Приложения, использующие знание
языка – очень перспективная область
• Основная проблема – неоднозначность
• В вычислительной лингвистике
широко используются методы теории
алгоритмов
Вопросы?
Источники
• http://www.cs.colorado.edu/~martin/slp.html
• Кормен, Лейзерон, Ривест «Алгоритмы.
Построение и анализ»
Документ
Категория
Презентации по информатике
Просмотров
8
Размер файла
140 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа