неділя, 21 січня 2018 р.

Збірка широковживаних тестів значущості пов'язаних з нормальним розподілом

Тут я наведу декілька тестів, що працюють з нормально розподіленими даними. Це марна справа намагатись запам'ятати ці тести, натомість ви маєте бути в змозі знайти необхідний тест коли це буде потрібно.

$z$-тест

  • Використання: Чи рівні середні значення популяції і гіпотетичне середнє.
  • Дані: $x_1, x_2, \dots, x_n$.
  • Припущення: Дані - це незалежні нормальні проби: $x_i \sim N(\mu, \sigma^2)$, де $\mu$ невідоме, а $\sigma$ - відоме.
  • $H_0$: для певного $\mu_0$, $\mu = \mu_0$.
  • $H_A$: $\mu \ne \mu_0, \mu > \mu_0, \mu < \mu_0$.
  • Тестова статистика: $z = \frac{\bar{x}-\mu_0}{\sigma/\sqrt{n}}$
  • Нульовий розподіл: $f(z|H_0)$ - це густина ймовіності $Z\sim N(0,1)$.
  • $p$-значення:
    Двостороння:$p = P(|Z| > z) = 2 * (1 - \mbox{pnorm}(|z|, 0, 1))$
    Одностороння-більше:$p = P(Z > z) = 1 - \mbox{pnorm}(z, 0, 1)$
    Одностороння-менше:$p = P(Z > z) = \mbox{pnorm}(z, 0, 1)$

Одновибірковий $t$-тест

  • Використання: Чи рівні середні значення популяції і гіпотетичне середнє.
  • Дані: $x_1, x_2, \dots, x_n$.
  • Припущення: Дані - це незалежні нормальні проби: $x_i \sim N(\mu, \sigma^2)$, де $\mu$ і $\sigma$ невідомі.
  • $H_0$: для певного $\mu_0$, $\mu = \mu_0$.
  • $H_A$: $\mu \ne \mu_0, \mu > \mu_0, \mu < \mu_0$.
  • Тестова статистика: $t = \frac{\bar{x}-\mu_0}{s/\sqrt{n}}$,
    де $s^2$ - це дисперсія вибірки: $s^2 = \frac {1}{n-1} \sum_{i=1}^n \left(x_i - \overline{x} \right)^ 2$
  • Нульовий розподіл: $f(t|H_0)$ - це густина ймовіності $T\sim t(n-1)$. (t-розподіл Стьюдента з $n-1$ ступенем свободи)
  • $p$-значення:
    Двостороння:$p = P(|Z| > z) = 2 * (1 - \mbox{pt}(|z|, n-1))$
    Одностороння-більше:$p = P(Z > z) = 1 - \mbox{pt}(z, n-1)$
    Одностороння-менше:$p = P(Z > z) = \mbox{pt}(z, n-1)$

Двовибірковий $t$-тест

Випадок рівних дисперсій

  • Використання: Чи різняться середні значення двох популяцій на гіпотетичну величину.
  • Дані: $x_1, x_2, \dots, x_n$ і $y_1, y_2, \cdots, y_m$.
  • Припущення: Дані - це незалежні нормальні проби: $x_i \sim N(\mu_x, \sigma^2)$, $y_i \sim N(\mu_y, \sigma^2)$, де $\mu_x$ і $\mu_y$ невідомі, можливо різні і $\sigma$ також невідома.
  • $H_0$: для певного $\mu_0$, $\mu_x - \mu_y = \mu_0$.
  • $H_A$: $\mu_x - \mu_y \ne \mu_0, \mu_x - \mu_y > \mu_0, \mu_x - \mu_y < \mu_0$.
  • Тестова статистика: $z = \frac{\bar{x}-\bar{y} - \mu_0}{s_{\bar{x}-\bar{y}}}$,
    де $s_x^2, s_y^2$ - це дисперсі] двох вибірок, а $s_{\bar{x}-\bar{y}}$ - оцінкова дисперсія: \begin{equation} s_{\bar{x}-\bar{y}} = s_P\left(\frac{1}{n} + \frac{1}{m}\right)\label{eq:sdiff} \end{equation} де $s_P$ - об'єднана (pooled) дисперсія (cереднє зважене): \begin{equation} s_P = \frac{(n-1)s_x^2 + (m-1)s_y^2}{n+m-2} \end{equation} де кількість ступенів свободи $df = n+m-2$.
    Множник $\frac{1}{n}+\frac{1}{m}$ в \eqref{eq:sdiff} випливає з того факту, що $\mbox{Var}(\bar{x}) = \frac{\sigma_x^2}{n}$ і $\mbox{Var}(\bar{x}-\bar{y}) = \frac{\sigma_x^2}{n} + \frac{\sigma_y^2}{m} = \sigma^2\left(\frac{1}{n}+\frac{1}{m}\right)$, бо $\sigma_x = \sigma_y = \sigma$.
  • Нульовий розподіл: $f(t|H_0)$ - це густина ймовіності $T\sim t(df)$.
  • $p$-значення:
    Двостороння:$p = P(|Z| > z) = 2 * (1 - \mbox{pt}(|z|, n-1))$
    Одностороння-більше:$p = P(Z > z) = 1 - \mbox{pt}(z, n-1)$
    Одностороння-менше:$p = P(Z > z) = \mbox{pt}(z, n-1)$

