Архив рубрики: Наука

Разберемся с измерением случайных величин (ч. 2/4)

Основная терминология

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

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

Distribution function, Сumulative distribution function, c.d.f.  Функция распределения, Функция распределения вероятностей, Интегральная функция распределения вероятностей – функция, характеризующая распределение случайной величины. Записывается как F(x) и обозначает вероятность того, что после выполнения эксперимента случайная величина X получит значение, не превышающее число x. Математически это записывается как
F(x) = P(X \leq x), -\infty < x < +\infty

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

Дискретная (от лат. disctretus – прерывистый) случная величина может принимать только определенный набор значений.

Например, результат бросания монеты может быть только орел или решка.

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

Возвращаясь к примеру из первой части, время открытия веб-страницы – это непрерывная случайная величина.

Помимо функции распределения вероятности для описания случайной величины вводятся функция вероятности и плотность вероятности. То есть и плотность распределения, и функция вероятности, и функция распределения, всё это есть одна из форм закона распределения, а закон распределения – это просто общий термин для описания случайной величины.

Probability massProbability mass functionp.m.f. – Функция вероятности – функция, описывающая распределение дискретной случайной величины. Записывается как множество значений, которые может принять случайная величина, и соответствующие им вероятности. Например, для монеты p_1=0.5, p_2=0.5, где p_1 – вероятности выпадения орла и p_2 – решки.

С функцией вероятности у меня остается один непонятный момент. Почему функцию распределения плотности вероятности для дискретной случайной величины назвали именно «функция вероятности»? Это же очень похоже на изначальное понятие «функция распределения вероятностей»? Надеюсь, кто-нибудь из читателей меня просветит.

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

Probability densityProbability density functionp.d.f  – Плотность вероятности, Функция плотности вероятности – функция, описывающая распределение непрерывной случайной величины. Кстати, да, «density» дословно переводится как «плотность». Плотность вероятности записывается как f(x) . Математически плотность вероятности является производной от функции распределения вероятностей:

f(x)=F'(x), -\infty < x < +\infty.

Соответственно, функцию распределения вероятностей можно выразить через плотность:

F(x)=P(X\in[\infty,x])=\int\limits_{-\infty}^{x} f(x)dx

Если словами, то функция распределения вероятности для значения x равна вероятности принятия случайной величины значения от минус бесконечности до x.

Само обозначение «плотность» взято из механики. В этой интерпретации функция f(x) буквально характеризует плотность распределения масс по оси абсцисс (ось x):

Стоит отметить, что в литературе часто пишут не «функция распределения непрерывной случайной величины», а «функция непрерывного распределения случайной величины». Тут может быть путаница, хотя все имеют в виду одно и тоже. Просто кто-то говорит о самой случайной величине, а кто-то – о её распределении. Соответственно, у непрерывной случайной величины – непрерывное распределение.

Виды распределений

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

  1. F(x)\in[0;1], потому что не может быть отрицательной вероятности и вероятности больше единицы;
  2. F(x_1)\le F(x_2),x_1<x_2, т.е. функция неубывающая, потому что чем больше совокупность случайных событий, тем более вероятно их наступление;
  3. \lim_{x\to -\infty}=0, \lim_{x\to +\infty}=1 по той же причине, что и п.2.
В википедии можно найти по меньшей мере 30 различных законов распределения случайных величин. Разберем одно из самых популярных распределений – нормальное, или распределение Гаусса.

Нормальное распределение

О нем говорилось в прошлой части, но теперь, когда вам знакомы понятия функции и плотности распределения, мы можем рассмотреть его в новом свете!
Плотность распределения записывается следующим образом:
В принципе, саму формулу запоминать нет особого смысла, главное запомнить, что в ней присутствуют два параметра, которые влияют на форму распределения (см. график ниже): \mu (мю) – среднее значение (математическое ожидание), указывает «центр» «купола», и \sigma^2 (сигма) – дисперсия (рассеивание), влияет на «толщину» купола. Сигму не в квадрате называют среднеквадратическим отклонением.
Выглядит плотность вероятности f(x) так:
Рассматривая на графике красную линию, можно сказать, что наиболее вероятное значение – это ноль, вероятность которого примерно равна 0.9.
Используя интерактивную консоль ipython с поддержкой построения графиков мы можем легко построить такие же графики сами (надеюсь, вы установили дистрибутив The Enthought Python Distribution из предыдущей части)!
Для начала запустите ipython в консоли командой «ipython —pylab». Затем введите следующий код:
from scipy.stats import norm
import numpy as np

