Языковые модели сергей николенко



Скачать 59.25 Kb.
Pdf просмотр
Дата05.04.2017
Размер59.25 Kb.
Просмотров269
Скачиваний0

ЛЕКЦИЯ 13. ЯЗЫКОВЫЕ МОДЕЛИ
СЕРГЕЙ НИКОЛЕНКО
1. Введение
Зачастую мы можем понять разговорную речь даже если говорящий произ- носит слова не очень разборчиво. А почему? Потому что мы “настроены” на язык, на котором говорит оратор. То есть, в каждый момент времени, слущаю- щий ожидает, что говорящий скажет следующую фонему, букву и/или слово из достаточно ограниченного набора, характерного для данного языка, контекста и темы разговора.
Например, в славянских языках нас бы сильно удивила последовательность из пяти согласных подряд, в японском или корейском нас бы удивили звуки «х»
и «л», для фино-угорских языков характерны последовательности гласных, в некоторых языках – таких как литовский и эсперанто – весьма ограниченны наборы окончаний различных частей речи.
То есть, говоря о конкретном языке, можно говорить о некоторой формаль- ной грамматике, заданной на фонемах, буквах и словах этого языка.
2. Формальные грамматики
Формальная грамматика (далее просто «грамматика») в теории формаль- ных языков, предложенной Хомским (Noam Chomsky) в начале 60-x — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавитa.
Грамматика представляет собой четверку – терминалы (обозначается Σ),
нетерминалы (обозначается N) и набор правил вида α → β (обозначается R),
где одно правило является начальным (обозначается S, кроме того, S – это ещё и символ в левой части этого правила в R, т.е. для него α = S).
Терминал – объект, непосредственно присутствующий в словах языка, со- ответствующего грамматике, и имеющий конкретное, неизменяемое значение
(обобщение понятия «буквы»).
Нетерминал – объект, обозначающий какую-либо сущность языка (напри- мер: формула, арифметическое выражение, команда) и не имеющий конкрет- ного символьного значения. Таким образом, первый встреченный нами нетер- минал – S (начальный символ).
По иерархии Хомского грамматики делятся на следующие типы:

Тип 0 – неограниченные грамматики (unrestricted grammars), где воз- можны любые правила. Такие грамматики разпознаются машинами
Тьюринга.

Тип 1 – контекстно-зависимые грамматики (context-sensitive grammars),
с правилами вида
Законспектировал Ян Малаховски.
1

2 2
.2. Формальные грамматики xAy → xγy
A → w где, A – нетерминал, w – терминал, а x, y и γ – некоторые строки,
состоящие из терминалов и нетерминалов (контекст), где x и y могут быть пустыми строками, а γ – нет.

Тип 2 – контекстно-свободные грамматики (context-free grammars, CFG,
КС-грамматики), с правилами вида
A → BC
A → w где, A, B, C – нетерминалы, w – терминал. Этот тип грамматик рас- познается автоматами с магазинной памятью. Также следует упомя- нуть, что любая грамматика с правилами вида α → β, где α – нетер- минал, может быть переписана в вышеприведенном виде (называемом нормальной формой).

Тип 3 – регулярные грамматики (regular grammars), с правилами вида
A → wB
A → w где, A, B– нетерминалы, w – терминал. Этот тип грамматик распозна- ется конечными автоматами.
Для практического применения найбольший интерес представляют контекстно- свободные грамматики, поскольку класс языков, распознаваемых ими, доста- точно широк, и, в то же время, для них существуют алгоритмы построения автоматов с магазинной памятью, распознающих какой-либо язык, по набо- ру правил R соответствующей грамматики. Примеры таких алгоритмов: SLR,
LL(1), LALR, ... (см. [1]).
Пример 1
Рассмотрим, например, предложение “люблю грозу в начале мая” и следующую контекстно-свободную грамматику:

S → сказуемое дополнение

сказуемое → глагол

дополнение → существительное определение

определение → предлог дополнение | существительное где S – начальный символ грамматики.

Лекция 13. Языковые модели
3
Тогда дерево разбора такого предложения будет выглядеть следующим образом:
Рис. 1. Дерево разбора предложения «люблю грозу в начале мая». Серым цветом выделены терминалы.
3. Естественные языки
Не смотря на то, что существуют человеческие (те, на которых люди го- ворят) языки, для которых вполне можно было бы построить приемлимую контекстно-свободную грамматику (так называемые “плановые” языки – на- пример, Esperanto и Ido), большая часть натуральных языков не может похва- статься такой возможностью. Это связано с тем, что в натуральных языках существует неимоверное количество двусмысленных конструкций (как пра- вило ещё и зависимых от контекста), которые невозможно представить КС- грамматикой. Кроме того, существуют фразы, которые вообще являются непра- вильными с точки зрения грамматики, в то же время используемые нами.
Выхода из данной ситуации два:

сделать распознаваемый язык очень простым,

сделать грамматику с огромным количеством правил.
Для машинной обработки второй подход, очевидно, не имеет смысла из-за сво- ей потенциальной трудоёмкости (в идеальном случае нам бы хотелось полу- чать результаты в реальном времени, оратор нас ждать не будет). Первый же подход широко используется.
Итак, мы решили, что для разбора естественных языков мы выберем некото- рое ограниченное подмножество грамматических конструкций нашего языка,
построим небольшую КС-грамматику и будем ей пользоваться.
4. SCFG
Для прозорливого читателя после предыдущей фразы должно остаться непо- нятным то, как именно мы будем использовать построенную грамматику. Ведь нас мало интерисуют ответы вида «Да/Нет» (правда ли, что вход не проти- воречит грамматике?) на предложенную парсеру строку символов. В самом начале лекции мы говорили, что после получения очередного элемента из Σ

