Поиск среди миллиарда слов. Считаем количество 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

Бомбим недругов с помощью A* search

Примерно год назад я прошел интересный онлайн курс от университета Berkley по основам искуственного интеллекта. Курс так и называется Artificial Intelligence (код CS188.1x). Было весело, лектор много юморил и в шутливой форме доходчиво объяснил много полезных алгоритмов и подходов к решению задач ИИ. В качестве лабораторных надо было написать бота для старой доброй игры Pacman, что было очень забавно.
Одним из первых базовых алгоритмов мы рассматривали A* search. Его я и применю в реализации бота для нашей игрушки bomberman. Кстати, программу, которая управляет персонажем игры правильнее называть агентом, а не ботом ;)

Вкратце что из себя представляет A* search.

Поиск А* - это алгоритм нахождения оптимального пути в графе. Хорошо подходит для поиска оптимального маршрута из пункта А в пункт Б. Я воспользуюсь известным примером "путешествие по Румынии" (tour by Romania), чтобы в 2х словах пояснить как это работает.

Задача. Нам нужно на йти кратчайший маршрут из города Арад (Arad) в Бухарест (Bucharest). Можно перебрать все варианты, но в случае большой карты это займет много времени.

Для реализации поиска с помощью A*, нам понадобится расчитать две величины для каждого пункта:

1. Эвристика. Расстояние от текущего города до Бухареста по прямой. На карте это расстояние не указано, оно есть в полной версии здесь.

2. Стоимость. Реальный пройденный километраж. Он обозначен на карте числами между пунктами.

Алгоритм

1. Берем все соседние с Арадом пункты (Zerind, Sibiu,Timisoara). Эти пункты называются successors.

2. Вычисляем эвристику для каждого пункта. Допустим для Zerind значение эвристики равно 374, для Sibiu 253, для Timisoara 329.

3. Складываем значение эвристики со стоимостью и помещаем successor в сортированную коллекцию. Эта сортированная коллекция в A* имеет название "фринж" (fringe). Т.е. соседние с Арадом пункты разместятся во фринже в таком порядке : Sibiu (253 + 140 = 393), Timisoara (329 + 118 = 447), Zerind (374 + 75 = 449).

4. Берем из фринжа первый пункт (Sibiu) и повторяем все, начиная с п.1 до тех пор пока мы не достигнем Бухареста или фринж не опустеет. Состояние "мы в Бухаресте" есть наша цель или по научному "goal state".

Здесь можно посмотреть пошаговое вычисление маршрута в задаче "tour by Romania": http://bit.ly/1hy3ezD

Важные свойства эвристики

1. Эвристика должна быть "допустимой" (admissible). 

\(\forall N, h(N) \leq C(N)\) 

где 

\( h(N) \) - значение эвристики в пункте n

\( C(N) \) - реальная стоимость из пункта n в goal state

2. Эвристика должна быть консистентной (consistent)

\( h(N) \leq C(N,P) + h(P) \) и \( h(G) = 0 \)

где 

\( h \) консистентная эвристика 

\( N \) любой пункт в графе 

\( P \) пункт, предидущий N 

\( C(N,P) \) стоимость перехода из пункта P в пункт N 

Реализация агента

Перед тем как сесть ваять код нужно ответить на несколько вопросов

- какие пункты считать "соседними" (successors) ?

- что будет нашей целью поиска (goal state) ?

- какую эвристику использовать ?

- как расчитывать стоимость передвижения?

Определяем соседей (successors)

Бомбермен может двигаться и ставить бомбы. Он так же может пропустить ход. 

Successor - это состояние игрового поля после того, как бомбермен сделает одно движение или поставит бомбу (или же пропустит ход). Так же нужно учитывать, что бомба взрывается через 5 секунд и ее осколки разлетаются в радиусе 3х шагов. 

Для состояния доски я создал класс GameState (ссылка на репозиторий). GameState может вернуть список доступных действий для бомбермена (метод getLegalActions) и вернуть новое состояние после того, как пойдет бомбермен (метод generateSuccessor(Action action))

Каким будет Goal state?

Поскольку A* - это алгоритм поиска, то надо определить что мы ищем. Я буду искать маршрут, где конечный пункт - забомбленый чертик (мы его зовем chopper).

Какую эвристику использовать?

Если я хочу забомбить ближайшего ко мне чертика, то в качестве эвристики для простоты можно использовать manhattan distance от бомбера к ближайшему чертику. Здесь, правда, пришлось немного пошаманить, т.к. после того, как бомбермен поставил бомбу пришлось быстро от нее убегать. Код эвристики реализовал в классе NearestChopperToBombHeuristic 

Как расчитывать стоимость передвижения?

Вообще расчет стоимости в данном случае - это задача не совсем тривиальная, т.к. необходимо учесть несколько параметров:

- "стоимость" установки бомбы. Т.е. должно быть выгоднее ставить бомбу ближе к чоперу

- передвижение бомбера (чтобы как минимум соответствовать эвристике)

- опасность быть убитым осколками

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

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

Что получилось

Нагляднее всего продемонстрируют картинки. Вот пара вариантов расчета из песочницы:

Для начала неплохо, но можно еще тюнить, подбирать коэффициенты и вводить новые параметры в функцию стоимости. Но налицо несколько ограничений:

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

