Мое Online обучение

Курсы, которые я прошел

Однажды мне очень сильно повезло и у меня появилось 9 относительно спокойных месяцев, когда выходные и нерабочие вечера чаще проводишь дома и никаких дальних поездок, курортов и прочих развлечений даже не планируешь. Я решил потратить это время с максимальной пользой для себя, тем более что после этого 9-ти месячного периода жизнь кардинально изменилась и свободного времени заметно поубавилось. Но это уже другая история :).

Я решил испопробовать массовое онлайн обучение (или MOOC) что называется "по максимуму". Всего удалось пройти чуть более 10 курсов, и, после двухгодичного перерыва многое стало забываться, посему и решил немого вспомнить как это было. Сейчас пока первые пару курсов "вспомнил", потом буду докидывать еще.

Стратегия прохождения

Я записывался на несколько курсов одновременно и не очень сопротивлялся соблазну подписываться на "все и сразу". Это же нереально круто, когда преподы из самого Standford, Princeton или Berkeley выкладывают свои курсы онлайн абсолютно бесплатно, причем программа курса зачастую такая же как и для студентов именитых университетов! Естественно, что пройти "все и сразу" невозможно и после первых недели-двух я определялся стоит ли продолжать слушать курс или лучше переключиться на другие. В процессе такого "естественного отбора" я обнаружил, что моя пропускная способность - это 2, максимум 3 параллельных курса, которые я планировал пройти до конца.

Конспектирование 

Оказалось очень удобно после 3х лет пролистать конспект и вспомнить детали, просмотреть слайды и видео лекций. Кстати, на экзаменах конспект тоже иногда помогал. В качестве инструмента конспектирования и использовал XMind. В mind map я приатачивал слайды и видео лекций, иногда вставлял свои пометки. Примерно так:

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

Heterogeneous Parallel Programming

Страница курса: https://www.coursera.org/course/hetero
Университет: University of Illinois at Urbana-Champaign
Сложность: 3

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

О чем курс

Мы как-то очень привыкли к старым добрым однопоточным машинам, прототипом которых была машина Тьюринга. Тьюринговская лента (или "нить" - thread) всего одна и поэтому нет проблем с переплетениями нескольких лент во время работы. По сути первые компьютеры и были такими себе одноленточными реализациями машины Тьюринга. Потом, в процессе эволюции, возникла необходимость делить процессорное время между несколькими операторами, для чего увеличивали мощьность процессорных устройств, повышали частоту, появились RISC процессоры, конвейерная обработка команд, процессорный кеш и много-много других усовершенствований, о которых 99.99% людей, пользующихся компьютерами даже не догадываются. В общем, однопоточные процессоры делались все сильнее, быстрее, совершеннее и отлично подходят для задач, где надо выполнять действия последовательно. Но что если такой подход неэффективен для ряда задач? Что если заменить несколько "одноленточных" суперпроцессоров на несколько тысяч не таких супер, но все же реально параллельных процессоров? Какие задачи тогда можно решать быстрее?
Задача из курса.
Предположим есть очень длинная палка колбасы (несколько км длиной), за которой стоит длинная очередь в сотни (а может и тысячи) людей. Каждый человек говорит какой длины кусок ему надо отрезать.
Традиционное последовательное решение было бы таким: каждый по очереди подходит и ему отрезают кусок такой длины, какой скажет. Понятно, что для очереди длиной, например, в миллиард, мы бы занимались этим очень долго.
Можно ли сразу у всех спросить длину отрезка, нанести разметку и, имея несколько тысяч ножей, сразу разрезать так как надо?
В этом курсе мы практиковались в решении подобного рода задач с использованием GPU, узнали много нового о многопроцессорной архитектуре. Задания надо было реализовывать на C с использованием CUDA SDK. У кого не было возможности отлаживать код локально (т.к. надо GPU от NVIDIA), те могли загружать код прямо из браузерного окна редактирования и дебажить способом просмотра логов. Форум был очень активен и там часто можно было найти подсказки на решения проблем. Очень жаль, что этот курс был всего один раз и непонятно будет ли повторяться, но есть похожий курс на Udacity.