x = np.linspace(-5,5,100)
plot(x, norm.pdf(x))
Вы получите следующий график:

Краткий итог

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

Смотрите в следующей серии

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

Разберемся с измерением случайных величин (ч. 1/4)

Задача: определить, сколько раз необходимо провести измерения производительности веб-сервиса, чтобы быть уверенным в полученных результатах на 95%.

Эта серия записей не претендует на звание статьи, методического пособия или еще чего-то. Я хочу рассказать об измерениях случайных величин просто, «на пальцах». Так, чтобы даже без знания теории вероятности после прочтения записи было бы всё понятно и можно было бы попробовать свои силы на практике.

Для начала необходимо признать один простой факт – результат любого измерения – это случайная величина. В моём случае результат измерения среднего времени обработки запросов веб-сервисом – случайнее вдвойне!)

Тут в дело не только в погрешности оборудования клиента и сервера, сети, но и во времени суток! В «час пик» среднее время обработки запроса может быть значительно больше. И тут в игру вступают условные вероятности. Впрочем, стоп. Сегодня пройдемся только по простому измерению без всяких условных факторов.

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

# coding:utf-8

import httplib
import time

for i in range(10):
    conn = httplib.HTTPConnection("ag.ru")
    conn.request("GET", "/")
    start_time = time.time()
    r1 = conn.getresponse()
    latency = time.time() - start_time
    print("Время обработки запроса: {0}мс".format(round(latency * 1000)))

И получите примерно такой результат:

Время обработки запроса: 14.0мс
Время обработки запроса: 10.0мс
Время обработки запроса: 10.0мс
Время обработки запроса: 10.0мс
Время обработки запроса: 15.0мс
Время обработки запроса: 9.0мс
Время обработки запроса: 14.0мс
Время обработки запроса: 9.0мс
Время обработки запроса: 10.0мс
Время обработки запроса: 11.0мс

Обозначим прописной буквой X возможное время обработки запроса, маленькой же буквой x обозначим конкретные принимаемые значения времени обработки запроса. Для приведенного примера для сайта http://ag.ru X может принимать значения от 9 до 15 мс, для первого измерения x_1=14мс.

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

Для запуска нового кода вам понадобится установленная библиотека matplotlib, которую в простейшем случае можно установить с помощью команды в консоли pip install matplotlib. Я же рекомендую скачать полный набор необходимых библиотек, который содержится в Enthought Python Distribution (тут и numpy, и matplotlib, и еще немало полезных и часто используемых библиотек), дистрибутив которого разработчики подготовили для всех популярных платформы (Windows, MacOS, Linux).

Код обновленной программы будет следующий:

# coding:utf-8

import httplib
import time
import matplotlib.pyplot as plt

latencies = []
for i in range(100):
    conn = httplib.HTTPConnection("habrahabr.ru")
    conn.request("GET", "/")
    start_time = time.time()
    r1 = conn.getresponse()
    latency = round((time.time() - start_time) * 1000)
    latencies.append(latency)
    print("Время обработки запроса: {0}мс".format(latency))

plt.hist(latencies, 50)
plt.title(u"Гистограмма времен обработки запросов")
plt.xlabel(u"Задержка")
plt.ylabel(u"Частота")
plt.show()

И получим следующий график:

Гистограмма времен обработки запросов для сайта habrahabr.ru

Какие же выводы мы можем сделать из этого графика? Получается, чаще всего вы сможете увидеть главную страницу сайта habrahabr.ru где-то спустя 900 мс, вероятность такого события самая высокая, поскольку именно за 900 мс +- несколько десятков миллисекунд согласно нашим измерениям мы 20 раз получали главную страницу! Также есть небольшие вероятности, что страница загрузится или за 100 мс, 200 мс и т.д.

Наша гистограмма весьма похожа на нормальное распределение! Нормальное распределение – это такое распределение случайной величины, где есть единственное наиболее вероятное значение случайного события – среднее значение, или математическое ожидание. Вероятности принятия случайной величиной других значений плавно убывают симметрично относительно среднего значения. Нормальным его называют потому, что именно такое распределение чаще всего встречается в природе. Например, рост человека – это случайная величина с нормальным распределением. Чаще всего вы встретите на улице человека с ростом 170-180 см, но есть же и люди с ростом 155 см и под два метра.

В самом обычном случае нормальное распределение выглядит так (разные формы получаются с помощью вариации двух основных параметров нормального распределения: математического ожидания и дисперсии):

Конечно, разные веб-сервисы будут по разному выглядеть на такой гистограмме, и здесь нам весьма повезло, что получили близкую к канонической форме «купола» нормального распределения.

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

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

  1. Кельтон В., Лоу А. Имитационное моделирование. Классика CS. 3-е изд. – СПб.: Питер; Киев: Издательская группа BHV, 2004.-847 c:ил.
  2. Спирин H.A. Методы планирования и обработки результатов инженерного эксперимента : Конспект лекций. / H.A. Спирин, В.В. Лавров. Екатеринбург : ГОУ ВПО УГТУ-УПИ, 2004. — 257 с.

Используемое программное обеспечение (ПО)

  1. Язык программирования Python
  2. Библиотека построения графиков matplotlib в составе дистрибутива The Enthought Python Distribution

Shogun Machine Learning Toolbox

Для решения ряда задач понадобилась хорошая библиотека с алгоритмами машинного обучения. Shogun Machine Learning Toolbox – оказался как раз именно тем проектом. Он активно разрабатывается, участвует в Google Summer of Code, имеет приличный багаж алгоритмов и интерфейсов доступа.

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

Ниже привожу список ошибок и их решения.

Traceback (most recent call last):
 File "svm_train.py", line 85, in <module>
 my_classifier()
 File "svm_train.py", line 55, in my_classifier
 output = svm.apply()
 File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/modshogun.py", line 20755, in apply
 return _modshogun.MultiClassSVM_apply(self, *args)
 SystemError: [ERROR] assertion m_svms[i] failed in file classifier/svm/MultiClassSVM.cpp line 134

Неверный формат labels. Должны быть от 0 (нуля).

 

Traceback (most recent call last):
File "svm_train.py", line 87, in <module>
 classifier_libsvmmulticlass_modular(*parameter_list)
 File "svm_train.py", line 80, in classifier_libsvmmulticlass_modular
 kernel.init(feats_train, feats_test)
 File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/modshogun.py", line 16415, in init
 return _modshogun.Kernel_init(self, *args)
 SystemError: [ERROR] train or test features #dimension mismatch (l:11 vs. r:5)

Неверный формат features.

 

error: No matching function for overload
error: called from:
error: /../svm_train_pred_vis.m at line 81, column 14

Неверный формат labels.

Для каждого языка программирования свои задачи, или выводы «9 лет спустя»

Окидывая взглядом последние 9 лет практики программирования, я пришел к ряду интересных и, думаю, полезных выводов. Свою историю изучения языков программирования (далее «ЯП») проиллюстрировал ниже. Где-то отметил фреймворки на этих ЯП. Отмеченные фреймворки, как правило, давали новую мотивацию и открывали новые горизонты в изучении и использовании этих ЯП.

Языки программирования по жизни

Языки программирования по жизни

Вывод 1: для разных классов задач – разные языки программирования

В действительности, достаточно хорошо изучив какой-либо язык, кажется, что на нём надо писать не только профильные приложения. Но будьте осторожны! На этом пути вы можете впасть в состояние «вбивания гвоздей микроскопом». Так рождаются демоны (постоянно висящие процессы, типа серверов) на PHP, веб-сервера на JavaScript, веб-приложения на C++ и прочее. В качестве эксперимента – это прекрасно, но всё становится гораздо ужасней, когда что-то в силу своей популярности в другой области становится частым решением в других.

Хорошим примером иллюстрирующим первый вывод является node.js и Erlang. На node.js с радостью накинулось большое число веб-разработчиков, ведь все знают JavaScript! Попробовав домашние проекты на этой платформе, многие начали использовать node.js в реальных проектах и в итоге столкнулись с большими проблемами, решение которых затрачивало всё больше сил. Например, отказоустойчивость таких приложений. Стоит вылезть ошибке в одном из потоков выполнения, и весь сервер падает, если только вы не оградились везде, где только можно try-catch блоками. Или горизонтальное масштабирование. Тут вообще беда. И рождаются костыли-костыли-костыли.

