Алексей Байтин: Поиск и машинный перевод

Доклад Алексея Байтина, руководителя сервиса Яндекс.Перевод, посвященный машинному переводу и поиску, был представлен на конференции «Российские интернет-технологии 2011», которая прошла в Москве 25-26 апреля .

В самом начале своего выступления докладчик сообщил, что где-то в 2008 году он уже докладывал на конференции о запуске сервиса исправления опечаток поисковой системой Яндекс. Это уже стало определенного рода традицией, что выпуская какой-то сервис, команда Яндекса докладывает на конференции о его запуске.

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

Почему вообще машинный перевод и поиск оказались связанными? Часто задают вопрос: «А как вообще люди зарабатывают машинным переводом?». Достаточно взглянуть на дневную статистику Яндекса, и все сразу становится понятно. Десять миллионов запросов в день задаются на английском языке, среди показанных документов – около 30 миллионов документов на английском, поэтому очень часто люди в поиске набирают запросы, связанные с переводом.

Алексей предложил слушателям заглянуть просто в поисковые подсказки, где можно увидеть, что переводчик онлайн на букву «П» стоит на первом месте, обгоняя даже погоду. Понятно, что у пользовательской аудитории есть некий интерес к переводу вообще. Докладчик не стал демонстрировать статистику по онлайн- переводчику с русского на английский, или с русского на итальянский, потому что и без этого всем ясно, что основная масса – это англо-русские переводы.

Яндексу только оставалось решить, что и как начать переводить. Выбор, как переводить — очень простой, либо с использованием синтаксических правил, либо статистического машинного перевода. Яндекс сделал свой выбор в пользу статистического машинного перевода.

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

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

Задача идеального перевода — практические не решаема, Яндекс отдает себе в этом отчет, и заранее готов к тому, что его перевод будет содержать изрядное количество комических дефектов и до литературного перевода, может быть, не дотянет никогда.

Далее Алексей наглядно продемонстрировал слушателям трудности перевода на примере разбора нескольких предложений.

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

Больше всего смешных моментов, связаннj с идиомами, потому что переводить их дословно нет никакого смысла. Люди могут понять совершенно не то, что им хотят сказать. Например: «Трава не расти, если привезти». Что можно подумать об этой фразе носителю другого языка? В лучшем случае, что истинный смысл фразы очень сильно искажен, а в худшем могут подумать, что вы наркоман какой-то.

Алексей высказал благодарность ученым, которые за последние 20 лет осуществили большой прорыв в области машинного перевода, разработав практически цельные, математические модели дословного и фразового перевода. Фактически, Яндексу оставалось только сесть и сделать. В компании есть такая группа, которая занимается машинным переводом уже лет восемь. Это направление очень активно развивается, проводятся семинары, конференции и так далее, но далеко не все так просто.

Основными тезисами в машинном переводе является вероятностная модель и попытка всеми возможными способами разбить задачу на ряд мелких и уже более решаемых задач. Есть задача – английское предложение. Нужно найти его наиболее вероятный русский перевод. Решение обычно классическое. Используется модель канала, — мы получаем вместо одной вероятности перевода английского предложения в русское уже две вероятности. Одна, грубо говоря, условная модель перевода и другая – известная модель языка. То есть, задача разбита уже на две.

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

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

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

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

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

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

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

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

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

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

Где вообще можно взять все эти материалы? Можно из книжек, сайтов. Яндекс – крупнейший поисковик, проиндексировавший много документов, естественно и вполне логично было решить, что если начать разбирать все документы в индексе, то можно найти достаточное количество документов, из которых можно вытянуть модель перевода.

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

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

К примеру, есть три предложения английских и три соответствующих им предложения на русском языке. Всего четыре слова в предложении. Необходимо найти какой-то способ, который сопоставил бы английское слово с русским. Такие задачи обычно решаются интерактивным методом, поскольку тут есть скрытые переменные. Здесь используется метод, который называется exception optimization. Работает он очень устойчиво, надежно. Модели оптимизируются, условно равномерным распределением, чтобы слово перевелось на другое. Дальше происходит расчет весов. Расчет производится до тех пор, пока качество не устраивает. Буквально вот эта комбинация сходится на шестидесятой операции, и мы получаем точный перевод. Вот, собственно, так и была обучена первая модель для машинного перевода. Теперь только надо понимать, что в предложениях будет не три слова и не четыре, а в миллионы раз больше.

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

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

