Автоматическое порождение правил транскрипции фамильно именных групп

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

ИПМ им. М.В. Келдыша РАН

Автоматическое порождение правил транскрипции фамильно_именных групп

Э.С. Клышинский

В.К. Логачева

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

Введение

Проблема передачи фамильно_именных групп и имен собственных в целом средствами другого языка постоянно возникает в самых разных областях. В разное время наибольшей популярностью пользовались разные подходы, но с середины XX века господствующей тенденцией стала передача звучания имени при его переводе на иностранный язык. К ранним работам в области создания систем автоматической транслитерации и транскрипции имен собственных относятся работы группы Найта. Изначально проводилась транслитерация с японского языка на английский [Knightetal., 1998]. Вскоре этот метод был адаптирован для работы с арабским языком [Al-Onaizanetal., 2002]. Основной задачей метода являлось обнаружение и восстановление имен собственных, уже переданных с использованием другого алфавита. В качестве основы использовался модифицированный алгоритм Витерби.

Однако базовый принцип использования лишь отдельных символов алфавита не позволял получить высокие показатель качества передачи. В связи с этим стали применяться методы, использующие подстроки [Sherif, 2007]. Применение подстрок взамен отдельных символов позволило повысить качество транслитерации примерно с 30 до 90%.

Еще одной важной задачей здесь является автоматическое обучение системы переходов конечного автомата (КА), используемого в перечисленных методах. На данный момент развиваются методы как обучения с учителем [Knightetal., 1998], так и без него [Taoetal., 2006]. Последние работы позволили перейти к обучению по одноязычному корпусу [Ravietal., 2009], что привело, правда, к существенному падению качества передачи.

Данная работа основана на программе «Трансскриба» [Klyshinskyetal., 2008]. В отличие от рассмотренных работ, здесь используется не стохастический, а детерминированный подход, при котором правила пишет эксперт. Метод позволяет повысить эффективность передачи, но требует создания системы правил - правила для одного языка создаются от нескольких недель до нескольких месяцев, в зависимости от сложности задачи.

1. Метод транскрипции

Предлагаемый в данной работе метод объединяет удобство и скорость разбора с использованием КА с удобством представления правил преобразования в привычном для человека виде. Правила преобразования цепочек из одного языка на другой представляются в виде «входная цепочка» ? «выходная цепочка». Скорость работы алгоритма зависит от размеров базы и длины входной цепочки. В данной статье используется КА, скорость работы которого линейна. Скорость разбора с использованием КА пропорциональна длине цепочки.

Здесь мы считаем, что набор правил может быть создан лингвистом или получен в ходе машинного обучения. При необходимости специалист работает в привычных ему терминах правил. Далее набор правил может быть расширен за счет дообучения. В другом случае набор правил может быть изначально автоматически сформирован с использованием предлагаемого метода. Набор правил преобразуется в КА, который используется для передачи имен собственных с языка на язык.

1.1 Структура конечного автомата

Используемый нами автомат представляет собой преобразователь. Его можно представить как множество g = <VI, VO, Q, q0, F, д>

VI- входной алфавит (алфавит языка оригинала);

VO - выходной алфавит (алфавит языка перевода)Входной и выходной алфавиты включают символы начала “<” и конца “>” слова.;

Q - множество состояний автомата;

q0- начальное состояние автомата;

F - множество конечных состояний;

д - функция переходов Q?VI?<Q, a>.

Здесь a - это действие, совершаемое при переходе, причем a-A - множеству действий, выполняемых КА при переходе.

A = {out(), shift()}

Out(s) - функция, подающая на выход строку символов s (в том числе пустую) из алфавита перевода.

Shift(n) - функция, выполняющая сдвиг рассматриваемой строки на n символов.

1.2 Описание правил транскрипции

За основу был взят метод, описанный в [Klyshinskyetal., 2008]. Так как в предлагаемом методе правила используются прежде всего для пополнения матрицы переходов КА и генерируются компьютером, а не человеком, их структура отличается от базового варианта.

В нашем случае правило представляется в виде тройки r = <p, c>, где:

p - непустое упорядоченное множество символов из алфавита языка оригинала, p=<p1, p2, p3>, где p1и p3 - пред- и постусловия соответственно (левый и правый контекст правила), а p2- преобразуемая подстрока,p2=<v1, v2, …, vn2>, p1=<{v1}, {v2}, …, {vn1}>, p3=<{v1}, {v2}, …, {vn3}>, где vi-VI, i-[1,nj], nj=|pj|.

