Лекция 10 Грамматическая классификация образов




ЛЕКЦИЯ 10

Грамматическая систематизация образов


Исследование применительно к вычислительной технике лингвистики вызвано тем, что меж программкой и конструкцией машины, способной распознавать верно построенные выражения (предложения в виде цепочки знаков) на языке, определяемом порождающей грамматикой, существует Лекция 10 Грамматическая классификация образов некое соответствие. Введём последующие обозначения: грамматика, порождаемый ею язык; огромное количество терминальных знаков, использующихся в ; x- цепочка терминальных знаков и огромное количество всех цепочек, которые можно выстроить из . Задачка лингвистического определения языка (либо Лекция 10 Грамматическая классификация образов задачка лингвистической систематизации образов) заключается в том, чтоб за конечное число шагов узнать, принадлежит ли случайная цепочка огромному количеству либо . Если можно найти метод, осуществляющий это, то язык именуют рекурсивным, а грамматика - разрешимой Лекция 10 Грамматическая классификация образов.

Есть нерекурсивные языки. Для их можно выстроить алго­ритм, который будет распознавать всякую цепочку , но нельзя гарантировать, что он будет останавливаться для всех цепочек Такие языки именуются рекурсивно перечислимыми. Хоть какой Лекция 10 Грамматическая классификация образов язык, определяемый порождающей грамматикой, рекурсивно перечислим.

Систематизация цепочек при распознавании образов обеспечивает общий подход в отличие от рассматриваемой до сего времени векторной систематизации. Векторы представляют собой цепочки конечной длины, так как фактически существует Лекция 10 Грамматическая классификация образов предел разрешимости 2-ух точек в пространстве. Потому их можно обрисовать при помощи некой порождающей грамматики. Потому что каждому классу принадлежит только конечное число векторов, то «язык», соответственный векторам некого подпространства евклидова места Лекция 10 Грамматическая классификация образов описаний, можно рассматривать как конечный, т.е. содержащий только конечное число цепочек. Задачки систематизации цепочек не содержат формулировок на языке систематизации векторов. В самом общем смысле это те задачки, в Лекция 10 Грамматическая классификация образов каких принадлежность объекта какому-то классу зависит не от булевой композиции наличия либо отсутствия признаков, а от соотношения (может быть, сложного) меж составными частями объекта.

В процессе лингвистической систематизации участвует огромное количество инфы Лекция 10 Грамматическая классификация образов о структуре рассматриваемой цепочки. Важную роль структуры можно показать на примере из естественного языка (она может быть полезна также при анализе языков программирования). Какие из последующих цепочек эквивалентны?

Любит Мери Джон

Джон любит Мери

Мери Лекция 10 Грамматическая классификация образов любит Джона

Джон любим Мери.

Хоть какой человек знает, что только две последние цепочки имеют однообразное значение. 1-ая цепочка не является грамотным предложением. 2-ая, 3-я и четвёртая - грамотные предложения, но глубинная структура Лекция 10 Грамматическая классификация образов 2-ой отлична от глубинной структуры третьей и четвёртой. Для того, чтоб деяния с этими предложениями были осмысленными, нужно провести их систематизацию и раскрыть дела меж компонентами.

Исходя из убеждений реализации Лекция 10 Грамматическая классификация образов структурной систематизации Любопытно было бы выстроить вычислительную систему, которая могла бы распознавать устную речь. Выстроить такую машину оказалось очень тяжело по ряду обстоятельств. Одна из главных состоит в том, что на шаге обработки акустической инфы Лекция 10 Грамматическая классификация образов при распознавании речи исследуется структура физического сигнала, а не наличие какого-то определённого физического смысла.

Задачку определения образов на базе внедрения лингвистических способов принято именовать грамматическим выводом. В задачке Лекция 10 Грамматическая классификация образов вывода входными данными служит огромное количество цепочек, любая из которых считается порождённой некой неведомой грамматикой либо не согласующейся с нею. Цепочки можно рассматривать как описания определённых объектов из наружной среды, которые были сгруппированы Лекция 10 Грамматическая классификация образов по неведомому природному закону. К примеру, огромное количество воспринимаемых цепочек могло бы представлять собой описание треков, приобретенных в пузырьковой камере во время опыта по ядерной физике. Если б удалось раскрыть порождающую эти цепочки грамматику Лекция 10 Грамматическая классификация образов, то, возможно, её правила можно было бы увязать с нашими представлениями относительно физических процессов, происходящих в опыте.

Разглядим сейчас пример с утверждениями политического содержания.

^ Бедняки должны получать поддержку правительства. Те Лекция 10 Грамматическая классификация образов, кто

отрешается работать, не должны получать поддержки

правительства.

