Содержание » Вопросы и материалы к экзамену по предмету ЛЗКС

Ниже представлен краткий обзор материала по каждому вопросу. Данный обзор не является ни полным, ни достаточным ответом на вопросы. Для успешной сдачи теоретического вопроса на экзамене абсолютно необходимо читать дополнительные материалы.

Что такое компьютерная лингвиcтика

Компьютерная лингвиcтика, она же математическая лингвистика - наука, решающая задачи моделирования, распознавания и обработки естественного языка с помощью компьютеров.

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

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

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

Дополнительные материалы:

Направления исследований

Основные направления исследований в компьютерной лингвистике (с указанием их англоязычных эквивалентов для упрощения поиска информации) следующие:

Дополнительные материалы:

Вклад Ноама Хомского в компьютерную лингвистику

Ноам Хомский стал первым, кто проложил мост между лингвистикой и компьютерными науками. Его формальные грамматики и языки, обладающие четкими синтаксическими структурами, доступными для разбора на компьютере, являются уже более 50-ти лет основным средством общения человека и компьютера. Они же позволили применить компьютеры для машинной проверки правописания и синтаксиса, машинного перевода - всего, что сейчас доступно современному человеку. Как бы ни были несовершенны программы-переводчики, но они позволяют преодолеть языковый барьер и узнать чем живут, что думают и что делают люди других стран и народов. Как ни удивительно, но наша современная lingua franca, английский, не помогает если вы работаете с людьми из традиционно закрытой (или недостаточно открытой) для внешнего мира культурой. Автору этих строк кажется что японцы могут быть таким примером. Знаниям, рождающиеся в их среде, зачастую нужно около 10 лет чтобы стать доступными остальному миру. Например, эта статья из области компьютерных наук не существует ни на каком языке кроме японского. При этом мы можем ее прочитать по-английски, а качество перевода выглядит хоть и не идеальным, но вполне достаточным.

Трансформационные грамматики, предложенные Хомским для формализации естественных языков, хоть и сложны с вычислительной точки зрения, но являются на сегодня единственной абстракцией, способной описать естественный язык для работы с ним на компьютере. К слову, cложность трансформационных грамматик означает, что для их построения для естественного языка требуется несколько десятков лет работы, что и определило их практическую неприменимость. На сегодня не существует полных трансформационных грамматик для современных языков. Идея траснформации синтаксических структур используется только для разрешения неоднозначностей в контекстно-свободных грамматиках. Ниже эти грамматики описаны подробнее.

Еще одна идея Хомского - идея о глубоких синтаксических структурах ценна больше, чем все трансформационная грамматика. Но и она еще не дождалась проверки на практике. Идея состоит в том, что в предложениях языка заложена "глубокая синтаксическая структура", которая представляет глубокие семантические отношения. На поверхности-же лежит синтаксическая структура, выражающая только фонологические отношения. Когда человек конструирует предложение, эти глубокие структуры преобразовываются в поверхностные с помощью трансформаций (а, соответственно, грамматика этих структур и преобразований будет упомянутая выше трансформационная грамматика). Что важно в этой идее - это мнение Хомского о том, что синтаксис так или иначе выражает семантику. Иными словами, смысл предложения языка заложен не в человеке, а в нем самом. Это дает надежду на то, что компьютерная программа, устроенная совершенно иначе, чем человек, сможет когда-нибудь нас не только услышать, проверить наше правописание и синтаксис, а и понять нас (а может быть и говорить с нами). Кстати, надеяться в этом случае мы можем и на общение с другой (инопланетной!) расой.

Дополнительные материалы:

Вклад Карен Джоунс в компьютерную лингвистику

Карен Джоунс (Karen Spärck Jones) как человек, занимавшийся компьютерной лингвистикой, нам интересна по двум причинам.

Во-первых, Карен предложила концепцию IDF - inverse document frequency. Эта концепция лежит в основе работы и в основе успеха всех современных поисковых систем без исключения - Google, Rambler, Yandex, Yahoo, etc. Поисковая система ищет документы по ключевым словам (например мы ищем в Google словосочетание "американский лопух"). Естественно, что чем больше раз ключевые слова встречаются в документе, тем больше нам этот документ подходит. Однако некоторые слова употребляются чаще других (такие как "американский" в нашем примере). Это означает, что слова, которые употребляются реже, являются более ценными. Т.е. чем реже слово встречается в текстах, доступных поисковой системе, тем ценнее это слово. Эта идея и была названа IDF - Inverse Document Frequency. Вы можете поискать в Google по словосочетанию "американский лопух" и убедиться что сначала будут найдены лопухи, а потом другие американские вещи.