Випадок відмінних дисперсій

Цей випадок майже повністю повторює випадок з рівними дисперсіями, нам лише треба змінити наші припущення і формулу для об'єднаної дисперсії.
  • Використання: Чи різняться середні значення двох популяцій на гіпотетичну величину.
  • Дані: $x_1, x_2, \dots, x_n$ і $y_1, y_2, \cdots, y_m$.
  • Припущення: Дані - це незалежні нормальні проби: $x_i \sim N(\mu_x, \sigma^2)$, $y_i \sim N(\mu_y, \sigma^2)$, де $\mu_x$ і $\mu_y$ невідомі і різні і $\sigma$ також невідома.
  • $H_0$: для певного $\mu_0$, $\mu_x - \mu_y = \mu_0$.
  • $H_A$: $\mu_x - \mu_y \ne \mu_0, \mu_x - \mu_y > \mu_0, \mu_x - \mu_y < \mu_0$.
  • Тестова статистика: $z = \frac{\bar{x}-\bar{y} - \mu_0}{s_{\bar{x}-\bar{y}}}$, де \begin{equation} s_{\bar{x}-\bar{y}} = \frac{s_x^2}{n} + \frac{s_y^2}{m},\ df = \frac{(s_x^2/n+s_y^2/m)^2}{\frac{(s_x^2/n)^2}{n-1}+\frac{(s_y^2/m)^2}{m-1}} \end{equation}
  • Нульовий розподіл: $f(t|H_0)$ - це густина ймовіності $T\sim t(df)$.
  • $p$-значення:
    Двостороння:$p = P(|Z| > z) = 2 * (1 - \mbox{pt}(|z|, n-1))$
    Одностороння-більше:$p = P(Z > z) = 1 - \mbox{pt}(z, n-1)$
    Одностороння-менше:$p = P(Z > z) = \mbox{pt}(z, n-1)$

субота, 6 січня 2018 р.

Арифметика рухомої коми

Відносні помилки і ulp'и

Обчисленням з рухомою комою властиві помилки заокруглення, тому важливо мати змогу вимірювати їх. Розглянемо формат рухомої коми з основою ($\beta$) 10 і мантисою ($p$) 4. Якщо результат обчислень з рухомою комою $3.143\times10^{-1}$,а результат із використанням нескінченної точності $0.3141$, тоді помилка рівна 2 одиницям в останній позиції (units in last place - ulp). \begin{equation} 1\mbox{ulp} = \beta\times \beta^{-p}\label{eq:ulp} \end{equation}

Якщо результат обчислень з рухомою комою лежить найближче до справжнього результата, то помилка все ще може становити $0.5$ ulp. Якщо дійсне число наближене за допомогою числа з рухомою комою, то помилка може бути завбільшки з $0.0005$ ($p=4, \beta=10$), або $\beta/2\times \beta^{-p}$.

Щоб обчислити відносну помилку, що відповідає $0.5$ ulp, зауважимо, що коли дійсне число наближається за допомогою числа з рухомою точкою $$d.\underbrace{d\dots d}_{p \mbox{ раз}}\times \beta^e,$$ то помилка може бути завбільшки з $$0.\underbrace{0\dots 0}_{p \mbox{ раз}}\beta'\times\beta^e,$$ де $\beta' = \beta/2$. Ця помилка рівна $(\beta/2)\times\beta^{-p}\times\beta^e$. Числа у вигляді $d.d\dots d\times\beta^e$ набувають значень в діапазоні $[\beta^e,\beta\times\beta^e)$. Отже, діапазон відносної помилки простягається від $\frac{(\beta/2)\times\beta^{-p}\times\beta^e}{\beta\times\beta^e}$ до $\frac{(\beta/2)\times\beta^{-p}\times\beta^e}{\beta^e}$. Скорочуючи, отримуємо такий діапазон для відносної помилки, що відповідає половині ulp \begin{equation} (\frac{1}{2}\times\beta^{-p}, \frac{\beta}{2}\times\beta^{-p}].\label{eq:re_ulp_diap} \end{equation} Таким чином відносна помилка, що відповідає одному ulp може відрізнятись на множник $\beta$. Встановлюючи $\varepsilon=(\beta/2)\times\beta^{-p}$ у значення більшої межі діапазону \eqref{eq:re_ulp_diap}, ми можемо сказати, що коли дійсне число заокруглене до найближчого числа з рухомою точкою, то відносна помилка завжди обмежена $\varepsilon$, яке ми називаємо машинним епсілон.

З того, що $\varepsilon$ може переоцінити ефект заокруглювання до найближчого числа з рухомою комою у $\beta$ разів, оцінки помилок у формулах будуть тугішими на машинах із маленьким $\beta.$

Відносна помилка при відніманні

