Главная > Распознавание образов > Лекции по теории образов: Анализ образов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.3. Разбиение слов на классы

Важнейший элемент алгоритма абдукции — это процедура поиска разбиения на классы эквивалентных слов. Если это удается сделать, то «комбинаторная сложность» задачи существенно понижается, так как в результате возникает возможность работать на уровне претерминалов вместо терминалов. Число слов в тестовой грамматике уменьшается при этом с 52 до 23. Вероятно, что при работе с естественным языком подобное сокращение окажется даже более существенным.

Но это не единственная причина того, почему этому вопросу уделяется столько внимания. Ниже мы убедимся, что именно в этой задаче разбиения и заключается основная математическая сложность: если она будет решена, то аналогичные рассуждения позволят справиться с задачей полной абдукции для автоматных грамматик. Следовательно, необходимо подробно изучить эту подзадачу.

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

Как было показано в предыдущем разделе, предложение I будет деформировано посредством и перейдет в I в результате замены одного или нескольких вхождений на у. Если не входит в никакие изменения не производятся. Нам придется точно описать, как происходит это замещение, когда мы подвергнем математическому анализу но сейчас достаточно

указать, что алгоритм не может быть абсолютно правильным и поэтому требуется ввести вероятности ошибок

— вероятность положительного результата в тесте, несмотря на то, что

— вероятность отрицательного результата в тесте, несмотря на то, что

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

Для вычисления мы должны точно определить алгоритм тестирования; будет приведен один пример такого вычисления. При вариациях алгоритма тестирования соответствующее соотношение не будет выполняться точно, хотя оно может указать порядок Допустим, что обнаружено первое вхождение (если оно вообще имеет место) и проведена замена на у. Чтобы определить для фиксированных х и у, можно рассуждать так: Вероятность порождения какого-нибудь предложения, имеющего в первой позиции и длину равна

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

суммирование проводится по и по Можно выписать подобные выражения для любой позиции вплоть до

Определим

Чтобы деформированное изображение необходимо при первом вхождении позиции выполнение для некоторой последовательности следующего соотношения:

Событие, заключающееся в том, что I содержит будет тогда иметь вероятность рхуу которую можно определить с помощью выражений (7.3.2) и (7.3.3), включив правую часть (7.3.5) в качестве множителя в члены этих выражений, суммируя, как было сказано, и, кроме того, по Выполнив эти операции, мы получим следующее:

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

Тогда выражение (7.3.6) можно записать как

Это дает нам

Отметим, что и линейные операторы, представленные трехмерным и четырехмерным массивами соответственно, а второй единичный оператор обозначает тождество, определенное с помощью четырех индексов:

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

суммирование проводится по если воспользоваться (7.3.7), то последнее выражение приобретает следующий вид:

где .

Рассмотрим условную вероятность того, что не обнаружено, если входит в предложение и заменяется на у:

Из-за наличия множителя в выражении (7.3.9) создается впечатление, что его трудно непосредственно вычислить. Можно предложить прямую и полезную интерпретацию матрицы Обратимся к рис. 7.3.1, на котором представлено порождение двух рассматриваемых цепочек Обратившись к (7.3.6), нетрудно убедиться в том, что элемент матрицы представляет собой вероятность порождения некоторой подцепочки, началом которой служит состояние у, а концом — состояние причем та же лексическая цепочка обеспечивает также переход из состояния Матрица не должна быть обязательно симметрической.

Элементы должны подчиняться рекуррентному соотношению

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

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

Введем отношение Е, связывающее состояния, причем если существуют

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

Рис. 7.3.1.

Объединив (7.3.11) с (7.3.9), мы получаем вероятность того, что деформация не обнаруживает

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

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

Вместо этого следует выбирать х и у так, чтобы проверке подвергались лишь «критические» случаи, когда существуют реальные

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

Алгоритм разбиения

Шаг 1. Работа алгоритма начинается с создания единственного класса, включающего все и выбора одного слова в качестве прототипа класса.