Во вторых, она была одной из немногих женщин, занимающихся компьютерной лингвистикой и активно пропагандирующей среди лингвистов эту науку. Она верила, что современные ей лингвисты слишком глубоко ушли в теорию и их результаты их работ нельзя использовать на компьютерах (как она говорила, computational linguistics потеряла "computational"). Она также считала, что женщины должны больше внимания уделять компьютерным наукам и компьютерной лингвистике. Ее словами были "computation is too important to leave it to men"! Позволю себе выразить надежду, что студентки, читающие эти строки, прислушаются к совету Карен...

Дополнительные материалы:

Определение формальных языков и грамматик

Формальный язык L состоит из 4х элементов:

L = (T, N, S, P)

T - множество терминалов, т.е. тех элементов, из которых состоят предложения языка (терминальных элементов, из которых уже ничего не сотворить)
N - множество нетерминалов, т.е. синтаксических конструкций (составляющих), которые составляют предложение
S - корневой символ грамматики, т.е. та синтаксическая составляющая, из которых начинается конструирование предложения
P - множество продукций, т.е. правил построения предложений из корневого символа

Например, для предложения

мама мыла раму

формальная грамматика будет следующей:

Терминальными элементами, очевидно, являются слова в предложении, т.е.

T = { мама, мыла, раму }

Синтаксическая структура этого простого предложения состоит из фразы существительного (Noun Phrase, NP) и фразы глагола (Verb Phrase, VP). При чем фраза существительного - это само существительное ("мама"), а фраза глагола - это глагол и дополнение, выраженное существительным. Таким образом, нетерминалы грамматики:

N = { NP, VP, Noun, Verb }

Корневой символ - самая общая синтаксическая составляющая - это само предложение (Sentence), т.е.

S = Sentence

Корневой символ - такая-же синтаксическая составляющая, т.е. нетерминал, и, соответсвенно, должен быть внесен в список нетерминалов:

N = { NP, VP, Noun, Verb, Sentence }

Множество продукций просто выражает правила построения одной синтаксической структуры из другой так, как это было описано выше:

Sentence -> NP VP
NP -> Noun
Noun -> мама
VP -> Verb Noun
Verb -> мыла
Noun -> раму

Два правила (две продукции) для одного нетерминала Noun объединяются в одно:

Noun -> мама
      | раму

Итак, формальная грамматика, принимающая предложение "мама мыла раму":

G = (T, N, S, P)
T = { мама, мыла, раму }
N = { NP, VP, Noun, Verb, Sentence }
S = Sentence
P:
    Sentence -> NP VP
    NP -> Noun
    VP -> Verb Noun
    Verb -> мыла
    Noun -> мама
        | раму

Заметьте, что формальная грамматика записана с соблюдением определенных правил, которых необходимо строго придерживаться.

Дополнительные материалы:

Порождение предложений формальных языков

Мы утверждали, что грамматика, полученная выше, принимает предложение "мама мыла раму". Слово "принимать" здесь означает, что предложение соответствует грамматике и может существовать компьютерная программа, читающая это предложение и говорящая, что оно правильное с точки зрения синтаксиса.

Грамматика, принимающая предложения языка, также умеет и порождать. Породить - значит применить продукции грамматики для построения предложения.

Порождение начинается с корневого символа:

Sentence

Корневой символ заменяется согласно продукциям грамматики. Наша грамматика включала продукцию "Sentence -> NP VP". Поэтому мы можем записать порождение, в котором заменим предложение на фразу существительного и фразу глагола:

Sentence => NP VP

Знак "=>" означает порождение и тем отличается от знака "->", используемого в продукциях/правилах.

Полученное предложение "NP VP" не закончено, потому как предложение русского языка состоит из слов, а не из синтаксических конструкций. Поэтому порождения должны быть продолжены и все нетерминалы постепенно заменены на терминалы. Так, заменим NP согласно продукции "NP -> Noun" на Noun:

Sentence => NP VP => Noun VP

Заменим VP согласно продукции "VP -> Verb Noun"

Sentence => NP VP => Noun VP => Noun Verb Noun

По аналогии проведем все остальные замены и закончим порождение предложением, состоящим только из терминальных символов:

Sentence => NP VP => Noun VP => Noun Verb Noun => мама мыла раму

Записанное выше и является примером порождения предложения. При этом, можно заметить, что наша грамматика позволяет заменять любой из нетерминалов Noun словом "мама" либо "раму". Поэтому, существуют еще три порождения:

Sentence => NP VP => Noun VP => Noun Verb Noun => мама мыла мама
Sentence => NP VP => Noun VP => Noun Verb Noun => раму мыла мама
Sentence => NP VP => Noun VP => Noun Verb Noun => раму мыла раму

С точки формальной грамматики, все 4 предложения являются синтаксически правильными:

мама мыла раму
мама мыла мама
раму мыла мама
раму мыла раму

Формальные языки против естественных языков

В приведенном выше примере из четырех предложений некоего формального языка только два из них являются правильными предложениями русского языка:

мама мыла раму
раму мыла мама

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

Можно попытаться улучшить нашу грамматику, внеся идею падежей в нее:

G = (T, N, S, P)
T = { мама, мыла, раму }
N = { NP, VP, Noun, Verb, Sentence }
S = Sentence
P:
    Sentence -> NP VP
    NP -> NominativeNoun
    VP -> Verb AccusativeNoun
    Verb -> мыла
    NominativeNoun -> мама | рама
    AccusativeNoun -> маму | раму

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

Sentence => NP VP => Noun VP => NominativeNoun Verb AccusativeNoun => мама мыла маму
Sentence => NP VP => Noun VP => NominativeNoun Verb AccusativeNoun => мама мыла раму
Sentence => NP VP => Noun VP => NominativeNoun Verb AccusativeNoun => рама мыла маму
Sentence => NP VP => Noun VP => NominativeNoun Verb AccusativeNoun => рама мыла раму

С точки зрения грамматики как русского так и нашего формального языков, все такие предложения являются правильными. Но теперь появляется новая проблема - два последних не имеют смысла. Если верить Хомскому и его глубоким синтаксическим структурам, то нам нужно модифицировать грамматику так, чтобы бессмысленных конструкций не было.

Но перед тем как сделать это, отметим несколько важных моментов, касающихся отношения естественного языка (например, русского) и нашей формальной грамматики:

  1. Формальная грамматика в нашем примере является контекстно-свободной (см. ниже про контекстно-свободные грамматики и языки). Мы можем использовать любое слово, представляющее синтаксическую структуру на любом месте, ей дозволенном. В нашем примере мы могли подставить как "маму" так и "раму" на место AccusativeNoun независимо от контекста, в котором этот AccusativeNoun используется (иными словами независимо от того, кто моет - "мама" или "рама").
  2. формальный язык, порождаемый контекстно-свободной грамматикой, тем не менее очень похож на русский. Это говорит о том, что контекстно-свободная грамматика является достаточно хорошей моделью грамматики естественного языка.
  3. Большую часть проблем несоответствия контекстно-свободного языка и естественного языка можно решить применением идеи контекстной зависимости (см. ниже про контекстно-зависимые грамматики).

Дополнительные материалы:

Иерархия языков и грамматик Хомского

Формальные грамматики, подпадающие под определение G = (T, N, S, P) могут быть разными. В зависимости от ограничений, накладываемых на множество продукций P выделяют следующие виды грамматик (и, соответственно, языков):

Дополнительные материалы:

Регулярные языки и грамматики

В регулярных грамматиках левая часть продукций содержит один нетерминал, а правая часть - либо терминал либо терминал и нетерминал либо пустую строку (ε).

Праворегулярная грамматика имеет продукции вида:

  1. A -> a
    где A - нетерминал, a - терминал
  2. A -> aB
    где A и B - нетерминалы, a - терминал
  3. A -> ε
    где A - нетерминал, ε - пустая строка

Леворегулярная грамматика имеет продукции вида:

  1. A -> a
  2. A -> Ba
  3. A -> ε

Например, такая грамматика регулярна:

A -> aA
A -> a

а такая - нет:

S -> A B
A -> aA | a
B -> bB | b

Примером регулярной грамматики может быть грамматика нашего "языка" общения с телевизором.

TV -> power_on Watch
Watch -> switch_channel Watch
Watch -> power_off

Здесь power_on, switch_channel, power_off - терминалы языка, т.е. кнопки, которые мы нажимаем на телевизионном пульте. A TV и Watch - нетерминалы, т.е. своеобразные синтаксические конструкции нашего примитивного языка общения с телевизором. Естественно, TV - корневой символ грамматики языка, из которого и начинается порождение предложений языка.

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

TV => power_on Watch => power_on switch_channel Watch =>
      power_on switch_channel switch_channel Watch =>
      power_on switch_channel switch_channel power_off

А вот как порождается то предложение, которое очень часто говорит своему телевизору автор этих строк:

TV => power_on Watch => power_on power_off

Заметьте, что грамматика позволяет порождать предложения с просмотром одного, двух, трех и так далее каналов. Мы можем применять правило Watch -> switch_channel Watch сколь угодно долго (до бесконечности). Таким образом, в языке общения с телевизором количество возможных предложений ничем не ограничено, более точно, оно бесконечно. Несмотря на всю простоту, наш примитивный язык оказался очень "мощным", что сразу сближает его с любым естественным языком, количество возможных предложений в котором также бесконечно.

