diploma-3 (1015783), страница 4
Текст из файла (страница 4)
. . ωm ))P 0 (ωm |ω1 . . . ωm−1 ) = ∑ (δ + частота (ω1j . . . ωmj )i=δ + частота (ω1 . . . ωm ))∑(δ·V +частота (ω1j . . . ωmj )iV – количество всех n-грамм в используемом корпусе. Наиболее простымслучаем аддитивного сглаживания является метод, когда δ = 1 – метод сглаживания Лапласа [58].Существуют и другие техники сглаживания вероятностей (ГудаТьюринга, Катца, Кнезера-Нейя [2]),23ВЫЧИСЛЕНИЕ МОДЕЛИ ПЕРЕВОДАОбозначим:• Θe — «английский» текст (множество предложений);• Θr — «русский» текст;• Πe — «английское» предложение (последовательность слов);• Πr — «русское» предложение;• ωe — «английское» слово;• ωr — «русское» слово;• le ← |Πe |;• lr ← |Πr |;• πωr ← позиция ωr в Πr ;• πωe ← позиция ωe в Πe .Пусть P (Πe |Πr ) — вероятность некоторой строки (предложения) из e,при гипотезе перевода из r.
По аналогии c моделью языка можно предположить, чтоP (Πe |Πr ) =частота (Πe , Πr );частота (Πr )Однако это не верно. Для вычисления модели перевода нужно:• разделить предложение на меньшие части;• ввести новую переменную a, представляющую выравнивания междуотдельными словами в паре предложений.P (Πe |Πr ) =∑aP (Πe , a|Πr );24Вероятность перевода:le∏εP (Πe , a|Πr ) =t(ωej |ωra(j) )(lr + 1)le j=1t – это вероятность слова оригинала в позиции j при соответствующем емуслове перевода ωra(j) , определенном выравниванием a. ε — нормализующая«константа».
В этой работе ε выбирается равным 1, но если рассуждать болеестрого, ε — распределение вероятностей длин предложений каждого из языковε = ε(le |lr )Для приведения P (Πe , a|Πr ) к P (a|Πe , Πr ), т.е. к вероятности данного выравнивания при данной паре предложений, каждая вероятность P (Πe , a|Πr )нормализуется по сумме вероятностей всех выравниваний данной пары предложений:P (Πe , a|Πr )P (a|Πe , Πr ) = ∑P (Πe , a|Πr )aИмея набор выравниваний с определенными вероятностями, можно подсчитать частоты каждой пары слов, взвешенные по вероятности выравниваний, в которых они встречаются. Например, если какая-то пара слов встречается в двух выравниваниях, имеющих вероятности 0.5 и 1, то взвешеннаячастота (counts) такой пары равна 1.5 [55].counts(ωe |ωr )counts(ωe |ωr )=;t(ωe |ωr ) = ∑counts(ωe |ωr )total(ωr )ωeТребуется оценить вероятности лексического перевода t(ωe |ωr ) из параллельного корпуса (Θe , Θr ).
Но чтобы сделать это нужно вычислить a, которойу нас нет. Возникает так называемая «проблема курицы и яйца». Для оценки параметров модели нужно знать выравнивания. Для оценки выравниваниянужно знать параметры модели.25При решении этой проблемы используют EM-алгоритм (Витерби), который более детально рассмотрен в приложении. EM-алгоритм:1) Инициализируем параметры модели (одинаковыми значениями, напервой итерации);2) Оценим вероятности отсутствующей информации;3) Оценим параметры модели на основании новой информации;4) Перейдем к следующей итерации.1.3.2. ДЕКОДИРОВАНИЕ ССМПДекодер нужен для осуществления непосредственно перевода. Он вычисляет величинуarg max (P (ϕe ) · P (ϕr |ϕe ))∪ϕeЗадача декодирования является NP-полной [7].
Существует несколько способов и методов декодирования. Обычно выделяют:• полный перебор;• поиск по первому наилучшему совпадению (A*):– стековый поиск,– мультистековый поиск;• жадный инкрементный поиск;• сведение к обобщенной (асимметричной или симметричной) задачекоммивояжера:– задача ЛП,– метод Лина-Кернигана,– генетические алгоритмы,– «муравьиная оптимизация».26Каждый из методов обладает своими достоинствами и недостатками. Вариант полного перебора мы рассматривать не будем, так как, если мы ограничим наш поиск в строке не более чем в два раза длины m строки исходногоязыка, то мы получим наивный метод c сложностью O(m2 v 2m ) [7].В данном случае можно рассмотреть только часть пространства возможных состояний. При этом, скорее всего, мы можем пропустить самое хорошеерешение, но сможем найти «достаточно хорошее».
Для алгоритмов декодирования важными параметрами являются скорость, поиск ошибок, качествоперевода.ПОИСК ПО ПЕРВОМУ НАИЛУЧШЕМУ СОВПАДЕНИЮПоиск учитывает как расстояние от начального состояния и оценки расстояния до цели. В приложении декодирования имеем следующий алгоритмдля стекового поиска:1) Инициализируем стек пустой гипотезой.2) Достаем лучшую гипотезу h из стека.3) Если h — все предложение, выводим его и завершаем выполнение.4) Для всех возможных следующих слов ω расширить гипотезу h и положить обратно в стек.5) Перейти ко второму шагу.«Стековым» поиск назван по историческим причинам, на самом деле используется очередь с приоритетами.Большим минусом этого поиска является, то что более короткие гипотезыимеют приоритет.
Мультистековый поиск отличается наличием отдельного«для гипотез» разного размера. Крайне не экономичен по памяти. Для уменьшения пространства поиска возможны различные ухищрения, основанные назнаниях о структуре предложения.27ЖАДНЫЙ ИНКРЕМЕНТНЫЙ ПОИСКПростой поиск, позволяет достичь решения путем выбора лучшей альтернативы, чтобы добраться до цели в настоящее время. Эвристическая функцияопределяется как стоимость самого дешевого пути из текущего состояния вцелевое состояние. Жадный инкрементный поиск имеет следующие особенности:• «плохой» вариант перевода получаем сразу;• последовательно применяя набор операций можем улучшить перевод:– изменить перевод слова (группы слов),– удалить слово (группу слов),– поменять слова местами.В оригинальной работе [4] приводится иной набор операций, но он относится исключительно к моделям высшего порядка (IBM 3-5).
Дело в том, чтомодели высших порядков учитывают наличие фертильности слова — величину показывающую сколько слов языка перевода способно породить данноеслово исходного языка. C понятием фертильности связано понятие нулевого слова. Нулевое слова— слово исходного языка не имеющее графическогоначертания в тексте, и какого либо еще своего проявления, кроме того, чтооно обладает ненулевой фертильностью.
Кроме того, в классических моделях используется биграммная модель языка. В связи с этим, к описаннымвыше опирается сразу добавляются замены слов в зависимости от их фертильности, вставки слов в какой либо участок между словами, вставка слови их одновременная замена. В этой работе мы не вводим формальное описание моделей высших порядков, так как это займет достаточно внушительныйобъем.
Потому мы привели упрощенную версию алгоритма жадного поиска.Именно такая версия поиска используется нами в практической части работы. Выносить отдельно описание мы тоже не стали, так как ничем особенноновым этот вариант поиска не отличается. Всего скорее такой алгоритм будетпроходить по циклу операции быстрее оригинального, но этот факт требуетдополнительных исследований и количественных измерений. В любом случае ясно, что за меньшее число операций придется платить большим количеством итераций алгоритма.28Жадный поиск может стартовать из начального состояния, которое ниприведет к конечной цели.
Не является полным или оптимальным. Однако,это самый быстрый из существующих методов. Жадный инкрементный поиск используется в данной работе.СВЕДЕНИЕ К ОБОБЩЕННОЙ ЗАДАЧЕ КОММИВОЯЖЕРАИсходными данными для задачи является множество вершин, разбиениеэтого множества на подмножества, и также матрица стоимостей перехода изодной вершины в другую.
Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом подмножестве.__Если для двух смежных вершин |AB| 6= |BA|, то задача является асимметричной. Для декодирования имеем:• подмножество вершин — слово исходного текста ωr ;• вершина — вариант перевода ωe (обычно выбирают 10 наиболее вероятных вариантов);• расстояние — величина неопределенности − log (P (ϕe ) · P (ϕr |ϕe )).Обобщенная задача коммивояжера (OЗК) сводится к простой задаче коммивояжера (ЗК) при помощи алгоритма Нуна-Бена [19].
Далее ее решаютсредствами линейной оптимизации (крайне медленный вариант), эвристических алгоритмов, генетических алгоритмов, методов роевого интеллекта.Для данной работы сведения задачи декодирования к обобщенной задачекоммивояжера практического значения не имеет, но представляет особеннойинтерес в рамках статистического машинного перевода.
В ходе исследований, сопутствующих работе нами был рассмотрен метод решения обобщенной задачи коммивояжера с помощью метода «муравьиной оптимизации». Врезультате, было сделано очень важное наблюдение — для ЗК не важен городс которого был начат обход графа, а для задачи декодирования важен — естьзаданный порядок слов.Метод «муравьиной оптимизации» как раз относился к таким не устойчивым методам.
Относительный порядок слов (расположение n соседних слов)29может быть установлено с помощью модели целевого языка, однако, например при циклическом сдвиге слов выходного предложения, модель языка будет бессильна.Сам по себе метод «муравьиной оптимизации» представляет из себя приближенный метод решения ЗК. Он основан на наблюдениях за поведением муравьев в природе.
Перемещаясь от одного пункта до другого, муравьиоставляют за собой тропы из феромонов Если другие муравьи находят такие тропы, они, пойдут по ним. Тем самым укрепят воздействие феромоннойтропы. Со временем феромонная тропа испаряется. Чем больше времени требуется для прохождения, тем сильнее испарится феромонная тропа. Для ЗКмуравьи сначала в случайном порядке выходят из каждого города, после заданного числа переходов отбирается путь который менее всего «испарился».В рамках задачи перевода при решении ЗК методом «муравьиной оптимизации» можно использовать на выходе циклический сдвиг полученных результатов, но в это потребует дополнительных накладных расходов, которыемогут перекрыть преимущества приближенного метода.Можно также предложить вариант метода, когда каждый полученный результат можно будет циклически сдвинуть на определенную величину и потом целиком проверить по модели языка, но в этом случае, мы получим очередной и очень экзотический вариант жадного инкрементного поиска.301.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