Discrete Optimization 

Страница курса: https://www.coursera.org/course/optimization

Университет: The University of Melbourne
Сложность: 4.9

Как только я посмотрел интродактори видео я понял, что будет очень интересно и не ошибся. Профессор оказался еще тем гиком. Я вот даже не поленился добавить это интродактари видео:

О чем курс

Сколько надо цветов, чтобы раскрасить карту так, чтобы соседние государства не были окрашены в одинаковый цвет? А если государств 1000 или 10000? 

По какому маршруту должна ездить фура чтобы развезти продукты по нескольким магазинам и потратить как можно меньше горючего/времени? А если магазинов 1000, а фур всего 10?

Классическая задача комивояжера - как найти оптимальное решение для 10 городов? А для 100? А для 1000? А вообще возможно ли его найти за относительно небольшое время? А если нет, то как можно максимально приблизиться к оптимальному решению?

Вот такие задачи мы учились решать в рамках курса. Оказывается есть довольно много инструментов, которые успешно применяются для задач оптимизации. Это и constraint programming и алгоритмы локального поиска (local search), и линейное программирование (linear programming), и целочисленное программирование. (integer programming)
Практические задачи были разделены на 5 уровней сложности. Для каждого уровня свой набор входных данных. Например, для задачи комивояжера для уровня 1 было до 10 городов, для 2го от 10 до 50, для 3-го от 100 до 200, 4й -500 - 1000 и для 5-го более 50тыс. Если первые пару уровней обычно можно было решить простым перебором, то начиная с 3го все становилось очень интересно. Естественно, чтобы получить сертификат нужно было решить все задачи как минимум 3го уровня сложности, а для сертификата с отличием (with distinction) - 4го и 5го.
Попробовал тулы
- SCIP optimizer http://scip.zib.de/. Простой и быстрый оптимизатор, оптимизирует задачи с помощью constraint programming и linear-integer programming. Поддерживает стандарт языка ZIMPL. Очень хорошо ломает мозг.
- GLPK solver: http://www.gnu.org/software/glpk/. Изначально я пробовал его для некоторых задач, но потом перешел на SCIP, не помню почему
- Много кодил на Java :). Задачу комивояжера, например, оптимизировал с помощью алгоритма K-opt (local search) и Simulated annealing для поиска глобального минимума.

Парадокс дней рождения

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

Задача

Допустим в компании работает 25 человек. Какая вероятность того, что у двух людей из этой компании день рождения в один и тот же день?

Интуитивное решение

Ход мыслей может быть примерно такой: 25 человек, у каждого день рождения 1 раз в 365 дней. Поскольку надо 2 совпадения, то вероятности перемножаются, и, поскольку это надо повторить для всех, то еще умножить на 25:
  \(\frac{25}{365} * \frac{25}{365} * 25\), то есть \(\frac{25}{365}\).

Правильное решение 

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

Пишу код

Для подобных экспериментов, результаты которых можно сразу же опубликовать мне очень нравится Python notebook. Его можно установить себе на компьютер, но я воспользуюсь бесплатным сервисом от https://www.wakari.io

В wakari.io создал новый файл, вставил ячейку (cell) типа Code и в ней заимпортил NumPy и вывел номер версии:

Затем создал функцию, которая создает массив размером n, каждый элемент которого случайное число от 1 до 365:

Эта функция проверяет есть ли в массиве birthdays элементы, которые повторяются больше чем 1 раз:

Запускает эксперимент несколько раз и возвращает количество успешных экспериментов (количество совпадений > 1)

Запускаю эксперимент и получаю вероятность того, что в группе из 23 человек хотя бы у двух совпадут дни рождения:

Вероятность более 50%, то есть интуитивное решение не является правильным.

