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

• гистограмма
• ящик с усами

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



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

Скрытые модели/цепи Маркова одни из подходов к представлению данных. Мне очень понравилось как обобщается множество таких подходов в этой статье.

В продолжение же моей предыдущей статьи описания скрытых моделей Маркова, задамся вопросом: откуда взять хорошую модель? Ответ достаточно стандартен, взять неплохую модель и сделать из нее хорошую.

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

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



Интересный метод, описан в статье «A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition» L.R. Rabiner, которая вводит модель скрытой цепи Маркова и описывает три ценных алгоритма: The Forward-Backward Procedure, Viterbi Algorithm и Baum-Welch reestimation. Несмотря на то, что эти алгоритмы представляют интерес только в совокупности, для большего понимания описывать их лучше по отдельности.

Занимаясь разработкой алгоритмов, постоянно одергиваю себя, а вдруг изменения, которые работают на небольшом примере, привнесут разброд и шатание в результаты на других, больших данных. Тогда мне на помощь приходит командная строка. Самое ужасное, что каждый раз реализовывать парсер аргументов уже надоело, а значит, не последним средством для C++ программиста оказывается пакет program_options из библиотеки boost.

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

Но предположим, что у нас «нечестная» кость и грани выпадают неравномерно. Пусть наша кость имеет K граней, и вероятность выпадения грани . При этом выполняется естественное ограничение . Постараюсь ответить на вопрос: как смоделировать псевдослучайную последовательность с таким распределением?