Н. Е. Бузикашвили, Г. А. Крылова, Д. В. Самойлов




Дата канвертавання20.04.2016
Памер237.86 Kb.

N-граммы в лингвистике

Н.Е. Бузикашвили, Г.А. Крылова, Д.В. Самойлов


Рассмотрены N-граммы как средство фиксации языковой реальности и как модельный конструкт. Разобрана связь модельных N-грамм и формальных грамматик. Обращено внимание на недостатки и противоречия, связанные с использованием вероятностных моделей.

Введение


Начнем с формального определения. Пусть задан некоторый конечный алфавит VT={wi}, где wi –отдельный символ. Множество цепочек (строк) конечной длины, состоящих из символов алфавита VT , называется языком на алфавите VT и обозначается L(VT ). Отдельную цепочку из языка L(VT) будем называть высказыванием на этом языке. В свою очередь, N-граммой на алфавите VT называется цепочка длиной N. N-грамма может совпадать с каким-то высказыванием, быть его подстрокой или вообще не входить в L(VT).

Приведем несколько примеров N-грамм.

П1. Алфавит – буквы русского языка плюс дефис, высказывания – слова русского языка. Тогда N-грамма – последовательность из N символов (букв и дефисов), принадлежащая одному слову.

П2. Алфавит – слова русского языка, высказывания – письменные фразы на русском языке. В этом случае N-грамма – последовательность из N слов одной фразы. Если высказывания – тексты, то N-грамма – последовательность из N слов одного текста.

П3. Алфавит – морфологические описания слов русского языка плюс знаки пунктуации, высказывания – соответствующие фразам и грамматически допустимые морфологические описания входящих в них слов. N-грамма – последовательность из грамматически допустимых описаний N подряд стоящих слов. (О грамматической допустимости – в фразах “Она разинула пасть” и “Она решила пасть” слово “пасть” имеет разные описания.) В [3] рассмотрена технология извлечения/построения N-грамм, соответствующих этому, синтаксическому уровню описания естественного языка.

П4. Алфавит – фонемы русского языка и специальный «символ» – пауза, высказывания – связный речевой поток. N-грамма – последовательность из N фонем/пауз.

П5. Алфавит – нуклеотиды, высказывания – цепочки ДНК. N-грамма – фрагмент длины N цепочки ДНК.

Ниже мы убедимся, что N -грамма при всей своей простоте и однозначности оказывается объектом, скорее перегруженным смыслами и связями. Отчасти именно исходная простота и теоретическая автономность этого объекта в немалой степени и провоцируют желание поместить N-граммы в более широкий контекст и придать им смысл, выходящий за рамки простой фиксации свойств языка. В результате на почти пустом месте возникла целая прикладная отрасль.


Используемые сокращения


АГ – автоматная грамматика

ЕЯ – естественный язык

КСГ – контекстно-свободная (бесконтекстная) грамматика

НФХ – грамматика в нормальной форме Хомского

САГ – стохастическая автоматная грамматика

СКСГ – стохастическая контекстно-свободная грамматика

СНФХ – стохастическая грамматика в нормальной форме Хомского

N-граммы в лингвистике – откуда и зачем


Для лингвистики N-грамма исходно и по сей день является маргинальной и изолированной сущностью. С чисто лингвистической точки зрения N-граммы (в любой из своих ипостасей) абсолютно бессодержательны, поскольку просто фиксируют языковую данность, нисколько не способствуя ее пониманию и не только не являясь основой сколь-нибудь серьезной объяснительной модели, но до последнего времени даже не входя в таковую. Внутри лингвистики они не имеют никакого базиса и одновременно сами не служат базисом ни для чего. Описание предложения в не имеющих отношения к его структуре терминах частей речи (пример П3) способно вызвать у классического лингвиста чувство близкое к брезгливости. Конечно, исследователь биграмм может быть преисполнен гордости, неся миру благую весть, что в предложении могут соседствовать, скажем, два прилагательных. Но вот что проясняет эта весть с точки зрения лингвиста, знающего, что в одном случае эти прилагательные окажутся из одной, а в другом – из разных частей предложения?