Дополнительные материалы:

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

Регулярные грамматики просты, и их простота накладывает определения ограничения на выразительную возможность. Представьте себе, что вам нужно сказать фразу

тонкий лепесток упал на китайскую фарфоровую вазу

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

Sentence -> NP VP

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

Говоря более формально, контекстно-свободная грамматика имеет один нетерминал в левой части продукции и любую строку (комбинацию) терминалов и нетерминалов в правой части продукции.

Грамматика предложения "мама мыла раму", которую мы рассматривали выше, также контекстно-свободна.

G = (T, N, S, P)
T = { мама, мыла, раму }
N = { NP, VP, Noun, Verb, Sentence }
S = Sentence
P:
    Sentence -> NP VP
    NP -> NominativeNoun
    VP -> Verb AccusativeNoun
    Verb -> мыла
    NominativeNoun -> мама | рама
    AccusativeNoun -> маму | раму

Повторюсь, что "свобода от контекста" означает, что мы можем использовать любое слово, представляющее синтаксическую структуру на любом месте, ей дозволенном. В нашем примере мы можем подставить как "маму" так и "раму" на место AccusativeNoun вне зависимости от контекста, в котором этот AccusativeNoun используется (иными словами независимо от того, кто моет - "мама" или "рама").

Дополнительные материалы:

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

Для того, чтобы подставлять при порождении терминалы (слова) в зависимости от контекста, продукционное правило должно позволять порождать строки не из одного нетерминала, а из строки из терминалов и нетерминалов. Формально, в контекстно-зависимой грамматике позволяются следующие продукции:
αAβ -> αγβ
где α, β и γ - любые строки (комбинации) из терминалов и нетерминалов.

Говоря проще, α и β определяют "контекст", в котором происходит замена нетерминала A на строку γ.

Вернемся к примеру с мамой и рамой. Все предложение говорит о том, что кто-то что-то моет. Т.е. существительное в именительном падеже употребляется как субъект мытья, а существительное в винительном падеже - как объект мытья. Мы можем говорить о "субъекте мытья" и "объекте мытья" как о контекстах, в которых NominativeNoun должен при порождении стать только словом "мама", а AccusativeNoun - только словом "раму".

Контекстно-зависимая грамматика для предложения "мама мыла раму" будет следующей:

G = (T, N, S, P)
T = { мама, мыла, раму }
N = { NP, VP, Noun, Verb, Sentence }
S = Sentence
P:
    Sentence -> NP WashingSubject VP WashingObject
    NP WashingSubject -> NominativeNoun WashingSubject
    VP WashingObject -> Verb AccusativeNoun WashingObject
    Verb -> мыла
    NominativeNoun WashingSubject -> мама
    AccusativeNoun WashingObject -> раму

При этом грамматика порождает только одно (правильное) предложение:

Sentence => NP WashingSubject VP WashingObject
    => NominativeNoun WashingSubject VP WashingObject
    => мама VP WashingObject
    => мама Verb AccusativeNoun WashingObject
    => мама мыла AccusativeNoun WashingObject
    => мама мыла раму

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

NominativeNoun WashingSubject -> дочка
AccusativeNoun WashingObject -> куклу | посуду | пол

Дополнительные материалы:

Синтаксис и семантика

Контекстно-зависимая грамматика, как видно из этих примеров, довольно хорошо описывает не только синтаксические правила естественного языка, но и семантические. Хомский похоже был прав, когда говорил что внутри предложения заложено нечто большее чем просто форма, в нем есть "скрытый смысл".

Иными словами, компьютерный синтаксический и семантический анализ с использованием формальных грамматик и языков вместо естественных принципиально возможен. Более того, многие существующие программы вплотную такие возможности используют. Любой современный текстовый редактор умеет проверять как минимум синтаксис. Но на этом потенциал формальных языков не исчерпывается. Как только мы научимся создавать программы, понимающие не только синтаксическую, но и семантическую структуру текста на естественном языке, мы сможем не только эффективно искать информацию, но и извлекать из нее новые сведения и делать новые выводы. Мы сможем автоматически категоризировать и классифицировать информацию, автоматически определять ее важность и полезность. Мне кажется, что в нашем веке информационного пресыщения решение вышеуказанных задач - задач Text Data Mining станет существенным прорывом для всего человечества.

Трансформационные грамматики

Дополнительные материалы:

Компьютерный морфологический и синтаксический анализ

Все необходимые сведения и ссылки на дополнительные материалы по этой группе вопросов перечислены на странице с заданиями: Практические и индивидуальные задания по предмету ЛЗКС.