По отношению какого-нибудь лица к отдельным цепочкам этого утверждения можно в определённой мере судить о том, как он рассуждает о политике. Для этого Лекция 10 Грамматическая классификация образов нужно испытуемого попросить отобрать цепочки по утверждениям, с которыми он согласен и с которыми не согласен. В процессе такового отбора испытуемый устанавливает огромного количества принятых и отвергнутых цепочек некой (предполагаемой) грамматикой Лекция 10 Грамматическая классификация образов, которой он пользуется в согласовании со своими поли0тическими убеждениями.

Приведенные примеры иллюстрируют предпосылки, по которым необ­ходимо учить грамматический вывод в качестве задачки определения образов. Раскрытие грамматик в нетривиальном смысле аналогично построению теории Лекция 10 Грамматическая классификация образов в науке, так как грамматика, как и теория, есть не что другое, как совокупа правил для разъяснения тех либо других наблюдаемых явлений либо процессов.

По сей день, но, при помощи грамматического Лекция 10 Грамматическая классификация образов вывода не было получено особо нужных результатов, потому дальше будет затронуто то малое, что понятно, и как его можно использовать.


10.1. Задачки грамматического вывода

Подборкой именуется последовательность x,…,x цепочек знаков, избранных из . Подразумевается Лекция 10 Грамматическая классификация образов, что некие из этих це­почек порождены неведомой грамматикой . Обозначим через огромное количество тех цепочек из , которые допускаются грамматикой а через тех цепочек, которые отвергаются ею:



Предложения в и в будем именовать положительными и Лекция 10 Грамматическая классификация образов отрица-тельными, соответственно.

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

.

Точно также можно подразумевать машину Лекция 10 Грамматическая классификация образов, которая поочередно рассматривает огромного количества и сформировывает после каждого просмотра грамматику Задачка грамматического вывода разрешима, если сконструированная машина будет способна сформировать грамматику порождающую тот же язык, что и т.е.



В Лекция 10 Грамматическая классификация образов данном случае считается, что грамматика согласуется с . Это са­мое сильное из разумных определений решения. Тяжело представить о способности построения машины, которая cможет в конце концов воспроизвести конкретно так как Лекция 10 Грамматическая классификация образов может быть нескончаемо много грамматик, согласованных с Инфы, содержащейся в выборке, недостаточно, чтоб различать грамматики в таких парах.

Пробные грамматики должны выбираться из места гипотетичных грамматик, которые машина М способна сформировать. Если машина Лекция 10 Грамматическая классификация образов сформировывает грамматики из в неком фиксированном порядке, то молвят, что М перечисляет. На каждом шаге не плохая машина грамматического вывода должна выбирать из грамматику, «наиболее подходящую» конечной выборке . Считается, что грамматика Лекция 10 Грамматическая классификация образов удовлетворяет выборке, если она пра­вильно систематизирует все цепочки из и даёт «естественное» описание

огромного количества . В согласовании с аспектом простоты разъяснения грамматику следует предпочесть грамматике , если она содержит меньше правил, являющихся просто переформулировками соответствующей Лекция 10 Грамматическая классификация образов ситуации в рассматриваемой выборке.

Метод построения подборки может ограничить обилие выводов, которые можно выполнить на её базе, и эффективность процесса вывода. Более значительно различие меж подборками, содержащими только положительные предложения, и подборками Лекция 10 Грамматическая классификация образов, содержащими как положительные, так и отрицательные предложения. В первом случае представление именуется текстуальным, так как оно аналогично задачке для человека, пытающегося разобрать язык, используя тексты, содержащие только правильные конструкции. Во Лекция 10 Грамматическая классификация образов 2-м случае представление информаторное, так как тут аналогия со случаем, когда человек пробует осознать язык, задавая вопросы другому человеку, для которого этот язык родной.

В процессе грамматического вывода машина должна облагораживать вы­вод по мере Лекция 10 Грамматическая классификация образов приобретения инфы. Процесс вывода начинают с огромного количества грамматик, которые машина могла бы предложить, при всем этом подразумевается, что грамматика может быть согласована с некой грамматикой из этого огромного количества. На Лекция 10 Грамматическая классификация образов каждом шаге вывода некие грамматики могут отвергаться из-за их неспособности порождать какое-либо положительное предложение в , или какое-либо отрицательное предложение в выборке они считают допустимым. Пусть огромное количество грамматик, оставшихся в Лекция 10 Грамматическая классификация образов для исследования на шаге . Если машина вывода делает успехи, то огромное количество (t) должно равномерно уменьшаться, т.е. должно производиться соотношение

.

Если процесс вывода может привести к грамматике, согласованной с , то в Лекция 10 Грамматическая классификация образов некий момент G будет содержать те грамматики для которых

Для оценки того, как грамматика подходит для описания подборки , употребляется функция адекватности Функция может изменяться от 0 до , причём 0 интерпретируется как «совершенное Лекция 10 Грамматическая классификация образов описание» а значение показывает на то, что не содержит всех положительных предложений рассматриваемой подборки, либо содержит одно из отрицательных предложений, т.е. огромное количество грамматик не годится для описания подборки