Бесполезность N-грамм для понимания языка в сочетании с их откровенной «неизощренностью» (достойное ли занятие подсчитывать тройки букв или слов) обусловили их относительно недавнее привнесение в лингвистический обиход, причем привнесение извне. Никаких внутрилигвистических предпосылок для пробуждения интереса к N-граммам быть не могло. По иронии судьбы, хотя N-граммы являются сугубо описательным конструктом, первая, кажется, попытка ввести N-граммы была предпринята самым неорганичным для них образом – как элемент объяснительной модели, заметим, модели откровенно, а потому и вызывающе наивной. Именно, в рамках ассоцианистской теории поведения была предложена модель построения фраз как марковского процесса. Понятно, утверждение буквально состоящее в том, что очередное произносимое слово определяется одним–двумя произнесенными перед ним, выглядит чрезмерно отважным. И напасть на такую, подчеркнем, не описательную и стало быть не прикрытую даже оговорками о параморфности (когда сообщается, что, да, конечно, в действительности процесс проистекает совсем не так, как в модели, но, заметьте, модель практически в точности предсказывает результат процесса), а объяснительную модель может каждый. Что и не приминул сделать, кстати, с сугубо лингвистических позиций Лэшли [19] (см. также [10]). Внимания, однако, заслуживает не объяснительный пафос псилингвистов-бихевиористов, а модель сама по себе. История же совершенно типична для бихевиоризма. Так, для какого-то явления предлагается достаточно продуктивная модель. При этом наиболее последовательные (читай, зычные) адепты всерьез без провозглашают, что именно согласно этой модели жизнь и устроена. Проходит время, экстремистские тирады вместе с их носителями забываются, а для модели находится ниша, в которой она успешно работает.

Итак, с легкой руки бихевиористов, в середине XX века на лингвистическое поле просачиваются N-граммы, точнее их «разновидность» в форме цепей Маркова. Предложенная модель речи, не важно, письменной или устной, – 1) объяснительная и 2) вероятностная. Забавно, что достоинства модели были непривычны для лингвистики, тогда как провальная для данной модели объяснительная направленность – близка. Действительно, объяснительный характер данной модели более чем нелеп, однако сами объяснительные модели для лингвистики – скорее правило, чем исключение. С другой стороны, правомерный в этой модели вероятностный аппарат для лингвистики был нехарактерен.

Воспроизведем цитату из того же сборника, в котором опубликована статья Лэшли. «Лингвисты не интересуются частотностями. Их внимание направлено на выяснение того, может ли данная структура появиться, но не как часто она появляется.» [22] – цит. по [6].

Если попытаться ответить, о каких «вероятностях» может идти речь применительно к N-граммам естественного языка, то обнаружится, что N-граммы не только маргинальны для лигвистики, но и парадоксальны. Действительно, рассматривая корпус текстов, мы не можем говорить ни о каком едином статистическом ансамбле. В крайнем случае мы будем иметь дело со смесями – разные авторы слишком индивидуальны и частотные различия будут проявляться у них даже на уровне N-грамм. (Впрочем, наиболее важный в прикладном отношении класс текстов является как раз достаточно однородным корпусом – это тексты на канцелярите.) Далее, сама частотная интерпретация вероятностей применительно к N-граммам выглядит не самой обоснованной. Предпочтительнее были бы субъективные вероятности. Но, очевидно, оценить субъективные вероятности N -грамм не сможет ни один человек в трезвом уме и здравой памяти, а единственный способ оценки этих «скорее субъективных» вероятностей – как раз частотный. Таким образом, «вероятность N-граммы» оказывается метафизическим свойством. Правда, это почти и не грех на фоне того как при использовании вероятностных моделей методологические (ошибочный выбор модели) огрехи благополучно сочетаются с методическими (применение методов, модели противоречащих), порой приводя к верным выводам (чаще неверным – о чем см., например, [4], [11] и обширный вероятностно-статистический фольклор).

Внутрилигвистическая мотивация для обращения к N-граммам связана с возникновением дескриптивной лигвистики ([5], [18]). Как следует из названия, установкой для нее служит принцип фиксации языковых явлений в сочетании, заметим, с их качественным теоретическим анализом. Модель дистрибутивных отношений Хэрриса [18] на своем нижнем уровне представляет ни что иное как N-граммное описание.

Однако значение N-грамм целиком исчерпывается их прикладной направленностью. Именно, в любой из своих ипостасей (на уровне букв, фонем или описания слов) N-граммы являются чрезвычайно эффективным инструментом решения в сущности одной вспомогательной задачи – отбраковки вариантов. Хотя содержательные задачи, в рамках которых эта отбраковка производится, весьма различны (доопределение частей речи и, как следствие, нормальных форм, выбор альтернатив при распознавании символов или предсказание допустимых/вероятных фонем в речевом потоке) и различны конкретные схемы использования (проход вперед, отход назад или одновременное разбегание вперед и назад), тем не менее в любом случае использование N-грамм сводится к наложению допустимых/вероятных N-грамм на имеющиеся данные, в частности, полученные на предшествующем шаге наложения, и перечислению допустимых или наиболее вероятных цепочек, согласующихся с таким наложением.