- Алгоритм не смотрит дальше Goal state. В случае бесконечной игры вариант "убить чертика, а там хоть трава не расти" часто заканчивается тем, что бомбермена съедают как только он поставил бомбу под чопером

- сложная функция стоимости. Как я уже указывал, в стоимость приходится закладывать множество параметров и искать баланс приоритетов между ними.

Ресурсы

1. Онлайн курс университета Беркли по ИИ Artificial Intelligence (код CS188.1x)

2. Пример "Tour by Romania" в формате PowerPoint можно скачать здесь. 

3. Тот же пример в формате PDF можно скачать здесь

4. Мой гитхаб репозиторий с исходниками (еще будет меняться:)) https://github.com/szelenin/bomberman

5. Онлайн игра bomberman на нашем игровом портале Codenjoy

Прикольный фреймворк для тестов Spock.

Недавно на проекте заюзали spock для юнит тестов. Ему, оказывается, уже много лет (целых 4 года!), а я узнал о нем только сейчас. Так обидно стало за бесцельно прожитые годы рядом с морально устаревшим JUnit'ом :).

Кто такой Спок?

Спок - коммандер и научный сотрудник звездолета "Энтерпрайз", родился в 2230 году по земному летоисчислению. Наполовину землянин, наполовину вулканец. Увлечение компютерами привело его в звездный флот, где он и сделал свою карьеру научного сотрудника.
Кому не хватило терпения посмотреть сериал, на википедии есть краткая биография Спока.
Не знаю, что сподвигло разработчиков назвать фреймворк для тестирования именем персонажа из Стартрека. Может двойственная натура героя (spock хорошо подходит как для тестирования Java так и Groovy кода), а может что еще.

Парадокс Монти Холла

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

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

Есть 3 двери. За одной из них - автомобиль, за другими - ничего (в оригинале там козел, но про козлов и так в последнее время слишком много пишут ;)). Ты выбираешь дверь. Затем ведущий открывает одну из оставщихся дверей, за которой козел пусто. Ты можешь поменять свой выбор или остаться со своей дверью.

Вопрос

Стоит ли менять дверь и какая вероятность выиграша в каждом варианте?
Здесь я предлагаю подумать и предложить свой вариант. Как обычно в конце - правильный ответ ;)

Решение

Решить эту задачку, написав программу предлагают на гарвардском курсе по Data Science. Также очень понятное логическое объяснение дано в википедии.  Я же воспользуюсь тем, что гарвард не обязывает подписывать соглашение о неразглашении для своих архивных онлайн курсов и расскажу как я решал эту задачку.
Внимание. Если ты решился пройти курс cs109, то лучше сделай это сам, без моих подсказок :).

Решать задачку предлагается на Python с расширениями для работы с массивами и прочими математическими штуками numpy. Numpy, а также масса других полезностей для дата анализа на питоне уже содержится в инсталлере Anaconda. Установка анаконды тривиальная, детали опустим.

Блокнот

Блокнот - обалденная штука в ipython. После установки anaconda просто запускаем команду:

ipython notebook

И в окне браузера нажимаем New Notebook:

Notebook - это что-то вроде вики, в которую можно вставлять код на питоне. Причем результаты будут отображаться тут же на странице. Код вместе с разметкой автоматически записывается в файл (в данном случае Untitled0.ipynb)



Импортирую модуль Numpy и вывожу его версию:


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


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


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


Функция switch_guesses позволяет менять выбор двери


Дальше функция win_percentage - подсчет процента угадываний


И, наконец, запускаю эксперимент 10тыс раз и выводим результат:

Вывод

Полностью совпадает с теорией. Если менять решение, то вероятность выиграша 66.6%. Подробнее о теории можно почитать в википедии

Ресурсы

1. Гарвардский курс Data Science
2. Парадокс Монти Холла в википедии
3. Анаконда
4. Код здесь: https://github.com/szelenin/cs109

Выжить при крушении. Улучшаем прогноз.

В прошлый раз я использовал линейную регрессию для прогнозирования того, выжил ли пассажир при крушении или нет. Точность прогноза составила 0.77, что неплохо для начала. Самыми значимыми переменными (по значению P-Value) были Sex, Fare, Age. Их я и брал в для прогнозирования.

Смотрим чего не хватает

Что делать, если для некоторых значимых переменных отсуствуют значения? Например, для поля возраст в тренировочном наборе отсутствует значение в 177 случаях:

Один из участников соревнования предложил заполнить эти значения спрогнозированными данными. Детальнее можно ознакомиться на форуме Kaggle, я же опишу как я применил его идею.

Добавляем новую колонку

От каких переменных может зависеть возраст? Возможно, что от количества детей (Parch) или братьев-сестер (Sibsp), а может стоимости билета (Fare)? Может можно из данных вытащить дополнительную информацию, которая нам помогла бы спрогнозировать возраст? Например, имя пассажира уже содержит его титул: Mr, Mrs, Miss, Master.

Написать скрипт, который из полного имени вытащит титул из имени не составит особого труда. Я написал его на питоне, точнее на его расширенной версии Anaconda, которая содержит массу нужных пакетов, в том числе модуль для чтения/записи csv файлов. Скрипт находится здесь. После обработки в файлах с тренировочными и тестовыми данными появилась колонка Title.

Считываю полученный csv файл в R:

Определяем переменные с помощью corrgram