Wakari.io очень прикольный сервис, он позволяет публиковать свои поделки. Этот код целиком можно глянуть тут: https://www.wakari.io/sharing/bundle/szelenin/birthdays

Ссылки на использованные материалы

- Wakari.io -  online сервис для анализа данных на Python.
- Парадокс дней рождения на википедиит
- Мой код  https://www.wakari.io/sharing/bundle/szelenin/birthdays

Softmax Regression Pylearn2

На установленном ранее pylearn2 пробую пройти туториал. Начну с softmax регрессии.
ссылка на туториал:
http://nbviewer.ipython.org/github/lisa-lab/pylearn2/blob/master/pylearn2/scripts/tutorials/softmax_regression/softmax_regression.ipynb

Пытаюсь установить ipython

В принципе туториал можно запустить локально. Надо только ipython установить:
Захожу на запущенную Vagrant виртуалку и запускаю команду

sudo pip install "ipython[all]"

Нельзя инсталить без [all]:
sudo pip install ipython
и вот почему: http://stackoverflow.com/questions/24995438/pyzmq-missing-when-running-ipython-notebook

дальше перехожу в папку с туториалом:
cd /home/vagrant/pylearn2/pylearn2/scripts/tutorials/

и запускаю ipython'овский notebook:
sudo ipython notebook

ноутбук запустился в аутентичном текстовом браузере w3m :)

Немного побаловался, но в хроме все-таки удобнее было бы работать :). Для этого надо "перебросить" порт, который внутри виртуальной машины "наружу", чтобы я мог с хост системы зайти браузером.
-Смотрю какой порт использовал ipython :

Добавляю в "forwarded_port" в Vagrant файл (сразу за config.vm.box):
  config.vm.network "forwarded_port", guest: 8888, host: 8888
И перегружаю vagrant (команда vagrant reload):

не заработало... :(

Update

Проблема решилась после того как сделал uninstall ipython (тот, который не [all])
sudo pip uninstall ipython 

и заново проинсталил ipython[all]:
sudo pip install ipython[all]

Оставлю пока ipython, делаю в отдельном файле train.py.

import os
import pylearn2
dirname = os.path.abspath('/vagrant/ml_invsetigaiton/pylearn2_softmax')
with open(os.path.join(dirname, 'sr_dataset.yaml'), 'r') as f:
    dataset = f.read()
hyper_params = {'train_stop' : 50000}
dataset = dataset % (hyper_params)
print dataset

Результат:

vagrant@vagrant-ubuntu-trusty-64:/vagrant/ml_invsetigaiton/pylearn2_softmax$ sudo python train.py
OpenBLAS : Your OS does not support AVX instructions. OpenBLAS is using Nehalem kernels as a fallback, which may give poorer performance.
!obj:pylearn2.datasets.mnist.MNIST {
        which_set: 'train',
        start: 0,
        stop: 50000
}

Что это было?

грубо говоря прочел YAML файл, в котором было описание датасета из набора MNIST. Этот набор поставляется с pylearn2. Всего в наборе 60000 записей, но я передал гиперпараметр, который обозначает, что стопнуть обучение нужно на 50000

короче, скопировал я все степы, запустил, но выдалась такая ошибка:

оказывается надо самому скачать MNIST датасет. Хорошо, что pylearn2 предоставляет для этого скрипт. в папке ~/pylearn2/pylearn2/scripts/datasets запускаю python download_mnist.py:

Запускаю опять, модель в процессе обучения печатает как хорошо она обучается:

Теперь чтобы расшифровать результаты запускаю скрипт print_monitor.py, который находится в /home/vagrant/pylearn2/pylearn2/scripts и передаю ему сгенерированный файл с моделью:

Процент неправильно классифирированых записей из тестового набора 7.68 (test_y_misclass: 0.0768)

Ставлю IntelliJ Idea + Oracle JDK на Ubuntu в Vagrant (VirtualBox)

Изучаю Pylearn2 в Идее

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

Ставлю графическую оболочку xfce4.

Загуглил и пошел инсталлить по первой же ссылке:
http://stackoverflow.com/questions/18878117/using-vagrant-to-run-virtual-machines-with-desktop-environment

Выполнил все инструкции, перезапустил виртуалку (vagrant reload). В появившемся окне VirtualBox'a залогинился как vagrant/vagrant.

Ставлю Oracle JDK 8

Опять же загуглил и нашел чудовую пошаговую инструкцию как инсталлить ораковую ждк на убунту (14.10)

http://www.wikihow.com/Install-Oracle-Java-JDK-on-Ubuntu-Linux

По шагам все сделал почти по инструкции за исключением путей

Перезапускаю

Ставлю идею

http://tutorialforlinux.com/2013/02/24/linux-debian-wheezy-xfce-howto-install-gettingstarted-latest-intellij-idea-community-edition/

Тоже по инструкции.

Из UXTerm (можно и из XTerm) набираю idea <Enter>: 

Вау, красота то какая!

Все, теперь ставлю Python plugin и дальше буду работать в нормальной IDE :)