c - упорядоченное множество символов из алфавита языка перевода, которым передается множество символов p в языке перевода, c=<w1, w2, …, wnс>, где wi-VO,i-[1,nc], nc=|c|.

Правило применимо с текущей позиции, если на текущей позиции находится подстрока p2, перед ней - подстрока, на соответствующих позициях которой находятся символы из p1, а после нее - подстрока, на соответствующих позициях которой находятся символы из p3.

Считается, что к входной строке последовательно ищутся применяемые правила. При нахождении такого правила текущая позиция сдвигается вправо на n2, а на выход подается c.

1.3 Преобразование правил в конечный автомат

транскрипция автомат конечный имя

Для правила r = <p, c> процедура добавления в КА будет следующей. Здесь за исключением начального состояния q0, все состояния заводятся для данного правила заново. При этом дополнительным алгоритмом обеспечивается уникальность нумерации состояний.

Для правил, в которых левый контекст пуст, в КА добавляется переход из состояния qi-1 в qi по символу vi из p2, i-[1,n2]. При этом никакие действия не совершаются. Состояние qn2 помечается как конечное.

Для правил, в которых правый контекст пуст, в КА добавляется переход из qn2в q0 по e-символу, сопровождаемый Shift(n2) и Out(c).

Для правил, в которых правый контекст не пуст, в КА добавляется переход из состояния qn2+i-1 в состояние qn2+i по всем символам из {vi} из p3, i-[1,n3]. Далее в КА добавляется переход из qn2+n3 в q0 по пустому символу, сопровождаемый действиями Shift(n2) и Out(c).

Для правил, в которых левый контекст не пуст, для всех qf-F в КА добавляется переход из qfв qn2+n3+1 по всем символам {v1} из p1, и переходы из состояния qn2+n3+i-1 в состояние qn2+n3+i по всем символам из {vi} из p1, i-(1,n1]. При этом никакие действия не совершаются. Далее в КА добавляется переход из qn1+n2+n3 в q0 по пустому символу, сопровождаемый действиями Shift(n2) и Out(c).

Подобные операции проводятся для всех правил.

2. Порождение правил

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

2.1 Разделение слова на слоги

Термин «слог» в данном контексте употребляется в смысле, отличном от того, в котором он используется в трудах по фонетике. Поэтому необходимо дать его определение. Слог - это непустое множество букв, содержащее один или более символов, обозначающих гласные звуки. Слово делится на слоги по следующим правилам:

деление осуществляется по гласной букве. Граница слога - после гласной;

2 и более гласных подряд не разделяются;

2 и более согласных не разделяются;

множество элементов, среди которых нет гласной, не выделяется в отдельный слог;

символы начала и конца слова считаются согласными буквами;

(для русского) не отделять «ь» от предыдущей согласной.

Таким образом, слог - это цепочка вида C*V+, где С - буква, обозначающая согласный звук, V - буква, обозначающая гласный звук. Слог может иметь вид C*V+C+ только случае, если это последний слог в слове и заключительное множество согласных не может быть выделено в отдельный слог, так как среди них нет слогообразующего символа.

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

2.2 Порождение первичных правил

Первый этап порождения правил - порождение первичных правил. Первичными правилами мы называем правила транслитерации, то есть правила, для которых |p2| = |c| = 1.

Первичные правила порождаются на основе слогов вида CV > CV: i-му символу слога ставится в соответствие i-й символ его перевода, при условии, что оба символа обозначают звуки одного и того же типа (гласные или согласные). При таком подходе вероятность порождения некорректного правила очень мала.

В порожденном множестве первичных правил могут содержаться неоднозначности, то есть пары правил r1 = <p, c> и r2 = <p, c> такие, что r1(p2) = r2(p2) и r1(c) ? r2(c). Такие ситуации в принципе возможны в языке, но на данном этапе неоднозначность, скорее всего, обозначает влияние на букву окружающих ее букв. Для избавления от неоднозначностей вводится новый тип правил - временные правила.

Временными правилами мы называем правила, используемые при обучении системы правил. Временное правило представляет собой тройку r= <p, c, s>, где p и c описаны выше (см. п. 1.2); s - множество слогов, удовлетворяющих правилу.

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

Избавление от неоднозначностей производится следующим образом.

Для каждого правила ri, для которого существует rj, такое что ri(p2) = rj(p2), ri(c) ? rj(c), для каждого sk из ri(s) составляется новое правило rik = <p, c, s>, такое, что: rik(p2) = ri(p2), rik(c) = ri(c), rik(p1) = <{v1}>, где v1-VI - символ, предшествующий p2 в слоге sk, rik(p3) = <{v3}>, где v2-VI - символ, следующий за p2 в слоге sk. В случае если p2 - начальная или заключительная подстрока в слоге, v1 и v2 берутся из предыдущего или следующего слога соответственно.

После порождения системы первичных правил производится расширение их контекстов на основе слогов вида CnV > CnV, где n > 1. Каждый слог si, который не может быть целиком разобран с помощью существующей системы правил, можно представить как <pi1, …, pik, px, pik+1, …, pin> > <ci1, …, cik, cx, cik+1, …, cim>, где px > cx - подстрока, не удовлетворяющая ни одному из существующих правил. Можно выделить три случая несоответствия px правилам:

существует ri такое, что px = ri(p2), cx = ri(c), но pik ? {v11} или pik+1  {v31} (т.к. ri(p1) = <{v11}>, ri(p3) = <{v31}>). В этом случае контекст правила ri расширяется: ri(p1) = <{v11, pik}>,ri(p3) = <{v31, pik+1}>;

не существует ri такого, что px = ri(p2) и cx = ri(c). В этом случае составляется новое правило rj такое, что rj(p1) = <{pik}>, rj(p2) = px, rj(p3) = <{pik+1}>, rj(c) = cx, rj(s) = {si};

существует ri такое, что px = ri(p2), pik - {v11} и pik+1 - {v31} (т.к. ri(p1) = <{v11}>, ri(p3) = <{v31}>), cx ? ri(c). Это может объясняться одной из следующих причин:

контекст правила ri недостаточен для правильной интерпретации подстроки, и надо рассматривать не один, а несколько символов, предшествующих ей или следующих за ней. Например, для имени Marin > Марен (франц.) было порождено правило i > е, которое при избавлении от неоднозначностей приобрело вид i{n}> е. Но имя Marine > Марин не удовлетворяет этому правилу, потому что i переходит в е(э) только если после него стоит n и слог является закрытым (заканчивается на согласную). В этом случае нужно проверять не один, а два следующих за i символа.

Подстрока может читаться двумя различными способами в силу причин, не зависящих от контекста. В шведском языке е читается как «о», однако в машиночитаемых текстах без диакритик е заменяется на аа. Между тем сочетание двух шведских букв а будет передаваться на русский язык как «аа». В тестовой выборке для шведского языка можно встретить примеры неоднозначностей Baad > Баад, Baang > Бонг, Haapanen > Хаапанен Haafman > Хофман, которые нельзя предугадать, имея в качестве обучающей выборки машиночитаемый файл. Значит, для каждого шведского имени, содержащего подстроку «aa», будет сгенерировано два варианта перевода.

В настоящее время нет алгоритма выбора одной из двух описанных причин и избавления от подобных неоднозначностей.

2.3 Порождение сложных правил

Более сложные правила порождаются по следующему алгоритму:

отбираются слоги определенной структуры;

множество отобранных слогов проверяется с помощью КА;

к подмножеству, не принятому КА (то есть, к слогам, для которых выход КА не совпал с переводом), снова применяются правила: происходит проверка слога справа налево и слева направо для выделения подстроки, не удовлетворяющей существующим правилам;

по возможности на основе подстроки, не удовлетворяющей правилам, производится расширение контекста какого-либо из существующих правил (по алгоритму, описанному в п.2.2);

для каждого слога, который не удалось объяснить после расширения контекста существующих правил, составляется кандидат в правило: подстрока оригинала слога и подстрока перевода, не объясненные правилами;

кандидаты в правила, удовлетворяющие определенным требованиям, добавляются в систему правил;

при появлении в системе правил неоднозначностей правила уточняются путем добавления контекста;

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

Порядок рассмотрения слогов:

слоги вида CnV > CnV - принимаются кандидаты в правила вида v1 > v2, где v1-VI, v2-VO (пополнение системы первичных правил) ;

слоги вида CnV > CmV, n>m - принимаются кандидаты вида <v1> > v2, где ?v-<v1>: v-VI, v2-VO (правила передачи устойчивых сочетаний согласных одной буквой русского алфавита);

слоги вида CnV > CmV, n<m - принимаются кандидаты вида K > B, где K-VI, B-VO (правила передачи согласной несколькими буквами русского алфавита);

слоги вида CpVn > CqVm, n>m - принимаются кандидаты вида K > B, где K-VI, B-VO (правила передачи устойчивых сочетаний гласных);

прочие слоги - принимаются кандидаты произвольного вида.

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

2.4 Нормализация системы правил

Нормализация системы правил состоит в избавлении от правил, полностью или частично дублирующих друг друга.

Для двух правил r1 = <p, c, s> и r2 = <p, c, s>, где r1(p1) = r2(p1) = r1(p3) = r2(p3) справедливо утверждение r1 = r2, если r1(p2) = r2(p2) и r1(c) = r2(c). В этом случае правила r1 и r2 заменяются правилом r3 = r1?r2 = <p, c, s>, где r3(p1) = r3(p3) =, r3(p2) = r1(p2) = r2(p2),r3(c) = r1(c) = r2(c) и r3(s) = r1(s)? r2(s).

Два правила r1 = <p, c, s> и r2 = <p, c, s>, для которых хотя бы одно из множеств r1(p1), r2(p1), r1(p3), r2(p3) не пусто, считаются эквивалентными, если r1(p2) = r2(p2), r1(c) = r2(c), |r1(p1)| = |r2(p1)|, |r1(p3)| = |r2(p3)|, и выполняется хотя бы одно из неравенств r1(p1) ? r2(p1) ? ?, r1(p3)  r2(p3) ? . В этом случае правила r1 и r2 заменяются правилом r3 = r1  r2 = <p, c, s>, где r3(p1) = r1(p1) ? r2(p1), r2(p3) = r1(p3)  r2(p3),r3(p2) = r1(p2) = r2(p2),r3(c) = r1(c) = r2(c) и r3(s) = r1(s) r2(s).

В конце этапа нормализации проводится проверка на предмет порождения «фантомных» правил, для которых имеются противоречащие им тестовые примеры, и их удаление.

3. Реализация метода. Результаты экспериментов

Нами были программно реализована часть этапов описанного метода: происходит деление слов из тестовой выборки на слоги, отбор слов, подходящих для участия в порождении правил, составление первичной системы правил, избавление ее от неоднозначностей (правил с одинаковыми левыми и различающимися правыми частями) и добавление полученной системы к КА. Программа протестирована на примерах из французского и шведского языков. В обоих случаях полученная система правил не полна, но корректна. Процедура избавления от неоднозначностей выделяет различия в правилах чтения некоторых согласных перед гласными (см. 1), и в начальной и неначальной позициях (см. 2). Напомним, что для букв также выделяются правила их чтения без учета контекста. Порождаются некоторые правила преобразования устойчивых сочетаний согласных (см. 3).

(1) правила чтения буквы «c» перед гласными переднего и заднего рядов (шведский язык):

<ca > <ка , <co > <ко , <ce > <се , <ci > <си

(2) правила чтения буквы «s» в позиции в начале и в середине слова (французский язык):

si > зи , <si > <си , se > зе , <se > <се , sa > за

(3) правила чтения устойчивых сочетаний согласных:

rs > ш (швед.), ph > ф (франц.), ch > ш (франц.)

4. Обсуждение метода

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

Механизм использования контекста в настоящее время также несовершенен. В правилах используются только «простые» контексты: составляются множества символов, которые могут стоять на n-й позиции слева и справа от рассматриваемой цепочки. Однако иногда необходимо учитывать более сложные условия, например, закрытый слог.

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

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

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 10-01-00800).

Список литературы

Al-Onaizan Y., Knight K. Machine Transliteration of Names in Arabic Text. In Proceedings of the ACL Workshop on Computational Approaches to Semitic Languages. - 2002.

Klyshinsky E., Maximov V., Yolkeen S. Cross-Language Transcription of Proper Names: Language Forum. Vol. 34, № 1. 2008.

Knight K., Graehl J. Machine transliteration. Computational Linguistics, 24(4), 1998.

Ravi S., Knight K., Learning Phoneme Mappings for Transliteration without Parallel Data. Human Language Technology Conference archive Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics. 2009.

Sherif T., Kondrak G. Substring-Based Transliteration. In Proceedings of the ACL Workshop on Computational Approaches to Semitic Languages. 2007.

Tao T., Yoon S., Fister A., Sproat R., Zhai C. Unsupervised named entity transliteration using temporal and phonetic correlation. InProc. ofEMNLP. 2006.

Размещено на Allbest.ru