Дальше определим, от каких переменных зависит возраст. Для этого воспользуюсь таким графиком, который называется коррелограмма (correlogram). Его я тоже нарыл на том же форуме, ссылка внизу. Реализована эта красота в пакете corrgram.
Поскольку corrgram показывает зависимости между числовыми переменными, добавлю колонку TitleNum, в которой будет числовое значение от Title:

Строю график.

Вот что получилось:

Чем насыщеннее цвет в нижней части, тем более тесная связь между переменными. Синий цвет - связь положительная, красный - отрицательная. Интересные графики в верхней части показывают эти изменения графически (чтобы отобразились графики в верхней части нужно задать параметер upper.panel=panel.ellipse ).
Например, между Pclass и Age есть сильная отрицательная связь, т.к. соответствующий цвет квадратика в нижней части темно-красный. На графике так же видно, что с уменьшением Pclass возраст пассажира увеличивается (сейчас, как и 100 лет назад первым классом в основном путешествовали старперы, студики и прочий нищеброд ютились в эконом классах).

Заполняем недостающие данные

Переменные, наиболее связанные с возрастом определили - это Pclass, SibSp и Title. Осталось заполнить отстутствующие значения и запихнуть в общую модель. Недостающие значения в тренировочных и тестовых данных я проставляю в процедуре, которую вызываю перед тем, как построить модель и делать прогноз. Вот код функции:

```{r}

predictMissing <- function(dataSet){

  #Find missing Age

  age.model = lm(Age~as.factor(Title)  + SibSp + Pclass, data=dataSet)

  fare.model = lm(Fare~Parch+Pclass, data=dataSet)

  for (i in 1:nrow(dataSet)){

    if (is.na(dataSet[i, "Age"])){

      dataSet[i,"Age"] = predict(age.model, newdata=dataSet[i,])

    }

  }

  return(dataSet)

}

```{r}

Финальный результат

После отправки новых прогнозов на Kaggle я увеличил счет на один процент(с 0.77512 до 0.78469). Немного, но главное - это полученный опыт! :)

Ресурсы

1. Пост от Wallace Campbell. https://www.kaggle.com/c/titanic-gettingStarted/forums/t/5232/r-code-to-score-0-79426
2. Anaconda, python visualization and explaration tool. https://store.continuum.io/cshop/anaconda/
3. Скрипт добавления колонки title. https://dl.dropboxusercontent.com/u/22607711/AddTitle.py
4. Пост на Kaggle форуме про корелограммы. https://www.kaggle.com/c/titanic-gettingStarted/prospector#489

Выжить при крушении. Анализ данных катастрофы "Титаник".

Все знают чем закончилась эта печальная история с трансатлантическим рейсом, который совершал "Титаник" в  апреле 1912 года. В результате крушения погибло 1495 человек, спаслось 712. Эта катастрофа стала предметом многих исследований, документальных и художественных фильмов. Создатели онлайн площадки для научного моделирования Kaggle тоже решили использовать эту историю вместе с данными о всех пассажирах Титаника для тренировочного задания.

Коротко о задании

Есть данные о 891м пассажире (в формате csv), которые содержат класс, которым путешествовал, имя, пол, возраст, цену билета и т.д. Также дана информация о том выжил ли пассажир. Это т.н. тренировочный набор данных. Вместе с тренировочными данными прилагается тестовый набор, который содержит такую же информацию о еще 418 пассажирах кроме индикатора "выжил/нет".  Необходимо предсказать кто из 418 выжил.
Более подробно о деталях можно посмотреть здесь https://www.kaggle.com/c/titanic-gettingStarted

Инструменты

Для построения модели я буду использовать R и RStudio. Ссылки для скачивания внизу. Мне удобнее работать в RStudio, чем в консоли R т.к. там наряду с возможностью выполнять команды можно создать исполняемый документ (Rmd - R Markup Document или "чистый" R). RMD - это Markup document со скриптовыми вставками на языке R, в результате выполнения которого получается HTML.

Загружаем данные

Загрузил тренировочный и тестовый наборы данных. Полный тренировочный набор разделил на данные для кросс-валидации (30% записей) и тренировочный (trainFaith). Это делается для того,чтобы затем можно было оценить эффективность модели. На тренировочных данных (trainFaith) буду "обучать" модель, а данные для кросс-валидации (cvFaith) использую для оценки.
Делал примерно так:

```{r}

set.seed(333)

l=length(train[,1]);

cvSamples <- sample(1:l,size=(l/3),replace=F)

cvFaith <- train[cvSamples,]

trainFaith <- train[-cvSamples,]

```

Определяем переменные

От чего зависит выжил пассажир или нет? Возможно, что сначала спасали женщин и детей, а может пассажиров первого класса спасали первыми? По одноименному фильму вполне можно сделать такие предположения. Тот, кто смотрел фильм, уже может считаться "экспертом" в предметной области. А что делать человеку, который ничего не слышал о Титанике? Можно использовать научный подход к определению первоначальных переменных для дальнейшего построения модели.
Для "научного" подхода я буду использовать P-Values. Очень хорошее объяснение что такое P-Values можно посмотреть на Khan Academy, набор лекций Hypothesis Testing and P-values.
Если коротко, то P-Value - это величина, которая показывает насколько принятая гипотеза не влияет на данные. Например, гипотеза: у женщин больше шансов быть спасенными при крушении. Если эта гипотеза неверна, то P-value для поля Sex по отношению к Survived будет близко к 1. К сожалению, не всегда можно сказать, что если P-value близко к 0, то гипотеза верна, т.к. на данные могут влиять другие факторы.
Самый простой способ получить эти значения в R - это "впихнуть" (по-англ. fit) данные в линейную модель и вызвать на ней функцию summary. Самая простая модель линейной регрессии, ее и возьмем:

```{r}
glm1=glm(Survived ~ Sex + Fare + Age + SibSp + Parch, data=train, family="binomial")
summary(glm1)
```
Здесь family="binomial" указана для построения логистической регрессии.
Вот что получилось. Смотрим сразу на раздел coefficients, колонка Pr:

Для построения модели возьму переменные Sex, Fare, Age и SibSp.

Обучение модели

Тут все просто. Впихиваю тренировочные данные в модель. В качестве набора - trainFaith

```{r}
predictFunction = Survived ~ Sex + Fare + Age + SibSp
glm1 = glm(predictFunction, data=trainFaith, family="binomial")
```

Прогнозирование
Используем обученную модель для предсказаний кто выжил. Встроенная функция predict делает практически все что нам надо. Параметер type="response" конвертирует значения из логарифмической шкалы в обычную. В качестве данных используем cvFaith (помним, что это 30% случайно отобранных данных из полного тренировочн набора).
Далее я создал новый набор, который состоит из 2х колонок: предсказанное значение и PassengerId.

```{r}
rawpredict=predict(glm1, newdata=cvFaith, type="response")
cvPredicted=data.frame(Survived = rawpredict, PassengerId = cvFaith$PassengerId)
head(cvPredicted)
```

Вероятность выживания в колонке Survived:

Оценка

Как известно, что выжить частично очень сложно, поэтому предсказанные значения, которые находятся в диапазоне от 0 до 1 нужно конвертнуть в 0 (не выжил) или 1 (выжил). Тут я решил выпендриться и использовать стороннюю библиотеку. Я хочу посмотреть изменится ли точность моих предугадываний, если в качестве порога я возьму число, отличное от 0.5.

```{r}

library(ROCR)

pred = prediction(cvPredicted$Survived, cvFaith$Survived)

perf <- performance(pred,"acc")

plot(perf)

```

Получился такой график:

По оси Y точность прогнозирования (accuracy), по оси X - порог. Т.е. если в качестве порога я возьму 0.8, то точность модели будет около 0.65. Выбрать 0.5 в качестве порога вполне резонно, т.к. это обеспечит максимальную точность.

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

```{r}

threshold = function (val) as.numeric(val > 0.5)

glmProd = glm(predictFunction, data=train, family="binomial")

rawpredict=predict(glmProd, newdata=test, type="response")

predicted=data.frame(Survived = threshold(rawpredict), PassengerId = test$PassengerId)

```

Запись в файл производится одной командой:

```{r}

write.table(predicted, "D:/Dropbox/kaggle/Titanic/output-R.csv", row.names=FALSE, quote=FALSE, sep=",", append=FALSE)

```

После отправки на kaggle эта модель дала точность 0.77033. Это немногим больше, если прогнозировать только по полю Sex (это дало бы 0.7655). Но для начала пойдет. 

Ресурсы

1. Язык для статистической обработки данных R
2. RStudio - IDE для R
3. P-Values https://www.khanacademy.org/math/probability/statistics-inferential/hypothesis-testing/v/hypothesis-testing-and-p-values
4. Здесь много алгоритмов моделирования : http://www.machinelearning.ru
5. Пакет ROCR http://rocr.bioinf.mpi-sb.mpg.de/
6. Исходный текст

Стоит ли проверять свои изменения перед комитом? Оцениваем сколько может стоить ошибка.

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

Цель и ожидаемый результат.

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

Выводы предидущего исследования.

Согласно нашей модели если я, как разработчик, никогда не буду тестировать свои изменения перед тем, как отдать тестировщику, то в 58% случаев это сработает и качество системы не пострадает. Если же я всегда буду прогонять предкомитные тесты, то следует ожидать качественную систему в 78%.

Приводим проценты к денежному эквиваленту.

Ок, основываясь на оптимистичных ожиданиях и субьективных оценках мы получили разницу в 20% между вероятностями "хорошей" и "плохой" сборки приложения в зависимости от того, поленюсь я или нет запустить приложение перед комитом. 

Много это или мало? Кто-то наверняка скажет, что 20% - это много и лучше бы разработчику потратить лишних 10 минут чтобы убедиться, что он отдает неполоманную систему. Однако лично мне эти проценты не позволяют делать окончательные выводы. 

Я основываюсь на следующем предположении:

Предположение

Если в большинстве случаев мои изменения "проканают", то мне незачем тратить время на тестирование. Т.е. в том случае, если я буду тестировать, то я потрачу (к примеру) 10 минут + тестировщик тоже потратит 10 минут. Если тестировщик ничего не найдет, то свои 10 минут я потратил впустую. Если же тестировщик что-то найдет, то сэкономленного мной времени должно с лихвой хватить на исправление замечаний от тестера.

Метод оценки

В предидущем исследовании мы получили вероятностые зависимости между моим действием проверять/не проверять систему  (переменная Check, дальше C) и качеством приложения, выраженном через то, переоткроется ли баг (переменная Reopen, дальше R) и найдутся ли новые ошибки (переменная Introduced new issues, дальше I).
Как же, имея вышеперечисленные вероятностные характеристики оценить мои и тестировщика трудозатраты в вариантах, когда система мной проверена (C=1) и когда не проверена (C=0)?