Другое дело Erlang, который изначально «by-design» создавался для больших телекоммуникационных систем. Писать на нём серверное приложение — сплошное удовольствие. Хотите постоянно работающий сервер, которым можно управлять по telnet? Да легко! Держите встроенный пакет gen_tcp. Горизонтальное масштабирование существующего приложения? Вам скорей всего придется поменять пару строчек, где описывается передача сообщений другим функциям, — добавить в них отправку сообщений на другие ноды. Тоже и с отказоустойчивостью (привет супервизорам), обработкой бинарных данных и пр. пр.

Вывод 2 – не упускайте возможности изучать новые ЯП и/или их популярные фреймворки

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

Существует две основные когорты ЯП:

  1. Си-подобные: С++, С#, Java, PHP, JavaScript, ActionScript и др.
  2. LISP-подобные: Erlang, Python, Ruby, Perl и др.

Если вы знаете хотя бы один язык из каждого класса, то считайте, что вы знаете и все остальные ЯП.) Исключениями можно считать Assembler и языки-приколы, типа Brainfuck. Кстати, часто различить эти классы ЯП можно по наличию/отсутствию кортежей и обрамлению условных операций и циклов в фигурные скобки.

Я не стал разбивать на группы ООП, функциональные и процедурные парадигмы программирования, т.к. по большому счету почти любой подход можно использовать почти в любом языке (например, функциональный подход в Java). Другое дело, что язык изначально для этого не создавался (см. вывод 1;-) и такие извороты выглядят крайне противоестественно. Исключение Python. Он изначально разрабатывался мульти-парадигмальным.

Мой топ-рейтинг открытий типа: «А-а-а! Так вот с помощью чего это надо было делать!»:

1.  Zend Framework (на PHP)

Ну нафига я писал свою глючную библиотеку для работы с БД? О боги, а зачем я каждый раз придумывал новую архитектуру для каждого нового веб-приложения? MVC, Zend_Db, Zend_Action даруют возможность писать веб-приложения быстрее, а код делать надежным!

2.  Erlang

Боже! Ну почему я потратил кучу времени на написание этого простого демона на Java, если в Эрланге это можно было сделать парой десятков строчек, да и работало бы безотказно, да и масштабировать было бы проще!

3.  Octave

Так, надо бы быстрое преобразование Фурье… О, Matlab! Ну что, пошли на страшное преступление в ближайший торрент-трекер. Хотя ладно, вот есть бесплатная библиотечка для любимого PHP. Эхх…что-то как-то всё грустно и медленно. Octave? Octave… Octave! Мега-удобный синтаксис работы с матрицами, встроенные функции для кучи математических задач, да тут еще и графики с пол пинка строятся! Да оно еще совместимо с MatLab! А еще open-source!

4.  KnockoutJS (на JavaScript).

Как же мне надоели эти простыни с кодом, запутанная логика работы с объектами на странице, эти бесконечные onSomeEvent функции. Как бы хотелось MVC, но вот только на клиенте. Чтобы вот есть у тебя модель данных и при её изменении автоматически всё само менялось на странице. Добавил к ней объект «Задача», а на странице возьми и появись соответствующий блок для новой задачи.

KnockoutJS, как ты вовремя!

5.  Django (на Python)

Да-да, Zend Framework, ты не плох, но ты… рутинный. Каждый раз надо писать свою админку, прикручивать авторизацию, свои однотипные операции добавления, редактирования и удаления сущностей, расписывать формы ввода данных, писать однотипные виды для типичных задач, типа показа по 10 новостей на одной странице и разбивках остальных новостей по страницам. Copy-paste, copy-paste…

Ммм… что-то зачастили на хабре со своими дифирамбами во славу Django и Python.  Да давно уже поют, который год. Что ж они всё никак не угомонятся?) Ну попробуем и мы.