Шаг 2. Алгоритм порождает какое-либо предложение языка в соответствии с моделью синтаксически управляемой вероятности (неизвестной).

Шаг 3. Алгоритм (см. ниже) выбирает вызывается текущий прототип у. Производится переход к шагу 4, если прототип, в противном случае переход к шагу 5.

Шаг 4. Выбирается другое слово из класса, содержащего этот прототип, с вероятностями, убывающими с расстоянием. Проверяется , и над осуществляются те же операции, что осуществляются над на шагах Переход к шагу 2.

Шаг 5. Алгоритм воспроизводит деформированную цепочку где у равен прототипу того класса, к которому в данный момент принадлежит Определяется грамматическая правильность М Переход к шагу 7, если

Шаг 6. Если то алгоритм увеличивает правдоподобие за счет того, что перемещается ближе к у в данном классе, если это возможно. Другими словами, и соседний по направлению к у элемент меняются местами до тех пор, пока соседним элементом не окажется у. Переход к шагу 2 (или останов).

Шаг 7. перемещается к концу соседнего класса, если таковой существует; в противном случае переход к шагу 8.

Шаг Создается новый класс, в котором является единственным элементом и прототипом.

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

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

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

Рис. 7.3.2.

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

Теорема 7.3.1. Алгоритм обеспечивает разбиения, сходящиеся с вероятностью единица к истинному разбиению за конечное число шагов.

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

хотя, быть может, и очень мала. При наличии события Е шаг 8 алгоритма вводит новый класс. Используя обращение леммы Бореля—Кантелли (см., например, Феллер (1967), т. 1, с. 205), мы обнаруживаем, что это имеет место с вероятностью единица для бесконечной последовательности предложений, порожденных так, что почти наверное равна истинному числу классов. Благодаря способу выбора прототипов они все взаимно неэквивалентны. Следовательно, с вероятностью единица они представляют истинные классы эквивалентности, хотя их «маркировка» может отличаться от использовавшейся первоначально.

Перемещения, обусловленные алгоритмом (см. рис. 7.3.2.), происходят частично в пределах «своих» классов, а частично между классами. Первый тип перемещений непосредственно на разбиение не влияет и характеризует лишь изменения наших представлений. Второй тип перемещает слово вниз, в другой класс или в некоторый новый класс. Это означает, что, как только значение достигнуто, алгоритм лишь удаляет слова из тех классов, к которым они не принадлежат. Слово почти наверное не будет оставаться в неправильном классе на протяжении более чем конечного числа итераций. Следовательно, разбиения сходятся к истинному разбиению после некоторого конечного числа шагов.

Наша теорема гарантирует состоятельность этого процессора образов, но ничего не говорит о скорости сходимости. Чтобы разобраться с этим вопросом, несколько совершенно различных вариантов алгоритма были реализованы и опробованы на вычислительной машине.

Для случая тестовой грамматики (разд. 7.2) слова были быстро разбиты на классы эквивалентности еще на ранней стадии выполнения алгоритма. Затем скорость обучения существенно уменьшается. В типичном прогоне после прослушивания и обработки 200 предложений была определена большая часть из 23 классов эквивалентности и лишь два слова из 52 были классифицированы неверно.

Соответствующие графики приведены на рис. 7.3.3, где представлено число правильно классифицированных слов в зависимости от числа предложений, и на рис. 7.3.4, где показано количество выделенных классов слов.

В каком-то смысле этот алгоритм абдукции удовлетворяет требованиям разд. 7.2. «Единственный» он или нет —об этом можно судить по-разному, но этот алгоритм по крайней мере более естествен, чем некоторые альтернативные варианты. Он явно обладает быстродействием, хотя мы ничего не утверждаем относительно его оптимальности, он нечувствителен к ошибке которая играет фундаментальную роль в выводе на основании правдоподобия.

Рис. 7.3.3. (см. скан)

Рис. 7.3.4. (см. скан)

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

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

Поскольку в алгоритме отсутствует шаг, предусматривающий объединение классов, эта ошибка не будет устранена вообще.

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление