11 Часть I. Компоненты 14 Глава Компьютерная


Неоднозначность и проблема комбинаторного взрыва



бет32/197
Дата19.03.2022
өлшемі4,29 Mb.
#136225
түріЛитература
1   ...   28   29   30   31   32   33   34   35   ...   197
Байланысты:
nikolaev is mitrenina ov lando tm red prikladnaia i kompiute

Неоднозначность и проблема комбинаторного взрыва


Главная проблема синтаксического анализа связана с неоднозначно- стью языковых единиц. Даже, казалось бы, однозначные слова, например, слово телевизор, имеют так называемые «контекстуальные» значения, т. е. значения, проявляющиеся в особых условиях: например, телевизо- ром, хоть и редко, могут назвать и монитор вычислительной машины, и даже, в переносном смысле, телевидение — ср. Телевизору нельзя верить; Как их вообще пустили в телевизор.
Помимо очевидной многозначности слов (лексической неоднознач- ности), есть и менее очевидная многозначность грамматических форм (морфологическая неоднозначность): ср., например, например, числи- тельное три и форму повелительного наклонения единственного числа глагола тереть, или форму именительного падежа слова стекло и форму прошедшего времени, единственного числа, среднего рода глагола сте- кать. Морфологическая неоднозначность может показаться редким явле- нием, но только потому, что она редко бывает очевидной.
Больше всего проблем вызывает, однако, не морфологическая, а син- таксическая неоднозначность. Из-за морфологической неоднозначности одна и та же фраза может иметь несколько разных пониманий, которые соответствуют разным структурам (Он увидел их семью своими глазами, Эти типы стали есть в цехе). Более того, одна и та же фраза может быть понята по-разному даже при однозначности всех её словоформ (ср. Вася встретил Петю в коридоре и Вася встретил Петю в костюме). В дейст- вительности, обе фразы имеют, по крайней мере, три возможные синтак- сических структуры. Им соответствует три разные ситуации. Для первой фразы они таковы:
Вася встретил Петю, и это произошло в коридоре Вася встретил Петю, одетого в коридор
Вася, одетый в коридор, встретил Петю
По наблюдению И. А. Мельчука, одно предложение в первой статье Конституции США допускает 16 различных синтаксических структур.
Чтобы найти верный вариант разбора целого предложения, можно попытаться перебрать все комбинации вариантов разбора его частей. Про- блема в том, что при компьютерном анализе это приводит к так называе- мому комбинаторному взрыву.
Действительно, если три словоформы в предложении имеют хотя бы два варианта разбора, то в сумме получается 23 = 8 возможных комбина- ций, которые необходимо рассмотреть. 7 неоднозначных словоформ в

предложении приводят уже к 27 = 128 комбинациям. Время работы маши- ны напрямую зависит от количества перебираемых комбинаций, которое в данном случае растёт экспоненциально.


Несложно убедиться в том, что в реальных текстах число неодно- значных словоформ часто оказывается выше, чем семь, а число вариантов разбора часто превышает два даже в русскоязычном тексте. Если же речь идёт об арабском тексте, где чаще всего пропускаются обозначения глас- ных фонем, то семь — это нормальное, даже довольно низкое количество версий разбора для каждой словоформы (77 = 823543).
Таким образом, даже неоднозначности словоформ было бы достаточ- но для серьёзных проблем с производительностью парсеров. Между тем, неоднозначность словоформ — это лишь часть проблемы. Выше рассмат- ривались предложения Вася встретил Петю в коридоре и Вася встретил Петю в костюме, различающиеся лишь одной словоформой, причём од- нозначной. Эти два предложения имеют различные синтаксические струк- туры, но установить этот факт машина может только на основании семан- тических, а не синтаксических знаний. Вместе с тем, в данном случае все словоформы в предложениях однозначны. Синтаксическая неоднознач- ность возникает из-за того, что одна и та же цепочка слов в одних и тех же грамматических формах может быть порождена разными, неравнознач- ными способами (деривациями). В терминах теории синтаксических групп, группа в костюме может относиться как к словоформе Вася, так и к словоформе Петя, или даже ко всему предложению Вася встретил Петю, если допустить, что костюм был местом встречи.
Кроме того, в языке встречаются пропуски словоформ — эллипсис. Чтобы машина могла обнаруживать эллипсис там, где он действительно есть, ей приходится сначала предполагать подобные пропуски везде. Это выводит масштабы комбинаторного взрыва на уровень миллионов комби- наций.
В определённом смысле масштаб и сложность, да и сама суть про- блемы, о которой идёт речь, напоминают известную задачу коммивояжё- ра. Эта задача обычно формулируется так. Имеется набор городов, соеди- нённых дорогами, каждая из которых имеет длину (стоимость) и может быть односторонней. Нужно найти самый выгодный маршрут, который проходил бы через все города хотя бы по одному разу и возвращался бы в исходный город, и, самое главное, доказать, что более выгодного маршру- та не существует. Человек (конечно, ничего не доказывая) может найти такой маршрут, как правило, мгновенно, но как именно он это делает, на сегодняшний день точно неизвестно. Машина же куда хуже справляется с этой задачей.
Найти оптимальное правильное синтаксическое дерево, которое бы связывало все словоформы в предложении, — ничуть не проще, чем ре-

