Четвертая лекция знаменитого курса Стэнфордского университета CS224N «Обработка естественного языка с глубоким обучением» (весна 2024 года) посвящена фундаментальной лингвистической теме — синтаксическому анализу зависимостей (Dependency Parsing). Профессор Кристофер Маннинг подробно разбирает, как линейный поток человеческой речи трансформируется в иерархические структуры смыслов, и как эволюционировали компьютерные алгоритмы для решения этой задачи — от жестких символьных правил до современных нейросетевых моделей.
🏗️ Два взгляда на синтаксис: составляющие против зависимостей 2:13
В лингвистике исторически сложились два основных подхода к описанию синтаксической структуры человеческих языков. Первый подход основан на понятии структуры составляющих (phrase structure), которую специалисты по компьютерным наукам знают как контекстно-свободные грамматики (КСГ). В этой парадигме слова сначала объединяются в базовые классы — части речи (существительные, прилагательные, детерминативы, предлоги), которые затем формируют всё более крупные иерархические блоки: именные группы (Noun Phrase), предложные группы (Prepositional Phrase) и глагольные группы (Verb Phrase).
Второй подход, ставший главным предметом этой лекции, — это грамматика зависимостей (dependency grammar). Вместо построения абстрактных синтаксических блоков этот метод связывает слова напрямую бинарными асимметричными связями. В каждой паре выделяется главное слово (head) и зависимое (dependent), которое модифицирует вершину или выступает ее аргументом.
Кристофер Маннинг с иронией демонстрирует сложность синтаксического разбора на примере фразы «look in the large crate in the kitchen by the door», вспоминая, как сам когда-то допустил ошибку при построении дерева составляющих на доске, неверно сгруппировав предложные фразы. Грамматика зависимостей позволяет гораздо прозрачнее показать структуру: свойства «large», «in the kitchen» и «by the door» напрямую модифицируют именно ящик (crate), выступающий для них вершиной.
🌀 Проблема глобальной неоднозначности человеческого языка 14:49
Человеческое общение происходит в виде линейного потока звуков или символов, где отсутствуют явные маркеры синтаксических границ. Слушатель (или алгоритм NLP) должен самостоятельно восстанавливать иерархическую структуру для верной интерпретации смысла. Главная трудность заключается в том, что естественный язык, по утверждению Кристофера Маннинга, обладает глобальной синтаксической неоднозначностью. Если в языках программирования локальные неоднозначности всегда разрешаются строгими правилами компилятора (например, привязкой else к ближайшему if), то в человеческой речи контекст и здравый смысл остаются единственными арбитрами.
Профессор Маннинг приводит несколько классических курьезных примеров из заголовков реальных газет:
- «Scientists count whales from space». Фраза допускает два прочтения: либо ученые находятся в космосе и оттуда считают китов (что является верным смыслом статьи), либо они пересчитывают гипотетических «космических китов».
- «Students get first hand job experience». Из-за отсутствия дефисов и специфики сопоставления слов возникает двусмысленность: получают ли студенты практический опыт (first-hand experience) или же их опыт носит весьма пикантный характер, что традиционно вызывает смех в студенческой аудитории.
- «Mutilated body washes up on Rio beach to be used for Olympics beach volleyball». Инфинитивный оборот цели может относиться как к пляжу в Рио, так и к изувеченному телу, которое якобы собираются использовать для олимпийского матча.
Синтаксическая неоднозначность растет экспоненциально при добавлении последовательных предложных групп (так называемая проблема PP-attachment) и математически описывается числами Каталана. В типичном предложении из Wall Street Journal («The board approved its acquisition by Royal Trustco Limited of Toronto for $27 a share at its monthly meeting») подряд идут четыре предложные группы, что порождает 13 вариантов разбора; пять групп дают уже 27 вариантов. Человеческий мозг легко справляется с этим за завтраком, но для компьютерных моделей это колоссальный вызов.
Помимо фундаментального лингвистического интереса, точный синтаксический разбор критически важен для прикладных задач, например, в биоинформатике. Поиск фактов взаимодействия белков в научных текстах (например, как белок KaiC взаимодействует с SasA, KaiA и KaiB) напрямую опирается на выявление синтаксических связей между подлежащим, сказуемым и сложными однородными дополнениями.
📜 От Древней Индии до Хомского: краткая история зависимостей 29:19
Хотя в современных учебниках по компьютерным наукам чаще фигурируют контекстно-свободные грамматики, исторически именно грамматика зависимостей доминировала в мировом языкознании. Первым лингвистом, детально описавшим синтаксис человеческого языка (санскрита) через систему зависимостей, был древнеиндийский ученый Панини, живший между IV и VIII веками до нашей эры. Удивительно, но огромный и сложный свод правил Панини был составлен и передавался из поколения в поколение исключительно в устной форме, что, по признанию Маннинга, «просто взрывает мозг». В первом тысячелетии нашей эры аналогичный подход активно развивался арабскими филологами.
Напротив, структура составляющих — концепция крайне молодая, зародившаяся в 1940-х годах и канонизированная американским лингвистом Ноамом Хомским в 1950-х. Профессор Маннинг развенчивает популярный среди студентов миф: знаменитая иерархия Хомского была создана вовсе не для того, чтобы мучить первокурсников на экзаменах по теории автоматов. Хомский разработал ее исключительно как лингвистический аргумент, чтобы доказать неполноту конечноавтоматных (регулярных) механизмов при моделировании сложности человеческой речи.
Современный компьютерный синтаксис зависимостей во многом опирается на теоретические труды французского лингвиста Люсьена Теньера. В его традиции стрелки направлены от главного слова к зависимому, формируя связный ациклический граф — дерево. Для удобства парсинга к предложению обычно добавляется искусственный корневой узел (ROOT), который указывает на главный глагол предложения.
📊 Революция Treebanks и метрики оценки 39:07
В ранние эпохи компьютерной лингвистики (до конца 1980-х) исследователи пытались прописывать синтаксические правила вручную, что привело к тупику. Живой язык обладает бесконечным «длинным хвостом» редких конструкций, а люди используют его слишком творчески — профессор вспоминает специфическую речь магистра Йоды из «Звездных войн» и моду добавлять отрицание «not» в самый конец предложения.
Прорыв произошел благодаря переходу к машинному обучению и созданию аннотированных корпусов текстов — Treebanks. Одним из флагманских проектов стал Universal Dependencies — международная база данных, охватывающая более 100 языков с унифицированной разметкой зависимостей, в развитии которой Кристофер Маннинг принимает непосредственное участие.
Появление таких корпусов решило две важнейшие задачи:
- Сбор частотной статистики, позволяющей алгоритмам предсказывать наиболее вероятные точки прикрепления слов.
- Внедрение строгой методологии оценки. До 1990-х годов авторы парсеров доказывали их качество субъективно: запускали программу перед коллегами и говорили: «Смотрите, это работает!». Систематической оценки не существовало. Сегодня качество синтаксического анализа оценивается по двум строгим метрикам на основе тестовых выборок:
- UAS (Unlabeled Attachment Score) — процент правильно определенных синтаксических стрелок без учета их типа.
- LAS (Labeled Attachment Score) — процент связей, у которых верно определены и направление, и тип грамматического отношения (например, субъект, дополнение, детерминатив).
⚙️ Алгоритм переходов: парсинг на основе стека и буфера 54:02
При принятии решений синтаксический анализатор опирается на четыре ключевых фактора: семантическая сочетаемость пары слов, расстояние зависимости (большинство связей в языке короткие), наличие промежуточных глаголов или знаков препинания, а также валентность вершин (информация о том, сколько аргументов слева и справа обычно принимает конкретный глагол).
Большинство предложений в языках мира стремятся к проективности — свойству, при котором линии зависимостей не пересекаются друг с другом. Непроективные структуры возникают редко, например, при вынесении вопросительных слов в начало предложения или при дистанционном разрыве словосочетаний (например, «I'll give a talk tomorrow on neural networks», где тема доклада отделена от самого доклада наречием времени). В рамках учебной лабораторной работы студентам предлагается реализовать именно проективный парсер.
Наиболее популярным практическим методом стал transition-based parsing (алгоритм на основе переходов), концептуально схожий с shift-reduce парсерами из теории компиляторов. Он использует две основные структуры данных:
- Стек (Stack) — хранит частично обработанные слова (его вершина условно находится справа).
- Буфер (Buffer) — содержит еще не обработанные слова входного предложения (его вершина находится слева).
На каждом шаге алгоритма классификатор выбирает одно из трех возможных действий (переходов):
- Shift: взять первое слово из буфера и перенести его на вершину стека.
- Left-Arc: создать стрелку зависимости от второго слова на стеке (предпоследнего) к первому (верхнему), после чего предпоследнее слово удаляется со стека.
- Right-Arc: создать стрелку зависимости от первого слова на стеке к второму, после чего верхнее слово удаляется со стека.
Процесс инициализируется фиктивным узлом ROOT на стеке и полным предложением в буфере, а завершается, когда буфер пуст, а на стеке остается только ROOT. Этот подход, разработанный шведским ученым Йоакимом Нивре в начале 2000-х годов, обладает колоссальным преимуществом — он работает за линейное время $O(n)$ от длины предложения. В отличие от классических алгоритмов динамического программирования для контекстно-свободных грамматик, требующих кубического времени $O(n^3)$, этот метод работает мгновенно.
🧠 Эволюция моделей: от формул Нивре до Parsey McParseface 1:02:39
В оригинальной версии 2005 года Йоаким Нивре использовал традиционное машинное обучение (логистическую регрессию или SVM) со сложными символьными индикаторными фичами. Инженеры вручную конструировали миллионы комбинаций из конкретных слов и их частей речи, находящихся в данный момент на вершине стека и буфера. Это приводило к двум фундаментальным проблемам: колоссальной разреженности данных (многие комбинации встречались считанные разы на миллион предложений) и экстремальной вычислительной дороговизне. Большая часть времени инференса уходила не на работу классификатора, а на строковую генерацию этих фич.
Революцию совершила Данци Чэнь (Danqi Chen), аспирантка Кристофера Маннинга. Она предложила использовать плотные векторные представления (эмбеддинги) не только для слов, но и для частей речи (POS-tags), а также для типов синтаксических меток.
Нейросетевая архитектура Чэнь извлекала компактный набор базовых токенов со стека и буфера, конкатенировала их плотные векторы в единый вектор и пропускала через скрытый слой с нелинейной функцией активации ReLU. На выходе слой Softmax выдавал распределение вероятностей над доступными переходами (Shift, Left-Arc, Right-Arc). За счет нелинейности классификатора глубокая сеть Чэнь превзошла по точности тяжеловесные альтернативные парсеры, сохранив линейную скорость.
Этот успех спровоцировал ажиотаж в индустрии. В 2016 году компания Google провела масштабную пиар-кампанию, представив доработанную глубокую версию этого парсера под шутливым названием Parsey McParseface. За счет увеличения емкости нейросети, тонкой настройки гиперпараметров и внедрения пучкового поиска (beam search) инженерам Google удалось поднять метрику UAS до внушительных 94.6%.
🌐 Графовые методы синтаксического анализа 1:15:15
Альтернативой пошаговым методам переходов являются графовые парсеры (graph-based dependency parsers). Вместо последовательной сборки структуры они оценивают вероятность связи каждого слова со всеми остальными словами в предложении, формируя матрицу оценок размером $n \times n$, где $n$ — количество слов. Задача сводится к поиску максимального направленного остовного дерева (Maximum Spanning Tree) в графе, исключающего циклы и разрывы.
Исторически символьные графовые методы были точнее переходных, но работали примерно в 50 раз медленнее. Однако в 2017 году были представлены полностью нейросетевые графовые парсеры, которые превзошли Parsey McParseface более чем на один процент по точности. Именно этот высокоточный алгоритм сегодня интегрирован в Stanza — популярную open-source библиотеку синтаксического анализа, разрабатываемую исследовательской группой Стэнфорда.
Профессор Маннинг резюмирует лекцию утверждением, что современные большие языковые модели на архитектуре Transformer внутренне оперируют схожими структурными и синтаксическими единицами, даже если формально принимают на вход обычную линейную последовательность текстовых токенов.