Установка Pylearn2 с помощью Vagrant и puppet

Добрался я наконец-то до компа, но не так чтобы для работы, а подтянуть свои практические знания по Machine learning на python. В последнее время в тренде всякие диплернинги (http://deeplearning.net), особенный пинок в этом направлении дала возможность обучения нейронных сетей с использованием GPU, что на порядки увеличивает процесс обучения.

Далее я буду пытаться утановить Pylearn2 со встроенной поддержкой Theano. Забегая вперед скажу, что сначала я описываю процесс наступления на грабли, а в конце привел исправленный процесс. Так что нетерпеливым можно сразу туда :).

Итак, начнем.

Я взял инструкцию по установке Pylearn2 отсюда: http://deeplearning.net/software/pylearn2/

1. Устанавливаю Vagrant

Актуальная версия 1.7.2
https://www.vagrantup.com/downloads.html
скачал, перезапустил комп

2. Устанавливаю VirtualBox

https://www.virtualbox.org/wiki/Downloads
и VirtualBox Extension Pack (там же)

3. Устанавливаю pylearn2 из образа

клонирую репозиторий с настройками Vagrant
git clone git@github.com:ironchief/pylearn2_vagrant.git
и в папке pylearn2_vagrant стартую Vagrant:
vagrant up

Скачивание образа застопорилось на 12%, поэтому я скачал образ вручую. В файле Vagrant указан url на образ:
config.vm.box_url = "http://files.vagrantup.com/precise64.box"

эту строку я заменил на:

config.vm.box_url = "C:/workspace/bin/images/precise64.box"

Опять запустил vagrant up

Упало с непонятной ошибкой. 

Следую рекоментациям открыть машину в GUI. Переключаюсь в VirtualBox, где появилась новая машина и пытаюсь ее стартовать:

Включаю виртуализацию в биосе, и опять запускаю vagrant up:

puppet долго конфигурирует систему...
и в результате выдал маловразумительную ошибку :(

понять что произошло помог лог файл pip.log, который лежит в папке pylearn2_vagrant. Там вот такая ошибка:
numpy.distutils.system_info.NotFoundError: no lapack/blas resources found

Гугл в помощь, на stackOverflow нашел интересный пост: http://stackoverflow.com/questions/7496547/does-python-scipy-need-blas

В puppet манифест (pylearn2_vagrant/manifest/default.pp) в раздел package добавил liblapack-dev :

и опять запустил vagrant с командой provision :
vagrant provision
опять долго инсталлируется ...

День 2

На следующий день я решил начать все сначала. Но перед экспериментами я форкнул себе репозиторий https://github.com/ironchief/pylearn2_vagrant, склонировал уже свой репозиторий (https://github.com/szelenin/pylearn2_vagrant) в новую папку и в Vagrant файле поставил версию последней убунты:
config.vm.box = "ubuntu/trusty64"

и запустил команду vagrant up из новой папки pylearn2_vagrant:

и о чудо! все проинсталлилось с первого раза!

Финальная версия

Итого чтобы поставить pylearn2 (в моем случае на винду) надо

1. Установить Vagrant

актуальная версия 1.7.2
https://www.vagrantup.com/downloads.html

2. Установить VirtualBox

https://www.virtualbox.org/wiki/Downloads
и VirtualBox Extension Pack (там же)

3. Склонировать форкнутый репозиторий 

Пулреквест отошлю чуть позднее

git clone git@github.com:szelenin/pylearn2_vagrant.git

4. Запустить Vagrant

Переходим в папку pylearn2_vagrant и запускаем команду (желательно из вменяемой консоли, я делал это из git bash)

vagrant up

* Возможно прийдется включить поддержку виртуализации в BIOS.

5. Enjoy

Дальше можно приконектиться по ssh (я использую XShell) порт 2222, пользователь vagrant/vagrant

Используемые материалы

1. Vagrant: https://www.vagrantup.com/downloads.html

2. VirtualBox: https://www.virtualbox.org/wiki/Downloads

3. Puppet провижнер для Vagrant и сам Vagrant файл: https://github.com/ironchief/pylearn2_vagrant 

4. Мои дополнения для последней версии ubuntu: https://github.com/szelenin/pylearn2_vagrant

Поиск среди миллиарда слов. Считаем количество N-Gram.

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

Оцениваем сложность по пямяти

Для начала надо было придумать как посчитать сколько раз встречаютсы все эти "the", "the cat", "the cat likes" и т.д. Уникальных слов будет много, а уникальных bi-,tri-, и.т.д -gramm будет еще больше. Для каждой n-gramm'ы нужно хранить сколько раз она встречается в тексте. Чтобы примерно оценить масштаб проблемы я предварительно спросил у гугла "сколько слов в английском языке?"
Гугл говорит, что более 1млн:

Если считать только количество unigram (уникальных слов), то это не проблема хранить 1млн счетчиков в памяти, но как только понядобятся 2-,3-..грамы, то требования к памяти совсем другие. Для bigram в худшем случае понадобится хранить \(1млн^2\) каунтеров, для trigram \(1млн^3\) и т.д.
Хотелось бы обойтись без всяких DB/NoSQL и прочих Hadoop'ов, поскольку это сильно утяжелит решение. Я начну с чего-то простого, но достаточно эффективного по памяти.

Структура данных Trie

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

Поясню на примере.
Возьмем предложения "The dog likes the cat" и "the cat hates the dog".
Вот как будет выглядеть Trie после того, как посчитаю количество биграм для этих 2х предложений:

По дереву легко можно найти, например, что слово "the" встречается 4 раза, а "the dog" - 1 раз. Слово "dog" - 2 раза, а "dog likes" - 1 и т.д. При увеличении "N-грамности" дерево будет содержать новые уровни. Количество уровней в trie будет равно числу N в N-Gram'е (рутовую ноду я не считаю). 

Пишу код

Сам код здесь не буду постить, для этого есть гитхаб:https://github.com/szelenin/kaggle/tree/master/billion-word-imputation. Укажу лишь, что но начал я с такого теста:

А закончил таким:

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

Пробный пуск

Для начала я запустил подсчет уникальных слов, чтобы получить общую статистику по тренировочному файлу. Вот что выдала после 2х с небольшим минут.

Lines read: 30301028. Unique words: 1026207, total words: 693467918

Количество уникальных слов практически такое же как выдал гугл. Так что, думаю, все возможные слова, которые есть в английском языке присутствуют :)

1й запуск для подсчета триграм

Я особенно не расчитывал, что моя считалка посчитает количество всех возможных триграм в тексте, просто интересно через сколько времени закончится память :). Память закончилась практически сразу и JVM вывалился с жуткой ошибкой:

# A fatal error has been detected by the Java Runtime Environment:

#

#  EXCEPTION_ACCESS_VIOLATION (0xc0000005) at pc=0x000000006f533c0b, pid=4768, tid=6776

#

# JRE version: Java(TM) SE Runtime Environment (8.0_20-b26) (build 1.8.0_20-b26)

2й запуск

На второй запуск я выделил 12Гб под JVM и запустил jvisualvm чтобы посмотреть как кушается память. Проработала программка 4минуты и вывалилась с такой же ошибкой. Но все таки успела  прочитать 3.6 млн строк, в которых было 83.5 млн слов, из которых почти 400 тыс уникальных, что в общем-то неплохо для 4х минут работы :) :

Lines read: 3648300. Unique words: 398484, total words: 83500620

Вот как заполнялась память

 А вот какие обьекты наиболее активно ее наполняли:

Глядя на количество инстансов HashMap я решил немного сэкономить и чуть оптимизировать код. Дело в том, что в каждой ноде я по умолчанию создавал мапу для ее детей:

Но для последнего уровня дерева детей не предполагается, поэтому можно мапу не создавать.

3й запуск

Сделал создание мапы с детьми lazy и запустил еще раз. На этот раз работало 30 минут, после чего я убил процесс, т.к. дожидаться правильного OutOfMemory совсем не хотелось. Перед смертью считалка отчиталась, что прочитала 7.1 млн предложений из 16.2млн слов, из которых 541тыс уникальных.

Lines read: 7119000. Unique words: 541538, total words: 162929078

Вот график поедания памяти

 А вот ее содержимое

Выводы

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

PS

Как говорится "быстро сказка сказывается, но не быстро дело делается". На следующий день я бодренько поправил код, который разбивает тренировочный набор на 10 частей, считает каунтеры и сохраняет расчитанные значения в файле. Запустил прогу и через 30 минут она вывалилась с таким же ACCESS VIOLATION как и в 1й раз. Вот так съедалась память во время работы:

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

Ради эксперимента я сказал JVM использовать Garbage Collector GC1 (-XX:+UseG1GC) и запустил считалку опять. На этот раз она упала при сериализации модели, так что я поменял стандартную Java сериализацию на kryo и запустил еще раз. В этот раз все прошло как и ожидалось:

График показывает, что GC корректно убивает ненужные объекты. Тогда почему это не работало раньше, с Garbage collector'ом, по умолчанию? 

По умолчанию применяется Concurrent Mark&Sweep GC, который разделяет объекты на "короткоживущие" и "долгоживущие". Область короткоживущих чистится часто, а долгоживущие чистятся гораздо реже. Если JVM положил объект в "долгоживущую" область, то потом его оттуда сложно будет вытащить. По крайней мере в моем случае похоже, что все попытки почистить долгоживущую область заканчивались крашем JVM. GC1 разделяет весь хип на блоки размером от 1 до 32мб. Каждый блок может быть "короткоживущим" или "долгоживущим". Если в блоке все объекты уже не используются, то блок освобождается целиком. Подробнее про устройство GC1 можно посмотреть здесь.

Ресурсы

1. Мой код на гитхабе https://github.com/szelenin/kaggle/tree/master/billion-word-imputation

2. Описание с структуры Trie на википедии: http://en.wikipedia.org/wiki/Trie

3. Описание Trie с примерами : http://www.toptal.com/java/the-trie-a-neglected-data-structure

4. Как устроен GC1 : http://www.infoq.com/articles/G1-One-Garbage-Collector-To-Rule-Them-All
5. Kryo serialization framework : https://github.com/EsotericSoftware/kryo

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

Ничто так не настраивает на продуктивную работу, как день проведенный в совещаниях. Вот и я, после дня проведенного в бесконечных трындежах, решил сделать что-то полезное. Как только дома все уснули я решил покодить. Нашел интересный контест на 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