Так-так… значит я раскомментирую вот тут и вот тут, еще одна команда в консоли и… у меня готова полноценная админка?! Вы издеваетесь?) Так просто! А вот еще бы хотелось, чтобы в админке было удобно приписывать к разным авторам разные статьи, чтобы было красивая связь многим-ко-многим. Добавить одну строку в модель?! Ну-у, у вас совсем нет совести! Зачем же я столько времени тратил на эту рутину в зенде?»

Для этой записи хватит выводов, а то, ведь, до конца не дочитаете!) Оставим еще парочку на будущее.)

Основные программы, которые я использую в работе (v.2)

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

Для написания статей

Google Chrome – быстрый, надежный и защищенный браузер, всегда его всем рекомендую. Вот и опять.) Но интересен не только сам браузер, но и дополнения, которые я использую с ним. Основные это:

  • Evernote Clipper – позволяет одним кликом скопировать в Evernote (см. ниже, что это такое) статью на веб-странице. Есть механизм определения границ статьи, чтобы в блокнот не попадали реклама, комментарии и прочее. Привычки сохранять интересные статьи хорошо начинает вырабатываться, когда вспоминаешь о каком-то нужном материале в Интеренте, а его уже там нет.
  • Evernote Clearly – при нажатии на кнопку Cleary статья приображается, остается только самое необходимо для чтения статьи, увеличивается шрифт, текст центрируется и т.д. Статьи в интернете становится очень удобно читать.
  • Google Task – позволяет работать со списком задач в Google Task.
  • Chrome to Phone – позволяет скидывать ссылку на веб-страницу на телефон, чтобы можно было потом посмотреть. Использую, чтобы прочитать интересные статьи, когда еду на работу.

Zotero – практически главное открытие позапрошлого года. Программа позволяет вести учет библиографических ссылок и легко формировать библиографию в документах Word и OpenOffice. Присутствует синхронизация с сервером, что позволяет использовать программу как и с помощью локальных программ, так и с помощью веб-интерфейс.


Совсем недавно у них еще появилось отдельное настольное приложение (раньше работало как плагин к Firefox) и очень удобный помощник для Chrome, позволяющий автоматически создавать библиграфические ссылки, находясь на странице работы на таких веб-сайтах как Springer, arXiv.org и многих других. В общем must have для всех тех, кто имеет дело с библиграфией.

LibreOffice (ранее OpenOffice) – open-source набор офисных программ. Несмотря на устаревший интерфейс, практически полностью хватает для решения многих задач.

Google Docs – онлайновый пакет офисных программ, аналог LibreOffice. Очень удобен для совместной работы над документами.

Evernote – супер органайзер заметок. Есть настольные, веб- и мобильные версии приложения. С помощью Evernote Clipper for Google Chrome можно, нажав только одну кнопку, сохранить часть или всю веб-страницу в заметки. Очень полезно во время сбора информации, да и вообще, чтобы всегда иметь под рукой полезные статьи и заметки.

Dropbox – отличное облачное хранилище файлов. Храню в нем файлы нужных материалов и документы, относящиеся к своей работе. Функцию общих папок используем в лаборатории для хранения файлов, которые могут понадобится всем.

Xmind – open-source настольная программа для составления ментальных карт. Отличное кросс-платформенное решение на базе Eclipse. Ментальные карты часто помогают изобразить цельную картину какой-либо задачи, представить структуру сайта, расписать этапы проекта.

Cacoo – аналог xmind, только работа происходит через веб-интерфейс. Использую для создания прототипов интерфейсов. На работе используем для совместной работы над интерфейсом, что возможно благодаря функции общих документов.

Для программирования

Eclipse – open-source среда разработки, в которой есть ВСЁ.) Абсолютно достаточно для программирования на любом языке и для решению любых задач. Все это возможно благодаря огромной коллекции расширений. Одним из самых любимых является Remote Systems Explorer – sftp, ftp, ssh и пр. клиент для работы с удаленным серверами.

Linux-консоль – часто многие задачи типа компиляции, настройки и пр. быстрее решить с помощью консоли, а с удаленном сервером вообще работать по-другому никак.)

Timeout – программа напоминает дать отдых глазам. Много программ не напишешь, если угробишь глаза перед монитором.) Есть куча аналогов для любых платформ, а в Ubuntu даже подобная программа встроена в интерфейс изначально.)