Модель N-граммы


Обозначим C(w) = C(w1w2wn-1wn) число вхождений строки w = w1w2wn-1wn в некую «генеральную совокупность всех текстов» рассматриваемого языка. Если бы эта гипотетическая совокупность исчерпывалась двумя текстами

“–Ааа, – сказал Иван Иванович.

Ааа, – отозвался Петр Петрович.”

и

“–Ааа, – сказал Иван Иванович.



Ыыы, – отозвался Петр Петрович.”

то для строки “ааа” (без учета заглавная буква или строчная) было бы 3 вхождения, а для строки “аа” – 6 (4 в первом тексте и 2 во втором). Положим, алфавит рассматриваемого языка содержит буквы (без учета регистра) и знаки пунктуации, тогда как пробел, переход на новую строку и начало текста – специальные разделители, не входящие в алфавит. Высказывание в таком языке – просто нераздельная последовательность символов, например, “–ааа,”.или “Петр”.

В
ероятность p(w) появления N-граммы w = w1 wn равна отношению C(w) к общему числу экземпляров всех встреченных в совокупности N-грамм:

В частности, для униграмм, то есть отдельных символов

г
де wi – символ алфавита VT, числитель – количество вхождений wi в “генеральную совокупность”, а сумма в знаменателе – просто общее число символов в ней.

Если вероятности появления символов в любой позиции цепочки независимы и одинаково распределены, то вероятность N-граммы

Э
то, в частности, значит, что любые перестановки символов строки w1wn-1wn имеют одну и ту же вероятность. Например, в языке из примера П1 (где алфавит – буквы русского языка и дефис) вероятность встретить выражения «красно-коричневый» та же, что и выражение «к-рснкрчнваооиеый», что плохо согласуется с нашими представлениями об ЕЯ (о том, что им можно доверять говорит то, что спросив, скажем, у 100 человек, какое из несуществующих слов «фопа» и «пфао» могло бы быть словом русского языка, мы гарантированно получим один и тот же ответ). Со статистической точки зрения вопрос о независимости и одинаковом распределении в условиях примера П1 решается просто. Дабы не перетруждать себя, сравним только распределения символов, стоящих в позиции перед буквой «ь», и символов-предшественников буквы «е». Гипотеза об одинаковости распределений незамедлительно будет отвергнута, правда на невысоком уровне значимости, так как пары <*ь> и <*е> встречаются недостаточно часто. Чтобы исключить малейшие подозрения о почему-то скопившихся в парах <*ь> выбросах, построим статистику, охватывающую всю выборку. Именно, рассмотрим все пары соседних символов, разделив при этом символы на две группы – гласные (Г) и все остальные (О). Подсчитаем число соответствующих символов, стоящих перед гласными и перед согласными. Окажется, что на сколь угодно высоком уровне значимости доли Г и О в парах вида <*Г > и <*О > различны. Вместе с гипотезой об одинаковости распределений придется отбросить и все основанные на ней выводы и практические советы типа «из альтернативных символов выбирать наиболее часто встречающийся».

Отступление. Столь популярное в компьютерной лингвистике правило «выбора наиболее частого» оказывается, применительно к языку, последним делом. Причем буквально. В языке нет стохастичности. Поэтому прежде чем использовать чуждое его природе «частотное правило», нужно исчерпать все остальные правила, основанные на анализе структуры. И только в последнюю очередь, когда все остальные возможности уже исчерпаны, имеет смысл прибегнуть к помощи частотности. Но и при этом, если есть возможно, следует выбирать не «самый частый», а самый устойчивый вариант. Языковые конструкции практически всегда недвусмысленны. Предложения типа «Весло задело платье», из которого не ясно что же было задето, – исключение, а отнюдь не правило. Чтобы избежать обсуждения вопроса о семантической однозначности фразы «Маша ела кашу» (какая Маша, какую кашу?), покривив душой, скажем, что имеем в виду грамматическую (лексико-синтаксическую) однозначность.

Если нет достоверного априорного знания о равенстве распределений символов в разных позициях строки, следует попытаться ввести контекстную привязку – через условные вероятности. Тогда если обозначить p(wj = w*j) вероятность того, что в j-й позиции строки стоит символ w*j, получим “контекстную” вероятность строки



p(w*1w*n) = p(wj = w*j | wi= w*i i j) p(wi= w*i  i j) (4)