шить задачу коммивояжёра. Вместе с абстрактными единицами граммати- ки словоформы конкретного предложения образуют сложную систему связей, в которой синтаксическое дерево — это маршрут. Решению задачи коммивояжёра посвящено множество исследований, равно как и проблеме комбинаторного взрыва при компьютерном синтаксическом анализе. В обоих случаях на практике вместо универсальных часто используются эвристические алгоритмы — частные решения, дающие верный или приближенный к верному результат в большей части случаев, но не при- годные для полноценного решения задачи. Например, в области компью- терного синтаксиса к числу таких решений относятся так называемые од- ноцелевые парсеры синтаксические анализаторы, которые для каждо- го предложения строят лишь одну версию разбора. Одноцелевые парсеры часто используют вероятностные грамматики (см. ниже) в качестве эври- стики для выбора основной версии, но также используются и эвристиче- ские правила (например, исключать версию именительного падежа в су- ществительных после предлогов, привязывать предложные группы только к ближайшему соседу и т. д.). Как правило, для разных предложений, со- стоящих из одних и тех же грамматических форм, они показывают одну и ту же синтаксическую структуру. Поэтому, если, например, для предложе- ния Вася встретил Петю в костюме такой анализатор выстроит одну из верных версий разбора (т. е. в костюме будет отнесено к Вася или к Петю, а не к встретил), то и для предложения Вася встретил Петю в коридоре синтаксическая структура будет выстроена точно такая же, и при семанти- ческом анализе кто-то из участников встречи непременно окажется «оде- тым» в коридор (таково одно из возможных значений предлога в при пря- мом подчинении именной группе, обозначающей живое существо).


Такой подход приводит и к более серьёзным проблемам. Синтаксиче- ская неоднозначность может оказаться неразрешимой на уровне синтакси- са — например, в известном предложении Он увидел их семью своими гла- зами (те, кому неизвестен этот пример, редко сразу догадываются, что машина может предположить наличие семи глаз у действующего лица, но даже те, кто догадываются, редко осознают, что машина может оказаться права, например, если речь идёт о пауке, лишённом одного глаза). Верным результатом синтаксического анализа таких предложений (а значит, в об- щем случае и любых других), всё же, является не одно наиболее вероятное дерево, а совокупность всех возможных деревьев. В данном случае их, по меньшей мере, четыре (Толкования этих четырёх структур выглядят при- близительно так: ‘Он сам увидел их семью’, ‘Он увидел их при помощи семи своих глаз’, ‘Он увидел, что их семья может стать его глазами’ и ‘Он увидел, что они могут стать семью его глазами’). Поэтому в современных системах, как правило, всё же используются многоцелевые парсеры

анализаторы, которые для каждого предложения порождают набор версий синтаксического дерева.


Между тем, именно при разработке многоцелевых парсеров проблема комбинаторного взрыва оказывается особо важной.




  1. Достарыңызбен бөлісу:
1   ...   28   29   30   31   32   33   34   35   ...   197




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет