«Интеллектуальная история искусственного интеллекта: ИИ и я»

Области искусственного интеллекта более полувека, но технологический прорыв, связанный с нейросетями, произошел лишь относительно недавно. По мнению профессора компьютерных наук и исследователя ИИ , который пришел в эту область в 1967 году, их цель с самого начала была верной, а вот пути ее достижения — ошибочными. В книге «Интеллектуальная история искусственного интеллекта: ИИ и я» («Издательство Института Гайдара»), переведенной на русский язык Артемом Смирновым, он рассказывает о ключевых идеях и фундаментальных заблуждениях, сопровождавших развитие этой дисциплины вплоть до наших дней. Предлагаем вам ознакомиться с фрагментом, посвященным обучению компьютеров синтаксическому анализу.

Графические модели и грамматика

В любом языке есть грамматика — правила построения предложений. Я помню, как получал четкие инструкции по структуре предложения, когда учился в начальной школе (по-английски, она, кстати, называется grammar school). Сначала мы писали простое повествовательное предложение, подлежащее-сказуемое-дополнение, например, «Alice moved the tray» («Алиса передвинула поднос»), и нам говорили его подчеркнуть. Затем мы проводили вертикальную линию между подлежащим и сказуемым, а за ней — еще одну, покороче, между сказуемым и прямым дополнением. Смотрите рисунок 7.2. Если это было призвано улучшить мою грамматику, то это был полный провал, но, полагаю, я усвоил терминологию. Когда мой сын учился примерно в пятом классе, я спросил его, были ли у него подобные уроки. Он ответил, что были, и они также изучали предложные группы (как в «Alice moved the tray to the floor»), которые они называли «треугольниками». Хотя я и считал грамматику бесполезной, я провел большую часть своей академической карьеры пытаясь научить ей компьютеры. Истинное предназначение грамматики — не улучшать ваше письмо, а, скорее, помогать конструировать значение предложений из значений их частей.

Почти все предложения, которые вы встречаете, являются для вас новыми. Возьмем последнее предложение предыдущего абзаца. Я почти уверен, что вы без труда его поняли, но даже если вы каким-то образом читали предложение с похожим содержанием, весьма вероятно, что точная последовательность слов является новой. Если бы это было не так, вы могли бы заподозрить плагиат. Отсюда вопрос: как вы понимаете новые последовательности слов? Ответ должен быть таким: части предложений, слова, не новы, и этого достаточно, чтобы собрать воедино значение всего предложения. Идея в том, что именно грамматика делает это возможным.

Рассмотрим предложение «Bob sold the dog biscuits». Лингвистическим эквивалентом подчеркивания предложений и рисования треугольников является грамматическое дерево, как показано на рисунке 7.3. Все предложение (S) разбивается на именную группу (NP) и глагольную группу (VP). Заметьте, что «sold» — это глагол, который допускает косвенные дополнения, в данном случае «the dog», поэтому глагольная группа разбивается на глагол и две именные группы. Именно грамматика английского языка говорит нам об этом, и она же говорит нам, что первая из двух групп играет семантическую роль «получателя», а не прямого дополнения. (Прямое дополнение — это вторая NP.) Таким образом, эта версия нашего предложения означает, что собака купила печенье.

Читатель, возможно, заметил, что я намеренно сконструировал это предложение так, чтобы оно было неоднозначным — оно имеет более одного значения. Более того, разные значения имеют разные деревья. Глагольная группа для второй версии имеет форму, показанную на рисунке 7.4.

Грамматика, таким образом, — это набор правил того, как предложения строятся из слов. Для нашего примера некоторые из необходимых нам правил будут следующими:

1. S → NP VP
2. VP → sold NP NP
3. VP → sold NP
4. NP → Bob

Эта форма грамматики называется контекстно-свободной грамматикой. Правила следует интерпретировать так, что, например, глагольная группа (VP) может быть построена как глагол «sold», за которым следуют две именные группы (NP). Символы, написанные заглавными буквами, называются нетерминалами, потому что они должны быть заменены с использованием других правил для построения полного предложения. Эта грамматика называется «контекстно-свободной», потому что все правила содержат в своей левой части ровно один нетерминал, поэтому правило гласит, что нетерминал может быть раскрыт с помощью любого из его правил без учета контекста.

Теперь вспомните, что я говорил о том, как грамматическое дерево показывает нам, как собрать воедино значение предложения из слов. Посмотрите на слово «biscuits» во второй версии и на то, как я поместил его в ту же именную группу, что и «the dog». Это говорит нам, что мы объединяем «the», «dog» и «biscuits» перед тем, как присоединить их к «sold», в отличие от версии на рисунке 7.3, где мы рассматриваем «the dog» и «biscuits» как отдельные компоненты, а затем присоединяем их оба к «sold». Или, выражаясь иначе, первая версия говорит о некой конкретной собаке, а вторая — нет.

Идея в том, что если машина может установить синтаксическую структуру предложения — если она может выполнить его синтаксический анализ, — это, как минимум, укажет нам порядок, в котором следует комбинировать значения слов. Забудем о попытках улучшить грамматику компьютера (предписывающую грамматику) — нам просто нужна грамматика, которая отражает реальное использование языка (описательная грамматика).

Таким образом, способность выполнять синтаксический анализ произвольного текста была давней целью в области обработки естественного языка в ИИ. И, как это часто бывало, первые идеи пришли со стороны, на этот раз из разработки компиляторов, где людям нужно было анализировать не английский язык, а языки вроде FORTRAN. Оказалось, что для большинства языков программирования контекстно-свободных грамматик достаточно, и на раннем этапе эффективный алгоритм для синтаксического анализа контекстно-свободных грамматик был независимо открыт тремя исследователями в этой области — алгоритм Кока — Янгера — Касами (CYK algorithm) — по именам трех его первооткрывателей: Джона Кока, Дэниела Янгера и Тадао Касами. Мы начинаем с пар слов и ищем все возможные структуры, допустимые нашей грамматикой для данной подстроки. На каждом шаге рассматриваются только попарные сочетания уже найденных структур.

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

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

На раннем этапе исследователи в области обработки естественного языка осознали, что, хотя не все правила английского языка соответствовали формату контекстно-свободных грамматик, те, что не соответствовали, были сравнительно редкими. Поскольку эффективный синтаксический анализ с использованием контекстно-свободных грамматик является простой задачей, для английского языка были приняты варианты синтаксического анализа на основе алгоритма Кока — Янгера — Касами.

Таким образом, на данном этапе проблема заключалась в том, чтобы просто создать контекстно-свободную грамматику, которая строила бы интуитивно правдоподобные структуры для всего разнообразия английского языка, встречающегося в книгах и газетах. Однако эта задача оказалась очень сложной. Взгляните еще раз, скажем, на первое предложение этого абзаца. Какова его структура? Его длина составляет тридцать пять слов и знаков препинания. Когда вы доходите до такой длины, определение структуры становится трудным, а количество правил контекстно-свободной грамматики, необходимое для охвата всех альтернатив, — огромно. Много времени было потрачено на попытки найти такие наборы правил, но все потерпели неудачу. Лингвист Эдвард Сепир был известен многими важными наблюдениями о языке; одно из самых знаменитых: «Во всех грамматиках есть „исключения“» («All grammars leak»). Под этим он имел в виду, что невозможно составить исчерпывающую грамматику для естественного языка.

Возможно, еще хуже было то, что по мере добавления новых правил в грамматику, предложения, которые ранее были однозначными, внезапно обретали дополнительные структуры, имевшие мало смысла или не имевшие его вовсе. Например, рассмотрим фразу «five dollars a share», что означает, что каждая акция стоит пять долларов. Стандартный анализ предполагает создание нового правила грамматики, NP→NP NP, где первая NP — это «five dollars», а вторая — «a share». Добавление этого правила необходимо для предложения «The stockbroker paid five dollars a share», что вполне логично, но внезапно наше предложение о «собачьем печенье» получило не две, а три структуры. Эта новая структура имеет именную группу, «the dog biscuits», которая сама состоит из двух именных групп, «the dog» и «biscuits». А у более длинных предложений их было еще больше: десятки тысяч были обычным делом. Область находилась в хаосе. Предложения либо совсем не соответствовали грамматике, либо существовало так много возможных структур, что понять, как же их правильно собрать, было почти нереально. А ведь именно в этом и состоял весь смысл предприятия. 