4 2
.5. Inside-Outside
(терминалы, они же элементы языка) из потока, мы хотим на выходе наше- го алгоритма получить список найболее вероятных вариантов разбора (может быть корректнее “продолжения”? ведь набор терминалов ограничен и мы мо- жем пытаться предсказывать следующий) фразы.
Эту задачу решают вероятностные КС-грамматики (stochastic context-free grammars, SCFG, probabilistic context-free grammars, PCFG, ВКС-грамматики).
SCFG – это КС-грамматика, где к каждому правилу приписана вероятность его применения, т.е. если KC-грамматика была четвёркой (Σ, N, R, S), то
ВКС-грамматика – это пятёрка (Σ, N, R, S, P ), где P – отображение из R в промежуток [0, 1] (вероятность правила). В широком смысле, ВКС-грамматики
– это такое же расширение КС-грамматик, как скрытые марковские модели
(см. лекцию #9) – расширение регулярных грамматик.
Пусть все правила грамматики записаны в нормальной форме:
• A
i
→ A
m
A
n
• A
i
→ w k
где A
i
– нетерминалы, w k
– терминалы, а вероятность каждого правила вы- числяется по формуле:
p(A
i
→ α) =
#(A
i
→ α)
β
#(A
i
→ β)
где #(A
i
→ α)
– количество “срабатываний” правила A
i
→ α
для некоторого текста.
Интересующий нас результат – это вероятность p(S ⇒ W = w
1
w
2
...w
T
|G)
,
где G – грамматика, S – ее начальный символ, W – некоторая цепочка термина- лов w i
(количество которых T ), а символ “⇒” следует читать как «порождает».
Тогда с учетом вышеприведенных правил мы могли бы вычислить искомую вероятность для конкретного дерева разбора следующим образом:
p(S ⇒ W = w
1
w
2
...w
T
|G) = p(S → A
m
A
n
)p(A
m
→ ...)p(A
n
→ ...)...
5. Inside-Outside
Однако, нас интересует p(S ⇒ W ) в общем случае. Поэтому вводят функции inside и outside:
inside(j, A
i
, k)
=
p(A
i
⇒ w j
...w k
),
определена для ∀j ≤ k outside(s, A
i
, t)
=
p(S ⇒ w
1
..w s−1
A
i w
t+1
...w
T
),
определена для ∀s ≤ t
Учитывая, что правила грамматики не зависимы и записаны в нормальной форме, имеем:
p(S ⇒ W ) =
i inside(j, A
i
, k)outside(j, A
i
, k) = inside(1, S, T )
Для самих же функций inside и outside вводят следующие реккурентные соотношения:
inside(j, A
i
, k)
=
m,n,l inside(j, A
m
, l)p(A
i
→ A
m
A
n
)inside(l + 1, A
n
, k)
inside(j, A
i
, j)
=
p(A
i
→ w i
)

Лекция 13. Языковые модели
5
и outside(j, A
i
, k)
=
m,n
[
l p(A
m
→ A
n
A
i
)outside(l, A
m
, k)inside(l, A
n
, j − 1) +
+
l p(A
m
→ A
i
A
n
)outside(j, A
m
, l)inside(k + 1, A
n
, l)]
outside(1, S, T )
=
1
где l ∈ [j, k], а m, n – пробегают по всем возможным значениям.
6. Адаптация алгоритма Баума-Велха
Теперь мы умеем считать p(S ⇒ W ), однако парсить книги для получения вероятностей правил из R – достаточно трудоемкое занятие. Поэтому обычно для этих целей используют адаптацию алгоритма Баума-Велха, где функция
ξ
имеет вид:
ξ(i, m, n, s, t) = p(A
i
⇒ w s
...w t
, A
i
→ A
m
A
n
) =
1
p(S ⇒ W )
×
×
k p(A
i
→ A
m
A
n
)inside(s, A
m
, k)inside(k + 1, A
n
, t)outside(s, A
i
, t)
а пересчет значений вероятностей правил производят по формуле:
p(A
i
→ A
m
A
n
) =
s,t
ξ(i, m, n, s, t)
m,n,s,t
ξ(i, m, n, s, t)
В качестве начальных распределений обычно используют вероятности веток начального правила S.
7. N-граммы
Другой очень простой и часто используемый метод, применяемый для со- здания языковых моделей – N-граммы. Пусть известны вероятности p(w k
|w k−N
, w k−N +1
...w k−1
),
т.е. вероятности того, что текущее (при разборе цепочки) слово – это w k
, а N
предыдущими словами были w k−N
, w k−N +1
...w k−1
Тогда вероятность некоторой цепочки beg w
1
...w
T
end
, где beg и end – спе- циальные символы начала и конца строки (цепочки), можно вычислить как p(beg w
1
...w
T
end) = p(w
1
|beg)p(w
2
|w
1
)...p(w
T
|w
1
...w
T −1
)p(end|w
1
...w
T
)
Пример 2
Рассмотрим следующий текст:
«однажды ежи прочел книгу ежи взял и прочел книгу ежи прочел книгу о себе»
Тогда для N-граммы с N = 1 вероятности для слова «ежи» будут иметь вид:
• p(
ежи|beg) = 2/3,
• p(
ежи|однажды) = 1/3.
А для слова «книгу»: p(книгу|прочел) = 1.

6 2
.8. N-граммы
8. *
Список литературы
[1] Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман «Компиляторы: прин- ципы, технологии и инструментарий»; «Compilers: Principles, Techniques, and Tools» — 2
изд. — М.: «Вильямс», 2008. — ISBN 978-5-8459-1349-4



Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал