четверг, 27 июля 2017 г.

Игра на определение изоморфных графов

Сделал игру на JS и HTML.
Среди трех вариантов нужно находить граф, изоморфный данному на скорость.
Ссылка на игру — http://isomorphism-game.xpast.me/

воскресенье, 31 января 2016 г.

Dota 2: статистика винрейтов по длительности матча

В течении нескольких недель я собирал статистику матчей по всем героям. Обычный winrate можно посмотреть на dotabuff.com. Но обычный winrate не имеет какого-то осмысленного значения. Я построил графики winrate/duration, т.е. сила героя в зависимости от продолжительности матча, которые, на мой взгляд, более интересны. Вот примеры:

Тут уже отчётливо можно отличить саппортов от керри, а также прослеживаются другие интересные моменты.
Полная ститистика доступна по ссылке - http://imgur.com/a/aSHTu

четверг, 21 января 2016 г.

Логистическая регрессия: как оценить $P(y | x_1, ..., x_n)$, зная $P(y | x_1, ..., x_{k-1}, x_{k+1}, ..., x_n)$

Допустим, есть следующая проблема: есть набор данных и мы считаем какую-то статистику. Допустим, для любого $k \in [1, ..., n]$ по исходным данным мы можем посчитать $P(y | x_1, ..., x_{k-1}, x_{k+1}, ..., x_n)$, но не можем посчитать $P(y | x_1, ..., x_n)$, т.к. исходных данных слишком мало. Как оценить $P(y | x_1, ..., x_n)$ через $n-1$-элементные подмножества?
Обозначим
$$p_{1,...,n} = P(y | x_1, ..., x_n)$$
$$p_{1,...,k-1,k+1,...,n} = P(y | x_1, ..., x_{k-1}, x_{k+1}, ..., x_n) = \overline{p_k}$$
Давайте применим модель логистической регрессии. Нам известно, что
$$p_{1,...,n} = P(y | x_1, ..., x_n) = \frac{1}{1 + e^{-(t_1 + ... + t_n)}}$$, где $t_i = \beta_i x_i$ для некоторого $\beta_i$, т.е. $\ln \frac{p_{1,...,n}}{1 - p_{1,...,n}}=t_1 + ... + t_n$ (линейно зависит от $n$ переменных).
Тогда $\overline{p_k}$ зависит от $n-1$ переменной, а именно
$$\overline{p_k} = \frac{1}{1 + e^{-(t_1 + ... + t_{k-1}+ t_{k+1} + ... + t_n)}}$$
$$\ln \frac{\overline{p_k}}{1 - \overline{p_k}}=t_1 + ... + t_{k-1}+ t_{k+1} + ... + t_n$$

Тогда

$$\sum_{k=1}^{n} (t_1 + ... + t_{k-1}+ t_{k+1} + ... + t_n) = (n-1)(t_1 + ... + t_n)$$

Действительно, суммируем $n-1$-подмножества $n$-элементного множества, значит каждый элемент $t_k$ "отсутствует" ровно один раз. С другой стороны

$$\sum_{k=1}^{n} (t_1 + ... + t_{k-1}+ t_{k+1} + ... + t_n) = \sum_{k=1}^{n} \ln \frac{\overline{p_k}}{1 - \overline{p_k}}$$

И получаем, что

$$\sum_{k=1}^{n} \ln \frac{\overline{p_k}}{1 - \overline{p_k}} =  (n-1)(t_1 + ... + t_n)$$

Откуда

$$t_1 + ... + t_n = \frac{\sum_{k=1}^{n} \ln \frac{\overline{p_k}}{1 - \overline{p_k}}}{n-1}$$

Подставляем это в выражение для $p_{1,...,n}$ и получаем окончательную формулу:

$$p_{1,...,n} = \frac{1}{1 + (\prod_{k=1}^{n} \frac{1-\overline{p_k}}{\overline{p_k}})^{\frac{1}{n-1}}}$$