Решение пришло откуда не ждали. В 1994 году группа из Пенсильванского университета под руководством Митчелла Маркуса Penn treebank — коллекцию из миллиона слов текста из Wall Street Journal вместе со структурой предложений в форме синтаксических деревьев. Из Penn treebank можно извлечь все контекстно-свободные правила, позволяющие правильно разобрать все содержащиеся в нем предложения. Это в значительной степени решило проблему «исключений» в грамматиках.

Более того, можно подсчитать, сколько раз использовалось каждое правило, а затем разделить на общее число раз, когда использовалось любое правило для данной грамматической категории, чтобы получить вероятность того, что данная категория будет раскрыта с помощью данного правила. Например, если мы разделим частоту использования NP→NP NP на количество всех NP в корпусе, мы получим вероятность того, что любая конкретная именная группа реализуется через конструкцию типа «five dollars a share». Это дает нам вероятностную контекстно-свободную грамматику.

Затем мы решаем проблему синтаксической неоднозначности, требуя не любую структуру для предложения, а наиболее вероятную, которую можно вычислить путем перемножения вероятностей всех контекстно-свободных правил, использованных в дереве. Более того, у нас есть эффективный способ найти этот вариант разбора — внутренне-внешний алгоритм. Это дает нам грамматику и алгоритм, которые (а) не имеют исключений, по крайней мере в том смысле, что они возвращают какую-то структуру для любого поданного предложения, и (б) возвращают единственную наиболее вероятную структуру в соответствии с контекстно-свободной грамматикой.

К сожалению, «наиболее вероятный» не значит «правильный». Это был шаг в верном направлении, но тем не менее почти все варианты разбора оказывались неправильными. Даже если мы рассмотрим отдельное решение — правило, использованное для раскрытия какого-то конкретного нетерминала, — вероятность того, что это правильное решение, составляет всего около 75 процентов. А когда у вас в дереве тридцать таких решений, вероятность, что все они будут правильными, ничтожно мала. Грубо говоря, предложения до восьми слов разбираются в основном верно, а все, что длиннее (то есть 90 процентов предложений), — с ошибками.

Последним необходимым элементом стали лексикализованные контекстно-свободные грамматики, предложенные Майклом Коллинзом в 1996 году, также из Пенсильванского университета. Идея заключается в том, чтобы ассоциировать грамматические правила с конкретными словами, которые можно рассматривать как активирующие соответствующие правила. Например, косвенные дополнения могут иметь только определенные глаголы — sold, gave, take и так далее. Нельзя сказать, например, «Alice received Bill a gift». Присваивая более высокую вероятность правилам, когда в предложении есть подходящее слово (лексическая единица — это просто слово), и более низкую, когда его нет, Коллинз повысил точность на уровне отдельного решения до 85 процентов. А в последующие пятнадцать лет появились техники, которые подняли эту точность до 97 процентов, что превосходит человеческие показатели в этой задаче (всего 95 процентов). Найти единственно верную структуру для предложения из тридцати слов — весьма непростая задача даже для людей. Так что, по сути, проблема синтаксического анализа была решена, по крайней мере для английского языка. (Ваш автор, вместе со своим коллегой Марком Джонсоном, внес свой вклад в это улучшение.)

Подробнее читайте:
Черняк, Ю. Интеллектуальная история искусственного интеллекта: ИИ и я [Текст] /Юджин Черняк ; перевод с английского под научной редакцией Артема Смирнова. — Москва: Издательство Института Гайдара, 2025. — 280 с.