^ 10.2.Объединение бейесовских Лекция 10 Грамматическая классификация образов процедур с лингвисти- ческим перечислением



Лингвистическое перечисление приводит к лучшей пробной грамматике для данной подборки. Статистический подход к грамматическому выводу приписывал бы каждому кандидату в грамматику возможность быть «правильной» грамматикой. Процедура объединения этих 2-ух подходов Лекция 10 Грамматическая классификация образов базируется на учёте вероятности возникновения предложения. Пусть порождающая грамматика, а стохастическая грамматика, которая выходит из , если каждой её продукции приписать вероятностную меру . Эта мера определяет возможность того, что к цепочке r будет Лекция 10 Грамматическая классификация образов использована продукция Произнесенное иллюстрируется примером, оформленным в виде таблиц 10.1 и 10.2


Таблица 10.1


Продукция

Возможность внедрения



2/3



1/3



1/4



3/4



1/4



3/4



Таблица 10.2

Вывод цепочки







3/4





2/3





1/4





3/4









Перемножая вероятности из правого столбца таблицы 10.2, находим возможность порождения цепочки x а конкретно

Незначительность Лекция 10 Грамматическая классификация образов данной величины обоснована тем, что хоть какое конкретное предложение языка всегда имеет маленькую возможность.

Две стохастические грамматики, порождающие один и тот же язык, могут отличаться вероятностями возникновения отдельных предложений.

Две грамматики и Лекция 10 Грамматическая классификация образов именуются стохастически согласованными, если они порождают один и тот же язык, т.е.

и имеет место равенство для всех

Разглядим пример, в каком экспериментатор выбирает грамматику с целью написания предложений подборки, определяющей эту грамматику Лекция 10 Грамматическая классификация образов. Если обозначить возможность выбора хоть какой определенной грамматики для использования её в качестве и представить, что обучающая машина (либо машина вывода) может вычислить априорной вероятностью выбора . Для вывода по применим бейесовскую функцию Лекция 10 Грамматическая классификация образов и определим апостериорная возможность

(10.1)

Вычислить (10.1) тяжело, так как это нескончаемое огромное количество, правда, не все его элементы различны. Эта трудность обходится оковём ограничения вычислений обилием грамматик, априорные вероятности которых превосходят некое произвольно Лекция 10 Грамматическая классификация образов маленькое число . Но, если ограничится только каким-то подмножеством

огромного количества вероятных грамматик, то с некой произвольно

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

Обозначенная неувязка Лекция 10 Грамматическая классификация образов решается минимизацией функции несовместимости. Представим, огромное количество упорядоченно по возрастанию априорных вероятностей его грамматик: . То же упорядочение даёт оккамовское перечисление, в каком употребляется функция внутренней трудности

. (10.2)

Функция трудности вывода, которая должна отражать возможность возникновения подборки Лекция 10 Грамматическая классификация образов, выбирается последующим образом

(10.3)

Бейесовское решающее устройство на каждом шаге процесса вывода должно выбирать единственную грамматику так, чтоб величина

(10.4)

была наибольшей. Это эквивалентно минимизации функции несовместимости

(10.5)

где и определяются формулами (10.2) и (10.3). Отсюда видно, что Лекция 10 Грамматическая классификация образов существует процедура перечисления, минимизирующая на каждом шаге процесса предъявления функцию несовместимости и выбирающая ту же грамматику, что и бейесовская процедура. Как следует, можно выстроить бейесовский метод вывода, который позволяет отыскивать для каждой Лекция 10 Грамматическая классификация образов подборки лучшую грамматику.


^ Бейесовский метод перечисления для стохастического

текстуального представления

1.Пустьоккамовское перечисление нескончаемого огромного количества , использующее функцию внутренней трудности вида (10.2).

2.При данной выборке отыскать такое меньшее целое , что . Подсчитать значение

. (10.6)

3.Отыскать такое меньшее целое , что Лекция 10 Грамматическая классификация образов . Ясно, что

(10.7)

Потому что (10.7) справедливо для хоть какого , то для максимизации на целое число , должно лежать в интервале (,).

4.Избрать из огромного количества , пользуясь обыкновенной процедурой вывода. Этим определяется лучший выбор грамматики из Лекция 10 Грамматическая классификация образов , объясняющей . Добавить к , образовав , и повторить процесс с шагом 2.

Таким макаром, бейесовскую индукцию можно использовать для выбора лучшей грамматики, объясняющей фиксированную подборку.






lekciya-16-deyatelnost-strahovih-organizacij-v-usloviyah-perehoda-k-rinku.html
lekciya-16-epoha-ellinizma.html
lekciya-16-konstruirovanie-metallicheskih-konstrukcij-stiki-i-uzli-sopryazheniya.html