У цьому прикладі ми використаємо той самий формат рухомої коми з основою ($\beta$) 10 і мантисою ($p$) 4. Припустимо нам потрібно порахувати різницю між $1$ і $0,9999$, в заявленому форматі вони виглядатимуть так $1.000\times 10^0$ та $9.999\times 10^{-1}$. Але для виконання арифметичних дій нам потрібно, щоб порядок у чисел був однаковим, тому друге число втратить одну цифру \begin{equation*}\begin{array}{c} \phantom{-}1.000\times 10^0\\ \underline{-0.999\times 10^0}\\ \phantom{-}0.001\times 10^0\\ \end{array}\end{equation*} Тоді як відповідь у випадку з нескінченною точністю становить $0.0001$, отже відносна помилка $\eta$, яка дорівнює різниці між двома значеннями поділеній на справжнє значення, така $$ \frac{|0.0001-0.001|}{0.0001} = \frac{0.0009}{0.0001} = 9 $$ Отже, відносна помилка може сягати $9 = \beta - 1.$

Вартові числа

Для подолання такої великої відностної помилки використовують вартові цифри (guard digits).
Теорема
Якщо $x$ і $y$ - це числа з рухомою комою у форматі з параметрами $\beta$ і $p$, і віднімання виконується із використанням одного вартового числа, тобто з $p+1$ цифрами, тоді помилка заокруглення результату менша ніж $2\varepsilon$.

Відкидання

Тут ми можемо підсумувати, що без використання вартових чисел, відносна помилка утворена через віднімання двох близьких величин може бути дуже великою. Інакше кажучи, обчислення будь-якого виразу, що містить віднімання (або додавання величин з різним знаком) може у висліді дати відносну помилку настільки вилику, що всі цифри беззмістовні. Ми розрізняємо два типи відкидання: катастрофічне і доброякісне.

Катастрофічне відкидання трапляється коли операнди були заокруглені. Наприклад, воно відбуваєтсья у виразі $b^2-4ac$. Покладемо $b = 3.345; a = 1.219; c = 2.294$. Точне значення $b^2-4ac$ рівне $0.003481$. Але $b^2 = 11.189025$ і $4ac = 11.185544$, а з урахуванням заокруглення, $b^2 = 11.19$ і $4ac = 11.19$, і їх різниця це $0$. Тобто, ми отримали помилку в розмірі 35 ulp, див. \eqref{eq:ulp}.

Доброякісне відкидання відбувається коли віднімаюємо дві точно відомі величини. Про це нам каже теорема з попереднього розділу.

Іншим прикладом формули де відбувається катастрофічне відкидання є $x^2 - y^2$, але ми можемо уникнути цього ефекту замінивши її на $(x-y)(x+y)$. Обчислення $(x-y)(x+y)$ і $x^2-y^2$ потребує приблизно однакової кількості дій, тому очевидно якій формі варто віддавати перевагу. Однак, на загал, заміна катастрофічного на доброякісне відкидання не варта зусиль якщо витрати на це занадто великі, бо входові дані часто (хоча й не завжди) є наближеними. Але повне виключення видкидання має сенс навіть якщо дані не точні.

Іншим прикладом заміни катастрофічного на доброякісне відкидання слугує формула обчислення площі трикутника через довжини сторін.

\begin{equation} A = \sqrt{s(s-a)(s-b)(s-c)}, \mbox{де} s=(a+b+c)/2\label{eq:tr_area_catas} \end{equation} Припустимо, що трикутник дуже тонкий; тобто, $a\approx b+c$. Тоді $s\approx a$, а множник $s-a$ віднімає два майже однакових числа, одне з яких містить помилку заокруглення. Але ми можемо переписати формулу \eqref{eq:tr_area_catas} так, що вона повертає акуратні результати навіть для тонких трикутників: \begin{equation} A = \frac{\sqrt{(a+(b+c))(c-(a-b))(c+(a-b))(a+(b-c))}}{4}, a\ge b\ge c \label{eq:tr_area_benign} \end{equation}

неділя, 3 грудня 2017 р.

Розподіл порядкових статистик

Статистики вибірки такі я середнє значення вибірки, квантилі вибірки, максимальне та мінімальне значення вибірки відіграють важливу роль в аналізі даних. В цьому дописі я розгляну порядкові статистики і їх розподіли. Порядкові статистики - це елементи випадкової вибірки впорядковані за зростанням. Тут я зосережусь на функції розподілу ймовірностей і густині ймовірності порядкової статистики.

В цьому дописі я розгляну лише випадкові вибірки отримані з неперервних розподілів (тобто функція розподілу ймовірностей неперервна). Нехай $X_1, \dots, X_n$ - це випадкова вибірка розміру $n$ з неперервного розподілу з функцією розподілу ймовірностей $F(x)$. Впорядкувавши цю вибірку у зростному порядку отримуємо $Y_1, \dots, Y_n$.

Порядкова статистика $Y_i$ називається $i$-тою порядковою статистикою. Тут ми припускаємо, що $Y_1 < Y_2 < \dots < Y_n$, тобто збігів бути не може.

Функція розподілу ймовірностей

Якщо має місце подія $Y_i \le y$ тоді ми знаємо, що щонайменше $i$ з $X_j$ лежать ліворуч від $y$. Розглянемо подію, що $Y_j \le y$ як успіх, тоді має місце $n$ проб Бернуллі з імовірністю успіху $F(X \le y)$. Нас цікавить імовірність мати не менше ніж $i$ успіхів: \begin{equation} F_{Y_i}(y) = P(Y_i \le y) = \sum_{k=i}^n\binom{n}{k}F(y)^k(1-F(y))^{n-k} \label{eq:cdf} \end{equation}

Густина ймовірності

Для знаходження густини ймовірності нам знадобиться така формула: \begin{equation} F_{Y_i}(y) = F_{Y_{i-1}}(y) - \binom{n}{i-1}F(y)^{i-1}(1-F(y))^{n-i+1} \label{eq:cdf_diff} \end{equation} Я одразу наведу формулу густину ймовірності, а потім ми доведемо її індукційно. \begin{equation} f_{Y_i}(y) = \frac{n!}{(i-1)!(n-i)!}F(y)^{i-1}(1-F(y))^{n-i}f_X(y)\label{eq:pdf} \end{equation} Почнемо з бази індукції. Розглянемо $i = 1$. Отже, нас цікавить іморність того, що хоча б одна проба менша ніж $y$. Доповняльною подією буде те, що усі проби більші ніж $y$. Тому, $F_{Y_1}(y) = (1 - F(y))^n$. Для отримання густини ймовірності нам потрібно обчислити похідну: $$f_{Y_1}(y) = n(1 - F(y))^{n-1}f_X(y)$$ Припустимо, що ми довели \ref{eq:pdf} для $Y_{i-1}$: $$f_{Y_{i-1}}(y) = \frac{n!}{(i-2)!(n-i+1)!}F(y)^{i-2}(1-F(y))^{n-i+1}f_X(y)$$ Тепер розглянемо випадок для $Y_i$. Тут нам можна скористатись рівнянням \ref{eq:cdf_diff}: \begin{align*} f_{Y_i}(y) &= f_{Y_{i-1}}(y)\\ &\phantom{=}-\binom{n}{i-1}(i-1)F(y)^{i-2}f_X(y)(1-F(y))^{n-i+1}\\ &\phantom{=}-\binom{n}{i-1}F(y)^{i-1}(n-i+1)(1-F(y))^{n-i}f_X(y) \end{align*} Трошки алгебри і правий бік рівняння перетвориться в \ref{eq:pdf}.

Коментар

Розглянемо другу половину \ref{eq:pdf}: $$F(y)^{i-1}f_X(y)(1-F(y))^{n-i}$$ тут перший множник - це імовірність, що $i-1$ проб менші ніж $y$, другий - імовірність, що одна проба поблизу $y$ і третій - імовірність, що $n-i$ проб більші ніж $y$. Таким чином \ref{eq:pdf} - це такий мультиноміальний розподіл: \begin{equation} f_{Y_i}(y) = \frac{n!}{(i-1)!1!(n-i)!}F(y)^{i-1}f_X(y)(1-F(y))^{n-i}\label{eq:pdf_multi} \end{equation}

четвер, 2 листопада 2017 р.

Двоїстість у лінійному програмуванні

Згадаємо формулювання прямої і двоїстої програм у стандартній формі.
\begin{align} \text{максимізувати}\ &\vec{c}^T\vec{x}\\ \text{за умов}\ &A\vec{x}\le \vec{b}\\ &\vec{x}\ge 0 \end{align} \begin{align} \text{мінімізувати}\ &\vec{b}^T\vec{y}\\ \text{за умов}\ &A^T\vec{y} \ge \vec{c} \label{eq:dual_constr}\\ &\vec{y}\ge 0 \end{align}

Фізичне тлумачення

  • Застосувати поле $\vec{c}$ до кульки в середині обмеженого багатогранника $A\vec{x} \le \vec{b}$.
  • Зрештою, кулька зупиниться біля краю багатогранника (в точці $\vec{x}'$).
  • Грань $\vec{a}_i\vec{x}'\le b_i$ накладає певну силу $-y_i\vec{a}_i$ на кульку.
  • Кулька стабільна, тому $\vec{c}^T = \sum_i y'_i\vec{a}_i = \vec{y}'^TA$.
  • Двоїстість можна уявити як намагання мінімізувати "роботу" $\sum_i y_ib_i$, щоб перенести м'ячик у початок координат рухаючи багатогранник.
  • В оптимальній позиції тиснуть лише стіни суміжні з кулькою. (На рисунку лише $y_1, y_2$ не нульові.)
Звернемо увагу на те, що на кульку тиснуть лише грані до яких вона притуляється. Тобто для кожного $i$, або вона перебуває на лінії $\vec{a}_i^T \vec{x} = b_i$ або тиск дорівнює нулю: \begin{align} \vec{a}_i\vec{x} = b_i, y_i > 0&\ \text{торкається грані, тиск є} \label{eq:compslack1}\\ \vec{a}_i\vec{x} < b_i, y_i = 0&\ \text{не торкається грані, тиску немає}\label{eq:compslack2} \end{align} Тепер покажемо, що наш $\vec{x}'$ і є оптимальним розв'язком. Згідно з принципом слабкої двоїстості $\vec{c}^T\vec{x} \le \vec{b}^T\vec{y}$. Отже, якщо ми покажемо, що $\vec{c}^T\vec{x}' = \vec{b}^T\vec{y}'$, то це і є оптимальний розв'язок. Cтабільність кульки разом із третім законом Ньютона даюсть нам, що $A^T \vec{y}' = \vec{c}$. Завдяки рівнянням (\ref{eq:compslack1}, \ref{eq:compslack2}) ми можемо записати, що $\vec{a}_i\vec{x}'y'_i = b_iy'_i$, а отже $$\vec{c}^T\vec{x}' = \vec{x}'^T\vec{c} = \vec{x}'^TA^T\vec{y}' = (A\vec{x}')^T\vec{y}' = \sum_i\vec{a}_i\vec{x}'y'_i = \sum_i b_iy'_i = \vec{b}^T\vec{y}'$$ Отже, $\vec{x}'$ - оптимальний розв'язок, а $\vec{y}'$ - двоїстий до нього.