Работать с (4) достаточно неудобно, поэтому перейдем к «односторонней» модели, а именно принятой при использовании N-грамм «правосторонней», в которой вероятность очередного символа строки задается в зависимости от предшествующих ему (n-1) символов, что записывается как p(wn | w1 wn-1). Тогда



p(w1wn-1wn) = p(wn | w1 wn-1) p(w1 wn-1) (5)

В терминах вероятности “быть справа” имеем




и
ли

В
ведя фиктивный символ «начало» и договорившись, что p(w1| w0) есть ни что иное как p(w1), можно переписать

Таким образом, моделью N-граммы оказывается марковская цепь (N–1)-го порядка, а задача оценивания статистических параметров N-граммы – хорошо изученной задачей оценивания параметров марковской цепи.



Замечание 1. Мы воспользовались гипотезой о контекстной зависимости и о форме этой зависимости – от предшественников в строке. Понятно, что модель (7*) ничуть не лучше модели (3) в том смысле, что также нуждается в проверке согласованности гипотезы и данных, по которым мы намереваемся оценить параметры модели. Иначе будет довольно огорчительно, когда получив несколькими разными методами вожделенные наборы оценок и выбрав “лучший” из них, мы вдруг чисто случайно обнаружим зыбкость допущений, на которых основывались последующие выводы. А оптимальные (эффективные, несмещенные и т.д.) оценки окажутся оптимальными, но в рамках неадекватной модели. В этой связи обратим внимание на тот казус, что до недавних пор в биостатистических исследованиях массовым было ошибочное использование критерия Стьюдента. С. Гланц [4] предложил остроумное объяснение, состоящее в том, что в книгах, по которым учились исследователи, первая глава была посвящена именно критерию Стьюдента. В этой связи и чуть забегая вперед, заметим, что вопрос согласованности марковской модели и данных (в отличие от оценивания параметров модели) не является для нее внутренним и потому в монографиях по цепям Маркова не освещается.

Продолжим рассмотрение модели (7*). Поскольку число N-грамм растет экспоненциально относительно их длины N, хотелось бы ее ограничить. Нужно это только в силу технических причин – желательно минимизировать обучающую выборку при сохранении ее полноты, что означает, что (почти) все N-граммы должны в эту выборку попасть и не по одному разу. Менее важные причины – желание иметь компактные описания данные и ускорить обработку. Однако произвольное сокращение N сопряжено с двумя проблемами. Первая, отчетливо осознаваемая, – чем меньше N, тем вероятнее, что произвольная N-грамма встречается в языке. Что снижает практическую ценность N-грамм, использование которых всегда ограничивается тем или иным вариантом отбраковки (при выборе допустимых цепочек букв, аминокислот, фонем и т.п.). Вторая проблема, как и первая, лежит не внутри модели, а во взаимодействии модели и данных. Это проблема их согласованности. Действительно, только что отвергнутая для П1 модель (3) есть ни что иное как модель униграмм. Модель (7*) может не противоречить данным при NN*, но окажется не согласована с ними при N<N*. И в таком случае, N* – минимальное допустимое для имеющихся данных (то есть для рассматриваемого языка L(VT)). Будучи, безусловно, важнее первой, эта проблема тем не менее попросту игнорируется.

О
ценкой вероятности N-граммы служит частота ее встречаемости:

Формула (8) для условных вероятностей триграмм использовалась в разработанной IBM системе распознавания речи. Как показали эксперименты, в обучающей выборке отсутствовало значительное число триграмм, встреченных при проверки системы. Однако по (8) вероятность таких триграмм равна нулю. Чтобы избежать этого, Джелинек [14] предложил линейную интерполяцию вероятности триграммы:




Здесь f(wi|…) – выборочные оценки, подобные (8):

г
де C – общее число всех экземпляров всех символов, а остальные величины в знаменателях – число соответствующих (N-1)-грамм, за которыми идет допустимый в рассматриваемом языке символ. В каждом слове это число на единицу меньше числа (N-1)-грамм, если число (N-1)-грамм больше нуля, и равно 0 в противном случае. Так в условиях примера П1 для выборки «строка слов» общее число 4-грамм равно 3+1 тогда как 4-грамм, имеющих продолжение – 2+0. Для 3-грамм эти величины соответственно 4+2 и 3+1.

