11 Часть I. Компоненты 14 Глава Компьютерная
Неоднозначность и проблема комбинаторного взрыва
жүктеу/скачать 4,29 Mb.
|
nikolaev is mitrenina ov lando tm red prikladnaia i kompiute
Латын тілі 4,5 - дәріс 2, 169-182 фил, Вопросы на русском языке, 6 үж
Неоднозначность и проблема комбинаторного взрываГлавная проблема синтаксического анализа связана с неоднозначно- стью языковых единиц. Даже, казалось бы, однозначные слова, например, слово телевизор, имеют так называемые «контекстуальные» значения, т. е. значения, проявляющиеся в особых условиях: например, телевизо- ром, хоть и редко, могут назвать и монитор вычислительной машины, и даже, в переносном смысле, телевидение — ср. Телевизору нельзя верить; Как их вообще пустили в телевизор. Помимо очевидной многозначности слов (лексической неоднознач- ности), есть и менее очевидная многозначность грамматических форм (морфологическая неоднозначность): ср., например, например, числи- тельное три и форму повелительного наклонения единственного числа глагола тереть, или форму именительного падежа слова стекло и форму прошедшего времени, единственного числа, среднего рода глагола сте- кать. Морфологическая неоднозначность может показаться редким явле- нием, но только потому, что она редко бывает очевидной. Больше всего проблем вызывает, однако, не морфологическая, а син- таксическая неоднозначность. Из-за морфологической неоднозначности одна и та же фраза может иметь несколько разных пониманий, которые соответствуют разным структурам (Он увидел их семью своими глазами, Эти типы стали есть в цехе). Более того, одна и та же фраза может быть понята по-разному даже при однозначности всех её словоформ (ср. Вася встретил Петю в коридоре и Вася встретил Петю в костюме). В дейст- вительности, обе фразы имеют, по крайней мере, три возможные синтак- сических структуры. Им соответствует три разные ситуации. Для первой фразы они таковы: Вася встретил Петю, и это произошло в коридоре Вася встретил Петю, одетого в коридор Вася, одетый в коридор, встретил Петю По наблюдению И. А. Мельчука, одно предложение в первой статье Конституции США допускает 16 различных синтаксических структур. Чтобы найти верный вариант разбора целого предложения, можно попытаться перебрать все комбинации вариантов разбора его частей. Про- блема в том, что при компьютерном анализе это приводит к так называе- мому комбинаторному взрыву. Действительно, если три словоформы в предложении имеют хотя бы два варианта разбора, то в сумме получается 23 = 8 возможных комбина- ций, которые необходимо рассмотреть. 7 неоднозначных словоформ в предложении приводят уже к 27 = 128 комбинациям. Время работы маши- ны напрямую зависит от количества перебираемых комбинаций, которое в данном случае растёт экспоненциально. Несложно убедиться в том, что в реальных текстах число неодно- значных словоформ часто оказывается выше, чем семь, а число вариантов разбора часто превышает два даже в русскоязычном тексте. Если же речь идёт об арабском тексте, где чаще всего пропускаются обозначения глас- ных фонем, то семь — это нормальное, даже довольно низкое количество версий разбора для каждой словоформы (77 = 823543). Таким образом, даже неоднозначности словоформ было бы достаточ- но для серьёзных проблем с производительностью парсеров. Между тем, неоднозначность словоформ — это лишь часть проблемы. Выше рассмат- ривались предложения Вася встретил Петю в коридоре и Вася встретил Петю в костюме, различающиеся лишь одной словоформой, причём од- нозначной. Эти два предложения имеют различные синтаксические струк- туры, но установить этот факт машина может только на основании семан- тических, а не синтаксических знаний. Вместе с тем, в данном случае все словоформы в предложениях однозначны. Синтаксическая неоднознач- ность возникает из-за того, что одна и та же цепочка слов в одних и тех же грамматических формах может быть порождена разными, неравнознач- ными способами (деривациями). В терминах теории синтаксических групп, группа в костюме может относиться как к словоформе Вася, так и к словоформе Петя, или даже ко всему предложению Вася встретил Петю, если допустить, что костюм был местом встречи. Кроме того, в языке встречаются пропуски словоформ — эллипсис. Чтобы машина могла обнаруживать эллипсис там, где он действительно есть, ей приходится сначала предполагать подобные пропуски везде. Это выводит масштабы комбинаторного взрыва на уровень миллионов комби- наций. В определённом смысле масштаб и сложность, да и сама суть про- блемы, о которой идёт речь, напоминают известную задачу коммивояжё- ра. Эта задача обычно формулируется так. Имеется набор городов, соеди- нённых дорогами, каждая из которых имеет длину (стоимость) и может быть односторонней. Нужно найти самый выгодный маршрут, который проходил бы через все города хотя бы по одному разу и возвращался бы в исходный город, и, самое главное, доказать, что более выгодного маршру- та не существует. Человек (конечно, ничего не доказывая) может найти такой маршрут, как правило, мгновенно, но как именно он это делает, на сегодняшний день точно неизвестно. Машина же куда хуже справляется с этой задачей. Найти оптимальное правильное синтаксическое дерево, которое бы связывало все словоформы в предложении, — ничуть не проще, чем ре- шить задачу коммивояжёра. Вместе с абстрактными единицами граммати- ки словоформы конкретного предложения образуют сложную систему связей, в которой синтаксическое дерево — это маршрут. Решению задачи коммивояжёра посвящено множество исследований, равно как и проблеме комбинаторного взрыва при компьютерном синтаксическом анализе. В обоих случаях на практике вместо универсальных часто используются эвристические алгоритмы — частные решения, дающие верный или приближенный к верному результат в большей части случаев, но не при- годные для полноценного решения задачи. Например, в области компью- терного синтаксиса к числу таких решений относятся так называемые од- ноцелевые парсеры — синтаксические анализаторы, которые для каждо- го предложения строят лишь одну версию разбора. Одноцелевые парсеры часто используют вероятностные грамматики (см. ниже) в качестве эври- стики для выбора основной версии, но также используются и эвристиче- ские правила (например, исключать версию именительного падежа в су- ществительных после предлогов, привязывать предложные группы только к ближайшему соседу и т. д.). Как правило, для разных предложений, со- стоящих из одних и тех же грамматических форм, они показывают одну и ту же синтаксическую структуру. Поэтому, если, например, для предложе- ния Вася встретил Петю в костюме такой анализатор выстроит одну из верных версий разбора (т. е. в костюме будет отнесено к Вася или к Петю, а не к встретил), то и для предложения Вася встретил Петю в коридоре синтаксическая структура будет выстроена точно такая же, и при семанти- ческом анализе кто-то из участников встречи непременно окажется «оде- тым» в коридор (таково одно из возможных значений предлога в при пря- мом подчинении именной группе, обозначающей живое существо). Такой подход приводит и к более серьёзным проблемам. Синтаксиче- ская неоднозначность может оказаться неразрешимой на уровне синтакси- са — например, в известном предложении Он увидел их семью своими гла- зами (те, кому неизвестен этот пример, редко сразу догадываются, что машина может предположить наличие семи глаз у действующего лица, но даже те, кто догадываются, редко осознают, что машина может оказаться права, например, если речь идёт о пауке, лишённом одного глаза). Верным результатом синтаксического анализа таких предложений (а значит, в об- щем случае и любых других), всё же, является не одно наиболее вероятное дерево, а совокупность всех возможных деревьев. В данном случае их, по меньшей мере, четыре (Толкования этих четырёх структур выглядят при- близительно так: ‘Он сам увидел их семью’, ‘Он увидел их при помощи семи своих глаз’, ‘Он увидел, что их семья может стать его глазами’ и ‘Он увидел, что они могут стать семью его глазами’). Поэтому в современных системах, как правило, всё же используются многоцелевые парсеры — анализаторы, которые для каждого предложения порождают набор версий синтаксического дерева. Между тем, именно при разработке многоцелевых парсеров проблема комбинаторного взрыва оказывается особо важной. жүктеу/скачать 4,29 Mb. Достарыңызбен бөлісу:
|