Category: лингвистика

Category was added automatically. Read all entries about "лингвистика".

любопытно

dataset для машин, понимающих русский язык

Запись будет интересна (тм) разработчикам чего-нибудь искусственно-интеллектуального или тексто-распознавательного.

В комментариях к предыдущему посту мы выяснили, что востребованы какие-нибудь данные на тему "корректных" и "некорректных" высказываний в естественных языках. Быстро я такой dataset не нашел, поэтому пришлось сделать самому. А раз уж так, решил сделать для русского языка; таких то ли немного, то ли совсем нет.

Итак, черновая-ознакомительная версия dataset'а для проверки разных техник natural language acquisition. Скачивать отсюда: result.zip.
Collapse )
любопытно

Зачем в Яндексе перемножать разреженные матрицы

Например, для того, чтобы автоматически искать синонимы.

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

Итак, представим, что у нас есть гигантский набор текстов, написанных на одном и том же языке (корпус), и нам нужно, используя только этот корпус, автоматически составить список троек (А, Б, f): "слово А означает то же самое, что и слово Б, и мы в этом уверены на f процентов". Зачем поисковику может понадобиться такой список, думаю, рассказывать не обязательно.

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

Нет, не проще, поскольку объем итогового словаря совершенно гигантский, а вот кластер под говорящим названием SDF построит его за полчаса. Даже с учетом затрат на программиста и программирование выигрыш все равно огромен. К тому же, что интереснее, русских языков много. Язык, которым люди пишут запросы, очень отличается от языка, которым они пишут тексты web-страниц, и оба они отличаются от литературного русского имени Розенталя. Синонимия в них тоже разная; например, в языке запросов слова "секс" и "порно" - практически полные синонимы (что несколько подрывает мою веру в человечество); ни в каком другом русском языке эти слова синонимами не являются (кроме, возможно, языка спамерских ссылок, но я не проверял). Другой пример отличий: в сообщениях на форумах и в комментариях в ЖЖ слово "км" является главной формой слова "километр", а не наоборот, как в литературном русском. Сделать "один на все случаи жизни" словарь можно, но это было бы неверно. Мало того, все эти языки меняются, и куда быстрее, чем русский классический. Превед медвед, мистер Блейн; слова "президент" и "Путин" уже куда меньшие синонимы, чем три года назад.

Очень хорошо, как же господа лингвисты учат нас искать синонимы? Для этого нужно по всему корпусу составить список слов, и для каждого из них список слов-соседей с указанием того, насколько часто это слово бывает его соседом. "Соседей" можно определять по-разному, как это лучше делать - предмет holy war'ов. Так или иначе, получится что-то вроде такого: сосед расположен не дальше двух слов влево или одного вправо, не отделен знаком препинания, и не является слишком частотным словом вроде "и" (стоп-словом), или слишком низкочастотным (выдуманным, именем собственным или опечаткой).

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

Когда слова А и Б - синонимы? Не тогда, когда число соседства большое (даже если его нормировать по частоте встречаемости слов по отдельности). Такое всего лишь свидетельствует о том, что А часто стоит рядом с Б ("кофе" - "растворимый", "обжарить" - "лук", "бабы" - "дуры" и тп).

На самом деле А и Б синонимы, если их строки похожи с точностью до множителя. То есть это два N-мерных вектора, угол между которыми должен быть близок к нулю. Или, что то же самое, косинус этого угла должен быть близок к единице. А косинус - это скалярное произведение, деленное на длины этих векторов.

Пусть слов всего у нас N, разных соседей тоже примерно N (чуть меньше, т.к. некоторые слова мы исключили, но не намного). В каждой строке в среднем не так уж много ненулевых чисел (у слова "параллелограмм" гораздо меньше соседей, чем слов русского языка вообще). Обозначим это среднее число соседей M. Все длины всех векторов мы вычислим примерно за N*M действий, а вот вычисление всех скалярных произведений - уже очень вычислительно затратное действие, и занимает примерно N*N*M действий.

Вот тут на помощь и приходят сотни компьютеров и всякие sexy методики распараллеливания вроде MapReduce.