Здесь есть интересная, неожиданная штука. Она заключается в том, что выравнивать можно по длине предложения. Не нужно никаких словарей. Первый проход, который дает для хороших, выровненных страниц документа очень хорошую полноту, почти 90%, на таком совершенно простом риторическом программировании. Если необходимо увеличить полноту выравнивания, то делается еще один проход. После первого прохода, по удачно выровненным парам, составляются слова, а на втором этапе уже осуществляется проход с учетом лексической вероятности. При этих условиях удается увеличить полноту на 5%. 5% кажется ерундой, но если вы поймете, что речь идет о миллионах предложений, то, наверное, стоит побороться.

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

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

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

Что делать с обнаруженными документами? Сравнивать. Самый ломовой способ – это перевести все английские документы на русский язык, а потом просто сравнить. Что делает Яндекс.Перевод? Берет таблицу переводов, которая получилась на первой итерации, и строит слова. В результате перевода получаются смешные фразы. «Осень» может перевестись, как «ликер». Это происходит в результате замыкания двух документов, где один про осень, а второй про ликер. Вот чего можно добиться таким способом. Есть и другие курьезные пересечения. От комнаты можно перейти к космосу и так далее.

Алексей Байтин: Что с этим делается? Методом выделения связанных компонент делается искривизация. Вот этот словарь просто оптимизируется в размеры кластера. То есть мы хотим, чтобы не было каких-то больших кластеров, в которые попала комната вместе с космосом. И просто варьируя минимальным коэффициентом связанности, мы пытаемся лишние слабые звенья разрулить. За счет таких методов нам удается собрать словарь в двенадцать тысяч классов с хорошей полнотой и точностью. Это один из самых интересных промежуточных результатов работы по всему построителю машинного перевода.

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

Задача состоит не в том, чтобы эти два предложения дальше использовать. На этом этапе просто надо зацепиться за документ. Есть вероятность, что остальные предложения будут лучше ему соответствовать. Поэтому главная задача — поймать просто какие-то предложения, которые друг с другом связаны. То есть, сравнить все русские документы со всеми английскими. Если нарисовать матрицу, то она получится очень большой. Очевидно, что эта задача неподъемна, даже при использовании Яндекс ресурса.

Что делается? Используется метод, состоящий из цепочки совпадающих слов, в данном случае — признаков. И в каждом предложении, тексте, эти цепочки признаков объединяются.

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

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

Зал: — Вопрос касается алгоритма. Используете ли вы семантическую связь или используете ли вы синонимию при переводе?

— Нет. Ничего не используем.

Зал: — Какой примерно объем документов должна получить система, чтобы начать нормально переводить?

— У нас был объем от сотен тысяч документов до нескольких миллионов.

Зал: — А вы можете сделать персональный инструмент для переводчика, объединив со словарями, который выдавал бы еще обратную связь?

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

Зал: — Если бы вы могли привлечь колоссальные человеческие ресурсы при русской разметке текста или оценки перевода, это бы сильно помогло?

— Я, честно говоря, не думаю. Может быть, когда-нибудь это и придет. Люди будут улучшать машинный перевод. Можно высадить миллион человек, и они будут совершенствовать перевод, но большие усилия математиков или установка еще одной тысячи машин, скорее всего, не повлияет на результат. У нас сейчас есть аналитики, которые оценивают качество.

Зал: — Я переписываюсь сейчас на немецком и французском языках. Немецкого я совершенно не знаю, и приходится пользоваться подобного рода переводом. Когда пытаешься перевести с одного языка на другой язык фразу, чтобы потом использовать ее в письме, одно слово меняешь в предложении, и уже полпредложения может перевести по-другому. Потому что программа смотрит статистику вот этих кусочков и получается совершенно другая картина. Если бы можно было по-разному заменять исходное предложение, заменять синонимы, применять другие глаголы, но чтобы целый смысл оставался, и я бы видел, что перевод стал лучше после этого изменения, я бы его с большей готовностью перенес в письмо. А сейчас разницы никакой нет, проверять приходиться в Яндексе и Google на чистоту вот этого предложения, говорят ли так.

— Я об этом говорил, что есть специальный инструмент для построения переводов. Конечно, можно все это сделать. Ничего нас не останавливает. К этому надо двигаться, но сказать, что завтра будет этот инструмент, который позволит вам на незнакомом языке освоить честный, красивый перевод – это иллюзия.

Журналист, новостной редактор, работает на сайте с 2009 года. Специализация: интернет-маркетинг, SEO, поисковые системы, обзоры профильных мероприятий, отраслевые новости рунета. Языки: румынский, испанский. Кредо: Арфы нет, возьмите бубен.