Записи с меткой «математика»

Интуиция и Байесовские сети

23.05.2012

Помимо краткого курса по теории игр я записался еще на курс, который называется «Probabilistic Graphical Models», что можно перевести как «Вероятностные графические модели». На самом деле речь там идет в основном о Байесовских и Марковских сетях. В этом курсе также встречаются очень простые модели, которые тем не менее хорошо описывают окружающую действительность. Об одном таком примере, который меня очень впечатлил, хочу вам рассказать.

В качестве иллюстрации возьмем известную историю о племяннице губернатора Кубани. Суть ее в том, что молодая девушка, студентка, является владелицей крупного бизнеса, при этом дядя ее – губернатор Краснодарского края. Одни скажут: что такого, может, она очень умная и имеет недюжие предпринимательские способности? Но большинство говорят: это ей дядя подсобил. Но если спросить большинство, почему они отметают идею о ее уме, они только пожмут плечами: это ведь очевидно!

А на самом деле у этой интуитивной уверенности есть строгое математическое обоснование. Итак, допустим, у нас есть случайная величина, показывающая, имеет ли произвольная молодая девушка крупный бизнес. Эта величина зависит от двух других случайных величин (на самом их число конечно больше, но в нашей модели их будет две): «девушка умна» и «ее дядя губернатор». Ведь если девушка умна, то вероятность того, что у ней есть крупный бизнес выше, чем вероятность того, что бизнеса у ней нет. И если ее дядя губернатор, то (во всяком случае в современной России) вероятность того, что бизнес у нее есть много выше вероятности обратного. Мы только что построили простейшую Байесовскую сеть. Изобразим ее графически, ведь это графическая вероятностная модель!

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

С первыми двумя переменными все понятно. Вероятность родиться умной 10%, глупой 90%. Это конечно взято с потолка, но суть отражает. Аналогично с вероятностью иметь дядю губернатора. А вот последняя вероятность выглядит сложнее. Это так называемая условная вероятность. Она показывает, какая вероятность иметь или не иметь бизнес при разных условиях. Например, если ты умная, но у тебя нет дяди губернатора, то вероятность иметь бизнес равна 70%. А если ты глупая, но дядя твой губернатор, то вероятность 80%. Если умная и с дядей – 90%, глупая и без дяди – 10%. Числа опять же произвольные, но между собой более или менее согласованные.

Теперь начинается самое интересное. Фигура, когда две стрелочки сходятся книзу в одну переменную, называется V-структура (потому что похожа на латинскую V). Известно, что если нижняя переменная («Имеет бизнес») неизвестна, то две другие переменные не зависят друг от друга. То есть, мы не можем ничего сказать о предпринимательских способностях девушки, зная, что ее дядя губернатор, и наоборот. Но если эта переменная известна, то две другие переменные становятся зависимыми, то есть коррелируют друг с другом. Этот эффект называется probabilistic influence. Посмотрим, как он проявляется.

Зададим в нашей модели, что бизнес имеется.

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

Вероятность наличия предпринимательской жилки уменьшилась и стала около 10% (все вероятности программа рассчитывает сама, решая уравнения, так что там все довольно строго). То есть наша уверенность в том, что девушка честно заработала свои миллионы уменьшилась в три раза от того, что мы узнали, кто ее дядя. Это и есть эффект зависимости родительских переменных в V-структуре, если значение дочерней переменной известно.

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

,

Пробки и теория игр

14.05.2012

В связи с успешным окончанием курса по теории игр хочу рассказать еще об одной простой модели, хорошо иллюстрирующей наш мир. В оригинале она называется «Tradegy of commons», что можно перевести как «Трагедия общин», хотя я бы перевел как «Трагедия (драма) общежития», ибо общинами сейчас уже почти не живут, а вот в общежитиях – запросто.

Итак, рассмотрим типичную ситуацию: две дороги сливаются в одну. Пропускная способность слияния падает по мере увеличения интенсивности вливающихся потоков машин. В предельном случае, когда машин очень много, все встают, образовывается мертвая пробка. Пусть из каждого рукава идет поток в q_i машин в час. Допустим также, что пропускная способность падает линейно и равна S = 300-\sum\limits_{i=1}^n q_i (конкретные значения констант сейчас не важны, важна сама идея). В нашем случае n=2. Тогда из каждого потока за час проедет q_iS = q_i(300-q_i-q_{-i}), где q_{-i} – другой поток. Каждый поток будет стараться максимизировать свое количество проехавших машин. Приравняем производную по q_i к нулю, чтобы найти максимум:

300-2q_i-q_{-i}=0

Отсюда

q_i=150-q_{-i}/2

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

q_{eq}=150-q_{eq}/2

Откуда

q_{eq}=100

То есть в равновесии, к которому будут стремиться участники движения, из каждого потока будет въезжать по 100 машин в час. Посмотрим, сколько из них проедет слияние:

q_{eq}S = 100(300-100-100)=10000

Не нужно удивляться, что проедет больше чем въехало. Число 10000 означается лишь, что въехавшие 100 машин проедут слияние быстрее, чем за час, а конкретнее за 100/10000=1/100 часа. Теперь попробуем максимизировать не количество проехавших машин в каждом рукаве, а общее число машин, проехавших через слияние. Обозначим общий въезжающий поток через q_{total} = q_1+q_2, тогда число машин, проехавших через слияние будет

q_{total}S = q_{total}(300-q_{total})

Возьмем производную по q_{total} и приравняем к нулю для поиска максимума:

300-2q_{total} = 0

Отсюда q_{total}=150. Опять-таки в силу симметричности ситуации для все участников

q_{total} = q_1 + q_2 = 2q_{op}, где q_{op} – оптимальный поток из каждого рукава.

Значит, q_{op} = 150/2=75. Видим, что в этом случае интенсивность каждого потока меньше. Посмотрим, как изменилось количество проехавших через слияние машин для каждого потока:

q_{op}S=75(300-75-75)=11250

Оно выросло! Таким образом получается, что если все участники договорятся, что будут ехать с меньшей интенсивностью, то в результате каждый из них проедет быстрее. В этом-то и заключается трагедия. С ростом числа участников игры ситуация только ухудшается, и в пределе без регулирования равновесная скорость движения каждого участника будет близка к нулю, тогда как при наличии регулирования она будет весьма высокая. Что собственно мы и наблюдаем в пробках.

,

Революция и теория игр

20.04.2012

Я сейчас изучаю стэнфордский курс «Теория игр» и не перестаю удивляться, как достаточно простые модели хорошо описывают окружающую действительность. Возьмем относительно недавнее выступление Навального на митинге в Москве. Он сказал примерно следующее: «Мы можем занять Кремль уже сейчас, но не собираемся этого делать, так как мы мирный народ.» Что эта фраза значит в терминах теории игр?

Пусть у нас есть два игрока, условно, Навальный и Путин. У игрока Навальный есть две стратегии: штурм Кремля или ничего не делание. У Путина в ответ на действия Навального также есть две стратегии: подавление штурма или капитуляция. Если Навальный штурмует и Путин капитулирует, Навальный выигрывает, Путин проигрывает. Если Навальный штурмует, и Путин подавляет штурм, Навальный проигрывает. Но выигрывает ли в этом случае Путин? Тут нужно сделать одно допущение, чтобы наша моделька заработала. Допустим, при подавлении Путин проигрывает больше, чем при капитуляции: кровавая бойня, шок у западных партнеров, волнения в стране и так далее. Всего этого можно избежать, если в случае активных действий оппозиционеров попытаться договориться, «заболтать», как он умеет, и так далее.

Итак, мы только что описали нашу игру в нормальной форме. Запишем ее в виде таблицы.

             Путин
          Подавление Переговоры
Навальный
Штурм       -1, -2     1, -1
Нет          0,  0     0,  0

