Поиск среди миллиарда слов

Ничто так не настраивает на продуктивную работу, как день проведенный в совещаниях. Вот и я, после дня проведенного в бесконечных трындежах, решил сделать что-то полезное. Как только дома все уснули я решил покодить. Нашел интересный контест на Kaggle,  Billion Word imputation.

Суть задачи состоит в следующем:

Есть два файла. В первом - текст, состоящий большой кучи осмысленных предложений (на инглиш оф коз). Размер текстового файла примерно 3.86Гб и в нем находится примерно 1миллиард слов. Это тренировочный набор (training data).
Второй файл чуть поменьше (40мб). В нем из каждого предложения удалили по 1 слову.  Это тестовый набор (test data).
Задача: вставить пропущенное слово в тестовом наборе. Тексты никак друг с другом не связаны.

Как собираюсь решать

На тренировочных данных нужно построить модель, с помощью которой можно предсказать пропущенные слова в тестовом наборе. Какую модель будем строить?
Когда-то давно я прошел очень интересный курс по Natural Language Processing на Coursera от Columbia University. Основным элементом языковых моделей, которые мы рассматривали были так называемые N-Gram'ы. N-Gram - это последовательность N слов в предложении. Если N=1, то такую N-Gramm'у называют Unigram (т.к. одно слово), если 2-Bigram, 3-Trigrams и т.д.

Например, если разложить предложение "The dog likes the cat"  на N-Gramm'ы, то получится:

- Пять Unigram: The, dog, likes, the, cat

- 6 Bigram: * The, The dog, dog likes, likes the, the cat, cat _STOP_

- 6 Trigram: * * The, * The dog, The dog likes, dog likes the, likes the cat, the cat _STOP_

Здесь символ * и _STOP_ - это служебные символы, означающие начало и конец предложения.

Что можно сделать с этими N-Gramмами?

Можно посчитать вероятность, с которой встречается в тексте каждая N-Gram'ма. В простейщем случае (Unigram) вероятность слова w будет такой:

$$p(w)=\frac{count(w)}{N}$$

где N-общее количество слов в тексте, \(count(w)\) - сколько раз встречается слово w.

Например, в предложении "the dog likes the cat" \(p(the)=2/5\)

Если N > 1 (bigram, trigram и т.д.) то немного сложнее. Здесь мы должны считать условную вероятность \(p(w_n|w_{1},w_{2}...w_{n-1})\).  Это еще называют правдоподобием (likelihood). Т.е. это вероятность того, что слово  \(w_n\) встретится за словами \(w_{1} w_{2}...w_{n-2}w_{n-1}\).

В случае с биграммами мы будем "заглядывать" на одно слово назад, в случае с триграммами на 2 и т.д.
Вот как считаются вероятности для биграм
$$p(w_i|w_{i-1})=\frac{count(w_{i-1},w_i)}{count(w_{i-1})}$$
Где \(count(w_{i-1},w_i)\) - сколько раз встречаются вместе слова \(w_{i-1} w_i\), а \(count(w_{i-1})\) - частота появления слова \(w_{i-1}\)
Точно так же для триграм
$$p(w_i|w_{i-2},w_{i-1})=\frac{count(w_{i-2},w_{i-1},w_{i})}{count(w_{i-2},w_{i-1})}$$
Например, вероятность того, что likes встретится сразу за "the dog":
$$p(likes|the, dog)=\frac{count(the, dog, likes)}{count(the, dog)}$$

Как использовать расчитанные вероятности?

Допустим, что я как-то посчитал сколько раз встречается в тренировочном тексте все "the", "the dog", "the dog likes", "likes the cat", "cat _STOP_" и т.д. Как это можно использовать, чтобы найти пропущенное слово?

Поясню на примере.

Допустим, что в предложении "the dog likes the cat" удалили слово likes: "the dog likes the cat". Можно предположить, что likelihood для биграммы "dog the" будет очень маленьким, так же и для триграмм "the dog the" и "dog the cat". В идеале хотелось бы чтобы эти все 3 вероятности были бы нулевыми: 

\(p(the|dog)->{min}\)

\(p(the|the,dog)->{min}\)

\(p(cat|dog,the)->{min}\)

То есть нам надо пробежаться по предложению ("the dog the cat") и посчитать правдоподобия для всех bi-,tri-(возможно 4,5,6)-Gram в этом предложении. Если правдоподобие всех (или большинства) N-Gram минимально в одном и том же месте, то предполагаем, что в это место нужно вставить слово. 

Какое? тут уже надо искать слово, которое максимизирует правдоподобие (maximum likelihood) в заданном месте предложения. То есть если мы нашли, что слово удалили между "dog" и "the", то имеет смысл поискать что чаще всего встречалось после "the dog", "dog" и перед "the cat", "the". Это пока первоначальная гипотеза как можно найти слово, наверняка с реализацией она претерпит существенных изменений как это обычно бывает. 

Если есть мысли\предложения по поводу модели и реализации, то велкам. Про то, как я начал считать каунтеры расскажу в следующем посте. Там тоже интересно получилось :).

Ресурсы

Kaggle, Billion Word imputation contest

Курс Natural Language Processing на Coursera