Я воспользуюсь методом, который применяется в алгоритме поиска оптимального решения в дереве возможных вероятных действий/состояний expectimax search. Много умных слов, но смысл попытаюсь донести на дурацком примере.

Дурацкий пример

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

Выразим эту историю в виде структуры (дерево), которую можно загрузить в алгоритм поиска. Основными элементами дерева являются: состояние (state), действие (action), вероятность перехода в новое состояние (P) и выгода (Utility). Здесь многовато новых терминов в одном предложении, поэтому вот поясняющий рисунок.

Рис 1. Дерево вероятностных состояний

В текущем состоянии (очень жарко) можно сделать 2 действия (actions): пройти мимо киоска или выпить ледяной напиток. 

• Если пройти мимо, то это заберет 10 "условных единиц" здоровья. -10 - это выгода (utility), которую мы получим, перейдя в новое состояние. Вероятность перехода (P) в это новое состояние = 1.0.
• Если выпить напиток, то тут немного интереснее и возможны следующие варианты:
• Можно заболеть с вероятностью 0.2, при этом здоровье пострадает на 100 условных единиц.
•  Может все будет хорошо и здоровье улучшится на 10 пунктов. Вероятность такого варианта 0.8.

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

Имея набор вероятных состояний с ассоциированной выгодой (utility) можно определить какое действие предпринять. Для этого нужно посчитать математическое ожидание (expected value, дальше EV) для каждого действия и выбрать то, у которого значение EV выше. Посчитать EV довольно просто - нужно сложить все возможные выгоды, умноженные на вероятности их получения:

$$EV_a=\sum_{s'}{P(s,a,s') U(s')}$$

Здесь \(EV_a\) - ожидаемая выгода действия a. \(P(s,a,s')\) - вероятность попадания в состояние s' если выбираем действие a. \(U(s')\) - выгода, которую мы получим, когда перейдем в состояние s'.

В этом примере значения EV такие:

• Если выбираем "пройти мимо": \(EV=1.0 (-10) = -10\)
• Если выбираем "выпить" \(EV=0.8*10 + 0.2 (-100) = -12\)

Если сравнить значения ожидаемой выгоды, то очевидно, что лучше не пить холодных напитков в жару (\(-10 > -12\)).

Строим дерево

Возможные состояния

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

• Изменение не принесло новых ошибок и мой фикс был успешно протестирован в новом билде (I=0 и R=0)
• Баг отрепродюсился на новом билде (R=1), но новых багов не нашлось (I=0)
• Мое изменение внесло новые баги (I=1), но изначальный баг успешно пофикшен (R=0)
• Состояние "пж"  (п="полная"): изменение не пофиксило изначальную проблему плюс оно породило новые баги (I=1 и R=1)

На рисунке изображены все возможные состояния системы, в которые она может попасть после моих потенциальных действий.

Рис 2. Возможные состояния системы после действия.

Вероятности переходов

В предидущем посте я предположил следующие вероятности для событий "Баг переоткрыт" (переменная R - Reopen) и "Внесеные новые баги" (переменная I - Introduced new issues). Для того, чтобы освежить значения вот эти таблицы из предидущего поста:

Таблица 1. Вероятность возникновения R при фиксированном C

Таблица 2. Вероятность возникновения I при фиксированном C

В таблице представлены бинарные переменные. Если значение переменной 1, то в колонке Probability указана вероятность того, что событие произойдет. Если 0, то вероятность того, что события не будет.

Например, вот как следует читать первую строчку таблицы #1:
Если проверить систему перед комитом (колонка C=1), то баг переоткроется с вероятностью 10% (R=1, Probability=0.1). 

Теперь посмотрим на возможные состояния в нашей системы (см. рис 2). Как видишь, каждое состояние - это один вариант из набора из всех возможных значений R и I. Чтобы получить вероятность перехода, нужно посчитать совместную вероятность (joint probability) возникновения событий R и I при известном C. Для этого просто перемножим соответствующие значения R и I*.

* Как только мы знаем, какое значение принимает C это делает события R и I независимыми и их совместная вероятность равна произведению вероятностей возникновения R и I.

Так, например, для действия "проверять" (To Check, где C = 1) вероятность попасть в состояние, когда изменение успешно проверено (R=0) и новых багов не обнаружено (I=0) равна \(0.9 * 0.8 = 0.72\), для C=1, R=1 и I=0 - \(0.1 * 0.8 = 0.08\) и т.д. В табличном виде это выглядит следующим образом:

Таблица 3. Совместные вероятност событий R и I при фиксированном C.

Определяем выгоду

Ок, на данным момент у нас есть варианты возможных действий (проверять/не проверять), список состояний, в которые можем попасть (см. рис 2) и вероятности попадания в новое состояние при выборе того или иного действия (см. таблицу 3). Осталось совсем немного - определить выгоду (utility) каждого из состояний.

Как можно оценить utility? Что "выгоднее" - чтобы тестировщик переоткрыл багу (R=1) или чтобы закрыл, но обнаружил новые (I=1)? Интуитивно кажется, что состояние (R=1,I=0) выгоднее чем (R=0,I=1) но насколько? Я предлагаю оценить трудозатраты тестировщика и разработчика для каждого состояния, а после расчета мат. ожидания (EV) выбрать то действие, которое его минимизирует.

Оценка трудозатрат основана исключительно на моих субъективных ощущениях, которые я иногда включаю во время планирования очередного спринта. Оценю в абстрактных и никому до конца не понятных единицах - стори поинтах *. 

Поигрю немного сам с собой в "планнинг покер" дабы получить искомые значения :). 

Стори №1. Итак, самая минимальная задача, которую можно придумать - это проверка моего изменения. Ее возьмем за 1. В случае, если это будет делать тестировщик, то он прогонит основной набор тестов, относящийся к изменению за 1 единицу времени **. Я предполагаю, что набор этих кейзов небольшой и разработчик (если он не раздолбай) запустит такой же набор у себя перед комитом.

Стори №2. Бага переоткрыта. Тестировщик прогнал базовые тесты и обнаружил, что моего изменения в билде нет. Он переоткрывает багу и, скорее всего, проведет небольшое исследовательское тестирование дабы убедиться, что симптомы проблемы не поменялись. Предположу, что объем работы такой же как и в стори №1 (т.е. 1). 

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

Стори №3. Тестировщик обнаружил новые проблемы. Скорее всего ему прийдется запустить более полный набор тестов, затем локализировать проблемы и зарепортить симптомы в виде новых багов. Предположу, что это сложнее стори №1 в 3 раза, следовательно займет 3 единицы времени.

Я уже чувствую разочарование разработчика, который находится в подобном состоянии :) Согласись, это довольно печально - пофиксить 1 баг, а взамен получить пачку новых :). Скорее всего здесь кроется что-то очень сложное, поскольку мое изменение повлияло на те части системы, о которых я и не думал во время работы. Следовательно фикс может затянуться, т.к. во всех этих кусках прийдется колупаться. Ставлю 5 сторипоинтов (упс.. сори - единиц времени :)) этой задаче.

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

** Здесь может быть некоторое противоречие с теми сторипоинтами, которыми нас учат классики. В качестве сторипоинта я беру не сложность, как это принятно, а "идеальную" единицу времени, поскольку потом буду приводить эти единицы к денежному эквиваленту. Я  исхожу из предположения, что любой тестировщик потратит 1 единицу времени на эту задачу.

*** И еще одно расхождение с классиками. Обычно историю оценивает команда (тестеры и девелоперы) и дает общую оценку. Но в целях данного трактата я разделю тестерские и девелоперские оценки. Дальше поймешь зачем я это сделал.

Вот для наглядности варианты оценок в виде таблицы

Таблица 4. Оценка трудозатрат в сторипоинтах.

Осталось посчитать выгоду каждого действия. Напомню, что выгода = математическое ожидание, которое считается как сумма вероятности события помноженное на его выгоду: \(\sum_{s'}{P(s,a,s') U(s')}\)

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

Оценка математического ожидания если программист параноидально добросовестен (C=1):

Таблица 5. Оценка трудозатрат в случае 100% проверки перед комитом.

Оценка мат. ожидания в случае абсолютного программиста-разгильдяя:

Таблица 6. Оценка трудозатрат если не делать проверок перед комитом.

Как видно из таблиц, если проверять свои изменения перед комитом, то изменение будет стоить 3.9 условных единиц - "попугаев". Если же изменения не проверять, то 4.8.

Следовательно можно было бы сделать вывод, что проверять изменения перед комитом обходится дешевле. Но раз уж мы говорим про стоимость, то давай переведем полученные мат ожидания (EV) в условные денежные единицы и посмотрим на окончательный результат.

Переводим в доллары

Здесь мы попытаемся получить оценки решений проверять/не проверять в денежном эквиваленте. Денежный эквивалент мат ожидания называется expected monetary value (EMV). На русском это звучит как-то нелепо, поэтому я буду пользоваться английским названием.

Известно, что зарплаты программистов отличаются от зарплат тестировщиков. Следовательно цена 1 единицы времени программиста не равна цене 1 единицы времени тестера. Для расчета соотношения зарплат я взял на DOU средние зарплаты по киеву QA Engineer и Software Engineer за май-июнь 2012 год. Там фигурируют такие цифры:

- Средняя зп QA Engineer с опытом 1-10 лет  = $1280

- Средняя зп Software Engineer с опытом 1-10 лет = $2000

Исходя из стредних зарплат соотношение зп программиста к зп тестера = 2000/1280 = 1.5625. Пересчитаю таблицу оценки трудозатрат из сторипоинтов в доллары *. 

Таблица 7. Относительная оценка трудозатрат в $

* Здесь я просто умножил оценки затрат для девелопера на полученное соотношение (1.5625).

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

Дальше остается расчитать EMV по известной формуле, где для подсчета Utility используем "девелоперские" и "тестерские" оценки из таблицы №7 *

Оценка EMV если программист параноидально добросовестен (C=1):

Таблица 8. Относительное значение EMV если делать проверку.

Оценка EMVв случае абсолютного программиста-разгильдяя:

Таблица 9. Относительное значение EMV если не проверять свои изменения.

* Я понимаю, что на картинках не показано как именно получаются значения Utility, поэтому в конце поста я добавил ссылку на экселевский документ, чтобы можно было детальнее разобрать этот пример. 

Выводы

Мы нашли два математических ожидания: оценили последствия безалаберности (если не проверять изменения) и абсолютной параноидальности (если всегда проверять свои изменения перед комитом). Результаты оказались не в пользу безалаберности. 

1. Во временных трудозатратах разница составляет ~ 20% (4.8 сторипоинта в случае безалаберности и 3.9 в случае паранойи)
2. В денежном эквиваленте разница между безалаберностью и паранойей составляет 10-12% (6.15 если не проверять свои изменения и 5.14 в случае проверки перед комитом). Видно, что на денежное ожидание (EMV) повлияло то, что программисты стоят дороже почти в 1.5 раза чем тестеры и экономия времени на проверке своих изменений дает такую разницу.

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

Ссылки на источники, используемые файлы

• Таблица расчетов в Excel
• Обзор рынка зарплат в Украине за май-июнь 2012
• Курс Berkley по ИИ 

Стоит ли проверять свои изменения перед комитом? Задаем вопрос к сети Байеса.

Предисловие.

На этот пост меня вдохновила профессор Дафна Коллер (Daphne Koller), которая за первую неделю курса Probabilistic Graphical Models расширила мое мировозрение простой, понятной и довольно эффективной моделью Байесовских сетей (Bayesian Network).

Цель исследования.

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

Ожидаемый результат.

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

Построение модели.

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

Итак, я могу влиять на решение проверять или не проверять приложение перед комитом.

Что зависит от моего решения делать проверку или нет? 

1. Прежде всего, если я не проверю свои изменения, то логично предположить, что увеличится вероятность того, что тестировщик попросту "переоткроет багу" (Reopen *). То есть изменения, которые я отдал на тестирование не устранили проблему (если же речь идет о новой фиче, то это адекватно тому, что новую функциональность тестировщик не увидел).
2. Возможно, что тестировщик обнаружит, что начальная проблема решена, но появились новые проблемы (Introduced new issues). То есть вместе с фиксом я наплодил кучу новых проблем.
3. На что влияют эти 2 потенциальные проблемы? Рискну предположить, что они влияют на качество системы (Quality).

* Амсори, но дальше в описании я нечаянно подменил Reopen на Reproduce.

Исходя из вышеизложенных умозаключений в стиле КО определим переменные модели.

• Check (C). Это мое решение делать проверку или нет
• Reopen (R). Это вероятность того, что тестировщик "переоткроет" баг.
• Introduced new issue (I). Это вероятность того, что тестировщик найдет новые проблемы, связанные с моими изменениями.
• Quality (Q). Качество системы

Вот и зависимости:

Мое решение делать проверку (C) влияет на вероятность того, что тестировщик переоткроет баг (R) и на то, обнаружит ли он новые проблемы (I). Обе переменные (R и I) влияют на качество системы (Q).

Изобразим это в виде диаграммы зависимостей.

Рис 1. Сеть Байеса.

Это и есть сеть Байеса. Я построил ее с помощью специальной программы SamIam.

Установка значений модели.

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

Например, я хочу посмотреть, как мое решение проверить мой фикс (C) влияет на качество (Q) через вероятность переоткрытия (R) и внесения новых багов (I).

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

КО подсказывает простые правила:

1. Если я перед комитом проверю приложение, то вероятность переоткрытия (R) очень маленькая. Вероятность внесения новых проблем (I) в этом случае тоже невысока.
2. Если я перед комитом поленюсь делать проверку, то вероятности появления событий R и I будут чуть выше. Но поскольку я доверяю юнит тестам они тоже будут небольшими.

Изобразим вероятности событий в виде таблиц.

Таблица 1. Вероятность возникновения R при фиксированном C

Таблица 2. Вероятность возникновения I при фиксированном C

В таблице представлены бинарные переменные. Если значение переменной 1, то в колонке Probability указана вероятность того, что событие произойдет. Если 0, то вероятность того, что события не будет.

Например, вот как следует читать первую строчку таблицы #1:
Если проверить систему перед комитом (колонка C=1), то баг переоткроется с вероятностью 10% (R=1, Probability=0.1). 

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

Теперь внесем эти значения в модель (с помощью той же программы SamIam)

Рис 2. Значения переменных.

На первый взгляд картинка кажется слегка сложной, но думаю после пояснений будет понятнее что на ней изображено:

1. Значения переменной C (проверка приложения). В 30% случаях я проверяю систему, в 70% - отправляю тестировщикам без проверки. Значение Yes=0.3 соответствует 30%-й вероятности проверки перед комитом. Также No=0.7 соответствует 70%-й "безответственности" :).
2. Значения переменной R.
1. Если C=Yes (если я проверяю приложение перед комитом), то в 10% бага репродюсится, в 90% - нет (значения в Yes-Reproduced и Yes-NotReproduced соответственно
2. Если C=No (если я ленюсь выполнить проверку), то в 20% бага репродюсится, в 80% - нет (значения в No-Reproduced и No-NotReproduced соответственно).
3. Значения переменной I
1. Если C=Yes, то в 20% случаев тестировщик найдет новые проблемы в 80% - нет (значения в Yes-Introduced и Yes-NotIntroduced соответственно).
2. Если C=No, то в 40% случаев тестировщик найдет новые проблемы в 60% - нет (No-Introduced / No-NotIntroduced соответственно)

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

Рис 3. Значения переменных-2. Значения Q.

Пояснения значений качества (Q)

1. Если багу переоткрыли (R=Reproduced), И
1. Если к тому же еще тестировщик нашел новые проблемы (I=Introduced), то в 1% случаев можно сказать, что качество хорошее, в 99% - нет
2. Если новых проблем не найдено (I=NotIntroduced), то качество хорошее в 40% случаев, плохое в 60%
2. Если багу не переоткрыли (R=NotReproduced), И
1. Тестировщик нашел новые проблемы (I=Introduced), то с вероятностью 0.2 система хорошего качества, соответственно 0.8 - плохого
2. Если тестер новых проблем не обнаружил, то в 99% качество хорошее и 1% - плохое

Запросы к модели.

Отступление. 
Я заранее хочу предупредить, что здесь не будет дано обьяснение того, как именно происходит "магия" и по каким принципам переменные влияют друг на друга. Это тема отдельного поста, а ищущие могут найти объяснения в первых же лекциях курса Probabilistic Graphical Models. 

Теперь самое интересное. Перейдем в Query mode и посмотрим на то, как повлияли зависимости между переменными на их значения

Событий не зафиксировано

Рис 4. Никаких событий не наблюдается.

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

• Я продолжаю делать проверку в 30% случаев. При этом
• Вероятность того, что я своими изменениями внесу новые баги 34%. I приймет значение  Introduced в 34 комитах из 100 *
• Вероятность того, что тестировщик переоткроет багу после комита 17%. R станет равным 1 в 17 комитах *
• При таких раскладах хорошее качество системы можно наблюдать в 64.42% случаев

* Ты верно обратил внимание на значения для переменных I и R (34-60 и 17-83). Незнание значения C делает эти узлы зависимыми. На интуитивном уровне я это понимаю так : если после комита появились новые баги, то, возможно это повлияет на вероятность переоткрытия старых через то, что, возможно кто-то просто забыл провести интеграционный тест.

Дальше с помощью этой модели можно попытаться ответить на следующие вопросы

Как изменится качество системы, если я никогда не буду тестировать свои  изменения перед тем, как отдать их тестировщику?

То есть я совсем разленюсь и перестану запускать приложение в интеграции. Для этого зафиксирую значение переменной C в No:

Рис 5. Совсем разленился - не тестирую в интеграции.

 Как видишь, вероятность того, что мы будем наблюдать качественную систему упала с 64% до 58%. Вроде логично. *

* Видишь, здесь переменные I и R приняли те значения, которые мы вводили изначально. Это потому, что "зафиксировав" C мы разорвали связь между I и R. То есть, если я постоянно буду забивать на локальное тестирование, то будут действовать те вероятности, которые я выдумал и записал в таблицах 1 и 2, где C=0.

Как изменится качество системы, если я всегда буду тестировать перед комитом?

Перед тем, как отдать изменение тестировщику я всегда одолеваю свое нежелание прогнать самому несколько важных интеграционных тестов. Фиксирую значение C в Yes:

Рис 6. Всегда тестирую перед тем, как отдать тестировщику.

Предполагаемый уровень качества приложения повысился. В этом варианте из 78 комитов из 100 можно ожидать сносного качества.

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

А если тестировщих обнаружил новые баги после моего комита?

Что в этом случае можно сказать о моей прилежности и добросовестности? А можно сказать, что с вероятностю 82.35% я не тестировал интеграционно свой код перед отправкой.
А как изменилось качество? КО говорит, что качество не очень. Конкретнее можно надеятсья, что только в 16% подобных ситуаций качество будет приемлемо. *

* Еще одна примечательность. Вероятность того, что бага переоткроется (R) немного увеличилась. Это потому, что знание того, какое значение приняла I (появились новые баги) повлияло на C (логично же - раз есть новые баги, то я не добросовестно отнесся к интеграционному тестированию). А поскольку вероятность того, что я тестировал свои изменения уменшилась, то и увеличилась вероятность того, что бага переоткроется.

Выводы.

Мы построили сеть Байеса чтобы проанализировать зависимости между проведением "предкомитного"  тестирования (C), вероятностями появления новых багов (I), переоткрытия старых (R) и как это влияет на качество системы (Q). 

Согласно нашей модели если я, как разработчик, никогда не буду тестировать свои изменения перед тем, как отдать тестировщику, то в 58% случаев это сработает и качество системы не пострадает. Если же я всегда буду прогонять предкомитные тесты, то следует ожидать качественную систему в 78%.
Можно предположить, что даже имея довольно оптимистичные прогнозы насчет качества моих изменений все равно влияние предкомитного тестирования довольно существенное.

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

Дальнейшие исследования.

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

Disclaimer (что по-русски означает письменный отказ от ответственности)

1. Прошу не относиться к этому исследованию, как к сколь-нибудь весомому аргументу, который может повлиять на твои методы разработки. Это всего лишь один из множества вариантов построения и оценки взаимодействия взаимозависимых элементов модели. А как известно, любая модель зависит от данных, которыми она оперирует, другими словами "garbage in - garbage out" :). К тому же и в модели тоже бывают ошибки ;)
2. Я старался избегать специальных терминов и попытался изложить идею максимально просто, но если ты нашел, что изложение слишком сложно для восприятия, то пожалуйста оставь коментарий или задай вопрос.

Ссылки на источники, исходные файлы
- Средство моделирования сетей Байеса SamIam
- Курс на Coursera Probabilistic Graphical Models
- Файл модели для SamIam можно скачать отсюда http://bit.ly/ZALP1J

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