Что еще можно добавить?
1) Круто работать в месте, где можно решать подобные задачи в качестве рутинной основной работы
2) Все это можно было бы придумать "из головы", но существуют и некоторые "магические константы", которые без опыта узнать просто неоткуда. Например: какого минимального размера должен быть корпус? Что такое "низкочастотное" и "высокочастотное" слова - каков конкретный порог? Что лучше - приводить слово-соседа к главной форме или оставлять как есть, и как это повлияет на требуемый размер корпуса?

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

Лингвистика: трансформации как часть грамматики

Пытаюсь продираться сквозь матлингвистику (в изложении Хомского и Миллера). Похоже, что не зря. Прочел пока только формальную постановку задач, но уже узнал кое-какие интересные вещи. Если сравнить с подходом, принятым к языкам программирования, можно прийти к нетривиальным идеям.

Попробую пересказать своими словами отличия подхода лингвистов от принятого в computer science. К сожалению, у меня нет ни фундаментального CS-образования (о чем периодически сильно жалею), ни лингвистического, так что если где-то ошибусь в терминологии - поправьте, пожалуйста.

Итак, описание любого языка программирования (а в более широкой постановке - любого machine-readable языка) принято разделять на две части: грамматику и семантику. Грамматика - гораздо более строгая и формализуемая часть описания. Грамматика языка определяет способ узнать, является ли заданная последовательность символов программой (в более общем случае - "высказыванием") на данном языке, и если да, то какова структура этого высказывания. Например, грамматика С++ позволяет определить, что такой-то набор символов - на самом деле декларация класса, имеющего такие-то поля и такие-то методы, каждый из которых принимает такие-то аргументы.

В матлингвистике (в отличие от уроков русского языка) словом "грамматика" тоже называют именно это понятие, а не набор правил, по которым в тексте расставляются запятые.

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

Семантика языка - вещь, очень плохо формализуемая (вряд ли существует способ описать в единых терминах семантику, скажем, SQL, UnrealScript и C++), а грамматика, наоборот, формализуется очень хорошо. Есть множество способов описывать те или иные грамматики. Наиболее часто встречающиеся, afaik - BNF и EBNF. Существует большое количество "компиляторов компиляторов", по описанию грамматики генерирующих интерпретаторы или "почти компиляторы" данного языка (этот процесс обычно разбит на несколько стадий). К таким инструментам относятся, например, flex и bison. Я не буду дальше вдаваться в подробности, потому что многие это все и так знают, а тем, кто не знает, google и wikipedia в помощь.

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

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

Грамматика "канонических" предложений очень хорошо описывается при помощи BNF. Остальные предложения получаются из "канонических" набором трансформаций. Трансформация может поменять порядок слов, возможно, какие-то убрать, какие-то добавить. Трансформация может изменить смысл предложения, а может не менять (то есть, трансформация - не только грамматическое понятие, но и семантическое тоже). Некоторые трансформации в некоторых ситуациях могут быть "частично допустимыми" в том смысле, что получившееся предложение будет не очень верным с точки зрения данного языка, но все же вполне понятным.

Осмысленность такого взгляда на грамматику языка состоит в том, что число допустимых трансформаций невелико, и грамматика "канонических" предложений тоже проста (и то и другое - только по сравнению с богатством реального языка, конечно; на самом деле это "невелико" велико, и "просто" совсем не просто). Если бы лингвисты пытались выписать полную BNF для, скажем, русского языка, они могли бы заниматься этим бесконечно долго (к тому же, была бы потеряна возможность описывать "частично допустимые" предложения; но в контексте языков программирования это не очень интересно).

За всем этим просматриваются интересные вопросы: почему, собственно, все естественные языки так устроены? Есть ли у человека "аппаратный" модуль понимания именно таких языков? Насколько понял, как минимум упомянутые авторы считают, что есть. (Мое воображение отказывает при попытке придумать, как такой модуль мог появиться эволюционным путем - но это тема для отдельной беседы).

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

Некоторые примеры таких конструкций есть уже сейчас, скажем, в Python и Boo. Например, в Boo (а также в Ruby и Perl) можно вместо

if condition:
    statement

написать

statement if condition
 
Это трансформация в чистом виде.

Подозреваю, в таком стиле намного проще имплементить различного рода приятный синтаксический сахар вроде optional и named method arguments в Python. Но это так, развлечения; если применить идеи планомерно (например, вместо синтаксических макросов a la Nemerle/Boo дать возможность пользователям определять свои трансформации), думаю, результаты могут быть куда как интереснее.