Економічне тлумачення

Розглянемо задачу оптимального виробництва:
  • $n$ продуктів, $m$ сирих матеріалів.
  • Продукт $j$ потребує $a_{ij}$ одиниць сирого матеріалу $i$.
  • Всього доступно $b_i$ одиниць матеріалу $i$.
  • Продукт $j$ дає $c_j$ прибутку на одиницю.
  • Майстерня хоче максимізувати прибуток за наявних матеріалів
\begin{matrix} \text{максимізувати}&\vec{c}^T\vec{x}&\\ \text{за умов}&\vec{a}_i^T\vec{x}\le b_i,&\ i = 1, \dots, m.\\ &x_j\ge 0,& j = 1,\dots,n. \end{matrix} Якщо задача розв'язна і розв'язок скінченний, то допустима область - це опуклий багатогранник. Завжди існує щонайменше одна вершина в якій цільова функція набуває оптимального значення. Для задачі оптимального виробництва це означає, що для $n$ продуктів і $m$ сирих матеріалів, існує оптимальний план з щонайбільше $m$ продуктами.

Тлумачення двоїстих змінних

Для кожної одиниці продукту $j, j \in \{1,n\}$, нам потріно $a_{ij}, i \in \{1, m\}$. Для того, щоб було вигідно випускати продукт, його ціна має бути не меншою ніж сумарна ціна всіх складових. Позначимо ціну продукту через $c_p(j)$ і ціну матеріалу через $c_m(i)$, тоді $$c_p(j) \ge \sum_i a_{ij} c_m(i)$$ Але ж з точністю до знаку це те саме, що і обмеження двоїстої програми (\ref{eq:dual_constr}). Поглянемо на це з іншого боку. За умови що $\vec{x}$ і $\vec{y}$ оптимальні розв'язки відповідно прямої і двоїстої задач згідно з принципом сильної двоїстості маємо: $$\vec{c}^T\vec{x}=\vec{b}^T\vec{y}$$
  • Ліворуч маємо максимальний виторг.
  • Праворуч - $\sum_i (\text{наявність матеріалу}\ i) \times (\text{виторг на одиницю матеріалу}\ i)$
Інакше кажучі: Значення $y_i$ в оптимумі - це двоїста ціна ресурсу $i$.

Якщо ж значення не оптимальні, тобто

$$\vec{c}^T\vec{x}<\vec{b}^T\vec{y}$$ Розв'язок не оптимальний, бо ресурси не використані повністю.

субота, 7 жовтня 2017 р.

Найкоротший шлях у графі. Рішення через прямий-двоїстий алгоритм.

Розглянемо добре знайому задачу знаходження найкоротшого шляху. Маючи зв'язний граф $G = (V, E)$, цінову функцію $\omega: E \to R_+$ і дві вершини $s$ і $t$, знайти шлях найменшої вартості, що сполучає ці дві вершини в $G$. Цю задачу можна ефективно розв'язати за допомогою алгоритма Дейкстри. Але тут ми побудуємо прямий-двоїстий алгоритм, що ефективно обчислить найкоротший шлях.

Введемо такі позначення: $\mathcal S = \{ S \mid S \subset V, s \in S, t \notin S\}$ і, для кожної множини $S \subset V$, через $\delta(S)$ позначимо множину ребер, що мають одну вешину в $S$, а другу в $V\setminus S$.