Игрок номер 1 – Навальный, номер 2 – Путин. В клетках таблицы указаны выигрыши игроков. И вот что получается. Состояние (Нет, Подавление) является устойчивым (равновесие Нэша), так как ни одному из игроков не выгодно из него выходить. Если Навальный пойдет на штурм (передвинется вверх по таблице), то его выигрыш изменится с 0 до -1, то есть уменьшится. Если Путин пойдет на переговоры (сместится вправо), то его выигрыш останется равным нулю, то есть он индифферентен в данном случае. Поэтому обоим игрокам выгодно находится именно в этой позиции, то есть играть с такими стратегиями. Именно поэтому Навальный не идет на штурм. Однако, конкретно в этой игре есть еще одно состояние равновесия! Посмотрим на клетку (Штурм, Переговоры). Навальному нет смысла ее покидить, так как его выигрыш уменьшится с 1 до 0. И Путину также не выгодно менять стратегию, иначе его выигрыш уменьшится с -1 до -2. То есть это еще одно равновесие, еще один вероятный сценарий развития событий. Проблема в том, что если ты уже находишься в равновесии (Нет, Подавление), то выйти из него крайне сложно, так как это ведет к уменьшению выигрыша.

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

,

О пользе наук

18.10.2011

Недавно на собеседовании мне предложили несколько задачек, среди которой была задача о шарах. Вы, возможно, знаете ее, формулировка у ней такая. В корзине лежит m белых и n черных шаров. Из нее наугад вынимают 2 шара. Если шары одного цвета, то в корзину возвращают белый шар, если разного, то черный. Считается, что есть достаточное количество белых шаров вне корзины для их возврата в случае постоянной выемки пар из двух черных шаров. Вопрос: можно ли, зная числа m и n, заранее сказать, какой шар в корзине останется последним?

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

Сначала я снова начал бродить вокруг тех же безрезультатных идей, которые у меня были на собеседовании. Но потом вдруг вспомнил о недавнем чтении ТФКП и придумал вот что. Пусть общее число шаров в корзине соответствует некому комплексному числу z = x + iy, причем действительная часть показывает количество белых шаров, а мнимая — черных. Если вынули два белых шара и затем один вернули, то в корзине останется x + iy-2 + 1 = (x-1) + iy. Если вынули два черных и вернули белый, то в корзине будет x + iy-2i + 1 = (x + 1) + i(y-2). И, наконец, если вынули белый и черный и вернули черный, в корзине останется x + iy-1-i + i = (x-1) + iy. Видно, что третий случай эквивалентен первому. Кроме того, общее число шаров (x + y) на каждом шаге уменьшается ровно на единицу, то есть в конечном итоге действительно останется только один шар. Таким образом, при очередной выемке к текущему числу шаров прибавляют либо число z_1 = -1, либо z_2 = 1-2i.

Пусть до того, как в корзине остался один шар, сделали k выемок по z_1 и l выемок по z_2 (k, l — неотрицательные целые). Тогда возможно два варианта: m + in + kz_1 + lz_2 = 1, если последний шар белый, и m + in + kz_1 + lz_2 = i, если последний шар черный.

Вообще, сами комплексные числа тут особо не нужны, нужно только их представление на комплексной плоскости, т. е. можно вполне обойтись обычными векторами. Пусть (m, n) — вектор, задающий начальное состояние корзины. Тогда конечное состояние можно представить в виде суммы начального вектора и линейной комбинации векторов (-1, 0) и (1, -2).

Таким образом, векторные уравнения распадаются на пары скалярных:

m + (-1)\cdot k + l = 1 \\n + 0\cdot k + (-2)\cdot l = 0, если последний шар белый, и

m + (-1)\cdot k + l = 0 \\n + 0\cdot k + (-2)\cdot l = 1, если последний шар черный.

Отсюда видно, что n = 2l для белого шара и n = 2l + 1 для черного. То есть если начальное число черных шаров четное, то последним останется белый шар, если нечетное — то черный. Это и есть ответ.

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

,

Снова в школу

13.09.2011

Под впечатлением от Фейнмана я испытал жгучую необходимость вернуть хотя бы часть тех знаний, которые в меня пытались вложить преподаватели одного их лучших технических ВУЗов страны. Почему-то начать мне захотелось с ТФКП, возможно, из-за того, что этот предмет я почти полностью пропустил мимо ушей.

После некоторых размышлений я приобрел «Конспект лекций по высшей математике» господина Письменного Д. Т. Помимо ТФКП там есть и линейная алгебра, и аналитическая геометрия, и вещественный анализ и теория поля. Для изучения с нуля столь сжатое изложение, конечно же, не подходит, а вот для восстановления утраченных знаний — в самый раз. Я начал читать с самого начала, вспомнил матрицы, векторы и принялся за матан.