Замечание 2. Крайне важно, что проблема неадекватности – это проблема вероятностной модели N-грамм. Она отсутствует для детерминированной модели, в которой о каждой N-грамме известна не «вероятность», а допустима N-грамма или нет. (Вспомним цитату из [22]). Детерминированная модель N-грамм адекватна для всех значений N. Замечательно в этом то, что детерминированная модель используется в точности в тех же приложениях и для тех же целей, что и вероятностная, но только, в отличие от вероятностной, гарантированно дает устойчивые выводы.

Поскольку приведенные модели рассчитаны на практическое использование, то прежде чем распространять на имеющиеся данные следствия модели, крайне желательно проверить ее согласованность с этими данными. И только после этого перейти к оцениванию параметров. К сожалению, не выполняется ни это условие, ни проверка значимости полученных оценок.


Формальные грамматики. Согласованность


Прежде чем рассмотреть N-граммы в рамках формально-грамматической модели, приведем необходимые в дальнейшем сведения из теории формальных грамматик ([12]).

Порождающей грамматикой G называется четверка G = <VN, VT, P, S>, где VT, как и раньше, – алфавит основных (терминальных), а VN – вспомогательных (нетерминальных) символов, SVN – начальный символ, с которого начинается порождение, P – набор правил порождения (подстановки), имеющих вид , где  – строка, содержащая хотя бы один нетерминальный символ,  – строка, включающая какие-то (хотя бы один) символы из объединенного алфавита V = VNVT. (Символы из VN будем обозначать заглавными, из VT – строчными буквами, как впрочем, и смешанные строки. Правила подстановки будем также называть продукциями, а выражения в их левых частях – посылками.) Говорят, что строка  = 12 непосредственно выводится из  = 12, если и существует правило  (здесь 1, 2 – строки символов из V = VNVT, возможно, пустые. Запись    означает, что существует последовательность непосредственных выводов, преобразующих строку  в строку . Языком L(G), порождаемым грамматикой G, назовем множество всех конечных строк из символов VT, выводимых в грамматике G. Множество всех непустых строк из символов алфавита R обозначим R+ (понятно, что верно L(G)  VT+).

Наиболее доступный формальному исследованию класс грамматик – контекстно-свободные (КСГ), в которых правила подстановки имеют вид Ai, где AiVN, а строка   V+. Далее все правила, посылкой в которых служит нетерминал A, будем для краткости называть A-правилами. Важный частный случай КСГ – автоматные грамматики (АГ). В них правила подстановки ограничиваются двумя типами: A  B и A  , где AVN. и   VT.

Определение стохастической грамматики GS полностью совпадает с приведенным с той лишь разницей, что всем правилам P = {ij} приписаны веса pij, называемые вероятностями и удовлетворяющие ограничениям 0< pij 1 и j pij= 1. То есть подстановки, имеющие одинаковые левые части (которые будем называть посылками), рассматриваются как случайная функции. Вероятность вывода p(  ) есть произведение вероятностей непосредственных выводов, приводящих от строки  к строке . Тем самым, неявно предполагается независимость вероятностей для разных посылок i, j.

Для стохастической грамматики GS назовем несущей грамматику G, полученную из GS выбрасыванием вероятностных весов.

Для грамматик “старше” КСГ, в которых одна посылка может содержать более одного символа, альтернативами оказываются не только подстановки с одинаковыми посылками, но и подстановки с непустым пересечением посылок. Это влечет два неприятных следствия. Первое, равно относящееся к “безвероятностным” и к стохастическим грамматикам, – неоднозначность вывода или, в других словах, невозможность одновременного примененения применимых к текущей строке посылок. Второе касается только стохастических грамматик – недостаточность присвоения вероятностей только внутри правил с одинаковыми посылками. Например, в стохастической грамматике с правилами



SA1A2

(с вероятностью 1 среди подстановок с данной посылкой)

A1  

(с вероятностью p среди подстановок с данной посылкой)

A1  

(с вероятностью 1-p среди подстановок с данной посылкой)

A2  

(с вероятностью 1 среди подстановок с данной посылкой)

посылка A2 – альтернатива посылке A1 и поэтому требуется задание совместных вероятностей на всех правилах с альтернативными посылками. В частности, в форме указания вероятности «применения посылок», а уже внутри класса правил с одной посылкой – вероятности конкретной подстановки. Для грамматик с односимвольными посылками (то есть КСГ) таких проблем не возникает.

Интересным свойством стохастической грамматики является ее согласованность. Содержательно, грамматика называется согласованной, если в процессе порождения вероятность получить на очередном шаге терминальную строку (строку из символов VT) стремится к 1, или, что то же самое, стремится к нулю математическое ожидание числа нетерминальных символов. Пусть рассматривается СКСГ с посылками {Ai} и, положим, в VN нет бесполезных символов, то есть {Ai} = VN и вместо “посылка” можно говорить “нетерминал”. Для каждого нетерминала Ai вычислим математические ожидания числа порождаемых им (по всем Ai-продукциям) нетерминалов. Эту величину для пары <порождающий нетерминал Ai, порождаемый нетерминал Aj> обозначим Eij. Таким образом, имеем уже знакомую нам стохастическую матрицу выводимости E = [Eij], то есть матрицу математических ожиданий числа порождаемых нетерминалов.

Э
та неудобочитаемая запись означает, что суммирование производится по всем k продукциям с посылкой Ai, pik обозначает вероятность каждой такой продукции, а N(j, ik) – число вхождений нетерминала Aj в правую часть продукции ik.

Например, для СКГС



SA1A2

(с вероятностью 1 среди подстановок с посылкой S)

A1  A2

(с вероятностью p1 среди подстановок с посылкой A1)

A1  

(с вероятностью 1-p1 среди подстановок с посылкой A1)

A2A1A1A1

(с вероятностью p2 среди подстановок с посылкой A2)

A2

(с вероятностью 1-p2 среди подстановок с посылкой A2)

{Ai} = VN = {A0=S, A1, A2}.

Матрица E имеет вид

Е
сли Et0 (где 0 – нулевая матрица) при t, то грамматика является согласованной. Условие согласованности СКСГ – выполнение ограничения на максимальное по абсолютной величине собственное значение матрицы E: ||<1 ([12], [15]).

Для частного случая СКСГ – стохастической АГ – в [Фу] дано специальное условие согласованности. Однако можно воспользоваться и только что приведенным критерием. В САГ любая порождаемая строка  имеет вид B, где   VT+ и BVN ( – пустая строка), то есть к  одновременно может быть применено ровно одно правило. Элементами матрица E для САГ будут суммы вероятностей продукций, имеющих в правой части нетерминал. Например, для САГ с правилами



QQ

(p)

Q

(1–p)

E – 11–матрица [p], и поскольку 0  p < 1, эта САГ согласована.

В прикладной лингвистике вопросу согласованности СКСГ почему-то придается необъяснимо важное значение. Вплоть до того, что несогласованная грамматика лишается права если не на существование, то на рассмотрение. В [1] показана безосновательность столь радикальных выводов из буквального переноса на лингвистическую почву одного из результатов теории ветвящихся процессов [13]. В плане лингвистического анализа несогласованные СКСГ ничем не отличаются от согласованных.


N-граммы и формальные грамматики


Если существование N-грамм как средства фиксации языковой реальности оправдано их прикладной полезностью, то N-граммы как объект теоретического анализа, т.е. модельный конструкт, откровенно провисают в воздухе. Модель N-грамм сама не является объяснительной и не входит ни в какую другую объяснительную модель. Эта изолированность N-грамм лишает их какой бы то ни было теоретико-лингвистической ценности. Тем сильнее позыв нарушить изоляцию.

В качестве естественного донора для модели N-граммы выступает формальная грамматика. Очевидная задача состоит в том, чтобы для формальной грамматики G определить все N-граммы, допустимые в порождаемом ею языке. В вероятностной формулировке – для стохастической грамматики GS определить вероятность каждой (допустимой) N-граммы.


Вероятности N-грамм в стохастических грамматиках


Напомним, что нормальной формой Хомского (НФХ) называется такая грамматика, в которой правила подстановки имеют вид

XYZ

(Хом1)

или




Xt

(Хом2)

где X, Y, Z VN, а tVT. Легко показать, что к нормальной форме Хомского приводится любая бесконтекстная грамматика.

С
ледуя [23], вычислим вероятности N-грамм в языке, порождаемом стохастической грамматикой СНФХ. Обозначив E(w1wn) математическое ожидание строки w = w1wn, а p(wn| w1wn-1) – условную вероятность символа wn после строки w1wn-1, получим

Т
аким образом, рекурсивно вычисляя ожидания E(w1wn-1), E(w1wn-2),… E(w1), найдем оценку вероятности p(wn| w1wn-1).

В НФХ нетерминал X может породить строку w = w1wn либо непосредственно – если строка w – символ из VT (правило (Хом2)), либо опосредованно – по правилу (Хом1). В последнем случае w порождается (через произвольное число шагов) либо как подстрока одного из нетерминалов Y или Z, либо как конкатенация хвоста строки, порожденной нетерминалом Y, и начала строки, порожденной нетерминалом Z. Таким образом, E(w|X) есть сумма p(Xw) (в СНФХ отлична от 0 только для униграмм), и сумма по всем подстановкам вида (Хом1): p(X YZ) {E(w|Y) + E(w|Z) + p(Y q w*) p(Z w**r)}, где конкатенация w*w**= w. Запишем общую формулу для E(w|X):

г
де q и r – подстроки, возможно пустые.

Например, применительно к триграммам компонента p(Y qw*) p(Z w**r) принимает вид



p(Y q1 w1) p(Z w2w3r1) + p(Y q2 w1w2) p(Z w3 r2)

Для биграмм эта компонента равна p(Y q w1) p(Z w2r), а для униграмм – нулю.

Алгоритм вычисления вероятностей начальных (префиксных) подстрок для СКСГ приведен в [17]. Заметим, что операция “инвертирования”, состоящая в замене подстановки XYZ на XZY, сохраняет принадлежность грамматики к классу НФХ. (В случае КСГ, не приведенных к НФХ, для получения “инвертированной грамматики” заменим в правилах подстановки и терминальные строки t1t2tn на их инверсный образ tntn-1 t1.Новая грамматика также останется КСГ.) Тогда наравне с исходной грамматикой рассмотрим и “инвертированную”. Применив к последней алгоритм [17], получим вероятности появления хвостовых подстрок для исходной грамматики.

Пример


Приведем пример из [23]. Дана СНФХ Gs* с правилами:

Sz

(с вероятностью p)

SSS

(с вероятностью 1–p)

Нужно вычислить математическое ожидание для униграммы z.

Формула (11) для униграммы имеет вид

П
рименительно к Gs* имеем

и
ли

Т
о есть

П
ри p<0,5 получаем отрицательное величину, а при p=0,5 соответственно – слева и + справа. Что вполне согласуется с условием согласованности грамматики.

И одновременно является победой неадекватно заимствованного формализма над лингвистическим, а равно и здравым смыслом. На том факте, что ни одна фраза на естественном языке не есть бесконечный (марковский, ветвящийся) процесс, основана простая идея грамматик с отсечением [1], позволяющая избежать ложных парадоксов и смещенных оценок.

Заключение


Двое ученых, получив грант, решили поохотиться на птиц. Встав пораньше, они взяли ружья и собак и отправились на охоту. Однако, встретив множество птиц, они вернулись ни с чем. “Послушай, – сказал один из филологов, – должно быть, мы делали что-то неверно”. “Возможно, – согласился, подумав, другой. – В следующий раз собак надо будет повыше подбрасывать”.

По Марвину Минскому ([9]).

По глубокому убеждению авторов все концептуальные достижения лингвистики (и что удивительно, не только лингвистики) за последние полвека пришлись на период 1950х–начала 60х годов. Для рассмотренного вопроса – это классические работы З.Харриса (дистрибутивные отношения – N-граммы) и Н.Хомского (грамматики). Последующее усилия были в значительной мере сосредоточены на разработке или заимствовании методов, что не могло не способствовать некоторой утрате предмета или подмене его сугубо модельными объектами.

Мы изложили свою точку зрения на историю вторжения и судьбу N-грамм в лингвистике. Похоже, что “гадкий утенок” превратился в монстра. Скромный, но эффективный инструмент зажил собственной жизнью – приобрел статус самостоятельного объекта, оброс заимствованными и не вполне органичными формализмами и, как результат заимствований, даже асимптотическими свойствами, что удивительно вдвойне – и в смысле способности исследователей истолковать несколько точек как стационарный процесс и в смысле выводов, рожденных таким толкованием. Мы попытались показать пути исправления ситуации, вместе с тем отдавая отчет, что история N-грамм – это не более чем один из примеров неизбежного в отсутствии содержательных идей торжества техники над здравым смыслом.

Однако это не единственная точка зрения. Приведем несколько цитат. “Впервые марковская модель, в которой подсчитывалась вероятность появления цепочки из N слов, была использована при распознавании слитной речи (Джелинек, 1976). … Использование N-грамм, в особенности биграмм и триграмм, получило в последнее время широкую популярность в зарубежной компьютерной лингвистике, поскольку выяснилось, что этот подход удачным образом сочетает в себе простоту и эффективность.» [8]. Затем авторы обзора [8] цитируют Джелинека: “У нас есть основания считать, что можно построить лучшие [чем N-граммы] модели языка… и тем не менее, каждый раз, когда мы создаем более или менее сложную модель, оказывается, что она не оправдывает наших ожиданий”. Что не удивительно, если учесть степень аккуратности, с которой проводилось вероятностное совершенствование исходно корректной модели. Разумеется, “хотели как лучше”. В результате вместо большего реализма было достигнуто прямое противоречие с реальностью, трактуемое, естественно, не в пользу последней. Однако чтобы оценить поистине радужные перспективы технического совершенствования, продолжим цитату из [8], посвященную системе синтеза речи: “Физическое паузирование привязано к приписыванию интонационных моделей, которое по умолчанию связано со знаками препинания”. То есть, если есть пунктуация – по умолчанию паузируем, а нет – так “на одном дыхании сто тысяч слов подряд”. Со своей стороны, мы почти готовы поверить, что не существует биомеханических ограничений, препятствующих слитному произнесению труднопроизносимых сочетаний звуков. Но еще более нам симпатична гипотеза о врожденном и безошибочном чувстве знака препинания, особенно в форме концепции праязыкового универсализма запятой. Возможно, дальнейшее развитие этой плодотворной идеи приведет к заключению, что чрезмерное, как может показаться, интонирование у народов, лишенных письменности, есть ни что иное как сублимация мольбы об элипсисе.

Один из авторов с удовольствием вспоминает нежные комментарии В.А. Звегинцева, посвященные кюнстам такого рода. Авторы также считают своим долгом выразить признательность А.А. Рывкину и А.С. Тангяну, методологические установки которых сильно повлияли на взгляды авторов, и Г.Н. Бузикашвили и А.В. Мисюреву за пробуждение интереса к теме.


Литература


1. Бузикашвили Н.Е. Стохастические грамматики с отсечением. // Настоящий сборник.

2. Бузикашвили Н.Е., Самойлов Д.В., Бродский Л.И., Усков А.В. Задача поиска в неструктурированном тексте и лингвистический анализ. // Интеллектуальные технологии ввода и обработки информации, М., 1998.

3. Бузикашвили Н.Е., Оберляйтнер М.С., Усков А.В. N-граммы русского языка. // Настоящий сборник.

4. Гланц С. Медико-биологическая статистика. Пер. с англ. под ред. Н.Е. Бузикашвили и Д.В. Самойлова. М., 1999.

5. Звегинцев В.А. Дескриптивная лингвистика. Предисловие к книге Г.Глисона «Введение в дескриптивную лингвистику». М., 1959.

6. Звегинцев В.А. Теоретическая и прикладная лингвистика. М., 1968.

7. История языкознания XIX–XX веков в очерках и извлечениях, ч. 2. Под ред. В.А. Звегинцева. М., 1965.

8. Кривнова О.Ф., Чарлин И.С. Паузирование при автоматическом синтезе речи. // Теория и практика речевых исследований. М. 1999.

9. Минский М. Остроумие и логика когнитивного бессознательного. // Новое в зарубежной лингвистике. Вып. XXIII. М., 1988.

10. Слобин Д., Грин Дж. Психолингвистика. М., 1976

11. Тутубалин В.Н. Теория вероятностей. М., 1972.

12. Фу К. Структурные методы в распознавании образов. М., 1977.

13. Харрис Т. Теория ветвящихся случайных процессов. М., 1966.

14. Brill E. et al. Beyond N-grams: Can linguistic sophistication improve language modeling?

15. Booth T. Probability Representation of Formal Languages. // IEEE Annual Symp. Switching and Automata Theory. 1969.

16. Jelinek F. Self-Organized Language Modeling for Speech Recognition. // Readings in Speech Recognition. 1989.

17. Jelinek F., Lafferty J. Computation of the probability of initial substring generation by stochastic context-free grammar. // Computational Linguistics, vol.17. 1991.

18. Harris Z.S. Method in Structural Linguistics. Chicago, 1951.

19. Lashley K. The problem of serial order in behavior. // Psycholinguistics: A book of readings, N.Y. 1961.

20. Schlesinger E. Sentence Structure and the Reading Process. Mouton. 1968.

21. Shieber S. Evidence against the context-freeness of natural language. // Linguistics and Philosophy, vol. 8. 1985.

22. Sola Pool I. Trends in Content Analysis Today. // Psycholinguistics: A book of readings, N.Y. 1961



23. Stolcke A., Segal J. Precise n-gram probabilities from stochastic context-free grammars. // Proceedings of the 32th Annual Meeting of ACL. 1994.


База данных защищена авторским правом ©shkola.of.by 2016
звярнуцца да адміністрацыі

    Галоўная старонка