Для цього ми роглянемо лінійну програму в формі. Взагалі-то, нам потрібно, щоб $x_e$ набували лише ${0,1}$, але цілочисельні лінійні програми NP-складні, тому ми ослаблюємо програму до нецілочельної лінійної програми. \begin{align} \min \sum_{e\in E}x_e\cdot\omega(e) \end{align} за умови, що \begin{align} \forall S \in \mathcal{S}, \sum_{e\in \delta(S)} x_e\ge 1\\ \forall e \in E, x_e \ge 0 \end{align} Наступний крок - це створення двоїстої лінійної програми. Для того, щоб це зробити спочатку згадаємо як виглядає лінійна програма в стандартній формі: \begin{align*} &\max \sum_{j=1}^n c_j x_j\\ \text{за умови, що}&\sum_{j=1}^n a_{ij}x_j \le b_i, i = 1,2,\dots, m\\ &x_j \ge 0, j = 1,2, \dots, n \end{align*} Часто зручніше записувати в матричному вигляді: \begin{align*} &\max c^Tx\\ \text{за умови, що}&\ Ax \le b, x \ge 0 \end{align*} Тоді двоїста програма така: \begin{align*} &\min b^T y\\ \text{за умови, що}&\ A^Ty \ge c, y \ge 0 \end{align*} Тепер ми можемо записати двоїсту програму:
\begin{align} \max \sum_{S\in\mathcal{S}}y_S \end{align} за умови, що \begin{align} \sum_{S:e\in \delta(S)} y_S\le c_e, \forall e \in E \label{eq:dual_constraint}\\ \forall S \in \mathcal{S}, y_S \ge 0 \end{align} Тобто, тепер ми максимізуємо суму нових зміних $y_S$. У (\ref{eq:dual_constraint}) ми для кожного ребра, сумуємо $y_S$ з усіх $S$, що перетинають це ребро.

Алгоритм