Интересно, что по мере чтения возникают вопросы, которые не возникали во время учебы в институте. Например, почему определитель матрицы и модуль вектора, оба обозначаются двумя вертикальными чертами, нет ли тут глубинного смысла? И каков вообще физический смысл определителя? И ответ находится в следующем разделе: геометрический смысл определителя — ориентированный объем многомерного параллелепипеда, образованного из векторов-строк (или столбцов) матрицы. В принципе, модуль вектора — тоже в каком-то смысле его одномерный объем, так что связь прослеживается.

И снова P=NP

07.06.2011

У Романова появился конкурент из Бразилии. Правда, насколько я понял, у него пока даже нет работающей программы для решения 3-SAT.

ЭВМ/ Статистический анализ нагрузки хранилища данных

21.03.2011

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

(далее…)

, ,

Если бы Ферма жил сегодня…

10.02.2011

Амазон выпустил обновление прошивки для своих Kindle. Помимо всего прочего появилась возможность оставлять публичные заметки к читаемой книге, которые могут видеть другие люди. Представляете, едет Ферма в электричке, читает на своем Kindle 3G «Арифметику» Диофанта. Доходит до разложения квадрата на сумму квадратов и делает пометку:

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

Это сразу же попадает в Twitter, тысячи ретвитов, в Facebook начинаются бурные обсуждения, и к моменту, когда Ферма выходит из электрички на Курском вокзале, какой-нибудь неизвестный индийский студент публикует ссылку на свое доказательство этой теоремы.

,

P=NP

20.01.2011

А вы уже осилили доказательство, что P=NP? Некий Романов В. Ф. с своей статье утверждает, что нашел полиномиальный алгоритм для решения NP-полной задачи 3-SAT, что в свою очередь означает, что P=NP, и мы все умрем. Есть даже реализация предложенного алгоритма на Java.

Реакции ученого мира пока нет, так что будем следить за новостями.

ЭВМ/ Расчет производительности хранилища данных

08.11.2010

В наше время глобализации, виртуализации и облачных технологий одним из краеугольных камней любой серьезной IT инфраструктуры становится общее хранилище данных. Это может быть как традиционные NAS или SAN, так и специализированная система вроде Amazon Dynamo. При этом при проектировании инфраструктуры первым встает вопрос оценки требуемой производительности хранилища. Конечно, в архитектуру всегда стараются заложить возможность легкого масштабирования, чтобы наращивать производительность по мере надобности. Однако это не отменяет полностью задачу первоначальной оценки.

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

(далее…)

, ,

ЭВМ/ Высокие нагрузки

26.10.2010

Просыпаюсь я в понедельник, не рано, умываюсь, не спеша готовлю завтрак. Размышляю о том, как не хочется ехать на работу. И тут я понимаю, что на работу ехать не надо! А надо ехать на «Highload», конференцию, посвященную высоким нагрузкам в Интернете. Понятно, что 90% высоких нагрузок в Интернете — это популярные веб-сайты для школьников и скучающих офисных работников. В принципе вся эта кухня мне не особо интересна, но некоторые технические аспекты бывают любопытны. Кроме того на таких мероприятиях можно продуктивно пообщаться на отвлеченный темы. Например мы пытались придумать систему счисления с основанием «пи». Поняли, что для начала нам нужно придать смысл фразе «сделать что-то 3.14 раз». Подняли аксиоматику натуральных чисел, но никуда не продвинулись. Наконец обратились за помощью в Гугл и выяснили интересные вещи. Системы с иррациональным основанием изучал некий Бергман, при этом в качестве основания он использовал «золотое сечение», «тау» — ((sqrt(5) + 1)/2 (извините, лень доставать латех). В его системе любое целое число раскладывается в сумму целых степеней «тау». Системы с трансцендентными основаниями (в частности «пи») изучал Кнут, но его работу я так и не смог найти. Полагаю, что в системе с основанием «пи» целое число должно раскладываться в какой-то бесконечный многочлен по степеням «пи». Ясно, что понятие «цифра» в таких системах теряет смысл.

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

,

И немедленно вывел

15.07.2010

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

,