В этой статье мы рассмотрим синтаксический анализ в искусственном интеллекте.
Синтаксический анализ — это процесс изучения цепочки слов с целью определения ее фразовой структуры с использованием грамматических правил. Мы можем начать со знака S и искать сверху вниз дерево со словами в качестве его листьев, или мы можем начать со слов и искать дерево снизу вверх, которое заканчивается на S, как показано на рис. 23.4. С другой стороны, синтаксический анализ сверху вниз и снизу вверх может быть расточительным, поскольку он может привести к тому, что такое же количество усилий будет затрачено на те части пространства поиска, которые ведут в тупик.
Взгляните на следующие два предложения:
- Учащиеся из класса физики сдают тест?
- Сдали ли учащиеся класса физики тест?
Эти фразы имеют совершенно разные разборы, несмотря на то, что у них общие первые десять слов. Первый — это команда, а второй — запрос. Алгоритм синтаксического анализа слева направо должен был бы оценить, является ли первое слово частью команды или вопроса, и не будет знать, является ли оно правильным до одиннадцатого слова, взятого или взятого. Если алгоритм неверен, ему придется вернуться к исходному слову и заново проанализировать всю фразу, используя другое значение.
Мы можем использовать динамическое программирование, чтобы устранить этот источник неэффективности: каждый раз, когда мы проверяем подстроку, сохраняем результаты, чтобы нам не пришлось повторно анализировать их позже. Например, после того как мы определили, что «ученики в классе физики» являются NP, мы можем сохранить информацию в структуре данных, называемой диаграммой. Анализаторы диаграмм — это алгоритмы, которые достигают этого. Поскольку мы работаем с контекстно-свободной грамматикой, каждый термин, найденный в одной ветви пространства поиска, может использоваться в любой другой ветви. Есть много других типов парсеров диаграмм; мы обсуждаем метод CYK, названный в честь его создателей Джона Кока, Дэниела Янгера и Тадео Касами.
Стоит отметить, что алгоритм CYK требует грамматики, которая содержит все правила в одном из двух очень конкретных форматов: лексические правила в форме и синтаксические правила в форме . Этот грамматический тип, известный как нормальная форма Хомского, может показаться ограниченным, но это не так: любая контекстно-свободная грамматика может быть автоматически преобразована в нормальную форму Хомского.
Для общих контекстно-свободных грамматик ни один алгоритм не может превзойти алгоритм CYK, хотя существуют более быстрые алгоритмы для более ограниченных грамматик. Учитывая, что фраза может иметь экспоненциальное количество деревьев синтаксического анализа, выполнение метода за время O(n 3 ) является настоящим подвигом. Рассмотрим предложение
Fall leaves fall and spring leaves spring.
Непонятно, так как каждое слово (за исключением «и» ) может быть существительным или глаголом, а «падение» и «весна» также могут быть прилагательными. (Например, одна из интерпретаций фразы «Осень отходит от осени» — «Осень покидает осень».) [S [S [NP Осенние листья] Fall] и [S [NP Весенние листья] Spring] — два из четырех синтаксических анализов в 
.
У нас было бы 2 c возможностей выбора синтаксических разборов для подпредложений, если бы у нас было c двусторонне-неоднозначных соединенных подпредложений. Как алгоритм CYK обрабатывает эти 2 дерева синтаксического анализа за время O (c 3 ) ? Решение состоит в том, что ему не нужно просматривать все деревья синтаксического анализа; все, что ему нужно сделать, это вычислить вероятность наиболее вероятного из них. Все поддеревья представлены в таблице P, и мы могли бы перечислить их все (за экспоненциальное время) с небольшими усилиями, но прелесть метода CYK в том, что нам не нужно этого делать.