Роглянемо такий алгоритм:
  1. $F\gets \varnothing$
  2. $y \gets 0$
  3. Допоки в $F$ ще нема шляху, що поєднує $s$ і $t$
    • Нехай $C$ - компонента зв'язності графу $G' = (V, F)$, що містить $s$
    • Збільшити двоїсту змінну $y_C$ так, щоб вперше виконалось $\sum\limits_{S \in \mathcal{S}~:~e \in \delta(S)} y_S = w(e')$
    • Додати $e'$ до $F$
  4. Повернути шлях $P$ з $F$, що поєднує $s$ і $t$.

Коректність

На кожній ітерації ми збільшуємо іншу $y_S$, бо $C$ постійно змінюється. Отже виконання алгоритму завершиться не пізніше ніж через $|V|$ кроків.

Перебіг виконання

Спочатку сформулюємо лему, яка нам допоможе зрозуміти як виконується алгоритм.
Лема
На кожному кроці алгоритму множина $F$ - це дерево.
Важливо, що ми повертаємо не все дерево, а лише шлях, що поєднує дві вершини. Читач може переконатись, що порядок додавання ребер в дереву той самий, що й у алгоритму Дейкстри.

субота, 23 вересня 2017 р.

Геометричний погляд на перцептрони

Двопогоровий нейрон

  • Спочатку обчислити зважену суму входових даних від інших нейронів (плюс зсув).
  • Тоді видати 1, якщо зважена сума більше нуля.
\begin{equation}\label{eq:z_def} z = b + \sum_i x_i w_i \end{equation} \begin{equation}\label{eq:y_def} y = \begin{cases} 1, \mbox{якщо}\ z \ge 0\\ 0, \mbox{інакше} \end{cases} \end{equation} Тут ми не зважатимемо на зсув, бо ми можемо розглядати зсув як вагу для ще одного входового елементу, що постійно дає 1.

Простір-ваг.

  • Цей простір має один вимір на кожну вагу.
  • Вектор (точка) в цьому просторі представляє якийсь набір ваг.
Припускаючи, що ми не зважаємо на зсуви, ми можемо розглядати кожен тренувальний випадок як гіперплощину крізь початок координат. Ваги мусять лежати з одного боку цієї гіперплощини, щоб відповідь була правильною.
Погляньмо, що ж це означає матиематично. припустимо, що у нас на вході є вектор з координатами $\vec{v} = (a, b)$. Щоб цей вектор повертав правильну відповідь, згідно з \ref{eq:z_def} і \ref{eq:y_def} нам потрібно, щоб $\vec{v}\cdot\vec{w} \ge 0$. Тут $\vec{w}$ - це вектор ваг з координатами $(x ,y)$. Тобто, нам треба, щоб $ax+by \ge 0$. Якщо переписати нерівність як $y = -\frac{a}{b} x$, то стає зрозуміло, що підхожі набори ваг лежать з боку цієї гіперплощини куди вказує входовий вектор.

Конус допустимих розв'язків

Щоб ваги працювали з усіма тренувальними випадками, нам потрібно знайти точку з парвильного боку для всіх гіперплощин. Такої точки може й не бути. Якщо ж вона існує, то вона лежить в гіперконі з вершиною в початку координат. Отже, середнє між двома хорошими векторами ваг також хороший вектор ваг. Це означає, що проблема опукла.

Процедура навчання

Вибираємо тренувальні випадки за алгоритмом згідно з яким зрештою ми переберемо усі тренувальні випадки.
  • Якщо вихід правильний, залишаємо ваги без змін.
  • Якщо результат - це помилковий 0, додаємо входовий вектор до ваг.
  • Якщо результат - це помилкова 1, віднімаємо входовий вектор від ваг.
Ця процедура гарантує знаходження набору ваг, який видає правильний резльтат для всіх тренувальних випадків, якщо такий набір існує.

Чому процедура працює

Розглянемо піднесену до квадрату відстань $d_a^2+d_b^2$ між будь-яким допустимим вектором ваг і поточним вектором ваг. Нам би хотілось щоб кожного разу коли перцептрон помиляється ми наближали поточний вектор ваг до всіх допустимих векторів ваг. Але це не так. Тому ми розглянемо щедро допустимі вектори ваг, що лежать в допустимомій області із відступом не менше ніж довжина входового вектора, який визначає гіперплощину-обмеження.

Кілька слів про доведення

  • Кожного разу перцептрон помиляється, поточний вектор ваг змінюється, щоб зменшити відстань до кожного вектора ваг зі щедро допустимої області.
  • Піднесена до квадрату відстань зменшується щонайменша на квадрат входового вектора.
  • Отже, після скінченної кількості ітерації, вектор ваг мусить лежати у допустимій області, якщо така існує.

Приклад програми, що реалізує цей алгоритм навчання.

Тут я подаю приклад програми, яка вчиться розрізняти лінійно роздільну множину. Насправді більшість коду - це виведення графіки в gif-файл.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
ds = [1 1; 2 -2; -1 -1.5; -2 -1; -2 1; 3 -1];
class = [1 -1 -1 -1 1 1];

ds_neg = ds(class==-1,:);
ds_pos = ds(class==1,:);

w = [0 1 0.5]';
eta = 0.2;

count = size(ds, 1);

y = @(w, x) -(w(2)*x+w(1))/w(3);

h = figure;
epoch = 0;
% тут ми припускаємо, що множини лінійно роздільні, тому
% ми зупинимось лише коли не буде помилок
stillMistakes = true;
while stillMistakes
    for i = 1:count 
        x = [1 ds(i, :)];
        if class(i) * x * w < 0
            w = w + class(i) * eta * x';
        end

        hold off
        plot([-5, 5], [y(w, -5), y(w, 5)]);
        title(strcat('епоха', {' '}, num2str(epoch)));
        hold on
        scatter(ds_neg(:,1), ds_neg(:,2), 'o');
        scatter(ds_pos(:,1), ds_pos(:,2), '+');
        plot(x(2),x(3), 'o', 'MarkerSize',15);
        axis([-5, 5, -5, 5]);

        drawnow
        frame = getframe(1);
        im{epoch * count + i} = frame2im(frame);
    end
    epoch = epoch + 1;
    
    % як множину для перевірки ми використовуємо усю тренувальну множину
    stillMistakes = false;
    for i = 1:count
        x = [1 ds(i, :)];
        if class(i) * x * w < 0
            stillMistakes = true;
            break
        end
    end
end
close;

fn = 'linearlySeparable.gif';
for idx = 1:(epoch * count)
    [A,map] = rgb2ind(im{idx},256);
    if idx == 1
        imwrite(A,map,fn,'gif','LoopCount',Inf,'DelayTime',1);
    else
        imwrite(A,map,fn,'gif','WriteMode','append','DelayTime',1);
    end
end

субота, 9 вересня 2017 р.

Нотатки на курс "Вступ до комплексного аналізу"

Аналітичність

Теорема
Нехай $f = u + iv$ визначена в області $D \subset C$. Тоді $f$ - аналітична в $D$ ТТТ, якщо $u(x, y)$ і $v(x, y)$ мають неперервні перші частинні похідні в $D$, які задовольняють рівнянням Коші-Рімана.

Інтегрування

Означення
Нехай $D \subset C$ буде областю визначення і нехай $f : D \to C$ буде неперервною функцією. Первісна $f$ у $D$ - це аналітична функція $F : D \to C$ така, що $F' = f$ у $D$.
Теорема
Якщо $f$ - це неперервна функція в області $D$ і, якщо $f$ має первісну $F$ в $D$, тоді для будь-якої кривої $\gamma : [a, b] \to D$ маємо, що $$\int_{\gamma}f(z)dz = F(\gamma(b)) − F(\gamma(a)).$$

Коли $f$ має первісну?

Теорема (Коші для трикутників)
Нехай $D$ буде відкритою множиною в $C$ і нехай $f$ буде аналітичною в $D$. Нехай $T$ буде трикутником, що вміщається в $D$ (включно з границею) і нехай $\delta T$ буде його границею, орієнтованою позитивно. Тоді $$\int_{\delta T}f(z)dz = 0.$$
Теорема (Морери)
Якщо $f$ неперервна у однозв'язній області $D$ і, якщо $\int_{\gamma}f(z)dz = 0$ для кожної трикутної кривої в $D$, тоді $f$ має первісну в $D$.
Теорема (Ґурсата)
Нехай $D$ буде однозв'язною областю в $C$, і нехай $f$ буде аналітичною в $D$. Тоді $f$ має первісну в $D$. Більше того, первісна задається явно вибором точки $z_0 \in D$ і покладенням $$F(z) = \int_{z_0}^z f(w)dw,$$ де інтеграл береться по довільній кривій в $D$ від $z_0$ до $z$.
Теорема (Коші для однозв'язних областей)
Нехай $D$ буде однозв'язною областю в $C$ і нехай $f$ - аналітична в $D$. Нехай $\gamma : [a, b] \to D$ буде кусково гладкою, замкнутою кривою в $D$ (тобто $\gamma(b) = \gamma(a)$). Тоді $$\int_{\gamma}f(z)dz = 0.$$
Наслідок
Нехай $\gamma_1$ і $\gamma_2$ - це дві прості замкнуті криві (тобто жодна з них не перетинає саму себе), орінтовані проти годинникової стрілки, при чому $\gamma_2$ всередині $\gamma_1$. Якщо $f$ аналітична в області $D$, яка містить обидві криві і область між ними, тоді $$\int_{\gamma_1}f(z)dz =\int_{\gamma_2}f(z)dz.$$
Теорема (інтегральна формула Коші)
Нехай $D$ - це однозв'язна область, обмежена кусково гладкою кривою $\gamma$, і нехай $f$ аналітична на множині $U$, що містить в собі замкнення $D$ (тобто $D$ і $\gamma$). Тоді $$f(w) = \frac{1}{2\pi i}\int_{\gamma} \frac{f(z)}{z-w}dz$$ для всіх $w \in D.$
Теорема
Якщо $f$ аналітична у відкритій множині $U$, тоді $f'$ також аналітична в $U$.
Теорема (інтегральна формула Коші для похідних)
Нехай $D$ - це однозв'язна область, обмежена кусково гладкою кривою $\gamma$, і нехай $f$ аналітична на множині $U$, що містить в собі замкнення $D$ (тобто $D$ і $\gamma$). Тоді $$f(w)^{(k)} = \frac{k!}{2\pi i}\int_{\gamma}\frac{f(z)}{(z − w)^{k+1}}dz$$ для всіх $w \in D, k ≥ 0$.
Це дуже захоплююча теорема, бо для обчислення значення $f$ або її похідної в будь-якій точці з області обмеженої кривою $\gamma$ нам необхідно знати лише значення функції на самій кривій.
Теорема (оцінка Коші)
Припустимо, що $f$ аналітична у відкритій множині, що містить $B_r(z_0)$, і що $|f(z)| \le m$ виконується на $\delta B_r(z_0)$ для деякої сталої $m$. Тоді для всіх $k \ge 0$, $$|f^{(k)}(z_0)| \le \frac{k!m}{r^k}.$$
Теорема (Ліувілля)
Нехай $f$ аналітична на всій комплексній площині. Якщо $f$ обмежена, тоді $f$ мусить бути сталою.
З цієї теореми випливає, що раз $\sin z$ аналітична на всій комплексній площині і вона не костантна, то значить, що вона сягає $\infty$ в якомусь напрямку. І дійсно, такий напрямок може бути $ni$.
Теорема (Принцип максимума)
Нехай $f$ аналітична в $D$ і припустимо, що існує точка $z_0 \in D$ така, що $|f(z)| \le |f(z_0)|$ для всіх $z \in D$. Тоді $f$ константна в $D$.
Наслідок
Якщо $D \subset C$ - це обмежена область і якщо $f : D \to C$ неперервна і аналітична в $D$, тоді $|f|$ досягає максимума на $\delta D$.

Ряди

Означення
Точка $z_0$ - ізольована сингулярність $f$ якщо $f$ - аналітична в проколотому диску $\{0 < |z − z_0| < r\}$ з центром $z_0$.
Означення
Припустимо, що $z_0$ це ізольована сингулярність аналітичної функції $f$ з рядом Лорана $$\sum^{\infty}_{k=−\infty} a_k (z − z_0)^k, 0 < |z − z_0| < r.$$ Тоді сингулярність $z_0$ є
  • усувною, якщо $a_k = 0$ для всіх $k < 0$.
  • полюсом, якщо існує $N > 0$ таке, що $a_{−N} \neq 0$, але $a_k = 0$ для всіх $k < −N$. Індекс $N$ - порядок полюса.
  • істотною, якщо $a_k \neq 0$ для нескінченної кількості $k < 0$.
Теорема (Касораті-Веєрштраса)
Припустимо, що $z_0$ це істотна сингулярність $f$. Тоді для кожної точки $w_0 \in C$ існує послідовність $\{z_n\}$ із $z_n \to z_0$ така, що $f(z_n) \in w_0$ коли $n \to ∞$.
Означення
Якщо $f$ має ізольовану сингулярність в $z_0$ з таким рядом Лорана $$f(z) = \sum^{\infty}_{k=−\infty} a_k (z − z_0)^k, 0 < |z − z_0| < r$$, тоді лишок $f$ в $z_0$ це $\operatorname{Res}(f, z0) = a_{-1}$.
Теорема (про лишки)
Нехай $D$ буде однозв'язною областю і нехай $f$ аналітична $D$, окрім як в ізольованих сингулярностях. Нехай $C$ - проста замкнута крива в $D$ (орієнтована проти годинникової стрілки), і нехай $z_1, \dots , z_n$ - ізольовані сингулярності $f$, які лежать поза $C$. Тоді $$\int_C f(z)dz = 2\pi i\sum_{k=1}^n \operatorname{Res}(f, z_k)$$.
  • Лишок в усувній сингулярності дорінює $0$.
  • Лишок в полюсі можна знайти за формулою $$\operatorname{Res}(f, z_0) = a_{−1} = \frac{1}{(n − 1)!} \lim_{z\to z_0}\frac{d^{n−1}}{dz^{n−1}}\left((z − z_0)^nf(z)\right).$$